計算機操作系統(tǒng)（第3版）課件 第3章 進程

第二部分進程管理

PartTwoProcessManagement第3章進程Chapter3

Processes本章目標(biāo)：ChapterObjective介紹進程的概念Tointroducethenotionofaprocess介紹進程的特點Todescribethevariousfeaturesofprocess3.1進程的概念ProcessConcept

為了描述并發(fā)程序執(zhí)行時的特征，引入了進程。進程是資源分配的基本單位，也是獨立運行的基本單位。本書使用的名詞作業(yè)和進程基本可互換。Thetermsjobandprocessareusedalmostinterchangeablyinthistext.

前趨圖前趨圖是一個有向無循環(huán)圖，用于描述程序、程序段或語句執(zhí)行的先后次序。圖中的每個結(jié)點可以表示一條語句、一個程序段或一個進程，結(jié)點間的有向邊表示兩個結(jié)點之間存在的前趨關(guān)系“→”：→={(Pi，Pj)│Pi必須在Pj開始執(zhí)行之前完成}前趨圖中的各類結(jié)點如果(Pi，Pj)∈→，可以寫成Pi→Pj，則稱Pi是Pj的直接前趨，Pj是Pi的直接后繼。若存在一個序列Pi→Pj→…→Pk，則稱Pi是Pk的前趨。在前趨圖中，沒有前趨的結(jié)點稱為初始結(jié)點，沒有后繼的結(jié)點稱為終止結(jié)點。

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

一個程序通常由若干個程序段所組成，它們必須按照某種先后次序來執(zhí)行，僅當(dāng)前一個操作執(zhí)行完后才能執(zhí)行后繼操作，這類計算過程就是程序的順序執(zhí)行過程。例如：先輸入→再計算→最后輸出，即：I1→C1→P1→I2→C2→P2→…→In→Cn→Pn。程序順序執(zhí)行時的特征

順序性：處理機的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每一個操作必須在下一個操作開始之前結(jié)束。封閉性：程序一旦開始運行，其執(zhí)行結(jié)果不受外界因素影響。可再現(xiàn)性：只要程序執(zhí)行時的初始條件和執(zhí)行環(huán)境相同，當(dāng)程序重復(fù)執(zhí)行時，都將獲得相同的結(jié)果。程序的并發(fā)執(zhí)行及特點程序的并發(fā)執(zhí)行是指若干個程序（或程序段）同時在系統(tǒng)中運行，這些程序（或程序段）的執(zhí)行在時間上是重疊的，一個程序（或程序段）的執(zhí)行尚未結(jié)束，另一個程序（或程序段）的執(zhí)行已經(jīng)開始。程序并發(fā)執(zhí)行例進程1、2、3并發(fā)執(zhí)行。對每個進程而言，其輸入、計算和輸出這三個操作必須順序執(zhí)行。它們之間存在如下先后關(guān)系：I1先于C1和I2，C1先于P1和C2，P1先于P2I2和C1，I3、C2和P1可以并發(fā)。I1I2I3C1C3C2P1P2程序并發(fā)執(zhí)行時的特征

間斷性：并發(fā)程序具有“執(zhí)行---暫停----執(zhí)行”這種間斷性的活動規(guī)律。失去封閉性：多個程序共享系統(tǒng)中的資源，這些資源的狀態(tài)將由多個程序來改變，致使程序之間相互影響。不可再現(xiàn)性：在初始條件相同的情況下，程序的執(zhí)行結(jié)果依賴于執(zhí)行的次序。與時間有關(guān)的錯誤例程序并發(fā)執(zhí)行時可能出現(xiàn)與時間有關(guān)的錯誤。例進程1：r1=x；進程2：r2=x；r1++；r2++；x=r1；x=r2；設(shè)在兩進程運行之前，x的值為0。則兩進程運行結(jié)束后，x值可為：12程序并發(fā)執(zhí)行的條件讀集：語句執(zhí)行期間要引用的變量集合，記為R（Si）={a1，…，am}寫集：語句執(zhí)行期間要改變的變量集合，記為W（Si）={b1，…，bn}Bernstein條件Bernstein條件能保證兩個程序段并發(fā)執(zhí)行而不會產(chǎn)生與時間有關(guān)的錯誤：R（Si）∩W（Sj）={}這兩條保證R（Sj）∩W（Si）={}兩次讀之間數(shù)據(jù)不變W（Si）∩W（Sj）={}本條保證寫操作結(jié)果不丟例考慮下面是條語句：S1：a=x+yS2：b=z+1S3：c=a-bS4：d=c+1R(S1)={x,y}R(S2)={z}R(S3)={a,b}W(S1)={a}W(S2)={b}W(S3)={c}因R(S1)∩W(S2)∪R(S2)∩W(S1)∪W(S1)∩W(S2)={}，故S1和S2可以并發(fā)執(zhí)行。因R(S2)∩W(S3)∪R(S3)∩W(S2)∪W(S3)∩W(S2)={b}，故S2和S3不能并發(fā)執(zhí)行。并發(fā)語句的描述方式cobeginS1；S2；…Sn；coend對應(yīng)的前趨圖如右，其中S0和Sn+1分別是cobegin和coend語句前后的兩條語句。S0S1S2…SnSn+13.1.1進程Theprocess進程是執(zhí)行中的程序，這是一種非正式的說法。Informally,aprocessisaprograminexecution.一個進程包括：Aprocessincludes代碼段textsection程序計數(shù)器和處理機寄存器內(nèi)容programcounterandthecontentsofprocessor’sregister棧stack數(shù)據(jù)段datasection內(nèi)存中的進程

ProcessinMemory

進程的定義進程有多種定義，下面列舉一些有代表性的定義：進程是程序在處理器上的一次執(zhí)行過程。進程是可以和別的計算并行執(zhí)行的計算。進程是程序在一個數(shù)據(jù)集合上運行的過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。進程是一個具有一定功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。進程的特征動態(tài)性：進程是程序的一次執(zhí)行過程。動態(tài)性還表現(xiàn)為它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因無資源而暫停，因撤消而消亡。而程序是靜態(tài)實體。并發(fā)性：多個進程實體同時存在于內(nèi)存中，能在一段時間內(nèi)同時運行。獨立性：在傳統(tǒng)OS中，進程是獨立運行的基本單位，也是系統(tǒng)分配資源和調(diào)度的基本單位。異步性：也叫制約性，進程以各自獨立的不可預(yù)知的速度向前推進。結(jié)構(gòu)性：進程實體由程序段、數(shù)據(jù)段及進程控制塊組成，又稱為進程映像。進程與程序的關(guān)系進程是動態(tài)概念，程序是靜態(tài)概念；進程是程序在處理機上的一次執(zhí)行過程，而程序是指令的集合。進程是暫時的，程序是永久的。進程是一個狀態(tài)變化的過程；程序可以長久保存。進程與程序的組成不同。進程的組成包括程序、數(shù)據(jù)和進程控制塊。進程與程序是密切相關(guān)的。一個程序可以對應(yīng)多個進程；一個進程可以包括多個程序。進程可以創(chuàng)建新進程，而程序不能形成新程序。3.1.2進程狀態(tài)ProcessState進程執(zhí)行時會改變狀態(tài)。進程狀態(tài)包括：Asaprocessexecutes,itchangesstate.

新建：進程正被創(chuàng)建。new:Theprocessisbeingcreated.

運行：指令在執(zhí)行。running:Instructionsarebeingexecuted.

等待：進程等待某事件發(fā)生。waiting:Theprocessiswaitingforsomeeventtooccur.

就緒：進程等待分配處理器。ready:Theprocessiswaitingtobeassignedtoaprocessor.終止：進程執(zhí)行完畢。terminated:Theprocesshasfinishedexecution.

進程狀態(tài)圖DiagramofProcessState進程的基本狀態(tài)通常，一個進程至少應(yīng)有以下三種基本狀態(tài)：就緒狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)進程的基本狀態(tài)2就緒狀態(tài)：進程已獲得除處理機以外的所有資源，一旦分配了處理機就可以立即執(zhí)行。執(zhí)行狀態(tài)：又稱運行狀態(tài)。一個進程獲得必要的資源并正在處理機上執(zhí)行。阻塞狀態(tài)：又稱等待狀態(tài)、睡眠狀態(tài)。正在執(zhí)行的進程，由于發(fā)生某事件而暫時無法執(zhí)行下去（如等待輸入/輸出完成）。這時即使把處理機分配給該進程，它也無法運行。進程狀態(tài)轉(zhuǎn)換圖執(zhí)行就緒阻塞進程調(diào)度時間片用完等待事件事件發(fā)生新建狀態(tài)和終止?fàn)顟B(tài)在許多系統(tǒng)中又增加了兩種狀態(tài)：新建狀態(tài)：進程剛剛建立，但還未進入就緒隊列。又稱創(chuàng)建狀態(tài)。終止?fàn)顟B(tài)：當(dāng)一個進程正常或異常結(jié)束，操作系統(tǒng)已釋放它所占用的資源，但尚未將它撤消時的狀態(tài)，又稱退出狀態(tài)。五狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖運行就緒等待進程調(diào)度時間片用完等待事件事件發(fā)生新建終止接納完成狀態(tài)轉(zhuǎn)換的有關(guān)說明大多數(shù)狀態(tài)不可逆轉(zhuǎn)，如等待不能轉(zhuǎn)換為運行。狀態(tài)轉(zhuǎn)換大多為被動進行，但運行→等待是主動的。一個進程在一個時刻只能處于上述狀態(tài)之一。3.1.3進程控制塊

ProcessControlBlock(PCB)每個進程在操作系統(tǒng)內(nèi)用進程控制塊表示。Eachprocessisrepresengtedinoperatingsystembyaprocesscontrolblock.

PCB包含：PCBincludingthese：進程狀態(tài)Processstate程序計數(shù)器ProgramcounterCPU寄存器CPUregisters進程控制塊2

ProcessControlBlock(PCB)CPU調(diào)度信息CPUschedulinginformation內(nèi)存管理信息Memory-managementinformation計賬信息AccountinginformationI/O狀態(tài)信息I/Ostatusinformation進程控制塊(PCB)進程間CPU的切換

CPUSwitchFromProcesstoProcess進程控制塊PCB是描述和管理進程的數(shù)據(jù)結(jié)構(gòu)。它是進程實體的一部分，操作系統(tǒng)通過PCB感知進程的存在，PCB是進程存在的唯一標(biāo)志。進程的掛起狀態(tài)

在某些系統(tǒng)中，希望人為將進程掛起使之處于靜止?fàn)顟B(tài)。進程掛起的原因有：系統(tǒng)故障或功能受到破壞：先掛起，故障消除后再恢復(fù)。檢查中間結(jié)果：掛起進程以便檢查。資源不足：掛起進程以騰出資源。內(nèi)存不足：在外存掛起。有掛起狀態(tài)的進程狀態(tài)轉(zhuǎn)換圖基于上述原因，需引入一個新的狀態(tài)：掛起狀態(tài)。執(zhí)行進程調(diào)度時間片完活動就緒等待事件掛起事件發(fā)生掛起激活活動阻塞掛起就緒掛起阻塞掛起激活事件發(fā)生創(chuàng)建退出接納接納完成因果變遷？3.2進程調(diào)度-3.2.1

調(diào)度隊列

ProcessScheduling-SchedulingQueues作業(yè)隊列：系統(tǒng)中所有進程的集合Jobqueue：setofallprocessesinthesystem.就緒隊列：內(nèi)存中就緒并等待執(zhí)行的所有進程的集合。該隊列通常用鏈表實現(xiàn)。

Readyqueue：setofallprocessesresidinginmainmemory,readyandwaitingtoexecute.Thisqueueisgenerallystoredasalinkedlist.調(diào)度隊列2

SchedulingQueues設(shè)備隊列：等待某一I/O設(shè)備的進程隊列Devicequeues：setofprocesseswaitingforanI/Odevice.就緒隊列和各種I/O設(shè)備隊列

ReadyQueueAndVariousI/ODeviceQueues表示進程調(diào)度的隊列圖

Queueing-diagramrepresentationofProcessScheduling3.2.2調(diào)度程序Schedulers

長程調(diào)度（或作業(yè)調(diào)度）：選擇可以進入就緒隊列的進程Long-termscheduler(orjobscheduler)：selectswhichprocessesshouldbebroughtintothereadyqueue.短程調(diào)度（或CPU調(diào)度）：選擇可下一個執(zhí)行并分配CPU的進程Short-termscheduler(orCPUscheduler)：selectswhichprocessshouldbeexecutednextandallocatesCPU.

兩者的主要差別是執(zhí)行頻率。Theprimarydistinctionbetweenthesetwoschedulersliesinfrequencyofexecution.

調(diào)度程序續(xù)Schedulers

長程調(diào)度控制了多道程序度Thelong-termschedulercontrolsthedegreeofmultiprogramming.進程可以分為：Processescanbedescribedaseither:I/O型進程：花費I/O時間多于計算，I/O-boundprocess：spendsmoretimedoingI/Othancomputations.CPU型進程：花費更多時間用于計算CPU-boundprocess：spendsmoretimedoingcomputations.

中程調(diào)度

MediumTermScheduling有的系統(tǒng)還引入了中程調(diào)度。3.2.3上下文切換ContextSwitch將CPU切換到另一個進程需要保存當(dāng)前進程的狀態(tài)并恢復(fù)另一個進程的狀態(tài)，這一任務(wù)稱為上下文切換。switchingtheCPUtoanotherprocessrequiresperformingastatesaveofthecurrentprocessandastaterestoreofadifferentprocess.Thistaskisknownasacontextswitch.上下文切換的時間開銷較重；在切換時，系統(tǒng)沒有做有用的工作。時間取決于硬件的支持Context-switchtimeisoverhead;thesystemdoesnousefulworkwhileswitching.

Timedependentonhardwaresupport.

3.3進程操作

OperatingonProcesses進程控制的職能是對系統(tǒng)中的所有進程實施有效的管理。常見的進程控制功能有進程創(chuàng)建、撤消、阻塞與喚醒等。這些功能一般由操作系統(tǒng)內(nèi)核原語來實現(xiàn)。操作系統(tǒng)內(nèi)核在操作系統(tǒng)設(shè)計中，往往把一些與硬件緊密相關(guān)的模塊、運行頻率較高的模塊及公用的一些基本操作安排在靠近硬件的軟件層次中，使它們常駐內(nèi)存，以提高操作系統(tǒng)的運行效率，通常把這部分軟件稱為操作系統(tǒng)內(nèi)核。內(nèi)核主要包括：中斷時鐘管理進程管理存儲器管理設(shè)備管理原語原語是由若干條機器指令構(gòu)成的，用以完成特定功能的一段程序，這段程序在執(zhí)行期間不可分割。3.3.1進程創(chuàng)建

ProcessCreation通過創(chuàng)建進程系統(tǒng)調(diào)用可以創(chuàng)建多個新進程，創(chuàng)建進程稱為父進程，被創(chuàng)建進程稱為子進程。Aprocessmaycreateseveralnewprocessesviaacreate-processsystemcall,Thecreatingprocessiscalledaparentprocesses，andthenewprocessesarecalledchildren.每個新進程可以再創(chuàng)建新進程，從而形成了進程樹。Eachofthesenewprocessesmayinturncreateotherprocess，formingatreeofprocesses.進程樹又稱進程圖或進程家族樹

進程創(chuàng)建2

ProcessCreation資源共享（方式）Resourcesharing父進程子進程共享所有的資源。Parentandchildrenshareallresources.子進程共享父進程資源的子集。Childrensharesubsetofparent’sresources.父進程和子進程無資源共享。Parentandchildsharenoresources.

進程創(chuàng)建3

ProcessCreation執(zhí)行（方式）Execution父進程和子進程并發(fā)執(zhí)行。Parentandchildrenexecuteconcurrently.

父進程等待，直到子進程終止。Parentwaitsuntilchildrenterminate.

地址空間Addressspace子進程是父進程的復(fù)制品。The

childprocessisaduplicateoftheparentprocess子進程裝入一個新程序。Thechildprocesshasanewprogramloadedintoit.典型UNIX系統(tǒng)中的進程樹

ProcessesTreeonaUNIXSystem進程創(chuàng)建ProcessCreation導(dǎo)致進程創(chuàng)建的原因用戶登錄：用戶登錄后，若合法則為用戶創(chuàng)建一個進程。作業(yè)調(diào)度：為調(diào)度到的作業(yè)分配資源并創(chuàng)建進程。OS服務(wù)：創(chuàng)建服務(wù)進程。應(yīng)用需要：應(yīng)用程序根據(jù)需要創(chuàng)建子進程。創(chuàng)建原語的主要功能進程創(chuàng)建原語的功能是創(chuàng)建一個新進程，其主要操作過程如下：向系統(tǒng)申請一個空閑PCB。為新進程分配資源。如分配內(nèi)存空間。初始化新進程的PCB。在其PCB中填入進程名、家族信息、程序和數(shù)據(jù)地址、進程優(yōu)先級、資源清單及進程狀態(tài)等。將新進程的PCB插入就緒隊列。3.3.2

進程終止

ProcessTermination當(dāng)進程執(zhí)行完最后一條語句并使用系統(tǒng)調(diào)用exit()請求操作系統(tǒng)刪除自身時，進程終止。Aprocessterminateswhenitfinishesexecutingitsfinalstatementandaskstheoperatingsystemtodeleteitbyusingtheexit()systemcall.這時進程將狀態(tài)值返回給父進程，所有進程資源由操作系統(tǒng)回收。Atthatpoint,theprocessmayreturnastatusvaluetoitsparentprocess.Alltheresourcesofprocessaredeallocatedbytheoperatingsystem.進程終止2

ProcessTermination父進程終止子進程的原因有：Aparentmayterminatetheexecutionofoneofitschildrenforavarietyofreason,suchas:子進程超量使用分配的資源Childhasexceededallocatedresources.賦予子進程的任務(wù)不再需要Taskassignedtochildisnolongerrequired.

父進程退出Parentisexiting.進程終止3

ProcessTermination有些系統(tǒng)中，若父進程終止，不允許子進程繼續(xù)。Somesystem，Operatingsystemdoesnotallowchildtocontinueifitsparentterminates.這種現(xiàn)象，稱為級聯(lián)終止。Thisphenomenon，referredtoascascadingtermination.進程終止也稱為進程撤消。引起進程撤銷的原因正常結(jié)束異常結(jié)束：超時、內(nèi)存不足、地址越界、算術(shù)錯、I/O故障、非法指令等。外界干預(yù)：包括操作員或系統(tǒng)干預(yù)，父進程請求。撤消原語采用的兩種策略撤消原語采用的兩種策略：撤消指定標(biāo)識符的進程撤消指定進程及其所有子孫進程下面給出后一種撤消策略的功能描述。

撤消原語的主要功能撤消原語的功能是撤消一個進程，其主要操作過程如下：從系統(tǒng)的PCB表中找到被撤消進程的PCB。檢查被撤消進程的狀態(tài)是否為執(zhí)行狀態(tài)，若是則立即停止該進程的執(zhí)行，設(shè)置重新調(diào)度標(biāo)志。檢查被撤消進程是否有子孫進程，若有子孫進程還應(yīng)撤消該進程的子孫進程。回收該進程占有的全部資源并回收其PCB。進程阻塞與喚醒引起進程阻塞及喚醒的事件：請求系統(tǒng)服務(wù)。如請求分配打印機，但無空閑打印機則進程阻塞；當(dāng)打印機重又空閑時應(yīng)喚醒進程。啟動某種操作并等待操作完成。如啟動I/O操作，進程阻塞；I/O完成則喚醒進程。等待合作進程的協(xié)同配合。如計算進程尚未將數(shù)據(jù)送到緩沖區(qū)，則打印進程阻塞；當(dāng)緩沖區(qū)中有數(shù)據(jù)時應(yīng)喚醒進程。系統(tǒng)進程無新工作可做。如沒有信息可供發(fā)送，則發(fā)送請求阻塞；當(dāng)收到新的發(fā)送請求時，應(yīng)將阻塞進程喚醒。

阻塞原語的主要功能阻塞原語的主要功能是將進程由執(zhí)行狀態(tài)轉(zhuǎn)為阻塞狀態(tài)。其主要操作過程如下：停止當(dāng)前進程的執(zhí)行；保存該進程的CPU現(xiàn)場信息；將進程狀態(tài)改為阻塞，并插入到相應(yīng)事件的等待隊列中；轉(zhuǎn)進程調(diào)度程序，從就緒隊列中選擇一個新的進程投入運行。喚醒原語的主要功能當(dāng)進程等待的事件發(fā)生時，由發(fā)現(xiàn)者進程將其喚醒。喚醒原語的主要功能是將進程喚醒，其主要操作過程如下：將被喚醒進程從相應(yīng)的等待隊列中移出；將進程狀態(tài)改為就緒，并將該進程插入就緒隊列；轉(zhuǎn)進程調(diào)度或返回。阻塞與喚醒的關(guān)系一個進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)，是這個進程自己調(diào)用阻塞原語去完成的。進程由阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)，是另一個發(fā)現(xiàn)者進程調(diào)用喚醒原語實現(xiàn)的。一般發(fā)現(xiàn)者進程與被喚醒進程是合作的并發(fā)進程。進程的掛起與激活掛起原語和激活原語都有多種實現(xiàn)方式如：把發(fā)出掛起原語的進程自身掛起掛起具有指定標(biāo)識符的進程把某進程及其子孫進程掛起激活一個具有指定標(biāo)識名的進程激活某進程及其子孫進程下面以掛起或激活具有指定標(biāo)識符的進程為例，說明這兩種原語的主要功能。

掛起原語的主要功能

掛起原語的主要功能是將指定進程掛起，算法思想如下：到PCB表中查找該進程的PCB；檢查該進程的狀態(tài)，若為執(zhí)行則停止執(zhí)行并保護CPU現(xiàn)場信息，將該進程狀態(tài)改為掛起就緒；若為活動阻塞，則將該進程狀態(tài)改為掛起阻塞；若為活動就緒，則將該進程狀態(tài)改為掛起就緒；若進程掛起前為執(zhí)行狀態(tài)，則轉(zhuǎn)進程調(diào)度，從就緒隊列中選擇一個進程投入運行。激活原語的主要功能

激活原語的主要功能是將指定進程激活。其算法思想如下：到PCB表中查找該進程的PCB。檢查該進程的狀態(tài)。若狀態(tài)為掛起阻塞，則將該進程狀態(tài)改為活動阻塞。若狀態(tài)為掛起就緒，則將該進程狀態(tài)改為活動就緒。若進程激活后為活動就緒狀態(tài)，可能需要轉(zhuǎn)進程調(diào)度。進程的組織系統(tǒng)中有許多進程，為了能對它們進行有效的管理，應(yīng)將PCB組織起來。常用的組織方式有：線性方式鏈表方式索引方式線性方式線性方式：將PCB順序存放在一片連續(xù)內(nèi)存中。PCB1PCB2PCB3PCBnPCBn-1PCBn-2…鏈接方式鏈接方式：將同一狀態(tài)的PCB組成一個鏈表。運行指針

就緒隊列指針阻塞隊列指針PCBPCBPCBPCB^PCB^PCBPCB^索引方式索引方式：將同一狀態(tài)的進程歸入一個索引表，再由索引指向相應(yīng)的PCB運行指針

就緒表指針阻塞表指針PCB表就緒索引表阻塞索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9………3.4進程間通信

InterprocessCommunication獨立進程不能影響其他進程或被其他進程執(zhí)行所影響。

Independentprocesscannotaffectorbeaffectedbytheexecutionofanotherprocess.協(xié)作進程可能影響另一個進程的執(zhí)行或被另一個進程執(zhí)行影響

Cooperatingprocesscanaffectorbeaffectedbytheexecutionofanotherprocess進程間通信2

InterprocessCommunication進程協(xié)作的優(yōu)點Advantagesofprocesscooperation信息共享Informationsharing加速運算Computationspeed-up模塊化Modularity方便Convenience協(xié)作進程需要一種進程間通信的機制來允許進程間交換數(shù)據(jù)與信息。Cooperationprocessesrequiresaninterprocesscommunicationmechanismthatallowthemtoexchangedataandinformation.通信模型CommunicationsModelsMessagepassingSharedmemory進程通信進程通信是指進程之間的信息交換。進程互斥與同步交換的信息量較少且效率較低，因此稱這兩種進程通信方式為低級進程通信方式，相應(yīng)地也將P、V原語稱為兩條低級進程通信原語。高級進程通信方式是指進程之間以較高的效率傳送大量數(shù)據(jù)。進程通信的類型高級進程通信方式可分為三大類：共享存儲器系統(tǒng)消息傳遞系統(tǒng)管道通信系統(tǒng)或共享文件系統(tǒng)共享存儲器系統(tǒng)相互通信的進程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)。基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式：諸進程通過公用某些數(shù)據(jù)結(jié)構(gòu)交換信息。如生產(chǎn)者-消費者問題。基于共享存儲區(qū)的通信方式：在存儲器中劃出一塊共享存儲區(qū)，諸進程可通過對共享存儲區(qū)進行讀或?qū)憗韺崿F(xiàn)通信。包括建立共享存儲區(qū)、附接及斷接。消息傳遞系統(tǒng)在消息傳遞系統(tǒng)中，進程間的數(shù)據(jù)交換以消息為單位，程序員直接利用系統(tǒng)提供的一組通信命令（原語）來實現(xiàn)通信。消息傳遞系統(tǒng)因其實現(xiàn)方式不同可分為：直接通信方式：發(fā)送進程將消息發(fā)送到接收進程，并將其掛在接收進程的消息隊列上；接收進程從消息隊列上取消息。間接通信方式：發(fā)送進程將消息發(fā)送到信箱，接收進程從信箱中取消息。管道（共享文件）通信管道（共享文件）通過連接讀進程和寫進程的共享文件來實現(xiàn)讀寫進程之間通信。3.4.1共享內(nèi)存系統(tǒng)

Shared-MemorySystems協(xié)作進程的通用范例—生產(chǎn)者消費者問題CommonParadigmforcooperatingprocesses--Producer-ConsumerProblem生產(chǎn)者進程生產(chǎn)信息供消費者進程消費。可以使用兩種緩沖區(qū)：Aproducerprocessproducesinformationthatisconsumedbyaconsumerprocess.Twotypesofbufferscanbeused：無界緩沖unbounded-buffer有界緩沖bounded-buffer有界緩沖區(qū)-共享內(nèi)存解決方案

Bounded-Buffer–Shared-MemorySolution下述變量由生產(chǎn)者-消費者共享：Thefollowingvariablessharedbytheproducerandcomsumerprocesses：#defineBUFFER_SIZE10Typedefstruct{ ...}item;itembuffer[BUFFER_SIZE];intin=0;intout=0;有界緩沖區(qū)-生產(chǎn)者進程

Bounded-Buffer–ProducerProcess

Producer:itemnextProduced;while(true){

/*produceaniteminnextProduced*/; while(((in+1)%BUFFER_SIZE)==out) ;/*donothing*/ buffer[in]=nextProduced; in=(in+1)%BUFFER_SIZE; }

有界緩沖區(qū)-消費者進程

Bounded-Buffer–ConsumerProcess

Consumer:

itemnextConsumed;

while(true){while(in==out) ;/*donothing*/ nextConsumed=buffer[out]; out=(out+1)%BUFFER_SIZE;/*consumetheiteminnextConsumed*/; } InChap6wediscusshowsynchronizationamongcooperatingprocesses.3.4.2消息傳遞系統(tǒng)

Message-PassingSystem消息傳遞提供一種機制允許進程不必通過共享地址空間來實現(xiàn)進程通信和同步。Messagepassingprovidesamechanismtoallowprocessestocommunicateandtosynchronizetheiractionswithoutsharingthesameaddressspace.消息傳遞工具提供至少兩種操作Amessagepassingfacilityprovidesatleasttwooperations:send(message)receive(message)消息傳遞系統(tǒng)2

Message-PassingSystem若P與Q要通信，需要:

IfPandQwishtocommunicate,theyneedto:建立通信連接establishacommunicationlinkbetweenthem通過send/receive交換消息exchangemessagesviasend/receive消息傳遞系統(tǒng)3

Message-PassingSystem實現(xiàn)鏈接和發(fā)送/接收操作的幾種方法：

severalmethodforimplementingalinkandthesend/receiveoperation:直接或間接的通信Directorindirectcommunication同步或異步通信Synchronousorasynchronouscommunication

自動或顯式的緩沖Automaticorexplicitbuffering1.命名

Naming直接通信需要通信的進程明確地命名通信的接收者及發(fā)送者。Underdirectcommunication，eachprocessthatwantstocommunicatemustexplicitlynametherecipientorsenderofthecommunication.

send(P,message)：向進程P發(fā)消息

sendamessagetoprocessP

receive(Q,message)：接收來自進程Q的消息receiveamessagefromprocessQ

消息緩沖通信及其數(shù)據(jù)結(jié)構(gòu)消息緩沖通信是直接通信方式的一種實現(xiàn)。所謂消息是指一組信息，消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)如下：structmessage{sender;發(fā)送者進程標(biāo)識符

size;消息長度

text;消息正文

next;指向下一個消息緩沖區(qū)的指針}在PCB中還應(yīng)增加structPCB{┇mq;消息隊列隊首指針

mutex;消息隊列互斥信號量

sm;消息隊列資源信號量┇}

消息緩沖通信的實現(xiàn)思想為了實現(xiàn)消息通信，發(fā)送進程應(yīng)先在自己的工作區(qū)中設(shè)置一個發(fā)送區(qū)，把欲發(fā)送的消息填入其中，然后再用發(fā)送原語將其發(fā)送出去。接收進程調(diào)用接收原語從自己的消息緩沖隊列中摘下第一個消息，并將其內(nèi)容復(fù)制到自己的消息接收區(qū)內(nèi)。send（B，a）;

┇sender：Asize：6text：Hello！兩個進程進行通信的過程進程APCB（B）進程Breceive（b）

┇sender：Asize：6text:Hello！┇

mqmutexsmsender：Asize：6text:Hello！next：0ab第一個消息緩沖區(qū)發(fā)送原語描述voidsend（receiver，a）receiver為接收者標(biāo)識號，a為發(fā)送區(qū)首址{

向系統(tǒng)申請一個消息緩沖區(qū)i；

將發(fā)送區(qū)a中的消息復(fù)制到i中；獲得接收進程的內(nèi)部標(biāo)識j;P（mutex）；

把消息插入j的消息隊列上；

V（mutex）；V（sm）；}接收原語描述voidreceive（b）b為接收區(qū)首址{

獲得接收進程內(nèi)部標(biāo)識j;P（sm）；P（mutex）；

將消息隊列中的第一個消息移出；

V（mutex）；

將消息復(fù)制到接收區(qū)b；}間接通信

IndirectCommunication在間接通信中，通過郵箱或端口發(fā)送或接收消息。

Withindirectcommunication，themessagesaresendtoandreceivedfrommailboxesorports.原語send()和receive()定義如下：Thesend()andreceive()primitivesaredefinedasfollows:send(A,message)：sendamessagetomailboxAreceive(A,message)：receiveamessagefrommailboxA間接通信2IndirectCommunication操作系統(tǒng)必須提供機制：Operatingsystemmustprovideamechanism創(chuàng)建新的信箱createanewmailbox通過信箱發(fā)送和接收消息sendandreceivemessagesthroughmailbox刪除信箱deleteamailbox信箱通信信箱通信方式中，進程之間通信需要通過共享數(shù)據(jù)結(jié)構(gòu)實體--信箱來進行。信箱是一種數(shù)據(jù)結(jié)構(gòu)，其中存放信件。信箱邏輯上分成信箱頭和信箱體兩部分。信箱頭中存放有關(guān)信箱的描述。信箱體由若干格子組成，每格存放一個信件，格子的數(shù)目和大小在創(chuàng)建信箱時確定。

信箱通信原語信箱通信原語包括：信箱的創(chuàng)建和撤消：消息的發(fā)送和接收：Send(mailbox,message);Receive(mailbox,message);2.同步Synchronization消息傳遞可以是阻塞或非阻塞。也稱為同步或異步Messagepassingmaybeeitherblockingornon-blocking—allknownassynchronousandasynchronous阻塞發(fā)送Blockingsend非阻塞發(fā)送Nonblockingsend阻塞接收Blockingreceive非阻塞接收Nonblockingreceive同步2Synchronization進程間的消息通信存在同步關(guān)系對于發(fā)送進程來說，它在執(zhí)行發(fā)送原語后有兩種可能選擇：發(fā)送進程阻塞，直到這個消息被接收進程接收到，這種發(fā)送稱為阻塞發(fā)送。發(fā)送進程不阻塞，繼續(xù)執(zhí)行，這種發(fā)送稱為非阻塞發(fā)送。同步3Synchronization對于一個接收進程來說，在執(zhí)行接收原語后也有兩種可能選擇：如果一個消息在接收原語執(zhí)行之前已經(jīng)發(fā)送，則該消息被接收進程接收，接收進程繼續(xù)執(zhí)行。如果沒有正在等待的消息，則該進程阻塞直到有消息到達；或者該進程繼續(xù)執(zhí)行，放棄接收的努力。前者稱為阻塞接收，后者稱為非阻塞接收。同步4Synchronization根據(jù)發(fā)送進程和接收進程采取方式的不同，通常有三種常用的組合方式：非阻塞發(fā)送、阻塞接收。非阻塞發(fā)送、非阻塞接收。阻塞發(fā)送，阻塞接收。3.緩沖Buffering通信進程交換的消息都駐留在臨時隊列中，隊列實現(xiàn)有三種方式messagesexchangedbycommunicatingprocessesresideinatemporaryqueue;implementedinoneofthreeways.零容量：0個消息。發(fā)送者必須等待接收者Zerocapacity：0messages.Sendermustwaitforreceiver

有限容量：有限的n個消息；如線路滿則發(fā)送者必須等待。Boundedcapacity–finitelengthofnmessages.Sendermustwaitiflinkfull.無限容量：無限長度；發(fā)送者不等待Unboundedcapacity–infinitelength.Senderneverwaits.管道使用管道通信時，基本上采用文件系統(tǒng)的原有機制實現(xiàn)。包括創(chuàng)建、打開、關(guān)閉、讀寫等。管道機制應(yīng)提供以下三方面的協(xié)調(diào)能力：互斥：諸進程互斥讀寫管道同步：管道空、滿情況處理存在：確定對方是否存在管道通信示意圖1初始時，其長度為4，系統(tǒng)將管道看成一個循環(huán)隊列。按先進先出的方式讀寫。inoutABCD寫入字符E后，管道長度為5inoutABCDE管道通信示意圖2讀一個字符后，管道長度為4inoutBCDE若管道容量為n且in=n時，再寫入一個字符，則in移到管道的另一端。inoutDE

…X習(xí)題習(xí)題33.1UsingtheprogramshowninFigure3.30,explainwhattheoutputwillbeatLINEA.習(xí)題3.2Includingtheinitialparentprocess,howmanyprocessesarecreatedbytheprogramshowninFigure3.31?選擇題1對進程的管理和控制使用_____。A.指令

B.信號量C.原語

D.信箱分配到必要的資源并獲得處理機時的進程狀態(tài)是_____。A.就緒狀態(tài)