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

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

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

3、共享系統(tǒng)中資源被多個(gè)進(jìn)程使用（4）獨(dú)立性和制約性獨(dú)立的相對(duì)速度、起始時(shí)間 進(jìn)程之間可相互作用（相互制約） 可分為直接作用和間接作用（5）程序和計(jì)算不再一一對(duì)應(yīng) （計(jì)算：一個(gè)程序的執(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è)計(jì)（Multiprogramming）,多道程序設(shè)計(jì)是指允許多個(gè)程序同時(shí)進(jìn)入內(nèi)存并運(yùn)行，引入目的是為了提高系統(tǒng)效率,考慮因

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

6、機(jī)訂票系統(tǒng)，兩個(gè)終端，運(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ù)制一個(gè)記錄,與時(shí)間有關(guān)的錯(cuò)誤（續(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è)信息長(zhǎng)度為m，有多少種可能性？,與時(shí)間有關(guān)的錯(cuò)誤（續(xù)2）,,并發(fā)環(huán)境下程序間的制約關(guān)系,與時(shí)間有關(guān)的錯(cuò)誤（續(xù)3）,二、進(jìn)

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

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

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

12、分類(lèi)：系統(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）：一個(gè)進(jìn)程已經(jīng)具備運(yùn)行條件，但由于無(wú)CPU暫時(shí)不能運(yùn)行的狀態(tài)（當(dāng)調(diào)度給其CPU時(shí)，立即可以運(yùn)行）等待態(tài)（Blocked）：阻塞態(tài)、封鎖態(tài)、睡眠態(tài)指進(jìn)程因等

13、待某種事件的發(fā)生而暫時(shí)不能運(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)行過(guò)程中，由于進(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)度程序選擇一個(gè)新的進(jìn)程運(yùn)行運(yùn)行 --> 就緒運(yùn)行進(jìn)程用完了時(shí)

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

15、標(biāo)識(shí)符已創(chuàng)建了管理進(jìn)程所需的表格但還沒(méi)有允許執(zhí)行該進(jìn)程 (尚未同意) 因?yàn)橘Y源有限,終止（退出exit)狀態(tài),中止后進(jìn)程移入該狀態(tài)它不再有執(zhí)行資格表格和其它信息暫時(shí)由輔助程序保留例子: 為處理用戶帳單而累計(jì)資源使用情況的財(cái)務(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）：把一個(gè)進(jìn)程從內(nèi)存轉(zhuǎn)到外存；可能有以下幾種情況：阻塞→阻塞掛起：沒(méi)有進(jìn)程處于就緒狀態(tài)或就緒進(jìn)程要求更多內(nèi)存資源時(shí)，發(fā)生這種轉(zhuǎn)換，以提交新進(jìn)程或運(yùn)行就緒進(jìn)程就緒→就緒掛起：當(dāng)有高優(yōu)先級(jí)阻塞（系統(tǒng)認(rèn)為會(huì)很

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、進(jìn)程有機(jī)會(huì)得到CPU的使用權(quán),前提：任何進(jìn)程無(wú)權(quán)停止其它進(jìn)程的運(yùn)行 進(jìn)程之間相對(duì)運(yùn)行速度無(wú)硬性規(guī)定進(jìn)程互斥的解決有兩種做法:由競(jìng)爭(zhēng)各方平等協(xié)商引入進(jìn)程管理者，由管理者來(lái)協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互斥資源的使用具體方法：硬件軟件,使用互斥區(qū)的原則（續(xù)）,軟件解法 (1),free: 表示臨界區(qū)標(biāo)志 true: 有進(jìn)程在臨界區(qū) false:無(wú)進(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枚舉類(lèi)型 初值任意 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)一個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí)，先調(diào)用enter_region函數(shù)，判斷是否能安全進(jìn)入，不能的話等待；當(dāng)它從臨界區(qū)退出后，需調(diào)用leave_region函數(shù)，允許其它進(jìn)程進(jìn)入臨界區(qū)。兩個(gè)函數(shù)的參數(shù)均為進(jìn)程號(hào),#define FALSE 0#

38、define TRUE 1#define N 2// 進(jìn)程的個(gè)數(shù)int turn;// 輪到誰(shuí)？int interested[N];// 興趣數(shù)組，初始值均為FALSEvoid enter_region ( int process)// process = 0 或 1{ int other;// 另外一個(gè)進(jìn)程的進(jìn)程號(hào) 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)程已離開(kāi)臨界區(qū)},Peterson算法解決了互斥訪問(wèn)的問(wèn)題，而且克服了強(qiáng)制輪流法的缺點(diǎn)，可以完全正常地工作,軟件解法(5) : Peterson算法（續(xù)2）,軟件解法的缺點(diǎn)： 1. 忙等待 2. 實(shí)現(xiàn)過(guò)于復(fù)雜，需要高的編程技巧硬件解法：提供專(zhuān)門(mén)的硬件指令，允許對(duì)一個(gè)字的內(nèi)容進(jìn)行檢測(cè)和修正，或交換兩

41、個(gè)字的內(nèi)容目的：解決共享變量的完整性和正確性 簡(jiǎn)單、有效，特別適用于多處理機(jī)缺點(diǎn)：忙等待,硬件解法 (1) “測(cè)試并設(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;,,,中斷屏蔽方法 “開(kāi)關(guān)中斷”指令,進(jìn)入臨界區(qū)前執(zhí)行： 執(zhí)行“關(guān)中斷”指令離開(kāi)臨界區(qū)后執(zhí)行： 執(zhí)行“

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

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

45、多值）（同步）,信號(hào)量及P、V操作,信號(hào)量：semaphore,是一個(gè)數(shù)據(jù)結(jié)構(gòu)定義如下： struc semaphore {int value;pointer_PCB queue; }信號(hào)量說(shuō)明： 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、等待隊(duì)列末尾s.queue; }},P、V操作,V(s){ s.value = s.value ++; if (s.value < = 0) { 喚醒相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)進(jìn)程 改變其狀態(tài)為就緒態(tài) 并將其插入就緒隊(duì)列 }},P、V操作為原語(yǔ)操作原語(yǔ)：primitive or atomic action 是由若干多機(jī)器指令構(gòu)成的完成某種特定功能的一段程序，具有不

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

48、Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號(hào)量S2,S1初值為1，S2初值為0,P： Q：while (true) { while (true) { 生產(chǎn)一個(gè)產(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)者問(wèn)題（續(xù)2）,,多個(gè)緩沖區(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; };,【思考題】要不要對(duì)緩沖區(qū)（臨界資源）進(jìn)行互斥操作？,多個(gè)緩沖區(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個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(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、 };,有錯(cuò)誤？若顛倒兩個(gè)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個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(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) 信號(hào)量的物理含義：S>0表示有S個(gè)資源可用S=0表示無(wú)資源可用S<0則| S |表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)P(S)：表示申請(qǐng)一個(gè)資源 V(S)：表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0,信號(hào)量及P、V操作討論,2) P.V

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

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

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

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

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

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

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

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