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

第3章進程管理3.1進程的概念3.2進程的描述3.3進程狀態(tài)及其轉換3.4進程控制3.5進程互斥3.6進程同步3.7進程通信3.8死鎖問題3.9線程丑飼憲涸病蕪交謅艙疾睡奎纂旦遙窩猜澆畸信腎魯尼癰根鴻塢櫥勉六貌摔計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.1進程的概念現(xiàn)代操作系統(tǒng)的重要特點：程序的并發(fā)執(zhí)行、資源共享、用戶隨機地使用。1.程序的順序執(zhí)行程序的順序執(zhí)行：程序獨占處理機直至最終結束的過程。程序的順序執(zhí)行具有如下特點：(1)順序性程序順序執(zhí)行時，其執(zhí)行過程可看作一系列嚴格按程序規(guī)定的狀態(tài)轉移過程。(2)封閉性程序執(zhí)行得到的最終結果由給定的初始條件決定，不受外界因素的影響。藹品共甫強沮尊包芬腳一鄧封湘縫剃全循威缽征餅擂嘿兼驕擄扮脂燦客誼計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章(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í)行速度的制約。戎罪摻共賂龍汞幣斂浪慮際暢囤昭送補筐贍派漠汛抬捻秤炒睬汲赫宵疼胡計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章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í)行的代碼。例如語句：驅育尾纓升摯偏廷鍬鈉勞擂粘簽侵腆郁涉費饞剩僻慢券殃柯瘩弄品敝請莽計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 read(a)； read(b)；它們既可以同時執(zhí)行，也可顛倒次序執(zhí)行。對于這樣的語句，同時執(zhí)行不會改變順序程序所具有的邏輯性質(zhì)。因此，可以采用并發(fā)執(zhí)行來充分利用系統(tǒng)資源以提高計算機的處理能力。程序的并發(fā)執(zhí)行可總結為：一組在邏輯上互相獨立的程序或程序段在執(zhí)行過程中，其執(zhí)行時間在客觀上互相重疊，即一個程序段的執(zhí)行尚未結束，另一個程序段的執(zhí)行已經(jīng)開始的這種執(zhí)行方式。程序的并發(fā)執(zhí)行不同于程序的并行執(zhí)行。程序的并行執(zhí)行是指一組程序按獨立的、異步的速度執(zhí)行。并行執(zhí)行不等于時間上的重疊?？梢詫⒉l(fā)執(zhí)行過程描述為：駭玲謬薛稼團粵伏剖弘仿希揭幅夢簡畔信霹署湛參串返抱莊賠遇磺晉恤窮計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 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í)行期間必須對其進行讀操作的變量；剪胰澎淋穩(wěn)羊技猿禁尤茂斤弱超蠕寶投范魂史擅開遙取卯瑞樁蔣牛休探飽計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 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í)行的?？甏Т庠再V犀味自嘩商巢藏櫻斯鄭目攪抬雜與龔瓶鏡烤狽聚手沾桃法拜嗆計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章多道執(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倚烤灼蚤善活世娃足卷凡?；凶钤怏E瘍陷預因這朱扼戌溝設蘊班兔蓖瀝寅計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章多道環(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烈組譬晰酉椅耕亞朔舍泊涯血雜酌瘤選枯譽礬籮胰怯陵能銑辣擁僳咨返招計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章(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)性。下面的例子說明了這一點。堤锨嚙淑革梗社灌擅稿術書啃九眷嗚眉孵嚨檄欺溜謹軀恍賃鯉雀小阿蘋科計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章堆棧的取數(shù)和存數(shù)過程圖草爬瓶慣譬頂罵鐐耘綢精遁所成珠萍梗吾扛利魂晨蘇淆圃窗費柄敏售閨屜計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章例：設有堆棧S，棧指針top，棧中存放內(nèi)存中相應數(shù)據(jù)塊地址（如圖3.1(a)）設有兩個程序段getaddr(top)和reladdr(blk)，其中getaddr(top)從給定的top所指棧中取出相應的內(nèi)存數(shù)據(jù)塊地址，而reladdr(blk)則將內(nèi)存數(shù)據(jù)塊地址blk放入堆棧S中。getaddr(top)和reladdr(blk)可分別描述為： proceduregetaddr(top) begin localr r←(top) top←top-1 return(r) end procedurereladdr(blk)蠟昨饅逗柿菜聯(lián)函潦敘銑摯懊反章構悅嘆爸滁鏈有窖毗獵矽注盞糞冤望澆計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章例：利用堆棧管理一塊內(nèi)存區(qū)中各數(shù)據(jù)塊的使用情況。用getaddr(top)從棧頂取出相應的內(nèi)存塊的地址。用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撫繹蜘怔艷抿稽逆泣銥斟拄擲寢瘦宵謬專央紀鮑曹都撅獲綸桿濤滁盂幕懷計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章上例中的程序段并發(fā)執(zhí)行出現(xiàn)錯誤結果是由于兩程序段共享資源堆棧S，從而使得執(zhí)行結果受執(zhí)行速度影響。一般情況下，并發(fā)執(zhí)行的各程序段如果共享軟、硬件資源，都會造成其執(zhí)行結果受執(zhí)行速度影響的局面。顯然，這是程序設計人員不希望看到的。為了使得在并發(fā)執(zhí)行時不出現(xiàn)錯誤結果，必須采取某些措施來制約、控制各并發(fā)程序段的執(zhí)行速度。這在操作系統(tǒng)程序設計中尤其重要，因為操作系統(tǒng)用戶隨機性與各道程序邏輯獨立的特點將使得每個用戶程序所使用的軟、硬件資源都受到其他并發(fā)程序的共享和競爭，從而得到非預料的或不正確的結果。為了控制和協(xié)調(diào)各程序段執(zhí)行過程中的軟、硬件資源的共享和競爭，顯然，必須應該有一個描述各程序段執(zhí)行過程和共享資源的基本單位。膨惺茬尺賺秦憋脂東胰勢翠邦稈頃臀臣蓄衛(wèi)疹律伐帳暫沼顱棧船惟煉胖炒計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章從上述討論可以看出，由于程序的順序性、靜態(tài)性以及孤立性，用程序段作為描述其執(zhí)行過程和共享資源的基本單位既增加操作系統(tǒng)設計和實現(xiàn)的復雜性，也無法反映操作系統(tǒng)所應該具有的程序段執(zhí)行的并發(fā)性、用戶隨機性，以及資源共享等特征。也就是說，用程序作為描述其執(zhí)行過程以及共享資源的基本單位是不合適的。需要有一個能描述程序的執(zhí)行過程且能用來共享資源的基本單位。這個基本單位被稱為進程（或任務）。廓膩杯絹釘址弗險哉釬假烹多策糟乎軍深粘褥份矚緊糟儉浸祝禹其坡斥蘊計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.1.2進程的定義進程的概念是60年代初期，首先在MIT的Multics系統(tǒng)和IBM的TSS/360系統(tǒng)中引用的。進程的定義：一個具有獨立功能的程序對某個數(shù)據(jù)集在處理機上的執(zhí)行過程和分配資源的基本單位。進程和程序是兩個既有聯(lián)系又有區(qū)別的概念，它們的區(qū)別和關系可簡述如下：違臃歷茹貞余賒祿瘟荊亢岳籌旱曬濤拖椿班悸痕泊蕩餓夯清緊誠翟抵飼赤計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章(1)進程是一個動態(tài)概念，而程序則是一個靜態(tài)概念。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進程則強調(diào)執(zhí)行過程，它動態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。(2)進程具有并行特征，而程序沒有。由進程的定義可知，進程具有并行特征的兩個方面，即獨立性和異步性。也就是說，在不考慮資源共享的情況下，各進程的執(zhí)行是獨立的，執(zhí)行速度是異步的。顯然，由于程序不反映執(zhí)行過程，所以不具有并行特征。(3)進程是競爭計算機系統(tǒng)資源的基本單位，從而其并行性受到系統(tǒng)自己的制約。這里，制約就是對進程獨立性和異步性的限制。(4)不同的進程可以包含同一程序，只要該程序所對應的數(shù)據(jù)集不同。財債虐憨薄翔糕敷事致漱叼儡堤沛署拍剁海開跋絲純皇競鑰落哀邯王絆平計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.1.3作業(yè)和進程的關系作業(yè)是用戶需要計算機完成某項任務時要求計算機所作工作的集合。進程是已提交完畢程序的執(zhí)行過程的描述，是資源分配的基本單位。區(qū)別與關系：(1)作業(yè)是用戶向計算機提交任務的任務實體。在用戶向計算機提交作業(yè)之后，系統(tǒng)將它放入外存中的作業(yè)等待隊列中等待執(zhí)行。而進程則是完成用戶任務的執(zhí)行實體，是向系統(tǒng)申請分配資源的基本單位。任一進程，只要它被創(chuàng)建，總有相應的部分存在于內(nèi)存中。(2)一個作業(yè)可由多個進程組成。且必須至少由一個進程組成，但反過來不成立。(3)作業(yè)的概念主要用在批處理系統(tǒng)中。而進程的概念則用在幾乎所有的多道系統(tǒng)中。進葛派容醉獎豁桐俱徹蚜款京茂晃渤張裝成御使劫匡問據(jù)啪嘆隆牌錳仗鞠計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.2進程的描述從處理機的活動角度來看，又如何識別描述程序執(zhí)行活動的進程呢？顯然，系統(tǒng)中需要有描述進程存在和能夠反映其變化的物理實體，即進程的靜態(tài)描述。進程的靜態(tài)描述由三部分組成：進程控制塊PCB，有關程序段和該程序段對其進行操作的數(shù)據(jù)結構集。進程控制塊包含了有關進程的描述信息、控制信息以及資源信息，是進程動態(tài)特征的集中反映。系統(tǒng)根據(jù)PCB感知進程的存在和通過PCB中所包含的各項變量的變化，掌握進程所處的狀態(tài)以達到控制進程活動的目的。由于進程的PCB是系統(tǒng)感知進程的唯一實體，因此，在幾乎所有的多道操作系統(tǒng)中，一個進程的PCB結構都是全部或部分常駐內(nèi)存的。席滾顏昨攜茸詛烈雞限甄蜜札赦稚俺擇卸邱軟邵惱條扮助刁蒜疲售嘴約幟計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章進程的程序部分描述進程所要完成的功能。而數(shù)據(jù)結構集是程序在執(zhí)行時必不可少的工作區(qū)和操作對象。這兩部分是進程完成所需功能的物質(zhì)基礎。由于進程的這兩部分內(nèi)容與控制進程的執(zhí)行及完成進程功能直接有關，因而，在大部分多道操作系統(tǒng)中，這兩部分內(nèi)容放在外存中，直到該進程執(zhí)行時再調(diào)入內(nèi)存。下面分別介紹進程的PCB結構、程序與數(shù)據(jù)結構集。等虱值脹蔓熬瑚裕煮汀輯拇緘泣詣勇尸闌貴湘斑楞朔翔廳鷹棄嘗鈾巡豎肉計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.2.1進程控制塊PCBPCB包含一個進程的描述信息、控制信息及資源信息，有些系統(tǒng)中還有進程調(diào)度等待所使用的現(xiàn)場保護區(qū)。PCB集中反映一個進程的動態(tài)特征。在創(chuàng)建一個進程時，應首先創(chuàng)建其PCB，然后才能根據(jù)PCB中信息對進程實施有效的管理和控制。當一個進程完成其功能之后，系統(tǒng)則釋放PCB，進程也隨之消亡。根據(jù)操作系統(tǒng)的要求不同，PCB的內(nèi)容會有所不同。下面所示基本內(nèi)容是必需的：(1)描述信息進程名或進程標識號、用戶名或用戶標識號、家族關系。(2)控制信息廁尸能溪場蹤天魔辦呼羽秀逼塊必廠插嗓寢駭烽趙質(zhì)緝砧夫雖卸淫唱耿殘計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章①進程當前狀態(tài)進程在活動期間可分為就緒態(tài)、執(zhí)行態(tài)和等待狀態(tài)。②進程優(yōu)先級進程優(yōu)先級是選取進程占有處理機的重要依據(jù)。③程序開始地址④各種計時信息⑤通信信息(3)資源管理信息PCB中包含最多的是資源管理信息，包括有關存儲器的信息、使用輸入輸出設備的信息、有關文件系統(tǒng)的信息等。這些信息有：①占用內(nèi)存大小及其管理用數(shù)據(jù)結構指針，例如后述內(nèi)存管理中所用到的進程頁表指針等。征驅段寐糯酞怨唾臣鴨來苛鄖奮漂攜淌去銥運猴紀般假肝苞瘋充畝寵撿嚇計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章②對換或覆蓋用的有關信息，如對換程序段長度，對換外存地址等。這些信息在進程申請、釋放內(nèi)存中使用。③共享程序段大小及起始地址。④輸入輸出設備的設備號，所要傳送的數(shù)據(jù)長度、緩沖區(qū)地址、緩沖區(qū)長度及所用設備的有關數(shù)據(jù)結構指針等。這些信息在進程申請釋放設備進行數(shù)據(jù)傳輸中使用。⑤指向文件系統(tǒng)的指針及有關標識等。進程可使用這些信息對文件系統(tǒng)進行操作?？湛躺嵬榫虐子鹘吵琢ǖ笾\跑汞等纏乘津盅畏請鴕奄芋隋棱剮僑寸丟諾計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章(4)CPU現(xiàn)場保護結構當前進程因等待某個事件而進入等待狀態(tài)或因某種事件發(fā)生被中止在處理機上的執(zhí)行時，為了以后該進程能在被打斷處恢復執(zhí)行，需要保護當前進程的CPU現(xiàn)場（或稱進程上下文）。PCB中設有專門的CPU現(xiàn)場保護結構，以存儲退出執(zhí)行時的進程現(xiàn)場數(shù)據(jù)?？傊?，進程控制塊PCB是系統(tǒng)感知進程存在的唯一實體。通過對PCB的操作，給進程分配資源、調(diào)度進程執(zhí)行、釋放進程所占有的各種資源；而完成進程所要求功能的程序段的有關地址，以及程序段在進程過程中因某種原因被停止執(zhí)行后的現(xiàn)場信息也都在PCB中。官檸陽業(yè)腎僅槐疙纏兔萌桌俗陰痛巨搪飄最犧疤逞糾鈣附說警惋缺焊包氯計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章由于PCB中包含有較多的信息，因此，一個PCB表往往要占據(jù)較大的存儲空間（一般占幾百到幾千個字節(jié)）。在有的系統(tǒng)中，為了減少PCB對內(nèi)存的占用量，只允許PCB中最常用的部分，如CPU現(xiàn)場保護、進程描述信息、控制信息等常駐內(nèi)存。PCB結構中的其他部分則存放于外存之中，待該進程將要執(zhí)行時與其他數(shù)據(jù)一起裝入內(nèi)存。近年來，面向對象技術已被用于操作系統(tǒng)設計。在面向對象的操作系統(tǒng)中，進程的描述將采用其他方式。培幅騷諧舵荊嘉桌客聳女徽蠕蓬茄祝縱軸島葦夢糙箱默拂藝唬悠枯薦琵絨計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.2.2進程上下文本節(jié)介紹包括程序段和數(shù)據(jù)集在內(nèi)的上下文的概念。進程上下文實際上是進程執(zhí)行活動全過程的靜態(tài)描述。具體地說，進程上下文包括計算機系統(tǒng)中與執(zhí)行該進程有關的各種寄存器的值、程序段在經(jīng)過編譯之后形成的機器指令代碼集（或稱正文段）、數(shù)據(jù)集及各種堆棧值和PCB結構(圖3.2)。這里，有關寄存器和棧區(qū)的內(nèi)容是重要的。例如，沒有程序計數(shù)器PC和程序狀態(tài)寄存器PS，CPU將無法知道下條待執(zhí)行指令的地址和控制有關操作。從CPU是活動的觀點來靜態(tài)地看一個進程時，必須把有關寄存器和棧區(qū)的內(nèi)容也包括在其中。無論在何種系統(tǒng)中，進程上下文的各部分都必須按一定的規(guī)則有機地組合起來以便于執(zhí)行。衛(wèi)避慕釜蘇芝翅析蓋舌扇晰現(xiàn)夾燭竅悠煙鼠潤涕義拆尖悠誰謹傲遷淫走殿計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章圖3.2進程上下文結構痔垛呀箍翔煮疲峪黑燒鍛爾啃迂編印趣鎢僳抑睹階汁險拂四池飾即祭凜滑計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章進程上下文可按一定的執(zhí)行層次組合，例如用戶級上下文、系統(tǒng)級上下文等。顯然，一個進程的執(zhí)行是在該進程的上下文中執(zhí)行，而當系統(tǒng)調(diào)度新進程占有處理機時，新老進程的上下文發(fā)生轉換。在UNIXSystemⅤ中，進程上下文由用戶級上下文、寄存器上下文以及系統(tǒng)級上下文組成。用戶級上下文由進程的用戶程序段部分編譯而成的用戶正文段、用戶數(shù)據(jù)、用戶棧等組成。而寄存器上下文則由程序寄存器PC、處理機狀態(tài)字寄存器PS、棧指針和通用寄存器的值組成。其中PC給出CPU將要執(zhí)行的下條指令的虛地址；PS給出機器與該進程相關聯(lián)時的硬件狀態(tài)，例如當前執(zhí)行模式、能否執(zhí)行特權指令等；棧指針指向下一項的當前地址，而通用寄存器則用于不同執(zhí)行模式之間的參數(shù)傳遞等。飲閡杭館桅儈抵案炭闊孜眨凈晃家狄泊烴癰貨勝齲蛤炬甫泉共德鋇餌拌椒計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章進程的系統(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)調(diào)用的調(diào)用序列。系統(tǒng)級上下文的動態(tài)部分是與寄存器上下文相關聯(lián)的。進程上下文的層次概念也主要體現(xiàn)在動態(tài)部分中，即系統(tǒng)級上下文的動態(tài)部分可看成是一些數(shù)量變化的層次組成。其變化規(guī)則滿足先進后出的堆棧方式，每個上下文層次在棧中各占一項。UNIXSystemⅤ的進程上下文組成如圖3.3。則跳搖咎畢龍吁研趙還豫霍擦謅晨遇膛蠢等頁水茬筒顱哭彼莽撿秋乙扁俱計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章圖3.3UNIXSystemⅤ進程上下文組成扔剮舷狙栓畦仔刁宇核皇壘補徒屏諜廈蕩助錦灰掀惱應她傻流蠟促烈圍綻計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.2.3進程空間任一進程，都有一個自己的地址空間，把該空間稱為進程空間或虛空間。進程空間的大小只與處理機的位數(shù)有關。在UNIX以及Linux等操作系統(tǒng)中，進程空間還被劃分為用戶空間和系統(tǒng)空間兩大部分。在進程空間被劃分為兩大部分后，用戶程序在用戶空間內(nèi)執(zhí)行，而操作系統(tǒng)內(nèi)核程序則在進程的系統(tǒng)空間內(nèi)執(zhí)行。為防止用戶程序訪問系統(tǒng)空間，造成訪問出錯，系統(tǒng)通過程序狀態(tài)寄存器等設置不同的執(zhí)行模式，即用戶模式和系統(tǒng)模式來進行保護。

兆字巋征媚惰盛敵酷蓉跳豈鑄陳念檔撬瞞腔疏蹭挺無錨滿撣侶傘艾勢閻擂計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.3進程狀態(tài)及其轉換3.3.1進程狀態(tài)一個進程的生命期可以劃分為一組狀態(tài)，這些狀態(tài)刻劃了整個進程。系統(tǒng)根據(jù)PCB結構中的狀態(tài)值控制進程。在進程的生命期內(nèi)，一個進程至少具有三種基本狀態(tài)，它們是：執(zhí)行狀態(tài)、等待狀態(tài)和就緒狀態(tài)。處于就緒狀態(tài)的進程已經(jīng)得到除CPU之外的其他資源，只要由調(diào)度得到處理機，便可立即投入執(zhí)行。國返糯元梆琵沸唇謬誘栓蔚刑運珊醞緝秧沒聘挨糙演蜒甭則筍織符咯紀駱計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章在有些系統(tǒng)中，為了有效地利用內(nèi)存，就緒狀態(tài)又可進一步分為內(nèi)存就緒狀態(tài)和外存就緒狀態(tài)。在這樣的系統(tǒng)中，只有處于內(nèi)存就緒狀態(tài)的進程在得到處理機后才能立即投入執(zhí)行。而處于外存就緒狀態(tài)的進程只有先成為內(nèi)存就緒狀態(tài)后，才可能被調(diào)度執(zhí)行。這種方式明顯地提高了內(nèi)存的利用效率，但反過來也增加了系統(tǒng)開銷和系統(tǒng)復雜性。在單CPU系統(tǒng)中，任一時刻處于執(zhí)行狀態(tài)的進程只能有一個。只有處于就緒狀態(tài)的進程經(jīng)調(diào)度選中之后才可進入執(zhí)行狀態(tài)。咋施始械淋泡隘勘膳籃莖纖掂妊猶趙憑書租彥裴隸伎丹貧瞞背曠旱幀式禁計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章在某些操作系統(tǒng)中，一個進程在其生命期內(nèi)的執(zhí)行過程中，總要涉及到用戶程序和操作系統(tǒng)內(nèi)核程序兩部分。因此，進程的執(zhí)行狀態(tài)又可進一步劃分為用戶執(zhí)行狀態(tài)和系統(tǒng)執(zhí)行狀態(tài)。劃分用戶態(tài)和系統(tǒng)態(tài)最主要的原因是要把用戶程序和系統(tǒng)程序區(qū)分開來，以利于程序的共享和保護。顯然，這也是以增加系統(tǒng)復雜度和系統(tǒng)開銷為代價的。進程因等待某個事件發(fā)生而放棄處理機進入等待狀態(tài)。顯然，等待狀態(tài)可根據(jù)等待事件的種類而進一步劃分為不同的子狀態(tài)，例如內(nèi)存等待、設備等待、文件等待和數(shù)據(jù)等待等。這樣做的好處是系統(tǒng)控制簡單，發(fā)現(xiàn)和喚醒相應的進程較為容易。但系統(tǒng)中設置過多的狀態(tài)又會造成系統(tǒng)參數(shù)和狀態(tài)轉換過程的增加。她熾蜜孵裴襪如淀咆洲阿拿貞蔫橡捕就糾谷迄閉柯裸恍鈔簍潔粥勉鑲詞粹計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.3.2進程狀態(tài)轉換進程的狀態(tài)反映進程執(zhí)行過程的變化。這些狀態(tài)隨著進程的執(zhí)行和外界條件發(fā)生變化和轉換。那么，是什么樣的條件使得進程各狀態(tài)發(fā)生轉換呢？示圖給出了三個基本狀態(tài)，即就緒狀態(tài)、執(zhí)行狀態(tài)與等待狀態(tài)之間的轉換關系。事實上，進程的狀態(tài)轉換是一個非常復雜的過程。從一個狀態(tài)到另一個狀態(tài)的轉換除了要使用不同的控制過程（將在下節(jié)中講述），有時還要借助于硬件觸發(fā)器才能完成。例如，在UNIX系統(tǒng)中，從系統(tǒng)態(tài)到用戶態(tài)的轉換要借助硬件觸發(fā)器完成。裳輯快偏雹墑僧遠謾受魁余泥乙神沿玲往刊椿橇怖毖崩險斧撾駕奢蠕柵鹵計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章進程狀態(tài)轉換圖筏柞傈牙優(yōu)堡照繩裳桐叔宣京兼牌接殷丁末枕舔概粱抬佰成寂乃袱強施邢計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.4進程控制進程和處理機管理的一個重要任務是進程控制。所謂進程控制，就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進程以及完成進程各狀態(tài)間的轉換，從而達到多進程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實現(xiàn)資源共享的目的。一般地，把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。原語可分為兩類：一類是機器指令級的，其特點是執(zhí)行期間不允許中斷。另一類是功能級的，其特點是作為原語的程序段不允許并發(fā)執(zhí)行。這兩類原語都在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個系統(tǒng)管理所需要的功能和被高層軟件所調(diào)用。斃頂儡迷趨娟納抹糠亡薦刮鋸銜內(nèi)帝插進崔誓滌涯版貞南丈覺翻亨算瑤秉計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章顯然，系統(tǒng)在創(chuàng)建、撤消一個進程以及要改變進程的狀態(tài)時，都要調(diào)用相應的程序段來完成這些功能。那么，這些程序段是不是原語呢？如果它們不是原語，則由上述原語的定義可知，這些程序段是允許并發(fā)執(zhí)行的。然而，如果不加控制和管理地讓這些控制進程狀態(tài)轉換及創(chuàng)建和撤消進程的程序段并發(fā)執(zhí)行，則會使得其執(zhí)行結果失去封閉性和可再現(xiàn)性，從而達不到進程控制的目的。反過來，如果對這些程序段采用下面章節(jié)中所述的控制方法使其在并發(fā)執(zhí)行過程中也能完成進程控制任務的話，將會大大增加系統(tǒng)的開銷和復雜度。因此，在操作系統(tǒng)中，通常把進程控制用程序段做成原語。用于進程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。午剃池咒坡侮柴論犧癥輸罕糯適蛀虐尿群卑索諾隱燈睬撫竹埃譏糜劊昭烏計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.4.1進程創(chuàng)建與撤消1.進程創(chuàng)建(1)由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建，例如在批處理系統(tǒng)中，由操作系統(tǒng)的作業(yè)調(diào)度程序為用戶作業(yè)創(chuàng)建相應的進程以完成用戶作業(yè)所要求的功能。(2)由父進程創(chuàng)建，例如在層次結構的系統(tǒng)中，父進程創(chuàng)建子進程以完成并行工作。由系統(tǒng)統(tǒng)一創(chuàng)建的進程之間的關系是平等的，它們之間一般不存在資源繼承關系。而在父進程創(chuàng)建的進程之間則存在隸屬關系，且互相構成樹型結構的家族關系。屬于某個家族的一個進程可以繼承其父進程所擁有的資源。另外，無論是哪一種方式創(chuàng)建進程，在系統(tǒng)生成時，都必須由操作系統(tǒng)創(chuàng)建一部分承擔系統(tǒng)資源分配和管理工作的系統(tǒng)進程。奄懷鉤秦譏濾夜碑蹈輥班滴普舷針祝賂隊刁盯妹劈豈范末梧或券碼舍廓市計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章無論是系統(tǒng)創(chuàng)建方式還是父進程創(chuàng)建方式，都必須調(diào)用創(chuàng)建原語來實現(xiàn)。2.進程撤消以下幾種情況導致進程被撤消：(1)該進程已完成所要求的功能而正常終止。(2)由于某種錯誤導致非正常終止。(3)祖先進程要求撤消某個子進程。采鬃承案炒壘窗這菊纂本鎢傘忱雇饒?zhí)ぴ丿B慚千聾奔銀簡錯面伺蜘淚鬃計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章無論哪一種情況導致進程被撤消，進程都必須釋放它所占用的各種資源和PCB結構本身，以利于資源的有效利用。另外，當一個祖先進程撤消某個子進程時，還需審查該子進程是否還有自己的子孫進程，若有的話，還需撤消其子孫進程的PCB結構和釋放它們所占有的資源。撤消原語首先檢查PCB進程鏈或進程家族，尋找所要撤消的進程是否存在。如果找到了所要撤消的進程的PCB結構，則撤消原語釋放該進程所占有的資源之后，把對應的PCB結構從進程鏈或進程家族中摘下并返回給PCB空隊列。如果被撤消的進程有自己的子進程，則撤消原語先撤消其子進程的PCB結構并釋放子進程所占用的資源之后，再撤消當前進程的PCB結構和釋放其資源。趣炸喉殃窿窩歪奪蛛戮舵呼票廖嗓婆凝慮苞寶從連丙剝購竄膏麥違抹糾杜計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.4.2進程的阻塞與喚醒進程的創(chuàng)建原語和撤消原語完成了進程從無到有，從存在到消亡的變化。被創(chuàng)建后的進程最初處于就緒狀態(tài)，然后經(jīng)調(diào)度程序選中后進入執(zhí)行狀態(tài)。這里主要介紹實現(xiàn)進程的執(zhí)行狀態(tài)到等待狀態(tài)，又由等待狀態(tài)到就緒狀態(tài)轉換的兩種原語，即阻塞原語與喚醒原語。阻塞原語在一個進程期待某一事件發(fā)生，但發(fā)生條件尚不具備時，被該進程自己調(diào)用來阻塞自己。阻塞原語在阻塞一個進程時，由于該進程正處于執(zhí)行狀態(tài)，故應先中斷處理機和保存該進程的CPU現(xiàn)場。然后將被阻塞進程置“阻塞”狀態(tài)后插入等待隊列中，再轉進程調(diào)度程序選擇新的就緒進程投入運行。阻塞原語的實現(xiàn)過程如圖。濫足規(guī)盛吻港籍奄妒郝贈訛拋牲龍髓駿踢止蝸泉禹嘛棲各曾疇攣赴篙瘁慶計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章這里，轉進程調(diào)度程序是很重要的，否則，處理機將會出現(xiàn)空轉而浪費資源。阻塞原語圖趟垢簾甚疏霧猜鋸啊涎辯素嵌螞杯況抹嘗瓤罰虎嚎鞭禮弦瑟馭吸屋蝕甜矣計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章當?shù)却犃兄械倪M程所等待的事件發(fā)生時，等待該事件的所有進程都將被喚醒。喚醒一個進程有兩種方法：一種是由系統(tǒng)進程喚醒。另一種是由事件發(fā)生進程喚醒。當由系統(tǒng)進程喚醒等待進程時，系統(tǒng)進程統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進程。從而使得該進程因等待事件已發(fā)生而進入就緒隊列。由事件發(fā)生進程喚醒時，事件發(fā)生進程和被喚醒進程之間是合作關系。因此，喚醒原語既可被系統(tǒng)進程調(diào)用，也可被事件發(fā)生進程調(diào)用。稱調(diào)用喚醒原語的進程為喚醒進程。喚醒原語首先將被喚醒進程從相應的等待隊列中摘下，將被喚醒進程置為就緒狀態(tài)之后，送入就緒隊列。在把被喚醒進程送入就緒隊列之后，喚醒原語既可以返回原調(diào)用程序，也可以轉向進程調(diào)度，以便讓調(diào)度程序有機會選擇一個合適的進程執(zhí)行。如圖：攫稽毫斥戌梗寐砒胸把眉疤棘蝴漱忌跺殖臼仁六話墟?zhèn)兿x拉牙報揚虱超表計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章喚醒原語圖領溢懶潑滓艙纂勺紳姻潛窮蓑疽賢驕游獺漁版筏島何場閥酶涵負袱燦駐茄計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.5進程互斥3.5.1資源共享所引起的制約進程的并發(fā)執(zhí)行不僅僅是用戶程序的執(zhí)行開始時間的隨機性和提高資源利用率的結果，也是資源有限性導致資源的競爭與共享對進程的執(zhí)行過程進行制約所造成的。1.臨界區(qū)在描述一個程序或算法時，總是認為存在一個偽處理機，可以按程序或算法所規(guī)定的步驟來執(zhí)行該程序或算法的。但是，事實上，在實際的系統(tǒng)中則往往不是這樣。一般說來，即使在程序中所描述的一條語句，也是由多條執(zhí)行指令構成的。例如，各種程序中經(jīng)常出現(xiàn)的賦值語句： X=X+1；歌市竄條熏駝笨拼下姐磚查菏敘釋葦論殘兇誘矩拉窟劊埋誣舔努條灌瘍姑計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章在用匯編語言書寫時，就變成： LOADA，X ADDIA，1 STOREA，X 等三條語句，這里A代表累加器。根據(jù)系統(tǒng)的設計和要求，在這三條語句的執(zhí)行期間，也有可能發(fā)生中斷或調(diào)度，從而使得與當前進程無關的程序得以執(zhí)行。為了保證程序執(zhí)行最終結果的正確性，必須對并發(fā)執(zhí)行的各進程進行制約，以控制它們的執(zhí)行速度和對資源的競爭。在進程的概念一節(jié)中已經(jīng)介紹了進程中兩相鄰語句可并發(fā)執(zhí)行的三個條件。是否有一種更為簡單的辦法來檢查出需要對程序的哪些部分進行制約才能保證其執(zhí)行結果的正確性呢？這里來看下面的例子。矩稱害砍麻腳索舉拂卷太霖躇緒醬托兢戊起惹略而寞陵跑閩們矢斷伎禾夜計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章設有兩個計算進程ＰA，ＰB共享內(nèi)存ＭS。其中ＭS分為三個領域，即系統(tǒng)區(qū)、進程工作區(qū)和數(shù)據(jù)區(qū)。這里數(shù)據(jù)區(qū)被劃分大小相等的塊，每個塊中既可能放有數(shù)據(jù)，也有可能未放有數(shù)據(jù)。系統(tǒng)區(qū)主要是堆棧Ｓ，其中存放那些空數(shù)據(jù)塊的地址。多進程共享內(nèi)存棧區(qū)示例圖憋拜噸繃畸槳招纏茫褲添苞啃騷偶丁瑣俞奠塞錢紉蠶嫁僚遜帛哦效恨渣小計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章當進程Ｐ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)可進一步描述為：欣隴膳鑲朗簇廢郁服僧瞞沼哭應披臂桔體昂哎黔眼柄本訪饅潔鵬巋庶膩凳計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 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í)行，得：肯鶴席吟仲趴晨蒙戎也墨晦籌建喪朋酌岡慫鈕糜皺蕩惜戀均飲棧汾鳴須擊計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 t1：g←stack［top］→ g=stack［h0+1］； t2：top←top-1 → top=h0；再是release(ad)的第二句執(zhí)行，得： t3：stack［top］←ad→ stack［h0］←ad；其結果是調(diào)用getspace的進程取到的是h0+1中的一個未定義值，而調(diào)用release(ad)的進程把所釋放的空塊地址ad重復放入了h0中。怎樣保證上述執(zhí)行結果的正確性呢？一個較為明顯的答案是，如果把getspace和release(ad)抽象為兩個各以一個動作完成的順序執(zhí)行單位，那么執(zhí)行結果的正確性是可以保證的。策姐鋤桶鱉它噸尿憊汕速阿六鯨仲光工侍藥滋虜預狐弟恥誘遏固士函沁干計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章把不允許多個并發(fā)進程交叉執(zhí)行的一段程序稱為臨界部分（criticalsection）或臨界區(qū)（criticalregion）。臨界區(qū)是由屬于不同并發(fā)進程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的，例如上例中就是因為過程getspace和release(ad)共同訪問棧Ｓ中的數(shù)據(jù)而引起的。臨界區(qū)不可能用增加硬件的方法來解決。因此，臨界區(qū)也可以被稱為訪問公用數(shù)據(jù)的那段程序。渠同應苞劃招它屯繡拙訴帕寫性秧嶼治粱埂停鰓弧咒相頃掘屬網(wǎng)聊堅禾刺計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章2.間接制約一般來說，可以把那些不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的集合。上例中，以公用數(shù)據(jù)棧Ｓ劃分的臨界區(qū)集合是{getspace,release}。把這些集合稱為類（class）。顯然，對類給定一個唯一的標識名，系統(tǒng)就會容易地區(qū)分它們。在程序的描述中，可用下列標準形式來描述臨界區(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弓糯盤軌作嚏吭咯鐮芝隴旦渦瘍衰偉秧霧紛但旁毅俘捧椎含忙狀八攏贍代計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章把這種由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對并發(fā)進程執(zhí)行速度的間接制約，簡稱間接制約。這里，“間接”二字主要是指各并發(fā)進程的速度受公有資源制約，而不是進程間直接制約的意思。這里，受間接制約的類中各程序段在執(zhí)行順序上是任意的。顯然，對于每一類，系統(tǒng)應有相應的分配和釋放相應公有資源的管理辦法，以制約并發(fā)進程。這就是互斥。酚宰獻擇嘴鑷度蚤著姨陷書杏繡傳冒柳妮闡雌計遞僻滄裴測霓對耶胃媳汪計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.什么是互斥可以把互斥定義為：一組并發(fā)進程中的一個或多個程序段，因共享某一公有資源而導致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)稱為互斥。這里，考慮類中只有一個元素，也就是只有一個程序段的情況是很有意思的。這時程序段本身為公有資源被并發(fā)進程共享。一般情況下，作為程序段的一個過程不允許多個進程共同訪問它。但如果該過程是純過程，則各并發(fā)進程可以同時訪問它。純過程是指在執(zhí)行過程中不改變過程自身代碼的一類過程。糾枚怨恕型的模哥枚肥標書嘻硒格拳矢旱窮駛抓窯年別浴握諄沿算滿瞄消計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章通常，在計算機系統(tǒng)中，有許多過程是被多個并發(fā)進程同時訪問共享，例如編輯程序、編譯程序等。把一個過程作成純過程可便于多個進程共享，但由于編制純過程必須對有關變量和工作區(qū)作相應的處理，從而其執(zhí)行效率往往會受到一定的影響。一組并發(fā)進程互斥執(zhí)行時必須滿足如下準則：(1)不能假設各并發(fā)進程的相對執(zhí)行速度。即各并發(fā)進程享有平等的、獨立的競爭共有資源的權利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結束時，其他并發(fā)進程可以進入臨界區(qū)。(2)并發(fā)進程中的某個進程不在臨界區(qū)時，它不阻止其他進程進入臨界區(qū)。(3)并發(fā)進程中的若干個進程申請進入臨界區(qū)時，只能允許一個進程進入。選毯巍掇砌漫咱糊猙按廠的淚朋句系滾費茶櫥勛專揚圣攣罷嗚誼依舀錄鹼計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章(4)并發(fā)進程中的某個進程申請進入臨界區(qū)時開始，應在有限時間內(nèi)得以進入臨界區(qū)。這里，準則(1)，(2)，(3)是保證各并發(fā)進程享有平等的、獨立的競爭和使用公有資源的權利，且保證每一時刻至多只有一個進程在臨界區(qū)。而準則(4)則是并發(fā)進程不發(fā)生死鎖（將在后面講述）的重要保證。否則，由于某個并發(fā)進程長期占有臨界區(qū)，其他進程則因為不能進入臨界區(qū)而進入互相等待狀態(tài)。在一組并發(fā)執(zhí)行進程中，除了因為競爭公有資源而引起的間接制約帶來進程之間互斥之外，還存在有因為并發(fā)進程互相共享對方的私有資源所引起的直接制約。直接制約將使得各并發(fā)進程同步執(zhí)行。下面，將討論互斥的實現(xiàn)方法。捶汀伶員雪君撥胖拔莉碩羅鼻舒印略邪仲尺茹丘銻劊屜霞顫沂掉烯鄭潮伙計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.5.2互斥的加鎖實現(xiàn)上節(jié)中，給出了臨界區(qū)的描述方法和并發(fā)進程互斥執(zhí)行時所必要遵守的準則。但是，并沒有給出怎樣實現(xiàn)并發(fā)進程的互斥。人們可能認為只需把臨界區(qū)中的各個過程按不同的時間排列調(diào)用就行了。但事實上這是不可能的。因為這要求該組并發(fā)進程中的每個進程事先知道其他并發(fā)進程與系統(tǒng)的動作，由用戶程序執(zhí)行開始的隨機性可知，這是不可能的。一種可能的辦法是對臨界區(qū)加鎖以實現(xiàn)互斥。當某個進程進入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進程在申請進入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)。身扶躇昧愉獲年廉恬召瘴嗣皚玄俗繞企鼻屜恬袖鈔都俊曙蕉貫贏錯英滴始計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章設臨界區(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)起來較為困難。臭卉廷瘤定戲坑稿遂今號扼尊貨葬屠察憊租狠咳帛贊巫勸伎奠便頹紳陀巴計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章一種簡便的實現(xiàn)方法是： lock(x)=beginlocalv repeat v←x untilv=1 x←0 end這種實現(xiàn)方法是不能保證并發(fā)進程互斥執(zhí)行所要求的準則(3)的。因為當同時有幾個進程調(diào)用lock(key［Ｓ］)時，在x←0語句執(zhí)行之前，可能已有兩個以上的多個進程由于key［Ｓ］=1而進入臨界區(qū)。為解決這個問題有些機器在硬件中設置了“測試與設置指令，保證第一步和第二步執(zhí)行不可分離。注意：在系統(tǒng)實現(xiàn)時鎖定位key［Ｓ］總是設置在公有資源所對應的數(shù)據(jù)結構中的。舅墳銘望賠嗎肌擲點繪廄飯瘟拋成則蕾纖帽侈諒纖匠垮輛蹋購鋤瑚挾廉要計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.5.3信號量和Ｐ，Ｖ原語1.信號量（semaphore）盡管用加鎖的方法可以實現(xiàn)進程之間的互斥，但這種方法仍然存在一些影響系統(tǒng)可靠性和執(zhí)行效率的問題。例如，循環(huán)測試鎖定位將損耗較多的CPU計算時間。如果一組并發(fā)進程的進程數(shù)較多，且由于每個進程在申請進入臨界區(qū)時都得對鎖定位進行測試，這種開銷是很大的。另外，使用加鎖法實現(xiàn)進程間互斥時，還將導致在某些情況下出現(xiàn)不公平現(xiàn)象。試考慮以下進程PA和PB反復使用臨界區(qū)的情況： PA A：lock(key［Ｓ］) 〈Ｓ〉縣齡稈飲容肌孺災蛛店腕僧鳥吩均訃綿淑蕪坯駱鐳蜘揭案奮癌虧只嘎澆揉計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 unlock(key［Ｓ］) GotoA PB B：lock(key［Ｓ］) ＜Ｓ＞ unlock(key［Ｓ］) GotoB設進程ＰA已通過lock(key［Ｓ］)過程而進入臨界區(qū)。顯然，在進程PA執(zhí)行unlock(key［Ｓ］)過程之前，key［Ｓ］=0且進程PB沒有進入臨界區(qū)的機會。然而，當進程PA執(zhí)行完unlock(key［Ｓ］)過程之后，由于緊接著是一轉向語句，進程PA將又立即去執(zhí)行l(wèi)ock(key［Ｓ］)過程。愧涅潮屑旱燼隴非呸弄嗚磺煎銜鹵錢墊幅婆溜賣娟紋饅挫燕窩灶瞳閃烤雪計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章此時，由于unlock(key［Ｓ］)過程已將key［Ｓ］的值置為1，也就是開鎖狀態(tài)，從而進程PA又可進入臨界區(qū)Ｓ。只有在進程PA執(zhí)行完unlock(key［Ｓ］)過程之后、執(zhí)行GotoA語句之前的瞬間發(fā)生進程調(diào)度，使進程PA把處理機轉讓給進程PB，進程PB才有可能得到執(zhí)行。然而遺憾的是，這種可能性是非常小的。因此，進程PB將處于永久饑餓狀態(tài)（starvation）。解決上述問題首先必須找到產(chǎn)生問題的原因。顯然，在用加鎖法解決進程互斥的問題時，一個進程能否進入臨界區(qū)是依靠進程自己調(diào)用lock過程去測試相應的鎖定位。每個進程能否進入臨界區(qū)是依靠自己的測試判斷。這樣沒有獲得執(zhí)行機會的進程當然無法判斷，從而出現(xiàn)不公平現(xiàn)象。而獲得了測試機會的進程又因需要測試而損失一定的CPU時間。剎唁曳旬鎬沈感術吼哭決扣辛柑酮鐮被底沛豺軸樓謠榷駱蒼粘灣隙有澳闊計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章這正如某個學生想使用某個人人都可借用、且不規(guī)定使用時間的教室時一樣，他必須首先申請獲得使用該教室的權利，然后再到教室看看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復將持續(xù)到他進門后為止。從這個例子中，可以得到解決加鎖法所帶來的問題的方法。一種最直觀的辦法是，設置一個教室管理員。從而，如果有學生申請使用教室而未能如愿時，教室管理員記下他的名字，并等到教室門一打開則通知該學生進入。這樣，既減少了學生多次來去教室檢查門是否被打開的時間，又減少了因為學生自發(fā)地檢查造成的不公平現(xiàn)象。在操作系統(tǒng)中，這個管理員就是信號量。信號量管理相應臨界區(qū)的公有資源，它代表可用資源實體。謊軒鯨疽窩訴晾伍妄啊棒格湃峽閻炎宦瘟罐遺吭锨魔凰盧韋酒撐見巋唬舜計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章信號量的概念和下面所述的Ｐ、Ｖ原語是荷蘭科學家E.W.Dijkstra提出來的。信號是鐵路交通管理中的一種常用設備，交通管理人員利用信號顏色的變化來實現(xiàn)交通管理。在操作系統(tǒng)中，信號量sem是一整數(shù)。在sem大于等于零時代表可供并發(fā)進程使用的資源實體數(shù)，但sem小于零時則表示正在等待使用臨界區(qū)的進程數(shù)。顯然，用于互斥的信號量sem的初值應該大于零，而建立一個信號量必須經(jīng)過說明所建信號量所代表的意義，和賦初值以及建立相應的數(shù)據(jù)結構以便指向那些等待使用該臨界區(qū)的進程。雙卡魄農(nóng)篡任措疚悼義響閣耗焙壺陳抑團順應青甄腺閡灑懸氟荔有脅亢脅計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章2.Ｐ，Ｖ原語信號量的數(shù)值僅能由Ｐ，Ｖ原語操作改變(Ｐ和Ｖ分別是荷蘭語Passeren和Verhoog的頭一個字母，相當于英文的pass和increment的意思)。采用Ｐ，Ｖ原語，可以把類名為Ｓ的臨界區(qū)描述為WhenＳdoＰ(sem)臨界區(qū)Ｖ(sem)od。這里，sem是與臨界區(qū)內(nèi)所使用的公用資源有關的信號量。一次Ｐ原語操作使得信號量sem減1，而一次Ｖ原語操作將使得信號量sem加1。必須強調(diào)的一點是，當某個進程正在臨界區(qū)內(nèi)執(zhí)行時，其他進程如果執(zhí)行了Ｐ原語操作，則該進程并不像調(diào)用lock時那樣因進不了臨界區(qū)而返回到lock的起點，等以后重新執(zhí)行測試，而是在等待隊列中等待有其他進程做Ｖ原語操作釋放資源后，進入臨界區(qū)，這時，Ｐ原語的執(zhí)行才算真正結束。毆仍闡續(xù)領憚油尺蔥柿傳扶惡謀庫司益敢揍羅大拍屑叭喇瞅韌踩熾看論沛計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章另外，當有好幾個進程執(zhí)行Ｐ原語未通過而進入等待狀態(tài)之后，如有某進程作了Ｖ原語操作，則等待進程中的一個可以進入臨界區(qū)，但其他進程必須等待。Ｐ原語操作的主要動作是：(1)sem減1；(2)若sem減1后仍大于或等于零，則進程繼續(xù)執(zhí)行；(3)若sem減1后小于零，則該進程被阻塞后與該信號相對應的隊列中，然后轉進程調(diào)度。Ｐ原語操作的功能框圖如圖3.11。搭涵褐伺薄狗慶瞅穴胃軟四孰祿焦肺誡糊膀娥騾洶詭押妊灸壹到掉綠雌標計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章圖3.11Ｐ原語操作功能 圖3.12Ｖ原語操作功能戌與弄妖憎削專叼直暑皂嗓豎耶棱艇圣邢榨托誓蠻拇雞哇鎳偷隱瘩簇恒頻計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章Ｖ原語的操作主要動作是：(1)sem加1；(2)若相加結果大于零，進程繼續(xù)執(zhí)行；(3)若相加結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉進程調(diào)度。Ｖ原語操作的功能框圖如圖3.12。有了加鎖法的基礎，大家應該明白為什么Ｐ，Ｖ過程要以原語實現(xiàn)的原因。否則，如果多個進程同時調(diào)用Ｐ操作或Ｖ操作的話，則有可能在Ｐ操作剛把sem-1而未把對應進程送入等待隊列時，Ｖ操作開始執(zhí)行。從而，Ｖ操作將無法發(fā)現(xiàn)等待進程而返回。因此，Ｐ，Ｖ操作都必須以原語實現(xiàn)，且在Ｐ，Ｖ原語執(zhí)行期間不允許中斷發(fā)生。蜂葫狠怎爐兌踞潘呻儈馮絞俄咖窄蝴蟹挽漳溪騰米怖繕竭炙緘迸匡翁吼志計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章關于Ｐ，Ｖ原語的實現(xiàn)，有許多方法。這里介紹一種使用加鎖法的軟件實現(xiàn)方法，實現(xiàn)過程描述如下： Ｐ（sem）： begin 封鎖中斷； lock(lockbit) val［sem］=val［sem］-1 ifval［sem］<0 保護當前進程CPU現(xiàn)場 當前進程狀態(tài)置為″等待″ 將當前進程插入信號sem等待隊列 轉進程調(diào)度 fi unlock(lockbit)；開放中斷 end喲同斟墓敖持肩匡氟凸鵝散仿闊瓤羊砂損刃泌躲立掏馳柳瘓充氮沏肇記舍計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章Ｖ（sem）： begin 封鎖中斷； lock(lockbit) va［sem］=val［sem］+1 ifval［sem］≤0 localk 從sem等待隊列中選取一等待進程，將其指針置入k中 將k插入就緒隊列 進程狀態(tài)置“就緒” fi unlock(lockbit)；開放中斷end碌轅慘膏顱刺拒間渾樞毖硒白禍囚肩茬盼氣器藤邀柔枉看夾忘生漫滴咕匙計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.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ū)。崖?lián)富I讀規(guī)質(zhì)遂伎涯拿慶磚簇閉惜似墓蹈劃顏丙骸按恨薯沈繡祝窘孟餡票計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章在該進程未執(zhí)行Ｖ原語操作之前如有另一進程想進入臨界區(qū)的話，它也應先執(zhí)行Ｐ原語操作，從而使sem的值變?yōu)?1，因此，第二個進程將被阻塞。直到第一個進程執(zhí)行Ｖ原語操作之后，sem的值變?yōu)?，從而可喚醒第二個進程進入就緒隊列，經(jīng)調(diào)度后再進入臨界區(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ū)。倉漲失扁披桔毗初寂育李頃韓育衫穩(wěn)擴丈厚字矽揀磕妹肛度妥畏樁嫡伐駁計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章2)描述： PA： Ｐ(sem) 〈Ｓ〉 Ｖ(sem)： ： ：

PB： Ｐ(sem) 〈Ｓ〉 Ｖ(sem)∷ ： ：鉻甘鞭商炕竿溺眶妊違讀祟姐盧躺冷營上頂頰咒八凈投喂者虎柴概蠢稈忘計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章吸晤禍婿樓挎倦皮殃爸疊霸診如羚越褪繞潑酉沖有新嗆民擺烴墮侄猶譏娩計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.6進程同步3.6.1同步的概念除了對公有資源的競爭而引起的間接制約之外，并發(fā)進程之間是否還存在著其他制約關系影響執(zhí)行速度呢？來看下面的例子。計算進程和打印進程共同使用同一緩沖區(qū)Buf。計算進程反復地把每次計算結果放入Buf中，而打印進程則把計算進程每次放入Buf中的數(shù)據(jù)通過打印機打印輸出。如果不采取任何制約措施，這兩個進程的執(zhí)行起始時間和執(zhí)行速度都是彼此獨立的，其相應的控制段可以描述為：蟻瞧呆陶反呈椒樓值剿苗餾標魂正舅芝求死呆排簍遮劈馭君都矛蹭究蛆卻計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章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衍沒守據(jù)程冤毫丈壕殷讓穢鋪旋朱毀喂菇蹈祭體魚科雁硒不蟲峭屆筒蚊始計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章這里，如果假定進程PC和PP對公用緩沖區(qū)Buf已采取了互斥措施。顯然，如果按上面的描述并發(fā)執(zhí)行進程PA和PB的話，則會造成CPU時間的極大浪費（因為其中包含有二處反復測試語句）。這是操作系統(tǒng)設計要求不允許的。CPU時間的浪費主要是由于進程PA和PB的執(zhí)行互相制約所引起的。PA的輸出結果是PB的執(zhí)行條件，反過來，PB的執(zhí)行結果也是PA的執(zhí)行條件。這種現(xiàn)象在操作系統(tǒng)和用戶進程中大量存在。這與上節(jié)中講述的進程互斥是不同的，進程互斥時它們的執(zhí)行順序可以是任意的。一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程稱為并發(fā)進程間的直接制約。毒健摧弧紫遏秘化全袱汀模疏擲沫評藏紐拆乾搔恢柒卒淖妻盾瓢薪鉸他抿計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章這里異步環(huán)境主要指各并發(fā)進程的執(zhí)行起始時間的隨機性和執(zhí)行速度的獨立性。正如在上面例子中所看到的那樣，如果沒有相應的解決方法，進程的直接制約將會造成大量的CPU時間浪費。一種最為簡單和直觀的方法是直接制約的進程互相給對方進程發(fā)送執(zhí)行條件已經(jīng)具備的信號。這樣，被制約進程即可省去對執(zhí)行條件的測試，只要收到了制約進程發(fā)來的信號便開始執(zhí)行，而在未收到制約進程發(fā)來的信號時便進入等待狀態(tài)。誅陽卜酬末苦往曼未養(yǎng)砌啡泵鴻姆拎魄孺要撕秒鄲貴榴頤俏嫡激扇裔志漢計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章把異步環(huán)境下的一組并發(fā)進程，因直接制約而互相發(fā)送消息而進行互相合作、互相等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步。具有同步關系的一組并發(fā)進程稱為合作進程，合作進程間互相發(fā)送的信號稱為消息或事件。如果對一個消息或事件賦以唯一的消息名，則可用過程 wait(消息名）表示進程等待合作進程發(fā)來的消息，而用過程 signal（消息名）表示向合作進程發(fā)送消息。利用過程wait和signal，可以簡單地描述上面例子中的計算進程PA和打印進程PB的同步關系如下：輸淳戒崔惱陵維礬漲援生擰醋呈耿徊尿姥維怒葫自匆閡廣沃垃攝帆風蛇老計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章(1)設消息名Bufempty表示Buf空，消息名Buffull表示Buf中裝滿了數(shù)據(jù)。(2)初始化Bufempty=true，Buffull=false。(3)描述： PA ： A: wait(Bufempty) 計算 Buf←計算結果 signal(Buffull) Goto A汗乎踢寬雨魚蛀迂賈贛哄掀廣睫蚤呢奈簡耗兄踐僳鍋偷崗摟麥掛埋盛藉營計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 PB ： B: wait(Buffull) 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù) signal(Bufempty) Goto B過程wait的功能是等待到消息名為true的進程繼續(xù)執(zhí)行，而signal的功能則是向合作進程發(fā)送合作進程所需要的消息名，并將其值置為true。喚肺桑檻誣婦卑毒脂輛忌遞弘殼屜關藏謹頭瞥灰堿樹鎂寺貝恢橡酚柜腎更計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.6.2私用信號量上面用wait（消息名）與signal（消息名）的方式，描述了進程同步的一種實現(xiàn)方法。事實上，使用信號量的方法也可實現(xiàn)進程間的同步。一般來說，也可以把各進程之間發(fā)送的消息作為信號量看待。與進程互斥時不同的是，這里的信號量只與制約進程及被制約進程有關而不是與整組并發(fā)進程有關。因此，稱該信號量為私用信號量（PrivateSemaphvre）。一個進程Pi的私用信號量Semi是從制約進程發(fā)送來的進程Pi的執(zhí)行條件所需要的消息。與私用信號量相對應，稱互斥時使用的信號量為公用信號量。儡核懈棋品彪到拙花兔?；涡贤窗泐H祭潰嗓檬暇師琵舔捧普佛鼓疥衫穆甜計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.6.3用Ｐ，Ｖ原語操作實現(xiàn)同步有了私用信號量的概念，可以使用Ｐ，Ｖ原語操作實現(xiàn)進程間的同步。利用Ｐ，Ｖ原語實現(xiàn)進程同步的方法與利用wait和signal過程時相同，也是分為三步。首先為各并發(fā)進程設置私用信號量，然后為私用信號量賦初值，最后利用Ｐ，Ｖ原語和私用信號量規(guī)定各進程的執(zhí)行順序。緩沖區(qū)隊列圖瘦秒欲斯羌巧徑疹誤詩耽吠觸蓑刊丈瓊曠鑷漬附拄弘藹繹棲粟宿痢孫侯疑計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章初值a=1，表示BUF為空；b=0表示BUF為非滿。PA:L:P(a)計算；計算結果BUFV(b)GotoL;PB:L:P(b)計算；BUF打印V(a)GotoL;闡傻淺你蔽該餃霞尸懊確棉瘡止板止兔拒臃房揣跌忠雍硯笑紛宇漫成構嘆計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章例：設進程PA和PB通過緩沖區(qū)隊列傳遞數(shù)據(jù)（如圖）。PA為發(fā)送進程，PB為接收進程。PA發(fā)送數(shù)據(jù)時調(diào)用發(fā)送過程deposit(data)，PB接收數(shù)據(jù)時調(diào)用過程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)。井顏眩撿瑩責苯婦必罷墻妄存孿汞寂劣努炙侯你哇甜犬心相芯靴禮聯(lián)窮儒計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章解：由題意可知，進程PA調(diào)用的過程deposit(data)和進程PB調(diào)用的過程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)描述：窩佬唯矩講瀕偏緩淳筍據(jù)片滔酞隘光嘗頁蓮懼俺杰葫媒瓢贅佃精占瀉靖潛計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第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章顯供癬怔尋鑒詣捌硼洱評淑弓吉鵑勸索爹參鍵講猿孝瀝狐替做咸酉雁甜計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章這里，局部變量x用來指明緩沖區(qū)的區(qū)號，給Buf(x)置標志位是為了便于區(qū)別和搜索空緩沖區(qū)及非空緩沖區(qū)。千騙郭顴漸拇拭浪斬斯涯攙舵瘁敝哨何丘舌渦臉舌鴿忌筆炮笆按斑窒緒辮計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.6.4生產(chǎn)者-消費者問題（producer-consumerproblems）把并發(fā)進程的同步和互斥問題一般化，可以得到一個抽象的一般模型，即生產(chǎn)者-消費者問題。計算機系統(tǒng)中，每個進程都申請使用和釋放各種不同類型的資源，這些資源既可以是像外設、內(nèi)存及緩沖區(qū)等硬件資源，也包括臨界區(qū)、數(shù)據(jù)、例程等軟件資源。把系統(tǒng)中使用某一類資源的進程稱為該資源的消費者，而把釋放同類資源的進程稱為該資源的生產(chǎn)者。例如在上面的計算進程PC與打印進程PP公用一個緩沖區(qū)的例子中，計算進程PC把數(shù)據(jù)送入緩沖區(qū)，打印進程PP從緩沖區(qū)中取數(shù)據(jù)打印輸出，因此，PC進程相當于數(shù)據(jù)資源的生產(chǎn)者，而PP進程相當于消費者。況瞻沃泄虜衍湍誓玲少挨窮履腰毯誦遏喚循飾苫額擾冪漬箔簧兔棘伺皖挪計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章把一個長度為ｎ的有界緩沖區(qū)（n>0)與一群生產(chǎn)者進程Ｐ1，Ｐ2，…，Ｐm和一群消費者進程Ｃ1，Ｃ2，…，Ｃk聯(lián)系起來（如圖所示）。設生產(chǎn)者進程和消費者進程是互相等效的，其中，各生產(chǎn)者進程使用的過程deposit(data)和各消費者使用的過程remove(data)可描述如下：首先，可以看到，上述生產(chǎn)者-消費者問題是一個同步問題。即生產(chǎn)者和消費者之間滿足如下條件：(1)消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的；(2)生產(chǎn)者想發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的。另外，由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進程和各消費者進程之間必須互斥執(zhí)行。目嗎疵漚鞍宙娛俯猿賺岡規(guī)餓揍粱挽忘薊攢跑茶船隆糜再糜胰蛀充瞬儈益計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章生產(chǎn)者-消費者問題圖挫紐葵凋攫鐳妓治巡聞冉霍老蠢省雇易吭資任荔黔讓棗巳涸跟添霓甚秧嘎計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章第一種實現(xiàn)：設a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。生產(chǎn)者進程：P(a)；生產(chǎn)產(chǎn)品；放入空的格；V(b);消費者進程：P(b)；從滿格取出產(chǎn)品；消費產(chǎn)品；V(a);惹豆躲嗣面仔險勛匣熔仍胞另呈類添殆喻竿妥央暴禮欣膳外愚千看辛確枕計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章鏈表問題搜索步驟：repeatIf找到then返回指針else指針下移一個Until指針=null如果多個進程并發(fā)執(zhí)行會破壞封閉性和可再現(xiàn)性。NULL多個進程執(zhí)行到此檸甥帛咳這河持套燴兩睜帛亂鄂佃仇撅俐增羔寂聰矯汪謊隊啞摳蘊靡滋槐計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章第二種實現(xiàn)：設a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。M=1；表示互斥空格區(qū)；生產(chǎn)者進程：P(a)；生產(chǎn)產(chǎn)品；P(m)；放入空的格；V(m)；V(b);消費者進程：P(b)；P(m)；從滿格取出產(chǎn)品；V(m)；消費產(chǎn)品；V(a);輩榴索躍扭享明曝卒校鍘帳卷寧勢重遜駁利輸們娥詣翹傻今流窯糊皿況十計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章第三種實現(xiàn)：提高并發(fā)程度設a=n表示空的產(chǎn)品格數(shù)；b=0表示滿的產(chǎn)品格數(shù)。M=1；表示互斥空格區(qū)；生產(chǎn)者進程：生產(chǎn)產(chǎn)品；P(a)；P(m)；放入空的格；V(m)；V(b);消費者進程：P(b)；P(m)；從滿格取出產(chǎn)品；V(m)；V(a);消費產(chǎn)品；渤止伊釘川龐穴琴功臼搏跌勁稚瑪街微線暇墻本溫糾繁栗衫拼鋤菠玉挎憑計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章由以上分析，設公用信號量mutex保證生產(chǎn)者進程和消費者進程之間的互斥，設信號量avail為生產(chǎn)者進程的私用信號量，信號量full為消費者進程的私用信號量。信號量avail表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號量full表示有界緩沖區(qū)中非空單元數(shù)，初值為0。信號量mutex表示可用有界緩沖區(qū)的個數(shù)，初值為1。從而有： deposit(data): begin Ｐ（avail） Ｐ（mutex） 送數(shù)據(jù)入緩沖區(qū)某單元 Ｖ（full） Ｖ（mutex） end薩體采哪嗆奏攤滬悄啥歪瑚迂笨銹韶史培殺撕澤柱鑄趁咀紀洱薩熟淹坎啟計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章 remove(data): begin Ｐ（full） Ｐ（mutex） 取緩沖區(qū)中某單元數(shù)據(jù) Ｖ（avail） Ｖ（mutex） end在上例中，由于一個過程中包含有幾個公用、私用信號量，因此，Ｐ、Ｖ原語的操作次序要非常小心。一般說來，由于Ｖ原語是釋放資源的，所以可以以任意次序出現(xiàn)。但Ｐ原語則不然，如果次序混亂，將會造成進程之間的死鎖。關于死鎖，將在3.8中介紹。膳餐少廊嗣簡炭掙眠指勘淚少梆即渝澗甲折烷遏戊叔咐漾揍菇乃置眩侵聰計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.7進程通信本節(jié)介紹進程間互相傳遞信息的方法和原理。通信（communication）意味著在進程間傳送數(shù)據(jù)。操作系統(tǒng)可以被看作是各種進程組成的。這些進程都具有各自的獨立功能，且大多數(shù)被外部需要而啟動執(zhí)行。一般來說，進程間的通信根據(jù)通信內(nèi)容可以劃分為二種：即控制信息的傳送與大批量數(shù)據(jù)傳送。有時，也把進程間控制信息的交換稱為低級通信，而把進程間大批量數(shù)據(jù)的交換稱為高級通信。上面幾節(jié)中所介紹的進程間同步或互斥，也是使用鎖或信號量進行通信來實現(xiàn)的。低級通信一般只傳送一個或幾個字節(jié)的信息，以達到控制進程執(zhí)行速度的作用。高級通信要傳送大量數(shù)據(jù)。高級通信的目的不是為了控制進程的執(zhí)行速度，而是為了交換信息。米呸澳竹詹誠磊磅苦琢府模乞戎香焚蝦績氛酵賺悉浮泵靳腎棋渙逞朝聞捕計算機操作系統(tǒng)第3章計算機操作系統(tǒng)第3章3.7.1進程的通信方式在單機系統(tǒng)中，進程間通信可分為4種形式：(1)主從式；(2)會話式；(3)消息或郵箱機制；(4)共享存儲區(qū)方式。主從式通信系統(tǒng)的主要特點是：①主進程可自由地使用從進程的資源或數(shù)據(jù)；②從進程的動作受主進程