操作系統(tǒng) 課件 第8章 進程同步機制與死鎖

第8章

進程同步機制與死鎖學習目標<2

>1．理解進程間的相互作用及臨界區(qū)的概念和使用準則2．掌握進程同步、進程互斥的概念和實例3．掌握信號量及Ｐ、Ｖ操作4．掌握經典的進程同步、進程互斥問題的解決方案5．掌握死鎖的基本概念、死鎖的定義6．掌握死鎖發(fā)生的原因和四個必要條件7．掌握死鎖檢測與解除方法、死鎖避免及死鎖預防的各種方法教師導讀<3

>1．本章內容是關于進程同步與進程互斥問題產生及解決方法2．信號量及Ｐ、Ｖ操作是同步互斥機制之一，可以解決各種同步互斥問題3．生產者消費者問題和讀者寫者問題是典型的進程同步互斥模型4．死鎖隨著操作系統(tǒng)的復雜度增加而產生，并隨著技術的發(fā)展而發(fā)展5．在應對死鎖的策略中，平衡系統(tǒng)運行效率、資源利用率與發(fā)生死鎖的風險是關鍵8.1進程（線程）的同步與互斥8.2經典的進程同步問題8.3死鎖8.4哲學家就餐問題8.5本章小結

目錄CONTENTSPART8.1進程（線程）的同步與互斥8.1進程（線程）的同步與互斥<6

>

多道程序系統(tǒng)中并發(fā)進程通常有多個。在邏輯上具有某種聯(lián)系的進程稱為相關進程

如果一個進程的執(zhí)行不影響其他進程的執(zhí)行，且不受其他進程的影響，則這些并發(fā)進程相互之間是無關的

如果一個進程的執(zhí)行影響到其他進程的執(zhí)行，或者受其他進程的影響，則這些并發(fā)進程是相關的8.1.1與時間有關的錯誤<7

>

一個進程由于各種原因而可能被中斷，且斷點是不固定的。進程被中斷后，哪個進程可以得到運行，而被中斷的那個進程在什么時候再去占用處理器等等問題，則與進程調度策略有關

進程執(zhí)行的速度是不能由進程自身控制的。若干相關并發(fā)進程共享資源，形成交替使用共享資源的情形8.1.1與時間有關的錯誤<8

>

例如，兩個并發(fā)程序A和B共享一個公共變量n，程序A每執(zhí)行一次循環(huán)都要作n=n+1操作，程序B則在每一次循環(huán)中打印出n的值并將n重新置0。程序描述如程序8-1。8.1.1與時間有關的錯誤<9

>

由于程序A和B的執(zhí)行都以各自獨立的速度向前推進，它們的語句在時間上可任意穿插或交叉執(zhí)行，故程序A的①n=n+1操作可能在程序B的②print（n）和③n=0操作之前，也可能在它們之后或它們之間（即①出現(xiàn)在②之后，而在③之前），設在開始某個循環(huán)之前n的值為5，則對于上面三種情形，執(zhí)行完一個循環(huán)后，打印機印出的值可以分別為6、5和5，而執(zhí)行后的n值分別為0，1，0。相同的程序可能產生三組不同的結果，顯然，這不是我們所希望的

產生了這種情形的根本原因在于：在相關并發(fā)程序中共享了公共變量，使得程序的計算結果與并發(fā)程序執(zhí)行的時間有關（如上例中的三種情形，其結果時對時錯），所以，把它稱為“與時間有關的錯誤”8.1.1與時間有關的錯誤<10

>

另一個售票系統(tǒng)例子：假設一個售票系統(tǒng)有n個售票處（或者有n個網絡客戶端）。在售票系統(tǒng)的公共數(shù)據(jù)庫存放著某月某日某次車次的票額，這些票額用單元Aj（j=1,2,3,…）代表。每個客戶端訪問系統(tǒng)的公共數(shù)據(jù)庫。用P1，P2，…Pn表示各訂票的處理進程；而R1，R2，…，Rn為各進程執(zhí)行時所使用的存儲單元

當某個售票處有旅客買票時，進程如程序8-2訂票過程8.1.1與時間有關的錯誤<11

>

由于訂票進程執(zhí)行的時間以及要求購買的車票日期和車次是隨機的，因此存在著有若干個旅客幾乎在相同的時刻、不同的終端要求購買同一天同一車次的可能。于是，若干個進程都要訪問同一個Aj，進程并發(fā)執(zhí)行時可能出現(xiàn)如圖8-1中所示的情況。

在圖8-1中，進程Pi讀出的Aj值與進程Pk讀出的Aj值相同，當Aj≥1時，這兩個進程Pi和Pk都認為有票可售給旅客。于是，進程繼續(xù)執(zhí)行，各自對余票數(shù)減1，然后把剩余的余票數(shù)存回Aj。這樣售票系統(tǒng)的公共數(shù)據(jù)庫中的票額記錄就出錯了

如果在這些進程處理之前，Aj=1，即剛好只剩下一張票，那么這一張票就賣給了兩個旅客，甚至是多個旅客8.1.1與時間有關的錯誤<12

>

顯然，這也是與時間有關的錯誤

并發(fā)執(zhí)行的進程競爭資源就是互斥關系，使用其他進程的數(shù)據(jù)就是同步關系8.1.2進程同步與進程互斥<13

>

解決進程同步與互斥的做法有兩種：一是由競爭各方平等協(xié)商；二是引入進程管理者

臨界資源是指計算機系統(tǒng)中的需要互斥使用的硬件或軟件資源，如外設、共享代碼段、共享數(shù)據(jù)結構等。多個進程在對臨界資源進行寫入或修改操作時，必須互斥地進行

計算機系統(tǒng)中也有一些可以同時訪問的共享資源不是臨界資源，如只讀數(shù)據(jù)

8.1.2進程同步與進程互斥<14

>進程間的相互制約關系按相互感知程度分為如表8-1所列的三種類型。資源共享的程度分成三個層次：互斥（mutualexclusion）、死鎖（deadlock）和饑餓（starvation）

保證資源的互斥使用是指多個進程不同時使用同一個資源。避免死鎖是指避免多個進程互不相讓而得不到足夠的資源的情況出現(xiàn)。避免饑餓是指避免某些進程一直得不到資源8.1.2進程同步與進程互斥<15

>相互感知的程度交互關系一個進程對其他進程的影響潛在的控制問題相互不感知（完全不了解其他進程的存在)競爭（competition）一個進程的操作對其他進程的結果無影響互斥，死鎖，饑餓間接感知（雙方都與第三方交互，如共享資源）通過共享進行協(xié)作一個進程的結果依賴于從其他進程獲得的信息互斥，死鎖，饑餓直接感知（雙方直接交互，如通信）通過通信進行協(xié)作一個進程的結果依賴于從其他進程獲得的信息死鎖，饑餓表8-1進程間的相互制約關系8.1.2進程同步與進程互斥<16

>臨界資源的正確訪問過程分成如圖8-2所示的四個部分：

1）進入?yún)^(qū)（entrysection）：在進入?yún)^(qū)設置相應的“正在訪問臨界區(qū)”標志，檢查可否進入臨界區(qū)；以防止其他進程同時進入臨界區(qū)

2）臨界區(qū)（criticalsection）：進程中訪問臨界資源的一段代碼

3）退出區(qū)（exitsection）：將“正在訪問臨界區(qū)”的標志清除

4）剩余區(qū)（remaindersection）：代碼中的其余部分

8.1.2進程同步與進程互斥<17

>同步機制應遵循以下4條準則1）空閑則入：任何時刻最多只有一個進程位于臨界區(qū)。當有進程位于臨界區(qū)時，其他進程不能進入臨界區(qū)2）忙則等待：當已有進程處于臨界區(qū)時，后到達的進程只能在進入?yún)^(qū)等待3）有限等待：等待進入臨界區(qū)的進程不能無限期地“死等”4）讓權等待：因在進入?yún)^(qū)等待而不能進入臨界區(qū)的進程，應釋放處理機，轉換到阻塞狀態(tài)8.1.2進程同步與進程互斥<18

>

1．進程互斥的軟件方法

通過平等協(xié)商方式實現(xiàn)進程互斥的最初方法是軟件方法。其基本思路是在進入?yún)^(qū)檢查和設置一些標志，如果已有進程在臨界區(qū)，則在進入?yún)^(qū)通過循環(huán)檢查進行等待；在退出區(qū)修改標志

皮特遜算法（Peterson’sAlgorithm）是一種軟件實現(xiàn)的臨界區(qū)訪問算法，其做法是：先修改臨界區(qū)標識、后檢查、后修改者等待

以兩個進程為例，假設有兩個進程Pi和Pj，其中一個公用整型變量為turn，描述允許進入臨界區(qū)的進程標識；turn為i時，進程Pi可進入，否則不可進入；標志flag[i]表示進程i想進入臨界區(qū)，若flag[i]為TRUE，則進程i準備進入臨界區(qū)，反之則不想進入

8.1.2進程同步與進程互斥<19

>

皮特遜算法的基本思想是：每個進程都在進入?yún)^(qū)先將flag修改為本進程為TRUE，而將turn設為另一個進程，所以當另一個進程想進臨界區(qū)時就可以進入。如果兩個進程同時希望進入臨界區(qū)，那么turn會在幾乎同時被設成i和j，但是只有后一個賦值語句的結果會被保持，因此turn的最終值決定了先到的（先賦值的）進程能進入臨界區(qū)。圖8-3為進程Pi的代碼

8.1.2進程同步與進程互斥<20

>

皮特遜算法可實現(xiàn)四條準則中的前二條：空閑則入和忙則等待。但Pi和Pj會形成乒乓效應，也就是當Pi希望進入臨界區(qū)而Pj無響應時，Pi會出現(xiàn)“饑餓”現(xiàn)象。另外對于三個以上進程間的互斥其標識設計更為復雜

這里的根本問題就是修改標志和檢查標志不能作為一個整體來執(zhí)行

8.1.2進程同步與進程互斥<21

>

2．進程互斥的硬件方法軟件方法實現(xiàn)進程互斥不適用于數(shù)目很多的進程間的互斥

利用硬件方法的主要思路是用一條指令完成讀和寫兩個操作，因而保證讀操作與寫操作不被打斷。依據(jù)所采用的指令的不同硬件方法分成TS指令和Swap指令兩種

（1）Test-and-Set指令TS指令的功能是讀出指定標志后把該標志設置為TRUE。TS指令的功能可描述成程序8-38.1.2進程同步與進程互斥<22

>TS指令互斥算法是，每個臨界資源設置一個公共布爾變量lock，表示資源的兩種狀態(tài)：TRUE表示正被占用，F(xiàn)ALSE表示空閑。初值為FALSE。在進入?yún)^(qū)利用TS進行檢查和修改標志lock。有進程在臨界區(qū)時，重復檢查；直到其他進程退出時，檢查通過。如圖8-4所示，所有要訪問臨界資源的進程的進入?yún)^(qū)和退出區(qū)代碼是相同的

8.1.2進程同步與進程互斥<23

>（2）Swap指令（或Exchange指令）Swap指令的功能是交換兩個字（字節(jié)）的內容。我們可用程序8-4的函數(shù)描述Swap指令的功能

8.1.2進程同步與進程互斥<24

>Swap指令互斥算法是，每個臨界資源設置一個公共布爾變量lock，初值為FALSE；每個進程設置一個私有布爾變量key，用于與lock間的信息交換。在進入?yún)^(qū)利用Swap指令交換lock與key的內容，然后檢查key的狀態(tài)；有進程在臨界區(qū)時，重復交換和檢查過程，直到其他進程退出時，檢查通過。圖8-5所有要訪問臨界資源的進程的相關代碼8.1.2進程同步與進程互斥<25

>

硬件方法把修改和檢查操作合成為整體而具有明顯的優(yōu)點，體現(xiàn)在以下幾個方面：

1）適用范圍廣：硬件方法適用于任意數(shù)目的進程，在單處理器和多處理器環(huán)境中完全相同

2）簡單：硬件方法的標志設置簡單，含義明確，容易驗證其正確性

3）支持多個臨界區(qū)：在一個進程內有多個臨界區(qū)時，只需為每個臨界區(qū)設立一個布爾變量

硬件方法的主要缺點包括：

1）進程在等待進入臨界區(qū)時，處理機為“忙等”，不能實現(xiàn)“讓權等待”

2）進入臨界區(qū)的進程是從等待進程中隨機選擇的，可能導致“饑餓”8.1.3信號量（semaphore）和P、V原語<26

>

平等進程間的協(xié)商機制存在有些問題是平等協(xié)商無法解決的，需要引入一個地位高于進程的管理者來解決公有資源的使用問題

操作系統(tǒng)可以從進程管理者的角度來處理互斥的問題，信號量就是由操作系統(tǒng)提供的管理公有資源的有效手段8.1.3信號量（semaphore）和P、V原語<27

>

信號量是荷蘭學者Dijkstra于1965年提出的一種卓有成效的進程同步機制

信號量機制所使用的P、V原語就來自荷蘭語的test（proberen）和increment（verhogen）所謂“原語”即指執(zhí)行中不受進程調度和執(zhí)行的打斷，恰如一條指令

每個信號量s除一個整數(shù)值s.count（計數(shù)）外，還有一個進程等待隊列s.queue，其中存放的是阻塞在該信號量的各個進程的標識

信號量只能通過初始化和兩個標準的原語即P原語和V原語來訪問。P、V原語的執(zhí)行很好地解決了操作的整體性

信號量的初始化可指定一個非負整數(shù)值，表示空閑資源總數(shù)。若信號量為非負整數(shù)值，表示當前的空閑資源數(shù)；若為負值，其絕對值表示當前等待臨界區(qū)的進程數(shù)

8.1.3信號量（semaphore）和P、V原語<28

>

信號量機制中P原語相當于進入?yún)^(qū)操作，V原語相當于退出區(qū)操作

P原語所執(zhí)行的操作可用下面函數(shù)wait(s)來描述。見程序8-5

8.1.3信號量（semaphore）和P、V原語<29

>V原語所執(zhí)行的操作可用下面函數(shù)signal(s)來描述。見程序8-68.1.3信號量（semaphore）和P、V原語<30

>

信號量機制可實現(xiàn)臨界資源的互斥訪問。如圖8-6所示，mutex（MUTualExclusion）為互斥信號量，其初值為1；臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間

在使用信號量時，必須成對使用P和V原語。遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放給其他等待的進程。P、V原語的使用不能次序錯誤、重復或遺漏8.1.3信號量（semaphore）和P、V原語<31

>

信號量機制可實現(xiàn)進程間的同步。如圖8-7所示前趨關系是指并發(fā)執(zhí)行的進程P1和P2中，分別有代碼C1和C2，要求C1在C2開始前完成執(zhí)行。我們可設置一個互斥信號量S12，其初值為0。這樣，只有在P1執(zhí)行到V(S12)后，P2才會結束P(S12)的執(zhí)行

背景-2：北京大學圖書館PART8.2經典的進程同步問題<33

>8.2經典的進程同步問題Dijkstra把同步問題抽象成一種“生產者-消費者關系”

生產者-消費者問題是計算機中各種實際的同步、互斥問題的一個抽象模型。計算機系統(tǒng)中的許多問題都可被歸結為生產者和消費者關系，例如，處理并生成數(shù)據(jù)是生產者進程，打印結果是消費者進程；在輸入時輸入進程是生產者進程，處理并生成數(shù)據(jù)是消費者進程<34

>8.2.1簡單生產者-消費者問題簡單生產者-消費者問題：設有一個生產者進程P，一個消費者進程Q，它們通過一個緩沖區(qū)聯(lián)系起來，如圖8-8所示。緩沖區(qū)只能容納一個產品，生產者不斷地生產產品，然后往空緩沖區(qū)送產品；而消費者則不斷地從緩沖區(qū)中取出產品，并消費掉<35

>8.2.1簡單生產者-消費者問題生產者-消費者問題中，生產者進程P不能往已經“滿”的緩沖區(qū)中放入產品，設置信號量empty，其初值為1，用于指示空緩沖區(qū)數(shù)量；同樣，消費者進程Q也不能從已經“空”的緩沖區(qū)中取出產品，設置信號量full，初值為0，用于指示滿緩沖區(qū)數(shù)量

生產者-消費者同步問題的解決方案如程序8-7<36

>8.2.2多個生產者-消費者問題簡單生產者-消費者問題可以推廣為多個生產者和多個消費者問題多個生產者和多個消費者問題的描述：設有若干個生產者進程P1，P2，…，Pn，若干個消費者進程Q1，Q2，…，Qm，它們通過一個環(huán)形緩沖池聯(lián)系起來，如圖8-8所示。該環(huán)形緩沖池由k個大小相等的緩沖區(qū)組成，每個緩沖區(qū)能容納一個產品，生產者每次往空緩沖區(qū)送一個產品；消費者每次從滿緩沖區(qū)取出一個產品。生產者進程不斷地生產產品并把它們放入緩沖池內，消費者進程不斷地從緩沖池內取產品并消費之。這里既存在同步問題，也存在互斥問題<37

>8.2.2多個生產者-消費者問題

當整個緩沖區(qū)全滿時，此時生產者必須暫緩生產。當整個緩沖區(qū)全空時，此時消費者必須等待。在上述生產者和消費者之間存在一定的合作關系

在生產者向空的緩沖區(qū)里放入產品之后，或者消費者從滿的緩沖區(qū)里取出產品之后，有關的緩沖區(qū)就改變了它的狀態(tài)

緩沖區(qū)首尾相接形成的環(huán)形緩沖池是臨界資源，因為生產者和消費者都要使用它。在某個緩沖區(qū)為空時，消費者不能從這個空的緩沖區(qū)里取出產品；同樣，在某個緩沖區(qū)為滿時，生產者不能向這個滿的緩沖區(qū)里放入產品?？梢娫谏a者和消費者之間還存在著互斥關系<38

>8.2.2多個生產者-消費者問題1．同步問題

P進程不能往“滿”的緩沖區(qū)中放產品，設置信號量empty，初值為k，用于指示緩沖池中空緩沖區(qū)數(shù)目；進程Q不能從“空”的緩沖區(qū)中取產品，設置信號量full，初值為0，用于指示緩沖池中滿緩沖區(qū)數(shù)目2．互斥問題

設置信號量mutex，初值為1，用于實現(xiàn)臨界區(qū)（環(huán)形緩沖池）的互斥；另設整型量i，j，初值均為0。i用于指示空緩沖區(qū)的頭指針；j用于指示有產品的滿緩沖區(qū)的頭指針3．算法

該同步互斥問題的解決方案如程序8-8所示<39

>8.2.2多個生產者-消費者問題<40

>8.2.3讀者-寫者問題1．讀者-寫者問題的描述

假定有某個共享文件F，系統(tǒng)允許若干進程對文件F進行讀或寫。這里把要讀文件的進程稱為讀者，把要寫文件的進程稱為寫者。讀者和寫者必須遵守如下的規(guī)定（1）多個進程可以同時讀文件F（2）任一個進程在對文件F進行寫時，不允許其他進程對文件進行讀或寫（3）當有進程正在讀文件時不允許任何進程去寫文件<41

>8.2.3讀者-寫者問題

當有多個讀者和寫者都要讀寫文件F時，按規(guī)定每次只允許一個進程執(zhí)行寫操作，且在有進程執(zhí)行寫時不允許進程讀文件。顯然，寫者與寫者之間要互斥，寫者與讀者之間也要互斥。但按規(guī)定多個讀者可同時讀文件，也就是說只要第一個讀者取得了讀文件的權利，則其他讀者可以跟著讀文件。所以，寫者與讀者之間的互斥就變成了寫者與第一個讀者之間的互斥

設read_count記錄當前正在讀的讀者進程個數(shù)，由于多個讀者都對read_count進行修改，所以read_count是一個共享變量，需要互斥使用，故設置信號量mutex。再設置信號量write，用于寫者之間互斥，或第一個讀者和最后一個讀者與寫者的互斥<42

>8.2.3讀者-寫者問題2．讀者-寫者問題的解決方案程序8-9給出讀者-寫者問題的解決方案<43

>8.2.3讀者-寫者問題read_count是一個計數(shù)器，初值為0。而mutex和write都是信號量，它們的初值都是1

read_count是一個共享變量，需要互斥使用，在每個讀者進入時，對read_count的計數(shù)不能出錯。另外，如果第一個讀者進入，就不能再允許寫者進入，這就是ifread_count=1，thenP（write）語句的作用；第一個讀者負責禁止任何寫者進入。以上這兩個操作都要放在互斥區(qū)內

而其他的讀者可以隨著第一個讀者進入陸續(xù)進入

當有讀者完成讀操作之后，相應地要對read_count進行減一操作。而且如果read_count=0，表明已經沒有讀者了，寫者可以隨時進入

對于讀者來說，只要有一個寫者已經在臨界區(qū)執(zhí)行寫操作，所有的讀者就必須等待<44

>三個經典的進程同步問題總結三個經典的同步問題均涉及到互斥以及同步，他們的共同特點如下：1、互斥時對信號量的PV操作通常在同一進程中，而同步的PV操作分布在不同進程中2、對信號量的PV操作在程序流程上必定是成對出現(xiàn)，不能缺少，缺少了會死鎖3、當同時有互斥P操作和同步P操作時，同步P操作一定在前，互斥P操作在后，不能顛倒，而V操作無此限制PART8.3死鎖8.3.1死鎖的定義<46

>

死鎖現(xiàn)象并不是計算機操作系統(tǒng)環(huán)境下所獨有，在日常生活乃至各個領域是屢見不鮮的。例如，沒有交通燈的十字路口出現(xiàn)了死鎖，見圖8-98.3.1死鎖的定義<47

>

死鎖是指在多道程序系統(tǒng)中的一種現(xiàn)象：一組進程中的每一個進程均無限期地等待被該組進程中的另一個進程所占有且永遠不會釋放的資源。系統(tǒng)發(fā)生這種現(xiàn)象稱為系統(tǒng)處于死鎖狀態(tài)，簡稱死鎖。處于死鎖狀態(tài)的進程稱為死鎖進程

當死鎖發(fā)生后，死鎖進程將一直等待下去，除非有來自死鎖進程之外的某種干預。系統(tǒng)發(fā)生死鎖時，死鎖進程的個數(shù)至少為兩個系統(tǒng)發(fā)生死鎖不僅浪費了大量的系統(tǒng)資源，甚至會導致整個系統(tǒng)崩潰，帶來災難性的后果8.3.2死鎖產生的原因<48

>

產生死鎖的原因主要有兩個：一是競爭資源，系統(tǒng)資源在分配時出現(xiàn)失誤，進程間對資源的相互爭奪而造成僵局；二是多道程序運行時，進程推進順序不合理1．資源的概念系統(tǒng)中的資源有兩類：永久性資源（可重用資源），如內存、外部設備、CPU等硬件資源，以及各種數(shù)據(jù)文件、表格、共享程序代碼等軟件資源

臨時性資源（消耗性資源），是指由某個進程所產生、只為另一個進程使用一次、或經過短暫時間后便不再使用的資源，如I/O和時鐘中斷信號、同步信號、消息等

永久性資源和臨時性資源都可能導致死鎖發(fā)生8.3.2死鎖產生的原因<49

>2．死鎖的例子

程序8-10為申請不同類資源產生死鎖

進程P1和P2在運行中都使用輸入、輸出設備，假定系統(tǒng)中只有一臺輸入設備，一臺輸出設備，則進程P1和P2可有如下形式8.3.2死鎖產生的原因<50

>

當進程P1申請并獲得了該輸入設備后（運行完成①），由于進程切換或某種原因，停止前進。此時P2到達，P2進程完成了對輸出設備的申請（運行完成②），接下來再申請輸入設備（運行④），由于輸入設備被P1占用必將導致P2被阻塞且進入等待隊列等待

若進程P1重新獲得運行機會，接下來便要申請輸出設備（運行③），同樣，也被阻塞進入等待輸出設備的等待隊列。進程P1和P2彼此無限地等待對方釋放資源從而喚醒自己，于是形成了僵局，如圖8-10所示8.3.2死鎖產生的原因<51

>

程序8-11申請同類資源產生死鎖

假設有一類可重用資源R，如主存（或磁盤），它包含有m個頁面（或扇區(qū)），由n個進程P1，P2，…，Pn（2≤m≤n）共享。假定每個進程按下述順序依次申請和釋放頁面（或扇區(qū)）：8.3.2死鎖產生的原因<52

>

這里每次申請和釋放只涉及R的一個分配單元（頁面或扇區(qū)）。因此，當所有單元全部分配完畢時，很容易發(fā)生死鎖；占有R的單元的所有進程（前m個進程）會永遠封鎖在第二次申請②上，而有些進程（n－m個進程）類似地會封鎖在它們的第一次申請①上。圖8-11說明了n＝3、m＝2時系統(tǒng)的狀態(tài)

這類死鎖是相當普遍的。例如，在若干輸入和輸出進程競爭磁盤空間的SPOOLing系統(tǒng)中，就可能發(fā)生這類死鎖。如果磁盤空間完全分配給等待裝入的作業(yè)輸入文件和已部分運行的作業(yè)輸出記錄，則系統(tǒng)就有可能發(fā)生死鎖8.3.2死鎖產生的原因<53

>

程序8-12說明了P、V操作使用不當產生死鎖對于第四章描述的生產者和消費者問題，若把生產者和消費者程序中前面兩個P操作順序顛倒，則形成如下所示的兩個序列8.3.2死鎖產生的原因<54

>

當進行了n次生產后（或n個生產者，每人都送了緩沖區(qū)一個產品后），緩沖區(qū)被全部占滿，此時empty=0。若生產者執(zhí)行P（mutex）后（此時mutex=0），又繼續(xù)執(zhí)行P（empty），此刻empty=?1，使生產者因無可用緩沖區(qū)而在empty上等待。若又有一個消費者進程到達，并執(zhí)行P（mutex），結果使mutex=?1

因此，消費者也阻塞，并且在mutex上等待。此時，生產者、消費者都彼此等待對方來喚醒自己，處于循環(huán)等待狀態(tài)，這樣便形成了死鎖局面8.3.2死鎖產生的原因<55

>

程序8-13對臨時性資源的使用不加限制而引起的死鎖信件可以看作是一種臨時性資源，也可能引起死鎖。比如，進程P1等待進程P3的信件s3到來后再向進程P2發(fā)送信件s1，P2又要等待P1的信件s1到來后再向P3發(fā)送信件s2，而P3也要等待P2的信件s2來到后才能發(fā)出信件s3。在這種情況就形成了循環(huán)等待，產生死鎖8.3.3死鎖產生的必要條件<56

>產生死鎖有四個必要條件（Coffman等，1971）1．互斥條件

資源是獨占的且排他使用2．不可剝奪條件

又稱不可搶占或不可強占。進程所獲得的資源在未釋放前，不能被其他進程強行剝奪8.3.3死鎖產生的必要條件<57

>3．請求和保持條件

又稱部分分配或占有申請。進程在申請新的資源的同時，繼續(xù)占用已分配到的資源4．循環(huán)等待條件

又稱環(huán)路等待。在發(fā)生死鎖時，必然存在一個進程等待隊列{P1，P2，…，Pn}，其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個進程等待環(huán)路

8.3.4死鎖發(fā)生后的處理方法<58

>1．死鎖預防

死鎖預防通過設置某些嚴格限制，破壞產生死鎖的必要條件以防止死鎖發(fā)生8.3.4死鎖發(fā)生后的處理方法<59

>若死鎖是由于資源數(shù)量不足而造成的，可以通過增加資源數(shù)量的方法來進行預防，例如內存

臨時性的資源如系統(tǒng)中的共享寫數(shù)據(jù)，各種信號量等，不能通過增加資源數(shù)量來解決，所以這種情況下通過破壞互斥條件來預防死鎖不現(xiàn)實8.3.4死鎖發(fā)生后的處理方法<60

>

在預防死鎖的靜態(tài)分配策略中，資源分配的原則是

一個進程在申請新資源的要求不能立即得到滿足時，便處于等待狀態(tài)。而一個處于等待狀態(tài)的進程的全部資源可以被剝奪。被剝奪的資源重新加入到資源表中。僅當該進程重新獲得它原有的資源以及得到新申請的資源時，才能重新啟動執(zhí)行

這種方法破壞了不可剝奪條件

具體實施方法

（1）若一個進程已占用了某些資源，又要申請一個新的資源，在申請新的資源時，不能立即得到滿足，在變?yōu)榈却隣顟B(tài)之前，該進程必須釋放已占有的所有資源，即阻塞前釋放資源8.3.4死鎖發(fā)生后的處理方法<61

>

（2）若一個進程申請某些資源，首先系統(tǒng)應檢查這些資源是否可用，如果可用，就分配給該進程。否則，系統(tǒng)檢查這些資源是否分配給另外某個等待進程。若是，則系統(tǒng)將剝奪所需資源，分配給這個進程。如果資源沒有被等待進程占有，那么，該進程必須等待。在其等待過程中，其資源也有可能被剝奪

破壞不可剝奪條件以預防死鎖的方法適用于這樣一些資源，它們的狀態(tài)是容易保存和恢復的，例如CPU、內存等在預防死鎖的靜態(tài)分配策略中，還可以采用以下方法，該方法破壞了請求和保持條件8.3.4死鎖發(fā)生后的處理方法<62

>

（3）每個進程必須在開始執(zhí)行前就申請它所需要的全部資源，僅當系統(tǒng)能滿足進程的資源申請要求且把資源一次性分配給進程后，該進程才能開始執(zhí)行

采用該方法后，進程在執(zhí)行過程中不再申請資源，故不可能出現(xiàn)占有了某些資源再等待其他資源的情況，即“請求和保持”的條件不成立，從而預防死鎖的發(fā)生

這種方法其缺點是嚴重浪費系統(tǒng)資源靜態(tài)分配資源策略還有一個問題是大部分進程在運行開始時不能確定所需要的全部資源，例如堆棧所需的內存8.3.4死鎖發(fā)生后的處理方法<63

>

（4）當進程沒有占用資源時才允許它去申請資源，如果進程已經占用了某些資源而又要再申請資源，則它應先歸還所占的資源后再申請新資源

這種資源分配策略仍會使進程處于等待狀態(tài)，同時也存在著資源利用率低的缺點8.3.4死鎖發(fā)生后的處理方法<64

>

采用資源有序分配策略打破了循環(huán)等待的條件

其基本思想是將系統(tǒng)中所有資源順序編號。進程申請資源時，必須嚴格按照資源編號的順序進行，否則系統(tǒng)不予分配。釋放資源時，應按編號逆序進行

8.3.4死鎖發(fā)生后的處理方法<65

>2．死鎖避免

在資源的動態(tài)分配過程中，采取某種方法防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖的發(fā)生。可獲得較高的資源利用死鎖避免的基本思想是：系統(tǒng)對進程發(fā)出的每一個申請進行動態(tài)檢查，并根據(jù)檢查結果決定是否分配資源；如果分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配

死鎖避免和死鎖預防的區(qū)別在于，死鎖預防是設法破壞產生死鎖的四個必要條件之一，嚴格地防止死鎖的出現(xiàn)。而死鎖避免則是在系統(tǒng)運行過程中注意避免死鎖的最終發(fā)生8.3.4死鎖發(fā)生后的處理方法<66

>

由于在避免死鎖的策略中允許進程動態(tài)地申請資源，因而，系統(tǒng)需提供某種方法在進行資源分配之前，先分析資源分配的安全性。當估計到可能有死鎖發(fā)生時就應設法避免死鎖的發(fā)生

如果操作系統(tǒng)能保證所有的進程在有限時間內得到需要的全部資源，則稱系統(tǒng)處于“安全狀態(tài)”，否則說系統(tǒng)是不安全的

所謂安全狀態(tài)是指，如果存在一個由系統(tǒng)中所有進程構成的安全序列{P1，…，Pn}，則系統(tǒng)處于安全狀態(tài)。一個進程序列{P1，…，Pn}是安全的，如果對于其中每一個進程Pi(1≤i≤n)，它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj(j<i)當前占有資源量之和。則系統(tǒng)處于安全狀態(tài)8.3.4死鎖發(fā)生后的處理方法<67

>如果不存在任何一個安全序列，則系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)不一定導致死鎖，但死鎖狀態(tài)一定是不安全狀態(tài)它們的關系如圖8-12所示8.3.4死鎖發(fā)生后的處理方法<68

>

最著名的死鎖避免算法是由Dijkstra[1965]和Habermann[1969]提出來的銀行家算法。這一名稱的來歷是基于該算法將操作系統(tǒng)比作一個銀行家，操作系統(tǒng)的各種資源比作資金，申請資源的進程比作向銀行貸款的顧客

操作系統(tǒng)的資源分配問題就如同銀行家利用其資金貸款的問題，一方面銀行家能貸款給若干顧客，滿足顧客對資金的要求；另一方面，銀行家可以安全地收回其全部貸款而不至于破產8.3.4死鎖發(fā)生后的處理方法<69

>銀行家算法規(guī)定（1）當一個顧客對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該顧客（2）顧客可以分期貸款，但貸款的總數(shù)不能超過最大需求量（3）當銀行家現(xiàn)有的資金不能滿足顧客尚需的貸款數(shù)額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間里得到貸款（4）當顧客得到所需的全部資金后，一定能在有限的時間里歸還所有的資金8.3.4死鎖發(fā)生后的處理方法<70

>

假定某系統(tǒng)有三類資源A、B、C，A類資源共有10個資源實例，B類資源共有5個資源實例，C類資源共有7個資源實例，現(xiàn)有5個進程P1、P2、P3、P4、P5，它們對各類資源的最大需求量和第一次分配后已占有的資源量如圖8-13所示8.3.4死鎖發(fā)生后的處理方法<71

>

應用銀行家算法，找到一個進程安全序列P2，P4，P5，P3，P1，可以得出結論：圖8-13中的系統(tǒng)狀態(tài)是安全狀態(tài)

在此狀態(tài)下，進程P2提出新的資源申請：A類1個，B類0個，C類2個，進行試探性分配后，系統(tǒng)狀態(tài)如圖8-14所示8.3.4死鎖發(fā)生后的處理方法<72

>

應用銀行家算法，仍然可以找到一個進程安全序列P2，P4，P5，P1，P3，表明該系統(tǒng)狀態(tài)是安全狀態(tài)，可以實施資源分配

在圖8-14所示狀態(tài)下，進程P5又申請資源：A類3個，B類3個，C類0個，此時系統(tǒng)不能實施分配，因為該申請超過了系統(tǒng)當前剩余的資源量

若進程P1提出新的資源申請：A類0個，B類2個，C類0個，也不能實施資源分配，因為根據(jù)銀行家算法，若進行了分配，則在新的系統(tǒng)狀態(tài)下找不到進程安全序列，這將導致系統(tǒng)進入不安全狀態(tài)8.3.4死鎖發(fā)生后的處理方法<73

>

不安全狀態(tài)并非是死鎖狀態(tài)，只是有死鎖的可能性8.3.4死鎖發(fā)生后的處理方法<74

>3．死鎖的檢測與解除

死鎖的檢測與解除是在系統(tǒng)運行過程中，通過在系統(tǒng)中設置檢測機構，定時檢測死鎖是否真的發(fā)生，并精確地確定與死鎖有關的進程與資源，然后采取措施解除死鎖8.3.4死鎖發(fā)生后的處理方法<75

>

操作系統(tǒng)可定時運行一個“死鎖檢測”程序，該程序按一定的算法去檢測系統(tǒng)中是否存在死鎖，即是否存在“循環(huán)等待”條件。

通常，死鎖檢測可以在任何一次資源分配后，也可以在每次調度后，或者利用定時器定時運行檢測，或某個進程長期位于阻塞態(tài)或阻塞進程過多時，啟動死鎖檢測程序8.3.4死鎖發(fā)生后的處理方法<76

>

死鎖檢測的算法過程（1）為每個進程和每個資源指定唯一編號（2）設置一張資源分配狀態(tài)表，每個表目包含“資源號”和占有該資源的“進程號”兩項，資源分配表中記錄了每個資源正在被哪個進程所占有（3）設置一張進程等待分配表，每個表目包含“進程號”和該進程所等待的“資源號”兩項（4）算法規(guī)則：當任一進程Pj申請一個已被其他進程占用的資源ri時，進行死鎖檢測。檢測算法通過反復查找資源分配表和進程等待表，來確定進程Pj對資源ri的請求是否導致形成環(huán)路，若是，便確定出現(xiàn)死鎖8.3.4死鎖發(fā)生后的處理方法<77

>

例如，圖8-15所示系統(tǒng)中有進程P1、P2和P3共享資源r1、r2和r3。在某一時刻資源使用情況如圖8-15(a)所示。此后依次發(fā)生P1請求r2，P2請求r3，P3請求r1。當執(zhí)行死鎖檢測算法后，得到圖(b)；再執(zhí)行死鎖檢測算法，得到圖(c)；再執(zhí)行死鎖檢測算法，得到圖(d)。檢查圖(d)與圖(a)，確定是否出現(xiàn)死鎖8.3.4死鎖發(fā)生后的處理方法<78

>解除死鎖的方法剝奪資源法解除死鎖（1）選擇一個犧牲進程，即要剝奪哪個進程的哪些資源（2）被選中的進程重新運行或回退到某一點開始繼續(xù)運行8.3.4死鎖發(fā)生后的處理方法<79

>（3）保證不發(fā)生“餓死”現(xiàn)象（4）“最小代價”

進程重新運行的代價包括

①進程的優(yōu)先級

②進程已經運行了多長時間，該進程完成其任務還需要多長時間

③該進程使用的資源種類和數(shù)量？這些資源能簡單地剝奪嗎

④為完成其任務，進程還需要多少資源

⑤有多少進程要被撤銷

⑥該進程被重新啟動運行的次數(shù)8.3.4死鎖發(fā)生后的處理方法<80

>死鎖的解除方法（1）剝奪資源

使用掛起/激活機制掛起一些進程，剝奪它們占有的資源給死鎖進程，以解除死鎖8.3.4死鎖發(fā)生后的處理方法<81

>盡量保證被剝奪資源的進程代價最小

①還原算法，還原到資源剝奪前的計算結果

②建立檢查點，用來恢復資源剝奪前的狀態(tài)8.3.4死鎖發(fā)生后的處理方法<82

>

（2）撤銷進程

撤銷死鎖進程，將它們占有的資源分配給另一些死鎖進程，直到死鎖解除為止8.3.4死鎖發(fā)生后的處理方法<83

>撤銷進程的代價

①進程優(yōu)先數(shù)，即被撤銷進程的優(yōu)先數(shù)

②進程類的外部代價

③運行代價

8.3.4死鎖發(fā)生后的處理方法<84

>4．忽略死鎖

對于那些死鎖發(fā)生的幾率極低，而解決死鎖的方法代價極大或暫時沒有辦法解決的死鎖問題暫時不予理睬PART8.4哲學家就餐問題8.4哲學家就餐問題<86

>

哲學家就餐問題是操作系統(tǒng)中關于進程同步與互斥的經典問題，也是涉及到死鎖的關鍵問