操作系統(tǒng)進程管理三互斥和同步二

1、12.3 進程互斥和同步 臨界資源、臨界區(qū)定義 記錄型的信號量內部成員 的意義 signal wait操作含義 怎樣利用信號量解決進程之間的前趨關系？2 臨界區(qū)(critical section)：進程中訪問臨界資源的一段代碼。 進入區(qū)(entry section)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)檢查可否進入臨界區(qū)的一段代碼。如果可以進入臨界區(qū)，通常設置相應正在訪問臨正在訪問臨界區(qū)界區(qū)標志 退出區(qū)(exit section)：用于將正在訪問臨界區(qū)標志清除。 剩余區(qū)(remainder section)：代碼中的其余部分。返回32.3.1 基本概念-臨界區(qū) 2、臨界區(qū)：每個進程中訪問臨界資

2、源的那段、臨界區(qū)：每個進程中訪問臨界資源的那段程序段稱為臨界區(qū)（臨界段）。程序段稱為臨界區(qū)（臨界段）。42.3.1 基本概念-臨界區(qū)的訪問過程entry sectionexit section critical section remainder section臨界區(qū)的訪問過程返回進入區(qū)退出區(qū)臨界區(qū)5同步機制應遵循的準則 空閑讓進：其他進程均不處于臨界區(qū)； 忙則等待：已有進程處于其臨界區(qū)； 有限等待：等待進入臨界區(qū)的進程不能死等； 讓權等待：不能進入臨界區(qū)的進程，應釋放CPU（如轉換到阻塞狀態(tài)）返回6實現進程互斥的硬件方法 完全利用軟件方法，有很大局限性（如不適于多進程），現在已很少采用。 可

3、以利用某些硬件指令其讀寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷；Test-and-Set指令該指令讀出標志后設置為該指令讀出標志后設置為TRUEboolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;lock表示資源的兩種狀態(tài)：TRUE表示正被占用，FALSE表示空閑7互斥算法（互斥算法（TS指令）指令） 利用TS實現進程互斥：每個臨界資源設置一個公共布爾變量lock，初值為FALSE 在進入區(qū)利用TS進行檢查：有進程在臨界區(qū)時，重復檢查；直到其它進程退出時，檢查通過；while TS

4、(&lock);lock = FALSE;critical sectionremainder section82.3.2 信號量(semaphore)需要一個地位高于進程的管理者來解決公有資源的使用問題。OS可從進程管理者的角度來處理互斥的問題，信號量就是OS提供的管理公有資源的有效手段。 1965年，由荷蘭學者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)），是一種卓有成效的進程同步機制。 信號量是一個被保護的變量，被初始化之后，只有只有wait操作、signal操作才能訪問和改變它的值。信號量代表可用資源實體的數量

5、。 wait操作、signal操作又稱為P、V操作。它們都是原子操作（原語原語）92.3.2 信號量(semaphore)一、一、整型信號量整型信號量 整型信號量是表示共享資源狀態(tài)且只能由特殊的原子操作改變的整型量。 想法：定義一個整型變量，用整形變量值來標記資源 使用情況：如整型量0,說明有可用資源;整型量0說明資源忙，進程必須等待。 對于一次只允許一個進程訪問的臨界資源，可定義一個用于互斥的整型信號量，并初始化為初始化為1 1。 102.3.2 信號量(semaphore)一、一、整型信號量整型信號量 整型信號量的wait和signal操作Wait(s):while s0 do no-op

6、 對CS的互斥訪問。 s:=s-1. Signal(s): s:=s+1 實現對資源的釋放注：wait(s)和 signal(s)都是原子操作(原語）112.3.2 信號量(semaphore)一、一、整型信號量整型信號量 利用整型信號量實現互斥方法：利用整型信號量實現互斥方法： 想法：為必須互斥訪問的CS定義一個互斥信號量mutexmutex，初始值為1，然后將CS放入wait(mutexwait(mutex) )和signal(mutexsignal(mutex) )之間，當CS可訪問時，wait(mutexwait(mutex) )才能正常結束使進程進入CS。122.3.2 信號量(se

7、maphore)二、利用整型信號量實現互斥二、利用整型信號量實現互斥while mutex0 do no-op mutex:=mutex-1.mutexmutex:=mutex+1:=mutex+1 Begin Repeat wait(mutex); Critical section Signal(mutex) Remainder section Until false;end13三、利用信號量來協調進程執(zhí)行的順序三、利用信號量來協調進程執(zhí)行的順序例例1 1：P P1 1、P P2 2兩個進程，要求兩個進程，要求P P2 2必須在必須在P P1 1結束結束后執(zhí)行后執(zhí)行, ,為此，設置一個信號量

8、為此，設置一個信號量S,S,初始值初始值為為0 0。 parbegin begin P1; Signal(s); end begin Wait(s); P2 ; end parend14三、利用信號量來描述前趨關系三、利用信號量來描述前趨關系例2：有P1，P2兩個進程：S1，S2，SS6分別是P1、P2中的語句，我們要求它們的執(zhí)行順序如下圖所示 :15fS1S2S5S4S3S6gbdace16利用信號量來描述前趨關系利用信號量來描述前趨關系-例例2 2varvar a,b,c,d,e,f,g:semaphorea,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0;:=0,0

9、,0,0,0,0;beginbegin prabeginprabegin begimbegim s s1 1; signal(a); signal(b); end; signal(a); signal(b); end; begin wait(a); begin wait(a); s s2 2; ;signal(c); signal(d); signal(c); signal(d); end;end; begin wait(b); begin wait(b); s s3 3; ;signal(g); end;signal(g); end; begin wait(c); begin wait(c)

10、; s s4 4; ;signal(e); end;signal(e); end; begin wait(d); begin wait(d); s s5 5; ;signal(f); end;signal(f); end; begin wait(e); wait(f); wait(g); begin wait(e); wait(f); wait(g); s s6 6; ; end.end. parendparendend.end.17記錄型信號量和wait、signal原語 信號量是一個確定的二元組（value, L），value 是一個具有非負初值的整型變量，L 是一個初始狀態(tài)為空的隊列。

11、value代表資源的實體。在實際應用中應準確地說明s的意義和初值; 初始化指定一個非負整數值，表示空閑資源總數（又稱為“資源信號量”）若為非負值表示當前的空閑資源數，若為負值其絕對值表示當前等待臨界區(qū)的進程數 L：每個信號量的相關隊列，表示因得不到臨界資源而阻塞的進程，其初始狀態(tài)為空。 信號量和wait、signal原語 信號量只能通過信號量只能通過初始化初始化和和兩個標準的兩個標準的原語原語來訪問來訪問作為作為OS核心代碼執(zhí)行，核心代碼執(zhí)行，不受進程調度的打斷不受進程調度的打斷在實際操作系統(tǒng)中，一般情況下是由機器硬件提供在實際操作系統(tǒng)中，一般情況下是由機器硬件提供P、V操操

12、作作的指令，當然是原子操作，若機器不提供的指令，當然是原子操作，若機器不提供P、V操作的指操作的指令，則操作系統(tǒng)提供令，則操作系統(tǒng)提供P、V操作原語。操作原語。 信號量的形式化定義：信號量的形式化定義：type semaphore=record value: integer; L: listofprocess;end1. P原語(wait)19procedure wait(S)var S：semaphore；beginS.value:=S.value-1； /表示申請一個資源表示申請一個資源;if S.value0 then block(S.L)； /如果沒如果沒有空閑資源，調用進程進入和有空

13、閑資源，調用進程進入和信號量信號量S相關的等相關的等待隊列待隊列 s.L; 阻塞調用阻塞調用wait 的進程的進程end 2. V原語(signal)procedure signal(S)var S: semaphore；beginS.value:=S.value+1； /表示釋放一個資源；表示釋放一個資源；if S.value=1 & S2 = 1 & & Sn = 1) /滿足資源要求時的處理；滿足資源要求時的處理； for (i = 1; i = n; +i) -Si; /注：與注：與wait的處理不同，這里是在確信可滿足的處理不同，這里是在確信可滿足 /資源要求

14、時，才進行減資源要求時，才進行減1操作；操作； break; else /某些資源不夠時的處理；某些資源不夠時的處理； 調用進程進入第一個小于調用進程進入第一個小于1信號量的等待隊列信號量的等待隊列Sj.L; 阻塞調用進程阻塞調用進程;將調用進程的將調用進程的PC置為置為swait操作開頭操作開頭 44 Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si;/釋放占用的資源；釋放占用的資源； for (each process P waiting in Si.L) /檢查每種資源的等待隊列的所有進程；檢查每種資源的等待隊列的所有進程； 從等待隊列從等

15、待隊列Si.L中取出進程中取出進程P;進程進程P進入就緒隊列進入就緒隊列; 需要注意：需要注意：原先處于阻塞狀態(tài)的進程，被喚醒后，從何處開始執(zhí)行？原先處于阻塞狀態(tài)的進程，被喚醒后，從何處開始執(zhí)行？與與 記錄型信號量機制有何不同？記錄型信號量機制有何不同？451. 生產者消費者問題(the producer-consumer problem)問題描述：若干進程通過有限的共享緩沖區(qū)交換數據。其中，生產者進程不斷寫入，而消費者進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。共享緩沖區(qū)生產指針消費指針Producer 1Producer 2.Producer MCons

16、umer 1Consumer 2.Consumer N滿空指針移動方向46生產者消費者問題 AND型信號量 若不愿意考慮wait操作的先后順序，也可用AND型信號量來實現。 生產者進程中生產者進程中： 用用Swait(empty,mutex)代替代替wait(empty)和和wait(mutex), 用用Ssignal(mutex,full)代替代替signal(mutex)和和signal(full) 消費者進程中消費者進程中 用用Swait(full,mutex)代替代替wait(full)和和wait(mutex), 用用Ssignal(mutex,empty)代替代替signal(mu

17、tex)和和signal(empty)472. 讀者寫者問題讀者寫者問題(the readers-writers problem) 問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個 “讀寫”互斥， “寫寫”互斥， 讀讀允許48 采用信號量機制： Wmutex表示允許寫，初值是1。 公共變量Rcount表示“正在讀”的進程數，初值是0； Rmutex表示對Rcount的互斥操作，初值是1。P(Rmutex); if (Rcount = 0)P(Wmutex); +Rcount;V(Rmutex); read;P(Rmutex); -Rcount; if (Rc

18、ount = 0)V(Wmutex);V(Rmutex);ReaderP(Wmutex); write;V(Wmutex);Writer49 采用一般信號量集機制：問題增加一個限制條件：同時讀的讀者最多R個 Wmutex表示允許寫，初值是1 Rcount表示允許讀者數目，初值為RSwait(Rcount, 1, 1; Wmutex, 1, 0); read;Ssignal(Rcount, 1);ReaderSwait(Wmutex, 1, 1; Rcount, R, 0); write;Ssignal(Wmutex, 1);Writer503. 哲學家進餐問題(the dining philo

19、sophers problem) 問題描述：（由Dijkstra首先提出并解決）5個哲學家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個哲學家之間放一支；哲學家的動作包括思考和進餐，進餐時需要同時拿起他左邊和右邊的兩支筷子，思考時則同時將兩支筷子放回原處。如何保證哲學家們的動作有序進行？如：不出現相鄰者同時要求進餐；不出現有人永遠拿不到筷子；5152 1.利用記錄型信號量機制解決 2.利用AND型信號量機制解決2.4.2哲學家就餐問題53哲學家就餐問題 問題分析： 筷子是臨界資源：每根有多于一個哲學家要用，而且同時只能有一個哲學家使用 5根筷子可以用5個信號量表示。形成信號量數組： var ch

20、opstick:array0,4of semaphore； 所有信號量初值為1，表示未被使用。54哲學家就餐問題 第第i位哲學家的活動描述為：位哲學家的活動描述為： Repeat wait(chopsticki); wait(chopstick(i+1)mod 5); eat; signal(chopsticki); signal(chopstick(i+1)mod 5); think; Until false;parbegin philosopher (0)；philosopher (1)；philosopher (2)；philosopher (3)；philosopher (4)；parend