操作系统第二章 进程习题2

1、,Page 1,2020/7/19,第二章 进程,操作系统,Page 2,2020/7/19,回答,1.两个可以并发执行的程序都分别包含输入、计算和打印3个程序段，即I1,C1,P1和I2,C2,P2，前趋关系如图所示，试用信号量机制实现它们的同步关系。,I1,C1,P1,I2,C2,P2,Page 3,2020/7/19,回答,1.答： 构造两程序的制约关系如下,I1,C1,P1,I2,C2,P2,a,b,c,d,e,f,g,Page 4,2020/7/19,回答,. 接上页 则同步关系如下 Var a,b,c,d,e,f,g: semaphore=0,0,0,0,0,0,0; begin

2、parbegin begin I1; signal(a); signal(c); end; begin wait(a); C1; signal(b); signal(d); end; begin wait(b); P1; signal(e); end; begin wait(c); I2; signal(f); end; begin wait(d);wait(f);C2; signal(g); end; begin wait(e); wait(g); P2; end; parend end,Page 5,2020/7/19,回答,2.有3个并发进程R,M,P，它们共享同一缓冲区。进程R负责从输

3、入设备读信息，读入一个记录后将它放入缓冲区；进程M在缓冲区中加工读入的记录；进程P将加工后的记录打印输出。输出完成后缓冲区又可以存放下一个记录。试写出它们能够正确并发执行的程序。,Page 6,2020/7/19,回答,答：这是一个生产者-消费者问题。R,M,P之间存在如下的制约关系,R,M,P,a,b,c,Page 7,2020/7/19,回答,程序如下 var a,b,c:semaphore:=0,0,1; begin cobegin R: begin repeat wait(c); input a record from input device; signal(a); until fa

4、lse end; M: begin repeat wait(a); manual the record in buffer; signal(b); end;,P: begin repeat wait(b); print the result; signal(c); end; coend end,Page 8,2020/7/19,回答,3.记录型信号量中的wait(S)和signal(S)操作为何要设计成原语。,Page 9,2020/7/19,回答,答：记录型信号量的操作如下 type semaphore=record value: integer; L : list of process;

5、end procedure wait(S) var S : semaphore; begin S.value:= S.value-1; if S.value0 then block (S, L) end procedure signal(S) var S : semaphore; begin S.value := S.value + 1; if S.value=0 then wakeup(S, L); end,Page 10,2020/7/19,回答,. 假定信号量S.value的初值为1，当一个wait操作执行完S.value:= S.value-1后，S.value的值变为0，此时该进程不

6、发生阻塞。 如果wait操作不是原语，即在一个wait操作执行过程中可以有另一个wait操作同时执行，假设第二个wait 操作在第一个wait操作执行if S.value0 .之前执行了S.value:= S.value-1，此时S.value的值变为-1而不是0，这时第一个执行wait操作的进程就会阻塞。这样就不符合对wait操作的定义。,Page 11,2020/7/19,回答,4. 在生产者和消费者管理中，信号量mutex, empty和full的作用是什么？为什么p操作的顺序不能调换？,Page 12,2020/7/19,回答,4.答 信号量mutex作为公用信号量使生产者进程和消费者

7、进程对缓冲池实现互斥访问。信号量empty作为私用信号最用来表示空缓冲区的数量，生产者进程通过信号量empty来申请存放产品的空缓冲区。信号量full作为私用信号量来表示装满产品的缓冲区数量，消费者进程通过信号量full来申请消费产品的满缓冲区。信号量empyt和full起着协调生产者进程和消费者进程同步的作用 若将生产者消费者问题程序中的生产者程序由wait(empty); wait(mutex);改为 wait(mutex); wait(empty);则在无空缓冲区的条件下，生产者进程首先通过wait(mutex)占有缓冲区的使用权，然后再执行wait(empty)，但此时因无空缓冲区而阻

8、塞，等待消费者进程消费产品后产生空缓冲区；而消费者进程因没有缓冲区的控制权而不能进入缓冲区消费。此时两进程均不能运行而死锁 对于消费者进程中的wait(full); wait(mutex);也是如此 因此，wait操作的顺序通常不能调换 在wait操作中，每个进程应先申请自己的私用信号量，然后再去申请公用信号量,Page 13,2020/7/19,回答,5. 设有5个哲学家，共享一张有5把椅子的桌子，每人有1 把椅子，但桌上只有5支筷子，每人两边各放1支。哲学家在饥饿时可以分两次从两边各抢占筷子就餐。就餐的条件是 哲学家想吃饭时，先提出吃饭的要求 提出吃饭要求，并拿到两支筷子后，方可吃饭 如筷

9、子已被他人获得，则只能等他吃完后才能获得筷子 任一哲学家在自己未拿到两支筷子吃饭前，不放下手中的筷子 则开始就餐前只允许两个哲学家请求吃饭 求 描述一个保证不会出现两个邻座同时要求吃饭的算法,Page 14,2020/7/19,回答,5.答： 假设哲学家的编号为04，则对第i个哲学家来说，其邻座分别为(i+1) mod 5 和 (i+4) mod 5,i,(i+4) mod 5,(i+1) mod 5,(i+2) mod 5,(i+3) mod 5,Page 15,2020/7/19,回答,为保证不会出现相邻的哲学家同时提出吃饭请求，设置信号量S0S4来互斥相邻哲学家吃饭的请求，其初值均为1

10、5支筷子也是临界资源，C0C4的初值为1 算法如下,Page 16,2020/7/19,回答,begin S0=S1=S2=S3=S4:=1; C0=C1=C2=C3=C4:=1; cobegin Pi (i=0,1,2,3,4) : /第i个哲学家 begin repeat wait (Si); /第i个哲学家申请吃饭 wait(S(i+1) mod 5); /禁止两边的哲学家申请 wait(S(i+4) mod 5); wait(Ci); /申请筷子 wait(C(i+1) mod 5); signal (Si); /第i个哲学家申请结束 signal(S(i+1) mod 5); /取消

11、对两边哲学家的申请限制 signal(S(i+4) mod 5); eat; signal(Ci); / 放下筷子 signal(C(i+1) mod 5); until false end coend end;,Page 17,2020/7/19,回答,6.多个进程共享一个文件，其中只读文件的称为读者，其余只写文件的称为写者。读者可以同时读，但是写者只能独立地写。 问 （1）说明进程间的相互制约关系，应设哪些信号量 （2）用信号量机制写出同步算法 （3）修改上述算法，使其对写者优先，即一旦有写者到达，后续的读者必须等待，直到写者完成操作。,Page 18,2020/7/19,回答,(1) 进

12、程之间的关系有3类 读者之间允许同时读 读者与写者之间要互斥 写者与写者之间要互斥 应设如下信号量 共享变量count, 用于记录正在读文件的读者数目，初值为0，只有当count=0时，才允许写 读互斥信号量，用于使读者互斥地共享变量count，初值为1 写互斥信号量，wmutex，用于实现写者与读者互斥及写者之间互斥，初值为1,Page 19,2020/7/19,回答,（2） begin rmutex:=1;wmutex:=1; count :=0; cobegin reder i (i=0,1,2,.m) : begin wait(rmutex); count:=count + 1; if

13、 count=1 then wait (wmutex); /第一个读者开始访问，禁止写者访问 signal(rmutex); read; wait(rmutex); count:=count 1; if count=0 then signal(wmutex); /没有读者访问，允许写者访问 signal(rmutex); end;,writer j (j=0,1,2,.,n) : begin wait(wmutex); write; signal(wmutex); end coend end;,Page 20,2020/7/19,回答,(3) 为提高写者的优先级，可增加一信号量W,当有写者提出

14、写请求时，通过W封锁后续读者的读请求,Page 21,2020/7/19,回答,begin rmutex:=1;wmutex:=1; count :=0; W:=1; cobegin reder i (i=0,1,2,.m) : begin wait(W); /无写者请求时进入 wait(rmutex); count:=count + 1; if count=1 then wait (wmutex); signal(rmutex); signal(W); read; wait(rmutex); count:=count 1; if count=0 then signal(wmutex); /没

15、有读者访问，允许写者访问 signal(rmutex); end;,writer j (j=0,1,2,.,n) : begin wait(W); wait(wmutex); write; signal(wmutex); signal(W) end coend end;,Page 22,2020/7/19,回答,7.分析下面用信号量解决哲学家进餐问题的同步算法是否满足同步机制的准则。若不满足，说明为什么，并给出满足同步机制准则的同步算法。 Var c: Array0.4 OF semaphore; /定义筷子为信号量 c0:=c1:=c2:=c3:=c4:=1; parbegin pi(i=0

16、,1,2,3,4): REPEAT Think; wait(ci); /哲学家申请筷子 wait(c(i+1) mod 5); Eat; /进餐 signal(ci); /放下筷子 signal(c(i+1) mod 5); UNTIL false parend,Page 23,2020/7/19,回答,7.答： 该算法不满足同步机制准则中的有限等待，即每个哲学家都只拿到了一只筷子（如左手），时就会产生死锁。 解决方案如下,Page 24,2020/7/19,回答,解法1：互斥申请资源 设置信号量mutex，初值为1，控制申请资源的过程，要求一次申请完所有资源（2支筷子）后才开始运行。也就是在

17、申请过程中其他进程不能打断，且在满足要求前其他进程也不能申请。 parbegin pi(i=0,1,2,3,4): REPEAT Think; wait(mutex); wait(ci); /哲学家申请筷子 wait(c(i+1) mod 5); signal(mutex); Eat; /进餐 signal(ci); /放下筷子 signal(c(i+1) mod 5); UNTIL false parend,Page 25,2020/7/19,回答,解法2：改变申请资源顺序 规定奇数哲学家先拿起左边的筷子，然后拿右边；偶数号正相反。即拿到一支筷子的才有权拿下一个筷子，而没有拿到的则退出竞争，这样不会出现每人只拿到一支筷子的情况。 pi(i=0,1,2,3,4): REPEAT Think; if odd(i) then /如果i为奇数号 begin wait(c(i+1) mod 5); /先拿左手的筷子 wait(ci); end else begin wait(ci); /先拿右手的筷子 wait(c(i+1) mod 5); e