操作系统PV习题课

1、O,操作系统习题讲解,一、进程概念二、进程同步和互斥,O,进程概念（一）,问题：如果系统中有N个进程，运行进程最多几个，最少几个？就绪进程最多几个，最少几个？等待进程最多几个，最少几个？,O,解答：运行进程最多1个，最少0个；就绪进程最多N-1个，最少0个；等待进程最多N个，最少0个；,O,进程同步和互斥（一）,问题一：用P.V操作解决下图之同步问题,O,一个数据上的操作顺序：get-copy-put,Get不能向“满”的S中放；Copy不能从“空”的S中取；不能向“满”的T中放；Put不能“空”的T中取,O,（同步）信号量：实际上也起到互斥作用S_Empty,T_Empty，初值为1S_Fu

2、ll,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;End,Put:BeginRepeatP(T_Full);T_put_G();V(T_Empty);Untilfalse;End,O,进程同步和互斥（二）,问题：用P.V操作解决下面问题,O,信号量：S_Door,初值为0S_Stop;初值为0,司机进程：BeginRepeatP(S_Do

3、or);启动；驾驶；停车；V(S_Stop);Untilfalse;End,乘务员进程:BeginRepeat关门；V(S_Door);售票；P(S_Stop);开门；Untilfalse;End,同步要求：先关门，后开车；先停车，后开门,O,第二类读者写者问题（写者优先）1）共享读2）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）,进程同步和互斥（三）,O,Varmutex:semaphore;互斥信号量，初值为1R:semaphore;对应读者等待队列，初值为0W:semaphore;对应写者等待队列，初值为0一般变量：Writing:Boolea

4、n;初值false,有写者正在写rc:integer;初值0,共享读的读者数rq:integer;初值0,等待队列中读者数wq:integer;初值0,等待队列中写者数,O,读者进程,BeginRepeatP(mutex);If(WritingORwq0)ThenBeginrq:=rq+1;V(mutex);P(R);P(mutex);resumeEnd;rc:=rc+1;V(mutex);Read();,O,P(mutex);rc:=rc-1;If(rc=0ANDwq0)ThenBeginwq:=wq-1;Writing:=true;V(mutex);V(W);End;ElseV(mutex

5、);UntilfalseEnd,O,写者进程,BeginRepeatP(mutex);If(WritingORrc0)ThenBeginwq:=wq+1;V(mutex);P(W);End;ElseBeginWriting:=true;V(mutex);Write();,O,P(mutex);If(wq0)ThenBeginwq:=wq-1;V(mutex);V(W);EndElse,O,If(rq0)ThenBeginWriting:=false;While(rq0)Beginrq:=rq-1;V(R);EndEndElseBeginWriting:=false;V(mutex);EndEn

6、dUntilfalse,O,理发师问题:理发店里有一位理发师,一把理发椅和N把供等候理发的顾客坐的椅子.如果没有顾客,则理发师便在理发椅上睡觉.当一个顾客到来时,他必须先唤醒理发师.如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开。,进程同步和互斥（四）,O,VarSn:semaphore;位子数目，初值为nS:semaphore;理发师睡觉，初值为0mutex:semaphore;初值为1顾客进程i:P(Sn);门外观望P(mutex);进门；V(mutex);V(S);等候；理发；V(Sn)P(mutex);出门；V(mutex);,O,理发师进程：RepeatP(S);

7、P(mutex);叫人理发；V(mutex);理发；Untilfalse;,O,问题：推广读写者问题中的消息缓冲处理。消息缓冲区为k个，有m个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次,进程同步和互斥（五）,O,解题思路：发送者发送消息后唤醒所有的接收者；所有的接收者都接收后空出缓冲区；接收者接收时要修改接收次数；接收计数和缓冲区的指针为临界资源，访问时要互斥。,O,TypeBufferType=Recordmsg:MessageType;count:integer;mutex:semaphore;初值为1empty:semaphore;初值为1full:array1.no

8、fsemaphore；初值全为0EndVarmutex:semaphore;初值为1s:integer;初值为0buff:array0.k-1ofBufferType;k是缓冲区大小；n是接收进程个数m是发送进程个数，通过s进行“写互斥”,O,ProcedureSender_i(i:integer);i为发送进程的标号Vars0,j:integer;BeginRepeatP(mutex);s0:=s;s:=(s+1)modk;V(mutex);P(buffs0.empty)；在buffs0.msg中写信息；P(buffs0.mutex)；buffs0.count:=n;V(buffs0.mutex);For(j:=1tondo)V(buffs0.fullj);Untilfalse;End,O,ProcedureRecvr(i:integer);i为接收进程的标号Varj:integer;Beginj:=0;RepeatP(buffj.fulli);从buffj.msg中读