作業(yè)_進(jìn)程_習(xí)題課

1、操作系統(tǒng)習(xí)題講解操作系統(tǒng)習(xí)題講解一、一、進(jìn)程概念進(jìn)程概念二、二、進(jìn)程同步和互斥進(jìn)程同步和互斥進(jìn)進(jìn) 程程 概概 念（一）念（一）問題：如果系統(tǒng)中有問題：如果系統(tǒng)中有N個(gè)進(jìn)程，個(gè)進(jìn)程， 運(yùn)行進(jìn)程最多幾個(gè)，最少幾個(gè)？運(yùn)行進(jìn)程最多幾個(gè)，最少幾個(gè)？ 就緒進(jìn)程最多幾個(gè)，最少幾個(gè)？就緒進(jìn)程最多幾個(gè)，最少幾個(gè)？ 等待進(jìn)程最多幾個(gè)，最少幾個(gè)？等待進(jìn)程最多幾個(gè)，最少幾個(gè)？運(yùn)行運(yùn)行就緒就緒等待等待進(jìn)程的狀態(tài)及其轉(zhuǎn)換進(jìn)程的狀態(tài)及其轉(zhuǎn)換解答：假設(shè)只有一個(gè)解答：假設(shè)只有一個(gè)cpucpu，則，則 運(yùn)行進(jìn)程最多運(yùn)行進(jìn)程最多1 1個(gè)，最少個(gè)，最少0 0個(gè)；個(gè)； 就緒進(jìn)程最多就緒進(jìn)程最多N-1-1個(gè)，最少個(gè)，最少0 0個(gè)；個(gè)；

2、等待進(jìn)程最多等待進(jìn)程最多N個(gè)，最少個(gè)，最少0 0個(gè)；個(gè)；概念：概念： (1)(1)進(jìn)程、進(jìn)程的基本狀態(tài)；進(jìn)程、進(jìn)程的基本狀態(tài)；單單CPU；進(jìn)程切換；進(jìn)程切換；系統(tǒng)進(jìn)程、用戶進(jìn)程；系統(tǒng)進(jìn)程、用戶進(jìn)程； (2)(2)死鎖（不是死鎖（不是“死機(jī)死機(jī)”）；）；進(jìn)進(jìn) 程程 概概 念（一）念（一）進(jìn)進(jìn) 程程 概概 念（二）念（二）問題：問題：進(jìn)程有無如下狀態(tài)轉(zhuǎn)換，為什么？進(jìn)程有無如下狀態(tài)轉(zhuǎn)換，為什么？（1）等待）等待運(yùn)行運(yùn)行 （2）就緒）就緒等待等待解答：解答：（1）不能：）不能：等待就緒運(yùn)行等待就緒運(yùn)行 （2）不能：）不能：就緒運(yùn)行等待就緒運(yùn)行等待問題：問題：一個(gè)轉(zhuǎn)換發(fā)生，是否另一個(gè)轉(zhuǎn)換一一個(gè)轉(zhuǎn)換發(fā)生，

3、是否另一個(gè)轉(zhuǎn)換一定發(fā)生？找出所有的可能。定發(fā)生？找出所有的可能。解答：解答： 就緒就緒運(yùn)行運(yùn)行: : 不一定不一定（系統(tǒng)中僅一個(gè)進(jìn)程）（系統(tǒng)中僅一個(gè)進(jìn)程） 轉(zhuǎn)換條件：被調(diào)度程序選中轉(zhuǎn)換條件：被調(diào)度程序選中 運(yùn)行運(yùn)行就緒就緒: : 一定一定（討論就緒隊(duì)列的長度）（討論就緒隊(duì)列的長度） 轉(zhuǎn)換條件：時(shí)間片到時(shí)轉(zhuǎn)換條件：時(shí)間片到時(shí), ,或有更高優(yōu)先級或有更高優(yōu)先級 的進(jìn)程出現(xiàn)的進(jìn)程出現(xiàn)進(jìn)進(jìn) 程程 概概 念（三）念（三）解答：解答： 運(yùn)行運(yùn)行等待等待: : 不一定（考慮死鎖）不一定（考慮死鎖）轉(zhuǎn)換條件：等待某事件發(fā)生轉(zhuǎn)換條件：等待某事件發(fā)生 等待等待就緒就緒: : 不一定不一定轉(zhuǎn)換條件：等待的事件發(fā)生轉(zhuǎn)

4、換條件：等待的事件發(fā)生進(jìn)進(jìn) 程程 概概 念（三）念（三）進(jìn)進(jìn) 程程 概概 念（四）念（四）問題：問題：日常生活中的日常生活中的“進(jìn)程進(jìn)程”舉例舉例解答：解答：從什么角度來看待進(jìn)程從什么角度來看待進(jìn)程兩個(gè)角度：兩個(gè)角度：“程序程序- -數(shù)據(jù)數(shù)據(jù)- -運(yùn)行運(yùn)行” 或或“資源資源- -調(diào)度調(diào)度- -運(yùn)行運(yùn)行”經(jīng)典例子：經(jīng)典例子：“按照菜譜作菜按照菜譜作菜”“”“樂隊(duì)演樂隊(duì)演奏奏”或或“向服務(wù)員請求服務(wù)向服務(wù)員請求服務(wù)”等等進(jìn)程同步和互斥（一）進(jìn)程同步和互斥（一）問題：問題：用信號量機(jī)制解決下圖之同步問題用信號量機(jī)制解決下圖之同步問題getcopyputfstg條件是什么？哪些需要加鎖，即哪些資源需要

5、同步？進(jìn)程同步和互斥（一）進(jìn)程同步和互斥（一）cpcgpcgpg一個(gè)數(shù)據(jù)上的操作順序：一個(gè)數(shù)據(jù)上的操作順序：get - copy - putGet不能向不能向“滿滿”的的S中放；中放；Copy不能從不能從“空空”的的S中??；不能向中??；不能向“滿滿”的的T中中放；放；Put不能不能“空空”的的T中取中?。ㄍ剑┬盘柫浚海ㄍ剑┬盘柫浚簩?shí)際上也起到互斥作用實(shí)際上也起到互斥作用S_Empty, T_Empty， 初值為初值為1S_Full, T_Full; 初值為初值為0（同步）信號量：（同步）信號量：實(shí)際上也起到互斥作用實(shí)際上也起到互斥作用S_Empty, T_Empty， 初值為初值為1S_F

6、ull, T_Full; 初值為初值為0Get:while（1） wait(S_Empty) T_get_S(); signal(S_Full); Copy:while(1) wait(S_Full); wait(T_Empty); S_copy_T(); signal(T_Full); signal(S_Empty); Put:While(1) wait(T_Full); T_put_G(); siganl(T_Empty); 進(jìn)程同步和互斥（二）進(jìn)程同步和互斥（二）問題：用問題：用信號量機(jī)制信號量機(jī)制解決下面問題解決下面問題司機(jī)進(jìn)程：司機(jī)進(jìn)程：REPEAT啟動車輛啟動車輛正常駕駛正常駕駛到

7、站停車到站停車UNTIL 售票員進(jìn)程：售票員進(jìn)程：REPEAT關(guān)門關(guān)門售票售票開門開門UNTIL 同步要求：先關(guān)門，后開車；先停車，后開門同步要求：先關(guān)門，后開車；先停車，后開門信號量：信號量：S_Door, 初值為初值為0S_Stop; 初值為初值為0司機(jī)進(jìn)程司機(jī)進(jìn)程：while(1) wait(S_Door); 啟動；啟動； 駕駛；駕駛； 停車；停車；/可以開門可以開門 signal(S_Stop);乘務(wù)員進(jìn)程乘務(wù)員進(jìn)程:While(1) 關(guān)門；關(guān)門；/可以開車可以開車 signal(S_Door); 售票；售票； wait(S_Stop); 開門；開門；同步要求：先關(guān)門，后開車；同步要求

8、：先關(guān)門，后開車； 先停車，后開門先停車，后開門wait(s): s:=s-1; If s0 Then 將本進(jìn)程插入相應(yīng)隊(duì)列將本進(jìn)程插入相應(yīng)隊(duì)列末尾末尾等待；等待；signal(s)： s:=s+1; If s=0 Then 從等待隊(duì)列從等待隊(duì)列隊(duì)尾隊(duì)尾取一個(gè)進(jìn)程喚醒，取一個(gè)進(jìn)程喚醒，插入就緒隊(duì)列插入就緒隊(duì)列進(jìn)程同步和互斥（五）進(jìn)程同步和互斥（五）對對 wait 和和signal 操作定義作以下修改操作定義作以下修改,是是否有問題？否有問題？問題：問題：這樣定義這樣定義wait,signal操作是否有問操作是否有問題？題？不合理：先進(jìn)后出；可能不合理：先進(jìn)后出；可能“無限等待無限等待”第二類第

9、二類讀者寫者讀者寫者問題（寫者優(yōu)先）問題（寫者優(yōu)先）1 1）共享讀）共享讀2 2）互斥寫、讀寫互斥）互斥寫、讀寫互斥3 3）寫者優(yōu)先于讀者（）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)一旦有寫者，則后續(xù)讀者必須等待讀者必須等待，喚醒時(shí)優(yōu)先考慮寫者喚醒時(shí)優(yōu)先考慮寫者）進(jìn)程同步和互斥進(jìn)程同步和互斥初始值：初始值：mutex = 1, wrt = 1, readcount = 0wait(mutex);readcount+;if (readcount = 1)wait(wrt);signal(mutex); reading is performed wait(mutex);readcount-;if (re

10、adcount = 0)signal(wrt);signal(mutex):wait(wrt); writing is performed signal(wrt);2個(gè)信號量的作用是什么？Readcount的作用是什么？這種互斥機(jī)制會產(chǎn)生什么影響？寫者優(yōu)先：寫者優(yōu)先： 需要對兩種操作進(jìn)行何種修改？需要對兩種操作進(jìn)行何種修改？普通讀寫互斥，只要在讀寫之間進(jìn)行互斥操作即可。普通讀寫互斥，只要在讀寫之間進(jìn)行互斥操作即可。而現(xiàn)在，讀者進(jìn)程：而現(xiàn)在，讀者進(jìn)程：在在進(jìn)入進(jìn)入時(shí)必須考慮有無寫者在等待，如果有，時(shí)必須考慮有無寫者在等待，如果有，讀者進(jìn)程必須等待；讀者進(jìn)程必須等待；在在退出退出時(shí)必須考慮有無寫者

11、在等待，如果有，時(shí)必須考慮有無寫者在等待，如果有，必須優(yōu)先喚醒寫者進(jìn)程必須優(yōu)先喚醒寫者進(jìn)程寫者進(jìn)程也必須作同樣的考慮寫者進(jìn)程也必須作同樣的考慮需要解決的問題：需要解決的問題：1 1：如何表明有寫者在等待？：如何表明有寫者在等待？寫者等待進(jìn)程計(jì)數(shù)寫者等待進(jìn)程計(jì)數(shù)2 2：如何喚醒寫者進(jìn)程？：如何喚醒寫者進(jìn)程？（普通讀寫互斥中等待隊(duì)列的形成位置）（普通讀寫互斥中等待隊(duì)列的形成位置）現(xiàn)在讀寫進(jìn)程必須有各自的等待隊(duì)列現(xiàn)在讀寫進(jìn)程必須有各自的等待隊(duì)列同樣的同樣的3 3：寫者進(jìn)程結(jié)束后，如果沒有正在等待的：寫者進(jìn)程結(jié)束后，如果沒有正在等待的寫者，就必須喚醒讀者，當(dāng)前有無讀者寫者，就必須喚醒讀者，當(dāng)前有無讀者

12、? ?需要讀者等待進(jìn)程計(jì)數(shù)需要讀者等待進(jìn)程計(jì)數(shù)Var 三個(gè)信號量三個(gè)信號量 mutex: semaphore; 互斥信號量，初值為互斥信號量，初值為1 R : semaphore; 對應(yīng)讀者等待隊(duì)列，初值為對應(yīng)讀者等待隊(duì)列，初值為0 W: semaphore; 對應(yīng)寫者等待隊(duì)列，初值為對應(yīng)寫者等待隊(duì)列，初值為0一般變量：一般變量： Writing: Boolean; 初值初值false, 有寫者正在寫有寫者正在寫 rc: integer; 初值初值0, 共享讀的讀者數(shù)共享讀的讀者數(shù) rq: integer; 初值初值0,等待隊(duì)列中讀者數(shù)等待隊(duì)列中讀者數(shù) wq: integer; 初值初值0,等

13、待隊(duì)列中寫者數(shù)等待隊(duì)列中寫者數(shù)各信號量和一般變量的作用是什么？各信號量和一般變量的作用是什么？mutex的作用？的作用？Begin wait(mutex);If (Writing OR wq0)Then Begin rq:=rq+1; signal(mutex); wait(R); wait(mutex);/resume End;rc:=rc+1;signal(mutex);Read();wait(mutex);rc:=rc-1;If (rc=0 AND wq0) Then Begin wq:=wq-1;Writing:=true;signal(mutex);signal(W); End;El

14、se signal(mutex);End讀者進(jìn)程(a) 檢測是否有寫者并處理(b) Inc(rc)(c) Read()(d) Dec(rc)(e) 處理寫者等待隊(duì)列如果有寫進(jìn)程在寫或者等待，讀進(jìn)程在R中等待當(dāng)前在讀的進(jìn)程數(shù)加1讀進(jìn)程等待隊(duì)列數(shù)加1當(dāng)前在讀的進(jìn)程數(shù)減1寫進(jìn)程等待隊(duì)列數(shù)減1喚醒某一等待寫進(jìn)程Begin wait(mutex);If (Writing OR rc0)Then Beginwq:=wq+1; signal(mutex);wait(W); End;Else BeginWriting:=true; signal(mutex);Write();wait(mutex);If (w

15、q0)Then Beginwq:=wq-1;signal(mutex);signal(W); EndElse If (rq0)Then BeginWriting:=false;signal(mutex);While (rq0) Beginrq:=rq-1;signal(R); End EndElse BeginWriting:=false;signal(mutex); EndEnd寫者進(jìn)程(a) 檢測是否有進(jìn)程正在讀寫檢測是否有進(jìn)程正在讀寫 (b) Writing(T); Write(); Writing(F)(c) 處理寫者等待隊(duì)列處理寫者等待隊(duì)列;處理處理Reader等待隊(duì)列等待隊(duì)列wai

16、t.signalwait.signal操作討論操作討論( (很多書中又成很多書中又成為為P P，V V操作操作) )1) 1) 信號量的物理含義：信號量的物理含義：S0S0表示有表示有S S個(gè)資源可用；個(gè)資源可用；S=0S=0表示無資源可用；表示無資源可用；S0S0則則| S | S |表示表示S S等待隊(duì)列中的進(jìn)程個(gè)數(shù)。等待隊(duì)列中的進(jìn)程個(gè)數(shù)。wait(S):wait(S):表示申請一個(gè)資源表示申請一個(gè)資源; ; signal(S)signal(S)表示釋放一個(gè)資源。信號量的初表示釋放一個(gè)資源。信號量的初值應(yīng)該大于等于值應(yīng)該大于等于0 0wait.signalwait.signal操作討論操作

17、討論2) wait,signal2) wait,signal操作必須成對出現(xiàn)，有一個(gè)操作必須成對出現(xiàn)，有一個(gè)waitwait操作就一定有一個(gè)操作就一定有一個(gè)signalsignal操作。操作。當(dāng)當(dāng)為互斥操作為互斥操作時(shí)，它們同時(shí)，它們同處于同一進(jìn)程處于同一進(jìn)程。當(dāng)為當(dāng)為同步操作同步操作時(shí)，則時(shí)，則不在同一進(jìn)程中不在同一進(jìn)程中出現(xiàn)。出現(xiàn)。如果如果wait(S1)wait(S1)和和signal(S2)signal(S2)兩個(gè)操作在一起，兩個(gè)操作在一起，那那么么waitwait操作的順序至關(guān)重要操作的順序至關(guān)重要, ,一個(gè)同步一個(gè)同步waitwait操操作與一個(gè)互斥作與一個(gè)互斥waitwait操作在一起時(shí)同步操作在一起時(shí)同步waitwait操作操作在互斥在互斥waitwait操作前。操作前。而兩個(gè)而兩