《操作系統(tǒng)》PV習題課new

操作系統(tǒng)習題講解一、進程概念

二、進程同步和互斥OperatingSystemConcepts進程概念（一）問題：如果系統(tǒng)中有N個進程，運行進程最多幾個，最少幾個？就緒進程最多幾個，最少幾個？等待進程最多幾個，最少幾個？OperatingSystemConcepts解答：運行進程最多1個，最少0個； 就緒進程最多N-1個，最少0個； 等待進程最多N個，最少0個；OperatingSystemConcepts進程同步和互斥（一）問題一：用P.V操作解決下圖之同步問題getcopyputfstgOperatingSystemConcepts一個數(shù)據(jù)上的操作順序：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第二類讀者寫者問題（寫者優(yōu)先）1）共享讀2）互斥寫、讀寫互斥3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）進程同步和互斥（三）OperatingSystemConceptsVar

mutex:semaphore;{互斥信號量，初值為1}

R:semaphore;{對應讀者等待隊列，初值為0}

W:semaphore;{對應寫者等待隊列，初值為0}{一般變量：}

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

rc :integer;{初值0,共享讀的讀者數(shù)}

rq :integer;{初值0,等待隊列中讀者數(shù)}

wq :integer;{初值0,等待隊列中寫者數(shù)}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理發(fā)師問題:

理發(fā)店里有一位理發(fā)師,一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子.如果沒有顧客,則理發(fā)師便在理發(fā)椅上睡覺.當一個顧客到來時,他必須先喚醒理發(fā)師.如果顧客到來時理發(fā)師正在理發(fā)，則如果有空椅子，可坐下來等；否則離開。進程同步和互斥（四）OperatingSystemConcepts

Var

Sn:semaphore;{位子數(shù)目，初值為n}S:semaphore;{理發(fā)師睡覺，初值為0}

mutex:semaphore;{初值為1} 顧客進程i:P(Sn);{門外觀望}P(mutex);進門；V(mutex);V(S);等候；理發(fā)；V(Sn)P(mutex);出門；V(mutex);OperatingSystemConcepts理發(fā)師進程：RepeatP(S);

P(mutex);

叫人理發(fā)；

V(mutex);

理發(fā)；Untilfalse;OperatingSystemConcepts問題： 推廣讀寫者問題中的消息緩沖處理。消息緩沖區(qū)為k個，有m個發(fā)送進程，n個接收進程，每個接收進程對發(fā)送來的消息都必須取一次進程同步和互斥（五）OperatingSystemConcepts解題思路：發(fā)送者發(fā)送消息后喚醒所有的接收者；所有的接收者都接收后空出緩沖區(qū)；接收者接收時要修改接收次數(shù)；接收計數(shù)和緩沖區(qū)的指針為臨界資源，訪問時要互斥。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是緩沖區(qū)大?。籲是接收進程個數(shù)}{m是發(fā)送進程個數(shù)，通過s進行“寫互斥”}OperatingSystemConcepts

ProcedureSender_i(i:integer);{i為發(fā)送進程的標號}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