計算機操作系統(tǒng)典型例題解析之四

1、計算機操作系統(tǒng)典型例題解析之四【例1】可變分區(qū)存儲管理系統(tǒng)中，若采用最佳適應(yīng)分配算法，“空閑區(qū)表”中的空閑區(qū)可按（A ）順序排列。A、長度遞增B、長度遞減C、地址遞增D、地址遞減分析：最佳適應(yīng)算法要求每次都分配給用戶進程能夠滿足其要求的空閑區(qū)中最小的空閑區(qū)， 所以為了提高算法效率，我們把所有的空閑區(qū)，按其大小以遞增的順序形成一空閑分區(qū)鏈。 這樣，第一個找到的滿足要求的空閑區(qū)，必然是符合要求中最小的。所以本題的答案是A?！纠?】虛擬存儲技術(shù)是（B）oA、擴充主存物理空間技術(shù) B、擴充主存邏輯地址空間技術(shù)C、擴充外存空間的技術(shù) D、擴充輸入/輸出緩沖區(qū)技術(shù)分析：所謂虛擬存儲器，是指僅把作業(yè)的一部分

2、裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)。具體地說，所謂虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。 實際上，用戶所看到的大容量只是一種感覺，是虛的，故稱之為虛擬存儲器。虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)、故被廣泛地應(yīng)用于大、中、小型機器和微型機中。所以本題的答案是Bo【例3】很好地解決了“零頭”問題的存儲管理方法是（ A ）oA、分頁存儲管理方式B、分段存儲管理方式 C、多重分區(qū)管理D、可變式分區(qū)管理分析：“零頭”也就是內(nèi)存碎片，是指內(nèi)存中無法被利用的小空閑區(qū)。在有些內(nèi)存管理 方式下，系統(tǒng)運行一段時間后，內(nèi)存的碎片會占據(jù)相當?shù)臄?shù)量的空間。分段存

3、儲管理方式、 多重分區(qū)管理、可變式分區(qū)管理都會因為內(nèi)存分配回收產(chǎn)生“零頭”，而分頁存儲管理方式，按事先劃分好的內(nèi)存塊為單位分配回收內(nèi)存，所以不會產(chǎn)生“零頭”。所以本題的答案是 A【例4】系統(tǒng)“抖動”現(xiàn)象的發(fā)生是由（B ）引起的。A、交換的信息量過大B、置換算法選擇不當 C、內(nèi)存容量不足D、請求分頁管理方案分析：“抖動”現(xiàn)象是指剛被換出的頁很快又要被訪問，為此，又要換出其他頁，而該頁又 很快被訪問，如此頻繁地置換頁面， 以致大部分時間都花在頁面置換上。交換的信息量過大，內(nèi)存容量不足都不是引起系統(tǒng)“抖動”現(xiàn)象的原因，而選擇的置換算法不當才是引起“抖動” 現(xiàn)象的根本原因，例如，先進先出算法就可能產(chǎn)生

4、“抖動”現(xiàn)象。所以本題的答案是Bo【例5】虛擬存儲管理系統(tǒng)的基礎(chǔ)是程序的（C）理論。A、全局性B 、虛擬性C局部性D 、動態(tài)性分析：虛擬存儲技術(shù)是基于程序的局部性原理的，程序的局部性原理體現(xiàn)在兩個方面： 時間局部性和空間局部性。 時間局部性是指一條指令被執(zhí)行后，那么它可能很快會再次被執(zhí)行，空間局部性是指若某一存儲單元被訪問，那么與該存儲單元相鄰的單元可能也會很快被訪問。所以本題的答案是 Co【例6】簡述頁和段的區(qū)別。答：分頁和分段有許多相似之處，但是在概念上兩者完全不通，主要表現(xiàn)在：頁是信息的物理單位， 分頁是為了系統(tǒng)管理內(nèi)存的方便而進行的，故對用戶而言，分頁是不可見的，是透明的；段是信息的邏

5、輯單位，分段是作業(yè)邏輯上的要求，對用戶而言， 分段是可見的。頁的大小是固定的，由系統(tǒng)決定；段的大小是不固定的，由用戶作業(yè)本身決定。從用戶角度看，分頁的地址空間是一維的，而段的地址空間是二維的?！纠?】內(nèi)存保護是否可以完全由軟件來實現(xiàn)？為什么？答：內(nèi)存保護的主要任務(wù)是確保每道程序都只在自己的內(nèi)存內(nèi)運行。這就要求系統(tǒng)能對每條指令所訪問的地址進行越界檢查。若發(fā)生越界，系統(tǒng)應(yīng)能立即發(fā)現(xiàn)，并發(fā)出越界中斷請求，以終止該指令。若每次檢查完全用軟件來實現(xiàn)，則每執(zhí)行一條指令，都要增加若干條指 令去執(zhí)行越界的檢查功能，這無疑將降低程序的執(zhí)行速度，因此，越界檢查通常由硬件實現(xiàn)，并使指令的執(zhí)行與越界檢查功能并行執(zhí)行，

6、從而不使程序的運行速度降低。當然，對發(fā)現(xiàn)有越界后的處理需要與軟件配合來完成。因此說內(nèi)存保護功能是由硬件和軟件共同完成的?！纠?】用可變分區(qū)方式管理主存時，假定主存中按地址順序依次有五個空閑區(qū)，空閑區(qū)的大小為 32K，10K，5K，228K，100K?，F(xiàn)有五個作業(yè) J1，J2, J3, J4和J5。它們各 需主存11K, 10K , 108K , 28K , 115K。若采用首次適應(yīng)分配算法能把這五個作業(yè)按J1J5的次序全部裝入主存嗎？你認為按怎樣的次序裝入這五個作業(yè)可時主存空間的利用率最 高？答：最先適應(yīng)分配算法能把這五個作業(yè)按J1J5的次序全部裝入主存時，J1、J2分割第一個空閑區(qū)，剩 11

7、K; J3、J4分割第四個空閑區(qū)，剩 92K; J5無法裝入，所以用最先適 應(yīng)分配算法不能把這五個作業(yè)按J1J5的次序全部裝入主存。如果先裝入J3,裝入第四個空閑區(qū)，剩余空間 120K ;再裝入J5,裝入第四個空閑區(qū)， 剩余空間5K ;再裝入J4,裝入第一個空閑區(qū)，剩余 4K ;再裝入J1, J1裝入第五個空閑區(qū)， 剩余空間104K ;再裝入J2，裝入第二個空閑區(qū)，這樣效率最好。【例9】簡述什么是覆蓋？什么是交換？覆蓋和交換的區(qū)別是什么？答：所謂覆蓋，是指同一主存區(qū)可以被不同的程序段重復(fù)使用。通常一個作業(yè)由若干個功能上相互獨立的程序段組成， 作業(yè)在一次運行時，也只用到其中的幾段，利用這樣一個事

8、 實，我們就可以讓那些不會同時執(zhí)行的程序段共用同一個主存區(qū)。所謂交換，就是系統(tǒng)根據(jù)需要把主存中暫時不運行的某個(或某些)作業(yè)部分或全部移到外存，而把外存中的某個 (或某些)作業(yè)移到相應(yīng)的主存區(qū)，并使其投入運行。覆蓋技術(shù)要求程序員必須把一個程序劃分成不同的程序段，并規(guī)定好它們的執(zhí)行和覆蓋順序，操作系統(tǒng)根據(jù)程序員提供的覆蓋結(jié)構(gòu)來完成程序之間的覆蓋。覆蓋主要在同一個作業(yè)或同一個進程內(nèi)進行； 而交換主要是在進程或作業(yè)之間進行。 另外，覆蓋只能覆蓋那些與覆 蓋程序段無關(guān)的程序段。【例10】對一個將頁表放在內(nèi)存中的分頁系統(tǒng)：(1) 如果訪問內(nèi)存需要 0.2卩s，有效訪問時間為多少？(2) 如果增加一個快表

9、，且假定在快表中找到頁表項的幾率高達90 %，則有效訪問時間又是多少(假定查找快報需花的時間為0)?分析：每次訪問數(shù)據(jù)時，若不使用快表，則需要兩次訪問內(nèi)存，即先從內(nèi)存的頁表中讀 出頁對應(yīng)的塊號，然后再根據(jù)形成的物理地址去存取數(shù)據(jù)；使用快表時，若能從快表中直接找到對應(yīng)的頁表項，則可立即形成物理地址去訪問相應(yīng)的數(shù)據(jù)，否則，仍需兩次訪問內(nèi)存。答： (1)有效訪問時間為：2X 0.2=0.4卩s(2)有效訪問時間為：0.9X 0.2+ (1 0.9)X 2X 0.2=0.22 卩 s【例11】某系統(tǒng)采用分頁存儲管理方式，擁有邏輯空間32頁，每頁2K,擁有物理空間1M。(1 )寫出邏輯地址的格式。(2)

10、若不考慮訪問權(quán)限等，進程的頁表項有多少項？每項至少有多少位？ ( 3)如果物理空間減少一半，頁表結(jié)構(gòu)應(yīng)相應(yīng)作怎樣的改變？答：該系統(tǒng)擁有邏輯空間 32頁，故邏輯地址中頁號必須用5位來描述；而每頁為 2k,因此，頁內(nèi)地址必須用 11位來描述，這樣可得到它的邏輯地址格式如下：1511 100頁號頁內(nèi)位移(2)每個進程最多有32個頁面，因此，進程的頁表項最多為 32項；若不考慮訪問權(quán)限等， 則頁表項中只需給出頁所對應(yīng)的物理塊號，1M的物理空間可分成 29個物理塊，故每個頁表項至少有9位。（3）如果物理空間減少一半，則頁表中頁表項數(shù)仍不變，但每項的長度可減少1位?！纠?2】在分頁存儲管理系統(tǒng)中，邏輯地址

11、的長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH且第0、1、2頁依次存放在物理塊 5、10、11中，問相應(yīng)的物理地址 是多少？分析：在分頁存儲管理系統(tǒng)中進行地址轉(zhuǎn)換時，地址變換機構(gòu)將自動把邏輯地址轉(zhuǎn)化為頁號和頁內(nèi)地址，如果頁號不小于頁表長度，則產(chǎn)生越界中斷；否則便以頁號為索引去檢索頁表，從中得到對應(yīng)的塊號，并把塊號和頁內(nèi)位移分別送入物理地址寄存器的塊號和塊內(nèi)位移字段中，形成物理地址。答：由題目所給條件可知，分頁存儲管理系統(tǒng)的邏輯地址結(jié)構(gòu)為：1512110頁號頁內(nèi)位移邏輯地址2F6AH的二進制表示如下：0010 111101101010 頁號 頁內(nèi)位移由此可知邏輯地址 2F6A

12、H的頁號為2,小于頁表長度 3,沒有越界，該頁存放在第 11個 物理塊中，用十六進制表示塊號為B，所以物理地址為 BF6AH。【例13】什么是虛擬存儲器？如何實現(xiàn)分頁虛擬存儲管理系統(tǒng)？答：所謂虛擬存儲器，是指僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)。具體地說，所謂虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。要實現(xiàn)分頁虛擬存儲管理系統(tǒng)，首先要擴充頁表，擴充后的頁表是在原來頁表的基礎(chǔ)上發(fā)展起來的，包括以下內(nèi)容：頁號、物理塊號、狀態(tài)位、訪問位、修改位、外存地址。其中 狀態(tài)位表示該頁是否已經(jīng)調(diào)入內(nèi)存；訪問位表示該頁在內(nèi)存期間是否被訪問過；修改位表示該

13、頁在內(nèi)存中是否被修改過，若未被修改，則在置換該頁時就不需將該頁寫回到外存，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則在置換該頁時必須把該頁寫回到外存，以保證外存中所保留的始終是最新副本；外存地址用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入該頁時使用。另外，還要使用兩項關(guān)鍵技術(shù)：請求調(diào)頁技術(shù)和頁面置換技術(shù)?！纠?4】在分頁虛擬存儲管理系統(tǒng)中， 為什么說一條指令執(zhí)行期間可能產(chǎn)生多次缺頁中斷？答：因分頁虛擬管理方式中，只要作業(yè)的部分頁在內(nèi)存，該作業(yè)就能執(zhí)行，而在執(zhí)行過程中發(fā)現(xiàn)所要訪問的指令或者數(shù)據(jù)不在內(nèi)存時，則產(chǎn)生缺頁中斷，將所需的頁面調(diào)入內(nèi)存。在分頁虛擬存儲管理系統(tǒng)中，一條指令（如Co

14、py A to B）可能跨了兩個頁，而其中要訪問的操作數(shù)可能也跨了兩個頁。當要執(zhí)行這類指令，而相應(yīng)的頁都不在內(nèi)存時，就將產(chǎn)生多次缺頁中斷（如 Copy A to B可能產(chǎn)生6次缺頁中斷）。【例15】在分頁虛擬存儲管理系統(tǒng)中，假定系統(tǒng)為某進程分配了四個主存塊（將開始4頁先裝入主存），頁的引用順序為：7，1，2，0，3，0，4，2，3，0，3，2，7，0，1，若采 用FIFO調(diào)度算法、LRU調(diào)度算法時分別產(chǎn)生多少次缺頁中斷？依次淘汰的頁分是什么？答：按照先進先出算法的原則：當發(fā)生缺頁中斷時，將淘汰最先調(diào)入主存的頁面:發(fā)生了 3次缺頁中斷，依次淘汰的頁位7、1、4?！纠?6】現(xiàn)有一分頁虛擬存取管理系

15、統(tǒng)，其頁表保存在寄存器中。若有一個可用的空頁或被替換的頁未被修改，則它處理一個缺頁中斷需要8mso如果被替換的頁已被修改，則處理一個缺頁中斷需要 20ms內(nèi)存存取時間為1卩S。假定70%被替換的頁被修改過，為保證有效存取時間不超過 2卩s,可接受的最大缺頁率是多少？分析：因為頁表放在寄存器里，所以訪問頁表的時間可以忽略不計。則存取時間就包括內(nèi)存存取時間和處理缺頁中斷的時間。答：如果用P表示缺頁率，則有效訪問時間不超過2卩s可表示為：（1-p） X 1 卩 s + px （0.7 x 20ms+ 0.3 x 8ms+ 1 卩 s） < 2 卩 s因此可計算出：pw 1/164000.000

16、06練習題及參考答案一、單項選擇題1. 位示圖法可用于（C ）oA、頁式虛擬存儲管理中頁面置換B、可變式分區(qū)存儲管理中空閑區(qū)的分配和回收C、分頁式存儲管理中主存空閑塊的分配和回收D、文件目錄的查找2下列（A ）存儲方式不能實現(xiàn)虛擬存儲器。A、分區(qū)B、頁式C、段式D、段頁式3. 操作系統(tǒng)處理缺頁中斷時，選擇一種好的調(diào)度算法對主存和輔存中的信息進行高效調(diào)度 盡可能地避免（D ）oA、碎片B、CPU空閑C、多重中斷D、抖動4. 分頁式存儲管理的主要特點是（C ）oA、要求處理缺頁中斷B、要求擴充主存容量C、不要求作業(yè)裝入到主存的連續(xù)區(qū)域D、不要求作業(yè)全部同時裝人主存5. LRU頁面調(diào)度算法淘汰（B

17、）的頁。A、最近最少使用B、最近最久未使用C、最先進入主存D、將來最久使用6. 虛擬存儲器實際容量受（B ）限制。A、物理主存的大小B、計算機的地址結(jié)構(gòu)C、磁盤容量D、數(shù)據(jù)存放的絕對地址7分區(qū)管理要求對每一個作業(yè)都分配（A）的主存單元。A、地址連續(xù)B、若干地址不連續(xù)的C、若干連續(xù)的頁D、若干不連續(xù)的幀&頁面置換算法中（A ）不是基于程序執(zhí)行的局部性理論。A、先進先出調(diào)度算法B、LRUC、LFUD、最近最不常用調(diào)度算法9.在存儲管理中，采用覆蓋與交換技術(shù)的目的是（A ）。A、節(jié)省主存空間B、物理上擴充主存容量C、提高CPU的效率 D、實現(xiàn)主存共享10分頁虛擬存儲管理中，缺頁中斷時，欲調(diào)度

18、一頁進入主存中，內(nèi)存己無空閑塊，如何決 定淘汰已在主存的塊時，（B ）的選擇是很重要的。A、地址變換B、頁面調(diào)度算法C、對換方式D、覆蓋技術(shù)11動態(tài)重定位技術(shù)依賴于( B )。A、重定位裝入程序B、重定位寄存器C、地址結(jié)構(gòu)D、目標程序12. ( D)存儲管理兼顧了段式在邏輯上清晰和頁式在存儲管理上方便的優(yōu)點。A、分段B、分頁C、可變分區(qū)方式D、段頁式13. 在可變分區(qū)存儲管理中， 某作業(yè)完成后要收回其主存空間， 該空間可能與相鄰空閑區(qū)合 并，修改空閑區(qū)表使空閑區(qū)始址改變但空閑區(qū)數(shù)不變的是( C )情況。A、有上鄰空閑區(qū)也有下鄰空閑區(qū)B、有上鄰空閑區(qū)但無下鄰空閑區(qū)C、無上鄰空閑區(qū)但有下鄰空閑區(qū)D

19、、無上鄰空閑區(qū)且也無下鄰空閑區(qū)14. 可變分區(qū)管理中，首次適應(yīng)分配算法可將空閑區(qū)表中的空閑區(qū)欄目按(A )順序排列。A、地址遞增B、長度遞增C、地址遞減D、長度遞減15. 在固定分區(qū)分配中，每個分區(qū)的大小是(C )。A、隨作業(yè)長度變化B、相同C、可以不同但預(yù)先固定D、可以不同但根據(jù)作業(yè)長度固定16. 存儲管理主要管理的是(C )。A、外存存儲器用戶區(qū)B、外存存儲器系統(tǒng)區(qū)C主存儲器用戶區(qū)17. 下述( B )頁面置換算法會產(chǎn)生 Belady 現(xiàn)象。A、最佳置換算法B、先進先出算法C LRU算法18. 作業(yè)執(zhí)行中發(fā)生了缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行(A、被中斷的前一條B、被中斷的后一條19

20、 可變分區(qū)方式常用的主存分配算法中， (A、最佳適應(yīng)算法 B、首次適應(yīng)算法20 可變分區(qū)方式常用的主存分配算法中， (A、最佳適應(yīng)算法B、首次適應(yīng)算法二、多項選擇題A)CC)D 、主存儲器系統(tǒng)區(qū)、 Clock 算法C )指令。、啟動時的第一條總是找到能滿足作業(yè)要求的最小空閑區(qū)分配。C被中斷的、最壞適應(yīng)算法 D 、循環(huán)首次適應(yīng)算法總是找到能滿足作業(yè)要求的最大空閑區(qū)分配。C最壞適應(yīng)算法D 、循環(huán)首次適應(yīng)算法1. 不需硬件地址轉(zhuǎn)換機構(gòu)支撐的存儲管理方式是(AD )。A、單用戶連續(xù)方式B、可變分區(qū)方式C、頁式和段式D、固定分區(qū)方式E、段頁式2. 可用上下界限寄存器實現(xiàn)存儲保護的是(ACE )存儲管理。A、分段 B、段頁式C、可變分區(qū)D、分頁E、固定分區(qū)3. 在下列存儲器管理方案中，能實現(xiàn)虛擬存儲的是(CD )A、分區(qū)管理B、分頁存儲管理 C、請求分頁存儲管理D、請求分段存儲管理E、段頁式存儲管理4. 在下列算法中，可用于頁面置換算法的是(ABE )。A、先進先出算法B、LRU算法C、優(yōu)先級高者優(yōu)先算法D、時間片輪轉(zhuǎn)法E、 Clock 算法三、填空題 1 .在存儲器管理中，頁是信息的 物理 單位，段是信息的 邏輯 單位。頁面大小由 系統(tǒng) 確定， 段的大小由 _用戶作業(yè)本身 確定。2. 將作業(yè)地址空間