《操作系统》PV习题课new.ppt

《《操作系统》PV习题课new.ppt》由会员分享，可在线阅读，更多相关《《操作系统》PV习题课new.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Silberschatz, Galvin and Gagne 20022.2Operating System Concepts进 程 概 念（一）问题：如果系统中有问题：如果系统中有N个进程，个进程，4运行进程最多几个，最少几个？运行进程最多几个，最少几个？4就绪进程最多几个，最少几个？就绪进程最多几个，最少几个？4等待进程最多几个，最少几个？等待进程最多几个，最少几个？Silberschatz, Galvin and Gagne 20022.3Operating System Concepts解答解答：运行进程最多：运行进程最多1 1个，最少个，最少0 0个；个； 就绪进程最多就绪进程最多N

2、-1-1个，最少个，最少0 0个；个； 等待进程最多等待进程最多N个，最少个，最少0 0个；个；Silberschatz, Galvin and Gagne 20022.4Operating System Concepts进程同步和互斥（一）问题一问题一：用用P.VP.V操作解决下图之同步问题操作解决下图之同步问题getcopyputfstgSilberschatz, Galvin and Gagne 20022.5Operating System Concepts一个数据上的操作顺序：一个数据上的操作顺序：get - copy - putcpcgpcgpgGet不能向不能向“满满”的的S中放

3、；中放；Copy不能从不能从“空空”的的S中取；不能向中取；不能向“满满”的的T中放；中放；Put不能不能“空空”的的T中取中取Silberschatz, Galvin and Gagne 20022.6Operating System Concepts（同步）信号量：（同步）信号量：实际上也起到互斥作用实际上也起到互斥作用S_Empty, T_Empty， 初值为初值为1S_Full, T_Full; 初值为初值为0Get:Begin Repeat P(S_Empty) T_get_S(); V(S_Full); Until false;EndCopy:Begin Repeat P(S_Fu

4、ll); P(T_Empty); S_copy_T(); V(T_Full); V(S_Empty); Until false;EndPut:Begin Repeat P(T_Full); T_put_G(); V(T_Empty); Until false;EndSilberschatz, Galvin and Gagne 20022.7Operating System Concepts进程同步和互斥（二）问题：用问题：用P.V操作解决下面问题操作解决下面问题司机进程：司机进程：REPEAT启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车UNTIL 售票员进程：售票员进程：REPEAT关门关

5、门售票售票开门开门UNTIL Silberschatz, Galvin and Gagne 20022.8Operating System Concepts信号量：信号量：S_Door, 初值为初值为0S_Stop; 初值为初值为0司机进程司机进程：Begin Repeat P(S_Door); 启动；启动； 驾驶；驾驶； 停车；停车； V(S_Stop); Until false;End乘务员进程乘务员进程:Begin Repeat 关门；关门； V(S_Door); 售票；售票； P(S_Stop); 开门；开门； Until false;End同步要求：先关门，后开车；同步要求：先关门，

6、后开车； 先停车，后开门先停车，后开门Silberschatz, Galvin and Gagne 20022.9Operating System Concepts第二类读者写者问题（写者优先）第二类读者写者问题（写者优先）1）共享读）共享读2）互斥写、读写互斥）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续读者必）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）须等待，唤醒时优先考虑写者）进程同步和互斥（三）Silberschatz, Galvin and Gagne 20022.10Operating System ConceptsVar mutex: sema

7、phore; 互斥信号量，初值为互斥信号量，初值为1 R : semaphore; 对应读者等待队列，初值为对应读者等待队列，初值为0 W: semaphore; 对应写者等待队列，初值为对应写者等待队列，初值为0一般变量：一般变量： Writing: Boolean; 初值初值false, 有写者正在写有写者正在写 rc : integer; 初值初值0, 共享读的读者数共享读的读者数 rq : integer; 初值初值0,等待队列中读者数等待队列中读者数 wq: integer; 初值初值0,等待队列中写者数等待队列中写者数Silberschatz, Galvin and Gagne 2

8、0022.11Operating System Concepts读者进程Begin RepeatP(mutex);If (Writing OR wq0) Then Beginrq:=rq+1; V(mutex);P(R);P(mutex); resume End;rc:=rc+1;V(mutex);Read();Silberschatz, Galvin and Gagne 20022.12Operating System ConceptsP(mutex);rc:=rc-1;If (rc=0 AND wq0) Then Begin wq:=wq-1;Writing:=true;V(mutex);

9、V(W); End;Else V(mutex); Until falseEndSilberschatz, Galvin and Gagne 20022.13Operating System Concepts写者进程Begin RepeatP(mutex);If (Writing OR rc0)Then Begin wq:=wq+1; V(mutex); P(W); End;Else BeginWriting:=true; V(mutex);Write();Silberschatz, Galvin and Gagne 20022.14Operating System Concepts P(mut

10、ex);If (wq0)Then Beginwq:=wq-1;V(mutex);V(W); EndElseSilberschatz, Galvin and Gagne 20022.15Operating System Concepts If (rq0)Then BeginWriting:=false;While (rq0) Beginrq:=rq-1;V(R) ; End EndElse BeginWriting:=false;V(mutex); EndEnd Until falseSilberschatz, Galvin and Gagne 20022.16Operating System

11、Concepts理发师问题理发师问题: 理发店里有一位理发师理发店里有一位理发师,一把理发椅和一把理发椅和N把供把供等候理发的顾客坐的椅子等候理发的顾客坐的椅子.如果没有顾客如果没有顾客,则理发师则理发师便在理发椅上睡觉便在理发椅上睡觉.当一个顾客到来时当一个顾客到来时,他必须先唤他必须先唤醒理发师醒理发师.如果顾客到来时理发师正在理发，则如如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。果有空椅子，可坐下来等；否则离开。进程同步和互斥（四）Silberschatz, Galvin and Gagne 20022.17Operating System Concepts Va

12、r Sn: semaphore; 位子数目，初值为位子数目，初值为n S: semaphore; 理发师睡觉，初值为理发师睡觉，初值为0 mutex: semaphore; 初值为初值为1顾客进程顾客进程 i:P(Sn);门外观望门外观望P(mutex);进门；进门；V(mutex);V(S);等候；等候；理发；理发；V(Sn)P(mutex);出门；出门；V(mutex);Silberschatz, Galvin and Gagne 20022.18Operating System Concepts理发师进程理发师进程 ：Repeat P(S); P(mutex); 叫人理发；叫人理发； V

13、(mutex); 理发；理发；Until false;Silberschatz, Galvin and Gagne 20022.19Operating System Concepts问题：问题：推广读写者问题中的消息缓冲处理。消息缓推广读写者问题中的消息缓冲处理。消息缓冲区为冲区为k个，有个，有m个发送进程，个发送进程，n个接收进程，每个接收进程，每个接收进程对发送来的消息都必须取一次个接收进程对发送来的消息都必须取一次 进程同步和互斥（五）Silberschatz, Galvin and Gagne 20022.20Operating System Concepts解题思路：解题思路： 发送

14、者发送消息后唤醒所有的接收者；发送者发送消息后唤醒所有的接收者； 所有的接收者都接收后空出缓冲区；所有的接收者都接收后空出缓冲区； 接收者接收时要修改接收次数；接收者接收时要修改接收次数； 接收计数和缓冲区的指针为临界资源，访问接收计数和缓冲区的指针为临界资源，访问时要互斥时要互斥 。Silberschatz, Galvin and Gagne 20022.21Operating System Concepts Type BufferType = Recordmsg:MessageType;count:integer;mutex:semaphore; 初值为初值为1empty: semapho

15、re; 初值为初值为1full: array 1.n of semaphore； 初值全为初值全为0EndVar mutex: semaphore; 初值为初值为1s: integer; 初值为初值为0buff: array 0.k-1 of BufferType; k是缓冲区大小；是缓冲区大小； n是接收进程个数是接收进程个数 m是发送进程个数，通过是发送进程个数，通过 s 进行进行“写互斥写互斥” Silberschatz, Galvin and Gagne 20022.22Operating System Concepts Procedure Sender_i(i:integer); i

16、 为发送进程的标号为发送进程的标号Vars0, j: integer;Begin Repeat P(mutex); s0:=s; s:=(s+1) mod k; V(mutex); P(buffs0.empty)； 在在buffs0.msg中写信息；中写信息； P(buffs0.mutex)； buffs0.count:=n; V(buffs0.mutex); For (j:=1 to n do) V(buffs0.fullj); Until false;EndSilberschatz, Galvin and Gagne 20022.23Operating System ConceptsPro

17、cedure Recvr(i:integer); i 为接收进程的标号为接收进程的标号Varj: integer;Begin j:=0; Repeat P(buffj.fulli); 从从buffj.msg中读信息；中读信息； P(buffj.mutex)； buffj.count:= buffj.count-1; If (buffj.count=0) Then V(buffj.empty)； V(buffj.mutex); j:=(j+1) mod kUntil false;EndSilberschatz, Galvin and Gagne 20022.24Operating System C