第2章-進(jìn)程描述及控制-2

1、第第2章章 進(jìn)程描述與控制（續(xù)）進(jìn)程描述與控制（續(xù)）2.3 同步與互斥同步與互斥2.4 經(jīng)典同步問(wèn)題經(jīng)典同步問(wèn)題2.5 進(jìn)程通信進(jìn)程通信2.6 線程及線程及其其實(shí)現(xiàn)實(shí)現(xiàn) 12.3 同步與互斥同步與互斥2.3.1 同步和互斥的基本概念同步和互斥的基本概念2.3.2 進(jìn)程間的互斥技術(shù)進(jìn)程間的互斥技術(shù)2.3.3 信號(hào)量機(jī)制信號(hào)量機(jī)制2.3.4 信號(hào)量的應(yīng)用信號(hào)量的應(yīng)用2.3.5 管程機(jī)制管程機(jī)制2背景背景T1T2機(jī)票問(wèn)題機(jī)票問(wèn)題process Ti ( ) / i = 1, 2 按旅客訂票要求找到按旅客訂票要求找到A ； Xi = A; if (Xi=1) Xi=Xi-1; A=Xi;輸出一張票；輸

2、出一張票； else 輸出票已售完輸出票已售完 ； 3消費(fèi)者消費(fèi)者生產(chǎn)者生產(chǎn)者哲學(xué)家進(jìn)餐問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題42.3.1 同步和互斥的基本概念同步和互斥的基本概念l多進(jìn)程的并發(fā)執(zhí)行多進(jìn)程的并發(fā)執(zhí)行n概念概念處理器同時(shí)交錯(cuò)執(zhí)行多個(gè)進(jìn)程；處理器同時(shí)交錯(cuò)執(zhí)行多個(gè)進(jìn)程；一組進(jìn)程在一段時(shí)間內(nèi)同時(shí)存在。一組進(jìn)程在一段時(shí)間內(nèi)同時(shí)存在。n特性特性間斷性：因運(yùn)行環(huán)境的開(kāi)放性，具體表現(xiàn)為間斷性：因運(yùn)行環(huán)境的開(kāi)放性，具體表現(xiàn)為n被動(dòng)影響被動(dòng)影響：資源競(jìng)爭(zhēng)資源競(jìng)爭(zhēng)。n主動(dòng)合作主動(dòng)合作：合作同步、數(shù)據(jù)交互、收發(fā)信號(hào)合作同步、數(shù)據(jù)交互、收發(fā)信號(hào)。失去封閉性失去封閉性不可再現(xiàn)性不可再現(xiàn)性結(jié)果的不確定性結(jié)果的不確定性5l進(jìn)程間

3、的約束關(guān)系進(jìn)程間的約束關(guān)系n間接的相互制約關(guān)系：間接的相互制約關(guān)系：資源競(jìng)爭(zhēng)資源競(jìng)爭(zhēng)( (共享共享) )需互斥地訪問(wèn)臨界資源需互斥地訪問(wèn)臨界資源n直接的相互制約關(guān)系：直接的相互制約關(guān)系：進(jìn)程協(xié)作進(jìn)程協(xié)作( (如數(shù)據(jù)共享、并行處理如數(shù)據(jù)共享、并行處理) )6l進(jìn)程同步進(jìn)程同步n是并發(fā)進(jìn)程在執(zhí)行時(shí)序上進(jìn)行相互制約，使并發(fā)進(jìn)程是并發(fā)進(jìn)程在執(zhí)行時(shí)序上進(jìn)行相互制約，使并發(fā)進(jìn)程能按一定的規(guī)則共享資源和相互合作的技術(shù)。（能按一定的規(guī)則共享資源和相互合作的技術(shù)。（廣義廣義上的同步）上的同步）。若兩個(gè)或兩個(gè)以上的進(jìn)程要協(xié)作完成一個(gè)任務(wù)，則它們?nèi)魞蓚€(gè)或兩個(gè)以上的進(jìn)程要協(xié)作完成一個(gè)任務(wù)，則它們之間就要互相配合，需在

4、某些動(dòng)作之間進(jìn)行同步（狹義之間就要互相配合，需在某些動(dòng)作之間進(jìn)行同步（狹義上的同步）。上的同步）。n如：計(jì)算進(jìn)程和打印進(jìn)程如：計(jì)算進(jìn)程和打印進(jìn)程若多個(gè)進(jìn)程競(jìng)爭(zhēng)某個(gè)資源，則也需同步（互斥）。若多個(gè)進(jìn)程競(jìng)爭(zhēng)某個(gè)資源，則也需同步（互斥）。7例如例如: 司機(jī)司機(jī) P1 售票員售票員 P2 Repeat Repeat 啟動(dòng)啟動(dòng) 關(guān)門(mén)關(guān)門(mén) 正常運(yùn)行正常運(yùn)行 售票售票 到站停到站停 開(kāi)門(mén)開(kāi)門(mén) Until False Until False8l互斥互斥n互斥是同步的一個(gè)特例?；コ馐峭降囊粋€(gè)特例。n兩個(gè)或兩個(gè)以上的進(jìn)程兩個(gè)或兩個(gè)以上的進(jìn)程競(jìng)爭(zhēng)競(jìng)爭(zhēng)/ /共享某資源共享某資源，而該資，而該資源在同一時(shí)刻只能被一個(gè)

5、進(jìn)程使用。源在同一時(shí)刻只能被一個(gè)進(jìn)程使用。n操作系統(tǒng)需要提供一種資源分配機(jī)制，來(lái)控制為操作系統(tǒng)需要提供一種資源分配機(jī)制，來(lái)控制為這些進(jìn)程分配資源的順序，既保證各進(jìn)程能夠使這些進(jìn)程分配資源的順序，既保證各進(jìn)程能夠使用資源，又能保證各進(jìn)程互斥使用資源用資源，又能保證各進(jìn)程互斥使用資源。9l例如：例如：n兩個(gè)進(jìn)程共享一臺(tái)打印機(jī)，若讓他們隨意使用，兩個(gè)進(jìn)程共享一臺(tái)打印機(jī)，若讓他們隨意使用，則很容易發(fā)生兩進(jìn)程的輸出結(jié)果混淆在一起的情則很容易發(fā)生兩進(jìn)程的輸出結(jié)果混淆在一起的情況。況。n解決辦法：解決辦法：當(dāng)一個(gè)進(jìn)程提出打印請(qǐng)求并得到許可當(dāng)一個(gè)進(jìn)程提出打印請(qǐng)求并得到許可后，打印機(jī)就一直為該進(jìn)程所獨(dú)占；若在此

6、期間后，打印機(jī)就一直為該進(jìn)程所獨(dú)占；若在此期間有另一進(jìn)程也提出打印請(qǐng)求，則必須等待使用打有另一進(jìn)程也提出打印請(qǐng)求，則必須等待使用打印機(jī)的那個(gè)進(jìn)程釋放打印機(jī)后方可使用。印機(jī)的那個(gè)進(jìn)程釋放打印機(jī)后方可使用。10l臨界資源臨界資源n一次僅允許一個(gè)進(jìn)程訪問(wèn)或使用的資源。臨界資一次僅允許一個(gè)進(jìn)程訪問(wèn)或使用的資源。臨界資源可能是硬件設(shè)備，也可能是軟件資源。源可能是硬件設(shè)備，也可能是軟件資源。n引起不可再現(xiàn)性是因?yàn)榕R界資源沒(méi)有互斥訪問(wèn)。引起不可再現(xiàn)性是因?yàn)榕R界資源沒(méi)有互斥訪問(wèn)。可并發(fā)訪問(wèn)可并發(fā)訪問(wèn)不可并發(fā)訪問(wèn)不可并發(fā)訪問(wèn)硬件硬件內(nèi)存、顯示器、硬盤(pán)內(nèi)存、顯示器、硬盤(pán)打印機(jī)、繪圖儀、磁帶機(jī)打印機(jī)、繪圖儀、磁帶機(jī)

7、軟件軟件共享程序段共享程序段共享變量等共享變量等11l臨界區(qū)臨界區(qū)（ Dijkstra在在1965年首先提出）年首先提出）n是每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼。是每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段代碼。當(dāng)一個(gè)進(jìn)程進(jìn)入自身的這段代碼時(shí)，不允許其他進(jìn)程當(dāng)一個(gè)進(jìn)程進(jìn)入自身的這段代碼時(shí)，不允許其他進(jìn)程進(jìn)入自己對(duì)應(yīng)的臨界區(qū)。進(jìn)入自己對(duì)應(yīng)的臨界區(qū)。n若保證進(jìn)程在臨界區(qū)執(zhí)行時(shí)，不讓另一個(gè)進(jìn)程進(jìn)若保證進(jìn)程在臨界區(qū)執(zhí)行時(shí)，不讓另一個(gè)進(jìn)程進(jìn)入自身對(duì)應(yīng)的臨界區(qū)，即各進(jìn)程對(duì)臨界資源的訪入自身對(duì)應(yīng)的臨界區(qū)，即各進(jìn)程對(duì)臨界資源的訪問(wèn)是互斥的，則不會(huì)造成與時(shí)間有關(guān)的錯(cuò)誤。問(wèn)是互斥的，則不會(huì)造成與時(shí)間有關(guān)的錯(cuò)誤。n同一臨界資源的臨

8、界區(qū)個(gè)數(shù)同一臨界資源的臨界區(qū)個(gè)數(shù) = 共享該臨界資源的共享該臨界資源的進(jìn)程數(shù)。進(jìn)程數(shù)。12兩個(gè)進(jìn)程兩個(gè)進(jìn)程 P1和和P2存在存在共享變量共享變量countP1： P2： R1=count R2=count R1=R1+1 R2=R2+1 count=R1 count=R2 臨界區(qū)示例臨界區(qū)示例本意本意: count初值為初值為0，結(jié)果：，結(jié)果：count = 2。13l在并發(fā)系統(tǒng)中，進(jìn)程可能并發(fā)交叉執(zhí)行，兩個(gè)進(jìn)程在并發(fā)系統(tǒng)中，進(jìn)程可能并發(fā)交叉執(zhí)行，兩個(gè)進(jìn)程可能的相對(duì)執(zhí)行次序：可能的相對(duì)執(zhí)行次序： P1：R1=count R1=R1+1 P2：R2=count R2=R2+1 count=R2

9、P1：count=R1l結(jié)果：結(jié)果：count = 1l原因？原因？14l臨界區(qū)的訪問(wèn)模型臨界區(qū)的訪問(wèn)模型while( true ) Entry section 進(jìn)入?yún)^(qū)（檢查有無(wú)進(jìn)程進(jìn)入）進(jìn)入?yún)^(qū)（檢查有無(wú)進(jìn)程進(jìn)入） Critical section 臨界區(qū)臨界區(qū) Exit section 退出區(qū)（將訪問(wèn)標(biāo)志復(fù)位）退出區(qū)（將訪問(wèn)標(biāo)志復(fù)位） Remainder section剩余區(qū)剩余區(qū)15l使用臨界區(qū)時(shí)，同步機(jī)制應(yīng)遵循的準(zhǔn)則使用臨界區(qū)時(shí)，同步機(jī)制應(yīng)遵循的準(zhǔn)則n前提前提任何進(jìn)程無(wú)權(quán)停止其它進(jìn)程的運(yùn)行任何進(jìn)程無(wú)權(quán)停止其它進(jìn)程的運(yùn)行對(duì)進(jìn)程速度和處理器的數(shù)量沒(méi)有任何要求和限制對(duì)進(jìn)程速度和處理器的數(shù)量沒(méi)有

10、任何要求和限制n使用臨界區(qū)的準(zhǔn)則使用臨界區(qū)的準(zhǔn)則空閑讓進(jìn)空閑讓進(jìn)忙則等待忙則等待有限等待有限等待讓權(quán)等待讓權(quán)等待162.3.2 進(jìn)程間的互斥技術(shù)進(jìn)程間的互斥技術(shù)l臨界區(qū)互斥的實(shí)現(xiàn)方法臨界區(qū)互斥的實(shí)現(xiàn)方法n平等協(xié)商平等協(xié)商硬件方法硬件方法n互斥鎖互斥鎖n特殊指令法（特殊指令法（test&set指令、交換指令指令、交換指令exchange）n中斷禁用法中斷禁用法n組合法組合法軟件方法軟件方法n引入進(jìn)程管理者引入進(jìn)程管理者17l互斥的互斥的硬件方法硬件方法1 1互斥鎖互斥鎖n通過(guò)鎖的狀態(tài)來(lái)表示是否有進(jìn)程在臨界區(qū)通過(guò)鎖的狀態(tài)來(lái)表示是否有進(jìn)程在臨界區(qū)X=0：打開(kāi)狀態(tài)：打開(kāi)狀態(tài)X=1：關(guān)閉狀態(tài)：關(guān)閉狀態(tài)n

11、進(jìn)程要進(jìn)入臨界區(qū)前，必須要測(cè)試鎖的狀態(tài)，只進(jìn)程要進(jìn)入臨界區(qū)前，必須要測(cè)試鎖的狀態(tài)，只有打開(kāi)狀態(tài)時(shí)，才能進(jìn)入臨界區(qū)有打開(kāi)狀態(tài)時(shí)，才能進(jìn)入臨界區(qū)n進(jìn)程在進(jìn)入臨界區(qū)的那一刻立即關(guān)鎖進(jìn)程在進(jìn)入臨界區(qū)的那一刻立即關(guān)鎖n進(jìn)程在離開(kāi)臨界區(qū)時(shí)要立即開(kāi)鎖進(jìn)程在離開(kāi)臨界區(qū)時(shí)要立即開(kāi)鎖例：在火車(chē)上如廁例：在火車(chē)上如廁18鎖機(jī)制不安全性分析鎖機(jī)制不安全性分析l安全性問(wèn)題安全性問(wèn)題n鎖的關(guān)閉操作包含鎖的關(guān)閉操作包含測(cè)試鎖的狀態(tài)測(cè)試鎖的狀態(tài)和和關(guān)鎖關(guān)鎖兩個(gè)步驟。兩個(gè)步驟。n問(wèn)題描述問(wèn)題描述若進(jìn)程若進(jìn)程A測(cè)試鎖狀態(tài)為開(kāi)，但在測(cè)試鎖狀態(tài)為開(kāi)，但在關(guān)鎖前被剝奪關(guān)鎖前被剝奪CPU;被調(diào)度的進(jìn)程被調(diào)度的進(jìn)程B發(fā)現(xiàn)鎖狀態(tài)為開(kāi)，可能關(guān)

12、鎖并進(jìn)入臨發(fā)現(xiàn)鎖狀態(tài)為開(kāi)，可能關(guān)鎖并進(jìn)入臨界區(qū)。界區(qū)。A恢復(fù)執(zhí)行后，以為鎖狀態(tài)仍為開(kāi)，于是關(guān)鎖并進(jìn)入恢復(fù)執(zhí)行后，以為鎖狀態(tài)仍為開(kāi)，于是關(guān)鎖并進(jìn)入臨界區(qū)。臨界區(qū)。n可能出現(xiàn)兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)可能出現(xiàn)兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)l安全性保證條件安全性保證條件n把測(cè)試鎖狀態(tài)和關(guān)鎖兩個(gè)步驟把測(cè)試鎖狀態(tài)和關(guān)鎖兩個(gè)步驟實(shí)現(xiàn)為不可分割的原實(shí)現(xiàn)為不可分割的原子性操作子性操作。19 boolean testset (boolean *lock) /testset指令語(yǔ)義指令語(yǔ)義boolean ts=*lock;*lock=TRUE;return ts;互斥的硬件方法互斥的硬件方法2 test &set指令指令n每

13、個(gè)臨界資源對(duì)應(yīng)一個(gè)每個(gè)臨界資源對(duì)應(yīng)一個(gè)lock，其初值為，其初值為FALSE，表示臨界資源空閑；表示臨界資源空閑；n用用test&set指令測(cè)試指令測(cè)試lock狀態(tài)，并加鎖；狀態(tài)，并加鎖；n由于由于test&set是一條完整是一條完整的指令的指令，執(zhí)行中是不會(huì)被，執(zhí)行中是不會(huì)被“中斷中斷” 的，故保證了鎖的，故保證了鎖的測(cè)試和關(guān)閉操作的原子的測(cè)試和關(guān)閉操作的原子性（即不可分解的特性）。性（即不可分解的特性）。20test &set指令的應(yīng)用指令的應(yīng)用boolean lock;void P(int i)while(true)while(testset(&lock); /循環(huán)測(cè)試循環(huán)測(cè)試criti

14、cal section;lock=FALSE;remainder section;void main()lock=FALSE;parbegin(P(1), P(2), , P(n);21void exchange(boolean *key, boolean *lock) boolean temp;temp = *lock;*lock = *key;*key = temp;互斥的硬件方法互斥的硬件方法3交換指令交換指令exchange（swap）22lexchange指令能夠?qū)崿F(xiàn)兩個(gè)變量之間的內(nèi)容交換。指令能夠?qū)崿F(xiàn)兩個(gè)變量之間的內(nèi)容交換。l基本思想基本思想n交換的同時(shí)進(jìn)行加鎖交換的同時(shí)進(jìn)行加鎖l

15、具體實(shí)現(xiàn)具體實(shí)現(xiàn)n設(shè)置：測(cè)試變量設(shè)置：測(cè)試變量key、鎖變量、鎖變量lockn進(jìn)入臨界區(qū)前進(jìn)入臨界區(qū)前A.先置測(cè)試變量的值為先置測(cè)試變量的值為T(mén)RUE，再對(duì)測(cè)試變量和鎖變量執(zhí)，再對(duì)測(cè)試變量和鎖變量執(zhí)行交換指令。行交換指令。B.若測(cè)試變量值為若測(cè)試變量值為FALSE：進(jìn)入臨界區(qū)：進(jìn)入臨界區(qū)C.若測(cè)試變量值為若測(cè)試變量值為T(mén)RUE ：重新轉(zhuǎn)向：重新轉(zhuǎn)向A。n離開(kāi)臨界區(qū)離開(kāi)臨界區(qū)設(shè)置鎖變量值為設(shè)置鎖變量值為FALSE23void Pi( )while(true)keyi=TURE;doexchage(&keyi , &lock); /循環(huán)測(cè)試循環(huán)測(cè)試 while(keyi!=FALSE) criti

16、cal section;lock=FALSE;remainder section;24l硬件硬件方法的不足方法的不足n忙等，不能實(shí)現(xiàn)忙等，不能實(shí)現(xiàn)“讓權(quán)等待讓權(quán)等待”（循環(huán)測(cè)試）；（循環(huán)測(cè)試）；n硬件實(shí)現(xiàn)代價(jià)較大硬件實(shí)現(xiàn)代價(jià)較大；n可移植性差，依賴具體的硬件平臺(tái)可移植性差，依賴具體的硬件平臺(tái)；n在多處理環(huán)境下有些硬件實(shí)現(xiàn)方式不適用在多處理環(huán)境下有些硬件實(shí)現(xiàn)方式不適用。25l實(shí)現(xiàn)進(jìn)程互斥的軟件方法實(shí)現(xiàn)進(jìn)程互斥的軟件方法n基本思路基本思路：在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，若：在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，若已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過(guò)循環(huán)檢查已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過(guò)循環(huán)檢查進(jìn)行等待；在退出區(qū)

17、修改標(biāo)志。進(jìn)行等待；在退出區(qū)修改標(biāo)志。n主要問(wèn)題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志？主要問(wèn)題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志？26l軟件方法軟件方法1：?jiǎn)螛?biāo)志單標(biāo)志n設(shè)立一個(gè)公用整型變量設(shè)立一個(gè)公用整型變量 turn，描述允許進(jìn)入臨界描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí)；區(qū)的進(jìn)程標(biāo)識(shí)；n假設(shè)有兩個(gè)進(jìn)程假設(shè)有兩個(gè)進(jìn)程Pi, Pj ，其中，其中Pi：在進(jìn)入臨界區(qū)前，循環(huán)檢查是否允許本進(jìn)程進(jìn)入在進(jìn)入臨界區(qū)前，循環(huán)檢查是否允許本進(jìn)程進(jìn)入nturn為為i時(shí)，進(jìn)程時(shí)，進(jìn)程Pi可進(jìn)入；可進(jìn)入；在退出臨界區(qū)時(shí)，修改允許進(jìn)入進(jìn)程標(biāo)識(shí)在退出臨界區(qū)時(shí)，修改允許進(jìn)入進(jìn)程標(biāo)識(shí)n進(jìn)程進(jìn)程Pi退出時(shí)，改退出時(shí)，改turn為進(jìn)程為進(jìn)程Pj的標(biāo)

18、識(shí)的標(biāo)識(shí)j；27n單標(biāo)志的缺點(diǎn)單標(biāo)志的缺點(diǎn)強(qiáng)制輪流進(jìn)入臨界區(qū)強(qiáng)制輪流進(jìn)入臨界區(qū)，未考慮進(jìn)程的實(shí)際需要。容易，未考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在造成資源利用不充分：在Pi讓出臨界區(qū)之后，讓出臨界區(qū)之后，Pj使用使用臨界區(qū)之前，臨界區(qū)之前，Pi不可能再次使用臨界區(qū)。不可能再次使用臨界區(qū)。while (turn != i);critical sectionturn = j;remainder sectionPi28l軟件算法軟件算法2：雙標(biāo)志、先檢查：雙標(biāo)志、先檢查n設(shè)立一個(gè)標(biāo)志數(shù)組設(shè)立一個(gè)標(biāo)志數(shù)組flag0.1：描述進(jìn)程是否在臨界：描述進(jìn)程是否在臨界區(qū)，初值均為區(qū)，初值均為FALSE

19、。先檢查，后修改先檢查，后修改：在進(jìn)入?yún)^(qū)檢查另一進(jìn)程是否在臨：在進(jìn)入?yún)^(qū)檢查另一進(jìn)程是否在臨界區(qū)，界區(qū)，若不在若不在，則修改本進(jìn)程在臨界區(qū)的標(biāo)志；，則修改本進(jìn)程在臨界區(qū)的標(biāo)志；在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志。在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志。Pi29n雙標(biāo)志、先檢查的優(yōu)點(diǎn)：雙標(biāo)志、先檢查的優(yōu)點(diǎn)：不用交替進(jìn)入，可連續(xù)使用；n缺點(diǎn)：缺點(diǎn)：Pi、Pj可能同時(shí)進(jìn)入臨界區(qū)可能同時(shí)進(jìn)入臨界區(qū)。如：按下面序列執(zhí)行時(shí)：如：按下面序列執(zhí)行時(shí)：“Pi Pj Pi Pj”。即在檢查對(duì)方。即在檢查對(duì)方flag之后和切換自己之后和切換自己flag之前之前有一段時(shí)間，結(jié)果都檢查通過(guò)，同時(shí)進(jìn)入臨界區(qū)，有一段時(shí)間，結(jié)果都檢查

20、通過(guò)，同時(shí)進(jìn)入臨界區(qū)，顯然顯然違背了違背了“忙則等待忙則等待”的原則的原則。這里的問(wèn)題出在。這里的問(wèn)題出在檢查和修改操作不能連續(xù)進(jìn)行。檢查和修改操作不能連續(xù)進(jìn)行。30l軟件算法軟件算法3：雙標(biāo)志、后檢查雙標(biāo)志、后檢查n類(lèi)似于算法類(lèi)似于算法2，與算法，與算法2的區(qū)別在于先修改后檢的區(qū)別在于先修改后檢查。查?？煞乐箖蓚€(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)可防止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。31l雙標(biāo)志、后檢查的缺點(diǎn)雙標(biāo)志、后檢查的缺點(diǎn)nPi、Pj可能都進(jìn)不了臨界區(qū)可能都進(jìn)不了臨界區(qū)如：按下面序列執(zhí)行時(shí)：如：按下面序列執(zhí)行時(shí)：“Pi Pj Pi Pj”。即在切換自己。即在切換自己flag之后和檢查對(duì)方之后和檢查對(duì)方flag

21、之之前有一段時(shí)間，結(jié)果都切換前有一段時(shí)間，結(jié)果都切換flag，都檢查不通過(guò)。，都檢查不通過(guò)。因而，因而，這又違背了這又違背了“空閑讓進(jìn)空閑讓進(jìn)”和和“有限等待有限等待”原則原則。32練習(xí)題練習(xí)題l兩個(gè)旅行社甲和乙為旅客到某航空公司訂飛機(jī)票，形成互斥兩個(gè)旅行社甲和乙為旅客到某航空公司訂飛機(jī)票，形成互斥資源的是（）。資源的是（）。A. 旅行社旅行社 B.航空公司航空公司 C.飛機(jī)票飛機(jī)票 D.旅行社與航空公司旅行社與航空公司l臨界區(qū)是指并發(fā)進(jìn)程訪問(wèn)共享資源的（）。臨界區(qū)是指并發(fā)進(jìn)程訪問(wèn)共享資源的（）。A. 管理信息管理信息 B.信息存儲(chǔ)信息存儲(chǔ) C.數(shù)據(jù)數(shù)據(jù) D.代碼代碼l以下（）不是同步機(jī)制遵循

22、的準(zhǔn)則。以下（）不是同步機(jī)制遵循的準(zhǔn)則。A. 讓權(quán)等待讓權(quán)等待B.空閑讓進(jìn)空閑讓進(jìn)C.忙則等待忙則等待 D.無(wú)限等待無(wú)限等待l進(jìn)程進(jìn)程A和和B通過(guò)共享緩沖區(qū)協(xié)作完成數(shù)據(jù)處理，通過(guò)共享緩沖區(qū)協(xié)作完成數(shù)據(jù)處理，A負(fù)責(zé)產(chǎn)生負(fù)責(zé)產(chǎn)生數(shù)據(jù)并放入緩沖區(qū)，數(shù)據(jù)并放入緩沖區(qū)，B負(fù)責(zé)從緩沖區(qū)讀數(shù)據(jù)并輸出，負(fù)責(zé)從緩沖區(qū)讀數(shù)據(jù)并輸出，A和和B之間是（）關(guān)系。之間是（）關(guān)系。nA. 互斥互斥 B.同步同步 C.同步與互斥同步與互斥 D.沒(méi)有沒(méi)有332.3.3 信號(hào)量機(jī)制信號(hào)量機(jī)制l前面的互斥算法都是平等進(jìn)程間的一種協(xié)商機(jī)制，前面的互斥算法都是平等進(jìn)程間的一種協(xié)商機(jī)制，但存在的問(wèn)題是平等協(xié)商無(wú)法解決的。但存在的問(wèn)題是平

23、等協(xié)商無(wú)法解決的。l需要引入一個(gè)地位高于進(jìn)程的管理者來(lái)解決公有需要引入一個(gè)地位高于進(jìn)程的管理者來(lái)解決公有資源的使用問(wèn)題。資源的使用問(wèn)題。lOS可從進(jìn)程管理者的角度來(lái)處理進(jìn)程同步問(wèn)題，可從進(jìn)程管理者的角度來(lái)處理進(jìn)程同步問(wèn)題，信號(hào)量信號(hào)量就是就是OS提供的管理公有資源的有效手段。提供的管理公有資源的有效手段。n信號(hào)量信號(hào)量 代表代表 可用資源實(shí)體的數(shù)量可用資源實(shí)體的數(shù)量。34信號(hào)量機(jī)制：信號(hào)量機(jī)制：信號(hào)量的基本原理和思想信號(hào)量的基本原理和思想l進(jìn)程間通過(guò)信號(hào)實(shí)現(xiàn)互斥、協(xié)作。進(jìn)程間通過(guò)信號(hào)實(shí)現(xiàn)互斥、協(xié)作。n信號(hào)在邏輯意義上對(duì)應(yīng)于資源，信號(hào)可以類(lèi)似于短消息，信號(hào)在邏輯意義上對(duì)應(yīng)于資源，信號(hào)可以類(lèi)似于短

24、消息，可以緩存在某個(gè)地方?？梢跃彺嬖谀硞€(gè)地方。l進(jìn)程要申請(qǐng)互斥資源，必須等待信號(hào)的到來(lái)。進(jìn)程要申請(qǐng)互斥資源，必須等待信號(hào)的到來(lái)。n若有信號(hào)到來(lái)，則消耗一個(gè)信號(hào)后，占有資源。若有信號(hào)到來(lái)，則消耗一個(gè)信號(hào)后，占有資源。n若沒(méi)有信號(hào)，則把自己阻塞在這個(gè)信號(hào)上。若沒(méi)有信號(hào)，則把自己阻塞在這個(gè)信號(hào)上。l進(jìn)程在釋放資源時(shí)，發(fā)出釋放資源的信號(hào)。進(jìn)程在釋放資源時(shí)，發(fā)出釋放資源的信號(hào)。35l若在阻塞過(guò)程中收到信號(hào)，則消耗掉該信號(hào)后，若在阻塞過(guò)程中收到信號(hào)，則消耗掉該信號(hào)后，進(jìn)程被喚醒。進(jìn)程被喚醒。l若多個(gè)進(jìn)程阻塞在一個(gè)信號(hào)上，有信號(hào)到來(lái)，會(huì)若多個(gè)進(jìn)程阻塞在一個(gè)信號(hào)上，有信號(hào)到來(lái)，會(huì)根據(jù)調(diào)度原則，決定哪個(gè)進(jìn)程真正

25、收到該信號(hào)。根據(jù)調(diào)度原則，決定哪個(gè)進(jìn)程真正收到該信號(hào)。信號(hào)量機(jī)制：信號(hào)量機(jī)制：信號(hào)量的基本原理和思想信號(hào)量的基本原理和思想信號(hào)量機(jī)制是一種卓有成效的進(jìn)程同步工信號(hào)量機(jī)制是一種卓有成效的進(jìn)程同步工具，被廣泛應(yīng)用于單處理機(jī)和多處理機(jī)系具，被廣泛應(yīng)用于單處理機(jī)和多處理機(jī)系統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)中。統(tǒng)以及計(jì)算機(jī)網(wǎng)絡(luò)中。36信號(hào)量機(jī)制：信號(hào)量機(jī)制：信號(hào)量的具體實(shí)現(xiàn)信號(hào)量的具體實(shí)現(xiàn)l1、整型信號(hào)量、整型信號(hào)量 和和 P、V原語(yǔ)原語(yǔ)n一個(gè)整型量一個(gè)整型量s，僅通過(guò)原子操作，僅通過(guò)原子操作P(s)和和V(s)訪問(wèn)。訪問(wèn)。nP(s)： while( s= 0 ) ; s-;nV(s)： s+;P: Wait V: s

26、ignal37l整型信號(hào)量整型信號(hào)量在邏輯上在邏輯上表示可分配的資源數(shù)量表示可分配的資源數(shù)量。n初始值為該類(lèi)資源的總數(shù)量。初始值為該類(lèi)資源的總數(shù)量。lP(s)表示表示資源申請(qǐng)資源申請(qǐng)操作（進(jìn)入臨界區(qū)前調(diào)用該操作）操作（進(jìn)入臨界區(qū)前調(diào)用該操作）n信號(hào)量的值減信號(hào)量的值減1lV(s)表示表示資源釋放資源釋放操作操作(離開(kāi)臨界區(qū)前調(diào)用該操作離開(kāi)臨界區(qū)前調(diào)用該操作)n信號(hào)量的值增信號(hào)量的值增1l對(duì)信號(hào)量只能執(zhí)行對(duì)信號(hào)量只能執(zhí)行P、V操作，操作， P、V操作不可中斷。操作不可中斷。l信號(hào)量必須置一次且信號(hào)量必須置一次且只能置一次初值，初值不能只能置一次初值，初值不能為負(fù)為負(fù)。38void P( sema

27、phore s )s.value - - ; if (s.value 0 ) 調(diào)用調(diào)用block原語(yǔ)自我阻塞原語(yǔ)自我阻塞, 即將即將進(jìn)程放入阻塞隊(duì)列進(jìn)程放入阻塞隊(duì)列s.queue; 并進(jìn)行調(diào)度并進(jìn)行調(diào)度; typedef struct semaphore int value; /可用資源數(shù)可用資源數(shù) Queue queue; /被阻塞進(jìn)被阻塞進(jìn)程隊(duì)列程隊(duì)列 semaphore ；由于整型信號(hào)量機(jī)制中的由于整型信號(hào)量機(jī)制中的P操作，只要操作，只要s=0就會(huì)不斷測(cè)試，就會(huì)不斷測(cè)試，不滿足不滿足“讓權(quán)等待讓權(quán)等待”，因此，引入，因此，引入記錄型信號(hào)量記錄型信號(hào)量。l2、記錄型信號(hào)量、記錄型信號(hào)量39

28、void V(semaphore s)s.value +; if (s.value = 0 ) 從阻塞隊(duì)列從阻塞隊(duì)列s.queue取出一進(jìn)程，調(diào)用取出一進(jìn)程，調(diào)用wakeup喚醒該進(jìn)程；喚醒該進(jìn)程；40l3、AND型信號(hào)量型信號(hào)量n基本思想：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有基本思想：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要有一個(gè)資源未能分配給進(jìn)程，再一起釋放。只要有一個(gè)資源未能分配給進(jìn)程，其它所有可能分配給它的資源也不分配給它。其它所有可能分配給它的資源也不分配給它。n當(dāng)不用它時(shí)，有可能發(fā)生當(dāng)不用它時(shí)，

29、有可能發(fā)生死鎖死鎖。41process A: P(Dmutex); P(Emutex);process B: P(Emutex); P(Dmutex);若這若這2個(gè)進(jìn)程交替執(zhí)行，則個(gè)進(jìn)程交替執(zhí)行，則死鎖死鎖。用用and型信號(hào)量機(jī)制可避免上述死鎖情況型信號(hào)量機(jī)制可避免上述死鎖情況的發(fā)生。的發(fā)生。如：如：42Swait(S1, S2, , Sn) while(true) if (Si1& & Sn1) for (i=1; i=n; i+) Si-; break; else 將進(jìn)程放入相應(yīng)的等待隊(duì)列將進(jìn)程放入相應(yīng)的等待隊(duì)列; Ssignal(S1, S2, , Sn) while(true) for

30、 (i=1; i1）或互斥型信）或互斥型信號(hào)量（號(hào)量（S=1）。）。P (S, 1, 0)，可控開(kāi)關(guān)，當(dāng)，可控開(kāi)關(guān)，當(dāng) S=1 時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)，定區(qū)，S=0時(shí)，阻止進(jìn)入。時(shí)，阻止進(jìn)入。44資源分配資源分配的下限的下限資源需求資源需求量量2.3.4 信號(hào)量的應(yīng)用信號(hào)量的應(yīng)用l用信號(hào)量實(shí)現(xiàn)互斥用信號(hào)量實(shí)現(xiàn)互斥l用信號(hào)量實(shí)現(xiàn)同步用信號(hào)量實(shí)現(xiàn)同步45信號(hào)量的應(yīng)用信號(hào)量的應(yīng)用：用信號(hào)量實(shí)現(xiàn)互斥用信號(hào)量實(shí)現(xiàn)互斥l基本思想基本思想n用信號(hào)量用信號(hào)量S表示可分配的某類(lèi)資源數(shù)量。表示可分配的某類(lèi)資源數(shù)量。n用用P原語(yǔ)表示申請(qǐng)資源，原語(yǔ)表示申請(qǐng)資源，V原語(yǔ)表示釋放原語(yǔ)表示釋放

31、資源。資源。nP、V原語(yǔ)原語(yǔ)必須在臨界區(qū)前后成對(duì)出現(xiàn)必須在臨界區(qū)前后成對(duì)出現(xiàn)。n互斥信號(hào)量的初值互斥信號(hào)量的初值一般為一般為1。46l信號(hào)量的取值含義：信號(hào)量的取值含義：nS 0：某類(lèi)資源當(dāng)前可用的數(shù)量，表示還某類(lèi)資源當(dāng)前可用的數(shù)量，表示還能有能有S個(gè)進(jìn)程可分配到該資源。個(gè)進(jìn)程可分配到該資源。nS=0：表示沒(méi)有待分配資源，但也沒(méi)有進(jìn)表示沒(méi)有待分配資源，但也沒(méi)有進(jìn)程在等待資源。程在等待資源。nS0表示有表示有S個(gè)資源可用個(gè)資源可用nS=0表示無(wú)資源可用表示無(wú)資源可用nS0則則| S |表示阻塞隊(duì)列中的阻塞進(jìn)程個(gè)數(shù)表示阻塞隊(duì)列中的阻塞進(jìn)程個(gè)數(shù)n信號(hào)量的初值應(yīng)該大于等于信號(hào)量的初值應(yīng)該大于等于095

32、lP/V操作操作nP(S):表示申請(qǐng)一個(gè)資源表示申請(qǐng)一個(gè)資源 nV(S):表示釋放一個(gè)資源表示釋放一個(gè)資源n必須成對(duì)出現(xiàn)必須成對(duì)出現(xiàn)n當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程n當(dāng)為同步操作時(shí)，則在不同進(jìn)程中出現(xiàn)當(dāng)為同步操作時(shí)，則在不同進(jìn)程中出現(xiàn)n一個(gè)同步一個(gè)同步P操作與一個(gè)互斥操作與一個(gè)互斥P操作在一起時(shí)，同操作在一起時(shí)，同步步P操作在互斥操作在互斥P操作前。而兩個(gè)操作前。而兩個(gè)V操作順序無(wú)關(guān)操作順序無(wú)關(guān)緊要。緊要。96信號(hào)量機(jī)制的優(yōu)缺點(diǎn)信號(hào)量機(jī)制的優(yōu)缺點(diǎn)l優(yōu)點(diǎn)優(yōu)點(diǎn)n簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用信號(hào)量機(jī)制可解決任何同步簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用信號(hào)量機(jī)制可解決任何同步互斥

33、問(wèn)題）互斥問(wèn)題）l缺點(diǎn)缺點(diǎn)n同步操作分散：同步操作分散：信號(hào)量機(jī)制中，同步操作分散在各個(gè)進(jìn)信號(hào)量機(jī)制中，同步操作分散在各個(gè)進(jìn)程中，使用不當(dāng)就可能導(dǎo)致各進(jìn)程程中，使用不當(dāng)就可能導(dǎo)致各進(jìn)程死鎖、饑餓和不公平。死鎖、饑餓和不公平。不適合實(shí)時(shí)系統(tǒng)。不適合實(shí)時(shí)系統(tǒng)。n可讀性差：可讀性差：要了解對(duì)于一組共享變量及信號(hào)量的操作是要了解對(duì)于一組共享變量及信號(hào)量的操作是否正確，必須通讀整個(gè)系統(tǒng)或者并發(fā)程序；否正確，必須通讀整個(gè)系統(tǒng)或者并發(fā)程序；n不利于修改和維護(hù)：不利于修改和維護(hù)：各模塊的獨(dú)立性差，任一組變量或各模塊的獨(dú)立性差，任一組變量或一段代碼的修改都可能影響全局；一段代碼的修改都可能影響全局；n正確性難以

34、保證：正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個(gè)復(fù)雜的系統(tǒng)沒(méi)有邏輯錯(cuò)誤。保證這樣一個(gè)復(fù)雜的系統(tǒng)沒(méi)有邏輯錯(cuò)誤。97作業(yè)作業(yè)對(duì)于前面例題對(duì)于前面例題2，若司機(jī)和售票員的工作流程如下，若司機(jī)和售票員的工作流程如下（司機(jī)：?jiǎn)?dòng)開(kāi)車(chē)、正常行車(chē)、到站停車(chē)；售票員司機(jī)：?jiǎn)?dòng)開(kāi)車(chē)、正常行車(chē)、到站停車(chē)；售票員：開(kāi)車(chē)門(mén)、關(guān)車(chē)門(mén)、售票：開(kāi)車(chē)門(mén)、關(guān)車(chē)門(mén)、售票），），則用則用PV操作如何實(shí)現(xiàn)操作如何實(shí)現(xiàn)司機(jī)和售票員之間的同步（提示，此時(shí)初始狀態(tài)為司機(jī)和售票員之間的同步（提示，此時(shí)初始狀態(tài)為停車(chē)而還沒(méi)開(kāi)門(mén)狀態(tài)，即乘客還沒(méi)下車(chē)）。停車(chē)而還沒(méi)開(kāi)門(mén)狀態(tài)，即乘客還沒(méi)下車(chē)）。有一個(gè)

35、倉(cāng)庫(kù)，可以存放有一個(gè)倉(cāng)庫(kù)，可以存放A和和B 兩種產(chǎn)品。要求：兩種產(chǎn)品。要求：1)每次只能存入一種產(chǎn)品每次只能存入一種產(chǎn)品(A或或B)；2)NA產(chǎn)品產(chǎn)品數(shù)量數(shù)量B產(chǎn)品數(shù)量產(chǎn)品數(shù)量0）個(gè)單元的緩沖區(qū)。個(gè)單元的緩沖區(qū)。P1每次用每次用produce( )生成一個(gè)正生成一個(gè)正整數(shù)并用整數(shù)并用put( )送入緩沖區(qū)某一空單元中；送入緩沖區(qū)某一空單元中；P2每次每次用用getodd( )從該緩沖區(qū)中取出一個(gè)奇數(shù)并用從該緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd( )統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；P3每次用每次用geteven( )從從該緩沖區(qū)中取出一個(gè)偶數(shù)并用該緩沖區(qū)中取出一個(gè)偶數(shù)并用counteven( )

36、統(tǒng)計(jì)偶統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng)，并說(shuō)明所定義的信號(hào)量的含義?；コ饣顒?dòng)，并說(shuō)明所定義的信號(hào)量的含義。 992.5 進(jìn)程通信進(jìn)程通信100l并發(fā)進(jìn)程之間的交互必須滿足兩個(gè)基本要求：并發(fā)進(jìn)程之間的交互必須滿足兩個(gè)基本要求：同同步和通信步和通信。n例如，進(jìn)程同步可通過(guò)信號(hào)量，建立進(jìn)程之間的聯(lián)系，例如，進(jìn)程同步可通過(guò)信號(hào)量，建立進(jìn)程之間的聯(lián)系，相互協(xié)調(diào)運(yùn)行和協(xié)同工作。相互協(xié)調(diào)運(yùn)行和協(xié)同工作。l進(jìn)程協(xié)同工作時(shí)，需要互相交換信息，有些情況進(jìn)程協(xié)同工作時(shí)，需要互相交換信息，有些情況下進(jìn)程間交換少量信息，有些情況下進(jìn)程間交換下進(jìn)程間交

37、換少量信息，有些情況下進(jìn)程間交換大量數(shù)據(jù)。大量數(shù)據(jù)。l進(jìn)程通信進(jìn)程通信(Inter-Process Communication, IPC)：是指進(jìn)程之間的信息交換。：是指進(jìn)程之間的信息交換。101l低級(jí)進(jìn)程通信低級(jí)進(jìn)程通信n只能傳遞狀態(tài)和控制信息，如：信號(hào)量和管程。只能傳遞狀態(tài)和控制信息，如：信號(hào)量和管程。優(yōu)點(diǎn)是速度快，缺點(diǎn)：優(yōu)點(diǎn)是速度快，缺點(diǎn)：傳送傳送信息量小、效率低信息量小、效率低。通信對(duì)用戶不透明，編程復(fù)雜、容易出錯(cuò)。通信對(duì)用戶不透明，編程復(fù)雜、容易出錯(cuò)。l高級(jí)進(jìn)程通信高級(jí)進(jìn)程通信n用戶直接使用用戶直接使用OS提供的一組通信命令高效地傳送提供的一組通信命令高效地傳送大量數(shù)據(jù)大量數(shù)據(jù)。nO

38、S屏蔽了通信細(xì)節(jié)，即通信過(guò)程屏蔽了通信細(xì)節(jié)，即通信過(guò)程對(duì)用戶透明對(duì)用戶透明，減，減少了通信程序編制的復(fù)雜性。少了通信程序編制的復(fù)雜性。進(jìn)程通信的分類(lèi)進(jìn)程通信的分類(lèi)102l（1）共享存儲(chǔ)器系統(tǒng)）共享存儲(chǔ)器系統(tǒng)n基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（是低級(jí)通信）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（是低級(jí)通信）如：如：producer-consumer中的有界緩沖區(qū)。中的有界緩沖區(qū)。低效、不透明、適于少量數(shù)據(jù)的傳遞。低效、不透明、適于少量數(shù)據(jù)的傳遞。n基于共享存儲(chǔ)區(qū)的通信方式基于共享存儲(chǔ)區(qū)的通信方式共享存儲(chǔ)區(qū)（從內(nèi)存中劃分）共享存儲(chǔ)區(qū)（從內(nèi)存中劃分） 。通信過(guò)程：通信過(guò)程：n向系統(tǒng)申請(qǐng)一個(gè)或多個(gè)分區(qū)向系統(tǒng)申請(qǐng)一個(gè)或多

39、個(gè)分區(qū)n獲得分區(qū)后即可讀獲得分區(qū)后即可讀/寫(xiě)寫(xiě) 特點(diǎn)：高效、速度快、可傳輸大量數(shù)據(jù)。特點(diǎn)：高效、速度快、可傳輸大量數(shù)據(jù)。進(jìn)程通信的分類(lèi)進(jìn)程通信的分類(lèi)103l（3）消息傳遞系統(tǒng)）消息傳遞系統(tǒng) n信息單位：消息（報(bào)文）；信息單位：消息（報(bào)文）；n是目前主要的通信方式，分為是目前主要的通信方式，分為直接通信、間接通信直接通信、間接通信；n實(shí)現(xiàn)：一組通信命令（原語(yǔ)），具有透明性；實(shí)現(xiàn)：一組通信命令（原語(yǔ)），具有透明性；n可用于多處理機(jī)系統(tǒng)、分布式系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)。可用于多處理機(jī)系統(tǒng)、分布式系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)。l（2）管道（）管道（pipe）通信）通信n管道：用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程之間通信的管道：

40、用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程之間通信的共享文件（共享文件（pipe文件）。文件）。n功能：大量的數(shù)據(jù)發(fā)收。功能：大量的數(shù)據(jù)發(fā)收。n注意：互斥地使用管道、同步、對(duì)方是否存在。注意：互斥地使用管道、同步、對(duì)方是否存在。進(jìn)程通信的分類(lèi)進(jìn)程通信的分類(lèi)104l（4）客戶機(jī)）客戶機(jī)-服務(wù)器系統(tǒng)服務(wù)器系統(tǒng)n是網(wǎng)絡(luò)環(huán)境中的主流通信機(jī)制。是網(wǎng)絡(luò)環(huán)境中的主流通信機(jī)制。n主要的實(shí)現(xiàn)方法：主要的實(shí)現(xiàn)方法：套接字套接字遠(yuǎn)程過(guò)程調(diào)用和遠(yuǎn)程方法調(diào)用遠(yuǎn)程過(guò)程調(diào)用和遠(yuǎn)程方法調(diào)用消息傳遞通信的實(shí)現(xiàn)方式消息傳遞通信的實(shí)現(xiàn)方式105l(1)直接通信方式直接通信方式nsend(Receiver, message)nreceive(S

41、ender, message)l(2)間接通信方式（可實(shí)現(xiàn)非實(shí)時(shí)通信）間接通信方式（可實(shí)現(xiàn)非實(shí)時(shí)通信）n優(yōu)點(diǎn)：優(yōu)點(diǎn)：在讀在讀/寫(xiě)時(shí)間上的隨機(jī)性寫(xiě)時(shí)間上的隨機(jī)性n寫(xiě)進(jìn)程寫(xiě)進(jìn)程-信箱信箱（中間實(shí)體）（中間實(shí)體）-讀進(jìn)程讀進(jìn)程n信箱的創(chuàng)建與撤消信箱的創(chuàng)建與撤消信箱名、屬性（公用、私用、共享）、共享者名字信箱名、屬性（公用、私用、共享）、共享者名字n消息的發(fā)送和接收消息的發(fā)送和接收Send (mailbox, message)Receive (mailbox, message)消息傳遞通信的實(shí)現(xiàn)方式消息傳遞通信的實(shí)現(xiàn)方式106n信箱類(lèi)型信箱類(lèi)型私用：擁有者有讀私用：擁有者有讀/寫(xiě)權(quán)，其它只有寫(xiě)權(quán)，存在

42、期寫(xiě)權(quán)，其它只有寫(xiě)權(quán)，存在期進(jìn)程存在期。進(jìn)程存在期。公用：系統(tǒng)創(chuàng)建，雙向，存在期公用：系統(tǒng)創(chuàng)建，雙向，存在期=系統(tǒng)存在期。系統(tǒng)存在期。共享信箱：創(chuàng)建時(shí)指明其共享者，雙向。共享信箱：創(chuàng)建時(shí)指明其共享者，雙向。n利用郵箱通信時(shí)，發(fā)送、接收進(jìn)程之間的關(guān)系利用郵箱通信時(shí)，發(fā)送、接收進(jìn)程之間的關(guān)系一對(duì)一關(guān)系；一對(duì)一關(guān)系；多對(duì)一關(guān)系多對(duì)一關(guān)系(C/S交互交互)；一對(duì)多關(guān)系一對(duì)多關(guān)系(廣播方式廣播方式)；多對(duì)多關(guān)系多對(duì)多關(guān)系(公用信箱公用信箱)。消息傳遞系統(tǒng)實(shí)現(xiàn)中的幾個(gè)問(wèn)題消息傳遞系統(tǒng)實(shí)現(xiàn)中的幾個(gè)問(wèn)題107l(1)(1)通信鏈路通信鏈路n顯式建立：（多用于網(wǎng)絡(luò)）顯式建立：（多用于網(wǎng)絡(luò)）利用建立鏈路的原語(yǔ)利用

43、建立鏈路的原語(yǔ)n隱式建立：（多用于單機(jī)系統(tǒng)）隱式建立：（多用于單機(jī)系統(tǒng)）使用發(fā)送命令時(shí)，系統(tǒng)自動(dòng)建立使用發(fā)送命令時(shí)，系統(tǒng)自動(dòng)建立n鏈路類(lèi)型：鏈路類(lèi)型：由通信方式分：?jiǎn)蜗蜴溌贰㈦p向鏈路由通信方式分：?jiǎn)蜗蜴溌?、雙向鏈路消息傳遞系統(tǒng)實(shí)現(xiàn)中的幾個(gè)問(wèn)題消息傳遞系統(tǒng)實(shí)現(xiàn)中的幾個(gè)問(wèn)題108l(2)消息格式消息格式 n消息頭消息頭含控制信息，如收含控制信息，如收/發(fā)進(jìn)程名、消息長(zhǎng)度、類(lèi)型、發(fā)進(jìn)程名、消息長(zhǎng)度、類(lèi)型、編號(hào)編號(hào)n消息正文消息正文n定長(zhǎng)消息定長(zhǎng)消息系統(tǒng)開(kāi)銷(xiāo)小，對(duì)傳長(zhǎng)消息的用戶不便系統(tǒng)開(kāi)銷(xiāo)小，對(duì)傳長(zhǎng)消息的用戶不便n變長(zhǎng)消息變長(zhǎng)消息開(kāi)銷(xiāo)大，對(duì)用戶方便。開(kāi)銷(xiāo)大，對(duì)用戶方便。消息傳遞系統(tǒng)實(shí)現(xiàn)中的幾個(gè)問(wèn)題消息

44、傳遞系統(tǒng)實(shí)現(xiàn)中的幾個(gè)問(wèn)題109l(3)進(jìn)程同步方式進(jìn)程同步方式進(jìn)程間的通信需要同步進(jìn)程間的通信需要同步n發(fā)送和接收進(jìn)程阻塞發(fā)送和接收進(jìn)程阻塞用于緊密同步，無(wú)緩沖區(qū)時(shí)。用于緊密同步，無(wú)緩沖區(qū)時(shí)。n發(fā)送進(jìn)程不阻塞，接收進(jìn)程阻塞發(fā)送進(jìn)程不阻塞，接收進(jìn)程阻塞（多個(gè)）（多個(gè)）相當(dāng)于接收進(jìn)程（可能是多個(gè)）一直等待發(fā)送進(jìn)相當(dāng)于接收進(jìn)程（可能是多個(gè)）一直等待發(fā)送進(jìn)程，如：打印進(jìn)程等待打印任務(wù)。程，如：打印進(jìn)程等待打印任務(wù)。n發(fā)送發(fā)送/ /接收進(jìn)程均不阻塞接收進(jìn)程均不阻塞一般在發(fā)、收進(jìn)程間有多個(gè)緩沖區(qū)時(shí)。一般在發(fā)、收進(jìn)程間有多個(gè)緩沖區(qū)時(shí)。消息傳遞系統(tǒng)實(shí)例消息傳遞系統(tǒng)實(shí)例110l消息緩沖隊(duì)列通信機(jī)制消息緩沖隊(duì)列通

45、信機(jī)制n是直接消息傳遞系統(tǒng)是直接消息傳遞系統(tǒng)n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)消息緩沖區(qū)消息緩沖區(qū)typedef struct message_bufferint sender; /發(fā)送者的標(biāo)識(shí)符發(fā)送者的標(biāo)識(shí)符int size; /消息長(zhǎng)度消息長(zhǎng)度char *text; /消息正文消息正文struct message_buffer *next; /指向下一個(gè)消息緩沖區(qū)指向下一個(gè)消息緩沖區(qū)PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)中有關(guān)通信的數(shù)據(jù)項(xiàng)struct message_buffer *mq; /消息隊(duì)列隊(duì)首指針消息隊(duì)列隊(duì)首指針semaphore mutex; /消息隊(duì)列互斥信號(hào)量消息隊(duì)列互斥信號(hào)量semaphore sm

46、; /消息隊(duì)列資源信號(hào)量（消息數(shù)）消息隊(duì)列資源信號(hào)量（消息數(shù)）消息傳遞系統(tǒng)實(shí)例消息傳遞系統(tǒng)實(shí)例111l消息緩沖隊(duì)列通信機(jī)制消息緩沖隊(duì)列通信機(jī)制n發(fā)送原語(yǔ)發(fā)送原語(yǔ)void send(receiver, a) getbuf( a.size,i ); /申請(qǐng)緩沖區(qū)申請(qǐng)緩沖區(qū) i.sender=a.sender; i.size=a.size; copy( i.text, a.text ); i.next=0; getid( PCBset, receiver.j ); wait(j.mutex); insert(j.mq, i); signal(j.mutex); signal(j.sm); 112n接

47、收原語(yǔ)接收原語(yǔ)void receive(b) j=internal name; wait(j.sm); wait(j.mutex); remove(j.mq, i); signal(j.mutex); b.sender=i.sender; b.size=i.size; copy( b.text, i.text ); releasebuf(i);1132.6 線程及其實(shí)現(xiàn)線程及其實(shí)現(xiàn)114l由于進(jìn)程是一個(gè)資源的擁有者，因而在創(chuàng)建、撤由于進(jìn)程是一個(gè)資源的擁有者，因而在創(chuàng)建、撤消和切換中，系統(tǒng)必須為之付出較大的時(shí)空開(kāi)銷(xiāo)。消和切換中，系統(tǒng)必須為之付出較大的時(shí)空開(kāi)銷(xiāo)。n在系統(tǒng)中設(shè)置的進(jìn)程數(shù)目不宜過(guò)多，進(jìn)

48、程切換的頻率在系統(tǒng)中設(shè)置的進(jìn)程數(shù)目不宜過(guò)多，進(jìn)程切換的頻率也不宜過(guò)高，這限制了并發(fā)程度。也不宜過(guò)高，這限制了并發(fā)程度。l引入線程引入線程，作為獨(dú)立調(diào)度和分派的單位，作為獨(dú)立調(diào)度和分派的單位，而而不獨(dú)不獨(dú)立擁有資源立擁有資源（僅有少量基本資源），與其它線程（僅有少量基本資源），與其它線程共享同一進(jìn)程的資源，減少了系統(tǒng)的時(shí)空開(kāi)銷(xiāo)。共享同一進(jìn)程的資源，減少了系統(tǒng)的時(shí)空開(kāi)銷(xiāo)。l實(shí)質(zhì)：把進(jìn)程的任務(wù)劃分為更小、不能再分的、實(shí)質(zhì)：把進(jìn)程的任務(wù)劃分為更小、不能再分的、具有獨(dú)立功能的單位，以提高程序的并發(fā)度。具有獨(dú)立功能的單位，以提高程序的并發(fā)度。線程的屬性線程的屬性l輕型實(shí)體輕型實(shí)體 n只擁有一點(diǎn)必不可少的資

49、源，如：只擁有一點(diǎn)必不可少的資源，如：TCB、寄存器上下文、寄存器上下文和棧和棧l獨(dú)立調(diào)度和分派的基本單位獨(dú)立調(diào)度和分派的基本單位 n具有具有就緒、阻塞、執(zhí)行就緒、阻塞、執(zhí)行三種基本狀態(tài)三種基本狀態(tài)n線程的創(chuàng)建、終止時(shí)間比進(jìn)程短線程的創(chuàng)建、終止時(shí)間比進(jìn)程短n同進(jìn)程內(nèi)線程切換時(shí)間短，系統(tǒng)開(kāi)銷(xiāo)小同進(jìn)程內(nèi)線程切換時(shí)間短，系統(tǒng)開(kāi)銷(xiāo)小l可并發(fā)執(zhí)行可并發(fā)執(zhí)行n同一進(jìn)程的線程并發(fā)執(zhí)行；不同進(jìn)程間的線程并發(fā)執(zhí)行同一進(jìn)程的線程并發(fā)執(zhí)行；不同進(jìn)程間的線程并發(fā)執(zhí)行l(wèi)共享進(jìn)程資源共享進(jìn)程資源 n由于同進(jìn)程內(nèi)線程間共享內(nèi)存和文件資源，可直接進(jìn)行由于同進(jìn)程內(nèi)線程間共享內(nèi)存和文件資源，可直接進(jìn)行不通過(guò)內(nèi)核的通信不通過(guò)內(nèi)核的

50、通信115116/64l單線程與多線程的進(jìn)程單線程與多線程的進(jìn)程被進(jìn)程內(nèi)的被進(jìn)程內(nèi)的線程共享線程共享線程線程資源資源線程與進(jìn)程的比較線程與進(jìn)程的比較l(1)(1)調(diào)度。調(diào)度。無(wú)線程時(shí)，獨(dú)立調(diào)度、分派的基本單位是無(wú)線程時(shí)，獨(dú)立調(diào)度、分派的基本單位是進(jìn)程。而引入線程后，把線程作為調(diào)度和分派的基進(jìn)程。而引入線程后，把線程作為調(diào)度和分派的基本單位，本單位，而進(jìn)程而進(jìn)程只只是資源的擁有者。是資源的擁有者。n同一進(jìn)程中的線程之間切換，不會(huì)引起進(jìn)程切換同一進(jìn)程中的線程之間切換，不會(huì)引起進(jìn)程切換，不不同同進(jìn)進(jìn)程程中中的線程之間切換，會(huì)引起進(jìn)程切換。的線程之間切換，會(huì)引起進(jìn)程切換。l(2)(2)并發(fā)性。并發(fā)性。

51、引入線程后，進(jìn)程間可以并發(fā)執(zhí)行，一引入線程后，進(jìn)程間可以并發(fā)執(zhí)行，一個(gè)進(jìn)程中的多個(gè)線程間亦可并發(fā)執(zhí)行，不同進(jìn)程中個(gè)進(jìn)程中的多個(gè)線程間亦可并發(fā)執(zhí)行，不同進(jìn)程中的線程也能并發(fā)，因而，使的線程也能并發(fā)，因而，使OSOS具有更好的并發(fā)性，具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。117線程與進(jìn)程的比較線程與進(jìn)程的比較l(3)(3)擁有資源。擁有資源。進(jìn)程是擁有資源的獨(dú)立單位。線程自進(jìn)程是擁有資源的獨(dú)立單位。線程自己一般不擁有系統(tǒng)資源，僅有一點(diǎn)必不可少的資源己一般不擁有系統(tǒng)資源，僅有一點(diǎn)必不可少的資源，但它可以訪問(wèn)其隸屬進(jìn)程的資源。，但它可以訪問(wèn)其隸屬進(jìn)程的資源。l(4)(4)獨(dú)立性。獨(dú)立性。同一進(jìn)程中的線程間的獨(dú)立性要低于不同一進(jìn)程中的線程間的獨(dú)立性要低于不同進(jìn)程之間的獨(dú)立性。同進(jìn)程之間的獨(dú)立性。l