操作系统作业讲解

1、第二章 习题讲解1、进程之间存在着哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关 系？（1）若干同学去图书馆借书； （ 2）两队举行篮球比赛； （ 3）流水线生产的各道工序； （4） 商品生产和社会消费。答：进程之间存在着直接制约与间接制约这两种制约关系，其中直接制约（同步） 是由于进 程间的相互合作而引起的，而间接制约（互斥）则是由于进程间共享临界资源而引起的。 （1）若干同学去图书馆借书，是间接制约，其中书是临界资源；（ 2）两队举行篮球比赛，是间接制约，其中蓝球是临界资源； （ 3）流水线生产的各道工序，是直接制约，各道工序间 需要相互合作， 每道工序的开始都依赖于前一道

2、工序的完成； （ 4）商品生产和社会消费，是 直接制约， 两者也需要相互合作： 商品生产出来后才可以被消费； 商品被消费后才需要再生 产。2、试写出相应的程序来描述下图所示的前趋图var a,b,c,d,e,f:semaphore:=0,0,0,0,0,0; begin S1; signal(a); signal(b); signal(c); end; begin wait(a); S2; end;begin wait(b); S3; signal(d); end;begin wait(c); S4; end;begin wait(d); S5; signal(e); signal(f); e

3、nd; begin wait(e); S6; end;begin wait(f); S7; end;3、已知一个求值公式 （A23B）/（B+5A） ，若 A、B 已赋值，试画出该公式求值过程的前趋图， 并使用信号量描述这些前趋关系。答：根据求值公式，假设：S1: X1=A*AS2: X2=3*BS3: X3=5*AS4: X4=X1+X2S5: X5=B+X3S6: X6=X4/X5var a,b,c,d,e:semaphore:=0,0,0,0,0;begin S1; signal(a); end;begin S2; signal(b); end;begin S3; signal(c);

4、end;begin wait(a); wait(b); S4; signal(d); end begin wait(c); S5; signal(e); end begin wait(d); wait(e); S6; end4、桌上有一只能容纳一个水果的盘子；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子 (orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果，1)试用信号量实现他们的同步关系； 2)如果有两个家庭的爸爸、妈妈、儿子、女儿和二只盘子呢？ 会需要专门的实现吗？var empty,apple,orange:semaphore:= 1,0,0;说明： em

5、pty 与 apple 表示盘子为空与盘子中放入了苹果，用于表示爸爸与女儿间的同步关 系；empty 与 orange 表示盘子为空与盘子中放入了桔子， 用于表示妈妈与儿子间的同步关系； 答案： 1)使用记录型信号量father:begindaughter:beginrepeatrepeatproducer an apple;wait(apple);wait(empty);Get an apple from dish;Put an apple to the dish;signal(empty);signal(apple);Eat an apple;Until falseUntil falsee

6、ndendmother:beginson:beginrepeatrepeatproducer an orange;wait(orange);wait(empty);Get an orange from dish;Put an orange to the dish;signal(empty);signal(orange);Eat an orange;Until falseUntil falseendend2)使用记录型信号量var mutex,empty,apple,orange:semaphore:=1,2,0,0; dish: array0,1 of fruit;in, out:intege

7、r:= 0,0;father:begindaughter:beginrepeatrepeatproducer an apple;wait(apple);wait(empty);wait(mutex);wait(mutex);if dishout=orange thenif dishin=apple or dishin=orange thenout:=(out+1) mod 2;in:=(in+1) mod 2;get an apple from dishout;diskin:=apple;out:=(out+1) mod 2;in:=(in+1) mod 2;signal(mutex);sig

8、nal(mutex);signal(empty);signal(apple);Eat an apple;Until falseUntil falseendEndmother:beginson:beginrepeatrepeatproducer an orange;wait(orange);wait(empty);wait(mutex);wait(mutex);if dishout=apple thenif dishin=apple or dishin=orange thenout:=(out+1) mod 2;in:=(in+1) mod 2;get an orange from dishou

9、t;diskin:=orange;out:=(out+1) mod 2;in:=(in+1) mod 2;signal(mutex);signal(mutex);signal(empty);signal(orange);Eat an apple;Until falseUntil falseendend5、试用信号量实现课件 92 页，司机与售票员进程的同步关系 var stop, door :semaphore:=0,0;driver:beginconductor:beginrepeatrepeatdrive a bus;sell tickets;arrive at bus station;w

10、ait(stop);signal(stop);Open the door;rest;Close the doorwait(door);signal(door);Until falseUntil falseendend6、试用信号量解决读者写者问题，使得写者与读者优先级根据到达顺序确定。1) 典型错误代码讲解：不增加任何信号量Var rmutex, wmutex:semaphore Readcount:integer = 0;parbeginReader:beginwait(rmutex);if Readcount=0 then wait(wmutex);Readcountsignal(rmut

11、ex);wait(rmutex);Readcount = Readcount-if Readcount=0 then signal(wmutex);writer:beginif readcount0 then wait(rumtex); wait(wmutex);perform writsignal(rmutex);parendend到达序列： R1, R2, W1, R3, R4, W2进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行 /就绪第 1 位读者R2到达rmutex=0rmute

12、x=1Readcount=2执行 /就绪W1到达rmutex=0阻塞 1阻塞Readcount0R3到达阻塞 1阻塞rmutex=0R4到达阻塞 2阻塞rmutex=0W2到达阻塞 3阻塞rmutex=0R1离开阻塞 4阻塞rmutex=0R2离开阻塞 5阻塞rmutex=0产生死锁2)学习指导与题解上的解题思路答：为使写者优先，可在原来的读优先算法基础上增加一个初值为 1 的信号量 S，使得当至 少有一个写者准备访问共享对象时， 它可使后续的读者进程等待写完成。 初值为 0 的整 型变量 writecount 用来对写者进行计数； 初值为 1 的互斥信号量 mutex 用来实现多个写 者对

13、writecount 的互斥访问。读者与写者进程算法描述如下： var S, mutex, rmutex, wmutex: semaphore:=1,1, 1,1;writecount, readcount: integer:=0,0;reader: beginrepeatwait(S);wait(rmutex);if readcount=0 then wait(wmutex) ;readcount:=readcount+1;signal(rmutex);signal(S);perform read operation;wait(rmutex); readcount:=readcount-1;

14、if readcount=0 then signal(wmutex) ; signal(rmutex);until falseendwriter: beginrepeatwait(mutex);if writecount=0 then wait(S) ; writecount:=writecount+1; signal(mutex); wait(wmutex) ;perform write operation; signal(wmutex);wait(mutex); writecount:=writecount-1;if writecount=0 then signal(S); signal(

15、mutex);until falseend到达序列： R1, R2, W1, R3, R4, W2进程行为S=1mutex=1rmutex=1wmutex=1writecount=0readcount=0备注R1到达S=0S=1rmutex=0rmutex=1wmutex=0readcount=1第一个读者执行 /就 绪R2到达S=0S=1rmutex=0rmutex=1readcount=2执行 /就 绪W1到达S=0mutex=0mutex=1阻塞 1writecount=1第一个写者R3到达阻塞 1R4到达阻塞 2W2到达mutex=0mutex=1阻塞 2writecount=2R1离

16、开rmutex=0rmutex=1readcount=1R2离开rmutex=0rmutex=1wmutex=1readcount=0负责唤 醒 W1W1被唤醒wmutex=0执行 /就 绪W1离开mutex=0mutex=1wmutex=1writecount=1负责唤醒 W23）改写上述代码，真正实现读写平等策略var S, rmutex, wmutex: semaphore:=1, 1,1;readcount: integer:= 0;reader: beginrepeatwait(S); wait(rmutex);if readcount=0 then wait(wmutex) ; r

17、eadcount:=readcount+1; signal(rmutex);signal(S);perform read operation; wait(rmutex); readcount:=readcount-1;if readcount=0 then signal(wmutex) ; signal(rmutex);until falseendwriter: beginrepeatwait(S) ; wait(wmutex) ; perform write operation; signal(wmutex); signal(S);until falseend到达序列： R1, R2, W1

18、, R3, R4, W2进程行为S=1rmutex=1wmutex=1readcount=0备注R1到达S=0rmutex=0wmutex=0readcount=1第一个读者 执行 / 就绪S=1rmutex=1R2到达S=0S=1rmutex=0rmutex=1readcount=2执行 / 就绪W1到达S=0阻塞 1第一个写者R3到达阻塞 1R4到达阻塞 2W2到达阻塞 3R1离开rmutex=0rmutex=1readcount=1R2离开rmutex=0rmutex=1wmutex=1readcount=0负责唤醒 W1W1被唤醒wmutex=0执行 / 就绪W1离开S=1wmutex

19、=1负责唤醒 R37、试说明 PCB 的作用，为什么说 PCB 是进程存在的唯一标志？（课本第 7 题） 答：进程控制块的作用， 是使一个在多道程序环境下不能独立运行的程序， 成为一个能独立 运行的基本单位，即一个能与其他进程并发执行的进程。 在创建进程时，系统将为它配置一个 PCB；在进行进程调度时，系统将根据 PCB 中的 状态和优先级等信息来选择新进程，然后将老进程的现场信息保存到它的 PCB 中，再 根据新进程 PCB 中所保存的处理机状态信息来恢复运行的现场；执行中的进程，如果 需要访问文件或者需要与合作进程实现同步或通信，也都需要访问 PCB；当进程因某 种原因而暂停执行时，也必须

20、将断点的现场信息保存到它的 PCB 中；当进程结束时， 系统将回收它的 PCB。可见，在进程的整个生命周期中，系统总是通过其 PCB 对进程 进行控制和管理， 亦即，系统是根据其 PCB 而不是任何别的什么而感知到进程的存在， 所以说， PCB 是进程存在的唯一标志。8、同步机构应遵循哪些基本准则？为什么？（课本第18 题）答：空闲让进、忙则等待、有限等待、让权等待。这样才能保证多个进程对临界资源的互斥 访问，不会造成系统的混乱、程序执行结果的不确定性或死锁的产生。9、试从物理概念上说明记录型信号量wait 和 signal。（课本第 19 题）答：一个信号量通常对应一类临界资源，在使用前，信

21、号量必须经过定义并赋适当的初值。每次对它进行 wait 操作意味着申请一个单位的该资源， signal 操作操作意味着归还一个 单位的该类资源。当 S.value0 时，它的值表示系统中该类资源当前可用的数目； S.value=0 时，表示该类资源已经分配完毕， 其绝对值表示系统中因申请资源而阻塞在 S.L 队列上的进程数目。10、在生产者消费者问题中，如果缺少了signal(full) 或 signal(empty)，对执行结果将会有何影响？(课本第 23 题)答：如果生产者进程中缺少了 signal(full) ，生产者一开始是不断往缓冲池送消息，而消费者 一开始就因为 full 为 0

22、而处于阻塞状态， 当所有缓冲区装满之后， 由于 empty 由 n 减为 0，而消费者已经阻塞，生产者也会因为wait(empty) 而处于阻塞状态。产生死锁。消费者进程中缺少了 signal(empty) ，缓冲区指针 in 从 0 指向了 n-1 后，生产者就会因为 执行 wait(empty) 处于阻塞状态；生产者阻塞后，消费者消费掉所有的产品，即缓冲区 指针 out 从 0 指向了 n-1 后，也会因为执行 wait(full) 处于阻塞状态。产生死锁。11、我们为某临界资源设置一把锁W ，当 W=1 时表示关锁；当 W=0 时表示锁已经打开，试写出开锁和关锁原语，并利用它们去实现互斥。 (课本第 25 题) 答：相应的关锁原语 lock(W) 和开锁原语 unlock(W) 可描述如下：lock(W): while W=1 do no-op;W:=1;unlock(W): W:=0;在利用关锁原语和开锁原语实现进程互斥时，可将临界区 CS 放在其间，即： lock(W);CS;unlock(W);12、当前有哪几种高级通信机制？(课本