操作系統(tǒng)精髓與設(shè)計(jì)重點(diǎn)店課后習(xí)題整理

1、1 3 4 9 7 8 11 12 6章第10章多CPU調(diào)度，實(shí)時(shí)調(diào)度第1章 作業(yè)：習(xí)題P25 1.3 1.8 1.9（更正印刷錯(cuò)誤106）1.3操作系統(tǒng)的大神求解答假設(shè)有一個(gè)32位微處理器，其32位的指令由兩個(gè)域組成：第一個(gè)字節(jié)包含操作碼，其余部分為一個(gè)直接操作數(shù)或一個(gè)操作數(shù)地址。如果微處理器總線具有如下特征，分析a、最大可直接尋址的存儲(chǔ)器能力為多少？以字節(jié)為單位如果微處理器總線具有如下特征，分析對(duì)系統(tǒng)速度的影響：b、（1）一個(gè)32位局部地址總線和一個(gè)16位局部數(shù)據(jù)總線，或者（2） 一個(gè)16位局部地址總線和一個(gè)16位局部數(shù)據(jù)總線。C、程序計(jì)數(shù)器和指令寄存器分別需要多少位答案：沒(méi)必要全寫撿重點(diǎn)

2、(定長(zhǎng))指令32位，1字節(jié)操作碼，則后3字節(jié)為立即數(shù)或內(nèi)存地址(a) 最大可直接尋址直接尋址是一種基本的尋址方法，其特點(diǎn)是：在指令格式的地址的字段中直接指出操作數(shù)在內(nèi)存的地址。由于操作數(shù)的地址直接給出而不需要經(jīng)過(guò)某種變換，所以稱這種尋址方式為直接尋址方式。224(b) 總線問(wèn)題地址總線32位，數(shù)據(jù)總線16位直接尋址存儲(chǔ)器24位，bus32位，地址傳送一次即可；但指令32位，操作數(shù)32位(因?yàn)槭?2位微處理器)，要兩次傳送地址總線16位，數(shù)據(jù)總線16位傳送地址，傳送指令/數(shù)據(jù)全部需要2次。地址可視作：先行地址后列地址(c) PC和IR 至少：PC24位，IR8位一般：PC32bit IR 32b

3、it更現(xiàn)實(shí)復(fù)雜情形：是否分段，使用段寄存器; 直接尋址中邏輯地址/位移/偏移offset，與有效地址effective address區(qū)別OS中，邏輯地址與物理地址1.8一個(gè)DMA模塊從外部設(shè)備給內(nèi)存?zhèn)魉妥止?jié)，傳送速度為9600位每秒（b/s)。處理器可以每秒100萬(wàn)次的速度取指令，由于DMA活動(dòng)，處理器的速度將會(huì)減慢多少？答案：沒(méi)必要全寫撿重點(diǎn)看清楚題干：每秒100萬(wàn)次取指令，即1M/s取一次指令，不是100M！該CPU主頻多少不知，是否使用cache不知，執(zhí)行一條指令多少時(shí)鐘周期不知，此題中無(wú)需知道還假設(shè)，此CPU只取指令要訪問(wèn)內(nèi)存，執(zhí)行指令不需要讀寫數(shù)據(jù)，不訪內(nèi)存. 還假設(shè)DMA一次訪問(wèn)

4、內(nèi)存?zhèn)魉?個(gè)字節(jié) 憑什么如此假設(shè)？9600b/s=1200B/s 即1s中要傳送1200次，而原本CPU要1M次訪存，現(xiàn)在因DMA要減少1200次，所以影響是1200/1M=0.12%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指令。假設(shè)1個(gè)處理器周期等于1個(gè)總線周期，現(xiàn)在要在M和D之間傳送大塊數(shù)據(jù)。a.若使用程序控

5、制I/O，I/O每傳送1個(gè)字需要CPU執(zhí)行兩條指令。請(qǐng)估計(jì)通過(guò)D的I/O數(shù)據(jù)傳送的最大可能速度。b.如果使用DMA傳送，請(qǐng)估計(jì)傳送速度。答案：沒(méi)必要全寫撿重點(diǎn)題干信息：多少位CPU不知，字長(zhǎng)多少位不知，以處理器周期為單位，訪問(wèn)內(nèi)存(讀1條指令讀1字?jǐn)?shù)據(jù))要1周期，執(zhí)行1指令需要5周期。CPU每秒最多執(zhí)行106條指令程序IO：傳送1字要2條指令限制只能有5%的CPU處理用于IO程序IO：傳送1字要2條指令限制只能有5%的CPU處理用于IO此限制下，1秒可執(zhí)行用于IO的指令為5% * 106條指令而2條指令才可傳送1字?jǐn)?shù)據(jù)，所以每秒IO最大可傳送的字為0.5*5%*106=25000字/秒DMA情

6、形：最大速度：在CPU執(zhí)行后臺(tái)程序時(shí)，總共能找到多少周期可以利用。1周期傳送1字5%CPU處理能力，全部可用于DMA,可執(zhí)行指令條數(shù)為5%*106，而1條有5周期，所以可傳送字：5*5%*106 個(gè)字DMA情形：最大速度：在CPU執(zhí)行后臺(tái)程序時(shí)，總共能找到多少周期可以利用。1周期傳送1字最大嗎？要見(jiàn)縫插針！后臺(tái)程序執(zhí)行時(shí)，執(zhí)行1條指令共5個(gè)周期，但只在3個(gè)周期中訪存，還有2個(gè)沒(méi)有使用，DMA可用這兩個(gè)周期DMA情形：最大速度：在CPU執(zhí)行后臺(tái)程序時(shí)，總共能找到多少周期可以利用。1周期傳送1字最后，DMA最大速度為：106(0.05 × 5 + 0.95 × 2) = 2.1

7、5 × 106 即2.15M字/秒第3章 ：進(jìn)程描述與控制P103 3.5，3.14 P104 3.111、概念：交換(swapping)：操作系統(tǒng)將內(nèi)存中進(jìn)程的內(nèi)容或部分內(nèi)容寫入硬盤，或反之的操作。進(jìn)程：具有一定獨(dú)立功能的程序關(guān)于一個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。2. 進(jìn)程有哪三個(gè)基本狀態(tài)？試說(shuō)明狀態(tài)轉(zhuǎn)換的典型原因，圖示。（1） 處于就緒狀態(tài)的進(jìn)程，當(dāng)進(jìn)程調(diào)度程序?yàn)橹峙淞颂幚頇C(jī)后，該進(jìn)程就由就緒狀態(tài)變?yōu)閳?zhí)行狀態(tài) （2） 正在執(zhí)行的進(jìn)程因發(fā)生某事件而無(wú)法執(zhí)行，如暫時(shí)無(wú)法取得所需資源，則由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)。 （3） 正在執(zhí)行的進(jìn)程，如因時(shí)間片用完或被高優(yōu)先級(jí)的進(jìn)程搶占處理機(jī)而被暫停執(zhí)

8、行，該進(jìn)程便由執(zhí)行轉(zhuǎn)變?yōu)榫途w狀態(tài)。（2） 狀態(tài)轉(zhuǎn)換1不會(huì)立即引起其他狀態(tài)轉(zhuǎn)換。 狀態(tài)轉(zhuǎn)換2必然立即引發(fā)狀態(tài)轉(zhuǎn)換1：狀態(tài)轉(zhuǎn)換2發(fā)生后，進(jìn)程調(diào)度程序必然要選出一個(gè)新的就緒進(jìn)程投入運(yùn)行，該新進(jìn)程可能是其他進(jìn)程，也可能是剛從執(zhí)行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)的那個(gè)進(jìn)程。 狀態(tài)轉(zhuǎn)換3可能立即引發(fā)狀態(tài)轉(zhuǎn)換1：狀態(tài)轉(zhuǎn)換3發(fā)生后，若就緒隊(duì)列非空，則進(jìn)程調(diào)度程序?qū)⑦x出一個(gè)就緒進(jìn)程投入執(zhí)行。 狀態(tài)轉(zhuǎn)換4可能引發(fā)狀態(tài)轉(zhuǎn)換1：狀態(tài)轉(zhuǎn)換4發(fā)生后，若CPU空閑，并且沒(méi)有其他進(jìn)程競(jìng)爭(zhēng)CPU，則該進(jìn)程將被立即調(diào)度。 另外，狀態(tài)轉(zhuǎn)換4還可能同時(shí)引發(fā)狀態(tài)轉(zhuǎn)換1和2：若系統(tǒng)采用搶占調(diào)度方式，而新就緒的進(jìn)程具備搶占CPU的條件（如其優(yōu)先權(quán)很高）

9、，則它可立即得到CPU轉(zhuǎn)換成執(zhí)行狀態(tài)，而原來(lái)正在執(zhí)行的進(jìn)程則轉(zhuǎn)換成就緒狀態(tài)。3.5什么是交換，目的是什么：操作系統(tǒng)將內(nèi)存中進(jìn)程的內(nèi)容或部分內(nèi)容寫入硬盤，或反之的操作。目的：將暫時(shí)無(wú)法運(yùn)行的進(jìn)程（阻塞狀態(tài)）從內(nèi)存中移出，空出內(nèi)存，以便在內(nèi)存中裝入盡可能多的可運(yùn)行的進(jìn)程。3.14模式切換與進(jìn)程切換是什么有什么區(qū)別是什么：為便于OS實(shí)現(xiàn)和管理，處理器一般支持兩種（以上的）執(zhí)行模式：用戶態(tài)和內(nèi)核態(tài)。OS在內(nèi)核態(tài)下運(yùn)行，用戶進(jìn)程在用戶態(tài)下運(yùn)行。從用戶態(tài)到內(nèi)核態(tài)的改變或反之，稱之為模式切換。用戶進(jìn)程運(yùn)行時(shí)，如處理器響應(yīng)中斷，進(jìn)入中斷處理程序，則由用戶態(tài)進(jìn)入內(nèi)核態(tài)；而中斷返回后，從內(nèi)核態(tài)返回用戶態(tài)。區(qū)別：模

10、式切換不一定會(huì)改變當(dāng)前運(yùn)行的進(jìn)程的狀態(tài)，而進(jìn)程切換過(guò)程中必然會(huì)出現(xiàn)模式切換。模式切換（對(duì)應(yīng)的中斷處理）保存/恢復(fù)的狀態(tài)信息少，而進(jìn)程切換需要保存/恢復(fù)的狀態(tài)信息多。3.11 中斷A）中斷如何支持多道程序設(shè)計(jì)：1.外部設(shè)備具備中斷能力后，CPU才可能在外部設(shè)備開始工作到完成之間執(zhí)行其它程序；（輪詢方式中，外部設(shè)備工作完成之前，CPU一直循環(huán)測(cè)試外部設(shè)備的狀態(tài)，不可能執(zhí)行其它程序）2.利用中斷方式，操作系統(tǒng)可以及時(shí)獲得控制權(quán)，在多個(gè)程序之間選擇調(diào)度。B)中斷如何支持錯(cuò)誤處理：在硬件發(fā)生異常時(shí)，如奇偶校驗(yàn)錯(cuò)，掉電等，以特殊中斷形式出現(xiàn)；程序中出現(xiàn)系統(tǒng)錯(cuò)誤時(shí)，如除零，地址越界，（無(wú)訪問(wèn)權(quán)限的）非法訪問(wèn)

11、，以特殊中斷形式出現(xiàn)；程序中應(yīng)用語(yǔ)義級(jí)的錯(cuò)誤，也可以中斷形式出現(xiàn)；各種錯(cuò)誤統(tǒng)一地用中斷方式處理，只要分別編制相應(yīng)的中斷處理程序即可，簡(jiǎn)化了硬件設(shè)計(jì)，也方便了用戶程序開發(fā)。C）對(duì)于單線程而言，說(shuō)明一個(gè)能夠引起中斷并且導(dǎo)致進(jìn)程切換的情景，另外說(shuō)明能引起中斷但沒(méi)有進(jìn)程切換的例子導(dǎo)致切換例：用戶進(jìn)程要求輸入，則在啟動(dòng)外部設(shè)備工作后，用戶進(jìn)程進(jìn)入阻塞狀態(tài)，進(jìn)行進(jìn)程切換；不導(dǎo)致切換例：發(fā)生時(shí)鐘中斷，當(dāng)前運(yùn)行的用戶進(jìn)程的時(shí)間片還未用完，則繼續(xù)執(zhí)行。(另，若不限定為外部中斷，則用戶進(jìn)程執(zhí)行系統(tǒng)調(diào)用時(shí)，發(fā)生中斷，若系統(tǒng)調(diào)用不涉及IO，則不會(huì)發(fā)生進(jìn)程切換)第4章 線程對(duì)稱處理SMP和微內(nèi)核概念：線程是進(jìn)程中一個(gè)相

12、對(duì)獨(dú)立的執(zhí)行流，是CPU調(diào)度的單位。1、為什么要引入線程，多線程有何優(yōu)點(diǎn)？操作系統(tǒng)引入線程后，可以簡(jiǎn)化并發(fā)程序的設(shè)計(jì)，方便在一個(gè)進(jìn)程內(nèi)實(shí)現(xiàn)多個(gè)并行處理。多線程的優(yōu)點(diǎn)包括：實(shí)現(xiàn)進(jìn)程內(nèi)并行處理；方便數(shù)據(jù)共享；降低了切換時(shí)的系統(tǒng)開銷；提高了CPU的利用率；改善了程序的響應(yīng)性。2. 比較TCB與PCB內(nèi)容。TCB：線程標(biāo)識(shí)，線程狀態(tài)（運(yùn)行,就緒,阻塞）,處理器狀態(tài)，（堆棧,私用數(shù)據(jù)段的）指針PCB: (TCB中沒(méi)有的)進(jìn)程的虛擬空間指針，文件等資源，進(jìn)程的權(quán)限，進(jìn)程間通信等。3. 比較用戶級(jí)線程與內(nèi)核級(jí)線程的異同用戶級(jí)：優(yōu)點(diǎn)：不需要OS支持，調(diào)度方式靈活，開銷??；缺點(diǎn)：不能并行，一線程阻塞，其它線程也

13、不能運(yùn)行。內(nèi)核級(jí)：優(yōu)點(diǎn)：可并行，一線程阻塞不會(huì)阻塞其它線程，缺點(diǎn)：創(chuàng)建切換開銷相對(duì)大第9章 ：?jiǎn)翁幚砥髡{(diào)度 P291 9.1, 9.5, 9.109.1簡(jiǎn)要描述三種類型的處理器調(diào)度長(zhǎng)程調(diào)度：決定加入到待執(zhí)行的進(jìn)程池中；中程調(diào)度：決定加入到部分或全部在主存中的進(jìn)程集合中；短程調(diào)度：決定哪一個(gè)可用進(jìn)程將被處理器執(zhí)行。9.5搶占式和非搶占式有什么區(qū)別非搶占：在這種情況下，一旦進(jìn)程處于運(yùn)行態(tài)，他就不斷執(zhí)行直到終止，或者為等待I/O或請(qǐng)求某些操作系統(tǒng)服務(wù)而阻塞自己。搶占：當(dāng)前正在運(yùn)行的進(jìn)程可能被操作系統(tǒng)中斷，并轉(zhuǎn)移到就緒態(tài)。關(guān)于搶占的決策可能是在一個(gè)新進(jìn)程到達(dá)時(shí)，或者在一個(gè)中斷發(fā)生后把一個(gè)被阻塞的進(jìn)程置

14、為就緒態(tài)時(shí)，或者基于周期性的時(shí)間中斷。9.10簡(jiǎn)答定義最高響應(yīng)比優(yōu)先調(diào)度調(diào)度基于搶占原則并且使用動(dòng)態(tài)優(yōu)先級(jí)機(jī)制。當(dāng)一個(gè)進(jìn)程第一次進(jìn)入系統(tǒng)時(shí)，它被放置在RQ0。當(dāng)它第一次被搶占后并返回就緒狀態(tài)時(shí)，它被防止在RQ1。在隨后的時(shí)間里，每當(dāng)它被搶占時(shí)，它被降級(jí)到下一個(gè)低優(yōu)先級(jí)隊(duì)列中。一個(gè)短進(jìn)程很快會(huì)執(zhí)行完，不會(huì)在就緒隊(duì)列中降很多級(jí)。一個(gè)長(zhǎng)進(jìn)程會(huì)逐級(jí)下降。因此，新到的進(jìn)程和短進(jìn)程優(yōu)先于老進(jìn)程和長(zhǎng)進(jìn)程。在每個(gè)隊(duì)列中，除了在優(yōu)先級(jí)最低的隊(duì)列中，都使用簡(jiǎn)單的FCFS機(jī)制。一旦一個(gè)進(jìn)程處于優(yōu)先級(jí)最低的隊(duì)列中，它就不可能再降低，但是會(huì)重復(fù)地返回該隊(duì)列，直到運(yùn)行結(jié)束。 補(bǔ)充題：分析多級(jí)反饋算法(指出其目標(biāo)

15、，假設(shè)，內(nèi)容及效果)反饋調(diào)度算法分析：目標(biāo)系統(tǒng)效率：減少平均等待時(shí)間，提高系統(tǒng)呑吐量公平：減少饑餓現(xiàn)象出現(xiàn)或減輕程度盡量減少系統(tǒng)開銷反饋調(diào)度算法分析:假設(shè),理由程序由CPU陣發(fā)期，IO陣發(fā)期交替構(gòu)成程序完成一次IO后，緊接著可能是一個(gè)短暫的IO陣發(fā)期程序一開始，一般都是一個(gè)CPU陣發(fā)期程序運(yùn)行時(shí)間有長(zhǎng)有短；長(zhǎng)時(shí)間運(yùn)行沒(méi)有結(jié)束的程序可能還需要很長(zhǎng)時(shí)間才能結(jié)束反饋調(diào)度算法分析:內(nèi)容設(shè)置多個(gè)分成優(yōu)先級(jí)不同的就緒隊(duì)列，高優(yōu)先級(jí)隊(duì)列的時(shí)間片短，低優(yōu)先級(jí)隊(duì)列的時(shí)間片長(zhǎng)。(任一優(yōu)先級(jí)的進(jìn)程被調(diào)度運(yùn)行時(shí)，時(shí)間片內(nèi)不會(huì)被搶占。)調(diào)度時(shí)，某一優(yōu)先級(jí)隊(duì)列的進(jìn)程只在所有比其高的隊(duì)列都為空時(shí)，才會(huì)調(diào)度這一隊(duì)列中的進(jìn)程。

16、進(jìn)程新創(chuàng)建時(shí)，進(jìn)入優(yōu)先級(jí)最高的隊(duì)列。每一進(jìn)程被調(diào)度運(yùn)行，用完時(shí)間片仍未結(jié)束重新回到就緒狀態(tài)時(shí)，移入下一優(yōu)先級(jí)隊(duì)列而進(jìn)程從阻塞狀態(tài)到就緒狀態(tài)時(shí)，提高優(yōu)先級(jí)反饋調(diào)度算法分析：效果體現(xiàn)了短作業(yè)“優(yōu)先”：因?yàn)槠渌璧臅r(shí)間片少，優(yōu)先級(jí)不會(huì)下降很多，會(huì)被優(yōu)先調(diào)度，從而很快運(yùn)行結(jié)束。因此，響應(yīng)時(shí)間短，平均周轉(zhuǎn)時(shí)間短有較好的響應(yīng)時(shí)間：因?yàn)樾逻M(jìn)程優(yōu)先級(jí)最高，被優(yōu)先調(diào)度執(zhí)行，所以響應(yīng)時(shí)間短；IO結(jié)束的進(jìn)程提高優(yōu)先級(jí)，也會(huì)相對(duì)優(yōu)先被調(diào)度執(zhí)行，同樣響應(yīng)時(shí)間短(用戶在輸入完成后，進(jìn)程很快會(huì)有反應(yīng))長(zhǎng)作業(yè)的系統(tǒng)開銷較?。洪L(zhǎng)作業(yè)最終會(huì)落到優(yōu)先級(jí)最低，時(shí)間片最長(zhǎng)的就緒隊(duì)列中。一旦此類作業(yè)被調(diào)度運(yùn)行時(shí)，(大)時(shí)間片用完之前不會(huì)

17、有搶占調(diào)度，減少了調(diào)度次數(shù)，所以系統(tǒng)開銷小。公平性和饑餓：由于長(zhǎng)作業(yè)最終的時(shí)間片長(zhǎng)，可以減少周轉(zhuǎn)時(shí)間；在發(fā)生一次IO操作后可提升優(yōu)先級(jí)，可以部分抵消“短作業(yè)優(yōu)先”的不公平，也可減輕長(zhǎng)作業(yè)的饑餓程序。選做9.1第7章 ：內(nèi)存1. 什么是重定位，為什么需要重定位，如何實(shí)現(xiàn)重定位？2. P227， 7.12(不做d小題) (刪除"用6位表示頁(yè)號(hào)"描述)1. 什么是重定位，為什么需要重定位，如何實(shí)現(xiàn)重定位？什么是：重定位指在執(zhí)行過(guò)程中，程序在內(nèi)存中的位置發(fā)生了移動(dòng)。（可重定位指代碼在內(nèi)存中移動(dòng)后仍能正確執(zhí)行）為什么需要：為了實(shí)現(xiàn)多道程序設(shè)計(jì)，在內(nèi)存中存在多個(gè)程序，一個(gè)程序一旦被換出

18、內(nèi)存，當(dāng)它再次換入時(shí)可能原來(lái)的位置已經(jīng)被占用，故收到限制，需要找其他空閑的內(nèi)存存放，這時(shí)便需要重定位。如何實(shí)現(xiàn)：代碼中只使用相對(duì)的邏輯地址，不使用絕對(duì)的物理地址，在加載時(shí)根據(jù)分配的物理內(nèi)存地址，由加載工具將代碼中邏輯地址改寫為物理地址；或者在指令執(zhí)行時(shí)由CPU完成邏輯地址到物理地址的轉(zhuǎn)換。重定位：與頁(yè)式管理中邏輯地址物理地址轉(zhuǎn)換無(wú)必然關(guān)系。2. P227， 7.12(不做d小題) (刪除"用6位表示頁(yè)號(hào)"描述)在一個(gè)32位機(jī)器上，假設(shè)把邏輯地址分為8位，6位，6位，12位四個(gè)部分。換句話說(shuō)，系統(tǒng)使用3級(jí)頁(yè)表，其中第一個(gè)8位是第一季，后邊的6位是第二季，以此類推。在這個(gè)系統(tǒng)中

19、，用6位表示頁(yè)號(hào)，假設(shè)內(nèi)存是按照字節(jié)訪問(wèn)的。A), 頁(yè)大小212=4096字節(jié)B), 一個(gè)進(jìn)程的頁(yè)面?zhèn)€數(shù)為220=1M個(gè)C), 邏輯地址空間為232=4GB字節(jié)如題干中，改為“用6位表示頁(yè)框號(hào)”，則D)答案：物理內(nèi)存最大為26 *4K=256K第8章 虛擬內(nèi)存1.解釋下列術(shù)語(yǔ)：抖動(dòng)，TLB，工作集，LRU算法2. P266 8.4 題目印刷錯(cuò)誤1.解釋下列術(shù)語(yǔ)：TLB:存放頁(yè)表內(nèi)容的特殊Cache,一般多采用聯(lián)想寄存器實(shí)現(xiàn)。CPU在地址轉(zhuǎn)換時(shí)，首先檢查該虛擬地址的頁(yè)號(hào)的映射項(xiàng)在TLB中是否存在，TLB命中可大大縮短邏輯地址到物理地址的轉(zhuǎn)換。抖動(dòng)/顛簸：CPU將絕大多數(shù)時(shí)間用在進(jìn)程的換進(jìn)換出而不

20、是執(zhí)行用戶程序的現(xiàn)象。出現(xiàn)抖動(dòng)時(shí)，應(yīng)改進(jìn)替換算法;增加物理內(nèi)存的容量;減少并發(fā)執(zhí)行的進(jìn)程的個(gè)數(shù)。頁(yè)表：是頁(yè)式內(nèi)存管理中使用的數(shù)據(jù)結(jié)構(gòu)，存放邏輯地址到物理地址的映射。工作集(working set)：進(jìn)程在過(guò)去一段時(shí)間內(nèi)所訪問(wèn)頁(yè)面的集合。工作集隨時(shí)間變化而變化。如果一個(gè)進(jìn)程的工作集沒(méi)有在內(nèi)存中，則會(huì)影響進(jìn)程的執(zhí)行效率。LRU算法:頁(yè)式內(nèi)存管理中的替換算法。選擇最近最少使用的頁(yè)替換,即最后一次訪問(wèn)時(shí)間最早的頁(yè)，推測(cè)該頁(yè)在不遠(yuǎn)的將來(lái)被訪問(wèn)的可能性最低。理論分析LRU的準(zhǔn)確性很高，但是實(shí)現(xiàn)復(fù)雜，系統(tǒng)開銷大，實(shí)際使用時(shí)一般采用LRU的簡(jiǎn)化版本。2. P266 8.4 題目印刷錯(cuò)誤P266 8.4 一個(gè)進(jìn)

21、程分配給4個(gè)頁(yè)框（下面的所有數(shù)字均為十進(jìn)制數(shù)，每一項(xiàng)都是從0開始計(jì)數(shù)的）。上一次把一頁(yè)裝入到一個(gè)頁(yè)框的時(shí)間，上一次訪問(wèn)頁(yè)框中的頁(yè)的時(shí)間，每個(gè)頁(yè)框中的虛擬頁(yè)號(hào)以及每個(gè)頁(yè)幀的訪問(wèn)位（R）和修改位（M）如下表所示（時(shí)間均為從進(jìn)程開始到該事件之間的時(shí)鐘時(shí)間，而不是從事件發(fā)生到當(dāng)前的時(shí)鐘值）8.4題目印刷錯(cuò)誤 3-5當(dāng)虛擬頁(yè)4發(fā)生錯(cuò)誤時(shí)，使用下列內(nèi)存管理策略，哪一個(gè)頁(yè)幀將用于置換？解釋原因。 a.FIFO（先進(jìn)先出）算法 b.LRU（最近最少使用）算法 c.Clock算法 d.最佳（使用下面的訪問(wèn)串）算法 e.在頁(yè)錯(cuò)誤之前給定上述內(nèi)存狀態(tài)，考慮下面的虛擬頁(yè)訪問(wèn)序列： 4,0,0,2,4,2,1,0,3,

22、2 如果使用窗口大小為4的工作集策略來(lái)代替固定分配，會(huì)發(fā)生多少頁(yè)錯(cuò)誤？每個(gè)頁(yè)錯(cuò)誤何時(shí)發(fā)生？ P266 8.4題目印刷錯(cuò)誤說(shuō)明：clock算法按“加載時(shí)間”順序查找E)算法：LRU,窗口4時(shí)間單位A).替換頁(yè)框3，因?yàn)槠鋬?nèi)容最早裝入(加載時(shí)間20)B).替換頁(yè)框1， 因?yàn)樽詈笠淮卧L問(wèn)時(shí)間最早(訪問(wèn)時(shí)間160)C).替換頁(yè)框0，因?yàn)檫@個(gè)頁(yè)框是掃描時(shí)最一個(gè)遇到的訪問(wèn)位為0的頁(yè)框D).替換頁(yè)框3，因?yàn)槠鋬?nèi)容(頁(yè)號(hào)3)將來(lái)最晚被訪問(wèn)。4,0,0,0,2,4,2,1,0,3,2E).P266 8.4 工作集策略可變分配！E).P266 8.4 工作集策略工作集窗口示意圖第11章 ：I/O管理和磁盤管理P3

23、63 11.5,11.7（0,1,5級(jí)）,11.8選做：P364,11.3(a),11.7(多少個(gè)扇區(qū)，柱面), 11.8, 11.911.5磁盤讀寫延遲因素：尋道時(shí)間:指磁頭移動(dòng)到指定柱面所需要的時(shí)間；旋轉(zhuǎn)延遲:指要訪問(wèn)的指定扇區(qū)轉(zhuǎn)動(dòng)到磁頭位置所需要的時(shí)間；傳送時(shí)間:指完成對(duì)指定扇區(qū)讀寫操作所需要的時(shí)間。11.7 簡(jiǎn)單定義7個(gè)RAID級(jí)別 RAID（0,1,5級(jí)）0級(jí)：分條，指邏輯上連續(xù)的數(shù)據(jù)被分散存放在多個(gè)可用磁盤中，以后(連續(xù))讀寫時(shí)，可利用多個(gè)磁盤并行工作以縮短操作時(shí)間;1級(jí)：鏡像,指數(shù)據(jù)重復(fù)存放在多個(gè)磁盤中，通過(guò)這種冗余的方式來(lái)提高整體可靠性;5級(jí)：塊分布奇偶校驗(yàn),指邏輯上連續(xù)的數(shù)據(jù)

24、分塊，并計(jì)算逐位奇偶校驗(yàn)和，然后分散到N個(gè)磁盤構(gòu)成的磁盤組中。以后如果組中任一個(gè)磁盤發(fā)生故障，可利用其余N-1個(gè)可用磁盤計(jì)算出故障磁盤中的所有數(shù)據(jù)。(常用：0，1，5及0+1)0：非冗余 1：被鏡像；每個(gè)磁盤都有一個(gè)包含相同數(shù)據(jù)的鏡像磁盤。 2：通過(guò)漢明碼實(shí)現(xiàn)冗余；對(duì)每個(gè)數(shù)據(jù)磁盤中的相應(yīng)都計(jì)算一個(gè)錯(cuò)誤校正碼，并且這個(gè)碼位保存在多個(gè)奇偶校驗(yàn)磁盤中相應(yīng)的文件。 3：交錯(cuò)位奇偶校驗(yàn)；類似于第二層，不同之處在于RAID3為所有數(shù)據(jù)磁盤中同一位置的位的集合計(jì)算一個(gè)簡(jiǎn)單的奇偶校驗(yàn)位，而不是錯(cuò)誤校正碼。 4：交錯(cuò)塊分布奇偶校驗(yàn)；對(duì)每個(gè)數(shù)據(jù)磁盤中相應(yīng)的條帶計(jì)算一個(gè)逐位奇偶。 5：交錯(cuò)塊分布奇偶校驗(yàn)；類似于第四

25、層，但把奇偶校驗(yàn)條帶分布在所有磁盤中。 6：交錯(cuò)塊雙重分布奇偶校驗(yàn)；兩種不同的奇偶校驗(yàn)計(jì)算保存在不同磁盤的不同塊中。11.8 典型磁盤扇區(qū)大?。?12字節(jié)(在今天超大容量磁盤中，真正的物理扇區(qū)的大小是512的2n,如4096，但OS和應(yīng)用程序在邏輯上仍然可以認(rèn)為扇區(qū)為512字節(jié)。)512比特， 比特？512KB11.3a11.7如果磁盤中扇區(qū)大小固定為每扇區(qū)512字節(jié)，并且每磁道128個(gè)扇區(qū)，每面130個(gè)磁道，一共有12個(gè)可用的面，計(jì)算存儲(chǔ)90000條200比特長(zhǎng)的邏輯記錄需要多少磁盤空間（扇區(qū)，磁道和面）.忽略文件頭的記錄和磁道索引，并假設(shè)記錄不能跨越兩個(gè)扇區(qū)。200比特=25字節(jié)，一扇區(qū)5

26、12字節(jié)中，可存放512/25 = 20個(gè)記錄(因記錄不跨扇區(qū)存放)90000記錄需要90000/20=4500個(gè)扇區(qū)。一個(gè)柱面有128*12=1536個(gè)扇區(qū)90000記錄需要4500/1536=2.93=3個(gè)柱面或2個(gè)完整柱面+1428個(gè)扇區(qū) 11.8考慮11.7中的提到的磁盤系統(tǒng)，假設(shè)磁盤轉(zhuǎn)速是1200轉(zhuǎn)/分，磁盤控制器每旋轉(zhuǎn)一圈可以講一個(gè)扇區(qū)讀入其內(nèi)部緩沖區(qū)，接著操作系統(tǒng)以字節(jié)為單位讀取這些數(shù)據(jù)，每讀取一個(gè)字節(jié)，磁盤控制器會(huì)產(chǎn)生一個(gè)中斷A)如果中斷服務(wù)列成處理每個(gè)中斷的時(shí)間是1.8微妙，那么系統(tǒng)讀入整個(gè)扇區(qū)需要花多少時(shí)間？（不考慮尋道所需要花費(fèi)的時(shí)間）1200轉(zhuǎn)/分，則每秒20轉(zhuǎn)一轉(zhuǎn)為1

27、/20秒=50ms題意：“每旋轉(zhuǎn)一圈可以將一個(gè)扇區(qū)讀入內(nèi)部緩沖區(qū)”一字節(jié)一中斷，一扇區(qū)512字節(jié)，中斷512次，共需要時(shí)間：1.8us*512=921.6us=0.92msB)在系統(tǒng)讀取數(shù)據(jù)的過(guò)程匯總，操作系統(tǒng)可以用于處理其他進(jìn)程的時(shí)間是多少？相對(duì)于讀取磁盤的總傳輸時(shí)間？所占的百分比是多少？50ms中0.92ms用于中斷，其余時(shí)間CPU處理其它內(nèi)容，50-0.92=49.08ms百分比： ( 50-0.92)/50 = 98.16%(另外一種理解:磁盤控制器先從盤面將數(shù)據(jù)讀入內(nèi)部緩沖區(qū)(50ms),然后再一個(gè)字節(jié)一個(gè)字節(jié)中斷，共0.92ms，百分比為50/(50+0.92)=98.193%)1

28、1.9再次考慮11.7 11.8中的磁盤系統(tǒng)，假設(shè)磁盤控制器和系統(tǒng)內(nèi)存之間的數(shù)據(jù)傳輸采用DMA方式，總線速度為2MB/S，在該條件下，系統(tǒng)讀入整個(gè)扇區(qū)需要花費(fèi)多少時(shí)間？在這段時(shí)間內(nèi)，操作系統(tǒng)可以用于處理其他進(jìn)程的時(shí)間是多少？總線速度2MB/s，則傳輸一字節(jié)時(shí)間為：1/2M = 0.5s傳512字節(jié)時(shí)間為0.5*512=256s=0.256ms依前例，磁盤控制器準(zhǔn)備一扇區(qū)數(shù)據(jù)需要50ms所以，其它處理時(shí)間為50-0.256=49.744ms百分比：49.744/50=99.49%(與11.8同樣:若考慮磁盤先讀盤面數(shù)據(jù)，然后再DMA傳送，沒(méi)有任何并行，則百分比計(jì)算為：50/(50+.256)第十

29、二章 文件管理 概念文件,文件系統(tǒng),文件目錄文件系統(tǒng)功能，P404 12.10文件(file):(文件系統(tǒng)中)具有符號(hào)名而且在邏輯上具有完整意義的信息項(xiàng)的序列。文件系統(tǒng)：文件與管理文件的方法和程序集合稱作文件系統(tǒng)。文件目錄:包含文件信息的一類特殊文件,文件系統(tǒng)利用其完成從文件名到文件號(hào)(inode)的映射。文件系統(tǒng)功能：建立文件目錄;提供必要的存取方法以適應(yīng)不同應(yīng)用的要求;完成從文件的邏輯組織到物理組織的轉(zhuǎn)換;有效地管理文件在外存的存放;實(shí)現(xiàn)文件保護(hù)和共享;提供對(duì)文件進(jìn)行操作的系統(tǒng)調(diào)用命令.12.10考慮由一個(gè)索引節(jié)點(diǎn)表示的UNIX文件的組織 見(jiàn)圖12.12 假設(shè)有12個(gè)直接快指針，在每個(gè)索引

30、節(jié)點(diǎn)中由一個(gè)一級(jí)，二級(jí)，和三級(jí)間接指針，此外,假設(shè)系統(tǒng)塊大小和磁盤扇區(qū)大小都是8K。如果磁盤塊指針是32位，其中8位用于標(biāo)識(shí)物理磁盤，24位用于標(biāo)識(shí)物理塊，那么A）該系統(tǒng)支持的最大文件大小是多少A)8K*(12+2K+4M+8G)=8K*(8594130956)=70403120791552B)該系統(tǒng)支持的最大文件系統(tǒng)分區(qū)是多少B)8K*224=8K*16M=128GBC)假設(shè)內(nèi)存中除了文件索引節(jié)點(diǎn)外沒(méi)有別的信息，訪問(wèn)在位置13 423 956中的字節(jié)需要多少次磁盤訪問(wèn)？C)文件的索引結(jié)點(diǎn)已讀入哪一塊？13423956 / 8192=1638.66650390625塊號(hào)碼1638前12塊：直接塊前12+2048=2060塊，一級(jí)間接IO次數(shù)：2次，一次讀一級(jí)索引塊，一次讀數(shù)據(jù)塊第六章：并發(fā)死鎖和饑餓1. 什么是死鎖，什么是饑餓？2. 解釋死鎖四個(gè)必要條件的含