操作系統(tǒng)精髓與設(shè)計(jì)原理-第7章

1、第7章內(nèi)存管理復(fù)習(xí)題：內(nèi)存管理需要滿足哪些需求？答：重定位、保護(hù)、共享、邏輯組織和物理組織。為什么需要重定位進(jìn)程的能力？答：通常情況下，并不能事先知道在某個(gè)程序執(zhí)行期間會(huì)有哪個(gè)程序駐留在主存中。此外還希望通過提供一個(gè)巨大的就緒進(jìn)程池，能夠把活動(dòng)進(jìn)程換入和換出主存，以便 使處理器的利用率最大化。在這兩種情況下，進(jìn)程在主存中的確切位置是不可預(yù)知的。為什么不可能在編譯時(shí)實(shí)施內(nèi)存保護(hù)？答：由于程序在主存中的位置是不可預(yù)測(cè)的，因而在編譯時(shí)不可能檢查絕對(duì)地址來確 保保護(hù)。并且，大多數(shù)程序設(shè)計(jì)語言允許在運(yùn)行時(shí)進(jìn)行地址的動(dòng)態(tài)計(jì)算（例如，通過 計(jì)算數(shù)組下標(biāo)或數(shù)據(jù)結(jié)構(gòu)中的指針）。因此，必須在運(yùn)行時(shí)檢查進(jìn)程產(chǎn)生的所

2、有存儲(chǔ) 器訪問，以便確保它們只訪問了分配給該進(jìn)程的存儲(chǔ)空間。允許兩個(gè)或多個(gè)進(jìn)程訪問進(jìn)程的某一特定區(qū)域的原因是什么？答：如果許多進(jìn)程正在執(zhí)行同一程序，則允許每個(gè)進(jìn)程訪問該程序的同一個(gè)副本要比 讓每個(gè)進(jìn)程有自己?jiǎn)为?dú)的副本更有優(yōu)勢(shì)。同樣，合作完成同一任務(wù)的進(jìn)程可能需要共 享訪問同一個(gè)數(shù)據(jù)結(jié)構(gòu)。在固定分區(qū)方案中，使用大小不等的分區(qū)有什么好處？答：通過使用大小不等的固定分區(qū)：1.可以在提供很多分區(qū)的同時(shí)提供一到兩個(gè)非常 大的分區(qū)。大的分區(qū)允許將很大的進(jìn)程全部載入主存中。2.由于小的進(jìn)程可以被放入 小的分區(qū)中，從而減少了內(nèi)部碎片。M.內(nèi)部碎片和外部碎片有什么區(qū)別？答：內(nèi)部碎片是指由于被裝入的數(shù)據(jù)塊小于分區(qū)

3、大小而導(dǎo)致的分區(qū)內(nèi)部所浪費(fèi)的空間。外部碎片是與動(dòng)態(tài)分區(qū)相關(guān)的一種現(xiàn)象，它是指在所有分區(qū)外的存儲(chǔ)空間會(huì)變成 越來越多的碎片的。邏輯地址、相對(duì)地址和物理地址間有什么區(qū)別？答：邏輯地址是指與當(dāng)前數(shù)據(jù)在內(nèi)存中的物理分配地址無關(guān)的訪問地址，在執(zhí)行對(duì)內(nèi) 存的訪問之前必須把它轉(zhuǎn)化成物理地址。相對(duì)地址是邏輯地址的一個(gè)特例，是相對(duì)于 某些已知點(diǎn)（通常是程序的開始處）的存儲(chǔ)單元。物理地址或絕對(duì)地址是數(shù)據(jù)在主存 中的實(shí)際位置。78頁和幀之間有什么區(qū)別？答：在分頁系統(tǒng)中，進(jìn)程和磁盤上存儲(chǔ)的數(shù)據(jù)被分成大小固定相等的小塊，叫做頁。而主存被分成了同樣大小的小塊，叫做幀。一頁恰好可以被裝入一幀中。79頁和段之間有什么區(qū)別？答

4、：分段是細(xì)分用戶程序的另一種可選方案。采用分段技術(shù)，程序和相關(guān)的數(shù)據(jù)被劃 分成一組段。盡管有一個(gè)最大段長(zhǎng)度，但并不需要所有的程序的所有段的長(zhǎng)度都相等。習(xí)題：2.3節(jié)中列出了內(nèi)存管理的5個(gè)目標(biāo)，7.1節(jié)中列出了 5中需求。請(qǐng)說明它們是一致 的。答：重定位e支持模塊化程序設(shè)計(jì)；保護(hù)e保護(hù)和訪問控制以及進(jìn)程隔離；共享e保護(hù)和訪問控制；邏輯組織e支持模塊化程序設(shè)計(jì)；物理組織e長(zhǎng)期存儲(chǔ)及自動(dòng)分配和管理.考慮使用大小相等分區(qū)的固定分區(qū)方案。分區(qū)大小為2e16字節(jié)，貯存的大小為2e24 字節(jié)。使用一個(gè)進(jìn)程表來包含每一個(gè)進(jìn)程對(duì)應(yīng)的分區(qū)。這個(gè)指針需要多少位？答:分區(qū)的數(shù)量等于主存的字節(jié)數(shù)除以每個(gè)分區(qū)的字節(jié)數(shù)：2

5、2416= 28.需要8個(gè)比 特來確定一個(gè)分區(qū)大小為28中的某一個(gè)位置。考慮動(dòng)態(tài)分區(qū)方案，說明平均內(nèi)存中空洞的數(shù)量是段數(shù)量的一半。答：設(shè)n和h為斷數(shù)量和空洞數(shù)量的個(gè)數(shù).在主存中，每劃分一個(gè)斷產(chǎn)生一個(gè)空洞的概 率是0.5,因?yàn)閯h除一個(gè)斷和添加一個(gè)斷的概率是一樣的.假設(shè)s是內(nèi)存中斷的個(gè)數(shù)那 么空洞的平均個(gè)數(shù)一定等于s/2.而導(dǎo)致空洞的個(gè)數(shù)一定小余斷的數(shù)量的直接原因是 相鄰的兩個(gè)斷在刪除是一定會(huì)產(chǎn)生一個(gè)空洞.在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)中的各種放置算法（見7.2節(jié)），內(nèi)存中必須保留一個(gè)空閑塊列表。 分別討論最佳適配、首次適配、臨近適配三種方法的平均查找長(zhǎng)度。答:通過上題我們知道，假設(shè)s是駐留段的個(gè)數(shù)，那么空洞的平

6、均個(gè)數(shù)是s/2。從平均 意義上講，平均查找長(zhǎng)度是s/4。動(dòng)態(tài)分區(qū)的另一種放置算法是最壞適配，在這種情況下，當(dāng)調(diào)入一個(gè)進(jìn)程時(shí)，使用最 大的空閑存儲(chǔ)塊。該方法與最佳適配、首次適配、鄰近適配相比，優(yōu)點(diǎn)和缺點(diǎn)各是什 么？它的平均查找長(zhǎng)度是多少？答：一種對(duì)最佳適配算法的評(píng)價(jià)即是為固定分配一個(gè)組塊后和剩余空間是如此小以至 于實(shí)際上已經(jīng)沒有什么用處。最壞適配算法最大化了在一次分配之后，剩余空間的大 小仍足夠滿足另一需求的機(jī)率，同時(shí)最小化了壓縮的概率。這種方法的缺點(diǎn)是最大存 儲(chǔ)塊最早被分配，因此大空間的要求可能無法滿足。如果使用動(dòng)態(tài)分區(qū)方案，下圖所示為在某個(gè)給定的時(shí)間點(diǎn)的內(nèi)存配置：陰影部分為已經(jīng)被分配的塊;空

7、白部分為空閑塊。接下來的三個(gè)內(nèi)存需求分別為40MB， 20MB和10MB。分別使用如下幾種放置算法，指出給這三個(gè)需求分配的塊的起始地址。首次適配最佳適配臨近適配（假設(shè)最近添加的塊位于內(nèi)存的開始）最壞適配答：40M的塊放入第2個(gè)洞中，起始地址是80M. 20M的塊放入第一個(gè)洞中.起始地址是 20M. 10M的塊的起始地址是120M。40M,20N,10M的起始地址分別為230M,20M和160M.40M,20M,10M的起始地址是80虬120160M.d. 40M,20M,10M,的起始地址是 80M,230M,360M.c.7.7.使用伙伴系統(tǒng)分配一個(gè)1MB的存儲(chǔ)塊。a.利用類似于圖7.6的圖

8、來說明按下列順序請(qǐng)求和返回的結(jié)果：請(qǐng)求70；請(qǐng)求35； 請(qǐng)求80；返回A；請(qǐng)求60；返回B；返回D；返回C。給出返回B之后的二叉樹表示。答：考慮一個(gè)伙伴系統(tǒng)，在當(dāng)前分配下的一個(gè)特定塊地址為011011110000.如果塊大小為4,它的伙伴的二進(jìn)制地址為多少？如果塊大小為16,它的伙伴的二進(jìn)制地址為多少？答：011011110100011011100000令buddyk (x)為大小為2k、地址為x的塊的伙伴的地址，寫出buddyk (x)的通用表達(dá)式。答:1 . +2 il、g；l =R頃皿|.頊i&mod舟=2*Fabonacci序列定義如下：Fo=0,F=1,Fn+2=Fn+i+Fn，nM

9、0這個(gè)序列可以用于建立伙伴系統(tǒng)嗎？該伙伴系統(tǒng)與本章介紹的二叉伙伴系統(tǒng)相比，有什么優(yōu)點(diǎn)？ 答:a.是。字區(qū)大小可以確定Fn = Fn-1 + Fn-2.。b.這種策略能夠比二叉伙伴系統(tǒng)提供更多不同大小的塊，因而具有減少內(nèi)部碎片的可 能性。但由于創(chuàng)建了許多沒用的小塊，會(huì)造成更多的外部碎片。在程序執(zhí)行期間，每次取指令后處理器把指令寄存器的內(nèi)容（程序計(jì)數(shù)器）增加一個(gè) 字，但如果遇到會(huì)導(dǎo)致在程序中其他地址繼續(xù)執(zhí)行的轉(zhuǎn)跳或調(diào)用指令，處理器將修改 這個(gè)寄存器的內(nèi)容?，F(xiàn)在考慮圖7.8。關(guān)于指令地址有兩種選擇：在指令寄存器中保存相對(duì)地址，并把指令寄存器作為輸入進(jìn)行動(dòng)態(tài)地址轉(zhuǎn)換。當(dāng) 遇到一次成功的轉(zhuǎn)跳或調(diào)用時(shí)，由

10、這個(gè)轉(zhuǎn)跳或調(diào)用產(chǎn)生的相對(duì)地址被裝入到指令 寄存器中。在指令寄存器中保存絕對(duì)地址。當(dāng)遇到一次成功的轉(zhuǎn)跳或調(diào)用時(shí)，采用動(dòng)態(tài)地址 轉(zhuǎn)換，其結(jié)果保存到指令寄存器中。哪種方法更好？答：使用絕對(duì)地址可以減少動(dòng)態(tài)地址轉(zhuǎn)換的次數(shù)。但是，我們希望程序能夠被重定位。 因此，在指令寄存器中保存相對(duì)地址似乎就更好一些。也可以選擇在進(jìn)程被換出主存 時(shí)將指令寄存器中的地址轉(zhuǎn)換為相對(duì)地址?？紤]一個(gè)簡(jiǎn)單分頁系統(tǒng)，其物理存儲(chǔ)器大小為232字節(jié)，頁大小為210字節(jié)，邏輯地址 空間為216個(gè)頁。a.邏輯地址空間包含多少位？b. 一個(gè)幀中包含多少字節(jié)？在物理地址中指定幀需要多少位？在頁表中包含多少個(gè)頁表項(xiàng)？在每個(gè)頁表項(xiàng)中包含多少位？

11、（假設(shè)每個(gè)頁表項(xiàng)中包含一個(gè)有效/無效位） 答：a.物理地址空間的比特?cái)?shù)是216*210=226b. 一個(gè)幀包含的字節(jié)跟一個(gè)頁是一樣的,210比特.主存中幀的數(shù)量是232/210=222,所以每個(gè)幀的定位要22個(gè)比特在物理地址空間，每個(gè)頁都有一個(gè)頁表項(xiàng),所以有216項(xiàng)加上有效/無效位，每個(gè)頁表項(xiàng)包含23位。分頁系統(tǒng)中的虛地址a相當(dāng)于一對(duì)（p，w），其中p是頁號(hào)，w是頁中的字節(jié)號(hào)。令z 是一頁中的字節(jié)總數(shù)，請(qǐng)給出p和w關(guān)于z和a的函數(shù)。答：關(guān)系是：a = pz + w，其中p = La/z , a/z的整數(shù)部分。w = Rz（a） , a除以z 的余數(shù)在一個(gè)簡(jiǎn)單分段系統(tǒng)中，包含如下段表：起始地址長(zhǎng)

12、度（字節(jié)）6602481752442222198996604對(duì)如下的每一個(gè)邏輯地址，確定其對(duì)應(yīng)的物理地址或者說明段錯(cuò)誤是否會(huì)發(fā)生: TOC o 1-5 h z 0，1982， 256 HYPERLINK l bookmark36 o Current Document 1，5303，4440，222答：段0定位在660,所以我們有物理地址660+190=858.222+156=378段1長(zhǎng)度為422,所以會(huì)發(fā)生錯(cuò)誤996+444=1440660+222=882.在內(nèi)存中，存在連續(xù)的段SpS2,，Sn按其創(chuàng)建順序一次從一端放置到另一端，如下 圖所示：當(dāng)段Sn+1被創(chuàng)建時(shí)，盡管S,s2,，Sn中的某些段可能已經(jīng)被刪除，段Sn+1仍被立即放 置在段、之后。當(dāng)段(正在使用或已被刪除)和洞之間的邊界到達(dá)內(nèi)存的另一端時(shí)，n壓縮正在使用的段。說明花費(fèi)在壓縮上的時(shí)間F遵循以下的不等式：FM(1-f)/1+kf), k=t/2s-1其中，s表示段的平均長(zhǎng)度(以字為單位)；l標(biāo)識(shí)段的平均生命周期，按存儲(chǔ)器 訪問；？表示在平衡條件下，未使用的內(nèi)存部分。提示：計(jì)算邊界在內(nèi)存中移動(dòng)的 平均速度，并假設(shè)復(fù)制一個(gè)字至少需要兩次存儲(chǔ)器訪問。當(dāng) f=0.2，t=1000，s=50 時(shí)，計(jì)算 F。答：