【正文】 態(tài)標(biāo)記，并把控制轉(zhuǎn)到該進(jìn)程，把它由就緒狀態(tài)變?yōu)檫\(yùn)行狀態(tài)，這樣進(jìn)程就投入運(yùn)行。 ② 運(yùn)行→阻塞。如，運(yùn)行中的進(jìn)程需要等待文件的輸入，系統(tǒng)便自動(dòng)轉(zhuǎn)入系統(tǒng)控制程序，進(jìn)行文件輸入，在文件輸入過程中，該進(jìn)程進(jìn)入阻塞狀態(tài)，而系統(tǒng)將控制轉(zhuǎn)給進(jìn)程調(diào)度程序，進(jìn)程調(diào)度程序根據(jù)調(diào)度算法把 CPU分配給處于就緒狀態(tài)的其它進(jìn)程。 ③ 阻塞→就緒。僅當(dāng)進(jìn)程調(diào)度程序把 CPU 再次分配給它時(shí)，才可恢復(fù)曾被中斷的現(xiàn)場(chǎng)繼續(xù)運(yùn)行。 ④ 運(yùn)行 →就緒。一個(gè)正在運(yùn)行的進(jìn)程，由于規(guī)定運(yùn)行時(shí)間片用完而使系統(tǒng)發(fā)出超時(shí)中斷請(qǐng)求，超時(shí)中斷處理程序把該進(jìn)程的狀態(tài)修改為就緒狀態(tài)，并根據(jù)其自身的特征而插入就緒隊(duì)列的適當(dāng)位置，保存進(jìn)程現(xiàn)場(chǎng)信息，收回 CPU并轉(zhuǎn)入進(jìn)程調(diào)度程序。即運(yùn)行進(jìn)程時(shí)間片用完時(shí)，發(fā)生此狀態(tài)變遷。另外當(dāng)有終端用戶請(qǐng)求、父進(jìn)程請(qǐng)求、負(fù)荷調(diào)節(jié)需要等情況時(shí)，也要用到掛起狀態(tài)?？捎幸韵聨追N情況： ① 活動(dòng)就緒→靜止就緒。 ② 活動(dòng)阻塞→靜止阻塞。 ③ 靜止就緒→活動(dòng)就緒。 ④ 靜止阻塞→活動(dòng)阻塞。 具有掛起狀態(tài)的進(jìn)程狀態(tài)變遷過程如圖 4。為了保存這些內(nèi)容，需要建立 — 個(gè)專用數(shù)據(jù)結(jié)構(gòu)，我們稱這個(gè)數(shù)據(jù)結(jié)構(gòu)為進(jìn)程控制塊 PCB （ Process Control Block）。當(dāng)創(chuàng)建一個(gè)進(jìn)程時(shí)，實(shí)際上就是為其建立一個(gè)進(jìn)程控制塊。為了標(biāo)識(shí)系統(tǒng)中的各個(gè)進(jìn)程，每個(gè)進(jìn)程必須有惟一的標(biāo)識(shí)名或標(biāo)識(shí)數(shù)。有的系統(tǒng)用進(jìn)程標(biāo)識(shí)名作為進(jìn)程的外部標(biāo)識(shí)，它通常由創(chuàng)建者給出；用進(jìn)程標(biāo)識(shí)數(shù)作為進(jìn)程的內(nèi)部標(biāo)識(shí)，通常由系統(tǒng)給出。 ② 位置信息。 ③ 狀態(tài)信息。 ④ 進(jìn)程的優(yōu)先級(jí)。進(jìn)程調(diào)度程序根據(jù)優(yōu)先數(shù)的大小，確定優(yōu)先級(jí)的高低，并把 CPU控制權(quán)交給優(yōu)先級(jí)最高的進(jìn)程。當(dāng)進(jìn)程狀態(tài)變化時(shí)（例如一個(gè)進(jìn)程放棄使用 CPU），它需要將當(dāng)時(shí)的 CPU現(xiàn)場(chǎng)保護(hù)到內(nèi)存中，以便再次占用 CPU時(shí)恢復(fù)正常運(yùn)行，有的系統(tǒng)把要保護(hù)的 CPU現(xiàn)場(chǎng)放在進(jìn)程的工作區(qū)中，而 PCB中僅給出 CPU現(xiàn)場(chǎng)保護(hù) 區(qū)起始地址。每個(gè)進(jìn)程在運(yùn)行時(shí)，除了需要內(nèi)存外，還需要其它資源，如 I/O 設(shè)備、外存、數(shù)據(jù)區(qū)等。 ⑦ 隊(duì)列指針或鏈接字。 ⑧ 其它信息。 在一個(gè)系統(tǒng)中，通?？赡苡腥舾蓚€(gè)進(jìn)程同時(shí)存在，所以就擁有若干個(gè) PCB，為了能對(duì) PCB進(jìn)行有效的管理，就要用適當(dāng)?shù)姆椒ò堰@ 些 PCB組織起來(lái)。這種方式適用于系統(tǒng)中進(jìn)程數(shù)目不多的情況。 ② 鏈接表方式：系統(tǒng)按照進(jìn)程的狀態(tài)將進(jìn)程的 PCB 鏈接成隊(duì)列，從而形成就緒隊(duì)列、阻塞隊(duì)列、運(yùn)行隊(duì)列等。 ③ 索引表方式：系統(tǒng)按照進(jìn)程的狀態(tài)分別建立就緒索引表、阻塞索引表等，通過索引表來(lái)管理系統(tǒng)中的進(jìn)程。 PCB1 PCB2 PCB3 ?? PCBn 圖 5 線性方式組織 PCB 的示意圖 圖 6 鏈接方式組織 PCB 的示意圖 PCB1 4 PCB2 3 PCB3 0 PCB4 8 PCB5 PCB6 7 PCB7 9 PCB8 0 PCB9 1 …… 執(zhí)行指針 就緒隊(duì)列指針 阻塞隊(duì)列指針 空閑隊(duì)列指針 中國(guó)最大的管理資源中心 37 就緒索引 表 阻塞索引表 圖 7 索引方式組織 PCB 的示意圖 進(jìn)程的特性 前面我們通過程序并發(fā)執(zhí)行時(shí)所產(chǎn)生的問題引出了進(jìn)程的概念，并描述了進(jìn)程、進(jìn)程狀態(tài)以及進(jìn)程狀態(tài)之間的轉(zhuǎn)換，現(xiàn)在，我們對(duì)進(jìn)程的特征進(jìn)行梳理，以便更好地理解進(jìn)程。進(jìn)程是程序的一次執(zhí)行過程，一個(gè)進(jìn)程可以看成是一組動(dòng)作序列，而每個(gè)動(dòng)作則是由執(zhí)行一段指令序列來(lái)實(shí)現(xiàn)的，其結(jié)果是實(shí)現(xiàn)某種功能。而程序是一組有序靜態(tài)指令和數(shù)據(jù)的集合，用來(lái)指示 CPU 的操作，本身并不具有運(yùn)動(dòng)含義，是一種靜態(tài)概念。多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，在一段時(shí)間內(nèi)可以同時(shí)運(yùn)行。引入進(jìn)程概念的目的，也正是為了描述和實(shí)現(xiàn)并發(fā)執(zhí)行。從結(jié)構(gòu)上看，進(jìn)程是由程序段和相應(yīng)的數(shù)據(jù)段及進(jìn)程控制塊構(gòu)成的，程序只包含指令代碼及相應(yīng)數(shù)據(jù)。進(jìn)程是操作系統(tǒng)進(jìn)行調(diào)度和分配資源的獨(dú)立單 位。系統(tǒng)中的進(jìn)程，按照各自的、不可預(yù)知的速度向前推進(jìn)。它們的區(qū)別是： ① 系統(tǒng)進(jìn)程是操作系統(tǒng)用來(lái)管理系統(tǒng)資源并行活動(dòng)的并發(fā)軟件；用戶進(jìn)程是可以獨(dú)立執(zhí)行的用戶程序段，它是操作系統(tǒng)提供服務(wù)的對(duì)象，是系統(tǒng)資源的實(shí)際使用者。 ③ 系統(tǒng)進(jìn)程直接管理有關(guān)的軟、硬設(shè)備的活動(dòng) ；用戶進(jìn)程只能間接地和系統(tǒng)資源發(fā)生關(guān)系，當(dāng)用戶進(jìn)程需要某種資源時(shí)，它必須向系統(tǒng)提出請(qǐng)求，由系統(tǒng)調(diào)度和分配。無(wú)論是系統(tǒng)進(jìn)程還是用戶進(jìn)程，對(duì)核心層來(lái)說它們都是基本的活動(dòng)單位。進(jìn)程控制的職能是對(duì)系統(tǒng)中的全 部進(jìn)程實(shí)行有效的管理，其主要是對(duì)一個(gè)進(jìn)程進(jìn)行創(chuàng)建、撤銷以及在某些進(jìn)程狀態(tài)間的轉(zhuǎn)換控制。采用這種樹形結(jié)構(gòu)的方式，使得進(jìn)程控制更為靈活方便。所謂“原語(yǔ)”一般是指由若干條指令所組成，用來(lái)實(shí)現(xiàn)某個(gè)特定功能，在執(zhí)行過程中不可被中斷的程序段。所以，這些操作可以用原語(yǔ)來(lái)實(shí)現(xiàn)。原語(yǔ)一旦開始執(zhí)行，就要連續(xù)執(zhí)行完，中間不允許中斷。由于進(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ì)列中。 能夠?qū)е聞?chuàng)建進(jìn)程的事件主要有：用戶登錄、作 業(yè)調(diào)度、提供服務(wù)和應(yīng)用請(qǐng)求。 撤銷進(jìn)程原語(yǔ) 進(jìn)程完成了其“歷史使命”之后，應(yīng)當(dāng)退出系統(tǒng)而消亡，系統(tǒng)及時(shí)收回它占有的全部資源以便其它進(jìn)程使用，這是通過撤銷原語(yǔ)完成的。 撤銷原語(yǔ)撤銷的是標(biāo)志進(jìn)程存在的進(jìn)程控制塊 PCB，而不是進(jìn)程的程序段。 3. 阻塞進(jìn)程原語(yǔ) 一個(gè)正在運(yùn)行的進(jìn)程，因?yàn)槲礉M足其所申請(qǐng)的資源而會(huì)被迫處于阻塞狀態(tài)，等待所需事件的發(fā)生，進(jìn)程的這種狀態(tài)變化就是通過進(jìn)程本身調(diào)用阻塞原語(yǔ)實(shí)現(xiàn)的。然后系統(tǒng)執(zhí)行調(diào)度程序，將 CPU分配給另一個(gè)就緒的進(jìn)程。喚醒原語(yǔ)的基本功能是：把除了 CPU之外的一切資源都得到滿足的進(jìn)程置成就緒狀態(tài)。 3 進(jìn)程互斥與同步 并發(fā)執(zhí)行的多個(gè)進(jìn)程，是在異步環(huán)境下運(yùn)行的 ，每個(gè)進(jìn)程都以各自獨(dú)立的、不可預(yù)知的速度向前推進(jì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ì)造成混亂。我們把在異步環(huán)境下并發(fā)執(zhí)行的進(jìn)程，因直接制約而需要相互等待、相互合作，以達(dá)到各進(jìn)程按相互協(xié)調(diào)的速度執(zhí)行的過程稱為進(jìn)程間的同步。 臨界資源與臨界區(qū) 系統(tǒng)中同時(shí)存在有許多進(jìn)程，它們共享各種資源，然而有許多資源在某一時(shí)刻只能允許一個(gè)進(jìn)程使用。因此必須保護(hù)這些資源，避免兩個(gè)或多個(gè)進(jìn)程同時(shí)訪問這類資源。 幾個(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ò)。 以 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變量。 由于對(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)入。因此，使用臨界資源的代碼結(jié)構(gòu) 為： 進(jìn)入?yún)^(qū) 臨界區(qū) 退出區(qū) 有了臨界資源和臨界區(qū)的概念，進(jìn)程間的互斥可以描述為禁止兩個(gè)或兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入訪問同一臨界資源的臨界區(qū)。 1. 硬件方式 ① 中斷禁用 為保證多個(gè)并發(fā)進(jìn)程互斥使用臨界資源，只需保證一個(gè)進(jìn)程在執(zhí)行臨界區(qū)代碼時(shí)不被中 中國(guó)最大的管理資源中心 41 斷即可，這個(gè)能力可以通過系統(tǒng)內(nèi)核為啟用和禁用中斷定義的原語(yǔ)提供。 while(1) { 禁止中斷 臨界區(qū) 啟用中斷 其余部分 } 由于臨界區(qū)不能被中斷，故可保證互斥。 ② 專用的機(jī)器指令 CPU 的設(shè)計(jì)者提供了一些硬件指令，用于保證幾個(gè)動(dòng)作的原子性。如 testset指令和 exchange指令。 return true。 } 該指令測(cè)試它的參數(shù) i的值。由于整個(gè) testset函數(shù)自動(dòng)整體執(zhí)行，就是說它不服從于任何中斷，故可實(shí)現(xiàn)進(jìn)程互斥。 void P(int i) { while ( 1 ) { while (!testset (bolt)) /*什么也不做 */。 /* 其余部分 */ } } void main( ) { bolt = 0。 } 每個(gè)進(jìn)程都在循環(huán)檢測(cè) bolt變量，當(dāng) bolt為 0時(shí)，進(jìn)程進(jìn)入臨界區(qū)；否則進(jìn)程一直循環(huán)檢測(cè)。 temp=memory。 register=temp。在執(zhí)行該指令的過程中，任何其它指令對(duì)該存儲(chǔ)器單元的訪問均被阻止。 void P(int i) { int keyi。 while (keyi != 0) exchange (keyi, bolt)。 /* 其余部分 */ } } void main( ) { 中國(guó)最大的管理資源中心 43 bolt = 0。 } 共享變量 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ī)器指令方法的特點(diǎn)： ① 優(yōu)點(diǎn)： ? 適用于在單 CPU或共享主存的多 CPU上的任何數(shù)目的進(jìn)程。 ? 可用于支持多個(gè)臨界區(qū)。因此，當(dāng)一個(gè)進(jìn)程正在等待進(jìn)入一個(gè)臨界區(qū)時(shí)，它會(huì)繼續(xù)消耗 CPU時(shí)間。當(dāng)一個(gè)進(jìn)程離開一個(gè)臨界區(qū)并且有多個(gè)進(jìn)程正在等待時(shí)，選擇哪一個(gè)等待進(jìn)程是隨意的，因此，某些進(jìn)程可能無(wú)限地被拒絕進(jìn)入?？紤]單 CPU 中的下列情況：進(jìn)程 Pl 執(zhí)行專門指令并進(jìn)入臨界區(qū)，然后 P1 被中斷并把 CPU 給具有更高優(yōu)先級(jí)的 P2。因此，它會(huì)進(jìn)入忙等待循環(huán)。 軟件方式 Dekker算法 : boolean flag [2]。 void P0( ) { while (true) { flag [0] = true。 while ( turn == 1) /* 什么也不做 */ flag [0] = true。 flag[0]= false。 while (flag[0]) if(turn==0) { flag[1] = false。 } 臨界區(qū) turn = 0。 其余部分 } } void main( )