第4章進(jìn)程及進(jìn)程管理

學(xué)習(xí)內(nèi)容-64個(gè)學(xué)時(shí)第1章緒論第2章OS的結(jié)構(gòu)和硬件支持第3章OS的用戶接口第4章進(jìn)程及進(jìn)程管理第5章資源分配和調(diào)度第6章內(nèi)存管理（重點(diǎn)）-20個(gè)學(xué)時(shí)（包括實(shí)驗(yàn)學(xué)時(shí)）第7章設(shè)備管理（重點(diǎn)）-7個(gè)學(xué)時(shí)第8章文件系統(tǒng)（重點(diǎn)）-6個(gè)學(xué)時(shí)期末復(fù)習(xí)-1個(gè)學(xué)時(shí)（基礎(chǔ)）-10個(gè)學(xué)時(shí)（重點(diǎn)）-20個(gè)學(xué)時(shí)（包括實(shí)驗(yàn)學(xué)時(shí)）第4章進(jìn)程及進(jìn)程管理

4.1進(jìn)程引入（順序和并發(fā)程序）4.2進(jìn)程概念4.3進(jìn)程控制（進(jìn)程創(chuàng)建、撤銷、阻塞、喚醒）4.4進(jìn)程之間的約束關(guān)系（同步和互斥）4.5同步機(jī)構(gòu)4.6進(jìn)程互斥與同步的實(shí)現(xiàn)4.7進(jìn)程通信4.8線程（了解）4.10進(jìn)程調(diào)度24.1并發(fā)活動(dòng)——進(jìn)程的引入操作系統(tǒng)的特性之一是并發(fā)與共享，即在系統(tǒng)中（內(nèi)存）同時(shí)存在幾個(gè)相互獨(dú)立的程序，這些程序在系統(tǒng)中既交叉地運(yùn)行，又要共享系統(tǒng)中的資源，這就會(huì)引起一系列的問題，包括：對(duì)資源的競爭、運(yùn)行程序之間的通信、程序之間的合作與協(xié)同等等。要解決這些問題，用程序的概念已經(jīng)不能描述程序在內(nèi)存中運(yùn)行的狀態(tài)，必須引入新的概念——進(jìn)程。4.1.1順序程序一個(gè)程序由若干個(gè)程序段組成，這些程序段的執(zhí)行必須按照嚴(yán)格的先后次序順序地執(zhí)行，即只有當(dāng)一個(gè)操作結(jié)束后，才能開始后繼操作。這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。例：討論單道系統(tǒng)的工作情況用戶作業(yè)的處理，通常分為如下3個(gè)步驟：首先輸入用戶的程序和數(shù)據(jù)然后進(jìn)行計(jì)算最后打印計(jì)算結(jié)果例：討論單道系統(tǒng)的工作情況這三個(gè)順序執(zhí)行的操作分別設(shè)為：I：輸入操作C：計(jì)算操作P：輸出操作順序程序設(shè)計(jì)的特點(diǎn)傳統(tǒng)的程序設(shè)計(jì)方法是順序程序設(shè)計(jì)，即把一個(gè)程序設(shè)計(jì)成一個(gè)順序執(zhí)行的程序模塊。順序程序設(shè)計(jì)具有如下的特點(diǎn)：1.執(zhí)行的順序性一個(gè)程序的執(zhí)行是嚴(yán)格按序的，即每個(gè)操作必須在下一個(gè)操作開始之前結(jié)束。順序程序設(shè)計(jì)的特點(diǎn)2.環(huán)境的封閉性程序一旦開始執(zhí)行，其計(jì)算結(jié)果不受外界的影響，當(dāng)程序的初始條件給定之后，其后的狀態(tài)只能由程序本身確定，即只有本程序才能改變它。順序程序設(shè)計(jì)的特點(diǎn)3.計(jì)算過程的可再現(xiàn)性程序執(zhí)行的結(jié)果與初始條件有關(guān)，而與執(zhí)行時(shí)間（執(zhí)行速度）無關(guān)。即，只要程序的初始條件相同，它的執(zhí)行結(jié)果是相同的，不論它在什么時(shí)間執(zhí)行，也不管計(jì)算機(jī)的運(yùn)行速度。順序程序設(shè)計(jì)的特點(diǎn)順序程序設(shè)計(jì)的順序性、封閉性和再現(xiàn)性給程序的編制、調(diào)試帶來很大方便，其缺點(diǎn)是計(jì)算機(jī)系統(tǒng)效率不高。在計(jì)算機(jī)系統(tǒng)中只有一個(gè)程序在運(yùn)行，這個(gè)程序獨(dú)占系統(tǒng)中所有資源，其執(zhí)行不受外界影響。4.1.2并發(fā)程序例：在多道批處理系統(tǒng)中，對(duì)大量作業(yè)的處理在系統(tǒng)中有n個(gè)作業(yè)，每個(gè)作業(yè)都有3個(gè)處理步驟，輸入數(shù)據(jù)、處理、輸出，即Ii,Ci,Pi(i=1,2,3,...,n)。批量作業(yè)執(zhí)行的先后次序4.1.2程序的并發(fā)執(zhí)行這些作業(yè)在系統(tǒng)中執(zhí)行時(shí)是對(duì)時(shí)間的偏序：有些操作必須在其它操作之前執(zhí)行，這是有序的；但有些操作是可以同時(shí)執(zhí)行的。也就是說：I1、C1、P1的執(zhí)行必須嚴(yán)格按照I1、C1、P1的順序，I2、C2、P2的執(zhí)行也必須嚴(yán)格按照I2、C2、P2的順序，而C1與I2，P1與C2、I3是可以同時(shí)執(zhí)行的。討論(1)哪些程序段的執(zhí)行必須是順序的？為什么？(2)哪些程序段的執(zhí)行可以是并行的？為什么？并發(fā)執(zhí)行的條件該條件在1966年首先由Bernstein提出，又稱之為Bernstein條件假設(shè)，對(duì)于程序pi：R(pi)={a1，a2，…，an}，表示程序pi在執(zhí)行期間引用的變量集，即要讀的變量集合；W(pi)={b1，b2，…，bm}，表示程序pi在執(zhí)行期間改變的變量集，即要寫的變量集合；若兩個(gè)程序p1和p2能滿足Bernstein條件：引用變量集與改變變量集交集之和為空集。并發(fā)執(zhí)行的條件Bernstein條件：任意兩個(gè)程序P(i)和P(j)，有：R(pi)W(pj)=;W(pi)R(pj)=;W(pi)W(pj)=;前兩條保證程序在讀數(shù)據(jù)時(shí)數(shù)據(jù)沒有變化；最后一條保證寫的結(jié)果不沖突。

并發(fā)執(zhí)行的條件例如，有如下四條語句：S1:a:=x+yS2:b:=z+1S3:c:=a-bS4:w:=c+1哪些語句能并發(fā)執(zhí)行？哪些語句不能并發(fā)執(zhí)行？并發(fā)執(zhí)行的條件分析有：R(S1)={x，y}，R(S2)={z}，R(S3)={a，b}，R(S4)={c}；W(S1)={a}，W(S2)=，W(S3)={c}，W(S4)={w}?？梢奡1和S2可并發(fā)執(zhí)行，因?yàn)?，滿足Bernstein條件。其他語句間因變量交集之和非空，并發(fā)執(zhí)行可能會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。程序并發(fā)執(zhí)行（定義）程序并發(fā)執(zhí)行：若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始，即使這種重迭是很小的，也稱這幾個(gè)程序段是并發(fā)執(zhí)行的。程序并發(fā)執(zhí)行的描述程序并發(fā)執(zhí)行的描述：cobegin

S1;S2;S3;...;SNcoend;其中Si(i=1,2,3,...,n)表示n個(gè)語句（程序段），這n個(gè)語句用cobegin和coend括起來表示這n個(gè)語句是可以并發(fā)執(zhí)行的。說明：co是concurrent的頭兩個(gè)字符。這是著名的荷蘭計(jì)算機(jī)科學(xué)家Dijkstra提出的。程序并發(fā)執(zhí)行的描述假設(shè)有一個(gè)程序有S0-Sn+1個(gè)語句，其中S1-Sn語句是并發(fā)執(zhí)行的，程序描述如下：

S0;

cobegin

S1;S2;S3;...;SN

coend;Sn+1;采用并發(fā)程序設(shè)計(jì)的目的目的是：充分發(fā)揮硬件的并行性，消除處理器和I/O設(shè)備的互等現(xiàn)象，提高系統(tǒng)效率。機(jī)器部件能并行工作僅僅是有了提高效率的可能性，其實(shí)現(xiàn)還需要軟件技術(shù)去利用和發(fā)揮，這種軟件技術(shù)就是并發(fā)程序設(shè)計(jì)。并發(fā)程序設(shè)計(jì)是多道程序設(shè)計(jì)的基礎(chǔ)，多道程序的實(shí)質(zhì)就是把并發(fā)程序設(shè)計(jì)引入到單處理器的系統(tǒng)中。思考順序程序有一個(gè)很大的特性就是：運(yùn)行結(jié)果具有確定性，與程序的運(yùn)行時(shí)間及運(yùn)行速度無關(guān)。那么，當(dāng)程序并發(fā)執(zhí)行時(shí)是否還具有這個(gè)特性呢？4.1.3與時(shí)間有關(guān)的錯(cuò)誤兩個(gè)交互的并發(fā)進(jìn)程，其中一個(gè)進(jìn)程對(duì)另一個(gè)進(jìn)程的影響常常是不可預(yù)期的，甚至無法再現(xiàn)。這是因?yàn)閮蓚€(gè)并發(fā)進(jìn)程執(zhí)行的相對(duì)速度不可預(yù)測，交互進(jìn)程的速率不僅受到處理器調(diào)度的影響，而且還受到與其交互的并發(fā)進(jìn)程的影響，甚至受到與其無關(guān)的其他進(jìn)程的影響，所以，一個(gè)進(jìn)程的速率通常無法為另一個(gè)進(jìn)程所知。4.1.3與時(shí)間有關(guān)的錯(cuò)誤因此，對(duì)資源的共享充滿了危險(xiǎn)，各種與時(shí)間有關(guān)的錯(cuò)誤就可能出現(xiàn)，與時(shí)間有關(guān)的錯(cuò)誤有兩種表現(xiàn)形式：結(jié)果不唯一永遠(yuǎn)等待為了說明與時(shí)間有關(guān)的錯(cuò)誤，現(xiàn)觀察下面的例子：例1（結(jié)果不唯一）購買飛機(jī)票問題假設(shè)一個(gè)飛機(jī)訂票系統(tǒng)有兩個(gè)終端，分別運(yùn)行進(jìn)程Tl和T2。該系統(tǒng)的公共數(shù)據(jù)區(qū)中的一些單元Aj(j=l，2，…)分別存放某月某日某次航班的余票數(shù)，Tl和T2共享Aj。飛機(jī)票售票程序如下：例1（結(jié)果不唯一）購買飛機(jī)票問題。例1（結(jié)果不唯一）購買飛機(jī)票問題由于T1

和T2

是兩個(gè)可以同時(shí)執(zhí)行的并發(fā)進(jìn)程，它們?cè)谕粋€(gè)計(jì)算機(jī)系統(tǒng)中運(yùn)行，共享與余票數(shù)Aj，因此，有可能出現(xiàn)幾種不同的運(yùn)行情況。并發(fā)多道程序，有3個(gè)特點(diǎn)：多道宏觀上并行微觀上串行微觀上串行的含義是多道程序輪流和分時(shí)的占有處理機(jī)，交替執(zhí)行。當(dāng)這個(gè)交替執(zhí)行交替的不巧的時(shí)候，就會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。例1（結(jié)果不唯一）購買飛機(jī)票問題例如，可能出現(xiàn)如下所示的運(yùn)行情況：T1:X1=Aj;//（T1執(zhí)行此處暫停，T2執(zhí)行）T2:X2=Aj;T2:X2=X2-1;Aj=X2;輸出一張票；//（T2執(zhí)行完畢后，T1才接著執(zhí)行）T1:X1=X1-1;Aj=X1;輸出一張票；例1（結(jié)果不唯一）購買飛機(jī)票問題假設(shè)初值A(chǔ)j=5，在這種執(zhí)行順序下買了兩張票，可是Aj的終值卻為4。（為什么？）顯然，兩個(gè)旅客各自都買到了一張同天同次航班的機(jī)票，可是，Aj的值實(shí)際上只減去了1，造成余票數(shù)不正確。特別是，當(dāng)某次航班只有一張余票時(shí)，就可能把這一張票同時(shí)售給了兩位旅客，這是不能允許的。思考1：再考慮另外一種情況：T1:X1=Aj;T1:X1=X1-1;Aj=X1;輸出一張票；T2:X2=Aj;T2:X2=X2-1;Aj=X2;輸出一張票；還假設(shè)初值A(chǔ)j=5，在這種執(zhí)行順序下買了兩張票，可是Aj的終值為多少？（思考之）答案：為3，沒有出錯(cuò)。思考2：而如果出現(xiàn)如下所示的運(yùn)行情況：T1:X1=Aj;T2:X2=Aj;T1:X1=X1-1;Aj=X1;輸出一張票；T2:X2=X2-1;Aj=X2;輸出一張票；還假設(shè)初值A(chǔ)j=5，在這種執(zhí)行順序下買了兩張票，可是Aj的終值為多少？（思考之）答案：為4，還是出現(xiàn)一票兩買。例2（永遠(yuǎn)等待）內(nèi)存管理問題假定有兩個(gè)并發(fā)進(jìn)程borrow和return分別負(fù)責(zé)申請(qǐng)和歸還主存資源，算法描述中，x表示現(xiàn)有的空閑主存總量，B表示申請(qǐng)或歸還的主存量。并發(fā)進(jìn)程算法及執(zhí)行描述如下：34例2（永遠(yuǎn)等待）內(nèi)存管理問題由于borrow和return共享了表示主存物理資源的變量x，對(duì)并發(fā)執(zhí)行不加限制會(huì)導(dǎo)致錯(cuò)誤。例如，一個(gè)進(jìn)程調(diào)用borrow申請(qǐng)主存，在執(zhí)行了比較B和x的指令后，發(fā)現(xiàn)B>x，但在將要執(zhí)行{申請(qǐng)進(jìn)程進(jìn)入等待隊(duì)列等主存資源}時(shí)（這條語句沒有執(zhí)行），另一個(gè)進(jìn)程調(diào)用return搶先執(zhí)行，歸還了所借全部的主存資源。這時(shí)，由于前一個(gè)進(jìn)程borrow還未成為等待狀態(tài)，return中的{釋放等主存資源的進(jìn)程}相當(dāng)于空操作，即，當(dāng)前等待隊(duì)列中沒有進(jìn)程。以后當(dāng)調(diào)用borrow的進(jìn)程被設(shè)置成等主存資源狀態(tài)時(shí)，可能己經(jīng)沒有其他進(jìn)程來歸還主存資源了，從而，申請(qǐng)資源的進(jìn)程borrow可能永遠(yuǎn)處于等待狀態(tài)。一道考研題兄弟倆共用一個(gè)賬戶，每次限存或取10元，存錢與取錢的進(jìn)程如下所示，由于兄弟倆可能同時(shí)存錢和取錢，因此兩個(gè)進(jìn)程是并發(fā)的。若哥哥先存了兩次錢，但在哥哥第三次存錢時(shí)，弟弟在取錢，請(qǐng)問最后的帳號(hào)上amount可能有多少錢？（南京大學(xué)2000年考題5分）：答案：amount=20,30,10答案分析4種情況：savetake,amount=20;takesave,amount=20;takesavetake（take沒有運(yùn)行完，先運(yùn)行前2個(gè)語句，等save運(yùn)行完之后，再運(yùn)行最后一條語句）,amount=10;savetakesave（save沒有運(yùn)行完，先運(yùn)行前2個(gè)語句，等take運(yùn)行完之后，再運(yùn)行最后一條語句）,amount=30;并發(fā)程序的特點(diǎn)并發(fā)程序執(zhí)行雖然提高了系統(tǒng)的處理能力和機(jī)器的利用率，但它也帶來了一些新的問題，產(chǎn)生了與順序程序不同的特征：一、失去了程序的封閉性和可再現(xiàn)性

如果程序執(zhí)行的結(jié)果是一個(gè)與時(shí)間無關(guān)的函數(shù)，即具有封閉性。若一個(gè)程序的執(zhí)行可改變另一個(gè)程序的變量（共享變量,例如，現(xiàn)有內(nèi)存數(shù)x，銀行賬號(hào)amount），程序執(zhí)行的結(jié)果不僅依賴于程序的初始條件，還依賴于程序執(zhí)行時(shí)的相對(duì)速度，在這種情況下就失去了程序的封閉性。一、失去了程序的封閉性和可再現(xiàn)性

例：討論共享公共變量的兩個(gè)程序，它們執(zhí)行時(shí)可能產(chǎn)生的不同結(jié)果。設(shè)：初值n=0，程序A每執(zhí)行一次都要做n加1的操作，程序B每隔一定時(shí)間打印出n值，并將它重新置為零。程序A、B并發(fā)執(zhí)行。討論n的最終值與其打印值。舉例說明n=0;舉例說明即產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤——結(jié)果不唯一000100二、程序與計(jì)算不再一一對(duì)應(yīng)在程序順序執(zhí)行時(shí)，一個(gè)程序總是對(duì)應(yīng)一個(gè)具體的計(jì)算。但在程序的并發(fā)執(zhí)行時(shí)，可能有多用戶共享使用同一個(gè)程序，但處理（計(jì)算）的對(duì)象卻是不同的。例如，在多用戶環(huán)境下，可能同時(shí)有多個(gè)用戶調(diào)用C語言的編譯程序，這就是典型的一個(gè)程序?qū)?yīng)多個(gè)用戶源程序的情況。二、程序與計(jì)算不再一一對(duì)應(yīng)三、程序并發(fā)執(zhí)行的相互制約在多道程序設(shè)計(jì)的環(huán)境下，程序是并發(fā)執(zhí)行的。即系統(tǒng)中有多道程序在“同時(shí)”執(zhí)行，這些程序之間要共享系統(tǒng)的資源，程序之間有合作（通信）的關(guān)系。合作與競爭產(chǎn)生一系列的矛盾，這些矛盾實(shí)際上是一種相互制約，有直接的也有間接。直接的相互制約關(guān)系-同步間接的相互制約關(guān)系-互斥歷史回顧回頭來，我們?cè)倏纯床僮飨到y(tǒng)的第三個(gè)特性：不確定性：在多道程序環(huán)境中，允許多個(gè)進(jìn)程并發(fā)執(zhí)行，由于資源有限而進(jìn)程眾多，多數(shù)情況，進(jìn)程的執(zhí)行不是一貫到低，而是“走走停?！薄Ｋ伎迹翰l(fā)和并行的區(qū)別并行和并發(fā)的區(qū)別

并行同一時(shí)刻，兩個(gè)事物均處于活動(dòng)狀態(tài)例如：多CPU環(huán)境下，每個(gè)程序有各自的CPU，真正的同時(shí)執(zhí)行

并發(fā)（多道程序運(yùn)行方式）宏觀上存在并行特征，微觀上存在順序性同一時(shí)刻，只有一個(gè)事物處于活動(dòng)狀態(tài)例如：分時(shí)操作系統(tǒng)中多個(gè)程序的同時(shí)運(yùn)行，共享CPU（只有一個(gè)CPU），輪流使用CPU49OS對(duì)進(jìn)程的要求OS必須交替執(zhí)行多個(gè)進(jìn)程，以便最大程度的使用CPU，同時(shí)提供合理的響應(yīng)時(shí)間。OS必須將資源分配給進(jìn)程，同時(shí)避免死鎖（永遠(yuǎn)等待）。OS必須支持進(jìn)程間通信以及用戶進(jìn)程創(chuàng)建。50第4章進(jìn)程及進(jìn)程管理

4.1進(jìn)程引入（順序和并發(fā)程序）4.2進(jìn)程概念4.3進(jìn)程控制（進(jìn)程創(chuàng)建、撤銷、阻塞、喚醒）4.4進(jìn)程之間的約束關(guān)系（同步和互斥）4.5同步機(jī)構(gòu)4.6進(jìn)程互斥與同步的實(shí)現(xiàn)4.7進(jìn)程通信4.8線程（了解）4.10進(jìn)程調(diào)度514.2.1進(jìn)程的定義在多道程序設(shè)計(jì)的環(huán)境下，為了描述程序在計(jì)算機(jī)系統(tǒng)內(nèi)的執(zhí)行情況，必須引人新的概念－－進(jìn)程。進(jìn)程的概念來自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系統(tǒng)中也曾叫過任務(wù)（task)。進(jìn)程的定義-很多行為的一個(gè)規(guī)則叫做程序，程序在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動(dòng)稱為進(jìn)程（Dijkstra）。進(jìn)程是這樣的計(jì)算部分，它是可以和其它計(jì)算并行的一個(gè)計(jì)算。(Donovan)進(jìn)程（有時(shí)稱為任務(wù)）是一個(gè)程序與其數(shù)據(jù)一道通過處理機(jī)的執(zhí)行所發(fā)生的活動(dòng)。（Alan.C.Shaw）進(jìn)程是執(zhí)行中的程序。（KenThompsonandDennisRitchie）教材上給出的進(jìn)程的定義：進(jìn)程，即是一個(gè)具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次活動(dòng)。進(jìn)程與程序的區(qū)別與聯(lián)系1、程序是指令的集合，是靜態(tài)的概念。進(jìn)程是程序在處理機(jī)上的一次執(zhí)行的過程，是動(dòng)態(tài)的概念。程序可以作為軟件資料長期保存。進(jìn)程是有生命周期的。2、進(jìn)程是一個(gè)獨(dú)立的運(yùn)行單位，能與其它進(jìn)程并行（并發(fā)）活動(dòng)。而程序則不是。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è)程序。閱讀菜譜準(zhǔn)備原料烹制菜肴飯菜閱讀洗衣機(jī)手冊(cè)準(zhǔn)備衣服、洗衣粉設(shè)定參數(shù)，洗衣服干凈衣服程序輸入運(yùn)行輸出程序輸入運(yùn)行輸出分時(shí)切換洗衣進(jìn)程做飯進(jìn)程進(jìn)程與程序的區(qū)別55進(jìn)程的類型在系統(tǒng)中同時(shí)有多個(gè)進(jìn)程存在，但歸納起來有兩大類：1、系統(tǒng)進(jìn)程：執(zhí)行操作系統(tǒng)核心代碼的進(jìn)程。系統(tǒng)進(jìn)程起著資源管理和控制的作用。2、用戶進(jìn)程：執(zhí)行用戶程序的進(jìn)程。系統(tǒng)進(jìn)程與用戶進(jìn)程的區(qū)別1、系統(tǒng)進(jìn)程被分配一個(gè)初始的資源集合，這些資源可以為它獨(dú)占，也能以最高優(yōu)先權(quán)的資格使用。用戶進(jìn)程通過系統(tǒng)服務(wù)請(qǐng)求的手段競爭使用系統(tǒng)資源；2、用戶進(jìn)程不能直接做I/O操作，而系統(tǒng)進(jìn)程可以做顯示的、直接的I/O操作。3、系統(tǒng)進(jìn)程在管態(tài)下活動(dòng)，而用戶進(jìn)程則在用戶態(tài)（目態(tài)）下活動(dòng)。4.2.2進(jìn)程的狀態(tài)進(jìn)程在系統(tǒng)中的活動(dòng)規(guī)律是：執(zhí)行——暫?！獔?zhí)行進(jìn)程的三種基本狀態(tài)：運(yùn)行狀態(tài)就緒狀態(tài)等待狀態(tài)（又稱阻塞、掛起、睡眠）進(jìn)程的基本狀態(tài)1、就緒狀態(tài)（Ready)存在于處理機(jī)調(diào)度隊(duì)列中的那些進(jìn)程，它們已經(jīng)準(zhǔn)備就緒，一旦得到CPU，就立即可以運(yùn)行，這些進(jìn)程所取的狀態(tài)為就緒狀態(tài)。（可有多個(gè)進(jìn)程處于此狀態(tài)）2、運(yùn)行狀態(tài)(Running）當(dāng)進(jìn)程由調(diào)度/分派程序分派后，得到CPU控制權(quán)，它的程序正在運(yùn)行，該進(jìn)程所處的狀態(tài)為運(yùn)行狀態(tài)。（在系統(tǒng)中，某一時(shí)刻，總是只有一個(gè)進(jìn)程處于此狀態(tài)，這也就是所謂的微觀上串行。）3、等待狀態(tài)（Wait)若一個(gè)進(jìn)程正在等待某個(gè)事件的發(fā)生（如等待I/O的完成），而暫停執(zhí)行，這時(shí)，即使給它CPU，它也無法執(zhí)行，則稱該進(jìn)程處于等待狀態(tài)。進(jìn)程狀態(tài)變遷圖進(jìn)程的狀態(tài)不是固定不變的，而是在不斷變換。如下圖所示：61AThree-stateProcessModelReadyRunningBlockedEventOccursDispatchTime-outEventWait運(yùn)行就緒等待進(jìn)程的狀態(tài)及其轉(zhuǎn)換-動(dòng)畫63在進(jìn)程運(yùn)行過程中，由于進(jìn)程自身進(jìn)展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換：

就緒—運(yùn)行（進(jìn)程調(diào)度）

運(yùn)行—就緒（時(shí)間片到等）

運(yùn)行—等待（服務(wù)請(qǐng)求，如請(qǐng)求I/O等）

等待—就緒（服務(wù)完成/事件來到）進(jìn)程狀態(tài)轉(zhuǎn)換：進(jìn)程轉(zhuǎn)換就緒運(yùn)行調(diào)度程序選擇一個(gè)新的進(jìn)程運(yùn)行運(yùn)行就緒運(yùn)行進(jìn)程用完了時(shí)間片運(yùn)行進(jìn)程被中斷，因?yàn)橐粋€(gè)高優(yōu)先級(jí)進(jìn)程處于就緒狀態(tài)進(jìn)程轉(zhuǎn)換運(yùn)行等待OS尚未完成服務(wù)(例如，系統(tǒng)功能調(diào)用)對(duì)一資源的訪問尚不能進(jìn)行初始化I/O且必須等待結(jié)果等待某一進(jìn)程提供輸入等待就緒當(dāng)所等待的事件發(fā)生時(shí)/請(qǐng)求的服務(wù)已經(jīng)完成創(chuàng)建狀態(tài)：創(chuàng)建一個(gè)新的進(jìn)程終止?fàn)顟B(tài)：完成任務(wù)，結(jié)束進(jìn)程掛起（suspend）狀態(tài)進(jìn)程沒有占用內(nèi)存空間處在掛起狀態(tài)的進(jìn)程映像在磁盤上進(jìn)程的其它狀態(tài)五狀態(tài)進(jìn)程模型操作系統(tǒng)的控制結(jié)構(gòu)操作系統(tǒng)作為資源管理和分配程序，其本質(zhì)任務(wù)是自動(dòng)控制程序的執(zhí)行，并滿足進(jìn)程執(zhí)行過程中提出的資源使用要求。因此，操作系統(tǒng)的核心控制結(jié)構(gòu)是進(jìn)程結(jié)構(gòu)(如何定義和實(shí)現(xiàn)它？)，資源管理的數(shù)據(jù)結(jié)構(gòu)將圍繞進(jìn)程結(jié)構(gòu)展開。在研究進(jìn)程的控制結(jié)構(gòu)之前，首先介紹一下操作系統(tǒng)的控制結(jié)構(gòu)。操作系統(tǒng)的控制結(jié)構(gòu)為了有效的管理進(jìn)程和資源，操作系統(tǒng)必須掌握每一個(gè)進(jìn)程和資源的當(dāng)前狀態(tài)。操作系統(tǒng)通常是通過構(gòu)造一組表（思考：表是什么？怎么編程實(shí)現(xiàn)？）來管理和維護(hù)進(jìn)程和每一類資源的信息。操作系統(tǒng)的控制表分為四類：進(jìn)程控制表存儲(chǔ)控制表I/O控制表文件控制表操作系統(tǒng)的控制結(jié)構(gòu)71操作系統(tǒng)的控制結(jié)構(gòu)進(jìn)程控制表用來管理進(jìn)程及其相關(guān)信息。存儲(chǔ)控制表用來管理一級(jí)（主）存儲(chǔ)器和二級(jí)（輔）存儲(chǔ)器。I/O控制表用來管理計(jì)算機(jī)系統(tǒng)的I/O設(shè)備和通道。文件控制表用來管理文件。4.2.3進(jìn)程的描述——進(jìn)程控制塊(1)什么是進(jìn)程控制塊？描述進(jìn)程與其他進(jìn)程、系統(tǒng)資源的關(guān)系以及進(jìn)程在各個(gè)不同時(shí)期所處的狀態(tài)的數(shù)據(jù)結(jié)構(gòu)（怎么去編程實(shí)現(xiàn)？），稱為進(jìn)程控制塊pcb(processcontrolblock)或稱為進(jìn)程描述器(processdescriptor)。4.2.3進(jìn)程的描述——進(jìn)程控制塊系統(tǒng)利用PCB來控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志。進(jìn)程與PCB是一一對(duì)應(yīng)的。進(jìn)程控制塊進(jìn)程控制塊PCB集中反映一個(gè)進(jìn)程的動(dòng)態(tài)特征。在進(jìn)程并發(fā)執(zhí)行時(shí)，由于資源共享，帶來各進(jìn)程之間的相互制約。顯然，為了反映這些制約關(guān)系和資源共享關(guān)系，在創(chuàng)建一個(gè)進(jìn)程時(shí)，應(yīng)首先創(chuàng)建其PCB（怎么創(chuàng)建？），然后才能根據(jù)PCB中的信息對(duì)進(jìn)程實(shí)施有效的管理和控制。當(dāng)一個(gè)進(jìn)程完成其功能時(shí)之后，系統(tǒng)則釋放PCB（怎么釋放？），進(jìn)程也隨之消亡。一個(gè)比喻：PCB就象我們的戶口。PCB的結(jié)構(gòu)PCB的結(jié)構(gòu)說明1、進(jìn)程標(biāo)識(shí)符/name：每個(gè)進(jìn)程都必須有一個(gè)唯一的標(biāo)識(shí)符，可以是字符串，也可以是一個(gè)數(shù)字。UNIX系統(tǒng)中就是一個(gè)整型數(shù)，在進(jìn)程創(chuàng)建時(shí)由系統(tǒng)賦予。2、進(jìn)程當(dāng)前狀態(tài)status：說明本進(jìn)程目前處于何種狀態(tài)（運(yùn)行、就緒、等待），作為進(jìn)程調(diào)度時(shí)的主要依據(jù)。PCB的結(jié)構(gòu)說明3、當(dāng)前隊(duì)列指針next：登記與本進(jìn)程處于同一隊(duì)列的下一個(gè)進(jìn)程的PCB的地址。PCB的結(jié)構(gòu)說明4、總鏈指針all-q-next：登記在系統(tǒng)總鏈隊(duì)列中，下一個(gè)進(jìn)程的pcb地址。5、執(zhí)行程序開始地址

start-addr：該進(jìn)程的程序?qū)拇说刂烽_始執(zhí)行。6、進(jìn)程優(yōu)先級(jí)priority：

進(jìn)程的優(yōu)先級(jí)反映進(jìn)程的緊迫程度，通常由用戶指定和系統(tǒng)設(shè)置。PCB的結(jié)構(gòu)說明7、CPU現(xiàn)場保護(hù)區(qū)cpustatus：當(dāng)處理機(jī)被中斷時(shí)，各種寄存器的內(nèi)容都必須保存在被中斷進(jìn)程的PCB中，以便在該進(jìn)程重新執(zhí)行時(shí)，能從斷點(diǎn)繼續(xù)執(zhí)行。通常被保護(hù)的信息有：通用寄存器、指令計(jì)數(shù)器PC以及程序狀態(tài)字PSW等。例如，我們下課，這時(shí)我要記住這次講到什么地方，以便下次課接著講。PCB的結(jié)構(gòu)說明8.通信信息communicationinformation：每個(gè)進(jìn)程在運(yùn)行過程中和別的進(jìn)程進(jìn)行通信時(shí)所記錄的有關(guān)信息。9.家族關(guān)系processfamily：有的系統(tǒng)還允許一個(gè)進(jìn)程創(chuàng)建自己的子進(jìn)程，這樣會(huì)形成一個(gè)進(jìn)程家族。在pcb中必須指明本進(jìn)程與家族的關(guān)系，如它的子進(jìn)程和父進(jìn)程的標(biāo)識(shí)符。PCB的結(jié)構(gòu)說明10.占有資源清單own-resource

記錄進(jìn)程占用系統(tǒng)資源的情況。說明：PCB包含的這些信息，通常占幾百-幾千字節(jié)思考：如何編程實(shí)現(xiàn)這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)struct？PCB的實(shí)現(xiàn)？實(shí)驗(yàn)：進(jìn)程調(diào)度實(shí)驗(yàn)中用到的主要數(shù)據(jù)結(jié)構(gòu)是進(jìn)程控制塊PCB，其結(jié)構(gòu)如圖所示：數(shù)據(jù)項(xiàng)作用next前向指針，指向下一個(gè)進(jìn)程控制塊，用來構(gòu)成進(jìn)程隊(duì)列process_name進(jìn)程名稱process_number進(jìn)程號(hào)，當(dāng)進(jìn)程有相同名稱時(shí)，用來區(qū)分進(jìn)程process_start_moment進(jìn)程啟動(dòng)時(shí)刻process_need_time進(jìn)程要求運(yùn)行時(shí)間process_time_slice時(shí)間片process_priority優(yōu)先數(shù)PCB的實(shí)現(xiàn)typedefstructpcb{ structpcb*next;//下一個(gè)進(jìn)程控制塊指針 charprocess_name[20];//進(jìn)程名 intprocess_number;//進(jìn)程編號(hào) intprocess_start_moment;//進(jìn)程啟動(dòng)時(shí)刻 intprocess_need_time;//要求運(yùn)行時(shí)間 intprocess_time_slice;//時(shí)間片 intprocess_priority;//優(yōu)先數(shù)}PCB;//自定義數(shù)據(jù)類型：進(jìn)程控制塊PCBpcb_table[MAX_PROCESS];//進(jìn)程控制塊表，數(shù)組進(jìn)程控制塊表即數(shù)組pcb_table說明：隊(duì)列指針為了便于對(duì)進(jìn)程實(shí)施管理，通常把具有相同狀態(tài)的進(jìn)程鏈接在一起，組成各種隊(duì)列。例如：把所有處于就緒狀態(tài)的進(jìn)程鏈在一起，稱為就緒隊(duì)列。把所有因等待某事件而處于等待狀態(tài)的進(jìn)程鏈在一起就形成了等待（阻塞）隊(duì)列。PCB的組成方式在一個(gè)系統(tǒng)中，通?？蓳碛袛?shù)十個(gè)、數(shù)百個(gè)，乃至數(shù)千個(gè)PCB，為了能對(duì)它們進(jìn)行有效的管理，應(yīng)該用適當(dāng)?shù)姆绞綄⑺鼈兘M織起來，目前常用的組織方式有兩種：鏈接方式、索引方式。系統(tǒng)中進(jìn)程隊(duì)列分類：就緒隊(duì)列、等待隊(duì)列、運(yùn)行隊(duì)列。就緒隊(duì)列：整個(gè)系統(tǒng)一個(gè)等待隊(duì)列：每一個(gè)等待事件一個(gè)運(yùn)行隊(duì)列：單機(jī)系統(tǒng)中整個(gè)系統(tǒng)一個(gè)88PCB表組織方式-索引方式索引表就緒隊(duì)列等待隊(duì)列1等待隊(duì)列2PCB1PCB2PCB3PCB4PCB5PCB6PCB7…PCBnPCB表系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)，建立幾張索引表，例如：就緒索引表，阻塞索引表等，在索引表的表目中，記錄具有相應(yīng)狀態(tài)的PCB在PCB表中的地址。進(jìn)程隊(duì)列及其管理當(dāng)發(fā)生的某個(gè)事件使一個(gè)進(jìn)程的狀態(tài)發(fā)生變化時(shí)，這個(gè)進(jìn)程就要退出所在的某個(gè)隊(duì)列而排入到另一個(gè)隊(duì)列中去。一個(gè)進(jìn)程從一個(gè)所在的隊(duì)列中退出的事件稱為出隊(duì)。一個(gè)進(jìn)程排入到一個(gè)指定的隊(duì)列中的事件稱為入隊(duì)。處理器調(diào)度中負(fù)責(zé)入隊(duì)和出隊(duì)工作的功能模塊稱為隊(duì)列管理模塊，簡稱隊(duì)列管理。下圖給出了操作系統(tǒng)的隊(duì)列管理和狀態(tài)轉(zhuǎn)換示意圖。91①就緒隊(duì)列結(jié)構(gòu)及指針①就緒隊(duì)列結(jié)構(gòu)及指針編程實(shí)現(xiàn)PCB*ready_q_start=&pcb_table[0];//就緒隊(duì)列頭指針指向第一個(gè)進(jìn)程②等待隊(duì)列結(jié)構(gòu)及指針②等待隊(duì)列結(jié)構(gòu)及指針③運(yùn)行指針③運(yùn)行指針編程實(shí)現(xiàn)例子：先來先服務(wù)進(jìn)程調(diào)度算法：選擇就緒隊(duì)列的隊(duì)首進(jìn)程讓其運(yùn)行running=ready_q_start;//將就緒隊(duì)列的頭指針指向的第一個(gè)進(jìn)程的地址賦值給running指針④總鏈隊(duì)列結(jié)構(gòu)及指針系統(tǒng)中存在大量的進(jìn)程，它們依各自的狀態(tài)分別處于相應(yīng)的隊(duì)列中，這便于對(duì)進(jìn)程實(shí)施調(diào)度。但是當(dāng)進(jìn)行某些管理功能時(shí)，如創(chuàng)建進(jìn)程的功能時(shí)（進(jìn)程的初始化），就感到系統(tǒng)具有所有進(jìn)程的總鏈?zhǔn)鞘址奖愕?。譬如檢查進(jìn)程名是否重名，進(jìn)入各個(gè)隊(duì)列中查詢是很麻煩的。進(jìn)程控制塊表即數(shù)組pcb_table第4章進(jìn)程及進(jìn)程管理

4.1進(jìn)程引入（順序和并發(fā)程序）4.2進(jìn)程概念4.3進(jìn)程控制（進(jìn)程創(chuàng)建、撤銷、阻塞、喚醒）4.4進(jìn)程之間的約束關(guān)系（同步和互斥）4.5同步機(jī)構(gòu)4.6進(jìn)程互斥與同步的實(shí)現(xiàn)4.7進(jìn)程通信4.8線程（了解）4.10進(jìn)程調(diào)度1024.3.1進(jìn)程控制的概念進(jìn)程是有生命周期的，產(chǎn)生、運(yùn)行、暫停、終止。對(duì)進(jìn)程的這些操作叫進(jìn)程控制。進(jìn)程控制的職責(zé)是對(duì)系統(tǒng)中全部進(jìn)程實(shí)施有效的管理，它是處理機(jī)管理的部分（另一部分是進(jìn)程調(diào)度）。進(jìn)程控制進(jìn)程控制包括：

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

進(jìn)程撤消、

進(jìn)程阻塞、

進(jìn)程喚醒這些操作都要對(duì)應(yīng)地執(zhí)行一個(gè)特殊的程序段（操作系統(tǒng)核心程序），同時(shí)系統(tǒng)也通過系統(tǒng)調(diào)用給用戶提供進(jìn)程控制的功能。教材上叫原語（一種特殊的系統(tǒng)調(diào)用）。4.3.1進(jìn)程控制的概念原語的概念原語是一種特殊的系統(tǒng)調(diào)用命令，它可以完成一個(gè)特定的功能，一般為外層軟件所調(diào)用，其特點(diǎn)是原語執(zhí)行時(shí)是不可中斷的，所以原語操作具有原子性，它是不可再分的。常用的進(jìn)程控制原語常用的進(jìn)程控制原語有：創(chuàng)建原語撤消原語阻塞原語喚醒原語4.3.2進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建原語的形式:create(name,priority,start_addr)其中：name為被創(chuàng)建進(jìn)程的標(biāo)識(shí)符priority為進(jìn)程優(yōu)先級(jí)start_addr為程序的開始地址UNIX/Linux系統(tǒng)：fork()108109進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建原語的功能：創(chuàng)建一個(gè)具有指定標(biāo)識(shí)符的進(jìn)程，建立進(jìn)程的PCB結(jié)構(gòu)。進(jìn)程創(chuàng)建的步驟所謂資源池也就是pcb的集合，它是在系統(tǒng)存儲(chǔ)區(qū)域開辟的一片區(qū)域，用來集中存放所有的進(jìn)程控制塊。自己編程實(shí)現(xiàn)？首先為進(jìn)程分配一個(gè)唯一標(biāo)識(shí)號(hào)ID初始化進(jìn)程控制塊表即數(shù)組pcb_table編程實(shí)現(xiàn)如何實(shí)現(xiàn)：向PCB資源池/進(jìn)程控制表里申請(qǐng)一個(gè)空的PCB？設(shè)置一個(gè)pcb_free指針，該指針總是指向第一個(gè)空的PCB。PCB*pcb_free=NULL;//進(jìn)程空閑隊(duì)列的頭指針，初始為空pcb_free=&pcb_table[0];//編程實(shí)現(xiàn)if(pcb_free==NULL)//如果無空閑的PCB則返回空指針returnNULL;else //如果有空閑的PCB{pcb_free=pcb_free->next;//空閑PCB指針下移一個(gè)節(jié)點(diǎn)PCB初始化；PCB插入就緒隊(duì)列和總鏈隊(duì)列；}進(jìn)程創(chuàng)建后隊(duì)列的變化圖-修改鏈接指針編程實(shí)現(xiàn)新建的PCB插入就緒隊(duì)列隊(duì)尾：PCB*p=pcb_free;//定義了一個(gè)局部變量p，代表新建進(jìn)程if(pcb_ready==NULL) //如果就緒隊(duì)列為空pcb_ready=pcb_ready_rear=p;//則新PCB為就緒隊(duì)列的唯一節(jié)點(diǎn)，隊(duì)首指針與隊(duì)尾指針相同else //如果就緒隊(duì)列不空，新建的PCB插入就緒隊(duì)列隊(duì)尾{ pcb_ready_rear->next=p;//原就緒隊(duì)列的最后一個(gè)節(jié)點(diǎn)指向新建的PCB pcb_ready_rear=p;//修改就緒隊(duì)列的尾指針，指向新建的PCB}4.3.2進(jìn)程撤銷進(jìn)程完成其任務(wù)，希望終止時(shí)，調(diào)用撤消進(jìn)程的系統(tǒng)調(diào)用（進(jìn)程撤消原語）撤消進(jìn)程。（相當(dāng)于某人死亡后，就要去派出所消戶口）在一般操作系統(tǒng)中進(jìn)程撤消的系統(tǒng)調(diào)用是：killUNIX系統(tǒng)中是exit()

4.3.2進(jìn)程撤銷撤消進(jìn)程以下幾種情況導(dǎo)致進(jìn)程被撤消：該進(jìn)程已完成所要求的功能而正常終止由于某種錯(cuò)誤導(dǎo)致非正常終止父進(jìn)程要求撤消某個(gè)子進(jìn)程進(jìn)程撤銷進(jìn)程撤消原語的形式：kill(或exit)該命令沒有參數(shù)，其執(zhí)行結(jié)果也無返回信息。進(jìn)程撤消原語的功能：撤消當(dāng)前運(yùn)行的進(jìn)程。將該進(jìn)程的pcb結(jié)構(gòu)歸還到pcb資源池，所占用的資源歸還給父進(jìn)程，從總鏈隊(duì)列中摘除它。進(jìn)程撤銷4.3.3進(jìn)程阻塞進(jìn)程阻塞亦稱進(jìn)程等待：當(dāng)一個(gè)處在運(yùn)行狀態(tài)的進(jìn)程，因等待某個(gè)事件的發(fā)生（如等待打印機(jī)）而不能繼續(xù)運(yùn)行時(shí)，將調(diào)用進(jìn)程阻塞系統(tǒng)調(diào)用，把進(jìn)程的狀態(tài)設(shè)置為阻塞狀態(tài)，并調(diào)用進(jìn)程調(diào)度程序（等于讓出處理機(jī)）。4.3.3進(jìn)程阻塞進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)換成阻塞狀態(tài)是由進(jìn)程阻塞原語實(shí)現(xiàn)的，因此，調(diào)用進(jìn)程阻塞操作是在進(jìn)程處于運(yùn)行狀態(tài)下執(zhí)行的。它的執(zhí)行將引起等待某事件的隊(duì)列的改變。例如，進(jìn)程是因等待打印機(jī)而進(jìn)入阻塞狀態(tài)，則該進(jìn)程將加入到等待打印機(jī)的隊(duì)列。4.3.3進(jìn)程阻塞進(jìn)程阻塞的內(nèi)部調(diào)用形式（UNIX系統(tǒng)）：sleep(chan,pri)其中：chan表示進(jìn)程掛起（睡眠）的原因pri進(jìn)程被喚醒后的優(yōu)先級(jí)

一般調(diào)用形式：susp(chan)4.3.3進(jìn)程阻塞4.3.3進(jìn)程阻塞

在阻塞隊(duì)列中插入了一個(gè)新的進(jìn)程4.3.3進(jìn)程喚醒一個(gè)正在運(yùn)行的進(jìn)程會(huì)因等待某事件（例如，等待打印機(jī)）的發(fā)生，由運(yùn)行狀態(tài)轉(zhuǎn)換成阻塞狀態(tài)。而當(dāng)它等待的事件發(fā)生后，這個(gè)進(jìn)程將由阻塞狀態(tài)轉(zhuǎn)換成就緒狀態(tài)。這種轉(zhuǎn)換由進(jìn)程喚醒操作完成。1294.3.3進(jìn)程喚醒進(jìn)程喚醒原語的形式：wakeup(chan)參數(shù)chan：進(jìn)程等待的原因進(jìn)程喚醒原語的功能：當(dāng)進(jìn)程等待的事件發(fā)生時(shí)，喚醒等待該事件的所有進(jìn)程或等待該事件的首進(jìn)程。4.3.3進(jìn)程喚醒例如，打印機(jī)在完成了打印完成的操作后，就去檢查等待打印機(jī)的隊(duì)列，若不為空，則調(diào)用進(jìn)程喚醒操作，喚醒一個(gè)（或多個(gè)）等待打印機(jī)的進(jìn)程。

4.3.3進(jìn)程喚醒算法：wakeup輸入：chan：等待的事件（阻塞原因）輸出：無{

找到chan的等待隊(duì)列的指針；

for(該隊(duì)列不為空）

{從隊(duì)列中移出一個(gè)進(jìn)程；設(shè)置進(jìn)程狀態(tài)為“就緒”，并加入到就緒隊(duì)列；

}}4.3.3進(jìn)程喚醒按此算法，是把等待在chan事件上的所有進(jìn)程喚醒。也有的系統(tǒng)只喚醒一個(gè)等待chan事件的進(jìn)程，若這樣處理，等待隊(duì)列就要按某種優(yōu)先級(jí)排隊(duì)。進(jìn)程喚醒操作會(huì)引起就緒隊(duì)列和等待chan事件的等待隊(duì)列發(fā)生變化。復(fù)習(xí)：進(jìn)程的阻塞與喚醒

阻塞原因：請(qǐng)求系統(tǒng)服務(wù)；啟動(dòng)某種操作，如I/O；新數(shù)據(jù)尚未到達(dá)；暫時(shí)無新工作可做等。當(dāng)出現(xiàn)阻塞事件，進(jìn)程調(diào)用阻塞原語將自己阻塞。并將其狀態(tài)變?yōu)椤白枞麪顟B(tài)”，并進(jìn)入相應(yīng)事件的阻塞隊(duì)列；當(dāng)阻塞進(jìn)程期待的事件發(fā)生，有關(guān)進(jìn)程調(diào)用喚醒原語，將等待該事件的進(jìn)程喚醒。并將其狀態(tài)變?yōu)椤熬途w狀態(tài)”，插入就緒隊(duì)列。一般,進(jìn)程可以自己阻塞自己；而喚醒操作則由操作系統(tǒng)，或其它相關(guān)進(jìn)程來完成，進(jìn)程無法自己喚醒自己。

第4章進(jìn)程及進(jìn)程管理

4.1進(jìn)程引入（順序和并發(fā)程序）4.2進(jìn)程概念4.3進(jìn)程控制（進(jìn)程創(chuàng)建、撤銷、阻塞、喚醒）4.4進(jìn)程之間的約束關(guān)系（同步和互斥）4.5同步機(jī)構(gòu)4.6進(jìn)程互斥與同步的實(shí)現(xiàn)4.7進(jìn)程通信4.8線程（了解）4.10進(jìn)程調(diào)度1354.4進(jìn)程的相互制約關(guān)系在多道程序的環(huán)境中，系統(tǒng)中的多個(gè)進(jìn)程可以并發(fā)執(zhí)行，同時(shí)它們又要共享系統(tǒng)中的資源，這些資源有些是可共享使用的，如磁盤，有些是以獨(dú)占方式使用的，如打印機(jī)。由此將會(huì)引起一系列的矛盾，產(chǎn)生錯(cuò)綜復(fù)雜的相互制約的關(guān)系。產(chǎn)生這種錯(cuò)綜復(fù)雜的相互制約關(guān)系的原因有二：資源共享進(jìn)程合作進(jìn)程間的關(guān)系進(jìn)程之間有兩種關(guān)系：第一種是競爭關(guān)系，從而有進(jìn)程的互斥是解決進(jìn)程間競爭關(guān)系的手段。第二種是協(xié)作關(guān)系，某些進(jìn)程為完成同一任務(wù)需要分工協(xié)作。進(jìn)程的同步是解決進(jìn)程間協(xié)作關(guān)系的手段。進(jìn)程間的關(guān)系進(jìn)程的互斥是指若干個(gè)進(jìn)程要使用同一共享資源時(shí)，任何時(shí)刻最多允許一個(gè)進(jìn)程去使用，其它要使用該資源的進(jìn)程必須等待，直到占有資源的進(jìn)程釋放該資源。臨界區(qū)管理可以解決進(jìn)程互斥問題，后續(xù)課程將詳細(xì)介紹臨界區(qū)的解決方案。動(dòng)畫-互斥進(jìn)程間的關(guān)系進(jìn)程的同步是解決進(jìn)程間協(xié)作關(guān)系的手段。指一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程的消息，當(dāng)一個(gè)進(jìn)程沒有得到來自于另一個(gè)進(jìn)程的消息時(shí)則等待，直到消息到達(dá)才被喚醒。動(dòng)畫-同步進(jìn)程間的關(guān)系對(duì)于協(xié)作關(guān)系有如下例子：設(shè)input、process、和output三個(gè)進(jìn)程分工協(xié)作完成讀入數(shù)據(jù)、加工處理和打印輸出任務(wù)，這是一種典型的協(xié)作關(guān)系。操作系統(tǒng)要確保諸進(jìn)程在執(zhí)行次序上協(xié)調(diào)一致：沒有輸入完一塊數(shù)據(jù)之前不能加工處理沒有加工處理完一塊數(shù)據(jù)之前不能打印輸出等等4.4.2互斥的概念例子：宿舍固定電話的使用打印機(jī)的使用還有內(nèi)存變量、指針、數(shù)組等等也是臨界資源臨界資源說明例1：兩個(gè)進(jìn)程A、B共享一臺(tái)打印機(jī)，

若不加以控制，兩個(gè)進(jìn)程的輸出結(jié)果可能交織在一起，很難區(qū)分。臨界資源說明例2：兩個(gè)進(jìn)程共享一個(gè)變量x，設(shè)：x代表某航班機(jī)座號(hào)，p1和p2兩個(gè)售票進(jìn)程，售票工作是對(duì)變量x加1。這兩個(gè)進(jìn)程在一個(gè)處理機(jī)C上并發(fā)執(zhí)行，兩個(gè)進(jìn)程共享一個(gè)變量x時(shí)，兩種可能的執(zhí)行次序：情況B為x=10+1

說明以前的課程也講到了與時(shí)間有關(guān)的錯(cuò)誤，其實(shí)就是因?yàn)楣蚕碜兞?，這個(gè)共享的變量就是臨界資源。如果不對(duì)臨界資源加以控制，那么就可能出現(xiàn)錯(cuò)誤，這就是本節(jié)要解決的問題。什么是臨界資源特點(diǎn)：當(dāng)兩個(gè)進(jìn)程公用一個(gè)變量時(shí)，它們必須順序地使用，一個(gè)進(jìn)程對(duì)公用變量操作完畢后，另一個(gè)進(jìn)程才能去訪問和修改這一變量。一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。

哪些是臨界資源？臨界資源：物理設(shè)備，如輸入機(jī)、打印機(jī)、磁帶機(jī)等都具有這種性質(zhì)。軟件資源，如公用變量、數(shù)據(jù)、表格、隊(duì)列等也都具有這一特點(diǎn)。什么是臨界區(qū)臨界區(qū)：在每個(gè)進(jìn)程中，訪問臨界資源的那段程序能夠從概念上分離出來，稱為臨界區(qū)或臨界段。動(dòng)畫什么是臨界區(qū)什么是互斥？互斥：在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某一存儲(chǔ)區(qū)域時(shí)，就不允許其他進(jìn)程來讀出或者修改存儲(chǔ)區(qū)的內(nèi)容，否則，就會(huì)發(fā)生后果無法估計(jì)的錯(cuò)誤。進(jìn)程間的這種相互制約關(guān)系稱為互斥。例如上圖所示：進(jìn)程A正在執(zhí)行csa段時(shí)，進(jìn)程B就不能進(jìn)入csb段執(zhí)行。151進(jìn)入臨界區(qū)的準(zhǔn)則：進(jìn)入臨界區(qū)的準(zhǔn)則：每次至多有一個(gè)進(jìn)程處于臨界區(qū)當(dāng)有若干個(gè)進(jìn)程欲進(jìn)入臨界區(qū)時(shí)，應(yīng)在有限的時(shí)間內(nèi)使其進(jìn)入（有限等待）進(jìn)程在臨界區(qū)內(nèi)僅逗留有限的時(shí)間4.5.1鎖和上鎖、開鎖操作解決進(jìn)程互斥的最簡單的辦法是加鎖。什么是鎖：用變量w代表某種資源的狀態(tài)，w稱為“鎖”。鎖位值：為“0”表示資源可用為"1"表示資源已被占用（不可用）

在系統(tǒng)中為每個(gè)臨界資源設(shè)置一個(gè)鎖位4.5.1鎖和上鎖、開鎖操作當(dāng)一個(gè)進(jìn)程使用某個(gè)臨界資源之前必須完成下列操作：1、考察鎖位的值(是0還是1)；2、若原來的值是為“0”，將鎖位置為“1”，此為上鎖操作（表示準(zhǔn)備占用該資源）；3、若原來的值是為“1”，（該資源已被別人占用），則不改變?cè)瓉淼闹?，循環(huán)檢測等待。4、當(dāng)某進(jìn)程使用完資源后，將鎖位置為“0”

，稱為開鎖操作，此時(shí)別的等待進(jìn)程一旦檢測到w的不為1了，則表示可以使用臨界資源了。4.5.1鎖和上鎖、開鎖操作說明在上述簡單的上鎖原語中，goto語句使得lock(w)原語的進(jìn)程占用處理機(jī)而等待進(jìn)入互斥段（稱為忙等待busywaiting)測試法，浪費(fèi)CPU時(shí)間。為此，可將上述上鎖原語和開鎖原語做進(jìn)一步修改。修改后的原語如下所示：改進(jìn)的lock和unlock算法經(jīng)過鎖處理，任何時(shí)候都不可能有兩個(gè)及以上的進(jìn)程進(jìn)入臨界區(qū)。

4.6.1用上鎖原語和開鎖原語實(shí)現(xiàn)互斥假設(shè)有兩個(gè)進(jìn)程共享打印機(jī)，兩個(gè)進(jìn)程中使用打印機(jī)的程序段為臨界區(qū)。為保證打印的正確，設(shè)置打印機(jī)的鎖print，其初值為“0”，表示打印機(jī)可用。4.6.1用上鎖原語和開鎖原語實(shí)現(xiàn)互斥4.5.2信號(hào)燈的概念前面介紹的方法雖能保證互斥，可以正確解決臨界區(qū)問題，但有明顯缺點(diǎn)：對(duì)不能進(jìn)入臨界區(qū)的進(jìn)程，采用忙式等待(busywaiting)測試法，浪費(fèi)CPU時(shí)間。將測試能否進(jìn)入臨界區(qū)的責(zé)任推給各個(gè)競爭的進(jìn)程會(huì)削弱系統(tǒng)的可靠性，加重了用戶編程的負(fù)擔(dān)。4.5.2信號(hào)燈的概念1965年荷蘭的計(jì)算機(jī)科學(xué)家Dijkstra提出了新的同步工具——信號(hào)量和P、V操作。他將交通管制中多種顏色的信號(hào)燈管理交通的方法引入操作系統(tǒng)，讓兩個(gè)或多個(gè)進(jìn)程通過信號(hào)量(Semaphore)展開交互。進(jìn)程在某一特殊點(diǎn)上停止執(zhí)行直到得到一個(gè)對(duì)應(yīng)的信號(hào)量，通過信號(hào)量這一設(shè)施，任何復(fù)雜的進(jìn)程交互要求都可以得到滿足，這種特殊的變量就是信號(hào)量。4.5.2信號(hào)燈的概念信號(hào)量只能由同步原語對(duì)其進(jìn)行操作（原語是操作系統(tǒng)中執(zhí)行時(shí)不可中斷的過程、即原子操作）。Dijkstra發(fā)明了兩個(gè)同步原語：P操作和V操作（荷蘭語中“測試(Proberen)”

和“增量(Verhogen)”

的頭字母。）利用信號(hào)量和P、V操作既可以解決并發(fā)進(jìn)程的競爭問題，又可以解決并發(fā)進(jìn)程的協(xié)作問題。信號(hào)燈的分類信號(hào)量按其用途可分為兩種：公用信號(hào)量：聯(lián)系一組并發(fā)進(jìn)程，相關(guān)的進(jìn)程均可在此信號(hào)量上執(zhí)行P和V操作。初值常常為1，用于實(shí)現(xiàn)進(jìn)程互斥。私有信號(hào)量：聯(lián)系一組并發(fā)進(jìn)程，僅允許此信號(hào)量擁有的進(jìn)程執(zhí)行P操作，而其他相關(guān)進(jìn)程可在其上施行V操作。初值常常為0或正整數(shù)，用于并發(fā)進(jìn)程同步。信號(hào)燈的分類信號(hào)量按其取值可分為兩種：二元信號(hào)量：僅允許取值為0和1，主要用于解決進(jìn)程互斥問題（非我即你，通常用一個(gè)布爾量來表示）。一般信號(hào)量：允許取值為非負(fù)整數(shù)，主要用于解決進(jìn)程間的同步問題。4.5.2信號(hào)燈的概念信號(hào)燈的定義：信號(hào)燈是一個(gè)確定的二元組（s,q），s是一個(gè)具有非負(fù)初值的整型變量，q是一個(gè)初始狀態(tài)為空的隊(duì)列。

S代表資源的實(shí)體。在實(shí)際應(yīng)用中應(yīng)準(zhǔn)確地說明s的意義和初值，每個(gè)信號(hào)燈都有一個(gè)隊(duì)列，其初始狀態(tài)為空。4.5.2P、V操作信號(hào)燈的值只能由P、V操作來改變。對(duì)信號(hào)燈的P操作記為：P(S)，P操作是一個(gè)原子操作。對(duì)信號(hào)燈的V操作記為：V(S),V操作是一個(gè)原子操作。信號(hào)量值的物理意義信號(hào)燈是整型變量。變量值≥0時(shí)，表示綠燈，進(jìn)程執(zhí)行。變量值<0時(shí)，表示紅燈，進(jìn)程停止執(zhí)行。4.5.2P、V操作P操作：s值減1；若相減結(jié)果大于等于0，則進(jìn)程繼續(xù)執(zhí)行；若結(jié)果小于0，則該進(jìn)程掛起。注：推起該進(jìn)程包括：保留調(diào)用進(jìn)程CPU現(xiàn)場；置“等待”狀態(tài)；入等待隊(duì)列；轉(zhuǎn)進(jìn)程調(diào)度；消耗掉一個(gè)資源4.5.2P、V操作V操作：s值加1；若相加結(jié)果大于0，進(jìn)程繼續(xù)執(zhí)行；否則，喚醒一個(gè)（或多個(gè)）等待該信號(hào)燈的進(jìn)程?；厥找粋€(gè)資源用P、V操作解決進(jìn)程間互斥問題P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)4.6.2用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥例子：兩個(gè)進(jìn)程共享打印機(jī)。設(shè)信號(hào)燈print表示打印機(jī)，初值為1，表示打印機(jī)可用(也可理解為有一臺(tái)打印機(jī))。說明：print是用于互斥的信號(hào)燈，教材上設(shè)置為mutex，設(shè)置成何種符號(hào)無所謂，只要可讀性好即可。4.6.2用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥信號(hào)量的物理意義S>0：其數(shù)值代表可用的資源數(shù)量S=0：代表無資源可用，但也沒有等待的進(jìn)程，即也沒有申請(qǐng)資源的進(jìn)程S<0：其|S|表示等待隊(duì)列中想申請(qǐng)資源而還沒有成功的進(jìn)程數(shù)量用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥的例子設(shè)：x代表某航班機(jī)座號(hào)，p1和p2兩個(gè)售票進(jìn)程，售票工作是對(duì)變量x加1。試用信號(hào)燈的P、V操作實(shí)現(xiàn)這兩個(gè)進(jìn)程的互斥。設(shè)：mutex為互斥信號(hào)燈，初值為1（通過pv操作，可以解決與時(shí)間有關(guān)的錯(cuò)誤）五個(gè)哲學(xué)家就餐問題下面再來看一下使用互斥信號(hào)量和PV操作解決操作系統(tǒng)經(jīng)典的五個(gè)哲學(xué)家就餐問題。有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤子，每兩人之間放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。五個(gè)哲學(xué)家就餐-動(dòng)畫演示179五個(gè)哲學(xué)家就餐問題在這道題目中，每一把叉子都是必須互斥使用的，因此應(yīng)為每把叉子（臨界資源）設(shè)置一個(gè)互斥信號(hào)量Si，初值均為1。#typedefintsemaphere;semaphorechopstick[5];for(inti=0;i<=4;i++)chopstick[i]=1;//因?yàn)榫鶠榛コ庑盘?hào)量，故初始化為1五個(gè)哲學(xué)家就餐問題當(dāng)一個(gè)哲學(xué)家吃通心面前必須獲得自己左邊和右邊的兩把叉子，即執(zhí)行兩個(gè)P操作，吃完通心面后必須放下叉子，即執(zhí)行兩個(gè)V操作。程序如下：cobeginprocessPi//i=0,1,2,3,4begin

L1:

思考…；饑餓…；P(chopstick[i])；//拿左叉子P(chopstick[(i+1)mod5]);//拿右叉子

吃通心面…；

V(chopstick[i]);//放下左叉子V(chopstick[(i+1)mod5]);//放下右叉子

gotoL1;end;coend;思考：這樣做能保證每個(gè)哲學(xué)家都能吃到面嗎？五個(gè)哲學(xué)家就餐問題分析請(qǐng)大家注意，如果五個(gè)哲學(xué)家同時(shí)變得饑餓的話，且同時(shí)拿起他左邊的叉子。這樣所有的chopstick都變成0。就有可能出現(xiàn)每個(gè)哲學(xué)家舉起左邊的一把叉子，卻又在永遠(yuǎn)等待相鄰哲學(xué)家手中的叉子的情況——哲學(xué)家就都會(huì)餓死。死鎖現(xiàn)象-永遠(yuǎn)等待五個(gè)哲學(xué)家就餐問題分析思考：如果增加一條指令：吃不到就放下自己手中的叉子，這樣哲學(xué)家就不會(huì)餓死嗎？這樣同樣會(huì)導(dǎo)致哲學(xué)家會(huì)餓死，因?yàn)榭赡茉谏厦娴那闆r下，五個(gè)哲學(xué)家因?yàn)樽约撼圆坏綎|西，同時(shí)放下叉子，因?yàn)榇蠹疫€餓著呢，環(huán)顧一看左右都有叉子，可能又同時(shí)拿起叉子，就這樣，同時(shí)拿起，同時(shí)放下…循環(huán)往復(fù)。哲學(xué)家們不餓死，也得累死。這就是——死鎖情況。并發(fā)進(jìn)程臨界區(qū)的管理原則計(jì)算機(jī)專家Dijkstra在1965年提出臨界區(qū)設(shè)計(jì)原則，即一組并發(fā)進(jìn)程互斥執(zhí)行時(shí)必須滿足：空閑讓進(jìn)：當(dāng)無進(jìn)程在臨界區(qū)時(shí)，任何有權(quán)使用臨界區(qū)的進(jìn)程都可進(jìn)入忙則等待：不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū)有限等待：任何進(jìn)入臨界區(qū)的要求在有限時(shí)間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU，以使其他進(jìn)程有機(jī)會(huì)得到CPU的使用權(quán)同步的例子引例1：兩位同學(xué)約好星期天去東湖，早上8:00在校門口，不見不散。當(dāng)一個(gè)同學(xué)先來到校門口，要等另一個(gè)同學(xué)，到齊后一道打的去東湖。同步的例子——病員就診187同步的概念互斥的概念來自于多個(gè)進(jìn)程對(duì)獨(dú)占使用資源（設(shè)備）的競爭，同步來源于多個(gè)進(jìn)程的合作。在人類社會(huì)中競爭與合作是永恒的。同步的定義：所謂同步就是并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要相互等待與互通消息，這樣的相互制約關(guān)系稱為進(jìn)程同步。4.6.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步在操作系統(tǒng)中，同步有各種各樣，但歸納起來有兩類：諸進(jìn)程合作完成某工作的邏輯順序：如看病拿藥問題對(duì)系統(tǒng)資源的共享：如兩個(gè)進(jìn)程共享一個(gè)（或多個(gè)）打印機(jī)，一個(gè)（或多個(gè)）變量4.6.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步用信號(hào)燈及P、V操作來描述左圖1、說明進(jìn)程的同步關(guān)系進(jìn)程P1、P2可并發(fā)執(zhí)行，P3的執(zhí)行必須等待P1、P2都完成后才能開始執(zhí)行。2、設(shè)置信號(hào)燈，說明含義、初值初值s13=0表示進(jìn)程P1尚未執(zhí)行完成；初值s23=0表示進(jìn)程P2尚未執(zhí)行完成；4.6.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步P、V操作實(shí)現(xiàn)合作進(jìn)程的同步練習(xí)：設(shè)pa、pb、pc為一組合作進(jìn)程，其進(jìn)程流圖如右圖所示，試用信號(hào)燈的p、v操作實(shí)現(xiàn)這三個(gè)進(jìn)程的同步。解答(1)三個(gè)進(jìn)程的同步關(guān)系：pa先執(zhí)行，當(dāng)它結(jié)束后pb、pc可以開始執(zhí)行。(2)信號(hào)燈設(shè)置：設(shè)兩個(gè)同步信號(hào)燈sb、sc分別表示進(jìn)程pb和pc能否開始執(zhí)行，其初值均為0。解答共享緩沖區(qū)的合作進(jìn)程的同步例：計(jì)算進(jìn)程cp和打印進(jìn)程iop公用一個(gè)單緩沖（buffer大小為1個(gè)字節(jié)），為了完成正確的計(jì)算與打印，試用信號(hào)燈的p、v操作實(shí)現(xiàn)這兩個(gè)進(jìn)程的同步。4.6.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步分析：CP進(jìn)程不斷產(chǎn)生字符，送buffer，IOP進(jìn)程從buffer中取出字符打印。如不加控制，會(huì)有多種打印結(jié)果，這取決于這兩個(gè)進(jìn)程運(yùn)行的相對(duì)速度。在這眾多的打印結(jié)果中，只有CP、IOP進(jìn)程的運(yùn)行剛好匹配的一種是對(duì)的，其它均為錯(cuò)誤，并且不能重現(xiàn)。4.6.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步要保證打印結(jié)果的正確，CP、IOP必須遵循以下同步規(guī)則，兩個(gè)進(jìn)程的同步關(guān)系如下：當(dāng)CP把結(jié)果送入buffer后，IOP才能從buffer中取，否則IOP必須等待；當(dāng)IOP從buffer中取走數(shù)據(jù)后，CP才能將新產(chǎn)生數(shù)據(jù)送buffer，否則也必須等待。1974.6.3用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步解決這個(gè)問題的步驟：分析問題，弄清楚同步關(guān)系，如上分析；設(shè)置信號(hào)燈，說明含義、初值；寫出程序描述。198用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步信號(hào)燈設(shè)置：設(shè)置兩個(gè)信號(hào)燈sa和sb。信號(hào)燈sa--表示緩沖區(qū)中是否有可供打印的計(jì)算結(jié)果，其初值為0。信號(hào)燈sb--表示緩沖區(qū)有無空位置存放新的信息，其初值為1。用信號(hào)燈實(shí)現(xiàn)進(jìn)程的同步信號(hào)量的小結(jié)信號(hào)量值的小結(jié)（回顧）：S>0：其數(shù)值代表可用的資源數(shù)量S=0：代表無資源可用，但也沒有等待的進(jìn)程，即也沒有申請(qǐng)資源的進(jìn)程S<0：其|S|表示等待隊(duì)列中想申請(qǐng)資源而還沒有成功的進(jìn)程數(shù)量信號(hào)量的小結(jié)P和V的位置放置的小結(jié)：對(duì)于互斥資源：P、V操作在同一個(gè)進(jìn)程中。對(duì)于共享資源的同步：P、V操作在不同進(jìn)程中（強(qiáng)調(diào)的是你中有我，我中有你的協(xié)作關(guān)系）P和V信號(hào)量的初始化：必須置一次初值，且只能置一次初值初值必須>=0，不能為負(fù)值4.6.4多緩沖的生產(chǎn)者－消費(fèi)者問題

問題描述：若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，“生產(chǎn)者”進(jìn)程不斷寫入，而“消費(fèi)者”進(jìn)程不斷讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。即滿足如下條件：（1）消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的。（2）生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的。動(dòng)畫：生產(chǎn)者和消費(fèi)者生產(chǎn)者－消費(fèi)者的例子例1：計(jì)算進(jìn)程和打印進(jìn)程：計(jì)算進(jìn)程cp不斷產(chǎn)生數(shù)據(jù)，是生產(chǎn)者；打印進(jìn)程iop不斷打印數(shù)據(jù)，是消費(fèi)者。例2：通信問題：發(fā)消息進(jìn)程send不斷產(chǎn)生消息，是生產(chǎn)者；收消息進(jìn)程receive不斷接收消息，是消費(fèi)者。

生產(chǎn)者--消費(fèi)者問題圖示生產(chǎn)者與消費(fèi)者生產(chǎn)者：當(dāng)有界緩沖區(qū)中無空位置時(shí)，要等待；向有界緩沖區(qū)放入物品后，要發(fā)消息。消費(fèi)者：當(dāng)有界緩沖區(qū)中無物品時(shí)，要等待；從有界緩沖區(qū)取出物品后，要發(fā)消息。多緩沖區(qū)的P-C問題之間的關(guān)系一、同步關(guān)系：對(duì)于生產(chǎn)者進(jìn)程：產(chǎn)生一個(gè)數(shù)據(jù)，當(dāng)要送入緩沖區(qū)時(shí)，要檢查緩沖區(qū)是否已滿，若未滿，則可將數(shù)據(jù)送入緩沖區(qū)，并通知消費(fèi)者進(jìn)程；否則，等待；對(duì)于消費(fèi)者進(jìn)程：當(dāng)它去取數(shù)據(jù)時(shí)，要看緩沖區(qū)中是否有數(shù)據(jù)可取，若有則取走一個(gè)數(shù)據(jù)，并通知生產(chǎn)者進(jìn)程，否則，等待。這種相互等待，并互通信息就是典型的進(jìn)程同步。多緩沖區(qū)的P-C問題之間的關(guān)系二、互斥關(guān)系緩沖區(qū)是臨界資源，在多個(gè)進(jìn)程在生產(chǎn)產(chǎn)品時(shí)，它不允許在緩沖區(qū)的某一個(gè)單元同時(shí)存放產(chǎn)品；也不允許多個(gè)進(jìn)程同時(shí)消費(fèi)緩沖區(qū)的某一個(gè)單元產(chǎn)品，因此，還有個(gè)互斥的問題。多生產(chǎn)者-消費(fèi)者問題的一般解答信號(hào)燈設(shè)置：兩個(gè)同步信號(hào)燈：empty：表示空緩沖區(qū)的數(shù)目，初值為有界緩沖區(qū)的大小nfull：表示滿緩沖區(qū)的數(shù)目，其初值為0一個(gè)互斥信號(hào)燈：mutex：互斥信號(hào)燈，初值為1同步描述程序描述程序描述動(dòng)畫演示214思考與說明如果我們把消費(fèi)者進(jìn)程中的兩個(gè)P操作交換次序，即那么會(huì)有什么問題嗎？參見下圖的程序參考：主程序216并發(fā)程序思考與說明在這個(gè)問題中P操作的次序是很重要的，如果我們把消費(fèi)者進(jìn)程中的兩個(gè)P操作交換次序，那么就會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。分析如下：分析說明在某個(gè)時(shí)刻，消費(fèi)者消費(fèi)的比較快，把所有的產(chǎn)品消費(fèi)完，有：empty=n，mutex=1，full=0接著消費(fèi)者進(jìn)程運(yùn)行到1處，使得mutex=0，運(yùn)行到2處full=-1<0，消費(fèi)者進(jìn)程等待接著，生產(chǎn)者進(jìn)程運(yùn)行到3處，由于生產(chǎn)了一個(gè)產(chǎn)品，故空位置-1，empty=n-1，運(yùn)行到4處，由于p(mutex)操作，mutex=mutex-1=-1<0，生產(chǎn)者進(jìn)程也等待。故而，這兩個(gè)程序陷于相互等待的死鎖狀態(tài)。思考思考與延伸：交換生產(chǎn)者的兩個(gè)p操作會(huì)不會(huì)帶來與時(shí)間有關(guān)的錯(cuò)誤呢？如果會(huì)，在什么情況下會(huì)？請(qǐng)分析之。程序見下圖：思考與說明思考與結(jié)論所以，在使用PV操作實(shí)現(xiàn)進(jìn)程同步時(shí)，特別要當(dāng)心P操作的次序，而V操作的次序倒是無關(guān)緊要的。一般來說，用于互斥的信號(hào)量上的P操作，總是在用于協(xié)作的P操作之后執(zhí)行。即，同步的P操作在互斥的P操作之前。P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí)，它們處于同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要，同步P操作在互斥P操作前而兩個(gè)V操作的順序無關(guān)緊要信號(hào)量及P、V操作總結(jié)P.V操作的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，而且表達(dá)能力強(qiáng)（用P.V操作可解決任何同步互斥問題）缺點(diǎn)：不夠安全：P.V操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜信號(hào)量及P、V操作總結(jié)一道考研題蘋果桔子問題：桌上有一只盤子，最多可以容納兩個(gè)水果，每次只能放入/取出一只水果；爸爸專向盤子中放蘋果(apple)，媽媽專向盤子中放桔子(orange)，兩個(gè)兒子專等吃盤子中的桔子，兩個(gè)女兒專等吃盤子里的蘋果。請(qǐng)用PV操作來實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步和互斥。（南京大學(xué)2000年）分析這個(gè)問題實(shí)際上是兩個(gè)生產(chǎn)者和兩個(gè)消費(fèi)者被連接到僅能放兩個(gè)產(chǎn)品的緩沖區(qū)上。生產(chǎn)者各自生產(chǎn)不同的產(chǎn)品，但就其本質(zhì)而言，他們是同一類生產(chǎn)者。而消費(fèi)者則各自取需要的產(chǎn)品消費(fèi)，他們的消費(fèi)方式不同。程序如下：main(){tpyedefintsemaphore;semaphoreempty；/*盤子里可以放幾個(gè)水果*/semaphoreorange;/*盤子里有桔子*/semaphoreapple;/*盤子里有蘋果*/semaphoremutex;/*不能同時(shí)對(duì)盤子操作的互斥量

empty

=2;/*盤子里最多放兩個(gè)水果*/

orange

=0;/*盤子里沒有桔子*/

apple

=0;/*盤子里沒有蘋果*/mutex=1cobegin/*可并發(fā)的進(jìn)程*/father();mother();son();daugher();

coend}father(){while(手中還有蘋果){

P(empty);P(mutex)；

向盤中放蘋果…；

V(mutex)；

V(apple);}}

mother(){while(手中還有桔子){

P(empty);P(mutex)；

向盤中放桔子…；

V(mutex)；

V(orange);}}

soni()//i=1，2{while(盤中還有蘋果){

P(apple);P(mutex)；

從盤中拿蘋果…；

V(mutex)；

V(empty);}}

daugheri()//i=1，2{while(盤中還有桔子){

P(orange);P(mutex)；

從盤中拿桔子…；

V(mutex)；

V(empty);}}

回顧：哲學(xué)家就餐問題問題描述：有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子哲學(xué)家就餐問題解法#defineN5voidphilosopher(inti){while(true){

思考；

P(fork[i]);P(fork[(i+1)%5])；進(jìn)食；

V(fork[i]);V(fork[(i+1)%5])；

}}為防止死鎖發(fā)生可采取的措施：最多允許4個(gè)哲學(xué)家同時(shí)去拿右/左邊的筷子（解1）給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿右邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之（解2）僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子-全部分配回顧：哲學(xué)家就餐問題最多允許4個(gè)哲學(xué)家同時(shí)去拿右邊的筷子設(shè)fork[5]為5個(gè)互斥信號(hào)量，初值均為1設(shè)信號(hào)量S，初值為4，S用于封鎖第5個(gè)哲學(xué)家無死鎖哲學(xué)家就餐問題---解1234Philosopheri：{

思考；

P(S);//S的值減1P(fork[i]);P(fork[(i+1)mod5])；吃飯；

V(fork[i]);V(fork[(i+1)mod5])；

V(S);}給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿右邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之。235無死鎖哲學(xué)家就餐問題---解2Philosopher1：{

思考；

P(fork[1]);//右邊的筷子P(fork[2]);//左邊的筷子吃飯；

V(fork[2]);V(fork[1])；}Philosopher2：{

思考；

P(fork[3]);P(fork[2])；吃飯；

V(fork[2]);V(fork[3])；}經(jīng)典問題讀者寫者問題問題描述：有兩組并發(fā)進(jìn)程:讀者和寫者,共享數(shù)據(jù)區(qū)要求：

允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作不允許多個(gè)寫者同時(shí)操作動(dòng)畫-讀者與寫者讀者-寫者問題分析如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但同時(shí)有其它讀者正在讀，則新讀者也可以讀（多個(gè)讀者可同時(shí)讀數(shù)據(jù)）3）有寫者正在寫，新讀者等（讀者和寫者不能同時(shí)操作）如果寫者來：1）無讀者，新寫者可以寫2）有讀者正在讀，新寫者等待（讀者和寫者不能同時(shí)操作）3）有其它寫者正在寫，新寫者等待（多個(gè)寫者不能同時(shí)寫數(shù)據(jù)）信號(hào)量w用于讀者和寫者、寫者和寫者之間的互斥（互斥信號(hào)量），即用來控制由誰使用共享數(shù)據(jù)區(qū)；變量readcount表示正在讀的讀者數(shù)目，它是一個(gè)臨界資源（因?yàn)槎鄠€(gè)讀者進(jìn)程都可以訪問readcount變量，而每次只能允許一個(gè)讀者進(jìn)程使用這個(gè)變量，所以readcount變量是一個(gè)臨界資源）；信號(hào)量mutex用于對(duì)readcount這個(gè)臨界資源的互斥訪問；所以，有兩個(gè)互斥信號(hào)量，初值w=1，mutex=1。讀者-寫者問題分析因?yàn)橹灰幸粋€(gè)讀者在讀，便不允許寫者去寫。所以：從第1個(gè)讀者進(jìn)入共享數(shù)據(jù)區(qū)開始，就不允許寫者去寫，即當(dāng)readcount+1后其值為1時(shí)，讀者進(jìn)程執(zhí)行p(w)，表示對(duì)共享數(shù)據(jù)區(qū)實(shí)行保護(hù)，不允許寫者去寫；當(dāng)最后1個(gè)讀者退出共享數(shù)據(jù)區(qū)之后，也就是當(dāng)共享數(shù)據(jù)區(qū)中沒有讀者時(shí)，就可以讓寫者進(jìn)來寫，即當(dāng)readcount-1后其值為0時(shí),讀者進(jìn)程執(zhí)行v(w)，讓出對(duì)共享數(shù)據(jù)區(qū)的使用權(quán)。讀者-寫者問題分析讀者：

read{P(mutex);readcount++;if(readcount==1)P(w);//禁止寫V(mutex);

讀

P(mutex);readcount--;if(readcount==0)V(w);//可以允許寫V(mutex);};寫者：

write{P(w);

寫

V(w);};//寫者在寫數(shù)據(jù)的時(shí)候不允許其他寫者寫，也不允許其他讀者讀。讀者-寫者問題的解法動(dòng)畫演示!//初始化mut