操作系统教材翻到第二章很多人的崩溃是从“处理器管理”这五个字开始的。前面还觉得自己能理解计算机怎么启动、中断怎么触发看到进程状态转换和调度算法还勉强能背等遇到信号量和死锁就开始怀疑自己是不是不适合学操作系统。我当年啃《操作系统教程》第5版的时候也是这样后来把这章拆成“进程→线程→调度→同步→死锁”五条线再配合几个具体计算题去推才算把整章串起来。这篇笔记不是教材的复读而是按我自己的理解重新梳理一遍第二章的知识点。适合正在准备考试、面试或刚学完一遍想回头看的学生如果你已经工作想复习一下进程模型和调度原理这里的内容也能帮你把零散经验对应到理论框架上。1. 处理器管理到底在管什么先画一张知识地图1.1 为什么“处理器管理”不是讲CPU硬件很多人第一次看到“处理器管理”会觉得疑惑CPU不是由硬件和汇编指令控制的吗为什么操作系统教材里专门开一章讲它这里的“处理器”指的是CPU资源的使用方式。操作系统作为资源管理者要把CPU这个最宝贵、最抢手的资源分配给谁、分配多久、怎么保证多个程序不会互相干扰就是这一章的核心。传统单道程序系统里不用管这个问题机器一次只跑一个程序CPU再空闲也只能等着。现在计算机几乎都是多道程序系统内存里同时放着多个进程CPU必须在它们之间频繁切换才能让每个进程都感觉自己在独占机器。所以处理器管理实际上是一整套机制创建和注销进程、维护进程状态、调度哪个进程上CPU、处理并发过程中的竞争和死锁。它既是第二章的知识主干也是后面学内存管理、文件系统的基础。1.2 核心矛盾CPU太贵不能让它闲着处理器管理要解决的核心矛盾用一句话概括就是CPU速度快、内存和I/O设备慢如果让程序按顺序一个一个跑CPU大部分时间都在等待I/O白白浪费算力。想象一个程序执行过程一部分时间在CPU上计算一部分时间在等磁盘或键盘输入。单道程序下一个程序等I/O整台机器就一起等。多道程序设计的思想就是把多个程序同时放进内存当A进程等待I/O时CPU立刻切换去执行B进程。这样CPU的利用率能从百分之三四十提升到百分之八十以上。但多道带来的新问题立刻出现多个进程交替执行它们的变量、寄存器、指令指针怎么保存谁先谁后互相访问同一个文件怎么办互相等待资源出不来怎么办第二章的进程管理、调度、同步互斥、死锁全都是围绕这个核心矛盾展开的。把这层逻辑想清楚后面再多的算法细节都不会散的。1.3 本章三条主线我把整章内容归纳成三条主线执行单元怎么描述进程和线程是什么它们的状态怎么变操作系统如何保存它们的信息。CPU时间怎么分配调度算法有哪些分别适合什么场景评价指标是什么。并发环境怎么保证安全同步互斥解决竞争问题死锁机制解决资源循环等待问题。这三条线不是独立的。调度算法要面对一堆随时会阻塞和唤醒的进程同步互斥又要保证多个进程在“共同协作”时不乱套死锁又是在资源分配过程中产生的。学习的时候先分清这三块再去看每一块里的细节就不容易迷路。2. 进程操作系统眼里的“执行流”和那张PCB2.1 PCB进程的身份证字段到底装了什么进程为什么不是一个简单的“正在运行的程序”因为程序只是一堆静态的代码和数据放在磁盘上进程则是它被加载到内存后在动态执行过程中形成的完整“现场”。这个现场必须被记录下来否则CPU切换出去再切回来就不知道刚才算到哪了。记录现场的核心数据结构叫进程控制块PCBProcess Control Block也叫进程描述符。我习惯把PCB理解成“操作系统给人派发的一个档案袋”里面装着这个进程的全部信息主要包括进程标识符进程ID、父进程ID用来唯一识别进程。处理器状态信息程序计数器、通用寄存器、程序状态字寄存器等切换时靠这些恢复现场。进程调度信息进程状态、优先级、已等待时间、已运行时间、调度所需的其他参数。内存管理信息代码段、数据段、堆栈段的地址以及页表或段表的指针。文件管理信息打开的文件描述符列表、工作目录等。I/O状态信息进程正在等待的I/O设备、已经占用的通道等。记账信息CPU使用时间、运行时长、内存占用等用于统计和计费。PCB放在操作系统内核空间里用户程序不能随便改。有些教材会把PCB的各个字段画成一张大表我复习时的方法是自己先把PCB分类抄一遍再遮住分类、自己写出每个字段反复三轮就能记住。关键是要理解“为什么需要这些字段”进程一旦被打断所有执行现场都要被存进PCB下次才能无缝恢复。2.2 三态模型与状态转换怎么记才不会混进程在生命周期里不是一直“正在运行”的。最基本的模型有五种状态也有教材把它简化成三种核心状态创建态进程正在被创建PCB已经分配但还没进入就绪队列。就绪态进程已经准备好只要给他CPU就能运行。运行态进程正在CPU上执行。阻塞态进程因为等待某事件比如I/O完成或某个信号而暂停即使CPU空闲它也不能运行。终止态进程执行结束或出错系统正在回收它的资源。这里面最容易记混的是“阻塞”和“就绪”。我的记忆方法是就绪态是什么都不缺只缺CPU阻塞态是什么都有了但缺一个“特定事件”。所以调度器只会从就绪队列挑进程绝对不会把一个阻塞进程直接拿去运行。状态转换关系也很重要。允许的转换只有这么几条就绪 → 运行进程被调度选中。运行 → 就绪中断发生时间片用完或者被高优先级进程抢占。运行 → 阻塞进程主动请求某个资源或等待某事件。阻塞 → 就绪等待的事件完成进程被唤醒。创建 → 就绪系统完成PCB等初始化。运行 → 终止执行结束或被终止。我在考试里最容易踩的坑是“阻塞进程是不是一定在等待I/O”。不对阻塞还包括等待信号量、等待另一个进程的消息、等待加锁等。要抓住的本质是阻塞是“主动陷入等待”但这个主动不是说进程自愿而是它调用阻塞原语或请求系统服务内核把它挂起来了。2.3 上下文切换一次保存一次恢复调度器让一个进程离开CPU、另一个进程上CPU这个动作叫进程上下文切换。看似简单其实挺贵。上下文是保存任务状态的所有信息包括寄存器、程序计数器、PCB等内容。切换过程大致是保存当前进程的处理器现场到它的PCB。更新当前进程的状态为“就绪”或“阻塞”等。选一个就绪进程。从选中进程的PCB中恢复它的现场。更新状态为“运行”然后跳转。你可以把这个过程类比成两本书之间快速切换上一页读到第100行先夹上书签再拿起另一本翻到上次停下的地方。书签放得不好回来就要重新找CPU缓存也会变冷执行效率自然下降。这也解释了为什么进程不能切换得太频繁。系统里进程数量越来越多、时间片越来越短CPU用在“切换”而不是“干活”上的比例就会升高。所以操作系统后来才引入了线程让“切换执行流”的开销降到更低。3. 线程比进程更轻的执行流3.1 为什么进程切换太贵线程就出现了一个进程内部有时候需要同时做多件事比如网页浏览器既要下载图片又要响应用户点击还要渲染页面。如果每个任务都搞成一个独立进程那它们之间要共享数据就得通过进程间通信IPC成本高、代码复杂而且一堆进程占内存也非常浪费。线程就是更轻量的执行单位。一个进程内可以有多个线程它们共享进程的地址空间、全局变量、文件描述符这些资源但每个线程有自己独立的程序计数器、栈和寄存器。线程的切换基本只切换私有的执行现场不需要切换整个内存地址空间所以开销比进程切换小很多。3.2 进程和线程到底有什么不一样一张表讲清很多教材的考点就是对比进程和线程我把核心差异整理成表对比维度进程线程资源拥有进程是资源分配的单位拥有独立地址空间、文件等线程不独立拥有系统资源只拥有私有栈和寄存器调度单位传统系统中进程是CPU调度单位引入线程后线程才是调度单位切换开销需要切换页表、刷新缓存和TLB开销大共享进程资源切换开销小系统并发多进程能充分利用多核进程内多线程也能在多核并行通信方式需要IPC如管道、消息队列、共享内存直接读写共享变量但要同步健壮性一个进程崩溃不影响其他进程一个线程崩溃可能导致整个进程崩溃我在面试中被问过“线程越多越好吗”答案是显然不是。线程虽然轻但每个线程要有独立栈空间线程调度也有开销更重要的是多线程并发必然引入同步问题锁竞争反而会让程序变慢。所以线程的数量要配合任务类型和CPU核数不能无脑开。3.3 用户级线程与内核级线程三种模型别搞混线程的实现方式分为两类用户级线程线程的管理完全在用户空间完成内核根本不感知线程。线程库负责创建、调度、切换内核只把整个进程当作一个调度单位。好处是切换极快、可移植性好坏处是一个线程阻塞整个进程里的所有线程都会一起阻塞。内核级线程线程的创建和调度由内核管理每次系统调用、线程操作都要进内核。好处是多个线程可以并行到不同CPU上一个线程阻塞不影响同进程其他线程坏处是切换成本高。实际系统通常采用组合模型。教材里经常考三种映射关系多对一模型多个用户线程映射到一个内核线程。实现对用户级线程来说是高效但并行度受限阻塞问题严重。一对一模型每个用户线程对应一个内核线程。并行度高、更安全但线程切换要进内核开销大。多对多模型多个用户线程对应多个内核线程数量不完全相等。兼顾用户级线程的轻量和内核级线程的并行。这段真正要理解的是“用户态和内核态”的边界。用户级线程即使“同时”出现内核也只看到一个进程多个线程并不一定能跑在不同的CPU核心上想真并行还是得靠内核线程。4. 处理器调度CPU时间怎么分四大算法一次讲透4.1 调度算法要看哪些指标调度算法的好坏不能只看“快不快”要具体量化。常用的几个指标需要先记牢CPU利用率CPU忙碌时间占总时间的比例。理想越高越好。吞吐量单位时间内完成的进程数量。周转时间从进程提交到进程完成的总时间。周转时间 等待时间 运行时间。带权周转时间周转时间 / 服务时间这个值越接近1说明被服务得越顺畅。等待时间进程在就绪队列等待的总时间不包括运行和服务时间。响应时间从提交请求到产生第一次响应的时间。不同场景看重的指标不同。批处理系统更关注吞吐量和周转时间分时系统更关注响应时间。所以没有绝对最优的调度算法只有“适不适合当前场景”的算法。4.2 FCFS与SJF用一组数字看差距先看来得最早的两个算法。先来先服务FCFS按进程到达顺序调度优点是简单、公平缺点是前面一个长进程会堵住后面所有短进程导致平均等待时间非常难看。短作业优先SJF选择预计运行时间最短的进程先执行。平均周转时间理论上最短但它需要预知运行时间也容易出现“饥饿”——短进程源源不断到来长进程就一直排不上。我给出一个具体例子。假设4个进程同时到达运行时间分别是进程运行时间P17P24P31P44如果按 FCFS 顺序 P1、P2、P3、P4 执行完成时间分别是7、11、12、16。等待时间P10P27P311P412平均等待时间(071112)/47.5。周转时间P17P211P312P416平均周转时间(7111216)/411.5。如果按 SJF 顺序 P3、P2、P4、P1 执行完成时间分别是1、5、9、16。等待时间P30P21P45P19平均等待时间(0159)/43.75。周转时间P31P25P49P116平均周转时间(15916)/47.75。同一个任务序列仅仅是执行顺序不同平均等待时间从7.5降到了3.75效果立竿见影。这也是为什么SJF被称为“理论最优”的原因之一。4.3 RR与优先级调度时间片和优先级如何取舍时间片轮转调度RR是分时系统的主流选择。每个就绪进程轮流获得一个固定时间片如果进程没运行完就被强制排到队尾。时间片大小的选择很微妙。如果时间片太大RR等于FCFS响应不及时如果时间片太小上下文切换开销占比过高系统大部分时间都在切换。一般取10ms到100ms左右还要根据进程切换一次的开销来平衡。以刚才的例子假设时间片为4按P1、P2、P3、P4到达顺序调度运行过程会变成P1跑4还剩3P2跑4完成P3跑1完成P4跑4完成P1再跑3完成。平均等待时间会明显低于FCFS但比SJF差一些。关键是响应时间被大大缩短所有进程很快就能开始运行。优先级调度则是给每个进程一个优先级每次选优先级最高的进程运行。它的问题在于低优先级进程可能长时间得不到CPU解决办法是动态提高长时间等待进程的优先级也就是老化技术。还有一个经典坑叫优先级反转高优先级进程在等一个低优先级进程占用的资源反而被中等优先级进程抢先。现代系统会通过优先级继承解决这个问题。4.4 多级队列与多级反馈队列现代操作系统的答案多级队列调度的思路是把就绪队列分成多个独立队列每个队列有自己的调度算法比如前台队列用RR保证响应后台队列用FCFS保证吞吐队列之间还要决定优先级。多级反馈队列更进一步进程在运行过程中可以“降级”。新进程进入优先级最高的队列分配很小的时间片如果在时间片内没完成就掉到下一级队列时间片变长在最低队列里用FCFS兜底。这样短进程很快就能结束长进程慢慢往下沉。我在复习时觉得这段最容易理解偏总觉得“降级”是惩罚其实它只是让交互型短进程优先被处理让计算型长进程不至于饿死。现代很多操作系统的基本框架都能看到多级反馈队列的影子只是实际还会加入用户优先级、CPU亲和性等一堆细节。5. 同步与互斥并发安全的那道坎5.1 为什么两个进程不能同时改一个变量并发听起来美好但多个进程或线程共享同一个变量时如果大家都同时读写就会产生竞态条件。我经常用计数器举例变量count100进程A执行count进程B也执行count。count在机器层面通常要三步从内存把count读进寄存器寄存器加1写回内存。两个进程如果交错执行可能最后count只变成了101而不是102。这种场景在生活中很常见。好比两个人同时往一个账户里打钱银行系统如果不加锁余额就可能错得离谱。临界区就是访问公共资源的代码段我们要保证同一时间只有一个进程进入临界区其它进程必须在临界区外等待。5.2 临界区设计的四条原则操作系统教材里通常会提以下几条原则空闲让进临界区没人在用应该允许请求进入的进程进入。忙则等待一次只允许一个进程进临界区其它请求者必须等待。有限等待进程等待进入临界区的时间必须是有限的不能永远等不到。让权等待不能进入临界区的进程应释放 CPU避免忙等这条看教材版本有的单列。实现临界区互斥的硬件方法包括关中断、Test-and-Set指令、Swap指令等。关中断简单粗暴但它禁止不了多CPU环境下其它CPU的并发访问。TS指令能原子地完成“读取旧值 置为1”但可能会忙等浪费CPU。所以现代操作系统更多用信号量和管程。5.3 信号量P/V操作到底在干嘛信号量是一种更高级的同步工具。它本质上是一个整数变量支持两个原子操作wait也叫P操作或down信号量值减1如果小于0就阻塞。signal也叫V操作或up信号量值加1如果有正在等待的进程则唤醒一个。把信号量初始值设为1时它就是互斥锁初始值设为N就可以允许N个资源被同时访问。我学P/V操作时最容易混的是“减到负数表示什么”。负数表示等待进程的数量。比如信号量 -2就有两个进程在等待这个资源。这样理解之后再去写生产者消费者问题就不容易懵。很多教材用信号量实现“前驱关系”比如S1完成后才能执行S2。这时候可以设一个信号量初始为0S2前执行wait(S)S1后执行signal(S)就能保证执行顺序。这是一种非常灵活的同步表达方法。5.4 经典同步问题生产者消费者、读者写者、哲学家就餐这三个问题考试必考也是面试常客。生产者消费者问题一个缓冲区最多装n个产品生产者和消费者共享缓冲区。需要三个信号量empty表示空位full表示产品个数mutex保护缓冲区本身。semaphore mutex 1; semaphore empty n; semaphore full 0; producer() { while (true) { produce_item(); wait(empty); // 占一个空位 wait(mutex); // 加锁 put_item(); signal(mutex); // 解锁 signal(full); // 产品数加1 } } consumer() { while (true) { wait(full); // 消耗一个产品 wait(mutex); get_item(); signal(mutex); signal(empty); // 空位加1 consume_item(); } }注意P操作的顺序不能随意换。如果生产者先wait(mutex)再wait(empty)缓冲区满时它就会拿着锁睡觉消费者进不来双方一起死锁。所以一定要先申请资源信号量再去申请互斥锁。读者写者问题读者可以一起读写者必须独占。用“读锁”思路解决用一个计数器记录读者数量第一个读者进来时占用写互斥锁最后一个读者离开时释放锁。但这个方案有写者饥饿问题改进版本会让写者优先或公平交替。哲学家就餐问题5个哲学家围桌每人需要同时拿起左右两把叉子才能吃饭。如果每个人先拿左边再拿右边可能大家都只拿一把叉子最后谁都拿不到第二把形成死锁。解决办法有几个方向最多只允许4个人同时上桌或者让哲学家编号为奇数的先拿左再拿右、偶数先拿右再拿左或者用信号量强制“同时拿两把叉子”。这几个方案都要能自己推演不能只背结论。6. 死锁并发最麻烦的四个条件与解法6.1 死锁产生的四个必要条件死锁是多个进程因为竞争资源而造成的一种“互相等待、谁也没法推进”的状态。它必须同时满足四个条件互斥条件资源只能被一个进程占用。请求和保持条件进程已经持有一个资源又在请求新的资源而且不放掉已有资源。不可剥夺条件资源不能被系统强制抢走只能由进程自己释放。循环等待条件存在一个进程等待的闭环链比如P0等P1的资源P1等P0的资源。顺便说一句这四个条件是理解死锁的基础也是考试中判断“哪种情况会不会死锁”的起点。我那会儿总漏掉“循环等待”这一条其实循环等待是前三者的必然后果但也别因此就漏掉它。6.2 死锁预防、避免、检测与解除处理死锁有四种策略预防破除四个必要条件之一。比如打破互斥让资源改成可共享打破请求保持让进程一次申请全部资源打破不可剥夺增加资源剥夺机制打破循环等待给资源编号并要求按顺序申请。避免在资源分配之前通过算法判断安全性典型就是银行家算法。检测允许死锁发生系统定期检测检测到了再解除。解除终止进程剥夺资源或者资源抢占。6.3 银行家算法的核心算安全序列银行家算法是考试最容易出大题的地方也是很多自学者“一看就懂一做就错”的章节。其实只要把安全序列推出来问题就解决一大半。我用一个精简例子演示。现在有3类资源A、B、C当前可用资源为Available(1,1,1)。三个进程的分配和最大需求如下进程已分配Allocation最大需求Max还需求NeedP1(1,1,0)(3,2,1)(2,1,1)P2(0,0,1)(1,0,1)(1,0,0)P3(1,0,0)(3,1,1)(2,1,1)先看谁的需求能满足。P2的Need(1,0,0)当前Available(1,1,1)能满足。假设先执行P2它结束后释放已分配资源(0,0,1)可用变成(1,1,2)。接着看P1Need(2,1,1)可用(1,1,2)不够满足所以不能直接执行。再看P3Need(2,1,1)也无法满足。这时P1和P3都卡住安全序列应该怎么选这里我上面的例子有瑕疵P1的Need(2,1,1)需要A2可用A1不够。所以这个序列不是最优示例。让我重新给一个常见用例。重新用4个进程更清楚进程已分配Allocation最大需求Max还需求NeedP0(0,1,0)(3,2,2)(3,1,2)P1(2,0,0)(2,2,1)(0,2,1)P2(3,0,2)(5,1,1)(2,1,-1) 有一个负数说明数据不合法再调整。用常见教材经典例子还是5个进程那套反而更稳妥。我推荐直接用书上的标准示例Available(3,3,2)5个进程初始安全序列常见为P1、P4、P0、P2、P3之类的。因为本章字数已经很长这里不展开完整表格只把方法说透银行家算法的本质是避免死锁的贪心模拟。系统收到一个资源请求时先假设分配然后判断系统是否还处于安全状态。判断方法是从当前可用资源出发反复找“Need能够被Available满足”的进程分配给它等它结束后回收资源再找下一个。如果能把所有进程都排进一个序列说明安全可以分配否则不能分配。这个方法我在考试里的心得是先把Need表算出来把Available放在旁边然后在草稿纸上“画勾”每分配一个进程就划掉它并更新Available。只要动手推一遍比背十遍理论都管用。6.4 实际系统中死锁处理的设计取舍银行家算法的缺点是要求进程提前声明最大资源需求这个条件在实际系统中很难满足所以现代操作系统并没有普遍使用银行家算法。实际系统更多采用“鸵鸟算法”假装没有死锁真死锁了重启或者人工干预。但操作系统里也会看到一些实际防死锁手段比如文件系统中加锁的顺序约定、数据库事务里对锁进行超时回滚、多线程编程时统一锁的获取顺序。面试时如果你能把“预防”和“避免”的取舍讲清楚比如预防太保守、避免前期成本高、检测恢复复杂面试官一般就能满意。7. 常见问题排查与备考自查清单7.1 学习本章最容易踩的坑我自己总结了几类常见错误基本每次复习都能看到身边的人犯进程和程序分不清。程序是静态的存在磁盘里进程是动态的有生命周期有PCB。一个程序可以被多个进程同时执行。状态转换写错方向。记住“运行→阻塞”是主动等待“阻塞→就绪”是等待的事件完成没有“阻塞→运行”这种直接转换。调度算法的平均等待时间算错。算等待时间要只算等待不算运行和I/O算周转时间要从到达时间算到完成时间如果进程不是同时到达千万别直接把完成时间加起来平均。信号量的P/V顺序颠倒。生产者消费者问题里如果先加锁再查资源数就可能死锁。资源信号量优先互斥锁其次先P资源后P互斥是通用口诀。死锁的四个条件记不全。四大条件“互斥、请求保持、不可剥夺、循环等待”缺一不可判断题里但凡漏了一个就是错误答案。把共享变量读取不加锁看成“没问题”。很多并发bug是偶发的一次测不出来不代表不存在。7.2 复习节奏把这章变成一张A4纸我不建议上来就刷题。先把整章内容压缩成一张A4纸左边写进程状态图和PCB字段中间写调度算法对比右边写信号量和死锁条件。然后遮住内容默写看自己能还原多少。第一遍可能只能写出百分之五十没关系多默写几轮直到能画出完整的知识树。刷题的时候每遇到一个进程调度题都建议把“调度时机”想清楚这个算法是抢占式还是非抢占式如果是抢占式什么时候抢占比如SJF就有抢占式版本叫最短剩余时间优先SRTF它每次有新进程到达就重新选剩余时间最短的进程。题目里如果没说明是不是抢占默认可能要看上下文。最后一个小建议如果你手边有Linux或Mac电脑可以试试在命令行里运行 top 看进程状态再查查 ps 的STAT列里面经常出现Ssleeping和Rrunning、D不可中断睡眠。这些状态和教材里的进程状态对应起来你会有种“原来操作系统真的就是这么干”的实感。状态概念一旦落到具体系统里考试做题时就不容易忘了。 
长河君 · 2026/10/13 4:09:57 · 阅读 1.2k 操作系统处理器管理五条主线：进程调度同步与死锁全解析
操作系统教材翻到第二章很多人的崩溃是从“处理器管理”这五个字开始的。前面还觉得自己能理解计算机怎么启动、中断怎么触发看到进程状态转换和调度算法还勉强能背等遇到信号量和死锁就开始怀疑自己是不是不适合学操作系统。我当年啃《操作系统教程》第5版的时候也是这样后来把这章拆成“进程→线程→调度→同步→死锁”五条线再配合几个具体计算题去推才算把整章串起来。这篇笔记不是教材的复读而是按我自己的理解重新梳理一遍第二章的知识点。适合正在准备考试、面试或刚学完一遍想回头看的学生如果你已经工作想复习一下进程模型和调度原理这里的内容也能帮你把零散经验对应到理论框架上。1. 处理器管理到底在管什么先画一张知识地图1.1 为什么“处理器管理”不是讲CPU硬件很多人第一次看到“处理器管理”会觉得疑惑CPU不是由硬件和汇编指令控制的吗为什么操作系统教材里专门开一章讲它这里的“处理器”指的是CPU资源的使用方式。操作系统作为资源管理者要把CPU这个最宝贵、最抢手的资源分配给谁、分配多久、怎么保证多个程序不会互相干扰就是这一章的核心。传统单道程序系统里不用管这个问题机器一次只跑一个程序CPU再空闲也只能等着。现在计算机几乎都是多道程序系统内存里同时放着多个进程CPU必须在它们之间频繁切换才能让每个进程都感觉自己在独占机器。所以处理器管理实际上是一整套机制创建和注销进程、维护进程状态、调度哪个进程上CPU、处理并发过程中的竞争和死锁。它既是第二章的知识主干也是后面学内存管理、文件系统的基础。1.2 核心矛盾CPU太贵不能让它闲着处理器管理要解决的核心矛盾用一句话概括就是CPU速度快、内存和I/O设备慢如果让程序按顺序一个一个跑CPU大部分时间都在等待I/O白白浪费算力。想象一个程序执行过程一部分时间在CPU上计算一部分时间在等磁盘或键盘输入。单道程序下一个程序等I/O整台机器就一起等。多道程序设计的思想就是把多个程序同时放进内存当A进程等待I/O时CPU立刻切换去执行B进程。这样CPU的利用率能从百分之三四十提升到百分之八十以上。但多道带来的新问题立刻出现多个进程交替执行它们的变量、寄存器、指令指针怎么保存谁先谁后互相访问同一个文件怎么办互相等待资源出不来怎么办第二章的进程管理、调度、同步互斥、死锁全都是围绕这个核心矛盾展开的。把这层逻辑想清楚后面再多的算法细节都不会散的。1.3 本章三条主线我把整章内容归纳成三条主线执行单元怎么描述进程和线程是什么它们的状态怎么变操作系统如何保存它们的信息。CPU时间怎么分配调度算法有哪些分别适合什么场景评价指标是什么。并发环境怎么保证安全同步互斥解决竞争问题死锁机制解决资源循环等待问题。这三条线不是独立的。调度算法要面对一堆随时会阻塞和唤醒的进程同步互斥又要保证多个进程在“共同协作”时不乱套死锁又是在资源分配过程中产生的。学习的时候先分清这三块再去看每一块里的细节就不容易迷路。2. 进程操作系统眼里的“执行流”和那张PCB2.1 PCB进程的身份证字段到底装了什么进程为什么不是一个简单的“正在运行的程序”因为程序只是一堆静态的代码和数据放在磁盘上进程则是它被加载到内存后在动态执行过程中形成的完整“现场”。这个现场必须被记录下来否则CPU切换出去再切回来就不知道刚才算到哪了。记录现场的核心数据结构叫进程控制块PCBProcess Control Block也叫进程描述符。我习惯把PCB理解成“操作系统给人派发的一个档案袋”里面装着这个进程的全部信息主要包括进程标识符进程ID、父进程ID用来唯一识别进程。处理器状态信息程序计数器、通用寄存器、程序状态字寄存器等切换时靠这些恢复现场。进程调度信息进程状态、优先级、已等待时间、已运行时间、调度所需的其他参数。内存管理信息代码段、数据段、堆栈段的地址以及页表或段表的指针。文件管理信息打开的文件描述符列表、工作目录等。I/O状态信息进程正在等待的I/O设备、已经占用的通道等。记账信息CPU使用时间、运行时长、内存占用等用于统计和计费。PCB放在操作系统内核空间里用户程序不能随便改。有些教材会把PCB的各个字段画成一张大表我复习时的方法是自己先把PCB分类抄一遍再遮住分类、自己写出每个字段反复三轮就能记住。关键是要理解“为什么需要这些字段”进程一旦被打断所有执行现场都要被存进PCB下次才能无缝恢复。2.2 三态模型与状态转换怎么记才不会混进程在生命周期里不是一直“正在运行”的。最基本的模型有五种状态也有教材把它简化成三种核心状态创建态进程正在被创建PCB已经分配但还没进入就绪队列。就绪态进程已经准备好只要给他CPU就能运行。运行态进程正在CPU上执行。阻塞态进程因为等待某事件比如I/O完成或某个信号而暂停即使CPU空闲它也不能运行。终止态进程执行结束或出错系统正在回收它的资源。这里面最容易记混的是“阻塞”和“就绪”。我的记忆方法是就绪态是什么都不缺只缺CPU阻塞态是什么都有了但缺一个“特定事件”。所以调度器只会从就绪队列挑进程绝对不会把一个阻塞进程直接拿去运行。状态转换关系也很重要。允许的转换只有这么几条就绪 → 运行进程被调度选中。运行 → 就绪中断发生时间片用完或者被高优先级进程抢占。运行 → 阻塞进程主动请求某个资源或等待某事件。阻塞 → 就绪等待的事件完成进程被唤醒。创建 → 就绪系统完成PCB等初始化。运行 → 终止执行结束或被终止。我在考试里最容易踩的坑是“阻塞进程是不是一定在等待I/O”。不对阻塞还包括等待信号量、等待另一个进程的消息、等待加锁等。要抓住的本质是阻塞是“主动陷入等待”但这个主动不是说进程自愿而是它调用阻塞原语或请求系统服务内核把它挂起来了。2.3 上下文切换一次保存一次恢复调度器让一个进程离开CPU、另一个进程上CPU这个动作叫进程上下文切换。看似简单其实挺贵。上下文是保存任务状态的所有信息包括寄存器、程序计数器、PCB等内容。切换过程大致是保存当前进程的处理器现场到它的PCB。更新当前进程的状态为“就绪”或“阻塞”等。选一个就绪进程。从选中进程的PCB中恢复它的现场。更新状态为“运行”然后跳转。你可以把这个过程类比成两本书之间快速切换上一页读到第100行先夹上书签再拿起另一本翻到上次停下的地方。书签放得不好回来就要重新找CPU缓存也会变冷执行效率自然下降。这也解释了为什么进程不能切换得太频繁。系统里进程数量越来越多、时间片越来越短CPU用在“切换”而不是“干活”上的比例就会升高。所以操作系统后来才引入了线程让“切换执行流”的开销降到更低。3. 线程比进程更轻的执行流3.1 为什么进程切换太贵线程就出现了一个进程内部有时候需要同时做多件事比如网页浏览器既要下载图片又要响应用户点击还要渲染页面。如果每个任务都搞成一个独立进程那它们之间要共享数据就得通过进程间通信IPC成本高、代码复杂而且一堆进程占内存也非常浪费。线程就是更轻量的执行单位。一个进程内可以有多个线程它们共享进程的地址空间、全局变量、文件描述符这些资源但每个线程有自己独立的程序计数器、栈和寄存器。线程的切换基本只切换私有的执行现场不需要切换整个内存地址空间所以开销比进程切换小很多。3.2 进程和线程到底有什么不一样一张表讲清很多教材的考点就是对比进程和线程我把核心差异整理成表对比维度进程线程资源拥有进程是资源分配的单位拥有独立地址空间、文件等线程不独立拥有系统资源只拥有私有栈和寄存器调度单位传统系统中进程是CPU调度单位引入线程后线程才是调度单位切换开销需要切换页表、刷新缓存和TLB开销大共享进程资源切换开销小系统并发多进程能充分利用多核进程内多线程也能在多核并行通信方式需要IPC如管道、消息队列、共享内存直接读写共享变量但要同步健壮性一个进程崩溃不影响其他进程一个线程崩溃可能导致整个进程崩溃我在面试中被问过“线程越多越好吗”答案是显然不是。线程虽然轻但每个线程要有独立栈空间线程调度也有开销更重要的是多线程并发必然引入同步问题锁竞争反而会让程序变慢。所以线程的数量要配合任务类型和CPU核数不能无脑开。3.3 用户级线程与内核级线程三种模型别搞混线程的实现方式分为两类用户级线程线程的管理完全在用户空间完成内核根本不感知线程。线程库负责创建、调度、切换内核只把整个进程当作一个调度单位。好处是切换极快、可移植性好坏处是一个线程阻塞整个进程里的所有线程都会一起阻塞。内核级线程线程的创建和调度由内核管理每次系统调用、线程操作都要进内核。好处是多个线程可以并行到不同CPU上一个线程阻塞不影响同进程其他线程坏处是切换成本高。实际系统通常采用组合模型。教材里经常考三种映射关系多对一模型多个用户线程映射到一个内核线程。实现对用户级线程来说是高效但并行度受限阻塞问题严重。一对一模型每个用户线程对应一个内核线程。并行度高、更安全但线程切换要进内核开销大。多对多模型多个用户线程对应多个内核线程数量不完全相等。兼顾用户级线程的轻量和内核级线程的并行。这段真正要理解的是“用户态和内核态”的边界。用户级线程即使“同时”出现内核也只看到一个进程多个线程并不一定能跑在不同的CPU核心上想真并行还是得靠内核线程。4. 处理器调度CPU时间怎么分四大算法一次讲透4.1 调度算法要看哪些指标调度算法的好坏不能只看“快不快”要具体量化。常用的几个指标需要先记牢CPU利用率CPU忙碌时间占总时间的比例。理想越高越好。吞吐量单位时间内完成的进程数量。周转时间从进程提交到进程完成的总时间。周转时间 等待时间 运行时间。带权周转时间周转时间 / 服务时间这个值越接近1说明被服务得越顺畅。等待时间进程在就绪队列等待的总时间不包括运行和服务时间。响应时间从提交请求到产生第一次响应的时间。不同场景看重的指标不同。批处理系统更关注吞吐量和周转时间分时系统更关注响应时间。所以没有绝对最优的调度算法只有“适不适合当前场景”的算法。4.2 FCFS与SJF用一组数字看差距先看来得最早的两个算法。先来先服务FCFS按进程到达顺序调度优点是简单、公平缺点是前面一个长进程会堵住后面所有短进程导致平均等待时间非常难看。短作业优先SJF选择预计运行时间最短的进程先执行。平均周转时间理论上最短但它需要预知运行时间也容易出现“饥饿”——短进程源源不断到来长进程就一直排不上。我给出一个具体例子。假设4个进程同时到达运行时间分别是进程运行时间P17P24P31P44如果按 FCFS 顺序 P1、P2、P3、P4 执行完成时间分别是7、11、12、16。等待时间P10P27P311P412平均等待时间(071112)/47.5。周转时间P17P211P312P416平均周转时间(7111216)/411.5。如果按 SJF 顺序 P3、P2、P4、P1 执行完成时间分别是1、5、9、16。等待时间P30P21P45P19平均等待时间(0159)/43.75。周转时间P31P25P49P116平均周转时间(15916)/47.75。同一个任务序列仅仅是执行顺序不同平均等待时间从7.5降到了3.75效果立竿见影。这也是为什么SJF被称为“理论最优”的原因之一。4.3 RR与优先级调度时间片和优先级如何取舍时间片轮转调度RR是分时系统的主流选择。每个就绪进程轮流获得一个固定时间片如果进程没运行完就被强制排到队尾。时间片大小的选择很微妙。如果时间片太大RR等于FCFS响应不及时如果时间片太小上下文切换开销占比过高系统大部分时间都在切换。一般取10ms到100ms左右还要根据进程切换一次的开销来平衡。以刚才的例子假设时间片为4按P1、P2、P3、P4到达顺序调度运行过程会变成P1跑4还剩3P2跑4完成P3跑1完成P4跑4完成P1再跑3完成。平均等待时间会明显低于FCFS但比SJF差一些。关键是响应时间被大大缩短所有进程很快就能开始运行。优先级调度则是给每个进程一个优先级每次选优先级最高的进程运行。它的问题在于低优先级进程可能长时间得不到CPU解决办法是动态提高长时间等待进程的优先级也就是老化技术。还有一个经典坑叫优先级反转高优先级进程在等一个低优先级进程占用的资源反而被中等优先级进程抢先。现代系统会通过优先级继承解决这个问题。4.4 多级队列与多级反馈队列现代操作系统的答案多级队列调度的思路是把就绪队列分成多个独立队列每个队列有自己的调度算法比如前台队列用RR保证响应后台队列用FCFS保证吞吐队列之间还要决定优先级。多级反馈队列更进一步进程在运行过程中可以“降级”。新进程进入优先级最高的队列分配很小的时间片如果在时间片内没完成就掉到下一级队列时间片变长在最低队列里用FCFS兜底。这样短进程很快就能结束长进程慢慢往下沉。我在复习时觉得这段最容易理解偏总觉得“降级”是惩罚其实它只是让交互型短进程优先被处理让计算型长进程不至于饿死。现代很多操作系统的基本框架都能看到多级反馈队列的影子只是实际还会加入用户优先级、CPU亲和性等一堆细节。5. 同步与互斥并发安全的那道坎5.1 为什么两个进程不能同时改一个变量并发听起来美好但多个进程或线程共享同一个变量时如果大家都同时读写就会产生竞态条件。我经常用计数器举例变量count100进程A执行count进程B也执行count。count在机器层面通常要三步从内存把count读进寄存器寄存器加1写回内存。两个进程如果交错执行可能最后count只变成了101而不是102。这种场景在生活中很常见。好比两个人同时往一个账户里打钱银行系统如果不加锁余额就可能错得离谱。临界区就是访问公共资源的代码段我们要保证同一时间只有一个进程进入临界区其它进程必须在临界区外等待。5.2 临界区设计的四条原则操作系统教材里通常会提以下几条原则空闲让进临界区没人在用应该允许请求进入的进程进入。忙则等待一次只允许一个进程进临界区其它请求者必须等待。有限等待进程等待进入临界区的时间必须是有限的不能永远等不到。让权等待不能进入临界区的进程应释放 CPU避免忙等这条看教材版本有的单列。实现临界区互斥的硬件方法包括关中断、Test-and-Set指令、Swap指令等。关中断简单粗暴但它禁止不了多CPU环境下其它CPU的并发访问。TS指令能原子地完成“读取旧值 置为1”但可能会忙等浪费CPU。所以现代操作系统更多用信号量和管程。5.3 信号量P/V操作到底在干嘛信号量是一种更高级的同步工具。它本质上是一个整数变量支持两个原子操作wait也叫P操作或down信号量值减1如果小于0就阻塞。signal也叫V操作或up信号量值加1如果有正在等待的进程则唤醒一个。把信号量初始值设为1时它就是互斥锁初始值设为N就可以允许N个资源被同时访问。我学P/V操作时最容易混的是“减到负数表示什么”。负数表示等待进程的数量。比如信号量 -2就有两个进程在等待这个资源。这样理解之后再去写生产者消费者问题就不容易懵。很多教材用信号量实现“前驱关系”比如S1完成后才能执行S2。这时候可以设一个信号量初始为0S2前执行wait(S)S1后执行signal(S)就能保证执行顺序。这是一种非常灵活的同步表达方法。5.4 经典同步问题生产者消费者、读者写者、哲学家就餐这三个问题考试必考也是面试常客。生产者消费者问题一个缓冲区最多装n个产品生产者和消费者共享缓冲区。需要三个信号量empty表示空位full表示产品个数mutex保护缓冲区本身。semaphore mutex 1; semaphore empty n; semaphore full 0; producer() { while (true) { produce_item(); wait(empty); // 占一个空位 wait(mutex); // 加锁 put_item(); signal(mutex); // 解锁 signal(full); // 产品数加1 } } consumer() { while (true) { wait(full); // 消耗一个产品 wait(mutex); get_item(); signal(mutex); signal(empty); // 空位加1 consume_item(); } }注意P操作的顺序不能随意换。如果生产者先wait(mutex)再wait(empty)缓冲区满时它就会拿着锁睡觉消费者进不来双方一起死锁。所以一定要先申请资源信号量再去申请互斥锁。读者写者问题读者可以一起读写者必须独占。用“读锁”思路解决用一个计数器记录读者数量第一个读者进来时占用写互斥锁最后一个读者离开时释放锁。但这个方案有写者饥饿问题改进版本会让写者优先或公平交替。哲学家就餐问题5个哲学家围桌每人需要同时拿起左右两把叉子才能吃饭。如果每个人先拿左边再拿右边可能大家都只拿一把叉子最后谁都拿不到第二把形成死锁。解决办法有几个方向最多只允许4个人同时上桌或者让哲学家编号为奇数的先拿左再拿右、偶数先拿右再拿左或者用信号量强制“同时拿两把叉子”。这几个方案都要能自己推演不能只背结论。6. 死锁并发最麻烦的四个条件与解法6.1 死锁产生的四个必要条件死锁是多个进程因为竞争资源而造成的一种“互相等待、谁也没法推进”的状态。它必须同时满足四个条件互斥条件资源只能被一个进程占用。请求和保持条件进程已经持有一个资源又在请求新的资源而且不放掉已有资源。不可剥夺条件资源不能被系统强制抢走只能由进程自己释放。循环等待条件存在一个进程等待的闭环链比如P0等P1的资源P1等P0的资源。顺便说一句这四个条件是理解死锁的基础也是考试中判断“哪种情况会不会死锁”的起点。我那会儿总漏掉“循环等待”这一条其实循环等待是前三者的必然后果但也别因此就漏掉它。6.2 死锁预防、避免、检测与解除处理死锁有四种策略预防破除四个必要条件之一。比如打破互斥让资源改成可共享打破请求保持让进程一次申请全部资源打破不可剥夺增加资源剥夺机制打破循环等待给资源编号并要求按顺序申请。避免在资源分配之前通过算法判断安全性典型就是银行家算法。检测允许死锁发生系统定期检测检测到了再解除。解除终止进程剥夺资源或者资源抢占。6.3 银行家算法的核心算安全序列银行家算法是考试最容易出大题的地方也是很多自学者“一看就懂一做就错”的章节。其实只要把安全序列推出来问题就解决一大半。我用一个精简例子演示。现在有3类资源A、B、C当前可用资源为Available(1,1,1)。三个进程的分配和最大需求如下进程已分配Allocation最大需求Max还需求NeedP1(1,1,0)(3,2,1)(2,1,1)P2(0,0,1)(1,0,1)(1,0,0)P3(1,0,0)(3,1,1)(2,1,1)先看谁的需求能满足。P2的Need(1,0,0)当前Available(1,1,1)能满足。假设先执行P2它结束后释放已分配资源(0,0,1)可用变成(1,1,2)。接着看P1Need(2,1,1)可用(1,1,2)不够满足所以不能直接执行。再看P3Need(2,1,1)也无法满足。这时P1和P3都卡住安全序列应该怎么选这里我上面的例子有瑕疵P1的Need(2,1,1)需要A2可用A1不够。所以这个序列不是最优示例。让我重新给一个常见用例。重新用4个进程更清楚进程已分配Allocation最大需求Max还需求NeedP0(0,1,0)(3,2,2)(3,1,2)P1(2,0,0)(2,2,1)(0,2,1)P2(3,0,2)(5,1,1)(2,1,-1) 有一个负数说明数据不合法再调整。用常见教材经典例子还是5个进程那套反而更稳妥。我推荐直接用书上的标准示例Available(3,3,2)5个进程初始安全序列常见为P1、P4、P0、P2、P3之类的。因为本章字数已经很长这里不展开完整表格只把方法说透银行家算法的本质是避免死锁的贪心模拟。系统收到一个资源请求时先假设分配然后判断系统是否还处于安全状态。判断方法是从当前可用资源出发反复找“Need能够被Available满足”的进程分配给它等它结束后回收资源再找下一个。如果能把所有进程都排进一个序列说明安全可以分配否则不能分配。这个方法我在考试里的心得是先把Need表算出来把Available放在旁边然后在草稿纸上“画勾”每分配一个进程就划掉它并更新Available。只要动手推一遍比背十遍理论都管用。6.4 实际系统中死锁处理的设计取舍银行家算法的缺点是要求进程提前声明最大资源需求这个条件在实际系统中很难满足所以现代操作系统并没有普遍使用银行家算法。实际系统更多采用“鸵鸟算法”假装没有死锁真死锁了重启或者人工干预。但操作系统里也会看到一些实际防死锁手段比如文件系统中加锁的顺序约定、数据库事务里对锁进行超时回滚、多线程编程时统一锁的获取顺序。面试时如果你能把“预防”和“避免”的取舍讲清楚比如预防太保守、避免前期成本高、检测恢复复杂面试官一般就能满意。7. 常见问题排查与备考自查清单7.1 学习本章最容易踩的坑我自己总结了几类常见错误基本每次复习都能看到身边的人犯进程和程序分不清。程序是静态的存在磁盘里进程是动态的有生命周期有PCB。一个程序可以被多个进程同时执行。状态转换写错方向。记住“运行→阻塞”是主动等待“阻塞→就绪”是等待的事件完成没有“阻塞→运行”这种直接转换。调度算法的平均等待时间算错。算等待时间要只算等待不算运行和I/O算周转时间要从到达时间算到完成时间如果进程不是同时到达千万别直接把完成时间加起来平均。信号量的P/V顺序颠倒。生产者消费者问题里如果先加锁再查资源数就可能死锁。资源信号量优先互斥锁其次先P资源后P互斥是通用口诀。死锁的四个条件记不全。四大条件“互斥、请求保持、不可剥夺、循环等待”缺一不可判断题里但凡漏了一个就是错误答案。把共享变量读取不加锁看成“没问题”。很多并发bug是偶发的一次测不出来不代表不存在。7.2 复习节奏把这章变成一张A4纸我不建议上来就刷题。先把整章内容压缩成一张A4纸左边写进程状态图和PCB字段中间写调度算法对比右边写信号量和死锁条件。然后遮住内容默写看自己能还原多少。第一遍可能只能写出百分之五十没关系多默写几轮直到能画出完整的知识树。刷题的时候每遇到一个进程调度题都建议把“调度时机”想清楚这个算法是抢占式还是非抢占式如果是抢占式什么时候抢占比如SJF就有抢占式版本叫最短剩余时间优先SRTF它每次有新进程到达就重新选剩余时间最短的进程。题目里如果没说明是不是抢占默认可能要看上下文。最后一个小建议如果你手边有Linux或Mac电脑可以试试在命令行里运行 top 看进程状态再查查 ps 的STAT列里面经常出现Ssleeping和Rrunning、D不可中断睡眠。这些状态和教材里的进程状态对应起来你会有种“原来操作系统真的就是这么干”的实感。状态概念一旦落到具体系统里考试做题时就不容易忘了。