課件2014第二章進程管理

1、計算機操作系統(tǒng)楊為民 湯小丹 等 編著22.3.1 進程同步的基本概念2. 臨界資源(Critical Resource) 生產(chǎn)者-消費者(producer-consumer)問題是一個著名的進程同步問題。它描述的是：有一群生產(chǎn)者進程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進程去消費。為使生產(chǎn)者進程與消費者進程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個具有n個緩沖區(qū)的緩沖池，生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中；消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費。盡管所有的生產(chǎn)者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即不允許消費者進程到一個空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進程向一個已裝滿

2、產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。 32.3.1 進程同步的基本概念 我們可利用一個數(shù)組來表示上述的具有n個(0，1，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進程生產(chǎn)并投放一個產(chǎn)品后，輸入指針加1；用一個輸出指針out來指示下一個可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費者進程取走一個產(chǎn)品后，輸出指針加1。由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)把輸入指針加1表示成 in=(in+1)mod n；輸出指針加1表示成out=(out+1) mod n。當(dāng)(in+1) mod n=out時表示緩沖池滿；而in=out則表示緩沖池空。此外，還引入了一個整型變量coun

3、ter, 其初始值為0。每當(dāng)生產(chǎn)者進程向緩沖池中投放一個產(chǎn)品后，使counter加1；反之，每當(dāng)消費者進程從中取走一個產(chǎn)品時， 使counter減1。生產(chǎn)者和消費者兩進程共享下面的變量： 42.3.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。在生產(chǎn)者和消費者進程的描述中，no-op是一條空操作指令，while condition do no-op語句表示重復(fù)的測試條件(condicati

4、on)，重復(fù)測試應(yīng)進行到該條件變?yōu)閒alse(假)，即到該條件不成立時為止。在生產(chǎn)者進程中使用一局部變量nextp，用于暫時存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費者進程中，則使用一個局部變量nextc,用于存放每次要消費的產(chǎn)品。 52.3.1 進程同步的基本概念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 n

5、o-op; nextc =bufferout; out =(out+1) mod n; counter =counter-1; consumer the item in nextc; until false; 63. 臨界區(qū)(critical section)可把一個訪問臨界資源的循環(huán)進程描述如下：repeat critical section; remainder section;until false; entry sectionexit section2.3.1 進程同步的基本概念72.3.1 進程同步的基本概念4. 同步機制應(yīng)遵循的規(guī)則 (1) 空閑讓進。(2) 忙則等待。 (3) 有

6、限等待。 (4) 讓權(quán)等待。 82.3.2 信號量機制1. 整型信號量最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作(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; 92.3.2 信號量機制type semaphore=record value:integer; L:list of process; end相應(yīng)地，wait(S)和signal(S)

7、操作可描述為：procedure wait(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); end102.3.2 信號量機制 在記錄型信號量機制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號量，對它的每次wait操作，意味著進程請求一個單位的該類資源，因此描述為S.value=S

8、.value-1； 當(dāng)S.value0時，表示該類資源已分配完畢，因此進程應(yīng)調(diào)用block原語，進行自我阻塞，放棄處理機，并插入到信號量鏈表S.L中?？梢姡摍C制遵循了“讓權(quán)等待”準(zhǔn)則。此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數(shù)目。對信號量的每次signal操作，表示執(zhí)行進程釋放一個單位資源，故S.value =S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value0，則表示在該信號量鏈表中，仍有等待該資源的進程被阻塞，故還應(yīng)調(diào)用wakeup原語，將S.L鏈表中的第一個等待進程喚醒。如果S.value的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量轉(zhuǎn)化為互

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

10、 and and Sn1 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 waitin

11、g in the queue associated with Si into the ready queue. endfor; 132.3.2 信號量機制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

12、 of the 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; 142.3.2 信號量機制 一般“信號量集”的幾種特殊情況：(1) Swait(S, d, d)。 此時在信號量集中只有一個信號量S， 但允許它每次申請d個資源，當(dāng)現(xiàn)有資源數(shù)少于d時，不予分配。(2) Swait(S, 1, 1)。 此時的信號量集已蛻

13、化為一般的記錄型信號量(S1時)或互斥信號量(S=1時)。(3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號量操作。當(dāng)S1時，允許多個進程進入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進程進入特定區(qū)。換言之，它相當(dāng)于一個可控開關(guān)。 152.3.3 信號量的應(yīng)用 1. 利用信號量實現(xiàn)進程互斥 利用信號量實現(xiàn)進程互斥的進程可描述如下：Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder seetion unti

14、l false; 162.3.3 信號量的應(yīng)用 end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 17圖 2-10 前趨圖舉例 2.3.3 信號量的應(yīng)用2. 利用信號量實現(xiàn)前趨關(guān)系182.3.3 信號量的應(yīng)用 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 wai

15、t(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 192.4 經(jīng)典進程的同步問題2.4.1 生產(chǎn)者消費者問題2.4.2 哲學(xué)家進餐問題2.4.3 讀者-寫者問題202.4.1 生產(chǎn)者消費者問題前面我們已經(jīng)對生產(chǎn)者消費者問題(The proceducer-con

16、sumer problem)做了一些描述，但未考慮進程的互斥與同步問題，因而造成了數(shù)據(jù)Counter的不定性。生產(chǎn)者消費者問題是相互合作的進程關(guān)系的一種抽象。在輸入時，輸入進程是生產(chǎn)者，計算進程是消費者；而在輸出時，則計算進程是生產(chǎn)者，而打印進程是消費者，因此，該問題有很大的代表性及實用價值。 212.4.1 生產(chǎn)者消費者問題 1. 利用記錄型信號量解決生產(chǎn)者消費者問題假定在生產(chǎn)者和消費者之間的公用緩沖池中，具有n個緩沖區(qū)，這時可利用互斥信號量mutex實現(xiàn)諸進程對緩沖池的互斥使用；利用信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費者相互等效，只要緩

17、沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產(chǎn)者消費者問題可描述如下： 222.4.1 生產(chǎn)者消費者問題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(

18、mutex); signal(full); until false; end 232.4.1 生產(chǎn)者消費者問題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 242.4.1 生產(chǎn)者消費者問題 在生產(chǎn)者消費者問題中應(yīng)注意：首先，在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)

19、必須成對地出現(xiàn)； 其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計算進程中，而signal(empty)則在打印進程中，計算進程若因執(zhí)行wait(empty)而阻塞， 則以后將由打印進程將它喚醒；最后，在每個程序中的多個wait操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進程死鎖。252.4.1 生產(chǎn)者消費者問題2. 利用AND信號量解決生產(chǎn)者消費者問題 Var mutex, empty, full:semaphore=1, n, 0;

20、 buffer:array0, , n-1 of item; in out:integer=0, 0; begin parbegin producer:begin repeat produce an item in nextp; Swait(empty, mutex); buffer(in)=nextp; in=(in+1)mod n; Ssignal(mutex, full); until false; end262.4.1 生產(chǎn)者消費者問題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 end272.4.2 哲學(xué)家進餐問題 1. 利用記錄型信號量解決哲學(xué)家進餐問題經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時間內(nèi)只允許一位哲學(xué)家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構(gòu)成信號量數(shù)組。其描述如下：Var chopstick: array0, , 4 of semaphore;282.4.2 哲學(xué)家進餐問題所有信號量均被初始化為1，第i位哲學(xué)家的活動