學習內容-64個學時第1章緒論第2章OS的結構和硬件支持第3章OS的用戶接口第4章進程及進程管理第5章資源分配和調度第6章內存管理（重點）-20個學時（包括實驗學時）第7章設備管理（重點）-7個學時第8章文件系統（重點）-6個學時期末復習-1個學時（基礎）-10個學時（重點）-20個學時（包括實驗學時）第4章進程及進程管理

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

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

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

S0;

cobegin

S1;S2;S3;...;SN

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

和T2

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

如果程序執行的結果是一個與時間無關的函數，即具有封閉性。若一個程序的執行可改變另一個程序的變量（共享變量,例如，現有內存數x，銀行賬號amount），程序執行的結果不僅依賴于程序的初始條件，還依賴于程序執行時的相對速度，在這種情況下就失去了程序的封閉性。一、失去了程序的封閉性和可再現性

例：討論共享公共變量的兩個程序，它們執行時可能產生的不同結果。設：初值n=0，程序A每執行一次都要做n加1的操作，程序B每隔一定時間打印出n值，并將它重新置為零。程序A、B并發執行。討論n的最終值與其打印值。舉例說明n=0;舉例說明即產生與時間有關的錯誤——結果不唯一000100二、程序與計算不再一一對應在程序順序執行時，一個程序總是對應一個具體的計算。但在程序的并發執行時，可能有多用戶共享使用同一個程序，但處理（計算）的對象卻是不同的。例如，在多用戶環境下，可能同時有多個用戶調用C語言的編譯程序，這就是典型的一個程序對應多個用戶源程序的情況。二、程序與計算不再一一對應三、程序并發執行的相互制約在多道程序設計的環境下，程序是并發執行的。即系統中有多道程序在“同時”執行，這些程序之間要共享系統的資源，程序之間有合作（通信）的關系。合作與競爭產生一系列的矛盾，這些矛盾實際上是一種相互制約，有直接的也有間接。直接的相互制約關系-同步間接的相互制約關系-互斥歷史回顧回頭來，我們再看看操作系統的第三個特性：不確定性：在多道程序環境中，允許多個進程并發執行，由于資源有限而進程眾多，多數情況，進程的執行不是一貫到低，而是“走走停停”。思考：并發和并行的區別并行和并發的區別

并行同一時刻，兩個事物均處于活動狀態例如：多CPU環境下，每個程序有各自的CPU，真正的同時執行

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

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

就緒—運行（進程調度）

運行—就緒（時間片到等）

運行—等待（服務請求，如請求I/O等）

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

start-addr：該進程的程序將從此地址開始執行。6、進程優先級priority：

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

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

4.1進程引入（順序和并發程序）4.2進程概念4.3進程控制（進程創建、撤銷、阻塞、喚醒）4.4進程之間的約束關系（同步和互斥）4.5同步機構4.6進程互斥與同步的實現4.7進程通信4.8線程（了解）4.10進程調度1024.3.1進程控制的概念進程是有生命周期的，產生、運行、暫停、終止。對進程的這些操作叫進程控制。進程控制的職責是對系統中全部進程實施有效的管理，它是處理機管理的部分（另一部分是進程調度）。進程控制進程控制包括：

進程創建、

進程撤消、

進程阻塞、

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

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

一般調用形式：susp(chan)4.3.3進程阻塞4.3.3進程阻塞

在阻塞隊列中插入了一個新的進程4.3.3進程喚醒一個正在運行的進程會因等待某事件（例如，等待打印機）的發生，由運行狀態轉換成阻塞狀態。而當它等待的事件發生后，這個進程將由阻塞狀態轉換成就緒狀態。這種轉換由進程喚醒操作完成。1294.3.3進程喚醒進程喚醒原語的形式：wakeup(chan)參數chan：進程等待的原因進程喚醒原語的功能：當進程等待的事件發生時，喚醒等待該事件的所有進程或等待該事件的首進程。4.3.3進程喚醒例如，打印機在完成了打印完成的操作后，就去檢查等待打印機的隊列，若不為空，則調用進程喚醒操作，喚醒一個（或多個）等待打印機的進程。

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

找到chan的等待隊列的指針；

for(該隊列不為空）

{從隊列中移出一個進程；設置進程狀態為“就緒”，并加入到就緒隊列；

}}4.3.3進程喚醒按此算法，是把等待在chan事件上的所有進程喚醒。也有的系統只喚醒一個等待chan事件的進程，若這樣處理，等待隊列就要按某種優先級排隊。進程喚醒操作會引起就緒隊列和等待chan事件的等待隊列發生變化。復習：進程的阻塞與喚醒

阻塞原因：請求系統服務；啟動某種操作，如I/O；新數據尚未到達；暫時無新工作可做等。當出現阻塞事件，進程調用阻塞原語將自己阻塞。并將其狀態變為“阻塞狀態”，并進入相應事件的阻塞隊列；當阻塞進程期待的事件發生，有關進程調用喚醒原語，將等待該事件的進程喚醒。并將其狀態變為“就緒狀態”，插入就緒隊列。一般,進程可以自己阻塞自己；而喚醒操作則由操作系統，或其它相關進程來完成，進程無法自己喚醒自己。

第4章進程及進程管理

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

若不加以控制，兩個進程的輸出結果可能交織在一起，很難區分。臨界資源說明例2：兩個進程共享一個變量x，設：x代表某航班機座號，p1和p2兩個售票進程，售票工作是對變量x加1。這兩個進程在一個處理機C上并發執行，兩個進程共享一個變量x時，兩種可能的執行次序：情況B為x=10+1

說明以前的課程也講到了與時間有關的錯誤，其實就是因為共享變量，這個共享的變量就是臨界資源。如果不對臨界資源加以控制，那么就可能出現錯誤，這就是本節要解決的問題。什么是臨界資源特點：當兩個進程公用一個變量時，它們必須順序地使用，一個進程對公用變量操作完畢后，另一個進程才能去訪問和修改這一變量。一次僅允許一個進程使用的資源稱為臨界資源。

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

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

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

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

和“增量(Verhogen)”

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

S代表資源的實體。在實際應用中應準確地說明s的意義和初值，每個信號燈都有一個隊列，其初始狀態為空。4.5.2P、V操作信號燈的值只能由P、V操作來改變。對信號燈的P操作記為：P(S)，P操作是一個原子操作。對信號燈的V操作記為：V(S),V操作是一個原子操作。信號量值的物理意義信號燈是整型變量。變量值≥0時，表示綠燈，進程執行。變量值<0時，表示紅燈，進程停止執行。4.5.2P、V操作P操作：s值減1；若相減結果大于等于0，則進程繼續執行；若結果小于0，則該進程掛起。注：推起該進程包括：保留調用進程CPU現場；置“等待”狀態；入等待隊列；轉進程調度；消耗掉一個資源4.5.2P、V操作V操作：s值加1；若相加結果大于0，進程繼續執行；否則，喚醒一個（或多個）等待該信號燈的進程。回收一個資源用P、V操作解決進程間互斥問題P(mutex)V(mutex)P1P2P3互斥區P(mutex)P(mutex)V(mutex)V(mutex)4.6.2用信號燈實現進程互斥例子：兩個進程共享打印機。設信號燈print表示打印機，初值為1，表示打印機可用(也可理解為有一臺打印機)。說明：print是用于互斥的信號燈，教材上設置為mutex，設置成何種符號無所謂，只要可讀性好即可。4.6.2用信號燈實現進程互斥信號量的物理意義S>0：其數值代表可用的資源數量S=0：代表無資源可用，但也沒有等待的進程，即也沒有申請資源的進程S<0：其|S|表示等待隊列中想申請資源而還沒有成功的進程數量用信號燈實現進程互斥的例子設：x代表某航班機座號，p1和p2兩個售票進程，售票工作是對變量x加1。試用信號燈的P、V操作實現這兩個進程的互斥。設：mutex為互斥信號燈，初值為1（通過pv操作，可以解決與時間有關的錯誤）五個哲學家就餐問題下面再來看一下使用互斥信號量和PV操作解決操作系統經典的五個哲學家就餐問題。有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤子，每兩人之間放一把叉子。每個哲學家思考、饑餓、然后吃通心面。為了吃面，每個哲學家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。五個哲學家就餐-動畫演示179五個哲學家就餐問題在這道題目中，每一把叉子都是必須互斥使用的，因此應為每把叉子（臨界資源）設置一個互斥信號量Si，初值均為1。#typedefintsemaphere;semaphorechopstick[5];for(inti=0;i<=4;i++)chopstick[i]=1;//因為均為互斥信號量，故初始化為1五個哲學家就餐問題當一個哲學家吃通心面前必須獲得自己左邊和右邊的兩把叉子，即執行兩個P操作，吃完通心面后必須放下叉子，即執行兩個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;思考：這樣做能保證每個哲學家都能吃到面嗎？五個哲學家就餐問題分析請大家注意，如果五個哲學家同時變得饑餓的話，且同時拿起他左邊的叉子。這樣所有的chopstick都變成0。就有可能出現每個哲學家舉起左邊的一把叉子，卻又在永遠等待相鄰哲學家手中的叉子的情況——哲學家就都會餓死。死鎖現象-永遠等待五個哲學家就餐問題分析思考：如果增加一條指令：吃不到就放下自己手中的叉子，這樣哲學家就不會餓死嗎？這樣同樣會導致哲學家會餓死，因為可能在上面的情況下，五個哲學家因為自己吃不到東西，同時放下叉子，因為大家還餓著呢，環顧一看左右都有叉子，可能又同時拿起叉子，就這樣，同時拿起，同時放下…循環往復。哲學家們不餓死，也得累死。這就是——死鎖情況。并發進程臨界區的管理原則計算機專家Dijkstra在1965年提出臨界區設計原則，即一組并發進程互斥執行時必須滿足：空閑讓進：當無進程在臨界區時，任何有權使用臨界區的進程都可進入忙則等待：不允許兩個以上的進程同時進入臨界區有限等待：任何進入臨界區的要求在有限時間內得到滿足讓權等待：處于等待狀態的進程應放棄占用CPU，以使其他進程有機會得到CPU的使用權同步的例子引例1：兩位同學約好星期天去東湖，早上8:00在校門口，不見不散。當一個同學先來到校門口，要等另一個同學，到齊后一道打的去東湖。同步的例子——病員就診187同步的概念互斥的概念來自于多個進程對獨占使用資源（設備）的競爭，同步來源于多個進程的合作。在人類社會中競爭與合作是永恒的。同步的定義：所謂同步就是并發進程在一些關鍵點上可能需要相互等待與互通消息，這樣的相互制約關系稱為進程同步。4.6.3用信號燈實現進程的同步在操作系統中，同步有各種各樣，但歸納起來有兩類：諸進程合作完成某工作的邏輯順序：如看病拿藥問題對系統資源的共享：如兩個進程共享一個（或多個）打印機，一個（或多個）變量4.6.3用信號燈實現進程的同步用信號燈及P、V操作來描述左圖1、說明進程的同步關系進程P1、P2可并發執行，P3的執行必須等待P1、P2都完成后才能開始執行。2、設置信號燈，說明含義、初值初值s13=0表示進程P1尚未執行完成；初值s23=0表示進程P2尚未執行完成；4.6.3用信號燈實現進程的同步P、V操作實現合作進程的同步練習：設pa、pb、pc為一組合作進程，其進程流圖如右圖所示，試用信號燈的p、v操作實現這三個進程的同步。解答(1)三個進程的同步關系：pa先執行，當它結束后pb、pc可以開始執行。(2)信號燈設置：設兩個同步信號燈sb、sc分別表示進程pb和pc能否開始執行，其初值均為0。解答共享緩沖區的合作進程的同步例：計算進程cp和打印進程iop公用一個單緩沖（buffer大小為1個字節），為了完成正確的計算與打印，試用信號燈的p、v操作實現這兩個進程的同步。4.6.3用信號燈實現進程的同步分析：CP進程不斷產生字符，送buffer，IOP進程從buffer中取出字符打印。如不加控制，會有多種打印結果，這取決于這兩個進程運行的相對速度。在這眾多的打印結果中，只有CP、IOP進程的運行剛好匹配的一種是對的，其它均為錯誤，并且不能重現。4.6.3用信號燈實現進程的同步要保證打印結果的正確，CP、IOP必須遵循以下同步規則，兩個進程的同步關系如下：當CP把結果送入buffer后，IOP才能從buffer中取，否則IOP必須等待；當IOP從buffer中取走數據后，CP才能將新產生數據送buffer，否則也必須等待。1974.6.3用信號燈實現進程的同步解決這個問題的步驟：分析問題，弄清楚同步關系，如上分析；設置信號燈，說明含義、初值；寫出程序描述。198用信號燈實現進程的同步信號燈設置：設置兩個信號燈sa和sb。信號燈sa--表示緩沖區中是否有可供打印的計算結果，其初值為0。信號燈sb--表示緩沖區有無空位置存放新的信息，其初值為1。用信號燈實現進程的同步信號量的小結信號量值的小結（回顧）：S>0：其數值代表可用的資源數量S=0：代表無資源可用，但也沒有等待的進程，即也沒有申請資源的進程S<0：其|S|表示等待隊列中想申請資源而還沒有成功的進程數量信號量的小結P和V的位置放置的小結：對于互斥資源：P、V操作在同一個進程中。對于共享資源的同步：P、V操作在不同進程中（強調的是你中有我，我中有你的協作關系）P和V信號量的初始化：必須置一次初值，且只能置一次初值初值必須>=0，不能為負值4.6.4多緩沖的生產者－消費者問題

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

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

empty

=2;/*盤子里最多放兩個水果*/

orange

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

apple

=0;/*盤子里沒有蘋果*/mutex=1cobegin/*可并發的進程*/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);}}

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

思考；

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

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

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

思考；

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

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

V(S);}給所有哲學家編號，奇數號的哲學家必須首先拿右邊的筷子，偶數號的哲學家則反之。235無死鎖哲學家就餐問題---解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])；}經典問題讀者寫者問題問題描述：有兩組并發進程:讀者和寫者,共享數據區要求：

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

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);};//寫者在寫數據的時候不允許其他寫者寫，也不允許其他讀者讀。讀者-寫者問題的解法動畫演示!//初始化mut