1、第1章 計算機系統概述1.1、圖1.3中的理想機器還有兩條I/O指令： 0011 = 從I/O中載入AC 0111 = 把AC保存到I/O中在這種情況下，12位地址標識一個特殊的外部設備。請給出以下程序的執(zhí)行過程（按照圖1.4的格式）：1. 從設備5中載入AC。2. 加上存儲器單元940的內容。3. 把AC保存到設備6中。假設從設備5中取到的下一個值為3940單元中的值為2。答案：存儲器（16進制內容）：300：3005；301：5940；302：7006 步驟1：3005>IR；步驟2：3>AC 步驟3：5940>IR；步驟4：325>AC 步驟5：7006>I

2、R：步驟6：AC>設備 61.2、本章中用6步來描述圖1.4中的程序執(zhí)行情況，請使用MAR和MBR擴充這個描述。答案：1. a. PC中包含第一條指令的地址300，該指令的內容被送入MAR中。 b. 地址為300的指令的內容（值為十六進制數1940）被送入MBR，并且PC增1。這兩個步驟是并行完成的。 c. MBR中的值被送入指令寄存器IR中。 2. a. 指令寄存器IR中的地址部分（940）被送入MAR中。 b. 地址940中的值被送入MBR中。 c. MBR中的值被送入AC中。 3. a. PC中的值（301）被送入MAR中。 b. 地址為301的指令的內容（值為十六進制數5941）

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

4、、假設有一個微處理器產生一個16位的地址（例如，假設程序計數器和地址寄存器都是16位）并且具有一個16位的數據總線。a.如果連接到一個16位存儲器上，處理器能夠直接訪問的最大存儲器地址空間為多少？b.如果連接到一個8位存儲器上，處理器能夠直接訪問的最大存儲器地址空間為多少？c.處理訪問一個獨立的I/O空間需要哪些結構特征？d.如果輸入指令和輸出指令可以表示8位I/O端口號，這個微處理器可以支持多少8位I/O端口？答案：對于(a)和(b)兩種情況，微處理器可以直接訪問的最大存儲器地址空間為216 = 64K bytes；唯一的區(qū)別是8位存儲器每次訪問傳輸1個字節(jié)，而16位存儲器每次訪問可以傳輸一

5、個字節(jié)或者一個16位的字。對于(c)情況，特殊的輸入和輸出指令是必要的，這些指令的執(zhí)行體會產生特殊的“I/O信號”（有別于“存儲器信號”，這些信號由存儲器類型指令的執(zhí)行體產生）；在最小狀態(tài)下，一個附加的輸出針腳將用來傳輸新的信號。對于(d)情況，它支持28 = 256個輸入和28 = 256個輸出字節(jié)端口和相同數目的16位I/O端口；在任一情況, 一個輸入和一個輸出端口之間的區(qū)別是通過被執(zhí)行的輸入輸出指令所產生的不同信號來定義的。1.5、考慮一個32位微處理器，它有一個16位外部數據總線，并由一個8MHz的輸入時鐘驅動。假設這個微處理器有一個總線周期，其最大持續(xù)時間等于4個輸入時鐘周期。請問該

6、微處理器可以支持的最大數據傳送速度為多少？外部數據總線增加到21位，或者外部時鐘頻率加倍，哪種措施可以更好地提高處理器性能？請敘述你的設想并解釋原因。答案：時鐘周期1/（8MHZ）125ns總線周期4×125ns500ns每500ns傳輸2比特；因此傳輸速度4MB/s加倍頻率可能意味著采用了新的芯片制造技術（假設每個指令都有相同的時鐘周期數）；加倍外部數據總線，在芯片數據總線驅動/鎖存、總線控制邏輯的修改等方面手段廣泛（或許更新）。在第一種方案中，內存芯片的速度要提高一倍（大約），而不能降低微處理器的速度；第二種方案中，內存的字長必須加倍，以便能發(fā)送/接受32位數量。1.6、考慮一個

7、計算機系統，它包含一個I/O模塊，用以控制一臺簡單的鍵盤/打印機電傳打字設備。CPU中包含下列寄存器，這些寄存器直接連接到系統總線上：INPR：輸入寄存器，8位OUTR：輸出寄存器，8位FGI：輸入標記，1位FGO：輸出標記，1位IEN：中斷允許，1位I/O模塊控制從打字機中輸入擊鍵，并輸出到打印機中去。打字機可以把一個字母數字符號編碼成一個8位字，也可以把一個8位字解碼成一個字母數字符號。當8位字從打字機進入輸入寄存器時，輸入標記被置位；當打印一個字時，輸出標記被置位。a. 描述CPU如何使用這4個寄存器實現與打字機間的輸入/輸出。b. 描述通過使用IEN，如何提高執(zhí)行效率？答案：a.來源于

8、打字機的輸入儲存在INPR中。只有當FGI0時，INPR才會接收來自打字機的數據。當數據接收后，被儲存在INPR里面，同時FGI置為1。CPU定期檢查FGI。如果FGI1，CPU將把INPR里面的內容傳送至AC，并把FGI置為0。 當CPU需要傳送數據到打字機時，它會檢查FGO。如果FGO0，CPU處于等待。如果FGO1，CPU將把AC的內容傳送至OUTER并把FGO置為0。當數字符號打印后，打字機將把FGI置為1。 b.（A）描述的過程非常浪費。速度遠高于打字機的CPU必須反復不斷的檢查FGI和FGO。如果中斷被使用，當打字機準備接收或者發(fā)送數據時，可以向CPU發(fā)出一個中斷請求。IEN計數器

9、可以由CPU設置（在程序員的控制下）。1.7、實際上在所有包括DMA模塊的系統中，DMA訪問主存儲器的優(yōu)先級總是高于處理器訪問主存儲器的優(yōu)先級。這是為什么?答案：如果一個處理器在嘗試著讀或者寫存儲器時被掛起, 通常除了一點輕微的時間損耗之外沒有任何危害。但是，DMA可能從或者向設備(例如磁盤或磁帶)以數據流的方式接收或者傳輸數據并且這是不能被打斷的。否則，如果DMA設備被掛起（拒絕繼續(xù)訪問主存），數據可能會丟失。1.9、一臺計算機包括一個CPU和一臺I/O設備D，通過一條共享總線連接到主存儲器M，數據總線的寬度為1個字。CPU每秒最多可執(zhí)行106條指令，平均每條指令需要5個機器周期，其中3個周

10、期需要使用存儲器總線。存儲器讀/寫操作使用1個機器周期。假設CPU正在連續(xù)不斷地執(zhí)行后臺程序，并且需要保證95%的指令執(zhí)行速度，但沒有任何I/O指令。假設1個處理器周期等于1個總線周期，現在要在M和D之間傳送大塊數據。a.若使用程序控制I/O，I/O每傳送1個字需要CPU執(zhí)行兩條指令。請估計通過D的I/O數據傳送的最大可能速度。b.如果使用DMA傳送，請估計傳送速度。答案：a.處理器只能分配5的時間給I/O.所以最大的I/O指令傳送速度是10e6×0.0550000條指令/秒。因此I/O的傳送速率是25000字/秒。 b.使用DMA控制時，可用的機器周期下的數量是10e6（0.05&

11、#215;50.95×2）2.15×10e6 如果我們假設DMA模塊可以使用所有這些周期，并且忽略任何設置和狀態(tài)檢查時間，那么這個值就是最大的I/O傳輸速率。1.10、考慮以下代碼： for ( i = 0；i < 20；i+) for (j = 0；j < 10；j+) ai = ai*ja. 請舉例說明代碼中的空間局部性。b. 請舉例說明代碼中的時間局部性。答案：a.讀取第二條指令是緊跟著讀取第一條指令的。 b.在很短的間歇時間內， ai在循環(huán)內部被訪問了十次。1.11、請將附錄1A中的式（1.1）和式（1.2）推廣到n級存儲器層次中。答案：定義： Ci =

12、 存儲器層次i上每一位的存儲單元平均花銷 Si = 存儲器層次i的規(guī)模大小 Ti = 存儲器層次i上訪問一個字所需時間 Hi = 一個字在不高于層次i的存儲器上的概率 Bi = 把一個數據塊從層次i+1的存儲器上傳輸到層次i的存儲器上所需時間 高速緩沖存儲器作為是存儲器層次1；主存為存儲器層次2；針對所有的N層存儲器層以此類推。有： Ts的引用更復雜，我們從概率論入手：所期望的值，由此我們可以寫出：我們需要清楚如果一個字在M1（緩存）中，那么對它的讀取非常快。如果這個字在M2而不在M1中，那么數據塊需要從M2傳輸到M1中，然后才能讀取。因此，T2 = B1+T1進一步，T3 = B2+T2 =

13、 B1+B2+T1以此類推：所以，但是，最后，1.12、考慮一個存儲器系統，它具有以下參數： Tc = 100 ns Cc = 0.01 分/位 Tm = 1200 ns Cm = 0.001 分/位a.1MB的主存儲器價格為多少？b.使用高速緩沖存儲器技術，1MB的主存儲器價格為多少？c.如果有效存取時間比高速緩沖存儲器存取時間多10% ，命中率H為多少？答案：a.價格 = Cm×8×106 = 8×103 = 80 b.價格 = Cc×8×106 = 8×104 = 800 c.由等式1.1知：1.1×T1 = T1+(

14、1-H)T2 (0.1)(100) = (1-H)(1200) H=1190/12001.13、一臺計算機包括包括高速緩沖存儲器、主存儲器和一個用做虛擬存儲器的磁盤。如果要存取的字在高速緩沖存儲器中，存取它需要20ns；如果該字在主存儲器中而不在高速緩沖存儲器中，把它載入高速緩沖存儲器需要60ns（包括最初檢查高速緩沖存儲器的時間），然后再重新開始存?。蝗绻撟植辉谥鞔鎯ζ髦校瑥拇疟P中取到內存需要12ms，接著復制到高速緩沖存儲器中還需要60ns，再重新開始存取。高速緩沖存儲器的命中率為0.9，主存儲器的命中率為0.6，則該系統中存取一個字的平均存取時間是多少（單位為ns）？答案：有三種情況需

15、要考慮：字所在的位置概率訪問所需時間（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、假設處理器使用一個棧來管理過程調用和返回。請問可以取消程序計數器而用棧指針代替嗎？答案：如果棧只用于保存返回地址?；蛘呷绻麠Ｒ灿糜趥鬟f參數，這種方案只有當棧作為傳遞參數的控制單元而非機器指令時才成立。這兩種情況下可以取消程

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

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

18、算法的青睞。然而，受處理器限制的進程如果在足夠長的時間內得不到處理器時間，同一算法將允許處理器去處理此進程，因為它最近沒有使用過處理器。這樣，一個處理器限制的進程不會永遠得不到處理器。2.3請對優(yōu)化分時系統的調度策略和用于優(yōu)化多道程序批處理系統的調度策略進行比較。分時系統關注的是輪轉時間，時間限制策略更有效是因為它給所有進程一個較短的處理時間。批處理系統關心的是吞吐量，更少的上下文轉換和更多的進程處理時間。因此，最小的上下文轉換最高效。2.4系統調用的目的是什么?如何實現與操作系統相關的的系統調用以及與雙重模式（內核模式和用戶模式）操作相關的系統調用？系統調用被應用程序用來調用一個由操作系統提

19、供的函數。通常情況下，系統調用最終轉換成在內核模式下的系統程序。2.5在IBM的主機操作系統OS/390中，內核中的一個重要模塊是系統資源管理程序（System Resource Manager,SRM），他負責地址空間（進程）之間的資源分配。SRM是的OS/390在操作系統中具有特殊性，沒有任何其他的主機操作系統，當然沒有任何其他類型的操作系統可以比得上SRM所實現的功能。資源的概念包括處理器、實存和I/O通道，SRM累計處理器、I/O通道和各種重要數據結構的利用率，它的目標是基于性能監(jiān)視和分析提供最優(yōu)的性能，其安裝設置了以后的各種性能目標作為SRM的指南，這會基于系統的利用率動態(tài)的修改安裝

20、和作業(yè)性能特點。SRM依次提供報告，允許受過訓練的操作員改進配置和參數設置，以改善用戶服務。現在關注SRM活動的一個實例。實存被劃分為成千上萬個大小相等的塊，稱為幀。每個幀可以保留一塊稱為頁的虛存。SRM每秒大約接受20次控制，并在互相之間以及每個頁面之間進行檢查。如果頁未被引用或被改變，計數器增1。一段時間后，SRM求這些數據的平均值，以確定系統中一個頁面未曾被觸及的平均秒數。這樣做的目的是什么？SRM將采取什么動作？操作系統可以查看這些數據已確定系統的負荷，通過減少加在系統上的活躍作業(yè)來保持較高的平均利用率。典型的平均時間應該是兩分鐘以上，這個平均時間看起來很長，其實并不長。第3章 進程描

21、述和控制3.1. 給出操作系統進行進程管理時的五種主要活動，并簡單描述為什么需要它們。答：用戶進程和系統進程創(chuàng)建及刪除。系統中的進程可以為信息共享、運算加速、模塊化和方便并發(fā)地執(zhí)行。而并發(fā)執(zhí)行需要進程的創(chuàng)建和刪除機制。當進程創(chuàng)建或者運行時分配給它需要的資源。當進程終止時，操作系統需要收回任何可以重新利用的資源。進程的暫停和繼續(xù)執(zhí)行。在進程調度中，當進程在等待某些資源時，操作系統需要將它的狀態(tài)改變?yōu)榈却蚓途w狀態(tài)。當所需要的資源可用時，操作系統需要將它的狀態(tài)變?yōu)檫\行態(tài)以使其繼續(xù)執(zhí)行。提供進程的同步機制。合作的進程可能需要共享數據。對共享數據的并行訪問可能會導致數據沖突。操作系統必須提供進程的同步

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

23、使用本章中給出的定義。請比較這兩組定義的優(yōu)點。答：PINK89中引用了以下例子來闡述其中阻塞和掛起的定義：假設一個進程已經執(zhí)行了一段時間，它需要一個額外的磁帶設備來寫出一個臨時文件。在它開始寫磁帶之前，進程必須得到使用某一設備的許可。當它做出請求時，磁帶設備可能并不可用，這種情況下，該進程就處于阻塞態(tài)。假設操作系統在某一時刻將磁帶設備分配給了該進程，這時進程就重新變?yōu)榛钴S態(tài)。當進程重新變?yōu)閳?zhí)行態(tài)時要對新獲得的磁帶設備進行寫操作。這時進程變?yōu)閽炱饝B(tài)，等待該磁帶上當前所進行的寫操作完成。這種對等待某一設備的兩種不同原因的區(qū)別，在操作系統組織其工作時是非常有用的。然而這并不能表明那些進程是換入的，那

24、些進程是換出的。后一種區(qū)別是必需的，而且應該在進程狀態(tài)中以某種形式表現出來。3.3. 對于圖3.9（b）中給出的7狀態(tài)進程模型，請仿照圖3.8（b）畫出它的排隊圖。答：圖9.3給出了單個阻塞隊列的結果。該圖可以很容易的推廣到多個阻塞隊列的情形。3.4. 考慮圖3.9（b）中的狀態(tài)轉換圖。假設操作系統正在分派進程，有進程處于就緒態(tài)和就緒/掛起態(tài)，并且至少有一個處于就緒/掛起態(tài)的進程比處于就緒態(tài)的所有進程的優(yōu)先級都高。有兩種極端的策略：（1）總是分派一個處于就緒態(tài)的進程，以減少交換；（2）總是把機會給具有最高優(yōu)先級的進程，即使會導致在不需要交換時進行交換。請給出一種能均衡考慮優(yōu)先級和性能的中間策略

25、。答：對于一個就緒/掛起態(tài)的進程，降低一定數量（如一或兩個）優(yōu)先級，從而保證只有當一個就緒/掛起態(tài)的進程比就緒態(tài)的進程的最高優(yōu)先級還高出幾個優(yōu)先級時，它才會被選做下一個執(zhí)行。3.5. 表3.13給出了VAX/VMS操作系統的進程狀態(tài)。a. 請給出這么多種等待狀態(tài)的理由。b. 為什么以下狀態(tài)沒有駐留和換出方案：頁錯誤等待、也沖突等待、公共事件等待、自由頁等待和資源等待。c. 請畫出狀態(tài)轉換圖，并指出引發(fā)狀態(tài)裝換的原因。答：a. 每一種等待狀態(tài)都有一個單獨的隊列與其相關聯。當影響某一等待進程的事件發(fā)生時，把等待進程分成不同的隊列就減少了定位這一等待進程所需的工作量。例如，當一個頁錯誤完成時，調度程

26、序就可以在頁錯誤等待隊列中找到等待的進程。b. 在這些狀態(tài)下，允許進程被換出只會使效率更低。例如，當發(fā)生頁錯誤等待時，進程正在等待換入一個頁從而使其可以執(zhí)行，這是將進程換出是毫無意義的。c. 可以由下面的進程狀態(tài)轉換表得到狀態(tài)轉換圖。當前狀態(tài)下一狀態(tài)當前正在執(zhí)行可計算（駐留）可計算（換出）各種等待狀態(tài)（駐留）各種等待狀態(tài)（換出）當前正在執(zhí)行重調度等待可計算（駐留）調度換出可計算（換出）換入各種等待狀態(tài)（駐留）事件發(fā)生換出各種等待狀態(tài)（換出）事件發(fā)生3.6. VAM/VMS操作系統采用了四種處理器訪問模式，以促進系統資源在進程間的保護和共享。訪問模式確定：l 指令執(zhí)行特權：處理器將執(zhí)行什么指令。

27、l 內存訪問特權：當前指令可能訪問虛擬內存中的哪個單元。四種模式如下：l 內核模式：執(zhí)行VMS操作系統的內核，包括內存管理、中斷處理和I/O操作。l 執(zhí)行模式：執(zhí)行許多操作系統服務調用，包括文件（磁盤和磁帶）和記錄管理例程。l 管理模式：執(zhí)行其他操作系統服務，如響應用戶命令。l 用戶模式：執(zhí)行用戶程序和諸如編譯器、編輯器、鏈接程序、調試器之類的實用程序。在較少特權模式執(zhí)行的進程通常需要調用在較多特權模式下執(zhí)行的過程，例如，一個用戶程序需要一個操作系統服務。這個調用通過使用一個改變模式（簡稱CHM）指令來實現，該指令將引發(fā)一個中斷，把控制轉交給處于新的訪問模式下的例程，并通過執(zhí)行REI（Retu

28、rn from Exception or Interrupt，從異常或中斷返回）指令返回。a. 很多操作系統有兩種模式，內核和用戶，那么提供四種模式有什么優(yōu)點和缺點？b. 你可以舉出一種有四種以上模式的情況嗎？答：a. 四種模式的優(yōu)點是對主存的訪問控制更加靈活，能夠為主存提供更好的保護。缺點是復雜和處理的開銷過大。例如，程序在每一種執(zhí)行模式下都要有一個獨立的堆棧。b. 原則上，模式越多越靈活，但是四種以上的模式似乎很難實現。3.7. 在前面習題中討論的VMS方案常常稱為環(huán)狀保護結構，如圖3.18所示。3.3節(jié)所描述的簡單的內核/用戶方案是一種兩環(huán)結構，SILB04指出了這種方法的問題：環(huán)狀（層

29、次）結構的主要缺點是它不允許我們實施須知原理，特別地，如果一個對象必須在域Dj中可訪問，但在域Di中不可訪問，則必須有就j<i。這意味著在Di中可訪問的每個段在Dj中都可以訪問。a. 請清楚地解釋上面引文中提出的問題。b. 請給出環(huán)狀結構操作系統解決這個問題的一種方法。答：a. 當j<i時，運行在Di中的進程被禁止訪問Dj中的對象。因此，如果Dj中包含的信息比Di中的更具有特權或者要求的安全性更高，那么這種限制就是合理的。然而，通過以下方法卻可以繞過這種安全策略。一個運行在Dj中的進程可以讀取Dj中的數據，然后把數據復制到Di中。隨后，Di中的進程就可以訪問這些信息了。b. 有一種

30、解決這一問題的方法叫做可信系統，我們將在16章中進行討論。3.8. 圖3.7（b）表明一個進程每次只能在一個事件隊列中。a. 是否能夠允許進程同時等待一個或多個事件？請舉例說明。b. 在這種情況下，如何修改圖中的排隊結構以支持這個新特點？答：a. 一個進程可能正在處理從另一個進程收到的數據并將結果保存到磁盤上。如果當前在另一個進程中正有數據在等待被取走，進程就可以繼續(xù)獲得數據并處理它。如果前一個寫磁盤操作已經完成，并且有處理好的數據在等待寫出，那么進程就可以繼續(xù)寫磁盤。這樣就可能存在某一時刻，進程即在等待從輸入進程獲得數據，又在等待磁盤可用。b. 有很多種方法解決這一問題?？梢允褂靡环N特殊的隊

31、列，或者將進程放入兩個獨立的隊列中。不論采用哪種方法，操作系統都必須處理好細節(jié)工作，使進程相繼地關注兩個事件的發(fā)生。3.9. 在很多早期計算機中，中斷導致寄存器值被保存在與給定的中斷信息相關聯的固定單元。在什么情況下這是一種實用的技術？請解釋為什么它通常是不方便的。答：這種技術是基于被中斷的進程A在中斷響應之后繼續(xù)執(zhí)行的假設的。但是，在通常情況下，中斷可能會導致另一個進程B搶占了進程A。這是就必須將進程A的執(zhí)行狀態(tài)從與中斷相關的位置復制到與A相關的進程描述中。然而機器卻有可能仍將它們保存到前一位置。參考：BRIN73。3.10. 3.4節(jié)曾經講述過，由于在內核模式下執(zhí)行的進程是不能被搶占的，因

32、此UNIX不適用于實時應用。請闡述原因。答：由于存在進程不能被搶占的情況（如在內核模式下執(zhí)行的進程），操作系統不可能對實時需求給予迅速的反應。第4章 線程、對稱多處理和微內核4.1. 一個進程中的多個線程有以下兩個優(yōu)點：（1）在一個已有進程中創(chuàng)建一個新線程比創(chuàng)建一個新進程所需的工作量少；（2）在同一個進程中的線程間的通信比較簡單。請問同一個進程中的兩個線程間的模式切換與不同進程中的兩個線程間的模式切換相比，所需的工作量是否要少？答：是的，因為兩個進程間的模式切換要儲存更多的狀態(tài)信息。4.2. 在比較用戶級線程和內核級線程時曾指出用戶級線程的一個缺點，即當一個用戶級線程執(zhí)行系統調用時，不僅這個線

33、程被阻塞，而且進程中的所有線程都被阻塞。請問這是為什么？答：因為對于用戶級線程來說，一個進程的線程結構對操作系統是不可見的，而操作系統的調度是以進程為單位的。4.3. 在OS/2中，其他操作系統中通用的進程概念被分成了三個獨立類型的實體：會話、進程和線程。一個會話是一組與用戶接口（鍵盤、顯示器、鼠標）相關聯的一個或多個進程。會話代表了一個交互式的用戶應用程序，如字處理程序或電子表格，這個概念使得PC用戶可以打開一個以上的應用程序，在屏幕上顯示一個或更多個窗口。操作系統必須知道哪個窗口，即哪個會話是活躍的，從而把鍵盤和鼠標的輸入傳遞個相應的會話。在任何時刻，只有一個會話在前臺模式，其他的會話都在

34、后臺模式，鍵盤和鼠標的所有輸入都發(fā)送給前臺會話的一個進程。當一個會話在前臺模式時，執(zhí)行視頻輸出的進程直接把它發(fā)送到硬件視頻緩沖區(qū)。當一個會話在后臺時，如果該會話的任何一個進程的任何一個線程正在執(zhí)行并產生屏幕輸出，則這個輸出被送到邏輯視頻緩沖區(qū)；當這個會話返回前臺時，屏幕被更新，為新的前臺會話反映出邏輯視頻緩沖區(qū)中的當前內容。有一種方法可以把OS/2中與進程相關的概念的數目從3個減少到2個。刪去會話，把用戶接口（鍵盤、顯示器、鼠標）和進程關聯起來。這樣，在某一時刻，只有一個進程處于前臺模式。為了進一步地進行構造，進程可以被劃分成線程。a. 使用這種方法會喪失什么優(yōu)點？b. 如果繼續(xù)使用這種修改方

35、法，應該在哪里分配資源（存儲器、文件等）：在進程級還是線程級？答：a. 會話的使用非常適合個人計算機和工作站對交互式圖形接口的需求。它為明確圖形輸出和鍵盤/鼠標輸入應該被關聯到什么位置提供了一個統一的機制，減輕了操作系統的工作負擔。b. 應該和其他的進程/線程系統一樣，在進程級分配地址空間和文件。4.4. 考慮這樣一個環(huán)境，用戶級線程和內核級線程呈一對一的映射關系，并且允許進程中的一個或多個線程產生會引發(fā)阻塞的系統調用，而其他線程可以繼續(xù)運行。解釋為什么這個模型可以使多線程程序比在單處理器機器上的相應的單線程程序運行速度更快？答：問題在于機器會花費相當多的時間等待I/O操作的完成。在一個多線程

36、程序中，可能一個內核級線程會產生引發(fā)阻塞的系統調用，而其他內核級線程可以繼續(xù)執(zhí)行。而在單處理器機器上，進程則必須阻塞知道所有的系統調用都可以繼續(xù)運行。參考：LEWI964.5. 如果一個進程退出時，該進程的某些線程仍在運行，請問他們會繼續(xù)運行嗎？答：不會。當一個進程退出時，會帶走它的所有東西內核級線程，進程結構，存儲空間包括線程。參考：LEWI964.6. OS/390主機操作系統圍繞著地址空間和任務的概念構造。粗略說來，一個地址空間對應于一個應用程序，并且或多或少地對應于其他操作系統中的一個進程；在一個地址空間中，可以產生一組任務，并且它們可以并發(fā)執(zhí)行，這大致對應于多線程的概念。管理任務結構

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

38、。4.7. 一個多處理系統有8個處理器和20個附加磁帶設備?，F在有大量的作業(yè)提交給該系統，完成每個作業(yè)最多需要4個磁帶設備。假設每個作業(yè)開始運行時只需要3個磁帶設備，并且在很長時間內都只需要這3個設備，而只是在最后很短的一段時間內需要第4個設備以完成操作。同時還假設這類作業(yè)源源不斷。a. 假設操作系統中的調度器只有當4個磁帶設備都可用時才開始一個作業(yè)。當作業(yè)開始時，4個設備立即被分配給它，并且直到作業(yè)完成時才被釋放。請問一次最多可以同時執(zhí)行幾個作業(yè)？采用這種策略，最多有幾個磁帶設備可能是空閑的？最少有幾個？b. 給出另外一種策略，要求其可以提高磁帶設備的利用率，并且同時可以避免系統死鎖。分析最

39、多可以有幾個作業(yè)同時執(zhí)行，可能出現的空閑設備的范圍是多少。答：a. 采用一個保守的策略，一次最多同時執(zhí)行20/4=5個作業(yè)。由于分配各一個任務的磁帶設備最多同時只有一個空閑，所以在同一時刻最多有5個磁帶設備可能是空閑的。在最好的情況下沒有磁帶設備空閑。b. 為了更好的利用磁設備，每個作業(yè)在最初只分配三個磁帶設備。第四個只有的需要的時候才分配。在這種策略中，最多可以有20/3=6個作業(yè)同時執(zhí)行。最少的空閑設備數量為0，最多有2個。參考：Advanced Computer Architectrue,K.Hwang,1993.4.8. 在描述Solaris用戶級線程狀態(tài)時，曾表明一個用戶級線程可能讓

40、位于具有相同優(yōu)先級的另一個線程。請問，如果有一個可運行的、具有更高優(yōu)先級的線程，讓位函數是否還會導致讓位于具有相同優(yōu)先級或更高優(yōu)先級的線程？答：任何一個可能改變線程優(yōu)先級或者使更高優(yōu)先級的線程可運行的調用都會引起調度，它會依次搶占低優(yōu)先級的活躍線程。所以，永遠都不會存在一個可運行的、具有更高優(yōu)先級的線程。參考：LEVI96第5章 并發(fā)性：互斥和同步5.1答：b.協同程序read讀卡片，將字符賦給一個只有一個字大小的緩沖區(qū)rs然后在賦給squash協同程。協同程序Read在每副卡片圖像的后面插入一個額外的空白。協同程序squash不需要知道任何關于輸入的八十個字符的結構，它簡單的查找成對出現的星

41、號，然后將更改夠的字符串經由只有一個字符大小的緩沖sp，傳遞給協同程序print。最后協同程序print簡單的接受到來的字符串，并將他們打印在包含125個字符的行中。5.2考慮一個并發(fā)程序，它有兩個進程p和q，定義如下。A.B.C.D和E是任意的原子語句。假設住程序執(zhí)行兩個進程的parbegin Void 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 co

42、unt; for(count =1;count <=n;count +) tally+; void main() tally =0;parbegin(total(),total();write(tally); 答：a.隨意一看,tally值的范圍好像是落在50,100這個區(qū)間里,因為當沒有互斥時可以從0直接增加到50.這一基本論點是當并發(fā)的運行這兩進程時,我們不可能得到一個比連續(xù)執(zhí)行單一某進程所得tally值還低的一個最終tally值.但是考慮下面由這兩進程按交替順序執(zhí)行載入,增加,存儲的情況,同時變更這個共享變量的取值: 1.進程A載入tally值,tally值加到1,在此時失去處理器

43、(它已經增加寄存器的值到1,但是還沒有存儲這個值). 2.進程B載入tally值(仍然是0),然后運行完成49次增加操作,在它已經將49這個值存儲給共享變量tally后,失去處理器控制權. 3.進程A重新獲得處理器控制權去完成它的第一次存儲操作(用1去代替先前的49這個tally值),此時被迫立即放棄處理器. 4.進程B重新開始,將1(當前的tally值)載入到它自己的寄存器中,但此時被迫放棄處理器(注意這是B的最后一次載入). 5.進程A被重新安排開始,但這次沒有被中斷,直到運行完成它剩余的49次載入,增加和存儲操作,結果是此時tally值已經是50. 6.進程B在它終止前完成僅有的最后一次

44、增加和存儲操作.它的寄存器值增至2,同時存儲這個值做為這個共享變量的最終結果. 一些認為會出現低于2這個值的結果,這種情況不會出現.這樣tally值的正確范圍是2,100. b.對一般有N個進程的情況下,tally值的最終范圍是2,N*50,因為對其他所有進程來說,從最初開始運行到在第五步完成.但最后都被進程B破壞掉它們的最終結果.5.4.忙等待是否總是比阻塞等待效率低（根據處理器的使用時間）？請解釋。答：就一般情況來說是對的,因為忙等待消耗無用的指令周期.然而,有一種特殊情況,當進程執(zhí)行到程序的某一點處,在此處要等待直到條件滿足,而正好條件已滿足,此時忙等待會立即有結果,然而阻塞等待會消耗操

45、作系統資源在換出與換入進程上.5.5考慮下面的程序 boolean blocked2; int rurn; void P(int id) While (true) While(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的值為

46、true,在這時發(fā)現布爾變量blocked0的值為false,然后P(0)會將true值賦予blocked0,此時turn=0,P(0)進入臨界區(qū),P(1)在將1賦值給turn后,也進入了臨界區(qū).5.6解決互斥的另一種軟件方法是lamport的面包店（bakery）算法，之所以起這個名字，是因為它的思想來自于面包店或其他商店中，每個顧客在到達時都得到一個有編號的票，并按票號依次得到服務，算法如下： Boolean choosingn; Int numbern; While (true) Choosingi=true; Numberi=1+getmax(number,n)； Choosingi=

47、false; For(int j=0;j<n;j+) While (choosingj) While (numberj!=0)&&(numberj,j)<(numberi,i) /*critical section*/ Numberi=0; /*remainder*/; 數組choosing和number分別被初始化成false和0，每個數組的第i個元素可以由進程i讀或寫，但其他進程只能讀。符號（a，b）<（c，d）被定義成 （a，c）或（a=c且b<d）A 用文字描述這個算法。B 說明這個算法避免了死鎖。C 說明它實施了互斥。答：a.當一個進程希望進入

48、臨界區(qū)時,它被分配一個票號.分配的票號是通過在目前那些等待進入臨界區(qū)的進程所持票號和已經在臨界區(qū)的進程所持票號比較,所得最大票號再加1得到的.有最小票號的進程有最高的優(yōu)先級進入臨界區(qū).當有多個進程擁有同樣的票號時,擁有最小數字號進入臨界區(qū).當一個進程退出臨界區(qū)時,重新設置它的票號為0. b.如果每個進程被分配唯一的一個進程號,那么總會有一個唯一的,嚴格的進程順序.因此,死鎖可以避免. c.為了說明互斥,我們首先需要證明下面的定理:如果Pi在它的臨界區(qū),Pk已經計算出來它的numberk,并試圖進入臨界區(qū),此時就有下面的關系式: ( numberi, i ) < ( numberk, k

49、).為證明定理,定義下面一些時間量: Tw1:Pi最后一次讀choosingk, 當 j=k,在它的第一次等待時,因此我們在Tw1處有choosingk = false. Tw2:Pi開始它的最后執(zhí)行, 當j=k,在它的第二次while循環(huán)時,因此我們有Tw1 < Tw2. Tk1:Pk在開始repeat循環(huán)時;Tk2:Pk完成numberk的計算;Tk3: Pk設置choosingk為false時.我們有Tk1<Tk2<Tk3.因為在Tw1處,choosingk=false,我們要么有Tw1<Tk1,要么有Tk3<Tw1.在第一種情況中,我們有numberi&l

50、t;numberk,因為Pi在Pk之前被分配號碼;這個滿足定理條件.在第二種情況中,我們有Tk2 < Tk3 < Tw1 < Tw2,因此有Tk2<Tw2.這意味著在Tw2時,Pi已經讀了當前numberk的值.而且,因為Tw2是當j=k第二次while循環(huán)執(zhí)行發(fā)生的時刻,我們有(numberi, i ) < ( numberk, k),這樣完成了定理的證明.現在就很容易說明實施了互斥.假定Pi在臨界區(qū),Pk正試圖進入臨界區(qū).Pk將不能進入臨界區(qū),因為它會發(fā)現numberi不等于0,并且( numberi, i ) < ( numberk, k ).5.7當按圖5.2的形式使用一個專門機器指令提供互斥時，對進程在允許訪問臨界區(qū)之前必須等待多久沒有控制。設計一個使用testset指令的算法