計算機三級進程管理課件

第二章進程管理

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

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

程序的順序執(zhí)行

一個程序通常可分成若干個程序段，它們必須按照某種先后次序執(zhí)行，僅當前一操作執(zhí)行完后，才能執(zhí)行后繼操作?！?．１前趨圖2C1P1I1C1P1I1C1P1I2C2P2C1P1I1C1P1I1C1P1I2C2P23

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

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

三

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

三

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

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

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

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

程序在并發(fā)執(zhí)行時，是多個程序共享一臺機器，因而機內(nèi)資源的狀態(tài)將由多個程序來改變，因此使程序的運行已失去了封閉性，這樣，某程序在執(zhí)行時，也必然會受到其他程序的影響，例如，當處理機資源被其他程序占有時，某程序必須等２．程序并發(fā)執(zhí)行所帶來的影響（特征）8（３）不可再現(xiàn)性程序在并發(fā)執(zhí)行時，也將失去其可再現(xiàn)性。例如，有兩個循環(huán)程序A和B，它們共享一個變量n。程序A每執(zhí)行一次時都要做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í)行時，也將失去其可再現(xiàn)性。例9

§2．2進程的基本概念

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

1.進程的定義

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

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

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

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

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

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

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

獨立性

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

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

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

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

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

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

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

1

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

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

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

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

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

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

在進行層次設計時，往往指一些與硬件緊密相關的模塊或運行頻率較高的模塊以及為許多模塊公用的一些基本操作，安排在靠近硬件的層次中，并使它們常駐內(nèi)層，以提高OS的運行效率，通常將這一部分稱為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)核的最基本功能，也是整個操作系統(tǒng)賴以活動的基礎。通常，內(nèi)核只對中斷進行“有限的處理”，然后便轉(zhuǎn)由有關進程繼續(xù)處理；（2）進程控制和管理。進程管理的任務有四個：進程的建立和撤消；進程狀態(tài)的轉(zhuǎn)換。系統(tǒng)應能使進程從阻塞變?yōu)榫途w，把活動進程掛起或把掛起的進程激活；進程調(diào)度。進行處理機的重新分配；控制進程的并發(fā)執(zhí)行。保證進程間的同步，實現(xiàn)相互全作進程間的通信。（3）資源管理中的基本操作。包括對時鐘、I/O設備和文件系統(tǒng)進行控制和管理的基本操作。

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

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

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

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

創(chuàng)建原語一個進程可借助于創(chuàng)建原語來創(chuàng)建一個新進程。創(chuàng)建一個新進程的主要工作是：

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

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

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

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

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

§2．4進程的互斥與同步

一、進程間的制約關系

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

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

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

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

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

當兩個進程按下述順序執(zhí)行時但若P1和P2按另一種順序?qū)ount進行修改

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都各自對count作了加

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

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

2.

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

repeat

entrysection

criticalsection

exitsection

remaindersection

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

進程互斥

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

進程互斥不允許多于一個事件在同一時刻發(fā)生。亦即指在31４．同步機制應遵循的準則

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

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

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

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

三、信號量機制1.

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

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

計錄型信號量機制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

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

§2．5進程通信一、

低級和高級進程通信方式

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

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

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

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

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

高級進程通信

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當一個緊急任務到達時，它不能立即投入運行，以至于延誤時機；②

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

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

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

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

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

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

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

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

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

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

時間片輪轉(zhuǎn)法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、檢測死鎖69PR1R2

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

四、死鎖的解除71

第二章進程管理

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

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

程序的順序執(zhí)行

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

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

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

三

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

三

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

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

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

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

程序在并發(fā)執(zhí)行時，是多個程序共享一臺機器，因而機內(nèi)資源的狀態(tài)將由多個程序來改變，因此使程序的運行已失去了封閉性，這樣，某程序在執(zhí)行時，也必然會受到其他程序的影響，例如，當處理機資源被其他程序占有時，某程序必須等２．程序并發(fā)執(zhí)行所帶來的影響（特征）79（３）不可再現(xiàn)性程序在并發(fā)執(zhí)行時，也將失去其可再現(xiàn)性。例如，有兩個循環(huán)程序A和B，它們共享一個變量n。程序A每執(zhí)行一次時都要做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í)行時，也將失去其可再現(xiàn)性。例80

§2．2進程的基本概念

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

1.進程的定義

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

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

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

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

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

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

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

獨立性

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

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

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

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

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

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

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

1

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

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

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

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

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

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

在進行層次設計時，往往指一些與硬件緊密相關的模塊或運行頻率較高的模塊以及為許多模塊公用的一些基本操作，安排在靠近硬件的層次中，并使它們常駐內(nèi)層，以提高OS的運行效率，通常將這一部分稱為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)核的最基本功能，也是整個操作系統(tǒng)賴以活動的基礎。通常，內(nèi)核只對中斷進行“有限的處理”，然后便轉(zhuǎn)由有關進程繼續(xù)處理；（2）進程控制和管理。進程管理的任務有四個：進程的建立和撤消；進程狀態(tài)的轉(zhuǎn)換。系統(tǒng)應能使進程從阻塞變?yōu)榫途w，把活動進程掛起或把掛起的進程激活；進程調(diào)度。進行處理機的重新分配；控制進程的并發(fā)執(zhí)行。保證進程間的同步，實現(xiàn)相互全作進程間的通信。（3）資源管理中的基本操作。包括對時鐘、I/O設備和文件系統(tǒng)進行控制和管理的基本操作。

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

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

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

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

創(chuàng)建原語一個進程可借助于創(chuàng)建原語來創(chuàng)建一個新進程。創(chuàng)建一個新進程的主要工作是：

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

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

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

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

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