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

1、52 / 54第 1 章 計算機系統(tǒng)概述1.1、 圖 1.3 中的理想機器還有兩條I/O 指令：0011 = 從 I/O 中載入AC0111 = 把 AC 保存到I/O 中1.4 的格式） ：在這種情況下， 12 位地址標(biāo)識一個特殊的外部設(shè)備。請給出以下程序的執(zhí)行過程（按照圖1. 從設(shè)備 5 中載入 AC 。2. 加上存儲器單元940 的內(nèi)容。3. 把 AC 保存到設(shè)備 6 中。假設(shè)從設(shè)備5 中取到的下一個值為 3940 單元中的值為 2。答案：存儲器（ 16 進制內(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 步來描述圖 1.4 中的程序執(zhí)行情況，請使用 MAR 和 MBR 擴充這個描述。答案： 1. a. PC 中包含第一條指令的地址300 ，該指令的內(nèi)容被送入 MAR 中。b. 地址為 300 的指令的內(nèi)容（值為十六進制數(shù)1940）被送入MBR ，并且 PC 增 1。這兩個步驟是并行完成的。c. MBR 中的值被送入指令寄存器IR 中。2. a. 指令寄存器 IR 中的地址部分（ 940 ）被送入 MAR 中。b. 地址 940 中的值被送入 MBR 中。c. MBR

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

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

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

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

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

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

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

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

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

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

13、儲器上的概率把一個數(shù)據(jù)塊從層次i+1的存儲器上傳輸?shù)綄哟蝘高速緩沖存儲器作為是存儲器層次1;主存為存儲器層次的存儲器上所需時間2;針對所有的N層存儲器層以此類推。 有:nCi SiCJ1CSnSi i 1nTs的引用更復(fù)雜，我們從概率論入手：所期望的值x iPrx 1,由此我們可以寫出:i 1n TsTiHii 1我們需要清楚如果一個字在 M1 (緩存)中，那么對它的讀取非?？?。如果這個字在M2而不在M1中，那么數(shù)據(jù)塊需要從M2傳輸?shù)組1中，然后才能讀取。因此，T2= B1+T1進一步，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、 考慮一個存儲器系統(tǒng)，它具有以下參數(shù)：Tc = 100 nsCc = 0.01 分/位Tm = 1200 nsCm = 0.001 分/位a.1MB的主存儲器價格為多少？ b.使用高速緩沖存儲器技術(shù)，1MB的主存儲器價格為多少？c.如果有效存取時間比高速緩沖存儲器存取時間多10% ,命中率H為多少？答案：a.價格=CmX8X106 = 8X103 0 = $80 b.價格 = 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、 一臺計算機包括包括高速緩沖存儲器、主存儲器和一個用做虛擬存儲器的磁盤。如果要存取的字在 高速緩沖存儲器中，存取它需要20ns；如果該字在主存儲器中而不在高速緩沖存儲器中，把它載入高速緩沖存儲器需要 60ns (包括最初檢查高速緩沖存儲器的時間)，然后再重新開始存??；如果該字不在主存儲器中，從磁盤中取到內(nèi)存需要12ms,接著復(fù)制到高速緩沖存儲器中還需要60ns,再重新開始存取。高速緩沖存儲器的命中率為0.9,主存儲器的命中率為0.6,則該系統(tǒng)中存取一個字的平均存取時間是多少(單位為ns) ?答案：有三種情況需要考

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

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

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

19、的處理器時間，因此更受算法的青睞。然而，受處理器限制的進程如果在足夠長的時間內(nèi)得不到處理器時間，同一算法將允許處理器去處理此進程，因為它最近沒有使用過處理器。這樣，一個處理器限制的進程不會永遠得不到處理器。2.3 請對優(yōu)化分時系統(tǒng)的調(diào)度策略和用于優(yōu)化多道程序批處理系統(tǒng)的調(diào)度策略進行比較。分時系統(tǒng)關(guān)注的是輪轉(zhuǎn)時間，時間限制策略更有效是因為它給所有進程一個較短的處理時間。批處理系統(tǒng)關(guān)心的是吞吐量，更少的上下文轉(zhuǎn)換和更多的進程處理時間。因此，最小的上下文轉(zhuǎn)換最高效。2.4 系統(tǒng)調(diào)用的目的是什么?如何實現(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、程序用來調(diào)用一個由操作系統(tǒng)提供的函數(shù)。通常情況下，系統(tǒng)調(diào)用最終轉(zhuǎn)換成在內(nèi)核模式下的系統(tǒng)程序。2.5 在 IBM 的主機操作系統(tǒng)OS/390 中，內(nèi)核中的一個重要模塊是系統(tǒng)資源管理程序（ System ResourceManager,SRM） ，他負責(zé)地址空間（進程）之間的資源分配。 SRM 是的 OS/390 在操作系統(tǒng)中具有特殊性，沒有任何其他的主機操作系統(tǒng)，當(dāng)然沒有任何其他類型的操作系統(tǒng)可以比得上SRM 所實現(xiàn)的功能。資源的概念包括處理器、實存和 I/O 通道， SRM 累計處理器、 I/O 通道和各種重要數(shù)據(jù)結(jié)構(gòu)的利用率，它的目標(biāo)是基于性能監(jiān)視和分析提供最優(yōu)的性能，其安裝設(shè)置了以后的各種

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

22、均利用率。典型的平均時間應(yīng)該是兩分鐘以上，這個平均時間看起來很長，其實并不長。第 3 章 進程描述和控制3.1. 給出操作系統(tǒng)進行進程管理時的五種主要活動，并簡單描述為什么需要它們。答：用戶進程和系統(tǒng)進程創(chuàng)建及刪除。系統(tǒng)中的進程可以為信息共享、運算加速、模塊化和方便并發(fā)地執(zhí)行。而并發(fā)執(zhí)行需要進程的創(chuàng)建和刪除機制。當(dāng)進程創(chuàng)建或者運行時分配給它需要的資源。當(dāng)進程終止時，操作系統(tǒng)需要收回任何可以重新利用的資源。進程的暫停和繼續(xù)執(zhí)行。在進程調(diào)度中，當(dāng)進程在等待某些資源時，操作系統(tǒng)需要將它的狀態(tài)改變?yōu)榈却蚓途w狀態(tài)。 當(dāng)所需要的資源可用時， 操作系統(tǒng)需要將它的狀態(tài)變?yōu)檫\行態(tài)以使其繼續(xù)執(zhí)行。提供進程的同步

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

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

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

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

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

28、6. VAM/VMS操作系統(tǒng)采用了四種處理器訪問模式，以促進系統(tǒng)資源在進程間的保護和共享。訪問模 式確定：指令執(zhí)行特權(quán)：處理器將執(zhí)行什么指令。內(nèi)存訪問特權(quán)：當(dāng)前指令可能訪問虛擬內(nèi)存中的哪個單元。四種模式如下：內(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)試器之類的實用程序。在較少特權(quán)模式執(zhí)行的進程通常需要調(diào)用在較多特權(quán)模式下執(zhí)行的過程，例如，一個用戶程序需要一個操作系統(tǒng)服務(wù)。這個調(diào)用通過

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、.D 和 E 是任意的原子語句。假設(shè)住程序執(zhí)行兩個進程的 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這個區(qū)間里，因為當(dāng)沒有互斥時可以從0直接增加到50.這一基本論點是當(dāng)并發(fā)的運行這兩進程時,我們不可能得到一個比連續(xù)執(zhí)行單一某進程所得 tally 值還低的一個最終 tally 值 .但是考慮下面由這兩進程按交替順序執(zhí)行載入 ,增加 ,存儲的情況,同時變更這個共享變量的取值:1 .進程A載入tally值,tally值加到1,在此時失去處理器(它已經(jīng)增加寄存器的值到1,但是還沒有存儲這個值).2 .進程B 載入 tally 值(仍然是0),然后運行完成49 次增加操作,在它已經(jīng)將49 這個值存儲給共享變量 tally 后 ,失去處理器控制權(quán) .3 .進程A 重新獲得處理

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

46、00.b.對一般有N個進程的情況下，tally值的最終范圍是2,N*50,因為對其他所有進程來說，從最初開始 運行到在第五步完成.但最后都被進程B 破壞掉它們的最終結(jié)果.5.4 .忙等待是否總是比阻塞等待效率低(根據(jù)處理器的使用時間)？請解釋。答：就一般情況來說是對的, 因為忙等待消耗無用的指令周期.然而,有一種特殊情況,當(dāng)進程執(zhí)行到程序的某一點處,在此處要等待直到條件滿足,而正好條件已滿足,此時忙等待會立即有結(jié)果,然而阻塞等待會消耗操作系統(tǒng)資源在換出與換入進程上.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 】中提出的解決互斥問題的一種方法。請舉出證明該方法不正確的一個反例。答：考慮這種情況：此時turn=0,進程P(1)使布爾變量blocked1的值為true,在這時發(fā)現(xiàn)布爾變量blocked0的值為false,然后P(0)會將true值賦予blocked0，此時turn=0,P(0)進入臨界區(qū)，P(1)在將1賦值給turn后

48、，也進入了臨界區(qū).5.6 解決互斥的另一種軟件方法是lamport的面包店(bakery)算法，之所以起這個名字，是因為它的思想來自于面包店或其他商店中，每個顧客在到達時都得到一個有編號的票，并按票號依次得到服務(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 ， 每個數(shù)組的第i 個元素可以由進程i 讀或?qū)懀?但其他進程只能讀。符號(a, b) (c, d)被定義成(a, c) 或(a=c且 bd)A 用文字描述這個算法。B 說 明這個算法避免了死鎖。C 說 明它實施了互斥。答：a.當(dāng)一個進程希望進入臨界區(qū)時，它被分配一個票號.分配的票號是通過在目前那些等待進入臨界區(qū)的進程所持票號和已經(jīng)在臨界區(qū)的進程所持票號比較,所得最大票號再加1 得到的.有最小票號的進程有最高的優(yōu)先級進入臨界區(qū) .當(dāng)有多個進程擁有同樣的票

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

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

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

53、離開臨界區(qū)而另一個進程獲準(zhǔn)訪問這個一個事件。答：以下的程序由 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這個算

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