進(jìn)程的描述與控制

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

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

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

2-1前趨圖

6對(duì)于圖2-1(a)所示的前趨圖，存在下述前趨關(guān)系：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)}應(yīng)當(dāng)注意，前趨圖中不允許存在循環(huán)（循環(huán)意味著不可實(shí)現(xiàn)的前趨關(guān)系），在圖2-1(b)中就有著下述不可實(shí)現(xiàn)的前趨關(guān)系：S2→S3，S3→S27嘗試畫(huà)出下述四條語(yǔ)句的前趨圖：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b四條語(yǔ)句的前趨關(guān)系

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

2-2

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

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

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

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

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

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

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

322.2.4

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

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

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

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

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

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

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

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

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

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

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

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

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

=0：無(wú)可用資源也無(wú)等待該資源的進(jìn)程。

<0：還需該資源的數(shù)目，即當(dāng)前因該資源而阻塞的進(jìn)程數(shù)為|n|個(gè)。例：設(shè)資源信號(hào)量S.Value初值為1，請(qǐng)按下面的進(jìn)程表寫(xiě)出從10:00之前到10:30之后S.Value值的變化過(guò)程？

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

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

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

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

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

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

Wait(S);

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

Wait(S);

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

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

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

…end；

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

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

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

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

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

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

producer:begin

repeat

produceaniteminnextp；

PC.put(item)；

untilfalse；

end

consumer:begin

repeat

PC.get(item)；

consumetheiteminnextc；

untilfalse；

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