第三章并發(fā)進(jìn)程

3.1并發(fā)進(jìn)程

3.2臨界區(qū)管理

3.3信號量與PV操作

3.4管程

3.5進(jìn)程通信

3.7死鎖

第3章并發(fā)進(jìn)程

3.1.1順序程序設(shè)計3.1.2并發(fā)程序設(shè)計3.1.3進(jìn)程的交互：競爭和協(xié)作3.1并發(fā)進(jìn)程

3.1.1順序程序設(shè)計程序執(zhí)行的順序性程序在處理器上執(zhí)行時嚴(yán)格有序的，即只有當(dāng)一個操作結(jié)束后，才能開始后繼操作，這稱為程序內(nèi)部的順序性如果完成一個任務(wù)需要若干個不同的程序，這些不同程序在時間上按調(diào)用次序嚴(yán)格有序執(zhí)行，這稱為程序外部的順序性傳統(tǒng)的程序設(shè)計方法是順序程序設(shè)計,即把一個程序設(shè)計成一個順序執(zhí)行的程序模塊，不同程序也是按序執(zhí)行的順序程序設(shè)計的特點執(zhí)行的順序性環(huán)境的封閉性結(jié)果的確定性過程的可再現(xiàn)性3.1.2并發(fā)程序設(shè)計1.程序并發(fā)執(zhí)行進(jìn)程的并發(fā)性:一組進(jìn)程的執(zhí)行在時間上是重疊的所謂執(zhí)行在時間上是重疊的，是指一個進(jìn)程執(zhí)行的第一條指令是在另一個進(jìn)程執(zhí)行的最后一條指令完成之前開始的例如：有兩個進(jìn)程A和B，進(jìn)程A執(zhí)行操作a1、a2、a3，進(jìn)程B執(zhí)行操作b1、b2、b3進(jìn)程A和B順序（串行）執(zhí)行的情況：在單處理器上，進(jìn)程A執(zhí)行完，進(jìn)程B才開始執(zhí)行，它們的操作次序為：a1、a2、a3、b1、b2、b3進(jìn)程A和B并發(fā)執(zhí)行的一種情況：在單處理器上，進(jìn)程A和B交替（交叉）執(zhí)行，它們交替（交叉）執(zhí)行的操作次序可能為：a1、b1、b2、a2、a3、b3進(jìn)程的并發(fā)性從宏觀上看，并發(fā)性反映一個時間段中幾個進(jìn)程都在同一處理器上處于運行還未運行結(jié)束的狀態(tài)從微觀上看，任一時刻僅有一個進(jìn)程在處理器上運行并發(fā)的實質(zhì)是一個處理器在幾個進(jìn)程之間的多路復(fù)用并發(fā)是對有限的物理資源強(qiáng)制行使多用戶共享，消除計算機(jī)部件之間的互等現(xiàn)象，以提高系統(tǒng)資源利用率在采用多道程序設(shè)計的系統(tǒng)中，利用了處理器與外圍設(shè)備、外圍設(shè)備與外圍設(shè)備之間的并行工作能力，提高了計算機(jī)的工作效率。進(jìn)程的并發(fā)性(續(xù))例如：程序P=while(I<Count){input(data[I]，process

data[I]，output

data[I])}對一批數(shù)據(jù)（Count組）進(jìn)行處理Input涉及對輸入設(shè)備的操作process涉及處理器的計算工作output涉及對輸出設(shè)備的操作程序的編制決定了程序的執(zhí)行一次僅能操作一臺物理設(shè)備，設(shè)備之間存在等待現(xiàn)象，循環(huán)迭代一次僅能處理一組數(shù)據(jù)程序P屬于串行執(zhí)行的程序進(jìn)程的并發(fā)性(續(xù))若對這個計算問題改用三個程序來實現(xiàn)：（I=J=K=1）輸入程序PI：while(I<Count){input(data[I++])，send}計算程序PC：while(J<Count){receive， process(data[J++])，send}輸出程序PO：while(K<Count){receive， output(data[K++])}send、receive為通信控制操作進(jìn)程的并發(fā)性(續(xù))輸入程序PI

計算程序PC 輸出程序POinput(data[1])input(data[2]) process(data[1])input(data[3]) process(data[2]) output(data[1])input(data[4]) process(data[3]) output(data[2])input(data[5]) process(data[4]) output(data[3]) process(data[5]) output(data[4]) output(data[5])t1t2t3t4t5t6t7進(jìn)程的并發(fā)性(續(xù))并發(fā)程序設(shè)計：使一個程序分成若干個可同時執(zhí)行的程序模塊的方法稱為并發(fā)程序設(shè)計(如果這些模塊都屬于一個進(jìn)程，在進(jìn)程內(nèi)部執(zhí)行,則稱為并發(fā)多線程程序設(shè)計;若模塊屬于不同進(jìn)程,則稱為并發(fā)多進(jìn)程程序設(shè)計)2.并發(fā)進(jìn)程的特性

并發(fā)進(jìn)程之間的關(guān)系分為兩類：無關(guān)的和交互的無關(guān)的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)，即一個并發(fā)進(jìn)程不會改變另一個并發(fā)進(jìn)程的變量值交互的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程共享某些變量，一個進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的執(zhí)行結(jié)果。交互的并發(fā)進(jìn)程之間具有制約關(guān)系，這種交互必須是有控制的，否則會出現(xiàn)不正確的結(jié)果進(jìn)程的并發(fā)性(續(xù))并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時間無關(guān)的一個充分條件，又稱為Bernstein條件Bernstein條件：設(shè)

R(pi)={a1,a2,…an}，程序pi在執(zhí)行期間引用的變量集

W(pi)={b1,b2,…bm}，程序pi在執(zhí)行期間改變的變量集若兩個程序p1、p2的引用變量集與改變變量集交集之和為空集：

R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}則并發(fā)進(jìn)程的執(zhí)行與時間無關(guān)

進(jìn)程的并發(fā)性(續(xù))并發(fā)可以是程序內(nèi)部語句之間或模塊之間的并發(fā)，也可以是程序與程序之間的并發(fā)例如，一個程序PS有如下四條語句：S1:a=x+y；S2:b=z+1;S3:c=a–b；S4:w=c+1;這四條語句的書寫次序定義了一個串行程序的執(zhí)行流程，也定義了程序的邏輯意義，程序執(zhí)行時將按S1、S2、S3、S4的次序執(zhí)行?，F(xiàn)在要將該程序PS進(jìn)行變換，得到一個并發(fā)程序PC，而且PC與PS等價分析：該問題的核心是找出哪些語句能夠同時執(zhí)行，而這些語句同時執(zhí)行時對變量的訪問和修改合乎程序PS的原有邏輯與時間有關(guān)的錯誤對于一組交互的并發(fā)進(jìn)程，若執(zhí)行的相對速度無法相互控制，則各種與時間有關(guān)的錯誤就可能出現(xiàn)與時間有關(guān)的錯誤有兩種表現(xiàn)形式：結(jié)果不唯一永遠(yuǎn)等待…a1=n//n表示剩余的票數(shù)if(a1>=1){a1=a1-1;//售出一張票

n=a1;}…… …a2=n//n表示剩余的票數(shù)if(a2>=1){a2=a2-1;//售出一張票

n=a2;}…… 因為這種錯誤和相對執(zhí)行速度有關(guān)，因此稱為與時間有關(guān)的錯誤。服務(wù)器售票員A售票員B與時間有關(guān)的錯誤-結(jié)果不唯一與時間有關(guān)的錯誤-永遠(yuǎn)等待

例：內(nèi)存管理問題：有2個并發(fā)進(jìn)程borrow和return分別負(fù)責(zé)申請和歸還主存資源，下面算法中，x表示現(xiàn)有空閑主存容量，B表示申請或歸還的主存量。并發(fā)進(jìn)程的算法及執(zhí)行描述如下：voidborrow(intB){while（B>X） {進(jìn)程進(jìn)入等待隊列等主存資源}

X=X-B;

修改主存分配表，進(jìn)程獲得主存資源;}voidreturn(intB){X=X+B;

修改主存分配表釋放等主存資源的進(jìn)程

}intX=memory;cobegin repeatborrow(B); repeatreturn(B);coend3.1.3進(jìn)程的交互：競爭和協(xié)作1.并發(fā)進(jìn)程之間的競爭關(guān)系系統(tǒng)中的多個進(jìn)程之間彼此無關(guān)，相互并不知道其它進(jìn)程的存在，相互之間并不交換信息。但是由于這些進(jìn)程共用了一套計算機(jī)系統(tǒng)資源，因而必然產(chǎn)生競爭資源的問題，一個進(jìn)程的執(zhí)行可能影響到同其競爭資源的其它進(jìn)程。操作系統(tǒng)必須協(xié)調(diào)好諸進(jìn)程對資源的爭用。一旦一個進(jìn)程要使用已分配給另一個進(jìn)程的資源，則該進(jìn)程必須等待2.并發(fā)進(jìn)程之間的協(xié)作關(guān)系某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作，由于合作的每一個進(jìn)程都是獨立地以不可預(yù)知的速度推進(jìn)，這就需要相互協(xié)作的進(jìn)程在某些協(xié)調(diào)點上協(xié)調(diào)各自的工作。當(dāng)協(xié)作進(jìn)程中的一個到達(dá)協(xié)調(diào)點后，在尚未得到其伙伴進(jìn)程發(fā)來的消息或信號之前應(yīng)阻塞自己，直到其他合作進(jìn)程發(fā)來協(xié)調(diào)信號或消息后才被喚醒并繼續(xù)執(zhí)行。這種協(xié)作進(jìn)程之間相互等待對方消息或信號的協(xié)調(diào)關(guān)系稱為進(jìn)程同步競爭（互斥）關(guān)系定義：當(dāng)多個進(jìn)程因為爭奪臨界資源而互斥執(zhí)行稱為進(jìn)程的互斥。臨界資源：也稱獨占資源，是指在一段時間內(nèi)只允許一個進(jìn)程訪問的資源。例如打印機(jī)，磁帶機(jī)，也可以是進(jìn)程共享的數(shù)據(jù)、變量等。競爭關(guān)系

資源競爭產(chǎn)生兩個問題：

一個是死鎖(Deadlock)問題，就是一組進(jìn)程如果都獲得了部分資源，還想要得到其他進(jìn)程所占用的資源，最終所有進(jìn)程都將陷入死鎖一個是饑餓(Starvation)問題，是指一個進(jìn)程由于其它進(jìn)程總是優(yōu)先于它而被無限期拖延既要解決饑餓問題，又要解決死鎖問題。協(xié)作（同步）關(guān)系data定義：進(jìn)程之間這種相互合作、協(xié)同工作的關(guān)系稱為進(jìn)程的同步。簡單說來就是：多個相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。實例有2個進(jìn)程P1、P2，其中P1是計算進(jìn)程，P2是打印進(jìn)程，每當(dāng)P1計算出一個結(jié)果以后，將計算結(jié)果送到緩沖區(qū)，以便P2進(jìn)程從中取出數(shù)據(jù)打印。假設(shè)緩沖區(qū)被劃分為0、1、2…k-1共k個單元。還設(shè)置了兩個指針：in指針用于計算進(jìn)程存放數(shù)據(jù)，指向緩沖區(qū)下一個空閑的單元；out指針用于打印進(jìn)程取數(shù)據(jù)，指向緩沖區(qū)下一個將要取走數(shù)據(jù)單元?！?0123456789k-1inout3.2.1互斥與臨界區(qū)3.2.2臨界區(qū)管理的嘗試3.2.3實現(xiàn)臨界區(qū)管理的軟件方法3.2.4實現(xiàn)臨界區(qū)管理的硬件設(shè)施

3.2臨界區(qū)管理

…a1=n//n表示剩余的票數(shù)if(a1>=1){a1=a1-1;//售出兩張票

n=a1;}…… …a2=n//n表示剩余的票數(shù)if(a2>=1){a2=a2-1;//售出一張票

n=a2;}…… 服務(wù)器售票員A售票員B臨界資源臨界區(qū)：與臨界資源操作相關(guān)的程序段。3.2.1互斥與臨界區(qū)與同一變量有關(guān)的臨界區(qū)分散在各進(jìn)程的程序段中，而各進(jìn)程的執(zhí)行速度不可預(yù)知如果能保證進(jìn)程在臨界區(qū)執(zhí)行時，不讓另一個進(jìn)程進(jìn)入臨界區(qū)，即各進(jìn)程對共享變量的訪問是互斥的，就不會造成與時間有關(guān)的錯誤臨界區(qū)的調(diào)度原則一次至多允許一個進(jìn)程進(jìn)入臨界區(qū)內(nèi)；如果已有進(jìn)程在臨界區(qū)中，試圖進(jìn)入此臨界區(qū)的其他進(jìn)程應(yīng)等待；進(jìn)入臨界區(qū)的進(jìn)程應(yīng)在有限時間內(nèi)退出，以便讓等待隊列中的一個進(jìn)程進(jìn)入臨界區(qū)調(diào)度原則可總結(jié)成三句話：互斥使用、有空讓進(jìn)；忙則等待、有限等待；擇一而入、讓權(quán)等待、算法可行。算法可行是指不能因為所選的調(diào)度策略造成進(jìn)程饑餓甚至死鎖。3.2.2臨界區(qū)管理的嘗試下面的程序是采用標(biāo)志方法實現(xiàn)互斥的一種嘗試booleaninside1=false;/*P1不在其臨界區(qū)內(nèi)*/boolean

inside2=false;/*P2不在其臨界區(qū)內(nèi)*/cobeginprocessP1{… whileinside2do{}; inside1=true;

臨界區(qū);

inside1=false;…}coendprocessP2{… whileinside1do{}; inside2=true;

臨界區(qū);

inside2=false;…}臨界區(qū)管理的嘗試(續(xù))下面是第二個嘗試：booleaninside1=false;/*P1不在其臨界區(qū)內(nèi)*/booleaninside2=false;/*P2不在其臨界區(qū)內(nèi)*/cobeginprocessP1{… inside1:=true; whileinside2do{};

臨界區(qū);

inside1:=false;…}

coend

processP2{…inside2:=true;whileinside1do{};

臨界區(qū);inside2:=false;…};改進(jìn)算法★初步設(shè)想◆進(jìn)程交替進(jìn)入臨界區(qū)。當(dāng)turn=0時，P1必須等待P0進(jìn)入臨界區(qū)執(zhí)行，退出后，才能進(jìn)入臨界區(qū)；即使此時臨界區(qū)空閑，不符合空閑讓進(jìn)◆任何進(jìn)程在臨界區(qū)內(nèi)或外失敗，其它進(jìn)程將可能因為等待使用臨界區(qū)而無法向前推進(jìn)processP0{…inside[0]=true;turn=1;while(inside[1]&&turn==1) {donothing};

{臨界區(qū);}inside[0]=false;…}booleaninside[2];intturn=0or1;inside[0]=false;inside[1]=false;cobegin

coendprocessP1{…inside[1]=true;turn=0;while(inside[0]&&turn==0)

{donothing};

{臨界區(qū);}inside[1]=false;…}3.2.3實現(xiàn)臨界區(qū)管理的軟件方法Peterson算法

實現(xiàn)臨界區(qū)管理的軟件方法(續(xù))當(dāng)一個進(jìn)程沒有意圖進(jìn)入臨界區(qū)時，另一個進(jìn)程可以立即進(jìn)入臨界區(qū)。當(dāng)兩個進(jìn)程都想進(jìn)入臨界區(qū)時，如果turn=i，則只有第i個進(jìn)程可以進(jìn)入臨界區(qū)。一次只有一個進(jìn)程可以進(jìn)入臨界區(qū)，因為在該進(jìn)程退出之前turn的值是不會改變的該算法雖然能解決互斥問題但是算法復(fù)雜難以理解忙等3.2.4實現(xiàn)臨界區(qū)管理的硬件設(shè)施

使用軟件方法實現(xiàn)進(jìn)程互斥使用臨界資源是很困難的，他們通常能實現(xiàn)兩個進(jìn)程之間的互斥，很難控制多個進(jìn)程的互斥程序設(shè)計時應(yīng)該非常注意，否則就會產(chǎn)生死鎖和不能解決互斥軟件方法始終不能解決忙等，系統(tǒng)效率不高用來實現(xiàn)互斥的硬件設(shè)施主要有：關(guān)中斷、測試并建立指令、對換指令實現(xiàn)臨界區(qū)管理的硬件設(shè)施(續(xù))1.關(guān)中斷

關(guān)中斷是實現(xiàn)互斥的最簡單方法之一進(jìn)程在測試標(biāo)志之前，首先關(guān)中斷，直到測試完并設(shè)置標(biāo)志之后才開中斷進(jìn)程在臨界區(qū)執(zhí)行期間，計算機(jī)系統(tǒng)不響應(yīng)中斷因此，不會轉(zhuǎn)向調(diào)度，也就不會引起進(jìn)程或線程切換，正在執(zhí)行標(biāo)志測試和設(shè)置的進(jìn)程或線程不會被打斷，從而保證了互斥實現(xiàn)臨界區(qū)管理的硬件設(shè)施(續(xù))關(guān)中斷方法的缺點：關(guān)中斷時間過長會影響系統(tǒng)效率，限制處理器交叉執(zhí)行程序的能力關(guān)中斷方法也不適用于多CPU系統(tǒng)，因為，在一個處理器上關(guān)中斷，并不能防止進(jìn)程在其他處理器上執(zhí)行相同臨界區(qū)代碼實現(xiàn)臨界區(qū)管理的硬件設(shè)施(續(xù))2.測試并建立指令（專用的機(jī)器指令）硬件提供的測試并建立指令的執(zhí)行過程如下：TS(x):若x=true，則x=false；returntrue；否則returnfalse；TS指令管理臨界區(qū)時，可把一個臨界區(qū)與一個布爾變量s相連，由于變量s代表了臨界資源的狀態(tài)，可把它看成一把鎖

實現(xiàn)臨界區(qū)管理的硬件設(shè)施(續(xù))用TS指令實現(xiàn)臨界區(qū)管理（互斥）的算法如下：booleans=true; //沒有進(jìn)程在臨界區(qū)內(nèi)processPi()/*i=1,2,…,n*/{ while(!TS(s))；//上鎖

臨界區(qū);

s=true；//開鎖}

實現(xiàn)臨界區(qū)管理的硬件設(shè)施(續(xù))3.對換指令

對換（Swap）指令的功能是交換兩個字的內(nèi)容，處理過程如下：

voidSwap(boolean&a,boolean&b)temp=a;a=b;b=temp;在Intel80x86中，對換指令稱為XCHG指令實現(xiàn)臨界區(qū)管理的硬件設(shè)施(續(xù))用對換指令實現(xiàn)進(jìn)程互斥的程序如下：

booleanlock;lock=false; //無進(jìn)程在臨界區(qū)processPi()/*i=1,2,…,n*/{ boolean

keyi=true;do{

Swap(keyi,lock);//上鎖 }while(keyi);臨界區(qū)；

Swap(keyi,lock);//開鎖}實現(xiàn)臨界區(qū)管理的硬件設(shè)施(續(xù))導(dǎo)致饑餓：臨界區(qū)空閑時，執(zhí)行循環(huán)檢測的若干進(jìn)程能進(jìn)入臨界區(qū)的幾率是相等的，有的進(jìn)程可能運氣很不好，很難有機(jī)會進(jìn)入臨界區(qū)，因而饑餓軟件方法和硬件方法都存在忙等問題，浪費了處理器的時間不會成為一種通用的方法3.3.1同步與同步機(jī)制3.3.2信號量與PV操作3.3.3信號量實現(xiàn)互斥3.3.4信號量解決5位哲學(xué)家吃通心面問題3.3.5信號量解決生產(chǎn)者-消費者問題3.3.6信號量解決讀者-寫者問題3.3.7信號量解決理發(fā)師問題3.3信號量及其操作

3.3.1同步與同步機(jī)制著名的生產(chǎn)者--消費者問題是計算機(jī)操作系統(tǒng)中并發(fā)進(jìn)程內(nèi)在關(guān)系的一種抽象，是典型的進(jìn)程同步問題。在操作系統(tǒng)中，生產(chǎn)者進(jìn)程可以是計算進(jìn)程、發(fā)送進(jìn)程；而消費者進(jìn)程可以是打印進(jìn)程、接收進(jìn)程等等。解決好生產(chǎn)者--消費者問題就解決好了一類并發(fā)進(jìn)程的同步問題生產(chǎn)者--消費者問題表述：有一環(huán)形緩沖池，包含k個緩沖區(qū)（0~k-1）。有兩類進(jìn)程：一組生產(chǎn)者進(jìn)程和一組消費者進(jìn)程，生產(chǎn)者進(jìn)程向空的緩沖區(qū)中放產(chǎn)品，消費者進(jìn)程從滿的緩沖區(qū)中取走產(chǎn)品生產(chǎn)者-消費者必須同步…….0123456789k-1inout…….0123456789k-1inout生產(chǎn)者不能向滿緩沖區(qū)寫數(shù)據(jù)，消費者不能從空緩沖區(qū)取數(shù)據(jù)，即生產(chǎn)者與消費者必須同步。同步與同步機(jī)制(續(xù))

生產(chǎn)者進(jìn)程和消費者進(jìn)程共享下面的變量intk;typedef

anyitemitem;itembuffer[k];//所有生產(chǎn)者進(jìn)程和消費者進(jìn)程共享bufferintin,out,counter;//所有生產(chǎn)者進(jìn)程共享變量in//所有消費者進(jìn)程共享變量out//所有生產(chǎn)者進(jìn)程和消費者進(jìn)程共享counter生產(chǎn)者進(jìn)程：processproducer(void){

while(true){produceaniteminnextp;if(counter==k)sleep(producer);buffer[in]=nextp;in=（in+1）%k；counter=counter+1;if(counter==1)wakeup(consumer);}}消費者進(jìn)程：processconsumer(void){While(true){if(counter==0)sleep(consumer);nextc=buffer[out];out=（out+1）%k；counter=counter-1;if(counter==k-1)wakeup(producer)consumetheiteminnextc;}}同步與同步機(jī)制(續(xù))出現(xiàn)錯誤結(jié)果的原因在于各個進(jìn)程訪問緩沖區(qū)的速率不同，要得到正確結(jié)果，需要調(diào)整并發(fā)進(jìn)程的速度，這需要通過在進(jìn)程間交換信號或消息來調(diào)整相互速率，達(dá)到進(jìn)程協(xié)調(diào)運行的目的。這種協(xié)調(diào)過程稱為進(jìn)程同步操作系統(tǒng)實現(xiàn)進(jìn)程同步的機(jī)制稱為同步機(jī)制，它通常由同步原語組成常用的同步機(jī)制有：信號量與PV操作管程消息傳遞3.3.2信號量與PV操作1.前面種種方法解決臨界區(qū)調(diào)度問題的缺點1)對不能進(jìn)入臨界區(qū)的進(jìn)程，采用忙等測試法，浪費CPU時間2)將測試能否進(jìn)入臨界區(qū)的責(zé)任推給各個競爭的進(jìn)程會削弱系統(tǒng)的可靠性，加重了用戶編程負(fù)擔(dān)2.信號量同步機(jī)制的提出1965年荷蘭計算機(jī)科學(xué)家E.W.Dijkstra提出了新的同步工具--信號量和P、V操作。他將交通管制中多種顏色的信號燈管理交通的方法引入操作系統(tǒng)，讓兩個或多個進(jìn)程通過特殊變量展開交互。一個進(jìn)程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應(yīng)的特殊變量值，這種特殊變量就是信號量(Semaphore)。進(jìn)程可以使用P、V兩個特殊操作來發(fā)送和接收信號信號量與PV操作（續(xù)）起信號燈作用的變量稱為信號量操作系統(tǒng)中，信號量是用來表示物理資源的實體,信號量是一種軟資源除賦初值外，信號量僅能由同步原語P、V操作對其進(jìn)行操作。P、V操作的不可分割性確保執(zhí)行時的原子性及信號量值的完整性。利用信號量和P、V操作既可以解決并發(fā)進(jìn)程的競爭問題，又可以解決并發(fā)進(jìn)程的協(xié)作問題一般信號量——結(jié)構(gòu)型信號量

typedefstructsemaphore{ intvalue;//可用資源數(shù)

structpcb*list;//阻塞隊列}voidP(semaphore&s){ s.value--;//信號量值減一 if(s.value<0)sleep(s.list);//若信號量值小于0，}阻塞當(dāng)前進(jìn)程。voidV(semaphore&s){ s.value++;//信號量值加一if(s.value≤0)wakeup(s.list);//若信號量值小于等于0，}

//喚醒s.list中一個進(jìn)程。P、V操作的應(yīng)用用P操作和V操作實現(xiàn)同步與互斥。s.value初值表示系統(tǒng)中某類資源的數(shù)目。進(jìn)程進(jìn)入臨界區(qū)之前，首先執(zhí)行P操作原語，若s.value<0,則進(jìn)程調(diào)用sleep()內(nèi)核函數(shù)，將自己阻塞，并插入到s.list隊列排隊。所以如果s.value<0，|s.value|表該信號量鏈表中已阻塞進(jìn)程的數(shù)目。當(dāng)其它進(jìn)程執(zhí)行了V操作原語，若s.value<=0，說明阻塞隊列中還有被阻塞的進(jìn)程，則調(diào)用wakeup()內(nèi)核函數(shù)，把s.list中第一進(jìn)程修改為就緒狀態(tài)，送到就緒隊列，準(zhǔn)備執(zhí)行臨界區(qū)代碼。propgrammutualexclusion;intn=...;/*進(jìn)程數(shù)*/semaphoremutex=1;/*定義信號量mutex，mutex.value初始化為1*/cobeginprocessPi()//i=1,2,…,n{P(mutex);<臨界區(qū)>;V(mutex);<其余程序>};coendvoidP(semaphore&s){ s.value--; if(s.value<0)sleep(s.list);}voidV(semaphore&s){ s.value++; if（s.value≤0)wakeup(s.list);}記錄型信號量與PV操作（續(xù)）P(s)和V(s)中的s為兩個過程的共享變量s的取值：信號量s的初值在初始化時，根據(jù)其用途進(jìn)行設(shè)置推論1：s.value>=0時，s.value值表示還可以執(zhí)行P而不會被阻塞的進(jìn)程數(shù)，每執(zhí)行一次P就意味著一次分配一個單位的資源推論2：當(dāng)s.value<0，表示沒有可用資源，請求該資源的進(jìn)程被阻塞。s.value的絕對值表示被阻塞的進(jìn)程數(shù)，執(zhí)行一次V就意味著釋放一個資源。若s.value<0表示還有被阻塞的進(jìn)程，需要喚醒一個被阻塞的進(jìn)程，使他到就緒隊列中排隊推論3：通常，P操作意味著請求一個資源，V操作意味著釋放一個資源；特定條件下P操作代表阻塞進(jìn)程的操作，V操作代表喚醒被進(jìn)程的操作。信號量的分類

信號量按其用途分為兩種：公用信號量：初值常常為1，用來實現(xiàn)進(jìn)程間的互斥。相關(guān)進(jìn)程均可對其執(zhí)行P、V操作私有信號量：初值常常為可用資源數(shù)，多用來實現(xiàn)進(jìn)程同步。擁有該信號量的一類進(jìn)程可以對其執(zhí)行P操作，而另一類進(jìn)程可以對其執(zhí)行V操作信號量按其取值分為兩種：二元信號量：僅取0和1，主要用于解決進(jìn)程互斥問題一般信號量：允許取值為非負(fù)整數(shù)，主要用于解決進(jìn)程同步問題信號量的應(yīng)用我們將分析這樣幾個經(jīng)典進(jìn)程的同步問題：（1）哲學(xué)家進(jìn)餐問題（2）讀者--寫者問題（3）生產(chǎn)者--消費者問題（4）理發(fā)師問題3.3.4哲學(xué)家進(jìn)餐問題五位哲學(xué)家圍坐一張圓桌，桌上放五根筷子，每位哲學(xué)家只能拿起與他相鄰的兩根筷子吃飯哲學(xué)家的生活方式是交替地進(jìn)行思考和進(jìn)餐哲學(xué)家筷子0011223344哲學(xué)家進(jìn)餐問題（續(xù)）1.利用結(jié)構(gòu)型信號量解決哲學(xué)家進(jìn)餐問題數(shù)據(jù)結(jié)構(gòu)：每根筷子都是一個臨界資源，都應(yīng)定義一個信號量，為五根筷子定義一個信號量數(shù)組，每個信號量的初值為1算法分析：若每個哲學(xué)家都各自拿起他左邊的一根筷子，然后再去拿他右邊的筷子時，將都拿不到右邊的筷子，大家又都不會放下手中的筷子，大家在相互等待別人釋放筷子，系統(tǒng)于是進(jìn)入死鎖狀態(tài)操作描述：第i位哲學(xué)家的活動如下：

Semaphorefork[5];for(inti=0;i<5;i++)fork[i].value=1;

cobeginProcessphilosopher_i(){

while(true){think();

P(fork[i]);

P(fork[(i+1)mod5]); eating;

V(fork[i]);

V(fork[(i+1)mod5]); }}

coend哲學(xué)家筷子0011223344哲學(xué)家進(jìn)餐問題（續(xù)）死鎖問題解決方案：1）至多允許有四位哲學(xué)家同時去拿左邊的筷子，最終保證至少有一位哲學(xué)家能夠進(jìn)餐，（至多可以有兩位哲學(xué)家能夠進(jìn)餐）2）規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；偶數(shù)號哲學(xué)家先拿他右邊的筷子，然后再去拿左邊的筷子3)每個哲學(xué)家取到手邊的兩把筷子才開始進(jìn)餐，否則一根也不要3.3.5多緩沖區(qū)生產(chǎn)者-消費者問題對于m個生產(chǎn)者和n個消費者，它們共享可存放k件產(chǎn)品的緩沖區(qū)操作要求：多個生產(chǎn)者進(jìn)程之間、多個消費者進(jìn)程之間、生產(chǎn)者進(jìn)程與消費者進(jìn)程之間均能正確同步生產(chǎn)者/消費者必須同步…….0123456789k-1inout…….0123456789k-1inout生產(chǎn)者不能向滿緩沖區(qū)寫數(shù)據(jù)，消費者不能從空緩沖區(qū)取數(shù)據(jù)，即生產(chǎn)者與消費者必須同步。生產(chǎn)者/消費者必須互斥…….0123456789k-1inout生產(chǎn)者和消費者必須互斥進(jìn)入緩沖區(qū)，即，某時刻只允許一個進(jìn)程（生產(chǎn)者或消費者）訪問緩沖區(qū)，生產(chǎn)者必須互斥消費者和其它任何生產(chǎn)者。P1將計算出來的數(shù)據(jù)放入in指針指向的6號單元，然后將in指向下個空閑單元-7號單元。P2將計算出來的數(shù)據(jù)放入in指針指向的7號單元，P2被中斷。P1將計算出來的數(shù)據(jù)放入in指針指向的7號單元，覆蓋了P2存放的數(shù)據(jù)，出錯！生產(chǎn)一條數(shù)據(jù)是否有空存儲單元是否可用存入一條數(shù)據(jù)歸還使用權(quán)數(shù)據(jù)單元加1，喚醒一個消費者等待資源，阻塞被喚醒等待使用權(quán)，阻塞被喚醒無否有是生產(chǎn)者消費者空單元加1，喚醒一個生產(chǎn)者是否有數(shù)據(jù)單元是否可用取走一條數(shù)據(jù)歸還使用權(quán)消費數(shù)據(jù)等待資源，阻塞被喚醒等待使用權(quán)，阻塞被喚醒無否有是生產(chǎn)者-消費者問題1.利用記錄型信號量解決生產(chǎn)者--消費者問題

數(shù)據(jù)結(jié)構(gòu)：1）含有k個緩沖區(qū)的公用緩沖池2）互斥信號量mutex：實現(xiàn)諸進(jìn)程對緩沖池的互斥使用，一次僅允許一個進(jìn)程讀或?qū)懝镁彌_池，初值為13）資源信號量empty：記錄空緩沖區(qū)個數(shù)，初值為k4）資源信號量full：記錄滿緩沖區(qū)個數(shù)，初值為0操作要求：多個生產(chǎn)者進(jìn)程之間、多個消費者進(jìn)程之間、生產(chǎn)者進(jìn)程與消費者進(jìn)程之間均能正確同步itemB[k];Semaphoreempty,full,mutex;empty=k;full=0;mutex=1;Intin=0;out=0;cobeginprocessproducer_i(){ while(true){produce();

P(empty);

P(mutex);appendtoB[in];in=(in+1)%k;

V(mutex);

V(full);}}processconsumer_j(){while(true){

P(full);

P(mutex);take()fromB[out];out=(out+1)%k;

V(mutex);

V(empty);consume();}}coend生產(chǎn)者-消費者問題（續(xù)）注意：1）在每個程序中用于互斥的P(mutex)和V(mutex)必須成對出現(xiàn)2）對資源信號量empty和full的操作也同樣必須成對出現(xiàn)，但它們在不同的程序中3）在每個程序中的多個P操作順序不能顛倒，否則容易引起死鎖3.3.6讀者寫者問題該問題為多個進(jìn)程訪問一個共享數(shù)據(jù)區(qū)，如數(shù)據(jù)庫、文件、內(nèi)存區(qū)、寄存器等數(shù)據(jù)問題建立了一個通用模型，其中讀進(jìn)程只能讀數(shù)據(jù)，寫進(jìn)程只能寫數(shù)據(jù)。多個Reader進(jìn)程同時讀一條數(shù)據(jù)可以的，但如果一個Writer進(jìn)程正在更新數(shù)據(jù)時，則所有其他進(jìn)程都不能訪問（讀或?qū)懀┰撚涗洝ata讀者讀者寫者寫者讀者優(yōu)先當(dāng)一個讀者正在讀數(shù)據(jù)時，另一個讀者也需要讀數(shù)據(jù)，應(yīng)該允許第二個讀者進(jìn)入，同理第三個及隨后更多的讀者都被允許進(jìn)入?，F(xiàn)在假設(shè)一個寫者到來，由于寫操作時排他的，所以它不能訪問數(shù)據(jù)，需要阻塞等待。如果一直都有新的讀者陸續(xù)到來，寫者的寫操作將被嚴(yán)重推遲。該方法稱為“讀者優(yōu)先”。即，一旦有讀者正在讀數(shù)據(jù)，允許多個讀者同時進(jìn)入讀數(shù)據(jù)，只有當(dāng)全部讀者退出，才允許寫者進(jìn)入寫數(shù)據(jù)。讀者寫者問題（續(xù)）1.利用記錄型信號量解決讀者-----寫者問題數(shù)據(jù)結(jié)構(gòu)：1）互斥信號量writeblock：用于Reader與Writer、Writer與Writer之間的互斥，初值為1；2）ReadCount：正在讀的進(jìn)程數(shù)目，初值為03）互斥信號量mutex：用于Reader與Reader互斥訪問整型量ReadCount，初值為1

semaphoremutex=1,writeblock=1; intReadCount=0;

cobegin processreader_i{

P(mutex);ifReadCount==0thenP(writeblock); ReadCount:=ReadCount+1;

V(mutex); {讀文件};

P(mutex); ReadCount:=ReadCount-1; ifReadCount==0thenV(writeblock);

V(mutex); }

coendprocesswriter_j(){

P(writeblock);{寫文件};

V(writeblock);}3.3.7信號量解決理發(fā)師問題理發(fā)店有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子。如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。當(dāng)一個顧客到來時，它必須叫醒理發(fā)師。如果理發(fā)師正在理發(fā)時又有顧客來到，則如果有空椅子可坐，他們就坐下來等待，否則就離開。記錄型信號量解決理發(fā)師問題intwaiting=0;//等候理發(fā)的顧客數(shù)

intCHAIRS=N;//為顧客準(zhǔn)備的椅子數(shù)

semaphore

customers=0,barbers=0，mutex=1;procedurebarber(){While(true)

{P(cutomers);

P(mutex);

waiting:=waiting–1;

V(barbers);

V(mutex);

cut-hair();}}procedurecustomer(){P(mutex);

if(waiting<CHAIRS){waiting:=waiting+1;

V(customers);

V(mutex);

P(barbers);

get_haircut();}elseV(mutex);}3.4.1管程和條件變量3.4.2管程的實現(xiàn)3.4.3使用管程解決進(jìn)程同步問題3.4 管程

3.4.1管程和條件變量1.為什么要引入管程信號量機(jī)制的缺點：進(jìn)程自備同步操作，P(S)和V(S)操作大量分散在各個進(jìn)程中，不易管理，易發(fā)生死鎖管程特點：管程集中封裝了同步操作，對進(jìn)程隱蔽了同步細(xì)節(jié)，簡化了同步功能的調(diào)用界面。用戶編寫并發(fā)程序如同編寫串行程序引入管程機(jī)制的目的：把分散在各進(jìn)程中的臨界區(qū)集中起來進(jìn)行管理防止進(jìn)程有意或無意的違反同步操作便于用高級語言來書寫程序，也便于程序正確性驗證管程和條件變量（續(xù)）管程基本思想：把分散在各個進(jìn)程中的臨界區(qū)集中起來管理，并把共享資源用數(shù)據(jù)結(jié)構(gòu)抽象地表示出來建立一個“秘書”程序管理到來的訪問“秘書”每次只讓一個進(jìn)程來訪，后“秘書”更名為管程對共享資源的管理可以借助數(shù)據(jù)結(jié)構(gòu)及其上所實施操作單若干進(jìn)程來進(jìn)行對共享資源的申請和釋放通過進(jìn)程在數(shù)據(jù)結(jié)構(gòu)上的操作來實現(xiàn)代表共享資源的數(shù)據(jù)結(jié)構(gòu)及并發(fā)進(jìn)程在其上執(zhí)行的一組過程構(gòu)成了管程管程和條件變量（續(xù)）2.什么是管程一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行的在該數(shù)據(jù)結(jié)構(gòu)上的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。3.管程的三個組成部分1）局部于管程的共享變量2）對數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程3）對局部于管程的數(shù)據(jù)進(jìn)行初始化的語句管程和條件變量（續(xù)）說明：管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)是私有的，只能在管程內(nèi)使用，管程內(nèi)的過程也只能使用管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)進(jìn)程通過調(diào)用管程的過程使用臨界資源。任一時刻，管程中只能有一個活躍進(jìn)程。也就是說對管程的使用是互斥的conditionc1wait(c1)…conditioncnwait(cn)urgentqueuesignal局部數(shù)據(jù)條件變量過程1過程k出口初始化代碼入口管程等待調(diào)用的進(jìn)程隊列管程等待區(qū)域…管程的結(jié)構(gòu)

3.5.1信號通信機(jī)制3.5.2管道通信機(jī)制3.5.3共享存儲區(qū)通信機(jī)制3.5.4消息通信機(jī)制

3.5進(jìn)程通信

什么是進(jìn)程通信？簡單來說就是在進(jìn)程間傳輸數(shù)據(jù)(交換信息)。進(jìn)程通信的方式根據(jù)交換信息量的多少和效率的高低，分為：低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息）進(jìn)程1進(jìn)程2P、V操作缺點：傳送信息量小，效率低，每次通信傳遞的信息量固定，若傳遞較多信息則需要進(jìn)行多次通信。編程復(fù)雜：用戶直接實現(xiàn)通信的細(xì)節(jié)，容易出錯。高級通信：提高信號通信的效率，傳遞大量數(shù)據(jù)，減輕程序編制的復(fù)雜度。進(jìn)程1進(jìn)程2data提供三種方式：1、管道通信2、共享存儲區(qū)方式3、消息傳遞方式3.5.1信號通信機(jī)制信號通信機(jī)制信號機(jī)制又稱軟中斷，是一種進(jìn)程之間進(jìn)行通信的簡單通信機(jī)制，通過發(fā)送一個指定的信號來通知進(jìn)程某個異常時間發(fā)生，并進(jìn)行適當(dāng)處理軟中斷例子：軟中斷鍵與硬中斷的差別：軟中斷運行在用戶態(tài)，往往延時較長硬中斷運行在核心態(tài)，能及時發(fā)現(xiàn)信號的發(fā)送：可以由內(nèi)核發(fā)給用戶進(jìn)程也可以由用戶進(jìn)程發(fā)送給其他的進(jìn)程。在unix系統(tǒng)中使用kill函數(shù)可以發(fā)送信號到某個進(jìn)程或某組進(jìn)程。在unix系統(tǒng)中定義了幾十種系統(tǒng)信號3.5.2管道通信機(jī)制管道：是連接讀寫進(jìn)程實現(xiàn)他們之間通信的一個特殊文件。屬于一種共享文件通信機(jī)制管道：是一個共享文件，連接讀寫進(jìn)程實現(xiàn)通信。寫進(jìn)程往管道一端寫入信息，讀進(jìn)程從管道另一端讀信息。管道可借助于文件系統(tǒng)的機(jī)制實現(xiàn)，包括（管道）文件的創(chuàng)建、打開、關(guān)閉和讀寫也稱共享文件方式，基于文件系統(tǒng)，利用一個打開的共享文件連接兩個相互通信的進(jìn)程，文件作為緩沖傳輸介質(zhì)發(fā)送進(jìn)程接收進(jìn)程以字符流方式寫入讀出，按先進(jìn)先出方式傳送數(shù)據(jù)管道通信機(jī)制

(續(xù))管道機(jī)制應(yīng)具備的三個協(xié)調(diào)功能：1)互斥。一次僅由一個進(jìn)程讀寫。（通過測試i_node節(jié)點的特征位來保證，改特征位就是一個讀寫互斥標(biāo)志）2)確定對方是否存在3)同步。睡眠和喚醒功能。（管道文件只使用了i_node節(jié)點中的直接地址項，長度一般限制在幾kb）4)進(jìn)程在關(guān)閉管道的讀出或?qū)懭霑r，應(yīng)喚醒等待寫或讀此管道的進(jìn)程3.5.3共享存儲區(qū)通信機(jī)制內(nèi)存需要交換信息的兩個進(jìn)程，通過對同一共享數(shù)據(jù)區(qū)的操作實現(xiàn)互相通信。原理進(jìn)程1進(jìn)程2申請申請datadata這種通信方式不要求數(shù)據(jù)移動，一般用于本地通信。對于遠(yuǎn)程通信來說，不宜實現(xiàn)共享存儲區(qū)的訪問。共享區(qū)3.5.4消息傳遞通信機(jī)制這里的消息是指進(jìn)程之間傳遞的大量的、具有格式的信息。消息的格式與消息傳遞的機(jī)制及消息的范圍有關(guān)。消息體消息格式消息頭消息類型目的端地址源端地址消息長度控制信息消息傳遞通信機(jī)制(續(xù))采用消息傳遞機(jī)制后，進(jìn)程間通過消息來交換信息一個正在執(zhí)行的進(jìn)程可在任何時刻向另一個正在執(zhí)行的進(jìn)程發(fā)送消息一個正在執(zhí)行的進(jìn)程也可在任何時刻向正在執(zhí)行的另一個進(jìn)程請求消息如果進(jìn)程在某一時刻的執(zhí)行依賴于另一進(jìn)程的消息或等待其他進(jìn)程對所發(fā)消息的應(yīng)答，則消息機(jī)制與進(jìn)程的阻塞和釋放相聯(lián)系消息傳遞不僅具有進(jìn)程通信的能力，還提供進(jìn)程同步的能力消息傳遞通信機(jī)制(續(xù))消息傳遞通信方式分兩類：直接通信(消息緩沖區(qū))方式間接通信(信箱)方式消息傳遞工作原理進(jìn)程A進(jìn)程B原語Send(B,m)消息原語Receive(m)消息緩沖區(qū)進(jìn)程B的消息隊列進(jìn)程C的消息隊列進(jìn)程A的消息隊列消息不阻塞發(fā)送，阻塞接收Send()和Receive()通信原語ProcedureSend(receiver,

Ma)begingetbuf(Ma，size，i)；

i.sender:=Ma.sender；

i.size:=Ma.size；

i.text:=Ms.text；

i.next:=0；

getid(PCBset,receiver,j)；

P(j.mutex)；

insert(j.Hptr,i)；

V(j.Sn)；

V(j.mutex)；

endProcedureReceive(Mb)beginj：internalname；

P(j.Sn)；

P(j.mutex)；

remove(j.Hptr，i)；

V(j.mutex)；

Mb.Sender:=i.Sender；

Mb.Size:=i.Size；

Mb.text:=i.text；

end消息傳遞中的尋址直接尋址(直接通信)方式：點到點的發(fā)送

Send(destination,message)；

Receive(source,message)；間接尋址(間接通信)方式：以信箱為媒介進(jìn)行傳遞

Send(mailbox,message)；

Receive(mailbox,message)；進(jìn)程A進(jìn)程B原語Send(…)原語Receive(…)Mailbox利用消息傳遞實現(xiàn)互斥采用“不阻塞發(fā)送，阻塞接收”方式。多個并發(fā)執(zhí)行的發(fā)送進(jìn)程和接收進(jìn)程共享一個郵箱box，它被初始化為一個無內(nèi)容的“空”消息。如果一個進(jìn)程希望進(jìn)入臨界區(qū)，首先必須申請從box郵箱中接收一條消息。若郵箱為“空”，則該進(jìn)程阻塞（接收）；若進(jìn)程收到郵箱中的一條消息，則進(jìn)入臨界區(qū)，執(zhí)行完畢以后，退出臨界區(qū)，并將該消息發(fā)送回郵箱box中。constn=…;/*進(jìn)程數(shù)*/voidPi(){ messagemsg; while(true){ receive(box,msg);/*從郵箱接收一條消息*/ <臨界區(qū)>; send(box,msg);/*將消息發(fā)回郵箱*/ <其余部分>} begin/*主程序*/ create_mailbox(box);/*創(chuàng)建郵箱*/ send(box,null);/*初始化，向郵箱發(fā)送一條空消息*/

cobegin

P(1);P(2);…P(n)

coend end利用消息傳遞解決生產(chǎn)者/消費者問題供使用了capacity條消息，類似于共享內(nèi)存緩沖區(qū)中capacity個存儲單元。首先將capacity條“空”消息發(fā)送給生產(chǎn)者。當(dāng)生產(chǎn)者向消費者傳遞一個數(shù)據(jù)項時，它取走一條“空”消息，并發(fā)送回一條填充了內(nèi)容的消息。通過這種方式進(jìn)行數(shù)據(jù)傳遞，系統(tǒng)中的總消息數(shù)保持不變，所以，消息可以存放在預(yù)知數(shù)量的內(nèi)存中。如果生產(chǎn)者產(chǎn)生數(shù)據(jù)的速度比消費者消費數(shù)據(jù)的速度快，則所有的“空”消息最終都將被填滿，于是生產(chǎn)者將因為接收不到“空”消息而阻塞，等待消費者取走帶有數(shù)據(jù)的消息，然后返回一條“空”消息。如果消費者消費數(shù)據(jù)的速度快，則消費者因為接收不到“數(shù)據(jù)”消息而阻塞，直到生產(chǎn)者生產(chǎn)并發(fā)送一條“數(shù)據(jù)”消息。propgrammutualexclusion;intcapacity=...;/*消息緩沖區(qū)大小*/null=...;/*空消息*/voidproducer(){while(true){receive(mayproduce,null);pmsg:=produce;send(mayconsume,pmsg);}}

begin/*主程序*/create_mailbox(mayproduce);create_mailbox(mayconsume);fori=1tocapacitydosend(mayproduce,null);cobeginproducer;consumer;coendendvoidconsumer(){while(true){receive(mayconsume,cmsg);consume(cmsg);send(mayproduce,null);}}

3.6.1死鎖產(chǎn)生3.6.2死鎖防止3.6.3死鎖避免3.6.4死鎖的檢測和解除3.6死鎖

3.6.1死鎖的產(chǎn)生和定義例1：兩個同學(xué)同時進(jìn)入只有一張書桌和一把凳子的房間學(xué)習(xí)，假設(shè)必需擁有書桌和凳子，方可學(xué)習(xí)。如果在某個時刻，A同學(xué)申請得到書桌，而B同學(xué)申請到凳子，A和B都希望得到對方的資源，而又不肯放手已經(jīng)占有的資源，這時就發(fā)生了僵持局面。例2：在哲學(xué)家進(jìn)餐問題中，5個哲學(xué)家，每人各執(zhí)一個筷子，任何人都沒有兩個筷子進(jìn)餐。例3：在生產(chǎn)者—消費者問題中，將生產(chǎn)者或消費者進(jìn)程的兩個P操作顛倒時也會發(fā)生死鎖。死鎖的產(chǎn)生和定義(續(xù))死鎖——多個進(jìn)程運行過程中因爭奪資源而造成的一種僵局，無外力作用，它們都無法向前推進(jìn)。有關(guān)死鎖的結(jié)論：參與死鎖的進(jìn)程最少是兩個（兩個以上進(jìn)程才會出現(xiàn)死鎖）參與死鎖的進(jìn)程至少有兩個已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰產(chǎn)生死鎖的條件1.互斥：競爭的資源一次只能被一個進(jìn)程使用。2.占有且等待：當(dāng)一個進(jìn)程占有一些資源，同時又申請新的資源，如果新資源申請失敗，進(jìn)程將占有資源且阻塞等待。3.不剝奪：進(jìn)程已占有的資源不能被其它進(jìn)程強(qiáng)行剝奪。4.循環(huán)等待：在系統(tǒng)中存在一個由若干進(jìn)程形成的環(huán)形請求鏈，其中的每一個進(jìn)程均占有一些資源，同時又申請環(huán)形請求鏈中下一個進(jìn)程所占有的資源。前3個條件為必要條件，第4個條件為前3個條件可能導(dǎo)致的結(jié)果，為死鎖的充分條件，4個條件共同組成了死鎖的充分必要條件。解決死鎖的方法1.死鎖防止：破壞4個條件之一；有效，使資源利用率低。2.死鎖避免：防止進(jìn)入不安全態(tài)。3.死鎖檢測與恢復(fù)：檢測到死鎖再清除。死鎖防止是通過限制死鎖產(chǎn)生的4個充要條件之一，以預(yù)防死鎖的發(fā)生。1.互斥條件是臨界資源固有屬性，不能避免。2.禁止“占有且等待”條件:全分配，全釋放(AND）缺點：（1）延遲進(jìn)程運行 （2）資源嚴(yán)重浪費3.禁止“不剝奪”條件 增加系統(tǒng)開銷，且進(jìn)程前段工作可能失效。3.6.2死鎖防止4.禁止“環(huán)路等待”條件有序資源分配法：為資源編號，申請時需按編號進(jìn)行。缺點：（1）新增新設(shè)備類型不便，（原序號已排定）（2）資源與進(jìn)程使用順序不同造成浪費（3）增加了程序設(shè)計難度例：系統(tǒng)中有四類資源編號為：1.輸入機(jī)4.打印機(jī) 7.磁帶機(jī) 9.磁盤機(jī)現(xiàn)有兩個進(jìn)程P1、P2都要使用打印機(jī)和磁盤機(jī)，P1先使用打印機(jī)后使用磁盤機(jī)，P2先使用磁盤機(jī)后使用打印機(jī)。如果P2先提出資源請求，則P2只能先申請打印機(jī)（編號?。缓笊暾埓疟P機(jī)（編號大）。P2在使用磁盤機(jī)的時候，打印機(jī)空閑著不能被P1申請使用3.6.3死鎖的避免避免死鎖的方法通過資源分配之前預(yù)測是否會導(dǎo)致死鎖，決定是否進(jìn)行此次資源分配。系統(tǒng)的兩種狀態(tài)：安全狀態(tài)和不安全狀態(tài)

按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源而順序完成的序列為安全序列。能找到安全序列的狀態(tài)為安全狀態(tài)。若系統(tǒng)找不到這個安全序列則處于不安全狀態(tài)。安全狀態(tài)實例系統(tǒng)有三個進(jìn)程P1、P2和P3，共有14臺打印機(jī)；進(jìn)程P1、P2和P3要求12臺、4臺和9臺打印機(jī)。假設(shè)T0時刻，進(jìn)程P1、P2和P3已經(jīng)獲得5臺、2臺和4臺打印機(jī)。進(jìn)程最大需求已分配還需要可用P112573P2422P3945安全序列：P2P3P1安全狀態(tài)向不安全狀態(tài)上例中，若P1再申請一臺，則變?yōu)椴话踩珷顟B(tài)。進(jìn)程最大需求已分配還需要可用P112662P2422P3945利用銀行家算法避免死鎖1．?dāng)?shù)據(jù)結(jié)構(gòu)Resource[j]=k:系統(tǒng)Rj類資源一共有k個；Available[j]=k:系統(tǒng)現(xiàn)有Rj類資源k個；Claim[i,j]=k:進(jìn)程i需要Rj的最大數(shù)k個；Alloction[i,j]=k:進(jìn)程i已得到Rj類資源k個；Need[i,j]=k: 進(jìn)程i需要Rj類資源k個有：Need[i,j]=Claim[i,j]－Alloction[i,j]設(shè)Requesti是進(jìn)程i請求資源數(shù)worki：進(jìn)程i執(zhí)行完后系統(tǒng)應(yīng)有資源數(shù)（也即可用數(shù)）Finish[i]：布爾量，表進(jìn)程i能否順序完成。銀行家算法Requesti≤Needi出錯Requesti≤Availablei阻塞Available=Available-RequestiAlloctioni=Alloctioni+RequestiNeedi=Needi-RequestiFinish[j]=.F.Needj<=WorkWork=Work+AlloctionjFinish[j]=.T.否否是是舉例

ClaimR1R2R3AllocationR1R2R3

NeedR1R2R3

AvailableR1R2R3P1322100

P2613612P3314211P4422002假定系統(tǒng)中有四個進(jìn)程P1，P2，P3，P4和三類資源R1，R2，R3，每一種資源的數(shù)量分別為9、3、6，T0時刻的資源分配情況如下表。22

2001103420011T0時刻的安全序列<P2,P1,P4,P