進程間的制約關系

1、進程間的制約關系第1頁，共64頁，2022年，5月20日，19點10分，星期三 在多道程序的環(huán)境中，系統(tǒng)中的多個進程可以并發(fā)執(zhí)行，同時它們又要共享系統(tǒng)中的資源，這些資源有些是可共享使用的，如磁盤，有些是以獨占方式使用的，如打印機。由此將會引起一系列的矛盾，產(chǎn)生錯綜復雜的相互制約的關系。 產(chǎn)生這種錯綜復雜的相互制約關系的原因有二： 資源共享間接制約關系 進程合作直接制約關系6.1 進程間制約關系第2頁，共64頁，2022年，5月20日，19點10分，星期三進程間的同步 2. 進程間的互斥 一、進程間的同步和互斥 第3頁，共64頁，2022年，5月20日，19點10分，星期三臨界資源：某段時間僅允

2、許一個進程使用的資源稱為臨界資源。宿舍電話打印機 電話和打印機都屬于臨界資源。除此之外，還有內存變量、指針、數(shù)組等等也是臨界資源。 幾個進程若共享同一臨界資源，它們必須以互斥的方式使用這個臨界資源，即當一個進程正在使用臨界資源且尚未使用完畢時，則其他進程必須推遲對該資源的進一步操作。一、進程間的同步和互斥 第4頁，共64頁，2022年，5月20日，19點10分，星期三臨界區(qū)(critical section) 每個進程中訪問臨界資源的那段程序段稱為相對于臨界資源的臨界區(qū)。訪問臨界資源的進程互斥的進入各自的臨界區(qū)。第5頁，共64頁，2022年，5月20日，19點10分，星期三這種方法使用了一個物

3、理實體，稱為鎖，用W來表示，鎖有兩種狀態(tài)，W=0表示鎖已打開；W=1表示鎖被關閉。加鎖原語用LOCK(W)表示，其操作為：測試W，若W=1，表示資源正在使用，繼續(xù)反復測試；若W=0，置W=1(加鎖)。加鎖原語用LOCK(W)可描述為L：if W=1 then go to L else W：=1；開鎖原語用UNLOCK(W)表示，可描述為 W：=0； 二、實現(xiàn)臨界區(qū)互斥的鎖操作法 第6頁，共64頁，2022年，5月20日，19點10分，星期三兩個進程P1、P2使用如下程序實施進程的互斥： 進程P1 進程P2 LOCK(W) LOCK(W) S1 S2 UNLOCK(W) UNLOCK(W)其中S

4、1和S2分別為進程P1和P2的臨界區(qū)。 第7頁，共64頁，2022年，5月20日，19點10分，星期三三、 實現(xiàn)臨界區(qū)互斥的TS指令法 Test-and-Set指令Function TS(VAR boolean :lock)： booleanBegin TS = lock; lock = TRUE;END lock表示臨界資源的兩種狀態(tài)： lock =TRUE表示臨界資源正被占用， lock =FALSE表示臨界資源空閑； lock的初值為FALSE。第8頁，共64頁，2022年，5月20日，19點10分，星期三互斥算法（TS指令） 利用TS實現(xiàn)進程互斥：每個臨界資源設置一個公共布爾變量loc

5、k，初值為FALSE while TS(lock) do skip;lock := FALSE;critical sectionremainder section第9頁，共64頁，2022年，5月20日，19點10分，星期三1965年，荷蘭學者Dijkstra提出的信號量機制是一種卓有成效的進程同步工具，在長期廣泛的應用中，信號量機制又得到了很大的發(fā)展，它從整型信號量機制發(fā)展到記錄型信號量機制，進而發(fā)展為“信號集”機制。現(xiàn)在信號量機制已廣泛應用于OS中。6.2 信號量和P、V操作第10頁，共64頁，2022年，5月20日，19點10分，星期三信號量按聯(lián)系進程的關系分成二類：公用信號量（互斥信號

6、量）：它為一組需互斥共享臨界資源的并發(fā)進程而設置，代表共享的臨界資源，每個進程均可對它施加P、V操作，即都可申請和釋放該臨界資源，其初始值置為1。 信號量s取值意義如下： s 1 ；表示資源空閑，可供使用。 s 0 ；表示資源已被占用，無其它進程等待。 s -n ；表示資源已被占用，還有n個進程因等待資源而阻塞。私用信號量（同步信號量）：它為一組需同步協(xié)作完成任務的并發(fā)進程而設置，只有擁有該資源的進程才能對它施加P操作（即可申請資源），而由其合作進程對它施加V操作（即釋放資源）。第11頁，共64頁，2022年，5月20日，19點10分，星期三P、V操作是定義在信號量S上的兩個操作，其定義分別如

7、下： P(S)：S：=S-1若S0，則調用P(S)的進程繼續(xù)運行；若S0，則調用P(S)的進程被阻塞，并把它插入到等待信號量S的阻塞隊列中。V(S)：S：=S+1；若S0，則調用V(S)的進程繼續(xù)運行；若S0，從等待信號量S的阻塞隊列中喚醒頭一個進程，然后調用V(S)的進程繼續(xù)運行。第12頁，共64頁，2022年，5月20日，19點10分，星期三P、V操作可表示為如下兩個過程：P操作：Procedure P(Var S:Semaphore)Begin S:=S-1; /表示申請一個資源; If s0 /表示沒有空閑資源; then W(S) /調用進程進入等待隊列 ;End; 第13頁，共64

8、頁，2022年，5月20日，19點10分，星期三V操作：Procedure V(Var s:semaphore)Begin S:=S+1; /表示釋放一個資源； If S0 /表示有進程處于阻塞狀態(tài)； then R(S)/從等待隊列s中取出一個進程是其進入就緒 隊列;End;其中W(S)表示將調用該過程的進程置成等待信號量S的阻塞狀態(tài)，并插入相應的阻塞隊列中。R(S)表示要喚醒等待信號S阻塞隊列中的頭一個進程。第14頁，共64頁，2022年，5月20日，19點10分，星期三為臨界資源設置一個互斥信號量mutex(MUTual Exclusion)，其初值為1；在每個進程中將臨界區(qū)代碼置于P(m

9、utex)和V(mutex)原語之間必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；P、V原語不能次序錯誤、重復或遺漏利用信號量實現(xiàn)互斥第15頁，共64頁，2022年，5月20日，19點10分，星期三為使多個進程能互斥地訪問某臨界資源，只需為該資源設置一個互斥信號量mutex,并設其初值為1，然后將各進程的臨界區(qū)CS置于P（mutex）和V(mutex)操作之間即可。 利用信號量實現(xiàn)共享打印機的A、B兩進程互斥的類并行PASCAL程序描述如下：利用信號量實現(xiàn)進程互斥第16頁，共64頁，2022年，5月20日，19點10分，星

10、期三var mutex.value =1 :semaphore；beginparbeginA:begin B:begin Input data 1 from I/0 1 ； Input data 2 from I/O 2 ； Compute； Compute； P(mutex) ； P(mutex) ； Print results1 by printer; Print results2 by printer; V(mutex) ； V(mutex) ； end endparendend第17頁，共64頁，2022年，5月20日，19點10分，星期三 mutex:互斥信號量（mutual exc

11、lusion），最多只允許一個進程進入臨界區(qū),相當于一把鎖！初值=1，在n個進程間實現(xiàn)互斥,則只有一個進程能用P操作把mutex.vaule減為0，而執(zhí)行其臨界區(qū)！第二個進程對mutex執(zhí)行P操作時，mutex .vaule =-1, 進程被阻塞。如此繼續(xù).某進程對mutex執(zhí)行V操作，mutex .vaule加1，當mutex .vaule =0時喚醒等在mutex上的一個進程使之進入就緒狀態(tài)繼而進入臨界區(qū)！信號量mutex .vaule的取值范圍：1.-(n-1)最多n-1個進程等待進入臨界區(qū)第18頁，共64頁，2022年，5月20日，19點10分，星期三利用信號量實現(xiàn)進程同步利用信號量能

12、解決進程間的同步問題，這里以下圖所示的計算進程C和打印進程P通過單緩沖區(qū)Buffer傳送數(shù)據(jù)的同步問題為例說明。BufferCP第19頁，共64頁，2022年，5月20日，19點10分，星期三C和P兩進程基本算法如下：C：begin P: begin repeat repeat Compute next number ; take from Buffer ; add to Buffer ; print last number ; until false until false end endC和P兩進程并發(fā)執(zhí)行，必須在執(zhí)行序列上遵循以下規(guī)則，才能避免錯誤。 只有當C進程把數(shù)據(jù)送入Buffer后

13、，P進程才能從Buffer中取出數(shù)據(jù)來打印，否則P進程只能等待。 只有當P進程從Buffer中取走數(shù)據(jù)后，C進程才能將新計算的數(shù)據(jù)再存入Buffer,否則C進程也只能等待。第20頁，共64頁，2022年，5月20日，19點10分，星期三經(jīng)典的同步/互斥問題 1生產(chǎn)者與消費者問題 2讀者與寫者問題 第21頁，共64頁，2022年，5月20日，19點10分，星期三1生產(chǎn)者與消費者問題 Dijkstra把廣義同步問題抽象成一種“生產(chǎn)者與消費者問題”（Producer-consumer-relationship）的抽象模型。事實上，計算機系統(tǒng)中的許多問題都可歸結為生產(chǎn)者與消費者問題，生產(chǎn)者與消費者可以

14、通過一個環(huán)形緩沖池（見圖3.8）聯(lián)系起來，環(huán)形緩沖池由幾個大小相等的緩沖塊組成，每個緩沖塊容納一個產(chǎn)品。每個生產(chǎn)者可不斷地每次往緩沖池中送一個生產(chǎn)產(chǎn)品，而每個消費者則可不斷地每次從緩沖池中取出一個產(chǎn)品。 下一頁第22頁，共64頁，2022年，5月20日，19點10分，星期三環(huán)形緩沖池第23頁，共64頁，2022年，5月20日，19點10分，星期三問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，生產(chǎn)者進程不斷寫入，而消費者進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。共享緩沖區(qū)生產(chǎn)指針消費指針Producer 1Producer 2.Producer MC

15、onsumer 1Consumer 2.Consumer N滿空指針移動方向第24頁，共64頁，2022年，5月20日，19點10分，星期三下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費者關系的形式描述，設：（1）公用信號量mutex：初值為1，用于實現(xiàn)臨界區(qū)互斥。（2）生產(chǎn)者私用信號量empty：初值為n，指示空緩沖塊數(shù)目。（3）消費者私用信號量full：初值為0，指示滿緩沖塊數(shù)目。（4）整型量i和j初值均為0，i指示首空緩沖塊序號，j指示首滿緩沖塊序號。第25頁，共64頁，2022年，5月20日，19點10分，星期三采用信號量機制：full是滿數(shù)目，初值為0，empty是空數(shù)目，初值為N。實際上，f

16、ull和empty是同一個含義：full + empty = Nmutex用于訪問緩沖區(qū)時的互斥，初值是1 每個進程中各個P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥否則可能死鎖(為什么？)第26頁，共64頁，2022年，5月20日，19點10分，星期三 Var mutex，empty，full：semaphore; i,j:integer；buffer：array 0n一1 of item； Procedure producer; 生產(chǎn)者進程 begin while true do begin produce a product; P(empty); P(mutex); Buffer

17、 (i)：Product; i：(i+1) mod n； V(mutex); V(full) end end;第27頁，共64頁，2022年，5月20日，19點10分，星期三procedure consumer; 消費者進程begin While true do begin P(full)； P(mutex) goods：buffer(j); j：(j+1) mod n; V(mutex); V(empty); Consume a product; end end;第28頁，共64頁，2022年，5月20日，19點10分，星期三begin seminitial ; i:j:0; cobegin

18、 producer； consumer； coend end第29頁，共64頁，2022年，5月20日，19點10分，星期三 P(empty); P(mutex); Buffer (i)：Product; i：(i+1) mod n； V(mutex); V(full)P(full)； P(mutex)goods：buffer(j); j：(j+1) mod n; V(mutex); V(empty);第30頁，共64頁，2022年，5月20日，19點10分，星期三2讀者與寫者問題 設某航空公司有2個售票處，它們通過遠程終端訪問設在公司總部的航空訂票系統(tǒng)，并要查詢或修改系統(tǒng)中記錄所有班機當前訂

19、票數(shù)的數(shù)據(jù)庫B。設Bi為某班機的當前訂票數(shù)，P1和P2分別代表2個售票處的售票進程，R1和R2為進程執(zhí)行時使用的工作寄存器。由于售票進程并發(fā)執(zhí)行，且各自訪問數(shù)據(jù)庫B的時間是隨機的，故有可能出現(xiàn)下面的訪問序列（假定Bi的當前值為x）：第31頁，共64頁，2022年，5月20日，19點10分，星期三P1: R1:=Bi; R1:=R1+1P2: R2=Bi; R2:=R2+1;P1: Bi:=R1;P2:Bi:=R2可見，Bi的新值是X+1，而不是X+2。這里的P1和P2均為寫者，顯然，對于寫者Bi為臨界資源，因此寫者應該互斥。第32頁，共64頁，2022年，5月20日，19點10分，星期三 一個

20、數(shù)據(jù)集（如文件）如果被幾個并行進程所共享，有些進程只要求讀數(shù)據(jù)集內容，它稱讀者，而另一些進程則要求修改數(shù)據(jù)集內容，它稱寫者，幾個讀者可以同時讀這些數(shù)據(jù)集，而不需要互斥，但一個寫者不能和其它進程（不管是寫者或讀者）同時訪問些數(shù)據(jù)集，它們之間必須互斥。 讀者和寫者,共享一組數(shù)據(jù)區(qū) 要求： 允許多個讀者同時執(zhí)行讀操作 不允許讀者、寫者同時操作 不允許多個寫者同時操作設置互斥信號量wrt 表示寫者間、讀者和寫者間互斥第33頁，共64頁，2022年，5月20日，19點10分，星期三讀者與寫者問題讀者：beginP(mutex);readcount:=readcount+1;if readcount=1

21、then P(wrt);V(mutex);讀P(mutex);readcount:=readcount-1;if readcount=0 then V(wrt);V(mutex);End寫者：beginP(wrt);寫V(wrt);End第34頁，共64頁，2022年，5月20日，19點10分，星期三var mutex, wrt: semaphore;readcount: integer;begin seminit ;readcount:=0cobeginprocedure reader;beginP(mutex);Readcount:=readcount+1;If readcount=1 t

22、hen P (wrt);V(mutex);Reading is performing;第35頁，共64頁，2022年，5月20日，19點10分，星期三P(mutex);readcount:=readcount-1if readcount=0 then V(wrt);V (mutex);End Procedure writer;Begin P(wrt);writing is performing;V(wrt);EndCoendEnd;第36頁，共64頁，2022年，5月20日，19點10分，星期三由于readcount是讀者間共享變量，屬于臨界資源，它也需互斥，為此又增設互斥信號量rmutex.

23、第37頁，共64頁，2022年，5月20日，19點10分，星期三讀者：beginP(mutex);readcount:=readcount+1;if readcount=1 then P(wrt);V(mutex);讀P(mutex);readcount:=readcount-1;if readcount=0 then V(wrt);V(mutex);End寫者：beginP(wrt);寫V(wrt);End第38頁，共64頁，2022年，5月20日，19點10分，星期三第39頁，共64頁，2022年，5月20日，19點10分，星期三6.3 死鎖問題和高級進程通信6.3.1 死鎖產(chǎn)生的原因和必

24、要條件 6.3.2 預防死鎖 6.3.3 發(fā)現(xiàn)死鎖 6.3.4 解除死鎖6.3.5 高級進程通信 第40頁，共64頁，2022年，5月20日，19點10分，星期三6.3.1 死鎖產(chǎn)生的原因和必要條件 當某個進程提出申請資源后，使得有關進程在無外力協(xié)助下，永遠分配不到必需的資源而無法繼續(xù)運行，這就產(chǎn)生了一種特殊的現(xiàn)象死鎖。在許多實時應用中，比如計算機控制運輸和監(jiān)視系統(tǒng)方面，死鎖問題也極為重要。 第41頁，共64頁，2022年，5月20日，19點10分，星期三死鎖產(chǎn)生例子1：我們先來看一個申請不同類型資源的死鎖例子，假定有兩個進程Pl和P2都要修改文件F，修改時都需要一條暫時存放信息的磁帶，而只有

25、一臺磁帶機T可用。又假定由于某種原因，在進行修改之前，P2需要一暫存磁帶（例如為了修改，要重新組織輸入數(shù)據(jù)）。設F和T都是可重用資源，它們分別表示允許更新文件和允許使用磁帶機。于是Pl和P2?？捎腥缦滦问剑旱?2頁，共64頁，2022年，5月20日，19點10分，星期三分析：從上面的申請-釋放過程可以看出，進程Pl和P2有可能“同時”分別到達rl和r2處，例如，P2首先得到T，然后Pl得到F，接著Pl到達r1，最后P2到達r2，此時，若Pl繼續(xù)運行，則占有F的進程Pl將阻塞在T上，若P2繼續(xù)運行，則占有T的進程P2將阻塞在F上，如果P2不能前進，則P1也不能繼續(xù)下去，反之亦然。我們說這兩個進程

26、處在死鎖狀態(tài)。 第43頁，共64頁，2022年，5月20日，19點10分，星期三 簡單的死鎖例子第44頁，共64頁，2022年，5月20日，19點10分，星期三死鎖產(chǎn)生例子2：現(xiàn)在我們再來看一個關于相同類型資源共享的死鎖例子，假設有一類可再使用資源R，例如主存或外存，它包含有m個頁面或扇區(qū)，由n個進程P1，P2，Pn（2mn）共享。假定每個進程按右圖順序申請和釋放頁面（或扇區(qū)）：第45頁，共64頁，2022年，5月20日，19點10分，星期三分析：這里每次申請和釋放只涉及R的一個分配單元（頁或扇區(qū)）。因此，當把所有單元全部分配完畢時，便很容易發(fā)生死鎖；占有R的單元的所有進程（前m個進程）會永遠

27、阻塞在第二次申請上，而有些進程（nm個進程）類似地會阻塞在它們的第一次申請上，在圖3.12中說明了n3，m2時這種系統(tǒng)的狀態(tài)，這類死鎖是相當普遍的。 第46頁，共64頁，2022年，5月20日，19點10分，星期三 同類資源共享時的死鎖現(xiàn)象第47頁，共64頁，2022年，5月20日，19點10分，星期三產(chǎn)生死鎖有四個必要條件： 互斥條件：一個資源一次只能被一個進程所使用，即是排它性使用。不可剝奪/搶占條件：一個資源僅能被占有它的進程所釋放，而不能被別的進程搶占。請求和保持條件：進程已經(jīng)保持了至少一個資源，但又提出了新的資源要求，而該資源又已被其它進程占有，此時請求進程阻塞，但又對已經(jīng)獲得的其它

28、資源保持不放。第48頁，共64頁，2022年，5月20日，19點10分，星期三環(huán)路等待條件：前一進程占有的資源正是后一進程所需要的資源，在發(fā)生死鎖時，必然存在一個進程-資源的環(huán)形鏈。如一系統(tǒng)狀態(tài)的資源分配圖所示，P1正在等待一個P2 占用的資源R2，P2正在等待一個P1占用的資源R1。第49頁，共64頁，2022年，5月20日，19點10分，星期三6.3.2 預防死鎖 預防死鎖的方法是破壞四個產(chǎn)生死鎖的必要條件之一。1.破壞互斥條件 互斥使用是資源本身特征所決定的。2.破壞不可剝奪/不可搶占條件 搶占式調度法主要用于處理機和存貯器資源調度，它們的狀態(tài)容易保存和恢復。但此法對外部設備和私存數(shù)據(jù)不

29、宜使用。第50頁，共64頁，2022年，5月20日，19點10分，星期三3破壞“請求與保持條件” 這種方法的基本思想是：每個進程在運行之前，必須預先提出自己所要使用的全部資源，調度程序在該進程所需要的資源末得到滿足之前，不讓它們投入運行，并且當資源一旦分配給某個進程之后，那么在該進程的整個運行期間相應資源一直被它占有，這就破壞了產(chǎn)生死鎖的請求與保持條件。第51頁，共64頁，2022年，5月20日，19點10分，星期三4破壞環(huán)路條件 這種方法的基本思想是：對系統(tǒng)提供的每一項資源，由系統(tǒng)設計者將它們按類型進行線性排隊，并賦予不同的序號。例如，設卡片輸入機為1，打印機為2，磁帶機為3，磁盤機為4，。

30、所有的進程都只能嚴格地按照編號遞增（或遞減）的次序去請求資源，亦即，只有低編號的資源要求滿足后，才能對高編號資源提出要求；釋放資源時，應按編號遞減的次序進行。由此可以看出，對資源請求采取了這種限制之后，所形成的進程資源圖不可能再產(chǎn)生環(huán)路。如圖所示 .第52頁，共64頁，2022年，5月20日，19點10分，星期三資源申請和釋放順序圖第53頁，共64頁，2022年，5月20日，19點10分，星期三5資源受控動態(tài)分配 為了避免死鎖發(fā)生，操作系統(tǒng)必須根據(jù)預先掌握的關于資源用法的信息控制資源分配，使得共同進展路徑的下一步不致于進入危險區(qū)，即只要有產(chǎn)生死鎖的可能性，就避免把一種資源分配給一個進程。 第5

31、4頁，共64頁，2022年，5月20日，19點10分，星期三6.3.3 發(fā)現(xiàn)死鎖 假定系統(tǒng)有n個進程P1，P2，Pn和Pm種類型資源Rl，R2，Rm。.建立資源分配表S和進程等待表W，分別如表3.1和表3.2所示，其中aij表示分配給進程Pi的資源Rj的數(shù)目，bij表示進程Pi請求資源Rj的數(shù)目。另外為每一個進程設置一個等待資源計數(shù)器C1，C2，Cn，它們表示引起相應進程被阻塞的資源數(shù)目，將末阻塞的進程組成一個表L（或隊列）。第55頁，共64頁，2022年，5月20日，19點10分，星期三資源分配表S 第56頁，共64頁，2022年，5月20日，19點10分，星期三進程等待表W第57頁，共64頁，2022年，5月20日，19點10分，星期三其發(fā)現(xiàn)死鎖的算法