1、會計學1操作系統教學操作系統教學02第1頁/共255頁2.1 進程的基本概念進程的基本概念程序和數據程序和數據進程結構進程結構指令流指令流第2頁/共255頁2.1.1 程序的順序執行及其特征程序的順序執行及其特征第3頁/共255頁2.1.1 程序的順序執行及其特征程序的順序執行及其特征第4頁/共255頁2.1.2 前趨圖前趨圖第5頁/共255頁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),

2、 (P7, P9), (P8, P9) 第6頁/共255頁2.1.3 程序的并發執行及其特征程序的并發執行及其特征P1P2P3P4I1I2I3I4C1C2C3C4在該例中存在下述前趨關系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1在Pi-1和Ci以及Ii+1之間，可以并發執行多個程序同時在系統中運行，這些程序的執行在時間上是重疊的，即前一程序的執行尚未結束，后一程序的執行已經開始。第7頁/共255頁2.1.3 程序的并發執行及其特征程序的并發執行及其特征第8頁/共255頁第9頁/共255頁不可再現性的例子：l兩個并發執行的程序A和B，如下所示： A：N:=N+1； B：

3、print（N）； N:=0；l 分析：1）并發：A、B交替占用CPU執行；2）異步性導致：CPU交替執行A、B的語句時順序可能不同！l 設某次循環前，N的值為8, CPU執行順序 打印結果 N的值1)N:=N+1;print(N);N:=0; 9 02)print(N);N:=0;N:=N+1; 8 13)print(N);N:=N+1;N:=0; 8 0第10頁/共255頁第11頁/共255頁第12頁/共255頁引入進程后引入進程后第13頁/共255頁第14頁/共255頁2.1.4 進程的特征與狀態進程的特征與狀態多道程序環境下，如何能使程序并發執行？如何對并發執行的程序加以控制和描述？第

4、15頁/共255頁l 進程和程序的區別很微妙l 想象一位好廚藝的科學家正在為女兒烘制生日蛋糕。有食譜，有原料：面粉、雞蛋、糖、香草汁等等。在這個比喻中，食譜就是程序(即用適當形式描述的算法)，科學家就是處理機(CPU)，各種原料就是輸入數據。進程就是廚師閱讀食譜、取來各種原料、以及烘制蛋糕的一系列動作的總和。第16頁/共255頁l 現在假設科學家的兒子哭著跑了進來，說他被一只蜜蜂螫了。科學家就記錄下他照著食譜做到哪兒了(保存進程的當前狀態)，然后拿出一本急救手冊，按照其中的指示處理螫傷。l 這里，我們看到處理機從一個進程(做蛋糕)切換到另一個高優先級的進程(實施醫療救治)，每個(進程)擁有各自

5、的程序(食譜和急救書)。當蜜蜂螫傷處理完之后，科學家又回來做蛋糕，從他離開時的那一步繼續做下去。l 關鍵思想是：一個進程是某種類型的一個活動，它有程序、輸入、輸出、及狀態。單個處理機被若干進程共享，它使用某種調度算法決定何時停止一個進程的工作，并轉而為另一個進程提供服務。第17頁/共255頁閱讀菜譜閱讀菜譜準備原料準備原料烹制菜肴烹制菜肴飯菜飯菜閱讀洗衣機手冊閱讀洗衣機手冊準備衣服、洗衣粉準備衣服、洗衣粉設定參數，洗衣服設定參數，洗衣服干凈衣服干凈衣服程序程序輸入輸入運行運行輸出輸出程序程序輸入輸入運行運行輸出輸出分時切換分時切換第18頁/共255頁l 進程的核心思想進程是某個程序在某個數據集

6、合上的運行過程，它有程序、輸入、輸出和狀態。在分時操作系統中，單個CPU被若干進程共享，它使用某種調度算法決定何時停止一個進程的運行，轉而為其他進程提供服務。第19頁/共255頁操作系統維護一個程序計數器，在進程間切換操作系統維護一個程序計數器，在進程間切換對每一個進程而言，都有獨立的計數器和對每一個進程而言，都有獨立的計數器和CPUCPU時間時間操作系統實現分時，任意時刻只有一個進程運行操作系統實現分時，任意時刻只有一個進程運行第20頁/共255頁進程同程序的差別進程同程序的差別第21頁/共255頁一個程序對應兩個進程第22頁/共255頁一個進程包括多個程序第23頁/共255頁進程的特征進程

7、的特征第24頁/共255頁第25頁/共255頁運行態運行態阻塞態阻塞態就緒態就緒態進程就緒，可以運行狀態轉換：進程等待外部事件，阻塞OS決定由哪個進程占用CPU，進程調度？第26頁/共255頁l 運行態變為就緒態l 強制終止某進程的運行（系統原因）l 運行態變為阻塞態l 運行進程等待外部事件發生（自身原因）l 阻塞態變為就緒態l 外部事件已經發生，可準備運行l 就緒態變為運行態l 停止其他進程運行后，運行該進程占用CPU第27頁/共255頁l 問題1：為什么不能從阻塞態變為運行態呢？l 問題2：為什么不能從就緒態變為阻塞態呢？l 答案：l 三種狀態的變換體現了OS的資源管理作用l 進程的核心思

8、想在于運行CPU資源的分配第28頁/共255頁第29頁/共255頁是一個進程剛剛建立，但還未將它送入就緒隊列時的狀態是一個進程剛剛建立，但還未將它送入就緒隊列時的狀態一個進程已經正常結束或異常結束，一個進程已經正常結束或異常結束，OSOS已將它從就緒隊列中移出，但尚未將它撤消已將它從就緒隊列中移出，但尚未將它撤消第30頁/共255頁活動活動掛起掛起事件事件發生發生事件事件發生發生等待等待事件事件掛起掛起調度調度超時超時釋放釋放活動活動掛起掛起第31頁/共255頁第32頁/共255頁l 重要的術語 Cocurrency & Parallel & MultiProgramming Program

9、& Process & Thread Running & Ready & Block & Suspend Dispatch & Activate & Suspend & Wakel 重要的思想 程序與進程：靜態和動態的思想 多道程序：并發與互斥的思想 進程管理：雜七雜八好煩哪？第33頁/共255頁2.1.5 進程控制塊進程控制塊第34頁/共255頁第35頁/共255頁第36頁/共255頁思考：PCB是進程存在的唯一標志 為什么？ 因為因為PCB 1PCB 1、包含了進程的包含了進程的描述信息和控制信息描述信息和控制信息，2 2、是進是進程的程的動態特征的集中反映動態特征的集中反映，3 3、系統

10、系統根據根據PCBPCB而感知某一進程的而感知某一進程的存在存在，所以，所以PCBPCB是進程存在的唯一標志。是進程存在的唯一標志。( (只有在多任務即多道只有在多任務即多道批處理系統中，才可能建立批處理系統中，才可能建立PCBPCB結構，該系統才具有進程活動結構，該系統才具有進程活動) )第37頁/共255頁PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901執行指針就緒隊列指針阻塞隊列指針空閑隊列指針系統中可能擁有數十個、數百個乃至數千個PCB，如何組織？第38頁/共255頁執行指針就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索

11、引表就緒表指針阻塞表指針第39頁/共255頁第40頁/共255頁第41頁/共255頁第42頁/共255頁(1) (1) 創建進程原語創建進程原語 (2) (2) 撤消進程原撤消進程原語語 (3) (3) 掛起進程原語掛起進程原語 (4) (4) 解掛進程原解掛進程原語語(5) (5) 阻塞進程原語阻塞進程原語(6) (6) 喚醒進程原喚醒進程原語語(7) (7) 調度進程運行原語調度進程運行原語(8) (8) 改變優先級改變優先級原語原語第43頁/共255頁2.2.1 進程的創建進程的創建DEFGHBCIJKLMA第44頁/共255頁引起創建進程的事件 (1) 用戶登錄 （分時系統）(2)作業

12、調度 （批處理系統）(3)提供服務 （打印進程）(4)應用請求 系統內核創建進程系統內核創建進程應用程序創建進程應用程序創建進程第45頁/共255頁進程的創建步驟(Creation of Process) 調用進程創建原語Create（） (1)申請空白PCB (2)為新進程分配資源（內存等） (3)初始化進程控制塊 (4)將新進程插入就緒隊列 第46頁/共255頁程序中的第程序中的第1 1語句是調用查找語句是調用查找進程名過程進程名過程“ “ Get Internal Get Internal Name ”Name ”，參數為進程外部名參數為進程外部名n n。該過程查找該過程查找PCBPCB

13、集合，如已集合，如已有此同樣外部名進程則返回出有此同樣外部名進程則返回出錯消息，否則返回一個空閑的錯消息，否則返回一個空閑的PCBPCB內部標識號內部標識號i i。第第2 2語句是把進程外部名語句是把進程外部名n n登記登記到第到第i i個個PCBPCB的相應外部名表目的相應外部名表目中。中。語句語句3 3是往是往PCBPCB中登記優先數。中登記優先數。語句語句4 4登記現場狀態初始值登記現場狀態初始值 S0S0到 相 應 的 現 場 保 留 區 中 或到 相 應 的 現 場 保 留 區 中 或CpustateCpustate中。中。procedure Create (n, Sprocedur

14、e Create (n, S0 0, k, k0 0, M, M0 0, R, R0 0) )beginbegin/ / 請求分配請求分配PCBPCB空間空間i : = Get Internal i : = Get Internal Name(n);Name(n);/ / 初始化初始化PCB PCB Id(i) : =n;Id(i) : =n;Priority(i) : = kPriority(i) : = k0 0; ;Cpustate(i) : = SCpustate(i) : = S0 0; ;Main Store(i) : = MMain Store(i) : = M0 0; ;Res

15、ources(i) : = RResources(i) : = R0 0; ;Status(i) : = Status(i) : = ReadysReadys Parent(i) : = CALLERParent(i) : = CALLER / / 插入就緒隊列插入就緒隊列Insert(RL,i);Insert(RL,i);endend建立進程原語的工作大致描述為：建立進程原語的工作大致描述為：第47頁/共255頁 ，分別記入主存和資源的分別記入主存和資源的初始占有情況，這是由父進程初始占有情況，這是由父進程將自己的一部分資源分給子進將自己的一部分資源分給子進程的。程的。是把進程初始狀態置為是

16、把進程初始狀態置為“ “ 掛起就緒掛起就緒 ” ”。語句語句中中CALLERCALLER代表調用本過代表調用本過程的父進程之內部標識號，將程的父進程之內部標識號，將它記入子進程它記入子進程PCBPCB的父進程名這的父進程名這一欄。一欄。語 句語 句 也 是 調 用 插 入 過 程也 是 調 用 插 入 過 程InsertInsert，其中，其中RLRL表示就緒隊列表示就緒隊列，即把進程，即把進程i i插入就緒隊列。插入就緒隊列。procedure Create (n, Sprocedure Create (n, S0 0, k, k0 0, M, M0 0, R, R0 0) )beginbe

17、gin/ / 請求分配請求分配PCBPCB空間空間i : = Get Internal i : = Get Internal Name(n);Name(n);/ / 初始化初始化PCB PCB Id(i) : =n;Id(i) : =n;Priority(i) : = kPriority(i) : = k0 0; ;Cpustate(i) : = SCpustate(i) : = S0 0; ;Main Store(i) : = MMain Store(i) : = M0 0; ;Resources(i) : = RResources(i) : = R0 0; ;Status(i) : = S

18、tatus(i) : = ReadysReadys Parent(i) : = CALLERParent(i) : = CALLER / / 插入就緒隊列插入就緒隊列Insert(RL,i);Insert(RL,i);endend第48頁/共255頁2.2.2 進程的終止進程的終止第49頁/共255頁進程的終止過程進程的終止過程l 根據被終止進程的標識符，從PCB集合中檢索出該進程的PCB，從中讀出該進程的狀態l 若被終止進程正處于執行狀態，應立即終止該進程的執行，并置調度標志為真，用于指示該進程被終止后應重新進行調度l 若該進程還有子孫進程，還應將其所有子孫進程予以終止，以防他們成為不可控的

19、進程l 將被終止進程所擁有的全部資源，或者歸還給其父進程， 或者歸還給系統l 將被終止進程(它的PCB)從所在隊列(或鏈表)中移出第50頁/共255頁2.2.3 進程的阻塞與喚醒進程的阻塞與喚醒第51頁/共255頁進程的阻塞過程進程的阻塞過程第52頁/共255頁進程的喚醒過程進程的喚醒過程第53頁/共255頁2.2.4 進程的掛起與激活進程的掛起與激活進程的掛起第54頁/共255頁2.2.4 進程的掛起與激活進程的掛起與激活進程的激活第55頁/共255頁進程控制原語與進程狀態轉換的對應第56頁/共255頁UNIX系統實例：1-進程家族樹1、系統初啟后，由系統核心程序建立init進程。init進

20、程讀取文件/etc/ttys，該文件告訴系統共有幾個終端并提供每個終端的說明。init進程將為每個終端生成一個子進程，然后將自己阻塞直到所有子進程結束。2、每個子進程等待用戶登記（login）使用系統，接著執行shell命令解釋程序。3、圖例系統中有三個終端。運行在終端0上的子進程仍在等待用戶登錄；在終端1上的子進程已成功登錄了用戶，正運行shell等待命令輸入；在終端2上的子進程也成功登錄了用戶，該用戶正運行cp程序，cp是shell的子進程，shell 則等待該進程結束。cp結束后，shell再接收輸入，創建新進程執行新輸入命令。第57頁/共255頁UNIX系統實例：2-相關系統調用1.f

21、ork系統調用：功能：建立子進程返回值：fork對子進程返回0，對父進程返回子進程的標識符。具體描述：子進程是父進程的一個副本，這就允許父進程可以很容易地與子進程通信。父子進程都從fork后的那條指令繼續執行。2. exec系統調用：輸入參數：新程序名，功能：以指定程序覆蓋當前進程的程序代碼。3. wait系統調用：輸入參數：進程號功能：等待指定進程結束。第58頁/共255頁UNIX系統實例：3-shell的內部部分代碼顯示命令提示符等待用戶輸入命令行對命令行分析和解釋，得到要運行的程序（例如cp）及其運行參數if (pid=fork( )0 ) /*父進程代碼，典型地如：*/wait ( p

22、id); /*等待該子進程結束*/顯示下一個命令提示符else /*子進程代碼，典型地如：*/exec(cp, L);第59頁/共255頁第60頁/共255頁2.3 進程的同步進程的同步進程同步進程同步的主要任務，是使并發執行的諸進程之間的主要任務，是使并發執行的諸進程之間能有效的共享資源和相互合作，從而使程序的執行能有效的共享資源和相互合作，從而使程序的執行具有可再現性。具有可再現性。第61頁/共255頁2.3.1 進程同步的基本概念進程同步的基本概念第62頁/共255頁Out：4In：7進程進程A：N_f_s = In; /In = 7InsertFileIntoSpooler(N_f_s

23、);In=N_f_s+; /In = 8N_f_s4：File15：File26：File37：Null8：NullSpooler目錄目錄進程切換，一切正常進程切換，一切正常第63頁/共255頁Out：4In：7進程進程A：N_f_s = In; /In = 7進程進程B：N_f_s = In; /In = 7InsertFileIntoSpooler(N_f_s);In=N_f_s+; /In = 84：File15：File26：File37：Null8：NullSpooler目錄目錄進程切換進程切換進程進程A：InsertFileIntoSpooler(N_f_s);In=N_f_s+;

24、 /In = 8進程切換，進程進程切換，進程B數據丟失數據丟失第64頁/共255頁l Get、Copy、Put為三個并發的程序l F、G為保存多條數據的緩沖區，S、T為臨時緩沖區l 三個程序順序執行，可將F的值經過S、T保存到G中l 正常情況下，不存在任何問題，但是程序運行順序發生變化時，結果可能出錯第65頁/共255頁同步問題舉例（同步問題舉例（2 2）初始狀態FSTG分析程序運行順序3，4，5221，2G、C、P4，5331，2，3正確G、P、C4，5331，2，2錯誤C、P、G4，5321，2，2錯誤C、G、P4，5321，2，2錯誤P、C、GP、G、C第66頁/共255頁問題分析兩個獨

25、立進程如何保持同步？現實應用中存在大量的類似實例司機進程司機進程While(True)While(True) 啟動公車；啟動公車；駕駛公車；駕駛公車；停止公車；停止公車； 售票員進程售票員進程While(True)While(True) 關車門；關車門；賣車票；賣車票；開車門；開車門； 正確運行過程正確運行過程While(True)While(True) （司機）啟動公車；（司機）啟動公車；（售票員）關車門；（售票員）關車門；（司機）駕駛公車；（司機）駕駛公車；（售票員）賣車票（售票員）賣車票（司機）停止公車；（司機）停止公車；（售票員）開車門；（售票員）開車門； 第67頁/共255頁只能排它

26、使用的資源稱為臨界資源。一次僅允許一個進程使用的資源。第68頁/共255頁例：二人合作存款例：二人合作存款cobeginPA: N: = count N: = N+100 count: = N;PB: M: = count M: = M+200由由 count: = Mcoendcs1cs2cs1cs2countcs臨界區臨界區臨界資源臨界資源執行速度的不同，導致結果不唯一。執行速度的不同，導致結果不唯一。countcount是一個互斥性使是一個互斥性使用的變量用的變量 ( (有排它性有排它性) )。第69頁/共255頁生產者-消費者問題第70頁/共255頁由于生產者和消費者并發運行，且共享變

27、量counter counter ，造成：第71頁/共255頁第72頁/共255頁可把一個訪問臨界資源的循環進程描述如下：repeat 進入區進入區 critical section; 臨界區臨界區 退出區退出區 remainder section; 剩余區剩余區 until false; 第73頁/共255頁第74頁/共255頁第75頁/共255頁假如有兩個進程假如有兩個進程PiPi和和PjPj，它們共享一個臨界資源，它們共享一個臨界資源R R。如何用軟件方法使進程如何用軟件方法使進程PiPi和和PjPj能互斥地訪問資源能互斥地訪問資源R R呢？呢？程序上如何實現互斥使用臨界資源第76頁/共

28、255頁利用軟件解決進程互斥問題利用軟件解決進程互斥問題 設置一個公用整型變量turn，用于指示被允許進入臨界區的進程編號，若turn=i，表示允許Pi進程進入臨界區。該算法可確保每次只允許一個進入臨界區 Pj進程:repeat while turnj do no op Critical section turn=iRemain Section until falsePi進程:repeat while turni do no op Critical section turn=jRemain Section until false但采用強制兩個進程輪流進入臨界區，很容易造成資源利用不充分。缺點：

29、強制兩進程輪流進入臨界區；不能保證“空閑讓進”第77頁/共255頁利用軟件解決進程互斥問題利用軟件解決進程互斥問題l在每一個進程訪問臨界區資源之前，先動查看一下臨界資源是否正被訪問，若正被訪問，該進程需等待，否則才進入自己的臨界區。設置了一個數組 flag，如第i個元素值為false表示Pi進程未進入臨界區，值為true表示Pi進程進入臨界區。Pi: repeat while flagj do no_op; flagi:=true; critical_section; flagi:=false; remainder section; until false Pj: repeat while f

30、lagi do no_op; flagj:=true; critical_section; flagj:=false; remainder section; until false 缺點：會出現缺點：會出現PiPi和和PjPj同時進入臨界區錯誤。先檢測對方進程狀態標志后再置自己同時進入臨界區錯誤。先檢測對方進程狀態標志后再置自己標志，由于在檢測和放置中可插入另一個進程時檢測操作，會造成二個進程在分標志，由于在檢測和放置中可插入另一個進程時檢測操作，會造成二個進程在分別檢測后同時進入臨界區。解決了別檢測后同時進入臨界區。解決了“空閑讓進空閑讓進”，但又違背了，但又違背了“忙則等待忙則等待”第78

31、頁/共255頁利用軟件解決進程互斥問題利用軟件解決進程互斥問題算法2是先檢測對方進程狀態標志后再置自己標志，由于在檢測和放置中可插入另一個進程時檢測操作，會造成二個進程在分別檢測后同時進入臨界區。為此算法3采用先設置自己標志后再檢測對方狀態標志，它的程序如下。Pj: repeat flagj:=true; while flagi do no_op; critical_section; flagj:=false; remainder section; until falsePi: repeat flagi:=true; while flagj do no_op; critical_section

32、; flagi:=false; remainder section; until false缺點：可能出現二個進程先后同時設置后再分別檢測對方狀態標志，造成缺點：可能出現二個進程先后同時設置后再分別檢測對方狀態標志，造成對方都不能進入臨界區，無限期等待。解決了對方都不能進入臨界區，無限期等待。解決了“忙則等待忙則等待”，但又違背了，但又違背了“空閑讓進空閑讓進”和和“有限等待有限等待”第79頁/共255頁利用軟件解決進程互斥問題利用軟件解決進程互斥問題 Repeat flagi = false Critical section; Remainder sectiont; Until flase;

33、 flagi:= true; turn:=j; While (flagj and turn=j) do no-op; 說明：說明：Flagi=true PiFlagi=true Pi要進或正進要進或正進turn=jturn=j應輪到應輪到PjPjPi第80頁/共255頁l 組合了算法組合了算法1 1和算法和算法3 3，既實現了，既實現了“空閑讓進空閑讓進”，又保證了，又保證了“忙則等待忙則等待”l 為了防止二進程進入臨界區而無限期等待，又為了防止二進程進入臨界區而無限期等待，又設置變量設置變量turnturn，表示不允許進入臨界區的編號，表示不允許進入臨界區的編號，每個進程在先設置自己標，每個

34、進程在先設置自己標志后再設置志后再設置turnturn標志，不允許另一個進程進入，這時再同時標志，不允許另一個進程進入，這時再同時檢測另一個進程狀態標志和不允許進入標志，這樣可以保證檢測另一個進程狀態標志和不允許進入標志，這樣可以保證當二個進程同時要求進入臨界區時，只允許一個進程進入臨當二個進程同時要求進入臨界區時，只允許一個進程進入臨界區。界區。l 缺點：四種算法全部屬于缺點：四種算法全部屬于“忙等待忙等待”方式，現在已很少使用方式，現在已很少使用。第81頁/共255頁利用硬件解決進程互斥問題利用硬件解決進程互斥問題第82頁/共255頁第83頁/共255頁開鎖操作： lock false，任

35、何機器一條指令可以實現。關鎖操作 ：共有3步 （1）測試lock的值是false，才可關鎖。 （2）lock true （3）原lock值為true時，返回。等待別的進程釋放資源后開鎖。 前兩步應作為一個整體來執行，不可分開，這樣才能保證在前兩步之間，lock不被別的進程改變。這一點在許多機器中都提供了專門的硬件指令來實現。不同的機器，指令略有不同，但基本功能是相同的，例如在IBM370系列機中的TS指令（test and set），和在Intel 8086中的XCHG（交換指令）。第84頁/共255頁檢測和設置（TS）的功能可用PASCAL語言描述如下：function TS(var loc

36、k：boolean): boolean；begin TS:=lock; Lock:=true;EndC+語言描述如下: bool TS(bool& lock)if(lock=true)return true;elselock=true; return false;第85頁/共255頁l 程序中的第一條語句用于檢查TS指令執行后的TS狀態。若為false表示資源空閑，進程可進入臨界區；否則，不斷測試執行TS指令后的TS變量值，直至其為false。l 當進程退出臨界區時，設置變量lock為false，以允許其它進程進入臨界區。l 可為每個臨界資源設置一可為每個臨界資源設置一個布爾變量個布爾變量1o

37、ck1ock，并賦予其初，并賦予其初值為值為falsefalse，以表示資源空閑，以表示資源空閑。利用。利用TSTS指令實現互斥的循環指令實現互斥的循環進程可描述為：進程可描述為： 關鎖操作關鎖操作 Repeat Lock := false; Critical section; Remainder section; Until false; While TS(lock) do skip; 開鎖操作開鎖操作 利用利用TSTS實現進程互斥實現進程互斥第86頁/共255頁l 在利用Swap實現進程互斥時，可為臨界資源設置一個全局布爾變量lock，其初值為false，在每個進程中再利用一個局部布爾變量

38、key。利用Swap指令實現進程互斥的循環進程可描述為： Repeat Lock := false; Critical section; Remainder sectiont; Until flase; Key:=true; Repeat Swap(lock,key); until key = false; 利用交換指令利用交換指令SwapSwap實現進程互斥實現進程互斥第87頁/共255頁鎖方法缺點：l“忙等”，違背了“讓權等待”原則l 某種臨界資源只能一個進程使用l 很難用它解決復雜的同步問題第88頁/共255頁2.3.2 信號量機制信號量機制第89頁/共255頁信號量機制信號量機制整型信

39、號量整型信號量wait(S): while S0 do no-op S =S-1;signal(S): S =S+1;Wait操作，只要信號量S 0，就會不斷測試，忙等，違背讓權等待。 第90頁/共255頁思考題：設有兩個優先級相同的進程思考題：設有兩個優先級相同的進程P1P1、P2P2如下。令信號量如下。令信號量S1S1、S2S2的初值為的初值為0 0，已知，已知z=2z=2，試問，試問P1P1、P2P2并發運行后并發運行后x=?y=?z=?(x=?y=?z=?(北航北航2001)2001)進程進程P1 P1 進程進程P2 P2 y:=1; x:=1;y:=y+2; x:=x+1;V(S1)

40、; P(S1);z:=y+1; x:=x+y;P(S2); V(S2); y:=z+y; z:=z+x;第91頁/共255頁l y:=z+y在z:=z+x之前 x=5 , y=12 , z=9l y:=z+y在z:=z+x之后 x=5 , y=7, z=9結果結果第92頁/共255頁記錄型信號量記錄型信號量第93頁/共255頁信號量機制信號量機制記錄型信號量記錄型信號量數據結構數據結構type semaphore=record value:integer; L:list of process; endprocedure wait(S) var S: semaphore; begin S.val

41、ue:=S.value-1; if S.value0 then block(S,L) endprocedure signal(S) var S: semaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S,L); end 第94頁/共255頁第95頁/共255頁前趨關系處理程序或語句間的前趨關系信號量應用舉例信號量應用舉例第96頁/共255頁利用信號量實現進程互斥利用信號量實現進程互斥第97頁/共255頁var mutex：semaphore：l；begin parbegin process 1:begin repeat wai

42、t(mutex); critical section signal(mutex); remainder section until false; end process 2:begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend第98頁/共255頁下面是兩進程模擬執行情況：下面是兩進程模擬執行情況：如果如果P2P2先進入臨界區，則先進入臨界區，則P1P1等待，等待，P1P1，P2P2不會同時進入臨界區。不會同時進入臨界區。第99頁/共255頁 1 1

43、無進程進入臨界區無進程進入臨界區mutexmutex= 0 1= 0 1個進程在臨界區個進程在臨界區 -1 1-1 1個進程在等待臨界區個進程在等待臨界區（對兩個進程：（對兩個進程：mutexmutex只能取三個值）只能取三個值）用用mutexmutex實現實現n n個進程的互斥時，個進程的互斥時，mutexmutex取值？取值？ 1 -(n-1)1 -(n-1)第100頁/共255頁利用信號量實現前趨關系利用信號量實現前趨關系l 設有兩個并發執行的進程P1和P2。P1中有語句S1；P2中有語句S2。希望在S1執行后再執行S2，怎么辦？l 為實現這種前趨關系，用一個公用信號量S并賦予其初值為初

44、值為0 0，且使P1、P2取如下形式： P1 中： S1S1；signalsignal（S S）；）； P2 中： waitwait（S S）；）； S2S2； 第101頁/共255頁S4S5S3S1S6S2 前趨圖舉例前趨圖舉例 第102頁/共255頁 Var a,b,c,d,e,f,g; semaphore =0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e);

45、 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 第103頁/共255頁信號量機制信號量機制AND型信號量型信號量第104頁/共255頁AND型信號量型信號量第105頁/共255頁 if Si1 and and Sn1 then for i =1 to n do Si =Si-1; endfor else place the process in the waiting queue ass

46、ociated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endifSwait(S1, S2, , Sn)第106頁/共255頁 for i =1 to n do Si=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue. endfor; Ssignal(S1, S2, , Sn)第107

47、頁/共255頁信號量機制信號量機制信號量集信號量集第108頁/共255頁 If S1 = t1 AND s2 = t2 Sn = tn then for I := 1 to n do Si:= Si di; endfor else place the process in the waiting queue associated with the first Si found with Si =1 then L:=L-1 Else waiting endif If mx =1 then mx:=mx-0 Else waiting endif 利用信號量集機制解決讀者利用信號量集機制解決讀者-寫

48、者問題寫者問題 L :=L+1 第143頁/共255頁 writer:begin repeat Swait(mx,1,1; L,RN,0);Swait(mx,1,1; L,RN,0); perform write operationperform write operation; ; Ssignal(mx,1);Ssignal(mx,1); until false; end parend end If mx =1 and L=RN then mx:=mx-1; L:=L-RN; Else waiting endif mx :=mx+1 第144頁/共255頁第145頁/共255頁2.4.3 睡

49、眠理發師問題問題描述一把理發椅，N把等待座位理發師為理發椅上的顧客理發，沒有顧客就在理發椅上睡覺有一個顧客時需要叫醒理發師多個顧客時需要在等待座位上等候第146頁/共255頁互斥關系分析理發椅上只能有一位顧客等待座位是有限緩沖區同步關系分析只要存在顧客，理發師就不能睡覺信號量設計互斥信號量：實現對“等待顧客數”的互斥同步信號量1：理發師“睡眠”和“工作”的同步同步信號量2：等待顧客與等待座位的同步第147頁/共255頁 var waiting : integer; /*等候理發的顧客數*/ CHAIRS: integer; /*為顧客準備的椅子數*/ customers, barbers，mu

50、tex : semaphore; customers := 0; barbers := 0; waiting := 0; mutex := 1;第148頁/共255頁Procedure barber;beginwhile(TRUE); /*理完一人,還有顧客嗎?*/ P( P(cutomerscutomers); ); /*若無顧客,理發師睡眠*/ P(mutex); /*進程互斥*/ waiting := waiting 1; /*等候顧客數少一個*/ V(barbers); V(barbers); /*理發師去為一個顧客理發*/ V(mutex); /*開放臨界區*/ cut-hair(

51、); /*正在理發*/end;第149頁/共255頁procedure customerbegin P(mutex); /*進程互斥*/ if waitingCHAIRS begin /*看看有沒有空椅子*/ waiting := waiting+1; /* 等候顧客數加1*/ V(customers); V(customers); /*必要的話喚醒理發師*/ V(mutex); /*開放臨界區*/ P(barbers); P(barbers); /*無理發師, 顧客坐著養神*/ get-haircut( ); /*一個顧客坐下等理發*/ end else V(mutex); /*人滿了,走吧

52、!*/end;第150頁/共255頁第151頁/共255頁請添加必要的信號量和P、V（或wait()、signal()）操作，實現上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦初值。第152頁/共255頁【解析】Semaphore seets = 10; /表示空余座位數量的資源信號量，初值為10Semaphore mutex = 1; /管理取號機的互斥信號量，初值為1，表示取號機空閑。Semaphore custom = 0; /表示顧客數量的資源信號量，初值為0第153頁/共255頁第154頁/共255頁優點分析徹底解決忙等待忙等待弊端，提高OS的管理層次可實現復雜復雜

53、的同步與互斥情況，特別是多進程多進程間通信可最大限度的保證并發效率缺點分析實現機制復雜復雜，互斥和同步關系分析困難存在死鎖陷阱，需要謹慎小心嚴密的設計第155頁/共255頁1.有橋如圖所示，車流方向如箭頭所示。回答下列問題：有橋如圖所示，車流方向如箭頭所示。回答下列問題：橋假設：該橋上每次只能有一輛車行駛，試用信號量的假設：該橋上每次只能有一輛車行駛，試用信號量的P、V操作實現橋上的交通管理。操作實現橋上的交通管理。假設：該橋上不允許兩車交會，但允許同方向多個車依假設：該橋上不允許兩車交會，但允許同方向多個車依次通過（即橋上可有多個同方向行駛的車）。試用信號次通過（即橋上可有多個同方向行駛的車

54、）。試用信號量的量的P、V操作實現橋上的交通管理。操作實現橋上的交通管理。第156頁/共255頁.第157頁/共255頁第158頁/共255頁.第159頁/共255頁第160頁/共255頁ParBegin Var x: integer; Process P1 Var y, z:integer; Begin x:=1; y:=0; If x1 then y:=y+1; z:=y; End; Process P2 Var t,u:integer; Begin x:=0; t:=0; If x1 then t:=t+2; u:=t; End;ParEnd1、下面是兩個并發執行的進程。試回答：1) 它

55、們能正確執行嗎（有唯一確定的結果）？若不能，試舉例說明2)進行適當修改，使兩個并發執行的進程能夠正確執行。課堂討論題課堂討論題第161頁/共255頁第162頁/共255頁2 2、 對于諸如公共汽車上駕駛員和售票員的工作，如視其為對于諸如公共汽車上駕駛員和售票員的工作，如視其為2 2個進個進程，試用程，試用P.VP.V操作控制這類關系。操作控制這類關系。（可直接在下面加（可直接在下面加P.VP.V操作，并給出信號量初值）操作，并給出信號量初值） 駕駛員駕駛員售票員售票員 L1L1：L2L2： 停車停車開車門開車門 開車開車關車門關車門goto L1goto L1goto L2goto L2第16

56、3頁/共255頁 到站停車到站停車 開開 車車 開開 車車 門門 關關 車車 門門 售售 票票 正常行車正常行車。售票員售票員司機司機第164頁/共255頁3、某高校計算機系開設網絡課并安排上機實習，假設機房共有2m臺機器，有2n名學生選該課，規定： （1）每2個學生組成一組，各占一臺機器，合作完成上機實習。 （2）只有一組2個學生到齊，并且此時機房有空閑機器時，該組學生才能進入機房。 （3）上機實習由一名教師檢查，檢查完畢，一組學生同時離開機房，試設計相應的數據結構，并用P.V操作模擬上機實習過程。第165頁/共255頁4、設有三個進程P1，P2，P3共用一個緩沖池協同工作。P1和P2負責循

57、環地分別從設備1和設備2上輸入數據，“加工”后送入緩沖池，P3負責循環地以任何順序從緩沖池中取數據在設備3上輸出。緩沖池中共有9個長度相等的緩沖區（進程每次傳輸的數據與緩沖區長度相同），初始均為空。利用兩個棧S1和S2分別記錄空，滿緩沖區始地址。 （1）試寫出各進程工作流程示意圖； （2）進程間是否存在臨界區問題，為什么？ （3）用P.V操作控制各進程正確運行。第166頁/共255頁進程的基本概念 進程控制 進程同步 經典進程的同步問題 管程機制 進程通信 線程 第167頁/共255頁第168頁/共255頁第169頁/共255頁圖 2-11 管程的示意圖 共享數據一組操作過程初始化代碼進入隊列

58、條件(不忙)隊列第170頁/共255頁type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 第171頁/共255頁第172頁/共255頁第173頁/共255頁第174頁/共255頁第175頁/共255頁第176頁/共255頁第177頁/共255頁第178頁/共255頁 第179頁/共255頁typ

59、e producer-consumer=monitortype producer-consumer=monitor var in,out,count:integer; var in,out,count:integer; buffer:array buffer:array0,n-10,n-1 of item;of item; notfull, notempty:condition; notfull, notempty:condition; procedure entry put(item)procedure entry put(item) begin begin if countn then i

60、f countn then notfull.wait;notfull.wait; buffer(in)=nextp; buffer(in)=nextp; in=(in+1) mod n; in=(in+1) mod n; count=count+1; count=count+1; if notempty.queue then if notempty.queue then notempty.signal;notempty.signal; end end procedure entry get(item) begin if count0 then notempty.wait; nextc =buf