进程三态图我画了不下十遍考场上还是会在阻塞到就绪和阻塞到运行之间犹豫两秒。死锁更烦四个必要条件背得滚瓜烂熟一遇到下列属于死锁避免而非预防的是就开始猜。后来我把这块拆成四件事分开记状态怎么转、CPU 分给谁、进程之间怎么同步、抢不到资源怎么办。四件事各自独立之前的混乱其实是把它们揉在一起了。第 2 章的进程管理本质上就考这四件其中第三件调度算法和第四件死锁分值最集中。一、程序、进程、线程三个词别再混着用先解决命名问题。这三个词在题干里经常同时出现选项之间只差几个字。对比项程序进程线程存在形态静态躺在磁盘上的代码动态有生命周期动态进程内的执行流是否占有资源不占资源分配的基本单位基本不独立占有共享进程资源能否被调度不能能传统调度的对象能现代调度的实际对象地址空间无独立地址空间同一进程内的线程共享地址空间切换开销无大要换页表与现场小只换栈和寄存器数量关系一个程序可对应多个进程一个进程至少有一个线程一个进程可含多个线程一句话记程序是菜谱进程是按菜谱做菜的那一次过程线程是厨房里的几个厨师。同一份菜谱能同时做多份每份是独立进程一份菜里有好几个人在忙每个人是一条线程共用同一口锅。选择题常在这里下套进程是程序的一次执行是对的“进程是程序的集合”线程拥有独立的地址空间是错的。二、三态、五态、七态箭头方向比状态名更重要教材给的是三态模型运行、就绪、阻塞。五态再加新建和终止。七态再加就绪挂起和阻塞挂起引入挂起是因为内存不够要把进程换到外存。真正考的是哪些转换存在、哪些不存在。转换触发原因主动还是被动新建 → 就绪创建完成、系统接纳系统行为就绪 → 运行被调度程序选中分到 CPU被动运行 → 就绪时间片用完或被更高优先级抢占被动剥夺运行 → 阻塞请求 I/O、等信号量、等资源主动进程自己发起阻塞 → 就绪等待的事件发生I/O 完成或资源到位被动运行 → 终止正常结束或异常终止系统行为就绪 ↔ 就绪挂起内存紧张挂起内存宽松激活系统行为阻塞 ↔ 阻塞挂起同上系统行为两条最有用的判断规则只有运行能进阻塞就绪态的进程不可能直接变阻塞——它根本还没执行不可能发起等待。“阻塞只能回就绪”永远不能直达运行。事件到来之后进程要先排回就绪队列重新竞争 CPU。七态只比五态多挂起两个字记法挂起就是把进程从内存搬到外存进程本身没结束激活后还能回来。选择题里挂起态的进程在外存中是正确表述。三、调度算法六种算法放一张表再手算一遍调度算法考两种形式给场景选算法或者给数据算周转时间。先放对照表。算法依据抢占优点缺点适合场景先来先服务 FCFS到达先后否简单公平长作业拖死短作业不利于 I/O 型批处理、CPU 繁忙型短作业优先 SJF运行时间最短通常否平均周转时间最优需预知运行时间长作业可能饥饿批处理高响应比优先 HRRN响应比最高否兼顾长短不饥饿每次调度都要算一遍响应比批处理时间片轮转 RR时间片用完就换是响应及时公平时间片难定过小切换开销大分时系统、交互式优先级调度优先级高低可抢占可非抢占能体现任务重要性低优先级饥饿需老化补偿实时系统多级反馈队列队列优先级 时间片递增是短作业快、长作业也能跑完实现复杂通用操作系统实际采用的思路响应比公式响应比 (等待时间 要求服务时间) / 要求服务时间。等待越久分子涨得越快长作业自然被扶起来这就是它不饥饿的原因。举个例子A 已等待 10ms、需运行 2ms响应比(102)/2 6B 等待 2ms、需运行 8ms响应比(28)/8 1.25先调度 A。手算三个作业三种算法题目给 P1 需 8、P2 需 4、P3 需 2全部在 0 时刻到达。周转时间 完成时间 - 到达时间。FCFS按 P1 → P2 → P3 顺序完成时间 8、12、14周转时间 8、12、14平均(81214)/3 34/3 ≈ 11.33。SJF按 P3 → P2 → P1 顺序完成时间 2、6、14周转时间 2、6、14平均22/3 ≈ 7.33。RR时间片 4P1 跑 0 到 4 后剩 4P2 跑 4 到 8 结束P3 跑 8 到 10 结束P1 跑 10 到 14 结束。完成时间 P114、P28、P310周转时间 14、8、10平均32/3 ≈ 10.67。结论很直观SJF 平均周转最短RR 的响应最及时。这个数值关系本身就是考点——平均周转时间最小的算法选 SJF几乎不会翻车。四、死锁四个条件与四种对策对应关系别张冠李戴死锁四条件四个必须同时成立缺一个就不会死锁互斥、占有且等待也叫请求与保持、不可抢占、循环等待。必要条件含义怎么破坏它预防代价互斥资源一次只给一个进程改造成可共享如 SPOOLing 把打印机虚拟成共享设备适用面窄多数资源天生互斥占有且等待拿着资源还申请新的一次性申请全部资源静态分配或先释放再申请资源利用率低容易饥饿不可抢占已分配的不能强行收回申请不到就释放已占资源或按优先级抢占只适用于 CPU、内存这种能保存恢复现场的资源循环等待存在环形等待链资源有序分配统一编号必须按递增顺序申请代价最小、最常用但编号要稳定四种对策的区分是最大的失分点尤其预防和避免对策时机做法代表方法允许死锁发生吗预防事前设计系统时破坏四个条件之一资源有序分配、静态分配不允许避免每次分配请求时判断分配后系统是否仍安全银行家算法不允许检测定期或事后资源分配图化简化简法、死锁定理允许解除检测到之后剥夺资源、撤销进程、进程回退按代价最小选撤销对象允许判断口诀预防是不让条件成立避免是每次都先看一眼安不安全检测是让它发生再抓解除是抓到之后拆。只要题干出现分配前先试算是否处于安全状态选避免出现给资源编号按顺序申请选预防。银行家算法走一遍假设系统有 A、B、C 三类资源总量 (10, 5, 7)当前已分配出去 (7, 2, 5)剩余可用 Available (3, 3, 2)。五个进程的 Need 分别是进程已分配 Allocation最大需求 Max还需要的 NeedP0(0, 1, 0)(7, 5, 3)(7, 4, 3)P1(2, 0, 0)(3, 2, 2)(1, 2, 2)P2(3, 0, 2)(9, 0, 2)(6, 0, 0)P3(2, 1, 1)(2, 2, 2)(0, 1, 1)P4(0, 0, 2)(4, 3, 3)(4, 3, 1)推演安全序列规则是找一个 Need 小于等于当前 Available 的进程假设它跑完并归还资源P1 的 (1,2,2) ≤ (3,3,2)可行归还后 Available (5, 3, 2)P3 的 (0,1,1) ≤ (5,3,2)可行归还后 Available (7, 4, 3)P4 的 (4,3,1) ≤ (7,4,3)可行归还后 Available (7, 4, 5)P0 的 (7,4,3) ≤ (7,4,3)可行归还后 Available (7, 5, 5)P2 的 (6,0,0) ≤ (7,5,5)可行归还后 Available (10, 5, 7)序列 P1 → P3 → P4 → P0 → P2 成立系统处于安全状态。只要能找出任意一条安全序列就安全找不到才是不安全。注意不安全不等于已死锁只是存在发生死锁的可能这个区别也是常考点。死锁、饥饿、死循环现象涉及进程数进程状态能否自行解开死锁至少两个互相等待全部阻塞不能必须外力介入饥饿一个或多个可能处于就绪态能高优先级任务跑完就可能轮到死循环一个处于运行态不能代码逻辑问题区分死锁和饥饿的关键死锁一定是多个进程都在阻塞饥饿的进程可能一直就绪却排不上队。五、信号量与 PV 操作前趋图怎么翻译成代码这块在案例题里出现过形式是给一个前趋图让你补全 P、V 的位置和信号量初值。用途初值P、V 的位置关键点互斥mutex 1临界区前面 P后面 V同一进程内成对出现同步通常为 0后执行的操作前 P先执行的操作后 V分布在不同进程里信号量 S 的物理含义要记死S 0 表示还有 S 个资源可用S 0 时|S| 表示排队的进程个数。P 是申请S 减一不够就阻塞V 是释放S 加一有等待者就唤醒。前趋图翻译规则每一条边设一个信号量初值设 0。前驱节点执行完做 V后继节点开始前做 P。看清箭头方向就不会把 V 写到前面去。六、这章值几分论文能用吗考频判断进程管理在综合知识里稳定占 2~4 分属于性价比很高的部分。状态转换的箭头方向、调度算法选型、死锁四条件与对策匹配、信号量初值这四个点反复考。案例分析里偶尔出现系统响应变慢请分析资源竞争问题这时死锁四条件和饥饿的概念能直接用上。论文可用性直接写进程调度当论文主题不合适论文要的是架构级实践。但如果你写的是高并发系统或资源池设计可以把资源有序分配避免死锁写进解决方案一段说明连接池按固定顺序申请以防循环等待这比空谈我们做了优化有技术含量得多。速记收尾状态记只有运行能进阻塞阻塞只能回就绪调度记SJF 周转最短、RR 响应最快、HRRN 不饥饿死锁对策记预防破条件、避免算安全、检测画化简、解除撤进程信号量记互斥成对、同步分居。下一篇讲第 2 章第三块存储管理。页式、段式、段页式三种方案的对比以及虚拟存储里那几个必须动手算的地址变换与页面置换比这篇的计算量更大。