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

第8章

進(jìn)程同步機(jī)制與死鎖學(xué)習(xí)目標(biāo)<2

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

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

目錄CONTENTSPART8.1進(jìn)程（線程）的同步與互斥8.1進(jìn)程（線程）的同步與互斥<6

>

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

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

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

>

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

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

>

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

>

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

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

>

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

當(dāng)某個售票處有旅客買票時，進(jìn)程如程序8-2訂票過程8.1.1與時間有關(guān)的錯誤<11

>

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

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

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

>

顯然，這也是與時間有關(guān)的錯誤

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

>

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

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

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

8.1.2進(jìn)程同步與進(jìn)程互斥<14

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

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

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

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

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

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

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

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

8.1.2進(jìn)程同步與進(jìn)程互斥<17

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

>

1．進(jìn)程互斥的軟件方法

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

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

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

8.1.2進(jìn)程同步與進(jìn)程互斥<19

>

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

8.1.2進(jìn)程同步與進(jìn)程互斥<20

>

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

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

8.1.2進(jìn)程同步與進(jìn)程互斥<21

>

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

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

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

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

8.1.2進(jìn)程同步與進(jìn)程互斥<23

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

8.1.2進(jìn)程同步與進(jìn)程互斥<24

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

>

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

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

2）簡單：硬件方法的標(biāo)志設(shè)置簡單，含義明確，容易驗證其正確性

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

硬件方法的主要缺點(diǎn)包括：

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

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

>

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

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

>

信號量是荷蘭學(xué)者Dijkstra于1965年提出的一種卓有成效的進(jìn)程同步機(jī)制

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

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

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

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

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

>

信號量機(jī)制中P原語相當(dāng)于進(jìn)入?yún)^(qū)操作，V原語相當(dāng)于退出區(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

>

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

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

>

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

背景-2：北京大學(xué)圖書館PART8.2經(jīng)典的進(jìn)程同步問題<33

>8.2經(jīng)典的進(jìn)程同步問題Dijkstra把同步問題抽象成一種“生產(chǎn)者-消費(fèi)者關(guān)系”

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

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

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

生產(chǎn)者-消費(fèi)者同步問題的解決方案如程序8-7<36

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

>8.2.2多個生產(chǎn)者-消費(fèi)者問題

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

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

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

>8.2.2多個生產(chǎn)者-消費(fèi)者問題1．同步問題

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

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

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

>8.2.2多個生產(chǎn)者-消費(fèi)者問題<40

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

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

>8.2.3讀者-寫者問題

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

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

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

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

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

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

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

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

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

>

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

>

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

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

>

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

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

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

>2．死鎖的例子

程序8-10為申請不同類資源產(chǎn)生死鎖

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

>

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

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

>

程序8-11申請同類資源產(chǎn)生死鎖

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

>

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

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

>

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

>

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

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

>

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

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

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

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

>3．請求和保持條件

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

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

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

>1．死鎖預(yù)防

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

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

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

>

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

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

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

具體實施方法

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

>

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

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

>

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

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

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

>

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

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

>

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

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

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

>2．死鎖避免

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

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

>

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

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

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

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

>

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

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

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

>

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

>

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

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

>

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

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

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

>

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

>3．死鎖的檢測與解除

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

>

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

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

>

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

>

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

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

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

進(jìn)程重新運(yùn)行的代價包括

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

②進(jìn)程已經(jīng)運(yùn)行了多長時間，該進(jìn)程完成其任務(wù)還需要多長時間

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

④為完成其任務(wù)，進(jìn)程還需要多少資源

⑤有多少進(jìn)程要被撤銷

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

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

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

>盡量保證被剝奪資源的進(jìn)程代價最小

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

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

>

（2）撤銷進(jìn)程

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

>撤銷進(jìn)程的代價

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

②進(jìn)程類的外部代價

③運(yùn)行代價

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

>4．忽略死鎖

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

>

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