第2章 進程管理

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

在早期的操作系統(tǒng)中，程序采用絕對裝入方式(見第5章5.1節(jié))，內存采用單一連續(xù)分配方式(見第5章5.2節(jié))。在這個時期，每個正在運行的程序占用了系統(tǒng)所有資源，只有一個程序運行完畢后才考慮運行下一個程序。也就是，程序的執(zhí)行是順序執(zhí)行，即必須在一個程序執(zhí)行完成后，才允許另一個程序執(zhí)行。2.1進程的基本概念隨著支持多任務系統(tǒng)的固定分區(qū)內存分配技術(見第5章5.2節(jié))的出現(xiàn)，系統(tǒng)允許多個程序并發(fā)執(zhí)行。程序的這兩種運行方式間有著顯著不同。也正是程序并發(fā)執(zhí)行時的特征，才在操作系統(tǒng)中引入進程的概念。2.1進程的基本概念1.程序的順序執(zhí)行程序是一個在時間上按嚴格次序前后相繼的操作序列，是一個靜態(tài)的概念。一個具有獨立功能的程序獨占處理機直至得到最終結果的過程稱為程序的順序執(zhí)行。一個完整的程序應該包括輸入、計算和輸出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í)行過程可看做一系列嚴格按程序規(guī)定的狀態(tài)轉移過程，也就是每執(zhí)行一條指令，系統(tǒng)就從上一個執(zhí)行狀態(tài)轉移到下一個執(zhí)行狀態(tài)，且上一條指令的執(zhí)行結束是下一條指令執(zhí)行開始的充分必要條件。2.1.1程序的順序執(zhí)行及特征2.程序順序執(zhí)行時的特征(2)封閉性程序是在封閉的環(huán)境下執(zhí)行。即程序在運行時獨占全部資源，資源的狀況只有本程序才能改變它。程序一旦開始執(zhí)行，其執(zhí)行結果不受外界因素影響。(3)可再現(xiàn)性順序執(zhí)行的最終結果可再現(xiàn)是說它與執(zhí)行速度無關。只要輸入的初始條件相同，則無論何時重復執(zhí)行該程序都會得到相同的結果。2.1.1程序的順序執(zhí)行及特征2.程序順序執(zhí)行時的特征(2)封閉性程序是在封閉的環(huán)境下執(zhí)行。即程序在運行時獨占全部資源，資源的狀況只有本程序才能改變它。程序一旦開始執(zhí)行，其執(zhí)行結果不受外界因素影響。(3)可再現(xiàn)性順序執(zhí)行的最終結果可再現(xiàn)是說它與執(zhí)行速度無關。只要輸入的初始條件相同，則無論何時重復執(zhí)行該程序都會得到相同的結果。2.1.1程序的順序執(zhí)行及特征

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

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

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

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

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

然而交往的并發(fā)進程它們共享某些變量或資源，所以一個進程的執(zhí)行可能影響其他進程的結果，因此這種交往必須是有控制的，否則會出現(xiàn)不正確的結果。叫作與時間有關的錯誤。2.3.1與時間有關的錯誤為了保證共享資源的并發(fā)進程正確地操作，引進互斥技術來保證并發(fā)進程不同時進入這個特別的區(qū)域，或者說不讓他們同時訪問共享變量或資源。這個涉及到共享變量或資源的區(qū)域稱為臨界區(qū)。一次只能供一個進程使用的資源被稱為臨界資源，訪問臨界資源的那段程序被稱為臨界區(qū)。多個進程訪問公共變量時，當一個進程正在進行訪問時，就不允許其他進程對該臨界資源訪問，它們必須互斥地使用這個臨界資源，這種約束關系叫做互斥。2.3.2互斥的概念互斥訪問應遵循準則：1)不能假設各并發(fā)進程的相對執(zhí)行速度。即各并發(fā)進程享有平等的、獨立的競爭共有資源的權利，且在不采取任何措施的條件下，在臨界區(qū)內任一指令結束時，其他并發(fā)進程可以進入臨界區(qū)。2)某一時間，只能有一個進程在臨界區(qū)內執(zhí)行。3)并發(fā)進程中的某個進程不在臨界區(qū)時，它不阻止其他進程進入臨界區(qū)。4)并發(fā)進程中的若干個進程申請進入臨界區(qū)時，只能允許一個進程進入。5)并發(fā)進程中的某個進程申請進入臨界區(qū)時開始，應在有限時間內得以進入臨界區(qū)。2.3.2互斥的概念臨界區(qū)？臨界資源？直接制約？間接制約？互斥？同步？2.3.2互斥的概念臨界區(qū)？臨界資源？直接制約？間接制約？互斥？同步？要實現(xiàn)互斥，一種可能的辦法是對臨界區(qū)加鎖以實現(xiàn)互斥。當某個進程進入臨界區(qū)之后鎖上臨界區(qū)，直到它退出臨界區(qū)時再開鎖。并發(fā)進程在申請進入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。單CPU環(huán)境下，可能會陷入循環(huán)測試（忙等）。2.3.3互斥的加鎖實現(xiàn)2.4進程同步異步環(huán)境：相互合作的一組并發(fā)進程，其中每一個進程都以各自獨立的、不可預知的速度向前推進；但它們又需要密切合作，以實現(xiàn)共同的任務。直接制約：一組在異步環(huán)境下的并發(fā)進程，當各自的執(zhí)行結果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程稱為并發(fā)進程間的直接制約。同步：把因直接制約而互相發(fā)送消息、互相等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步。2.4.1同步切菜機和洗菜機之間的相互制約、相互等待的合作關系就是典型的同步關系。同步機制應遵循的規(guī)則：空閑讓進；忙則等待；有限等待；讓權等待。2.4.2同步的例子：流水作業(yè)互斥和同步的區(qū)別前面的互斥算法都存在問題，需要一個地位高于進程的管理者來解決公有資源的使用問題。操作系統(tǒng)可從進程管理者的角度來處理互斥的問題，信號量就是操作系統(tǒng)提供的管理公有資源的有效手段。十字路口帶計時器的信號燈就是典型的信號量。在操作系統(tǒng)中，信號量sem是一整數(shù)。2.4.3信號量機制1整型信號量機制最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。wait和signal操作可描述為：Voidwait(S){ whileS≤0dono-op; S=S-1;} 2.4.3信號量機制Voidsignal(S){S:=S+1;} 2記錄型信號量機制(1)記錄型信號量的出現(xiàn)盡管整型信號能夠實現(xiàn)進程之間的同步，但是，代價是巨大的，缺陷是進程出現(xiàn)了“忙等”的現(xiàn)象，原因是該機制不能完全遵循同步機制應遵循的規(guī)則。以此為思路，提出記錄型信號量機制，解決進程“忙等”問題，從而使得該機制能夠完全遵循同步機制應遵循的規(guī)則。 2.4.3信號量機制(2)記錄型信號量的P、V操作1)P原語操作的主要動作是：sem減1；若sem減1后仍大于或等于零，則進程繼續(xù)執(zhí)行；若sem減1后小于零，則該進程被阻塞到與該信號相對應的阻塞隊列中，然后轉向進程調度。2.4.3信號量機制(2)記錄型信號量的P、V操作2)V原語操作的主要動作是：sem加1；若相加結果大于零，則進程繼續(xù)執(zhí)行；若相加結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉向進程調度。2.4.3信號量機制2記錄型信號量機制(3)記錄型信號量的實現(xiàn)在記錄型信號量機制中，1）需要一個用于代表資源數(shù)目的整型變量value(資源信號量)。2）需要一個用于鏈接上述的所有等待進程的進程鏈表L。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結構而得名的。 2.4.3信號量機制Pascal語言描述Typesemaphore=recordvalue:integer;L:listofprocess;End C語言描述Structsemaphore{intvalue;semaphoreL;};2.4.3信號量機制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信號量機制(4)記錄型信號量機制的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）;【實例】在籠子上互斥地執(zhí)行放入/拿出操作intempty=1;intmutex=1;intfull=0;items;3AND型信號量機制(1)信號量機制存在的問題上述的進程互斥問題，是針對并發(fā)進程之間共享一個臨界資源而言的。在有些應用場合，一個進程需要獲得兩個或兩個以上的資源才能執(zhí)行。判定：繼續(xù)采用記錄型信號量，是否可能會出現(xiàn)死鎖?；卮穑菏?。（why？？？） 2.4.3信號量機制3AND型信號量機制(2)AND同步機制的基本思想將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完后再一起釋放。只要有一個資源未分配給進程，其他所有可能為之分配的資源，也不分配給他。亦即，對若干個臨界資源的分配，采取原子操作方式：要么全部分配到進程，要么一個也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。 2.4.3信號量機制3AND型信號量機制(3)AND同步機制的實現(xiàn)基于以上分析，在wait操作中，增加了一個“AND”條件，故稱為AND同步，或稱為同時wait操作，即Swait(Simultaneouswait)。教材：p34 2.4.3信號量機制4信號量集(1)信號量集的必要性在記錄型信號量機制中wait(s)或signal(s)操作僅能對信號量實施加1或減1操作，意味著每次只能獲得或釋放一個單位的臨界資源。而當一次需要N個某類臨界資源時，需要進行N次wait(s)操作。顯然這很低效。此外，在有些情況下當資源數(shù)量低于某一閾值時，不予分配，因此在每次分配時要測試該資源的數(shù)量，是否大于閾值。基于上述兩點，對AND信號量加以擴展，形成一般化的“信號量集”機制。 2.4.3信號量機制4信號量集(2)信號量集機制的形式化描述swait(Si,ti,di)變量描述：Si：可用資源數(shù)；ti：閾值；di：申請資源數(shù)。教材：p35 2.4.3信號量機制2.4.3信號量機制表2-1信號量機制比較

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

PCM為使生產(chǎn)者進程和消費者進程并發(fā)進行，在它們之間設置了一個具有多個緩沖區(qū)的緩沖池，生產(chǎn)者進程可以將其所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中，消費者進程可以從一個緩沖區(qū)中取得產(chǎn)品去消費。盡管所有的生產(chǎn)者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即不允許消費者進程從空緩沖區(qū)中取產(chǎn)品；也不允許生產(chǎn)者進程向滿緩沖區(qū)中放產(chǎn)品。由于生產(chǎn)者—消費者問題是相互合作的進程關系的一種抽象，因此，該問題有很大的代表性及實用價值。生產(chǎn)者—消費者問題即theProducer-ConsumerProblem，簡稱PC問題。 1問題描述我們可利用一個數(shù)組來表示上述的具有n個(0，1，…，n-1)緩沖單元的緩沖區(qū)。用輸入指針in作寫指針，每當生產(chǎn)者進程生產(chǎn)并投放一個產(chǎn)品后，輸入指針加1；用一個輸出指針out作讀指針，每當消費者進程取走一個產(chǎn)品后，輸出指針加1。由于緩沖區(qū)通常被組織成循環(huán)隊列，故應把寫指針加1表示成in：=(in+1)modn；讀指針加1表示成out：=(out+1)modn。當(in+1)modn=out時表示緩沖區(qū)滿；而in=out則表示緩沖區(qū)空。此外，還引入了一個整型變量counter,其初始值為0。每當生產(chǎn)者進程向緩沖區(qū)中投放一個產(chǎn)品后，使counter加1；反之，每當消費者進程從中取走一個產(chǎn)品時，使counter減1。 2問題分析生產(chǎ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問題設生產(chǎn)者和消費者之間的公用緩沖區(qū)有n個緩沖單元。利用互斥信號量mutex實現(xiàn)諸進程對緩沖區(qū)的互斥訪問；信號量empty表示緩沖區(qū)中空緩沖單元的個數(shù)，F(xiàn)ull表示滿緩沖區(qū)中產(chǎn)品的個數(shù)。這些生產(chǎn)者和消費者之間存在同步關系，只要緩沖區(qū)未滿，生產(chǎn)者便可將數(shù)據(jù)寫入緩沖區(qū)；只要緩沖區(qū)未空，消費者便可從緩沖區(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問題首先，在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)；其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在生產(chǎn)者進程中，而signal(empty)則在消費者進程中，生產(chǎn)者進程若因執(zhí)行wait(empty)而阻塞，以后將由消費者進程通過執(zhí)行Signal(empty)將它喚醒；最后，在每個程序中的多個wait操作順序不能顛倒。應先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進程死鎖。 PC問題注意事項

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ù)對象，可以被多個進程共享。其中有些進程要求讀，這些進程叫做讀進程；而另一些進程要求寫或修改，這些進程叫寫進程。

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

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

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

2利用記錄型信號量解決讀者-寫者問題//以下為離開讀書室wait(rmutex);//互斥地通過門禁，離開讀書室readcount=readcount-1;//最后1個讀者離開讀書室時需要關閉禁止寫者進入的信號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利用信號量集機制解決讀者-寫者問題Voidwriter(){dowhile(true){Swait(mx,1,1;0,L,0);performwriteoperation;Ssignal(mx,1);}}【實例2-5】

（a）b）圖2-6

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

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