計(jì)算機(jī)操作系統(tǒng) 第3章

1、第3章 進(jìn)程管理3.1 進(jìn)程的概念3.2 進(jìn)程的描述3.3 進(jìn)程狀態(tài)及其轉(zhuǎn)換3.4 進(jìn)程控制3.5 進(jìn)程互斥3.6 進(jìn)程同步3.7 進(jìn)程通信3.8 死鎖問題3.9 線程 3.1 進(jìn)程的概念 現(xiàn)代操作系統(tǒng)的重要特點(diǎn)：程序的并發(fā)執(zhí)行、資源共享、用戶隨機(jī)地使用。1.程序的順序執(zhí)行程序的順序執(zhí)行：程序獨(dú)占處理機(jī)直至最終結(jié)束的過程。程序的順序執(zhí)行具有如下特點(diǎn)：(1) 順序性程序順序執(zhí)行時(shí)，其執(zhí)行過程可看作一系列嚴(yán)格按程序規(guī)定的狀態(tài)轉(zhuǎn)移過程。(2) 封閉性程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因素的影響。(3) 可再現(xiàn)性只要輸入的初始條件相同，則無論何時(shí)重復(fù)執(zhí)行該程序都會(huì)得到相同的結(jié)果。2.

2、 多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化多道程序執(zhí)行的系統(tǒng)環(huán)境具有下述三個(gè)特點(diǎn)：(1) 獨(dú)立性每道程序都是邏輯上獨(dú)立的，它們之間不存在邏輯上的制約關(guān)系。(2) 隨機(jī)性在多道程序環(huán)境下，特別是在多用戶環(huán)境下，程序和數(shù)據(jù)的輸入與執(zhí)行開始時(shí)間都是隨機(jī)的。(3) 資源共享資源共享將導(dǎo)致對進(jìn)程執(zhí)行速度的制約。3. 程序的并發(fā)執(zhí)行(1) 什么是程序的并發(fā)執(zhí)行 并發(fā)執(zhí)行：即一道程序的執(zhí)行尚未結(jié)束；另一道程序的執(zhí)行已經(jīng)開始的執(zhí)行方式。是為了增強(qiáng)計(jì)算機(jī)系統(tǒng)的處理能力和提高資源利用率所采取的一種同時(shí)操作技術(shù)。程序的并發(fā)執(zhí)行可進(jìn)一步分為兩種：第一種是多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行。微觀上仍是順序

3、執(zhí)行，盡管多道程序的并發(fā)執(zhí)行在宏觀上是同時(shí)進(jìn)行的。第二種并發(fā)執(zhí)行是在某道程序的幾個(gè)程序段中（例如幾個(gè)程序），包含著一部分可以同時(shí)執(zhí)行或順序顛倒執(zhí)行的代碼。例如語句：read (a) ；read (b) ；它們既可以同時(shí)執(zhí)行，也可顛倒次序執(zhí)行。對于這樣的語句，同時(shí)執(zhí)行不會(huì)改變順序程序所具有的邏輯性質(zhì)。因此，可以采用并發(fā)執(zhí)行來充分利用系統(tǒng)資源以提高計(jì)算機(jī)的處理能力。程序的并發(fā)執(zhí)行可總結(jié)為：一組在邏輯上互相獨(dú)立的程序或程序段在執(zhí)行過程中，其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始的這種執(zhí)行方式。程序的并發(fā)執(zhí)行不同于程序的并行執(zhí)行。程序的并行執(zhí)行是指一組程序按獨(dú)

4、立的、異步的速度執(zhí)行。并行執(zhí)行不等于時(shí)間上的重疊?？梢詫⒉l(fā)執(zhí)行過程描述為：S0CobeginP1；P2；. PnCoendSn這里，S0，Sn分別表示并發(fā)程序段P1，P2，Pn開始執(zhí)行前和并發(fā)執(zhí)行結(jié)束后的語句。P1，2，Pn也可以由同一程序段中的不同語句組成。1966年Bernstein 提出了兩相鄰語句S1，S2可以并發(fā)執(zhí)行的條件：將程序中任一語句Si劃分為兩個(gè)變量的集合R(Si)和W(Si)。其中R(Si)=a1 a2 am，aj(j=1，m)是語句Si在執(zhí)行期間必須對其進(jìn)行讀操作的變量；W(Si)=b1 b2 bn，bj(j=1，n)是語句Si在執(zhí)行期間必須對其進(jìn)行寫操作的變量；如果對

5、于兩相鄰語句S1和S2，有 R(S1) W(S2)=， W(S1) R(S2)=， W(S1) W(S2)= 同時(shí)成立，則語句S1和S2是可以并發(fā)執(zhí)行的。多道執(zhí)行與單道執(zhí)行有何優(yōu)點(diǎn):例：有三個(gè)程序A、B、C；每個(gè)程序都由輸入、計(jì)算、輸出三部分代碼組成；記為Ai、Ac、Ao，Bi、Bc、Bo，Ci、Cc、Co；假設(shè)各部分代碼在相應(yīng)的設(shè)備上執(zhí)行的時(shí)間都為t；在單道環(huán)境下：總的運(yùn)行時(shí)間9t，輸入設(shè)備占用3t，輸出設(shè)備占用3t。 C P U 利用率3t9t3933.3 輸入設(shè)備利用率3t9t39 33.3 輸出設(shè)備利用率3t9t39 33.3 AiAoAcBiBoBcCiCcCoAiAoAcBiBoB

6、cCiCcCott時(shí)間ttttttt多道環(huán)境下：總的運(yùn)行時(shí)間5t，輸入設(shè)備占用3t，輸出設(shè)備占用3t。 C P U 利用率3t5t3560 輸入設(shè)備利用率3t5t3560 輸出設(shè)備利用率3t5t3560CPU時(shí)間片進(jìn) 程 A進(jìn) 程 B進(jìn) 程 CtAiAcAoBiBcBoCiCcCotttt輸入設(shè)備輸出設(shè)備CPU(2) 程序的并發(fā)執(zhí)行所帶來的影響程序的并發(fā)執(zhí)行充分地利用了系統(tǒng)資源，從而提高了系統(tǒng)的處理能力，這是并發(fā)執(zhí)行好的一方面。但是，正如前面所提到的那樣，由于系統(tǒng)資源有限，程序的并發(fā)執(zhí)行必然導(dǎo)致資源共享和資源競爭，從而改變程序的執(zhí)行速度。如果并發(fā)執(zhí)行的各程序段中語句或指令滿足上述Bernste

7、in 的三個(gè)條件，則認(rèn)為并發(fā)執(zhí)行不會(huì)對執(zhí)行結(jié)果的封閉性和可再現(xiàn)性產(chǎn)生影響。但在一般情況下，系統(tǒng)要判定并發(fā)執(zhí)行的各程序段是否滿足Bernstein 條件是相當(dāng)困難的。從而，如果并發(fā)執(zhí)行的程序段不按照特定的規(guī)則和方法進(jìn)行資源共享和競爭，則其執(zhí)行結(jié)果將不可避免地失去封閉性和可再現(xiàn)性。下面的例子說明了這一點(diǎn)。堆棧的取數(shù)和存數(shù)過程圖例：設(shè)有堆棧S，棧指針top，棧中存放內(nèi)存中相應(yīng)數(shù)據(jù)塊地址（如圖3.1(a)）設(shè)有兩個(gè)程序段getaddr(top)和reladdr(blk)，其中g(shù)etaddr(top)從給定的top所指棧中取出相應(yīng)的內(nèi)存數(shù)據(jù)塊地址，而reladdr(blk)則將內(nèi)存數(shù)據(jù)塊地址blk放入堆

8、棧S中。getaddr(top)和reladdr(blk)可分別描述為：procedure getaddr(top)beginlocal rr (top)top top-1return(r)endprocedure reladdr(blk)例：利用堆棧管理一塊內(nèi)存區(qū)中各數(shù)據(jù)塊的使用情況。用getaddr(top) 從棧頂取出相應(yīng)的內(nèi)存塊的地址。用reladdr(blk)將數(shù)據(jù)塊的地址（以bkl為地址）放入堆棧中。proc getaddr(top) Begin local r; 1.1 r stop; 1.2 top top-1; 1.3 return (r);end;Proc reladdr(

9、blk) Begin 2.1 top top+1; 2.2 stop blk; End;分析getaddr(top) 與reladdr(blk)的并發(fā)執(zhí)行012345t abtop2.1 top top+11.1 r stop1.2 top top-11.3 return (r)2.2 stop blktoptop blk上例中的程序段并發(fā)執(zhí)行出現(xiàn)錯(cuò)誤結(jié)果是由于兩程序段共享資源堆棧S，從而使得執(zhí)行結(jié)果受執(zhí)行速度影響。一般情況下，并發(fā)執(zhí)行的各程序段如果共享軟、硬件資源，都會(huì)造成其執(zhí)行結(jié)果受執(zhí)行速度影響的局面。顯然，這是程序設(shè)計(jì)人員不希望看到的。為了使得在并發(fā)執(zhí)行時(shí)不出現(xiàn)錯(cuò)誤結(jié)果，必須采取某些措施

10、來制約、控制各并發(fā)程序段的執(zhí)行速度。這在操作系統(tǒng)程序設(shè)計(jì)中尤其重要，因?yàn)椴僮飨到y(tǒng)用戶隨機(jī)性與各道程序邏輯獨(dú)立的特點(diǎn)將使得每個(gè)用戶程序所使用的軟、硬件資源都受到其他并發(fā)程序的共享和競爭，從而得到非預(yù)料的或不正確的結(jié)果。為了控制和協(xié)調(diào)各程序段執(zhí)行過程中的軟、硬件資源的共享和競爭，顯然，必須應(yīng)該有一個(gè)描述各程序段執(zhí)行過程和共享資源的基本單位。從上述討論可以看出，由于程序的順序性、靜態(tài)性以及孤立性，用程序段作為描述其執(zhí)行過程和共享資源的基本單位既增加操作系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的復(fù)雜性，也無法反映操作系統(tǒng)所應(yīng)該具有的程序段執(zhí)行的并發(fā)性、用戶隨機(jī)性，以及資源共享等特征。也就是說，用程序作為描述其執(zhí)行過程以及共享資

11、源的基本單位是不合適的。需要有一個(gè)能描述程序的執(zhí)行過程且能用來共享資源的基本單位。這個(gè)基本單位被稱為進(jìn)程（或任務(wù)）。3.1.2 進(jìn)程的定義進(jìn)程的概念是60年代初期，首先在MIT 的 Multics系統(tǒng)和IBM 的 TSS/360系統(tǒng)中引用的。進(jìn)程的定義：一個(gè)具有獨(dú)立功能的程序?qū)δ硞€(gè)數(shù)據(jù)集在處理機(jī)上的執(zhí)行過程和分配資源的基本單位。進(jìn)程和程序是兩個(gè)既有聯(lián)系又有區(qū)別的概念，它們的區(qū)別和關(guān)系可簡述如下：(1) 進(jìn)程是一個(gè)動(dòng)態(tài)概念，而程序則是一個(gè)靜態(tài)概念。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進(jìn)程則強(qiáng)調(diào)執(zhí)行過程，它動(dòng)態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。(2) 進(jìn)程具有并行特征，而程序沒有。由進(jìn)程的定義

12、可知，進(jìn)程具有并行特征的兩個(gè)方面，即獨(dú)立性和異步性。也就是說，在不考慮資源共享的情況下，各進(jìn)程的執(zhí)行是獨(dú)立的，執(zhí)行速度是異步的。顯然，由于程序不反映執(zhí)行過程，所以不具有并行特征。(3) 進(jìn)程是競爭計(jì)算機(jī)系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)自己的制約。這里，制約就是對進(jìn)程獨(dú)立性和異步性的限制。(4) 不同的進(jìn)程可以包含同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。3.1.3 作業(yè)和進(jìn)程的關(guān)系作業(yè)是用戶需要計(jì)算機(jī)完成某項(xiàng)任務(wù)時(shí)要求計(jì)算機(jī)所作工作的集合。進(jìn)程是已提交完畢程序的執(zhí)行過程的描述，是資源分配的基本單位。區(qū)別與關(guān)系：(1) 作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。在用戶向計(jì)算機(jī)提交作業(yè)之后，系統(tǒng)

13、將它放入外存中的作業(yè)等待隊(duì)列中等待執(zhí)行。而進(jìn)程則是完成用戶任務(wù)的執(zhí)行實(shí)體，是向系統(tǒng)申請分配資源的基本單位。任一進(jìn)程，只要它被創(chuàng)建，總有相應(yīng)的部分存在于內(nèi)存中。(2) 一個(gè)作業(yè)可由多個(gè)進(jìn)程組成。且必須至少由一個(gè)進(jìn)程組成，但反過來不成立。(3) 作業(yè)的概念主要用在批處理系統(tǒng)中。而進(jìn)程的概念則用在幾乎所有的多道系統(tǒng)中。3.2 進(jìn)程的描述從處理機(jī)的活動(dòng)角度來看，又如何識(shí)別描述程序執(zhí)行活動(dòng)的進(jìn)程呢？顯然，系統(tǒng)中需要有描述進(jìn)程存在和能夠反映其變化的物理實(shí)體，即進(jìn)程的靜態(tài)描述。進(jìn)程的靜態(tài)描述由三部分組成：進(jìn)程控制塊PCB，有關(guān)程序段和該程序段對其進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)集。進(jìn)程控制塊包含了有關(guān)進(jìn)程的描述信息、控制

14、信息以及資源信息，是進(jìn)程動(dòng)態(tài)特征的集中反映。系統(tǒng)根據(jù)PCB感知進(jìn)程的存在和通過PCB中所包含的各項(xiàng)變量的變化，掌握進(jìn)程所處的狀態(tài)以達(dá)到控制進(jìn)程活動(dòng)的目的。由于進(jìn)程的PCB 是系統(tǒng)感知進(jìn)程的唯一實(shí)體，因此，在幾乎所有的多道操作系統(tǒng)中，一個(gè)進(jìn)程的PCB結(jié)構(gòu)都是全部或部分常駐內(nèi)存的。進(jìn)程的程序部分描述進(jìn)程所要完成的功能。而數(shù)據(jù)結(jié)構(gòu)集是程序在執(zhí)行時(shí)必不可少的工作區(qū)和操作對象。這兩部分是進(jìn)程完成所需功能的物質(zhì)基礎(chǔ)。由于進(jìn)程的這兩部分內(nèi)容與控制進(jìn)程的執(zhí)行及完成進(jìn)程功能直接有關(guān)，因而，在大部分多道操作系統(tǒng)中，這兩部分內(nèi)容放在外存中，直到該進(jìn)程執(zhí)行時(shí)再調(diào)入內(nèi)存。下面分別介紹進(jìn)程的PCB結(jié)構(gòu)、程序與數(shù)據(jù)結(jié)構(gòu)集。

15、3.2.1 進(jìn)程控制塊PCB PCB包含一個(gè)進(jìn)程的描述信息、控制信息及資源信息，有些系統(tǒng)中還有進(jìn)程調(diào)度等待所使用的現(xiàn)場保護(hù)區(qū)。PCB 集中反映一個(gè)進(jìn)程的動(dòng)態(tài)特征。在創(chuàng)建一個(gè)進(jìn)程時(shí)，應(yīng)首先創(chuàng)建其 PCB，然后才能根據(jù)PCB 中信息對進(jìn)程實(shí)施有效的管理和控制。當(dāng)一個(gè)進(jìn)程完成其功能之后，系統(tǒng)則釋放PCB，進(jìn)程也隨之消亡。根據(jù)操作系統(tǒng)的要求不同，PCB的內(nèi)容會(huì)有所不同。下面所示基本內(nèi)容是必需的：(1) 描述信息 進(jìn)程名或進(jìn)程標(biāo)識(shí)號(hào)、 用戶名或用戶標(biāo)識(shí)號(hào)、 家族關(guān)系。(2) 控制信息 進(jìn)程當(dāng)前狀態(tài)進(jìn)程在活動(dòng)期間可分為就緒態(tài)、執(zhí)行態(tài)和等待狀態(tài)。 進(jìn)程優(yōu)先級(jí)進(jìn)程優(yōu)先級(jí)是選取進(jìn)程占有處理機(jī)的重要依據(jù)。 程序開

16、始地址 各種計(jì)時(shí)信息 通信信息(3) 資源管理信息PCB 中包含最多的是資源管理信息，包括有關(guān)存儲(chǔ)器的信息、使用輸入輸出設(shè)備的信息、有關(guān)文件系統(tǒng)的信息等。這些信息有： 占用內(nèi)存大小及其管理用數(shù)據(jù)結(jié)構(gòu)指針，例如后述內(nèi)存管理中所用到的進(jìn)程頁表指針等。 對換或覆蓋用的有關(guān)信息，如對換程序段長度，對換外存地址等。這些信息在進(jìn)程申請、釋放內(nèi)存中使用。 共享程序段大小及起始地址。 輸入輸出設(shè)備的設(shè)備號(hào)，所要傳送的數(shù)據(jù)長度、緩沖區(qū)地址、緩沖區(qū)長度及所用設(shè)備的有關(guān)數(shù)據(jù)結(jié)構(gòu)指針等。這些信息在進(jìn)程申請釋放設(shè)備進(jìn)行數(shù)據(jù)傳輸中使用。 指向文件系統(tǒng)的指針及有關(guān)標(biāo)識(shí)等。進(jìn)程可使用這些信息對文件系統(tǒng)進(jìn)行操作。(4) CPU

17、 現(xiàn)場保護(hù)結(jié)構(gòu)當(dāng)前進(jìn)程因等待某個(gè)事件而進(jìn)入等待狀態(tài)或因某種事件發(fā)生被中止在處理機(jī)上的執(zhí)行時(shí)，為了以后該進(jìn)程能在被打斷處恢復(fù)執(zhí)行，需要保護(hù)當(dāng)前進(jìn)程的 CPU現(xiàn)場（或稱進(jìn)程上下文）。PCB 中設(shè)有專門的 CPU現(xiàn)場保護(hù)結(jié)構(gòu)，以存儲(chǔ)退出執(zhí)行時(shí)的進(jìn)程現(xiàn)場數(shù)據(jù)?？傊?，進(jìn)程控制塊PCB 是系統(tǒng)感知進(jìn)程存在的唯一實(shí)體。通過對PCB 的操作，給進(jìn)程分配資源、調(diào)度進(jìn)程執(zhí)行、釋放進(jìn)程所占有的各種資源；而完成進(jìn)程所要求功能的程序段的有關(guān)地址，以及程序段在進(jìn)程過程中因某種原因被停止執(zhí)行后的現(xiàn)場信息也都在PCB 中。由于PCB 中包含有較多的信息，因此，一個(gè)PCB表往往要占據(jù)較大的存儲(chǔ)空間（一般占幾百到幾千個(gè)字節(jié)）。在

18、有的系統(tǒng)中，為了減少 PCB對內(nèi)存的占用量，只允許PCB中最常用的部分，如CPU現(xiàn)場保護(hù)、進(jìn)程描述信息、控制信息等常駐內(nèi)存。PCB 結(jié)構(gòu)中的其他部分則存放于外存之中，待該進(jìn)程將要執(zhí)行時(shí)與其他數(shù)據(jù)一起裝入內(nèi)存。近年來，面向?qū)ο蠹夹g(shù)已被用于操作系統(tǒng)設(shè)計(jì)。在面向?qū)ο蟮牟僮飨到y(tǒng)中，進(jìn)程的描述將采用其他方式。3.2.2 進(jìn)程上下文本節(jié)介紹包括程序段和數(shù)據(jù)集在內(nèi)的上下文的概念。進(jìn)程上下文實(shí)際上是進(jìn)程執(zhí)行活動(dòng)全過程的靜態(tài)描述。具體地說，進(jìn)程上下文包括計(jì)算機(jī)系統(tǒng)中與執(zhí)行該進(jìn)程有關(guān)的各種寄存器的值、程序段在經(jīng)過編譯之后形成的機(jī)器指令代碼集（或稱正文段）、數(shù)據(jù)集及各種堆棧值和PCB結(jié)構(gòu)(圖3.2)。這里，有關(guān)寄存

19、器和棧區(qū)的內(nèi)容是重要的。例如，沒有程序計(jì)數(shù)器PC和程序狀態(tài)寄存器PS，CPU將無法知道下條待執(zhí)行指令的地址和控制有關(guān)操作。從CPU是活動(dòng)的觀點(diǎn)來靜態(tài)地看一個(gè)進(jìn)程時(shí)，必須把有關(guān)寄存器和棧區(qū)的內(nèi)容也包括在其中。無論在何種系統(tǒng)中，進(jìn)程上下文的各部分都必須按一定的規(guī)則有機(jī)地組合起來以便于執(zhí)行。圖3.2 進(jìn)程上下文結(jié)構(gòu)進(jìn)程上下文可按一定的執(zhí)行層次組合，例如用戶級(jí)上下文、系統(tǒng)級(jí)上下文等。顯然，一個(gè)進(jìn)程的執(zhí)行是在該進(jìn)程的上下文中執(zhí)行，而當(dāng)系統(tǒng)調(diào)度新進(jìn)程占有處理機(jī)時(shí)，新老進(jìn)程的上下文發(fā)生轉(zhuǎn)換。在UNIX System 中，進(jìn)程上下文由用戶級(jí)上下文、寄存器上下文以及系統(tǒng)級(jí)上下文組成。用戶級(jí)上下文由進(jìn)程的用戶程序

20、段部分編譯而成的用戶正文段、用戶數(shù)據(jù)、用戶棧等組成。而寄存器上下文則由程序寄存器PC、處理機(jī)狀態(tài)字寄存器PS、棧指針和通用寄存器的值組成。其中PC給出CPU 將要執(zhí)行的下條指令的虛地址；PS給出機(jī)器與該進(jìn)程相關(guān)聯(lián)時(shí)的硬件狀態(tài)，例如當(dāng)前執(zhí)行模式、能否執(zhí)行特權(quán)指令等；棧指針指向下一項(xiàng)的當(dāng)前地址，而通用寄存器則用于不同執(zhí)行模式之間的參數(shù)傳遞等。進(jìn)程的系統(tǒng)級(jí)上下文又分為靜態(tài)部分與動(dòng)態(tài)部分。這里的動(dòng)態(tài)部分不是指程序的執(zhí)行，而是指在進(jìn)入和退出不同的上下文層次時(shí)，系統(tǒng)為各層上下文中相關(guān)聯(lián)的寄存器值所保存和恢復(fù)的記錄。系統(tǒng)級(jí)上下文的靜態(tài)部分包括PCB 結(jié)構(gòu)（UNIX系統(tǒng)中的 PCB結(jié)構(gòu)被分為proc結(jié)構(gòu)和us

21、er結(jié)構(gòu)兩部分）、將進(jìn)程虛地址空間映射到物理空間用的有關(guān)表格和核心棧。這里，核心棧主要用來裝載進(jìn)程中所使用系統(tǒng)調(diào)用的調(diào)用序列。系統(tǒng)級(jí)上下文的動(dòng)態(tài)部分是與寄存器上下文相關(guān)聯(lián)的。進(jìn)程上下文的層次概念也主要體現(xiàn)在動(dòng)態(tài)部分中，即系統(tǒng)級(jí)上下文的動(dòng)態(tài)部分可看成是一些數(shù)量變化的層次組成。其變化規(guī)則滿足先進(jìn)后出的堆棧方式，每個(gè)上下文層次在棧中各占一項(xiàng)。UNIX System 的進(jìn)程上下文組成如圖3.3。圖3.3 UNIX System 進(jìn)程上下文組成3.2.3 進(jìn)程空間任一進(jìn)程，都有一個(gè)自己的地址空間，把該空間稱為進(jìn)程空間或虛空間。進(jìn)程空間的大小只與處理機(jī)的位數(shù)有關(guān)。在UNIX以及Linux等操作系統(tǒng)中，進(jìn)程

22、空間還被劃分為用戶空間和系統(tǒng)空間兩大部分。在進(jìn)程空間被劃分為兩大部分后，用戶程序在用戶空間內(nèi)執(zhí)行，而操作系統(tǒng)內(nèi)核程序則在進(jìn)程的系統(tǒng)空間內(nèi)執(zhí)行。為防止用戶程序訪問系統(tǒng)空間，造成訪問出錯(cuò)，系統(tǒng)通過程序狀態(tài)寄存器等設(shè)置不同的執(zhí)行模式，即用戶模式和系統(tǒng)模式來進(jìn)行保護(hù)。 3.3 進(jìn)程狀態(tài)及其轉(zhuǎn)換3.3.1 進(jìn)程狀態(tài)一個(gè)進(jìn)程的生命期可以劃分為一組狀態(tài)，這些狀態(tài)刻劃了整個(gè)進(jìn)程。系統(tǒng)根據(jù)PCB 結(jié)構(gòu)中的狀態(tài)值控制進(jìn)程。在進(jìn)程的生命期內(nèi)，一個(gè)進(jìn)程至少具有三種基本狀態(tài)，它們是：執(zhí)行狀態(tài)、等待狀態(tài)和就緒狀態(tài)。處于就緒狀態(tài)的進(jìn)程已經(jīng)得到除 CPU之外的其他資源，只要由調(diào)度得到處理機(jī)，便可立即投入執(zhí)行。在有些系統(tǒng)中，為

23、了有效地利用內(nèi)存，就緒狀態(tài)又可進(jìn)一步分為內(nèi)存就緒狀態(tài)和外存就緒狀態(tài)。在這樣的系統(tǒng)中，只有處于內(nèi)存就緒狀態(tài)的進(jìn)程在得到處理機(jī)后才能立即投入執(zhí)行。而處于外存就緒狀態(tài)的進(jìn)程只有先成為內(nèi)存就緒狀態(tài)后，才可能被調(diào)度執(zhí)行。這種方式明顯地提高了內(nèi)存的利用效率，但反過來也增加了系統(tǒng)開銷和系統(tǒng)復(fù)雜性。在單CPU系統(tǒng)中，任一時(shí)刻處于執(zhí)行狀態(tài)的進(jìn)程只能有一個(gè)。只有處于就緒狀態(tài)的進(jìn)程經(jīng)調(diào)度選中之后才可進(jìn)入執(zhí)行狀態(tài)。在某些操作系統(tǒng)中，一個(gè)進(jìn)程在其生命期內(nèi)的執(zhí)行過程中，總要涉及到用戶程序和操作系統(tǒng)內(nèi)核程序兩部分。因此，進(jìn)程的執(zhí)行狀態(tài)又可進(jìn)一步劃分為用戶執(zhí)行狀態(tài)和系統(tǒng)執(zhí)行狀態(tài)。劃分用戶態(tài)和系統(tǒng)態(tài)最主要的原因是要把用戶程序和

24、系統(tǒng)程序區(qū)分開來，以利于程序的共享和保護(hù)。顯然，這也是以增加系統(tǒng)復(fù)雜度和系統(tǒng)開銷為代價(jià)的。進(jìn)程因等待某個(gè)事件發(fā)生而放棄處理機(jī)進(jìn)入等待狀態(tài)。顯然，等待狀態(tài)可根據(jù)等待事件的種類而進(jìn)一步劃分為不同的子狀態(tài)，例如內(nèi)存等待、設(shè)備等待、文件等待和數(shù)據(jù)等待等。這樣做的好處是系統(tǒng)控制簡單，發(fā)現(xiàn)和喚醒相應(yīng)的進(jìn)程較為容易。但系統(tǒng)中設(shè)置過多的狀態(tài)又會(huì)造成系統(tǒng)參數(shù)和狀態(tài)轉(zhuǎn)換過程的增加。3.3.2 進(jìn)程狀態(tài)轉(zhuǎn)換進(jìn)程的狀態(tài)反映進(jìn)程執(zhí)行過程的變化。這些狀態(tài)隨著進(jìn)程的執(zhí)行和外界條件發(fā)生變化和轉(zhuǎn)換。那么，是什么樣的條件使得進(jìn)程各狀態(tài)發(fā)生轉(zhuǎn)換呢？示圖給出了三個(gè)基本狀態(tài)，即就緒狀態(tài)、執(zhí)行狀態(tài)與等待狀態(tài)之間的轉(zhuǎn)換關(guān)系。事實(shí)上，進(jìn)程的

25、狀態(tài)轉(zhuǎn)換是一個(gè)非常復(fù)雜的過程。從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換除了要使用不同的控制過程（將在下節(jié)中講述），有時(shí)還要借助于硬件觸發(fā)器才能完成。例如，在 UNIX 系統(tǒng)中，從系統(tǒng)態(tài)到用戶態(tài)的轉(zhuǎn)換要借助硬件觸發(fā)器完成。 進(jìn)程狀態(tài)轉(zhuǎn)換圖3.4 進(jìn) 程 控 制進(jìn)程和處理機(jī)管理的一個(gè)重要任務(wù)是進(jìn)程控制。所謂進(jìn)程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。一般地，把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。原語可分為兩類：一類是機(jī)器指令級(jí)的，其特點(diǎn)是執(zhí)行期間不允許中斷。另一類是功能級(jí)的，其特點(diǎn)是作為原語的程序

26、段不允許并發(fā)執(zhí)行。這兩類原語都在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個(gè)系統(tǒng)管理所需要的功能和被高層軟件所調(diào)用。顯然，系統(tǒng)在創(chuàng)建、撤消一個(gè)進(jìn)程以及要改變進(jìn)程的狀態(tài)時(shí)，都要調(diào)用相應(yīng)的程序段來完成這些功能。那么，這些程序段是不是原語呢？如果它們不是原語，則由上述原語的定義可知，這些程序段是允許并發(fā)執(zhí)行的。然而，如果不加控制和管理地讓這些控制進(jìn)程狀態(tài)轉(zhuǎn)換及創(chuàng)建和撤消進(jìn)程的程序段并發(fā)執(zhí)行，則會(huì)使得其執(zhí)行結(jié)果失去封閉性和可再現(xiàn)性，從而達(dá)不到進(jìn)程控制的目的。反過來，如果對這些程序段采用下面章節(jié)中所述的控制方法使其在并發(fā)執(zhí)行過程中也能完成進(jìn)程控制任務(wù)的話，將會(huì)大大增加系統(tǒng)的開銷和復(fù)雜度。因此，在操作系統(tǒng)中，通常把進(jìn)

27、程控制用程序段做成原語。用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。3.4.1 進(jìn)程創(chuàng)建與撤消1. 進(jìn)程創(chuàng)建(1) 由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建，例如在批處理系統(tǒng)中，由操作系統(tǒng)的作業(yè)調(diào)度程序?yàn)橛脩糇鳂I(yè)創(chuàng)建相應(yīng)的進(jìn)程以完成用戶作業(yè)所要求的功能。(2) 由父進(jìn)程創(chuàng)建，例如在層次結(jié)構(gòu)的系統(tǒng)中，父進(jìn)程創(chuàng)建子進(jìn)程以完成并行工作。由系統(tǒng)統(tǒng)一創(chuàng)建的進(jìn)程之間的關(guān)系是平等的，它們之間一般不存在資源繼承關(guān)系。而在父進(jìn)程創(chuàng)建的進(jìn)程之間則存在隸屬關(guān)系，且互相構(gòu)成樹型結(jié)構(gòu)的家族關(guān)系。屬于某個(gè)家族的一個(gè)進(jìn)程可以繼承其父進(jìn)程所擁有的資源。另外，無論是哪一種方式創(chuàng)建進(jìn)程，在系統(tǒng)生成時(shí)，都必須由操作系統(tǒng)創(chuàng)建一部分

28、承擔(dān)系統(tǒng)資源分配和管理工作的系統(tǒng)進(jìn)程。無論是系統(tǒng)創(chuàng)建方式還是父進(jìn)程創(chuàng)建方式，都必須調(diào)用創(chuàng)建原語來實(shí)現(xiàn)。2. 進(jìn)程撤消以下幾種情況導(dǎo)致進(jìn)程被撤消：(1) 該進(jìn)程已完成所要求的功能而正常終止。(2) 由于某種錯(cuò)誤導(dǎo)致非正常終止。(3) 祖先進(jìn)程要求撤消某個(gè)子進(jìn)程。無論哪一種情況導(dǎo)致進(jìn)程被撤消，進(jìn)程都必須釋放它所占用的各種資源和PCB 結(jié)構(gòu)本身，以利于資源的有效利用。另外，當(dāng)一個(gè)祖先進(jìn)程撤消某個(gè)子進(jìn)程時(shí)，還需審查該子進(jìn)程是否還有自己的子孫進(jìn)程，若有的話，還需撤消其子孫進(jìn)程的 PCB結(jié)構(gòu)和釋放它們所占有的資源。撤消原語首先檢查 PCB進(jìn)程鏈或進(jìn)程家族，尋找所要撤消的進(jìn)程是否存在。如果找到了所要撤消的進(jìn)

29、程的 PCB結(jié)構(gòu)，則撤消原語釋放該進(jìn)程所占有的資源之后，把對應(yīng)的 PCB結(jié)構(gòu)從進(jìn)程鏈或進(jìn)程家族中摘下并返回給 PCB空隊(duì)列。如果被撤消的進(jìn)程有自己的子進(jìn)程，則撤消原語先撤消其子進(jìn)程的 PCB結(jié)構(gòu)并釋放子進(jìn)程所占用的資源之后，再撤消當(dāng)前進(jìn)程的 PCB結(jié)構(gòu)和釋放其資源。3.4.2 進(jìn)程的阻塞與喚醒進(jìn)程的創(chuàng)建原語和撤消原語完成了進(jìn)程從無到有，從存在到消亡的變化。被創(chuàng)建后的進(jìn)程最初處于就緒狀態(tài)，然后經(jīng)調(diào)度程序選中后進(jìn)入執(zhí)行狀態(tài)。這里主要介紹實(shí)現(xiàn)進(jìn)程的執(zhí)行狀態(tài)到等待狀態(tài)，又由等待狀態(tài)到就緒狀態(tài)轉(zhuǎn)換的兩種原語，即阻塞原語與喚醒原語。阻塞原語在一個(gè)進(jìn)程期待某一事件發(fā)生，但發(fā)生條件尚不具備時(shí)，被該進(jìn)程自己調(diào)用

30、來阻塞自己。阻塞原語在阻塞一個(gè)進(jìn)程時(shí)，由于該進(jìn)程正處于執(zhí)行狀態(tài)，故應(yīng)先中斷處理機(jī)和保存該進(jìn)程的CPU現(xiàn)場。然后將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。阻塞原語的實(shí)現(xiàn)過程如圖。這里，轉(zhuǎn)進(jìn)程調(diào)度程序是很重要的，否則，處理機(jī)將會(huì)出現(xiàn)空轉(zhuǎn)而浪費(fèi)資源。阻塞原語圖當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，等待該事件的所有進(jìn)程都將被喚醒。喚醒一個(gè)進(jìn)程有兩種方法：一種是由系統(tǒng)進(jìn)程喚醒。另一種是由事件發(fā)生進(jìn)程喚醒。當(dāng)由系統(tǒng)進(jìn)程喚醒等待進(jìn)程時(shí)，系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進(jìn)程。從而使得該進(jìn)程因等待事件已發(fā)生而進(jìn)入就緒隊(duì)列。由事件發(fā)生進(jìn)程喚醒時(shí)

31、，事件發(fā)生進(jìn)程和被喚醒進(jìn)程之間是合作關(guān)系。因此，喚醒原語既可被系統(tǒng)進(jìn)程調(diào)用，也可被事件發(fā)生進(jìn)程調(diào)用。稱調(diào)用喚醒原語的進(jìn)程為喚醒進(jìn)程。喚醒原語首先將被喚醒進(jìn)程從相應(yīng)的等待隊(duì)列中摘下，將被喚醒進(jìn)程置為就緒狀態(tài)之后，送入就緒隊(duì)列。在把被喚醒進(jìn)程送入就緒隊(duì)列之后，喚醒原語既可以返回原調(diào)用程序，也可以轉(zhuǎn)向進(jìn)程調(diào)度，以便讓調(diào)度程序有機(jī)會(huì)選擇一個(gè)合適的進(jìn)程執(zhí)行。如圖：喚醒原語圖3.5 進(jìn) 程 互 斥3.5.1 資源共享所引起的制約進(jìn)程的并發(fā)執(zhí)行不僅僅是用戶程序的執(zhí)行開始時(shí)間的隨機(jī)性和提高資源利用率的結(jié)果，也是資源有限性導(dǎo)致資源的競爭與共享對進(jìn)程的執(zhí)行過程進(jìn)行制約所造成的。1. 臨界區(qū)在描述一個(gè)程序或算法時(shí)，

32、總是認(rèn)為存在一個(gè)偽處理機(jī)，可以按程序或算法所規(guī)定的步驟來執(zhí)行該程序或算法的。但是，事實(shí)上，在實(shí)際的系統(tǒng)中則往往不是這樣。一般說來，即使在程序中所描述的一條語句，也是由多條執(zhí)行指令構(gòu)成的。例如，各種程序中經(jīng)常出現(xiàn)的賦值語句：X=X+1；在用匯編語言書寫時(shí)，就變成：LOADA，XADDIA，1STOREA，X等三條語句，這里 A代表累加器。根據(jù)系統(tǒng)的設(shè)計(jì)和要求，在這三條語句的執(zhí)行期間，也有可能發(fā)生中斷或調(diào)度，從而使得與當(dāng)前進(jìn)程無關(guān)的程序得以執(zhí)行。為了保證程序執(zhí)行最終結(jié)果的正確性，必須對并發(fā)執(zhí)行的各進(jìn)程進(jìn)行制約，以控制它們的執(zhí)行速度和對資源的競爭。在進(jìn)程的概念一節(jié)中已經(jīng)介紹了進(jìn)程中兩相鄰語句可并發(fā)執(zhí)

33、行的三個(gè)條件。是否有一種更為簡單的辦法來檢查出需要對程序的哪些部分進(jìn)行制約才能保證其執(zhí)行結(jié)果的正確性呢？這里來看下面的例子。設(shè)有兩個(gè)計(jì)算進(jìn)程A，B共享內(nèi)存S。其中 S分為三個(gè)領(lǐng)域，即系統(tǒng)區(qū)、進(jìn)程工作區(qū)和數(shù)據(jù)區(qū)。這里數(shù)據(jù)區(qū)被劃分大小相等的塊，每個(gè)塊中既可能放有數(shù)據(jù)，也有可能未放有數(shù)據(jù)。系統(tǒng)區(qū)主要是堆棧，其中存放那些空數(shù)據(jù)塊的地址。多進(jìn)程共享內(nèi)存棧區(qū)示例圖當(dāng)進(jìn)程A或B要求空數(shù)據(jù)塊時(shí)，從堆棧最頂部（top指針?biāo)傅奈恢茫┤〕鏊钄?shù)據(jù)塊。當(dāng)進(jìn)程A或B釋放數(shù)據(jù)塊時(shí)，則把所釋放數(shù)據(jù)塊的地址放入堆棧頂部。令getspace 為取空數(shù)據(jù)塊過程，release(ad)為釋放數(shù)據(jù)塊過程。這里，ad為待釋放數(shù)據(jù)塊的

34、地址。如果堆棧非空的話，進(jìn)程A或B是可以用任意的順序釋放和獲取數(shù)據(jù)塊的。執(zhí)行g(shù)etspace就是獲取一個(gè)空數(shù)據(jù)塊，而執(zhí)行release(ad)就是釋放一個(gè)地址為ad的數(shù)據(jù)塊。然而，由下面的描述可以看到，在進(jìn)程并發(fā)執(zhí)行時(shí)，getspace或 release(ad)將有可能完不成所要求的功能。getspace和 release(ad)可進(jìn)一步描述為：getspace:beginlocalggstack top toptop-1endrelease(ad):begin top top+1stack top adend設(shè)時(shí)刻t0時(shí)，top=h0，則getspace和 release(ad)可能按以下順

35、序執(zhí)行：首先 release(ad)的第一句執(zhí)行，t0：top top+1 top=h0+1；接著getspace 執(zhí)行，得：t1：g stack top g=stack h0+1；t2：top top-1 top=h0；再是 release(ad)的第二句執(zhí)行，得：t3：stack top ad stack h0 ad；其結(jié)果是調(diào)用getspace的進(jìn)程取到的是h0+1中的一個(gè)未定義值，而調(diào)用release(ad)的進(jìn)程把所釋放的空塊地址ad重復(fù)放入了h0中。怎樣保證上述執(zhí)行結(jié)果的正確性呢？ 一個(gè)較為明顯的答案是，如果把getspace和release(ad)抽象為兩個(gè)各以一個(gè)動(dòng)作完成的順序

36、執(zhí)行單位，那么執(zhí)行結(jié)果的正確性是可以保證的。把不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界部分（critical section ）或臨界區(qū)（critical region）。臨界區(qū)是由屬于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的，例如上例中就是因?yàn)檫^程 getspace 和 release(ad)共同訪問棧中的數(shù)據(jù)而引起的。臨界區(qū)不可能用增加硬件的方法來解決。因此，臨界區(qū)也可以被稱為訪問公用數(shù)據(jù)的那段程序。2. 間接制約一般來說，可以把那些不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的集合。上例中，以公用數(shù)據(jù)棧劃分的臨界區(qū)集合是getspace,release。把這些集合稱

37、為類（class）。顯然，對類給定一個(gè)唯一的標(biāo)識(shí)名，系統(tǒng)就會(huì)容易地區(qū)分它們。在程序的描述中，可用下列標(biāo)準(zhǔn)形式來描述臨界區(qū)：when類名do臨界區(qū)od設(shè)類 getspace，release 的類名為sp，則getspace和release(ad)可重新描述為：getspace: when sp do getspcestack top toptop-1 odrelease(ad): when sp do top top+1stack top ad od把這種由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對并發(fā)進(jìn)程執(zhí)行速度的間接制約，簡稱間接制約。這里

38、，“間接”二字主要是指各并發(fā)進(jìn)程的速度受公有資源制約，而不是進(jìn)程間直接制約的意思。這里，受間接制約的類中各程序段在執(zhí)行順序上是任意的。顯然，對于每一類，系統(tǒng)應(yīng)有相應(yīng)的分配和釋放相應(yīng)公有資源的管理辦法，以制約并發(fā)進(jìn)程。這就是互斥。3. 什么是互斥可以把互斥定義為：一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)稱為互斥。這里，考慮類中只有一個(gè)元素，也就是只有一個(gè)程序段的情況是很有意思的。這時(shí)程序段本身為公有資源被并發(fā)進(jìn)程共享。一般情況下，作為程序段的一個(gè)過程不允許多個(gè)進(jìn)程共同訪問它。但如

39、果該過程是純過程，則各并發(fā)進(jìn)程可以同時(shí)訪問它。純過程是指在執(zhí)行過程中不改變過程自身代碼的一類過程。通常，在計(jì)算機(jī)系統(tǒng)中，有許多過程是被多個(gè)并發(fā)進(jìn)程同時(shí)訪問共享，例如編輯程序、編譯程序等。把一個(gè)過程作成純過程可便于多個(gè)進(jìn)程共享，但由于編制純過程必須對有關(guān)變量和工作區(qū)作相應(yīng)的處理，從而其執(zhí)行效率往往會(huì)受到一定的影響。一組并發(fā)進(jìn)程互斥執(zhí)行時(shí)必須滿足如下準(zhǔn)則：(1) 不能假設(shè)各并發(fā)進(jìn)程的相對執(zhí)行速度。即各并發(fā)進(jìn)程享有平等的、獨(dú)立的競爭共有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時(shí)，其他并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)。(2) 并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止其他進(jìn)程進(jìn)入臨界區(qū)。(

40、3) 并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入。(4) 并發(fā)進(jìn)程中的某個(gè)進(jìn)程申請進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。這里，準(zhǔn)則(1)，(2)，(3)是保證各并發(fā)進(jìn)程享有平等的、獨(dú)立的競爭和使用公有資源的權(quán)利，且保證每一時(shí)刻至多只有一個(gè)進(jìn)程在臨界區(qū)。而準(zhǔn)則(4)則是并發(fā)進(jìn)程不發(fā)生死鎖（將在后面講述）的重要保證。否則，由于某個(gè)并發(fā)進(jìn)程長期占有臨界區(qū)，其他進(jìn)程則因?yàn)椴荒苓M(jìn)入臨界區(qū)而進(jìn)入互相等待狀態(tài)。在一組并發(fā)執(zhí)行進(jìn)程中，除了因?yàn)楦偁幑匈Y源而引起的間接制約帶來進(jìn)程之間互斥之外，還存在有因?yàn)椴l(fā)進(jìn)程互相共享對方的私有資源所引起的直接制約。直接制約將使得各并發(fā)進(jìn)程同步執(zhí)行

41、。下面，將討論互斥的實(shí)現(xiàn)方法。3.5.2 互斥的加鎖實(shí)現(xiàn)上節(jié)中，給出了臨界區(qū)的描述方法和并發(fā)進(jìn)程互斥執(zhí)行時(shí)所必要遵守的準(zhǔn)則。但是，并沒有給出怎樣實(shí)現(xiàn)并發(fā)進(jìn)程的互斥。人們可能認(rèn)為只需把臨界區(qū)中的各個(gè)過程按不同的時(shí)間排列調(diào)用就行了。但事實(shí)上這是不可能的。因?yàn)檫@要求該組并發(fā)進(jìn)程中的每個(gè)進(jìn)程事先知道其他并發(fā)進(jìn)程與系統(tǒng)的動(dòng)作，由用戶程序執(zhí)行開始的隨機(jī)性可知，這是不可能的。一種可能的辦法是對臨界區(qū)加鎖以實(shí)現(xiàn)互斥。當(dāng)某個(gè)進(jìn)程進(jìn)入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時(shí)為止。并發(fā)進(jìn)程在申請進(jìn)入臨界區(qū)時(shí)，首先測試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進(jìn)程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)。

42、設(shè)臨界區(qū)的類名為。為了保證每一次臨界區(qū)中只能有一個(gè)程序段被執(zhí)行，又設(shè)鎖定位 key 。key表示該鎖定位屬于類名為的臨界區(qū)。加鎖后的臨界區(qū)程序描述如下：lock(key )臨 界 區(qū)unlock(key )設(shè)key =1時(shí)表示類名為的臨界區(qū)可用，key =0時(shí)表示類名為的臨界區(qū)不可用。則，unlock(key )只用一條語句即可實(shí)現(xiàn)。即：key 1不過，由于lock(key )必須滿足key =0時(shí)，不允許任何進(jìn)程進(jìn)入臨界區(qū)，而key =1時(shí)僅允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)的準(zhǔn)則，因而實(shí)現(xiàn)起來較為困難。一種簡便的實(shí)現(xiàn)方法是：lock (x)=begin local vrepeatvxuntilv=1x

43、0end這種實(shí)現(xiàn)方法是不能保證并發(fā)進(jìn)程互斥執(zhí)行所要求的準(zhǔn)則(3)的。因?yàn)楫?dāng)同時(shí)有幾個(gè)進(jìn)程調(diào)用lock(key )時(shí)，在x0語句執(zhí)行之前，可能已有兩個(gè)以上的多個(gè)進(jìn)程由于key =1而進(jìn)入臨界區(qū)。為解決這個(gè)問題有些機(jī)器在硬件中設(shè)置了“測試與設(shè)置指令，保證第一步和第二步執(zhí)行不可分離。注意：在系統(tǒng)實(shí)現(xiàn)時(shí)鎖定位key 總是設(shè)置在公有資源所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的。3.5.3 信號(hào)量和，原語1. 信號(hào)量（semaphore）盡管用加鎖的方法可以實(shí)現(xiàn)進(jìn)程之間的互斥，但這種方法仍然存在一些影響系統(tǒng)可靠性和執(zhí)行效率的問題。例如，循環(huán)測試鎖定位將損耗較多的 CPU計(jì)算時(shí)間。如果一組并發(fā)進(jìn)程的進(jìn)程數(shù)較多，且由于每個(gè)進(jìn)程在

44、申請進(jìn)入臨界區(qū)時(shí)都得對鎖定位進(jìn)行測試，這種開銷是很大的。另外，使用加鎖法實(shí)現(xiàn)進(jìn)程間互斥時(shí)，還將導(dǎo)致在某些情況下出現(xiàn)不公平現(xiàn)象。試考慮以下進(jìn)程PA和PB反復(fù)使用臨界區(qū)的情況：PAA：lock(key)unlock(key)Goto APBB：lock(key )unlock(key )Goto B設(shè)進(jìn)程A已通過lock(key )過程而進(jìn)入臨界區(qū)。顯然，在進(jìn)程PA執(zhí)行unlock(key )過程之前，key =0且進(jìn)程PB沒有進(jìn)入臨界區(qū)的機(jī)會(huì)。然而，當(dāng)進(jìn)程PA執(zhí)行完unlock(key )過程之后，由于緊接著是一轉(zhuǎn)向語句，進(jìn)程PA將又立即去執(zhí)行l(wèi)ock(key )過程。此時(shí)，由于unlock(k

45、ey)過程已將key的值置為1，也就是開鎖狀態(tài)，從而進(jìn)程PA又可進(jìn)入臨界區(qū)。只有在進(jìn)程PA執(zhí)行完unlock(key)過程之后、執(zhí)行Goto A語句之前的瞬間發(fā)生進(jìn)程調(diào)度，使進(jìn)程PA把處理機(jī)轉(zhuǎn)讓給進(jìn)程PB，進(jìn)程PB才有可能得到執(zhí)行。然而遺憾的是，這種可能性是非常小的。因此，進(jìn)程PB將處于永久饑餓狀態(tài)（starvation）。解決上述問題首先必須找到產(chǎn)生問題的原因。顯然，在用加鎖法解決進(jìn)程互斥的問題時(shí)，一個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠進(jìn)程自己調(diào)用lock過程去測試相應(yīng)的鎖定位。每個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠自己的測試判斷。這樣沒有獲得執(zhí)行機(jī)會(huì)的進(jìn)程當(dāng)然無法判斷，從而出現(xiàn)不公平現(xiàn)象。而獲得了測試機(jī)會(huì)的進(jìn)

46、程又因需要測試而損失一定的CPU 時(shí)間。這正如某個(gè)學(xué)生想使用某個(gè)人人都可借用、且不規(guī)定使用時(shí)間的教室時(shí)一樣，他必須首先申請獲得使用該教室的權(quán)利，然后再到教室看看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復(fù)將持續(xù)到他進(jìn)門后為止。從這個(gè)例子中，可以得到解決加鎖法所帶來的問題的方法。一種最直觀的辦法是，設(shè)置一個(gè)教室管理員。從而，如果有學(xué)生申請使用教室而未能如愿時(shí)，教室管理員記下他的名字，并等到教室門一打開則通知該學(xué)生進(jìn)入。這樣，既減少了學(xué)生多次來去教室檢查門是否被打開的時(shí)間，又減少了因?yàn)閷W(xué)生自發(fā)地檢查造成的不公平現(xiàn)象。在操作系統(tǒng)中，這個(gè)管理員就是信

47、號(hào)量。信號(hào)量管理相應(yīng)臨界區(qū)的公有資源，它代表可用資源實(shí)體。信號(hào)量的概念和下面所述的、原語是荷蘭科學(xué)家E.W.Dijkstra提出來的。信號(hào)是鐵路交通管理中的一種常用設(shè)備，交通管理人員利用信號(hào)顏色的變化來實(shí)現(xiàn)交通管理。在操作系統(tǒng)中，信號(hào)量sem是一整數(shù)。在sem大于等于零時(shí)代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，但sem小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。顯然，用于互斥的信號(hào)量sem的初值應(yīng)該大于零，而建立一個(gè)信號(hào)量必須經(jīng)過說明所建信號(hào)量所代表的意義，和賦初值以及建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以便指向那些等待使用該臨界區(qū)的進(jìn)程。2. ，原語信號(hào)量的數(shù)值僅能由，原語操作改變(和分別是荷蘭語 Passeren

48、和Verhoog 的頭一個(gè)字母，相當(dāng)于英文的pass和increment的意思)。采用，原語，可以把類名為的臨界區(qū)描述為When do (sem)臨界區(qū)(sem)od。這里，sem是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號(hào)量。一次原語操作使得信號(hào)量sem減1，而一次原語操作將使得信號(hào)量sem加1。必須強(qiáng)調(diào)的一點(diǎn)是，當(dāng)某個(gè)進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時(shí)，其他進(jìn)程如果執(zhí)行了原語操作，則該進(jìn)程并不像調(diào)用lock時(shí)那樣因進(jìn)不了臨界區(qū)而返回到lock的起點(diǎn)，等以后重新執(zhí)行測試，而是在等待隊(duì)列中等待有其他進(jìn)程做原語操作釋放資源后，進(jìn)入臨界區(qū)，這時(shí)，原語的執(zhí)行才算真正結(jié)束。另外，當(dāng)有好幾個(gè)進(jìn)程執(zhí)行原語未通過而進(jìn)入等待狀

49、態(tài)之后，如有某進(jìn)程作了原語操作，則等待進(jìn)程中的一個(gè)可以進(jìn)入臨界區(qū)，但其他進(jìn)程必須等待。原語操作的主要?jiǎng)幼魇牵?1) sem減 1；(2) 若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；(3) 若sem減1后小于零，則該進(jìn)程被阻塞后與該信號(hào)相對應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。原語操作的功能框圖如圖3.11。圖3.11 原語操作功能圖 3.12原語操作功能原語的操作主要?jiǎng)幼魇牵?1) sem加1；(2) 若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3) 若相加結(jié)果小于或等于零，則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。原語操作的功能框圖如圖3.12。有了加鎖法的基礎(chǔ)，大家應(yīng)該明

50、白為什么，過程要以原語實(shí)現(xiàn)的原因。否則，如果多個(gè)進(jìn)程同時(shí)調(diào)用操作或操作的話，則有可能在操作剛把sem-1而未把對應(yīng)進(jìn)程送入等待隊(duì)列時(shí)，操作開始執(zhí)行。從而，操作將無法發(fā)現(xiàn)等待進(jìn)程而返回。因此，操作都必須以原語實(shí)現(xiàn)，且在，原語執(zhí)行期間不允許中斷發(fā)生。關(guān)于，原語的實(shí)現(xiàn)，有許多方法。這里介紹一種使用加鎖法的軟件實(shí)現(xiàn)方法，實(shí)現(xiàn)過程描述如下：（sem）：begin封鎖中斷；lock(lockbit)valsem=valsem-1if valsem0)與一群生產(chǎn)者進(jìn)程1，2，m和一群消費(fèi)者進(jìn)程1，2，k聯(lián)系起來（如圖所示）。設(shè)生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用的過程deposit(d

51、ata)和各消費(fèi)者使用的過程remove(data)可描述如下：首先，可以看到，上述生產(chǎn)者-消費(fèi)者問題是一個(gè)同步問題。即生產(chǎn)者和消費(fèi)者之間滿足如下條件：(1) 消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的；(2) 生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的。另外，由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程之間必須互斥執(zhí)行。生產(chǎn)者-消費(fèi)者問題圖第一種實(shí)現(xiàn)：設(shè)a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。生產(chǎn)者進(jìn)程：P(a)；生產(chǎn)產(chǎn)品；放入空的格；V(b);消費(fèi)者進(jìn)程：P(b)；從滿格取出產(chǎn)品；消費(fèi)產(chǎn)品；V(a);鏈表問題搜索步驟：repeatIf 找到 the

52、n 返回指針 else 指針下移一個(gè)Until 指針=null如果多個(gè)進(jìn)程并發(fā)執(zhí)行會(huì)破壞封閉性和可再現(xiàn)性。NULL多個(gè)進(jìn)程執(zhí)行到此第二種實(shí)現(xiàn)：設(shè)a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。M=1；表示互斥空格區(qū)；生產(chǎn)者進(jìn)程：P(a)；生產(chǎn)產(chǎn)品；P(m)；放入空的格；V(m)；V(b);消費(fèi)者進(jìn)程：P(b)；P(m)；從滿格取出產(chǎn)品；V(m)；消費(fèi)產(chǎn)品；V(a);第三種實(shí)現(xiàn)：提高并發(fā)程度設(shè)a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。M=1；表示互斥空格區(qū)；生產(chǎn)者進(jìn)程：生產(chǎn)產(chǎn)品；P(a)；P(m)；放入空的格；V(m)；V(b);消費(fèi)者進(jìn)程：P(b)；P(m)；從滿格取出產(chǎn)品；V(m)；V

53、(a);消費(fèi)產(chǎn)品；由以上分析，設(shè)公用信號(hào)量mutex保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥，設(shè)信號(hào)量avail為生產(chǎn)者進(jìn)程的私用信號(hào)量，信號(hào)量full為消費(fèi)者進(jìn)程的私用信號(hào)量。信號(hào)量avail表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號(hào)量full表示有界緩沖區(qū)中非空單元數(shù)，初值為0。信號(hào)量mutex表示可用有界緩沖區(qū)的個(gè)數(shù)，初值為 1。從而有：deposit(data):begin（avail）（mutex）送數(shù)據(jù)入緩沖區(qū)某單元（full）（mutex）endremove(data):begin（full）（mutex）取緩沖區(qū)中某單元數(shù)據(jù)（avail）（mutex）end在上例中，由于一個(gè)過程中

54、包含有幾個(gè)公用、私用信號(hào)量，因此，、原語的操作次序要非常小心。一般說來，由于原語是釋放資源的，所以可以以任意次序出現(xiàn)。但原語則不然，如果次序混亂，將會(huì)造成進(jìn)程之間的死鎖。關(guān)于死鎖，將在3.8 中介紹。3.7 進(jìn) 程 通 信本節(jié)介紹進(jìn)程間互相傳遞信息的方法和原理。通信（communication）意味著在進(jìn)程間傳送數(shù)據(jù)。操作系統(tǒng)可以被看作是各種進(jìn)程組成的。這些進(jìn)程都具有各自的獨(dú)立功能，且大多數(shù)被外部需要而啟動(dòng)執(zhí)行。一般來說，進(jìn)程間的通信根據(jù)通信內(nèi)容可以劃分為二種：即控制信息的傳送與大批量數(shù)據(jù)傳送。有時(shí)，也把進(jìn)程間控制信息的交換稱為低級(jí)通信，而把進(jìn)程間大批量數(shù)據(jù)的交換稱為高級(jí)通信。上面幾節(jié)中所介紹

55、的進(jìn)程間同步或互斥，也是使用鎖或信號(hào)量進(jìn)行通信來實(shí)現(xiàn)的。低級(jí)通信一般只傳送一個(gè)或幾個(gè)字節(jié)的信息，以達(dá)到控制進(jìn)程執(zhí)行速度的作用。高級(jí)通信要傳送大量數(shù)據(jù)。高級(jí)通信的目的不是為了控制進(jìn)程的執(zhí)行速度，而是為了交換信息。3.7.1 進(jìn)程的通信方式在單機(jī)系統(tǒng)中，進(jìn)程間通信可分為4種形式：(1) 主從式；(2) 會(huì)話式；(3) 消息或郵箱機(jī)制；(4) 共享存儲(chǔ)區(qū)方式。主從式通信系統(tǒng)的主要特點(diǎn)是： 主進(jìn)程可自由地使用從進(jìn)程的資源或數(shù)據(jù)； 從進(jìn)程的動(dòng)作受主進(jìn)程的控制； 主進(jìn)程和從進(jìn)程的關(guān)系是固定的。主從式通信系統(tǒng)的典型例子是終端控制進(jìn)程和終端進(jìn)程。會(huì)話方式中，通信進(jìn)程雙方可分別稱為使用進(jìn)程和服務(wù)進(jìn)程。其中，使用

56、進(jìn)程調(diào)用服務(wù)進(jìn)程提供的服務(wù)。它們具有如下特點(diǎn)： 使用進(jìn)程在使用服務(wù)進(jìn)程所提供的服務(wù)之前，必須得到服務(wù)進(jìn)程的許可； 服務(wù)進(jìn)程根據(jù)使用進(jìn)程的要求提供服務(wù)，但對所提供服務(wù)的控制由服務(wù)進(jìn)程自身完成。 使用進(jìn)程和服務(wù)進(jìn)程在通信時(shí)有固定連接關(guān)系。用戶進(jìn)程與磁盤管理進(jìn)程之間的通信是會(huì)話系統(tǒng)的一個(gè)例子。各用戶進(jìn)程向磁盤管理進(jìn)程提出使用要求并得到許可之后，才可以使用相應(yīng)的存儲(chǔ)區(qū)。而且，由磁盤管理進(jìn)程自身完成對磁盤存儲(chǔ)區(qū)的管理和控制。另外，用戶進(jìn)程與磁盤管理進(jìn)程之間，只有在用戶進(jìn)程要求使用磁盤存儲(chǔ)區(qū)時(shí)才有通信關(guān)系。消息或郵箱機(jī)制則無論接收進(jìn)程是否已準(zhǔn)備好接收消息，發(fā)送進(jìn)程都將把所要發(fā)送的消息送入緩沖區(qū)或郵箱。消息

57、的一般形式為個(gè)部分組成。即：發(fā)送進(jìn)程名、接收進(jìn)程名、數(shù)據(jù)和有關(guān)數(shù)據(jù)的操作。消息或郵箱機(jī)制的特點(diǎn)是： 只要存在空緩沖區(qū)或郵箱，發(fā)送進(jìn)程就可以發(fā)送消息。 與會(huì)話系統(tǒng)不同，發(fā)送進(jìn)程和接收進(jìn)程之間無直接連接關(guān)系，接收進(jìn)程可能在收到某個(gè)發(fā)送進(jìn)程發(fā)來的消息之后，又轉(zhuǎn)去接收另一個(gè)發(fā)送進(jìn)程發(fā)來的消息。消息的組成圖緩沖區(qū)或郵箱通信結(jié)構(gòu)圖 發(fā)送進(jìn)程和接收進(jìn)程之間存在緩沖區(qū)或郵箱用來存放被傳送消息。與前面三種方式不同，共享存儲(chǔ)區(qū)方式不要求數(shù)據(jù)移動(dòng)。兩個(gè)需要互相交換信息的進(jìn)程通過對同一共享數(shù)據(jù)區(qū)（shared memory）的操作來達(dá)到互相通信的目的。這個(gè)共享數(shù)據(jù)區(qū)是每個(gè)互相通信進(jìn)程的一個(gè)組成部分。以上幾種通信方式都

58、可用于大量數(shù)據(jù)傳送，而且，由于其通信方式不同，需要使用不同的控制方式來達(dá)到通信進(jìn)程之間同步或互斥的目的。下面，首先介紹進(jìn)程通信中較為常用的消息與郵箱機(jī)制，然后再介紹幾個(gè)實(shí)際例子。3.7.2 消息緩沖機(jī)制發(fā)送進(jìn)程和接收進(jìn)程采用消息緩沖機(jī)制進(jìn)行數(shù)據(jù)傳送時(shí)，發(fā)送進(jìn)程在發(fā)送消息前，先在自己的內(nèi)存空間設(shè)置一個(gè)發(fā)送區(qū)，把欲發(fā)送的消息填入其中，然后再用發(fā)送過程將其發(fā)送出去。接收進(jìn)程則在接收消息之前，在自己的內(nèi)存空間內(nèi)設(shè)置相應(yīng)的接收區(qū)，然后用接收過程接收消息。由于消息緩沖機(jī)制中所使用的緩沖區(qū)為公用緩沖區(qū)，使用消息緩沖機(jī)制傳送數(shù)據(jù)時(shí)，兩通信進(jìn)程必須滿足如下條件： 在發(fā)送進(jìn)程把消息寫入緩沖區(qū)和把緩沖區(qū)掛入消息隊(duì)列

59、時(shí)，應(yīng)禁止其他進(jìn)程對該緩沖區(qū)消息隊(duì)列的訪問。否則，將引起消息隊(duì)列的混亂。同理，當(dāng)接收進(jìn)程正從消息隊(duì)列中取消息緩沖時(shí)，也應(yīng)禁止其他進(jìn)程對該隊(duì)列的訪問。 當(dāng)緩沖區(qū)中無消息存在時(shí)，接收進(jìn)程不能接收到任何消息。至于發(fā)送進(jìn)程是否可以發(fā)送消息，則由發(fā)送進(jìn)程是否申請到緩沖區(qū)決定。設(shè)公用信號(hào)量mutex 為控制對緩沖區(qū)訪問的互斥信號(hào)量，其初值為1 。設(shè)SM為接收進(jìn)程的私用信號(hào)量，表示等待接收的消息個(gè)數(shù)，其初值為0 。設(shè)發(fā)送進(jìn)程調(diào)用過程send(m)將消息m 送往緩沖區(qū)，接收進(jìn)程調(diào)用過程Receive(m)將消息m從緩沖區(qū)讀往自己的數(shù)據(jù)區(qū)，則Send(m)和Receive(n)可分別描述為：Send(m):be

60、gin向系統(tǒng)申請一個(gè)消息緩沖區(qū)（mutex）將發(fā)送區(qū)消息m送入新申請的消息緩沖區(qū)把消息緩沖區(qū)掛入接收進(jìn)程的消息隊(duì)列（mutex）（SM）endReceive(n):begin（SM）（mutex）摘下消息隊(duì)列中的消息n 將消息n從緩沖區(qū)復(fù)制到接收區(qū)釋放緩沖區(qū)（mutex）end一般來說，盡管系統(tǒng)中可利用的緩沖區(qū)總數(shù)是已知的，但由于消息隊(duì)列是按接收進(jìn)程排列，因而，在同一時(shí)間內(nèi)，系統(tǒng)中存在著多個(gè)消息隊(duì)列；且這些隊(duì)列的長度是不固定的。因此，發(fā)送進(jìn)程無法在Send過程用操作判斷信號(hào)量SM。3.7.3 郵箱通信郵箱通信就是由發(fā)送進(jìn)程申請建立一與接收進(jìn)程鏈接的郵箱。發(fā)送進(jìn)程把消息送往郵箱，接收進(jìn)程從郵箱中