操作系統(tǒng)第2章進(jìn)程管理

第二章進(jìn)程管理操作系統(tǒng)劉剛2/4/20231第二章進(jìn)程管理重點(diǎn)理解進(jìn)程的含義理解和掌握同步的概念及經(jīng)典進(jìn)程同步問(wèn)題，是本課程的重點(diǎn)之一難點(diǎn)會(huì)寫(xiě)進(jìn)程同步問(wèn)題的算法知識(shí)點(diǎn)進(jìn)程、線程、進(jìn)程的特征、PCB、進(jìn)程控制、進(jìn)程狀態(tài)轉(zhuǎn)換、進(jìn)程同步、進(jìn)程通信2/4/20232第二章進(jìn)程管理進(jìn)程的基本概念進(jìn)程控制進(jìn)程同步經(jīng)典進(jìn)程的同步問(wèn)題管程機(jī)制進(jìn)程通信線程2/4/20233進(jìn)程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進(jìn)程的特征與狀態(tài)進(jìn)程控制塊2/4/20234程序的順序執(zhí)行及其特征兩種方式順序執(zhí)行：是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡(jiǎn)單的單片機(jī)系統(tǒng)并發(fā)執(zhí)行：現(xiàn)在的操作系統(tǒng)，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率順序執(zhí)行的特征順序性：按照程序結(jié)構(gòu)所指定的次序（可能有分支或循環(huán)）封閉性：獨(dú)占全部資源，計(jì)算機(jī)的狀態(tài)只由于該程序的控制邏輯所決定可再現(xiàn)性：初始條件相同則結(jié)果相同。如：可通過(guò)空指令控制時(shí)間關(guān)系2/4/20235程序的順序執(zhí)行及其特征僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。語(yǔ)句s1,s2,s3必須按順序執(zhí)行S1:a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;2/4/20236程序的順序執(zhí)行及其特征Ii→Ci→Pi和S1→S2→S3程序的順序執(zhí)行(a)程序的順序執(zhí)行I1C1P1I2C2P2(b)三條語(yǔ)句的順序執(zhí)行S1S2S32/4/20237進(jìn)程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進(jìn)程的特征與狀態(tài)進(jìn)程控制塊2/4/20238前趨圖前趨圖(PrecedenceGraph)是一個(gè)有向無(wú)循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語(yǔ)句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(PartialOrder)或前趨關(guān)系(PrecedenceRelation)“→”→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可寫(xiě)成Pi→Pj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒(méi)有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(InitialNode)，把沒(méi)有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(FinalNode)2/4/20239前趨圖每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight,權(quán)值)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間P1P3P8P9P4P2P5P6P7(a)具有九個(gè)結(jié)點(diǎn)的前趨圖S1S2S3(b)具有循環(huán)的前趨圖2/4/202310前趨圖對(duì)于圖(a)所示的前趨圖，存在下述前趨關(guān)系P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9或表示為：P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}應(yīng)當(dāng)注意，前趨圖中必須不存在循環(huán)，但在圖(b)中卻有著下述的前趨關(guān)系：S2→S3,S3→S22/4/202311進(jìn)程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進(jìn)程的特征與狀態(tài)進(jìn)程控制塊2/4/202312程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行時(shí)的前趨圖2/4/202313程序的并發(fā)執(zhí)行及其特征在該例中存在下述前趨關(guān)系：Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。2/4/202314程序的并發(fā)執(zhí)行及其特征對(duì)于具有下述四條語(yǔ)句的程序段S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+bS1S2S3S42/4/202315程序的并發(fā)執(zhí)行及其特征例如有兩個(gè)循環(huán)程序A和B，它們共享一個(gè)變量N程序A和B以不同的速度運(yùn)行(失去封閉性，導(dǎo)致不可再現(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程序A：N∶=N+1;

程序B：

Print(N);N∶=0;

2/4/202316程序的并發(fā)執(zhí)行及其特征N：n程序A：N∶=N+1;

//N==n+1程序B：

Print(N);//N=n+1N∶=0;

//N==0程序切換N：n程序B：Print(N);//N=nN∶=0;

//N==0程序A：N∶=N+1;

//N==1程序切換N：n程序B：

Print(N);//N=n程序切換程序A：N∶=N+1;

//N==n+1程序切換程序B：N∶=0;

//N==0注意：A、B程序得到的共享變量結(jié)果不同，失去封閉性、不可再現(xiàn)性；要得到良好的控制，系統(tǒng)必須要進(jìn)行管理——進(jìn)程控制管理2/4/202317程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行的特征間斷(異步)性"走走停停"，一個(gè)程序可能走到中途停下來(lái)，失去原有的時(shí)序關(guān)系；失去封閉性共享資源，受其他程序的控制邏輯的影響。如：一個(gè)程序?qū)懙酱鎯?chǔ)器中的數(shù)據(jù)可能被另一個(gè)程序修改，失去原有的不變特征。失去可再現(xiàn)性失去封閉性－>失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征2/4/202318程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行失去封閉性的原因是共享資源的影響，去掉這種影響就行了。1966年，由Bernstein給出并發(fā)執(zhí)行的條件。（這里沒(méi)有考慮執(zhí)行速度的影響。）程序P(i)針對(duì)共享變量的讀集和寫(xiě)集R(i)和W(i)條件：任意兩個(gè)程序P(i)和P(j)，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;前兩條保證一個(gè)程序的兩次讀之間數(shù)據(jù)不變化；最后一條保證寫(xiě)的結(jié)果不丟掉現(xiàn)在的問(wèn)題是這個(gè)條件不好檢查2/4/202319程序并發(fā)執(zhí)行的條件（1966年由Bernstein提出）若兩個(gè)程序P1和P2滿足下述條件，便能并發(fā)執(zhí)行且有可再現(xiàn)性：R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}“讀集”R(Pi)為程序Pi在執(zhí)行期間所需參考的所有變量的集合?！皩?xiě)集”W(Pi)為程序Pi在執(zhí)行期間所需改變的所有變量的集合。例如：S1: a:=x+y S2: b:=z+1 S3: c:=a-b S4: d:=c+12/4/202320程序并發(fā)執(zhí)行的條件（1966年由Bernstein提出）S1: a:=x+y R(S1)={ } W(S1)={ }S2: b:=z+1 R(S2)={ } W(S2)={ }S3: c:=a-b R(S3)={ } W(S3)={ }S4: d:=c+1 R(S4)={ } W(S4)={ }語(yǔ)句S1、S2______并發(fā)，因?yàn)開(kāi)_____________________。語(yǔ)句S1、S3______并發(fā)，因?yàn)開(kāi)_____________________。語(yǔ)句S2、S3______并發(fā)，因?yàn)開(kāi)_____________________。語(yǔ)句S3、S4______并發(fā)，因?yàn)開(kāi)_____________________。語(yǔ)句S2、S4______并發(fā)，因?yàn)開(kāi)_____________________。x,yazba,bccd可以R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}不能R(S3)∩W(S1)={a}≠{}不能不能可以R(S3)∩W(S2)=≠{}R(S4)∩W(S3)={c}≠{}2/4/202321進(jìn)程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進(jìn)程概念進(jìn)程的特征與狀態(tài)進(jìn)程控制塊2/4/202322進(jìn)程概念何謂進(jìn)程（Process）如何理解進(jìn)程概念？進(jìn)程與程序有何差別？描述性定義：計(jì)算機(jī)中的所有程序（軟件），按照某種順序運(yùn)行，這種運(yùn)行的過(guò)程稱之為進(jìn)程。2/4/202323進(jìn)程概念閱讀菜譜準(zhǔn)備原料烹制菜肴飯菜閱讀洗衣機(jī)手冊(cè)準(zhǔn)備衣服、洗衣粉設(shè)定參數(shù)，洗衣服干凈衣服程序輸入運(yùn)行輸出程序輸入運(yùn)行輸出分時(shí)切換洗衣進(jìn)程做飯進(jìn)程2/4/202324進(jìn)程概念進(jìn)程的核心思想進(jìn)程是某種類型的一個(gè)活動(dòng)，它有程序、輸入、輸出和狀態(tài)。在分時(shí)操作系統(tǒng)中，單個(gè)CPU被若干進(jìn)程共享，它使用某種調(diào)度算法決定何時(shí)停止一個(gè)進(jìn)程的運(yùn)行，轉(zhuǎn)而為其他進(jìn)程提供服務(wù)。2/4/202325進(jìn)程概念較典型的進(jìn)程定義有：進(jìn)程是程序的一次執(zhí)行進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位2/4/202326進(jìn)程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進(jìn)程概念進(jìn)程的特征與狀態(tài)進(jìn)程控制塊2/4/202327進(jìn)程的特征與狀態(tài)動(dòng)態(tài)性：進(jìn)程具有動(dòng)態(tài)的地址空間（數(shù)量和內(nèi)容），地址空間上包括：代碼（指令執(zhí)行和CPU狀態(tài)的改變）數(shù)據(jù)（變量的生成和賦值）系統(tǒng)控制信息（進(jìn)程控制塊的建立和系統(tǒng)收回）獨(dú)立性：各進(jìn)程的地址空間相互獨(dú)立，除非采用進(jìn)程間通信手段；并發(fā)性：多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，且能在一段時(shí)間內(nèi)同時(shí)運(yùn)行；引入進(jìn)程實(shí)體的目的就是并發(fā)執(zhí)行異步性：各進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)結(jié)構(gòu)性：程序段、數(shù)據(jù)段和PCB；程序文件中通常也劃分了代碼段和數(shù)據(jù)段，進(jìn)程的創(chuàng)建與撤消就是PCB的創(chuàng)建與撤消2/4/2023282.1.4進(jìn)程的特征與狀態(tài)1.進(jìn)程的特征和定義 通常的程序是不能并發(fā)執(zhí)行的。應(yīng)為之配置進(jìn)程控制塊，即PCB；而由程序段、相關(guān)的數(shù)據(jù)段和PCB三部分便構(gòu)成了進(jìn)程實(shí)體。在許多情況下所說(shuō)的進(jìn)程，實(shí)際上是指進(jìn)程實(shí)體。所謂創(chuàng)建進(jìn)程，實(shí)質(zhì)上是創(chuàng)建進(jìn)程實(shí)體中的PCB；而撤銷進(jìn)程，實(shí)質(zhì)上是撤銷進(jìn)程的PCB。2/4/202329進(jìn)程概念較典型的進(jìn)程定義有：進(jìn)程是程序的一次執(zhí)行進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位在引入了進(jìn)程實(shí)體的概念后，我們可以把傳統(tǒng)OS中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位”2/4/202330進(jìn)程與程序的區(qū)別進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進(jìn)程是程序的執(zhí)行。通常進(jìn)程不可在計(jì)算機(jī)之間遷移；而程序通常對(duì)應(yīng)著文件、靜態(tài)和可以復(fù)制進(jìn)程是暫時(shí)的，程序的永久的：進(jìn)程是一個(gè)狀態(tài)變化的過(guò)程，程序可長(zhǎng)久保存進(jìn)程與程序的組成不同：進(jìn)程的組成包括程序、數(shù)據(jù)和進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）進(jìn)程與程序的對(duì)應(yīng)關(guān)系：通過(guò)多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程；通過(guò)調(diào)用關(guān)系，一個(gè)進(jìn)程可包括多個(gè)程序2/4/202331進(jìn)程的特征與狀態(tài)—進(jìn)程的三種基本狀態(tài)就緒(Ready)狀態(tài)

可運(yùn)行，已獲得除CPU外的所需資源，等待分配CPU一個(gè)系統(tǒng)中多個(gè)處于就緒狀態(tài)的進(jìn)程排成就緒隊(duì)列執(zhí)行(Running)狀態(tài)占用CPU運(yùn)行；處于此狀態(tài)的進(jìn)程的數(shù)目<=CPU的數(shù)目沒(méi)有其它進(jìn)程可以執(zhí)行時(shí)（如所有進(jìn)程都在阻塞狀態(tài)），通常會(huì)自動(dòng)執(zhí)行系統(tǒng)的idle進(jìn)程（相當(dāng)于空操作）阻塞(Blocked)狀態(tài)

等待某種條件（如I/O操作或進(jìn)程同步），在條件滿足之前無(wú)法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程，也無(wú)法運(yùn)行通常阻塞進(jìn)程也排成一個(gè)阻塞隊(duì)列2/4/202332進(jìn)程的特征與狀態(tài)—進(jìn)程的三種基本狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請(qǐng)求進(jìn)程調(diào)度時(shí)間片完2/4/202333進(jìn)程的特征與狀態(tài)—進(jìn)程的三種基本狀態(tài)問(wèn)題1：為什么不能從阻塞態(tài)變?yōu)檫\(yùn)行態(tài)呢？問(wèn)題2：為什么不能從就緒態(tài)變?yōu)樽枞麘B(tài)呢？2/4/202334進(jìn)程的特征與狀態(tài)—進(jìn)程的三種基本狀態(tài)問(wèn)題1：為什么不能從阻塞態(tài)變?yōu)檫\(yùn)行態(tài)呢？問(wèn)題2：為什么不能從就緒態(tài)變?yōu)樽枞麘B(tài)呢？答案：三種狀態(tài)的變換體現(xiàn)了OS的資源管理作用進(jìn)程的核心思想在于運(yùn)行——CPU資源的分配狀態(tài)不能夠滿足系統(tǒng)和用戶需要?。?！2/4/202335創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)4)創(chuàng)建狀態(tài)進(jìn)程剛建立，還未進(jìn)入就緒隊(duì)列。5)終止?fàn)顟B(tài)進(jìn)程已（正?；虍惓＃┙Y(jié)束，已從就緒隊(duì)列中移出，但尚未撤銷。暫留，以便其他進(jìn)程收集該進(jìn)程的有關(guān)信息。2/4/202336圖2-5進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換創(chuàng)建

終止

2/4/202337進(jìn)程的特征與狀態(tài)—掛起狀態(tài)（靜止?fàn)顟B(tài)）這個(gè)問(wèn)題的出現(xiàn)是由于進(jìn)程優(yōu)先級(jí)的引入，一些低優(yōu)先級(jí)進(jìn)程可能等待較長(zhǎng)時(shí)間，從而被對(duì)換至外存。這樣做的目的是：提高處理機(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)程（從而對(duì)其地址空間進(jìn)行讀寫(xiě)）2/4/202338進(jìn)程的特征與狀態(tài)—掛起狀態(tài)引起進(jìn)程掛起的原因有以下幾種終端用戶的請(qǐng)求當(dāng)終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)有可疑問(wèn)題時(shí)，希望暫時(shí)將自己的程序靜止下來(lái)父進(jìn)程請(qǐng)求父進(jìn)程需要考查和修改子進(jìn)程負(fù)荷調(diào)節(jié)的需要在實(shí)時(shí)系統(tǒng)中為了調(diào)整工作負(fù)荷可將不重要的進(jìn)程掛起操作系統(tǒng)的需要如檢查運(yùn)行中的資源使用情況2/4/202339進(jìn)程的特征與狀態(tài)—狀態(tài)轉(zhuǎn)換掛起（Suspend）：進(jìn)程從內(nèi)存轉(zhuǎn)到外存就緒掛起：活動(dòng)就緒到靜止就緒，當(dāng)有高優(yōu)先級(jí)阻塞（系統(tǒng)認(rèn)為會(huì)很快就緒的）進(jìn)程和低優(yōu)先級(jí)就緒進(jìn)程時(shí)，系統(tǒng)會(huì)選擇掛起低優(yōu)先級(jí)就緒進(jìn)程阻塞掛起：活動(dòng)阻塞到靜止阻塞，無(wú)進(jìn)程處于就緒狀態(tài)或就緒進(jìn)程要求更多內(nèi)存資源時(shí)，會(huì)進(jìn)行這種轉(zhuǎn)換，以提交新進(jìn)程或運(yùn)行就緒進(jìn)程運(yùn)行到就緒掛起：對(duì)搶占式分時(shí)系統(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)①執(zhí)行的進(jìn)程暫停②就緒的進(jìn)程暫不調(diào)度③阻塞的進(jìn)程即使引起阻塞的事件消失也不調(diào)度2/4/202340進(jìn)程的特征與狀態(tài)—狀態(tài)轉(zhuǎn)換激活（Activate）：進(jìn)程從外存轉(zhuǎn)到內(nèi)存就緒激活：靜止就緒到活動(dòng)就緒，沒(méi)有就緒進(jìn)程或掛起就緒進(jìn)程優(yōu)先級(jí)高于就緒進(jìn)程時(shí)，會(huì)進(jìn)行這種轉(zhuǎn)換；阻塞激活：靜止阻塞到活動(dòng)阻塞，當(dāng)一個(gè)進(jìn)程釋放足夠內(nèi)存時(shí)，系統(tǒng)會(huì)把一個(gè)高優(yōu)先級(jí)阻塞掛起（系統(tǒng)認(rèn)為會(huì)很快出現(xiàn)所等待的事件）進(jìn)程激活；2/4/202341進(jìn)程的特征與狀態(tài)—轉(zhuǎn)換事件出現(xiàn)(EventOccurs)：進(jìn)程等待的事件出現(xiàn)，如：操作完成、申請(qǐng)成功等；可能的情況有：阻塞到就緒：針對(duì)內(nèi)存進(jìn)程的事件出現(xiàn)；阻塞掛起到就緒掛起：針對(duì)外存進(jìn)程的事件出現(xiàn)；收容(Admit)：收容一個(gè)新進(jìn)程，進(jìn)入就緒狀態(tài)或就緒掛起狀態(tài)。進(jìn)入就緒掛起的原因是系統(tǒng)希望保持一個(gè)大的就緒進(jìn)程表（掛起和非掛起）；2/4/202342進(jìn)程的特征與狀態(tài)—狀態(tài)轉(zhuǎn)換具有掛起狀態(tài)的進(jìn)程狀態(tài)圖I/O完成2/4/202343進(jìn)程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進(jìn)程概念進(jìn)程的特征與狀態(tài)進(jìn)程控制塊2/4/202344進(jìn)程控制塊進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。或者說(shuō)，OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的進(jìn)程控制塊中的信息進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符：內(nèi)部標(biāo)識(shí)符在所有的操作系統(tǒng)中，都為每一個(gè)進(jìn)程賦予一個(gè)惟一的數(shù)字標(biāo)識(shí)符，它通常是一個(gè)進(jìn)程的序號(hào)。設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便系統(tǒng)使用外部標(biāo)識(shí)符它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進(jìn)程)在訪問(wèn)該進(jìn)程時(shí)使用。為了描述進(jìn)程的家族關(guān)系，還應(yīng)設(shè)置父進(jìn)程標(biāo)識(shí)及子進(jìn)程標(biāo)識(shí)。此外，還可設(shè)置用戶標(biāo)識(shí)，以指示擁有該進(jìn)程的用戶系統(tǒng)感知進(jìn)程存在的惟一標(biāo)志?。?/4/202345進(jìn)程控制塊進(jìn)程控制塊中的信息處理機(jī)狀態(tài)（CPU現(xiàn)場(chǎng)保護(hù)區(qū)）主要是由CPU的各種寄存器中的內(nèi)容組成的：通用寄存器又稱為用戶可視寄存器，是用戶程序可以訪問(wèn)的，用于暫存信息，在大多數(shù)處理機(jī)中，有8~32個(gè)通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過(guò)100個(gè)；指令計(jì)數(shù)器其中存放了要訪問(wèn)的下一條指令的地址；程序狀態(tài)字PSW其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、中斷屏蔽標(biāo)志等；用戶棧指針指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂2/4/202346進(jìn)程控制塊進(jìn)程控制塊中的信息進(jìn)程調(diào)度信息存放與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信息，包括:進(jìn)程狀態(tài)指明進(jìn)程的當(dāng)前狀態(tài)，作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)；進(jìn)程優(yōu)先級(jí)用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)，調(diào)度的依據(jù)，高者優(yōu)先獲得處理機(jī)；進(jìn)程調(diào)度所需的其它信息它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等；事件是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因2/4/202347進(jìn)程控制塊進(jìn)程控制塊中的信息進(jìn)程控制信息程序和數(shù)據(jù)的地址是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)；進(jìn)程同步和通信機(jī)制指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制，如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地放在PCB中；占用資源清單列出了除CPU以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單；鏈接指針?biāo)o出了本進(jìn)程(PCB)所在隊(duì)列中的下一個(gè)進(jìn)程的PCB的首地址家族聯(lián)系指明本進(jìn)程與家族的關(guān)系，如它的子進(jìn)程與父進(jìn)程的標(biāo)識(shí)2/4/202348進(jìn)程控制塊進(jìn)程控制塊的組織方式鏈接方式把具有同一狀態(tài)的PCB用其中的鏈接字鏈接成一個(gè)隊(duì)列，可以形成就緒隊(duì)列、若干個(gè)阻塞隊(duì)列和空白隊(duì)列2/4/202349進(jìn)程控制塊進(jìn)程控制塊的組織方式索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表，如就緒索引表、阻塞索引表等，并把各索引表在內(nèi)存的首地址記錄在專用單元中。索引表中記錄的是PCB在PCB表中的地地址2/4/202350第二章進(jìn)程管理進(jìn)程的基本概念

進(jìn)程控制進(jìn)程同步經(jīng)典進(jìn)程的同步問(wèn)題管程機(jī)制進(jìn)程通信線程2/4/202351進(jìn)程控制職責(zé)是對(duì)系統(tǒng)中全部進(jìn)程實(shí)施有效管理，包括創(chuàng)建新進(jìn)程終止已結(jié)束進(jìn)程終止由于某事件而無(wú)法運(yùn)行下去的進(jìn)程負(fù)責(zé)進(jìn)程的狀態(tài)轉(zhuǎn)換這些功能一般由操作系統(tǒng)的內(nèi)核實(shí)現(xiàn)，操作系統(tǒng)的內(nèi)核是基于硬件的第一次擴(kuò)充。把與硬件緊密相關(guān)的模塊、運(yùn)行頻率較高的模塊及一些公用的基本操作安排在靠近硬件的軟件層次中，并常駐內(nèi)存，以提高系統(tǒng)運(yùn)行效率。這些進(jìn)程控制功能是通過(guò)執(zhí)行各種原語(yǔ)實(shí)現(xiàn)的！2/4/202352操作系統(tǒng)內(nèi)核OS內(nèi)核是計(jì)算機(jī)硬件的第一層軟件擴(kuò)充，常駐內(nèi)存。例：中斷處理程序、設(shè)備驅(qū)動(dòng)程序以及時(shí)鐘管理、進(jìn)程調(diào)度等。一、支撐功能中斷處理：最基本的功能，是OS的基礎(chǔ)。時(shí)鐘管理：為基本功能，如分時(shí)系統(tǒng)的時(shí)間片，實(shí)時(shí)系統(tǒng)的時(shí)間控制。原語(yǔ)操作：是原子操作（是不可分割的操作），用來(lái)執(zhí)行基本操作。創(chuàng)建、撤銷、阻塞、喚醒、掛起、激活。2/4/202353操作系統(tǒng)內(nèi)核OS內(nèi)核是計(jì)算機(jī)硬件的第一層軟件擴(kuò)充，常駐內(nèi)存。例：中斷處理程序、設(shè)備驅(qū)動(dòng)程序以及時(shí)鐘管理、進(jìn)程調(diào)度等。二、資源管理功能進(jìn)程管理：放在內(nèi)核。例：調(diào)度、分派、創(chuàng)建、撤銷、同步、通信。運(yùn)行頻率高。存儲(chǔ)器管理：內(nèi)存分配、回收、保護(hù)、對(duì)換等放在內(nèi)核，保證運(yùn)行速度高。設(shè)備管理：驅(qū)動(dòng)程序、緩沖管理、設(shè)備分配等。2/4/202354進(jìn)程控制原語(yǔ)(primitive)由若干條指令構(gòu)成的“原子操作(atomicoperation)”過(guò)程，作為一個(gè)整體而不可分割－－要么全都做，要么全不做系統(tǒng)調(diào)用并不都是原語(yǔ)進(jìn)程A調(diào)用read()，因無(wú)數(shù)據(jù)而阻塞，在read()里未返回。然后進(jìn)程B調(diào)用read()，此時(shí)read()被重入。系統(tǒng)調(diào)用不一定一次執(zhí)行完并返回該進(jìn)程，有可能在特定的點(diǎn)暫停，而轉(zhuǎn)入到其他進(jìn)程處理機(jī)的執(zhí)行狀態(tài)——保護(hù)系統(tǒng)程序核心態(tài)（管態(tài)、系統(tǒng)態(tài)）系統(tǒng)管理程序執(zhí)行時(shí)的狀態(tài)。具有較高的特權(quán)，能執(zhí)行一切指令，訪問(wèn)所有的寄存器和存儲(chǔ)區(qū)用戶態(tài)（目態(tài)）以后程序執(zhí)行時(shí)的狀態(tài)。具有較低的特權(quán)，只能執(zhí)行規(guī)定指令，訪問(wèn)指定的寄存器和存儲(chǔ)區(qū)2/4/202355進(jìn)程控制進(jìn)程的創(chuàng)建進(jìn)程的終止進(jìn)程的阻塞與喚醒進(jìn)程的掛起與激活2/4/202356進(jìn)程的創(chuàng)建進(jìn)程圖(ProcessGraph)是用于描述一個(gè)進(jìn)程的家族關(guān)系的有向樹(shù)，樹(shù)中的結(jié)點(diǎn)表示進(jìn)程在進(jìn)程Pi創(chuàng)建了進(jìn)程Pj之后稱Pi是Pj的父進(jìn)程(ParentProcess)，Pj是Pi的子進(jìn)程(ProgenyProcess)。創(chuàng)建父進(jìn)程的進(jìn)程稱為祖先進(jìn)程，把樹(shù)的根結(jié)點(diǎn)稱為進(jìn)程家族的祖先進(jìn)程(Ancestor)子進(jìn)程可以繼承(Inherit)父進(jìn)程的資源撤消父進(jìn)程時(shí)必須同時(shí)撤消子進(jìn)程PCB中設(shè)家族關(guān)系表項(xiàng)2/4/202357進(jìn)程的創(chuàng)建引起創(chuàng)建進(jìn)程的事件

在多道程序環(huán)境中，要運(yùn)行程序，必須為其創(chuàng)建進(jìn)程用戶登錄 分時(shí)系統(tǒng)的用戶在終端登錄后，如是合法用戶，系統(tǒng)將為其創(chuàng)建一個(gè)進(jìn)程，并插入就緒隊(duì)列作業(yè)調(diào)度 在批處理系統(tǒng)中，當(dāng)作業(yè)調(diào)度程序調(diào)度到某作業(yè)時(shí)，將該作業(yè)裝入內(nèi)存，為它分配資源并創(chuàng)建進(jìn)程提供服務(wù) 當(dāng)運(yùn)行中的用戶進(jìn)程提出某種請(qǐng)求后，系統(tǒng)將專門(mén)創(chuàng)建一個(gè)進(jìn)程來(lái)提供服務(wù)，如打印應(yīng)用請(qǐng)求 由應(yīng)用程序?yàn)樽约簞?chuàng)建進(jìn)程，以便能并發(fā)執(zhí)行，如輸入、計(jì)算、輸出程序內(nèi)核創(chuàng)建2/4/202358進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建(CreationofProcess)申請(qǐng)空白PCB為新進(jìn)程申請(qǐng)惟一的數(shù)字標(biāo)識(shí)符，并從PCB集合中索取一個(gè)空白PCB為新進(jìn)程分配資源為新進(jìn)程的程序和數(shù)據(jù)分配內(nèi)存。對(duì)于批處理型作業(yè)，可在用戶提出創(chuàng)建進(jìn)程時(shí)要求提供所需內(nèi)存大小。對(duì)于交互型作業(yè)可以由系統(tǒng)來(lái)分配一定的空間初始化進(jìn)程控制塊初始化標(biāo)識(shí)信息將系統(tǒng)標(biāo)識(shí)信息寫(xiě)入新PCB初始化處理機(jī)狀態(tài)信息使程序計(jì)數(shù)器指向程序的入口地址，棧指針指向棧頂初始化處理機(jī)控制信息將進(jìn)程的狀態(tài)設(shè)為就緒狀態(tài)或靜止就緒狀態(tài)將新進(jìn)程插入就緒隊(duì)列如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程，便將新進(jìn)程插入就緒隊(duì)列2/4/202359進(jìn)程控制進(jìn)程的創(chuàng)建進(jìn)程的終止進(jìn)程的阻塞與喚醒進(jìn)程的掛起與激活2/4/202360進(jìn)程的終止引起進(jìn)程終止(TerminationofProcess)的事件正常結(jié)束 應(yīng)有一個(gè)通知OS進(jìn)程已經(jīng)運(yùn)行完成的指令。如，在批處理系統(tǒng)中，通常在程序最后安排一條Halt指令或終止的系統(tǒng)調(diào)用。當(dāng)程序執(zhí)行Halt指令時(shí)，將產(chǎn)生一個(gè)中斷，通知OS本進(jìn)程已經(jīng)完成。在分時(shí)系統(tǒng)中，用戶可利用Logsoff去表示進(jìn)程運(yùn)行完畢，此時(shí)同樣產(chǎn)生一個(gè)中斷，告知OS進(jìn)程已運(yùn)行完畢異常結(jié)束 在進(jìn)程運(yùn)行期間，由于出現(xiàn)某些錯(cuò)誤和故障而迫使進(jìn)程終止。越界錯(cuò)誤這是指程序所訪問(wèn)的存儲(chǔ)區(qū)，已越出該進(jìn)程的區(qū)域2/4/202361進(jìn)程的終止保護(hù)錯(cuò)進(jìn)程試圖訪問(wèn)一不允許訪問(wèn)的資源或文件，或者以不適當(dāng)?shù)姆绞竭M(jìn)行訪問(wèn)，如進(jìn)程試圖去寫(xiě)一個(gè)只讀文件非法指令程序試圖去執(zhí)行一條不存在的指令。出現(xiàn)該錯(cuò)誤的原因，可能是程序錯(cuò)誤地轉(zhuǎn)移到數(shù)據(jù)區(qū)，把數(shù)據(jù)當(dāng)成了指令特權(quán)指令錯(cuò)用戶進(jìn)程試圖去執(zhí)行一條只允許OS執(zhí)行的指令運(yùn)行超時(shí)進(jìn)程的執(zhí)行時(shí)間超過(guò)了指定的最大值；等待超時(shí)進(jìn)程等待某事件的時(shí)間，超過(guò)了規(guī)定的最大值；算術(shù)運(yùn)算錯(cuò)進(jìn)程試圖去執(zhí)行一個(gè)被禁止的運(yùn)算，如被0除；I/O故障這是指在I/O過(guò)程中發(fā)生了錯(cuò)誤等2/4/202362進(jìn)程的終止引起進(jìn)程終止(TerminationofProcess)的事件外界干預(yù) 外界干預(yù)并非指在本進(jìn)程運(yùn)行中出現(xiàn)了異常事件，而是指進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行操作員或操作系統(tǒng)干預(yù)由于某種原因，例如，發(fā)生了死鎖，由操作員或操作系統(tǒng)終止該進(jìn)程父進(jìn)程請(qǐng)求由于父進(jìn)程具有終止自己的任何子孫進(jìn)程的權(quán)利，因而當(dāng)父進(jìn)程提出請(qǐng)求時(shí)，系統(tǒng)將終止該進(jìn)程；父進(jìn)程終止當(dāng)父進(jìn)程終止時(shí)，OS也將他的所有子孫進(jìn)程終止2/4/202363進(jìn)程的終止進(jìn)程的終止過(guò)程根據(jù)被終止進(jìn)程的標(biāo)識(shí)符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，以便進(jìn)程撤消后將處理機(jī)分配給其他進(jìn)程若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止，以防他們成為不可控的進(jìn)程將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)撤消PCB2/4/202364進(jìn)程控制進(jìn)程的創(chuàng)建進(jìn)程的終止進(jìn)程的阻塞與喚醒進(jìn)程的掛起與激活2/4/202365進(jìn)程的阻塞與喚醒引起進(jìn)程阻塞和喚醒的事件請(qǐng)求系統(tǒng)服務(wù) 如請(qǐng)求打印機(jī)時(shí)，若已被其他進(jìn)程占用，此時(shí)只能阻塞，等其他進(jìn)程釋放后再將請(qǐng)求進(jìn)程喚醒啟動(dòng)某種操作 當(dāng)進(jìn)程啟動(dòng)某種操作后，如果該進(jìn)程必須在該操作完成后才能繼續(xù)執(zhí)行，則必須先使進(jìn)程阻塞，以等待該操作完成。如啟動(dòng)I/O設(shè)備新數(shù)據(jù)尚未到達(dá) 對(duì)于相互合作的進(jìn)程，如果一個(gè)進(jìn)程需要另一合作進(jìn)程提供的數(shù)據(jù)，則在數(shù)據(jù)到達(dá)之前只能阻塞無(wú)新工作可做 系統(tǒng)中的一些特殊功能進(jìn)程，在完成了任務(wù)之后，等待新任務(wù)到來(lái)。如系統(tǒng)中的發(fā)送進(jìn)程2/4/202366進(jìn)程的阻塞與喚醒進(jìn)程阻塞過(guò)程正在執(zhí)行的進(jìn)程，當(dāng)發(fā)現(xiàn)上述某事件時(shí)，因無(wú)法繼續(xù)執(zhí)行，進(jìn)程便通過(guò)調(diào)用阻塞原語(yǔ)block()把自己阻塞?？梢?jiàn)，進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為進(jìn)入block過(guò)程后，由于此時(shí)該進(jìn)程還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列若系統(tǒng)中設(shè)置了因不同事件而阻塞的多個(gè)阻塞隊(duì)列，則將本進(jìn)程插入到具有相同事件的阻塞(等待)隊(duì)列調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀態(tài)(在PCB中)，再按新進(jìn)程的PCB中的處理機(jī)狀態(tài)設(shè)置CPU的環(huán)境2/4/202367進(jìn)程的阻塞與喚醒進(jìn)程喚醒過(guò)程當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時(shí)，如I/O完成或其所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程(比如，用完并釋放了該I/O設(shè)備的進(jìn)程)調(diào)用喚醒原語(yǔ)wakeup()，將等待該事件的進(jìn)程喚醒喚醒原語(yǔ)執(zhí)行的過(guò)程是把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒將該P(yáng)CB插入到就緒隊(duì)列中2/4/2023683.進(jìn)程喚醒過(guò)程應(yīng)當(dāng)指出，block原語(yǔ)和wakeup原語(yǔ)是一對(duì)作用剛好相反的原語(yǔ)。因此，如果在某進(jìn)程中調(diào)用了阻塞原語(yǔ)，則必須在與之相合作的另一進(jìn)程中或其他相關(guān)的進(jìn)程中，安排喚醒原語(yǔ)，以能喚醒阻塞進(jìn)程；否則，被阻塞進(jìn)程將會(huì)因不能被喚醒而長(zhǎng)久的處于阻塞狀態(tài)，從而再無(wú)機(jī)會(huì)繼續(xù)運(yùn)行。2/4/202369進(jìn)程的掛起與激活進(jìn)程的掛起當(dāng)出現(xiàn)引起進(jìn)程掛起的事件時(shí)，比如，用戶進(jìn)程請(qǐng)求將自己掛起，或父進(jìn)程請(qǐng)求將自己的某個(gè)子進(jìn)程掛起，系統(tǒng)將利用掛起原語(yǔ)suspend()將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起suspend()原語(yǔ)的執(zhí)行過(guò)程首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒狀態(tài)，便將其改為靜止就緒；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程，則將之改為靜止阻塞為了方便用戶或父進(jìn)程考查該進(jìn)程的運(yùn)行情況而把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度2/4/2023702.2.4進(jìn)程的掛起與激活

1.進(jìn)程的掛起當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，比如，用戶進(jìn)程請(qǐng)求將自己掛起，或父進(jìn)程請(qǐng)求將自己的某個(gè)子進(jìn)程掛起，系統(tǒng)將利用掛起原語(yǔ)suspend()將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。掛起原語(yǔ)的執(zhí)行過(guò)程是：①得到掛起進(jìn)程的__________，②首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒狀態(tài)，便將其改為_(kāi)_______；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程，則將之改為_(kāi)_______；若為正在執(zhí)行，則改為_(kāi)________。為了方便用戶或父進(jìn)程考查該進(jìn)程的運(yùn)行情況而把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。③最后，若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。內(nèi)部標(biāo)識(shí)符靜止就緒靜止阻塞靜止就緒①執(zhí)行的進(jìn)程暫停②就緒的進(jìn)程暫不調(diào)度③阻塞的進(jìn)程即使引起阻塞的事件消失也不調(diào)度2/4/202371進(jìn)程的掛起與激活進(jìn)程的激活過(guò)程當(dāng)發(fā)生激活進(jìn)程的事件時(shí)，如，父進(jìn)程或用戶進(jìn)程請(qǐng)求激活指定進(jìn)程，若該進(jìn)程駐留在外存而內(nèi)存中已有足夠的空間時(shí)，則可將在外存上處于靜止就緒狀態(tài)的進(jìn)程換入內(nèi)存。這時(shí)，系統(tǒng)將利用激活原語(yǔ)active()將指定進(jìn)程激活active()原語(yǔ)執(zhí)行過(guò)程激活原語(yǔ)先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動(dòng)就緒；若為靜止阻塞便將之改為活動(dòng)阻塞若采用搶占調(diào)度策略，則每當(dāng)有新進(jìn)程（激活）進(jìn)入就緒隊(duì)列時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級(jí)的比較，如果被激活進(jìn)程的優(yōu)先級(jí)更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把處理機(jī)分配給剛被激活的進(jìn)程2/4/202372第二章進(jìn)程管理進(jìn)程的基本概念

進(jìn)程控制

進(jìn)程同步

經(jīng)典進(jìn)程的同步問(wèn)題管程機(jī)制進(jìn)程通信線程2/4/2023732.3進(jìn)程同步 進(jìn)程同步的主要任務(wù)，是使并發(fā)執(zhí)行的諸進(jìn)程之間能有效的共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。2/4/202374進(jìn)程同步進(jìn)程同步的基本概念信號(hào)量機(jī)制信號(hào)量的應(yīng)用2/4/202375進(jìn)程同步的基本概念兩種形式的制約關(guān)系

在多道程序環(huán)境下，當(dāng)程序并發(fā)執(zhí)行時(shí)，由于資源共享和進(jìn)程合作，使同處于系統(tǒng)中的諸進(jìn)程之間存在兩種形式的制約關(guān)系間接相互制約關(guān)系 同處于一個(gè)系統(tǒng)中的進(jìn)程必然共享某種資源，如CPU、I/O設(shè)備等，間接相互制約即源于資源共享。如A、B共享打印機(jī)，若A申請(qǐng)打印時(shí)，打印機(jī)已分配給B，則A只能阻塞，等B釋放后再改為就緒，又稱為"互斥"直接相互制約關(guān)系 這種制約源于進(jìn)程之間的合作關(guān)系。如進(jìn)程A向B提供數(shù)據(jù)，當(dāng)輸入緩沖空時(shí)，B不能得到數(shù)據(jù)而阻塞；反之當(dāng)緩沖滿時(shí)，A無(wú)法寫(xiě)入而阻塞，又稱為"同步"2/4/202376進(jìn)程同步的示例共享變量的修改沖突??！2/4/202377進(jìn)程同步的示例getcopyputfstg有3個(gè)進(jìn)程：get,copy和put，它們對(duì)4個(gè)存儲(chǔ)區(qū)域f、s、t和g進(jìn)行操作。操作順序沖突?。?/4/202378進(jìn)程同步的示例有6種可能的操作順序，只有一種結(jié)果是正確的。2/4/202379進(jìn)程的相互關(guān)系：可以按照相互感知的程度來(lái)分類互斥，指多個(gè)進(jìn)程不能同時(shí)使用同一個(gè)資源；死鎖，指多個(gè)進(jìn)程互不相讓，都得不到足夠的資源；饑餓，指一個(gè)進(jìn)程一直得不到資源（其他進(jìn)程可能輪流占用資源）要協(xié)調(diào)進(jìn)程之間的相互制約關(guān)系，就需要實(shí)現(xiàn)進(jìn)程的同步2/4/202380進(jìn)程同步的基本概念臨界資源(CriticalResouce)一次僅允許一個(gè)進(jìn)程使用的資源系統(tǒng)中許多硬件如打印機(jī)等，諸進(jìn)程之間只能用互斥的方式進(jìn)行訪問(wèn)生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。為使生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(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)。盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品2/4/202381inoutcount=2n個(gè)緩沖區(qū)的緩沖池進(jìn)程同步的基本概念生產(chǎn)者-消費(fèi)者問(wèn)題——解決思路利用一個(gè)數(shù)組來(lái)表示上述的具有n個(gè)(0，1，…，n-1)緩沖區(qū)的緩沖池。用輸入指針in來(lái)指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品后，輸入指針加1；用一個(gè)輸出指針out來(lái)指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后，輸出指針加1。設(shè)緩沖池的組織是循環(huán)緩沖，故應(yīng)把輸入指針加1表示成in:=(in+1)modn；輸出指針加1表示成out:=(out+1)modn當(dāng)(in+1)modn=out時(shí)表示緩沖池滿；in=out則表示緩沖池空引入了一個(gè)整型變量counter,其初始值為0。每當(dāng)生產(chǎn)者進(jìn)程向緩沖池中投放一個(gè)產(chǎn)品后，使counter加1；反之，每當(dāng)消費(fèi)者進(jìn)程從中取走一個(gè)產(chǎn)品時(shí)，使counter減12/4/202382進(jìn)程同步的基本概念生產(chǎn)者-消費(fèi)者問(wèn)題——解決思路生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量Varn:integer;typeitem=…;//定義緩沖區(qū)的類型varbuffer:array［0,1,…,n-1］ofitem;//分配緩沖區(qū)in,out:0,1,…,n-1;//定義指針counter:0,1,…,n;//定義計(jì)數(shù)器指針in和out初始化為1設(shè)no-op是一條空操作指令，則對(duì)于生產(chǎn)者當(dāng)counter=n時(shí)，應(yīng)執(zhí)行no-op，而對(duì)于消費(fèi)者進(jìn)程當(dāng)counter=0時(shí)應(yīng)執(zhí)行no-op

在生產(chǎn)者進(jìn)程中設(shè)一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來(lái)的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則設(shè)一個(gè)局部變量nextc，用于存放每次要消費(fèi)的產(chǎn)品2/4/202383進(jìn)程同步的基本概念producer:repeat//*生產(chǎn)者進(jìn)程…produceaniteminnextp;//生產(chǎn)一個(gè)產(chǎn)品…whilecounter=ndono-op;buffer［in］∶=nextp;//將產(chǎn)品存入緩沖區(qū)in∶=in+1modn;//修改緩沖區(qū)指針counter∶=counter+1;//修改計(jì)數(shù)器untilfalse;consumer:repeat//*消費(fèi)者進(jìn)程whilecounter=0dono-op;nextc∶=buffer［out］; out∶=(out+1)modn;counter∶=counter-1;consumetheiteminnextc;untilfalse;2/4/202384進(jìn)程同步的基本概念雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問(wèn)題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操作，消費(fèi)者對(duì)它做減1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)，?？捎孟旅娴男问矫枋錾a(chǎn)者：消費(fèi)者：register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2; ......2/4/202385假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語(yǔ)言語(yǔ)句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語(yǔ)句，則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語(yǔ)句，然后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語(yǔ)句，counter值也還是5，但是如果按下述順序執(zhí)行：register1:=counter;register1:=register1+1;register2:=counter;register2:=register2-1;counter:=register1;counter:=register2;register1:=counter;register1:=register1+1;counter:=register1;register2:=counter;register2:=register2-1;counter:=register2;(register1=5)(register1=6)(register2=5)(register2=4)(counter=6)(counter=4)counter的值應(yīng)為5，但此時(shí)得到的是4。表明此時(shí)的程序已失去再現(xiàn)性。解決此問(wèn)題的關(guān)鍵應(yīng)是將counter作為臨界資源處理2/4/202386進(jìn)程同步的基本概念臨界區(qū)（criticalsection）不論是硬件臨界資源還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對(duì)它進(jìn)行訪問(wèn)在每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼稱為臨界區(qū)(criticalsection)每個(gè)進(jìn)程進(jìn)入臨界區(qū)之前應(yīng)先對(duì)欲訪問(wèn)的臨界資源進(jìn)行檢查，看是否正在被訪問(wèn)。如果此刻該臨界資源未被訪問(wèn)，該進(jìn)程可進(jìn)入臨界區(qū)，并設(shè)置它正在被訪問(wèn)的標(biāo)志，在臨界區(qū)之前執(zhí)行的這段代碼稱為進(jìn)入?yún)^(qū)（entrysection）在臨界區(qū)之后也要加上一段代碼，用于將臨界區(qū)被訪問(wèn)的標(biāo)志恢復(fù)為未被訪問(wèn)的標(biāo)志，稱為退出區(qū)（exitsection）2/4/2023873.臨界區(qū)(criticalsection)可把一個(gè)訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下：repeat

criticalsection;remaindersection;untilfalse;entrysectionexitsection←進(jìn)入?yún)^(qū)←臨界區(qū)←退出區(qū)←剩余區(qū)2/4/202388進(jìn)程同步的基本概念同步機(jī)制應(yīng)遵循的規(guī)則空閑讓進(jìn) 當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，應(yīng)允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)忙則等待

當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，其他進(jìn)程必須等待有限等待

對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)，防止"死等"讓權(quán)等待

當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，防止"忙等"2/4/202389進(jìn)程同步進(jìn)程同步的基本概念信號(hào)量機(jī)制信號(hào)量的應(yīng)用2/4/202390信號(hào)量機(jī)制1965年，荷蘭學(xué)者Dijkstra提出的信號(hào)量（Semaphores）機(jī)制是一種有效的進(jìn)程同步工具,所以P、V分別是荷蘭語(yǔ)的test(proberen)和increment(verhogen)信號(hào)量機(jī)制已從整型信號(hào)量發(fā)展為記錄型信號(hào)量，又進(jìn)一步發(fā)展為信號(hào)量集目前，信號(hào)量機(jī)制已廣泛應(yīng)用于單處理機(jī)、多處理機(jī)以及計(jì)算機(jī)網(wǎng)絡(luò)中信號(hào)量就是OS提供的管理公有資源的有效手段信號(hào)量代表可用資源實(shí)體的數(shù)量2/4/202391信號(hào)量機(jī)制——整型信號(hào)量整型信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量，除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來(lái)訪問(wèn)。這兩個(gè)操作一直被分別稱為P、V操作。wait和signal操作可描述為：wait(S):whileS≤0dono-op S∶=S-1;signal(S):S∶=S+1;wait(S)和signal(S)是原子操作，執(zhí)行時(shí)是不可中斷的。另外，在wait操作中，對(duì)S的測(cè)試和做S∶=S-1操作時(shí)都不可中斷，信號(hào)量只能通過(guò)原語(yǔ)操作來(lái)訪問(wèn)，不能被進(jìn)程調(diào)度所打斷缺點(diǎn)：信號(hào)量S≤0時(shí)“忙等”，未遵循“讓權(quán)等待”2/4/202392信號(hào)量機(jī)制——記錄型信號(hào)量記錄型信號(hào)量采取了“讓權(quán)等待”的策略，是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。在采取了“讓權(quán)等待”的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問(wèn)同一臨界資源的情況。為此，在記錄型信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的，定義如下：typesemaphore=recordvalue:integer;L:listofprocess;end2/4/202393信號(hào)量機(jī)制——記錄型信號(hào)量相應(yīng)地，wait(S)和signal(S)操作可描述為：procedurewait(S)varS:semaphore;beginS.value:=S.value-1;//請(qǐng)求一個(gè)該類資源ifS.value＜0thenblock(S.L);//該類資源已分配完畢,調(diào)用block原語(yǔ)，進(jìn)行自我阻塞并放棄處理機(jī)、插入到信號(hào)量鏈表S.L中endproceduresignal(S)varS:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S.L);end2/4/202394信號(hào)量機(jī)制——記錄型信號(hào)量在記錄型信號(hào)量機(jī)制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號(hào)量對(duì)信號(hào)量S.value每次wait操作，S.value:=S.value-1S.value>0時(shí)，有該類資源S.value＜0時(shí)，該類資源已分配完畢，|S.value|=該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)目對(duì)信號(hào)量的每次signal操作，S.value:=S.value+1若加1后仍是S.value≤0，表示在該信號(hào)量鏈表中仍有等待該資源的進(jìn)程被阻塞，則應(yīng)調(diào)用wakeup原語(yǔ)，將S.L鏈表中的第一個(gè)等待進(jìn)程喚醒。若S.value的初值為1，表示只允許一個(gè)進(jìn)程訪問(wèn)臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量2/4/202395信號(hào)量機(jī)制——AND型信號(hào)量AND型信號(hào)量在有些任務(wù)中，一個(gè)進(jìn)程先要獲得多個(gè)共享資源后才能執(zhí)行，若進(jìn)程A和B都要訪問(wèn)共享數(shù)據(jù)D和E，設(shè)信號(hào)量Dmutex和Emutexmutex(MUTualExclusion)的初值均為1在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作，即processA: processB:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞此時(shí)，A和B處于僵持狀態(tài)，若無(wú)外力作用無(wú)法解脫，稱為“死鎖”狀態(tài)2/4/202396信號(hào)量機(jī)制——AND型信號(hào)量AND同步機(jī)制的基本思想是將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作，即Swait(Simultaneouswait)2/4/202397信號(hào)量機(jī)制——AND型信號(hào)量Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1then//每個(gè)資源都可用fori:=1tondoSi:=Si-1;//分配所有資源endforelse//否則，將進(jìn)程放到等待資源Si的隊(duì)列中placetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori:=1tondoSi=Si+1;//釋放所有資源RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor;2/4/202398信號(hào)量機(jī)制——信號(hào)量集信號(hào)量集在記錄型信號(hào)量機(jī)制中，wait(S)和signal(S)操作僅能對(duì)信號(hào)量施以加1或減1操作，意味著每次只能獲得或釋放一個(gè)單位的臨界資源，效率較低在有些情況下，當(dāng)資源數(shù)量低于某下限值時(shí)便不予分配。因而，在每次分配之前，都必須測(cè)試該資源的數(shù)量，看其是否大于等于下限值在對(duì)AND型信號(hào)量機(jī)制擴(kuò)充的基礎(chǔ)上，形成一般化的“信號(hào)量集”機(jī)制Swait(S1,t1,d1,…,Sn,tn,dn)Ssignal(S1,d1,…,Sn,dn)下限值需求值2/4/202399信號(hào)量機(jī)制——信號(hào)量集Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…andSn≥tnthenfori:=1tondoSi:=Si-di;//一次分配d個(gè)資源endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSi

withSi＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifSsignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;//釋放所有資源 RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor;2/4/2023100信號(hào)量機(jī)制——信號(hào)量集一般“信號(hào)量集”的幾種特殊情況Swait(S,d,d)。此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S，但允許它每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配Swait(S,1,1)。此時(shí)的信號(hào)量集已蛻化為一般的記錄型信號(hào)量(S＞1時(shí))或互斥信號(hào)量(S=1時(shí))Swait(S,1,0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開(kāi)關(guān)2/4/2023101進(jìn)程同步進(jìn)程同步的基本概念信號(hào)量機(jī)制信號(hào)量的應(yīng)用2/4/2023102信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥mutex作為互斥鎖使用Varmutex:semaphore:=1;beginparbeginprocess1:begin repeat wait(mutex); criticalsection signal(mutex); remainderseetion untilfalse; endprocess2:begin repeat wait(mutex); criticalsection signal(mutex); remaindersection untilfalse; endparend2/4/2023103信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥利用整型信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥時(shí)應(yīng)注意，wait(mutex)和signal(mutex)必須成對(duì)出現(xiàn)缺少wait(mutex)會(huì)導(dǎo)致系統(tǒng)混亂，不能保證對(duì)臨界資源的互斥訪問(wèn)缺少signal(mutex)將會(huì)使臨界資源永遠(yuǎn)不被釋放，從而使因等待該資源而阻塞的進(jìn)程不再被喚醒2/4/2023104信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系設(shè)有兩個(gè)并發(fā)進(jìn)程P1和P2。P1中有語(yǔ)句S1，P2中有語(yǔ)句S2，希望在執(zhí)行完S1后執(zhí)行S2為實(shí)現(xiàn)這種前趨關(guān)系，可讓進(jìn)程P1和P2共享一個(gè)公用信號(hào)量S，并賦初值為0，將signal(S)操作放在語(yǔ)句S1后面；而在S2語(yǔ)句前插入wait(S)操作進(jìn)程P1，S1;signal(S);進(jìn)程P2，wati(S);S2;由于S被初始化為0，若P2先執(zhí)行，必定阻塞，只有在進(jìn)程P1執(zhí)行完使S增為1后，P2才能執(zhí)行S2操作2/4/20231052.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系圖2-10前趨圖舉例abcdefg2/4/2023106Vara,b,c,d,e,f,g;semaphore:=0,0,0,0,0,0,0;beginparbegin beginS1;signal(a);signal(b);end; begin

wait(a);S2;signal(c);signal(d);end;

2/4/20231072.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系圖2-10前趨圖舉例abcdefg2/4/2023108Vara,b,c,d,e,f,g;semaphore:=0,0,0,0,0,0,0;beginparbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end;

2/4/20231092.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系圖2-10前趨圖舉例abcdefg2/4/2023110Vara,b,c,d,e,f,g;semaphore:=0,0,0,0,0,0,0;beginparbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end;

2/4/20231112.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系圖2-10前趨圖舉例abcdefg2/4/2023112Vara,b,c,d,e,f,g;semaphore:=0,0,0,0,0,0,0;beginparbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S5;signal(g);end;

2/4/20231132.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系圖2-10前趨圖舉例abcdefg2/4/2023114Vara,b,c,d,e,f,g;semaphore:=0,0,0,0,0,0,0;beginparbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S5;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;

2/4/2023115Vara,b,c,d,e,f,g;semaphore:=0,0,0,0,0,0,0;beginparbegin beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(c);S4;signal(f);end; beginwait(d);S5;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;parendend2/4/2023116第二章進(jìn)程管理進(jìn)程的基本概念

進(jìn)程控制

進(jìn)程同步

經(jīng)典進(jìn)程的同步問(wèn)題管程機(jī)制進(jìn)程通信線程2/4/2023117經(jīng)典進(jìn)程的同步問(wèn)題生產(chǎn)者—消費(fèi)者問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題讀者—寫(xiě)者問(wèn)題2/4/2023118生產(chǎn)者—消費(fèi)者問(wèn)題前面我們已經(jīng)對(duì)生產(chǎn)者—消費(fèi)者問(wèn)題(Theproducer-consumerproblem)做了一些描述，但未考慮進(jìn)程的互斥與同步問(wèn)題，因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者—消費(fèi)者問(wèn)題是相互合作的進(jìn)程關(guān)系的一種抽象，例如，在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者；而在輸出時(shí)，則計(jì)算進(jìn)程是生產(chǎn)者，而打印進(jìn)程是消費(fèi)者，因此，該問(wèn)題有很大的代表性及實(shí)用價(jià)值2/4/2023119生產(chǎn)者—消費(fèi)者問(wèn)題利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題

假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中，具有n個(gè)緩沖區(qū)考慮哪些是互斥資源、哪些是資源信號(hào)量？互斥資源——緩沖區(qū)、計(jì)數(shù)器，設(shè)互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用及計(jì)數(shù)器的加減操作資源信號(hào)量——緩沖池，設(shè)信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個(gè)消息2/4/2023120生產(chǎn)者—消費(fèi)者問(wèn)題Varmutex,empty,full:semaphore:=1,n,0;buffer:array［0,…,n-1］ofitem;in,out:integer∶=0,0;begin

parbeginproducer:begin//生產(chǎn)者進(jìn)程repeat…produceranitemnextp;//產(chǎn)一個(gè)產(chǎn)品…

wait(empty);//empty減1

wait(mutex);//加鎖buffer(in):=nextp;in:=(in+1)modn;//移動(dòng)生產(chǎn)指針

signal(mutex);//解鎖

signal(full);//full增1untilfalse;endconsumer:begin//消費(fèi)者進(jìn)程repeat

wait(full);

wait(mutex);nextc:=buffer(out);out:=(out+1)modn;

signal(mutex);

signal(empty);consumertheiteminnextc;untilfalse;end