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

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

教學(xué)內(nèi)容

2.1進(jìn)程的引入2.2進(jìn)程的描述

2.3進(jìn)程控制

2.4進(jìn)程的同步與互斥

2.5信號(hào)量機(jī)制

2.6進(jìn)程同步問(wèn)題舉例

2.7管程

2.8進(jìn)程的高級(jí)通信

2.9信號(hào)通信機(jī)制

2.10線程

22.1進(jìn)程的引入

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

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

I→C→P。

32.1進(jìn)程的引入

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

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

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

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

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

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

就緒

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

進(jìn)程的動(dòng)態(tài)性由它的狀態(tài)及狀態(tài)轉(zhuǎn)換來(lái)體現(xiàn)的。1．進(jìn)程的三個(gè)基本狀態(tài)

進(jìn)程通常至少有三種基本狀態(tài)：（1）就緒狀態(tài)（ready）進(jìn)程運(yùn)行所需的外部條件滿足，但因?yàn)槠渌M(jìn)程已占用CPU，所以暫時(shí)不能運(yùn)行。（2）執(zhí)行狀態(tài)(running)

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

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

對(duì)于處于就緒狀態(tài)的進(jìn)程，在調(diào)度程序?yàn)橹峙淞颂幚頇C(jī)之后，該進(jìn)程便可執(zhí)行。相應(yīng)地，它由就緒狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行狀態(tài)。執(zhí)行==》就緒

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

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

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

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

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

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

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

Linux系統(tǒng)的一個(gè)任務(wù)總體上有以下幾種狀態(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)。由于某些原因進(jìn)程被終止，這個(gè)進(jìn)程所占有的資源全部釋放之后，還保存著PCB信息，這種占有PCB但已被撤消的進(jìn)程就處于僵死狀態(tài)。（5）TASK-STOPPED狀態(tài)，暫停狀態(tài)。

18P12.2進(jìn)程的描述

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

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

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

進(jìn)程標(biāo)識(shí)符

處理機(jī)狀態(tài)

進(jìn)程調(diào)度信息

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

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

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

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

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

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

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

244．進(jìn)程控制信息

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

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

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

（3）資源清單:

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

本進(jìn)程PCB所在隊(duì)列的下一個(gè)進(jìn)程PCB的首地址。

252.2.2進(jìn)程控制塊的組織方式各進(jìn)程的PCB有如下幾種組織方式：

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

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

2．鏈接方式

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

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

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

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

進(jìn)程和處理機(jī)管理的一個(gè)重要任務(wù)是進(jìn)程控制。

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，等待該事件的進(jìn)程都將被喚醒。喚醒一個(gè)進(jìn)程有兩種方法，一種是由系統(tǒng)進(jìn)程喚醒，另一種是由事件發(fā)生進(jìn)程喚醒。

37

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

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

運(yùn)行運(yùn)行

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

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

fork.c

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

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

intfork()；

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

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

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

pid的值為新創(chuàng)建的子進(jìn)程標(biāo)識(shí)號(hào)。pid=-1：創(chuàng)建失敗。用進(jìn)程的家族關(guān)系main(){fork();fork();fork();printf(“S”);}SSSSSSSSacb例：編寫一段程序，使用系統(tǒng)調(diào)用fork()創(chuàng)建兩個(gè)子進(jìn)程。當(dāng)此程序運(yùn)行時(shí)，在系統(tǒng)中有一個(gè)父進(jìn)程和兩個(gè)子進(jìn)程活動(dòng)。讓每一個(gè)進(jìn)程在屏幕上顯示一個(gè)字符：父進(jìn)程顯示字符“a”，子進(jìn)程分別顯示字符“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í)行另一個(gè)程序。在Linux系統(tǒng)中，當(dāng)由fork()系統(tǒng)調(diào)用創(chuàng)建一個(gè)子進(jìn)程后，可再利用exec()系統(tǒng)調(diào)用執(zhí)行另一個(gè)程序。3．exit()系統(tǒng)調(diào)用對(duì)于一般的用戶進(jìn)程，在其任務(wù)完成后應(yīng)被盡快撤消。

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

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

兩個(gè)或兩個(gè)以上的進(jìn)程不能同時(shí)使用的資源為臨界資源。

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

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

（2）進(jìn)程T2的定義

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

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

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

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

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

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

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

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

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

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

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

進(jìn)程的互斥與同步1．同步與互斥的概念

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

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

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

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

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

1981年，G.L.Peterson提出了一個(gè)簡(jiǎn)單的算法來(lái)解決進(jìn)程互斥進(jìn)入臨界區(qū)的問(wèn)題。這種方法描述為：為每個(gè)進(jìn)程設(shè)置一個(gè)標(biāo)志，當(dāng)標(biāo)志值為true時(shí)，表示此進(jìn)程要求進(jìn)入臨界區(qū)，另外，再設(shè)置一個(gè)指示器turn，用來(lái)標(biāo)識(shí)由哪個(gè)進(jìn)程可以進(jìn)入臨界區(qū)，即當(dāng)turn=＝i時(shí)，表示進(jìn)程pi可以進(jìn)入臨界區(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實(shí)現(xiàn)進(jìn)程同步的硬件機(jī)制許多計(jì)算機(jī)已經(jīng)提供了一些特殊的硬件指令，允許對(duì)一個(gè)字中的內(nèi)容進(jìn)行檢測(cè)和修改正，或者是對(duì)兩個(gè)字的內(nèi)容進(jìn)行交換等?？衫眠@些特殊的指令來(lái)解決臨界區(qū)問(wèn)題。下面是實(shí)現(xiàn)對(duì)臨界區(qū)管理的硬件方法。1．關(guān)中斷

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

可以為每類資源設(shè)置一個(gè)信號(hào)量。

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

申請(qǐng)和釋放臨界資源的兩個(gè)原語(yǔ)操作：

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

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

P、V操作的操作對(duì)象是信號(hào)量61semaphores1=2,s2=3;AND型信號(hào)量

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

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．整型信號(hào)量

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

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

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

進(jìn)程等待；

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

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

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

structsemaphore{

ints;structPCB*queue;}semaphore；65

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

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

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

本進(jìn)程繼續(xù)；

Else{

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

設(shè)變量Ｓ為記錄型信號(hào)量:

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

ifs≤0then

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

}2.5.3利用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步和互斥

可以用wait(s)和signal(s)操作處理飛機(jī)買票問(wèn)題。對(duì)臨界資源n設(shè)一互斥信號(hào)量S，將原進(jìn)程T1及T2做如下修改：進(jìn)程：semaphoreS=1；T1()進(jìn)程：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操作可以實(shí)現(xiàn)進(jìn)程之間的同步。關(guān)于這類問(wèn)題的應(yīng)用有兩種類型：一種是對(duì)于臨界資源，在使用之前申請(qǐng)，使用之后釋放，我們給這類資源設(shè)一個(gè)互斥信號(hào)量即可；第二種類型是利用信號(hào)量控制進(jìn)程之間運(yùn)行的順序，這時(shí)需要根據(jù)實(shí)際情況設(shè)置多于一個(gè)信號(hào)量，對(duì)同一個(gè)信號(hào)量的P、V操作在不同的進(jìn)程之間進(jìn)行。2.6進(jìn)程同步問(wèn)題舉例

692.6.1

兩個(gè)簡(jiǎn)單的例子

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

打印，V(S);……}在這個(gè)例子中，多個(gè)進(jìn)程隨機(jī)使用打印機(jī)信號(hào)量，使用之前先申請(qǐng)，使用之后釋放該信號(hào)量。。2.6.1

兩個(gè)簡(jiǎn)單的例子

例2．有一個(gè)緩沖區(qū)，供多個(gè)進(jìn)程共享。這些進(jìn)程中有生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程。寫出多個(gè)進(jìn)程共同使用同一個(gè)緩沖區(qū)時(shí)實(shí)現(xiàn)進(jìn)程同步的程序。71緩沖區(qū)用來(lái)臨時(shí)存放數(shù)據(jù)，在使用緩沖區(qū)時(shí)應(yīng)該注意:對(duì)一個(gè)緩沖區(qū)，數(shù)據(jù)的寫入和提取應(yīng)當(dāng)是交替執(zhí)行的，否則會(huì)發(fā)生錯(cuò)誤：數(shù)據(jù)丟失或數(shù)據(jù)重復(fù)。緩沖區(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);……}}解：同步使用一個(gè)緩沖區(qū)的程序段為：semaphoreempty=n,full=0，mutex=1;／＊定義信號(hào)量并賦初值＊／

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

1．問(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)。規(guī)定消費(fèi)者進(jìn)程不能到一個(gè)空緩沖區(qū)中去取產(chǎn)品；生產(chǎn)者進(jìn)程不能將產(chǎn)品放入一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中。74012……i………n-2n-1

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

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

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

mutex：互斥使用緩沖池信號(hào)量，由于初始情況下無(wú)進(jìn)程使用緩沖池，故初值mutex=１；

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

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

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

＊定義信號(hào)量并賦初值＊／

messagebuffer[n];

intin=0,out=0;

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

voidmain(){parbegin(proceducer,consumer);}生產(chǎn)者進(jì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消費(fèi)者進(jìn)程：voidconsumer(){do{

P(full);

P(mutex);

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

V(mutex);

V(empty);

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

緩沖池、空閑區(qū)、存貨區(qū)；對(duì)應(yīng)信號(hào)量：

緩沖池==》mutex

空閑區(qū)==》empty

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

empty=n；

full=0;

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

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

…

P(empty);

P(mutex);

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

in=(in+1)%n;

V(mutex);

V(full);消費(fèi)者進(jìn)程：

P(full);

P(mutex);

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

V(mutex);

V(empty);

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

4．在生產(chǎn)者—消費(fèi)者問(wèn)題中應(yīng)注意：

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

1．問(wèn)題的提出

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

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

（2）信號(hào)量：共享文件F對(duì)應(yīng)信號(hào)量為wmutex；整形變量readcount對(duì)應(yīng)信號(hào)量rmutex；

（3）信號(hào)量初值：wmutex=1;

rmutex=1。853．算法及程序

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

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

readcount++;

V(rmutex);

…

進(jìn)行讀操作;…

P(rmutex);

readcount--;

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

87寫者進(jìn)程：voidwriter(){……

P(wmutex);

執(zhí)行寫操作;

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

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

P(chop);P(chop);

吃；

V(chop);

V(chop);}

2．問(wèn)題分析

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

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

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

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

925個(gè)哲學(xué)家就餐問(wèn)題

臨界資源：5只筷子

信號(hào)量：每只筷子一個(gè)信號(hào)量semaphorechopstick[5]={1,1,1,1,1};

則第i位哲學(xué)家的活動(dòng)可描述為：

93

semaphore

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

//5個(gè)互斥信號(hào)量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;

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

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

（1）臨界資源等待的座位，互斥的，一個(gè)座位一個(gè)人取號(hào)機(jī)，互斥使用服務(wù)窗口，營(yíng)業(yè)員與顧客同步使用

（2）信號(hào)量等待的座位：seets

取號(hào)機(jī)：mutex

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

（3）初值

seets=10,//有10個(gè)坐位的資源信號(hào)量

mutex=1,//取號(hào)機(jī)互斥信號(hào)量

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

解：semaphoreseets=10,//有10個(gè)坐位的資源信號(hào)量mutex=1,//取號(hào)機(jī)互斥信號(hào)量haveCustom=0;//顧客與營(yíng)業(yè)員同步，無(wú)顧客時(shí)營(yíng)業(yè)員休息

process顧客

{

P(seets);//等空位

P(mutex);//申請(qǐng)使用取號(hào)機(jī)

從取號(hào)機(jī)上取號(hào);

V(mutex);//取號(hào)完畢

V(haveCustom);//通知營(yíng)業(yè)員有新顧客到來(lái)，等待營(yíng)業(yè)員叫號(hào);

V(seets);//離開(kāi)坐位接受服務(wù)；}

process營(yíng)業(yè)員

{while(True)

{P(haveCustom);//沒(méi)有顧客則休息叫號(hào);

為顧客服務(wù);}}補(bǔ)充例題2

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

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

s1:read、move互斥使用

empty1、full1read、move同步緩沖器B2信號(hào)量：

s2:move和print互斥使用

empty2、full2move和print同步

（4）初值

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

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

s1=1、s2=1控制互斥其同步描述如下：intempty1=m;/*也可定義為其他信號(hào)量類型*/intempty2=n;intfull1=0;intfull2=0;ints1=1;ints2=1;main(){ PA(); PB(); PC();}read(){從設(shè)備讀一批數(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ù)進(jìn)程加工；

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補(bǔ)充例題3在一輛公共汽車上，司機(jī)和售票員各行其職，司機(jī)負(fù)責(zé)開(kāi)車和到站停車；售票員負(fù)責(zé)售票和開(kāi)、關(guān)門，當(dāng)售票員關(guān)好車門后，司機(jī)才能繼續(xù)開(kāi)車行駛。試用P、V操作實(shí)現(xiàn)司機(jī)與售票員之間的同步。分析（1）并發(fā)進(jìn)程：

司機(jī)進(jìn)程driver和售票員進(jìn)程busman

（2）臨界資源：車輛啟動(dòng)與車門開(kāi)關(guān)（3）信號(hào)量：

S1：是否允許司機(jī)啟動(dòng)汽車的變量

S2：是否允許售票員開(kāi)門的變量

（4）初值

S1=0：不得啟動(dòng)汽車

S2=0：不得開(kāi)門driver()//司機(jī)進(jìn)程

{

P(S1);//請(qǐng)求啟動(dòng)汽車

啟動(dòng)汽車;正常行車；到站停車；

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

}busman()//售票員進(jìn)程

{關(guān)車門;

V(S1)；//釋放開(kāi)車變量，相當(dāng)于通知司機(jī)可以開(kāi)車售票到站

P(S2)；//請(qǐng)求開(kāi)門開(kāi)車門；上下乘客；

}Semaphores1=0;

Semaphore

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

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

父親、母親、兒子、女兒

（2）臨界資源：盤子（3）信號(hào)量：

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）改為：兒子要吃蘋果時(shí)，請(qǐng)母親放蘋果，女兒要吃香蕉時(shí)，請(qǐng)父親放香蕉，（還是盤子為空時(shí)才可以放）。父親(){

P(SF)P(SE)

放香蕉

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

P(SM)P(SE)

放蘋果

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

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

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

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