計(jì)算機(jī)三級(jí)進(jìn)程管理課件

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

進(jìn)程是操作系統(tǒng)中最重要的概念之一在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，進(jìn)程不僅是最基本的并發(fā)執(zhí)行單位，而且也是分配資源、交換信息的基本單位。而進(jìn)程管理則是操作系統(tǒng)中最重要且最復(fù)雜的管理。第二章進(jìn)程管理1

§2．１前趨圖一程序的順序執(zhí)行與特征1．

程序的順序執(zhí)行

一個(gè)程序通?？煞殖扇舾蓚€(gè)程序段，它們必須按照某種先后次序執(zhí)行，僅當(dāng)前一操作執(zhí)行完后，才能執(zhí)行后繼操作。§2．１前趨圖2C1P1I1C1P1I1C1P1I2C2P2C1P1I1C1P1I1C1P1I2C2P23

程序順序執(zhí)行時(shí)的特征（1）順序性。處理機(jī)的操作嚴(yán)格按照程序規(guī)定的順序執(zhí)行，即只有前一操作結(jié)束后，才能啟動(dòng)后一操作的執(zhí)行；（2）封閉性。程序在封閉的環(huán)境下運(yùn)行，并獨(dú)占全機(jī)，因此機(jī)內(nèi)資源的狀態(tài)只有運(yùn)行程序的操作才能改變它，其執(zhí)行結(jié)果不受外界因素的影響；（3）可再現(xiàn)性。只要程序執(zhí)行時(shí)環(huán)境和初始條件相同，程序經(jīng)多次運(yùn)行后所得的結(jié)果必然相同。程序順序執(zhí)行時(shí)的特征4514236789二

前趨圖的定義前趨圖是一個(gè)有向無環(huán)圖，記為DAG。如圖所示：有向無環(huán)圖123456789514236789二前趨圖的定義有向無環(huán)圖123455

三

程序的并發(fā)執(zhí)行與特征1雖然對(duì)于一個(gè)程序的輸入、計(jì)算和打印必須順序執(zhí)行，但在對(duì)一批程序進(jìn)行處理時(shí)，則可使上述三種操作并發(fā)執(zhí)行，以提高系統(tǒng)的吞吐量。例如，輸入程序在輸入第三個(gè)程序（I3）的同時(shí)，計(jì)算程序可以正在對(duì)第二個(gè)程序進(jìn)行計(jì)算（C2），而打印程序正在打印第一個(gè)程序（Ｐ1）的計(jì)算結(jié)果。如下圖所示：I1I2I3I4C1C2C3C4P1P2P3P4程序段并發(fā)執(zhí)行的有向圖

三

程序的并發(fā)執(zhí)行與特征I1I2I3I4C1C2C3C6

程序的并發(fā)執(zhí)行（concurrence）指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。在多道程序環(huán)境下，并發(fā)是指宏觀上在一段時(shí)間內(nèi)有多道程序在同時(shí)運(yùn)行，而微觀上這些程序是在交替地執(zhí)行。

（并行(parallel)指兩個(gè)或多個(gè)事件在同一時(shí)刻進(jìn)行，例如，在具有中斷的計(jì)算機(jī)系統(tǒng)中，CPU可以和I/O設(shè)備并行執(zhí)行。

程序的并發(fā)執(zhí)行雖然提高了系統(tǒng)的吞吐量，但也產(chǎn)生了下述一些新特征：程序的并發(fā)執(zhí)行（concurrence）7２．程序并發(fā)執(zhí)行所帶來的影響（特征）（１）間斷性相互制約將導(dǎo)致并發(fā)程序具有“執(zhí)行－暫停－執(zhí)行”這種間斷性的活動(dòng)規(guī)律。（２）失去封閉性

程序在并發(fā)執(zhí)行時(shí)，是多個(gè)程序共享一臺(tái)機(jī)器，因而機(jī)內(nèi)資源的狀態(tài)將由多個(gè)程序來改變，因此使程序的運(yùn)行已失去了封閉性，這樣，某程序在執(zhí)行時(shí)，也必然會(huì)受到其他程序的影響，例如，當(dāng)處理機(jī)資源被其他程序占有時(shí)，某程序必須等２．程序并發(fā)執(zhí)行所帶來的影響（特征）8（３）不可再現(xiàn)性程序在并發(fā)執(zhí)行時(shí)，也將失去其可再現(xiàn)性。例如，有兩個(gè)循環(huán)程序A和B，它們共享一個(gè)變量n。程序A每執(zhí)行一次時(shí)都要做n：=n+1操作；程序B則每執(zhí)行一次都要執(zhí)行print（n）操作，然后再將N置成“０”。如下程序段所示:varn:integer;beginn:=0;cobeginprogramA:beginrepeat…n:=n+1;remainderofprogramAuntilfalseend;programB:beginrepeat…printn;n:=0;remainderofprogramBuntilfalseend;coendend;（３）不可再現(xiàn)性程序在并發(fā)執(zhí)行時(shí)，也將失去其可再現(xiàn)性。例9

§2．2進(jìn)程的基本概念

由上所述可知，程序并發(fā)執(zhí)行時(shí)，產(chǎn)生了一些新特征，致使一般的程序不能并發(fā)執(zhí)行。例如，程序在執(zhí)行中一旦受阻而停下來時(shí)，系統(tǒng)無法保留該程序的現(xiàn)場(chǎng)，因而也就無法再恢復(fù)該程序的現(xiàn)場(chǎng)并以繼續(xù)執(zhí)行。為了使程序在多道程序環(huán)境下能并發(fā)執(zhí)行，并能對(duì)并發(fā)執(zhí)行的程序加以控制和描述，而專門為之配置了一個(gè)稱為“進(jìn)程控制塊”的數(shù)據(jù)結(jié)構(gòu)。其中，存放了進(jìn)程標(biāo)識(shí)符、進(jìn)程運(yùn)行的當(dāng)前狀態(tài)、程序和數(shù)據(jù)的地址，以及能保存該程序運(yùn)行時(shí)CPU的環(huán)境信息。由程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分構(gòu)成了進(jìn)程的實(shí)體?！?．2進(jìn)程的基本概念10一、進(jìn)程的定義和特征

1.進(jìn)程的定義

至此，已知程序并發(fā)執(zhí)行產(chǎn)生了一系列新特點(diǎn)，為了能對(duì)并發(fā)程序的執(zhí)行加以描述而引入了進(jìn)程的概念。曾有許多人從不同角度對(duì)進(jìn)程下過各種定義，其中較典型的進(jìn)程定義有：

進(jìn)程是程序的一次執(zhí)行。

進(jìn)程是一個(gè)程序及其數(shù)據(jù)，在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。

進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。

進(jìn)程是可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程。

第三個(gè)定義比較準(zhǔn)確，它包含了進(jìn)程的主要特征。這里，我們?cè)谠摱x的基礎(chǔ)上加以修改后，可把進(jìn)程定義為：進(jìn)程是程序的一次執(zhí)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位，動(dòng)態(tài)產(chǎn)生和動(dòng)態(tài)消亡，它可以和其他程序并發(fā)執(zhí)行。一、進(jìn)程的定義和特征112．進(jìn)程的特征進(jìn)程和程序是兩個(gè)截然不同的概念。進(jìn)程具有五個(gè)基本特征，而程序則沒有。（1）

動(dòng)態(tài)性進(jìn)程的實(shí)質(zhì)是程序的一次執(zhí)行過程，因此，動(dòng)態(tài)性是進(jìn)程的最基本特征。動(dòng)態(tài)性還表現(xiàn)為：“它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤消而消亡”?？梢?，進(jìn)程有一定的生命期，而程序只是一組有序指令的集合，并存放于某種介質(zhì)上，本身并無運(yùn)動(dòng)的含義，因此是靜態(tài)的。（2）并發(fā)性這是指多個(gè)進(jìn)程能在一段時(shí)間內(nèi)同時(shí)運(yùn)行，并發(fā)性是進(jìn)程的重要特征。引入進(jìn)程的目的也正是為了使其程序能和其他進(jìn)程的程序并發(fā)執(zhí)行，而程序（沒有建立進(jìn)程）是不能并發(fā)執(zhí)行的（由于程序不反映執(zhí)行過程）。2．進(jìn)程的特征12(3)

獨(dú)立性

這是指進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立調(diào)度的基本單位，凡未建立進(jìn)程的程序，都不能作為一個(gè)獨(dú)立的單位參加運(yùn)行。（4）異步性

這是指進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)，或說進(jìn)程按異步方式運(yùn)行。（5）結(jié)構(gòu)特征

為使進(jìn)程能獨(dú)立運(yùn)行，應(yīng)為之配置一個(gè)稱為“進(jìn)程控制塊”的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱PCB。這樣，從結(jié)構(gòu)上看，進(jìn)程是由程序段、數(shù)據(jù)段及PCB三部分組成，有人把這三部分稱為“進(jìn)程映象”。（UNIX稱進(jìn)程的映象）。(3)獨(dú)立性這是指進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和133進(jìn)程和程序的聯(lián)系與區(qū)別：

（1）聯(lián)系。程序是構(gòu)成進(jìn)程的組成部分之一，一個(gè)進(jìn)程的運(yùn)行目標(biāo)是執(zhí)行它所對(duì)應(yīng)的程序，如果沒有程序，進(jìn)程就失去了其實(shí)際存在的意義。從靜態(tài)的角度看，進(jìn)程是由程序、數(shù)據(jù)和進(jìn)程控制塊三部分組成的。

（2）區(qū)別。程序是靜態(tài)的，而進(jìn)程是動(dòng)態(tài)的。進(jìn)程既是程序的執(zhí)行過程，因而進(jìn)程是有生命期的，有誕生，亦有消亡。因此，程序的存在是永久的，而進(jìn)程的存在是暫時(shí)的，動(dòng)態(tài)地產(chǎn)生和消亡。一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序，一個(gè)程序亦可以構(gòu)成多個(gè)進(jìn)程。例如，一個(gè)編譯進(jìn)程在運(yùn)行時(shí)，要執(zhí)行詞法分析、語(yǔ)法分析、代碼生成和優(yōu)化等幾個(gè)程序，或者一個(gè)編譯程序可以同時(shí)生成幾個(gè)編譯進(jìn)程，為幾個(gè)用戶服務(wù)。進(jìn)程具有創(chuàng)建其他進(jìn)程的功能，被創(chuàng)建的進(jìn)程稱為子進(jìn)程，創(chuàng)建者稱為父進(jìn)程，從而構(gòu)成進(jìn)程家族。3進(jìn)程和程序的聯(lián)系與區(qū)別：

（1）聯(lián)系。程序是構(gòu)成14二、進(jìn)程的狀態(tài)及其轉(zhuǎn)換

進(jìn)程在運(yùn)行中不斷地改變其運(yùn)行狀態(tài)。通常，一個(gè)運(yùn)行進(jìn)程必須具有以下三種基本狀態(tài)：

1

進(jìn)程的基本狀態(tài)(由進(jìn)程運(yùn)行的間斷性，決定了進(jìn)程至少具有下述三種基本狀態(tài))①就緒狀態(tài)當(dāng)進(jìn)程已分配到除CPU以外的所有必要的資源后，只要能再獲得處理機(jī)，便能立即執(zhí)行，把進(jìn)程這時(shí)的狀態(tài)稱為就緒狀態(tài)。在一個(gè)系統(tǒng)中，可以有多個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)，通常把它們排成一個(gè)隊(duì)列，稱為就緒隊(duì)列。②執(zhí)行狀態(tài)指進(jìn)程已獲得處理機(jī)，其程序正在執(zhí)行。在單處理機(jī)系統(tǒng)中，只能有一個(gè)進(jìn)程正在執(zhí)行狀態(tài)。③阻塞狀態(tài)進(jìn)程因發(fā)生某事件（如請(qǐng)求I/O、申請(qǐng)緩沖空間等）而暫停執(zhí)行時(shí)的狀態(tài)，亦即進(jìn)程的執(zhí)行處于受到阻塞，故稱這種暫停狀態(tài)為阻塞狀態(tài)，有時(shí)也稱為“等待”狀態(tài)，或“睡眠”狀態(tài)。通常將處于阻塞狀態(tài)的進(jìn)程排成一個(gè)隊(duì)列，稱為阻塞隊(duì)列。二、進(jìn)程的狀態(tài)及其轉(zhuǎn)換152進(jìn)程狀態(tài)的轉(zhuǎn)換

就緒執(zhí)行阻塞執(zhí)行就緒阻塞進(jìn)程調(diào)度時(shí)間片用完、請(qǐng)求I/O操作、P操作I/O完成、V操作掛起狀態(tài)：系統(tǒng)需要進(jìn)程釋放某些資源。如系統(tǒng)內(nèi)存空間不足，可用掛起原語(yǔ)將進(jìn)程掛起，該進(jìn)程從內(nèi)存轉(zhuǎn)到外存，將活動(dòng)狀態(tài)變?yōu)閽炱馉顟B(tài)，由就緒態(tài)掛起后轉(zhuǎn)換為就緒掛起；由阻塞態(tài)掛起稱為阻塞掛起。它們被激活后分別轉(zhuǎn)換為就緒態(tài)和阻塞態(tài)。退出完成就掛等掛掛起激活掛起激活2進(jìn)程狀態(tài)的轉(zhuǎn)換就緒執(zhí)行阻塞執(zhí)行就緒阻塞進(jìn)程調(diào)度時(shí)間片用16三、進(jìn)程控制塊１．進(jìn)程控制塊的作用

為了描述和控制進(jìn)程的運(yùn)行,隨時(shí)跟蹤和記錄各進(jìn)程的變化情況，以及掌握進(jìn)程間的相互關(guān)系，系統(tǒng)為每個(gè)進(jìn)程配置了一個(gè)數(shù)據(jù)結(jié)構(gòu),該數(shù)據(jù)結(jié)構(gòu)被稱為進(jìn)程控制塊PCB（ProcessControlBlock）。所謂系統(tǒng)創(chuàng)建一個(gè)進(jìn)程，就是由系統(tǒng)為某個(gè)程序設(shè)置一個(gè)PCB，用于對(duì)該進(jìn)程進(jìn)行控制和管理。進(jìn)程任務(wù)完成，由系統(tǒng)收回其PCB，該進(jìn)程便消亡。系統(tǒng)將根據(jù)某PCB而感知相應(yīng)進(jìn)程的存在，故說PCB是進(jìn)程存在的唯一標(biāo)志。2．進(jìn)程控制塊中的內(nèi)容PCB中包含了進(jìn)程的描述信息和控制信息。主要有：進(jìn)程標(biāo)識(shí)符、現(xiàn)行狀態(tài)、現(xiàn)場(chǎng)保留區(qū)、程序與數(shù)據(jù)地址、互斥與同步機(jī)構(gòu)、進(jìn)程通信機(jī)構(gòu)、進(jìn)程優(yōu)先數(shù)、資源清單、鏈接字、家族聯(lián)系

進(jìn)程控制塊PCB是系統(tǒng)感知進(jìn)程存在的唯一實(shí)體。三、進(jìn)程控制塊17四、進(jìn)程的組成

進(jìn)程由程序、數(shù)據(jù)和PCB三部分組成。PCB是進(jìn)程的“靈魂”，由于進(jìn)程控制塊中保存有進(jìn)程的地址信息，通過PCB可以得到該進(jìn)程所對(duì)應(yīng)的程序的存儲(chǔ)位置。程序和數(shù)據(jù)是進(jìn)程的“軀體”。由于現(xiàn)代操作系統(tǒng)提供程序共享的功能，這就要求程序是可重入程序，且與數(shù)據(jù)分離。所謂可重入程序是指“純”代碼程序，即在運(yùn)行過程中不修改自身。四、進(jìn)程的組成18

§2．3進(jìn)程控制進(jìn)程和處理機(jī)管理的一個(gè)重要任務(wù)是進(jìn)程控制。所謂進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段（內(nèi)核）來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。即進(jìn)程控制的主要任務(wù)是創(chuàng)建和撤消進(jìn)程，以及實(shí)現(xiàn)進(jìn)程的狀態(tài)轉(zhuǎn)換等。進(jìn)程控制一般是由操作系統(tǒng)的內(nèi)核來實(shí)現(xiàn)的?！?．3進(jìn)程控制19OS內(nèi)核

在進(jìn)行層次設(shè)計(jì)時(shí)，往往指一些與硬件緊密相關(guān)的模塊或運(yùn)行頻率較高的模塊以及為許多模塊公用的一些基本操作，安排在靠近硬件的層次中，并使它們常駐內(nèi)層，以提高OS的運(yùn)行效率，通常將這一部分稱為OS的內(nèi)核。亦即OS內(nèi)核是OS常駐內(nèi)存的程序和數(shù)據(jù)。OS內(nèi)核20

一內(nèi)核的基本功能內(nèi)核包含系統(tǒng)支撐功能和資源管理功能中的許多基本操作。（1）中斷處理。這是操作系統(tǒng)中內(nèi)核的最基本功能，也是整個(gè)操作系統(tǒng)賴以活動(dòng)的基礎(chǔ)。通常，內(nèi)核只對(duì)中斷進(jìn)行“有限的處理”，然后便轉(zhuǎn)由有關(guān)進(jìn)程繼續(xù)處理；（2）進(jìn)程控制和管理。進(jìn)程管理的任務(wù)有四個(gè)：進(jìn)程的建立和撤消；進(jìn)程狀態(tài)的轉(zhuǎn)換。系統(tǒng)應(yīng)能使進(jìn)程從阻塞變?yōu)榫途w，把活動(dòng)進(jìn)程掛起或把掛起的進(jìn)程激活；進(jìn)程調(diào)度。進(jìn)行處理機(jī)的重新分配；控制進(jìn)程的并發(fā)執(zhí)行。保證進(jìn)程間的同步，實(shí)現(xiàn)相互全作進(jìn)程間的通信。（3）資源管理中的基本操作。包括對(duì)時(shí)鐘、I/O設(shè)備和文件系統(tǒng)進(jìn)行控制和管理的基本操作。

一內(nèi)核的基本功能21１特權(quán)指令特權(quán)指令是指只允許操作系統(tǒng)使用，而不允許一般用戶使用的指令。如啟動(dòng)I/O設(shè)備的指令、取寄取器狀態(tài)指令及對(duì)系統(tǒng)安全有影響的指令等。這些指令如果允許用戶隨便使用，就可能使系統(tǒng)陷入混亂。２．非特權(quán)指令特權(quán)指令以外的指令。非特權(quán)指令的執(zhí)行不影響其他用戶以及系統(tǒng)，如算術(shù)運(yùn)算指令、邏輯運(yùn)算指令、取操作數(shù)指令等。處理機(jī)的兩種執(zhí)行狀態(tài)，用它們來區(qū)分某程序是否享有特權(quán)。３．核心態(tài)（管態(tài)）計(jì)算機(jī)的一種工作方式，在此方式下，可以執(zhí)行任何指令，可以訪問全部主存。OS在核心態(tài)下運(yùn)行。4

用戶態(tài)（目態(tài)）計(jì)算機(jī)的另一種工作方式，在此方式下，不允許執(zhí)行特權(quán)指令，只允許訪問受限定的主存。用戶程序或其它系統(tǒng)程序在目態(tài)下運(yùn)行。１特權(quán)指令特權(quán)指令是指只允許操作系統(tǒng)使用，而不允許一般用225

原語(yǔ)（primitive）完成某一特定功能的程序段，其執(zhí)行是不可分割的。換言之，在一個(gè)操作中的所有動(dòng)作，要么全做，要么全不做。原語(yǔ)可分為兩類：一類是機(jī)器指令級(jí)的，其特點(diǎn)是執(zhí)行期間不允許中斷；另一類是功能級(jí)的，其特點(diǎn)是人作為原語(yǔ)的程序段不允許并發(fā)執(zhí)行。這兩類原語(yǔ)都在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個(gè)系統(tǒng)管理所需要的功能和被高層軟件所調(diào)用。進(jìn)程控制由原語(yǔ)實(shí)現(xiàn)。5

原語(yǔ)（primitive）完成某一特定功能的程序段23二、進(jìn)程的創(chuàng)建和撤消原語(yǔ)1．

創(chuàng)建原語(yǔ)一個(gè)進(jìn)程可借助于創(chuàng)建原語(yǔ)來創(chuàng)建一個(gè)新進(jìn)程。創(chuàng)建一個(gè)新進(jìn)程的主要工作是：

申請(qǐng)一空閑PCB→無空閑PCB，則創(chuàng)建失??；否則產(chǎn)生PID（進(jìn)程標(biāo)識(shí)）→申請(qǐng)必要的資源→初始化PCB→插入就緒隊(duì)列2．

撤消進(jìn)程原語(yǔ)找出被撤消進(jìn)程的PCB→該進(jìn)程若正在執(zhí)行，則終止該進(jìn)行的執(zhí)行→該進(jìn)程若有子進(jìn)程，則撤消其所有子進(jìn)程→將該進(jìn)程所擁有的全部資源，歸還給父進(jìn)程或系統(tǒng)→將被撤消進(jìn)程的PCB從所在隊(duì)列（或鏈表）中清除，放回到空閑PCB隊(duì)列。二、進(jìn)程的創(chuàng)建和撤消原語(yǔ)24三、進(jìn)程的阻塞和喚醒原語(yǔ)１．進(jìn)程的阻塞原語(yǔ)

正在執(zhí)行的進(jìn)程，當(dāng)出現(xiàn)請(qǐng)求操作系統(tǒng)服務(wù)、啟動(dòng)某種操作、新數(shù)據(jù)尚未到達(dá)、無新工作可做等事件時(shí)，由于無法繼續(xù)運(yùn)行，于是自己便通過調(diào)用block原語(yǔ)，把自己阻塞起來?？梢姡M(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為。進(jìn)入block過程后，由于此時(shí)進(jìn)程還在執(zhí)行，故而應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為“阻塞”，并將它插入到阻塞隊(duì)列。若系統(tǒng)中設(shè)置了由于不同事件而阻塞的多個(gè)阻塞隊(duì)列，則應(yīng)將該進(jìn)程插入到具有相同事件的阻塞（等待）隊(duì)列，最后，轉(zhuǎn)進(jìn)程調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，即保留被阻塞進(jìn)程的處理機(jī)狀態(tài)在PCB中，按新進(jìn)程PCB中的處理機(jī)狀態(tài)設(shè)置CPU狀態(tài)。保存CPU現(xiàn)場(chǎng)→置該進(jìn)程的狀態(tài)→被阻塞進(jìn)程入等待隊(duì)列→轉(zhuǎn)進(jìn)程調(diào)度。三、進(jìn)程的阻塞和喚醒原語(yǔ)252．進(jìn)程的喚醒原語(yǔ)

當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)，如I/O操作完成，其所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程（比如，用完并釋放了該I/O設(shè)備的進(jìn)程）調(diào)用喚醒原語(yǔ)weakup()，將等待該事件的進(jìn)程喚醒。喚醒原語(yǔ)的操作有：先把被阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB的現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該進(jìn)程插到就緒隊(duì)列中。

從等待隊(duì)列中摘下被喚醒進(jìn)程→置進(jìn)程的狀態(tài)→將被喚醒進(jìn)程送入就緒隊(duì)列→轉(zhuǎn)進(jìn)程調(diào)度或返回。應(yīng)當(dāng)指出：block原語(yǔ)和weakup原語(yǔ)是一對(duì)功能剛好相反的原語(yǔ)，因此，如果在某進(jìn)程中調(diào)用了阻塞原語(yǔ)，則必須在與之相合作的另一進(jìn)程或其他相關(guān)進(jìn)程中調(diào)用喚醒原語(yǔ)來喚醒它，否則被阻塞進(jìn)程將會(huì)因不能被喚醒而長(zhǎng)久地處于阻塞狀態(tài)，從而再無運(yùn)行機(jī)會(huì)。2．進(jìn)程的喚醒原語(yǔ)26

§2．4進(jìn)程的互斥與同步

一、進(jìn)程間的制約關(guān)系

在多道程序系統(tǒng)中，由于資源共享與進(jìn)程合作，使諸進(jìn)程之間可能產(chǎn)生兩種形式的制約關(guān)系：１．間接相互制約

這種制約主要源于資源共享。例如，有兩進(jìn)程Ａ和Ｂ，如果在Ａ進(jìn)程提出打印請(qǐng)求時(shí)，系統(tǒng)已將打印機(jī)分配給進(jìn)程Ｂ，則進(jìn)程Ａ阻塞；一旦進(jìn)程Ｂ將打印機(jī)釋放，也就使進(jìn)程Ａ由阻塞改為就緒狀態(tài)。２．直接相互制約

這種制約主要源于進(jìn)程合作。例如，有一輸入進(jìn)程A通過單緩沖向進(jìn)程B提供數(shù)據(jù)。當(dāng)該緩沖空時(shí)，計(jì)算進(jìn)程Ｂ因不能獲得所需數(shù)據(jù)而阻塞，當(dāng)進(jìn)程A把數(shù)據(jù)送入緩沖時(shí)，便將B喚醒；反之，進(jìn)程Ａ因不能再向緩沖區(qū)投放數(shù)據(jù)而阻塞，當(dāng)進(jìn)程B將緩沖區(qū)內(nèi)數(shù)據(jù)取走時(shí)喚醒A。§2．4進(jìn)程的互斥與同步27

可見，諸進(jìn)程在并發(fā)執(zhí)行時(shí)，必須按照一定的次序執(zhí)行。進(jìn)程同步的定義如下：

進(jìn)程同步指多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。用于保證這種關(guān)系的相應(yīng)機(jī)制稱為進(jìn)程的同步機(jī)制。例如，對(duì)于共享一個(gè)緩沖區(qū)的輸入進(jìn)程和計(jì)算進(jìn)程，當(dāng)輸入進(jìn)程未將數(shù)據(jù)送入緩沖區(qū)時(shí)，計(jì)算進(jìn)程不能開動(dòng)計(jì)算；同樣，若計(jì)算進(jìn)程未從緩沖區(qū)中取走數(shù)據(jù)時(shí)，輸入進(jìn)程不能再啟動(dòng)下一次的輸入。緩沖區(qū)輸入進(jìn)程計(jì)算進(jìn)程可見，諸進(jìn)程在并發(fā)執(zhí)行時(shí)，必須按照一定的次序執(zhí)28二、臨界區(qū)（criticalsection）1.臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源。例如，有兩個(gè)進(jìn)程共享一個(gè)變量count：（R1和R2是處理機(jī)中的寄存器）：

當(dāng)兩個(gè)進(jìn)程按下述順序執(zhí)行時(shí)但若P1和P2按另一種順序?qū)ount進(jìn)行修改

P1：R1：=count；P1：R1：=count;

R1:=R1+1;P2:R2:=count;

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

P2:R2:=count;P2:R2:=R2+1;count:=R2;

R2:=R2+1;雖然P1和P2都各自對(duì)count作了加

count:=R2;1操作，但最后的count卻只增加了1。亦其結(jié)果使count增加了2；即發(fā)生了與執(zhí)行順序有關(guān)的錯(cuò)誤。

二、臨界區(qū)（criticalsection）29

2.

臨界區(qū)：訪問臨界資源的那段代碼。諸進(jìn)程在訪問臨界資源時(shí)，必須互斥。我們把每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。為了實(shí)現(xiàn)對(duì)臨界區(qū)的互斥訪問，應(yīng)保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)。為此，每個(gè)進(jìn)程在進(jìn)入其臨界區(qū)前，必須先提出申請(qǐng)，經(jīng)允許后方可進(jìn)入。稱用以實(shí)現(xiàn)此請(qǐng)求的代碼段為進(jìn)入?yún)^(qū)。顯然，在臨界區(qū)后還應(yīng)跟上一段退出區(qū)。進(jìn)程代碼中的其它部分稱為剩留區(qū)。這樣一個(gè)循環(huán)進(jìn)程可描述為

repeat

entrysection

criticalsection

exitsection

remaindersection

untilfalse2.臨界區(qū)：訪問臨界資源的那段代碼。諸進(jìn)程在訪問臨界資303

進(jìn)程互斥

不允許多于一個(gè)事件在同一時(shí)刻發(fā)生。亦即指在多道程序環(huán)境下，每次只允許一個(gè)進(jìn)程對(duì)臨界資源進(jìn)行訪問。為此必須使諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)。綜上，諸進(jìn)程對(duì)臨界資源的訪問必須互斥。我們把每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。顯然，若能保證諸進(jìn)程互斥進(jìn)入自己的臨界區(qū)，便可實(shí)現(xiàn)它對(duì)臨界資源的互斥訪問。進(jìn)程互斥也可被稱作是一種特殊形式的同步。3

進(jìn)程互斥不允許多于一個(gè)事件在同一時(shí)刻發(fā)生。亦即指在31４．同步機(jī)制應(yīng)遵循的準(zhǔn)則

為實(shí)現(xiàn)進(jìn)程互斥與同步，系統(tǒng)中應(yīng)設(shè)置專門的同步機(jī)制，所有同步機(jī)制都應(yīng)遵循下述四條準(zhǔn)則：（１)

空閑讓進(jìn)臨界資源空閑時(shí)，允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。（２)

忙則等待當(dāng)臨界資源正被訪問時(shí)，其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問。（３）有限等待對(duì)要求訪問臨界資源的進(jìn)程，應(yīng)能在有限的時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。（４）

讓權(quán)等待當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程“忙等”。４．同步機(jī)制應(yīng)遵循的準(zhǔn)則32信號(hào)量管理相應(yīng)的臨界區(qū)的公有資源，它代表可用資源實(shí)體。(1)經(jīng)典信號(hào)量機(jī)制

三、信號(hào)量機(jī)制1.

信號(hào)量（semaphore）信號(hào)量管理相應(yīng)的臨界區(qū)的公有資源，它代表可用資源實(shí)體。33（2）

計(jì)錄型信號(hào)量機(jī)制計(jì)數(shù)信號(hào)量機(jī)制是一個(gè)不具有“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。計(jì)錄型信號(hào)量是一個(gè)記錄型的數(shù)據(jù)結(jié)構(gòu)，包含兩個(gè)數(shù)據(jù)項(xiàng)，它可描述為：typesemaphore=recordvalue:integer;L:listofprocess;end相應(yīng)地，P（S）和V（S）操作可描述為：（2）

計(jì)錄型信號(hào)量機(jī)制34procedureP(S)varS:semaphore;beginS.value:=S.value-1;ifS.value<0thenblock(S.L)end;procedureV(S)varS:semaphore;beginS.value:=S.value+1;ifS.value≤0thenweakup(S.L)end;procedureP(S)35varmutex:semaphore:=1;begincobeginprocess1:beginrepeat

P(mutex);criticalsecion;V(mutex);remaindersection;untilfalseendprocess2:beginrepeat

P(mutex);criticalsection;V(mutex);remaindersection;untilfalseendcoendEnd

利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥varmutex:semaphore:=1;利用信號(hào)量實(shí)現(xiàn)36說明：①mutex為互斥信號(hào)量，其取值范圍為（1，0，-1）；其中mutex=1表示進(jìn)程1、進(jìn)程2都未進(jìn)入類名為S的臨界區(qū)，mutex＝０表示進(jìn)程1或進(jìn)程2已進(jìn)入類名為S的臨界區(qū)，mutex=-1表示進(jìn)程1和進(jìn)程2中，一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一個(gè)進(jìn)程等待進(jìn)入臨界區(qū)。若有n個(gè)并發(fā)進(jìn)程，有一個(gè)臨界資源，則信號(hào)量取值范圍-(n-1)——1,n-1表示阻塞進(jìn)程的個(gè)數(shù)。由此可見，在記錄型信號(hào)量機(jī)制中，如果S.value的初值為１，表示只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號(hào)量便轉(zhuǎn)化為上述互斥信號(hào)量。②P（mutex）和V（mutex）必須成對(duì)地出現(xiàn)。P、V操作是不可分割的。P、V操作“不可分割”的含義是指在同一個(gè)信號(hào)量上不能同時(shí)執(zhí)行一個(gè)以上的P或V操作，亦即一個(gè)P或V操作的執(zhí)行必須在另一個(gè)操作執(zhí)行完畢以后進(jìn)行，否則會(huì)產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤。缺少P(mutex)將會(huì)引起系統(tǒng)混亂，不能保證對(duì)臨界資源的互斥訪問；而缺V(mutex)將會(huì)使該臨界資源永久不被釋放，從使而因等待該資源而阻塞的進(jìn)程不再被喚醒。說明：①mutex為互斥信號(hào)量，其取值范圍為（1，0，-1）37管程用信號(hào)量可以實(shí)現(xiàn)進(jìn)程間的同步與互斥，但信號(hào)量的操作分散在各個(gè)進(jìn)程中，不利于系統(tǒng)對(duì)臨界資源的集中管理。管程是指把信號(hào)量與操作原語(yǔ)封裝在一個(gè)對(duì)象內(nèi)部，即將共享資源以及針對(duì)共享資源的所有操作集中在一個(gè)模塊中。管程可以用函數(shù)庫(kù)的形式實(shí)現(xiàn)，一個(gè)管程就是一個(gè)基本程序單位，可以單獨(dú)編譯。所有進(jìn)程要訪問臨界資源時(shí)，要經(jīng)過管程才能進(jìn)入，而管程每次只允許一個(gè)進(jìn)程進(jìn)入，從而實(shí)現(xiàn)了進(jìn)程互斥。管程用信號(hào)量可以實(shí)現(xiàn)進(jìn)程間的同步與互斥，但信號(hào)量的操作分散在38

§2．5進(jìn)程通信一、

低級(jí)和高級(jí)進(jìn)程通信方式

雖然一個(gè)作業(yè)可分為若干個(gè)能并發(fā)執(zhí)行的進(jìn)程，但它們應(yīng)經(jīng)常保持聯(lián)系，以便協(xié)調(diào)一致地完成指定任務(wù)。這種聯(lián)系是指在進(jìn)程之間交換一定數(shù)量的信息。信息量可多可少，多是指能交換成千個(gè)數(shù)據(jù)，少則僅是一個(gè)狀態(tài)或數(shù)值。顯然，進(jìn)程同步是一種簡(jiǎn)單通信方式，進(jìn)程通過修改信號(hào)量，可向另一進(jìn)程表明臨界資源是否可用。在生產(chǎn)者－消費(fèi)者問題中，可由生產(chǎn)者進(jìn)程向消費(fèi)者進(jìn)程傳送一批消息，或者說，生產(chǎn)者通過緩沖池與消費(fèi)者通信。應(yīng)當(dāng)指出，信號(hào)量機(jī)制作為同步工具是卓有成效的，但作為通信工具則不夠理想，因?yàn)槠湫噬醯?，因此，稱為低級(jí)通信方式?！?．391低級(jí)進(jìn)程通信

進(jìn)程的互斥和同步可歸結(jié)為低級(jí)進(jìn)程通信。在進(jìn)程互斥中進(jìn)程通過修改信號(hào)量，向其他進(jìn)程表明臨界資源是否可用；在生產(chǎn)者－消費(fèi)者問題中，生產(chǎn)者通過緩沖池與消費(fèi)者通信。應(yīng)當(dāng)指出，信號(hào)量機(jī)制作為同步工具是卓有成效的，但作為通信工具則不夠理想，主要表現(xiàn)在：

（１）效率低生產(chǎn)者每次只能向緩沖區(qū)中投放一個(gè)消息，消費(fèi)者每次只能從緩沖區(qū)中取得一個(gè)消息；

（２）通信對(duì)用戶不透明即設(shè)置共享數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的傳送、進(jìn)程的互斥與同步都是由程序員去實(shí)現(xiàn)，操作系統(tǒng)只提供共享存儲(chǔ)器。

簡(jiǎn)言之，這種通信方式的效率低，不方便，故只適用于傳送少量信息的情況。1低級(jí)進(jìn)程通信進(jìn)程的互斥和同步可歸結(jié)為低級(jí)進(jìn)程通信。402.

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

以較高的效率傳送大量數(shù)據(jù)的一種通信方式。高級(jí)通信的目的不是為了控制進(jìn)程的執(zhí)行速度，而是為了交換信息。在這種通信方式中，程序員可直接利用系統(tǒng)提供的一組通信命令（通信原語(yǔ)），高效地傳送大量數(shù)據(jù)，操作系統(tǒng)隱藏了實(shí)現(xiàn)通信的細(xì)節(jié)，這大大簡(jiǎn)化了通信程序編制上的復(fù)雜性。高級(jí)通信原語(yǔ)不僅保證相互制約的進(jìn)程之間的正確關(guān)系，還同時(shí)實(shí)現(xiàn)了進(jìn)程之間的信息交換。目前常用的高級(jí)通信機(jī)構(gòu)有消息緩沖通信、管道通信和信箱通信。2.

高級(jí)進(jìn)程通信以較高的效率傳送大量數(shù)據(jù)的一種41二、進(jìn)程通信的類型(1)共享存儲(chǔ)區(qū)內(nèi)存中開辟一個(gè)共享存儲(chǔ)區(qū),各進(jìn)程通過該儲(chǔ)存區(qū)進(jìn)行通信.(2)消息傳遞系統(tǒng)

通過os提供的一組消息通信命令來實(shí)現(xiàn)信息的傳遞.

直接通信方式:os提供send和receive實(shí)現(xiàn).

間接通信方式:通過共享信箱來實(shí)現(xiàn).二、進(jìn)程通信的類型42(3)

管道通信管道通信是由UNIX首創(chuàng)的，是一種重要的通信方式。管道通信以文件系統(tǒng)為基礎(chǔ)。所謂管道，就是連接兩個(gè)進(jìn)程的一個(gè)打開的共享文件（pipes），專用于進(jìn)程之間進(jìn)行數(shù)據(jù)通信。發(fā)送進(jìn)程可以源源不斷地從管道一端寫入數(shù)據(jù)流，接收進(jìn)程在需要時(shí)可以從管道的另一端讀出數(shù)據(jù)。在對(duì)管道文件進(jìn)行讀寫操作時(shí)，發(fā)送進(jìn)程和接收進(jìn)程要實(shí)施正確的同步和互斥，以確保通信的正確性。管道通信的實(shí)質(zhì)是利用外存來進(jìn)行數(shù)據(jù)通信，故具有傳送數(shù)據(jù)量大的優(yōu)點(diǎn)，但管道通信速度較慢。(3)管道通信43

§２．6進(jìn)程調(diào)度一、

調(diào)度的基本概念

在多道程序環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭(zhēng)用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。由于處理機(jī)是最重要的計(jì)算機(jī)資源，提高處理機(jī)的利用率及改善系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間）在很大程序上取決于進(jìn)程調(diào)度性能的好壞，因而進(jìn)程調(diào)度便成為操作系統(tǒng)設(shè)計(jì)的中心問題之一?！欤玻?進(jìn)程44三級(jí)調(diào)度(1)

高級(jí)調(diào)度（宏觀調(diào)度）又稱作業(yè)調(diào)度，如幾分鐘才調(diào)度一次，且調(diào)度算法復(fù)雜。(2)低級(jí)調(diào)度（微觀調(diào)度）又稱為進(jìn)程調(diào)度。(3）中級(jí)調(diào)度又稱進(jìn)程對(duì)換，按一定算法在內(nèi)存和外存之間進(jìn)行進(jìn)程對(duì)換，其目的是為了使內(nèi)存緊張的情況得以緩和。中級(jí)調(diào)度的主要工作是將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換至外存，騰出內(nèi)存空間以便將外存上已具備執(zhí)行條件的進(jìn)程換入內(nèi)存，準(zhǔn)備執(zhí)行。進(jìn)程在運(yùn)行期間可能要經(jīng)歷多次換進(jìn)換出，在分時(shí)系統(tǒng)中常采用中級(jí)調(diào)度。三級(jí)調(diào)度452.引起進(jìn)程調(diào)度的原因（１)

正在執(zhí)行的進(jìn)程執(zhí)行完畢（處理機(jī)要分配給新進(jìn)程）；（２）

執(zhí)行中進(jìn)程自己調(diào)用阻塞原語(yǔ)將自己阻塞起來而進(jìn)入等待狀態(tài)；（３）執(zhí)行進(jìn)程調(diào)用了P、V操作。P－因資源不足而被阻塞，V－激活等待資源的進(jìn)程隊(duì)列；（４）執(zhí)行中進(jìn)程提出I/O請(qǐng)求；（５）

時(shí)間片用完（分時(shí)系統(tǒng)）；（６）執(zhí)行完系統(tǒng)調(diào)用后。執(zhí)行完系統(tǒng)調(diào)用后的系統(tǒng)程序返回用戶進(jìn)程時(shí)，這時(shí)可看作系統(tǒng)進(jìn)程執(zhí)行完畢，從而可選擇一新的用戶進(jìn)程執(zhí)行；（７)

就緒隊(duì)列中的某進(jìn)程的優(yōu)先級(jí)變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級(jí)，從而也將引發(fā)進(jìn)程調(diào)度。2.引起進(jìn)程調(diào)度的原因463．進(jìn)程調(diào)度的方式(１）非剝奪方式以這種調(diào)度方式運(yùn)行時(shí)，不允許強(qiáng)行剝奪已經(jīng)分配給某進(jìn)程的處理機(jī)。例如，調(diào)度程序一旦把處理機(jī)分配給某進(jìn)程后應(yīng)讓它一直運(yùn)行下去，直至進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才把處理機(jī)分配給另一進(jìn)程。這種調(diào)度方式的優(yōu)點(diǎn)是簡(jiǎn)單、系統(tǒng)開銷小，但卻可能導(dǎo)致系統(tǒng)性能的惡化，表現(xiàn)為：①

當(dāng)一個(gè)緊急任務(wù)到達(dá)時(shí)，它不能立即投入運(yùn)行，以至于延誤時(shí)機(jī)；②

若干個(gè)后到的短作業(yè)，需等待先到的長(zhǎng)作業(yè)運(yùn)行完畢，致使短作業(yè)的周轉(zhuǎn)時(shí)間較長(zhǎng)。例如，有三個(gè)進(jìn)程P1、P２、P３先后（但又幾乎在同時(shí)）到達(dá)，它們分別需要20、4和2個(gè)單位時(shí)間運(yùn)行完畢。若它們就按P1、P２、P３的順序執(zhí)行，且不可剝奪，則三進(jìn)程各自的周轉(zhuǎn)時(shí)間分別為20、24和26個(gè)單位時(shí)間，平均周轉(zhuǎn)時(shí)間是（20+24+26）/3=70/3個(gè)單位時(shí)間。這種非剝奪方式對(duì)短作業(yè)P3而言是不公平的。

非剝奪方式在批處理系統(tǒng)中常用。3．進(jìn)程調(diào)度的方式47(2)

剝奪調(diào)度方式這是指進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可根據(jù)某種原則，剝奪已分配給它的處理機(jī)，并再分配給其他進(jìn)程的一種調(diào)度方式。剝奪的原則有：①優(yōu)先權(quán)原則優(yōu)先權(quán)高的進(jìn)程可以剝奪優(yōu)先權(quán)低的進(jìn)程而運(yùn)行；②短進(jìn)程優(yōu)先原則短進(jìn)程到達(dá)后可以剝奪長(zhǎng)進(jìn)程的運(yùn)行；③時(shí)間片原則一個(gè)時(shí)間片運(yùn)行完后重新調(diào)度。下面我們?nèi)砸陨鲜鋈齻€(gè)進(jìn)程的情況為例，說明基于時(shí)間片原則的剝奪調(diào)度方式。由下圖可以看出，P1、P２、P３的周轉(zhuǎn)時(shí)間分別為26、10、6個(gè)單位時(shí)間，而平均周轉(zhuǎn)時(shí)間已由剝奪方式的70/3，降低為（26+10+6）/3=14個(gè)單位時(shí)間。設(shè)時(shí)間片為2個(gè)單位時(shí)間

基于時(shí)間片原則的剝奪調(diào)度方式示例P1P2P1P1P2P1P1P1…P1(2)

剝奪調(diào)度方式這是指進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可根據(jù)483與調(diào)度算法和性能有關(guān)的術(shù)語(yǔ)（１）周轉(zhuǎn)時(shí)間（TurnaroundTime）周轉(zhuǎn)時(shí)間是批處理系統(tǒng)中衡量調(diào)度性能的一個(gè)重要指標(biāo)。對(duì)于一個(gè)作業(yè)來講，從提交開始到完成為止的這段時(shí)間間隔稱為該作業(yè)的周轉(zhuǎn)時(shí)間。它包括：①作業(yè)在外存后備隊(duì)列上等待進(jìn)入內(nèi)存的時(shí)間；②在就緒隊(duì)列上等待獲得處理機(jī)的時(shí)間；③在CPU上的執(zhí)行時(shí)間；④等待I/O操作完成的時(shí)間。對(duì)于一個(gè)進(jìn)程來說，它的周轉(zhuǎn)時(shí)間是從第一次進(jìn)入就緒隊(duì)列開始，到進(jìn)程運(yùn)行完畢所經(jīng)歷的時(shí)間。當(dāng)一個(gè)作業(yè)轉(zhuǎn)換為一個(gè)進(jìn)程時(shí)，進(jìn)程的周轉(zhuǎn)時(shí)間便是作業(yè)周轉(zhuǎn)時(shí)間中的后三部分之和。3與調(diào)度算法和性能有關(guān)的術(shù)語(yǔ)49（2）響應(yīng)時(shí)間（responseTime）它是分時(shí)系統(tǒng)中衡量調(diào)度性能的一個(gè)重要指標(biāo)。所謂響應(yīng)時(shí)間，是指從提交一個(gè)請(qǐng)求開始到首次產(chǎn)生響應(yīng)為止（顯示出結(jié)果）的一段時(shí)間間隔。它包括：①把請(qǐng)求信息從鍵盤傳送到計(jì)算機(jī)的時(shí)間；②計(jì)算機(jī)對(duì)請(qǐng)求進(jìn)行處理的時(shí)間；③再將響應(yīng)送回終端的時(shí)間。(3）CPU-I/O執(zhí)行期通常一個(gè)進(jìn)程在運(yùn)行時(shí)，會(huì)交替地處于兩種工作狀態(tài)：CPU忙或稱CPU運(yùn)行期（CPUburst）；I/O忙（或稱I/O運(yùn)行期）。CPU執(zhí)行期的長(zhǎng)短因進(jìn)程而異，對(duì)于含有大量I/O操作的作業(yè)（簡(jiǎn)稱I/O型作業(yè)），每個(gè)CPU執(zhí)行期通常很短，例如為幾十毫秒；對(duì)那些需要長(zhǎng)期利用CPU進(jìn)行計(jì)算的作業(yè)（簡(jiǎn)稱計(jì)算型作業(yè)），CPU執(zhí)行期可能長(zhǎng)達(dá)數(shù)小時(shí)。（2）響應(yīng)時(shí)間（responseTime）它是分時(shí)系統(tǒng)50二、進(jìn)程調(diào)度算法對(duì)于不同的系統(tǒng)及系統(tǒng)目標(biāo)，應(yīng)采用不同的調(diào)度算法。例如，在批處理系統(tǒng)中，如果希望照顧到為數(shù)眾多的短作業(yè)，應(yīng)采取短進(jìn)程優(yōu)先的進(jìn)程調(diào)度算法；在分時(shí)系統(tǒng)中，為了保證具有合理的響應(yīng)時(shí)間，應(yīng)采用輪轉(zhuǎn)法。下面分別介紹幾種進(jìn)程調(diào)度算法。

1先來先服務(wù)（FCFS或FIFO）算法2最短CPU運(yùn)行期優(yōu)先調(diào)度算法（SCBF-ShortestCPUBurstFirst）

二、進(jìn)程調(diào)度算法513

最高優(yōu)先數(shù)優(yōu)先調(diào)度算法

這是在批處理系統(tǒng)和實(shí)時(shí)系統(tǒng)中常用的一種調(diào)度算法。它是把處理機(jī)分配給就緒隊(duì)列中具有最高優(yōu)先權(quán)的進(jìn)程。該算法的關(guān)鍵是如何確定進(jìn)程的優(yōu)先權(quán)，常用以下兩種方法：（１）靜態(tài)優(yōu)先數(shù)。靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在整個(gè)運(yùn)行期間不再改變。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有：進(jìn)程類型（通常系統(tǒng)進(jìn)程的優(yōu)先權(quán)高于用戶進(jìn)程的優(yōu)先權(quán)）、進(jìn)程對(duì)資源的要求（如估計(jì)的運(yùn)行時(shí)間、內(nèi)存需要量等）、用戶要求的優(yōu)先級(jí)（靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行，但不夠準(zhǔn)確）。3

最高優(yōu)先數(shù)優(yōu)先調(diào)度算法52基于靜態(tài)優(yōu)先權(quán)的調(diào)度算法實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小，但由于靜態(tài)優(yōu)先權(quán)一旦確定之后，直到執(zhí)行結(jié)束為止始終保持不變，從而使系統(tǒng)效率較低，調(diào)度性能不高。現(xiàn)在在操作系統(tǒng)中，如使用優(yōu)先權(quán)調(diào)度算法的話，大多采用動(dòng)態(tài)優(yōu)先權(quán)算法。（2）動(dòng)態(tài)優(yōu)先數(shù)。動(dòng)態(tài)優(yōu)先權(quán)是基于某種原則，使進(jìn)程的優(yōu)先權(quán)隨時(shí)間而改變，例如在就緒隊(duì)列中的進(jìn)程，其優(yōu)先權(quán)以速度a增加，若再令正在執(zhí)行進(jìn)程的優(yōu)先權(quán)以速度b下降，便可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期壟斷處理機(jī)?；陟o態(tài)優(yōu)先權(quán)的調(diào)度算法實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小，但由于靜態(tài)優(yōu)先534

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

在分時(shí)系統(tǒng)中都采用時(shí)間片輪轉(zhuǎn)法。在簡(jiǎn)單的輪轉(zhuǎn)法中，系統(tǒng)將所有就緒進(jìn)程按FIFO規(guī)則排成一個(gè)隊(duì)列，把CPU分配給隊(duì)首進(jìn)程，并規(guī)定它執(zhí)行一個(gè)時(shí)間片。當(dāng)時(shí)間片完時(shí)，系統(tǒng)剝奪該進(jìn)程珠運(yùn)行并將它送就緒隊(duì)列末尾，重新把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同樣也讓它執(zhí)行一個(gè)時(shí)間片。這樣，就緒隊(duì)列中的所有進(jìn)程在一給定時(shí)間內(nèi)，均可獲得一個(gè)時(shí)間片的處理機(jī)執(zhí)行時(shí)間。4

時(shí)間片輪轉(zhuǎn)法54５多級(jí)反饋隊(duì)列(目前分時(shí)系統(tǒng)將之與時(shí)間片結(jié)合)

多級(jí)反饋隊(duì)列方式系統(tǒng)中，設(shè)置了多個(gè)就緒隊(duì)列，并賦予各隊(duì)列以不同的優(yōu)先權(quán)。系統(tǒng)在調(diào)度時(shí)，總是先調(diào)度第一級(jí)隊(duì)列上的進(jìn)程執(zhí)行：僅當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，才調(diào)度第二級(jí)隊(duì)列上的進(jìn)程執(zhí)行；類推之，僅當(dāng)?shù)冢薄?n-1)級(jí)隊(duì)列都空時(shí)，才調(diào)度第n級(jí)隊(duì)列中的進(jìn)程執(zhí)行。如果處理機(jī)正在服務(wù)于第i級(jí)隊(duì)列中的進(jìn)程又有新進(jìn)程進(jìn)入較高級(jí)隊(duì)列，則此時(shí)將引起重新調(diào)度，把處理機(jī)分配給新進(jìn)程。這種調(diào)度算法能較好地滿足各種用戶的要求。５多級(jí)反饋隊(duì)列(目前分時(shí)系統(tǒng)將之與時(shí)間片結(jié)合)556.響應(yīng)比高者優(yōu)先（HRN）ＨighestResponse-ratio

設(shè)響應(yīng)比為R，則一種常用的響應(yīng)比的計(jì)算方法如下：R=（W+T）/T=1+W/TW：在后備隊(duì)列中等待的時(shí)間；T：該作業(yè)估計(jì)要執(zhí)行的時(shí)間。這樣，即使是長(zhǎng)作業(yè)，隨著它等待時(shí)間的增加，W/T也就增加，R也就隨之增加，也就有機(jī)會(huì)獲得調(diào)度而執(zhí)行。6.響應(yīng)比高者優(yōu)先（HRN）ＨighestRespons56§2．7線程

引入線程是為了減少程序并發(fā)執(zhí)行時(shí)付出的時(shí)空開銷，使系統(tǒng)具有更好的并發(fā)性。線程僅擁有在運(yùn)行中必不可少的資源.

具有動(dòng)態(tài)性、并發(fā)性和結(jié)構(gòu)性，還有共享性。同一進(jìn)程中的所有線程共享進(jìn)程資源.線程：是調(diào)度的單位，進(jìn)程是分配資源的單位類型：（1）內(nèi)核級(jí)線程：可以存在于系統(tǒng)進(jìn)程和用戶進(jìn)程中，它們的創(chuàng)建、撤消和切換都由內(nèi)核實(shí)現(xiàn)。（2）用戶級(jí)線程：僅存在于用戶進(jìn)程中.（3）混合式線程：§2．7線程

引入線程是為了減少程序并發(fā)執(zhí)行時(shí)付出57

§2．8死鎖一、死鎖的概念在多道程序系統(tǒng)中，可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利用率和提高系統(tǒng)的處理能力。但可能發(fā)生一種危險(xiǎn)——死鎖。１．死鎖是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局，若無外力作這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。產(chǎn)生死鎖的原因可歸結(jié)為以下兩點(diǎn)：（１）競(jìng)爭(zhēng)資源。為多個(gè)進(jìn)程所共享的資源不足，引起它們對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖；（２）進(jìn)程推進(jìn)順序不當(dāng)。進(jìn)程運(yùn)動(dòng)過程中，請(qǐng)求和釋放資源的順序不當(dāng)，而導(dǎo)致進(jìn)程死鎖。２．死鎖的起因（1）競(jìng)爭(zhēng)資源引起死鎖（2）進(jìn)程推進(jìn)順序不當(dāng)引起死鎖§2．583．產(chǎn)生死鎖的四個(gè)必要條件（１）互斥條件并發(fā)進(jìn)程所要求和占有的資源是不能同時(shí)被兩個(gè)以上進(jìn)程使用或操作的，進(jìn)程對(duì)它所需要的資源進(jìn)行排它性控制，即進(jìn)程間必須互斥使用資源。（２）請(qǐng)求和保持條件（部分分配條件）進(jìn)程每次申請(qǐng)它所需要的一部分資源，在等待新資源的同時(shí)，繼續(xù)占用已分配到的資源。即進(jìn)程保持已占用資源，等待分配附加資源。（３）不剝奪條件進(jìn)程所獲得的資源在未使用完畢之前，不能被其它進(jìn)程強(qiáng)行剝奪，而只能由獲得該資源的進(jìn)程自己釋放。即進(jìn)程已獲得資源，只能在使用完時(shí)自行釋放。（４)

環(huán)路等待條件進(jìn)程資源圖構(gòu)成的有向環(huán)路（在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源環(huán)形鏈，即進(jìn)程集合{P0,P1,P2,…,Pn}中的P0正在等待一個(gè)P1占用的資源，P1正在等待一個(gè)P2占用的資源……Pn正在等待一個(gè)P0占用的資源。3．產(chǎn)生死鎖的四個(gè)必要條件59二、死鎖的處理解決死鎖的方法一般可分為預(yù)防死鎖、避免死鎖、檢測(cè)死鎖、解除死鎖（恢復(fù)）四種，由于檢測(cè)死鎖與解除死鎖的方法通常必須聯(lián)合使用，故有些教材將解決死鎖的方法分為預(yù)防、避免、檢測(cè)和恢復(fù)三種。（一）預(yù)防死鎖通過設(shè)置某些限制條件，以破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，來防止發(fā)生死鎖。預(yù)防死鎖方法已得到廣泛應(yīng)用，但可能導(dǎo)致資源利用率很低。我們可以通過使（２、（３）、（４）三個(gè)必要條件不能成立的方法，來預(yù)防死鎖的產(chǎn)生，至于必要條件（１），由于是設(shè)備的固有特性，不僅不能改變，還應(yīng)設(shè)法加以保證。二、死鎖的處理60１．摒棄“請(qǐng)求和保持”（部分分配）條件為了摒棄這一條件，系統(tǒng)要求所有進(jìn)程都一次性地申請(qǐng)其所需的全部資源，若系統(tǒng)擁有足夠的資源分配給進(jìn)程時(shí)，便把進(jìn)程所需資源分配給它，這樣，該進(jìn)程在整個(gè)運(yùn)行期間，便不會(huì)再提出資源請(qǐng)求，從而摒棄了請(qǐng)求條件，但只要有一種資源的要求不能滿足，則已有的其他資源也全部不分配給該進(jìn)程，讓進(jìn)程等待。由于在等待期間的進(jìn)程不占有任何資源，因此摒棄了保持條件，從而可以避免發(fā)生死鎖。這種方法的優(yōu)點(diǎn)是簡(jiǎn)單，易于實(shí)現(xiàn)，且很安全；但缺點(diǎn)也極其明顯：（１）

資源嚴(yán)重浪費(fèi)：一個(gè)進(jìn)程一次獲得共所需的全部資源，嚴(yán)重地惡化了系統(tǒng)的資源利用率；（２）

進(jìn)程推遲運(yùn)行：僅當(dāng)進(jìn)程獲得其所需全部資源后，方能開始運(yùn)行，但可能有某些資源長(zhǎng)期被其它進(jìn)程占用，致使進(jìn)程遲遲不能運(yùn)行。１．摒棄“請(qǐng)求和保持”（部分分配）條件612

摒棄“不剝奪”條件該策略規(guī)定，一個(gè)已保持了某些資源的進(jìn)程，若新的資源要求不能立即得到滿足，它必須釋放已保持的所有資源，以后需要時(shí)再重新申請(qǐng)。這意味著，進(jìn)程已占有資源在運(yùn)行過程中可被剝奪，從而摒棄了“不剝奪條件”。這種策略實(shí)現(xiàn)起來比較復(fù)雜，且要付出很大代價(jià)。因?yàn)橐粋€(gè)資源在使用一段時(shí)間后被釋放，可能會(huì)造成前階段工作的失效。此外，該策略還可能由于反復(fù)地申請(qǐng)和釋放資源，使進(jìn)程的執(zhí)行無限推遲。這不僅延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，也增加了系統(tǒng)開銷。2

摒棄“不剝奪”條件62３．摒棄“環(huán)路等待”條件該策略規(guī)定，系統(tǒng)將所有的資源按類型進(jìn)行線性排隊(duì)，并賦予不同的序號(hào)。例如，令輸入機(jī)的序號(hào)為１，打印機(jī)的序號(hào)為２，穿孔機(jī)為３，磁帶機(jī)為４，磁盤為５。所有進(jìn)程對(duì)資源請(qǐng)求，必須嚴(yán)格按資源序號(hào)遞增的順序提出，這樣在所形成的資源分配圖中不再可能出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件。在采用這種策略時(shí)，由于總有一個(gè)進(jìn)程占據(jù)了較高序號(hào)的資源，它繼續(xù)請(qǐng)求的資源必然是空閑的，因此進(jìn)程可以一直向前推進(jìn)。該策略較之前兩種策略，在資源利用率、系統(tǒng)吞吐量上都有顯蓍提高，但也存在不述嚴(yán)重問題：(１）

為系統(tǒng)中各種資源類型分配的序號(hào)，必須相對(duì)穩(wěn)定，這就限制了新設(shè)備類型的增加；(2)盡管在為資源分配序號(hào)時(shí)，已考慮到大多數(shù)作業(yè)實(shí)際使用這些資源的順序，但也經(jīng)常會(huì)發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源的浪費(fèi)

３．摒棄“環(huán)路等待”條件63（二）避免死鎖在預(yù)防死鎖中所采取的幾種策略，都施加了較強(qiáng)的限制條件，因而嚴(yán)重地?fù)p害了系統(tǒng)性能。而避免死鎖方法所施加的限制條件較弱，可能獲得較為滿意的系統(tǒng)性能。死鎖避免可被稱為動(dòng)態(tài)預(yù)防，因?yàn)橄到y(tǒng)采用動(dòng)態(tài)分配資源的方法，在分配過程中預(yù)測(cè)出死鎖發(fā)生的可能性并加以避免。這種方法中把運(yùn)行中的系統(tǒng)歸為下述兩種狀態(tài)：（二）避免死鎖64１．安全與不安全狀態(tài)（１)安全狀態(tài)在避免死鎖方法中，系統(tǒng)允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源。系統(tǒng)在為進(jìn)程分配資源前，要先對(duì)系統(tǒng)的安全性進(jìn)行計(jì)算。若為進(jìn)程分配了其所需的資源后，系統(tǒng)仍處于安全狀態(tài)，那么才可將資源分配給進(jìn)程。所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程推進(jìn)順序（P1,P2,…,Pn）（稱<P1,P2,…,Pn>為安全序列），來為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都能順利完成（即所有并發(fā)進(jìn)程都在該序列中）。若系統(tǒng)不存在這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進(jìn)入死鎖狀態(tài)。因此，避免死鎖的實(shí)質(zhì)在于如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。１．安全與不安全狀態(tài)65(2)

安全狀態(tài)之例假定系統(tǒng)有三個(gè)進(jìn)程P1、P2、P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1、P2、P3分別要求10臺(tái)、4臺(tái)和9臺(tái)。設(shè)在T0時(shí)刻進(jìn)程P1、P2、P3已分別獲得５臺(tái)、２臺(tái)和２臺(tái)，尚有３臺(tái)空閑磁帶機(jī)未分配出去。分配情況如下表所示：進(jìn)程號(hào)最大需求量已分配未分配P11053P242P392(2)

安全狀態(tài)之例進(jìn)程號(hào)最大需求量已分配未分配66經(jīng)分析發(fā)現(xiàn)，在T0時(shí)刻系統(tǒng)是安全的，因?yàn)榇藭r(shí)存在一個(gè)安全序列<P2,P1,P3>，即只要系統(tǒng)按此進(jìn)程順序分配資源，每個(gè)進(jìn)程就都可順利完成。例如：將剩余的磁帶機(jī)取２臺(tái)分配給P2，使這繼續(xù)運(yùn)行，待P2完成便使可用資源增至５臺(tái)，再將它們?nèi)糠峙浣oP1，待P1完成后釋放出10臺(tái)磁帶機(jī)，P3便可獲得足夠的資源，從而使P1、P2、P3三個(gè)進(jìn)程都能順利完成。經(jīng)分析發(fā)現(xiàn)，在T0時(shí)刻系統(tǒng)是安全的，因?yàn)榇藭r(shí)存在一個(gè)安全序列67（３）向不安全狀態(tài)的轉(zhuǎn)換

如果在T0時(shí)刻以后，P3請(qǐng)求１臺(tái)磁帶機(jī)，若系統(tǒng)此時(shí)把剩余３臺(tái)中的１臺(tái)分配給P3，則系統(tǒng)進(jìn)入不安全狀態(tài)。因?yàn)椋盐捶峙涞模才_(tái)分配給P2，而P2完成后只能釋放出４臺(tái)，既不能滿足P3，從而它們都無法推進(jìn)到完成，于是，系統(tǒng)進(jìn)入了不安全狀態(tài)。由此可見，在P3請(qǐng)求資源時(shí)，盡管系統(tǒng)中尚有可用的磁帶機(jī)，但卻不能為它分配，而需讓它一直等待到P1、P2完成，釋放出資源后，再將足夠的資源分配給P3，它才能順利完成。.銀行家算法（３）向不安全狀態(tài)的轉(zhuǎn)換68三、檢測(cè)死鎖檢測(cè)死鎖，系統(tǒng)必須：（１）保存有關(guān)資源的請(qǐng)求和分配信息；（２）提供一種算法，以利用這些信息來檢測(cè)系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。檢測(cè)死鎖算法主要是檢查系統(tǒng)中進(jìn)程是否有循環(huán)等待，如可利用資源分配圖進(jìn)行檢查。

三、檢測(cè)死鎖69PR1R2

Q資源分配圖進(jìn)程死鎖狀態(tài)的示意圖PR1R2Q資源分配圖進(jìn)程死鎖狀態(tài)的示意圖70四、死鎖的解除當(dāng)發(fā)現(xiàn)有進(jìn)程死鎖后，便應(yīng)立即把它從死鎖狀態(tài)中解脫出來，常采用的兩種方法是：（１）剝奪資源。從其它進(jìn)程剝壓足夠數(shù)量的資源給死鎖進(jìn)程，以解除死鎖狀態(tài)；（２）撤消進(jìn)程。最簡(jiǎn)單的撤消進(jìn)程的方法是使全部死鎖進(jìn)程都夭折掉；稍為溫和一點(diǎn)的方法是按照某種順序逐個(gè)地撤消進(jìn)程，直至有足夠的資源可用，死鎖狀態(tài)消除為止。

四、死鎖的解除71

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

進(jìn)程是操作系統(tǒng)中最重要的概念之一在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，進(jìn)程不僅是最基本的并發(fā)執(zhí)行單位，而且也是分配資源、交換信息的基本單位。而進(jìn)程管理則是操作系統(tǒng)中最重要且最復(fù)雜的管理。第二章進(jìn)程管理72

§2．１前趨圖一程序的順序執(zhí)行與特征1．

程序的順序執(zhí)行

一個(gè)程序通常可分成若干個(gè)程序段，它們必須按照某種先后次序執(zhí)行，僅當(dāng)前一操作執(zhí)行完后，才能執(zhí)行后繼操作。§2．１前趨圖73C1P1I1C1P1I1C1P1I2C2P2C1P1I1C1P1I1C1P1I2C2P274

程序順序執(zhí)行時(shí)的特征（1）順序性。處理機(jī)的操作嚴(yán)格按照程序規(guī)定的順序執(zhí)行，即只有前一操作結(jié)束后，才能啟動(dòng)后一操作的執(zhí)行；（2）封閉性。程序在封閉的環(huán)境下運(yùn)行，并獨(dú)占全機(jī)，因此機(jī)內(nèi)資源的狀態(tài)只有運(yùn)行程序的操作才能改變它，其執(zhí)行結(jié)果不受外界因素的影響；（3）可再現(xiàn)性。只要程序執(zhí)行時(shí)環(huán)境和初始條件相同，程序經(jīng)多次運(yùn)行后所得的結(jié)果必然相同。程序順序執(zhí)行時(shí)的特征75514236789二

前趨圖的定義前趨圖是一個(gè)有向無環(huán)圖，記為DAG。如圖所示：有向無環(huán)圖123456789514236789二前趨圖的定義有向無環(huán)圖1234576

三

程序的并發(fā)執(zhí)行與特征1雖然對(duì)于一個(gè)程序的輸入、計(jì)算和打印必須順序執(zhí)行，但在對(duì)一批程序進(jìn)行處理時(shí)，則可使上述三種操作并發(fā)執(zhí)行，以提高系統(tǒng)的吞吐量。例如，輸入程序在輸入第三個(gè)程序（I3）的同時(shí)，計(jì)算程序可以正在對(duì)第二個(gè)程序進(jìn)行計(jì)算（C2），而打印程序正在打印第一個(gè)程序（Ｐ1）的計(jì)算結(jié)果。如下圖所示：I1I2I3I4C1C2C3C4P1P2P3P4程序段并發(fā)執(zhí)行的有向圖

三

程序的并發(fā)執(zhí)行與特征I1I2I3I4C1C2C3C77

程序的并發(fā)執(zhí)行（concurrence）指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。在多道程序環(huán)境下，并發(fā)是指宏觀上在一段時(shí)間內(nèi)有多道程序在同時(shí)運(yùn)行，而微觀上這些程序是在交替地執(zhí)行。

（并行(parallel)指兩個(gè)或多個(gè)事件在同一時(shí)刻進(jìn)行，例如，在具有中斷的計(jì)算機(jī)系統(tǒng)中，CPU可以和I/O設(shè)備并行執(zhí)行。

程序的并發(fā)執(zhí)行雖然提高了系統(tǒng)的吞吐量，但也產(chǎn)生了下述一些新特征：程序的并發(fā)執(zhí)行（concurrence）78２．程序并發(fā)執(zhí)行所帶來的影響（特征）（１）間斷性相互制約將導(dǎo)致并發(fā)程序具有“執(zhí)行－暫停－執(zhí)行”這種間斷性的活動(dòng)規(guī)律。（２）失去封閉性

程序在并發(fā)執(zhí)行時(shí)，是多個(gè)程序共享一臺(tái)機(jī)器，因而機(jī)內(nèi)資源的狀態(tài)將由多個(gè)程序來改變，因此使程序的運(yùn)行已失去了封閉性，這樣，某程序在執(zhí)行時(shí)，也必然會(huì)受到其他程序的影響，例如，當(dāng)處理機(jī)資源被其他程序占有時(shí)，某程序必須等２．程序并發(fā)執(zhí)行所帶來的影響（特征）79（３）不可再現(xiàn)性程序在并發(fā)執(zhí)行時(shí)，也將失去其可再現(xiàn)性。例如，有兩個(gè)循環(huán)程序A和B，它們共享一個(gè)變量n。程序A每執(zhí)行一次時(shí)都要做n：=n+1操作；程序B則每執(zhí)行一次都要執(zhí)行print（n）操作，然后再將N置成“０”。如下程序段所示:varn:integer;beginn:=0;cobeginprogramA:beginrepeat…n:=n+1;remainderofprogramAuntilfalseend;programB:beginrepeat…printn;n:=0;remainderofprogramBuntilfalseend;coendend;（３）不可再現(xiàn)性程序在并發(fā)執(zhí)行時(shí)，也將失去其可再現(xiàn)性。例80

§2．2進(jìn)程的基本概念

由上所述可知，程序并發(fā)執(zhí)行時(shí)，產(chǎn)生了一些新特征，致使一般的程序不能并發(fā)執(zhí)行。例如，程序在執(zhí)行中一旦受阻而停下來時(shí)，系統(tǒng)無法保留該程序的現(xiàn)場(chǎng)，因而也就無法再恢復(fù)該程序的現(xiàn)場(chǎng)并以繼續(xù)執(zhí)行。為了使程序在多道程序環(huán)境下能并發(fā)執(zhí)行，并能對(duì)并發(fā)執(zhí)行的程序加以控制和描述，而專門為之配置了一個(gè)稱為“進(jìn)程控制塊”的數(shù)據(jù)結(jié)構(gòu)。其中，存放了進(jìn)程標(biāo)識(shí)符、進(jìn)程運(yùn)行的當(dāng)前狀態(tài)、程序和數(shù)據(jù)的地址，以及能保存該程序運(yùn)行時(shí)CPU的環(huán)境信息。由程序段、數(shù)據(jù)段及進(jìn)程控制塊三部分構(gòu)成了進(jìn)程的實(shí)體?！?．2進(jìn)程的基本概念81一、進(jìn)程的定義和特征

1.進(jìn)程的定義

至此，已知程序并發(fā)執(zhí)行產(chǎn)生了一系列新特點(diǎn)，為了能對(duì)并發(fā)程序的執(zhí)行加以描述而引入了進(jìn)程的概念。曾有許多人從不同角度對(duì)進(jìn)程下過各種定義，其中較典型的進(jìn)程定義有：

進(jìn)程是程序的一次執(zhí)行。

進(jìn)程是一個(gè)程序及其數(shù)據(jù)，在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。

進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。

進(jìn)程是可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程。

第三個(gè)定義比較準(zhǔn)確，它包含了進(jìn)程的主要特征。這里，我們?cè)谠摱x的基礎(chǔ)上加以修改后，可把進(jìn)程定義為：進(jìn)程是程序的一次執(zhí)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位，動(dòng)態(tài)產(chǎn)生和動(dòng)態(tài)消亡，它可以和其他程序并發(fā)執(zhí)行。一、進(jìn)程的定義和特征822．進(jìn)程的特征進(jìn)程和程序是兩個(gè)截然不同的概念。進(jìn)程具有五個(gè)基本特征，而程序則沒有。（1）

動(dòng)態(tài)性進(jìn)程的實(shí)質(zhì)是程序的一次執(zhí)行過程，因此，動(dòng)態(tài)性是進(jìn)程的最基本特征。動(dòng)態(tài)性還表現(xiàn)為：“它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤消而消亡”。可見，進(jìn)程有一定的生命期，而程序只是一組有序指令的集合，并存放于某種介質(zhì)上，本身并無運(yùn)動(dòng)的含義，因此是靜態(tài)的。（2）并發(fā)性這是指多個(gè)進(jìn)程能在一段時(shí)間內(nèi)同時(shí)運(yùn)行，并發(fā)性是進(jìn)程的重要特征。引入進(jìn)程的目的也正是為了使其程序能和其他進(jìn)程的程序并發(fā)執(zhí)行，而程序（沒有建立進(jìn)程）是不能并發(fā)執(zhí)行的（由于程序不反映執(zhí)行過程）。2．進(jìn)程的特征83(3)

獨(dú)立性

這是指進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立調(diào)度的基本單位，凡未建立進(jìn)程的程序，都不能作為一個(gè)獨(dú)立的單位參加運(yùn)行。（4）異步性

這是指進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)，或說進(jìn)程按異步方式運(yùn)行。（5）結(jié)構(gòu)特征

為使進(jìn)程能獨(dú)立運(yùn)行，應(yīng)為之配置一個(gè)稱為“進(jìn)程控制塊”的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱PCB。這樣，從結(jié)構(gòu)上看，進(jìn)程是由程序段、數(shù)據(jù)段及PCB三部分組成，有人把這三部分稱為“進(jìn)程映象”。（UNIX稱進(jìn)程的映象）。(3)獨(dú)立性這是指進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和843進(jìn)程和程序的聯(lián)系與區(qū)別：

（1）聯(lián)系。程序是構(gòu)成進(jìn)程的組成部分之一，一個(gè)進(jìn)程的運(yùn)行目標(biāo)是執(zhí)行它所對(duì)應(yīng)的程序，如果沒有程序，進(jìn)程就失去了其實(shí)際存在的意義。從靜態(tài)的角度看，進(jìn)程是由程序、數(shù)據(jù)和進(jìn)程控制塊三部分組成的。

（2）區(qū)別。程序是靜態(tài)的，而進(jìn)程是動(dòng)態(tài)的。進(jìn)程既是程序的執(zhí)行過程，因而進(jìn)程是有生命期的，有誕生，亦有消亡。因此，程序的存在是永久的，而進(jìn)程的存在是暫時(shí)的，動(dòng)態(tài)地產(chǎn)生和消亡。一個(gè)進(jìn)程可以執(zhí)行一個(gè)或幾個(gè)程序，一個(gè)程序亦可以構(gòu)成多個(gè)進(jìn)程。例如，一個(gè)編譯進(jìn)程在運(yùn)行時(shí)，要執(zhí)行詞法分析、語(yǔ)法分析、代碼生成和優(yōu)化等幾個(gè)程序，或者一個(gè)編譯程序可以同時(shí)生成幾個(gè)編譯進(jìn)程，為幾個(gè)用戶服務(wù)。進(jìn)程具有創(chuàng)建其他進(jìn)程的功能，被創(chuàng)建的進(jìn)程稱為子進(jìn)程，創(chuàng)建者稱為父進(jìn)程，從而構(gòu)成進(jìn)程家族。3進(jìn)程和程序的聯(lián)系與區(qū)別：

（1）聯(lián)系。程序是構(gòu)成85二、進(jìn)程的狀態(tài)及其轉(zhuǎn)換

進(jìn)程在運(yùn)行中不斷地改變其運(yùn)行狀態(tài)。通常，一個(gè)運(yùn)行進(jìn)程必須具有以下三種基本狀態(tài)：

1

進(jìn)程的基本狀態(tài)(由進(jìn)程運(yùn)行的間斷性，決定了進(jìn)程至少具有下述三種基本狀態(tài))①就緒狀態(tài)當(dāng)進(jìn)程已分配到除CPU以外的所有必要的資源后，只要能再獲得處理機(jī)，便能立即執(zhí)行，把進(jìn)程這時(shí)的狀態(tài)稱為就緒狀態(tài)。在一個(gè)系統(tǒng)中，可以有多個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)，通常把它們排成一個(gè)隊(duì)列，稱為就緒隊(duì)列。②執(zhí)行狀態(tài)指進(jìn)程已獲得處理機(jī)，其程序正在執(zhí)行。在單處理機(jī)系統(tǒng)中，只能有一個(gè)進(jìn)程正在執(zhí)行狀態(tài)。③阻塞狀態(tài)進(jìn)程因發(fā)生某事件（如請(qǐng)求I/O、申請(qǐng)緩沖空間等）而暫停執(zhí)行時(shí)的狀態(tài)，亦即進(jìn)程的執(zhí)行處于受到阻塞，故稱這種暫停狀態(tài)為阻塞狀態(tài)，有時(shí)也稱為“等待”狀態(tài)，或“睡眠”狀態(tài)。通常將處于阻塞狀態(tài)的進(jìn)程排成一個(gè)隊(duì)列，稱為阻塞隊(duì)列。二、進(jìn)程的狀態(tài)及其轉(zhuǎn)換862進(jìn)程狀態(tài)的轉(zhuǎn)換

就緒執(zhí)行阻塞執(zhí)行就緒阻塞進(jìn)程調(diào)度時(shí)間片用完、請(qǐng)求I/O操作、P操作I/O完成、V操作掛起狀態(tài)：系統(tǒng)需要進(jìn)程釋放某些資源。如系統(tǒng)內(nèi)存空間不足，可用掛起原語(yǔ)將進(jìn)程掛起，該進(jìn)程從內(nèi)存轉(zhuǎn)到外存，將活動(dòng)狀態(tài)變?yōu)閽炱馉顟B(tài)，由就緒態(tài)掛起后轉(zhuǎn)換為就緒掛起；由阻塞態(tài)掛起稱為阻塞掛起。它們被激活后分別轉(zhuǎn)換為就緒態(tài)和阻塞態(tài)。退出完成就掛等掛掛起激活掛起激活2進(jìn)程狀態(tài)的轉(zhuǎn)換就緒執(zhí)行阻塞執(zhí)行就緒阻塞進(jìn)程調(diào)度時(shí)間片用87三、進(jìn)程控制塊１．進(jìn)程控制塊的作用

為了描述和控制進(jìn)程的運(yùn)行,隨時(shí)跟蹤和記錄各進(jìn)程的變化情況，以及掌握進(jìn)程間的相互關(guān)系，系統(tǒng)為每個(gè)進(jìn)程配置了一個(gè)數(shù)據(jù)結(jié)構(gòu),該數(shù)據(jù)結(jié)構(gòu)被稱為進(jìn)程控制塊PCB（ProcessControlBlock）。所謂系統(tǒng)創(chuàng)建一個(gè)進(jìn)程，就是由系統(tǒng)為某個(gè)程序設(shè)置一個(gè)PCB，用于對(duì)該進(jìn)程進(jìn)行控制和管理。進(jìn)程任務(wù)完成，由系統(tǒng)收回其PCB，該進(jìn)程便消亡。系統(tǒng)將根據(jù)某PCB而感知相應(yīng)進(jìn)程的存在，故說PCB是進(jìn)程存在的唯一標(biāo)志。2．進(jìn)程控制塊中的內(nèi)容PCB中包含了進(jìn)程的描述信息和控制信息。主要有：進(jìn)程標(biāo)識(shí)符、現(xiàn)行狀態(tài)、現(xiàn)場(chǎng)保留區(qū)、程序與數(shù)據(jù)地址、互斥與同步機(jī)構(gòu)、進(jìn)程通信機(jī)構(gòu)、進(jìn)程優(yōu)先數(shù)、資源清單、鏈接字、家族聯(lián)系

進(jìn)程控制塊PCB是系統(tǒng)感知進(jìn)程存在的唯一實(shí)體。三、進(jìn)程控制塊88四、進(jìn)程的組成

進(jìn)程由程序、數(shù)據(jù)和PCB三部分組成。PCB是進(jìn)程的“靈魂”，由于進(jìn)程控制塊中保存有進(jìn)程的地址信息，通過PCB可以得到該進(jìn)程所對(duì)應(yīng)的程序的存儲(chǔ)位置。程序和數(shù)據(jù)是進(jìn)程的“軀體”。由于現(xiàn)代操作系統(tǒng)提供程序共享的功能，這就要求程序是可重入程序，且與數(shù)據(jù)分離。所謂可重入程序是指“純”代碼程序，即在運(yùn)行過程中不修改自身。四、進(jìn)程的組成89

§2．3進(jìn)程控制進(jìn)程和處理機(jī)管理的一個(gè)重要任務(wù)是進(jìn)程控制。所謂進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段（內(nèi)核）來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。即進(jìn)程控制的主要任務(wù)是創(chuàng)建和撤消進(jìn)程，以及實(shí)現(xiàn)進(jìn)程的狀態(tài)轉(zhuǎn)換等。進(jìn)程控制一般是由操作系統(tǒng)的內(nèi)核來實(shí)現(xiàn)的?！?．3進(jìn)程控制90OS內(nèi)核

在進(jìn)行層次設(shè)計(jì)時(shí)，往往指一些與硬件緊密相關(guān)的模塊或運(yùn)行頻率較高的模塊以及為許多模塊公用的一些基本操作，安排在靠近硬件的層次中，并使它們常駐內(nèi)層，以提高OS的運(yùn)行效率，通常將這一部分稱為OS的內(nèi)核。亦即OS內(nèi)核是OS常駐內(nèi)存的程序和數(shù)據(jù)。OS內(nèi)核91

一內(nèi)核的基本功能內(nèi)核包含系統(tǒng)支撐功能和資源管理功能中的許多基本操作。（1）中斷處理。這是操作系統(tǒng)中內(nèi)核的最基本功能，也是整個(gè)操作系統(tǒng)賴以活動(dòng)的基礎(chǔ)。通常，內(nèi)核只對(duì)中斷進(jìn)行“有限的處理”，然后便轉(zhuǎn)由有關(guān)進(jìn)程繼續(xù)處理；（2）進(jìn)程控制和管理。進(jìn)程管理的任務(wù)有四個(gè)：進(jìn)程的建立和撤消；進(jìn)程狀態(tài)的轉(zhuǎn)換。系統(tǒng)應(yīng)能使進(jìn)程從阻塞變?yōu)榫途w，把活動(dòng)進(jìn)程掛起或把掛起的進(jìn)程激活；進(jìn)程調(diào)度。進(jìn)行處理機(jī)的重新分配；控制進(jìn)程的并發(fā)執(zhí)行。保證進(jìn)程間的同步，實(shí)現(xiàn)相互全作進(jìn)程間的通信。（3）資源管理中的基本操作。包括對(duì)時(shí)鐘、I/O設(shè)備和文件系統(tǒng)進(jìn)行控制和管理的基本操作。

一內(nèi)核的基本功能92１特權(quán)指令特權(quán)指令是指只允許操作系統(tǒng)使用，而不允許一般用戶使用的指令。如啟動(dòng)I/O設(shè)備的指令、取寄取器狀態(tài)指令及對(duì)系統(tǒng)安全有影響的指令等。這些指令如果允許用戶隨便使用，就可能使系統(tǒng)陷入混亂。２．非特權(quán)指令特權(quán)指令以外的指令。非特權(quán)指令的執(zhí)行不影響其他用戶以及系統(tǒng)，如算術(shù)運(yùn)算指令、邏輯運(yùn)算指令、取操作數(shù)指令等。處理機(jī)的兩種執(zhí)行狀態(tài)，用它們來區(qū)分某程序是否享有特權(quán)。３．核心態(tài)（管態(tài)）計(jì)算機(jī)的一種工作方式，在此方式下，可以執(zhí)行任何指令，可以訪問全部主存。OS在核心態(tài)下運(yùn)行。4

用戶態(tài)（目態(tài)）計(jì)算機(jī)的另一種工作方式，在此方式下，不允許執(zhí)行特權(quán)指令，只允許訪問受限定的主存。用戶程序或其它系統(tǒng)程序在目態(tài)下運(yùn)行。１特權(quán)指令特權(quán)指令是指只允許操作系統(tǒng)使用，而不允許一般用935

原語(yǔ)（primitive）完成某一特定功能的程序段，其執(zhí)行是不可分割的。換言之，在一個(gè)操作中的所有動(dòng)作，要么全做，要么全不做。原語(yǔ)可分為兩類：一類是機(jī)器指令級(jí)的，其特點(diǎn)是執(zhí)行期間不允許中斷；另一類是功能級(jí)的，其特點(diǎn)是人作為原語(yǔ)的程序段不允許并發(fā)執(zhí)行。這兩類原語(yǔ)都在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個(gè)系統(tǒng)管理所需要的功能和被高層軟件所調(diào)用。進(jìn)程控制由原語(yǔ)實(shí)現(xiàn)。5

原語(yǔ)（primitive）完成某一特定功能的程序段94二、進(jìn)程的創(chuàng)建和撤消原語(yǔ)1．

創(chuàng)建原語(yǔ)一個(gè)進(jìn)程可借助于創(chuàng)建原語(yǔ)來創(chuàng)建一個(gè)新進(jìn)程。創(chuàng)建一個(gè)新進(jìn)程的主要工作是：

申請(qǐng)一空閑PCB→無空閑PCB，則創(chuàng)建失??；否則產(chǎn)生PID（進(jìn)程標(biāo)識(shí)）→申請(qǐng)必要的資源→初始化PCB→插入就緒隊(duì)列2．

撤消進(jìn)程原語(yǔ)找出被撤消進(jìn)程的PCB→該進(jìn)程若正在執(zhí)行，則終止該進(jìn)行的執(zhí)行→該進(jìn)程若有子進(jìn)程，則撤消其所有子進(jìn)程→將該進(jìn)程所擁有的全部資源，歸還給父進(jìn)程或系統(tǒng)→將被撤消進(jìn)程的PCB從所在隊(duì)列（或鏈表）中清除，放回到空閑PCB隊(duì)列。二、進(jìn)程的創(chuàng)建和撤消原語(yǔ)95三、進(jìn)程的阻塞和喚醒原語(yǔ)１．進(jìn)程的阻塞原語(yǔ)

正在執(zhí)行的進(jìn)程，當(dāng)出現(xiàn)請(qǐng)求操作系統(tǒng)服務(wù)、啟動(dòng)某種操作、新數(shù)據(jù)尚未到達(dá)、無新工作可做等事件時(shí)，由于無法繼續(xù)運(yùn)行，于是自己便通過調(diào)用block原語(yǔ)，把自己阻塞起來?？梢姡M(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為。進(jìn)入block過程后，由于此時(shí)進(jìn)程還在執(zhí)行，故而應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為“阻塞”，并將它插入到阻塞隊(duì)列。若系統(tǒng)中設(shè)置了由于不同事件而阻塞的多個(gè)阻塞隊(duì)列，則應(yīng)將該進(jìn)程插入到具有相同事件的阻塞（等待）隊(duì)列，最后，轉(zhuǎn)進(jìn)程調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，即保留被阻塞進(jìn)程的處理機(jī)狀態(tài)在PCB中，按新進(jìn)程PCB中的處理機(jī)狀態(tài)設(shè)置CPU狀態(tài)。保存CPU現(xiàn)場(chǎng)→置該進(jìn)程的狀態(tài)→被阻塞進(jìn)程入等待隊(duì)列→轉(zhuǎn)進(jìn)程調(diào)度。三、進(jìn)程的阻塞和喚醒原語(yǔ)962．進(jìn)程的喚醒原語(yǔ)

當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)，如I/O操作完成，其所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程（比如，用完并釋放了該I/O設(shè)備的進(jìn)程）調(diào)用喚醒原語(yǔ)weakup()，將等待該事件的進(jìn)程喚醒。喚醒原語(yǔ)的操作有：先把被阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB的現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該進(jìn)程插到就緒隊(duì)列中。

從等待隊(duì)列中摘下被喚醒進(jìn)程→置進(jìn)程的狀態(tài)→將被喚醒進(jìn)程送入就緒隊(duì)列→轉(zhuǎn)進(jìn)程調(diào)度或返回。應(yīng)當(dāng)指出：block原語(yǔ)和weakup原語(yǔ)是一對(duì)功能剛好相反的原語(yǔ)，因此，如果在某進(jìn)程中調(diào)用了阻塞原語(yǔ)，則必須