1、第二章 進 程 管 理 第二章第二章 進程管理進程管理 2.1 2.1 進程的基本概念進程的基本概念 2.2 2.2 進程控制進程控制 2.3 2.3 進程同步進程同步 2.4 2.4 經典進程的同步問題經典進程的同步問題 2.5 2.5 進程通信進程通信 2.6 2.6 線程線程 第二章 進 程 管 理 2.1 進程的基本概念進程的基本概念 2.1.1 程序的順序執行及其特征程序的順序執行及其特征 1. 程序的順序執行程序的順序執行 僅當前一操作(程序段)執行完后，才能執行后繼操作。例如，在進行計算時，總須先輸入用戶的程序和數據，然后進行計算，最后才能打印計算結果。 S1: a =x+y;

2、S2: b =a-5; S3: c =b+1;第二章 進 程 管 理 圖 2-1 程序的順序執行 (a) 程序的順序執行(b) 三條語句的順序執行I1C1P1I2C2P2S1S2S3 S1: a =x+y; S2: b =a-5; S3: c =b+1;第二章 進 程 管 理 2. 程序順序執行時的特征程序順序執行時的特征 順序性：處理機的操作必須嚴格按照程序所規定的順序執行(2) 封閉性： 程序在執行時獨占系統的全部資源，因此機器資源狀態的改變只與執行的程序有關，與外界環境無關(3) 可再現性： 只要初始條件相同，一個程序的多次重復執行，將得到相同的結果第二章 進 程 管 理 2.1.2 前

3、趨圖前趨圖 前趨圖(Precedence Graph)是一個有向無循環圖，記為DAG(Directed Acyclic Graph)，用于描述進程之間執行的前后關系。圖中的每個結點可用于描述一個程序段或進程，乃至一條語句；結點間的有向邊則用于表示兩個結點之間存在的偏序(Partial Order)或前趨關系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結點稱為初始結點(Initial

4、Node)，把沒有后繼的結點稱為終止結點(Final Node)。第二章 進 程 管 理 每個結點還具有一個重量(Weight)，用于表示該結點所含有的程序量或結點的執行時間。 IiCiPi和S1S2S3 圖 2-2 前趨圖 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九個結點的前趨圖(b) 具有循環的前趨圖第二章 進 程 管 理 對于圖 2-2(a)所示的前趨圖， 存在下述前趨關系： P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示為： P=P1, P2, P3, P4, P5, P6, P

5、7, P8, P9= (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9) 應當注意，前趨圖中必須不存在循環，但在圖2-2(b)中卻有著下述的前趨關系：S2S3, S3S2 第二章 進 程 管 理 【聯48】已知一個求值公式： 若A、B已賦值，試畫出該公式求值過程的前趨圖。2(3 )/(5 )ABBA第二章 進 程 管 理 2.1.3 程序的并發執行及其特征程序的并發執行及其特征 1. 程序的并發執行程序的并發執行 圖 2-3 并發

6、執行時的前趨圖 P1P2P3P4I1I2I3I4C1C2C3C4第二章 進 程 管 理 在該例中存在下述前趨關系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發執行。 對于具有下述四條語句的程序段： S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b P1P2P3P4I1I2I3I4C1C2C3C4第二章 進 程 管 理 圖 2-4 四條語句的前趨關系S1S2S3S4 S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b第二

7、章 進 程 管 理 2. 程序并發執行時的特征程序并發執行時的特征 程序的并發執行是指二個或二個以上的程序或程序段可在同一時間間隔內同時執行。 程序的并發執行極大提高了資源利用率和系統吞吐量，也產生了不同于順序執行的新特征：1. 間斷性： 由于資源共享和相互合作，并發執行的程序間形成了相互制約關系，導致程序的運行過程出現“執行-暫停-執行”的現象2. 失去封閉性：程序在執行時與其他并發執行的程序共享系統的資源，因此資源狀態的改變還與其他程序有關 3. 不可再現性 ：同樣的初始條件，一個程序的多次重復執行，可能得到不同的結果 第二章 進 程 管 理 例如，有兩個循環程序A和B，它們共享一個變量N

8、。程序A每執行一次時，都要做N =N+1操作；程序B每執行一次時， 都要執行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運行。 (1) N =N+1在Print(N)和N =0之前，此時得到的N值分別為n+1, n+1, 0。 (2) N =N+1在Print(N)和N =0之后，此時得到的N值分別為n, 0, 1。 (3) N =N+1在Print(N)和N =0之間，此時得到的N值分別為n, n+1, 0。 第二章 進 程 管 理 2.1.4 進程的特征與狀態進程的特征與狀態 1. 進程的特征和定義進程的特征和定義 結構特征：從結構上說，每個進程實體中除了相應的程序段

9、、數據段外，必須包含一個數據結構進程控制塊PCB2) 動態性 ：進程是程序的一次執行過程，因此是都動態的。動態性還表現在進程具有一定的生命期，它必須由創建而產生、由調度而執行、由撤銷而消亡。3) 并發性 ：指多個進程實體同存于內存中，且能在一段時間內同時運行。只有為程序創建進程后，多個程序才能正確地并發運行，并發是引入進程的目的。第二章 進 程 管 理 4) 獨立性：進程實體是一個能獨立運行、獨立分配資源和獨立接受調度的基本單位 5) 異步性 ：進程可按各自獨立、不可預知的速度向前推進第二章 進 程 管 理 較典型的進程定義有： (1) 進程是程序的一次執行。 (2) 進程是一個程序及其數據在

10、處理機上順序執行時所發生的活動。 (3) 進程是程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立單位。 在引入了進程實體的概念后，我們可以把傳統OS中的進程定義為：“進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位”。 第二章 進 程 管 理 【聯1】以下對進程的描述中，錯誤的是 A進程是動態的概念 B 進程執行需要處理機 C 進程是有生命期的 D 進程是指令的集合第二章 進 程 管 理 【聯3】一個進程是 A 有處理機執行的一個程序 B 一個獨立的程序+數據集 C PCB結構、程序和數據的組合 D 一個獨立的程序第二章 進 程 管 理 【聯5】在單處理機系

11、統中實現并發技術后，A 各進程在某一時刻并行運行，cpu與i/o設備間并行工作B各進程在一個時間段內并行運行，cpu與i/o設備間串行工作C各進程在一個時間段內并行運行，cpu與i/o設備間并行工作D各進程在某一時刻并行運行，cpu與i/o設備間串行工作第二章 進 程 管 理 總結：進程與程序的區別 1.進程是程序的執行，所以進程屬于動態概念，而程序是一組指令的有序集合，是靜態的概念 2.進程既然是程序的執行，或者說是“一次運行活動”，因而它是有生命過程的，從投入運行到運行完成，它的存在是暫時的，而程序的存在時永久的 3.進程是程序的執行，因此進程的組成應包括程序和數據。除此之外，進程還由記錄

12、進程狀態信息的PCB組成。 4.進程是競爭計算機系統有限資源的基本單位 5.一個進程能與其他進程并發地活動 6.一個程序可能對應多個進程，一個進程可以包含多個程序。進程和程序無一一對應關系第二章 進 程 管 理 2. 進程的三種基本狀態進程的三種基本狀態 就緒(Ready)狀態 ：進程已獲得除cpu以外的所有必要資源，只要得到cpu便可立即執行。可以有多個就緒狀態的進程2) 執行狀態：進程已得到cpu，其程序正在cpu上執行 3) 阻塞狀態：正在執行的進程因某種事件（如I/O請求）的發生而暫時無法繼續執行，只有等相應事件完成后，才能去競爭cpu 第二章 進 程 管 理 圖 2-5 進程的三種基

13、本狀態及其轉換 就緒阻塞執行時間片完進程調度I/O完成I/O請求第二章 進 程 管 理 3. 掛起狀態掛起狀態不少系統中，進程只有上述三種基本狀態，但另些系統中增加了掛起狀態，其實質使進程不能繼續執行，即掛起后的進程處于就緒狀態，它也不能參加cpu的競爭，被掛起的進程處于靜止狀態，相反，沒有被掛起的進程處于活動狀態，只有通過激活才能得以實現引入掛起狀態的原因引入掛起狀態的原因 終端用戶的請求。 用戶發現可疑問題，希望暫時使自己的程序靜止下來，以便研究其執行情況或修改 第二章 進 程 管 理 (2) 父進程請求。 父進程希望掛起某個子進程，考查或修改它，或協調各子進程之間的活動 (3) 負荷調節

14、的需要。 當負荷較重，影響對實時任務的控制 (4) 操作系統的需要。 檢查運行中的資源使用情況等另外，掛起進程可以騰出內存空間給其它就緒進程使用第二章 進 程 管 理 2) 進程狀態的轉換 活動就緒靜止就緒。 (2) 活動阻塞靜止阻塞。 (3) 靜止就緒活動就緒。 (4) 靜止阻塞活動阻塞。 第二章 進 程 管 理 圖 2-6 具有掛起狀態的進程狀態圖 活動就緒靜止就緒執行掛起激活釋放掛起活動阻塞靜止阻塞掛起激活釋放請求I/O第二章 進 程 管 理 【聯8】分配到必要的資源并獲得處理機時間的進程狀態是 A 就緒 B 運行 C 阻塞 D 撤銷第二章 進 程 管 理 【聯9】當一個進程處于這樣的狀

15、態時，_，稱為阻塞狀態 A 它正等著輸入一批數據 B 它正等著進程調度 C 它正等著分給它一個時間片 D 它正等著進入內存第二章 進 程 管 理 用戶作業錄入提交收容完成運行就緒等待作業調度執行作業調度 批處理系統中作業處理及狀態批處理系統中作業處理及狀態第二章 進 程 管 理 【聯10】某運行中的進程要申請打印機，它將變為_ A 就緒態 B 阻塞態 C 創建態 D 撤銷態第二章 進 程 管 理 【聯11】以下進程狀態轉變中，_轉變時不可能發生的。 A 運行-就緒 B 運行-阻塞 C 阻塞-運行 D 阻塞-就緒第二章 進 程 管 理 【聯13】一個進程的基本狀態可以從其他兩種基本狀態轉變過來，

16、這個基本狀態一定是 就緒狀態 第二章 進 程 管 理 【聯19】進程自身決定_ A 從運行狀態到阻塞狀態 B 從運行狀態到就緒狀態 C 從就緒狀態到運行狀態 D 從阻塞狀態到就緒狀態第二章 進 程 管 理 【聯20】以下可能導致一個進程從運行狀態變為就緒狀態的事件是_ A 一次 I/O 操作結束 B 運行進程需要做 I/O 操作 C 運行進程結束 D 出現了比現在進程優先級更高的進程第二章 進 程 管 理 【聯21】一個進程釋放一種資源有可能導致一個或幾個進程_ A 就緒變運行 B 運行變就緒 C 阻塞變運行 D 阻塞變就緒第二章 進 程 管 理 【聯22】一次i/o操作的結束，有可能導致_A

17、一個進程由阻塞變為就緒B 幾個進程由阻塞變為就緒C一個進程由阻塞變為運行D幾個進程由阻塞變為運行第二章 進 程 管 理 2.1.5 進程控制塊進程控制塊 1. 進程控制塊的作用進程控制塊的作用 進程控制塊的作用是使一個在多道程序環境下不能獨立運行的程序(含數據)，成為一個能獨立運行的基本單位，一個能與其它進程并發執行的進程。或者說，OS是根據PCB來對并發執行的進程進行控制和管理的。PCB要被系統頻繁訪問，必須常駐內存。第二章 進 程 管 理 2. 進程控制塊中的信息進程控制塊中的信息 1) 進程標識符 進程標識符用于惟一地標識一個進程。一個進程通常有兩種標識符： (1) 內部標識符。在所有的

18、操作系統中，都為每一個進 程賦予一個惟一的數字標識符，它通常是一個進程的序號。 設置內部標識符主要是為了方便系統使用。 (2) 外部標識符。它由創建者提供，通常是由字母、數字組成，往往是由用戶(進程)在訪問該進程時使用。為了描述進程的家族關系， 還應設置父進程標識及子進程標識。此外，還可設置用戶標識，以指示擁有該進程的用戶。 第二章 進 程 管 理 2) 處理機狀態 處理機狀態信息主要是由處理機的各種寄存器中的內容組成的。 處理機在運行時，許多信息都存放在寄存器中，當處理機被中斷時，所有這些信息都必須保持在PCB中，以便在該進程重新執行時，能從斷點繼續執行。第二章 進 程 管 理 3) 進程調

19、度信息 在PCB中還存放一些與進程調度和進程對換有關的信息，包括： 進程狀態，指明進程的當前狀態， 作為進程調度和對換時的依據； 進程優先級，用于描述進程使用處理機的優先級別的一個整數， 優先級高的進程應優先獲得處理機； 進程調度所需的其它信息，它們與所采用的進程調度算法有關，比如，進程已等待CPU的時間總和、 進程已執行的時間總和等； 事件，是指進程由執行狀態轉變為阻塞狀態所等待發生的事件，即阻塞原因。 第二章 進 程 管 理 4) 進程控制信息 進程控制信息包括： 程序和數據的地址， 是指進程的程序和數據所在的內存或外存地(首)址，以便再調度到該進程執行時，能從PCB中找到其程序和數據；

20、進程同步和通信機制，指實現進程同步和進程通信時必需的機制， 如消息隊列指針、信號量等，它們可能全部或部分地放在PCB中； 資源清單，是一張列出了除CPU以外的、進程所需的全部資源及已經分配到該進程的資源的清單； 鏈接指針， 它給出了本進程(PCB)所在隊列中的下一個進程的PCB的首地址。 第二章 進 程 管 理 3. 進程控制塊的組織方式進程控制塊的組織方式 1) 鏈接方式 圖 2-7 PCB鏈接隊列示意圖 PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901執行指針就緒隊列指針阻塞隊列指針空閑隊列指針第二章 進 程 管 理 2) 索引方式 圖 2-8 按索

21、引方式組織PCB 執行指針就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就緒表指針阻塞表指針第二章 進 程 管 理 2.2 進進 程程 控控 制制 2.2.1 進程的創建進程的創建 1. 進程圖(Process Graph) 圖 2-9 進程樹 DEFGHBCIJKLMA第二章 進 程 管 理 2. 引起創建進程的事件引起創建進程的事件 用戶登錄。用戶在終端鍵入登錄命令后，如果是合法用戶，系統將建立一個進程，并插入就緒隊列中 (2) 作業調度。作業裝入內存，立即分配資源，創建進程，插入就緒隊列 (3) 提供服務。 用戶提出請求后，系統專門創建一個進程里提供用戶所需

22、的服務(4) 應用請求。 以上三種都是系統內核創建的，應用程序為自己創建一個新進程第二章 進 程 管 理 3. 進程的創建進程的創建(Creation of Progress) (1)申請空白PCB。 (2) 為新進程分配資源。 (3) 初始化進程控制塊。 (4) 將新進程插入就緒隊列，如果進程就緒隊列能夠接納新進程， 便將新進程插入就緒隊列。 第二章 進 程 管 理 2.2.2 進程的終止進程的終止 1. 引起進程終止引起進程終止(Termination of Process)的事件的事件 當進程完成任務或遇到異常情況和外界干預需要結束時，應通過進程終止原語來終止進程。終止進程的實質是收回P

23、CB。具體的操作過程是：找到要終止進程的PCB；若該進程正在執行，則終止它的執行，并置重新調度的標志；終止屬于該進程的所有子孫進程；釋放終止進程所擁有的全部資源；將終止進程移出它所在的隊列并收回PCB。第二章 進 程 管 理 1) 正常結束 在任何計算機系統中，都應有一個用于表示進程已經運行完成的指示。例如，在批處理系統中，通常在程序的最后安排一條Holt指令或終止的系統調用。當程序運行到Holt指令時，將產生一個中斷，去通知OS本進程已經完成。 在分時系統中，用戶可利用Logs off去表示進程運行完畢， 此時同樣可產生一個中斷，去通知OS進程已運行完畢。 第二章 進 程 管 理 2) 異常

24、結束 在進程運行期間，由于出現某些錯誤和故障而迫使進程終止。這類異常事件很多，常見的有： 越界錯誤越界錯誤。這是指程序所訪問的存儲區，已越出該進程的區域； 保護錯保護錯。進程試圖去訪問一個不允許訪問的資源或文件，或者以不適當的方式進行訪問，例如，進程試圖去寫一個只讀文件； 非法指令非法指令。程序試圖去執行一條不存在的指令。出現該錯誤的原因，可能是程序錯誤地轉移到數據區，把數據當成了指令； 特權指令錯特權指令錯。用戶進程試圖去執行一條只允許OS執行的指令； 運行超時運行超時。進程的執行時間超過了指定的最大值； 等待超時等待超時。進程等待某事件的時間， 超過了規定的最大值； 算術運算錯。算術運算錯

25、。進程試圖去執行一個被禁止的運算，例如，被0除； I/O故障故障。這是指在I/O過程中發生了錯誤等。 第二章 進 程 管 理 3) 外界干預 外界干預并非指在本進程運行中出現了異常事件，而是指進程應外界的請求而終止運行。這些干預有： 操作員或操作系統干預。 由于某種原因，例如，發生了死鎖， 由操作員或操作系統終止該進程； 父進程請求。 由于父進程具有終止自己的任何子孫進程的權利， 因而當父進程提出請求時，系統將終止該進程； 父進程終止。 當父進程終止時，OS也將他的所有子孫進程終止。 2.2.3 進程的阻塞與喚醒進程的阻塞與喚醒1. 引起進程阻塞和喚醒的事件引起進程阻塞和喚醒的事件 請求系統服

26、務，不能滿足 2) 啟動某種操作，等待完成3) 新數據尚未到達 4) 無新工作可做 進進程程的的阻阻塞塞是是進進程程自自身身的的一一種種自自主主行行為為 2. 進程阻塞過程進程阻塞過程入口入口保存當前的保存當前的CPU現場現場置進程的狀態為阻塞態置進程的狀態為阻塞態被阻塞進程入等待隊列被阻塞進程入等待隊列轉進程調度轉進程調度 3. 進程喚醒過程進程喚醒過程入口入口從等待隊列中摘下被喚醒的進程從等待隊列中摘下被喚醒的進程將被喚醒進程置為就緒態將被喚醒進程置為就緒態將被喚醒進程送入就緒隊列將被喚醒進程送入就緒隊列轉進程調度或返回轉進程調度或返回第二章 進 程 管 理 Block原語和wakeup原

27、語是一對作用剛好相反的原語。因此，如果在某進程中調用了阻塞原語，則必須在與之合作的另一進程中或其它相關的進程中安排喚醒原語；否則，被阻塞進程將會因不能被喚醒而長久地處于阻塞狀態，從而再無機會繼續運行。2.2.4 進程的掛起與激活進程的掛起與激活 1. 進程的掛起進程的掛起 當出現了引起進程掛起的事件時，系統將利用掛起當出現了引起進程掛起的事件時，系統將利用掛起原語原語suspend( )將指定進程或處于阻塞狀態的進程掛起。將指定進程或處于阻塞狀態的進程掛起。 掛起原語的掛起原語的執行過程執行過程是：首先檢查被掛起進程的狀是：首先檢查被掛起進程的狀態，若處于態，若處于活動就緒狀態活動就緒狀態，便

28、將其改為，便將其改為靜止就緒靜止就緒；對于；對于活動阻塞狀態活動阻塞狀態的進程，則將之改為的進程，則將之改為靜止阻塞靜止阻塞。 為了方便為了方便用戶或父進程考查該進程的運行情況而把該進程的用戶或父進程考查該進程的運行情況而把該進程的PCB復制到某指定的內存區域。最后，若被掛起的進程正在復制到某指定的內存區域。最后，若被掛起的進程正在執行，則轉向執行，則轉向調度程序重新調度調度程序重新調度。 2. 進程的激活過程進程的激活過程 當發生激活進程的事件時，系統將利用當發生激活進程的事件時，系統將利用激活原語激活原語active( )將指定進程激活。將指定進程激活。 激活原語先將進程從外存調入內存，檢

29、激活原語先將進程從外存調入內存，檢查該進程的現行狀態，若是靜止就緒，便將之改為活動就緒；查該進程的現行狀態，若是靜止就緒，便將之改為活動就緒；若為靜止阻塞便將之改為活動阻塞。若為靜止阻塞便將之改為活動阻塞。 假如采用的是假如采用的是搶占調度策略搶占調度策略，則每當有新進程進入就緒，則每當有新進程進入就緒隊列時，應檢查是否要進行重新調度。隊列時，應檢查是否要進行重新調度。 第二章 進 程 管 理 【聯28】以下說法中，_不是創建進程所必須的。 A 建立一個進程的進程表項 B 為進程分配內存 C 為進程分配cpu D 將進程表項插入就緒隊列中第二章 進 程 管 理 【聯30】以下_不會引起進程創建

30、 A 用戶登錄 B 作業調度 C 設備分配 D 應用請求2.3 進進 程程 同同 步步 2.3.1 進程同步的基本概念進程同步的基本概念 1. 兩種形式的制約關系兩種形式的制約關系 間接相互制約關系。間接相互制約關系。（資源共享）（資源共享） 進程A和B共享一臺打印機(2) 直接相互制約關系。直接相互制約關系。（進程合作）（進程合作） 進程A和B通過單緩沖區合作工作 2. 臨界資源臨界資源(Critical Resouce) 生產者-消費者(producer-consumer)問題是一個著名的進程同步問題。它描述的是：有一群生產者一群生產者進程進程在生產產品，并將這些產品提供給消費者進程消費者

31、進程去消費。為使生產者進程與消費者進程能并發執行，在兩者之間設置了一個具有n個緩沖區的個緩沖區的循環循環緩沖緩沖池池，生產者進程將它所生產的產品放入一個緩沖區中；諸進程采取互斥方式訪問的資源諸進程采取互斥方式訪問的資源即為即為臨界資源。臨界資源。 消費者進程可從一個緩沖區中取走產品去消費。盡管所有的生產者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步必須保持同步，即不允不允許消費者進程到一個空緩沖區去取產品；也不允許消費者進程到一個空緩沖區去取產品；也不允許生產者進程向一個已裝滿產品且尚未被取走的許生產者進程向一個已裝滿產品且尚未被取走的緩沖區中投放產品。緩沖區中投放產品。 我們

32、可利用一個數組來表示上述的具有n個(0，1，n-1)緩沖區的緩沖池。用輸入指針輸入指針in來指示下一個可投放產品的緩沖區，每當生產者進程生產并投放一個產品后，輸入指針加1；用一個輸出指針輸出指針out來指示下一個可從中獲取產品的緩沖區，每當消費者進程取走一個產品后，輸出指針加1。 由于這里的緩沖池是組織成循環緩沖的，故應把輸入指針加1表示成 in =(in+1)mod n； 輸出指針加1表示成out =(out+1) mod n。當(in+1) mod n=out時表示緩沖池滿時表示緩沖池滿；而in=out則表示緩沖池空則表示緩沖池空。此外，還引入了一個整型變整型變量量counter, 其初始

33、值為0。每當生產者進程向緩沖池中投放一個產品后，使counter加1；反之，每當消費者進程從中取走一個產品時， 使counter減1。生產者和消費者兩進程共享下面的變量：Var n, integer;type item=;var buffer:array0, 1, , n-1 of item;in, out: 0, 1, , n-1;counter: 0, 1, , n; 指針指針in和和out初始化為初始化為1。在生產者和消費者進程的描述。在生產者和消費者進程的描述中，中，no-op是一條空操作指令，是一條空操作指令，while condication do no-op語句表示重復的測試條件

34、語句表示重復的測試條件(condication)，重復測試應進行到，重復測試應進行到該條件變為該條件變為false(假假)，即到該條件不成立時為止。在生產者，即到該條件不成立時為止。在生產者進程中使用一局部變量進程中使用一局部變量nextp，用于暫時存放每次剛生產出，用于暫時存放每次剛生產出來的產品；而在消費者進程中，則使用一個局部變量來的產品；而在消費者進程中，則使用一個局部變量nextc,用于存放每次要消費的產品。用于存放每次要消費的產品。 producer: repeat produce an item in nextp; while counter=n do no-op; buffer

35、in =nextp; in =in+1 mod n; counter =counter+1; until false;consumer: repeat while counter=0 do no-op; nextc =bufferout; out =(out+1) mod n; counter =counter-1; consumer the item in nextc; until false; 雖然上面的生產者程序和消費者程序，在分別看時都是正確的，而且兩者在順序執行時其結果也會是正確的，但若并發執行時，就會出現差錯，問題就在于這兩個進程共享變量counter。生產者對它做加1操作，消費者

36、對它做減1操作，這兩個操作在用機器語言實現時， 常可用下面的形式描述： register 1 =counter; register 2 =counter; register1 =register1+1; register 2 =register2 -1; counter = register 1; counter =register 2;假設：counter的當前值是5。如果生產者進程先執行左列的三條機器語言語句，然后消費者進程再執行右列的三條語句， 則最后共享變量counter的值仍為5；反之，如果讓消費者進程先執行右列的三條語句，然后再讓生產者進程執行左列的三條語句，counter值也還是

37、5。但是，如果按下述順序執行： register 1 =counter; (register 1=5) register 1 =register 1+1; (register 1=6) register 2 =counter; (register 2=5) register 2 =register 2-1; (register 2=4) counter =register 1; (counter=6) counter =register 2; (counter=4) 正確的值應該為5，但現在是4.還可能出現答案為6的情況。失去可再現性失去可再現性3. 臨界區臨界區(critical secti

38、on) 諸進程須采取互斥方式訪問的軟硬件資源臨界資源進程中訪問臨界資源的那段代碼稱為臨界區可把一個訪問臨界資源的循環進程描述如下：repeat critical section; remainder section;until false; entry sectionexit section4. 同步機制應遵循的規則同步機制應遵循的規則 空閑讓進。臨界資源空閑時允許進程進入自己的臨界區(2) 忙則等待。臨界資源被訪問時，其他要求進去臨界區的進程必須等待 (3) 有限等待。進程應在有限的時間內進入自己的臨界區，以免死等 (4) 讓權等待。不能進入臨界區的進程應立即釋放CPU，以免忙等 第二章 進

39、 程 管 理 2.3.2 信號量機制信號量機制 1. 整型信號量整型信號量 最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作(Atomic Operation) wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。 wait和signal操作可描述為： wait(S): while S0 do no-op S =S-1; signal(S): S =S+1; 第二章 進 程 管 理 2. 記錄型信號量記錄型信號量 在整型信號量機制中的wait操作，只要是信號量S0， 就會不斷地測試。因此，該機制并未遵循“讓權等待”的準則， 而

40、是使進程處于“忙等”的狀態。記錄型信號量機制，則是一種不存在“忙等”現象的進程同步機制。但在采取了“讓權等待”的策略后，又會出現多個進程等待訪問同一臨界資源的情況。為此，在信號量機制中，除了需要一個用于代表資源數目的整型變量value外，還應增加一個進程鏈表L，用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數據結構而得名的。它所包含的上述兩個數據項可描述為： 第二章 進 程 管 理 type semaphore=record value:integer; L:list of process; end相應地，wait(S)和signal(S)操作可描述為：procedure wa

41、it(S) var S: semaphore; begin S.value =S.value-1; if S.value0 then block(S,L) end procedure signal(S) var S: semaphore; begin S.value =S.value+1; if S.value0 then wakeup(S,L); end 第二章 進 程 管 理 在記錄型信號量機制中，S.value的初值表示系統中某類資源的數目， 因而又稱為資源信號量，對它的每次wait操作，意味著進程請求一個單位的該類資源，因此描述為S.value =S.value-1； 當S.value

42、0時，表示該類資源已分配完畢，因此進程應調用block原語，進行自我阻塞，放棄處理機，并插入到信號量鏈表S.L中。可見，該機制遵循了“讓權等待”準則。 此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數目。 對信號量的每次signal操作，表示執行進程釋放一個單位資源，故S.value =S.value+1操作表示資源數目加1。 若加1后仍是S.value0，則表示在該信號量鏈表中，仍有等待該資源的進程被阻塞，故還應調用wakeup原語，將S.L鏈表中的第一個等待進程喚醒。如果S.value的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量轉化為互斥信號量。 第二章 進 程 管

43、 理 3. AND型信號量型信號量 在兩個進程中都要包含兩個對Dmutex和Emutex的操作， 即process A: process B:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若進程A和B按下述次序交替執行wait操作：process A: wait(Dmutex); 于是Dmutex=0process B: wait(Emutex); 于是Emutex=0process A: wait(Emutex); 于是Emutex=-1 A阻塞process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 第二

44、章 進 程 管 理 AND同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其它所有可能為之分配的資源，也不分配給他。亦即，對若干個臨界資源的分配，采取原子操作方式：要么全部分配到進程，要么一個也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發生。為此，在wait操作中，增加了一個“AND”條件，故稱為AND同步，或稱為同時wait操作， 即Swait(Simultaneous wait)定義如下： 第二章 進 程 管 理 Swait(S1, S2, , Sn) if Si1 and and Sn

45、1 then for i =1 to n do Si =Si-1; endfor else place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endifSsignal(S1, S2, , Sn) for i =1 to n do Si=Si+1; Remove all the process waiting in the q

46、ueue associated with Si into the ready queue. endfor; 第二章 進 程 管 理 4. 信號量集信號量集 Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i =1 to n do Si =Si-di; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of t

47、he Swait Operation. endif signal(S1, d1, , Sn, dn) for i =1 to n do Si =Si+di;Remove all the process waiting in the queue associated with Si into the ready queue endfor; 第二章 進 程 管 理 一般“信號量集”的幾種特殊情況： (1) Swait(S, d, d)。 此時在信號量集中只有一個信號量S， 但允許它每次申請d個資源，當現有資源數少于d時，不予分配。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般

48、的記錄型信號量(S1時)或互斥信號量(S=1時)。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號量操作。當S1時，允許多個進程進入某特定區；當S變為0后，將阻止任何進程進入特定區。換言之，它相當于一個可控開關。 第二章 進 程 管 理 2.3.3 信號量的應用信號量的應用 1. 利用信號量實現進程互斥利用信號量實現進程互斥 利用信號量實現進程互斥的進程可描述如下：Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex)

49、; remainder seetion until false; 第二章 進 程 管 理 end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 第二章 進 程 管 理 2. 利用信號量實現前趨關系利用信號量實現前趨關系 圖 2-10 前趨圖舉例 圖 2-10 前趨圖舉例 S4S5S3S1S6S2abcdfge第二章 進 程 管 理 Var a,b,c,d,e,f,g; semaphore =0,0,0,0,0,0,0;

50、begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end 第二章 進 程 管 理 第二章 進 程 管 理 第二章 進 程 管 理 第二章 進 程

51、管 理 第二章 進 程 管 理 第二章 進 程 管 理 第二章 進 程 管 理 華中理工大學1999年試題，哈工大2000年試題第二章 進 程 管 理 司機和售票員之間的同步關系司機和售票員之間的同步關系 司機只有在售票員關車門后，才能啟動汽車。 售票員只有在司機到站停車后，才能開車門。第二章 進 程 管 理 解： Semaphore close=0，stop=0； driver( ) /*司機*/while(True) P(close);啟動車輛;正常行車;到站停車;V(stop);第二章 進 程 管 理 Conductor( )/*售票員*/while(True)關車門;V(close);

52、售票;P(stop);開車門;上下乘客;Main( ) parbegin(driver,conductor);第二章 進 程 管 理 2.4 經典進程的同步問題經典進程的同步問題 2.4.1 生產者生產者消費者問題消費者問題 前面我們已經對生產者消費者問題(The proceducer-consumer problem)做了一些描述，但未考慮進程的互斥與同步問題，因而造成了數據Counter的不定性。由于生產者消費者問題是相互合作的進程關系的一種抽象，例如， 在輸入時，輸入進程是生產者，計算進程是消費者；而在輸出時，則計算進程是生產者，而打印進程是消費者， 因此，該問題有很大的代表性及實用價值

53、。 第二章 進 程 管 理 1. 利用記錄型信號量解決生產者利用記錄型信號量解決生產者消費者問題消費者問題 假定在生產者和消費者之間的公用緩沖池中，具有n個緩沖區，這時可利用互斥信號量mutex實現諸進程對緩沖池的互斥使用；利用信號量empty和full分別表示緩沖池中空緩沖區和滿緩沖區的數量。又假定這些生產者和消費者相互等效，只要緩沖池未滿，生產者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產者消費者問題可描述如下： 第二章 進 程 管 理 Var mutex, empty, full:semaphore =1,n,0; buffer:array0, , n-

54、1 of item; in, out: integer =0, 0; begin parbegin proceducer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in) =nextp; in =(in+1) mod n; signal(mutex); signal(full); until false; end 第二章 進 程 管 理 consumer:begin repeat wait(full); wait(mutex); nextc =buffer(out); out =(out+1) m

55、od n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end 第二章 進 程 管 理 在生產者消費者問題中應注意：首先，在每個程序中用于實現互斥的wait(mutex)和signal(mutex)必須成對地出現； 其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現，但它們分別處于不同的程序中。例如，wait(empty)在計算進程中，而signal(empty)則在打印進程中，計算進程若因執行wait(empty)而阻塞， 則以后將由打印

56、進程將它喚醒；最后，在每個程序中的多個wait操作順序不能顛倒。應先執行對資源信號量的wait操作，然后再執行對互斥信號量的wait操作，否則可能引起進程死鎖。第二章 進 程 管 理 2. 利用利用AND信號量解決生產者信號量解決生產者消費者問題消費者問題 Var mutex, empty, full:semaphore =1, n, 0; buffer:array0, , n-1 of item; in out:integer =0, 0; begin parbegin producer:begin repeat produce an item in nextp; Swait(empty,

57、mutex); buffer(in) =nextp; in =(in+1)mod n; Ssignal(mutex, full); until false; end第二章 進 程 管 理 consumer:begin repeat Swait(full, mutex); nextc =buffer(out); out =(out+1) mod n; Ssignal(mutex, empty); consumer the item in nextc; until false; end parend end 第二章 進 程 管 理 第二章 進 程 管 理 假定系統有3個并發進程get 、copy

58、和put共享緩沖器B1和B2。進程get負責從輸入設備上讀信息，每讀出一條記錄后放到B1中。進程copy從緩沖器B1中取出一條記錄拷貝后存入B2。進程put取出B2中的記錄打印輸出。B1和B2每次只能存放一條記錄。要求3個進程協調完成任務，使打印出來的與讀入的記錄個數、次序完全一樣。請用記錄型信號量寫出并發程序。第二章 進 程 管 理 解：解： 設置4個信號量，其中empty1對應空閑的緩沖區1，其初值為1；full1對應緩沖區1中的記錄，其初值為0； empty2對應空閑的緩沖區2，其初值為1；full2對應緩沖區2中的記錄，其初值為0。相應進程描述為：get( )while(1)從輸入設備

59、讀入一條記錄;P(empty1);將記錄存入緩沖區1；V(full1);第二章 進 程 管 理 copy( )while(1)P(full1);從緩沖區1中取出一條記錄;V(empty1);P(empty2);將取出的記錄存入緩沖區2 ；V(full2);第二章 進 程 管 理 put( )while(1) P(full2);從緩沖區2中取出一條記錄; V(empty2);將取出的記錄打印出來； Main( ) parbegin(get,copy,put);第二章 進 程 管 理 水果問題水果問題 桌上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果。爸爸專向盤中放蘋果，媽媽專向盤中

60、放橘子；兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果。請用P、V操作實現爸爸、媽媽、兒子、女兒之間的同步與互斥關系。第二章 進 程 管 理 水果問題水果問題 桌上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放橘子；兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果。請用P、V操作實現爸爸、媽媽、兒子、女兒之間的同步與互斥關系。 答：設置信號量empty表示還可以向盤中放幾個水果，其初值為2；apple對應已放入盤中的蘋果，orange對應已放入盤中的橘子，它們的初值均為0；mutex用來實現對盤子的互斥訪問（包括放和取），其初值為1。第二章 進 程