《計(jì)算機(jī)操作系統(tǒng)教程》課件-第3章

3.1為什么要引入進(jìn)程的概念3.2進(jìn)程的表示和調(diào)度狀態(tài)3.3進(jìn)程的控制3.4進(jìn)程調(diào)度3.5線程及其管理3.6進(jìn)程通訊3.7死鎖3.8小結(jié)習(xí)題3.1.1從順序程序設(shè)計(jì)談起

自從計(jì)算機(jī)問世以來，人們廣泛地使用“程序”這一概念。在多道程序設(shè)計(jì)出現(xiàn)以前，“程序”的最大特征是它的順序性，即順序執(zhí)行。實(shí)際上應(yīng)把它稱為“順序程序”，但是因?yàn)檫@一性質(zhì)是不言而喻的，所以就簡(jiǎn)稱為“程序”。下面我們用一個(gè)簡(jiǎn)單的例子來說明順序程序的某些重要特性。3.1為什么要引入進(jìn)程的概念我們假設(shè)有n個(gè)作業(yè)，而每個(gè)作業(yè)Ji都由三個(gè)程序段Ii、Ci、Pi組成。其中，Ii

表示從輸入機(jī)上讀入第i個(gè)作業(yè)的信息；Ci表示執(zhí)行第i個(gè)作業(yè)的計(jì)算；Pi表示在打印機(jī)上印出第i個(gè)作業(yè)的計(jì)算結(jié)果。在早期的計(jì)算機(jī)中，每一作業(yè)的這三個(gè)程序只能是一個(gè)接一個(gè)地順序執(zhí)行。也就是輸入、計(jì)算和打印三者串行工作，并且前一個(gè)作業(yè)結(jié)束后，才能執(zhí)行下一個(gè)作業(yè)，見圖3.1。圖3.1程序的順序執(zhí)行顯然，程序的順序執(zhí)行具有如下特性：

(1)當(dāng)順序程序在處理機(jī)上執(zhí)行時(shí)，處理機(jī)嚴(yán)格地順序執(zhí)行程序規(guī)定的動(dòng)作。每個(gè)動(dòng)作都必須在前一動(dòng)作結(jié)束后才能開始。除了人為的干預(yù)造成機(jī)器暫時(shí)停頓外，前一動(dòng)作的結(jié)束就意味著后一動(dòng)作的開始。程序和機(jī)器執(zhí)行程序的活動(dòng)嚴(yán)格一一對(duì)應(yīng)。

(2)一個(gè)程序在機(jī)器中執(zhí)行時(shí)，它獨(dú)占全機(jī)資源，除了初始狀態(tài)外，只有程序本身規(guī)定的動(dòng)作才能改變這些資源的狀態(tài)。

(3)程序的執(zhí)行結(jié)果與其執(zhí)行速度無關(guān)。也就是說，處理機(jī)在執(zhí)行程序的兩個(gè)動(dòng)作之間如有停頓時(shí)，不會(huì)影響程序的執(zhí)行結(jié)果。

上述特點(diǎn)概括起來就是程序的封閉性和可再現(xiàn)性。所謂封閉性指的是程序一旦開始執(zhí)行，其計(jì)算結(jié)果就只取決于程序本身，除了人為改變機(jī)器運(yùn)行狀態(tài)或機(jī)器故障外，不受外界因素的影響。所謂可再現(xiàn)性是指當(dāng)該程序重復(fù)執(zhí)行時(shí)，必將獲得相同的結(jié)果。這給程序的調(diào)試帶來了很大的方便。3.1.2程序的并發(fā)執(zhí)行和資源共享

1.程序的并發(fā)執(zhí)行

采用多道程序設(shè)計(jì)技術(shù)后，系統(tǒng)中各個(gè)部分不再以單純的串行方式工作。換句話說，在任一時(shí)刻，系統(tǒng)中不再只有一個(gè)活動(dòng)，而是存在著許多并行的活動(dòng)。從硬件方面看，處理機(jī)、各種外設(shè)、存儲(chǔ)部件常常并行地工作著；從程序活動(dòng)方面看，則可能有若干個(gè)作業(yè)程序或者同時(shí)，或者相互穿插地在系統(tǒng)中被執(zhí)行。這就是說，有很多程序段是可以并發(fā)(Concurrent)執(zhí)行的。所謂并發(fā)執(zhí)行是指兩個(gè)程序的執(zhí)行在時(shí)間上是重疊的，即使這種重疊只有很小的一部分，我們也稱這兩個(gè)程序是并發(fā)執(zhí)行的。程序的并發(fā)執(zhí)行已成為現(xiàn)代操作系統(tǒng)的一個(gè)基本特征?，F(xiàn)在我們回到圖3.1的例子。對(duì)于任何一個(gè)作業(yè)i，其輸入操作Ii、計(jì)算操作Ci、打印操作Pi這三者必須順序執(zhí)行，但對(duì)n個(gè)作業(yè)來說，則有可能并發(fā)執(zhí)行。例如，輸入程序在輸入完第i個(gè)作業(yè)程序后，計(jì)算程序在對(duì)第i個(gè)作業(yè)進(jìn)行計(jì)算的同時(shí)，再啟動(dòng)輸入程序，輸入第i+1個(gè)作業(yè)程序，這就使得第i+1個(gè)作業(yè)的輸入和第i個(gè)作業(yè)的計(jì)算能并發(fā)執(zhí)行。圖3.2給出了輸入、計(jì)算、打印程序?qū)σ慌鳂I(yè)進(jìn)行處理的執(zhí)行順序。圖3.2程序段并發(fā)執(zhí)行的有向圖在該例中：

I1先于C1和I2;

C1先于P1和C2;

P1先于P2;

I2先于C2和I3。

說明了某些程序段必須在其它程序段之前完成。此外從圖中可以看出：

I2和C1;

I3、C2和P1;

I4、C3和P2;

是重疊的。

2.資源共享

資源共享是現(xiàn)代操作系統(tǒng)另一基本特性。所謂資源共享是指系統(tǒng)中的硬件資源和軟件資源不再為單個(gè)用戶程序所獨(dú)占，而由幾道用戶程序共同使用。于是，這些資源的狀態(tài)不再取決于一道程序，而是由多道程序的活動(dòng)所決定。這就從根本上打破了一道程序封閉于一個(gè)系統(tǒng)中執(zhí)行的局面。

程序并發(fā)執(zhí)行和資源共享之間互為依存條件。一方面，資源共享是以程序并發(fā)執(zhí)行為條件的，因?yàn)槿粝到y(tǒng)不允許程序并發(fā)，也就不存在資源共享問題；另一方面，若系統(tǒng)不能對(duì)共享資源進(jìn)行有效的管理，也就降低了程序并發(fā)執(zhí)行的效果。3.1.3程序并發(fā)執(zhí)行的特性

程序并發(fā)執(zhí)行雖然卓有成效地增加了系統(tǒng)的處理能力，提高了系統(tǒng)資源的利用率，但也帶來了一些新問題，也就是產(chǎn)生了與順序程序不同的新特性，這些新特性是：

1.失去了程序的封閉性

設(shè)有觀察者和報(bào)告者并行工作。在一條單向行駛的公路上經(jīng)常有卡車通過。觀察者不斷觀察并對(duì)通過的卡車計(jì)數(shù)。報(bào)告者定時(shí)地將觀察者的計(jì)數(shù)值打印出來，然后將計(jì)數(shù)器重新清“0”。此時(shí)我們可以寫出如下程序（其中Cobegin和Coend表示它們之間的程序可以并發(fā)執(zhí)行）：

begin

count∶integer;

count∶=0;

cobegin

observer

begin

L1；……

observenextcar;

count∶=count+1;

gotoL1

end

reporter

begin

L2∶……

printcount;

count∶=0

gotol2

end

coend

end由于觀察者和報(bào)告者各自獨(dú)立地并行工作，count∶=count+1的操作，既可以在報(bào)告者的printcount和count∶=0操作之前，也可以在其后，還可以在printco

unt和count∶=0之間。即可能出現(xiàn)以下三種執(zhí)行序列：

(1)count∶=count+1;printcount;count∶=0;

(2)printcount;count∶=0;count∶=count+1;

(3)printcount;count∶=count+1,count∶=0。假設(shè)在開始某個(gè)循環(huán)之前，count的值為n，則在完成一個(gè)循環(huán)后，對(duì)上述三個(gè)執(zhí)行序列打印機(jī)打印的count值和執(zhí)行后的count值如下表所示：由上表可見，由于觀察者和報(bào)告者的執(zhí)行速度不同，導(dǎo)致了計(jì)算結(jié)果的不同。這就是說，程序并發(fā)執(zhí)行已喪失了順序程序所保持的封閉性和可再現(xiàn)性。

2.程序和機(jī)器執(zhí)行程序的活動(dòng)不再一一對(duì)應(yīng)

程序和機(jī)器執(zhí)行程序的活動(dòng)是兩個(gè)概念。程序是指令的有序集合，是靜態(tài)的概念；而機(jī)器執(zhí)行程序的活動(dòng)是指指令序列在處理機(jī)上的執(zhí)行過程，或處理機(jī)按照程序執(zhí)行指令序列的過程。通常把機(jī)器執(zhí)行程序的活動(dòng)稱為“計(jì)算”。顯然，“計(jì)算”是一個(gè)動(dòng)態(tài)的概念。

如前所述，程序在順序執(zhí)行時(shí)，程序和“計(jì)算”之間保持一一對(duì)應(yīng)的關(guān)系。但在并發(fā)執(zhí)行時(shí)，這種關(guān)系是否還存在呢?我們知道，一個(gè)并發(fā)程序可為多個(gè)用戶作業(yè)調(diào)用，而使該程序處于多個(gè)“執(zhí)行”中，從而形成了多個(gè)“計(jì)算”。這就是說，多個(gè)“計(jì)算”可能是在不同數(shù)據(jù)集上執(zhí)行同一程序。所以程序和“計(jì)算”不再一一對(duì)應(yīng)。例如在分時(shí)系統(tǒng)中，內(nèi)存中一個(gè)編譯程序的副本同時(shí)為幾個(gè)用戶作業(yè)編譯時(shí)，該編譯程序的幾次執(zhí)行，便對(duì)應(yīng)了幾個(gè)“計(jì)算”。

3.并發(fā)程序間的相互制約

資源共享和程序的并發(fā)執(zhí)行(或稱并發(fā)活動(dòng))使得系統(tǒng)的工作情況變得相當(dāng)錯(cuò)綜復(fù)雜，尤其表現(xiàn)在系統(tǒng)中并發(fā)程序間的相互依賴和制約方面。

系統(tǒng)中各個(gè)并發(fā)程序活動(dòng)都有一定的獨(dú)立性，它們分別提供一種用戶或系統(tǒng)功能。例如，各用戶作業(yè)的活動(dòng)分別提供一種用戶需要的功能，它們之間相互獨(dú)立，而沒有相互依賴和制約關(guān)系。又如，操作系統(tǒng)中對(duì)處理機(jī)的調(diào)度和對(duì)各種外部設(shè)備的控制活動(dòng)，兩者之間基本上也是獨(dú)立的，各自提供一種系統(tǒng)功能。這就是說，系統(tǒng)中各個(gè)并發(fā)程序活動(dòng)具有獨(dú)立性的一面，但在兩個(gè)并發(fā)程序活動(dòng)之間有時(shí)也會(huì)以直接或間接方式發(fā)生相互依賴和相互制約關(guān)系。直接制約關(guān)系通常是在彼此之間有邏輯關(guān)系的兩個(gè)并發(fā)執(zhí)行的程序之間發(fā)生的。例如，一個(gè)正在執(zhí)行的程序段需要另一程序段的計(jì)算結(jié)果，只有當(dāng)另一程序段在某一時(shí)刻送來計(jì)算結(jié)果時(shí)，正在執(zhí)行的程序段才能繼續(xù)執(zhí)行下去。否則它就一直等待，無法執(zhí)行。兩個(gè)并發(fā)程序段以間接方式發(fā)生制約關(guān)系是由競(jìng)爭(zhēng)使用同一資源引起的。得到資源的程序段可以繼續(xù)執(zhí)行，得不到資源的程序段就只好暫停等待。

由于各程序活動(dòng)之間的相互制約關(guān)系，各個(gè)程序活動(dòng)的工作狀態(tài)就與它所處的環(huán)境有密切聯(lián)系。它隨著外界變化而不停地變化，并且它不像單道程序系統(tǒng)中連貫順序執(zhí)行那樣，而是走走停停，具有執(zhí)行-暫停-執(zhí)行的活動(dòng)規(guī)律。3.1.4進(jìn)程概念的引入

綜上所述，在多道程序的環(huán)境下,程序的并發(fā)執(zhí)行代替了程序的順序執(zhí)行。它破壞了程序的封閉性和可再現(xiàn)性，使得程序和計(jì)算不再一一對(duì)應(yīng)，而且由于資源共享和程序的并發(fā)執(zhí)行導(dǎo)致在各個(gè)程序活動(dòng)之間可能存在相互制約關(guān)系?？傊?，程序活動(dòng)不再處于一個(gè)封閉系統(tǒng)中，而出現(xiàn)了許多新的特征，即獨(dú)立性、并發(fā)性、動(dòng)態(tài)性以及它們之間的相互制約性。在這種情況下,程序這個(gè)靜態(tài)概念已經(jīng)不能如實(shí)地反映程序活動(dòng)的這些特征。為此，20世紀(jì)60年代中期的MULTICS系統(tǒng)的設(shè)計(jì)者和以E.W.Dijkstra為首的T.H.E系統(tǒng)的設(shè)計(jì)者開始廣泛使用“進(jìn)程”(Process)這一新概念來描述系統(tǒng)和用戶的程序活動(dòng)，而IBM公司的CTSS/360系統(tǒng)使用了另一術(shù)語——“任務(wù)”(Task)，但兩者的意義相同。進(jìn)程是操作系統(tǒng)中的一個(gè)最基本也是最重要的概念。掌握這個(gè)概念對(duì)于理解操作系統(tǒng)實(shí)質(zhì)，對(duì)于分析、設(shè)計(jì)操作系統(tǒng)都有其非常重要的意義。但是迄今為止，對(duì)這一概念尚無一個(gè)非常確切的、令人滿意的、統(tǒng)一的定義。下面列舉幾個(gè)操作系統(tǒng)的權(quán)威人士對(duì)“進(jìn)程”所下的定義：

(1)行為的一個(gè)規(guī)則叫做程序，程序在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動(dòng)稱為進(jìn)程(Dijkstra)。

(2)一個(gè)進(jìn)程是一系列逐一執(zhí)行的操作，而操作的確切含義則有賴于我們以何種詳盡程度來描述進(jìn)程(Brinch.Hansen)。

(3)進(jìn)程是這樣的計(jì)算部分，它可以與別的進(jìn)程并發(fā)執(zhí)行(MadnickandDonovan)。

(4)順序進(jìn)程(有時(shí)稱為任務(wù))是一個(gè)程序與其數(shù)據(jù)集一道順序通過處理機(jī)的執(zhí)行所發(fā)生的活動(dòng)(AlanC.Shaw)。

(5)一個(gè)進(jìn)程是由偽處理機(jī)執(zhí)行的一個(gè)程序(J.H.Saltzer)。

上述這些從不同角度對(duì)進(jìn)程所做的解釋或所下的定義，有些是近似的，有些則側(cè)重某一方面。這說明進(jìn)程這一概念尚未完全統(tǒng)一，但長期以來卻已廣泛而成功地用于許多系統(tǒng)之中，成為構(gòu)造操作系統(tǒng)的不可缺少的強(qiáng)有力的工具。

為了強(qiáng)調(diào)進(jìn)程的并發(fā)性和動(dòng)態(tài)性，我們定義如下：進(jìn)程是程序的一次執(zhí)行，該程序可與其它程序并發(fā)執(zhí)行。

3.2.1進(jìn)程的表示

1.進(jìn)程的組成

進(jìn)程通常由三部分組成。一部分是程序，一部分是數(shù)據(jù)集合，再一部分是進(jìn)程控制塊(ProcessControlBlock，記為PCB)，如圖3.3所示。3.2進(jìn)程的表示和調(diào)度狀態(tài)圖3.3進(jìn)程的表示進(jìn)程的程序部分描述了進(jìn)程所要完成的功能。如果一個(gè)程序能為多個(gè)進(jìn)程同時(shí)共享執(zhí)行，那么，這部分就應(yīng)以純碼(PureCode)，也就是以再入碼(ReentryCode)的形式編寫。它是進(jìn)程執(zhí)行時(shí)不可修改的部分。

數(shù)據(jù)集合部分包括程序在執(zhí)行時(shí)所需要的數(shù)據(jù)和工作區(qū)。這部分只能為一個(gè)進(jìn)程所專用，是進(jìn)程的可修改部分。

程序和數(shù)據(jù)集合兩部分是進(jìn)程存在的物質(zhì)基礎(chǔ)，即進(jìn)程的實(shí)體。進(jìn)程控制塊(或任務(wù)控制塊)包含了進(jìn)程的描述信息和控制信息，是進(jìn)程的動(dòng)態(tài)特性的集中反映。不同的操作系統(tǒng)其進(jìn)程控制塊的內(nèi)容及信息量也不同。在小型機(jī)、微型機(jī)等比較簡(jiǎn)單的操作系統(tǒng)中，PCB只占用十幾個(gè)單元；而在一些大、中型機(jī)的操作系統(tǒng)中，PCB的內(nèi)容可能占用幾十甚至上百個(gè)單元。

進(jìn)程的PCB和進(jìn)程的程序、數(shù)據(jù)集合之間的關(guān)系是，如果把進(jìn)程的程序、數(shù)據(jù)比喻為進(jìn)程的“軀體”，那么PCB便是進(jìn)程的“靈魂”。

2.進(jìn)程控制塊

為描述進(jìn)程的動(dòng)態(tài)變化，便于系統(tǒng)對(duì)進(jìn)程進(jìn)行有效的控制和管理，系統(tǒng)中為每一進(jìn)程設(shè)置了一個(gè)進(jìn)程控制塊。進(jìn)程控制塊是進(jìn)程存在的一個(gè)惟一標(biāo)志。當(dāng)系統(tǒng)創(chuàng)建一個(gè)進(jìn)程時(shí)，系統(tǒng)便為其建立一個(gè)PCB，當(dāng)進(jìn)程被撤消時(shí)，系統(tǒng)收回它的PCB，隨之該進(jìn)程也就消亡了。

在通常的操作系統(tǒng)中，PCB應(yīng)包含如下一些信息：

(1)進(jìn)程標(biāo)識(shí)名或標(biāo)識(shí)數(shù)。為了標(biāo)識(shí)系統(tǒng)中的各個(gè)進(jìn)程，每個(gè)進(jìn)程必須有一個(gè)而且是惟一的標(biāo)識(shí)名或標(biāo)識(shí)數(shù)。進(jìn)程標(biāo)識(shí)名通常用字母和數(shù)字組成的“串”表示，進(jìn)程標(biāo)識(shí)數(shù)則是在一定數(shù)值范圍內(nèi)的進(jìn)程編號(hào)。有的系統(tǒng)用進(jìn)程標(biāo)識(shí)名作為進(jìn)程的外部標(biāo)識(shí)，它通常由創(chuàng)建者給出；用進(jìn)程標(biāo)識(shí)數(shù)作為進(jìn)程的內(nèi)部標(biāo)識(shí)，通常由系統(tǒng)給出。有的系統(tǒng)只用其中之一。

(2)位置信息。它指出進(jìn)程的程序和數(shù)據(jù)部分在內(nèi)存或外存中的物理位置。

(3)狀態(tài)信息。它指出進(jìn)程當(dāng)前所處的狀態(tài)，作為進(jìn)程調(diào)度分配處理機(jī)的依據(jù)，詳情后述。

(4)進(jìn)程的優(yōu)先級(jí)。一般根據(jù)進(jìn)程的輕重緩急程度為進(jìn)程指定一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)用優(yōu)先數(shù)表示。進(jìn)程調(diào)度程序根據(jù)優(yōu)先數(shù)的大小確定優(yōu)先級(jí)的高低，并把CPU控制交給優(yōu)先級(jí)最高的進(jìn)程。

(5)進(jìn)程現(xiàn)場(chǎng)保護(hù)區(qū)。當(dāng)進(jìn)程狀態(tài)變化時(shí)(例如一個(gè)進(jìn)程放棄使用處理機(jī))，它需要將當(dāng)時(shí)的CPU現(xiàn)場(chǎng)保護(hù)到內(nèi)存中，以便再次占用處理機(jī)時(shí)恢復(fù)正常運(yùn)行。有的系統(tǒng)把要保護(hù)的CPU現(xiàn)場(chǎng)放在進(jìn)程的工作區(qū)中，而PCB中僅給出CPU現(xiàn)場(chǎng)保護(hù)區(qū)起始地址。

(6)資源清單。每個(gè)7進(jìn)程在運(yùn)行時(shí)，除了需要內(nèi)存外，還需要其它資源，如I/O設(shè)備、外存、數(shù)據(jù)區(qū)等。這一部分指出資源需求、分配和控制信息。

(7)隊(duì)列指針或鏈接字。它用于將處于同一狀態(tài)的進(jìn)程鏈接成一個(gè)隊(duì)列，在該單元中存放下一進(jìn)程PCB首址。

(8)其它。我們這里只給出了一般操作系統(tǒng)中PCB所應(yīng)具有的內(nèi)容，然而各種不同操作系統(tǒng)的PCB其結(jié)構(gòu)是不相同的。例如在UNIX中，進(jìn)程控制塊包括兩大部分：其一是進(jìn)程基本控制塊，稱為proc結(jié)構(gòu)，這一部分內(nèi)容是，不管進(jìn)程是否正在處理機(jī)上運(yùn)行，系統(tǒng)都要查詢和修改的一些控制信息；另一部分則相反，當(dāng)進(jìn)程不在處理機(jī)上運(yùn)行時(shí)，系統(tǒng)不會(huì)對(duì)這部分信息進(jìn)行查詢和處理，它構(gòu)成了進(jìn)程控制塊的user結(jié)構(gòu)，稱為進(jìn)程擴(kuò)充控制塊。3.2.2進(jìn)程的調(diào)度狀態(tài)

1.進(jìn)程的基本調(diào)度狀態(tài)

進(jìn)程有三種基本調(diào)度狀態(tài)，它們是：

(1)運(yùn)行狀態(tài)。進(jìn)程已獲得必要的資源，并占有一個(gè)處理機(jī)，處理機(jī)正在執(zhí)行該進(jìn)程的程序。

(2)就緒狀態(tài)。如果進(jìn)程已具備了運(yùn)行條件，但由于處理機(jī)已被其它進(jìn)程占用，因此暫時(shí)不能運(yùn)行，而等待分配處理機(jī)，則稱該進(jìn)程處于就緒狀態(tài)，有時(shí)也稱為可運(yùn)行狀態(tài)。

(3)阻塞狀態(tài)。進(jìn)程在運(yùn)行過程中，因等待某一事件(如等待某一輸入輸出操作完成)而暫時(shí)不能運(yùn)行的狀態(tài)，稱為阻塞狀態(tài)，即進(jìn)程的運(yùn)行受到了阻塞。此時(shí)，即使處理機(jī)“空

閑”，也無法使用。這種狀態(tài)也稱為不可運(yùn)行狀態(tài)。

正在處理機(jī)上運(yùn)行的進(jìn)程稱為該處理機(jī)的現(xiàn)運(yùn)行進(jìn)程。任何時(shí)候，一個(gè)系統(tǒng)的現(xiàn)運(yùn)行進(jìn)程數(shù)一定少于或等于可用的處理機(jī)數(shù)。進(jìn)程的各種調(diào)度狀態(tài)，可以依據(jù)一定的條件而發(fā)生變化。處于運(yùn)行狀態(tài)的進(jìn)程可能因等待某種事件的發(fā)生而變成阻塞狀態(tài)(如等待輸入輸出操作的結(jié)束)；相應(yīng)事件發(fā)生后(如輸入輸出完成)，該進(jìn)程即可從阻塞狀態(tài)進(jìn)入就緒狀態(tài)。當(dāng)系統(tǒng)的進(jìn)程調(diào)度程序把處理機(jī)分配給某一就緒狀態(tài)的進(jìn)程時(shí)，它就從就緒狀態(tài)進(jìn)入運(yùn)行狀態(tài)。系統(tǒng)的進(jìn)程調(diào)度程序也可迫使某一處于運(yùn)行狀態(tài)的進(jìn)程放棄處理機(jī)而進(jìn)入就緒狀態(tài)。例如在分時(shí)系統(tǒng)中，現(xiàn)運(yùn)行進(jìn)程所使用的時(shí)間片已用完，便立即放棄處理機(jī)。進(jìn)程的三種基本狀態(tài)及其變化的條件示于圖3.4中。圖3.4進(jìn)程的基本調(diào)度狀態(tài)及其轉(zhuǎn)換

2.細(xì)分的進(jìn)程調(diào)度狀態(tài)

就緒、運(yùn)行和阻塞狀態(tài)是基本調(diào)度狀態(tài)。在有些系統(tǒng)中為了調(diào)度的方便，將上述三種基本調(diào)度狀態(tài)進(jìn)一步細(xì)分。例如，將就緒狀態(tài)細(xì)分為低優(yōu)先級(jí)就緒、中優(yōu)先級(jí)就緒和高優(yōu)先級(jí)就緒；把阻塞狀態(tài)細(xì)分為因等待盤、帶的I/O而阻塞，因等待終端的I/O而阻塞和因等待頁面的I/O而阻塞。對(duì)應(yīng)此種情況的進(jìn)程狀態(tài)的轉(zhuǎn)換如圖3.5所示。圖3.5細(xì)分的進(jìn)程狀態(tài)轉(zhuǎn)換圖另一種細(xì)分方法是將上述基本調(diào)度狀態(tài)的就緒和阻塞細(xì)分為活躍的和靜止的兩部分。這是因?yàn)?，有時(shí)需要人為地把正在運(yùn)行或沒在運(yùn)行的進(jìn)程掛起(Suspend)，使它們處于靜止?fàn)顟B(tài)(即正在運(yùn)行的進(jìn)程停止運(yùn)行，沒有運(yùn)行的進(jìn)程不再運(yùn)行)，以便研究它的運(yùn)行情況或?qū)λM(jìn)行修改。這樣一來，系統(tǒng)的三種基本調(diào)度狀態(tài)就演變?yōu)槲宸N調(diào)度狀態(tài)：運(yùn)行、活躍就緒、活躍阻塞、靜止就緒和靜止阻塞。圖3.6就是具有掛起操作的進(jìn)程狀態(tài)轉(zhuǎn)換圖。圖3.6具有掛起操作的進(jìn)程狀態(tài)轉(zhuǎn)換圖由此可以看出，在一些實(shí)際操作系統(tǒng)中，進(jìn)程的調(diào)度狀態(tài)往往不止三種基本狀態(tài)，通常要多設(shè)一些狀態(tài)。例如在UNIX系統(tǒng)版本6中，進(jìn)程調(diào)度狀態(tài)分為六種：運(yùn)行狀態(tài)、高優(yōu)先級(jí)睡眠狀態(tài)、低優(yōu)先級(jí)睡眠狀態(tài)、暫停狀態(tài)、等待善后處理狀態(tài)和創(chuàng)建子進(jìn)程狀態(tài)。3.3.1進(jìn)程的控制機(jī)構(gòu)

系統(tǒng)中的進(jìn)程并非永遠(yuǎn)存在于系統(tǒng)之中，它們都有自己的生命期，即經(jīng)歷誕生、生存直至消亡的不同歷史時(shí)期。在一個(gè)系統(tǒng)中能存在的進(jìn)程數(shù)，通常有數(shù)十甚至數(shù)百個(gè)。為了對(duì)進(jìn)程進(jìn)行有效的控制，操作系統(tǒng)必須設(shè)置一套控制機(jī)構(gòu)。這套控制機(jī)構(gòu)應(yīng)具有創(chuàng)建一個(gè)新進(jìn)程，撤消一個(gè)已經(jīng)運(yùn)行結(jié)束的進(jìn)程，以及改變進(jìn)程狀態(tài)、實(shí)現(xiàn)進(jìn)程間通信的能力。這樣的機(jī)構(gòu)屬于操作系統(tǒng)的內(nèi)核(Kernel)。內(nèi)核本身并不是一個(gè)或一組進(jìn)程，它是計(jì)算機(jī)系統(tǒng)硬件的首次延伸，它通過執(zhí)行各種原語(Primitive)操作來實(shí)現(xiàn)其控制功能。3.3進(jìn)程的控制

1.原語的定義

所謂“原語”，是指由若干條機(jī)器指令構(gòu)成的并用以完成特定功能的一段程序，這段程序在執(zhí)行期間是不可分割的。這就是說，原語的執(zhí)行不能被中斷，和機(jī)器指令相似，原語一旦開始執(zhí)行就“一口氣”地被執(zhí)行完，中間不允許插入別的操作。在當(dāng)今硬件日趨便宜的情況下，將這樣由幾條機(jī)器指令所構(gòu)成的原語固化為一條機(jī)器指令是完全可能的。不過當(dāng)前現(xiàn)有的操作系統(tǒng)中，大多數(shù)仍采用屏蔽中斷的辦法來保證原語操作的不可分割性。

2.進(jìn)程控制原語

上面我們已經(jīng)指出，操作系統(tǒng)的內(nèi)核是操作系統(tǒng)中最接近裸機(jī)的部分。通常內(nèi)核只占整個(gè)操作系統(tǒng)代碼中的一小部分。內(nèi)核的各項(xiàng)功能是通過執(zhí)行原語來實(shí)現(xiàn)的。

內(nèi)核中所包含的原語主要有進(jìn)程控制原語、進(jìn)程通信原語、資源管理原語以及其它方面的原語。

屬于進(jìn)程控制方面的原語有進(jìn)程創(chuàng)建原語、進(jìn)程撤消原語、進(jìn)程掛起原語、進(jìn)程激活原語、進(jìn)程阻塞原語以及進(jìn)程喚醒原語等。3.3.2進(jìn)程控制原語

1.進(jìn)程的建立

我們?cè)?jīng)講過，系統(tǒng)中同時(shí)存在的進(jìn)程數(shù)可達(dá)數(shù)十或數(shù)百之多。那么，這些進(jìn)程是怎樣建立起來的呢?通常有兩種方式來建立進(jìn)程：一種是在系統(tǒng)生成時(shí)就建立起一些系統(tǒng)進(jìn)程；另一種方法是利用創(chuàng)建原語來創(chuàng)建一個(gè)新進(jìn)程。用創(chuàng)建原語所建立的進(jìn)程主要是非常駐內(nèi)存的系統(tǒng)進(jìn)程和用戶進(jìn)程。當(dāng)某一進(jìn)程被分配去完成所規(guī)定的功能時(shí)，它能創(chuàng)建若干個(gè)子進(jìn)程使其各自負(fù)擔(dān)其中部分功能，子進(jìn)程又可以創(chuàng)建自己的子進(jìn)程，從而形成了進(jìn)程家族。圖3.7表示作業(yè)步進(jìn)程

A0，創(chuàng)建了子進(jìn)程B1、B2,子進(jìn)程又分別創(chuàng)建它們自己的子進(jìn)程C1、C2和C3，從而構(gòu)成了進(jìn)程的樹型結(jié)構(gòu)。其中進(jìn)程A0是該進(jìn)程家族的祖先。

在樹型結(jié)構(gòu)系統(tǒng)中，如果一個(gè)進(jìn)程創(chuàng)建了另一個(gè)進(jìn)程，則前者稱為父進(jìn)程，后者稱為子進(jìn)程。創(chuàng)建父進(jìn)程的進(jìn)程稱為祖父進(jìn)程。圖3.7進(jìn)程的樹型結(jié)構(gòu)樹型結(jié)構(gòu)系統(tǒng)的主要優(yōu)點(diǎn)是：

(1)資源分配嚴(yán)格。子進(jìn)程僅能分配到父進(jìn)程所擁有的資源，用完后立即歸還。一個(gè)進(jìn)程家族所占有的全部資源應(yīng)在其祖先所擁有的資源范圍內(nèi)。

(2)進(jìn)程控制靈活。可根據(jù)需要給進(jìn)程以不同的控制權(quán)力。當(dāng)一進(jìn)程被分配去完成某一任務(wù)時(shí)，可建立若干子進(jìn)程各自分擔(dān)其中的子任務(wù)。這些子任務(wù)可以并發(fā)地執(zhí)行。

(3)進(jìn)程層次清晰，關(guān)系明確。下面說明創(chuàng)建原語的功能和實(shí)現(xiàn)方法。

創(chuàng)建原語的功能是用來創(chuàng)建子進(jìn)程。其具體做法是：先向PCB集合索取一張空白PCB，并獲得PCB的內(nèi)部標(biāo)識(shí)數(shù)。若該進(jìn)程的程序不在內(nèi)存，應(yīng)將其調(diào)入內(nèi)存。然后，把創(chuàng)建者提供的PCB參數(shù)(如進(jìn)程外部標(biāo)識(shí)名，初始CPU狀態(tài)，優(yōu)先數(shù)及資源清單等)以及父進(jìn)程的內(nèi)部標(biāo)識(shí)數(shù)填入PCB中，并設(shè)置記帳信息，再置該進(jìn)程狀態(tài)為“靜止就緒”，最后把它插入進(jìn)程家族和就緒隊(duì)列中。這樣，子進(jìn)程就建立起來了。

2.狀態(tài)轉(zhuǎn)換原語

(1)掛起原語。當(dāng)需要把某個(gè)進(jìn)程掛起時(shí)可調(diào)用掛起原語。應(yīng)注意，對(duì)于樹型結(jié)構(gòu)系統(tǒng)，被掛起的進(jìn)程只能是它的子孫或其自身。可有多種掛起方式：把發(fā)出本原語的進(jìn)程自身掛起、掛起具有指定標(biāo)識(shí)名的進(jìn)程、把某進(jìn)程及其全部或部分“子孫”(例如具有指定優(yōu)先數(shù)進(jìn)程的子孫)進(jìn)程掛起?，F(xiàn)以掛起具有指定標(biāo)識(shí)名的進(jìn)程為例，說明掛起原語的操作步驟。

掛起原語的具體做法是：以被掛起的進(jìn)程標(biāo)識(shí)名為索引，到PCB集合中查找該進(jìn)程的PCB，得到該進(jìn)程的內(nèi)部標(biāo)識(shí)數(shù)，并檢查該進(jìn)程的狀態(tài)。若狀態(tài)為“運(yùn)行”，則中斷處理機(jī)，把CPU狀態(tài)保存在PCB中，停止運(yùn)行該進(jìn)程；若狀態(tài)為活躍阻塞，則改為靜止阻塞；若狀態(tài)為活躍就緒，則改為靜止就緒；若狀態(tài)為運(yùn)行，則從活躍就緒隊(duì)列中按某種算法選一進(jìn)程投入運(yùn)行。

(2)激活原語。在掛起原語的作用下，進(jìn)程的狀態(tài)由活躍轉(zhuǎn)為靜止。激活原語則使處于靜止?fàn)顟B(tài)的進(jìn)程變成活躍，即把“靜止就緒”變成“活躍就緒”，把“靜止阻塞”變成“活躍阻塞”。一旦被激活的進(jìn)程處于“活躍就緒”時(shí)，便引起處理機(jī)的重新調(diào)度。激活原語只能激活某進(jìn)程自己的子孫。同樣，激活原語也可以有多種激活方式：如激活一個(gè)具有指定標(biāo)識(shí)名的進(jìn)程，或者激活某進(jìn)程及其所有的子孫進(jìn)程。

由創(chuàng)建原語所創(chuàng)建的子進(jìn)程處于“靜止就緒”，若希望該進(jìn)程盡快獲得處理機(jī)，應(yīng)在創(chuàng)建原語后緊跟一個(gè)激活原語，使之變成活躍就緒，從而引起調(diào)度程序的重新調(diào)度。

(3)阻塞原語和喚醒原語。由運(yùn)行到活躍阻塞，由活躍阻塞到活躍就緒通常是在資源管理原語“請(qǐng)求”和“釋放”的作用下完成的。但在有的系統(tǒng)中，使用了阻塞原語和喚醒原語完成上述狀態(tài)的轉(zhuǎn)換。

當(dāng)一進(jìn)程所期待的某一事件尚未出現(xiàn)時(shí)，該進(jìn)程調(diào)用阻塞原語把自己阻塞起來，阻塞原語的操作過程如下：由于進(jìn)程正處于運(yùn)行狀態(tài)，故應(yīng)中斷處理機(jī)，把CPU狀態(tài)保護(hù)到PCB中，停止運(yùn)行該進(jìn)程。然后把“活躍阻塞”賦予該進(jìn)程，并把它插入到該事件的等待隊(duì)列中，再從活躍就緒隊(duì)列中按一定算法選取一進(jìn)程投入運(yùn)行。

當(dāng)某進(jìn)程所期待的事件出現(xiàn)時(shí)，由“發(fā)現(xiàn)者”進(jìn)程調(diào)用喚醒原語。發(fā)現(xiàn)者進(jìn)程可能與被喚醒進(jìn)程不直接相干，但通常與被喚醒進(jìn)程是合作的并發(fā)進(jìn)程。喚醒原語的操作是：將被喚醒進(jìn)程從相應(yīng)的等待隊(duì)列中摘除，狀態(tài)如為靜止阻塞改為靜止就緒；如為活躍阻塞改為活躍就緒并插入相應(yīng)的就緒隊(duì)列中；如為活躍就緒，還需引起調(diào)度程序的重新調(diào)度。

3.進(jìn)程的撤消

當(dāng)一個(gè)進(jìn)程在完成其規(guī)定的任務(wù)后，應(yīng)予以撤消。撤消也有兩種方式：僅撤消一個(gè)具有指定標(biāo)識(shí)名的進(jìn)程，或撤消該進(jìn)程及其所有子孫。前者可能導(dǎo)致被撤消的進(jìn)程子孫與進(jìn)程家族隔離，成為不可控的。因此，撤消原語應(yīng)采用第二種方式。

撤消原語的操作過程如下：以調(diào)用者提供的進(jìn)程標(biāo)識(shí)名為索引，到PCB集合中尋找相應(yīng)的PCB，獲得該進(jìn)程的內(nèi)部標(biāo)識(shí)數(shù)和狀態(tài)。若該進(jìn)程處于運(yùn)行狀態(tài)，則中斷處理機(jī)，保護(hù)CPU現(xiàn)場(chǎng)，停止執(zhí)行該進(jìn)程，并設(shè)置重新調(diào)度標(biāo)志。根據(jù)狀態(tài)指出的該進(jìn)程所在隊(duì)列，將其從隊(duì)列中消去。而且凡屬于該進(jìn)程的所有子孫也一律撤消。對(duì)于被撤消者所占有的資源，若它們是屬于撤消者或其祖先的，都應(yīng)歸還。凡是屬于被撤消者自己的，則消去它的資源描述塊，最后消去被撤消者的PCB，若重新調(diào)度標(biāo)志已置位，則重新調(diào)度。

3.4.1交通控制程序和進(jìn)程調(diào)度程序

1.交通控制程序

前面我們引進(jìn)了進(jìn)程的概念，并給出了進(jìn)程表示和進(jìn)程的調(diào)度狀態(tài)。系統(tǒng)中的各個(gè)進(jìn)程是怎樣運(yùn)行的，在進(jìn)程存在期間其狀態(tài)是怎樣變化的，操作系統(tǒng)中為數(shù)眾多的進(jìn)程又如何能保證協(xié)調(diào)一致的工作等問題是由處理機(jī)管理中的交通控制程序和進(jìn)程調(diào)度程序來解決的。3.4進(jìn)程調(diào)度交通控制程序(TrafficController)是J.H.Saltzer于1966年起的名字。他把操作系統(tǒng)中指揮各個(gè)進(jìn)程的工作比作一個(gè)交通警察，而把各個(gè)進(jìn)程比作車輛。它們之間有時(shí)要競(jìng)爭(zhēng)，有時(shí)要合作，交通警察就要保證它們協(xié)調(diào)一致，互不沖突。在操作系統(tǒng)中，交通控制程序的主要職能是管理進(jìn)程狀態(tài)之間的轉(zhuǎn)變和協(xié)調(diào)進(jìn)程間的通訊。例如，一個(gè)現(xiàn)運(yùn)行進(jìn)程因等待某一事件的到來，不能繼續(xù)運(yùn)行，就要調(diào)用交通控制程序使其狀態(tài)由運(yùn)行變?yōu)樽枞?，放棄自己的處理機(jī)。又如，某一現(xiàn)運(yùn)行進(jìn)程在運(yùn)行過程中，出現(xiàn)了另一進(jìn)程所期待的事件，那么現(xiàn)運(yùn)行進(jìn)程也要調(diào)用交通控制程序喚醒等待此事件的阻塞進(jìn)程，使其由阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。在所有的操作系統(tǒng)中，交通控制程序的功能都存在，但大多數(shù)的操作系統(tǒng)并未單獨(dú)設(shè)置交通控制程序，而是將其功能分散到各處，以原語或廣義指令的面貌出現(xiàn)。

2.進(jìn)程調(diào)度程序

在進(jìn)程狀態(tài)的變化中，從就緒到運(yùn)行的轉(zhuǎn)變是由一個(gè)專門的程序來完成的，該程序稱為進(jìn)程調(diào)度程序。進(jìn)程調(diào)度稱為“低級(jí)”調(diào)度，是相對(duì)作業(yè)調(diào)度而言的。進(jìn)程調(diào)度程序所要完成的是把一臺(tái)物理的CPU轉(zhuǎn)變?yōu)槎嗯_(tái)虛擬的CPU或者多臺(tái)邏輯的CPU。

3.進(jìn)程調(diào)度程序的功能

進(jìn)程調(diào)度程序的具體功能如下：

(1)記住系統(tǒng)中所有進(jìn)程的狀態(tài)、優(yōu)先數(shù)和資源需求情況。對(duì)于動(dòng)態(tài)優(yōu)先數(shù)，還需按一定算法定期地對(duì)它進(jìn)行計(jì)算。

(2)確定調(diào)度算法，決定把處理機(jī)分配給哪個(gè)進(jìn)程和分配多長時(shí)間。某個(gè)進(jìn)程正在運(yùn)行時(shí)，如果有優(yōu)先級(jí)更高的進(jìn)程進(jìn)入就緒隊(duì)列，是繼續(xù)運(yùn)行原進(jìn)程還是分配處理機(jī)給優(yōu)先級(jí)更高的進(jìn)程，由調(diào)度方式確定。

(3)分配處理機(jī)給進(jìn)程?，F(xiàn)運(yùn)行進(jìn)程調(diào)用進(jìn)程調(diào)度程序表示自己要放棄處理機(jī)，此時(shí)調(diào)度程序應(yīng)保護(hù)CPU現(xiàn)場(chǎng)，將狀態(tài)由運(yùn)行變成就緒或阻塞，并插入到相應(yīng)隊(duì)列中去，把相應(yīng)獲得CPU的進(jìn)程從就緒隊(duì)列中移出，恢復(fù)CPU現(xiàn)場(chǎng)，并改為運(yùn)行狀態(tài)。

進(jìn)程調(diào)度程序是操作系統(tǒng)的真正核心。它相當(dāng)于所有進(jìn)程的轉(zhuǎn)接站，如果我們把物理CPU看成是一臺(tái)裸機(jī)，那么加上這個(gè)進(jìn)程調(diào)度程序就變成了多臺(tái)邏輯上相同的CPU，只是速度慢了一些。3.4.2進(jìn)程調(diào)度算法的設(shè)計(jì)

1.引起進(jìn)程調(diào)度的時(shí)機(jī)

當(dāng)發(fā)現(xiàn)下述情況時(shí)，現(xiàn)運(yùn)行進(jìn)程使用的處理機(jī)被收回。

(1)現(xiàn)運(yùn)行進(jìn)程運(yùn)行結(jié)束或者因任務(wù)完成而正常結(jié)束，或者因出現(xiàn)錯(cuò)誤而異常結(jié)束。

(2)現(xiàn)運(yùn)行進(jìn)程因某種原因，比如I/O請(qǐng)求，從運(yùn)行進(jìn)入阻塞狀態(tài)。

(3)現(xiàn)運(yùn)行進(jìn)程執(zhí)行某種原語操作，如P操作、阻塞原語等，進(jìn)入阻塞狀態(tài)。

(4)一個(gè)具有更高優(yōu)先級(jí)的進(jìn)程要求使用處理機(jī)，即進(jìn)入就緒隊(duì)列(這與調(diào)度方式有關(guān))。

(5)分配給該進(jìn)程運(yùn)行的時(shí)間片已用完(這與系統(tǒng)類型有關(guān)，多用于分時(shí)系統(tǒng)中)。

2.進(jìn)程調(diào)度方式

所謂進(jìn)程調(diào)度方式，是指當(dāng)一個(gè)進(jìn)程正在處理機(jī)上運(yùn)行時(shí)，若有某個(gè)更為緊迫或更為重要的進(jìn)程需要進(jìn)行處理，或者說，如果有更高優(yōu)先級(jí)的進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，如何分配處理機(jī)。通常有兩種進(jìn)程調(diào)度方式：

(1)非剝奪方式。這種方式是讓原來正在運(yùn)行的進(jìn)程繼續(xù)運(yùn)行，直至該進(jìn)程完成或發(fā)生某種事件(如I/O請(qǐng)求)，而進(jìn)入“完成”或“阻塞”狀態(tài)時(shí)，才主動(dòng)放棄自己的處理機(jī)，把處理機(jī)分配給重要或緊迫的進(jìn)程，讓其運(yùn)行。

(2)剝奪方式?，F(xiàn)運(yùn)行進(jìn)程在運(yùn)行過程中，如有重要或緊迫的進(jìn)程到達(dá)(其狀態(tài)為就緒)，則現(xiàn)運(yùn)行進(jìn)程被迫放棄處理機(jī)，暫停原進(jìn)程的運(yùn)行并把處理機(jī)立即分配給新進(jìn)程。

3.進(jìn)程調(diào)度算法的選擇

進(jìn)程調(diào)度的主要任務(wù)就是按照一定的調(diào)度算法從就緒隊(duì)列中選出一個(gè)進(jìn)程，把CPU分配給它。調(diào)度算法的選擇與系統(tǒng)的設(shè)計(jì)目標(biāo)和系統(tǒng)工作效率密切相關(guān)。例如，有的算法有利于

系統(tǒng)資源的充分作用，有的算法有利于系統(tǒng)處理能力的充分發(fā)揮，有的算法有利于公平地響應(yīng)用戶的服務(wù)請(qǐng)求，如此等等。

與作業(yè)調(diào)度算法的選擇類似，進(jìn)程調(diào)度算法的選擇也要綜合各方面的因素，從中選擇一種切合實(shí)際、行之有效的算法。

進(jìn)程調(diào)度算法基本分為兩大類：優(yōu)先數(shù)法和時(shí)間片輪轉(zhuǎn)法，后面詳細(xì)敘述。

4.進(jìn)程隊(duì)列的組織

為了便于對(duì)進(jìn)程的調(diào)度和管理，須對(duì)進(jìn)程進(jìn)行合理的組織。

所謂對(duì)進(jìn)程進(jìn)行組織，實(shí)際上是對(duì)進(jìn)程控制塊PCB進(jìn)行組織。PCB的組織通常有兩種方式：

(1)線性表，如圖3.8(a)所示。此種方式是將系統(tǒng)中的所有PCB排列成一個(gè)表。

線性表的優(yōu)點(diǎn)是簡(jiǎn)單，所有的PCB均放在一個(gè)表中，無須復(fù)雜的申請(qǐng)、釋放操作及額外的指針。缺點(diǎn)是管理不夠方便，例如要查找某一個(gè)PCB，就要從頭掃描這個(gè)PCB表。圖3.8PCB的組織方式

(2)鏈接表或進(jìn)程隊(duì)列，如圖3.8(b)所示。這種方式是按照進(jìn)程的不同狀態(tài)，將其PCB放入不同的隊(duì)列中。在單處理機(jī)的情況下，運(yùn)行隊(duì)列只有一個(gè)進(jìn)程，即現(xiàn)運(yùn)行進(jìn)程。所有的就緒進(jìn)程排成一個(gè)隊(duì)列，用PCB中的鏈接指針指向下一個(gè)PCB，最后一個(gè)PCB的鏈接指針用“0”表示隊(duì)尾。

由于進(jìn)程被阻塞的原因不同，須建立多個(gè)阻塞隊(duì)列。每一隊(duì)列對(duì)應(yīng)一種阻塞原因，在同一隊(duì)列中用PCB中的隊(duì)列指針指向下一PCB，最后一個(gè)PCB的指針為“0”，表示隊(duì)尾。當(dāng)現(xiàn)運(yùn)行進(jìn)程因等待某一事件到來時(shí)，便將該進(jìn)程的PCB送入相應(yīng)的阻塞隊(duì)列；而某一事件出現(xiàn)時(shí)，就從相應(yīng)的阻塞隊(duì)列中取出，送入就緒隊(duì)列。鏈接表或進(jìn)程隊(duì)列方式可以使PCB的數(shù)目不受限制，可以動(dòng)態(tài)申請(qǐng)或釋放。由于各隊(duì)列分開，因此管理起來也就比較方便。其缺點(diǎn)是動(dòng)態(tài)分配PCB所占內(nèi)存的算法比較復(fù)雜，額外的指針也占用一定的存儲(chǔ)空間，并花費(fèi)一些操作時(shí)間。

在鏈接方式中，就緒隊(duì)列按何種次序排列PCB，將取決于進(jìn)程調(diào)度算法。3.4.3常用的進(jìn)程調(diào)度算法

1.靜態(tài)優(yōu)先級(jí)法

優(yōu)先級(jí)法按照進(jìn)程執(zhí)行任務(wù)的輕重緩急程度，使每一進(jìn)程都有一個(gè)調(diào)度的優(yōu)先級(jí)。優(yōu)先級(jí)的高低用優(yōu)先數(shù)表示。有的系統(tǒng)，優(yōu)先數(shù)越大，表示優(yōu)先級(jí)越高，優(yōu)先數(shù)越小，表示優(yōu)先級(jí)越低；有的系統(tǒng)則反之。系統(tǒng)在調(diào)度進(jìn)程時(shí)按優(yōu)先級(jí)從高到低進(jìn)行選擇。如果在進(jìn)程創(chuàng)建時(shí)就確定了它的優(yōu)先級(jí)(或優(yōu)先數(shù))，而且在進(jìn)程運(yùn)行過程中不再動(dòng)態(tài)改變，那么這種優(yōu)先級(jí)法稱為靜態(tài)優(yōu)先級(jí)法。靜態(tài)優(yōu)先級(jí)的確定方法有如下幾種：

(1)按進(jìn)程類型確定。通常，系統(tǒng)中有兩類進(jìn)程，即系統(tǒng)進(jìn)程和用戶進(jìn)程。在某些系統(tǒng)(如UNIX)中，一個(gè)進(jìn)程可以有兩種運(yùn)行狀態(tài)，即核心態(tài)和用戶態(tài)。系統(tǒng)中各進(jìn)程運(yùn)行速度以及系統(tǒng)資源的利用率在很大程度上依賴于系統(tǒng)進(jìn)程或在核心態(tài)下運(yùn)行的進(jìn)程。例如，若系統(tǒng)中某種共享輸入輸出設(shè)備由一系統(tǒng)進(jìn)程管理，那么使用這種設(shè)備的所有進(jìn)程的運(yùn)行速度都依賴于這一系統(tǒng)進(jìn)程。又如，負(fù)責(zé)存儲(chǔ)管理的進(jìn)程，其工作速度對(duì)用戶進(jìn)程也會(huì)產(chǎn)生重要影響。所以，系統(tǒng)進(jìn)程的優(yōu)先級(jí)應(yīng)高于用戶進(jìn)程，進(jìn)程在核心態(tài)下運(yùn)行的優(yōu)先級(jí)應(yīng)高于用戶態(tài)。

在批量處理與分時(shí)結(jié)合的系統(tǒng)中，為了加快與分時(shí)用戶的交互作用的速度，前臺(tái)作業(yè)的進(jìn)程優(yōu)先級(jí)應(yīng)高于后臺(tái)。

(2)按作業(yè)的資源要求確定。根據(jù)作業(yè)要求系統(tǒng)提供的處理機(jī)時(shí)間，內(nèi)存大小和I/O設(shè)備的類型、臺(tái)數(shù)來確定作業(yè)的優(yōu)先級(jí)。如果系統(tǒng)賦予作業(yè)的優(yōu)先級(jí)反比于作業(yè)的估計(jì)執(zhí)行時(shí)間，就形成了短作業(yè)優(yōu)先算法。由于作業(yè)的執(zhí)行時(shí)間事先難以確定，因此只能根據(jù)用戶提出的估計(jì)時(shí)間來確定。為防止用戶少報(bào)自己作業(yè)的執(zhí)行時(shí)間以獲得優(yōu)先服務(wù)，在采取短作業(yè)優(yōu)先算法時(shí)，應(yīng)采取適當(dāng)防備措施。

在有的系統(tǒng)中，分配給作業(yè)進(jìn)程的優(yōu)先級(jí)還取決于它所用的內(nèi)存大小。作業(yè)愈大，占用內(nèi)存愈多，分配給它的優(yōu)先級(jí)就愈低。顯然，不論是根據(jù)作業(yè)的執(zhí)行時(shí)間，還是根據(jù)作業(yè)占用內(nèi)存大小所確定的優(yōu)先級(jí)，都有利于短作業(yè)。這將使得作業(yè)的平均周轉(zhuǎn)時(shí)間最小，從而改善了調(diào)度性能。

(3)按作業(yè)到達(dá)時(shí)間確定。進(jìn)程的優(yōu)先級(jí)也可以按有關(guān)作業(yè)到達(dá)的時(shí)間依次排隊(duì)，使到達(dá)早的作業(yè)具有較高的優(yōu)先級(jí)。這種優(yōu)先級(jí)的確定方法構(gòu)成了先來先服務(wù)算法(FCFS)。

(4)按用戶類型和要求確定。計(jì)算機(jī)系統(tǒng)的用戶可按不同標(biāo)準(zhǔn)分類，但通常是與用戶類型和收費(fèi)標(biāo)準(zhǔn)有關(guān)。用戶的收費(fèi)標(biāo)準(zhǔn)越高，則賦予該用戶作業(yè)的進(jìn)程的優(yōu)先級(jí)也越高。因此，系統(tǒng)可以按用戶提出的要求設(shè)置進(jìn)程優(yōu)先級(jí)，即用戶花錢購買優(yōu)先級(jí)。

2.動(dòng)態(tài)優(yōu)先級(jí)法

靜態(tài)優(yōu)先級(jí)法實(shí)現(xiàn)起來比較簡(jiǎn)單，但不能反映系統(tǒng)以及進(jìn)程在運(yùn)行過程中發(fā)生的各種變化。如果能按照變化的情況對(duì)各個(gè)進(jìn)程的優(yōu)先級(jí)進(jìn)行適當(dāng)?shù)恼{(diào)整，可以獲得更好的調(diào)度效果。這就是動(dòng)態(tài)優(yōu)先級(jí)法。

在動(dòng)態(tài)地確定進(jìn)程優(yōu)先級(jí)時(shí)，同樣要考慮前述的一般原則，但實(shí)施起來可以更為精確。例如，一個(gè)進(jìn)程執(zhí)行不同程序段有輕重緩急之分，動(dòng)態(tài)優(yōu)先級(jí)法就可以不斷調(diào)整進(jìn)程的優(yōu)先級(jí)，使之產(chǎn)生相應(yīng)的高低變化。又如，各個(gè)進(jìn)程使用CPU的程度是動(dòng)態(tài)變化的，在分時(shí)系統(tǒng)中，為了使各個(gè)進(jìn)程比較均衡地使用它，可以根據(jù)進(jìn)程使用CPU的程度動(dòng)態(tài)地修改其優(yōu)先級(jí)。

3.時(shí)間片輪轉(zhuǎn)法

雖然優(yōu)先級(jí)的算法(靜態(tài)的或動(dòng)態(tài)的)用于多道批量處理系統(tǒng)可以獲得滿意的調(diào)度效果，但是在這種系統(tǒng)中，只能在優(yōu)先級(jí)高的進(jìn)程全部完成或發(fā)生某種事件后，才去執(zhí)行下一個(gè)進(jìn)

程。這樣，優(yōu)先級(jí)較低的進(jìn)程必須等待很長時(shí)間才能得到服務(wù)，這在分時(shí)系統(tǒng)中是絕對(duì)不允許的。為此，在分時(shí)系統(tǒng)中通常采用時(shí)間片輪轉(zhuǎn)法。在簡(jiǎn)單時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)把所有就緒進(jìn)程按FCFS規(guī)則排成一個(gè)隊(duì)列，首先將處理機(jī)分配給隊(duì)列中的第一個(gè)進(jìn)程，并規(guī)定執(zhí)行一定時(shí)間，例如100ms，該時(shí)間稱為時(shí)間片。當(dāng)該進(jìn)程用完這一時(shí)間片時(shí)，系統(tǒng)將它送至就緒隊(duì)列隊(duì)尾，又把處理機(jī)分配給下一進(jìn)程，再執(zhí)行同樣大小的時(shí)間片。這樣，就緒隊(duì)列中的所有進(jìn)程，就可以依次輪流獲得一個(gè)時(shí)間片的處理時(shí)間，然后系統(tǒng)又回到隊(duì)列的開始部分。如此不斷循環(huán)。在上述輪轉(zhuǎn)法中，如果一個(gè)進(jìn)程其時(shí)間片尚未用完而發(fā)生I/O請(qǐng)求，這時(shí)它進(jìn)入相應(yīng)的阻塞隊(duì)列，而不進(jìn)入就緒隊(duì)列。僅當(dāng)所要求的I/O請(qǐng)求完成時(shí)，才能重新返回到就緒隊(duì)列的末尾，等待下次運(yùn)行。在時(shí)間片輪轉(zhuǎn)法中，時(shí)間片是一個(gè)重要的參數(shù)。系統(tǒng)的響應(yīng)時(shí)間和時(shí)間片的關(guān)系，可以表示為：T=Nq，其中T為系統(tǒng)的響應(yīng)時(shí)間，q為時(shí)間片的大小，N為就緒隊(duì)列中的進(jìn)程數(shù)。顯然，時(shí)間片的大小對(duì)進(jìn)程調(diào)度有很大影響。如果q取得足夠大，以致所有進(jìn)程都能在分得的一個(gè)時(shí)間片內(nèi)執(zhí)行完畢，則此時(shí)的輪轉(zhuǎn)法就變成了FCFS法。這對(duì)于短作業(yè)，對(duì)于I/O操作多的作業(yè)都很不利。q的減小，可使調(diào)度效果得到改善，但是，q值很小時(shí)，則從一個(gè)進(jìn)程到另一個(gè)進(jìn)程的轉(zhuǎn)換時(shí)間就不可忽略。換言之，過小的q值會(huì)導(dǎo)致系統(tǒng)開銷的增加。因此，時(shí)間片的選擇必須適當(dāng)，通常為100ms。時(shí)間片的長短通常由以下因素確定：

(1)系統(tǒng)的響應(yīng)時(shí)間；

(2)就緒隊(duì)列中的進(jìn)程數(shù)；

(3)進(jìn)程的轉(zhuǎn)換時(shí)間；

(4)計(jì)算機(jī)的處理能力，計(jì)算機(jī)的速度越高，時(shí)間片就可越短。

簡(jiǎn)單輪轉(zhuǎn)法的優(yōu)點(diǎn)是方法簡(jiǎn)單，但由于采用固定時(shí)間片和僅有一個(gè)就緒隊(duì)列，故服務(wù)質(zhì)量不夠理想。為進(jìn)一步改變輪轉(zhuǎn)法的調(diào)度性能，應(yīng)做兩方面改進(jìn)：①將固定時(shí)間片改為可變

時(shí)間片；②將單就緒隊(duì)列改變?yōu)槎嗑途w隊(duì)列?？勺儠r(shí)間片輪轉(zhuǎn)法，可采用如下措施：

(1)系統(tǒng)的響應(yīng)時(shí)間固定，每次計(jì)算就緒隊(duì)列中的進(jìn)程數(shù)，記為Nmax，則時(shí)間片為q=T/Nmax。在這種方式中，每一輪開始時(shí)，系統(tǒng)便根據(jù)就緒隊(duì)列中已有的進(jìn)程數(shù)，計(jì)算一次q值，然后進(jìn)行輪轉(zhuǎn)。在此期間所到達(dá)的進(jìn)程都暫不進(jìn)入就緒隊(duì)列，等此次輪轉(zhuǎn)完畢再一并進(jìn)入。系統(tǒng)根據(jù)此時(shí)就緒隊(duì)列中的進(jìn)程數(shù)重新計(jì)算q值，然后開始下一輪循環(huán)。這種方法稱為固定周期輪轉(zhuǎn)法。

(2)時(shí)間片的長短取決于優(yōu)先級(jí)的高低。優(yōu)先級(jí)高的進(jìn)程分得的時(shí)間片長，優(yōu)先級(jí)低的進(jìn)程分得的時(shí)間片短。

(3)短作業(yè)的時(shí)間片短，長作業(yè)的時(shí)間片長。

4.多隊(duì)列輪轉(zhuǎn)法

如果一個(gè)進(jìn)程經(jīng)多次輪轉(zhuǎn)才能達(dá)到運(yùn)行的終點(diǎn)，那么系統(tǒng)的開銷就一定很大。為此，可采用多隊(duì)列輪轉(zhuǎn)法。例如，可設(shè)置三個(gè)就緒隊(duì)列，其時(shí)間片長度可分別規(guī)定為0.02s、0.2s、2s。若一個(gè)進(jìn)程運(yùn)行了0.02s后尚未結(jié)束，則進(jìn)入0.2s隊(duì)列的末尾。當(dāng)0.02s的隊(duì)列中每一進(jìn)程都輪轉(zhuǎn)了一次后，便調(diào)度0.2s的第一個(gè)進(jìn)程，接著依次運(yùn)行0.2s隊(duì)列中的各進(jìn)程，如果分得的0.2s的時(shí)間仍未運(yùn)行結(jié)束，則該進(jìn)程進(jìn)入2s隊(duì)列的末尾。對(duì)2s的隊(duì)列則采用循環(huán)輪轉(zhuǎn)法。在上述方法中，只有前一隊(duì)列中沒有進(jìn)程可以調(diào)度時(shí)，才選擇下一隊(duì)列中的進(jìn)程占用處理機(jī)。于是，短作業(yè)能夠較快地占用處理機(jī)，長作業(yè)一旦占用處理機(jī)，就可以使用較長時(shí)間，避免了因頻繁調(diào)度而增加系統(tǒng)開銷。3.4.4作業(yè)、進(jìn)程和程序之間的區(qū)別和聯(lián)系

至此為止，除了進(jìn)程之間通信和死鎖問題尚未講述外，有關(guān)進(jìn)程的定義、進(jìn)程的控制以及進(jìn)程的調(diào)度都講過了。應(yīng)該說，對(duì)進(jìn)程及其特性已有了進(jìn)一步的了解和認(rèn)識(shí)，現(xiàn)在有必要也能夠說清作業(yè)、進(jìn)程和程序三者之間的區(qū)別和聯(lián)系了。

1.用戶作業(yè)、進(jìn)程和程序之間的聯(lián)系

所謂一個(gè)作業(yè)，就是用戶在一次算題過程或一個(gè)事務(wù)處理中要求計(jì)算機(jī)系統(tǒng)所做工作的總和。在一個(gè)多道程序并發(fā)執(zhí)行的系統(tǒng)中，一個(gè)作業(yè)就是獨(dú)立于其它作業(yè)的工作單位。一個(gè)用戶作業(yè)通常包括程序、數(shù)據(jù)和操作說明書三部分。我們又知道，一個(gè)作業(yè)又可劃分為幾個(gè)作業(yè)步，這些作業(yè)步按順序執(zhí)行。當(dāng)一個(gè)作業(yè)被作業(yè)調(diào)度程序選中后，為其建立作業(yè)步進(jìn)程。系統(tǒng)的各個(gè)作業(yè)步進(jìn)程以及由它們所創(chuàng)建的子孫進(jìn)程，再加上若干系統(tǒng)進(jìn)程，進(jìn)程數(shù)就可以達(dá)到幾十~幾百個(gè)之多。當(dāng)系統(tǒng)中若干個(gè)作業(yè)同時(shí)開動(dòng)之后，這些為數(shù)眾多的進(jìn)程并發(fā)運(yùn)行的局面將復(fù)雜到無法描述的程度。這些進(jìn)程爭(zhēng)先恐后地向著目的地飛速前進(jìn)。若干個(gè)進(jìn)程完成其使命后被撤消了，但又產(chǎn)生了許多新的進(jìn)程，若干作業(yè)結(jié)束了，又調(diào)進(jìn)一批新的作業(yè)。因此，整個(gè)系統(tǒng)始終處于緊張狀態(tài)，不斷地運(yùn)行著，忙碌著。對(duì)于每一個(gè)進(jìn)程，我們知道，它由進(jìn)程控制塊、程序和數(shù)據(jù)集合組成。這說明程序是進(jìn)程的一部分，是進(jìn)程的實(shí)體。

由此，我們可以得到結(jié)論：一個(gè)作業(yè)可劃分為若干個(gè)進(jìn)程來完成，而每個(gè)進(jìn)程又都有其實(shí)體——程序和數(shù)據(jù)集合。

2.進(jìn)程和程序的區(qū)別

以下說明進(jìn)程和程序間的區(qū)別。

(1)進(jìn)程是程序的一次執(zhí)行，屬于一種動(dòng)態(tài)概念，而程序是一組有序的指令，是一種靜態(tài)概念。但是進(jìn)程離開了程序也就失去了存在的意義。因此，我們可以這樣說，進(jìn)程是程序執(zhí)行的動(dòng)態(tài)過程，而程序是進(jìn)程運(yùn)行的靜態(tài)文本。

(2)一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序；反之，同一程序可能由幾個(gè)進(jìn)程同時(shí)執(zhí)行。

(3)程序可以作為一種軟件資源長期保留，而進(jìn)程是程序的一次執(zhí)行過程，是暫時(shí)的。也就是說，進(jìn)程具有生命期。進(jìn)程由“創(chuàng)建”而產(chǎn)生，因“調(diào)度”而運(yùn)行，因得不到資源而阻塞，因“撤消”而死亡。

(4)進(jìn)程具有并發(fā)性，它能與其它進(jìn)程并發(fā)運(yùn)行。而一般的程序不具有這種明顯的特性。

(5)進(jìn)程是一個(gè)獨(dú)立的運(yùn)行單位，也是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。因此，進(jìn)程具有其獨(dú)立性。除了獨(dú)立性一面之外，另一方面進(jìn)程間又具有相互制約性，這種特性

表現(xiàn)為進(jìn)程之間的同步與互斥。

上面我們所講的進(jìn)程，說它是一個(gè)獨(dú)立的運(yùn)行單位，是指在不具有線程的系統(tǒng)中而言的。在引入線程的系統(tǒng)中，進(jìn)程不再是運(yùn)行(調(diào)度)的基本單位，只是資源分配的基本單位。下節(jié)我們將引入操作系統(tǒng)中另一基本的重要概念，即線程的概念。3.5.1線程概念的引入

在操作系統(tǒng)中引入進(jìn)程概念的目的在于提高系統(tǒng)效率，提高系統(tǒng)資源利用率。自從引入了進(jìn)程的概念后，操作系統(tǒng)便以進(jìn)程為單位在處理機(jī)上并發(fā)執(zhí)行。進(jìn)程不僅作為系統(tǒng)調(diào)度的基本單位，同時(shí)也是系統(tǒng)資源分配的基本單位。進(jìn)程因創(chuàng)建而產(chǎn)生，經(jīng)調(diào)度程序的調(diào)度而運(yùn)行，因等待某一事件而阻塞，最后因任務(wù)完成而被撤消。這就是說，進(jìn)程在整個(gè)生存期內(nèi)，不斷地改變其運(yùn)行環(huán)境。在進(jìn)程調(diào)度過程中，進(jìn)程切換更是經(jīng)常的。3.5線程及其管理在進(jìn)程切換時(shí)，由于要保留現(xiàn)運(yùn)行進(jìn)程的運(yùn)行環(huán)境，又要設(shè)置所選中進(jìn)程的運(yùn)行環(huán)境。為此要花費(fèi)不少處理機(jī)時(shí)間。因此，把進(jìn)程作為系統(tǒng)調(diào)度的基本單位要付出較大的時(shí)空開銷，從而也限制了系統(tǒng)中進(jìn)程的數(shù)量和進(jìn)程切換的頻率。為了提高系統(tǒng)的并行能力，把并行粒度進(jìn)一步減小，在進(jìn)程內(nèi)部又引入線程(Thread)的概念。在引入線程的操作系統(tǒng)中，線程是系統(tǒng)調(diào)度的基本單位，而不是獨(dú)立分配資源的基本單位，使之輕裝運(yùn)行，而對(duì)擁有資源的基本單位又不頻繁地對(duì)其切換。這樣，引入了線程概念后，既減少了系統(tǒng)的時(shí)空開銷，又增強(qiáng)了系統(tǒng)的并行能力。要實(shí)現(xiàn)并行性，采用多進(jìn)程方式不是也可以嗎?是的，問題在于采用線程比采用進(jìn)程實(shí)現(xiàn)并行性更方便、更有效?，F(xiàn)以UNIX為例，當(dāng)一個(gè)進(jìn)程創(chuàng)建一個(gè)子進(jìn)程時(shí)，系統(tǒng)必須把父進(jìn)程地址空間的所有內(nèi)容都拷貝到子進(jìn)程的地址空間中去。對(duì)于大地址空間來說，這樣的操作是很費(fèi)時(shí)的，更何況兩進(jìn)程還需建立共享數(shù)據(jù)。如果采用多線程來實(shí)現(xiàn)并行性就要好得多，因?yàn)檫@些線程共享進(jìn)程的同一地址空間以及其它資源。3.5.2什么是線程

1.線程的定義

線程可定義為“進(jìn)程內(nèi)的一個(gè)執(zhí)行單位”，或者定義為“進(jìn)程內(nèi)的一個(gè)可調(diào)度的實(shí)體”。

在具有多線程機(jī)制的操作系統(tǒng)中，處理機(jī)調(diào)度的基本單位不是進(jìn)程而是線程。負(fù)責(zé)處理機(jī)調(diào)度的程序稱為線程調(diào)度程序，它是操作系統(tǒng)內(nèi)核的重要組成部分，線程調(diào)度也是內(nèi)核的主要功能之一。

一個(gè)進(jìn)程可以有多個(gè)線程，而且至少有一個(gè)可執(zhí)行線程。

2.進(jìn)程和線程的關(guān)系

進(jìn)程和線程是構(gòu)造操作系統(tǒng)的兩個(gè)基本元素，是操作系統(tǒng)的兩個(gè)活動(dòng)部分，兩者的關(guān)系歸納如下：

(1)線程是進(jìn)程的一個(gè)組成部分。每個(gè)進(jìn)程在創(chuàng)建時(shí)通常只有一個(gè)線程，需要時(shí)這個(gè)線程可以創(chuàng)建其它線程。

(2)進(jìn)程的多線程都在進(jìn)程的地址空間活動(dòng)。

(3)資源是分給進(jìn)程的，而不是分給線程的。線程在執(zhí)行中需要資源時(shí)，系統(tǒng)從進(jìn)程的資源配額中扣除并分配給它。

(4)處理機(jī)調(diào)度的基本單位是線程，線程之間競(jìng)爭(zhēng)處理機(jī)，真正在處理機(jī)上運(yùn)行的是線程。

(5)線程在執(zhí)行過程中，需要同步。3.5.3WindowsNT中的進(jìn)程和線程

1.WindowsNT中的進(jìn)程

WindowsNT中，進(jìn)程被定義為“一個(gè)程序的動(dòng)態(tài)調(diào)用”。它由以下四部分組成：

(1)一個(gè)可執(zhí)行的程序，它定義了初始代碼和數(shù)據(jù)。

(2)一個(gè)私用地址空間，即進(jìn)程的虛擬地址空間。

(3)系統(tǒng)資源，例如信號(hào)量、通信端口、文件等。它們是在程序執(zhí)行時(shí)，由操作系統(tǒng)分配給它的。

(4)至少有一個(gè)執(zhí)行線程。

WindowsNT把進(jìn)程視為一個(gè)對(duì)象類。進(jìn)程對(duì)象是由NT執(zhí)行體中的對(duì)象管理程序創(chuàng)建或刪除的。

2.WindowsNT中的線程

WindowsNT中，線程和進(jìn)程一樣，也用對(duì)象來實(shí)現(xiàn)。線程由對(duì)象管理程序創(chuàng)建或刪除。

一個(gè)線程的基本組成是：

(1)一個(gè)惟一的標(biāo)識(shí)符，稱之為客戶ID。

(2)描述處理機(jī)狀態(tài)的一組寄存器內(nèi)容。

(3)兩個(gè)棧，分別用于用戶態(tài)和核心態(tài)下執(zhí)行。

(4)一個(gè)私用的存儲(chǔ)區(qū)。

3.WindowsNT中的線程調(diào)度

WindowsNT中線程的調(diào)度是WindowsNT內(nèi)核的主要任務(wù)之一。

WindowsNT的內(nèi)核與NT執(zhí)行體的其它部分不同的是：內(nèi)核永久駐留內(nèi)存，內(nèi)核的執(zhí)行是不可搶占的,并且總運(yùn)行在核心態(tài)。

WindowsNT的內(nèi)核采用微內(nèi)核技術(shù)，它提供了一組精心設(shè)計(jì)的操作系統(tǒng)原語和機(jī)制，通過這些原語和機(jī)制，執(zhí)行體可以構(gòu)造許多更高級(jí)的操作系統(tǒng)功能。WindowsNT內(nèi)核決定了操作系統(tǒng)如何使用處理機(jī)，整個(gè)操作系統(tǒng)的成功將依賴于內(nèi)核的正確、有效地操作。

線程調(diào)度的主要功能是選擇一個(gè)適當(dāng)?shù)木€程到處理機(jī)上去執(zhí)行并進(jìn)行描述表的切換。線程的描述表和描述表切換的過程因處理機(jī)的結(jié)構(gòu)而不同。典型的描述表切換要求保存原運(yùn)行線程的現(xiàn)場(chǎng)并裝入新運(yùn)行線程的現(xiàn)場(chǎng)，這些現(xiàn)場(chǎng)是指：

①程序計(jì)數(shù)器(PC)；

②處理機(jī)狀態(tài)寄存器(PSW)；

③其它寄存器內(nèi)容；

④用戶棧和核心棧指針；

⑤線程運(yùn)行的地址空間的指針(進(jìn)程頁表目錄)

當(dāng)一個(gè)線程被創(chuàng)建后，這個(gè)線程便開始了它的生命期。一旦被初始化，便要經(jīng)歷以下六種狀態(tài)，如圖3.9所示。圖3.9線程的調(diào)度狀態(tài)及其轉(zhuǎn)換

(1)就緒狀態(tài)：該線程已具備執(zhí)行條件以等待CPU的執(zhí)行，線程調(diào)度程序只從就緒線程池中選擇線程進(jìn)入備用狀態(tài)。

(2)備用狀態(tài)：系統(tǒng)中每個(gè)處理機(jī)上只能有一個(gè)線程處于備用狀態(tài)。處于備用狀態(tài)的線程已被選定為某一特定處理機(jī)的一個(gè)執(zhí)行對(duì)象。當(dāng)條件合適時(shí)，調(diào)度程序?yàn)樵摼€程進(jìn)行描述表切換。

(3)運(yùn)行狀態(tài)：一旦調(diào)度程序執(zhí)行完描述表切換，該線程便進(jìn)入了運(yùn)行狀態(tài)。

(4)等待狀態(tài)：以下情況可使線程進(jìn)入等待狀態(tài)：線程等待某一對(duì)象(事件)以便同步它的執(zhí)行；因I/O系統(tǒng)而等待；環(huán)境子系統(tǒng)導(dǎo)致線程自己阻塞。當(dāng)線程的等待結(jié)束，就回到就緒狀態(tài)。

(5)轉(zhuǎn)化狀態(tài)：如果線程已準(zhǔn)備好執(zhí)行，但由于資源不可用(如某核心棧所在頁面被換出主存)，從而成為轉(zhuǎn)化狀態(tài)。當(dāng)資源為可用時(shí)，線程便由轉(zhuǎn)化狀態(tài)進(jìn)入就緒狀態(tài)。

(6)終止?fàn)顟B(tài)：線程完成了它的執(zhí)行。

WindowsNT內(nèi)核的線程調(diào)度程序采用的調(diào)度算法是可搶占的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，即按線程的優(yōu)先級(jí)進(jìn)行調(diào)度，高優(yōu)先級(jí)的線程先被調(diào)度。

最初線程從創(chuàng)建它的進(jìn)程那里獲得基本優(yōu)先級(jí)，線程可將繼承的進(jìn)程基本優(yōu)先級(jí)改為稍高或稍低的優(yōu)先級(jí)。線程在執(zhí)行過程中，優(yōu)先級(jí)可以動(dòng)態(tài)改變。調(diào)度程序調(diào)度時(shí)所依據(jù)的主要數(shù)據(jù)結(jié)構(gòu)就是多優(yōu)先級(jí)就緒隊(duì)列。如前所述，系統(tǒng)中各進(jìn)程可以并發(fā)執(zhí)行，并以各自獨(dú)立的速度向前推進(jìn)。但另一方面，有時(shí)進(jìn)程之間存在著一定的制約關(guān)系。這種制約關(guān)系來源于并發(fā)進(jìn)程的合作以及對(duì)資源的共

享。體現(xiàn)在如下兩個(gè)方面：

第一，某一進(jìn)程若收不到另一進(jìn)程給它提供的必要信息就不能繼續(xù)運(yùn)行下去，這種情況表明了兩個(gè)進(jìn)程之間在某些點(diǎn)上要交換信息，相互交流運(yùn)行情況。這種制約關(guān)系的基本形式是：進(jìn)程—進(jìn)程，稱為直接制約關(guān)系。3.6進(jìn)程通訊第二，若某一進(jìn)程要求使用某一資源，而該資源正被另一進(jìn)程使用，并且這一資源不允許兩個(gè)進(jìn)程同時(shí)使用，那么該進(jìn)程只好等待已占用資源的進(jìn)程釋放后才能使用。這種制約關(guān)系的基本形式是：進(jìn)程—資源—進(jìn)程，稱為間接制約關(guān)系。

在進(jìn)程之間的這種相互依賴又相互制約、相互合作又相互競(jìng)爭(zhēng)的關(guān)系，意味著進(jìn)程之間需要某種形式的通訊，這主要表現(xiàn)為同步和互斥兩個(gè)方面。3.6.1進(jìn)程間的同步和互斥

1.進(jìn)程間的同步

一般來說，一個(gè)進(jìn)程相對(duì)另一進(jìn)程的運(yùn)行速度是不確定的。也就是說，進(jìn)程之間是在異步環(huán)境下運(yùn)行的，每個(gè)進(jìn)程都以各自獨(dú)立的、不可預(yù)知的速度向運(yùn)行的終點(diǎn)推進(jìn)。但是相互合作的幾個(gè)進(jìn)程需要在某些確定點(diǎn)上協(xié)調(diào)它們的工作。一個(gè)進(jìn)程到達(dá)了這些點(diǎn)后，除非另一進(jìn)程已完成了某些操作，否則就不得不停下來等待這些操作的結(jié)束。這就是進(jìn)程間的同步。在現(xiàn)實(shí)生活中，同步的例子也是俯拾即是的。例如，在一輛公共汽車上，司機(jī)和售票員各行其職，獨(dú)立工作。司機(jī)負(fù)責(zé)開車和到站停車；售票員負(fù)責(zé)售票和開、關(guān)車門。但兩者需要密切配合、協(xié)調(diào)一致。即當(dāng)司機(jī)駕駛的車輛到站并把車輛停穩(wěn)后，售票員打開車門，讓乘客上、下車，然后關(guān)好車門，這時(shí)汽車司機(jī)繼續(xù)開車行駛。由此例可以看出，汽車司機(jī)和售票員之間的同步關(guān)系，如圖3.10所示。圖3.10司機(jī)和售票員的同步又如，有用戶作業(yè)程序，其形式是：

Z=func1(x)*func2(y)

其中func1(x)，func2(y)均是一個(gè)復(fù)雜函數(shù)，為了加快本題的計(jì)算速度，可用兩個(gè)進(jìn)程P1、P2各計(jì)算一個(gè)函數(shù)。進(jìn)程P2計(jì)算func2(y)，進(jìn)程P1在計(jì)算完func1(x)之后，與進(jìn)程P2的計(jì)算結(jié)果相乘，以獲得最終結(jié)果Z。

進(jìn)程P1在計(jì)算完func1(x)之后，檢測(cè)進(jìn)程P2的結(jié)果是否已經(jīng)算好，如未算好，則進(jìn)入阻塞狀態(tài)；如果進(jìn)程P2已經(jīng)算完，則進(jìn)程P1取其計(jì)算結(jié)果，然后進(jìn)行乘法運(yùn)算，最后得到Z。進(jìn)程P2在計(jì)算出func2(y)之后，要設(shè)置計(jì)算完成標(biāo)志，供P1檢測(cè)，并向進(jìn)程P1發(fā)一信號(hào)，將進(jìn)程P1喚醒。

進(jìn)程P1和P2之間的同步示于圖3.11中。

在操作系統(tǒng)中，各系統(tǒng)進(jìn)程之間也存在著大量的同步操作。圖3.11進(jìn)程P1和P2間的同步

2.進(jìn)程間的互斥

在各協(xié)同工作的進(jìn)程之間存在著同步關(guān)系，但進(jìn)程之間更為一般的關(guān)系卻是互斥關(guān)系。這是由于進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源所引起的。例如，有兩個(gè)進(jìn)程P1、P2，它們都要使用打印機(jī)，如果讓它們隨意使用，那么就有可能出現(xiàn)這種情況，P1打印幾行接著P2再打印幾行，打印結(jié)果混在一起，很難區(qū)分，即使能夠區(qū)分，也要將各自輸出結(jié)果從打印紙上剪下來，再用漿糊粘接起來。解決這一問題的辦法是，不允許一臺(tái)打印機(jī)讓兩個(gè)進(jìn)程同時(shí)使用，應(yīng)在一個(gè)進(jìn)程用完后再讓另一進(jìn)程使用。由此可見，系統(tǒng)中存在許多進(jìn)程，它們共享各種資源，然而有很多資源一次只能供一個(gè)進(jìn)程使用。我們把一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源(CriticalResource)。很多物理設(shè)備都屬于臨界資源，如輸入機(jī)、打印機(jī)、磁帶機(jī)等。除了物理設(shè)備外，還有很多變量、數(shù)據(jù)、表格、隊(duì)列等也都由若干進(jìn)程所共享，通常它們也不允許兩個(gè)進(jìn)程同時(shí)使用，故也屬于臨界資源。臨界資源也稱可逐次再使用資源。兩個(gè)或兩個(gè)以上進(jìn)程由于不能同時(shí)使用同一臨界資源，只能一個(gè)進(jìn)程使用完了，另一進(jìn)程才能使用，這種現(xiàn)象稱為進(jìn)程互斥，故臨界資源也稱互斥資源。以下給出進(jìn)程互斥和臨界區(qū)的例子。如圖3.12所示，設(shè)有進(jìn)程A、B，在其運(yùn)行中它們要求使用臨界資源R(比如打印機(jī)或輸入機(jī))。進(jìn)程A在①點(diǎn)提出使用要求，由于資源R未被其它進(jìn)程使用，故進(jìn)程A開始使用。在進(jìn)程A使用過程中，進(jìn)程B在②點(diǎn)也提出對(duì)資源R的請(qǐng)求。由于R是臨界資源，故進(jìn)程B的請(qǐng)求不能被滿足，于是進(jìn)程B被阻塞，等待進(jìn)程A對(duì)資源的釋放。進(jìn)程A在③點(diǎn)釋放了資源R，表示該資源不再使用，同時(shí)喚醒等待該資源的進(jìn)程B，進(jìn)程B從阻塞狀態(tài)進(jìn)入就緒狀態(tài)。當(dāng)進(jìn)程調(diào)度程序再次調(diào)度到進(jìn)程B時(shí)，它就開始使用資源R了，而且資源R只能供進(jìn)程B自己使用，不允許其它進(jìn)程使用。圖3.12資源互斥使用例又如，設(shè)有兩個(gè)進(jìn)程P1、P2，它們共享同一變量count,P1、P2的主要操作如下：

P1：R1∶=count;P2:R2∶=count;

R1∶=R1+1; R2∶=R2+1;

count∶=R1; count∶=R2;

其中，R1和R2是處理機(jī)的兩個(gè)通用寄存器。這兩個(gè)進(jìn)程各自對(duì)count進(jìn)行加1操作，兩個(gè)進(jìn)程共同訪問和修改的結(jié)果使count加2，這是我們所期望的。但我們知道，P1、P2是兩個(gè)并發(fā)執(zhí)行的進(jìn)程，它們可以按各自獨(dú)立的速度前進(jìn)，所以運(yùn)行的順序也可能是：

P1:R1∶=count;

P2:R2∶=count;

P1:R1∶=R1+1;count∶=R1;

P2:R2∶=R2+1;count∶=R2;顯然，此時(shí)的效果是使變量count只增加了1。為什么會(huì)有這種錯(cuò)誤的結(jié)果呢?主要原因是沒有把變量count當(dāng)作臨界資源來對(duì)待，沒有實(shí)施互斥操作。如果我們把變量count當(dāng)作臨界資源，一次只允許一個(gè)進(jìn)程進(jìn)行訪問和修改，即僅當(dāng)進(jìn)程P1對(duì)count進(jìn)行修改并退出后，進(jìn)程P2才允許訪問和修改，那么就可以避免上述的錯(cuò)誤結(jié)果。這就是說，為幾個(gè)進(jìn)程共享的數(shù)據(jù)結(jié)構(gòu)、變量等也應(yīng)作為臨界資源來處理。各進(jìn)程對(duì)臨界資源操作的程序段的執(zhí)行應(yīng)該是互斥的。我們把這種互斥執(zhí)行的程序段稱為臨界區(qū)(CriticalSection)或互斥段。

由此可見，對(duì)系統(tǒng)中任何一個(gè)進(jìn)程來說，其工作正確與否不僅取決于它自身的正確性，而且與它在執(zhí)行中能否與其它相關(guān)進(jìn)程正確地實(shí)施同步或互斥有關(guān)，所以解決進(jìn)程間的同步和互斥是非常重要的問題。

3.實(shí)現(xiàn)臨界區(qū)互斥的鎖操作法

上面我們給出了臨界資源和臨界區(qū)的定義。為禁止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，必須有一相應(yīng)機(jī)構(gòu)來協(xié)調(diào)它們，這一機(jī)構(gòu)應(yīng)遵循下述原則：

(1)當(dāng)有若干進(jìn)程要求進(jìn)入它們的臨界區(qū)時(shí)，應(yīng)在有限時(shí)間內(nèi)使一進(jìn)程進(jìn)入臨界區(qū)。換句話說，它們不應(yīng)相互等待而致使誰都不能進(jìn)入。

(2)每次最多有一個(gè)進(jìn)程處于臨界區(qū)內(nèi)。

(3)進(jìn)程在臨界區(qū)內(nèi)逗留應(yīng)在有限時(shí)間范圍內(nèi)。下面給出實(shí)現(xiàn)臨界區(qū)互斥的鎖操作法：

這種方法使用了一個(gè)物理實(shí)體，稱為鎖，用W來表示。鎖有兩種狀態(tài)：W=0表示鎖已打開；W=1表示鎖被關(guān)閉。

加鎖原語用LOCK(W)表示，其操作為：

測(cè)試W，若W=1，表示資源正在使用，繼續(xù)反復(fù)測(cè)試；若W=0，置W=1(加鎖)。

加鎖原語用LOCK(W)表示，可描述為

L:ifW=1thengotoLelseW∶=1;

開鎖原語用UNLOCK(W)表示，可描述為

W∶=0；于是，兩個(gè)進(jìn)程P1、P2使用如下程序?qū)嵤┻M(jìn)程的互斥：

進(jìn)程P1 進(jìn)程P2

LOCK(W) LOCK(W)

S1

S2

UNLOCK(W) UNLOCK(W)

其中S1和S2分別為進(jìn)程P1和P2的臨界區(qū)。在有些系統(tǒng)中，上述的加鎖、開鎖操作可用機(jī)器硬件指令完成。例如IBM/370中就有一條稱為“測(cè)試并置位”指令TS。該指令的功能是按第二操作域指出的地址從主存中取出一個(gè)字節(jié)，其最高位(最左邊的位)為0時(shí)，置條件碼為0；否則置條件碼為1，并將該字節(jié)的所有位均置1。于是加鎖原語LOCK(W)可用指令

TSW

BNZ*-4

來代替，其中BNZ表示不等于0轉(zhuǎn)移，*-4表示本指令地址減4(BNZ本身是4字節(jié)指令)。即當(dāng)W不為0時(shí)轉(zhuǎn)移到上一條指令TS繼續(xù)測(cè)試，否則停止測(cè)試，進(jìn)入臨界區(qū)。請(qǐng)注意，測(cè)試W和置W=1是在一個(gè)指令周期內(nèi)完成的。開鎖原語UNLOCK(W)用指令

MVIW，X′00′

來完成，MVI將一個(gè)全0的字節(jié)送入W中。用加鎖和開鎖的方法實(shí)現(xiàn)臨界區(qū)互斥，其效率很低。因?yàn)橹灰粋€(gè)進(jìn)程進(jìn)入臨界區(qū)后，其它企圖進(jìn)入臨界區(qū)的進(jìn)程，在執(zhí)行LOCK(W)時(shí)，因不斷測(cè)試W造成處理機(jī)時(shí)間的浪費(fèi)。此時(shí)CPU一直處于忙碌狀態(tài)，以等待W為0。為此，E.W.Dijkstra提出了一種解決同步、互斥問題的更一般的方法，這就是信號(hào)量(Semaphore)以及有關(guān)的P、V操作。3.6.2信號(hào)量和P、V操作

1.信號(hào)量及P、V操作

信號(hào)量或信號(hào)燈是交通管理中的一種常用設(shè)備。交通管理人員利用信號(hào)燈的顏色(紅、綠)實(shí)現(xiàn)交通管理。在操作系統(tǒng)中，信號(hào)量是表示資源的實(shí)體，是一個(gè)與隊(duì)列有關(guān)的整型變量，其值僅能由P、V操作來改變。操作系統(tǒng)利用信號(hào)量對(duì)進(jìn)程和資源進(jìn)行控制和管理。根據(jù)用途不同，分為公用信號(hào)量和私用信號(hào)量。公用信號(hào)量通常用于實(shí)現(xiàn)進(jìn)程之間的互斥，初值為1，它所聯(lián)系的一組并發(fā)進(jìn)程均可對(duì)其實(shí)施P、V操作；私用信號(hào)量一般用于實(shí)現(xiàn)進(jìn)程間的同步，初值為0或?yàn)槟硞€(gè)正整數(shù)n，僅允許擁有它的進(jìn)程對(duì)其實(shí)施P操作。

P、V操作是定義在信號(hào)量S上的兩個(gè)操作，其定義如下：

P(S)：①S∶=S-1;

②若S≥0，則調(diào)用P(S)的進(jìn)程繼續(xù)運(yùn)行；

③若S<0，則調(diào)用P(S)的進(jìn)程被阻塞，并把它插入到等待信號(hào)量S的阻塞隊(duì)列中。

V(S)：①S∶=S+1;

②若S>0，則調(diào)用V(S)的進(jìn)程繼續(xù)運(yùn)行；

③若S≤0，從等待信號(hào)量S的阻塞隊(duì)列中喚醒頭一個(gè)進(jìn)程，然后調(diào)用V(S)的進(jìn)程繼續(xù)運(yùn)行。

P、V操作可表示為如下兩個(gè)過程：

ProcedureP(VarS：Semaphore);

beginS∶=S-1;

ifS<0thenW(S)

end;{P}

ProcedureV(VarS：Semaphore);

beginS∶=S+1;

ifS≤0thenR(S)

end;{V}

其中，W(S)表示將調(diào)用該過程的進(jìn)程置成等待信號(hào)量S的阻塞狀態(tài)，并插入相應(yīng)的阻塞隊(duì)列中；R(S)表示要喚醒等待信號(hào)量S阻塞隊(duì)列中的頭一個(gè)進(jìn)程。

Dijkstra提出的P、V操作是能夠?qū)崿F(xiàn)對(duì)臨界區(qū)管理要求的兩條原語，現(xiàn)在分析一下這兩條原語。當(dāng)信號(hào)量的初值為1時(shí)，如果有若干個(gè)進(jìn)程都要求進(jìn)入臨界區(qū)時(shí)，由于每個(gè)進(jìn)程都要調(diào)用P(S)過程，則只有第一個(gè)調(diào)用P(S)的進(jìn)程，執(zhí)行P操作而使S為0，立即進(jìn)入臨界區(qū)；而其余進(jìn)程在執(zhí)行完P(guān)操作后，由于S變?yōu)樨?fù)值而進(jìn)入阻塞，被插入到等待信號(hào)量S的阻塞隊(duì)列中。由于信號(hào)量S的初值為1，P操作起到了限制一次只有一個(gè)進(jìn)程進(jìn)入臨界區(qū)的作用。任何一個(gè)進(jìn)程，在執(zhí)行完臨界區(qū)操作后，在退出臨界區(qū)前必須調(diào)用V操作，從而保證了進(jìn)程在臨界區(qū)內(nèi)逗留有限時(shí)間。當(dāng)一個(gè)進(jìn)程退出臨界區(qū)時(shí)，如有進(jìn)程在等待進(jìn)入臨界區(qū)，V操作將喚醒位于阻塞隊(duì)列中的頭一個(gè)進(jìn)程，使其可以進(jìn)入臨界區(qū)，因而不會(huì)出現(xiàn)進(jìn)程無限等待進(jìn)入臨界區(qū)的情況，這完全符合對(duì)臨界區(qū)管理的三條原則。以下舉例說明如何利用信號(hào)量和P、V操作實(shí)現(xiàn)進(jìn)程互斥和同步。

2.利用信號(hào)量實(shí)現(xiàn)進(jìn)程的互斥

利用信號(hào)量可以方便地解決臨界區(qū)問題。設(shè)S為兩進(jìn)程互斥的公用信號(hào)量，初值賦予1，表明該臨界資源未被占用。只需把臨界區(qū)的程序段置于P(S)和V(S)之間，即可實(shí)現(xiàn)兩進(jìn)程的互斥。例如進(jìn)程P1和進(jìn)程P2按如下安排，即可實(shí)現(xiàn)互斥：

進(jìn)程P1進(jìn)程P2

P(S) P(S)

S1 S2

V(S) V(S)

其中的S1、S2是兩個(gè)互斥的程序段，即P1、P2的臨界區(qū)。由于信號(hào)量的初值為1，故第一個(gè)進(jìn)程P1執(zhí)行P操作后信號(hào)量減為0，表明臨界資源空閑，可分配給該進(jìn)程，使之進(jìn)入臨界區(qū)。若此時(shí)又有第二個(gè)進(jìn)程P2欲進(jìn)入臨界區(qū)，也應(yīng)先執(zhí)行P操作。結(jié)果使S=-1，表示臨界資源已被占用，因此第二進(jìn)程變?yōu)樽枞麪顟B(tài)。當(dāng)?shù)谝贿M(jìn)程在臨界區(qū)內(nèi)將S1執(zhí)行完后執(zhí)行V操作，釋放該資源而使信號(hào)量恢復(fù)到0，又喚醒了第二個(gè)進(jìn)程P2。待第二個(gè)進(jìn)程P2完成對(duì)臨界資源的使用(S2)后，又執(zhí)行V操作，最后使信號(hào)量恢復(fù)到初值1。由此例可以看出：信號(hào)量S>0時(shí)的數(shù)值表示某類可用資源的數(shù)量，執(zhí)行P操作意味著申請(qǐng)分配一個(gè)單位的資源。因此可描述為S∶=S-1，當(dāng)S≤0時(shí)，表示已無資源可用，此時(shí)S的絕對(duì)值表示信號(hào)量S的阻塞隊(duì)列中的進(jìn)程數(shù)；而執(zhí)行一次V操作意味著釋放一個(gè)單位的資源，描述為S∶=S+1，若此時(shí)S≤0，表明信號(hào)量的阻塞隊(duì)列中仍有被阻塞的進(jìn)程，因此在執(zhí)行V操作時(shí)應(yīng)喚醒該隊(duì)列的第一個(gè)進(jìn)程。

例3-1

前面例子中的公用變量count,也是一個(gè)臨界資源。

兩個(gè)并發(fā)進(jìn)程對(duì)count的操作必須互斥地執(zhí)行。對(duì)此，可寫出如下程序：

begin

count:integer;

S∶semaphore;

count∶=0;S∶=1;

cobegin

processp1

R1:register;

begin

P(S);

R1∶=count;

R1∶=R1+1;

count∶=R1;

V(S)

end; processP2

R2:register;

begin

P(S);

R2∶=count;

R2∶=R2+1;

count∶=R2;

V(S)

end;

coend;

end;

例3-2

設(shè)一民航航班售票系統(tǒng)有n個(gè)售票處。每個(gè)售票

處通過終端訪問系統(tǒng)中的公用數(shù)據(jù)區(qū)，假定公共數(shù)據(jù)區(qū)中一些單元xk(k=1,2,…)分別存放×月×日×次航班的現(xiàn)存票數(shù)。設(shè)P1，P2，…，Pn

表示各售票處的處理進(jìn)程，R1,R2,…,Rn表示各進(jìn)程執(zhí)行時(shí)所用的工作單元。用信號(hào)量實(shí)現(xiàn)進(jìn)程間互斥的程序如下：

begin

S:Semaphore;

S∶=1

cobegin

ProcessPi(i=1,2,…,n)

begin

按旅客訂票要求找到xk;

P(S)

Ri∶=xk; ifR1≥1thenbeginRi∶=Ri-1;

xk∶=R1;

V(S)

輸出一張票

end

elsebeginV(S);

輸