【正文】 P(n))。 臨界區(qū) exchange (keyi, bolt)。 while ( 1 ) { keyi = 1。 用 exchange指令實現(xiàn)互斥舉例： const int n = / * 進(jìn)程數(shù) * / int bolt。 } 該指令交換一個寄存器和一個存儲器單元的內(nèi)容。 memory=register。 exchange指令定義如下： void exchange(int register, int memory) { int temp。 parbegin (P⑴ , P⑵ ? , P(n))。 臨界區(qū) 中國最大的管理資源中心 42 bolt =0。 用 testset指令實現(xiàn)互斥舉例： const int n = / * 進(jìn)程數(shù) * / int bolt。如果 i為 0，則用 1取代并返回 true，這可以表示臨界資源未被使用時，進(jìn)程占用臨界資源；如果 i為 1， i值不變，返回 false，這可以表示臨界資源已被使用時，進(jìn)程不能再占用臨界資源。 } else return false。 testset指令定義如下： boolean testset(int i) { if(i==0) { i=1。這幾個動作在一個指令周期中執(zhí)行，不會受到其它指令的干擾。但該方法代價太高，因為 CPU被限制于只能交替執(zhí)行程序，執(zhí)行效率明顯降低。進(jìn)程可以通過下面的方法實現(xiàn)互斥。 互斥工具 進(jìn)程互斥可以用若干種方式實現(xiàn)，下面介紹兩種方式：硬件方式和軟件方式。當(dāng)進(jìn)程用完臨界資源時，要開放臨界區(qū)，以便其它進(jìn)程進(jìn)入。系統(tǒng)只能 讓它們按次序交替使用，而不能同時使用，即只有進(jìn)程 A執(zhí)行完 CS1 程序段釋放了 V之后，才允許 B 進(jìn)程執(zhí)行 CS2 程序段來使用 V，我們把公用變量 V 稱為臨界資源，把 CS1 和 CS2 這種必須互斥執(zhí)行的程序段稱為相對于臨界資源 V的臨界區(qū)。我們把訪問臨界資源的代碼段稱為臨界區(qū)。我們把某段時間內(nèi)只能允許一個進(jìn)程使用的資源稱為臨界資源。例如打印機(jī)、磁帶機(jī)等硬件設(shè)備和變量、隊列等數(shù)據(jù)結(jié)構(gòu)，如果有多個進(jìn)程同時去使用這類資源就會造成混亂。把因間接制約而導(dǎo)致交替執(zhí)行的過程稱為進(jìn)程間的互斥。另外，還有一些進(jìn)程由于共享某一公有資源，而這類資源對于不同的進(jìn)程必須交叉使用，如打印機(jī)，當(dāng)一個進(jìn)程正在使用時，另一個進(jìn)程必須等待，這就產(chǎn)生間接制約關(guān) 系。但是，有時相互合作的進(jìn)程需要在某些確定的點上協(xié)調(diào)它們的工作，以各自的執(zhí)行結(jié)果為對方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度，產(chǎn)生直接制約關(guān)系。執(zhí)行時，首先找到被喚醒進(jìn)程的 內(nèi)部標(biāo)識 ，讓該進(jìn)程脫離阻塞隊列，將現(xiàn)行狀態(tài)改變?yōu)榫途w狀態(tài)，然后插入就緒隊列等待調(diào)度運行。 4. 喚醒進(jìn)程原語 當(dāng)某進(jìn)程所需要的資源出現(xiàn)時，由釋放資源的進(jìn)程調(diào)用喚醒原語，喚醒等待該資源的進(jìn)程。其實現(xiàn)過程是：首先中斷 CPU，停止進(jìn)程運行， 將 CPU 的現(xiàn)行狀態(tài)存放到 PCB 的 CPU 狀態(tài)保護(hù)區(qū)中，然后將該進(jìn)程置阻塞狀態(tài)，并把它插入到等待隊列中。這是因為一個程序段可能是幾個進(jìn)程的一部分，即可能有多個進(jìn)程共享該程序段。撤銷原語的實現(xiàn)過程是：根據(jù)提供的欲被撤銷進(jìn)程的名字，在 PCB 鏈中查找對應(yīng)的 PCB，若找不到要撤銷的進(jìn)程的名字或該進(jìn)程尚未停止，則轉(zhuǎn)入異常終止處理程序，否則從 PCB 鏈中撤銷該進(jìn)程及其所有子孫進(jìn)程 (因為僅撤銷該進(jìn)程 可能導(dǎo)致其子進(jìn)程與進(jìn)程家族隔離開來，而成為難以控制的進(jìn)程 )；檢查此進(jìn)程是否有等待讀取的消息，有則釋放所有緩沖區(qū)，最后釋放該進(jìn)程的工作空間和 PCB 空間，以及其它資源。前三種由系統(tǒng)內(nèi)核直接調(diào)用創(chuàng)建原語創(chuàng)建新進(jìn)程，后一種由用戶調(diào)用操作系統(tǒng)提供的系統(tǒng)調(diào)用完成創(chuàng)建任務(wù)，如 Linux中的 fork( )系統(tǒng)調(diào)用。所以，創(chuàng)建一個新進(jìn)程的過程是：首先申請 PCB空間，根據(jù)建立的進(jìn)程名字查找 PCB表，若找到了則非正常終止 (即已有同名進(jìn)程 )，否則，申請分配一塊 PCB 空間；其次，為新進(jìn)程分配資源，若進(jìn)程的程序或數(shù)據(jù)不在內(nèi)存中，則應(yīng)將它們從外存調(diào)入分配的內(nèi)存中；然后把有關(guān)信息 (如進(jìn)程名字、信號量和狀態(tài)位等 )分別填入 PCB 的相應(yīng)欄目中；最后把 PCB 插入到就緒隊列中。 1. 創(chuàng)建進(jìn)程原語 通過創(chuàng)建原語完成創(chuàng)建一個新進(jìn)程的功能。 原語是操作系統(tǒng)核心（不是由進(jìn)程而是由一組程序模塊所組成）的一個組成部分，并且常駐內(nèi)存，通常在管態(tài)下執(zhí)行。 ?? 圖 8 進(jìn)程家族結(jié)構(gòu)圖 在操作系統(tǒng)中，某些被進(jìn)程調(diào)用的操作，例如隊列操作、對信號燈的操作、檢查啟動外設(shè)操作等，一旦開始執(zhí)行，就不能被中斷，否則就會出現(xiàn)操作錯誤，造成系統(tǒng)混亂。 進(jìn)程的控制通常由原語完成。通常允許一個進(jìn)程創(chuàng)建和控制另一個進(jìn)程，前者稱為父進(jìn)程，后者稱為子進(jìn)程，子進(jìn)程又可創(chuàng)建其子進(jìn)程，從而形成了一個樹形結(jié)構(gòu)的進(jìn)程家族，如圖 8所示。 2 進(jìn)程控制 進(jìn)程有由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡的生命周期，因此操作系統(tǒng)要有對進(jìn)程生命周期的各個環(huán)節(jié)進(jìn)行控制的功能，這就是進(jìn)程控制。 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 PCB9 …… 執(zhí)行指針 就緒表指針 阻塞表指針 5 7 ?? 3 9 ?? 中國最大的管理資源中心 38 ④ 在進(jìn)程調(diào)度中，系統(tǒng)進(jìn)程的優(yōu)先級高于用戶進(jìn)程。 ② 系統(tǒng)進(jìn)程之間的關(guān)系由操作系統(tǒng)自己負(fù)責(zé)， 這樣有利于增加系統(tǒng)的并行性，提高資源的利用率；用戶進(jìn)程之間的關(guān)系主要由用戶自己負(fù)責(zé)，為了便于用戶管理自己的任務(wù)，操作系統(tǒng)提供一套簡便的任務(wù)調(diào)用命令作為協(xié)調(diào)手段，并 在用戶區(qū)根據(jù)用戶作業(yè)的性質(zhì)（是單任務(wù)還是多任務(wù)）裝入相應(yīng)的任務(wù)調(diào)度程序 。 進(jìn)程通常分為兩類，一類是系統(tǒng)進(jìn)程，另一類是用戶進(jìn)程。 ⑤ 進(jìn)程具有異步性（不確定性）。 ④ 進(jìn)程具有獨立性。 ③ 進(jìn)程具有結(jié)構(gòu)特性。并發(fā)性是進(jìn)程的重要特性，也是操作系統(tǒng)的重要特性。 ② 進(jìn)程具有并發(fā)性。進(jìn)程的動態(tài)性不僅表現(xiàn)在“程序的執(zhí)行”， 而且還表現(xiàn)在它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡的生命周期。 ① 進(jìn)程具有動態(tài)性。按索引方式組織 PCB的情況如圖 7。按鏈接方式組織 PCB的情況如圖 6。按線性方式組織 PCB的情況如圖 5。目前常用的 PCB的組織方式有以下三種： ① 線性表方式：不論進(jìn)程的狀態(tài)如何，將所有的 PCB 連續(xù)地存放在內(nèi)存的系統(tǒng)區(qū)。 這里給出的只是一般操作系統(tǒng)中 PCB所應(yīng)具有的內(nèi)容，不同操作系統(tǒng)的 PCB結(jié)構(gòu)是不同執(zhí)行 活動 阻塞 靜止 阻塞 活動 就緒 靜止 就緒 調(diào)度 請求 I/O 中國最大的管理資源中心 36 的，我們將在 8 節(jié)介紹 Linux系統(tǒng)的 PCB結(jié)構(gòu)。它用于將處于同一狀態(tài)的進(jìn)程鏈接成一個隊列，在該單元中存放下一進(jìn)程 PCB首址。這一部分指出資源需求、分配和控制信息。 ⑥ 資源清單。 ⑤ 進(jìn)程現(xiàn)場保護(hù)區(qū)。一般根據(jù)進(jìn)程的輕重緩急程度為進(jìn)程指定一個優(yōu)先級，優(yōu)先級用優(yōu)先數(shù)表示。指出進(jìn)程當(dāng)前所處的狀態(tài)，作為進(jìn)程調(diào)度、分配 CPU的依據(jù)。指出 進(jìn)程的程序和數(shù)據(jù)部分在內(nèi)存或外存中的物理位置。有的系統(tǒng)只用其中之一。進(jìn)程標(biāo)識名，通常用字母和數(shù)字組成的“串”表示，進(jìn)程標(biāo)識數(shù)則是在一定數(shù)值范圍內(nèi)的進(jìn)程編號。 掛起 時間片到 激活 掛起 釋放 激活 釋放 掛起 圖 4 具有掛起狀態(tài)的進(jìn)程狀態(tài)變遷圖 在通常的操作系統(tǒng)中， PCB應(yīng)包含如下一些信息： ① 進(jìn)程標(biāo)識信息。 進(jìn)程控制塊是進(jìn)程存在的惟一標(biāo)志，它跟蹤程序執(zhí)行的情況，表明了進(jìn)程在當(dāng)前時刻的狀態(tài)以及與其它進(jìn)程和資源的關(guān)系。 進(jìn)程控制塊 由于多個程序并發(fā)執(zhí)行，各程序需要輪流使用 CPU， 當(dāng)某程序不在 CPU 上運行時，必須保留其被中斷的程序的現(xiàn)場，包括：斷點地址、程序狀態(tài)字、通用寄存器的內(nèi)容、堆棧內(nèi)容、 中國最大的管理資源中心 35 程序當(dāng)前狀態(tài)、程序的大小、運行時間等信息，以便程序再次獲得 CPU時，能夠正確執(zhí)行。處于靜止阻塞狀態(tài)的進(jìn)程，若用激活原語激活后，該進(jìn)程將轉(zhuǎn)變?yōu)榛顒幼枞麪顟B(tài)。處于靜止就緒狀態(tài)的進(jìn)程，若用激活原語激活后，該進(jìn)程將轉(zhuǎn)變?yōu)榛顒泳途w狀態(tài)。當(dāng)進(jìn)程處于未被掛起的阻塞狀態(tài)時，稱它是處于活動阻塞狀態(tài)，當(dāng)用掛起原語將它掛起后，進(jìn)程便轉(zhuǎn)變?yōu)殪o止阻塞狀態(tài)，處于靜止阻塞狀態(tài)的進(jìn)程在其所期待的事件出現(xiàn)后，將從靜止阻塞變?yōu)殪o止就緒。當(dāng)進(jìn)程處于未被掛起的就緒狀態(tài)時，稱此為活動就緒狀態(tài)，當(dāng)用掛起原語將該進(jìn)程掛起后，該進(jìn)程便轉(zhuǎn)變?yōu)殪o止就緒狀態(tài)，處于靜止就緒狀態(tài)的進(jìn)程不再被調(diào)度執(zhí)行。 引入掛起狀態(tài)后，又將增加從掛起狀態(tài)（又稱為靜止?fàn)顟B(tài)）到非掛起狀態(tài)（又稱為活動狀態(tài)）的轉(zhuǎn)換：或者相反。 具有掛起狀態(tài) 的進(jìn)程狀態(tài)轉(zhuǎn)換 在許多系統(tǒng)中，進(jìn)程除了具有上述三種基本狀態(tài)以外，又增加了一些新狀態(tài)，其中最重要的是掛起狀態(tài)，引入掛起狀態(tài)的主要原因是內(nèi)存資源不足。于是，正在運行的進(jìn)程就由運行狀態(tài)變?yōu)榫途w狀態(tài)。這種狀態(tài)變化通常出現(xiàn)在分時操作系統(tǒng)中。即阻塞進(jìn)程的 I/O請求完成時，發(fā)生此狀態(tài)變遷。被阻塞的進(jìn)程在其被阻塞的原因獲得解除后，并不能立即投人運行，需要通過進(jìn)程調(diào)度程序統(tǒng)一調(diào)度才能獲得 CPU，于是將其狀態(tài)由阻塞狀 態(tài)變成就緒狀態(tài)繼續(xù)等待 CPU。即運行進(jìn)程遇 I/O請求時，發(fā)生此狀態(tài)變遷。處于運行狀態(tài)的進(jìn)程申請新資源而又不能立即被滿足時，進(jìn)程狀態(tài)由運行變成阻塞。即就緒狀態(tài)的進(jìn)程，一旦被調(diào)度進(jìn)程選中，獲 得 CPU，便發(fā)生此 狀態(tài) 變遷。對于單 CPU 系統(tǒng)而言，因為處于就緒狀態(tài)的進(jìn)程往往不止一個，同一時刻就緒 執(zhí)行 阻塞 中國最大的管理資源中心 34 只能有一個就緒進(jìn)程獲得 CPU。 I/O 完成 時間片完 進(jìn)程調(diào)度 I/O 請求 圖 3 進(jìn)程狀態(tài)變遷圖 ① 就緒 → 運行。在一個系統(tǒng)中，處于就緒狀態(tài)的進(jìn)程可能有多個，統(tǒng)稱排成一個隊列，稱為就緒隊列。等待 CPU 的狀態(tài)。處于該狀態(tài)的 進(jìn)程不能參加競爭 CPU，因為此時即使分配給它 CPU，它也不能運行。 ② 阻塞狀態(tài)。進(jìn)程正在 CPU上運行的狀態(tài)，該進(jìn)程已獲得必要的資源，包括 CPU，該程序正在 CPU上運行。運行中的進(jìn)程具有三種基本狀態(tài)：運行、阻塞、就緒，這三種狀態(tài)構(gòu)成了最簡單的進(jìn)程生命周期模型，進(jìn)程在其生命周期內(nèi)處于這三種狀態(tài)之一，其狀態(tài)將隨著自身的推進(jìn)和外界環(huán)境的變化而變化，由一種狀態(tài)變遷到另一種狀態(tài)。 進(jìn)程狀態(tài)及其轉(zhuǎn)換 1. 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 有了進(jìn)程的概念，就可以用動態(tài)的觀點分析進(jìn)程的狀態(tài)變化及相互制約關(guān)系。 上述這些從不同角度對進(jìn)程所做的解釋或所下的定義，有些是近似的，有些則側(cè)重某一方面，這說明進(jìn)程這一概念尚未完全統(tǒng)一，但長期以來卻巳廣泛而成功地用于許多系統(tǒng)之中，成為構(gòu)造操作系統(tǒng)的不可缺少的強(qiáng)有力的工具。 ④ 順序進(jìn)程 (有時稱為任務(wù) )是一個程序與其數(shù)據(jù)集一道順序通過 CPU 的執(zhí)行所發(fā)生的活動（ Alan ）。 中國最大的管理資源中心 33 ② 一個進(jìn)程是一系列逐一執(zhí)行的操作，而操作的確切含義則有賴于我們以何種詳盡程度來描述進(jìn)程（ ）。進(jìn)程是現(xiàn)代操作系統(tǒng)中的一個最基本也是最重要的概念，掌握這個概念對于理解操作系統(tǒng)實質(zhì)，分析、設(shè)計操作系統(tǒng)都有其非常重要的意義。在這種情況下，程序這 個靜態(tài)概念已經(jīng)不能如實地反映程序活動的這些特征。 進(jìn)程定義 如上所述，在多道程序的環(huán)境下，程序的并發(fā)執(zhí)行代替了程序的順序執(zhí)行，