第二章的作业我来来回回做了三遍才真正做顺。第一遍对着课件抄答案第二遍把《计算机操作系统》慕课版翻了一遍第三遍才敢合上书自己推。现在回头看第二章进程的描述与控制的课后习题之所以让人头大不是题目本身有多难而是它把进程这一个概念拆成了前趋图、状态转换、PCB、同步互斥、进程通信、线程六七个侧面每一面的题都有自己的套路。你要是按题号从第一题老老实实做到最后一题很容易做着做着就乱了做到信号量那部分还会怀疑前面几节是不是白学了。这篇东西是我把计算机操作系统慕课版第二章习题分类整理之后的复盘包含各类题的解题思路和参考答案的写法也标出了我自己踩过的坑。汤小丹老师这本教材里进程管理是后面处理机调度、死锁、内存管理的前置知识第二章没吃透第三章讲调度的时候你会发现自己连就绪队列里排的到底是什么都说不清。所以不管你是跟着慕课视频学还是在准备期末复习这一章的题都值得认真做一遍而且最好做两遍第一遍按类型做第二遍合上书自己推。1. 第二章的知识地图一条主线串起六类习题1.1 从前趋关系到进程这条逻辑链很多人做第二章的题有个误区把前趋图当成一道孤立的画图题。其实整章的逻辑是一根链条先看程序顺序执行有什么特征——顺序性、封闭性、可再现性再看并发执行带来了什么变化——间断性、失去封闭性、不可再现性于是需要一个能描述并发执行、能被系统独立调度和分配资源的实体这就是进程。顺着这条线第二章的习题自然分成六类前趋图类、进程概念与特征类、状态转换类、进程控制PCB与原语类、同步互斥类、通信与线程类。每一类都在回答上一条链里产生的一个问题。你在做题的时候心里挂着这根链条就不会觉得知识点是散的。举个具体的例子。很多教材同步习题里会问为什么程序并发执行会失去可再现性 标准答案说的是多个程序共享系统资源执行过程中会受到其他程序的影响导致执行结果与执行速度有关。但你要是理解了链条可以答得更透因为并发执行打破了封闭性程序的执行不再只由自身初始条件决定还取决于调度时机所以同样的输入可能得到不同的结果。这种答法在主观题里更容易拿满分。1.2 六类题的难度分布与复习优先级按我自己的感受第二章习题的难度大致是这样的题型难度失分主因建议投入时间前趋图绘制与转换中漏边、重复计数2小时进程概念与特征辨析低只背不解释1小时状态转换合法性判断中混淆主动与被动2小时PCB与进程控制原语中步骤遗漏、顺序错2小时信号量与经典同步问题高P/V顺序错误、初值错6小时以上通信与线程对比低到中答得太笼统2小时这张表不是让你按顺序做恰恰相反——我建议先做概念辨析和状态转换这两块因为它们能快速建立信心而且做熟了之后再回去看同步问题你会发现信号量题里那些为什么阻塞的判断根基就在状态转换上。信号量放到最后集中攻因为它需要整块的时间中间被打断思路容易前功尽弃。还有一点要提醒慕课版的课后习题里选择题和判断题的数量比传统版本多这类题看似简单但特别爱在细节上设陷阱。比如进程是静态的这种说法就是错的进程的本质特征是动态性PCB才是静态的。这类题我吃过亏第一遍做的时候凭感觉选错了七八道。2. 状态转换与PCB把那张图画到能默写2.1 三态图和五态图的差别到底在哪第二章最基础的一道题通常是画出进程的三种基本状态及转换关系。三种基本状态是就绪、执行、阻塞。转换关系一共四条就绪到执行被调度、执行到就绪时间片用完或被抢占、执行到阻塞请求资源或I/O、阻塞到就绪资源到位或I/O完成。五态图多了创建态和终止态转换变成创建到就绪、执行到终止。如果是带挂起状态的七态图还要加上就绪挂起和阻塞挂起转换关系就复杂了就绪到就绪挂起、阻塞到阻塞挂起、就绪挂起到就绪激活、阻塞挂起到阻塞激活、阻塞挂起到就绪挂起等待的事件发生了但进程还在外存。这张图我建议你画到能默写的程度不是背文字而是画图。因为考试里的变式题往往是给你一句描述让你判断这个转换是否可能发生你脑子里有图就能秒答没图就只能靠猜。2.2 状态转换题的唯一判断规则所有的状态转换判断题只需要记住一条规则进程处于阻塞状态时不占用处理机而任何需要占用处理机才能发起的动作都不可能是从就绪态或阻塞态出发的。按这条规则下面这些说法都可以直接判错阻塞态可以直接转到执行态——错阻塞的进程没有处理机必须先回到就绪队列等被调度。就绪态可以直接转到阻塞态——错就绪态没有处理机没法发起导致阻塞的资源请求。执行态转就绪态是被动行为——错时间片用完是被动的但被更高优先级进程抢占也是被动的这两种都算被动转换而执行态转阻塞态才是主动的进程自己调用阻塞原语。下表是我整理的完整判断表建议对照记忆转换是否合法触发原因主动/被动就绪 → 执行合法调度程序选中被动执行 → 就绪合法时间片用完或被抢占被动执行 → 阻塞合法请求I/O或申请资源失败主动阻塞 → 就绪合法I/O完成或资源可用被动阻塞 → 执行非法必须先回到就绪队列—就绪 → 阻塞非法未占用处理机—执行 → 终止合法正常结束或异常终止主动2.3 挂起与激活两条最容易画错的边带挂起的题是第二章里最容易丢分的地方。核心是理解挂起这个动作意味着什么——进程被换出到外存不再参与内存中的调度竞争但它的PCB还在状态信息还保留。最容易错的是这两条边阻塞挂起到就绪挂起。这条边存在的原因很微妙一个被挂起的阻塞进程它等待的事件比如I/O完成发生了但因为它还在外存没法直接进入内存就绪队列所以只能先变成就绪挂起。很多人做这道题时会忘记这条边直接画成阻塞到就绪。就绪挂起到执行。这条边不存在。挂起的进程必须先激活换入内存变成就绪态才可能被调度。我当时的记法是挂起态之间可以互相转挂起态到内存态必须先激活。把这句话记住七态图的题基本不会错。PCB部分常考的题是PCB中应该包含哪些信息以及为什么说PCB是进程存在的唯一标志。前者的答案要分四块写进程标识符外部PID和内部标识符、处理机状态通用寄存器、指令计数器、程序状态字、用户栈指针、进程调度信息状态、优先级、等待事件、进程控制信息程序和数据地址、同步通信机制、资源清单、链接指针。后者要答出逻辑PCB是操作系统感知进程存在的唯一依据系统通过PCB来管理和调度进程一旦PCB被回收进程也就不存在了。所以创建进程本质上就是创建PCB撤销进程本质上就是回收PCB。这个理解在答进程控制原语那类题的时候会非常有用。3. 前趋图与并发执行把程序的关系翻译成约束3.1 前趋图怎么画才不丢边前趋图是第二章里少有的画图给分题但也是最容易因为粗心丢分的题。前趋图本质上是一个有向无环图结点表示语句、程序段或进程有向边表示前趋关系。画图的关键是逐条语句扫描找出每条语句直接依赖哪些语句而不是凭感觉连线。比如这样一段程序S1: a x y S2: b z 1 S3: c a - b S4: d c * 2 S5: e c d扫描过程是这样的S1用了x、y都是初始变量没有依赖S2用了z也没有依赖S3用了a和b而a来自S1、b来自S2所以S1→S3、S2→S3S4用了cc来自S3所以S3→S4S5用了c和d所以S3→S5、S4→S5。这样画出来的图有两条并列的起点S1和S2中间在S3汇聚最后在S5再次汇聚。丢边的典型情况是看到S5用了c就只画了S4→S5忘了S3→S5。所以我的习惯是画完之后倒着检查一遍——对每个结点问自己它的所有输入变量分别来自哪里这些来源我都连边了吗。3.2 前趋图转成信号量的标准写法前趋图题还有第二种考法把前趋图用信号量机制实现。这类题有完全固定的套路学会了就是送分题。规则是前趋图里有几条边就设几个信号量初值全部为0每条边的起点在执行完之后对它执行V操作终点在执行之前对它执行P操作。拿上面那张图来写。边有S1→S3、S2→S3、S3→S4、S3→S5、S4→S5一共五条边。semaphore a 0; // S1 - S3 semaphore b 0; // S2 - S3 semaphore c 0; // S3 - S4 semaphore d 0; // S3 - S5 semaphore e 0; // S4 - S5 // S1 a x y; V(a); // S2 b z 1; V(b); // S3 P(a); P(b); c a - b; V(c); V(d); // S4 P(c); d c * 2; V(e); // S5 P(d); P(e); e_val c d;这里有个细节值得强调如果一个结点有多条出边就在它执行完之后连续对这几个信号量做V操作如果一个结点有多条入边就在它开始之前连续对这几个信号量做P操作。P操作的先后顺序不影响正确性但如果出边的V操作分散在不同位置就说明你对程序结构的理解有问题。注意这里用变量名d既当信号量又当程序变量实际写答案的时候一定要换开不然阅卷老师会觉得你概念不清。这是我自己第一次做这道题时踩的坑虽然答案逻辑没错但被扣了分。3.3 并发执行时间那道计算题第二章还有一类计算题给出几个程序段的执行时间问顺序执行、并发执行各自需要多少时间。做这类题有两个前提要说清楚一是并发执行的时间取决于资源约束如果两段程序都要用同一个设备那它们实际上还是串行的二是并发的总时间等于关键路径的长度。举个例子S1需要30个单位时间S2需要20个单位时间S3需要50个单位时间其中S2依赖S1S3和S1、S2都无关。顺序执行是302050100。并发执行时S1和S3可以同时开始假设处理机足够S1跑30后S2开始跑20到第50时S2完成、S3也完成所以总共50个时间单位。这里有个隐藏考点如果题目说的是单处理机那无论怎么并发总时间都不会少于顺序执行的时间因为并发只是让多个程序交替占用处理机并不能真的同时执行。这一点在选择题里经常出现看到单处理机三个字就要警觉。4. 信号量与经典同步问题从会看到会写4.1 PV操作到底在做什么信号量这一节是第二章的重头戏也是计算机操作系统里最容易出大题的地方。先把PV操作的语义钉死// P操作wait申请资源 void P(semaphore s) { s.value--; if (s.value 0) { // 把当前进程加入s的等待队列并阻塞 block(s.L); } } // V操作signal释放资源 void V(semaphore s) { s.value; if (s.value 0) { // 从s的等待队列中唤醒一个进程 wakeup(s.L); } }很多人只记住P减V加但真正决定答案对不对的是那两行判断。判断里的**小于0和小于等于0**这一字之差是记录型信号量和整型信号量的分界线也是阅卷时的常见扣分点。更实用的是理解信号量值的含义当value大于0时它表示当前可用资源数当value等于0时表示资源刚好用完、没有进程在等当value小于0时它的绝对值表示当前在等待队列中阻塞的进程数。所以判断题里出现信号量S的值为-3说明有3个进程在等待这类说法是正确的而说明有3个可用资源就是错的。4.2 生产者-消费者缓冲区大小决定初值生产者-消费者问题是必考题但它有很多变体变量数量的不同会直接改写代码。我把它拆成两档来说。单缓冲区版本缓冲区只能放一个产品所以同一时刻只能有一个进程在里面操作。此时需要三个信号量mutex用于互斥访问缓冲区初值1empty表示空闲缓冲区数量初值1full表示已存放的产品数量初值0。semaphore mutex 1; semaphore empty 1; semaphore full 0; // 生产者 while (1) { item produce(); P(empty); // 先申请空位 P(mutex); // 再申请缓冲区访问权 put(item); V(mutex); V(full); // 通知消费者有产品了 } // 消费者 while (1) { P(full); // 先申请产品 P(mutex); item take(); V(mutex); V(empty); // 通知生产者有空位了 consume(item); }多缓冲区版本缓冲区大小变成n只需要把empty的初值改成n其余代码完全不变。这里有一个必须强调的点P(empty)和P(mutex)的顺序不能颠倒。假如生产者写成先P(mutex)再P(empty)那么当缓冲区满时生产者持有了mutex却因为empty为0而阻塞此时消费者想取产品又因为拿不到mutex而阻塞双方互相等待形成死锁。这个死锁分析题在很多学校的期末卷子上出现过答的时候要画清楚持有和等待的关系。至于V操作的顺序倒是不影响正确性但先V(mutex)再V(full)是更规范的习惯因为它能让等待资源的进程尽可能早地被唤醒。这一点属于经验不是硬性规定但写出来会显得你对临界区的边界理解得更清楚。4.3 读者-写者与哲学家进餐三种改法的对比读者-写者问题的核心是多个读者可以同时读写者必须独占且写者与读者之间互斥。最基本的解法是引入一个整型变量readcount记录当前读者数量用rmutex保护readcount本身用wmutex保护共享文件。semaphore rmutex 1, wmutex 1; int readcount 0; // 读者 P(rmutex); if (readcount 0) P(wmutex); // 第一个读者负责关上门 readcount; V(rmutex); read_file(); P(rmutex); readcount--; if (readcount 0) V(wmutex); // 最后一个读者负责打开门 V(rmutex); // 写者 P(wmutex); write_file(); V(wmutex);这段代码里有三个容易出错的点。第一判断readcount时用的是 0不要写成 0。第二对readcount的加一减一必须在rmutex的保护范围内否则多个读者同时修改会出错。第三也是很多人忽略的——这个版本是读者优先的只要还有读者在读写者就一直等着严重时写者会被饿死。如果题目要求写者优先就得再加一个信号量来控制读者和写者的排队顺序代码会长一倍。考试时如果题目没说要写者优先写读者优先版本就行但可以补一句如果需要写者优先需要额外引入一个信号量来实现公平排队这是加分项。哲学家进餐问题问的是五个哲学家围坐一桌每两人之间放一根筷子哲学家需要同时拿到左右两根筷子才能进餐怎么用信号量实现且不发生死锁。最直接的写法是让每个哲学家先拿左再拿右但这个写法会导致死锁——五个人同时拿起左边筷子然后都在等右边。解决办法有四种我按答题的性价比排序解法核心思路优点缺点限制人数最多允许4人同时拿筷子改动最小只需一个信号量并发度降低AND信号量要求左、右筷子同时可用才分配语义清晰不死锁需要支持原子申请奇偶编号奇数号先左后右偶数号先右后左不引入新信号量逻辑绕容易写错管程用管程封装拿筷子和放筷子结构最清晰代码量大限制人数的写法最省事加一个初值为4的信号量countsemaphore chopstick[5] {1, 1, 1, 1, 1}; semaphore count 4; // 第 i 个哲学家 while (1) { P(count); // 最多4人同时尝试 P(chopstick[i]); // 拿左筷 P(chopstick[(i 1) % 5]); // 拿右筷 eat(); V(chopstick[i]); V(chopstick[(i 1) % 5]); V(count); think(); }有一个坑必须点出来P(count)必须放在最前面。如果放在两根筷子之后限流就失效了因为进程已经先持有了一根筷子还是可能凑成环路。我在第一次写这题的时候就把count那个P放在了中间表面上看代码跑得通但一分析极端情况就露馅了。4.4 同步题答题时的四个扣分点做完十几道信号量的题之后我总结出阅卷时最容易扣分的四个地方你们可以对号入座信号量初值写错。empty写成n还是1取决于缓冲区大小别想当然。full和empty的初值之和等于缓冲区总数这个恒等式可以自查。P操作顺序颠倒。凡是涉及先申请资源、再申请互斥锁的场景资源信号量的P永远在互斥信号量的P前面。变量没声明或类型混淆。readcount、count这类整型变量要单独声明不能和信号量混在一起写。忘记写循环和结束条件。生产者-消费者是无限循环写代码时不要漏掉while(1)。5. 进程通信、管程与线程概念题怎么写得不空泛5.1 三种通信方式答题要答出适用场景第二章后半部分讲进程通信课后题通常问进程通信有哪几种方式各有什么特点。这种题如果只写共享存储器、消息传递、管道三行字最多拿一半分。要把每种方式的适用场景和代价写出来。共享存储器系统分两个层次。低级的是基于共享数据结构的通信比如用共享变量加同步机制只适合传递少量数据程序员要自己处理互斥。高级的是基于共享存储区的通信系统在内存中划出一块区域进程直接在这块区域上读写速度快适合传输大量数据但同步问题仍然要自己解决。消息传递系统是当前用得最广的。它分成两种直接通信方式下发送进程明确指定接收进程的标识系统提供的原语是send和receive间接通信方式下消息先发到一个中间实体信箱接收方从信箱取收发双方不需要知道对方是谁解耦程度更高。这种方式的好处是可靠性高、适合分布式环境代价是需要内核参与开销比共享内存大。管道通信是连接读写进程的一个共享文件本质上是内存中的一块固定大小的缓冲区。它的关键是三条约束一是半双工同一时刻只能单向传输二是读写互斥同时只能有一个进程操作管道三是要同步管道空时读进程阻塞管道满时写进程阻塞。另外只有确定了对方存在管道才有意义。答这类题时我的习惯是最后加一句结论选择哪种方式取决于数据量、实时性要求和进程是否在同一台机器上。这句话能把三种方式的对比收成一个判断标准阅卷时是明显的加分点。5.2 管程的三条特性管程这部分内容不多但容易出判断题。管程的定义是代表共享资源的数据结构以及对该数据结构实施操作的一组过程所组成的资源管理程序。它有三条特性模块化、抽象数据类型、信息掩蔽。更关键的是理解管程和信号量的关系。管程把所有对共享变量的操作封装在内部进程只能通过管程提供的入口过程访问资源而且同一时刻只允许一个进程进入管程。这个互斥是由编译器负责实现的不需要程序员自己写P/V这正是管程比裸信号量更安全的地方。答管程与信号量的区别这类题时可以这样组织信号量是低层的同步机制需要程序员自己保证P/V的配对和顺序容易出错管程是高层的同步机制把同步逻辑封装在内部程序员只需要调用过程出错概率低。同时管程内部仍然可以用条件变量来实现等待和唤醒所以它并没有抛弃信号量的思想而是把它包装起来了。5.3 进程与线程的区别怎么答出层次线程是第二章的收尾内容课后题一般会问线程与进程的区别。这道题几乎人人都会答但答出层次的不多。我建议按下面这个表格的五个维度来写每个维度一句话结构清楚不容易漏。维度进程线程调度单位传统系统中是独立调度单位引入线程后成为独立调度和分派的基本单位并发性进程之间可以并发同一进程内的多个线程也可以并发并发度更高资源拥有拥有独立的地址空间和系统资源基本不拥有资源共享所属进程的资源系统开销创建、撤销、切换开销大切换只需保存少量寄存器内容开销小地址空间相互独立通信需要借助通信机制共享同一地址空间通信直接通过共享变量如果题目进一步问用户级线程和内核级线程的区别就要从谁在管理这个角度切入。用户级线程由用户程序库管理内核完全不知道线程的存在所以切换不需要陷入内核速度快但缺点是一个线程发起阻塞式系统调用整个进程都会被阻塞而且无法利用多处理机的并行能力。内核级线程由操作系统内核管理可以调度到不同的处理机上真正并行执行一个线程阻塞不影响其他线程代价是线程切换必须经过内核开销比用户级线程大。还有一种组合方式就是把两者结合比如多对一、一对一、多对多模型。答到这里其实已经超出基础要求了但如果你在复习的时候顺手把这块补上主观题遇到请分析几种线程实现方式的优缺点就不会慌。6. 我做这套习题的顺序和复盘方法第二章的题做完之后我最大的体会是进度慢不是因为题多而是因为知识点之间没有连起来。前面我提到六类题的分类其实这个分类本身就是一种复习方法——你每做完一类就在笔记上写一句这类题的核心判断依据是什么全部写完一章的骨架就出来了。关于做题顺序我后来调整成了这样先做概念辨析和状态转换因为这两块反馈快能快速找到学习节奏然后做PCB和进程控制原语这两块是背多分但要注意步骤顺序我一般会自己画一张流程图不看书画两遍接着做前趋图画图题手感很重要隔一天不画就会手生最后集中火力攻信号量一次至少留出两小时中间不打断做完之后当天晚上再复盘一遍。错题本的记法我也想多说两句。我一开始记的是答案是什么但发现下次遇到变式题照样不会。后来改成记我当时为什么那么想效果完全不一样。比如生产者-消费者那道题我做错了我在错题本上写的不是正确代码而是我以为mutex要先拿觉得先锁住缓冲区更安全但实际上锁的粒度太大会导致死锁——先申请资源信号量是因为资源不足时阻塞不会持有互斥锁。这个思路其实就是一句话同步题的错误九成都能归结到谁持有锁的时候被阻塞了。你只要在做题时习惯性地问自己这个问题绝大多数死锁错误都能提前发现。还有个细节是我在复习后期才意识到的第二章的那些经典同步问题本质上都是在给互斥和同步这两种关系配对。互斥是多个进程抢一个资源需要一把锁同步是多个进程之间有先后顺序需要一个信号量来传递我完成了。你把每道题里的这两种关系标出来代码结构基本就自动浮现了。我后来做陌生的同步题会先在草稿纸上写两行哪些资源是互斥访问的哪些动作之间有先后依赖。这两行写完剩下的就是套模板。如果你也在啃计算机操作系统慕课版第二章别急着往后翻。这一章的题做透了后面调度算法、死锁避免那些内容会顺很多做不透你会发现后面每一章都在还债。