操作系统PV习题课课件

操作系统习题讲解一、进程概念

二、进程同步和互斥1进程概念（一）问题：如果系统中有N个进程，运行进程最多几个，最少几个？就绪进程最多几个，最少几个？等待进程最多几个，最少几个？2运行就绪等待进程的状态及其转换

3解答：运行进程最多1个，最少0个； 就绪进程最多N-1个，最少0个； 等待进程最多N个，最少0个；概念：(1)进程、进程的基本状态； 单CPU；进程切换瞬间； 系统进程、用户进程；

(2)死锁（不是“死机”）；进程概念（一）4进程概念（二）问题：

进程有无如下状态转换，为什么？ （1）等待—运行 （2）就绪—等待解答：

（1）不能：等待－就绪－运行 （2）不能：就绪－运行－等待5问题：一个转换发生，是否另一个转换一定发生？找出所有的可能。解答：

就绪—运行:不一定（系统中仅一个进程） 转换条件：被调度程序选中

运行—就绪:一定（讨论就绪队列的长度） 转换条件：时间片到时,或有更高优先级 的进程出现进程概念（三）6解答：

运行—等待:不一定（考虑死锁） 转换条件：等待某事件发生

等待—就绪:不一定 转换条件：等待的事件发生进程概念（三）7进程概念（四）问题：日常生活中的“进程”举例解答：

两个角度：“程序-数据-运行” 或“资源-调度-运行” 经典例子：“按照菜谱作菜”“乐队演奏” 或“向服务员请求服务”等 8进程同步和互斥（一）问题：用P.V操作解决下图之同步问题getcopyputfstg9进程同步和互斥（一）cpcgpcgpg一个数据上的操作顺序：get-copy-putGet不能向“满”的S中放；Copy不能从“空”的S中取；不能向“满”的T中放；Put不能“空”的T中取10（同步）信号量：{实际上也起到互斥作用} S_Empty,T_Empty，{初值为1} S_Full,T_Full; {初值为0}Get: BeginRepeatP(S_Empty)T_get_S();V(S_Full);Untilfalse;End Copy:BeginRepeatP(S_Full);P(T_Empty);S_copy_T();V(T_Full);V(S_Empty);Untilfalse;EndPut:BeginRepeatP(T_Full);T_put_G();V(T_Empty);Untilfalse;End11进程同步和互斥（二）问题：用P.V操作解决下面问题司机进程：REPEAT启动车辆正常驾驶到站停车UNTIL…售票员进程：REPEAT关门售票开门UNTIL…12信号量：

S_Door, {初值为0} S_Stop; {初值为0}司机进程： BeginRepeatP(S_Door);

启动；驾驶；停车；

V(S_Stop);Untilfalse;End 乘务员进程:BeginRepeat

关门；

V(S_Door);

售票；

P(S_Stop);

开门；

Untilfalse;End 同步要求：先关门，后开车； 先停车，后开门13问题：

推广读写者问题中的消息缓冲处理。消息缓冲区为k个，有m个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次

进程同步和互斥（三）14TypeBufferType=Record msg:MessageType; count:integer; mutex:semaphore;{初值为1} empty:semaphore;{初值为1} full:array[1..n]ofsemaphore；

{初值全为0} EndVar mutex:semaphore;{初值为1} s:integer; {初值为0} buff:array[0..k-1]ofBufferType;{k是缓冲区大小；n是接收进程个数}{m是发送进程个数，通过s进行“写互斥”}15ProcedureSender_i(i:integer);{i为发送进程的标号}Var s0,j:integer;BeginRepeatP(mutex);s0:=s;s:=(s+1)modk;V(mutex);P(buff[s0].empty)；在buff[s0].msg中写信息；

P(buff[s0].mutex)；

buff[s0].count:=n;V(buff[s0].mutex);For(j:=1tondo)V(buff[s0].full[j]);Untilfalse;EndProcedureRecvr(i:integer);{i为接收进程的标号}Var j:integer;Beginj:=0;RepeatP(buff[j].full[i]);

从buff[j].msg中读信息；

P(buff[j].mutex)；

buff[j].count:=buff[j].count-1;If(buff[j].count=0)ThenV(buff[j].empty)；

V(buff[j].mutex);j:=(j+1)modkUntilfalse;End16第二类读者写者问题（写者优先）1）共享读2）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续 读者必须等待，唤醒时优先考虑写者）进程同步和互斥（四）17Var mutex:semaphore;{互斥信号量，初值为1}R:semaphore;{对应读者等待队列，初值为0}W:semaphore;{对应写者等待队列，初值为0}{一般变量：}Writing:Boolean;{初值false,有写者正在写}rc :integer;{初值0,共享读的读者数}rq :integer;{初值0,等待队列中读者数}wq :integer;{初值0,等待队列中写者数}18Begin P(mutex); If(WritingORwq<>0) ThenBegin rq:=rq+1; V(mutex); P(R); P(mutex);{resume} End; rc:=rc+1; V(mutex); Read(); P(mutex); rc:=rc-1; If(rc=0ANDwq<>0) ThenBegin wq:=wq-1; Writing:=true; V(mutex); V(W); End; ElseV(mutex) ;End读者进程(a)检测是否有写者并处理(b)Inc(rc)(c)Read()(d)Dec(rc)(e)处理写者等待队列19Begin P(mutex); If(WritingORrc>0) ThenBegin wq:=wq+1; V(mutex); P(W); End; ElseBegin Writing:=true; V(mutex); Write(); P(mutex); If(wq<>0) ThenBegin wq:=wq-1; V(mutex); V(W); End Else If(rq>0) ThenBegin Writing:=false; While(rq>0) Begin rq:=rq-1; V(R) ; End End ElseBegin Writing:=false; V(mutex); End End写者进程(a)检测是否有进程正在读写(b)Writing(T);Write();Writing(F)(c)处理写者等待队列;处理Reader等待队列20P(s): s:=s-1; Ifs<0 Then将本进程插入相应队列末尾等待；V(s)：s:=s+1; Ifs<=0 Then

从等待队列队尾取一个进程唤醒， 插入就绪队列进程同步和互斥（五）对P/V操作定义作以下修改21问题：1）这样定义P、V操作是否有问题？ 不合理：先进后出；可能“无限等待”2）用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。 思路：令等待队列中始终只有一个进程。 将“栈”变成“队列”

VarS:array[1..n-1]ofsemaphore; {n为进程数目；S[i]初值为i；S[n]到

S[1]的作用好象是n层筛子}22ProcedurePi;Vari:integer;Begin Repeat Pre_Do_it(); Fori:=n-1Downto1Do P(S[i]); Do_It_In_Critical_Section; Fori:=1Ton-1Do V(S[i]); Post_Do_it(); Untilfalse;End233）对于2）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？ 上述解法每次都需要做2n次P/V操作，性能低下。采用二叉树的思想，改进如下： S[1..4]P[1..4]S1S2S3让信号量处于不同的层次上，每个信号量至多控制两个进程（对两个进程进行同步）P1P2P3P424ProcedureP1;{P2isthesame }Begin Repeat P(S1); P(S3); Do_It(); V(S3); V(S1); Untilfalse;End;ProcedureP3;{P4isthesame}Begin Repeat P(S2); P(S3); Do_It(); V(S3); V(S2); Untilfalse;End;不妨设有4个进程P1..P4，VarS1,S2,S3:semaphore;{初值为1}假设共有2N个进程争用临界区；时间复杂性：2Nvs N；空间复杂性：2Nvs2N－125理发师问题理发店里有一位理发师,一把理发椅和N把供等候理发的顾客坐的椅子.如果没有顾客,则理发师便在理发椅上睡觉.当一个顾客到来时,他必须先唤醒理发师.如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。进程同步和互斥（六）26顾客进程i:P(Sn);{门外观望}P(mutex);进门；V(mutex);V(S);等候；理发；V(Sn)P(mutex);出门；V(mutex);Var Sn: semaphore;{位子数目，初值为n} S: semaphore;{理发师睡觉，初值为1}mutex: semaphore;{初值为1}理发师进程：RepeatP(S);P(mutex);

叫人理发；

V(mutex);

理发；Untilfalse;27用P.V操作来实现Receive原语:Receive（S，M）