進(jìn)程管理1課件

第3章

進(jìn)程管理3.1引言3.2進(jìn)程的引入和定義3.3進(jìn)程的狀態(tài)和進(jìn)程控制塊3.4進(jìn)程控制3.5線程的基本概念3.6進(jìn)程調(diào)度3.7進(jìn)程通信3.8死鎖問題本章學(xué)習(xí)目標(biāo)進(jìn)程的概念進(jìn)程的實(shí)體、狀態(tài)及狀態(tài)的演變進(jìn)程的控制與調(diào)度進(jìn)程之間的關(guān)系協(xié)調(diào)進(jìn)程的通信死鎖問題及解決3.1引言處理機(jī)管理是操作系統(tǒng)的基本管理功能之一，它所關(guān)心的是處理機(jī)的分配問題。也就是說把CPU（中央處理機(jī)）的使用權(quán)分給某個程序，通常把這個正準(zhǔn)備進(jìn)入內(nèi)存的程序稱為作業(yè)，當(dāng)這個作業(yè)進(jìn)入內(nèi)存后我們把它稱為進(jìn)程。處理機(jī)管理分為作業(yè)管理和進(jìn)程管理兩個階段去實(shí)現(xiàn)處理機(jī)的分配，常常又把直接實(shí)行處理機(jī)時(shí)間分配的進(jìn)程調(diào)度工作作為處理機(jī)管理的主要內(nèi)容。

進(jìn)程管理的主要功能是把處理機(jī)分配給進(jìn)程以及協(xié)調(diào)各個進(jìn)程之間的相互關(guān)系。它是由進(jìn)程調(diào)度程序和進(jìn)程控制（控制進(jìn)程狀態(tài)轉(zhuǎn)換）程序這兩部分內(nèi)容組成的。

返回首頁3.2進(jìn)程的引入和定義3.2.1進(jìn)程的引入3.2.2進(jìn)程的定義

返回首頁3.2.1進(jìn)程的引入1．程序的順序執(zhí)行及其特性2．資源共享3．程序的并發(fā)執(zhí)行及其特性1．程序的順序執(zhí)行及其特性圖3.1表示每次僅能調(diào)度一個用戶作業(yè)進(jìn)行操作的先后次序。輸入、計(jì)算和打印輸出工作只能串行執(zhí)行，我們可以把程序的執(zhí)行過程看作是一系列狀態(tài)轉(zhuǎn)變過程，每執(zhí)行一個操作，系統(tǒng)就從一種狀態(tài)變成另一種狀態(tài)。圖中I表示輸入操作，P表示處理操作，O表示輸出操作。圖3.1順序處理操作的先后次序由上述順序程序的執(zhí)行情況可以看出，一切順序執(zhí)行的程序都具有下列特性：（1）順序性。程序在處理機(jī)上執(zhí)行時(shí)，其操作只能嚴(yán)格地按照所規(guī)定的順序執(zhí)行，后繼操作只有在前一操作執(zhí)行完畢之后方能執(zhí)行，否則就會發(fā)生程序邏輯錯誤。（2）資源獨(dú)占。程序在執(zhí)行過程中獨(dú)占全部資源，資源狀態(tài)的改變只與程序本身有關(guān)，而與外界環(huán)境無關(guān)。（3）結(jié)果的無關(guān)性。第一，指程序執(zhí)行的結(jié)果與其執(zhí)行速度無關(guān)。第二，是指只要程序的初始條件不變，當(dāng)重復(fù)執(zhí)行時(shí)，一定能得到相同的結(jié)果。2．資源共享操作系統(tǒng)是用來實(shí)現(xiàn)對計(jì)算機(jī)資源進(jìn)行管理的一個大型系統(tǒng)程序，其基本特征之一就是資源共享。這里的資源就是指計(jì)算機(jī)處理一個任務(wù)或一個作業(yè)時(shí)的所有硬設(shè)備（處理機(jī)、內(nèi)存、外存、輸入/輸出設(shè)備等）和軟設(shè)備（文件、程序、數(shù)據(jù)、信息等）的總稱。所謂資源共享，就是指計(jì)算機(jī)中并發(fā)執(zhí)行的多個程序交替使用計(jì)算機(jī)硬件和軟件資源。操作系統(tǒng)提供了兩種實(shí)現(xiàn)資源共享的方法。（1）由操作系統(tǒng)統(tǒng)一管理和分配。（2）由進(jìn)程自行使用。

I1P1O1I2P2O2I3P3O3作業(yè)1圖3.2并行計(jì)算的先后次序3．程序的并發(fā)執(zhí)行及其特性在大多數(shù)計(jì)算問題中，僅要求操作在時(shí)間上是部分有序的。有些操作必須在其他操作之后執(zhí)行，另外有些操作卻可以并行地執(zhí)行。如圖3.2所示，其先后次序是：I1先于P1和I2；P1先于O1、P2和I3；O1先于O2，P3……部分有序使某些操作的并行執(zhí)行成為可能，如I2和P1，I3，P2與O1等操作的執(zhí)行可以在時(shí)間上互相重疊。通常，程序的制約方式有如下兩種。（1）間接制約方式。（2）直接制約方式。無論是操作系統(tǒng)自身的程序還是用戶程序，通常總是存在一些相對獨(dú)立、但又能并發(fā)執(zhí)行的程序段。

為了合理利用系統(tǒng)資源，更好地發(fā)揮各種資源的效益，使各種物理設(shè)備之間的時(shí)間性限制條件減少到最低限度，最大限度地提高系統(tǒng)的效率，因而引出了多道程序方法。其實(shí)質(zhì)是減少程序的順序性，提高系統(tǒng)的并行性。

返回本節(jié)3.2.2進(jìn)程的定義。進(jìn)程是現(xiàn)代操作系統(tǒng)的一個基本概念，是并發(fā)程序出現(xiàn)后出現(xiàn)的一個重要概念，它是指程序在一個數(shù)據(jù)集合上運(yùn)行的過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度運(yùn)行的一個獨(dú)立單位，有時(shí)也稱為活動、路徑或任務(wù)。進(jìn)程，作為程序執(zhí)行的過程，至少有兩個方面的性質(zhì)：一是它的活動性，即進(jìn)程是動態(tài)變化的，且總有一個從創(chuàng)建到消亡的過程；二是它的并發(fā)性，即多道程序中每個進(jìn)程的執(zhí)行過程，總是與其他執(zhí)行過程并發(fā)執(zhí)行的。

進(jìn)程與程序的區(qū)別和相互關(guān)系：（1）動態(tài)性和靜態(tài)性。

（2）從結(jié)構(gòu)上看每個進(jìn)程的實(shí)體都是由程序段和相應(yīng)的數(shù)據(jù)段兩部分構(gòu)成的，這一特征與程序的含義相近。

（3）一個進(jìn)程可以涉及到一個或幾個程序的執(zhí)行。（4）并發(fā)性。

（5）進(jìn)程具有創(chuàng)建其他進(jìn)程的功能。

（6）操作系統(tǒng)中的每一個程序都是在一個進(jìn)程現(xiàn)場中運(yùn)行的。

進(jìn)程通常分為兩類，一類是系統(tǒng)進(jìn)程，另一類是用戶進(jìn)程。它們的區(qū)別是：（1）系統(tǒng)進(jìn)程是操作系統(tǒng)用來管理系統(tǒng)資源并行活動的并發(fā)軟件。

（2）系統(tǒng)進(jìn)程之間的關(guān)系由操作系統(tǒng)自己負(fù)責(zé)。

（3）系統(tǒng)進(jìn)程直接管理有關(guān)的軟、硬設(shè)備的活動。（4）在進(jìn)程調(diào)度中，系統(tǒng)進(jìn)程的優(yōu)先級高于用戶進(jìn)程。

返回本節(jié)3.3進(jìn)程的狀態(tài)和進(jìn)程控制塊3.3.1進(jìn)程的狀態(tài)及狀態(tài)變化圖3.3.2進(jìn)程的結(jié)構(gòu)、進(jìn)程控制塊及組織方式

返回首頁3.3.1進(jìn)程的狀態(tài)及狀態(tài)變化圖（1）運(yùn)行狀態(tài)：進(jìn)程正在處理機(jī)上運(yùn)行的狀態(tài)，該進(jìn)程已獲得必要的資源，也獲得了處理機(jī)，用戶程序正在處理機(jī)上運(yùn)行。（2）阻塞狀態(tài)：進(jìn)程等待某種事件完成（例如，等待輸入/輸出操作的完成）而暫時(shí)不能運(yùn)行的狀態(tài)，處于該狀態(tài)的進(jìn)程不能參加競爭處理機(jī)，此時(shí)，即使分配給它處理機(jī)，它也不能運(yùn)行。（3）就緒狀態(tài)：該進(jìn)程運(yùn)行所需的一切條件都得到滿足，但因處理機(jī)資源個數(shù)少于進(jìn)程個數(shù)，所以該進(jìn)程不能運(yùn)行，而必須等待分配處理機(jī)資源，一旦獲得處理機(jī)就立即投入運(yùn)行。運(yùn)行就緒阻塞進(jìn)程因某事件（如等待I/O完成）變成阻塞狀態(tài)某事件被解除

（I/O完成）時(shí)間片已用完進(jìn)程調(diào)度程序把處理機(jī)分配給進(jìn)程（1）（2）（3）（4）圖3.3典型的進(jìn)程狀態(tài)演變圖在具有掛起和激活的系統(tǒng)中，又增加了兩種基本的進(jìn)程狀態(tài)：靜止就緒和靜止阻塞。

（1）靜止就緒：它是活動就緒進(jìn)程由其自身或其他進(jìn)程調(diào)用掛起原語而進(jìn)入的一種狀態(tài)。處于靜止就緒狀態(tài)的進(jìn)程沒有資格爭用CPU，只有其他進(jìn)程調(diào)用激活原語將其激活才行。（2）靜止阻塞：它是活動阻塞進(jìn)程由其自身或其他進(jìn)程調(diào)用掛起原語而進(jìn)入的一種狀態(tài)。處于靜止阻塞狀態(tài)的進(jìn)程，在其掛起期間并不影響其等待事件的發(fā)生。圖3.4是具有靜止?fàn)顟B(tài)的進(jìn)程狀態(tài)變遷圖。運(yùn)行活動就緒活動阻塞進(jìn)程因某事件（如等待I/O完成）變成阻塞狀態(tài)某事件被解除（如I/O完成）時(shí)間片已用完進(jìn)程調(diào)度程序把處理機(jī)分配給進(jìn)程靜止阻塞靜止就緒掛起掛起激活激活某事件被解除（如I/O完成）創(chuàng)建圖3.4具有靜止?fàn)顟B(tài)的進(jìn)程狀態(tài)變遷圖返回本節(jié)3.3.2進(jìn)程的結(jié)構(gòu)、進(jìn)程控制塊及組織方式1．進(jìn)程的結(jié)構(gòu)進(jìn)程都是由一系列操作（動作）所組成，通過這些操作來完成其任務(wù)。因此，不同的進(jìn)程，其內(nèi)部操作也不相同。在操作系統(tǒng)中，描述一個進(jìn)程除了需要程序和私有數(shù)據(jù)之外，最主要的是需要一個與動態(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，ProcessControlBlock）。PCB程序段私有數(shù)據(jù)塊圖3.5進(jìn)程的結(jié)構(gòu)2．進(jìn)程控制塊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)建一個進(jìn)程時(shí)，實(shí)際上就是為其建立一個進(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）索引表方式：該方式是線性表方式的改進(jìn)，系統(tǒng)按照進(jìn)程的狀態(tài)分別建立就緒索引表、阻塞索引表等。

3）鏈接表方式：系統(tǒng)按照進(jìn)程的狀態(tài)將進(jìn)程的PCB組成隊(duì)列，從而形成就緒隊(duì)列、阻塞隊(duì)列、運(yùn)行隊(duì)列等。

返回本節(jié)3.4進(jìn)程控制3.4.1原語3.4.2進(jìn)程控制原語

返回首頁3.4.1原語原語通常由若干條指令所組成，用來實(shí)現(xiàn)某個特定的操作。通過一段不可分割的或不可中斷的程序?qū)崿F(xiàn)其功能。原語是操作系統(tǒng)核心，它不是由進(jìn)程而是由一組程序模塊所組成，是操作系統(tǒng)的一個組成部分，它必須在管態(tài)（一種機(jī)器狀態(tài)，管態(tài)下執(zhí)行的程序可以執(zhí)行特權(quán)和非特權(quán)兩類指令，通常把它定義為操作系統(tǒng)的狀態(tài)）下執(zhí)行，并且常駐內(nèi)存，而個別系統(tǒng)有一部分不在管態(tài)下運(yùn)行。

圖3.7進(jìn)程家族示例返回本節(jié)3.4.2進(jìn)程控制原語1．創(chuàng)建原語2．撤消原語3．阻塞原語4．喚醒原語5．掛起原語6．激活原語返回本節(jié)3.5線程的基本概念3.5.1線程的引入3.5.2線程與進(jìn)程的關(guān)系

3.5.3線程的類型

返回首頁3.5.1線程的引入（1）創(chuàng)建進(jìn)程。系統(tǒng)在創(chuàng)建進(jìn)程時(shí)，必須為之分配其所必需的、除處理機(jī)以外的所有資源。如內(nèi)存空間、I/O設(shè)備以及建立相應(yīng)的PCB結(jié)構(gòu)。（2）撤消進(jìn)程。系統(tǒng)在撤消進(jìn)程時(shí)，又必須先對這些資源進(jìn)行回收操作，然后再撤消PCB結(jié)構(gòu)。（3）進(jìn)程切換。在對進(jìn)程進(jìn)行切換時(shí)，由于要保留當(dāng)前進(jìn)程的CPU環(huán)境和設(shè)置新選中進(jìn)程的CPU環(huán)境，為此需花費(fèi)不少處理機(jī)時(shí)間。返回本節(jié)3.5.2線程與進(jìn)程的關(guān)系1．調(diào)度2．并發(fā)性3．擁有資源4．系統(tǒng)開銷返回本節(jié)3.5.3線程的類型1．線程的調(diào)度與切換速度2．系統(tǒng)功能調(diào)用3．線程執(zhí)行時(shí)間線程已在許多系統(tǒng)中實(shí)現(xiàn)，但實(shí)現(xiàn)的方式并不完全相同。在有的系統(tǒng)中，特別是一些數(shù)據(jù)庫管理系統(tǒng)如Informix，實(shí)現(xiàn)的是用戶級線程（User-Level-Threads），這種線程不依賴于內(nèi)核。而另一些系統(tǒng)（如Mach和OS/2操作系統(tǒng)）實(shí)現(xiàn)的是內(nèi)核支持線程（Kernel-Supported-Threads），這種線程依賴于內(nèi)核。還有一些系統(tǒng)如Solaris操作系統(tǒng)，則同時(shí)實(shí)現(xiàn)了這兩種類型的線程。返回本節(jié)3.6進(jìn)程調(diào)度3.6.1進(jìn)程調(diào)度的職能3.6.2進(jìn)程調(diào)度所用的主要數(shù)據(jù)結(jié)構(gòu)3.6.3進(jìn)程調(diào)度的方式3.6.4進(jìn)程調(diào)度算法

3.6.5綜合的調(diào)度策略——調(diào)度用的進(jìn)程狀態(tài)切換圖返回首頁3.6.1進(jìn)程調(diào)度的職能（1）記錄系統(tǒng)中所有進(jìn)程的有關(guān)情況。

（2）確定分配處理機(jī)的原則。

（3）分配處理機(jī)給進(jìn)程。

（4）從進(jìn)程收回處理機(jī)。引起進(jìn)程調(diào)度的原因不僅與操作系統(tǒng)的類型有著密切的關(guān)系，而且還與下列因素有關(guān)：①正在運(yùn)行的進(jìn)程運(yùn)行完畢；②運(yùn)行中的進(jìn)程要求I/O；③執(zhí)行某種原語操作；④一個比正在運(yùn)行進(jìn)程優(yōu)先數(shù)更高的進(jìn)程申請運(yùn)行（在可剝奪調(diào)度方式下）；⑤分配給運(yùn)行進(jìn)程的時(shí)間片已經(jīng)用完等。返回本節(jié)3.6.2進(jìn)程調(diào)度所用的主要數(shù)據(jù)結(jié)構(gòu)通過3.3.2節(jié)的學(xué)習(xí)我們知道操作系統(tǒng)對進(jìn)程的管理具體體現(xiàn)在對進(jìn)程的PCB的管理。同時(shí)也了解到進(jìn)程控制塊PCB的幾種組織方式：線性表方式、索引表方式和鏈接表方式。一般情況下，進(jìn)程控制塊PCB的組織方式采用的是鏈接表方式。因此，在進(jìn)程調(diào)度中所用的主要數(shù)據(jù)結(jié)構(gòu)是隊(duì)列（PCB的鏈接方式在這里就不詳細(xì)介紹了，若需要請?jiān)斠?.3.2節(jié)）

返回本節(jié)3.6.3進(jìn)程調(diào)度的方式進(jìn)程調(diào)度的方式可分為非剝奪式和剝奪式。剝奪式調(diào)度是指當(dāng)系統(tǒng)按照某種原則發(fā)現(xiàn)一個比現(xiàn)運(yùn)行進(jìn)程更合適、更應(yīng)該占用CPU的進(jìn)程時(shí)，系統(tǒng)將強(qiáng)迫處于運(yùn)行狀態(tài)的進(jìn)程將CPU的使用權(quán)交給這個更適合的進(jìn)程。

非剝奪式調(diào)度是指一旦某個進(jìn)程占用了CPU，除非是由于它自身原因自動放棄CPU，否則它將一直運(yùn)行下去直到完成。

返回本節(jié)3.6.4進(jìn)程調(diào)度算法1．先來先服務(wù)2．輪轉(zhuǎn)調(diào)度3．分級輪轉(zhuǎn)法4．優(yōu)先數(shù)法進(jìn)程調(diào)度的主要問題就是采用某種算法合理有效地把處理機(jī)分配給進(jìn)程，其調(diào)度算法應(yīng)盡可能提高資源的利用率，減少處理機(jī)的空閑時(shí)間。對于用戶作業(yè)采用較合理的平均響應(yīng)時(shí)間，以及盡可能地增強(qiáng)處理機(jī)的處理能力，避免有些作業(yè)長期不能投入運(yùn)行。這些“合理的原則”往往是互相制約的，甚至是矛盾的，難以全部達(dá)到要求。進(jìn)程的優(yōu)先數(shù)是根據(jù)什么條件確定的，這是一個很重要的問題，通常應(yīng)考慮如下幾個因素：

（1）進(jìn)程類型。根據(jù)不同類型的進(jìn)程確定其優(yōu)先數(shù)。

（2）運(yùn)行時(shí)間。通常規(guī)定進(jìn)程優(yōu)先數(shù)與進(jìn)程所需運(yùn)行時(shí)間成反比，即運(yùn)行時(shí)間長的（一般占用內(nèi)存也較多）大作業(yè)，分配給它的優(yōu)先數(shù)就越低，反之則越高。

（3）作業(yè)的優(yōu)先數(shù)。根據(jù)作業(yè)的優(yōu)先數(shù)來決定其所屬進(jìn)程的優(yōu)先數(shù)。

（4）動態(tài)優(yōu)先數(shù)。時(shí)間片的長短由如下四個因素決定：（1）系統(tǒng)的響應(yīng)時(shí)間。當(dāng)進(jìn)程數(shù)目一定時(shí)，時(shí)間片的長短直接影響系統(tǒng)的響應(yīng)時(shí)間。（2）就緒隊(duì)列中進(jìn)程的數(shù)目。這與前面的問題正好相反，即當(dāng)系統(tǒng)對響應(yīng)時(shí)間要求一定時(shí)，時(shí)間片長則就緒隊(duì)列中進(jìn)程數(shù)應(yīng)少，反之亦然。（3）進(jìn)程狀態(tài)轉(zhuǎn)換（即進(jìn)程由就緒到運(yùn)行，由運(yùn)行到就緒）的時(shí)間開銷。（4）計(jì)算機(jī)本身的處理能力。執(zhí)行速度和可運(yùn)行作業(yè)的道數(shù)。返回本節(jié)3.6.5綜合的調(diào)度策略——調(diào)度用的進(jìn)程狀態(tài)切換圖我們采用進(jìn)程狀態(tài)切換圖來幫助大家進(jìn)一步了解進(jìn)程調(diào)度算法。以分級輪轉(zhuǎn)法為例，將就緒進(jìn)程分成高優(yōu)先數(shù)和低優(yōu)先數(shù)兩個隊(duì)列。如果進(jìn)程運(yùn)行中超過了規(guī)定的時(shí)間片就進(jìn)入低優(yōu)先數(shù)隊(duì)列，而I/O操作完成的進(jìn)程，即由阻塞狀態(tài)進(jìn)入高優(yōu)先數(shù)就緒隊(duì)列。如圖3.8所示，其調(diào)度算法是：首先從高優(yōu)先就緒隊(duì)列中選擇一個進(jìn)程來運(yùn)行，如果在高優(yōu)先數(shù)就緒隊(duì)列中沒有進(jìn)程，則從低優(yōu)先數(shù)就緒隊(duì)列中選擇一個進(jìn)程運(yùn)行。低優(yōu)先數(shù)就緒運(yùn)行高優(yōu)先數(shù)就緒因等待I/O而阻塞首先選擇I/O完成其次選擇超過時(shí)間片請求I/O圖3.8調(diào)度用的進(jìn)程狀態(tài)切換圖返回本節(jié)3.7進(jìn)程通信3.7.1進(jìn)程互斥3.7.2互斥用的硬件機(jī)制3.7.3進(jìn)程同步3.7.4用信號量實(shí)現(xiàn)進(jìn)程同步

3.7.5兩個經(jīng)典的同步/互斥問題

3.7.6結(jié)構(gòu)化的同步/互斥機(jī)制——管程3.7.7進(jìn)程的通信方式之二——消息緩沖

返回首頁3.7.1進(jìn)程互斥幾個進(jìn)程若共享同一臨界資源，它們必須以互斥的方式使用這個臨界資源，即當(dāng)一個進(jìn)程正在使用臨界資源且尚未使用完畢時(shí)，則其他進(jìn)程必須推遲對該資源的進(jìn)一步操作，在當(dāng)前進(jìn)程的使用完成之前，不能從中插進(jìn)去使用這個臨界資源，否則將會造成信息混亂和操作出錯。系統(tǒng)中同時(shí)存在有許多進(jìn)程，它們共享各種資源，然而有些資源每次只能讓一個進(jìn)程所使用。臨界區(qū)是一個進(jìn)程訪問臨界資源的那段程序代碼。有了臨界資源和臨界區(qū)的概念，進(jìn)程間的互斥可以描述為禁止兩個或兩個以上的進(jìn)程同時(shí)進(jìn)入訪問同一臨界資源的臨界區(qū)。

返回本節(jié)3.7.2互斥用的硬件機(jī)制下面我們不局限于某特定系統(tǒng)，定義TS指令為：functionTS（varlock：boolean）：boolean；beginTS：=lock；lock：=true；end用TS指令實(shí)現(xiàn)互斥的循環(huán)進(jìn)程可描述如下：repeat

whileTS(lock)doskip；criticalsection；lock：=false；

remaindersection；untilfalse返回本節(jié)3.7.3進(jìn)程同步并發(fā)執(zhí)行的多個進(jìn)程，看起來好像是異步前進(jìn)的，彼此之間都可以互不相關(guān)的速度向前推進(jìn)，而實(shí)際上每一個進(jìn)程在其運(yùn)行過程中并非相互隔絕。一方面它們相互協(xié)作以達(dá)到運(yùn)行用戶作業(yè)所預(yù)期的目的，另一方面它們又相互競爭使用系統(tǒng)中有限的資源。兩個并行的進(jìn)程A、B，如果當(dāng)A進(jìn)行某個操作時(shí)，B不能做這一操作，進(jìn)程間的這種限制條件稱為進(jìn)程互斥，引起資源不可共享的原因：一是資源的物理特性所致；二是某些資源如果同時(shí)被幾個進(jìn)程使用，則一個進(jìn)程的動作可能會干擾其他進(jìn)程的動作。

返回本節(jié)3.7.4用信號量實(shí)現(xiàn)進(jìn)程同步1．lock和unlock大部分同步方案均采用某個物理實(shí)體（如鎖、信號燈等）實(shí)現(xiàn)通信，進(jìn)程通信原語中關(guān)鎖（lock）和開鎖（unlock）是最簡單的原語。在這兩個原語中設(shè)置一個公共變量x代表某個臨界資源的狀態(tài)。

進(jìn)程使用臨界資源必須作如下三個不可分割的操作：（1）檢查x的值。（2）進(jìn)入臨界區(qū)，訪問臨界區(qū)資源。（3）釋放臨界區(qū)資源，置x為0（開鎖）。

Y退出C并開鎖置X=0進(jìn)入臨界區(qū)C關(guān)鎖則置X=1測試X=0?返回繼續(xù)測試N圖3.9開鎖和關(guān)鎖程序流程圖2．P/V操作設(shè)s1、、s2初值為0，用P／V操作實(shí)現(xiàn)上述同步模型如下：返回本節(jié)3.7.5兩個經(jīng)典的同步/互斥問題1．生產(chǎn)者與消費(fèi)者問題Dijkstra把廣義同步問題抽象成一種“生產(chǎn)者與消費(fèi)者問題”（Producer-consumer-relationship）的抽象模型。2．讀者與寫者問題一個數(shù)據(jù)對象（比如一個文件或記錄）若被多個并發(fā)進(jìn)程所共享，且其中一些進(jìn)程只要求讀該數(shù)據(jù)對象的內(nèi)容，而另一些進(jìn)程則要求修改它，對此，可把那些只想讀的進(jìn)程稱之為“讀者”；而把要求修改的進(jìn)程稱為“寫者”。下面給出基于環(huán)形緩沖區(qū)的生產(chǎn)者與消費(fèi)者關(guān)系的形式描述，設(shè)：（1）公用信號量mutex：初值為1，用于實(shí)現(xiàn)臨界區(qū)互斥。（2）生產(chǎn)者私用信號量empty：初值為n，指示空緩沖塊數(shù)目。（3）消費(fèi)者私用信號量full：初值為0，指示滿緩沖塊數(shù)目。（4）整型量i和j初值均為0，i指示首空緩沖塊序號，j指示首滿緩沖塊序號。Varmutex，empty，full：semaphore;i,j:integer；buffer：array[0…n一1]ofitem；Procedureproducer;生產(chǎn)者進(jìn)程

beginwhiletruedobeginproduceaproduct;P(empty);P(mutex);Buffer(i)：＝Product;i：＝(i+1)modn;V(mutex);V(full);endend;procedureconsumer;消費(fèi)者進(jìn)程

beginwhiletruedobeginP(full);P(mutex);goods：＝buffer(j);j：＝(j+1)modn;V(mutex);V(empty);Consumeaproduct;endend;beginseminitial;i:＝j(luò):＝0;cobeginproducer;consumer;Coendend下面給出讀者進(jìn)程與寫者進(jìn)程的一般結(jié)構(gòu)。varmutex,wrt:semaphore;readcount:integer;beginseminit;readcount:=0cobeginprocedurereader;beginP(mutex);readcount:=readcount+1;Ifreadcount=1thenP(wrt);V(mutex);readingisperforming;P(mutex);readcount:=readcount-1ifreadcount=0thenV(wrt);V(mutex);endprocedurewriter;beginP(wrt);writingisperforming;V(wrt);endcoendend;返回本節(jié)3.7.6結(jié)構(gòu)化的同步/互斥機(jī)制——管程建立管程的基本理由是：由于對臨界區(qū)的執(zhí)行分散在各進(jìn)程中，這樣不便于系統(tǒng)對臨界資源的控制和管理，也很難發(fā)現(xiàn)和糾正分散在用戶程序中的對同步原語的錯誤使用等問題。為此，應(yīng)把分散的各同類臨界區(qū)集中起來。并為每個可共享資源設(shè)立一個專門的管程來統(tǒng)一管理各進(jìn)程對該資源的訪問。這樣既便于系統(tǒng)管理共享資源，又能保證互斥訪問。管程主要由兩部分組成：（1）局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀態(tài)。（2）局部于該管程的若干過程，每個過程完成關(guān)于上述數(shù)據(jù)的某種規(guī)定操作。

例如，對并發(fā)PASCAL編譯程序在編譯源程序時(shí)，對每一個形如：monitor—cedure/function—entry—name的調(diào)用語句，都將自動保證其按如下方式執(zhí)行：P(mutex)；執(zhí)行相應(yīng)的過程或函數(shù)：V(mutex)；其中，mutex是關(guān)于相應(yīng)管程的互斥信號燈，初值為1。前面我們曾給出了利用信號燈及其P、V操作實(shí)現(xiàn)的生產(chǎn)者與消費(fèi)者共享環(huán)形緩沖池的同步模型，這里再以環(huán)形緩沖池為例，給出環(huán)形緩沖池的管程結(jié)構(gòu)。monitorringbuffer;varrbuffer：array[0．．n-1]ofitem；k,nextempty,nextfull:integer;empty,full:condition;procedureentryput(varproduct:item);beginifk=nwait(empty);rbuffer[nextempty]:product;k:=k+1；nextempty:=(nextempty+1)modn;signal(full);end;procedureentryget(vargoods:item);beginifk=0wait(full);goods:=rbuffer[nextfull];k:=k-1;nextfull:=(nextfull+1)modn;signal(empty);end;begink:=0;nextempty:=0;nextfull:=0;end;管程ringbuffer包含兩個局部過程：過程put負(fù)責(zé)執(zhí)行將數(shù)據(jù)寫入某個緩沖塊的操作；過程get負(fù)責(zé)執(zhí)行從某個緩沖塊讀取數(shù)據(jù)的操作。empty和full定義為兩個條件變量，對應(yīng)于緩沖池滿和緩沖池空條件等待隊(duì)列。任一進(jìn)程都必須通過調(diào)用管程ringbuffer來使用環(huán)形緩沖池，生產(chǎn)者進(jìn)程調(diào)用其中的put過程，消費(fèi)者進(jìn)程調(diào)用get過程。在利用管程解決生產(chǎn)者、消費(fèi)者問題時(shí)，其中的生產(chǎn)者和消費(fèi)者可描述為：producer：beginrepeatproduceanitem;ringbuffer.put(item);untilfalse;endconsumer：beginrepeatringbuffer.get(item);consumetheitem;end返回本節(jié)3.7.7進(jìn)程的通信方式之二——消息緩沖兩個并發(fā)進(jìn)程可以通過互相發(fā)送消息進(jìn)行合作，消息是通過消息緩沖而在進(jìn)程之間互相傳遞的。所謂消息是指進(jìn)程之間以不連續(xù)的成組方式發(fā)送的信息，而消息緩沖區(qū)則是包含有指向發(fā)送進(jìn)程的指針、指向消息接收進(jìn)程的指針、指向下一個消息緩沖區(qū)的指針、消息長度、消息內(nèi)容等信息的一個緩沖區(qū)。這個緩沖區(qū)就構(gòu)成進(jìn)程通信的一個基本單位。當(dāng)進(jìn)程需要發(fā)送消息時(shí)，就構(gòu)成這樣一個緩沖區(qū)，并發(fā)送給指定的接收進(jìn)程。

1．SEND(A)（發(fā)送消息）原語2．READ（A）（讀取消息）原語1．SEND(A)（發(fā)送消息）原語發(fā)送消息原語被進(jìn)程用于把消息發(fā)送到存放消息的緩沖區(qū)。A是原語的參數(shù)，表示發(fā)送區(qū)的地址。其工作原理是：首先調(diào)用“尋找目標(biāo)進(jìn)程的PCB”的程序查找接收進(jìn)程的PCB，如果接收進(jìn)程存在，申請一個存放消息的緩沖區(qū)，消息緩沖區(qū)為空時(shí)，接收此消息的進(jìn)程因等待此消息的到來而處于阻塞狀態(tài)，則喚醒此進(jìn)程，并把消息的內(nèi)容、發(fā)送原語的進(jìn)程名和消息等，復(fù)制到預(yù)先申請的存放消息的緩沖區(qū)，且將存放消息的緩沖區(qū)連接到接收進(jìn)程的PCB上；如果接收進(jìn)程不存在，則由系統(tǒng)給出一個“啞”回答；最后控制返回到發(fā)送消息的進(jìn)程繼續(xù)執(zhí)行，或轉(zhuǎn)入進(jìn)程調(diào)度程序重新分配處理機(jī)。如圖3.11所示。

圖3.11發(fā)送消息過程流圖2．READ（A）（讀取消息）原語READ(A)原語用來讀取消息，接收進(jìn)程讀取消息之前，在自己的空間中確定一個接收區(qū)。當(dāng)接收進(jìn)程想要讀取消息時(shí)，使用READ(A)原語，A是接收進(jìn)程提供的接收區(qū)開始地址。如圖3.12所示。

圖3.12讀取消息返回本節(jié)3.8死鎖問題3.8.1死鎖產(chǎn)生的原因和必要條件3.8.2預(yù)防死鎖

3.8.3避免死鎖3.8.4檢測與解除死鎖

返回首頁3.8.1死鎖產(chǎn)生的原因和必要條件在許多中型和大型計(jì)算機(jī)系統(tǒng)中，都期望在各級系統(tǒng)和用戶程序上具有動態(tài)共享資源、并發(fā)程序設(shè)計(jì)及進(jìn)程通信這些操作特征，來改善系統(tǒng)資源的利用率和提高系統(tǒng)的處理能力。由于資源的占用往往是互斥的，因此當(dāng)某個進(jìn)程提出申請資源后，使得有關(guān)進(jìn)程在無外力協(xié)助下，永遠(yuǎn)分配不到必需的資源而無法繼續(xù)運(yùn)行，這就產(chǎn)生了一種特殊的現(xiàn)象——死鎖。

先來看一個申請不同類型資源的死鎖例子，假定有兩個進(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ī)Tr1：申請磁帶機(jī)T……r2：申請文件F

釋放磁帶機(jī)T…

釋放文件F釋放文件F…釋放磁帶機(jī)T…TFP1P2請求配分已請求配分已圖3.13簡單的死鎖例子R°°P1P2P3分配申請圖3.14同類資源共享時(shí)的死鎖現(xiàn)象由以上諸例子可知，產(chǎn)生死鎖現(xiàn)象的原因，一是系統(tǒng)提供的資源不能滿足每個進(jìn)程的使用；二是在多道程序運(yùn)行時(shí)，進(jìn)程推進(jìn)順序不合理。產(chǎn)生死鎖有四個必要條件：（1）互斥條件。

（2）不剝奪條件。

（3）請求和保持條件。

（4）環(huán)路等待條件。

返回本節(jié)3.8.2預(yù)防死鎖1．破壞“請求與保持條件”2．破壞環(huán)路條件3．資源受控動態(tài)分配圖3.15資源申請和釋放順序圖

返回本節(jié)3.8.3避免死鎖避免死鎖是指通過某種算法，當(dāng)系統(tǒng)分配資源時(shí)始終能作出是否分配的正確選擇，從而避免死鎖。目前運(yùn)用的避免死鎖的算法是E.W.Dijkstra提出的銀行家算法。銀行家算法的數(shù)據(jù)結(jié)構(gòu)包括：可用資源向量Available

最大需求矩陣Max分配矩陣Allocation需求矩陣Need

銀行家算法如下：設(shè)Requesti是進(jìn)程Pi的請求向量，Requesti(j)=k表示進(jìn)程Pi請求分配Rj類資源k個，當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按照下列步驟進(jìn)行檢查。（1）若Requesti≤Need，則執(zhí)行步驟（2）；否則系統(tǒng)會因?yàn)樗枰馁Y源數(shù)已超過它要求的最大值而認(rèn)為出錯。（2）若Requesti≤Available，則執(zhí)行步驟（3）；否則系統(tǒng)會因?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)將試探分配作

系統(tǒng)所執(zhí)行的安全性算法描述如下：

（1）設(shè)置兩個向量：Work和Finish。

（2）從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：①Finish(i)=false②Needi≤Work（3）當(dāng)進(jìn)程Pi獲得資源后可順利執(zhí)行直到完成，然后釋放分配給它的資源，并作如下工作：①Work=Work+Allocation②Finish(i)=true（4）若所有進(jìn)程的Finish(i)的值都為true，則說明