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

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

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

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

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

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

7、白部分為空閑塊。接下來的三個內(nèi)存需求分別為40MB， 20MB和10MB。分別使用如下幾種放置算法，指出給這三個需求分配的塊的起始地址。首次適配最佳適配臨近適配（假設最近添加的塊位于內(nèi)存的開始）最壞適配答：40M的塊放入第2個洞中，起始地址是80M. 20M的塊放入第一個洞中.起始地址是 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)分配一個1MB的存儲塊。a.利用類似于圖7.6的圖

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

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

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

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

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