本篇文章已整理至我的 VuePress 文档站，后续更新将于文档进行。

第一章 操作系统引论

单道批处理

多道批处理

多道批处理系统宏观上并行微观上串行的含义

并发与并行的区别

一个宏观的时间段内，单 CPU 核心处理多个进程任务，称为并发；多 CPU 核心在同一时间处理多个进程任务，称为并行。

分时操作系统

实时操作系统

操作系统的四个基础特性

并发性，共享性，虚拟性，异步性

异步性是指进程以不可预知的速度向前推进。内存中的每个进程何时执行，何时暂停，以怎样的速度向前推进，每道程序总共需要多少时间才能完成等，都是不可预知的。

现代 OS 的基本单位

内核、进程、线程、类程、管程

作业 1

Focus on FE learning 操作系统学习笔记 - 2：体系结构设计和运行机制

《王道考研 操作系统》学习笔记汇总

内核

微内核中，应用程序与 OS 内核的通信：系统调用；非内核功能（用户空间的 OS）和 OS 内核的通信：消息传递；非内核功能之间的通信：直接调用。

用户态切换到内核态的 3 种方式：系统调用、异常、外围设备的中断

内核态切换到用户态的方式：特权指令，设置程序状态字为 PSW

中断和异常

中断的类型：内中断（也称为 “异常”、例外）；外中断（也称为 “中断”）

内中断的案例：非法指令；应用程序请求操作系统时发出 “陷入指令”，该指令会引发一个内部中断指令，意味着应用程序主动将 CPU 控制权还给 OS。“系统调用” 就是通过陷入指令完成。

中断处理程序一定是内核程序，需要运行在 “内核态”。

系统调用

系统调用是应用程序获得 OS 服务的唯一途径。内核的主体是系统调用的集合，内核可以看成是特殊的公共子程序。

系统调用的方式

用户 -> 应用程序 -> 系统调用（系统调用组成了程序接口 API，每一个系统调用都是一个完成特定功能的子程序）->OS 内核（裸机）

用户 -> 图形窗口 ->OS 内核（裸机）

用户 -> 操作命令 -> 系统程序（操作接口由一组控制命令和作业控制语句组成）->OS 内核（裸机）

系统调用与库函数的区别

应用程序不可以直接调用系统调用，是通过库函数调用系统调用的。

冷启动和热启动

冷启动

（1）开机执行 BIOS 引导程序，标识和配置所有的即插即用设备，并配置 DMA 通道

（2）完成加电自检，测试内存，端口，键盘，视频适配器，磁盘驱动器等基本设备，及 CD-ROM 驱动器。

（3）对引导驱动器引导分区定位：在 CMOS 中，可以自行设置引导顺序，一般顺序是软盘，磁盘，光驱；

（4）加载主引导记录以及引导驱动器的分区表，执行主引导记录 MBR。

（5）装入操作系统

热启动

（1）BOOT 被自动执行，指引 CPU 把操作系统从大容量存储器中传送到主存储器的易失区；

（2）BOOT 要求 CPU 执行一条转移指令，转到这个存储区域；此时，操作系统接管并且开始控制整个机器的活动。

补充资料

为什么说直到出现中断和通道技术后，多道程序概念才变为有用的？

采用多道程序设计减少了 CPU 时间的浪费，增加了系统吞吐量，提高了系统的效率。. 多道程序并发执行是指有的程序正在 CPU 上执行，而另一些程序正在 I/O 设备上进行传输，即通过 CPU 操作与外设传输在时间上的重叠减少 CPU 时间的浪费，并提高了系统的效率。实现 CPU 操作与外设传输在时间上的重叠必须有中断和通道技术支持，其原因如下：

（1）通道是一种控制一台或多台外部设备的硬件机构，它一旦被启动就独立与 CPU 运行，因而做到了输入输出操作与 CPU 并行工作。但早期 CPU 与通道的联络方法是由 CPU 向通道发出询问指令来了解通道工作是否完成。若未完成，则主机就循环询问直到通道工作结束为止。因此，这种询问方式是无法真正做到 CPU 与 I/O 设备并行工作的。

（2）在硬件上引入了中断技术。所谓中断，就是在输入输出结束时，或硬件发生某种故障时，由相应硬件（即中断机构）向 CPU 发出信号。这时 CPU 立即停下手头的工作而转向处理中断请求，道处理完中断后再继续原来手头的工作。因此，通道技术和中断技术结合起来就可实现 CPU 与 I/O 设备并行工作，即 CPU 启动通道传输数据后便去执行其他程序的计算工作，而通道则进行输入输出操作；当通道工作结束时，再通过中断机构向 CPU 发出中断请求，CPU 则暂停正在执行的操作，对出现的中断进行处理，处理完后则继续原来的工作。这样，就真正做到了 CPU 与 I/O 设备并行工作。此时，多道程序的概念才变为现实。

作业 2（书面版进行了概括）

1. 设计现代 OS 的主要目标是什么？

   方便性，有效性，可扩充性，开放性

2. 试从交互性、及时性以及可靠性方面将分时系统与实时系统进行比较。

   （1）及时性：实时信息处理系统对实时性的要求与分时系统类似，都是以人所能接受的等待时间来确定；而实时控制系统的及时性，是以控制对象所要求的开始截止时间或完成截止时间来确定的，一般为秒级到毫秒级，甚至有的要低于 100 微秒。

   （2）交互性：实时信息处理系统具有交互性，但实时终端设备只是作为执行装置或咨询装置，人与系统的交互仅限于访问系统中某些特定的专用服务程序。分时系统的用户可以与系统进行人机交互，包括在终端上可以直接调试自己的程序，系统能向终端用户提供数据和资源共享等服务。

   （3）可靠性：分时系统也要求系统可靠，但相比之下，实时系统则要求系统具有高度的可靠性。因为任何差错都可能带来巨大的经济损失，甚至是灾难性后果，所以在实时系统中，往往都采取了多级容错措施保障系统的安全性及数据的安全性。

3. 在多道程序技术的 OS 环境下的资源共享与一般情况下的资源共享有何不同？对独占资源应采取何种共享方式？

   （1）OS 环境下与一般情况下的资源共享间的不同点

   ①一般情况下的共享

   一般情况下的共享只是说明某种资源能被大家使用，对于这样的资源共享方式，只要通过适当的安排，用户之间并不会产生对资源的竞争，因此资源管理是比较简单的。

   ②OS 环境下的共享

   OS 环境下的资源共享或称为资源复用，是指系统中的资源可供内存中多个并发执行的进程共同使用。这里在宏观上既限定了时间（进程在内存期间），也限定了地点（内存）。对于这种资源共享方式，其管理就要复杂得多，因为系统中的资源少于多道程序需求的总和，会形成它们对共享资源的争夺。所以，系统必须对资源共享进行妥善管理。

   （2）独占资源应采取的共享方式

   对独占资源应采用互斥共享方式，该共享方式仅当占有该资源的进程访问并释放资源后，才允许另一进程对该资源进行访问。

4. 什么是时分复用技术？举例说明它能提高资源利用率的根本原因是什么。

   （1）时分复用技术的定义
   时分复用技术是将不同的信号相互交织在不同的时间段内，沿着同一个信道传输；在接收端再用某种方法，将各个时间段内的信号提取出来还原成原始信号的通信技术。这种技术可以在同一个信道上传输多路信号。
   （2）时分复用技术能提高资源利用率的根本原因
   时分复用技术能提高资源利用率的根本原因在于，它利用某设备为一用户服务的空闲时间，又转去为其他用户服务使设备得到最充分的利用。

5. 何谓微内核技术？在基于微内核结构的 OS 中，应用了哪些新技术？在微内核中通常提供了哪些功能？

   （1）把操作系统中更多的成分和功能放到更高的层次 (即用户模式) 中去运行，而留下一个尽量小的内核，用它来完成操作系统最基本的核心功能，称这种技术为微内核技术。

   （2）面向对象的程序设计技术。

   （3）在微内核中通常提供了进程 (线程) 管理、低级存储器管理、中断和陷入处理等功能。

附言

最近我的操作系统老师和软件工程老师都在上课时讲鸿蒙 OS 有多么多么划时代，可事实上并非如此。我一问才知道，是华为有人找他们合作，让他们上课时多放入一点鸿蒙的知识。我理解鸿蒙是一个较为优秀的国产定制系统，但是把它等同于目前所有系统、实时操作系统的下一代系统，实在太误人子弟。

19 年鸿蒙说是要完全自主开发内核，22 年现在却在用 AOSPAndriod Open Source Project；“分布式” 有两个，真正意义上的分布式可以同步两台设备上同一版本软件的操作，目前还停留在 SDK 阶段，大肆宣传的那个分布式不过是投屏罢了。

要说怪谁，只能怪一开始饼画太大，缺口已经补不上了。其实按照开源协议使用开源代码不丢人，丢人的是欲盖弥彰啊。

第二章 进程的描述与控制

程序的基本概念

可再现性

为什么程序不能调度？

程序具有独立性，结果再现。如果程序执行过程中，出现结果无法再现的情况，则程序肯定有问题。如果要让程序被调度，必须满足 Berstein 条件（任意两条读写的交集不能为空，很难实现）。

判断程序是否可以并发

（1）程序顺序执行，因为某一时段独占全机，所以结果可再现。

（2）程序并发执行，若不满足 Bernstein 条件，则结果不再现。

总之，程序不可以并发执行。

进程的基本概念

进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位。进程是一个既能用来共享资源，又能描述程序并发执行过程的一个基本单位。

进程控制块 PCB

正是因为有了 PCB，可以记录任意时刻下进程的状态。所谓的调度就是进程在运行中被中断，但 PCB 可以记录此时进程的状态。所以进程是 “动态” 的。

简答题 “程序为什么不能被调度 + 进程为什么可以并发执行” 是捆绑在一起的。

父 / 子标识指向父 / 子进程的 PID

• 进程调度信息

进程的状态：三态、五态、七态

进程的优先级：一个整数

进程调度需要的信息：如等待 CPU 的时间、执行 CPU 的时间等等，是调度的一个参考。

阻塞原因：执行 -> 阻塞状态转换发生的事件

• 进程的控制信息

程序和数据在内存、外存的地址

进程同步和通信机制

资源清单：列出除了 CPU 以外进程所需资源和已经拿到的资源。

链接指针：指出本进程的 pcb 在 pcb 队列中下一个进程的 pcb 首地址

进程控制块 PCB 的组织方式

作业

为什么程序不能被调度？为什么要引入进程？

为什么程序不能调度？

为什么程序不能并发？

为什么要引入进程？

进程控制

进程控制由 “原语” 实现。原语具有 “原子性”，要么不被执行，一旦被执行，不可以被中断。

在关中断指令下，即使有中断信号发射过来，也不会调用中断处理程序去处理中断，这就保证了原语操作不会被打断。而在开中断指令下，才会去处理中断。

原语的基本操作包括：

• 更新 PCB 中的信息（修改进程状态标志、保存当前运行环境到 PCB、从 PCB 中恢复运行环境）
• 将 PCB 插入到合适的队列
• 分配 / 回收资源

创建原语和撤销原语配对，阻塞原语和唤醒原语配对。

进程的执行是 “异步” 的，进程的控制是 “原子性” 的。

进程的状态转换

三态

阻塞态的进程不会立即转为执行态。阻塞态和就绪态的进程在内存中，执行态的进程在 CPU 中。

五态

创建进程的过程在内存里完成。

七态（重要，在后面的章节会有所拓展）

静止阻塞 / 就绪队列的理解

当我们把作业从外存拿到内存时，这个过程叫做高级调度。

进程 PCB 被创建后，PCB 存在内存中，创建的过程在内存中实现；进程创建完成后，如果所需的资源除了内存之外都满足，则进程被对换到静止就绪队列，不参与调度，此时进程创建工作完成。

如果静止阻塞队列中的进程，内存资源得到满足，但是阻塞的原因仍未解除，则从静止阻塞队列进入活动阻塞队列。

如果静止就绪队列中的进程，内存资源得到满足，则从静止就绪队列进入活动就绪队列。

挂起的原因

负荷调节的需要、终端用户的请求、父进程请求、操作系统的需要

挂起的特征

• 该进程不能立即被执行
• 挂起进程可能会等待事件，但所等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件
• 进程进入挂起状态是由于操作系统父进程或进程本身阻止它的运行
• 结束进程挂起状态的命令只能通过操作系统或父进程发出

状态转换的汇总

进程一旦被挂起，就意味着它被对换到了外存中，此时该进程无法再被 CPU 直接调度，除非它被对换回内存中，回到活动就绪态。比如静止就绪态、静止阻塞态，最后要得到 CPU 的调度，都必须经历回归到活动就绪态的过程。

进程的创建（创建原语）

1. 申请空白 PCB
2. 为新进程分配其运行所需的资源
3. 初始化 PCB
4. 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。如果是三态或五态，进程转入就绪态；如果是七态，储存在内存中的为活动就绪态，储存在外存中的为静止就绪态。

进程的终止（撤销原语）

引起进程终止的事件包括正常结束、异常结束和外界干预。

终止进程的过程包括：从 PCB 集合中找到终止进程的 PCB，如果进程正在运行，则立即将它的 CPU 使用权移交给其它进程。接着终止它的所有子进程，将该进程的资源还给父进程或者操作系统，最后再删除 PCB。

1. 进入终止态的进程不能再执行
2. OS 中保留其记录（状态码 + 计时统计数据），供其他进程收集
3. 一旦其他进程完成了对终止状态进程的信息提取，OS 将删除该进程

进程的阻塞（阻塞原语 block）

阻塞进程的过程包括：找到要阻塞的进程的 PCB，保存当前运行环境到 PCB（方便后续恢复），修改 PCB 状态信息。接着暂停进程的运行，将 PCB 插入相应事件的阻塞队列（即改变它的链接地址）。

引起进程阻塞的事件一般是：

• 请求系统分配共享资源失败（系统已无足够的资源）
• 等待某种操作的完成。如请求系统某些服务（比如打印服务）和启动某种操作（比如 I/O 操作）
• 新数据尚未到达
• 等待新任务的到达

进程从运行态切换到阻塞态是一种主动行为，这个主动体现在是进程自己调用了阻塞原语。

进程的唤醒（唤醒原语 wake up）

唤醒进程的过程包括：在事件阻塞队列中找到 PCB 并将进程移出队列，修改 PCB 的状态信息，再将 PCB 插入到就绪队列。

一般在等待的事件发生时，进程就会被唤醒。

阻塞原语和唤醒原语是一对作用刚好相反的原语，必须成对使用。进程从阻塞态切换到运行态，是一个被动的过程，这个被动体现在并不是进程自己调用了唤醒原语，而是 “合作” 或相关进程进行了调用。

进程的切换（切换原语）

前面的原语主要都是操作一个进程，而切换原语同时操作到了两个进程。

切换原语负责让当前运行的进程从 A 切换为 B，具体包括：

• 一方面，将 A 的运行环境保存到 PCB 中，再将其 PCB 移入到相应的队列（如果当前进程是从运行态到阻塞态，那么就进入阻塞队列；如果是从运行态到就绪态，那么就进入就绪队列）
• 另一方面，选择 B 进程运行，更新其 PCB，同时可能会恢复其运行环境（考虑到 B 进程此前可能曾处于阻塞态）

引起进程切换的事件一般有四种：

• 当前进程的时间片被消耗完
• 有更高优先级的进程到达，抢占了当前进程正在使用的 CPU
• 当前进程主动阻塞
• 当前进程终止

进程的挂起（挂起原语 suspend 和激活原语 active）

挂起原语：

将进程从内存对换到外存，具体包括：找到需要挂起的进程的 PCB，检查它的状态并做相应操作（活动就绪态 -> 静止就绪态，活动阻塞态 -> 静止阻塞态），之后将该 PCB 复制到指定的内存区域。若被挂起的进程正在执行，则转向调度程序重新调度。

引起进程挂起的事件，比如用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起。

激活原语：

将进程从外存对换回内存，检查该进程的现行状态并进行相应操作（静止就绪态 -> 活动就绪态，静止阻塞 -> 活动阻塞态）。

引起进程激活的事件，比如，父进程或用户进程请求激活指定进程，或者是某个进程驻留在外存而内存中已有足够的空间。

进程的特征

结构性：程序块、数据块、进程控制块 PCB

动态性：进程是程序在数据集合上的一次执行过程，有生命周期（由创建而产生、由调度而执行、由事件而等待、由撤销而消亡）

并发性：多个进程实体同时存在在内存中，能在一段时间内同时运行，是进程的重要特征

独立性：进程是独立运行、独立获取资源、独立接受调度的基本单位 -> 线程就不独立，它没有资源，依赖于 fork 的进程的资源

异步性：进程按各自独立的、不可预知的速度向前推进。OS 要根据 “进程同步机制” 来解决异步问题。

操作系统的 “虚拟性” 是进程所没有的。

进程同步

基本概念

在多道批处理系统中，多个进程是并发执行的，而并发执行的进程不可避免地需要共享一些系统资源（比如内存、打印机、摄像头等）。然而，有些资源在一个时间段内只允许一个进程使用，诸如各种物理设备、变量、数据、内存缓冲区等，这些称之为临界资源 —— 也就是说，一方面，并发执行的进程需要共享资源；另一方面，临界资源的访问又必须是互斥地进行（不能同时共享），很显然，这会导致资源访问上的矛盾。我们通过进程互斥来解决此类问题。

进程同步：指多个相关进程在执行次序上的协调

进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问

临界资源：一次仅供一个进程使用的资源

临界区：在进程中涉及到临界资源的程序段叫临界区

相关临界区：多个进程的临界区称为相关临界区

进程互斥的基本实现逻辑

为了实现临界资源的互斥访问，可以在逻辑上将一个进程对临界资源的访问过程分为四个部分：

1
2
3
4
5
6

do {
    extry section;       // 进入区
    critical section;    // 临界区
    exit section;        // 退出区
    remainder section;   // 剩余区
} while(true)

• 进入区：A 进程想要访问临界资源，首先会在进入区检查是否可以进入，由于此时没有其它进程占用临界资源，所以检查通过，同时它设置了一个 Flag 标志当前自己正在访问临界资源；
• 临界区：实际访问临界资源的那段代码
• 退出区：负责解除之前的 Flag
• 剩余区：其它处理

对于 B 进程，如果此时它也想要访问这个资源，同样就会在进入区做一个检查，它知道了 A 进程正在访问，所以自己就不能访问了。这样就实现了资源访问的互斥。

同步机制应遵循的原则

空闲让进：临界区空闲时，应该让想要进入临界区的进程立刻进来

忙则等待：同一时刻只允许一个进程进入临界区

有限等待：要求访问临界资源的进程，应该保证在有限时间内进入临界区

让权等待：当 A 进程进入临界区而导致 B 进程不能进入自己的临界区时，应该立刻释放处理机，防止进程陷入 “忙等” 状态。

信号量和 PV 操作

信号量机制

信号量机制可以让用户通过使用操作系统提供的一对原语来对信号量进行操作，从而方便地实现进程互斥和进程同步。信号量（Semaphore）其实就是一个变量，它可以记录系统中某个资源的数量，而原语指的是 wait(S) 原语和 signal(S) 原语（或者说是 P 操作和 V 操作，即通过和释放），可以看作是两个函数。

整型信号量

信号量如果单纯是一个整数型的变量，那么就称为整型信号量，它的值记录了系统中某种资源的数量。在使用整型信号量的情况下，P 、V 操作是类似这样的：

1
2
3
4
5
6
7
8
9
10

int S = 1;
wait(int S)               
{                       
    while(S <= 0)			
    S = S-1              
}
signal(int S)
{
    S = S+1
}

同样以进程 P0，P1 为例进行说明：

1
2
3
4

P0：                   P1:
wait(S)                wait(S)            // 进入区
critical section       critical section   // 临界区
signal(S)              signal(S)          // 退出区 

假定 P0 想要进入临界区，那么它就会在进入区申请资源：执行 P 操作，进行 “检查” 和 “上锁”，由于 S 一开始是 1（表示目前有一个资源可以使用），所以 P0 可以跳过循环，成功申请到资源。此后，S 减一变为 0，代表已经没有可用资源了 —— 这一步也相当于上锁；对于 P1，当他想要申请资源的时候，同样先来到进入区执行 P 操作，由于 S = 0，所以此时 P1 陷入了死循环；再回到 P0 ，他完成任务后会在退出区释放资源，S 加一变为 1，这时候 P1 才有机会退出循环，进而申请资源。

整个过程其实和之前介绍的方法是很类似的，但是由于这次，“检查” 和 “上锁” 两个操作被封装在一个原语里，所以这两个操作必定是一气呵成、无法被打断的，这就避免了某个进程钻空子的现象。但是同时我们也发现，在 P0 时间片用完后，P1 仍然会占用处理机进行没有意义的死循环，也就是仍然违背了 “让权等待” 的原则。

于是在此基础上，又出现了记录型信号量

记录型信号量

与整型信号量仅用一个单一变量记录可用资源数不同，记录型信号量的数据结构类似于一个结构体，它不仅记录了可用资源数 value，而且还提供了一个等待队列 L。

记录型信号量的思想其实是，如果由于 P0 在使用临界资源而导致 P1 暂时无法使用，那么干脆就不给 P1 陷入循环的机会，直接让它自己去阻塞队列，这样 P1 在被唤醒之前，永远无法占用处理机，也自然就不可能出现白白占用处理机的情况。而在 P0 释放资源后，我们才来考虑唤醒 P1。

记录型信号量的结构如下所示：

1
2
3
4

typedef struct {
    int value
    sturct process *L
} semaphore

同时，记录型信号量的 P、V 操作也有所不同，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12

wait (semaphore S){
    S.value--
    if(S.value < 0){
        block(S.L)
    }
}
signal(semaphore S){
    S.value++
    if(S.value <= 0){
        wakeup(S.L)
    }
}

• 这里要注意的第一个地方是，value 是可用的资源数，当它大于 0 的时候自然是存在可用资源（供大于求），当它小于 0 的时候，则说明不仅无可用资源而且有其他进程等着用（供不应求）。
• 第二个地方是，在进入区 value 一定会减一，表示申请到了资源，或者表示存在着某个进程有想要申请资源的意愿
• 执行 ++ 或–前，S.value 为正值时代表可利用的物理资源数；S.value 为负值时，其绝对值代表阻塞队列中等待的进程数。

下面我们用例子来说明记录型信号量工作的过程，为了加深记忆，这里用四个进程来说明：

1
2
3
4

PO:            P1              P2           P3
wait(S)        wait(S)         wait(S)      wait(S)
临界区          临界区           临界区        临界区
signal(S)      signal(S)       signal(S)    signal(S)

假设计算机中有两台可用的打印机 A 和 B（也就是说，value = 2），有四个进程需要用到打印机资源。

一开始假定是 P0 先占有处理机，那么 P0 就会在进入区申请资源 。由于 value 一开始是 2，所以 P0 成功申请到资源 A，之后 value 数量减一变为 1，同时来到临界区开始 “干活”；在 P0 的时间片完了之后，P1 占有处理机，此时同样申请到资源 B，value 由 1 变为 0，之后来到临界区 “干活”。自此，两个打印机都被占用了。

在 P1 的时间片完了之后，P2 占有处理机，value 由 0 变为 -1 < 0，前面我们说过，value < 0 说明无可用资源，所以此时 P2 将自己主动送到了阻塞队列。接着来到了 P3，value 由 -1 变为 -2，P3 同样进入阻塞队列。P2，P3 都从运行态转为阻塞态。

处理机又来到 P0，P0 很快执行完了，于是在退出区执行 P 操作释放资源，将 value 加一变为 -1，之后由于通过 if 检测到阻塞队列中有进程等着用资源，所以马上唤醒了队头的 P2 ，P2 从阻塞态回到就绪态，并直接进入临界区开始自己的工作，在完成后同样来到退出区释放资源，value 由 -1 变为 0，但是在 if 中还是检测到了队列中仍然有进程等着用资源，于是马上把队头的 P3 唤醒，P3 回到就绪态，并直接进入临界区开始工作，此后，value 由 0 变为 1，此时 if 不通过，说明队列中再也没有其它进程等着了，该拿到资源的进程都拿到了。自此，P0，P2，P3 都拿到了 A 资源，而 P1 也在不久后完成工作，在退出区释放资源 B，此时 value 从 1 变回最初的 2 ，代表占用的资源已经全数归还。

当然，实际情况还可能是，P2 拿到了 A 资源，P3 拿到了 B 资源，但分析过程也是大同小异的。

显然，记录型信号量与前面介绍的所有方法最大的区别就在于，不会再有进程白白占用处理机进行没有意义的循环 —— 相反地，这些进程非常 “老实” 地把自己送到了阻塞队列，选择在那里慢慢地等待，等待其它进程完成后将自己唤醒，这种做法 “既方便了别人，也方便了自己”。这就正好与我们多次强调的 “让权等待” 非常契合了。

记录型信号量明显优于整型信号量，所以在提到 PV 操作的时候，一般默认指的都是记录型信号量。

我们通过几道题加深一下印象：

• n 个并发进程，信号量初始值为 1，当 n 个进程都执行 P 操作后，信号量的值为多少？
• 信号量初值为 4，多次 PV 操作后变为 -2，那么获得资源的进程数目是多少？
• 5 个并发进程，信号量初始值为 3，那么信号量取值范围是多少？

（1）每执行一次 P 操作，信号量就会减一，所以对于 n 个并发进程，共需要执行 n 次 P 操作，所以此后信号量的值是 1-n

（2）信号量值为 -2，说明有两个进程位于阻塞队列，说明暂无空闲资源可用，换句话说，四个资源都被占用了，所以共有四个进程获得资源

（3）信号量初始值为 3，所以最大值为 3，如果 5 个进程都执行 P 操作，那么信号量会变成 3-5 = -2，即最小值为 -2，所以取值范围 -2 ~ 3。

信号量机制实现

进程互斥

其实上面讲的例子就已经很好地实现了进程互斥，但是我们可以简化一下写法，如下：

1
2
3
4
5
6
7
8
9
10
11

semaphore mutex = 1;
P0(){
    P(mutex) //使用临界资源前需要加锁
    critical section //临界区代码段
    V(mutex) //使用临界资源前需要解锁
}
P1(){
    P(mutex)
    critical section //临界区代码段
    V(mutex)
}

我们默认已经定义了 semaphore 的结构体，并用互斥信号量 mutex 记录可用资源的个数（进入临界区的名额），初始值为 1。要实现互斥，关键就是要在临界区之前使用 P 操作进行上锁，在临界区之后使用 V 操作进行解锁。

PV 操作要成对出现，但不一定要在同一个进程中。不同的临界资源设置不同的互斥信号量。记录型信号量有时需要自己定义。

进程同步

多个进程（如 P1、P2）一起完成某项任务的时候，如何确保它们按照一定的先后顺序（先 P1 后 P2）有秩序地执行呢？信号量机制也可以很好地实现进程同步。它有三个关键步骤：

• 设置同步信号量初始值为 0
• 在 “前操作” 之后执行 V (S)
• 在 “后操作” 之前执行 P (S)

首先，0 是一个非常关键的 “分水岭”，大于 0 的时候不会发生阻塞，小于 0 则会发生阻塞。

我们要确保 “前操作” 在前面，“后操作” 在后面，实际上只要做到三件事：V 在 “前操作” 后面、P 在 “后操作” 前面、V 在 P 前面。第一个和第二个条件都是可以通过实际书写代码来做到的，而要达到第三个条件 —— V 在 P 前面，就有必要让信号量初始值为 0，因为一旦初始值为 0，则每当 P 想要 “违规” 抢先于 V 执行的时候，都会由于首先执行信号量自减的操作而导致当前所在进程进入阻塞队列 ，也就是说：

P 先于 V 执行 => P 所在进程会被阻塞 => ” 后操作 “始终无法执行

所以，在这种情况下，就只能转而执行 V 所在的进程了。在这个进程里，由于 V 在 “前操作” 后面，所以一定是 “前操作” 执行完了再去执行 V。而执行 V 就会自增信号量，同时唤醒对方进程，对方进程再去顺序执行 P 操作 —— 虽然此时信号量又自减，但是是在加一的基础上自减，所以并不会导致再次阻塞，所以 P 执行完后就顺序执行 “后操作”。由此，我们确保了两个操作一定是严格按照先后顺序执行的。

来看下面的例子：

1
2
3
4
5
6

// 顺序应该是：code1,code2,code4
P0：                 P1:
code 1               P(S)
code 2               code 4
V(S)                 code 5
code 3               code 6

我们设想比较差的情况 —— P1 想要抢先执行 code 4，看看会发生什么。假设是 P1 首先占用处理机，那么就会执行 P 操作，这个操作使得信号量由 0 变成 -1，进而进入 if 代码块，使得 P1 进程阻塞；这之后，处理机来到 P0，执行 code1，code2，V 操作，使得信号量由 -1 变成 0，同时唤醒 P1 进程；P1 进程被唤醒后从 P 操作之后的断点继续执行（P1 被唤醒后不会重新再执行一遍 P 操作，否则会再次进入阻塞。与七态中进程所需资源得到满足后会从阻塞队列转入就绪队列相同，P1 会接着之前停下的地方继续），来到 code4。以上，整个过程确保了按照 code1，code2，code4 的顺序执行。

前驱关系

前面描述的都是两个进程的同步问题，但有时候也可能出现像下图这样多个进程互相依赖、有序运行的情况。其中，code 语句仍然是前操作或者后操作，P1 进程有 code1 语句，P2 进程有 code2 语句… 以此类推，这里要求六个进程必须按照箭头所指方向有序运行。

其实这种情况就是把多个同步问题结合起来，我们仍然可以用信号量机制来实现：

• 每一个前驱关系都是一个同步问题，要保证一前一后的操作
• 为每一个前驱关系各设置一个同步信号量
• 在 “前操作” 之后对相应的同步信号量执行 V 操作
• 在 “后操作” 之前对相应的同步信号量执行 P 操作

代码大概如下：

1
2
3
4
5
6
7
8
9
10

P1:          P2:          P3:          P4:        
code1        P(signal1)   P(signal2)   P(signal3)
V(signal1)   code2        code3        code4 
V(signal2)   V(signal3)   V(signal7)   V(signal5)
             V(signal4)
P5:          P6:         
P(signal4)   P(signal5)   
code5        P(signal6) 
V(signal6)   P(signal7)
             code6

可以观察到，除了 P1 进程之外，其它进程首先执行的都是 P 操作，所以一旦这些进程之一首先拿到处理机使用权，都无一例外地会进入阻塞队列。由于情况很多，这里我们试着只分析某一种情况 ——

假设一开始是 P2 占有处理机，那么由于 signal1 初始为 0，导致了 P2 进队列，此后处理机来到 P3，P3 同样进队列… 以此类推，阻塞队列就会变成：

随后总算来到 P1 进程了，P1 进程作为一切的开始，特殊之处就在于它不是以 P 操作开始的，P1 会首先执行 V (signal1)，这一步把 signal1 加一，同时唤醒 P2 进程，P2 进程进入就绪队列：

再之后，P1 执行 V (signal2)，这一步把 signal2 加一，同时唤醒 P3 进程，P3 进程也进入就绪队列。

P1 执行完之后，就绪队列队头的 P2 进入运行态，执行到 V (signal3) 的时候，signal3 加一，同时唤醒 P4 进程，P4 进程进入就绪队列，

再之后，P2 执行 V (signal4)，这一步把 signal4 加一，同时唤醒 P5 进程，P5 进程也进入就绪队列。

P2 执行完之后，处理机调度就绪队列队头的 P3 开始执行，P3 执行到 V (signal7) 的时候，signal7 加一，注意这一步没有唤醒任何进程

P3 执行完之后，处理机调度就绪队列队头的 P4 开始执行，P4 执行到 V (signal5) 的时候，signal5 加一，同时唤醒 P6 进程，P6 进程进入就绪队列

P4 执行完之后，处理机调度就绪队列队头的 P5 开始执行，P5 执行到 V (signal6) 的时候，signal6 加一，注意这一步没有唤醒任何进程（阻塞队列已经没有进程了）

P5 执行完之后，处理机调度就绪队列队头的 P6 开始执行，P6 的 signal6 、signal7 在前面已经得到加一操作，所以此时绝对不会在这里卡住，可以顺利执行，直到结束。

这样基本就把整个流程过了一遍，当然，经过排列组合之后，分析过程都是大同小异的。

信号量和 PV 操作解决进程同步问题

生产者 - 消费者

生产者 - 消费者问题是系统中并发进程内在关系的一种抽象，是典型的进程同步问题。生产者进程 P1 可以是计算进程、发送进程；而消费者进程 P2 可以是打印进程、接收进程等等。

有界缓冲：

• 一个生产者一次放入缓冲区一个产品，且无限次循环
• 一个消费者一次取出缓冲区一个产品，且无限次循环
• 两个进程独立

要解决的问题：

• 缓冲池满生产者不能放产品
• 缓冲池空消费者不能取产品
• 只能一个生产者或者消费者对缓冲区进行操作

进程个数：2

关系分析：

• 互斥关系 P1、P2 互斥访问缓冲区
• 同步关系 P1 生产后 P2 才能消费

信号量设置：

• 互斥信号量 mutex = 1 ，实现对缓冲区这个资源的互斥访问
• 同步信号量 empty = n ，表示空闲缓冲区的数量
• 同步信号量 full = 0 ，表示非空闲缓冲区的数量，也即产品数量

产品： P1 V P2 P（V 增加，P 锁定，生产者放入产品，消费者取出产品）

空间：P1 P P2 V

先考虑对互斥关系的实现。这里的临界资源是缓冲区，生产者进程把产品放进去，消费者进程从里面取走产品，这两者不能同时进行，所以这里是互斥的关系。P1、P2 都各有一对 PV 操作，用以实现对缓冲区资源的访问。另外，生产者在进行 PV 操作之前，必定要先生产产品；而消费者在进行 PV 操作之后，必定要使用产品。这时候，初步的伪代码是这样的：

1
2
3
4
5
6
7
8

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                              P(mutex)
        P(mutex)                             从缓冲区中取走产品 
		把产品放入缓冲区                       V(mutex)
        V(mutex)                             使用产品 
    }                                   }
}                                   }

接着考虑第一个同步关系，关注空缓冲区。先释放缓冲区，后使用缓冲区，且缓冲区满不再放入产品，所以这里 “前操作” 是消费者释放缓冲区，“后操作” 是生产者占用缓冲区，根据 “前 V 后 P”，我们需要在 “前操作” 之后针对 empty 这个信号量进行一次 V 操作，需要在 “后操作” 之前针对 empty 进行一次 P 操作。生产者执行 P 操作检查是否还有空缓冲区时，若缓冲区已满，将进入阻塞。所以，这时候代码变成：

1
2
3
4
5
6
7
8
9

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                             P(mutex)
        P(empty)                            从缓冲区中取走产品 
		P(mutex)                            V(mutex)
        把产品放入缓冲区                      V(empty)  
        V(mutex)                            使用产品 
    }                                   }     
}                                   }

再考虑第二个同步关系，关注产品。先生产产品并将其放入缓冲区，后从缓冲区取出产品并使用。这里划分出前后两个操作，所以再安排一对 PV 操作：

1
2
3
4
5
6
7
8
9
10

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                            P(full)
        P(empty)                           P(mutex)
		P(mutex)                           从缓冲区中取走产品 
        把产品放入缓冲区                     V(mutex) 
        V(mutex)                           V(empty)  
        V(full)                            使用产品 
    }                                   }     
}                                   }

这就是最后的代码了。现在我们试着跑一下流程：初始的时候 empty = n，表示所有缓冲区都是空闲的，同时 full = 0，表示一个产品都没生产出来。假如处理机首先来到 consumer 进程，那么就会通过 P(full) 检查是否有产品，这里当然是没有，所以它只能进行等待；处理机来到 producer，首先通过 P(empty) 检查是否有空闲缓冲区，这里当然有，于是它开始把生产的产品放入缓冲区，随后记录产品的数量，这个过程可以反复进行，直到所有缓冲区都被占用了，此时 producer 就会进入等待状态，等待 consumer 进程取出产品、释放缓冲区；当然还有可能的情况是，producer 尚未占用完所有缓冲区，进程就切换到 consumer 了，那么这时候 consumer 因为检查到有产品，所以也会取出产品、释放缓冲区。

P 操作不可以随意对调位置，V 操作可以。

这里要注意可能会引起 “死锁” 现象的一种写法。如下所示：

1
2
3
4
5
6
7
8
9
10

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                            P(mutex)
        P(mutex)                           P(full)
		P(empty)                           从缓冲区中取走产品 
        把产品放入缓冲区                     V(mutex) 
        V(mutex)                           V(empty)  
        V(full)                            使用产品 
    }                                   }     
}                                   }

这个写法的问题在于，还没有先检查缓冲区是否没满或者是否非空，就强行进行互斥的 “上锁”。假如还是按照前面的流程，一开始处理机在 consumer 这里，那么 consumer 实际上在没有检查缓冲区是否非空的情况下就直接 “上锁” 了，这导致它在 P(full) 这一步的时候被卡住，只能等待，而在之后切换到 producer 的时候，正常情况下他应该生产可供对方消费的产品，但是由于对方已经上了锁，所以 producer 在 P(mutex) 这一步也被卡住了，只能进行等待。这也就是说，producer 等待 consumer 释放临界区，而 consumer 等待 producer 使用缓冲区，双方陷入循环等待，造成了 “死锁”。

另一种情况，我们也可以设想一开始处理机是在 producer 这里，依然会导致 “死锁”。按照这种情况正常用完全部缓冲区之后，如果处理机还是在 producer 这里，那么 producer 在检查缓冲区是否已满之前也会将自己提前上锁，在 P(empty) 这一步陷入等待，之后即使进程切换到 consumer 这里，它也会因为对方提前上锁，而导致自己在 P(mutex) 这一步陷入等待。也就是说，这不过是前面那种” 死锁 “现象的翻版。

总之，关键就在于不管是消费者进程，还是生产者进程，都不能先上锁再检查，否则就有可能发生死锁。

苹果橘子问题

盘子 缓冲区

2 水果 2 产品

爸爸 妈妈 2 生产者，P1 P2

儿子 女儿 2 消费者，C1 C2

进程个数：4

关系分析：

• 互斥关系 P1、P2、C1、C2 互斥访问缓冲区
• 同步关系 P1 生产后 C1 才能消费，P2 生产后 C2 才能消费

信号量设置：

• 互斥信号量 mutex = 1 ，实现对缓冲区这个资源的互斥访问
• 同步信号量 apple = 0 ，表示苹果的数量
• 同步信号量 orange = 0 ，表示橘子的数量

产品： P1 P2 V C1 C2 P（V 增加，P 锁定，生产者放入产品，消费者取出产品）

空间：P1 P2 P C1 C2 V

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

P1(){
  while(1){
      P(mutex)
      把苹果放入盘子
      V(apple)
  }
}
P2(){
  while(1){
      P(mutex)
      把橘子放入盘子
      V(orange)
  }
}
C1(){
   while(1){
       P(apple)
       从盘子中取走苹果
       V(mutex)
 }
C2(){
  while(1){
       P(orange)
       从盘子中取走橘子
       V(mutex)
 }

银行问题

顾客的 V (full) 与 P (service) 应调换位置，并去除 “获取服务”

service 默认值应为 1

五个哲学家进餐问题

一张圆桌，五个哲学家，五支筷子（每两个哲学家中间会有一支筷子），哲学家要么思考，要么吃饭，吃饭前会拿起左右两边的筷子，吃饭后会放下筷子。如果筷子被其它哲学家拿走，则自己需要等待。我们的目的很简单：保证所有哲学家都有机会吃上饭，不能让一个或者多个哲学家始终无法吃饭。

如果哲学家 0 号拿起左右筷子后，进程切换到哲学家 1 号，那么 1 号是会被阻塞的，所以这样相邻的哲学家中有一个可以吃饭。但是，如果 0 号拿起左筷子后进程切换到 1 号，1 号也拿起自己的左筷子，以此类推，所有的哲学家都只有左筷子，这导致了所有的哲学家都被阻塞，没有任何哲学家能够吃饭，也没有人可以释放筷子，使这些哲学家都陷入无限的等待中，造成 “死锁” 的发生。

解决这个问题有三个方法：

实现原子操作

很容易想到，拿起左筷子和拿起右筷子并不是一个原子操作。准备一个互斥信号量 mutex = 1 ，并把拿筷子的操作封装在一个 PV 操作里。代码如下：

1
2
3
4
5
6
7
8
9
10
11

Pi(){
    while(1){
        P(mutex)
        P(chopstick[i])
        P(chopstick[(i+1)%5])
        V(mutex)
        eat()
        V(chopstick[i])
        V(chopstick[(i+1)%5])
    }
}

在 0 号哲学家拿起左筷子之后，即使发生进程切换，1 号进程也会被卡在 mutex 的 P 操作，被送往阻塞队列，其它进程也同理。所以最后再次来到 0 号进程时便可以顺利拿起右筷子。这种做法保证了有一个哲学家是可以吃饭的。

这里涉及到了一个进程需要一次性两个资源才能完成任务的问题，也可以使用 AND 信号量集机制。AND 信号量集机制的 P 操作是一个相对苛刻的操作，要求一个进程要么拿到全部资源，要么一个资源也拿不到。一开始筷子数量足够，所以 0 号在一开始就可以一次性拿到左右筷子。同理，在释放筷子的时候，也是一次性释放两支筷子。代码如下：

1 2 3 4 5 6 7

Pi(){ while(1){ Swait(chopstick[(i+1)%5],chopstick[i]); eat() Ssignal(chopstick[(i+1)%5],chopstick[i]); } }

只有四个人参与这个过程

之前的情况是五个哲学家，五支筷子，所以容易出现谁也无法吃饭的情况，但是如果规定整个过程最多只有四个哲学家参与，即使这四个哲学家每个人都拿走了一支筷子，也还剩下一支筷子可以分配给某个哲学家。

如何限定 “最多四个人可以参与这个过程” 呢？准备一个互斥信号量 count，但是这个信号量初值不再是 1 ，而是 4，表示最多允许四个哲学家参与过程。当 count 减少到 -1 的时候，就不能再让哲学家进来了。代码如下：

1
2
3
4
5
6
7
8
9
10
11

Pi(){
    while(1){
        P(count)
        P(chopstick[i])
        P(chopstick[(i+1)%5])
        eat()
        V(chopstick[i])
        V(chopstick[(i+1)%5])
        V(count)
    }
}

再来演示前面发生 “死锁” 的过程。假如从 0 号进程开始，在他拿到左筷子之后，进程切换到 1 号进程，由于 count 数量充足，所以它不会阻塞，而是同样拿到了左筷子… 以此类推，到了 4 号哲学家的时候，由于 count = -1 < 0，所以它此时无法进来。 4 号哲学家左边的筷子在第一轮谁也没拿到，第二轮轮到 3 号哲学家时，就可以拿到这支筷子了。总会存在至少一个进程可以吃到饭。

奇数拿左边，偶数拿右边

还可以考虑对拿筷子的优先顺序进行调整。规定对于奇数哲学家，总是先拿左筷子再拿右筷子；对于偶数哲学家，总是先拿右筷子再拿左筷子。那么 0 号哲学家和 1 号哲学家就会争夺 1 号筷子，而 2 号哲学家和 3 号哲学家就会争夺 3 号筷子。如图所示：

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Pi(){
    while(1)
	{
		if(i%2 == 0) // 偶数哲学家，先右后左。
		{
			P(chopstick[(i + 1)%5]) ;
			P(chopstick[i]) ;
			eat();
			V(chopstick[(i + 1)%5]) ;
			V(chopstick[i]) ;
		}
		else   //奇数哲学家，先左后右。
		{
			P(chopstick[i]) ;
			P(chopstick[(i + 1)%5]) ;
			eat();
			V(chopstick[i]) ;
			V(chopstick[(i + 1)%5]) ;
		}
	}
}

假如从 0 号进程开始，很显然 0 号先拿到 1 号筷子，所以在之后切换进程的时候，1 号进程就会直接被阻塞。接着来到 2 号进程，显然他先拿到 3 号筷子，所以之后轮到 3 号进程的时候，3 号进程直接被阻塞。现在轮到 4 号进程，它优先拿到右边的 0 号筷子，之后进程又切换到其它地方。但是，由于先前 3 号进程已经被阻塞，所以在再次轮到 4 号进程的时候，并没有人和他一起争夺 4 号筷子，换言之，4 号进程可以拿到 4 号筷子，再加上之前优先拿到的 0 号筷子，4 号进程现在就可以吃饭了。

这只是其中一种情况，但无论是哪一种，在一对进程的争抢中必然有一个进程首先被送到阻塞队列，因此这个 “被淘汰的” 进程很难再去影响其它进程，相当于间接提高了其它进程拿到筷子的可能性。就像我们上面的例子一样，一下子 “淘汰了” 1 号和 3 号两个进程，并且这两个进程当时并没有带着筷子进入阻塞队列，所以对于其它进程 2 号、4 号、 0 号来说，再次拿到一支筷子的可能性就大大提高了。所以，我们还是能够达到最初的目的，也就是至少让一个哲学家吃上饭。

管程

信号量机制效率低，且通信对用户不透明

管程的基本思想

管程 = 共享资源 + 同步操作

进入管程无法直接访问临界资源，而是通过管程的方法来访问临界资源：

进程通信

进程通信的概念

任何时候都不能直接访问临界资源

共享存储

共享空间是临界区，P1 和 P2 互斥访问（PV 操作）

共享方式上，共享存储分为基于数据结构的共享（较为低级，速度慢限制多，例如开辟一个数组）和基于存储区的共享（高级通信方式，速度快，在内存中划出一块共享存储区，数据结构和存放位置都由进程控制，而不是 OS）

管道通信

从 P2 传回给 P1 时，必须再开辟一个管道，以实现全双工。

消息传递

回顾第一章消息传递等通信方式

直接通信方式

发送进程发送消息之前，首先申请一个缓冲区，之后把消息复制到缓冲区，再通过发送原语把缓冲区发送给接受进程，缓冲区首先到达接受进程的消息缓冲队列队尾。接受进程通过接受原语读取队列消息，并复制到本地变量。

间接通信方式

也叫做信箱通信。发送进程发送的消息首先到达一个消息容器，接受进程再从消息容器中接受消息。

线程

引入线程

首先回忆一下为什么会有进程 —— 在以前，程序是串行执行的，为了让多道程序并发执行，引入了进程。进程虽然显著提高了资源利用率和系统吞吐量，满足了并发的需求，但是这种并发能不能做得更好呢？事实上，进程既是一个携带资源的独立单位，也是独立调度的基本单位，因此，在进程的创建、撤销和切换时，系统必须为之付出较大的时间空间开销。鉴于此，系统不宜设置过多的进程，也不宜频繁地切换进程，这对于并发来说是一种限制。

如何解决这个问题呢？可以把进程看作是管理初创公司的老板，一开始人手不足，老板既要管理公司，也要四处奔跑沟通业务；但是一旦人手充足，那么老板仍然可以管理公司，只是沟通业务的工作就可以交给手下人去执行了。同理，我们可以考虑依然让进程作为拥有资源的独立单位，但是独立调度的基本单位则不再是进程，而是新引入的线程了。

线程与进程

调度的基本单位

引入线程后，调度的基本单位不再是进程，而是线程。线程能够独立运行，且切换的时候，代价远远小于进程切换的代价。同一进程不同线程的切换，不会引起进程的切换。

执行的基本单位

我们可以说进程处于 “执行” 状态，但其实指的是该进程的某个线程正在执行；可以说进程处于 “挂起” 状态，但其实指的是该进程的所有线程都被挂起。但我们不能说 “挂起线程”，只能说 “挂起进程”，因为我们只有在无法为进程分配资源时才会将其挂起，而线程并不携带资源，“挂起线程” 没有意义。

并发性

进程间仍然能够并发，不仅如此，同一进程内不需要切换进程运行环境和内存地址空间，一个进程中的多个线程间也能并发，不同进程中的线程也能够并发，系统并发性提升。

资源

资源由进程携带。为了性能考虑，线程仅占有一点必不可少的资源（比如 TCB，程序计数器等）。虽然线程不携带资源，但它可以使用 fork 的进程的资源，即同一进程的线程共享该进程所拥有的资源。另外，这些线程还共享同一片内存地址空间，所以也可以方便地进行通信。

系统开销

在创建和撤销进程时，系统需要分配或者回收 PCB，分配或者回收资源，所以需要付出一定的时空开销；但是同一进程下的各个线程共享内存空间，线程的创建、撤销和通信的时空开销则小很多。

独立性

同一进程中的线程间独立性要比不同进程间独立性低很多。前者独立性高，因为要防止进程之间彼此干扰和破坏；后者独立性低，因为同一进程的多个线程通常需要协作完成任务，互相之间可访问程度相对来说会比较高。

支持多处理机系统

传统的单线程进程，即使处理机再多，一个进程也只能运行在一个处理机上；但是引入了线程后，一个进程的多个线程可以分配到多个处理机上、并行执行。

线程的状态

线程的状态有：运行、就绪和阻塞，线程的状态转换也类似于进程。

第三章 处理机调度与死锁

处理机调度的层次

三级调度

作业调度

作业调度也即高级调度，这个阶段可以看作是准备阶段。主要任务是根据某种算法从外存上处于后备队列的作业中挑选一个或多个作业，为其分配内存，建立 PCB（进程） 等，使它们具备竞争处理机的能力。

这个阶段进程的状态变化是：无 –> 创建态 –> 就绪态

内存调度

内存调度也即中级调度，这个阶段可以看作是优化阶段。主要任务是将暂时不能运行的进程对换到外存（虚拟内存）中，使它们挂起；而当挂起的进程具备运行条件时，它们会被重新对换回内存，得到激活。引入中级调度的主要目的是提高内存利用率和系统吞吐量，它实际上就是存储器管理中的对换功能。

这个阶段进程的状态变化是： 静止就绪态 –> 活动就绪态，静止阻塞态 –> 活动阻塞态

进程调度

进程调度即低级调度，这个阶段让进程真正运行起来。主要任务是按照某种算法，从就绪队列中选取一个进程（内核级线程），分配处理机给它。进程调度是最基本、次数最频繁的阶段。

这个阶段进程的状态变化是： 就绪态 –> 活动态

根据进程运行的过程中，处理机能否被其它进程抢占，将调度分为两种方式：非抢占式和抢占式，为抢占式时，抢占原则有：优先权原则、短作业（进程）优先原则、时间片原则。

抢占式的缺点在于进程切换频繁发生，系统开销大。优点在于对短作业而言能更及时的得到调度。

队列调度模型

仅有进程调度的队列模型

分时操作系统没有后备作业队列，所以没有高级调度；又因为此系统的应用范围大多只是查询，分配的任务比较简单，以时间片轮转的方式执行终端的任务，所以没有中级调度。也即分时操作系统只有低级调度。

具有高级调度和低级调度的调度队列模型

看到这张图，要想到五态转换

具有三级调度的调度队列模型

看到这张图，要想到七态转换

选择调度算法的原则

面向用户的准则

周转时间

面向批处理 OS

周转时间：作业完成时刻 - 作业提交时刻 = 作业实际运行的时间 + 等待时间

等待时间包括在后备队列上等待作业调度的时间、进程在就绪队列上等待进程调度的时间、等待 I/O 操作完成的时间。作业实际运行的时间即进程在 CPU 上执行的时间。周转时间是衡量批处理 OS 性能的重要指标。

平均周转时间：各作业周转时间之和 / 作业数

带权周转时间：周转时间 / 作业实际运行的时间（>=1，比周转时间更能衡量一个调度算法的优劣）

平均带权周转时间：各作业带权周转时间之和 / 作业数

响应时间

面向分时 OS

响应时间：从用户提交请求到首次产生响应所用的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。包括从键盘输入的请求信息传送到处理机的时间、处理机对请求信息进行处理的时间、将所形成的响应时间回送到终端显示器的时间。

截止时间

面向实时 OS

截止时间：指某任务必须开始执行的最迟时间，或必须完成的最迟时间

优先权准则

面向系统的准则

系统吞吐量：完成作业量 / 总时间

CPU 利用率：忙碌的时间 / 总时间

公平性：确保每个用户每个进程获得合理的 CPU 份额，不会出现饿死情况。

调度算法

先来先服务 (FCFS) 调度算法（作业调度 + 进程调度）

周转时间 = 完成时间 - 到达时间

带权周转时间 = 周转时间 / 服务时间

FCFS 算法对长作业（CPU 时间长的作业）有利，对短作业不利。

最短作业 (SJF) 调度算法（作业调度 + 进程调度）

对这个情况而言，SJF 比 FCFS 更好，尤其是 C。

SJF 调度算法也存在不容忽视的缺点：

• 该算法对长作业不利，更严重的是，如果有一长作业（进程）进入系统的后备队列（就绪队列），由于调度程序总是优先调度那些（即使是后进来的）短作业（进程），将导致长作业（进程）长期不被调度。
• 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。
• 由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

高响应比优先 (HRRN) 调度算法（作业调度 + 进程调度）

HRRN (Highest Response Ratio Next) = HRRF (Highest Response Ratio First)

NUIST 老师习惯用 HRRF，我觉得 HRRN 更合适

FCFS 与 SJF 是片面的调度算法。FCFS 只考虑作业等候时间而忽视了作业的计算时间问题；SJF 只考虑用户估计的作业计算时间而忽视了作业等待时间。

HRRN 是介乎这两者之间的非剥夺式算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。

响应比（带权周转时间） = 作业周转时间 / 作业处理时间 = （作业等待时间 + 作业处理时间） / 作业处理时间 = 1 + 作业等待时间 / 作业处理时间

• 短作业容易得到较高响应比（分母小）
• 长作业等待时间足够长后，也将获得足够高的响应比（分子足够大）
• 饥饿现象不会发生

例题 1

首先调度 J1，然后计算响应比：

1
2
3

J2 1+15/15=2
J3 1+10/5=3
J4 1+5/10=1.5

J3 的响应比最大，调度 J3。随后计算 J3 完成后的响应比：

1
2
3

t=20+5
J2 1+20/15=2.3
J4 1+10/10=2

所以调用 J2，最后调用 J4。

例题 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

FCFS J1 2 3 4
8 10 2 1
10 10.5 1.5+1/6 (1.5+1/6)/0.5=3.3
10.5 10.6 1.6 1.6/0.1=16
10.6 10.8 0.8+2/3 (0.8+2/3)/0.2=7.3
(2+1.5+1/6+1.6+0.8+2/3)/4=1.68
(1+(1.5+1/6)/0.5+1.6/0.1+(0.8+2/3)/0.2)/4=6.92
SJF J1 3 4 2
8 10 2 1
10.3 10.8 1.8+1/6 (1.8+1/6)/0.5=3.93
10 10.1 1.1 1.1/0.1=11
10.1 10.3 0.3+2/3 (0.3+2/3)/0.2=4.83
(2+1.8+1/6+1.1+0.3+2/3)/4=1.51
(1+(1.8+1/6)/0.5+1.1/0.1+(0.3+2/3)/0.2)/4=5.19
HRRF J1 
8 10 2 1
(10) J2 未完成

高优先权 (FPF) 调度算法（作业调度 + 进程调度）

非抢占式优先权算法

和 HRRN 算法很像，进程会正常运行，直到结束之后才发生调度，在调度的时候会选择队列中优先级最高的进程。

抢占式优先权算法

除了正常运行结束会发生调度之外，每次就绪队列有新的进程到达时还会做一次检查，如果新到达进程优先级高于正在运行进程的优先级，那么新到达进程会抢占处理机。

静态优先权

静态优先级，指的是进程的优先级在它创建的时候就确定了，此后一直不会改变。一般认为系统进程优先级要高于用户进程优先级；前台进程优先级高于后台进程优先级；I/O 型进程优先级会比较高。

动态优先权

动态优先级，会尽量遵循公平的原则。也就是说，如果某个进程实在等得太久，那么不妨提高它的优先级，让他有机会被调度；反之，如果某个进程占用处理机时间过长，那么就要考虑降低它的优先级，不要让他一直 “霸占” 处理机了。另外，之前说过 I/O 型进程的优先级会很高，所以如果某个进程频繁进行 I/O 操作，也可以考虑提高它的优先级。

优先级算法的优点在于区分了各个进程的紧急程度，比较紧急重要的进程会优先得到处理，因此它适用于实时操作系统。另外，由于动态优先级的存在，使得它对进程的调度相对灵活很多。缺点则是，如果源源不断进来了一些高优先级的进程，那么优先级相对较低的进程可能一直无法执行，进而导致饥饿现象的发生。这点和 HRRN 算法也是很像的。（其实也可以把 HRRN 算法看作优先级算法的一种特殊情况，将响应比作为优先级评判的标准）

例题 1

可剥夺：

1
2
3
4
5
6
7
8

开始执行时间:进程 0:P1 3:P2 5:P3 10:P4 20:P3 21:P1 23:DONE
进程 周转时间 带权周转时间
P1 23-0=23 23/5=4.6
P2 5-3=2 2/2=1
P3 21-5=16 16/6=2.67
P4 20-10=10 10/10=1
平均周转时间：12.75
带权周转时间：2.32

时间片轮转 (RR) 调度算法（进程调度）

RR 算法的特点则在于 “公平分配”，按照进程到达就绪队列的顺序，轮流让每个进程执行一个相等长度的时间片，若在自己的时间片内没有执行完，则进程自动进入就绪队列队尾，并调度队头进程运行。整体呈现出 “交替” 的特点。因为进程即使没运行完也会发生调度，所以这是一个抢占式的算法。

答题需表格 + 执行顺序时间线

例题 1

1
2
3
4
5
6
7

开始执行时间:进程(剩余时间)：0:P1(33) 20:P2(0) 37:P3(48) 57:P4(4) 77:P1(13) 97:P3(28) 117:P4(0) 121:P1(0)  134:P3(8) 154:P3(0) 162:DONE
P1 134 134/50
P2 17 17/17
P3 162 162/68
P4 121 121/24
平均周转时间：108.5
带权平均周转时间：2.78

多级反馈调度算法（进程调度）

• 有多个级别的就绪队列，各级队列优先级从高到低，时间片从小到大
• 每次有新进程到达，都会首先进入第一级队列，并按 FCFS 算法被分配时间片。如果时间片用完了而进程还没执行完，那么该进程将被送到下一级队列队尾。如果当前已经是最后一级，则重新放回当前队列队尾
• 当且仅当上层级别的队列为空时，下一级队列的进程才有机会被调度
• 关于抢占：如果某个进程运行的时候，比它所在队列级别更高的队列中有新进程到达，则那个新进程会抢占处理机，而当前正在运行的进程会被送到当前队列队尾

优点：

• 对各类型进程相对公平（FCFS 的优点）：谁先进来，谁就会处于高级队列，优先得到服务
• 每个新到达的进程都可以很快就得到响应（RR 的优点）：新到达的进程首先在高级队列，可以很快得到响应
• 短进程只用较少的时间就可完成（SPF 的优点）：不需要经历过多的队列
• 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）
• 对各类型用户友好。对于终端型用户来说，他们提交的大多属于较小的交互型作业，系统只要能使这些作业在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意；对短批处理作业用户来说，只需在第一队列中执行一个时间片，或至多在第二和第三队列中各执行一个时间片即可完成；对长批处理作业用户来说，只要让作业依次在第 1, 2，… n 个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。

缺点：

• 可能会导致饥饿。若有源源不断的短进程到达第一队列，那么这些进程会持续被调度，使得下面一级的那些进程一直得不到调度，导致饥饿现象的发生。

例题 1

D 就绪队列 2 有误

例题 2（只有 3 个就绪队列的例题 1）

1
2
3
4
5
6
7
8
9
10
11

A 2-0=2 2/2
B 22-2=20 20/6
C 58-4=54 54/10
D 66-6=60 60/14
E 110-8=102 102/18
F 118-10=108 108/22
G 146-12=134 134/26
H 154-14=140 140/30
I 166-16=150 150/34
平均周转时间：85.56
带权平均周转时间：4.31

平均周转时间 = 结束时间 - 开始时间 ×，平均周转时间 = 结束时间 - 到达时间 √。若没有给到达时间，则默认所有任务一开始就同时到达。

死锁

出现死锁的场景

进程推进顺序不当

资源竞争

产生死锁的四个必要条件

互斥

进程互斥使用资源。因为如果是可以共享使用的资源，多个进程直接同时使用就好，不会陷入等待的僵局。

非抢占

一个进程不能抢夺其他进程占有的资源。因为如果其它进程可以抢占资源，那么就是直接拿到资源了，也不会陷入等待的僵局。

请求和占有

申请新资源时不释放已占有资源，即要求进程是在占有（holding）至少一个资源的前提下，请求（waiting）新的资源的。由于新的资源被其它进程占有，此时，发出请求的进程就会带着自己占有的资源进入阻塞状态。假设 P1，P2 分别都需要 R1，R2 资源，如果是下面这种方式：

1
2
3

P1:          P2:
request(R1)  request(R2)
request(R2)  request(R1) 

如果 P1 请求到了 R1 资源之后，P2 请求到了 R2 资源，那么此后不管是哪个进程再次请求资源，都是在占有资源的前提下请求的，此时就会带着这个资源陷入阻塞状态。P1 和 P2 需要互相等待，发生了死锁。

换一种情况：

1
2
3

P1:          P2:
request(R1)  request(R1)
request(R2)  request(R2) 

如果 P1 请求到了 R1 资源，那么 P2 在请求 R1 的时候虽然也会阻塞，但是是在不占有资源的情况下阻塞的，不像之前那样占有 R2。所以，此时 P1 可以正常完成任务并释放 R1，P2 拿到 R1 之后再去执行任务。这种情况就不会发生死锁。

环路循环等待

要求存在一条进程资源的循环等待链，链中的每一个进程占有的资源同时被另一个进程所请求。

[P0，P1，P2，…Pn] 中的 P0 正在等待 P1 占用的资源，P1 正在等待 P2 占用的资源……Pn 正在等待 P0 占用的资源。

发生死锁时一定有循环等待（因为是死锁的必要条件），但是发生循环等待的时候不一定会发生死锁。这是因为，如果循环等待链中的 P1 和 链外的 P6 都占有某个进程 P2 请求的资源，那么 P2 完全可以选择不等待 P1 释放该资源，而是等待 P6 释放资源。这样就不会发生死锁了。

预防死锁

通过设置某些限制条件，以牺牲资源利用率和系统吞吐量为代价，破坏产生死锁的四个必要条件中的一个或几个。特点是简单、限制条件严格，有可能导致资源利用率和系统吞吐量低

破坏互斥条件

如果可以把某个互斥资源转化成共享资源，那么就不存在互相等待资源的情况了，也就不会发生死锁。

破坏非抢占条件

如果资源是可以抢占的，那么在进程需要资源的时候，就可以直接抢占了，不存在互相等待资源的情况，也就不会发生死锁。要破坏非抢占条件，做到可抢占，可以从两个角度（方案）考虑：

• 从占有资源的进程的角度考虑，如果它请求不到新的资源，那么它必须立即释放占有的全部资源，以后需要的时候重新申请
• 从请求资源的进程的角度考虑，如果它需要请求资源，那么操作系统会帮助它抢占相关资源。比如现在有一个优先级更高的进程，如果是采用优先级调度算法，那么它将有机会在操作系统的帮助下抢占到资源。

这种做法的问题在于：

• 实现起来复杂
• 某个占有资源的进程释放占有的全部资源时，可能会导致工作进度丢失
• 反复的申请和释放资源会增加系统开销
• 可能导致饥饿

破坏 “请求和占有” 条件

所有进程在运行之前，都必须一次性地申请其在整个行过程中的所需的全部资源，此时，若系统有足够的资源分配给某进程，便可把其需要的所有资源分配给该进程，这样，该进程在整个运行期间便不会再提出资源要求。

该方法可能导致饥饿现象。若有 ABC 三类进程，A 用到 a 资源，B 用到 b 资源，C 用到 ab 资源，那么 AB 会在运行前事先申请到 ab 资源，如果 AB 源源不断进入就绪队列，那么 C 进程没有办法在运行前拿到 ab 资源，就进入了饥饿状态。

破坏 “环路循环等待” 条件

将所有资源按类型进行线性排队并编号，所有进程必须严格按照序号递增的顺序请求资源，即先请求小编号资源，后请求大编号资源。这样，在形成的资源分配图中，不再出现环路。

优点：和前两种相比，资源利用率和吞吐量利用率高

缺点：系统中各类资源所分配的序号必须相对稳定，限制了新类型设备的增加；作业（进程）使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费；为方便用户，系统对用户在编程时所施加的限制条件应尽量少，但必然限制用户简单、自主地编程。

以之前的例子讲解：

1
2
3

P1:          P2:
request(R1)  request(R2)
request(R2)  request(R1) 

这种情况下资源请求是无序的，尤其是 P2，它没有按照递增的顺序请求资源，因此很容易发生死锁。但是如果是这种情况：

1
2
3

P1:          P2:
request(R1)  request(R1)
request(R2)  request(R2) 

实际上，这里除了破坏 “占有和请求条件” 之外，更重要的是破坏了循环等待条件 —— 因为这里是按照编号递增的顺序请求资源了，不管是 P1 还是 P2，都是先请求小编号的 R1，后请求大编号的 R2，这样的话就不会发生死锁，因为此时两个进程对资源的请求并没有形成一个闭环。

也可以拿之前的哲学家进餐问题解释，如果我们给每个筷子进行编号，规定必须按照编号递增的顺序申请资源，那么从 0 号到 3 号，它们依然会拿起左手边小编号的筷子，但是轮到 4 号的时候，情况就不一样了。因为对于 4 号来说，右手筷子编号更小，所以在拿到左手筷子之前，它会先试图拿右手筷子，又由于该筷子已经被 0 号拿走，4 号被阻塞。对于 3 号来说，没人和自己抢 4 号筷子了，所以 3 号哲学家可以拿到左右筷子，避免了死锁。

还可以从另一个角度考虑，因为我们是按照编号递增的顺序请求资源的，设想在某一时刻，若干个进程中必定有一个进程的资源编号暂时是所有进程中最大的，那么该进程在此后申请新的资源的时候，只可能申请编号更大的资源，一方面避开了小编号、可能已经被拿走的资源，也就避开了阻塞和死锁，另一方面，大编号资源并没有被其他进程拿走。因此这个时候，该进程一定可以拿到资源，不会有死锁现象。

但这种预防死锁的方法，问题在于：

• 如何进行编号，从什么角度考虑？
• 如果增加资源或设备，怎么重新编号？
• 虽然资源请求上是先小编号资源，后大编号资源，但是实际使用的时候可能是得先使用大编号资源，这就意味着小编号资源虽然暂时用不到，但还是被进程占用，明显有资源浪费的问题。

避免死锁

安全状态：指系统按某种顺序 (P1,P2,…,Pn)(称 < P1,P2,…,Pn > 为安全序列) 来为每个进程分配其所需资源，直至满足每个进程资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态

安全状态之例：假定系统中有三个进程 P1、P2 和 P3, 共有 12 台磁带机。进程 P1 总共要求 10 台磁带机，P2 和 P3 分别要求 4 台和 9 台。假设在 T0 时刻，进程 P1、P2 和 P3 分别获得 5 台、2 台和 2 台，尚有 3 台未分配，如下表所示：

进程 - 资源分配图

当各类资源都只有一个的时候，可以使用这种方法求解。资源分配图是描述进程和资源之间请求和分配关系的有向图，从进程指向资源的虚线代表资源需求（要使用），从进程指向资源的实线代表资源请求（申请使用），从资源指向进程的实线代表资源分配（正在使用）。

• 如果 P1 请求 R2 资源：那么就把 P1 到 R2 的需求边改为 R2 到 P1 的分配边，此时整个图中不存在回路，那么就认为系统处于安全状态，不会发生死锁。可以分配资源。
• 如果 P2 请求 R2 资源：那么就把 P2 到 R2 的需求边改为 R2 到 P2 的分配边，此时整个图中存在一条回路，那么就认为系统处于不安全状态，有可能发生死锁。不可以分配资源。

银行家算法

• 银行家拥有一笔周转资金
• 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能放贷
• 银行家应谨慎的贷款，防止出现坏帐

银行家算法案例

设银行家有 10 万贷款，P,Q,R 分别需要 8,3,9 万元搞项目（假设任何人满足资金总额后都会归还所有贷款)

如果 P 已申请到了 4 万：

• Q 要申请 2 万，显然，如果满足 Q 的申请，有安全序列 <P,Q,R>/<Q,P,R>
• R 要申请 4 万，显然，如果满足 R 的申请，则不存在安全序列。

基本思想：分配申请的资源前，判断系统是否安全。如果不安全，则不分配。

银行家算法过程

假设系统中有 n 个进程，m 种资源，规定：

• 每个进程在运行前先声明自己需要的最大资源数，用一个 n*m 的最大需求矩阵 Max 表示各个进程的需求情况，比如 Max[i][j]= K 就表示进程 i 需要 K 个 j 类型资源
• 用一个 n*m 的分配矩阵 Allocation 表示各个进程的已分配资源情况
• 用一个 n*m 的需求矩阵 Need 表示各个进程的最多还需要资源情况，Need = Max - Allocation
• 用一个 m 长度的一维数组 Avaliable 表示剩余资源数目
• 用一个 m 长度的申请矩阵 Request[i][j] 表示某个进程 i 某次申请的 j 类型资源数目

按照之前说过的流程图，银行家算法的工作过程是：

• 请求资源数是否超过最大资源数？Request[i][j]<=Need[i][j]，则到下一步；否则出错
• 请求资源数是否超过剩余资源数？Request[i][j]<=Available[j]，则到下一步；否则说明资源不够，进程等待
• 尝试进行资源分配。
  • 剩余资源减少：Available = Available - Request
  • 已分配资源增加：Allocation[i][j] = Allocation[i][j] + Request[i][j]
  • 需求资源减少：Need[i][j] = Need[i][j] - Request[i][j]
• 对分配后的状态通过安全性算法进行预判：
  • 安全状态：不会发生死锁，可以分配资源
  • 不安全状态：可能发生死锁，不分配资源，进程进入等待资源状态，并恢复系统状态

例题 1

假如现在有 P0 ~ P4 共五个进程，ABC 三类资源，个数为（10,5,7）。在某一时刻，资源剩余量为（3,3,2），各个进程的最大需求量、已分配量和需求量如下图所示：

如何检测当前是否处于安全状态呢？尝试寻找安全序列：

• 当前剩余资源（3,3,2），无法满足 P0 需要的（7,4,3），所以不能首先分配给 P0；但是可以满足 P1 需要的（1,2,2），P3 需要的（0,1,1），所以可以分配给 P1 和 P3，P1 和 P3 进入安全序列。
• P1 和 P3 执行完之后，归还资源，剩余资源（3,3,2）+（2,0,0）+（2,1,1）=（7,4,3），可以满足 P0 需要的（7,4,3），P2 需要的（6,0,0），P4 需要的（4,3,1），所以 P0、P2、P4 依次进入安全序列。
• 所以存在安全序列 P1->P3->P0->P2->P4 ，使得按照这个顺序分配资源后，每个进程都能拿到需要的资源并顺利完成，所以该状态是安全状态。

看另一种情况。假如现在有 P0 ~ P4 共五个进程，ABC 三类资源，个数为（10,5,7）。在某一时刻，资源剩余量为（3,3,2），各个进程的最大需求量、已分配量和需求量如下图所示：

当尝试寻找安全序列的时候，容易发现 P1 P3 可以满足，所以 P1 P3 进入安全序列，此后剩余资源为（7,4,3）。又由于 P0 P2 P4 都是无法满足的，所以实际上并不存在一个安全序列使得所有进程都能被分配资源。因此状态是不安全状态，可能发生死锁，取消资源分配。

例题 2

t0 时刻安全状态检查。如果 t0 时刻都不安全，则后面的部分都不用做了。但是考试时 t0 都是安全的。

安全序列之一：<p1,p3,p4,p2,p0>

例题 3

在银行家算法中，若出现下述资源分配情况，试问：

(1) 该状态是否安全？

1
2
3
4
5
6

P0 1622+0032=1654
P3 1654+0332=1986
P1 1986+1000=2986
P4 2986+0014=299 10
P2 299 10+1354=3 12 14 14
故存在安全序列P0 P3 P1 P4 P2

(2) 若进程 P2 提出请求 Request (1,2,2,2) 后，系统能否将资源分配给它？

1
2

P2的Allocation加上1 2 2 2为2 5 7 6，Need变为1 1 3 4， Available变为0 4 0 0
由(1)可知，此时系统资源无法满足任何一个进程，安全性检查不通过，无法分配资源

检测死锁

简化进程 - 资源分配图

各类资源只有一个

当各类资源只有一个的时候，可以把资源分配图化简为一个等待图（wait-for graph），比如说 A 进程请求 X 资源、X 资源被 B 进程占有，这个过程可以被简化为 A 进程等待 B 进程。比如说下面，左图被转化为对应的右图：

死锁定理：有环路，且每个类型的资源只有一个，则一定会出现死锁。

• 如果进程 - 资源分配图中无环路，则此时系统没有发生死锁。
• 如果进程 - 资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充分和必要条件，环路中的进程便为死锁进程。
• 如果进程 - 资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。

各类资源有多个

各类资源有多个的时候，我们可能需要根据给定表或给定图检测是否有死锁。对于前者，可以沿用之前的安全性算法进行检测；对于后者，可以尝试简化资源分配图。

给定一个资源分配图为例：

约定蓝色线为请求边，黑色线为分配边，资源中的一个圆点代表一个该类资源。那么 P1 占有两个 R1 资源，请求一个 R2 资源；P2 占有一个 R2 资源，一个 R1 资源，请求一个 R1 资源。

• 首先找出非阻塞非孤立的进程点。P1 P2 都不是孤立的，所谓非阻塞指的是进程请求的资源数量足够，比如说 P2 请求 R1，由于 R1 已经有两个被 P1 占有，一个被 P2 占有，无多余资源，所以 P2 是阻塞的；而 P1 请求 R2，因为 R2 只有一个被 P2 占有，有多余资源，P1 是非阻塞的。这样就找到了符合条件的进程点 P1
• 去除这样的点的所有边。那么就会去除 P1 的所有边，归还所有资源。P1 成为孤立点
• 重复第一步和第二步。此时，因为这次 P2 请求的 R2 资源是足够的（被 P1 释放了），所以 P2 是非阻塞非孤立的点，把他的全部边去除
• 由于图中所有的边都能被消除，所以称该图可以被简化，因此它不存在死锁（如果不可简化，则存在死锁）

又比如下面这种情况：

首先还是找一个非孤立非阻塞的点，很显然只有 P3 符合要求。之后把 P3 的分配边去掉，会发现 P1 和 P2 都是非孤立阻塞的点，它们的边都无法消除。此时就说该资源分配图不能简化，因此存在死锁。

解除死锁

资源剥夺法

将部分死锁的进程挂起并抢占它的资源，将这些资源分配给其它的死锁进程。但应防止被挂起的进程长时间得不到资源而饥饿。

注意不是抢占非死锁进程的资源。

终止进程法

强制终止部分或全部死锁进程，并剥夺它们的资源。这种方式的优点是实现简单，但可能付出很大的代价。因为有些进程可能已经运行了很长时间，一旦被终止就功亏一篑了。

进程回退法

让一个或多个死锁进程回退到足以避免死锁的地步。这要求系统必须记录进程的历史信息，设置还原点。

无论是哪种方法，都可以从以下角度考虑需要做出牺牲的进程：

• 优先级比较低的进程做出牺牲
• 占用过多资源的进程做出牺牲
• 执行时间长的进程不做出牺牲
• 快要完成的进程不做出牺牲
• 交互式进程不做出牺牲

第四章 存储器管理

多级存储器结构

程序的装入与链接

用户程序在执行前必须先进入内存，具体来说包括以下步骤：

• 编译：由编译程序将用户源程序编译成多个目标模块
• 链接：由链接程序将编译后的多个目标模块和所需的库函数链接在一起，形成一个总的装入模块
• 装入：由装入程序将装入模块装入内存运行

链接

根据链接的时间不同进行区分

静态链接

直接将编译后的多个目标模块和所需的库函数链接在一起，形成一个不再拆开的装入模块，该模块整体装入内存。

装入时动态链接

不事先进行链接，而是一边装入内存，一边进行链接，即在装入一个目标模块时，若发生一个外部模块调用事件，装入程序就去找出相应的外部目标模块。这种方式便于修改和更新，便于实现对目标模块的共享。

运行时动态链接

不事先进行链接，而是一边执行程序，一边进行模块的装入和链接，这种方式可以确保只装入和链接那些在执行时需要用到的模块，而不会引入多余的、实际根本用不到的模块，因此拥有装入时动态链接的优点，还加快了程序的装入过程，有利于节省内存空间。

装入

装入模块中指令所涉及的地址是逻辑地址（相对地址），往往并不是装入内存后的物理地址，因此在装入模块装入内存后，需要将原先的逻辑地址转换成物理地址（绝对地址）。在下面三种装入方式中，对逻辑地址的处理是不同的。

绝对装入方式

程序员如果事先知道程序最终装入内存时的物理地址（如在单道程序运行环境中），那么编译程序产生的目标模块中可以直接使用物理地址，此时的逻辑地址与物理地址一样，模块在装入到内存的时候也无需进行地址转换的工作。

静态重定位装入方式

在多道程序运行环境中，无法事先知道程序最终装入内存时的物理地址，所以目标模块中只能使用逻辑地址，所有指令中涉及到的逻辑地址都是从 0 开始的。装入模块可以装入到内存的合适位置，并且在装入的时候会进行地址转换（重定位）的工作。例如将程序中起始于 0 的逻辑地址都转换为起始于 10000 的物理地址。

“静态” 主要体现在程序装入内存后，在运行期间就不能再移动了，因为一旦移动就意味着需要再次更改物理地址，而地址是无法修改的，否则会发生错误。

动态重定位装入方式

很多时候，程序在内存中的位置会经常发生改变，比如在外存和内存之间对换。位置不会是一成不变的，这时候就要采用动态重定位装入方式。这种方式并不急于在装入的时候就进行地址转换，而是在程序真正执行的时候才去进行地址转换的工作。

这意味着程序在装入内存后，在运行期间是可以移动的。因为不管移动到哪个内存位置，始终会有一个重定位寄存器用于记录和更新装入模块当前的物理起始地址，逻辑地址只需要和这个物理起始地址相加即可得到物理地址。

连续内存分配

外部碎片和内部碎片

• 外部碎片指的是尚未分配出去、由于太小而无法分配出去的内存空间（化整为零）
• 内部碎片指的是已经分配出去、但没有完全得到利用的内存空间

单一连续分配

单一连续分配只适用于单用户、单任务的操作系统中，它会把整个内存区划分为系统区和用户区，一道用户程序就会独占整个用户区，因此存储器的利用率非常低、内部碎片很大（分配了整个用户区，但实际用到的空间并不多）。

固定分区分配

固定分区分配是最简单的多道程序的存储管理方式，依然是将整个内存区划分为系统区和用户区，但是用户区进一步细分：划分为多个固定大小的分区，系统启动后就已经分好了分区，一个分区放一个进程。

每个分区的大小可以相等也可以不等：

• 如果每个分区大小相等，缺乏灵活性：对于小进程，无法利用全部空间而产生内部碎片；对于大进程，找不到大小足够的分区。

• 如果每个分区的大小不等，提高了灵活度，可以将用户区划分为大量的小分区、适量的中分区、少量的大分区，并维护一张记录了分区号、分区大小、分区起始地址、分区分配状态的分区使用表。每次需要为进程分配内存空间的时候，先在这张表上进行检索，找到一个合适的分区分配给它。

  这种划分方式可以认为不存在过小的、分配不出去的内存空间，不会产生外部碎片；但是，由于提前划分了分区，不能保证一个进程完全利用完某个分区，分区会产生内部碎片：

  

  浪费了 7+23+87+211K=328K 的空间

动态分区分配

概括

动态分区分配方式比前面的分配方式要灵活很多，类似于按需分配，不是预先划分好，而是进程需要多少内存空间，就给它多少内存空间。

但这种分配方式需要考虑的问题是，当一个进程有多个空闲的内存分区可供选择的时候，它应该使用哪个空间呢？比如进程 2 运行完释放了 20K 的内存空间，此时进程 4 进来，也需要用到 20K 的内存空间，它既可以选择占用进程 2 释放的空间，也可以选择占用后面没被用到的一大片空间。

因此，我们需要一种算法来决定进程 4 的选择，而且为了更好地描述内存使用情况，我们同样要像固定分区分配一样维护一张空闲分区表或者一个空闲分区链。

主要过程

假设进程 X 需要用到 x 大小的内存空间，在某种算法下，系统会检索空闲分区表或者空闲分区链，决定将某个空闲分区分配给这个进程。假设这个空闲分区大小为 y（y>x），若 y-x 的值小于预先设定的一个阈值，说明进程可以充分利用这个空闲分区，可以将整个分区直接分配给进程；若 y-x 的值大于这个阈值，说明空闲分区无法得到完全的利用，可以将整个分区能够被充分利用的那部分（也即 x）划分给进程，而剩下的 y-x 则继续留在空闲分区表（因为只记录空闲分区，所以没有 “状态” 项）或者空闲分区链（不讲不考察）中。

基于顺序搜索的算法

首次适应（FF）

将多个空闲分区按照地址递增的顺序排列，每次分配内存的时候顺序查找空闲分区表，找到第一个大小能满足要求的空闲分区。

• 由于地址一开始就是确定下来的，能够保证顺序始终是递增的，因此这种算法无需频繁地变更空闲分区的顺序，而且每次优先利用低地址空间，保证了高地址空间有足够大的空闲区域可供大进程使用。
• 但是，因为每次优先利用低地址空间，所以低地址空间被不断分割，产生了大量的外部碎片；而且，每次都是从头开始寻找空闲空间，效率并不高。

邻近适应（NF）

邻近适应算法（循环首次适应算法）克服了首次适应算法的缺点，它同样是将多个空闲分区按照地址递增的顺序排列，不同的是，每次查找都是从上次查找结束的位置开始查找的

• 不会从头开始一个个找，一定程度上提高了效率；而且，它会更趋向于往后推进，避免了对低地址空间重复地进行分割，进而避免了大量外部碎片的产生。

• 优点同时也是缺点，由于邻近适应算法更趋向于往后推进，所以更可能分割高地址空间，这就破坏了首次适应算法的初衷，导致大进程可能没有足够的空闲空间可利用。

最佳适应（BF）

连续分配的方式规定，为各个进程分配的必须是一块连续的空间，因此对于一块内存空间来说，若它不断被分割，则意味着它能容纳下大进程的可能性越低。为了保证有足够的内存空间可以容纳大进程，基本思想应该是优先利用小的空闲分区，而保留大的空闲分区。

最佳适应算法将空闲分区按照容量递增的顺序排列，每次分配内存的时候顺序查找空闲分区表，找到第一个大小能满足要求的空闲分区。

• 分配操作主要集中在小的空闲分区那里进行，保证了有大的空闲分区可以用来容纳大进程。
• 因为要按照容量递增的顺序排列，而每次内存的分配和回收都会改变某一块空间的大小，每次在进行分配和回收的时候，基本都要重新进行排序，算法开销大。而且，由于分配操作集中在小的空闲分区进行，导致它们不断被分割，容易产生大量外部碎片。

最坏适应 （WF）

为了克服最佳适应算法的缺点，最坏适应算法规定，将空闲分区按照容量递减的顺序排列，每次分配内存的时候顺序查找空闲分区表，找到第一个大小能满足要求的空闲分区。

• 最坏适应算法优先使用大的空闲分区，而大的空闲分区由于容量充足，即使被不断分割，也可以保证剩余空间不至于太小，依然能够被新的进程利用，大幅度减少了外部碎片的产生。
• 但是，这又破坏了最佳适应算法的初衷，因为优先使用大的空闲分区，很容易导致后续的大进程没有足够大小的空闲分区可以利用。并且，这种算法也无法避免分配和回收之后的重新排序。

总结

由于动态分区分配不是事先划分好区域，而是 “按需分配”，所以不会出现区域划分出去后无法完全得到利用的情况，也即不会产生内部碎片；但是可能出现内存空间太小而无法被分配出去的情况，也即可能产生外部碎片。

基于索引搜索的算法

当系统很大的时候，内存分区会很多，这时候还采取基于顺序搜索的动态分区分配算法的话，效率并不高。因此出现了基于索引搜索的动态分区分配算法。

快速适应

快速适应算法（分类搜索算法）将空闲分区按照进程常用的空间大小进行分类，比如 2KB 为一类，4KB 为一类，6KB 为一类等，对于每一类空闲分区，会有一个单独的空闲分区链表。此外，还会有一张总的管理索引表，索引表的每一个表项对应了一类空闲分区。

在为进程分配分区的时候，首先会根据进程长度，从索引表中找到能容纳它的最小空闲区链表，接着将该链表的第一块分配给进程。

• 因为前面已经进行了合理的分类，因此这种方法不会对任何分区产生分割，也不会产生外部或者内部碎片，并且查找效率很高
• 但是，回收、合并分区时的算法复杂，系统开销比较大

伙伴系统

接下来的伙伴关系和哈希算法为自学内容

举个例子

假设系统总的内存为 512KB，现有进程活动如下：

• 进程 A 请求 100KB，进程 B 请求 50KB，进程 C 请求 100KB
• 进程 A 释放 100KB
• 进程 D 请求 20KB
• 进程 D 释放 20KB
• 进程 B 释放 50KB

按照伙伴系统的算法，内存的分配和回收是怎么进行的呢？

首先，一开始肯定是整片空的内存空间，进程 A 请求 100KB，因为 64<100<128，即 2^6^<100<2^7^，所以寻找是否有 2^7^=128 的空闲分区，当然是没有的（目前只有 512KB)，所以寻找是否有 2^8^=256 的空闲分区，也没有，所以寻找是否有 2^9^=512 的空闲分区，找到了，此时就把 512KB 一分为二：

一半的 256KB 加入到对应的空闲分区链表，一半的 256KB 用于分配，对这一半继续一分为二：

一半的 128KB 加入到对应的空闲分区链表，一半的 128KB 用于分配，这一半对进程 A 来说足够了，于是占用它：

进程 B 请求 50KB，因为 32<50<64，即 2^5^<100<2^6^，所以寻找是否有 2^6^=64 的空闲分区，没有，所以寻找是否有 2^7^=128，找到了，此时就把 128KB 一分为二：

一半的 64KB 加入到对应的空闲分区链表，一半的 64KB 用于分配，这一半对进程 B 来说足够了，于是占用它：

进程 C 请求 100KB，因为 64<100<128，即 2^6^<100<2^7^，所以寻找是否有 2^7^=128 的空闲分区，没有，所以寻找是否有 2^8^=256 的空闲分区，找到了，此时就把 256KB 一分为二：

一半的 128KB 加入到对应的空闲分区链表，一半的 128KB 用于分配，这一半对进程 C 来说足够了，于是占用它：

进程 A 释放 100KB：

进程 D 请求 20KB，因为 16<20<32，即 2^4^<100<2^5^，所以寻找是否有 2^5^=32 的空闲分区，没有，所以寻找是否有 2^6^=64 的空闲分区，找到了，此时就把 64KB 一分为二：

一半的 32KB 加入到对应的空闲分区链表，一半的 32KB 用于分配，这一半对进程 D 来说足够了，于是占用它：

进程 D 释放 20KB，回收 32KB，由于事先已经有一个 32KB，所以此时两个互为伙伴的 32KB 进行合并：

进程 B 释放 50KB，回收 64KB，由于事先已经有一个 64KB，所以此时两个互为伙伴的 64KB 进行合并，形成 128KB，由于事先已经有一个 128KB，所以此时两个互为伙伴的 128KB 进行合并，形成 256KB：

计算伙伴地址的方法：对于给定的内存块，若它的大小为 2^k^，起始地址为 x，

• 如果 x/2^k 为奇数，则伙伴地址为 x - 2^k
• 如果 x/2^k 为偶数，则伙伴地址为 x + 2^k

哈希算法

快速适应和伙伴系统都是将空闲分区按照大小进行分类，并为每一类建立一个独立的空闲分区链表，再用一个总的索引表进行记录。不过，如果分类过多，则索引表的表项也会过多，这时候搜索索引表的时间开销就会比较大。

因此，哈希算法选择建立一张哈希表（而不是普通的索引表），这张哈希表以空闲分区大小作为关键字，每次需要进行分配的时候，会根据所需空闲分区的大小，通过哈希函数快速计算得到该空闲分区在表中的位置，从而得到对应的空闲分区链表。

动态可重定位分区分配

动态可重定位分区分配算法与动态分区分配算法基本一致，仅仅增加了紧凑功能。

连续分配为某个进程分配的必须是一块连续的空间，若多个空闲分区不是相邻的，即便它们的大小总和已经满足进程的需求，也无法进行分配。采用紧凑技术解决这个问题。紧凑技术把内存中各个进程进行移动并使其相邻，从而化零为整，带来了更大的空闲分区：

在这里会发现，每次发生紧凑，各个程序和数据的物理地址就要发生改变。

• 假定我们先前采用的是静态重定位装入方式，那么在模块装入内存的时候，就已经把逻辑地址转换为物理地址了，每次发生紧凑，都要在程序上重新修改一次物理地址。
• 如果我们采用动态重定位装入方式，各个程序和数据的地址全部都是逻辑地址，当程序需要访问地址时，无需修改程序上的地址，只需要将该逻辑地址与当前重定位寄存器里存放的物理起始地址进行相加。每次发生紧凑时，也只需要用紧凑后的新起始地址去替换重定位寄存器里的旧起始地址。

非连续内存分配

固定分区分配容易产生内部碎片，动态分区分配容易产生外部碎片（虽然可以用紧凑技术解决，但是有一定的成本），都不是理想的解决方案。

基本分页存储管理

基本思路

在连续分配中，一个进程不可被分割，只能整体放入一块连续的内存空间中；但在基本分页存储管理中，允许把一个进程按照固定大小 X 分割为多个部分，同时把内存也按照固定大小 X 分割为多个部分，并把前者对应地放到后者中（不要求连续存放）。通常来说，一个进程的最后一部分会小于 X，这部分若放到内存的某个 X 空间中，仍然会产生碎片（这种碎片称为页内碎片）。

页面、页框

• 页框 (Page Frame)：具体来说，把内存分割为多个固定大小 X 的部分，这些部分就叫做页框 / 页帧 / 物理块 / 内存块，每个页框会有一个数字编号，第一个页框就从 0 开始

• 页面 (Page)：同样，进程被分割为多个固定大小 X 的部分，这些部分就叫做页面 / 页，每个页面会有一个数字编号，第一个页面就从 0 开始

若页面太小，虽然可使页内碎片减小、提高内存利用率，但是会使页表过长、降低页面换进换出的效率；若页面太大，则相反。因此页面的大小应是 2 的整数幂，通常为 1KB~8KB。

系统以页框为单位为各个进程分配内存空间，一个页面就对应一个页框，它具体放到哪个页框是随意的，无需顾虑是否连续和先后顺序。

地址转换的思路

假设我们采用动态重定位方式进行模块装入，程序中是逻辑地址，但在程序执行到需要访问地址的时候，需要进行逻辑地址到物理地址的转换。

十进制地址

左边进程按照 50B 的大小分为 4 个页面，右边内存按照 50B 的大小分为若干个页框：

在程序执行到指令 1 的时候，需要访问地址 80，这是一个逻辑地址，需要转换成对应的物理地址。转换步骤如下：

• 计算逻辑地址的页号
• 根据页号找到页号对应页面在内存中的起始地址
• 计算逻辑地址在当前页面内的偏移量（页内偏移量）
• 物理地址 = 起始地址 + 页内偏移量

从左图可以看出，逻辑地址 80 在 1 号页面内，而 1 号页面对应的是右图中的红色页框，起始地址为 450；逻辑地址 80 在 1 号页面内的偏移量为 30；所以物理地址 = 450 + 30 = 480

也可以用计算的方法，在已知逻辑地址的情况下：

• 页号 = 逻辑地址 / 页面大小，即 80/50 = 1（取整数部分）
• 页内偏移量 = 逻辑地址 % 页面大小，即 80%50 = 30

二进制地址

地址实际上是用 32 位二进制数表示的。这时候计算页号 P 和页内偏移量 W 实际上更加简单，因为地址本身已经包含了这两者的信息。

以页面 / 页框大小 4KB 为例，用地址的前 20 位（红色部分，也叫高 20 位）表示页号 P，用地址的后 12 位（黑色部分，也叫低 12 位）表示页内偏移量 W。页内偏移量的位数可以表明每个页面的大小，即 2^12^ = 4KB。0 号页、1 号页、2 号页的表示如下：

若页面 / 页框大小为 1KB，也即 2^10^B = 1024B，那么地址的前 22 位表示页号，剩余的 10 位表示页内偏移量：

例题

页表

根据地址，就已经可以知道页号和页内偏移量，还有一个工作是根据页号找到对应页面在内存中的物理地址。

每一个进程都有一张页表来记录页面号（页号）与页框号（块号）的映射关系，可以根据页号找到内存中对应页框的编号。其中页号是隐含的，相当于从 0 开始的下标，不占存储空间，页表实际只保存了块号。

根据地址知道页号后，从页表中找出页号对应的块号，再用块号 * 页框大小，即可算出块的起始地址。用起始地址 + 偏移量，即可算出物理地址。

地址变换机构

基本地址变换机构

上述的地址转换是通过基本地址变换机构这个硬件实现的，它借助页表将逻辑地址转换为物理地址。转换过程如下：

在程序未执行的时候，PCB 中存放程序对应页表的初始地址 F 以及页表长度 M（页表项个数）。程序一旦开始执行，F 和 M 会被送到页表寄存器中。在需要访问地址的时候，基本地址变换机构开始运行：

• 首先将逻辑地址 A 拆分为页号和页内偏移量两个部分，然后将页号与页表寄存器中的页表长度作比较。页表长度即页表项个数，即页面个数，因此页号是不能大于等于（不能等于，因为页号从 0 开始计算）页表长度的，如果页号越界就会发生越界中断。
• 由于页表中每个页表项的大小是一样的（假设为 size），且已经知道了页表在内存中连续分配的起始地址（假设为 X），所以页号 P 对应的页表项的存放地址等于 X + P*size，在这个地址保存着页号对应的块号
• 将块号与偏移量的二进制数拼接，就得到了物理地址，得以访问目标

例子中涉及到的都是二进制数，要计算物理地址，只需要将块号二进制数与偏移量二进制数拼接即可。如果例子给出的是十进制数，则应用 块起始地址 + 页内偏移量 进行相加，计算结果再转化为二进制数。

例题 1

若给定的是十进制：

页面大小 1KB，块号 2，偏移量 1023。

块起始地址等于 2 * 1KB = 2 * 1024B = 2048B，又偏移量 1023，所以物理地址等于 2048 + 1023 = 3071，转化为 32 位二进制数，就是 0000000000000000000010,1111111111

若给定的是二进制：

页面大小 1KB，块号 2，偏移量 1111111111。

块号 2 转化为 22 位二进制数就是 0000000000000000000010，与偏移量拼接，就得到 0000000000000000000010,1111111111，与十进制的结果是一样的。

具有快表的地址变换机构

在前面的基本地址变换机构中，存在两个问题：

• 每次存取数据都需要访问内存两次：第一次访问内存中的页表，找到块号，并将块号与偏移量拼接得到物理地址；第二次根据物理地址访问内存中存放的数据。第二次访存肯定是不能避免的，但是第一次访存可以想办法避免
• 若多条指令涉及到的逻辑地址的页号都相同，就都必须经历第一次访存，找到该页号对应的块号

这两个问题可以通过引入快表来解决。

快表（联想寄存器）是一种访问速度比内存快很多的高速缓冲存储器，用以存放访问过的页表项的副本，从而加快地址转换的过程。引入快表后，地址转换大概率不需要经历第一次访存，而是直接从快表中拿到需要的页表项。于是内存中原本的页表被称为慢表。

此时的地址变换机构的运行过程和之前还是差不多的，只是多了一个快表的处理过程：

在程序未执行的时候，PCB 中存放程序对应页表的初始地址 F 以及页表长度 M（页表项个数）。程序一旦开始执行，F 和 M 会被送到页表寄存器中。在需要访问地址的时候，地址变换机构开始运行：

• 首先将地址拆分为页号和页内偏移量两个部分，然后将页号与页表寄存器中的页表长度作比较。若越界，则发生越界中断。
• 该页号被送往快表，并与其中的页表项比较，寻找是否有匹配的页号。因为这里我们是第一次查询，所以是没有的，即未命中，页号被送往慢表。
• 第一次访存，在慢表中找到页号对应的页表项的地址，意味着找到了页号对应的块号
• 将该页表项拷贝一份副本放到快表中
• 将块号与偏移量的二进制数拼接，就得到了物理地址，得以访问目标

我们需要继续访问某个地址，并且与上次访问的地址的页号一样：

• 首先将地址拆分为页号和页内偏移量两个部分，然后将页号与页表寄存器中的页表长度作比较。若越界，则发生越界中断。
• 该页号被送往快表，并与其中的页表项比较，寻找是否有匹配的页号。因为快表中已经存放了一份页表项的副本，所以找到了匹配的页号，即命中。
• 从快表中读出该页号对应的块号，并与偏移量拼接，就得到了物理地址，得以访问目标

例题 2

某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。假设访问一次快表耗时 1us，访问一次内存耗时 100us，快表的命中率为 90%。

• 若未引入快表，则访问一个逻辑地址耗时 100 + 100 = 200us

• 若引入快表，则访问一个逻辑地址耗时 (1+100) * 0.9 + (1+100+100) * 0.1 = 111 us

• 若引入快表，且该系统支持同时查询快表和慢表，则访问一个逻辑地址耗时 (1+100) * 0.9 + (100+100) * 0.1 = 110.9us

页表项的大小

假设某系统物理内存大小为 4GB，页面大小为 4KB，则每个页表项至少应该为多少字节？

一条页表项的大小取决于块号的位数。的 4GB=2^32^B， 4KB=2^12^B，因此 4GB 的内存总共会被分为 2^32^/2^12^ = 2^20^ 个内存块，因此内存块号的范围应该是 0～2^20^-1。因此对于单个页表项，它要用一个 20 位二进制数才能表示这样的一个内存块号，而一个字节 8 位，所以至少要 3B 才可以表示这样的一个内存块号。

但是一个页表项用 3 个字节其实会出现一些问题。类似于进程被拆分为多个页面存储在内存中一样，页表也是被拆分为多个页表项存储在内存中的。假设页面 / 页框大小为 4KB，也即 4096B，由于一个页表项 3B，所以一个页框至多可以放 4096/3=1365 个页表项，并且这个页框剩余 1B 的空间。由于 1B 不足以再存放一个页表项，所以第 1366 个页表项（1365 号页表项）只能放在下一个页框中了。

这就会导致，前面 1365 个页表项的地址依然可以采用 X + 3*P 的方式计算，但是第 1366 个页表项，它的地址却应该是 X + 3*P + 1，也就是说，我们无法以一个通用的式子去计算页表项的存放地址。

因此，一个页表项的大小通常应选取 2 的整数幂。如果页表项大小为 4B，那么一个页框就刚好可以放 4096/4=1024 个页表项，余下的页表项可以依次放在下一个页框中。这样，涉及到页表项地址的计算都可以用通用的式子 X + 4*P，就无需考虑由于页框无法得到完全利用而带来的查询麻烦的问题了。当然，为了这个式子能够通用，页表通常也应该连续地存放在内存块中，中间不出现断节。

Q: 首先，在 页表项的大小 中，按照您的讲述，第 1366 个页表项的地址应为 X + 3*(P+1)。另外，我对 “一个页表项的大小应同样选取 2 的整数幂” 的说法抱有疑问，因为 “一个页框能否在没有剩余空间的情况下装入足够多的页表项” 并不会影响到 “利用页号在页表中找到对应的块号”。即使页表项大小为 3B 时，第 1366 个页表项会被装入下一个页框，但是当页表项大小为 4B 时，第 4097 个页表项也同样会被装入下一个页框，不是吗？请问您是怎么理解的呢？

A: 页表项的地址≠块号，页表项的存放地址的数据内容才是块号。同样的，块号≠内存块的物理地址，块号是内存块在内存中组织顺序的索引，块号 * 页框大小才等于内存块的起始物理地址。

问题不在于 “如何从已经找到地址的页表项中读取块号”，而在于 “如何根据隐含的页号找到页表项的存放地址”。页号是隐含的，页表中并没有储存页号，我们无法根据页号直接读取到页表项存储的块号，必须先根据 X + P*size 这个式子来确定页表项的存放地址。页表项大小为 3B 时，第 1365 个页表项和第 1366 个页表项之间间隔了未分配的 1B，先前 X + 3*P 的寻址规律就被打破了。X + 3*P + 1 中的 +1 是前一个页框剩余的 1B，而不是 “下一个页框” 的意思。

两级页表

单级页表占用过大的连续内存空间的问题

假设页面 / 页框大小 4KB，页表项大小 4B，一个页表占用的空间：

• 计算页表一共有多少个页表项：4KB = 2^12^B，所以 32 位逻辑地址中，后 12 位表示偏移量，前 20 位表示页号。总共有 2^20^ 个页面，也就是有 2^20^ 个页表项需要存放。
• 计算一个页框可以放多少个页表项：一个页框 4KB，一个页表项 4B，所以一个页框可以放 4096/4 = 1024 个页表项
• 计算存放所有页表项需要多少个页框：2^20^/1024 = 1024

需要 1024 个页框才能放下整个页表，而且为了以通用的式子计算页表项地址，页表必须是连续存放的，这违背了分页存储的初衷。

引入两级页表

就像进程拆分为多个页面一样，页表也可以进行拆分：将长的单级页表分为多个子页表，再将每每个子页表离散地存放到各个内存块中。在之前的例子中，一个页框可以放 1024 个页表项，那么每 1024 个页表项就拆分出一个子页表，因为页表一共有 2^20^ 个页表项，所以一共可以拆分出 1024 个子页表，这些子页表再各自存放到内存块中。

于是，我们需要一张页目录表（一级页表 / 顶层页表 / 外层页表）来记录页目录表和子页表（二级页表）之间的映射关系，如下图：

同时，之前的逻辑地址的含义也发生了改变。在单级页表中，前 20 位表示页号；而在两级页表中，前 10 位表示一级页号（一级页表的页号），紧跟着的 10 位表示二级页号（二级页表的页号）。这么划分之后，一级页号共有 2^10^=1024 种可能的取值，即页目录表的 1024 个页表项；二级页号也有 2^10^=1024 种可能的取值，即子页表的 1024 个页表项。

在需要进行地址转换时：

• 首先将逻辑地址分为三个部分：一级页号、二级页号、页内偏移量
• 然后从 PCB 中读出页目录表的初始地址，结合一级页号以及每个页表项的大小，找到一级页号对应页表项的地址，即读取到了一级页号对应的块号
• 根据块号到内存中找到对应的二级页表
• 在二级页表中，根据二级页号找到对应的块号
• 块号 * 页框大小 + 偏移量得到物理地址

上面的过程也可以直接看这幅图理解：

单级页表常驻内存的问题

执行程序时，往往只需要访问特定的几个页面，但整个单级页表是常驻在内存中的。[虚拟存储技术](# 第五章 虚拟存储器) 可以在需要访问页面的时候才把对应的页表项调入内存。

多级页表

某系统按字节编址，采用 40 位逻辑地址，页面大小为 4KB，页表项大小为 4B，假设采用纯页式存储，则要采用多少级页表？页内偏移量为多少位？

4KB = 4*1024B = 2^12^B，根据之前讲过的，页面偏移量应该是 12 位。40 - 12 = 28，所以前面 28 位用来表示页号。

因为采用多级页表后，各级页表的大小不能超过一个页面，而一个页面最多只能放 1024 个页表项，所以应该限制页表最多只能包含 1024 个页表项（否则就放不下多余的页表项，导致页表超过一个页面），即逻辑地址中的 10 位二进制数。

在逻辑地址的前 28 位中，可以选择 10 位用于表示某一级的页号（这一级的页表假设页表项可能有 1024 个这么多），再用 10 位表示某一级的页号（这一级的页表假设页表项可能有 1024 个这么多），再用剩下的 8 位表示某一级的页号（这一级的页表假设页表项远远少于 1024 个）。

也可以考虑前面 8 位作为一级页号，紧接着的 10 位作为二级页号，再紧接着的 10 位作为三级页号，这样刚好就用完了逻辑地址前 28 位。所以题目需要采用三级页表。

那如果这里不采用三级页表，强行使用二级页表，则必定有某一级的页号位数超过了 10，说明页表的页表项个数超过了 2^10^=1024 个，很显然就会导致一个页框放不下这一级的页表，需要跨页，这与规定 “采用多级页表后，各级页表的大小不能超过一个页面” 是相悖的。

习题

1. 若系统采用两级分页存储方式，物理内存 64MB，页面大小 1KB，页表项大小 2B，则顶级页表有多少个页表项？

这里我们可以参考之前求页表项大小的思路。物理内存 64MB = 2^26^B，表示这么多内存需要 26 位逻辑地址。这 26 位中，一部分表示一级页号，一部分表示二级页号，剩下的表示页内偏移量。

因为页面大小 1KB = 2^10^B，所以页内偏移量需要 10 位来表示，余下 16 位供一、二级页号使用。一个页面大小 2^10^B，一个页表项 2B，所以一个页框可以最多可以放 2^10^/2 = 2^9^ 个页表项，又由于各级页表不能超过一个页面，所以各级页表都不能超过 2^9^ 个页表项。在余下的 16 位中，用 9 位表示二级页表的页号（此时该页表的页表项个数取满）。剩下的 7 位表示一级页表的页号，可以包含 2^7^ = 128 个页表项。

2. 若系统采用分页存储方式，物理内存 256MB，页面大小 1KB，页表如下：

页号 0，1，2，3，4，5，6，7，8，9，10 分别对应块号 15，16，20，28，29，30，31，32，36，38，39

则逻辑地址 1A68（16 进制）对应的物理地址是多少？

为了方便计算，我们先统一用十进制计算，得到十进制的物理地址后再转换为十六进制。

1A68 按权展开转化为对应的十进制数字是 6760，对于逻辑地址 6760，可以计算它的页号和页内偏移量：

• 页号 = 6760/1024 = 6（取整数部分）
• 页内偏移量 = 6760%1024 = 616

根据页号 6 找到块号 31，根据块号 31 计算块初始地址为 31*1024 = 31744，偏移量和初始地址相加得到的物理地址为 31744+616 = 32360。32360 是十进制的物理地址，短除法转化为对应的十六进制物理地址就是 7E68。

若统一使用二进制计算：

256MB = 2^28^B 逻辑地址共 28 位

1A68 转换为二进制：0001 1010 0110 1000

页内偏移量 10 位

28-10=18 页号位数

补齐位数 0000 0000 0000 0001 1010 0110 1000

即 000000000000000110,1001101000

页号为 6，起始地址 31*1024=31744

出题者想让你用十进制做，因为给的是十进制的页表

3. 若系统采用分页存储方式，物理内存 1MB，共有 32 个页面，一个页面 2KB，则逻辑地址一共多少位？

因为物理内存 1MB = 2^20^B，所以逻辑地址 20 位。

根据上面的经验，我们可能会这么做，但是这是错误的做法。上面的习题都没有告诉我们程序具体被划分为多少个页面，所以我们认为物理地址需要多少位，逻辑地址也需要多少位。但是这道题已经告诉了我们程序具体被划分为 32 个页面 —— 显然，仅仅 32 个页面是不需要 20 这么多位的逻辑地址的。

逻辑地址包括两部分，页号和页内偏移量：

• 考虑页内偏移量位数。由于一个页面 2KB，也即 2^11^B，所以页内偏移量占 11 位（注意这点是不变的）
• 考虑页号位数。由于页面仅仅被划分为 32 = 2^5^ 个，所以页号只需要 5 位

11 + 5 = 16，所以逻辑地址一共 16 位。

当题目明确给出分页个数的时候，按照页号位数 + 偏移量位数计算逻辑地址总位数。

基本分段存储管理

基本思路

在基本分页存储管理中，我们将程序分为多个大小相等的物理单元（页面）。而在基本分段存储管理中，我们倾向于从逻辑功能的角度去考虑，将程序分为多个逻辑功能段，每个段都有自己的段名，并且都从 0 开始编址。分配内存时以段为单位进行分配，段内所占内存空间是连续的，但是各个段之间可以不相邻，如下图：

编写程序时可以将程序按照逻辑功能模块进行划分，会更加方便，可读性会更高，比如：

1
2

LOAD 1，[D]|<A>
STORE 1，[X]|<B>

分别表示：将分段 D 中 A 单元内的值读入寄存器 1，以及将寄存器 1 的值存入分段 X 的 B 单元中。这里的分段 D 和 X 都是段名，程序员在编程的时候只需要使用段名，编译时段名会转化为对应的段号。同理，A、B 单元编译时也会转化为寄存器地址。

逻辑地址

分段存储管理中逻辑地址的含义与分页存储管理不同。假设仍然是用 32 位二进制数表示逻辑地址，地址的前 16 位表示段号，后 16 位表示段内偏移量：

• 段号是 16 位二进制数，有 2^16^ 种取值，即每个进程最多可以被分为 2^16^ 个段
• 段内偏移量也是 16 位二进制数，在一个段内，段内地址可能有 2^16^ 种取值，所以一个段的最大长度为 2^16^

段表

类似的，我们需要用段表来记录某个编号段与实际物理存放位置之间的映射关系。在分段存储管理中，程序被分为大小不等的多个段，且不连续，没法像之前一样只凭借块号来推导块的初始地址。为了准确地找出段存放在内存中的位置，我们要将段号、段长、基址 这三者作为段表的三列。这样，根据段号可以在段表中找到对应段在内存中的基址（即起始地址，不是块号），再结合段长，可以知道这个段具体占用了哪里的空间。

如下图所示：

段表项的大小

每个段表项由段号、段长、基址构成，我们可以依次考虑每一列可能占用的空间（假设物理内存 4GB，按字节寻址）：

• 基址：因为物理内存 4GB，也就是 2^32^B，那么内存中的地址最多可能取到 2^32^ 种值。为了让基址列足够表示这些值，基址列占用了 32 位。
• 段长：前面讲过，在逻辑地址中，段号和段内偏移量都是 16 位，所以段内偏移量最多可能取到 2^16^ 种值，为了让段长列足够表示这些值，段长列占用了 16 位
• 段号：和页表一样，在段表中同样隐含段号，因为段表也是连续的，我们只需要知道段表的起始地址和每个段表项的大小就能定位一个段表项的地址，而无需去维护一个从段号到段表项的映射。

因此，每个段表项占用了 16+32=48 位，一个字节 8 位，占用了 6 个字节， 即 6B。

地址转换

转换过程我们可以直接看下图理解：

可以联系分页存储的地址转换过程。在需要将逻辑地址转换为物理地址的时候：

• 首先将逻辑地址分为段号和段内偏移量两个部分，段表寄存器中的段表长度保存了程序总共被分为了多少段，因此段号不应该超过段表长度，若超过则发生越界中断。
• 根据段号、段表初始地址和段表项的大小，找到段号对应的段表项。比较段表项中的段长 C 和逻辑地址中的段内偏移量 W，若 W >= C 则发生越界中断（此处比分页存储多一次越界判断，因为页表的页框大小固定，且受页内偏移量位数限制不会越界，而段长可变）
• 在段表项中找到段号对应的基址，将该基址与段内偏移量拼接，得到物理地址，得以访问目标

分页和分段的对比

划分的角度和维度

信息的共享和保护

在分段存储方式中，更容易实现信息共享和保护：

可重入代码 (Reentry code) 也叫纯代码 (Pure code) 是一种允许多个进程同时访问的代码。为了使各进程所执行的代码完全相同，故不允许任何进程对其进行修改。程序在运行过程中可以被打断，并由开始处再次执行，并且在合理的范围内（多次重入，而不造成堆栈溢出等其他问题），程序可以在被打断处继续执行，且执行结果不受影响。

在分页存储方式中，则很难：

访存次数

两者的访存次数是一样的：

• 若不引入快表，两者的第一次访存都是访问内存中的页 / 段表，第二次是访问内存中的目标。
• 若引入快表，则两者的第一次访存有可能因为命中而省去。

段页式存储管理

基本思路

• 采用分页存储管理，内存利用率高，不会产生外部碎片，仅会产生少量内部碎片；但是不方便按照逻辑模块实现信息的共享和保护
• 采用分段存储管理，可以按照逻辑模块实现信息的共享和保护，但是若逻辑过多则会导致段过长，另外，这种方式也会产生外部碎片

所以结合二者之长，出现了段页式存储管理方式。

如下图，段页存储管理会首先将进程按照逻辑模块划分为多个段，针对每个段再划分为多个页；同时也把内存划分为多个页框。分配内存的时候，一个页面就对应了一个页框。

逻辑地址

在分段存储管理中，给出一个逻辑地址，可以划分为段号和段内地址两个部分；而在段页存储管理中，段内地址还要继续细分成页号和页内偏移量两个部分。所以逻辑地址由段号、页号和页内偏移量三个部分组成。

段号的位数仍然决定了一个进程可以被划分为多少个段，而页号的位数则决定了一个段可以被划分为多少个页面，页内偏移量则决定了一个页面可以有多大，即页面 / 页框大小。

和分段存储管理一样，段页存储管理的地址结构也是二维的。

段表

段页存储管理中的段表不同于分段存储管理中的段表。程序被划分为多个段，每个段都会再被划分为多个页面，因此每一个段都维护着属于自己的一张页表。段表需要记录的是段号与段号对应段的页表之间的映射关系，包括段号、页表长度和存放页表的块号（块号 * 页框大小 = 页表所在块的起始地址）。段号是隐含的。

地址转换

段页式存储的地址转换机构结合了分页存储和分段存储的方式，在需要将逻辑地址转换为物理地址的时候：

• 首先将逻辑地址分为段号、页号和页内偏移量三个部分，段表寄存器中的段表长度仍代表程序总共被分为多少个段，因此段号不应该超过段表长度，若超过则越界中断（同段式存储第一次越界检查）
• 根据段号、段表初始地址以及段表项的大小，找到段号对应的段表项。可以从这个段表项读取到该段号对应的页表的位置和大小。这里同样要比较段表项中的页表长度和逻辑地址中的页号 P，若页号大于等于页表长度则越界中断（同页式存储唯一一次越界检查，不同于段式存储第二次越界检查）
• 找到了段表项就是找到了该段的页表所在块的块号。根据块号，在内存中找到这个块，再从块中找到页表
• 根据逻辑地址中的页号，在页表中找到页号对应的块号，将块号和逻辑地址中的页内偏移量拼接，得到物理地址，得以访问目标

访存次数

不采用快表时，段页式存储管理需要经历三次访存：第一次访存，访问内存中的段表，找到段表中记录的页表信息；第二次访存，访问内存中的页表，找到目标所在的块；第三次访存，访问内存中的目标。

如果采用快表，会利用段号和页号去寄存器中检索，若命中，则无需经历第一次和第二次访存，可以直接拿到块号并和偏移量进行拼接，得到物理地址。同样只需要一次访存。

第五章 虚拟存储器

期末考试备考

选择题 15 分

判断题 10 分

简答题 30 分

综合应用题 45 分