操作系統(tǒng)概論-第6章_并發(fā)管理

1、第6章 并發(fā)管理操作系統(tǒng)概論操作系統(tǒng)概論主要內(nèi)容6.1進(jìn)程的并發(fā)性進(jìn)程的并發(fā)性 6.2與時間有關(guān)的錯誤與時間有關(guān)的錯誤 6.3臨界區(qū)與臨界區(qū)與PV操作操作 6.4進(jìn)程的互斥與同步進(jìn)程的互斥與同步 6.5進(jìn)程通信進(jìn)程通信 6.6死鎖死鎖 重點：分析與時間有關(guān)的錯誤；用PV操作實現(xiàn)進(jìn)程的互斥與同步；解決死鎖問題的方法6.1 6.1 程序的順序執(zhí)行與并發(fā)執(zhí)行程序的順序執(zhí)行與并發(fā)執(zhí)行 一一. 程序的順序執(zhí)行與特征程序的順序執(zhí)行與特征 1. 什么是程序的順序執(zhí)行什么是程序的順序執(zhí)行 一個程序由若干個程序段組成，而這些程序段的執(zhí)一個程序由若干個程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式

2、就稱為程序的順行必須是順序的，這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。序執(zhí)行。 例如：例如： 2. 順序程序的特征順序程序的特征 （1）順序性：處理機的操作嚴(yán)格按照程序規(guī)定的順）順序性：處理機的操作嚴(yán)格按照程序規(guī)定的順序執(zhí)行，即只有前一操作結(jié)束后，才能啟動后一操序執(zhí)行，即只有前一操作結(jié)束后，才能啟動后一操作的執(zhí)行作的執(zhí)行 （2）封閉性：程序在封閉的環(huán)境下運行，并獨占全）封閉性：程序在封閉的環(huán)境下運行，并獨占全機，因此機內(nèi)的資源的狀態(tài)只有運行的程序操作才機，因此機內(nèi)的資源的狀態(tài)只有運行的程序操作才能改變它，其執(zhí)行結(jié)果不受外界因素的影響能改變它，其執(zhí)行結(jié)果不受外界因素的影響 （3）可再現(xiàn)性：只要程

3、序執(zhí)行時的環(huán)境和初始條件）可再現(xiàn)性：只要程序執(zhí)行時的環(huán)境和初始條件相同，程序經(jīng)多次運行后所得的結(jié)果必然相同相同，程序經(jīng)多次運行后所得的結(jié)果必然相同 二二. 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 1. 什么是程序的并發(fā)執(zhí)行什么是程序的并發(fā)執(zhí)行 若干個程序段同時在系統(tǒng)中運行，這些程序段若干個程序段同時在系統(tǒng)中運行，這些程序段的執(zhí)行在時間上是重疊的，一個程序段的執(zhí)行尚未的執(zhí)行在時間上是重疊的，一個程序段的執(zhí)行尚未結(jié)束，另一個程序段的執(zhí)行已經(jīng)開始，即使這種重結(jié)束，另一個程序段的執(zhí)行已經(jīng)開始，即使這種重疊是很小的一部分，也稱這幾個程序段是并發(fā)執(zhí)行疊是很小的一部分，也稱這幾個程序段是并發(fā)執(zhí)行的。的。PQR例：三個

4、并發(fā)執(zhí)行的程序段。例：三個并發(fā)執(zhí)行的程序段。 用下圖說明在多道批處理系統(tǒng)中，大量操作執(zhí)用下圖說明在多道批處理系統(tǒng)中，大量操作執(zhí)行的先后次序。行的先后次序。 I1 I2 I3 I4C1C3C2P1P2討論：討論：(1) 哪些程序段的執(zhí)哪些程序段的執(zhí)行必須是順序的？為行必須是順序的？為什么？什么？(2) 哪些程序段的執(zhí)哪些程序段的執(zhí)行是并行的？為什么？行是并行的？為什么？2. 2. 表示方法表示方法s0;cobegins1; s2; sn;coendsn+1;s0s1s2snSn+1程序順序執(zhí)行在順序環(huán)境下在順序環(huán)境下:先先A,后后B CPU利用率利用率= 40/80 = 50%DEV1利用率利用

5、率=18.75%DEV2利用率利用率= 31.25%程序并發(fā)執(zhí)行在并發(fā)環(huán)境下在并發(fā)環(huán)境下CPU利用率利用率=89%DEV1并發(fā)環(huán)境下利用并發(fā)環(huán)境下利用=33%DEV2并發(fā)環(huán)境下利用并發(fā)環(huán)境下利用=66%并行和并發(fā)在單在單CPU系統(tǒng)中，系統(tǒng)調(diào)度在某一時刻只能讓一系統(tǒng)中，系統(tǒng)調(diào)度在某一時刻只能讓一個線程個線程(進(jìn)程進(jìn)程)運行，雖然這種調(diào)度機制有多種形運行，雖然這種調(diào)度機制有多種形式式(大多數(shù)是時間片輪巡為主大多數(shù)是時間片輪巡為主)，但無論如何，要，但無論如何，要通過不斷切換需要運行的線程讓其運行的方式就通過不斷切換需要運行的線程讓其運行的方式就叫叫并發(fā)(concurrent)。而在多而在多CPU系

6、統(tǒng)中，可以讓兩個以上的線程系統(tǒng)中，可以讓兩個以上的線程(進(jìn)進(jìn)程程)同時運行，這種可以同時讓兩個以上線程同時同時運行，這種可以同時讓兩個以上線程同時運行的方式叫做運行的方式叫做并行(parallel)多道程序設(shè)計和并發(fā)的關(guān)系多道程序設(shè)計和并發(fā)的關(guān)系6.2 6.2 與時間有關(guān)的錯誤與時間有關(guān)的錯誤 1. 1. 什么是與時間有關(guān)的錯誤什么是與時間有關(guān)的錯誤 執(zhí)行結(jié)果與并發(fā)程序執(zhí)行的相對速度相關(guān)執(zhí)行結(jié)果與并發(fā)程序執(zhí)行的相對速度相關(guān) 2. 2. 為什么會發(fā)生與時間有關(guān)的錯誤為什么會發(fā)生與時間有關(guān)的錯誤 當(dāng)兩個或多個程序有共同的臨界資源時，由于程序當(dāng)兩個或多個程序有共同的臨界資源時，由于程序執(zhí)行的速度不同

7、，則會發(fā)生與時間有關(guān)的錯誤執(zhí)行的速度不同，則會發(fā)生與時間有關(guān)的錯誤例：例：P111例：例：P113并發(fā)程序的特征并發(fā)程序的特征 1. 失去程序的封閉性和可再現(xiàn)性失去程序的封閉性和可再現(xiàn)性 如果程序執(zhí)行的結(jié)果是一個與時間無關(guān)的函數(shù)，即具有封如果程序執(zhí)行的結(jié)果是一個與時間無關(guān)的函數(shù)，即具有封閉性。閉性。 若一個程序的執(zhí)行可改變另一個程序的變量，程序執(zhí)行的若一個程序的執(zhí)行可改變另一個程序的變量，程序執(zhí)行的結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時的相結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時的相對速度，在這種情況下就失去了程序的封閉性。對速度，在這種情況下就失去了程序的封閉性。 在并發(fā)環(huán)

8、境中，機內(nèi)資源狀態(tài)將由多個程序來改變，因此在并發(fā)環(huán)境中，機內(nèi)資源狀態(tài)將由多個程序來改變，因此使程序的運行失去了封閉性。使程序的運行失去了封閉性。 2. 2.程序與計算不再一一對應(yīng)程序與計算不再一一對應(yīng) 一個程序的一次執(zhí)行稱為一個計算一個程序的一次執(zhí)行稱為一個計算 在并發(fā)的環(huán)境下，一個程序可對應(yīng)多個計算。在并發(fā)的環(huán)境下，一個程序可對應(yīng)多個計算。 在程序順序執(zhí)行時，一個程序總是對應(yīng)一個具體在程序順序執(zhí)行時，一個程序總是對應(yīng)一個具體的計算，但在程序的并發(fā)執(zhí)行時，可能有多用戶共享的計算，但在程序的并發(fā)執(zhí)行時，可能有多用戶共享使用同一個程序，但處理（計算）的對象卻是不同的，使用同一個程序，但處理（計算）

9、的對象卻是不同的，例如，在多用戶環(huán)境下，可能同時有多個用戶調(diào)用例如，在多用戶環(huán)境下，可能同時有多個用戶調(diào)用C C語語言的編譯程序，這就是典型的一個程序?qū)?yīng)多個用戶言的編譯程序，這就是典型的一個程序?qū)?yīng)多個用戶源程序的情況。源程序的情況。 3.3.程序并發(fā)執(zhí)行的相互制約程序并發(fā)執(zhí)行的相互制約 在多道程序設(shè)計的環(huán)境下，程序是并發(fā)執(zhí)行的。在多道程序設(shè)計的環(huán)境下，程序是并發(fā)執(zhí)行的。即系統(tǒng)中有多道程序在即系統(tǒng)中有多道程序在“同時同時”執(zhí)行，這些程序之間執(zhí)行，這些程序之間要共享系統(tǒng)的資源，程序之間有合作（通信）的關(guān)系。要共享系統(tǒng)的資源，程序之間有合作（通信）的關(guān)系。合作與競爭產(chǎn)生一系列的矛盾，這些矛盾實際

10、上是一合作與競爭產(chǎn)生一系列的矛盾，這些矛盾實際上是一種相互制約，有直接的，也有間接。種相互制約，有直接的，也有間接。 （1 1）資源共享）資源共享 （間接制約關(guān)系）（間接制約關(guān)系） （2 2）進(jìn)程合作）進(jìn)程合作 （直接制約關(guān)系）（直接制約關(guān)系） 無關(guān)的并發(fā)進(jìn)程并發(fā)進(jìn)程分類：并發(fā)進(jìn)程分類：無關(guān)的，交互的無關(guān)的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個別在不同的變量集合上操作，一個進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)無關(guān)并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時間無關(guān)的一個充分條件進(jìn)程的相互制約關(guān)系進(jìn)程的相互制約關(guān)系交互的并發(fā)進(jìn)程交互的并發(fā)進(jìn)程

11、：一組并發(fā)進(jìn)程共享交互的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程共享某些變量，或者一組進(jìn)程相互合作某些變量，或者一組進(jìn)程相互合作; ;一一個進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程個進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的結(jié)果的結(jié)果與時間有關(guān)的錯誤執(zhí)行的相對速度無法相互控制執(zhí)行的相對速度無法相互控制表現(xiàn)形式：表現(xiàn)形式：結(jié)果不唯一結(jié)果不唯一 例：例：P P111,111,P P113113永遠(yuǎn)等待永遠(yuǎn)等待 例：死鎖例：死鎖進(jìn)程的交互：競爭與協(xié)作 并發(fā)進(jìn)程之間的競爭關(guān)系并發(fā)進(jìn)程之間的競爭關(guān)系共享資源共享資源 進(jìn)程的互斥進(jìn)程的互斥 并發(fā)進(jìn)程之間的協(xié)作關(guān)系并發(fā)進(jìn)程之間的協(xié)作關(guān)系進(jìn)程的相互合作進(jìn)程的相互合作進(jìn)程的同步進(jìn)程的同步進(jìn)程的交互：

12、競爭與協(xié)作第一種是競爭關(guān)系 資源競爭的兩個控制問題：一個是死鎖一個是死鎖(Deadlock)(Deadlock)問題問題 一個是饑餓一個是饑餓(Starvation) (Starvation) 問題問題既要解決饑餓問題，又要解決死鎖問題既要解決饑餓問題，又要解決死鎖問題進(jìn)程的交互：競爭與協(xié)作進(jìn)程互斥是解決進(jìn)程間競爭關(guān)系是解決進(jìn)程間競爭關(guān)系( (間接制約關(guān)系間接制約關(guān)系) )的手段的手段進(jìn)程互斥指若干進(jìn)程要使用同一共指若干進(jìn)程要使用同一共享資源時，任何時刻最多允許一個享資源時，任何時刻最多允許一個進(jìn)程使用，其他進(jìn)程必須等待，直進(jìn)程使用，其他進(jìn)程必須等待，直到占有資源的進(jìn)程釋放該資源到占有資源的進(jìn)

13、程釋放該資源進(jìn)程的交互：競爭與協(xié)作第二種是協(xié)作關(guān)系(1) 某些進(jìn)程為完成同一任務(wù)需要某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作分工協(xié)作 進(jìn)程的同步是解決進(jìn)程間協(xié)作是解決進(jìn)程間協(xié)作關(guān)系關(guān)系( (直接制約關(guān)系直接制約關(guān)系) )的手段的手段進(jìn)程的交互：競爭與協(xié)作第二種是協(xié)作關(guān)系(2) 進(jìn)程同步指兩個以上進(jìn)程基于某個指兩個以上進(jìn)程基于某個條件來協(xié)調(diào)它們的活動。一個進(jìn)程條件來協(xié)調(diào)它們的活動。一個進(jìn)程的執(zhí)行依賴于協(xié)作進(jìn)程的消息或信的執(zhí)行依賴于協(xié)作進(jìn)程的消息或信號，當(dāng)一個進(jìn)程沒有得到來自于協(xié)號，當(dāng)一個進(jìn)程沒有得到來自于協(xié)作進(jìn)程的消息或信號時需等待，直作進(jìn)程的消息或信號時需等待，直到消息或信號到達(dá)才被喚醒到消息或信號

14、到達(dá)才被喚醒 進(jìn)程的交互：競爭與協(xié)作第二種是協(xié)作關(guān)系(3)進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程進(jìn)程互斥關(guān)系是一種特殊的進(jìn)程同步關(guān)系，即同步關(guān)系，即逐次使用逐次使用互斥共享互斥共享資源，是對進(jìn)程使用資源次序上資源，是對進(jìn)程使用資源次序上的一種協(xié)調(diào)的一種協(xié)調(diào)6.3臨界區(qū)與PV操作6.3.1臨界區(qū)臨界區(qū) 6.3.2 PV操作操作 6.3 6.3 臨界區(qū)和臨界區(qū)和PVPV操作操作 引例：引例： 宿舍電話的使用宿舍電話的使用 打印機的使用打印機的使用 1. 臨界資源：一次僅允許一個進(jìn)程使用的資源稱為臨臨界資源：一次僅允許一個進(jìn)程使用的資源稱為臨界資源界資源 引例中的電話和打印機都屬于臨界資源。除此之外引例中的電

15、話和打印機都屬于臨界資源。除此之外，還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源，還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源2 2、臨界區(qū)：、臨界區(qū)：每個進(jìn)程中訪問臨界資每個進(jìn)程中訪問臨界資源的那段程序段稱為臨源的那段程序段稱為臨界區(qū)（臨界段）界區(qū)（臨界段）臨界區(qū)臨界區(qū)例：例：P111例：例：P113臨界區(qū)臨界區(qū)互斥互斥定義定義: : 在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某臨界區(qū)時，在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某臨界區(qū)時，就不允許其它進(jìn)程進(jìn)入，否則就會發(fā)生就不允許其它進(jìn)程進(jìn)入，否則就會發(fā)生( (后果后果) )無法無法估計的錯誤。我們把進(jìn)程之間的這種相互制約的關(guān)估計的錯誤。我們把進(jìn)程之間的這種相互制約

16、的關(guān)系稱為互斥系稱為互斥 進(jìn)入臨界區(qū)的準(zhǔn)則：進(jìn)入臨界區(qū)的準(zhǔn)則： (1)(1)每次至多有一個進(jìn)程處于臨界區(qū)；每次至多有一個進(jìn)程處于臨界區(qū)； (2)(2)當(dāng)有若干個進(jìn)程欲進(jìn)入臨界區(qū)時，應(yīng)在有當(dāng)有若干個進(jìn)程欲進(jìn)入臨界區(qū)時，應(yīng)在有限的時間內(nèi)使其進(jìn)入；限的時間內(nèi)使其進(jìn)入； (3)(3)進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時間進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時間信號量信號量 信號量信號量是一個確定的二元組是一個確定的二元組(s，q)，s是一個具有非負(fù)初是一個具有非負(fù)初值的整型變量，值的整型變量，q是一個初始狀態(tài)為空的隊列。操作系是一個初始狀態(tài)為空的隊列。操作系統(tǒng)利用信號燈的狀態(tài)對并發(fā)進(jìn)程和共享資源進(jìn)行控制和統(tǒng)利用信號燈的

17、狀態(tài)對并發(fā)進(jìn)程和共享資源進(jìn)行控制和管理管理 s代表資源的實體代表資源的實體，是，是整型變量整型變量 s 0 0 時，表示綠燈，進(jìn)程執(zhí)行時，表示綠燈，進(jìn)程執(zhí)行( (表示系統(tǒng)擁有的表示系統(tǒng)擁有的資源個數(shù)資源個數(shù)) s 0 0 時，表示紅燈，進(jìn)程停止執(zhí)行時，表示紅燈，進(jìn)程停止執(zhí)行( ( |s|表示等待表示等待某資源的進(jìn)程個數(shù)某資源的進(jìn)程個數(shù)) ) 注意：創(chuàng)建信號燈時，應(yīng)準(zhǔn)確說明信號燈注意：創(chuàng)建信號燈時，應(yīng)準(zhǔn)確說明信號燈 s 的意義的意義和初值和初值 (這個初值絕不能為負(fù)值這個初值絕不能為負(fù)值)用原語實現(xiàn)互斥用原語實現(xiàn)互斥記錄型信號量設(shè)s為一個記錄型數(shù)據(jù)結(jié)構(gòu),一個分量為整型量value,另一個為信號量

18、隊列queue, P和V操作原語定義： P(s)：將信號量s減去l，若結(jié)果小于0，則調(diào)用P(s)的進(jìn)程被置成等待信號量s的狀態(tài) V(s)：將信號量s加1，若結(jié)果不大于0，則釋放一個等待信號量s的進(jìn)程記錄型信號量type semaphore = record value:integer; queue: list of process;Endprocedure P(var s:semaphore);begin s := s 1; / /* * 把信號量減去把信號量減去1 1 * */ / if s 0 then W(s);/ /* * 若信號量小于若信號量小于0 0，則調(diào)用，則調(diào)用P(s)P(s)

19、的進(jìn)的進(jìn) 程被置成等待信號量程被置成等待信號量s s的狀態(tài)的狀態(tài) * */ /end;procedure V(var s:semaphore);begins := s + 1; / /* * 把信號量加把信號量加1 1 * */ /if s 0表示有S個資源可用；S=0表示無資源可用；S0則| S |表示S等待隊列中的進(jìn)程個數(shù)。P(S):表示申請一個資源; V(S)表示釋放一個資源。信號量的初值應(yīng)該大于等于0P.V操作討論P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作當(dāng)為互斥操作時，它們同處于同一進(jìn)程當(dāng)為同步操作時，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操

20、作的順序至關(guān)重要,一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前,而兩個V操作無關(guān)緊要總結(jié)：如何描述進(jìn)程同步問題？先寫出對問題的初步描述（用漢語，流程）；例如司機售票員問題中：司機（進(jìn)程）：啟動車輛；正常行駛；停車問題中存在的關(guān)系（互斥、同步，各有幾種）；互斥：涉及到對共享資源的訪問同步：涉及到進(jìn)程之間的執(zhí)行次序設(shè)置信號量（信號量的個數(shù)和初值（考慮問題的初始狀態(tài)），信號量的物理含義）； 信號量的初值：0，1，n三種情況 1：表示臨界資源； 0：表示進(jìn)程間的同步（前驅(qū)）關(guān)系 n：表示若干個資源總結(jié)：如何描述進(jìn)程同步問題？（續(xù)）把P、V操作放到合適的位置。P操作：要控制誰就放在誰的

21、前面；6.5 進(jìn)程通信P.V操作實現(xiàn)的是進(jìn)程之間的低級通訊，所操作實現(xiàn)的是進(jìn)程之間的低級通訊，所以以P.V為低級通訊原語。它只能傳遞簡單的為低級通訊原語。它只能傳遞簡單的信號，不能傳遞交換大量信息信號，不能傳遞交換大量信息如果要在進(jìn)程間傳遞大量信息則要用如果要在進(jìn)程間傳遞大量信息則要用Send / Receive原語（高級通信原語）原語（高級通信原語）目前常用的高級通信方式有信箱通信、消息緩沖通信、管道通信。6.5.1 信件發(fā)送者名發(fā)送者名-進(jìn)程名進(jìn)程名信息信息(地址和長度地址和長度)等等/不等回信不等回信回信存放地址回信存放地址6.5.2 信箱若干個進(jìn)程可向同一進(jìn)程發(fā)送信件若干個進(jìn)程可向同一

22、進(jìn)程發(fā)送信件.接受信件的進(jìn)程接受信件的進(jìn)程可以設(shè)立一個信箱可以設(shè)立一個信箱信箱的大小決定了可容納的信件數(shù)信箱的大小決定了可容納的信件數(shù)由信箱說明和信箱體兩部分組成由信箱說明和信箱體兩部分組成6.5.3 通信原語通信遵循規(guī)則通信遵循規(guī)則:發(fā)送信件時信箱已滿發(fā)送信件時信箱已滿,則將發(fā)送信件的進(jìn)程置為則將發(fā)送信件的進(jìn)程置為”等信箱等信箱”狀態(tài)狀態(tài),直到信箱有空才被釋放直到信箱有空才被釋放取信件信箱為空取信件信箱為空,則將收信件的進(jìn)程置為則將收信件的進(jìn)程置為”等信等信件件”狀態(tài)狀態(tài),直到有信件才被釋放直到有信件才被釋放通信原語send(N,M) 功能：把信件功能：把信件M送到指定的送到指定的信箱信箱N

23、中中 receive(N,X) 功能：從指定信箱功能：從指定信箱N中取中取出一封信，存放到指定的地址出一封信，存放到指定的地址X中中 6.6死鎖6.6.1死鎖的形成死鎖的形成 6.6.2死鎖的必要條件死鎖的必要條件 6.6.3死鎖的防止死鎖的防止 6.6.4死鎖的避免死鎖的避免 6.6.5死鎖的檢測死鎖的檢測 例例1： 進(jìn)程進(jìn)程P 進(jìn)程進(jìn)程Q : : 請求讀卡機請求讀卡機 請求打印機請求打印機 : : 請求打印機請求打印機 請求讀卡機請求讀卡機 : : 釋放讀卡機釋放讀卡機 釋放讀卡機釋放讀卡機 : : 釋放打印機釋放打印機 釋放打印機釋放打印機 : :資源分配不當(dāng)產(chǎn)生死鎖資源分配不當(dāng)產(chǎn)生死鎖

24、6.6.1 死鎖的形成死鎖的形成例例2：m個資源被個資源被n個進(jìn)程共享，每個進(jìn)程要求個進(jìn)程共享，每個進(jìn)程要求k個資個資源，則當(dāng)源，則當(dāng) m=n*(k-1) 時，如果分配不當(dāng)就可能發(fā)時，如果分配不當(dāng)就可能發(fā)生死鎖。生死鎖。 死鎖的定義：死鎖的定義：在兩個或多個并發(fā)進(jìn)程中，如果在兩個或多個并發(fā)進(jìn)程中，如果每個進(jìn)程持有某種資源而又都等待著別的進(jìn)程釋放每個進(jìn)程持有某種資源而又都等待著別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。此時每個進(jìn)程都占用了一定的資源但又都不能向前此時每個進(jìn)程都占用了一定的資源但又都不能向前推進(jìn)，稱這一組進(jìn)程產(chǎn)生可死鎖。

25、推進(jìn)，稱這一組進(jìn)程產(chǎn)生可死鎖。資源分配不當(dāng)產(chǎn)生死鎖資源分配不當(dāng)產(chǎn)生死鎖1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 資源不足資源不足 進(jìn)程推進(jìn)次序不合適進(jìn)程推進(jìn)次序不合適2. 2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 互斥條件互斥條件 一個資源一次只能被一個進(jìn)程使用。一個資源一次只能被一個進(jìn)程使用。 不可剝奪條件不可剝奪條件 一個資源僅能被占有它的進(jìn)程釋放。一個資源僅能被占有它的進(jìn)程釋放。 部分分配部分分配 一個進(jìn)程已占有了一些資源，但仍然要求其它資源。一個進(jìn)程已占有了一些資源，但仍然要求其它資源。 環(huán)路條件環(huán)路條件 系統(tǒng)中存在著一個由若干個進(jìn)程形成的環(huán)形請求鏈。系統(tǒng)中存在著一個由若干個進(jìn)程形成的環(huán)形

26、請求鏈。6.6.2. 死鎖的必要條件死鎖的必要條件解決死鎖問題的策略解決死鎖問題的策略破壞產(chǎn)生死鎖的四個必要條件之一破壞產(chǎn)生死鎖的四個必要條件之一 解決死鎖的策略：解決死鎖的策略： 死鎖的防止死鎖的防止 死鎖的避免死鎖的避免 死鎖的檢測死鎖的檢測6.6.3 6.6.3 死鎖的防止死鎖的防止 1.1.靜態(tài)分配資源：靜態(tài)分配資源：僅當(dāng)系統(tǒng)能滿足作業(yè)運行時所僅當(dāng)系統(tǒng)能滿足作業(yè)運行時所需的全部資源時，才把該作業(yè)調(diào)入內(nèi)存運行，需的全部資源時，才把該作業(yè)調(diào)入內(nèi)存運行，同時在作業(yè)運行前，將其所需的全部資源一次同時在作業(yè)運行前，將其所需的全部資源一次性地分配給該作業(yè)。作業(yè)在運行過程中不再提性地分配給該作業(yè)。作

27、業(yè)在運行過程中不再提出新的資源要求出新的資源要求破壞破壞“占有且等待資源占有且等待資源”和和“循環(huán)等待資源循環(huán)等待資源” 缺點：資源利用率低缺點：資源利用率低 作業(yè)等待時間長作業(yè)等待時間長2. 2. 按序分配資源：按序分配資源：系統(tǒng)中的所有資源類都分給系統(tǒng)中的所有資源類都分給一個唯一的序號，并要求每個進(jìn)程均應(yīng)一個唯一的序號，并要求每個進(jìn)程均應(yīng)嚴(yán)格按照遞增的次序請求資源嚴(yán)格按照遞增的次序請求資源破壞破壞 “循環(huán)等待資源循環(huán)等待資源” 缺點：缺點：對于實際資源使用順序與資源序號不一對于實際資源使用順序與資源序號不一致的作業(yè)仍存在著資源浪費現(xiàn)象致的作業(yè)仍存在著資源浪費現(xiàn)象3. 剝奪式分配資源剝奪式分配資源：可搶奪其它進(jìn)程的資源：可搶奪其它進(jìn)程的資源破壞破壞 “非搶奪式分配非搶奪式分配” 例：分配主存例：分配主存6.6.4 死鎖的避免死鎖的避免 銀行家算法銀行家算法 檢查申請者對各類資源的最大需求量，如果檢查申請者對各類資源的最大需求量，如果系