【正文】 3. 管程 中國最大的管理資源中心 49 利用信號量和 P、 V 操作，雖可有效地解決并發(fā)進程之間的同步與互斥問題，但要求用戶自己使用同步原語設(shè)計程序處理同步與互斥關(guān)系，這樣既加重了用戶的編程負擔，又難以保證并發(fā)系統(tǒng)的正確性。 1. 生產(chǎn)者與消費者問題 荷蘭計算機科學(xué)家 把廣義同步問題抽象成一種“生產(chǎn)者與消費者問題”（ produceconsumer relationship）的模型。 } 讀者可自己分析該算法的執(zhí)行過程，其中 producer 和 consumer 為并發(fā)進程。 } } 有了管程，則生產(chǎn)者和消費者進程可描述如下： void producer( ) { while⑴ { produce an item in nextp。 READ。 這種算法適合于查詢較多修改較少的情況 。 中國最大的管理資源中心 55 } } void writer( ) { while ⑴ { P(mwc)。 P(mrc)。 現(xiàn)在假設(shè)一個寫者到來，由于寫操作是排他的，所以它不能訪問數(shù)據(jù)庫，而是被掛起。 void reader( ) { while ⑴ { P(mutex)。 nextc =buffer[out]。 V(full)。每個獨立的條件變量是與進程需要等待的某種原因（或說條件）相聯(lián)系的，當定義一 個條件變量時，系統(tǒng)就建立一個相應(yīng)的等待隊列。 用信號量可以實現(xiàn)進程之間的同步。 if S0 block ( )； } 即：當執(zhí)行 P 操作時，將信號燈變量 S 的值減 1，如果 S≥ 0，表示申請的臨界區(qū)資源可用，則該進 程占用資源，繼續(xù)執(zhí)行；如果 S0，則執(zhí)行此原語的進程被置成阻塞狀態(tài)，并使其在 S 信號量的隊列中等待，由調(diào)度程序重新調(diào)度其它進程執(zhí)行。 1. lock和 unlock 中國最大的管理資源中心 46 大部分同步方案均采用某個物理實體（如鎖、信號量等）實現(xiàn)通信，進程通信原語中關(guān)鎖（ lock）和開鎖 (unlock)是最簡單的原語。 turn==l] /*什么也不做 */。 while (flag[0]) if(turn==0) { flag[1] = false。因此，當一個進程正在等待進入一個臨界區(qū)時，它會繼續(xù)消耗 CPU時間。 register=temp。如 testset指令和 exchange指令。因此必須保護這些資源，避免兩個或多個進程同時訪問這類資源。 撤銷原語撤銷的是標志進程存在的進程控制塊 PCB，而不是進程的程序段。進程控制的職能是對系統(tǒng)中的全 部進程實行有效的管理，其主要是對一個進程進行創(chuàng)建、撤銷以及在某些進程狀態(tài)間的轉(zhuǎn)換控制。多個進程實體同存于內(nèi)存中，在一段時間內(nèi)可以同時運行。 ⑧ 其它信息。有的系統(tǒng)用進程標識名作為進程的外部標識，它通常由創(chuàng)建者給出；用進程標識數(shù)作為進程的內(nèi)部標識，通常由系統(tǒng)給出。可有以下幾種情況： ① 活動就緒→靜止就緒。 ② 運行→阻塞。 ① 運行狀態(tài)。為此，在操作系統(tǒng)中引入了“進程”的概念。例如在分時系統(tǒng)中，內(nèi)存中一個編譯程序的副本同時為幾個用戶作業(yè)編 中國最大的管理資源中心 32 譯時，該編譯程序的幾次執(zhí)行，便對應(yīng)了幾個“計算”。 多道程序的并發(fā)執(zhí)行大大地提高 了 系統(tǒng)的處理能力，改善了系統(tǒng)資源的利用效率。程序的執(zhí)行結(jié)果與其執(zhí)行速度無關(guān)。程序的這兩種不同的執(zhí)行方式，體現(xiàn)出不同的特性。本章就來闡述有關(guān)進程的問題。例如，用戶要求計算機完成一道程序的運行時，通常先輸入用戶的程序和數(shù)據(jù)，然后運行程序進行計算，最后將結(jié)果打印出來 。所謂可再現(xiàn)性是指當該程序重復(fù)執(zhí)行時，必將獲得相同的結(jié)果。此時我們可以寫出如下程序，其中 parbegin 表示多個程序可以并發(fā)執(zhí)行。這就是說，系統(tǒng)中各個并發(fā)程序活動具有獨立性的一面，但在兩個并發(fā)程序活動之間有時也會有相互依賴和相互制約關(guān)系。進程是現(xiàn)代操作系統(tǒng)中的一個最基本也是最重要的概念，掌握這個概念對于理解操作系統(tǒng)實質(zhì)，分析、設(shè)計操作系統(tǒng)都有其非常重要的意義。處于該狀態(tài)的 進程不能參加競爭 CPU，因為此時即使分配給它 CPU，它也不能運行。被阻塞的進程在其被阻塞的原因獲得解除后，并不能立即投人運行，需要通過進程調(diào)度程序統(tǒng)一調(diào)度才能獲得 CPU，于是將其狀態(tài)由阻塞狀 態(tài)變成就緒狀態(tài)繼續(xù)等待 CPU。處于靜止就緒狀態(tài)的進程，若用激活原語激活后，該進程將轉(zhuǎn)變?yōu)榛顒泳途w狀態(tài)。指出進程當前所處的狀態(tài)，作為進程調(diào)度、分配 CPU的依據(jù)。按線性方式組織 PCB的情況如圖 5。 ④ 進程具有獨立性。 ?? 圖 8 進程家族結(jié)構(gòu)圖 在操作系統(tǒng)中，某些被進程調(diào)用的操作，例如隊列操作、對信號燈的操作、檢查啟動外設(shè)操作等，一旦開始執(zhí)行，就不能被中斷，否則就會出現(xiàn)操作錯誤，造成系統(tǒng)混亂。 4. 喚醒進程原語 當某進程所需要的資源出現(xiàn)時，由釋放資源的進程調(diào)用喚醒原語，喚醒等待該資源的進程。系統(tǒng)只能 讓它們按次序交替使用，而不能同時使用，即只有進程 A執(zhí)行完 CS1 程序段釋放了 V之后，才允許 B 進程執(zhí)行 CS2 程序段來使用 V，我們把公用變量 V 稱為臨界資源，把 CS1 和 CS2 這種必須互斥執(zhí)行的程序段稱為相對于臨界資源 V的臨界區(qū)。如果 i為 0，則用 1取代并返回 true，這可以表示臨界資源未被使用時，進程占用臨界資源；如果 i為 1， i值不變，返回 false，這可以表示臨界資源已被使用時，進程不能再占用臨界資源。 while ( 1 ) { keyi = 1。如果 P2試圖使用與 P1 相同的資源，由于互斥機制，它將被拒絕訪問。 flag[0] = false。 while( flag[0]amp。 ③ 釋放臨界資源，置 X 為 0（開鎖）。 信號量和 P/V操作是實現(xiàn)進程互斥與同步的非常有效的方法。 1971 年 提出了秘書進程的概念 ，后經(jīng) Hansen 和 Hoare改變成管程并加以實現(xiàn)。事實上，計算機 系統(tǒng)中的許多問題都可歸結(jié)為生產(chǎn)者與消費者問題，例如：對于需要輸出打印文件的某用戶進程和相對于打印機的管理進程，對各臨界資源的各種操作 中國最大的管理資源中心 50 該用戶進程是生產(chǎn)者，而后者便是消費者；同理，若該用戶進程需要讀入一個磁盤文件，相對于磁盤管理進程，該用戶進程是消費者，而磁盤管理進程則是生產(chǎn)者。 注意：在此模塊中無論是生產(chǎn)者還是消費者，關(guān)于 P 操作的次序不能顛倒，否則可能造成死鎖。 PC. put(item)。 P(mutex)。 對于修改頻繁的問題，應(yīng)采用寫者優(yōu)先算法。 writecount++。 READ。 設(shè)想當一個讀者在使用數(shù)據(jù)庫時，另一個讀者也來訪問數(shù)據(jù)庫，由于同時允許多個讀者同時進行讀操作， 所 以第二個讀者也被允許進入，同理第三個及隨后更多的讀者都被允許進入。下面給出讀者進程與寫者進程的解法： 讀者優(yōu)先 : int readcount=0； semaphore mutex = 1, wsem=1。 中國最大的管理資源中心 52 } void get(item) . { if (count= 0) 。 void producer( ) /*生產(chǎn)者進程 */ { while⑴ { produce next product； P(empty)； P(mutex)； buffer[i]=product； i=(i+1) % n； 中國最大的管理資源中心 51 V(mutex)。為此，引入了條件 (condition)變量及其操作的概念。只有當 P1進程執(zhí)行了 V (S2)后，才能喚醒 P2 進程。 P 操作原語定義如下： P（ S） { S。 這里介紹三種同步機制：鎖、信號量和管程。amp。 其余部分 } } void P1( ) { while (true) { flag [1]= true。 ② 缺點： ? 使用了忙等待。 memory=register。這幾個動作在一個指令周期中執(zhí)行，不會受到其它指令的干擾。例如打印機、磁帶機等硬件設(shè)備和變量、隊列等數(shù)據(jù)結(jié)構(gòu)，如果有多個進程同時去使用這類資源就會造成混亂。撤銷原語的實現(xiàn)過程是：根據(jù)提供的欲被撤銷進程的名字，在 PCB 鏈中查找對應(yīng)的 PCB，若找不到要撤銷的進程的名字或該進程尚未停止，則轉(zhuǎn)入異常終止處理程序，否則從 PCB 鏈中撤銷該進程及其所有子孫進程 (因為僅撤銷該進程 可能導(dǎo)致其子進程與進程家族隔離開來，而成為難以控制的進程 )；檢查此進程是否有等待讀取的消息，有則釋放所有緩沖區(qū)，最后釋放該進程的工作空間和 PCB 空間，以及其它資源。 2 進程控制 進程有由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡的生命周期，因此操作系統(tǒng)要有對進程生命周期的各個環(huán)節(jié)進行控制的功能，這就是進程控制。 ② 進程具有并發(fā)性。它用于將處于同一狀態(tài)的進程鏈接成一個隊列，在該單元中存放下一進程 PCB首址。進程標識名，通常用字母和數(shù)字組成的“串”表示，進程標識數(shù)則是在一定數(shù)值范圍內(nèi)的進程編號。 引入掛起狀態(tài)后，又將增加從掛起狀態(tài)（又稱為靜止狀態(tài)）到非掛起狀態(tài)（又稱為活動狀態(tài)）的轉(zhuǎn)換：或者相反。即就緒狀態(tài)的進程，一旦被調(diào)度進程選中，獲 得 CPU，便發(fā)生此 狀態(tài) 變遷。運行中的進程具有三種基本狀態(tài)：運行、阻塞、就緒，這三種狀態(tài)構(gòu)成了最簡單的進程生命周期模型，進程在其生命周期內(nèi)處于這三種狀態(tài)之一，其狀態(tài)將隨著自身的推進和外界環(huán)境的變化而變化，由一種狀態(tài)變遷到另一種狀態(tài)。為了準確地描述程序的執(zhí)行過程，設(shè)計出高質(zhì)量的操作系統(tǒng)，就不能再用靜態(tài)的觀點，而應(yīng)該用動態(tài)的觀點來刻畫程序。如前所述，程序在順序執(zhí)行時，程序和“計算”之間保持一一對應(yīng)的關(guān)系，但在并發(fā)執(zhí)行時，一個并發(fā)程序可為多個用戶作業(yè)調(diào)用，而使該程序處于多個“執(zhí)行”過程中，從而形成了多個“計算”，這就是說，多個“計算’可能是在不同數(shù)據(jù)集上執(zhí)行同一程序，所以程序和“計算”不再一一對應(yīng)。此外從圖中可以看出： I2 與 Cl、 I3 與 C2 與 P I4 與 C3 與 中國最大的管理資源中心 30 P2是重疊的。 ③ 結(jié)果無關(guān)性。 程序的并發(fā)執(zhí)行是在多道程序環(huán)境下完成的，而在單道程序工作環(huán)境中，程序是順序執(zhí)行的。 1 進程的概念 程序的并發(fā)執(zhí)行 現(xiàn)在所有的計算機都能同時做幾件事情。 假設(shè)系統(tǒng)中有 2個程序，而每個程序都由三個程序段 I、C、 P 組成，其中， I 表示從輸入機上讀入程序的信息， C 表示執(zhí)行程序的計算過程， P 表示在打印機上打印出程序的計算結(jié)果。這給程序的調(diào)試帶來了很大的方便。 int n=0。程序之間的 制約關(guān)系有兩種：直接制約關(guān)系和間接制約關(guān)系。但是，迄今為止，對這一概念尚無一個非常確切的、令人滿意的、統(tǒng)一的定義，不同的人，站在不同的角度，對進程進行了不同的描述，下面列舉幾個操作系統(tǒng)的權(quán)威人士對“ 進程”所下的定義： ① 行為的一個規(guī)則叫做程序，程序在 CPU上執(zhí)行時所發(fā)生的活動稱為進程（ Dijkstra）。 ③ 就緒狀態(tài)。僅當進程調(diào)度程序把 CPU 再次分配給它時，才可恢復(fù)曾被中斷的現(xiàn)場繼續(xù)運行。 ④ 靜止阻塞→活動阻塞。 ④ 進程的優(yōu)先級。 ② 鏈接表方式：系統(tǒng)按照進程的狀態(tài)將進程的 PCB 鏈接成隊列，從而形成就緒隊列、阻塞隊列、運行隊列等。進程是操作系統(tǒng)進行調(diào)度和分配資源的獨立單 位。所以，這些操作可以用原語來實現(xiàn)。喚醒原語的基本功能是：把除了 CPU之外的一切資源都得到滿足的進程置成就緒狀態(tài)。 由于對臨界資源的使用必須互斥進行，所以進程在進入臨界區(qū)時，首先判斷是否有其它進程在使用該臨界資源，如果有，則該進程必須等待，如果沒有，該進程才能進入臨界區(qū)，執(zhí)行臨界區(qū)代碼，同時，關(guān)閉臨界區(qū)