操作系統(tǒng)-第三章 進(jìn)程管理

1、第三章 進(jìn)程管理3.1 進(jìn)程(PROCESS)3.2 進(jìn)程描述及狀態(tài)轉(zhuǎn)換3.3 進(jìn)程控制3.4 進(jìn)程互斥3.5 進(jìn)程同步3.6 死鎖問題(DEADLOCK)為了描述程序在并發(fā)執(zhí)行時(shí)對系統(tǒng)資源的共享，我們需要一個(gè)描述程序執(zhí)行時(shí)動(dòng)態(tài)特征的概念，這就是進(jìn)程。在本章中，我們將討論進(jìn)程概念、進(jìn)程控制和進(jìn)程間關(guān)系。3.1 進(jìn)程(PROCESS)3.1.1 程序的順序執(zhí)行和并發(fā)執(zhí)行3.1.2 進(jìn)程的引入3.1.3 進(jìn)程的定義3.1.4 進(jìn)程和程序及作業(yè)的關(guān)系返回3.1.1 程序的順序執(zhí)行和并發(fā)執(zhí)行程序的執(zhí)行有兩種方式：順序執(zhí)行和并發(fā)執(zhí)行。順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡單的單片機(jī)系統(tǒng)；現(xiàn)在的操作

2、系統(tǒng)多為并發(fā)執(zhí)行，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。1程序的順序執(zhí)行及其特性圖3.1表示每次僅能調(diào)度一個(gè)用戶作業(yè)進(jìn)行操作的先后次序。輸入、計(jì)算和打印輸出工作只能串行執(zhí)行，我們可以把程序的執(zhí)行過程看作是一系列狀態(tài)轉(zhuǎn)變過程，每執(zhí)行一個(gè)操作，系統(tǒng)就從一種狀態(tài)變成另一種狀態(tài)。圖中I表示輸入操作，P表示處理操作，O表示輸出操作。圖3.1 順序處理操作的先后次序順序執(zhí)行的特征順序性：按照程序結(jié)構(gòu)所指定的次序（可能有分支或循環(huán)）封閉性：獨(dú)占全部資源，計(jì)算機(jī)的狀態(tài)只由于該程序的控制邏輯所決定可再現(xiàn)性：初始條件相同則結(jié)果相同。如：可通過空指令控制時(shí)間關(guān)系。2資源共享操作系統(tǒng)是用來實(shí)現(xiàn)對計(jì)

3、算機(jī)資源進(jìn)行管理的一個(gè)大型系統(tǒng)程序，其基本特征之一就是資源共享。這里的資源就是指計(jì)算機(jī)處理一個(gè)任務(wù)或一個(gè)作業(yè)時(shí)的所有硬設(shè)備（處理機(jī)、內(nèi)存、外存、輸入/輸出設(shè)備等）和軟設(shè)備（文件、程序、數(shù)據(jù)、信息等）的總稱。所謂資源共享，就是指計(jì)算機(jī)中并發(fā)執(zhí)行的多個(gè)程序交替使用計(jì)算機(jī)硬件和軟件資源。操作系統(tǒng)提供了兩種實(shí)現(xiàn)資源共享的方法 。（1）由操作系統(tǒng)統(tǒng)一管理和分配。（2）由進(jìn)程自行使用。 3多道系統(tǒng)中程序執(zhí)行環(huán)境的變化1、多道系統(tǒng)運(yùn)行環(huán)境的變化：多個(gè)程序同時(shí)位于內(nèi)存中，處于并發(fā)狀態(tài)。在大多數(shù)計(jì)算問題中，僅要求操作在時(shí)間上是部分有序的。有些操作必須在其他操作之后執(zhí)行，另外有些操作卻可以并行地執(zhí)行。如圖3.2所

4、示，其先后次序是：I1先于P1和I2；P1先于O1、P2和I3；O1先于O2，P3部分有序使某些操作的并行執(zhí)行成為可能，如I2和P1，I3，P2與O1等操作的執(zhí)行可以在時(shí)間上互相重疊I1P1O1I2P2O2I3P3O3作業(yè)1圖3.2 并行計(jì)算的先后次序并發(fā)執(zhí)行的條件：達(dá)到封閉性和可再現(xiàn)性例：假設(shè)有兩個(gè)程序P1和P2，其工作過程如下：P1：XX1 P2： XX1 設(shè)C1、C2是共享內(nèi)存的雙處理機(jī)系統(tǒng)的兩個(gè)CPU。兩個(gè)寄存器R1和R2。其中P1在C1上運(yùn)行，P2在C2上運(yùn)行，則以下執(zhí)行順序在整個(gè)執(zhí)行過程中都有可能發(fā)生。并發(fā)執(zhí)行失去封閉性的原因是共享資源的影響，去掉這種影響就行了。如下例說明了并發(fā)環(huán)

5、境下程序執(zhí)行對封閉性和可再現(xiàn)性的影響。1）P1：R1X，R1R11，XR1（設(shè)X初值為0） P2： R2X， R2R21，XR2 兩個(gè)程序運(yùn)行后X的結(jié)果為1。2）P1：R1X，R1R11， XR1 P2： R2X， R2R21，XR2 兩個(gè)程序運(yùn)行后X的結(jié)果為2。 顯然，順序2的結(jié)果是正確的，而順序1產(chǎn)生錯(cuò)誤的原因在于X是一個(gè)不允許多個(gè)程序同時(shí)交叉使用的公共變量（變量即內(nèi)存的一個(gè)存儲單元）程序并發(fā)執(zhí)行的概念定義：一組在邏輯上互相獨(dú)立的程序或 程序段在執(zhí)行過程中，其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序的執(zhí)行尚未結(jié)束，另一個(gè)的執(zhí)行已經(jīng)開始。并發(fā)和并行的區(qū)別：并行執(zhí)行指多個(gè)程序在多個(gè)資源上按獨(dú)立的、

6、異步的速度執(zhí)行，程序之間的執(zhí)行互不影響。而并發(fā)則存在多個(gè)程序因共享同一資源而互相影響的現(xiàn)象。程序的并發(fā)執(zhí)行帶來的影響由于資源的有限性，多個(gè)程序在并發(fā)執(zhí)行的過程中必然會(huì)對有限的資源進(jìn)行競爭，從而破壞程序結(jié)果的封閉性和可再現(xiàn)性。3.1.2 進(jìn)程的定義一個(gè)具有獨(dú)立功能的程序?qū)σ粋€(gè)數(shù)據(jù)集在處理機(jī)上的一次動(dòng)態(tài)執(zhí)行過程。2. 進(jìn)程的特征動(dòng)態(tài)性：進(jìn)程具有動(dòng)態(tài)的地址空間（數(shù)量和內(nèi)容），地址空間上包括：代碼（指令執(zhí)行和CPU狀態(tài)的改變）數(shù)據(jù)（變量的生成和賦值）系統(tǒng)控制信息（進(jìn)程控制塊的生成和刪除）獨(dú)立性：各進(jìn)程的地址空間相互獨(dú)立，除非采用進(jìn)程間通信手段；并發(fā)性、異步性：虛擬結(jié)構(gòu)化：代碼段、數(shù)據(jù)段和核心段（在地址

7、空間中）；程序文件中通常也劃分了代碼段和數(shù)據(jù)段，而核心段通常就是OS核心（由各個(gè)進(jìn)程共享，包括各進(jìn)程的PCB）3. 進(jìn)程與程序的區(qū)別進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進(jìn)程是程序的執(zhí)行。通常進(jìn)程不可在計(jì)算機(jī)之間遷移；而程序通常對應(yīng)著文件、靜態(tài)和可以復(fù)制。進(jìn)程是暫時(shí)的，程序的永久的：進(jìn)程是一個(gè)狀態(tài)變化的過程，程序可長久保存。進(jìn)程與程序的組成不同：進(jìn)程的組成包括程序、數(shù)據(jù)和進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）。進(jìn)程與程序的對應(yīng)關(guān)系：通過多次執(zhí)行，一個(gè)程序可對應(yīng)多個(gè)進(jìn)程；通過調(diào)用關(guān)系，一個(gè)進(jìn)程可包括多個(gè)程序。4.進(jìn)程和作業(yè)的關(guān)系1、作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的實(shí)體，有可能全部位于外存，而進(jìn)程則

8、是完成用戶任務(wù)的執(zhí)行實(shí)體，總會(huì)有一部分位于內(nèi)存。2、一個(gè)作業(yè)可由多個(gè)進(jìn)程組成且至少包含一個(gè)進(jìn)程，反之不可。3、作業(yè)的概念只存在于批處理系統(tǒng)中。3.2 進(jìn)程描述及狀態(tài)轉(zhuǎn)換1進(jìn)程的結(jié)構(gòu)進(jìn)程都是由一系列操作（動(dòng)作）所組成，通過這些操作來完成其任務(wù)。因此，不同的進(jìn)程，其內(nèi)部操作也不相同。在操作系統(tǒng)中，描述一個(gè)進(jìn)程除了需要程序和私有數(shù)據(jù)之外，最主要的是需要一個(gè)與動(dòng)態(tài)過程相聯(lián)系的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)用來描述進(jìn)程的外部特性（名字、狀態(tài)等）以及與其他進(jìn)程的聯(lián)系（通信關(guān)系）等信息，該數(shù)據(jù)結(jié)構(gòu)稱為進(jìn)程控制塊（PCB，Process Control Block）。 PCB程序段私有數(shù)據(jù)塊圖3.5 進(jìn)程的結(jié)構(gòu)2進(jìn)程控

9、制塊PCB及組織方式（1）進(jìn)程控制塊PCB進(jìn)程控制塊跟蹤程序執(zhí)行過程中的狀態(tài)，它們表達(dá)了進(jìn)程在當(dāng)前時(shí)刻的狀態(tài)以及它與其他進(jìn)程和資源的關(guān)系。進(jìn)程控制塊是進(jìn)程存在的標(biāo)志，當(dāng)系統(tǒng)或父進(jìn)程創(chuàng)建一個(gè)進(jìn)程時(shí)，實(shí)際上就是為其建立一個(gè)進(jìn)程控制塊。進(jìn)程控制塊不但指出了進(jìn)程的名字，而且也標(biāo)志出程序和數(shù)據(jù)集合的物理位置 。進(jìn)程名當(dāng)前狀態(tài)優(yōu)先數(shù)現(xiàn)場保留區(qū)指示處于同一狀態(tài)進(jìn)程的鏈指針資源清單進(jìn)程起始地址家族關(guān)系其他圖3.6 進(jìn)程控制塊的基本內(nèi)容（2）進(jìn)程控制塊PCB的組織方式 1）線性表方式：不論進(jìn)程的狀態(tài)如何，將所有的PCB連續(xù)地存放在內(nèi)存的系統(tǒng)區(qū)。這種方式適用于系統(tǒng)中進(jìn)程數(shù)目不多的情況。 2）索引表方式：該方式是線

10、性表方式的改進(jìn)，系統(tǒng)按照進(jìn)程的狀態(tài)分別建立就緒索引表、阻塞索引表等。 3）鏈接表方式：系統(tǒng)按照進(jìn)程的狀態(tài)將進(jìn)程的PCB組成隊(duì)列，從而形成就緒隊(duì)列、阻塞隊(duì)列、運(yùn)行隊(duì)列等。 PCB的組織方式鏈表：同一狀態(tài)的進(jìn)程其PCB成一鏈表，多個(gè)狀態(tài)對應(yīng)多個(gè)不同的鏈表各狀態(tài)的進(jìn)程形成不同的鏈表：就緒鏈表、阻塞鏈表索引表：同一狀態(tài)的進(jìn)程歸入一個(gè)index表（由index指向PCB），多個(gè)狀態(tài)對應(yīng)多個(gè)不同的index表各狀態(tài)的進(jìn)行形成不同的索引表：就緒索引表、阻塞索引表進(jìn)程的狀態(tài)及轉(zhuǎn)換運(yùn)行狀態(tài)(Running)：占用處理機(jī)資源；處于此狀態(tài)的進(jìn)程的數(shù)目小于等于CPU的數(shù)目。在沒有其他進(jìn)程可以執(zhí)行時(shí)（如所有進(jìn)程都在阻塞

11、狀態(tài)），通常會(huì)自動(dòng)執(zhí)行系統(tǒng)的idle進(jìn)程（相當(dāng)于空操作）。就緒狀態(tài)(Ready)：進(jìn)程已獲得除處理機(jī)外的所需資源，等待分配處理機(jī)資源；只要分配CPU就可執(zhí)行?？梢园炊鄠€(gè)優(yōu)先級來劃分隊(duì)列，如：時(shí)間片用完低優(yōu)，I/O完成中優(yōu)，頁面調(diào)入完成高優(yōu)阻塞狀態(tài)(Blocked)：由于進(jìn)程等待某種條件（如I/O操作或進(jìn)程同步），在條件滿足之前無法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程，也無法運(yùn)行。如：等待I/O操作的完成。狀態(tài)的轉(zhuǎn)換運(yùn)行就緒阻塞進(jìn)程因某事件（如等待I/O完成）變成阻塞狀態(tài)某事件被解除（I/O完成）時(shí)間片已用完進(jìn)程調(diào)度程序把處理機(jī)分配給進(jìn)程（1）（2）（3）（4）狀態(tài)變化 ：（1）就緒狀

12、態(tài)變化到運(yùn)行狀態(tài) 。（2）運(yùn)行狀態(tài)變化到就緒狀態(tài)。 （3）運(yùn)行狀態(tài)變化到阻塞狀態(tài)。 （4）阻塞狀態(tài)變化到就緒狀態(tài)。 3.3 進(jìn)程控制3.3.1 原語3.4.2 進(jìn)程控制原語 返回3.3.1 原語的概念原語(primitive)：由若干條指令構(gòu)成的不可分割的最小程序運(yùn)行單位，只能在系統(tǒng)態(tài)下由系統(tǒng)調(diào)用來執(zhí)行。原語分為兩類： 1）機(jī)器指令級原語：執(zhí)行期間不允許中斷； 2）功能級原語：允許中斷但不允許并發(fā)執(zhí)行。3.3.2 進(jìn)程控制原語1創(chuàng)建原語2撤消原語3阻塞原語4喚醒原語1、創(chuàng)建原語1）作用：負(fù)責(zé)進(jìn)程的創(chuàng)建，被創(chuàng)建的進(jìn) 程處于就緒態(tài)。2）創(chuàng)建過程： a.查找空白PCB塊并填入相關(guān)參數(shù)； b.置進(jìn)程狀

13、態(tài)為就緒態(tài)并將其放入系統(tǒng) 就緒隊(duì)列末尾。2、撤銷原語1）作用：負(fù)責(zé)進(jìn)程的撤銷。2）進(jìn)程撤銷的條件： a.該進(jìn)程已完成其全部功能； b.進(jìn)程由于錯(cuò)誤而終止； c.祖先進(jìn)程要求撤銷某個(gè)子進(jìn)程。3）撤銷過程： a.回收進(jìn)程占用的所有資源； b.回收PCB塊。3、阻塞原語1）作用：完成運(yùn)行態(tài)向阻塞態(tài)的轉(zhuǎn)換。2）阻塞過程：a.產(chǎn)生中斷并保存被阻塞進(jìn)程的中斷現(xiàn)場。b.置被阻塞進(jìn)程狀態(tài)為阻塞態(tài)并放入阻塞隊(duì)列末尾。注意：阻塞原語只能由需要阻塞的進(jìn)程自己來調(diào)用(為什么?)。4、喚醒原語1）作用：完成阻塞態(tài)向就緒態(tài)的轉(zhuǎn)換。2）阻塞過程： a.完成被喚醒進(jìn)程的狀態(tài)轉(zhuǎn)換； b.將被喚醒進(jìn)程放入就緒隊(duì)列末尾。注意：可由

14、系統(tǒng)進(jìn)程或事件發(fā)生進(jìn)程來 進(jìn)行喚醒。3.4 進(jìn)程互斥3.4.1 進(jìn)程間的制約關(guān)系3.4.2臨界資源和臨界區(qū)3.4.3互斥的加鎖實(shí)現(xiàn)3.4.4 信號量(semaphore)3.4.5互斥的信號量實(shí)現(xiàn)3.4.6 進(jìn)程互斥舉例返回1 進(jìn)程間的制約關(guān)系某些進(jìn)程必須在另外某些進(jìn)程后運(yùn)行1）間接制約：處于并發(fā)狀態(tài)的多個(gè)進(jìn)程由于要共享某個(gè)獨(dú)享型資源而產(chǎn)生的執(zhí)行速度的制約。2）直接制約：處于并發(fā)狀態(tài)的多個(gè)進(jìn)程要完成同一個(gè)任務(wù)，由于各個(gè)進(jìn)程之間的協(xié)同合作而產(chǎn)生的制約。3）產(chǎn)生制約的原因： a.資源共享 b.進(jìn)程合作實(shí)例： a.有進(jìn)程p1、p2、p3都需要打印機(jī)，而 系統(tǒng)只有一臺，由此產(chǎn)生間接制約。 b.有一計(jì)算

15、任務(wù)：（ab）（cd）， 其中：p1完成ab，p2完成cd，p3 完成p1p2，由此產(chǎn)生直接制約。2 臨界資源和臨界區(qū)1）臨界資源：一次僅允許一個(gè)進(jìn)程使用 的資源。2）臨界區(qū)：訪問臨界資源的程序段或不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序。3）臨界區(qū)設(shè)計(jì)原則： a.每次至多允許一個(gè)進(jìn)程位于臨界區(qū)； b.若有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū)，應(yīng)在有限 時(shí)間內(nèi)選擇一個(gè)進(jìn)入。 c.進(jìn)程在臨界區(qū)內(nèi)只能停留一定的時(shí)間。 3 互斥的加鎖實(shí)現(xiàn)1）進(jìn)程互斥：當(dāng)一個(gè)進(jìn)程正在使用臨界資源且尚未使用完畢時(shí)，則其他進(jìn)程必須推遲對該資源的進(jìn)一步操作，在當(dāng)前進(jìn)程的使用完成之前，不能從中插進(jìn)去使用這個(gè)臨界資源?；颍簝蓚€(gè)并發(fā)的進(jìn)程A、B，

16、如果當(dāng)A進(jìn)行某個(gè)操作時(shí)，B不能做這一操作，進(jìn)程間的這種限制條件稱為進(jìn)程互斥。定義:不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)2）互斥的加鎖實(shí)現(xiàn)：lock和unlock大部分同步方案均采用某個(gè)物理實(shí)體（如鎖、信號燈等）實(shí)現(xiàn)通信，進(jìn)程通信原語中關(guān)鎖（lock）和開鎖（unlock）是最簡單的原語。在這兩個(gè)原語中設(shè)置一個(gè)公共變量x代表某個(gè)臨界資源的狀態(tài)。如：x=0，表示資源可用，x=1，表示資源正在使用。關(guān)鎖原語1ock（x）： L：if x1 then goto L else x：=1；開鎖原語unlock（x）： x：=0；圖3.7 開鎖和關(guān)鎖程序流程圖硬件方法的優(yōu)點(diǎn)適用于任意數(shù)目的進(jìn)程

17、，在單處理器或多處理器上簡單，容易驗(yàn)證其正確性可以支持進(jìn)程內(nèi)存在多個(gè)臨界區(qū)，只需為每個(gè)臨界區(qū)設(shè)立一個(gè)布爾變量硬件方法的缺點(diǎn)等待要耗費(fèi)CPU時(shí)間，不能實(shí)現(xiàn)讓權(quán)等待可能饑餓：從等待進(jìn)程中隨機(jī)選擇一個(gè)進(jìn)入臨界區(qū)，有的進(jìn)程可能一直選不上可能死鎖4 信號量(semaphore)前面的互斥算法都存在問題，它們是平等進(jìn)程間的一種協(xié)商機(jī)制，需要一個(gè)地位高于進(jìn)程的管理者來解決公有資源的使用問題。OS可從進(jìn)程管理者的角度來處理互斥的問題，信號量就是OS提供的管理公有資源的有效手段。信號量代表某類可用資源實(shí)體的數(shù)量。 信號量和P、V原語1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語的test(p

18、roberen)和increment(verhogen)），是一種卓有成效的進(jìn)程同步機(jī)制。信號量：在操作系統(tǒng)中代表可用資源的數(shù)目，是一個(gè)整形變量，其值只能通過P、V原語改變。分類：1）公用信號量：初值為1，用于進(jìn)程互斥，值域?yàn)?（n1），n為需互斥的進(jìn)程的個(gè)數(shù)； 2）私用信號量：初值為0或正整數(shù)n，用于進(jìn)程同步，值域范圍較公用信號量寬。 P原語wait(s)-s.count;/表示申請一個(gè)資源;if (s.count 0)/表示沒有空閑資源; 調(diào)用進(jìn)程進(jìn)入等待隊(duì)列s.queue; 阻塞調(diào)用進(jìn)程;P原語的執(zhí)行過程每執(zhí)行一次P（S）原語操作，信號量S的值減1，然后由OS判定S的值。若S0則進(jìn)程繼續(xù)

19、執(zhí)行，進(jìn)入臨界區(qū)；若S0則阻塞該進(jìn)程，把它插入該信號量的進(jìn)程等待隊(duì)列末尾。V原語signal(s)+s.count;/表示釋放一個(gè)資源；if (s.count 0則進(jìn)程繼續(xù)執(zhí)行；若S0則從該信號量等待隊(duì)列的隊(duì)首移出一個(gè)進(jìn)程，把它插入進(jìn)程就緒隊(duì)列末尾，等待處理機(jī)調(diào)度。P、V原語的物理意義（1）S0時(shí)的數(shù)值表示系統(tǒng)中某類可用 資源的數(shù)量。執(zhí)行一次P原語意味 著進(jìn)程請求分配一個(gè)資源；當(dāng)Sbuf1;V(S2); PB:P(S2);P(S3);Buf1-buf2;V(S1);V(S4);PC:P(S4);BUF2-PRINTER;V(S3);有編程要求：X=ABC/D； 其中：P1完成AB ，P2完成C

20、/D ，P3 完成P1P2，試用信號量方法完成這3個(gè)函數(shù)間制約關(guān)系的描述。分析:P3與P1、P2之間屬于直接制約。信號量設(shè)計(jì)：S1用于描述P1的事件是否產(chǎn)生 初值為0； S2用于描述P2的事件是否產(chǎn)生， 初值為0；P1:計(jì)算；V（）；P:計(jì)算；V（）；P:P（S1）；P（S2）；計(jì)算；生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個(gè)箱子里，現(xiàn)要用自動(dòng)分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個(gè)并發(fā)執(zhí)行的進(jìn)程組成，功能如下：（1）進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；（2）每個(gè)進(jìn)程每次只揀一個(gè)子，當(dāng)一個(gè)進(jìn)程在揀子時(shí)不允許另一個(gè)進(jìn)程去揀子。分析：第一步：確定進(jìn)程間的關(guān)系。由功能（2）可知進(jìn)程之間是互斥

21、的關(guān)系。第二步：確定信號量及其值。由于進(jìn)程A和進(jìn)程B要互斥進(jìn)入箱子去揀棋子，箱子是兩個(gè)進(jìn)程的公有資源，所以設(shè)置一個(gè)信號量s，其值取決于公有資源的數(shù)目，由于箱子只有一個(gè)，s的初值就設(shè)為1。begin s:semaphore; s:=1; cobegin process A begin L1: P(s); 揀黑子； V(s); goto L1; end; process B begin L2:P(s); 揀白子； V(s); goto L2; end; coend; end;在上例的基礎(chǔ)之上再添加一個(gè)功能（3）當(dāng)一個(gè)進(jìn)程A揀了一個(gè)棋子（黑子）以后，必讓另一個(gè)進(jìn)程B揀一個(gè)棋子（白子）。分析：第一步：

22、確定進(jìn)程間的關(guān)系。由功能（1）（2）（3）可知，進(jìn)程間的關(guān)系為同步關(guān)系。第二步：確定信號量及其值。進(jìn)程A和B共享箱子這個(gè)公有資源，但規(guī)定兩個(gè)進(jìn)程必須輪流去取不同色的棋子，因而相互間要互通消息。對于進(jìn)程A可設(shè)置一個(gè)私有信號量s1，該私有信號量用于判斷進(jìn)程A是否能去揀黑子，初值為1。對于進(jìn)程B同樣設(shè)置一個(gè)私有信號量s2，該私有信號量用于判斷進(jìn)程B是否能去揀白子，初值為0。當(dāng)然也可以設(shè)置s1初值為0，s2初值為1。PA： P（S1）； 揀黑子；V（S2）；PB： P（S2）； 揀白子； V（S1）；在公共汽車上，司機(jī)和售票員的活動(dòng)分別是：司機(jī)：啟動(dòng)車輛，正常行車，到站停車。售票員：上乘客，關(guān)車門，售

23、票，開車門，下乘客。用PV操作對其控制。 分析：第一步：確定進(jìn)程間的關(guān)系。司機(jī)到站停車后，售票員方可工作。同樣，售票員關(guān)車門后，司機(jī)才能工作。所以司機(jī)與售票員之間是一種同步關(guān)系。第二步：確定信號量及其值。由于司機(jī)與售票員之間要互通消息，司機(jī)進(jìn)程設(shè)置一個(gè)私有信號量run，用于判斷司機(jī)能否進(jìn)行工作，初值為0。售票員進(jìn)程設(shè)置一個(gè)私有信號量stop，用于判斷是否停車，售票員是否能夠開車門，初值為0。 L1: P(run);啟動(dòng)車輛；正常行車；到站停車；V(stop); L2:上乘客；關(guān)車門； V(run); 售票； P(stop); 開車門； 下乘客；有四個(gè)進(jìn)程R1，R2，W1，W2，它們共享可以存放

24、一個(gè)數(shù)的緩沖器B。進(jìn)程R1每次把從鍵盤上讀出的一個(gè)數(shù)存到緩沖器B中，供進(jìn)程W1打印輸出；進(jìn)程R2每次從磁盤上讀一個(gè)數(shù)存放到緩沖器B中，供進(jìn)程W2打印輸出。為防止數(shù)據(jù)的丟失和重復(fù)打印，問怎樣用PV操作來協(xié)調(diào)這四個(gè)進(jìn)程的并發(fā)執(zhí)行。分析：進(jìn)程R1和R2各自生產(chǎn)不同的產(chǎn)品要存入共享的緩沖器B中，由于B中每次只能存入一個(gè)數(shù)，因此，進(jìn)程R1和R2在存數(shù)時(shí)必須互斥。進(jìn)程R1和R2在把數(shù)存入B中后應(yīng)分別發(fā)送消息通知進(jìn)程W1和W2；進(jìn)程W1和W2在取出數(shù)之后應(yīng)發(fā)出緩沖器B中又允許存放一個(gè)新數(shù)的消息。故進(jìn)程R1與W1、進(jìn)程R2與W2之間要同步。信號量：首先應(yīng)定義一個(gè)是否允許進(jìn)程R1或R2存入緩沖器B的信號量S，初

25、值為“1”；其次，進(jìn)程R1和R2分別要向進(jìn)程W1和W2發(fā)送消息，要有兩個(gè)信號量S1和S2來表示相應(yīng)的消息，初值為“0”。然后進(jìn)程W1或W2在取出緩沖器B中的數(shù)之后只需發(fā)出“允許存放一個(gè)新數(shù)”的消息，通過調(diào)用V（S）即可，不必增加新的信號量。R1：P（S）;Data-B;V(S1);R2：P（S）；Data-B;V(S2);W1：P（S1）；B-data;V(S);W2：P（S2）；B-data;V(S);4.5 進(jìn)程間通信(IPC, INTER-PROCESS COMMUNICATION)4.5.0 進(jìn)程間通信的類型4.5.1 信號(signal)4.5.2 共享存儲區(qū)(shared memo

26、ry)4.5.3 管道(pipe)4.5.4 消息(message)4.5.5 套接字(socket)返回4.5.0 進(jìn)程間通信的類型低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進(jìn)程互斥和同步所采用的信號量和管程機(jī)制。優(yōu)點(diǎn)的速度快。缺點(diǎn)是：傳送信息量?。盒实?，每次通信傳遞的信息量固定，若傳遞較多信息則需要進(jìn)行多次通信。編程復(fù)雜：用戶直接實(shí)現(xiàn)通信的細(xì)節(jié)，編程復(fù)雜，容易出錯(cuò)。高級通信：能夠傳送任意數(shù)量的數(shù)據(jù)，包括三類：共享存儲區(qū)、管道、消息。返回1. 低級通信和高級通信2. 直接通信和間接通信直接通信：信息直接傳遞給接收方，如管道。在發(fā)送時(shí)，指定接收方的地址或標(biāo)識，也可以指定多個(gè)接收方或廣播

27、式地址；在接收時(shí)，允許接收來自任意發(fā)送方的消息，并在讀出消息的同時(shí)獲取發(fā)送方的地址。間接通信：借助于收發(fā)雙方進(jìn)程之外的共享數(shù)據(jù)結(jié)構(gòu)作為通信中轉(zhuǎn)，如消息隊(duì)列。通常收方和發(fā)方的數(shù)目可以是任意的。3. 高級通信的特征通信鏈路(communication link)：點(diǎn)對點(diǎn)/多點(diǎn)/廣播單向/雙向有容量（鏈路帶緩沖區(qū)）/無容量（發(fā)送方和接收方需自備緩沖區(qū)）數(shù)據(jù)格式：字節(jié)流(byte stream)：各次發(fā)送之間的分界，在接收時(shí)不被保留，沒有格式；報(bào)文(datagram/message)：各次發(fā)送之間的分界，在接收時(shí)被保留，通常有格式（如表示類型），定長/不定長報(bào)文，可靠報(bào)文/不可靠報(bào)文。收發(fā)操作的同步方

28、式發(fā)送阻塞（直到被鏈路容量或接收方所接受）和不阻塞（失敗時(shí)立即返回）接收阻塞（直到有數(shù)據(jù)可讀）和不阻塞（無數(shù)據(jù)時(shí)立即返回）由事件驅(qū)動(dòng)收發(fā)：在允許發(fā)送或有數(shù)據(jù)可讀時(shí)，才做發(fā)送和接收操作4.6 死鎖問題(DEADLOCK)4.6.1 概述4.6.2 死鎖的預(yù)防4.6.2 死鎖的檢測4.6.3 死鎖的避免4.6.4 解決死鎖問題的綜合方法返回1 死鎖產(chǎn)生的原因和必要條件在許多中型和大型計(jì)算機(jī)系統(tǒng)中，都期望在各級系統(tǒng)和用戶程序上具有動(dòng)態(tài)共享資源、并發(fā)程序設(shè)計(jì)及進(jìn)程通信這些操作特征，來改善系統(tǒng)資源的利用率和提高系統(tǒng)的處理能力。由于資源的占用往往是互斥的，因此當(dāng)某個(gè)進(jìn)程提出申請資源后，使得有關(guān)進(jìn)程在無外力

29、協(xié)助下，永遠(yuǎn)分配不到必需的資源而無法繼續(xù)運(yùn)行，這就產(chǎn)生了一種特殊的現(xiàn)象死鎖。 死鎖的定義死鎖是指計(jì)算機(jī)系統(tǒng)或進(jìn)程所處的一種狀態(tài),即兩個(gè)或多個(gè)進(jìn)程無限期地等待永遠(yuǎn)不會(huì)發(fā)生的條件。先來看一個(gè)申請不同類型資源的死鎖例子，假定有兩個(gè)進(jìn)程Pl和P2都要修改文件F，修改時(shí)都需要一條暫時(shí)存放信息的磁帶，而只有一臺磁帶機(jī)T可用。又假定由于某種原因，在進(jìn)行修改之前，P2需要一暫存磁帶（例如為了修改，要重新組織輸入數(shù)據(jù)）。設(shè)F和T都是可重用資源，它們分別表示允許更新文件和允許使用磁帶機(jī)。于是Pl和P2可有如下形式： 進(jìn)程P1 進(jìn)程P2 ： ： 申請文件F 申請磁帶機(jī)T r1：申請磁帶機(jī)T r2：申請文件F 釋放磁

30、帶機(jī)T 釋放文件F 釋放文件F 釋放磁帶機(jī)T TFP1P2請 求 配分已請 求 配 分已圖3.13 簡單的死鎖例子R P1P2P3 分配 申請圖3.14 同類資源共享時(shí)的死鎖現(xiàn)象由以上諸例子可知，產(chǎn)生死鎖現(xiàn)象的原因，一是系統(tǒng)提供的資源不能滿足每個(gè)進(jìn)程的使用，即系統(tǒng)資源不足；二是在多道程序運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合理，即進(jìn)程推進(jìn)順序非法。死鎖的必要條件：（1）互斥條件。 （2）不剝奪條件。 （3）請求和保持條件。 （4）環(huán)路等待條件。 解決死鎖問題的策略1利用假脫機(jī)技術(shù)，變獨(dú)享資源為共享資源；2采用可剝奪的資源使用方式；3采用資源的預(yù)先全部分配方式；4. 采用有控資源分配方法。死鎖的預(yù)防1、資源預(yù)

31、分配法 每個(gè)用戶向系統(tǒng)提交作業(yè)時(shí)，需一次性說明所需要的資源；并且作業(yè)調(diào)度程序只能在滿足作業(yè)所需的全部資源的前提下才能將它投入運(yùn)行。 當(dāng)資源一旦分配給該作業(yè)后，在其整個(gè)運(yùn)行期間這些資源為它獨(dú)占。資源預(yù)分配法的缺點(diǎn)1、用戶在作業(yè)運(yùn)行前可能不能提出該作業(yè)運(yùn)行所需的全部資源；2、資源利用率很低；3、作業(yè)等待時(shí)間較長；4、系統(tǒng)吞吐量很低；死鎖預(yù)防方法22、有序資源分配法 該方法給系統(tǒng)中所有資源給定一個(gè)唯一的編號，所有的分配請求必須以上升的次序進(jìn)行，系統(tǒng)要求每個(gè)進(jìn)程： 1）對它所必須使用的而且屬于同一類的所有資源，必須一次申請完； 2）在申請不同類的資源時(shí)，必須按各類資源的編號依次請求。死鎖預(yù)防方法3銀行

32、家算法 該算法在有進(jìn)程提出資源分配請求時(shí)，首先檢查申請者對各類資源的最大需求量，如果系統(tǒng)現(xiàn)存的各類資源可以滿足當(dāng)前它對各類資源的最大需求量時(shí)，就滿足它的請求。 即：僅當(dāng)申請者可以在一定時(shí)間內(nèi)無條件地歸還它所申請的全部資源時(shí)，才能將資源分配給它。銀行家算法示例假設(shè)系統(tǒng)有三個(gè)進(jìn)程p，q，r，系統(tǒng)只具有某類資源10個(gè)，目前分配情況如下： 進(jìn)程 已占資源個(gè)數(shù) 還需資源個(gè)數(shù) p 4 4 q 2 2 r 2 7 此時(shí)，p，r再申請資源系統(tǒng)就不能進(jìn)行分配了，因?yàn)槟壳爸皇Ｏ?個(gè)資源，不能滿足它們的最大需求，如果將剩余2個(gè)資源分配給p或r，就會(huì)形成： 進(jìn)程 已占資源個(gè)數(shù) 還需資源個(gè)數(shù) p 4 或5或6 4或3或

33、2 q 2 2 r 2 或3或4 7或6或5 此后，3個(gè)進(jìn)程再提出資源請求系統(tǒng)就無法滿足了，結(jié)果就產(chǎn)生了死鎖。 而如果等q提出請求卻可以滿足它，因?yàn)樗恍枰?個(gè)資源就可運(yùn)行結(jié)束，系統(tǒng)此時(shí)能夠滿足它的最大需求。等它運(yùn)行結(jié)束后就能滿足p的最大要求對p進(jìn)行分配。最后再對r進(jìn)行分配，這樣就不會(huì)產(chǎn)生死鎖。銀行家算法的數(shù)據(jù)結(jié)構(gòu)包括：可用資源向量Available 最大需求矩陣Max分配矩陣Allocation需求矩陣Need 銀行家算法如下：設(shè)Requesti是進(jìn)程Pi的請求向量，Requesti (j)=k表示進(jìn)程Pi請求分配Rj類資源k個(gè)，當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按照下列步驟進(jìn)行檢查。（1）若Req

34、uestiNeed，則執(zhí)行步驟（2）；否則系統(tǒng)會(huì)因?yàn)樗枰馁Y源數(shù)已超過它要求的最大值而認(rèn)為出錯(cuò)。（2）若RequestiAvailable，則執(zhí)行步驟（3）；否則系統(tǒng)會(huì)因?yàn)橄到y(tǒng)中尚無足夠的資源滿足Pi的申請而使進(jìn)程Pi等待。（3）系統(tǒng)試探地把資源分配給進(jìn)程Pi并修改如下數(shù)據(jù)結(jié)構(gòu)中的值：Available=Available-RequestiAllocationi=Allocationi+RequestiNeedi=Needi-Requesti（4）系統(tǒng)執(zhí)行安全算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若是則系統(tǒng)才真正將資源分配給進(jìn)程Pi以完成本次分配；若不是則系統(tǒng)將試探分配其他進(jìn)程。

35、系統(tǒng)所執(zhí)行的安全性算法描述如下： （1）設(shè)置兩個(gè)向量：Work和Finish。 （2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finish(i)=false NeediWork（3）當(dāng)進(jìn)程Pi獲得資源后可順利執(zhí)行直到完成，然后釋放分配給它的資源，并作如下工作： Work=Work+Allocation Finish(i)=true（4）若所有進(jìn)程的Finish(i)的值都為true，則說明系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)。銀行家算法實(shí)例1、假定系統(tǒng)中有5個(gè)進(jìn)程P0，P1，P2，P3，P4和三種類型的資源A，B，C，每一種資源的數(shù)量分別為10、5、7，在T時(shí)刻的資源分配情況如下：已分

36、配的資源數(shù)尚需的資源數(shù)系統(tǒng)T時(shí)刻剩余資源數(shù)ABCABCABCp00 10743332p1200122p2302600p3211011p4002431試問：（1）T時(shí)刻的狀態(tài)是否安全，并說明原因； （2）如果進(jìn)程P1提出請求Request1(1，0，2)，請說明系統(tǒng)能否將資源分配給它？ （3）如果進(jìn)程P4提出請求Request4(3，3，0)，請說明系統(tǒng)能否將資源分配給它？ 死鎖的解除（1）資源剝奪法。1）還原算法。即恢復(fù)計(jì)算結(jié)果和狀態(tài)。2）建立檢查點(diǎn)主要是用來恢復(fù)分配前的狀態(tài)。 （2）撤消進(jìn)程法。1）程序的優(yōu)先數(shù)，即被撤消進(jìn)程的優(yōu)先數(shù)。2）作業(yè)類的外部代價(jià) 3）運(yùn)行代價(jià)，即重新啟動(dòng)它并運(yùn)行到當(dāng)

37、前撤消點(diǎn)所需要的代價(jià)。 哲學(xué)家就餐問題有5個(gè)哲學(xué)家P1,P2,P3,P4 ,P5圍坐在一張圓桌旁，桌中央有一盤通心面，每人面前有一個(gè)空盤子 ，另有5把叉子f1，f2,f3,f4,f5分別放在兩人之間，如圖7.5所示。每個(gè)哲學(xué)家做兩件事:思考問題和吃通心面 ，當(dāng)思考問題時(shí)放下叉子，想吃通心面時(shí)，必須獲得2把叉子 ，且每人只能直接從自己的左右兩邊取叉子，吃過后放下叉子以便別人使用。 方法一void philosopher(int i)while (TRUE) think( );take_fork(i);take_fork(i+1) % N);eat( );put_fork(i);put_fork(

38、i+1) % N);分析：當(dāng)出現(xiàn)以下情形，在某一個(gè)瞬間，所有的哲學(xué)家都同時(shí)啟動(dòng)這個(gè)算法，拿起左側(cè)的筷子，而看到右側(cè)筷子不可用，又都放下左側(cè)筷子，等一會(huì)兒，又同時(shí)拿起左側(cè)筷子如此這樣永遠(yuǎn)重復(fù)下去。對于這種情況，所有的程序都在運(yùn)行，但卻無法取得進(jìn)展，即出現(xiàn)饑餓，所有的哲學(xué)家都吃不上飯。 方法二原理：至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐,以保證至少有一個(gè)哲學(xué)家能夠進(jìn)餐,最終總會(huì)釋放出他所使用過的兩支筷子,從而可使更多的哲學(xué)家進(jìn)餐。以下將room 作為信號量，只允許4 個(gè)哲學(xué)家同時(shí)進(jìn)入餐廳就餐，這樣就能保證至少有一個(gè)哲學(xué)家可以就餐，而申請進(jìn)入餐廳的哲學(xué)家進(jìn)入room 的等待隊(duì)列，根據(jù)FIFO 的原則，總會(huì)進(jìn)入

39、到餐廳就餐，因此不會(huì)出現(xiàn)餓死和死鎖的現(xiàn)象。semaphore chopstick5=1，1，1，1，1;semaphore room=4;void philosopher(int i)while(true)think();wait(room); /請求進(jìn)入房間進(jìn)餐wait(chopsticki); /請求左手邊的筷子wait(chopstick(i+1)%5); /請求右手邊筷子eat();signal(chopstick(i+1)%5); /釋放右手邊的筷子signal(chopsticki); /釋放左手邊的筷子signal(room); /退出房間釋放信號量room方法三原理：僅當(dāng)哲學(xué)家的左右兩支筷子都可用時(shí),才允許他拿起筷子進(jìn)餐。方法1：利用AND 型信號量機(jī)