Operating system memo

处理机调度是多道程序操作系统的基础,是操作系统设计的核心问题。

作业调度的主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个(或多个)作业,给它(们)分配内存、输入/输出设备等必要的资源,并建立相应的进程,使它(们)获得竞争处理机的权利。

内存调度是将暂时不能运行的进程调至外存等待,把此时的进程状态称为挂起态。

进程调度的主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给它。

IO设备可以和CPU并行工作。

挂起和阻塞都是暂时不能获得CPU的服务,但是挂起态是将进程映像调到外存中去,而阻塞态下,进程映像还在内存中。

操作系统具有异步性。

将一次仅允许一个进程使用的资源称为临界资源。访问临界资源的那段代码称为临界区。

进程间的直接制约关系源于它们之间的相互合作。

互斥也称间接制约关系。

有限等待:对请求访问的进程,应保证能在有限时间内进入临界区。 让权等待:当进程不能进入临界区时,应立即释放处理器,防止进程忙等待。

在进入区设置并检查一些标志来标明是否有进程在临界区中,若已有进程在临界区,则在进入区通过循环检查进行等待。

单标志算法设置一个公用整型变量,用于指示被允许进入临界区的进程编号。

双标志先检查算法的问题出在检查和修改操作不能一次进行。

所有的解决方案都无法实现让权等待。

CPU只在发生中断时引起进程切换,因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完。

信号量机制只能被两个标准的原语(P、V操作)访问。

在互斥问题中,P,V 操作要紧夹使用互斥资源的那个行为,中间不能有其他冗余代码。

管程:代表共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序。

每次仅允许一个进程进入管程,从而实现进程互斥。

只有初始化和PV操作才能改变信号量的值。通常,信号量分为互斥量和资源量,互斥量的初值一般为1,表示临界区只允许一个进程进入,从而实现互斥。互斥量的绝对值表示在临界区外等待进入的进程数。资源量的绝对值表示等待的进程数。当信号量 K < 0 时,表示有 |k| 个进程在等待该资源。

进程进入临界区必须满足互斥条件,当进程进入临界区但尚未离开时就被迫进入阻塞是可以的,系统中经常出现这样的情形。在此状态下,只要其它进程在运行过程中不寻求进入该进程的临界区,就应允许其运行,即分配CPU。该进程所锁定的临界区是不允许其它进程访问的,其它进程若要访问,必定会在临界区的“锁”上阻塞,期待该进程下次运行时可以离开并将临界区交给它。

公用队列可供多个进程使用,但一次只可供一个进程使用,试想若多个进程同时使用公共队列,势必会造成队列中的数据混乱而无法使用。

并发进程是异步的。

共享程序段可能同时被多个进程使用,所以必须可重入编码,否则无法实现共享的功能。

管程中的signal操作是针对某个条件变量的,若不存在因该条件而阻塞的进程,则signal不会产生任何影响。信号量机制中的V操作一定会改变信号量的值。

PV操作是一种低级的进程通信原语,不是系统调用。

CPU 在执行指令的过程中,就是在处理内存或者寄存器中的一些数据。那么如何找到和处理这些数据呢,就是基于“地址”。

暂时换出外存等待的进程状态为挂起态。

覆盖是在同一个程序或进程中的。交换是在不同进程(或作业)之间的。

Peterson算法的伪代码


// 进程 P0
void P0()
{
  while(true)
  {
    flag[0] = true;
    turn = 1;
    while(flag[1] && (turn == 1));
    临界区;
    flag[0] = false;
  }
}

// 进程 P1
void P1()
{
  while(true)
  {
    flag[1] = true;
    turn = 0;
    while(flag[0] && (turn = 0));
    临界区;
    flag[1] = false;
  }
}

两个不同的进程,并不共享内存空,其内的变量对应的存储单元也就不相同。

动态分区分配就是增加了内存移动的功能。由于若干次内存分配与回收之后,各个空闲的内存块不连续了。通过“重定位”将已经分配的内存“紧凑”在一块,从而空出一大块空闲的内存。“紧凑”是需要开销的,比如需要重新计算地址。

虽然进程的各个页面是离散存放的,但是页面内部是连续存放的。

如果要访问逻辑地址 A,则

(1)确定逻辑地址A对应的“页号” P

(2)找到P号页面在内存中的起始地址(需要查页表)

(3)确定逻辑地址A的“页内偏移量” W

逻辑地址 A 对应的物理地址 = P 号页面在内存中的起始地址 + 页内偏移量 W

将内存空间分为一个个大小相等的分区(比如每个分区4KB),每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面)。每个叶框有一个编号,即“页框号”,页框号从0开始。

将进程的逻辑地址空间也分为与页框大小相等的一个个部分,每个部分称为一个“页”或“页面”。每个页面也有一个编号,即“页号”,页号也是从0开始。

一个进程对应着一张页表;进程的每一个页面对应着一个页表项;每个页表项由“页号”和“块号”组成;页表记录进程页面和实际存放的内存块之间的映射关系。

虽然进程的各个页面是离散存放的,但是页面内部是连续存放的。

页表长度指的是这个页表总共有几个页表项,即总共有几个页;页表项长度指的是每个页表项占多大的存储空间;页面大小指的是一个页面占多大的存储空间。

页面不是按照逻辑模块划分的,这就很难实现共享。

分页管理的内存空间利用率较高,不会产生外部碎片,只会有少量的页内碎片。分段管理中,如果段长过大,为其分配的连续空间会很不方便。段式管理会产生外部碎片。

段号的位数决定了每个进程最多可以分为几个段;页号的位数决定了每个段最大有多少页;页内偏移量决定了页面的大小、内存块大小是多少。

与进程管理一样,为实现目录管理,操作系统引入了文件控制块的数据结构。

树形目录结构可以很方便地对文件进行分类,层次结构清晰,也能够更有效地进行文件的管理和保护。但是,树形结构不便于实现文件的共享。

共享文件不同于复制文件,在共享文件中,各用户指向的是同一个文件。

读取某个磁盘块时,需要移动磁头。访问的两个磁盘块相隔越远,移动磁头所需实际就越长。因此,连续分配的文件在顺序读/写时的速度最快。

索引分配允许文件离散地分配在各个磁盘中,系统会为每个文件建立一份索引表,索引表记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表–建立逻辑页面到物理页面之间的映射关系)。

在显示链接的链式分配中,文件分配表FAT是一张磁盘对应一张。而索引分配方式中,索引表是一个文件对应一张 😴