1、現(xiàn)代操作系統(tǒng)第二章進(jìn)程與線程習(xí)題1. 圖2-2中給出了三個(gè)進(jìn)程狀態(tài)，在理論上，三個(gè)狀態(tài)可以有六種轉(zhuǎn)換，每個(gè)狀態(tài)兩個(gè)。但是，圖中只給出了四種轉(zhuǎn)換。有沒有可能發(fā)生其他兩種轉(zhuǎn)換中的一個(gè)或兩個(gè)？A：從阻塞到運(yùn)行的轉(zhuǎn)換是可以想象的。假設(shè)某個(gè)進(jìn)程在I/O上阻塞，而且I/O結(jié)束，如果此時(shí)CPU空閑，該進(jìn)程就可以從阻塞態(tài)直接轉(zhuǎn)到運(yùn)行態(tài)。而另外一種轉(zhuǎn)換（從阻塞態(tài)到就緒態(tài)）是不可能的。一個(gè)就緒進(jìn)程是不可能做任何會(huì)產(chǎn)生阻塞的“0或者別的什么事情。只有運(yùn)行的進(jìn)程才能被阻塞。2. 假設(shè)要設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來(lái)完成進(jìn)程切換。CPU需要哪些信息？請(qǐng)描述用硬件完成進(jìn)程切換的工作過(guò)程。A：應(yīng)該有一

2、個(gè)寄存器包含當(dāng)前進(jìn)程表項(xiàng)的指針。當(dāng)I/O結(jié)束時(shí)，CPU將把當(dāng)前的機(jī)器狀態(tài)存入到當(dāng)前進(jìn)程表項(xiàng)中。然后，將轉(zhuǎn)到中斷設(shè)備的中斷向量，讀取另一個(gè)過(guò)程表項(xiàng)的指針（服務(wù)例程），然后，就可以啟動(dòng)這個(gè)進(jìn)程了。3. 當(dāng)代計(jì)算機(jī)中，為什么中斷處理程序至少有一部分是用匯編語(yǔ)言編寫的？A：通常，高級(jí)語(yǔ)言不允許訪問CPU硬件，而這種訪問是必需的。例如，中斷處理程序可能需要禁用和啟用某個(gè)特定設(shè)備的中斷服務(wù)，或者處理進(jìn)程堆棧的數(shù)據(jù)。另外，中斷服務(wù)例程需要盡快地執(zhí)行。（補(bǔ)充）主要是出于效率方面的考量。中斷處理程序需要在盡量短的時(shí)間內(nèi)完成所需的必要處理，盡量減少%6U>d<=%66<frlvdndDMfd*酬

3、彳硏郵ng辭0/1圳毘'毘觸T=9N9SZ/(9NZTS-99HW&4iSM:V6<7e»o/i¥V'%66宙儲(chǔ)nd?9S。回arneieH(N44WX%)9N9S?m霹蘇尊°flNZTSm駿斟HK中策'999i/i別WlftM+H-9%SZl*E=Sv(SO):Vi4；駟醐MDmsOile»卻郵畤一擊齟輙°«S>kSlim商錠岸詼I刪蜜雌42s°w«ssaM=ewn;«極H宙觀鯽礎(chǔ)，回劃宙BrnSfW翊，匪理星ms佳翟鴦世g自畐韭懸甜咤妙琳韻蘭血竽土型任k!繪

4、劉«ss±'弼：邁曲彌姬創(chuàng)紳m:v6銀M6W陶卿砂申農(nóng)"酹案期減1剛晦輝卿矚翩豳測(cè)卿叭。&解酗理姬鯉Bssxiafl，smsas±i£ii£¥!nrs，蜩6mm«s/s融MgmrMWsna4IS書6、S.920¥8CPUa畫。ssi、«SIZ350*。wmoW459lma、cpu£aB尊Tp>nN7596cpuit爲(wèi)畫帖40min、B33tH40/75*H5333min8蠱Jssws(ssss6±s)-aura3§事Dr40*畏CPUSS97A

5、:進(jìn)aB1»"TP>n"T(04>6HT0.004096U99.6*ssss.S94SH10為什么圖2-11a的模式不適合用于在內(nèi)存使用高速緩存的文件服務(wù)器？每個(gè)進(jìn)程可以有自己的高速緩存嗎？A:即使是有可能實(shí)現(xiàn)，也是很難保持文件系統(tǒng)的一致性。假設(shè)某個(gè)客戶進(jìn)程給服務(wù)器進(jìn)程1發(fā)送請(qǐng)求要更新文件。該進(jìn)程更新其內(nèi)存的cache項(xiàng)。然后，另一個(gè)客戶進(jìn)程給服務(wù)器進(jìn)程2發(fā)送請(qǐng)求讀取該文件。不幸的是，如果該文件還在cache中，服務(wù)器進(jìn)程2對(duì)此毫不知情，將返回過(guò)時(shí)的數(shù)據(jù)。如果第一個(gè)進(jìn)程在緩沖后將文件寫到磁盤中，而服務(wù)器進(jìn)程2每次讀取時(shí)檢查磁盤其緩存的備份是否是最新的，

6、系統(tǒng)還可以工作，但是需要避免磁盤訪問的所有緩存系統(tǒng)。（個(gè)人認(rèn)為，高速緩存應(yīng)該每個(gè)進(jìn)程共享，因?yàn)椴皇敲總€(gè)進(jìn)程都需要頻繁讀寫數(shù)據(jù)，如果每個(gè)進(jìn)程都分配cache會(huì)造成資源浪費(fèi)。11當(dāng)一個(gè)多線程進(jìn)程創(chuàng)建子進(jìn)程時(shí)，如果子進(jìn)程復(fù)制父進(jìn)程的所有線程，就會(huì)出現(xiàn)問題:假如夫進(jìn)程中有一個(gè)線程正在等待鍵盤輸入，現(xiàn)在就有兩個(gè)線程在等待鍵盤輸入，父進(jìn)程和子進(jìn)程各有一個(gè)。這種問題在單線程進(jìn)程中也會(huì)發(fā)生嗎？A:不會(huì)。如果單線程進(jìn)程在鍵盤上阻塞，就不能創(chuàng)建子進(jìn)程。（而多線程進(jìn)程在一個(gè)線程阻塞時(shí)可以運(yùn)行另一個(gè)線程，整個(gè)進(jìn)程不會(huì)因此被阻塞。）12在圖2-8中，給出了一個(gè)多線程Web服務(wù)器。如果讀取文件的惟一途徑是正常的阻塞rea

7、d系統(tǒng)調(diào)用，那么Web服務(wù)器應(yīng)該使用用戶級(jí)線程還是內(nèi)核級(jí)線程？為什么？A:當(dāng)工作者線程從磁盤讀取Web頁(yè)時(shí)，它就會(huì)被阻塞。如果使用用戶級(jí)線程，該動(dòng)作將阻塞整個(gè)進(jìn)程，而破壞多線程的價(jià)值。這就是使用內(nèi)核線程的某些線程的阻塞不會(huì)影響到其他線程。13在本章中，我們介紹了多線程Web服務(wù)器，說(shuō)明它比單線程服務(wù)器和有限狀態(tài)機(jī)服務(wù)器更好的原因。存在單線程服務(wù)器更好一些的情形嗎？請(qǐng)舉例。A:在多線程Web服務(wù)器中，由分派程序從網(wǎng)絡(luò)中讀入工作請(qǐng)求，在檢查請(qǐng)求后，分派線程挑選一個(gè)空轉(zhuǎn)的（即被阻塞的）工作線程，提交該請(qǐng)求。在工作線程被喚醒后，他檢查有關(guān)的請(qǐng)求是否在Web頁(yè)面高速緩存中，這個(gè)高速緩存是所有線程否可以訪

8、問的。如果沒有，該線程開始一個(gè)從磁盤調(diào)入頁(yè)面的read操作，并且阻塞知道該磁盤操作完成。在上述線程被阻塞在磁盤操作上時(shí)，分派線程可能挑選另一個(gè)線程運(yùn)行，可以有效利用CPU資源。而在單線程服務(wù)器上，只能等第一個(gè)線程完成后，才能開始第二個(gè)線程。也存在單線程服務(wù)器更好的情形。如果服務(wù)器是完全CPU綁定的，則不需要多線程。這只會(huì)增加不必要的復(fù)雜性。假設(shè)某個(gè)百萬(wàn)人口區(qū)域的電話查號(hào)系統(tǒng)（類似于114），如果每個(gè)（姓名，電話號(hào)碼）記錄為64個(gè)字符，整個(gè)的數(shù)據(jù)庫(kù)則為64MB，這就很容易全部讀入服務(wù)器內(nèi)存中以提供快速的查詢。a:lissamsssB-ass»sSBs-LssCPU番CPUsmswcpu

9、7A:S43SS-ssfflsaiMisMaISMSSS3DtyEmssCPU。s34s«issiBxtswa3-7BMS、m衣HHTF凹IU7B昴凹IU、a:靈aMSsa畫naB»。sssfilss、SSMWi、Isiiffi17.請(qǐng)對(duì)使用單線程文件服務(wù)器和多線程文件服務(wù)器讀取文件進(jìn)行比較。假設(shè)所需要的數(shù)據(jù)都在塊高速緩存中，獲得工作請(qǐng)求，分派工作，并處理其余必要工作需要花費(fèi)12ms。如果在時(shí)間過(guò)去1/3時(shí)，需要一個(gè)磁盤操作，額外花費(fèi)75ms，此時(shí)該線程進(jìn)入睡眠。單線程服務(wù)器每秒鐘可以處理多少個(gè)請(qǐng)求？多線程服務(wù)器呢？A:在單線程情況下，cache命中需要12ms,cache

10、未命中需要87ms，其加權(quán)平均為2/312+1/387=37ms，秒鐘可以完成1s/37ms=27個(gè).在多線程情況下，所有磁盤等待都是重疊的，因此每個(gè)請(qǐng)求耗時(shí)12ms，一秒鐘可以完成1s/12ms=833個(gè)（個(gè)人認(rèn)為這樣算不太準(zhǔn)確，因?yàn)樽詈蟮膸讉€(gè)線程如果cache未命中的話，就需要87ms，可能是完不成的，不過(guò)這個(gè)題意翻譯的不是很清楚，什么叫做“時(shí)間過(guò)去1/3時(shí)”，估計(jì)原意應(yīng)該是”有1/3的時(shí)間需要額外的磁盤操作“。這樣平均算下來(lái)也可以忽略cache未命中發(fā)生的分布情況。）18在用戶態(tài)實(shí)現(xiàn)線程的最大的優(yōu)點(diǎn)是什么？最大的缺點(diǎn)是什么？A:最大的優(yōu)勢(shì)就是效率。不需要陷入內(nèi)核來(lái)切換線程。最大的缺點(diǎn)是，

11、如果一個(gè)線程阻塞，整個(gè)進(jìn)程都會(huì)阻塞。19在圖2-15中創(chuàng)建線程和線程打印消息是隨機(jī)交織在一起的。有沒有方法可以嚴(yán)格按照以下次序運(yùn)行:創(chuàng)建線程1，線程1打印消息，線程1結(jié)束，創(chuàng)建線程2，線程2打印消息，線程2結(jié)束，以此類推；如果有，是什么方法，如果沒有請(qǐng)解釋原因A:是的，這是可以做到的。每次執(zhí)行pthread-create后，主程序可以調(diào)用pthread_join等待剛剛創(chuàng)建的線程退出后再創(chuàng)建下一個(gè)線程。20在討論線程中的全局變量時(shí)，曾使用過(guò)程create_global將存儲(chǔ)分配給指向變量的指針，而不是變量自身。這是必需的嗎？還是直接使用變量自身也可行？A:將存儲(chǔ)分配給指針是確實(shí)必要的，因?yàn)槿?/p>

12、變的大小是未知的。它可能是從字符到浮點(diǎn)數(shù)數(shù)組的任何類型。如果保存其值，就不得不把其大小傳遞給create_global，這都沒有問題，但是必須將其類型作為set_global的第二個(gè)，那么read_global返回的類型是不確定的。21.考慮一個(gè)線程全部在用戶態(tài)實(shí)現(xiàn)的系統(tǒng)，該運(yùn)行時(shí)系統(tǒng)每秒鐘獲得一個(gè)時(shí)鐘中斷。當(dāng)某個(gè)線程正在運(yùn)行時(shí)系統(tǒng)中執(zhí)行時(shí)發(fā)生一個(gè)時(shí)鐘中斷，此時(shí)會(huì)出現(xiàn)什么問題？你有什么解決該問題的建議嗎？A:runtime系統(tǒng)可以正好在這一時(shí)刻阻塞或者解除阻塞某個(gè)線程，并且忙于處理調(diào)度隊(duì)列。此時(shí)并不適合于時(shí)鐘中斷處理程序開始檢查該隊(duì)列是否應(yīng)該進(jìn)行線程切換，因?yàn)樗鼈兛赡芴幱诓灰恢碌臓顟B(tài)。解決方法

13、可以是:當(dāng)進(jìn)入runtime系統(tǒng)后，設(shè)一個(gè)標(biāo)志。時(shí)鐘處理程序?qū)⒌皆摌?biāo)志，并且設(shè)其自己的標(biāo)志，然后返回。當(dāng)runtime系統(tǒng)完成時(shí)，它將檢測(cè)時(shí)鐘標(biāo)志，是否有時(shí)鐘中斷發(fā)生，并且現(xiàn)在運(yùn)行時(shí)鐘處理程序。22假設(shè)一個(gè)操作系統(tǒng)中不存在類似于select的系統(tǒng)調(diào)用來(lái)提前了解在從文件、管道或設(shè)備中讀取時(shí)是否安全，不過(guò)該操作系統(tǒng)確實(shí)允許設(shè)置報(bào)警時(shí)鐘，以便中斷阻塞的系統(tǒng)調(diào)用。在上述條件下，是否有可能在用戶態(tài)中實(shí)現(xiàn)一個(gè)線程包？請(qǐng)討論。A:這是可能的，不過(guò)效率很低。線程想要做一個(gè)系統(tǒng)調(diào)用，首先設(shè)定警報(bào)定時(shí)器，然后才執(zhí)行調(diào)用。如果線程阻塞，定時(shí)器將控制歸還給線程包。當(dāng)然，大多數(shù)調(diào)用是不阻塞的，而定時(shí)器必須被清除。每個(gè)可

14、能被阻塞的系統(tǒng)調(diào)用都必須作為3個(gè)系統(tǒng)調(diào)用來(lái)執(zhí)行。如果定時(shí)器過(guò)早失效，各種問題都可能發(fā)生。用這種方法建立線程包并不好。23兩個(gè)進(jìn)程在一個(gè)共享內(nèi)存的多處理器（兩個(gè)CPU）上運(yùn)行，當(dāng)他們要共享一塊內(nèi)存時(shí)，圖2-23中使用turn變量的忙等待解決方案還有效嗎？A:仍然有效，但也仍舊是忙等待。24在搶占式進(jìn)程調(diào)度的條件下，圖2-24中互斥問題的Peterson解法可行嗎？如果是非搶占式調(diào)度呢？A:對(duì)搶占式調(diào)度可行。事實(shí)上，這種解法就是為它設(shè)計(jì)的。而對(duì)于林占式調(diào)度，可能會(huì)失敗?？紤]這種情況：turn被初始化為0,但進(jìn)程1先開始運(yùn)行了，它就會(huì)一直循環(huán)，但不釋放CPU，具有忙等待的缺點(diǎn).25.2.3.4節(jié)中所

15、討論的優(yōu)先級(jí)反轉(zhuǎn)問題在用戶級(jí)線程中是否可能發(fā)生？為什么？A:當(dāng)?shù)蛢?yōu)先級(jí)進(jìn)程位于其臨界區(qū)，而高優(yōu)先級(jí)進(jìn)程就緒并且被調(diào)度時(shí)，將發(fā)生優(yōu)先級(jí)倒置問題。如果使用忙等待，高優(yōu)先級(jí)進(jìn)程將一直運(yùn)行。對(duì)于用戶級(jí)線程，不可能發(fā)生低優(yōu)先級(jí)線程突然被剝奪而允許高優(yōu)先級(jí)線程運(yùn)行，因?yàn)槭遣豢蓜儕Z的。而內(nèi)核級(jí)線程，就會(huì)出現(xiàn)這個(gè)問題。26.2.3.4節(jié)中描述了一種有高優(yōu)先級(jí)進(jìn)程H和低優(yōu)先級(jí)進(jìn)程L的情況，導(dǎo)致了H陷入死循環(huán)。若采用輪轉(zhuǎn)調(diào)度算法而不是優(yōu)先級(jí)調(diào)度算法，還會(huì)發(fā)生這樣問題嗎？請(qǐng)討論。A:不會(huì)發(fā)生這樣的問題。在輪轉(zhuǎn)調(diào)度算法下。L遲早會(huì)運(yùn)行，最終它將會(huì)離開臨界區(qū)。關(guān)鍵是，在優(yōu)先級(jí)調(diào)度算法下，L永遠(yuǎn)不會(huì)運(yùn)行；在輪轉(zhuǎn)循環(huán)下，它

16、定期得到一個(gè)正常的時(shí)間片，所以有機(jī)會(huì)離開其臨界區(qū)。27. 在使用線程的系統(tǒng)中，若使用用戶級(jí)線程，是每個(gè)線程一個(gè)棧還是每個(gè)進(jìn)程一個(gè)棧？如果使用內(nèi)核級(jí)線程呢？請(qǐng)解釋。A:每個(gè)線程都是自己調(diào)用例程，因此它必須有其自己的堆棧以保存局部變量、返回地址等等。這一點(diǎn)用戶級(jí)線程和內(nèi)核級(jí)線程是一樣的。28. 在開發(fā)計(jì)算機(jī)時(shí)，通常首先用一個(gè)程序模擬執(zhí)行，一次運(yùn)行一條指令，多處理器也嚴(yán)格按此模擬。在這種沒有同時(shí)事件發(fā)生的情形下，會(huì)出現(xiàn)競(jìng)爭(zhēng)條件嗎？A：（競(jìng)爭(zhēng)條件指多個(gè)線程或者進(jìn)程在讀寫一個(gè)共享數(shù)據(jù)時(shí)結(jié)果依賴于它們執(zhí)行的相對(duì)時(shí)間的情形。競(jìng)爭(zhēng)條件發(fā)生在當(dāng)多個(gè)進(jìn)程或者線程在讀寫數(shù)據(jù)時(shí)，其最終的的結(jié)果依賴于多個(gè)進(jìn)程的指令執(zhí)行

17、順序。）是的。模擬計(jì)算機(jī)也可以是多道程序設(shè)計(jì)的。例如，在進(jìn)程A運(yùn)行時(shí)，它讀取一些共享變。然后發(fā)生了一個(gè)模擬時(shí)鐘周期和進(jìn)程B運(yùn)行。它也讀取相同的變量，然后對(duì)變進(jìn)行了加1操作。當(dāng)進(jìn)程A運(yùn)行時(shí)，如果它也對(duì)變進(jìn)行了加1操作，就發(fā)生了競(jìng)爭(zhēng)條件。29. 將生產(chǎn)者-消費(fèi)者問題擴(kuò)展成一個(gè)多生產(chǎn)者-多消費(fèi)者的問題，生產(chǎn)（消費(fèi)）者都寫（讀）一個(gè)共享的緩沖區(qū)，每個(gè)生產(chǎn)者和消費(fèi)者都在自己的線程中執(zhí)行。圖2-28中使用信號(hào)的解法在這個(gè)系統(tǒng)中還可行嗎？A:可行。在給定的某個(gè)時(shí)刻，只有一個(gè)生產(chǎn)者（消費(fèi)者）可以向（從）緩沖30考慮對(duì)于兩個(gè)進(jìn)程P0和P1的互斥問題的解決方案。假設(shè)變初始值為0。P0的代碼如下：pl的代碼是將上述

18、代碼中的0替換為1。該方法是否能處理互斥問題中所有可能的情形？A:該解決方案滿足互斥，因?yàn)閮蓚€(gè)流程不可能同時(shí)處于CriticalSection。也就是說(shuō)，當(dāng)turn為0時(shí)，P0可以執(zhí)行其臨界區(qū)，但P1不能執(zhí)行。當(dāng)turn為1也有相似的情況。但是，這假設(shè)P0必須先運(yùn)行。如果P1產(chǎn)生某些東西并將其放入緩沖區(qū)，那么當(dāng)P0可以進(jìn)入其臨界區(qū)時(shí)，它會(huì)發(fā)現(xiàn)緩沖區(qū)為空并阻塞。而且，該解決方案需要嚴(yán)格交替兩個(gè)過(guò)程，這是不希望發(fā)生的。31一個(gè)可以屏蔽中斷的操作系統(tǒng)如何實(shí)現(xiàn)信號(hào)量？A:執(zhí)行信號(hào)操作，操作系統(tǒng)首先要禁用中斷。然后，它讀取信號(hào)的如果執(zhí)行down操作，而信號(hào)等于0,就將調(diào)用進(jìn)程放入與信號(hào)有關(guān)的阻塞進(jìn)程列表

19、中。如果執(zhí)行up操作，必須檢測(cè)看是否有任何進(jìn)程在信號(hào)上被阻塞。如果有一個(gè)或多個(gè)進(jìn)程被阻塞，從阻塞進(jìn)程的列表中移出一個(gè)，使之就緒。當(dāng)所有這些操作都完成后，就可以開啟中斷了。書中的原話是：操作系統(tǒng)只需在執(zhí)行以下操作時(shí)暫時(shí)屏蔽全部中斷：測(cè)試信號(hào)、更新信號(hào)量以及在需要時(shí)是某個(gè)進(jìn)程睡眠。:32.請(qǐng)說(shuō)明如何僅通過(guò)二元信號(hào)量和普通機(jī)器指令實(shí)現(xiàn)計(jì)數(shù)信號(hào)量（即可以保持一個(gè)任意值的信號(hào)量）。:A:用兩個(gè)二值信號(hào)量和一個(gè)計(jì)數(shù)器counter實(shí)現(xiàn)一個(gè)計(jì)數(shù)信號(hào)量：M用于互斥,B用于阻塞,counter用于記錄up減去down的次數(shù)，再用一個(gè)鏈表來(lái)記錄阻塞在這個(gè)計(jì)數(shù)信號(hào)量上的進(jìn)程。down的實(shí)現(xiàn)：進(jìn)程先對(duì)M進(jìn)行down來(lái)

20、獲得counter、鏈表的獨(dú)占訪問權(quán)，并把counter減1。如果counter大于等于0，接對(duì)M進(jìn)行up即可；否則，記錄在鏈表再up,然后對(duì)B進(jìn)行down從而阻塞這個(gè)進(jìn)程。up的實(shí)現(xiàn)：進(jìn)程同樣先對(duì)M進(jìn)行down，counter加1,若其大于0，接對(duì)M進(jìn)行up即可；否則counter小于等于0,把鏈表中一個(gè)進(jìn)程移出，然后對(duì)B、M依次up。33. 如果一個(gè)系統(tǒng)只有兩個(gè)進(jìn)程,可以使用一個(gè)屏障來(lái)同步這兩個(gè)進(jìn)程嗎？為什么？A:如果程序操作按階段執(zhí)行，直到兩個(gè)進(jìn)程都完成當(dāng)前階段才能進(jìn)入下一階段,這時(shí)就應(yīng)該使用屏障。（這個(gè)答案也有點(diǎn)奇怪,我認(rèn)為只要這兩個(gè)進(jìn)程不是生產(chǎn)者-消費(fèi)者模式就可以使用屏障。）34.

21、如果線程在內(nèi)核態(tài)實(shí)現(xiàn),可以使用內(nèi)核信號(hào)量對(duì)同一個(gè)進(jìn)程中的兩個(gè)線程進(jìn)行同步嗎？如果線程在用戶態(tài)實(shí)現(xiàn)呢？假設(shè)在其他進(jìn)程中沒有線程必須訪問該信號(hào)量。請(qǐng)解釋你的答案。A:對(duì)于內(nèi)核線程，線程可以在信號(hào)量上阻塞，而內(nèi)核可以運(yùn)行該進(jìn)程中的其它線程。而，使用信號(hào)量沒有問題。而對(duì)于用戶級(jí)線程，當(dāng)某個(gè)線程在信號(hào)此，在用戶量上阻塞時(shí)，內(nèi)核將認(rèn)為整個(gè)進(jìn)程都被阻塞，而且不再執(zhí)行它。態(tài)線程的同步失敗。35. 管程內(nèi)的同步機(jī)制使用條件變和兩個(gè)特殊操作wait和signal。一種更通用的同步形式是只用一條原語(yǔ)waituntil，它以任意的布爾謂詞作為參數(shù)。例waituntilx<0ory+z<n這樣就不再需要si

22、gnal原語(yǔ)。很顯然這種方法比Hoare或BrinchHansen方案更通用，但它從未被采用過(guò)。為什么？（提示:請(qǐng)考慮其實(shí)現(xiàn)。）A：其實(shí)現(xiàn)的代價(jià)很高。每次在某些等待變化的進(jìn)程的謂詞中出現(xiàn)的任何變量,runtime系統(tǒng)都必須重新計(jì)算該謂詞，以判斷該進(jìn)程是否能夠被解鎖。而對(duì)于Hoare和BrinchHansen管程，則只需signal原語(yǔ)即可喚醒進(jìn)程。36. 一個(gè)快餐店有四類雇員：（1）領(lǐng)班，接收頓客點(diǎn)的菜單；（2）廚師，準(zhǔn)備飯菜；（3）打包工，將飯菜裝在袋子里；（4）收銀員，將食品袋交給顧客并收錢。每個(gè)雇員可被看作一個(gè)進(jìn)行通信的順序進(jìn)程。它們采用的進(jìn)程間通信方式是什么？請(qǐng)將這個(gè)模型與UNIX中進(jìn)

23、程聯(lián)系起來(lái)。s0099UQMS«fsisssssiclsswzlss.mrfrX!Nnw。皆R%¥昔富健frw-SMBSS3NS.<siH-OssEg*()u«rteEp«rto>vrpuouQsHe-<sswiaswm。豪wrCNe皚痛CM事ogf£ml-lswiffifiESSW.§0、G01-1A：3個(gè)。40Round-robin調(diào)度算法一般需要維護(hù)一個(gè)繼續(xù)進(jìn)程列表，每個(gè)進(jìn)程在列表中只出現(xiàn)一次。如果某個(gè)進(jìn)程在列表中出現(xiàn)兩次會(huì)發(fā)生什么情況？什么情況下可以允許多次出現(xiàn)？A:如果一個(gè)進(jìn)程多次岀現(xiàn)在列表中，在每個(gè)周期，

24、它將得到多個(gè)時(shí)間片。這種方法可以用來(lái)為更重要的進(jìn)程提供更大的CPU份額。但是，當(dāng)進(jìn)程阻塞時(shí)，所有條目最好從可運(yùn)行進(jìn)程列表中刪除。41是否可以通過(guò)分析源代碼來(lái)確定進(jìn)程是CPU密集型的還是I/O密集型的？運(yùn)行時(shí)如何確定？單的情況下是有可能通過(guò)看源代碼來(lái)判斷是否為I/O綁定的。例如，程序開始時(shí)，將其所有輸入文件讀入到緩沖器中，這種程序通常不是I/O綁定的；但是，對(duì)不同文件進(jìn)行增量地讀寫（諸如編譯程序）的問題很有可能是I/O綁定的。如果操作系統(tǒng)提供諸如UNIXps的命令，就可以得知被程序使用的CPU時(shí)間的，你能把這個(gè)時(shí)間量與整個(gè)的時(shí)間比較以判斷。當(dāng)然，這在你是系統(tǒng)中唯一的用戶時(shí)最有意義。42請(qǐng)說(shuō)明在R

25、ound-robin調(diào)度算法中時(shí)間片長(zhǎng)度和上下文切換時(shí)間時(shí)怎樣相互影響的。A:如果上下文切換時(shí)間較大，則時(shí)間時(shí)間片必須成比例大。否則，上下文切換的開銷可能相當(dāng)高。如果典型的CPU突發(fā)時(shí)間小于時(shí)間片，則選擇大的時(shí)間片會(huì)導(dǎo)致系統(tǒng)效率低下。如果上下文切換非常小或是可以忽略的，那么可以用更多的自由選擇時(shí)間片。43對(duì)某系統(tǒng)進(jìn)行監(jiān)測(cè)后發(fā)現(xiàn)，在阻塞I/O之前，平均每個(gè)進(jìn)程運(yùn)行時(shí)間為T。一次進(jìn)程切換需要的時(shí)間為S,這里S實(shí)際上就是幵銷。對(duì)于采用時(shí)間片長(zhǎng)度為Q的輪轉(zhuǎn)調(diào)度，請(qǐng)給出以下各種情況中CPU利用率的計(jì)算公式:(a) Q=8(b) Q>T(c) S<Q<T(d) Q=S(e) Q趨近于0A

26、:(a)T/(T+S);(b)T/(T+S);(c)Q/(Q+S);(d)1/2；(e)>0;44有5個(gè)待運(yùn)行作業(yè)，估計(jì)它們的運(yùn)行時(shí)N分別是9,6,3,5和X。采用哪種次序運(yùn)行這些作業(yè)將得到最短的平均響應(yīng)時(shí)間？（答案將依賴于X）A：最短作業(yè)優(yōu)先可以使得平均響應(yīng)時(shí)間最短。0<XM3:X,3,5,6,9.3<XM5:3,X,5,6,9.5<XM6:3,5,X,6,9.6<XM9:3,5,6,X,9.X>9:3,5,6,9,X.ss(p)ls(q)issuSSSSBS$R.sn§。品我8/門901-|醫(yī))禮舉量s。MR暴牡(q)ws$«

27、1;=$(番壘番)量牡K。荼8RY901-|«|!眾&蠱egw蚩UJffi<sRSBF聚ocnEoz71-197usssttsiisN6I-I曽ssocnEcol-l.91-l.ov-l813IfcweUJAa。聚8.8V-I«aBFssocnR9ri龍.5SRies.£&s.S9M*SSSK。慕zz«aBFOE展82£0010TiIn<oss«e*s舉慕a嚶凰&n<DsstgiBH慕8e*FS.sYss01-10放詩(shī)lul-ll-l«ssuesssee巻冷«»E

28、s«fsuess£s«e巻s風(fēng)ISECNSBStcJC&GHE8才7£sI-l.TFSSKS&eHssmt.san«3ln£rMW3&ss5osulsI-lRsulok,sluoz蔚Eok«=DR&£JMfASA-<laesksimitxsKS»ST3.§.SSBss&sV3S3甘著SMKitsss閱i£s弐營(yíng)£»£Es:s»ss,SBSiv-<A:(40V2+2E2)1、2+4ql、2n25msmo.lxwsstt933、sss50ms、looms200ms蓉250my435ms、20ms、10ms昌xmssCPUA-35、50+20、100+10、200g2502HHVX22.5Dr1msCPUa畫、sk25184-fss20ms8CPUa畫。ssssfi7A:l、6+25£5000"2、3A、WW.843、WKisissaasin-SSIA:內(nèi)核可以通過(guò)任何方式調(diào)度進(jìn)程，但對(duì)于每個(gè)進(jìn)程，嚴(yán)格按照進(jìn)程的優(yōu)先級(jí)順序執(zhí)行。通過(guò)讓用戶進(jìn)程設(shè)置自己的優(yōu)先級(jí)，讓用戶控制策略，而內(nèi)核處理機(jī)制。54.在哲學(xué)家就餐問題的解法（圖