1、精選優質文檔-傾情為你奉上第三章 內存管理 習題1.IBM360有一個設計，為了對2KB大小的塊進行加鎖，會對每個塊分配一個4bit的密鑰，這個密鑰存在PSW（程序狀態字）中，每次內存引用時，CPU都會進行密鑰比較。但該設計有諸多缺陷，除了描述中所言，請另外提出至少兩條缺點。A：密鑰只有四位，故內存只能同時容納最多十六個進程；需要用特殊硬件進行比較，同時保證操作迅速。2.在圖3-3中基址和界限寄存器含有相同的值16384，這是巧合，還是它們總是相等？如果這只是巧合，為什么在這個例子里它們是相等的？A：巧合。基地址寄存器的值是進程在內存上加載的地址；界限寄存器指示存儲區的長度。3.交換系統通過緊

2、縮來消除空閑區。假設有很多空閑區和數據段隨機分布，并且讀或寫32位長的字需要10ns的時間，緊縮128MB大概需要多長時間？為了簡單起見，假設空閑區中含有字0，內存中最高地址處含有有效數據。A：32bit=4Byte=>每字節10/4=2.5ns 128MB=128220=227Byte 對每個字節既要讀又要寫，22.5*227=671ms4.在一個交換系統中，按內存地址排列的空閑區大小是10MB，4MB，20MB，18MB，7MB，9MB，12MB，和15MB。對于連續的段請求：(a) 12MB(b) 10MB(c) 9MB使用首次適配算法，將找出哪個空閑區？使用最佳適配、最差適配、下

3、次適配算法呢？A： 首次適配算法：20MB，10MB，18MB； 最佳適配算法：12MB，10MB，9MB； 最差適配算法：20MB；18MB；15MB； 下次適配算法：20MB；18MB；9MB；5.物理地址和虛擬地址有什么區別？A：實際內存使用物理地址。這些是存儲器芯片在總線上反應的數字。虛擬地址是指一個進程的地址空間的邏輯地址。因此，具有32位字的機器可以生成高達4GB的虛擬地址，而不管機器的內存是否多于或少于4GB。6.對下面的每個十進制虛擬地址，分別使用4KB頁面和8KB頁面計算虛擬頁號和偏移量：20000，32768，60000。A：轉換為二進制分別為：00000 虛擬地址應該是1

4、6位 00000 00000 4KB頁面偏移量范圍04027，需要12位來存儲偏移量，剩下4位作為頁號； 同理8KB頁面需要13位來存儲偏移量，剩下3位作為頁號； 所以， 4KB | 8KB 頁號 | 偏移量 | 頁號 | 偏移量 20000 | 0100 0 | 010 00 32768 | 1000 0 | 100 00 60000 | 1110 0 | 111 007. 使用圖3-9的頁表，給出下面每個虛擬地址對應的物理地址：(a) 20(b) 4100(c) 8300A： （a）20+40962=8212 （b）4100=4096+（4100-4096）=4100 （c）8300=64

5、096+（8300-4096*2）=246848. Inlel 8086處理器不支持虛擬內存，然而一些公司曾經設計過包含未作任何改動的8086 CPU的分頁系統。猜想一下，他們是如何做到這一點的。（提示：考慮MMU的邏輯位置。）A：他們制作了MMU，并連接在CPU與地址總線之間，這樣從處理器進入MMU的地址全部被視為虛擬地址，并被轉換為物理地址，然后被送到地址總線，映射到內存中。9.為了讓分頁虛擬內存工作，需要怎樣的硬件支持？A：需要一個MMU能夠將虛擬頁面重新映射到物理頁面。此外，當缺頁中斷時，需要對操作系統設置陷阱，以便可以獲取頁面。10.寫時復制是使用在服務器系統上的好方法，它能否在手機

6、上起作用。A： “寫時復制“技術，也就是只有進程空間的各段的內容要發生變化時，才會將父進程的內容復制一份給子進程。 如果智能手機支持多重編程，iPhone、Android和Windows手機都支持多重編程，那么支持多個進程。如果進程發出fork()系統調用和頁面在父進程和子進程之間共享，則復制對寫是有意義的。智能手機比服務器小，但從邏輯上講，它并沒有什么不同。11.考慮下面的C程序：int XN; int step = M; /M是某個預定義的常量 for (int i = 0; i < N; i += step) Xi = Xi + 1;a)如果這個程序運行在一個頁面大小為4KB且有6

7、4 個TLB 表項的機器上時，M和N取什么值會使得內層循環的每次執行都會引起TLB失效?b)如果循環重復很多遍，結果會和a)的答案相同嗎？請解釋。A: a)M必須至少為1024，以確保對X元素的每一次訪問都有一個TLB缺失。因為N只影響X訪問多少次，N取大于M的任何值都可以。 b)M應該至少是1024，以確保對X元素的每次訪問都遺漏TLB。但是現在N應該大于64K，以便處理TLB，也就是說，X應該超過256KB。12.存儲頁面必須可用的磁盤空間和下列因素有關：最大進程數n，虛擬地址空間的字節數v，RAM的字節數r，給出最壞情況下磁盤空間需求的表達式。這個數量的真實性如何？A：所有進程的整個虛擬

8、地址空間為nv，這就是頁面存儲所需的。不過，可以在RAM中存儲量為r，因此需要的磁盤存儲量僅為nv-r。該量比實際所需的要大得多，因為極少有n個進程實際運行，而且這些進程也極少需要其最大允許的虛擬內存。13.如果一條指令執行1ns，缺頁中斷執行額外的Nns，且每條k指令產生一個缺頁，請給出一個公式，計算有效指令時間。A： (1*(k-1)+(1+N)/k = 1+N/k ns14.一個機器有32位地址空間和8KB頁面，頁表完全用硬件實現，頁表的每一表項為一個32位字。進程啟動時，以每個字100ns的速度將頁表從內存復制到硬件中。如果每個進程運行100ms（包含裝入頁表的時間）用來裝人頁表的CP

9、U時間的比例是多少？A: 32位地址空間構成4GB內存空間，4GB/8KB=512個頁面，頁表項512項，頁表大小512·32=214 bit,復制頁表的時間=214/25*10ns = 5120 ns, 時間比例5120ns/100ms=5120·10(-9) / 100·10(-3) =51.2% 8KB頁面大小，需要13位偏移量，故頁號有19位，頁面有219個，頁表項也是219個，每項32位字。 219·100ns/100ms=52.4288%15.假設一個機器有48位的虛擬地址和32位的物理地址。a)假設頁面大小是4

10、KB，如果只有一級頁表，那么在頁表里有多少頁表項？ 請解釋。b)假設同一系統有32個TLB表項，并且假設一個程序的指令正好能放入一個頁，并且該程序順序地從有數千個頁的數組中讀取長整型元素。在這種情況下TLB的效果如何？A： a）頁面大小4KB，偏移量有12位，則頁號有36位，有236項頁表項； b）TLB訪問的命中率達100%。在指令訪問下一個頁面之前讀取數據的命中率是100%，一個4KB大小的頁面包含1024個長整型數據，每訪問1024個數據就會有一次TLB失效。16.給定一個虛擬內存系統的如下數據：（a）TLB有1024項，可以在1個時鐘周期（1ns）內訪問。（b）頁表項可以在100時鐘周

11、期（100ns）內訪問。（c）平均頁面替換時間是6ms。如果TLB處理的頁面訪問占99%，并且0.01%的頁面訪問會發生缺頁中斷，那么有效地址轉換時間是多少？A： 99%·1ns+1%·99.99%·100ns+1%·0.01%·6ms=7.9899 99%·1ns+0.99%·100ns+0.01%·6ms=601.98ns17. 假設一個機器有38位的虛擬地址和32位的物理地址。a)與一級頁表比較，多級頁表的主要優點是什么？b)若采用二級頁表，頁面大小為16KB，每個頁表項為4字節，應該對第

12、一級頁表域分配多少位,對第二級頁表域分配多少位？請解釋原因A： a）避免把全部頁表一直保存在內存中。 b） ”16KB個頁“估計是指這個二級頁表的大小是16KB，故頁表項有16KB/4B=4K個，二級頁表域需要12位，四字節表項說明頁面大小是12 頁面大小16KB，則偏移量需要14位，每個條目4字節18.在3.3.4節的陳述中，奔騰Pro將多級頁表中的每個頁表項擴展到64位，但仍只能對4GB的內存進行尋址。請解釋頁表項為64位時，為何這個陳述正確。A：雖然頁表項擴展了，但是虛擬內存地址依然只有32位。19.個32位地址的計算機使用兩級頁表。 虛擬地址被分成9位的頂級頁表域、

13、 11位的二級頁表域和一個偏移量，頁面大小是多少？在地址空間中一共有多少個頁面？A： 頁面大小與偏移量位數有關=212Byte=4KB,每個地址對應內存一個字節， 地址空間的頁面數量=220個。20.一個計算機使用32位的虛擬地址，4KB大小的頁面。程序和數據都位于最低的頁面（04095），棧位于最高的頁面。如果使用傳統（一級）分頁，頁表中需要多少個表項？如果使用兩級分頁，每部分有10位，需要多少個頁表項？A：32位地址對應4GB內存，有4GB/4KB=220個頁面,如果使用傳統（一級）分頁：需要220個頁表項；如果使用兩級分頁，頂級頁表有210個頁表項，其中三項指向二級頁表（程序段、數據段、

14、堆棧段），二級頁表每個也有有210個頁表項，總共212個頁表項。21.如下是在頁大小為512字節的計算機上，一個程序片段的執行軌跡。這個程序在1020地址，其棧指針在8192（棧向0生長）。請給出該程序產生的頁面訪問串。每個指令（包括立即常數）占4個字節（1個字）。指令和數據的訪問都要在訪問串中計數。將字6144載入寄存器0寄存器0壓棧調用5120處的程序，將返回地址壓棧棧指針減去立即數16比較實參和立即數4如果相等，跳轉到5152處A：程序地址范圍10201532。 頁面訪問串：6144-81915120819081845152. A：每個頁面512B，1020地址屬于5

15、121023，即頁面1；棧指針8192屬于81928704，即頁面16，但是棧向0生長，故寄存器壓棧到81918188，屬于頁面15；5152地址屬于51205631，即頁面10. 每條指令4個字節，故第一條指令在地址范圍10201023，屬于頁面1；第二條指令在地址范圍10241027，屬于頁面2；第三條指令地址也在頁面2，但是將數據壓棧到頁面15了。 LOAD 6144,R0 1(I), 12(D) PUSH R0 2(I), 15(D) CALL 5120 2(I), 15(D) JEQ 5152 10(I) 代碼（I）指示指令引用，而（D）指示數據引用。22.一臺計算機的進程在其地址空

16、間有1024個頁面，頁表保存在內存中。從頁表中讀取一個字的開銷是5n。為了減小這一開銷，該計算機使用了TLB，它有32個（虛擬頁面，物理頁框）對，能在1ns內完成查找。請問把平均開銷降到2ns需要的命中率是多少？A：p·1+(5+1)·（1-p）< 2 =>p>0.823.TLB需要的相聯存儲設備如何用硬件實現，這種設計對擴展性意味著什么？A:相聯存儲器本質上將key與多個寄存器的內容同時進行比較。對于每個寄存器，必須有一組比較器，將寄存器內容中的每個位與正在搜索的鍵進行比較。實現這種設備所需的門（或晶體管）的數量是寄存器數量的線性函數，因此這種設計對擴展

17、性意味著成本變得昂貴。24.一臺機器有48位虛擬地址和32位物理地址，頁面大小是8KB，試問頁表中需要多少個表項？A: 物理內存是4GB，頁面數量是4GB/8KB=219項， 頁面偏移量需要213位，頁表域總共35位。25.一個計算機的頁面大小為8KB，內存大小為256KB，虛擬地址空間為64GB，使用倒排頁表實現虛擬內存。為了保證平均散列鏈的長度小于1，散列表應該多大？假設散列表的大小為2的冪。A：（原答案）內存有228(256KB) / 213(8KB) =(215)32768頁。32K的哈希表的平均鏈長為1。為了使之小于1，必須使用下一個尺寸(216)65536項。將

18、32768項放入65536格中使其平均鏈長為0.5，以保證快速的查詢。 （這個題目有錯吧？內存應該是256MB才對） 物理頁面數=256MB/8KB=215，若散列表為215，則平均散列長度為1，為保證平均散列鏈長度小于1，散列表至少為216.26.一個學生在編譯器設計課程中向教授提議了一個項目：編寫一個編譯器，用來產生頁面訪問列表，該列表可以用于實現最優頁面置換算法。試問這是否可能？為什么？有什么方法可以改進運行時的分頁效率？A：這是不可能的，除了程序的執行過程在編譯時是完全可預測的少數情況。如果編譯器收集程序有關調用代碼中的位置信息，則可以在鏈接時使用此信息來重新排列目標代碼，以便程序位于

19、它們調用的代碼附近。這將使得進程更可能與所調用的代碼在同一個頁面上。當然這從許多地方進行調用的程序來說是無效的。27.假設虛擬頁碼索引流中有一些長的頁碼索引序列的重復，序列之后有時會是一個隨機的頁碼索引。例如，序列0，1，511，431，0，1，511，332， 0，1，中就包含了0，1，511的重復，以及跟隨在它們之后的隨機頁碼索引431和332。a)在工作負載比該序列短的情況下，標準的頁面置換算法（LRU，FIFO，Clock) 在處理換頁時為什么效果不好？ b)如果一個程序分配了500個頁框，請描述一個效果優于LRU、FIFO或Clock算法的頁面置換方法。A： a)標準的頁面置換算法是

20、針對已經在內存中的頁面研究的。當工作負載比序列短時，會出現內存容量不夠而長生顛簸，這種情況下LRU、Clock、FIFO算法達不到預期的效果，任何訪問都會引起缺頁除非內存的頁框數量大于512。 b)如果分配了500個頁框，那么0498號頁框是固定的，只有一個頁框進行頁面置換。28.如果將FIFO頁面罝換算法用到4個頁框和8個頁面上，若初始時頁框為空，訪問字符串為，請問會發生多少次缺頁中斷？如果使用LRU算法呢？A： FIFO 6 LRU 729.考慮圖3- 15b中的頁面序列。假設從頁面B到頁面A的R位分別是。 使用第二次機會算法，被移走的是哪個頁面？A：D。30. 一臺小計算機有4個頁框。在

21、第一個時鐘滴答時R位是0111（頁面0是0，其他頁面是1），在隨后的時鐘滴答中這個值是1011、1010、1101、0010、1010、 1100、0001。如果使用帶有8位計數器的老化算法，給出最后一個滴答后4個計數器的值。A： 0號頁框：； 1號頁框：； 2號頁框：； 3號頁框：。31.請給出一個頁面訪問序列，使得對于這個訪問序列，使用Clock和LRU 算法得到的第一個被選擇置換的頁面不同。假設一個進程分配了3個頁框，訪問串中的頁號屬于集合0，1，2，3。A：。 LRU將第3頁替換為第2頁。 Clock將第0頁替換為第2頁。32.在圖3-21c的工作集時鐘算法中，表針指向那個R = 0的

22、頁面。如果=400，這個頁面將被移出嗎？如果= 1000呢？（當前時間2204）A：該頁面的生存時間是2204 - 1213 = 991。如果= 400，它就不在工作集中，最近沒有被引用，所以它將被移出。= 1000的情況不同，此時頁面在工作集中，所以它不會被刪除。34.一個學生聲稱：“抽象來看，除了選取替代頁面使用的屬性不同外，基本頁面置換算法（FIFO，LRU，最優算法）都相同。”（a）FIFO、LRU、最優算法使用的屬性是什么？（b）請給出這些頁面置換算法的通用算法。A： a）FIFO：加載時間；LRU：最近訪問時間；OPT：在未來的最近訪問時間 b）有標簽算法和替換算法。標記算法用部分

23、a給出的屬性從大到小標記每個頁面。替換算法刪除標簽最小的頁面。35.從平均尋道時間10ms、旋轉延遲時間10ms、 每磁道32KB的磁盤上載入一個64KB的程序，對于下列頁面大小分別需要多少時間？    a)頁面大小為2KB；    b)頁面大小為4KB。    假設頁面隨機地分布在磁盤上，柱面的數目非常大以至于兩個頁面在同一個柱面的機會可以忽略不計。A：      a）頁面有64KB/2KB=32個，32·（10+10）=640msb）頁面16個，16·

24、20=320ms原答案：（很迷啊，怎么算的傳輸時間啊？）：搜索加旋轉等待時間為10毫秒。對于2-KB頁面，傳輸時間約為0.毫秒，總共約10.毫秒。加載這些頁面的32將花費大約320.21毫秒。對于4-KB頁面，傳輸時間加倍到大約0.01953毫秒，因此每頁的總時間是10.01953毫秒。加載這些頁面的16需要大約160.3125毫秒。使用這樣快的磁盤，所有重要的是減少傳輸的數量（或者連續地將頁面放在磁盤上）。  現在我知道是如何計算的了，參考現代操作系統中文第四版 第4章文件系統4.4.1的例子：假設磁盤每道有1MB，其旋轉時間是8.33ms，平均尋道時間為5ms。以毫秒為

25、單位，讀取一個k字節的塊所需要的時間是尋道時間、旋轉延遲和傳送時間之和：                    5 + 4.165 + (k/) x 8.33從中可以得知單位容量傳送時間 = 旋轉時間/每道容量故本題中單位容量傳送時間 = 23/215 x 10 = 0.00244 ms/KB42.人們已經觀察到在兩次缺頁中斷之間執行的指令數與分配給程序的頁框數直接成比例。如果可用內存加倍，缺頁中斷間的平均間隔也加倍。假設一條普通指令需要1m，但是如果發生了缺頁中斷，就需要2001s （即2ms

26、處理缺頁中斷），如果一個程序運行了60s，期間發生了15000次缺頁中斷，如果可用內存是原來的兩倍，那么這個程序運行需要多少時間？A：該程序發生了15000次缺頁中斷，每個缺頁中斷都需要2ms的額外處理時間。處理缺頁中斷的總開銷為30s。這意味著在程序運行的60s內，一半用于缺頁中斷開銷，一半用于運行程序。如果我們運行程序的內存是內存的兩倍，我們會得到一半的內存頁錯誤，只有15秒的頁面錯誤開銷，所以總的運行時間將是45秒。43.Frugal計算機公司的一組操作系統設計人員正在考慮在他們的新操作系統中減少對后備存儲數量的需求。老板建議根本不要把程序正文保存在交換區中，而是在需要的時候直接從二進制文件中調頁進來。在什么條件下（如果有這樣的條件話）這種想法適用于程序文本？在什么條件下（如果有這樣的條