1第二章進程的描述與控制2.1前趨圖和程序執行2.2進程的描述2.3進程控制2.4進程同步2.5

經典的進程同步問題2.6進程通信2.7

線程的基本概念2.8線程的實現2本章前言在傳統的操作系統中，為了提高資源利用率和系統吞吐量，通常采用多道程序技術，將多個程序同時裝入內存，并使之并發運行，傳統意義上的程序不再能獨立運行。此時，作為資源分配和獨立運行的基本單位都是進程。操作系統所具有的四大特征也都是基于進程而形成的，并從進程的角度對操作系統進行研究。可見，在操作系統中，進程是一個極其重要的概念。因此，本章專門對進程進行詳細闡述。32.1前趨圖和程序執行2.1.1前趨圖前趨圖(PrecedenceGraph)是一個有向無循環圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執行的前后關系。圖中的每個結點可用于表示一個程序或程序段，乃至一條語句；結點間的有向邊則用于表示兩個結點之間存在的偏序(PartialOrder，亦稱偏序關系)或前趨關系(PrecedenceRelation)“→”。4→={(Pi，Pj)|PimustcompletebeforePjmaystart}，如果(Pi，Pj)∈→，可寫成Pi→Pj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結點稱為初始結點(InitialNode)，把沒有后繼的結點稱為終止結點(FinalNode)。此外，每個結點還具有一個重量(Weight)，用于表示該結點所含有的程序量或程序的執行時間。5圖

2-1前趨圖

6對于圖2-1(a)所示的前趨圖，存在下述前趨關系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9或表示為：P={P1，P2，P3，P4，P5，P6，P7，P8，P9}→={(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P4，P7)，(P5，P8)，(P6，P8)，(P7，P9)，(P8，P9)}應當注意，前趨圖中不允許存在循環（循環意味著不可實現的前趨關系），在圖2-1(b)中就有著下述不可實現的前趨關系：S2→S3，S3→S27嘗試畫出下述四條語句的前趨圖：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b四條語句的前趨關系

82.1.2程序的順序執行及其特征1.程序的順序執行含義：前趨程序段未完成時，后繼程序段不能開始，如：在進行計算任務時，必須先輸入用戶的程序和數據，然后進行計算，最后才能打印計算結果。若用I代表輸入操作，C代表計算操作，P為打印操作，則三個程序段的執行順序如圖2-2(a)中。對一個程序段中的多條語句來說，也有一個執行順序問題，例如對于下述三條語句的程序段應按圖2-2(b)所示的順序執行:S1:a=x+y;S2:b=a-5;S3:c=b+1;圖

2-2

程序順序執行的前趨圖

92.程序順序執行時的特征(1)順序性。處理機的操作嚴格按照程序所規定的順序執行，即每一操作必須在上一個操作結束之后開始。(2)封閉性(獨占)。程序是在封閉的環境下執行的，即程序運行時獨占全機資源，資源的狀態(除初始狀態外)只有本程序才能改變它。程序一旦開始執行，其執行結果不受外界因素影響。(3)可再現性。只要程序執行時的環境和初始條件相同，當程序重復執行時，不論它是從頭到尾不停頓地執行，還是“停停走走”地執行，都將獲得相同的結果。102.1.3程序的并發執行及其特征1．程序的并發執行含義：為增強計算機系統的處理能力和提高資源利用率而采取的一種“同時”操作技術。在圖2-2中的輸入程序、計算程序和打印程序三者之間，存在著Ii→Ci→Pi這樣的前趨關系，以至對同一個作業的輸入、計算和打印三個操作，必須順序執行，但并不存在Pi→Ii+1的關系，因而在對一批程序進行處理時，可使它們并發執行。一般來說，輸入程序在輸入第i+1個程序時，計算程序可能正在對第i個程序進行計算，而打印程序正在打印第i-1個程序的計算結果。類似于指令流水線（取指、譯碼、取數、執行），在某一時刻，Pi-1，Ci，Ii+1并發執行。11圖2-3并發執行時的前趨圖

時間軸12看一個例子有一個公有變量i，其初值為1，現有兩個程序：程序1程序2①i++;③i=0;②printf(“%d”,i);④printf(“%d”,--i);如果讓程序1和程序2并發執行，在OS不施加并發規則的情況下，屏幕上的顯示結果可能是哪些？①→②→③→④，顯示結果為：2,-1①→③→②→④，顯示結果為：0,-1①→③→④→②，顯示結果為：-1,-1。。。思考：這個例子說明了什么問題？132．程序并發執行時的特征1)間斷性程序在并發執行時，由于它們共享系統資源，以及為完成同一項任務而相互合作，致使在這些并發執行的程序之間形成了相互制約的關系。相互制約將導致并發程序具有“執行-暫停-執行”這種間斷性的活動規律。2)失去封閉性程序在并發執行時，是多個程序共享系統中的各種資源，因而這些資源的狀態將由多個程序來改變，致使程序的運行失去了封閉性。這樣，某程序在執行時，必然會受到其它程序的影響。143)不可再現性(危害)程序在并發執行時，由于失去了封閉性，也將導致其再失去可再現性。例如，前面兩個程序對于公有變量i的并發執行的結果。程序在并發執行時，由于失去了封閉性，程序經過多次執行后，雖然它們執行時的環境和初始條件相同，但得到的結果卻各不相同。153.程序并發執行的條件（Bernstein）Bernstein定理：保證并發時的可再現性。定義R(Pi)={a1,a2,…,am}，a1~am是程序Pi將讀取的變量的集合(讀集)定義W(Pi)={b1,b2,…,bn}，b1~bn是程序Pi將寫入的變量的集合(寫集)如：R(c=a-b;)={a,b}W(c=a-b;)={c}若兩個程序P1和P2能滿足下述條件，則允許并發執行且結果可再現：Bernstein條件：R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)=φ16例：四條語句：S1:a=x+y;S2:b=z+1;S3:c=a–b;S4:d=c+1;右表各情況能否并發？R(S1)={x,y}W(S1)={a}R(S2)={z}W(S2)={b}R(S3)={a,b}W(S3)={c}R(S4)={c}W(S4)=yhdqydiS1S2S3S4S1S2S3S4S1S2S3S4S1/√×√S2/×√S3/×S4/172.2進程的描述2.2.1進程的定義和特征1.進程的定義出于程序并發執行的不封閉性和不可再現性，加上程序本身是靜態和順序的，故用程序作為描述其執行過程以及共享資源的基本單位是不合適的。進程是什么(Process)？可以并行執行的計算部分。一個獨立的可以調度的活動。一個抽象實體，當它執行某個任務時，將要分配和釋放各種資源。行為的規則叫程序，程序在處理機上執行時的活動稱為進程。一個具有獨立功能的程序對某個數據集在處理機上的動態執行過程和分配資源的基本單位。一個程序在給定活動空間和初始環境下，在一個處理機上的執行過程。182.進程的特征1)結構性特征一個進程由3部分組成：Code、Data、PCB，亦即程序段、數據段、進程控制塊，總稱為進程實體或進程映像，簡稱為進程2)動態性特征由創建而產生、由調度而執行、由撤銷而消亡。3)并發性特征多進程并發。4)獨立性特征進程獨立參與運行、調度、分配、回收。5)異步性特征走走停停，完成順序與開始順序無關。19現在我們再來討論進程的定義。進程是程序的一次執行。進程是一個程序及其數據在處理機上順序執行時所發生的活動。進程是具有獨立功能的程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立單位。本書給出的進程定義：進程是程序實體的運行過程，是系統進行資源分配和調度的一個獨立單位。推薦定義一個具有獨立功能的程序對某個數據集在處理機上的動態執行過程和分配資源的基本單位。20進程與程序的關系與區別進程是動態而暫時的，程序是靜態而永久的。(如何理解？)進程具有并發特征，而程序沒有。不同的進程可以基于同一程序來創建，只是對應的數據集不同。(舉例說明？)某進程在執行過程中可調用多個程序（創建多個子進程）。進程有一定的生命期，而程序是指令的集合，本身無“運動”的含義。沒有建立進程的程序不能作為一個獨立任務單位得到操作系統的認可。進程包括程序代碼、數據和進程控制塊。212.2.2進程的基本狀態及轉換1.進程的三種基本狀態1)就緒(Ready)狀態進程萬事俱備(所有目前所需資源均已申請到手)，只欠CPU。所有的就緒進程組成了就緒隊列。2)執行(Running)狀態進程已獲得CPU并正在執行。在單處理機系統中，任一時刻至多有一個進程處于執行狀態；在多處理機系統中，則可能有多個進程同時處于執行狀態。3)阻塞(Blocked)狀態進程因發生某事件而暫停執行的狀態，也稱為等待/封鎖狀態。某事件：如請求I/O，申請緩存空間失敗，等待設備資源等…所有的阻塞進程組成了阻塞隊列。(也可按阻塞原因構成多個阻塞隊列)就緒：有獲得CPU的愿望執行：已經獲得CPU阻塞：無獲得CPU的愿望結束22圖2-5進程的三種基本狀態及其轉換

創建接納就緒執行進程調度進程中斷(如時間片完)終止阻塞I/O請求或等待某事件(阻塞)I/O完成或該事件發生(喚醒)2.進程三種基本狀態的轉換23回顧進程的三種基本狀態之間的遷移就緒→執行進程被調度，獲得CPU。執行→阻塞請求資源未被滿足或開始I/O操作，讓出CPU。執行→就緒中斷發生（如時間片完或有搶占式任務到達），讓出CPU。阻塞→就緒請求的資源已被滿足或結束I/O操作，等待CPU。243．創建狀態和終止狀態1)創建狀態創建一個進程一般要通過兩個步驟：首先，為一個新進程創建PCB，并填寫必要的控制和管理信息；其次，為該進程分配其初期運行所必需的資源（比如內存）；最后，進程狀態便可由創建狀態轉入就緒狀態并插入就緒隊列之中。當一個新進程被創建時，系統已為其分配了PCB，填寫了進程標識等信息，但由于該進程所必需的資源（如主存資源）尚未分配。雖然此時的進程已擁有了自己的PCB，但進程自身還未進入主存，即創建工作尚未完成，進程還不能被調度運行，此時所處的狀態就是創建狀態。252)終止狀態進程的終止也要通過兩個步驟：首先等待操作系統進行善后處理，然后將其PCB清零，并將PCB空間返還給系統。當一個進程到達了自然結束點，或是出現了無法克服的錯誤，或是被操作系統所終結，或是被其他有終止權的進程所終結，它將進入終止狀態。進入終止態的進程以后不能再執行，但在操作系統中依然保留一個記錄，其中保存狀態碼和一些計時統計數據，供其它進程收集。一旦其它進程完成了對終止狀態進程的信息提取之后，操作系統將刪除該進程。圖2-6示出了增加了創建狀態和終止狀態后，進程的三種基本狀態衍變為五種狀態。26圖2-6進程的五種基本狀態及轉換

272.2.3.掛起(Suspend)操作和進程狀態的轉換引入：操作系統的掛起：STR(SuspendToRAM)技術/STD(SuspendToDisk)技術STR意為“掛起到內存”，是一種瞬間開機技術。具體地說，是把數據和系統運行狀態信息保存到內存中，然后整機斷電，進入STR后，主板仍然會提供3.3V的電壓給內存條供電，用來維持內存里的信息，其它設備(包括風扇)則一律斷電，以達到了節電的目的。當下次開機(指開啟機箱上的電源開關)的時候，電腦將跳過POST(加電自檢)等過程，可不通過復雜的OS系統檢測，而從內存中讀取相應數據直接使系統進入掛起前的狀態。一般從啟動到進入Windows不會超過10秒鐘。實現STR的條件：ATX電源、BIOS和芯片組支持STR、支持ACPI的操作系統（Windows2000、XP、2003、VISTA…）。STR在Windows中的實現：睡眠（待機）功能。STD意為“掛起到硬盤”，原理雷同。在Windows中的實現：休眠功能（Shift+待機）。281.引入掛起狀態的原因終端用戶的請求。父進程請求。負荷調節的需要。操作系統的需要。對換的需要。…與掛起（Suspend）操作對應的操作是激活（Active）292.引入掛起后進程狀態的轉換在引入掛起狀態后，又將增加從掛起狀態(又稱為靜止狀態)到非掛起狀態(又稱為活動狀態)的相互轉換。(1)活動就緒→靜止就緒。當進程處于未被掛起的就緒狀態時，稱此為活動就緒狀態，表示為Readya。當用掛起原語Suspend將該進程掛起后，該進程便轉變為靜止就緒狀態，表示為Readys，處于Readys狀態的進程不再被調度執行。(2)活動阻塞→靜止阻塞。當進程處于未被掛起的阻塞狀態時，稱它是處于活動阻塞狀態，表示為Blockeda。當用Suspend原語將它掛起后，進程便轉變為靜止阻塞狀態，表示為Blockeds。處于該狀態的進程在其所期待的事件出現后，將從靜止阻塞變為靜止就緒。(3)靜止就緒→活動就緒。處于靜止就緒狀態的進程，若用激活原語Active激活后，該進程將轉變為活動就緒狀態。(4)靜止阻塞→活動阻塞。處于靜止阻塞狀態的進程，若用激活原語Active激活后，該進程將轉變為活動阻塞狀態。30圖

2-7具有掛起狀態的進程狀態圖

接納I/O完成或該事件發生(喚醒)活動就緒執行進程調度進程中斷(如時間片完)靜止阻塞活動阻塞I/O請求或等待某事件(阻塞)I/O完成或該事件發生(喚醒)掛起激活靜止就緒掛起掛起激活創建終止延遲創建結束31圖2-8具有創建、終止和掛起狀態的進程狀態圖

322.2.4

進程管理中的數據結構1．操作系統中用于管理控制的數據結構操作系統為每個資源設置了資源信息表，為每個進程設置了進程信息表，并分類鏈接為不同的隊列，以便于操作系統進行管理圖2-9操作系統控制表的一般結構332．進程控制塊的作用進程控制塊PCB(ProcessControlBlock)PCB包含了該進程全部的描述信息、控制信息以及資源信息，是進程動態特征的集中反映，PCB是進程存在的唯一標志，OS完全通過PCB來感知進程的存在，同時完全依據PCB來對該進程進行并發的控制和管理，PCB需要常駐內存，所有進程的PCB構成了內存中的PCB鏈表/隊列。34例如，當OS要調度某進程執行時，要從該進程的PCB中查出其現行狀態及優先級；在調度到某進程后，要根據其PCB中所保存的處理機狀態信息來設置該進程恢復運行的現場，并根據PCB中的程序和數據的內存始址，找到其程序和數據；進程在執行過程中，當需要和與之合作的進程實現同步、通信或訪問文件時，也都需要訪問PCB；當進程由于某種原因而暫停執行時，又須將其斷點的處理機環境保存在PCB中。35PCB的具體作用（1）作為獨立運行基本單位的標志創建進程時為其建立PCB，終止進程時回收其PCB（2）能實現間斷性運行方式中斷或阻塞時用于保存CPU現場信息，以供下次調度運行時恢復（3）提供進程管理所需要的信息記錄程序或數據的地址、該進程所需資源清單等（4）提供進程調度所需要的信息記錄進程當前狀態、優先級、各類時間信息等（5）實現與其它進程的同步與通信記錄同步信號量、通信緩沖區等363．進程控制塊中的信息1)進程標識符：進程標識符用于惟一地標識一個進程。一個進程通常有兩種標識符：①內部標識符(整數形式)；②外部標識符(單詞形式)。2)處理機狀態（CPU上下文）①通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問的，用于暫存信息；②指令計數器，其中存放了要訪問的下一條指令的地址；③程序狀態字PSW，其中含有狀態信息，如條件碼、執行方式、中斷屏蔽標志等；④用戶棧指針，指每個用戶進程都有一個或若干個與之相關的系統棧，用于存放過程和系統調用參數及調用地址。373)進程調度信息①進程當前狀態；②進程優先級；③進程調度所需的其它信息，它們與所采用的進程調度算法有關，比如，進程已等待CPU的時間總和、進程已執行的時間總和等；④事件，即阻塞原因。4)進程控制信息①程序和數據的地址，指進程的程序和數據所在的內存或外存地(首)址，以便再調度到該進程執行時，能從PCB中找到其程序和數據；②進程同步和通信機制，指實現進程同步和進程通信時必需的機制，如消息隊列指針、信號量等；③資源清單，即一張列出了除CPU以外的、進程所需的全部資源及已經分配到該進程的資源的清單；④鏈接指針，它給出了本進程(PCB)所在隊列中的下一個進程的PCB的首地址。384.進程控制塊的組織方式1)線性方式將系統中所有PCB組織在一張線性表中。實現簡單、開銷小，適合進程數目不多的系統。PCB1PCB2PCB3…PCBn圖2-10PCB線性表示意圖392)鏈接方式這是把具有同一狀態的PCB，用其中的鏈接字鏈接成一個隊列。這樣，可以形成就緒隊列、若干個阻塞隊列和空白隊列等。對其中的就緒隊列常按進程優先級的高低排列，把優先級高的進程的PCB排在隊列前面。此外，也可根據阻塞原因的不同而把處于阻塞狀態的進程的PCB排成等待I/O操作完成的隊列和等待分配內存的隊列等。圖2-11示出了一種鏈接隊列的組織方式。40圖2-11

PCB鏈接隊列示意圖0413)索引方式系統根據所有進程的狀態建立幾張索引表。例如，就緒索引表、阻塞索引表等，并把各索引表在內存的首地址記錄在內存的一些專用單元中。在每個索引表的表目中，記錄具有相應狀態的某個PCB在PCB表中的地址。這種方式適合于進程數量很多的情況。圖2-12示出了索引方式的PCB組織。42圖

2-12按索引方式組織PCB432.3

進程控制進程控制是進程管理中最基本的功能。它用于創建(Create)一個新進程，終止(Terminate)一個已完成的進程，還負責進程運行中的狀態轉換：如當一個正在執行的進程因等待某事件而暫時不能繼續執行時，將其阻塞(Block)到阻塞隊列，而當該進程所期待的事件出現時，又將該進程喚醒(Wakeup)到就緒隊列，另外還有掛起(Suspend)和激活(Active)操作。進程控制一般是由OS的內核中的原語來實現的。44原語(Primitive)：是操作系統定義好的，由若干條指令組成的，在系統態下執行的，具備特定功能的一個原子性程序。它與一般過程的區別在于：原語是“原子操作(ActionOperation)”，其中所有動作要么全做，要么全不做。換言之，原語是一個不可分割的基本單位，因此在執行過程中不允許被中斷或并發。原語常駐內存。原語的三大特點：系統態（管態）下執行；不允許被中斷；不允許并發執行。原語分類：進程控制原語、進程同步原語、進程通信原語等。452.3.1

操作系統內核OS內核：是指操作系統中一些與硬件緊密相關的模塊（如中斷處理程序）、設備驅動程序、運行頻率較高的模塊等，常駐內存。處理機的執行狀態：系統態（又叫管態或內核態）：高特權，能執行一切指令，訪問所有寄存器和存儲區。主要負責OS內核運行。用戶態（目態）：低特權，僅能執行規定的指令，訪問指定的寄存器和存儲區。主要負責應用程序運行。OS內核的兩大功能：支撐功能：如中斷處理、時鐘管理、原語操作。資源管理功能：如進程管理、存儲器管理、設備管理。462.3.2進程的創建1．進程的層次結構OS允許一個進程去創建另一個進程。這樣，由若干級父進程、子進程構成了層次結構。子進程可以繼承父進程所擁有的資源。2.進程圖(ProcessGraph)進程圖是用于描述一個進程的家族關系的有向樹，如圖2-13所示。圖中的結點(圓圈)代表進程。在進程A創建了進程B之后，稱A是B的父進程(ParentProcess)，B是A的子進程(ProgenyProcess)。47圖2-13進程樹

483．引起創建進程的事件(1)用戶登錄(由系統內核模塊負責創建)。(2)作業調度(由系統內核模塊負責創建)。(3)提供服務(由系統內核模塊負責創建)。(4)應用請求(由父進程負責創建)。494．進程的創建(CreationofProcess)一旦操作系統發現了上述要求創建新進程的事件后，便調用進程創建原語Create()按下述步驟創建一個新進程。有有50入口查PCB鏈表有空PCB？無取空表PCB(i)并初始化分配資源否PCB(i)入就緒隊列PCB(i)入進程家族或進程鏈返回創建失敗等待進程內外標識、處理機狀態、優先級、地址、資源清單等內存、文件、設備等512.3.3進程的終止1．引起進程終止的事件1)正常結束：如Halt，Logoff等2)異常結束(1)越界錯誤。(2)保護錯。(3)非法指令。(4)特權指令錯。(5)運行超時。(6)等待超時。(7)算術運算錯。(8)I/O故障。3)外界干預(1)人工干預（如taskkill）。(2)父進程請求。(3)父進程終止。522．進程的終止過程如果系統中發生了上述要求終止進程的某事件，OS便調用進程終止原語Terminate()，按下述過程去終止指定的進程。53入口查進程鏈表或進程家族有此PCB？無有該進程正執行？終止執行并轉進程調度是否釋放該進程所占有的資源并歸還給父進程或系統釋放該PCB結構并移出進程鏈表或進程家族返回出錯處理該進程有子進程？有處理子進程的終止無542.3.4進程的阻塞（Block）與喚醒（Wakeup）1.引起進程阻塞和喚醒的事件1)請求系統服務或資源而得不到滿足時。2)啟動某種操作(典型如I/O操作)。3)受合作方進程影響(如生產者進程和消費者進程)。4)無新工作可做。552．進程阻塞過程執行狀態→阻塞狀態，是一種自主行為。入口停止當前進程的執行并將CPU現場保存到該進程PCB置該進程PCB狀態為阻塞該進程PCB入阻塞隊列轉進程調度返回56在搶占式OS中，可能引發進程調度3．進程喚醒過程阻塞狀態→就緒狀態，是一種被動行為。入口從阻塞隊列中摘下被喚醒進程的PCB置該進程PCB狀態為就緒該進程PCB入就緒隊列視情況決定是否進程調度返回57應當指出，Block原語和Wakeup原語是一對作用剛好相反的原語，必須成對使用。即：如果進程A調用了阻塞原語將自己阻塞，則必須在與之相合作的另一進程或其他相關的進程中安排喚醒原語，方能在此后某個時間喚醒阻塞進程A；否則，已阻塞進程A將會因不能被喚醒而永遠地處于阻塞狀態，從而再無機會繼續運行。582.3.5進程的掛起（Suspend）與激活（Active）1．進程的掛起過程：內存→外存入口該進程PCB狀態為執行？是置PCB為靜止就緒并轉進程調度否該進程PCB狀態為活動阻塞？否是置PCB為靜止阻塞置PCB為靜止就緒進程換至外存返回592．進程的激活過程：外存→內存入口該進程PCB狀態為靜止阻塞？否置PCB為活動就緒是置PCB為活動阻塞返回進程換入內存搶占式OS？是處理進程調度否602.4

進程同步2.4.1進程同步的基本概念1．生產者-消費者問題：生產者-消費者(producer-consumer)問題是一個著名的進程同步問題。它描述的是：有一群生產者進程在生產產品，并將這些產品提供給消費者進程去消費。為使生產者進程與消費者進程能并發執行，在兩者之間設置了一個具有n個緩沖區的緩沖池，生產者進程將它所生產的產品放入一個緩沖區中；消費者進程可從一個緩沖區中取走產品去消費。盡管所有的生產者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即不允許消費者進程到一個空緩沖區去取產品，也不允許生產者進程向一個已裝滿產品的緩沖區中投放產品。同步：對多個并發進程在執行次序上的協調，以達到有效的資源共享和相互合作，使程序執行具有可再現性。61數據結構定義：(假定產品的數據類型為Item)#definen20intin=0,out=0,counter=0;Itembuffer[n],nextp,nextc;數據結構說明：n：緩沖區大小常量。in：下一個產品的存放位置，初值為0，范圍0~n-1，操作為in=(in+1)%n。out：下一個產品的消費位置，初值為0，范圍0~n-1，操作為out=(out+1)%n。counter：當前緩沖區中的產品總數量，初值為0，范圍0~n。生產者執行counter++，消費者執行counter--。nextp：由生產者生產出的產品在放入緩沖區之前的暫存地。nextc：由消費者從緩沖區中取走的產品在消費掉之前的暫存地。Producer→→Consumer共享緩沖區(長度為n)0123…n-2n-1消費指針out↑↑生產指針in

→指針的移動方向62/*生產者程序*/voidProducer(void){

生產一個產品并暫存到nextp;while(counter==n){printf(“庫房已滿，等待！”);}buffer[in]=nextp;in=(in+1)%n;counter++;}/*消費者程序*/voidConsumer(void){while(counter==0){printf(“庫房已空，等待！”);}nextc=buffer[out];out=(out+1)%n;counter--;

將nextc中暫存的產品消費掉;}兩個程序共享counter變量，生產者進行counter++，消費者進行counter--，假定counter當前值為1，現在生產和消費各一次，按理說結束后counter的值應該仍為1。但事實上…63在這里r1和r2為寄存器，生產者借助寄存器r1完成counter++操作，消費者借助寄存器r2完成counter--操作。假設counter的初值為1，現在讓生產者進程和消費者進程并發執行：①②③④⑤⑥：結果為1④⑤⑥①②③：結果為1①②④⑤③⑥：結果為0①②④⑤⑥③：結果為2上述結果說明：程序的執行失去了可再現性。結論：counter屬于臨界資源，應互斥訪問。生產者加1①r1=counter;②r1++;③counter=r1;消費者減1④

r2=counter;⑤r2--;⑥counter=r2;642．相關概念臨界資源——在一段時間內只允許一個進程訪問的資源，如打印機、磁帶機、公有變量、緩沖區等，即獨占資源。臨界區——每個并發進程中訪問臨界資源的程序段，即不允許多個并發進程交叉執行的一段程序。進程間接制約——由于共享某一公有資源而引起的在臨界區內不允許并發進程交叉執行的現象。對應于進程間的互斥。比如打印機正被進程A使用，若進程B此時提出申請打印機則必阻塞，此時A和B之間就形成了間接制約關系。再如前面生產者進程和消費者進程之間因counter形成間接制約。進程直接制約——一組在異步環境下的并發合作進程，各自的執行結果互為對方的執行條件，從而限制各進程執行速度的過程。對應于進程間的同步。比如當緩沖區空時，生產者進程直接制約了消費者進程。而當緩沖區滿時，消費者進程直接制約了生產者進程。65互斥訪問——不允許兩個或以上的共享某一臨界資源的并發進程同時進入各自的臨界區。饑餓——某進程長期無法申請到所需資源的現象。死鎖——一組并發進程中的每個成員彼此互相等待對方所擁有的資源，且在得到對方的資源之前不會釋放自己已擁有的資源，從而導致各并發進程無法繼續推進的狀態。典型如哲學家進餐問題。663．臨界區(criticalsection)若能保證競爭同一臨界資源的各并發進程互斥地進入自己的臨界區，便可實現諸進程對該臨界資源的互斥訪問。為此，每個進程在進入自己的臨界區之前，應先對欲訪問的臨界資源的狀態進行檢查，看它是否正被訪問。如果此刻該臨界資源未被訪問，進程便可進入臨界區對該資源進行訪問，并設置它正被訪問的標志；如果此刻該臨界資源正被另一某進程訪問，則該進程不能進入臨界區。因此，必須在臨界區前面增加一段用于進行上述檢查的代碼，把這段代碼稱為進入區(entrysection)。相應地，在臨界區后面也要加上一段稱為退出區(exitsection)的代碼，用于將臨界資源正被訪問的標志恢復為未被訪問的標志。67進程A…進入區代碼臨界區A退出區代碼…進程B…進入區代碼臨界區B退出區代碼…檢查能否進入臨界區，若能則進入并為臨界資源加鎖進程A對臨界資源的訪問進程B對臨界資源的訪問退出時為臨界資源解鎖在現實生活中能找到很多類似臨界區訪問的例子。注意：對于競爭不同臨界資源的臨界區不需要互斥訪問。684．同步機制應遵循的規則(1)空閑讓進只要臨界資源空閑就應該允許進程進入自己的臨界區。(2)忙則等待只要臨界資源不空閑就應該禁止進程進入自己的臨界區。(3)有限等待進程在有限時間內有機會進入自己的臨界區(避免“死等”)。(4)讓權等待正處于執行狀態的進程若進不了臨界區就應主動讓出CPU并阻塞自己(避免“忙等”)。692.4.2

硬件同步機制（略）關中斷利用Test-and-Set指令實現進程互斥利用Swap指令實現進程互斥702.4.3信號量機制信號量(Semaphore)：OS中管理公有資源的有效手段，用來代表可用資源實體的數量。整型信號量記錄型信號量AND型信號量一般信號量集711．整型信號量最初由Dijkstra把整型信號量定義為一個用于表示資源數目的整型量S，它與一般整型量不同，除初始化外，僅能通過兩個標準的原子操作wait(S)和signal(S)來訪問。很長時間以來，這兩個操作一直被分別稱為P、V操作。Wait(S)和signal(S)操作可描述為：由于wait(S)和signal(S)是兩個原子操作，因此，它們在執行時是不可中斷的。這樣，當S<=0時，wait(S)會不斷占用CPU進行測試。所以整型信號量的致命缺點是：不符合“讓權等待”，即出現“忙等”現象。Wait(S)while(S<=0){;}S--;Signal(S)S++;722．記錄型信號量(1)每個信號量S除了有一個整型信號量S.Value之外，還有一個進程阻塞隊列S.L，其中記錄因該信號量而阻塞的各進程的標識，即：structSemaphore{intValue;/*該資源的當前可用數量*/Process_QueueL;/*因該資源而阻塞的進程隊列*/}S;73(2)Wait(S)和Signal(S)操作Block(S.L)：進程將自己阻塞并進入阻塞隊列S.L。Wakeup(S.L)：從阻塞隊列S.L中喚醒首個進程并放入就緒隊列。Wait(S)S.Value--;if(S.Value<0)Block(S.L);Signal(S)S.Value++;if(S.Value<=0)Wakeup(S.L);74在記錄型信號量機制中，S.value的初值表示系統中某類資源的數目，因而又稱為資源信號量。對它的每次wait操作，意味著進程請求一個單位的該類資源，使系統中可供分配的該類資源數減少一個，因此描述為S.value--；當S.value<0時，表示該類資源已分配完畢，因此進程應調用block原語，進行自我阻塞，放棄處理機，并插入到信號量鏈表S.L中。可見，該機制遵循了“讓權等待”準則。此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數目。對信號量的每次signal操作，表示執行進程釋放一個單位資源，使系統中可供分配的該類資源數增加一個，故S.value++操作表示資源數目加1。若加1后仍是S.value≤0，則表示在該信號量鏈表中，仍有等待該資源的進程正在阻塞，故還應調用wakeup原語，將S.L鏈表中的第一個阻塞進程喚醒。75假設S.Value當前值為n，則n在不同的值范圍代表著不同的含義：

>0：本資源當前空閑可用數目為n個。

=0：無可用資源也無等待該資源的進程。

<0：還需該資源的數目，即當前因該資源而阻塞的進程數為|n|個。例：設資源信號量S.Value初值為1，請按下面的進程表寫出從10:00之前到10:30之后S.Value值的變化過程？

時間進程申請歸還A10:0010:10B10:0510:20C10:0610:25D10:1510:30記錄型信號量：1→0→-1→-2→-1→-2→-1→0→1思考：如果是整型信號量呢？n76(3)利用信號量實現互斥訪問若S.value的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量用于進程互斥，即初值為1的信號量稱為互斥信號量。對應地，初值不為1的信號量稱為資源信號量。為臨界資源設置一個互斥信號量mutex，其初值為1，將每個進程的臨界區代碼置于wait和signal之間：注意：①必須成對使用Wait(mutex)和Signal(mutex)且次序不能顛倒；②遺漏Wait將違反互斥訪問原則，使得多個進程同時活躍在臨界區，導致系統混亂；③遺漏Signal將導致其它競爭該臨界資源的進程餓死(整型)或睡死(記錄型)，即其它進程永遠無法再進入臨界區執行或永遠不會被喚醒。每個需訪問該臨界資源的進程的互斥算法…Wait(mutex);本進程的臨界區代碼Signal(mutex);…773．AND型信號量例：現有進程A和B，兩者都要訪問臨界資源S1和S2，

已知S1和S2信號量初值均為1。下列訪問算法有問題嗎？若按①②③④或③④①②的順序并發，不會出問題。若按①③②④、①③④②、③①②④、③①④②中的任何一種順序并發，結果將導致死鎖！解決方法：某進程所需的資源，要么全給，要么一個都不給。這就是AND型信號量的實現思想。進程A①Wait(S1);②Wait(S2);

臨界區代碼A;Signal(S2);Signal(S1);進程B③Wait(S2);④Wait(S1);

臨界區代碼B;Signal(S1);Signal(S2);78SWait(S1….Sn)和SSignal(S1…Sn)操作SWait實際上是將多條連續的Wait原語封裝為一條更大的原語，SWait比Wait更安全，但效率稍低。SWait(S1,S2,…,Sn)if(S1>=1&&S2>=1&&…&&Sn>=1){for(i=1;i<=n;i++)Si--;}else{調用該進程進入第一個小于1的信號量Si的阻塞隊列Si.L，并將進程的程序計數器恢復到Swait開始處;}SSignal(S1,S2,…,Sn)for(i=1;i<=n;i++){Si++;

喚醒因Si而阻塞的所有進程并送入就緒隊列;}794．信號量集在記錄型信號量機制中，wait(S)或signal(S)操作僅能對同一信號量施以加1或減1操作，意味著每次只能獲得或釋放一個單位的臨界資源。而當一次需要N個某類臨界資源時，便要進行N次wait(S)操作，顯然這是低效并且容易導致死鎖的。此外，在有些情況下，當資源數量低于某一下限值時，便不予以分配。因而，在每次分配之前，都必須測試該資源的數量，看其是否大于其下限值。基于上述兩點，可以對AND信號量機制加以擴充，形成一般化的“信號量集”機制。Swait操作可描述如下，其中S為信號量，d為需求值，而t為下限值。80(1)Swait(S，d，d)。此時在信號量集中只有一個信號量S，但允許它每次申請d個資源，當現有資源數少于d時，不予分配。(2)Swait(S，1，1)。此時的信號量集已蛻化為一般的資源信號量(S>1時)或互斥信號量(S=1時)。(3)Swait(S，1，0)。相當于一個可控開關：當S設置為≥1時，允許多個進程進入某特定區；當S設置為0后，將阻止任何進程進入特定區。SWait(S1,t1,d1;…;Sn,tn,dn)if(S1>=t1&&S2>=t2&&…&&Sn>=tn){for(i=1;i<=n;i++)Si=Si-di;}else{調用該進程進入第一個小于ti的信號量Si的阻塞隊列Si.L，并將進程的程序計數器恢復到Swait開始處;}SSignal(S1,d1;…;Sn,dn)for(i=1;i<=n;i++){Si=Si+di;

喚醒因Si而阻塞的所有進程并送入就緒隊列;}812.4.4信號量的應用1．利用信號量實現進程互斥為使多個進程能互斥地訪問某臨界資源，只須為該資源設置一個互斥信號量mutex，并設其初始值為1，然后將各進程訪問該資源的臨界區置于wait(mutex)和signal(mutex)操作之間即可。這樣，每個欲訪問該臨界資源的進程在進入臨界區之前，都要先對mutex執行wait操作，若該資源此刻未被訪問，本次wait操作必然成功，進程便可進入自己的臨界區，這時若再有其他進程也欲進入自己的臨界區，此時由于對mutex執行wait操作定會失敗，因而該進程阻塞，從而保證了該臨界資源能被互斥地訪問。當訪問臨界資源的進程退出臨界區后，又應對mutex執行signal操作，以便釋放該臨界資源。利用信號量實現進程互斥的進程可描述如下：每個需訪問該臨界資源的進程的互斥算法…Wait(mutex);本進程的臨界區代碼Signal(mutex);…82例：小王和小張是同一個寢室的同學，該寢室只有一個衛生間，請分別寫出小王和小張互斥使用衛生間的步驟。答：設該寢室衛生間的信號量為S，其初值為1小王

Wait(S);

小王使用衛生間的過程;Signal(S);小張

Wait(S);

小張使用衛生間的過程;Signal(S);如果該寢室有兩個衛生間呢？832．利用信號量實現前趨關系還可利用信號量來描述程序或語句之間的前趨關系。設有兩個并發執行的進程P1和P2。P1中有語句S1；P2中有語句S2。我們希望在S1執行后再執行S2。為實現這種前趨關系，我們只須使進程P1和P2共享一個公用信號量S，并賦予其初值為0，將signal(S)操作放在語句S1后面；而在S2語句前面插入wait(S)操作，即：在進程P1中，用：S1；signal(S)；在進程P2中，用：wait(S)；S2；84例：圖2-14示出了一個前趨圖，其中S1，S2，S3，…，S6是最簡單的程序段(只有一條語句)。為使各程序段能正確執行，應設置若干個初始值為“0”的信號量。如為保證S1→S2，S1→S3的前趨關系，應分別設置信號量a和b，同樣，為了保證S2→S4，S2→S5，S3→S6，S4→S6和S5→S6，應設置信號量c，d，e，f，g。85Semaphorea=0,b=0,c=0,d=0,e=0,f=0,g=0;S1;Signal(a);Signal(b);Wait(a);S2;Signal(c);Signal(d);Wait(b);S3;Signal(g);Wait(c);S4;Signal(e);Wait(d);S5;Signal(f);Wait(e);Wait(f);Wait(g);S6;圖2-14前趨圖舉例

abcdefg862.4.5管程機制(自學內容)1．管程的定義系統中的各種硬件資源和軟件資源，均可用數據結構抽象地描述其資源特性，即用少量信息和對該資源所執行的操作來表征該資源，而忽略了它們的內部結構和實現細節。例如，對一臺電傳機，可用與分配該資源有關的狀態信息(busy或free)和對它執行請求與釋放的操作，以及等待該資源的進程隊列來描述。又如，一個FIFO隊列，可用其隊長、隊首和隊尾以及在該隊列上執行的一組操作來描述。87利用共享數據結構抽象地表示系統中的共享資源，而把對該共享數據結構實施的操作定義為一組過程，如資源的請求和釋放過程request和release。進程對共享資源的申請、釋放和其它操作，都是通過這組過程對共享數據結構的操作來實現的，這組過程還可以根據資源的情況，或接受或阻塞進程的訪問，確保每次僅有一個進程使用共享資源，這樣就可以統一管理對共享資源的所有訪問，實現進程互斥。88代表共享資源的數據結構，以及由對該共享數據結構實施操作的一組過程所組成的資源管理程序，共同構成了一個操作系統的資源管理模塊，我們稱之為管程。管程被請求和釋放資源的進程所調用。Hansan為管程所下的定義是：“一個管程定義了一個數據結構和能為并發進程所執行(在該數據結構上)的一組操作，這組操作能同步進程和改變管程中的數據”。由上述的定義可知，管程由四部分組成：①管程的名稱；②局部于管程內部的共享數據結構說明；③對該數據結構進行操作的一組過程；④對局部于管程內部的共享數據設置初始值的語句。圖2-15是一個管程的示意圖。89圖2-15管程的示意圖90管程的語法描述如下：

typemonitor_name=MONITOR；<共享變量說明>；define<(能被其他模塊引用的)過程名列表>；use<(要調用的本模塊外定義的)過程名列表>；procedure<過程名>(<形式參數表>)；begin

…end;…91function<函數名>(<形式參數表>)：值類型；begin

…end；

…begin<管程的局部數據初始化語句序列>；end92需要指出的是，局部于管程內部的數據結構，僅能被局部于管程內部的過程所訪問，任何管程外的過程都不能訪問它；反之，局部于管程內部的過程也僅能訪問管程內的數據結構。由此可見，管程相當于圍墻，它把共享變量和對它進行操作的若干過程圍了起來，所有進程要訪問臨界資源時，都必須經過管程(相當于通過圍墻的門)才能進入，而管程每次只準許一個進程進入管程，從而實現了進程互斥。93管程是一種程序設計語言結構成分，它和信號量有同等的表達能力，從語言的角度看，管程主要有以下特性：(1)模塊化。管程是一個基本程序單位，可以單獨編譯。(2)抽象數據類型。管程中不僅有數據，而且有對數據的操作。(3)信息掩蔽。管程中的數據結構只能被管程中的過程訪問，這些過程也是在管程內部定義的，供管程外的進程調用，而管程中的數據結構以及過程(函數)的具體實現外部不可見。94管程和進程不同，主要體現在以下幾個方面：(1)雖然二者都定義了數據結構，但進程定義的是私有數據結構PCB，管程定義的是公共數據結構，如消息隊列等；(2)二者都存在對各自數據結構上的操作，但進程是由順序程序執行有關的操作，而管程主要是進行同步操作和初始化操作；(3)設置進程的目的在于實現系統的并發性，而管程的設置則是解決共享資源的互斥使用問題；(4)進程通過調用管程中的過程對共享數據結構實行操作，該過程就如通常的子程序一樣被調用，因而管程為被動工作方式，進程則為主動工作方式；(5)進程之間能并發執行，而管程則不能與其調用者并發；(6)進程具有動態性，由“創建”而誕生，由“撤銷”而消亡，而管程則是操作系統中的一個資源管理模塊，供進程調用。952．條件變量在利用管程實現進程同步時，必須設置同步工具，如兩個同步操作原語wait和signal。當某進程通過管程請求獲得臨界資源而未能滿足時，管程便調用wait原語使該進程等待，并將其排在等待隊列上，如圖2-15所示。僅當另一進程訪問完成并釋放該資源之后，管程才又調用signal原語，喚醒等待隊列中的隊首進程。96在利用管程實現進程同步時，必須設置同步工具，如兩個同步操作原語wait和signal。當某進程通過管程請求獲得臨界資源而未能滿足時，管程便調用wait原語使該進程等待，并將其排在等待隊列上，如圖2-15所示。僅當另一進程訪問完成并釋放該資源之后，管程才又調用signal原語，喚醒等待隊列中的隊首進程。97但是僅僅有上述的同步工具是不夠的。考慮一種情況：當一個進程調用了管程，在管程中時被阻塞或掛起，直到阻塞或掛起的原因解除，而在此期間，如果該進程不釋放管程，則其它進程無法進入管程，被迫長時間地等待。為了解決這個問題，引入了條件變量condition。通常，一個進程被阻塞或掛起的條件(原因)可有多個，因此在管程中設置了多個條件變量，對這些條件變量的訪問，只能在管程中進行。98管程中對每個條件變量都須予以說明，其形式為：Varx，y：condition。對條件變量的操作僅僅是wait和signal，因此條件變量也是一種抽象數據類型，每個條件變量保存了一個鏈表，用于記錄因該條件變量而阻塞的所有進程，同時提供的兩個操作即可表示為x.wait和x.signal，其含義為：①x.wait：正在調用管程的進程因x條件需要被阻塞或掛起，則調用x.wait將自己插入到x條件的等待隊列上，并釋放管程，直到x條件變化。此時其它進程可以使用該管程。②x.signal：正在調用管程的進程發現x條件發生了變化，則調用x.signal，重新啟動一個因x條件而阻塞或掛起的進程。如果存在多個這樣的進程，則選擇其中的一個，如果沒有，則繼續執行原進程，而不產生任何結果。這與信號量機制中的signal操作不同，因為后者總是要執行s=s+1操作，因而總會改變信號量的狀態。99如果有進程Q因x條件處于阻塞狀態，當正在調用管程的進程P執行了x.signal操作后，進程Q被重新啟動，此時兩個進程P和Q，如何確定哪個執行，哪個等待，可采用下述兩種方式之一進行處理：(1)P等待，直至Q離開管程或等待另一條件。(2)Q等待，直至P離開管程或等待另一條件。采用哪種處理方式，當然是各執一詞。Hoare采用了第一種處理方式，而Hansan選擇了兩者的折衷，他規定管程中的過程所執行的signal操作是過程體的最后一個操作，于是，進程P執行signal操作后立即退出管程，因而進程Q馬上被恢復執行。1002.5經典的進程同步問題2.5.1生產者—消費者問題1．利用記錄型信號量解決生產者—消費者問題假定在生產者和消費者之間的公用緩沖池（即庫房）中，具有n個緩沖區，這時可利用互斥信號量mutex實現諸進程對緩沖池的互斥使用。利用信號量empty和full分別表示緩沖池中空緩沖區和滿緩沖區的數量。又假定這些生產者和消費者相互等效，只要緩沖池未滿，生產者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產者—消費者的數據結構可描述如下:/*生產者-消費者數據結構*/Semaphoremutex=1,empty=n,full=0;Itembuffer[n],nextp,nextc;intin=0,out=0;/*buffer[n]：長度為n的緩沖區(0~n-1)，用于存放Item類型的產品。in：下一個產品的存放位置,初值為0,范圍0~n-1,操作為in=(in+1)%n。out：下一個產品的消費位置,初值為0,范圍0~n-1,操作為out=(out+1)%n。nextp：由生產者生產出的產品在放入緩沖區之前的暫存地。nextc：由消費者從緩沖區取走的產品在消費掉之前的暫存地。mutex：互斥信號量，用于實現互斥訪問緩沖區buffer，初值為1。empty和full：資源信號量，分別代表當前緩沖區的空位數(初值為n)和滿位數(初值為0)。*/思考：empty和full的值有何關系？能否只定義其中一個？答：empty和full的值相加恒等于n。但由于信號量不允許直接參與算術運算，故兩者都要定義。101說明：用于互斥的Wait(mutex)和Signal(mutex)必須在同一程序中配對出現。Wait(empty)和Signal(empty)在不同程序中出現，同理，Wait(full)和Signal(full)在不同程序中出現。Wait(mutex)必須出現在Wait(empty)或Wait(full)之后，否則可能導致死鎖。(一般原則，先Wait資源信號量再Wait互斥信號量)同一個程序中的Signal的順序可以調換。/*生產者程序*/voidProducer(void){

生產一個產品并暫存到nextp;Wait(empty);Wait(mutex);buffer[in]=nextp;in=(in+1)%n;Signal(mutex);Signal(full);}/*消費者程序*/voidConsumer(void){Wait(full);Wait(mutex);nextc=buffer[out];out=(out+1)%n;Signal(mutex);Signal(empty);

將nextc中暫存的產品消費掉;}1022．利用AND信號量解決生產者-消費者問題對于生產者—消費者問題，也可利用AND信號量來解決，即用Swait(empty，mutex)來代替wait(empty)和wait(mutex)；用Ssignal(mutex，full)來代替signal(mutex)和signal(full)；用Swait(full，mutex)來代替wait(full)和wait(mutex)，以及用Ssignal(mutex，empty)代替Signal(mutex)和Signal(empty)。利用AND信號量來解決生產者—消費者問題的算法描述如下：103/*生產者程序*/voidProducer(void){

生產一個產品并暫存到nextp;Wait(empty);Wait(mutex);buffer[in]=nextp;in=(in+1)%n;Signal(mutex);Signal(full);}/*消費者程序*/voidConsumer(void){Wait(full);Wait(mutex);nextc=buffer[out];out=(out+1)%n;Signal(mutex);Signal(empty);

將nextc中暫存的產品消費掉;}Swait(empty,mutex);Ssignal(mutex,full);Swait(full,mutex);Ssignal(mutex,empty);1043．利用管程解決生產者—消費者問題(自學)

在利用管程方法來解決生產者—消費者問題時，首先便是為它們建立一個管程，并命名為ProclucerConsumer，或簡稱為PC。其中包括兩個過程：(1)put(item)過程。生產者利用該過程將自己生產的產品投放到緩沖池中，并用整型變量count來表示在緩沖池中已有的產品數目，當count≥n時，表示緩沖池已滿，生產者須等待。(2)get(item)過程。消費者利用該過程從緩沖池中取出一個產品，當count≤0時，表示緩沖池中已無可取用的產品，消費者應等待。105PC管程可描述如下：

typeproducer-consumer=monitor

Varin,out,count:integer；

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

notfull，notempty:condition；

procedureentryput(item)

begin

ifcount>=nthennotfull.wait；

buffer(in):=nextp；

in:=(in+1)modn；

count:=count+1；

ifnotempty.queuethennotempty.signal；

endprocedureentryget(item)

begin

ifcount<=0thennotempty.wait；

nextc:=buffer(out)；

out:=(out+1)modn；

count:=count-1；

ifnotfull.quenethennotfull.signal；

end

beginin:=out:=0；

count:=0end106在利用管程解決生產者—消費者問題時，其中的生產者和消費者可描述為：

producer:begin

repeat

produceaniteminnextp；

PC.put(item)；

untilfalse；

end

consumer:begin

repeat

PC.get(item)；

consumetheiteminnextc；

untilfalse；

end1072.5.2哲學家進餐問題由Dijkstra提出并解決的哲學家進餐問題是典型的同步問題。該問題是描述有五個哲學家共用一張圓桌，分別坐在周圍的五張椅子上，在圓桌上有五個碗和五只筷子，他們的生活方式是交替地進行思考和進餐。平時，一個哲學家進行思考，饑餓時便試圖取用其左右最靠近他的筷子，只有在他拿到兩只筷子時才能進餐。進餐完畢后放下筷子繼續思考。圓桌1081．利用記錄型信號量解決哲學家進餐問題經分析可知，放在桌子上的筷子是臨界資源，在一段時間內只允許一位哲學家使用。為了實現對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構成信號量數組。其描述如下：Semaphorechopstick[5]={1,1,1,1,1};用記錄型信號量實現的哲學家i的進餐方案(0≤i≤4)Wait(chopstick[i]);/*先嘗試拿左手邊的筷子*/Wait(chopstick[(i+1)%5]);/*再嘗試拿右手邊的筷子*/開始進餐…Signal(chopstick[i]);/*歸還左手邊的筷子*/Signal(chopstick[(i+1)%5]);/*歸還右手邊的筷子*/繼續思考…請思考這樣的方案安全嗎？如果每個哲學家都同時拿到左手邊的筷子，那么誰也無法得到右手邊的筷子。最終所有人餓死！109上述方案的解決方法(1)至多允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐(如何實現？)。(2)僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐(如何實現？)。(3)規定奇數號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子，而偶數號哲學家則相反。按此規定，將是1、2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即五位哲學家都先競爭奇數號筷子，獲得后，再去競爭偶數號筷子，最后總會有一位哲學家能獲得兩只筷子而