操作系統(tǒng)課件CCH07-ProcessSynchronization

1、Module 7: Process SynchronizationBackground（背景）（背景）The Critical-Section Problem （臨界區(qū)問(wèn)題）（臨界區(qū)問(wèn)題）Synchronization Hardware （同步的硬件實(shí)現(xiàn)）（同步的硬件實(shí)現(xiàn)）Semaphores （信號(hào)量）（信號(hào)量）Classical Problems of Synchronization（經(jīng)典同步問(wèn)題）經(jīng)典同步問(wèn)題）Monitors （管程）（管程）Java Synchronization （Java中的同步機(jī)制）中的同步機(jī)制）Synchronization in Solaris 2 （Sol

2、aris 2的同步機(jī)制）的同步機(jī)制）Synchronization in Windows NT （Windows NT的同步機(jī)制）的同步機(jī)制）7.1 Background 進(jìn)程間的聯(lián)系進(jìn)程間的聯(lián)系:相交進(jìn)程：指多個(gè)并發(fā)進(jìn)程在邏輯上有某種聯(lián)系相交進(jìn)程：指多個(gè)并發(fā)進(jìn)程在邏輯上有某種聯(lián)系無(wú)關(guān)進(jìn)程：在邏輯上無(wú)任何聯(lián)系的進(jìn)程無(wú)關(guān)進(jìn)程：在邏輯上無(wú)任何聯(lián)系的進(jìn)程7.1 Backgroundl進(jìn)程間的制約關(guān)系進(jìn)程間的制約關(guān)系 間接制約：間接制約：有些資源需要互斥使用，因此各進(jìn)程競(jìng)有些資源需要互斥使用，因此各進(jìn)程競(jìng)爭(zhēng)使用這些資源獨(dú)占分配到的部分或全部共享爭(zhēng)使用這些資源獨(dú)占分配到的部分或全部共享資源，進(jìn)程的這種關(guān)

3、系為資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥進(jìn)程的互斥 直接制約：直接制約：系統(tǒng)中一些進(jìn)程需要相互合作，共同完系統(tǒng)中一些進(jìn)程需要相互合作，共同完成一項(xiàng)任務(wù)。具體說(shuō)，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要成一項(xiàng)任務(wù)。具體說(shuō)，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)緒態(tài).進(jìn)程的這種關(guān)系為進(jìn)程的這種關(guān)系為進(jìn)程的同步進(jìn)程的同步7.1 Background共享變量的修改沖突共享變量的修改沖突間接制約間接制約操作順序沖突操作順序沖突直接制約直接制約有有3個(gè)進(jìn)程：個(gè)進(jìn)

4、程：get, copy和和put，它們對(duì)它們對(duì)4個(gè)存儲(chǔ)區(qū)域個(gè)存儲(chǔ)區(qū)域f、s、t和和g進(jìn)行操作。進(jìn)行操作。7.1 Background7.1 Background Concurrent access to shared data may result in data inconsistency（對(duì)共享數(shù)據(jù)的并發(fā)訪問(wèn)可能導(dǎo)致（對(duì)共享數(shù)據(jù)的并發(fā)訪問(wèn)可能導(dǎo)致數(shù)據(jù)的不一致性）數(shù)據(jù)的不一致性）. Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes（

5、要保持?jǐn)?shù)據(jù)的一致性，就需要一種保證并（要保持?jǐn)?shù)據(jù)的一致性，就需要一種保證并發(fā)進(jìn)程的正確執(zhí)行順序的機(jī)制）發(fā)進(jìn)程的正確執(zhí)行順序的機(jī)制）.A race condition Depending on which process reaches the shared resource first, we have several possible results!The bounded bufferenter( )remove( )producerconsumerBounded Buffer public class BoundedBuffer public void enter(Object item

6、) / producer calls this method public Object remove() / consumer calls this method/ potential race condition on countprivate volatile int count; enter( )public void enter(Object item) while( count = BUFFER_SIZE) ; / do nothing! count+; bufferin = item; in = (in+1) % BUFFER_SIZE;remove( )public Objec

7、t remove() Object item; while( count = 0) ; / do nothing! count-; item = bufferout; out = (out+1) % BUFFER_SIZE;+ and at the machine level+count:Register1=count;Register1=register1+1;Count=register1-count:Register2=count;Register2=register2-1;Count=register2Understanding the issue Concurrent access

8、to shared data may result in data inconsistency Lack of synchronization means results may be non-deterministic and non-repeatable In the bounded buffer solution, both the consumer and the producer update counter 臨界區(qū)臨界區(qū)(critical section)：進(jìn)程中訪問(wèn)臨界資源的進(jìn)程中訪問(wèn)臨界資源的一段代碼。一段代碼。 假定一個(gè)系統(tǒng)有假定一個(gè)系統(tǒng)有n個(gè)進(jìn)程個(gè)進(jìn)程P0,P1,Pn-1,

9、每個(gè)進(jìn)程有每個(gè)進(jìn)程有一個(gè)代碼段稱為臨界區(qū)一個(gè)代碼段稱為臨界區(qū),在該區(qū)中進(jìn)程可能修改共享在該區(qū)中進(jìn)程可能修改共享變量變量更新一個(gè)表更新一個(gè)表寫一個(gè)文件等寫一個(gè)文件等.當(dāng)一個(gè)進(jìn)程在臨界當(dāng)一個(gè)進(jìn)程在臨界區(qū)中執(zhí)行時(shí)區(qū)中執(zhí)行時(shí),其他進(jìn)程都不能進(jìn)入臨界區(qū)其他進(jìn)程都不能進(jìn)入臨界區(qū)7.2 臨界區(qū)問(wèn)題臨界區(qū)問(wèn)題7.2 臨界區(qū)問(wèn)題臨界區(qū)問(wèn)題 臨界區(qū)的執(zhí)行在時(shí)間上是互斥的臨界區(qū)的執(zhí)行在時(shí)間上是互斥的, ,進(jìn)程必須請(qǐng)求進(jìn)入進(jìn)程必須請(qǐng)求進(jìn)入臨界區(qū)臨界區(qū) 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)(entry section)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)臨界區(qū)的一段代

10、碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)“正在訪問(wèn)臨界區(qū)正在訪問(wèn)臨界區(qū)”標(biāo)志。標(biāo)志。 退出區(qū)退出區(qū)(exit section)：用于將用于將正在訪問(wèn)臨界區(qū)正在訪問(wèn)臨界區(qū)標(biāo)志清除標(biāo)志清除 剩余區(qū)剩余區(qū)(remainder section)：代碼中的其余部分。代碼中的其余部分。7.2 臨界區(qū)問(wèn)題臨界區(qū)問(wèn)題entry sectionexit section critical section remainder sectionSolution to Critical-Section Problem1.Mutual Exclusion. If process Pi is executing in its c

11、ritical section, then no other processes can be executing in their critical sections（互斥。假定進(jìn)程（互斥。假定進(jìn)程Pi在其臨界區(qū)內(nèi)執(zhí)行，其他任在其臨界區(qū)內(nèi)執(zhí)行，其他任何進(jìn)程將被排斥在自己的臨界區(qū)之外）何進(jìn)程將被排斥在自己的臨界區(qū)之外）.2. Progress. If no process is executing in its critical section and there exist some processes that wish to enter their critical section, t

12、hen the selection of the processes that will enter the critical section next cannot be postponed indefinitely（有空讓進(jìn)。當(dāng)沒(méi)有進(jìn)程在臨界區(qū)中執(zhí)行時(shí)，需要進(jìn)（有空讓進(jìn)。當(dāng)沒(méi)有進(jìn)程在臨界區(qū)中執(zhí)行時(shí)，需要進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)能夠很快進(jìn)入入臨界區(qū)的進(jìn)程，應(yīng)能夠很快進(jìn)入. ）3. Bounded Waiting. A bound must exist on the number of times that other processes are allowed to enter their cr

13、itical sections after a process has made a request to enter its critical section and before that request is granted（有限等待。在一個(gè)進(jìn)程提出進(jìn)入臨界區(qū)的請(qǐng)求和該請(qǐng)求（有限等待。在一個(gè)進(jìn)程提出進(jìn)入臨界區(qū)的請(qǐng)求和該請(qǐng)求得到答復(fù)的時(shí)間內(nèi)，其他進(jìn)程進(jìn)入臨界區(qū)的次數(shù)必須是有限的）得到答復(fù)的時(shí)間內(nèi)，其他進(jìn)程進(jìn)入臨界區(qū)的次數(shù)必須是有限的）.兩進(jìn)程互斥的軟件方法兩進(jìn)程互斥的軟件方法 算法算法1:單標(biāo)志單標(biāo)志 算法算法2：雙標(biāo)志、后檢查：雙標(biāo)志、后檢查 算法算法3(Petersons Algori

14、thm)：先修改、后檢先修改、后檢查；后修改者等待查；后修改者等待算法算法1：?jiǎn)螛?biāo)志：?jiǎn)螛?biāo)志 設(shè)立一個(gè)公用整型變量設(shè)立一個(gè)公用整型變量 turn：描述允許進(jìn)入臨界區(qū)描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí)的進(jìn)程標(biāo)識(shí).有兩個(gè)進(jìn)程有兩個(gè)進(jìn)程Pi, Pj，其中的其中的Piwhile (turn != i);critical sectionturn = j;remainder section在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：turn為為i時(shí)，進(jìn)程時(shí)，進(jìn)程Pi可進(jìn)入；可進(jìn)入；在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識(shí)：進(jìn)程在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識(shí)：進(jìn)程Pi退出時(shí)，改退出時(shí)，改turn為進(jìn)

15、程為進(jìn)程Pj的的標(biāo)識(shí)標(biāo)識(shí)j； 缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒(méi)有考慮進(jìn)程缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒(méi)有考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在的實(shí)際需要。容易造成資源利用不充分：在進(jìn)程進(jìn)程1出讓臨界區(qū)之后，進(jìn)程出讓臨界區(qū)之后，進(jìn)程2使用臨界區(qū)之使用臨界區(qū)之前，進(jìn)程前，進(jìn)程1不可能再次使用臨界區(qū)；不可能再次使用臨界區(qū)；Algorithm 1算法算法2：雙標(biāo)志、后檢查：雙標(biāo)志、后檢查 設(shè)立一個(gè)標(biāo)志數(shù)組設(shè)立一個(gè)標(biāo)志數(shù)組flag：描述進(jìn)程是否在臨界區(qū)，初描述進(jìn)程是否在臨界區(qū)，初值均為值均為FALSE,先修改后檢查?？煞乐箖蓚€(gè)進(jìn)程同時(shí)進(jìn)先修改后檢查。可防止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。入臨界區(qū)。flagi

16、= TRUE;while (flagj);critical sectionflagi = FALSE;remainder section 缺點(diǎn)：缺點(diǎn)： Pi和和Pj可能都進(jìn)入不了臨界區(qū)。按下面序列執(zhí)可能都進(jìn)入不了臨界區(qū)。按下面序列執(zhí)行時(shí)，會(huì)都進(jìn)不了臨界區(qū)：行時(shí)，會(huì)都進(jìn)不了臨界區(qū)：Pi Pj Pi Pj。即在切換自己即在切換自己flag之后和檢查對(duì)方之后和檢查對(duì)方flag之前之前有一段時(shí)間，結(jié)果都切換有一段時(shí)間，結(jié)果都切換flag，都檢查不通過(guò)。都檢查不通過(guò)。Algorithm 2算法算法3(Petersons Algorithm)：先修改、后檢查；后修改者等待先修改、后檢查；后修改者等待tur

17、n=j;描述可進(jìn)入的進(jìn)程（同時(shí)修改標(biāo)志時(shí)）描述可進(jìn)入的進(jìn)程（同時(shí)修改標(biāo)志時(shí)）在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后： 檢查對(duì)方檢查對(duì)方flag，如果不在臨界區(qū)則自己進(jìn)入空閑則入如果不在臨界區(qū)則自己進(jìn)入空閑則入 否則再檢查否則再檢查turn：保存的是較晚的一次賦值，則較晚的進(jìn)程等待，保存的是較晚的一次賦值，則較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入先到先入，后到等待較早的進(jìn)程進(jìn)入先到先入，后到等待flagi = TRUE; turn = j;while (flagj & turn = j);critical sectionflagi = FALSE;rema

18、inder section7.3 進(jìn)程互斥的硬件方法進(jìn)程互斥的硬件方法 完全利用軟件方法，有很大局限性（如不適于多進(jìn)完全利用軟件方法，有很大局限性（如不適于多進(jìn)程），現(xiàn)在已很少采用。程），現(xiàn)在已很少采用。 特殊硬件指令原子地執(zhí)行，因而保證讀寫操作特殊硬件指令原子地執(zhí)行，因而保證讀寫操作不被中斷不被中斷: Test-and-Set (TS)指令指令 SWAP指令指令Test-and-Set指令指令為每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量為每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量lock，初值為初值為FALSElock表示資源的兩種狀態(tài)：表示資源的兩種狀態(tài)：TRUE:占用占用FALSE:空閑空閑該指令讀出標(biāo)志后

19、設(shè)置為該指令讀出標(biāo)志后設(shè)置為TRUE boolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old; Test-and-Set指令指令 在進(jìn)入?yún)^(qū)利用在進(jìn)入?yún)^(qū)利用TS進(jìn)行檢查：進(jìn)行檢查：有進(jìn)程在臨界區(qū)時(shí)，重復(fù)有進(jìn)程在臨界區(qū)時(shí)，重復(fù)檢查；直到其它進(jìn)程退出檢查；直到其它進(jìn)程退出時(shí)，檢查通過(guò)；時(shí)，檢查通過(guò)； 在退出區(qū)置在退出區(qū)置lock為為FALSEwhile TS(&lock);lock = FALSE;critical sectionremainder sectionSwap instruction交換兩個(gè)

20、字（字節(jié)）的內(nèi)容交換兩個(gè)字（字節(jié)）的內(nèi)容void SWAP(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp;Swap instruction 利用利用Swap實(shí)現(xiàn)進(jìn)程互斥：每個(gè)臨界資源設(shè)置一個(gè)公共實(shí)現(xiàn)進(jìn)程互斥：每個(gè)臨界資源設(shè)置一個(gè)公共布爾變量布爾變量lock，初值為初值為FALSE。每個(gè)進(jìn)程設(shè)置一個(gè)私每個(gè)進(jìn)程設(shè)置一個(gè)私有布爾變量有布爾變量keykey = TRUE;do SWAP(&lock, &key); while (key);lock = FALSE;critical sectionremainder section硬件方法

21、的優(yōu)點(diǎn)硬件方法的優(yōu)點(diǎn) 適用于任意數(shù)目的進(jìn)程適用于任意數(shù)目的進(jìn)程 簡(jiǎn)單，容易驗(yàn)證其正確性簡(jiǎn)單，容易驗(yàn)證其正確性 可以支持進(jìn)程內(nèi)存在多個(gè)臨界區(qū)，只需為每個(gè)臨界可以支持進(jìn)程內(nèi)存在多個(gè)臨界區(qū)，只需為每個(gè)臨界區(qū)設(shè)立一個(gè)布爾變量區(qū)設(shè)立一個(gè)布爾變量硬件方法的缺點(diǎn)硬件方法的缺點(diǎn) 等待要耗費(fèi)等待要耗費(fèi)CPU時(shí)間時(shí)間 可能可能饑餓饑餓：從等待進(jìn)程中隨機(jī)選擇一個(gè)進(jìn)入臨界：從等待進(jìn)程中隨機(jī)選擇一個(gè)進(jìn)入臨界區(qū)，有的進(jìn)程可能一直選不上區(qū)，有的進(jìn)程可能一直選不上 可能死鎖可能死鎖Synchronization Hardware7.4 進(jìn)程的同步機(jī)制進(jìn)程的同步機(jī)制 進(jìn)程在并發(fā)執(zhí)行時(shí)為了保證結(jié)果的可再現(xiàn)性，對(duì)各進(jìn)進(jìn)程在并發(fā)執(zhí)行

22、時(shí)為了保證結(jié)果的可再現(xiàn)性，對(duì)各進(jìn)程的執(zhí)行次序必須加以限制程的執(zhí)行次序必須加以限制,以保證互斥地使用臨界以保證互斥地使用臨界資源，相互合作完成任務(wù)。資源，相互合作完成任務(wù)。l前面的互斥算法都存在問(wèn)題，它們是平等進(jìn)程間的一前面的互斥算法都存在問(wèn)題，它們是平等進(jìn)程間的一種協(xié)商機(jī)制，需要一個(gè)地位高于進(jìn)程的管理者來(lái)解決種協(xié)商機(jī)制，需要一個(gè)地位高于進(jìn)程的管理者來(lái)解決公有資源的使用問(wèn)題。公有資源的使用問(wèn)題。 多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)稱為進(jìn)程同步。多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)稱為進(jìn)程同步。 用于保證多個(gè)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)關(guān)系的相應(yīng)機(jī)用于保證多個(gè)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)關(guān)系的相應(yīng)機(jī)制稱為進(jìn)程同步機(jī)制。

23、制稱為進(jìn)程同步機(jī)制。Semaphore信號(hào)量信號(hào)量lOS從進(jìn)程管理者的角度來(lái)處理互斥的問(wèn)題，信從進(jìn)程管理者的角度來(lái)處理互斥的問(wèn)題，信號(hào)量就是號(hào)量就是OS提供的管理公有資源的有效手段。提供的管理公有資源的有效手段。l1965年，信號(hào)量由荷蘭學(xué)者年，信號(hào)量由荷蘭學(xué)者Dijkstra提出（所提出（所以以P、V分別是荷蘭語(yǔ)的分別是荷蘭語(yǔ)的test(proberen)和和increment(verhogen)），），是一種卓有成效的進(jìn)程是一種卓有成效的進(jìn)程同步機(jī)制同步機(jī)制。Semaphore Implementation With busy wait : Atomicity Entire wait (S

24、) must be atomic How? Disable interrupts Or use another mutex solution, e.g., lockSemaphore Implementation with no Busy waiting With each semaphore there is an associated waiting queue. A waiting queue has two data items: value (of type integer) pointer to a list of PCBs Introduce a pointer in the P

25、CB structure Two operations: block place the process invoking the operation on the appropriate waiting queue. wakeup remove one of processes in the waiting queue and place it in the ready queue. FIFO ordering = bounded-waiting Is busy waiting completely gone? Semaphore Implementation with no Busy wa

26、iting (Cont.)Implementation of wait: wait (S) value-; if (value 0) add this process to waiting queue block(); Implementation of signal: Signal (S) value+; if (value = 0) remove a process P from the waiting queue wakeup(P); Semaphore Implementation with no Busy waiting: Atomicity Implementation of wa

27、it: wait (S) value-; if (value 0) add this process to waiting queue block(); Implementation of signal: Signal (S) value+; if (value = 0) remove a process P from the waiting queue wakeup(P); How to make these atomic?Semaphore Implementation with no Busy waiting: Atomicity Uniprocessors Disable interr

28、upts during wait and signal Once interrupts are disabled, instructions from different processes cannot be interleaved. Only the currently running process executes until interrupts are re-enabled and the scheduler can regain control. Multi-processors Inhibiting interrupts does not work Instructions f

29、rom different processes (running on different processors) may be interleaved in some arbitrary way If the hardware does not provide any special instructions, we can employ any of the correct software solutions (e.g., Petersons, Bakery) for the critical-section problem, where the critical sections co

30、nsist of the wait and signal operations (EXTREMELY COOL) So, we have not completely eliminated busy waiting with this definition of wait and signal We have moved busy waiting to the critical sections Furthermore, we have limited busy waiting to the critical sections of wait and signalSemaphore Imple

31、mentation with no Busy waiting: Atomicity Uniprocessors Disable interrupts during wait and signal Once interrupts are disabled, instructions from different processes cannot be interleaved. Only the currently running process executes until interrupts are re-enabled and the scheduler can regain contro

32、l. Multi-processors Inhibiting interrupts does not work Instructions from different processes (running on different processors) may be interleaved in some arbitrary way If the hardware does not provide any special instructions, we can employ any of the correct software solutions (e.g., Petersons, Ba

33、kery) for the critical-section problem, where the critical sections consist of the wait and signal operations (EXTREMELY COOL) So, we have not completely eliminated busy waiting with this definition of wait and signal We have moved busy waiting to the critical sections Furthermore, we have limited b

34、usy waiting to the critical sections of wait and signalSemaphore Implementation with no Busy waiting: Atomicity Uniprocessors Disable interrupts during wait and signal Once interrupts are disabled, instructions from different processes cannot be interleaved. Only the currently running process execut

35、es until interrupts are re-enabled and the scheduler can regain control. Multi-processors Inhibiting interrupts does not work Instructions from different processes (running on different processors) may be interleaved in some arbitrary way If the hardware does not provide any special instructions, we

36、 can employ any of the correct software solutions (e.g., Petersons) for the critical-section problem, where the critical sections consist of the wait and signal operations (EXTREMELY COOL) So, we have not completely eliminated busy waiting with this definition of wait and signal We have moved busy w

37、aiting to the critical sections Furthermore, we have limited busy waiting to the critical sections of wait and signal信號(hào)量和信號(hào)量和P、V原語(yǔ)原語(yǔ) S是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號(hào)量是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號(hào)量 S0 可供并發(fā)進(jìn)程使用的資源數(shù)可供并發(fā)進(jìn)程使用的資源數(shù) S=1 & S2 = 1 & & Sn = 1) /滿足資源要求時(shí)的處理；滿足資源要求時(shí)的處理； for (i = 1; i = n; +i) -Si; /注：與注：與wait的處理不同，這里是

38、在確信可滿足的處理不同，這里是在確信可滿足 /全部資源要求時(shí)，才進(jìn)行減全部資源要求時(shí)，才進(jìn)行減1操作；操作； break; else /某些資源不夠時(shí)的處理；某些資源不夠時(shí)的處理； 進(jìn)程進(jìn)入第一個(gè)小于進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列信號(hào)量的等待隊(duì)列Sj.queue; 阻塞調(diào)用進(jìn)程阻塞調(diào)用進(jìn)程; AND型信號(hào)量集型信號(hào)量集 Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si;/釋放占用的資源；釋放占用的資源； for (each process P waiting in Si.queue) /檢查每種資源的等待隊(duì)列；檢查每種資源的等待隊(duì)列； 從等

39、待隊(duì)列從等待隊(duì)列Si.queue中取出進(jìn)程中取出進(jìn)程P; if (判斷進(jìn)程判斷進(jìn)程P是否通過(guò)是否通過(guò)Swait中的測(cè)試中的測(cè)試) /注：與注：與signal不同，這里要進(jìn)行重新判斷；不同，這里要進(jìn)行重新判斷； /通過(guò)檢查（資源夠用）時(shí)的處理；通過(guò)檢查（資源夠用）時(shí)的處理； 進(jìn)程進(jìn)程P進(jìn)入就緒隊(duì)列進(jìn)入就緒隊(duì)列; else /未通過(guò)檢查（資源不夠用）時(shí)的處理；未通過(guò)檢查（資源不夠用）時(shí)的處理； 進(jìn)程進(jìn)程P進(jìn)入某等待隊(duì)列；進(jìn)入某等待隊(duì)列； AND型信號(hào)量集型信號(hào)量集一般信號(hào)量集一般信號(hào)量集l一般信號(hào)量集用于同時(shí)需要多種資源、每種占用的數(shù)目不同、且可一般信號(hào)量集用于同時(shí)需要多種資源、每種占用的數(shù)目不同

40、、且可分配的資源還存在一個(gè)臨界值時(shí)的處理；分配的資源還存在一個(gè)臨界值時(shí)的處理；l一次需要一次需要N個(gè)某類臨界資源時(shí)，就要進(jìn)行個(gè)某類臨界資源時(shí)，就要進(jìn)行N次次wait操作低效又操作低效又可能死鎖可能死鎖l基本思想：在基本思想：在AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充：進(jìn)程對(duì)信號(hào)量型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充：進(jìn)程對(duì)信號(hào)量Si的測(cè)試值為的測(cè)試值為ti（用于信號(hào)量的判斷，即用于信號(hào)量的判斷，即Si =1時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)；時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)； 當(dāng)當(dāng)S=0時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)；時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)；一般信號(hào)量集未必成對(duì)使用一般信號(hào)量集未必成對(duì)使用Swait和和Ssignal：如：一

41、起申請(qǐng)，但不如：一起申請(qǐng)，但不一起釋放；一起釋放；一般信號(hào)量集一般信號(hào)量集Semaphore機(jī)制機(jī)制l同步、互斥的約束條件同步、互斥的約束條件l臨界資源的抽象臨界資源的抽象l初始條件初始條件l正確的正確的P-V操作操作7.5 Classical Problems of Synchronization Dining-Philosophers Problem （哲學(xué)家就餐問(wèn)題）（哲學(xué)家就餐問(wèn)題） Bounded-Buffer Problem （有限緩沖區(qū)問(wèn)題）（有限緩沖區(qū)問(wèn)題） Readers and Writers Problem （讀者寫者問(wèn)題）（讀者寫者問(wèn)題）7.5.1 哲學(xué)家進(jìn)餐問(wèn)題哲學(xué)家

42、進(jìn)餐問(wèn)題(the dining philosophers problem)l問(wèn)題描述：（由問(wèn)題描述：（由Dijkstra首先提出并解決）首先提出并解決）5個(gè)哲個(gè)哲學(xué)家圍繞一張圓桌而坐，桌子上放著學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每支筷子，每?jī)蓚€(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括思考和兩個(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？哲學(xué)家們的動(dòng)作有序進(jìn)行？Dining-Philosophers

43、ProblemShared data Semaphore chopStick = new Semaphore5;Repeat 思考；思考； 取取chopSticki; 取取chopStick(i+1) mod 5； 進(jìn)食；進(jìn)食； 放放chopSticki; 放放chopStick(i+1) mod 5；Until false;Philosopher(i)Dining-Philosophers Problem (Cont.)Philosopher i:while (true) / get left chopstickchopSticki.P();/ get right chopstickchop

44、Stick(i + 1) % 5.P();/ eat for a while/return left chopstick chopSticki.V();/ return right chopstick chopStick(i + 1) % 5.V();/ think for awhileDining-Philosophers Problem (Cont.) The structure of Philosopher i:do wait ( chopsticki ); wait ( chopStick (i + 1) % 5 ); / eat signal ( chopsticki ); sign

45、al (chopstick (i + 1) % 5 ); / think while (TRUE);Deadlock? Starvation?What happens if all pick their left chopsticks?為防止死鎖發(fā)生可采取的措施： 最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周圍 僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子（） 給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之 為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿 state:array0.4 of (思考，饑餓，進(jìn)食）； ph: array

46、0.4 of semaphore; mutex:semaphore; i:0.4;Procedure test(i:=04); begin if (state i = 饑餓饑餓) And (state(i-1)mod5進(jìn)食進(jìn)食) And (state(i+1)mod5進(jìn)食進(jìn)食) then begin state i =進(jìn)食進(jìn)食 V(ph i ) end endProcedure philosopher(i: 04) Begin Repeat 思考；思考； statei :=饑餓；饑餓； P(mutex); test(i); V(mutex); P(ph i ); 拿左筷子；拿左筷子； 拿右筷子

47、；拿右筷子； 進(jìn)食；進(jìn)食； 放左筷子；放左筷子； 放右筷子；放右筷子；P(mutex)state i :=思考；思考；test(i-1mod5);tset(i+1mod5);V(mutex);until falesEndstate I =思考思考ph I =0mutex=1解法：解法：AND型信號(hào)量型信號(hào)量Var chopstick array0,4 of semaphore :=(1,1,1,1,1);Processi Reeat think; Swait (chopstick(I+1) mod 5,chopstickI); Eat; Ssignal (chopstick(I+1) mod

48、5,chopstickI); Until false;7.5.2 生產(chǎn)者消費(fèi)者問(wèn)題生產(chǎn)者消費(fèi)者問(wèn)題(the producer-consumer problem)l若干進(jìn)程通過(guò)若干進(jìn)程通過(guò)有限有限的共享緩沖區(qū)交換數(shù)據(jù)。的共享緩沖區(qū)交換數(shù)據(jù)。-“生產(chǎn)者生產(chǎn)者”進(jìn)程不斷寫入進(jìn)程不斷寫入-“消費(fèi)者消費(fèi)者”進(jìn)程不斷讀出進(jìn)程不斷讀出-共享緩沖區(qū)共有共享緩沖區(qū)共有N個(gè)個(gè)-任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作共享緩沖區(qū)生產(chǎn)指針消費(fèi)指針Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N滿

49、空指針移動(dòng)方向采用信號(hào)量機(jī)制：采用信號(hào)量機(jī)制： full是是滿滿數(shù)目，初值為數(shù)目，初值為0，empty是是空空數(shù)目，初值為數(shù)目，初值為N。實(shí)際實(shí)際上，上，full + empty = N mutex用于訪問(wèn)緩沖區(qū)時(shí)的互斥，初值是用于訪問(wèn)緩沖區(qū)時(shí)的互斥，初值是1 每個(gè)進(jìn)程中各個(gè)每個(gè)進(jìn)程中各個(gè)P操作的次序是重要的：先檢查資源數(shù)目，再檢操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥查是否互斥否則可能死鎖否則可能死鎖采用采用AND信號(hào)量集：信號(hào)量集：Swait(empty, mutex), Ssignal(full, mutex), 7.5.2 生產(chǎn)者消費(fèi)者問(wèn)題生產(chǎn)者消費(fèi)者問(wèn)題(the produ

50、cer-consumer problem)ConsumerProducerP(empty);P(mutex);/進(jìn)入?yún)^(qū) one unit - buffer;V(mutex);V(full);/退出區(qū)P(full);P(mutex);/進(jìn)入?yún)^(qū) one unit 0表示有表示有S個(gè)資源可用個(gè)資源可用 S=0表示無(wú)資源可用表示無(wú)資源可用 S= n then notfull.wait ; buffer ( in ) : = nextp ; in := (in+1) mod n ; count = count + 1 ; if notempty.queue then notempty.signal ;

51、end procedure entry get ( item) begin if count = 0 then notempty.wait ; nextc := buffer ( out ) ; out := (out+1) mod n ; count := count - 1 ;if notfull.queue then notfull.signal ; end begin in := out := 0 ; count := 0; end producer : begin repeat produce an item in nextp ; PC.put ( item) ; until false ; endconsumer : begin repeat PC.get (item) ; consume the item in nextc ; until false ; end利用管程解決生產(chǎn)者利用管程解決生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題Solution to Dining Philosophersmonit