3.1并發進程

3.2臨界區管理

3.3信號量與PV操作

3.4管程

3.5進程通信

3.7死鎖

第3章并發進程

3.1.1順序程序設計3.1.2并發程序設計3.1.3進程的交互：競爭和協作3.1并發進程

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

data[I]，output

data[I])}對一批數據（Count組）進行處理Input涉及對輸入設備的操作process涉及處理器的計算工作output涉及對輸出設備的操作程序的編制決定了程序的執行一次僅能操作一臺物理設備，設備之間存在等待現象，循環迭代一次僅能處理一組數據程序P屬于串行執行的程序進程的并發性(續)若對這個計算問題改用三個程序來實現：（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為通信控制操作進程的并發性(續)輸入程序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進程的并發性(續)并發程序設計：使一個程序分成若干個可同時執行的程序模塊的方法稱為并發程序設計(如果這些模塊都屬于一個進程，在進程內部執行,則稱為并發多線程程序設計;若模塊屬于不同進程,則稱為并發多進程程序設計)2.并發進程的特性

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

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

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

R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}則并發進程的執行與時間無關

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

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

n=a2;}…… 因為這種錯誤和相對執行速度有關，因此稱為與時間有關的錯誤。服務器售票員A售票員B與時間有關的錯誤-結果不唯一與時間有關的錯誤-永遠等待

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

X=X-B;

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

修改主存分配表釋放等主存資源的進程

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

資源競爭產生兩個問題：

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

3.2臨界區管理

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

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

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

inside2=false;/*P2不在其臨界區內*/cobeginprocessP1{… whileinside2do{}; inside1=true;

臨界區;

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

臨界區;

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

臨界區;

inside1:=false;…}

coend

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

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

{臨界區;}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};

{臨界區;}inside[1]=false;…}3.2.3實現臨界區管理的軟件方法Peterson算法

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

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

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

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

臨界區;

s=true；//開鎖}

實現臨界區管理的硬件設施(續)3.對換指令

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

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

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

keyi=true;do{

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

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

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

生產者進程和消費者進程共享下面的變量intk;typedef

anyitemitem;itembuffer[k];//所有生產者進程和消費者進程共享bufferintin,out,counter;//所有生產者進程共享變量in//所有消費者進程共享變量out//所有生產者進程和消費者進程共享counter生產者進程：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);}}消費者進程：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;}}同步與同步機制(續)出現錯誤結果的原因在于各個進程訪問緩沖區的速率不同，要得到正確結果，需要調整并發進程的速度，這需要通過在進程間交換信號或消息來調整相互速率，達到進程協調運行的目的。這種協調過程稱為進程同步操作系統實現進程同步的機制稱為同步機制，它通常由同步原語組成常用的同步機制有：信號量與PV操作管程消息傳遞3.3.2信號量與PV操作1.前面種種方法解決臨界區調度問題的缺點1)對不能進入臨界區的進程，采用忙等測試法，浪費CPU時間2)將測試能否進入臨界區的責任推給各個競爭的進程會削弱系統的可靠性，加重了用戶編程負擔2.信號量同步機制的提出1965年荷蘭計算機科學家E.W.Dijkstra提出了新的同步工具--信號量和P、V操作。他將交通管制中多種顏色的信號燈管理交通的方法引入操作系統，讓兩個或多個進程通過特殊變量展開交互。一個進程在某一特殊點上被迫停止執行直到接收到一個對應的特殊變量值，這種特殊變量就是信號量(Semaphore)。進程可以使用P、V兩個特殊操作來發送和接收信號信號量與PV操作（續）起信號燈作用的變量稱為信號量操作系統中，信號量是用來表示物理資源的實體,信號量是一種軟資源除賦初值外，信號量僅能由同步原語P、V操作對其進行操作。P、V操作的不可分割性確保執行時的原子性及信號量值的完整性。利用信號量和P、V操作既可以解決并發進程的競爭問題，又可以解決并發進程的協作問題一般信號量——結構型信號量

typedefstructsemaphore{ intvalue;//可用資源數

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

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

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

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

數據結構：1）含有k個緩沖區的公用緩沖池2）互斥信號量mutex：實現諸進程對緩沖池的互斥使用，一次僅允許一個進程讀或寫公用緩沖池，初值為13）資源信號量empty：記錄空緩沖區個數，初值為k4）資源信號量full：記錄滿緩沖區個數，初值為0操作要求：多個生產者進程之間、多個消費者進程之間、生產者進程與消費者進程之間均能正確同步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生產者-消費者問題（續）注意：1）在每個程序中用于互斥的P(mutex)和V(mutex)必須成對出現2）對資源信號量empty和full的操作也同樣必須成對出現，但它們在不同的程序中3）在每個程序中的多個P操作順序不能顛倒，否則容易引起死鎖3.3.6讀者寫者問題該問題為多個進程訪問一個共享數據區，如數據庫、文件、內存區、寄存器等數據問題建立了一個通用模型，其中讀進程只能讀數據，寫進程只能寫數據。多個Reader進程同時讀一條數據可以的，但如果一個Writer進程正在更新數據時，則所有其他進程都不能訪問（讀或寫）該記錄。data讀者讀者寫者寫者讀者優先當一個讀者正在讀數據時，另一個讀者也需要讀數據，應該允許第二個讀者進入，同理第三個及隨后更多的讀者都被允許進入。現在假設一個寫者到來，由于寫操作時排他的，所以它不能訪問數據，需要阻塞等待。如果一直都有新的讀者陸續到來，寫者的寫操作將被嚴重推遲。該方法稱為“讀者優先”。即，一旦有讀者正在讀數據，允許多個讀者同時進入讀數據，只有當全部讀者退出，才允許寫者進入寫數據。讀者寫者問題（續）1.利用記錄型信號量解決讀者-----寫者問題數據結構：1）互斥信號量writeblock：用于Reader與Writer、Writer與Writer之間的互斥，初值為1；2）ReadCount：正在讀的進程數目，初值為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信號量解決理發師問題理發店有一位理發師、一把理發椅和n把供等候理發的顧客坐的椅子。如果沒有顧客，理發師便在理發椅上睡覺。當一個顧客到來時，它必須叫醒理發師。如果理發師正在理發時又有顧客來到，則如果有空椅子可坐，他們就坐下來等待，否則就離開。記錄型信號量解決理發師問題intwaiting=0;//等候理發的顧客數

intCHAIRS=N;//為顧客準備的椅子數

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管程的實現3.4.3使用管程解決進程同步問題3.4 管程

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

3.5.1信號通信機制3.5.2管道通信機制3.5.3共享存儲區通信機制3.5.4消息通信機制

3.5進程通信

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

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

Send(destination,message)；

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

Send(mailbox,message)；

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

cobegin

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

coend end利用消息傳遞解決生產者/消費者問題供使用了capacity條消息，類似于共享內存緩沖區中capacity個存儲單元。首先將capacity條“空”消息發送給生產者。當生產者向消費者傳遞一個數據項時，它取走一條“空”消息，并發送回一條填充了內容的消息。通過這種方式進行數據傳遞，系統中的總消息數保持不變，所以，消息可以存放在預知數量的內存中。如果生產者產生數據的速度比消費者消費數據的速度快，則所有的“空”消息最終都將被填滿，于是生產者將因為接收不到“空”消息而阻塞，等待消費者取走帶有數據的消息，然后返回一條“空”消息。如果消費者消費數據的速度快，則消費者因為接收不到“數據”消息而阻塞，直到生產者生產并發送一條“數據”消息。propgrammutualexclusion;intcapacity=...;/*消息緩沖區大小*/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死鎖產生3.6.2死鎖防止3.6.3死鎖避免3.6.4死鎖的檢測和解除3.6死鎖

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

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

ClaimR1R2R3AllocationR1R2R3

NeedR1R2R3

AvailableR1R2R3P1322100

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

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