第2章 進(jìn)程的描述及控制

1、1 1第二章 進(jìn)程的描述與控制第二章第二章 進(jìn)程的描述與控制進(jìn)程的描述與控制 2.1 前趨圖和程序執(zhí)行2.2 進(jìn)程的描述2.3 進(jìn)程控制2.4 進(jìn)程同步2.5 經(jīng)典進(jìn)程的同步問(wèn)題2.6 進(jìn)程通信2.7 線程(Threads)的基本概念2.8 線程的實(shí)現(xiàn)習(xí)題2 2第二章 進(jìn)程的描述與控制2.1 前趨圖和程序執(zhí)行在早期未配置OS的系統(tǒng)和單道批處理系統(tǒng)中，程序的執(zhí)行方式是順序執(zhí)行，即在內(nèi)存中僅裝入一道用戶(hù)程序，由它獨(dú)占系統(tǒng)中的所有資源，只有在一個(gè)用戶(hù)程序執(zhí)行完成后，才允許裝入另一個(gè)程序并執(zhí)行?？梢?jiàn)，這種方式浪費(fèi)資源、系統(tǒng)運(yùn)行效率低等缺點(diǎn)。 3 3第二章 進(jìn)程的描述與控制2.1.1 前趨圖為了能更好地

2、描述程序的順序和并發(fā)執(zhí)行情況，我們先介紹用于描述程序執(zhí)行先后順序的前趨圖。所謂前趨圖(Precedence Graph)，是指一個(gè)有向無(wú)循環(huán)圖，可記為DAG(Directed Acyclic Graph)，它用于描述進(jìn)程之間執(zhí)行的先后順序。圖中的每個(gè)結(jié)點(diǎn)可用來(lái)表示一個(gè)進(jìn)程或程序段，乃至一條語(yǔ)句，結(jié)點(diǎn)間的有向邊則表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(Partial Order)或前趨關(guān)系(Precedence Relation)。4 4第二章 進(jìn)程的描述與控制進(jìn)程(或程序)之間的前趨關(guān)系可用“”來(lái)表示，如果進(jìn)程Pi和Pj存在著前趨關(guān)系，可表示為(Pi，Pj)，也可寫(xiě)成PiPj，表示在Pj開(kāi)始執(zhí)行之前Pi

3、必須完成。此時(shí)稱(chēng)Pi是Pj的直接前趨，而稱(chēng)Pj是Pi的直接后繼。在前趨圖中，把沒(méi)有前趨的結(jié)點(diǎn)稱(chēng)為初始結(jié)點(diǎn)(Initial Node)，把沒(méi)有后繼的結(jié)點(diǎn)稱(chēng)為終止結(jié)點(diǎn)(Final Node)。此外，每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或程序的執(zhí)行時(shí)間。 5 5第二章 進(jìn)程的描述與控制在圖2-1(a)所示的前趨圖中，存在著如下前趨關(guān)系：P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P9或表示為：P=P1, P2, P3, P4, P5, P6, P7, P8, P9 =(P1, P2), (P1, P3), (

4、P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9)6 6第二章 進(jìn)程的描述與控制應(yīng)當(dāng)注意，前趨圖中是不允許有循環(huán)的，否則必然會(huì)產(chǎn)生不可能實(shí)現(xiàn)的前趨關(guān)系。如圖2-1(b)所示的前趨關(guān)系中就存在著循環(huán)。它一方面要求在S3開(kāi)始執(zhí)行之前，S2必須完成，另一方面又要求在S2開(kāi)始執(zhí)行之前，S3必須完成。顯然，這種關(guān)系是不可能實(shí)現(xiàn)的。S2S3，S3S27 7第二章 進(jìn)程的描述與控制圖2-1 前趨圖8 8第二章 進(jìn)程的描述與控制2.1.2 程序順序執(zhí)行1. 程序的順序執(zhí)行通常，一個(gè)應(yīng)用程

5、序由若干個(gè)程序段組成，每一個(gè)程序段完成特定的功能，它們?cè)趫?zhí)行時(shí)，都需要按照某種先后次序順序執(zhí)行，僅當(dāng)前一程序段執(zhí)行完后，才運(yùn)行后一程序段。例如，在進(jìn)行計(jì)算時(shí)，應(yīng)先運(yùn)行輸入程序，用于輸入用戶(hù)的程序和數(shù)據(jù)；然后運(yùn)行計(jì)算程序，對(duì)所輸入的數(shù)據(jù)進(jìn)行計(jì)算；最后才是運(yùn)行打印程序，打印計(jì)算結(jié)果。我們用結(jié)點(diǎn)(Node)代表各程序段的操作(在圖2-1中用圓圈表示)，其中I代表輸入操作，C代表計(jì)算操作，P為打印操作，用箭頭指示操作的先后次序。9 9第二章 進(jìn)程的描述與控制這樣，上述的三個(gè)程序段間就存在著這樣的前趨關(guān)系：IiCiPi，其執(zhí)行的順序可用前趨圖2-2(a)描述。即使是一個(gè)程序段，也可能存在著執(zhí)行順序問(wèn)題，

6、下面示出了一個(gè)包含了三條語(yǔ)句的程序段：S1: a :=x+y；S2: b :=a-5；S3: c :=b+1；其中，語(yǔ)句S2必須在語(yǔ)句S1后(即a被賦值)才能執(zhí)行，語(yǔ)句S3也只能在b被賦值后才能執(zhí)行，因此，三條語(yǔ)句存在著這樣的前趨關(guān)系：S1S2S3，應(yīng)按前趨圖2-2(b)所示的順序執(zhí)行。10 10第二章 進(jìn)程的描述與控制圖2-2程序順序執(zhí)行的前趨圖11 11第二章 進(jìn)程的描述與控制由上所述可以得知，在程序順序執(zhí)行時(shí)，具有這樣三個(gè)特征： 順序性：指處理機(jī)嚴(yán)格地按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在下一個(gè)操作開(kāi)始之前結(jié)束； 封閉性：指程序在封閉的環(huán)境下運(yùn)行，即程序運(yùn)行時(shí)獨(dú)占全機(jī)資源，資源的狀態(tài)

7、(除初始狀態(tài)外)只有本程序才能改變它，程序一旦開(kāi)始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響； 可再現(xiàn)性：指只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時(shí)，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行，都可獲得相同的結(jié)果。程序順序執(zhí)行時(shí)的這種特性，為程序員檢測(cè)和校正程序的錯(cuò)誤帶來(lái)了很大的方便。12 12第二章 進(jìn)程的描述與控制2.1.3程序并發(fā)執(zhí)行1. 程序的并發(fā)執(zhí)行我們通過(guò)一個(gè)常見(jiàn)的例子來(lái)說(shuō)明程序的順序執(zhí)行和并發(fā)執(zhí)行。在圖2-2中的輸入程序、計(jì)算程序和打印程序三者之間，存在著IiCiPi這樣的前趨關(guān)系，以至對(duì)一個(gè)作業(yè)的輸入、計(jì)算和打印三個(gè)程序段必須順序執(zhí)行。但若是對(duì)一批作業(yè)進(jìn)行處理時(shí)，每

8、道作業(yè)的輸入、計(jì)算和打印程序段的執(zhí)行情況如圖2-3所示。 13 13第二章 進(jìn)程的描述與控制圖2-3 程序并發(fā)執(zhí)行時(shí)的前趨圖 14 14第二章 進(jìn)程的描述與控制由圖2-3可以看出，存在前趨關(guān)系IiCi，IiIi+1，CiPi，CiCi+1，PiPi+1，而Ii+1和Ci及Pi-1是重疊的，即在Pi-1和Ci以及Ii+1之間，不存在前趨關(guān)系，可以并發(fā)執(zhí)行。對(duì)于具有下述四條語(yǔ)句的程序段：S1: a :=x+2S2: b :=y+4S3: c :=a+bS4: d :=c+b可畫(huà)出圖2-4所示的前趨關(guān)系。可以看出：S3必須在a和b被賦值后方能執(zhí)行；S4必須在S3之后執(zhí)行；但S1和S2則可以并發(fā)執(zhí)行，

9、因?yàn)樗鼈儽舜嘶ゲ灰蕾?lài)。15 15第二章 進(jìn)程的描述與控制 圖2-4 四條語(yǔ)句的前趨關(guān)系 16 16第二章 進(jìn)程的描述與控制2. 程序并發(fā)執(zhí)行時(shí)的特征在引入了程序間的并發(fā)執(zhí)行功能后，雖然提高了系統(tǒng)的吞吐量和資源利用率，但由于它們共享系統(tǒng)資源，以及它們?yōu)橥瓿赏豁?xiàng)任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間必將形成相互制約的關(guān)系，由此會(huì)給程序并發(fā)執(zhí)行帶來(lái)新的特征。(1) 間斷性。(2) 失去封閉性。(3) 不可再現(xiàn)性。17 17第二章 進(jìn)程的描述與控制2.2 進(jìn)程的描述2.2.1 進(jìn)程的定義和特征1. 進(jìn)程的定義 在多道程序環(huán)境下，程序的執(zhí)行屬于并發(fā)執(zhí)行，此時(shí)它們將失去其封閉性，并具有間斷性，以及

10、其運(yùn)行結(jié)果不可再現(xiàn)性的特征。由此，決定了通常的程序是不能參與并發(fā)執(zhí)行的，否則，程序的運(yùn)行也就失去了意義。為了能使程序并發(fā)執(zhí)行，并且可以對(duì)并發(fā)執(zhí)行的程序加以描述和控制，人們引入了“進(jìn)程”的概念。18 18第二章 進(jìn)程的描述與控制對(duì)于進(jìn)程的定義，從不同的角度可以有不同的定義，其中較典型的定義有：(1) 進(jìn)程是程序的一次執(zhí)行。(2) 進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。(3) 進(jìn)程是具有獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。19 19第二章 進(jìn)程的描述與控制2. 進(jìn)程的特征進(jìn)程和程序是兩個(gè)截然不同的概念，除了進(jìn)程具有程序所沒(méi)有的PCB

11、結(jié)構(gòu)外，還具有下面一些特征：(1) 動(dòng)態(tài)性。(2) 并發(fā)性。(3) 獨(dú)立性。(4) 異步性。2020第二章 進(jìn)程的描述與控制2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換1. 進(jìn)程的三種基本狀態(tài)由于多個(gè)進(jìn)程在并發(fā)執(zhí)行時(shí)共享系統(tǒng)資源，致使它們?cè)谶\(yùn)行過(guò)程中呈現(xiàn)間斷性的運(yùn)行規(guī)律，所以進(jìn)程在其生命周期內(nèi)可能具有多種狀態(tài)。一般而言，每一個(gè)進(jìn)程至少應(yīng)處于以下三種基本狀態(tài)之一：(1) 就緒(Ready)狀態(tài)。(2) 執(zhí)行(Running)狀態(tài)。(3) 阻塞(Block)狀態(tài)。 21 21第二章 進(jìn)程的描述與控制2. 三種基本狀態(tài)的轉(zhuǎn)換進(jìn)程在運(yùn)行過(guò)程中會(huì)經(jīng)常發(fā)生狀態(tài)的轉(zhuǎn)換。例如，處于就緒狀態(tài)的進(jìn)程，在調(diào)度程序?yàn)橹峙淞颂幚?/p>

12、機(jī)之后便可執(zhí)行，相應(yīng)地，其狀態(tài)就由就緒態(tài)轉(zhuǎn)變?yōu)閳?zhí)行態(tài)；正在執(zhí)行的進(jìn)程(當(dāng)前進(jìn)程)如果因分配給它的時(shí)間片已完而被剝奪處理機(jī)暫停執(zhí)行時(shí)，其狀態(tài)便由執(zhí)行轉(zhuǎn)為就緒；如果因發(fā)生某事件，致使當(dāng)前進(jìn)程的執(zhí)行受阻(例如進(jìn)程訪問(wèn)某臨界資源，而該資源正被其它進(jìn)程訪問(wèn)時(shí))，使之無(wú)法繼續(xù)執(zhí)行，則該進(jìn)程狀態(tài)將由執(zhí)行轉(zhuǎn)變?yōu)樽枞?。圖2-5示出了進(jìn)程的三種基本狀態(tài)，以及各狀態(tài)之間的轉(zhuǎn)換關(guān)系。2222第二章 進(jìn)程的描述與控制圖2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換2323第二章 進(jìn)程的描述與控制3. 創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)1) 創(chuàng)建狀態(tài)如前所述，進(jìn)程是由創(chuàng)建而產(chǎn)生。創(chuàng)建一個(gè)進(jìn)程是個(gè)很復(fù)雜的過(guò)程，一般要通過(guò)多個(gè)步驟才能完成：如首先由進(jìn)程

13、申請(qǐng)一個(gè)空白PCB，并向PCB中填寫(xiě)用于控制和管理進(jìn)程的信息；然后為該進(jìn)程分配運(yùn)行時(shí)所必須的資源；最后，把該進(jìn)程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊(duì)列之中。但如果進(jìn)程所需的資源尚不能得到滿(mǎn)足，比如系統(tǒng)尚無(wú)足夠的內(nèi)存使進(jìn)程無(wú)法裝入其中，此時(shí)創(chuàng)建工作尚未完成，進(jìn)程不能被調(diào)度運(yùn)行，于是把此時(shí)進(jìn)程所處的狀態(tài)稱(chēng)為創(chuàng)建狀態(tài)。2424第二章 進(jìn)程的描述與控制2) 終止?fàn)顟B(tài)進(jìn)程的終止也要通過(guò)兩個(gè)步驟：首先，是等待操作系統(tǒng)進(jìn)行善后處理，最后將其PCB清零，并將PCB空間返還系統(tǒng)。當(dāng)一個(gè)進(jìn)程到達(dá)了自然結(jié)束點(diǎn)，或是出現(xiàn)了無(wú)法克服的錯(cuò)誤，或是被操作系統(tǒng)所終結(jié)，或是被其他有終止權(quán)的進(jìn)程所終結(jié)，它將進(jìn)入終止?fàn)顟B(tài)。進(jìn)入終止態(tài)的進(jìn)程以后

14、不能再執(zhí)行，但在操作系統(tǒng)中依然保留一個(gè)記錄，其中保存狀態(tài)碼和一些計(jì)時(shí)統(tǒng)計(jì)數(shù)據(jù)，供其他進(jìn)程收集。一旦其他進(jìn)程完成了對(duì)其信息的提取之后，操作系統(tǒng)將刪除該進(jìn)程，即將其PCB清零，并將該空白PCB返還系統(tǒng)。圖2-6示出了增加了創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)后進(jìn)程的五種狀態(tài)及轉(zhuǎn)換關(guān)系圖。2525第二章 進(jìn)程的描述與控制圖2-6 進(jìn)程的五種基本狀態(tài)及轉(zhuǎn)換2626第二章 進(jìn)程的描述與控制2.2.3 掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換1. 掛起操作的引入引入掛起操作的原因，是基于系統(tǒng)和用戶(hù)的如下需要：(1) 終端用戶(hù)的需要。(2) 父進(jìn)程請(qǐng)求。(3) 負(fù)荷調(diào)節(jié)的需要。(4) 操作系統(tǒng)的需要。 2727第二章 進(jìn)程的描述與控制2.

15、引入掛起原語(yǔ)操作后三個(gè)進(jìn)程狀態(tài)的轉(zhuǎn)換在引入掛起原語(yǔ)Suspend和激活原語(yǔ)Active后，在它們的作用下，進(jìn)程將可能發(fā)生以下幾種狀態(tài)的轉(zhuǎn)換：(1) 活動(dòng)就緒靜止就緒。(2) 活動(dòng)阻塞靜止阻塞。(3) 靜止就緒活動(dòng)就緒。(4) 靜止阻塞活動(dòng)阻塞。2828第二章 進(jìn)程的描述與控制3. 引入掛起操作后五個(gè)進(jìn)程狀態(tài)的轉(zhuǎn)換如圖2-8示出了增加了創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)后具有掛起狀態(tài)的進(jìn)程狀態(tài)及轉(zhuǎn)換圖。如圖2-8所示，引進(jìn)創(chuàng)建和終止?fàn)顟B(tài)后，在進(jìn)程狀態(tài)轉(zhuǎn)換時(shí)，與圖2-7所示的進(jìn)程五狀態(tài)轉(zhuǎn)換相比較，要增加考慮下面的幾種情況：(1) NULL創(chuàng)建：(2) 創(chuàng)建活動(dòng)就緒：(3) 創(chuàng)建靜止就緒：(4) 執(zhí)行終止：2929

16、第二章 進(jìn)程的描述與控制圖2-7具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 3030第二章 進(jìn)程的描述與控制 圖2-8 具有創(chuàng)建、終止和掛起狀態(tài)的進(jìn)程狀態(tài)圖 31 31第二章 進(jìn)程的描述與控制2.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)1. 操作系統(tǒng)中用于管理控制的數(shù)據(jù)結(jié)構(gòu) 在計(jì)算機(jī)系統(tǒng)中，對(duì)于每個(gè)資源和每個(gè)進(jìn)程都設(shè)置了一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于表征其實(shí)體，我們稱(chēng)之為資源信息表或進(jìn)程信息表，其中包含了資源或進(jìn)程的標(biāo)識(shí)、描述、狀態(tài)等信息以及一批指針。通過(guò)這些指針，可以將同類(lèi)資源或進(jìn)程的信息表，或者同一進(jìn)程所占用的資源信息表分類(lèi)鏈接成不同的隊(duì)列，便于操作系統(tǒng)進(jìn)行查找。 3232第二章 進(jìn)程的描述與控制如圖2-9所示，OS管理的這些數(shù)據(jù)

17、結(jié)構(gòu)一般分為以下四類(lèi)：內(nèi)存表、設(shè)備表、文件表和用于進(jìn)程管理的進(jìn)程表，通常進(jìn)程表又被稱(chēng)為進(jìn)程控制塊PCB。 3333第二章 進(jìn)程的描述與控制圖2-9 操作系統(tǒng)控制表的一般結(jié)構(gòu)3434第二章 進(jìn)程的描述與控制2. 進(jìn)程控制塊PCB的作用(1) 作為獨(dú)立運(yùn)行基本單位的標(biāo)志。(2) 能實(shí)現(xiàn)間斷性運(yùn)行方式。 (3) 提供進(jìn)程管理所需要的信息。(4) 提供進(jìn)程調(diào)度所需要的信息。(5) 實(shí)現(xiàn)與其它進(jìn)程的同步與通信。3535第二章 進(jìn)程的描述與控制3. 進(jìn)程控制塊中的信息在進(jìn)程控制塊中，主要包括下述四個(gè)方面的信息。1) 進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符用于唯一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符：(1) 外部標(biāo)識(shí)符。

18、(2) 內(nèi)部標(biāo)識(shí)符。3636第二章 進(jìn)程的描述與控制2) 處理機(jī)狀態(tài)處理機(jī)狀態(tài)信息也稱(chēng)為處理機(jī)的上下文，主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。 3737第二章 進(jìn)程的描述與控制3) 進(jìn)程調(diào)度信息在OS進(jìn)行調(diào)度時(shí)，必須了解進(jìn)程的狀態(tài)及有關(guān)進(jìn)程調(diào)度的信息，這些信息包括： 進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)，它是作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)； 進(jìn)程優(yōu)先級(jí)，是用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)，優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)； 進(jìn)程調(diào)度所需的其它信息，它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等； 事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，

19、即阻塞原因。3838第二章 進(jìn)程的描述與控制4) 進(jìn)程控制信息是指用于進(jìn)程控制所必須的信息，它包括： 程序和數(shù)據(jù)的地址，進(jìn)程實(shí)體中的程序和數(shù)據(jù)的內(nèi)存或外存地(首)址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)； 進(jìn)程同步和通信機(jī)制，這是實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制，如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地放在PCB中； 資源清單，在該清單中列出了進(jìn)程在運(yùn)行期間所需的全部資源(除CPU以外)，另外還有一張已分配到該進(jìn)程的資源的清單； 鏈接指針，它給出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的PCB的首地址。3939第二章 進(jìn)程的描述與控制4. 進(jìn)程控制塊的組織方式在一個(gè)系

20、統(tǒng)中，通?？蓳碛袛?shù)十個(gè)、數(shù)百個(gè)乃至數(shù)千個(gè)PCB。為了能對(duì)它們加以有效的管理，應(yīng)該用適當(dāng)?shù)姆绞綄⑦@些PCB組織起來(lái)。目前常用的組織方式有以下三種。(1) 線性方式，即將系統(tǒng)中所有的PCB都組織在一張線性表中，將該表的首址存放在內(nèi)存的一個(gè)專(zhuān)用區(qū)域中。該方式實(shí)現(xiàn)簡(jiǎn)單、開(kāi)銷(xiāo)小，但每次查找時(shí)都需要掃描整張表，因此適合進(jìn)程數(shù)目不多的系統(tǒng)。圖2-10示出了線性表的PCB組織方式。 4040第二章 進(jìn)程的描述與控制圖2-10 PCB線性表示意圖 41 41第二章 進(jìn)程的描述與控制(2) 鏈接方式，即把具有相同狀態(tài)進(jìn)程的PCB分別通過(guò)PCB中的鏈接字鏈接成一個(gè)隊(duì)列。這樣，可以形成就緒隊(duì)列、若干個(gè)阻塞隊(duì)列和空白隊(duì)

21、列等。對(duì)就緒隊(duì)列而言，往往按進(jìn)程的優(yōu)先級(jí)將PCB從高到低進(jìn)行排列，將優(yōu)先級(jí)高的進(jìn)程PCB排在隊(duì)列的前面。同樣，也可把處于阻塞狀態(tài)進(jìn)程的PCB根據(jù)其阻塞原因的不同，排成多個(gè)阻塞隊(duì)列，如等待I/O操作完成的隊(duì)列和等待分配內(nèi)存的隊(duì)列等。圖2-11示出了一種鏈接隊(duì)列的組織方式。4242第二章 進(jìn)程的描述與控制圖2-11 PCB鏈接隊(duì)列示意圖4343第二章 進(jìn)程的描述與控制(3) 索引方式，即系統(tǒng)根據(jù)所有進(jìn)程狀態(tài)的不同，建立幾張索引表，例如，就緒索引表、阻塞索引表等，并把各索引表在內(nèi)存的首地址記錄在內(nèi)存的一些專(zhuān)用單元中。在每個(gè)索引表的表目中，記錄具有相應(yīng)狀態(tài)的某個(gè)PCB在PCB表中的地址。圖2-12示出

22、了索引方式的PCB組織。4444第二章 進(jìn)程的描述與控制圖2-12 按索引方式組織PCB4545第二章 進(jìn)程的描述與控制2.3 進(jìn) 程 控 制進(jìn)程控制是進(jìn)程管理中最基本的功能，主要包括創(chuàng)建新進(jìn)程、終止已完成的進(jìn)程、將因發(fā)生異常情況而無(wú)法繼續(xù)運(yùn)行的進(jìn)程置于阻塞狀態(tài)、負(fù)責(zé)進(jìn)程運(yùn)行中的狀態(tài)轉(zhuǎn)換等功能。如當(dāng)一個(gè)正在執(zhí)行的進(jìn)程因等待某事件而暫時(shí)不能繼續(xù)執(zhí)行時(shí)，將其轉(zhuǎn)變?yōu)樽枞麪顟B(tài)，而在該進(jìn)程所期待的事件出現(xiàn)后，又將該進(jìn)程轉(zhuǎn)換為就緒狀態(tài)等。進(jìn)程控制一般是由OS的內(nèi)核中的原語(yǔ)來(lái)實(shí)現(xiàn)的。4646第二章 進(jìn)程的描述與控制2.3.1 操作系統(tǒng)內(nèi)核1. 支撐功能(1) 中斷處理。(2) 時(shí)鐘管理。(3) 原語(yǔ)操作。4

23、747第二章 進(jìn)程的描述與控制2. 資源管理功能(1) 進(jìn)程管理。(2) 存儲(chǔ)器管理。(3) 設(shè)備管理。 4848第二章 進(jìn)程的描述與控制2.3.2 進(jìn)程的創(chuàng)建1. 進(jìn)程的層次結(jié)構(gòu)在OS中，允許一個(gè)進(jìn)程創(chuàng)建另一個(gè)進(jìn)程，通常把創(chuàng)建進(jìn)程的進(jìn)程稱(chēng)為父進(jìn)程，而把被創(chuàng)建的進(jìn)程稱(chēng)為子進(jìn)程。子進(jìn)程可繼續(xù)創(chuàng)建更多的孫進(jìn)程，由此便形成了一個(gè)進(jìn)程的層次結(jié)構(gòu)。如在UNIX中，進(jìn)程與其子孫進(jìn)程共同組成一個(gè)進(jìn)程家族(組)。4949第二章 進(jìn)程的描述與控制2. 進(jìn)程圖為了形象地描述一個(gè)進(jìn)程的家族關(guān)系而引入了進(jìn)程圖(Process Graph)。所謂進(jìn)程圖就是用于描述進(jìn)程間關(guān)系的一棵有向樹(shù)，如圖2-13所示。 5050第二

24、章 進(jìn)程的描述與控制圖2-13 進(jìn)程樹(shù)51 51第二章 進(jìn)程的描述與控制3. 引起創(chuàng)建進(jìn)程的事件為使程序之間能并發(fā)運(yùn)行，應(yīng)先為它們分別創(chuàng)建進(jìn)程。導(dǎo)致一個(gè)進(jìn)程去創(chuàng)建另一個(gè)進(jìn)程的典型事件有四類(lèi)：(1) 用戶(hù)登錄。(2) 作業(yè)調(diào)度。(3) 提供服務(wù)。(4) 應(yīng)用請(qǐng)求。 5252第二章 進(jìn)程的描述與控制4. 進(jìn)程的創(chuàng)建(Creation of Process)在系統(tǒng)中每當(dāng)出現(xiàn)了創(chuàng)建新進(jìn)程的請(qǐng)求后，OS便調(diào)用進(jìn)程創(chuàng)建原語(yǔ)Creat按下述步驟創(chuàng)建一個(gè)新進(jìn)程：(1) 申請(qǐng)空白PCB，為新進(jìn)程申請(qǐng)獲得唯一的數(shù)字標(biāo)識(shí)符，并從PCB集合中索取一個(gè)空白PCB。(2) 為新進(jìn)程分配其運(yùn)行所需的資源，包括各種物理和邏輯

25、資源，如內(nèi)存、文件、I/O設(shè)備和CPU時(shí)間等。(3) 初始化進(jìn)程控制塊(PCB)。(4) 如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程，便將新進(jìn)程插入就緒隊(duì)列。5353第二章 進(jìn)程的描述與控制2.3.3 進(jìn)程的終止1. 引起進(jìn)程終止(Termination of Process)的事件(1) 正常結(jié)束(2) 異常結(jié)束(3) 外界干預(yù) 5454第二章 進(jìn)程的描述與控制2. 進(jìn)程的終止過(guò)程如果系統(tǒng)中發(fā)生了要求終止進(jìn)程的某事件，OS便調(diào)用進(jìn)程終止原語(yǔ)，按下述過(guò)程去終止指定的進(jìn)程：(1) 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)；(2) 若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止

26、該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度；5555第二章 進(jìn)程的描述與控制(3) 若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程也都予以終止，以防它們成為不可控的進(jìn)程；(4) 將被終止進(jìn)程所擁有的全部資源或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)；(5) 將被終止進(jìn)程(PCB)從所在隊(duì)列(或鏈表)中移出，等待其它程序來(lái)搜集信息。5656第二章 進(jìn)程的描述與控制2.3.4 進(jìn)程的阻塞與喚醒1. 引起進(jìn)程阻塞和喚醒的事件有下述幾類(lèi)事件會(huì)引起進(jìn)程阻塞或被喚醒：(1) 向系統(tǒng)請(qǐng)求共享資源失敗。(2) 等待某種操作的完成。(3) 新數(shù)據(jù)尚未到達(dá)。(4) 等待新任務(wù)的到達(dá)。 5757第二章

27、 進(jìn)程的描述與控制2. 進(jìn)程阻塞過(guò)程正在執(zhí)行的進(jìn)程，如果發(fā)生了上述某事件，進(jìn)程便通過(guò)調(diào)用阻塞原語(yǔ)block將自己阻塞?？梢?jiàn)，阻塞是進(jìn)程自身的一種主動(dòng)行為。進(jìn)入block過(guò)程后，由于該進(jìn)程還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列。如果系統(tǒng)中設(shè)置了因不同事件而阻塞的多個(gè)阻塞隊(duì)列，則應(yīng)將本進(jìn)程插入到具有相同事件的阻塞隊(duì)列。最后，轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀態(tài)，按新進(jìn)程的PCB中的處理機(jī)狀態(tài)設(shè)置CPU的環(huán)境。 5858第二章 進(jìn)程的描述與控制3. 進(jìn)程喚醒過(guò)程當(dāng)被阻塞進(jìn)程所

28、期待的事件發(fā)生時(shí)，比如它所啟動(dòng)的I/O操作已完成，或其所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程(比如提供數(shù)據(jù)的進(jìn)程)調(diào)用喚醒原語(yǔ)wakeup，將等待該事件的進(jìn)程喚醒。wakeup執(zhí)行的過(guò)程是：首先把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該P(yáng)CB插入到就緒隊(duì)列中。5959第二章 進(jìn)程的描述與控制2.3.5 進(jìn)程的掛起與激活1. 進(jìn)程的掛起2. 進(jìn)程的激活過(guò)程6060第二章 進(jìn)程的描述與控制2.4進(jìn) 程 同 步在OS中引入進(jìn)程后，一方面可以使系統(tǒng)中的多道程序并發(fā)執(zhí)行，這不僅能有效地改善資源利用率，還可顯著地提高系統(tǒng)的吞吐量，但另一方面卻使系統(tǒng)變得更加復(fù)雜

29、。如果不能采取有效的措施，對(duì)多個(gè)進(jìn)程的運(yùn)行進(jìn)行妥善的管理，必然會(huì)因?yàn)檫@些進(jìn)程對(duì)系統(tǒng)資源的無(wú)序爭(zhēng)奪給系統(tǒng)造成混亂。致使每次處理的結(jié)果存在著不確定性，即顯現(xiàn)出其不可再現(xiàn)性。61 61第二章 進(jìn)程的描述與控制2.4.1進(jìn)程同步的基本概念1. 兩種形式的制約關(guān)系1) 間接相互制約關(guān)系2) 直接相互制約關(guān)系6262第二章 進(jìn)程的描述與控制2. 臨界資源(Critical Resouce)在第一章中我們?cè)?jīng)介紹過(guò)，許多硬件資源如打印機(jī)、 磁帶機(jī)等，都屬于臨界資源，諸進(jìn)程間應(yīng)采取互斥方式，實(shí)現(xiàn)對(duì)這種資源的共享。 6363第二章 進(jìn)程的描述與控制3. 臨界區(qū)(critical section)由前所述可知，不

30、論是硬件臨界資源還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪問(wèn)。人們把在每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱(chēng)為臨界區(qū)(critical section)。 6464第二章 進(jìn)程的描述與控制4. 同步機(jī)制應(yīng)遵循的規(guī)則為實(shí)現(xiàn)進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，可用軟件方法，更多的是在系統(tǒng)中設(shè)置專(zhuān)門(mén)的同步機(jī)構(gòu)來(lái)協(xié)調(diào)各進(jìn)程間的運(yùn)行。所有同步機(jī)制都應(yīng)遵循下述四條準(zhǔn)則：(1) 空閑讓進(jìn)。(2) 忙則等待。(3) 有限等待。(4) 讓權(quán)等待。6565第二章 進(jìn)程的描述與控制2.4.2 硬件同步機(jī)制雖然可以利用軟件方法解決諸進(jìn)程互斥進(jìn)入臨界區(qū)的問(wèn)題，但有一定難度，并且存在很大的局限性，因而現(xiàn)在已很少采用。相應(yīng)地，目前

31、許多計(jì)算機(jī)已提供了一些特殊的硬件指令，允許對(duì)一個(gè)字中的內(nèi)容進(jìn)行檢測(cè)和修正，或者是對(duì)兩個(gè)字的內(nèi)容進(jìn)行交換等?？衫眠@些特殊的指令來(lái)解決臨界區(qū)問(wèn)題。 6666第二章 進(jìn)程的描述與控制1. 關(guān)中斷關(guān)中斷是實(shí)現(xiàn)互斥的最簡(jiǎn)單的方法之一。在進(jìn)入鎖測(cè)試之前關(guān)閉中斷，直到完成鎖測(cè)試并上鎖之后才能打開(kāi)中斷。這樣，進(jìn)程在臨界區(qū)執(zhí)行期間，計(jì)算機(jī)系統(tǒng)不響應(yīng)中斷，從而不會(huì)引發(fā)調(diào)度，也就不會(huì)發(fā)生進(jìn)程或線程切換。由此，保證了對(duì)鎖的測(cè)試和關(guān)鎖操作的連續(xù)性和完整性，有效地保證了互斥。但是，關(guān)中斷的方法存在許多缺點(diǎn)： 濫用關(guān)中斷權(quán)力可能導(dǎo)致嚴(yán)重后果； 關(guān)中斷時(shí)間過(guò)長(zhǎng)，會(huì)影響系統(tǒng)效率，限制了處理器交叉執(zhí)行程序的能力； 關(guān)中斷方法也

32、不適用于多CPU 系統(tǒng)，因?yàn)樵谝粋€(gè)處理器上關(guān)中斷并不能防止進(jìn)程在其它處理器上執(zhí)行相同的臨界段代碼。6767第二章 進(jìn)程的描述與控制這是一種借助一條硬件指令“測(cè)試并建立”指令TS(Test-and-Set)以實(shí)現(xiàn)互斥的方法。在許多計(jì)算機(jī)中都提供了這種指令。 6868第二章 進(jìn)程的描述與控制該指令稱(chēng)為對(duì)換指令，在Intel 80 x86中又稱(chēng)為XCHG指令，用于交換兩個(gè)字的內(nèi)容。 6969第二章 進(jìn)程的描述與控制2.4.3信號(hào)量機(jī)制1. 整型信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)用于表示資源數(shù)目的整型量S，它與一般整型量不同，除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作(Atomic Ope

33、ration) wait(S)和signal(S)來(lái)訪問(wèn)。很長(zhǎng)時(shí)間以來(lái)，這兩個(gè)操作一直被分別稱(chēng)為P、V操作。 7070第二章 進(jìn)程的描述與控制2. 記錄型信號(hào)量在整型信號(hào)量機(jī)制中的wait操作，只要是信號(hào)量S0，就會(huì)不斷地測(cè)試。因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則，而是使進(jìn)程處于“忙等”的狀態(tài)。記錄型信號(hào)量機(jī)制則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問(wèn)同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表指針list，用于鏈接上述的所有等待進(jìn)程。 71 71第二章 進(jìn)程的描述與

34、控制3. AND型信號(hào)量前面所述的進(jìn)程互斥問(wèn)題針對(duì)的是多個(gè)并發(fā)進(jìn)程僅共享一個(gè)臨界資源的情況。在有些應(yīng)用場(chǎng)合，是一個(gè)進(jìn)程往往需要獲得兩個(gè)或更多的共享資源后方能執(zhí)行其任務(wù)。假定現(xiàn)有兩個(gè)進(jìn)程A和B，它們都要求訪問(wèn)共享數(shù)據(jù)D和E，當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。 7272第二章 進(jìn)程的描述與控制4. 信號(hào)量集在前面所述的記錄型信號(hào)量機(jī)制中，wait(S)或signal(S)操作僅能對(duì)信號(hào)量施以加1或減1操作，意味著每次只能對(duì)某類(lèi)臨界資源進(jìn)行一個(gè)單位的申請(qǐng)或釋放。當(dāng)一次需要N個(gè)單位時(shí)，便要進(jìn)行N次wait(S)操作，這顯然是低效的，甚至?xí)黾铀梨i的概率。此外，在有些情況下，為確保系統(tǒng)的安全性，當(dāng)所申請(qǐng)的

35、資源數(shù)量低于某一下限值時(shí)，還必須進(jìn)行管制，不予以分配。因此，當(dāng)進(jìn)程申請(qǐng)某類(lèi)臨界資源時(shí)，在每次分配之前，都必須測(cè)試資源的數(shù)量，判斷是否大于可分配的下限值，決定是否予以分配。7373第二章 進(jìn)程的描述與控制2.4.4信號(hào)量的應(yīng)用1. 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥為使多個(gè)進(jìn)程能互斥地訪問(wèn)某臨界資源，只需為該資源設(shè)置一互斥信號(hào)量mutex，并設(shè)其初始值為1，然后將各進(jìn)程訪問(wèn)該資源的臨界區(qū)CS置于wait(mutex)和signal(mutex)操作之間即可。 7474第二章 進(jìn)程的描述與控制2. 利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系還可利用信號(hào)量來(lái)描述程序或語(yǔ)句之間的前趨關(guān)系。設(shè)有兩個(gè)并發(fā)執(zhí)行的進(jìn)程P1和P2。P1中有語(yǔ)

36、句S1；P2中有語(yǔ)句S2。我們希望在S1執(zhí)行后再執(zhí)行S2。為實(shí)現(xiàn)這種前趨關(guān)系，只需使進(jìn)程P1和P2共享一個(gè)公用信號(hào)量S，并賦予其初值為0，將signal(S)操作放在語(yǔ)句S1后面，而在S2語(yǔ)句前面插入wait(S)操作，即在進(jìn)程P1中，用S1；signal(S)；在進(jìn)程P2中，用wait(S)；S2；7575第二章 進(jìn)程的描述與控制由于S被初始化為0，這樣，若P2先執(zhí)行必定阻塞，只有在進(jìn)程P1執(zhí)行完S1； signal(S)；操作后使S增為1時(shí)，P2進(jìn)程方能成功執(zhí)行語(yǔ)句S2。同樣，我們可以利用信號(hào)量按照語(yǔ)句間的前趨關(guān)系(見(jiàn)圖2-14)，寫(xiě)出一個(gè)更為復(fù)雜的可并發(fā)執(zhí)行的程序。 7676第二章 進(jìn)程

37、的描述與控制圖2-14 前趨圖舉例7777第二章 進(jìn)程的描述與控制2.4.5管程機(jī)制1管程的定義系統(tǒng)中的各種硬件資源和軟件資源均可用數(shù)據(jù)結(jié)構(gòu)抽象地描述其資源特性，即用少量信息和對(duì)該資源所執(zhí)行的操作來(lái)表征該資源，而忽略它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。 7878第二章 進(jìn)程的描述與控制由上述的定義可知，管程由四部分組成： 管程的名稱(chēng)； 局部于管程的共享數(shù)據(jù)結(jié)構(gòu)說(shuō)明； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程； 對(duì)局部于管程的共享數(shù)據(jù)設(shè)置初始值的語(yǔ)句。圖2-15是一個(gè)管程的示意圖。7979第二章 進(jìn)程的描述與控制圖2-15管程的示意圖8080第二章 進(jìn)程的描述與控制2. 條件變量在利用管程實(shí)現(xiàn)進(jìn)程同步時(shí)，必須設(shè)置同

38、步工具，如兩個(gè)同步操作原語(yǔ)wait和signal。當(dāng)某進(jìn)程通過(guò)管程請(qǐng)求獲得臨界資源而未能滿(mǎn)足時(shí)，管程便調(diào)用wait原語(yǔ)使該進(jìn)程等待，并將其排在等待隊(duì)列上，如圖2-13所示。僅當(dāng)另一進(jìn)程訪問(wèn)完成并釋放該資源之后，管程才又調(diào)用signal原語(yǔ)，喚醒等待隊(duì)列中的隊(duì)首進(jìn)程。81 81第二章 進(jìn)程的描述與控制2.5經(jīng)典進(jìn)程的同步問(wèn)題在多道程序環(huán)境下，進(jìn)程同步問(wèn)題十分重要，也是相當(dāng)有趣的問(wèn)題，因而吸引了不少學(xué)者對(duì)它進(jìn)行研究，由此而產(chǎn)生了一系列經(jīng)典的進(jìn)程同步問(wèn)題，其中較有代表性的是“生產(chǎn)者消費(fèi)者”問(wèn)題、“讀者寫(xiě)者問(wèn)題”、“哲學(xué)家進(jìn)餐問(wèn)題”等等。通過(guò)對(duì)這些問(wèn)題的研究和學(xué)習(xí)，可以幫助我們更好地理解進(jìn)程同步的概念

39、及實(shí)現(xiàn)方法。8282第二章 進(jìn)程的描述與控制2.5.1生產(chǎn)者-消費(fèi)者問(wèn)題1. 利用記錄型信號(hào)量解決生產(chǎn)者-消費(fèi)者問(wèn)題假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中具有n個(gè)緩沖區(qū)，這時(shí)可利用互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用；利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿(mǎn)緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿(mǎn)，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息。 8383第二章 進(jìn)程的描述與控制2. 利用AND信號(hào)量解決生產(chǎn)者-消費(fèi)者問(wèn)題對(duì)于生產(chǎn)者-消費(fèi)者問(wèn)題，也可利用AND信號(hào)量來(lái)解決，即用Swait(empty，mutex)

40、來(lái)代替wait(empty)和wait(mutex)；用Ssignal(mutex，full)來(lái)代替signal(mutex)和signal(full)；用Swait(full，mutex)代替wait(full)和wait(mutex)，以及用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。 8484第二章 進(jìn)程的描述與控制3. 利用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題在利用管程方法來(lái)解決生產(chǎn)者-消費(fèi)者問(wèn)題時(shí)，首先便是為它們建立一個(gè)管程，并命名為procducerconsumer，或簡(jiǎn)稱(chēng)為PC。其中包括兩個(gè)過(guò)程：(1) put(x)過(guò)程。(2) ge

41、t(x)過(guò)程。 8585第二章 進(jìn)程的描述與控制對(duì)于條件變量notfull和notempty，分別有兩個(gè)過(guò)程cwait和csignal對(duì)它們進(jìn)行操作：(1) cwait(condition)過(guò)程：當(dāng)管程被一個(gè)進(jìn)程占用時(shí)，其他進(jìn)程調(diào)用該過(guò)程時(shí)阻塞，并掛在條件condition的隊(duì)列上。(2) csignal(condition)過(guò)程：?jiǎn)拘言赾wait執(zhí)行后阻塞在條件condition隊(duì)列上的進(jìn)程，如果這樣的進(jìn)程不止一個(gè)，則選擇其中一個(gè)實(shí)施喚醒操作；如果隊(duì)列為空，則無(wú)操作而返回。8686第二章 進(jìn)程的描述與控制2.5.2哲學(xué)家進(jìn)餐問(wèn)題1. 利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題經(jīng)分析可知，放在桌子上的

42、筷子是臨界資源，在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使用，可以用一個(gè)信號(hào)量表示一只筷子，由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。 8787第二章 進(jìn)程的描述與控制2. 利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題在哲學(xué)家進(jìn)餐問(wèn)題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問(wèn)題，故用AND信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法。8888第二章 進(jìn)程的描述與控制2.5.3讀者-寫(xiě)者問(wèn)題1. 利用記錄型信號(hào)量解決讀者-寫(xiě)者問(wèn)題為實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號(hào)量Wmutex。另外，再設(shè)置一個(gè)整型變量Readcount表示

43、正在讀的進(jìn)程數(shù)目。由于只要有一個(gè)Reader進(jìn)程在讀，便不允許Writer進(jìn)程去寫(xiě)。因此，僅當(dāng)Readcount=0，表示尚無(wú)Reader進(jìn)程在讀時(shí)，Reader進(jìn)程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。 8989第二章 進(jìn)程的描述與控制2. 利用信號(hào)量集機(jī)制解決讀者-寫(xiě)者問(wèn)題這里的讀者寫(xiě)者問(wèn)題，與前面的略有不同，它增加了一個(gè)限制，即最多只允許RN個(gè)讀者同時(shí)讀。為此，又引入了一個(gè)信號(hào)量L，并賦予其初值為RN，通過(guò)執(zhí)行wait(L, 1, 1)操作來(lái)控制讀者的數(shù)目，每當(dāng)有一個(gè)讀者進(jìn)入時(shí)，就要先執(zhí)

44、行wait(L, 1, 1)操作，使L的值減1。當(dāng)有RN個(gè)讀者進(jìn)入讀后，L便減為0，第RN+1個(gè)讀者要進(jìn)入讀時(shí)，必然會(huì)因wait(L, 1, 1)操作失敗而阻塞。 9090第二章 進(jìn)程的描述與控制2.6 進(jìn) 程 通 信進(jìn)程通信是指進(jìn)程之間的信息交換。由于進(jìn)程的互斥與同步，需要在進(jìn)程間交換一定的信息，故不少學(xué)者將它們也歸為進(jìn)程通信，但只能把它們稱(chēng)為低級(jí)進(jìn)程通信。我們以信號(hào)量機(jī)制為例來(lái)說(shuō)明，它們之所以低級(jí)的原因在于： 效率低，生產(chǎn)者每次只能向緩沖池投放一個(gè)產(chǎn)品(消息)，消費(fèi)者每次只能從緩沖區(qū)中取得一個(gè)消息； 通信對(duì)用戶(hù)不透明，OS只為進(jìn)程之間的通信提供了共享存儲(chǔ)器。 91 91第二章 進(jìn)程的描述與

45、控制在進(jìn)程之間要傳送大量數(shù)據(jù)時(shí)，應(yīng)當(dāng)利用OS提供的高級(jí)通信工具，該工具最主要的特點(diǎn)是：(1) 使用方便。OS隱藏了實(shí)現(xiàn)進(jìn)程通信的具體細(xì)節(jié)，向用戶(hù)提供了一組用于實(shí)現(xiàn)高級(jí)通信的命令(原語(yǔ))，用戶(hù)可方便地直接利用它實(shí)現(xiàn)進(jìn)程之間的通信?；蛘哒f(shuō)，通信過(guò)程對(duì)用戶(hù)是透明的。這樣就大大減少了通信程序編制上的復(fù)雜性。(2) 高效地傳送大量數(shù)據(jù)。用戶(hù)可直接利用高級(jí)通信命令(原語(yǔ))高效地傳送大量的數(shù)據(jù)。9292第二章 進(jìn)程的描述與控制2.6.1進(jìn)程通信的類(lèi)型1. 共享存儲(chǔ)器系統(tǒng)(Shared-Memory System)在共享存儲(chǔ)器系統(tǒng)中，相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū)，進(jìn)程之間能夠通過(guò)這些空間進(jìn)行通信

46、。據(jù)此，又可把它們分成以下兩種類(lèi)型：(1) 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。(2) 基于共享存儲(chǔ)區(qū)的通信方式。9393第二章 進(jìn)程的描述與控制2. 管道(pipe)通信系統(tǒng)所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程以實(shí)現(xiàn)它們之間通信的一個(gè)共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫(xiě)進(jìn)程)以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱(chēng)為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它操作系統(tǒng)中。9494第二章 進(jìn)程的描述與控制為了

47、協(xié)調(diào)雙方的通信，管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力： 互斥，即當(dāng)一個(gè)進(jìn)程正在對(duì)pipe執(zhí)行讀/寫(xiě)操作時(shí)，其它(另一)進(jìn)程必須等待。 同步，指當(dāng)寫(xiě)(輸入)進(jìn)程把一定數(shù)量(如4KB)的數(shù)據(jù)寫(xiě)入pipe，便去睡眠等待，直到讀(輸出)進(jìn)程取走數(shù)據(jù)后再把它喚醒。當(dāng)讀進(jìn)程讀一空pipe時(shí)，也應(yīng)睡眠等待，直至寫(xiě)進(jìn)程將數(shù)據(jù)寫(xiě)入管道后才將之喚醒。 確定對(duì)方是否存在，只有確定了對(duì)方已存在時(shí)才能進(jìn)行通信。9595第二章 進(jìn)程的描述與控制在該機(jī)制中，進(jìn)程不必借助任何共享存儲(chǔ)區(qū)或數(shù)據(jù)結(jié)構(gòu)，而是以格式化的消息 (message)為單位，將通信的數(shù)據(jù)封裝在消息中，并利用操作系統(tǒng)提供的一組通信命令(原語(yǔ))，在進(jìn)程間進(jìn)行消息

48、傳遞，完成進(jìn)程間的數(shù)據(jù)交換?；谙鬟f系統(tǒng)的通信方式屬于高級(jí)通信方式，因其實(shí)現(xiàn)方式的不同，可進(jìn)一步分成兩類(lèi)：(1) 直接通信方式(2) 間接通信方式 9696第二章 進(jìn)程的描述與控制4. 客戶(hù)機(jī)-服務(wù)器系統(tǒng)(Client-Server system)1) 套接字(Socket)套接字起源于20世紀(jì)70年代加州大學(xué)伯克利分校版本的UNIX(即BSD Unix)，是UNIX 操作系統(tǒng)下的網(wǎng)絡(luò)通信接口。一開(kāi)始，套接字被設(shè)計(jì)用在同一臺(tái)主機(jī)上多個(gè)應(yīng)用程序之間的通信(即進(jìn)程間的通信)，主要是為了解決多對(duì)進(jìn)程同時(shí)通信時(shí)端口和物理線路的多路復(fù)用問(wèn)題。隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展以及UNIX 操作系統(tǒng)的廣泛使用，

49、套接字已逐漸成為最流行的網(wǎng)絡(luò)通信程序接口之一。9797第二章 進(jìn)程的描述與控制2) 遠(yuǎn)程過(guò)程調(diào)用和遠(yuǎn)程方法調(diào)用遠(yuǎn)程過(guò)程(函數(shù))調(diào)用RPC(Remote Procedure Call)，是一個(gè)通信協(xié)議，用于通過(guò)網(wǎng)絡(luò)連接的系統(tǒng)。該協(xié)議允許運(yùn)行于一臺(tái)主機(jī)(本地)系統(tǒng)上的進(jìn)程調(diào)用另一臺(tái)主機(jī)(遠(yuǎn)程)系統(tǒng)上的進(jìn)程，而對(duì)程序員表現(xiàn)為常規(guī)的過(guò)程調(diào)用，無(wú)需額外地為此編程。如果涉及的軟件采用面向?qū)ο缶幊?，那么遠(yuǎn)程過(guò)程調(diào)用亦可稱(chēng)做遠(yuǎn)程方法調(diào)用。9898第二章 進(jìn)程的描述與控制實(shí)際上，遠(yuǎn)程過(guò)程調(diào)用的主要步驟是：(1) 本地過(guò)程調(diào)用者以一般方式調(diào)用遠(yuǎn)程過(guò)程在本地關(guān)聯(lián)的客戶(hù)存根，傳遞相應(yīng)的參數(shù)，然后將控制權(quán)轉(zhuǎn)移給客戶(hù)存根

50、；(2) 客戶(hù)存根執(zhí)行，完成包括過(guò)程名和調(diào)用參數(shù)等信息的消息建立，將控制權(quán)轉(zhuǎn)移給本地客戶(hù)進(jìn)程；(3) 本地客戶(hù)進(jìn)程完成與服務(wù)器的消息傳遞，將消息發(fā)送到遠(yuǎn)程服務(wù)器進(jìn)程；(4) 遠(yuǎn)程服務(wù)器進(jìn)程接收消息后轉(zhuǎn)入執(zhí)行，并根據(jù)其中的遠(yuǎn)程過(guò)程名找到對(duì)應(yīng)的服務(wù)器存根，將消息轉(zhuǎn)給該存根；9999第二章 進(jìn)程的描述與控制(5) 該服務(wù)器存根接到消息后，由阻塞狀態(tài)轉(zhuǎn)入執(zhí)行狀態(tài)，拆開(kāi)消息從中取出過(guò)程調(diào)用的參數(shù)，然后以一般方式調(diào)用服務(wù)器上關(guān)聯(lián)的過(guò)程；(6) 在服務(wù)器端的遠(yuǎn)程過(guò)程運(yùn)行完畢后，將結(jié)果返回給與之關(guān)聯(lián)的服務(wù)器存根；(7) 該服務(wù)器存根獲得控制權(quán)運(yùn)行，將結(jié)果打包為消息，并將控制權(quán)轉(zhuǎn)移給遠(yuǎn)程服務(wù)器進(jìn)程；(8) 遠(yuǎn)程

51、服務(wù)器進(jìn)程將消息發(fā)送回客戶(hù)端；(9) 本地客戶(hù)進(jìn)程接收到消息后，根據(jù)其中的過(guò)程名將消息存入關(guān)聯(lián)的客戶(hù)存根，再將控制權(quán)轉(zhuǎn)移給客戶(hù)存根；(10) 客戶(hù)存根從消息中取出結(jié)果，返回給本地調(diào)用者進(jìn)程，并完成控制權(quán)的轉(zhuǎn)移。100100第二章 進(jìn)程的描述與控制2.6.2消息傳遞通信的實(shí)現(xiàn)方式1. 直接消息傳遞系統(tǒng)在直接消息傳遞系統(tǒng)中采用直接通信方式，即發(fā)送進(jìn)程利用OS所提供的發(fā)送命令(原語(yǔ))，直接把消息發(fā)送給目標(biāo)進(jìn)程。101101第二章 進(jìn)程的描述與控制1) 直接通信原語(yǔ)(1) 對(duì)稱(chēng)尋址方式。(2) 非對(duì)稱(chēng)尋址方式。102102第二章 進(jìn)程的描述與控制2) 消息的格式在消息傳遞系統(tǒng)中所傳遞的消息，必須具有一

52、定的消息格式。在單機(jī)系統(tǒng)環(huán)境中，由于發(fā)送進(jìn)程和接收進(jìn)程處于同一臺(tái)機(jī)器中，有著相同的環(huán)境，所以消息的格式比較簡(jiǎn)單，可采用比較短的定長(zhǎng)消息格式，以減少對(duì)消息的處理和存儲(chǔ)開(kāi)銷(xiāo)。該方式可用于辦公自動(dòng)化系統(tǒng)中，為用戶(hù)提供快速的便箋式通信。但這種方式對(duì)于需要發(fā)送較長(zhǎng)消息的用戶(hù)是不方便的。為此，可采用變長(zhǎng)的消息格式，即進(jìn)程所發(fā)送消息的長(zhǎng)度是可變的。對(duì)于變長(zhǎng)消息，系統(tǒng)無(wú)論在處理方面還是存儲(chǔ)方面，都可能會(huì)付出更多的開(kāi)銷(xiāo)，但其優(yōu)點(diǎn)在于方便了用戶(hù)。103103第二章 進(jìn)程的描述與控制3) 進(jìn)程的同步方式在進(jìn)程之間進(jìn)行通信時(shí)，同樣需要有進(jìn)程同步機(jī)制，以使諸進(jìn)程間能協(xié)調(diào)通信。不論是發(fā)送進(jìn)程還是接收進(jìn)程，在完成消息的發(fā)送

53、或接收后，都存在兩種可能性，即進(jìn)程或者繼續(xù)發(fā)送(或接收)或者阻塞。 104104第二章 進(jìn)程的描述與控制4) 通信鏈路為使在發(fā)送進(jìn)程和接收進(jìn)程之間能進(jìn)行通信，必須在兩者之間建立一條通信鏈路。有兩種方式建立通信鏈路。第一種方式是：由發(fā)送進(jìn)程在通信之前用顯式的“建立連接”命令(原語(yǔ))請(qǐng)求系統(tǒng)為之建立一條通信鏈路，在鏈路使用完后拆除鏈路。 105105第二章 進(jìn)程的描述與控制2. 信箱通信1) 信箱的結(jié)構(gòu)信箱定義為一種數(shù)據(jù)結(jié)構(gòu)。在邏輯上，可以將其分為兩個(gè)部分：(1) 信箱頭(2) 信箱體106106第二章 進(jìn)程的描述與控制圖2-16 雙向信箱示意圖107107第二章 進(jìn)程的描述與控制2) 信箱通信原

54、語(yǔ)系統(tǒng)為郵箱通信提供了若干條原語(yǔ)，分別用于：(1) 郵箱的創(chuàng)建和撤消。(2) 消息的發(fā)送和接收。108108第二章 進(jìn)程的描述與控制3) 信箱的類(lèi)型郵箱可由操作系統(tǒng)創(chuàng)建，也可由用戶(hù)進(jìn)程創(chuàng)建，創(chuàng)建者是郵箱的擁有者。據(jù)此，可把郵箱分為以下三類(lèi)：(1) 私用郵箱。(2) 公用郵箱。(3) 共享郵箱。 109109第二章 進(jìn)程的描述與控制2.6.3直接消息傳遞系統(tǒng)實(shí)例消息緩沖隊(duì)列通信機(jī)制首先由美國(guó)的Hansan提出，并在RC 4000系統(tǒng)上實(shí)現(xiàn)，后來(lái)被廣泛應(yīng)用于本地進(jìn)程之間的通信中。在這種通信機(jī)制中，發(fā)送進(jìn)程利用Send原語(yǔ)將消息直接發(fā)送給接收進(jìn)程；接收進(jìn)程則利用Receive原語(yǔ)接收消息。11011

55、0第二章 進(jìn)程的描述與控制1. 消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu)(1) 消息緩沖區(qū)。 (2) PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)。111111第二章 進(jìn)程的描述與控制2. 發(fā)送原語(yǔ)發(fā)送進(jìn)程在利用發(fā)送原語(yǔ)發(fā)送消息之前，應(yīng)先在自己的內(nèi)存空間設(shè)置一發(fā)送區(qū)a，如圖2-17所示，把待發(fā)送的消息正文、發(fā)送進(jìn)程標(biāo)識(shí)符、消息長(zhǎng)度等信息填入其中，然后調(diào)用發(fā)送原語(yǔ)，把消息發(fā)送給目標(biāo)(接收)進(jìn)程。發(fā)送原語(yǔ)首先根據(jù)發(fā)送區(qū)a中所設(shè)置的消息長(zhǎng)度a.size來(lái)申請(qǐng)一緩沖區(qū)i，接著，把發(fā)送區(qū)a中的信息復(fù)制到緩沖區(qū)i中。為了能將i掛在接收進(jìn)程的消息隊(duì)列mq上，應(yīng)先獲得接收進(jìn)程的內(nèi)部標(biāo)識(shí)符j，然后將i掛在j.mq上。由于該隊(duì)列屬于臨界資源

56、，故在執(zhí)行insert操作的前后都要執(zhí)行wait和signal操作。 112112第二章 進(jìn)程的描述與控制圖2-17消息緩沖通信113113第二章 進(jìn)程的描述與控制3. 接收原語(yǔ)接收進(jìn)程調(diào)用接收原語(yǔ)receive(b)，從自己的消息緩沖隊(duì)列mq中摘下第一個(gè)消息緩沖區(qū)i，并將其中的數(shù)據(jù)復(fù)制到以b為首址的指定消息接收區(qū)內(nèi)。 114114第二章 進(jìn)程的描述與控制2.7 線程(Threads)的基本概念2.7.1 線程的引入如果說(shuō)，在OS中引入進(jìn)程的目的是為了使多個(gè)程序能并發(fā)執(zhí)行，以提高資源利用率和系統(tǒng)吞吐量，那么，在操作系統(tǒng)中再引入線程，則是為了減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開(kāi)銷(xiāo)，使OS具有更好的

57、并發(fā)性。115115第二章 進(jìn)程的描述與控制1. 進(jìn)程的兩個(gè)基本屬性首先讓我們來(lái)回顧進(jìn)程的兩個(gè)基本屬性： 進(jìn)程是一個(gè)可擁有資源的獨(dú)立單位，一個(gè)進(jìn)程要能獨(dú)立運(yùn)行，它必須擁有一定的資源，包括用于存放程序正文、數(shù)據(jù)的磁盤(pán)和內(nèi)存地址空間，以及它在運(yùn)行時(shí)所需要的I/O設(shè)備、已打開(kāi)的文件、信號(hào)量等；116116第二章 進(jìn)程的描述與控制 進(jìn)程同時(shí)又是一個(gè)可獨(dú)立調(diào)度和分派的基本單位，一個(gè)進(jìn)程要能獨(dú)立運(yùn)行，它還必須是一個(gè)可獨(dú)立調(diào)度和分派的基本單位。每個(gè)進(jìn)程在系統(tǒng)中有唯一的PCB，系統(tǒng)可根據(jù)其PCB感知進(jìn)程的存在，也可以根據(jù)其PCB中的信息，對(duì)進(jìn)程進(jìn)行調(diào)度，還可將斷點(diǎn)信息保存在其PCB中。反之，再利用進(jìn)程PCB中

58、的信息來(lái)恢復(fù)進(jìn)程運(yùn)行的現(xiàn)場(chǎng)。正是由于進(jìn)程有這兩個(gè)基本屬性，才使進(jìn)程成為一個(gè)能獨(dú)立運(yùn)行的基本單位，從而也就構(gòu)成了進(jìn)程并發(fā)執(zhí)行的基礎(chǔ)。117117第二章 進(jìn)程的描述與控制2. 程序并發(fā)執(zhí)行所需付出的時(shí)空開(kāi)銷(xiāo)為使程序能并發(fā)執(zhí)行，系統(tǒng)必須進(jìn)行以下的一系列操作：(1) 創(chuàng)建進(jìn)程，系統(tǒng)在創(chuàng)建一個(gè)進(jìn)程時(shí)，必須為它分配其所必需的、除處理機(jī)以外的所有資源，如內(nèi)存空間、I/O設(shè)備，以及建立相應(yīng)的PCB；(2) 撤消進(jìn)程，系統(tǒng)在撤消進(jìn)程時(shí)，又必須先對(duì)其所占有的資源執(zhí)行回收操作，然后再撤消PCB；(3) 進(jìn)程切換，對(duì)進(jìn)程進(jìn)行上下文切換時(shí)，需要保留當(dāng)前進(jìn)程的CPU環(huán)境，設(shè)置新選中進(jìn)程的CPU環(huán)境，因而須花費(fèi)不少的處理機(jī)

59、時(shí)間。118118第二章 進(jìn)程的描述與控制3. 線程作為調(diào)度和分派的基本單位如何能使多個(gè)程序更好地并發(fā)執(zhí)行，同時(shí)又盡量減少系統(tǒng)的開(kāi)銷(xiāo)，已成為近年來(lái)設(shè)計(jì)操作系統(tǒng)時(shí)所追求的重要目標(biāo)。有不少研究操作系統(tǒng)的學(xué)者們想到，要設(shè)法將進(jìn)程的上述兩個(gè)屬性分開(kāi)，由OS分開(kāi)處理，亦即并不把作為調(diào)度和分派的基本單位也同時(shí)作為擁有資源的單位，以做到“輕裝上陣”；而對(duì)于擁有資源的基本單位，又不對(duì)之施以頻繁的切換。正是在這種思想的指導(dǎo)下，形成了線程的概念。119119第二章 進(jìn)程的描述與控制2.7.2 線程與進(jìn)程的比較1. 調(diào)度的基本單位2. 并發(fā)性3. 擁有資源 4. 獨(dú)立性5. 系統(tǒng)開(kāi)銷(xiāo)6. 支持多處理機(jī)系統(tǒng)12012

60、0第二章 進(jìn)程的描述與控制2.7.3 線程的狀態(tài)和線程控制塊1. 線程運(yùn)行的三個(gè)狀態(tài) 與傳統(tǒng)的進(jìn)程一樣，在各線程之間也存在著共享資源和相互合作的制約關(guān)系，致使線程在運(yùn)行時(shí)也具有間斷性。相應(yīng)地，線程在運(yùn)行時(shí)也具有下述三種基本狀態(tài)：(1) 執(zhí)行狀態(tài)，表示線程已獲得處理機(jī)而正在運(yùn)行；(2) 就緒狀態(tài)，指線程已具備了各種執(zhí)行條件，只須再獲得CPU便可立即執(zhí)行；(3) 阻塞狀態(tài)，指線程在執(zhí)行中因某事件受阻而處于暫停狀態(tài)，例如，當(dāng)一個(gè)線程執(zhí)行從鍵盤(pán)讀入數(shù)據(jù)的系統(tǒng)調(diào)用時(shí)，該線程就被阻塞。121121第二章 進(jìn)程的描述與控制2. 線程控制塊TCB如同每個(gè)進(jìn)程有一個(gè)進(jìn)程控制塊一樣，系統(tǒng)也為每個(gè)線程配置了一個(gè)線程