【总结】第二章:进程与线程
考研提示:本章是操作系统最重头的一章,每年必考,且必有大题。重点掌握:进程状态转换图、CPU调度算法计算、信号量PV操作写代码、死锁银行家算法。
一、进程基础
1.1 进程 vs 程序
| 对比项 | 程序 | 进程 |
|---|---|---|
| 本质 | 静态代码文件 | 动态执行过程 |
| 资源 | 不占用 | 占CPU/内存/文件等资源 |
| 数量关系 | 一个程序可对应多个进程 | 一个进程只对应一段程序 |
| 标识 | 文件名 | PID + PCB |
进程控制块(PCB):进程存在的唯一标志,内核区存储。包含:PID、进程状态、寄存器值、内存地址、优先级、I/O信息等。
1.2 进程五状态转换(必须会画!)
①创建完成
↓
【新建态】
│ ②OS允许
↓
⑥事件发生 ←← 【就绪态】 ←←←←←← ⑤时间片到/被抢占
(I/O完成) │ ↑ ↑
③被调度 ⑤ ⑤
↓ │
【运行态】 →→→→→→→→→→→→→→→→→→→┘
│
④等待事件(I/O请求/等信号量)
↓
【阻塞态】
│ ⑦结束
↓
【终止态】
关键转换规则:
- 运行→阻塞:进程主动等待(只能由运行态主动发起)
- 阻塞→就绪:等待的事件发生(被动唤醒)
- ⚠️ 阻塞不能直接变运行! 必须先经过就绪态
1.3 虚拟地址空间各区域
| 区域 | 存放内容 | 典型变量 |
|---|---|---|
| 内核区 | PCB、内核代码 | OS维护,用户不可直接访问 |
| 用户栈 | 局部变量、函数形参、返回地址 | int length;(函数内) |
| 运行时堆 | 动态分配内存(向上增长) | malloc()申请的空间 |
| 可读写数据段 | 全局变量、静态变量 | char *ptr;(函数外)、static int cnt; |
| 只读代码段 | 机器指令、字面常量 | 函数体编译后的二进制、"hello" |
口诀:指针变量本身看定义位置,malloc申请的内存永远在堆。
二、线程
2.1 线程 vs 进程
| 对比项 | 进程 | 线程 |
|---|---|---|
| 资源 | 资源分配基本单位 | 共享进程资源,不独立拥有 |
| 调度 | 传统OS调度单位 | 现代OS的调度基本单位 |
| 开销 | 创建/切换/通信开销大 | 开销小 |
| 隔离性 | 地址空间相互独立 | 同进程线程共享地址空间 |
线程私有:线程ID、PC寄存器、栈(局部变量) 线程共享:代码段、数据段、堆、打开的文件
2.2 用户级线程 vs 内核级线程
| 用户级线程(ULT) | 内核级线程(KLT) | |
|---|---|---|
| OS是否感知 | 不感知 | 感知,内核管理 |
| 切换开销 | 小(不入内核) | 大(需内核介入) |
| 一个线程阻塞 | 整个进程阻塞 | 其他线程可继续运行 |
| 多核利用 | 不能并行 | 可以并行 |
三、进程间通信(IPC)
| 方式 | 原理 | 速度 | 特点 |
|---|---|---|---|
| 共享内存 | 多进程映射同一物理内存 | 最快 | 需配合信号量同步 |
| 消息传递 | send/receive原语传消息 | 中等 | 有直接/间接(邮箱)两种 |
| 管道 | 字节流,单向,先进先出 | 中等 | 无名管道(亲缘进程),有名管道(任意进程) |
| 信号 | OS发异步通知 | 快(但只传数字) | 不能传数据内容 |
四、CPU调度
4.1 三级调度
| 名称 | 作用 | 频率 |
|---|---|---|
| 高级调度(作业调度) | 作业从磁盘→内存(新建→就绪) | 最低 |
| 中级调度(内存调度) | 进程挂起/激活 | 中 |
| 低级调度(进程调度) | 就绪队列→CPU | 最高,408重点 |
4.2 调度评价指标与公式
其中:=进程数,完成时间=进程结束时刻,到达时间=进程进就绪队列时刻,运行时间=实际需要在CPU上的时间
4.3 调度算法对比
| 算法 | 规则 | 是否抢占 | 优点 | 缺点 |
|---|---|---|---|---|
| FCFS | 先来先服务 | 否 | 简单公平 | 长进程优先,短进程等待久 |
| SJF | 运行时间最短优先 | 否(SRTF是抢占版) | 平均等待时间最短 | 长进程饥饿 |
| 优先级 | 优先级高者先 | 可选 | 灵活 | 低优先级进程饥饿(老化解决) |
| RR(轮转) | 时间片轮流 | 是 | 公平,响应好 | 时间片选择关键 |
| 多级反馈队列 | 多队列,新进程高优先级,超时降级 | 是 | 综合最优 | 实现复杂 |
RR时间片大小:太大→退化为FCFS;太小→切换开销占主导,效率下降
调度时机:进程主动放弃CPU、时间片用完、更高优先级进程到达(仅抢占式);临界区内/中断处理中不应调度
五、同步与互斥(最重要!)
5.1 基本概念
- 临界资源:每次只允许一个进程访问的资源
- 临界区:访问临界资源的那段代码
- 互斥:同一时刻只有一个进程在临界区
- 同步:进程间有先后执行顺序的约束
临界区四原则:空闲让进、忙则等待、有限等待、让权等待
5.2 信号量(Semaphore)
信号量S是一个整数,只能通过原子操作P/V修改:
P操作(申请资源):
P(S): S--; if(S < 0) block(S.L); // S<0则阻塞,挂入等待队列V操作(释放资源):
V(S): S++; if(S <= 0) wakeup(S.L); // S<=0说明有进程在等,唤醒一个信号量值的含义:
使用规范:
- 互斥信号量:初值=1,用于保护临界区,在同一进程内成对
P...V - 同步信号量:初值=0,用于表示”事件未发生”,P和V分布在两个不同进程
5.3 三大经典同步问题(大题必考!)
① 生产者-消费者(缓冲区大小N)
semaphore mutex = 1; // 互斥:保护缓冲区
semaphore empty = N; // 同步:空缓冲区数量
semaphore full = 0; // 同步:满缓冲区数量
生产者:
P(empty); // ①先申请空位(若为0则等待)
P(mutex); // ②再申请互斥锁
放入数据;
V(mutex); // ③先释放互斥锁
V(full); // ④再通知消费者
消费者:
P(full); // ①先申请产品(若为0则等待)
P(mutex); // ②再申请互斥锁
取出数据;
V(mutex); // ③先释放互斥锁
V(empty); // ④再通知生产者⚠️ 铁律:P(同步信号量) 必须在 P(互斥信号量) 之前!否则死锁!
② 读者-写者(读者优先)
semaphore rw = 1; // 互斥:保护写操作
semaphore mutex = 1; // 互斥:保护readCount
int readCount = 0; // 当前读者数量
读者:
P(mutex);
readCount++;
if(readCount == 1) P(rw); // 第一个读者阻止写者
V(mutex);
读数据;
P(mutex);
readCount--;
if(readCount == 0) V(rw); // 最后一个读者放行写者
V(mutex);
写者:
P(rw);
写数据;
V(rw);③ 哲学家进餐(5人5筷,防死锁)
方案:加互斥锁,一次性拿起两根:
semaphore mutex = 1; // 拿筷子的动作互斥
semaphore chopstick[5]={1,1,1,1,1};
哲学家i:
P(mutex); // 原子性拿两根
P(chopstick[i]);
P(chopstick[(i+1)%5]);
V(mutex);
吃饭;
V(chopstick[i]);
V(chopstick[(i+1)%5]);多类产品变体(2009统考):奇数/偶数消费者,需将full拆为odd=0和even=0两个信号量,不能合并!
六、死锁
6.1 四个必要条件(记”互持不循”)
| 条件 | 含义 |
|---|---|
| 互斥 | 资源不可共享 |
| 持有并等待 | 拿着资源还在等别的资源 |
| 不可抢占 | 资源不能被强制剥夺 |
| 循环等待 | 进程链形成等待环 |
四个条件是必要条件,不是充分条件(满足四个未必死锁)
6.2 处理策略
| 策略 | 思路 | 方法 |
|---|---|---|
| 预防 | 破坏四个条件之一 | 一次性申请所有资源(破持有等待);资源按序编号(破循环等待) |
| 避免 | 动态判断安全再分配 | 银行家算法 |
| 检测+解除 | 允许死锁,发现后处理 | 资源分配图化简;终止进程或抢占资源 |
6.3 银行家算法(必考计算!)
数据结构(n个进程,m种资源):
| 变量 | 含义 |
|---|---|
| Available[m] | 当前各资源的可用数量 |
| Max[n][m] | 各进程对各资源的最大需求量 |
| Allocation[n][m] | 各进程已分配到的各资源数量 |
| Need[n][m] | 各进程还需要的各资源数量 |
安全性检查算法:
- 令 Work = Available,Finish[n] = {False}
- 找满足条件的进程i:
Finish[i]=False且Need[i] ≤ Work - 找到则:
Work += Allocation[i],Finish[i] = True,回到② - 所有Finish[i]=True → 安全;否则不安全
资源请求算法(进程Pi请求Request):
- 若
Request > Need[i]→出错 - 若
Request > Available→等待 - 试探分配:
Available-=Request,Allocation[i]+=Request,Need[i]-=Request - 做安全性检查,安全则真正分配,否则回滚
七、高频易错汇总
| 易错点 | 正确理解 |
|---|---|
| 进程是调度基本单位 | 引入线程后,线程才是调度基本单位 |
| 阻塞→直接运行 | 阻塞必须先到就绪,再到运行 |
| P操作增加信号量 | P操作减少,V操作增加 |
| 同步信号量初值=1 | 同步信号量初值=0 |
| P(mutex)先于P(empty) | 同步P操作必须早于互斥P操作 |
| 死锁四条件是充分条件 | 只是必要条件,满足未必死锁 |
| 安全状态=不会死锁 | 安全状态一定不死锁;不安全状态可能死锁 |