操作系統(tǒng)第二章-課件

第二章進(jìn)程管理2.1進(jìn)程的基本概念2.2進(jìn)程控制2.3進(jìn)程同步2.4經(jīng)典進(jìn)程的同步問題2.52.6進(jìn)程通信2.7

線程7/23/20231第二章進(jìn)程管理2.1進(jìn)程的基本概念

2.1.1前趨圖

2.1.2程序的順序執(zhí)行及其特征

2.1.3程序的并發(fā)執(zhí)行及其特征

2.1.4

進(jìn)程的特征與狀態(tài)

2.1.5進(jìn)程控制塊7/23/20232第二章進(jìn)程管理前驅(qū)圖(PrecedenceGraph)前驅(qū)圖是一個(gè)有向無循環(huán)圖，圖中的每個(gè)結(jié)點(diǎn)可用于表示一條語句，一個(gè)程序段或進(jìn)程；結(jié)點(diǎn)間的有向邊則表示在兩結(jié)點(diǎn)之間存在的偏序或前驅(qū)關(guān)系。P1P2P3P4P5P6P7P8P9結(jié)點(diǎn)、有向邊、直接前驅(qū)、直接后繼、初始結(jié)點(diǎn)、終止結(jié)點(diǎn)無循環(huán)關(guān)系，可實(shí)現(xiàn)順序執(zhí)行7/23/20233第二章進(jìn)程管理程序的順序執(zhí)行程序是一個(gè)靜態(tài)的概念，是嚴(yán)格按次序執(zhí)行的計(jì)算機(jī)操作序列的集合，體現(xiàn)了編程人員要求計(jì)算機(jī)完成相應(yīng)功能時(shí)所應(yīng)采取的順序步驟。一個(gè)較大的程序通常都是由若干個(gè)程序段組成。在程序執(zhí)行時(shí)，必須按照某種先后次序逐個(gè)執(zhí)行，僅當(dāng)前一操作執(zhí)行完后，才能執(zhí)行后繼操作。例如：在進(jìn)行計(jì)算時(shí)，總是先輸入用戶的程序和數(shù)據(jù)，然后才能計(jì)算，計(jì)算完成后再將結(jié)果打印出來。7/23/20234第二章進(jìn)程管理程序的順序執(zhí)行如圖I1P1O1I2P2O2作業(yè)1作業(yè)2在計(jì)算機(jī)系統(tǒng)中只有一個(gè)程序在運(yùn)行，這個(gè)程序獨(dú)占系統(tǒng)中所有資源，其執(zhí)行不受外界影響。一道程序執(zhí)行完后另一道才能開始。程序的順序執(zhí)行7/23/20235第二章進(jìn)程管理程序的順序執(zhí)行一個(gè)程序的多條語句的順序執(zhí)行：S1:a:=x+yS2:b:=a-5S3:c:=b+1S1S2S37/23/20236第二章進(jìn)程管理程序順序執(zhí)行的特點(diǎn)順序性：一個(gè)程序開始執(zhí)行必須要等到前一個(gè)程序已執(zhí)行完成。封閉性：程序一旦開始執(zhí)行，其計(jì)算結(jié)果不受外界因素影響?？稍佻F(xiàn)性：程序的結(jié)果與它的執(zhí)行速度無關(guān)（即與時(shí)間無關(guān)），只要給定相同的輸入，一定會(huì)得到相同的結(jié)果。7/23/20237第二章進(jìn)程管理多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化計(jì)算機(jī)能夠同時(shí)處理多個(gè)具有獨(dú)立功能的程序（批處理系統(tǒng)，分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)、網(wǎng)絡(luò)與分布式系統(tǒng)）。這樣的執(zhí)行環(huán)境具有三個(gè)特點(diǎn)：

獨(dú)立性:每道程序都是邏輯上獨(dú)立的，之間不存在制約關(guān)系。

隨機(jī)性：程序和數(shù)據(jù)的輸入與開始執(zhí)行時(shí)間都是隨機(jī)的。這種隨機(jī)性形成了操作系統(tǒng)必須同時(shí)處理多道程序的客觀要求。

資源共享硬件資源：CPU、輸入輸出設(shè)備，存儲器軟件資源：各種例行程序、各種共享的數(shù)據(jù)多道程序環(huán)境下執(zhí)行程序的道數(shù)>計(jì)算機(jī)系統(tǒng)中CPU的個(gè)數(shù)單CPU中，則有N－1道程序處在等待CPU的狀態(tài)輸入輸出設(shè)備有限將導(dǎo)致這些設(shè)備被共享、內(nèi)存有限將導(dǎo)致內(nèi)存被共享7/23/20238第二章進(jìn)程管理程序的并發(fā)執(zhí)行I1P1O1I2P2O2I3P3O3所謂程序的并發(fā)執(zhí)行是指：若干個(gè)程序同時(shí)在系統(tǒng)中執(zhí)行，這些程序的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序的執(zhí)行尚未結(jié)束，另一個(gè)程序的執(zhí)行已經(jīng)開始。

7/23/20239第二章進(jìn)程管理程序的并發(fā)執(zhí)行一個(gè)程序的多條語句的并發(fā)執(zhí)行：S1:a:=x+2S2:b:=y+5S3:c:=a+bS4:d:=c+6S1S3S4S27/23/202310第二章進(jìn)程管理程序并發(fā)執(zhí)行的特點(diǎn)

間斷性

“走走停?！?，一個(gè)程序可能走到中途停下來，失去原有的時(shí)序關(guān)系

失去程序的封閉性

多個(gè)程序共享系統(tǒng)中的資源，這些資源的狀態(tài)將由多個(gè)程序來改變。如：一個(gè)程序?qū)懙酱鎯ζ髦械臄?shù)據(jù)可能被另一個(gè)程序修改，失去原有的不變特征。

不可再現(xiàn)性失去封閉性→失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征。7/23/202311第二章進(jìn)程管理abefabeftopabeftop例：設(shè)有堆棧S，棧指針top，棧中存放內(nèi)存中相應(yīng)數(shù)據(jù)塊地址，設(shè)有兩個(gè)程序段getaddr（top）和reladdr（blk），其中g(shù)etaddr（top）從給定的top所指棧中取出相應(yīng)的內(nèi)存數(shù)據(jù)塊地址，而reladdr（blk）則將內(nèi)存數(shù)據(jù)塊地址blk放入堆棧S中。Getaddr接著執(zhí)行Reladdr先執(zhí)行top執(zhí)行top=top＋1后中斷7/23/202312第二章進(jìn)程管理程序并發(fā)執(zhí)行的特點(diǎn)例：程序A、B，共享變量N，程序A，只有一個(gè)語句N:=N+1；程序B由兩個(gè)語句Print(N)，N=0組成。兩個(gè)程序以不同速度運(yùn)行，可能出現(xiàn)三種情況：N:=N+1在Print(N)和N=0之前，此時(shí)N值分為N+1,N+1,0N:=N+1在Print(N)和N=0之后，此時(shí)N值分為N,0,1N:=N+1在Print(N)和N=0之間，此時(shí)N值分為N,N+1,0問題：并發(fā)與并行的區(qū)別是什么？7/23/202313第二章進(jìn)程管理并行與并發(fā)的概念差別

并行（Parallel）同一時(shí)刻，兩個(gè)事物均處于活動(dòng)狀態(tài)并發(fā)（Concurrency）宏觀上存在并行特征，微觀上存在順序性同一時(shí)刻，只有一個(gè)事物處于活動(dòng)狀態(tài)7/23/202314第二章進(jìn)程管理并發(fā)所帶來的效率提升7/23/202315第二章進(jìn)程管理并發(fā)所帶來的效率提升順序執(zhí)行模式下的系統(tǒng)工作效率系統(tǒng)總運(yùn)行時(shí)間：80CPU使用效率：CPU占用時(shí)間/總時(shí)間＝40/80=50%DEV1使用效率：15/80＝18.75%DEV2使用效率：25/80=31.25%并發(fā)執(zhí)行模式下的系統(tǒng)工作效率系統(tǒng)總運(yùn)行時(shí)間：45CPU使用效率：40/45=89%DEV1使用效率：15/45=33%DEV2使用效率：25/45＝55.6%7/23/202316第二章進(jìn)程管理進(jìn)程的引入并發(fā)執(zhí)行的各程序段由于同時(shí)存在于主存中，共享軟硬件資源，造成其執(zhí)行結(jié)果受執(zhí)行速度影響的局面。在多道程序系統(tǒng)所帶來的復(fù)雜環(huán)境中，程序段具有了并發(fā)、制約、動(dòng)態(tài)的特性，原來的程序概念，難以刻畫系統(tǒng)中的情況。

程序本身完全是靜態(tài)的概念

程序概念也反映不了系統(tǒng)中的并發(fā)特性為了控制和協(xié)調(diào)各程序段執(zhí)行過程中的軟硬件資源共享和競爭，必須有一個(gè)描述各程序執(zhí)行過程和共享資源的基本單位。（這個(gè)單位被稱為進(jìn)程，或任務(wù)task）

7/23/202317第二章進(jìn)程管理

進(jìn)程的定義

進(jìn)程的概念是60年代初首先由MIT的MULTICS系統(tǒng)和IBM公司的TSS/360系統(tǒng)引入的。進(jìn)程有很多各式各樣的定義，如：

（1）進(jìn)程是可以并發(fā)執(zhí)行的計(jì)算部分（2）進(jìn)程是一個(gè)獨(dú)立的可以調(diào)度的活動(dòng)（3）進(jìn)程是一個(gè)抽象的實(shí)體，當(dāng)它執(zhí)行某個(gè)任務(wù)時(shí)，將要分配和釋放各種資源（4）行為的規(guī)則叫程序，程序在處理機(jī)上執(zhí)行的活動(dòng)稱為進(jìn)程。（5）一個(gè)進(jìn)程是一系列逐一執(zhí)行的操作，而操作的確切含義則有賴于以何種詳盡程度來描述進(jìn)程。7/23/202318第二章進(jìn)程管理

進(jìn)程的定義進(jìn)程是可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程。或是指進(jìn)程實(shí)體的運(yùn)行過程。7/23/202319第二章進(jìn)程管理閱讀菜譜準(zhǔn)備原料烹制菜肴飯菜閱讀洗衣機(jī)手冊準(zhǔn)備衣服、洗衣粉設(shè)定參數(shù)，洗衣服干凈衣服程序輸入運(yùn)行輸出程序輸入運(yùn)行輸出分時(shí)切換洗衣進(jìn)程做飯進(jìn)程進(jìn)程同程序的比較7/23/202320第二章進(jìn)程管理進(jìn)程同程序的比較程序是指令的有序集合，其本身沒有任何運(yùn)行的含義，是一個(gè)靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，它是一個(gè)動(dòng)態(tài)的概念；程序可以作為一種軟件資料長期存在，而進(jìn)程是有一定生命期的。程序是永久的，進(jìn)程是暫時(shí)的；7/23/202321第二章進(jìn)程管理進(jìn)程同程序的比較進(jìn)程更能真實(shí)地描述并發(fā)，而程序不能；進(jìn)程是由程序和數(shù)據(jù)、進(jìn)程控制塊三部分組成的；進(jìn)程具有創(chuàng)建其他進(jìn)程的功能，而程序沒有同一程序同時(shí)運(yùn)行于若干個(gè)數(shù)據(jù)集合上，它將屬于若干個(gè)不同的進(jìn)程。也就是說同一程序可以對應(yīng)多個(gè)進(jìn)程7/23/202322第二章進(jìn)程管理

進(jìn)程的特征結(jié)構(gòu)特征：由程序段、數(shù)據(jù)段、進(jìn)程控制塊三部分組成；動(dòng)態(tài)性：進(jìn)程是程序的執(zhí)行；并發(fā)性：多個(gè)進(jìn)程可同存于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)運(yùn)行；7/23/202323第二章進(jìn)程管理

進(jìn)程的特征獨(dú)立性：獨(dú)立運(yùn)行的基本單位，獨(dú)立獲得資源和調(diào)度的基本單位；異步性：各進(jìn)程按各自獨(dú)立的不可預(yù)知的速度向前推進(jìn)。7/23/202324第二章進(jìn)程管理進(jìn)程的狀態(tài)及其轉(zhuǎn)換不同系統(tǒng)設(shè)置的進(jìn)程狀態(tài)數(shù)目不同進(jìn)程有三種基本狀態(tài)： 進(jìn)程在生命期內(nèi)，至少具有三種基本狀態(tài)：執(zhí)行狀態(tài)、等待狀態(tài)和就緒狀態(tài)。7/23/202325第二章進(jìn)程管理進(jìn)程的三種基本狀態(tài)就緒狀態(tài)（Ready）：已經(jīng)得到除CPU之外的其他資源的那些進(jìn)程，它們已經(jīng)準(zhǔn)備就緒，一旦得到CPU，就立即可以運(yùn)行。這些進(jìn)程所處的狀態(tài)為就緒狀態(tài)。就緒隊(duì)列：常按照進(jìn)程優(yōu)先權(quán)的大小排列，把優(yōu)先權(quán)高的進(jìn)程的PCB排在隊(duì)列前面。7/23/202326第二章進(jìn)程管理進(jìn)程的三種基本狀態(tài)運(yùn)行狀態(tài)（Running）：正在運(yùn)行的進(jìn)程所處的狀態(tài)為運(yùn)行狀態(tài)。單處理機(jī)系統(tǒng)，任一時(shí)刻只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)多處理機(jī)系統(tǒng)有多個(gè)進(jìn)程處于運(yùn)行狀態(tài)只有處于就緒狀態(tài)的進(jìn)程經(jīng)調(diào)度選中之后才可進(jìn)入執(zhí)行狀態(tài)7/23/202327第二章進(jìn)程管理進(jìn)程的三種基本狀態(tài)等待狀態(tài)（Wait/Blocked）：若一進(jìn)程正在等待某一事件發(fā)生（如等待輸入輸出工作完成），這時(shí)，即使給它CPU，它也無法運(yùn)行，稱該進(jìn)程處于等待狀態(tài)、阻塞、睡眠、封鎖狀態(tài)。阻塞隊(duì)列根據(jù)阻塞原因可以設(shè)置多個(gè)隊(duì)列。7/23/202328第二章進(jìn)程管理進(jìn)程的狀態(tài)變遷圖7/23/202329第二章進(jìn)程管理進(jìn)程的狀態(tài)轉(zhuǎn)換①就緒→執(zhí)行：調(diào)度②執(zhí)行→等待：等待某個(gè)事件發(fā)生而睡眠③等待→就緒：因等待的事件發(fā)生而喚醒④執(zhí)行→就緒：時(shí)間片用完問題1：為什么不能從等待態(tài)變?yōu)檫\(yùn)行態(tài)呢？問題2：為什么不能從就緒態(tài)變?yōu)榈却龖B(tài)呢？答案：阻塞進(jìn)程即使被給予CPU，也無法運(yùn)行。理論上這種狀態(tài)轉(zhuǎn)換是可行的，只是沒有實(shí)際價(jià)值而被操作系統(tǒng)禁止對于就緒狀態(tài)的進(jìn)程，因沒有執(zhí)行，自然無法進(jìn)入到阻塞狀態(tài)。這種狀態(tài)轉(zhuǎn)換理論上不可行7/23/202330第二章進(jìn)程管理五狀態(tài)進(jìn)程模型增加了“創(chuàng)建”、“終止”兩種狀態(tài)創(chuàng)建狀態(tài)(New)：創(chuàng)建一個(gè)進(jìn)程要通過兩個(gè)步驟：首先，為一個(gè)新進(jìn)程創(chuàng)建PCB，并填寫必要的管理信息；其次，把該進(jìn)程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊(duì)列中。當(dāng)一個(gè)新進(jìn)程被創(chuàng)建時(shí)，系統(tǒng)已為其分配了PCB，填寫了進(jìn)程標(biāo)識等信息，但由于該進(jìn)程所必需的資源或其他信息沒有獲得，進(jìn)程自身還未進(jìn)入主存，即創(chuàng)建工作尚未完成，進(jìn)程還不能被調(diào)度運(yùn)行。引入創(chuàng)建狀態(tài)，是為了保證進(jìn)程的調(diào)度必須在創(chuàng)建工作完成后進(jìn)行，以確保對PCB操作的完整性。同時(shí)，也增加了管理的靈活性，操作系統(tǒng)可以根據(jù)系統(tǒng)性能或主存容量的限制，推遲創(chuàng)建狀態(tài)進(jìn)程的提交。對于處于創(chuàng)建狀態(tài)的進(jìn)程，獲得了其所必需的資源，以及對其PCB初始化工作完成后，進(jìn)程狀態(tài)便可由創(chuàng)建狀態(tài)轉(zhuǎn)入就緒狀態(tài)了。

7/23/202331第二章進(jìn)程管理結(jié)束狀態(tài)(Exit)：進(jìn)程的結(jié)束也要通過兩個(gè)步驟：首先等待操作系統(tǒng)進(jìn)行善后處理，然后將其PCB清零，并將PCB空間返還系統(tǒng)。當(dāng)一個(gè)進(jìn)程到達(dá)了自然結(jié)束點(diǎn)，或是出現(xiàn)了無法克服的錯(cuò)誤，或是被操作系統(tǒng)所終結(jié)，或是被其他有終止權(quán)的進(jìn)程所終結(jié)，它將進(jìn)入結(jié)束狀態(tài)。進(jìn)入結(jié)束狀態(tài)的進(jìn)程以后不能再執(zhí)行，但在操作系統(tǒng)中依然保留一個(gè)紀(jì)錄，其中保存狀態(tài)碼和一些計(jì)時(shí)統(tǒng)計(jì)數(shù)據(jù)，供其他進(jìn)程收集。一旦其他進(jìn)程完成了對結(jié)束狀態(tài)進(jìn)程的信息提取之后，操作系統(tǒng)將刪除該進(jìn)程。對于一個(gè)進(jìn)程來說“創(chuàng)建狀態(tài)”和“結(jié)束狀態(tài)”只有一次。五狀態(tài)進(jìn)程模型7/23/202332第二章進(jìn)程管理五狀態(tài)進(jìn)程模型7/23/202333第二章進(jìn)程管理五狀態(tài)進(jìn)程模型創(chuàng)建新進(jìn)程：創(chuàng)建一個(gè)新進(jìn)程，以運(yùn)行一個(gè)程序?？赡艿脑?yàn)椋河脩舻卿?、OS創(chuàng)建以提供某項(xiàng)服務(wù)、批處理作業(yè)。收容(Admit,也稱為提交)：收容一個(gè)新進(jìn)程，進(jìn)入就緒狀態(tài)。由于性能、內(nèi)存、進(jìn)程總數(shù)等原因，系統(tǒng)會(huì)限制并發(fā)進(jìn)程總數(shù)。釋放(Release)：由于進(jìn)程完成或失敗而終止進(jìn)程運(yùn)行，進(jìn)入結(jié)束狀態(tài)；運(yùn)行到結(jié)束：分為正常退出Exit和異常退出abort（執(zhí)行超時(shí)或內(nèi)存不夠，非法指令或地址，I/O失敗，被其他進(jìn)程所終止）7/23/202334第二章進(jìn)程管理五狀態(tài)進(jìn)程模型注：對于五狀態(tài)進(jìn)程模型，一個(gè)重要的問題是當(dāng)一個(gè)事件出現(xiàn)時(shí)如何檢查阻塞進(jìn)程表中的進(jìn)程狀態(tài)。當(dāng)進(jìn)程多時(shí)，對系統(tǒng)性能影響很大。一種可能的作法是按等待事件類型，排成多個(gè)隊(duì)列。7/23/202335第二章進(jìn)程管理五狀態(tài)進(jìn)程模型(單隊(duì)列結(jié)構(gòu))7/23/202336第二章進(jìn)程管理五狀態(tài)進(jìn)程模型(多隊(duì)列結(jié)構(gòu))7/23/202337第二章進(jìn)程管理七狀態(tài)進(jìn)程模型針對進(jìn)程的存在位置（內(nèi)存或者外存），進(jìn)一步增加“阻塞掛起”和“就緒掛起”兩種狀態(tài)這個(gè)問題的出現(xiàn)是由于進(jìn)程優(yōu)先級的引入，一些低優(yōu)先級進(jìn)程可能等待較長時(shí)間，從而被對換至外存。這樣做的目的是：提高處理機(jī)效率：就緒進(jìn)程表為空時(shí)，要提交新進(jìn)程，以提高處理機(jī)效率；為運(yùn)行進(jìn)程提供足夠內(nèi)存：資源緊張時(shí)，暫停某些進(jìn)程，如：CPU繁忙（或?qū)崟r(shí)任務(wù)執(zhí)行），內(nèi)存緊張用于調(diào)試：在調(diào)試時(shí)，掛起被調(diào)試進(jìn)程（從而對其地址空間進(jìn)行讀寫）7/23/202338第二章進(jìn)程管理七狀態(tài)進(jìn)程模型活動(dòng)掛起事件發(fā)生事件發(fā)生等待事件掛起調(diào)度超時(shí)釋放活動(dòng)掛起7/23/202339第二章進(jìn)程管理就緒狀態(tài)(Ready)：進(jìn)程在內(nèi)存且可立即進(jìn)入運(yùn)行狀態(tài)；阻塞狀態(tài)(Blocked)：進(jìn)程在內(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)。七狀態(tài)進(jìn)程模型——狀態(tài)7/23/202340第二章進(jìn)程管理七狀態(tài)進(jìn)程模型——轉(zhuǎn)換掛起（Suspend）：把一個(gè)進(jìn)程從內(nèi)存轉(zhuǎn)到外存；可能有以下幾種情況：阻塞到阻塞掛起：沒有進(jìn)程處于就緒狀態(tài)或就緒進(jìn)程要求更多內(nèi)存資源時(shí)，會(huì)進(jìn)行這種轉(zhuǎn)換，以提交新進(jìn)程或運(yùn)行就緒進(jìn)程；就緒到就緒掛起：當(dāng)有高優(yōu)先級阻塞（系統(tǒng)認(rèn)為會(huì)很快就緒的）進(jìn)程和低優(yōu)先級就緒進(jìn)程時(shí)，系統(tǒng)會(huì)選擇掛起低優(yōu)先級就緒進(jìn)程；運(yùn)行到就緒掛起：對搶先式分時(shí)系統(tǒng)，當(dāng)有高優(yōu)先級阻塞掛起進(jìn)程因事件出現(xiàn)而進(jìn)入就緒掛起時(shí)，系統(tǒng)可能會(huì)把運(yùn)行進(jìn)程轉(zhuǎn)到就緒掛起狀態(tài)；收容(Admit)：收容一個(gè)新進(jìn)程，進(jìn)入就緒狀態(tài)或就緒掛起狀態(tài)。進(jìn)入就緒掛起的原因是系統(tǒng)希望保持一個(gè)大的就緒進(jìn)程表（掛起和非掛起）；7/23/202341第二章進(jìn)程管理七狀態(tài)進(jìn)程模型——轉(zhuǎn)換

激活（Activate）：把一個(gè)進(jìn)程從外存轉(zhuǎn)到內(nèi)存；可能有以下幾種情況：就緒掛起到就緒：沒有就緒進(jìn)程或就緒掛起進(jìn)程優(yōu)先級高于就緒進(jìn)程時(shí)，會(huì)進(jìn)行這種轉(zhuǎn)換；阻塞掛起到阻塞：當(dāng)一個(gè)進(jìn)程釋放足夠內(nèi)存時(shí)，系統(tǒng)會(huì)把一個(gè)高優(yōu)先級阻塞掛起（系統(tǒng)認(rèn)為會(huì)很快出現(xiàn)所等待的事件）進(jìn)程轉(zhuǎn)換為阻塞進(jìn)程；事件出現(xiàn)（EventOccurs）：進(jìn)程等待的事件出現(xiàn)；如：操作完成、申請成功等；可能的情況有：阻塞到就緒：針對內(nèi)存進(jìn)程的事件出現(xiàn)；阻塞掛起到就緒掛起：針對外存進(jìn)程的事件出現(xiàn)；7/23/202342第二章進(jìn)程管理【思考題】1．如果系統(tǒng)中有N個(gè)進(jìn)程，運(yùn)行的進(jìn)程最多幾個(gè)，最少幾個(gè)；就緒進(jìn)程最多幾個(gè)，最少幾個(gè)；等待進(jìn)程最多幾個(gè)，最少幾個(gè)？答案：運(yùn)行進(jìn)程最多1個(gè)，最少1個(gè)就緒進(jìn)程最多N-1個(gè)，最少0個(gè)等待進(jìn)程最多N-1個(gè)，最少0個(gè)7/23/202343第二章進(jìn)程管理進(jìn)程的描述

進(jìn)程的靜態(tài)描述：由三部分組成進(jìn)程控制塊、有關(guān)程序段和該程序段對其進(jìn)行操作的數(shù)據(jù)集。1進(jìn)程控制塊：包含了有關(guān)進(jìn)程的描述信息、控制信息以及資源信息，是進(jìn)程動(dòng)態(tài)特征的集中反映。

2程序段：是進(jìn)程中能被進(jìn)程調(diào)度程序選中，并在CPU上執(zhí)行的程序代碼段。3數(shù)據(jù)段：一個(gè)進(jìn)程的數(shù)據(jù)段，可以是進(jìn)程對應(yīng)的程序加工處理的原始數(shù)據(jù)，也可以是程序執(zhí)行后產(chǎn)生的中間或最終數(shù)據(jù)。7/23/202344第二章進(jìn)程管理進(jìn)程控制塊（ProcessControlBlock）為了描述一個(gè)進(jìn)程與其它進(jìn)程以及系統(tǒng)資源的關(guān)系，為了刻畫一個(gè)進(jìn)程在各個(gè)不同時(shí)期所處的狀態(tài)，人們采用了一個(gè)與進(jìn)程相聯(lián)系的數(shù)據(jù)結(jié)構(gòu)，稱為進(jìn)程控制塊（PCB）。7/23/202345第二章進(jìn)程管理其作用是將一個(gè)不能獨(dú)立運(yùn)行的程序變成一個(gè)可以獨(dú)立運(yùn)行的基本單位，一個(gè)能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。OS利用PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的，PCB是OS感知進(jìn)程存在的唯一標(biāo)志。進(jìn)程與PCB是一一對應(yīng)的。PCB應(yīng)常駐內(nèi)存。進(jìn)程控制塊（ProcessControlBlock）7/23/202346第二章進(jìn)程管理1、PCB的內(nèi)容進(jìn)程描述信息：進(jìn)程標(biāo)識符(processID)，唯一，通常是一個(gè)整數(shù)進(jìn)程名，通?；诳蓤?zhí)行文件名（不唯一）用戶標(biāo)識符(userID)：指示該進(jìn)程由哪個(gè)用戶擁有進(jìn)程組（家族）關(guān)系：父進(jìn)程標(biāo)識符以及子進(jìn)程標(biāo)識符7/23/202347第二章進(jìn)程管理1、PCB的內(nèi)容進(jìn)程控制信息：當(dāng)前狀態(tài)優(yōu)先級(priority)程序的外存地址運(yùn)行統(tǒng)計(jì)信息（執(zhí)行時(shí)間、頁面調(diào)度）進(jìn)程間同步和通信；阻塞原因進(jìn)程的隊(duì)列指針進(jìn)程的消息隊(duì)列指針7/23/202348第二章進(jìn)程管理1、PCB的內(nèi)容資源管理信息1、占用內(nèi)存大小及其管理用數(shù)據(jù)結(jié)構(gòu)指針。2、共享程序段大小及其起始地址。3、輸入、輸出設(shè)備的設(shè)備號，所要傳送的數(shù)據(jù)長度、緩沖區(qū)地址、緩沖區(qū)長度及所用設(shè)備的有關(guān)數(shù)據(jù)結(jié)構(gòu)指針等。4、指向文件系統(tǒng)的指針及有關(guān)標(biāo)識。CPU現(xiàn)場保護(hù)結(jié)構(gòu)當(dāng)前進(jìn)程因等待某個(gè)事件而進(jìn)入等待狀態(tài)或因某種事件發(fā)生被終止在處理機(jī)上的執(zhí)行時(shí)，為了以后該進(jìn)程能在被中斷處恢復(fù)執(zhí)行，需要保護(hù)當(dāng)前進(jìn)程的CPU現(xiàn)場。CPU中設(shè)有專門的CPU現(xiàn)場保護(hù)結(jié)構(gòu)，以存儲退出執(zhí)行時(shí)的進(jìn)程現(xiàn)場數(shù)據(jù)。7/23/202349第二章進(jìn)程管理2、PCB表組織方式PCB表：

系統(tǒng)把所有PCB組織在一起，并把它們放在內(nèi)存的固定區(qū)域，就構(gòu)成了PCB表。PCB表的大小決定了系統(tǒng)中最多可同時(shí)存在的進(jìn)程個(gè)數(shù)，稱為系統(tǒng)的并發(fā)度。

7/23/202350第二章進(jìn)程管理鏈接結(jié)構(gòu)相同狀態(tài)的進(jìn)程其PCB組成一個(gè)鏈表，多個(gè)狀態(tài)對應(yīng)多個(gè)不同的鏈表。就緒鏈表、阻塞鏈表7/23/202351第二章進(jìn)程管理7/23/202352第二章進(jìn)程管理索引結(jié)構(gòu)對具有相同狀態(tài)的進(jìn)程，分別設(shè)置各自的PCB索引表，表明PCB在PCB表中的地址（由index指向PCB）。多個(gè)狀態(tài)對應(yīng)多個(gè)不同的index表：就緒索引表、阻塞索引表索引表在內(nèi)存的首地址記錄在內(nèi)存中的一些專用單元中。7/23/202353第二章進(jìn)程管理索引表就緒隊(duì)列等待隊(duì)列1等待隊(duì)列2PCB1PCB2PCB3PCB4PCB5PCB6PCB7…PCBnPCB表7/23/202354第二章進(jìn)程管理3.進(jìn)程的上下文進(jìn)程是在操作系統(tǒng)的支持下運(yùn)行的，進(jìn)程運(yùn)行時(shí)操作系統(tǒng)需要為其設(shè)置相應(yīng)的運(yùn)行環(huán)境，如系統(tǒng)棧、地址映射寄存器、打開文件表、PSW與PC、通用寄存器等。在UNIXSystemⅴ中，將進(jìn)程的物理實(shí)體與支持進(jìn)程運(yùn)行的物理環(huán)境合稱為進(jìn)程上下文。進(jìn)程切換過程就是進(jìn)程上下文切換的過程。由于進(jìn)程上下文涉及的內(nèi)容較多，進(jìn)程切換一般需要一定的時(shí)間才能完成，這是系統(tǒng)為實(shí)現(xiàn)并發(fā)而付出的額外代價(jià)，屬于系統(tǒng)開銷的一部分。7/23/202355第二章進(jìn)程管理2.2進(jìn)程控制

進(jìn)程控制就是對系統(tǒng)中的所有進(jìn)程實(shí)施管理（創(chuàng)建一個(gè)新進(jìn)程、終止一個(gè)已完成的進(jìn)程，或終止一個(gè)因出現(xiàn)某事件而使其無法運(yùn)行下去的進(jìn)程，還負(fù)責(zé)進(jìn)程運(yùn)行中狀態(tài)的轉(zhuǎn)換），進(jìn)程控制一般由OS的內(nèi)核來實(shí)現(xiàn)。7/23/202356第二章進(jìn)程管理原語

所謂原語是指系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段。分為兩類：

機(jī)器指令級的:執(zhí)行期間不允許中斷功能級的:作為原語的程序段不允許并發(fā)執(zhí)行常用的進(jìn)程控制原語：

創(chuàng)建原語Create

終止原語Destroy

阻塞原語Block、喚醒原語Wakeup

掛起原語Suspend、激活原語Active

7/23/202357第二章進(jìn)程管理進(jìn)程圖用來描述進(jìn)程家族關(guān)系的有向樹。ABCDMEIJHGFLK

子進(jìn)程可以繼承父進(jìn)程的所有資源，當(dāng)子進(jìn)程被撤消時(shí)，應(yīng)將從父進(jìn)程那里獲得的資源歸還給父進(jìn)程。撤消父進(jìn)程時(shí)也必須同時(shí)撤消其所有的子進(jìn)程。UNIX稱進(jìn)程樹里的所有進(jìn)程為一個(gè)進(jìn)程組，進(jìn)程組中的進(jìn)程分布在不同的層次上，從而形成一個(gè)層次架構(gòu)。Windows沒有進(jìn)程組的概念，所有進(jìn)程均地位平等。7/23/202358第二章進(jìn)程管理引起創(chuàng)建進(jìn)程的事件1用戶登錄：在分時(shí)系統(tǒng)中，用戶在終端鍵入登錄命令后，若是合法用戶，系統(tǒng)建立一個(gè)進(jìn)程，并插入就緒隊(duì)列。2作業(yè)調(diào)度：批處理系統(tǒng)中，作業(yè)調(diào)度程序調(diào)度到某個(gè)作業(yè)以后，就把這個(gè)作業(yè)裝入內(nèi)存，并分配必要的資源，創(chuàng)建進(jìn)程，插入就緒隊(duì)列。3提供服務(wù)：運(yùn)行中的用戶向系統(tǒng)提出請求后，系統(tǒng)專門建立一個(gè)進(jìn)程為用戶服務(wù)。（打印請求）由操作系統(tǒng)核心（系統(tǒng)程序模塊）創(chuàng)建4應(yīng)用請求：應(yīng)用進(jìn)程的需要，由它自己創(chuàng)建一個(gè)新進(jìn)程，使新進(jìn)程以并發(fā)運(yùn)行方式完成特定任務(wù)。（輸入數(shù)據(jù)并將處理結(jié)果輸出到表格上）由父進(jìn)程創(chuàng)建

進(jìn)程創(chuàng)建7/23/202359第二章進(jìn)程管理進(jìn)程創(chuàng)建申請空白PCB為新進(jìn)程分配資源如內(nèi)存初始化進(jìn)程控制塊將新進(jìn)程插入就緒隊(duì)列

7/23/202360第二章進(jìn)程管理入口查PCB鏈表有空PCB？PCB（i）入進(jìn)程家族或進(jìn)程鏈PCB(i)入就緒隊(duì)列將有關(guān)參數(shù)填入PCB（i）相應(yīng)項(xiàng)取空表PCB(i)返回創(chuàng)建失敗無有創(chuàng)建原語流程圖7/23/202361第二章進(jìn)程管理進(jìn)程撤消(終止)引起進(jìn)程終止的事件1正常結(jié)束：計(jì)算機(jī)系統(tǒng)中，都有一個(gè)表示進(jìn)程已經(jīng)運(yùn)行完成的指示。2異常結(jié)束

越界錯(cuò)誤、保護(hù)錯(cuò)、特權(quán)指令錯(cuò)、非法指令錯(cuò)、運(yùn)行超時(shí)、等待超時(shí)算術(shù)運(yùn)算錯(cuò)、I/O故障3外界干預(yù)操作員或操作系統(tǒng)干預(yù)父進(jìn)程請求父進(jìn)程終止7/23/202362第二章進(jìn)程管理進(jìn)程撤消過程根據(jù)被終止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB,從中讀出該進(jìn)程的狀態(tài)若被終止進(jìn)程處于執(zhí)行狀態(tài)，應(yīng)立即終止執(zhí)行，并置調(diào)度標(biāo)志為真(用于指示該進(jìn)程被終止時(shí)應(yīng)重新調(diào)度其它進(jìn)程)，然后再選擇一個(gè)進(jìn)程，分配處理機(jī)給它。如果該進(jìn)程還有子孫進(jìn)程，則結(jié)束該進(jìn)程所有子孫進(jìn)程的執(zhí)行，以防它們成不可控進(jìn)程；將進(jìn)程所擁有的資源交給父進(jìn)程或系統(tǒng)進(jìn)程；將被終止進(jìn)程(PCB)從所在隊(duì)列中移出，等待其他進(jìn)程來收集信息。7/23/202363第二章進(jìn)程管理查進(jìn)程鏈表或進(jìn)程家族入口返回有此PCB嗎？該P(yáng)CB有子進(jìn)程嗎？釋放該進(jìn)程所占有的資源釋放該P(yáng)CB結(jié)構(gòu)本身出錯(cuò)處理有無有撤消原語流程圖7/23/202364第二章進(jìn)程管理阻塞：當(dāng)一個(gè)進(jìn)程所期待的某一事件尚未出現(xiàn)時(shí)，該進(jìn)程調(diào)用阻塞原語將自己阻塞。進(jìn)程阻塞是進(jìn)程的自身的一種主動(dòng)行為。喚醒：處于阻塞狀態(tài)的進(jìn)程是絕不可能叫醒它自己的，它必須由它的合作進(jìn)程用喚醒原語喚醒它。進(jìn)程的阻塞與喚醒7/23/202365第二章進(jìn)程管理進(jìn)程的阻塞與喚醒引起進(jìn)程阻塞和喚醒的事件1請求系統(tǒng)服務(wù)正在執(zhí)行的程序請求操作系統(tǒng)服務(wù)，但是由于某種原因操作系統(tǒng)沒有立即滿足該進(jìn)程的要求，該進(jìn)程只能轉(zhuǎn)變?yōu)樽枞麪顟B(tài)來等待。2啟動(dòng)某操作當(dāng)進(jìn)程啟動(dòng)某種操作后，如果該進(jìn)程必須在該操作完成之后才能繼續(xù)執(zhí)行，所以必須先使進(jìn)程阻塞。3新數(shù)據(jù)尚未到達(dá)4無新工作可做系統(tǒng)往往設(shè)置一些具有某特定功能的系統(tǒng)進(jìn)程，每當(dāng)這種進(jìn)程完成任務(wù)以后便把自己阻塞起來等待新任務(wù)的到來。（發(fā)送進(jìn)程）7/23/202366第二章進(jìn)程管理阻塞過程：停止運(yùn)行轉(zhuǎn)變狀態(tài)插入相應(yīng)事件隊(duì)列重新調(diào)度喚醒過程：移出阻塞隊(duì)列轉(zhuǎn)變狀態(tài)插入就緒隊(duì)列可能重新調(diào)度進(jìn)程的阻塞與喚醒7/23/202367第二章進(jìn)程管理入口保存當(dāng)前進(jìn)程的CPU現(xiàn)場置該進(jìn)程的狀態(tài)被阻塞進(jìn)程入等待隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度入口從等待隊(duì)列中摘下被喚醒進(jìn)程將被喚醒進(jìn)程置為就緒狀態(tài)將被喚醒進(jìn)程送入就緒隊(duì)列轉(zhuǎn)進(jìn)程調(diào)度或返回阻塞原語喚醒原語阻塞原語和喚醒原語7/23/202368第二章進(jìn)程管理進(jìn)程的掛起與激活掛起：當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，系統(tǒng)利用掛起原語將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。

激活：當(dāng)發(fā)生激活進(jìn)程的事件時(shí)，系統(tǒng)利用激活原語將指定進(jìn)程激活。7/23/202369第二章進(jìn)程管理進(jìn)程的掛起與激活掛起過程：檢查/轉(zhuǎn)換狀態(tài)復(fù)制PCB到指定內(nèi)存掛起運(yùn)行時(shí)，重新調(diào)度激活過程：檢查/轉(zhuǎn)換狀態(tài)變活動(dòng)就緒時(shí)，可能重新調(diào)度7/23/202370第二章進(jìn)程管理2.3進(jìn)程同步進(jìn)程同步的主要任務(wù)是使并發(fā)執(zhí)行的諸進(jìn)程之間能有效的共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。2.3.1進(jìn)程同步的基本概念2.3.2信號量機(jī)制2.3.3信號量的應(yīng)用7/23/202371第二章進(jìn)程管理并發(fā)系統(tǒng)中諸進(jìn)程由于資源共享、進(jìn)程合作，而產(chǎn)生進(jìn)程之間的相互制約；又因共享資源的方式不同，而導(dǎo)致兩種不同的制約關(guān)系：間接制約關(guān)系（進(jìn)程互斥）由于共享公有資源而造成的對并發(fā)進(jìn)程執(zhí)行速度的間接制約。(系統(tǒng)資源：如A、B兩進(jìn)程競爭打印機(jī))

間接：指各并發(fā)進(jìn)程的速度受公有資源制約。直接制約關(guān)系（進(jìn)程同步）由于并發(fā)進(jìn)程互相共享對方的私有資源所引起的直接制約。（進(jìn)程間合作：如輸入進(jìn)程、計(jì)算進(jìn)程和打印進(jìn)程）2.3.1進(jìn)程同步的基本概念7/23/202372第二章進(jìn)程管理

相似處：進(jìn)程的互斥實(shí)際上是進(jìn)程同步的一種特殊情況；進(jìn)程的互斥和同步統(tǒng)稱為進(jìn)程同步。

差別：進(jìn)程互斥是進(jìn)程間競爭共享資源的使用權(quán)，這種競爭沒有固定的必然聯(lián)系，哪個(gè)進(jìn)程競爭到使用權(quán)就歸那個(gè)進(jìn)程使用，直到不需要使用時(shí)再歸還；而進(jìn)程同步則是涉及共享資源的并發(fā)進(jìn)程間有一種必然的聯(lián)系，當(dāng)進(jìn)程必須同步時(shí)，即使無進(jìn)程在使用共享資源時(shí)，那么尚未得到同步消息的進(jìn)程也不能去使用這個(gè)資源。進(jìn)程同步和互斥間的關(guān)系7/23/202373第二章進(jìn)程管理

臨界資源(criticalresource)：一次僅允許一個(gè)進(jìn)程訪問的資源。如：進(jìn)程ＡＢ共享一臺打印機(jī)，若讓它們交替使用則得到的結(jié)果肯定不是我們希望的。臨界資源可能是硬件，也可能是軟件：變量，數(shù)據(jù)，表格，隊(duì)列等。并發(fā)進(jìn)程對臨界資源的訪問必須作某種限制，否則就可能出與時(shí)間有關(guān)的錯(cuò)誤，如：聯(lián)網(wǎng)售票。

2.3.1進(jìn)程同步的基本概念7/23/202374第二章進(jìn)程管理與時(shí)間有關(guān)的錯(cuò)誤:一飛機(jī)訂票系統(tǒng)，兩個(gè)終端，運(yùn)行A1、A2進(jìn)程

A1:A2:

......

Read(x);Read(x);

ifx>=mthenifx>=mthen

x:=x-m;x:=x-m;(售出m張機(jī)票)

write(x);write(x);

......7/23/202375第二章進(jìn)程管理時(shí)間T1T2T3T4T5結(jié)果X的值10010010808080A1Sell(90)Read(x)x=x-90購票成功A2Sell(20)Read(x)x=x-20購票成功7/23/202376第二章進(jìn)程管理實(shí)例：生產(chǎn)者－消費(fèi)者問題一種同步問題的抽象描述計(jì)算機(jī)系統(tǒng)中的每個(gè)進(jìn)程都可以消費(fèi)（使用）或生產(chǎn)（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當(dāng)某一進(jìn)程使用某一資源時(shí)，可以看作是消費(fèi)，稱該進(jìn)程為消費(fèi)者。而當(dāng)某一進(jìn)程釋放某一資源時(shí)，它就相當(dāng)于生產(chǎn)者。7/23/202377第二章進(jìn)程管理實(shí)例：生產(chǎn)者－消費(fèi)者問題一種同步問題的抽象描述生產(chǎn)者－消費(fèi)者之間設(shè)置一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)；消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi)。不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未取走的緩沖區(qū)投放產(chǎn)品。7/23/202378第二章進(jìn)程管理實(shí)例：生產(chǎn)者－消費(fèi)者問題問題分析利用一個(gè)數(shù)組表示具有n個(gè)緩沖區(qū)的循環(huán)緩沖池；用輸入指針in指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品，輸入指針加1(in:=(in+1)modn)；用指針out指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取出一個(gè)產(chǎn)品，輸出指針加1(out:=(out+1)modn)；7/23/202379第二章進(jìn)程管理實(shí)例：生產(chǎn)者－消費(fèi)者問題……1234n-1ninout7/23/202380第二章進(jìn)程管理實(shí)例：生產(chǎn)者－消費(fèi)者問題問題分析(in+1)modn=out緩沖池滿；in=out緩沖池空；counter表示緩沖池內(nèi)產(chǎn)品的數(shù)量。在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品；使用一個(gè)局部變量nextc用于存放每次要消費(fèi)的產(chǎn)品。7/23/202381第二章進(jìn)程管理實(shí)例：生產(chǎn)者－消費(fèi)者問題producer：repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;

counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-opnextc:=buffer[out];out:=(out+1)modn;

counter:=counter-1;consumertheiteminnextc;untilfalse;兩者并發(fā)執(zhí)行會(huì)出現(xiàn)錯(cuò)誤!7/23/202382第二章進(jìn)程管理實(shí)例：生產(chǎn)者－消費(fèi)者問題register1:=counterregister1:=register1+1counter:=register1register2:=counterregister2:=register2-1counter:=register21

32

45

6應(yīng)把counter作為臨界資源處理!假設(shè)counter=5，則按上述次序執(zhí)行結(jié)果是4—程序的執(zhí)行失去了可再現(xiàn)性7/23/202383第二章進(jìn)程管理2.3.1進(jìn)程同步的基本概念臨界區(qū)(criticalsection)：在每個(gè)程序中，訪問臨界資源的那段程序。若在一組并發(fā)進(jìn)程的各自臨界區(qū)中都使用了相同的共享變量，則稱這組臨界區(qū)為相關(guān)臨界區(qū)。若能保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū),便可實(shí)現(xiàn)諸進(jìn)程對臨界資源的互斥訪問.

repeatentrysectioncriticalsectionexitsectionremaindersectionUntilfalse7/23/202384第二章進(jìn)程管理2.3.1進(jìn)程同步的基本概念注意：臨界區(qū)是對某一臨界資源而言的，對于不同臨界資源的臨界區(qū)，它們之間不存在互斥。

如程序段A、B有關(guān)于變量X的臨界區(qū)，而C、D有關(guān)于變量Y的臨界區(qū)，那么，A、B之間需要互斥執(zhí)行，C、D之間也要互斥執(zhí)行，而A與C、B與D之間不用互斥執(zhí)行。

。7/23/202385第二章進(jìn)程管理“金魚問題”zuo和you兩人合住一套公寓，共同養(yǎng)了一條金魚，該金魚每天進(jìn)食一頓。兩人想把金魚養(yǎng)活，一天只能喂一次，如果一天內(nèi)兩人都喂了魚，魚就脹死。如果一天內(nèi)兩人都沒有喂魚，魚就餓死。7/23/202386第二章進(jìn)程管理Solution#0沒有同步zuo:you:if(nofeed){if(nofeed){feedfishfeedfish}}7/23/202387第二章進(jìn)程管理Problemwithsolution#0zuo:you:13:00觀察魚（沒有喂）13:05觀察魚（沒有喂）13:10喂魚13:25喂魚

魚脹死了！7/23/202388第二章進(jìn)程管理臨界區(qū)Solution0#中臨界區(qū)為：if(nofeed)，feedfish要防止魚脹死，zuo和you就不能同時(shí)進(jìn)入臨界區(qū)。要達(dá)到這點(diǎn)，就需要某種協(xié)調(diào)手段。協(xié)調(diào)的目的就是在任何時(shí)刻只能有一個(gè)人在臨界區(qū)里——互斥。7/23/202389第二章進(jìn)程管理正確互斥需要滿足四個(gè)條件（1）空閑讓進(jìn)：當(dāng)無進(jìn)程處于臨界區(qū)時(shí)，應(yīng)允許一個(gè)請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效利用臨界資源。（2）忙則等待：當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對臨界資源的互斥訪問。（3）讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。（4）有限等待：對要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。7/23/202390第二章進(jìn)程管理Solution#1思想：zuo和you商定，每個(gè)人在察看魚的狀態(tài)之前留下字條，告訴對方自己將檢查魚缸并在需要時(shí)喂魚。zuo:you:if(nonote){if(nonote){leavenoteleavenoteif(nofeed){if(nofeed){feedfishfeedfish}}removenoteremovenote}}7/23/202391第二章進(jìn)程管理Problemwithsolution#1zuo:you:13:00檢查發(fā)現(xiàn)沒有字條13:05檢查發(fā)現(xiàn)沒有字條13:10留字條13:25留字條13:50觀察魚（沒有喂）14:05觀察魚（沒有喂）14:10喂魚14:25喂魚

魚脹死了！但魚脹死的概率降低了?。▃uo和you嚴(yán)格交叉執(zhí)行時(shí)，才可能發(fā)生魚脹死現(xiàn)象）7/23/202392第二章進(jìn)程管理Solution#2思想：上述程序不解決問題的原因是因?yàn)橄葯z查有沒有字條，然后留字條。這使得檢查字條和留字條之間存在空擋。為此修改一下順序，先留字條，再檢查有沒有對方字條，若沒有，就喂魚，喂完把字條拿掉。但要區(qū)分條子是誰的。zuo:you:leavenotezuoleavenoteyouif(nonoteyou){if(nonotezuo){if(nofeed){if(nofeed){feedfishfeedfish}}}}removenotezuoremovenoteyou魚不會(huì)脹死：因無論按怎樣順序穿插，總有一個(gè)人的留條子在另一人的檢查字條前執(zhí)行，從而防止兩人同時(shí)進(jìn)入臨界區(qū)。7/23/202393第二章進(jìn)程管理Problemwithsolution#2zuo:you:13:10留字條you13:25留字條zuo13:50檢查字條you(存在）14:05檢查字條zuo(存在）14:10拿掉字條you14:25拿掉字條zuo

沒人喂魚，魚餓死了！7/23/202394第二章進(jìn)程管理Solution#3思想：魚餓死是因?yàn)闆]人進(jìn)入臨界區(qū)。解決的方法是讓某個(gè)人等著，直到確認(rèn)有人喂了魚才離去。zuo:you:leavenotezuoleavenoteyouwhile(noteyou){donothing}if(nonotezuo){if(nofeed){if(nofeed){feedfishfeedfish}}}removenotezuoremovenoteyou7/23/202395第二章進(jìn)程管理Solution#3魚不會(huì)脹死，因?yàn)槭褂玫姆椒ò藄olution#2的同步方式；上述程序在兩個(gè)人都留字條的情況下，zuo不會(huì)離開，而是一直循環(huán)等待直到對方刪除字條后，再檢查魚有沒有喂，并在沒有喂魚的情況下喂魚，因此魚也不會(huì)餓死。存在的問題：程序不對稱，造成程序編寫困難。浪費(fèi)。Zuo的循環(huán)等待是一種很大的浪費(fèi)。循環(huán)等待還可能造成cpu調(diào)度的優(yōu)先級倒掛，即高優(yōu)先級的進(jìn)程等待低優(yōu)先級的進(jìn)程。7/23/202396第二章進(jìn)程管理進(jìn)一步改進(jìn)問題：對哪個(gè)方案進(jìn)行改進(jìn)，solution#3?solution#2？還是solution#1?Solution#1不滿足條件是因?yàn)闄z查字條和留字條中間存在空擋，造成字條作用的喪失，能否將這兩步驟并為一個(gè)步驟，或者變成原子操作，使其中間不留空擋？解決的辦法是提高抽象層次從保護(hù)魚和魚缸的層次提高到保護(hù)放置魚缸的房間的層次。即設(shè)計(jì)一種同步措施，使得在任何時(shí)候只能有一個(gè)人進(jìn)入放置魚缸的房間。7/23/202397第二章進(jìn)程管理鎖zuo:you:lock()lock()if(nofeed){if(nofeed){feedfishfeedfish}}unlock()unlock()問題：若zuo正在喂魚，you只能等待（等待鎖變?yōu)榇蜷_狀態(tài)）。若zuo喂魚的動(dòng)作很慢，you等待的時(shí)間就會(huì)很長，而這種繁忙等待將造成浪費(fèi)，也降低系統(tǒng)效率。7/23/202398第二章進(jìn)程管理減少鎖的繁忙等待時(shí)間zuo:you:lock()lock()if(nonoteyou)if(nonotezuo)leavenotezuoleavenoteyouunlock()unlock()if(nonoteyou){if(nonotezuo){if(nofeed){if(nofeed){feedfishfeedfish}}removenoteremovenote}}在鎖上的繁忙等待時(shí)間已經(jīng)很少，但還是有等待7/23/202399第二章進(jìn)程管理睡覺與叫醒思想：如果鎖被對方持有，不用等待鎖變?yōu)榇蜷_狀態(tài)，而是睡覺去，鎖打開后再來把你叫醒。producer：repeatproduceaniteminnextp;ifcounter=nsleep()；buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;ifcounter=1wakeup(consumer)untilfalse;consumer:repeatifcounter=0sleep()；nextc:=buffer[out];out:=(out+1)modn;

counter:=counter-1;ifcounter=n-1wakeup(profucer)consumertheiteminnextc;untilfalse;7/23/2023100第二章進(jìn)程管理睡覺與叫醒問題一：生產(chǎn)者和消費(fèi)者共用變量counter，兩進(jìn)程并發(fā)執(zhí)行時(shí)可能發(fā)生與時(shí)間有關(guān)的錯(cuò)誤。解決辦法：在對counter操作的前后加上lock和unlock即可防止生產(chǎn)者和消費(fèi)者同時(shí)訪問counter的情況出現(xiàn)。7/23/2023101第二章進(jìn)程管理睡覺與叫醒問題二：可能出現(xiàn)生產(chǎn)者和消費(fèi)者同時(shí)睡覺，從而無法相互叫醒繼續(xù)往前推進(jìn)。（假定消費(fèi)者先來，counter=0，于是去睡覺，但在執(zhí)行sleep語句前cpu發(fā)生切換，生產(chǎn)者開始運(yùn)行，它生產(chǎn)一件產(chǎn)品后，給counter加1，發(fā)現(xiàn)counter結(jié)果為1，因此發(fā)出叫醒消費(fèi)者的信號，但這時(shí)消費(fèi)者還沒睡，所以信號沒有任何效果。生產(chǎn)者一直運(yùn)行直到緩沖區(qū)滿后也去睡覺。這時(shí)cpu切換到消費(fèi)者，而消費(fèi)者執(zhí)行的第一個(gè)操作就是sleep，至此生產(chǎn)者與消費(fèi)者都進(jìn)入睡眠狀態(tài)）解決辦法：不讓二者同時(shí)睡覺。造成二者同時(shí)睡覺的原因是生產(chǎn)者發(fā)出的叫醒信號丟失（因消費(fèi)者此時(shí)還未睡）。若用某種方法將發(fā)出的信號累積起來，而不是丟掉，問題就會(huì)得到解決。即在消費(fèi)者獲得cpu執(zhí)行sleep語句后，生產(chǎn)者在這之前發(fā)送的叫醒信號還保留著，因此消費(fèi)者將馬上獲得這個(gè)信號而醒過來。----能夠?qū)⑿盘柪鄯e起來的操作系統(tǒng)原語就是信號量。7/23/2023102第二章進(jìn)程管理1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)）。一種卓有成效的進(jìn)程同步機(jī)制。經(jīng)歷整型信號量、記錄型信號量，發(fā)展為“信號量集”機(jī)制。P、V操作是原語。2.3.2信號量機(jī)制7/23/2023103第二章進(jìn)程管理1、整型信號量把整型信號量定義為一個(gè)表示資源數(shù)目的整型量，僅由兩個(gè)標(biāo)準(zhǔn)原子操作wait(S)（P操作）和signal(S)（V操作）來訪問。wait(S):whileS≤0dono-op;S:=S-1;signal(S):S:=S+1;注意：兩種操作皆為原語操作。7/23/2023104第二章進(jìn)程管理2、記錄型信號量記錄型信號量機(jī)制采取“讓權(quán)等待”策略，避免了整型信號量出現(xiàn)的“忙等”現(xiàn)象。實(shí)現(xiàn)時(shí)需要一個(gè)用于代表資源數(shù)目的整型變量value，一個(gè)用于鏈接所有等待進(jìn)程的進(jìn)程鏈表queue。7/23/2023105第二章進(jìn)程管理2、記錄型信號量信號量是一個(gè)數(shù)據(jù)結(jié)構(gòu)，定義如下：

structsemaphore{ intvalue; pointer_PCBqueue;//進(jìn)程鏈表}信號量說明：semaphores;7/23/2023106第二章進(jìn)程管理P操作(wait(s))—申請資源P(s){s.value=s.value-1;if(s.value<0){

該進(jìn)程狀態(tài)置為等待狀態(tài)將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列末尾s.queue;}}S.value初值表示系統(tǒng)中某類資源的數(shù)目;當(dāng)S.value<0時(shí),表示該資源已分配完畢,其絕對值表示在該信號量鏈表中已阻塞進(jìn)程的數(shù)目7/23/2023107第二章進(jìn)程管理V操作(signal(s))—釋放資源V(s){s.value=s.value+1;if(s.value<=0){喚醒相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)進(jìn)程改變其狀態(tài)為就緒狀態(tài)并將其插入就緒隊(duì)列}}7/23/2023108第二章進(jìn)程管理3、AND型信號量例如：兩個(gè)進(jìn)程A、B要求訪問共享數(shù)據(jù)D、E。

為D、E分別設(shè)置用于互斥的信號量Dmutex、Emutex，初值為1。

processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);可能出現(xiàn)死等現(xiàn)象7/23/2023109第二章進(jìn)程管理3、AND型信號量AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。實(shí)現(xiàn)時(shí)在wait操作中，增加一個(gè)“AND”條件，故稱AND同步，或同時(shí)wait操作(Swait)。7/23/2023110第二章進(jìn)程管理3、AND型信號量Swait(S1,S2,…,Sn)ifS1≥1and…andSn≥1thenfori:=1tondoSi:=Si-1;endforelse當(dāng)發(fā)現(xiàn)有Si<1時(shí)，該進(jìn)程狀態(tài)置為等待狀態(tài)endifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;

將與Si相關(guān)的所有 等待進(jìn)程移出到就 緒隊(duì)列endfor7/23/2023111第二章進(jìn)程管理Swait(S1,S2,…,Sn) //P原語；{if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時(shí)的處理；for(i=1;i<=n;++i)--Si;}else{ //某些資源不夠時(shí)的處理；

調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號量的等待隊(duì)列Sj.queue;

阻塞調(diào)用進(jìn)程;}}7/23/2023112第二章進(jìn)程管理Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源；for(在Si.queue中等待的每一個(gè)進(jìn)程P){從等待隊(duì)列Si.queue中取出進(jìn)程P;if(判斷進(jìn)程P是否通過Swait中的測試)//重新判斷{進(jìn)程P進(jìn)入就緒隊(duì)列;break；}else進(jìn)程P進(jìn)入某等待隊(duì)列；

}}}7/23/2023113第二章進(jìn)程管理4、信號量集一次需要N個(gè)某類臨界資源時(shí)，就要進(jìn)行N次P操作——低效又可能死鎖。信號量集是指同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號量處理。一般信號量集的基本思路就是在AND型信號量的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語操作中完成所有的資源申請。7/23/2023114第二章進(jìn)程管理進(jìn)程對信號量Si的測試值為ti（表示信號量的判斷條件，要求Si>=ti；即當(dāng)資源數(shù)量低于ti時(shí)，便不予分配）占用值為di（表示資源的申請量，即Si=Si-di）對應(yīng)的P、V原語格式為：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);4、信號量集7/23/2023115第二章進(jìn)程管理4、信號量集Swait(S1,t1,d1,…,Sn,tn,dn)ifS1≥t1and…andSn≥tnthenfori:=1tondoSi:=Si-di;endforelse

當(dāng)發(fā)現(xiàn)有Si<ti時(shí)，該進(jìn)程狀態(tài)置為等待狀態(tài)endif7/23/2023116第二章進(jìn)程管理4、信號量集Ssignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;將與Si相關(guān)的所有等待進(jìn)程移出 到就緒隊(duì)列

endfor7/23/2023117第二章進(jìn)程管理一般“信號量集”可以用于各種情況的資源分配和釋放，幾種特殊情況：Swait(S,d,d)表示每次申請d個(gè)資源，當(dāng)少于d個(gè)時(shí)，便不分配Swait(S,1,1)表示記錄型信號量或互斥信號量Swait(S,1,0)可作為一個(gè)可控開關(guān)（當(dāng)S1時(shí)，允許多個(gè)進(jìn)程進(jìn)入特定區(qū)域；當(dāng)S=0時(shí)，禁止任何進(jìn)程進(jìn)入該特定區(qū)域）一般“信號量集”未必成對使用。如：一起申請，但不一起釋放！7/23/2023118第二章進(jìn)程管理1、利用信號量實(shí)現(xiàn)進(jìn)程互斥2、利用信號量實(shí)現(xiàn)前趨關(guān)系2.3.3信號量的應(yīng)用7/23/2023119第二章進(jìn)程管理只須為臨界資源設(shè)置一互斥信號量mutex，設(shè)其初始值為1，然后將各進(jìn)程訪問該資源的臨界區(qū)CS置于wait(mutex)和signal(mutex)操作之間即可。1、利用信號量實(shí)現(xiàn)進(jìn)程互斥7/23/2023120第二章進(jìn)程管理用P、V操作解決進(jìn)程間互斥問題P(mutex)V(mutex)P1P2P3臨界區(qū)P(mutex)P(mutex)V(mutex)V(mutex)7/23/2023121第二章進(jìn)程管理Varmutex:semaphore:=1beginparbeginprocess1:beginrepeat

wait(mutex);criticalsection

signal(mutex);remaindersectionuntilfalse;endProcess2:begin

repeat

wait(mutex);criticalsection

signal(mutex);remaindersectionuntilfalse;endparend

7/23/2023122第二章進(jìn)程管理若干個(gè)進(jìn)程為了完成一個(gè)共同任務(wù)而并發(fā)執(zhí)行，在這些進(jìn)程中，有些進(jìn)程之間有次序的要求，有些進(jìn)程之間沒有次序的要求，為了描述方便，可以用一個(gè)圖來表示進(jìn)程集合的執(zhí)行次序。2、利用信號量實(shí)現(xiàn)前趨關(guān)系7/23/2023123第二章進(jìn)程管理2、利用信號量實(shí)現(xiàn)前趨關(guān)系7/23/2023124第二章進(jìn)程管理方法1：在需要順序執(zhí)行的進(jìn)程（P1→P2）間設(shè)置一個(gè)兩個(gè)進(jìn)程的共有信號量S，供兩個(gè)進(jìn)程共享，并賦初值為0。在進(jìn)程P1中，運(yùn)行完成，signal(S)在進(jìn)程P2中，wait(S)，運(yùn)行2、利用信號量實(shí)現(xiàn)前趨關(guān)系7/23/2023125第二章進(jìn)程管理方法2：在需要順序執(zhí)行的進(jìn)程（P1→P2）間設(shè)置一個(gè)同步信號量f，將用來標(biāo)識前面進(jìn)程是否執(zhí)行完成，該信號量如果沒有遇到同步則一直沿用下去，賦初值為0。在進(jìn)程P1中，運(yùn)行完成，signal(f)在進(jìn)程P2中，wait(f)，運(yùn)行2、利用信號量實(shí)現(xiàn)前趨關(guān)系7/23/2023126第二章進(jìn)程管理不同之處方法1在圖中存在n個(gè)進(jìn)程，則需要設(shè)置n-x個(gè)公用信號量，x表示起始進(jìn)程個(gè)數(shù)；方法2在圖中存在n個(gè)進(jìn)程，則需要設(shè)置n-x個(gè)同步信號量，x取決于終點(diǎn)進(jìn)程的數(shù)目。2、利用信號量實(shí)現(xiàn)前趨關(guān)系7/23/2023127第二章進(jìn)程管理例：試用信號量實(shí)現(xiàn)這三個(gè)進(jìn)程的同步。方法1：設(shè)有兩個(gè)共用信號量SB、SC，初值均為0。Pa：Pb：Pc：…P(SB);P(SC)

V(SB);……V(SC);2、利用信號量實(shí)現(xiàn)前趨關(guān)系7/23/2023128第二章進(jìn)程管理方法2：設(shè)有一個(gè)同步信號量SA，初值均為0。Pa：Pb：Pc：…P(SA);P(SA)

V(SA);……V(SA);2、利用信號量實(shí)現(xiàn)前趨關(guān)系7/23/2023129第二章進(jìn)程管理【思考題1】試用信號量實(shí)現(xiàn)這三個(gè)進(jìn)程的同步。7/23/2023130第二章進(jìn)程管理解設(shè)有一個(gè)信號量S3，初值均為0。P1：P2：P3：……P(S3)

V(S3);V(S3);P(S3)…7/23/2023131第二章進(jìn)程管理【思考題2】試用信號量實(shí)現(xiàn)這6個(gè)進(jìn)程的同步。7/23/2023132第二章進(jìn)程管理解設(shè)有5個(gè)信號量S2、S3、S4、S5、S6，初值均為０P1：P2：P3：…P(S2);P(S3)

V(S2);……V(S3);V(S4);V(S6);V(S5)P4：P5：P6：P(S4);P(S5);P(S6);…P(S5);P(S6);……V(S5);V(S6);7/23/2023133第二章進(jìn)程管理2.4經(jīng)典的進(jìn)程同步問題2.4.1生產(chǎn)者/消費(fèi)者問題2.4.2哲學(xué)家進(jìn)餐問題2.4.3讀者/寫者問題2.4.4理發(fā)師問題7/23/2023134第二章進(jìn)程管理2.4.1生產(chǎn)者/消費(fèi)者問題生產(chǎn)者消費(fèi)者問題是一種同步問題的抽象描述。計(jì)算機(jī)系統(tǒng)中的每個(gè)進(jìn)程都可以消費(fèi)（使用）或生產(chǎn)（釋放）某類資源。這些資源可以是硬件資源，也可以是軟件資源。當(dāng)某一進(jìn)程使用某一資源時(shí)，可以看作是消費(fèi)，稱該進(jìn)程為消費(fèi)者。而當(dāng)某一進(jìn)程釋放某一資源時(shí)，它就相當(dāng)于生產(chǎn)者。7/23/2023135第二章進(jìn)程管理問題描述通過一個(gè)有界緩沖區(qū)可以把一群生產(chǎn)者p1,p2…,pm，和一群消費(fèi)者Q1,Q2,…,Qn聯(lián)系起來。如圖只要緩沖區(qū)未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)；只要緩沖區(qū)未空，消費(fèi)者就可以從緩沖區(qū)中取走物品。7/23/2023136第二章進(jìn)程管理圖7/23/2023137第二章進(jìn)程管理問題分析由于在此問題中有M個(gè)生產(chǎn)者和N個(gè)消費(fèi)者，它們在執(zhí)行生產(chǎn)活動(dòng)和消費(fèi)活動(dòng)中要對有界緩沖區(qū)進(jìn)行操作。由于有界緩沖區(qū)是一個(gè)臨界資源，必須互斥使用，所以還需要設(shè)置一個(gè)互斥信號量mutex，其初值為１。7/23/2023138第二章進(jìn)程管理問題分析為解決生產(chǎn)者消費(fèi)者問題，可以設(shè)兩個(gè)同步（資源）信號量：一個(gè)代表空緩沖區(qū)的數(shù)目，用empty表示，初值為有界緩沖區(qū)的大小n；一個(gè)代表已用緩沖區(qū)的數(shù)目，用full表示，初值為0。7/23/20