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