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

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

1、 第 1 章 計(jì)算機(jī)系統(tǒng)概述 1.1、圖 1.3 中的理想機(jī)器還有兩條 I/O 指令： 0011 = 從 I/O 中載入 AC 0111 = 把 AC 保存到 I/O 中 在這種情況下， 12位地址標(biāo)識一個(gè)特殊的外部設(shè)備。請給出以下程序的執(zhí)行過程（按照圖 1.4 的格式）： 1. 從設(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、2：3－>AC 步驟 3: 5940— >IR ;步驟 4: 3+ 2= 5 — >AC 步驟5: 7006— >IR :步驟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ù) 是并行完成的。 c. MBR 中的值被送入指令寄存器 IR 中。 2. a. 指令寄存器 IR 中的地址部分（ 940）被送入 b. 地址 940 中的值被送入 MBR 中。 c. MBR

3、 中的值被送入 AC 中。 3. a. PC 中的值（ 301）被送入 MAR 中。 b. 地址為 301 的指令的內(nèi)容（值為十六進(jìn)制數(shù) c. MBR 中的值被送入指令寄存器 IR 中。 4. a. 指令寄存器 IR 中的地址部分（ 941 ）被送入 b. 地址 941 中的值被送入 MBR 中。 1940）被送入 MBR ，并且 PC 增 1。這兩個(gè)步驟 MAR 中。 5941 ）被送入 MBR ，并且 PC 增 1 。 MAR 中。 c. AC 中以前的內(nèi)容和地址為 941 的存儲(chǔ)單元中的內(nèi)容相加，結(jié)果保存到 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 中的值被存儲(chǔ)到地址為 941 的存儲(chǔ)單元之中。 1.4、假設(shè)有一個(gè)微處理器產(chǎn)生一個(gè) 16位的地址（例如，假設(shè)程序計(jì)數(shù)器和地址寄存器都是 16位）并且具 有一個(gè) 16 位的數(shù)據(jù)總線。 a?如果連接到一個(gè)16位存儲(chǔ)器上，處理器能夠直接訪問的最大存儲(chǔ)器地址空間為多少？ b?如果連接到一個(gè) 8位存儲(chǔ)器上，

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

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

7、原因。 答案：時(shí)鐘周期=1/ （8MHZ ）= 125ns 總線周期=4X 125 ns= 500ns 每500ns傳輸2比特；因此傳輸速度= 4MB/S 加倍頻率可能意味著采用了新的芯片制造技術(shù)（假設(shè)每個(gè)指令都有相同的時(shí)鐘周期數(shù)） ；加倍外部數(shù) 據(jù)總線， 在芯片數(shù)據(jù)總線驅(qū)動(dòng) /鎖存、總線控制邏輯的修改等方面手段廣泛 （或許更新） 。在第一種方案中， 內(nèi)存芯片的速度要提高一倍 （大約），而不能降低微處理器的速度； 第二種方案中， 內(nèi)存的字長必須加倍， 以便能發(fā)送 /接受 32 位數(shù)量。 1.6、 考慮一個(gè)計(jì)算機(jī)系統(tǒng)，它包含一個(gè) I/O 模塊，用以控制一臺(tái)簡單的鍵盤 /打印機(jī)電傳打字

8、設(shè)備。 CPU 中包含下列寄存器，這些寄存器直接連接到系統(tǒng)總線上： INPR ：輸入寄存器， 8 位 OUTR ：輸出寄存器， 8 位 FGI ：輸入標(biāo)記， 1 位 FGO ：輸出標(biāo)記， 1 位 IEN ：中斷允許， 1 位 I/O 模塊控制從打字機(jī)中輸入擊鍵，并輸出到打印機(jī)中去。打字機(jī)可以把一個(gè)字母數(shù)字符號編碼成一個(gè) 8 位字，也可以把一個(gè) 8 位字解碼成一個(gè)字母數(shù)字符號。當(dāng) 8 位字從打字機(jī)進(jìn)入輸入寄存器時(shí)，輸入標(biāo)記被 置位；當(dāng)打印一個(gè)字時(shí)，輸出標(biāo)記被置位。 a. 描述 CPU 如何使用這 4 個(gè)寄存器實(shí)現(xiàn)與打字機(jī)間的輸入 /輸出。 b. 描述通過使用 IEN ，如何提高

9、執(zhí)行效率？ 答案：a.來源于打字機(jī)的輸入儲(chǔ)存在 INPR中。只有當(dāng)FGI = 0時(shí)，INPR才會(huì)接收來自打字機(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需要傳送數(shù)據(jù)到打字機(jī)時(shí)，它會(huì)檢查 FGO。如果FGO= 0, CPU處于等待。如果 FGO =1 , CPU將把AC的內(nèi)容傳送至 OUTER并把FGO置為0。當(dāng)數(shù)字符號打印后，打字機(jī)將把 FGI 置為 1。 b. （A）描述的過程非常浪費(fèi)。速度遠(yuǎn)高于打字機(jī)的 CPU必須反復(fù)不斷的檢查 FGI和FG

10、O。如果中 斷被使用， 當(dāng)打字機(jī)準(zhǔn)備接收或者發(fā)送數(shù)據(jù)時(shí)， 可以向 CPU 發(fā)出一個(gè)中斷請求。 IEN 計(jì)數(shù)器可以由 CPU 設(shè)置（在程序員的控制下） 。 1.7、 實(shí)際上在所有包括 DMA 模塊的系統(tǒng)中， DMA 訪問主存儲(chǔ)器的優(yōu)先級總是高于處理器訪問主存儲(chǔ)器 的優(yōu)先級。這是為什么 ? 答案：如果一個(gè)處理器在嘗試著讀或者寫存儲(chǔ)器時(shí)被掛起 , 通常除了一點(diǎn)輕微的時(shí)間損耗之外沒有任何危 害。但是，DM可能從或者向設(shè)備（例如磁盤或磁帶）以數(shù)據(jù)流的方式接收或者傳輸數(shù)據(jù)并且這是不能 被打斷的。否則，如果 DM設(shè)備被掛起（拒絕繼續(xù)訪問主存），數(shù)據(jù)可能會(huì)丟失。 1.9、一臺(tái)計(jì)算機(jī)包括一個(gè) CPU和一

11、臺(tái)I/O設(shè)備D，通過一條共享總線連接到主存儲(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í)行速度, 但沒有任何 I/O 指令。 假設(shè) 1 個(gè)處理器周期等于 1 個(gè)總線周期, 現(xiàn)在要在 M 和 D 之間傳送大塊數(shù)據(jù)。 a. 若使用程序控制I/O , I/O每傳送1個(gè)字需要CPU執(zhí)行兩條指令。請估計(jì)通過D的I/O數(shù)據(jù)傳送的最大可 能速度。 b. 如果使用DMA傳送，請估計(jì)傳送速度。 答案：a

12、.處理器只能分配 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í)間，那么這個(gè)值 就是最大的I/O傳輸速率。 1.10、 考慮以下代碼： for ( i = 0 ; i < 20 ; i++) for (j = 0 ; j < 10 ; j++) a[i] = a[i]*j a. 請舉例說明代碼中

13、的空間局部性。 b. 請舉例說明代碼中的時(shí)間局部性。 答案：a.讀取第二條指令是緊跟著讀取第一條指令的。 b.在很短的間歇時(shí)間內(nèi)， a[i]在循環(huán)內(nèi)部被訪問了十次。 1.11、 請將附錄1A中的式(1.1)和式(1.2)推廣到n級存儲(chǔ)器層次中。 答案：定義： Ci =存儲(chǔ)器層次i上每一位的存儲(chǔ)單元平均花銷 Si =存儲(chǔ)器層次i的規(guī)模大小 Ti =存儲(chǔ)器層次i上訪問一個(gè)字所需時(shí)間 Hi = 一個(gè)字在不高于層次i的存儲(chǔ)器上的概率 Bi =把一個(gè)數(shù)據(jù)塊從層次i+1的存儲(chǔ)器上傳輸?shù)綄哟蝘的存儲(chǔ)器上所需時(shí)間 高速緩沖存儲(chǔ)器作為是存儲(chǔ)器層次 1;主存為存儲(chǔ)器層次2;針對所有的N層存儲(chǔ)器

14、層以此類推。 有: 、Ci Si Cs Si i =1 n Ts的引用更復(fù)雜，我們從概率論入手：所期望的值 x=v iPr[x=1]，由此我們可以寫出: i壬 n Ts 八 THi i ± 我們需要清楚如果一個(gè)字在 M1 (緩存)中，那么對它的讀取非?？?。如果這個(gè)字在 M2而不在M1中，那么 數(shù)據(jù)塊需要從M2傳輸?shù)組1中，然后才能讀取。因此， T2 = B什T1 進(jìn)一步，T3 = B 2+T2 = B1+B2+T1 i -1 以此類推：Ti =6 Bj 所以, n i -4 n Ts 二二（BjHJ T「Hi i =2 j d i z! i ± n

15、i」 最后，Ts 二二(BiHJ Ti i=2 j:J 1.12、 考慮一個(gè)存儲(chǔ)器系統(tǒng)，它具有以下參數(shù)： Tc = 100 ns Cc = 0.01 分 /位 Tm = 1200 ns Cm = 0.001 分 / 位 a. 1MB的主存儲(chǔ)器價(jià)格為多少？ b. 使用高速緩沖存儲(chǔ)器技術(shù)， 1MB的主存儲(chǔ)器價(jià)格為多少？ c. 如果有效存取時(shí)間比高速緩沖存儲(chǔ)器存取時(shí)間多 10%，命中率H為多少？ 答案：a.價(jià)格=CmX8X106 = 8XI03 C = $ 80 6 4 b. 價(jià)格=CcX8X10 = 8 W C = $ 800 c. 由等式 1.1 知：1.1 X1 = T

16、1+(1-H)T2 (0.1)(100) = (1-H)(1200) H=1190/1200 1.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è)字的平均存

17、取時(shí)間是多少(單 位為ns)? 答案：有三種情況需要考慮： 字所在的位置 概率 訪問所需時(shí)間(ns) 在緩存中 0.9 20 不在緩存，在主存中 (0.1) (0.6) = 0.06 60+20 = 80 不在緩存也不在主存中 (0.1) ( 0.4) = 0.04 12ms+60+20 = 12,000,080 所以平均訪問時(shí)間是： Avg = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns 1.14、假設(shè)處理器使用一個(gè)棧來管理過程調(diào)用和返回。請問可以取消程序計(jì)數(shù)器而用棧指針代替嗎？ 答案：如果棧只用于

18、保存返回地址?；蛘呷绻麠Ｒ灿糜趥鬟f參數(shù)，這種方案只有當(dāng)棧作為傳遞參數(shù)的控制 單元而非機(jī)器指令時(shí)才成立。這兩種情況下可以取消程序計(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è)使用簡單的循環(huán)法調(diào)度， 并且I/O操作可以與處理器操作重疊。定義以下量： ?時(shí)間周期=完成任務(wù)的實(shí)際時(shí)間 ?吞吐量=每個(gè)時(shí)間周期T內(nèi)平均完成的作業(yè)數(shù)目 ?處理器使用率=處理器

19、活躍(不是處于等待)的時(shí)間的百分比 當(dāng)周期T分別按下列方式分布時(shí)，對 1個(gè)、2個(gè)和4個(gè)同時(shí)發(fā)生的作業(yè)，請計(jì)算這些量： a. 前一般用于I/O,后一半用于處理器。 b. 前四分之一和后四分之一用于 I/O，中間部分用于處理器。 答：(*和(b)的答案相同。盡管處理器活動(dòng)不能重疊，但 I/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í)間要多的程序。處理 器限制的

20、程序則相反。假設(shè)短期調(diào)度算法偏愛那些在近期石油處理器時(shí)間較少的算法，請解釋為什么這個(gè) 算法偏愛 I/O 限制的程序，但是并不是永遠(yuǎn)不受理處理器限制程序所需的處理器時(shí)間？ 受 I/O 限制的程序使用相對較少的處理器時(shí)間，因此更受算法的青睞。然而，受處理器限制的進(jìn)程如 果在足夠長的時(shí)間內(nèi)得不到處理器時(shí)間，同一算法將允許處理器去處理此進(jìn)程，因?yàn)樗罱鼪]有使用過處 理器。這樣，一個(gè)處理器限制的進(jìn)程不會(huì)永遠(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í)間限制策略更有效是因?yàn)樗o所有進(jìn)程一個(gè)較短的處理時(shí)間。批處理 系統(tǒng)關(guān)

21、心的是吞吐量，更少的上下文轉(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)用程序用來調(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 Resource Manager,SRM ），他負(fù)責(zé)地址空間（進(jìn)程）之間的資源分配。 SRM 是的 OS/390 在操作系統(tǒng)中具有特殊性， 沒有任何其他的主機(jī)

22、操作系統(tǒng)，當(dāng)然沒有任何其他類型的操作系統(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è)置了以后的各種性能目標(biāo)作為 SRM 的指南，這會(huì)基 于系統(tǒng)的利用率動(dòng)態(tài)的修改安裝和作業(yè)性能特點(diǎn)。 SRM 依次提供報(bào)告， 允許受過訓(xùn)練的操作員改進(jìn)配置和 參數(shù)設(shè)置，以改善用戶服務(wù)。 現(xiàn)在關(guān)注 SRM 活動(dòng)的一個(gè)實(shí)例。實(shí)存被劃分為成千上萬個(gè)大小相等的塊，稱為幀。每個(gè)幀可以保留一塊 稱為頁的虛存。 SRM 每秒大約接受 20 次控制，并在互相之間以及每個(gè)頁面之

23、間進(jìn)行檢查。如果頁未被引 用或被改變，計(jì)數(shù)器增 1。一段時(shí)間后， SRM 求這些數(shù)據(jù)的平均值，以確定系統(tǒng)中一個(gè)頁面未曾被觸及的 平均秒數(shù)。這樣做的目的是什么？ SRM 將采取什么動(dòng)作？ 操作系統(tǒng)可以查看這些數(shù)據(jù)已確定系統(tǒng)的負(fù)荷，通過減少加在系統(tǒng)上的活躍作業(yè)來保持較高的平均利用率。 典型的平均時(shí)間應(yīng)該是兩分鐘以上，這個(gè)平均時(shí)間看起來很長，其實(shí)并不長。 第 3章 進(jìn)程描述和控制 3.1. 給出操作系統(tǒng)進(jìn)行進(jìn)程管理時(shí)的五種主要活動(dòng)，并簡單描述為什么需要它們。 答：用戶進(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)

24、程創(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)改變 為等待或就緒狀態(tài)。 當(dāng)所需要的資源可用時(shí)， 操作系統(tǒng)需要將它的狀態(tài)變?yōu)檫\(yùn)行態(tài)以使其繼續(xù)執(zhí)行。 提供進(jìn)程的同步機(jī)制。 合作的進(jìn)程可能需要共享數(shù)據(jù)。 對共享數(shù)據(jù)的并行訪問可能會(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ī)制。在多

25、道程序環(huán)境中，多個(gè)進(jìn)程可能會(huì)競爭有限的資源。如果發(fā)生死鎖， 所有的等待進(jìn)程都將永遠(yuǎn)不能由等待狀態(tài)再變?yōu)檫\(yùn)行態(tài)，資源將被浪費(fè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)獲得的某種資源上的操作 完成時(shí)，它處于掛起態(tài)。在許多操作系統(tǒng)中，這兩種狀態(tài)常常放在一起作為阻塞態(tài)，掛起態(tài)使用本 章中給出的定義。請比較這兩組定義的優(yōu)點(diǎn)。 答： [PINK89] 中引用了以下例子來闡述其中阻塞和掛起的定義： 假設(shè)一個(gè)進(jìn)程已經(jīng)執(zhí)行了一段時(shí)間，它需要一個(gè)額外的磁帶設(shè)

26、備來寫出一個(gè)臨時(shí)文件。在它開 始寫磁帶之前，進(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)，等待該磁帶上當(dāng)前所進(jìn)行的寫操作完成。 這種對等待某一設(shè)備的兩種不同原因的區(qū)別，在操作系統(tǒng)組織其工作時(shí)是非常有用的。然而這并不 能表明那些進(jìn)程是換入的，那些進(jìn)程是換出的。后一種區(qū)別是必需的，而且應(yīng)該在進(jìn)程狀態(tài)中以某 種形式表現(xiàn)出來。 3.3. 對于圖3.9（ b）中給出的7狀態(tài)進(jìn)程模型，請仿

27、照圖 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)先級都高。有兩種極端的策略： （1）總是分派一個(gè)處于就緒態(tài)的進(jìn)程，以減少交換； （2 ）總是把機(jī)會(huì)給具有最高優(yōu)先級的進(jìn)程，即 使會(huì)導(dǎo)致在不需要交換時(shí)進(jìn)行交換。請給出一種能均衡考慮優(yōu)先級和性能的中間策略。 答：對于一個(gè)就緒/掛起態(tài)的進(jìn)程，降低一定數(shù)量（如一或兩個(gè)）優(yōu)先級，從而保證只有當(dāng)一個(gè)就緒 /掛

28、起態(tài)的進(jìn)程比就緒態(tài)的進(jìn)程的最高優(yōu)先級還高出幾個(gè)優(yōu)先級時(shí)，它才會(huì)被選做下一個(gè)執(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)換圖，并指出引發(fā)狀態(tài)裝換的原因。 答： a. 每一種等待狀態(tài)都有一個(gè)單獨(dú)的隊(duì)列與其相關(guān)聯(lián)。當(dāng)影響某一等待進(jìn)程的事件發(fā)生時(shí)，把等待 進(jìn)程分成不同的隊(duì)列就減少了定位這一等待進(jìn)程所需的工作量。例如，當(dāng)一個(gè)頁錯(cuò)誤完成時(shí)， 調(diào)度程序就可以在頁錯(cuò)誤等待隊(duì)列中找到等待的進(jìn)程。 b. 在這些狀態(tài)

29、下，允許進(jìn)程被換出只會(huì)使效率更低。例如，當(dāng)發(fā)生頁錯(cuò)誤等待時(shí)，進(jìn)程正在等待 換入一個(gè)頁從而使其可以執(zhí)行，這是將進(jìn)程換出是毫無意義的。 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.6. VAM/VMS

30、操作系統(tǒng)采用了四種處理器訪問模式，以促進(jìn)系統(tǒng)資源在進(jìn)程間的保護(hù)和共享。訪問模 式確定： 指令執(zhí)行特權(quán)：處理器將執(zhí)行什么指令。 內(nèi)存訪問特權(quán)：當(dāng)前指令可能訪問虛擬內(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í)行的過程，例如，一個(gè)用戶程序需要 一個(gè)操作系統(tǒng)服務(wù)。這

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

32、現(xiàn)。 3.7. 在前面習(xí)題中討論的 VMS 方案常常稱為環(huán)狀保護(hù)結(jié)構(gòu)，如圖 3.18所示。 3.3 節(jié)所描述的簡單的內(nèi)核 /用戶方案是一種兩環(huán)結(jié)構(gòu)， [SILB04] 指出了這種方法的問題：環(huán)狀（層次）結(jié)構(gòu)的主要缺點(diǎn)是它不 允許我們實(shí)施須知原理， 特別地，如果一個(gè)對象必須在域 Dj中可訪問，但在域 Dj中不可訪問，則必 須有就j

33、 Di中的 更具有特權(quán)或者要求的安全性更高，那么這種限制就是合理的。然而，通過以下方法卻可以繞 過這種安全策略。一個(gè)運(yùn)行在 Dj中的進(jìn)程可以讀取 Dj中的數(shù)據(jù)，然后把數(shù)據(jù)復(fù)制到 Di中。隨 后， Di 中的進(jìn)程就可以訪問這些信息了。 b. 有一種解決這一問題的方法叫做可信系統(tǒng)，我們將在 16 章中進(jìn)行討論。 3.8. 圖3.7 （b）表明一個(gè)進(jìn)程每次只能在一個(gè)事件隊(duì)列中。 a. 是否能夠允許進(jìn)程同時(shí)等待一個(gè)或多個(gè)事件？請舉例說明。 b. 在這種情況下，如何修改圖中的排隊(duì)結(jié)構(gòu)以支持這個(gè)新特點(diǎn)？ 答： a. 一個(gè)進(jìn)程可能正在處理從另一個(gè)進(jìn)程收到的數(shù)據(jù)并將結(jié)果保存到磁盤上。如果當(dāng)前在

34、另一個(gè)進(jìn) 程中正有數(shù)據(jù)在等待被取走，進(jìn)程就可以繼續(xù)獲得數(shù)據(jù)并處理它。如果前一個(gè)寫磁盤操作已經(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)致寄存器值被保存在與給定的中斷信息相關(guān)聯(lián)的固定單元。在什么情 況下這是一種實(shí)用的技術(shù)？請解釋為什么它通常是不方便的。 答：這種技術(shù)是基于被中斷的進(jìn)程 A

35、 在中斷響應(yīng)之后繼續(xù)執(zhí)行的假設(shè)的。但是，在通常情況下，中 斷可能會(huì)導(dǎo)致另一個(gè)進(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í)需求給 予迅速的反應(yīng)。 第 4 章 線程、對稱多處理和微內(nèi)核 4.1. 一個(gè)進(jìn)程中的多個(gè)線程有以下兩個(gè)優(yōu)點(diǎn)： （ 1）在一個(gè)已有

36、進(jìn)程中創(chuàng)建一個(gè)新線程比創(chuàng)建一個(gè)新進(jìn)程 所需的工作量少； （ 2）在同一個(gè)進(jìn)程中的線程間的通信比較簡單。請問同一個(gè)進(jìn)程中的兩個(gè)線程間 的模式切換與不同進(jìn)程中的兩個(gè)線程間的模式切換相比，所需的工作量是否要少？ 答：是的，因?yàn)閮蓚€(gè)進(jìn)程間的模式切換要儲(chǔ)存更多的狀態(tài)信息。 4.2. 在比較用戶級線程和內(nèi)核級線程時(shí)曾指出用戶級線程的一個(gè)缺點(diǎn)，即當(dāng)一個(gè)用戶級線程執(zhí)行系統(tǒng)調(diào) 用時(shí)，不僅這個(gè)線程被阻塞，而且進(jìn)程中的所有線程都被阻塞。請問這是為什么？ 答：因?yàn)閷τ谟脩艏壘€程來說，一個(gè)進(jìn)程的線程結(jié)構(gòu)對操作系統(tǒng)是不可見的，而操作系統(tǒng)的調(diào)度是 以進(jìn)程為單位的。 4.3. 在 OS/2 中，其他操作系統(tǒng)中通用的進(jìn)程概

37、念被分成了三個(gè)獨(dú)立類型的實(shí)體：會(huì)話、進(jìn)程和線程。一 個(gè)會(huì)話是一組與用戶接口（鍵盤、顯示器、鼠標(biāo)）相關(guān)聯(lián)的一個(gè)或多個(gè)進(jìn)程。會(huì)話代表了一個(gè)交互 式的用戶應(yīng)用程序，如字處理程序或電子表格，這個(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è)線程正

38、在執(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ù)目從 3 個(gè)減少到 2 個(gè)。刪去會(huì)話， 把用戶接口 （鍵 盤、顯示器、鼠標(biāo)）和進(jìn)程關(guān)聯(lián)起來。這樣，在某一時(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)程級還是線程級？ 答： a. 會(huì)話的使用非常適合個(gè)人計(jì)算機(jī)和工作站對交互式圖形接口的需求。它為明確圖形輸出

39、和鍵盤 / 鼠標(biāo)輸入應(yīng)該被關(guān)聯(lián)到什么位置提供了一個(gè)統(tǒng)一的機(jī)制，減輕了操作系統(tǒng)的工作負(fù)擔(dān)。 b. 應(yīng)該和其他的進(jìn)程 /線程系統(tǒng)一樣，在進(jìn)程級分配地址空間和文件。 4.4. 考慮這樣一個(gè)環(huán)境，用戶級線程和內(nèi)核級線程呈一對一的映射關(guān)系，并且允許進(jìn)程中的一個(gè)或多個(gè) 線程產(chǎn)生會(huì)引發(fā)阻塞的系統(tǒng)調(diào)用，而其他線程可以繼續(xù)運(yùn)行。解釋為什么這個(gè)模型可以使多線程程 序比在單處理器機(jī)器上的相應(yīng)的單線程程序運(yùn)行速度更快？ 答：問題在于機(jī)器會(huì)花費(fèi)相當(dāng)多的時(shí)間等待 I/O 操作的完成。在一個(gè)多線程程序中，可能一個(gè)內(nèi)核 級線程會(huì)產(chǎn)生引發(fā)阻塞的系統(tǒng)調(diào)用，而其他內(nèi)核級線程可以繼續(xù)執(zhí)行。而在單處理器機(jī)器上，進(jìn)程 則必須阻塞知道

40、所有的系統(tǒng)調(diào)用都可以繼續(xù)運(yùn)行。參考： [LEWI96] 4.5. 如果一個(gè)進(jìn)程退出時(shí)，該進(jìn)程的某些線程仍在運(yùn)行，請問他們會(huì)繼續(xù)運(yùn)行嗎？ 答：不會(huì)。當(dāng)一個(gè)進(jìn)程退出時(shí)，會(huì)帶走它的所有東西——內(nèi)核級線程，進(jìn)程結(jié)構(gòu)，存儲(chǔ)空間——包 括線程。參考： [LEWI96] 4.6. OS/390 主機(jī)操作系統(tǒng)圍繞著地址空間和任務(wù)的概念構(gòu)造。粗略說來，一個(gè)地址空間對應(yīng)于一個(gè)應(yīng)用 程序，并且或多或少地對應(yīng)于其他操作系統(tǒng)中的一個(gè)進(jìn)程； 在一個(gè)地址空間中， 可以產(chǎn)生一組任務(wù)， 并且它們可以并發(fā)執(zhí)行，這大致對應(yīng)于多線程的概念。管理任務(wù)結(jié)構(gòu)有兩個(gè)主要的數(shù)據(jù)結(jié)構(gòu)。地址 空間控制塊（ ASCB ）含有 OS/390 所需

41、要的關(guān)于一個(gè)地址空間的信息，而不論該地址空間是否在執(zhí) 行。 ASCB 中的信息包括分派優(yōu)先級、分配給該地址空間的實(shí)存和虛存、該地址空間中就緒的任務(wù) 數(shù)以及是否每個(gè)都被換出。一個(gè)任務(wù)控制塊（ TCB ）標(biāo)識一個(gè)正在執(zhí)行的用戶程序，它含有在一個(gè) 地址空間中管理該任務(wù)所需要的信息，包括處理器狀態(tài)信息、指向該任務(wù)所涉及到的程序的指針和 任務(wù)執(zhí)行結(jié)構(gòu)。 ASCB 是在系統(tǒng)存儲(chǔ)器中保存的全局結(jié)構(gòu)，而 TCB 是保存在各自的地址空間中的局 部結(jié)構(gòu)。請問把控制信息劃分成全局和局部兩部分有什么好處？ 答：關(guān)于一個(gè)地址空間的盡可能多的信息可以隨地址空間被換出，從而節(jié)約了主存。 4.7. 一個(gè)多處理系統(tǒng)有 8

42、 個(gè)處理器和 20 個(gè)附加磁帶設(shè)備。 現(xiàn)在有大量的作業(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í)還假設(shè)這類作 業(yè)源源不斷。 a. 假設(shè)操作系統(tǒng)中的調(diào)度器只有當(dāng) 4 個(gè)磁帶設(shè)備都可用時(shí)才開始一個(gè)作業(yè)。 當(dāng)作業(yè)開始時(shí)， 4 個(gè)設(shè) 備立即被分配給它，并且直到作業(yè)完成時(shí)才被釋放。請問一次最多可以同時(shí)執(zhí)行幾個(gè)作業(yè)？采 用這種策略，最多有幾個(gè)磁帶設(shè)備可能是空閑的？最少有幾個(gè)？ b. 給出另外一種策略，要求其可以提高磁帶設(shè)備的利用率，并且同時(shí)

43、可以避免系統(tǒng)死鎖。分析最 多可以有幾個(gè)作業(yè)同時(shí)執(zhí)行，可能出現(xiàn)的空閑設(shè)備的范圍是多少。 答： a. 采用一個(gè)保守的策略，一次最多同時(shí)執(zhí)行 20/4=5 個(gè)作業(yè)。由于分配各一個(gè)任務(wù)的磁帶設(shè)備最多 同時(shí)只有一個(gè)空閑，所以在同一時(shí)刻最多有 5 個(gè)磁帶設(shè)備可能是空閑的。在最好的情況下沒有 磁帶設(shè)備空閑。 b. 為了更好的利用磁設(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.

44、8. 在描述 Solaris 用戶級線程狀態(tài)時(shí)， 曾表明一個(gè)用戶級線程可能讓位于具有相同優(yōu)先級的另一個(gè)線程。 請問，如果有一個(gè)可運(yùn)行的、具有更高優(yōu)先級的線程，讓位函數(shù)是否還會(huì)導(dǎo)致讓位于具有相同優(yōu)先 級或更高優(yōu)先級的線程？ 答：任何一個(gè)可能改變線程優(yōu)先級或者使更高優(yōu)先級的線程可運(yùn)行的調(diào)用都會(huì)引起調(diào)度，它會(huì)依次 搶占低優(yōu)先級的活躍線程。所以，永遠(yuǎn)都不會(huì)存在一個(gè)可運(yùn)行的、具有更高優(yōu)先級的線程。參考： [LEVI96] 第 5 章 并發(fā)性：互斥和同步 5.1 答：b.協(xié)同程序read讀卡片，將字符賦給一個(gè)只有一個(gè)字大小的緩沖區(qū) rs然后在賦給squash協(xié)同程。協(xié) 同程序Read在每副卡片圖像

45、的后面插入一個(gè)額外的空白。協(xié)同程序 squash不需要知道任何關(guān)于輸入的八 十個(gè)字符的結(jié)構(gòu)， 它簡單的查找成對出現(xiàn)的星號， 然后將更改夠的字符串經(jīng)由只有一個(gè)字符大小的緩沖 sp， 傳遞給協(xié)同程序 print。最后協(xié)同程序 print簡單的接受到來的字符串，并將他們打印在包含 125個(gè)字符的 行中。 5.2.考慮一個(gè)并發(fā)程序，它有兩個(gè)進(jìn)程 p和q，定義如下。A.B.C.D和E是任意的原子語句。假設(shè)住程序 執(zhí)行兩個(gè)進(jìn)程的 parbegin Void p() void q() { A; { D; B; E; C; } } 答： ABCDE;ABDCE;ABDEC;ADBCE;ADB

46、EC;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值的范圍好像是落在[50,100]這個(gè)區(qū)間里，因?yàn)楫?dāng)沒有互斥時(shí)可以從 0直接增加到50. 這一基本論點(diǎn)是當(dāng)并發(fā)的

47、運(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,但是還沒有存儲(chǔ) 這個(gè)值 ). 2. 進(jìn)程 B 載入 tally 值(仍然是 0),然后運(yùn)行完成 49 次增加操作 ,在它已經(jīng)將 49 這個(gè)值存儲(chǔ)給共享變 量 tally 后 ,失去處理器控制權(quán) . 3. 進(jìn)程 A 重新獲得處理器控制權(quán)去完成它的第一次存儲(chǔ)操作 (用 1 去代替先前的 49

48、這個(gè) tally 值), 此時(shí)被迫立即放棄處理器 . 4進(jìn)程B重新開始，將 1(當(dāng)前的tally值)載入到它自己的寄存器中，但此時(shí)被迫放棄處理器(注意這是 B 的最后一次載入 ). 5. 進(jìn)程 A 被重新安排開始 ,但這次沒有被中斷 ,直到運(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,100]. b?對一般

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

50、int id) { While (true) { While(turn!=id); { While(blocked[1-!id] /*do nothing*/; Turn =id; Void main () { Blocked[0]=false; Blocked[1]=false; Turn=0; Parbegin(P(0),P(1)); } 這是【 HYMA66 】中提出的解決互斥問題的一種方法。請舉出證明該方法不正確的一個(gè)反例。 答：考慮這種情況：此時(shí)turn=O,進(jìn)程P(1)使布爾變量blocked[1]的值為true,在這時(shí)發(fā)現(xiàn)布爾變量 block

51、ed[0] 的值為false，然后P(0)會(huì)將true值賦予blocked[0] ，此時(shí)turn=0,P(0)進(jìn)入臨界區(qū),P(1)在將1賦值給turn后也進(jìn)入了臨界區(qū). 5.6解決互斥的另一種軟件方法是 lamport的面包店(bakery)算法，之所以起這個(gè)名字，是因?yàn)樗乃枷? 來自于面包店或其他商店中，每個(gè)顧客在到達(dá)時(shí)都得到一個(gè)有編號的票，并按票號依次得到服務(wù)，算法如 下： Boolean choosing[n]; Int number[n]; While (true) { Choosing[i]=true; Number[i]=1+getmax(number[],n

52、) ； Choosing[i]=false; For(int j=0;j

53、個(gè)算法。 B ?說明這個(gè)算法避免了死鎖。 C.說明它實(shí)施了互斥。 答：a.當(dāng)一個(gè)進(jìn)程希望進(jìn)入臨界區(qū)時(shí)，它被分配一個(gè)票號.分配的票號是通過在目前那些等待進(jìn)入臨界區(qū)的進(jìn) 程所持票號和已經(jīng)在臨界區(qū)的進(jìn)程所持票號比較 ,所得最大票號再加 1 得到的 .有最小票號的進(jìn)程有最高的 優(yōu)先級進(jìn)入臨界區(qū) .當(dāng)有多個(gè)進(jìn)程擁有同樣的票號時(shí) ,擁有最小數(shù)字號進(jìn)入臨界區(qū) .當(dāng)一個(gè)進(jìn)程退出臨界區(qū)時(shí) 重新設(shè)置它的票號為 0. b. 如果每個(gè)進(jìn)程被分配唯一的一個(gè)進(jìn)程號 ，那么總會(huì)有一個(gè)唯一的，嚴(yán)格的進(jìn)程順序.因此,死鎖可以 避免 . c. 為了說明互斥，我們首先需要證明下面的定理 ：如果Pi在它的臨界區(qū),Pk

54、已經(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. 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] 為

55、false 時(shí) .我們有 Tk1

56、實(shí)施了互斥 ?假定 Pi 在臨界區(qū) ,Pk 正試圖進(jìn)入臨界區(qū) ?Pk 將不能進(jìn)入臨界區(qū) ,因?yàn)樗鼤?huì)發(fā)現(xiàn) number[i] 不等于 0,并且(number[i], i ) < ( number[k], k ). 5.7當(dāng)按圖5.2的形式使用一個(gè)專門機(jī)器指令提供互斥時(shí)， 對進(jìn)程在允許訪問臨界區(qū)之前必須等待多久沒有 控制。設(shè)計(jì)一個(gè)使用 testset 指令的算法，且保證任何一個(gè)等待進(jìn)入臨界區(qū)的進(jìn)程在 n-1 個(gè) turn 內(nèi)進(jìn)入， n 是要求訪問臨界區(qū)的進(jìn)程數(shù)， turn 是指一個(gè)進(jìn)程離開臨界區(qū)而另一個(gè)進(jìn)程獲準(zhǔn)訪問這個(gè)一個(gè)事件。 答：以下的程序由 [SILB98] 提供： var j: 0

57、.. 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 (not wait in g[j]) do j := j + 1 mod n; if j = i then lock := false else waiting := false; < remai

58、nder section > Until 這個(gè)算法用最普通的數(shù)據(jù)結(jié)構(gòu)： var waiti ng: array [0..n T] of boolea n Lock ： boolean 這些數(shù)據(jù)結(jié)構(gòu)被初始化成假的，當(dāng)一個(gè)進(jìn)程離開它的臨界區(qū)，它就搜索 waiting 的循環(huán)隊(duì)列 5.8 考慮下面關(guān)于信號量的定義： Void semWait(s) { If (s.count>0) { s.count--; } Else { Place this process in s.queue; Block; Void semSignal(s) { If (there is a

59、t liast one process blocked on semaphore) { Remove a process P from s.queue; Place process P on ready list; } Else s.count++; } 比較這個(gè)定義和圖 5.3 中的定義， 注意有這樣的一個(gè)區(qū)別： 在前面的定義中， 信號量永遠(yuǎn)不會(huì)取負(fù)值。 當(dāng)在程序中分別使用這兩種定義時(shí)， 其效果有什么不同？也就是說， 是否可以在不改變程序意義的前提下， 用一個(gè)定義代替另一個(gè)？ 答：這兩個(gè)定義是等價(jià)的，在圖 5.3 的定義中，當(dāng)信號量的值為負(fù)值時(shí)，它的值代表了有多少個(gè)進(jìn)程 在等

60、待；在此題中的定義中，雖然你沒有關(guān)于這方面的信息，但是這兩個(gè)版本的函數(shù)是一樣的。 5.9 可以用二元信號量實(shí)現(xiàn)一般信號量。 我們使用 semWaitB 操作和 semSignalB 操作以及兩個(gè)二元信號 量 delay 和 mutex ?？紤]下面的代碼 Void semWait(semaphor s) { semWaitB(mutex); s--; if (s<0) { semSignalB(mutex); semWaitB(delay); } Else Semsignalb(mutex) } Void semSignal(semaphore s); { semW

61、aitB(mutex); s++; if(s<=0) semSignalB(delay); semSignalB(mutex); } 最初。 S 被設(shè)置成期待的信號量值，每個(gè) semwait 操作將信號量減 1 ，每個(gè) semsignal 操作將信號量加 1. 二元信號量 mutex 被初始化成 1 ，確保在更新在更新 s 時(shí)保證互斥，二元信號量 delay 被初始化成 0 ，用 于掛起進(jìn)程， 上面的程序有一個(gè)缺點(diǎn)，證明這個(gè)缺點(diǎn)，并提出解決方案。提示：假設(shè)兩個(gè)進(jìn)程，每個(gè)都在 s 初始化 為0時(shí)調(diào)用semwait (s),當(dāng)?shù)谝粋€(gè)剛剛執(zhí)行了 semsignalb (mutex )但還

62、沒有執(zhí)行 semwaitb (delay ), 第二個(gè)調(diào)用 semwait ( s )并到達(dá)同一點(diǎn)?，F(xiàn)在需要做的就是移動(dòng)程序的一行 . 答：假設(shè)兩個(gè)進(jìn)程，每個(gè)都在s被初始化成0時(shí)調(diào)用semWait (s),當(dāng)?shù)谝粋€(gè)剛執(zhí)行了 semSignalB (mutex )但還沒有執(zhí)行 semWaitB (delay )時(shí)，第二個(gè)調(diào)用 semWait (s)并到達(dá)同一點(diǎn)。 因?yàn)閟=-2 mutex 沒有鎖定，假如有另外兩個(gè)進(jìn)程同時(shí)成功的調(diào)用 semSignal (s)，他們接著就會(huì)調(diào)用 semsignalb (delay )， 但是第二個(gè) semsignalb 沒有被定義。 解決方法就是移動(dòng) se

63、mWait 程序中 end 前的 else 一行到 semSignal 程序中最后一行之前。因此 semWait 中的最后一個(gè) semSignalB(mutex) 變成無條件的， semSignal 中的 semSignalb(mutex) 變成了有 條件的。 5.10 1978 年， dijkstra 提出了一個(gè)推測，即使用有限數(shù)目的弱信號量，沒有一種解決互斥的方案，使用于 數(shù)目未知但有限的進(jìn)程且可以避免饑餓。 1979 年， j.m.morris 提出 了一個(gè)使用三個(gè)弱信號量的算法，反 駁了這個(gè)推測。算法的行為可描述如下，如果一個(gè)或多個(gè)進(jìn)程正在 semwait (s )操作上等待，另一個(gè)

64、進(jìn) 程正在執(zhí)行 semsignal (s )，則信號量 s 的值未被修改，一個(gè)等待進(jìn)程被解除阻塞，并且這并不取決于 semwait (s)。除了這三個(gè)信號量外，算法使用兩個(gè)非負(fù)整數(shù)變量，作為在算法特定區(qū)域的進(jìn)程的計(jì)數(shù)器。 因此，信號量 A 和 B 被初始化為 1，而信號量 M 和計(jì)數(shù)器 NA ， NM 被初始化成 0.一個(gè)試圖進(jìn)入臨界區(qū)的 進(jìn)程必須通過兩個(gè)分別由信號量 A 和 M 表示路障，計(jì)數(shù)器 NA 和 NM 分別含有準(zhǔn)備通過路障 A 以及通過 路障A但還沒有通過路障 M的進(jìn)程數(shù)。在協(xié)議的第二部分，在 M上阻塞的NM個(gè)進(jìn)程將使用類似于第一 部分的串聯(lián)技術(shù)，依次進(jìn)入他們的臨界區(qū)，定義一個(gè)算

65、法實(shí)現(xiàn)上面的描述。 答：這個(gè)程序由 [RAYN86] 提供： var a, b, m: semaphore; na, nm: 0 … ; a := 1; b := 1; m := 0; na := 0; nm := 0; semWait(b); na J na + 1; semSignal(b); semWait(a); nm J nm + 1; semwait(b); na j na - 1; if na = 0 then semSignal(b); semSignal(m) else semSignal(b); semSignal(a) endif; semWait(

66、m); nm J nm - 1; ; if nm = 0 then semSignal(a) else semSignal(m) endif; 5.11 下面的問題曾被用于一個(gè)測試中： 侏羅紀(jì)公園有一個(gè)恐龍博物館和一個(gè)公園， 有 m 個(gè)旅客和 n 輛車， 每輛車只能容納一名旅客。 旅客在博物 館逛了一會(huì)兒， 然后派對乘坐旅客車。 當(dāng)一輛車可用時(shí)， 它載入一名旅客， 然后繞公園行駛?cè)我忾L的時(shí)間。 如果 n 輛車都已被旅客乘坐游玩，則想坐車的旅客需要等待；如果一輛車已經(jīng)就緒，但沒有旅客等待，那 么這輛車等待。 使用信號量同步 m 個(gè)旅客進(jìn)程和 n 個(gè)進(jìn)程。 下面的代碼框架是在教室的地板上發(fā)現(xiàn)的。 忽 略語法錯(cuò)誤和丟掉的變量聲明，請判定它是否正確。注意， p 和 v 分別對應(yīng)于 semwait 和 semsignal 。 Resource Jurassic_Park() Sem car_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0 Process passenger(i: