考频地图
这一章值得花整个 OS 复习时间的 40%。其中 PV 大题是 408 公认的难点,但它有固定套路,练 10 道左右就能上手。
| 考点 | 考频 | 题型 | 必须会的动作 |
|---|---|---|---|
| 进程状态转换 | ★★★★☆ | 选择 | 判断哪种转换可能、由什么事件引起 |
| 进程与线程的区别 | ★★★★☆ | 选择 | 知道线程共享什么、私有什么 |
| 调度算法 | ★★★★★ | 选择 / 计算 | 画甘特图,算周转、带权周转、等待时间 |
| 临界区与软硬件互斥方法 | ★★★☆☆ | 选择 | 判断某段代码违反了哪条准则 |
| 信号量与 PV 操作 | ★★★★★ | 选择 / 综合大题 | 按四步法写出同步互斥伪代码 |
| 死锁与银行家算法 | ★★★★★ | 选择 / 计算 | 求 Need、找安全序列、判断请求能否满足 |
进程:概念、状态与控制
程序是一本菜谱:静静放在书架(磁盘)上。进程是“照着菜谱做菜”这件事:要占用厨房(内存)、灶台(CPU)、锅碗(资源),有开始、有中断(等水开)、有结束。
同一本菜谱可以同时被三个厨师照着做——一个程序可以对应多个进程。
一、进程是什么
进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位(引入线程后,调度单位变成线程)。为了让 OS 能管理它,每个进程都配有一个“档案袋”——进程控制块 PCB。
| 对比 | 程序 | 进程 |
|---|---|---|
| 本质 | 静态的指令集合,存放在磁盘 | 动态的执行过程,有生命周期 |
| 组成 | 代码 + 数据 | PCB + 程序段 + 数据段 |
| 对应关系 | 一个程序可以对应多个进程(同一个程序运行多次);一个进程也可以执行多个程序(如 exec 换掉代码) | |
| 特征 | — | 动态性(最基本)、并发性、独立性、异步性、结构性 |
二、五状态模型(必背图)
一个进程从生到死,会在下面几种状态之间转换。三种基本状态是就绪、运行、阻塞,再加上“创建”和“终止”两个过渡状态:
| 状态 | 它在等什么 | 放在哪 | 单 CPU 下数量 |
|---|---|---|---|
| 运行态 | 什么都不等,正在 CPU 上执行 | CPU 上 | 最多 1 个 |
| 就绪态 | 只等 CPU | 就绪队列 | 可以多个 |
| 阻塞态(等待态) | 等某个事件:I/O 完成、资源、信号量 | 阻塞队列(常按原因分多个) | 可以多个 |
| 创建态 | 正在建 PCB、分配资源,还没进就绪队列 | — | — |
| 终止态 | 正在回收资源、撤销 PCB | — | — |
- 运行 → 阻塞是进程自己主动的(如调用了 read);阻塞 → 就绪是被动的(I/O 中断处理程序把它唤醒)。
- 单 CPU 中若没有进程在运行,就绪队列一定为空吗?不一定——可能所有进程都在阻塞,CPU 运行闲逛进程(idle)。
- 进程被唤醒(阻塞 → 就绪)后不会立刻运行,要等调度。
- 时间片用完是运行 → 就绪,不是运行 → 阻塞。
补充:在内存紧张时,OS 会把一些进程整个换到外存,这叫挂起,于是又多出“就绪挂起”和“阻塞挂起”两种状态(七状态模型)。挂起与阻塞的区别:阻塞是在等事件,进程映像还在内存;挂起是映像被调到了外存。
三、进程控制:用“原语”完成
创建、终止、阻塞、唤醒、切换这几件事都会修改 PCB 和各种队列,必须一气呵成,不能做到一半被打断,所以用原语(用“关中断 → 执行 → 开中断”实现的不可分割的程序段)实现,且在内核态执行。
| 原语 | 做了什么 | 什么时候发生 |
|---|---|---|
| 创建 | 申请空白 PCB → 分配资源(内存不够则等待) → 初始化 PCB → 插入就绪队列 | 用户登录、作业调度、系统提供服务、应用请求(fork) |
| 终止 | 找到 PCB → 若在运行则剥夺 CPU → 终止所有子孙进程 → 归还资源 → 删除 PCB | 正常结束、异常结束(越界、非法指令)、外界干预(kill) |
| 阻塞(block) | 找到 PCB → 保护现场 → 状态改为阻塞 → 插入对应阻塞队列 | 请求资源失败、等待 I/O、等待合作进程 |
| 唤醒(wakeup) | 在阻塞队列中找到 PCB → 移出 → 状态改为就绪 → 插入就绪队列 | 等待的事件发生;由别的进程调用 |
进程切换 vs 模式切换
进程切换是 CPU 从一个进程换到另一个进程:保存旧进程上下文到 PCB → 更新 PCB 状态、移到相应队列 → 选新进程 → 更新内存管理数据结构(换页表) → 恢复新进程上下文。它一定在内核态完成。
模式切换只是用户态 ↔ 内核态,可能还是同一个进程(如做个系统调用又回来了)。所以:进程切换一定有模式切换,模式切换不一定有进程切换。
四、进程通信(IPC)
各进程的地址空间相互独立,A 不能直接读 B 的变量。要交换数据,需要 OS 提供的通信机制:
- 管道是半双工的:要双向通信得建两根管道。管道只能先进先出,数据读走就没了。
- 共享存储中,OS 只负责提供共享区,互斥访问靠进程自己用同步工具(如 PV)实现。
- PCB 不能被用户进程直接访问,只有内核能改。
线程与多线程模型
进程切换很“贵”:要换页表、刷 TLB、换一大堆资源。可很多时候我们只是想让同一个程序里的几件事并发进行(比如浏览器一边下载一边渲染),没必要每件事都开一个进程。于是有了线程——同一进程内的多个“执行流”,共享进程的资源,各自只保留执行所需的最少东西。
一、引入线程后,进程和线程分工
| 维度 | 进程 | 线程 |
|---|---|---|
| 身份 | 资源分配的基本单位 | CPU 调度的基本单位 |
| 拥有资源 | 拥有独立的地址空间和资源 | 基本不拥有资源,共享所属进程的 |
| 切换开销 | 大(要切换地址空间) | 同进程内线程切换开销小;跨进程的线程切换仍会引起进程切换 |
| 通信 | 需要 IPC | 同进程线程直接读写全局变量(但要同步) |
| 并发性 | 进程间可并发 | 同进程的多个线程也可并发,多核上可并行 |
二、用户级线程 vs 内核级线程
| 对比 | 用户级线程(ULT) | 内核级线程(KLT) |
|---|---|---|
| 谁来管理 | 用户空间的线程库,内核意识不到线程存在 | 内核,每个线程都有内核数据结构 |
| 切换 | 不需进内核态,快 | 需进内核态,较慢 |
| 一个线程阻塞 | 整个进程都被阻塞(内核只看到进程) | 只阻塞该线程,同进程其他线程继续 |
| 多核并行 | 不能,一个进程只能占一个 CPU | 能,多个线程可同时在多个 CPU 上 |
| 调度单位 | 内核调度的仍是进程 | 内核调度的是线程 |
三、三种多线程模型
- 同一进程的线程共享:代码、全局变量、堆、打开的文件;不共享:栈、寄存器(含 PC)。
- “线程是资源分配的单位”是错的,资源仍然分给进程。
- 用户级线程的“阻塞”会阻塞整个进程,这是它最大的缺点,也是选择题最爱考的点。
处理机调度
就绪队列里有好几个进程都在等 CPU,先给谁?这就是调度。不同的选人规则(算法)会让平均等待时间、响应速度、公平性差别很大。
一、三级调度
二、什么时候调度、什么时候不能调度
- 当前进程运行结束或被终止
- 当前进程阻塞(等 I/O、P 操作失败)
- 时间片用完(抢占式)
- 有更高优先级进程进入就绪队列(抢占式)
- 中断/系统调用处理完、返回用户态之前(检查是否需要重新调度)
- 处理中断的过程中
- 进程在操作系统内核临界区中(如正在改就绪队列)
- 其他需要完全屏蔽中断的原子操作过程中(原语)
注意:进程在普通临界区(如访问打印机)时可以被调度走。
调度方式:非抢占式(一旦分到 CPU 就一直跑到完成或阻塞)与抢占式(OS 可以在时间片到或更高优先级进程到来时剥夺 CPU)。闲逛进程(idle):没有其他就绪进程时运行它,优先级最低,能耗低,不需要 CPU 之外的资源,不会阻塞。
三、评价指标——计算题就算这几个
四、六种调度算法,一个例子算到底
统一用这四个进程(时间单位任意)。优先数越小,优先级越高:
| 进程 | 到达时间 | 服务时间 | 优先数 |
|---|---|---|---|
| P1 | 0 | 7 | 3 |
| P2 | 2 | 4 | 1 |
| P3 | 4 | 1 | 4 |
| P4 | 5 | 4 | 2 |
① 先来先服务 FCFS(非抢占)
谁先到谁先跑,跑完为止。最简单,对长作业有利、对短作业不利(短作业可能排在长作业后面苦等)。
② 短作业优先 SJF(非抢占)
每次 CPU 空出来时,从已到达的进程中选服务时间最短的。手算过程:
③ 最短剩余时间优先 SRTF(抢占式 SJF)
每当有新进程到达,就比较“新进程的服务时间”和“当前进程的剩余时间”,谁短谁跑:
| 进程 | FCFS 完成 / 周转 | SJF 完成 / 周转 | SRTF 完成 / 周转 |
|---|---|---|---|
| P1(到 0,服务 7) | 7 / 7 | 7 / 7 | 16 / 16 |
| P2(到 2,服务 4) | 11 / 9 | 12 / 10 | 7 / 5 |
| P3(到 4,服务 1) | 12 / 8 | 8 / 4 | 5 / 1 |
| P4(到 5,服务 4) | 16 / 11 | 16 / 11 | 11 / 6 |
| 平均周转 | 35 / 4 = 8.75 | 32 / 4 = 8 | 28 / 4 = 7 |
④ 高响应比优先 HRRN(非抢占)
每次调度时算一遍所有就绪进程的响应比,选最大的。等得越久 R 越大,短作业 R 涨得快——兼顾了短作业和长作业,不会饥饿。本例时刻 7:P2 = (5+4)/4 = 2.25,P3 = (3+1)/1 = 4,P4 = (2+4)/4 = 1.5,选 P3;时刻 8:P2 = (6+4)/4 = 2.5,P4 = (3+4)/4 = 1.75,选 P2。
⑤ 优先级调度
按优先级选。分非抢占/抢占两种;优先级又分静态(创建时定死)和动态(随等待时间等调整)。通常:系统进程 > 用户进程,交互型 > 非交互型,I/O 型 > 计算型(让 I/O 设备尽早忙起来)。
⑥ 时间片轮转 RR(抢占)
就绪队列按 FCFS 排好,每个进程最多跑一个时间片 q,没跑完就排到队尾。专为分时系统设计。约定:时间片用完的进程和同一时刻新到达的进程,新到达的先入队。
- q 太大 → 每个进程都能在一个时间片内跑完,退化为 FCFS;
- q 太小 → 切换太频繁,开销大,CPU 真正干活的比例下降。
⑦ 多级反馈队列(MLFQ)
| 算法 | 抢占? | 会饥饿? | 优点 | 缺点 / 适用 |
|---|---|---|---|---|
| FCFS | 非抢占 | 不会 | 公平、简单 | 对短作业不利;对 CPU 繁忙型有利 |
| SJF / SPF | 默认非抢占 | 会(长作业) | 平均等待/周转时间最短 | 要预知运行时间,难实现 |
| SRTF | 抢占 | 会 | 平均等待时间更短 | 同上 |
| HRRN | 非抢占 | 不会 | 兼顾长短作业 | 每次都要算响应比 |
| 优先级 | 都可 | 会(静态优先级) | 区分轻重缓急,适合实时 | 可用“老化”(等越久优先级越高)缓解饥饿 |
| RR | 抢占 | 不会 | 公平,响应快,适合分时 | 切换开销;不区分紧急程度 |
| 多级反馈队列 | 抢占 | 会(持续有新短进程时) | 综合最好,无需预知运行时间 | 实现复杂 |
- SJF 选的是已经到达的进程中最短的,还没到的不参与。
- 带权周转时间 = 周转时间 / 运行时间,不是除以等待时间。
- 有 I/O 的题目里,等待时间 ≠ 周转 − 运行,要按甘特图一段段数。
- “HRRN 是抢占式的”是错的,它通常是非抢占的。
同步与互斥原理
并发进程因为异步性,推进速度不可预知。如果它们共享数据,最后结果可能取决于“谁碰巧先执行到哪一步”——这叫竞争条件。同步互斥就是给它们立规矩。
一、为什么会出错:看一个 count++
两个进程都对共享变量 count(初值 5)执行一次 count++,期望结果是 7。但 count++ 在机器层面是三条指令:
| 时刻 | 进程 A | 进程 B | 寄存器 / 内存 |
|---|---|---|---|
| 1 | load R1, count | A.R1 = 5 | |
| 2 | add R1, 1 | A.R1 = 6 | |
| 3 | (时间片到,被切走) | load R1, count | B.R1 = 5(count 还是 5!) |
| 4 | add R1, 1 ; store | count = 6 | |
| 5 | store count, R1 | count = 6(B 的修改被覆盖) |
问题出在:A 还没把结果写回,B 就读了旧值。访问共享变量的那段代码必须“一次只许一个进程进入”。
二、基本概念
临界资源:一次只允许一个进程使用的资源(打印机、共享变量、缓冲区)。
临界区:进程中访问临界资源的那段代码。
do {
entry section; // 进入区:检查能否进入,上锁
critical section; // 临界区
exit section; // 退出区:解锁
remainder section; // 剩余区
} while (true);
互斥(间接制约):两个进程抢同一个临界资源,谁先都行,但不能同时。如两个进程都要用打印机。
同步(直接制约):两个进程合作完成任务,有先后次序要求。如 A 往缓冲区写数据,B 必须等 A 写了才能读。
三、临界区的四条准则
| 准则 | 含义 | 违反时的现象 |
|---|---|---|
| 空闲让进 | 临界区没人时,想进的应该能进 | 没人用却进不去 |
| 忙则等待 | 已有进程在里面,其他想进的必须等 | 两个进程同时进入(互斥失败) |
| 有限等待 | 等待的进程要在有限时间内进入 | 饥饿 / 无限等待 |
| 让权等待 | 进不去时应释放 CPU,不要“忙等” | while 循环空转占用 CPU(原则上应该遵循,但非必须) |
四、软件实现:从三次失败到 Peterson
选择题常给一段代码,问它违反了哪条准则。按下面的顺序理解,每种方法都在修上一种的毛病:
// P0 while (turn != 0); critical section; turn = 1; // P1 while (turn != 1); critical section; turn = 0;
只能 P0、P1 严格轮流进入。P0 用完把 turn 给 P1,若 P1 一直不来,P0 想再进也进不去 → 违反空闲让进。
// P0 while (flag[1]); // ① flag[0] = true; // ② critical section; flag[0] = false; // P1 while (flag[0]); // ③ flag[1] = true; // ④ critical section; flag[1] = false;
若按 ①③②④ 执行,两人都看到对方没举手,都进去了 → 违反忙则等待。原因:“检查”和“上锁”不是一气呵成的。
// P0 flag[0] = true; // ① while (flag[1]); // ② critical section; flag[0] = false; // P1 flag[1] = true; // ③ while (flag[0]); // ④ critical section; flag[1] = false;
按 ①③②④ 执行,两人都举了手,都在等对方放下 → 都进不去,违反空闲让进和有限等待(会“饥饿”)。
// Pi(j 是另一个进程) flag[i] = true; // 我想进 turn = j; // 但先让你 while (flag[j] && turn == j); critical section; flag[i] = false;
两人同时想进时,最后写 turn 的人谦让成功,另一个进去。满足空闲让进、忙则等待、有限等待,但仍是 while 忙等 → 不满足让权等待。
五、硬件实现
| 方法 | 原理 | 缺点 |
|---|---|---|
| 中断屏蔽 | 进临界区前关中断,出来再开;关中断后不会发生进程切换 | 只适用于单处理机;关中断是特权指令,只适合内核进程 |
| TestAndSet(TS/TSL) | 用一条硬件原子指令“读出旧值并设为 true”:while (TestAndSet(&lock)); | 不满足让权等待(忙等) |
| Swap(XCHG) | 原子地交换 lock 和局部变量 old,效果与 TSL 相同 | 不满足让权等待 |
硬件方法的共同点:把“检查 + 上锁”合成一个不可打断的原子操作,解决了双标志法的根源问题;适用于多处理机。基于它们实现的互斥锁(自旋锁)也是忙等的,适合等待时间很短、多处理机的场景。
六、信号量:能让权等待的同步工具
信号量就是停车场门口的“剩余车位”牌。P 操作(wait,申请)= 开进去,牌子减 1;如果减完小于 0,说明没车位了,就在门口排队睡觉(阻塞,让出 CPU)。V 操作(signal,释放)= 开出来,牌子加 1;如果加完 ≤ 0,说明还有人在排队,叫醒一个。
typedef struct { int value; // 资源数 struct process *L; // 等待队列 } semaphore; void wait(semaphore S) { // P 操作 S.value--; if (S.value < 0) { 把当前进程加入 S.L; block(S.L); // 自我阻塞,让出 CPU —— 满足“让权等待” } } void signal(semaphore S) { // V 操作 S.value++; if (S.value <= 0) { // 说明还有进程在等 从 S.L 中移出一个进程 P; wakeup(P); // 阻塞 → 就绪 } }
| S.value 的值 | 含义 |
|---|---|
| S.value > 0 | 还有 S.value 个资源可用 |
| S.value = 0 | 资源刚好用完,没人在等 |
| S.value < 0 | 资源用完,且有 |S.value| 个进程在等待队列中 |
早期的整型信号量只有一个整数,wait 里是 while (S <= 0);,会忙等,不满足让权等待。现在说“信号量”默认指上面的记录型信号量。
七、信号量的三种基本用法
mutex = 1; P(mutex); ...临界区 V(mutex);
初值 1;P、V 成对出现在同一个进程里,夹住临界区。
S = 0; // A: x; V(S); // B: P(S); y;
初值 0。“前操作之后 V,后操作之前 P”;P、V 分在两个进程里。
S = n; P(S); // 申请 ...用资源 V(S); // 归还
初值 = 资源总数,如 3 台打印机就设 3。
前驱关系:每条边一个信号量
八、管程:把 PV 封装起来
PV 操作散落在各个进程里,写错一个顺序就死锁。管程把共享数据和对它的操作封装在一起,由编译器保证每次只有一个进程能进入管程(互斥自动实现),程序员只需用条件变量处理同步。
monitor ProducerConsumer { condition full, empty; // 条件变量 int count = 0; // 缓冲区中产品数 void insert(Item item) { if (count == N) full.wait(); // 满了,阻塞在 full 上 count++; 放入 item; if (count == 1) empty.signal(); // 之前是空的,唤醒消费者 } Item remove() { if (count == 0) empty.wait(); count--; 取出 item; if (count == N - 1) full.signal(); return item; } }
| 对比 | 信号量 | 管程的条件变量 |
|---|---|---|
| 有没有值 | 有值,表示资源数 | 没有值,只有一个等待队列 |
| V / signal 时没人在等 | 值加 1,“记住”了这次 V | signal 不起任何作用,被丢弃 |
| wait 时 | 值 ≤ 0 才阻塞 | 调用 wait 一定阻塞,并释放管程 |
- 信号量的值只能通过 P、V 和初始化来改变,不能直接赋值。
- Peterson 和 TSL 都不满足让权等待;记录型信号量满足。
- 同步的 P、V 在不同进程中;互斥的 P、V 在同一进程中。
- 管程中同一时刻只能有一个进程在执行管程内的过程,但可以有多个进程在管程的条件队列中等待。
PV 经典问题与大题套路
真题 PV 大题几乎都是下面五个模型的变形。先学会一个通用的四步法,再把五个模型看成“例题”,考场上就是识别模型 + 套用。
一、四步解题法
- 找进程:题目里有几类“主动干活的角色”,每类写一个进程,用自然语言写出它循环做的事(如“生产一个产品 → 放入缓冲区”)。
- 找关系:逐对检查——谁和谁不能同时做某事(互斥)?谁必须等谁做完某事(同步)?
- 设信号量:互斥 → 一个初值为 1 的 mutex;同步 → 看“需要等的东西”初始有多少个(缓冲区空位初值 n,产品初值 0)。
- 插 PV 并检查顺序:在“用之前”P、“做完之后”V。最后检查:同步的 P 必须放在互斥的 P 之前,否则可能死锁。
二、生产者-消费者(最核心)
semaphore mutex = 1; // 互斥访问缓冲区 semaphore empty = n; // 空闲缓冲区数 semaphore full = 0; // 产品数
producer() {
while (1) {
生产一个产品;
P(empty); // ① 同步:有空位吗
P(mutex); // ② 互斥
放入缓冲区;
V(mutex);
V(full); // 多了一个产品
}
}
consumer() {
while (1) {
P(full); // ① 同步:有产品吗
P(mutex); // ② 互斥
从缓冲区取出产品;
V(mutex);
V(empty); // 多了一个空位
消费产品;
}
}
- 为什么 P(empty) 必须在 P(mutex) 前?假设缓冲区已满,生产者先 P(mutex) 成功拿到锁,再 P(empty) 被阻塞——它抱着锁睡着了。消费者来了 P(mutex) 也阻塞,再没人能腾出空位 → 死锁。
- 两个 V 的顺序可以交换,V 不会导致阻塞。
- “生产一个产品”“消费产品”这种不碰缓冲区的操作,不要放进 P(mutex)…V(mutex) 中,否则降低并发度(不算错,但会扣分)。
三、多生产者-多消费者(水果盘)
桌上一个盘子,只能放一个水果。爸爸放苹果,妈妈放橘子;儿子只吃橘子,女儿只吃苹果。
分析:盘子是“容量为 1 的缓冲区”;女儿等苹果、儿子等橘子、爸妈等盘子空。
semaphore plate = 1, apple = 0, orange = 0; dad() { while(1){ 准备苹果; P(plate); 放苹果; V(apple); } } mom() { while(1){ 准备橘子; P(plate); 放橘子; V(orange); } } daughter() { while(1){ P(apple); 取苹果; V(plate); 吃苹果; } } son() { while(1){ P(orange); 取橘子; V(plate); 吃橘子; } }
为什么这里没有 mutex?因为缓冲区容量是 1,plate、apple、orange 三者之和最多为 1,任一时刻最多一个进程能通过 P 进入“访问盘子”的代码,天然互斥。若盘子容量 ≥ 2,就必须加 mutex。
四、读者-写者
多个读者可以同时读;写者必须独占(写-写互斥、读-写互斥)。难点在“第一个读者进来时锁住写者、最后一个读者离开时放开写者”,需要一个计数器 count,而 count 本身也要互斥访问。
int count = 0; semaphore rw = 1; // 读写/写写互斥 semaphore mutex = 1; // 保护 count writer() { while(1) { P(rw); 写; V(rw); } } reader() { while(1) { P(mutex); if (count == 0) P(rw); // 第一个读者锁写者 count++; V(mutex); 读; P(mutex); count--; if (count == 0) V(rw); // 最后一个放行 V(mutex); } }
int count = 0; semaphore rw = 1, mutex = 1; semaphore w = 1; // 实现“先来先服务” writer() { while(1) { P(w); P(rw); 写; V(rw); V(w); } } reader() { while(1) { P(w); P(mutex); if (count == 0) P(rw); count++; V(mutex); V(w); 读; P(mutex); count--; if (count == 0) V(rw); V(mutex); } }
左边的问题:只要源源不断有读者,count 永远不为 0,写者一直等。右边的 w 像一个“排队入口”,写者一旦排上,后来的读者就被挡在 w 外面。
五、哲学家进餐
semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1; // 方法③:拿筷子的动作互斥
Pi() {
while (1) {
P(mutex);
P(chopstick[i]);
P(chopstick[(i+1)%5]);
V(mutex);
吃饭;
V(chopstick[i]);
V(chopstick[(i+1)%5]);
思考;
}
}
六、吸烟者(一个生产者,轮流供应多种产品)
三个吸烟者分别有烟草、纸、胶水之一;供应者每次放两种材料到桌上,缺这两种的那个吸烟者拿走卷烟抽,抽完通知供应者再放下一组。
semaphore offer1 = 0, offer2 = 0, offer3 = 0; // 三种材料组合 semaphore finish = 0; // 抽完了 int i = 0; provider() { while (1) { if (i == 0) { 放组合一; V(offer1); } else if (i == 1) { 放组合二; V(offer2); } else { 放组合三; V(offer3); } i = (i + 1) % 3; P(finish); } } smoker1() { while(1){ P(offer1); 拿走组合一,卷烟,抽; V(finish); } } // smoker2、smoker3 同理
| 模型 | 识别特征 | 关键信号量 |
|---|---|---|
| 生产者-消费者 | 有缓冲区,一方放一方取 | empty = n, full = 0, mutex = 1 |
| 多生产多消费 | 不同产品对应不同消费者 | 每种产品一个同步信号量 + 容量信号量 |
| 读者-写者 | 一类可以共享、一类必须独占 | rw、mutex、计数器 count |
| 哲学家 | 每个进程要同时拿多个资源 | 资源数组 + 防死锁措施 |
| 吸烟者 | 一个生产者轮流给不同的人 | 每类一个 offer + finish |
答题格式建议:先写“信号量定义 + 初值 + 含义注释”,再用 Process_X() { while(1) { … } } 写每类进程。注释写清楚每个 P/V 的作用,阅卷时能拿过程分。如果题目问“为什么这样设计/能否交换顺序”,用上面生产者-消费者的死锁分析来答。
死锁
一座单行窄桥,两辆车从两头同时开上来,在中间顶住了:谁都不肯退(不可剥夺),各自占着半座桥(请求并保持),又都在等对方让出另一半(循环等待),而桥一次只能过一辆(互斥)。四个条件同时满足,于是谁也走不了。
一、定义与四个必要条件
死锁:多个进程因竞争资源而互相等待,若无外力作用,这些进程都将无法向前推进。四个条件必须同时满足才会死锁,破坏任意一个就不会:
| 必要条件 | 含义 | 能否破坏 / 怎么破坏(预防) |
|---|---|---|
| 互斥 | 资源一次只能给一个进程用 | 一般不能破坏(有些资源本质就互斥);SPOOLing 能把独占设备改造成共享设备 |
| 不可剥夺 | 资源在用完前不能被强行拿走 | 申请新资源得不到时,释放已有的全部资源;或按优先级强行剥夺。代价:之前的工作可能作废 |
| 请求并保持 | 拿着已有的,又去申请新的 | 一次性分配(运行前申请所有资源)。代价:资源浪费,可能饥饿 |
| 循环等待 | 存在进程-资源的循环等待链 | 顺序资源分配法:给资源编号,必须按编号递增申请。代价:编号难定,用的顺序与编号不一致时浪费 |
与之相关的两个概念:饥饿是某个进程长期得不到服务(可能只有一个进程处于饥饿,且它可能处在就绪态);死循环是程序逻辑 bug。死锁至少涉及两个进程,且都处于阻塞态。
二、资源分配图:一眼看出有没有死锁
化简资源分配图:找一个既不阻塞(请求都能满足)又不孤立的进程,假设它运行完,删掉它的所有边(归还资源);重复。死锁定理:系统处于死锁状态 ⟺ 资源分配图不可完全简化。结论:无环一定不死锁;有环且每类资源只有一个实例一定死锁;有环但资源有多个实例不一定死锁。
三、四种处理策略
| 策略 | 时机 | 做法 | 特点 |
|---|---|---|---|
| 预防 | 事前,静态 | 破坏四个必要条件之一(见上表) | 限制严格,资源利用率低,实现简单 |
| 避免 | 分配时,动态 | 每次分配前判断:分了以后系统是否仍安全(银行家算法) | 需事先知道各进程最大需求 |
| 检测与解除 | 事后 | 允许死锁发生,定期化简资源分配图检测;发现后剥夺资源 / 撤销进程 / 进程回退 | 不限制分配,资源利用率高 |
| 忽略(鸵鸟) | — | 假装死锁不会发生 | 通用 OS 常用,代价最小 |
四、安全状态与银行家算法
安全状态:系统能找到一个进程推进顺序 <Pa, Pb, …>(安全序列),按这个顺序给每个进程分配它还需要的全部资源,大家都能顺利完成。
四个数据结构(n 个进程,m 类资源)
安全性算法(找安全序列)
- 令
Work = Available,所有进程Finish = false。 - 找一个
Finish = false且Need ≤ Work(每一类都不超过)的进程;找不到就转第 4 步。 - 假设它运行完、归还资源:
Work = Work + Allocation,Finish = true,回到第 2 步。 - 若所有进程
Finish = true则安全,按选中的顺序就是安全序列;否则不安全。
资源请求算法(进程 Pi 申请 Request)
- 若
Request ≤ Need[i],转下一步;否则出错(要的超过了自己声明的最大需求)。 - 若
Request ≤ Available,转下一步;否则资源不够,Pi 等待。 - 试分配:
Available −= Request;Allocation[i] += Request;Need[i] −= Request。 - 对试分配后的状态执行安全性算法:安全则正式分配;不安全则撤销试分配,Pi 等待。
例题(教材经典数据)
5 个进程,A、B、C 三类资源,T0 时刻 Available = (3, 3, 2):
| 进程 | Max | Allocation | Need = Max − Alloc |
|---|---|---|---|
| P0 | 7 5 3 | 0 1 0 | 7 4 3 |
| P1 | 3 2 2 | 2 0 0 | 1 2 2 |
| P2 | 9 0 2 | 3 0 2 | 6 0 0 |
| P3 | 2 2 2 | 2 1 1 | 0 1 1 |
| P4 | 4 3 3 | 0 0 2 | 4 3 1 |
得到安全序列 <P1, P3, P0, P2, P4>,系统安全。(安全序列可能不唯一,如 <P1, P3, P4, P2, P0> 也对。检验:最后的 Work 一定等于系统资源总数。)
五、一个常考的小公式
思路:最坏情况是每个进程都拿到 k − 1 个、差 1 个,大家互相等。此时只要再多 1 个资源,就有一个进程能完成并释放全部 k 个资源,其他进程随之推进。
例:3 个进程,每个最多要 4 台打印机,至少需要 3 × 3 + 1 = 10 台才保证不死锁。
- 不安全 ≠ 死锁。不安全只表示“有可能死锁”。
- 银行家算法是死锁避免,不是预防;它不破坏任何必要条件。
- Request > Need 是出错;Request > Available 是等待。不要搞反。
- 死锁检测算法和安全性算法很像,区别是检测时用的是当前的请求 Request,而不是 Need。
- 撤销进程解除死锁时,优先撤销代价小的(优先级低、已运行时间短、占资源少的)。
真题与自测
一、真题问法
问法 1(状态):“下列选项中,导致进程从运行态变为就绪态的事件是:A. 执行 P(wait) 操作 B. 申请内存失败 C. 启动 I/O 设备 D. 被高优先级进程抢占。”→ A、B、C 都是运行 → 阻塞,选 D。
问法 2(线程):“同一进程中的线程不能共享的是:A. 进程代码段 B. 进程打开的文件 C. 进程的全局变量 D. 线程的栈指针。”→ D。
问法 3(调度):给出 3–5 个作业的到达时间和运行时间,求某算法下的平均周转/带权周转时间。→ 先画甘特图,再列表算,最后求平均。
问法 4(PV 大题):给一个现实场景(面包店、银行叫号、多线程计算、缓冲区搬运),要求用信号量实现。→ 四步法,识别为生产者-消费者 / 读者-写者等模型的变形。
问法 5(死锁):给出 Max、Allocation、Available,问是否安全、某请求能否满足。→ 先算 Need,再走安全性算法,写出完整的 Work 表格。
二、折叠自测
1. 为什么“阻塞 → 运行”的转换不可能发生?
阻塞进程等的事件发生后只会被唤醒到就绪队列,是否运行要由调度程序决定。调度程序只从就绪队列里挑进程,不会直接从阻塞队列挑。
2. 用户级线程中的一个线程执行了阻塞的系统调用,会怎样?
整个进程都被阻塞。因为内核根本不知道线程的存在,它看到的是“这个进程发起了阻塞调用”,于是把整个进程挂起,同进程的其他用户级线程也没法运行。
3. 三个作业到达时间都是 0,运行时间分别为 2、5、3,单 CPU 用 SJF。平均周转时间是多少?
顺序 2 → 3 → 5,完成时间 2、5、10,周转时间 2、5、10,平均 17/3 ≈ 5.67。
4. 时间片轮转中时间片无限大,会退化成什么算法?
先来先服务 FCFS。每个进程都能在一个时间片内运行完,等价于按到达顺序依次运行到结束。
5. Peterson 算法满足让权等待吗?为什么?
不满足。进不去的进程在 while (flag[j] && turn == j); 中空转,一直占着 CPU(忙等),而不是阻塞让出 CPU。
6. 信号量 S 当前值为 −3,说明什么?
资源已经用完,并且有 3 个进程正在 S 的等待队列中阻塞。
7. 生产者中把 P(empty) 和 P(mutex) 交换会怎样?
缓冲区满时,生产者先拿到 mutex 再在 P(empty) 上阻塞,抱着锁睡着;消费者 P(mutex) 也阻塞,没人能腾出空位,也没人能释放 mutex,形成死锁。
8. 系统有 5 台同类设备,k 个进程每个最多需要 2 台。k 最大为多少时一定不会死锁?
要 5 ≥ k(2−1)+1,即 k ≤ 4。k 最大为 4。
9. 银行家算法中,某进程 Request ≤ Need 且 Request ≤ Available,就一定能分配吗?
不一定。还要试分配后做安全性检查:只有分配后系统仍处于安全状态才真正分配,否则撤销试分配,进程等待。
10. 不安全状态一定会发生死锁吗?
不一定。不安全状态只是不能保证所有进程都能完成。进程实际可能不会用到它声明的最大需求,或者有进程中途释放资源,系统仍可能不死锁。
三、考前速览
PCB 是进程存在的唯一标志。
进程分资源,线程被调度。
周转 = 完成 − 到达;带权周转 = 周转 ÷ 运行。
同步 P 在前,互斥 P 在后。
安全不死锁,不安全不一定死锁。
① 阻塞 → 运行、就绪 → 阻塞不存在。
② 用户级线程阻塞会阻塞整个进程。
③ 普通临界区中可以进程调度。
④ Peterson、TSL 不满足让权等待。
⑤ Request > Need 出错,> Available 等待。