第3章進程管理3.1進程的概念3.2進程的描畫3.3進程形狀及其轉換3.4進程控制3.5進程互斥3.6進程同步3.7進程通訊3.8死鎖問題3.9線程3.1進程的概念現(xiàn)代操作系統(tǒng)的重要特點：程序的并發(fā)執(zhí)行、資源共享、用戶隨機地運用。1.程序的順序執(zhí)行程序的順序執(zhí)行：程序獨占處置機直至最終終了的過程。程序的順序執(zhí)行具有如下特點：(1)順序性程序順序執(zhí)行時，其執(zhí)行過程可看作一系列嚴厲按程序規(guī)定的形狀轉移過程。(2)封鎖性程序執(zhí)行得到的最終結果由給定的初始條件決議，不受外界要素的影響。(3)可再現(xiàn)性只需輸入的初始條件一樣，那么無論何時反復執(zhí)行該程序都會得到一樣的結果。2.多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化多道程序執(zhí)行的系統(tǒng)環(huán)境具有下述三個特點：(1)獨立性每道程序都是邏輯上獨立的，它們之間不存在邏輯上的制約關系。(2)隨機性在多道程序環(huán)境下，特別是在多用戶環(huán)境下，程序和數(shù)據(jù)的輸入與執(zhí)行開場時間都是隨機的。(3)資源共享資源共享將導致對進程執(zhí)行速度的制約。3.程序的并發(fā)執(zhí)行(1)什么是程序的并發(fā)執(zhí)行并發(fā)執(zhí)行：即一道程序的執(zhí)行尚未終了；另一道程序的執(zhí)行曾經(jīng)開場的執(zhí)行方式。是為了加強計算機系統(tǒng)的處置才干和提高資源利用率所采取的一種同時操作技術。程序的并發(fā)執(zhí)行可進一步分為兩種：第一種是多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行。微觀上仍是順序執(zhí)行，雖然多道程序的并發(fā)執(zhí)行在宏觀上是同時進展的。第二種并發(fā)執(zhí)行是在某道程序的幾個程序段中〔例如幾個程序〕，包含著一部分可以同時執(zhí)行或順序顛倒執(zhí)行的代碼。例如語句： read(a)； read(b)；它們既可以同時執(zhí)行，也可顛倒次序執(zhí)行。對于這樣的語句，同時執(zhí)行不會改動順序程序所具有的邏輯性質。因此，可以采用并發(fā)執(zhí)行來充分利用系統(tǒng)資源以提高計算機的處置才干。程序的并發(fā)執(zhí)行可總結為：一組在邏輯上相互獨立的程序或程序段在執(zhí)行過程中，其執(zhí)行時間在客觀上相互重疊，即一個程序段的執(zhí)行尚未終了，另一個程序段的執(zhí)行曾經(jīng)開場的這種執(zhí)行方式。程序的并發(fā)執(zhí)行不同于程序的并行執(zhí)行。程序的并行執(zhí)行是指一組程序按獨立的、異步的速度執(zhí)行。并行執(zhí)行不等于時間上的重疊。可以將并發(fā)執(zhí)行過程描畫為： S0 Cobegin P1；P2；...Pn Coend Sn這里，S0，Sn分別表示并發(fā)程序段P1，P2，…，Pn開場執(zhí)行前和并發(fā)執(zhí)行終了后的語句。P1，2，…，Pn也可以由同一程序段中的不同語句組成。1966年Bernstein提出了兩相鄰語句S1，S2可以并發(fā)執(zhí)行的條件：將程序中任一語句Si劃分為兩個變量的集合R(Si)和W(Si)。其中R(Si)={a1a2…am}，aj(j=1，…，m)是語句Si在執(zhí)行期間必需對其進展讀操作的變量；Until Buf=空Buf(x)置空標志線程只由相關堆棧〔系統(tǒng)?；蛴脩魲！炒娣牌骱途€程控制表TCB組成。1)設sem為互斥信號量，其取值范圍為(1,0,-1)。并在第一次借款時，能闡明他的最大借款額。普通地，把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。并在第一次借款時，能闡明他的最大借款額。(4)不同的進程可以包含同一程序，只需該程序所對應的數(shù)據(jù)集不同。6進程同步(3)祖先進程要求吊銷某個子進程。也就是說，在不思索資源共享的情況下，各進程的執(zhí)行是獨立的，執(zhí)行速度是異步的。從處置機的活動角度來看，又如何識別描畫程序執(zhí)行活動的進程呢？顯然，系統(tǒng)中需求有描畫進程存在和可以反映其變化的物理實體，即進程的靜態(tài)描畫。localr; W(Si)={b1b2…bn}，bj(j=1，…，n)是語句Si在執(zhí)行期間必需對其進展寫操作的變量；假設對于兩相鄰語句S1和S2，有①R(S1)∩W(S2)={∮}，②W(S1)∩R(S2)={∮}，③W(S1)∩W(S2)={∮}同時成立，那么語句S1和S2是可以并發(fā)執(zhí)行的。多道執(zhí)行與單道執(zhí)行有何優(yōu)點:例：有三個程序A、B、C；每個程序都由輸入、計算、輸出三部分代碼組成；記為Ai、Ac、Ao，Bi、Bc、Bo，Ci、Cc、Co；假設各部分代碼在相應的設備上執(zhí)行的時間都為t；在單道環(huán)境下：總的運轉時間9t，輸入設備占用3t，輸出設備占用3t。

CPU利用率＝3t／9t＝3／9＝33.3％

輸入設備利用率＝3t／9t＝3／9＝33.3％

輸出設備利用率＝3t／9t＝3／9＝33.3％AiAoAcBiBoBcCiCcCoAiAoAcBiBoBcCiCcCott時間ttttttt多道環(huán)境下：總的運轉時間5t，輸入設備占用3t，輸出設備占用3t。

CPU利用率＝3t／5t＝3／5＝60％

輸入設備利用率＝3t／5t＝3／5＝60％

輸出設備利用率＝3t／5t＝3／5＝60％CPU時間片進程A進程B進程CtAiAcAoBiBcBoCiCcCotttt輸入設備輸出設備CPU(2)程序的并發(fā)執(zhí)行所帶來的影響程序的并發(fā)執(zhí)行充分地利用了系統(tǒng)資源，從而提高了系統(tǒng)的處置才干，這是并發(fā)執(zhí)行好的一方面。但是，正如前面所提到的那樣，由于系統(tǒng)資源有限，程序的并發(fā)執(zhí)行必然導致資源共享和資源競爭，從而改動程序的執(zhí)行速度。假設并發(fā)執(zhí)行的各程序段中語句或指令滿足上述Bernstein的三個條件，那么以為并發(fā)執(zhí)行不會對執(zhí)行結果的封鎖性和可再現(xiàn)性產(chǎn)生影響。但在普通情況下，系統(tǒng)要斷定并發(fā)執(zhí)行的各程序段能否滿足Bernstein條件是相當困難的。從而，假設并發(fā)執(zhí)行的程序段不按照特定的規(guī)那么和方法進展資源共享和競爭，那么其執(zhí)行結果將不可防止地失去封鎖性和可再現(xiàn)性。下面的例子闡明了這一點。堆棧的取數(shù)和存數(shù)過程圖例：設有堆棧S，棧指針top，棧中存放內存中相應數(shù)據(jù)塊地址〔如圖3.1(a)〕設有兩個程序段getaddr(top)和reladdr(blk)，其中getaddr(top)從給定的top所指棧中取出相應的內存數(shù)據(jù)塊地址，而reladdr(blk)那么將內存數(shù)據(jù)塊地址blk放入堆棧S中。getaddr(top)和reladdr(blk)可分別描畫為： proceduregetaddr(top) begin localr r←(top) top←top-1 return(r) end procedurereladdr(blk)例：利用堆棧管理一塊內存區(qū)中各數(shù)據(jù)塊的運用情況。用getaddr(top)從棧頂取出相應的內存塊的地址。用reladdr(blk)將數(shù)據(jù)塊的地址〔以bkl為地址〕放入堆棧中。procgetaddr(top)Beginlocalr;1.1rs[top];1.2toptop-1;1.3return(r);end;Procreladdr(blk)Begin2.1toptop+1;2.2s[top]blk;End;分析getaddr(top)與reladdr(blk)的并發(fā)執(zhí)行012345t……abtop2.1toptop+11.1rs[top]1.2toptop-11.3return(r)2.2s[top]blktoptopblk上例中的程序段并發(fā)執(zhí)行出現(xiàn)錯誤結果是由于兩程序段共享資源堆棧S，從而使得執(zhí)行結果受執(zhí)行速度影響。普通情況下，并發(fā)執(zhí)行的各程序段假設共享軟、硬件資源，都會呵斥其執(zhí)行結果受執(zhí)行速度影響的局面。顯然，這是程序設計人員不希望看到的。為了使得在并發(fā)執(zhí)行時不出現(xiàn)錯誤結果，必需采取某些措施來制約、控制各并發(fā)程序段的執(zhí)行速度。這在操作系統(tǒng)程序設計中尤其重要，由于操作系統(tǒng)用戶隨機性與各道程序邏輯獨立的特點將使得每個用戶程序所運用的軟、硬件資源都遭到其他并發(fā)程序的共享和競爭，從而得到非預料的或不正確的結果。為了控制和協(xié)調各程序段執(zhí)行過程中的軟、硬件資源的共享和競爭，顯然，必需應該有一個描畫各程序段執(zhí)行過程和共享資源的根本單位。從上述討論可以看出，由于程序的順序性、靜態(tài)性以及孤立性，用程序段作為描畫其執(zhí)行過程和共享資源的根本單位既添加操作系統(tǒng)設計和實現(xiàn)的復雜性，也無法反映操作系統(tǒng)所應該具有的程序段執(zhí)行的并發(fā)性、用戶隨機性，以及資源共享等特征。也就是說，用程序作為描畫其執(zhí)行過程以及共享資源的根本單位是不適宜的。需求有一個能描畫程序的執(zhí)行過程且能用來共享資源的根本單位。這個根本單位被稱為進程〔或義務〕。3.1.2進程的定義進程的概念是60年代初期，首先在MIT的Multics系統(tǒng)和IBM的TSS/360系統(tǒng)中援用的。進程的定義：一個具有獨立功能的程序對某個數(shù)據(jù)集在處置機上的執(zhí)行過程和分配資源的根本單位。進程和程序是兩個既有聯(lián)絡又有區(qū)別的概念，它們的區(qū)別和關系可簡述如下：(1)進程是一個動態(tài)概念，而程序那么是一個靜態(tài)概念。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進程那么強調執(zhí)行過程，它動態(tài)地被創(chuàng)建，并被調度執(zhí)行后消亡。(2)進程具有并行特征，而程序沒有。由進程的定義可知，進程具有并行特征的兩個方面，即獨立性和異步性。也就是說，在不思索資源共享的情況下，各進程的執(zhí)行是獨立的，執(zhí)行速度是異步的。顯然，由于程序不反映執(zhí)行過程，所以不具有并行特征。(3)進程是競爭計算機系統(tǒng)資源的根本單位，從而其并行性遭到系統(tǒng)本人的制約。這里，制約就是對進程獨立性和異步性的限制。(4)不同的進程可以包含同一程序，只需該程序所對應的數(shù)據(jù)集不同。3.1.3作業(yè)和進程的關系作業(yè)是用戶需求計算機完成某項義務時要求計算機所作任務的集合。進程是已提交終了程序的執(zhí)行過程的描畫，是資源分配的根本單位。區(qū)別與關系：(1)作業(yè)是用戶向計算機提交義務的義務虛體。在用戶向計算機提交作業(yè)之后，系統(tǒng)將它放入外存中的作業(yè)等待隊列中等待執(zhí)行。而進程那么是完成用戶義務的執(zhí)行實體，是向系統(tǒng)懇求分配資源的根本單位。任一進程，只需它被創(chuàng)建，總有相應的部分存在于內存中。(2)一個作業(yè)可由多個進程組成。且必需至少由一個進程組成，但反過來不成立。(3)作業(yè)的概念主要用在批處置系統(tǒng)中。而進程的概念那么用在幾乎一切的多道系統(tǒng)中。3.2進程的描畫從處置機的活動角度來看，又如何識別描畫程序執(zhí)行活動的進程呢？顯然，系統(tǒng)中需求有描畫進程存在和可以反映其變化的物理實體，即進程的靜態(tài)描畫。進程的靜態(tài)描畫由三部分組成：進程控制塊PCB，有關程序段和該程序段對其進展操作的數(shù)據(jù)構造集。進程控制塊包含了有關進程的描畫信息、控制信息以及資源信息，是進程動態(tài)特征的集中反映。系統(tǒng)根據(jù)PCB感知進程的存在和經(jīng)過PCB中所包含的各項變量的變化，掌握進程所處的形狀以到達控制進程活動的目的。由于進程的PCB是系統(tǒng)感知進程的獨一實體，因此，在幾乎一切的多道操作系統(tǒng)中，一個進程的PCB構造都是全部或部分常駐內存的。進程的程序部分描畫進程所要完成的功能。而數(shù)據(jù)構造集是程序在執(zhí)行時必不可少的任務區(qū)和操作對象。這兩部分是進程完成所需功能的物質根底。由于進程的這兩部分內容與控制進程的執(zhí)行及完成進程功能直接有關，因此，在大部分多道操作系統(tǒng)中，這兩部分內容放在外存中，直到該進程執(zhí)行時再調入內存。下面分別引見進程的PCB構造、程序與數(shù)據(jù)構造集。3.2.1進程控制塊PCBPCB包含一個進程的描畫信息、控制信息及資源信息，有些系統(tǒng)中還有進程調度等待所運用的現(xiàn)場維護區(qū)。PCB集中反映一個進程的動態(tài)特征。在創(chuàng)建一個進程時，應首先創(chuàng)建其PCB，然后才干根據(jù)PCB中信息對進程實施有效的管理和控制。當一個進程完成其功能之后，系統(tǒng)那么釋放PCB，進程也隨之消亡。根據(jù)操作系統(tǒng)的要求不同，PCB的內容會有所不同。下面所示根本內容是必需的：(1)描畫信息進程名或進程標識號、用戶名或用戶標識號、家族關系。(2)控制信息①進程當前形狀進程在活動期間可分為就緒態(tài)、執(zhí)行態(tài)和等待形狀。②進程優(yōu)先級進程優(yōu)先級是選取進程占有處置機的重要根據(jù)。③程序開場地址④各種計時信息⑤通訊信息(3)資源管理信息PCB中包含最多的是資源管理信息，包括有關存儲器的信息、運用輸入輸出設備的信息、有關文件系統(tǒng)的信息等。這些信息有：①占用內存大小及其管理用數(shù)據(jù)構造指針，例如后述內存管理中所用到的進程頁表指針等。②對換或覆蓋用的有關信息，如對換程序段長度，對換外存地址等。這些信息在進程懇求、釋放內存中運用。③共享程序段大小及起始地址。④輸入輸出設備的設備號，所要傳送的數(shù)據(jù)長度、緩沖區(qū)地址、緩沖區(qū)長度及所用設備的有關數(shù)據(jù)構造指針等。這些信息在進程懇求釋放設備進展數(shù)據(jù)傳輸中運用。⑤指向文件系統(tǒng)的指針及有關標識等。進程可運用這些信息對文件系統(tǒng)進展操作。(4)CPU現(xiàn)場維護構造當前進程因等待某個事件而進入等待形狀或因某種事件發(fā)生被中止在處置機上的執(zhí)行時，為了以后該進程能在被打斷處恢復執(zhí)行，需求維護當前進程的CPU現(xiàn)場〔或稱進程上下文〕。PCB中設有專門的CPU現(xiàn)場維護構造，以存儲退出執(zhí)行時的進程現(xiàn)場數(shù)據(jù)?？傊?，進程控制塊PCB是系統(tǒng)感知進程存在的獨一實體。經(jīng)過對PCB的操作，給進程分配資源、調度進程執(zhí)行、釋放進程所占有的各種資源；而完成進程所要求功能的程序段的有關地址，以及程序段在進程過程中因某種緣由被停頓執(zhí)行后的現(xiàn)場信息也都在PCB中。由于PCB中包含有較多的信息，因此，一個PCB表往往要占據(jù)較大的存儲空間〔普通占幾百到幾千個字節(jié)〕。在有的系統(tǒng)中，為了減少PCB對內存的占用量，只允許PCB中最常用的部分，如CPU現(xiàn)場維護、進程描畫信息、控制信息等常駐內存。PCB構造中的其他部分那么存放于外存之中，待該進程將要執(zhí)行時與其他數(shù)據(jù)一同裝入內存。近年來，面向對象技術已被用于操作系統(tǒng)設計。在面向對象的操作系統(tǒng)中，進程的描畫將采用其他方式。3.2.2進程上下文本節(jié)引見包括程序段和數(shù)據(jù)集在內的上下文的概念。進程上下文實踐上是進程執(zhí)行活動全過程的靜態(tài)描畫。詳細地說，進程上下文包括計算機系統(tǒng)中與執(zhí)行該進程有關的各種存放器的值、程序段在經(jīng)過編譯之后構成的機器指令代碼集〔或稱正文段〕、數(shù)據(jù)集及各種堆棧值和PCB構造(圖3.2)。這里，有關存放器和棧區(qū)的內容是重要的。例如，沒有程序計數(shù)器PC和程序形狀存放器PS，CPU將無法知道下條待執(zhí)行指令的地址和控制有關操作。從CPU是活動的觀念來靜態(tài)地看一個進程時，必需把有關存放器和棧區(qū)的內容也包括在其中。無論在何種系統(tǒng)中，進程上下文的各部分都必需按一定的規(guī)那么有機地組合起來以便于執(zhí)行。圖3.2進程上下文構造進程上下文可按一定的執(zhí)行層次組合，例如用戶級上下文、系統(tǒng)級上下文等。顯然，一個進程的執(zhí)行是在該進程的上下文中執(zhí)行，而當系統(tǒng)調度新進程占有處置機時，新老進程的上下文發(fā)生轉換。在UNIXSystemⅤ中，進程上下文由用戶級上下文、存放器上下文以及系統(tǒng)級上下文組成。用戶級上下文由進程的用戶程序段部分編譯而成的用戶正文段、用戶數(shù)據(jù)、用戶棧等組成。而存放器上下文那么由程序存放器PC、處置機形狀字存放器PS、棧指針和通用存放器的值組成。其中PC給出CPU將要執(zhí)行的下條指令的虛地址；PS給出機器與該進程相關聯(lián)時的硬件形狀，例如當前執(zhí)行方式、能否執(zhí)行特權指令等；棧指針指向下一項的當前地址，而通用存放器那么用于不同執(zhí)行方式之間的參數(shù)傳送等。進程的系統(tǒng)級上下文又分為靜態(tài)部分與動態(tài)部分。這里的動態(tài)部分不是指程序的執(zhí)行，而是指在進入和退出不同的上下文層次時，系統(tǒng)為各層上下文中相關聯(lián)的存放器值所保管和恢復的記錄。系統(tǒng)級上下文的靜態(tài)部分包括PCB構造〔UNIX系統(tǒng)中的PCB構造被分為proc構造和user構造兩部分〕、將進程虛地址空間映射到物理空間用的有關表格和中心棧。這里，中心棧主要用來裝載進程中所運用系統(tǒng)調用的調用序列。系統(tǒng)級上下文的動態(tài)部分是與存放器上下文相關聯(lián)的。進程上下文的層次概念也主要表達在動態(tài)部分中，即系統(tǒng)級上下文的動態(tài)部分可看成是一些數(shù)量變化的層次組成。其變化規(guī)那么滿足先進后出的堆棧方式，每個上下文層次在棧中各占一項。UNIXSystemⅤ的進程上下文組成如圖3.3。圖3.3UNIXSystemⅤ進程上下文組成3.2.3進程空間任一進程，都有一個本人的地址空間，把該空間稱為進程空間或虛空間。進程空間的大小只與處置機的位數(shù)有關。在UNIX以及Linux等操作系統(tǒng)中，進程空間還被劃分為用戶空間和系統(tǒng)空間兩大部分。在進程空間被劃分為兩大部分后，用戶程序在用戶空間內執(zhí)行，而操作系統(tǒng)內核程序那么在進程的系統(tǒng)空間內執(zhí)行。為防止用戶程序訪問系統(tǒng)空間，呵斥訪問出錯，系統(tǒng)經(jīng)過程序形狀存放器等設置不同的執(zhí)行方式，即用戶方式和系統(tǒng)方式來進展維護。

3.3進程形狀及其轉換3.3.1進程形狀一個進程的生命期可以劃分為一組形狀，這些形狀刻劃了整個進程。系統(tǒng)根據(jù)PCB構造中的形狀值控制進程。在進程的生命期內，一個進程至少具有三種根本形狀，它們是：執(zhí)行形狀、等待形狀和就緒形狀。處于就緒形狀的進程曾經(jīng)得到除CPU之外的其他資源，只需由調度得四處置機，便可立刻投入執(zhí)行。在有些系統(tǒng)中，為了有效地利用內存，就緒形狀又可進一步分為內存就緒形狀和外存就緒形狀。在這樣的系統(tǒng)中，只需處于內存就緒形狀的進程在得四處置機后才干立刻投入執(zhí)行。而處于外存就緒形狀的進程只需先成為內存就緒形狀后，才能夠被調度執(zhí)行。這種方式明顯地提高了內存的利用效率，但反過來也添加了系統(tǒng)開銷和系統(tǒng)復雜性。在單CPU系統(tǒng)中，任一時辰處于執(zhí)行形狀的進程只能有一個。只需處于就緒形狀的進程經(jīng)調度選中之后才可進入執(zhí)行形狀。在某些操作系統(tǒng)中，一個進程在其生命期內的執(zhí)行過程中，總要涉及到用戶程序和操作系統(tǒng)內核程序兩部分。因此，進程的執(zhí)行形狀又可進一步劃分為用戶執(zhí)行形狀和系統(tǒng)執(zhí)行形狀。劃分用戶態(tài)和系統(tǒng)態(tài)最主要的緣由是要把用戶程序和系統(tǒng)程序區(qū)分開來，以利于程序的共享和維護。顯然，這也是以添加系統(tǒng)復雜度和系統(tǒng)開銷為代價的。進程因等待某個事件發(fā)生而放棄處置機進入等待形狀。顯然，等待形狀可根據(jù)等待事件的種類而進一步劃分為不同的子形狀，例如內存等待、設備等待、文件等待和數(shù)據(jù)等待等。這樣做的益處是系統(tǒng)控制簡單，發(fā)現(xiàn)和喚醒相應的進程較為容易。但系統(tǒng)中設置過多的形狀又會呵斥系統(tǒng)參數(shù)和形狀轉換過程的添加。3.3.2進程形狀轉換進程的形狀反映進程執(zhí)行過程的變化。這些形狀隨著進程的執(zhí)行和外界條件發(fā)生變化和轉換。那么，是什么樣的條件使得進程各形狀發(fā)生轉換呢？示圖給出了三個根本形狀，即就緒形狀、執(zhí)行形狀與等待形狀之間的轉換關系。現(xiàn)實上，進程的形狀轉換是一個非常復雜的過程。從一個形狀到另一個形狀的轉換除了要運用不同的控制過程〔將在下節(jié)中講述〕，有時還要借助于硬件觸發(fā)器才干完成。例如，在UNIX系統(tǒng)中，從系統(tǒng)態(tài)到用戶態(tài)的轉換要借助硬件觸發(fā)器完成。進程形狀轉換圖3.4進程控制進程和處置機管理的一個重要義務是進程控制。所謂進程控制，就是系統(tǒng)運用一些具有特定功能的程序段來創(chuàng)建、吊銷進程以及完成進程各形狀間的轉換，從而到達多進程高效率并發(fā)執(zhí)行和協(xié)調、實現(xiàn)資源共享的目的。普通地，把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。原語可分為兩類：一類是機器指令級的，其特點是執(zhí)行期間不允許中斷。另一類是功能級的，其特點是作為原語的程序段不允許并發(fā)執(zhí)行。這兩類原語都在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個系統(tǒng)管理所需求的功能和被高層軟件所調用。顯然，系統(tǒng)在創(chuàng)建、吊銷一個進程以及要改動進程的形狀時，都要調用相應的程序段來完成這些功能。那么，這些程序段是不是原語呢？假設它們不是原語，那么由上述原語的定義可知，這些程序段是允許并發(fā)執(zhí)行的。然而，假設不加控制和管理地讓這些控制進程形狀轉換及創(chuàng)建和吊銷進程的程序段并發(fā)執(zhí)行，那么會使得其執(zhí)行結果失去封鎖性和可再現(xiàn)性，從而達不到進程控制的目的。反過來，假設對這些程序段采用下面章節(jié)中所述的控制方法使其在并發(fā)執(zhí)行過程中也能完成進程控制義務的話，將會大大添加系統(tǒng)的開銷和復雜度。因此，在操作系統(tǒng)中，通常把進程控制用程序段做成原語。用于進程控制的原語有：創(chuàng)建原語、吊銷原語、阻塞原語、喚醒原語等。3.4.1進程創(chuàng)建與吊銷1.進程創(chuàng)建(1)由系統(tǒng)程序模塊一致創(chuàng)建，例如在批處置系統(tǒng)中，由操作系統(tǒng)的作業(yè)調度程序為用戶作業(yè)創(chuàng)建相應的進程以完成用戶作業(yè)所要求的功能。(2)由父進程創(chuàng)建，例如在層次構造的系統(tǒng)中，父進程創(chuàng)建子進程以完成并行任務。由系統(tǒng)一致創(chuàng)建的進程之間的關系是平等的，它們之間普通不存在資源承繼關系。而在父進程創(chuàng)建的進程之間那么存在隸屬關系，且相互構成樹型構造的家族關系。屬于某個家族的一個進程可以承繼其父進程所擁有的資源。另外，無論是哪一種方式創(chuàng)建進程，在系統(tǒng)生成時，都必需由操作系統(tǒng)創(chuàng)建一部分承當系統(tǒng)資源分配和管理任務的系統(tǒng)進程。無論是系統(tǒng)創(chuàng)建方式還是父進程創(chuàng)建方式，都必需調用創(chuàng)建原語來實現(xiàn)。2.進程吊銷以下幾種情況導致進程被吊銷：(1)該進程已完成所要求的功能而正常終止。(2)由于某種錯誤導致非正常終止。(3)祖先進程要求吊銷某個子進程。無論哪一種情況導致進程被吊銷，進程都必需釋放它所占用的各種資源和PCB構造本身，以利于資源的有效利用。另外，當一個祖先進程吊銷某個子進程時，還需審查該子進程能否還有本人的子孫進程，假設有的話，還需吊銷其子孫進程的PCB構造和釋放它們所占有的資源。吊銷原語首先檢查PCB進程鏈或進程家族，尋覓所要吊銷的進程能否存在。假設找到了所要吊銷的進程的PCB構造，那么吊銷原語釋放該進程所占有的資源之后，把對應的PCB構造從進程鏈或進程家族中摘下并前往給PCB空隊列。假設被吊銷的進程有本人的子進程，那么吊銷原語先吊銷其子進程的PCB構造并釋放子進程所占用的資源之后，再吊銷當前進程的PCB構造和釋放其資源。3.4.2進程的阻塞與喚醒進程的創(chuàng)建原語和吊銷原語完成了進程從無到有，從存在到消亡的變化。被創(chuàng)建后的進程最初處于就緒形狀，然后經(jīng)調度程序選中后進入執(zhí)行形狀。這里主要引見實現(xiàn)進程的執(zhí)行形狀到等待形狀，又由等待形狀到就緒形狀轉換的兩種原語，即阻塞原語與喚醒原語。阻塞原語在一個進程等待某一事件發(fā)生，但發(fā)生條件尚不具備時，被該進程本人調用來阻塞本人。阻塞原語在阻塞一個進程時，由于該進程正處于執(zhí)行形狀，故應先中斷處置機和保管該進程的CPU現(xiàn)場。然后將被阻塞進程置“阻塞〞形狀后插入等待隊列中，再轉進程調度程序選擇新的就緒進程投入運轉。阻塞原語的實現(xiàn)過程如圖。這里，轉進程調度程序是很重要的，否那么，處置機將會出現(xiàn)空轉而浪費資源。阻塞原語圖當?shù)却犃兄械倪M程所等待的事件發(fā)生時，等待該事件的一切進程都將被喚醒。喚醒一個進程有兩種方法：一種是由系統(tǒng)進程喚醒。另一種是由事件發(fā)生進程喚醒。當由系統(tǒng)進程喚醒等待進程時，系統(tǒng)進程一致控制事件的發(fā)生并將“事件發(fā)生〞這一音訊通知等待進程。從而使得該進程因等待事件已發(fā)生而進入就緒隊列。由事件發(fā)生進程喚醒時，事件發(fā)生進程和被喚醒進程之間是協(xié)作關系。因此，喚醒原語既可被系統(tǒng)進程調用，也可被事件發(fā)生進程調用。稱調用喚醒原語的進程為喚醒進程。喚醒原語首先將被喚醒進程從相應的等待隊列中摘下，將被喚醒進程置為就緒形狀之后，送入就緒隊列。在把被喚醒進程送入就緒隊列之后，喚醒原語既可以前往原調用程序，也可以轉向進程調度，以便讓調度程序有時機選擇一個適宜的進程執(zhí)行。如圖：喚醒原語圖3.5進程互斥3.5.1資源共享所引起的制約進程的并發(fā)執(zhí)行不僅僅是用戶程序的執(zhí)行開場時間的隨機性和提高資源利用率的結果，也是資源有限性導致資源的競爭與共享對進程的執(zhí)行過程進展制約所呵斥的。1.臨界區(qū)在描畫一個程序或算法時，總是以為存在一個偽處置機，可以按程序或算法所規(guī)定的步驟來執(zhí)行該程序或算法的。但是，現(xiàn)實上，在實踐的系統(tǒng)中那么往往不是這樣。普通說來，即使在程序中所描畫的一條語句，也是由多條執(zhí)行指令構成的。例如，各種程序中經(jīng)常出現(xiàn)的賦值語句： X=X+1；在用匯編言語書寫時，就變成： LOADA，X ADDIA，1 STOREA，X 等三條語句，這里A代表累加器。根據(jù)系統(tǒng)的設計和要求，在這三條語句的執(zhí)行期間，也有能夠發(fā)生中斷或調度，從而使得與當前進程無關的程序得以執(zhí)行。為了保證程序執(zhí)行最終結果的正確性，必需對并發(fā)執(zhí)行的各進程進展制約，以控制它們的執(zhí)行速度和對資源的競爭。在進程的概念一節(jié)中曾經(jīng)引見了進程中兩相鄰語句可并發(fā)執(zhí)行的三個條件。能否有一種更為簡單的方法來檢查出需求對程序的哪些部分進展制約才干保證其執(zhí)行結果的正確性呢？這里來看下面的例子。設有兩個計算進程ＰA，ＰB共享內存ＭS。其中ＭS分為三個領域，即系統(tǒng)區(qū)、進程任務區(qū)和數(shù)據(jù)區(qū)。這里數(shù)據(jù)區(qū)被劃分大小相等的塊，每個塊中既能夠放有數(shù)據(jù)，也有能夠未放有數(shù)據(jù)。系統(tǒng)區(qū)主要是堆棧Ｓ，其中存放那些空數(shù)據(jù)塊的地址。多進程共享內存棧區(qū)例如圖當進程ＰA或ＰB要求空數(shù)據(jù)塊時，從堆棧最頂部〔top指針所指的位置〕取出所需數(shù)據(jù)塊。當進程ＰA或ＰB釋放數(shù)據(jù)塊時，那么把所釋放數(shù)據(jù)塊的地址放入堆棧頂部。令getspace為取空數(shù)據(jù)塊過程，release(ad)為釋放數(shù)據(jù)塊過程。這里，ad為待釋放數(shù)據(jù)塊的地址。假設堆棧Ｓ非空的話，進程ＰA或ＰB是可以用恣意的順序釋放和獲取數(shù)據(jù)塊的。執(zhí)行getspace就是獲取一個空數(shù)據(jù)塊，而執(zhí)行release(ad)就是釋放一個地址為ad的數(shù)據(jù)塊。然而，由下面的描畫可以看到，在進程并發(fā)執(zhí)行時，getspace或release(ad)將有能夠完不成所要求的功能。getspace和release(ad)可進一步描畫為： getspace: begin local g g←stack［top］ top←top-1 end release(ad): begin top←top+1 stack［top］←ad end設時辰t0時，top=h0，那么getspace和release(ad)能夠按以下順序執(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；其結果是調用getspace的進程取到的是h0+1中的一個未定義值，而調用release(ad)的進程把所釋放的空塊地址ad反復放入了h0中。怎樣保證上述執(zhí)行結果的正確性呢？一個較為明顯的答案是，假設把getspace和release(ad)籠統(tǒng)為兩個各以一個動作完成的順序執(zhí)行單位，那么執(zhí)行結果的正確性是可以保證的。把不允許多個并發(fā)進程交叉執(zhí)行的一段程序稱為臨界部分〔criticalsection〕或臨界區(qū)〔criticalregion〕。臨界區(qū)是由屬于不同并發(fā)進程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的，例如上例中就是由于過程getspace和release(ad)共同訪問棧Ｓ中的數(shù)據(jù)而引起的。臨界區(qū)不能夠用添加硬件的方法來處理。因此，臨界區(qū)也可以被稱為訪問公用數(shù)據(jù)的那段程序。2.間接制約普通來說，可以把那些不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的集合。上例中，以公用數(shù)據(jù)棧Ｓ劃分的臨界區(qū)集合是{getspace,release}。把這些集合稱為類〔class〕。顯然，對類給定一個獨一的標識名，系統(tǒng)就會容易地域分它們。在程序的描畫中，可用以下規(guī)范方式來描畫臨界區(qū)： when〈類名〉do〈臨界區(qū)〉od設類{getspace，release}的類名為sp，那么getspace和release(ad)可重新描畫為： getspace: whenspdogetspce←stack［top］ top←top-1od release(ad):whenspdotop←top+1 stack［top］←adod把這種由于共享某一公有資源而引起的在臨界區(qū)內不允許并發(fā)進程交叉執(zhí)行的景象，稱為由共享公有資源而呵斥的對并發(fā)進程執(zhí)行速度的間接制約，簡稱間接制約。這里，“間接〞二字主要是指各并發(fā)進程的速度受公有資源制約，而不是進程間直接制約的意思。這里，受間接制約的類中各程序段在執(zhí)行順序上是恣意的。顯然，對于每一類，系統(tǒng)應有相應的分配和釋放相應公有資源的管理方法，以制約并發(fā)進程。這就是互斥。3.什么是互斥可以把互斥定義為：一組并發(fā)進程中的一個或多個程序段，因共享某一公有資源而導致它們必需以一個不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)稱為互斥。這里，思索類中只需一個元素，也就是只需一個程序段的情況是很有意思的。這時程序段本身為公有資源被并發(fā)進程共享。普通情況下，作為程序段的一個過程不允許多個進程共同訪問它。但假設該過程是純過程，那么各并發(fā)進程可以同時訪問它。純過程是指在執(zhí)行過程中不改動過程本身代碼的一類過程。通常，在計算機系統(tǒng)中，有許多過程是被多個并發(fā)進程同時訪問共享，例如編輯程序、編譯程序等。把一個過程作成純過程可便于多個進程共享，但由于編制純過程必需對有關變量和任務區(qū)作相應的處置，從而其執(zhí)行效率往往會遭到一定的影響。一組并發(fā)進程互斥執(zhí)行時必需滿足如下準那么：(1)不能假設各并發(fā)進程的相對執(zhí)行速度。即各并發(fā)進程享有平等的、獨立的競爭共有資源的權益，且在不采取任何措施的條件下，在臨界區(qū)內任一指令終了時，其他并發(fā)進程可以進入臨界區(qū)。(2)并發(fā)進程中的某個進程不在臨界區(qū)時，它不阻止其他進程進入臨界區(qū)。(3)并發(fā)進程中的假設干個進程懇求進入臨界區(qū)時，只能允許一個進程進入。(4)并發(fā)進程中的某個進程懇求進入臨界區(qū)時開場，應在有限時間內得以進入臨界區(qū)。這里，準那么(1)，(2)，(3)是保證各并發(fā)進程享有平等的、獨立的競爭和運用公有資源的權益，且保證每一時辰至多只需一個進程在臨界區(qū)。而準那么(4)那么是并發(fā)進程不發(fā)生死鎖〔將在后面講述〕的重要保證。否那么，由于某個并發(fā)進程長期占有臨界區(qū)，其他進程那么由于不能進入臨界區(qū)而進入相互等待形狀。在一組并發(fā)執(zhí)行進程中，除了由于競爭公有資源而引起的間接制約帶來進程之間互斥之外，還存在有由于并發(fā)進程相互共享對方的私有資源所引起的直接制約。直接制約將使得各并發(fā)進程同步執(zhí)行。下面，將討論互斥的實現(xiàn)方法。3.5.2互斥的加鎖實現(xiàn)上節(jié)中，給出了臨界區(qū)的描畫方法和并發(fā)進程互斥執(zhí)行時所必要遵守的準那么。但是，并沒有給出怎樣實現(xiàn)并發(fā)進程的互斥。人們能夠以為只需把臨界區(qū)中的各個過程按不同的時間陳列調用就行了。但現(xiàn)實上這是不能夠的。由于這要求該組并發(fā)進程中的每個進程事先知道其他并發(fā)進程與系統(tǒng)的動作，由用戶程序執(zhí)行開場的隨機性可知，這是不能夠的。一種能夠的方法是對臨界區(qū)加鎖以實現(xiàn)互斥。當某個進程進入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進程在懇求進入臨界區(qū)時，首先測試該臨界區(qū)能否是上鎖的。假設該臨界區(qū)已被鎖住，那么該進程要等到該臨界區(qū)開鎖之后才有能夠獲得臨界區(qū)。設臨界區(qū)的類名為Ｓ。為了保證每一次臨界區(qū)中只能有一個程序段被執(zhí)行，又設鎖定位key［Ｓ］。key［Ｓ］表示該鎖定位屬于類名為Ｓ的臨界區(qū)。加鎖后的臨界區(qū)程序描畫如下： lock(key［Ｓ］) 〈臨界區(qū)〉 unlock(key［Ｓ］)設key［Ｓ］=1時表示類名為Ｓ的臨界區(qū)可用，key［Ｓ］=0時表示類名為Ｓ的臨界區(qū)不可用。那么，unlock(key［Ｓ］)只用一條語句即可實現(xiàn)。即： key［Ｓ］←1不過，由于lock(key［Ｓ］)必需滿足key［Ｓ］=0時，不允許任何進程進入臨界區(qū)，而key［Ｓ］=1時僅允許一個進程進入臨界區(qū)的準那么，因此實現(xiàn)起來較為困難。一種簡便的實現(xiàn)方法是： lock(x)=beginlocalv repeat v←x untilv=1 x←0 end這種實現(xiàn)方法是不能保證并發(fā)進程互斥執(zhí)行所要求的準那么(3)的。由于當同時有幾個進程調用lock(key［Ｓ］)時，在x←0語句執(zhí)行之前，能夠已有兩個以上的多個進程由于key［Ｓ］=1而進入臨界區(qū)。為處理這個問題有些機器在硬件中設置了“測試與設置指令，保證第一步和第二步執(zhí)行不可分別。留意：在系統(tǒng)實現(xiàn)時鎖定位key［Ｓ］總是設置在公有資源所對應的數(shù)據(jù)構造中的。3.5.3信號量和Ｐ，Ｖ原語1.信號量〔semaphore〕雖然用加鎖的方法可以實現(xiàn)進程之間的互斥，但這種方法依然存在一些影響系統(tǒng)可靠性和執(zhí)行效率的問題。例如，循環(huán)測試鎖定位將損耗較多的CPU計算時間。假設一組并發(fā)進程的進程數(shù)較多，且由于每個進程在懇求進入臨界區(qū)時都得對鎖定位進展測試，這種開銷是很大的。另外，運用加鎖法實現(xiàn)進程間互斥時，還將導致在某些情況下出現(xiàn)不公平景象。試思索以下進程PA和PB反復運用臨界區(qū)的情況： PA A：lock(key［Ｓ］) 〈Ｓ〉 unlock(key［Ｓ］) GotoA PB B：lock(key［Ｓ］) ＜Ｓ＞ unlock(key［Ｓ］) GotoB設進程ＰA已經(jīng)過lock(key［Ｓ］)過程而進入臨界區(qū)。顯然，在進程PA執(zhí)行unlock(key［Ｓ］)過程之前，key［Ｓ］=0且進程PB沒有進入臨界區(qū)的時機。然而，當進程PA執(zhí)行完unlock(key［Ｓ］)過程之后，由于緊接著是一轉向語句，進程PA將又立刻去執(zhí)行l(wèi)ock(key［Ｓ］)過程。此時，由于unlock(key［Ｓ］)過程已將key［Ｓ］的值置為1，也就是開鎖形狀，從而進程PA又可進入臨界區(qū)Ｓ。只需在進程PA執(zhí)行完unlock(key［Ｓ］)過程之后、執(zhí)行GotoA語句之前的瞬間發(fā)生進程調度，使進程PA把處置機轉讓給進程PB，進程PB才有能夠得到執(zhí)行。然而遺憾的是，這種能夠性是非常小的。因此，進程PB將處于永久饑餓形狀〔starvation〕。處理上述問題首先必需找到產(chǎn)生問題的緣由。顯然，在用加鎖法處理進程互斥的問題時，一個進程能否進入臨界區(qū)是依托進程本人調用lock過程去測試相應的鎖定位。每個進程能否進入臨界區(qū)是依托本人的測試判別。這樣沒有獲得執(zhí)行時機的進程當然無法判別，從而出現(xiàn)不公平景象。而獲得了測試時機的進程又因需求測試而損失一定的CPU時間。這正如某個學生想運用某個人人都可借用、且不規(guī)定運用時間的教室時一樣，他必需首先懇求獲得運用該教室的權益，然后再到教室看看該教室是不是被鎖上了。假設該教室被鎖上了，他只好下次再來察看，看該教室的門能否已被翻開。這種反復將繼續(xù)到他進門后為止。從這個例子中，可以得到處理加鎖法所帶來的問題的方法。一種最直觀的方法是，設置一個教室管理員。從而，假設有學生懇求運用教室而未能如愿時，教室管理員記下他的名字，并等到教室門一翻開那么通知該學生進入。這樣，既減少了學生多次來去教室檢查門能否被翻開的時間，又減少了由于學生自發(fā)地檢查呵斥的不公平景象。在操作系統(tǒng)中，這個管理員就是信號量。信號量管理相應臨界區(qū)的公有資源，它代表可用資源實體。信號量的概念和下面所述的Ｐ、Ｖ原語是荷蘭科學家E.W.Dijkstra提出來的。信號是鐵路交通管理中的一種常用設備，交通管理人員利用信號顏色的變化來實現(xiàn)交通管理。在操作系統(tǒng)中，信號量sem是一整數(shù)。在sem大于等于零時代表可供并發(fā)進程運用的資源實體數(shù)，但sem小于零時那么表示正在等待運用臨界區(qū)的進程數(shù)。顯然，用于互斥的信號量sem的初值應該大于零，而建立一個信號量必需經(jīng)過闡明所建信號量所代表的意義，和賦初值以及建立相應的數(shù)據(jù)構造以便指向那些等待運用該臨界區(qū)的進程。2.Ｐ，Ｖ原語信號量的數(shù)值僅能由Ｐ，Ｖ原語操作改動(Ｐ和Ｖ分別是荷蘭語Passeren和Verhoog的頭一個字母，相當于英文的pass和increment的意思)。采用Ｐ，Ｖ原語，可以把類名為Ｓ的臨界區(qū)描畫為WhenＳdoＰ(sem)臨界區(qū)Ｖ(sem)od。這里，sem是與臨界區(qū)內所運用的公用資源有關的信號量。一次Ｐ原語操作使得信號量sem減1，而一次Ｖ原語操作將使得信號量sem加1。必需強調的一點是，當某個進程正在臨界區(qū)內執(zhí)行時，其他進程假設執(zhí)行了Ｐ原語操作，那么該進程并不像調用lock時那樣因進不了臨界區(qū)而前往到lock的起點，等以后重新執(zhí)行測試，而是在等待隊列中等待有其他進程做Ｖ原語操作釋放資源后，進入臨界區(qū)，這時，Ｐ原語的執(zhí)行才算真正終了。另外，當有好幾個進程執(zhí)行Ｐ原語未經(jīng)過而進入等待形狀之后，如有某進程作了Ｖ原語操作，那么等待進程中的一個可以進入臨界區(qū)，但其他進程必需等待。Ｐ原語操作的主要動作是：(1)sem減1；(2)假設sem減1后仍大于或等于零，那么進程繼續(xù)執(zhí)行；(3)假設sem減1后小于零，那么該進程被阻塞后與該信號相對應的隊列中，然后轉進程調度。Ｐ原語操作的功能框圖如圖3.11。圖3.11Ｐ原語操作功能 圖3.12Ｖ原語操作功能Ｖ原語的操作主要動作是：(1)sem加1；(2)假設相加結果大于零，進程繼續(xù)執(zhí)行；(3)假設相加結果小于或等于零，那么從該信號的等待隊列中喚醒一等待進程，然后再前往原進程繼續(xù)執(zhí)行或轉進程調度。Ｖ原語操作的功能框圖如圖3.12。有了加鎖法的根底，大家應該明白為什么Ｐ，Ｖ過程要以原語實現(xiàn)的緣由。否那么，假設多個進程同時調用Ｐ操作或Ｖ操作的話，那么有能夠在Ｐ操作剛把sem-1而未把對應進程送入等待隊列時，Ｖ操作開場執(zhí)行。從而，Ｖ操作將無法發(fā)現(xiàn)等待進程而前往。因此，Ｐ，Ｖ操作都必需以原語實現(xiàn)，且在Ｐ，Ｖ原語執(zhí)行期間不允許中斷發(fā)生。關于Ｐ，Ｖ原語的實現(xiàn)，有許多方法。這里引見一種運用加鎖法的軟件實現(xiàn)方法，實現(xiàn)過程描畫如下： Ｐ〔sem〕： begin 封鎖中斷； lock(lockbit) val［sem］=val［sem］-1 ifval［sem］<0 維護當前進程CPU現(xiàn)場 當前進程形狀置為″等待″ 將當前進程插入信號sem等待隊列 轉進程調度 fi unlock(lockbit)；開放中斷 endＶ〔sem〕： begin 封鎖中斷； lock(lockbit) va［sem］=val［sem］+1 ifval［sem］≤0 localk 從sem等待隊列中選取一等待進程，將其指針置入k中 將k插入就緒隊列 進程形狀置“就緒〞 fi unlock(lockbit)；開放中斷end3.5.4用Ｐ，Ｖ原語實現(xiàn)進程互斥利用Ｐ，Ｖ原語和信號量，可以方便地處理并發(fā)進程的互斥問題，而且不會產(chǎn)生運用加鎖法處理互斥問題時所出現(xiàn)的問題。設信號量sem是用于互斥的信號量，且其初值為1表示沒有并發(fā)進程運用該臨界區(qū)。顯然，由上面幾節(jié)的討論可知，只需把臨界區(qū)置于Ｐ(sem)和Ｖ(sem)之間，即可實現(xiàn)進程間的互斥。當一個進程想要進入臨界區(qū)時，它必需先執(zhí)行Ｐ原語操作以將信號量sem減1。在一個進程完成對臨界區(qū)的操作之后，它必需執(zhí)行Ｖ原語操作以釋放它所占用的臨界區(qū)。由于信號量初始值為1，所以，任一進程在執(zhí)行Ｐ原語操作之后將sem的值變?yōu)?，表示該進程可以進入臨界區(qū)。在該進程未執(zhí)行Ｖ原語操作之前如有另一進程想進入臨界區(qū)的話，它也應先執(zhí)行Ｐ原語操作，從而使sem的值變?yōu)?1，因此，第二個進程將被阻塞。直到第一個進程執(zhí)行Ｖ原語操作之后，sem的值變?yōu)?，從而可喚醒第二個進程進入就緒隊列，經(jīng)調度后再進入臨界區(qū)。在第二個進程執(zhí)行完Ｖ原語操作之后，假設沒有其他進程懇求進入臨界區(qū)的話，那么sem又恢復到初始值。用信號量實現(xiàn)兩并發(fā)進程PA，PB互斥的描畫如下：1)設sem為互斥信號量，其取值范圍為(1,0,-1)。其中sem=1表示進程PA和PB都未進入類名為Ｓ的臨界區(qū)，sem=0表示進程PA或PB已進入類名為Ｓ的臨界區(qū)，sem=-1表示進程PA和PB中，一個進程已進入臨界區(qū)，而另一個進程等待進入臨界區(qū)。2)描畫： PA： Ｐ(sem) 〈Ｓ〉 Ｖ(sem)： ： ：

PB： Ｐ(sem) 〈Ｓ〉 Ｖ(sem)∷ ： ：3.6進程同步3.6.1同步的概念除了對公有資源的競爭而引起的間接制約之外，并發(fā)進程之間能否還存在著其他制約關系影響執(zhí)行速度呢？來看下面的例子。計算進程和打印進程共同運用同一緩沖區(qū)Buf。計算進程反復地把每次計算結果放入Buf中，而打印進程那么把計算進程每次放入Buf中的數(shù)據(jù)經(jīng)過打印機打印輸出。假設不采取任何制約措施，這兩個進程的執(zhí)行起始時間和執(zhí)行速度都是彼此獨立的，其相應的控制段可以描畫為：PA ： : A: localBuf Repeat Buf←Buf Until Buf=空 計算 得到計算結果 Buf←計算結果 Goto APB: ： :B: localPri Repeat Pri←Buf Until Pri≠空 打印Buf中的數(shù)據(jù) 去除Buf中的數(shù)據(jù) Goto B這里，假設假定進程PC和PP對公用緩沖區(qū)Buf已采取了互斥措施。顯然，假設按上面的描畫并發(fā)執(zhí)行進程PA和PB的話，那么會呵斥CPU時間的極大浪費〔由于其中包含有二處反復測試語句〕。這是操作系統(tǒng)設計要求不允許的。CPU時間的浪費主要是由于進程PA和PB的執(zhí)行相互制約所引起的。PA的輸出結果是PB的執(zhí)行條件，反過來，PB的執(zhí)行結果也是PA的執(zhí)行條件。這種景象在操作系統(tǒng)和用戶進程中大量存在。這與上節(jié)中講述的進程互斥是不同的，進程互斥時它們的執(zhí)行順序可以是恣意的。一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程稱為并發(fā)進程間的直接制約。這里異步環(huán)境主要指各并發(fā)進程的執(zhí)行起始時間的隨機性和執(zhí)行速度的獨立性。正如在上面例子中所看到的那樣，假設沒有相應的處理方法，進程的直接制約將會呵斥大量的CPU時間浪費。一種最為簡單和直觀的方法是直接制約的進程相互給對方進程發(fā)送執(zhí)行條件曾經(jīng)具備的信號。這樣，被制約進程即可省去對執(zhí)行條件的測試，只需收到了制約進程發(fā)來的信號便開場執(zhí)行，而在未收到制約進程發(fā)來的信號時便進入等待形狀。把異步環(huán)境下的一組并發(fā)進程，因直接制約而相互發(fā)送音訊而進展相互協(xié)作、相互等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步。具有同步關系的一組并發(fā)進程稱為協(xié)作進程，協(xié)作進程間相互發(fā)送的信號稱為音訊或事件。假設對一個音訊或事件賦以獨一的音訊名，那么可用過程 wait(音訊名〕表示進程等待協(xié)作進程發(fā)來的音訊，而用過程 signal〔音訊名〕表示向協(xié)作進程發(fā)送音訊。利用過程wait和signal，可以簡單地描畫上面例子中的計算進程PA和打印進程PB的同步關系如下：(1)設音訊名Bufempty表示Buf空，音訊名Buffull表示Buf中裝滿了數(shù)據(jù)。(2)初始化Bufempty=true，Buffull=false。(3)描畫： PA ： A: wait(Bufempty) 計算 Buf←計算結果 signal(Buffull) Goto A PB ： B: wait(Buffull) 打印Buf中的數(shù)據(jù) 去除Buf中的數(shù)據(jù) signal(Bufempty) Goto B過程wait的功能是等待到音訊名為true的進程繼續(xù)執(zhí)行，而signal的功能那么是向協(xié)作進程發(fā)送協(xié)作進程所需求的音訊名，并將其值置為true。3.6.2私用信號量上面用wait〔音訊名〕與signal〔音訊名〕的方式，描畫了進程同步的一種實現(xiàn)方法。現(xiàn)實上，運用信號量的方法也可實現(xiàn)進程間的同步。普通來說，也可以把各進程之間發(fā)送的音訊作為信號量對待。與進程互斥時不同的是，這里的信號量只與制約進程及被制約進程有關而不是與整組并發(fā)進程有關。因此，稱該信號量為私用信號量〔PrivateSemaphvre〕。一個進程Pi的私用信號量Semi是從制約進程發(fā)送來的進程Pi的執(zhí)行條件所需求的音訊。與私用信號量相對應，稱互斥時運用的信號量為公用信號量。3.6.3用Ｐ，Ｖ原語操作實現(xiàn)同步有了私用信號量的概念，可以運用Ｐ，Ｖ原語操作實現(xiàn)進程間的同步。利用Ｐ，Ｖ原語實現(xiàn)進程同步的方法與利用wait和signal過程時一樣，也是分為三步。首先為各并發(fā)進程設置私用信號量，然后為私用信號量賦初值，最后利用Ｐ，Ｖ原語和私用信號量規(guī)定各進程的執(zhí)行順序。緩沖區(qū)隊列圖初值a=1，表示BUF為空；b=0表示BUF為非滿。PA:L:P(a)計算；計算結果BUFV(b)GotoL;PB:L:P(b)計算；BUF打印V(a)GotoL;例：設進程PA和PB經(jīng)過緩沖區(qū)隊列傳送數(shù)據(jù)〔如圖〕。PA為發(fā)送進程，PB為接納進程。PA發(fā)送數(shù)據(jù)時調用發(fā)送過程deposit(data)，PB接納數(shù)據(jù)時調用過程remove(data)。且數(shù)據(jù)的發(fā)送和接納過程滿足如下條件：(1)在PA至少送一塊數(shù)據(jù)入一個緩沖區(qū)之前，PB不能夠從緩沖區(qū)中取出數(shù)據(jù)〔假定數(shù)據(jù)塊長等于緩沖區(qū)長度〕；〔2)PA往緩沖隊列發(fā)送數(shù)據(jù)時，至少有一個緩沖區(qū)是空的；〔3)由PA發(fā)送的數(shù)據(jù)塊在緩沖隊列中按先進先出〔FIFO〕方式陳列。描畫發(fā)送過程deposit(data)和接納過程remove(data)。解：由題意可知，進程PA調用的過程deposit(data)和進程PB調用的過程remove(data)必需同步執(zhí)行，由于過程deposit(data)的執(zhí)行結果是過程remove(data)的執(zhí)行條件，而當緩沖隊列全部裝滿數(shù)據(jù)時，remove(data)的執(zhí)行結果又是deposit(data)的執(zhí)行條件，滿足同步定義。從而，按以下三步描畫過程deposit(data)和remove(data)：〔1)設Bufempty為進程PA的私用信號量，Buffull為進程PB的私用信號量；〔2)令Bufempty的初始值為n〔n為緩沖隊列的緩沖區(qū)個數(shù)〕，Buffull的初始值為0；〔3)描畫：PA:deposit(data): beginlocalx P(Bufempty)； 按FIFO方式選擇一個空緩沖區(qū)Buf(x)； Buf(x)←data Buf(x)置滿標志 Ｖ〔Buffull〕 endPB:remove(data): Beginlocalx Ｐ〔Buffull〕； 按FIFO方式選擇一個裝滿數(shù)據(jù)的緩沖區(qū)Buf(x) data←Buf(x) Buf(x)置空標志 Ｖ〔Bufempty〕 end這里，部分變量x用來指明緩沖區(qū)的區(qū)號，給Buf(x)置標志位是為了便于區(qū)別和搜索空緩沖區(qū)及非空緩沖區(qū)。3.6.4消費者-消費者問題〔producer-consumerproblems〕把并發(fā)進程的同步和互斥問題普通化，可以得到一個籠統(tǒng)的普通模型，即消費者-消費者問題。計算機系統(tǒng)中，每個進程都懇求運用和釋放各種不同類型的資源，這些資源既可以是像外設、內存及緩沖區(qū)等硬件資源，也包括臨界區(qū)、數(shù)據(jù)、例程等軟件資源。把系統(tǒng)中運用某一類資源的進程稱為該資源的消費者，而把釋放同類資源的進程稱為該資源的消費者。例如在上面的計算進程PC與打印進程PP公用一個緩沖區(qū)的例子中，計算進程PC把數(shù)據(jù)送入緩沖區(qū)，打印進程PP從緩沖區(qū)中取數(shù)據(jù)打印輸出，因此，PC進程相當于數(shù)據(jù)資源的消費者，而PP進程相當于消費者。把一個長度為ｎ的有界緩沖區(qū)〔n>0)與一群消費者進程Ｐ1，Ｐ2，…，Ｐm和一群消費者進程Ｃ1，Ｃ2，…，Ｃk聯(lián)絡起來〔如下圖〕。設消費者進程和消費者進程是相互等效的，其中，各消費者進程運用的過程deposit(data)和各消費者運用的過程remove(data)可描畫如下：首先，可以看到，上述消費者-消費者問題是一個同步問題。即消費者和消費者之間滿足如下條件：(1)消費者想接納數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的；(2)消費者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的。另外，由于有界緩沖區(qū)是臨界資源，因此，各消費者進程和各消費者進程之間必需互斥執(zhí)行。消費者-消費者問題圖第一種實現(xiàn)：設a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。消費者進程：P(a)；消費產(chǎn)品；放入空的格；V(b);消費者進程：P(b)；從滿格取出產(chǎn)品；消費產(chǎn)品；V(a);鏈表問題搜索步驟：repeatIf找到then前往指針else指針下移一個Until指針=null假設多個進程并發(fā)執(zhí)行會破壞封鎖性和可再現(xiàn)性。NULL多個進程執(zhí)行到此第二種實現(xiàn)：設a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。M=1；表示互斥空格區(qū)；消費者進程：P(a)；消費產(chǎn)品；P(m)；放入空的格；V(m)；V(b);消費者進程：P(b)；P(m)；從滿格取出產(chǎn)品；V(m)；消費產(chǎn)品；V(a);第三種實現(xiàn)：提高并發(fā)程度設a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。M=1；表示互斥空格區(qū)；消費者進程：消費產(chǎn)品；P(a)；P(m)；放入空的格；V(m)；V(b);消費者進程：P(b)；P(m)；從滿格取出產(chǎn)品；V(m)；V(a);消費產(chǎn)品；由以上分析，設公用信號量mutex保證消費者進程和消費者進程之間的互斥，設信號量avail為消費者進程的私用信號量，信號量full為消費者進程的私用信號量。信號量avail表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號量full表示有界緩沖區(qū)中非空單元數(shù)，初值為0。信號量mutex表示可用有界緩沖區(qū)的個數(shù)，初值為1。從而有： deposit(data): begin Ｐ〔avail〕 Ｐ〔mutex〕 送數(shù)據(jù)入緩沖區(qū)某單元 Ｖ〔full〕 Ｖ〔mutex〕 end remove(data): begin Ｐ〔full〕 Ｐ〔mutex〕 取緩沖區(qū)中某單元數(shù)據(jù) Ｖ〔avail〕 Ｖ〔mutex〕 end在上例中，由于一個過程中包含有幾個公用、私用信號量，因此，Ｐ、Ｖ原語的操作次序要非常小心。普通說來，由于Ｖ原語是釋放資源的，所以可以以恣意次序出現(xiàn)。但Ｐ原語那么不然，假設次序混亂，將會呵斥進程之間的死鎖。關于死鎖，將在3.8中引見。3.7進程通信本節(jié)引見進程間相互傳送信息的方法和原理。通訊〔communication〕意味著在進程間傳送數(shù)據(jù)。操作系統(tǒng)可以被看作是各種進程組成的。這些進程都具有各自的獨立功能，且大多數(shù)被外部需求而啟動執(zhí)行。普通來說，進程間的通訊根據(jù)通訊內容可以劃分為二種：即控制信息的傳送與大批量數(shù)據(jù)傳送。有時，也把進程間控制信息的交換稱為低級通訊，而把進程間大批量數(shù)據(jù)的交換稱為高級通訊。上面幾節(jié)中所引見的進程間同步或互斥，也是運用鎖或信號量進展通訊來實現(xiàn)的。低級通訊普通只傳送一個或幾個字節(jié)的信息，以到達控制進程執(zhí)行速度的作用。高級通訊要傳送大量數(shù)據(jù)。高級通訊的目的不是為了控制進程的執(zhí)行速度，而是為了交換信息。3.7.1進程的通訊方式在單機系統(tǒng)中，進程間通訊可分為4種方式：(1)主從式；(2)會話式；(3)音訊或郵箱機制；(4)共享存儲區(qū)方式。主從式通訊系統(tǒng)的主要特點是：①主進程可自在地運用從進程的資源或數(shù)據(jù)；②從進程的動作受主進程的控制；③主進程和從進程的關系是固定的。主從式通訊系統(tǒng)的典型例子是終端控制進程和終端進程。會話方式中，通訊進程雙方可分別稱為運用進程和效力進程。其中，運用進程調用效力進程提供的效力。它們具有如下特點：①運用進程在運用效力進程所提供的效力之前，必需得到效力進程的答應；②效力進程根據(jù)運用進程的要求提供效力，但對所提供效力的控制由效力進程本身完成。③運用進程和效力進程在通訊時有固定銜接關系。用戶進程與磁盤管理進程之間的通訊是會話系統(tǒng)的一個例子。各用戶進程向磁盤管理進程提出運用要求并得到答應之后，才可以運用相應的存儲區(qū)。而且，由磁盤管理進程本身完成對磁盤存儲區(qū)的管理和控制。另外，用戶進程與磁盤管理進程之間，只需在用戶進程要求運用磁盤存儲區(qū)時才有通訊關系。音訊或郵箱機制那么無論接納進程能否已預備好接納音訊，發(fā)送進程都將把所要發(fā)送的音訊送入緩沖區(qū)或郵箱。音訊的普通方式為４個部分組成。即：發(fā)送進程名、接納進程名、數(shù)據(jù)和有關數(shù)據(jù)的操作。音訊或郵箱機制的特點是：①只需存在空緩沖區(qū)或郵箱，發(fā)送進程就可以發(fā)送音訊。②與會話系統(tǒng)不同，發(fā)送進程和接納進程之間無直接銜接關系，接納進程能夠在收到某個發(fā)送進程發(fā)來的音訊之后，又轉去接納另一個發(fā)送進程發(fā)來的音訊。音訊的組成圖緩沖區(qū)或郵箱通訊構造圖③發(fā)送進程和接納進程之間存在緩沖區(qū)或郵箱用來存放被傳送音訊。與前面三種方式不同，共享存儲區(qū)方式不要求數(shù)據(jù)挪動。兩個需求相互交換信息的進程經(jīng)過對同一共享數(shù)據(jù)區(qū)〔sharedmemory〕的操作來到達相互通訊的目的。這個共享數(shù)據(jù)區(qū)是每個相互通訊進程的一個組成部分。以上幾種通訊方式都可用于大量數(shù)據(jù)傳送，而且，由于其通訊方式不同，需求運用不同的控制方式來到達通訊進程之間同步或互斥的目的。下面，首先引見進程通訊中較為常用的音訊與郵箱機制，然后再引見幾個實踐例子。3.7.2音訊緩沖機制發(fā)送進程和接納進程采用音訊緩沖機制進展數(shù)據(jù)傳送時，發(fā)送進程在發(fā)送音訊前，先在本人的內存空間設置一個發(fā)送區(qū)，把欲發(fā)送的音訊填入其中，然后再用發(fā)送過程將其發(fā)送出去。接納進程那么在接納音訊之前，在本人的內存空間內設置相應的接納區(qū)，然后用接納過程接納音訊。由于音訊緩沖機制中所運用的緩沖區(qū)為公用緩沖區(qū)，運用音訊緩沖機制傳送數(shù)據(jù)時，兩通訊進程必需滿足如下條件：①在發(fā)送進程把音訊寫入緩沖區(qū)和把緩沖區(qū)掛入音訊隊列時，應制止其他進程對該緩沖區(qū)音訊隊列的訪問。否那么，將引起音訊隊列的混亂。同理，當接納進程正從音訊隊列中取音訊緩沖時，也應制止其他進程對該隊列的訪問。②當緩沖區(qū)中無音訊存在時，接納進程不能接納到任何音訊。至于發(fā)送進程能否可以發(fā)送音訊，那么由發(fā)送進程能否懇求到緩沖區(qū)決議。設公用信號量mutex為控制對緩沖區(qū)訪問的互斥信號量，其初值為1。設SM為接納進程的私用信號量，表示等待接納的音訊個數(shù)，其初值為0。設發(fā)送進程調用過程send(m)將音訊m送往緩沖區(qū)，接納進程調用過程Receive(m)將音訊m從緩沖區(qū)讀往本人的數(shù)據(jù)區(qū)，那么Send(m)和Receive(n)可分別描畫為：Send(m): begin 向系統(tǒng)懇求一個音訊緩沖區(qū) Ｐ〔mutex〕 將發(fā)送區(qū)音訊m送入新懇求的音訊緩沖區(qū) 把音訊緩沖區(qū)掛入接納進程的音訊隊列 Ｖ〔mutex〕 Ｖ〔SM〕 endReceive(n): begin Ｐ〔SM〕 Ｐ〔mutex〕 摘下音訊隊列中的音訊n 將音訊n從緩沖區(qū)復制到接納區(qū) 釋放緩沖區(qū) Ｖ〔mutex〕 end(3)激活〔unblock〕：假設阻塞線程的事件發(fā)生，那么該線程被激活并進入就緒隊列。從而，假設并發(fā)執(zhí)行的程序段不按照特定的規(guī)那么和方法進展資源共享和競爭，那么其執(zhí)行結果將不可防止地失去封鎖性和可再現(xiàn)性。有了加鎖法的根底，大家應該明白為什么Ｐ，Ｖ過程要以原語實現(xiàn)的緣由。PA的輸出結果是PB的執(zhí)行條件，反過來，PB的執(zhí)行結果也是PA的執(zhí)行條件。試思索以下進程PA和PB反復運用臨界區(qū)的情況：PCB中設有專門的CPU現(xiàn)場維護構造，以存儲退出執(zhí)行時的進程現(xiàn)場數(shù)據(jù)。PCB中設有專門的CPU現(xiàn)場維護構造，以存儲退出執(zhí)行時的進程現(xiàn)場數(shù)據(jù)。分析平安檢查算法的時間復雜度？進程上下文可按一定的執(zhí)行層次組合，例如用戶級上下文、系統(tǒng)級上下文等。并發(fā)進程所要求和占有的資源是不能同時被兩個以上進程運用或操作的，進程對它所需求的資源進展排他性控制。也就是說，雖然相關進程的的形狀是阻塞的或等待的，但所屬線程形狀卻是執(zhí)行的。例如在上面的計算進程PC與打印進程PP公用一個緩沖區(qū)的例子中，計算進程PC把數(shù)據(jù)送入緩沖區(qū)，打印進程PP從緩沖區(qū)中取數(shù)據(jù)打印輸出，因此，PC進程相當于數(shù)據(jù)資源的消費者，而PP進程相當于消費者。當進程ＰA或ＰB釋放數(shù)據(jù)塊時，那么把所釋放數(shù)據(jù)塊的地址放入堆棧頂部。remove(m):普通來說，可以把那些不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的集合。在操作系統(tǒng)中，這個管理員就是信號量。普通來說，雖然系統(tǒng)中可利用的緩沖區(qū)總數(shù)是知的，但由于音訊隊列是按接納進程陳列，因此，在同一時間內，系統(tǒng)中存在著多個音訊隊列；且這些隊列的長度是不固定的。因此，發(fā)送進程無法在Send過程用Ｐ操作判別信號量SM。3.7.3郵箱通訊郵箱通訊就是由發(fā)送進程懇求建立一與接納進程鏈接的郵箱。發(fā)送進程把音訊送往郵箱，接納進程從郵箱中取出音訊，從而完成進程間信息交換。設置郵箱的最大益處就是發(fā)送進程和接納進程之間沒有處置時間上的限制。一個郵箱可思索成發(fā)送進程與接納進程之間的大小固定的私有數(shù)據(jù)構造，它不像緩沖區(qū)那樣被系統(tǒng)內一切進程共享。郵箱由郵箱頭和郵箱體組成。其中郵箱頭描畫郵箱稱號、郵箱大小、郵箱方向以及擁有該郵箱的進程名等。郵箱體主要用來存放音訊。郵箱通訊構造圖對于只需一發(fā)送進程和一接納進程運用的郵箱，那么進程間通訊應滿足如下條件：①發(fā)送進程發(fā)送音訊時，郵箱中至少要有一個空格能存放該音訊。②接納進程接納音訊時，郵箱中至少要有一個音訊存在。設發(fā)送進程調用過程deposit(m)將音訊發(fā)送到郵箱，接納進程調用過程remove(m)將音訊m從郵箱中取出。另外，為了記錄郵箱中空格個數(shù)和音訊個數(shù)，信號量fromnum為發(fā)送進程的私用信號量，信號量mesnum為接納進程的私用信號量。fromnum的初值為信箱的空格數(shù)n，mesnum的初值為0。那么deposit(m)和remove(m)可描畫如下： deposit(m): beginlocalx Ｐ〔fromnum〕 選擇空格x 將音訊m放入空格x中 置格x的標志為滿 Ｖ〔mesnum〕 end remove(m): beginlocalx Ｐ〔mesnum〕 選擇滿格x 把滿格x中的音訊取出放m中 置格x標志為空 Ｖ〔fromnum〕 end顯然，調用過程deposit(m)的進程與調用過程remove(m)的進程之間存在著同步制約關系而不是互斥制約關系。另外，在許多時侯，存在著多個發(fā)送進程和多個接納進程共享郵箱的情況。這時需求對過程deposit(m)和remove(m)作相應的改動。3.8死鎖問題3.8.1死鎖的概念1.死鎖的定義各進程在運用系統(tǒng)資源時，應留意系統(tǒng)產(chǎn)生死鎖問題。所謂死鎖，是指各并發(fā)進程彼此相互等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放本人所擁有的資源。從而呵斥大家都想得到資源而又都得不到資源，各并發(fā)進程不能繼續(xù)向前推進的形狀。圖示是兩個進程發(fā)生死鎖時的例子。 下面以消費者/消費者問題為例來進一步看看死鎖的概念。設消費者進程已獲得對緩沖區(qū)隊列的操作權，消費者進程進一步要求對緩沖區(qū)內的某一空緩沖區(qū)進展置入音訊操作。然而，設此時緩沖隊列內一切緩沖區(qū)都是滿的，即只需消費者進程才干對它們進展取音訊操作。因此，消費者進程進入等待形狀。反過來，消費者進程擁有對各緩沖區(qū)操作的操作權，為了對各緩沖區(qū)進展操作，它又要懇求對緩沖隊列操作的操作權。由于對緩沖隊列的操作權被消費者進程掌握，且消費者進程不會自動釋放它，從而消費者進程也只能進入等待形狀而墮入死鎖。普通地，可以把死鎖描畫為：有并發(fā)進程P1，P2，…，Pn，它們共享資源R1，R2，…，Rm〔n>0，m>0，n>=m〕。其中，每個Pi〔1≤i≤n〕擁有資源Rj〔1≤j≤m〕，直到不再有剩余資源。同時，各Pi又在不釋放Rj的前提下要求得到Rk〔k≠j，1≤k≤m〕，從而呵斥資源的相互占有和相互等待。在沒有外力驅動的情況下，該組并發(fā)進程停頓往前推進，墮入永久等待形狀。2.死鎖的原因死鎖的原因是并發(fā)進程的資源競爭。產(chǎn)生死鎖的根本緣由在于系統(tǒng)提供的資源個數(shù)少于并發(fā)進程所要求的該類資源數(shù)。顯然，由于資源的有限性，不能夠為一切要求資源的進程無限制地提供資源。但是，可以采用適當?shù)馁Y源分配算法，以到達消除死鎖的目的。為此，先看看產(chǎn)生死鎖的必要條件。3.產(chǎn)生死鎖的必要條件(1)互斥條件。并發(fā)進程所要求和占有的資源是不能同時被兩個以上進程運用或操作的，進程對它所需求的資源進展排他性控制。(2)不剝奪條件。進程所獲得的資源在未運用終了之前，不能被其他進程強行剝奪，而只能由獲得該資源的進程本人釋放。(3)部分分配。進程每次懇求它所需求的一部分資源，在等待新資源的同時繼續(xù)占用已分配到的資源。(4)環(huán)路條件。存在一種進程循環(huán)鏈，鏈中每一個進程已獲得的資源同時被下一個進程所懇求。顯然，只需使上述4個必要條件中的某一個不滿足，那么死鎖就可以排除。3.8.2死鎖的排除方法處理死鎖的方法普通可分為預防、防止、檢測與恢復等三種。預防是采用某種戰(zhàn)略，限制并發(fā)進程對資源的懇求，從而使得死鎖的必要條件在系統(tǒng)執(zhí)行的任何時間都不滿足。防止是指系統(tǒng)在分配資源時，根據(jù)資源的運用情況提早做出預測，從而防止死鎖的發(fā)生。死鎖檢測與恢復是指系統(tǒng)設有專門的機構，當死鎖發(fā)生時，該機構可以檢測到死鎖發(fā)生的位置和緣由，并能經(jīng)過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進程從死鎖形狀中恢復出來。經(jīng)過預防和防止的手段到達排除死鎖的目的是一件非常困難的事。死鎖的檢測和恢復那么不用破費多少執(zhí)行時間就能發(fā)現(xiàn)死鎖和從死鎖中恢復出來。因此，在實踐操作系統(tǒng)中大都運用檢測與恢復法排除死鎖。1.死鎖預防一種方法是突破資源的互斥和不可剝奪這兩個條件，例如允許進程同時訪問某些資源等。這種方法不能處理訪問那些不允許被同時訪問的資源時所帶來的死鎖問題。另一種方法那么是突破資源的部分分配這個死鎖產(chǎn)生的必要條件。即預先分配各并發(fā)進程所需求的全部資源。如某個進程的資源得不到滿足時，那么安排一定的等待次序讓其他進程釋放資源。但是，這種方法也有如下缺陷：(1)在許多情況下，一個進程在執(zhí)行之前不能夠提出它所需求的全部資源。(2)無論所需資源何時用到，一個進程只需在一切要求資源都得到滿足之后才開場執(zhí)行。(3)對于那些不經(jīng)常運用的資源，進程在生存過程期間不斷占用它們是一種極大的浪費。(4)降低了進程的并發(fā)性。另外一種死鎖的預防方法是突破死鎖的環(huán)路條件。即把資源分類按順序陳列，使進程在懇求、堅持資源時不構成環(huán)路。如有m種資源，那么列出R1＜R2＜…＜Rm。假設進程Pi堅持了資源Ri，那么它只能懇求比Ri級別更高的資源Rj〔Ri＜Rj〕。釋放資源時必需是Rj先于Ri被釋放，從而防止環(huán)路的產(chǎn)生。這種方法的缺陷是限制了進程對資源的懇求，而且對資源的分類編序也耗去一定的系統(tǒng)開銷。2死鎖