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

1、52 / 54第 1 章 計(jì)算機(jī)系統(tǒng)概述1.1、 圖 1.3 中的理想機(jī)器還有兩條I/O 指令：0011 = 從 I/O 中載入AC0111 = 把 AC 保存到I/O 中1.4 的格式） ：在這種情況下， 12 位地址標(biāo)識(shí)一個(gè)特殊的外部設(shè)備。請(qǐng)給出以下程序的執(zhí)行過(guò)程（按照?qǐng)D1. 從設(shè)備 5 中載入 AC 。2. 加上存儲(chǔ)器單元940 的內(nèi)容。3. 把 AC 保存到設(shè)備 6 中。假設(shè)從設(shè)備5 中取到的下一個(gè)值為 3940 單元中的值為 2。答案：存儲(chǔ)器（ 16 進(jìn)制內(nèi)容） ： 300 ： 3005 ； 301： 5940 ； 302 ： 7006步驟 1 ： 3005 IR ；步驟2： 3 A

2、C步驟 3: 5940IR;步驟 4: 3+ 2=5 AC步驟5: 7006 IR:步驟6: AC 設(shè)備 61.2、 本章中用6 步來(lái)描述圖 1.4 中的程序執(zhí)行情況，請(qǐng)使用 MAR 和 MBR 擴(kuò)充這個(gè)描述。答案： 1. a. PC 中包含第一條指令的地址300 ，該指令的內(nèi)容被送入 MAR 中。b. 地址為 300 的指令的內(nèi)容（值為十六進(jìn)制數(shù)1940）被送入MBR ，并且 PC 增 1。這兩個(gè)步驟是并行完成的。c. MBR 中的值被送入指令寄存器IR 中。2. a. 指令寄存器 IR 中的地址部分（ 940 ）被送入 MAR 中。b. 地址 940 中的值被送入 MBR 中。c. MBR

3、 中的值被送入 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 的存儲(chǔ)單元中的內(nèi)容相加，結(jié)果保存到 AC 中。5. a. PC 中的值（ 302）被送入 MAR 中。b. 地址為 302 的指令的內(nèi)容（值為十六進(jìn)制數(shù)2941）被送入 MBR ，并且 PC 增 1 。c.

4、MBR 中的值被送入指令寄存器IR 中。6. a. 指令寄存器 IR 中的地址部分（ 941 ）被送入 MAR 中。b. AC 中的值被送入 MBR 中。c. MBR 中的值被存儲(chǔ)到地址為 941 的存儲(chǔ)單元之中。1.4、 假設(shè)有一個(gè)微處理器產(chǎn)生一個(gè)16 位的地址（例如，假設(shè)程序計(jì)數(shù)器和地址寄存器都是16 位）并且具有一個(gè) 16 位的數(shù)據(jù)總線。a.如果連接到一個(gè)16位存儲(chǔ)器上，處理器能夠直接訪問(wèn)的最大存儲(chǔ)器地址空間為多少？b.如果連接到一個(gè)8位存儲(chǔ)器上，處理器能夠直接訪問(wèn)的最大存儲(chǔ)器地址空間為多少？c.處理訪問(wèn)一個(gè)獨(dú)立的I/O空間需要哪些結(jié)構(gòu)特征？d.如果輸入指令和輸出指令可以表示8位I/O端

5、口號(hào)，這個(gè)微處理器可以支持多少8位I/O端口？答案：對(duì)于（a）和（b）兩種情況，微處理器可以直接訪問(wèn)的最大存儲(chǔ)器地址空間為216 = 64K bytes;唯一的區(qū)別是 8位存儲(chǔ)器每次訪問(wèn)傳輸1 個(gè)字節(jié)，而16位存儲(chǔ)器每次訪問(wèn)可以傳輸一個(gè)字節(jié)或者一個(gè)16位的字。對(duì)于 （c） 情況，特殊的輸入和輸出指令是必要的，這些指令的執(zhí)行體會(huì)產(chǎn)生特殊的“ I/O 信號(hào)”（有別于“存儲(chǔ)器信號(hào)”，這些信號(hào)由存儲(chǔ)器類型指令的執(zhí)行體產(chǎn)生）；在最小狀態(tài)下，一個(gè)附加的輸出針腳將用來(lái)傳輸新的信號(hào)。對(duì)于（d）情況，它支持28 = 256個(gè)輸入和28 = 256個(gè)輸出字節(jié)端口和相同數(shù)目的16位I/O端口；在任一情況，一個(gè)輸入和

6、一個(gè)輸出端口之間的區(qū)別是通過(guò)被執(zhí)行的輸入輸出指令所產(chǎn)生的不同信號(hào)來(lái)定義的。1.5、 考慮一個(gè)32 位微處理器，它有一個(gè)16 位外部數(shù)據(jù)總線，并由一個(gè)8MHz 的輸入時(shí)鐘驅(qū)動(dòng)。假設(shè)這個(gè)微處理器有一個(gè)總線周期，其最大持續(xù)時(shí)間等于4 個(gè)輸入時(shí)鐘周期。請(qǐng)問(wèn)該微處理器可以支持的最大數(shù)據(jù)傳送速度為多少？外部數(shù)據(jù)總線增加到 21 位，或者外部時(shí)鐘頻率加倍，哪種措施可以更好地提高處理器性能？請(qǐng)敘述你的設(shè)想并解釋原因。答案：時(shí)鐘周期=1/ （8MHZ） = 125ns總線周期=4X125ns= 500ns每500ns傳車2比特；因此傳輸速度=4MB/S加倍頻率可能意味著采用了新的芯片制造技術(shù)（假設(shè)每個(gè)指令都有相

7、同的時(shí)鐘周期數(shù)） ；加倍外部數(shù)據(jù)總線， 在芯片數(shù)據(jù)總線驅(qū)動(dòng)/ 鎖存、總線控制邏輯的修改等方面手段廣泛 （或許更新） 。 在第一種方案中，內(nèi)存芯片的速度要提高一倍 （大約） ， 而不能降低微處理器的速度； 第二種方案中， 內(nèi)存的字長(zhǎng)必須加倍，以便能發(fā)送/接受 32 位數(shù)量。1.6、 考慮一個(gè)計(jì)算機(jī)系統(tǒng)，它包含一個(gè)I/O 模塊，用以控制一臺(tái)簡(jiǎn)單的鍵盤/打印機(jī)電傳打字設(shè)備。CPU中包含下列寄存器，這些寄存器直接連接到系統(tǒng)總線上：INPR ：輸入寄存器， 8 位OUTR ：輸出寄存器， 8 位FGI ：輸入標(biāo)記，1 位FGO ：輸出標(biāo)記， 1 位IEN ：中斷允許，1 位I/O 模塊控制從打字機(jī)中輸入

8、擊鍵，并輸出到打印機(jī)中去。打字機(jī)可以把一個(gè)字母數(shù)字符號(hào)編碼成一個(gè)8位字，也可以把一個(gè)8 位字解碼成一個(gè)字母數(shù)字符號(hào)。當(dāng) 8 位字從打字機(jī)進(jìn)入輸入寄存器時(shí)，輸入標(biāo)記被置位；當(dāng)打印一個(gè)字時(shí)，輸出標(biāo)記被置位。a. 描述 CPU 如何使用這4 個(gè)寄存器實(shí)現(xiàn)與打字機(jī)間的輸入/輸出。b. 描述通過(guò)使用 IEN ，如何提高執(zhí)行效率？答案：a.來(lái)源于打字機(jī)的輸入儲(chǔ)存在INPR中。只有當(dāng)FGI = 0時(shí)，INPR才會(huì)接收來(lái)自打字機(jī)的數(shù)據(jù)。當(dāng)數(shù)據(jù)接收后，被儲(chǔ)存在INPR里面，同時(shí)FGI置為1。CPU定期檢查FGI。如果FGI = 1, CPU將把INPR 里面的內(nèi)容傳送至AC ，并把 FGI 置為 0。當(dāng)CPU需

9、要傳送數(shù)據(jù)到打字機(jī)時(shí)，它會(huì)檢查FGO。如果FGO=0, CPU處于等待。如果 FGO=1, CPU將把AC的內(nèi)容傳送至 OUTER并把FGO置為0。當(dāng)數(shù)字符號(hào)打印后，打字機(jī)將把FGI置為 1。b.（ A ）描述的過(guò)程非常浪費(fèi)。速度遠(yuǎn)高于打字機(jī)的 CPU 必須反復(fù)不斷的檢查FGI 和 FGO 。如果中斷被使用， 當(dāng)打字機(jī)準(zhǔn)備接收或者發(fā)送數(shù)據(jù)時(shí)， 可以向 CPU 發(fā)出一個(gè)中斷請(qǐng)求。 IEN 計(jì)數(shù)器可以由 CPU 設(shè)置（在程序員的控制下） 。1.7、 實(shí)際上在所有包括DMA 模塊的系統(tǒng)中， DMA 訪問(wèn)主存儲(chǔ)器的優(yōu)先級(jí)總是高于處理器訪問(wèn)主存儲(chǔ)器的優(yōu)先級(jí)。這是為什么 ?答案：如果一個(gè)處理器在嘗試著讀或

10、者寫存儲(chǔ)器時(shí)被掛起, 通常除了一點(diǎn)輕微的時(shí)間損耗之外沒(méi)有任何危害。但是，DMAT能從或者向設(shè)備（例如磁盤或磁帶）以數(shù)據(jù)流的方式接收或者傳輸數(shù)據(jù)并且這是不能被打斷的。否則，如果 DM般備被掛起（拒絕繼續(xù)訪問(wèn)主存），數(shù)據(jù)可能會(huì)丟失。1.9、 一臺(tái)計(jì)算機(jī)包括一個(gè)CPU 和一臺(tái) I/O 設(shè)備 D ，通過(guò)一條共享總線連接到主存儲(chǔ)器M ，數(shù)據(jù)總線的寬度為 1 個(gè)字。 CPU 每秒最多可執(zhí)行106條指令，平均每條指令需要5 個(gè)機(jī)器周期，其中 3個(gè)周期需要使用存儲(chǔ)器總線。存儲(chǔ)器讀/寫操作使用1 個(gè)機(jī)器周期。假設(shè)CPU 正在連續(xù)不斷地執(zhí)行后臺(tái)程序，并且需要保證 95% 的指令執(zhí)行速度，但沒(méi)有任何 I/O 指令。

11、 假設(shè) 1 個(gè)處理器周期等于 1 個(gè)總線周期， 現(xiàn)在要在 M 和 D之間傳送大塊數(shù)據(jù)。a.若使用程序控制I/O , I/O每傳送1個(gè)字需要CPU執(zhí)行兩條指令。請(qǐng)估計(jì)通過(guò)D的I/O數(shù)據(jù)傳送的最大可 能速度。b.如果使用DMA傳送，請(qǐng)估計(jì)傳送速度。答案：a.處理器只能分配 5%的時(shí)間給I/O.所以最大的I/O指令傳送速度是10e6X 0.05= 50000條指令/秒。 因此I/O的傳送速率是25000字/秒。b.使用DMA控制時(shí)，可用的機(jī)器周期下的數(shù)量是10e6 (0.05X 5+0.95X 2) = 2.15X 10e6如果我們假設(shè) DMA模塊可以使用所有這些周期，并且忽略任何設(shè)置和狀態(tài)檢查時(shí)間

12、，那么這個(gè)值就是最大的I/O傳輸速率。1.10、 考慮以下代碼：for ( i = 0 ; i 20 ; i+)for (j = 0 ; j 10 ; j+) ai = ai*ja.請(qǐng)舉例說(shuō)明代碼中的空間局部性。b.請(qǐng)舉例說(shuō)明代碼中的時(shí)間局部性。答案:1.11、答案:a.讀取第二條指令是緊跟著讀取第一條指令的。b.在很短的間歇時(shí)間內(nèi)，ai在循環(huán)內(nèi)部被訪問(wèn)了十次。請(qǐng)將附錄1A中的式(1.1)和式(1.2)推廣到n級(jí)存儲(chǔ)器層次中。 定義：Ci =Si =T i =Hi =Bi =存儲(chǔ)器層次 存儲(chǔ)器層次 存儲(chǔ)器層次i上每一位的存儲(chǔ)單元平均花銷i的規(guī)模大小i上訪問(wèn)一個(gè)字所需時(shí)間一個(gè)字在不高于層次i的存

13、儲(chǔ)器上的概率把一個(gè)數(shù)據(jù)塊從層次i+1的存儲(chǔ)器上傳輸?shù)綄哟蝘高速緩沖存儲(chǔ)器作為是存儲(chǔ)器層次1;主存為存儲(chǔ)器層次的存儲(chǔ)器上所需時(shí)間2;針對(duì)所有的N層存儲(chǔ)器層以此類推。 有:nCi SiCJ1CSnSi i 1nTs的引用更復(fù)雜，我們從概率論入手：所期望的值x iPrx 1,由此我們可以寫出:i 1n TsTiHii 1我們需要清楚如果一個(gè)字在 M1 (緩存)中，那么對(duì)它的讀取非?？臁Ｈ绻@個(gè)字在M2而不在M1中，那么數(shù)據(jù)塊需要從M2傳輸?shù)組1中，然后才能讀取。因此，T2= B1+T1進(jìn)一步，T 3 = B2+T 2 = B1+B2+T1i 1以此類推：TiBj工j 1 n i 1n所以，Ts(Bj

14、Hi) Ti Hi1 2 j 1i 1n但是， Hi 1i 1最后,Ts(BH) Tii 2 j 11.12、 考慮一個(gè)存儲(chǔ)器系統(tǒng)，它具有以下參數(shù)：Tc = 100 nsCc = 0.01 分/位Tm = 1200 nsCm = 0.001 分/位a.1MB的主存儲(chǔ)器價(jià)格為多少？ b.使用高速緩沖存儲(chǔ)器技術(shù)，1MB的主存儲(chǔ)器價(jià)格為多少？c.如果有效存取時(shí)間比高速緩沖存儲(chǔ)器存取時(shí)間多10% ,命中率H為多少？答案：a.價(jià)格=CmX8X106 = 8X103 0 = $80 b.價(jià)格 = CcX8M06 = 8 104 0 = $800 c.由等式 1.1 知:1.1 Ti = Ti+(1-H)T

15、2(0.1)(100) = (1-H)(1200)H=1190/12001.13、 一臺(tái)計(jì)算機(jī)包括包括高速緩沖存儲(chǔ)器、主存儲(chǔ)器和一個(gè)用做虛擬存儲(chǔ)器的磁盤。如果要存取的字在 高速緩沖存儲(chǔ)器中，存取它需要20ns；如果該字在主存儲(chǔ)器中而不在高速緩沖存儲(chǔ)器中，把它載入高速緩沖存儲(chǔ)器需要 60ns (包括最初檢查高速緩沖存儲(chǔ)器的時(shí)間)，然后再重新開始存?。蝗绻撟植辉谥鞔鎯?chǔ)器中，從磁盤中取到內(nèi)存需要12ms,接著復(fù)制到高速緩沖存儲(chǔ)器中還需要60ns,再重新開始存取。高速緩沖存儲(chǔ)器的命中率為0.9,主存儲(chǔ)器的命中率為0.6,則該系統(tǒng)中存取一個(gè)字的平均存取時(shí)間是多少(單位為ns) ?答案：有三種情況需要考

16、慮：字所在的位置概率訪問(wèn)所需時(shí)間(ns)在緩存中0.920小在緩存，在生存中(0.1) (0.6) = 0.0660+20 = 80小在緩存也不在生存中(0.1) (0.4) = 0.0412ms+60+20 = 12,000,080所以平均訪問(wèn)時(shí)間是：Avg = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns1.14、假設(shè)處理器使用一個(gè)棧來(lái)管理過(guò)程調(diào)用和返回。請(qǐng)問(wèn)可以取消程序計(jì)數(shù)器而用棧指針代替嗎？ 答案：如果棧只用于保存返回地址。或者如果棧也用于傳遞參數(shù)，這種方案只有當(dāng)棧作為傳遞參數(shù)的控制單元而非機(jī)器指令時(shí)才成立。這兩種情況下可以

17、取消程序計(jì)數(shù)器而用棧指針代替。在后者情況中, 處理器同時(shí)需要一個(gè)參數(shù)和指向棧頂部的程序計(jì)數(shù)器。第2章 操作系統(tǒng)概述2.1 假設(shè)我們有一臺(tái)多道程序的計(jì)算機(jī)，每個(gè)作業(yè)有相同的特征。在一個(gè)計(jì)算周期T中，一個(gè)作業(yè)有一半時(shí)間花費(fèi)在I/O上，另一半用于處理器的活動(dòng)。每個(gè)作業(yè)一共運(yùn)行 N個(gè)周期。假設(shè)使用簡(jiǎn)單的循環(huán)法調(diào)度，并且I/O操作可以與處理器操作重疊。定義以下量：?時(shí)間周期=完成任務(wù)的實(shí)際時(shí)間?吞吐量=每個(gè)時(shí)間周期T內(nèi)平均完成的作業(yè)數(shù)目?處理器使用率=處理器活躍(不是處于等待)的時(shí)間的百分比當(dāng)周期T分別按下列方式分布時(shí)，對(duì) 1個(gè)、2個(gè)和4個(gè)同時(shí)發(fā)生的作業(yè)，請(qǐng)計(jì)算這些量：a.前一般用于I/O,后一半用于處

18、理器。b.前四分之一和后四分之一用于I/O,中間部分用于處理器。答：(a)和(b)的答案相同。盡管處理器活動(dòng)不能重疊，但I(xiàn)/O操作能。一個(gè)作業(yè)時(shí)間周期=NT處理器利用率=50 %兩個(gè)作業(yè)時(shí)間周期=nt處理器利用率=100%四個(gè)作業(yè) 時(shí)間周期二(2N-1) NT 處理器利用率=100%2.2 I/O 限制的程序是指如果單獨(dú)運(yùn)行，則花費(fèi)在等待 I/O 上的時(shí)間比使用處理器的時(shí)間要多的程序。處理器限制的程序則相反。假設(shè)短期調(diào)度算法偏愛(ài)那些在近期石油處理器時(shí)間較少的算法，請(qǐng)解釋為什么這個(gè)算法偏愛(ài) I/O 限制的程序，但是并不是永遠(yuǎn)不受理處理器限制程序所需的處理器時(shí)間？受 I/O 限制的程序使用相對(duì)較少

19、的處理器時(shí)間，因此更受算法的青睞。然而，受處理器限制的進(jìn)程如果在足夠長(zhǎng)的時(shí)間內(nèi)得不到處理器時(shí)間，同一算法將允許處理器去處理此進(jìn)程，因?yàn)樗罱鼪](méi)有使用過(guò)處理器。這樣，一個(gè)處理器限制的進(jìn)程不會(huì)永遠(yuǎn)得不到處理器。2.3 請(qǐng)對(duì)優(yōu)化分時(shí)系統(tǒng)的調(diào)度策略和用于優(yōu)化多道程序批處理系統(tǒng)的調(diào)度策略進(jìn)行比較。分時(shí)系統(tǒng)關(guān)注的是輪轉(zhuǎn)時(shí)間，時(shí)間限制策略更有效是因?yàn)樗o所有進(jìn)程一個(gè)較短的處理時(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)的系統(tǒng)調(diào)用？系統(tǒng)調(diào)用被應(yīng)用

20、程序用來(lái)調(diào)用一個(gè)由操作系統(tǒng)提供的函數(shù)。通常情況下，系統(tǒng)調(diào)用最終轉(zhuǎn)換成在內(nèi)核模式下的系統(tǒng)程序。2.5 在 IBM 的主機(jī)操作系統(tǒng)OS/390 中，內(nèi)核中的一個(gè)重要模塊是系統(tǒng)資源管理程序（ System ResourceManager,SRM） ，他負(fù)責(zé)地址空間（進(jìn)程）之間的資源分配。 SRM 是的 OS/390 在操作系統(tǒng)中具有特殊性，沒(méi)有任何其他的主機(jī)操作系統(tǒng)，當(dāng)然沒(méi)有任何其他類型的操作系統(tǒng)可以比得上SRM 所實(shí)現(xiàn)的功能。資源的概念包括處理器、實(shí)存和 I/O 通道， SRM 累計(jì)處理器、 I/O 通道和各種重要數(shù)據(jù)結(jié)構(gòu)的利用率，它的目標(biāo)是基于性能監(jiān)視和分析提供最優(yōu)的性能，其安裝設(shè)置了以后的各種

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

22、均利用率。典型的平均時(shí)間應(yīng)該是兩分鐘以上，這個(gè)平均時(shí)間看起來(lái)很長(zhǎng)，其實(shí)并不長(zhǎng)。第 3 章 進(jìn)程描述和控制3.1. 給出操作系統(tǒng)進(jìn)行進(jìn)程管理時(shí)的五種主要活動(dòng)，并簡(jiǎn)單描述為什么需要它們。答：用戶進(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)程終止時(shí)，操作系統(tǒng)需要收回任何可以重新利用的資源。進(jìn)程的暫停和繼續(xù)執(zhí)行。在進(jìn)程調(diào)度中，當(dāng)進(jìn)程在等待某些資源時(shí)，操作系統(tǒng)需要將它的狀態(tài)改變?yōu)榈却蚓途w狀態(tài)。 當(dāng)所需要的資源可用時(shí)， 操作系統(tǒng)需要將它的狀態(tài)變?yōu)檫\(yùn)行態(tài)以使其繼續(xù)執(zhí)行。提供進(jìn)程的同步

23、機(jī)制。 合作的進(jìn)程可能需要共享數(shù)據(jù)。 對(duì)共享數(shù)據(jù)的并行訪問(wèn)可能會(huì)導(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)境中，多個(gè)進(jìn)程可能會(huì)競(jìng)爭(zhēng)有限的資源。如果發(fā)生死鎖，所有的等待進(jìn)程都將永遠(yuǎn)不能由等待狀態(tài)再變?yōu)檫\(yùn)行態(tài)，資源將被浪費(fèi)，工作永遠(yuǎn)不能完成。3.2. 在 PINK89 中為進(jìn)程定義了以下?tīng)顟B(tài)：執(zhí)行（運(yùn)行）態(tài)、活躍（就緒）態(tài)、阻塞態(tài)和掛起態(tài)。當(dāng)進(jìn)程正在等待允許使用某一資源時(shí)，它處于阻塞態(tài)；當(dāng)進(jìn)程正在等待它

24、已經(jīng)獲得的某種資源上的操作完成時(shí)，它處于掛起態(tài)。在許多操作系統(tǒng)中，這兩種狀態(tài)常常放在一起作為阻塞態(tài)，掛起態(tài)使用本章中給出的定義。請(qǐng)比較這兩組定義的優(yōu)點(diǎn)。答： PINK89 中引用了以下例子來(lái)闡述其中阻塞和掛起的定義：假設(shè)一個(gè)進(jìn)程已經(jīng)執(zhí)行了一段時(shí)間，它需要一個(gè)額外的磁帶設(shè)備來(lái)寫出一個(gè)臨時(shí)文件。在它開始寫磁帶之前，進(jìn)程必須得到使用某一設(shè)備的許可。當(dāng)它做出請(qǐ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í)要對(duì)新獲得的磁帶設(shè)備進(jìn)行寫操作。這時(shí) 進(jìn)程變?yōu)閽炱饝B(tài)，等待該磁帶上當(dāng)前所進(jìn)行的寫操作完成

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

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

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

28、6. VAM/VMS操作系統(tǒng)采用了四種處理器訪問(wèn)模式，以促進(jìn)系統(tǒng)資源在進(jìn)程間的保護(hù)和共享。訪問(wèn)模 式確定：指令執(zhí)行特權(quán)：處理器將執(zhí)行什么指令。內(nèi)存訪問(wèn)特權(quán)：當(dāng)前指令可能訪問(wèn)虛擬內(nèi)存中的哪個(gè)單元。四種模式如下：內(nèi)核模式：執(zhí)行VMS 操作系統(tǒng)的內(nèi)核，包括內(nèi)存管理、中斷處理和 I/O 操作。執(zhí)行模式：執(zhí)行許多操作系統(tǒng)服務(wù)調(diào)用，包括文件（磁盤和磁帶）和記錄管理例程。管理模式：執(zhí)行其他操作系統(tǒng)服務(wù)，如響應(yīng)用戶命令。用戶模式：執(zhí)行用戶程序和諸如編譯器、編輯器、鏈接程序、調(diào)試器之類的實(shí)用程序。在較少特權(quán)模式執(zhí)行的進(jìn)程通常需要調(diào)用在較多特權(quán)模式下執(zhí)行的過(guò)程，例如，一個(gè)用戶程序需要一個(gè)操作系統(tǒng)服務(wù)。這個(gè)調(diào)用通過(guò)

29、使用一個(gè)改變模式（簡(jiǎn)稱CHM ）指令來(lái)實(shí)現(xiàn)，該指令將引發(fā)一個(gè)中斷， 把控制轉(zhuǎn)交給處于新的訪問(wèn)模式下的例程， 并通過(guò)執(zhí)行RE（I Return from Exception or Interrupt ，從異?；蛑袛喾祷兀┲噶罘祷?。a. 很多操作系統(tǒng)有兩種模式，內(nèi)核和用戶，那么提供四種模式有什么優(yōu)點(diǎn)和缺點(diǎn)？b. 你可以舉出一種有四種以上模式的情況嗎？答：c. 四種模式的優(yōu)點(diǎn)是對(duì)主存的訪問(wèn)控制更加靈活，能夠?yàn)橹鞔嫣峁└玫谋Ｗo(hù)。缺點(diǎn)是復(fù)雜和處 理的開銷過(guò)大。例如，程序在每一種執(zhí)行模式下都要有一個(gè)獨(dú)立的堆棧。d. 原則上，模式越多越靈活，但是四種以上的模式似乎很難實(shí)現(xiàn)。3.7. 在前面習(xí)題中討論的 V

30、MS 方案常常稱為環(huán)狀保護(hù)結(jié)構(gòu)，如圖 3.18所示。 3.3 節(jié)所描述的簡(jiǎn)單的內(nèi)核/用戶方案是一種兩環(huán)結(jié)構(gòu)，SILB04 指出了這種方法的問(wèn)題：環(huán)狀（層次）結(jié)構(gòu)的主要缺點(diǎn)是它不允許我們實(shí)施須知原理， 特別地，如果一個(gè)對(duì)象必須在域Dj 中可訪問(wèn)，但在域Di 中不可訪問(wèn)， 則必須有就 ji 。這意味著在Di 中可訪問(wèn)的每個(gè)段在Dj 中都可以訪問(wèn)。a. 請(qǐng)清楚地解釋上面引文中提出的問(wèn)題。b. 請(qǐng)給出環(huán)狀結(jié)構(gòu)操作系統(tǒng)解決這個(gè)問(wèn)題的一種方法。答：c. 當(dāng) ji 時(shí)，運(yùn)行在Di 中的進(jìn)程被禁止訪問(wèn) Dj 中的對(duì)象。因此，如果Dj 中包含的信息比 Di 中的更具有特權(quán)或者要求的安全性更高，那么這種限制就是合

31、理的。然而，通過(guò)以下方法卻可以繞過(guò)這種安全策略。一個(gè)運(yùn)行在Dj 中的進(jìn)程可以讀取Dj 中的數(shù)據(jù)，然后把數(shù)據(jù)復(fù)制到Di 中。隨后， Di 中的進(jìn)程就可以訪問(wèn)這些信息了。d. 有一種解決這一問(wèn)題的方法叫做可信系統(tǒng)，我們將在16 章中進(jìn)行討論。3.8. 圖3.7 （b）表明一個(gè)進(jìn)程每次只能在一個(gè)事件隊(duì)列中。a. 是否能夠允許進(jìn)程同時(shí)等待一個(gè)或多個(gè)事件？請(qǐng)舉例說(shuō)明。b. 在這種情況下，如何修改圖中的排隊(duì)結(jié)構(gòu)以支持這個(gè)新特點(diǎn)？答：c. 一個(gè)進(jìn)程可能正在處理從另一個(gè)進(jìn)程收到的數(shù)據(jù)并將結(jié)果保存到磁盤上。如果當(dāng)前在另一個(gè)進(jìn)程中正有數(shù)據(jù)在等待被取走，進(jìn)程就可以繼續(xù)獲得數(shù)據(jù)并處理它。如果前一個(gè)寫磁盤操作已經(jīng)完成，

32、并且有處理好的數(shù)據(jù)在等待寫出，那么進(jìn)程就可以繼續(xù)寫磁盤。這樣就可能存在某一時(shí)刻，進(jìn)程即在等待從輸入進(jìn)程獲得數(shù)據(jù)，又在等待磁盤可用。d. 有很多種方法解決這一問(wèn)題。可以使用一種特殊的隊(duì)列，或者將進(jìn)程放入兩個(gè)獨(dú)立的隊(duì)列中。不論采用哪種方法，操作系統(tǒng)都必須處理好細(xì)節(jié)工作，使進(jìn)程相繼地關(guān)注兩個(gè)事件的發(fā)生。3.9. 在很多早期計(jì)算機(jī)中，中斷導(dǎo)致寄存器值被保存在與給定的中斷信息相關(guān)聯(lián)的固定單元。在什么情況下這是一種實(shí)用的技術(shù)？請(qǐng)解釋為什么它通常是不方便的。答：這種技術(shù)是基于被中斷的進(jìn)程A 在中斷響應(yīng)之后繼續(xù)執(zhí)行的假設(shè)的。但是，在通常情況下，中斷可能會(huì)導(dǎo)致另一個(gè)進(jìn)程B 搶占了進(jìn)程A 。 這是就必須將進(jìn)程A

33、的執(zhí)行狀態(tài)從與中斷相關(guān)的位置復(fù)制到與 A 相關(guān)的進(jìn)程描述中。然而機(jī)器卻有可能仍將它們保存到前一位置。參考： BRIN73 。3.10. 3.4 節(jié)曾經(jīng)講述過(guò)，由于在內(nèi)核模式下執(zhí)行的進(jìn)程是不能被搶占的，因此UNIX 不適用于實(shí)時(shí)應(yīng)用。請(qǐng)闡述原因。答：由于存在進(jìn)程不能被搶占的情況（如在內(nèi)核模式下執(zhí)行的進(jìn)程） ，操作系統(tǒng)不可能對(duì)實(shí)時(shí)需求給予迅速的反應(yīng)。第 4 章 線程、對(duì)稱多處理和微內(nèi)核4.1. 一個(gè)進(jìn)程中的多個(gè)線程有以下兩個(gè)優(yōu)點(diǎn)： （ 1）在一個(gè)已有進(jìn)程中創(chuàng)建一個(gè)新線程比創(chuàng)建一個(gè)新進(jìn)程所需的工作量少； （ 2）在同一個(gè)進(jìn)程中的線程間的通信比較簡(jiǎn)單。請(qǐng)問(wèn)同一個(gè)進(jìn)程中的兩個(gè)線程間的模式切換與不同進(jìn)程中

34、的兩個(gè)線程間的模式切換相比，所需的工作量是否要少？答：是的，因?yàn)閮蓚€(gè)進(jìn)程間的模式切換要儲(chǔ)存更多的狀態(tài)信息。4.2. 在比較用戶級(jí)線程和內(nèi)核級(jí)線程時(shí)曾指出用戶級(jí)線程的一個(gè)缺點(diǎn)，即當(dāng)一個(gè)用戶級(jí)線程執(zhí)行系統(tǒng)調(diào)用時(shí)，不僅這個(gè)線程被阻塞，而且進(jìn)程中的所有線程都被阻塞。請(qǐng)問(wèn)這是為什么？答：因?yàn)閷?duì)于用戶級(jí)線程來(lái)說(shuō)，一個(gè)進(jìn)程的線程結(jié)構(gòu)對(duì)操作系統(tǒng)是不可見(jiàn)的，而操作系統(tǒng)的調(diào)度是以進(jìn)程為單位的。4.3. 在 OS/2 中，其他操作系統(tǒng)中通用的進(jìn)程概念被分成了三個(gè)獨(dú)立類型的實(shí)體：會(huì)話、進(jìn)程和線程。一個(gè)會(huì)話是一組與用戶接口（鍵盤、顯示器、鼠標(biāo)）相關(guān)聯(lián)的一個(gè)或多個(gè)進(jìn)程。會(huì)話代表了一個(gè)交互式的用戶應(yīng)用程序，如字處理程序或電

35、子表格，這個(gè)概念使得 PC 用戶可以打開一個(gè)以上的應(yīng)用程序，在屏幕上顯示一個(gè)或更多個(gè)窗口。操作系統(tǒng)必須知道哪個(gè)窗口，即哪個(gè)會(huì)話是活躍的，從而把鍵盤和鼠標(biāo)的輸入傳遞個(gè)相應(yīng)的會(huì)話。在任何時(shí)刻，只有一個(gè)會(huì)話在前臺(tái)模式，其他的會(huì)話都在后臺(tái)模式，鍵盤和鼠標(biāo)的所有輸入都發(fā)送給前臺(tái)會(huì)話的一個(gè)進(jìn)程。當(dāng)一個(gè)會(huì)話在前臺(tái)模式時(shí)，執(zhí)行視頻輸出的進(jìn)程直接把它發(fā)送到硬件視頻緩沖區(qū)。當(dāng)一個(gè)會(huì)話在后臺(tái)時(shí)，如果該會(huì)話的任何一個(gè)進(jìn)程的任何一個(gè)線程正在執(zhí)行并產(chǎn)生屏幕輸出，則這個(gè)輸出被送到邏輯視頻緩沖區(qū)；當(dāng)這個(gè)會(huì)話返回前臺(tái)時(shí)，屏幕被更新，為新的前臺(tái)會(huì)話反映出邏輯視頻緩沖區(qū)中的當(dāng)前內(nèi)容。有一種方法可以把OS/2 中與進(jìn)程相關(guān)的概念的數(shù)

36、目從3 個(gè)減少到 2 個(gè)。 刪去會(huì)話， 把用戶接口 （鍵盤、顯示器、鼠標(biāo)）和進(jìn)程關(guān)聯(lián)起來(lái)。這樣，在某一時(shí)刻，只有一個(gè)進(jìn)程處于前臺(tái)模式。為了進(jìn)一步地進(jìn)行構(gòu)造，進(jìn)程可以被劃分成線程。a. 使用這種方法會(huì)喪失什么優(yōu)點(diǎn)？b. 如果繼續(xù)使用這種修改方法，應(yīng)該在哪里分配資源（存儲(chǔ)器、文件等） ：在進(jìn)程級(jí)還是線程級(jí)？答：c. 會(huì)話的使用非常適合個(gè)人計(jì)算機(jī)和工作站對(duì)交互式圖形接口的需求。它為明確圖形輸出和鍵盤/鼠標(biāo)輸入應(yīng)該被關(guān)聯(lián)到什么位置提供了一個(gè)統(tǒng)一的機(jī)制，減輕了操作系統(tǒng)的工作負(fù)擔(dān)。d. 應(yīng)該和其他的進(jìn)程/線程系統(tǒng)一樣，在進(jìn)程級(jí)分配地址空間和文件。4.4. 考慮這樣一個(gè)環(huán)境，用戶級(jí)線程和內(nèi)核級(jí)線程呈一對(duì)一的

37、映射關(guān)系，并且允許進(jìn)程中的一個(gè)或多個(gè)線程產(chǎn)生會(huì)引發(fā)阻塞的系統(tǒng)調(diào)用，而其他線程可以繼續(xù)運(yùn)行。解釋為什么這個(gè)模型可以使多線程程序比在單處理器機(jī)器上的相應(yīng)的單線程程序運(yùn)行速度更快？答：?jiǎn)栴}在于機(jī)器會(huì)花費(fèi)相當(dāng)多的時(shí)間等待 I/O 操作的完成。在一個(gè)多線程程序中，可能一個(gè)內(nèi)核級(jí)線程會(huì)產(chǎn)生引發(fā)阻塞的系統(tǒng)調(diào)用，而其他內(nèi)核級(jí)線程可以繼續(xù)執(zhí)行。而在單處理器機(jī)器上，進(jìn)程則必須阻塞知道所有的系統(tǒng)調(diào)用都可以繼續(xù)運(yùn)行。參考： LEWI964.5. 如果一個(gè)進(jìn)程退出時(shí)，該進(jìn)程的某些線程仍在運(yùn)行，請(qǐng)問(wèn)他們會(huì)繼續(xù)運(yùn)行嗎？答：不會(huì)。當(dāng)一個(gè)進(jìn)程退出時(shí)，會(huì)帶走它的所有東西內(nèi)核級(jí)線程，進(jìn)程結(jié)構(gòu)，存儲(chǔ)空間包括線程。參考： LEWI96

38、4.6. OS/390 主機(jī)操作系統(tǒng)圍繞著地址空間和任務(wù)的概念構(gòu)造。粗略說(shuō)來(lái)，一個(gè)地址空間對(duì)應(yīng)于一個(gè)應(yīng)用程序， 并且或多或少地對(duì)應(yīng)于其他操作系統(tǒng)中的一個(gè)進(jìn)程； 在一個(gè)地址空間中， 可以產(chǎn)生一組任務(wù)，并且它們可以并發(fā)執(zhí)行，這大致對(duì)應(yīng)于多線程的概念。管理任務(wù)結(jié)構(gòu)有兩個(gè)主要的數(shù)據(jù)結(jié)構(gòu)。地址空間控制塊（ ASCB ）含有 OS/390 所需要的關(guān)于一個(gè)地址空間的信息，而不論該地址空間是否在執(zhí)行。 ASCB 中的信息包括分派優(yōu)先級(jí)、分配給該地址空間的實(shí)存和虛存、該地址空間中就緒的任務(wù)數(shù)以及是否每個(gè)都被換出。一個(gè)任務(wù)控制塊（ TCB ）標(biāo)識(shí)一個(gè)正在執(zhí)行的用戶程序，它含有在一個(gè)地址空間中管理該任務(wù)所需要的信

39、息，包括處理器狀態(tài)信息、指向該任務(wù)所涉及到的程序的指針和任務(wù)執(zhí)行結(jié)構(gòu)。 ASCB 是在系統(tǒng)存儲(chǔ)器中保存的全局結(jié)構(gòu)，而TCB 是保存在各自的地址空間中的局部結(jié)構(gòu)。請(qǐng)問(wèn)把控制信息劃分成全局和局部?jī)刹糠钟惺裁春锰?？答：關(guān)于一個(gè)地址空間的盡可能多的信息可以隨地址空間被換出，從而節(jié)約了主存。4.7. 一個(gè)多處理系統(tǒng)有8 個(gè)處理器和 20 個(gè)附加磁帶設(shè)備。 現(xiàn)在有大量的作業(yè)提交給該系統(tǒng)， 完成每個(gè)作業(yè)最多需要4 個(gè)磁帶設(shè)備。假設(shè)每個(gè)作業(yè)開始運(yùn)行時(shí)只需要3 個(gè)磁帶設(shè)備，并且在很長(zhǎng)時(shí)間內(nèi)都只需要這 3 個(gè)設(shè)備，而只是在最后很短的一段時(shí)間內(nèi)需要第 4 個(gè)設(shè)備以完成操作。同時(shí)還假設(shè)這類作 業(yè)源源不斷。a. 假設(shè)操

40、作系統(tǒng)中的調(diào)度器只有當(dāng) 4 個(gè)磁帶設(shè)備都可用時(shí)才開始一個(gè)作業(yè)。 當(dāng)作業(yè)開始時(shí)， 4 個(gè)設(shè) 備立即被分配給它，并且直到作業(yè)完成時(shí)才被釋放。請(qǐng)問(wèn)一次最多可以同時(shí)執(zhí)行幾個(gè)作業(yè)？采 用這種策略，最多有幾個(gè)磁帶設(shè)備可能是空閑的？最少有幾個(gè)？b. 給出另外一種策略，要求其可以提高磁帶設(shè)備的利用率，并且同時(shí)可以避免系統(tǒng)死鎖。分析最 多可以有幾個(gè)作業(yè)同時(shí)執(zhí)行，可能出現(xiàn)的空閑設(shè)備的范圍是多少。答：c. 采用一個(gè)保守的策略，一次最多同時(shí)執(zhí)行20/4=5 個(gè)作業(yè)。由于分配各一個(gè)任務(wù)的磁帶設(shè)備最多同時(shí)只有一個(gè)空閑，所以在同一時(shí)刻最多有5 個(gè)磁帶設(shè)備可能是空閑的。在最好的情況下沒(méi)有磁帶設(shè)備空閑。 b. 為了更好的利用磁

41、設(shè)備，每個(gè)作業(yè)在最初只分配三個(gè)磁帶設(shè)備。第四個(gè)只有的需要的時(shí)候才分配。在這種策略中，最多可以有20/3=6 個(gè)作業(yè)同時(shí)執(zhí)行。最少的空閑設(shè)備數(shù)量為 0 ，最多有 2個(gè)。參考： Advanced Computer Architectrue,K.Hwang,1993.4.8. 在描述 Solaris 用戶級(jí)線程狀態(tài)時(shí)， 曾表明一個(gè)用戶級(jí)線程可能讓位于具有相同優(yōu)先級(jí)的另一個(gè)線程。請(qǐng)問(wèn)，如果有一個(gè)可運(yùn)行的、具有更高優(yōu)先級(jí)的線程，讓位函數(shù)是否還會(huì)導(dǎo)致讓位于具有相同優(yōu)先 級(jí)或更高優(yōu)先級(jí)的線程？ 答：任何一個(gè)可能改變線程優(yōu)先級(jí)或者使更高優(yōu)先級(jí)的線程可運(yùn)行的調(diào)用都會(huì)引起調(diào)度，它會(huì)依次 搶占低優(yōu)先級(jí)的活躍線程。所

42、以，永遠(yuǎn)都不會(huì)存在一個(gè)可運(yùn)行的、具有更高優(yōu)先級(jí)的線程。參考： LEVI96第 5 章 并發(fā)性：互斥和同步5.1答：b.協(xié)同程序read讀卡片，將字符賦給一個(gè)只有一個(gè)字大小的緩沖區(qū)rs然后在賦給squash協(xié)同程。協(xié)同程序Read在每副卡片圖像的后面插入一個(gè)額外的空白。協(xié)同程序squash不需要知道任何關(guān)于輸入的八十個(gè)字符的結(jié)構(gòu)， 它簡(jiǎn)單的查找成對(duì)出現(xiàn)的星號(hào)， 然后將更改夠的字符串經(jīng)由只有一個(gè)字符大小的緩沖sp，傳遞給協(xié)同程序print。最后協(xié)同程序 print簡(jiǎn)單的接受到來(lái)的字符串，并將他們打印在包含125個(gè)字符的行中。5.2 考慮一個(gè)并發(fā)程序，它有兩個(gè)進(jìn)程p 和 q ，定義如下。 A.B.C

43、.D 和 E 是任意的原子語(yǔ)句。假設(shè)住程序執(zhí)行兩個(gè)進(jìn)程的 parbeginVoid p()void q() A; D;B;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+;void main()tally =0;parbegin(total(),total();write(tally);答：a.隨意一看，tally值

44、的范圍好像是落在50,100這個(gè)區(qū)間里，因?yàn)楫?dāng)沒(méi)有互斥時(shí)可以從0直接增加到50.這一基本論點(diǎn)是當(dāng)并發(fā)的運(yùn)行這兩進(jìn)程時(shí),我們不可能得到一個(gè)比連續(xù)執(zhí)行單一某進(jìn)程所得 tally 值還低的一個(gè)最終 tally 值 .但是考慮下面由這兩進(jìn)程按交替順序執(zhí)行載入 ,增加 ,存儲(chǔ)的情況,同時(shí)變更這個(gè)共享變量的取值:1 .進(jìn)程A載入tally值,tally值加到1,在此時(shí)失去處理器(它已經(jīng)增加寄存器的值到1,但是還沒(méi)有存儲(chǔ)這個(gè)值).2 .進(jìn)程B 載入 tally 值(仍然是0),然后運(yùn)行完成49 次增加操作,在它已經(jīng)將49 這個(gè)值存儲(chǔ)給共享變量 tally 后 ,失去處理器控制權(quán) .3 .進(jìn)程A 重新獲得處理

45、器控制權(quán)去完成它的第一次存儲(chǔ)操作(用 1 去代替先前的 49 這個(gè) tally 值 ),此時(shí)被迫立即放棄處理器.4 .進(jìn)程B 重新開始 ,將 1(當(dāng)前的 tally 值)載入到它自己的寄存器中 ,但此時(shí)被迫放棄處理器(注意這是B 的最后一次載入 ).5 .進(jìn)程A 被重新安排開始 ,但這次沒(méi)有被中斷,直到運(yùn)行完成它剩余的 49次載入,增加和存儲(chǔ)操作,結(jié)果是此時(shí) tally 值已經(jīng)是 50.6 .進(jìn)程B 在它終止前完成僅有的最后一次增加和存儲(chǔ)操作.它的寄存器值增至2,同時(shí)存儲(chǔ)這個(gè)值做為這個(gè)共享變量的最終結(jié)果.一些認(rèn)為會(huì)出現(xiàn)低于2 這個(gè)值的結(jié)果,這種情況不會(huì)出現(xiàn).這樣tally 值的正確范圍是2,1

46、00.b.對(duì)一般有N個(gè)進(jìn)程的情況下，tally值的最終范圍是2,N*50,因?yàn)閷?duì)其他所有進(jìn)程來(lái)說(shuō)，從最初開始 運(yùn)行到在第五步完成.但最后都被進(jìn)程B 破壞掉它們的最終結(jié)果.5.4 .忙等待是否總是比阻塞等待效率低(根據(jù)處理器的使用時(shí)間)？請(qǐng)解釋。答：就一般情況來(lái)說(shuō)是對(duì)的, 因?yàn)槊Φ却臒o(wú)用的指令周期.然而,有一種特殊情況,當(dāng)進(jìn)程執(zhí)行到程序的某一點(diǎn)處,在此處要等待直到條件滿足,而正好條件已滿足,此時(shí)忙等待會(huì)立即有結(jié)果,然而阻塞等待會(huì)消耗操作系統(tǒng)資源在換出與換入進(jìn)程上.5.5 考慮下面的程序boolean blocked2;int rurn;void P(int id)While (true) W

47、hile(turn!=id); While(blocked1-!id/*do nothing*/;Turn =id;Void main ()Blocked0=false;Blocked1=false;Turn=0;Parbegin(P(0),P(1);這是【 HYMA66 】中提出的解決互斥問(wèn)題的一種方法。請(qǐng)舉出證明該方法不正確的一個(gè)反例。答：考慮這種情況：此時(shí)turn=0,進(jìn)程P(1)使布爾變量blocked1的值為true,在這時(shí)發(fā)現(xiàn)布爾變量blocked0的值為false,然后P(0)會(huì)將true值賦予blocked0，此時(shí)turn=0,P(0)進(jìn)入臨界區(qū)，P(1)在將1賦值給turn后

48、，也進(jìn)入了臨界區(qū).5.6 解決互斥的另一種軟件方法是lamport的面包店(bakery)算法，之所以起這個(gè)名字，是因?yàn)樗乃枷雭?lái)自于面包店或其他商店中，每個(gè)顧客在到達(dá)時(shí)都得到一個(gè)有編號(hào)的票，并按票號(hào)依次得到服務(wù)，算法如下：Boolean choosingn;Int numbern;While (true)Choosingi=true;Numberi=1+getmax(number,n) ；Choosingi=false;For(int j=0;jn;j+) While (choosingj)While (numberj!=0)&(numberj,j)(numberi,i)/*critical

49、 section*/Numberi=0;/*remainder*/;數(shù)組 choosing 和 number 分別被初始化成false 和 0 ， 每個(gè)數(shù)組的第i 個(gè)元素可以由進(jìn)程i 讀或?qū)懀?但其他進(jìn)程只能讀。符號(hào)(a, b) (c, d)被定義成(a, c) 或(a=c且 bd)A 用文字描述這個(gè)算法。B 說(shuō) 明這個(gè)算法避免了死鎖。C 說(shuō) 明它實(shí)施了互斥。答：a.當(dāng)一個(gè)進(jìn)程希望進(jìn)入臨界區(qū)時(shí)，它被分配一個(gè)票號(hào).分配的票號(hào)是通過(guò)在目前那些等待進(jìn)入臨界區(qū)的進(jìn)程所持票號(hào)和已經(jīng)在臨界區(qū)的進(jìn)程所持票號(hào)比較,所得最大票號(hào)再加1 得到的.有最小票號(hào)的進(jìn)程有最高的優(yōu)先級(jí)進(jìn)入臨界區(qū) .當(dāng)有多個(gè)進(jìn)程擁有同樣的票

50、號(hào)時(shí),擁有最小數(shù)字號(hào)進(jìn)入臨界區(qū).當(dāng)一個(gè)進(jìn)程退出臨界區(qū)時(shí)重新設(shè)置它的票號(hào)為 0.b.如果每個(gè)進(jìn)程被分配唯一的一個(gè)進(jìn)程號(hào)，那么總會(huì)有一個(gè)唯一的，嚴(yán)格的進(jìn)程順序.因此，死鎖可以避免 .c.為了說(shuō)明互斥，我們首先需要證明下面的定理：如果Pi在它的臨界區(qū)，Pk已經(jīng)計(jì)算出來(lái)它的numberk, 并試圖進(jìn)入臨界區(qū),此時(shí)就有下面的關(guān)系式: ( numberi, i ) ( numberk, k ). 為證明定理,定義下面一些時(shí)間量:Tw1:Pi最后一次讀 choosingk,當(dāng)j=k,在它的第一次等待時(shí)，因此我們?cè)?Tw1處有choosingk= false.Tw2:Pi開始它的最后執(zhí)行,當(dāng)j=k,在它的第二

51、次 while循環(huán)時(shí)，因此我們有Tw1 Tw2. Tk1:Pk 在開始 repeat 循環(huán)時(shí) ;Tk2:Pk 完成 numberk 的計(jì)算 ;Tk3: Pk 設(shè)置 choosingk 為 false 時(shí).我們有Tk1Tk2Tk3.因?yàn)樵?Tw1處,choosingk=false,我們要么有 Tw1Tk1,要么有 Tk3Tw1.在第一種，情況中,我們有 numberinumberk,因?yàn)镻i在Pk之前被分配號(hào)碼；這個(gè)滿足定理?xiàng)l件.在第二種情況中，我們有Tk2 Tk3 Tw1 Tw2,因此有Tk2Tw2.這意味著在Tw2時(shí),Pi已經(jīng)讀了當(dāng)前numberk的值.而且，因?yàn)門w2是當(dāng)j=k第 二次 w

52、hile 循環(huán)執(zhí)行發(fā)生的時(shí)刻 ,我們有 (numberi, i ) ( numberk, k), 這樣完成了定理的證明 .現(xiàn)在就很容 易說(shuō)明實(shí)施了互斥.假定Pi 在臨界區(qū) ,Pk 正試圖進(jìn)入臨界區(qū).Pk 將不能進(jìn)入臨界區(qū),因?yàn)樗鼤?huì)發(fā)現(xiàn)numberi不等于 0,并且 ( numberi, i ) ( numberk, k ).5.7 當(dāng)按圖 5.2 的形式使用一個(gè)專門機(jī)器指令提供互斥時(shí)， 對(duì)進(jìn)程在允許訪問(wèn)臨界區(qū)之前必須等待多久沒(méi)有控制。設(shè)計(jì)一個(gè)使用 testset 指令的算法，且保證任何一個(gè)等待進(jìn)入臨界區(qū)的進(jìn)程在n-1 個(gè) turn 內(nèi)進(jìn)入， n是要求訪問(wèn)臨界區(qū)的進(jìn)程數(shù)， turn 是指一個(gè)進(jìn)程

53、離開臨界區(qū)而另一個(gè)進(jìn)程獲準(zhǔn)訪問(wèn)這個(gè)一個(gè)事件。答：以下的程序由 SILB98 提供：var j: 0.n-1;key: boolean; repeat waitingi := true; key := true;while waitingi and key do key := testset(lock); waitingi := false;j := i + 1 mod n;while (j 豐 i) and (not waitingj) do j := j + 1 mod n;if j = i then lock := false else waiting := false; Until這個(gè)算

54、法用最普通的數(shù)據(jù)結(jié)構(gòu)： var waiting: array 0.n T of booleanLock ： boolean 這些數(shù)據(jù)結(jié)構(gòu)被初始化成假的，當(dāng)一個(gè)進(jìn)程離開它的臨界區(qū)，它就搜索 waiting 的循環(huán)隊(duì)列 5.8 考慮下面關(guān)于信號(hào)量的定義：Void semWait(s) If (s.count0) s.count-; Else Place this process in s.queue; Block; 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;Elses.count+; 比較這個(gè)定義和圖 5.3 中的定義， 注意有這樣的一個(gè)區(qū)別： 在前面的定義中， 信號(hào)量永遠(yuǎn)不會(huì)取負(fù)值。當(dāng)在程序中分別使用這兩種定義時(shí)， 其效果有什么不同？也就是說(shuō)， 是否可以在不改變程序意義的前提下， 用一個(gè)定義代替另一個(gè)？答：這兩個(gè)定義是等價(jià)的，在圖 5.3 的定義中，當(dāng)信號(hào)量的值為負(fù)值時(shí)，它的值代表了有多少個(gè)進(jìn)程在等待；在此題中的定義中，雖然你沒(méi)有關(guān)于這方面的信息，但是這兩個(gè)版本的