操作系統(tǒng)課件第2章 進程管理

第二章進程管理

教學內(nèi)容

2.1進程的引入2.2進程的描述

2.3進程控制

2.4進程的同步與互斥

2.5信號量機制

2.6進程同步問題舉例

2.7管程

2.8進程的高級通信

2.9信號通信機制

2.10線程

22.1進程的引入

2.1.1程序的順序執(zhí)行1．程序的順序執(zhí)行

程序是人們要計算機完成特定功能的一些指令序列，是一個按嚴格次序、順序執(zhí)行的操作序列，是一個靜態(tài)的概念。我們把一個具有獨立功能的程序獨占處理機，直到最后結(jié)束的過程稱為程序的順序執(zhí)行。如：有一個程序，要求先輸入數(shù)據(jù)，再做相應的計算，最后輸出結(jié)果并用打印機打印。分別用I、C、P代表以上3個程序段，這樣，上述3個程序段的執(zhí)行順序為：

I→C→P。

32.1進程的引入

2．程序順序執(zhí)行時的特征（1）順序性。處理機的操作嚴格按照程序所規(guī)定的順序執(zhí)行，即只有前一個程序段完成才執(zhí)行下一個程序段，上一條指令完成再去執(zhí)行下一條指令。（2）封閉性。程序是在封閉環(huán)境下運行的。程序運行時獨占全機資源，資源的狀態(tài)除初始狀態(tài)外，只有該程序本身才能改變它。程序執(zhí)行的最終結(jié)果由給定的初始條件決定，不受外界因素的影響。（3）可再現(xiàn)性。順序執(zhí)行的最終結(jié)果可再現(xiàn)。也就是說它與執(zhí)行速度及執(zhí)行的時刻無關(guān)，只要輸入的初始條件相同，無論何時重復執(zhí)行該程序，結(jié)果都是相同的。42.1.2程序的并發(fā)執(zhí)行及其特征1．并發(fā)執(zhí)行的概念

所謂程序的并發(fā)性，是指多道程序在同一時間間隔內(nèi)同時發(fā)生。程序的并發(fā)執(zhí)行可總結(jié)為：一組在邏輯上互相獨立的程序或程序段在執(zhí)行過程中，其執(zhí)行時間在客觀上互相重疊，即一個程序段的執(zhí)行尚未結(jié)束，另一個程序段的執(zhí)行已經(jīng)開始的一種執(zhí)行方式。5C12．程序并發(fā)執(zhí)行時的特征（1）間斷性程序在并發(fā)執(zhí)行時，由于它們共享系統(tǒng)資源，以及為完成同一項任務而相互合作，致使這些并發(fā)執(zhí)行的程序之間，形成了相互制約的關(guān)系。相互制約將導致并發(fā)程序具有“執(zhí)行——暫?！獔?zhí)行”這種間斷性的活動規(guī)律。6I1I2I3C1C2C3P1P2P3I4C4圖2-2程序的并發(fā)執(zhí)行I1I2I3C2C3P1P2P3I4C4（2）失去封閉性程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個運行的程序來改變，致使程序的運行失去了封閉性。例如，當處理機被某個程序占有時，另一程序必須等待。（3）不可再現(xiàn)性

在并發(fā)環(huán)境下，同一個程序執(zhí)行多次，執(zhí)行的結(jié)果可能不同。例如，有兩個循環(huán)程序A和B，它們共享一個變量N，初值為0。程序A（）：程序B（）：{do{doN=N+1;print(N);While(1)While(1)}}

程序A和程序B以不同的速度運行，出現(xiàn)的結(jié)果可能不同。例如，當程序A和程序B運行的速度相近時，打印的結(jié)果為1、2、3、…；而當程序A的執(zhí)行速度是程序B的2倍時，打印的結(jié)果可能是2、4、6…。7引入進程的意義

從上例來看，程序在并發(fā)執(zhí)行時，由于失去了封閉性，其計算結(jié)果與并發(fā)程序的執(zhí)行速度有關(guān)，從而使程序失去了可再現(xiàn)性，程序經(jīng)過多次執(zhí)行后，雖然執(zhí)行時的環(huán)境和初始條件相同，但得到的結(jié)果卻各不相同。所以，從上面的討論看，由于程序的順序性、間斷性和不可再現(xiàn)性，用程序作為描述其執(zhí)行過程以及共享資源的基本單位是不合適的。這就需要一個既能描述程序的執(zhí)行過程，又能用來共享資源的基本單位，這個基本單位被稱為進程。82.1.3進程的定義與特征1．進程的定義進程是操作系統(tǒng)中最基本、最重要的概念之一。人們對進程下過許多定義?，F(xiàn)列舉其中的幾種：（1）進程是程序的一次執(zhí)行。（2）進程是可以和別的進程并發(fā)執(zhí)行的計算。（3）進程就是一個程序在給定活動空間和初始條件下，在一個處理機上的執(zhí)行過程。（4）進程是程序在一個數(shù)據(jù)集合上的運行過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。（5）進程是動態(tài)的，有生命周期的活動。內(nèi)核可以創(chuàng)建一個進程，最終將由內(nèi)核終止該進程使其消亡。綜上觀點定義為：“并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的執(zhí)行過程”【運行著的程序】9進程和程序之間的關(guān)系

進程和程序是兩個完全不同的概念，但又有密切的聯(lián)系。程序是規(guī)定的工作流程，進程則是實際的工作過程。它們之間的主要區(qū)別是：（1）程序是靜態(tài)的概念，而進程則是程序的一次執(zhí)行過程。它是動態(tài)的概念。（2）進程是一個能獨立運行的單位，能與其它進程并發(fā)執(zhí)行；而程序是不能作為一個獨立運行的單位而并發(fā)執(zhí)行的。（3）程序和進程無一一對應的關(guān)系。（4）各個進程在并發(fā)執(zhí)行過程中會產(chǎn)生相互制約關(guān)系，而程序本身是靜態(tài)的，不存在這種異步特征。102．進程的特征從進程與程序的區(qū)別可以看出，進程具有如下特征：（1）動態(tài)性動態(tài)性是進程最基本的特性。進程由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，因得不到資源而暫停執(zhí)行，以及因撤消而消亡。（2）并發(fā)性這是指多個進程實體，同存于內(nèi)存中，能在一段時間段內(nèi)同時執(zhí)行。并發(fā)性是進程的重要特征，同時也是操作系統(tǒng)的重要特征。提高并發(fā)性，可以提高系統(tǒng)的效率。（3）獨立性進程是一個能獨立運行的基本單位，同時也是系統(tǒng)中獨立獲得資源和獨立調(diào)度的基本單位。（4）異步性這是指進程按各自獨立的、不可預知的速度向前推進；或者說，進程按異步方式運行。（5）結(jié)構(gòu)特征從結(jié)構(gòu)上看，進程實體是由程序段、數(shù)據(jù)段及進程控制塊三部分組成，也稱這三部分為進程映像。11條件外部條件CPU運行滿足滿足不運行阻塞

就緒

滿足2.1.4進程的基本狀態(tài)及轉(zhuǎn)換2.1.4進程的基本狀態(tài)及轉(zhuǎn)換

進程的動態(tài)性由它的狀態(tài)及狀態(tài)轉(zhuǎn)換來體現(xiàn)的。1．進程的三個基本狀態(tài)

進程通常至少有三種基本狀態(tài)：（1）就緒狀態(tài)（ready）進程運行所需的外部條件滿足，但因為其它進程已占用CPU，所以暫時不能運行。（2）執(zhí)行狀態(tài)(running)

外部條件滿足，進程已獲得CPU，其程序正在執(zhí)行。在單處理機系統(tǒng)中，只有一個進程處于執(zhí)行狀態(tài)。（3）阻塞狀態(tài)(blocked)

進程因資源無法滿足而等待資源，暫時不能運行的狀態(tài)，稱為阻塞狀態(tài)，也稱為等待狀態(tài)。系統(tǒng)中處于阻塞狀態(tài)的進程可能有多個，通常將它們排成一個隊列，也有的系統(tǒng)則根據(jù)阻塞原因的不同將這些進程排成多個隊列。132．進程狀態(tài)的轉(zhuǎn)換就緒==》執(zhí)行

對于處于就緒狀態(tài)的進程，在調(diào)度程序為之分配了處理機之后，該進程便可執(zhí)行。相應地，它由就緒狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行狀態(tài)。執(zhí)行==》就緒

正在執(zhí)行的進程（執(zhí)行狀態(tài)）也稱為當前進程，如果因分配給它的時間片已用完而被暫停執(zhí)行時，該進程便由執(zhí)行狀態(tài)又回到就緒狀態(tài)；執(zhí)行==》阻塞

一個處在執(zhí)行狀態(tài)的進程，如果因等待資源而使進程的執(zhí)行受阻，使之無法繼續(xù)執(zhí)行，該進程將由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。阻塞==》就緒

一個處于阻塞狀態(tài)的進程，當它所需的外部事件滿足，它應由阻塞狀態(tài)變?yōu)榫途w狀態(tài)。14進程創(chuàng)建資源滿足如I/O請求滿足就緒狀態(tài)阻塞狀態(tài)執(zhí)行狀態(tài)結(jié)束進程等待資源如I/O請求執(zhí)行完或撤銷

進程基本狀態(tài)轉(zhuǎn)換圖PCB3．引入掛起狀態(tài)時的進程狀態(tài)掛起激活

除了上述3種基本狀態(tài)以外，很多系統(tǒng)中又引入了掛起狀態(tài)。

所謂掛起狀態(tài)，實際上就是一種靜止的狀態(tài)。一個進程被掛起后，不管它是否在就緒狀態(tài)，系統(tǒng)都不分配給它處理機。

處于掛起狀態(tài)的進程要想重新進入到活動狀態(tài)，必須被激活（即轉(zhuǎn)換為活動狀態(tài)），然后才有可能執(zhí)行。因此在引入掛起狀態(tài)后，進程之間的狀態(tài)轉(zhuǎn)換除了四種基本狀態(tài)轉(zhuǎn)換以外，又增加了以下幾種：（1）活動就緒—掛起—靜止就緒。（2）活動阻塞—掛起—靜止阻塞。（3）靜止就緒—激活—活動就緒。（4）靜止阻塞—激活—活動阻塞。16執(zhí)行外部事件滿足外掛起激活掛起掛激活活動就緒靜止就緒活動阻塞靜止阻塞調(diào)度圖2-2具有掛起狀態(tài)的進程狀態(tài)轉(zhuǎn)換等部事件外待起部條件滿足完成或撤消172.1.5Linux進程的狀態(tài)

Linux系統(tǒng)的一個任務總體上有以下幾種狀態(tài)：（1）TASK-RUNNING狀態(tài)

:執(zhí)行和就緒兩種狀態(tài)（2）TASK-INTERRUPTIBLE狀態(tài):可中斷的等待狀態(tài)。

（3）TASK-UNINTERRUPTIBLE狀態(tài):不可中斷等待狀態(tài)。

（4）TASK-ZOMBIE狀態(tài)，僵死狀態(tài)。由于某些原因進程被終止，這個進程所占有的資源全部釋放之后，還保存著PCB信息，這種占有PCB但已被撤消的進程就處于僵死狀態(tài)。（5）TASK-STOPPED狀態(tài)，暫停狀態(tài)。

18P12.2進程的描述

進程的活動是通過在CPU上執(zhí)行一系列程序和對相應數(shù)據(jù)進行操作來體現(xiàn)的。程序和操作的數(shù)據(jù)是進程存在的實體。程序和數(shù)據(jù)是靜態(tài)的，無法反映出其動態(tài)性，還需要一個數(shù)據(jù)結(jié)構(gòu)來描述進程的動態(tài)性（當前的狀態(tài)、本身的特性等）。這種數(shù)據(jù)結(jié)構(gòu)稱為進程控制塊PCB

（ProcessControlBlock）。所以，進程實體通常是由程序、數(shù)據(jù)集合和進程控制塊PCB這三部分構(gòu)成，也稱為“進程映象”。進程控制塊PCB程序部分數(shù)據(jù)集合20圖2-4進程的一般組成模型2.2.1進程控制塊PCB

PCB集中反映一個進程的動態(tài)特征，當系統(tǒng)創(chuàng)建了一個新進程時，就為它建立一個PCB；當進程終止后，系統(tǒng)回收其PCB，該進程在系統(tǒng)中就不存在了。所以，PCB是進程存在的惟一標志?？梢园凑展δ軐CB分成四個組成部分：

進程標識符

處理機狀態(tài)

進程調(diào)度信息

進程控制信息。211．進程標識符進程標識符用于惟一地標識一個進程。一個進程通常有兩種標識符：進程內(nèi)部標識符。進程外部標識符。（1）進程內(nèi)部標識符。在所有的操作系統(tǒng)中，為每一個進程賦予一個惟一的數(shù)字標識符，它通常是一個進程的序號。設置內(nèi)部標識符主要是為了方便系統(tǒng)使用。（2）進程外部標識符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往由用戶（進程）在訪問該進程時使用。為了描述進程的家族關(guān)系，還應設置父進程標識及子進程標識。222．處理機狀態(tài)：

處理機狀態(tài)信息主要由處理機的各種寄存器中的內(nèi)容組成。處理機在運行時，許多信息都放在寄存器中。當處理機被中斷時，這些信息都必須保存在PCB中，以便在該進程重新執(zhí)行時能從斷點繼續(xù)執(zhí)行。處理機的寄存器包括通用寄存器、指令計數(shù)器、程序狀態(tài)字PSW、用戶棧指針。233．進程調(diào)度信息

PCB中還存放一些與進程調(diào)度和進程對換有關(guān)的信息。（1）進程狀態(tài)。

指明進程當前的狀態(tài)，作為進程調(diào)度和對換的依據(jù)。（2）進程優(yōu)先級。

進程使用處理機的優(yōu)先級別的整數(shù)，優(yōu)先級高的進程應優(yōu)先獲得CPU。（3）進程調(diào)度所需要的其它信息。

與所采用的進程調(diào)度算法有關(guān)，如進程已等待CPU的時間、進程已運行的時間等。

（4）事件或阻塞原因。指進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所需要等待發(fā)生的事件。

244．進程控制信息

進程控制信息包括：（1）程序和數(shù)據(jù)的地址:

進程的程序和數(shù)據(jù)所在的內(nèi)存或外存地址，以便再調(diào)度到該進程執(zhí)行時，能從PCB中找到其程序和數(shù)據(jù)。（2）進程同步和通信機制:

實現(xiàn)進程同步和進程通信時必需的機制，如消息隊列指針、信號量等，它們可能全部或部分地放在PCB中。

（3）資源清單:

是一張列出了除CPU以外、進程所需的全部資源及已經(jīng)分配到該進程的資源清單。（4）鏈接指針:

本進程PCB所在隊列的下一個進程PCB的首地址。

252.2.2進程控制塊的組織方式各進程的PCB有如下幾種組織方式：

線性方式鏈接方式索引方式。1．線性方式將各進程的PCB依次放入一個表中，結(jié)構(gòu)如下圖所示。PCB1PCB2PCB3……PCBn-1PCBn26優(yōu)點：線性方式最簡單、最容易實現(xiàn)。缺點：限定了系統(tǒng)中同時存在的進程的最大數(shù)目；

為選擇合理的進程投入運行，經(jīng)常要對整個表進行掃描，降低了調(diào)度效率。

2．鏈接方式

鏈接方式是經(jīng)常采用的方式。其原理是：按照進程的不同狀態(tài)分別將其放在不同的隊列。Linux操作系統(tǒng)就是應用這種進程控制塊組織方式。就緒隊列指針PCBPCBPCB0運行隊列指針PCB0阻塞隊列1指針PCBPCBPCB0PCB阻塞隊列2指針PCBPCB0273．索引方式系統(tǒng)根據(jù)所有進程的狀態(tài)建立幾張索引表。如就緒索引表、阻塞索引表等。并把各索引表在內(nèi)存的首地址記錄在內(nèi)存的一些專用單元中。在每個索引表的表目中，記錄具有相應狀態(tài)的某個PCB在PCB表中的地址。阻塞索引表就緒索引表執(zhí)行指針就緒表指針阻塞表指針PCB1PCB2PCB3PCB4PCB5PCB6PCB7圖2-7PCB索引結(jié)構(gòu)示意圖282.2.3Linux進程的PCB

Linux系統(tǒng)中的進程稱為任務。該系統(tǒng)的進程控制塊PCB用一個稱為task-struct的結(jié)構(gòu)體來描述，Linux系統(tǒng)PCB包含以下信息：1．進程描述信息（1）進程標識號（pid，processidentifier）（2）用戶和組標識（userandgroupidentifier）（3）連接信息（Links）2．進程控制信息（1）進程當前狀態(tài)（2）調(diào)度信息（3）記時信息（4）通信信息293．進程資源信息

記錄了與該進程有關(guān)的存儲器的各種地址和資料、文件系統(tǒng)以及打開文件的信息等等。4．CPU現(xiàn)場信息

每個進程運行時都要使用處理器的寄存器以及堆棧等資源。當一個進程被掛起時，所有有關(guān)處理處理器的內(nèi)容都要保存到task_struct結(jié)構(gòu)中。當進程恢復運行時，所有保存的內(nèi)容再裝入到處理器中。302.3進程控制

進程和處理機管理的一個重要任務是進程控制。

所謂進程控制，就是系統(tǒng)使用具有特定功能的程序段來創(chuàng)建、撤消進程以及完成進程各狀態(tài)間的轉(zhuǎn)換，從而達到多進程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實現(xiàn)資源共享的目的。

系統(tǒng)在運行時分為兩種狀態(tài)：即核心態(tài)和用戶態(tài)。核心態(tài)也叫系統(tǒng)態(tài)或管態(tài)，是指CPU在運行操作系統(tǒng)的核心模塊；用戶態(tài)也稱用態(tài)，是指CPU正在運行用戶的程序。31

原語的概念：把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語，原語的特點是不可被中斷。

系統(tǒng)在創(chuàng)建、撤消一個進程以及要改變進程的狀態(tài)時，都要調(diào)用相應的程序段來完成這些功能。用于進程控制的原語有創(chuàng)建原語、撤消原語、阻塞原語和喚醒原語等。陷入用戶態(tài)核心態(tài)2.3.1進程的家族關(guān)系

操作系統(tǒng)通過內(nèi)核原語來實現(xiàn)進程控制。在系統(tǒng)初始化完成后，系統(tǒng)就可創(chuàng)建進程。

創(chuàng)建者稱為父進程，被創(chuàng)建的新進程稱為子進程，子進程又可以創(chuàng)建自己的子進程，從而形成一棵有向的進程家族樹。

子進程與父進程之間的關(guān)系:

子進程的許多屬性都是從父進程繼承來的，子進程與父進程的區(qū)別是形成自己獨立的屬性。子進程可以從父進程繼承的屬性包括：用戶標識符、環(huán)境變量、打開文件、文件系統(tǒng)的當前目錄、已經(jīng)連接的共享存儲區(qū)和信號處理處理例程入口表等。子進程不能從父進程繼承的屬性包括：進程標識符和父進程標識符等。進程創(chuàng)建資源滿足如I/O請求滿足就緒狀態(tài)阻塞狀態(tài)執(zhí)行狀態(tài)結(jié)束進程等待資源如I/O請求執(zhí)行完或撤銷2.3.2進程的創(chuàng)建與終止1．進程的創(chuàng)建fork.c

在多道程序環(huán)境下，為使程序運行，必須為他創(chuàng)建進程。系統(tǒng)發(fā)現(xiàn)要求創(chuàng)建進程的事件請求后，便通過調(diào)用創(chuàng)建原語Creat()創(chuàng)建進程。其步驟如下：（1）申請空白PCB。為新進程申請獲得惟一的進程標識符，并從PCB集合中索取一個空白PCB。（2）為新進程分配資源。包括新創(chuàng)建進程的程序、數(shù)據(jù)及用戶棧所需的內(nèi)存空間。（3）初始化進程控制塊。初始化標識信息，如進程標識符；處理機狀態(tài)信息，使程序計數(shù)器指向程序的入口地址，使棧指針指向棧頂；處理機控制信息，將新建進程的狀態(tài)設置為就緒狀態(tài)（活動就緒或靜止就緒狀態(tài)）；進程的優(yōu)先級等。（4）將新建進程插入就緒態(tài)隊列。352.3.2進程的創(chuàng)建與終止2．進程的終止過程

系統(tǒng)檢測到要求進程終止事件，操作系統(tǒng)調(diào)用進程終止原語，終止本進程的執(zhí)行。操作過程如下：（1）根據(jù)被終止進程的標識符，從PCB隊列中檢索出該進程的PCB，從中讀出該進程的狀態(tài)。（2）若被終止進程正處于執(zhí)行狀態(tài)，應立即終止該進程的執(zhí)行，該進程被終止后應重新進行進程調(diào)度。（3）檢查該進程有無子孫進程，若有，則應將其所有子孫進程終止。（4）釋放終止的進程所占有的資源，將其歸還它的父進程或者系統(tǒng)。（5）將被終止的進程從它的PCB隊列中移出。362.3.3進程的阻塞與喚醒

進程狀態(tài)的轉(zhuǎn)換需要通過進程之間的同步或通信機構(gòu)來實現(xiàn)，也可直接使用“阻塞原語”和“喚醒原語”來實現(xiàn)。

阻塞原語在一個進程期待某一事件發(fā)生，但發(fā)生條件還不滿足時，被該進程自己調(diào)用來阻塞自己，并轉(zhuǎn)換為等待狀態(tài)。

當?shù)却犃兄械倪M程所等待的事件發(fā)生時，等待該事件的進程都將被喚醒。喚醒一個進程有兩種方法，一種是由系統(tǒng)進程喚醒，另一種是由事件發(fā)生進程喚醒。

37

實現(xiàn)進程的執(zhí)行狀態(tài)到阻塞狀態(tài)的原語為阻塞原語；由阻塞狀態(tài)到就緒狀態(tài)轉(zhuǎn)換的原語分為喚醒原語

。入口保存該進程的CPU現(xiàn)場字置該進程的狀態(tài)為阻塞阻塞進程PCB進入等待隊列轉(zhuǎn)到進程調(diào)度入口從等待隊列取被喚醒進程將被喚醒進程置為就緒態(tài)被喚醒進程插入就緒隊列轉(zhuǎn)到進程調(diào)度或返回阻塞原語喚醒原語就緒--

運行運行

就緒進程創(chuàng)建資源滿足如I/O請求滿足就緒狀態(tài)阻塞狀態(tài)執(zhí)行狀態(tài)結(jié)束進程等待資源如I/O請求執(zhí)行完或撤銷2.3.4Linux系統(tǒng)調(diào)用

在Linux系統(tǒng)中，系統(tǒng)向用戶提供了一些對進程進行控制的系統(tǒng)調(diào)用。常用的有：1．fork()系統(tǒng)調(diào)用

fork.c

Linux利用fork()系統(tǒng)調(diào)用創(chuàng)建一個新進程。

fork()系統(tǒng)調(diào)用的格式是：

intfork()；

通常情況下，設返回值為intpid，調(diào)用格式為：pid=fork();fork()是通過復制來創(chuàng)建子進程的，子進程繼承父進程的上下文，是父進程的一個副本，與父進程使用同一段代碼。在該系統(tǒng)調(diào)用之后，兩個代碼相同的進程并發(fā)執(zhí)行。

fork系統(tǒng)調(diào)出錯可能基于以下兩方面的原因：一是當前進程數(shù)量已達到系統(tǒng)規(guī)定的最大值，二是系統(tǒng)內(nèi)存不足。40通常情況下，設返回值為intpid，調(diào)用格式為：pid=fork();其中，返回值pid意義如下：pid=0：創(chuàng)建子進程成功，表示從子進程返回，即

CPU正在運行該子進程。pid>0：創(chuàng)建子進程成功，表示從父進程返回，

pid的值為新創(chuàng)建的子進程標識號。pid=-1：創(chuàng)建失敗。用進程的家族關(guān)系main(){fork();fork();fork();printf(“S”);}SSSSSSSSacb例：編寫一段程序，使用系統(tǒng)調(diào)用fork()創(chuàng)建兩個子進程。當此程序運行時，在系統(tǒng)中有一個父進程和兩個子進程活動。讓每一個進程在屏幕上顯示一個字符：父進程顯示字符“a”，子進程分別顯示字符“b”和“c”。試觀察記錄屏幕上的顯示結(jié)果，并分析原因。acbmain(){intp1,p2;while((p1=fork())==-1);if(p1==0){printf(“%c”,”b”);exit();}else{while((p2=fork())==-1);if(p2==0){printf(“%c”,”c”);exit();}else(printf(“%c”,”a”);wait();wait();exit();}}}abcabccbaP2P1P2.3.4Linux系統(tǒng)調(diào)用

2．Exec系統(tǒng)調(diào)用利用exec系統(tǒng)調(diào)用執(zhí)行另一個程序。在Linux系統(tǒng)中，當由fork()系統(tǒng)調(diào)用創(chuàng)建一個子進程后，可再利用exec()系統(tǒng)調(diào)用執(zhí)行另一個程序。3．exit()系統(tǒng)調(diào)用對于一般的用戶進程，在其任務完成后應被盡快撤消。

Linux系統(tǒng)用exit()系統(tǒng)調(diào)用來實現(xiàn)進程的自我終止。通常，父進程在創(chuàng)建子進程時，應在進程的末尾寫一條exit()，使子進程自我終止。4．wait系統(tǒng)調(diào)用將調(diào)用進程掛起，直至其子進程因暫?；蚪K止而發(fā)來軟中斷信號為止。45#include<stdio.h>main(){intp1,p2;while((p1=fork())==-1);/*創(chuàng)建進程p1，創(chuàng)建成功后退出*/if(p1==0)/*CPU運行P1*/{putchar(‘b’);exit();}else{while((p2=fork())==-1);/*創(chuàng)建子進程p2，創(chuàng)建成功后退出*/if(p2==0){putchar(‘c’);exit();}else{putchar(‘a(chǎn)’);wait();wait();exit();}/*父進程執(zhí)行*/}}abc2.4進程的同步與互斥

進程的并發(fā)提高了系統(tǒng)效率，也同時導致了資源的競爭與共享。必須控制好進程的同步與互斥。2.4.1臨界資源的概念1．臨界資源

兩個或兩個以上的進程不能同時使用的資源為臨界資源。

臨界資源可能是一些獨占設備，如打印機、磁帶機等；也可能是一些共享變量、表格、鏈表等。47一個飛機訂票系統(tǒng)有兩個終端T1和T2，執(zhí)行下面的并發(fā)進程:

intn; /*系統(tǒng)中剩余票的數(shù)量，若n>0則可賣票*/voidmain(){intn=100;parbegin(T1,T2);}并發(fā)進程T2的執(zhí)行序列如下：

（2）進程T2的定義

voidT2(){do{read(n);if(n>=1){賣一張票；

n:=n-1;write(n);}}while(true);}}并發(fā)進程T1的執(zhí)行序列如下：（1）進程T1的定義

voidT1(){do{read(n);if（n>=1）

{賣一張票；n:=n-1;write(n);}while(true);}}共享變量n就是本程序的臨界資源！2．臨界區(qū)

不論硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地訪問臨界資源。臨界區(qū):

每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。進入?yún)^(qū):

在臨界區(qū)前面增加一段用于進行檢查是否正被其他進程訪問的的代碼，把這段代碼稱為進入?yún)^(qū)，進入?yún)^(qū)設置訪問標志；退出區(qū):

在臨界區(qū)后面再加一段用于退出臨界區(qū)的代碼，稱為退出區(qū)，退出區(qū)取消訪問標志。剩余區(qū):

進程中除去上述各區(qū)外，其它部分的代碼，稱為剩余區(qū)。49進入;----互斥臨界區(qū)退出;----同步2．臨界區(qū)因此，一個訪問臨界資源的進程描述如下：repeat

進入?yún)^(qū)；檢查是否有進程使用臨界資源，有則阻塞自己，無則設置標志臨界區(qū)；使用臨界資源

退出區(qū)；使用完臨界資源后釋放臨界資源，設置未使用標志，其他進程使用剩余區(qū)；其他代碼untilfalse;512.4.2

進程的互斥與同步1．同步與互斥的概念

進程互斥是指多個進程不能同時使用同一個臨界資源CR，即兩個或兩個以上進程必須互斥地使用臨界資源，或不能同時進入臨界區(qū)CS。

兩個邏輯上完全獨立、毫無關(guān)系的進程，由于競爭同一個資源而相互制約，就稱為進程的互斥。

如系統(tǒng)只有一臺打印機，兩個進程都要使用。為了保證打印結(jié)果的正確和方便使用，只能一個進程用完打印機后，另一個進程才能使用。

進程同步，是指有協(xié)作關(guān)系的進程之間，要不斷地調(diào)整它們之間的相對速度或執(zhí)行過程，以保證臨界資源的合理利用和進程的順利執(zhí)行。實現(xiàn)進程同步的機制稱為進程同步機制。如兩個進程合作使用同一個緩沖區(qū)。設進程A負責往緩沖區(qū)中輸入數(shù)據(jù)，進程B負責從同一緩沖區(qū)中輸出數(shù)據(jù)。當進程A將數(shù)據(jù)輸滿緩沖區(qū)，則只有當進程B將該數(shù)據(jù)讀出后，進程A才能繼續(xù)使用該緩沖區(qū)，否則將造成數(shù)據(jù)丟失。此時，進程A和進程B之間就形成了同步關(guān)系。532．同步機制應遵循的規(guī)則為實現(xiàn)進程互斥地進入自己的臨界區(qū)，所有同步機制都應遵循下列準則：（1）空閑讓進：并發(fā)進程中某個進程不在臨界區(qū)時，不阻止其他進程進入臨界區(qū)。（2）忙則等待：并發(fā)進程中的若干個進程申請進入臨界區(qū)時，只允許一個進程進入。當已有進程進入臨界區(qū)時，其他申請進入臨界區(qū)的進程必須等待，以保證對臨界資源的互斥訪問。（3）有限等待：

保證等待有限時間，不能無限期等待，陷入“等死”狀態(tài)。（4）讓權(quán)等待：當進程不能進入自己的臨界區(qū)時，應立即釋放處理機，以免進程陷入“忙等”狀態(tài)。54實現(xiàn)同步互斥的方法硬件方法軟件方法2.4.3實現(xiàn)進程同步的軟件方法

1981年，G.L.Peterson提出了一個簡單的算法來解決進程互斥進入臨界區(qū)的問題。這種方法描述為：為每個進程設置一個標志，當標志值為true時，表示此進程要求進入臨界區(qū)，另外，再設置一個指示器turn，用來標識由哪個進程可以進入臨界區(qū)，即當turn=＝i時，表示進程pi可以進入臨界區(qū)。以下是Peterson算法的描述。56bolinside[2]={false,false};eum[0,1]turn;cobegin

processP0(){inside[0]=true;turn=1;while(inside[1]&&turn==1);

臨界區(qū)；

iside[0]=false;}processP1(){inde[1]=true;turn=0while(inside[0]&&turn==1);

臨界區(qū)；

iside[1]=false;}coend2.4.4實現(xiàn)進程同步的硬件機制許多計算機已經(jīng)提供了一些特殊的硬件指令，允許對一個字中的內(nèi)容進行檢測和修改正，或者是對兩個字的內(nèi)容進行交換等?？衫眠@些特殊的指令來解決臨界區(qū)問題。下面是實現(xiàn)對臨界區(qū)管理的硬件方法。1．關(guān)中斷

實現(xiàn)互斥最簡單的方法是在進程進入臨界區(qū)時關(guān)中斷，進程退出臨界區(qū)時開中斷。中斷被關(guān)后，時鐘中斷也被屏蔽，進程上下文切換都是由中斷事件引起的，這樣進程的執(zhí)行就不會被打斷，因此采用關(guān)中斷、開中斷的方法就可確保并發(fā)進程互斥地進入臨界區(qū)。2．測試并設置指令使用硬件所提供的“測試并設置”機器指令TS(TestandSet)，實現(xiàn)進程之間的互斥。該指令是一條原語，需獨立執(zhí)行，可把這條指令看作函數(shù)，它的返回值和參數(shù)都是布爾類型。當TS(&x)測到x值為true時，置x=false，且根據(jù)所測試到的x值形成條件碼。3．對換指令對換指令swap用于交換兩個字的內(nèi)容。2.5信號量機制2.5.1信號量的概念信號量（Semaphore），也叫做信號燈，它是在信號量同步機制中用于實現(xiàn)進程的同步和互斥的有效數(shù)據(jù)結(jié)構(gòu)。

可以為每類資源設置一個信號量。

它有多種類型的數(shù)據(jù)結(jié)構(gòu)，即：整型信號量、記錄型信號量、ＡＮＤ型信號量及信號量集等。

申請和釋放臨界資源的兩個原語操作：

P操作--wait操作；進入?yún)^(qū)

V操作--signal操作；退出區(qū)

P、V操作的操作對象是信號量61semaphores1=2,s2=3;AND型信號量

P(S1,S2);P(S1);P(S2);V(S1,S2);V(S1);V(S2);信號量集

P(S1,T1,D1;S2,T2,D2);P(S1,2,1;S2,3,2;S3,1,1);P(S1,2,0;S2,3,2);1．整型信號量

整型信號量的數(shù)值表示當前系統(tǒng)中可用的該類臨界資源的數(shù)量。如設置整型信號量s，則s的值意義為：s>0，則s的值表示系統(tǒng)中空閑的該類臨界資源的個數(shù)；s=0，則表示系統(tǒng)中該類臨界資源剛好全部被占用，而且沒有進程在等待該臨界資源；s<0，則s的絕對值表示系統(tǒng)中的進程等待該類臨界資源的個數(shù)；63申請、進入臨界區(qū)Wait(s)【P(S)】互斥

釋放、退出臨界區(qū)Signal(s)【V(s)】同步

P(s)或者Wait(s)：While(s<=0)

進程等待；

s=s-1;注：S表示資源信號量64Signal(s)【V(s)】

s=s+1;注：S表示資源信號量2．記錄型信號量

記錄型信號量的數(shù)據(jù)結(jié)構(gòu)由兩部分構(gòu)成。定義記錄型信號量類型，有如下描述：

structsemaphore{

ints;structPCB*queue;}semaphore；65

定義記錄型信號量Ｓ，則：s的值value表示系統(tǒng)中可用的該類臨界資源的數(shù)量;

queue為進程鏈表指針，指向等待該類資源的PCB隊列是Wati(S)-p(s)s=s-1申請到資源本進程繼續(xù)本進程入阻塞隊列s≥0否轉(zhuǎn)進程調(diào)度

2.5.2信號量的申請與釋放66wait(S){S.value=s.value-1;ifS.value≥0

本進程繼續(xù)；

Else{

將本進程放入阻塞態(tài)隊列；轉(zhuǎn)進程調(diào)度;}}是signal(S)-v(s)s=s+1喚醒一阻塞態(tài)進程s≤0否釋放該類資源本進程繼續(xù)

設變量Ｓ為記錄型信號量:

V(S)、signal（Ｓ）操作的流程如下圖所示：67voidsignal(S){S.value=s.value+1;

ifs≤0then

喚醒指針queue所指的阻塞態(tài)進程；

}2.5.3利用信號量實現(xiàn)進程的同步和互斥

可以用wait(s)和signal(s)操作處理飛機買票問題。對臨界資源n設一互斥信號量S，將原進程T1及T2做如下修改：進程：semaphoreS=1；T1()進程：T2(){{

P(s)；

P(s)；

read(n);read(n);ifn>=1ifn>=1{n:=n-1;{n:=n-1;write(n);write(n);

V(s)；V(s)；賣一張票；｝賣一張票；｝

}}利用P、V操作可以實現(xiàn)進程之間的同步。關(guān)于這類問題的應用有兩種類型：一種是對于臨界資源，在使用之前申請，使用之后釋放，我們給這類資源設一個互斥信號量即可；第二種類型是利用信號量控制進程之間運行的順序，這時需要根據(jù)實際情況設置多于一個信號量，對同一個信號量的P、V操作在不同的進程之間進行。2.6進程同步問題舉例

692.6.1

兩個簡單的例子

例1．系統(tǒng)中有多個進程，共同使用一臺打印機。寫出這些進程并發(fā)執(zhí)行時，同步使用打印機的程序段。70解：同步使用打印機的程序段為：semaphores=1;／＊定義打印機信號量并賦初值＊／voidmain(){parbegin(P1，P2，……,Pn);}Pi()(i=1,2,3,……n){……P(S);

打印，V(S);……}在這個例子中，多個進程隨機使用打印機信號量，使用之前先申請，使用之后釋放該信號量。。2.6.1

兩個簡單的例子

例2．有一個緩沖區(qū)，供多個進程共享。這些進程中有生產(chǎn)者進程和消費者進程。寫出多個進程共同使用同一個緩沖區(qū)時實現(xiàn)進程同步的程序。71緩沖區(qū)用來臨時存放數(shù)據(jù)，在使用緩沖區(qū)時應該注意:對一個緩沖區(qū)，數(shù)據(jù)的寫入和提取應當是交替執(zhí)行的，否則會發(fā)生錯誤：數(shù)據(jù)丟失或數(shù)據(jù)重復。緩沖區(qū)Bufproducerconsumer1024Binout73consumer(){while(1){P(full);P(mutex);從緩沖區(qū)取數(shù)據(jù)；V(empty);V(mutex);……}}{while(1){P(empty);P(mutex);往緩沖區(qū)存放數(shù)據(jù)；V(full);V(mutex);……}}解：同步使用一個緩沖區(qū)的程序段為：semaphoreempty=n,full=0，mutex=1;／＊定義信號量并賦初值＊／

voidmain(){parbegin(producer,consumer);}注意：在該程序中，對同一個信號量的P、V操作是在兩個不同進程之間進行的，這樣可以保證讀進程和寫進程交替使用該緩沖區(qū)。例：P1--P2---P3producer()2.6.1生產(chǎn)者—消費者問題

1．問題的描述

有一批生產(chǎn)者進程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進程去消費。生產(chǎn)者進程與消費者進程能并發(fā)執(zhí)行，在兩者之間設置了一個具有n個緩沖區(qū)的緩沖池.

生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中；消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費。規(guī)定消費者進程不能到一個空緩沖區(qū)中去取產(chǎn)品；生產(chǎn)者進程不能將產(chǎn)品放入一個已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中。74012……i………n-2n-1

用一個數(shù)組表示上述具有n（0，1，…，n-1）個緩沖區(qū)的緩沖池。設一個輸入指針in，表示下一個可存放產(chǎn)品的緩沖區(qū)，每當生產(chǎn)者進程生產(chǎn)一個產(chǎn)品并放入該緩沖區(qū)后，in:=in+1；設一個輸出指針out，表示下一個可從中取得產(chǎn)品的緩沖區(qū)，每當消費者進程從此取走一個產(chǎn)品后，out:=out+1?？紤]此處的緩沖池構(gòu)成了循環(huán)緩沖，故當輸入或輸出指針加1時表示為in:=(in+1)%n；out:=(out+1)%n。當(in+1)%n=out時，表示緩沖池滿；當in=out時則表示緩沖池空。75inout

用整型變量counter表示該緩沖池中滿緩沖區(qū)的個數(shù)，顯然，每當生產(chǎn)者進程向緩沖池中存放一個產(chǎn)品后，counter加1；每當消費者進程從緩沖區(qū)中取走一件產(chǎn)品后，counter減1;

假設初始情況下緩沖池為空，即counter＝０。為在生產(chǎn)者—消費者問題中實現(xiàn)各進程的同步，可設下列信號量：（假設初始情況下沒有進程使用緩沖池，且緩沖池中各緩沖區(qū)都是空的。）

mutex：互斥使用緩沖池信號量，由于初始情況下無進程使用緩沖池，故初值mutex=１；

empty：表示緩沖池中空閑的緩沖區(qū)數(shù)目，由于初始情況下所有緩沖區(qū)為空，故初值empty=n；

full：表示緩沖池中有產(chǎn)品的緩沖區(qū)的數(shù)目，由于初始情況下沒有緩沖區(qū)存放產(chǎn)品，故初值full＝０。76算法及程序：semaphore

mutex=1,empty=n,full=0;

＊定義信號量并賦初值＊／

messagebuffer[n];

intin=0,out=0;

／＊定義存取指針的初始位置＊／

voidmain(){parbegin(proceducer,consumer);}生產(chǎn)者進程voidprocedure(){do{生產(chǎn)一件產(chǎn)品;

…P(mutex);P(empty);將產(chǎn)品放入緩沖區(qū)buffer[in];in=(in+1)%n;

V(mutex);

V(full);

}while(true);}77fullempty消費者進程：voidconsumer(){do{

P(full);

P(mutex);

從緩沖區(qū)buffer[out]中取走一件產(chǎn)品;out=(out+1)%n;

V(mutex);

V(empty);

消費這件產(chǎn)品;}while(true);}78fullempty臨界資源：

緩沖池、空閑區(qū)、存貨區(qū)；對應信號量：

緩沖池==》mutex

空閑區(qū)==》empty

存貨區(qū)==》full信號量初值：mutex=1；

empty=n；

full=0;

79fullempty生產(chǎn)者進程

生產(chǎn)一件產(chǎn)品;

…

P(empty);

P(mutex);

將產(chǎn)品放入緩沖區(qū)

in=(in+1)%n;

V(mutex);

V(full);消費者進程：

P(full);

P(mutex);

從存放緩沖區(qū)中取走一件產(chǎn)品;out=(out+1)%n;

V(mutex);

V(empty);

消費這件產(chǎn)品;

4．在生產(chǎn)者—消費者問題中應注意：

（１）在每個程序中用于實現(xiàn)互斥的P(mutex)和V(mutex)必須成對地出現(xiàn)。（２）對資源信號量empty和full的P和V操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的進程中，這樣保證生產(chǎn)者進程和消費者進程的同步及交替執(zhí)行。（３）在每個進程中，兩個P操作順序不能顛倒，而signal操作的次序是無關(guān)緊要的。802.6.3讀者—寫者問題

1．問題的提出

一文件Ｆ可以被多個并發(fā)進程共享，將這些訪問該文件的分為讀進程和寫進程。試用P、V操作解決各進程間的同步問題。81共享文件F寫進程W讀進程R1讀進程Rn…圖2-13讀者—寫者問題

設讀進程為reader，寫進程為writer。822．問題的分析寫進程WSemaphorewmutex=1;W—W互斥W----R互斥W與所有R互斥intcounter=0;If（第一個)P(wmutex);readfile……If(最后一個）V(wmutex);Reader(){P(rmutex);if(counter==0)P(wmutex);counter++;V(rmutex);讀文件;P(rmutex);counter--;if(counter==0)V(wmutex);V(rmutex);離開;}寫進程W共享文件F讀進程R1讀進程Rn…R---W互斥R---R同時intcounter=0;Semaphorewmutex=1,rmutex=1;Reader(){if(counter==0)P(wmutex);counter++;讀文件;counter--;if(counter==0)V(wmutex);離開;}Reader(){if(counter==0)P(wmutex);counter++;讀文件;counter--;if(counter==0)V(wmutex);離開;}設如下變量及信號量：計數(shù)器:intreadcount=0;（1）臨界資源：共享文件F和整型變量readcount

（2）信號量：共享文件F對應信號量為wmutex；整形變量readcount對應信號量rmutex；

（3）信號量初值：wmutex=1;

rmutex=1。853．算法及程序

讀者—寫者問題可描述如下：intreadcount=0;semaphorermutex=1,wmutex=1;voidmain(){parbegin(reader,writer);}86讀者進程：voidreader(){

P(rmutex);if(readcount==0)P(wmutex);

readcount++;

V(rmutex);

…

進行讀操作;…

P(rmutex);

readcount--;

if(readcount==0)V(wmutex);V(rmutex);}

87寫者進程：voidwriter(){……

P(wmutex);

執(zhí)行寫操作;

V(wmutex);}884．注意事項及提示（1）對于寫進程，共享文件是臨界資源；而對于讀進程，該文件不是臨界資源。（2）整型變量readcount是臨界資源，所以在使用前后要對其信號量rmutex進行P、V操作。南北橋2.6.4哲學家進餐問題1．問題的提出

設有5個哲學家圍坐在一張圓桌前吃飯。桌上有5只筷子，在每人之間放一只。哲學家要吃飯時，只有分別從左、右兩邊都拿到筷子時，才能吃飯。如果筷子已在他人手上，則該哲學家必須等待到他人吃完后才能拿到筷子；任何一個哲學家在自己未拿到兩只筷子吃飯之前，決不放下自己手里的筷子。試描述5位哲學家吃飯的進程。90圖2-14哲學家就餐問題0101semaphorechop=5;Pi(){……

P(chop);P(chop);

吃；

V(chop);

V(chop);}

2．問題分析

放在桌子上的每根筷子是臨界資源，在一段時間內(nèi)只允許一位哲學家使用。

為了實現(xiàn)對筷子的互斥使用，可以為每一只筷子設置一個信號量，由這五個信號量構(gòu)成信號量數(shù)組：semaphorechopstick[5];

設初始條件下，所有哲學家都未吃，故所有信號量均被初始化為1。3．實現(xiàn)方法

假設每一位哲學家拿筷子的方法都是：先拿起左邊的筷子，再拿起右邊的筷子。

925個哲學家就餐問題

臨界資源：5只筷子

信號量：每只筷子一個信號量semaphorechopstick[5]={1,1,1,1,1};

則第i位哲學家的活動可描述為：

93

semaphore

chopstick［5］={1,1,1,1,1};

//5個互斥信號量viodmain(){parbegin(P0(),P1(),P2(),P3(),P4());}94

Pi()/*i=0,1,2,3,4*/{while(1){{P(chopstick［i］);P(chopstick［(i+1)%5］);

eating;

…

V(chopstick［i］);

V(chopstick［(i+1)%5］);

thinking;}}95

Pi()/*i=0,1,2,3,4*/{while(1)

{P(S);

P(chopstick［i);P(chopstick［(i+1)%5］］);}

eating;

…

V(chopstick［i］);

V(chopstick［(i+1)%5］);

V(S);

thinking;}}Semaphores=4;

以上算法存在一個問題：假設5個哲學家同時拿起左邊的筷子，那么再去拿右邊的筷子時，就會產(chǎn)生死鎖。下面給出幾種解決方法。（1）至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。（2）僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。（3）規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學家則相反。最后總會有一位哲學家能獲得兩只筷子而進餐。具體程序段參看實訓教材。974．不產(chǎn)生死鎖的哲學家就餐問題算法補充例題1

某銀行提供1個服務窗口和10個供顧客等待的座位。顧客到達銀行時，若有空座位，則從取號機上取一個號，等待叫號。取號機每次僅允許一個顧客使用。當營業(yè)員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營業(yè)員的活動過程描述如下：顧客進程{從取號機取一個號碼；等待叫號；獲取服務；}營業(yè)員進程{叫號；為客戶服務；}請?zhí)砑颖匾男盘柫亢蚉、V操作，實現(xiàn)上述過程中的互斥和同步。要求寫出完整的過程，說明信號量的含義并賦初值。分析

（1）臨界資源等待的座位，互斥的，一個座位一個人取號機，互斥使用服務窗口，營業(yè)員與顧客同步使用

（2）信號量等待的座位：seets

取號機：mutex

服務窗口：haveCustom顧客與營業(yè)員同步

（3）初值

seets=10,//有10個坐位的資源信號量

mutex=1,//取號機互斥信號量

haveCustom=0;//顧客與營業(yè)員同步，無顧客時營業(yè)員休息

解：semaphoreseets=10,//有10個坐位的資源信號量mutex=1,//取號機互斥信號量haveCustom=0;//顧客與營業(yè)員同步，無顧客時營業(yè)員休息

process顧客

{

P(seets);//等空位

P(mutex);//申請使用取號機

從取號機上取號;

V(mutex);//取號完畢

V(haveCustom);//通知營業(yè)員有新顧客到來，等待營業(yè)員叫號;

V(seets);//離開坐位接受服務；}

process營業(yè)員

{while(True)

{P(haveCustom);//沒有顧客則休息叫號;

為顧客服務;}}補充例題2

假定系統(tǒng)有三個并發(fā)進程read,move和print共享緩沖器B1和B2。進程read負責從輸入設備上讀信息，每讀出一個記錄后把它存放到緩沖器B1中。進程move從緩沖器B1中取出一記錄，加工后存入緩沖器B2。進程print將B2中的記錄取出打印輸出。緩沖器B1和B2每次只能存放一個記錄。要求三個進程協(xié)調(diào)完成任務，使打印出來的與讀入的記錄的個數(shù)，次序完全一樣。請用P、V操作，寫出它們的并發(fā)程序。readPrintmoveB1B2分析（1）并發(fā)進程：

read,move和print（2）臨界資源緩沖器B1：read、move互斥使用，又相互協(xié)作緩沖器B2：move、print互斥使用，又相互協(xié)作（3）信號量緩沖器B1信號量：

s1:read、move互斥使用

empty1、full1read、move同步緩沖器B2信號量：

s2:move和print互斥使用

empty2、full2move和print同步

（4）初值

empty1=m、empty2=n;緩沖區(qū)數(shù)量

full1=0、full2=0;控制同步

s1=1、s2=1控制互斥其同步描述如下：intempty1=m;/*也可定義為其他信號量類型*/intempty2=n;intfull1=0;intfull2=0;ints1=1;ints2=1;main(){ PA(); PB(); PC();}read(){從設備讀一批數(shù)據(jù)；

p(empty1);

P(S1);

將數(shù)據(jù)存入緩沖池B1；

V(S1);

v(full1);}move(){

P(full1);P(S1);

從緩沖池B1中取出數(shù)據(jù)；

V(S1);

V(empty1);/*前半部分結(jié)束*/

將數(shù)據(jù)進程加工；

P(empty2);P(S2);

將數(shù)據(jù)存入緩沖池B2；

V(S2);

V(full2);}print(){

P(full2);P(S2);

從緩沖區(qū)2中取出數(shù)據(jù)；

V(S2);

V(empty2);

打印數(shù)據(jù)；}readPrintmoveB1B2補充例題3在一輛公共汽車上，司機和售票員各行其職，司機負責開車和到站停車；售票員負責售票和開、關(guān)門，當售票員關(guān)好車門后，司機才能繼續(xù)開車行駛。試用P、V操作實現(xiàn)司機與售票員之間的同步。分析（1）并發(fā)進程：

司機進程driver和售票員進程busman

（2）臨界資源：車輛啟動與車門開關(guān)（3）信號量：

S1：是否允許司機啟動汽車的變量

S2：是否允許售票員開門的變量

（4）初值

S1=0：不得啟動汽車

S2=0：不得開門driver()//司機進程

{

P(S1);//請求啟動汽車

啟動汽車;正常行車；到站停車；

V(S2);//釋放開門變量，相當于通知售票員可以開門

}busman()//售票員進程

{關(guān)車門;

V(S1)；//釋放開車變量，相當于通知司機可以開車售票到站

P(S2)；//請求開門開車門；上下乘客；

}Semaphores1=0;

Semaphore

s2=0;main(){ driver(); busman();}

補充例題4一家四人父、母、兒子、女兒圍桌而坐；桌上有一個水果盤；（1）當水果盤空時，父親可以放香蕉或者母親可以放蘋果，但盤中已有水果時，就不能放，父母等待。當盤中有香蕉時，女兒可吃香蕉，否則，女兒等待；當盤中有蘋果時，兒子可吃，否則，兒子等待。分析（1）并發(fā)進程：

父親、母親、兒子、女兒

（2）臨界資源：盤子（3）信號量：

SE(空盤子)；

SA（放了蘋果的盤子）；

SB(放了香蕉的盤子)

（4）初值

SE=1(空盤子)；

SA=0（放了蘋果的盤子）；

SB=0(放了香蕉的盤子)SemaphoreSE=1；SA=0;SB=0;main(){ 父親();

母親();

兒子();

女兒();}

父親(){

P(SE)

放香蕉

V(SB)//通知女兒)母親（）{

P(SE)

放蘋果

V(SA)//通知兒子}兒子（）{

P(SA)拿蘋果

V(SE)}女兒（）{

P(SB)拿香蕉

V(SE)}（2）把（1）改為：兒子要吃蘋果時，請母親放蘋果，女兒要吃香蕉時，請父親放香蕉，（還是盤子為空時才可以放）。父親(){

P(SF)P(SE)

放香蕉

V(SB)//通知女兒)母親（）{

P(SM)P(SE)

放蘋果

V(SA)//通知兒子}兒子（）{

V(SM)P(SA)拿蘋果V(SE)}女兒（）{

V(SF)P(SB)拿香蕉V(SE)}再增加兩個信號量：SF=0，女兒請求吃香蕉；,SM=0兒子請求吃蘋果2.7管程

在進程能夠共享內(nèi)存的前提下，如果能集中和封裝針對一個共享資源的所有訪問，即把相關(guān)的共享變量及操作集中在一起統(tǒng)一控制和管理，就可以方便地管理和使用