《操作系统》PV习题课new

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

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

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;EndOperatingSystemConcepts进程同步和互斥（二）问题：用P.V操作解决下面问题司机进程：REPEAT启动车辆正常驾驶到站停车UNTIL…售票员进程：REPEAT关门售票开门UNTIL…OperatingSystemConcepts信号量：

S_Door, {初值为0}

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

启动；驾驶；停车；

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

关门；

V(S_Door);

售票；

P(S_Stop);

开门；

Untilfalse;End 同步要求：先关门，后开车； 先停车，后开门OperatingSystemConcepts第二类读者写者问题（写者优先）1）共享读2）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）进程同步和互斥（三）OperatingSystemConceptsVar

mutex:semaphore;{互斥信号量，初值为1}

R:semaphore;{对应读者等待队列，初值为0}

W:semaphore;{对应写者等待队列，初值为0}{一般变量：}

Writing:Boolean;{初值false,有写者正在写}

rc :integer;{初值0,共享读的读者数}

rq :integer;{初值0,等待队列中读者数}

wq :integer;{初值0,等待队列中写者数}OperatingSystemConcepts读者进程BeginRepeat

P(mutex); If(WritingORwq<>0) ThenBegin

rq:=rq+1;

V(mutex); P(R);

P(mutex);{resume} End;

rc:=rc+1;

V(mutex); Read();OperatingSystemConcepts

P(mutex);

rc:=rc-1; If(rc=0ANDwq<>0) ThenBegin

wq:=wq-1; Writing:=true;

V(mutex); V(W); End; ElseV(mutex);UntilfalseEndOperatingSystemConcepts写者进程BeginRepeat

P(mutex); If(WritingORrc>0) ThenBegin

wq:=wq+1;

V(mutex); P(W); End; ElseBegin Writing:=true; V(mutex); Write();

OperatingSystemConcepts

P(mutex); If(wq<>0) ThenBegin

wq:=wq-1;

V(mutex); V(W); End ElseOperatingSystemConcepts

If(rq>0) ThenBegin Writing:=false; While(rq>0) Begin

rq:=rq-1; V(R) ; End End ElseBegin Writing:=false;

V(mutex); End EndUntilfalseOperatingSystemConcepts理发师问题:

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

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);OperatingSystemConcepts理发师进程：RepeatP(S);

P(mutex);

叫人理发；

V(mutex);

理发；Untilfalse;OperatingSystemConcepts问题： 推广读写者问题中的消息缓冲处理。消息缓冲区为k个，有m个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次进程同步和互斥（五）OperatingSystemConcepts解题思路：发送者发送消息后唤醒所有的接收者；所有的接收者都接收后空出缓冲区；接收者接收时要修改接收次数；接收计数和缓冲区的指针为临界资源，访问时要互斥。OperatingSystemConcepts

TypeBufferType=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进行“写互斥”}OperatingSystemConcepts

ProcedureSender_i(i:integer);{i为发送进程的标号}Var s0,j:integer;BeginRepeat

P(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;EndOperatingSystemConceptsProcedureRecvr(i:integer);{i为接收进程的标号}Var j:integer;Beginj:=0;RepeatP(buff[j].full[i]);

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

P(buff[j].mutex