操作系统作业讲解

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

2、会消费，是直接制约，两者也需要相互合作：商品生产出来后才可以被消费；商品被消费后才需要再生产。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); end;begin wait(e); S6; en

3、d;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+X3 S6: 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); end;begin wait(a); wait(b);

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

5、女儿间的同步关系；empty与orange表示盘子为空与盘子中放入了桔子，用于表示妈妈与儿子间的同步关系；答案：1）使用记录型信号量father:begin repeat producer an apple; wait(empty); Put an apple to the dish;signal(apple); Until falseenddaughter:begin repeatwait(apple); Get an apple from dish;signal(empty);Eat an apple; Until falseendmother:begin repeat producer

6、an orange; wait(empty); Put an orange to the dish;signal(orange); Until falseendson:begin repeatwait(orange); Get an orange from dish;signal(empty);Eat an orange; Until falseend2）使用记录型信号量var mutex,empty,apple,orange:semaphore:=1,2,0,0;dish: array0,1 of fruit;in, out:integer:= 0,0;father:begin repeat

7、 producer an apple; wait(empty);wait(mutex); if dishin=apple or dishin=orange then in:=(in+1) mod 2; diskin:=apple; in:=(in+1) mod 2; signal(mutex);signal(apple); Until falseenddaughter:begin repeatwait(apple);wait(mutex); if dishout=orange then out:=(out+1) mod 2;get an apple from dishout; out:=(ou

8、t+1) mod 2; signal(mutex);signal(empty);Eat an apple; Until falseEndmother:begin repeat producer an orange; wait(empty);wait(mutex); if dishin=apple or dishin=orange then in:=(in+1) mod 2; diskin:=orange; in:=(in+1) mod 2; signal(mutex); signal(orange); Until falseendson:begin repeatwait(orange);wai

9、t(mutex); if dishout=apple then out:=(out+1) mod 2; get an orange from dishout; out:=(out+1) mod 2; signal(mutex);signal(empty);Eat an apple; Until falseend5、试用信号量实现课件92页，司机与售票员进程的同步关系var stop, door :semaphore:=0,0;driver:begin repeat drive a bus;arrive at bus station;signal(stop); rest; wait(door);

10、 Until falseendconductor:begin repeatsell tickets;wait(stop); Open the door; Close the doorsignal(door); Until falseend6、试用信号量解决读者写者问题，使得写者与读者优先级根据到达顺序确定。1）典型错误代码讲解：不增加任何信号量Var rmutex, wmutex:semaphore=1,1; Readcount:integer =0; begin parbegin Reader:begin repeat wait(rmutex); if Readcount=0 then wa

11、it(wmutex); Readcount = Readcount+1; signal(rmutex); perform read operation; wait(rmutex); Readcount= Readcount-1; if Readcount=0 then signal(wmutex); signal(rmutex); until false; end writer:begin repeat if readcount>0 then wait(rumtex); wait(wmutex); perform write operation; signal(rmutex); sign

12、al(wmutex); until false; end parend end到达序列：R1, R2, W1, R3, R4, W2进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者R2到达rmutex=0rmutex=1Readcount=2执行/就绪W1到达rmutex=0阻塞1阻塞Readcount>0R3到达阻塞1阻塞rmutex=0R4到达阻塞2阻塞rmutex=0W2到达阻塞3阻塞rmutex=0R1离开阻塞4阻塞rmutex=0R2离开阻塞5阻塞rmutex

13、=0产生死锁2）学习指导与题解上的解题思路答：为使写者优先，可在原来的读优先算法基础上增加一个初值为1的信号量S，使得当至少有一个写者准备访问共享对象时，它可使后续的读者进程等待写完成。初值为0的整型变量writecount用来对写者进行计数；初值为1 的互斥信号量mutex用来实现多个写者对writecount的互斥访问。读者与写者进程算法描述如下： var S, mutex, rmutex, wmutex: semaphore:=1,1, 1,1; writecount, readcount: integer:=0,0;reader: begin repeat wait(S); wait(

14、rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); signal(S); perform read operation; wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false end writer: begin repeat wait(mutex); if writecount=0 then wait(S); writecount:=

15、writecount+1; signal(mutex); wait(wmutex); perform write operation; signal(wmutex); wait(mutex); writecount:=writecount-1; if writecount=0 then signal(S); signal(mutex); until false end到达序列：R1, R2, W1, R3, R4, W2进程行为S=1mutex=1rmutex=1wmutex=1writecount=0readcount=0备注R1到达S=0S=1rmutex=0rmutex=1wmutex=

16、0readcount=1第一个读者执行/就绪R2到达S=0S=1rmutex=0rmutex=1readcount=2执行/就绪W1到达S=0mutex=0mutex=1阻塞1writecount=1第一个写者R3到达阻塞1R4到达阻塞2W2到达mutex=0mutex=1阻塞2writecount=2R1离开rmutex=0rmutex=1readcount=1R2离开rmutex=0rmutex=1wmutex=1readcount=0负责唤醒W1W1被唤醒wmutex=0执行/就绪W1离开mutex=0mutex=1wmutex=1writecount=1负责唤醒W23）改写上述代码，真

17、正实现读写平等策略 var S, rmutex, wmutex: semaphore:=1, 1,1; readcount: integer:= 0;reader: begin repeat wait(S); wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); signal(S); perform read operation; wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex)

18、; signal(rmutex); until false end writer: begin repeat wait(S); wait(wmutex); perform write operation; signal(wmutex); signal(S); until false end到达序列：R1, R2, W1, R3, R4, W2进程行为S=1rmutex=1wmutex=1readcount=0备注R1到达S=0S=1rmutex=0rmutex=1wmutex=0readcount=1第一个读者执行/就绪R2到达S=0S=1rmutex=0rmutex=1readcount=2

19、执行/就绪W1到达S=0阻塞1第一个写者R3到达阻塞1R4到达阻塞2W2到达阻塞3R1离开rmutex=0rmutex=1readcount=1R2离开rmutex=0rmutex=1wmutex=1readcount=0负责唤醒W1W1被唤醒wmutex=0执行/就绪W1离开S=1wmutex=1负责唤醒R37、试说明PCB的作用，为什么说PCB是进程存在的唯一标志？（课本第7题）答：进程控制块的作用，是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，即一个能与其他进程并发执行的进程。 在创建进程时，系统将为它配置一个PCB；在进行进程调度时，系统将根据PCB中的状态

20、和优先级等信息来选择新进程，然后将老进程的现场信息保存到它的PCB中，再根据新进程PCB中所保存的处理机状态信息来恢复运行的现场；执行中的进程，如果需要访问文件或者需要与合作进程实现同步或通信，也都需要访问PCB；当进程因某种原因而暂停执行时，也必须将断点的现场信息保存到它的PCB中；当进程结束时，系统将回收它的PCB。可见，在进程的整个生命周期中，系统总是通过其PCB对进程进行控制和管理，亦即，系统是根据其PCB而不是任何别的什么而感知到进程的存在，所以说，PCB是进程存在的唯一标志。8、同步机构应遵循哪些基本准则？为什么？（课本第18题）答：空闲让进、忙则等待、有限等待、让权等待。这样才能

21、保证多个进程对临界资源的互斥访问，不会造成系统的混乱、程序执行结果的不确定性或死锁的产生。9、试从物理概念上说明记录型信号量wait和signal。（课本第19题）答：一个信号量通常对应一类临界资源，在使用前，信号量必须经过定义并赋适当的初值。每次对它进行wait操作意味着申请一个单位的该资源，signal操作操作意味着归还一个单位的该类资源。当S.value>0时，它的值表示系统中该类资源当前可用的数目；S.value<=0时，表示该类资源已经分配完毕，其绝对值表示系统中因申请资源而阻塞在S.L队列上的进程数目。10、在生产者消费者问题中，如果缺少了signal(full)或si

22、gnal(empty)，对执行结果将会有何影响？（课本第23题）答：如果生产者进程中缺少了signal(full)，生产者一开始是不断往缓冲池送消息，而消费者一开始就因为full为0而处于阻塞状态，当所有缓冲区装满之后，由于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);