操作系統(tǒng)PV習(xí)題課PPT學(xué)習(xí)教案

1、會計學(xué)1 操作系統(tǒng)操作系統(tǒng)PV習(xí)題課習(xí)題課PPT課件課件 進(jìn) 程 概 念（一） 問題：如果系統(tǒng)中有問題：如果系統(tǒng)中有N個進(jìn)程，個進(jìn)程， 4運行進(jìn)程最多幾個，最少幾個？運行進(jìn)程最多幾個，最少幾個？ 4就緒進(jìn)程最多幾個，最少幾個？就緒進(jìn)程最多幾個，最少幾個？ 4等待進(jìn)程最多幾個，最少幾個？等待進(jìn)程最多幾個，最少幾個？ 第1頁/共24頁 解答解答：運行進(jìn)程最多：運行進(jìn)程最多1 1個，最少個，最少0 0個；個； 就緒進(jìn)程最多就緒進(jìn)程最多N-1-1個，最少個，最少0 0個；個； 等待進(jìn)程最多等待進(jìn)程最多N個，最少個，最少0 0個；個； 第2頁/共24頁 問題一問題一：用用P.VP.V操作解決下圖之同步問

2、題操作解決下圖之同步問題 getcopyput fstg 第3頁/共24頁 一個數(shù)據(jù)上的操作順序：一個數(shù)據(jù)上的操作順序：get - copy - put c p c g p c g pg Get不能向不能向“滿滿”的的S中放；中放； Copy不能從不能從“空空”的的S中?。徊荒芟蛑腥?；不能向“滿滿”的的T中中 放；放； Put不能不能“空空”的的T中取中取 第4頁/共24頁 （同步）信號量：（同步）信號量：實際上也起到互斥作用實際上也起到互斥作用 S_Empty, T_Empty， 初值為初值為1 S_Full, T_Full; 初值為初值為0 Get: Begin Repeat P(S_Em

3、pty) T_get_S(); V(S_Full); Until false; End Copy: Begin Repeat P(S_Full); P(T_Empty); S_copy_T(); V(T_Full); V(S_Empty); Until false; End Put: Begin Repeat P(T_Full); T_put_G(); V(T_Empty); Until false; End 第5頁/共24頁 進(jìn)程同步和互斥（二） 問題：用問題：用P.V操作解決下面問題操作解決下面問題 司機(jī)進(jìn)程：司機(jī)進(jìn)程： REPEAT 啟動車輛啟動車輛 正常駕駛正常駕駛 到站停車到站停車

4、UNTIL 售票員進(jìn)程：售票員進(jìn)程： REPEAT 關(guān)門關(guān)門 售票售票 開門開門 UNTIL 第6頁/共24頁 信號量：信號量： S_Door, 初值為初值為0 S_Stop; 初值為初值為0 司機(jī)進(jìn)程司機(jī)進(jìn)程： Begin Repeat P(S_Door); 啟動；啟動； 駕駛；駕駛； 停車；停車； V(S_Stop); Until false; End 乘務(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)門，后開車； 先停車，后開門先

5、停車，后開門 第7頁/共24頁 第二類讀者寫者問題（寫者優(yōu)先）第二類讀者寫者問題（寫者優(yōu)先） 1）共享讀）共享讀 2）互斥寫、讀寫互斥）互斥寫、讀寫互斥 3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必 須等待，喚醒時優(yōu)先考慮寫者）須等待，喚醒時優(yōu)先考慮寫者） 進(jìn)程同步和互斥（三） 第8頁/共24頁 Var mutex: semaphore; 互斥信號量，初值為互斥信號量，初值為1 R : semaphore; 對應(yīng)讀者等待隊列，初值為對應(yīng)讀者等待隊列，初值為0 W: semaphore; 對應(yīng)寫者等待隊列，初值為對應(yīng)寫者等待隊列，初值為0 一般變量：一般

6、變量： Writing: Boolean; 初值初值false, 有寫者正在寫有寫者正在寫 rc: integer; 初值初值0, 共享讀的讀者數(shù)共享讀的讀者數(shù) rq: integer; 初值初值0,等待隊列中讀者數(shù)等待隊列中讀者數(shù) wq: integer; 初值初值0,等待隊列中寫者數(shù)等待隊列中寫者數(shù) 第9頁/共24頁 讀者進(jìn)程 Begin Repeat P(mutex); If (Writing OR wq0) Then Begin rq:=rq+1; V(mutex); P(R); P(mutex); resume End; rc:=rc+1; V(mutex); Read(); 第10

7、頁/共24頁 P(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 false End 第11頁/共24頁 寫者進(jìn)程 Begin Repeat P(mutex); If (Writing OR rc0) Then Begin wq:=wq+1; V(mutex); P(W); End; Else Begin Writing:=true; V(mutex); Write(); 第12頁/共24頁 P(mutex); If

8、 (wq0) Then Begin wq:=wq-1; V(mutex); V(W); End Else 第13頁/共24頁 If (rq0) Then Begin Writing:=false; While (rq0) Begin rq:=rq-1; V(R); End End Else Begin Writing:=false; V(mutex); End End Until false 第14頁/共24頁 理發(fā)師問題理發(fā)師問題: 理發(fā)店里有一位理發(fā)師理發(fā)店里有一位理發(fā)師,一把理發(fā)椅和一把理發(fā)椅和N把供把供 等候理發(fā)的顧客坐的椅子等候理發(fā)的顧客坐的椅子.如果沒有顧客如果沒有顧客,則理發(fā)師則

9、理發(fā)師 便在理發(fā)椅上睡覺便在理發(fā)椅上睡覺.當(dāng)一個顧客到來時當(dāng)一個顧客到來時,他必須先喚他必須先喚 醒理發(fā)師醒理發(fā)師.如果顧客到來時理發(fā)師正在理發(fā)，則如如果顧客到來時理發(fā)師正在理發(fā)，則如 果有空椅子，可坐下來等；否則離開。果有空椅子，可坐下來等；否則離開。 進(jìn)程同步和互斥（四） 第15頁/共24頁 Var Sn: semaphore; 位子數(shù)目，初值為位子數(shù)目，初值為n S: semaphore; 理發(fā)師睡覺，初值為理發(fā)師睡覺，初值為0 mutex: semaphore; 初值為初值為1 顧客進(jìn)程顧客進(jìn)程 i: P(Sn);門外觀望門外觀望 P(mutex); 進(jìn)門；進(jìn)門； V(mutex);

10、V(S); 等候；等候； 理發(fā)；理發(fā)； V(Sn) P(mutex); 出門；出門； V(mutex); 第16頁/共24頁 理發(fā)師進(jìn)程理發(fā)師進(jìn)程 ： Repeat P(S); P(mutex); 叫人理發(fā)；叫人理發(fā)； V(mutex); 理發(fā)；理發(fā)； Until false; 第17頁/共24頁 問題：問題： 推廣讀寫者問題中的消息緩沖處理。消息推廣讀寫者問題中的消息緩沖處理。消息 緩沖區(qū)為緩沖區(qū)為k個，有個，有m個發(fā)送進(jìn)程，個發(fā)送進(jìn)程，n個接收進(jìn)程，個接收進(jìn)程， 每個接收進(jìn)程對發(fā)送來的消息都必須取一次每個接收進(jìn)程對發(fā)送來的消息都必須取一次 進(jìn)程同步和互斥（五） 第18頁/共24頁 解題思路

11、：解題思路： 發(fā)送者發(fā)送消息后喚醒所有的接收者；發(fā)送者發(fā)送消息后喚醒所有的接收者； 所有的接收者都接收后空出緩沖區(qū)；所有的接收者都接收后空出緩沖區(qū)； 接收者接收時要修改接收次數(shù)；接收者接收時要修改接收次數(shù)； 接收計數(shù)和緩沖區(qū)的指針為臨界資源，訪問接收計數(shù)和緩沖區(qū)的指針為臨界資源，訪問 時要互斥時要互斥 。 第19頁/共24頁 Type BufferType = Record msg:MessageType; count:integer; mutex:semaphore; 初值為初值為1 empty: semaphore; 初值為初值為1 full: array 1.n of semaphore

12、； 初值全為初值全為0 End Var mutex: semaphore; 初值為初值為1 s: integer; 初值為初值為0 buff: array 0.k-1 of BufferType; k是緩沖區(qū)大??；是緩沖區(qū)大小； n是接收進(jìn)程個數(shù)是接收進(jìn)程個數(shù) m是發(fā)送進(jìn)程個數(shù)，通過是發(fā)送進(jìn)程個數(shù)，通過 s 進(jìn)行進(jìn)行“寫互斥寫互斥” 第20頁/共24頁 Procedure Sender_i(i:integer); i 為發(fā)送進(jìn)程的標(biāo)號為發(fā)送進(jìn)程的標(biā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; End 第21頁/共24頁 Procedure Recvr(i:integer); i 為接收進(jìn)程的標(biāo)號為接收進(jìn)程的標(biāo)號 Varj: integer; Begin j:=