【文章內(nèi)容簡介】 ?? 圖 8 進程家族結(jié)構(gòu)圖 在操作系統(tǒng)中，某些被進程調(diào)用的操作，例如隊列操作、對信號燈的操作、檢查啟動外設操作等，一旦開始執(zhí)行，就不能被中斷，否則就會出現(xiàn)操作錯誤，造成系統(tǒng)混亂。所以，這些操作可以用原語來實現(xiàn)。 原語是操作系統(tǒng)核心（不是由進程而是由一組程序模塊所組成）的一個組成部分，并且常駐內(nèi)存，通常在管態(tài)下執(zhí)行。原語一旦開始執(zhí)行，就要連續(xù)執(zhí)行完，中間不允許中斷。 1. 創(chuàng)建進程原語 通過創(chuàng)建原語完成創(chuàng)建一個新進程的功能。由于進程的存在是以其進程控制塊為標志的，因此，創(chuàng)建一個 新進程的主要任務是為進程建立一個進程控制塊 PCB，將調(diào)用者提供的進程 0 進程 1 進程 2 進程 3 進程 n 進程 5 進程 6 進程 4 中國最大的管理資源中心 39 有關信息填入該 PCB 中，并把該進程控制塊插入到就緒隊列中。所以，創(chuàng)建一個新進程的過程是：首先申請 PCB空間，根據(jù)建立的進程名字查找 PCB表，若找到了則非正常終止 (即已有同名進程 )，否則，申請分配一塊 PCB 空間；其次，為新進程分配資源，若進程的程序或數(shù)據(jù)不在內(nèi)存中，則應將它們從外存調(diào)入分配的內(nèi)存中；然后把有關信息 (如進程名字、信號量和狀態(tài)位等 )分別填入 PCB 的相應欄目中；最后把 PCB 插入到就緒隊列中。 能夠?qū)е聞?chuàng)建進程的事件主要有：用戶登錄、作 業(yè)調(diào)度、提供服務和應用請求。前三種由系統(tǒng)內(nèi)核直接調(diào)用創(chuàng)建原語創(chuàng)建新進程，后一種由用戶調(diào)用操作系統(tǒng)提供的系統(tǒng)調(diào)用完成創(chuàng)建任務，如 Linux中的 fork( )系統(tǒng)調(diào)用。 撤銷進程原語 進程完成了其“歷史使命”之后，應當退出系統(tǒng)而消亡，系統(tǒng)及時收回它占有的全部資源以便其它進程使用，這是通過撤銷原語完成的。撤銷原語的實現(xiàn)過程是：根據(jù)提供的欲被撤銷進程的名字，在 PCB 鏈中查找對應的 PCB，若找不到要撤銷的進程的名字或該進程尚未停止，則轉(zhuǎn)入異常終止處理程序，否則從 PCB 鏈中撤銷該進程及其所有子孫進程 (因為僅撤銷該進程 可能導致其子進程與進程家族隔離開來，而成為難以控制的進程 )；檢查此進程是否有等待讀取的消息，有則釋放所有緩沖區(qū)，最后釋放該進程的工作空間和 PCB 空間，以及其它資源。 撤銷原語撤銷的是標志進程存在的進程控制塊 PCB，而不是進程的程序段。這是因為一個程序段可能是幾個進程的一部分，即可能有多個進程共享該程序段。 3. 阻塞進程原語 一個正在運行的進程，因為未滿足其所申請的資源而會被迫處于阻塞狀態(tài)，等待所需事件的發(fā)生，進程的這種狀態(tài)變化就是通過進程本身調(diào)用阻塞原語實現(xiàn)的。其實現(xiàn)過程是：首先中斷 CPU，停止進程運行， 將 CPU 的現(xiàn)行狀態(tài)存放到 PCB 的 CPU 狀態(tài)保護區(qū)中，然后將該進程置阻塞狀態(tài)，并把它插入到等待隊列中。然后系統(tǒng)執(zhí)行調(diào)度程序，將 CPU分配給另一個就緒的進程。 4. 喚醒進程原語 當某進程所需要的資源出現(xiàn)時，由釋放資源的進程調(diào)用喚醒原語，喚醒等待該資源的進程。喚醒原語的基本功能是：把除了 CPU之外的一切資源都得到滿足的進程置成就緒狀態(tài)。執(zhí)行時，首先找到被喚醒進程的 內(nèi)部標識 ，讓該進程脫離阻塞隊列，將現(xiàn)行狀態(tài)改變?yōu)榫途w狀態(tài)，然后插入就緒隊列等待調(diào)度運行。 3 進程互斥與同步 并發(fā)執(zhí)行的多個進程，是在異步環(huán)境下運行的 ，每個進程都以各自獨立的、不可預知的速度向前推進。但是，有時相互合作的進程需要在某些確定的點上協(xié)調(diào)它們的工作，以各自的執(zhí)行結(jié)果為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度，產(chǎn)生直接制約關系。如：計算 中國最大的管理資源中心 40 進程和打印進程，打印進程必須等待計算進程得出計算結(jié)果后，才能進行打印輸出；而計算進程必須等待打印進程將上一次計算的結(jié)果打印輸出后，才能進行下一次計算，否則就會造成混亂。另外，還有一些進程由于共享某一公有資源，而這類資源對于不同的進程必須交叉使用，如打印機，當一個進程正在使用時，另一個進程必須等待，這就產(chǎn)生間接制約關 系。我們把在異步環(huán)境下并發(fā)執(zhí)行的進程，因直接制約而需要相互等待、相互合作，以達到各進程按相互協(xié)調(diào)的速度執(zhí)行的過程稱為進程間的同步。把因間接制約而導致交替執(zhí)行的過程稱為進程間的互斥。 臨界資源與臨界區(qū) 系統(tǒng)中同時存在有許多進程，它們共享各種資源，然而有許多資源在某一時刻只能允許一個進程使用。例如打印機、磁帶機等硬件設備和變量、隊列等數(shù)據(jù)結(jié)構(gòu)，如果有多個進程同時去使用這類資源就會造成混亂。因此必須保護這些資源，避免兩個或多個進程同時訪問這類資源。我們把某段時間內(nèi)只能允許一個進程使用的資源稱為臨界資源。 幾個進程若共享同一臨界資源，它們必須以互相排斥的方式使用這個臨界資源，即當一個進程正在使用某個臨界資源且尚未使用完畢時，其它進程必須延遲對該資源的操作，當使用該資源的進程釋放該資源時，其它進程才可使用該資源，任何進程不能從中插進去使用這個臨界資源，否則將會造成信息混亂和操作出錯。我們把訪問臨界資源的代碼段稱為臨界區(qū)。 以 A、 B 兩個進程共享一個公用變量 V 為例：如果 A 進程的 CS1 段程序向變量 V寫入數(shù)據(jù)值，而 B進程的 CS2段程序從 V中取數(shù)據(jù)值，那么當 A進程正在給 V變量賦值操作時，B 進程就不能去使用 V變量。系統(tǒng)只能 讓它們按次序交替使用，而不能同時使用，即只有進程 A執(zhí)行完 CS1 程序段釋放了 V之后，才允許 B 進程執(zhí)行 CS2 程序段來使用 V，我們把公用變量 V 稱為臨界資源，把 CS1 和 CS2 這種必須互斥執(zhí)行的程序段稱為相對于臨界資源 V的臨界區(qū)。 由于對臨界資源的使用必須互斥進行，所以進程在進入臨界區(qū)時，首先判斷是否有其它進程在使用該臨界資源，如果有，則該進程必須等待，如果沒有，該進程才能進入臨界區(qū)，執(zhí)行臨界區(qū)代碼，同時，關閉臨界區(qū)，以防其它進程進入。當進程用完臨界資源時，要開放臨界區(qū)，以便其它進程進入。因此，使用臨界資源的代碼結(jié)構(gòu) 為： 進入?yún)^(qū) 臨界區(qū) 退出區(qū) 有了臨界資源和臨界區(qū)的概念，進程間的互斥可以描述為禁止兩個或兩個以上的進程同時進入訪問同一臨界資源的臨界區(qū)。 互斥工具 進程互斥可以用若干種方式實現(xiàn)，下面介紹兩種方式：硬件方式和軟件方式。 1. 硬件方式 ① 中斷禁用 為保證多個并發(fā)進程互斥使用臨界資源，只需保證一個進程在執(zhí)行臨界區(qū)代碼時不被中 中國最大的管理資源中心 41 斷即可，這個能力可以通過系統(tǒng)內(nèi)核為啟用和禁用中斷定義的原語提供。進程可以通過下面的方法實現(xiàn)互斥。 while(1) { 禁止中斷 臨界區(qū) 啟用中斷 其余部分 } 由于臨界區(qū)不能被中斷，故可保證互斥。但該方法代價太高，因為 CPU被限制于只能交替執(zhí)行程序，執(zhí)行效率明顯降低。 ② 專用的機器指令 CPU 的設計者提供了一些硬件指令，用于保證幾個動作的原子性。這幾個動作在一個指令周期中執(zhí)行，不會受到其它指令的干擾。如 testset指令和 exchange指令。 testset指令定義如下： boolean testset(int i) { if(i==0) { i=1。 return true。 } else return false。 } 該指令測試它的參數(shù) i的值。如果 i為 0，則用 1取代并返回 true，這可以表示臨界資源未被使用時，進程占用臨界資源；如果 i為 1， i值不變，返回 false，這可以表示臨界資源已被使用時，進程不能再占用臨界資源。由于整個 testset函數(shù)自動整體執(zhí)行，就是說它不服從于任何中斷，故可實現(xiàn)進程互斥。 用 testset指令實現(xiàn)互斥舉例： const int n = / * 進程數(shù) * / int bolt。 void P(int i) { while ( 1 ) { while (!testset (bolt)) /*什么也不做 */。 臨界區(qū) 中國最大的管理資源中心 42 bolt =0。 /* 其余部分 */ } } void main( ) { bolt = 0。 parbegin (P⑴ , P⑵ ? , P(n))。 } 每個進程都在循環(huán)檢測 bolt變量，當 bolt為 0時，進程進入臨界區(qū)；否則進程一直循環(huán)檢測。 exchange指令定義如下： void exchange(int register, int memory) { int temp。 temp=memory。 memory=register。 register=temp。 } 該指令交換一個寄存器和一個存儲器單元的內(nèi)容。在執(zhí)行該指令的過程中，任何其它指令對該存儲器單元的訪問均被阻止。 用 exchange指令實現(xiàn)互斥舉例： const int n = / * 進程數(shù) * / int bolt。 void P(int i) { int keyi。 while ( 1 ) { keyi = 1。 while (keyi != 0) exchange (keyi, bolt)。 臨界區(qū) exchange (keyi, bolt)。 /* 其余部分 */ } } void main( ) { 中國最大的管理資源中心 43 bolt = 0。 parbegin(P⑴ , P⑵ .... ,P(n))。 } 共享變量 bolt 被初始化為 0，每個進程都使用一個局部變量 keyi 且初始化為 1，惟一可以進入臨界區(qū)的進程是發(fā)現(xiàn) bolt 等于 0的那個進程，它把 bolt 置為 1，排斥所有其它進程進入臨界區(qū)。進程離開臨界區(qū)時，它把 bolt重置為 0，允許另一個進程進入臨界區(qū)。 機器指令方法的特點： ① 優(yōu)點： ? 適用于在單 CPU或共享主存的多 CPU上的任何數(shù)目的進程。 ? 非常簡單且易于證明。 ? 可用于支持多個臨界區(qū)。 ② 缺點： ? 使用了忙等待。因此，當一個進程正在等待進入一個臨界區(qū)時，它會繼續(xù)消耗 CPU時間。 ? 可能發(fā)生餓死現(xiàn)象。當一個進程離開一個臨界區(qū)并且有多個進程正在等待時，選擇哪一個等待進程是隨意的，因此，某些進程可能無限地被拒絕進入。 ? 可能發(fā)生死鎖現(xiàn)象?？紤]單 CPU 中的下列情況：進程 Pl 執(zhí)行專門指令并進入臨界區(qū)，然后 P1 被中斷并把 CPU 給具有更高優(yōu)先級的 P2。如果 P2試圖使用與 P1 相同的資源，由于互斥機制，它將被拒絕訪問。因此，它會進入忙等待循環(huán)。但是，由于 P1比 P2的優(yōu)先級低，它將永遠不會被調(diào)度執(zhí)行。 軟件方式 Dekker算法 : boolean flag [2]。 int turn。 void P0( ) { while (true) { flag [0] = true。 while (flag[1]) if(turn==l) { flag[0] = false。 while ( turn == 1) /* 什么也不做 */ flag [0] = true。 } 臨