第五章 并發(fā)性：互斥和同步浙江工業(yè)大學(xué)

1、1并發(fā)性：互斥和同步并發(fā)性：互斥和同步第五章第五章2并發(fā)并發(fā) (Concurrency)多道程序設(shè)計(jì)技術(shù)、多處理器技術(shù)以及分多道程序設(shè)計(jì)技術(shù)、多處理器技術(shù)以及分布式處理技術(shù)使得操作系統(tǒng)設(shè)計(jì)時(shí)必須布式處理技術(shù)使得操作系統(tǒng)設(shè)計(jì)時(shí)必須要面對(duì)多個(gè)進(jìn)程并發(fā)的問(wèn)題，設(shè)計(jì)時(shí)需要面對(duì)多個(gè)進(jìn)程并發(fā)的問(wèn)題，設(shè)計(jì)時(shí)需要考慮下列問(wèn)題：要考慮下列問(wèn)題：并發(fā)進(jìn)程間如何通信？并發(fā)進(jìn)程間如何通信？怎么解決資源的共享和競(jìng)爭(zhēng)？怎么解決資源的共享和競(jìng)爭(zhēng)？多個(gè)進(jìn)程之間如何同步？多個(gè)進(jìn)程之間如何同步？處理器的時(shí)間如何分配？處理器的時(shí)間如何分配？3并發(fā)進(jìn)程間的制約關(guān)系并發(fā)進(jìn)程間的制約關(guān)系 在多道程序環(huán)境下，在多道程序環(huán)境下，系統(tǒng)中各進(jìn)程

2、以不可預(yù)測(cè)的系統(tǒng)中各進(jìn)程以不可預(yù)測(cè)的速度向前推進(jìn)，進(jìn)程的異步性會(huì)造成結(jié)果的不可再速度向前推進(jìn)，進(jìn)程的異步性會(huì)造成結(jié)果的不可再現(xiàn)性現(xiàn)性。為防止這種現(xiàn)象，異步的進(jìn)程間推進(jìn)受到兩。為防止這種現(xiàn)象，異步的進(jìn)程間推進(jìn)受到兩種限制：種限制： 1. 1.資源共享關(guān)系資源共享關(guān)系 多進(jìn)程共享資源，例如各進(jìn)程爭(zhēng)用一臺(tái)打印機(jī)，多進(jìn)程共享資源，例如各進(jìn)程爭(zhēng)用一臺(tái)打印機(jī)，這時(shí)各進(jìn)程使用這臺(tái)打印機(jī)時(shí)有一定的限制。每次這時(shí)各進(jìn)程使用這臺(tái)打印機(jī)時(shí)有一定的限制。每次只允許一個(gè)進(jìn)程使用一段時(shí)間打印機(jī)，等該進(jìn)程使只允許一個(gè)進(jìn)程使用一段時(shí)間打印機(jī)，等該進(jìn)程使用完畢后再將打印機(jī)分配給其它進(jìn)程。這種使用原用完畢后再將打印機(jī)分配給其它進(jìn)

3、程。這種使用原則稱為則稱為互斥使用互斥使用。4 進(jìn)程之間競(jìng)爭(zhēng)資源面臨三個(gè)控制問(wèn)題：進(jìn)程之間競(jìng)爭(zhēng)資源面臨三個(gè)控制問(wèn)題： 互斥互斥（ mutual exclusion )mutual exclusion )指多個(gè)進(jìn)程不能同時(shí)指多個(gè)進(jìn)程不能同時(shí)使用同一個(gè)資源；使用同一個(gè)資源； 死鎖死鎖（ deadlock )指多個(gè)進(jìn)程互不相讓，都得不到指多個(gè)進(jìn)程互不相讓，都得不到足夠的資源；足夠的資源； 饑餓饑餓（ starvation )指一個(gè)進(jìn)程一直得不到資源（其指一個(gè)進(jìn)程一直得不到資源（其他進(jìn)程可能輪流占用資源）他進(jìn)程可能輪流占用資源） 2. 2.相互合作關(guān)系相互合作關(guān)系 在某些進(jìn)程之間還存在合作關(guān)系，例如一

4、個(gè)程序在某些進(jìn)程之間還存在合作關(guān)系，例如一個(gè)程序的輸入、計(jì)算、打印三個(gè)程序段作為三個(gè)進(jìn)程并發(fā)執(zhí)的輸入、計(jì)算、打印三個(gè)程序段作為三個(gè)進(jìn)程并發(fā)執(zhí)行，由于這三個(gè)進(jìn)程間存在著相互合作的關(guān)系，即先行，由于這三個(gè)進(jìn)程間存在著相互合作的關(guān)系，即先輸入再計(jì)算、最后再打印的關(guān)系，所以這三個(gè)進(jìn)程在輸入再計(jì)算、最后再打印的關(guān)系，所以這三個(gè)進(jìn)程在并發(fā)執(zhí)行時(shí)推進(jìn)序列受到限制，要保證其合作關(guān)系正并發(fā)執(zhí)行時(shí)推進(jìn)序列受到限制，要保證其合作關(guān)系正確，進(jìn)程間這種關(guān)系稱為確，進(jìn)程間這種關(guān)系稱為同步關(guān)系同步關(guān)系。5一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子void echo()chin = getchar();chout = chin;putch

5、ar(chout); 6Process P1Process P2. .chin = getchar(); . chin = getchar();. chout = chin;. putchar(chout);chout = chin; putchar(chout);發(fā)生中斷發(fā)生中斷P1輸入輸入x，P2輸入輸入y結(jié)果：結(jié)果：y顯示了兩次，而顯示了兩次，而x沒有顯示沒有顯示原因：原因：chin是共享的全局變量是共享的全局變量一個(gè)簡(jiǎn)單的例子一個(gè)簡(jiǎn)單的例子7解決辦法解決辦法控制訪問(wèn)共享資源。控制訪問(wèn)共享資源。必須強(qiáng)加一條規(guī)則：一次只允許一個(gè)必須強(qiáng)加一條規(guī)則：一次只允許一個(gè)進(jìn)程訪問(wèn)共享資源。（互斥）進(jìn)程

6、訪問(wèn)共享資源。（互斥）8和并發(fā)相關(guān)的術(shù)語(yǔ)和并發(fā)相關(guān)的術(shù)語(yǔ)表表5.1 與并發(fā)相關(guān)的關(guān)鍵術(shù)語(yǔ)與并發(fā)相關(guān)的關(guān)鍵術(shù)語(yǔ)9臨界資源臨界資源 象打印機(jī)這類資源一次只允許一個(gè)進(jìn)程使用的資象打印機(jī)這類資源一次只允許一個(gè)進(jìn)程使用的資源稱為源稱為臨界資源臨界資源。屬于臨界資源的有硬件打印機(jī)、磁。屬于臨界資源的有硬件打印機(jī)、磁帶機(jī)等，軟件有消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)帶機(jī)等，軟件有消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)等。當(dāng)然還有一類象磁盤等資源，它允許進(jìn)程間共享，等。當(dāng)然還有一類象磁盤等資源，它允許進(jìn)程間共享，即可交替使用，所以它稱為即可交替使用，所以它稱為共享資源共享資源，而臨界資源又，而臨界資源又稱獨(dú)享資源。稱獨(dú)

7、享資源。10臨界區(qū)臨界區(qū)(critical sections)(critical sections) 多個(gè)進(jìn)程共享臨界資源時(shí)必須互斥使用，將程序多個(gè)進(jìn)程共享臨界資源時(shí)必須互斥使用，將程序中使用臨界資源的那一段代碼稱為臨界區(qū)。中使用臨界資源的那一段代碼稱為臨界區(qū)。 如二個(gè)進(jìn)程如二個(gè)進(jìn)程A A和和B B它們的程序如下：它們的程序如下： A: A: Input data 1 from I/O 1 ; Input data 1 from I/O 1 ; Computer; Computer; Print results 1 by printer ; APrint results 1 by printe

8、r ; A臨界區(qū)臨界區(qū) B: B: Input data 1 from I/O 2 ; Input data 1 from I/O 2 ; Computer; Computer; Print results 2 by printer ; BPrint results 2 by printer ; B臨界區(qū)臨界區(qū) 進(jìn)程進(jìn)程A和和B必須互必須互斥地分別進(jìn)入各斥地分別進(jìn)入各自的臨界區(qū)自的臨界區(qū)A和和B11競(jìng)爭(zhēng)條件競(jìng)爭(zhēng)條件 多個(gè)進(jìn)程或線程在讀寫一個(gè)共享數(shù)據(jù)時(shí)，結(jié)果多個(gè)進(jìn)程或線程在讀寫一個(gè)共享數(shù)據(jù)時(shí)，結(jié)果依賴于它們執(zhí)行的相對(duì)時(shí)間，這種情形叫競(jìng)爭(zhēng)。依賴于它們執(zhí)行的相對(duì)時(shí)間，這種情形叫競(jìng)爭(zhēng)。 例例1: 兩個(gè)

9、進(jìn)程兩個(gè)進(jìn)程p1和和P2，共享同一個(gè)全局變量，共享同一個(gè)全局變量a。 P1和和P2同時(shí)更新同時(shí)更新a，因此兩個(gè)進(jìn)程競(jìng)爭(zhēng)地寫變，因此兩個(gè)進(jìn)程競(jìng)爭(zhēng)地寫變量量a。a=？ 例例2:兩個(gè)進(jìn)程兩個(gè)進(jìn)程P3和和P4，P3:b=b+c, P4:c=b+c (初始值初始值b=1,c=2)。若。若P3先執(zhí)行先執(zhí)行,則結(jié)果為則結(jié)果為b=3,c=5; 若若P4先執(zhí)行，則結(jié)果為先執(zhí)行，則結(jié)果為 b=4,c=312操作系統(tǒng)關(guān)注的問(wèn)題操作系統(tǒng)關(guān)注的問(wèn)題跟蹤每個(gè)進(jìn)程的信息：通過(guò)跟蹤每個(gè)進(jìn)程的信息：通過(guò)PCB為進(jìn)程分配和釋放各種資源為進(jìn)程分配和釋放各種資源處理器時(shí)間：進(jìn)程調(diào)度處理器時(shí)間：進(jìn)程調(diào)度內(nèi)存：內(nèi)存管理內(nèi)存：內(nèi)存管理文件

10、：文件系統(tǒng)文件：文件系統(tǒng)I/O 設(shè)備：設(shè)備：I/O管理管理保護(hù)進(jìn)程的數(shù)據(jù)和資源，避免其他進(jìn)程的干保護(hù)進(jìn)程的數(shù)據(jù)和資源，避免其他進(jìn)程的干擾擾一個(gè)進(jìn)程的功能和輸出結(jié)果必須與執(zhí)行速度一個(gè)進(jìn)程的功能和輸出結(jié)果必須與執(zhí)行速度無(wú)關(guān)（進(jìn)程同步機(jī)制）無(wú)關(guān)（進(jìn)程同步機(jī)制）13多個(gè)進(jìn)程的交互多個(gè)進(jìn)程的交互進(jìn)程間相互不知道對(duì)方：進(jìn)程間相互不知道對(duì)方：獨(dú)立的進(jìn)程，獨(dú)立的進(jìn)程，存在著資源競(jìng)爭(zhēng)關(guān)系，會(huì)帶來(lái)互斥、死存在著資源競(jìng)爭(zhēng)關(guān)系，會(huì)帶來(lái)互斥、死鎖和饑餓的問(wèn)題鎖和饑餓的問(wèn)題進(jìn)程間通過(guò)共享對(duì)象間接知道對(duì)方：進(jìn)程間通過(guò)共享對(duì)象間接知道對(duì)方：帶帶來(lái)互斥、死鎖、饑餓和數(shù)據(jù)一致性的問(wèn)來(lái)互斥、死鎖、饑餓和數(shù)據(jù)一致性的問(wèn)題題進(jìn)程直接知

11、道對(duì)方：進(jìn)程直接知道對(duì)方：進(jìn)程間通過(guò)通信合進(jìn)程間通過(guò)通信合作，會(huì)帶來(lái)死鎖和饑餓的問(wèn)題作，會(huì)帶來(lái)死鎖和饑餓的問(wèn)題14進(jìn)程同步機(jī)制進(jìn)程同步機(jī)制進(jìn)程在并發(fā)執(zhí)行時(shí)為了保證結(jié)果的可再現(xiàn)進(jìn)程在并發(fā)執(zhí)行時(shí)為了保證結(jié)果的可再現(xiàn)性，各進(jìn)程執(zhí)行序列必須加以限制以保證性，各進(jìn)程執(zhí)行序列必須加以限制以保證互斥地使用臨界資源，相互合作完成任務(wù)。互斥地使用臨界資源，相互合作完成任務(wù)。多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)稱為多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)稱為進(jìn)進(jìn)程同步程同步。用于保證多個(gè)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)關(guān)用于保證多個(gè)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)關(guān)系的相應(yīng)機(jī)制稱為系的相應(yīng)機(jī)制稱為進(jìn)程同步機(jī)制進(jìn)程同步機(jī)制。15所有的進(jìn)程同步機(jī)制應(yīng)遵

12、循下述四條準(zhǔn)則：所有的進(jìn)程同步機(jī)制應(yīng)遵循下述四條準(zhǔn)則：l空閑讓進(jìn)空閑讓進(jìn) 當(dāng)無(wú)進(jìn)程進(jìn)入臨界區(qū)時(shí)，相應(yīng)的臨界資源處于空閑狀態(tài)，當(dāng)無(wú)進(jìn)程進(jìn)入臨界區(qū)時(shí)，相應(yīng)的臨界資源處于空閑狀態(tài)，因而允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界因而允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)。區(qū)。l忙則等待忙則等待 當(dāng)已有進(jìn)程進(jìn)入自己的臨界區(qū)時(shí)，即相應(yīng)的臨界資源正當(dāng)已有進(jìn)程進(jìn)入自己的臨界區(qū)時(shí)，即相應(yīng)的臨界資源正被訪問(wèn)，其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證進(jìn)被訪問(wèn)，其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證進(jìn)程互斥地訪問(wèn)臨界資源。程互斥地訪問(wèn)臨界資源。 l有限等待有限等待 對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證進(jìn)程

13、能在有限時(shí)間對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證進(jìn)程能在有限時(shí)間進(jìn)入臨界區(qū)，以免陷入進(jìn)入臨界區(qū)，以免陷入“饑餓饑餓”狀態(tài)。狀態(tài)。l讓權(quán)等待讓權(quán)等待 當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入忙等。以免進(jìn)程陷入忙等。16臨界區(qū)的互斥操作臨界區(qū)的互斥操作17l 一個(gè)由臨界區(qū)和剩余區(qū)一個(gè)由臨界區(qū)和剩余區(qū)1 1和剩余區(qū)和剩余區(qū)2 2程序段組成的進(jìn)程序段組成的進(jìn)程采用進(jìn)程同步機(jī)制后的描述如下：程采用進(jìn)程同步機(jī)制后的描述如下： begin remainder section 1begin remainder section 1； 剩余區(qū)剩余區(qū)1

14、 1 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) critical section critical section ； 臨界區(qū)臨界區(qū) 退出區(qū)退出區(qū) remainder section 2 remainder section 2 ； 剩余區(qū)剩余區(qū)2 2 end end 進(jìn)程同步機(jī)制在臨界區(qū)前加上進(jìn)入?yún)^(qū)，它負(fù)責(zé)對(duì)欲進(jìn)程同步機(jī)制在臨界區(qū)前加上進(jìn)入?yún)^(qū)，它負(fù)責(zé)對(duì)欲訪問(wèn)的臨界資源狀態(tài)進(jìn)行檢查，以決定是否允許該訪問(wèn)的臨界資源狀態(tài)進(jìn)行檢查，以決定是否允許該進(jìn)程進(jìn)入臨界區(qū)還是等待。同時(shí)在臨界區(qū)后加上退進(jìn)程進(jìn)入臨界區(qū)還是等待。同時(shí)在臨界區(qū)后加上退出區(qū)，它負(fù)責(zé)釋放臨界資源以便其它等待該臨界資出區(qū)，它負(fù)責(zé)釋放臨界資源以便其它等待該臨界資源的進(jìn)程

15、使用。源的進(jìn)程使用。18Const int n=/*進(jìn)程的數(shù)目進(jìn)程的數(shù)目*/Void p(int i) while(true) entercritical(Ra);/進(jìn)入臨界區(qū)進(jìn)入臨界區(qū) /*critical section*/ exitcritical(Ra);/退出臨界區(qū)退出臨界區(qū) /*remainder*/ Void main() parbegin(p(1),p(2),p(n);當(dāng)有進(jìn)程在臨界區(qū)時(shí)，任當(dāng)有進(jìn)程在臨界區(qū)時(shí)，任何其他想要訪問(wèn)臨界區(qū)的何其他想要訪問(wèn)臨界區(qū)的進(jìn)程必須等待進(jìn)程必須等待19互斥的三種實(shí)現(xiàn)方法互斥的三種實(shí)現(xiàn)方法 軟件方法軟件方法：由進(jìn)程本身負(fù)責(zé)實(shí)施互斥，不需要操：由進(jìn)程

16、本身負(fù)責(zé)實(shí)施互斥，不需要操作系統(tǒng)支持。作系統(tǒng)支持。增加一定的開銷增加一定的開銷硬件方法：硬件方法：使用專門的機(jī)器指令來(lái)實(shí)現(xiàn)互斥。使用專門的機(jī)器指令來(lái)實(shí)現(xiàn)互斥。 可減少開銷，但依賴于硬件，難以成為通用的可減少開銷，但依賴于硬件，難以成為通用的解決辦法解決辦法操作系統(tǒng)層提供支持解決互斥操作系統(tǒng)層提供支持解決互斥 信號(hào)量機(jī)制、管程機(jī)制和消息傳遞機(jī)制信號(hào)量機(jī)制、管程機(jī)制和消息傳遞機(jī)制20互斥：軟件支持互斥：軟件支持Dekker 算法算法第一次嘗試第一次嘗試int turn=0;Process 0 Process 1. .While(turn!=0) While(turn!=1)do nothing d

17、o nothing/*critical section*/ /*critical section*/turn=1; turn=0;實(shí)現(xiàn)方法：若實(shí)現(xiàn)方法：若turn值等于該進(jìn)程的進(jìn)程號(hào)，則該進(jìn)值等于該進(jìn)程的進(jìn)程號(hào)，則該進(jìn)程可以進(jìn)入臨界區(qū)執(zhí)行。程可以進(jìn)入臨界區(qū)執(zhí)行。21第二次嘗試：每個(gè)進(jìn)程都有自己可進(jìn)入臨界區(qū)第二次嘗試：每個(gè)進(jìn)程都有自己可進(jìn)入臨界區(qū)的鑰匙。的鑰匙。 enum booleanfalse=0;true=1;boolean flag2=false,falseProcess 0 Process 1. .While(flag1) While(flag0)do nothing do nothi

18、ngflag0=true; flag1=true;/*critical section*/ /*critical section*/flag0=false; flag1=false; 互斥：軟件支持互斥：軟件支持22第三次嘗試：第三次嘗試：可能導(dǎo)致死鎖可能導(dǎo)致死鎖enum booleanfalse=0;true=1;boolean flag2=false,falseProcess 0 Process 1. .flag0=true; flag1=true; While(flag1) While(flag0)do nothing do nothing/*critical section*/ /*c

19、ritical section*/flag0=false; flag1=false; 互斥：軟件支持互斥：軟件支持23第四次嘗試：第四次嘗試：導(dǎo)致活鎖導(dǎo)致活鎖enum booleanfalse=0;true=1;boolean flag2=false,falseProcess 0 Process 1. .flag0=true; flag1=true; While(flag1) While(flag0)flag0=false; flag1=false; /*延遲一段時(shí)間延遲一段時(shí)間*/ /*延遲一段時(shí)間延遲一段時(shí)間*/ flag0=true; flag1=true;/*critical sect

20、ion*/ /*critical section*/flag0=false; flag1=flase; 互斥：軟件支持互斥：軟件支持24Peterson算法算法 boolean flag2;int turn;Void P0() Void P1() while(true) while(true) flag0=true; flag1=true; turn=1; turn=0; While(flag1 &turn=1) While(flag0 &turn=0) /* do nothing*/ /* do nothing*/*critical section*/ /*critical

21、section*/flag0=false; flag1=false; 互斥：軟件支持互斥：軟件支持25中斷禁用中斷禁用 (Interrupt Disabling)單處理器情況下，并發(fā)進(jìn)程交替執(zhí)行。處于運(yùn)行狀單處理器情況下，并發(fā)進(jìn)程交替執(zhí)行。處于運(yùn)行狀態(tài)的進(jìn)程只有調(diào)用系統(tǒng)服務(wù)或被中斷時(shí)才會(huì)將控制態(tài)的進(jìn)程只有調(diào)用系統(tǒng)服務(wù)或被中斷時(shí)才會(huì)將控制權(quán)交給操作系統(tǒng)。權(quán)交給操作系統(tǒng)。為保證對(duì)臨界區(qū)的互斥，只要保證進(jìn)程在臨界區(qū)內(nèi)為保證對(duì)臨界區(qū)的互斥，只要保證進(jìn)程在臨界區(qū)內(nèi)不被中斷即可。不被中斷即可。通過(guò)系統(tǒng)內(nèi)核啟用中斷和禁用中斷的原語(yǔ)來(lái)實(shí)現(xiàn)。通過(guò)系統(tǒng)內(nèi)核啟用中斷和禁用中斷的原語(yǔ)來(lái)實(shí)現(xiàn)。缺陷：缺陷：處理器執(zhí)行效率

22、降低處理器執(zhí)行效率降低對(duì)于多處理器環(huán)境下，無(wú)法保證互斥對(duì)于多處理器環(huán)境下，無(wú)法保證互斥互斥：硬件支持互斥：硬件支持26特殊的機(jī)器指令特殊的機(jī)器指令在單個(gè)指令周期內(nèi)執(zhí)行，是原子性的指在單個(gè)指令周期內(nèi)執(zhí)行，是原子性的指令（不能被中斷）令（不能被中斷）在該指令執(zhí)行時(shí)，任何需要訪問(wèn)內(nèi)存的在該指令執(zhí)行時(shí)，任何需要訪問(wèn)內(nèi)存的其他指令都將被阻塞其他指令都將被阻塞兩種常見的指令：兩種常見的指令：Testset和和exchange指令指令互斥：硬件支持互斥：硬件支持27boolean testset (int i) if (i = 0) i = 1; return true; else return false

23、; i相當(dāng)于鎖值，相當(dāng)于鎖值，i=0表示表示當(dāng)前該臨界區(qū)未被訪當(dāng)前該臨界區(qū)未被訪問(wèn)問(wèn)Testset指令指令28void exchange(int register, int memory) int temp;temp = memory;memory = register;register = temp;交換存儲(chǔ)器單元和寄交換存儲(chǔ)器單元和寄存器單元的內(nèi)容存器單元的內(nèi)容Exchange指令指令29發(fā)現(xiàn)發(fā)現(xiàn)bolt=0的進(jìn)程是惟的進(jìn)程是惟一可以進(jìn)入臨界區(qū)的進(jìn)一可以進(jìn)入臨界區(qū)的進(jìn)程程30優(yōu)點(diǎn)優(yōu)點(diǎn)適用于在單處理器或共享內(nèi)存的多處理器上適用于在單處理器或共享內(nèi)存的多處理器上任何數(shù)目的進(jìn)程任何數(shù)目的進(jìn)程非常

24、簡(jiǎn)單且易于證明非常簡(jiǎn)單且易于證明可用于支持多個(gè)臨界區(qū)可用于支持多個(gè)臨界區(qū)缺點(diǎn)缺點(diǎn)忙等待忙等待 可能饑餓：可能饑餓：多個(gè)進(jìn)程等待進(jìn)入臨界區(qū)，選擇多個(gè)進(jìn)程等待進(jìn)入臨界區(qū)，選擇哪個(gè)進(jìn)程是隨機(jī)的哪個(gè)進(jìn)程是隨機(jī)的 可能死鎖：可能死鎖：考慮優(yōu)先級(jí)情況考慮優(yōu)先級(jí)情況硬件方法31信號(hào)量信號(hào)量(Semaphores)機(jī)制機(jī)制 1965年，由荷蘭年，由荷蘭學(xué)者學(xué)者Dijkstra提出（提出（P、V分別是荷蘭語(yǔ)的分別是荷蘭語(yǔ)的test(proberen)和和increment(verhogen)一種卓有成效的進(jìn)程同步機(jī)一種卓有成效的進(jìn)程同步機(jī)制。制。 最初提出的是二元最初提出的是二元信號(hào)量（互斥）信號(hào)量（互斥）,

25、推廣到推廣到一般信號(hào)量（多值）（同一般信號(hào)量（多值）（同步）。步）。Edsger W. Dijkstra 32信號(hào)量信號(hào)量(Semaphores)機(jī)制機(jī)制基本原理：兩個(gè)或多個(gè)進(jìn)程可以通過(guò)簡(jiǎn)單的基本原理：兩個(gè)或多個(gè)進(jìn)程可以通過(guò)簡(jiǎn)單的信號(hào)進(jìn)行合作，一個(gè)進(jìn)程可以被迫在某一個(gè)信號(hào)進(jìn)行合作，一個(gè)進(jìn)程可以被迫在某一個(gè)位置停止，直到它接收到一個(gè)特定的信號(hào)。位置停止，直到它接收到一個(gè)特定的信號(hào)。這是一種卓有成效的進(jìn)程同步工具，在長(zhǎng)期這是一種卓有成效的進(jìn)程同步工具，在長(zhǎng)期廣泛的應(yīng)用中，信號(hào)量機(jī)制又得到了很大的廣泛的應(yīng)用中，信號(hào)量機(jī)制又得到了很大的發(fā)展，它從整型信號(hào)量機(jī)制發(fā)展到記錄型信發(fā)展，它從整型信號(hào)量機(jī)制發(fā)展

26、到記錄型信號(hào)量機(jī)制，進(jìn)而發(fā)展為號(hào)量機(jī)制，進(jìn)而發(fā)展為“信號(hào)集信號(hào)集”機(jī)制?，F(xiàn)機(jī)制。現(xiàn)在信號(hào)量機(jī)制已廣泛應(yīng)用于在信號(hào)量機(jī)制已廣泛應(yīng)用于OSOS中。中。33信號(hào)量信號(hào)量 (Semaphores)特殊的變量特殊的變量，稱為信號(hào)量，用于發(fā)送信號(hào)，稱為信號(hào)量，用于發(fā)送信號(hào)一個(gè)進(jìn)程為了通過(guò)信號(hào)量一個(gè)進(jìn)程為了通過(guò)信號(hào)量s發(fā)送信號(hào)發(fā)送信號(hào),它需它需要執(zhí)行原語(yǔ)要執(zhí)行原語(yǔ) semSignal(s)/V(s)一個(gè)進(jìn)程通過(guò)信號(hào)量一個(gè)進(jìn)程通過(guò)信號(hào)量s接收信號(hào)接收信號(hào), 它需要執(zhí)它需要執(zhí)行原語(yǔ)行原語(yǔ)semWait(s) /P(s)如果相應(yīng)的信號(hào)沒有接收到，該進(jìn)程將被如果相應(yīng)的信號(hào)沒有接收到，該進(jìn)程將被掛起，直接它所需的信號(hào)

27、發(fā)送為止掛起，直接它所需的信號(hào)發(fā)送為止34信號(hào)量（記錄型信號(hào)量）信號(hào)量（記錄型信號(hào)量）一個(gè)具有整型數(shù)值的變量一個(gè)具有整型數(shù)值的變量被初始化為被初始化為非負(fù)數(shù)非負(fù)數(shù) (nonnegative number).semWait/P操作使信號(hào)量值減操作使信號(hào)量值減1。如果信號(hào)量。如果信號(hào)量值變?yōu)樨?fù)數(shù)，則執(zhí)行該操作的進(jìn)程被阻塞。值變?yōu)樨?fù)數(shù)，則執(zhí)行該操作的進(jìn)程被阻塞。semSignal/V 操作使信號(hào)量值增操作使信號(hào)量值增1。如果值小。如果值小于或等于零，表示之前有進(jìn)程在等該信號(hào)，則于或等于零，表示之前有進(jìn)程在等該信號(hào)，則需要在該信號(hào)量的阻塞隊(duì)列中喚醒一個(gè)進(jìn)程。需要在該信號(hào)量的阻塞隊(duì)列中喚醒一個(gè)進(jìn)程。（該

28、進(jìn)程的狀態(tài)如何變化？）（該進(jìn)程的狀態(tài)如何變化？）35信號(hào)量原語(yǔ)的定義信號(hào)量原語(yǔ)的定義等待該信號(hào)量的進(jìn)程隊(duì)列等待該信號(hào)量的進(jìn)程隊(duì)列進(jìn)程按什么順序移出呢？進(jìn)程按什么順序移出呢？36二元信號(hào)量原語(yǔ)：只有二元信號(hào)量原語(yǔ)：只有0或或1兩個(gè)值兩個(gè)值37A queue is used to hold processes waiting on the semaphore38A, B, and C depend on a result from D39信號(hào)量的類型信號(hào)量的類型信號(hào)量按聯(lián)系進(jìn)程的關(guān)系分成二類：信號(hào)量按聯(lián)系進(jìn)程的關(guān)系分成二類：互斥信號(hào)量（公用信號(hào)量）：它為一組需互斥共享互斥信號(hào)量（公用信號(hào)量）：它為

29、一組需互斥共享臨界資源的并發(fā)進(jìn)程而設(shè)置，它代表永久性共享的臨界資源的并發(fā)進(jìn)程而設(shè)置，它代表永久性共享的臨界資源，每個(gè)進(jìn)程均可對(duì)它施加臨界資源，每個(gè)進(jìn)程均可對(duì)它施加waitwait、signalsignal操操作，即可申請(qǐng)和釋放該臨界資源，其初始值置為作，即可申請(qǐng)和釋放該臨界資源，其初始值置為1 1。同步信號(hào)量（專用信號(hào)量）：它為一組需同步協(xié)作同步信號(hào)量（專用信號(hào)量）：它為一組需同步協(xié)作完成任務(wù)的并發(fā)進(jìn)程而設(shè)置，它代表消耗性的專用完成任務(wù)的并發(fā)進(jìn)程而設(shè)置，它代表消耗性的專用資源，只有擁有該資源的進(jìn)程才能對(duì)它施加資源，只有擁有該資源的進(jìn)程才能對(duì)它施加waitwait操操作（即可申請(qǐng)資源），而由其合

30、作進(jìn)程對(duì)它施加作（即可申請(qǐng)資源），而由其合作進(jìn)程對(duì)它施加signalsignal操作（即釋放資源）。操作（即釋放資源）。40為使多個(gè)進(jìn)程能互斥地訪問(wèn)某臨界資源，只為使多個(gè)進(jìn)程能互斥地訪問(wèn)某臨界資源，只需為該資源設(shè)置一個(gè)互斥信號(hào)量需為該資源設(shè)置一個(gè)互斥信號(hào)量mutex,mutex, 其初其初值為值為1 1。規(guī)定每個(gè)進(jìn)程在進(jìn)入臨界區(qū)規(guī)定每個(gè)進(jìn)程在進(jìn)入臨界區(qū)CSCS前必須申請(qǐng)資前必須申請(qǐng)資源，即對(duì)互斥信號(hào)量源，即對(duì)互斥信號(hào)量mutexmutex進(jìn)行進(jìn)行semwait操作，操作，在退出在退出臨界區(qū)臨界區(qū)CSCS后必須釋放資源，即對(duì)互斥后必須釋放資源，即對(duì)互斥信號(hào)量信號(hào)量mutexmutex進(jìn)行進(jìn)行se

31、msignal操作；操作；即將各進(jìn)即將各進(jìn)程的臨界區(qū)程的臨界區(qū)CSCS置于置于semwaitsemwait（mutexmutex）和）和semsignal(mutex)semsignal(mutex)操作之間。操作之間。使用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥使用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥41第一個(gè)執(zhí)行semWait操作的進(jìn)程將進(jìn)入臨界區(qū)42臨界區(qū)只能串行臨界區(qū)只能串行執(zhí)行執(zhí)行43S.count的物理意義的物理意義 如果一次允許有多個(gè)進(jìn)程進(jìn)入臨界區(qū)，如果一次允許有多個(gè)進(jìn)程進(jìn)入臨界區(qū)，如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？將信號(hào)量初始化為特定值，如將信號(hào)量初始化為特定值，如2，表示一次，表示一次允許最多有允許最多有2個(gè)進(jìn)程進(jìn)入臨界

32、區(qū)個(gè)進(jìn)程進(jìn)入臨界區(qū)S.count0：s的值表示可供使用的資源的值表示可供使用的資源數(shù)數(shù)S.count 0：表示資源已被占用，表示資源已被占用，s s的絕的絕對(duì)值表示有對(duì)值表示有n n個(gè)進(jìn)程因等待資源而阻塞個(gè)進(jìn)程因等待資源而阻塞44利用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步利用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步 利用信號(hào)量能解決進(jìn)程間的同步問(wèn)題，這里以下利用信號(hào)量能解決進(jìn)程間的同步問(wèn)題，這里以下圖所示的計(jì)算進(jìn)程圖所示的計(jì)算進(jìn)程C C和打印進(jìn)程和打印進(jìn)程P P通過(guò)緩沖區(qū)通過(guò)緩沖區(qū)BufferBuffer傳送數(shù)據(jù)的同步問(wèn)題為例說(shuō)明。傳送數(shù)據(jù)的同步問(wèn)題為例說(shuō)明。 BufferCP45C C和和P P兩進(jìn)程基本算法如下：兩進(jìn)程基本

33、算法如下：C C： P: P: while (true) while (true) while (true) while (true) Compute next number ; remove from Buffer ; Compute next number ; remove from Buffer ; add to Buffer ; print last number ; add to Buffer ; print last number ; C C和和P P兩進(jìn)程并發(fā)執(zhí)行，必須在執(zhí)行序列上遵循以下規(guī)則，兩進(jìn)程并發(fā)執(zhí)行，必須在執(zhí)行序列上遵循以下規(guī)則，才能避免錯(cuò)誤。才能避免錯(cuò)誤。只有當(dāng)只有當(dāng)

34、C C進(jìn)程把數(shù)據(jù)送入進(jìn)程把數(shù)據(jù)送入BufferBuffer后，后，P P進(jìn)程才能從進(jìn)程才能從BufferBuffer中取中取出數(shù)據(jù)來(lái)打印，否則出數(shù)據(jù)來(lái)打印，否則P P進(jìn)程只能等待。進(jìn)程只能等待。只有當(dāng)只有當(dāng)P P進(jìn)程從進(jìn)程從BufferBuffer中取走數(shù)據(jù)后，中取走數(shù)據(jù)后，C C進(jìn)程才能將新計(jì)算的進(jìn)程才能將新計(jì)算的數(shù)據(jù)再存入數(shù)據(jù)再存入Buffer,Buffer,否則否則C C進(jìn)程也只能等待。進(jìn)程也只能等待。46為了實(shí)現(xiàn)進(jìn)程同步，需采用為了實(shí)現(xiàn)進(jìn)程同步，需采用同步信號(hào)量同步信號(hào)量。為了滿足第一。為了滿足第一條同步規(guī)則：只有當(dāng)條同步規(guī)則：只有當(dāng)C C進(jìn)程把數(shù)據(jù)送入進(jìn)程把數(shù)據(jù)送入BufferBuf

35、fer后，后，P P進(jìn)程進(jìn)程才能從才能從BufferBuffer中取出數(shù)據(jù)來(lái)打印。設(shè)置一個(gè)中取出數(shù)據(jù)來(lái)打印。設(shè)置一個(gè)同步信號(hào)量同步信號(hào)量fullfull，它代表的消耗性的專用資源是緩沖器裝滿數(shù)據(jù)，它代表的消耗性的專用資源是緩沖器裝滿數(shù)據(jù)，這個(gè)資源只是后面動(dòng)作這個(gè)資源只是后面動(dòng)作（Remove from bufferRemove from buffer）的進(jìn)程的進(jìn)程（P P進(jìn)程）所擁有，進(jìn)程）所擁有，P P進(jìn)程在動(dòng)作前可以申請(qǐng)?jiān)撡Y源，對(duì)進(jìn)程在動(dòng)作前可以申請(qǐng)?jiān)撡Y源，對(duì)它施加它施加semwaitsemwait操作，如條件滿足操作，如條件滿足P P進(jìn)程可從進(jìn)程可從BufferBuffer中取中取數(shù)，它

36、的初值為數(shù)，它的初值為0 0。而前面動(dòng)作的進(jìn)程（。而前面動(dòng)作的進(jìn)程（P P進(jìn)程的合作進(jìn)進(jìn)程的合作進(jìn)程程C C）在動(dòng)作）在動(dòng)作（Add to bufferAdd to buffer）完成后對(duì)完成后對(duì)fullfull信號(hào)量施信號(hào)量施加加semsignalsemsignal操作，即當(dāng)操作，即當(dāng)C C進(jìn)程將數(shù)據(jù)存入進(jìn)程將數(shù)據(jù)存入BufferBuffer后，即后，即可釋放該資源供可釋放該資源供P P進(jìn)程再使用。實(shí)現(xiàn)進(jìn)程再使用。實(shí)現(xiàn)C C和和P P兩進(jìn)程第一條兩進(jìn)程第一條同步規(guī)則的類同步規(guī)則的類C C程序：程序：47考慮第一個(gè)同步關(guān)系考慮第一個(gè)同步關(guān)系C C加入后加入后P P再取再取Semaphore f

37、ull=0 Semaphore full=0 ；Void C() Void P()Void C() Void P() while (true) while (true) while (true) while (true) Compute next number Compute next number ； semWait(full) semWait(full) ； remove from Buffer remove from Buffer ； Add to buffer Add to buffer ； semSignal(full) semSignal(full) ； Print last nu

38、mber Print last number ； Void main()Void main() parbegin (C,P); parbegin (C,P);48為了滿足第二條同步規(guī)則：只有當(dāng)為了滿足第二條同步規(guī)則：只有當(dāng)P P進(jìn)程從進(jìn)程從BufferBuffer中取走數(shù)據(jù)后，中取走數(shù)據(jù)后，C C進(jìn)程才能將新計(jì)算的數(shù)據(jù)再存入進(jìn)程才能將新計(jì)算的數(shù)據(jù)再存入BufferBuffer。設(shè)置另一個(gè)。設(shè)置另一個(gè)同步信號(hào)量同步信號(hào)量emptyempty，它代表的，它代表的消耗性的專用資源是緩沖器空消耗性的專用資源是緩沖器空，這個(gè)資源只是后，這個(gè)資源只是后面動(dòng)作面動(dòng)作（Add to bufferAdd to

39、buffer）的進(jìn)程（的進(jìn)程（C C進(jìn)程）所擁進(jìn)程）所擁有，有，C C進(jìn)程在動(dòng)作前可以申請(qǐng)?jiān)撡Y源，對(duì)它施加進(jìn)程在動(dòng)作前可以申請(qǐng)?jiān)撡Y源，對(duì)它施加semwaitsemwait操作，如條件滿足進(jìn)程操作，如條件滿足進(jìn)程C C可以申請(qǐng)?jiān)撡Y源，可以申請(qǐng)?jiān)撡Y源，它的初值為它的初值為1 1 。而前面動(dòng)作。而前面動(dòng)作（Remove from Remove from bufferbuffer）的進(jìn)程（的進(jìn)程（C C進(jìn)程的合作進(jìn)程進(jìn)程的合作進(jìn)程P P）在動(dòng)作完）在動(dòng)作完成后對(duì)成后對(duì)emptyempty信號(hào)量施加信號(hào)量施加semsignalsemsignal操作，即當(dāng)操作，即當(dāng)P P進(jìn)進(jìn)程從程從BufferBuffe

40、r中取走數(shù)據(jù)后，即可釋放該資源供中取走數(shù)據(jù)后，即可釋放該資源供C C進(jìn)進(jìn)程再使用。程再使用。實(shí)現(xiàn)實(shí)現(xiàn)C C和和P P兩進(jìn)程第二條同步規(guī)則的類兩進(jìn)程第二條同步規(guī)則的類C C程序：程序：49Semaphore empty=1 Semaphore empty=1 ；Void C() Void P()Void C() Void P() while (true) while (true) while (true) while (true) Compute next number Compute next number ； semWait(empty); semWait(empty); remove fr

41、om Buffer remove from Buffer ； Add to buffer Add to buffer ； semSignal(empty);semSignal(empty); Print last number Print last number ； Void main()Void main() parbegin (C,P); parbegin (C,P);考慮第二個(gè)同步關(guān)系考慮第二個(gè)同步關(guān)系P取走后取走后C再加入再加入50Semaphore empty=1, full=0;Semaphore empty=1, full=0;Void C() Void P()Void C()

42、Void P() while (true) while (true) while (true) while (true) Compute next number Compute next number ； semWait(full) semWait(full) ； semWait(empty); semWait(empty); remove from Buffer remove from Buffer ； Add to buffer Add to buffer ； semSignal(empty);semSignal(empty); semSignal(full) semSignal(full

43、) ； Print last number Print last number ； Void main()Void main() parbegin (C,P); parbegin (C,P);考慮二個(gè)同步關(guān)系考慮二個(gè)同步關(guān)系51同步物理意義同步也可以理解為：先同步也可以理解為：先做動(dòng)作的做動(dòng)作的進(jìn)程進(jìn)程C C在在動(dòng)作動(dòng)作完成后對(duì)同步信號(hào)量施加完成后對(duì)同步信號(hào)量施加semSignalsemSignal操作，代操作，代表表發(fā)送消息；發(fā)送消息；后后做動(dòng)作的做動(dòng)作的進(jìn)程進(jìn)程P P在在動(dòng)作動(dòng)作前對(duì)同前對(duì)同步信號(hào)量施加步信號(hào)量施加semWaitsemWait操作，代表操作，代表測(cè)試消息是測(cè)試消息是否到達(dá)。

44、否到達(dá)。52利用信號(hào)量機(jī)制描述前趨關(guān)系利用信號(hào)量機(jī)制描述前趨關(guān)系 進(jìn)程間同步關(guān)系也可用前趨圖表示。進(jìn)程間同步關(guān)系也可用前趨圖表示。C C和和P P兩進(jìn)程間先計(jì)算好兩進(jìn)程間先計(jì)算好再打印同步關(guān)系用前趨圖表示如下：再打印同步關(guān)系用前趨圖表示如下： 對(duì)應(yīng)這個(gè)前趨關(guān)系可設(shè)置同步信號(hào)量對(duì)應(yīng)這個(gè)前趨關(guān)系可設(shè)置同步信號(hào)量fullfull，它為后繼進(jìn)程，它為后繼進(jìn)程P P擁有，初值為擁有，初值為0 0。它的并發(fā)執(zhí)行程序如下：。它的并發(fā)執(zhí)行程序如下： semaphore full=0; semaphore full=0; void C() void P() void C() void P() while (tr

45、ue) while (true) while (true) while (true) begin Compute ; begin Compute ; ; ; Print ; Print ; void main() void main() parbegin(C, P); parbegin(C, P);CPsemWait(full);semSignal(full);53經(jīng)典進(jìn)程同步問(wèn)題一：經(jīng)典進(jìn)程同步問(wèn)題一：生產(chǎn)者生產(chǎn)者/消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題問(wèn)題描述：?jiǎn)栴}描述：一個(gè)或多個(gè)生產(chǎn)者生產(chǎn)某種類型的數(shù)據(jù)（記錄、一個(gè)或多個(gè)生產(chǎn)者生產(chǎn)某種類型的數(shù)據(jù)（記錄、字符），并放置在緩沖區(qū)中；字符），并放置在緩沖區(qū)中；有

46、一個(gè)消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)，每次取一項(xiàng)；有一個(gè)消費(fèi)者從緩沖區(qū)中取數(shù)據(jù)，每次取一項(xiàng)；任何時(shí)候只有一個(gè)生產(chǎn)者或消費(fèi)者可以訪問(wèn)緩任何時(shí)候只有一個(gè)生產(chǎn)者或消費(fèi)者可以訪問(wèn)緩沖區(qū)沖區(qū)問(wèn)題：生產(chǎn)者和消費(fèi)者之間存在什么樣的關(guān)問(wèn)題：生產(chǎn)者和消費(fèi)者之間存在什么樣的關(guān)系？需要設(shè)置幾個(gè)信號(hào)量？系？需要設(shè)置幾個(gè)信號(hào)量？54同步問(wèn)題：同步問(wèn)題： 生產(chǎn)進(jìn)程不能往生產(chǎn)進(jìn)程不能往“滿滿”的緩沖區(qū)中放產(chǎn)品。的緩沖區(qū)中放產(chǎn)品。 消費(fèi)進(jìn)程不能從消費(fèi)進(jìn)程不能從“空空”的緩沖區(qū)中取產(chǎn)品。的緩沖區(qū)中取產(chǎn)品?；コ鈫?wèn)題：互斥問(wèn)題： 緩沖池是臨界資源，各進(jìn)程應(yīng)該互斥使用。緩沖池是臨界資源，各進(jìn)程應(yīng)該互斥使用。輸入指針輸入指針inin：指示下一個(gè)

47、可投放消息的緩沖區(qū)；指示下一個(gè)可投放消息的緩沖區(qū)；輸出指針輸出指針outout：指示下一個(gè)可獲取消息的緩沖區(qū)。指示下一個(gè)可獲取消息的緩沖區(qū)。55生產(chǎn)者之間、生產(chǎn)者與消費(fèi)者之間、消費(fèi)者生產(chǎn)者之間、生產(chǎn)者與消費(fèi)者之間、消費(fèi)者之間都必須互斥使用緩沖池。所以必須設(shè)置之間都必須互斥使用緩沖池。所以必須設(shè)置互斥信號(hào)量互斥信號(hào)量mutexmutex，它代表緩沖池資源，它，它代表緩沖池資源，它的數(shù)值為的數(shù)值為1 1。與計(jì)算打印兩進(jìn)程同步關(guān)系相同，生產(chǎn)者和與計(jì)算打印兩進(jìn)程同步關(guān)系相同，生產(chǎn)者和消費(fèi)者二類進(jìn)程消費(fèi)者二類進(jìn)程P P和和C C之間應(yīng)滿足下列二個(gè)同之間應(yīng)滿足下列二個(gè)同步條件：步條件：l只有在緩沖池中至少

48、有一個(gè)緩沖區(qū)已存入消息只有在緩沖池中至少有一個(gè)緩沖區(qū)已存入消息后，消費(fèi)者才能從中提取消息，否則消費(fèi)者必后，消費(fèi)者才能從中提取消息，否則消費(fèi)者必須等待。須等待。l只有緩沖池中至少有一個(gè)緩沖區(qū)是空時(shí)，生產(chǎn)只有緩沖池中至少有一個(gè)緩沖區(qū)是空時(shí)，生產(chǎn)者才能把消息放入緩沖區(qū)，否則生產(chǎn)者必須等者才能把消息放入緩沖區(qū)，否則生產(chǎn)者必須等待。待。（針對(duì)有限長(zhǎng)度的緩沖區(qū)）（針對(duì)有限長(zhǎng)度的緩沖區(qū)）56情況一：緩沖區(qū)無(wú)限大情況一：緩沖區(qū)無(wú)限大生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程producer:while (true) /* produce item v */bin = v;in+; 57消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程consumer:whil

49、e (true) while (in 0S0表示有表示有S S個(gè)資源可用；個(gè)資源可用； S=0S=0表示無(wú)資源可用；表示無(wú)資源可用； S0S0則則| | S |S |表示表示S S等待隊(duì)列中的進(jìn)程個(gè)數(shù)。等待隊(duì)列中的進(jìn)程個(gè)數(shù)。 信號(hào)量的初值應(yīng)該大于等于信號(hào)量的初值應(yīng)該大于等于0 0 semWait(s)semWait(s)（P(S)P(S)）: :表示申請(qǐng)表示申請(qǐng)( (等待等待) )一個(gè)資源一個(gè)資源 semSignal(s)semSignal(s)（V(S)V(S)）: :表示釋放一個(gè)資源。表示釋放一個(gè)資源。77進(jìn)程操作總結(jié)（續(xù)）2) wait(P)/signal(V)操作必須成對(duì)出現(xiàn)，有操作必

50、須成對(duì)出現(xiàn)，有一個(gè)一個(gè)wait(P)操作就一定有一個(gè)操作就一定有一個(gè)signal(V)操作操作 當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程 當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn) 如果如果wait(S1)和和wait(S2)兩個(gè)操作在一起，兩個(gè)操作在一起，那么那么wait操作的順序至關(guān)重要操作的順序至關(guān)重要,一個(gè)同步一個(gè)同步wait操作與一個(gè)互斥操作與一個(gè)互斥wait操作在一起時(shí)同步操作在一起時(shí)同步wait操作在互斥操作在互斥wait操作前；而兩個(gè)操作前；而兩個(gè)signal操作無(wú)操作無(wú)關(guān)緊要關(guān)緊要78【例題】司機(jī)進(jìn)程：司機(jī)進(jìn)程：while(1)while(1) 啟動(dòng)車輛啟動(dòng)車輛正常駕駛正常駕駛到站停車到站停車售票員進(jìn)程：售票員進(jìn)程：while(1)while(1) 關(guān)門關(guān)門售票售票開門開門1.1.用用P/VP/V（wait/signalwait/signal）操作解決司機(jī)與售票員的問(wèn)題操作解決司機(jī)與售票員的