第四章 進(jìn)程管理_第1頁(yè)
已閱讀1頁(yè),還剩112頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎ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)題

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論