第3章進(jìn)程管理課件

第3章進(jìn)程管理3.1進(jìn)程的概念3.2進(jìn)程的描述3.3進(jìn)程狀態(tài)及其轉(zhuǎn)換3.4進(jìn)程控制3.5進(jìn)程互斥3.6進(jìn)程同步3.7進(jìn)程通信3.8死鎖問題3.9線程的概念3.10線程分類與執(zhí)行本章小結(jié),習(xí)題第3章進(jìn)程管理3.1進(jìn)程的概念3.1進(jìn)程的概念1.現(xiàn)代操作系統(tǒng)的重要特點(diǎn)是: 程序的并發(fā)執(zhí)行; 系統(tǒng)所擁有的資源被共享； 用戶隨機(jī)地使用系統(tǒng)；三個(gè)特點(diǎn)互相聯(lián)系和互相依賴。它們是互相獨(dú)立的用戶如何使用有限的計(jì)算機(jī)系統(tǒng)資源的反映。2.采用什么樣的概念描述程序的執(zhí)行過程和作為資源分配的基本單位,才能反映上述特點(diǎn)?3.1進(jìn)程的概念3.1.1程序的并發(fā)執(zhí)行1.程序 程序用來描述計(jì)算機(jī)所要完成的獨(dú)立功能，并在時(shí)間上嚴(yán)格地按前后次序相繼的進(jìn)行計(jì)算機(jī)操作序列集合，是一個(gè)靜態(tài)的概念。 它體現(xiàn)了編程人員要求計(jì)算機(jī)完成所要求功能時(shí)所應(yīng)該采取的順序步驟。3.1.1程序的并發(fā)執(zhí)行2.程序的順序執(zhí)行一個(gè)程序只有經(jīng)過執(zhí)行才能得到最終結(jié)果;程序的執(zhí)行分為順序執(zhí)行和并發(fā)執(zhí)行。CPU是通過時(shí)序脈沖來控制順序執(zhí)行指令的。其執(zhí)行過程可以描述為： RepeatIR←M［pc］ pc←pc+1 〈Execute(instructioninIR)〉 UntilCPUhalt程序的順序性與計(jì)算機(jī)硬件的順序性是一致的。2.程序的順序執(zhí)行把一個(gè)具有獨(dú)立功能的程序獨(dú)占處理機(jī)直至最終結(jié)束的過程稱為程序的順序執(zhí)行。具有如下特點(diǎn)：(1)順序性程序執(zhí)行過程可看作一系列嚴(yán)格按程序規(guī)定的狀態(tài)轉(zhuǎn)移過程。(2)封閉性程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因素的影響。(3)可再現(xiàn)性順序執(zhí)行的最終結(jié)果與執(zhí)行速度無關(guān).只要輸入的初始條件相同,則無論何時(shí)重復(fù)執(zhí)行該程序都會(huì)得到相同的結(jié)果。把一個(gè)具有獨(dú)立功能的程序獨(dú)占處理機(jī)直至最終結(jié)束的過程稱為程序3.多道程序系統(tǒng)中程序執(zhí)行環(huán)境的特點(diǎn)：(1)獨(dú)立性每道程序都是邏輯上獨(dú)立的，它們之間不存在邏輯上的制約關(guān)系。即若有充分的資源保證,則每道程序都可以獨(dú)立執(zhí)行,且執(zhí)行速度與其他程序無關(guān),執(zhí)行的起止時(shí)間也是獨(dú)立的。(2)隨機(jī)性 程序和數(shù)據(jù)的輸入與執(zhí)行開始時(shí)間都是隨機(jī)的。(3)資源共享導(dǎo)致對(duì)進(jìn)程執(zhí)行速度的制約。3.多道程序系統(tǒng)中程序執(zhí)行環(huán)境的特點(diǎn)：4.程序的并發(fā)執(zhí)行(1)什么是程序的并發(fā)執(zhí)行為了增強(qiáng)計(jì)算機(jī)系統(tǒng)的處理能力和提高資源利用率所采取的一種同時(shí)操作技術(shù).可分為兩種：①多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行(宏觀上同時(shí)進(jìn)行，微觀上順序執(zhí)行)②在某道程序的幾個(gè)程序段中，包含著一部分可以同時(shí)執(zhí)行或順序顛倒執(zhí)行的代碼4.程序的并發(fā)執(zhí)行例如語句： read(a)； read(b)； c=a+b; Write(c);它們既可以同時(shí)執(zhí)行，也可顛倒次序執(zhí)行。對(duì)于這樣的語句，同時(shí)執(zhí)行不會(huì)改變順序程序所具有的邏輯性質(zhì)?？梢圆捎貌l(fā)執(zhí)行來充分利用系統(tǒng)資源以提高計(jì)算機(jī)的處理能力。例如語句： read(a)；

程序的并發(fā)執(zhí)行可總結(jié)為：一組在邏輯上互相獨(dú)立的程序或程序段在執(zhí)行過程中,其執(zhí)行時(shí)間在客觀上互相重疊,即一個(gè)程序段的執(zhí)行尚未結(jié)束,另一個(gè)程序段的執(zhí)行已經(jīng)開始的這種執(zhí)行方式?？梢詫⒉l(fā)執(zhí)行過程描述為：

S0 Cobegin P1；P2；...Pn Coend SnS0，Sn：表示并發(fā)程序段P1，…，Pn開始執(zhí)行前和并發(fā)執(zhí)行結(jié)束后的語句。P1，P2，…，Pn也可以由同一程序段中的不同語句組成。 程序的并發(fā)執(zhí)行可總結(jié)為：

程序的并發(fā)執(zhí)行不同于程序的并行執(zhí)行。程序的并行執(zhí)行是指一組程序按獨(dú)立的、異步的速度執(zhí)行。并行執(zhí)行不等于時(shí)間上的重疊。

程序的并發(fā)執(zhí)行不同于程序的并行執(zhí)行。5程序的并發(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;

5程序的并發(fā)執(zhí)行及其特征例如有兩個(gè)循環(huán)程序A和B，它們共享5程序的并發(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)程控制管理5程序的并發(fā)執(zhí)行及其特征N：n程序A：N∶=N+1;//N5程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行的特征間斷(異步)性"走走停停"，一個(gè)程序可能走到中途停下來，失去原有的時(shí)序關(guān)系；失去封閉性共享資源，受其他程序的控制邏輯的影響。如：一個(gè)程序?qū)懙酱鎯?chǔ)器中的數(shù)據(jù)可能被另一個(gè)程序修改，失去原有的不變特征。失去可再現(xiàn)性失去封閉性－>失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征5程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行的特征6程序并發(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í)行期間所需參考的所有變量的集合?！皩懠盬(Pi)為程序Pi在執(zhí)行期間所需改變的所有變量的集合。例如：S1: a:=x+y S2: b:=z+1 S3: c:=a-b S4: d:=c+16程序并發(fā)執(zhí)行的條件（1966年由Bernstein提出）6程序并發(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)={ }語句S1、S2______并發(fā)，因?yàn)開_____________________。語句S1、S3______并發(fā)，因?yàn)開_____________________。語句S2、S3______并發(fā)，因?yàn)開_____________________。語句S3、S4______并發(fā)，因?yàn)開_____________________。語句S2、S4______并發(fā)，因?yàn)開_____________________。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}≠{}6程序并發(fā)執(zhí)行的條件（1966年由Bernstein提出）7程序的并發(fā)執(zhí)行所帶來的影響好處:提高系統(tǒng)資源的利用率.弊端:必然導(dǎo)致資源共享和資源競(jìng)爭(zhēng)，改變程序的執(zhí)行速度，對(duì)程序的最終結(jié)果帶來不利的影響，且可能造成程序出現(xiàn)錯(cuò)誤。如果并發(fā)執(zhí)行的各程序段中語句或指令：

滿足Bernstein條件，則并發(fā)執(zhí)行不會(huì)對(duì)執(zhí)行結(jié)果的封閉性和可再現(xiàn)性產(chǎn)生影響。

不按照特定的規(guī)則和方法進(jìn)行資源共享和競(jìng)爭(zhēng)，則其執(zhí)行結(jié)果將失去封閉性和可再現(xiàn)性。7程序的并發(fā)執(zhí)行所帶來的影響例1：設(shè)有堆棧S，棧指針top，棧中存放內(nèi)存中相應(yīng)數(shù)據(jù)塊地址，如圖3.1(a)。

設(shè)有兩個(gè)程序段getaddr(top)和reladdr(blk)。例1：設(shè)有堆棧S，棧指針top，棧中存放內(nèi)存中相應(yīng)數(shù)據(jù)塊地址getaddr(top)：從給定的top所指棧中取出相應(yīng)的內(nèi)存數(shù)據(jù)塊地址；reladdr(blk)：將內(nèi)存數(shù)據(jù)塊地址blk放入堆棧S中。

proceduregetaddr(top) procedurereladdr(blk) begin begin localr top←top+1 r←(top) (top)←blk

top←top-1 end return(r) end

getaddr(top)：從給定的top所指棧中取出相應(yīng)的內(nèi)若getaddr和reladdr程序段進(jìn)行順序執(zhí)行：其執(zhí)行結(jié)果具有封閉性和可再現(xiàn)性。如果對(duì)這兩個(gè)程序段采用并發(fā)執(zhí)行：則在單CPU系統(tǒng)中，將有可能出現(xiàn)下述情況：若getaddr和reladdr程序段進(jìn)行順序執(zhí)行：其執(zhí)1）程序段reladdr開始執(zhí)行，當(dāng)執(zhí)行到top←top+1語句時(shí)(b)，程序段getaddr也開始執(zhí)行且搶占了處理機(jī)，從而程序段reladdr停在top←top+1處等待處理機(jī)。2）由于reladdr程序段的執(zhí)行將指針top升高了一格且未放進(jìn)適當(dāng)?shù)臄?shù)據(jù)，getaddr的執(zhí)行結(jié)果是失敗的(C)。1）程序段reladdr開始執(zhí)行，當(dāng)執(zhí)行到top←to結(jié)論1：程序的并發(fā)執(zhí)行使得其執(zhí)行結(jié)果不再具有封閉性和可再現(xiàn)性；分析：由于兩程序段共享資源堆棧S，從而使得執(zhí)行結(jié)果受執(zhí)行速度影響。一般情況下，并發(fā)執(zhí)行的各程序段如果共享軟、硬件資源，都會(huì)造成其執(zhí)行結(jié)果受執(zhí)行速度影響的局面。結(jié)論2：為了使在并發(fā)執(zhí)行時(shí)不出現(xiàn)錯(cuò)誤結(jié)果，必須采取某些措施來制約、控制各并發(fā)程序段的執(zhí)行速度。結(jié)論1：程序的并發(fā)執(zhí)行使得其執(zhí)行結(jié)果不再具有封閉性和可再現(xiàn)性為了控制和協(xié)調(diào)各程序段執(zhí)行過程中的軟、硬件資源的共享和競(jìng)爭(zhēng)，必須有一個(gè)描述各程序段執(zhí)行過程和共享資源的基本單位。程序：由于程序的順序性、靜態(tài)性及孤立性，用程序段作為描述其執(zhí)行過程和共享資源的基本單位既增加OS設(shè)計(jì)和實(shí)現(xiàn)的復(fù)雜性，也無法反映OS的并發(fā)性、用戶隨機(jī)性，以及資源共享等特征。進(jìn)程（或任務(wù)）：需要有一個(gè)能描述程序的執(zhí)行過程且能用來共享資源的基本單位。為了控制和協(xié)調(diào)各程序段執(zhí)行過程中的軟、硬件資源的共享和競(jìng)爭(zhēng)，3.1.2進(jìn)程的定義進(jìn)程的概念是60年代初期，首先在MIT的Multics系統(tǒng)和IBM的TSS/360系統(tǒng)中引用的。1)進(jìn)程是可以并行執(zhí)行的計(jì)算部分(S.E.Madnick,J.T.Donovan)2)進(jìn)程是一個(gè)獨(dú)立的可以調(diào)度的活動(dòng)E.Cohen,D.Jofferson3)進(jìn)程是一抽象實(shí)體，當(dāng)它執(zhí)行某個(gè)任務(wù)時(shí)，將要分配和釋放各種資源 （P.Denning）；4)行為的規(guī)則叫程序，程序在處理機(jī)上執(zhí)行時(shí)的活動(dòng)稱為進(jìn)程 （E.W.Dijkstra）；5)一個(gè)進(jìn)程是一系列逐一執(zhí)行的操作，而操作的確切含義則有賴于以何種詳盡程度來描述進(jìn)程;（BrinchHansen）3.1.2進(jìn)程的定義 以上進(jìn)程的定義，盡管各有側(cè)重，但在本質(zhì)上是相同的。即主要注重進(jìn)程是一個(gè)動(dòng)態(tài)的執(zhí)行過程這一概念。進(jìn)程：

一個(gè)具有獨(dú)立功能的程序?qū)δ硞€(gè)數(shù)據(jù)集在處理機(jī)上的執(zhí)行過程和分配資源的基本單位。 -程序：指一組操作序列; -數(shù)據(jù)集：是接受程序規(guī)定操作的一組存儲(chǔ)單元的內(nèi)容。并發(fā)執(zhí)行的程序在執(zhí)行過程中分配和管理資源的基本單位。 以上進(jìn)程的定義，盡管各有側(cè)重，但在本質(zhì)上是相同的。即主要進(jìn)程概念閱讀菜譜準(zhǔn)備原料烹制菜肴飯菜閱讀洗衣機(jī)手冊(cè)準(zhǔn)備衣服、洗衣粉設(shè)定參數(shù)，洗衣服干凈衣服程序輸入運(yùn)行輸出程序輸入運(yùn)行輸出分時(shí)切換洗衣進(jìn)程做飯進(jìn)程進(jìn)程概念閱讀菜譜準(zhǔn)備原料烹制菜肴飯菜閱讀洗衣機(jī)手冊(cè)準(zhǔn)備衣服、進(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ù)。進(jìn)程概念進(jìn)程的核心思想進(jìn)程是某種類型的一個(gè)活動(dòng)，它有程序、輸進(jìn)程和程序是區(qū)別和關(guān)系：(1)進(jìn)程是一個(gè)動(dòng)態(tài)概念；程序是一個(gè)靜態(tài)概念。程序是指令的有序集合，描述完成某個(gè)功能的一個(gè)具體操作過程；沒有任何執(zhí)行的含義。進(jìn)程強(qiáng)調(diào)執(zhí)行過程，它被動(dòng)態(tài)地創(chuàng)建，并被調(diào)度執(zhí)行后消亡。(2)進(jìn)程具有并發(fā)特征，而程序沒有。進(jìn)程具有并發(fā)特征的兩個(gè)方面：獨(dú)立性和異步性。即在不考慮資源共享的情況下，各進(jìn)程的執(zhí)行是獨(dú)立的，執(zhí)行速度是異步的。程序不反映執(zhí)行過程，所以不具有并發(fā)特征。進(jìn)程和程序是區(qū)別和關(guān)系：(3)進(jìn)程是競(jìng)爭(zhēng)計(jì)算機(jī)系統(tǒng)資源的基本單位，從而其并發(fā)性受到系統(tǒng)自己的制約。這里，制約就是對(duì)進(jìn)程獨(dú)立性和異步性的限制。(4)不同的進(jìn)程可以包含同一程序，只要該程序所對(duì)應(yīng)的數(shù)據(jù)集不同。(3)進(jìn)程是競(jìng)爭(zhēng)計(jì)算機(jī)系統(tǒng)資源的基本單位，從而其并發(fā)性受到作業(yè)和進(jìn)程*作業(yè):用戶需要計(jì)算機(jī)完成某項(xiàng)任務(wù)時(shí)要求計(jì)算機(jī)所作工作的集合。一個(gè)作業(yè)的完成要經(jīng)過提交、收容、執(zhí)行和完成四個(gè)階段。進(jìn)程:已提交完畢程序的執(zhí)行過程的描述，是資源分配的基本單位。作業(yè)和進(jìn)程*作業(yè)和進(jìn)程的區(qū)別1)作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。用戶向計(jì)算機(jī)提交作業(yè)后，系統(tǒng)將它放入外存的作業(yè)等待隊(duì)列中等待執(zhí)行。進(jìn)程是完成用戶任務(wù)的執(zhí)行實(shí)體，是向系統(tǒng)申請(qǐng)分配資源的基本單位。任一進(jìn)程只要被創(chuàng)建，總有相應(yīng)的部分存在于內(nèi)存中。2)作業(yè)描述用戶和OS之間的任務(wù)委托關(guān)系，進(jìn)程描述OS內(nèi)部任務(wù)的具體執(zhí)行過程。3)作業(yè)的概念主要用在批處理系統(tǒng)中,進(jìn)程的概念則用在幾乎所有的多道系統(tǒng)中。關(guān)系：一個(gè)用戶的作業(yè),由用戶提交給系統(tǒng),必須以進(jìn)程的形式具體完成。一個(gè)作業(yè)包含多個(gè)進(jìn)程,至少含一個(gè)進(jìn)程,但反過來不成立作業(yè)和進(jìn)程的區(qū)別進(jìn)程的特征動(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)建與撤消進(jìn)程的特征動(dòng)態(tài)性：進(jìn)程具有動(dòng)態(tài)的地址空間（數(shù)量和內(nèi)容），地址3.2進(jìn)程的描述從處理機(jī)的活動(dòng)角度（進(jìn)程的靜態(tài)描述）系統(tǒng)中有描述進(jìn)程存在和反映其變化的物理實(shí)體,即進(jìn)程的靜態(tài)描述。進(jìn)程的靜態(tài)描述由三部分組成：①進(jìn)程控制塊PCB、②有關(guān)程序段：描述進(jìn)程所要完成的功能。

③該程序段對(duì)其進(jìn)行操作的數(shù)據(jù)結(jié)構(gòu)集：程序在執(zhí)行時(shí)必不可少的工作區(qū)和操作對(duì)象。②③是進(jìn)程完成所需功能的物質(zhì)基礎(chǔ)。它們放在外存中,直到該進(jìn)程執(zhí)行時(shí)再調(diào)入內(nèi)存。3.2進(jìn)程的描述3.2.1進(jìn)程控制塊PCBPCB是系統(tǒng)感知進(jìn)程存在的唯一實(shí)體；PCB是進(jìn)程動(dòng)態(tài)特征的集中反映。創(chuàng)建一個(gè)進(jìn)程時(shí)，先創(chuàng)建其PCB，然后才能根據(jù)PCB中信息對(duì)進(jìn)程實(shí)施有效的管理和控制。當(dāng)一個(gè)進(jìn)程完成其功能之后，系統(tǒng)則釋放PCB，進(jìn)程也隨之消亡。一個(gè)進(jìn)程的PCB結(jié)構(gòu)全部或部分常駐內(nèi)存的。進(jìn)程的PCB所包含的基本內(nèi)容： (1)描述信息 (2)控制信息 (3)資源管理信息 (4)CPU現(xiàn)場(chǎng)保護(hù)結(jié)構(gòu)3.2.1進(jìn)程控制塊PCB(1)描述信息 ①進(jìn)程名或進(jìn)程標(biāo)識(shí)號(hào)（唯一） ②用戶名或用戶標(biāo)識(shí)號(hào) ③家族關(guān)系(2)控制信息①進(jìn)程當(dāng)前狀態(tài)：說明進(jìn)程當(dāng)前處于何種狀態(tài)。初始態(tài)、就緒態(tài)、執(zhí)行態(tài)、等待態(tài)、終止態(tài)就緒態(tài):表示該進(jìn)程準(zhǔn)備占有處理機(jī);執(zhí)行態(tài):表示該進(jìn)程占有處理機(jī);等待態(tài):表示該進(jìn)程因某種原因不能占有處理機(jī);(1)描述信息②進(jìn)程優(yōu)先級(jí) 是選取進(jìn)程占有處理機(jī)的重要依據(jù)。與它有關(guān)的PCB表項(xiàng)有： a.占有CPU時(shí)間； b.進(jìn)程優(yōu)先級(jí)偏移； c.占據(jù)內(nèi)存時(shí)間等。③程序開始地址 規(guī)定該進(jìn)程的程序從此地址開始執(zhí)行.④各種計(jì)時(shí)信息 給出進(jìn)程占有和利用資源的有關(guān)情況。⑤通信信息 用來說明該進(jìn)程在執(zhí)行過程中與別的進(jìn)程所發(fā)生的信息交換情況。②進(jìn)程優(yōu)先級(jí)(3)資源管理信息有關(guān)存儲(chǔ)器的信息、輸入輸出設(shè)備的信息、文件系統(tǒng)的信息等。

①占用內(nèi)存大小及其管理用的數(shù)據(jù)結(jié)構(gòu)指針。②對(duì)換或覆蓋用的有關(guān)信息③共享程序段大小及起始地址。④輸入輸出設(shè)備的設(shè)備號(hào)，所要傳送的數(shù)據(jù)長(zhǎng)度、緩沖區(qū)地址、緩沖區(qū)長(zhǎng)度及所用設(shè)備的有關(guān)數(shù)據(jù)結(jié)構(gòu)指⑤指向文件系統(tǒng)的指針及有關(guān)標(biāo)識(shí)等。進(jìn)程可使用這些信息對(duì)文件系統(tǒng)進(jìn)行操作。(3)資源管理信息(4)CPU現(xiàn)場(chǎng)保護(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)場(chǎng)（或稱進(jìn)程上下文）。PCB中設(shè)有專門的CPU現(xiàn)場(chǎng)保護(hù)結(jié)構(gòu)，以存儲(chǔ)退出執(zhí)行時(shí)的進(jìn)程現(xiàn)場(chǎng)數(shù)據(jù)。(4)CPU現(xiàn)場(chǎng)保護(hù)結(jié)構(gòu)3.2.2進(jìn)程上下文實(shí)際上是進(jìn)程執(zhí)行過程中順序關(guān)聯(lián)的靜態(tài)描述，是進(jìn)程執(zhí)行活動(dòng)全過程的靜態(tài)描述。是一個(gè)與進(jìn)程切換和處理機(jī)狀態(tài)發(fā)生變換有關(guān)的概念。是一個(gè)抽象的概念，它包含了每個(gè)進(jìn)程執(zhí)行過的、執(zhí)行時(shí)的以及待執(zhí)行的指令和數(shù)據(jù)，在IR、堆棧、狀態(tài)寄存器等中的內(nèi)容。已執(zhí)行過的進(jìn)程指令和數(shù)據(jù)在相關(guān)寄存器與堆棧中的內(nèi)容稱為上文。正在執(zhí)行的進(jìn)程指令和數(shù)據(jù)在相關(guān)寄存器與堆棧中的內(nèi)容稱為正文。待執(zhí)行的進(jìn)程指令和數(shù)據(jù)在相關(guān)寄存器與堆棧中的內(nèi)容稱為下文。3.2.2進(jìn)程上下文在不發(fā)生進(jìn)程調(diào)度時(shí)，進(jìn)程上下文的改變是在同一進(jìn)程內(nèi)進(jìn)行的。同一進(jìn)程的上下文結(jié)構(gòu)包括:計(jì)算機(jī)系統(tǒng)中與執(zhí)行該進(jìn)程有關(guān)的各種寄存器的值程序段在經(jīng)過編譯之后形成的機(jī)器指令代碼集（正文段）數(shù)據(jù)集及各種堆棧值與PCB結(jié)構(gòu)在不發(fā)生進(jìn)程調(diào)度時(shí)，進(jìn)程上下文的改變是在同一進(jìn)程內(nèi)進(jìn)行的。UNIXSystemⅤ中，進(jìn)程上下文由以下3部分組成：用戶級(jí)上下文：由進(jìn)程的用戶程序段部分編譯而成的用戶正文段、用戶數(shù)據(jù)、用戶棧等組成。寄存器上下文：由PC、PS、棧指針和通用寄存器的值組成。進(jìn)程的系統(tǒng)級(jí)上下文：分為靜態(tài)部分、動(dòng)態(tài)部分。靜態(tài)部分:PCB結(jié)構(gòu)將進(jìn)程虛地址空間映射到物理空間用的有關(guān)表格核心棧(用來裝載進(jìn)程中所使用系統(tǒng)調(diào)用的調(diào)用序列)UNIXSystemⅤ中，進(jìn)程上下文由以下3部分組成：寄系統(tǒng)級(jí)上下文的動(dòng)態(tài)部分是與寄存器上下文相關(guān)聯(lián)的。進(jìn)程上下文的層次概念也主要體現(xiàn)在動(dòng)態(tài)部分中，即系統(tǒng)級(jí)上下文的動(dòng)態(tài)部分可看成是一些數(shù)量變化的層次組成。其變化規(guī)則滿足先進(jìn)后出的堆棧方式，每個(gè)上下文層次在棧中各占一項(xiàng)。動(dòng)態(tài)部分是指在進(jìn)入和退出不同的上下文層次時(shí)，系統(tǒng)為各層上下文中相關(guān)聯(lián)的寄存器值所保存和恢復(fù)的記錄。系統(tǒng)級(jí)上下文的動(dòng)態(tài)部分是與寄存器上下文相關(guān)聯(lián)的。動(dòng)態(tài)部分是指3.2.3進(jìn)程上下文切換進(jìn)程上下文的切換發(fā)生在不同的進(jìn)程之間而不是同一個(gè)進(jìn)程內(nèi)。進(jìn)程上下文的切換過程包含3個(gè)部分,涉及到3個(gè)進(jìn)程。第1部分：保存被切換進(jìn)程的上下文部分到有關(guān)存儲(chǔ)區(qū)。第2部分：OS進(jìn)程中有關(guān)調(diào)度和資源分配程序執(zhí)行，并選取新的進(jìn)程。第3部分：將被選中進(jìn)程的原來被保存的正文部分從有關(guān)存儲(chǔ)區(qū)中取出，并送至有關(guān)寄存器與堆棧中，激活被選中進(jìn)程執(zhí)行。進(jìn)程上下文的切換過程：圖P463.2.3進(jìn)程上下文切換進(jìn)程上下文的切換過程涉及到誰來保護(hù)和獲取進(jìn)程的正文問題。也就是如何使得寄存器和堆棧等中的數(shù)據(jù)流入流出PCB的存儲(chǔ)區(qū)。進(jìn)程上下文的切換過程涉及到了系統(tǒng)調(diào)度和分配程序,耗費(fèi)CPU時(shí)間。多組寄存器技術(shù)：為了提高效率,進(jìn)程切換時(shí)進(jìn)程上下文不保存到存儲(chǔ)器區(qū),設(shè)置多組寄存器,直接切換到相應(yīng)的寄存器.進(jìn)程上下文的切換過程涉及到誰來保護(hù)和獲取進(jìn)程的正文問題。也就3.2.4進(jìn)程空間與大小任一進(jìn)程，都有一個(gè)自己的地址空間，稱為進(jìn)程空間。進(jìn)程空間的大小只與處理機(jī)的位數(shù)有關(guān)。(例如:16位機(jī)2的16次方(64K),32位機(jī)2的32次方單元(4G))程序的執(zhí)行都在進(jìn)程空間內(nèi)進(jìn)行。 用戶程序、進(jìn)程的各種控制表格等都按一定的結(jié)構(gòu)排列在進(jìn)程空間中。有些系統(tǒng)中，進(jìn)程空間還被劃分為：用戶空間、系統(tǒng)空間；用戶程序在用戶空間內(nèi)執(zhí)行；OS內(nèi)核程序則在進(jìn)程的系統(tǒng)空間內(nèi)執(zhí)行。系統(tǒng)通過程序狀態(tài)寄存器等設(shè)置不同的執(zhí)行模式，即用戶模式和系統(tǒng)模式,把用戶執(zhí)行模式和系統(tǒng)執(zhí)行模式分別稱為用戶態(tài)和系統(tǒng)態(tài)。3.2.4進(jìn)程空間與大小 圖3.4進(jìn)程空間第3章進(jìn)程管理課件3.3進(jìn)程狀態(tài)及其轉(zhuǎn)換3.3.1進(jìn)程狀態(tài)一個(gè)進(jìn)程的生命期可以劃分為一組狀態(tài)，這些狀態(tài)刻劃了整個(gè)進(jìn)程。系統(tǒng)根據(jù)PCB結(jié)構(gòu)中的狀態(tài)值控制進(jìn)程。在進(jìn)程的生命期內(nèi)，一個(gè)進(jìn)程至少具有5種基本狀態(tài)：初始態(tài)、就緒狀態(tài)、執(zhí)行狀態(tài)、等待狀態(tài)、終止態(tài)。3.3進(jìn)程狀態(tài)及其轉(zhuǎn)換1、初始態(tài)：進(jìn)程剛被創(chuàng)建時(shí)，由于其它進(jìn)程正占有處理機(jī)得不到執(zhí)行，處于初始態(tài)。初始終止2、終止態(tài)：

進(jìn)程在執(zhí)行結(jié)束后，將退出執(zhí)行而被終止，這時(shí)進(jìn)程處于終止態(tài)。1、初始態(tài)：初始終止2、終止態(tài)：3、就緒狀態(tài)：表示該進(jìn)程準(zhǔn)備占有處理機(jī);此時(shí)進(jìn)程已經(jīng)得到除CPU外的所有資源，只要由調(diào)度得到處理機(jī)，便可立即投入執(zhí)行。內(nèi)存就緒狀態(tài)： 處于這種狀態(tài)的進(jìn)程在得到處理機(jī)后才能立即投入執(zhí)行。外存就緒狀態(tài)： 處于這種狀態(tài)的進(jìn)程只有先成為內(nèi)存就緒狀態(tài)后，才可能被調(diào)度執(zhí)行。3、就緒狀態(tài)：表示該進(jìn)程準(zhǔn)備占有處理機(jī);4、執(zhí)行狀態(tài)：表示該進(jìn)程占有處理機(jī);單CPU系統(tǒng)中任一時(shí)刻處于執(zhí)行狀態(tài)的進(jìn)程只能有一個(gè)。只有處于就緒狀態(tài)的進(jìn)程經(jīng)調(diào)度選中之后才可進(jìn)入執(zhí)行狀態(tài)。又分為用戶執(zhí)行狀態(tài)和系統(tǒng)執(zhí)行狀態(tài)；用戶執(zhí)行狀態(tài)： 進(jìn)程的用戶程序段在執(zhí)行時(shí)該進(jìn)程處于用戶狀態(tài)。系統(tǒng)執(zhí)行狀態(tài)： 進(jìn)程的系統(tǒng)程序段在執(zhí)行時(shí)該進(jìn)程處于系統(tǒng)狀態(tài)。4、執(zhí)行狀態(tài)：表示該進(jìn)程占有處理機(jī);5、等待狀態(tài)：表示該進(jìn)程因某種原因不能占有處理機(jī);進(jìn)程因等待某個(gè)事件發(fā)生而放棄處理機(jī)進(jìn)入等待狀態(tài)。根據(jù)等待事件的種類而進(jìn)一步劃分為不同的子狀態(tài)，如內(nèi)存等待、設(shè)備等待、文件等待和數(shù)據(jù)等待等。5、等待狀態(tài)：表示該進(jìn)程因某種原因不能占有處理機(jī);3.3.2進(jìn)程狀態(tài)轉(zhuǎn)換進(jìn)程的狀態(tài)隨著進(jìn)程的執(zhí)行和外界條件變化和轉(zhuǎn)換。進(jìn)程的狀態(tài)轉(zhuǎn)換是一個(gè)非常復(fù)雜的過程。從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換除了要使用不同的控制過程，有時(shí)還要借助于硬件觸發(fā)器才能完成。3.3.2進(jìn)程狀態(tài)轉(zhuǎn)換圖3.5進(jìn)程狀態(tài)轉(zhuǎn)換初始終止初始終止3.4進(jìn)程控制進(jìn)程控制就是系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。原語可分為兩類：1.機(jī)器指令級(jí)的原語，特點(diǎn)是執(zhí)行期間不允許中斷，如物理學(xué)中的原子，在OS中它是一個(gè)不可分割的基本單位。功能級(jí)的原語，特點(diǎn)是作為原語的程序段不允許并發(fā)執(zhí)行。這兩類原語都在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個(gè)系統(tǒng)管理所需要的功能和被高層軟件所調(diào)用。3.4進(jìn)程控制系統(tǒng)在創(chuàng)建、撤消一個(gè)進(jìn)程以及要改變進(jìn)程的狀態(tài)時(shí)，都要調(diào)用相應(yīng)的程序段來完成這些功能。在OS中，通常把進(jìn)程控制用的程序段做成原語。用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。系統(tǒng)在創(chuàng)建、撤消一個(gè)進(jìn)程以及要改變進(jìn)程的狀態(tài)時(shí)，都要調(diào)用相應(yīng)3.4.1進(jìn)程創(chuàng)建與撤消進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建方式有2種:由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建。 批處理系統(tǒng)中，由OS的作業(yè)調(diào)度程序?yàn)橛脩糇鳂I(yè)創(chuàng)建(2)由父進(jìn)程創(chuàng)建。 例如在層次結(jié)構(gòu)的系統(tǒng)中，父進(jìn)程創(chuàng)建子進(jìn)程。由系統(tǒng)統(tǒng)一創(chuàng)建的進(jìn)程之間的關(guān)系是平等的，它們之間不存在資源繼承關(guān)系。在父進(jìn)程創(chuàng)建的進(jìn)程之間則存在隸屬關(guān)系，且互相構(gòu)成樹型結(jié)構(gòu)的家族關(guān)系。屬于某個(gè)家族的一個(gè)進(jìn)程可以繼承其父進(jìn)程所擁有的資源。無論是哪一種方式創(chuàng)建進(jìn)程，在系統(tǒng)生成時(shí)，都必須由OS創(chuàng)建一部分系統(tǒng)進(jìn)程，由系統(tǒng)進(jìn)程承擔(dān)資源分配和管理工作。無論是哪一種方式創(chuàng)建進(jìn)程，都必須調(diào)用創(chuàng)建原語來實(shí)現(xiàn)。3.4.1進(jìn)程創(chuàng)建與撤消圖3.6創(chuàng)建原語流圖創(chuàng)建原語掃描系統(tǒng)的PCB鏈表，在找到一定PCB表之后，填入調(diào)用者提供的有關(guān)參數(shù)，最后形成代表進(jìn)程的PCB結(jié)構(gòu)。參數(shù)：進(jìn)程名、進(jìn)程優(yōu)先級(jí)Ｐ0、進(jìn)程正文段起始地址ｄ0、資源清單Ｒ0等。圖3.6創(chuàng)建原語流圖創(chuàng)建原語掃描系統(tǒng)的PCB鏈表，在找到一2.進(jìn)程撤消以下幾種情況導(dǎo)致進(jìn)程被撤消：(1)該進(jìn)程已完成所要求的功能而正常終止。(2)由于某種錯(cuò)誤導(dǎo)致非正常終止。(3)祖先進(jìn)程要求撤消某個(gè)子進(jìn)程。進(jìn)程被撤消時(shí)，進(jìn)程都必須釋放它所占用的各種資源和PCB結(jié)構(gòu)本身。當(dāng)一個(gè)祖先進(jìn)程撤消某個(gè)子進(jìn)程時(shí)，還需審查該子進(jìn)程是否還有自己的子孫進(jìn)程，若有的話，還需撤消其子孫進(jìn)程的PCB結(jié)構(gòu)和釋放它們所占有的資源。2.進(jìn)程撤消撤消原語先檢查PCB進(jìn)程鏈或進(jìn)程家族，尋找所要撤消的進(jìn)程是否存在。若找到了，則釋放該進(jìn)程所占有的資源之后，把對(duì)應(yīng)的PCB結(jié)構(gòu)從進(jìn)程鏈或進(jìn)程家族中摘下并返回給PCB空隊(duì)列。若被撤消的進(jìn)程有自己的子進(jìn)程，則先撤消其子進(jìn)程的PCB結(jié)構(gòu)并釋放子進(jìn)程所占用的資源之后，再撤消當(dāng)前進(jìn)程的PCB結(jié)構(gòu)和釋放其資源。撤消原語圖3.7撤消原語流圖圖3.7撤消原語流圖3.4.2進(jìn)程的阻塞與喚醒阻塞原語：實(shí)現(xiàn)進(jìn)程的執(zhí)行態(tài)等待態(tài)的轉(zhuǎn)換。阻塞原語在一個(gè)進(jìn)程期待某一事件發(fā)生，但發(fā)生條件尚不具備時(shí)，被該進(jìn)程自己調(diào)用來阻塞自己。喚醒原語：實(shí)現(xiàn)進(jìn)程的等待態(tài)就緒態(tài)的轉(zhuǎn)換。當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，等待該事件的所有進(jìn)程都將被喚醒。喚醒一個(gè)進(jìn)程有兩種方法：1.由系統(tǒng)進(jìn)程喚醒。2.由事件發(fā)生進(jìn)程喚醒。3.4.2進(jìn)程的阻塞與喚醒圖3.8阻塞原語圖阻塞原語先中斷處理機(jī)和保存該進(jìn)程的CPU現(xiàn)場(chǎng)。將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列中；轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。圖3.8阻塞原語圖阻塞原語當(dāng)由系統(tǒng)進(jìn)程喚醒等待進(jìn)程時(shí)，系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進(jìn)程。從而使得該進(jìn)程因等待事件已發(fā)生而進(jìn)入就緒隊(duì)列。由事件發(fā)生進(jìn)程喚醒時(shí)，事件發(fā)生進(jìn)程和被喚醒進(jìn)程之間是合作關(guān)系。喚醒原語既可被系統(tǒng)進(jìn)程調(diào)用，也可被事件發(fā)生進(jìn)程調(diào)用。稱調(diào)用喚醒原語的進(jìn)程為喚醒進(jìn)程。當(dāng)由系統(tǒng)進(jìn)程喚醒等待進(jìn)程時(shí)，系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生并將“圖3.9喚醒原語喚醒原語先將被喚醒進(jìn)程從相應(yīng)的等待隊(duì)列中摘下，將被喚醒進(jìn)程置為就緒狀態(tài)之后，送入就緒隊(duì)列。喚醒原語既可以返回原調(diào)用程序，也可以轉(zhuǎn)向進(jìn)程調(diào)度，以便讓調(diào)度程序有機(jī)會(huì)選擇一個(gè)合適的進(jìn)程執(zhí)行。圖3.9喚醒原語喚醒原語3.5 進(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無法寫入而阻塞，又稱為"同步"3.5 進(jìn)程互斥兩種形式的制約關(guān)系3.5 進(jìn)程互斥3.5.1 資源共享所引起的制約例1:在描述一個(gè)程序或算法時(shí)，總認(rèn)為存在一個(gè)偽處理機(jī),可以按程序或算法所規(guī)定的步驟來執(zhí)行該程序或算法。在實(shí)際的系統(tǒng)，一般在程序中所描述的一條語句是由多條指令構(gòu)成的。例如，各種程序中經(jīng)常出現(xiàn)的賦值語句： X=X+1；在用匯編語言書寫時(shí)，就變成：

LOAD A，X ADDI A，1 STORE A，X這3條指令的執(zhí)行期間，有可能發(fā)生中斷或調(diào)度，從而使與當(dāng)前進(jìn)程無關(guān)的程序得以執(zhí)行。為了保證程序執(zhí)行最終結(jié)果的正確性，必須對(duì)并發(fā)執(zhí)行的各進(jìn)程進(jìn)行制約，以控制它們的執(zhí)行速度和對(duì)資源的競(jìng)爭(zhēng)。3.5 進(jìn)程互斥示例2共享變量的修改沖突！！示例2共享變量的修改沖突！！例3:設(shè)有兩個(gè)計(jì)算進(jìn)程ＰA，ＰB共享內(nèi)存ＭS。其中ＭS分為三個(gè)領(lǐng)域，即系統(tǒng)區(qū)、進(jìn)程工作區(qū)和數(shù)據(jù)區(qū)。這里數(shù)據(jù)區(qū)被劃分大小相等的塊，每個(gè)塊中既可能放有數(shù)據(jù)，也有可能未放有數(shù)據(jù)。系統(tǒng)區(qū)主要是堆棧Ｓ，其中存放那些空數(shù)據(jù)塊的地址。當(dāng)進(jìn)程ＰA或ＰB要求空數(shù)據(jù)塊時(shí)，從堆棧最頂部（top指針?biāo)傅奈恢茫┤〕鏊钄?shù)據(jù)塊的地址。當(dāng)進(jìn)程ＰA或ＰB釋放數(shù)據(jù)塊時(shí)，則把所釋放數(shù)據(jù)塊的地址放入堆棧頂部。getspace為取空數(shù)據(jù)塊過程，release(ad)為釋放數(shù)據(jù)塊過程。ad為待釋放數(shù)據(jù)塊的地址。如果堆棧Ｓ非空的話，進(jìn)程ＰA或ＰB是可以用任意的順序釋放和獲取數(shù)據(jù)塊的。例3:設(shè)有兩個(gè)計(jì)算進(jìn)程ＰA，ＰB共享內(nèi)存ＭS。其中ＭS分為

getspace: begin local g g←stack［top］ top←top-1 end

release(ad): begin top←top+1 stack［top］←ad end設(shè)時(shí)刻t0時(shí)，top=h0，則getspace和release(ad)可按以下順序執(zhí)行：t0：top←top+1 ;top=h0+1;

release(ad)的第一句執(zhí)t1：g←stack[top];g=stack[h0+1];getspace執(zhí)行t2：top←top-1 ;top=h0；getspace執(zhí)行t3：stack[top]←ad;stack[h0]←ad;release(ad)執(zhí)行 getspace: begin local g其結(jié)果是:調(diào)用getspace的進(jìn)程取到的是h0+1中的一個(gè)未定義值;調(diào)用release(ad)的進(jìn)程把所釋放的空塊地址ad重復(fù)放入了h0中。怎樣保證上述執(zhí)行結(jié)果的正確性呢？如果把getspace和release(ad)抽象為兩個(gè)各以一個(gè)動(dòng)作完成的順序執(zhí)行單位，那么執(zhí)行結(jié)果的正確性是可以保證的。其結(jié)果是:主要任務(wù)使并發(fā)執(zhí)行的諸進(jìn)程之間能有效的共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。主要任務(wù)使并發(fā)執(zhí)行的諸進(jìn)程之間能有效的共享資源和相互合作，從1、臨界區(qū)（criticalregion）把不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)（criticalregion）。臨界區(qū)是由屬于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的。臨界區(qū)也被稱為訪問公用數(shù)據(jù)的那段程序。一次僅允許一個(gè)進(jìn)程使用的資源為臨界資源。在每個(gè)進(jìn)程中，用來訪問臨界資源的那段程序稱為臨界區(qū)。1、臨界區(qū)（criticalregion）2、間接制約把那些不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的集合,把這些集合稱為類(class),對(duì)類給定一個(gè)唯一的標(biāo)識(shí)名; 上例中以公用數(shù)據(jù)棧Ｓ劃分的臨界區(qū)集合是{getspace,release}。描述臨界區(qū)： when〈類名〉do〈臨界區(qū)〉od2、間接制約 設(shè)類{getspace，release}的類名為sp，則getspace和release(ad)可重新描述為：getspace:

whenspdogetspace←stack[top] top←top-1od release(ad): whenspdotop←top+1 stack[top]←adod 設(shè)類{getspace，release}的類名為sp， 由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對(duì)并發(fā)進(jìn)程執(zhí)行速度的間接制約，簡(jiǎn)稱間接制約。間接制約主要指各并發(fā)進(jìn)程的速度受公有資源制約,而不是進(jìn)程間直接制約的意思!受制約的類中各進(jìn)程在執(zhí)行順序上是任意的! 由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉進(jìn)程之間的關(guān)系：間接制約（進(jìn)程互斥）: 各個(gè)進(jìn)程彼此不知道對(duì)方的存在，邏輯上沒有關(guān)系，由于競(jìng)爭(zhēng)同一資源所引起的制約；直接制約（進(jìn)程同步）:

各個(gè)進(jìn)程彼此不知道對(duì)方的名字，通過對(duì)某些對(duì)象的共同存取來協(xié)同完成一項(xiàng)任務(wù)。通信：

各個(gè)進(jìn)程通過名字彼此之間直接進(jìn)行通信，交換信息，合作完成一項(xiàng)任務(wù)。進(jìn)程之間的關(guān)系：3.什么是互斥一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不允許交叉執(zhí)行的單位執(zhí)行。也就是說，不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)稱為互斥。一組并發(fā)進(jìn)程互斥執(zhí)行時(shí)必須滿足如下準(zhǔn)則：不能假設(shè)各并發(fā)進(jìn)程的相對(duì)執(zhí)行速度。 各并發(fā)進(jìn)程享有平等的、獨(dú)立的競(jìng)爭(zhēng)公有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任一指令結(jié)束時(shí)，其他并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)。3.什么是互斥(2)并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止其他進(jìn)程進(jìn)入臨界區(qū)。(3)并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入。(4)并發(fā)進(jìn)程中的某個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。準(zhǔn)則(1)，(2)，(3)是保證各并發(fā)進(jìn)程享有平等的、獨(dú)立的競(jìng)爭(zhēng)和使用公有資源的權(quán)利，且保證每一時(shí)刻至多只有一個(gè)進(jìn)程在臨界區(qū)。準(zhǔn)則(4)則是并發(fā)進(jìn)程不發(fā)生死鎖的重要保證。(2)并發(fā)進(jìn)程中的某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止其他進(jìn)程進(jìn)3.5.2互斥的加鎖實(shí)現(xiàn)方法：對(duì)臨界區(qū)加鎖實(shí)現(xiàn)互斥當(dāng)某個(gè)進(jìn)程進(jìn)入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時(shí)為止。并發(fā)進(jìn)程在申請(qǐng)進(jìn)入臨界區(qū)時(shí)，首先測(cè)試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進(jìn)程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)。3.5.2互斥的加鎖實(shí)現(xiàn)設(shè):臨界區(qū)的類名為Ｓ；鎖定位key[Ｓ]表示該鎖定位屬于類名為Ｓ的臨界區(qū)。加鎖后的臨界區(qū)程序描述如下： lock(key［Ｓ］) 〈臨界區(qū)〉 unlock(key［Ｓ］)Key[S]=1：表示類名為Ｓ的臨界區(qū)可用；key[S]=0：表示類名為Ｓ的臨界區(qū)不可用；unlock(key[Ｓ])的實(shí)現(xiàn)：key[S]←1lock(key[S])的實(shí)現(xiàn)：key[S]=0，不允許任何進(jìn)程進(jìn)入臨界區(qū)。key[S]=1時(shí)，僅允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。設(shè):臨界區(qū)的類名為Ｓ；鎖定位key[Ｓ]表示該鎖定位屬于

一種方法是： lock(x)=beginlocalv repeat v←x untilv=1 x←0 end該方法不能保證并發(fā)進(jìn)程互斥執(zhí)行所要求的準(zhǔn)則(3)((3)并發(fā)進(jìn)程中的若干個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入)。當(dāng)同時(shí)有幾個(gè)進(jìn)程調(diào)用lock(key[S])時(shí)，在x←0語句執(zhí)行之前，可能已有兩個(gè)以上的多個(gè)進(jìn)程由于key[S]=1而進(jìn)入臨界區(qū)。解決方法:有些機(jī)器在硬件中設(shè)置“測(cè)試與設(shè)置”指令，來保證整個(gè)代碼執(zhí)行的不可分離性。?。≡谙到y(tǒng)實(shí)現(xiàn)時(shí)，鎖定位key[S]總是設(shè)置在公有資源所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的。 一種方法是：3.5.3信號(hào)量和P,V原語1、信號(hào)量1965年，荷蘭學(xué)者Dijkstra提出的信號(hào)量（Semaphores）機(jī)制是一種有效的進(jìn)程同步互斥工具,所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)信號(hào)是鐵路交通管理中的一種常用設(shè)備，交通管理人員利用信號(hào)顏色的變化來實(shí)現(xiàn)交通管理。信號(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ù)量3.5.3信號(hào)量和P,V原語1、信號(hào)量加鎖法的弊端：1.循環(huán)測(cè)試鎖定位將損耗較多的CPU計(jì)算時(shí)間。2.使用加鎖法實(shí)現(xiàn)進(jìn)程間互斥時(shí)，將導(dǎo)致在某些情況下出現(xiàn)不公平現(xiàn)象。 一個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠進(jìn)程自己調(diào)用lock過程去測(cè)試相應(yīng)的鎖定位判斷。沒有獲得執(zhí)行機(jī)會(huì)的進(jìn)程當(dāng)然無法判斷，從而出現(xiàn)不公平現(xiàn)象。加鎖法的弊端： PA PBA：lock(key[Ｓ]) B：lock(key[Ｓ]) 〈Ｓ〉＜Ｓ＞ unlock(key[Ｓ]) unlock(key[Ｓ]) GotoA GotoB

設(shè)ＰA已通過lock(key[S])而進(jìn)入臨界區(qū)。在PA執(zhí)行unlock(key[S])之前，key[S]=0且PB沒有進(jìn)入臨界區(qū)的機(jī)會(huì)。當(dāng)PA執(zhí)行完unlock(key[S])之后,由于緊接著是一轉(zhuǎn)向語句,PA將又立即去執(zhí)行l(wèi)ock(key[S])此時(shí)，unlock(key[S])已將key[S]的值置為1，即開鎖狀態(tài)，從而PA又可進(jìn)入臨界區(qū)Ｓ。只有在PA執(zhí)行完unlock(key[S])過程之后、執(zhí)行GotoA語句之前的瞬間發(fā)生進(jìn)程調(diào)度，使PA把處理機(jī)轉(zhuǎn)讓給進(jìn)程PB，PB才有可能得到執(zhí)行。這種可能性是非常小的。PB將處于永久饑餓狀態(tài)。 PA PB例2：教室：人人都可借用、且不規(guī)定使用時(shí)間。某個(gè)學(xué)生想使用該教室時(shí)，他必須先申請(qǐng)獲得使用該教室的權(quán)利；然后再到教室看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復(fù)將持續(xù)到他進(jìn)門后為止。一種最直觀的辦法：設(shè)置一個(gè)教室管理員。如果有學(xué)生申請(qǐng)使用教室而未能如愿時(shí)，教室管理員記下他的名字，并等到教室門一打開則通知該學(xué)生進(jìn)入。這樣，既減少了學(xué)生多次來去教室檢查門是否被打開的時(shí)間，又減少了因?yàn)閷W(xué)生自發(fā)地檢查造成的不公平現(xiàn)象。例2：教室：人人都可借用、且不規(guī)定使用時(shí)間。某個(gè)學(xué)生想使用該解決加鎖法帶來的問題的方法：在OS中，這個(gè)管理員就是信號(hào)量。信號(hào)量管理相應(yīng)臨界區(qū)的公有資源，代表可用資源實(shí)體。在OS中，信號(hào)量sem是一整數(shù)。sem≥0：代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)；Sem＜0：表示正在等待使用該資源的進(jìn)程數(shù)。用于互斥的信號(hào)量sem的初值應(yīng)該大于零；建立一個(gè)信號(hào)量必須：說明所建信號(hào)量所代表的意義；賦初值以及建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)以便指向那些等待使用該臨界區(qū)的進(jìn)程。解決加鎖法帶來的問題的方法：2.Ｐ，Ｖ原語信號(hào)量的數(shù)值僅能由Ｐ，Ｖ原語操作改變；采用Ｐ,Ｖ原語,可以把類名為Ｓ的臨界區(qū)描述為WhenＳdoＰ(sem)臨界區(qū)Ｖ(sem)odSem:與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號(hào)量一次Ｐ原語操作：使得信號(hào)量sem減1；一次Ｖ原語操作：將使得信號(hào)量sem加1；2.Ｐ，Ｖ原語當(dāng)某個(gè)進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時(shí)，其他進(jìn)程如果執(zhí)行了Ｐ原語操作：該進(jìn)程在等待隊(duì)列中等待有其他進(jìn)程做Ｖ原語操作釋放資源后，進(jìn)入臨界區(qū)，這時(shí)，Ｐ原語的執(zhí)行才算真正結(jié)束。當(dāng)有好幾個(gè)進(jìn)程執(zhí)行Ｐ原語未通過而進(jìn)入等待狀態(tài)之后，如有某進(jìn)程作了Ｖ原語操作： 等待進(jìn)程中的一個(gè)可以進(jìn)入臨界區(qū)，但其他進(jìn)程必須等待。當(dāng)某個(gè)進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時(shí)，其他進(jìn)程如果執(zhí)行了Ｐ原語操作：Ｐ原語操作的主要?jiǎng)幼魇牵?1)sem減1；(2)若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；(3)若sem減1后小于零，則該進(jìn)程被阻塞后進(jìn)入該信號(hào)相對(duì)應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。Ｐ原語操作的主要?jiǎng)幼魇牵海衷Z的操作主要?jiǎng)幼魇牵?1)sem加1；(2)若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3)若相加結(jié)果小于或等于零，則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。Ｖ原語的操作主要?jiǎng)幼魇牵簣D3.11Ｐ原語操作功能 圖3.12Ｖ原語操作功能第3章進(jìn)程管理課件Ｐ，Ｖ操作都必須以原語實(shí)現(xiàn)，且在Ｐ，Ｖ原語執(zhí)行期間不允許中斷發(fā)生。實(shí)現(xiàn)方法：一種使用加鎖法的Ｐ，Ｖ原語的軟件實(shí)現(xiàn)方法：Ｐ，Ｖ操作都必須以原語實(shí)現(xiàn)，且在Ｐ，Ｖ原語執(zhí)行期間不允許中斷Ｐ（sem）： begin 封鎖中斷； lock(lockbit) val［sem］=val［sem］-1 ifval［sem］<0 保護(hù)當(dāng)前進(jìn)程CPU現(xiàn)場(chǎng) 當(dāng)前進(jìn)程狀態(tài)置為″等待″

將當(dāng)前進(jìn)程插入信號(hào)sem等待隊(duì)列 轉(zhuǎn)進(jìn)程調(diào)度

fi unlock(lockbit)；開放中斷 endＰ（sem）：Ｖ（sem）： begin 封鎖中斷； lock(lockbit) va［sem］=val［sem］+1 ifval［sem］≤0 localk

從sem等待隊(duì)列中選取一等待進(jìn)程，將其指針置入k中 將k插入就緒隊(duì)列 進(jìn)程狀態(tài)置“就緒” fi unlock(lockbit)；開放中斷endＶ（sem）：3.5.4用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程互斥設(shè)信號(hào)量sem是用于互斥的信號(hào)量;sem初值為1:表示沒有并發(fā)進(jìn)程使用該 臨界區(qū)。只要把臨界區(qū)置于Ｐ(sem)和Ｖ(sem)之間，即可實(shí)現(xiàn)進(jìn)程間的互斥。3.5.4用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程互斥當(dāng)一個(gè)進(jìn)程想要進(jìn)入臨界區(qū)時(shí)，它必須先執(zhí)行Ｐ操作以將信號(hào)量sem減1。信號(hào)量初始值為1，任一進(jìn)程在執(zhí)行Ｐ操作之后將sem的值變?yōu)?，表示該進(jìn)程可以進(jìn)入臨界區(qū)。在一個(gè)進(jìn)程完成對(duì)臨界區(qū)的操作之后，它必須執(zhí)行Ｖ操作以釋放它所占用的臨界區(qū)。在該進(jìn)程未執(zhí)行Ｖ操作之前如有另一進(jìn)程想進(jìn)入臨界區(qū)的話，它也應(yīng)先執(zhí)行Ｐ，從而使sem的值變?yōu)?1，第二個(gè)進(jìn)程將被阻塞。直到第一個(gè)進(jìn)程執(zhí)行Ｖ操作之后，sem的值變?yōu)?，從而可喚醒第二個(gè)進(jìn)程進(jìn)入就緒隊(duì)列，經(jīng)調(diào)度后再進(jìn)入臨界區(qū)。在第二個(gè)進(jìn)程執(zhí)行完Ｖ操作之后，如果沒有其他進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)的話，則sem又恢復(fù)到初始值。當(dāng)一個(gè)進(jìn)程想要進(jìn)入臨界區(qū)時(shí)，它必須先執(zhí)行Ｐ操作以將信號(hào)量se用信號(hào)量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述：1)設(shè)sem為互斥信號(hào)量，取值范圍為(1,0,-1)。sem=1：表示進(jìn)程PA和PB都未進(jìn)入類名為Ｓ的臨界區(qū)；sem=0：表示進(jìn)程PA或PB已進(jìn)入類名為Ｓ的臨界區(qū)；sem=-1：表示進(jìn)程PA和PB中，一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一個(gè)進(jìn)程等待進(jìn)入臨界區(qū)。用信號(hào)量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述：2)描述： PA： Ｐ(sem) 〈Ｓ〉 Ｖ(sem)： ： ： PB： Ｐ(sem) 〈Ｓ〉 Ｖ(sem)∷ ： ：2)描述：應(yīng)用題：獨(dú)木橋問題。某條河上只有一座獨(dú)木橋，以便行人過河?，F(xiàn)在河的兩邊都有人要過橋，按照下面的規(guī)則過橋。為了保證過橋安全，請(qǐng)用P、V操作分別實(shí)現(xiàn)正確的管理。

過橋的規(guī)則是：每次只有一個(gè)人通過橋。process(E-W)i:begin P(mutex); 過橋； V(mutex);

endVarmutex=1:semaphore;process(W-E)j:begin P(mutex); 過橋； V(mutex);

end應(yīng)用題：process(E-W)i:Varmutex=3.6進(jìn)程同步3.6.1同步的概念各進(jìn)程之間需要相互合作以完成某項(xiàng)工作，產(chǎn)生了直接制約。例：緩沖區(qū)Buf：計(jì)算進(jìn)程和打印進(jìn)程共同使用同一緩沖區(qū)Buf。計(jì)算進(jìn)程：反復(fù)地把每次計(jì)算結(jié)果放入 Buf中；打印進(jìn)程：把計(jì)算進(jìn)程每次放入Buf中的數(shù)據(jù)通過打印機(jī)打印輸出。3.6進(jìn)程同步PC ： : A: localBuf1 Repeat Buf１←Buf UntilBuf１=空 計(jì)算 得到計(jì)算結(jié)果 Buf←計(jì)算結(jié)果 Goto APP: ： : B: localPri Repeat Pri←Buf Until Pri≠空 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù) Goto B假定進(jìn)程PC和PP對(duì)Buf已采取了互斥措施。如果按上面的描述并發(fā)執(zhí)行進(jìn)程PC和PP的話，則會(huì)造成CPU時(shí)間的極大浪費(fèi)。PC ：PP: ：假定進(jìn)程PC和PP對(duì)Buf已采取了互斥措直接制約: 一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過程稱為并發(fā)進(jìn)程間的直接制約。 異步環(huán)境主要指各并發(fā)進(jìn)程的執(zhí)行起始時(shí)間的隨機(jī)性和執(zhí)行速度的獨(dú)立性。直接制約:直接制約引起的問題：CPU時(shí)間的浪費(fèi)主要是由于進(jìn)程PC和PP的執(zhí)行互相制約所引起的。 PC的輸出結(jié)果是PP的執(zhí)行條件； PP的執(zhí)行結(jié)果也是PC的執(zhí)行條件；解決方案：直接制約的進(jìn)程互相給對(duì)方進(jìn)程發(fā)送執(zhí)行條件已經(jīng)具備的信號(hào)。這樣，被制約進(jìn)程即可省去對(duì)執(zhí)行條件的測(cè)試，只要收到了制約進(jìn)程發(fā)來的信號(hào)便開始執(zhí)行，而在未收到制約進(jìn)程發(fā)來的信號(hào)時(shí)便進(jìn)入等待狀態(tài)。直接制約引起的問題：CPU時(shí)間的浪費(fèi)主要是由于進(jìn)程PC和P進(jìn)程同步: 把異步環(huán)境下的一組并發(fā)進(jìn)程，因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過程稱為進(jìn)程間的同步。具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程；合作進(jìn)程間互相發(fā)送的信號(hào)稱為消息或事件。wait(消息名）： 表示進(jìn)程等待合作進(jìn)程發(fā)來的消息，signal（消息名）： 表示向合作進(jìn)程發(fā)送消息。進(jìn)程同步: 實(shí)現(xiàn)進(jìn)程同步：1）利用過程wait和signal實(shí)現(xiàn)同步；2）利用信號(hào)量實(shí)現(xiàn)同步； 實(shí)現(xiàn)進(jìn)程同步：wait的功能： 等待到消息名為true的進(jìn)程繼續(xù)執(zhí)行；signal的功能： 向合作進(jìn)程發(fā)送合作進(jìn)程所需要的消息名，并將其值置為true。wait的功能：(1)設(shè)消息名Bufempty：表示Buf空；

消息名Buffull：表示Buf中裝滿了數(shù)據(jù)。(2)初始化 Bufempty=true； Buffull=false。(3)描述： PC ： A: wait(Bufempty) 計(jì)算 Buf←計(jì)算結(jié)果 Bufempty←false signal(Buffull) Goto A PP ： B: wait(Buffull) 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù) Buffull←false signal(Bufempty) Goto B(1)設(shè)消息名Bufempty：表示Buf空； PP ：3.6.2私用信號(hào)量用信號(hào)量的方法實(shí)現(xiàn)進(jìn)程間的同步：把各進(jìn)程之間發(fā)送的消息作為信號(hào)量看；與互斥時(shí)不同，這里的信號(hào)量只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān)。因此，稱該信號(hào)量為私用信號(hào)量(PrivateSemaphvre）；一個(gè)進(jìn)程Pi的私用信號(hào)量Semi是從制約進(jìn)程發(fā)送來的進(jìn)程Pi的執(zhí)行條件所需要的消息。與私用信號(hào)量相對(duì)應(yīng)，稱互斥時(shí)使用的信號(hào)量為公用信號(hào)量。3.6.2私用信號(hào)量3.6.3用Ｐ，Ｖ原語操作實(shí)現(xiàn)同步利用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程同步的方法：首先為各并發(fā)進(jìn)程設(shè)置私用信號(hào)量；然后為私用信號(hào)量賦初值；最后利用Ｐ，Ｖ原語和私用信號(hào)量規(guī)定各進(jìn)程的執(zhí)行順序。3.6.3用Ｐ，Ｖ原語操作實(shí)現(xiàn)同步圖3.13緩沖區(qū)隊(duì)列例：設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)。PA為發(fā)送進(jìn)程；PB為接收進(jìn)程；PA發(fā)送數(shù)據(jù)時(shí)調(diào)用發(fā)送過程deposit(data);PB接收數(shù)據(jù)時(shí)調(diào)用過程remove(data)。且數(shù)據(jù)的發(fā)送和接收過程滿足如下條件：1)在PA至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長(zhǎng)等于緩沖區(qū)長(zhǎng)度）；2)PA往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí)，至少有一個(gè)緩沖區(qū)是空的；3)由PA發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出（FIFO）方式排列。圖3.13緩沖區(qū)隊(duì)列例：設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞發(fā)送過程deposit(data)和接受過程remove(data)必須同步執(zhí)行;deposit(data)的執(zhí)行結(jié)果是remove(data)的執(zhí)行條件；當(dāng)緩沖隊(duì)列全部裝滿數(shù)據(jù)時(shí)，remove(data)的執(zhí)行結(jié)果又是deposit(data)的執(zhí)行條件，滿足同步定義。按三步描述過程deposit(data)和remove(data)：（1)設(shè)Bufempty為進(jìn)程PA的私用信號(hào)量； Buffull為進(jìn)程PB的私用信號(hào)量；（2)令Bufempty的初始值為n（n為緩沖隊(duì)列的緩沖區(qū)個(gè)數(shù)）；Buffull的初始值為0；發(fā)送過程deposit(data)和接受過程remove(d（3)描述：PA:deposit(data): beginlocalx P(Bufempty)；

按FIFO方式選擇一個(gè)空緩沖區(qū)Buf(x)； Buf(x)←data Buf(x)置滿標(biāo)記 Ｖ（Buffull） endPB:remove(data): Beginlocalx Ｐ（Buffull）；

按FIFO方式選擇一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)Buf(x) data←Buf(x) Buf(x)置空標(biāo)記 Ｖ（Bufempty） end（3)描述：PB:remove(data):局部變量x用來指明緩沖區(qū)的區(qū)號(hào)，給Buf(x)置標(biāo)志位是為了便于區(qū)別和搜索空緩沖區(qū)及非空緩沖區(qū)。局部變量x用來指明緩沖區(qū)的區(qū)號(hào)，給Buf(x)置標(biāo)志位是為了3.6.4經(jīng)典進(jìn)程的同步問題生產(chǎn)者—消費(fèi)者問題哲學(xué)家進(jìn)餐問題讀者—寫者問題爸爸、媽媽，孩子吃水果問題3.6.4經(jīng)典進(jìn)程的同步問題生產(chǎn)者—消費(fèi)者問題生產(chǎn)者-消費(fèi)者問題把并發(fā)進(jìn)程的同步和互斥問題一般化，可以得到一個(gè)抽象的一般模型，即生產(chǎn)者-消費(fèi)者問題。把系統(tǒng)中使用某一類資源的進(jìn)程稱為該資源的消費(fèi)者;把釋放同類資源的進(jìn)程稱為該資源的生產(chǎn)者。例：計(jì)算進(jìn)程PC與打印進(jìn)程PP公用一個(gè)緩沖區(qū)。計(jì)算進(jìn)程PC把數(shù)據(jù)送入緩沖區(qū)；打印進(jìn)程PP從緩沖區(qū)中取數(shù)據(jù)打印輸出。PC進(jìn)程相當(dāng)于數(shù)據(jù)資源的生產(chǎn)者；PP進(jìn)程相當(dāng)于消費(fèi)者。生產(chǎn)者-消費(fèi)者問題把一個(gè)長(zhǎng)度為ｎ的有界緩沖區(qū)(n>0)與一群生產(chǎn)者進(jìn)程Ｐ1，Ｐ2，…，Ｐm和一群消費(fèi)者進(jìn)程Ｃ1，Ｃ2，…，Ｃk聯(lián)系起來；設(shè)生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程是互相等效;生產(chǎn)者和消費(fèi)者之間滿足同步條件：1)消費(fèi)者接收數(shù)據(jù)時(shí)有界緩沖區(qū)中至少有一個(gè)單元是滿的2)生產(chǎn)者發(fā)送數(shù)據(jù)時(shí)有界緩沖區(qū)中至少有一個(gè)單元是空的。有界緩沖區(qū)是臨界資源，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程之間必須互斥執(zhí)行。生產(chǎn)者調(diào)用過程deposit；消費(fèi)者調(diào)用過程remove把一個(gè)長(zhǎng)度為ｎ的有界緩沖區(qū)(n>0)與一群生產(chǎn)者進(jìn)程Ｐ1，Ｐ deposit(data): begin Ｐ（avail） Ｐ（mutex）

送數(shù)據(jù)入緩沖區(qū)某單元 Ｖ（full） Ｖ（mutex） end remove(data): begin Ｐ（full） Ｐ（mutex）

取緩沖區(qū)中某單元數(shù)據(jù) Ｖ（avail） Ｖ（mutex） end公用信號(hào)量mutex:保證生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程之間的互斥,表示可用有界緩沖區(qū)的個(gè)數(shù)，初值為1。信號(hào)量avail:為生產(chǎn)者進(jìn)程的私用信號(hào)量，表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號(hào)量full:為消費(fèi)者進(jìn)程的私用信號(hào)量,表示有界緩沖區(qū)中非空單元數(shù)，初值為0。 deposit(data): remove(data):公Ｖ原語是釋放資源的，可以以任意次序出現(xiàn)。Ｐ原語次序不能變，否則會(huì)造成死鎖。Ｖ原語是釋放資源的，可以以任意次序出現(xiàn)。經(jīng)典進(jìn)程的同步問題生產(chǎn)者—消費(fèi)者問題哲學(xué)家進(jìn)餐問題讀者—寫者問題爸爸、媽媽，孩子吃水果問題經(jīng)典進(jìn)程的同步問題生產(chǎn)者—消費(fèi)者問題哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題（TheDinningPhilosophersProblem）是由Dijkstra提出并解決的典型進(jìn)程同步問題問題描述5個(gè)哲學(xué)家坐在桌子邊，桌上有5個(gè)碗和5支筷子,分開放在每個(gè)人兩邊各一支.哲家家的生活方式是交替地進(jìn)行思考和進(jìn)餐哲學(xué)家饑餓時(shí)便拿起兩邊的筷子進(jìn)餐，但只有當(dāng)拿到兩支后才能進(jìn)餐用餐畢，放下筷子繼續(xù)思考哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題（TheDinningPhi哲學(xué)家進(jìn)餐問題利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問題經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使用，可以用一個(gè)信號(hào)量表示一只筷子，由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。其描述如下： Varchopstick:array［0,…,4］ofsemaphore;哲學(xué)家進(jìn)餐問題利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題所有信號(hào)量均被初始化為1，第i位哲學(xué)家的活動(dòng)可描述為：repeat wait(chopstick［i］);wait(chopstick［(i+1)mod5］);… eat;… signal(chopstick［i］); signal(chopstick［(i+1)mod5］); … think;untilfalse;問題：同時(shí)拿起一側(cè)的筷子，則——死鎖如何解決？？？哲學(xué)家進(jìn)餐問題所有信號(hào)量均被初始化為1，第i位哲學(xué)家的活動(dòng)哲學(xué)家進(jìn)餐問題可采取以下幾種解決方法至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。按此規(guī)定，將是1、2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子；3、4號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子。即五位哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后，再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐哲學(xué)家進(jìn)餐問題可采取以下幾種解決方法信號(hào)量機(jī)制——AND型信號(hào)量AND型信號(hào)量在有些任務(wù)中，一個(gè)進(jìn)程先要獲得多個(gè)共享資源后才能執(zhí)行，若進(jìn)程A和B都要訪問共享數(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)，若無外力作用無法解脫，稱為“死鎖”狀態(tài)信號(hào)量機(jī)制——AND型信號(hào)量AND型信號(hào)量此時(shí)，A和B處于僵信號(hào)量機(jī)制——AND型信號(hào)量AND同步機(jī)制的基本思想是將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作，即Swait(Simultaneouswait)信號(hào)量機(jī)制——AND型信號(hào)量AND同步機(jī)制的基本思想是信號(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;信號(hào)量機(jī)制——AND型信號(hào)量Swait(S1,S2,…,哲學(xué)家進(jìn)餐問題利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題在哲學(xué)家進(jìn)餐問題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是AND同步問題，用AND信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法Varchopstickarray［0,…,4］ofsemaphore:=(1,1,1,1,1);processirepeatthink;Sswait(chopstick［(i+1)mod5］,chopstick［i］);eat;Ssignat(chopstick［(i+1)mod5］,chopstick［i］);untilfalse;哲學(xué)家進(jìn)餐問題利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問題經(jīng)典進(jìn)程的同步問題生產(chǎn)者—消費(fèi)者問題哲學(xué)家進(jìn)餐問題讀者—寫者問題爸爸、媽媽，孩子吃水果問題經(jīng)典進(jìn)程的同步問題生產(chǎn)者—消費(fèi)者問題讀者—寫者問題一個(gè)數(shù)據(jù)文件或記錄可被多個(gè)進(jìn)程共享，我們把只要求讀該文件的進(jìn)程稱為“Reader進(jìn)程”，其他進(jìn)程稱為“Writer進(jìn)程”允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對(duì)象，因?yàn)樽x不會(huì)使數(shù)據(jù)文件混亂不允許一個(gè)Writer進(jìn)程和其他Reader進(jìn)程或Writer進(jìn)程同時(shí)訪問一個(gè)對(duì)象讀者—寫者問題(Reader-WriterProblem)是指保證一個(gè)Writer進(jìn)程必須與其他進(jìn)程互斥地訪問共享對(duì)象的同步問題讀者—寫者問題一個(gè)數(shù)據(jù)文件或記錄可被多個(gè)進(jìn)程共享，我們把只要讀者—寫者問題利用信號(hào)量解決讀者-寫者問題思想為實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號(hào)量Wmutex。另外，再設(shè)置一個(gè)整型變量Readcount表示正在讀的進(jìn)程數(shù)目由于只要有一個(gè)Reader進(jìn)程在讀，便不允許Writer進(jìn)程去寫。因此，僅當(dāng)Readcount=0,表示尚無Reader進(jìn)程在讀時(shí)，Reader進(jìn)程才需要執(zhí)行Wait(Wmutex)操作若wait(Wmutex)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時(shí)，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進(jìn)程寫又因?yàn)镽eadcount是一個(gè)可被多個(gè)Reader進(jìn)程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個(gè)計(jì)數(shù)器互斥信號(hào)量rmutex讀者—寫者問題利用信號(hào)量解決讀者-寫者問題思想讀者—寫者問題讀者-寫者問題可描述如下：Varrmutex,wmutex:semaphore:=1,1;Readcount:integer:=0;beginparbegin

Reader:begin

repe