第2章 進(jìn)程管理

第2章進(jìn)程管理王之倉青海師范大學(xué)2.12.32.22.42.52.6進(jìn)程的基本概念目錄進(jìn)程控制進(jìn)程同步管程機(jī)制線程進(jìn)程互斥2.72.8經(jīng)典同步問題進(jìn)程通信010203進(jìn)程特征、進(jìn)程控制進(jìn)程互斥與同步進(jìn)程通信、管程機(jī)制、線程要點(diǎn)學(xué)要123456理解進(jìn)程的特征及狀態(tài)變化了解進(jìn)程控制塊的構(gòu)成與作用掌握信號量機(jī)制及其應(yīng)用掌握生產(chǎn)者－消費(fèi)者問題理解管程的基本概念了解消息傳遞的直接方法與間接方法習(xí)求7了解微內(nèi)核OS結(jié)構(gòu)的基本特點(diǎn)運(yùn)行程序還是運(yùn)行進(jìn)程？在傳統(tǒng)的操作系統(tǒng)中，程序不能獨(dú)立運(yùn)行，作為資源分配和獨(dú)立運(yùn)行的單位是進(jìn)程。操作系統(tǒng)所具有的四大特征也都是基于進(jìn)程而形成的，并可從進(jìn)程的觀點(diǎn)來研究操作系統(tǒng)。顯然，在操作系統(tǒng)中，進(jìn)程是一個極其重要的概念。本章任務(wù)本章專門來描述進(jìn)程。通過本章的學(xué)習(xí)，學(xué)習(xí)者可以明確進(jìn)程為什么存在，什么是進(jìn)程，進(jìn)程有哪些狀態(tài)，如何控制進(jìn)程，進(jìn)程互斥，進(jìn)程同步以及幾個典型的進(jìn)程同步問題。同時，還會知道在現(xiàn)代操作系統(tǒng)中獨(dú)立調(diào)度、獨(dú)立運(yùn)行的最小單位是線程(Thread)，而不是進(jìn)程(Process)。2.1進(jìn)程的基本概念

在早期的操作系統(tǒng)中，程序采用絕對裝入方式(見第5章5.1節(jié))，內(nèi)存采用單一連續(xù)分配方式(見第5章5.2節(jié))。在這個時期，每個正在運(yùn)行的程序占用了系統(tǒng)所有資源，只有一個程序運(yùn)行完畢后才考慮運(yùn)行下一個程序。也就是，程序的執(zhí)行是順序執(zhí)行，即必須在一個程序執(zhí)行完成后，才允許另一個程序執(zhí)行。2.1進(jìn)程的基本概念隨著支持多任務(wù)系統(tǒng)的固定分區(qū)內(nèi)存分配技術(shù)(見第5章5.2節(jié))的出現(xiàn)，系統(tǒng)允許多個程序并發(fā)執(zhí)行。程序的這兩種運(yùn)行方式間有著顯著不同。也正是程序并發(fā)執(zhí)行時的特征，才在操作系統(tǒng)中引入進(jìn)程的概念。2.1進(jìn)程的基本概念1.程序的順序執(zhí)行程序是一個在時間上按嚴(yán)格次序前后相繼的操作序列，是一個靜態(tài)的概念。一個具有獨(dú)立功能的程序獨(dú)占處理機(jī)直至得到最終結(jié)果的過程稱為程序的順序執(zhí)行。一個完整的程序應(yīng)該包括輸入、計(jì)算和輸出3個部分。圖2-1所示為程序順序執(zhí)行的過程。圖中程序1和程序2分別包括I1、I2，C1、C2和P1、P2模塊。只有程序1執(zhí)行完畢后程序2才得以執(zhí)行。2.1.1程序的順序執(zhí)行及特征2.1.1程序的順序執(zhí)行及特征圖2-1

程序的順序執(zhí)行2.程序順序執(zhí)行時的特征(1)順序性程序順序執(zhí)行時，其執(zhí)行過程可看做一系列嚴(yán)格按程序規(guī)定的狀態(tài)轉(zhuǎn)移過程，也就是每執(zhí)行一條指令，系統(tǒng)就從上一個執(zhí)行狀態(tài)轉(zhuǎn)移到下一個執(zhí)行狀態(tài)，且上一條指令的執(zhí)行結(jié)束是下一條指令執(zhí)行開始的充分必要條件。2.1.1程序的順序執(zhí)行及特征2.程序順序執(zhí)行時的特征(2)封閉性程序是在封閉的環(huán)境下執(zhí)行。即程序在運(yùn)行時獨(dú)占全部資源，資源的狀況只有本程序才能改變它。程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響。(3)可再現(xiàn)性順序執(zhí)行的最終結(jié)果可再現(xiàn)是說它與執(zhí)行速度無關(guān)。只要輸入的初始條件相同，則無論何時重復(fù)執(zhí)行該程序都會得到相同的結(jié)果。2.1.1程序的順序執(zhí)行及特征2.程序順序執(zhí)行時的特征(2)封閉性程序是在封閉的環(huán)境下執(zhí)行。即程序在運(yùn)行時獨(dú)占全部資源，資源的狀況只有本程序才能改變它。程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響。(3)可再現(xiàn)性順序執(zhí)行的最終結(jié)果可再現(xiàn)是說它與執(zhí)行速度無關(guān)。只要輸入的初始條件相同，則無論何時重復(fù)執(zhí)行該程序都會得到相同的結(jié)果。2.1.1程序的順序執(zhí)行及特征

前趨圖(PrecedenceGraph)是一個有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。結(jié)點(diǎn)間的有向邊用于表示兩個結(jié)點(diǎn)之間存在的偏序(PartialOrder)或前趨關(guān)系。前趨關(guān)系用→表示，如圖2-1所示可看做前驅(qū)圖，圖中每個結(jié)點(diǎn)為1個進(jìn)程。于是表示了I1制約C1、C1制約P1等信息。圖2-2所示為多進(jìn)程并發(fā)執(zhí)行的前趨圖。2.1.2前趨圖2.1.2前趨圖圖2-2

程序的并發(fā)執(zhí)行前趨圖1.程序的并發(fā)執(zhí)行以程序?yàn)閱挝贿\(yùn)行時，都是順序執(zhí)行的方式。因?yàn)槌绦驎玫紺PU和輸入輸出設(shè)備，使得其他程序沒有資源可用。因此，程序的并發(fā)執(zhí)行，本質(zhì)上是以程序?yàn)榛A(chǔ)，結(jié)合在該程序上處理的數(shù)據(jù)以及用于控制進(jìn)程的數(shù)據(jù)結(jié)構(gòu)PCB(見第2章2.1.3)而創(chuàng)建起來的進(jìn)程的并發(fā)執(zhí)行。2.1.3程序的并發(fā)執(zhí)行及其特征2.程序并發(fā)執(zhí)行時的特征(1)間斷性程序在并發(fā)執(zhí)行時，微觀上是多個進(jìn)程并發(fā)執(zhí)行。由于它們共享系統(tǒng)資源，以及為完成同一任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間形成了相互制約的關(guān)系。從而使得有些程序在執(zhí)行中出現(xiàn)走走停停的情況。如上例中諸進(jìn)程之間極易出現(xiàn)這種情況。2.1.3程序的并發(fā)執(zhí)行及其特征2.程序并發(fā)執(zhí)行時的特征(2)失去封閉性程序并發(fā)執(zhí)行時，由多個程序(進(jìn)程)共享資源，因而對資源的狀態(tài)由多個程序來改變，從而失去了封閉性。(3)不可再現(xiàn)性各進(jìn)程推進(jìn)的順序不可再現(xiàn)。2.1.3程序的并發(fā)執(zhí)行及其特征3.程序并發(fā)執(zhí)行引發(fā)的問題1)協(xié)調(diào)各程序的執(zhí)行順序。例如，當(dāng)輸入的數(shù)據(jù)還未全部輸入內(nèi)存時，計(jì)算必須等待。2)多個執(zhí)行程序共享系統(tǒng)資源，程序之間可能會相互影響，甚至影響輸出結(jié)果。3)選擇哪些、多少個程序進(jìn)入內(nèi)存運(yùn)行：根據(jù)資源等情況決定。4)內(nèi)存中的執(zhí)行程序哪個先執(zhí)行：根據(jù)系統(tǒng)采用的調(diào)度算法。5)內(nèi)存如何有效分配：內(nèi)存資源非常寶貴2.1.3程序的并發(fā)執(zhí)行及其特征進(jìn)程和程序的對應(yīng)關(guān)系：一個程序?qū)?yīng)一個或多個進(jìn)程，一個進(jìn)程對應(yīng)一個或一段程序。2.1.4進(jìn)程的特征與狀態(tài)1.進(jìn)程的特征(1)進(jìn)程的特征1)結(jié)構(gòu)特征：程序段+相關(guān)數(shù)據(jù)段+PCB。2)動態(tài)性：進(jìn)程是運(yùn)行的程序。它由創(chuàng)建而產(chǎn)生、由調(diào)度而執(zhí)行，由撤消而消亡。3)并發(fā)性：多個進(jìn)程同時存在于內(nèi)存，且能在一段時間內(nèi)同時運(yùn)行。如分時系統(tǒng)中按時間片運(yùn)行。2.1.4進(jìn)程的特征與狀態(tài)1.進(jìn)程的特征(1)進(jìn)程的特征4)獨(dú)立性：進(jìn)程實(shí)體是一個能獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度的基本單位。凡未建立PCB的程序都不能作為一個獨(dú)立的單位參與運(yùn)行。5)異步性：各進(jìn)程按照各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)，或者說進(jìn)程按異步方式運(yùn)行。進(jìn)程最基本的兩個特征是動態(tài)性和并發(fā)性。2.1.4進(jìn)程的特征與狀態(tài)1.進(jìn)程的特征(2)引入進(jìn)程產(chǎn)生的問題1)增加空間的開銷：為進(jìn)程建立數(shù)據(jù)結(jié)構(gòu)(PCB)。2)增加時間開銷：管理、協(xié)調(diào)、跟蹤進(jìn)程；填寫和更新數(shù)據(jù)結(jié)構(gòu)、切換進(jìn)程、保護(hù)現(xiàn)場。3)更難控制：協(xié)調(diào)多個進(jìn)程競爭和共享資源，如何預(yù)防并解決多個進(jìn)程因?yàn)楦偁庂Y源而出現(xiàn)故障(如死鎖、饑餓)。4)處理機(jī)的競爭尤為突出。2.1.4進(jìn)程的特征與狀態(tài)進(jìn)程執(zhí)行時的間斷性，決定了進(jìn)程可能具有多種狀態(tài)。作業(yè)有四種狀態(tài)，分為提交、后備、執(zhí)行和完成。進(jìn)程有三種狀態(tài)，分為就緒(Ready)、運(yùn)行(Run)和阻塞(Block)。在有些操作系統(tǒng)中，將進(jìn)程狀態(tài)分為5種，還有新狀態(tài)、終止?fàn)顟B(tài)。圖2-3示出了進(jìn)程的三種基本狀態(tài)以及各狀態(tài)之間的轉(zhuǎn)換關(guān)系。2.1.4進(jìn)程的特征與狀態(tài)2.1.4進(jìn)程的特征與狀態(tài)圖2-3

進(jìn)程狀態(tài)轉(zhuǎn)換1)就緒(Ready)狀態(tài)已經(jīng)分配到除CPU之外的所有資源，可謂“萬事俱備，只欠CPU”。在一個系統(tǒng)中處于就緒狀態(tài)的進(jìn)程可能有多個，通常將它們排成一個隊(duì)列，稱為就緒隊(duì)列。2)執(zhí)行狀態(tài)(Run)進(jìn)程獲得了包括CPU在內(nèi)的所需的全部資源，程序正在執(zhí)行。2.1.4進(jìn)程的特征與狀態(tài)3)阻塞狀態(tài)(Block)正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機(jī)而處于暫停狀態(tài)，即進(jìn)程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)，或稱等待狀態(tài)。通常把處于阻塞狀態(tài)的進(jìn)程排成一個隊(duì)列，稱為阻塞隊(duì)列。2.1.4進(jìn)程的特征與狀態(tài)3.掛起狀態(tài)(1)引起掛起狀態(tài)的原因1)終端用戶的請求：修改程序。2)父進(jìn)程請求：對子進(jìn)程的修改等。3)負(fù)荷調(diào)節(jié)的需要：資源不夠用。4)操作系統(tǒng)的需要：檢查資源利用情況。2.1.4進(jìn)程的特征與狀態(tài)(2)進(jìn)程狀態(tài)的轉(zhuǎn)換在引入掛起狀態(tài)后，又增加了掛起狀態(tài)(靜止?fàn)顟B(tài))到非掛起狀態(tài)(活動狀態(tài))的轉(zhuǎn)換以及反轉(zhuǎn)換。圖2-4所示為具有掛起狀態(tài)的進(jìn)程狀態(tài)圖。1)活動就緒Readya→靜止就緒Readys：Suspend原語2)活動阻塞Blockeda→靜止阻塞Blockeds：Suspend原語3)靜止就緒Readys→活動就緒Readya：Active原語4)靜止阻塞Blockeds→活動阻塞Blockeda：Active原語2.1.4進(jìn)程的特征與狀態(tài)2.1.4進(jìn)程的特征與狀態(tài)圖2-4

具有掛起狀態(tài)的進(jìn)程狀態(tài)圖進(jìn)程控制塊是進(jìn)程的“身份證”，唯一地標(biāo)識著進(jìn)程的存在。每個進(jìn)程都和它的進(jìn)程控制塊一一對應(yīng)。操作系統(tǒng)在內(nèi)存專門劃出一塊區(qū)域——進(jìn)程控制塊區(qū)——存放進(jìn)程控制塊。2.1.5進(jìn)程控制塊1概念進(jìn)程控制塊(PCB，ProcessControlBlock)，為了描述和控制運(yùn)行進(jìn)程的運(yùn)行，系統(tǒng)為每個進(jìn)程定義了一個數(shù)據(jù)結(jié)構(gòu)，成為進(jìn)程控制塊。(/include/linux/sched.h中structtask_struct)PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。2.1.5進(jìn)程控制塊1概念進(jìn)程控制塊隨著進(jìn)程的創(chuàng)建而創(chuàng)建，即創(chuàng)建一個進(jìn)程，就是創(chuàng)建一個PCB；進(jìn)程控制塊隨著進(jìn)程的撤消而撤消，即撤消一個進(jìn)程，就是撤消進(jìn)程PCB。因此，PCB是進(jìn)程的存在的惟一標(biāo)志。2.1.5進(jìn)程控制塊2進(jìn)程控制塊中的信息(1)進(jìn)程標(biāo)識符(processidentifier,PID)包括進(jìn)程的標(biāo)識符ID(系統(tǒng)指定)、該進(jìn)程的父進(jìn)程標(biāo)識符FID(系統(tǒng)指定)和進(jìn)程的用戶標(biāo)識符UID(如計(jì)算進(jìn)程，由用戶命名)。(2)處理機(jī)狀態(tài)：處理機(jī)的各種寄存器中的內(nèi)容(3)進(jìn)程調(diào)度信息(4)進(jìn)程控制信息2.1.5進(jìn)程控制塊3進(jìn)程控制塊的組織方式(1)鏈接方式Linux操作系統(tǒng)中PCB的組織形式采用鏈接方式。當(dāng)操作系統(tǒng)的進(jìn)程控制塊采用鏈接方式時，操作系統(tǒng)將具有同一狀態(tài)的PCB，組成PCB隊(duì)列。分別是就緒隊(duì)列、阻塞隊(duì)列、空閑隊(duì)列。2.1.5進(jìn)程控制塊3進(jìn)程控制塊的組織方式(2)索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表。如為就緒進(jìn)程的進(jìn)程控制塊索引表、等待進(jìn)程的進(jìn)程控制塊索引表，多處理機(jī)中還會有運(yùn)行態(tài)進(jìn)程的進(jìn)程控制塊索引表，以及空閑的進(jìn)程控制塊索引表。各索引表在內(nèi)存的首地址記錄保存在PCB中。在每個索引表的表項(xiàng)中，記錄具有相應(yīng)狀態(tài)的某個PCB在PCB區(qū)中的地址。2.1.5進(jìn)程控制塊【實(shí)例2-1】LinuxKernal2.6.8定義的PCB。見教材。2.1.5進(jìn)程控制塊2.2進(jìn)程控制一般，把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。原語可分為機(jī)器指令級原語和功能級原語。前者是一條語句，后者是一段代碼。機(jī)器指令級原語的特點(diǎn)是執(zhí)行期間不允許中斷，它是一個不可分割的基本單位。功能級原語的特點(diǎn)是作為原語的程序段不允許并發(fā)執(zhí)行。2.2進(jìn)程控制進(jìn)程控制是進(jìn)程和處理機(jī)管理的一個重要任務(wù)。進(jìn)程控制是指系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。進(jìn)程的控制是通過原語實(shí)現(xiàn)的。用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語、掛起原語和激活原語等。2.2進(jìn)程控制1進(jìn)程圖進(jìn)程圖(ProcessGraph）是用于描述一個進(jìn)程的家族關(guān)系的有向樹。在進(jìn)程Pi創(chuàng)建了進(jìn)程Pj之后，稱Pi是Pj的父進(jìn)程，Pj是Pi的子進(jìn)程。子進(jìn)程可以繼承父進(jìn)程所擁有的所有資源。為了標(biāo)識進(jìn)程之間的家族關(guān)系，在PCB中設(shè)置了家族關(guān)系表項(xiàng)，以標(biāo)明自己的父進(jìn)程以及所有的子進(jìn)程。2.2.1進(jìn)程的創(chuàng)建2引起創(chuàng)建進(jìn)程的事件/創(chuàng)建進(jìn)程的原因1)用戶登錄：合法用戶登錄，創(chuàng)建用戶進(jìn)程。2)作業(yè)調(diào)度：在發(fā)生作業(yè)調(diào)度時，會為被調(diào)度作業(yè)分配內(nèi)存，并為之創(chuàng)建進(jìn)程，以待運(yùn)行。3)提供服務(wù)：如打印進(jìn)程。4)應(yīng)用請求：如輸入、計(jì)算、打印三進(jìn)程。2.2.1進(jìn)程的創(chuàng)建3進(jìn)程的創(chuàng)建(1)引起創(chuàng)建進(jìn)程的事件發(fā)生。(2)調(diào)用進(jìn)程創(chuàng)建原語。(3)創(chuàng)建步驟：1)申請空白PCB；2)為新進(jìn)程分配資源；3)初始化進(jìn)程控制塊；4）將新進(jìn)程插入就緒隊(duì)列。2.2.1進(jìn)程的創(chuàng)建【實(shí)例2-2】創(chuàng)建一個子進(jìn)程。子進(jìn)程的創(chuàng)建通過調(diào)用fork()函數(shù)完成。本質(zhì)上是從父進(jìn)程派生出一個子進(jìn)程。教材：p26提示：了解為什么調(diào)用fork()一次，會返回兩次。2.2.1進(jìn)程的創(chuàng)建1引起進(jìn)程終止的事件(1)正常結(jié)束，即進(jìn)程順利的完成使命后終止，大多數(shù)進(jìn)程終止都是這種情況。(2)異常結(jié)束，即在進(jìn)程運(yùn)行期間，由于出現(xiàn)某種錯誤和故障而迫使進(jìn)程終止。(3)外界干預(yù)，即在進(jìn)程運(yùn)行的過程中，響應(yīng)外界的請求而終止運(yùn)行?？赡艿母深A(yù)包括：1)操作員或操作系統(tǒng)干預(yù)；2)父進(jìn)程請求；3)父進(jìn)程終止。。2.2.2進(jìn)程的終止2進(jìn)程的終止過程(1)終止進(jìn)程事件發(fā)生。(2)調(diào)用終止原語。(3)終止步驟：1)根據(jù)進(jìn)程PID，得到進(jìn)程PCB和進(jìn)程的狀態(tài)；2)若進(jìn)程在執(zhí)行，停止執(zhí)行，置調(diào)度標(biāo)志為真；3)終止子進(jìn)程；4)歸還資源給父進(jìn)程或系統(tǒng)；5)移出隊(duì)列。。2.2.2進(jìn)程的終止1概念實(shí)現(xiàn)進(jìn)程從執(zhí)行狀態(tài)到等待狀態(tài)的轉(zhuǎn)換的原語稱為阻塞原語。實(shí)現(xiàn)進(jìn)程從等待狀態(tài)到就緒狀態(tài)的轉(zhuǎn)換的原語稱為喚醒原語。2.2.3進(jìn)程的阻塞與喚醒2阻塞原語阻塞原語在一個進(jìn)程期待某一事件(例如IO操作、其他進(jìn)程發(fā)來的數(shù)據(jù)等)發(fā)生，但發(fā)生條件尚不具備時，被該進(jìn)程自己調(diào)用來阻塞自己。阻塞事件：1)請求系統(tǒng)服務(wù)；2)啟動某種操作；3)新數(shù)據(jù)尚未到達(dá)；4)無新工作可做。2.2.3進(jìn)程的阻塞與喚醒3阻塞過程阻塞原語在阻塞一個進(jìn)程時，由于該進(jìn)程正處于執(zhí)行狀態(tài)，故應(yīng)先中斷處理機(jī)和保存該進(jìn)程的CPU現(xiàn)場。然后將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。

2.2.3進(jìn)程的阻塞與喚醒4喚醒問題當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時，等待該事件的所有進(jìn)程都可能被喚醒。顯然，一個處于阻塞狀態(tài)的進(jìn)程不可能自己喚醒自己。5喚醒進(jìn)程的方法喚醒進(jìn)程有兩種方法：一種是由系統(tǒng)進(jìn)程喚醒。另一種是由事件發(fā)生進(jìn)程喚醒。2.2.3進(jìn)程的阻塞與喚醒4喚醒問題當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時，等待該事件的所有進(jìn)程都可能被喚醒。顯然，一個處于阻塞狀態(tài)的進(jìn)程不可能自己喚醒自己。5喚醒進(jìn)程的方法喚醒進(jìn)程有兩種方法：一種是由系統(tǒng)進(jìn)程喚醒。另一種是由事件發(fā)生進(jìn)程喚醒。2.2.3進(jìn)程的阻塞與喚醒6喚醒過程喚醒原語首先將被喚醒進(jìn)程從相應(yīng)的等待隊(duì)列中取出，將被喚醒進(jìn)程置為就緒狀態(tài)之后，送入就緒隊(duì)列。在把被喚醒進(jìn)程送入就緒隊(duì)列之后，喚醒原語既可以返回原調(diào)用程序，也可以轉(zhuǎn)向進(jìn)程調(diào)度，以便讓調(diào)度程序有機(jī)會選擇一個合適的進(jìn)程執(zhí)行。2.2.3進(jìn)程的阻塞與喚醒1進(jìn)程的掛起(1)概念掛起進(jìn)程在操作系統(tǒng)中可以定義為暫時被淘汰出內(nèi)存的進(jìn)程系統(tǒng)的資源是有限的，在資源不足的情況下，操作系統(tǒng)會對在內(nèi)存中的進(jìn)程進(jìn)行合理的安排，其中有的進(jìn)程被暫時調(diào)離出內(nèi)存。2.2.4進(jìn)程的掛起和激活1進(jìn)程的掛起(2)引起掛起狀態(tài)的原因1)終端用戶的請求。2)父進(jìn)程的請求。3)負(fù)荷調(diào)節(jié)的需要。4)操作系統(tǒng)的需要。5)對換的需要。2.2.4進(jìn)程的掛起和激活2進(jìn)程的激活(1)概念處于掛起狀態(tài)的進(jìn)程，當(dāng)有存放其的內(nèi)存空間時，會被操作系統(tǒng)再次調(diào)回內(nèi)存，重新進(jìn)入等待被執(zhí)行的狀態(tài)（即就緒態(tài)）或阻塞狀態(tài)。(2)引起激活狀態(tài)的原因當(dāng)發(fā)生激活進(jìn)程的事件，如父進(jìn)程或用戶進(jìn)程請求激活指定進(jìn)程時，會發(fā)生激活。2.2.4進(jìn)程的掛起和激活2進(jìn)程的激活(3)激活原語active()激活過程1)激活原語將進(jìn)程從外存調(diào)入內(nèi)存。2)檢查該進(jìn)程的現(xiàn)行狀態(tài)并進(jìn)行相應(yīng)操作(靜止就緒→活動就緒；靜止阻塞→活動阻塞)。3)假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時，檢查是否要進(jìn)行重新調(diào)度，即比較被激活進(jìn)程與當(dāng)前進(jìn)程的優(yōu)先級，決定處理機(jī)歸屬。2.2.4進(jìn)程的掛起和激活2.3進(jìn)程互斥一組并發(fā)進(jìn)程之間可能是交往的也可能是無關(guān)的。無關(guān)的并發(fā)進(jìn)程是指它們分別在不同的變量集合或資源上操作，所以一個進(jìn)程的執(zhí)行與其他進(jìn)程的進(jìn)展無關(guān)，即一個并發(fā)進(jìn)程不會改變另一個并發(fā)進(jìn)程的變量值。

然而交往的并發(fā)進(jìn)程它們共享某些變量或資源，所以一個進(jìn)程的執(zhí)行可能影響其他進(jìn)程的結(jié)果，因此這種交往必須是有控制的，否則會出現(xiàn)不正確的結(jié)果。叫作與時間有關(guān)的錯誤。2.3.1與時間有關(guān)的錯誤為了保證共享資源的并發(fā)進(jìn)程正確地操作，引進(jìn)互斥技術(shù)來保證并發(fā)進(jìn)程不同時進(jìn)入這個特別的區(qū)域，或者說不讓他們同時訪問共享變量或資源。這個涉及到共享變量或資源的區(qū)域稱為臨界區(qū)。一次只能供一個進(jìn)程使用的資源被稱為臨界資源，訪問臨界資源的那段程序被稱為臨界區(qū)。多個進(jìn)程訪問公共變量時，當(dāng)一個進(jìn)程正在進(jìn)行訪問時，就不允許其他進(jìn)程對該臨界資源訪問，它們必須互斥地使用這個臨界資源，這種約束關(guān)系叫做互斥。2.3.2互斥的概念互斥訪問應(yīng)遵循準(zhǔn)則：1)不能假設(shè)各并發(fā)進(jìn)程的相對執(zhí)行速度。即各并發(fā)進(jìn)程享有平等的、獨(dú)立的競爭共有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時，其他并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)。2)某一時間，只能有一個進(jìn)程在臨界區(qū)內(nèi)執(zhí)行。3)并發(fā)進(jìn)程中的某個進(jìn)程不在臨界區(qū)時，它不阻止其他進(jìn)程進(jìn)入臨界區(qū)。4)并發(fā)進(jìn)程中的若干個進(jìn)程申請進(jìn)入臨界區(qū)時，只能允許一個進(jìn)程進(jìn)入。5)并發(fā)進(jìn)程中的某個進(jìn)程申請進(jìn)入臨界區(qū)時開始，應(yīng)在有限時間內(nèi)得以進(jìn)入臨界區(qū)。2.3.2互斥的概念臨界區(qū)？臨界資源？直接制約？間接制約？互斥？同步？2.3.2互斥的概念臨界區(qū)？臨界資源？直接制約？間接制約？互斥？同步？要實(shí)現(xiàn)互斥，一種可能的辦法是對臨界區(qū)加鎖以實(shí)現(xiàn)互斥。當(dāng)某個進(jìn)程進(jìn)入臨界區(qū)之后鎖上臨界區(qū)，直到它退出臨界區(qū)時再開鎖。并發(fā)進(jìn)程在申請進(jìn)入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。單CPU環(huán)境下，可能會陷入循環(huán)測試（忙等）。2.3.3互斥的加鎖實(shí)現(xiàn)2.4進(jìn)程同步異步環(huán)境：相互合作的一組并發(fā)進(jìn)程，其中每一個進(jìn)程都以各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)；但它們又需要密切合作，以實(shí)現(xiàn)共同的任務(wù)。直接制約：一組在異步環(huán)境下的并發(fā)進(jìn)程，當(dāng)各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過程稱為并發(fā)進(jìn)程間的直接制約。同步：把因直接制約而互相發(fā)送消息、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過程稱為進(jìn)程間的同步。2.4.1同步切菜機(jī)和洗菜機(jī)之間的相互制約、相互等待的合作關(guān)系就是典型的同步關(guān)系。同步機(jī)制應(yīng)遵循的規(guī)則：空閑讓進(jìn)；忙則等待；有限等待；讓權(quán)等待。2.4.2同步的例子：流水作業(yè)互斥和同步的區(qū)別前面的互斥算法都存在問題，需要一個地位高于進(jìn)程的管理者來解決公有資源的使用問題。操作系統(tǒng)可從進(jìn)程管理者的角度來處理互斥的問題，信號量就是操作系統(tǒng)提供的管理公有資源的有效手段。十字路口帶計(jì)時器的信號燈就是典型的信號量。在操作系統(tǒng)中，信號量sem是一整數(shù)。2.4.3信號量機(jī)制1整型信號量機(jī)制最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。wait和signal操作可描述為：Voidwait(S){ whileS≤0dono-op; S=S-1;} 2.4.3信號量機(jī)制Voidsignal(S){S:=S+1;} 2記錄型信號量機(jī)制(1)記錄型信號量的出現(xiàn)盡管整型信號能夠?qū)崿F(xiàn)進(jìn)程之間的同步，但是，代價是巨大的，缺陷是進(jìn)程出現(xiàn)了“忙等”的現(xiàn)象，原因是該機(jī)制不能完全遵循同步機(jī)制應(yīng)遵循的規(guī)則。以此為思路，提出記錄型信號量機(jī)制，解決進(jìn)程“忙等”問題，從而使得該機(jī)制能夠完全遵循同步機(jī)制應(yīng)遵循的規(guī)則。 2.4.3信號量機(jī)制(2)記錄型信號量的P、V操作1)P原語操作的主要動作是：sem減1；若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；若sem減1后小于零，則該進(jìn)程被阻塞到與該信號相對應(yīng)的阻塞隊(duì)列中，然后轉(zhuǎn)向進(jìn)程調(diào)度。2.4.3信號量機(jī)制(2)記錄型信號量的P、V操作2)V原語操作的主要動作是：sem加1；若相加結(jié)果大于零，則進(jìn)程繼續(xù)執(zhí)行；若相加結(jié)果小于或等于零，則從該信號的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)向進(jìn)程調(diào)度。2.4.3信號量機(jī)制2記錄型信號量機(jī)制(3)記錄型信號量的實(shí)現(xiàn)在記錄型信號量機(jī)制中，1）需要一個用于代表資源數(shù)目的整型變量value(資源信號量)。2）需要一個用于鏈接上述的所有等待進(jìn)程的進(jìn)程鏈表L。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。 2.4.3信號量機(jī)制Pascal語言描述Typesemaphore=recordvalue:integer;L:listofprocess;End C語言描述Structsemaphore{intvalue;semaphoreL;};2.4.3信號量機(jī)制Procedurewait(S)varS:semaphore;begin S.value:=S.value-1;ifS.value＜0thenblock(S,L);end

Proceduresignal(S)varS:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S,L);end2.4.3信號量機(jī)制(4)記錄型信號量機(jī)制的wait()和signal()操作put（s）{wait（empty）；wait（mutex）；put‘s’intotheemptyplace;signal（mutex）；signal（full）;get（s）{wait（full）；wait（mutex）；get‘s’fromthefullplace;signal（mutex）；signal（empty）;【實(shí)例】在籠子上互斥地執(zhí)行放入/拿出操作intempty=1;intmutex=1;intfull=0;items;3AND型信號量機(jī)制(1)信號量機(jī)制存在的問題上述的進(jìn)程互斥問題，是針對并發(fā)進(jìn)程之間共享一個臨界資源而言的。在有些應(yīng)用場合，一個進(jìn)程需要獲得兩個或兩個以上的資源才能執(zhí)行。判定：繼續(xù)采用記錄型信號量，是否可能會出現(xiàn)死鎖。回答：是。（why？？？） 2.4.3信號量機(jī)制3AND型信號量機(jī)制(2)AND同步機(jī)制的基本思想將進(jìn)程在整個運(yùn)行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要有一個資源未分配給進(jìn)程，其他所有可能為之分配的資源，也不分配給他。亦即，對若干個臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。 2.4.3信號量機(jī)制3AND型信號量機(jī)制(3)AND同步機(jī)制的實(shí)現(xiàn)基于以上分析，在wait操作中，增加了一個“AND”條件，故稱為AND同步，或稱為同時wait操作，即Swait(Simultaneouswait)。教材：p34 2.4.3信號量機(jī)制4信號量集(1)信號量集的必要性在記錄型信號量機(jī)制中wait(s)或signal(s)操作僅能對信號量實(shí)施加1或減1操作，意味著每次只能獲得或釋放一個單位的臨界資源。而當(dāng)一次需要N個某類臨界資源時，需要進(jìn)行N次wait(s)操作。顯然這很低效。此外，在有些情況下當(dāng)資源數(shù)量低于某一閾值時，不予分配，因此在每次分配時要測試該資源的數(shù)量，是否大于閾值?；谏鲜鰞牲c(diǎn)，對AND信號量加以擴(kuò)展，形成一般化的“信號量集”機(jī)制。 2.4.3信號量機(jī)制4信號量集(2)信號量集機(jī)制的形式化描述swait(Si,ti,di)變量描述：Si：可用資源數(shù)；ti：閾值；di：申請資源數(shù)。教材：p35 2.4.3信號量機(jī)制2.4.3信號量機(jī)制表2-1信號量機(jī)制比較

整型記錄型AND型信號量集備注種類數(shù)11NN1)記錄型是AND的特殊情況;2)AND型是信號量集的特殊情況數(shù)量111M特點(diǎn)整型信號量循環(huán)測試不支持讓權(quán)等待2.5經(jīng)典進(jìn)程的同步問題1問題描述生產(chǎn)者-消費(fèi)者模型(Producer-ConsumerModel，PCM)是6大并行算法模型之一，常用來討論并發(fā)程序和并發(fā)控制問題。生產(chǎn)者-消費(fèi)者描述的是有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。在生產(chǎn)者-消費(fèi)者模型中，既有生產(chǎn)者或消費(fèi)者自身進(jìn)程的并發(fā)，又有生產(chǎn)者和消費(fèi)者之間的并發(fā)，具備并發(fā)程序的典型特征。 2.5.1生產(chǎn)者-消費(fèi)者問題

PCM為使生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程并發(fā)進(jìn)行，在它們之間設(shè)置了一個具有多個緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程可以將其所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中，消費(fèi)者進(jìn)程可以從一個緩沖區(qū)中取得產(chǎn)品去消費(fèi)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程從空緩沖區(qū)中取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向滿緩沖區(qū)中放產(chǎn)品。由于生產(chǎn)者—消費(fèi)者問題是相互合作的進(jìn)程關(guān)系的一種抽象，因此，該問題有很大的代表性及實(shí)用價值。生產(chǎn)者—消費(fèi)者問題即theProducer-ConsumerProblem，簡稱PC問題。 1問題描述我們可利用一個數(shù)組來表示上述的具有n個(0，1，…，n-1)緩沖單元的緩沖區(qū)。用輸入指針in作寫指針，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個產(chǎn)品后，輸入指針加1；用一個輸出指針out作讀指針，每當(dāng)消費(fèi)者進(jìn)程取走一個產(chǎn)品后，輸出指針加1。由于緩沖區(qū)通常被組織成循環(huán)隊(duì)列，故應(yīng)把寫指針加1表示成in：=(in+1)modn；讀指針加1表示成out：=(out+1)modn。當(dāng)(in+1)modn=out時表示緩沖區(qū)滿；而in=out則表示緩沖區(qū)空。此外，還引入了一個整型變量counter,其初始值為0。每當(dāng)生產(chǎn)者進(jìn)程向緩沖區(qū)中投放一個產(chǎn)品后，使counter加1；反之，每當(dāng)消費(fèi)者進(jìn)程從中取走一個產(chǎn)品時，使counter減1。 2問題分析生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量：intn,buffer[n];intin,out;//in∈[0,n-1],out∈[0,n-1]intcount;//count∈[0,n] 3利用整型信號量解決PC問題

voidproducer() {produceaniteminnextp;while(counter)=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;}; voidconsumer(){whilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;};3利用整型信號量解決PC問題設(shè)生產(chǎn)者和消費(fèi)者之間的公用緩沖區(qū)有n個緩沖單元。利用互斥信號量mutex實(shí)現(xiàn)諸進(jìn)程對緩沖區(qū)的互斥訪問；信號量empty表示緩沖區(qū)中空緩沖單元的個數(shù)，F(xiàn)ull表示滿緩沖區(qū)中產(chǎn)品的個數(shù)。這些生產(chǎn)者和消費(fèi)者之間存在同步關(guān)系，只要緩沖區(qū)未滿，生產(chǎn)者便可將數(shù)據(jù)寫入緩沖區(qū)；只要緩沖區(qū)未空，消費(fèi)者便可從緩沖區(qū)中取走一個數(shù)據(jù)。 4利用記錄型信號量解決PC問題

intmutex=0,empty=n,full=0;intbuffer[n];intin=0,out=0;Voidproducer(){ Produceranitem,nextp;wait(empty); wait(mutex); Buffer(in)=nextp;In=(in+1)modn;Ssignal(mutex); Ssignal(full);}

Voidconsumer(){wait(full);wait(mutex);nextc=buffer(out);out=(out+1)modn;signal(mutex);signal(empty);consumenextc;}4利用記錄型信號量解決PC問題首先，在每個程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)；其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在生產(chǎn)者進(jìn)程中，而signal(empty)則在消費(fèi)者進(jìn)程中，生產(chǎn)者進(jìn)程若因執(zhí)行wait(empty)而阻塞，以后將由消費(fèi)者進(jìn)程通過執(zhí)行Signal(empty)將它喚醒；最后，在每個程序中的多個wait操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。 PC問題注意事項(xiàng)

Voidproducer(){produceranitem,nextp;swait(empty,mutex);buffer(in)=nextp;in=(in+1)modn;ssignal(mutex,full);}

Voidconsumer(){swait(full,mutex);nextc=buffer(out);out=(out+1)modn;ssignal(mutex,(empty);consumenextc;}5利用AND信號量解決PC問題一個數(shù)據(jù)文件或數(shù)據(jù)對象，可以被多個進(jìn)程共享。其中有些進(jìn)程要求讀，這些進(jìn)程叫做讀進(jìn)程；而另一些進(jìn)程要求寫或修改，這些進(jìn)程叫寫進(jìn)程。

2.5.2讀者-寫者問題“讀者—寫者”問題是現(xiàn)代操作系統(tǒng)中經(jīng)典的進(jìn)程同步互斥問題，在以C/S模式為代表的多進(jìn)(線)程通信系統(tǒng)都可以作為該模型的不同表現(xiàn)形式，有著廣泛的應(yīng)用。該問題首先在1971年由Courtois等人解決。該問題描述如下：一個數(shù)據(jù)文件或記錄可被多個進(jìn)程所共享，我們將其中只要求讀該文件的進(jìn)程稱為讀者，即“Reader進(jìn)程”，其他進(jìn)程稱為寫者，即“Writer進(jìn)程”。多個Reader進(jìn)程和多個Writer進(jìn)程在某個時間段內(nèi)對該文件資源進(jìn)行異步操作，也就是說允許多個進(jìn)程同時讀一個共享對象，但絕不允許一個Writer進(jìn)程和其他Reader進(jìn)程或Writer進(jìn)程同時訪問共享對象。

1問題描述因此，所謂“讀者—寫者問題”就是指必須保證一個Writer進(jìn)程和其他進(jìn)程(Writer進(jìn)程和Reader進(jìn)程)互斥地訪問共享對象的同步問題。兩者的讀寫操作限制如下：寫—寫互斥，即不允許多個寫者同時對文件進(jìn)行寫操作；讀—寫互斥，即不允許讀者和寫者同時對文件分別進(jìn)行讀寫操作；讀—讀允許，即允許多個讀者同時對文件進(jìn)行讀操作。

1問題描述intrmutex=1,wmutex=1，readcount=0；//初始化VoidReade(){dowhile(true){wait(rmutex);//各讀者互斥地通過門禁，進(jìn)入讀書室//第1個讀者進(jìn)入讀書室時需要開啟禁止寫者進(jìn)入的信號ifreadcount=0thenwait(wmutex);Readcount=Readcount+1;signal(rmutex);performreadoperation;//讀者閱讀，此時進(jìn)行的讀操作無需互斥

2利用記錄型信號量解決讀者-寫者問題//以下為離開讀書室wait(rmutex);//互斥地通過門禁，離開讀書室readcount=readcount-1;//最后1個讀者離開讀書室時需要關(guān)閉禁止寫者進(jìn)入的信號ifreadcount=0thensignal(wmutex);signal(rmutex);}} 2利用記錄型信號量解決讀者-寫者問題intrmutex=-1,wmutex=1；intreadcount=0;VoidReader() { dowhile(true){ Swait(L,1,1，mx,1,0); performreadoperation;Ssignal(L,1);} } 3利用信號量集機(jī)制解決讀者-寫者問題Voidwriter(){dowhile(true){Swait(mx,1,1;0,L,0);performwriteoperation;Ssignal(mx,1);}}【實(shí)例2-5】

（a）b）圖2-6

讀者-寫者問題在生活中的實(shí)例（a）大學(xué)校門的門禁系統(tǒng)（b）地鐵入口的門禁系統(tǒng)

有五個哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家們共用一張圓桌，分別坐在周圍的五張椅子上。在圓桌上有五個碗和五支筷子，平時哲學(xué)家進(jìn)行思考，饑餓時便試圖取用其左、右靠他最近的筷子，只有當(dāng)他拿到兩支筷子時才能進(jìn)餐。進(jìn)餐完畢，放下筷子又繼續(xù)思考。哲學(xué)家問題的實(shí)現(xiàn)，請參照教材，自主學(xué)習(xí)。2.5.3哲學(xué)家進(jìn)餐問題2.6管程機(jī)制信號量機(jī)制是一種方便而有效的進(jìn)程同步機(jī)制，但每個要訪問臨界資源的進(jìn)程須自備wait和signal操作。這樣不僅給系統(tǒng)管理造成麻煩，而且還會因同步操作使用不當(dāng)而導(dǎo)致死鎖，甚至產(chǎn)生與時間有關(guān)的錯誤。2.6.1管程的引入可能出現(xiàn)的錯誤：1)顛倒wait和signal操作導(dǎo)致臨界資源被同時訪問；2)signal誤寫為wait操作，導(dǎo)致任何進(jìn)程無法訪問臨界資源，發(fā)生死鎖；3)遺漏wait操作會導(dǎo)致多個進(jìn)程同時訪問臨界資源，遺漏signal則導(dǎo)致其他進(jìn)程無法進(jìn)入臨界區(qū)?；谝陨锨闆r，1971年Dijkstra提出了秘書“進(jìn)程”機(jī)制。1973年Hansan和Hoare又將“秘書”進(jìn)程思想發(fā)展為“管程”概念，把并發(fā)進(jìn)程間的同步操作分別集中在相應(yīng)的管程中。2.6.1管程的引入1管程的定義需要為管程賦予一個名字。另外，形式上，管程的結(jié)構(gòu)和面向?qū)ο蟪绦蛟O(shè)計(jì)技術(shù)中的類是類似的。管程和類的比較，如表2-2所示。表2-2管程和類的結(jié)構(gòu)比較2.6.2管程的基本概念管程（Monitor）類（Class）共享數(shù)據(jù)（變量申明）成員變量的申明操作過程（過程的定義）成員函數(shù)的定義數(shù)據(jù)初始值的設(shè)定（初始化）成員變量的初始化1管程的定義(1)管程由三部分組成1)局部于管程的共享變量說明。2)對該數(shù)據(jù)進(jìn)行操作的一組過程。3)對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。2.6.2管程的基本概念(2)管程的定義typemonitor-name=monitor//第一部分變量申明variabledeclarations//第二部分過程定義procedureentryP1(…)begin…end;procedureentryP2(…)begin…end;…procedureentryPn(…)begin…end;//第三部分初始化代碼begininitializationcode;end2.6.2管程的基本概念2條件變量在管程機(jī)制中，引起進(jìn)程等待的原因可能很多，為了區(qū)別它們，有引入了條件變量condition。管程中對每個條件變量，都須予以說明，其形式為Varx,y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.signal。2.6.2管程的基本概念1基本思想利用管程方法來解決生產(chǎn)者-消費(fèi)者問題時，首先便是為它們建立一個管程，并命名為Proclucer-Consumer，或簡稱為PC。其中包括兩個過程：1)put(item)過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖區(qū)中，并用整型變量count來表示在緩沖區(qū)中已有的產(chǎn)品數(shù)目，當(dāng)count≥n時，表示緩沖區(qū)已滿，生產(chǎn)者須等待。2)get(item)過程。消費(fèi)者利用該過程從緩沖區(qū)中取出一個產(chǎn)品，當(dāng)count≤0時，表示緩沖區(qū)中已無可取用的產(chǎn)品，消費(fèi)者應(yīng)等待。2.6.3利用管程解決PC問題2管程描述//管程producer-consumer的定義typeproducer-consumer=monitor//變量申明varin,out,count:integer;buffer:array[0..n-1]ofitem;notfull,notempty:condition;2.6.3利用管程解決PC問題//put()過程定義procedureentryput(item)beginifcount≥nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1;ifnotempty.queuethennotempty.signal;end2.6.3利用管程解決PC問題//get()過程定義procedureentryget(item)beginifcount≤0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.quenethennotfull.signal;end//變量初始化beginin:=out:=0;count:=0;end2.6.3利用管程解決PC問題3生產(chǎn)者和消費(fèi)者進(jìn)程描述在利用管程解決生產(chǎn)者-消費(fèi)者問題時，其中的生產(chǎn)者和消費(fèi)者可描述為：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;end2.6.3利用管程解決PC問題consumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end2.7進(jìn)程通信進(jìn)程通信，是指進(jìn)程之間的信息交換，其所交換的信息量大小不一。一般來說，進(jìn)程間的通信根據(jù)通信的內(nèi)容可以劃分為兩種：控制信息的傳送與大批量數(shù)據(jù)傳送。低級進(jìn)程通信：進(jìn)程之間的互斥和同步，由于其所交換的信息量少而被歸結(jié)為低級通信。信號量機(jī)制在通信方面的缺點(diǎn)：1)效率低；2)通信對用戶不透明。2.7進(jìn)程通信高級進(jìn)程通信是指用戶可直接利用操作系統(tǒng)所提供的一組通信命令，高效地傳送大量數(shù)據(jù)的一種通信方式。操作系統(tǒng)隱藏了進(jìn)程通信的細(xì)節(jié)?；蛘哒f，通信過程對用戶是透明的。這樣，就大大減少了通信程序編制上的復(fù)雜性。2.7進(jìn)程通信1共享存儲器系統(tǒng)在共享存儲器系統(tǒng)中，相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)，進(jìn)程之間能夠通過這些空間進(jìn)行通信。可分為兩類。(1)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 在該方式下，要求諸進(jìn)程公用某些數(shù)據(jù)結(jié)構(gòu)，借以實(shí)現(xiàn)諸進(jìn)程間的信息交換。如生產(chǎn)者—消費(fèi)者問題中有使用有界緩沖區(qū)這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)通信的。(2)基于共享存儲區(qū)的通信方式 2.7.1進(jìn)程的通信類型1共享存儲器系統(tǒng)在共享存儲器系統(tǒng)中，相互通信的進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)，進(jìn)程之間能夠通過這些空間進(jìn)行通信。可分為兩類。(1)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式(2)基于共享存儲區(qū)的通信方式 為了傳輸大量數(shù)據(jù)，在存儲器中劃出了一塊共享存儲區(qū)，諸進(jìn)程可通過對共享存儲區(qū)中數(shù)據(jù)的讀或?qū)憗韺?shí)現(xiàn)通信。這種方式屬于高級通信。2.7.1進(jìn)程的通信類型2消息傳遞系統(tǒng)消息傳遞機(jī)制是使用最廣泛的一種進(jìn)程間通信的機(jī)制。程序員直接利用系統(tǒng)提供的一組通信命令(原語)進(jìn)行通信。操作系統(tǒng)隱藏了通信的細(xì)節(jié)，簡化了通信程序的編制。3管道通信管道是指用于連接一個讀進(jìn)程和一個寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個共享文件，又名pipe文件。圖2-7所示為管道示意圖。2.7.1進(jìn)程的通信類型3管道通信管道是指用于連接一個讀進(jìn)程和一個寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個共享文件，又名pipe文件。圖2-7所示為管道示意圖。2.7.1進(jìn)程的通信類型圖2-7管道示意圖在進(jìn)程之間通信時，源進(jìn)程可以直接或間接地將消息傳送給目標(biāo)進(jìn)程，由此將進(jìn)程通信分為直接通信和間接方式。1直接通信方式直接通信方式指發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。此時，要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式提供對方的標(biāo)識符。2.7.2消息傳遞系統(tǒng)的實(shí)現(xiàn)方法1直接通信方式通常，系統(tǒng)提供下述兩條通信命令(原語)：1)發(fā)送原語：Send（Receiver,message)；發(fā)送一個消息給接收進(jìn)程2)接收原語：Receiv