【笔记】操作系统第二章-进程管理

操作系统第二章：进程管理 · 完整复习笔记

考研提示：本章是操作系统最重要的一章，每年必考，综合题高频。重点掌握：进程状态转换、CPU调度算法（含计算）、信号量实现同步互斥、死锁的银行家算法。

---

第一部分：进程与线程

1.1 进程的基本概念

进程是什么？

进程（Process）是程序的一次执行过程，是系统进行资源分配和调度的基本单位（注意：引入线程后，调度的基本单位变为线程）。

进程 vs 程序（高频考点）

对比项	程序	进程
本质	静态的代码文件（存在磁盘上）	动态的执行过程（在内存中运行）
存在性	永久存在	有创建→运行→消亡的生命周期
对应关系	一个程序可以对应多个进程	一个进程只对应一个程序
资源	不占用资源	占用CPU、内存、文件等资源

进程控制块 PCB（Process Control Block）

PCB是进程存在的唯一标志，操作系统通过PCB管理进程。PCB中记录：

• 进程标识符（PID）：区分不同进程
• 处理机状态：寄存器值，用于上下文切换
• 进程调度信息：优先级、状态等
• 进程控制信息：程序计数器、内存地址、I/O设备等

---

1.2 进程的状态与转换（必须会画图）

进程有五种基本状态（部分教材用三种，408考三种+变体）：

                    ┌──────────────────────────────────────────┐
                    │           进程状态转换图                    │
                    └──────────────────────────────────────────┘

                         ①进程创建
                              ↓
                          【新建态】
                              │ ②被OS允许进入内存
                              ↓
  ④等待的事件发生   ←←←← 【就绪态】 ←←←←←←← ⑤时间片用完/被抢占
  (I/O完成/信号到达)        ↓  ↑                    ↑
                         ③被调度   ⑤              ⑤
                              ↓                    │
                          【运行态】 →→→→→→→→→→→→→→→┘
                              │
                         ⑥等待事件（如I/O请求）
                              ↓
                          【阻塞态（等待态）】
                              │
                         ⑦进程结束
                              ↓
                          【终止态】

五种状态详解：

状态	含义	何时进入
新建态	进程刚被创建，OS还没完全接受	fork()刚执行
就绪态	万事俱备，只等CPU	创建完成、I/O结束、时间片到
运行态	正在占用CPU执行	调度器选中，分配CPU
阻塞态（等待态）	等待某事件（I/O、信号等），此时即使给CPU也不能运行	主动请求I/O、等待资源
终止态	进程执行完毕，等待OS回收资源	main()结束、exit()调用

转换条件记忆（重要！）：

• 就绪 → 运行：调度程序选中（被调度）
• 运行 → 就绪：时间片用完，或被更高优先级进程抢占
• 运行 → 阻塞：进程主动等待（I/O请求、等信号量为0）
• 阻塞 → 就绪：等待的事件发生（I/O完成、信号量变正）
• ⚠️注意：阻塞不能直接→运行！必须先到就绪！

记忆口诀：就绪←→运行双向走，运行→阻塞单向走，阻塞→就绪单向走。

---

1.3 线程的基本概念

为什么要引入线程？

进程切换开销太大（需要切换地址空间、寄存器等），线程是在进程内部的”轻量级执行流”，同一进程的线程共享地址空间，切换开销小。

线程 vs 进程（高频对比）

对比项	进程	线程
资源	资源分配基本单位	不独立拥有资源（共享进程资源）
调度	引入线程前是调度单位	现在的调度基本单位
开销	创建/切换开销大	创建/切换开销小
地址空间	进程间相互独立	同进程的线程共享地址空间
通信	进程间通信较复杂（IPC）	线程间通信简单（共享内存）

线程独有的东西（各线程私有）：

• 线程ID、程序计数器PC、寄存器组
• 栈（局部变量在栈上）

线程共享的东西（同进程所有线程共享）：

• 代码段、数据段（全局变量）、堆
• 打开的文件、信号处理

---

1.4 线程的实现方式

① 用户级线程（ULT，User-Level Thread）

线程由用户空间的线程库管理，OS不知道线程的存在。

• 优点：切换快（不需要内核介入），可在不支持线程的OS上运行
• 缺点：一个线程发生I/O阻塞 → 整个进程阻塞（OS只看到进程，不知道进程内有其他线程可运行）；无法利用多核CPU

② 内核级线程（KLT，Kernel-Level Thread）

线程由OS内核管理，OS知道每个线程。

• 优点：一个线程阻塞不影响其他线程；可利用多核并行
• 缺点：线程切换需要用户态↔内核态转换，开销大

③ 混合实现（多对多模型）

用户线程和内核线程多对多映射，结合两者优点（了解即可）。

---

1.5 进程间通信（IPC）

进程间地址空间相互独立，需要特殊机制通信。

① 共享内存（Shared Memory）

• 原理：多个进程映射同一块物理内存，直接读写
• 特点：速度最快，但需要同步机制（信号量）防止冲突
• 考点：共享内存本身不提供同步，需要配合信号量使用

② 消息传递（Message Passing）

• 原理：进程通过OS提供的send/receive原语传递消息
• 分类：
  • 直接通信：send(P, msg) 直接发给进程P
  • 间接通信：通过邮箱（信箱）中转
• 特点：适合分布式系统，有内核介入，速度比共享内存慢

③ 管道（Pipe）

• 原理：一个进程写入，另一个进程读出（像水管）
• 特点：
  • 半双工（单向，或用两个管道实现双向）
  • 无名管道：只能在有亲缘关系（父子进程）间使用
  • 有名管道（FIFO）：可在无亲缘关系进程间使用
• 数据：字节流，先进先出

④ 信号（Signal）

• 原理：OS向进程发送异步通知（如SIGKILL、SIGTERM）
• 特点：只能传递信号量（数字），不能传递数据内容
• 场景：中断处理、进程控制

---

第二部分：CPU调度与上下文切换

2.1 调度的基本概念

什么是调度？

当多个进程竞争CPU时，OS决定让哪个进程先用CPU、用多久，这就是调度。

调度层次（三级调度）：

调度层次	别名	作用	频率
高级调度	作业调度/长程调度	决定把哪个作业从磁盘调入内存（新建→就绪）	最低
中级调度	内存调度/中程调度	决定把哪个进程换出/换入内存（挂起机制）	中等
低级调度	进程调度/短程调度	决定就绪队列中哪个进程占用CPU	最高（最频繁）

408考试主要考低级调度（进程调度）。

---

2.2 调度的目标（评价指标）

这些指标用于评判一个调度算法的好坏：

指标	含义	期望
CPU利用率	CPU忙的时间 / 总时间	越高越好
吞吐量	单位时间内完成的进程数	越高越好
周转时间	作业提交到完成的总时间	越小越好
等待时间	进程在就绪队列等待的时间	越小越好
响应时间	提交请求到第一次响应的时间（交互系统重要）	越小越好

重要公式（必须掌握）：

$\text{周转时间}=\text{完成时间}-\text{到达时间}$

$\text{等待时间}=\text{周转时间}-\text{运行时间（服务时间）}$

$\text{带权周转时间}=\frac{\text{周转时间}}{\text{运行时间}}$

$\text{平均周转时间}=\frac{\sum \text{各进程周转时间}}{n}$

其中：

• n：进程总数
• 完成时间：进程执行完毕退出CPU的时刻
• 到达时间：进程进入就绪队列的时刻
• 运行时间（服务时间）：进程实际需要在CPU上运行的时间

带权周转时间 ≥ 1，值越小说明等待相对运行时间越少，用户体验越好。

---

2.3 调度算法（重点！必须掌握计算）

① 先来先服务（FCFS）

规则：按进程到达就绪队列的先后顺序分配CPU，先来的先服务。

特点：

• 非抢占式
• 有利于长进程，不利于短进程（短进程被长进程排在后面苦等）
• 不利于I/O密集型进程
• 实现最简单

例题：

进程	到达时间	运行时间
P1	0	7
P2	2	4
P3	4	1

执行顺序：P1(0-7) → P2(7-11) → P3(11-12)

进程	完成时间	周转时间	等待时间
P1	7	7-0=7	7-7=0
P2	11	11-2=9	9-4=5
P3	12	12-4=8	8-1=7

平均周转时间 = (7+9+8)/3 = 8

---

② 短作业优先（SJF / SPN）

规则：从就绪队列中选运行时间最短的进程优先执行。

特点：

• 默认非抢占式（非抢占SJF）；有抢占版本叫最短剩余时间优先（SRTF）
• 平均等待时间最短（在非抢占中对给定进程集合最优）
• 缺点：长进程可能”饥饿”（一直有短进程插队，长进程永远等）
• 实际难以准确预知运行时间

例题（非抢占SJF）（用上面同样的数据）：

t=0：只有P1到达，必须选P1，P1运行(0-7) t=7：P2和P3都到达了，P3运行时间1<P2运行时间4，选P3(7-8) t=8：选P2(8-12)

进程	完成时间	周转时间	等待时间
P1	7	7	0
P3	8	8-4=4	4-1=3
P2	12	12-2=10	10-4=6

平均周转时间 = (7+4+10)/3 ≈ 7 （比FCFS的8小）

---

③ 优先级调度

规则：每个进程有优先级数，选优先级最高（数值看规定是大还是小代表高）的执行。

抢占式 vs 非抢占式：

• 非抢占：当前进程不主动让出CPU就不换人
• 抢占式：新到达的高优先级进程可立即抢占CPU

问题：低优先级进程可能饥饿（Starvation）

解决方案（老化技术/Aging）：随着进程等待时间增加，动态提高其优先级

---

④ 轮转调度（Round Robin，RR）

规则：按时间片（Time Quantum/Time Slice）轮流给每个进程分配CPU，时间片用完则切换到下一个进程。

特点：

• 抢占式
• 专为分时系统设计，对所有进程公平
• 响应时间好
• 时间片大小的选择至关重要：
  • 时间片太大 → 退化为FCFS
  • 时间片太小 → 上下文切换开销占比过大，CPU效率下降

例题（时间片q=2）：

进程	到达时间	运行时间
P1	0	5
P2	1	3
P3	2	1

执行甘特图（就绪队列按到达顺序排）：

P1(0-2) → P2(2-4) → P3(4-5) → P1(5-7) → P2(7-8) → P1(8-9)

进程	完成时间	周转时间	等待时间
P1	9	9-0=9	9-5=4
P2	8	8-1=7	7-3=4
P3	5	5-2=3	3-1=2

---

⑤ 多级反馈队列（MFQ）

规则：设置多个优先级不同的就绪队列，时间片依次增大：

1. 新进程进入最高优先级队列（时间片最小）
2. 如果在时间片内没运行完，降级到下一个队列
3. 最低级队列采用FCFS

特点：

• 综合了SJF和RR的优点
• 短进程在高优先级队列很快完成，长进程逐渐下沉
• 408最常考的综合调度算法
• 兼顾了响应时间（短进程快速完成）和公平性

---

2.4 调度方式：抢占式 vs 非抢占式

	非抢占式（Non-preemptive）	抢占式（Preemptive）
含义	进程一旦获得CPU，只有自愿放弃（运行完/I/O/等待）才切换	高优先级进程可以强制抢走低优先级进程的CPU
响应性	差	好
适用	批处理系统	分时/实时系统
开销	小	大（频繁切换）

调度时机（什么时候可以调度）：

• 进程主动放弃CPU（I/O请求、wait()、exit()）
• 时间片用完
• 高优先级进程到达（仅抢占式）
• 注意：在中断处理程序、临界区中不应该进行进程调度

---

2.5 上下文切换（Context Switch）

什么是上下文？

进程运行时的”现场”：CPU寄存器（PC程序计数器、PSW程序状态字、通用寄存器）、栈指针等。

切换过程：

1. 保存当前进程的上下文到其PCB
2. 从新进程的PCB中恢复其上下文
3. 切换到新进程运行

开销：上下文切换是纯粹的额外开销（切换期间什么有用的事都没做），时间片越短，切换越频繁，系统有效工作时间越少。

---

第三部分：同步与互斥（最重要！）

3.1 基本概念

临界资源：每次只允许一个进程访问的资源（如打印机、共享变量）

临界区（Critical Section）：访问临界资源的那段代码

互斥（Mutual Exclusion）：任何时刻，只允许一个进程在临界区中执行

同步（Synchronization）：多个进程需要按一定顺序执行（如生产者先生产，消费者才能消费）

口诀：互斥是”同一时刻只能一个”；同步是”要有先后顺序”。

临界区的四个原则（必须背）：

1. 空闲让进：临界区空闲，有进程要进就让它进
2. 忙则等待：临界区有进程，其他进程必须等
3. 有限等待：进程等待进入临界区的时间必须有限（不能永远等）
4. 让权等待：进程等待时，应主动放弃CPU（不能忙等）

---

3.2 信号量（Semaphore）——最核心考点！

信号量是什么？

信号量是一个整数变量，只能通过P操作和V操作来访问（原子操作）。

P操作（wait，荷兰语Proberen=测试）：

P(S):
    S = S - 1
    if S < 0:
        阻塞该进程（加入等待队列）

V操作（signal，荷兰语Verhogen=增加）：

V(S):
    S = S + 1
    if S <= 0:
        唤醒等待队列中的一个进程

关键理解：

• S的初始值代表可用资源数
• S < 0时，|S|代表正在等待的进程数
• P操作：申请资源（可能阻塞）；V操作：释放资源（可能唤醒）

两类信号量：

• 互斥信号量：初始值=1，用于实现互斥（mutex）
• 同步信号量：初始值=0，用于实现同步（表示”事件尚未发生”）

互斥的信号量实现：

mutex = 1   // 初始化为1，表示资源空闲

进程Pi:
    P(mutex)    // 申请进入临界区
    临界区代码
    V(mutex)    // 退出临界区

---

3.3 经典同步问题（大题高频！）

问题一：生产者-消费者问题

场景：生产者生产数据放入缓冲区，消费者从缓冲区取数据。缓冲区大小为n。

分析：

• 互斥：同时只能有一个进程访问缓冲区（mutex=1）
• 同步1：缓冲区满时，生产者等待（消费者消费后唤醒）
• 同步2：缓冲区空时，消费者等待（生产者生产后唤醒）

信号量设置：

mutex = 1    // 互斥信号量，保护缓冲区（初始值=1）
empty = n    // 同步信号量，表示空缓冲区数量（初始值=n，缓冲区全空）
full  = 0    // 同步信号量，表示满缓冲区数量（初始值=0，缓冲区无产品）

伪代码：

生产者进程:
    while(True):
        生产一个产品
        P(empty)    // 申请一个空位（空位-1，若空位为0则等待）
        P(mutex)    // 申请进入临界区
        将产品放入缓冲区
        V(mutex)    // 退出临界区
        V(full)     // 通知消费者，满缓冲区+1

消费者进程:
    while(True):
        P(full)     // 申请一个产品（满位-1，若无产品则等待）
        P(mutex)    // 申请进入临界区
        从缓冲区取出产品
        V(mutex)    // 退出临界区
        V(empty)    // 通知生产者，空缓冲区+1
        消费产品

⚠️注意（易错！）：P(empty)和P(mutex)的顺序不能颠倒！

若先P(mutex)再P(empty)：生产者拿到mutex但empty=0被阻塞，此时没有释放mutex，消费者要P(mutex)也被阻塞，死锁！

规则：同步P操作必须在互斥P操作之前。

---

问题二：读者-写者问题

场景：多个读者可以同时读，但写者访问时必须独占（写时不能读，读时不能写，写写互斥）。

分析：

• 写者与任何人互斥
• 读者之间不互斥
• 需要记录当前读者数量

信号量设置：

rw = 1        // 互斥信号量，保护写操作（也保护读者计数）
mutex = 1     // 互斥信号量，保护readCount变量
readCount = 0 // 记录当前正在读的读者数量

伪代码（读者优先）：

读者进程:
    P(mutex)               // 保护readCount
    readCount++
    if readCount == 1:     // 第一个读者到来，阻止写者
        P(rw)
    V(mutex)
    
    读取数据
    
    P(mutex)               // 保护readCount
    readCount--
    if readCount == 0:     // 最后一个读者离开，允许写者
        V(rw)
    V(mutex)

写者进程:
    P(rw)       // 独占访问
    写数据
    V(rw)

理解：第一个读者来时”挡住”写者（P(rw)），最后一个读者离开时”放行”写者（V(rw)）。

问题：上面的实现是读者优先——只要有读者在读，后来的写者就要一直等，写者可能饥饿。

---

问题三：哲学家进餐问题

场景：5个哲学家围坐，每人左右各一根筷子（共5根），吃饭需要拿起左右两根筷子。

问题：如果5人同时拿起左边筷子，都在等右边，死锁！

解决方案：

1. 最多允许4人同时尝试拿筷子（设信号量room=4）
2. 奇数号哲学家先拿左边，偶数号先拿右边（破坏循环等待）
3. 一次性拿起两根（加互斥锁，要么同时拿，要么不拿）

方案3代码（推荐）：

mutex = 1         // 保护"拿筷子"这个动作
chopstick[5] = {1,1,1,1,1}  // 每根筷子的信号量

哲学家i:
    while(True):
        思考
        P(mutex)            // 确保拿筷子的动作是原子的
        P(chopstick[i])     // 拿左边筷子
        P(chopstick[(i+1)%5])  // 拿右边筷子
        V(mutex)
        吃饭
        V(chopstick[i])     // 放下左边筷子
        V(chopstick[(i+1)%5])  // 放下右边筷子

---

3.4 硬件同步机制

① 中断屏蔽（关中断）

关闭中断 → 执行临界区 → 开中断，防止切换。

• 缺点：仅适用于单核CPU，且不能给用户程序用（危险！）

② 硬件指令（Test-and-Set / Swap）

TestAndSet（TSL）原子指令：

bool TestAndSet(bool *lock):
    bool old = *lock
    *lock = True  // 原子地将lock置为True
    return old

// 使用：
while TestAndSet(&lock):  // 等待（忙等，自旋锁）
    pass                  // 忙等中
临界区代码
lock = False

• 问题：忙等待（Busy Waiting/Spin Lock）——进程等待时一直占CPU，浪费资源
• 适用：等待时间极短（如多核CPU的内核保护）

---

第四部分：死锁

4.1 死锁的基本概念

死锁定义：多个进程互相等待对方释放资源，导致所有进程都无法继续执行的状态。

四个必要条件（缺一不可，记”互持不循”）：

条件	含义
互斥条件	资源只能被一个进程占用（不可共享）
持有并等待（请求保持）	进程持有至少一个资源，又在等待其他被占用的资源
不可抢占（不可剥夺）	进程持有的资源不能被强制剥夺，只能自愿释放
循环等待	存在进程链P1→P2→…→Pn→P1，每个进程等待下一个进程持有的资源

注意：这四个条件是死锁的必要条件，不是充分条件（满足四个条件未必一定死锁，如资源数量足够时）。

---

4.2 处理死锁的策略

三种主要策略：

策略	方法	思路
死锁预防	破坏四个必要条件之一	事先限制，保守
死锁避免	动态检查，只有安全才分配	运行时谨慎分配
死锁检测+解除	允许死锁发生，检测后解除	事后处理

---

4.3 死锁预防

方法：破坏死锁的四个必要条件之一。

破坏哪个条件	方法	缺点
互斥条件	使资源可共享（如只读文件）	很多资源本来就不可共享，难以实现
持有并等待	要求进程一次性申请所有资源（静态分配）	资源利用率低，可能饥饿
不可抢占	允许抢占资源（高优先级可抢低优先级的资源）	适用范围窄，可能导致进程前功尽弃
循环等待	对资源编号，按序申请	编号不灵活，限制程序设计

最常考：破坏”持有并等待”（一次性申请）和”循环等待”（资源有序分配）。

---

4.4 死锁避免——银行家算法（必考！）

核心思想：分配资源前，先”假装”分配，看系统是否还处于安全状态，若安全才真正分配，否则让进程等待。

安全状态：存在一个安全序列，按这个顺序执行所有进程，每个进程都能获得所需资源并完成。

算法涉及的数据结构（n个进程，m种资源）：

变量	大小	含义
Available[m]	向量	每种资源当前可用数量
Max[n][m]	矩阵	每个进程对每种资源的最大需求量
Allocation[n][m]	矩阵	每个进程已分配到的各资源数量
Need[n][m]	矩阵	每个进程还需要的各资源数量

$\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j]$

安全性检查算法（判断当前状态是否安全）：

① 设 Work = Available（工作向量，初始等于当前可用资源）
   设 Finish[n] = {False}（是否能完成，初始都为False）

② 找一个满足以下条件的进程i：
   - Finish[i] == False（还未完成）
   - Need[i] <= Work（所需资源都能满足）
   
③ 若找到：
   Work = Work + Allocation[i]（进程i运行完，归还资源）
   Finish[i] = True
   回到②继续找
   
④ 若所有进程Finish[i]=True：安全状态，安全序列就是执行顺序
   否则：不安全状态！

资源请求算法（判断能否满足进程Pi的请求Request[i]）：

① 若 Request[i] <= Need[i]，继续；否则出错（超过最大需求）

② 若 Request[i] <= Available，继续；否则等待（资源不足）

③ 试探分配：
   Available = Available - Request[i]
   Allocation[i] = Allocation[i] + Request[i]
   Need[i] = Need[i] - Request[i]

④ 运行安全性算法，若安全则真正分配；否则回滚，让进程等待

完整例题（银行家算法）：

系统有3种资源A、B、C，数量分别为10、5、7。 当前状态：

进程	Max(A,B,C)	Allocation(A,B,C)	Need(A,B,C)	Available
P0	7,5,3	0,1,0	7,4,3	3,3,2
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

第一步：求Need矩阵：Need = Max - Allocation（已在表中）

第二步：安全性检查：Work=(3,3,2)

步骤	选进程	Need	Work足够？	Work执行后
1	P1	(1,2,2)	(3,3,2)≥(1,2,2) ✓	(3,3,2)+(2,0,0)=(5,3,2)
2	P3	(0,1,1)	(5,3,2)≥(0,1,1) ✓	(5,3,2)+(2,1,1)=(7,4,3)
3	P4	(4,3,1)	(7,4,3)≥(4,3,1) ✓	(7,4,3)+(0,0,2)=(7,4,5)
4	P2	(6,0,0)	(7,4,5)≥(6,0,0) ✓	(7,4,5)+(3,0,2)=(10,4,7)
5	P0	(7,4,3)	(10,4,7)≥(7,4,3) ✓	完成

安全序列：P1→P3→P4→P2→P0，系统处于安全状态。

---

4.5 死锁检测与解除

死锁检测：资源分配图（Resource Allocation Graph，RAG）

• 进程→资源：请求边
• 资源→进程：分配边
• 化简方法：找能满足需求的进程，删除其所有边，反复化简；若最终图不为空，则存在死锁

死锁解除方法：

方法	说明	缺点
终止进程	终止一个或多个死锁进程，释放资源	可能损失大量计算工作
资源抢占	强制剥夺某进程的资源给其他进程	被剥夺进程可能需要回滚

选择牺牲进程的原则：

• 进程已执行时间少、剩余工作多（损失少）
• 占用的资源多（解除效果好）
• 优先级低

---

第五部分：高频易错与综合总结

5.1 进程相关易错点

易错点	正确说法
进程是调度单位	引入线程后，线程才是调度单位，进程是资源分配单位
阻塞态可以直接变运行态	阻塞→就绪→运行，不能跳过就绪
进程切换就是上下文切换	上下文切换必然引起进程切换，但进程切换（如I/O完成）未必立即进行上下文切换
线程切换不需要切换地址空间	同进程的线程切换不需要，不同进程的线程切换需要

5.2 调度算法易错点

易错点	正确说法
SJF平均等待时间最短	SJF对给定进程集合的平均等待时间最短，但不公平，有饥饿问题
RR时间片越小越好	时间片太小，切换开销占比增大，效率反而下降
带权周转时间越大越好	带权周转时间越小越好（表示等待时间相对运行时间的比例小）

5.3 信号量易错点

易错点	正确说法
P操作增加信号量	P操作减少信号量（申请资源）；V操作增加（释放资源）
互斥信号量初始值任意	互斥信号量初始值=1
同步信号量初始值=1	同步信号量初始值通常=0（表示事件未发生）
生产者-消费者先P(mutex)再P(empty)	必须先P同步信号量，再P互斥信号量，否则死锁

5.4 死锁易错点

易错点	正确说法
四个条件充分满足必然死锁	四个条件是必要条件，充分满足未必死锁
死锁避免不分配资源	死锁避免是动态分配，安全则分配，不安全则等待
安全状态=不会死锁	安全状态确保不会死锁；不安全状态可能死锁（不一定）

5.5 考研大题答题模板

信号量题目答题步骤：

1. 分析有哪些临界资源
2. 确定哪些进程需要互斥（资源竞争）
3. 确定哪些进程需要同步（顺序依赖）
4. 为每个互斥关系设互斥信号量（初值=1），每个同步关系设同步信号量（初值=0或资源数）
5. 在对应位置写P/V操作

银行家算法题目步骤：

1. 求Need矩阵（Need = Max - Allocation）
2. 检查当前状态安全性（找安全序列）
3. 若有请求，先检查是否合法（不超过Need），再试探分配，再做安全性检查

---

附录：核心公式汇总

$\text{周转时间}(T_i)=\text{完成时间}-\text{到达时间}$

$\text{等待时间}(W_i)=\text{周转时间}-\text{运行时间}$

$\text{带权周转时间}(W_i^{\prime })=\frac{\text{周转时间}}{\text{运行时间}}\ge 1$

$\text{平均周转时间}=\frac{1}{n}{\sum }_{i=1}^n{T}_i$

$\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j]$

$\text{信号量S的含义：}\{\begin{array}{ll}S>0& \text{还有S个资源空闲}\\ S=0& \text{资源刚好用完}\\ S<0& \text{有}|S|\text{个进程在等待}\end{array}$

---

最后提醒：本章综合题必会写信号量代码（生产者-消费者、读者-写者）和银行家算法计算，这两块每年都考，必须能手写出来！