計算機學(xué)科專業(yè)基礎(chǔ)綜合計算機操作系統(tǒng)-10

1、計算機學(xué)科專業(yè)基礎(chǔ)綜合計算機操作系統(tǒng) -10（ 總分： 99.99 ，做題時間： 90 分鐘 ）一、 綜合應(yīng)用題 （ 總題數(shù)： 25，分數(shù)： 100.00）1. 創(chuàng)建包含可重定位代碼的程序時， 假定它將裝入內(nèi)存零地址。 在代碼中， 程序引用了下列地址： 50，78， 150，154。如果程序裝入起始地址為 250 的內(nèi)存，這些地址將要如何調(diào)整 ?（分數(shù)： 3.50 ） 所有地址必須增加 250。因此調(diào)整后的地址為 300，328，400，402， 404。2. 考慮一個由 8 個頁面，每頁有 1024B組成的邏輯空間，把它裝入到有 32個物理塊的存儲器中，問：（1）邏輯地址需要多少位表示 ?（

2、 二進制 ）（2）絕對地址需要多少位表示 ?（ 二進制 ）（分數(shù)： 3.50 ） 因為頁面數(shù)為 8=2 3 ，故需要 3 位二進制數(shù)表示。每頁有 1024B，1024=2 10 ，于是頁內(nèi)地址需要 10 位二 進制數(shù)表示。 32個物理塊需要 5位二進制數(shù)表示 （32=2 5 ） 。（1）頁的邏輯地址由頁號和頁內(nèi)地址組成，所以需要3+10=13 位二進制數(shù)表示。（2）頁的絕對地址由塊號和頁內(nèi)地址拼接，所以需要5+10=15 位二進制數(shù)表示。3. 分段保護的方法通常有哪些 ? （分數(shù)： 3.50 ） 分段保護的方法通常有：（1）越界檢查。 在段表寄存器中存放有段表長度信息， 在進行存儲器訪問時將邏

3、輯地址空間的段號與段表長 度進行比較，如段號等于或大于段表長度，將發(fā)出越界中斷信號。（2）存取控制檢查。段表中設(shè)置存取控制字段，用于規(guī)定對該段的訪問方式。4. 覆蓋技術(shù)與虛擬存儲技術(shù)有何本質(zhì)上的不同?交換技術(shù)與虛存中使用的調(diào)入 / 調(diào)出技術(shù)有何相同與不同之處?（分數(shù)： 3.50 ） 覆蓋技術(shù)中，覆蓋段由用戶設(shè)計，用戶自身對內(nèi)存的劃分要參與操作；虛擬存儲技術(shù)是由系統(tǒng)提供邏輯空 間給用戶使用的，而用戶并不真正了解內(nèi)存的情況，物理空間的劃分和管理由系統(tǒng)完成。交換技術(shù)是將內(nèi)存中處于就緒隊列或等待隊列的進程暫時調(diào)出內(nèi)存，放入磁盤空間，以便讓更多的作業(yè)被 選擇進入內(nèi)存，提高系統(tǒng)效率。虛存中使用的調(diào)入調(diào)出技

4、術(shù)是利用磁盤空間對內(nèi)存進行擴充，提供一個大 于實際內(nèi)存的邏輯空間給用戶使用。它們的相同之處是：都將本應(yīng)處于實際內(nèi)存的內(nèi)容調(diào)至輔存，提高系 統(tǒng)效率。不同之處是：交換技術(shù)并未提供大于實際內(nèi)存空間的邏輯空間以供用戶使用，該技術(shù)并不是直接 面向用戶的；而虛存技術(shù)則是提供更大的邏輯空間以供用戶使用，是直接面向用戶的。簡要描述下列存儲器管理方案中操作系統(tǒng)的功能。（分數(shù)： 4.00 ）（1）. 單一絕對分區(qū) （ 使用基址寄存器 ）。單一絕對分區(qū) （ 使用基址寄存器 ） ：系統(tǒng)引導(dǎo)時，操作系統(tǒng)裝入基址寄存器，該寄存器包括用戶程序可訪問 的最低內(nèi)存地址。（2）. 多重可變分區(qū)。多重可變分區(qū)：操作系統(tǒng)必須記錄哪些

5、內(nèi)存已用，哪些是空閑的。當(dāng)進程創(chuàng)建或終止時，操作系統(tǒng)都要更 新內(nèi)存分配的數(shù)據(jù)。在為進程分配內(nèi)存之前，操作系統(tǒng)必須決定把它放在內(nèi)存中的哪個位置。當(dāng)進程獲得 CPU的控制權(quán)時，操作系統(tǒng)必須在重定位寄存器和界限寄存器中分別裝入進程的首地址及其大小。5. 使用可重定位代碼的靜態(tài)分區(qū)方案 （即靜態(tài)重定位 ） 和動態(tài)分區(qū)方案 （即動態(tài)重定位 ）有何相似和不同之 處?分數(shù)： 4.00 ) 兩種方案都使用單一分區(qū)。兩種方案程序都是可重定位的，這樣代碼可以裝入內(nèi)存的任何位置。然而，在 靜態(tài)分區(qū)方案中，程序裝入內(nèi)存時代碼中地址必須調(diào)整并賦給實際內(nèi)存地址。動態(tài)分區(qū)方案中，程序執(zhí)行 過程中要訪問存儲單元時，各個地址賦

6、給實際的存儲單元。某分頁系統(tǒng)的邏輯地址為 16 位，其中高 6 位為頁號，低 10 位為頁內(nèi)地址，則這樣的地址機構(gòu)：(分數(shù)：3.99 )(1) . 一頁有多少字節(jié) ?(分數(shù)： 1.33 ) 頁的大小由頁內(nèi)位移所占的位數(shù)決定，題目中頁內(nèi)地址占 10 位，則頁面大小為 2 10 ，即 1KB。(2) . 邏輯地址有多少頁 ?(分數(shù)： 1.33 ) 頁號的位數(shù)決定了一共有多少頁，題目中頁號占了 6 位，則邏輯地址有 2 6 =64 頁(3) . 一個作業(yè)最大的使用空間是多少字節(jié) ?(分數(shù)： 1.33 ) 邏輯地址的位數(shù)決定了作業(yè)的最大使用空間，邏輯地址有 16位，所以答案是 (2 16 -1) 字節(jié)

7、。 解析 該題 經(jīng)常出現(xiàn)在考卷上，有時以綜合題出現(xiàn)，占分值較多。不管出題形式如何，方法相同，都是考查對于頁號 和頁內(nèi)位移的理解。6. 分段和分頁的主要區(qū)別是什么 ? (分數(shù)： 4.00 )(1) 在分段方式中，程序被分成大小不同的段。在分頁方式中，程序被分成固定大小的頁。(2) 在分段方式中，用戶 ( 或編譯器 ) 負責(zé)把程序分成段。在分頁方式中，操作系統(tǒng)完成分頁操作，該操作對 用戶透明。在某段頁式系統(tǒng)中，虛地址空間包含了 8 個段，段長為 2 29 B。硬件把每個段分成大小為 256B 的頁。問虛 地址中有多少位用于指定：(分數(shù)： 4.00 )(1) . 段號 ?3。由于 8=2 3 ，所以

8、要有 3 位指定段號。(2) . 頁號 ?21。由于頁大小為 256=2 8 B ，一個大小為 2 29 B 的段有 2 29 ÷2 8 =2 21 頁，因此，要有 21 位指定頁號。(3) . 頁內(nèi)偏移量 ?8。要指定大小為 2 8 B 的頁的偏移量，需要 8 位(4) . 整個虛地址 ?32。 3+21+8=32。7. 所謂程序局部性原理是什么 ? (分數(shù)： 4.00 ) 所謂程序局部性原理是指程序在執(zhí)行時所呈現(xiàn)的局部性規(guī)律，即在一段較短時間內(nèi)，程序的執(zhí)行僅限于某 個部分。相應(yīng)地，它所訪問的存儲器空間也局限在某個空間。用一句話回答有關(guān)虛擬存儲器的概念：(1). 虛存的應(yīng)用需求是什

9、么 ?小內(nèi)存中運行大程序。(2). 虛存可行性的基礎(chǔ)是什么 ?程序局部性原理。（3）. 虛存實現(xiàn)的主要技術(shù)是什么 ?部分裝入和部分對換。（4）. 虛存實現(xiàn)的主要支撐硬件是什么 動態(tài)重定位設(shè)施。（5）. 從原理上講，虛存空間大小等于什么CPU邏輯地址給出的大小。8. 在虛擬頁式存儲系統(tǒng)中引入了缺頁中斷，試說明為什么引入缺頁中斷?缺頁中斷的實現(xiàn)由哪幾部分組成，并分別給出其實現(xiàn)方法。（分數(shù)： 4.00 ） 頁式虛存管理是在頁式存儲管理的基礎(chǔ)上實現(xiàn)虛擬存儲器的，作業(yè)在執(zhí)行時并不是所有的頁均放在主存， 若欲訪問的頁面不在主存，則需由操作系統(tǒng)把當(dāng)前所需頁面從輔存裝入主存。這一過程由中斷系統(tǒng)完成， 稱為缺頁

10、中斷。缺頁中斷由缺頁處理和頁面淘汰組成，過程具體參見計算機考研考點精講及復(fù)習(xí)指導(dǎo)一書中對應(yīng)章節(jié) 的“考點精講”。9. 請求頁式管理系統(tǒng)中是否存在外零頭 （又叫外部碎片 ）和內(nèi)零頭 （又叫內(nèi)部碎片 ）? （分數(shù)： 4.00 ）頁式管理的優(yōu)點是將程序和內(nèi)存都等分成較小的單位，有利于存儲空間的使用。并不能保證所有的程序都 是頁面大小的整數(shù)倍，因此盡管所有頁面都可分配（即沒有外零頭 ） ，但在程序的最后一個頁面肯定會有若干空白字節(jié)，這就是內(nèi)零頭。10. 請求頁式存儲管理系統(tǒng)中，若把頁面的大小增加一倍，缺頁中斷次數(shù)會減少一半嗎?為什么 ?（分數(shù)： 4.00 ） 不會。缺頁中斷次數(shù)根據(jù)訪問串的具體內(nèi)容不同

11、而變化。頁面大小增加一倍，在某種程度上可以減少頁故 障數(shù)，但不一定成比例關(guān)系。11. 在請求頁式存儲管理系統(tǒng)中，頁面淘汰所花費的時間為什么屬于系統(tǒng)開銷 ?（分數(shù)： 4.00 ） 頁面淘汰要產(chǎn)生一次中斷，以進行頁面替換，按照調(diào)度策略將內(nèi)存中某頁換出主存，再將磁盤上某頁調(diào)入 主存，這是一次中斷處理過程，因此應(yīng)屬于系統(tǒng)開銷。在一個采用頁式虛擬存儲管理的系統(tǒng)中，某進程依次要訪問的字地址序列是：115，228 ，128，88，446 ，102，321，432，260，167，若作業(yè)的第 0頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的主存共300 字，頁的大小為100字，回答下列問題：（分數(shù)： 4.00 ）（1）.

12、按 FIFO 調(diào)度算法將產(chǎn)生多少次缺頁中斷，依次淘汰的頁號是什么 ?如表 1所示， FIFO算法產(chǎn)生 5 次缺頁中斷，淘汰的頁號依次是 0，1，2 表 1 FIFO 算法（2）. 按 LRU調(diào)度算法將產(chǎn)生多少次缺頁中斷，依次淘汰的頁號是什么如表 2所示， LRU算法產(chǎn)生 6 次缺頁中斷，淘汰的頁號依次是 2，0，1，3 表 2 LRU 算法先將地址序列轉(zhuǎn)換成訪問串，因為每頁有 100 字，所以訪問串就是地址除 100 取整后得到的數(shù)字；又，題 目給了 300 字，說明該作業(yè)在主存獲得 3 個駐留集。下面給出兩種算法的淘汰過程， 其中第 0 頁已在主存， 符號“×”代表產(chǎn)生頁故障 （以

13、下各題相同 ）。 解析 該類題目在有的試卷上是以綜合題的形式出現(xiàn)，不 管分值大小，只要牢記每種頁面替換策略的方法即可。12. 假定占有 M塊內(nèi)在 （ 初始為空 ） 的進程有一個頁訪問串，這個頁訪問串的長度為P，其中涉及 Q個不同的頁號。對于任何頁面替換算法，計算出：（1） 缺頁中斷次數(shù)的下界是多少 ?（2） 缺頁中斷次數(shù)的上界是多少 ?（分數(shù)： 4.00 ） 對于任何頁面替換算法， 缺頁中斷次數(shù)的下界是 Q，缺頁中斷次數(shù)的上界是 P。發(fā)生缺頁中斷的原因是當(dāng)前 訪問的頁不在內(nèi)存中， 需進行頁面調(diào)度， 將該頁面調(diào)入主存，此時不管內(nèi)存中是否已滿 （ 若滿則選擇調(diào)出一 頁，若不滿則可直接調(diào)入 ） ，都

14、要發(fā)生一次缺頁中斷，故無論怎樣安排， Q個不同頁號在初次進入主存時都 要發(fā)生一次缺頁中斷，總共發(fā)生 Q次。再討論上限為什么是 P。在進行頁面調(diào)度時， 進入內(nèi)存的頁面不可能永久占有內(nèi)存， 會在某個時刻被調(diào)出， 最壞的情況是每當(dāng)訪問一個頁面，該頁都不在主存，都要產(chǎn)生一次缺頁中斷；所以會發(fā)生P 次中斷，舉例如下：下限： M=2，P=12， Q=4，有如下訪問串：1 1 1 2 2 3 3 3 4 4 4 4缺頁中斷數(shù)為 4；上限： M=2，P=12， Q=4，有如下訪問串：1 2 3 4 1 2 3 4 1 2 3 4缺頁中斷數(shù)為 12。 解析 本題考的是對頁面替換整體概念的理解。對于任何一個算法而

15、言，衡量其優(yōu)劣 的標(biāo)準(zhǔn)并不是頁故障的多少，因為頁故障數(shù)是隨著訪問串的內(nèi)容變化而發(fā)生變化的，本題就是要說明這一 點。13. 頁面調(diào)度算法中有 LRU、FIFO和 Clock 算法。針對以下條件，計算上述 3 個算法下的頁面調(diào)度過程和缺 頁中斷率，并分析為什么在 3 種算法中 Clock 算法應(yīng)用得比較廣泛：頁面訪問序列： 2，3，2，1，5， 2，4，5，3，2，5，2分配內(nèi)存塊： 3 塊（分數(shù)： 4.00 ）LRU算法（見表 1） ： 表 1 LRU 算法中斷率： 7/12FIFO算法（見表 2）：表 2 FIFO 算法中斷率： 9/12Clock 算法（見表 3） ：表 3 Clock 算法

16、中斷率： 8/12在頁面調(diào)度算法中， OPT算法理論最優(yōu)但無法實現(xiàn)， LRU算法性能幾乎和 OPT一樣，但是實現(xiàn)相當(dāng)困難，系 統(tǒng)開銷非常大，此外，雖然 FIFO 算法簡單易行，但是性能較差。相比之述算法，Clock 算法是 LRU算法的變種，通過為每一塊附加一個附加位記錄該內(nèi)存塊的使用情況， 比較小的開銷接近了 LRU的性能，故 Clock 算法相對而言應(yīng)用比較廣泛。14. 某程序訪問下列頁而： 0，9，0，1，8， 1，8，7，8，7，1，2，8，2，7，8，2，3，8，3，如果程序有3 個頁幀可用且使剛下列算法，將會產(chǎn)生多少次缺頁：(1)FWO替換算法。(2)LRU 替換算法。(3) OP

17、T 替換算法。(分數(shù)： 4.00 ) 如下表所示(1)FIFO 替換算法產(chǎn)生 8 個缺頁。(2)LRU 替換算法產(chǎn)生 9 個缺頁。(3) OPT 替換算法產(chǎn)生 7 個缺頁。有一個請求頁式系統(tǒng)，幀數(shù)占 4B，頁大小為 256B，使用 LRU頁面替換算法，每個進程分配 3 個頁幀。一個 進程執(zhí)行下列代碼：inta=new int200200;int i=0;int j=0;while(i+ < 200) j=0;while(j+ < 200)aij=0;這段代碼占用第 0頁，由于每條指令都訪問第 0頁，第 0頁總是被裝入。變量 i 和 j 都存儲在快速寄存器 中。(分數(shù)： 4.00 )

18、(1). 假設(shè)數(shù)組的所有元素都存儲在連續(xù)的內(nèi)存區(qū)域中，那么數(shù)組需要多少頁 ?數(shù)組有 200×200=40000 元素，每個元素需要 4B的存儲空間。 160000B占用 625 頁 (2). 這個程序?qū)a(chǎn)生多少個缺頁 ?程序按數(shù)組元素的存儲順序訪問數(shù)組。因此，它將換入指令頁，同時 625 個數(shù)據(jù)頁每頁都對應(yīng)一次換入， 故總共是 626 次換入。15. 如下程序在頁式虛存系統(tǒng)中執(zhí)行，程序代碼位于虛空間頁，A為 128×128 的數(shù)組，在虛空間以行主秩序存放 A(1，1)，A(1，2)，每頁放 128個數(shù)組元素。 工作集大小為 2個頁幀 (開始時程序代碼已在內(nèi)存， 占了 1個頁

19、幀) ，用 LRU算法，下面兩種對 A初始化的程序引起的頁故障數(shù)分別為 和。第一空： for j:=1 to 128 do for i:=1 to 128 doA(i,j):=0;第二空：for i:=1 to 128 dofor j:=110 128 doA(i,j):=0;(分數(shù)： 4.00 )第1個空是 128×128，第 2個空是 128。計算頁故障數(shù)首先應(yīng)給出訪問串，其次是清楚是哪種替換策略。 本題中所給的替換策略無效， 因為任何一個替換策略在只有一個頁幀的情況下產(chǎn)生的頁故障數(shù)都是一樣的， 等于訪問串中連續(xù)不相等頁號的個數(shù)。如訪問串為1，2，3， 4，5，則故障數(shù)為 5。(

20、1) 中給出的循環(huán)條件要求訪問的次序為：A（1 ，1） ，A（2，1） ，A（128，1），A（1，2），A（2，2），A（128，2），A（1，128），A（2，128）， A（128 ，128） ；根據(jù)行主秩序存放的條件，訪問串為 1，2，3，128，1，2，3，128，即重復(fù) 128遍 128個不 同的頁號，則結(jié)果為 128 ×128。（2） 中給出的循環(huán)條件要求訪問的次序為：A（1，1），A（1，2）， A（1，128），A（2，1），A（2，2），A（2，128），A（128，1），A（128，2）， A（128 ，128） ；根據(jù)行主秩序存放的條件，訪問串為 1，2， 1

21、28（重復(fù)的頁號合并 ），結(jié)果為 128。 解析 本題考的是 頁面替換策略中頁故障數(shù)的計算方法，此類題目通常的出題方式是直接給出訪問串，要求按照某替換算法 計算頁故障數(shù)，但像本題這樣的方式也時有發(fā)生。在某簡單分段系統(tǒng)中， 給定下列段表 （下表 ） ，試計算每個邏輯地址的物理地址。 如果地址產(chǎn)生了分段錯誤， 請指明。段基址長度033012418762112111993498302(1).0 ， 99 429。偏移量 99 小于段長 124。段 0 從位置 330 開始，所以偏移量 99 的物理地址為 99+330=429（2）.2 ，78189。偏移量 78 小于段長 99。段 2 從位置 11

22、1 開始，所以偏移量 78 的物理地址為 78+111=189（3）.1 ， 265錯誤。偏移量 256 大于段長 211。該地址造成分段錯誤（4）.3 ， 222 720。偏移量 222 小于段長 302。段 3從位置 498 開始，所以偏移量 222 的物理地址為 222+498=720（5）.0 ， 111 441。偏移量 111 小于段長 124。段 0從位置 330 開始，所以偏移量 111 的物理地址為 111+330=44116. 現(xiàn)有一個作業(yè)，在段式存儲管理的系統(tǒng)中已為其主存分配，建立的段表內(nèi)容見表。段號主存起始地址段長度0120401760302 480203 37020計算

23、邏輯地址 （2，15），（0，60），（3，18） 的絕對地址是多少 ? 注：括號中第 1個元素為段號，第 2 個元素為段內(nèi)地址。 （分數(shù)： 4.00 ） 段式存儲管理的地址轉(zhuǎn)換過程為：（1） 根據(jù)邏輯地址中的段號查段表的相應(yīng)欄目；（2） 根據(jù)段內(nèi)地址段長度查地址是否越界；+段內(nèi)地址。（3）若不越界，則絕對地址的計算方法為：該段的主存起始地址邏輯地址 （2 ，15）查段表得段長度為 20，段內(nèi)地址 15<20，地址不越界， 段號 2 查段表得段首地址為 480， 于是絕對地址為 480+15=495。邏輯地址 （0 ， 60） 查段表得段長度為 40，段內(nèi)地址 60>40，地址越界，系統(tǒng)發(fā)出“地址越界”中斷。邏輯地址 （3 ，18）查段表得段長度為 20，段內(nèi)地址 18<20，地址不越界， 段號 3 查段表得段首地址為 370， 于是絕對地址 =370+18=388。17. 某系統(tǒng)使用分頁和分段，通過查找相聯(lián)表訪問已