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

1、Silberschatz, Galvin and Gagne 20022.1Operating System Concepts操作系統(tǒng)習(xí)題講解n一、一、進(jìn)程概念進(jìn)程概念n二、二、進(jìn)程同步和互斥進(jìn)程同步和互斥Silberschatz, Galvin and Gagne 20022.2Operating System Concepts進(jìn) 程 概 念（一）問(wèn)題：如果系統(tǒng)中有問(wèn)題：如果系統(tǒng)中有N個(gè)進(jìn)程，個(gè)進(jìn)程，4運(yùn)行進(jìn)程最多幾個(gè)，最少幾個(gè)？運(yùn)行進(jìn)程最多幾個(gè)，最少幾個(gè)？4就緒進(jìn)程最多幾個(gè)，最少幾個(gè)？就緒進(jìn)程最多幾個(gè)，最少幾個(gè)？4等待進(jìn)程最多幾個(gè)，最少幾個(gè)？等待進(jìn)程最多幾個(gè)，最少幾個(gè)？Silberscha

2、tz, Galvin and Gagne 20022.3Operating System Concepts解答解答：運(yùn)行進(jìn)程最多：運(yùn)行進(jìn)程最多1 1個(gè)，最少個(gè)，最少0 0個(gè)；個(gè)； 就緒進(jìn)程最多就緒進(jìn)程最多N-1-1個(gè)，最少個(gè)，最少0 0個(gè)；個(gè)； 等待進(jìn)程最多等待進(jìn)程最多N個(gè)，最少個(gè)，最少0 0個(gè)；個(gè)；Silberschatz, Galvin and Gagne 20022.4Operating System Concepts進(jìn)程同步和互斥（一）問(wèn)題一問(wèn)題一：用用P.VP.V操作解決下圖之同步問(wèn)題操作解決下圖之同步問(wèn)題getcopyputfstgSilberschatz, Galvin and

3、Gagne 20022.5Operating System Concepts一個(gè)數(shù)據(jù)上的操作順序：一個(gè)數(shù)據(jù)上的操作順序：get - copy - putcpcgpcgpgGet不能向不能向“滿滿”的的S中放；中放；Copy不能從不能從“空空”的的S中取；不能向中??；不能向“滿滿”的的T中放；中放；Put不能不能“空空”的的T中取中取Silberschatz, Galvin and Gagne 20022.6Operating System Concepts（同步）信號(hào)量：（同步）信號(hào)量：實(shí)際上也起到互斥作用實(shí)際上也起到互斥作用S_Empty, T_Empty， 初值為初值為1S_Full, T

4、_Full; 初值為初值為0Get:Begin Repeat P(S_Empty) T_get_S(); V(S_Full); Until false;EndCopy:Begin Repeat P(S_Full); P(T_Empty); S_copy_T(); V(T_Full); V(S_Empty); Until false;EndPut:Begin Repeat P(T_Full); T_put_G(); V(T_Empty); Until false;EndSilberschatz, Galvin and Gagne 20022.7Operating System Concepts進(jìn)

5、程同步和互斥（二）問(wèn)題：用問(wèn)題：用P.V操作解決下面問(wèn)題操作解決下面問(wèn)題司機(jī)進(jìn)程：司機(jī)進(jìn)程：REPEAT啟動(dòng)車輛啟動(dòng)車輛正常駕駛正常駕駛到站停車到站停車UNTIL 售票員進(jìn)程：售票員進(jìn)程：REPEAT關(guān)門關(guān)門售票售票開門開門UNTIL Silberschatz, Galvin and Gagne 20022.8Operating System Concepts信號(hào)量：信號(hào)量：S_Door, 初值為初值為0S_Stop; 初值為初值為0司機(jī)進(jìn)程司機(jī)進(jìn)程：Begin Repeat P(S_Door); 啟動(dòng)；啟動(dòng)； 駕駛；駕駛； 停車；停車； V(S_Stop); Until false;End乘

6、務(wù)員進(jìn)程乘務(wù)員進(jìn)程:Begin Repeat 關(guān)門；關(guān)門； V(S_Door); 售票；售票； P(S_Stop); 開門；開門； Until false;End同步要求：先關(guān)門，后開車；同步要求：先關(guān)門，后開車； 先停車，后開門先停車，后開門Silberschatz, Galvin and Gagne 20022.9Operating System Concepts第二類讀者寫者問(wèn)題（寫者優(yōu)先）第二類讀者寫者問(wèn)題（寫者優(yōu)先）1）共享讀）共享讀2）互斥寫、讀寫互斥）互斥寫、讀寫互斥3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫者）

7、須等待，喚醒時(shí)優(yōu)先考慮寫者）進(jìn)程同步和互斥（三）Silberschatz, Galvin and Gagne 20022.10Operating System ConceptsVar mutex: semaphore; 互斥信號(hào)量，初值為互斥信號(hào)量，初值為1 R : semaphore; 對(duì)應(yīng)讀者等待隊(duì)列，初值為對(duì)應(yīng)讀者等待隊(duì)列，初值為0 W: semaphore; 對(duì)應(yīng)寫者等待隊(duì)列，初值為對(duì)應(yīng)寫者等待隊(duì)列，初值為0一般變量：一般變量： Writing: Boolean; 初值初值false, 有寫者正在寫有寫者正在寫 rc : integer; 初值初值0, 共享讀的讀者數(shù)共享讀的讀者數(shù) r

8、q : integer; 初值初值0,等待隊(duì)列中讀者數(shù)等待隊(duì)列中讀者數(shù) wq: integer; 初值初值0,等待隊(duì)列中寫者數(shù)等待隊(duì)列中寫者數(shù)Silberschatz, Galvin and Gagne 20022.11Operating System Concepts讀者進(jìn)程Begin RepeatP(mutex);If (Writing OR wq0) Then Beginrq:=rq+1; V(mutex);P(R);P(mutex); resume End;rc:=rc+1;V(mutex);Read();Silberschatz, Galvin and Gagne 20022.12O

9、perating System ConceptsP(mutex);rc:=rc-1;If (rc=0 AND wq0) Then Begin wq:=wq-1;Writing:=true;V(mutex);V(W); End;Else V(mutex); Until falseEndSilberschatz, Galvin and Gagne 20022.13Operating System Concepts寫者進(jìn)程Begin RepeatP(mutex);If (Writing OR rc0)Then Begin wq:=wq+1; V(mutex); P(W); End;Else Begi

10、nWriting:=true; V(mutex);Write();Silberschatz, Galvin and Gagne 20022.14Operating System Concepts P(mutex);If (wq0)Then Beginwq:=wq-1;V(mutex);V(W); EndElseSilberschatz, Galvin and Gagne 20022.15Operating System Concepts If (rq0)Then BeginWriting:=false;While (rq0) Beginrq:=rq-1;V(R) ; End EndElse B

11、eginWriting:=false;V(mutex); EndEnd Until falseSilberschatz, Galvin and Gagne 20022.16Operating System Concepts理發(fā)師問(wèn)題理發(fā)師問(wèn)題: 理發(fā)店里有一位理發(fā)師理發(fā)店里有一位理發(fā)師,一把理發(fā)椅和一把理發(fā)椅和N把供把供等候理發(fā)的顧客坐的椅子等候理發(fā)的顧客坐的椅子.如果沒(méi)有顧客如果沒(méi)有顧客,則理發(fā)師則理發(fā)師便在理發(fā)椅上睡覺(jué)便在理發(fā)椅上睡覺(jué).當(dāng)一個(gè)顧客到來(lái)時(shí)當(dāng)一個(gè)顧客到來(lái)時(shí),他必須先喚他必須先喚醒理發(fā)師醒理發(fā)師.如果顧客到來(lái)時(shí)理發(fā)師正在理發(fā)，則如如果顧客到來(lái)時(shí)理發(fā)師正在理發(fā)，則如果有空椅子，可坐

12、下來(lái)等；否則離開。果有空椅子，可坐下來(lái)等；否則離開。進(jìn)程同步和互斥（四）Silberschatz, Galvin and Gagne 20022.17Operating System Concepts Var Sn: semaphore; 位子數(shù)目，初值為位子數(shù)目，初值為n S: semaphore; 理發(fā)師睡覺(jué)，初值為理發(fā)師睡覺(jué)，初值為0 mutex: semaphore; 初值為初值為1顧客進(jìn)程顧客進(jìn)程 i:P(Sn);門外觀望門外觀望P(mutex);進(jìn)門；進(jìn)門；V(mutex);V(S);等候；等候；理發(fā)；理發(fā)；V(Sn)P(mutex);出門；出門；V(mutex);Silbersc

13、hatz, Galvin and Gagne 20022.18Operating System Concepts理發(fā)師進(jìn)程理發(fā)師進(jìn)程 ：Repeat P(S); P(mutex); 叫人理發(fā)；叫人理發(fā)； V(mutex); 理發(fā)；理發(fā)；Until false;Silberschatz, Galvin and Gagne 20022.19Operating System Concepts問(wèn)題：?jiǎn)栴}：推廣讀寫者問(wèn)題中的消息緩沖處理。消息緩?fù)茝V讀寫者問(wèn)題中的消息緩沖處理。消息緩沖區(qū)為沖區(qū)為k個(gè)，有個(gè)，有m個(gè)發(fā)送進(jìn)程，個(gè)發(fā)送進(jìn)程，n個(gè)接收進(jìn)程，每個(gè)接收進(jìn)程，每個(gè)接收進(jìn)程對(duì)發(fā)送來(lái)的消息都必須取一次個(gè)接收

14、進(jìn)程對(duì)發(fā)送來(lái)的消息都必須取一次 進(jìn)程同步和互斥（五）Silberschatz, Galvin and Gagne 20022.20Operating System Concepts解題思路：解題思路： 發(fā)送者發(fā)送消息后喚醒所有的接收者；發(fā)送者發(fā)送消息后喚醒所有的接收者； 所有的接收者都接收后空出緩沖區(qū)；所有的接收者都接收后空出緩沖區(qū)； 接收者接收時(shí)要修改接收次數(shù)；接收者接收時(shí)要修改接收次數(shù)； 接收計(jì)數(shù)和緩沖區(qū)的指針為臨界資源，訪問(wèn)接收計(jì)數(shù)和緩沖區(qū)的指針為臨界資源，訪問(wèn)時(shí)要互斥時(shí)要互斥 。Silberschatz, Galvin and Gagne 20022.21Operating Syste

15、m Concepts Type BufferType = Recordmsg:MessageType;count:integer;mutex:semaphore; 初值為初值為1empty: semaphore; 初值為初值為1full: array 1.n of semaphore； 初值全為初值全為0EndVar mutex: semaphore; 初值為初值為1s: integer; 初值為初值為0buff: array 0.k-1 of BufferType; k是緩沖區(qū)大??；是緩沖區(qū)大??； n是接收進(jìn)程個(gè)數(shù)是接收進(jìn)程個(gè)數(shù) m是發(fā)送進(jìn)程個(gè)數(shù)，通過(guò)是發(fā)送進(jìn)程個(gè)數(shù)，通過(guò) s 進(jìn)行進(jìn)行“寫互

16、斥寫互斥” Silberschatz, Galvin and Gagne 20022.22Operating System Concepts Procedure Sender_i(i:integer); i 為發(fā)送進(jìn)程的標(biāo)號(hào)為發(fā)送進(jìn)程的標(biāo)號(hào)Vars0, j: integer;Begin Repeat P(mutex); s0:=s; s:=(s+1) mod k; V(mutex); P(buffs0.empty)； 在在buffs0.msg中寫信息；中寫信息； P(buffs0.mutex)； buffs0.count:=n; V(buffs0.mutex); For (j:=1 to n do) V(buffs0.fullj); Until false;EndSilberschatz, Galvin and Gagne 20022.23Operating System ConceptsProcedure Recvr(i:integer); i 為接收進(jìn)程的標(biāo)號(hào)為接收進(jìn)程的標(biāo)號(hào)Varj: