操作系統(tǒng)原理教程(第3版)第三章課件

1、第3章 進(jìn)程之間的并發(fā)控制和死鎖第3章 進(jìn)程之間的并發(fā)控制和死鎖2.6 進(jìn)程之間的低級通信 多道程序系統(tǒng)中進(jìn)程是并發(fā)執(zhí)行的，并發(fā)進(jìn)程之間存在著相互制約關(guān)系，為了協(xié)調(diào)進(jìn)程之間的相互制約關(guān)系，就需要實(shí)現(xiàn)進(jìn)程的低級通信。 系統(tǒng)之間之所以有這種關(guān)系是由于以下兩方面的原因造成的：2.6 進(jìn)程之間的低級通信 (1) 各并發(fā)進(jìn)程對資源的共享 互斥關(guān)系：通過共享資源而使進(jìn)程之間產(chǎn)生的關(guān)系叫做間接制約關(guān)系，又叫做互斥關(guān)系。 用“進(jìn)程-資源-進(jìn)程” 描述。例 進(jìn)程P1和P2在運(yùn)行中都要使用打印機(jī)，為了使各進(jìn)程輸出的完整性，打印機(jī)的使用必須獨(dú)占。一旦系統(tǒng)將打印機(jī)分配給進(jìn)程P1，那么進(jìn)程P2必須等待。P1-打印機(jī)-P

2、2(1) 各并發(fā)進(jìn)程對資源的共享 (2) 系統(tǒng)中存在若干協(xié)作進(jìn)程 同步關(guān)系：一個用戶作業(yè)涉及一組并發(fā)進(jìn)程（輸入、計(jì)算和輸出進(jìn)程），這些進(jìn)程須相互協(xié)作共同完成這項(xiàng)任務(wù)。進(jìn)程之間的這種制約關(guān)系叫做直接制約關(guān)系。 互斥是同步的一種特殊情況。低級通信：進(jìn)程之間的這種相互依賴又相互制約、相互合作又相互競爭的關(guān)系，也即進(jìn)程的同步與互斥關(guān)系,也叫進(jìn)程之間的低級通信。(2) 系統(tǒng)中存在若干協(xié)作進(jìn)程 共享資源引起進(jìn)程之間的互斥幾個基本概念： 共享資源：慢速的硬設(shè)備，如打印機(jī)等資源，軟件資源，如共享變量、共享文件等。 臨界資源：一次僅允許一個進(jìn)程使用的資源。具有這種特點(diǎn)的上述資源。臨界資源：上一章打印機(jī)的例子：如

3、何避免這種情況發(fā)生，關(guān)鍵是防止多個進(jìn)程同時讀或?qū)懝蚕頂?shù)據(jù)。換句話就是必須互斥的使用共享變量in。 臨界區(qū)(critical section)：就是并發(fā)執(zhí)行的進(jìn)程訪問臨界資源的那個必須互斥執(zhí)行的程序段。 2.6.1 進(jìn)程之間的互斥 共享資源引起進(jìn)程之間的互斥 2.6.1 進(jìn)程之間的互斥 進(jìn)程之間的互斥為進(jìn)一步說明臨界資源的概念，下面舉一個著名的進(jìn)程同步問題的例子：生產(chǎn)者_(dá)消費(fèi)者問題。在生產(chǎn)者與消費(fèi)者問題中，描述的是生產(chǎn)者與消費(fèi)者的關(guān)系。有一個生產(chǎn)者進(jìn)程生產(chǎn)產(chǎn)品，并將所生產(chǎn)的產(chǎn)品提供給一個消費(fèi)者進(jìn)程去消費(fèi)。為了使生產(chǎn)者與消費(fèi)者并發(fā)進(jìn)行，在兩者之間設(shè)置了一個具有n個緩沖區(qū)的緩沖池，盡管生產(chǎn)者與消費(fèi)者

4、都以異步的方式進(jìn)行，但是它們之間必須保持一定的同步關(guān)系。即消費(fèi)者進(jìn)程不允許到空緩沖區(qū)去取產(chǎn)品，也不允許生產(chǎn)者進(jìn)程向一個已裝滿產(chǎn)品，且尚未取走的緩沖區(qū)投放產(chǎn)品。進(jìn)程之間的互斥為進(jìn)一步說明臨界資源的概念，下面舉一個著名的進(jìn)進(jìn)程之間的互斥我們利用一個數(shù)組表示上述具有n個緩沖區(qū)的緩沖池。使用輸入指針in指示下一個可以放產(chǎn)品的緩沖區(qū)，每放一個產(chǎn)品指針加1。用一個輸出指針out指示下一個可以取從中取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程從緩沖區(qū)取走一個產(chǎn)品輸出指針加1由于緩沖區(qū)使用的是循環(huán)緩沖數(shù)組方式，所以輸入加1表示為in=（in+1）mod n同樣輸出加1表示為out=（out+1）mod n當(dāng)（in+1）mo

5、d n=out，表示緩沖區(qū)滿。初始狀態(tài)in=out表示緩沖區(qū)空。此外還要設(shè)置一個表示緩沖區(qū)產(chǎn)品數(shù)量的變量counter初值為0，每投放一個產(chǎn)品counter加1，消費(fèi)者每取走一個產(chǎn)品counter減1進(jìn)程之間的互斥我們利用一個數(shù)組表示上述具有n個緩沖區(qū)的緩沖池進(jìn)程之間的互斥生產(chǎn)者與消費(fèi)者共享下列變量：Var n, integer; Type item=“” ;Var buffer:arry0,1,2,n-1of item;In, out :0,1,.n-1;Counter: 0,1,n;In和out初始化為1。Noop表示控操作；While condition do no-op語句表示重復(fù)測試

6、條件（condition）直到條件為假false.生產(chǎn)者使用一個局部變量nextp,用于存放每次剛剛生產(chǎn)出來的產(chǎn)品，消費(fèi)者使用一局部變量nextc存放每次將要消費(fèi)的產(chǎn)品。則有程序：進(jìn)程之間的互斥生產(chǎn)者與消費(fèi)者共享下列變量：進(jìn)程之間的互斥Producer: repeat produce an item in nextp;. while counter=n do no-op; bufferin:=nextp; In:=(in+1)mod n; Counter:=counter+1; Until fase;Consumer: repeat while counter=0 do no-op; next

7、c:=bufferout; out:=(out+1)mod n counter:=counter-1; consumer the item in nextc; until false進(jìn)程之間的互斥進(jìn)程之間的互斥這個程序顯然是正確的，串行運(yùn)行也是正確的，但是如果并行運(yùn)行結(jié)果就不一定正確：其問題出現(xiàn)在兩個進(jìn)程共享了變量counter。其生產(chǎn)者加1操作和消費(fèi)者的減1操作，在計(jì)算機(jī)上實(shí)現(xiàn)時可用下面語句描述：其生產(chǎn)者加1操作:Register1:=counter;Register1:=register1+1;Counter:=register1;消費(fèi)者減1操作:Register2:=counter;Re

8、gister2:=register2-1;Counter:=register2;假設(shè)現(xiàn)在counter當(dāng)前值為5進(jìn)程之間的互斥這個程序顯然是正確的，串行運(yùn)行也是正確的，但是如果順序執(zhí)行先生產(chǎn)者后消費(fèi)者執(zhí)行一遍counter內(nèi)的值為5，但按如下順序執(zhí)行：Register1:=counter; register1=5Register1:=register1+1； register1=6Register2:=counter; register2=5Register2:=register2-1; register2=4Counter:=register1; counter=6Counter:=regi

9、ster2； counter=4正確值應(yīng)該是5，可執(zhí)行結(jié)果為4.又是結(jié)果還可能是6。表明程序并運(yùn)行時已失去了再現(xiàn)性。這就是因?yàn)閏ounter變量屬于臨界資源，而生產(chǎn)者與消費(fèi)者沒有互斥的訪問它們，對counter的訪問具有很大的任意性，故產(chǎn)生了不確定性，解決問題的關(guān)鍵是將counter作為臨界資源來處理，即要求生產(chǎn)者和消費(fèi)者互斥訪問。進(jìn)程之間的互斥如果順序執(zhí)行先生產(chǎn)者后消費(fèi)者執(zhí)行一遍counter內(nèi)的值為進(jìn)程之間的互斥臨界區(qū)(critical section)：就是并發(fā)執(zhí)行的進(jìn)程訪問臨界資源的那個必須互斥執(zhí)行的程序段。在實(shí)現(xiàn)互斥時如果采取整體的程序采取互斥運(yùn)行將會大大降低進(jìn)程的并發(fā)性。事實(shí)上每個

10、進(jìn)程訪問某個臨界區(qū)的代碼只是一小段，因此只需控制進(jìn)程互斥的進(jìn)入這一小段代碼。我們將這一小段代碼叫做臨界區(qū)。為此進(jìn)程在進(jìn)入臨界區(qū)之前應(yīng)對臨界區(qū)進(jìn)行檢查，看是否被訪問的標(biāo)志，我們將這一段代碼成為進(jìn)入?yún)^(qū)(entry section),同樣退出臨界區(qū)應(yīng)將其標(biāo)志為未被訪問，這一段代碼稱為退出區(qū)（exit section）此外的代碼可成為剩余區(qū)（remainder section）于是可以將訪問臨界資源的循環(huán)進(jìn)程描述為進(jìn)程之間的互斥臨界區(qū)(critical section)：就進(jìn)程之間的互斥 repeat entry section critical section Exit section Remain

11、der sectionUntil false進(jìn)程之間的互斥 repeat 任何時刻最多只有一個進(jìn)程位于臨界區(qū)。有空讓進(jìn)當(dāng)已有進(jìn)程處于其臨界區(qū)時，后到達(dá)的進(jìn)程只能在外等待。無空等待不應(yīng)該使要進(jìn)入臨界區(qū)的進(jìn)程無限期地等待在臨界區(qū)之外。有限等待不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)先釋放處理機(jī)，轉(zhuǎn)換到阻塞狀態(tài)。讓權(quán)等待 為了正確而有效地使用臨界資源，系統(tǒng)中的并發(fā)進(jìn)程需要遵循如下四個準(zhǔn)則：有空讓進(jìn)；無空等待；有限等待；讓權(quán)等待。任何時刻最多只有一個進(jìn)程位于臨界區(qū)。有空讓進(jìn) 為了正 2. 解決進(jìn)程之間互斥的方法 (1) 關(guān)中斷 解決進(jìn)程互斥的最簡單辦法是當(dāng)一個進(jìn)程正在臨界區(qū)執(zhí)行時，關(guān)閉所有的中斷。 當(dāng)進(jìn)程退出臨界段時

12、，再開中斷。之后其它要進(jìn)入臨界區(qū)的進(jìn)程就可進(jìn)入。描述如下： 關(guān)中斷(disable) critical section 開中斷(enable) 優(yōu)點(diǎn)：簡單。缺點(diǎn)：限制了進(jìn)程并發(fā)執(zhí)行的能力。 在多處理機(jī)情況下，這種方法不靈。 2. 解決進(jìn)程之間互斥的方法 關(guān)中斷(dis鎖位變量W ：為每個臨界資源設(shè)置一個，以指示該資源當(dāng)前的狀態(tài)。系統(tǒng)初始化時，將W置為0。 Testset指令可定義如下：(2) 使用測試和設(shè)置指令(test and set) testset(int w) l: if(w=0) w=1; else goto l; /一條機(jī)器指令，其執(zhí)行不可被中斷。鎖位變量W ：為每個臨界資源設(shè)置一

13、個，以指示該資源當(dāng)前的狀態(tài)Const int n=/*進(jìn)程數(shù) */int w;void p(int i) while(TRUE) testset(w); w=0; 顯然，采用這種加鎖語句，由于進(jìn)程循環(huán)測試，白白浪費(fèi)了CPU的時間。這種現(xiàn)象又叫做“忙等待”。void main() w=0; p(1);p(2);p(n);Const int n=/*進(jìn)程數(shù) */顯然，采用這種加鎖語同步的原因：一組進(jìn)程要合作完成一項(xiàng)任務(wù)。例兩個用戶進(jìn)程通過共享緩沖區(qū)完成其計(jì)算和打印任務(wù)。2.6.2 進(jìn)程之間的同步共享緩沖區(qū)計(jì)算進(jìn)程打印進(jìn)程計(jì)算進(jìn)程在緩沖區(qū)滿時等待，打印進(jìn)程在緩沖區(qū)空時等待。兩個進(jìn)程這種由于速度不匹配

14、引起的關(guān)系，需要進(jìn)行同步處理。為了解決進(jìn)程之間的同步，引入信號量機(jī)制。同步的原因：一組進(jìn)程要合作完成一項(xiàng)任務(wù)。2.6.2 進(jìn)1965年，荷蘭學(xué)者Dijkstra提出的一種同步機(jī)制。 基本原理：兩個或多個進(jìn)程可以通過簡單的信號機(jī)制，進(jìn)行同步。為此，需要引入一個稱作的特殊變量信號量。2.6.3 信號量和PV操作1965年，荷蘭學(xué)者Dijkstra提出的一種同步機(jī)制。 typedef struct semaphore int value; /表示該類資源的可用數(shù)量 struct process *pointer; /等待使用該類資源的進(jìn)程排成隊(duì)列的隊(duì)列頭指針。 sem; 對信號量s只允許執(zhí)行P、V操

15、作。 P、V操作由原語組成，執(zhí)行過程中不可分割。信號量的類型描述：Sem s；typedef struct semaphore 對信號量P（S)操作原語：void wait (sem s) s.value=s.value-1; /表示申請一個資源 if(s.value0) /申請資源不成功，阻塞等待。 add this process to s.pointer; block(); /“讓權(quán)等待” P（S)操作原語：V(S)操作原語：void signal(sem s) s.value=s.value+1; /釋放一個資源（或通過信號量s發(fā)消息） if(s.value=0) remove a p

16、rocess P from s. pointer; wakeup(P);/喚醒進(jìn)程P。 V(S)操作原語：顯然，P、V操作的引入，克服了加鎖操作的忙等待while(TRUE)循環(huán)現(xiàn)象，有效提高了系統(tǒng)的效率。 操作系統(tǒng)正是利用信號量的狀態(tài)對進(jìn)程和資源進(jìn)行管理和控制的。顯然，P、V操作的引入，克服了加鎖操作的忙等待while(對于互斥使用的資源，引入一個互斥信號量，用mutex表示。其初值為1。1. 利用信號量實(shí)現(xiàn)進(jìn)程之間的互斥int mutex=1;P1： P(mutex); critical section V(mutex); P2： P(mutex); critical section V(

17、mutex); 對于互斥使用的資源，引入一個互斥信號量，用mutex表示。其用信號量可以方便地解決n個進(jìn)程互斥地使用臨界資源，實(shí)現(xiàn)臨界區(qū)的互斥執(zhí)行問題。信號量的取值范圍是+1-(n-1)。信號量的值為負(fù)的含義：說明臨界區(qū)中有一個進(jìn)程正在執(zhí)行，有若干個進(jìn)程正在等待進(jìn)入。等待的進(jìn)程數(shù)為信號量值的絕對值。例若P、V操作的信號量初值為1，當(dāng)前值為-3，則表示有 3個等待進(jìn)程。用信號量可以方便地解決n個進(jìn)程互斥地使用臨界資源，實(shí)現(xiàn)臨界區(qū)例 用信號量實(shí)現(xiàn)計(jì)算進(jìn)程與打印進(jìn)程之間的同步過程。 假定計(jì)算進(jìn)程和打印進(jìn)程共享使用一個單緩沖的緩沖區(qū)。要解決兩者之間的同步，需要引入兩個同步信號量s1和s2。S1：表示緩

18、沖區(qū)是否空閑，初值為1; S2：表示緩沖區(qū)中是否有可供打印的計(jì)算結(jié)果，初始值為0。2. 利用信號量實(shí)現(xiàn)進(jìn)程之間的同步共享緩沖區(qū)計(jì)算進(jìn)程 Pc打印進(jìn)程 Pp例 用信號量實(shí)現(xiàn)計(jì)算進(jìn)程與打印進(jìn)程之間的同步過程。2. int s1=1，s2=0; Pc： compute next number; P(s1); add the number to buffer; V(s2); Pp： P(s2); take next number from buffer; V(s1); print the number; 能否用一個同步信號量？ int s1=1，s2=0;能否用一個同步信號量？計(jì)算機(jī)中的并發(fā)進(jìn)程，可以

19、抽象成生產(chǎn)者和消費(fèi)者問題進(jìn)行解決。生產(chǎn)者：運(yùn)行中的進(jìn)程當(dāng)其釋放一個資源或發(fā)一個信號時，可把它看成該資源或信號的生產(chǎn)者，消費(fèi)者：當(dāng)運(yùn)行中的進(jìn)程申請一個資源或接收一個信號時，又可把它看成該資源或信號的消費(fèi)者。電話號碼：買一個手機(jī)，消費(fèi)一個空資源。例 上述例子中計(jì)算進(jìn)程：被打印數(shù)據(jù)的生產(chǎn)者；空緩沖的消費(fèi)者打印進(jìn)程：被打印數(shù)據(jù)的消費(fèi)者；空緩沖的生產(chǎn)者3. 利用信號量解決生產(chǎn)者和消費(fèi)者問題計(jì)算機(jī)中的并發(fā)進(jìn)程，可以抽象成生產(chǎn)者和消費(fèi)者問題進(jìn)行解決。3 例假定有一組生產(chǎn)者和消費(fèi)者進(jìn)程，通過一個有界緩沖區(qū)發(fā)生聯(lián)系。正常情況下，生產(chǎn)者與消費(fèi)者可并發(fā)地釋放或取得緩沖區(qū)的產(chǎn)品。限制條件：緩沖區(qū)滿：生產(chǎn)者要等待；緩沖

20、區(qū)空，消費(fèi)者要等待。設(shè)共享緩沖區(qū)容量為k。存取緩沖區(qū)的限制：生產(chǎn)者/消費(fèi)者互斥地使用緩沖區(qū)。生產(chǎn)者進(jìn)程和消費(fèi)者需要同步存取緩沖區(qū)信息。 例empty：表示空緩沖塊的個數(shù)，初值為k；full：有數(shù)據(jù)的緩沖塊個數(shù)，初值為0。mutex：互斥訪問臨界區(qū)的信號量，初值為1（因?yàn)槎鄠€生產(chǎn)者互斥，相當(dāng)變量counter）。生產(chǎn)者1生產(chǎn)者2生產(chǎn)者M(jìn)放產(chǎn)品指針 i消費(fèi)者1消費(fèi)者2消費(fèi)者N取產(chǎn)品指針 jbuffer k（可以是一個循環(huán)棧）empty：表示空緩沖塊的個數(shù)，初值為k；生產(chǎn)者1放產(chǎn)品指針int mutex=1, empty=k, full=0, i=0, j=0; DataType buffer k;

21、 Producer： produce a product x; P(empty); /申請空緩沖塊 P(mutex); /實(shí)現(xiàn)對共享緩沖區(qū)的互斥訪問 buffer i = x; /放入產(chǎn)品 i = (i+1) % k; V(mutex); V(full); / 有數(shù)據(jù)的緩沖塊個數(shù)加1 int mutex=1, empty=k, full=0, Consumer： P(full); /申請有數(shù)據(jù)的緩沖塊 P(mutex); /實(shí)現(xiàn)對共享緩沖區(qū)的互斥訪問 y = buffer j; /取產(chǎn)品 j = (j+1) % k; V(mutex); V(empty); /空緩沖塊的個數(shù)加1 注意 每個進(jìn)程

22、中的P操作的次序是很重要的。P操作放置不當(dāng)，就可能死鎖。 Consumer：注意 讀/寫問題：有一個多進(jìn)程共享的數(shù)據(jù)區(qū)，這個數(shù)據(jù)區(qū)可以是一個文件或者主存的一塊空間；一些進(jìn)程（reader)只讀取這個數(shù)據(jù)區(qū)；一些進(jìn)程（writer)只往數(shù)據(jù)區(qū)中寫數(shù)據(jù)。讀寫必須滿足以下條件：允許任意多的讀進(jìn)程可以同時讀；一次只有一個寫進(jìn)程可寫；4. 讀者（reader)和寫者（writer)問題讀/寫問題：有一個多進(jìn)程共享的數(shù)據(jù)區(qū)，這個數(shù)據(jù)區(qū)可以是一個文計(jì)數(shù)器readcount：記錄同時讀的讀者數(shù)，初值為0。讀互斥信號量rmutex：使讀者互斥地訪問共享變量readcount，初值為1。 讀寫互斥信號量wrmut

23、ex：實(shí)現(xiàn)讀寫互斥和寫寫互斥地訪問共享文件，初值為1。讀寫同步的實(shí)現(xiàn)計(jì)數(shù)器readcount：記錄同時讀的讀者數(shù)，初值為0。讀寫int rmutex=1,wrmutex=1,readcount=0; Reader： P(rmutex); /互斥訪問readcount if readcount=0 then P(wrmutex); readcount+; V(rmutex); 讀文件; P(rmutex); readcount= readcount-1; if readcount=0 then V(wrmutex); V(rmutex);int rmutex=1,wrmutex=1,readco

24、u Writer： P(wrmutex); 寫文件； V(wrmutex)； Writer： 5 哲學(xué)家進(jìn)餐問題這也是一個典型的同步問題，是一大類并發(fā)控制問題的例子。假設(shè)有5個哲學(xué)家，花費(fèi)一生的時光思考和吃飯。在桌子上放著5只叉子。一個哲學(xué)家一次只能拿起一只叉子；僅當(dāng)拿有兩只叉子時才能吃飯；吃完，放下兩只叉子。5 哲學(xué)家進(jìn)餐問題這也是一個典型的同步問題，是一大類并發(fā)簡單的解決方法每只叉子都用一個信號量表示。semaphore fork5所有fork的元素被初始化為1。哲學(xué)家 i 的操作：do P(forki); P(fork(i+1)%5); eat V(forki); V (fork(i+1

25、)%5); thinkwhile(1);可能導(dǎo)致死鎖/饑餓最后一個人只能得到一把叉子不能吃飯將餓死簡單的解決方法每只叉子都用一個信號量表示。哲學(xué)家 i 的操作可能解決死鎖問題的方法最多只允許四個哲學(xué)家同時坐在桌子上。只有左右兩只叉子都可用時才允許他拿起叉子（他必須在臨界區(qū)內(nèi)拿起兩只叉子）。使用非對稱解決。奇數(shù)哲學(xué)家先拿起他左邊的叉子，接著拿起他右邊的叉子；偶數(shù)哲學(xué)家先拿起他右邊的叉子，接著拿起他左邊的叉子?？赡芙鉀Q死鎖問題的方法最多只允許四個哲學(xué)家同時坐在桌子上。2.6.4 管程信號量：編程負(fù)擔(dān)重，易出錯。管程(Monitor)：一種新的進(jìn)程間同步機(jī)制。管程比信號量容易控制。2.6.4 管程信

26、號量：編程負(fù)擔(dān)重，易出錯。1. 管程的定義基本思想：是把信號量及其pv操作原語封裝在一個對象內(nèi)部，將共享變量及對共享變量能夠進(jìn)行的所有操作集中在一個模塊中。管程：是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對該資源的操作過程所構(gòu)成的軟件模塊。管程提供互斥機(jī)制：一次只有一個進(jìn)程能在管程內(nèi)活動。從而，保證管程數(shù)據(jù)的一致性。組成：局部于該管程的共享數(shù)據(jù)的說明， 對共享數(shù)據(jù)執(zhí)行的一組操作過程的說明， 共享數(shù)據(jù)的初值設(shè)置語句。1. 管程的定義基本思想：是把信號量及其pv操作原語封裝在一2. 利用管程解決進(jìn)程之間的同步與互斥mutexshow: Monitor /管程名字 busy: boolean; /臨界資源是否

27、可用標(biāo)志，是管程 變量的說明， nonbusy: semaphore; /進(jìn)程等待隊(duì)列頭指針 define request, release; /管程中可供調(diào)用的過程說明 use wait, signal; /引用的外部模塊的過程說明 begin busy:=false; /為管程局部變量賦初值，表示資源空閑 end;（1）用管程解決臨界資源的互斥使用2. 利用管程解決進(jìn)程之間的同步與互斥mutexshow:procedure request /申請臨界資源的過程 begin if busy then wait(nonbusy);/忙則阻塞，并釋放對管程的互斥使用權(quán) busy:=true; /

28、設(shè)置資源已被占用標(biāo)志 end;procedure release /釋放臨界資源過程 begin busy:=false; /設(shè)置資源已空閑標(biāo)志 signal(nonbusy); /發(fā)信號，喚醒等待者 end;procedure request /申請臨界資源（2）用管程解決生產(chǎn)者和消費(fèi)者問題prod_conshow: Monitor rbuffer:array0.n-1of item; 有n個元素的環(huán)形緩沖區(qū) k: integer; 緩沖區(qū)中的元素個數(shù) nextempty,nextfull: integer; 送、取元素的指針 nonempty,nonfull:semaphore; 條件變量

29、 define put, get; 管程中定義的過程說明 use wait(), signal(); 引用外部模塊的過程說明 begin k=0; nextempty=nextfull=0; end; （2）用管程解決生產(chǎn)者和消費(fèi)者問題prod_conshow:procedure put(product: item) 向緩沖區(qū)送元素過程 begin if k=n then wait(nonempty); 緩沖區(qū)滿，生產(chǎn)者等待 rbuffernextempty=product; k=k+1; nextempty=(nextempty+1)mod n; signal(nonfull); 喚醒等待取

30、產(chǎn)品的消費(fèi)者 end;procedure get(product: goods) 從緩沖區(qū)取元素的過程 begin if k=0 then wait(nonfull); 緩沖區(qū)空，消費(fèi)者等待 goods=rbuffernextfull; k=k-1;procedure put(product: item) producer: 生產(chǎn)者進(jìn)程 begin produce an item; prod_conshow.put(item); end;consumer: 消費(fèi)者進(jìn)程 begin prod_conshow.get(item); consume the item; end; nextfull=(

31、nextfull+1)mod n; signal(nonempty); 喚醒等待送產(chǎn)品的生產(chǎn)者 end;producer: 生產(chǎn)者進(jìn)程 nextfull=(ne低級通信的缺點(diǎn)：效率低。生產(chǎn)者每次只能向緩沖區(qū)投放一個消息；消費(fèi)者每次只能從緩沖區(qū)取走一個消息。通信對用戶不透明。得由用戶（程序員）自己去實(shí)現(xiàn)通信。P、V操作使用不當(dāng)時，易導(dǎo)致死鎖。2.7 進(jìn)程之間的高級通信低級通信的缺點(diǎn)：2.7 進(jìn)程之間的高級通信高級通信：是指用戶可直接利用OS所提供的一組通信命令，高效地傳遞大量數(shù)據(jù)的一種通信方式。高級通信機(jī)制：是指進(jìn)程利用SO提供的，消息緩沖、信箱、管道、共享主存區(qū)等多種方式實(shí)現(xiàn)的通訊。高級通信：

32、是指用戶可直接利用OS所提供的一組通信命令，高效地非阻塞發(fā)送，阻塞接收發(fā)送進(jìn)程發(fā)送完繼續(xù)前進(jìn)，而接受進(jìn)程未收到消息則阻塞，等待接收。阻塞發(fā)送（類似）進(jìn)程執(zhí)行發(fā)送原語的規(guī)則進(jìn)程執(zhí)行接收原語的規(guī)則阻塞接收非阻塞接收非阻塞發(fā)送，阻塞接收進(jìn)程執(zhí)行發(fā)送原語的規(guī)則進(jìn)程執(zhí)行接收原語的接收者和發(fā)送者通信有如下組合方式：非阻塞發(fā)送，阻塞接收 例 服務(wù)器上的多個服務(wù)進(jìn)程平時處于阻塞狀態(tài)，一旦有客戶請求服務(wù)的消息到達(dá)，系統(tǒng)便喚醒相應(yīng)的服務(wù)進(jìn)程，去完成用戶所需要的服務(wù)。如：數(shù)據(jù)庫監(jiān)聽程序，端口號非阻塞發(fā)送，非阻塞接收 信件通信方式。單向通信方式。我們接收和發(fā)送E_mail，是一個例子。阻塞發(fā)送，阻塞接收 大多數(shù)的雙向

33、通訊，采用這種方式。打電話，類似。收發(fā)進(jìn)程的同步方式接收者和發(fā)送者通信有如下組合方式：收發(fā)進(jìn)程的同步方式1. 消息緩沖通信機(jī)制消息緩沖的實(shí)現(xiàn)方法屬于直接通信方式。系統(tǒng)設(shè)置一個由若干緩沖區(qū)組成的消息緩沖池，每個緩沖區(qū)可以存放一個完整的消息。欲發(fā)送消息進(jìn)程，向系統(tǒng)申請一個消息緩沖區(qū)，將消息存入緩沖區(qū)，然后把該緩沖區(qū)連入接收進(jìn)程的消息隊(duì)列上。消息隊(duì)列頭指針通常放在接收進(jìn)程控制塊PCB中。1. 消息緩沖通信機(jī)制（1） 消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)類型 struct message_buffer xx sender；/* 發(fā)送進(jìn)程標(biāo)識符*/ xx size； /* 消息長度*/ xx text； /*消息正文*

34、/ struct message_buffer *next； /*指向下一個 消息緩沖區(qū)的指針*/（1） 消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)類型（2） PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)描述 struct PCB mq； /消息隊(duì)列隊(duì)頭指針 mutex； /消息隊(duì)列互斥信號量 sm； /消息隊(duì)列同步信號量 （2） PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)描述發(fā)送者先在自己的地址區(qū)形成一個消息發(fā)送區(qū)，把待發(fā)送的消息正文、發(fā)送進(jìn)程標(biāo)識符、接收進(jìn)程標(biāo)識符、消息長度等信息填入其中，然后調(diào)用發(fā)送原語： send(receiver, message)；發(fā)送原語：申請一個 消息緩沖區(qū)，將消息從發(fā)送區(qū)傳入其中， 然后將該消息緩沖區(qū)掛到接收進(jìn)程的消息

35、隊(duì)列中。接收進(jìn)程先在自己的地址區(qū)形成一個消息接收區(qū)，然后調(diào)用接收原語： receive(sender, message)；接收原語：將消息接收到自己的接收區(qū)。 （3） 發(fā)送原語、接收原語發(fā)送者先在自己的地址區(qū)形成一個消息發(fā)送區(qū)，把待發(fā)送的消息正文send(B,a)text: Hellosize: 5sender: Aamqmutexsmsender: Asize: 5text:Hellonext: 0i第一消息緩沖區(qū)Receive(b)sender: Asize: 5text: HellobPCB(B)A進(jìn)程內(nèi)存空間B進(jìn)程內(nèi)存空間消息緩沖通信圖send(B,a)text: Hellosize:

36、 5sen send(receiver, a) /發(fā)送原語 getbuf(a.size, i)；/據(jù)a區(qū)長度申請一緩沖區(qū)i i.sender=a.sender; i.size=a.size; i.text=a.text; i.next=0; getid(PCB set, receiver j); /獲得接收進(jìn)程的內(nèi)部標(biāo)識符j P(j.mutex); insert(j.mq, i); /將i掛在接收進(jìn)程j的消息隊(duì)列mq上 V(j.mutex); V(j.sm); /消息隊(duì)列同步信號量sm send(receiver, a) /發(fā)送原語receive(b) /接收原語 j=get internal

37、 name; P(j.sm); /等消息 P(j. mutex); remove(j.mq, i); /從消息緩沖隊(duì)列mq中摘下第一個消息緩沖區(qū)i。 V(j.mutex); b.sender=i.sender; b.size=i.size; b.text=i.text;receive(b) /接收原語發(fā)送進(jìn)程將消息發(fā)送到某種中間實(shí)體（如信箱）中，接收進(jìn)程從中取得消息。是屬于間接通信方式 發(fā)送原語：send(A, Msg) 將一個消息Msg發(fā)送到信箱A。 接收原語：receive(A, Msg) 從信箱A中接收一個消息Msg。2. 信箱通信機(jī)制發(fā)送進(jìn)程將消息發(fā)送到某種中間實(shí)體（如信箱）中，接收進(jìn)

38、程從中取當(dāng)發(fā)送信件時，若指定的信箱未滿，則將信件送入由指針指示的信箱位置。若有等待該信箱中信件的接收者，則將其喚醒；否則（信箱滿）發(fā)送者等待，直到信箱有空位置為止。 當(dāng)接收信件時，若指定信箱中有信，則取走一封，并檢查是否有發(fā)送者在等待，若有則將其喚醒；否則（無信）等待，直到信箱中有信件時為止。當(dāng)發(fā)送信件時，若指定的信箱未滿，則將信件送入由指針指示的信箱3.管道和共享主存機(jī)制（1）管道管道：是指用于連接一個讀進(jìn)程和一個寫進(jìn)程，以實(shí)現(xiàn)它們之間通信的共享文件，又稱為pipe文件。（將在UNIX部分介紹）管道通信：發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的。發(fā)送進(jìn)程以字符流的形式將大量的數(shù)據(jù)送入管道；接收

39、進(jìn)程從管道中接收數(shù)據(jù)。（2）共享主存機(jī)制 在主存中劃出一塊共享存儲區(qū)，諸進(jìn)程通過讀或?qū)懝蚕碇鞔鎱^(qū)中的數(shù)據(jù)來實(shí)現(xiàn)通信。（速度快）3.管道和共享主存機(jī)制（1）管道2.8 死 鎖 在多道程序系統(tǒng)中，多個進(jìn)程可能同時競爭一定數(shù)量的資源。如果進(jìn)程由于申請不到資源，相互處于無休止的等待死 鎖。 例一個計(jì)算機(jī)系統(tǒng)，它有4臺磁帶機(jī)和2個并發(fā)執(zhí)行的進(jìn)程。每個進(jìn)程最多使用3臺磁帶機(jī)。某一時刻，每一進(jìn)程都已占有2臺磁帶機(jī)，還要再請求一臺磁帶機(jī)才能完成它們的任務(wù)。這時，由于系統(tǒng)再無空閑的磁帶機(jī)，兩個進(jìn)程就處于永遠(yuǎn)的相互等待狀態(tài)，我們就說系統(tǒng)產(chǎn)生了死鎖。2.8 死 鎖 在多道程序系統(tǒng)中，多個進(jìn)程可能同時競2.8.1 死

40、鎖的定義和死鎖產(chǎn)生的必要條件可搶占資源：如主存、CPU。當(dāng)資源從占用進(jìn)程剝奪走時，對進(jìn)程不產(chǎn)生什么破壞性的影響。不可搶占資源：如打印機(jī)、磁帶機(jī)等。一旦分配，不能強(qiáng)行收回，只能由使用者自動釋放。死鎖涉及的是不可搶占資源。1. 資源的特性資源：硬件和軟件之分資源：可搶占和不可搶占源之分2.8.1 死鎖的定義和死鎖產(chǎn)生的必要條件可搶占資源：如主 進(jìn)程使用資源的規(guī)則（1）請求資源：若請求不能立即滿足，則等待。（2）使用資源：獲得資源后，才能使用。（3）釋放資源：使用完畢，將資源歸還系統(tǒng)。一組進(jìn)程是死鎖的：是指這一組中的每個進(jìn)程都正在等待該組中的其他進(jìn)程占有資源時可能引起的一種錯誤現(xiàn)象。產(chǎn)生死鎖的根本原

41、因：系統(tǒng)中的資源數(shù)量不足，并發(fā)執(zhí)行進(jìn)程的推進(jìn)速度不當(dāng)。2. 死鎖的定義 進(jìn)程使用資源的規(guī)則一組進(jìn)程是死鎖的：是指這一組中的每個進(jìn)程互斥條件。（不可搶占的資源）保持和等待條件。（同時）不剝奪條件。（剝奪產(chǎn)生負(fù)面影響）循環(huán)等待條件。（相互）3. 死鎖產(chǎn)生的必要條件互斥條件。（不可搶占的資源）3. 死鎖產(chǎn)生的必要條件用有向圖研究解決死鎖的方法:圖中圓圈代表進(jìn)程，方塊代表資源。資源分給進(jìn)程，用從資源 (方塊)到進(jìn)程 (圓圈)的有向弧表示；進(jìn)程請求資源，用從進(jìn)程到資源的有向弧表示。2.8.2 解決死鎖的方法系統(tǒng)資源分配圖用有向圖研究解決死鎖的方法:2.8.2 解決死鎖的方法TDUC圖2.10 資源分配圖

42、(a) 分配了一個資源(b) 進(jìn)程B 請求一個資源(c)進(jìn)程D和進(jìn)程C已處于死鎖狀態(tài)RSABTDUC圖2.10 資源分配圖(a) 分配了一個資源(b)鴕鳥算法。忽略死鎖。檢測和恢復(fù)死鎖。允許死鎖發(fā)生，通過設(shè)置檢測機(jī)構(gòu)，及時檢測出死鎖的發(fā)生，然后采取適當(dāng)措施清除死鎖。避免死鎖。是在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。預(yù)防死鎖。通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來防止發(fā)生死鎖。解決死鎖的方法鴕鳥算法。忽略死鎖。解決死鎖的方法1鴕鳥算法（置之不理）是解決死鎖的最簡單方法。即像鴕鳥一樣，當(dāng)遇到危險時，將頭埋進(jìn)沙子里，假裝毫無問

43、題。當(dāng)死鎖在計(jì)算機(jī)中很少出現(xiàn)時，比如說每五年或更長時間才出現(xiàn)一次時，人們就不必花費(fèi)更多的精力去解決它，而是采用類似鴕鳥一樣的辦法忽略它。1鴕鳥算法（置之不理）例 UNIX系統(tǒng)，它潛在地存在死鎖，但它并不花功夫去檢測和解除死鎖，而是忽略不去理它。在UNIX系統(tǒng)中系統(tǒng)允許創(chuàng)建進(jìn)程總數(shù)是由進(jìn)程表中PCB的個數(shù)決定的，因此PCB塊的資源是有限的，就潛在死鎖。如PCB總數(shù)為100個已有10個進(jìn)程，每個進(jìn)程創(chuàng)建10個子進(jìn)程，（且每個進(jìn)程必需創(chuàng)建11個子進(jìn)程才能完成任務(wù)）。 : pid=fork() ; if (pid 0) printf(stderr, “fork failed”); exit (-1);

44、 if(pid = = 0)subprocess context else /parent process context : 例 UNIX系統(tǒng)，它潛在地存在死鎖，但它并不花功夫去檢測死鎖的檢測和恢復(fù)技術(shù)：是指定期啟動一個軟件檢測系統(tǒng)的狀態(tài)，若發(fā)現(xiàn)有死鎖存在，則采取措施恢復(fù)之。(1)死鎖的檢測 方法：用軟件檢查系統(tǒng)中由進(jìn)程和資源構(gòu)成的有向圖是否包含一個或多個環(huán)路，若有，則存在死鎖，否則不存在。2死鎖的檢測和恢復(fù)死鎖的檢測和恢復(fù)技術(shù)：是指定期啟動一個軟件檢測系統(tǒng)的狀態(tài)，若例 假定一個系統(tǒng)有七個進(jìn)程：AG；六個資源：RW。進(jìn)程A保持資源R，請求資源S。進(jìn)程B沒有保持資源，請求資源T。進(jìn)程C沒有保持

45、資源，請求S資源。進(jìn)程D保持資源U，請求S和T資源。進(jìn)程E保持T，請求V資源。進(jìn)程F保持W，請求S資源。進(jìn)程G保持V，請求U資源。ARSBTCSUDSTTVEWFSVGU例 假定一個系統(tǒng)有七個進(jìn)程：AG；六個資源：RW。A圖2.11 進(jìn)程資源圖RSWUTVACFDGBE環(huán)路死鎖環(huán)路：DTEVGUDD、E、G是死鎖進(jìn)程圖2.11 進(jìn)程資源圖RSWUTVACFDGBE環(huán)路環(huán)路：需要一個數(shù)據(jù)結(jié)構(gòu)L，用來記錄系統(tǒng)中各節(jié)點(diǎn)的情況。執(zhí)行過程中，標(biāo)記已檢測過的弧。類似于有向圖的遍歷。一個簡單的死鎖檢測算法需要一個數(shù)據(jù)結(jié)構(gòu)L，用來記錄系統(tǒng)中各節(jié)點(diǎn)的情況。執(zhí)行過程中，對圖中的每個節(jié)點(diǎn)N，以N為起始節(jié)點(diǎn)，并將選中

46、節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，開始執(zhí)行：將L初始化為空表，執(zhí)行以下算法。將當(dāng)前節(jié)點(diǎn)加到L的末端，檢查這個節(jié)點(diǎn)在表中是否出現(xiàn)過。如果是，這個圖包含一個環(huán)路，算法終止。如果沒有，轉(zhuǎn)。由這個節(jié)點(diǎn)再看，是否有未標(biāo)記過的引出弧。如果有，轉(zhuǎn)；若沒有，轉(zhuǎn)。任意選擇一個未標(biāo)記的引出弧并標(biāo)記它。然后，將引出弧所到節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，轉(zhuǎn)。若所有從這個節(jié)點(diǎn)引出的弧都已標(biāo)記，則返回到前一個節(jié)點(diǎn)。如果這個節(jié)點(diǎn)是最初開始的節(jié)點(diǎn)，這個圖沒有包含環(huán)路，算法終止；若不是初始節(jié)點(diǎn)，再以該節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，轉(zhuǎn)。對圖中的每個節(jié)點(diǎn)N，以N為起始節(jié)點(diǎn)，并將選中節(jié)點(diǎn)作為當(dāng)前節(jié)例從B開始。由B跟蹤引出弧一直到D，得L=B,T,E,V,G,U,D。此時

47、D有兩條引出弧，若向S方向，S是終結(jié)節(jié)點(diǎn)(沒有引出弧)。因此，由D只能向T前進(jìn)，并修改 L=B,T,E,V,G,U,D,T，由表中看出，T出現(xiàn)兩次，因此，該圖包含環(huán)路，停止算法的執(zhí)行。由于存在環(huán)路，故存在死鎖。死鎖進(jìn)程為D、E、G。RSWUTVACFDGBE環(huán)路死鎖例從B開始。由B跟蹤引出弧一直到D，得L=B,T,E,強(qiáng)制終止某個或某幾個進(jìn)程：系統(tǒng)會收回分配給進(jìn)程的所有資源。資源搶占：逐步從進(jìn)程中搶占資源給其他進(jìn)程使用，直到死鎖環(huán)被打破為止。選擇一個犧牲品：必須確定搶占順序以最小化系統(tǒng)代價?；貪L：應(yīng)對被搶占資源的進(jìn)程做些安排，回滾到某個安全狀態(tài)，以便從該狀態(tài)重啟進(jìn)程。（2）死鎖的恢復(fù)強(qiáng)制終止某

48、個或某幾個進(jìn)程：系統(tǒng)會收回分配給進(jìn)程的所有資源。（選擇“代價最小進(jìn)程”的原則目前剛剛啟動的進(jìn)程目前為止產(chǎn)生的輸出最少；預(yù)計(jì)剩余的時間最長；目前為止分配的資源總量最少；優(yōu)先級最低。 選擇“代價最小進(jìn)程”的原則基本思想： 允許進(jìn)程動態(tài)地申請資源。系統(tǒng)在進(jìn)行資源分配之前，先計(jì)算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，便將資源分配給進(jìn)程；否則，進(jìn)程等待。安全狀態(tài)：是指系統(tǒng)能按某種順序，如p1 , p2 , , pn (安全序列)，來為每個進(jìn)程分配其所需資源，直至最大需求，使每個進(jìn)程都可順序完成。 3 死鎖的避免基本思想： 允許進(jìn)程動態(tài)地申請資源。系統(tǒng)在進(jìn)行資源分配之前，(1) 進(jìn)程的資

49、源軌跡 避免死鎖的主要方法是以系統(tǒng)的安全狀態(tài)為基礎(chǔ)的。 用圖2.12所示的進(jìn)程資源軌跡圖來討論的安全狀態(tài)的概念。有兩個進(jìn)程（A和B）有兩個資源（一臺打印機(jī)和一臺繪圖儀）水平坐標(biāo)表示A進(jìn)程語句系列，綜坐標(biāo)表示進(jìn)程B指令序列。每個進(jìn)程都需要兩個資源才能完成自己的任務(wù)。(1) 進(jìn)程的資源軌跡 繪圖儀打印機(jī)繪圖儀打印機(jī)B進(jìn)程A進(jìn)程圖2.12 一個單處理器系統(tǒng)的進(jìn)程資源軌跡圖禁區(qū)安全安全安全安全安全不安全死鎖點(diǎn)繪圖儀打印機(jī)繪圖儀打印機(jī)B進(jìn)程A進(jìn)程圖2.12 一個單(2) 銀行家算法(Bankers Algorithm) 最具代表性的避免死鎖的算法是Dijkstra的銀行家算法，是在1965年提出的。利用

50、了上面圖中介紹的避免進(jìn)程進(jìn)入不安全區(qū)的原理。該算法能用于銀行系統(tǒng)的現(xiàn)金貸款的發(fā)放上。(2) 銀行家算法(Bankers Algorithm) 例 銀行家算法是用來模擬一個小城鎮(zhèn)的銀行家為一批顧客貸款的問題。 有四個顧客：A，B，C，D，每個顧客提出的最大貸款數(shù)量分別為6、5、4、7(以千美元為單位)。銀行家知道不是所有顧客都馬上需要其全部貸款（22）。因此，他只保留10個單位數(shù)量(而不是全部22個單位)為這些顧客服務(wù)。 在這個模型中，顧客是并發(fā)進(jìn)程，現(xiàn)金是資源，而銀行家就是操作系統(tǒng)。 例 圖2.13 資源的三種分配狀態(tài)C 得到全部貸款后，很快將其全部貸款還清顧客擁有量最大需求A06B05C04

51、D07系統(tǒng)擁有量:10(a)初始狀態(tài)顧客擁有量最大需求A16B15C24D47當(dāng)前剩余量:2(b)安全狀態(tài)顧客擁有量最大需求A16B25C24D47當(dāng)前剩余量:1(c) 不安全狀態(tài)圖2.13 資源的三種分配狀態(tài)C 得到全部貸款后，Available：可用資源向量。一個含有m個元素的數(shù)組，每個元素代表一類資源可用的數(shù)目。 Max：最大需求矩陣。nm矩陣，Max(i,j)=k表示進(jìn)程i 需要j類資源最大數(shù)目為k。Allocation：分配矩陣。nm矩陣，Allocation(i,j) = k 表示進(jìn)程i當(dāng)前已分得j類資源數(shù)目為k。Need：剩余需求矩陣。 nm矩陣，Need(i,j)=k表示進(jìn)程i

52、 還需要j類資源k個。Request：進(jìn)程的當(dāng)前請求向量。若Requestij=k，表示進(jìn)程Pi請求j類資源k個。銀行家算法Available：可用資源向量。一個含有m個元素的數(shù)組，每 若RequestiNeedi ，則轉(zhuǎn)；否則，出錯。 若RequestiAvailable，則轉(zhuǎn)；否則，Pi等待。 系統(tǒng)試探把請求的資源分配給進(jìn)程Pi。 Available = Available Requesti Allocationi = Allocationi + Requesti Needi = Needi Requesti檢測此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分給進(jìn)程Pi；否則，試

53、探分配作廢，讓Pi等待。具體實(shí)現(xiàn)：掃描Need的每一行，選擇其中一行，若其Needi Available，讓其釋放資源（使Available Allocationi Available；），并標(biāo)記該進(jìn)程為完成。再選擇其中一行，重復(fù)執(zhí)行上述操作，直待所有進(jìn)程被標(biāo)記時，系統(tǒng)狀態(tài)才是安全的。，才實(shí)施實(shí)際分配。進(jìn)程Pi發(fā)出資源請求Requesti后，系統(tǒng)進(jìn)行安全檢查： 若RequestiNeedi ，則轉(zhuǎn)；否則，出錯。進(jìn)例 P52有一個四種資源，五個進(jìn)程的系統(tǒng)，初始時：Available=(6,3,4,2)，4類資源向量：資源1有6個、資源2有3個、。4 1 1 10 2 1 24 2 1 01 1

54、1 12 1 1 054Allocation =Max =3 0 1 10 1 0 01 1 1 01 1 0 10 0 0 0Need =1 1 0 00 1 1 23 1 0 00 0 1 02 1 1 0Available = (1 0 2 0)進(jìn)程ij 類資源系統(tǒng)剩余的可用資源例 P52有一個四種資源，五個進(jìn)程的系統(tǒng)，初始時：Ava 當(dāng)進(jìn)程P4的請求向量 (0 0 1 0) 時， Request4=(0 0 1 0) 0,S=0,和S0表示有資源，進(jìn)程可以進(jìn)如臨界區(qū)。S=0表示資源數(shù)已經(jīng)為0，進(jìn)程應(yīng)到指針指向的隊(duì)列去排隊(duì)。S0資源為負(fù)，表明已有進(jìn)程在排隊(duì)等待使用資源設(shè)信號S的初值為2。

55、若S當(dāng)前值的為-1，則表示有1個等待進(jìn)程有m個進(jìn)程共享同一臨界資源，若使用信號量機(jī)制實(shí)現(xiàn)對一臨界資源的互斥訪問，則信號量的變化范圍是。 從-(m-1) 至1習(xí)題3_6當(dāng)進(jìn)程對信號量S執(zhí)行P、V操作時，S值發(fā)生變化，當(dāng)習(xí)題3_7習(xí)題3_7習(xí)題3_7 系統(tǒng)有n+1個進(jìn)程，其中有n個發(fā)送進(jìn)程和一個接受進(jìn)程，如圖2。15所示。A1,A2,An通過一個緩沖區(qū)分別不斷的向B進(jìn)程發(fā)消息，B不斷的從緩沖區(qū)取走消息，而且必須取走發(fā)來的每一個消息。剛開始時，緩沖區(qū)為空。試用P,V操作正確實(shí)現(xiàn)進(jìn)程之間的同步。習(xí)題3_7 系統(tǒng)有n+1個進(jìn)程，其中有n個發(fā)送進(jìn)程和一個接受習(xí)題 解： 系統(tǒng)中有n+1個進(jìn)程。其中A1、A2

56、、An分別通過緩沖區(qū)向進(jìn)程B發(fā)送消息。相互之間的制約關(guān)系為：發(fā)送進(jìn)程A1、A2、An要互斥地向BUF中送消息，當(dāng)接收進(jìn)程B還未將消息接收完之前，任何一個發(fā)送不能再送。同樣，B不能重復(fù)接收同一個消息。 為此，應(yīng)設(shè)置兩個信號量s1和s2。設(shè)系統(tǒng)只有容納一個消息的緩沖區(qū)，用信號量s1表示，其初值為1，它用來制約發(fā)送進(jìn)程。信號量s2用來制約接收進(jìn)程，其初值為0。習(xí)題解： 系統(tǒng)中有n+1個進(jìn)程。其中A1、A習(xí)題管道是是指用于連接一個讀進(jìn)程和一個寫進(jìn)程以實(shí)現(xiàn)它們之間通信的共享文件。注意管程不是，簡化PV通訊的一種方法習(xí)題管道是是指用于連接一個讀進(jìn)程和一個寫進(jìn)程以實(shí)現(xiàn)它們之間通習(xí)題現(xiàn)可用PV操作描述如下：初

57、值： S1=1, S2=0進(jìn)程A1、A2、An執(zhí)行的過程為: 進(jìn)程B執(zhí)行的過程為：begin begin loop loop 準(zhǔn)備消息 P（S2） p(s1) 從緩沖區(qū)BUF取消息 將消息送入BUF v(s1) v(s2) 消耗消息end loop; End loop; end end若緩沖區(qū)容量為m個，這個問題就變?yōu)樯a(chǎn)者和消費(fèi)者問題。1習(xí)題現(xiàn)可用PV操作描述如下：初值： S1=1, S2=0習(xí)題3-7有一個容量為100的緩沖區(qū)，有多個并發(fā)進(jìn)程通過緩沖區(qū)進(jìn)行通訊。為正確的管理緩沖區(qū)，系統(tǒng)設(shè)置了兩個讀/寫指針，分別為In和OUT,IN和OUT的值如何反映緩沖區(qū)為空還是滿？設(shè)IN為寫指針，OUT

58、為讀指針buffers系統(tǒng)初始化時，使IN=OUT，說明緩沖區(qū)為空。隨著進(jìn)程的不斷向緩沖區(qū)送和取，IN和OUT進(jìn)行動態(tài)修改：IN=(IN+1)MOD 100;OUT=(OUT+1)MOD 100;IF (IN=(IN+1)MOD 100)=OUT THEN 緩沖區(qū)為滿。IF(OUT=(OUT+1)MOD 100=IN) THEN緩沖區(qū)為空。習(xí)題3-7有一個容量為100的緩沖區(qū)，有多個并發(fā)進(jìn)程通過緩沖習(xí)題3-9有一個閱覽室，共100個座位。為了很好的利用它，讀者進(jìn)入時必須先在登記表上登記，該表設(shè)有座位號和讀者姓名；讀者離開時將其登記擦除。試問：（1）.為描寫讀者的動作應(yīng)編寫幾個程序，應(yīng)設(shè)幾個進(jìn)程

59、，它們之間的關(guān)系是什么？（2）.試用P,V操作描述進(jìn)程之間的同步算法。為描述閱覽室，用一個登記表來記錄使用情況。表中共有100項(xiàng)。每當(dāng)有讀者進(jìn)入閱覽室時，為了正確地登記，各讀者應(yīng)互斥使用。為此設(shè)兩個信號量。Mutex:互斥信號量，用來制約各讀者互斥地進(jìn)行登記，其初值為1；empty同步的信號量，用來制約各讀者能同時進(jìn)入閱覽室的數(shù)量，初值為100。習(xí)題3-9有一個閱覽室，共100個座位。為了很好的利用它，讀習(xí)題下面用兩個過程描述對表格應(yīng)執(zhí)行的動作： Mutex=1; empty=100; 登記過程： 擦除過程： begin begin p(empty) p(mutex) p(mutex) 找到自

60、己的登記項(xiàng) 找到一個登記項(xiàng)登記 v(mutex) v(mutex) v(empty) end end習(xí)題下面用兩個過程描述對表格應(yīng)執(zhí)行的動作： Mutex=1;習(xí)題為了正確地描述讀者的動作，我們可以將讀者看成進(jìn)程。若干讀者希望進(jìn)入閱覽室時，調(diào)用登記過程，退出閱覽室時，調(diào)用擦除過程?？梢娨粋€程序可對應(yīng)多個讀者。可設(shè)的進(jìn)程數(shù)由讀者數(shù)決定。其動作如下：begin 調(diào)用登記過程 進(jìn)入閱覽室閱讀 準(zhǔn)備退出 調(diào)用擦除過程end習(xí)題為了正確地描述讀者的動作，我們可以將讀者看成進(jìn)程。若干讀習(xí)題3_12.有4個同類資源，3個進(jìn)程，每個進(jìn)程的最大申請為2，系統(tǒng)不會發(fā)生死鎖。 因?yàn)樽顗牡那闆r是每個進(jìn)程已經(jīng)申請到一個