【正文】 ，由于規(guī)定運行時間片用完而使系統(tǒng)發(fā)出超時中斷請求，超時中斷處理程序把該進程的狀態(tài)修改為就緒狀態(tài)，并根據(jù)其自身的特征而插入就緒隊列的適當位置，保存進程現(xiàn)場信息，收回 CPU并轉(zhuǎn)入進程調(diào)度程序。另外當有終端用戶請求、父進程請求、負荷調(diào)節(jié)需要等情況時，也要用到掛起狀態(tài)。 ② 活動阻塞→靜止阻塞。 ④ 靜止阻塞→活動阻塞。為了保存這些內(nèi)容，需要建立 — 個專用數(shù)據(jù)結(jié)構(gòu)，我們稱這個數(shù)據(jù)結(jié)構(gòu)為進程控制塊 PCB （ Process Control Block）。為了標識系統(tǒng)中的各個進程，每個進程必須有惟一的標識名或標識數(shù)。 ② 位置信息。 ④ 進程的優(yōu)先級。當進程狀態(tài)變化時（例如一個進程放棄使用 CPU），它需要將當時的 CPU現(xiàn)場保護到內(nèi)存中，以便再次占用 CPU時恢復正常運行，有的系統(tǒng)把要保護的 CPU現(xiàn)場放在進程的工作區(qū)中，而 PCB中僅給出 CPU現(xiàn)場保護 區(qū)起始地址。 ⑦ 隊列指針或鏈接字。 在一個系統(tǒng)中，通?？赡苡腥舾蓚€進程同時存在，所以就擁有若干個 PCB，為了能對 PCB進行有效的管理，就要用適當?shù)姆椒ò堰@ 些 PCB組織起來。 ② 鏈接表方式：系統(tǒng)按照進程的狀態(tài)將進程的 PCB 鏈接成隊列，從而形成就緒隊列、阻塞隊列、運行隊列等。 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í)行指針 就緒隊列指針 阻塞隊列指針 空閑隊列指針 中國最大的管理資源中心 37 就緒索引 表 阻塞索引表 圖 7 索引方式組織 PCB 的示意圖 進程的特性 前面我們通過程序并發(fā)執(zhí)行時所產(chǎn)生的問題引出了進程的概念，并描述了進程、進程狀態(tài)以及進程狀態(tài)之間的轉(zhuǎn)換，現(xiàn)在，我們對進程的特征進行梳理，以便更好地理解進程。而程序是一組有序靜態(tài)指令和數(shù)據(jù)的集合，用來指示 CPU 的操作，本身并不具有運動含義，是一種靜態(tài)概念。引入進程概念的目的，也正是為了描述和實現(xiàn)并發(fā)執(zhí)行。進程是操作系統(tǒng)進行調(diào)度和分配資源的獨立單 位。它們的區(qū)別是： ① 系統(tǒng)進程是操作系統(tǒng)用來管理系統(tǒng)資源并行活動的并發(fā)軟件；用戶進程是可以獨立執(zhí)行的用戶程序段，它是操作系統(tǒng)提供服務(wù)的對象，是系統(tǒng)資源的實際使用者。無論是系統(tǒng)進程還是用戶進程，對核心層來說它們都是基本的活動單位。采用這種樹形結(jié)構(gòu)的方式，使得進程控制更為靈活方便。所以，這些操作可以用原語來實現(xiàn)。由于進程的存在是以其進程控制塊為標志的，因此，創(chuàng)建一個 新進程的主要任務(wù)是為進程建立一個進程控制塊 PCB，將調(diào)用者提供的進程 0 進程 1 進程 2 進程 3 進程 n 進程 5 進程 6 進程 4 中國最大的管理資源中心 39 有關(guān)信息填入該 PCB 中，并把該進程控制塊插入到就緒隊列中。 撤銷進程原語 進程完成了其“歷史使命”之后，應當退出系統(tǒng)而消亡，系統(tǒng)及時收回它占有的全部資源以便其它進程使用，這是通過撤銷原語完成的。 3. 阻塞進程原語 一個正在運行的進程，因為未滿足其所申請的資源而會被迫處于阻塞狀態(tài)，等待所需事件的發(fā)生，進程的這種狀態(tài)變化就是通過進程本身調(diào)用阻塞原語實現(xiàn)的。喚醒原語的基本功能是：把除了 CPU之外的一切資源都得到滿足的進程置成就緒狀態(tài)。如：計算 中國最大的管理資源中心 40 進程和打印進程，打印進程必須等待計算進程得出計算結(jié)果后，才能進行打印輸出；而計算進程必須等待打印進程將上一次計算的結(jié)果打印輸出后，才能進行下一次計算，否則就會造成混亂。 臨界資源與臨界區(qū) 系統(tǒng)中同時存在有許多進程，它們共享各種資源，然而有許多資源在某一時刻只能允許一個進程使用。 幾個進程若共享同一臨界資源，它們必須以互相排斥的方式使用這個臨界資源，即當一個進程正在使用某個臨界資源且尚未使用完畢時，其它進程必須延遲對該資源的操作，當使用該資源的進程釋放該資源時，其它進程才可使用該資源，任何進程不能從中插進去使用這個臨界資源，否則將會造成信息混亂和操作出錯。 由于對臨界資源的使用必須互斥進行，所以進程在進入臨界區(qū)時，首先判斷是否有其它進程在使用該臨界資源，如果有，則該進程必須等待，如果沒有，該進程才能進入臨界區(qū)，執(zhí)行臨界區(qū)代碼，同時，關(guān)閉臨界區(qū)，以防其它進程進入。 1. 硬件方式 ① 中斷禁用 為保證多個并發(fā)進程互斥使用臨界資源，只需保證一個進程在執(zhí)行臨界區(qū)代碼時不被中 中國最大的管理資源中心 41 斷即可，這個能力可以通過系統(tǒng)內(nèi)核為啟用和禁用中斷定義的原語提供。 ② 專用的機器指令 CPU 的設(shè)計者提供了一些硬件指令，用于保證幾個動作的原子性。 return true。由于整個 testset函數(shù)自動整體執(zhí)行，就是說它不服從于任何中斷，故可實現(xiàn)進程互斥。 /* 其余部分 */ } } void main( ) { bolt = 0。 temp=memory。在執(zhí)行該指令的過程中，任何其它指令對該存儲器單元的訪問均被阻止。 while (keyi != 0) exchange (keyi, bolt)。 } 共享變量 bolt 被初始化為 0，每個進程都使用一個局部變量 keyi 且初始化為 1，惟一可以進入臨界區(qū)的進程是發(fā)現(xiàn) bolt 等于 0的那個進程，它把 bolt 置為 1，排斥所有其它進程進入臨界區(qū)。 ? 可用于支持多個臨界區(qū)。當一個進程離開一個臨界區(qū)并且有多個進程正在等待時，選擇哪一個等待進程是隨意的，因此，某些進程可能無限地被拒絕進入。因此，它會進入忙等待循環(huán)。 void P0( ) { while (true) { flag [0] = true。 flag[0]= false。 } 臨界區(qū) turn = 0。 flag[1] = false。 Peterson算法 : boolean flag [2]={false, false}。 while( flag[1]amp。 /* 其余部分 */。amp。 } } 全局變量 flag 數(shù)組表示每個進程關(guān)于互斥的位置，全局變量 turn 解決同時沖突。實際上，進程互斥可以看作是進程同步的一種特例。如： 0 資源可用 X= 1 資源正在使用 進程使用臨界資源必須做如下三個不可分割的操作： ① 檢查 X的值。 通過以上分析，可以給出關(guān)鎖和開鎖原語的描述： 關(guān)鎖原語 lock(X) { L： if x==1 go to L else x=1。等待的過程 中國最大的管理資源中心 47 消耗了有價值的 CPU 時間，一直重復無意義的工作，降低了系統(tǒng)的速度。并且這兩個操作均屬于原子操作，不可被中斷。如果 S0，則該進程也繼續(xù)執(zhí)行。用信號量和 P/V操作實現(xiàn)進程互斥與同步的代碼結(jié)構(gòu)為： P（ S）； 臨界區(qū)； V（ S）； 例如，有兩個進程 A和 B， A進程向隊列加入一項， B 進程從該隊列中移出一項。如圖 9， P1 進程 P2 進程 緩沖區(qū) B 圖 9 進程間同步問題示意圖 進程 P1 將信息輸入到緩沖區(qū) B 中，進程 P2負責從緩沖區(qū) B 中取數(shù)據(jù)輸出，對于進程P1 來說，如果前一次輸入的數(shù)據(jù)尚未取走，則應暫時停止輸入，等待 P2 進程取走數(shù)據(jù)后再輸入新數(shù)據(jù)；而對于進程 P2 來說，如果 P1 尚未輸入數(shù)據(jù)，則應等待。 如果 P2進程先執(zhí)行，則由于 S2的初值是 0，表示緩沖區(qū)中無數(shù)據(jù)可取，執(zhí)行 P(S2)操作時，使 P2進程被阻塞掛到等待隊列上，等待緩沖區(qū)中數(shù)據(jù)的到達。 P/V操作在整個系統(tǒng)中是一一對應的，這種不可分性保證了信號量值的完整性。管程的基本思想是：把分散在各進程中的控制和管理臨界資源的臨界區(qū)集中起來統(tǒng)一管理。 進程 1 進程 1 進程 2 進程 2 進程 3 進程 3 ?? ?? ?? ?? ?? ?? 進程 n 進程 n 圖 10 管程示意圖 局部于管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)只能被管程內(nèi)的過程所訪問，而局部于管程內(nèi)的過程只能訪問該管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。 此外，當一進程進入管程執(zhí)行管程的某個過程時，如果因某種原因而被阻塞，應立即退出該管程，進入等待狀態(tài)，否則就會因阻擋其它進程進入該管程，而它本身又無法執(zhí)行造成死鎖。 把調(diào)用者進程掛在與 x相應的等待隊列 上， 。生產(chǎn)者與消費者可以通過一個環(huán)形緩沖池（見圖 11）聯(lián)系起來，環(huán)形緩沖池由幾個大小相等的緩沖塊組成，每個緩沖塊容納一個產(chǎn)品。當緩沖池全滿時，表示供過于求，生產(chǎn)者必須等待，同時喚醒消費者；當緩沖池全空時，表示供不應求，消費者應等待，同時喚醒生產(chǎn)者。 semaphore mutex=1， empty=n， full=0； int i=j=0； item buffer [n]。 V(empty)。 生產(chǎn)者消費者問題之管程解決： monitor PC。 void put(item) { if (count=n) notfull. wait。 if 。 count 。 } } void consumer( ) { while⑴ { PC. get(item)。 讀者與寫者問題 一個數(shù)據(jù)對象（比如一個文件或記錄）若被多個并發(fā)進程所共享，且其中一些進程只要 中國最大的管理資源中心 53 求讀該數(shù)據(jù)對象的內(nèi)容，而另一些進程則要求修改它，對此，可把那些只想讀的進程稱之為“讀者”，而把要求修改的進程稱為“寫者”。解決這類同步問題的基本思想是：任一寫者必須與其它寫者或讀者互斥訪問可共享的數(shù)據(jù)對象，而若干讀者可同時訪問共享的數(shù)據(jù)對象。 if (readcount== 1) P(wsem)。 readcount。 WRITE。 注意：如果一個寫者已進入臨界區(qū)且有 n 個讀者要求訪問該數(shù)據(jù)對象，則只有一個讀者進入 wsem 等待隊列，其余 n1 個讀者則進入 mutex等待隊列。這樣的結(jié)果是只要有讀者陸續(xù)到來，它們一來就被允許進入，而寫者將一直被掛起直到?jīng)]有一個讀者為止。 寫者優(yōu)先 : int readcount, writecount。 P(mrc)。 V(rsem)； V(wr)。 if (readcount ==0) V(wsem)。 if (writecount ==1) P(rse