第二章進(jìn)程管理1進(jìn)程的基本概念2進(jìn)程控制3進(jìn)程同步4經(jīng)典進(jìn)程同步問題5管程機(jī)制6進(jìn)程通信7線程1進(jìn)程的基本概念操作系統(tǒng)的特性之一是并發(fā)與共享，即在系統(tǒng)(內(nèi)存)中同時(shí)存在幾個(gè)相互獨(dú)立的程序，這些程序在系統(tǒng)中既交叉地運(yùn)行，又要共享系統(tǒng)中的資源，這就會引起一系列的問題，包括：對資源的競爭、運(yùn)行程序之間的通信、程序之間的合作與協(xié)同等。要解決這些問題，用程序的概念已經(jīng)不能描述程序在內(nèi)存中運(yùn)行的狀態(tài)，必須引人新的概念－－進(jìn)程。前趨圖(PrecedenceGraph)是一個(gè)有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中每個(gè)結(jié)點(diǎn)可用于描述一條語句、一個(gè)程序段或進(jìn)程結(jié)點(diǎn)間的有向邊則表示在兩結(jié)點(diǎn)之間存在的偏序或前趨關(guān)系“→”，→={（Pi，Pj）|PimustcompletebeforePjmaystart}如果（Pi，Pj）∈→，可寫成Pi→Pj；，稱Pi是Pj的直接前趨，而Pj是Pi的直接后繼。在前趨圖中，沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(InitialNode)

，沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(FinalNode)

。2.1.1前趨圖S1→S2→S3

每個(gè)結(jié)點(diǎn)還可具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。前趨圖P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九個(gè)結(jié)點(diǎn)的前趨圖(b)具有循環(huán)的有向圖圖2－l示出的前趨圖，存在下面的前趨關(guān)系：P1→P2,P1→P3，P1→P4，P2→P5，P3→P5，P4→P6,P5→P7，P6→P7或表示為：P={P1,P2,P3,P4,P5,P6,P7}→={(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P5，P7)，(P6，P7)}注意：前趨圖中必須不存在循環(huán)。2.1.1前趨圖一、概念一個(gè)程序由若干個(gè)程序段組成，在各程序段之間，必須按照某種先后次序順序執(zhí)行，僅當(dāng)前一(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。例如：2.1.2程序的順序執(zhí)行1.順序性 處理機(jī)嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每個(gè)操作必須在下一個(gè)操作開始之前結(jié)束。2.封閉性 程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界的影響。3.可再現(xiàn)性 程序執(zhí)行的結(jié)果與初始條件有關(guān)，而與執(zhí)行時(shí)間無關(guān)。二、程序順序執(zhí)行的特點(diǎn)例：在系統(tǒng)中有n個(gè)作業(yè)，每個(gè)作業(yè)都有三個(gè)處理步驟，輸入數(shù)據(jù)、處理、輸出，即Ii,Ci,Pi(i=1,2,...,n)。這些作業(yè)在系統(tǒng)中執(zhí)行時(shí)是對時(shí)間的偏序，有些操作必須在其它操作之前執(zhí)行，這是有序的，但有些操作是可以同時(shí)執(zhí)行的。例如:I1、C1、P1的執(zhí)行必須嚴(yán)格按照I1，C1，P1的順序，而P1與I2，C1與I2,I3與P1是可以同時(shí)執(zhí)行的。圖中存在下面的前趨關(guān)系：Ii→Ci,Ii→Ii＋1,Ci→Pi,Ci→Ci＋1,Pi→Pi＋1而Ii＋1和Ci及Pi－1是重迭的，它們可以并發(fā)執(zhí)行。2.1.3程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行時(shí)的前趨圖例如:對于具有下列四條語句的程序段：S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+8;其前趨圖如右圖。其中S1和S2可以并發(fā)執(zhí)行。2.1.3程序的并發(fā)執(zhí)行及其特征程序并發(fā)執(zhí)行（定義）若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序的執(zhí)行在時(shí)間上是重迭的，一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始，即使這種重迭是很小的，也稱這幾個(gè)程序段是并發(fā)執(zhí)行的。2.1.3程序的并發(fā)執(zhí)行及其特征程序并發(fā)執(zhí)行的描述：

parbeginS1;S2;S3;...;SNparend; Si(i=1,2,3,...,n)表示n個(gè)語句（程序段），這n個(gè)語句用parbegin和parend括起來表示這n個(gè)語句是可以并發(fā)執(zhí)行的。這是Dijkstra提出的。2.1.3程序的并發(fā)執(zhí)行及其特征假設(shè)有一個(gè)程序由S0～Sn+1個(gè)語句，其中S1～Sn語句是并發(fā)執(zhí)行的，程序如下：

S0;parbeginS1;S2;S3;...;SNparend;Sn+1;2.1.3程序的并發(fā)執(zhí)行及其特征程序并發(fā)執(zhí)行時(shí)的特征1、間斷性(執(zhí)行—暫停—執(zhí)行)2、失去了程序的封閉性3、不可再現(xiàn)性(失去封閉性引起)2.1.3程序的并發(fā)執(zhí)行及其特征

例如，有兩個(gè)循環(huán)程序A和B，它們共享一個(gè)變量N。程序A每執(zhí)行一次時(shí)，都要做N∶=N+1操作；程序B每執(zhí)行一次時(shí)，都要執(zhí)行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運(yùn)行。可能出現(xiàn)以下三種情形：

(1)N∶=N+1在Print(N)和N∶=0之前，此時(shí)得到的N值分別為n+1,n+1,0。

(2)N∶=N+1在Print(N)和N∶=0之后，此時(shí)得到的N值分別為n,0,1。

(3)N∶=N+1在Print(N)和N∶=0之間，此時(shí)得到的N值分別為n,n+1,0。結(jié)論：程序在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，其計(jì)算結(jié)果與并發(fā)程序的執(zhí)行速度有關(guān)，使程序執(zhí)行失去可再現(xiàn)性。

進(jìn)程的特征與狀態(tài)在單道程序設(shè)計(jì)環(huán)境下，CPU被一道程序獨(dú)占，CPU嚴(yán)格按程序的指令順序來執(zhí)行，程序具有順序性、封閉性和可再現(xiàn)性特征。在多道程序設(shè)計(jì)的環(huán)境下，系統(tǒng)中有多個(gè)程序同時(shí)運(yùn)行。此時(shí)的程序具有間斷性、失去了程序的封閉性、不可再現(xiàn)性等特征。程序一旦運(yùn)行起來，它不但與程序本身有關(guān)，而且與它運(yùn)行時(shí)所處的運(yùn)行環(huán)境有關(guān)，程序的活動不再是靜態(tài)的、封閉的，而顯現(xiàn)出并發(fā)性、動態(tài)性以及相互制約的關(guān)系。所以用程序的概念已經(jīng)不能描述上述這些特征，于是引入進(jìn)程的概念。進(jìn)程的概念來自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系統(tǒng)中也曾叫過任務(wù)(task)。進(jìn)程的特征（1）結(jié)構(gòu)特征：從結(jié)構(gòu)上看，進(jìn)程實(shí)體是由程序段、相關(guān)的數(shù)據(jù)段和進(jìn)程控制塊(PCB，processcontrolblock)三部分組成。（2）動態(tài)性：進(jìn)程的實(shí)質(zhì)是進(jìn)程實(shí)體的一次執(zhí)行過程，它有著創(chuàng)建、活動、暫停、終止等過程，具有一定的生命期，是動態(tài)地產(chǎn)生、變化和消亡的。（3）并發(fā)性：多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，且能在一段時(shí)間內(nèi)同時(shí)運(yùn)行。（4）獨(dú)立性：進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度的基本單位。（5）異步性：各個(gè)并發(fā)進(jìn)程按照各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。2.1.4進(jìn)程的特征與狀態(tài)行為的一個(gè)規(guī)則叫做程序，程序在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動稱為進(jìn)程（Dijkstra)。進(jìn)程是這樣的計(jì)算部分，它是可以和其它計(jì)算并行的一個(gè)計(jì)算。(Donovan)進(jìn)程（有時(shí)稱為任務(wù)）是一個(gè)程序與其數(shù)據(jù)一道通過處理機(jī)的執(zhí)行所發(fā)生的活動。（Alan.C.Shaw)進(jìn)程是執(zhí)行中的程序。（KenThompsonandDennisRitchie)教材上給出的進(jìn)程的定義：

進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。進(jìn)程的定義1、程序是指令的集合，是靜態(tài)的概念。進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，是動態(tài)的概念。程序可以作為軟件資料長期保存。進(jìn)程是有生命周期的。2、進(jìn)程是一個(gè)獨(dú)立的運(yùn)行單位，能與其它進(jìn)程并發(fā)活動。而程序則不是。3、進(jìn)程是競爭計(jì)算機(jī)系統(tǒng)有限資源的基本單位，也是進(jìn)行處理機(jī)調(diào)度的基本單位。4、一個(gè)程序可以作為多個(gè)進(jìn)程的運(yùn)行程序，一個(gè)進(jìn)程也可以運(yùn)行多個(gè)程序。進(jìn)程與程序的區(qū)別與聯(lián)系例子：光盤（CD、VCD）光盤（程序）放光盤的活動（進(jìn)程）進(jìn)程與程序的區(qū)別與聯(lián)系進(jìn)程在系統(tǒng)中的活動規(guī)律是：執(zhí)行暫停執(zhí)行(間斷性)進(jìn)程的三種基本狀態(tài)：

就緒狀態(tài)

執(zhí)行狀態(tài)

阻塞狀態(tài)（又稱等待，睡眠）進(jìn)程的三種基本狀態(tài)就緒狀態(tài)(Ready)若進(jìn)程已具備了運(yùn)行條件，只因CPU被別的進(jìn)程占用而不能被CPU執(zhí)行，則稱此時(shí)進(jìn)程處于就緒狀態(tài)。一旦把CPU分配給它，該進(jìn)程就可以運(yùn)行。從宏觀上講，它是一種邏輯上的可運(yùn)行狀態(tài)。系統(tǒng)中處于就緒狀態(tài)的進(jìn)程可能有多個(gè)，通常將它們按某種策略（優(yōu)先級）排成一個(gè)隊(duì)列，稱為就緒隊(duì)列。進(jìn)程的三種基本狀態(tài)執(zhí)行狀態(tài)(Running）當(dāng)一個(gè)進(jìn)程已分配到CPU，它的程序正在被CPU執(zhí)行時(shí)進(jìn)程所處的狀態(tài)稱執(zhí)行狀態(tài)，也稱為運(yùn)行狀態(tài)。對于單CPU系統(tǒng)而言，處于執(zhí)行狀態(tài)的進(jìn)程只可能有一個(gè)，多處理機(jī)系統(tǒng)中則有多個(gè)。進(jìn)程的三種基本狀態(tài)阻塞狀態(tài)(Wait)正在執(zhí)行的進(jìn)程因等待某種事件的發(fā)生而暫時(shí)不能運(yùn)行便放棄CPU的狀態(tài)稱阻塞狀態(tài)(等待狀態(tài))，例如，等待輸入/輸出、等待進(jìn)程間的同步/互斥等。一旦引起等待的原因消失，進(jìn)程便轉(zhuǎn)為就緒狀態(tài)。以便在適當(dāng)?shù)臅r(shí)候占用CPU。系統(tǒng)中處于等待狀態(tài)的進(jìn)程可能有多個(gè)，通常也將它們排成一個(gè)隊(duì)列。有的系統(tǒng)按照進(jìn)程不同的等待原因，把處于等待狀態(tài)的進(jìn)程排成多個(gè)隊(duì)列。進(jìn)程的三種基本狀態(tài)1．就緒狀態(tài)→執(zhí)行狀態(tài)2．執(zhí)行狀態(tài)→阻塞狀態(tài)3．執(zhí)行狀態(tài)→就緒狀態(tài)4.阻塞狀態(tài)→就緒狀態(tài)時(shí)間片完進(jìn)程狀態(tài)的轉(zhuǎn)換：進(jìn)程的三種基本狀態(tài)的轉(zhuǎn)換進(jìn)程的動態(tài)性決定了它不會固定處于某個(gè)狀態(tài)，系統(tǒng)中的進(jìn)程由于各種不同的原因在以上各個(gè)狀態(tài)之間變化。其狀態(tài)變化及原因如圖所示。創(chuàng)建（新）狀態(tài)和終止?fàn)顟B(tài)（1）創(chuàng)建（新）狀態(tài)：一個(gè)進(jìn)程剛剛建立，但還未將它插入就緒隊(duì)列時(shí)的狀態(tài)。（2）終止?fàn)顟B(tài)：一個(gè)進(jìn)程已經(jīng)正常結(jié)束或異常結(jié)束，OS已將它從就緒隊(duì)列中移出，但尚未將它撤消時(shí)的狀態(tài)。進(jìn)程狀態(tài)的轉(zhuǎn)換1．創(chuàng)建(新)狀態(tài)→就緒狀態(tài)2．就緒狀態(tài)→執(zhí)行狀態(tài)3．執(zhí)行狀態(tài)→阻塞狀態(tài)4．執(zhí)行狀態(tài)→就緒狀態(tài)5．執(zhí)行狀態(tài)→終止?fàn)顟B(tài)6．阻塞狀態(tài)→就緒狀態(tài)

時(shí)間片完進(jìn)程狀態(tài)變遷圖進(jìn)程的掛起狀態(tài)

使正在執(zhí)行的進(jìn)程暫停執(zhí)行；若此時(shí)用戶進(jìn)程正處于就緒狀態(tài)而未執(zhí)行，則該進(jìn)程暫不接受調(diào)度，我們把這種靜止?fàn)顟B(tài)稱為掛起狀態(tài)(靜止?fàn)顟B(tài))。

引入掛起狀態(tài)的原因有：

1．終端用戶的需要終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)有可疑問題，希望暫時(shí)使自己的程序靜止下來。

2．父進(jìn)程請求父進(jìn)程希望掛起自己的子進(jìn)程，以便考查和修改子進(jìn)程，或協(xié)調(diào)子進(jìn)程的活動。

3．負(fù)荷調(diào)節(jié)的需要當(dāng)實(shí)時(shí)系統(tǒng)中的負(fù)載較重，影響到實(shí)時(shí)任務(wù)的執(zhí)行，可掛起不重要進(jìn)程，保證系統(tǒng)正常運(yùn)行。

4．操作系統(tǒng)的需要操作系統(tǒng)有時(shí)希望掛起某些進(jìn)程，以便檢查運(yùn)行中的資源使用情況或進(jìn)行記帳。帶有掛起狀態(tài)時(shí)的進(jìn)程狀態(tài)轉(zhuǎn)換

所謂原語就是計(jì)算機(jī)機(jī)器指令的延伸，它是由若干條機(jī)器指令構(gòu)成，并完成一種特定功能的程序段。原語操作由操作系統(tǒng)內(nèi)核提供。為保證原語操作的正確性，還規(guī)定原語在執(zhí)行期間必須一次執(zhí)行完，中間不允許被中斷。也就是說，原語具有原子性，即原語操作中的所有指令（動作）要么全做，要么全不做，不允許被分割。在單CPU系統(tǒng)中，在執(zhí)行原語的過程中一般要關(guān)中斷。1．活動就緒→靜止就緒：當(dāng)進(jìn)程處于未被掛起的就緒狀態(tài)時(shí)，稱此為活動就緒狀態(tài)，表示為Readya，此時(shí)進(jìn)程可被調(diào)度。當(dāng)用掛起原語Suspend將該進(jìn)程掛起后，該進(jìn)程便轉(zhuǎn)變?yōu)殪o止就緒狀態(tài)，表示為Readys。 處于Readys狀態(tài)的進(jìn)程，不再被調(diào)度執(zhí)行。2．活動阻塞→靜止阻塞：當(dāng)進(jìn)程處于未被掛起的阻塞狀態(tài)時(shí)，稱為它處于活動阻塞狀態(tài)，表示為Blockeda。當(dāng)用Suspend原語將它掛起后，進(jìn)程便轉(zhuǎn)變?yōu)殪o止阻塞狀態(tài)，表示為Blockeds。 處于該狀態(tài)的進(jìn)程，在其所期待的事件出現(xiàn)后，它將從靜止阻塞變?yōu)殪o止就緒。帶有掛起狀態(tài)時(shí)的進(jìn)程狀態(tài)轉(zhuǎn)換

3．靜止就緒→活動就緒：處于Readys狀態(tài)的進(jìn)程，若用激活原語Active激活后，該進(jìn)程將轉(zhuǎn)變?yōu)镽eadya狀態(tài)。4．靜止阻塞→活動阻塞：處于Blockcds狀態(tài)的進(jìn)程，若用激活原語Active激活后，進(jìn)程將轉(zhuǎn)變?yōu)锽lockeda狀態(tài)。帶有掛起狀態(tài)時(shí)的進(jìn)程狀態(tài)轉(zhuǎn)換

具有掛起狀態(tài)的進(jìn)程狀態(tài)圖帶有掛起狀態(tài)時(shí)的進(jìn)程狀態(tài)轉(zhuǎn)換

時(shí)間片完調(diào)度具有創(chuàng)建、終止和掛起狀態(tài)的進(jìn)程狀態(tài)圖帶有掛起狀態(tài)時(shí)的進(jìn)程狀態(tài)轉(zhuǎn)換

創(chuàng)建許可許可終止釋放時(shí)間片完調(diào)度在系統(tǒng)中一個(gè)進(jìn)程存在：

進(jìn)程控制塊PCB(ProcessControlBlock)(記錄型數(shù)據(jù)結(jié)構(gòu))

進(jìn)程的執(zhí)行程序(一個(gè)可執(zhí)行文件)進(jìn)程執(zhí)行時(shí)所需的數(shù)據(jù)進(jìn)程總是位于某個(gè)隊(duì)列(就緒、阻塞某事件隊(duì)列)

處于某種狀態(tài)（執(zhí)行、就緒、阻塞）占用某些系統(tǒng)資源（內(nèi)存，打開某些文件、處理機(jī)、外設(shè)）進(jìn)程控制塊PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況及控制進(jìn)程運(yùn)行所需的全部信息。進(jìn)程標(biāo)識符用于惟一標(biāo)識一個(gè)進(jìn)程。內(nèi)部標(biāo)識符操作系統(tǒng)為每一個(gè)進(jìn)程賦予一個(gè)惟一的數(shù)字標(biāo)識符(進(jìn)程的序號)外部標(biāo)識符由創(chuàng)建者提供，由字母、數(shù)字組成。為了描述進(jìn)程的家族關(guān)系，還應(yīng)設(shè)置父進(jìn)程標(biāo)識及子進(jìn)程標(biāo)識。還可設(shè)置用戶標(biāo)識。處理機(jī)狀態(tài)信息由處理機(jī)的各種寄存器(通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字PSW、用戶棧指針)中的內(nèi)容組成。進(jìn)程控制塊中的信息3.進(jìn)程調(diào)度信息包括進(jìn)程狀態(tài)、進(jìn)程優(yōu)先級、進(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ā)生的事件)。4.進(jìn)程控制信息包括程序和數(shù)據(jù)的地址(進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地址)、進(jìn)程同步和通信機(jī)制、資源清單(除CPU以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單)、鏈接指針等。進(jìn)程控制塊中的信息進(jìn)程控制塊PCB的作用是使一個(gè)多道環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。操作系統(tǒng)是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。可以說PCB是進(jìn)程存在的惟一標(biāo)志。當(dāng)進(jìn)程被創(chuàng)建時(shí)，系統(tǒng)要為其建立一個(gè)PCB，在進(jìn)程的整個(gè)生命期內(nèi)系統(tǒng)利用該P(yáng)CB對其進(jìn)行控制，進(jìn)程運(yùn)行結(jié)束后要回收其PCB。(戶口)由于PCB經(jīng)常被系統(tǒng)訪問，故PCB應(yīng)常駐內(nèi)存。系統(tǒng)將所有的PCB組織成若干個(gè)鏈表(或隊(duì)列)，存放在操作系統(tǒng)中專門開辟的PCB區(qū)內(nèi)。進(jìn)程控制塊的作用進(jìn)程控制塊的組織方式1)線性方式 即將系統(tǒng)中所有的PCB都組織在一張線性表中，將該表的首地址存放在內(nèi)存的一個(gè)專用區(qū)域中。該方式實(shí)現(xiàn)簡單、開銷小，但每次查找時(shí)都需要掃描整張表，因此適合進(jìn)程數(shù)量不多的系統(tǒng)。PCB1PCB2PCB3…PCBn進(jìn)程控制塊的組織方式2)鏈接方式 系統(tǒng)把所有進(jìn)程的PCB按其狀態(tài)實(shí)行分類管理，每一類用一個(gè)隊(duì)列來管理。一般來說，系統(tǒng)中的進(jìn)程隊(duì)列可分為三類，即就緒隊(duì)列、若干個(gè)阻塞隊(duì)列(根據(jù)阻塞原因的不同把處于阻塞狀態(tài)的進(jìn)程的PCB排成不同的隊(duì)列)和空白隊(duì)列。進(jìn)程控制塊的組織方式3)索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表(就緒索引表、阻塞索引表等)，并把各索引表在內(nèi)存的首地址記錄在內(nèi)存的一些專用單元中。在每個(gè)索引表的表目中，記錄具有相應(yīng)狀態(tài)的某個(gè)PCB在PCB區(qū)中的地址。進(jìn)程控制用于創(chuàng)建一個(gè)新進(jìn)程，終止一個(gè)已完成的進(jìn)程，或去終止一個(gè)因出現(xiàn)某事件而使其無法運(yùn)行下去的進(jìn)程，還可負(fù)責(zé)進(jìn)程運(yùn)行中的狀態(tài)轉(zhuǎn)換。進(jìn)程控制一般由操作系統(tǒng)內(nèi)核來實(shí)現(xiàn)。在操作系統(tǒng)內(nèi)核中，有一組程序?qū)ｉT用于完成對進(jìn)程的控制。進(jìn)程控制包括：

進(jìn)程創(chuàng)建、

進(jìn)程終止、

進(jìn)程阻塞、

進(jìn)程喚醒、進(jìn)程掛起、進(jìn)程激活2.3進(jìn)程控制這些操作都要對應(yīng)地執(zhí)行一個(gè)特殊的程序段（操作系統(tǒng)核心程序），同時(shí)系統(tǒng)也通過系統(tǒng)調(diào)用(稱為原語，一種特殊的系統(tǒng)調(diào)用)給用戶提供進(jìn)程控制的功能。進(jìn)程圖(ProcessGraph)是用于描述一個(gè)進(jìn)程的家族關(guān)系的有向樹。一個(gè)進(jìn)程可以通過創(chuàng)建原語產(chǎn)生一個(gè)新進(jìn)程在進(jìn)程Pi創(chuàng)建了進(jìn)程Pj之后，稱Pi是Pj的父進(jìn)程(ParentProcess),Pj

是Pi的子進(jìn)程(ProgenyProcess)。用一條由進(jìn)程Pi指向進(jìn)程Pj的有向邊來描述它們的父子關(guān)系。創(chuàng)建父進(jìn)程的進(jìn)程稱為祖先進(jìn)程。這樣便形成了一棵進(jìn)程樹，樹的根結(jié)點(diǎn)作為進(jìn)程家族的祖先(Ancestor)。進(jìn)程樹的特點(diǎn)：資源分配嚴(yán)格，子進(jìn)程可以繼承父進(jìn)程所擁有的資源；當(dāng)子進(jìn)程被撤消時(shí)，應(yīng)將其從父進(jìn)程那里獲得的資源歸還給父進(jìn)程；在撤消父進(jìn)程時(shí)，也必須同時(shí)撤消其所有的子進(jìn)程，便于管理；系統(tǒng)可根據(jù)需要賦予進(jìn)程不同的控制權(quán)，并可以把一個(gè)任務(wù)分解成若干個(gè)進(jìn)程來完成，具有較好的靈活性；樹形結(jié)構(gòu)層次清晰，關(guān)系明確。進(jìn)程的創(chuàng)建ABCDIJEKGLMHNF圖2-9進(jìn)程樹祖先父進(jìn)程子進(jìn)程引起創(chuàng)建進(jìn)程的事件

1．用戶登錄

2．作業(yè)調(diào)度

3．提供服務(wù)

4．應(yīng)用請求由系統(tǒng)內(nèi)核創(chuàng)建由應(yīng)用進(jìn)程自已創(chuàng)建進(jìn)程的創(chuàng)建創(chuàng)建進(jìn)程的主要工作是申請一個(gè)進(jìn)程控制塊PCB，并向其中填入進(jìn)程名、優(yōu)先級等有關(guān)的參數(shù)。創(chuàng)建進(jìn)程的基本過程是：

(進(jìn)程創(chuàng)建原語Creat())(1)申請空白PCB。從空閑的PCB集合中申請一個(gè)新的PCB，同時(shí)獲得該進(jìn)程的內(nèi)部標(biāo)識；(2)為新進(jìn)程的程序和數(shù)據(jù)分配所需資源（內(nèi)存、文件、I/O和CPU時(shí)間片）；(3)初始化進(jìn)程控制塊PCB。向該P(yáng)CB中填寫各種參數(shù)；(4)將新進(jìn)程插入到就緒隊(duì)列。把該進(jìn)程的狀態(tài)設(shè)置成就緒狀態(tài)，并將該P(yáng)CB插入到就緒隊(duì)列中。進(jìn)程的創(chuàng)建引起進(jìn)程終止的事件

1．正常結(jié)束 進(jìn)程任務(wù)已完成，退出運(yùn)行。

2．異常結(jié)束在進(jìn)程運(yùn)行期間，由于出現(xiàn)異常事件而迫使進(jìn)程終止。如：越界錯(cuò)誤、保護(hù)錯(cuò)、非法指令、特權(quán)指令錯(cuò)、運(yùn)行超時(shí)、等待超時(shí)、算術(shù)運(yùn)算錯(cuò)、I/O故障等。

3．外界干預(yù)進(jìn)程應(yīng)外界的請求而終止運(yùn)行。包括：操作員或操作系統(tǒng)干預(yù)、父進(jìn)程請求、父進(jìn)程終止。進(jìn)程的終止進(jìn)程的終止過程是：

(進(jìn)程終止原語Holt())(1)根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)。(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。(3)若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其子孫進(jìn)程予以終止，以防它們成為不可控的進(jìn)程。(4)將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)。(5)將被終止進(jìn)程(其PCB)從所在隊(duì)列中移出，等待其他程序來搜集信息。進(jìn)程的終止引起進(jìn)程阻塞和喚醒的事件

1．請求系統(tǒng)提供服務(wù)正在執(zhí)行的進(jìn)程請求操作系統(tǒng)提供服務(wù)，由于某種原因，操作系統(tǒng)并不立即滿足該進(jìn)程的要求。

2．啟動某種操作進(jìn)程啟動某種操作后，必須在該操作完成之后才能繼續(xù)執(zhí)行。

3．新數(shù)據(jù)尚未到達(dá)對于相互合作的進(jìn)程，如果其中一個(gè)進(jìn)程需要先獲得另一進(jìn)程提供的數(shù)據(jù)才能運(yùn)行，則只要其所需的數(shù)據(jù)尚未到達(dá)，該進(jìn)程只有阻塞。

4．無新工作可做系統(tǒng)往往設(shè)置一些具有特定功能的系統(tǒng)進(jìn)程，每當(dāng)這種進(jìn)程完成任務(wù)后，便把自己阻塞起來以等待新任務(wù)到來。正在執(zhí)行的進(jìn)程，當(dāng)發(fā)生上述事件時(shí)，由于無法繼續(xù)執(zhí)行，于是進(jìn)程便通過調(diào)用阻塞（等待）原語block把自己阻塞。可見，進(jìn)程阻塞是進(jìn)程自身的一種主動行為。進(jìn)程的阻塞和喚醒進(jìn)程的阻塞(等待)過程

阻塞(等待)原語block(1)進(jìn)程立即停止執(zhí)行，把其PCB中的現(xiàn)行狀態(tài)由“執(zhí)行”變?yōu)樽枞?/p>

(2)將其PCB插入到相應(yīng)的阻塞隊(duì)列中去；

(3)轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)重新分配給另一就緒進(jìn)程，并進(jìn)行切換。進(jìn)程的阻塞和喚醒當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時(shí)，如I/O完成或所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程(如，用完并釋放了該I/O設(shè)備的進(jìn)程)調(diào)用喚醒原語，將等待該事件的進(jìn)程喚醒。進(jìn)程的喚醒過程喚醒原語wakeup()

(1)把被阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出;(2)將其PCB中的現(xiàn)行狀態(tài)由“阻塞”變?yōu)榫途w;(3)該P(yáng)CB插入到就緒隊(duì)列中。注意：如果在某進(jìn)程中調(diào)用了阻塞原語，則必須在與之相合作的另一進(jìn)程中或其他相關(guān)進(jìn)程中安排喚醒原語，以能喚醒阻塞進(jìn)程；否則，被進(jìn)程將會因不能被喚醒而長久地處于阻塞狀態(tài)。進(jìn)程的阻塞和喚醒當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，比如，用戶進(jìn)程請求將自己掛起，或者父進(jìn)程請求將自己的某個(gè)子進(jìn)程掛起時(shí)，系統(tǒng)將利用掛起原語suspend（）將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。掛起原語的執(zhí)行過程是:(1)檢查被掛起進(jìn)程的狀態(tài)：若正處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進(jìn)程，則將其改為靜止阻塞。(2)為了方便用戶或父進(jìn)程考查該進(jìn)程的運(yùn)行情況，而把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。(3)最后，如被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)調(diào)度程序重新調(diào)度。進(jìn)程的掛起與激活當(dāng)發(fā)生激活過程的事件時(shí)，如用戶進(jìn)程或父進(jìn)程請求激活指定進(jìn)程，若進(jìn)程駐留在外存而內(nèi)存中已有足夠的空間，則可將在外存上處于靜止就緒狀態(tài)的進(jìn)程換入內(nèi)存。這時(shí)，系統(tǒng)將利用激活原語active()將指定進(jìn)程激活。激活原語的執(zhí)行過程是：先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)：若是靜止就緒，便將其改為活動就緒；若為靜止阻塞，便將其改為活動阻塞。假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級的比較，如果被激活進(jìn)程的優(yōu)先級更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把處理機(jī)分配給剛被激活的進(jìn)程。進(jìn)程的掛起與激活2.4進(jìn)程同步

進(jìn)程同步的基本概念

兩種形式的制約關(guān)系在多道程序的環(huán)境中，系統(tǒng)中的多個(gè)進(jìn)程可能存在著以下兩種形式的制約關(guān)系：直接相互制約關(guān)系并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要相互等待與互通消息，比如，當(dāng)某進(jìn)程運(yùn)行到某點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未得到對方的消息時(shí)，該進(jìn)程必須處于等待狀態(tài)，直到收到消息后被喚醒，這種進(jìn)程之間的協(xié)同工作關(guān)系就是進(jìn)程之間的直接相互制約關(guān)系，也稱為進(jìn)程同步關(guān)系。例如：輸入進(jìn)程A通過單緩沖向計(jì)算進(jìn)程B提供數(shù)據(jù)間接相互制約關(guān)系也稱為進(jìn)程互斥關(guān)系，是由各進(jìn)程排它性使用共享資源(如共享CPU、I/O設(shè)備等)引起的。當(dāng)某進(jìn)程正在訪問某臨界資源時(shí)，就不允許其它進(jìn)程進(jìn)入，否則就會發(fā)生無法估計(jì)的錯(cuò)誤，這種關(guān)系就是進(jìn)程之間的互斥關(guān)系。例如：A、B兩個(gè)進(jìn)程共享一臺打印機(jī)操作系統(tǒng)中一次僅允許一個(gè)進(jìn)程訪問的資源稱為臨界資源。例：軟件臨界資源有內(nèi)存變量、指針、數(shù)組等等硬件臨界資源有打印機(jī)、磁帶機(jī)等不論是硬件臨界資源，還是軟件臨界資源，多個(gè)進(jìn)程互斥地對它進(jìn)行訪問。臨界資源

問題的描述：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)具有n個(gè)緩沖區(qū)(每個(gè)緩沖區(qū)只能放一件產(chǎn)品)的緩沖池。生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中；消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品消費(fèi)。分析：同步關(guān)系：生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間必須保持同步，即：不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。生產(chǎn)者進(jìn)程的處理過程：生產(chǎn)一個(gè)產(chǎn)品，當(dāng)要送入緩沖區(qū)時(shí)，要檢查緩沖區(qū)是否已滿。若未滿，則可將產(chǎn)品送入緩沖區(qū)；否則，等待。消費(fèi)者進(jìn)程的處理過程：當(dāng)它去取產(chǎn)品時(shí)，要檢查緩沖區(qū)是否有產(chǎn)品。若有，則取走一個(gè)產(chǎn)品；否則，等待。例生產(chǎn)者－消費(fèi)者問題

著名的進(jìn)程同步問題臨界資源

分析：用一個(gè)數(shù)組buffer來表示上述的具有n個(gè)(0，1，…，n-1)緩沖區(qū)的緩沖池。這里的緩沖池是組織成循環(huán)緩沖的。用輸入指針in來指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品后，輸入指針加1；用一個(gè)輸出指針out來指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后，輸出指針加1。當(dāng)(in+1)modn=out時(shí)表示緩沖池滿；而in=out則表示緩沖池空。引入了一個(gè)整型變量counter,其初始值為0。每當(dāng)生產(chǎn)者進(jìn)程向緩沖池中投放一個(gè)產(chǎn)品后，使counter加1；反之，每當(dāng)消費(fèi)者進(jìn)程從中取走一個(gè)產(chǎn)品時(shí)，使counter減1。生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量：

intin=0,out=0,count=0; itembuffer[n];Voidproducer()//生產(chǎn)者程序

Repeat

produceaniteminnextp;//nextp用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品…

whilecounter==ndono-op;//表示重復(fù)地測試條件,no-op是一條空操作指令

bufferin[in]=nextp;

in=(in+1)%n;

counter++;Voidconsumer()//消費(fèi)者程序

Repeatwhilecounter==0dono-op;

nextc=buffer［out］;

out=(out+1)%n;

counter--;

consumertheiteminnextc;//nextc用于存放每次要消費(fèi)的產(chǎn)品兩者在順序執(zhí)行時(shí)其結(jié)果會是正確的，但若并發(fā)執(zhí)行時(shí)，就會出現(xiàn)差錯(cuò)，問題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對它做加1操作，消費(fèi)者對它做減1操作，這兩個(gè)操作在用機(jī)器語言實(shí)現(xiàn)時(shí)，常可用下面的形式描述：register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;假設(shè)counter的當(dāng)前值是5。如果按下述順序執(zhí)行：

register1∶=counter;(register1=5)

register1∶=register1+1;(register1=6)

register2∶=counter;(register2=5)

register2∶=register2-1;(register2=4)

counter∶=register1;(counter=6)

counter∶=register2;(counter=4)結(jié)論：變量count應(yīng)作為臨界資源，生產(chǎn)者和消費(fèi)者進(jìn)程互斥訪問。不論是硬件臨界資源，還是軟件臨界資源，并發(fā)進(jìn)程必須互斥地對它進(jìn)行訪問。每個(gè)進(jìn)程中訪問臨界資源的那段程序段稱為臨界區(qū)(臨界段)臨界區(qū)同一臨界資源在多個(gè)共享它的進(jìn)程中將對應(yīng)多個(gè)臨界區(qū)。

如果能保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，便可保證諸進(jìn)程對臨界資源的互斥訪問。或者說：要臨界資源互斥地被使用，就要保證臨界區(qū)互斥地被執(zhí)行。臨界區(qū)為了保證諸進(jìn)程的臨界區(qū)互斥地被執(zhí)行，我們把一個(gè)訪問臨界資源的循環(huán)進(jìn)程分成以下幾部分：進(jìn)入?yún)^(qū)

每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對欲訪問的臨界資源進(jìn)行檢查，看它是否正被訪問，因此必須在臨界區(qū)之前增加一段用于上述檢查的代碼，把這段代碼稱為進(jìn)入?yún)^(qū)。臨界區(qū)訪問臨界資源的那段程序段。退出區(qū)在臨界區(qū)后面增加一段用于將臨界區(qū)正被訪問的標(biāo)志恢復(fù)為未被訪問的標(biāo)志的代碼，把這段代碼稱為退出區(qū)。剩余區(qū)進(jìn)程除上述進(jìn)入?yún)^(qū)、臨界區(qū)、退出區(qū)之外的其它部分代碼稱為剩余區(qū)。可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下：While(TURE)

{

進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)｝

臨界區(qū)進(jìn)程互斥進(jìn)入臨界區(qū)的過程：臨界區(qū)(1)在“進(jìn)入?yún)^(qū)”判斷是否可進(jìn)入臨界區(qū)。若可以進(jìn)入，則必須設(shè)置臨界區(qū)使用標(biāo)志，阻止其它進(jìn)程進(jìn)入臨界區(qū)。(2)后來的進(jìn)程通過查看臨界區(qū)使用標(biāo)志，知道自己不能進(jìn)入，就進(jìn)入阻塞隊(duì)列，將自己阻塞。(3)當(dāng)臨界區(qū)的進(jìn)程退出區(qū)時(shí)，即在“退出區(qū)”修改臨界區(qū)使用標(biāo)志，并負(fù)責(zé)喚醒一個(gè)進(jìn)程，讓其進(jìn)入臨界區(qū)。進(jìn)入臨界區(qū)的準(zhǔn)則：臨界區(qū)(1)每次至多有一個(gè)進(jìn)程處于臨界區(qū)；(2)當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有限的時(shí)間內(nèi)使其進(jìn)入；(3)進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時(shí)間。同步機(jī)制同步機(jī)制用來協(xié)調(diào)諸進(jìn)程間的運(yùn)行，以實(shí)現(xiàn)進(jìn)程互斥地進(jìn)入自己的臨界區(qū)。同步機(jī)制可以用軟件方法，也可以用硬件方法。同步機(jī)制應(yīng)遵循的規(guī)則：（1）空閑讓進(jìn)：無進(jìn)程處于臨界區(qū)內(nèi)時(shí)，允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)；（2）忙則等待：已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，其他欲進(jìn)入進(jìn)程必須等待；（3）有限等待：對要求訪問臨界區(qū)的進(jìn)程，應(yīng)保證在有限的時(shí)間內(nèi)使其進(jìn)入，以免陷入“死等”狀態(tài)。那么，當(dāng)一進(jìn)程離開臨界區(qū)時(shí)，若發(fā)現(xiàn)有進(jìn)程正在等待進(jìn)入臨界區(qū)，則要喚醒這些進(jìn)程。（4）讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放CPU，以免進(jìn)程陷入“忙等”狀態(tài)。信號量機(jī)制

1965年，荷蘭學(xué)者Dijkstra提出的信號量機(jī)制是一種卓有成效的進(jìn)程同步工具。在長期且廣泛的應(yīng)用中，信號量機(jī)制經(jīng)歷了四種形式：

整型信號量

記錄型信號量

AND型信號量信號量集整型信號量(互斥信號量)最初信號量S是一個(gè)整型變量，表示資源數(shù)目，除初始化外，對信號量僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作(即原語)wait(s)和signal(s)來訪問。這兩個(gè)原子操作一直被分別稱為P（s）和V(s)操作。

wait(s)和signal(s)描述為：

wait(s)：whiles<=0dono-op

s--;

signal(s)：s++;

存在的問題：在wait操作中，只要是信號量S<=0，就會不斷地測試，這將使進(jìn)程處于“忙等”狀態(tài)。這種機(jī)制就沒有遵循“讓權(quán)等待”的原則。記錄型信號量

記錄型信號量機(jī)制，是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后，又會出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況。為此，在信號量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表list，用于鏈接上述的所有等待進(jìn)程。 記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為：

typedefstruct{ intvalue;//表示系統(tǒng)中某類資源的數(shù)目，也稱為資源信號量

structprocess_control_block*list//進(jìn)程鏈表，用于鏈接等待訪問同一臨界資源的所有等待進(jìn)程

}semaphorewait(semaphore*s){s->value--;//表示進(jìn)程請求一個(gè)單位的資源

if(s->value<0)block(s->list);

//若資源分配完畢，就調(diào)用block原語自我阻塞，放棄處理機(jī)，并插入到信號量鏈表s->list中}//遵循“讓權(quán)等待”準(zhǔn)則，此時(shí)s->value的絕對值表示在該信號量鏈表中已阻塞進(jìn)程的數(shù)目。signal(semaphore*s)s->value++;//表示執(zhí)行進(jìn)程釋放一個(gè)單位的資源

if(s->value<=0)wakeup(s->list);//若還有等待資源的進(jìn)程被阻塞，則調(diào)用wakeup原語，將s->list鏈表中的第一個(gè)等待進(jìn)程喚醒。}//若s->value的初值為1，表明只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號量轉(zhuǎn)化為互斥信號量，用于進(jìn)程互斥。記錄型信號量在有些場合下，各進(jìn)程之間要共享兩個(gè)或多個(gè)共享資源(各進(jìn)程一次請求兩種或多種共享資源)后，方能執(zhí)行其任務(wù)。假定現(xiàn)有進(jìn)程A和B，都要訪問共享數(shù)據(jù)D和E(臨界資源)。因此，為D和E分別設(shè)置用于互斥的信號量Dmutex和Emutex，并令它們的初值為1。進(jìn)程A和B中都包含兩個(gè)對Dmutex和Emutex的操作，即：

ProcessAProcessBwait(Dmutex);wait(Emutex);

wait(Emutex);

wait(Dmutex);

若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：

ProcessA：wait(Dmutex); Dmutex＝0

ProcessB：wait(Emutex); Emutex＝0

ProcessA：wait(Emutex); Emutex＝-1

A阻塞

ProcessB：wait(Dmutex); Dmutex＝-1

B阻塞進(jìn)程A和B處于僵持狀態(tài)。在無外界干預(yù)的情況下，兩者都無法從此狀態(tài)中解脫出來。稱此時(shí)的進(jìn)程A和B已進(jìn)入死鎖狀態(tài)。顯然，當(dāng)進(jìn)程同時(shí)要求的共享資源越多，發(fā)生死鎖的可能性越大。AND型信號量機(jī)制可以解決諸進(jìn)程一次請求兩個(gè)或多個(gè)共享資源的問題。AND型信號量AND型信號量AND同步機(jī)制的基本思想：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給它。也即，對若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。AND同步機(jī)制的做法：在wait操作中，增加一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作(Simultaneouswait,Swait)。Swait(S1,S2,…,Sn)

ifSi≥1and

…

andSn≥1then

for(i=1;i<=n;i++)

Si--;//表示進(jìn)程請求n種資源，每種資源一個(gè)

break;

else

placetheprocessinthewaitingqueueassociatedwiththefirstSi

foundwithSi＜1,andsettheprogramcountofthisprocessto thebeginningofSwaitoperation

endifSsignal(S1,S2,…,Sn)

for(i=1;i<=n;i++)

Si++;

RemovealltheprocesswaitinginthequeueassociatedwithSiinto thereadyqueue.

信號量集在有些情況下，進(jìn)程一次需要N個(gè)某類臨界資源；當(dāng)資源數(shù)量低于某一下限值時(shí)，系統(tǒng)不予以分配，因此，在每次分配之前，都必須測試該資源的數(shù)量，看其是否大于其下限值。基于上述兩點(diǎn)，對AND信號量機(jī)制加以擴(kuò)充，形成一般化的“信號量集機(jī)制”。信號量集Swait(S1,t1,d1,…,Sn,tn,dn)

ifSi≥t1and…andSn≥tnthen

for(i=1;i<=n;i++)

Si=Si-di;

//表示進(jìn)程請求n種資源，每種資源di個(gè)

endfor

else

PlacetheexecutingprocessinthewaitingqueueofthefirstSi

with

Si＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation

endifSsignal(S1,d1,…,Sn,dn)

for(i=1;i<=n;i++)

Si

=Si+di;

RemovealltheprocesswaitinginthequeueassociatedwithSiinto

thereadyqueue

endfor;一般“信號量集”的幾種特殊情況：

(1)Swait(S,d,d)。此時(shí)在信號量集中只有一個(gè)信號量S，但允許它每次申請d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配。

(2)Swait(S,1,1)。此時(shí)的信號量集已蛻化為一般的記錄型信號量(S＞1時(shí))或互斥信號量(S=1時(shí))。

(3)Swait(S,1,0)。這是一種很特殊且很有用的信號量操作。當(dāng)S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開關(guān)。

進(jìn)程P0

進(jìn)程P1

進(jìn)程P2 ┊

┊

┊ wait（mutex）

wait（mutex）

wait（mutex） 臨界區(qū) 臨界區(qū) 臨界區(qū)

signal（mutex）signal（mutex）

signal（mutex） 剩余區(qū) 剩余區(qū)

剩余區(qū) 設(shè)置互斥信號量mutex的初值為1。在互斥模型中，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)時(shí)對信號量執(zhí)行wait操作，待臨界區(qū)執(zhí)行完后執(zhí)行signal操作。注：wait（mutex）和signal（mutex）必須成對出現(xiàn)。用wait、signal操作實(shí)現(xiàn)進(jìn)程互斥

進(jìn)程Pa 進(jìn)程Pb

┊

┊L1：wait（pro）

L2：signal（Pro）

┊

┊信號量pro的初值為0。

當(dāng)進(jìn)程Pa執(zhí)行到某點(diǎn)L1時(shí)，如果進(jìn)程Pb沒有執(zhí)行過L2點(diǎn)，則Pa必須等待，直到Pb執(zhí)行過L2點(diǎn)。用wait、signal操作實(shí)現(xiàn)同步的模型p1(){s1；signal(a)；signal(b);}p2(){wait(a)；s2；signal(c)；signal(d);}P3(){wait(b)；s3；signal(e);}P4(){wait(c)；s4；signal(f);}P5(){wait(d)；s5；signal(g);}P6(){wait(e)；wait(f)；wait(g)；s6;}Main(){semaphorea,b,c,d,e,f,g;a.value=b.value=c.value=0;d.value=e.value=0;f.value=g.value=0;cobeginp1();p2();p3();p4();p5();p6();coend

}S1S2S3S5S4S6利用信號量來描述前驅(qū)關(guān)系用信號量可以很好地實(shí)現(xiàn)進(jìn)程間的同步和互斥，但是，每個(gè)要使用臨界資源的用戶進(jìn)程都顯式的使用Wait(S)和Signal(S)同步操作來實(shí)現(xiàn)進(jìn)程間的同步和互斥，這就使大量的Wait(S)和Signal(S)同步操作分散在各個(gè)進(jìn)程中，即信號量的控制分布在整個(gè)系統(tǒng)中，這給系統(tǒng)的管理帶來了麻煩。

管程是管理進(jìn)程間同步的機(jī)制，它保證進(jìn)程互斥地訪問共享變量，并方便地阻塞和喚醒進(jìn)程。管程可以函數(shù)庫的形式實(shí)現(xiàn)。相比之下，管程比信號量好控制。2.4.5管程(monitor)機(jī)制管程的引入1971年，Dijkstra提出，把所有進(jìn)程對某一臨界資源的同步操作集中起來，構(gòu)成一個(gè)所謂的“秘書”進(jìn)程。凡是要訪問臨界資源的進(jìn)程，都必須先向“秘書”報(bào)告，并由“秘書”實(shí)現(xiàn)諸進(jìn)程的同步。1973年，Hoare和Hanson又把“秘書”的思想發(fā)展為管程的概念，把并發(fā)進(jìn)程之間的同步操作分別集中于相應(yīng)的管程中。其基本思想是把信號量及其操作原語封裝在一個(gè)對象內(nèi)部。即：將共享變量以及對共享變量能夠進(jìn)行的所有操作集中在一個(gè)模塊中。管程是一種在程序設(shè)計(jì)級控制進(jìn)程互斥與同步的機(jī)制，具有信號量的功能，且更容易使用和控制。2.4.5管程(monitor)機(jī)制(自學(xué))系統(tǒng)中的各種硬件資源和軟件資源均可用數(shù)據(jù)結(jié)構(gòu)加以抽象的描述，即用少量信息和對該資源所執(zhí)行的操作來表征該資源，而忽略它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。例如：一臺打印機(jī)，可用與分配該資源有關(guān)的狀態(tài)(busy和free)和對它執(zhí)行請求和釋放的操作，以及等待該資源的進(jìn)程隊(duì)列來描述。一個(gè)FIFO隊(duì)列，可用其隊(duì)長、隊(duì)首和隊(duì)尾以及在該隊(duì)列上執(zhí)行的一組操作來描述。2.4.5管程(monitor)機(jī)制

管程的基本概念當(dāng)共享資源用共享數(shù)據(jù)結(jié)構(gòu)表示時(shí)，資源管理程序可用對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程來表示。把這樣一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過程一并稱為管程。Hansan為管程所下的定義：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)上)的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對該資源的操作過程所構(gòu)成的軟件模塊。2.4.5管程(monitor)機(jī)制

管程的基本概念管程由四部分組成：管程的名稱對局部于管程的共享數(shù)據(jù)結(jié)構(gòu)的說明對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程對局部于管程的共享數(shù)據(jù)設(shè)置初始值的語句2.4.5管程(monitor)機(jī)制

管程的基本概念圖2-11管程的示意圖管程的結(jié)構(gòu)Monitormonitor_name={//管程名

sharevariabledeclarations;//共享變量說明

conddeclarations;//條件變量說明

public://能被進(jìn)程調(diào)用的過程

voidP1(……)//對數(shù)據(jù)結(jié)構(gòu)操作的過程

{……}voidP2(……){……}……void(……){……}……{//管程主體

initializationcode;//初始化代碼

……}}

管程的語法格式

模塊化：一個(gè)管程是一個(gè)基本程序單位，可以單獨(dú)編譯；抽象數(shù)據(jù)類型：管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)進(jìn)行操作的代碼；信息掩蔽：管程中的數(shù)據(jù)結(jié)構(gòu)只能被管程中的過程訪問，這些過程也是在管程內(nèi)部定義的，供管程外的進(jìn)程調(diào)用，而管程中的數(shù)據(jù)結(jié)構(gòu)以及過程(函數(shù))的具體實(shí)現(xiàn)外部不可見。為了保證管程中共享變量的數(shù)據(jù)完整性，把管程本身作為一種臨界區(qū)，規(guī)定管程互斥進(jìn)入；一個(gè)進(jìn)程通過調(diào)用管程的一個(gè)過程進(jìn)入管程。管程通常是用來管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊(duì)列以及相應(yīng)的等待及喚醒操作。任何時(shí)侯，只能有一個(gè)進(jìn)程在管程中執(zhí)行，調(diào)用管程的任何其他進(jìn)程都被阻塞，以等待管程變?yōu)榭捎谩９艹痰闹饕卣饔捎诠艹掏ǔＪ怯糜诠芾碣Y源的，為了實(shí)現(xiàn)進(jìn)程對資源的共享，管程必須包含同步工具。因而在管程內(nèi)部，應(yīng)當(dāng)存在某種等待機(jī)制。當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運(yùn)行時(shí)使其等待。為此在管程內(nèi)部可以說明和使用一種特殊類型的變量----條件變量。每個(gè)條件變量表示一種等待原因，并且不取具體數(shù)值－－相當(dāng)于每個(gè)原因?qū)?yīng)一個(gè)隊(duì)列。條件變量(condition)管程使用條件變量condition和同步操作原語wait和signal提供對同步的支持。等待的原因可有多個(gè)，條件變量相應(yīng)的可有多個(gè)。管程中對每個(gè)條件變量都要進(jìn)行說明，形式為：

conditionx,y;

且條件變量應(yīng)置于wait和signal之前，即表示為x.wait和x.signal。條件變量(condition)同步操作原語wait和signal

：針對條件變量x，x.wait將自己阻塞在x隊(duì)列中，x.signal將x隊(duì)列中的一個(gè)進(jìn)程喚醒。x.wait：正在調(diào)用管程的進(jìn)程因x條件需要被阻塞或掛起，則調(diào)用x.wait將自己插入到x條件的等待隊(duì)列上，并釋放管程，直到x條件變化。此時(shí)其它進(jìn)程可以使用該管程。x.signal：正在調(diào)用管程的進(jìn)程發(fā)現(xiàn)x條件發(fā)生了變化，則調(diào)用x.signal，重新啟動一個(gè)因x條件而阻塞的進(jìn)程。如果存在多個(gè)這樣的進(jìn)程，則選擇其中的一個(gè)，如果沒有，則繼續(xù)執(zhí)行原進(jìn)程，而不產(chǎn)生任何結(jié)果。條件變量(condition)如果有進(jìn)程Q因x條件處于阻塞狀態(tài)，當(dāng)正在調(diào)用管程的進(jìn)程P執(zhí)行了x.signal操作后，進(jìn)程Q被重新啟動，此時(shí)兩個(gè)進(jìn)程P和Q，如何確定哪個(gè)執(zhí)行，哪個(gè)等待，可采用下述方式之一進(jìn)行處理：(1)P等待，直至Q離開管程或等待另一條件Q等待，直至P離開管程或等待另一條件兩者的折衷，規(guī)定管程中的過程所執(zhí)行的signal操作是過程體的最后一個(gè)操作條件變量(condition)2.5經(jīng)典的進(jìn)程同步問題

2.5.1生產(chǎn)者－消費(fèi)者問題(Theproceducer-consumerproblem)一．利用記錄型信號量解決生產(chǎn)者/消費(fèi)者問題情形一：問題的描述：有一個(gè)生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給一個(gè)消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)緩沖區(qū)(只能放一件產(chǎn)品)。生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入緩沖區(qū)中；消費(fèi)者進(jìn)程可從緩沖區(qū)中取走產(chǎn)品消費(fèi)。分析：同步關(guān)系：生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間必須保持同步，即：不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。生產(chǎn)者進(jìn)程的處理過程：生產(chǎn)一個(gè)產(chǎn)品，當(dāng)要送入緩沖區(qū)時(shí)，要檢查是否可把產(chǎn)品存入緩沖區(qū)（即緩沖區(qū)是否為空，消費(fèi)者是否把產(chǎn)品取走）。若空，則可將產(chǎn)品送入緩沖區(qū)；否則，等待。消費(fèi)者進(jìn)程的處理過程：當(dāng)它去取產(chǎn)品時(shí)，要檢查緩沖區(qū)是否有產(chǎn)品。若有，則取走一個(gè)產(chǎn)品；否則，等待。一．利用記錄型信號量

解決生產(chǎn)者/消費(fèi)者問題定義如下信號量：empty表示緩沖池中空緩沖區(qū)的數(shù)量(物品是否可以存入緩沖區(qū))。full表示滿緩沖區(qū)的數(shù)量。mutex表示互斥信息量，對緩沖池的互斥使用。又假定這些生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程相互等效，只要緩沖池未滿，生產(chǎn)者進(jìn)程便可將產(chǎn)品（消息）投放到緩沖池；只要緩沖池未空，消費(fèi)者進(jìn)程便可從緩沖池中取走一個(gè)產(chǎn)品。程序段如下：intin=0,out=0;itembuffer[n];semaphoremutex=1,empty=n,full=0;voidproceduer(){do{ produceanitemnextp;…

wait(empty);

wait(mutex); buffer[in]=nextp; in=(in+1)%n;

signal(mutex);

signal(full);}while(TRUE);}Voidconsumer(){do{

wait(full);wait(mutex);nextc=buffer[out];out=(out+1)%n; signal(mutex);signal(empty);

consumetheiteminnextc; …}while(TRUE);}一．利用記錄型信號量

解決生產(chǎn)者/消費(fèi)者問題1.wait(mutex)和signal(mutex)必須成對出現(xiàn)；2.對資源信號量empty和full的wait和signal操作也要成對出現(xiàn)，但分別處于不同進(jìn)程中。e.g.:wait(empty)在生產(chǎn)者進(jìn)程中，signal(empty)在消費(fèi)者進(jìn)程中，生產(chǎn)者進(jìn)程因執(zhí)行wait(empty)而阻塞，之后將由消費(fèi)者進(jìn)程對它喚醒。

一．利用記錄型信號量解決生產(chǎn)者/消費(fèi)者問題情形二：問題的描述：有m個(gè)生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給r個(gè)消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了n個(gè)緩沖區(qū)(可以存放n件產(chǎn)品)。生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入緩沖區(qū)中；消費(fèi)者進(jìn)程可從緩沖區(qū)中取走產(chǎn)品消費(fèi)。分析：同步關(guān)系：生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間必須保持同步，即：當(dāng)n個(gè)緩沖區(qū)都為空時(shí)，不允許消費(fèi)者進(jìn)程到空緩沖區(qū)去取產(chǎn)品；當(dāng)n個(gè)緩沖區(qū)都為滿時(shí)，也不允許生產(chǎn)者進(jìn)程向已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。

互斥關(guān)系：緩沖池是個(gè)臨界資源，因此，諸進(jìn)程對緩沖池的操作程序是一個(gè)共享臨界區(qū)，因此，需要互斥的訪問。m個(gè)生產(chǎn)者往緩沖區(qū)存放物品時(shí)應(yīng)互斥，r個(gè)消費(fèi)者從緩沖區(qū)中取物品也互斥,同時(shí)也要求生產(chǎn)者和消費(fèi)者互斥存取物品。一．利用記錄型信號量

解決生產(chǎn)者/消費(fèi)者問題定義如下信號量：empty表示緩沖池中空緩沖區(qū)的數(shù)量(物品是否可以存入緩沖區(qū))，初值為n，即系統(tǒng)初始化時(shí)允許存入n件物品。full表示緩沖池中滿緩沖區(qū)的數(shù)量(緩沖區(qū)中是否存有物品)，初值為0，即系統(tǒng)初始化時(shí)緩沖區(qū)無物品。Mutex：互斥信號量，表示諸進(jìn)程對緩沖池的互斥使用，初值為1定義兩個(gè)指針：in：指示生產(chǎn)者往緩沖區(qū)存放產(chǎn)品的相對位置。out：指示消費(fèi)者從緩沖區(qū)取出產(chǎn)品的相對位置。程序段如下：Varempty,full,mutex

:semaphore:=n,0,1;Buffer:array[0..n-1]ofitemitem;in,out:integer:=0,0;beginparbeginproceduer:begin repeat… procedueanitemnextp;…wait(empty);wait(mutex);Buffer(in):=nextp;in:=(in+1)modn; signal(mutex);

signal(full); untillfalse;endConsumer:begin

repeatwait(full);wait(mutex);nextc:=Buffer(out); out:=(out+1)modn;signal(mutex);signal(empty);

consumetheiteminnextc; untillfalse;end

parend;end；一．利用記錄型信號量

解決生產(chǎn)者/消費(fèi)者問題注意:wait操作不能顛倒，必須先執(zhí)行對共享資源信號量的wait操作，然后執(zhí)行互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。

Varmutex,empty,full:semaphore:=1,n,0;Buffer:array[0..n-1]ofitem;in,out:integer:=0,0;beginparbeginproceduer:

begin

repeat

…

procedueanitemnextp;…

Swait(empty,mutex);

Buffer(in):=nextp; in:=(in+1)modn;

Ssignal(mutex,full);untillfalse;endConsumer:begin

repeat

Swait(full,mutex);nextc:=Buffer(out) out:=(out+1)modn;

Ssignal(mutex,empty);

consumetheiteminnextc; untillfalse;end

parend;end；二.利用AND信號量

解決生產(chǎn)者－消費(fèi)者問題三利用管程解決生產(chǎn)者-消費(fèi)者問題為生產(chǎn)者—消費(fèi)者問題建立一個(gè)管程，并命名為ProclucerConsumer。其中包括：數(shù)據(jù)結(jié)構(gòu)：

buffer:array[0,…,n-1]ofitem；

in,out:integer；

count:integer；//表示在緩沖池中已有產(chǎn)品的數(shù)目

notfull，notempty:condition；//條件變量，由過程cwait和csignal對它們進(jìn)行操作兩個(gè)過程：(1)put(item)過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，當(dāng)count≥n時(shí)，表示緩沖池已滿，生產(chǎn)者須等待，將自己阻塞在notfull隊(duì)列中。(2)get(item)過程。消費(fèi)者利用該過程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count≤0時(shí)，表示緩沖池中已無可取用的產(chǎn)品，消費(fèi)者應(yīng)等待，將自己阻塞在notempty隊(duì)列中。TYPEproducer_consumer=monitor

VARin,out,count:integer;

buffer:array[0..n-1]ofitem;

notfull,notempty:condition;

Procedureput(item)

begin

ifcount>=nthennotfull.wait;

buffer[in]:=item;

in:=(in+1)modn;

count:=count+1;

ifnotempty.queuethennotempty.signal;

end;Procedureget(item)beginifcount<=0thennotempty.wait;item:=buffer[out];out:=(out+1)modn;count:=count-1;ifnotfull.queuethennotfull.signal;end;beginin:=out:=0;count:=0;end三利用管程解決生產(chǎn)者-消費(fèi)者問題Producer:BEGIN

repeat

produceaniteminnextp;

PC.put(nextp);

untillfalse;END;Consumer:BEGIN

repeat

PC.get(nextc);

consumeraniteminnextc;

untillfalse;END;生產(chǎn)者、消費(fèi)者進(jìn)程不能直接訪問buffer，它們通過管程提供的過程調(diào)用間接訪問buffer。管程構(gòu)造了自己的互斥機(jī)制：生產(chǎn)者和消費(fèi)者進(jìn)程不可能同時(shí)訪問緩沖池。但對同步機(jī)制的實(shí)現(xiàn)，要求程序員把wait和signal原語放在合適的位置。可見，所有的同步、互斥機(jī)制都被限制在管程內(nèi)部，因此易于驗(yàn)證同步的正確性，易于檢查出錯(cuò)誤。而對于信號量，互斥和同步都屬于進(jìn)程的責(zé)任。另外，如果有一個(gè)管程被正確地使用，則所有進(jìn)程對臨界資源的使用都是正確的。而對于信號量，只有所有訪問臨界資源的進(jìn)程都能正確地使用信號量時(shí)，才能保證資源訪問的正確。三利用管程解決生產(chǎn)者-消費(fèi)者問題問題的描述：五個(gè)哲學(xué)家共用一張園桌，分別坐在周圍的五張椅子上，在園桌上有五個(gè)碗和五只筷子，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。平時(shí)，一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左右最靠近他的筷子，只有在他拿到兩只筷子時(shí)才能進(jìn)餐。進(jìn)餐完畢，放下筷子繼續(xù)思考。哲學(xué)家的生活包括兩種活動：即進(jìn)餐和思考。當(dāng)哲學(xué)家覺得餓時(shí)，