進程的描述與控制

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

經(jīng)典的進程同步問題2.6進程通信2.7

線程的基本概念2.8線程的實現(xiàn)2本章前言在傳統(tǒng)的操作系統(tǒng)中，為了提高資源利用率和系統(tǒng)吞吐量，通常采用多道程序技術，將多個程序同時裝入內(nèi)存，并使之并發(fā)運行，傳統(tǒng)意義上的程序不再能獨立運行。此時，作為資源分配和獨立運行的基本單位都是進程。操作系統(tǒng)所具有的四大特征也都是基于進程而形成的，并從進程的角度對操作系統(tǒng)進行研究?？梢?，在操作系統(tǒng)中，進程是一個極其重要的概念。因此，本章專門對進程進行詳細闡述。32.1前趨圖和程序執(zhí)行2.1.1前趨圖前趨圖(PrecedenceGraph)是一個有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執(zhí)行的前后關系。圖中的每個結點可用于表示一個程序或程序段，乃至一條語句；結點間的有向邊則用于表示兩個結點之間存在的偏序(PartialOrder，亦稱偏序關系)或前趨關系(PrecedenceRelation)“→”。4→={(Pi，Pj)|PimustcompletebeforePjmaystart}，如果(Pi，Pj)∈→，可寫成Pi→Pj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結點稱為初始結點(InitialNode)，把沒有后繼的結點稱為終止結點(FinalNode)。此外，每個結點還具有一個重量(Weight)，用于表示該結點所含有的程序量或程序的執(zhí)行時間。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)}應當注意，前趨圖中不允許存在循環(huán)（循環(huán)意味著不可實現(xiàn)的前趨關系），在圖2-1(b)中就有著下述不可實現(xiàn)的前趨關系：S2→S3，S3→S27嘗試畫出下述四條語句的前趨圖：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b四條語句的前趨關系

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

2-2

程序順序執(zhí)行的前趨圖

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

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

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

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

2-7具有掛起狀態(tài)的進程狀態(tài)圖

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

322.2.4

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

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

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

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

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

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

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

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

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

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

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

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

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

<0：還需該資源的數(shù)目，即當前因該資源而阻塞的進程數(shù)為|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)利用信號量實現(xiàn)互斥訪問若S.value的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量用于進程互斥，即初值為1的信號量稱為互斥信號量。對應地，初值不為1的信號量稱為資源信號量。為臨界資源設置一個互斥信號量mutex，其初值為1，將每個進程的臨界區(qū)代碼置于wait和signal之間：注意：①必須成對使用Wait(mutex)和Signal(mutex)且次序不能顛倒；②遺漏Wait將違反互斥訪問原則，使得多個進程同時活躍在臨界區(qū)，導致系統(tǒng)混亂；③遺漏Signal將導致其它競爭該臨界資源的進程餓死(整型)或睡死(記錄型)，即其它進程永遠無法再進入臨界區(qū)執(zhí)行或永遠不會被喚醒。每個需訪問該臨界資源的進程的互斥算法…Wait(mutex);本進程的臨界區(qū)代碼Signal(mutex);…773．AND型信號量例：現(xiàn)有進程A和B，兩者都要訪問臨界資源S1和S2，

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

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

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

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

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

Wait(S);

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

Wait(S);

小張使用衛(wèi)生間的過程;Signal(S);如果該寢室有兩個衛(wèi)生間呢？832．利用信號量實現(xiàn)前趨關系還可利用信號量來描述程序或語句之間的前趨關系。設有兩個并發(fā)執(zhí)行的進程P1和P2。P1中有語句S1；P2中有語句S2。我們希望在S1執(zhí)行后再執(zhí)行S2。為實現(xiàn)這種前趨關系，我們只須使進程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是最簡單的程序段(只有一條語句)。為使各程序段能正確執(zhí)行，應設置若干個初始值為“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管程機制(自學內(nèi)容)1．管程的定義系統(tǒng)中的各種硬件資源和軟件資源，均可用數(shù)據(jù)結構抽象地描述其資源特性，即用少量信息和對該資源所執(zhí)行的操作來表征該資源，而忽略了它們的內(nèi)部結構和實現(xiàn)細節(jié)。例如，對一臺電傳機，可用與分配該資源有關的狀態(tài)信息(busy或free)和對它執(zhí)行請求與釋放的操作，以及等待該資源的進程隊列來描述。又如，一個FIFO隊列，可用其隊長、隊首和隊尾以及在該隊列上執(zhí)行的一組操作來描述。87利用共享數(shù)據(jù)結構抽象地表示系統(tǒng)中的共享資源，而把對該共享數(shù)據(jù)結構實施的操作定義為一組過程，如資源的請求和釋放過程request和release。進程對共享資源的申請、釋放和其它操作，都是通過這組過程對共享數(shù)據(jù)結構的操作來實現(xiàn)的，這組過程還可以根據(jù)資源的情況，或接受或阻塞進程的訪問，確保每次僅有一個進程使用共享資源，這樣就可以統(tǒng)一管理對共享資源的所有訪問，實現(xiàn)進程互斥。88代表共享資源的數(shù)據(jù)結構，以及由對該共享數(shù)據(jù)結構實施操作的一組過程所組成的資源管理程序，共同構成了一個操作系統(tǒng)的資源管理模塊，我們稱之為管程。管程被請求和釋放資源的進程所調(diào)用。Hansan為管程所下的定義是：“一個管程定義了一個數(shù)據(jù)結構和能為并發(fā)進程所執(zhí)行(在該數(shù)據(jù)結構上)的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)”。由上述的定義可知，管程由四部分組成：①管程的名稱；②局部于管程內(nèi)部的共享數(shù)據(jù)結構說明；③對該數(shù)據(jù)結構進行操作的一組過程；④對局部于管程內(nèi)部的共享數(shù)據(jù)設置初始值的語句。圖2-15是一個管程的示意圖。89圖2-15管程的示意圖90管程的語法描述如下：

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

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

…end；

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

生產(chǎn)一個產(chǎn)品并暫存到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中暫存的產(chǎn)品消費掉;}1022．利用AND信號量解決生產(chǎn)者-消費者問題對于生產(chǎn)者—消費者問題，也可利用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信號量來解決生產(chǎn)者—消費者問題的算法描述如下：103/*生產(chǎn)者程序*/voidProducer(void){

生產(chǎn)一個產(chǎn)品并暫存到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中暫存的產(chǎn)品消費掉;}Swait(empty,mutex);Ssignal(mutex,full);Swait(full,mutex);Ssignal(mutex,empty);1043．利用管程解決生產(chǎn)者—消費者問題(自學)

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

producer:begin

repeat

produceaniteminnextp；

PC.put(item)；

untilfalse；

end

consumer:begin

repeat

PC.get(item)；

consumetheiteminnextc；

untilfalse；

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