chapter-2-進程的描述與控制解析課件

1、2022/10/101內容概述進程管理的主要功能是把處理機分配給進程,并對處理器運行進行有效地控制和管理,以及協(xié)調各個進程之間的相互關系。2.1 前驅圖和程序執(zhí)行 2.2 進程的描述2.3 進程控制2.4 進程同步2.5 經(jīng)典進程的同步問題2.6 進程通信2.7 線程的基本概念2.8 線程的實現(xiàn)2022/10/91內容概述進程管理的主要功能是把處理機分配2022/10/1022.1 前驅圖和程序執(zhí)行2.1.1 前趨圖2.1.2 程序順序執(zhí)行2.1.3 程序并發(fā)執(zhí)行2022/10/922.1 前驅圖和程序執(zhí)行2.1.1 前趨2022/10/1032.1.1 前趨圖前趨圖是一個有向無循環(huán)圖，記為D

2、AG。用于描述進程之間執(zhí)行的前后關系。圖中的每個結點可用于描述一個程序段或進程，乃至一條語句；結點間的有向邊則用于表示兩個結點之間存在的偏序或前趨關系“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj：稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。把沒有前趨的結點稱為初始結點(Initial Node)，把沒有后繼的結點稱為終止結點(Final Node)。2022/10/932.1.1 前趨圖前趨圖是一個有向無循環(huán)2022/10/104 每個結點還具有一個重量(Weight)，用于表示該結點所含有的

3、程序量或結點的執(zhí)行時間。 圖2-1 前趨圖 直接前趨直接后繼初始結點終止結點2022/10/94 每個結點還具有一個重量(W2022/10/105對于圖 2-1(a)所示的前趨圖,存在下述前趨關系P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示為: 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,

4、P9) 應當注意,前趨圖中必須不存在循環(huán),但在圖2-1(b)中卻有著下述的前趨關系: S2S3, S3S2 2022/10/95對于圖 2-1(a)所示的前趨圖,存在下2022/10/1062.1 進程的基本概念2.1.1 前趨圖2.1.2 程序順序執(zhí)行2.1.3 程序并發(fā)執(zhí)行2022/10/962.1 進程的基本概念2.1.1 前趨圖2022/10/107圖2-2 程序的順序執(zhí)行 1.程序的順序執(zhí)行僅當前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后進行計算，最后才能打印計算結果。 S1: a:=x+y; S2: b:=a-5; S3: c:

5、=b+1;2.1.2 程序順序執(zhí)行2022/10/97圖2-2 程序的順序執(zhí)行 1.程序的順序2022/10/1082.程序順序執(zhí)行時的特征(1)順序性:處理機的操作嚴格按照程序所規(guī)定的順序執(zhí)行,只有當上一個操作完成后,下一個操作才能執(zhí)行。(2)封閉性:程序運行在一個封閉的環(huán)境中,即程序運行時獨占系統(tǒng)的全部資源,這些資源的狀態(tài)只能因程序的執(zhí)行而改變,不受任何外界因素的影響。(3)可再現(xiàn)性:由于程序順序執(zhí)行的封閉性,只要程序順序執(zhí)行的初始條件和環(huán)境相同,則不論何時執(zhí)行,也不論程序執(zhí)行期間是否存在停頓,程序所得的結果也相同。結論:正由于程序順序執(zhí)行的特點,程序員可以檢測和重現(xiàn)程序的錯誤,可以調試和

6、校正程序。2022/10/982.程序順序執(zhí)行時的特征(1)順序性:處2022/10/1092.1 進程的基本概念2.1.1 前趨圖2.1.2 程序順序執(zhí)行2.1.3 程序并發(fā)執(zhí)行2022/10/992.1 進程的基本概念2.1.1 前趨圖2022/10/10102.1.3 程序并發(fā)執(zhí)行1.程序的并發(fā)執(zhí)行 圖2-3 并發(fā)執(zhí)行時的前趨圖 并發(fā)輸入程序I計算程序C輸出程序P2022/10/9102.1.3 程序并發(fā)執(zhí)行1.程序的并發(fā)2022/10/1011下述四條語句的程序段: S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 圖2-4 四條語句的前趨關系什么

7、樣的程序可以并發(fā)執(zhí)行？2022/10/911下述四條語句的程序段:圖2-4 四條2022/10/10122.程序并發(fā)執(zhí)行時的特征 (1)間斷性 相互制約導致并發(fā)程序具有“執(zhí)行-暫停-執(zhí)行”的間斷性活動規(guī)律。(2)失去封閉性 系統(tǒng)中多道程序共享資源，資源的狀態(tài)由多個程序來改變，必然失去了程序的封閉性。(3)不可再現(xiàn)性 失去封閉性失去可再現(xiàn)性，外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復特征。2022/10/9122.程序并發(fā)執(zhí)行時的特征 (1)間斷性例如,有兩個程序A和B,它們共享一個變量N(初始值為x)。 A: N:=N+1 B: Print(N); N:=0; 程序A和B并發(fā)執(zhí)行，

8、可出現(xiàn)以下三種情況: (1)N:=N+1在Print(N)和N:=0之前,此時得到的N值分別為x+1, x+1, 0。 (2)N:=N+1在Print(N)和N:=0之后,此時得到的N值分別為x, 0, 1。 (3)N:=N+1在Print(N)和N:=0之間,此時得到的N值分別為x, x+1, 0。 2022/10/1013例如,有兩個程序A和B,它們共享一個變量N(初始值為x)。22022/10/10142.2 進程的描述2.2.1 進程的定義和特征2.2.2 進程的基本狀態(tài)及轉換2.2.3 掛起狀態(tài)和進程狀態(tài)的轉換2.2.4 進程管理中的數(shù)據(jù)結構2022/10/9142.2 進程的描述2

9、.2.1 進程的定2022/10/10151.進程的定義進程是進程實體的運行過程,是系統(tǒng)進行資源分配和調度的一個獨立單位。2.進程實體的構成(1)程序(段)：進程要進行的操作。(2)數(shù)據(jù)段：包括操作的數(shù)據(jù)和程序自己的變量。(3)進程控制塊PCB(Process Control Block)：存放進程標識符、進程運行的當前狀態(tài)、程序和數(shù)據(jù)的地址、程序運行時的CPU環(huán)境等。2.2.1 進程的定義和特征 2022/10/9152.2.1 進程的定義和特征 2022/10/10162.2.1 進程的定義和特征 2.進程的特征 動態(tài)性：進程是一個動態(tài)的概念，實質上是程序的一次執(zhí)行過程。進程具有生命期：它

10、因“創(chuàng)建”而產(chǎn)生，因“調度”而執(zhí)行，執(zhí)行時還走走停停，因“撤消”而滅亡。并發(fā)性：多個進程實體同存于內存中,且能在一段時間內同時運行,共享系統(tǒng)資源;引入進程實體的目的就是并發(fā)執(zhí)行。獨立性：進程是一個能獨立運行的基本單位，也是系統(tǒng)進行資源分配和調度的基本單位。異步性：各進程按各自獨立的、不可預知的速度向前推進。2022/10/9162.2.1 進程的定義和特征 2.進程3.進程與程序的區(qū)別進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合，它可以復制；進程是程序在數(shù)據(jù)集上的一次執(zhí)行。進程是暫時的,程序是永久的：進程是一個狀態(tài)變化的過程，有它的撤銷，程序可長久保存。進程具有結構特征：由程序段、數(shù)據(jù)段和

11、進程控制塊三者組成，而程序僅是指令的有序集合,是進程的組成部分之一。進程與程序的對應關系：通過多次執(zhí)行，一個程序可對應多個進程。2022/10/10172.2.1 進程的定義和特征 3.進程與程序的區(qū)別進程是動態(tài)的，程序是靜態(tài)的：程序是有序代2022/10/10182.2 進程的描述2.2.1 進程的定義和特征2.2.2 進程的基本狀態(tài)及轉換2.2.3 掛起狀態(tài)和進程狀態(tài)的轉換（略）2.2.4 進程管理中的數(shù)據(jù)結構2022/10/9182.2 進程的描述2.2.1 進程的定2022/10/10191.進程的三種基本狀態(tài)就緒(Ready)狀態(tài)：進程已獲得除處理機外的所需資源，等待分配處理機資源；

12、只要分配CPU就可執(zhí)行。執(zhí)行(Running)狀態(tài)：處于就緒狀態(tài)的進程一旦獲得了處理機，進程狀態(tài)就處于執(zhí)行狀態(tài)。阻塞(Blocked)狀態(tài)(“等待”或“睡眠”)：由于進程等待某種事件(如I/O操作或進程同步)，在事件發(fā)生之前無法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機分配給該進程,也無法運行。如:請求I/O操作，申請緩沖空間等。2.2.2 進程的基本狀態(tài)及轉換 2022/10/9191.進程的三種基本狀態(tài)2.2.2 進程2022/10/1020圖2-5 進程的三種基本狀態(tài)及其轉換 1.時間片用完2.有優(yōu)先級高的進程到來終止2.進程的三種基本狀態(tài)的轉換2022/10/920圖2-5 進程的三種基本狀態(tài)

13、及其轉換 3.創(chuàng)建狀態(tài)和終止狀態(tài) 創(chuàng)建狀態(tài)：當一個新進程剛剛建立,還未將其放入就緒隊列時的狀態(tài)，稱為新狀態(tài)。 終止狀態(tài)：當一個進程已經(jīng)正常結束或異常結束，操作系統(tǒng)已將其從系統(tǒng)隊列中移出，但尚未撤消，這時稱為終止狀態(tài)。 2022/10/10213.創(chuàng)建狀態(tài)和終止狀態(tài) 創(chuàng)建狀態(tài)：當一個新進程剛剛建立,還未2022/10/1022圖2-6 進程的五種基本狀態(tài)及其轉換 釋放2022/10/922圖2-6 進程的五種基本狀態(tài)及其轉換 2022/10/10232.2 進程的描述2.2.1 進程的定義和特征2.2.2 進程的基本狀態(tài)及轉換2.2.3 掛起狀態(tài)和進程狀態(tài)的轉換2.2.4 進程管理中的數(shù)據(jù)結構2

14、022/10/9232.2 進程的描述2.2.1 進程的定2022/10/1024掛起操作的引入終端用戶的請求父進程請求負荷調節(jié)的需要操作系統(tǒng)的需要2.2.3 掛起操作和進程狀態(tài)的轉換圖2-7 具有掛起狀態(tài)的進程狀態(tài)圖 2022/10/924掛起操作的引入2.2.3 掛起操作和進2022/10/10252.2 進程的描述2.2.1 進程的定義和特征2.2.2 進程的基本狀態(tài)及轉換2.2.3 掛起狀態(tài)和進程狀態(tài)的轉換2.2.4 進程管理中的數(shù)據(jù)結構2022/10/9252.2 進程的描述2.2.1 進程的定2022/10/10262.2.4 進程管理中的數(shù)據(jù)結構 1.操作系統(tǒng)中用于管理控制的數(shù)據(jù)

15、結構 對于每個資源和每個進程都設置了一個數(shù)據(jù)結構。資源信息表、進程信息表（稱為PCB）2022/10/9262.2.4 進程管理中的數(shù)據(jù)結構 1.2022/10/10272.2.4 進程管理中的數(shù)據(jù)結構 2.進程控制塊的作用 進程控制塊的作用是使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù))，成為一個能獨立運行的基本單位，一個能與其它進程并發(fā)執(zhí)行的進程?；蛘哒f，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。 記錄了操作系統(tǒng)所需的,用于描述進程情況及控制進程運行所需的全部信息。 PCB是進程存在的唯一標志。2022/10/9272.2.4 進程管理中的數(shù)據(jù)結構 2.2022/10/102

16、82.2.4 進程管理中的數(shù)據(jù)結構 2.進程控制塊的作用 具體作用：作為獨立運行基本單位的標志能實現(xiàn)間斷性運行方式提供進程管理所需的信息提供進程調度所需的信息實現(xiàn)與其它進程的同步與通信2022/10/9282.2.4 進程管理中的數(shù)據(jù)結構 2.2022/10/10293.進程控制塊中的信息 進程標識符 內部標識符和外部標識符。 處理機狀態(tài)通用寄存器指令計數(shù)器PC程序狀態(tài)字PSW用戶棧指針 進程調度信息進程狀態(tài)進程優(yōu)先級進程調度所需的其它信息事件進程控制信息程序和數(shù)據(jù)的地址進程同步和通信機制資源清單鏈接指針struct pcb int id; /進程序號 int ra; /所需資源A的數(shù)量 in

17、t rb; /所需資源B的數(shù)量 int rc; /所需資源C的數(shù)量 int ntime; /所需的時間片個數(shù) int rtime; /已經(jīng)運行的時間片個數(shù) char state; /進程狀態(tài) struct pcb *next; 2022/10/9293.進程控制塊中的信息 進程標識符進2022/10/1030圖2-11 PCB鏈接隊列示意圖 4.進程控制塊的組織方式(1)線性方式(2)鏈接方式 (3)索引方式2022/10/930圖2-11 PCB鏈接隊列示意圖 4.2022/10/1031圖2-12 按索引方式組織PCB 4.進程控制塊的組織方式(1)線性方式(2)鏈接方式 (3)索引方式2

18、022/10/931圖2-12 按索引方式組織PCB 4.內容概述2022/10/10322.1 前驅圖和程序執(zhí)行 2.2 進程的描述2.3 進程控制2.4 進程同步2.5 經(jīng)典進程的同步問題2.6 進程通信2.7 線程的基本概念2.8 線程的實現(xiàn)內容概述2022/10/9322.1 前驅圖和程序執(zhí)行 2.3 進 程 控 制主要內容操作系統(tǒng)內核進程的創(chuàng)建進程的終止進程的阻塞與喚醒進程的掛起與激活2.3 進 程 控 制主要內容操作系統(tǒng)內核問題：現(xiàn)代操作系統(tǒng)中通常將一些與硬件緊密相關的模塊，各種常用的設備的驅動程序以及運行頻率較高的模塊都安排在緊靠硬件的軟件層次中，將它們常駐內存，即OS內核。為什

19、么這樣做？便于對這些軟件進行保護提高OS的運行效率操作系統(tǒng)內核問題：現(xiàn)代操作系統(tǒng)中通常將一些與硬件緊密相關的模操作系統(tǒng)內核1.處理機執(zhí)行狀態(tài)：系統(tǒng)態(tài)和用戶態(tài)處理機的執(zhí)行狀態(tài)分系統(tǒng)態(tài)和用戶態(tài)兩種:系統(tǒng)態(tài)(管態(tài)、核心態(tài))：有較高特權，能執(zhí)行一切指令，訪問所有寄存器和存儲區(qū)。用戶態(tài)(目態(tài))：有較低特權，能執(zhí)行規(guī)定指令，訪問指定寄存器和存儲區(qū)。用戶程序運行在用戶態(tài)，不能執(zhí)行OS指令及區(qū)域。OS內核運行在系統(tǒng)態(tài)，進程控制是由OS內核實現(xiàn)的。操作系統(tǒng)內核1.處理機執(zhí)行狀態(tài)：系統(tǒng)態(tài)和用戶態(tài)用戶程序運行在操作系統(tǒng)內核2.支撐功能 中斷處理 時鐘管理 原語操作由若干條指令構成的“原子操作”過程，在執(zhí)行期間不可中

20、斷，作為一個整體而不可分割。原子操作：一個操作中的所有動作要么全做，要么全不做。原子操作在管態(tài)下執(zhí)行，常駐內存。原語的作用是為了實現(xiàn)進程的通信和控制。思考：進程控制有哪些原語操作？1.創(chuàng)建原語2.撤消原語3.阻塞原語4.喚醒原語5.掛起原語6.激活原語操作系統(tǒng)內核2.支撐功能由若干條指令構成的“原子操作”過程，操作系統(tǒng)內核3.資源管理功能進程管理存儲器管理 設備管理操作系統(tǒng)內核3.資源管理功能2022/10/1038進程的創(chuàng)建圖2-13 進程樹 1.進程的層次結構父進程與子進程UNIX中進程家族Windows中進程句柄 2.進程圖(Process Graph)進程圖是用于描述一個進程的家族關系

21、的有向樹，樹中的結點表示進程。子進程可以繼承父進程的資源。撤消父進程時必須同時撤消子進程2022/10/938進程的創(chuàng)建圖2-13 進程樹 1.進程2022/10/10393.引起創(chuàng)建進程的事件用戶登錄作業(yè)調度提供服務應用請求 進程的創(chuàng)建2022/10/9393.引起創(chuàng)建進程的事件進程的創(chuàng)建2022/10/10404.進程的創(chuàng)建申請空白PCB 為新進程分配資源 初始化進程控制塊 將新進程插入就緒隊列進程的創(chuàng)建2022/10/9404.進程的創(chuàng)建進程的創(chuàng)建2022/10/1041進程的終止 1.引起進程終止的事件正常結束異常結束外界干預2022/10/941進程的終止 1.引起進程終止的事件20

22、22/10/10422.進程的終止過程 (1)從PCB集合中檢索出該進程的PCB, 讀出該進程的狀態(tài)。 (2)若被終止進程正處于執(zhí)行狀態(tài),應立即終止該進程的執(zhí)行。 (3)若該進程還有子孫進程,應將其所有子孫進程予以終止。 (4)將被終止進程所擁有的全部資源, 歸還給其父進程, 或者歸還給系統(tǒng)。 (5)將被終止進程(它的PCB)從所在隊列(或鏈表)中移出,等待其他程序來搜集信息。 進程的終止 2022/10/9422.進程的終止過程進程的終止 2022/10/1043進程的阻塞與喚醒1.引起進程阻塞和喚醒的事件 請求系統(tǒng)服務 啟動某種操作 新數(shù)據(jù)尚未到達 無新工作可做2022/10/943進程的

23、阻塞與喚醒1.引起進程阻塞和喚醒2022/10/1044 2.進程阻塞過程進程調用阻塞原語block()把自己阻塞，立即停止執(zhí)行，把進程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊列。將本進程插入到具有相同事件的阻塞(等待)隊列。調度程序進行重新調度,將處理機分配給另一就緒進程，并進行切換，亦即，保留被阻塞進程的處理機狀態(tài)(在PCB中)，再按新進程的PCB中的處理機狀態(tài)設置CPU的環(huán)境。進程的阻塞與喚醒2022/10/944 2.進程阻塞過程進程的阻塞與喚醒2022/10/1045 3.進程喚醒過程調用喚醒原語wakeup( )將等待該事件的進程喚醒。喚醒原語執(zhí)行的過程是把被阻塞

24、的進程從等待該事件的阻塞隊列中移出將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒將該PCB插入到就緒隊列中進程的阻塞與喚醒2022/10/945 3.進程喚醒過程進程的阻塞與喚醒2022/10/1046進程的掛起與激活 1.進程的掛起系統(tǒng)將利用掛起原語suspend( )將指定進程或處于阻塞狀態(tài)的進程掛起。suspend()原語的執(zhí)行過程首先檢查被掛起進程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進程，則將之改為靜止阻塞。把該進程的PCB復制到某指定的內存區(qū)域。若被掛起的進程正在執(zhí)行,則轉向調度程序重新調度。2022/10/946進程的掛起與激活 1.進程的掛起2022/10/1

25、047 2.進程的激活過程系統(tǒng)將利用激活原語active( )將指定進程激活。active()原語執(zhí)行過程將進程從外存調入內存，檢查該進程的現(xiàn)行狀態(tài)，若是靜止就緒，將之改為活動就緒；若為靜止阻塞便將之改為活動阻塞。假如采用的是搶占調度策略，則每當有新進程進入就緒隊列時，應檢查是否要進行重新調度，即由調度程序將被激活進程與當前進程進行優(yōu)先級的比較，如果被激活進程的優(yōu)先級更低，就不必重新調度；否則，立即剝奪當前進程的運行，把處理機分配給剛被激活的進程。進程的掛起與激活 2022/10/947 2.進程的激活過程進程的掛起與激活2022/10/10481.引起進程創(chuàng)建的主要事件？2.在創(chuàng)建一個進程時

26、所需要完成的主要工作是什么？3.在撤消一個進程時所要完成的主要工作是什么？課后思考題 2022/10/9481.引起進程創(chuàng)建的主要事件？課后思考題內容概述2022/10/10492.1 前驅圖和程序執(zhí)行 2.2 進程的描述2.3 進程控制2.4 進程同步2.5 經(jīng)典進程的同步問題2.6 進程通信2.7 線程的基本概念2.8 線程的實現(xiàn)內容概述2022/10/9492.1 前驅圖和程序執(zhí)行 2.4 進程同步 進程同步的主要任務是對多個相關進程在執(zhí)行次序上進行協(xié)調，以使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。2.4.1 進程同步的基本概念2.4.2 硬件同步機

27、制2.4.3 信號量機制2.4.4 信號量的應用2.4.5 管程機制2022/10/10502.4 進程同步 進程同步的主要任務是對多個相關進程在執(zhí)行2022/10/10512.4.1 進程同步的基本概念1.兩種形式的制約關系(1)間接相互制約關系 源于資源共享。如A、B共享打印機，若A申請打印時，打印機已分配給B，則A只能阻塞，等B釋放后再改為就緒，又稱為“互斥”。(2)直接相互制約關系 源于進程之間的合作關系。如進程A向B提供數(shù)據(jù)，當輸入緩沖空時，B不能得到數(shù)據(jù)而阻塞；反之當緩沖滿時，A無法寫入而阻塞，又稱為“同步”。2022/10/9512.4.1 進程同步的基本概念1.兩種2.臨界資源

28、定義:在一段時間內只允許一個進程訪問的資源。例如:打印機、磁帶機、卡片輸入機、變量、表格、數(shù)據(jù)、 指針、數(shù)組等。進程之間采取互斥方式實現(xiàn)對這些資源的共享。2022/10/1052例子： 生產(chǎn)者-消費者(producer-consumer)問題是一個著名的進程同步問題。有一群生產(chǎn)者進程在生產(chǎn)產(chǎn)品，提供給消費者進程去消費。不能向滿緩沖區(qū)投放產(chǎn)品，不能從空緩沖區(qū)中取產(chǎn)品。2.4.1 進程同步的基本概念2.臨界資源2022/10/952例子：2.4.1 進程同步2022/10/1053 一個數(shù)組緩沖池，有n個緩沖區(qū)。 buffer:array0, 1, , n-1 of item 輸入指針in in=

29、(in+1)mod n。 輸出指針out out=(out+1) mod n。 counter：初始值為0, 緩沖池中含有的產(chǎn)品數(shù)目。0 1 n-1 ninout 2022/10/953 一個數(shù)組緩沖池，有n個緩沖區(qū)。0 2022/10/1054producer: repeat 生產(chǎn)者進程 produce an item in nextp;/生產(chǎn)一個產(chǎn)品 while counter=n do no-op; bufferin =nextp;/將產(chǎn)品放入緩沖區(qū)內 in =in+1 mod n; counter =counter+1; /緩沖池中產(chǎn)品數(shù)加一 until false;consumer:

30、 repeat 消費者進程 while counter=0 do no-op; nextc =bufferout;/從緩沖區(qū)中消費產(chǎn)品 out =(out+1) mod n; counter = counter-1; /緩沖池中產(chǎn)品數(shù)減一 consumer the item in nextc;/消費一個產(chǎn)品 until false; 2022/10/954producer: repeat 生2022/10/1055 雖然上面的生產(chǎn)者程序和消費者程序，在分別看時都是正確的，而且兩者在順序執(zhí)行時其結果也會是正確的，但若并發(fā)執(zhí)行時，就會出現(xiàn)差錯，問題就在于這兩個進程共享變量counter。生產(chǎn)者對它

31、做加1操作，消費者對它做減1操作，這兩個操作在用機器語言實現(xiàn)時， ?？捎孟旅娴男问矫枋觯簉egister1=counter; register2=counter;register1=register1+1; register2=register2-1;counter=register1; counter=register2; 2022/10/955 雖然上面的生產(chǎn)者程序和2022/10/1056 假設：counter的當前值是5。如果生產(chǎn)者進程先執(zhí)行左列的三條機器語言語句，然后消費者進程再執(zhí)行右列的三條語句，則最后共享變量counter的值仍為5；反之，如果讓消費者進程先執(zhí)行右列的三條語句，然

32、后再讓生產(chǎn)者進程執(zhí)行左列的三條語句，counter值也還是5，但是，如果按下述順序執(zhí)行，counter值是4。由于并發(fā)執(zhí)行而失去封閉性。register1=counter; (register1=5)register1=register1+1; (register1=6)register2=counter; (register2=5)register2=register2-1; (register2=4)counter=register1; (counter=6)counter=register2; (counter=4) 共享資源的訪問互斥2022/10/956 假設：counter的當3.

33、臨界區(qū)不論是硬件臨界資源還是軟件臨界資源，多個進程必須互斥地對它進行訪問。在每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。每個進程進入臨界區(qū)之前應先對欲訪問的臨界資源進行檢查，看是否正在被訪問。如果此刻該臨界資源未被訪問，該進程可進入臨界區(qū),并設置它正在被訪問的標志，在臨界區(qū)之前執(zhí)行的這段代碼稱為進入?yún)^(qū)。在臨界區(qū)后面也要加上一段代碼，用于將臨界區(qū)被訪問的資源恢復為未被訪問的標志，稱為退出區(qū)。2022/10/10573.臨界區(qū)不論是硬件臨界資源還是軟件臨界資源，多個進程必須互2022/10/1058可把一個訪問臨界資源的循環(huán)進程描述如下:repeat critical section;臨界區(qū) re

34、mainder section;剩余區(qū)until false; entry sectionexit section進入?yún)^(qū)退出區(qū)2022/10/958可把一個訪問臨界資源的循環(huán)進程描述如下2022/10/10594.同步機制應遵循的規(guī)則(1)空閑讓進：當無進程處于臨界區(qū)時,應允許一個進程進入臨界區(qū),以有效利用臨界資源。(2)忙則等待：當有進程進入臨界區(qū)時,其他進程必須等待。(3)有限等待：對要求訪問臨界資源的進程,應保證在有限時間內進入自己的臨界區(qū),防止“死等”。(4)讓權等待：當進程不能進入其臨界區(qū)時,應立即釋放處理機,防止“忙等”,不能一直用語句判斷能不能進,占用處理機。2022/10/95

35、94.同步機制應遵循的規(guī)則2.4.2 硬件同步機制采用軟件方法實現(xiàn)進程互斥使用臨界資源是很困難的，它們通常能實現(xiàn)兩個進程的互斥，很難控制多個進程的互斥。算法設計需要非常小心，否則可能出現(xiàn)死鎖，或互斥失敗等嚴重問題。軟件方法始終不能解決“忙等”現(xiàn)象，降低系統(tǒng)效率。硬件方法包括屏蔽中斷和專用機器指令。2.4.2 硬件同步機制2.4.2 硬件同步機制-屏蔽中斷由于進程切換需要依賴中斷來實現(xiàn)，如果屏蔽中斷，則不會出現(xiàn)進程切換。因此，為了實現(xiàn)對臨界資源的互斥使用，可以在進程進入臨界區(qū)之前，屏蔽中斷,當進程退出臨界區(qū)時，打開系統(tǒng)中斷。中斷被屏蔽以后，系統(tǒng)時鐘中斷也被屏蔽。處理機將不會被切換到其他進程。于是

36、，一旦屏蔽中斷，進程就可以檢查和修改共享內存區(qū)中的數(shù)據(jù)，而不必擔心其他進程介入。其偽代碼如下： 2.4.2 硬件同步機制-屏蔽中斷由于進程切換需要依賴中斷來2.4.2 硬件同步機制-屏蔽中斷repeat ; ; ; forever.2.4.2 硬件同步機制-屏蔽中斷repeat2.4.2 硬件同步機制-屏蔽中斷這種方法約束條件太強，付出的代價太大因為中斷被屏蔽以后，系統(tǒng)將無法響應任何外部請求，也不會響應當前執(zhí)行進程的任何異常及系統(tǒng)故障，嚴重地降低了處理機性能。這種方法僅對單處理機系統(tǒng)有效，如果系統(tǒng)有兩個或多個共享內存的處理機，屏蔽中斷僅僅對執(zhí)行本指令的處理機有效，其它處理機仍將繼續(xù)運行，并可以

37、訪問共享內存空間。 2.4.2 硬件同步機制-屏蔽中斷這種方法約束條件太強，付出2.4.2 硬件同步機制-專用機器指令利用一些專用機器指令也能實現(xiàn)互斥，機器指令在一個指令周期內執(zhí)行，不會受到其它指令的干擾，也不會被中斷。Test and Set指令就是較常用的一種機器指令，其定義如下： 2.4.2 硬件同步機制-專用機器指令2.4.2 硬件同步機制-專用機器指令TestAndSet指令：這條指令是原子操作，即執(zhí)行該代碼時不允許被中斷。其功能是讀出指定標志后把該標志設置為真。指令的功能描述為：Boolean TestAndSet(Boolean *lock) Boolean old； old=*

38、lock； *lock=true； return old； while TestAndSet(&lock)；進程的臨界區(qū)代碼；lock=false；進程的其他代碼；2.4.2 硬件同步機制-專用機器指令TestAndSet指2.4.2 硬件同步機制-專用機器指令Swap指令：該指令的功能是交換兩個字節(jié)的內容。其功能描述如下。Swap(boolean *a, boolean *b) boolean temp;Temp=*a;*a = *b;*b = temp;2.4.2 硬件同步機制-專用機器指令Swap指令：該指令的2.4.2 硬件同步機制-專用機器指令應為每個臨界資源設置了一個共享布爾變量l

39、ock，初值為false；在每個進程中再設置一個局部布爾變量key，用于與lock交換信息。在進入臨界區(qū)之前先利用Swap指令交換lock與key的內容，然后檢查key的狀態(tài)；有進程在臨界區(qū)時，重復交換和檢查過程，直到進程退出。利用Swap指令實現(xiàn)進程互斥的算法描述如下：key=true;while(key!=false)Swap(&lock, &key); / 進程的臨界區(qū)代碼段；lock=false;/ 進程的其他代碼；2.4.2 硬件同步機制-專用機器指令應為每個臨界資源設置了機器指令優(yōu)點非常簡單，易于證明；同時適合于單處理機系統(tǒng)和共享內存的多處理機系統(tǒng)中多個進程的互斥；可以分別為臨界區(qū)

40、設置屬于它自己的變量，以實現(xiàn)對多個臨界區(qū)的互斥訪問。 機器指令優(yōu)點機器指令缺點 “忙等” 現(xiàn)象仍然存在。進程都需要循環(huán)檢測，等待時機進入臨界區(qū)。但是，由于采用了機器指令，這種“忙等”消耗的機器時間比軟件方法小，屬于“可接受的忙等”?？赡艹霈F(xiàn)饑餓現(xiàn)象。當臨界區(qū)空閑時，執(zhí)行循環(huán)檢測的若干等待進程能進入臨界區(qū)的機率是相等的，有的進程可能“運氣”非常不好，很難有機會進入臨界區(qū)，而饑餓。機器指令缺點 “忙等” 現(xiàn)象仍然存在。進程都需要循環(huán)檢測，等機器指令缺點還有可能導致死鎖。例如，進程P1的優(yōu)先級低于P2的優(yōu)先級，若P1通過執(zhí)行專用機器指令，進入臨界區(qū)，且在臨界區(qū)內被中斷，P2被調度執(zhí)行。若P2也需要進

41、入該臨界區(qū)，由于臨界區(qū)被P1占用，P2 “忙等” 。由于P1的優(yōu)先級低于P2，調度程序不可能強行剝奪P2的執(zhí)行而調度P1。這樣，P1將一直占用臨界區(qū)被中斷，P2一直“忙等”，如果沒有外力的作用，這種“僵持”狀態(tài)將一直保持下去，即系統(tǒng)出現(xiàn)死鎖。 機器指令缺點還有可能導致死鎖。1965年,荷蘭學者Dijkstra提出的信號量(Semaphores)機制是一種有效的進程同步工具，所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)。信號量機制已從整型信號量發(fā)展為記錄型信號量、AND型信號量，又進一步發(fā)展為信號量集。信號量就是OS提供的管理公有資源的有效手段。信

42、號量代表可用資源實體的數(shù)量。物理意義2022/10/10712.4.3 信號量機制 1965年,荷蘭學者Dijkstra提出的信號量(Semap2022/10/10721.整型信號量除初始化外，僅能通過兩個標準的原子操作wait(S)和signal(S)來訪問。也稱為P、V操作。wait和signal操作可描述為:wait(S): while S0 do no-op; S:=S-1;signal(S): S:=S+1; wait(S)和signal(S)是原子操作，因此它們在執(zhí)行時是不可中斷的。另外，信號量只能通過原語操作來訪問，不能被進程調度所打斷。有“忙等”現(xiàn)象。2022/10/9721.

43、整型信號量2022/10/1073可把一個訪問臨界資源的循環(huán)進程描述如下:repeat critical section; 臨界區(qū) remainder section; 剩余區(qū)until false; entry sectionexit sectionP(S)或wait(S);V(S)或signal(S);進入?yún)^(qū)退出區(qū)1.整型信號量2022/10/973可把一個訪問臨界資源的循環(huán)進程描述如下2022/10/10742.記錄型信號量記錄型信號量（也稱資源信號量）機制，則是一種不存在“忙等”現(xiàn)象的進程同步機制，它采用了記錄型的數(shù)據(jù)結構。在采取了“讓權等待”的策略后，又會出現(xiàn)多個進程等待訪問同一臨界

44、資源的情況。為此，在信號量機制中，除了需要一個用于代表資源數(shù)目的整型變量value外，還應增加一個進程鏈表L，用于鏈接上述的所有等待進程。2022/10/9742.記錄型信號量2022/10/1075type semaphore=record value: integer; /資源數(shù)目 L: list of process;/進程鏈表指針 endprocedure wait(S) var S: semaphore; begin S.value:=S.value-1; if S.value0 then block(S.L); end procedure signal(S) var S: sema

45、phore; begin S.value:=S.value+1; if S.value0 then wakeup(S.L); end 請求一個單位的該類資源該類資源數(shù)減少一個自我阻塞，放棄處理機釋放一個單位資源該類資源增加一個喚醒進程2022/10/975type semaphore=reco2022/10/10763.AND型信號量 在有些任務中,一個進程先要獲得多個共享資源后才能執(zhí)行，若進程A和B都要申請D和E兩種資源，設信號量Dmutex和Emutex的初值均為1在兩個進程中都要包含兩個對Dmutex和Emutex的操作，即process A: process B: P(Dmutex);

46、 P(Emutex); P(Emutex); P(Dmutex);若進程A和B按下述次序交替執(zhí)行P操作: process A: P(Dmutex); 于是Dmutex=0 process B: P(Emutex); 于是Emutex=0 process A: P(Emutex); 于是Emutex=-1 A阻塞 process B: P(Dmutex); 于是Dmutex=-1 B阻塞 2022/10/9763.AND型信號量 在有些任務2022/10/1077 AND同步機制的基本思想是:將進程在整個運行過程中需要的所有資源,一次性全部地分配給進程,待進程使用完后再一起釋放。只要尚有一個資源

47、未能分配給進程,其它所有可能為之分配的資源,也不分配給他。亦即,對若干個臨界資源的分配,采取原子操作方式:要么全部分配到進程,要么一個也不分配。由死鎖理論可知,這樣就可避免上述死鎖情況的發(fā)生。為此,在P操作中,增加了一個“AND”條件,故稱為AND同步,或稱為同時P操作, 即SP(Simultaneous wait)定義如下: 3.AND型信號量 2022/10/977 AND同步機制的基本思想是:將2022/10/1078SP:Swait(S1, S2, , Sn) if Si1 and and Sn1 then 每個資源都可用 for i: =1 to n do Si:=Si-1; 分配所

48、有資源 endfor else 否則,將進程放到等待資源Si的隊列中 “阻塞”(去第1個Si1的“等待Si”的阻塞隊列中排隊,并置它的程序計數(shù)器于SP操作的起始點) endifSV:Ssignal(S1, S2, , Sn) for i: =1 to n do Si=Si+1; 釋放所有資源 “喚醒”(所有“等待Si”的阻塞進程,置為“就緒”狀態(tài),移到就緒隊列中) endfor; 2022/10/978SP:Swait(S1, S2, ,4.信號量集:一次申請多個資源在記錄型信號量機制中,P(S)和V(S)操作僅能對信號量施以加1或減1操作,意味著每次只能獲得或釋放一個單位的臨界資源,效率較低

49、。在有些情況下,當資源數(shù)量低于某下限值時便不予分配。因而,在每次分配之前,都必須測試該資源的數(shù)量,看其是否大于下限值。在對AND型信號量機制擴充的基礎上,形成一般化的“信號量集”機制。2022/10/10794.信號量集:一次申請多個資源在記錄型信號量機制中,P(S)2022/10/1080SP:Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i:=1 to n do Si:=Si-di; 一次分配d個資源 endfor else “阻塞”(去第1個Sinextp; P(empty); empty減1 P(mutex)

50、; buffer(in):=nextp; in:=(in+1)mod n; 移動生產(chǎn)指針 V(mutex); V(full); full增1 until false; end consumer: 消費者進程 begin repeat P(full); P(mutex); nextc: =buffer(out); out:=(out+1) mod n; V(mutex); V(empty); 消費nextc中的一條消息; until false; end parendend 2022/10/994Var mutex, empty, f2022/10/1095在生產(chǎn)者消費者問題中要注意以下幾點：在

51、每個程序中用于實現(xiàn)互斥的P(mutex)和V(mutex)必須成對地出現(xiàn)；對資源信號量empty和full的P和V操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如,P(empty)在計算進程中,而V(empty)則在打印進程中,計算進程若因執(zhí)行P(empty)而阻塞, 則以后將由打印進程將它喚醒；在每個程序中的多個P操作順序不能顛倒。應先執(zhí)行對資源信號量的P操作，然后再執(zhí)行對互斥信號量的P操作，否則可能引起進程死鎖。2022/10/995在生產(chǎn)者消費者問題中要注意以下幾點：2022/10/10962.利用AND信號量解決生產(chǎn)者消費者問題 Var mutex, empty, full:

52、semaphore:=1, n, 0; buffer:array0, , n-1 of item; in out:integer:=0, 0; begin parbegin producer: begin repeat 生產(chǎn)一條消息=nextp; SP(empty, mutex); buffer(in):=nextp; in:=(in+1)mod n; SV(mutex, full); until false; end consumer: begin repeat SP(full, mutex); nextc:=buffer(out); out:=(out+1) mod n; SV(mutex

53、, empty); 消費nextc中的一條消息; until false; end parendend2022/10/9962.利用AND信號量解決生產(chǎn)者消費者2.5 經(jīng)典進程的同步問題 2.5.1 生產(chǎn)者消費者問題2.5.2 哲學家進餐問題2.5.3 讀者寫者問題2022/10/10972.5 經(jīng)典進程的同步問題 2.5.1 生產(chǎn)者消費者問題2.5.2 哲學家進餐問題 哲學家進餐問題(The Dinning Philosophers Problem)是由Dijkstra提出并解決的典型進程同步問題。 問題描述:5個哲學家坐在桌子邊,桌上有5個碗和5支筷子。哲學家的生活方式交替地進行思考和進餐

54、。哲學家饑餓時便拿起兩邊的筷子進餐,但只有當拿到兩支后才能進餐。用餐畢,放下筷子。2022/10/10982.5.2 哲學家進餐問題 哲學家進餐問題(Th2022/10/10991.利用記錄型信號量解決哲學家進餐問題 經(jīng)分析可知,放在桌子上的筷子是臨界資源,在一段時間內只允許一位哲學家使用。為了實現(xiàn)對筷子的互斥使用,可以用一個信號量表示一只筷子,由這五個信號量構成信號量數(shù)組。其描述如下:2022/10/9991.利用記錄型信號量解決哲學家進餐問題2022/10/10100Var chopstick: array0, , 4of semaphore:=(1,1,1,1,1);begin repe

55、at P(chopsticki); P(chopstick(i+1) mod 5); eat;進餐 V(chopsticki); V(chopstick(i+1) mod 5); think;思考 until false; end問題: 每個哲學家都拿起左邊的筷子等待右邊的筷子，結果誰也得不到兩把筷子，形成了死鎖。10234104322022/10/9100Var chopstick: arr2022/10/101012.利用AND信號量機制解決哲學家進餐問題 在哲學家進餐問題中,要求每個哲學家先獲得兩個臨界資源(筷子)后方能進餐,這在本質上就是前面所介紹的AND同步問題,故用AND信號量機制

56、可獲得最簡潔的解法。Var chopstick array 0, , 4 of semaphore:=(1,1,1,1,1); process i repeat SP(chopstick(i+1) mod 5, chopsticki); eat; SV(chopstick(i+1) mod 5, chopsticki); think; until false; 2022/10/91012.利用AND信號量機制解決哲學家進2.5 經(jīng)典進程的同步問題 2.5.1 生產(chǎn)者消費者問題2.5.2 哲學家進餐問題2.5.3 讀者寫者問題2022/10/101022.5 經(jīng)典進程的同步問題 2.5.1 生產(chǎn)

57、者消費者問題2.5.3 讀者-寫者問題 一個數(shù)據(jù)文件或記錄可被多個進程共享，把只要求讀該文件的進程稱為“Reader進程”，其他進程稱為“Writer進程”允許多個進程同時讀一個共享對象，因為讀不會使數(shù)據(jù)文件混亂。不允許一個Writer進程和其他Reader進程或Writer進程同時訪問一個對象。讀者寫者問題是指保證一個Writer進程必須與其他進程互斥地訪問共享對象的同步問題。2022/10/101032.5.3 讀者-寫者問題 一個數(shù)據(jù)文件或記錄可被多個進程共2022/10/101041.利用記錄型信號量解決讀者-寫者問題設置兩個信號量：讀互斥信號量rmutex和寫互斥信號量wmutex。

58、另外設立一個讀計數(shù)器readcount表示正在讀的進程數(shù)目，它是一個整型變量，初值為0。wmutex：用于實現(xiàn)Reader與Writer進程間在讀或寫時的互斥,初值為1。 rmutex：用于讀者互斥地訪問readcount，初值為1。2022/10/91041.利用記錄型信號量解決讀者-寫者問2022/10/10105讀者-寫者問題可描述如下:Var rmutex, wmutex:semaphore:=1,1; readcount:integer:=0; begin parbegin Reader:begin repeat P(rmutex); if readcount=0 then P(wm

59、utex); readcount:=readcount+1; V(rmutex); perform read operation; P(rmutex); readcount:=readcount-1; if readcount=0 then V(wmutex); V(rmutex); until false; end writer:begin repeat P(wmutex); perform write operation; V(wmutex); until false; end parendend2022/10/9105讀者-寫者問題可描述如下: 2022/10/101062.利用信號量集

60、機制解決讀者-寫者問題 Var RN integer; L, mx:semaphore:=RN,1; begin parbegin reader:begin repeat SP(L,1,1); SP(mx,1,0); perform read operation; SV(L,1); until false; end writer:begin repeat SP(mx,1,1; L,RN,0); perform write operation; SV(mx,1); until false; end parend end 2022/10/91062.利用信號量集機制解決讀者-寫者問進程通信 OS可