1、1,第4章 進程的同步與通信、進程死鎖,主要內(nèi)容：并發(fā)執(zhí)行，臨界段，信號量，經(jīng)典進程同步問題，消息傳遞原理，死鎖。 重點：臨界段、同步、互斥的概念；信號量的概念和物理意義；消息傳遞的原理，死鎖的概念。 難點：信號量解決進程同步與互斥的方法，死鎖防止、避免。,計算機操作系統(tǒng),前趨圖：用于描述一個程序的各部分（程序段或語句）間的執(zhí)行順序關(guān)系，或者是一個大的計算各子任務(wù)間的因果關(guān)系。 1）是一個有向無循環(huán)圖； 2）圖的結(jié)點對應(yīng)程序中的一條語句、 一個程序段或一個進程； 3）結(jié)點間的有向邊：表示兩個結(jié)點之 間存在的偏序或前趨關(guān)系 “”；,1. 程序的順序執(zhí)行,計算機操作系統(tǒng),指各程序段按照某種先后次序

2、執(zhí)行，僅當前一個操作執(zhí)行完后才能執(zhí)行后繼操作。,1. 程序的順序執(zhí)行,其中I、C、P分別表示輸入、計算和打印操作,圖3-2 程序順序執(zhí)行時的前趨圖,順序執(zhí)行的特點：順序性，封閉性，可再現(xiàn)性,計算機操作系統(tǒng),概念：若干個程序（或程序段）同時在系統(tǒng)中運行，這些程序（或程序段）的執(zhí)行在時間上是重疊的，一個程序（或程序段）的執(zhí)行尚未結(jié)束，另一個程序（或程序段）的執(zhí)行已經(jīng)開始。,2. 程序的并發(fā)執(zhí)行,若順序執(zhí)行三個作業(yè)共需要9（3*3）分鐘 并行執(zhí)行三個作業(yè)只需要5（5/3*3）分鐘,計算機操作系統(tǒng),間斷性：并發(fā)程序由于共享資源或為完成同一項任務(wù)而相互合作，形成相互制約關(guān)系。,程序并發(fā)執(zhí)行的特點：,失去

3、封閉性：多個程序共享系統(tǒng)中的各種資源，資源的狀態(tài)將由多個程序改變，失去封閉性。一個程序執(zhí)行時，會受到其他程序的影響。,不可再現(xiàn)性（待續(xù)）,并發(fā)與共享的問題：并行程序訪問共享數(shù)據(jù)問題舉例:(count為共享變量初值=300),Program A: N=count N=N+100 count=N ,Program B: M=count M=M-200 count=M ,如果按以下次序占處理機運行:,N=count,N=N+100; M=count,M=M-200,count=M; count=N. 結(jié)果count=400(應(yīng)為200)*,7,并發(fā)的需要 操作系統(tǒng)應(yīng)盡量支持用戶態(tài)程序最大限度地并發(fā)執(zhí)

4、行。 程序設(shè)計要利用OS對并發(fā)運行的支持，安排事務(wù)并發(fā)執(zhí)行。 操作系統(tǒng)核心程序也要盡可能地并發(fā)運行,4.1 并發(fā)執(zhí)行實現(xiàn),S1,S2,S3,圖4.1 任務(wù)中子任務(wù)關(guān)系示意圖,8,4.1.1 并發(fā)編程方法,傳統(tǒng)的串行程序存在著并行成分： Read (a)； Read (b)； c = a + b； Write (c),Read（a）和Read（b）兩個語句可并行執(zhí)行。,9,識別程序中的并發(fā)成分有兩種方法： 程序員寫順序程序，用識別工具識別并發(fā)成分。再組織使用操作系統(tǒng)的并發(fā)機制。 由程序員識別并發(fā)成分: 用并發(fā)程序設(shè)計語言設(shè)計并發(fā)程序， 由編譯系統(tǒng)安排并發(fā)； 直接利用操作系統(tǒng)的系統(tǒng)調(diào)用。,10,并

5、發(fā)程序設(shè)計語言 - 并發(fā)語句,它是一種高級語言； 語法形式： Parbegin S1；S2； Sn； Parend；,1）并發(fā)語句示例 1 Parbegin read（a）； read（b）； Parend； c= a+b； write（c）；,11,2）并發(fā)語句示例2 Var F,G:file of T; r,s:T; reset(F); read(F,r); while not eof(F) do s=r; Parbegin write(G,s); read(F,r); Parend; write(G,r); ,優(yōu)點: 并發(fā)語句的結(jié)構(gòu)化特征非常好。 缺點： 存在著描述能力不強的缺點，即存在

6、著用Parbegin/Parend語句無法描述的并發(fā)優(yōu)先關(guān)系。 改進手段： 輔以其他手段，則并發(fā)語句可以大大增加其描述并發(fā)的能力。,12,4.1.2并發(fā)執(zhí)行的實現(xiàn),前面是對并發(fā)的高級語言描述，要真正實現(xiàn)并發(fā)執(zhí)行，需要通過OS支持的進程機制。 實現(xiàn)的兩種方法： 1) OS提供進程創(chuàng)建，結(jié)束和同步的系統(tǒng)調(diào)用； 2) 由并行語言編譯器將并發(fā)語言的語句轉(zhuǎn)化為對OS的系統(tǒng)調(diào)用。,13,與進程相關(guān)的系統(tǒng)調(diào)用,UNIX操作系統(tǒng)利用進程支持并發(fā)執(zhí)行； 它提供了如下系統(tǒng)調(diào)用： fork（）：創(chuàng)建一個新進程。 (1) 該子進程繼承了父進程的程序空間，復(fù)制了父進程的數(shù)據(jù)段和棧段。也就是說不管是父進程還是子進程，在占

7、有處理機后，都從fork（）調(diào)用的返回點開始運行; (2) 父進程fork（）調(diào)用的返回值是子進程的進程標識pid； (3) 子進程fork（）調(diào)用的返回值是0。,14,exit（status）：進程結(jié)束。該系統(tǒng)調(diào)用發(fā)出后，操作系統(tǒng)將從系統(tǒng)中刪除調(diào)用exit的進程，并將status值傳給等待它結(jié)束的父進程。 wait（ /進入?yún)^(qū) critical code; /臨界段 exit code; /退出區(qū) remainder code;/剩余區(qū) ；,22,例2： P1,P2兩進程使用同一打印機。如果不互斥使用會交叉輸出。,Entry code,exit code,使用打印機,P1,Entry cod

8、e,exit code,使用打印機,P2,23,例3: 對共享變量count的互斥訪問。,Parbegin P1: M:=count; M:=M+1; count:= M; P2: N:=count; N:=N+2; count:=N; Parend;,Entry code,exit code,Entry code,exit code,24,如何實現(xiàn)進入?yún)^(qū)、退出區(qū)代碼同步機構(gòu),同步機構(gòu)：指能實現(xiàn)進程同步的機制，該機制能把其它進程需要的信息發(fā)送出去，也能測試自己需要的信息是否到達。 同步機構(gòu)應(yīng)遵循4個準則：,1、空閑讓進；,2、忙則等待；,3、有限等待；,4、讓權(quán)等待；,實現(xiàn)方法 軟件方法 硬件

9、方法,25,4.2.2 實現(xiàn)臨界段的硬件方法,與計算機體系結(jié)構(gòu)有關(guān),1、屏蔽中斷法 中斷引起的并發(fā)會導(dǎo)致錯誤的結(jié)果,進程1的程序 disableInterrupt(); Balance=balance+amount; enableInterrupt();,進程2的程序 disableInterrupt(); Balance=balance-amount; enableInterrupt();,兩條命令：enableInterrupt，disableInterrupt,缺點： 1）可能影響到I/O行為 2）只能用于單處理機系統(tǒng),26,2、“Test_and_Set”指令 該指令功能描述為： bo

10、olean Test_and_Set（boolean Target =true； Return rv,如果機器支持Test_and_Set，可用下列方法解決：(Lock=false) do while（Test_and_Set(,27,二、“Swap”指令 該指令功能描述為： void Swap（boolean While(s0) enableIntrrupt(); disableIntrrupt(); s=s-1; enableIntrrupt(); ,V(s) disableIntrrupt(); s=s+1; enableIntrrupt(); ,32,實現(xiàn)信號量時與進程調(diào)度相結(jié)合，消除

11、忙等待現(xiàn)象。 基本思想是： 在P操作循環(huán)等待的地方加入放棄處理機，進入等待隊列動作； 在V操作時，從等待隊列中摘取進程變?yōu)榫途w態(tài)。,2. 信號量的具體實現(xiàn),33,1. 信號量定義 typedef struct int:value; 一個數(shù)型變量 struct process *L;一個PCB隊列 Semaphore Semaphore S; 2. P操作 P(S): S.Value=S.value1; if S.value0 then 保存現(xiàn)場， 將本進程掛入S.L隊列，等待重新調(diào)度。 3. V操作 V(S): S.value:=value+1 if S.value0 then 從S.L隊列

12、取一進程，掛入就緒隊列。 4. P,V操作的優(yōu)點：同步能力強 5. P,V操作的缺點：程序結(jié)構(gòu)差，易產(chǎn)生死鎖。,34,信號量的物理意義,P(s)操作： 請求分配一個S代表的資源，執(zhí)行S.value-1； 若S.value0，表示系統(tǒng)已無該類資源，申請者阻塞。此時， |S.value|表示該信號量上阻塞的進程數(shù)；,V(s)操作： 進程釋放一個S代表的資源，執(zhí)行S.value+1； 若S.value=0，表示尚有進程因等待S代表的資源而處于阻塞狀態(tài)，所以應(yīng)喚醒其中之一。,35,3. 利用信號量實現(xiàn)進程互斥,使用方法： 1）為每一個共享的臨界資源設(shè)置一個互斥信號量，其初值為1。 2）各進程在進入臨界

13、段前先對該信號量進行P操作，退出臨界段后執(zhí)行V操作，從而保證各進程互斥的進入相關(guān)臨界段。 注意：對同一信號量操作的P與V操作在進程中必須成對出現(xiàn)。,36,進程 Pi : 信號量 mutex=1,P(mutex),V(mutex),臨界段,非臨界段,do,While(1),37,例子： 有一飛機機票售票系統(tǒng)，有m個售票處，各售票處通過計算機與該系統(tǒng)的票務(wù)中心連網(wǎng)，中心數(shù)據(jù)區(qū)中用Ri代表某天某次航班的余票數(shù)。進程pi為第i個售票處為旅客服務(wù)的進程，進程功能如下： pi() 接受旅客訂票要求； Xi=Ri ; /將票務(wù)中心該次航班的余票 /取出送該進程工作單元Xi if (Xi=1) Xi= Xi-

14、1; Ri =Xi; 輸出一張機票； else 輸出機票已售完； ,38,存在的問題： 1）存在幾個旅客幾乎同時在不同的售票處要求訂購?fù)焱淮魏桨嗟目赡堋?2）幾個進程都要訪問票務(wù)中心的共享變量Ri，可能出現(xiàn)這樣的執(zhí)行順序： 第i個售票處的售票進程pi剛剛?cè)〕鯮i， 執(zhí)行Xi=Ri； 第j個售票處的售票進程pj馬上執(zhí)行Xj= Xj-1;Ri =Xj； pi再執(zhí)行Xi= Xi-1;Ri =Xi。 產(chǎn)生的錯誤：pi，pj都售出了一張機票，但票務(wù)中心記錄機票余額的變量Ri卻只減了1。,39,semaphore mutex; mutex=1; pi() 接受旅客訂票要求； P(mutex); Xi=

15、Ri ; /將票務(wù)中心該次航班的余票Ri取出送該進 /程工作單元Xi if (Xi=1) Xi= Xi-1; Ri =Xi; V(mutex); 輸出一張機票; else V(mutex); 輸出機票已售完; ,解決辦法,40,同步模型：假設(shè)有兩個協(xié)作的并發(fā)進程P1，P2，S1是P1中的一段代碼，S2是P2中的一段代碼，只有P1中的S1執(zhí)行完后P2中的S2才能開始執(zhí)行 實現(xiàn)方法：利用信號量的同步原語P可以實現(xiàn)P1向P2發(fā)送消息，用V來測試P1的消息是否到達。設(shè)synch是實現(xiàn)同步的信號量，初值為0，則兩個進程的同步可以描述為：,4. 利用信號量實現(xiàn)進程同步,Parbegin,P2: ,P1:

16、,S1;,V(synch);,P(synch);,S2;,Parend;,41,利用信號量實現(xiàn)進程同步的例子,現(xiàn)實例子：,42,設(shè)置信號量close表示車門是否關(guān)好，初值為0，表示門未關(guān)好，不允許司機啟動汽車；設(shè)置信號量stop表示汽車是否停穩(wěn)，初值為0，表示未停穩(wěn)，售票員不能開車門。,Semaphore stop=0,close=0; Driver() P(close);/車門是否關(guān)好 啟動汽車 正常開車 到站停車 V(stop); /發(fā)送開門信息 ,實現(xiàn)方法：,busman() 關(guān)車門； V(close);/發(fā)送已關(guān)門信息 售車票； P(stop);/測試是否停車 開車門； 乘客上下車；

17、,43,首先要分析清楚進程間的同步關(guān)系，即它們之間交換信息的位置以及個數(shù)，每一個同步關(guān)系用一個信號量來表示。 其次是要注意信號量的初值以及意義。 1）P操作用來測試等待的信息是否到達； 2）V操作來向其它需要同步的進程發(fā)送信息。,解決進程同步問題時關(guān)鍵：,44,一般地，定義n個信號量來描述有n條邊的前趨圖，初值都設(shè)為0。例如：右圖的前趨關(guān)系可描述如下：,5.利用信號量描述前趨關(guān)系,semaphore a=0,b=0,c=0,d=0,e=0; P1() S1; V(a); V(b); P2() P(a); S2; V(c); V(d); P3() P(b); P(c); S3; V(e); P4

18、() P(d); P(e); S4;,45,4.2.4進程同步與互斥舉例,三個經(jīng)典的進程同步問題： 1、有限緩沖區(qū)問題（生產(chǎn)者-消費者問題）； (The Producer-Consumer Problem) 2、讀者-寫者問題； (The Read/Write Problem) 3、哲學(xué)家就餐問題； (The Dining Philosophers Problem),46,1.有限緩沖區(qū)問題 有限緩沖區(qū)的生產(chǎn)者/消費者問題（生產(chǎn)者和消費者共享一個產(chǎn)品緩沖池）。,說明： 將緩沖池看做是共享數(shù)據(jù)，對緩沖區(qū)的操作必須是互斥操作。 如果n個緩沖區(qū)全滿，生產(chǎn)者進程必須等待。 如果緩沖區(qū)全空，消費者進程必

19、須等待。,47,解：設(shè)置以下信號量 mutex, 初值為1，控制互斥訪問緩沖池。 full, 初值為0，表示當前緩沖池中滿緩沖區(qū)數(shù)，用于同步。 empty, 初值為n，表示當前緩沖池中空緩沖區(qū)數(shù)，用于同步。 有限緩沖區(qū)生產(chǎn)者/消費者進程描述如下： typedef struct item; typedef struct struct item inst; Struct buffer*next; buffer;,48,P(empty); P(mutex); add nextp to buffer; V(mutex); V(full); while(1);,semaphor full, empty,

20、 mutex; struct item nextp, nextc; full:=0; empty:=n; mutex:=1; Producer: do produce an item in nextp; .,互斥,49, consume the item in nextc; while(1);,consumer: do P(full); P(mutex); remove an item from buffer to nextc 釋放緩沖區(qū) V(mutex); V(empty);,互斥,50,補充：理發(fā)師睡覺問題,理發(fā)店由等待間（N個座位）和理發(fā)間（一個理發(fā)椅）構(gòu)成。無顧客時，理發(fā)師睡覺；當顧客

21、進入理發(fā)店發(fā)現(xiàn)理發(fā)師睡覺時，則喚醒理發(fā)師。 請寫出模擬理發(fā)師和顧客的算法。,51,理發(fā)師睡覺問題算法,Semphore seatempty=N,seatfull=0,chair=1,mutex=1;,Conmuser() do P(seatempty); P(mutex); find a seat; V(mutex); V(seatfull); while(1); ,Server() do P(seatfull); P(chair); enter into room V(seatempty); cutting; V(chair); while(1); ,補充作業(yè),52,課堂作業(yè)：,假設(shè)有三個并

22、發(fā)進程P、Q、R。其中P負責(zé)從輸入設(shè)備上讀入信息并傳給Q；Q將信息加工后傳給R；R則負責(zé)將信息打印輸出。 設(shè)：P、Q共享1個緩沖區(qū)，Q、R共享另一個緩沖區(qū)； 若一個緩沖區(qū)可保存一個數(shù)據(jù)信息，請寫出P、Q、R的并發(fā)算法。,53,若存在一共享數(shù)據(jù)A，那些對它進行讀訪問者叫Reader，對它進行寫訪問者叫做Writer。 Reader/ Writer問題：保證任何一個Writer進程與其他進程互斥訪問共享數(shù)據(jù)。 第一類Reader/ Writer問題： Reader和Writer爭奪訪問共享數(shù)據(jù)A時，Reader有較高優(yōu)先權(quán)。,2. Readers/Writers問題,54,該問題可具體描述為： 1

23、. 如果當前無進程訪問數(shù)據(jù)，則Reader/ Writer欲訪問即可訪問。 2. 如果已存在一個Reader正在訪問數(shù)據(jù)，其他欲訪問Reader可馬上訪問；而欲訪問的Writer無條件等待。 3. 若某個Writer正訪問數(shù)據(jù)，則欲訪問的Reader或 Writer都必須等待。 4. 當最后一個結(jié)束訪問數(shù)據(jù)的Reader發(fā)現(xiàn)有Writer正在等待時，則將其中一個喚醒。 5. 當某個Writer結(jié)束訪問時，若只有Writer在等待，則喚醒某個Writer，若既有Writer也有Reader；則按FIFO或某它原則喚醒一個Writer或所有Reader。,55,mutex，wrt為信號量，初值為1

24、； readcount用于記錄當前有多少個Reader正在訪問數(shù)據(jù)，初始值為0。 Reader的一般結(jié)構(gòu)為： P(mutex)； readcount:=readcount+1; if readcount=1 P(wrt); V(mutex)； 讀數(shù)據(jù)A P(mutex)； readcount:= readcount-1; if readcount=0 V(wrt); V(mutex); Writer的一般結(jié)構(gòu)為： P(wrt); 寫數(shù)據(jù)A V(wrt);,56,3. 哲學(xué)家就餐問題 問題描述：,吃飯程序是：先取左邊筷子，后取右邊筷子，再吃飯，再放筷子。,57,實現(xiàn)方法：為每個筷子設(shè)一把鎖（信號

25、量，初值為1）每個哲學(xué)家是一個進程。共享數(shù)據(jù)結(jié)構(gòu)為： semaphore Chopstick5; /初始值均為1 第i個進程描述為(i=0, ,4) do P(chopsticki); 取左邊筷子 P(chopstick(i+1)mod 5)； 取右邊筷子 吃 放左邊筷子 V(chopsticki); 放右邊筷子 V(Chopstick(i+1)mod 5； 思考 while(1);,(這可能導(dǎo)致死鎖),58,用以下幾種方法來解決上面的死鎖問題： 至多只允許有四位哲學(xué)家同時去拿左邊的筷子； 僅當哲學(xué)家的左、右兩支筷子均可用時，才允許他拿起筷子進餐； 規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿

26、右邊的筷子；而偶數(shù)號哲學(xué)家則相反。,59,用第一種方法來實現(xiàn)沒有死鎖的哲學(xué)家問題： 至多只允許有四位哲學(xué)家同時去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進餐，并在用畢時能放下他用過的兩支筷子，從而使其他的哲學(xué)家能夠進餐。 在實現(xiàn)時只需增加一個限定就餐人數(shù)的信號量num，其初值設(shè)為4。任何哲學(xué)家拿筷子前先檢測num，算法如下：,60,semaphore num=4, chopstick5=1，1，1，1，1； Philosopher i() do think; P(num); P(chopsticki); P(chopstick(i+1)% 5); 吃; V(num); V (chopsticki); V (chopstick(i+1)%5); while ( 1 ); ,61,4.3 消息傳遞原理 三種基本進程通信方法： 1.共享存儲（Shared-memory）,通信方式,p1,p2,p3,p4,共享存儲區(qū),需要解決兩個問題： 1）怎樣提供共享內(nèi)存 2）共享內(nèi)存的讀寫互斥,62,2 管道通信,管道通信是一種重要的通信方式。 特點： 同步與互斥都由系統(tǒng)自動進行，對用戶是透明的。 具有傳送數(shù)據(jù)量大的優(yōu)點，但通信速度較慢。 3.消息傳遞(message-pas