Chapter 1 引论

1.1 翻译程序和编译程序

翻译程序（Translator）：把某一种语言（源语言程序）等价转换为另一种语言程序（目标语言程序）的程序。
编译程序（Complier）：如果源语言为高级语言，而目标语言为编译语言或机器语言之类的低级语言，则称这样的翻译程序为编译程序。
解释程序（Interpreter）：将源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序。

采用编译方式在计算机上执行用高级语言编写的程序，需要分阶段进行，一般分为两大阶段：编译阶段和运行阶段。编译阶段首先将源程序通过编译程序编译为机器语言目标程序。运行阶段中将目标程序载入到运行系统中，输入初始数据得到结果。

1.2 编译过程和编译程序的基本结构

1. 词法分析

词法分析的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个个具有独立意义的单词（也称单词符号，简称单词）。
依据原则：构词原则
描述工具：有限自动机

2. 语法分析

语法分析的任务是在词法分析的基础上根据语法规则将单词符号串分解为各类语法单位（如表达式、说明、语句等）并进行语法检查。
依据原则：语法原则
描述工具：上下文无关文法

3. 语义分析和中间代码生成

任务是对各类语法单位按照语言的语义进行初步翻译，分析其含义，并使用另一种语言形式来描述这种语义。
依据原则：语义原则
描述工具：属性文法

4. 代码优化

对前面一个阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码
依据原则：程序的等价变换原则

5. 目标代码生成

将中间代码变换为特定机器上的目标代码，其依赖于硬件系统结构和机器指令的含义。
目标代码三种形式：

• 汇编指令代码：需要汇编
• 绝对指令代码：可以直接运行
• 可重定位指令代码：需要进行链接才能运行

上述5个程序分别称为词法分析程序、语法分析程序、中间代码生成程序、代码优化程序和目标代码生成程序。上述顺序只是逻辑关系，并不代表实际上的时间关系。

错误处理

在编译过程中如果出现错误，程序需要发现源程序中的错误并将有关信息报告给用户。错误包含语法错误和语义错误。

编译前端与后端

编译前端：与源语言有关，如词法分析、语法分析、语义分析与中间代码产生，与机器无关的优化
编译后端：与目标机器有关，与目标机器有关的优化与目标代码产生
带来的好处是：程序逻辑结构清晰，优化更加充分，更有利于移植。

1.3 编译程序的生成方法

生成一个编译程序一般需要考虑以下几个方面：

• 对源语言和目标语言认真分析
• 设计编译算法
• 选择语言编制程序
• 调试编译程序
• 提交相关文档材料

编译语言以汇编语言和机器语言为工具，好处是可以针对具体的机器，充分发挥计算机的系统功能，其生成的程序效率较高；缺点是程序难读、难写、易出错、难维护、生产的效率低下。相反以高级语言编写的程序易读、易理解、生产的效率高

第7章习题详解

1.

Cache是三级存储体系中速度最快（√），容量最大（×，最小）的一类

2.

固定地址映射由程序员或编译器完成地址映射，容易产生地址冲突，运行失败。（√）

3.

存储保护功能是指防止访问越界和防止访问越权。（√）

4.

静态地址映射和动态地址映射计算物理地址时都是用虚拟地址加上基址。（√，计算物理地址的公式：MA=BA+VA）

5.

虚拟内存管理的目标之一是使得大的程序能在较小的内存中运行。（√，使大的程序能够在较小的内存中运行的机制为虚拟存储，即借助辅存扩大逻辑上的内存空间）

6.

采用固定分区的系统在程序装入前，内存已被分区，且每个分区大小都相同（×，每一个分区的大小不一定相同），不再改变。

7.

动态分区容易产生碎片。（√，动态分区容易产生外部碎片）

8.

内存碎片是指内存损坏而导致不能使用的区域。（×，内存碎片是指内存被反复分割之后剩下的一些小的空闲区，它们难以被操作系统利用）

9.

在页式地址映射过程中，快表的作用是尽量减少内存访问次数。（√，快表存放于cache中，访问速度比内存块，将内存的部分内容保存到快表中可以减少内存访问次数，提高系统效率）

10.

缺页中断处理程序的作用就是把相应页面的数据从写入到硬盘中。（×，缺页中断处理程序的作用是将相应页面的数据从辅存写入到内存中）

11.

最佳算法（OPT算法）淘汰以后不再需要或最远的将来才会用到的页面，是实际应用中性能最好的淘汰算法。（×，实际应用中由于无法预测表中哪一页不再需要或在最远的将来才会需要，因此无法应用于实际）

12.

采用内存覆盖技术存储系统，调入一个模块时可以临时将其随意放在一个足够大的覆盖区上。（×，不能将其随意放在一个足够大的覆盖区。覆盖技术的目的是实现小内存运行大程序，基本思路是将程序分为多个模块，需要哪一个模块就将其装入到内存中，不需要则放到辅存中，因此在内存紧张的情况下，可能无法找到一个足够大的覆盖区，所以需要提前设计好如何装入。）

13.

使用内存交换技术可以增加进程并发数。（√，内存交换技术让等待的进程迁出内存，可以增加进程的并发数，实现在小内存运行多个程序的目的）

14.

提高程序的局部性可以有效降低系统的缺页率。（√，提高程序的局部性可以让程序集中地访问邻近几页的内容，可以直接通过cache进行访问，降低系统的缺页率）

15.

段页式系统的地址映射过程既需要段表，也需要页表，而且段表和页表都需要多个。（×，一个进程只需要一个段表，每一个段表需要配备一个页表，因此一个进程一般有多个页表）

16.

控制寄存器CR0的PG位作用是控制实模式和保护模式的选择。（×，PG位是用于控制是否将内存进行分页，在位0的PE位才是实模式和保护模式的选择）

17.

保护模式下，CS，DS存储的是相应段的基址。（×，保护模式中，段寄存器记录的是段描述符的索引，通过该索引找到段描述符，然后通过段描述符中的段基址域找到该段。）

18.

描述符表（Descriptor Table）以8字节为单位存储段的描述符。（√，段描述符一个8字节）

19.

选择子作用是选择描述符表中某个描述符。（√，段选择子是记录段描述符在描述符表中索引的数据结构）

20.

二级页表机制中，页表和页目录大小都是4K。（√）

第4-6章习题详解

1.

A：进程的运行全过程不可重现，正确，进程在运行过程中由于可能需要与其他进程之间进行互动产生影响，无法准确模拟出该进程在执行过程中不断变化的计算机环境。
B：一个程序只能生成一个进程，错误，一个程序可以生成多个进程，且这些进程可能可以同时运行。
C：进程具有异步性，正确。进程的四大特征分别是动态性、并发性、异步性、独立性。
D：多个并发进程共享CPU，正确。一台计算机一个时刻可能会有很多进程同时进行，进程之间需要共享CPU以保证运行。

2.

A：单CPU的系统处于运行态的进程可能有多个，错误，单CPU系统中任何一个时刻只能有一个进程获得CPU资源，因此处于运行态的进程在一个时刻只能有1个，但操作系统可以通过CPU分时让用户误以为有多个进程在同时运行。
B：进程在整个生存期间会根据不同条件转换状态，正确，当进程继续执行需要的条件不满足时，会从运行状态转向阻塞状态，当条件满足时又会转到就绪状态，就绪状态的进程通过获取CPU资源成为运行状态。
C：阻塞态的进程即使给它CPU也无法运行，正确，进程处于阻塞态说明该进程的运行条件不满足，即使有CPU资源也无法运行。
D：处于就绪态的进程都在等待CPU，正确，处于就绪态的进程只需要CPU资源即可运行。

3.

A：PCB是进程存在的标志，正确，一个PCB标识一个进程，不可能存在没有PCB的进程。
B：Linux定义PCB的结构是task_struct，正确，task_struct是Linux系统的进程控制块。
C：进程生存期间PCB中变量的值一直不变，错误，PCB中可能发生改变的变量有且不仅限于：nice值、运行状态、counter值等。
D：创建进程的时候创建PCB数据结构，正确。

4.

A：进程生存期间都受操作系统控制，正确。进程的整个生存过程中所有状态改变等都受到操作系统的调度。
B：进程控制采用原语实现，正确。进程控制是一个不可中断的操作，无论是上锁加信号量还是状态转换都应该使用原语实现。
C：进程被唤醒的条件与进程被阻塞的条件一致，正确。进程因为什么条件不满足被阻塞，就会因为这个条件被满足而被唤醒。
D：进程被撤销时操作系统收回其占用资源，但不释放相应的PCB。错误，进程被撤销时即刻释放PCB，注意Linux中的exit函数并没有立即撤销该进程，而是让该进程变为僵尸状态，等待父进程的wait函数收集信息，因此exit函数执行后wait函数能够获得已经结束进程的退出码与该选项陈述并不冲突。

5.

D：应用程序的初始化，错误，应用程序的初始化过程中应该只有一个线程在工作，不需要多线程。需要多线程的场景有：需要多个功能并发的地方、需要改善窗口交互性的地方、需要改善程序结构的地方、涉及多核CPU应用的地方。

6.

A：临界资源是一个共享变量，正确，临界资源指的是多个进程共享使用的资源，这里的资源对于一个进程而言只能够使用变量进行访问。无论这个变量本身是共享的，还是这个变量对应的资源是共享的，这里统一理解为共享变量。
B：临界区是程序中的某个片段，正确，程序在临界区访问临界资源。
C：临界区中含有对临界资源的存取操作，正确。
D：线程内定义的变量可以是临界资源，错误，临界资源指的是被多个进程竞争访问的具有逻辑排他性的资源，在线程中定义的变量只对本进程可见，而其他进程不可见。

7.

A：临界区不允许两个或多个进程同时进入。正确，注意临界区是用来访问临界资源的，而临界资源是互斥的，因此临界区不能有多个进程同时进入是没有问题的。因此使用信号量控制的代码段严格意义上说不能算是临界区。
B：有限等待原则要求程序员将临界区设置的大一些，错误，应该是小一些，临界区小一些可以让进程处于临界区的时间减少，有利于进程运行。
C：让权等待可以让系统工作效率更高。正确，让权等待实际上是进程主动放弃CPU资源，这样可以让其他进程使用一段时间的CPU资源，实现虚假的多进程同时运行。
D：同一个线程可以设置不同的临界区。正确，同一个线程内设置不同的临界区可以用于处理不同的资源问题。

8.

A：锁机制设置一个标志表示临界区是否可用。正确，通过设置一个布尔类型的标志可以实现一个简易的锁。
B：锁机制只能解决进程互斥的问题。正确，锁机制只能与临界区搭配使用，解决资源互斥的问题。
C：锁机制满足忙则等待和空闲让进的原则。正确，当锁被激活时，满足忙则等待原则，锁空闲时满足空闲让进的原则。
D：锁机制满足有限等待和让权等待的原则。错误，锁机制不满足让权等待的原则，即进程不会主动让操作系统回收它使用资源的权利，只有进程自己解锁退出临界区才能让其他进程进入临界区。

9.

A：P-V操作是比锁机制更灵活的同步机制。正确，P-V操作不仅可以实现锁的功能（初始化时将信号量的值设置为1即可实现锁的功能），还能实现锁不能实现的功能，即控制最多有几个进程访问某个资源。
B：P-V操作可以用于控制进程之间的同步和互斥。正确。
C：P-V操作用来对信号灯和进程进行控制。正确，P-V可以用于控制信号灯，其作用类似于信号灯，如服务区场景，当服务区前面等待的车辆数量大于某个阈值时将信号灯设置为红灯，让车辆进入其他服务区，等待车辆数量较少时设置为绿灯。
D：P操作和V操作都可以使信号量加1。错误，P操作会使信号量-1，而V操作会使信号量+1。

10.

A：P操作可能会阻塞调用进程。正确，P操作的步骤是：信号量-1，如果信号量值小于0则将自身进程加入到信号量进程等待队列，如果大于等于0则继续执行。
B：V操作会把信号量+1。正确，V操作的步骤是：信号量+1，如果信号量值小于等于0则从队列中激活一个进程的运行，如果大于0则继续执行。
C：P操作可以唤醒一个进程。错误，P操作只能阻塞当前进程。
D：P操作和V操作在所有并发进程中成对出现。正确，对于一个信号量，在不同进程的代码中不可能只有P操作或只有V操作。

11.

A：一般在关键操作之前执行V操作。错误，一般在关键操作之后执行V操作释放资源。
B：一般在关键操作之后执行P操作。错误，一般在关键操作之前执行P操作锁定资源。
C：信号量S的定义可以随意定义。错误，信号量S在初始定义时不能定义为一个非正值，且具体值由资源本身决定。
D：信号量S的初值设置不正确可能导致进程并发过程出错。正确，如果将信号量设置为负数，则所有有关进程可能都将阻塞。

12.

A：fork函数具有两个返回值。正确，fork函数在父进程和子进程中具有不同的返回值。
B：wait函数会阻塞进程直到其一个子进程结束未知。正确，wait函数只有在一个子进程结束时才会返回。
C：exit函数可以在进程结束的时候传递参数给父进程。正确，exit函数在进程结束前的一瞬间将参数传递给父进程。
D：sleep函数会唤醒一个进程。错误，sleep函数用于将一个进程阻塞固定时间。

13.

A：资源数量不够不一定产生死锁。正确，死锁发生需要4个条件：互斥条件、不剥夺条件、部分分配条件、环路条件。
B：每个死锁的进程一定在等待某个资源。正确，死锁的进程处于阻塞状态，阻塞状态就是在等待某个资源而阻塞。
C：每个死锁的进程一定持有某个资源。正确，死锁的进程一定持有资源，而参与死锁的进程中至少有两个进程持有资源。注意以下场景：进程1需要资源A，占用资源B，进程2需要资源B，占用资源A，二者死锁，此时进程3需要资源A，也会被阻塞，此时进程3不占有任何资源，但认为其并未参与死锁，可以说进程3因为死锁而被阻塞，但不能说它参与了死锁，因为死锁不是因为进程3引起的。
D：五个哲学家并发就餐的场景一定会发生死锁。错误，只要五个哲学家都不是只拿一根筷子就不会发生死锁。

Chapter 9 文件系统

9.1 文件系统概念

文件是信息存放形式，由若干信息项有序组成。
文件具有唯一文件名。
用户通过读写指针存取文件的信息项。

按照文件用途可以将文件分为系统文件、库文件和用户文件。
按照文件操作权限可以将文件分为只读文件、只写文件、可执行文件、可读可写文件、不保护文件。
按照文件存储时间可以将文件分为永久文件和临时文件。
按照文件性质可以将文件分为普通文件、目录文件和设备文件。

文件系统是管理文件的机构，负责文件的创建、撤销、读写、修改、复制和存取控制等，这方便用户以文件名来存取文件。还负责管理文件存储设备的空间和存取，可以高效利用存储空间和高效存取文件。

9.2 文件逻辑结构与存取方式

• 记录式文件：按照记录读写文件
  • 信息项是记录，一个记录中包含有若干成员。
  • 分为定长记录文件和非定长记录文件。文件头部需要保存记录数量和记录长度等说明信息
  • 记录式文件较浪费存储空间
• 流式文件：按照字节读写文件
  • 信息项是字节。
  • 文件长度就是字节的数量，在现代操作系统中所有文件均为流式文件，由应用程序根据特定的文件格式（协议）去解释和处理文件。

文件存取方式可以采用两种方式：顺序存取和随机存取。

• 顺序存取：从前到后的顺序依次对文件信息项进行读写，直到定位到目标信息位置。
• 随机存取：直接定位到文件目标信息项进行读写，适合流式文件或定长记录文件。

存储介质

• 一盘磁带、一个磁盘组或一张软盘都成为一卷，卷是存储介质的物理单位。
• 块是存储介质上连续信息所构成的一个区域，也叫做物理记录。
  • 块是内存和外存进行信息交换的物理单位，每一次总是交换一块或整数块信息。
  • 块大小要考虑用户使用方式、数据传输效率和存储设备等因素。
• 文件存储结构密切地依赖于存储设备的物理特性，存储设备的特性也决定了文件的存取方法。

顺序存储设备

顺序存储设备严格依赖信息物理位置进行定位和读/写的存储设备，只有在前面的物理块被存取访问过之后，才能存取后续的物理块的内容。如磁带机。按照顺序存取方式访问时速度比较高，而随机方式或按键存取方式效率不高。

优点：存储容量大，稳定可靠，文件卷可拆卸，便于保存和块长变化范围较大等，被广泛用于保存档案文件的存储介质。

随机存储设备

随机存储设备允许文件系统直接存取对应存储介质上的任意物理块。磁盘机是一种典型随机存储设备，存取任何一个物理块所需时间几乎不依赖于此信息的位置。这是一种高速、大容量、旋转型的存储设备，将信息记录在盘片上，每一个盘片都有正反两面，若干张盘片可以组成一个盘组。

驱动机构

• 固定磁头型：磁头不可移动，每一个磁道上设置一个磁头，优点是速度快，但结构复杂，目前使用较少

• 可移动磁头型：每一个盘面有一个读写磁头，所有读写磁头被固定在唯一移动臂，读写磁头按照从上到下的次序从0开始编号，称为磁头号。每一个盘面有很多磁道，从0开始按照由外向里的次序顺序编号称为磁道号，不同盘面上具有相同编号的磁道在一个柱面上，把盘面上的磁道号称为柱面号。所有的磁头都在一个柱面上，每一次只有其中的一个磁头可以进行读写操作。

• 在磁盘初始化时每一个盘面划分为相等数量的扇区，按照磁盘旋转的方向从1开始给各个扇区编号，称为扇区号。

• 每一个扇区各个磁道均可存放相等数量字符，称为块。块是信息读写的最小单位。

• 一个具有正反两个盘面的盘片，有2个磁头。

• 需要确定一个块的位置需要给出3个参数：柱面号、磁头号、扇区号。实际上相当于柱面坐标系中的r、z、θ。

若扇区数量s，磁头数量t，则第i个柱面、第j个磁头、第k个扇区的块号$b=(i\times t+j)\times s+(k-1)$，即索引从小到大依次为：扇区、磁头、柱面。也可以根据块号确定该块在磁盘中的位置。第P块在磁盘上的位置为：柱面号$[P/(s×t)]$，磁头号$[(P\%(s×t))/s]$，扇区号$P\%s+1$。

存储介质的容量逐渐增大，且有些像磁带一样可以随时更换，因此也可以作为保存档案，成为一种高速、大容量、可以拆卸的海量存储器。

9.3 文件的物理结构

文件的物理结构类型有连续文件、串联文件、索引文件3种。

连续文件

文件存放于连续的存储块中。文件目录记录文件长度（块数）和第一个存储块号。
优点：支持顺序存取和随机存取，顺序存取速度快。
缺点：文件不易动态增加，预留空间容易造成浪费，造成外部碎片。

串联文件

串联文件存放于离散存储块中，每一个存储块包含一个链接指针记录下一块的位置。
优点：可以显著消除存储碎片，创建文件时无需知道文件长度，文件动态增加时可以动态分配存储块，支持文件增删改等操作。
缺点：适合顺序访问模式（随机访问效率极低），如果某一个链接指针损坏，文件后面将无法访问。FAT文件系统就是使用这种形式保存文件。

索引文件

文件存放于不连续存储块中，系统建立索引表记录文件逻辑块和存储块的对应关系。索引文件=索引表+数据区。文件目录记录文件名和对应的索引表。

索引表的组织——多级索引。

• 直接索引
• 一级间接索引：文件目录项中有一组表项，其内容登记第一级索引表块的块号
• 二级间接索引

优点：读取索引文件需要索引表，支持顺序存取和随机存取，支持文件动态增长、插入、删除等要求。
缺点：索引表占据额外空间。

其中ext文件系统就采用索引文件方式。

9.4 磁盘空间存储管理

空闲文件目录

将连续空闲区组成的特殊文件称为空闲文件。存储设备上的所有空闲文件就代表了存储设备上的全部空闲空间。
空闲文件目录是为空闲文件建立的目录，记录空闲文件的首个存储块号和存储块数量。

空闲块链

把所有空闲存储块使用链表存储在一起，当申请空闲块时从链表头部取空闲块，回收时将块加载链表尾部。

位示图

内存中划出一块区域，每一位对应存储块使用情况（占用或空闲），空闲时对应位为1，否则为0。
根据磁盘总块数决定位示图中有多少个字。

成组链接法

把空闲块分为若干组，每一组第一个空闲块登记下一组空闲块的块号的空闲块数。在UNIX系统中100个空闲块为1组，余下不足100块的块号和块数登记在一个专用块中。
分配：将专用块读取到存储器，当需要分配空闲块时，直接在内存中找到哪些块是空闲的，每分配一块空闲块数-1。把一组中第一个空闲块分配前将登记在该块中的下一组块号即块数保存到专用块中。当一组空闲块被分配完后把专用块内容读取到内存储器。
回收：归还一块登记后将当前块数+1即可。如果当前组已经满100块将内存中的内容写到归还的那一块，作为新组中的第一块。

9.5 文件目录

文件目录功能：实现“按名存取”：用户向系统提供文件名，就能够找到指定文件

目录文件：文件目录可以看做一个特殊文件。

文件目录项：描述文件的基本信息、使用信息和存取控制信息的数据结构

• 基本信息：文件名、存储位置等
• 使用信息：属性、大小、建立时间、修改时间
• 存取控制信息

目录结构

• 单级目录
  • 最简单的目录结构，这种组织形式下全部文件都登记在同一个目录中。便于简单和实现，但查找速度慢，不允许重名和文件共享。
• 二级目录
  • 第一级称为主目录，第二级目录称为用户目录，即每一个用户有一个子目录，可以解决文件重名的问题，不同用户可以使用相同的名字。
• 多级目录（树形目录）
  • 二级目录结构的扩充，目录结构是倒置的树，根节点为主目录（根目录）

文件全名：从根目录到文件为止整个通路上面所有目录、子目录和文件的名字用"/"顺序连接构成的字符串称为文件全名。路径名分为绝对路径名和相对路径名。

文件属性：指定文件的类型、操作特性和存取保护等信息。一般保存在文件的目录中。

文件操作：创建、写、读、文件定位、删除、截短、属性设置和读取
目录操作：创建、删除

对于文件的访问系统首先需要检查访问权限（文件保护）：读写执行、追加、修改等

9.6 Linux索引文件/inode

索引文件=索引结点inode+若干数据块
索引结点inode：有一个指针指向数据块，指示文件的存储位置

创建文件时需要分配1个索引结点inode和1个数据块，数据块记录文件的内容。如果文件增长太大，则为该文件分配更多的数据块，分配更多的索引表。
创建目录与文件相同，分配1个索引结点inode和1个数据块，如果目录中的文件太多，则为该目录存放更多的数据块。

虚拟文件系统（VFS）：覆盖在逻辑文件系统之上面向操作系统的接口层，对于每一个逻辑文件系统的实现细节进行抽象，使得不同的文件系统在Linux核心以及其他进程看来都相同。

• 索引结点（inode）包含一个文件的所有信息
• 超级块描述物理文件系统的信息，每一个物理文件系统都有自己的超级块，建立文件系统时需要创建该超级块，卸载文件系统删除超级块
• 目录项为文件名与结点的对应位置
• 文件对象表示进程已经打开的文件

Chapter 8 设备管理

8.1 设备管理概念

设备：计算机中除了CPU和内存外其他设备一般统称为外部设备
设备分类：

• 按照交互对象分类：
  • 人机交互设备，如显示设备、键盘、鼠标、打印机
  • 与CPU等交互的设备：磁盘、磁带、传感器、控制器
  • 计算机间的交互设备：网卡、调制解调器
• 按照交互方向分类
  • 输入设备，如键盘、扫描仪
  • 输出设备，如显示设备、打印机
  • 双向设备：输入/输出，如硬盘、软盘、网卡
  • 存储型设备：硬盘、软盘、光盘、U盘
• 按数据传输速率分类：
  • 低速设备：一般速度在1KB/s以下的设备，如键盘
  • 中速设备：1KB/s到1MB/s之间的设备，如打印机
  • 高速设备，超过1MB/s的设备
• 按照信息组织特征分类
  • 字符设备：传输的基本单位是字符，如键盘、串口
  • 块设备：设备存储和传输的基本单位，基本是存储型设备
  • 网络设备：采用socket套接字接口访问，在全局具有唯一的名字，如eth0

设备管理的功能

设备管理的目标：

• 提高设备的利用率
• 提高设备的读写效率
• 提高CPU与设备并行速度
• 为用户提供统一接口
• 实现设备对用户透明

设备管理功能

• 状态跟踪
• 设备分配
• 设备映射
• 设备控制/设备驱动
• 缓冲区管理

设备控制块（DCB）

记录设备的基本属性、状态、操作接口以及进程与设备之间的交互信息等。包含设备名、设备属性、命令转换表（记录设备相关的I/O函数例程地址，不具备相应功能的设备在其例程地址上可以填-1）等。

设备分配

需要按照一定策略安全地分配和管理各种设备。

• 按照相应分配算法把设备分配给请求该设备的进程，并把未分配到设备的进程放入设备等待队列。

设备映射

设备具有一个逻辑名，用户可以为设备起一个友好名便于使用。
在Windows上通过加前缀\.\可访问设备，在Linux上所有设备均处于/dev/文件夹中，通过访问文件的方式访问设备即可。
设备物理名是I/O系统中实际安装的设备，可以为ID或字符串或主/次设备号。设备映射就是逻辑设备到物理设备的转换。用户使用逻辑设备的统一接口去访问设备，而无需考虑物理设备复杂的内部构成。

设备驱动

• 对物理设备进行控制，实现I/O操作
• 将应用服务请求转换为I/O指令
• 向用户提供统一的设备使用接口，将外设作为特别文件处理

设备驱动程序的特点：

• 介于应用程序与设备I/O操作命令之间
• 设备驱动程序与硬件密切相关
• 每一类设备都要配置特定的驱动程序
• 驱动程序一般由设备厂商根据操作系统要求编写

I/O缓冲区管理

设备可以开辟和管理I/O缓冲区，可以提高读写效率。

8.2 缓冲技术

缓冲区的作用：

• 连接不同传输速度的设备。一般情况下CPU的处理速度比设备快很多，在进程空间和设备存储空间之间添加一块内存作为缓冲区将二者进行连接。
• 协调数据记录大小的不一致，如果两个设备或设备与CPU之间记录的大小不一致，则可以通过添加缓冲区暂存避免丢失较大的数据记录。如网络消息的包和帧。
• 正确执行应用程序的语义拷贝。如写入时能够保证写入的数据是调用时刻的数据。如果没有缓冲区，应用程序等待内核写完之后再返回，速度可能比较慢，实时性差。因此加入缓冲区，首先将数据写到缓冲区之后，进程立即返回，不影响进程的执行，之后才由内核将缓冲区写入到磁盘，这能够确保事后拷贝的数据是正确版本。
• 提高CPU和外设之间的并发性。提高并行程度、吞吐量和设备的利用率。

四种缓冲形式

• Cache高速缓冲存储器
• 设备内部缓冲区（外部设备或I/O接口内部的缓冲区）
• 内存缓冲区（内存开辟，应用广泛，使用灵活，可以提前读/延后写）
• 辅存缓冲区（开辟在辅存上）

常用的缓冲技术

• 单缓冲（一个缓冲区，读和写互斥）
• 双缓冲（两个缓冲区）
• 环形缓冲（多个缓冲区，让首尾两个单元在逻辑上相连，有起始指针pStart、输入指针pWrite和输出指针pRead）
• 缓冲池（多个缓冲区，可供多个进程共享，提高缓冲区的利用率减少内存浪费）

提前读和延后写技术

• 该技术针对磁盘类的块设备
• 可以提高进程与设备之间的数据传输效率
• 可以减少访问目标设备次数，提高设备访问的效率

提前读：进程需要从外设读取的数据事先已经被读取到了缓冲区中（需要读取几个字节时将一整块数据全部读取），不需要继续启动外设执行读取操作。

延后写：进程需要向外设写入数据，缓冲区首先将这些数据缓存起来，延迟到特定事件发生或足够时间后再启动外设，完成数据真正写入，即几次写入一次完成。

Linux缓冲机制

• 设置内存高速缓冲区
  • 高速缓冲区被划分为缓冲块。每一个缓冲块与一个磁盘块对应，每一个缓冲块用一个叫缓冲头buffer_head的结构体描述，其中包含数据区指针、块号、设备号等
• 缓冲块中保存最近访问磁盘的数据

8.3 设备分配

设备分配被分为独享设备、共享设备和虚拟设备。

• 独享设备：不可抢占设备，每一次只供一个进程使用，如键盘、打印机等
• 共享设备：可抢占设备，允许多个作业或进行同时使用，如存储设备，随时申请随时可得
• 虚拟设备：借助虚拟技术，在共享设备上模拟独占设备

设备分配方法：

• 独享分配，进程使用设备前首先申请，申请成功后开始使用，直到使用完之后释放。如果设备已经被占用，则进程会被阻塞。
• 共享分配，进程申请使用共享设备时操作系统能够立即分配共享设备的一块空间，不会让进程阻塞。共享分配使得进程使用设备十分简单和高效，随时申请，随时可得。
• 虚拟分配，在一类物理设备上模拟另一类物理设备的技术，通常借助辅存部分区域模拟独占设备，将独占设备转化为共享设备。用来模拟独占设备的辅存区域称为虚拟设备，其中有输入井和输出井模拟输入输出设备的辅存区域。

虚拟分配过程：

• 当进程需要与独占设备交换信息时，采用虚拟技术将与该独占设备所对应的虚拟设备分配给它。首先采用共享分配为进程分配虚拟独占设备，然后将虚拟设备与指定的独占设备关联。
• 进程运行过程中直接与虚拟设备进行交互，传输速度快。

SPOOLing系统（Simultaneous Peripheral Operations Online）

• 是虚拟技术和虚拟分配的实现
• 外部设备同时联机操作
• 假脱机输入/输出

输入井和输出井是磁盘上开辟的两个存储区域。输入缓冲区是内存中开辟的存储区域。输入缓冲区暂存到输入数据，再传送到输入井；输出缓冲区暂存输出数据，以后再传送到输出设备。

软件有：

• 预输入程序，控制信息从独占设备输入到辅存

• 预输入表，从哪一台设备输入，存放在输入井的位置

• 缓输出程序，控制信息从辅存输出到独占设备

• 缓输出表，输出信息在输出井的位置，从哪台设备输出

• 井管理程序，控制用户程序和辅存之间的信息交换

• 预输入进程，模拟脱机输入的卫星机，将用户要求的数据从输入设备通过输入缓冲区传送输入井，当用户进程需要数据时直接从输入井读入所需数据。

• 缓输出进程模拟脱机输出的卫星机，用户进程将输出数据从内存先传送到输出井，当输出设备空闲时将输出井的内容输出到输出设备中。

• 任务执行前，预先将程序和数据输入到输入井中

• 任务运行时，使用数据时从输入井中取出

• 任务运行时，输出数据时将数据写入输出井

• 任务运行完，外设空闲时输出全部数据和信息

SPOOLing优点：

提高了I/O速度，将独占设备改造为了共享设备（实现了虚拟设备功能）

8.4 I/O控制

无条件传送方式

工作过程：

• 进程I/O时无需查询外设状态，直接进行。
• 主要用于外设时钟固定且已知的场合。
• 当程序执行I/O指令时，外设必定已经为传送数据做好了准备。

查询方式

• 在传送数据之前，CPU先对外设状态进行检测，知道外设准备好才开始传输，否则将一直检测等待。
• I/O操作由程序发起并等待完成，每一次读写必须通过CPU。

中断方式

• 外设数据准备好或准备好接收时，产生中断信号
• CPU收到中断信号之后，停止当前工作，处理该中断，完成数据传输
• CPU处理完成后继续原来的工作
• 缺点是降低CPU效率，适合少量数据低速传输

通道方式

• 通道是用来控制外设和内存数据传输的专门部件
• 通道有独立的指令系统，既能够受控于CPU又能独立于CPU
• I/O处理机

DMA（直接内存访问）方式

• Direct Memory Access
• 外设和内存之间直接进行数据交换，不需要CPU干预。
• 只有数据传送开始（初始化）和结束时（反初始化）需要CPU参与，传输过程不需要CPU参与。
• DMA控制器：DMAC，可以代替CPU控制内存和设备之间成块的数据交换，在微机中广泛采用。
• 局限性：不能完全脱离CPU（传送方向、内存地址、数据长度由CPU控制），每一台设备需要一个DMAC（设备较多时不经济）

I/O控制特点

• 在应用层为用户提供I/O接口，对设备的控制和操作则由内核I/O子系统来实施
• 每个通用设备类型都通过一组标准函数（及接口）来访问。具体的差别被I/O子系统中的内核模块（内核驱动程序）所封装，设备驱动程序层的作用是为内核I/O子系统隐藏设备控制器之间的差异，将I/O子系统与硬件分离，简化了操作系统开发人员的任务，也有利于设备的设计和制造。

控制I/O核心模块的方式

• 以设备驱动进程的方式
  • 为每一类设备设置一个设备驱动进程，当有I/O请求到来时该进程被唤醒进行设备驱动工作。当没有I/O请求时该进程睡眠，否则由I/O控制模块的接口程序负责解释用户的I/O系统调用，将其转换为I/O控制模块认识的命令形式后将I/O请求发送给对应的设备驱动进程。
• 将设备与文件一样对待
  • 使用文件系统的系统调用命令进行设备的读写。

8.5 设备驱动程序

8.5.1 Linux模块

LKM：可加载的内核模块，是一种未经连接的可执行代码，可以动态地加载或卸载模块，经过连接可称为内核的一部分。设备驱动可以通过模块的方式添加到内核。

Linux设备的分类：

• 字符设备：
  • 以字节为单位进行I/O操作
  • 字符设备中的缓存是否可有可无
  • 不支持随机访问
  • 如串口设备
• 块设备
  • 存取通过buffer、cache进行
  • 可以进行随机访问
  • 如IDE硬盘设备
  • 支持可安装文件系统
• 网络设备
  • 通过BSD套接口访问（SOCKET）

用户态和内核态

• Linux的两种运行方式：内核态、用户态
• 驱动程序工作在内核态
• 应用程序和驱动程序之间传送数据函数：
  • get_user
  • put_user
  • copy_from_user
  • copy_to_user

主设备号和次设备号

• 主设备号：表示设备种类，表示驱动程序，范围为1-255，支持动态分配主设备号
• 次设备号：标识同一个设备驱动程序的不同硬件设备

Chapter 7 存储管理

7.1 存储管理概述

7.1.1 多级存储体系

理想的存储系统：

• 容量足够大
• 速度足够快
• 信息永久保存
• 廉价

计算机中实际的存储体系往往由高速缓存、主存和辅存3种不同存储设备构成。

• 寄存器位于CPU内部，不同架构的CPU有不同数量的寄存器，寄存器的存取速度最快。
• 内存可以存放程序和数据，容量比寄存器大很多，RAM掉电会丢失数据，ROM可长期保存数据。
• 高速缓存位于CPU与内存之间，速度比内存更快，容量较小，仅复制内存极少量的数据。
• 辅存以硬盘为主，用于长期保存指令和数据，可联机和脱机存放数据，容量较大，还可以为内存提供交换空间。

在三级存储体系中，最上层为高速缓存，虽然价格贵容量小，但速度快；往下是内存，价格和容量适中，但是内容易丢失；最下面是辅存，容量最大价格最便宜但速度最慢。

有关于内存模块换入换出的问题：如果一次换入换出前后内存模块地址不变，那么有利于模块中的程序运行，程序设计简单，但是容易造成地址冲突；如果前后地址可以不一样，那么可以使内存使用更加灵活，缺点是需要进行地址重定位。

7.1.2 存储管理的功能

存储管理系统主要包含地址映射、虚拟存储、内存分配、存储共享和保护这4个部分。

地址映射

内存管理系统需要将虚拟地址转换为内存物理地址，即将程序中的地址（虚拟地址、逻辑地址）转换为真实的内存地址（实地址、物理地址），其方式有固定地址映射、静态地址映射和动态地址映射3种。

虚拟存储

为了解决内存不足的问题，内存管理系统借助辅存在逻辑上扩充内存，使用户觉得内存足够大。将程序代码从内存迁出到辅存中称为迁出，从辅存迁入到内存中称为迁入。

程序局部性原理：包含时间局部性和空间局部性，一段代码在刚刚访问后很有可能被再一次访问，这段代码的邻近空间也很可能在短时间内被访问。因此将程序的一小部分装入内存中通常也可以让其运行一段时间。

实现虚拟存储的前提：

• 适当容量的内存
• 足够大的辅存
• 地址变换机构

内存分配

为每一道程序分配足够的内存空间，同时应该尽量减少无法利用的内存零头或者碎片出现，提高系统内存空间的利用率。

内存分配需要解决：

• 放置策略，即程序应该分配到什么地方
• 调入策略，即如何将要运行的程序调入内存
• 淘汰策略，即迁出哪些代码以腾出内存空间

存储共享与保护

内存中一些用户或系统程序段可以进行不同进程共享，以提高内存的利用率，防止访问越界和越权。

具体的保护方式：

• 设置界址寄存器，规定一个段的上界和下界，程序每一次访问内存均进行检查。
• 基址寄存器和限长寄存器，适用于连续分配的物理内存。
• 存储键保护，适用于不连续分配的内存，也可以用于共享中的权限。

7.2 地址映射

7.2.1 地址映射的概念

程序员写在程序中的地址被称为逻辑地址，产生的前提是内存是理想的存储空间，是该进程独占的。逻辑地址一般使用相对地址计数，参考的起始地址是程序第一条指令或数据。地址映射又称为地址重定位、地址转换，是将程序中的逻辑地址变成真实内存中的物理地址的过程。

7.2.2 地址映射的方法

固定地址映射

在编程或编译时确定虚拟地址和物理地址的映射关系，程序员直接在源代码中指定目标数据的物理地址或指令跳转的目标地址的物理地址。采用固定地址映射编译的可执行程序在运行前必须放在指定的内存区域中。

缺点：程序加载时必须放在指定内存区域，容易导致运行失败，容易产生地址冲突，不能适应多道程序编程环境。

静态地址映射

程序装入内存时由操作系统完成逻辑地址到物理地址的映射，程序装入内存时整体装入，占用一片连续的内存空间。

静态地址映射公式：MA=BA+VA，其中MA为程序在内存中的物理地址，VA为程序的逻辑地址，BA为程序在内存中的装入基址。

• 程序运行前确定全部逻辑地址的映射关系。
• 程序装入后不能再移动，如果必须移动，需要在再次运行之前将其放回原来位置。
• 程序在内存中占用连续的内存空间。

动态地址映射

程序执行过程中将逻辑地址转换为物理地址，当程序运行到一条访问内存的指令时，临时将逻辑地址转化为物理地址。

动态地址映射的计算公式与静态地址映射相同。

动态地址映射需要借助重定位寄存器，其值由进程调度程序根据进程当前实际分配到的主存空间的起始地址决定。切换进程的同时需要切换基址寄存器BAR的值。

动态地址映射的实现思路：程序按照段进行编译，执行时不同的段被分配到不同的地址，虚拟地址的格式应该为段地址+段内偏移，每一段维护一个段寄存器用于段重定位、段式存储管理、段的切换。

特点：

• 程序占用的内存空间可以动态变化
• 程序不要求占用连续的内存空间
• 便于多个进程共享代码

缺点：需要硬件支持（MMU内存管理单元）、设计软件复杂。

7.3 分区存储管理系统

7.3.1 分区存储的概念

分区管理将内存划分为若干大小不等的区域，除了操作系统占用一个区域之外其他分区由多道程序环境下的各个并发进程共享。

7.3.2 单一分区管理

单一分区管理方式将整个内存空间分为用户区和系统区，系统区存放操作系统，用户区不分区，全部归一个用户作业占用。

单一分区管理需要一个栅栏寄存器记录两个区之间的界限，这种管理方式下任何一个时刻主存中只能由一道程序，各个作业的程序只能够按照次序逐一加载进内存运行。

• 单一分区管理仅适用于单用户的情况。
• 单一分区管理系统地址转换多采用静态地址映射
• 单一分区管理系统也可以采用动态地址映射

优点：模式简单，不需要硬件支持，适合于单用户单任务OS
缺点：浪费内存，内存利用率低

7.3.3 固定分区管理

固定分区将用户区划分为若干大小不等的分区，供不同子程序使用。固定分区在系统初始化时就已经被分割完成，一旦初始化完成每一个区域的大小和位置就被固定下来。每一个分区在任何一个时刻只能装入一道程序执行。

支持将多个作业装入内存运行，支持并发运行。系统需要维护一个分区表，记录每一个分区的区号、大小、起始位置、占用标志。

• 在程序装入前，内存已经被分区不再改变
• 每个分区大小不同，适用于不同大小的程序
• 系统需要维护分区表

缺点：浪费内存，大程序可能无法运行（当程序比最大分区大时），作业的内存无法被动态扩充，各个分区的作业需要共享程序和数据很难实现，可以并发运行的程序数量收到分区数量的限制。

在应用时应该尽量让程序大小与数量与分区划分保持一致

示例：IBM OS/360最多有15个分区15个程序

7.3.4 动态内存管理

动态分区管理在程序装入时创建分区，使得分区的大小和程序大小相等。动态分区的大小、位置和数量都是动态的。

动态分区管理有利于减少内存的浪费，有利于多道程序设计，可以实现多个作业对内存的共享，进一步提高的内存的利用率，但容易产生过小的内存碎片无法利用。

7.3.5 内存碎片

内存碎片是指内存被反复分割之后剩下的一些小的空闲区，这些小的空闲区由于太小以至于无法被其他任何程序使用，因此成为内存碎片。过多的内存碎片会减少有效内存空间，降低内存使用率。

内存碎片分为外部碎片和内部碎片。

• 分区内部出现的碎片称为内部碎片。固定分区法容易产生内部碎片。
• 所有分区之外新增的碎片称为外部碎片，一般碎片问题指的是外部碎片问题。

解决碎片问题的方法：

• 内存拼接技术，即移动内存内容，让所有空闲区空间移动到一起，最后合并为一整块。该技术不能应用于使用固定地址映射和静态地址映射的系统中。拼接时需要关闭系统进行离线拼接，会大大降低系统效率。
• 设置分割门槛技术，即设置门限值，当一次分配剩余的大小小于门限值时，不分割该空闲区而是直接全部分配给用户。这种方式容易产生内部碎片。
• 分段装入技术，将程序分为几个部分装入不同的分区，以便充分利用碎片。

7.3.6 分区回收管理

分区回收将已经结束程序的分区进行回收，将其适当处理后放入空闲区表中，以便再一次进行分配。如果没有任何空闲区与该分区相邻，则直接登记后插入到空闲区表中；如果有空闲区与该分区相邻，则首先进行合并后再进行登记。

7.3.7 分区分配与放置策略

分区分配指选择一个合适的空闲区并从中分割出需要的大小分配给程序。选择空闲区一般参考空闲区表，通过遍历空闲区表选择一个大小不低于程序要求的空闲区进行分割。根据空闲区表不同排序规则将放置策略分为首次适应算法、最佳适应算法、最坏适应算法。

首次适应算法

在空闲区表中选择第一个大小不低于程序要求的空闲区，分割出需要的大小给用户。首次适应算法一般优先使用主存低地址区域的空闲区，尽量保留高地址区域的大空闲区。在较大程序运行时可以从高地址区域获得大空闲区。同时该算法会在低地址区域留下很多内存碎片。

该算法中空闲区表的排序顺序是地址大小。

最佳适应算法

最佳适应算法将空闲区的大小进行递增排序，选择第一个大小不低于最低程序要求的空闲区分割出程序要求的大小给用户。剩下的部分留在空闲区表中。该算法能够保证较大程序能找到合适大小的空闲区，但也会留下很多微小的内存碎片。

最坏适应算法

最坏适应算法按照空闲区大小进行递减排序，从排好序的空闲区中选择第一个不小于程序要求的分区，该算法尽量选择最大的空闲区分割给用户，确保被分割之后的空闲区还是很大，该算法可能无法保证大的程序能够分配到合适大小的空闲区。

7.5 页式存储管理系统

通过物理内存进行内存的直接管理有很多缺点：

• 源程序全部使用物理内存运行容易导致内存访问冲突
• 程序必须全部装入内存才能运行，内存小时容易产生冲突
• 程序占用连续的内存地址，容易产生内存碎片
• 多程序同时运行容易产生干扰

因此引入虚拟内存进行内存管理。
虚拟内存是面向用户的存储空间，是线性的存储空间、封闭的存储空间，容量4GB（32位系统），是程序员编程时使用的地址，其与物理地址分离，进程之间的地址不会产生冲突。

7.5.1 页式管理的概念

页式存储管理将程序分拆为多个模块以装入不同的内存区域。页式存储管理将进程空间和内存空间都划分为等大的小片，进程的小片称为页，内存的小片称为页框。页框与页的大小一致，一个进程由多个页构成。内存被划分为多个页框，页框之间没有空隙。

根据程序的局部性原则，进程以页为单位装入内存，进程被装入内存时只需要将进程的部分页面装入内存即可运行，进程在内存中的多个页框不必相邻。需要新的页时按需从硬盘中调入新的页，而将内存中已经存放的且不再需要运行的页面及时删除，以腾出内存空间。因此进程将页装入内存的原则是局部装入，不断更新。

7.5.2 页面调入策略

预调策略

页面在需要前已经被调入内存，进程映像存放于外存之中，当调入其中一页时往往会将后续的连续多页一起调入。

请求调页策略

进程在运行时发现需要访问的页面不在内存时，临时提出调页请求由内核将所需的页面调入内存。

7.5.3 页式虚拟地址

进程空间的页式虚拟地址是一维线性地址，从0开始线性增加，若页式虚拟地址的宽度为m位，页大小为2ⁿ字节，那么虚拟地址的低n位为页内偏移地址，高m-n位为页号。

7.5.4 页面映射表

系统建立页面映射表，记录进程的页和内存的页框之间的对应关系，页表用于记录每一个页面在内存中所占用页框的页框号以及其他使用特性（如信息保护、权限等）。

每一条记录需要描述页号、页框号和其他属性。

操作系统为每一个进程建立一个页表，页表长度和首地址存放在该进程的PCB中，当前运行进程的页表必须驻留在内存，页表长度和首地址由特殊的寄存器记录。

7.5.5 页式地址映射过程

页式地址映射就是将页式虚拟地址转化为物理内存地址的过程。

物理地址MA=页框号P’×页大小+页内偏移地址W

7.5.6 空闲页框管理

7.5.7 快表

页表的实现方式将影响系统的效率，页表可以放在内存中，也可以放在cache中实现。

实践中将页表中最近常用的部分条目（页表的一个子集，一般为16条）复制到快表中，进行地址映射时首先访问快表，如果在快表中找到数据则称为命中。如果没有找到则访问慢表，并将慢表中的结果更新到快表中。页表的更新策略影响页表的命中率。

7.5.8 页面共享

页式存储管理共享内存的思想：将共享代码的页框映射到相关不同进程的页表中，从而实现页面共享。共享页面在内存中只存储一份，可以有效节省内存。

7.5.9 缺页中断

页表的扩充

实际上的页表除了页号和页框号之外还有其他的域：

• 访问位：记录当前页面在一定时间内是否被访问过
• 修改位：记录当前页面在一点时间内是否被修改过（脏位）
• 中断位：记录当前页面是否已经装入内存

缺页中断

当进程需要新的页面，而该页面没有被加载到内存时，就会产生缺页异常。缺页中断指地址映射过程中，当所要访问的目的页不在内存中时系统产生的异常。

缺页中断处理程序在遇到缺页中断时将所缺的页从页表指出的辅存地址调入到内存某个页框中，并更新页表中该页对应的页框号以及修改中断位。

定义缺页率=缺页次数/访问页面总次数，命中率=1-缺页率。

缺页中断和普通中断的异同点：

• 处理过程均为保护现场、中断处理、恢复现场。
• 普通中断在指令执行结束后响应，缺页中断在指令执行过程中发生；一条指令可能造成多次缺页中断。

7.5.10 多级页表

在多个进程并发的时候，多个页表将占据大量的内存，且页表必须连续存放，有时可能难以找到一块足够大的连续内存空间存放页表。因此引出多级页表的设计思路。

二级页表的设计思路是将页表本身划分为若干个页面，每一个页面都是一个小的页表，小的页表可以离散保存在内存中。为了对小页表进行索引和查找，需要另外设置一个称为页目录的表存放每一个小页表所在的页框。页目录又称为外层页表或一级页表，小页表称为内层页表或二级页表。

页目录本身就是一个特殊的页表，不过每一个表项记录的是二级页表的序号与所在页框的关系。

使用二级页表的好处就是不必将所有页表都保存在内存中。

7.5.11 页面淘汰算法

当缺页中断程序将所缺的页从辅存地址调入内存时，如果当前内存恰好没有空闲页框，就需要将内存中已有的页面淘汰一页。

选择淘汰哪一页的算法称为页面淘汰算法。

定义页面抖动为页面频繁在内存和辅存之间交换的现象。页面抖动会导致系统效率降低。好的淘汰策略应该保证较少的抖动和较高的命中率。

最佳淘汰算法（OPT算法）

淘汰以后不再需要的或最远的将来将要需要的页面。采用这种算法可以保证最低的缺页率，但难以判断到底哪一页是最远的将来将会使用的页面，因此只能多用于理论分析。

先进先出淘汰算法（FIFO算法）

该算法淘汰内存中已经停留时间最长的页面。

实现起来比较简单，只需要将各个页面按照装入顺序挂接在FIFO队列的末尾即可（实际上也可以使用每一页添加一个装入时间标志来判断，但是这样的话每一次淘汰都需要遍历所有的页，效率太低）

优点：实现简单，进程按照顺序访问页面地址空间时页面抖动较少，缺页率较低
缺点：对于一些特定的访问序列，分配页框越多，缺页率越高

最久未使用淘汰算法（LRU算法）

淘汰内存中最长时间未被使用的页面。

近似实现算法：利用页表访问位，页被访问时由硬件置1。页表访问位周期性被软件清零，当访问位为1时不可淘汰，访问位为0时表示可以淘汰。

缺点：软件周期性清零的周期难以确定，如果太小则有很多页访问位都为0，如果太大则有很多页访问位都为1，都无法确定到底淘汰哪一页。

最不经常使用淘汰算法（LFU算法）

淘汰当前时间为止访问次数最少的页面。

对每一页设置一个访问计数器，每当页面被访问时，访问计数器+1。发生缺页中断时查找计数器最小的页淘汰并将所有页的计数器清零。

影响缺页次数的因素：

• 页面越小，越容易缺页。
• 分配给进程的页框数量越少，越容易缺页。

因此程序局部性越好越不容易缺页，跳转越多越容易缺页。

页面的常见大小为1KB、2KB、4KB
如果页面过大，则会浪费内存
如果页面过小，则会导致页表长度增加，浪费内存，且换页次数多，影响系统效率

页式存储系统的不足：

• 页面划分没有逻辑含义
• 页面的共享不灵活
• 页内碎片

7.6 段式存储管理系统

7.6.1 段式管理的概念

段式存储管理系统允许程序员将进程按照逻辑意义划分为多个段，每一段有段名，长度不定。一个进程由多个段构成，一般一个进程都有代码段、数据段、堆栈段。

每个段的段内都从0开始编址，并占用一段连续的地址空间。每一个段的长度取决于段自身的内容，所以各个段的大小可以不等。

7.6.2 段式地址和段表

段式存储管理系统中的虚拟地址VA包含段号S和段内偏移地址W两个部分。进程以段为单位装入内存，每一段分配连续的内存，段和段之间不要求相邻。

进程的段在进行地址映射时，必须知道每一段内存中存放的位置，段表用于支持地址映射的数据结构，类似于页式系统的页表。

段表中记录每一段在内存中的映射的位置和相关的存取属性。段表的典型类型包含段号S、基址B、段长L、可读R、可写W、可执行X、访问位、修改位、中断位等属性。

7.6.3 段式地址映射

进程执行一条指令时

• 首先获取指令中的虚拟地址的段号S和段内偏移地址W，
• 其次以段号S为索引，查找段表，找到对应表项中基址字段和段长字段，分别获得该段在内存中的起始地址B和段长L。
• 利用段长L和偏移地址W进行合法性检查：如果W<0或W>L说明访问越界。
• 计算物理地址，物理地址=基址B+段内偏移地址W。

段的共享

• 共享段在内存中只保存一份。
• 共享段被进程映射到自己的内存空间（需要写入该进程的段表）。
• 需要共享的模块都可以设置为单独的段。

段式系统的缺点：段需要连续存储空间，最大尺寸受到内存大小的限制，在辅存中管理可变尺寸的段比较困难。

段式系统和页式系统的异同点：

• 页式系统是一维地址空间，段式系统是二维地址空间（段是一个维度，段内是一个维度）
• 段长可变而一页的大小固定
• 段的划分有意义，而页的划分无意义
• 相对而言段更容易共享
• 段对于用户可见，而页对于用户不可见
• 段偏移存在溢出问题，而页偏移不存在

7.7 段页式存储管理系统

7.7.1 段页式存储的概念

段页式系统的基本原理是段式存储和页式存储的组合，首先将用户程序分为若干个段，每一个段赋予一个段名，然后将每个段分为若干页。

7.7.2 段页式地址和地址映射

段页式存储管理系统中，进程中各个段依然具有二维地址空间：段号和段内偏移。段内偏移被分解为页号和页内偏移地址。因此段页式地址由3部分组成：段号、页号和页内偏移地址。

段页式地址的映射机构：

• 内存按照页进行划分，按照页进行装入
• 同时采用段表和页表进行地址映射
  • 系统为每一个进程创建一个段表，为每一个段创建一个页表
  • 段表给出每一段的长度和起始地址
  • 页表给出每一页对应的页框

7.8 IA-32 CPU内存管理机制

7.8.1 实模式和保护模式

实模式

计算机在加电前的一段短时间内处于实模式。

实模式内存空间为20位，即1MB物理地址空间，分段机制为段地址16位+偏移地址16位，物理地址=段地址左移4位+偏移地址。

保护模式

保护模式下依然为段地址16位+偏移地址16位的形式，但物理地址计算方式不同，书中原话：操作系统会通过一定的方法从这个“段地址”里面辗转多次获得真正的“段地址”，再和偏移地址相加获得物理地址。

保护模式优化的分段管理机制，支持分页管理机制，共可寻址4GB空间。CPU支持多任务，支持特权级机制，可以使用扩展寄存器和一些新增的寄存器。

可以使用的5个控制寄存器：CR0~CR4。

• CR0含有控制CPU操作模式的控制位和表示系统状态的标志位。第0位是PE位用于切换保护模式和实模式，第31位为PG位用于启动分页机制。
• CR1保留未用。
• CR2含有缺页中断的线性地址，又称页故障线性地址寄存器。缺页中断时CPU将引起缺页异常的线性地址保存在CR2中，由缺页中断处理程序对其进行处理。
• CR3含有页目录的物理内存基地址，又称页目录基地址寄存器PDBR，CR3仅有高20位用于标识地址，低12位用于其他用途。
• CR4包含虚拟8086模式扩展位、保护模式虚拟中断位、禁止RDTSC指令位等较为特殊的控制位。

7.8.2 段与段描述符

段是保护模式下一个重要的概念，指一段连续的内存。在保护模式下，对于任何一个内存单元的存取，都会被系统使用这个单元所在段的存取属性对该操作进行检验。

段的属性称为段描述符，共8字节，描述有段的段基址、段限长和段属性（段类型、访问该段需要的最小特权级、是否在内存中等）。

段基地址域

第2、3、4、7字节，指明段在4GB的线性地址空间中所处的位置。其可以是0~4GB范围内任意地址。

段限长域

第0、1字节和第6字节低4位，实际上是由段描述符中两个分离的字段组合成一个20位的值。段限长实际上是最大的段内偏移值，其仅仅是一个数字，长度单位由段属性域中的颗粒度标识域G指定。如果G=0，则该域中数字的单位是字节，此时段长最大为1MB；如果G=1，则数字的单位是页，此时段长最大可以为4GB。

段属性域

描述符特权级别DPL：描述符的特权级，范围从0到3。
描述符类型标志域S：仅1位，描述段的类型是存储段还是非存储段。存储段指的是这个段存放的是可以由程序直接访问的代码或数据，因此存储段含代码段和数据段两种。存储段描述符也分为代码段描述符和数据段描述符两种（堆栈段属于数据段），S=0表示是系统描述符，描述一段特殊的内存。
描述符访问类型标志域TYPE：4位，指定段或者门的类型，段的访问种类以及段的扩展方向。具体含义依赖于描述符类型域S。
段存在标志域P：指出一个段是否在内存中，=1表示在内存中。

7.8.3 描述符表与段选择子

所有段在使用之前都需要建立描述符表，每一个段描述符占用8KB空间，所有的段描述符集中存放于内存某个区域中，一个接着一个构成描述符表。IA-32 CPU中有3种描述符表，只介绍前面两种：全局描述符表GDT和局部描述符表LDT。

全局描述符表

GDT中包含所有进程可以共用的段的描述符。每个CPU只能有1个GDT，其包含的内存段往往是全局性的，是每一个进程都能够访问的段或者用于系统全局管理的段。

GDTR：48位的寄存器，保存GDT的入口，即全局描述符表寄存器。高32位为GDT在内存中的起始地址，低16位在数值上等于GDT的大小-1。

段选择子

GDT中有多个段描述符，如果需要选择其中的一个并通过该段描述符选择对应的段，则需要知道该段描述符在GDT的位置。

段选择子是记录段描述符在描述符表中索引的数据结构，共16位包含3个域。

• 索引域，高13位，记录描述符在描述符表中的索引，索引值从0开始。
• TI域，中间1位，指明所在描述符表是GDT还是LDT。TI=1从LDT中选择，否则从GDT中选择。
• 特权级域，低2位，描述对请求者最低特权级的限制。

保护模式中，段寄存器记录的是段描述符的索引，通过该索引找到段描述符，然后通过段描述符中的段基址域找到该段。

局部描述符表

LDT与特定任务相关，用于容纳仅属于该任务的段描述符。每个进程/任务都有一个LDT，LDT本身也有对应的描述符称为LDT描述符，描述LDT的基地址，LDT描述符是全局性的，存放于GDT中。因此如果需要找到LDT的基地址需要首先从GDT中找到LDT描述符。

CPU中有一个局部描述符表寄存器LDTR，16位，存放LDT描述符对应的段选择子，通过该段选择子可以在GDT中找到LDT描述符，然后找到LDT。

7.9 Linux内存管理

7.9.1 Linux内存管理概述

Linux使用三级页表机制，从最外层到最里层依次是页全局目录PGD、页中间目录PMD和页表PT。

线性地址从高到低被分为PGD索引域（10位）、PMD索引域（在32位系统中为0位，在64位系统中才使用）、PT索引域（10位）和页内偏移域（12位）4个部分。当前进程的PGD基址存放于CR3寄存器中。

例题

本章的例题涉及计算的部分比较多。

1. 分区分配策略问题

某计算机内存大小为1MB，某时刻其内存使用情况如下：
00000H~1EFFFH（124KB）：正在使用
1F000H~1FFFFH（4KB）：空闲
20000H~27FFFH（32KB）：正在使用
28000H~2FFFFH（32KB）：空闲
30000H~32FFFH（12KB）：正在使用
33000H~34FFFH（8KB）：空闲
35000H~37FFFH（12KB）：正在使用
38000H~5FFFFH（160KB）：空闲
60000H~EFFFFH（576KB）：正在使用
F0000H~FFFFFH（64KB）：空闲

画出3种分区分配策略（首次适应、最佳适应、最坏适应）对应于该内存环境的空闲区表，并处理下列内存分配请求：2KB、48KB、128KB、20KB。

解：
首次适应算法按照地址排序——

首次适应算法顺序查找，使用第一个大小大于请求的内存块进行分配。

2KB分配到1F000H~1F7FFH。
48KB分配到38000H~43FFFH。
128KB无法分配。
20KB分配到28000H~2CFFFH。

分配后空闲区表：

最佳适应算法按照空闲块从小到大排序：

2KB分配到1F000H~1F7FFH。
48KB分配到F0000H~FBFFFH。
128KB分配到38000H~57FFFH。
20KB分配到28000H~2CFFFH。

分配后空闲区表：

最坏适应算法按照空闲区从大到小排序：

2KB分配到38000H~387FFH。
48KB分配到38800H~447FFH。
128KB无法分配。
20KB分配到44800H~497FFH。

分配后空闲区表：

2. 页面淘汰算法

某计算机的快表可以保存4页内容，接下来计算机的页访问序列为：1、3、2、5、4、5、3、3、2、1、4、2、3、2，求出4种页面淘汰算法的快表命中率。（一开始快表均为空）

最优淘汰算法：

• 1 3 2 5 4 5 3 3 2 1 4 2 3 2
• × × × × × √ √ √ √ x √ √ √ √
• 1 1 1 1 4 4 4 4 4 4 4 4 4 4
• 0 3 3 3 3 3 3 3 3 3 3 3 3 3
• 0 0 2 2 2 2 2 2 2 2 2 2 2 2
• 0 0 0 5 5 5 5 5 5 1 1 1 1 1

命中率为8/14。

先进先出淘汰算法：

• 1 3 2 5 4 5 3 3 2 1 4 2 3 2
• × × × × × √ √ √ √ x √ √ x x
• 1 1 1 1 4 4 4 4 4 4 4 4 4 4
• 0 3 3 3 3 3 3 3 3 1 1 1 1 1
• 0 0 2 2 2 2 2 2 2 2 2 2 3 3
• 0 0 0 5 5 5 5 5 5 5 5 5 5 2

命中率为6/14。

最久未使用淘汰算法：

• 1 3 2 5 4 5 3 3 2 1 4 2 3 2
• × × × × × √ √ √ √ x x √ √ √
• 1 1 1 1 4 4 4 4 4 1 1 1 1 1
• 0 3 3 3 3 3 3 3 3 3 3 3 3 3
• 0 0 2 2 2 2 2 2 2 2 2 2 2 2
• 0 0 0 5 5 5 5 5 5 5 4 4 4 4

命中率为7/14。

最不经常使用淘汰算法

• 1 3 2 5 4 5 3 3 2 1 4 2 3 2
• × × × × × √ √ √ √ x x x √ √
• 1 1 1 1 4 4 4 4 4 1 1 1 1 1
• 0 3 3 3 3 3 3 3 3 3 3 3 3 3
• 0 0 2 2 2 2 2 2 2 2 4 2 2 2
• 0 0 0 5 5 5 5 5 5 5 5 5 5 5

命中率为6/14。

Chapter 6 进程调度

6.1 调度概念

6.1.1 调度的定义

调度广义上是指在一个队列中，按照某种策略从中选择一个最合适的个体。

6.1.2 调度的分类

按照调度层次和原因可分为长程调度、中程调度、短程调度和I/O调度。

• 长程调度是从多个作业构成的后备作业队列中，根据调度算法选取一个合适的作业调入内存。当一个作业结束退出系统时，需要执行长程调度从磁盘上选择一个后备作业投入执行。
• 中程调度主要是短期调节系统的负荷，对象为进程，将进程在内存和磁盘交换空间之间进行交换。这样做可能因为内存资源紧张需要挂起一些进程，另外是为系统减少并发性而降低系统开销。
• 短程调度即进程调度，决定哪一个进程将被执行、哪些进程将处于就绪状态。即进程在运行、就绪、阻塞这3个状态之间的转换调度由短程调度完成。其目的是让整个队列被调度的延迟最小，优化系统效率。
• I/O调度为当I/O设备可用时调度相应的等待队列中的进程使用该设备。属于设备管理模块的功能，确定一个合适的顺序来执行来自进程的I/O请求。可以改善系统整体性能。

6.2 调度的原则

6.2.1 调度的宏观原则

用户期望的调度原则应该包括：

• 响应速度尽可能快
• 进程处理时间尽可能短
• 系统吞吐量尽可能大
• 资源利用率尽可能高
• 对所有进程公平
• 避免饥饿
• 避免死锁

但上面几条原则本身就存在矛盾，操作系统一般采取折中的方式采纳其中的部分原则。

6.2.2 调度的时间性能测度

周转时间和平均周转时间：周转时间指作业从提交到计算机开始到给出结果花费的时间，包括在后备队列中等待的时间、对应进程在内存就绪队列中等待时间、对应进程在CPU上真正运行的时间、对应进程等待I/O操作完成的阻塞时间等。$t$表示周转时间，则$$t=t_c-t_s$$其中$t_s$表示作业的提交时刻，$t_c$表示作业的完成时刻，也可以计算为$$t=t_w+t_r$$其中$t_w$表示作业等待时间，$t_r$表示作业运行时间。周转时间越短越好。

平均周转时间指一批作业周转时间的平均值。

带权周转时间和平均带权周转时间：考虑作业大小对周转时间的影响，带权周转时间指作业周转时间和执行时间的比值：$$w=\frac{t}{t_r}$$其中$t$为进程周转时间，$t_r$为进程执行时间。

带权周转时间的意义是表明作业在系统中的相对停留时间，消除因为作业大小不同而导致的绝对周转时间缺少比较价值的问题。

平均带权周转时间指一组作业中带权周转时间的平均值。

6.3 进程调度过程

6.3.1 进程调度的功能

• 记录和管理全部进程的工作状态
• 按照调度策略选择合适的进程
• 进行进程上下文切换

6.3.2 进程调度的时机

主要的调度时机有：

• 时钟中断
• I/O中断
• 异常
• 进程结束
• 系统调用
• 主动调度

6.3 进程调度的方式

进程调度的方式可以分为非抢占方式和抢占方式。区别为当有优先级更高的进程到来时，进程调度程序是否会将当前进程立即切出而切入新进程。抢占方式将首先执行高优先级进程，将低优先级进程暂时挂起；非抢占方式将低优先级进程执行完再去执行高优先级进程。

6.4 作业调度算法

6.4.1 先来先服务调度算法

FCFS调度算法容易理解，容易实现，但是效率不高。该算法只考虑了作业的等待时间而没有考虑作业的执行时间，因此算法不利于晚到但是短的作业。

6.4.2 短作业优先调度算法

SJF算法参考运行时间从后备作业中选择运行时间最短的作业优先投入运行。易于实现，但不利于早到却很长的作业。

6.4.3 响应比高者优先调度算法

RRHF算法考虑作业的响应比。响应比=响应时间/运行时间=1+等待时间/运行时间。该调度算法有利于短作业，对于等待时间相同的作业，短作业的响应比高于长作业。该算法有利于等待已久的作业，等待时间越长越容易被调度。

6.5 进程调度算法

6.5.1 优先数高者优先调度算法

HPF调度算法根据进程的优先数将CPU分配给优先数最高的进程。优先数是一个人为定义的参数，包括静态优先数和动态优先数。静态优先数在进程创建时确定，动态优先数在进程运行期间根据环境动态指定。

静态优先数的确定需要考虑以下因素：

• 进程需要资源的多少，一般进程申请的资源越多，优先数越低，但如果涉及的I/O设备与人机交互有关则可以获得较高的优先数以提升用户体验。
• 进程运行时间长短，一般较大的进程运行时间较长，可以分配较低的优先数。
• 进程的类型，偏I/O的进程可以比偏CPU的进程获得更高的优先数，前台进程可以比后台进程获得更高的优先数，普通用户进程可以比核心进程获得更高的优先数等。

动态优先数的确定需要考虑以下因素：

• 当使用CPU超过一定时长时，可以考虑降低其优先数。
• 当进程等待时间超过一定时长时，可以考虑提高其优先数。
• 当进行I/O操作时，可以提高其优先数。

在Linux系统中，普通用户的进程可以将进程数设置为0~19，内核进程可以设置进程数为-20~19。

缺点：当低优先级进程占用高优先级进程资源时反而需要高优先级进程等待低优先级进程完成，这被称为优先级反转。解决方案有：临时设置高优先级、继承高优先级、临时使用中断禁止。

6.5.2 时间片轮转调度算法

时间片轮转调度算法将所有就绪进程排成一个队列，新来进程加到队列末尾，进程以时间片q为单位轮流使用CPU，刚使用完CPU的进程排到队列末尾，队列在逻辑上是环形的。

该算法需要合理选择时间片q的大小，时间片太短则会导致进程切换频繁，增加系统开销，时间片太长则可能会退化为FCFS算法。

6.5.3 多重时间片轮转调度算法

这是对时间片轮转调度算法的一种改进，设置多个就绪队列，每一个队列对应一个优先级，每个就绪队列使用的时间片大小不同，高优先级的时间片短而低优先级的时间片长。通常优先级每提高一级时间片缩短一半。这样可以提高系统吞吐量，缩短平均周转时间。

6.6 Linux进程调度

6.6.1 Linux调度机制

Linux进程调度的基本特点：

• 基于优先级调度，优先级由静态优先级和动态优先级构成
• 支持普通进程和实时进程
• 实时进程优先于普通进程
• 普通进程公平使用CPU时间

Linux进程控制块task_struct中的priority成员指的是进程的静态优先级，counter成员指的是动态优先级，还有一个nice值，可以通过修改nice值修改进程的静态优先级。nice值的设置范围为-20~19。静态优先级表示该进程被允许连续运行的最长时间，实时进程使用静态优先级调度。counter指的是该进程在当前时间片结束后还能够连续运行多少个时间片，其值越大优先级越高。在新一轮调度开始时，counter=priority，时钟中断服务程序执行后其值自减1，当所有进程的counter都减到0时开始新一轮的调度。

rt_priority成员表示实时进程特有的优先级，policy表示进程的调度策略，用于区分实时进程和普通进程，可选SCHED_OTHER、SCHED_FIFO、SCHED_RR三种。

Linux的调度函数为schedule函数，其在可运行队列中选择一个具有最高优先数的进程并将CPU切换给它。

例题

本章的例题大多与计算有关，即计算调度时间。

例-1：下面是各个任务的到达时间和任务长度，试写出3种作业调度算法下这些任务的开始时间，以及各自的周转时间、平均周转时间、带权周转时间和平均带权周转时间。

对于FCFS算法：

该算法的平均周转时间为50，平均带权周转时间为2.21。

对于SJF算法：

该算法的平均周转时间为47.5，平均带权周转时间为2.15。

对于RRHF算法：

该算法的平均周转时间为47.5，平均带权周转时间为2.15。

Chapter 5 死锁

5.1 进程饥饿

系统不能保证进程的等待时间上限，从而使该进程长时间等待，当等待时间给进程推进和响应带来明显不利影响时，称发生了进程饥饿。

5.2 死锁的概念

死锁是指两个或多个进程已经陷入阻塞，都在无限期地等待永远不会发生的条件的一种系统状态。进程进入死锁之后，永远都被阻塞而无法运行。

死锁的另一种定义是在两个或多个进程中，每一个进程都已经持有某一些资源，而在申请其他进程持有的资源。每一个进程都拥有部分资源，但又不足以运行，导致每一个进程都不能向前推进。

5.3 死锁的起因

5.3.1 资源的分类

将系统中的资源分为两类：可抢占资源和不可抢占资源。

可抢占资源指的是该类资源可以被多个进程同时访问，即被一个进程占用使用完之前可以被其他进程抢占，但不影响进程运行结果。如CPU和内存。
不可抢占资源指的是该资源被一个进程占用之后除非该进程已经使用完毕，否则其他进程不能强行抢占该资源，否则进程运行可能会出错。如大多数硬件和软件资源。

5.3.2 死锁的起因

引起系统死锁的原因：

• 系统资源不足，这是引起死锁的根本原因。
• 进程并发推进顺序不当。

关于死锁的一些结论：

• 陷入死锁的进程至少有2个。
• 参与死锁的进程至少有2个已经占有资源。
• 参与死锁的所有进程都在等待资源。
• 参与死锁的进程是当前所有进程的子集。
• 死锁会浪费大量系统资源，甚至导致系统崩溃。

5.3.3 死锁的必要条件

死锁的必要条件：

• 互斥条件，即进程竞争的资源均为不可抢占资源，进程需要互斥地使用这些资源。
• 不剥夺条件，进程释放资源之前不能被其他任何进程剥夺。
• 部分分配条件，进程运行全过程的所需的资源逐步分配，每一个资源在访问之前临时申请。
• 环路条件，多个进程因为资源的申请和占用的关系构成一个逻辑环路，如进程A占用进程B需要的资源，进程B占用进程C需要的资源，进程C占用进程A需要的资源。

5.4 死锁的解决

5.4.1 解决死锁的4种方法

• 预防：通过设置多个限制条件，使得死锁发生的必要条件中有几条不成立。其中破坏互斥条件几乎不可能，破坏不剥夺条件花销较大，破坏部分分配条件需要将资源进行预先静态分配，破坏环路条件需要资源的有序分配。但由于限制过于严格，导致资源利用率和吞吐量降低。
• 避免：用某种方法分析某种分配方式是否会造成死锁，可能导致算法过于复杂而不实用。
• 检测：检测当前系统中是否有发生死锁，难度和复杂程度较大。
• 恢复：撤销或者挂起一些进程以回收一些资源，实现难度大。

5.4.2 预先静态分配法

预先静态分配法破坏了部分分配条件，保证死锁不会发生。其采用全部分配法的策略，在进程运行之前就将其所需的资源一次性全部分配给它。如果资源不够则该进程无法运行。

缺点：浪费资源且资源利用率低，需要资源多的进程可能会被推迟，适应性有局限（某些进程需要如信号量这样的同步信号资源无法提前准备），应用程序设计开销较大。

5.4.3 有序资源分配法

有序资源分配法破坏环路条件，使得环路无法构成。采用的策略是给系统中的每一个资源分配一个序号，且进程每一次申请资源时只能申请比上次申请的资源的序号更大的资源。由于每一个进程只能按照资源序号递增顺序申请资源，因此系统对资源编号时可以按照从小到大的顺序编号，一般是输入设备较小，输出设备较大。

缺点：资源浪费，资源编号不易合理化（难以保证资源使用顺序满足每一个进程的资源使用顺序）

5.4.4 鸵鸟算法

一句话，不管，如果真的发生了死锁，可以由用户手动去清除。

Chapter 4 进程管理

4.1 进程的概念

定义：程序在并发环境下在一个数据集下的一次运行过程。

特征：

• 动态性：是程序的一次执行过程，其动态产生和消亡。
• 并发性：进程可以同其他进程一起向前推进。
• 异步性：进程按照各自速度向前推进。
• 独立性：进程是系统分配资源和调度CPU的单位。

一个程序可能有多个进程对应。

• 进程是动态的，程序是静态的
• 进程是暂存的，程序是长久的

4.2 进程的状态和转换

进程的3个基本运行状态：

• 运行状态：进程占用CPU正在CPU上运行的状态。
• 就绪状态：进程已经可以运行但是还没有获得CPU，暂时还无法运行的状态。
• 阻塞状态：进程因为缺少某个运行所需的必要条件（资源或信号）而进入等待的状态，如IO操作等。

进程状态的改变：

• 运行→阻塞：需要等待信号、服务结束或某个资源时
• 阻塞→就绪：信号到来、服务结束或所需资源有空闲
• 就绪→运行：通过进程调度使得该进程获得了CPU
• 运行→就绪：CPU被抢占

扩展进程状态：

• 新建状态：操作系统创建进程的过程，创建完毕后进入就绪状态。
• 终止状态：进程退出后的状态，虽不能运行但仍保留一些信息。只能由运行状态转换而来。

具有挂起和解挂操作的进程状态：

• 将就绪状态拆分为静止就绪和活跃就绪状态，将阻塞状态拆分为静止阻塞状态和活跃阻塞状态。处于静止状态时表示挂起状态，便于操作系统进行资源调度。
• 运行→静止就绪，活动就绪→静止就绪，活动阻塞→静止阻塞：进程挂起
• 静止就绪→活跃就绪，静止阻塞→活跃阻塞：解挂
• 静止阻塞→静止就绪：期待活动完成

4.3 进程控制块——PCB

进程控制块至少应该包含以下信息：

• 进程ID（PID）：标识进程的编号
• 进程起始地址：进程的可执行映像在内存（物理内存）中的起始地址
• 进程状态：当前状态
• 优先级：进程优先级别，用于进程调度
• CPU现场保护区：发生中断时对CPU状态的拷贝区，便于下一次将进程加载进CPU继续执行
• 进程间通信区：记录进程之间通信的控制信息、信号和信息缓冲区
• 资源列表：进程拥有的资源清单，主要为外设的占用信息
• 文件列表：进程打开的文件列表
• 内存列表：进程占用的内存空间（虚拟空间和物理空间）

创建进程时创建PCB，进程撤销时PCB应该同时撤销。

4.4 Linux进程控制块——task_struct

进程状态：

• TASK_RUNNING：运行态和就绪态。
• TASK_UNINTERRUPTIBLE：不可中断，不可被其他进程通过信号和时钟中断唤醒，只有资源得到满足才会进入就绪状态，一般非常短暂。
• TASK_INTERRUPTIBLE：可以被其他进程通过信号和时钟中断唤醒。
• TASK_ZOMBIE：进程终止执行，释放大部分资源。
• TASK_STOPPED：进程被挂起。

ps命令：可查看当前进程状态
ps aux，输出有多行。其中STAT行表示进程状态，字段含义：

• R：TASK_RUNNING
• S：TASK_INTERRUPTIBLE
• I：空闲
• Z：TASK_ZOMBIE
• D：TASK_UNINTERRUPTIBLE
• T：TASK_STOPPED/TASK_TRACED，停止或被调试

task_struct中的重要字段：

• 进程状态
• 进程调度信息
• 标识符：包含自身的ID（getpid()获取）、父进程ID（getppid()获取）、进程组ID
• 进程通信信息
• 链接信息
• 时间和计时器
• 文件系统
• 虚拟内存信息
• 处理器信息/现场保留区
• 进程链表：struct *next_task, prev_task，所有进程在一个双向链表之中。

4.5 进程基本控制

4.5.1 进程创建

参数：进程标识、优先级、进程起始地址、CPU初始状态、资源清单等
步骤：

• 分配PCB
• 分配并赋值PID
• 分配内存空间
• 初始化PCB（CPU状态、内存、优先级、进程状态、链表队列）
• 插入相应的进程队列
• 调度程序

4.5.2 进程阻塞

当需要等待外设IO操作、等待系统服务完成、等待请求资源、等待其他进程的约束、服务进程没有新任务可做时进行阻塞。
步骤：

• 进程停止运行（需要保存现场等）
• 修改PCB状态
• 插入相应阻塞队列
• 调度程序

4.5.3 进程唤醒

时机与进程阻塞相反。
步骤：

• 修改PCB状态
• 插入相应就绪队列
• 调度程序

4.5.4 进程撤销

终止此进程的运行。
步骤：

• 在队列中查找该进程
• 获取进程状态
• 如果该进程正在运行则立即终止
• 释放进程资源
• 将进程从队列中移除

4.5.5 原语

进程控制涉及底层的操作，为提高系统的稳定性和效率，进程操作由操作系统内核完成，且加以特殊保护。

原语是由若干条指令组成的一段小程序，用于实现某个特定操作，原语具有不可分割性，要么全部运行成功，要么彻底失败，执行过程不可中断。一个操作如果为原语则称该操作具有原子性，称该操作为原子操作。

主要的控制原语除了上述的创建原语、撤销原语、阻塞原语、唤醒原语外还包括挂起原语、激活原语等。

4.6 Windows进程控制

windows创建进程可以使用多个API实现：

• system
• WinExec
• ShellExecute
• CreateProcess，前面3个最终都需要调用CreateProcess

CreateProcess有很多参数，其中包含可执行程序名、程序参数、执行选项等。其执行步骤：

• 创建进程内核对象，创建虚拟地址空间
• 装载exe文件和dll文件到虚拟内存中
• 创建主线程和线程内核对象
• 启动主线程，进入主函数

结束进程：

• ExitProcess
• TerminateProcess

4.7 Linux进程控制

4.7.1 Linux进程分类

用户在Linux中执行一条命令就是创建了一个新的进程。

Linux进程可分为交互式进程、批处理进程、实时进程、守护进程等。

4.7.2 Linux进程创建

Linux中可以使用fork函数创建一个进程。创建出来的进程是一个子进程，创建进程的进程即为父进程。这里的子进程是父进程的复制，父进程和子进程并发运行。

fork函数的返回值是一个整数，表示进程号。在子进程中，该函数返回的值为0，父进程中返回一个大于0的值，如果创建进程错误则返回-1。在fork函数之后可以通过判断fork函数返回值的方法实现父进程和子进程分别执行不同的代码，让二者执行的分支不同。

4.7.3 fork函数实现过程

fork函数的执行流程：

• 分配task_struct结构体
• 拷贝父进程，复制正文段、数据段以及系统数据段（复制父进程task_struct的大部分内容，而修改小部分内容）
• 将新进程的task_struct保存到队列中
• 新进程置于就绪状态

fork函数的特殊机制：写时复制（COW），即父进程的资源被设置为只读，当父进程或子进程试图修改某些内容时，内核才在修改前对部分内容进行拷贝。

fork函数的实际开销主要就在于复制父进程页表以及给子进程创建PCB。

Linux启动的第一个进程是init进程（进程号为1），其余进程均为init的子孙进程。

4.7.5 execve函数创建进程

exec族函数可用于在子进程空间指定要执行的可执行程序。

首先根据文件名找到可执行程序，然后将可执行程序的内容填充入子进程的地址空间中。若exec调用成功则进入新的进程不再返回，若调用失败则继续从调用点向下进行。

除了execve外，还有execl、execlp、execle、execv、execvp等。

4.7.6 Linux进程撤销

exit函数用于终结此进程，终结进程后需要释放资源并向父进程报告。终结该进程后，该进程变成僵尸状态，保留部分PCB信息供wait函数进行收集。

进程结束时可调用schedule函数选择新进程运行。

4.7.7 Linux的wait()函数

wait函数用于进行进程的阻塞，通过wait函数可以阻塞自身，其会监测是否有子进程结束，如果没有则一直阻塞，如果有则停止阻塞，收集该结束的子进程信息并将其彻底终止，返回。wait函数有一个整型参数int& status接收子进程退出时的退出代码。若忽略子进程退出信息则参数填NULL。

sleep函数也可以用于进程阻塞，阻塞当前进程暂停执行多少秒，系统暂停调度该进程。

4.8 线程

4.8.1 线程概念

线程是进程内部的一个相对独立的运行路径，一个进程可以有多个线程。线程是进程内创建的可运行模块，能够执行指定的任务。线程和线程之间可以并发进行。

在具有线程概念的操作系统中，线程是操作系统进行调度的最小单位，如windows系统。

• 线程能够提高系统的并发性能，其并发粒度比进程更细，能够充分发挥CPU的性能。
• 线程的应用成本更低，更灵活。进程为线程提供地址空间和资源，线程与线程之间的通信比进程之间更加灵活。
• 大多数操作系统都采用了线程技术。

下面场景适用多线程：

• 多个功能需要并发
• 需要改善窗口交互性
• 需要改善程序结构
• 多核CPU之间的应用

现代操作系统中，进程=资源集+线程组。

线程的缺点：难以调试，容易造成线程安全问题，并发过程难以控制。

4.8.2 Windows线程

windows中可以通过CreateThread函数创建线程，并为其指定一个任务。

4.9 进程相互制约关系

4.9.1 互斥关系

在进程运行过程中互相排斥地访问一个具有独占性的公共资源，必须协调各个进程对资源的存取顺序，确保没有任何两个或两个以上的进程同时进行资源存取。

将一次只允许一个进程独占访问的资源称为临界资源，访问临界资源的代码段称为临界区。

4.9.2 同步关系

合作进程中某些操作之间需要满足某种先后关系或某个操作能否进行取决于某个前提条件是否满足，否则只能等待。互斥关系是特殊的同步关系。

4.9.3 同步机制

有效的同步机制满足：

• 当进程即将要执行的某个操作的运行条件不满足时，能够让该进程立即暂停执行该操作。
• 当被暂停的操作的运行条件满足时，相应进程能够被尽快唤醒以便继续运行。
• 同步机制在实现上也属于原子操作。

有关于多个进程不能同时访问临界区的问题，在硬件上可以通过中断屏蔽来完成，进入临界区时关中断，离开临界区时开中断。在软件上可以通过锁和信号量来解决。

4.10 锁

4.10.1 临界资源和临界区

4.10.2 锁的概念

锁机制通过设置标志来标识临界区是否可以进入或临界资源是否可用。如果为不可用状态，则程序在临界区之外进行等待，若为可用状态，则进入临界区并将临界资源设置为不可用状态。

上锁操作：检测锁S的状态，如果S=0则返回继续检测，如果S=1则设置S=0
开锁操作：将S设置为1
上锁和开锁都应该是原语。

锁可以保证临界区中最多只能有1个进程能够进入其中，在进入临界区之前执行上锁操作，在退出临界区时执行开锁操作。

设置临界区访问机制的4个原则：

• 忙则等待：临界区忙时其他的进程应该在外面等待
• 空闲让进：没有进程位于临界区时允许其他进程抢占临界区
• 有限等待：进程进入临界区的请求应该在有限时间内得到满足
• 让权等待：等待进程放弃CPU，以让其他进程有机会得到CPU

锁机制满足上面4个原则中的前三个。

4.11 信号量与P-V操作

4.11.1 信号量概念

信号量的核心数据结构是一个二元组（S,Q），其中S是一个初值非负的整型变量，Q是初始为空的队列。S可以表示某一类资源的可用数量，可以指某些条件等。当由于信号量的变化而导致某一个合作进程被阻塞，它将被挂接在队列Q中，而当信号量的变化导致满足了进程的运行条件时该进程将被唤醒，并离开队列Q。

4.11.2 P-V操作的定义

P操作指通过：

• S自减1
• 如果S大于或等于0，则函数返回，且调用者进程继续执行
• 如果S小于0，则函数返回，且调用者进程阻塞并插入到等待队列Q中，并由调度程序调度其他进程执行

S操作指释放：

• S自增1
• 若S大于0，则函数返回，且调用者进程继续执行
• 若S小于或等于0，则函数返回，调用者进程继续执行，并同时从等待队列Q中唤醒某一个等待进程

这两个操作在内核中均使用原语控制。

总结而言，P操作可能会阻塞某一个进程，V操作可能会唤醒某一个进程。对于S的初始值设置要合理。信号量实际上就是可以控制多个进程中最多可以有几个进程同时在临界区中运行。

在关键操作之前执行P操作，在关键操作之后执行V操作。

例题

1. 进程之间的互斥模型

进程之间的互斥模型几乎是必考的题型，需要理解锁与信号量控制进程之间互斥的原理。

技巧：

• 对于那些总量有限制的资源，需要定义两个信号量，一个信号量表示当前该资源剩余量，另一个信号量表示当前该资源最多还能够产生几个。
• 对于那些临界资源，临界区可能修改临界资源的值，需要加锁处理，或者使用一个初值为1的信号量代替锁。

例-1：生产者-消费者模型，一共有10个生产者生产5种资源，一个资源由2个生产者负责。另外有2个消费者，第1个消费者需要资源1、2、3循环进行操作A，第2个消费者需要资源3、4、5循环进行操作B。写出代码，实现10个生产者与2个消费者之间的进程互斥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

semaphore res1 = 0, res2 = 0, res3 = 0, res4 = 0, res5 = 0;
void producer_12(){V(res1);}
void producer_34(){V(res2);}
void producer_56(){V(res3);}
void producer_78(){V(res4);}
void producer_90(){V(res5);}
void consumer_1(){
	P(res1);
	P(res2);
	P(res3);
	A();
	
}
void consumer_2(){
	P(res3);
	P(res4);
	P(res5);
	B();
}
int main(){
	corun{
		producer_12
		producer_12
		producer_34
		producer_34
		producer_56
		producer_56
		producer_78
		producer_78
		producer_90
		producer_90
		consumer_1
		consumer_2
	}
}

例-2 某高速出口设有若干人工服务区和ETC服务区，不断有汽车从高速到达出口，其中货车只能选择人工通道，轿车可以选择人工通道也可以选择ETC通道，一辆轿车到达时优先选择ETC通道，如果ETC通道均在排队则选择人工通道。现设人工通道有1个，ETC通道有1个，要求写出代码，能够实时统计每一个通道前排队的车辆数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int queuep = 0, queueetc = 0;
semaphore p = 1, etc = 1, mutex_p = 1, mutex_etc = 1;
void car(){
	while(true){
		if(queueetc){
			P(etc);
			P(mutex_etc);
			queueetc++;
			V(mutex_etc);
		}else{
			P(p);
			P(mutex_p);
			queuep++;
			V(mutex_p);
		}
	}
}
void person(){
	while(true){
		if(queuep > 0){
			V(p);
			P(mutex_p);
			queuep--;
			V(mutex_p);
		}
	}
}
void etc(){
	while(true){
		if(queueetc > 0){
			V(etc);
			P(mutex_etc);
			queueetc--;
			V(mutex_etc);
		}
	}
}

Chapter 3 用户界面

3.1 用户环境

用户环境指的是计算机用户工作的软件环境，包括命令行环境、桌面环境、相关的用户使用手册。

用户环境的构造指的是按照用户的要求和硬件特性，安装和配置好操作系统，为用户提供必要的操作命令或图形界面，并使其工作方式和交互方式合理高效，方便用户使用计算机完成相应的工作。

3.2 用户界面概念

用户界面（UI）是用户与操作系统内核进行交互和信息交换的媒介，其目的是让用户能够更加方便、高效、安全、可靠地操作计算机的软件和硬件，并完成预期的工作。用户界面通常分为操作界面和系统调用。

3.3 操作命令

操作界面：用户可以通过操作界面直接或间接地控制自己的作业或获得操作系统提供的服务。操作界面包括操作命令、批处理命令和图形用户界面三种典型形式。

• 图形用户界面，GUI，包含窗口、图标、按钮等元素。
• 操作命令，一般通过命令行完成，用户在控制台输入命令与操作系统交互。
• 批处理与脚本程序，在控制台环境下自动处理一批命令，如执行windows批处理程序或linux shell脚本程序。

shell是操作系统与用户交互的页面，其本身不执行命令，而仅仅是组织和管理命令，shell脚本是Shell上可执行命令序列的集合。

Linux Bash有代码的自动补全功能（Tab键），Bash不区分变量类型，其中所有变量均为字符串，只有当变量中全为数字时其才为一个整数变量。

重定向与管道：在Linux中，标准输入输出以文件形式存在，分别为0（标准输入）、1（标准输出）、2（标准错误）。命令的输入缺省来自于键盘（文件0），输出缺省到达控制台命令行（文件1、2）。通过重定向可以将输入输出定向到其他地方如文件中。

• < 为输入重定向符号，将命令输入由键盘改为由其他文件等，相当于将文件中的内容输入到了控制台。
• > 为输出重定向符号
• >> 符号也是输出重定向，与>不同的是一个符号重定向到文件时会首先清空文件，而两个符号会在后面追加。
• 2>和2>>均为错误重定向，将命令的错误重定向到某个文件中。
• &>为输出与错误组合重定向，即将原来输出到文件1和2的内容均重定向到别的位置。

管道：将一个程序的输出作为另一个程序的输入。管道操作符"|"。

脚本（Script）通过类似程序的方式执行具有一定逻辑顺序的命令序列完成较复杂的功能和人机交互。脚本程序保存在文本文件中，是Shell命令语句的集合。脚本文件中所有命令按照顺序执行，凡是能够在shell中直接执行的命令，都可以写在脚本中，脚本中还可以使用一些shell中不能使用的命令。执行shell脚本需要可执行权限：chmod +x。
运行脚本程序的方法：

• 直接运行（缺省版本的shell）
• 使用某一个特定版本的shell运行脚本
• 在脚本文件首行指定文件shell（#!/bin/bash）

脚本文件中支持变量定义、流程控制、函数、调试方法。

3.4 系统调用

系统调用是操作系统内核为应用程序提供的服务，是应用程序与操作系统之间的接口。

系统调用一般涉及核心资源或硬件的操作，运行于核态，在调用时产生中断，这种中断是自愿中断、软件中断、内部中断。

系统调用的形式：通过访管指令SVC N，N即为系统调用编号，调用过程发生中断。执行该指令后CPU首先保护现场，然后由中断服务程序查找N号系统调用的入口地址，接着去执行这个系统调用，执行完之后恢复现场。在DOS系统中使用INT 21H进行系统调用（AH寄存器存放系统调用号，这里的INT指令就相当于SVC指令），Linux中为INT 80H（EAX存放系统调用号）。

Linux系统调用的工作原理：

• 应用程序使用隐式方式调用系统调用，这个系统调用将被编译器编译为含有INT 80H的代码。
• 在内核system_call函数部分查找系统调用的入口地址。
• 具体实现系统调用。

系统调用处理函数指针表sys_call_table[]。