第二章進程管理

1、進 程 的 同 步 第二章第二章 進程管理進程管理 2.1 2.1 進程的基本概念進程的基本概念 2.2 2.2 進程控制進程控制 2.3 2.3 進程同步進程同步 2.4 2.4 經(jīng)典進程的同步問題經(jīng)典進程的同步問題 2.5 2.5 管程機制管程機制進 程 的 同 步 上節(jié)回顧上節(jié)回顧1.整型信號量2.記錄型信號量3.AND型信號量4.信號量集5.信號量機制的特性進 程 的 同 步 實驗一實驗一進 程 的 同 步 2.4 經(jīng)典進程的同步問題經(jīng)典進程的同步問題 2.4.1 生產(chǎn)者生產(chǎn)者消費者問題消費者問題 前面我們已經(jīng)對生產(chǎn)者消費者問題(The proceducer-consumer prob

2、lem)做了一些描述，但未考慮進程的互斥與同步問題，因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者消費者問題是相互合作的進程關系的一種抽象，例如， 在輸入時，輸入進程是生產(chǎn)者，計算進程是消費者；而在輸出時，則計算進程是生產(chǎn)者，而打印進程是消費者， 因此，該問題有很大的代表性及實用價值。 進 程 的 同 步 1. 利用記錄型信號量解決生產(chǎn)者利用記錄型信號量解決生產(chǎn)者消費者問題消費者問題l具有n個緩沖區(qū)公用緩沖池中l(wèi)互斥信號量mutex實現(xiàn)諸進程對緩沖池的互斥使用l信號量empty表示緩沖池中空緩沖區(qū)數(shù)量。l信號量full表示緩沖池中滿緩沖區(qū)的數(shù)量。lmutex為公用信號量，full與empty

3、與私用信號量l假定這些生產(chǎn)者和消費者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。進 程 的 同 步 producer: repeat produce an item in nextp; while counter=n do no-op; bufferin =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; count

4、er =counter-1; consumer the item in nextc; until false; 進 程 的 同 步 Var mutex, empty, full:semaphore =1,n,0; buffer:array0, , n-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)

5、; signal(full); until false; end 進 程 的 同 步 consumer:begin repeat wait(full); wait(mutex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end 進 程 的 同 步 程序總結：l互斥（公用）信號量，在單個程序中必須成對地出現(xiàn)l例如實現(xiàn)互斥的wait(mutex)和signal(mutex) l資源（私用）信號量e

6、mpty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。l例如，wait(empty)在計算進程中，而signal(empty)則在打印進程中，計算進程若因執(zhí)行wait(empty)而阻塞， 則以后將由打印進程將它喚醒l每個程序中的多個wait操作順序不能顛倒。應先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進程死鎖?！跋人胶蠊边M 程 的 同 步 死鎖的發(fā)生：1. 先執(zhí)行消費者進程，消費者進程交換了P操作的次序，先鎖mutex，再鎖full，full初始為0導致阻塞在等待full信號量的隊列中。2. 轉去執(zhí)行生產(chǎn)者

7、進程，由于生產(chǎn)者進程也交換了P操作，在生產(chǎn)者進程執(zhí)行了P（mutex）操作后，生產(chǎn)者進程阻塞在等待mutex信號量的隊列中。3. 這樣生產(chǎn)者和消費者兩進程分別阻塞在等待mutex和full信號量的隊列，沒有進程可以向前推進，系統(tǒng)進入死鎖狀態(tài)。進 程 的 同 步 2. 利用利用AND信號量解決生產(chǎn)者信號量解決生產(chǎn)者消費者問題消費者問題 ar mutex, empty, full:semaphore =1, n, 0; buffer:array0, , n-1 of item; in out:integer =0, 0; begin parbegin producer:begin repeat p

8、roduce an item in nextp; Swait(empty, 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 進 程 的 同

9、步 2.4.2 哲學家進餐問題哲學家進餐問題 1. 利用記錄型信號量解決哲學家進餐問題利用記錄型信號量解決哲學家進餐問題 經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時間內只允許一位哲學家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構成信號量數(shù)組。其描述如下： Var chopstick: array0, , 4 of semaphore;進 程 的 同 步 所有信號量均被初始化為1， 第i位哲學家的活動可描述為： repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(chopstic

10、ki); signal(chopstick(i+1) mod 5); think; until false; 進 程 的 同 步 解法保證不會有兩個相鄰的哲學家同時進餐仍然有可能發(fā)生死鎖： 1. 當五個哲學家同時饑餓且同時拿起自己左邊的筷子，會使五個信號量均為0， 2. 當他們再試圖去拿各自右邊的筷子，都將因無筷子而無限期等待。進 程 的 同 步 可采取以下幾種解決方法： (1) 至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。 (2) 僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。 (3

11、) 規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學家則相反。按此規(guī)定，將是1、 2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即五位哲學家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學家能獲得兩只筷子而進餐。 進 程 的 同 步 2. 利用利用AND信號量機制解決哲學家進餐問題信號量機制解決哲學家進餐問題 在哲學家進餐問題中，要求每個哲學家先獲得兩個臨界資源(筷子)后方能進餐，這在本質上就是前面所介紹的AND同步問題，故用AND信號量機制可獲得最簡潔的解法。Var chopsiick array 0, , 4 of semaphore =(1,1

12、,1,1,1); processi repeat think; Sswait(chopstick(i+1) mod 5, chopstick i); eat; Ssignat(chopstick (i+1) mod 5, chopstick i); until false; 進 程 的 同 步 2.4.3 讀者讀者-寫者問題寫者問題 1. 利用記錄型信號量解決讀者利用記錄型信號量解決讀者-寫者問題寫者問題l互斥信號量Wmutex：實現(xiàn)Reader與Writer進程的互斥l整型變量Readcount表示正在讀的進程數(shù)目。l僅當Readcount=0, 表示尚無Reader進程在讀時，Reader

13、進程才需要執(zhí)行wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進程便可去讀，相應地，做Readcount+1操作。l僅當Reader進程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行signal(Wmutex)操作，以便讓Writer進程寫。l因為Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應該為它設置一個互斥信號量rmutex。 進 程 的 同 步 讀者-寫者問題可描述如下：Var rmutex, wmutex:semaphore =1,1; Readcount:integer =0; begin parbegin READE

14、R:begin repeat wait(rmutex); if readcount=0 then wait(wmutex); Readcount =Readcount+1; signal(rmutex); perform read operation; 進 程 的 同 步 wait(rmutex); readcount =readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end WRITER:begin repeat wait(wmutex); perform write operatio

15、n; signal(wmutex); until false; end parend end 進 程 的 同 步 2. 利用信號量集機制解決讀者利用信號量集機制解決讀者-寫者問題寫者問題 l增加限制，最多允許RN個讀者讀l信號量L，初值RN，用于控制讀者數(shù)目l在第RN+1個讀者要進入讀時，會引起阻塞l使用Swait(S, 1, 0)的方法實現(xiàn)開關作用進 程 的 同 步 Var RN integer; L, mx:semaphore =RN,1; begin parbegin READER:begin repeat Swait(L,1,1); Swait(mx,1,0); perform read operation; Ssignal(L,1); until false; end進 程 的 同 步 WRITER:begin repeat Swait(mx,1,1; L,RN,0); perform write operation; Ssignal(mx,1); until false; end parend end 進 程 的 同 步 練習：公交車問題練習：公交車問題在公共汽車上有司機和售票員，他們的活動如下：司機的活動：啟動車輛正常運行到站停車售票員的活動：上下乘客 關車門售票開車門 上下乘客注意：1）司機必須等售票員關車門后才能啟動車輛2）