第四章 進(jìn)程管理

1、第四章 進(jìn)程管理,多道程序設(shè)計進(jìn)程進(jìn)程間的相互作用進(jìn)程間的通信進(jìn)程（線程）調(diào)度（CPU調(diào)度）系統(tǒng)核心線程,一、多道程序設(shè)計,順序程序并發(fā)程序多道程序設(shè)計,1.順序程序,程序：指令或語句序列，體現(xiàn)了某種算法，所有程序是順序的順序環(huán)境： 在計算機(jī)系統(tǒng)中只有一個程序在運(yùn)行，這個程序獨(dú)占系統(tǒng)中所有資源，其執(zhí)行不受外界影響,特征：程序執(zhí)行的順序性程序執(zhí)行的封閉性 獨(dú)占資源，執(zhí)行過程中不受外界影響程序執(zhí)行結(jié)果的

2、確定性 即：程序結(jié)果的可再現(xiàn)性 程序運(yùn)行結(jié)果與程序執(zhí)行速度無關(guān)，只要初始狀態(tài)相同，結(jié)果應(yīng)相同,順序程序（續(xù)）,2.并發(fā)程序,并發(fā)環(huán)境： 在一定時間內(nèi)物理機(jī)器上有兩個或兩個以上的程序同處于開始運(yùn)行但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的,特征：（1）程序結(jié)果的不可再現(xiàn)性 并發(fā)程序執(zhí)行的結(jié)果與其執(zhí)行的相對速度有關(guān)，是不確定的（2）在并發(fā)環(huán)境下程序的執(zhí)行是間斷性的 執(zhí)行——?！獔?zhí)行,并發(fā)程序（續(xù)1）,（3）資源

3、共享系統(tǒng)中資源被多個進(jìn)程使用（4）獨(dú)立性和制約性獨(dú)立的相對速度、起始時間 進(jìn)程之間可相互作用（相互制約） 可分為直接作用和間接作用（5）程序和計算不再一一對應(yīng) （計算：一個程序的執(zhí)行）,并發(fā)程序（續(xù)2）,并發(fā)程序（續(xù)3）,引入并發(fā)的目的： 引入并發(fā)是為了提高資源利用率，從而提高系統(tǒng)效率并發(fā)與并行概念的區(qū)別：Concurrency，parallel,在順序環(huán)境下 CPU利用率=

4、40/80 = 50% DEV1利用率= 15/80=18.75% DEV2利用率= 25/80=31.25%,,t(s),,t(s),,并發(fā)程序（續(xù)4）,在并發(fā)環(huán)境下 CPU利用 = 89%DEV1并發(fā)環(huán)境下利用 = 33%DEV2并發(fā)環(huán)境下利用 = 66%,并發(fā)程序（續(xù)5）,3.多道程序設(shè)計（Multiprogramming）,多道程序設(shè)計是指允許多個程序同時進(jìn)入內(nèi)存并運(yùn)行，引入目的是為了提高系統(tǒng)效率,考慮因

5、素：在多道程序環(huán)境下如何向用戶提供服務(wù)在并發(fā)程序之間如何正確傳遞消息（通訊）如何對CPU進(jìn)行調(diào)度，保證每個用戶相對公平地得到CPU（CPU是一個只可調(diào)度，不可分配的資源）,如何管理其他資源 當(dāng)各用戶對資源使用上發(fā)生沖突時，如何處理競爭對CPU只能通過調(diào)度來解決競爭問題，而對于其他資源通過申請—分配—使用—回收的辦法進(jìn)行管理，當(dāng)且僅當(dāng)占有CPU的時候才可以申請，否則要排隊等候,多道程序設(shè)計（續(xù)）,4.與時間有關(guān)的錯誤,一飛

6、機(jī)訂票系統(tǒng)，兩個終端，運(yùn)行T1、T2進(jìn)程T1 : T2:... ...Read(x); Read(x);if x>=1 then if x>=1 then x:=x-1; x:=x-1;write(x); write(x);...

7、 ...,Cobegin get; copy; put;Coend,,復(fù)制一個記錄,與時間有關(guān)的錯誤（續(xù)1）,f s t g初始狀態(tài) 3,4,...,m 2 2 (1,2)g,c,p 4,5,...,m 3 3 (1,2,3) ?g,p,c 4,5,...,m 3 3 (1,2,2) Xc,g,p

8、 4,5,...,m 3 2 (1,2,2) Xc,p,g 4,5,...,m 3 2 (1,2,2) Xp,c,g 4,5,...,m 3 2 (1,2,2) Xp,g,c 4,5,...,m 3 3 (1,2,2) X 設(shè)信息長度為m，有多少種可能性？,與時間有關(guān)的錯誤（續(xù)2）,,并發(fā)環(huán)境下程序間的制約關(guān)系,與時間有關(guān)的錯誤（續(xù)3）,二、進(jìn)

9、程,進(jìn)程的概念進(jìn)程的狀態(tài)及其轉(zhuǎn)換進(jìn)程控制塊（Process Control Block）進(jìn)程的特征,進(jìn)程：為了描述程序在并發(fā)執(zhí)行時對系統(tǒng)資源的共享，所需的一個描述程序執(zhí)行時動態(tài)特征的概念OS 必須交替執(zhí)行多個進(jìn)程，以便最大程度的使用CPU，同時提供合理的響應(yīng)時間OS 必須將資源分配給進(jìn)程，同時避免死鎖OS必須支持用戶創(chuàng)建進(jìn)程OS必須支持進(jìn)程間通信,,1.進(jìn)程的概念,定義：Process 進(jìn)程是具有獨(dú)立功能的程序關(guān)于某

10、個數(shù)據(jù)集合上的一次運(yùn)行活動，是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位,進(jìn)程何時創(chuàng)建?,提交一個批處理作業(yè)用戶登錄由OS創(chuàng)建，用以向一用戶提供服務(wù)( 如：打印文件) 由已存在的一進(jìn)程創(chuàng)建一個用戶程序可創(chuàng)建成多個進(jìn)程,進(jìn)程何時中止?,批處理作業(yè)發(fā)出暫停（Halt）指令用戶退出登錄進(jìn)程執(zhí)行一中止服務(wù)請求出錯及失敗因素,進(jìn)程中止的原因,正常結(jié)束給定時限到缺少內(nèi)存存儲器出界保護(hù)性出錯例子: 寫只讀文件算術(shù)錯超出時間進(jìn)程等待

11、超過對某事件的最大值,進(jìn)程中止的原因（續(xù)1）,I/O 失敗無效指令如試圖執(zhí)行數(shù)據(jù)特權(quán)指令操作系統(tǒng)干預(yù)如當(dāng)死鎖發(fā)生時父進(jìn)程請求中止某一子進(jìn)程父進(jìn)程中止，所以子進(jìn)程也中止,程序與進(jìn)程之間的區(qū)別：,進(jìn)程更能真實地描述并發(fā)，而程序不能進(jìn)程是由程序和數(shù)據(jù)兩部分組成的程序是靜態(tài)的，進(jìn)程是動態(tài)的進(jìn)程有生命周期，有誕生有消亡，短暫的；而程序是相對長久的一個程序可對應(yīng)多個進(jìn)程，反之亦然進(jìn)程具有創(chuàng)建其他進(jìn)程的功能，而程序沒有,進(jìn)程的

12、分類：系統(tǒng)進(jìn)程用戶進(jìn)程（系統(tǒng)進(jìn)程優(yōu)先于用戶進(jìn)程）,2.進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換,進(jìn)程的三種基本狀態(tài)：進(jìn)程在生命消亡前處于且僅處于三種基本狀態(tài)之一不同系統(tǒng)設(shè)置的進(jìn)程狀態(tài)數(shù)目不同,運(yùn)行態(tài)（Running）：進(jìn)程占有CPU，并在CPU上運(yùn)行就緒態(tài)（Ready）：一個進(jìn)程已經(jīng)具備運(yùn)行條件，但由于無CPU暫時不能運(yùn)行的狀態(tài)（當(dāng)調(diào)度給其CPU時，立即可以運(yùn)行）等待態(tài)（Blocked）：阻塞態(tài)、封鎖態(tài)、睡眠態(tài)指進(jìn)程因等

13、待某種事件的發(fā)生而暫時不能運(yùn)行的狀態(tài)（即使CPU空閑，該進(jìn)程也不可運(yùn)行）,,,,,運(yùn)行,就緒,等待,,,,,進(jìn)程的狀態(tài)及其轉(zhuǎn)換,?,?,?,?,進(jìn)程狀態(tài)轉(zhuǎn)換： 在進(jìn)程運(yùn)行過程中，由于進(jìn)程自身進(jìn)展情況及外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一定的條件相互轉(zhuǎn)換 ? 就緒—運(yùn)行 ? 運(yùn)行—就緒 ? 運(yùn)行—等待 ? 等待—就緒,進(jìn)程轉(zhuǎn)換,就緒 --> 運(yùn)行調(diào)度程序選擇一個新的進(jìn)程運(yùn)行運(yùn)行 --> 就緒運(yùn)行進(jìn)程用完了時

14、間片運(yùn)行進(jìn)程被中斷，因為一高優(yōu)先級進(jìn)程處于就緒狀態(tài),進(jìn)程轉(zhuǎn)換（續(xù)1）,運(yùn)行 --> 等待當(dāng)一進(jìn)程必須等待時OS尚未完成服務(wù)對一資源的訪問尚不能進(jìn)行初始化I/O 且必須等待結(jié)果等待某一進(jìn)程提供輸入 (IPC)等待 --> 就緒當(dāng)所等待的事件發(fā)生時,其他狀態(tài)：創(chuàng)建狀態(tài)，終止?fàn)顟B(tài)掛起狀態(tài) （調(diào)節(jié)負(fù)載，對換，父進(jìn)程，操作系統(tǒng)，終端用戶）,創(chuàng)建(新new)狀態(tài),OS 已完成為創(chuàng)建一進(jìn)程所必要的工作已構(gòu)造了進(jìn)程

15、標(biāo)識符已創(chuàng)建了管理進(jìn)程所需的表格但還沒有允許執(zhí)行該進(jìn)程 (尚未同意) 因為資源有限,終止（退出exit)狀態(tài),中止后進(jìn)程移入該狀態(tài)它不再有執(zhí)行資格表格和其它信息暫時由輔助程序保留例子: 為處理用戶帳單而累計資源使用情況的財務(wù)程序當(dāng)數(shù)據(jù)不再需要后，進(jìn)程(和它的表格)被刪除,五狀態(tài)進(jìn)程模型,準(zhǔn)備退出：父進(jìn)程可中止子進(jìn)程,七狀態(tài)進(jìn)程模型,就緒狀態(tài)(Ready)：進(jìn)程在內(nèi)存且可立即進(jìn)入運(yùn)行狀態(tài)阻塞狀態(tài)(Blocked)：進(jìn)程

16、在內(nèi)存并等待某事件的出現(xiàn)阻塞掛起狀態(tài)（Blocked, suspend）：進(jìn)程在外存并等待某事件的出現(xiàn)就緒掛起狀態(tài)（Ready, suspend）：進(jìn)程在外存，但只要進(jìn)入內(nèi)存，即可運(yùn)行,七狀態(tài)進(jìn)程模型（續(xù)1）,掛起（Suspend）：把一個進(jìn)程從內(nèi)存轉(zhuǎn)到外存；可能有以下幾種情況：阻塞→阻塞掛起：沒有進(jìn)程處于就緒狀態(tài)或就緒進(jìn)程要求更多內(nèi)存資源時，發(fā)生這種轉(zhuǎn)換，以提交新進(jìn)程或運(yùn)行就緒進(jìn)程就緒→就緒掛起：當(dāng)有高優(yōu)先級阻塞（系統(tǒng)認(rèn)為會很

17、快就緒的）進(jìn)程和低優(yōu)先級就緒進(jìn)程時，系統(tǒng)會選擇掛起低優(yōu)先級就緒進(jìn)程運(yùn)行→就緒掛起：對搶占式系統(tǒng)，當(dāng)有高優(yōu)先級阻塞掛起進(jìn)程因事件出現(xiàn)而進(jìn)入就緒掛起時，系統(tǒng)可能會把運(yùn)行進(jìn)程轉(zhuǎn)到就緒掛起狀態(tài),七狀態(tài)進(jìn)程模型（續(xù)2）,激活（Activate）：把一個進(jìn)程從外存轉(zhuǎn)到內(nèi)存；可能有以下幾種情況：就緒掛起→就緒：沒有就緒進(jìn)程或掛起就緒進(jìn)程優(yōu)先級高于就緒進(jìn)程時，發(fā)生轉(zhuǎn)換阻塞掛起→阻塞：當(dāng)一個進(jìn)程釋放足夠內(nèi)存時，系統(tǒng)會把一個高優(yōu)先級阻塞掛起（系統(tǒng)認(rèn)為

18、會很快出現(xiàn)所等待的事件）進(jìn)程,七狀態(tài)進(jìn)程模型（續(xù)3）,3.進(jìn)程控制塊（Process Control Block）,概念：系統(tǒng)為了管理進(jìn)程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進(jìn)程的外部特征，描述進(jìn)程的運(yùn)動變化過程 系統(tǒng)利用PCB來控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志進(jìn)程與PCB是一一對應(yīng)的,進(jìn)程映象 (進(jìn)程要素),用戶程序用戶數(shù)據(jù)棧用于過程調(diào)用和參數(shù)傳遞進(jìn)程控制塊PCB (進(jìn)程屬性)處于核心段用戶

19、進(jìn)程不能直接訪問、修改自己的PCB,進(jìn)程映象（續(xù)）,對進(jìn)程執(zhí)行活動全過程的靜態(tài)描述 由進(jìn)程的用戶地址空間內(nèi)容、硬件寄存器內(nèi)容及與該進(jìn)程相關(guān)的核心數(shù)據(jù)結(jié)構(gòu)組成用戶級上下文：進(jìn)程的用戶地址空間（包括用戶棧各層次），包括用戶正文段、用戶數(shù)據(jù)段和用戶棧寄存器級上下文：程序寄存器、處理機(jī)狀態(tài)寄存器、棧指針、通用寄存器的值系統(tǒng)級上下文：靜態(tài)部分（PCB和資源表格）動態(tài)部分：核心棧（核心過程的棧結(jié)構(gòu)，不同進(jìn)程在調(diào)用相同核心過程時有不

20、同核心棧）,PCB的內(nèi)容,進(jìn)程描述信息：進(jìn)程標(biāo)識符(process ID)，唯一，通常是一個整數(shù)進(jìn)程名，通常基于可執(zhí)行文件名（不唯一）用戶標(biāo)識符(user ID)；進(jìn)程組關(guān)系進(jìn)程控制信息：當(dāng)前狀態(tài)優(yōu)先級(priority)代碼執(zhí)行入口地址程序的外存地址運(yùn)行統(tǒng)計信息（執(zhí)行時間、頁面調(diào)度）進(jìn)程間同步和通信；阻塞原因,PCB的內(nèi)容（續(xù)）,進(jìn)程的隊列指針進(jìn)程的消息隊列指針?biāo)鶕碛械馁Y源和使用情況：虛擬地址空間的現(xiàn)狀打開

21、文件列表CPU現(xiàn)場保護(hù)信息：寄存器值（通用、程序計數(shù)器PC、狀態(tài)PSW，地址包括棧指針）指向賦予該進(jìn)程的段/頁表的指針,PCB的內(nèi)容（續(xù)）,PCB表： 系統(tǒng)把所有PCB組織在一起，并把它們放在內(nèi)存的固定區(qū)域，就構(gòu)成了PCB表 PCB表的大小決定了系統(tǒng)中最多可同時存在的進(jìn)程個數(shù)，稱為系統(tǒng)的并發(fā)度 注：多道程序中的多道與系統(tǒng)并發(fā)度不同,PCB表組織方式,PCB表組織方式（續(xù)）,鏈接結(jié)構(gòu)：同一狀態(tài)進(jìn)程的PCB組成一個鏈

22、表，不同狀態(tài)對應(yīng)多個不同的鏈表就緒鏈表、阻塞鏈表 索引結(jié)構(gòu)：對具有相同狀態(tài)的進(jìn)程，分別設(shè)置各自的PCB索引表，表明PCB在PCB表中的地址進(jìn)程隊列：不同狀態(tài)進(jìn)程分別組成隊列運(yùn)行隊列、就緒隊列、等待隊列,PCB表組織方式（續(xù)）,4.進(jìn)程控制,創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)之間的轉(zhuǎn)換，由具有特定功能的原語完成 進(jìn)程創(chuàng)建原語 進(jìn)程撤消原語 阻塞原語 喚醒原語 掛起原語 激活（解掛）原語

23、 改變進(jìn)程優(yōu)先級,進(jìn)程的創(chuàng)建,創(chuàng)建一個PCB賦予一個統(tǒng)一進(jìn)程標(biāo)識符為進(jìn)程映象分配空間初始化進(jìn)程控制塊許多默認(rèn)值 (如: 狀態(tài)為 New，無I/O設(shè)備或文件...)設(shè)置相應(yīng)的鏈接如: 把新進(jìn)程加到就緒隊列的鏈表中,進(jìn)程撤消,收回進(jìn)程所占有的資源撤消該進(jìn)程的PCB,進(jìn)程阻塞和進(jìn)程喚醒,處于運(yùn)行狀態(tài)的進(jìn)程，在其運(yùn)行過程中期待某一事件發(fā)生，如等待鍵盤輸入、等待磁盤數(shù)據(jù)傳輸完成、等待其它進(jìn)程發(fā)送消息，當(dāng)被等待的事件未發(fā)生時，由進(jìn)程自

24、己執(zhí)行阻塞原語，使自己由運(yùn)行態(tài)變?yōu)樽枞麘B(tài),5.進(jìn)程的特征,并發(fā)性任何進(jìn)程都可以同其他進(jìn)程一起向前推進(jìn)動態(tài)性進(jìn)程對應(yīng)程序的執(zhí)行進(jìn)程是動態(tài)產(chǎn)生，動態(tài)消亡的進(jìn)程在其生命周期內(nèi)，在三種基本狀態(tài)之間轉(zhuǎn)換動態(tài)的地址空間,進(jìn)程的特征（續(xù)1）,獨(dú)立性進(jìn)程是資源分配的一個獨(dú)立單位 例如：各進(jìn)程的地址空間相互獨(dú)立交互性指進(jìn)程在執(zhí)行過程中可能與其他進(jìn)程產(chǎn)生直接或間接的關(guān)系異步性每個進(jìn)程都以其相對獨(dú)立的、不可預(yù)知的速度向

25、前推進(jìn),結(jié)構(gòu)性：進(jìn)程的組成：程序+數(shù)據(jù)+PCB可再入程序：可被多個進(jìn)程同時調(diào)用的程序，具有下列性質(zhì)：它是純代碼的，即在執(zhí)行過程中自身不改變，調(diào)用它的進(jìn)程應(yīng)該提供數(shù)據(jù)區(qū),進(jìn)程的特征（續(xù)2）,【思考題】,1．如果系統(tǒng)中有N個進(jìn)程，運(yùn)行的進(jìn)程最多幾個，最少幾個；就緒進(jìn)程最多幾個最少幾個；等待進(jìn)程最多幾個，最少幾個？2. 有沒有這樣的狀態(tài)轉(zhuǎn)換，為什么？ 等待—運(yùn)行； 就緒—等待3. 一個狀態(tài)轉(zhuǎn)換的發(fā)

26、生，是否一定導(dǎo)致另一個轉(zhuǎn)換發(fā)生，列出所有的可能4. 舉3個日常生活中類似進(jìn)程的例子,三、進(jìn)程間的相互作用,進(jìn)程間的聯(lián)系進(jìn)程的同步機(jī)制──信號量及P.V操作（解決進(jìn)程同步互斥問題）,1.進(jìn)程間的聯(lián)系,相交進(jìn)程與無關(guān)進(jìn)程相交進(jìn)程：指多個并發(fā)進(jìn)程在邏輯上有某種聯(lián)系無關(guān)進(jìn)程（不相交進(jìn)程）：在邏輯上無任何聯(lián)系的進(jìn)程,直接作用和間接作用直接作用：進(jìn)程間的相互聯(lián)系是有意識的安排的，直接作用只發(fā)生在相交進(jìn)程間間接作用：進(jìn)程間要通過某

27、種中介發(fā)生聯(lián)系，是無意識安排的，可發(fā)生在相交進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間,進(jìn)程的同步（直接作用）,進(jìn)程的同步：synchronism指系統(tǒng)中多個進(jìn)程中發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項任務(wù)。具體說，一個進(jìn)程運(yùn)行到某一點時要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài),例: 司機(jī) P1 售票員 P2 while (tr

28、ue) while (true) { { 啟動車輛； 關(guān)門； 正常運(yùn)行； 售票； 到站停車； 開門； } },進(jìn)程的互斥（間接作用）,由于各進(jìn)程要求共享資源，而有些資源需要互

29、斥使用，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥臨界資源：critical resource 系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量,臨界區(qū)（互斥區(qū)）：critical section,一個程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作 在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū) 多個進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū),,a := a

30、 -1 print (a),a := a +1 print (a),進(jìn)程的互斥（間接作用）,使用互斥區(qū)的原則,有空讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入無空等待：不允許兩個以上的進(jìn)程同時進(jìn)入互斥區(qū)多中擇一：當(dāng)沒有進(jìn)程在臨界區(qū)，而同時有多個進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入臨界區(qū)，其他進(jìn)程必須等待有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU，以使其他

31、進(jìn)程有機(jī)會得到CPU的使用權(quán),前提：任何進(jìn)程無權(quán)停止其它進(jìn)程的運(yùn)行 進(jìn)程之間相對運(yùn)行速度無硬性規(guī)定進(jìn)程互斥的解決有兩種做法:由競爭各方平等協(xié)商引入進(jìn)程管理者，由管理者來協(xié)調(diào)競爭各方對互斥資源的使用具體方法：硬件軟件,使用互斥區(qū)的原則（續(xù)）,軟件解法 (1),free: 表示臨界區(qū)標(biāo)志 true: 有進(jìn)程在臨界區(qū) false:無進(jìn)程在臨界區(qū)(初值) ....

32、 while (free); free = false; 臨界區(qū) free = true;,,,軟件解法 (2),turn: true P進(jìn)入臨界區(qū) false Q進(jìn)入臨界區(qū) ....P: while (not turn); 臨界區(qū) turn = false;Q: while (turn); 臨界區(qū) turn = true

33、;,,,,,軟件解法(3),pturn,qturn: 初值為falseP進(jìn)入臨界區(qū)的條件: pturn∧ not qturnQ進(jìn)入臨界區(qū)的條件: not pturn∧ qturn P .... Q ..... pturn = true; pturn = true; while (qturn); while (pturn); 臨界區(qū)

34、 臨界區(qū) pturn = false; qturn = false; ... ...,,,,,軟件解法(4) : Dekker算法,在解法(3)基礎(chǔ)上引入turn枚舉類型 初值任意 P : while (true) { pturn = true; while (qturn) {

35、if (turn==2) { pturn = false; while (turn==2)； pturn = true; } 臨界區(qū) turn = 2; pturn = false; ..... },軟件解法(4)（續(xù)1）,Q : while (true) {

36、 qturn = true; while (pturn) { if (turn==1) { qturn = false; while (turn==1)； qturn = true; } 臨界區(qū) turn = 1; qturn = false;

37、 ..... },軟件解法(5) : Peterson算法,enter_region ( i );臨界區(qū)leave_region ( i );非臨界區(qū),process i,當(dāng)一個進(jìn)程想進(jìn)入臨界區(qū)時，先調(diào)用enter_region函數(shù)，判斷是否能安全進(jìn)入，不能的話等待；當(dāng)它從臨界區(qū)退出后，需調(diào)用leave_region函數(shù)，允許其它進(jìn)程進(jìn)入臨界區(qū)。兩個函數(shù)的參數(shù)均為進(jìn)程號,#define FALSE 0#

38、define TRUE 1#define N 2// 進(jìn)程的個數(shù)int turn;// 輪到誰？int interested[N];// 興趣數(shù)組，初始值均為FALSEvoid enter_region ( int process)// process = 0 或 1{ int other;// 另外一個進(jìn)程的進(jìn)程號 other =

39、 1 - process; interested[process] = TRUE;// 表明本進(jìn)程感興趣 turn = process;// 設(shè)置標(biāo)志位 while( turn == process && interested[other] == TRUE);},軟件解法(5) : Peterson算法（續(xù)1）,void leave_region

40、( int process){ interested[process] = FALSE;// 本進(jìn)程已離開臨界區(qū)},Peterson算法解決了互斥訪問的問題，而且克服了強(qiáng)制輪流法的缺點，可以完全正常地工作,軟件解法(5) : Peterson算法（續(xù)2）,軟件解法的缺點： 1. 忙等待 2. 實現(xiàn)過于復(fù)雜，需要高的編程技巧硬件解法：提供專門的硬件指令，允許對一個字的內(nèi)容進(jìn)行檢測和修正，或交換兩

41、個字的內(nèi)容目的：解決共享變量的完整性和正確性 簡單、有效，特別適用于多處理機(jī)缺點：忙等待,硬件解法 (1) “測試并設(shè)置”指令,boolean TS (boolean *lock) { boolean old; old = *lock; *lock = true; },while TS(&lock); 臨界區(qū) lock = false;,,,硬件解法 (2) “交換”指

42、令,void SWAP(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;},key = true; do { SWAP(&lock,key); }while(key); 臨界區(qū) lock:=false;,,,中斷屏蔽方法 “開關(guān)中斷”指令,進(jìn)入臨界區(qū)前執(zhí)行： 執(zhí)行“關(guān)中斷”指令離開臨界區(qū)后執(zhí)行： 執(zhí)行“

43、開中斷”指令簡單，有效較高的代價，限制CPU并發(fā)能力（臨界區(qū)小）不適應(yīng)多處理器,2.進(jìn)程的同步機(jī)制──信號量及P.V操作,以上介紹的各種算法都存在問題，它們是平等進(jìn)程間的一種協(xié)商機(jī)制，需要一個地位高于進(jìn)程的管理者來解決公有資源的使用問題 操作系統(tǒng)可從進(jìn)程管理者的角度來處理互斥的問題，信號量就是操作系統(tǒng)提供的管理公有資源的有效手段,進(jìn)程的同步機(jī)制（續(xù)）,同步機(jī)制： 信號量及P、V操作；管程；條件臨界域；路徑表達(dá)式

44、等（用于集中式系統(tǒng)中） 會合；通信順序進(jìn)程；分布進(jìn)程；遠(yuǎn)程過程調(diào)用等（適用于分布式系統(tǒng)中）,同步機(jī)制應(yīng)滿足的基本要求：* 描述能力* 可以實現(xiàn)* 效率高* 使用方便,進(jìn)程的同步機(jī)制（續(xù)）,1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)）一種卓有成效的進(jìn)程同步機(jī)制最初提出的是二元信號量（互斥） 推廣到一般信號量（

45、多值）（同步）,信號量及P、V操作,信號量：semaphore,是一個數(shù)據(jù)結(jié)構(gòu)定義如下： struc semaphore {int value;pointer_PCB queue; }信號量說明： semaphore s;,P、V操作,P(s){ s.value = s.value --; if (s.value < 0) { 該進(jìn)程狀態(tài)置為等待狀態(tài) 將該進(jìn)程的PCB插入相應(yīng)的

46、等待隊列末尾s.queue; }},P、V操作,V(s){ s.value = s.value ++; if (s.value < = 0) { 喚醒相應(yīng)等待隊列s.queue中等待的一個進(jìn)程 改變其狀態(tài)為就緒態(tài) 并將其插入就緒隊列 }},P、V操作為原語操作原語：primitive or atomic action 是由若干多機(jī)器指令構(gòu)成的完成某種特定功能的一段程序，具有不

47、可分割性即原語的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷 實現(xiàn)：開關(guān)中斷,信號量及P、V操作（續(xù)1）,信號量的使用： 必須置一次且只能置一次初值 初值不能為負(fù)數(shù) 只能執(zhí)行P、V操作,信號量及P、V操作（續(xù)2）,用P、V操作解決進(jìn)程間互斥問題,經(jīng)典的生產(chǎn)者─消費(fèi)者問題,消費(fèi)者,生產(chǎn)者,經(jīng)典的生產(chǎn)者─消費(fèi)者問題（續(xù)1）,同步問題： P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為S1

48、Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量S2,S1初值為1，S2初值為0,P： Q：while (true) { while (true) { 生產(chǎn)一個產(chǎn)品; P(s2); P(s1) ; 從緩沖區(qū)取產(chǎn)品; 送產(chǎn)品到緩沖區(qū);

49、V(s1); V(s2); 消費(fèi)產(chǎn)品;}; };,經(jīng)典的生產(chǎn)者─消費(fèi)者問題（續(xù)2）,,多個緩沖區(qū)的生產(chǎn)者和消費(fèi)者,P：i = 0;while (true) { 生產(chǎn)產(chǎn)品; P(S1); 往Buffer [i]放產(chǎn)品; V(S2); i = (i+1) % n;

50、};,Q： j = 0; while (true) { P(S2); 從Buffer[j]取產(chǎn)品; V(S1); 消費(fèi)產(chǎn)品; j = (j+1) % n; };,【思考題】要不要對緩沖區(qū)（臨界資源）進(jìn)行互斥操作？,多個緩沖區(qū)的生產(chǎn)者和消費(fèi)者（續(xù)）,Q： j = 0; while (true) { P(S2); P(mutex);

51、 從Buffer[j]取產(chǎn)品; V(mutex); V(S1); 消費(fèi)產(chǎn)品; j = (j+1) % n; };,n個緩沖區(qū)、m個生產(chǎn)者和k個消費(fèi)者,P：i = 0;while (true) { 生產(chǎn)產(chǎn)品; P(S1); P(mutex); 往Buffer [i]放產(chǎn)品; V(mutex); V(S2); i = (i+1) % n;

52、 };,有錯誤？若顛倒兩個P操作的順序？,Q： j = 0; while (true) { P(S2); P(mutex2); 從Buffer[j]取產(chǎn)品; j = (j+1) % n; V(mutex2); V(S1); 消費(fèi)產(chǎn)品;};,n個緩沖區(qū)、m個生產(chǎn)者和k個消費(fèi)者,P：i = 0;while (true) { 生產(chǎn)產(chǎn)品; P(S1

53、); P(mutex1); 往Buffer [i]放產(chǎn)品; i = (i+1) % n; V(mutex1); V(S2); };,正確,1) 信號量的物理含義：S>0表示有S個資源可用S=0表示無資源可用S<0則| S |表示S等待隊列中的進(jìn)程個數(shù)P(S)：表示申請一個資源 V(S)：表示釋放一個資源。信號量的初值應(yīng)該大于等于0,信號量及P、V操作討論,2) P.V

54、操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作當(dāng)為互斥操作時，它們同處于同一進(jìn)程當(dāng)為同步操作時，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要,一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前而兩個V操作無關(guān)緊要,信號量及P、V操作討論（續(xù)1）,3）P.V操作的優(yōu)缺點優(yōu)點： 簡單，而且表達(dá)能力強(qiáng)（用P.V操作可解決任何同步互斥問題）缺點： 不夠安全

55、；P.V操作使用不當(dāng)會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜,信號量及P、V操作討論（續(xù)2）,3.信號量集——AND型信號量集,AND型信號量集是指同時需要多種資源且每種占用一個時的信號量操作 AND型信號量集的基本思想：在一個原語中申請整段代碼需要的多個臨界資源，要么全部分配給它，要么一個都不分配AND型信號量集P原語為SwaitAND型信號量集V原語為Ssignal,Swait(S1, S2, …, Sn)//P原語；

56、{while (TRUE) {if (S1 >=1 && S2 >= 1 && … && Sn >= 1){//滿足資源要求時的處理； for (i = 1; i <= n; ++i) -–Si; //注：與P的處理不同，這里是在確信可滿足 // 資源要求時，才進(jìn)行減1操作；break;}else {//某些資源不夠時的

57、處理； 調(diào)用進(jìn)程進(jìn)入第一個小于1信號量的等待隊列Sj.queue; 阻塞調(diào)用進(jìn)程; }}},信號量集——AND型信號量集（續(xù)）,Ssignal(S1, S2, …, Sn){for (i = 1; i <= n; ++i) { ++Si;//釋放占用的資源； for (在Si.queue中等待的每一個進(jìn)程P) //檢查每種資源的等待隊列的所有進(jìn)程； { 從等

58、待隊列Si.queue中取出進(jìn)程P;,信號量集——AND型信號量集（續(xù)1）,if (判斷進(jìn)程P是否通過Swait中的測試) //注：與signal不同，這里要進(jìn)行重新判斷； {//通過檢查（資源夠用）時的處理； 進(jìn)程P進(jìn)入就緒隊列; } else {//未通過檢查（資源不夠用）時的處理； 進(jìn)程P進(jìn)入某等待隊列； } } }},信號量集——

59、AND型信號量集（續(xù)2）,采用AND信號量集解決生產(chǎn)者-消費(fèi)者問題：Swait(empty, mutex), Ssignal(full, mutex),信號量集——AND型信號量集（續(xù)3）,一般“信號量集”,一般信號量集是指同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的信號量處理 （一次需要N個某類臨界資源時，就要進(jìn)行N次wait操作－－低效又可能死鎖）一般信號量集的基本思路就是在AND型信號量集的基

60、礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語操作中完成所有的資源申請,進(jìn)程對信號量Si的測試值為ti（表示信號量的判斷條件，要求Si >= ti；即當(dāng)資源數(shù)量低于ti時，便不予分配）占用值為di（表示資源的申請量，即Si = Si - di）對應(yīng)的P、V原語格式為：Swait(S1, t1, d1; ...; Sn, tn, dn);Ssignal(S1, d1; ...; Sn, dn);,一般“信號量集”（續(xù)）,一般“信號量集”可以

61、用于各種情況的資源分配和釋放，幾種特殊情況：,Swait(S, d, d)表示每次申請d個資源，當(dāng)少于d個時，便不分配Swait(S, 1, 1)表示互斥信號量Swait(S, 1, 0)可作為一個可控開關(guān)（當(dāng)S?1時，允許多個進(jìn)程進(jìn)入臨界區(qū)；當(dāng)S=0時，禁止任何進(jìn)程進(jìn)入臨界區(qū)）一般"信號量集"未必成對使用Swait和Ssignal：如：一起申請，但不一起釋放,,【思考題】,1.用P.V操作解決下圖之同步問題