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

操作系統(tǒng)習(xí)題講解一、進(jìn)程概念

二、進(jìn)程同步和互斥OperatingSystemConcepts進(jìn)程概念（一）問題：如果系統(tǒng)中有N個(gè)進(jìn)程，運(yùn)行進(jìn)程最多幾個(gè)，最少幾個(gè)？就緒進(jìn)程最多幾個(gè)，最少幾個(gè)？等待進(jìn)程最多幾個(gè)，最少幾個(gè)？OperatingSystemConcepts解答：運(yùn)行進(jìn)程最多1個(gè)，最少0個(gè)； 就緒進(jìn)程最多N-1個(gè)，最少0個(gè)； 等待進(jìn)程最多N個(gè)，最少0個(gè)；OperatingSystemConcepts進(jìn)程同步和互斥（一）問題一：用P.V操作解決下圖之同步問題getcopyputfstgOperatingSystemConcepts一個(gè)數(shù)據(jù)上的操作順序：get-copy-putcpcgpcgpgGet不能向“滿”的S中放；Copy不能從“空”的S中?。徊荒芟颉皾M”的T中放；Put不能“空”的T中取OperatingSystemConcepts（同步）信號(hào)量：{實(shí)際上也起到互斥作用}

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進(jìn)程同步和互斥（二）問題：用P.V操作解決下面問題司機(jī)進(jìn)程：REPEAT啟動(dòng)車輛正常駕駛到站停車UNTIL…售票員進(jìn)程：REPEAT關(guān)門售票開門UNTIL…OperatingSystemConcepts信號(hào)量：

S_Door, {初值為0}

S_Stop; {初值為0}司機(jī)進(jìn)程： BeginRepeatP(S_Door);

啟動(dòng)；駕駛；停車；

V(S_Stop);Untilfalse;End 乘務(wù)員進(jìn)程:BeginRepeat

關(guān)門；

V(S_Door);

售票；

P(S_Stop);

開門；

Untilfalse;End 同步要求：先關(guān)門，后開車； 先停車，后開門OperatingSystemConcepts第二類讀者寫者問題（寫者優(yōu)先）1）共享讀2）互斥寫、讀寫互斥3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫者）進(jìn)程同步和互斥（三）OperatingSystemConceptsVar

mutex:semaphore;{互斥信號(hào)量，初值為1}

R:semaphore;{對(duì)應(yīng)讀者等待隊(duì)列，初值為0}

W:semaphore;{對(duì)應(yīng)寫者等待隊(duì)列，初值為0}{一般變量：}

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

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

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

wq :integer;{初值0,等待隊(duì)列中寫者數(shù)}OperatingSystemConcepts讀者進(jìn)程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寫者進(jìn)程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ā)椅上睡覺.當(dāng)一個(gè)顧客到來時(shí),他必須先喚醒理發(fā)師.如果顧客到來時(shí)理發(fā)師正在理發(fā)，則如果有空椅子，可坐下來等；否則離開。進(jìn)程同步和互斥（四）OperatingSystemConcepts

Var

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

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

P(mutex);

叫人理發(fā)；

V(mutex);

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

ProcedureSender_i(i:integer);{i為發(fā)送進(jìn)程的標(biāo)號(hào)}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為接收進(jìn)程的標(biāo)號(hào)}Var j:integer;Beginj:=0;RepeatP(buff[j].full[i]);

從buff[j].msg中讀信息；

P(buff[j].mutex