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

第二章進程管理操作系統(tǒng)劉剛2/4/20231第二章進程管理重點理解進程的含義理解和掌握同步的概念及經典進程同步問題，是本課程的重點之一難點會寫進程同步問題的算法知識點進程、線程、進程的特征、PCB、進程控制、進程狀態(tài)轉換、進程同步、進程通信2/4/20232第二章進程管理進程的基本概念進程控制進程同步經典進程的同步問題管程機制進程通信線程2/4/20233進程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進程的特征與狀態(tài)進程控制塊2/4/20234程序的順序執(zhí)行及其特征兩種方式順序執(zhí)行：是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡單的單片機系統(tǒng)并發(fā)執(zhí)行：現(xiàn)在的操作系統(tǒng)，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率順序執(zhí)行的特征順序性：按照程序結構所指定的次序（可能有分支或循環(huán)）封閉性：獨占全部資源，計算機的狀態(tài)只由于該程序的控制邏輯所決定可再現(xiàn)性：初始條件相同則結果相同。如：可通過空指令控制時間關系2/4/20235程序的順序執(zhí)行及其特征僅當前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后進行計算，最后才能打印計算結果。語句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)三條語句的順序執(zhí)行S1S2S32/4/20237進程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進程的特征與狀態(tài)進程控制塊2/4/20238前趨圖前趨圖(PrecedenceGraph)是一個有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執(zhí)行的前后關系。圖中的每個結點可用于描述一個程序段或進程，乃至一條語句；結點間的有向邊則用于表示兩個結點之間存在的偏序(PartialOrder)或前趨關系(PrecedenceRelation)“→”→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,可寫成Pi→Pj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結點稱為初始結點(InitialNode)，把沒有后繼的結點稱為終止結點(FinalNode)2/4/20239前趨圖每個結點還具有一個重量(Weight,權值)，用于表示該結點所含有的程序量或結點的執(zhí)行時間P1P3P8P9P4P2P5P6P7(a)具有九個結點的前趨圖S1S2S3(b)具有循環(huán)的前趨圖2/4/202310前趨圖對于圖(a)所示的前趨圖，存在下述前趨關系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)}應當注意，前趨圖中必須不存在循環(huán)，但在圖(b)中卻有著下述的前趨關系：S2→S3,S3→S22/4/202311進程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進程的特征與狀態(tài)進程控制塊2/4/202312程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行時的前趨圖2/4/202313程序的并發(fā)執(zhí)行及其特征在該例中存在下述前趨關系：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í)行及其特征對于具有下述四條語句的程序段S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+bS1S2S3S42/4/202315程序的并發(fā)執(zhí)行及其特征例如有兩個循環(huán)程序A和B，它們共享一個變量N程序A和B以不同的速度運行(失去封閉性，導致不可再現(xiàn)性）N∶=N+1在Print(N)和N∶=0之前，此時得到的N值分別為n+1,n+1,0N∶=N+1在Print(N)和N∶=0之后，此時得到的N值分別為n,0,1N∶=N+1在Print(N)和N∶=0之間，此時得到的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程序得到的共享變量結果不同，失去封閉性、不可再現(xiàn)性；要得到良好的控制，系統(tǒng)必須要進行管理——進程控制管理2/4/202317程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行的特征間斷(異步)性"走走停停"，一個程序可能走到中途停下來，失去原有的時序關系；失去封閉性共享資源，受其他程序的控制邏輯的影響。如：一個程序寫到存儲器中的數(shù)據(jù)可能被另一個程序修改，失去原有的不變特征。失去可再現(xiàn)性失去封閉性－>失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復特征2/4/202318程序的并發(fā)執(zhí)行及其特征并發(fā)執(zhí)行失去封閉性的原因是共享資源的影響，去掉這種影響就行了。1966年，由Bernstein給出并發(fā)執(zhí)行的條件。（這里沒有考慮執(zhí)行速度的影響。）程序P(i)針對共享變量的讀集和寫集R(i)和W(i)條件：任意兩個程序P(i)和P(j)，有：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;前兩條保證一個程序的兩次讀之間數(shù)據(jù)不變化；最后一條保證寫的結果不丟掉現(xiàn)在的問題是這個條件不好檢查2/4/202319程序并發(fā)執(zhí)行的條件（1966年由Bernstein提出）若兩個程序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+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)={ }語句S1、S2______并發(fā)，因為______________________。語句S1、S3______并發(fā)，因為______________________。語句S2、S3______并發(fā)，因為______________________。語句S3、S4______并發(fā)，因為______________________。語句S2、S4______并發(fā)，因為______________________。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進程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進程概念進程的特征與狀態(tài)進程控制塊2/4/202322進程概念何謂進程（Process）如何理解進程概念？進程與程序有何差別？描述性定義：計算機中的所有程序（軟件），按照某種順序運行，這種運行的過程稱之為進程。2/4/202323進程概念閱讀菜譜準備原料烹制菜肴飯菜閱讀洗衣機手冊準備衣服、洗衣粉設定參數(shù)，洗衣服干凈衣服程序輸入運行輸出程序輸入運行輸出分時切換洗衣進程做飯進程2/4/202324進程概念進程的核心思想進程是某種類型的一個活動，它有程序、輸入、輸出和狀態(tài)。在分時操作系統(tǒng)中，單個CPU被若干進程共享，它使用某種調度算法決定何時停止一個進程的運行，轉而為其他進程提供服務。2/4/202325進程概念較典型的進程定義有：進程是程序的一次執(zhí)行進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調度的一個獨立單位2/4/202326進程的基本概念程序的順序執(zhí)行及其特征前趨圖程序的并發(fā)執(zhí)行及其特征進程概念進程的特征與狀態(tài)進程控制塊2/4/202327進程的特征與狀態(tài)動態(tài)性：進程具有動態(tài)的地址空間（數(shù)量和內容），地址空間上包括：代碼（指令執(zhí)行和CPU狀態(tài)的改變）數(shù)據(jù)（變量的生成和賦值）系統(tǒng)控制信息（進程控制塊的建立和系統(tǒng)收回）獨立性：各進程的地址空間相互獨立，除非采用進程間通信手段；并發(fā)性：多個進程實體同存于內存中，且能在一段時間內同時運行；引入進程實體的目的就是并發(fā)執(zhí)行異步性：各進程按各自獨立的、不可預知的速度向前推進結構性：程序段、數(shù)據(jù)段和PCB；程序文件中通常也劃分了代碼段和數(shù)據(jù)段，進程的創(chuàng)建與撤消就是PCB的創(chuàng)建與撤消2/4/2023282.1.4進程的特征與狀態(tài)1.進程的特征和定義 通常的程序是不能并發(fā)執(zhí)行的。應為之配置進程控制塊，即PCB；而由程序段、相關的數(shù)據(jù)段和PCB三部分便構成了進程實體。在許多情況下所說的進程，實際上是指進程實體。所謂創(chuàng)建進程，實質上是創(chuàng)建進程實體中的PCB；而撤銷進程，實質上是撤銷進程的PCB。2/4/202329進程概念較典型的進程定義有：進程是程序的一次執(zhí)行進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調度的一個獨立單位在引入了進程實體的概念后，我們可以把傳統(tǒng)OS中的進程定義為：“進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調度的一個獨立單位”2/4/202330進程與程序的區(qū)別進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進程是程序的執(zhí)行。通常進程不可在計算機之間遷移；而程序通常對應著文件、靜態(tài)和可以復制進程是暫時的，程序的永久的：進程是一個狀態(tài)變化的過程，程序可長久保存進程與程序的組成不同：進程的組成包括程序、數(shù)據(jù)和進程控制塊（即進程狀態(tài)信息）進程與程序的對應關系：通過多次執(zhí)行，一個程序可對應多個進程；通過調用關系，一個進程可包括多個程序2/4/202331進程的特征與狀態(tài)—進程的三種基本狀態(tài)就緒(Ready)狀態(tài)

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

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

終止

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

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

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

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

進程控制

進程同步

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

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

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

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

當已有進程進入臨界區(qū)時，其他進程必須等待有限等待

對要求訪問臨界資源的進程，應保證在有限時間內進入自己的臨界區(qū)，防止"死等"讓權等待

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

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

進程控制

進程同步

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

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

parbeginproducer:begin//生產者進程repeat…produceranitemnextp;//產一個產品…

wait(empty);//empty減1

wait(mutex);//加鎖buffer(in):=nextp;in:=(in+1)modn;//移動生產指針

signal(mutex);//解鎖

signal(full);//full增1untilfalse;endconsumer:begin//消費者進程repeat

wait(full);

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

signal(mutex);

signal(empty);consumertheiteminnextc;untilfalse;end