《操作系统pv习题课》由会员分享，可在线阅读，更多相关《操作系统pv习题课（24页珍藏版）》请在金锄头文库上搜索。
1、Operating System Concepts,操作系统习题讲解,一、进程概念 二、进程同步和互斥,进 程 概 念（一）,问题：如果系统中有N个进程， 运行进程最多几个，最少几个？ 就绪进程最多几个，最少几个？ 等待进程最多几个，最少几个？,Operating System Concepts,解答：运行进程最多1个，最少0个； 就绪进程最多N-1个，最少0个； 等待进程最多N个，最少0个；,Operating System Concepts,进程同步和互斥（一）,问题一：用P.V操作解决下图之同步问题,Operating System Concepts,一个数据上的操作顺序：get - c
2、opy - put,Get不能向“满”的S中放； Copy不能从“空”的S中取；不能向“满”的T中放； Put不能“空”的T中取,Operating System Concepts,（同步）信号量：实际上也起到互斥作用 S_Empty, T_Empty， 初值为1 S_Full, T_Full; 初值为0,Get: Begin Repeat P(S_Empty) T_get_S(); V(S_Full); Until false; End,Copy: Begin Repeat P(S_Full); P(T_Empty); S_copy_T(); V(T_Full); V(S_Empty); U
3、ntil false; End,Put: Begin Repeat P(T_Full); T_put_G(); V(T_Empty); Until false; End,Operating System Concepts,进程同步和互斥（二）,问题：用P.V操作解决下面问题,Operating System Concepts,信号量： S_Door, 初值为0 S_Stop; 初值为0,司机进程： Begin Repeat P(S_Door); 启动； 驾驶； 停车； V(S_Stop); Until false; End,乘务员进程: Begin Repeat 关门； V(S_Door);
4、售票； P(S_Stop); 开门； Until false; End,同步要求：先关门，后开车； 先停车，后开门,Operating System Concepts,第二类读者写者问题（写者优先） 1）共享读 2）互斥写、读写互斥 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）,进程同步和互斥（三）,Operating System Concepts,Var mutex: semaphore; 互斥信号量，初值为1 R : semaphore; 对应读者等待队列，初值为0 W: semaphore; 对应写者等待队列，初值为0 一般变量： Writing: Bool
5、ean; 初值false, 有写者正在写 rc : integer; 初值0, 共享读的读者数 rq : integer; 初值0,等待队列中读者数 wq : integer; 初值0,等待队列中写者数,Operating System Concepts,读者进程,Begin Repeat P(mutex); If (Writing OR wq0) Then Begin rq:=rq+1; V(mutex); P(R); P(mutex); resume End; rc:=rc+1; V(mutex); Read();,Operating System Concepts,P(mutex); r
6、c:=rc-1; If (rc=0 AND wq0) Then Begin wq:=wq-1; Writing:=true; V(mutex); V(W); End; Else V(mutex); Until false End,Operating System Concepts,写者进程,Begin Repeat P(mutex); If (Writing OR rc0) Then Begin wq:=wq+1; V(mutex); P(W); End; Else Begin Writing:=true; V(mutex); Write();,Operating System Concept
7、s,P(mutex); If (wq0) Then Begin wq:=wq-1; V(mutex); V(W); End Else,Operating System Concepts,If (rq0) Then Begin Writing:=false; While (rq0) Begin rq:=rq-1; V(R) ; End End Else Begin Writing:=false; V(mutex); End End Until false,Operating System Concepts,理发师问题: 理发店里有一位理发师,一把理发椅和N把供等候理发的顾客坐的椅子.如果没有顾客
8、,则理发师便在理发椅上睡觉.当一个顾客到来时,他必须先唤醒理发师.如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。,进程同步和互斥（四）,Operating System Concepts,Var Sn: semaphore; 位子数目，初值为n S: semaphore; 理发师睡觉，初值为0 mutex: semaphore; 初值为1 顾客进程 i: P(Sn);门外观望 P(mutex); 进门； V(mutex); V(S); 等候； 理发； V(Sn) P(mutex); 出门； V(mutex);,Operating System Concepts,理发师进程
9、 ： Repeat P(S); P(mutex); 叫人理发； V(mutex); 理发； Until false;,Operating System Concepts,问题： 推广读写者问题中的消息缓冲处理。消息缓冲区为k个，有m个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次,进程同步和互斥（五）,Operating System Concepts,解题思路： 发送者发送消息后唤醒所有的接收者； 所有的接收者都接收后空出缓冲区； 接收者接收时要修改接收次数； 接收计数和缓冲区的指针为临界资源，访问时要互斥 。,Operating System Concepts,Type B
10、ufferType = Record msg:MessageType; count:integer; mutex:semaphore; 初值为1 empty: semaphore; 初值为1 full: array 1n of semaphore； 初值全为0 End Var mutex: semaphore; 初值为1 s: integer; 初值为0 buff: array 0k-1 of BufferType; k是缓冲区大小； n是接收进程个数 m是发送进程个数，通过 s 进行“写互斥” ,Operating System Concepts,Procedure Sender_i(i:i
11、nteger); i 为发送进程的标号 Var s0, 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; End,Operating System Concepts,Procedure Recvr(i:integer); i 为接收进程的标号 Var j: 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 k Until false; End,Operating System Concepts,computercollege,
