《操作系統(tǒng)精髓與設(shè)計(jì)原理·第五版》練習(xí)題及答案(2)

《《操作系統(tǒng)精髓與設(shè)計(jì)原理·第五版》練習(xí)題及答案(2)》由會員分享，可在線閱讀，更多相關(guān)《《操作系統(tǒng)精髓與設(shè)計(jì)原理·第五版》練習(xí)題及答案(2)（116頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第1章 計(jì)算機(jī)系統(tǒng)概述 1.1、圖1.3中的抱負(fù)機(jī)器尚有兩條I/O指令： 0011 = 從I/O中載入AC 0111 = 把AC保存到I/O中 在這種狀況下，12位地址標(biāo)記一種特殊的外部設(shè)備。請給出如下程序的執(zhí)行過程（按照圖1.4的格式）： 1. 從設(shè)備5中載入AC。 2. 加上存儲器單元940的內(nèi)容。 3. 把AC保存到設(shè)備6中。 假設(shè)從設(shè)備5中取到的下一種值為3940單元中的值為2。 答案：存儲器（16進(jìn)制內(nèi)容）：300：3005；301：5940；302：7006 環(huán)節(jié)1：3005－>IR；環(huán)節(jié)2：3－>AC

2、 環(huán)節(jié)3：5940－>IR；環(huán)節(jié)4：3＋2＝5－>AC 環(huán)節(jié)5：7006－>IR：環(huán)節(jié)6：AC－>設(shè)備 6 1.2、本章中用6步來描述圖1.4中的程序執(zhí)行狀況，請使用MAR和MBR擴(kuò)大這個(gè)描述。 答案：1. a. PC中涉及第一條指令的地址300，該指令的內(nèi)容被送入MAR中。 b. 地址為300的指令的內(nèi)容（值為十六進(jìn)制數(shù)1940）被送入MBR，并且PC增1。這兩個(gè)環(huán)節(jié)是并行完畢的。 c. MBR中的值被送入指令寄存器IR中。 2. a. 指令寄存器IR中的地址部分（940）被送入MAR中。 b.

3、地址940中的值被送入MBR中。 c. MBR中的值被送入AC中。 3. a. PC中的值（301）被送入MAR中。 b. 地址為301的指令的內(nèi)容（值為十六進(jìn)制數(shù)5941）被送入MBR，并且PC增1。 c. MBR中的值被送入指令寄存器IR中。 4. a. 指令寄存器IR中的地址部分（941）被送入MAR中。 b. 地址941中的值被送入MBR中。 c. AC中此前的內(nèi)容和地址為941的存儲單元中的內(nèi)容相加，成果保存到AC中。 5. a. PC中的值（302）被

4、送入MAR中。 b. 地址為302的指令的內(nèi)容（值為十六進(jìn)制數(shù)2941）被送入MBR，并且PC增1。 c. MBR中的值被送入指令寄存器IR中。 6. a. 指令寄存器IR中的地址部分（941）被送入MAR中。 b. AC中的值被送入MBR中。 c. MBR中的值被存儲到地址為941的存儲單元之中。 1.4、假設(shè)有一種微解決器產(chǎn)生一種16位的地址（例如，假設(shè)程序計(jì)數(shù)器和地址寄存器都是16位）并且具有一種16位的數(shù)據(jù)總線。 a.如果連接到一種16位存儲器上，解決器可以直接訪問的最大存儲器地址空間為多少？

5、b.如果連接到一種8位存儲器上，解決器可以直接訪問的最大存儲器地址空間為多少？ c.解決訪問一種獨(dú)立的I/O空間需要哪些構(gòu)造特性？ d.如果輸入指令和輸出指令可以表達(dá)8位I/O端標(biāo)語，這個(gè)微解決器可以支持多少8位I/O端口？ 答案：對于(a)和(b)兩種狀況，微解決器可以直接訪問的最大存儲器地址空間為216 = 64K bytes；唯一的區(qū)別是8位存儲器每次訪問傳播1個(gè)字節(jié)，而16位存儲器每次訪問可以傳播一種字節(jié)或者一種16位的字。對于(c)狀況，特殊的輸入和輸出指令是必要的，這些指令的執(zhí)行體會產(chǎn)生特殊的“I/O信號”（有別于“存儲器信號”，這些信號由存儲器類型指令的執(zhí)行體產(chǎn)生）；在最小

6、狀態(tài)下，一種附加的輸出針腳將用來傳播新的信號。對于(d)狀況，它支持28 = 256個(gè)輸入和28 = 256個(gè)輸出字節(jié)端口和相似數(shù)目的16位I/O端口；在任一狀況, 一種輸入和一種輸出端口之間的區(qū)別是通過被執(zhí)行的輸入輸出指令所產(chǎn)生的不同信號來定義的。 1.5、考慮一種32位微解決器，它有一種16位外部數(shù)據(jù)總線，并由一種8MHz的輸入時(shí)鐘驅(qū)動。假設(shè)這個(gè)微解決器有一種總線周期，其最大持續(xù)時(shí)間等于4個(gè)輸入時(shí)鐘周期。請問該微解決器可以支持的最大數(shù)據(jù)傳送速度為多少？外部數(shù)據(jù)總線增長到21位，或者外部時(shí)鐘頻率加倍，哪種措施可以更好地提高解決器性能？請論述你的設(shè)想并解釋因素。 答案：時(shí)鐘周期＝1/（8M

7、HZ）＝125ns 總線周期＝4×125ns＝500ns 每500ns傳播2比特；因此傳播速度＝4MB/s 加倍頻率也許意味著采用了新的芯片制造技術(shù)（假設(shè)每個(gè)指令均有相似的時(shí)鐘周期數(shù)）；加倍外部數(shù)據(jù)總線，在芯片數(shù)據(jù)總線驅(qū)動/鎖存、總線控制邏輯的修改等方面手段廣泛（或許更新）。在第一種方案中，內(nèi)存芯片的速度要提高一倍（大概），而不能減少微解決器的速度；第二種方案中，內(nèi)存的字長必須加倍，以便能發(fā)送/接受32位數(shù)量。 1.6、考慮一種計(jì)算機(jī)系統(tǒng)，它涉及一種I/O模塊，用以控制一臺簡樸的鍵盤/打印機(jī)電傳打字設(shè)備。CPU中涉及下列寄存器，這些寄存器直接連接到系統(tǒng)總線上： INPR：輸入寄存器，

8、8位 OUTR：輸出寄存器，8位 FGI：輸入標(biāo)記，1位 FGO：輸出標(biāo)記，1位 IEN：中斷容許，1位 I/O模塊控制從打字機(jī)中輸入擊鍵，并輸出到打印機(jī)中去。打字機(jī)可以把一種字母數(shù)字符號編碼成一種8位字，也可以把一種8位字解碼成一種字母數(shù)字符號。當(dāng)8位字從打字機(jī)進(jìn)入輸入寄存器時(shí)，輸入標(biāo)記被置位；當(dāng)打印一種字時(shí)，輸出標(biāo)記被置位。 a. 描述CPU如何使用這4個(gè)寄存器實(shí)現(xiàn)與打字機(jī)間的輸入/輸出。 b. 描述通過使用IEN，如何提高執(zhí)行效率？ 答案：a.來源于打字機(jī)的輸入儲存在INPR中。只有當(dāng)FGI＝0時(shí)，INPR才會接受來自打字機(jī)的數(shù)據(jù)。當(dāng)數(shù)據(jù)接受后，被儲存在INPR里面，同步

9、FGI置為1。CPU定期檢查FGI。如果FGI＝1，CPU將把INPR里面的內(nèi)容傳送至AC，并把FGI置為0。 當(dāng)CPU需要傳送數(shù)據(jù)到打字機(jī)時(shí)，它會檢查FGO。如果FGO＝0，CPU處在等待。如果FGO＝1，CPU將把AC的內(nèi)容傳送至OUTER并把FGO置為0。當(dāng)數(shù)字符號打印后，打字機(jī)將把FGI置為1。 b.（A）描述的過程非常揮霍。速度遠(yuǎn)高于打字機(jī)的CPU必須反復(fù)不斷的檢查FGI和FGO。如果中斷被使用，當(dāng)打字機(jī)準(zhǔn)備接受或者發(fā)送數(shù)據(jù)時(shí)，可以向CPU發(fā)出一種中斷祈求。IEN計(jì)數(shù)器可以由CPU設(shè)立（在程序員的控制下）。 1.7、事實(shí)上在所有涉及DMA模塊的系

10、統(tǒng)中，DMA訪問主存儲器的優(yōu)先級總是高于解決器訪問主存儲器的優(yōu)先級。這是為什么? 答案：如果一種解決器在嘗試著讀或者寫存儲器時(shí)被掛起, 一般除了一點(diǎn)輕微的時(shí)間損耗之外沒有任何危害。但是，DMA也許從或者向設(shè)備(例如磁盤或磁帶)以數(shù)據(jù)流的方式接受或者傳播數(shù)據(jù)并且這是不能被打斷的。否則，如果DMA設(shè)備被掛起（回絕繼續(xù)訪問主存），數(shù)據(jù)也許會丟失。 1.9、一臺計(jì)算機(jī)涉及一種CPU和一臺I/O設(shè)備D，通過一條共享總線連接到主存儲器M，數(shù)據(jù)總線的寬度為1個(gè)字。CPU每秒最多可執(zhí)行106條指令，平均每條指令需要5個(gè)機(jī)器周期，其中3個(gè)周期需要使用存儲器總線。存儲器讀/寫操作使用1個(gè)機(jī)器周期。假設(shè)CPU正

11、在持續(xù)不斷地執(zhí)行后臺程序，并且需要保證95%的指令執(zhí)行速度，但沒有任何I/O指令。假設(shè)1個(gè)解決器周期等于1個(gè)總線周期，目前要在M和D之間傳送大塊數(shù)據(jù)。 a.若使用程序控制I/O，I/O每傳送1個(gè)字需要CPU執(zhí)行兩條指令。請估計(jì)通過D的I/O數(shù)據(jù)傳送的最大也許速度。 b.如果使用DMA傳送，請估計(jì)傳送速度。 答案：a.解決器只能分派5％的時(shí)間給I/O.因此最大的I/O指令傳送速度是10e6×0.05＝50000條指令/秒。因此I/O的傳送速率是25000字/秒。 b.使用DMA控制時(shí)，可用的機(jī)器周期下的數(shù)量是 10e6（0.05×5＋0.95×2）＝2.15×10e6

12、 如果我們假設(shè)DMA模塊可以使用所有這些周期，并且忽視任何設(shè)立和狀態(tài)檢查時(shí)間，那么這個(gè)值就是最大的I/O傳播速率。 1.10、考慮如下代碼： for ( i = 0；i < 20；i++) for (j = 0；j < 10；j++) a[i] = a[i]*j a. 請舉例闡明代碼中的空間局部性。 b. 請舉例闡明代碼中的時(shí)間局部性。 答案：a.讀取第二條指令是緊跟著讀取第一條指令的。 b.在很短的間歇時(shí)間內(nèi)， a[i]在循環(huán)內(nèi)部被訪問了十次。 1.11、請將附錄1A中的式（1.1）和式（1.2）推廣到n

13、級存儲器層次中。 答案：定義： Ci = 存儲器層次i上每一位的存儲單元平均花銷 Si = 存儲器層次i的規(guī)模大小 Ti = 存儲器層次i上訪問一種字所需時(shí)間 Hi = 一種字在不高于層次i的存儲器上的概率 Bi = 把一種數(shù)據(jù)塊從層次i+1的存儲器上傳播到層次i的存儲器上所需時(shí)間 高速緩沖存儲器作為是存儲器層次1；主存為存儲器層次2；針對所有的N層存儲器層以此類推。有： Ts的引用更復(fù)雜，我們從概率論入手：所盼望的值，由此我們可以寫出： 我們需要清晰如果一種字在M1（緩存）中，那么對它的

14、讀取非?？?。如果這個(gè)字在M2而不在M1中，那么數(shù)據(jù)塊需要從M2傳播到M1中，然后才干讀取。因此，T2 = B1+T1 進(jìn)一步，T3 = B2+T2 = B1+B2+T1 以此類推： 因此， 但是， 最后， 1.12、考慮一種存儲器系統(tǒng)，它具有如下參數(shù)： Tc = 100 ns Cc = 0.01 分/位 Tm = 1200 ns Cm = 0.001 分/位 a.1MB的主存儲器價(jià)格為多少？ b.使用高速緩沖存儲器技術(shù)，1MB的主存儲器價(jià)格為多少？ c.如果有效存取時(shí)間比高速緩沖存儲器存取時(shí)間

15、多10% ，命中率H為多少？ 答案：a.價(jià)格 = Cm×8×106 = 8×103 ￠ = ＄80 b.價(jià)格 = Cc×8×106 = 8×104 ￠ = ＄800 c.由等式1.1知：1.1×T1 = T1+(1-H)T2 (0.1)(100) = (1-H)(1200) H=1190/1200 1.13、一臺計(jì)算機(jī)涉及涉及高速緩沖存儲器、主存儲器和一種用做虛擬存儲器的磁盤。如果要存取的字在高速緩沖存儲器中，存取它需要20ns；如果該字在主存儲器中而不在高速

16、緩沖存儲器中，把它載入高速緩沖存儲器需要60ns（涉及最初檢查高速緩沖存儲器的時(shí)間），然后再重新開始存?。蝗绻撟植辉谥鞔鎯ζ髦?，從磁盤中取到內(nèi)存需要12ms，接著復(fù)制到高速緩沖存儲器中還需要60ns，再重新開始存取。高速緩沖存儲器的命中率為0.9，主存儲器的命中率為0.6，則該系統(tǒng)中存取一種字的平均存取時(shí)間是多少（單位為ns）？ 答案：有三種狀況需要考慮： 字所在的位置 概率 訪問所需時(shí)間（ns） 在緩存中 0.9 20 不在緩存，在主存中 （0.1）（0.6）= 0.06 60+20 = 80 不在緩存也不在主存中 （0.1）（0.4）= 0.04 12ms+60

17、+20 = 12,000,080 因此平均訪問時(shí)間是：Avg = (0.9)(20) + (0.06)(80) + (0.04)(1080) = 480026 ns 1.14、假設(shè)解決器使用一種棧來管理過程調(diào)用和返回。請問可以取消程序計(jì)數(shù)器而用棧指針替代嗎？ 答案：如果棧只用于保存返回地址?；蛘呷绻麠Ｒ灿糜趥鬟f參數(shù)，這種方案只有當(dāng)棧作為傳遞參數(shù)的控制單元而非機(jī)器指令時(shí)才成立。這兩種狀況下可以取消程序計(jì)數(shù)器而用棧指針替代。在后者狀況中，解決器同步需要一種參數(shù)和指向棧頂部的程序計(jì)數(shù)器。 第2章 操作系統(tǒng)概述 2.1假設(shè)我們有一臺多道程序的計(jì)算機(jī)，每個(gè)作業(yè)有相似的特性。在一種計(jì)算

18、周期T中，一種作業(yè)有一半時(shí)間耗費(fèi)在I/O上，另一半用于解決器的活動。每個(gè)作業(yè)一共運(yùn)營N個(gè)周期。假設(shè)使用簡樸的循環(huán)法調(diào)度，并且I/O操作可以與解決器操作重疊。定義如下量： ?時(shí)間周期=完畢任務(wù)的實(shí)際時(shí)間 ?吞吐量=每個(gè)時(shí)間周期T內(nèi)平均完畢的作業(yè)數(shù)目 ?解決器使用率=解決器活躍（不是處在等待）的時(shí)間的比例 當(dāng)周期T分別按下列方式分布時(shí)，對1個(gè)、2個(gè)和4個(gè)同步發(fā)生的作業(yè)，請計(jì)算這些量： a. 前一般用于I/O，后一半用于解決器。 b. 前四分之一和后四分之一用于I/O，中間部分用于解決器。 答：（a）和（b）的答案相似。盡管解決器活動不能重疊，但I(xiàn)/O操作能。

19、 一種作業(yè) 時(shí)間周期=NT 解決器運(yùn)用率=50﹪ 兩個(gè)作業(yè) 時(shí)間周期=NT 解決器運(yùn)用率=100﹪ 四個(gè)作業(yè) 時(shí)間周期=（2N-1）NT 解決器運(yùn)用率=100﹪ 2.2 I/O限制的程序是指如果單獨(dú)運(yùn)營，則耗費(fèi)在等待I/O上的時(shí)間比使用解決器的時(shí)間要多的程序。解決器限制的程序則相反。假設(shè)短期調(diào)度算法偏愛那些在近期石油解決器時(shí)間較少的算法，請解釋為什么這個(gè)算法偏愛I/O限制的程序，但是并不是永遠(yuǎn)不受理解決器限制程序所需的解決器時(shí)間？ 受I/O限制的

20、程序使用相對較少的解決器時(shí)間，因此更受算法的青睞。然而，受解決器限制的進(jìn)程如果在足夠長的時(shí)間內(nèi)得不到解決器時(shí)間，同一算法將容許解決器去解決此進(jìn)程，由于它近來沒有使用過解決器。這樣，一種解決器限制的進(jìn)程不會永遠(yuǎn)得不到解決器。 2.3請對優(yōu)化分時(shí)系統(tǒng)的調(diào)度方略和用于優(yōu)化多道程序批解決系統(tǒng)的調(diào)度方略進(jìn)行比較。 分時(shí)系統(tǒng)關(guān)注的是輪轉(zhuǎn)時(shí)間，時(shí)間限制方略更有效是由于它給所有進(jìn)程一種較短的解決時(shí)間。批解決系統(tǒng)關(guān)懷的是吞吐量，更少的上下文轉(zhuǎn)換和更多的進(jìn)程解決時(shí)間。因此，最小的上下文轉(zhuǎn)換最高效。 2.4系統(tǒng)調(diào)用的目的是什么?如何實(shí)現(xiàn)與操作系統(tǒng)有關(guān)的的系統(tǒng)調(diào)用以及與雙重模式（內(nèi)核模式和顧客模式）操作有關(guān)的系

21、統(tǒng)調(diào)用？ 系統(tǒng)調(diào)用被應(yīng)用程序用來調(diào)用一種由操作系統(tǒng)提供的函數(shù)。一般狀況下，系統(tǒng)調(diào)用最后轉(zhuǎn)換成在內(nèi)核模式下的系統(tǒng)程序。 2.5在IBM的主機(jī)操作系統(tǒng)OS/390中，內(nèi)核中的一種重要模塊是系統(tǒng)資源管理程序（System Resource Manager,SRM），她負(fù)責(zé)地址空間（進(jìn)程）之間的資源分派。SRM是的OS/390在操作系統(tǒng)中具有特殊性，沒有任何其她的主機(jī)操作系統(tǒng)，固然沒有任何其她類型的操作系統(tǒng)可以比得上SRM所實(shí)現(xiàn)的功能。資源的概念涉及解決器、實(shí)存和I/O通道，SRM合計(jì)解決器、I/O通道和多種重要數(shù)據(jù)構(gòu)造的運(yùn)用率，它的目的是基于性能監(jiān)視和分析提供最優(yōu)的性能，其安裝設(shè)立了后來的多種性

22、能目的作為SRM的指南，這會基于系統(tǒng)的運(yùn)用率動態(tài)的修改安裝和作業(yè)性能特點(diǎn)。SRM依次提供報(bào)告，容許受過訓(xùn)練的操作員改善配備和參數(shù)設(shè)立，以改善顧客服務(wù)。 目前關(guān)注SRM活動的一種實(shí)例。實(shí)存被劃分為成千上萬個(gè)大小相等的塊，稱為幀。每個(gè)幀可以保存一塊稱為頁的虛存。SRM每秒大概接受20次控制，并在互相之間以及每個(gè)頁面之間進(jìn)行檢查。如果頁未被引用或被變化，計(jì)數(shù)器增1。一段時(shí)間后，SRM求這些數(shù)據(jù)的平均值，以擬定系統(tǒng)中一種頁面未曾被觸及的平均秒數(shù)。這樣做的目的是什么？SRM將采用什么動作？ 操作系統(tǒng)可以查看這些數(shù)據(jù)已擬定系統(tǒng)的負(fù)荷，通過減少加在系統(tǒng)上的活躍作業(yè)來保持較高的平均運(yùn)用率。典型的平均時(shí)間應(yīng)

23、當(dāng)是兩分鐘以上，這個(gè)平均時(shí)間看起來很長，其實(shí)并不長。 第3章 進(jìn)程描述和控制 3.1. 給出操作系統(tǒng)進(jìn)行進(jìn)程管理時(shí)的五種重要活動，并簡樸描述為什么需要它們。 答：顧客進(jìn)程和系統(tǒng)進(jìn)程創(chuàng)立及刪除。系統(tǒng)中的進(jìn)程可覺得信息共享、運(yùn)算加速、模塊化和以便并發(fā)地執(zhí)行。而并發(fā)執(zhí)行需要進(jìn)程的創(chuàng)立和刪除機(jī)制。當(dāng)進(jìn)程創(chuàng)立或者運(yùn)營時(shí)分派給它需要的資源。當(dāng)進(jìn)程終結(jié)時(shí)，操作系統(tǒng)需要收回任何可以重新運(yùn)用的資源。 進(jìn)程的暫停和繼續(xù)執(zhí)行。在進(jìn)程調(diào)度中，當(dāng)進(jìn)程在等待某些資源時(shí)，操作系統(tǒng)需要將它的狀態(tài)變化為等待或就緒狀態(tài)。當(dāng)所需要的資源可用時(shí)，操作系統(tǒng)需要將它的狀態(tài)變?yōu)檫\(yùn)營態(tài)以使其繼續(xù)執(zhí)行。 提供進(jìn)程的同步機(jī)制。合伙的進(jìn)

24、程也許需要共享數(shù)據(jù)。對共享數(shù)據(jù)的并行訪問也許會導(dǎo)致數(shù)據(jù)沖突。操作系統(tǒng)必須提供進(jìn)程的同步機(jī)制以使合伙進(jìn)程有序地執(zhí)行，從而保證數(shù)據(jù)的一致性。 提供進(jìn)程的通信機(jī)制。操作系統(tǒng)下執(zhí)行的進(jìn)程既可以是獨(dú)立進(jìn)程也可以是合伙進(jìn)程。合伙進(jìn)程之間必須具有一定的方式進(jìn)行通信。 提供進(jìn)程的死鎖解決機(jī)制。在多道程序環(huán)境中，多種進(jìn)程也許會競爭有限的資源。如果發(fā)生死鎖，所有的等待進(jìn)程都將永遠(yuǎn)不能由等待狀態(tài)再變?yōu)檫\(yùn)營態(tài)，資源將被揮霍，工作永遠(yuǎn)不能完畢。 3.2. 在[PINK89] 中為進(jìn)程定義了如下狀態(tài)：執(zhí)行（運(yùn)營）態(tài)、活躍（就緒）態(tài)、阻塞態(tài)和掛起態(tài)。當(dāng)進(jìn)程正在等待容許使用某一資源時(shí)，它處在阻塞態(tài)；當(dāng)進(jìn)程正在等待它已經(jīng)

25、獲得的某種資源上的操作完畢時(shí)，它處在掛起態(tài)。在許多操作系統(tǒng)中，這兩種狀態(tài)常常放在一起作為阻塞態(tài)，掛起態(tài)使用本章中給出的定義。請比較這兩組定義的長處。 答：[PINK89]中引用了如下例子來論述其中阻塞和掛起的定義： 假設(shè)一種進(jìn)程已經(jīng)執(zhí)行了一段時(shí)間，它需要一種額外的磁帶設(shè)備來寫出一種臨時(shí)文獻(xiàn)。在它開始寫磁帶之前，進(jìn)程必須得到使用某一設(shè)備的許可。當(dāng)它做出祈求時(shí)，磁帶設(shè)備也許并不可用，這種狀況下，該進(jìn)程就處在阻塞態(tài)。假設(shè)操作系統(tǒng)在某一時(shí)刻將磁帶設(shè)備分派給了該進(jìn)程，這時(shí)進(jìn)程就重新變?yōu)榛钴S態(tài)。當(dāng)進(jìn)程重新變?yōu)閳?zhí)行態(tài)時(shí)要對新獲得的磁帶設(shè)備進(jìn)行寫操作。這時(shí)進(jìn)程變?yōu)閽炱饝B(tài)，等待該磁帶上目前所進(jìn)行的寫操作完畢

26、。 這種對等待某一設(shè)備的兩種不同因素的區(qū)別，在操作系統(tǒng)組織其工作時(shí)是非常有用的。然而這并不能表白那些進(jìn)程是換入的，那些進(jìn)程是換出的。后一種區(qū)別是必需的，并且應(yīng)當(dāng)在進(jìn)程狀態(tài)中以某種形式體現(xiàn)出來。 3.3. 對于圖3.9（b）中給出的7狀態(tài)進(jìn)程模型，請仿照圖3.8（b）畫出它的排隊(duì)圖。 答：圖9.3給出了單個(gè)阻塞隊(duì)列的成果。該圖可以很容易的推廣到多種阻塞隊(duì)列的情形。 3.4. 考慮圖3.9（b）中的狀態(tài)轉(zhuǎn)換圖。假設(shè)操作系統(tǒng)正在分派進(jìn)程，有進(jìn)程處在就緒態(tài)和就緒/掛起態(tài)，并且至少有一種處在就緒/掛起態(tài)的進(jìn)程比處在就緒態(tài)的所有進(jìn)程的優(yōu)先級都高。有兩種極端的方略：（1）總是分派一種處在就緒態(tài)的進(jìn)程

27、，以減少互換；（2）總是把機(jī)會給具有最高優(yōu)先級的進(jìn)程，雖然會導(dǎo)致在不需要互換時(shí)進(jìn)行互換。請給出一種能均衡考慮優(yōu)先級和性能的中間方略。 答：對于一種就緒/掛起態(tài)的進(jìn)程，減少一定數(shù)量（如一或兩個(gè)）優(yōu)先級，從而保證只有當(dāng)一種就緒/掛起態(tài)的進(jìn)程比就緒態(tài)的進(jìn)程的最高優(yōu)先級還高出幾種優(yōu)先級時(shí)，它才會被選做下一種執(zhí)行。 3.5. 表3.13給出了VAX/VMS操作系統(tǒng)的進(jìn)程狀態(tài)。 a. 請給出這樣多種等待狀態(tài)的理由。 b. 為什么如下狀態(tài)沒有駐留和換出方案：頁錯(cuò)誤等待、也沖突等待、公共事件等待、自由頁等待和資源等待。 c. 請畫出狀態(tài)轉(zhuǎn)換圖，并指出引起狀態(tài)裝換的因素。 答： a. 每一種等待狀

28、態(tài)均有一種單獨(dú)的隊(duì)列與其有關(guān)聯(lián)。當(dāng)影響某一等待進(jìn)程的事件發(fā)生時(shí)，把等待進(jìn)程提成不同的隊(duì)列就減少了定位這一等待進(jìn)程所需的工作量。例如，當(dāng)一種頁錯(cuò)誤完畢時(shí)，調(diào)度程序就可以在頁錯(cuò)誤等待隊(duì)列中找到等待的進(jìn)程。 b. 在這些狀態(tài)下，容許進(jìn)程被換出只會使效率更低。例如，當(dāng)發(fā)生頁錯(cuò)誤等待時(shí)，進(jìn)程正在等待換入一種頁從而使其可以執(zhí)行，這是將進(jìn)程換出是毫無意義的。 c. 可以由下面的進(jìn)程狀態(tài)轉(zhuǎn)換表得到狀態(tài)轉(zhuǎn)換圖。 目前狀態(tài) 下一狀態(tài) 目前正在執(zhí)行 可計(jì)算（駐留） 可計(jì)算（換出） 多種等待狀態(tài)（駐留） 多種等待狀態(tài)（換出） 目前正在執(zhí)行 重調(diào)度 等待 可計(jì)算

29、（駐留） 調(diào)度 換出 可計(jì)算（換出） 換入 多種等待狀態(tài)（駐留） 事件發(fā)生 換出 多種等待狀態(tài)（換出） 事件發(fā)生 3.6. VAM/VMS操作系統(tǒng)采用了四種解決器訪問模式，以增進(jìn)系統(tǒng)資源在進(jìn)程間的保護(hù)和共享。訪問模式擬定： l 指令執(zhí)行特權(quán)：解決器將執(zhí)行什么指令。 l 內(nèi)存訪問特權(quán)：目前指令也許訪問虛擬內(nèi)存中的哪個(gè)單元。 四種模式如下： l 內(nèi)核模式：執(zhí)行VMS操作系統(tǒng)的內(nèi)核，涉及內(nèi)存管理、中斷解決和I/O操作。 l 執(zhí)行模式：執(zhí)行許多操作系統(tǒng)服務(wù)調(diào)用，涉及文獻(xiàn)（磁盤和磁帶）和記錄管理例程。 l 管理模式：

30、執(zhí)行其她操作系統(tǒng)服務(wù)，如響應(yīng)顧客命令。 l 顧客模式：執(zhí)行顧客程序和諸如編譯器、編輯器、鏈接程序、調(diào)試器之類的實(shí)用程序。 在較少特權(quán)模式執(zhí)行的進(jìn)程一般需要調(diào)用在較多特權(quán)模式下執(zhí)行的過程，例如，一種顧客程序需要一種操作系統(tǒng)服務(wù)。這個(gè)調(diào)用通過使用一種變化模式（簡稱CHM）指令來實(shí)現(xiàn)，該指令將引起一種中斷，把控制轉(zhuǎn)交給處在新的訪問模式下的例程，并通過執(zhí)行REI（Return from Exception or Interrupt，從異?；蛑袛喾祷兀┲噶罘祷亍? a. 諸多操作系統(tǒng)有兩種模式，內(nèi)核和顧客，那么提供四種模式有什么長處和缺陷？ b. 你可以舉出一種有四種以上模式的狀況嗎？ 答：

31、a. 四種模式的長處是對主存的訪問控制更加靈活，可覺得主存提供更好的保護(hù)。缺陷是復(fù)雜和解決的開銷過大。例如，程序在每一種執(zhí)行模式下都要有一種獨(dú)立的堆棧。 b. 原則上，模式越多越靈活，但是四種以上的模式似乎很難實(shí)現(xiàn)。 3.7. 在前面習(xí)題中討論的VMS方案常常稱為環(huán)狀保護(hù)構(gòu)造，如圖3.18所示。3.3節(jié)所描述的簡樸的內(nèi)核/顧客方案是一種兩環(huán)構(gòu)造，[SILB04]指出了這種措施的問題：環(huán)狀（層次）構(gòu)造的重要缺陷是它不容許我們實(shí)行須知原理，特別地，如果一種對象必須在域Dj中可訪問，但在域Di中不可訪問，則必須有就j

32、面引文中提出的問題。 b. 請給出環(huán)狀構(gòu)造操作系統(tǒng)解決這個(gè)問題的一種措施。 答： a. 當(dāng)j

33、 在這種狀況下，如何修改圖中的排隊(duì)構(gòu)造以支持這個(gè)新特點(diǎn)？ 答： a. 一種進(jìn)程也許正在解決從另一種進(jìn)程收到的數(shù)據(jù)并將成果保存到磁盤上。如果目前在另一種進(jìn)程中正有數(shù)據(jù)在等待被取走，進(jìn)程就可以繼續(xù)獲得數(shù)據(jù)并解決它。如果前一種寫磁盤操作已經(jīng)完畢，并且有解決好的數(shù)據(jù)在等待寫出，那么進(jìn)程就可以繼續(xù)寫磁盤。這樣就也許存在某一時(shí)刻，進(jìn)程即在等待從輸入進(jìn)程獲得數(shù)據(jù)，又在等待磁盤可用。 b. 有諸多種措施解決這一問題?？梢允褂靡环N特殊的隊(duì)列，或者將進(jìn)程放入兩個(gè)獨(dú)立的隊(duì)列中。不管采用哪種措施，操作系統(tǒng)都必須解決好細(xì)節(jié)工作，使進(jìn)程相繼地關(guān)注兩個(gè)事件的發(fā)生。 3.9. 在諸多初期計(jì)算機(jī)中，中斷導(dǎo)致寄存器值被保

34、存在與給定的中斷信息有關(guān)聯(lián)的固定單元。在什么狀況下這是一種實(shí)用的技術(shù)？請解釋為什么它一般是不以便的。 答：這種技術(shù)是基于被中斷的進(jìn)程A在中斷響應(yīng)之后繼續(xù)執(zhí)行的假設(shè)的。但是，在一般狀況下，中斷也許會導(dǎo)致另一種進(jìn)程B搶占了進(jìn)程A。這是就必須將進(jìn)程A的執(zhí)行狀態(tài)從與中斷有關(guān)的位置復(fù)制到與A有關(guān)的進(jìn)程描述中。然而機(jī)器卻有也許仍將它們保存到前一位置。參照：[BRIN73]。 3.10. 3.4節(jié)曾經(jīng)講述過，由于在內(nèi)核模式下執(zhí)行的進(jìn)程是不能被搶占的，因此UNIX不合用于實(shí)時(shí)應(yīng)用。請論述因素。 答：由于存在進(jìn)程不能被搶占的狀況（如在內(nèi)核模式下執(zhí)行的進(jìn)程），操作系統(tǒng)不也許對實(shí)時(shí)需求予以迅速的反映。

35、第4章 線程、對稱多解決和微內(nèi)核 4.1. 一種進(jìn)程中的多種線程有如下兩個(gè)長處：（1）在一種已有進(jìn)程中創(chuàng)立一種新線程比創(chuàng)立一種新進(jìn)程所需的工作量少；（2）在同一種進(jìn)程中的線程間的通信比較簡樸。請問同一種進(jìn)程中的兩個(gè)線程間的模式切換與不同進(jìn)程中的兩個(gè)線程間的模式切換相比，所需的工作量與否要少？ 答：是的，由于兩個(gè)進(jìn)程間的模式切換要儲存更多的狀態(tài)信息。 4.2. 在比較顧客級線程和內(nèi)核級線程時(shí)曾指出顧客級線程的一種缺陷，即當(dāng)一種顧客級線程執(zhí)行系統(tǒng)調(diào)用時(shí)，不僅這個(gè)線程被阻塞，并且進(jìn)程中的所有線程都被阻塞。請問這是為什么？ 答：由于對于顧客級線程來說，一種進(jìn)程的線程構(gòu)造對操作系統(tǒng)是不可見的，而

36、操作系統(tǒng)的調(diào)度是以進(jìn)程為單位的。 4.3. 在OS/2中，其她操作系統(tǒng)中通用的進(jìn)程概念被提成了三個(gè)獨(dú)立類型的實(shí)體：會話、進(jìn)程和線程。一種會話是一組與顧客接口（鍵盤、顯示屏、鼠標(biāo)）有關(guān)聯(lián)的一種或多種進(jìn)程。會話代表了一種交互式的顧客應(yīng)用程序，如字解決程序或電子表格，這個(gè)概念使得PC顧客可以打開一種以上的應(yīng)用程序，在屏幕上顯示一種或更多種窗口。操作系統(tǒng)必須懂得哪個(gè)窗口，即哪個(gè)會話是活躍的，從而把鍵盤和鼠標(biāo)的輸入傳遞個(gè)相應(yīng)的會話。在任何時(shí)刻，只有一種會話在前臺模式，其她的會話都在后臺模式，鍵盤和鼠標(biāo)的所有輸入都發(fā)送給前臺會話的一種進(jìn)程。當(dāng)一種會話在前臺模式時(shí)，執(zhí)行視頻輸出的進(jìn)程直接把它發(fā)送到硬件視頻

37、緩沖區(qū)。當(dāng)一種會話在后臺時(shí)，如果該會話的任何一種進(jìn)程的任何一種線程正在執(zhí)行并產(chǎn)生屏幕輸出，則這個(gè)輸出被送到邏輯視頻緩沖區(qū)；當(dāng)這個(gè)會話返回前臺時(shí)，屏幕被更新，為新的前臺會話反映出邏輯視頻緩沖區(qū)中的目前內(nèi)容。 有一種措施可以把OS/2中與進(jìn)程有關(guān)的概念的數(shù)目從3個(gè)減少到2個(gè)。刪去會話，把顧客接口（鍵盤、顯示屏、鼠標(biāo)）和進(jìn)程關(guān)聯(lián)起來。這樣，在某一時(shí)刻，只有一種進(jìn)程處在前臺模式。為了進(jìn)一步地進(jìn)行構(gòu)造，進(jìn)程可以被劃提成線程。 a. 使用這種措施會喪失什么長處？ b. 如果繼續(xù)使用這種修改措施，應(yīng)當(dāng)在哪里分派資源（存儲器、文獻(xiàn)等）：在進(jìn)程級還是線程級？ 答： a. 會話的使用非常適合個(gè)人計(jì)算機(jī)和

38、工作站對交互式圖形接口的需求。它為明確圖形輸出和鍵盤/鼠標(biāo)輸入應(yīng)當(dāng)被關(guān)聯(lián)到什么位置提供了一種統(tǒng)一的機(jī)制，減輕了操作系統(tǒng)的工作承當(dāng)。 b. 應(yīng)當(dāng)和其她的進(jìn)程/線程系統(tǒng)同樣，在進(jìn)程級分派地址空間和文獻(xiàn)。 4.4. 考慮這樣一種環(huán)境，顧客級線程和內(nèi)核級線程呈一對一的映射關(guān)系，并且容許進(jìn)程中的一種或多種線程產(chǎn)生會引起阻塞的系統(tǒng)調(diào)用，而其她線程可以繼續(xù)運(yùn)營。解釋為什么這個(gè)模型可以使多線程程序比在單解決器機(jī)器上的相應(yīng)的單線程程序運(yùn)營速度更快？ 答：問題在于機(jī)器會耗費(fèi)相稱多的時(shí)間等待I/O操作的完畢。在一種多線程程序中，也許一種內(nèi)核級線程會產(chǎn)生引起阻塞的系統(tǒng)調(diào)用，而其她內(nèi)核級線程可以繼續(xù)執(zhí)行。而在單解

39、決器機(jī)器上，進(jìn)程則必須阻塞懂得所有的系統(tǒng)調(diào)用都可以繼續(xù)運(yùn)營。參照：[LEWI96] 4.5. 如果一種進(jìn)程退出時(shí)，該進(jìn)程的某些線程仍在運(yùn)營，請問她們會繼續(xù)運(yùn)營嗎？ 答：不會。當(dāng)一種進(jìn)程退出時(shí)，會帶走它的所有東西——內(nèi)核級線程，進(jìn)程構(gòu)造，存儲空間——涉及線程。參照：[LEWI96] 4.6. OS/390主機(jī)操作系統(tǒng)環(huán)繞著地址空間和任務(wù)的概念構(gòu)造。粗略說來，一種地址空間相應(yīng)于一種應(yīng)用程序，并且或多或少地相應(yīng)于其她操作系統(tǒng)中的一種進(jìn)程；在一種地址空間中，可以產(chǎn)生一組任務(wù)，并且它們可以并發(fā)執(zhí)行，這大體相應(yīng)于多線程的概念。管理任務(wù)構(gòu)造有兩個(gè)重要的數(shù)據(jù)構(gòu)造。地址空間控制塊（ASCB）具有OS/39

40、0所需要的有關(guān)一種地址空間的信息，而不管該地址空間與否在執(zhí)行。ASCB中的信息涉及分派優(yōu)先級、分派給該地址空間的實(shí)存和虛存、該地址空間中就緒的任務(wù)數(shù)以及與否每個(gè)都被換出。一種任務(wù)控制塊（TCB）標(biāo)記一種正在執(zhí)行的顧客程序，它具有在一種地址空間中管理該任務(wù)所需要的信息，涉及解決器狀態(tài)信息、指向該任務(wù)所波及到的程序的指針和任務(wù)執(zhí)行構(gòu)造。ASCB是在系統(tǒng)存儲器中保存的全局構(gòu)造，而TCB是保存在各自的地址空間中的局部構(gòu)造。請問把控制信息劃提成全局和局部兩部分有什么好處？ 答：有關(guān)一種地址空間的盡量多的信息可以隨處址空間被換出，從而節(jié)省了主存。 4.7. 一種多解決系統(tǒng)有8個(gè)解決器和20個(gè)附加磁帶設(shè)

41、備。目前有大量的作業(yè)提交給該系統(tǒng)，完畢每個(gè)作業(yè)最多需要4個(gè)磁帶設(shè)備。假設(shè)每個(gè)作業(yè)開始運(yùn)營時(shí)只需要3個(gè)磁帶設(shè)備，并且在很長時(shí)間內(nèi)都只需要這3個(gè)設(shè)備，而只是在最后很短的一段時(shí)間內(nèi)需要第4個(gè)設(shè)備以完畢操作。同步還假設(shè)此類作業(yè)源源不斷。 a. 假設(shè)操作系統(tǒng)中的調(diào)度器只有當(dāng)4個(gè)磁帶設(shè)備都可用時(shí)才開始一種作業(yè)。當(dāng)作業(yè)開始時(shí)，4個(gè)設(shè)備立即被分派給它，并且直到作業(yè)完畢時(shí)才被釋放。請問一次最多可以同步執(zhí)行幾種作業(yè)？采用這種方略，最多有幾種磁帶設(shè)備也許是空閑的？至少有幾種？ b. 給出此外一種方略，規(guī)定其可以提高磁帶設(shè)備的運(yùn)用率，并且同步可以避免系統(tǒng)死鎖。分析最多可以有幾種作業(yè)同步執(zhí)行，也許浮現(xiàn)的空閑設(shè)備的范

42、疇是多少。 答： a. 采用一種保守的方略，一次最多同步執(zhí)行20/4=5個(gè)作業(yè)。由于分派各一種任務(wù)的磁帶設(shè)備最多同步只有一種空閑，因此在同一時(shí)刻最多有5個(gè)磁帶設(shè)備也許是空閑的。在最佳的狀況下沒有磁帶設(shè)備空閑。 b. 為了更好的運(yùn)用磁設(shè)備，每個(gè)作業(yè)在最初只分派三個(gè)磁帶設(shè)備。第四個(gè)只有的需要的時(shí)候才分派。在這種方略中，最多可以有20/3=6個(gè)作業(yè)同步執(zhí)行。至少的空閑設(shè)備數(shù)量為0，最多有2個(gè)。參照：Advanced Computer Architectrue,K.Hwang,1993. 4.8. 在描述Solaris顧客級線程狀態(tài)時(shí)，曾表白一種顧客級線程也許讓位于具有相似優(yōu)先級的另一種線程。

43、請問，如果有一種可運(yùn)營的、具有更高優(yōu)先級的線程，讓位函數(shù)與否還會導(dǎo)致讓位于具有相似優(yōu)先級或更高優(yōu)先級的線程？ 答：任何一種也許變化線程優(yōu)先級或者使更高優(yōu)先級的線程可運(yùn)營的調(diào)用都會引起調(diào)度，它會依次搶占低優(yōu)先級的活躍線程。因此，永遠(yuǎn)都不會存在一種可運(yùn)營的、具有更高優(yōu)先級的線程。參照：[LEVI96] 第5章 并發(fā)性：互斥和同步 5.1 答：b.協(xié)同程序read讀卡片，將字符賦給一種只有一種字大小的緩沖區(qū)rs然后在賦給squash協(xié)同程。協(xié)同程序Read在每副卡片圖像的背面插入一種額外的空白。協(xié)同程序squash不需要懂得任何有關(guān)輸入的八十個(gè)字符的構(gòu)造，它簡樸的查找成對浮現(xiàn)的星號，然

44、后將更改夠的字符串經(jīng)由只有一種字符大小的緩沖sp，傳遞給協(xié)同程序print。最后協(xié)同程序print簡樸的接受到來的字符串，并將她們打印在涉及125個(gè)字符的行中。 5.2．考慮一種并發(fā)程序，它有兩個(gè)進(jìn)程p和q，定義如下。A.B.C.D和E是任意的原子語句。假設(shè)住程序執(zhí)行兩個(gè)進(jìn)程的parbegin Void p() void q() { A; { D; B;

45、 E; C; } } 答：ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE; 5.3考慮下面的程序 const int n=50; int tally; void total() { int count; for(count =1;count <=n;count ++) {tally++;

46、 } } void main() { tally =0; parbegin(total(),total(); write(tally); } 答：a.隨意一看,tally值的范疇仿佛是落在[50,100]這個(gè)區(qū)間里,由于當(dāng)沒有互斥時(shí)可以從0直接增長到50.這一基本論點(diǎn)是當(dāng)并發(fā)的運(yùn)營這兩進(jìn)程時(shí),我們不也許得到一種比持續(xù)執(zhí)行單一某進(jìn)程所得tally值還低的一種最后tally值.但是考慮下面由這兩進(jìn)程按交替順序執(zhí)行載入,增長,存儲的狀況,同步變更這個(gè)共享變量的取值: 1.進(jìn)程A載入tally值,tally值加到1,

47、在此時(shí)失去解決器(它已經(jīng)增長寄存器的值到1,但是還沒有存儲這個(gè)值). 2.進(jìn)程B載入tally值(仍然是0),然后運(yùn)營完畢49次增長操作,在它已經(jīng)將49這個(gè)值存儲給共享變量tally后,失去解決器控制權(quán). 3.進(jìn)程A重新獲得解決器控制權(quán)去完畢它的第一次存儲操作(用1去替代先前的49這個(gè)tally值),此時(shí)被迫立即放棄解決器. 4.進(jìn)程B重新開始,將1(目前的tally值)載入到它自己的寄存器中,但此時(shí)被迫放棄解決器(注意這是B的最后一次載入). 5.進(jìn)程A被重新安排開始,但這次沒有被中斷,直到運(yùn)營完畢它剩余的49次載入,增長和存儲

48、操作,成果是此時(shí)tally值已經(jīng)是50. 6.進(jìn)程B在它終結(jié)前完畢僅有的最后一次增長和存儲操作.它的寄存器值增至2,同步存儲這個(gè)值做為這個(gè)共享變量的最后成果. 某些覺得會浮現(xiàn)低于2這個(gè)值的成果,這種狀況不會浮現(xiàn).這樣tally值的對的范疇是[2,100]. b.對一般有N個(gè)進(jìn)程的狀況下,tally值的最后范疇是[2,N*50],由于對其她所有進(jìn)程來說,從最初開始運(yùn)營到在第五步完畢.但最后都被進(jìn)程B破壞掉它們的最后成果. 5.4.忙等待與否總是比阻塞等待效率低（根據(jù)解決器的使用時(shí)間）？請解釋。 答：就一般狀況來說是對的,由于忙等待消耗無用的指令周

49、期.然而,有一種特殊狀況,當(dāng)進(jìn)程執(zhí)行到程序的某一點(diǎn)處,在此處要等待直到條件滿足,而正好條件已滿足,此時(shí)忙等待會立即有成果,然而阻塞等待會消耗操作系統(tǒng)資源在換出與換入進(jìn)程上. 5.5考慮下面的程序 boolean blocked[2]; int rurn; void P(int id) { While (true) {

50、 While(turn!=id); { While(blocked[1-!id] /*do nothing*/; Turn =id; } } Void main () {

51、 Blocked[0]=false; Blocked[1]=false; Turn=0; Parbegin(P(0),P(1)); } 這是【HYMA66】中提出的解決互斥問題的一種措施。請舉出證明該措施不對的的一種反例。 答：考慮這種狀況:此時(shí)turn=0,進(jìn)程P(1)使布爾變量blocked[1]的值為true,在這時(shí)發(fā)現(xiàn)布爾變量blocked[0]的值為f

52、alse,然后P(0)會將true值賦予blocked[0] ,此時(shí)turn=0,P(0)進(jìn)入臨界區(qū),P(1)在將1賦值給turn后,也進(jìn)入了臨界區(qū). 5.6解決互斥的另一種軟件措施是lamport的面包店（bakery）算法，之因此起這個(gè)名字，是由于它的思想來自于面包店或其她商店中，每個(gè)顧客在達(dá)到時(shí)都得到一種有編號的票，并按票號依次得到服務(wù)，算法如下： Boolean choosing[n]; Int number[n]; While (true)

53、 { Choosing[i]=true; Number[i]=1+getmax(number[],n)； Choosing[i]=false; For(int j=0;j

54、 {} While ((number[j]!=0)&&(number[j],j)<(number[i],i) {} } /*critical section*/ Number[i]=0; /*remainder*/;

55、 } 數(shù)組choosing和number分別被初始化成false和0，每個(gè)數(shù)組的第i個(gè)元素可以由進(jìn)程i讀或?qū)?，但其她進(jìn)程只能讀。符號（a，b）<（c，d）被定義成 （a，c）或（a=c且b

56、界區(qū).當(dāng)一種進(jìn)程退出臨界區(qū)時(shí),重新設(shè)立它的票號為0. b.如果每個(gè)進(jìn)程被分派唯一的一種進(jìn)程號,那么總會有一種唯一的,嚴(yán)格的進(jìn)程順序.因此,死鎖可以避免. c.為了闡明互斥,我們一方面需要證明下面的定理:如果Pi在它的臨界區(qū),Pk已經(jīng)計(jì)算出來它的number[k],并試圖進(jìn)入臨界區(qū),此時(shí)就有下面的關(guān)系式: ( number[i], i ) < ( number[k], k ).為證明定理,定義下面某些時(shí)間量: Tw1:Pi最后一次讀choosing[k], 當(dāng) j=k,在它的第一次等待時(shí),因此我們在Tw1處有choosing[k] = false.

57、 Tw2:Pi開始它的最后執(zhí)行, 當(dāng)j=k,在它的第二次while循環(huán)時(shí),因此我們有Tw1 < Tw2. Tk1:Pk在開始repeat循環(huán)時(shí);Tk2:Pk完畢number[k]的計(jì)算; Tk3: Pk設(shè)立choosing[k]為false時(shí).我們有Tk1

58、k2

59、待進(jìn)入臨界區(qū)的進(jìn)程在n-1個(gè)turn內(nèi)進(jìn)入，n是規(guī)定訪問臨界區(qū)的進(jìn)程數(shù)，turn是指一種進(jìn)程離開臨界區(qū)而另一種進(jìn)程獲準(zhǔn)訪問這個(gè)一種事件。 答：如下的程序由[SILB98]提供： var j: 0..n-1; key: boolean; repeat waiting[i] := true; key := true; while waiting[i] and key do key := testset(lock); waiting[i] := false; < critical section > j := i + 1 mod n; while (j ≠ i) and (no

60、t waiting[j]) do j := j + 1 mod n; if j = i then lock := false else waiting := false; < remainder section > Until 這個(gè)算法用最一般的數(shù)據(jù)構(gòu)造：var waiting: array [0..n – 1] of boolean Lock：boolean 這些數(shù)據(jù)構(gòu)造被初始化成假的，當(dāng)一種進(jìn)程離開它的臨界區(qū)，它就搜索waiting的循環(huán)隊(duì)列 5.8考慮下面有關(guān)信號量的定義： Voi

61、d semWait(s) { If (s.count>0) { s.count--; } Else { Place this process in s.queue; Block;

62、 } } Void semSignal(s) { If (there is at liast one process blocked on semaphore) { Remove a process P from s.queue; Place process P on ready list;

63、 } Else s.count++; } 比較這個(gè)定義和圖5.3中的定義，注意有這樣的一種區(qū)別：在前面的定義中，信號量永遠(yuǎn)不會取負(fù)值。當(dāng)在程序中分別使用這兩種定義時(shí)，其效果有什么不同？也就是說，與否可以在不變化程序意義的前提下，用一種定義替代另一種？ 答：這兩個(gè)定義是等價(jià)的，在圖5.3的定義中，當(dāng)信號量的值為負(fù)值時(shí)，它的值代表了有多少個(gè)進(jìn)程在等待；在此題中的定義中，雖然你沒有有關(guān)這方面的信息，但是這兩個(gè)版本的函數(shù)是同樣的。 5.9可以用二元

64、信號量實(shí)現(xiàn)一般信號量。我們使用semWaitB操作和semSignalB操作以及兩個(gè)二元信號量delay和mutex?？紤]下面的代碼 Void semWait(semaphor s) { semWaitB(mutex); s--; if (s<0) { semSignalB(mutex); semWaitB(del

65、ay); } Else Semsignalb(mutex) } Void semSignal(semaphore s); { semWaitB(mutex); s++; if(s<=0) semSignalB(delay);

66、 semSignalB(mutex); } 最初。S被設(shè)立成期待的信號量值，每個(gè)semwait操作將信號量減1，每個(gè)semsignal操作將信號量加1.二元信號量mutex被初始化成1，保證在更新在更新s時(shí)保證互斥，二元信號量delay被初始化成0，用于掛起進(jìn)程， 上面的程序有一種缺陷，證明這個(gè)缺陷，并提出解決方案。提示：假設(shè)兩個(gè)進(jìn)程，每個(gè)都在s初始化為0時(shí)調(diào)用semwait（s）,當(dāng)?shù)谝环N剛剛執(zhí)行了semsignalb（mutex）但還沒有執(zhí)行semwaitb（delay），第二個(gè)調(diào)用semwait（s）并達(dá)到同一點(diǎn)。目前需要做的就是移動程序的一行. 答：假設(shè)兩個(gè)進(jìn)程，每個(gè)都在s被初始化成0時(shí)調(diào)用semWait（s），當(dāng)?shù)谝环N剛執(zhí)行了semSignalB（mutex）但還沒有執(zhí)行semWaitB（delay）時(shí)，第二個(gè)調(diào)用semWait（s）并達(dá)到同一點(diǎn)。由于s=-2 mutex沒有鎖定，如果有此外兩個(gè)進(jìn)程同步成功的調(diào)用semSignal（s），她們接著就會調(diào)用semsignalb（delay），但是第二個(gè)s