《操作系统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,