操作系統(tǒng)PV習(xí)題課課件

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

二、進(jìn)程同步和互斥1進(jìn)程概念（一）問題：如果系統(tǒng)中有N個進(jìn)程，運行進(jìn)程最多幾個，最少幾個？就緒進(jìn)程最多幾個，最少幾個？等待進(jìn)程最多幾個，最少幾個？2運行就緒等待進(jìn)程的狀態(tài)及其轉(zhuǎn)換

3解答：運行進(jìn)程最多1個，最少0個； 就緒進(jìn)程最多N-1個，最少0個； 等待進(jìn)程最多N個，最少0個；概念：(1)進(jìn)程、進(jìn)程的基本狀態(tài)； 單CPU；進(jìn)程切換瞬間； 系統(tǒng)進(jìn)程、用戶進(jìn)程；

(2)死鎖（不是“死機(jī)”）；進(jìn)程概念（一）4進(jìn)程概念（二）問題：

進(jìn)程有無如下狀態(tài)轉(zhuǎn)換，為什么？ （1）等待—運行 （2）就緒—等待解答：

（1）不能：等待－就緒－運行 （2）不能：就緒－運行－等待5問題：一個轉(zhuǎn)換發(fā)生，是否另一個轉(zhuǎn)換一定發(fā)生？找出所有的可能。解答：

就緒—運行:不一定（系統(tǒng)中僅一個進(jìn)程） 轉(zhuǎn)換條件：被調(diào)度程序選中

運行—就緒:一定（討論就緒隊列的長度） 轉(zhuǎn)換條件：時間片到時,或有更高優(yōu)先級 的進(jìn)程出現(xiàn)進(jìn)程概念（三）6解答：

運行—等待:不一定（考慮死鎖） 轉(zhuǎn)換條件：等待某事件發(fā)生

等待—就緒:不一定 轉(zhuǎn)換條件：等待的事件發(fā)生進(jìn)程概念（三）7進(jìn)程概念（四）問題：日常生活中的“進(jìn)程”舉例解答：

兩個角度：“程序-數(shù)據(jù)-運行” 或“資源-調(diào)度-運行” 經(jīng)典例子：“按照菜譜作菜”“樂隊演奏” 或“向服務(wù)員請求服務(wù)”等 8進(jìn)程同步和互斥（一）問題：用P.V操作解決下圖之同步問題getcopyputfstg9進(jìn)程同步和互斥（一）cpcgpcgpg一個數(shù)據(jù)上的操作順序：get-copy-putGet不能向“滿”的S中放；Copy不能從“空”的S中?。徊荒芟颉皾M”的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進(jìn)程同步和互斥（二）問題：用P.V操作解決下面問題司機(jī)進(jìn)程：REPEAT啟動車輛正常駕駛到站停車UNTIL…售票員進(jìn)程：REPEAT關(guān)門售票開門UNTIL…12信號量：

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

啟動；駕駛；停車；

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

關(guān)門；

V(S_Door);

售票；

P(S_Stop);

開門；

Untilfalse;End 同步要求：先關(guān)門，后開車； 先停車，后開門13問題：

推廣讀寫者問題中的消息緩沖處理。消息緩沖區(qū)為k個，有m個發(fā)送進(jìn)程，n個接收進(jìn)程，每個接收進(jìn)程對發(fā)送來的消息都必須取一次

進(jì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是緩沖區(qū)大??；n是接收進(jìn)程個數(shù)}{m是發(fā)送進(jìn)程個數(shù)，通過s進(jìn)行“寫互斥”}15ProcedureSender_i(i:integer);{i為發(fā)送進(jìn)程的標(biāo)號}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為接收進(jìn)程的標(biāo)號}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第二類讀者寫者問題（寫者優(yōu)先）1）共享讀2）互斥寫、讀寫互斥3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù) 讀者必須等待，喚醒時優(yōu)先考慮寫者）進(jìn)程同步和互斥（四）17Var mutex:semaphore;{互斥信號量，初值為1}R:semaphore;{對應(yīng)讀者等待隊列，初值為0}W:semaphore;{對應(yīng)寫者等待隊列，初值為0}{一般變量：}Writing:Boolean;{初值false,有寫者正在寫}rc :integer;{初值0,共享讀的讀者數(shù)}rq :integer;{初值0,等待隊列中讀者數(shù)}wq :integer;{初值0,等待隊列中寫者數(shù)}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讀者進(jìn)程(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寫者進(jìn)程(a)檢測是否有進(jìn)程正在讀寫(b)Writing(T);Write();Writing(F)(c)處理寫者等待隊列;處理Reader等待隊列20P(s): s:=s-1; Ifs<0 Then將本進(jìn)程插入相應(yīng)隊列末尾等待；V(s)：s:=s+1; Ifs<=0 Then

從等待隊列隊尾取一個進(jìn)程喚醒， 插入就緒隊列進(jìn)程同步和互斥（五）對P/V操作定義作以下修改21問題：1）這樣定義P、V操作是否有問題？ 不合理：先進(jìn)后出；可能“無限等待”2）用這樣的P、V操作實現(xiàn)N個進(jìn)程競爭使用某一共享變量的互斥機(jī)制。 思路：令等待隊列中始終只有一個進(jìn)程。 將“?！弊兂伞瓣犃小?/p>

VarS:array[1..n-1]ofsemaphore; {n為進(jìn)程數(shù)目；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）的解法，有無效率更高的方法。如有，試問降低了多少復(fù)雜性？ 上述解法每次都需要做2n次P/V操作，性能低下。采用二叉樹的思想，改進(jìn)如下： S[1..4]P[1..4]S1S2S3讓信號量處于不同的層次上，每個信號量至多控制兩個進(jìn)程（對兩個進(jìn)程進(jìn)行同步）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;不妨設(shè)有4個進(jìn)程P1..P4，VarS1,S2,S3:semaphore;{初值為1}假設(shè)共有2N個進(jìn)程爭用臨界區(qū)；時間復(fù)雜性：2Nvs N；空間復(fù)雜性：2Nvs2N－125理發(fā)師問題理發(fā)店里有一位理發(fā)師,一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子.如果沒有顧客,則理發(fā)師便在理發(fā)椅上睡覺.當(dāng)一個顧客到來時,他必須先喚醒理發(fā)師.如果顧客到來時理發(fā)師正在理發(fā)，則如果有空椅子，可坐下來等；否則離開。進(jìn)程同步和互斥（六）26顧客進(jìn)程i:P(Sn);{門外觀望}P(mutex);進(jìn)門；V(mutex);V(S);等候；理發(fā)；V(Sn)P(mutex);出門；V(mutex);Var Sn: semaphore;{位子數(shù)目，初值為n} S: semaphore;{理發(fā)師睡覺，初值為1}mutex: semaphore;{初值為1}理發(fā)師進(jìn)程：RepeatP(S);P(mutex);

叫人理發(fā)；

V(mutex);

理發(fā)；Untilfalse;27用P.V操作來實現(xiàn)Receive原語:Receive（S，M）