『操作系统』期末复习

本文页码均指课件页码

操作系统概述

一、核心主线

操作系统是位于硬件之上、其他软件之下的系统软件，它负责管理计算机软硬件资源，并为用户和应用程序提供方便、安全、高效的服务。

也就是说，操作系统既是：

资源管理者：管理 CPU、内存、设备、文件等资源。
用户接口：提供命令行、图形界面、系统调用等使用方式。
虚拟机：把复杂硬件包装成更易用的逻辑资源，比如虚拟 CPU、虚拟内存、虚拟设备。
控制程序：通过中断、调度、保护机制控制程序运行。

二、操作系统的概念

1. 操作系统的地位

课件中强调：操作系统位于 硬件层 HAL 之上，位于 其他系统软件和应用软件之下。

可以理解成：

应用软件
系统软件 / 系统库
操作系统
硬件 / HAL

应用程序通常不会直接操作硬件，而是通过 库函数 或 系统调用 请求操作系统完成底层工作。

例如：

printf("Hello");

表面上是 C 语言函数，实际上最终要通过操作系统完成显示设备或终端输出。

2. 操作系统的作用

主要有两类：

第一，管理资源：

第二，提供服务接口：

包括 API、GUI、命令行、作业控制语言 JCL 等。

3. 操作系统定义

课件中的定义可以背下来：

操作系统是位于硬件层之上、所有其他软件层之下的系统软件，通过它管理系统中各种软硬件资源，使它们被充分利用，并方便用户使用计算机系统。

考试中如果问“什么是操作系统”，答这个定义基本够用。

三、操作系统的发展历史

这一部分容易考“发展阶段”和“各阶段特点”。

1. 手工操作阶段

时间大约是 20 世纪 40 年代，无操作系统。

特点：

程序员手工操作机器；
使用纸带、卡片、开关、接线板；
CPU 经常等待人操作，效率极低；
资源被一个作业独占。

重点理解：机器越来越快后，人工操作时间反而成了主要瓶颈。

2. 批处理阶段

为了解决人工干预太多的问题，出现批处理。

分为：

联机批处理：作业从读卡机进入计算机，按批处理执行。优点是减少人工干预，缺点是 I/O 慢，主机等待时间长。

脱机批处理：使用卫星机完成输入输出转换，主机专心计算。优点是减少主机等待 I/O，缺点是需要人工搬磁带和额外设备。

3. 执行系统阶段

出现了 通道 和 中断 技术。

通道可以理解为专门负责 I/O 的处理机，它接受 CPU 委托执行 I/O 操作。这样 CPU 和 I/O 可以并行工作。

这一阶段出现了 SPOOLing 假脱机技术。

4. 多道批处理系统

这是操作系统走向成熟的重要标志。

核心思想：

内存中同时放入多个作业，当一个作业等待 I/O 时，CPU 可以去执行另一个作业。

优点：

提高 CPU 利用率；
提高系统吞吐量；
适合大型科学计算任务。

但它也带来了一系列新问题：

互斥、同步、通信、死锁、饥饿等。

这些正是后面几章重点内容。

5. 分时系统

分时系统面向交互式用户。

特点：

多用户通过终端连接主机；
系统轮流给每个用户分配 CPU 时间片；
用户感觉自己独占一台机器。

典型系统：CTSS、Multics、UNIX。

6. 实时系统

实时系统强调 及时响应 和 高可靠性。

应用场景：

工业控制、军事控制、医疗控制、航班订票、联机检索等。

重点：实时系统不是单纯追求“快”，而是要求 在规定时间内完成响应。

7. 通用操作系统

通用操作系统把批处理、分时、实时等功能结合起来。

常见模式：

前台分时 + 后台批处理；
前台实时 + 后台批处理。

四、操作系统的四大特性

这部分常考简答题。

1. 并发性

多个程序在宏观上同时向前推进。

注意区分：

单 CPU 上可以有并发，但不能真正并行执行多个程序。

2. 共享性

多个程序共同使用系统资源。

例如：

多个程序共享 CPU；
多个进程共享内存中的某些区域；
多个用户共享打印机；
多个进程共享文件。

共享必须由操作系统协调，否则会产生冲突。

3. 异步性

程序推进速度不可预知。

原因是：

多个程序交替运行；
中断随机发生；
调度时机不确定。

所以程序执行顺序并不完全由程序员控制，而受中断、调度、资源状态影响。

4. 虚拟性

通过某种技术把一个物理实体变成多个逻辑实体。

例子：

这一点非常重要，后面虚拟存储、虚拟设备都会继续展开。

五、操作系统的主要类型

1. 多道批处理系统

关键词：多道、成批、吞吐量、资源利用率。

适合非交互、大批量计算任务。

重点概念：SPOOLing。

SPOOLing 又叫假脱机技术或排队转储技术，由输入井、输出井和常驻 I/O 进程组成。它可以把独占设备改造成共享设备，实现虚拟设备功能。

2. 分时操作系统

关键词：多路性、交互性、独占性。

多路性：一个主机连接多个终端。
交互性：用户可以和系统对话。
独占性：每个用户感觉自己独占一台虚拟机。

3. 实时操作系统

关键词：响应及时、可靠性高。

实时控制系统中，课件用 t2 - t1 表示响应时间。

4. 网络操作系统

网络操作系统用于实现网络通信和网络资源管理。

目标：

相互通信；
资源共享；
提供网络服务，如数据库服务、FTP、邮件、Telnet 等。

注意：网络操作系统通常没有完全透明的统一视图。

5. 分布式操作系统

分布式操作系统强调多个计算机在统一操作系统管理下协同工作。

特点：

统一操作系统；
资源进一步共享；
可靠性高；
透明性强。

目标：

资源共享、负载均衡、计算加速。

常见技术：作业迁移、进程迁移。

6. 多处理机操作系统

面向具有公共内存的多 CPU 系统。

重点概念：

SMP，对称多处理机系统；
多个 CPU 没有主从关系；
进程和 CPU 是多对多关系。

新问题：

调度问题；
并发控制问题。

7. 嵌入式操作系统

应用于掌上设备、车载系统、通信设备、信息家电等。

特点：

微内核结构；
核心小；
可裁剪性好；
可移植性好；
可扩展性好；
可靠性高，但效率可能较低。

六、操作系统运行环境

这一节讲“操作系统为什么能控制程序”。

1. 定时装置

分为：

绝对时钟：记录实际时间，一般不发中断。
间隔时钟：定期发中断，是实现多道程序的重要基础。

考试重点：

间隔时钟保证操作系统能定期获得 CPU 控制权。

如果没有时钟中断，一个死循环程序可能一直占用 CPU。

2. 堆和栈

每个运行程序通常有：

一个堆；
一个用户栈；
一个系统栈。

注意：

用户栈属于用户空间；
系统栈属于操作系统空间；
进程切换时，系统栈也要切换。

3. 寄存器

程序切换时，需要保存和恢复寄存器内容。

重要寄存器包括：

PSW 程序状态字；
PC 指令计数器；
SP 栈指针；
通用寄存器；
浮点寄存器；
地址映射寄存器。

4. 特权指令与非特权指令

特权指令：只能在系统态执行，会影响系统状态。
例如：开关中断、设置 PSW、停机、I/O 指令等。

非特权指令：用户态和系统态都可以执行。
例如：取数、四则运算等。

5. 处理机状态

有两种基本状态：

状态转换：

系统态 → 用户态：通过设置 PSW 等特权指令。
用户态 → 系统态：通过中断、trap、系统调用。

6. 地址映射与存储保护

地址映射：

逻辑地址 → 物理地址

逻辑地址是程序中产生的地址；
物理地址是真实内存地址。

存储保护用于防止：

应用程序侵犯操作系统空间；
应用程序侵犯其他用户空间；
非法访问共享区域。

主要检查：

越界检查；
越权检查。

7. 中断装置

中断是操作系统获得控制权的关键机制。

发生中断时，大致过程是：

保存当前 PSW 和 PC；
根据中断向量找到处理程序入口；
转入操作系统执行中断处理程序。

8. 通道与 DMA

二者都能实现 I/O 设备和内存之间的数据直传。

区别：

七、操作系统的界面形式

1. 命令行接口

例如 UNIX shell：

rm -i *.c

其中：

rm 是命令名；
-i 是选项；
*.c 是参数。

Shell 的优点：

缩小操作系统核心；
不同用户可以选择不同界面；
Shell 本身通常是用户态进程。

2. GUI 图形用户界面

由窗口、图标、菜单、按钮、鼠标等组成。

本质上仍然是交互式接口，只是从命令输入变成图形操作。

3. 作业控制语言 JCL

主要用于批处理系统。

用户通过 JCL 告诉操作系统：

需要什么资源；
如何控制作业执行；
作业如何输入输出。

4. 系统调用 OS API

系统调用是应用程序请求操作系统内核服务的方式。

常见系统调用类型：

文件相关；
进程相关；
进程通信相关；
资源管理相关。

系统调用过程可以概括为：

用户程序执行系统调用；
通过陷入指令进入内核；
保存现场；
查系统调用入口表；
执行对应内核服务；
返回用户程序。

八、操作系统运行机理

课件中用“程序 1、程序 2、中断、程序切换”说明 OS 的运行机制。

核心过程：

程序正常运行；
发生中断；
CPU 转入操作系统；
操作系统保存当前程序现场；
选择另一个程序运行；
恢复新程序现场；
返回用户态继续执行。

这就是进程切换、调度、中断机制的基础。

九、研究操作系统的三种观点

1. 进程观点

把操作系统看成：

若干可以独立运行的程序；
一个协调这些程序的核心。

重点问题：

互斥；
同步；
通信；
死锁；
饥饿。

2. 资源管理观点

操作系统是资源管理者。

它要做三件事：

描述资源状态；
决定资源分配策略；
提供申请和释放资源的机制。

3. 虚拟机观点

操作系统把硬件包装成更容易使用的虚拟机器。

例如：

单个 CPU → 多个虚拟 CPU；
内存 + 外存 → 虚拟存储；
独占设备 → 虚拟设备。

十、操作系统的基本功能

课件最后归纳了四大功能：

这张表很适合背诵，后续章节基本就是围绕这几类功能展开。

十一、易考知识点

1. 操作系统定义、地位和作用
   会答“OS 是什么”“为什么需要 OS”。
2. 并发、共享、异步、虚拟四大特性
   尤其要区分并发和并行。
3. 多道批处理、分时、实时系统的区别
   这是常见简答题和选择题。
4. SPOOLing 技术
   要会解释输入井、输出井、虚拟设备、缓冲作用。
5. 系统态和用户态
   要知道为什么要区分，以及如何转换。
6. 特权指令和非特权指令
   要能举例说明。
7. 中断机制
   中断是 OS 获得控制权、实现调度和系统调用的重要基础。
8. 系统调用过程
   用户程序不能直接操作内核资源，必须通过系统调用进入内核。
9. 通道和 DMA 的区别
   通道功能更强，有指令系统；DMA 更简单。
10. OS 的四大管理功能
    存储管理、处理器管理、文件管理、设备管理。

十二、用课件中的 Hello 程序理解整章

课件最后用 Hello 程序提问，适合串联整章：

main()
{
    char *H = "Hello";
    printf("%s", H);
    while(TRUE)
    {
        int i = 100;
    }
}

可以这样理解：

Hello.exe 如何存放？
由文件系统负责，涉及文件管理。

Hello.exe 如何启动？
由操作系统装入程序、创建进程、分配资源。

如何分配内存？
由存储管理负责，涉及地址映射、内存分配、保护。

printf 如何输出字符串？
通过库函数进一步调用系统调用，由设备管理和 I/O 系统完成输出。

while 死循环会不会独占 CPU？
正常不会。因为间隔时钟会周期性中断，操作系统重新获得控制权并进行调度。

程序结束如何退出系统？
通过系统调用通知操作系统回收资源、关闭文件、释放内存。

这道题本质上考的是：一个应用程序从存储、装入、运行、输出、调度到退出，全程都离不开操作系统。

十三、小结

第一章是操作系统全书的地图。后面章节只是把 CPU、内存、文件、设备、进程这些模块展开讲。

进程、线程与作业

总体框架

这一章主要讲四部分：

你可以把它们理解成三个层次：

作业：用户要求计算机完成的一整套任务
 ↓
进程：作业进入内存后，程序的一次执行活动
 ↓
线程：进程内部更小的执行单位

2.1 多道程序设计

1. 单道程序设计的缺点

单道程序设计指系统中一次只允许一个程序运行。

它最大的问题是：

资源利用率低。

因为程序运行时并不是一直使用 CPU。很多时候程序在等待磁盘、打印机、磁带等 I/O 设备。

例如：

程序A：
CPU计算 → 等待设备1 → CPU计算 → 等待设备2 → CPU计算

当程序 A 等待 I/O 时，CPU 可能空闲；当 CPU 工作时，设备可能空闲。

所以单道程序设计会造成：

CPU等设备，设备等CPU，大家都不能充分利用。

2. 多道程序设计的提出

多道程序设计是指：

多个程序同时进入系统，并发地投入执行。

注意这里的“同时”不一定是真正同时。单 CPU 下通常是：

程序A运行一会儿 → 程序B运行一会儿 → 程序A继续运行 → 程序C运行……

这叫并发执行。

多道程序设计能提高：

本章中给出的例子说明：
单道方式下 CPU 利用率为 50%，多道方式下 CPU 利用率可提高到 89%。

计算公式是：

CPU利用率 = CPU实际占用时间 / 程序总运行时间

考试里常考这种题：给出多个程序的 CPU、I/O 时间段，让你画时序图并计算 CPU 利用率。

3. 多道程序设计的问题

多道程序设计虽然提高效率，但也带来管理问题。

主要有三类：

所以，多道程序设计引出了一个重要概念：

操作系统必须有一种机制来描述和管理正在执行的程序，这就是进程。

2.2 进程的引入

1. 为什么需要进程？

在多道程序系统中，程序不是从头到尾连续执行的，而是：

推进 → 暂停 → 推进 → 暂停 → ……

暂停的原因可能是：

1. 自己主动等待资源，比如等待 I/O；
2. 被操作系统剥夺 CPU，让其他程序运行。

因此，操作系统必须能做到：

暂停时：保存现场
继续时：恢复现场

所谓“现场”，主要包括：

为了保存和管理这些信息，操作系统引入了进程。

2. 进程的概念

本章给出多个定义，本质上都指向一句话：

进程是程序的一次执行过程。

也可以说：

进程是具有一定独立功能的程序，关于某个数据集合的一次运行活动。

考试中最重要的是抓住两个关键词：

所以：

程序 = 静态的代码
进程 = 程序运行起来之后的动态活动

比如：

QQ.exe 是程序
打开一个 QQ 后产生的运行实例是进程
同时打开两个 QQ，可能对应两个进程

3. 进程的三种基本状态

进程有三种基本状态：

状态转换关系非常重要：

就绪态 --获得CPU--> 运行态
运行态 --时间片用完/被剥夺CPU--> 就绪态
运行态 --等待I/O或资源--> 等待态
等待态 --事件发生--> 就绪态

注意：

等待态不能直接变成运行态。

它必须先变成就绪态，再等待调度。

考试常考判断题：

某进程等待的事件发生后，它一定立即运行吗？

答案：不一定。
事件发生后，它只是从等待态进入就绪态，是否运行还要看 CPU 调度。

4. 进程控制块 PCB

PCB 是本章最重要概念之一。

PCB，Process Control Block，进程控制块。

定义：

PCB 是标志进程存在的数据结构，其中保存操作系统管理进程所需的全部信息。

可以记成一句话：

PCB 是进程在操作系统中的“身份证 + 档案袋”。

PCB 中通常包括：

重点结论：

系统创建进程时创建 PCB，撤销进程时撤销 PCB。

所以也可以说：

PCB 是进程存在的唯一标志。

5. 进程的组成

一个进程通常由三部分组成：

进程 = PCB + 程序代码 + 数据/堆栈

具体来说：

其中：

本章还提到：

进程的程序代码和数据称为进程影像 Process Image。

6. 进程上下文与上下文切换

进程上下文可以理解为：

让一个进程能够继续运行所需的全部环境。

包括：

PCB + 程序代码 + 数据 + 地址空间 + 系统栈 + 打开文件表等

上下文切换是指：

CPU 从一个进程切换到另一个进程时，保存当前进程现场，恢复另一个进程现场。

上下文切换是有成本的。

这个成本叫：

系统开销 system overhead

所以多道程序并不是越多越好。
程序太少，资源利用率低；程序太多，上下文切换和管理开销增加，响应速度下降。

7. 进程队列

操作系统通常用 PCB 组成各种队列。

主要有三类：

一个很重要的模型是：

创建 → 就绪队列 → CPU运行 → 完成
              ↓
           等待事件
              ↓
           等待队列
              ↓
           事件发生
              ↓
           回到就绪队列

这个图是考试高频内容。

8. 进程的类型与特征

进程分为：

进程的特征有六个：

这里容易考选择题或简答题。

9. 进程间关系与相互作用

进程之间有两种关系：

进程间相互作用分为：

典型问题有：

互斥、同步、死锁、饥饿

这些内容通常会在后续章节继续展开。

10. 进程的创建与撤销

进程创建过程

一般包括：

1. 申请一个空闲 PCB；
2. 分配唯一进程标识 pid；
3. 为新进程分配资源；
4. 初始化 PCB；
5. 加载程序；
6. 将 PCB 插入就绪队列。

引起进程创建的事件包括：

进程撤销过程

一般包括：

1. 找到被撤销进程的 PCB；
2. 如果正在运行，立即停止；
3. 设置重新调度标志；
4. 撤销其子孙进程；
5. 回收资源；
6. 回收 PCB。

引起进程撤销的事件：

11. 进程等待与唤醒

进程等待

当运行进程不能继续执行时，会进入等待态。

过程是：

停止当前进程执行
保存现场到 PCB
状态改为等待态
进入等待队列

引起等待的原因包括：

进程唤醒

等待事件发生后，操作系统会唤醒进程。

过程是：

从等待队列移出
状态改为就绪态
插入就绪队列

注意：

唤醒 ≠ 立即运行

唤醒只是进入就绪态。

12. 父进程创建子进程 vs 主程序调用子程序

这是一个很容易考的比较题。

一句话：

创建子进程是并发关系，调用子程序是顺序关系。

13. UNIX 进程相关系统调用

本章重点讲了几个 UNIX 系统调用：

fork()

pid = fork();

返回值很重要：

典型代码：

pid = fork();

if (pid == 0) {
    // 子进程执行
} else {
    // 父进程执行
}

execl()

execl("P", 0);

作用是：

用新程序 P 覆盖原来的程序，从 P 的第一条指令开始执行。

wait()

父进程等待子进程结束：

pid = wait(&status);

exit()

子进程自我终止：

exit(status);

14. fork 的问题与 vfork

fork 的功能：

复制地址空间 code + data + stack
复制控制结构 proc + user

问题是：

1. 父子进程数据各自独立，不方便共享；
2. 如果子进程马上 exec 新程序，那么刚刚复制的地址空间马上被覆盖，浪费时间和空间。

所以引入了 vfork：

15. 进程与程序的联系和区别

这是考试必背内容。

一句话记忆：

程序是菜谱，进程是按菜谱做菜的过程。

2.3 线程与轻进程

1. 为什么引入线程？

进程虽然解决了多道程序管理问题，但进程切换开销大。

因为进程上下文包括：

PCB + 地址空间 + 系统栈 + 打开文件表 + 程序代码 + 数据

切换一个进程，需要保存和恢复大量信息。

而且相关进程之间共享数据不方便，因为它们通常拥有独立地址空间。

所以引入线程。

2. 线程的概念

线程是：

进程中一个相对独立的执行流。

核心区别：

进程是资源分配单位
线程是执行单位

也就是说：

一个进程至少有一个线程，也可以有多个线程。

3. 多线程的优点

多线程的优点包括：

比如 Word 可以有多个线程：

线程1：编辑输入
线程2：拼写检查
线程3：自动保存

在线视频播放器也可以有多个线程：

线程1：视频解码
线程2：音频解码
线程3：网络接收
线程4：界面控制

4. 线程结构

多线程进程中，线程共享：

代码段
数据段
堆
打开文件
地址空间

每个线程独有：

线程 ID
寄存器
PC
栈
线程状态

可以记成：

同一进程的线程：共享资源，各自执行。

5. 线程控制块 TCB

TCB 是 Thread Control Block，线程控制块。

它类似于 PCB，但更轻量。

TCB 通常包括：

存放位置取决于线程类型：

6. 用户级线程

用户级线程的特点：

线程管理由用户态线程库完成，操作系统不知道这些线程的存在。

优点：

缺点：

重点：

用户级线程：OS 不可见，切换快，但并行能力差。

7. 核心级线程

核心级线程的特点：

线程由操作系统内核创建、撤销和调度，操作系统知道线程的存在。

优点：

缺点：

重点：

核心级线程：OS 可见，可以真正并行，但系统开销大。

8. 用户级线程 vs 核心级线程

这是考试高频比较题。

9. 混合线程与轻进程 LWP

混合线程试图结合两者优点。

以 Solaris 为例，有三层：

用户级线程
    ↓
轻量级进程 LWP
    ↓
核心级线程
    ↓
CPU

本章强调：

多个用户级线程可以通过 LWP 映射到核心级线程。

10. 线程和进程的比较

这也是必背内容。

一句话：

进程更安全但更重，线程更高效但更容易相互影响。

11. 多任务与多线程的区别

例如：

一边开浏览器，一边开音乐播放器：多任务
浏览器内部一个线程加载网页，一个线程渲染页面：多线程

2.4 作业

1. 作业的概念

作业是：

用户要求计算机系统为其完成的计算任务集合。

作业比进程更偏向“用户任务”的概念。

一个作业可以包含多个作业步。

2. 作业步

作业步是：

作业处理过程中一个相对独立的步骤。

通常：

一个作业步可由一个进程完成
某些作业步之间可以并行

例如一个编程作业可能包含：

编辑源程序 → 编译 → 链接 → 执行 → 输出结果

其中每一步都可以看作一个作业步。

3. 作业分类

作业分为两类：

4. 作业控制块 JCB

JCB 是 Job Control Block，作业控制块。

它类似于 PCB，但管理对象是作业。

JCB 中通常包括：

可以这样记：

PCB 管进程，TCB 管线程，JCB 管作业。

5. 批处理作业

批处理作业常用 JCL，即作业控制语言。

JCL 用来描述作业执行步骤。

例如：

$JOB J1
$FORTN …
$LINK …
$EXEC …
$ENDJOB

批处理作业的大致过程：

作业进入输入井
    ↓
作业调度选中作业进入内存
    ↓
创建作业控制进程
    ↓
解释作业说明书
    ↓
为每个作业步创建相应进程
    ↓
输出结果
    ↓
作业结束

6. 交互式作业

交互式作业强调用户登录、输入命令、系统响应。

以 UNIX shell 为例：

显示提示符 $
读取用户命令
分析命令
如果是内部命令，直接处理
如果是外部命令，创建子进程执行
如果是后台命令，输出子进程号后继续
如果是 logout，注销并记账

这里和前面的 fork、exec、wait 联系很紧密：

shell 读入命令
fork 创建子进程
子进程 exec 执行程序
父进程 wait 等待子进程结束

本章最重要的几组对比

1. 程序、进程、线程、作业

2. PCB、TCB、JCB

3. 就绪态、运行态、等待态

易考知识点

1. 进程的定义：进程是程序的一次执行。
2. 进程和程序的区别：程序静态，进程动态；程序可长期保存，进程有生命周期。
3. 三态模型：运行、就绪、等待，以及转换原因。
4. PCB 的作用：PCB 是进程存在的唯一标志。
5. 进程组成：PCB + 程序 + 数据/堆栈。
6. 上下文切换：保存当前进程现场，恢复另一个进程现场，会产生系统开销。
7. 进程创建与撤销过程。
8. fork、exec、wait、exit 的作用和返回值。
9. 线程和进程区别：进程是资源分配单位，线程是执行单位。
10. 用户级线程和核心级线程区别。
11. 作业、进程、线程关系。

简答题模板

1. 题目：简述进程和程序的区别。

程序是静态的，是一组指令和数据的集合；进程是动态的，是程序关于某个数据集合的一次执行活动。程序可以长期保存，而进程有生命周期，会被创建、运行、等待和撤销。一个程序可以对应多个进程，而一个进程在某一时刻通常执行一个程序。进程还具有 PCB，是操作系统进行资源分配和调度的基本对象。

2. 题目：简述 PCB 的作用。

PCB 是进程控制块，是标志进程存在的数据结构。操作系统通过 PCB 保存和管理进程的全部信息，包括进程标识、状态、现场信息、调度参数、地址信息、打开文件和队列指针等。进程创建时建立 PCB，进程撤销时回收 PCB。因此 PCB 是操作系统感知和管理进程的依据。

3. 题目：为什么要引入线程？

进程切换需要保存和恢复大量上下文信息，如地址空间、系统栈、打开文件表等，系统开销较大；同时进程之间地址空间相互独立，通信不够方便。线程是进程内部相对独立的执行流，同一进程内的线程共享代码段、数据段和地址空间，只需保存少量现场信息，因此切换速度快、通信方便、系统开销小，还能提高并发性和资源利用率。

4. 题目：用户级线程和核心级线程有什么区别？

用户级线程由用户态线程库管理，操作系统不可见，创建、撤销和切换不需要进入内核，因此速度快、调度灵活，但不能充分利用多处理器，并且一个线程阻塞可能导致整个进程阻塞。核心级线程由操作系统内核管理，操作系统可见，线程是 CPU 调度单位，可以在多处理器上真正并行，一个线程阻塞不影响同进程其他线程，但创建和切换需要进入内核，系统开销较大。

小结

单道程序资源利用率低
        ↓
引入多道程序设计，提高 CPU 和设备利用率
        ↓
多道程序需要管理正在执行的程序
        ↓
引入进程
        ↓
进程需要 PCB、状态、队列、上下文切换
        ↓
进程切换开销大，进程间通信不方便
        ↓
引入线程
        ↓
线程轻量、切换快、共享进程资源
        ↓
用户提交的整体任务称为作业
        ↓
作业进入内存后通常对应一个或多个进程

本章概括：

作业是用户任务，进程是资源分配和管理单位，线程是 CPU 执行单位；多道程序设计通过进程和线程机制实现并发，提高系统资源利用率。

中断与处理器调度

第三章总主线

这一章其实围绕一句话展开：操作系统是中断驱动的。

也就是说，操作系统不是一直主动运行，而是很多时候在等待事件发生。一旦发生中断，例如 I/O 完成、时间片用完、程序出错、用户执行系统调用，CPU 就从用户程序转入操作系统，由操作系统决定：

继续原进程？让它等待？终止它？还是切换到另一个进程？

所以本章可以拆成三条主线：

3.1 中断与中断系统

1. 中断的概念

中断是指程序运行过程中出现某个紧急事件，CPU 必须暂停当前程序，转去处理该事件，处理完后再返回原程序继续执行。

可以把中断理解为：

CPU 正在做题，突然有人敲门。CPU 先把当前做到哪一步记下来，去开门处理事情，然后回来继续做题。

课件强调：操作系统是中断驱动的。没有中断，操作系统很难及时响应外设、时间片、错误、系统调用等事件。

中断系统 = 硬件 + 软件

2. 中断装置

中断装置的主要职责有四个：

1. 发现并响应中断
2. 识别中断源
3. 多个中断源同时出现时，按优先级排序
4. 保存现场，并引出中断处理程序

课件第 7 页的图展示了典型中断响应过程：正在运行的程序被打断，硬件保存 PSW、PC 到系统栈，然后根据中断向量转到中断处理程序。

这里的两个核心寄存器要特别记住：

所以保存 PC 和 PSW，本质上就是保存“程序执行到哪里”和“程序当时处于什么状态”。

3. 中断源、中断寄存器、中断字

例如 I/O 中断：

不是所有中断都一定需要中断寄存器。例如溢出中断，CPU 根据运算结果就能知道发生了溢出。

4. 中断类型

课件给了两种分类方式。

第一种：按是否由程序主动引起。

第二种：按来源。

考试中常见判断：

• 时钟中断：外部中断、强迫性中断。
• I/O 中断：外部中断、强迫性中断。
• 系统调用/访管指令：内部中断、自愿性中断。
• 除 0、溢出、非法指令：内部中断、通常属于程序性中断。

5. 中断向量

中断向量保存的是某类中断处理程序的运行环境和入口地址，主要包括：

PSW + PC

每类中断事件都有一个中断向量。中断向量的位置由硬件规定，内容由操作系统在初始化时设置好。

重点：

中断向量中的 PSW 必须是系统态/管态。

原因很简单：中断处理程序属于操作系统代码，必须在核心态运行，否则无法执行特权指令。

6. 中断嵌套与系统栈

中断嵌套是指：系统正在处理中断时，又来了一个新的、更高优先级的中断。

一般原则：

高优先级中断可以嵌入低优先级中断。

实现方法：

1. 响应一个中断后，屏蔽不高于当前优先级的中断。
2. 允许更高优先级的中断继续进入。
3. 每一层中断现场都压入系统栈。
4. 返回时按栈的后进先出顺序恢复。

课件第 18 页有一句很重要：

中断相当于一种特殊的子程序调用，发生时刻具有==不确定性==。

普通函数调用是程序自己安排的；中断调用是外部或硬件突然打断的，所以必须由硬件和操作系统共同保证现场保存正确。

7. 中断现场和进程现场

这是本章非常容易考的点。

更细一点：

当用户进程被中断时，硬件先把用户态的 PC、PSW 压入系统栈。之后操作系统可能继续保存通用寄存器等信息。

如果中断处理完后不切换进程，就从系统栈恢复现场，返回原程序。

如果需要切换进程，例如当前进程等待 I/O 或被剥夺 CPU，操作系统就要把该进程的核心级现场保存到 PCB 中。

所以说：

PCB 保存的是核心级别现场。

这是因为发生等待、剥夺等动作时，进程已经进入核心态，正在操作系统中执行，PCB 保存的是当时核心态下的寄存器、SP、PSW、PC 等。

8. 进程状态转换：结合用户态和核心态理解

课件第 22 到 36 页为状态图，这部分一定要理解。

传统进程状态是：

创建、就绪、运行、等待、终止

但本章进一步把“运行”拆成：

典型过程如下：

1. 进程创建：建立 PCB、分配资源、加载程序、初始化 PC、PSW、SP、寄存器，进入就绪队列。
2. 被调度选中：恢复 PCB 中保存的现场。
3. 最后恢复 PSW 和 PC：进程真正进入运行态。
4. 用户态运行时发生中断：PC、PSW 等现场压入系统栈，进入核心态。
5. 如果进程等待事件：保存核心现场到 PCB，PCB 进入等待队列。
6. 如果事件发生：I/O 中断唤醒该进程，PCB 从等待队列转入就绪队列。
7. 如果中断嵌套返回：从系统栈弹出现场。
8. 如果处理器被剥夺：保存当前进程核心现场到 PCB，进入就绪队列。
9. 如果执行 exit：收回资源，撤销 PCB，进入终止状态。

9. 各类中断处理程序

I/O 中断处理

I/O 正常结束时：

• 如果还需要继续传输数据，就准备下一批数据并启动通道。
• 如果有进程正在等待 I/O 完成，就唤醒该进程。

如果 I/O 出错：

• 可以重试若干次，例如 3 次。
• 仍失败，则报告系统操作员或做错误处理。

时钟中断处理

时钟分为：

时钟中断非常重要，它负责：

• 实现软件时钟和定时程序。
• 记录进程 CPU 使用时间。
• 判断时间片是否用完。
• 重新计算动态优先级。
• 记录作业等待时间。
• 统计资源使用情况。
• 实时系统中定时发出控制信号。
• 定期运行死锁检测、系统记账等维护程序。

控制台中断处理

控制台上不同按钮可对应不同中断向量。按下按钮后，系统转入对应中断处理程序。

硬件故障中断处理

例如电源故障：

1. 掉电时，硬件应保证机器继续运行一小段时间。
2. 操作系统把内存、寄存器内容保存到外存。
3. 停止设备。
4. 停止处理机。
5. 恢复时，再从外存恢复内存和寄存器。

内存故障时，系统可以检测错误单元，并把相关区域永久划为不可用区。

程序性中断处理

分两类：

课件第 46 到 60 页讲了“应用程序自行处理中断”。其核心思想是：

用户程序可以设置一个“中断续元表”。当发生某些用户可处理的异常时，OS 查表，如果用户设置了处理入口，就转到用户自己的处理程序；否则由 OS 标准处理。

自愿性中断：系统调用

用户程序不能直接执行特权指令，例如启动外设、修改系统资源、创建进程等。

解决办法是：

用户程序通过系统调用进入操作系统，由操作系统代替它完成特权操作。

系统调用有两种形式：

编译器会把系统调用形式翻译成访管指令形式。

课件第 63 页的图很重要：用户程序执行陷入指令后，陷入处理机构保护现场，取得系统调用功能号，查入口地址表，转入对应系统子程序，最后返回用户程序。

常见系统调用类型：

• 文件类：创建文件、删除文件。
• 进程类：创建进程、撤销进程。
• 通信类：发送消息、接收消息。
• 资源类：申请资源、释放资源。

3.2 处理器调度

处理器调度解决三个问题：

1. 调度评价指标

常见指标：

重点公式：

做调度题时，一般步骤是：

1. 画 Gantt 图。
2. 求每个进程完成时间。
3. 求周转时间。
4. 求带权周转时间。
5. 求平均值。

2. CPU burst 与 I/O burst

进程的运行通常不是一直占 CPU，而是：

CPU burst → I/O burst → CPU burst → I/O burst → …

CPU 调度主要考虑的是已经就绪、准备进入下一段 CPU burst 的进程。

CPU burst 预测公式：

$$ \tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n $$

含义：

• $t_n$：最近一次实际 CPU burst 长度。
• $\tau_n$：原来的估计值。
• $\tau_{n+1}$：新的估计值。
• $\alpha$：权重，通常取 0.5。

如果 $\alpha=1$，完全相信最近一次实际值。

如果 $\alpha=0$，完全不看最近一次实际值。

3. 剥夺式与非剥夺式调度

剥夺式调度响应更快，但系统开销更大，实现更复杂。

4. FCFS：先到先服务

FCFS = First Come First Serve

规则：

谁先进入就绪队列，谁先运行。

优点：

• 简单。
• 看起来公平。

缺点：

• 短作业可能等待很久。
• 容易出现“长作业堵住短作业”的现象。

适合考法：

给到达时间和运行时间，让你按到达顺序画 Gantt 图，求平均周转时间和平均带权周转时间。

5. SJF：短作业优先

SJF = Shortest Job First

规则：

选择 CPU burst 最短的作业或进程先运行。

特点：

• 如果所有任务同时到达，SJF 可以得到最短平均等待时间。
• 但长作业可能长期得不到运行，也就是“饥饿”。

适合批处理系统，不太适合交互系统。

6. SRTN：最短剩余时间优先

SRTN = Shortest Remaining Time Next

它是可剥夺版 SJF。

规则：

每次调度时选择剩余运行时间最短的进程。

如果新来的进程剩余时间更短，就可以抢占当前进程。

做题重点：

• 不只在进程结束时判断。
• 新进程到达时也要判断是否抢占。
• Gantt 图可能被切成很多段。

7. HRN：最高响应比优先

HRN = Highest Response Ratio Next

响应比公式：

$$ RR=\frac{BT+WT}{BT}=1+\frac{WT}{BT} $$

规则：

每次选择响应比最高的作业。

它兼顾了短作业和长作业：

• 如果等待时间相同，短作业响应比更高。
• 长作业等待越久，响应比也会逐渐增大，因此不容易饿死。

8. HPF：最高优先数算法

HPF = Highest Priority First

优先级分为两种：

也可以分为：

注意：不同系统对“优先数”的大小含义可能不同。

• 有的系统数值越大，优先级越高。
• UNIX 例子中 $p_{pri}$ 越小，优先级越高。

做题时一定看题目说明或样例。

9. RR：时间片轮转

RR = Round Robin

规则：

每个进程轮流运行一个时间片，用完时间片还没结束，就回到就绪队列尾部。

时间片选择很重要：

RR 适合分时系统和交互系统。

做 RR 题时，重点是维护就绪队列顺序。进程时间片用完后，如果还没结束，通常放到队尾。

10. MLQ：多级队列算法

MLQ = Multi-Level Queue

思想：

把进程固定分到不同队列，每个队列可用不同调度算法。

例如：

CPU 空闲时先看高优先级队列，高优先级队列为空才看低优先级队列。

缺点是进程所属队列固定，灵活性不够。

11. FB：反馈排队算法

FB = Feed Back

也叫多级反馈队列。

思想：

多个就绪队列，进程所在队列可以变化。

典型规则：

1. 新进程或被唤醒进程进入高优先级队列。
2. 如果一个进程用完时间片还没完成，就降到低一级队列。
3. 越低级队列时间片越长、调度频率越低。

优点：

• 交互式进程响应快。
• I/O 型进程容易被快速调度。
• CPU 型长进程调度频率下降，系统开销小。
• 不需要预先知道进程运行时间。

缺点：

• 长进程可能被惩罚，甚至饥饿。

12. 处理器调度时机

调度通常发生在三种情况：

1. 运行进程结束。
2. 运行进程等待。
3. 处理器被剥夺。

一个重要结论：

中断是处理器切换的必要条件，但不是充分条件。

意思是：

• 没有中断，操作系统一般拿不到控制权，无法切换进程。
• 但发生中断后，不一定要切换进程。

例如：

13. Dispatcher：处理器分派程序

如果中断处理后需要切换进程，就进入 dispatcher。

dispatcher 做三件事：

1. 保存下降进程现场到 PCB。
2. 按调度算法选择上升进程。
3. 从 PCB 恢复上升进程现场。

恢复现场时要注意：

先恢复通用寄存器、地址寄存器、SP，最后恢复 PSW 和 PC。

并且：

PSW 和 PC 必须用一条机器指令同时恢复。

原因是 PC 决定下一条执行哪条指令，PSW 决定以什么状态执行。如果分开恢复，可能出现“地址已经变了但状态没变”或“状态已经变了但地址没变”的危险情况，导致权限、地址空间、中断屏蔽状态不一致。

3.3 调度级别与多级调度

调度分三级：

1. 中级调度：交换

交换 swapping：

在内存和外存之间调度进程。

中级调度的目标是控制并发度。

并发度是指同时向前推进的进程个数。

并发度太高会导致：

• 系统开销大。
• 响应速度慢。
• 内存资源紧张。
• 进程频繁等待。
• 死锁可能性增加。

所以系统可能把一些进程换出到外存，降低内存压力。

课件第 106 页为加入“挂起”后的状态图：

• 就绪
• 等待
• 就绪挂起
• 等待挂起

事件发生后，等待挂起可以变为就绪挂起；换入后再回到就绪队列。

2. UNIX 中级调度

UNIX 的 sched #0 思路：

系统希望把外存中处于 SRUN 状态的进程换入内存。

如果内存不够：

1. 先换出 SWAIT 和 SSTOP 状态进程。
2. 还不够，再换出 SSLEEP 和 SRUN 状态进程。

条件：

• 待移入进程在外存时间 ≥ 3 秒。
• 待移出进程在内存时间 ≥ 2 秒。

这里体现了一个思想：不要频繁换入换出，否则交换本身会造成巨大开销。

3. 高级调度：作业调度

作业调度：

把磁盘输入井中的作业调入内存，并为其建立相应进程，使其获得运行资格。

批处理作业的状态：

课件第 111 页讲到了 SPOOLing。

SPOOLing = Simultaneous Peripheral Operation On-Line

它通过磁盘输入井/输出井，把慢速外设操作变成相对高效的联机操作。

4. JCB：作业控制块

JCB 类似于进程的 PCB，只不过它描述的是作业。

JCB 中常见信息：

• 作业标识
• 所属用户
• 作业状态
• 调度参数
• 输入井地址
• 输出井地址
• 资源需求
• 进入时间
• 处理时间
• 完成时间

JCB 由 SPOOLing 输入建立，作业调度使用，SPOOLing 输出撤销。

5. 作业调度算法

适合批处理作业调度的算法：

• FCFS
• HPF
• SJF
• HRN

不适合作业调度的算法：

• RR
• SRTN
• FB

原因是作业调度面对的是“后备作业进入系统”的问题，不是已经在内存中的进程频繁切换问题。RR、SRTN、FB 更适合低级处理器调度。

3.4 实时调度

1. 实时任务

实时任务是有明确时间约束的任务。

例如：

• 必须在某时刻前开始。
• 必须在某时刻前完成。

实时调度的目标是：

合理安排就绪实时任务的执行次序，使任务满足时间约束。

2. 实时任务分类

3. 实时调度术语

4. 周期性实时任务的可调度条件

如果任务 $P_i$ 的处理时间是 $C_i$，周期是 $T_i$，则处理器利用率为：

$$ \sum_{i=1}^{m}\frac{C_i}{T_i} $$

必要条件：

$$ \sum_{i=1}^{m}\frac{C_i}{T_i}\le 1 $$

直观理解：

所有任务平均需要的 CPU 时间不能超过 CPU 总能力。

例如课件中的例子：

• $C_1/T_1=50/100=0.5$
• $C_2/T_2=30/200=0.15$
• $C_3/T_3=100/500=0.2$

总和：

$$ 0.5+0.15+0.2=0.85<1 $$

说明从 CPU 总量上看，有可能调度成功。

5. EDF：最早截止期优先

EDF = Earliest Deadline First

规则：

谁的完成截止期最早，谁优先运行。

如果新到达任务的截止期早于当前任务，则可以抢占当前任务。

EDF 的可调度条件：

$$ \sum_{i=1}^{m}\frac{C_i}{T_i}\le 1 $$

EDF 的优点是处理器利用率高；缺点是动态比较截止期，实现复杂度比固定优先级调度高。

6. RMS：速率单调调度

RMS = Rate Monotonic Scheduling

规则：

周期越短，优先级越高。

周期短说明任务发生频率高，所以优先级高。

RMS 的充分可调度条件：

$$ \sum_{i=1}^{n}\frac{C_i}{T_i}\le n(2^{1/n}-1) $$

当 $n\to \infty$ 时，上界趋近：

$$ \ln 2 \approx 0.693 $$

强调：

注意：RMS 的利用率条件是充分条件。如果超过上界，不一定绝对不可调度，只是不能用这个简单公式保证可调度。

7. MLF：最小裕度优先

MLF = Minimum Laxity First

裕度公式：

$$ L=D-(T+C) $$

含义：

如果现在不运行这个任务，它最多还能拖多久。

如果 $L=0$，说明任务必须马上运行，否则一定错过截止期。

MLF 比 EDF 更精确，因为它不仅看截止期，还看剩余运行时间。

3.5 多处理器调度

1. 多处理器调度问题

系统中有：

• M 个进程或线程。
• N 个处理器。

在 SMP 系统中，所有处理器是对称的、同构的。

目标：

Load sharing，即负载共享，让多个 CPU 尽量均衡工作。

常见就绪队列设计：

2. 自调度

Self scheduling

规则：

多个 CPU 共同访问一个就绪队列，谁空闲谁自己取任务。

优点：

• 不需要专门处理器负责分派。
• 任务分配较均衡。

缺点：

• CPU 很多时，共享就绪队列会成为瓶颈。
• 同一线程两次调度可能在不同处理器上运行，影响缓存局部性。
• 不能保证合作线程同时运行。

Mach 的改进方式：

• 一个全局队列。
• 每个 CPU 一个局部队列。
• 调度时先看局部队列，再看全局队列。

3. 组调度

Gang scheduling

规则：

把一组相关或合作线程同时分派到多个处理器上运行。

优点：

• 避免合作线程互相等待。
• 降低同步开销。
• 提高并行程序效率。

适合多线程并行计算任务。

3.6 系统举例

1. Linux 进程调度

早期 Linux 的 goodness-based scheduling。

核心参数：

counter 的变化：

• 运行进程每个时钟中断 counter 减 1。
• counter 为 0 时，该进程不能继续运行。
• 当所有就绪进程 counter 都为 0 时，重新计算：

$$ counter = counter/2 + priority $$

goodness 规则：

调度发生时机：

• 当前进程 counter 减到 0。
• 当前进程 exit。
• 当前进程等待 I/O 或信号量。
• 原来高 goodness 的进程被唤醒。

调度效果：

• 实时进程优先于分时进程。
• 交互进程和 I/O 型进程优先于 CPU 密集型进程。

Linux SMP：

早期 Linux 2.0 使用一个大的内核自旋锁，保证任意时刻最多一个处理器执行核心代码。后来版本把大锁拆成多个细粒度锁，支持真正意义上的 SMP 并行。

2. Windows 线程调度

Windows 的调度单位主要是线程，而不是进程。

特点：

• 线程是主要调度单位
• 支持实时、前台、后台特征
• 抢占式调度
• 动态优先级
• RR
• Feedback
• 支持 SMP

Windows 优先级：

线程有两个优先级：

优先级提升情况：

• I/O 操作完成
• 等待事件结束
• 前台进程线程完成等待
• GUI 线程因窗口活动被唤醒
• 就绪时间超过一定时限还没获得 CPU

抢占 CPU 的情况：

• 被唤醒线程优先级高于当前运行线程
• 某就绪线程优先级动态提高

时间配额 quantum：

• 专业版较短
• 服务器版较长
• 时间片用完后线程进入就绪队列，优先级下降

SMP 上的 Windows 调度：

• 尽量让线程在同一个处理器上运行。
• 使用处理器亲和性 affinity。
• 每个线程有理想处理器 ideal processor。
• 空闲处理器选择线程时会考虑缓存利用、理想处理器、等待时间、优先级等因素。

3. UNIX 进程调度

UNIX 采用：

可抢占 + 动态优先级

公式：

$$ p_{pri}=\min{127,\ USER+p_{cpu}/16+p_{nice}} $$

其中：

规则：

• 运行进程每 20ms，$p_{cpu}$ 加 1，优先级降低。
• 其他进程每 1200ms，$p_{cpu}$ 减 10，优先级提高。
• 调度时选择 $p_{pri}$ 最小的进程。

这体现了动态优先级思想：

CPU 用得多，优先级下降；等待得久，优先级上升。

考点总结

概念

公式

调度算法对比

做题

1. 普通调度题

统一步骤：

1. 按算法画 Gantt 图。
2. 找每个进程完成时间。
3. 周转时间 = 完成时间 - 到达时间。
4. 带权周转时间 = 周转时间 / 运行时间。
5. 平均值 = 求和 / 进程数。

特别注意：

• SRTN 要在新进程到达时判断是否抢占。
• RR 要维护队列顺序。
• HRN 每次调度前重新计算响应比。
• HPF 要看清楚“数值大优先”还是“数值小优先”。

2. 中断与进程切换题

记住：

中断不一定导致进程切换，但进程切换一定需要操作系统通过中断或异常等机制获得控制权。

判断题常见说法：

• “发生中断一定发生进程切换”——错。
• “发生进程切换一定要保存 PCB”——对。
• “中断现场保存在 PCB 中”——不严谨，通常中断现场先保存在系统栈中。
• “PCB 保存核心级现场”——对。
• “系统调用是自愿性中断”——对。

3. 实时调度题

先算：

$$ U=\sum C_i/T_i $$

然后判断：

• EDF：若 $U\le1$，通常可调度。
• RMS：若 $U\le n(2^{1/n}-1)$，一定可调度。
• 若 RMS 超过该上界，不能直接说一定不可调度，要看题目是否要求进一步画图验证。

思考题

1. 用户程序不能执行特权指令，但想启动外设怎么办？

答案：

通过系统调用。用户程序执行访管指令 SVC/Trap，陷入操作系统，由操作系统在核心态完成外设操作，再返回用户程序。

2. 中断现场保存在什么地方？进程现场保存在什么地方？

答案：

中断现场通常保存在系统栈；进程切换时，进程现场保存在 PCB。

3. 为什么说 PCB 保存的是核心级别现场？

答案：

因为进程只有通过中断、异常、系统调用进入核心态后，操作系统才可能让它等待、剥夺它或切换它。此时保存到 PCB 的是该进程在核心态下的寄存器、SP、PSW、PC 等现场。

4. 为什么 PSW 和 PC 必须用一条机器指令同时恢复？

答案：

因为 PC 决定下一条执行地址，PSW 决定运行模式、权限、中断屏蔽等状态。如果二者分开恢复，可能出现执行地址和运行状态不匹配，造成权限错误或系统安全问题。因此必须原子地同时恢复。

小结

本章的三层逻辑：

第一层：中断让操作系统获得控制权。
包括中断类型、中断向量、系统栈、嵌套、系统调用。

第二层：获得控制权后，操作系统决定是否切换进程。
包括中断与进程切换关系、PCB 保存现场、dispatcher。

第三层：如果要切换，按照调度算法选择下一个进程。
包括 FCFS、SJF、SRTN、HRN、HPF、RR、MLQ、FB、EDF、RMS、MLF。

本章易考：

1. 概念判断：中断、系统调用、PCB、系统栈。
2. 调度算法计算：画 Gantt 图、算周转时间和带权周转时间。
3. 实时调度判断：EDF/RMS 可调度性。
4. 简答题：为什么中断是进程切换必要不充分条件；为什么 PSW 和 PC 要同时恢复。

互斥、同步与通信

主线：并发带来不确定性 → 需要互斥和同步控制 → 用信号量、管程等机制实现 → 再进一步学习进程间通信。

一、4.1 并发进程

1. 前趋图

前趋图是一个有向无环图，用来表示程序、语句、计算步骤或进程之间的先后依赖关系。

记作：

Pi → Pj

含义是：Pj 开始之前，Pi 必须已经完成。

前趋图中：

考试中如果给你一张图，通常要求判断哪些可以并发、哪些必须先后执行。

2. 顺序程序及其特性

顺序程序有两层顺序性：

内部顺序性：一个进程内部的语句按顺序执行。

例如：

S1: a = x + y
S2: b = a - z
S3: c = a + b
S4: d = c + 5

这里 S2 依赖 S1，S3 依赖 S1、S2，不能随意并发。

外部顺序性：多个进程之间也一个接一个执行，比如：

I1 C1 P1 I2 C2 P2

表示第一个作业输入、计算、打印完，第二个作业才开始。

顺序程序的三个特性：

其中可再现性最重要，因为并发程序最容易破坏它。

3. 并发程序及其特性

并发有两种：

内部并发性：一个程序内部某些语句无依赖，可以同时执行。

例如：

S1: a = x + 2
S2: b = y + 4
S3: c = a + b

S1 和 S2 互不依赖，可以并发；S3 依赖 S1、S2，必须在它们之后。

外部并发性：多个程序之间并发执行。例如多个作业的输入、计算、打印可以流水线式重叠。

并发程序的三个特性：

并发程序最核心的问题是：进程执行顺序不同，结果可能不同。这类错误称为与时间有关的错误。

4. 与时间有关的错误

文件中举了几个典型例子：

例 1：图书借阅系统

设 x = 1，表示某本书只剩 1 本。两个终端同时执行：

if x >= 1:
    x = x - 1
    借书
else:
    无书

可能出现：

1. 终端 1 判断 x >= 1 成立；
2. 还没来得及执行 x = x - 1；
3. 终端 2 也判断 x >= 1 成立；
4. 两个终端都借书成功；
5. 结果一本书被借了两次。

错误原因：多个进程并发访问并修改共享变量 x。

例 2：就绪队列整队错误

多个进程同时修改就绪队列，可能导致某个进程节点丢失。

例 3：两个进程申请两个独占资源

P1: 申请打印机 → 申请输入机
P2: 申请输入机 → 申请打印机

可能出现：

P1 已拿到打印机，等待输入机
P2 已拿到输入机，等待打印机

于是双方永久等待，形成死锁。

所以并发错误通常来自两个条件：

1. 进程交叉执行
2. 访问共享变量或共享资源

5. Bernstein 条件

为了判断两个程序能否并发执行，引入读集和写集。

两个程序 P1、P2 可以并发执行的条件是：

R(P1) ∩ W(P2) = ∅
R(P2) ∩ W(P1) = ∅
W(P1) ∩ W(P2) = ∅

合起来就是：

R(P1)∩W(P2) ∪ R(P2)∩W(P1) ∪ W(P1)∩W(P2) = ∅

理解：

只要涉及写，就可能冲突；读读不冲突。

二、4.2 进程互斥

1. 共享变量、临界资源、临界区

临界区不是随便一段代码，而是访问共享资源的那段代码。

例如：

P(mutex)
x = x - 1
V(mutex)

这里 x = x - 1 是临界区，mutex 用来保证互斥。

2. 临界区管理的三个要求

实现互斥必须满足三个条件：

考试中常考：判断某算法是否满足这三个条件。

3. 软件实现互斥

软件方法不依赖特殊硬件指令，主要靠标志变量实现，但通常存在忙等。

忙等和阻塞的区别

4. 几种软件互斥算法

尝试 1：turn 变量轮流进入

while(turn == 1);
critical section;
turn = 1;

问题：必须严格交替进入临界区。

如果 P0 不想进，P1 也可能被迫等待。

所以：不满足进展性。

尝试 2：先检查后上锁

while(flag[1]);
flag[0] = 1;
critical section;

问题：两个进程可能同时看到对方 flag 为 0，然后同时进入临界区。

所以：不满足互斥性。

尝试 3：先上锁后检查

flag[0] = 1;
while(flag[1]);
critical section;

问题：两个进程都先把自己的 flag 置 1，然后都等待对方，谁也进不去。

所以：不满足进展性，会死等。

Peterson 算法

两个进程互斥的经典软件算法：

flag[i] = true;
turn = j;
while(flag[j] && turn == j);
critical section;
flag[i] = false;

思想：

flag[i] 表示我想进
turn = j 表示如果发生竞争，我让对方先进

Peterson 算法在理论模型下满足互斥性、进展性、有限等待，是两个进程互斥中非常经典的算法。

Lamport 面包店算法

用于 n 个进程互斥。

思想类似面包店排号：

谁的号码小，谁先进；
号码相同，则进程编号小者先进。

比较规则：

(a,b) < (c,d)
当且仅当 a < c，或者 a == c 且 b < d

它通过 choosing[] 和 number[] 保证多个进程可以排出一个全序，满足互斥、进展、有限等待。

Eisenberg/McGuire 算法

也是 n 个进程的软件互斥算法。

每个进程状态有三种：

算法思想是：

1. 进程先声明自己想进入；
2. 从 turn 开始扫描前面的进程；
3. 如果没有更优先的竞争者，则把自己置为 in_cs；
4. 再检查是否有其他进程也是 in_cs；
5. 没有则进入临界区，否则重来。

它满足互斥性、进展性和有限等待。

5. 硬件实现互斥

1）关中断 / 开中断

关中断
临界区
开中断

原理：单 CPU 中，进程切换依赖中断。关中断后不会发生进程切换，所以可以保证互斥。

优点：

简单、高效、无忙等

缺点：

只适合单 CPU
影响并发性
只能由操作系统使用

2）Test-and-Set 指令

原子操作：

int test_and_set(int *lock) {
    int temp = *lock;
    *lock = 1;
    return temp;
}

使用方式：

while(test_and_set(&lock));
critical section;
lock = 0;

特点：

因为某个进程可能一直抢不到锁。

3）Swap 指令

原子交换两个变量：

swap(lock, key)

同样可以实现互斥，但也可能不满足有限等待。

4）多处理机环境下的问题

在多 CPU 系统中，不同 CPU 可能同时访问内存。普通的 test_and_set 或 swap 如果没有总线锁或缓存一致性支持，就不一定真正原子。

所以多处理机互斥需要：

lock bus
执行 test_and_set / swap
unlock bus

或者现代体系结构中的原子指令、内存屏障等支持。

三、4.3 进程同步

1. 同步的概念

同步是指一组合作进程为了协调推进速度，在某些点互相等待或唤醒。

互斥和同步的区别非常重要：

例如司机—售票员问题：

售票员先关门 → 司机才能开车
司机到站停车 → 售票员才能开门

这就是同步关系。文件中将同步机制归纳为信号量与 PV 操作、管程、条件临界区、会合、路径表达式、事件等。

2. 信号量与 PV 操作

信号量结构：

typedef struct {
    int value;
    PCB *queue;
} semaphore;

信号量有两个核心操作：

P 操作

P(S):
    S.value--
    if S.value < 0:
        当前进程阻塞，进入 S.queue

含义：申请资源 / 等待条件成立。

V 操作

V(S):
    S.value++
    if S.value <= 0:
        唤醒 S.queue 中一个等待进程

含义：释放资源 / 发出完成信号。

3. 信号量的重要结论

信号量状态解释：

4. 用信号量实现互斥

模板：

semaphore mutex = 1;

P(mutex);
临界区;
V(mutex);

例如借书系统中，对 x 的判断和修改必须放入临界区：

P(mutex)
if x >= 1:
    x = x - 1
    V(mutex)
    借书
else:
    V(mutex)
    无书

注意：只保护真正访问共享变量的部分，不要把无关代码都放进临界区，否则并发性会下降。

5. 用信号量实现同步

模板：

semaphore S = 0;

先动作进程:
    先动作;
    V(S);

后动作进程:
    P(S);
    后动作;

口诀：

谁要等，谁 P；
谁做完，谁 V。

6. 生产者—消费者问题

这是最重要的经典同步问题之一，也叫有界缓冲区问题。

资源：

生产者：

produce item;
P(empty);
P(mutex);
放入缓冲区;
V(mutex);
V(full);

消费者：

P(full);
P(mutex);
从缓冲区取出;
V(mutex);
V(empty);
consume item;

核心理解：

生产者不能在缓冲区满时放；
消费者不能在缓冲区空时取；
放和取缓冲区时还要互斥。

文件还提到提高并发性的策略：生产者只竞争 in 和 B[in]，消费者只竞争 out 和 B[out]，可以用两个 mutex 分别保护生产者和消费者侧，从而允许生产者和消费者在某些情况下更并发地执行。

7. 读者—写者问题

规则：

读者优先解法

变量：

semaphore r_w_w = 1;  // 控制读写互斥
semaphore mutex = 1;  // 保护 read_count
int read_count = 0;

读者：

P(mutex);
read_count++;
if read_count == 1:
    P(r_w_w);
V(mutex);

读操作;

P(mutex);
read_count--;
if read_count == 0:
    V(r_w_w);
V(mutex);

写者：

P(r_w_w);
写操作;
V(r_w_w);

思想：

第一个读者锁住数据库；
最后一个读者释放数据库。

问题：如果读者源源不断，写者可能饿死。

公平解法

增加一个信号量 w，让读者和写者都先经过它，避免读者无限插队。

写者优先解法

一旦有写者等待，新来的读者必须等待。变量包括：

r_w_w
rmutex
wmutex
read_q
read_count
write_count

核心思想：

第一个等待写者关闭 read_q，阻止新读者进入；
最后一个写者释放 read_q，允许读者进入。

8. 障栅 barrier 问题

问题：n 个进程都必须到达某一点，等所有进程到达后，才能继续。

变量：

count = 0
mutex = 1
barrier = 0

模板：

W1;

P(mutex);
count++;
if count == n:
    for i = 1 to n:
        V(barrier);
V(mutex);

P(barrier);

W2;

含义：

最后一个到达障栅的进程负责唤醒所有进程。

9. 三台打印机管理

三台同类打印机可以用计数信号量：

S = 3
mutex = 1
lp[1..3] = free

申请：

P(S);
P(mutex);
找到一台 free 打印机，标记 used;
V(mutex);
返回打印机编号;

释放：

P(mutex);
lp[i] = free;
V(mutex);
V(S);

这里 S 管理数量，mutex 保护打印机状态数组。

10. 吸烟者问题

传统 PV 操作无法很好解决“同时等待多个资源”的问题，因此引入：

SP: 同时 P 多个信号量
SV: 同时 V 多个信号量

关键原因：

吸烟者必须同时获得两种材料；
如果分别 P，可能拿到一个材料后等待另一个，导致错误或死锁。

11. 自行车生产线问题

资源：

工人 1 生产车架，工人 2 生产车轮，工人 3 取 1 个车架和 2 个车轮组装自行车。

简单做法可能死锁：

箱子里全是车轮，没有车架；
或者箱子里车架过多，车轮不足。

解决：限制箱子中车架和车轮数量：

S1 = k - 2  // 车架最多 k-2 个
S2 = k - 1  // 车轮最多 k-1 个

保证始终有空间让另一类资源进入，避免死锁。

12. 哲学家就餐问题

5 个哲学家，5 把叉子，每人需要左右两把叉子才能吃饭。

朴素做法：

先拿左叉，再拿右叉

可能死锁：

每个人都拿到左叉，都等待右叉。

文件给出的解法使用状态数组：

state[i] = thinking / hungry / eating
self[i] = 0
mutex = 1

测试函数：

如果 i 饥饿，且左右邻居都不在 eating，
则 state[i] = eating，并 V(self[i])

思想：

只有当左右邻居都不吃饭时，哲学家才能进入 eating 状态。

这个解法能避免死锁，但仍可能存在饥饿问题。

13. 寺庙问题

资源：

小和尚：

P(empty);
P(bucket);
P(mutex_well);
井中取水;
V(mutex_well);
P(mutex_bigjar);
水入缸;
V(mutex_bigjar);
V(bucket);
V(full);

老和尚：

P(full);
P(bucket);
P(mutex_bigjar);
缸中取水;
V(mutex_bigjar);
喝水;
V(bucket);
V(empty);

重点：P 操作顺序不当会死锁。文件明确强调：若多个小和尚、老和尚存在，先 P(bucket) 再 P(empty) 可能在极限状态下造成死锁。

14. PV 解题规则

这是考试最重要的方法论。

第一步：区分互斥和同步

第二步：设置信号量

第三步：安排 P/V 顺序

最重要规则：

如果一个进程中既有同步 P，又有互斥 P：
必须先 P(同步信号量)，再 P(互斥信号量)。

错误写法：

P(mutex);
P(empty);

如果缓冲区满，进程拿着 mutex 等 empty，其他进程无法进入临界区释放 empty，就会死锁。

正确写法：

P(empty);
P(mutex);

四、条件临界区 CCR

条件临界区形式：

region r when b do s

含义：进程执行 s 必须同时满足两个条件：

1. 没有其他进程在 r 的临界区内
2. 条件 b 为 true

例如：

region buffer when count > 0 do
    取出一个元素

优点：

比 PV 更高级，更接近问题描述。

缺点：

效率较低。

原因是条件表达式 b 可能涉及局部信息，调度程序不能统一判断。被唤醒进程还要重新计算条件，可能再次等待，本质上仍有类似忙等的问题。

五、管程 Monitor

1. 管程的基本思想

管程是一种集中式同步机制。

它把：

共享变量
访问共享变量的操作
同步控制

封装在一个模块中。

文件指出，PV 操作是分散式同步机制，灵活高效但容易写错；管程可读性更好、正确性更容易保证、便于维护。

2. 管程的特点

管程中的共享变量在外部不可见，外部只能调用管程提供的过程。

3. 条件变量

定义：

condition c;

操作：

wait(c)
signal(c)

wait(c)

含义：

当前进程进入 c 的等待队列，并释放管程互斥权。

signal(c)

含义：

如果 c 队列中有等待进程，则唤醒一个；
如果没有等待进程，则什么也不做。

注意：管程的 signal 不等同于信号量的 V 操作。

区别：

4. Hoare、Hansen、Java 管程语义

当 P 执行 signal(c) 唤醒 Q 时，有三种语义：

考试常考 Hoare 管程队列变化。文件例题中，P3 拥有管程，P4 申请进入后进入入口队列；P3 执行 signal(C) 后，条件队列中的 P2 被唤醒运行，P3 进入紧急等待队列，答案为 D。

5. 管程实现生产者—消费者

管程中定义：

B[0..n-1]
count
in
out
condition pq, cq

生产者调用：

pc.put_in(item)

消费者调用：

pc.get_out(item)

管程内部自动互斥，所以外部不需要手写 P(mutex) 和 V(mutex)。

6. 管程实现读者—写者

使用条件变量：

rq
wq
reading_count
write_count

写者优先思想：

如果有写者等待，新读者等待；
读者全部结束后唤醒写者；
写者结束后，如果还有写者继续唤醒写者，否则唤醒读者。

7. 管程和 PV 操作的等价性

文件指出：

用 PV 操作可以构造管程；
用管程也可以构造 PV 操作。

用管程构造信号量时，管程内部保存：

count
condition c

P 操作：

count--;
if count < 0:
    wait(c);

V 操作：

count++;
if count <= 0:
    signal(c);

8. Java 中的类似管程机制

Java 中：

synchronized
wait()
notify()
notifyAll()

对应管程思想。

重要规则：

Java 属于 signal and continue 语义，所以被唤醒线程不能立即执行，必须重新竞争锁。

因此 Java 中等待条件通常写成：

while (条件不满足) {
    wait();
}

而不是：

if (条件不满足) {
    wait();
}

因为被唤醒后条件可能仍然不满足。

六、Windows 互斥同步机制

文件介绍了 Windows 中几种常见同步对象：

区别：

Mutex 可以跨进程，但开销较大；
CRITICAL_SECTION 只能用于同一进程内线程，但更快；
Semaphore 允许多个线程同时访问有限数量资源；
Event 用于通知某个事件已经发生。

七、4.4 进程高级通讯

进程通讯分为：

高级通讯主要有两类：

共享内存
消息传递

文件将进程高级通讯分为 shared memory vs message passing、direct vs indirect、symmetric vs non-symmetric、buffering vs non-buffering 等类型。

1. 共享内存模式

多个进程共享同一块内存区域。

优点：

速度快，数据不需要反复复制。

缺点：

互斥和同步需要用户自己控制。

典型 Linux 系统调用：

共享内存适合同一台机器上的进程通信。

2. 消息传递模式

操作系统提供两个基本命令：

send
receive

通信形式分为：

直接通信

进程直接指定对方。

对称形式：

send(R, message)
receive(S, message)

发送者指定接收者，接收者也指定发送者。

非对称形式：

send(R, message)
receive(pid, message)

发送者指定接收者，但接收者不指定具体发送者，适合 C/S 模型。

3. 有缓冲消息传递

发送者把消息复制到内核缓冲区，接收者再从缓冲区取。

优点：

发送者和接收者不必同时到达，并发性较好。

缺点：

需要缓冲区空间，且有数据复制开销。

通常需要：

4. 无缓冲消息传递

没有中间缓冲区。

特点：

发送者 send 和接收者 receive 必须同时配合；
消息直接从发送进程空间复制到接收进程空间。

优点：

节省缓冲空间。

缺点：

并发性差，发送者或接收者可能长时间等待。

5. 间接通信：信箱 Mailbox

进程不直接指定对方，而是通过信箱通信。

send_MB(MB, M)
receive_MB(MB, N)

信箱可以支持：

多发送者—多接收者
多发送者—单接收者

信箱本质上类似有界缓冲区。

信箱结构通常包括：

in, out
s1 = k    // 空位数
s2 = 0    // 消息数
mutex = 1 // 信箱互斥
letter[0..k-1]

发送：

P(s1);
P(mutex);
放入信件;
V(mutex);
V(s2);

接收：

P(s2);
P(mutex);
取出信件;
V(mutex);
V(s1);

6. UNIX 管道 pipe

管道是 UNIX 中一种高级通信机制。

特点：

管道是特殊文件；
没有名字；
有两个文件描述符：读端 fd[0]，写端 fd[1]；
通常用于具有共同祖先的进程之间通信。

调用：

int fd[2];
pipe(fd);

使用：

fd[0] 读
fd[1] 写

优点：

实现简单，接口统一，节省内存。

缺点：

速度较慢。

管道写端关闭后，读端读完已有数据后会返回 0，表示文件结束。

7. UNIX 信号 Signal

信号是一种异步通知机制。

常见例子：

信号来源：

键盘
终端命令
程序调用
硬件异常或内核

信号处理方式：

注意：

SIGKILL 和 SIGSTOP 不能被捕捉，也不能被忽略。

信号和中断的区别：

八、本章考点

1. 概念辨析

并发 vs 并行
互斥 vs 同步
临界资源 vs 临界区
忙等 vs 阻塞
信号量 vs 条件变量
共享内存 vs 消息传递
直接通信 vs 间接通信
有缓冲 vs 无缓冲

2. Bernstein 条件

看到读集、写集题，直接判断：

读写冲突？
写读冲突？
写写冲突？

只要三个交集都为空，就可以并发。

3. 临界区管理三条件

背熟：

互斥性
进展性
有限等待

判断算法时逐条检查。

4. PV 操作题

考试常见。

通用步骤：

1. 找资源
2. 找同步顺序
3. 定义信号量
4. 写每类进程代码
5. 检查 P/V 顺序
6. 检查是否死锁、饥饿、互斥遗漏

最重要口诀：

互斥信号量初值 1；
同步信号量初值 0；
资源信号量初值为资源数；
先 P 同步，再 P 互斥；
谁等待谁 P，谁完成谁 V。

5. 经典问题模板必须掌握

重点掌握：

生产者—消费者
读者—写者
哲学家就餐
障栅 barrier
多资源管理
寺庙取水问题
单缓冲/双缓冲流水线问题

这些题本质都是 PV 操作组合。

6. 管程考点

重点掌握：

管程自动互斥；
共享变量封装在管程内部；
wait 会释放管程互斥权；
signal 不等于 V；
Hoare / Hansen / Java 三种语义区别；
Java 中 wait 要放在 while 中。

九、小结

本章研究并发进程带来的互斥、同步和通信问题。并发执行可以提高系统效率，但由于进程交叉执行并访问共享变量，会产生与时间有关的错误。为保持结果正确，需要对临界资源实施互斥，对合作进程实施同步。互斥要求满足互斥性、进展性和有限等待，可通过软件算法、硬件原子指令、关中断、信号量和管程等机制实现。信号量通过 P/V 操作管理资源、实现互斥和同步，是解决生产者消费者、读者写者、哲学家就餐等经典问题的重要工具。管程将共享变量及其操作封装起来，提供更高级、更安全的同步机制。进程高级通信包括共享内存和消息传递，消息传递又可分为直接/间接、有缓冲/无缓冲等方式。Linux/UNIX 中常见通信机制包括管道、信号和共享内存。

死锁与饥饿

本章主线：什么是死锁 → 为什么会死锁 → 如何表示死锁 → 如何预防、避免、检测、恢复 → 死锁与饥饿/活锁的区别 → 典型问题分析

一、核心框架

两个现象：

死锁：多个进程因为竞争资源，相互等待对方释放资源，导致谁也无法继续执行。它通常表现为“无限等待”，可以通过算法检测出来。

饥饿：资源分配策略不公平，导致某个进程长期得不到资源。饥饿不一定处于阻塞等待状态，也可能处于忙等状态。忙等状态下的饥饿称为活锁。

本章目录：

二、5.1 死锁的概念

1. 死锁定义

一组进程中的每一个进程，都无限期等待该组中其他进程所占有的资源，导致永远无法继续执行，这种现象叫进程死锁。

例如：

P1：申请 r1 → 再申请 r2
P2：申请 r2 → 再申请 r1

如果 P1 已经拿到 r1，P2 已经拿到 r2，那么 P1 等 r2，P2 等 r1，双方互相等待，就形成死锁。课件第5—6页用“厨房互相等待”“两头牛过桥”的图直观说明：双方都占着一部分条件，同时等待对方先让步，结果谁也走不了。

2. 由定义得到的结论

死锁有几个重要结论：

1. 参与死锁的进程至少有两个。
2. 每个参与死锁的进程都在等待资源。
3. 参与死锁的进程中至少有两个进程已经占有资源。
4. 死锁进程只是系统当前全部进程集合的一个子集，不一定所有进程都死锁。

3. 死锁产生原因

从两个角度理解：

时间上：进程推进==顺序不当==。也就是调度时机不合适，本来不该切换的时候切换，可能导致资源交叉占有。

空间上：独占资源==分配不当==。互斥资源一旦被部分分配，又不能被剥夺，就容易形成死锁。

三、5.2 死锁类型

三类：

1. 竞争资源引起的死锁

这是最常见的死锁。

不同种资源死锁

例如道路交叉口、多个方向车辆各自占用某段路，又等待下一段路。资源类型不同，但相互等待。

同种资源死锁

例如有 4 台打印机，两个进程都需要多台打印机。若资源被分散占有，每个进程都等不到足够数量，也可能死锁。

2. 进程通信引起的死锁

例如：

P1：receive(P2, M1)
P2：receive(P3, M2)
P3：receive(P1, M3)

P1 等 P2，P2 等 P3，P3 等 P1，形成通信等待环。

3. 其他原因引起的死锁

“After you / after you” 表示：双方都等对方先行动，结果谁也不行动。

四、5.3 死锁的四个必要条件：Coffman 条件

死锁发生必须同时满足四个条件：

这四个条件是必要条件。如果每类资源只有一个实例，那么它们也是充要条件。也就是说：单实例资源系统中，只要四个条件同时成立，就一定死锁。

所以：

破坏 Coffman 四个条件中的任意一个，就可以预防死锁。

五、5.4 资源分配图

资源分配图是判断死锁的重要工具。

1. 图的构成

系统资源分配图记为：

G = (V, E)
V = P ∪ R

其中：

• P 是进程集合：P1、P2、……
• R 是资源集合：R1、R2、……
• 申请边：Pi → Rj，表示进程 Pi 申请资源 Rj。
• 分配边：Rj → Pi，表示资源 Rj 已经分配给进程 Pi。

2. 图中环路与死锁的关系

重点结论：

1. 资源分配图无环路，则一定无死锁。
2. 资源分配图有环路，则可能死锁。
3. 如果每类资源只有一个实例，有环路就意味着死锁。
4. 如果某类资源有多个实例，有环路不一定死锁。

判断题：“有环一定死锁”是错的。
正确说法是：无环一定无死锁；有环不一定死锁。

3. 资源分配图约简

约简算法的思想是：看看系统中有没有某个进程可以顺利完成。如果可以完成，就假设它释放所有资源，然后继续判断其他进程。

步骤：

1. 找一个非孤立且没有请求边的进程 Pi。
2. 删除 Pi 的所有分配边，使它成为孤立点。
3. 找所有请求都可以满足的进程，把请求边改为分配边。
4. 重复上述过程。

如果最后所有节点都变成孤立点，说明图完全可约简，没有死锁。

如果不能完全约简，说明有死锁。

4. 死锁定理

系统 S 为死锁状态的充分必要条件是：S 的资源分配图不可完全约简。

六、5.5 死锁处理方法总览

死锁处理有四类：

可以这样理解：

**预防：事前立规矩。
避免：分配前先算一算。
检测：出事后查一查。
恢复：查出来后救一救。**

七、5.6 死锁预防

死锁预防的目标是：破坏 Coffman 四个条件中的至少一个。

1. 预先分配法

进程运行前一次性申请全部资源。

系统规则：

• 如果能满足，就一次性全部分配。
• 如果不能满足，一个也不分配。

这样进程运行期间不再申请新资源，所以破坏了“保持申请”条件。

优点：简单。

缺点：

1. 资源利用率低。
2. 进程很难提前知道自己需要的全部资源。
3. 有些资源暂时不用也被提前占有。

2. 有序分配法

给所有资源编号：

F(r1) < F(r2) < ... < F(rn)

规定进程必须按照资源编号从小到大的顺序申请资源。

例如：

scanner = 1
tape = 2
printer = 3

进程如果已经占有编号较大的资源，就不能再申请编号较小的资源。

它破坏的是：循环等待条件。

证明思路常考：反证法。
假设出现循环等待：

P1 等 R1，被 P2 占有
P2 等 R2，被 P3 占有
...
Pn 等 Rn，被 P1 占有

根据有序申请，应该有：

F(R1) < F(R2) < ... < F(Rn) < F(R1)

这显然矛盾，所以不会死锁。

缺点：

1. 资源编号困难。
2. 增加程序员负担。
3. 为了按顺序申请，可能提前申请暂时不用的资源，降低资源利用率。
4. 如果程序不遵守规则，仍可能死锁。

八、5.7 死锁避免与银行家算法

死锁避免是动态策略：
每次资源请求到来时，系统先判断分配后是否安全，安全才分配，不安全就等待。

1. 安全状态

如果系统存在一个安全进程序列：

<P1, P2, ..., Pn>

使得这些进程可以依次完成，那么系统处于安全状态。

安全序列的判断条件是：

Pi 还需要的资源 ≤ 当前剩余资源 + 前面已完成进程释放的资源

要理解三者关系：

安全状态 ⊄ 死锁
不安全状态 ≠ 死锁
死锁状态 ⊂ 不安全状态

也就是说：

• 安全状态一定不会死锁。
• 不安全状态不一定已经死锁。
• 死锁一定是不安全状态。

2. 银行家算法的数据结构

银行家算法要求进程提前声明最大资源需求。

常用数据结构：

其中：

Need = Claim - Allocation

3. 银行家算法的资源请求流程

当 Pi 请求资源 $Request[i]$ 时：

第一步：

Request[i] ≤ Need[i] ?

如果不满足，说明请求超过最大声明，出错。

第二步：

Request[i] ≤ Available ?

如果不满足，说明当前资源不够，Pi 等待。

第三步：试探性分配：

Available = Available - Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] - Request[i]

第四步：做安全性检查。

如果安全，正式分配。
如果不安全，撤销试探分配，让 Pi 等待。

4. 安全性检测算法

核心步骤：

Work = Available
Finish[i] = false

循环寻找某个进程 i：
Finish[i] == false 且 Need[i] ≤ Work

如果找到：
Finish[i] = true
Work = Work + Allocation[i]

最后如果所有 Finish[i] 都为 true，则安全；
否则不安全。

考试做银行家算法题时，一定要写出安全序列，例如：

<P1, P3, P4, P2, P0>

例子中，P2 请求 (1,0,2) 后仍能找到安全序列，所以可以分配；P4 请求 (3,3,0) 时当前资源不足，等待；P0 请求 (0,2,1) 虽然可试分配，但会导致不安全，所以撤销分配。

5. 银行家算法的保守性

银行家算法只知道进程的最大需求，不知道进程未来具体的申请和释放顺序。因此它会按最坏情况判断。

所以：

银行家算法可能拒绝某些实际上不会导致死锁的请求。

这就是它的保守性。第62—67页专门举例说明：某些请求被判为“不安全”而不分配，但如果真的分配，进程仍可能通过特定执行顺序全部完成。

九、5.8 死锁检测

如果系统既没有死锁预防，也没有死锁避免，就可能发生死锁。这时需要死锁检测。

1. 检测算法的数据结构

和银行家算法相似，但更简单：

注意：
死锁检测算法没有 Claim / Need，因为它不关心最大需求，只关心当前请求能否满足。

2. 检测算法思想

Work = Available
Finish[i] = false

若某进程 i：
Finish[i] == false 且 Request[i] ≤ Work

则说明它可以继续执行并释放资源：
Finish[i] = true
Work = Work + Allocation[i]

最后：

• 如果所有 Finish 都为 true，无死锁。
• 如果某些 Finish 为 false，这些进程就是参与死锁的进程。

优化点：

如果某进程当前没有占有资源，即：

Allocation[i] = 0

那么初始化时可令：

Finish[i] = true

因为它不占有资源，不会阻塞别人，通常不用参与检测。

3. 什么时候检测？

常见时机：

1. 进程等待资源时检测。
2. 定时检测。
3. CPU 等资源利用率下降时检测。
4. 交互式任务长期无响应时检测。

十、5.9 死锁恢复

检测到死锁后，需要恢复。方法有四种。

1. 重新启动

最简单、最常用，但代价很大。

2. 终止进程

有两种：

• 一次性终止所有死锁进程。
• 逐步终止，根据优先级或代价函数选择牺牲哪个进程。

3. 剥夺资源

强行从某些进程那里拿回资源。

也有两种：

• 一次剥夺。
• 逐步剥夺。

4. 进程回退

让进程回退到之前某个安全点重新执行。
缺点是系统开销大，需要保存检查点。

十一、5.10 鸵鸟算法

鸵鸟算法就是：假装看不见死锁。

工程观点认为：

• 死锁发生频率可能很低。
• 处理死锁的日常开销可能远大于偶尔死锁造成的损失。
• 用户可能更愿意忍受偶发故障，而不是让系统长期变慢。

课件提到 UNIX、Windows 等商用系统在很多情况下采用这种思路。

数学观点则认为：
只要理论上会死锁，就必须处理。

考试中可以这样答：

鸵鸟算法是一种工程折中策略，适用于死锁发生概率低、处理成本高、系统更重视平均性能的场景。

十二、5.11 有关问题讨论

1. 关于充要性算法

死锁预防没有运行时检测开销，但限制多、资源利用率低。

死锁避免开销大，而且银行家算法不是必要性算法。它只知道最大资源需求，不知道未来具体资源申请和释放顺序，因此只能保守判断。

如果要做真正充要的判断，需要知道每个进程完整的资源命令序列，但由于程序有分支和循环，这通常很困难。

2. 消耗型资源

消耗型资源也叫生灭资源，例如消息。

• send 产生消息。
• receive 消耗消息。

消息通信也可能死锁。常见解决方式是：超时技术。

3. 可剥夺资源

CPU 是可剥夺资源，可以被高优先级进程抢占，因此多个进程一般不会因为竞争 CPU 而死锁。

内存也可以通过外存交换缓解。若外存也不足，理论上仍可能死锁，但实际较少见。

4. 两阶段锁

两阶段封锁协议包括：

1. 增长阶段：只加锁，不释放锁。
2. 消退阶段：只释放锁，不加锁。

死锁可能发生在增长阶段。

十三、5.12 饥饿与活锁

1. 饥饿和死锁的区别

2. 饥饿定义

如果一个进程等待时间过长，已经明显影响推进和响应，就称为饥饿。

如果等待到某种程度，即使任务完成也失去意义，就称为饿死。

3. 排队等待与忙式等待

排队等待：进程申请不到资源就阻塞，等资源可用后再唤醒。

优点：不浪费 CPU。
缺点：需要进程切换，有系统开销。

忙式等待：进程不阻塞，而是不断检查资源是否可用。

如果忙式等待时间过长，就可能形成活锁。

4. 活锁

活锁是忙式等待条件下发生的饥饿。

活锁和死锁不同：

• 死锁通常完全停住。
• 活锁中进程还在运行，但没有实质进展。
• 活锁可能解除。

UNIX v6 中进程表项耗尽的例子说明：进程不断尝试 fork()，失败后睡眠再试，若一直得不到表项，就形成活锁；但如果某些子进程结束，表项释放，活锁可能解除。

十四、哲学家就餐问题

这是死锁问题的经典例子。

1. 问题描述

5 个哲学家围坐圆桌，每两人之间有一把叉子。每个哲学家要吃饭，必须同时拿到左、右两把叉子。

注意：课件强调，叉子不是“同种组合资源”，因为每把叉子的位置不同。第92—96页图展示了 5 个哲学家和 5 把叉子的环形关系。

2. 错误做法

每个哲学家都先拿左叉，再拿右叉：

P(fork[i])
P(fork[(i+1) mod 5])
eat()
V(fork[(i+1) mod 5])
V(fork[i])

如果 5 个哲学家同时拿到左叉，再都等待右叉，就死锁。

3. 防止死锁的三种方法

这里给出三种思路：

1. 最多只允许 4 个哲学家同时坐到桌边。
2. 只有左右两把叉子都可用时，才允许哲学家拿叉子。
3. 奇数号哲学家先拿左叉，偶数号哲学家先拿右叉，破坏循环等待。

4. PV 操作解法思想

引入：

state[i] = thinking / hungry / eating
self[i]  = 每个哲学家自己的信号量
mutex    = 保护 state 的互斥信号量

核心测试函数：

如果 i 号哲学家 hungry，
且左右邻居都不是 eating，
则让 i 进入 eating，并唤醒 i。

注意：
共享变量 state 的修改必须放在临界区中，所以需要 mutex。

这个解法可以避免死锁，但课件也指出可能存在饿死问题：某哲学家的左右邻居交替进食，导致它长期无法进食。

十五、过河问题

过河问题可以看成多个进程竞争石块资源。

1. 简单过河问题

最简单策略是：同一时刻只允许一个方向过河。

这可以预防死锁，但可能导致：

• 饥饿或饿死。
• 并行度低。

2. 石块桥过河问题

一个更复杂的石块桥问题：

• 西岸到东岸路线：1-2-3-4-6-5
• 东岸到西岸路线：5-6-7-8-2-1

每个石块最多容纳一个人。

死锁情况包括：

1. 两个方向各有 3 人踏上石块时，必发生死锁。
2. 两个方向各有 1 人分别踏上 1、2 或 5、6 时，也可能发生死锁。

3. 解法思想

一种方法是：

1. 限制同时过河人数不超过 5。
2. 对竞争严重的石块对 1、2 和 5、6 使用有序分配法。
3. 用信号量表示石块资源。
4. 用额外信号量限制总人数。

后面进一步提高并行度，在某些情况下最大并行度可以达到 8，但实现更复杂，需要记录东西方向正在过河人数、等待人数，并配合等待队列。

理解：

过河者 = 进程；石块 = 独占资源；路线 = 资源申请顺序。
死锁预防的核心是限制并发数量和规定资源申请顺序。

十六、5.13 简单组合资源死锁的静态分析

这一节比较偏证明和分析题。

1. 基本概念

可复用资源：一次只能分配给一个进程使用的资源。

组合资源：由若干相对独立的子资源构成的资源集合。

同种组合资源：由相同类型子资源构成的组合资源。

简单组合资源：每类子资源只有一个资源实例。

2. 静态分析条件

已知每个进程的资源活动序列，判断是否可能死锁。

3. 分析步骤

第一步：把每个进程“占有资源、申请资源”的情况写成状态：

(pi : aj : ak1, ak2, ..., akn)

含义：

进程 pi 正在请求 aj，同时已经占有 ak1, ak2, ..., akn

第二步：每个状态作为一个节点。

第三步：如果 P1 申请的资源被 P2 占有，就从 P1 状态节点向 P2 状态节点画有向边。

第四步：找所有环路。

第五步：判断环路上的状态能否同时到达。

不能同时到达的两种情况：

1. 环路中有相同进程。
2. 环路中有相同被占有资源。

如果环路上的状态可以同时到达，则有死锁可能。

第137—138页图展示了多个环路的判断：有的环路因为含有相同进程而不可达，有的因为要求同一资源同时被不同状态占有而不可达，有的环路则可以同时到达，因此会产生死锁。

十七、5.14 同种组合资源死锁的必要条件

这一节给出一个非常重要的判定公式。

设：

M：资源数量
N：使用该类资源的进程数量
Σ：所有进程需要该类资源的总量

结论：

如果 Σ < M + N，则一定没有死锁。
如果 Σ ≥ M + N，则至少存在某种交叉执行可能发生死锁。

证明思路：

假设有 n 个进程参与死锁：

2 ≤ n ≤ N

参与死锁的进程所需资源总量至少为：

M + n

未参与死锁的进程至少各需要 1 个资源，所以总需求至少为：

N - n

因此：

Σ ≥ M + n + N - n = M + N

所以如果：

Σ < M + N

就不可能死锁。

例子

例1：

M = 15
N = 4
P1(4), P2(6), P3(1), P4(7)

Σ = 4 + 6 + 1 + 7 = 18
M + N = 19
Σ < M + N

所以无死锁可能。

例2：

M = 15
N = 4
P1(5), P2(6), P3(1), P4(7)

Σ = 5 + 6 + 1 + 7 = 19
M + N = 19
Σ ≥ M + N

所以存在死锁可能。

十八、考试重点

1. 必背概念

1. 死锁定义
2. 死锁四个必要条件
3. 资源分配图中“无环一定无死锁，有环不一定死锁”
4. 死锁定理：资源分配图不可完全约简是死锁的充要条件
5. 安全状态、安全序列、不安全状态、死锁状态之间的关系
6. 饥饿、活锁与死锁的区别

2. 算法

1. 资源分配图约简
2. 银行家算法
3. 安全性检测算法
4. 死锁检测算法
5. 简单组合资源静态死锁分析
6. 同种组合资源公式：Σ < M + N 则无死锁

3. 银行家算法模板

1. 计算 Need = Max - Allocation
2. 判断 Request ≤ Need
3. 判断 Request ≤ Available
4. 试分配
5. 用安全性算法寻找安全序列
6. 若存在安全序列，则分配；否则撤销分配

4. 死锁检测模板

1. Work = Available
2. Finish[i] = false
   若 Allocation[i] = 0，可令 Finish[i] = true
3. 找 Request[i] ≤ Work 的进程
4. Work = Work + Allocation[i]
5. 重复
6. 若最后有 Finish[i] = false，则这些进程死锁

十九、小结

死锁是多个进程互相等待对方资源而无限阻塞。死锁产生必须满足资源独占、不可剥夺、保持申请、循环等待四个 Coffman 条件。资源分配图无环一定无死锁，有环可能死锁；不可完全约简是死锁的充要条件。处理死锁有预防、避免、检测、恢复四类方法。预防通过破坏必要条件，避免通过银行家算法保持安全状态，检测通过 Work/Finish 判断当前是否已有死锁，恢复可重启、终止进程、剥夺资源或回退。饥饿是长期得不到资源，忙等形式的饥饿称为活锁。哲学家就餐、过河问题、组合资源分析都是死锁思想的典型应用。

存储管理

本章主线：操作系统如何管理内存，让多个进程安全、高效、灵活地共享有限的主存空间。

第六章 主存管理

本章可以分成四大部分：

1. 存储管理功能：操作系统为什么要管理内存，要完成哪些任务。
2. 内存资源管理：内存空闲区如何记录、如何分配、如何回收。
3. 存储管理方式：界地址、分页、分段、段页式四种管理方式。
4. Linux 伙伴堆算法：Linux 如何管理连续页框，如何分配和合并空闲内存块。

程序给出的是逻辑地址，CPU真正访问的是物理地址。
主存管理的核心，就是完成“逻辑地址到物理地址的转换”，同时解决分配、回收、共享、保护、扩充和碎片问题。

6.1 存储管理功能

1. 存储分配和去配

操作系统需要决定：

• 给哪个进程分配内存；
• 分配多大；
• 分配在哪里；
• 进程结束后如何回收。

分配和去配的对象包括内存和外存，方法上具有相似性。分配和回收通常发生在：

• 进程创建；
• 进程撤销；
• 进程交换；
• 进程长度变化，例如栈溢出或栈扩展。

为了管理这些空间，系统需要两类表：

问：操作系统为什么需要空闲表和分配表？
答：为了知道哪些内存已经被占用，哪些内存还可以继续分配。

2. 存储共享

存储共享的目的有两个：

第一，节省内存。例如多个进程运行同一个程序时，代码段可以只在内存中保存一份。

第二，进程间通信。多个进程可以通过共享数据段交换信息。

共享内容包括：

• 代码；
• 数据。

注意：代码段通常可以共享，因为代码一般是只读的；数据段通常不能随便共享，因为不同进程的数据应该相互隔离。

3. 存储保护

存储保护主要解决两个问题：

例如，一个进程只能访问自己的内存空间，不能随便读写操作系统内核或其他进程的数据。

4. 存储扩充

存储扩充指的是把内存和外存结合起来，形成虚拟存储体系。

理想目标是：

速度接近内存，容量接近外存。

基本思想是：

• 正在运行的程序放在内存中；
• 暂时不用的程序或页面放到外存中；
• 需要时再调入内存。

这就是后面虚拟存储、换入换出、页面置换等内容的基础。

5. 地址映射

地址映射是本章最核心的概念之一。

程序中使用的地址叫：

逻辑地址

内存硬件真正访问的地址叫：

物理地址

地址映射就是：

逻辑地址 → 物理地址

文件中提到三种地址映射方式：

固定地址映射

在编译时就确定逻辑地址和物理地址的对应关系。

缺点很明显：程序必须放在指定内存位置。如果那个位置已经被占用，就会发生冲突。

静态地址映射

程序装入内存时，由操作系统完成地址映射。

公式是：

物理地址 = 逻辑地址 + 装入地址

特点：

• 程序运行前确定映射关系；
• 程序装入后不能移动；
• 程序必须占用连续内存空间。

动态地址映射

在程序运行过程中，每次访问内存时才进行地址转换。

例如执行：

MOV AX, [500]

访问逻辑地址 500 时，硬件临时把它转换为物理地址。

动态映射需要硬件支持，例如：

• MMU，内存管理单元；
• 基址寄存器；
• 限长寄存器；
• 快表 TLB。

它的优点是灵活，程序在内存中可以移动；缺点是地址转换有额外开销。

6. 实际存储体系

文件中给出三级存储体系：

Cache + 内存 + 辅存

核心思想：

当内存不够时，用辅存支持内存。

暂时不用的程序可以换出到辅存，需要时再换入内存。

7. 局部性原理

局部性原理是 Cache、虚拟存储、分页管理能够高效工作的基础。

分为两种：

时间局部性

正在访问的存储单元，在不久之后还可能再次被访问。

例如循环中的变量反复被使用。

空间局部性

程序在短时间内访问的地址，往往集中在较小范围内。

例如顺序执行数组元素：

a[0], a[1], a[2], a[3]

这些地址相邻，所以具有空间局部性。

6.2 内存资源管理

这一节主要讲：空闲内存怎么表示，怎么分配，怎么回收。

1. 内存分区方式

按照分区时刻，可以分为：

按照分区大小，可以分为：

常见组合：

2. 静态等长分区的分配

静态等长分区常用于分页管理。因为每个页框大小相同，所以管理方式比较简单。

三种方法：

1）位示图 / 字位映象图

用一个 bit 表示一个页面状态：

分配时：

从头寻找第一个为 0 的 bit，改为 1，返回页号。

回收时：

把对应页号的 bit 改回 0。

优点是结构紧凑，缺点是如果内存很大，查找空闲位可能需要扫描较多位置。

2）空闲页面表

把若干连续空闲页面作为一组登记在表中。

表项包括：

例如：

表示第 120、121、122、123 页都是空闲的。

3）空闲页面链

把所有空闲页面连成链表。

优点：

节省空间。

缺点：

对外存页面的分配和去配需要执行数据传输，速度较慢。

3. 动态异长分区的分配

动态异长分区不是一开始固定划分，而是根据进程申请的大小动态切割内存。

它使用：

空闲区域表

表中记录：

==动态分区==常用四种分配算法：

1. 最先适应 First Fit；
2. 下次适应 Next Fit；
3. 最佳适应 Best Fit；
4. 最坏适应 Worst Fit。

4. 最先适应算法 First Fit

空闲区按首地址递增排列。

申请内存时，从头开始找，找到第一个大小足够的空闲区就分配。

优点：

尽量使用低地址空间，高地址区可以保留较大的空闲区域。

缺点：

可能频繁切割前面的空闲区，形成碎片。

5. 下次适应算法 Next Fit

它和 First Fit 类似，但不是每次从头找，而是：

从上次分配位置的下一个位置继续找。

优点：

减少查找时间，使空闲区域分布更均匀。

缺点：

也可能切割较大的空闲区。

6. 最佳适应算法 Best Fit

申请内存时，选择：

能满足申请要求的最小空闲区。

优点：

尽量保留大空闲区。

缺点：

容易留下很小的碎片。

例如申请 30KB，如果有一个 32KB 的空闲区，Best Fit 会使用它，剩下 2KB 碎片。

7. 最坏适应算法 Worst Fit

申请内存时，选择：

最大的空闲区。

优点：

分割后剩余区域仍然比较大，不容易形成极小碎片。

缺点：

会破坏大的空闲区域。

8. 四种动态分区算法对比

题目给一串“分配、释放、再分配”的操作，让画内存变化图，问最后最大空闲分区是多少。

做题方法：

1. 画一条内存条；
2. 按顺序执行分配和释放；
3. 每次分配时根据算法选择空闲区；
4. 注意释放后相邻空闲区要合并；
5. 最后看最大空闲分区。

9. 碎片与紧凑

动态异长分区容易形成很小的空闲区域，这些小区域叫：

碎片 fragment

碎片太多会造成内存浪费。

解决方法是：

紧凑 compaction

紧凑就是移动已经占用的区域，让所有空闲区合并成一个大的连续空闲区。

优点：

可以得到大的连续空闲空间。

缺点：

开销很大，需要移动进程，可能导致系统暂停。

紧凑时机包括：

• 系统找不到足够大的空闲区时；
• 定期进行；
• 空闲区管理过于复杂时。

6.3 存储管理方式

这一节是全章最重要的部分

四种方式：

6.3.1 界地址管理方式

1. 基本思想

界地址管理是最简单的内存管理方式。

它的特点是：

一个进程占用一个连续的内存区域。

进程逻辑地址从 0 到 l-1。

假设进程装入内存的起始地址是 b，进程长度是 l。

那么逻辑地址 a 对应的物理地址是：

物理地址 = b + a

但前提是：

0 ≤ a ≤ l - 1

如果不满足，就越界。

2. 需要的寄存器

界地址管理需要两个寄存器：

地址转换过程：

1. CPU 产生逻辑地址 a；
2. 判断 a 是否小于 l；
3. 如果越界，产生中断；
4. 如果合法，物理地址 = b + a。

3. 单对界和双对界

单对界

一个进程只有一对 base 和 limit。

特点：

整个进程占用一个连续内存区。

双对界

一个进程可以有两个连续区域：

• 代码空间 I 空间；
• 数据空间 D 空间。

代码区可以被多个进程共享，数据区通常由进程独享。

4. 交换技术 Swapping

当内存不够时，系统可以把暂时不能运行的进程写到磁盘，叫：

换出 Swap Out

当进程需要运行时，再从磁盘写回内存，叫：

换入 Swap In

缺点：

• 换入换出是 I/O 操作，开销大；
• 交换单位太大，通常是整个进程；
• 需要考虑外存交换区管理；
• 换入时可能需要重新定位地址。

5. 重定位

因为进程换出后再次换入内存，位置可能变了，所以需要重定位。

相关概念：

6. 覆盖技术 Overlay

覆盖技术的目的：

在较小内存中运行较大程序。

它把程序分成多个段：

• 常驻区：放全局代码和数据；
• 覆盖区：多个程序段轮流使用同一块内存。

例如一个程序总大小 190KB，但实际内存只有 110KB，可以让不同时执行的模块共用覆盖区。

缺点：

• 需要程序员手动划分模块；
• 需要从外存反复装入模块，执行时间变长。

6.3.2 页式存储管理 Paging

==分页==是本章最重要的内容之一

1. 基本思想

分页管理中：

• ==内存==被划分成大小相同的块，叫页框 frame；
• ==进程逻辑空间==也被划分成同样大小的块，叫页面 page。

页面可以装入任意页框，不需要连续。

2. 页式地址结构

逻辑地址由两部分组成：

逻辑地址 = 逻辑页号 p + 页内地址 d

物理地址由两部分组成：

物理地址 = 页框号 f + 页内地址 d

页内地址 d 不变，只需要把逻辑页号 p 转换成页框号 f。

所以分页地址转换的本质是：

p → f

3. 页表

每个进程有一张页表。

页表记录：

含义是：

• 逻辑第 0 页在物理第 15 个页框；
• 逻辑第 1 页在物理第 22 个页框；
• 以此类推。

4. 页式地址转换步骤

逻辑地址为：

(p, d)

转换过程：

1. CPU 产生逻辑地址 p, d；
2. 查快表 TLB，看是否有 p 对应的页框号 f；
3. 如果 TLB 命中，直接得到 f；
4. 如果没有命中，则查页表；
5. 判断页号 p 是否越界；
6. 从页表中找到页框号 f；
7. 将 p → f 的映射放入快表；
8. 得到物理地址 f, d。

5. 快表 TLB

快表是一组联想寄存器，用来保存当前进程页表中的一部分常用表项。

为什么需要快表？

因为如果没有快表，每次访问数据都需要：

1. 访问页表；
2. 再访问真正的数据。

也就是一次逻辑访问变成两次内存访问。

有快表后，如果命中，就可以少访问一次页表。

6. 有效访问时间 EAT

文件中给出的单级页表 EAT 公式是：

EAT = 命中率 × (快表访问时间 + 内存访问时间)
    + (1 - 命中率) × (快表访问时间 + 2 × 内存访问时间)

例如：

命中率 = 98%
快表访问时间 = 20ns
内存访问时间 = 100ns

则：

EAT = 98% × (20 + 100) + 2% × (20 + 200)
    = 122ns

这个公式考试常考

7. 多级页表

为什么需要多级页表？

因为单级页表可能太大。

例如：

• 32 位地址空间是 4GB；
• 页大小 4KB；
• 页内地址占 12 位；
• 页号占 20 位；
• 页表最多有 2²⁰ 个表项；
• 如果每个表项 4 字节，页表大小是 4MB；
• 这 4MB 页表还需要连续的 1K 个页框存放。

问题：

1. 页表太大；
2. 需要连续空间；
3. 进程地址空间中有很多空洞，页表项浪费严重。

解决方法：

二级页表或多级页表。

8. 二级页表

二级页表把大页表再分页。

结构：

逻辑地址 = 外层页号 p1 + 内层页号 p2 + 页内地址 d

地址转换：

1. 用 p1 查页目录表；
2. 找到对应页表页；
3. 用 p2 查页表页；
4. 得到页框号 f；
5. 形成物理地址 f, d。

特点：

• 页目录表常驻内存；
• 页表页可以按需调入；
• 页表页之间不需要连续；
• 减少了连续内存需求。

缺点：

如果没有快表，访问数据需要三次内存访问：页目录表、页表页、数据单元。

9. 四级页表 EAT

文件中给出四级页表的 EAT 公式：

EAT = 命中率 × (快表访问时间 + 内存访问时间)
    + (1 - 命中率) × (快表访问时间 + 5 × 内存访问时间)

例如：

98% × (20 + 100) + 2% × (20 + 500)
= 128ns

这里未命中时要访问 5 次内存：四级页表 + 实际数据。

10. 反置页表 Inverted Page Table

传统页表是：

每个进程一个页表，每个逻辑页一个表项。

如果虚拟地址空间很大，传统页表会很大。

反置页表改为：

面向物理内存，每个物理页框一个表项。

表项内容是：

(pid, p)

即：

• 哪个进程；
• 哪个逻辑页；
• 占用了这个物理页框。

优点：

表大小固定，只和物理页框数有关。

缺点：

地址转换时查找困难。

因为给定 pid 和逻辑页号 p，需要反过来找它在哪个物理页框中。

11. 反置页表的 Hash 技术

为了加快反置页表查找，可以使用杂凑 Hash 技术。

过程：

1. 根据 hash(pid, p) 计算入口；
2. 从入口开始查找；
3. 找到匹配的 pid 和 p；
4. 表项位置就是页框号 f；
5. 得到物理地址 f, d。

为了进一步提高速度，也可以使用 TLB 缓冲。

12. 页式存储管理优缺点

优点：

消除了外部碎片。

因为进程的页面可以分散放在任意空闲页框中，不需要连续内存。

缺点：

会产生页内零头，也就是内部碎片。

如果一个进程大小不是页大小的整数倍，最后一页可能用不满。

平均来说，一个进程页内零头大约是半页。

页式地址转换例题

例子：

• 进程大小 8KB；
• 页面大小 2KB；
• 页面依次装入内存第 7、9、2、5 块；
• 求逻辑地址 0AEF 的物理地址。

页面大小 2KB = 2048B = 2¹¹，所以页内地址占 11 位。

逻辑地址 0AEF 十六进制转换时，可以分为：

逻辑页号 + 页内地址

根据文件中的结果，逻辑页号为 1，页内地址为 2EF。

页表中：

逻辑页 1 → 页框 9

所以物理地址为：

页框号 9 + 页内地址 2EF

即：

物理地址 = 9 × 2KB + 2EF

文件中转换结果为：

4AEF

你做这类题时只要记住：

页内地址不变，只替换页号为页框号。

6.3.3 段式存储管理 Segmentation

1. 基本思想

分页是从物理管理角度划分的，页面大小固定，用户通常感受不到页面的逻辑意义。

分段则不同，它按照程序的逻辑结构划分。

例如一个程序可以分为：

• 主程序 main；
• 函数 X；
• 函数 Y；
• 数据段 D。

每个段是一个逻辑单位。

2. 段式地址结构

段式逻辑地址是二维地址：

逻辑地址 = 段号 s + 段内地址 d

物理地址计算：

物理地址 = 段首址 b' + 段内地址 d

前提是：

0 ≤ d ≤ 段长 l' - 1

否则段内地址越界。

3. 段表

每个进程有一张段表。

段表表项包括：

例如：

4. 段式地址转换步骤

逻辑地址为：

(s, d)

转换过程：

1. CPU 产生逻辑地址 s, d；
2. 查 TLB，看是否已有段号 s 对应的段首址和段长；
3. 如果没有命中，检查段号 s 是否越界；
4. 查段表，得到段首址 b' 和段长 l'；
5. 检查段内地址 d 是否越界；
6. 若合法，物理地址 = b' + d。

段式管理中有两次越界判断：

5. 段的共享

段式管理天然适合共享。

例如多个进程使用同一个代码段，可以让它们的段表指向同一个物理段。

文件中讲了共享段表。

共享段表记录：

共享过程：

1. 第一个进程使用共享段时，将该段登记到共享段表，共享计数为 1；
2. 其他进程使用时，共享计数加 1；
3. 某进程结束使用时，共享计数减 1；
4. 当共享计数为 0 时，释放该段。

6. 段的保护

段式管理也适合做保护。

可以在段表中增加访问权限位：

例如代码段可以设置为：

R = 1, W = 0, E = 1

表示可以读、可以执行，但不能写。

7. 段式管理优缺点

优点：

• 符合程序逻辑结构；
• 方便共享；
• 方便保护；
• 段长可以不同，比较灵活。

缺点：

• 段长不固定，需要动态异长分配；
• 会产生外部碎片；
• 需要空闲区管理算法，如 FF、NF、BF、WF。

6.3.4 段页式存储管理

段页式是分页和分段的结合。

段式优于页式：便于共享和保护。
页式优于段式：消除碎片问题。
段页式：结合二者优点。

1. 基本思想

一个进程先分成若干段，每个段再分成若干页。

所以逻辑地址是三部分：

逻辑地址 = 段号 s + 逻辑页号 p + 页内地址 d

物理地址是：

物理地址 = 页框号 f + 页内地址 d

2. 需要的表

段页式需要两级结构：

段表

每个进程一张段表。

段表中每个表项记录：

页表

每个段一张页表。

页表记录：

3. 段页式地址转换步骤

逻辑地址：

(s, p, d)

转换过程：

1. CPU 产生逻辑地址 s, p, d；
2. 查快表，看是否有 s, p 对应的页框号 f；
3. 若命中，直接形成物理地址 f, d；
4. 若未命中，检查段号 s 是否越界；
5. 查段表，找到该段页表的首址 b' 和长度 l'；
6. 检查页号 p 是否越界；
7. 查该段页表，得到页框号 f；
8. 把 s, p, f 放入快表；
9. 形成物理地址 f, d。

4. 段页式优缺点

优点：

• 保留分段的逻辑性；
• 方便共享和保护；
• 保留分页的离散分配能力；
• 减少外部碎片。

缺点：

• 地址转换过程更复杂；
• 需要段表和页表；
• 未命中快表时访问内存次数更多。

5. 代码段共享例子

文本编辑器：

文本编辑器包括：

• 150KB 代码段；
• 50KB 数据段。

如果有 10 个进程并发执行。

不共享代码时：

10 × (150 + 50) KB = 2000KB = 2MB

共享代码段时：

150KB + 10 × 50KB = 650KB

这说明共享代码段可以大幅节省内存。

6.4 Linux 伙伴堆存储分配算法

这一部分讲 Linux 如何管理物理页框

1. 为什么需要伙伴堆算法？

Linux 中 DMA 输入输出不带地址变换机构，因此某些场景下要求进程或设备使用连续的物理页面。

伙伴堆算法用于管理内存中的空闲页框，是一种针对碎片问题的稳定、高效分配策略。

2. 基本概念

页框

内存被静态划分成等长区域，每个区域叫页框。

例如：

1 页框 = 4KB

块组

Linux 把空闲页面按大小分组。

第 i 组中的块大小为：

2^i 个页面

例如：

同一组中的所有空闲块用链表连接。

3. free_area$[i]$

文件中说：

free_area[i]

表示页框数为 2^i 的块组。

它包含两类指针：

4. 什么是伙伴 Buddy？

两个块成为伙伴，需要满足三个条件：

1. 大小相同；
2. 物理地址相邻；
3. 按页框编号计算，后一个块最后页框号 + 1 必须是 2b 的整数倍，其中 b 是块大小。

简单理解：

两个相邻、同大小、由同一个大块拆出来的块，就是伙伴。

例如对于块组 1，每个块大小是 2 页：

• 页框 0、1 是一块；
• 页框 2、3 是一块；
• 这两块是一对伙伴。

对于块组 2，每个块大小是 4 页：

• 页框 0、1、2、3 是一块；
• 页框 4、5、6、7 是一块；
• 这两块是一对伙伴。

5. 伙伴堆分配算法

申请 fn 个页框时：

1. 找到最小的 i，使得：

2^(i-1) < fn ≤ 2^i

2. 到第 i 组中找空闲块；
3. 如果第 i 组有空闲块，直接分配一个 2^i 页的块；
4. 如果没有，就向更大的块组查找；
5. 找到更大的块后，把它拆分；
6. 分配需要的部分；
7. 剩余部分放回对应块组；
8. 修改位图。

例如申请 3 页：

2^1 < 3 ≤ 2^2

所以要分配 4 页。

这会产生 1 页内部碎片。

6. 伙伴堆释放算法

释放一个块时，系统会检查它的伙伴是否也空闲。

如果伙伴也空闲：

合并成更大的块。

然后继续检查更大块的伙伴是否空闲，可以继续向上合并。

例如释放页框 13 后：

• 12、13 可以构成伙伴；
• 14、15 可以构成伙伴；
• 如果它们都空闲，就能合并成 4 页的大空闲块；
• 加入块组 2。

7. 伙伴堆的内部碎片问题

伙伴堆按 2 的整数次幂分配。

如果申请 17 页：

2^4 < 17 ≤ 2^5

系统会分配 32 页。

浪费：

32 - 17 = 15 页

这就是内部碎片。

解决方向：

本章核心

1. 分页与分段对比

2. 四种存储管理方式对比

易考题型

题型一：动态分区分配算法

给一组空闲区，再给一串申请和释放，让用 FF、NF、BF、WF 计算结果。

做题关键：

• First Fit：找第一个满足的；
• Next Fit：从上次位置后继续找；
• Best Fit：找最小满足的；
• Worst Fit：找最大满足的；
• 释放时相邻空闲区要合并。

题型二：页式地址转换

做题步骤：

1. 根据页面大小确定页内地址位数；
2. 把逻辑地址拆成页号 p 和页内地址 d；
3. 查页表得到页框号 f；
4. 物理地址 = f 和 d 拼接，或者 f × 页面大小 + d。

最重要口诀：

页内地址不变，页号换成页框号。

题型三：EAT 有效访问时间

单级页表常见公式：

EAT = α × (TLB时间 + 内存时间)
    + (1 - α) × (TLB时间 + 2 × 内存时间)

多级页表公式要根据未命中时访问几级页表来改。

例如四级页表：

EAT = α × (TLB时间 + 内存时间)
    + (1 - α) × (TLB时间 + 5 × 内存时间)

题型四：段式地址转换

做题步骤：

1. 拆出段号 s 和段内地址 d；
2. 判断 s 是否超过段表长度；
3. 查段表得到段首址和段长；
4. 判断 d 是否超过段长；
5. 如果合法，物理地址 = 段首址 + d。

注意段式有两次越界判断。

题型五：段页式地址转换

做题步骤：

1. 拆成 s, p, d；
2. 查段表，找到该段页表首址和页表长度；
3. 判断段号是否越界；
4. 判断页号是否越界；
5. 查页表得到页框号；
6. 物理地址 = f, d。

题型六：伙伴堆算法

做题步骤：

1. 申请 fn 页；
2. 找最小 $2^i$，使 $2^(i-1) < fn ≤ 2^i$；
3. 到第 i 组找空闲块；
4. 没有则向更大组找并拆分；
5. 释放时检查伙伴是否空闲；
6. 空闲则合并，继续向上合并。

口诀：

分配向上找，拆大成小；释放找伙伴，能合就合。

梳理

1. 存储管理五大功能：分配去配、共享、保护、扩充、地址映射。
2. 地址映射三种方式：固定、静态、动态。
3. 动态分区四种算法：FF、NF、BF、WF。
4. 碎片问题：分页有内部碎片，分段有外部碎片。
5. 界地址管理：base + limit，物理地址 = 基址 + 逻辑地址。
6. 分页管理：页号变页框号，页内地址不变。
7. TLB 和 EAT 计算：命中和未命中分别计算。
8. 多级页表：解决页表过大和连续空间需求问题。
9. 反置页表：面向物理页框，系统一张表。
10. 分段管理：便于共享和保护，但有外部碎片。
11. 段页式管理：先分段，段内分页，结合二者优点。
12. 伙伴堆算法：按 2 的幂分配，释放时按伙伴合并。

小结

主存管理就是操作系统在有限内存中，通过分配、回收、保护、共享和地址转换，让多个进程安全高效运行；其中分页解决连续分配问题，分段解决逻辑共享保护问题，段页式结合两者优点，而伙伴堆算法则用于高效管理连续物理页框。

虚拟存储管理

主线：外存如何管理 → 为什么需要虚拟存储 → 虚拟页式/段式/段页式如何实现 → 页面置换算法如何计算 → Linux 伙伴堆如何分配页框

总体框架

本章分为两大部分：

7.1 外存空间管理

讲外存如何划分、如何记录空闲块、进程在外存中如何存放。

7.2 虚拟存储系统

讲虚拟存储的基本思想，以及三种实现方式：

1. 虚拟页式存储管理
2. 虚拟段式存储管理
3. 虚拟段页式存储管理

后面还补充了 Linux 的 Buddy Heap 伙伴堆分配算法，这是管理内存空闲页框的一种方法。

7.1 外存空间管理

1. 外存空间的类型

文件中把外存空间分成几类：

1. Swap 空间：用于进程页面或段的换入换出。
2. File 空间：用于存放普通文件。
3. 输入井：用于输入缓冲。
4. 输出井：用于输出缓冲。

在虚拟存储系统中，外存不是单纯存文件，还承担了“临时放置暂时不在内存中的程序页/段”的作用。

2. 外存空间划分

外存空间通常被划分成固定大小的块，称为 block。

特点：

• 块是外存分配的基本单位。
• 块也是 I/O 传输的基本单位。
• 块大小通常是 2 的整数次幂。
• 如果实际需求不足一个块，会产生块内零头，但由于外存容量较大，通常可以忽略。

这里和内存页框类似：
内存按页框分配，外存按块分配。

3. 外存空闲空间管理方法

文件中提到三种外存空闲块管理方式。

方式一：空闲块链

把所有空闲块串成一个链表。

优点：结构简单。
缺点：查找较慢，尤其是需要连续空闲块时效率低。

方式二：空闲块表

把连续的空闲块记录为同一个表项。

例如：

优点：适合记录连续空闲区域。
缺点：表项可能增加，也需要维护合并和分裂。

方式三：字位映像图

用 1 个二进制位表示一个外存块的状态。

例如：

• 0 表示空闲
• 1 表示占用

优点：空间利用率高，适合快速判断某块是否空闲。
缺点：查找连续空闲块时可能需要扫描位图。

4. 进程和外存的对应关系

不同存储管理方式下，进程在外存中的组织方式不同。

1. 界地址方式

每个进程占一组连续外存块，或者占两组连续外存块。

这种方式比较简单，但不够灵活。

2. 页式方式

内存的一页对应外存的一块。

要求：

内存页大小 = 外存块大小

进程的页面可以分散存放在外存不同块中。

3. 段式方式

每个段在外存中占若干连续块。

一个进程有多个段，不同段之间可以不连续。

4. 段页式方式

段内再分页。

特点：

• 内存一页对应外存一块。
• 一个段内部的多个页对应的外存块可以不连续。
• 一个进程的多个段也可以分散在外存不同区域。

7.2 虚拟存储系统

1. 为什么需要虚拟存储？

如果没有虚拟存储，会有两个大问题：

问题一：不能运行比内存大的程序

如果程序大小超过物理内存，就无法全部装入内存运行。

问题二：进程全部装入内存会浪费空间

程序运行具有 局部性原理。

所谓局部性，就是：

在一段时间内，程序访问的代码和数据往往集中在一个较小的地址范围内。

例如，一个程序虽然有 1GB，但当前几秒钟可能只用其中几十 MB。

所以没有必要把整个程序一次性全部装入内存。

2. 虚拟存储的基本思想

虚拟存储的思想是：

程序运行时，只把当前必要的一小部分代码和数据装入内存，其余部分放在外存。当访问到不在内存中的部分时，再动态调入。如果内存不够，就淘汰暂时不用的部分。

一句话理解：

用外存扩展内存，让程序感觉自己拥有很大的内存空间。

3. 虚拟存储的目标

虚拟存储主要有四个目标：

1. 让大程序能在小内存中运行。
2. 让多个程序能在小内存中并发运行。
3. 让多个程序的地址空间互不冲突。
4. 提高内存利用率。

7.2.1 虚拟页式存储管理

虚拟页式存储管理是本章最重要的内容，也是考试最常考的部分。

1. 基本原理

进程运行前：

• 一部分页面装入内存。
• 另一部分页面装入外存。
• 甚至可以全部先放在外存，运行时再调入。

进程运行时：

• 如果访问的页在内存中，正常访问。
• 如果访问的页不在内存中，发生 缺页中断。

2. 缺页中断处理过程

缺页中断发生后，操作系统大致做这些事情：

1. 保存现场。
2. 根据页表找到所需页在外存中的位置。
3. 在内存中寻找空闲页框。
4. 如果有空闲页框，直接调入。
5. 如果没有空闲页框，根据页面置换算法选择一个页面淘汰。
6. 如果被淘汰页面被修改过，需要写回外存。
7. 把所需页面从外存读入内存。
8. 修改页表和快表。
9. 恢复现场。
10. 重新执行导致缺页中断的那条指令。

注意：
缺页中断不是错误，而是虚拟存储系统的正常机制。

3. 虚拟页式地址变换

逻辑地址形式为：

逻辑地址 = 页号 p + 页内位移 d

地址变换过程：

1. CPU 给出逻辑地址 (p, d)。
2. 先查快表 TLB。
3. 如果快表命中，得到页框号 f。
4. 物理地址 = (f, d)。
5. 如果快表未命中，查页表。
6. 如果页在内存中，得到页框号，更新快表。
7. 如果页不在内存中，发生缺页中断。
8. 缺页处理后，再重新执行地址变换。

还要注意越界检查：

• 如果页号 p 超出进程页表范围，发生越界中断。
• 如果访问权限不合法，发生越权中断。

4. 页表和快表的改进

普通页表需要增加一些字段：

快表中通常保存：

修改标志很重要，因为页面淘汰时：

• 如果没修改过，可以直接丢弃。
• 如果修改过，必须写回外存。

7.2.1.2 内存页框分配策略

在内存容量和进程数量确定时，需要决定每个进程分多少页框。

四种静态分配方法。

1. 平均分配

把所有物理页框平均分给进程。

例如：

内存 128 个页框，进程 25 个，则每个进程大约分 5 个页框。

优点：简单。
缺点：不考虑进程大小和优先级。

2. 按进程长度比例分配

设：

• 进程 pi 有 si 个页面。
• 所有进程页面总数为 S = Σsi。
• 内存共有 m 个页框。

则：

ai = (si / S) × m

ai 表示分给进程 pi 的页框数。

例如：

内存 62 个页框，两个进程：

• p1 有 127 页
• p2 有 10 页

则 p1 分得 57 个页框，p2 分得 5 个页框。

3. 按优先级比例分配

设进程 pi 的优先级为 ri，总优先级为：

S = Σri

则：

ai = (ri / S) × m

优先级越高，分到的页框越多。

4. 按长度和优先级综合分配

综合考虑页面数和优先级：

ai = ((si + ri) / S) × m

其中：

S = Σ(si + ri)

5. 静态分配策略的问题

这些方法都是静态的，缺点是没有反映：

1. 程序结构。
2. 程序在不同时刻的行为特性。

例如，一个程序虽然很大，但当前只频繁访问少量页面，那么给它太多页框可能浪费。

7.2.1.3 外存块分配策略

1. 静态分配

外存始终保存进程的全部页面。

即使某个页面被调入内存，它在外存中的副本也不释放。

优点：

• 速度快。
• 页面淘汰时，如果没有修改，可以不必写回。

缺点：

• 浪费外存。

2. 动态分配

外存只保存当前不在内存中的页面。

当某个外存页面被调入内存后，它原来占用的外存块释放。

优点：

• 节省外存空间。

缺点：

• 页面淘汰时通常必须写回外存，速度较慢。

7.2.1.4 页面调入时机

1. 请求调页 Demand Paging

当发生缺页中断时，才把所需页面调入内存。

优点：

• 不浪费调页。
• 只调真正需要的页。

缺点：

• 发生缺页时进程必须等待，影响执行速度。

2. 预调页 Prepaging

在页面真正被访问之前，提前调入。

依据通常是程序顺序执行特征。

优点：

• 可以减少缺页等待时间。

缺点：

• 预测不一定准确。
• 如果预调入的页后面没有用到，会浪费内存和 I/O。

注意：

预调页必须配合请求调页使用，因为预调不可能完全准确。

7.2.1.5 页面置换算法

页面置换算法用于决定：

当内存没有空闲页框时，应该淘汰哪个页面？

目标是：

尽可能降低页故障率。

页故障率公式：

f = F / A

其中：

• F 是页故障次数。
• A 是总访问次数。

1. 最佳置换算法 OPT

思想：

淘汰以后不再使用，或者最长时间以后才会再次使用的页面。

优点：

• 页故障率最低。
• 理论上最优。

缺点：

• 无法真正实现，因为操作系统无法准确知道未来页面访问序列。

考试中常用 OPT 作为比较标准。

2. FIFO 先进先出算法

思想：

淘汰最早进入内存的页面。

实现方式：

• 用队列维护页面进入内存的顺序。
• 队头是最早进入的页面。
• 淘汰队头页面。

优点：

• 简单。

缺点：

• 可能淘汰常用页面。
• 会出现 Belady 异常。

3. Belady 异常

Belady 异常指：

增加分配给进程的页框数，缺页次数反而可能增加。

文件中的例子说明：

访问序列：

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

FIFO 下：

• 3 个页框时，页故障率为 9/12。
• 4 个页框时，页故障率为 10/12。

页框更多，缺页反而更多，这就是 Belady 异常。

考试要记住：

FIFO 可能出现 Belady 异常，LRU 和 OPT 不会。

4. LRU 最近最少使用算法

思想：

淘汰最近最长时间没有被访问的页面。

依据：

如果一个页面很久没有被访问，未来短期内也可能不会被访问。

实现方法：

• 可以用栈。
• 每访问一个页面，就把它移到栈顶。
• 栈底页面就是最近最少使用页面。

优点：

• 性能通常较好。
• 符合局部性原理。

缺点：

• 实现开销大。
• 需要硬件支持。
• 如果完全靠软件实现，速度会严重下降。

5. NUR / NRU 最近不用算法

NUR，也叫 NRU，Not Used Recently。

思想：

淘汰最近一段时间没有使用过的页面。

每个页面增加两个硬件位：

每隔一段时间，把所有引用位清 0。

淘汰优先级如下：

1. r = 0, m = 0：最近没访问，也没修改，最好淘汰。
2. r = 0, m = 1：最近没访问，但修改过，淘汰前要写回。
3. r = 1, m = 0：最近访问过，但没修改。
4. r = 1, m = 1：最近访问过，也修改过，最不适合淘汰。

核心记忆：

优先淘汰没访问过的；在没访问过中，优先淘汰没修改过的。

6. LFU 最不经常使用算法

思想：

淘汰访问次数最少的页面。

实现：

• 每个页面设置计数器。
• 页面调入时计数器清 0。
• 每访问一次，计数器加 1。
• 淘汰计数器最小的页面。

缺点：

1. 前期访问很多、后期不用的页面可能难以淘汰。
2. 刚调入的页面计数少，可能马上被淘汰。

7. MFU 最频繁使用算法

思想与 LFU 相反：

淘汰访问次数最多的页面。

理由：

访问次数少的页面可能刚调入，未来可能还要使用；访问次数多的页面可能已经使用完了。

缺点：

• 有些页面确实会贯穿整个程序运行过程，频繁使用，不应该淘汰。
• 实现开销也很大。

8. 二次机会算法 Second Chance

思想：

FIFO 的改进版。先看最老页面，如果它最近被访问过，就给它第二次机会。

每个页面有引用位 r。

过程：

1. 检查最早进入内存的页面。
2. 如果 r = 0，淘汰。
3. 如果 r = 1，把 r 置 0，并把该页面移动到队尾。
4. 继续检查下一个页面。

一句话理解：

老页面不一定马上淘汰，如果最近访问过，就再给一次机会。

9. 时钟算法 Clock Algorithm

时钟算法是二次机会算法的环形实现。

页面组织成环形队列，有一个指针指向当前位置。

过程：

1. 从指针当前位置开始检查。
2. 如果当前页面 r = 0，淘汰它。
3. 如果当前页面 r = 1，把 r 清 0，指针顺时针移动。
4. 重复直到找到 r = 0 的页面。

考试记忆：

Clock 算法本质上是“环形二次机会算法”。

10. 改进的时钟算法

普通 Clock 只考虑引用位 r。
改进 Clock 同时考虑：

• 引用位 r
• 修改位 m

优先级：

1. r = 0, m = 0：最佳，直接淘汰。
2. r = 0, m = 1：次佳，淘汰前写回。
3. r = 1, m = 0：再次。
4. r = 1, m = 1：最差，淘汰前写回。

步骤：

1. 第一轮找 r = 0, m = 0，不修改 r 位。
2. 如果找不到，第二轮找 r = 0, m = 1，同时把扫描过的 r 清 0。
3. 如果还找不到，再重新执行第一轮和第二轮，此时一定能找到。

核心理解：

普通 Clock 尽量淘汰没访问过的页；改进 Clock 尽量淘汰没访问过且没修改过的页。

2010 年考研题讲解

题目给出：

• 虚拟页式系统。
• 进程空间和内存空间都是 64K。
• 页长 1K。
• 某进程 6 个页。
• 分配 4 个页框。
• 访问逻辑地址 13B7H。

因为页长 1K = 2¹⁰，所以：

• 低 10 位是页内地址。
• 高位是逻辑页号。

13B7H 对应的逻辑页号是 4。

4 号页不在内存，发生缺页中断。

FIFO 情况

FIFO 淘汰最早装入的页面。

题中最早装入的是第 5 页，对应页框号 3。

所以 4 号页调入页框 3。

物理地址为：

0FB7H

CLOCK 情况

Clock 算法从指针位置开始检查引用位。

根据题目给出的 Clock 结构，最终淘汰第 0 页，对应页框号 5。

所以物理地址为：

17B7H

这个题的考点是：

1. 根据页大小拆分逻辑地址。
2. 判断是否缺页。
3. 根据不同置换算法找被淘汰页。
4. 用页框号 + 页内位移形成物理地址。

7.2.1.6 颠簸 Thrashing

1. 什么是颠簸？

颠簸指：

页面在内存和外存之间频繁换入换出，系统大部分时间都在做换页，而不是执行程序。

现象：

• 缺页率很高。
• CPU 利用率下降。
• 系统响应变慢。

2. 颠簸的原因

文件中总结了三个原因：

1. 分给进程的物理页框太少。
2. 页面淘汰算法不合理。
3. 程序结构不好，局部性差。

3. 颠簸的处理方法

对应处理：

1. 增加分给进程的页框数。
2. 改进页面置换算法。
3. 改善程序结构，提高局部性。

4. 程序结构对缺页的影响

文件中用二维数组举例：

int a[1024][1024];

for(i = 0; i < 1024; i++)
    for(j = 0; j < 1024; j++)
        a[i][j] = 0;

和：

for(i = 0; i < 1024; i++)
    for(j = 0; j < 1024; j++)
        a[j][i] = 0;

在 C 语言中，二维数组按行连续存储。

所以：

• a[i][j] 按行访问，局部性好。
• a[j][i] 按列访问，可能频繁跨页，缺页率更高。

考试经常考这个思想：

程序访问顺序会影响缺页次数。

7.2.1.7 工作集模型

1. 工作集定义

工作集 Working Set 指：

进程在某一段时间内访问过的页面集合。

记作：

WS(t, Δ)

其中：

• t 是当前时刻。
• Δ 是窗口尺寸。
• WS(t, Δ) 表示从 t - Δ 到 t 这段时间内访问过的页面集合。

2. 工作集的意义

为了让程序有效运行：

进程的工作集应该能放入内存。

如果工作集放不进内存，就会频繁缺页，可能发生颠簸。

3. 工作集和窗口尺寸的关系

窗口 Δ 太小：

• 不能覆盖进程真正活跃的页面。
• 页故障率高。

窗口 Δ 太大：

• 包含太多暂时不用的页面。
• 浪费内存。

所以工作集大小与时间和窗口尺寸都有关。

4. 工作集实现方法

可以在页表中增加访问位。

过程：

1. 每个窗口开始时，把访问位全部清 0。
2. 页面被访问时，访问位置 1。
3. 窗口结束时，访问位为 1 的页面就是该窗口的工作集。

5. 工作集估计公式

文件给出估计公式：

τn+1 = αwn + (1 - α)τn

其中：

• wn 是第 n 个窗口的实际工作集大小。
• τn 是第 n 个窗口的估计工作集大小。
• α 是 0 到 1 之间的权重。

这个公式本质是“加权平均”：

• α 越大，越重视最近一次实际值。
• α 越小，越重视过去估计值。

7.2.1.8 页故障率反馈模型 PFFB

PFFB 全称：

Page Fault Feed Back

思想：

根据页故障率动态调整分给进程的页框数。

规则：

• 页故障率太高：说明页框太少，增加页框。
• 页故障率太低：说明页框可能太多，减少页框。

它比静态分配更灵活，因为它根据程序运行时行为调整内存分配。

7.2.1.11 非均匀存储器访问 NUMA

在单处理机系统中，访问所有内存的速度大致相同。

但在多处理机系统中，每个 CPU 可能有自己的局部存储器。

特点：

• 访问本 CPU 的局部内存较快。
• 访问其他 CPU 附近的非局部内存较慢。

这称为：

NUMA，Non-Uniform Memory Access，非均匀存储器访问。

调度和分配原则：

1. CPU 给进程分配页框时，尽量分配本 CPU 的局部内存。
2. CPU 空闲时，尽量调度上次在本 CPU 上运行过的进程。

原因是：

这个进程拥有的页面更可能位于该 CPU 的局部内存中。

页面大小的选择

页面大小不能太大，也不能太小。

页面太大

缺点：

• 页内碎片增大。
• 内存浪费。
• 极端情况下退化为分区存储。

页面太小

缺点：

• 页面数量变多。
• 页表长度增加。
• 页表本身占用更多内存。
• 换页更频繁，系统效率降低。

常见页面大小：

• 1KB
• 2KB
• 4KB

通常是 2 的整数次幂。

影响缺页次数的因素

文件总结了几个因素：

1. 页面置换算法
   算法越合理，缺页次数越少。
2. 分配给进程的页框数
   页框数越少，越容易缺页。
3. 页面大小
   页面太小，可能更容易缺页。
4. 程序编制方法
   局部性越好，越不容易缺页；跳转、分支越多，可能越容易缺页。

页式系统的不足

虚拟页式存储管理有三个主要不足：

1. 页面划分没有逻辑意义。
   页只是固定大小的块，不对应函数、模块、数组等逻辑单位。
2. 页的共享不灵活。
   程序共享通常以模块为单位，但页不一定刚好对应模块。
3. 存在页内碎片。
   一个页面最后可能没有完全用满。

7.2.2 虚拟段式存储系统

虚拟段式存储管理以“段”为单位。

段通常对应程序的逻辑单位，例如：

• 主程序段
• 子程序段
• 数据段
• 栈段
• 共享库段

1. 基本思想

进程运行前：

• 整个进程装入外存。
• 部分段装入内存。

进程运行时：

• 如果访问的段在内存中，正常访问。
• 如果访问的段不在内存中，发生 缺段中断。

如果内存空间不够，有两种办法：

1. 紧凑：移动内存中的段，把分散的空闲区合并。
2. 淘汰：把某个段移到外存。

2. 虚拟段式地址变换

逻辑地址形式：

(s, d)

其中：

• s 是段号。
• d 是段内位移。

地址变换过程：

1. CPU 给出逻辑地址 (s, d)。
2. 先查快表。
3. 如果快表命中，得到段内存首址 b' 和段长 l'。
4. 检查 d 是否小于段长。
5. 如果合法，物理地址 = b' + d。
6. 如果快表未命中，查段表。
7. 如果段不在内存，发生缺段中断。
8. 如果段号或段内位移越界，发生越界中断。

3. 段表字段

段表通常包括：

7.2.2.2 段的动态连接

这是虚拟段式存储管理的重要内容。

1. 静态连接

静态连接发生在程序运行前，由链接程序 link 完成。

特点：

• 程序运行前所有需要的段都确定。
• 每个段提前分配段号。
• 目标程序较大。
• 连接时间较长。
• 有些段可能根本不会执行，但也被连接进来了。

2. 动态连接

动态连接发生在程序运行时，由操作系统完成。

特点：

• 程序运行过程中，需要某个段时才连接。
• 一个程序到底会连接多少段，运行前不一定知道。
• 段名到段号的转换需要操作系统完成。

优点：

• 减少初始装入时间。
• 减少目标代码长度。
• 没用到的段可以不连接。

3. 动态连接的实现思想

系统维护几个数据结构：

每进程一个段名-段号对照表

记录当前进程已经连接的段。

每段一个符号表

记录符号名和段内位移。

例如：

4. 连接中断

编译时，如果遇到访问外段的指令，会采用间接寻址。

间接字中有一个连接标志 L：

• L = 1：未连接。
• L = 0：已连接。

执行时：

1. 遇到间接指令。
2. 如果 L = 1，说明外段尚未连接。
3. 发生连接中断。
4. 操作系统根据段名找到段。
5. 如果段已经连接过，取出段号。
6. 如果段没有连接过，从文件中读入，分配段号，填写段表和段名-段号表。
7. 根据符号表找到段内地址。
8. 把符号地址改成逻辑地址。
9. 把 L 置 0。
10. 重新执行指令。

5. 动态连接与共享的矛盾

动态连接需要修改连接字，也就是修改代码中的某些内容。

但是段共享通常要求代码是：

pure code，纯代码

纯代码不能被修改，否则多个进程共享时会相互影响。

解决方法：

• 把共享代码分为纯段和杂段。
• 纯段可以共享。
• 杂段每个进程私用。

7.2.3 虚拟段页式存储系统

虚拟段页式存储管理结合了页式和段式的优点。

1. 为什么需要段页式？

页式优点

• 存储分配简单。
• 没有外部碎片。

页式缺点

• 地址是一维的。
• 页面没有逻辑意义。
• 不方便动态连接和动态扩充。
• 共享和保护不够自然。

段式优点

• 段有逻辑意义。
• 地址是二维的。
• 方便共享和保护。
• 可以动态扩充。
• 可以动态连接。

段式缺点

• 存储分配复杂。
• 可能产生外部碎片。
• 需要紧凑。

段页式思想

段页式：

先分段，再把每个段分页。

这样：

• 对用户来说，看到的是段。
• 对内存分配来说，使用页。
• 既保留了段的逻辑意义，又保留了页的分配便利。

2. 段页式需要的数据结构

1. 段表

每个进程一个段表。

每连接一个新段，增加一个段表项。

段表包括：

• 页表长度
• 页表首址
• 访问权限
• 扩展标志
• 共享段入口

2. 页表

每段一个页表。

进程开始时，只为主程序段建立页表。
其他段的页表在段连接时建立。

页表包括：

• 页框号
• 外存块号
• 内外标志
• 修改标志

3. 总页表

内存和外存各一个，通常用位示图表示空闲/占用情况。

4. 共享段表

系统一个，记录所有共享段。

包括：

• 段名
• 页表长度
• 页表首址
• 扩充标志
• 共享计数

5. 段名-段号对照表

每个进程一个。

用于动态连接时，把段名转换为段号。

3. 段页式地址格式

逻辑地址形式：

(s, p, d)

其中：

• s 是段号。
• p 是段内页号。
• d 是页内位移。

地址映射为：

(s, p, d) → (f, d)

其中 f 是物理页框号。

4. 段页式地址变换过程

1. 根据 (s, p) 查快表。
2. 如果快表命中，得到页框号 f。
3. 检查访问权限。
4. 形成物理地址 (f, d)。
5. 如果快表未命中，先查段表。
6. 检查段号是否越界。
7. 根据段表找到该段的页表。
8. 检查页号是否越界。
9. 查页表，看该页是否在内存。
10. 如果不在内存，发生缺页中断。
11. 如果是间接地址且有障碍位，可能发生连接中断。
12. 更新快表。
13. 形成物理地址。

5. 段页式中断处理

1. 连接中断

分三种情况：

情况一：所有进程都没连接过该段

操作系统需要：

1. 查文件目录找到该段。
2. 为该段建立页表。
3. 从文件读入外存 swap。
4. 部分页读入内存。
5. 填写页表。
6. 分配段号。
7. 填写段名-段号表。
8. 如果是共享段，填写共享段表。
9. 填写段表。
10. 查符号表得到 (p, d)。

情况二：其他进程连接过，本进程没连接过

说明共享段表中已有该段，但本进程的段名-段号表中没有。

操作系统需要：

1. 给本进程分配段号。
2. 填写本进程段名-段号表。
3. 填写本进程段表。
4. 共享计数加 1。
5. 查符号表得到 (p, d)。

情况三：本进程已经连接过

直接查符号表，得到 (p, d)。

2. 缺页中断

处理方法：

1. 分配页框。
2. 调入所需页面。
3. 更新页表。
4. 更新总页表。

3. 越界中断

分两种：

段号越界

访问不存在的段，属于地址错误，程序终止。

页号越界

访问段内不存在的页。

此时要看段是否允许扩展：

• 如果允许扩展，增加页，修改页表和段表。
• 如果不允许扩展，地址错误，程序终止。

4. 越权中断

违反段的访问权限，例如只读段被写入。

结果：

程序终止。

6. 三种虚拟存储管理方式对比

重要结论：

分页对用户透明，分段对用户可见。

Linux 伙伴堆 Buddy Heap 分配算法

这是本章后半部分的重要补充内容。

1. 为什么需要伙伴堆？

Linux 中需要管理大量空闲页框。

有些场景需要连续的物理页框，例如 DMA 操作。

伙伴堆算法用于：

管理内存中的空闲页框，减少外部碎片，提高分配和释放效率。

2. 基本概念

页框

内存被划分成固定大小的页框，例如 4KB。

块组

Linux 把空闲页框按大小分组。

第 i 组保存大小为：

2^i 个连续页框

的空闲块。

例如：

同一组中的空闲块大小相同，并通过链表组织。

3. free_area 结构

每个 free_area[i] 包含：

1. 空闲块链表指针。
2. 块组位图指针。

空闲链表用于记录当前有哪些大小为 2^i 页的空闲块。

位图用于辅助判断伙伴块状态。

4. 什么是伙伴？

两个块是伙伴，需要满足三个条件：

1. 大小相同。
2. 物理地址连续。
3. 按页框编号计算，它们的位置满足伙伴对齐关系。

通俗理解：

一个大块被一分为二之后，这两个小块互为伙伴。

例如：

• 页框 0、1 和页框 2、3 可以是一对大小为 2 页的伙伴。
• 页框 0、1、2、3 和页框 4、5、6、7 可以是一对大小为 4 页的伙伴。

5. 分配过程

假设申请 fn 个页框。

第一步：找到最小的 2 的幂

找到满足：

2^(i-1) < fn ≤ 2^i

的 i。

也就是说，申请 fn 页时，至少要分配 2^i 页。

例如：

申请 3 页：

2^1 < 3 ≤ 2^2

所以要分配 4 页，从 free_area[2] 中分配。

第二步：查找对应块组

如果 free_area[i] 有空闲块，直接分配。

如果没有，就向更大的块组查找。

第三步：分裂大块

如果找到更大的块，比如 2^j 页，且 j > i，就把大块分裂。

例如申请 128 页：

• 应从第 7 组取，因为 2^7 = 128。
• 如果第 7 组没有空闲块，就找第 8 组。

• 如果第 8 组有 256 页块，则分成两个 128 页块：

  • 一个分配出去。
  • 另一个放回第 7 组。
• 如果第 8 组也没有，就找第 9 组，继续分裂。

6. 释放过程

释放 2^i 个页框时：

1. 找到它的伙伴块。
2. 如果伙伴块也是空闲的，就合并成更大的块。
3. 合并后的块继续尝试和自己的伙伴合并。
4. 直到不能合并为止。
5. 把最终得到的空闲块加入对应块组链表。
6. 修改位图。

分配时，大块不断拆小；释放时，小块尽量合大。

7. 伙伴堆的内部碎片问题

伙伴堆以 2 的幂为单位分配，会产生内部碎片。

例如申请 17 个页框：

因为：

2^4 < 17 ≤ 2^5

所以必须分配 32 个页框。

实际只需要 17 个，浪费了 15 个页框。

这就是内部碎片。

8. 解决方法

second memory allocator

当实际申请页框数小于分配块大小时，把剩余空间按 2 的幂继续切分，由第二级分配器管理。

third memory allocator

如果进程物理空间不要求连续，可以由第三级分配器完成更灵活的分配。

2015 年期末题思路

1. 页式系统地址转换。
2. 页表中引用位、修改位、内外标志的变化。
3. 空闲页框链表 head 的变化。
4. 页面调入和页面淘汰。

关键点：

• 页面大小 2KB = 2¹¹，所以逻辑地址低 11 位是页内偏移。
• 高位是页号。
• 如果访问页不在内存中，发生缺页中断。
• 如果进程还能分配页框，就从空闲页框链表取一个。
• 如果页框已达上限，就根据时钟算法淘汰页面。
• 修改后的页面如果被淘汰，需要写回外存。
• 页表中的引用位、修改位、内外标志要随访问变化。

易错点：

1. 页号和页内位移拆错。
2. 十六进制和二进制转换错。
3. 缺页后忘记重新执行指令。
4. 忘记更新引用位。
5. 写操作后忘记设置修改位。
6. 淘汰修改页时忘记写回。

章末作业涉及的考点

作业 1：伙伴堆算法

要求根据主存映像图写出：

1. free_area 各表项的空闲块链表。
2. 块组位图内容。
3. 申请 3 页后的内存映像图。
4. 分配后的伙伴堆数据结构。

考点：

• 会判断哪些页框空闲。
• 会判断哪些空闲页框能组成 1 页、2 页、4 页块。
• 会判断伙伴关系。
• 会根据申请页数向上取 2 的幂。
• 会更新链表和位图。

作业 2：页式地址转换

题目给出：

• 主存 10KB。
• 页面大小 1024B。
• J2 有 4 个页面，分别装入内存第 3、4、6、8 块。

要求：

1. 写出 J2 页表。
2. 计算 MOV 指令中两个操作数的物理地址。

考点：

• 页大小 1024B = 2¹⁰，所以低 10 位是页内位移。
• 逻辑地址除以 1024 得页号。
• 逻辑地址对 1024 取余得页内位移。
• 查页表得到物理块号。
• 物理地址 = 物理块号 × 页面大小 + 页内位移。

作业 3：请求分页 + TLB + LRU

题目涉及：

• 页表有效位。
• TLB 初始为空。
• 访问 TLB 时间 10ns。
• 访问内存时间 100ns。
• 缺页平均处理时间 10⁸ns。
• 驻留集大小固定为 2。
• LRU 局部淘汰。
• 虚地址访问序列：2362H、1565H、25A5H。

考点：

1. 地址拆分。
2. TLB 命中和未命中时间计算。
3. 页表访问。
4. 缺页中断处理。
5. 缺页后重新执行指令。
6. LRU 淘汰顺序。
7. 有效位变化。
8. 物理地址形成。

特别注意：

缺页处理后，导致缺页的那条指令要重新执行，所以时间计算通常包括缺页处理时间以及重新访问 TLB/页表/内存的时间。

考试重点

1. 缺页中断处理流程
   从访问页不在内存，到调入页面、更新页表、重新执行指令。
2. 逻辑地址到物理地址转换
   页式：页号 + 页内位移。
   段式：段号 + 段内位移。
   段页式：段号 + 页号 + 页内位移。
3. 页面置换算法
   OPT、FIFO、LRU、NUR、Second Chance、Clock、改进 Clock。
4. Belady 异常
   FIFO 可能出现，页框数增加缺页次数反而增加。
5. Clock 算法和改进 Clock 算法计算
   这是考试非常常见的题型。

6. 工作集模型和 PFFB
   都是为了防止颠簸，但思路不同：

   • 工作集：根据最近访问页面集合分配页框。
   • PFFB：根据缺页率动态调整页框数。
7. 颠簸原因和解决方法
   页框少、算法差、程序局部性差。
8. 页式、段式、段页式对比
   表格题、简答题常考。
9. 动态连接
   理解连接中断、段名-段号表、符号表、连接字 L。
10. 伙伴堆算法
    会按 2 的幂分配和合并，会判断内部碎片。

总结

虚拟存储利用局部性原理，只把当前需要的页或段放入内存；当访问内容不在内存时，通过缺页或缺段中断调入；内存不够时用置换算法淘汰页面；为了避免频繁换入换出的颠簸，需要合理分配页框、选择置换算法，并利用工作集或缺页率反馈模型动态调整；页式简单但逻辑性差，段式逻辑性强但分配复杂，段页式结合二者优点；Linux 伙伴堆则用 2 的幂大小管理连续空闲页框。

文件系统

主线： 文件系统 = 操作系统把“用户看到的文件名、目录、读写操作”转换成“磁盘上的块、inode/FCB、缓冲区、I/O 操作”的机制。

用户关心“文件名和操作”，系统关心“空间分配、目录查找、权限、安全、效率”。

一、8.1 文件与文件系统

1. 什么是文件？

具有符号名，并且在逻辑上具有完整意义的信息项序列。

文件不是一堆杂乱数据，而是操作系统管理的一段有名字、有属性、有结构的数据。

文件内部有一个读写指针，表示当前读写位置。例如打开一个文件后，连续 read() 会从上一次读到的位置继续读。

2. 什么是文件系统？

文件系统是：

文件 + 管理文件的程序集合。

它的目标分两个角度：

文件系统的主要功能包括：按名存取、目录维护、文件查找定位、外存空间分配、提供访问方式、共享保护保密、提供文件操作命令、统一设备接口等。

3. 文件分类

常见分类方式：

UNIX 中常见三类文件：