1、存儲(chǔ)管理習(xí)題,例1,1.某系統(tǒng)采用動(dòng)態(tài)分區(qū)管理技術(shù)。某時(shí)刻在內(nèi)存有三個(gè)空閑區(qū)，它們的首地址和大小分別是：空閑區(qū)1（100KB，10KB），空閑2（200KB，30KB），空閑區(qū)3（300KB，15KB），現(xiàn)有如下作業(yè)序列：作業(yè)1需要15KB，作業(yè)2需求16KB，作業(yè)3需求10KB。要求： （1）畫(huà)出該時(shí)刻內(nèi)存分配圖。 （2）用首次適應(yīng)算法和最佳適應(yīng)算法畫(huà)出此時(shí)的自由主存隊(duì)列結(jié)構(gòu)。,（1）將作業(yè)序列裝入主存之前，內(nèi)存的分配圖如下所示：,（2）首次適應(yīng)算法的自由主存隊(duì)列結(jié)構(gòu)為：,（2）最佳適應(yīng)算法的自由主存隊(duì)列結(jié)構(gòu)為：,例2,2.在分頁(yè)系統(tǒng)中地址結(jié)構(gòu)長(zhǎng)度為16位,頁(yè)面大小為2K,作業(yè)地址空間為6K

2、,該作業(yè)的各頁(yè)依次存放在2、3、6號(hào)物理塊中，相對(duì)地址2500處有一條指令store 1,4500，請(qǐng)給出該作業(yè)的頁(yè)表和該指令的物理單元以及數(shù)據(jù)存放的物理單元。,答案,頁(yè)面大小為2K，即2048字節(jié)；作業(yè)地址空間6K，則占用頁(yè)數(shù)為3，編號(hào)為0、1、2，依次存放在2、3、6號(hào)物理塊中，作業(yè)頁(yè)表如下： 相對(duì)地址為2500字節(jié)，應(yīng)在第2500/2048=1號(hào)頁(yè)面，余數(shù)452即為頁(yè)內(nèi)位移，所以對(duì)應(yīng)的物理塊號(hào)為3，得到物理地址為2048*3+452=6596；相對(duì)地址4500/2048=2號(hào)頁(yè)面，頁(yè)內(nèi)位移為404，對(duì)應(yīng)的物理塊號(hào)為6，得到物理地址為2048*6+404=12692。,例3,3.某操作系統(tǒng)

3、的存儲(chǔ)管理采用頁(yè)式管理系統(tǒng)，系統(tǒng)的物理地址空間大小為32K，頁(yè)的大小是4K。假定某進(jìn)程的大小為32頁(yè)，請(qǐng)回答如下問(wèn)題： （1）寫(xiě)出邏輯地址的格式。 （2）如果不考慮權(quán)限位，該進(jìn)程的頁(yè)表有多少項(xiàng)？每項(xiàng)至少多少位？,答案,頁(yè)面大小是4K，即212，進(jìn)程大小是32頁(yè)，即25。 （1）邏輯地址應(yīng)有17位，其中011位是頁(yè)內(nèi)位移，1216位是頁(yè)號(hào)。 （2）該進(jìn)程頁(yè)表有32項(xiàng)，每項(xiàng)5位。,例4,4.對(duì)一個(gè)將頁(yè)表放在內(nèi)存中的分頁(yè)系統(tǒng)： （1）如果訪問(wèn)內(nèi)存需要 （2）如果增加一個(gè)快表，且假定在快表中找到頁(yè)表項(xiàng)的概率高達(dá)90%，則有效訪問(wèn)時(shí)間表又是多少（假定查找快表需花的時(shí)間為0）？,答案,每次訪問(wèn)數(shù)據(jù)時(shí)，若不

4、使用快表，則需要兩次訪問(wèn)內(nèi)存，即先從內(nèi)存的頁(yè)表中讀出頁(yè)對(duì)應(yīng)的塊號(hào)，然后再根據(jù)形成的物理地址去存取數(shù)據(jù)；使用快表時(shí)，若能從快表中直接找到對(duì)應(yīng)的頁(yè)表項(xiàng)，則可立即形成物理地址去訪問(wèn)相應(yīng)的數(shù)據(jù)，否則，仍需兩次訪問(wèn)內(nèi)存。 （1）有效訪問(wèn)時(shí)間為： （2）有效訪問(wèn)時(shí)間為：,例5,5.在分頁(yè)存儲(chǔ)管理系統(tǒng)中，邏輯地址的長(zhǎng)度為16位，頁(yè)面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且0、1、2頁(yè)依次存放在物理塊5、10、11中，問(wèn)相應(yīng)的物理地址是多少？,答案,分析：在分頁(yè)存儲(chǔ)管理系統(tǒng)中進(jìn)行地址轉(zhuǎn)換時(shí)，地址變換機(jī)構(gòu)將自動(dòng)把邏輯地址轉(zhuǎn)化為頁(yè)號(hào)和頁(yè)內(nèi)地址，如果頁(yè)號(hào)不小于頁(yè)表長(zhǎng)度，則產(chǎn)生越界中斷；否則便以頁(yè)號(hào)為索引去

5、檢索頁(yè)表，從中得到對(duì)應(yīng)的塊號(hào)，并把塊號(hào)和頁(yè)內(nèi)位移分別送入物理地址寄存器的塊號(hào)和塊內(nèi)位移字段中，形成物理地址。 答案：由分析所給條件可知，分頁(yè)存儲(chǔ)管理系統(tǒng)的邏輯地址結(jié)構(gòu)如下圖： 邏輯地址2F6AH的二進(jìn)制表示如下： 0010 111101101010 頁(yè)號(hào) 頁(yè)內(nèi)位移 由此可知邏輯地址2F6AH的頁(yè)號(hào)為2，小于頁(yè)表長(zhǎng)度3，沒(méi)有越界，該頁(yè)存放在第11個(gè)物理塊中，用十六進(jìn)制表示塊號(hào)為B，所以物理地址為BF6AH。,例7,7.某虛擬存儲(chǔ)器的用戶(hù)空間共有32個(gè)頁(yè)面，每頁(yè)1KB，主存16KB。假定某時(shí)刻系統(tǒng)為用戶(hù)的第0、1、2、3頁(yè)分別分配的物理塊號(hào)為5、10、4、7，試將虛擬地址0A5C和093C變換為物

6、理地址。,答案,虛擬地址為0A5C，對(duì)應(yīng)的二進(jìn)制數(shù)為：0000 1010 0101 1100。其中，頁(yè)內(nèi)偏移量占10位地址碼，為25C。因第頁(yè)存儲(chǔ)在號(hào)塊中，其基地址為：0001 0000 0000 0000,這樣，虛擬地址為十六進(jìn)制的125C。 虛擬地址為093C，對(duì)應(yīng)的二進(jìn)制數(shù)為：0000 1001 0011 1100。其中，頁(yè)內(nèi)偏移量占10位地址碼，為13C。因第2號(hào)頁(yè)存儲(chǔ)在4號(hào)塊中，其基地址為：0001 0000 0000 0000， 010001 0011 1100。這樣，虛擬地址為十六進(jìn)制的113C。,例8,8.在采用頁(yè)式存儲(chǔ)管理的系統(tǒng)中，某作業(yè)J的邏輯地址空間為4頁(yè)（每頁(yè)2048字

7、節(jié)），且已知該作業(yè)的頁(yè)面映像表（即頁(yè)表）如下： 試借助地址變換（要求畫(huà)出地址變換圖）求出有效邏輯地址4865所對(duì)應(yīng)的物理地址。,分析與解答,邏輯地址4865指的是2號(hào)頁(yè)中偏移地址為769的存儲(chǔ)單元（4865-4096=769）。而內(nèi)存6號(hào)塊的起始地址是12288（2048*6），因此對(duì)應(yīng)的物理地址為13057（12288+769）。地址變換圖如下：,+,例9,9.設(shè)一段表如圖所示 那么，邏輯地址（2，88）對(duì)應(yīng)的物理地址是多少？邏輯地址（4，100）所對(duì)應(yīng)的物理地址是多少？,分析與解答,(1)2號(hào)段所占的內(nèi)存空間基地址是90，段內(nèi)地址是88，因此訪存的物理地址應(yīng)當(dāng)是二者相加：90+88=178

8、。 (2)在分段存儲(chǔ)管理系統(tǒng)中，段的長(zhǎng)度是不固定的。因此段表內(nèi)需要登記各段的實(shí)際長(zhǎng)度，用以檢查CPU產(chǎn)生的訪存地址是否超界。題中第2部分給出的段內(nèi)地址是100，而段的長(zhǎng)度是96，因此將產(chǎn)生越界中斷，無(wú)任何物理地址產(chǎn)生。,例10,10.某頁(yè)式存儲(chǔ)管理系統(tǒng)中，地址寄存器長(zhǎng)度為24位，其中頁(yè)號(hào)占14位，則主存的分塊大小應(yīng)該是多少字節(jié)？程序最多占有多少頁(yè)？,分析與解答,主存的分塊大小占10位，應(yīng)為1K個(gè)字節(jié)，即210。 程序最多可以占有16K個(gè)頁(yè)，即214。,0,9,10,23,邏輯地址,在分頁(yè)機(jī)制中，需要將用戶(hù)的線性地址空間劃分成二維地址空間。讓地址的高位部分作為頁(yè)號(hào)，低位部分作為分塊的大小，也稱(chēng)位

9、移量。,例11,11.某虛擬存儲(chǔ)器的用戶(hù)空間共有32個(gè)頁(yè)面，每頁(yè)1K，主存16K。假定某時(shí)刻系統(tǒng)為用戶(hù)的第0、1、2、3頁(yè)分配的物理塊號(hào)為5、10、4、7，而該用戶(hù)作業(yè)的長(zhǎng)度為6頁(yè)，試將十六進(jìn)制的虛擬地址0A5C轉(zhuǎn)換成物理地址。,分析與解題,邏輯地址有15位，其中高5位為頁(yè)號(hào)，低10位為頁(yè)內(nèi)地址；物理地址有14位，其中高4位為塊號(hào)，低10位為塊內(nèi)地址。 邏輯地址(0A5C)16的頁(yè)號(hào)為(00010)2，即2，故頁(yè)號(hào)合法。從頁(yè)表中找到對(duì)應(yīng)的內(nèi)存塊號(hào)為4，即(0100)2;與頁(yè)內(nèi)地址(10 0101 1100)2拼接形成物理地址(010010 0101 1100)2,即(125C)16。,邏輯地址

10、,0,5,A,1,C,C,5,2,物理地址 125C,頁(yè)號(hào)2,塊號(hào)4,頁(yè)內(nèi)地址 25C,塊內(nèi)地址 25C,例12,在一個(gè)使用交換技術(shù)(Swapping)的系統(tǒng)中,按地址從低到高排列的內(nèi)存空間長(zhǎng)度是:10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。對(duì)于下列順序段的請(qǐng)求： （1）12KB （2）10KB （3）15KB （4）18KB （5）12KB 分別使用首次適配、最佳適配、最差適配和下次適配算法說(shuō)明空間的使用情況，并說(shuō)明對(duì)暫時(shí)不能分配情況的處理方法。,分析與解題,首次適配：（1）12KB：2#區(qū) （2） 10KB：0#區(qū) （3） 15KB：3#區(qū) （4） 18KB：

11、失敗 （5） 12KB：6#區(qū) 最佳適配：1）12KB：6#區(qū) （2） 10KB：0#區(qū) （3） 15KB：7#區(qū) （4） 18KB： 3#區(qū) （5） 12KB：2#區(qū) 最差適配：1）12KB：2#區(qū) （2） 10KB：3#區(qū) （3） 15KB：7#區(qū) （4） 18KB：失敗 （5） 12KB：6#區(qū) 下次適配：1）12KB：2#區(qū) （2） 10KB：3#區(qū) （3） 15KB：7#區(qū) （4） 18KB：失敗 （5） 12KB：6#區(qū) 上述算法中，只有最佳適配算法是分配成功的，其他3種算法都在第4段請(qǐng)求（18KB）出現(xiàn)時(shí)分配失敗。 當(dāng)出現(xiàn)暫時(shí)不能分配的情況時(shí)，系統(tǒng)可以采用拼接技術(shù)，將內(nèi)存中的進(jìn)程

12、移動(dòng)到存儲(chǔ)器的一端，使夾雜于其間的空閑小空間移動(dòng)到另一端，形成一個(gè)較大的可用空間，以滿(mǎn)足用戶(hù)的需求。,例13,13.某頁(yè)式存儲(chǔ)管理系統(tǒng)中，地址寄存器長(zhǎng)度24位，其中頁(yè)號(hào)占14位，則主存的分塊大小應(yīng)該是（ ）字節(jié)，程序最多占有（ ）頁(yè)。 A. 210 B. 10 C.14 D. 214 E. 24 F. 224,分析與解答,本題的考核要點(diǎn)是內(nèi)存分頁(yè)管理機(jī)制，主要涉及頁(yè)面長(zhǎng)度的劃分方法。我們知道，在分頁(yè)機(jī)制中，需要將用戶(hù)的線性地址空間劃分成二維地址空間。讓地址的高位部分作為頁(yè)號(hào)，低位部分作為分塊的大小，也稱(chēng)位移量，見(jiàn)下圖所示。 主存的分塊大小占10位，應(yīng)為1K個(gè)字節(jié)，即210。因此，第1個(gè)選項(xiàng)是A

13、，程序最多可以占有16K個(gè)頁(yè)，即214，第2個(gè)選項(xiàng)是D。,例14,14.假設(shè)一個(gè)分頁(yè)存儲(chǔ)管理系統(tǒng)具有快表，多數(shù)活動(dòng)頁(yè)表項(xiàng)都可以存在其中。如果頁(yè)表放在內(nèi)存中，內(nèi)存訪問(wèn)時(shí)間是1s, 若快表的命中率是85%，則有效存取時(shí)間為多少？若快表的命中率為50%，那么有效存取時(shí)間為多少？,分析與解答,本題的考核要點(diǎn)是內(nèi)存分頁(yè)存儲(chǔ)管理中，具有快表機(jī)制的訪問(wèn)過(guò)程，涉及的內(nèi)容有： 1）當(dāng)快表的命中率是85%時(shí)，有效存取時(shí)間為： 0.851+(1-0.85) (1+1)=1.15m 2）當(dāng)快表的命中率是50%時(shí)，有效存取時(shí)間為： 0.51+(1-0. 5) (1+1)=1. 5m,例15,15.在可變式分區(qū)分配方案中

14、，某 一作業(yè)完成后系統(tǒng)收回其主存空間，并與相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑數(shù)減1的情況是（ ）。 A.無(wú)上鄰空閑區(qū)，也無(wú)下鄰空閑區(qū) B.有上鄰空閑區(qū)，但無(wú)下鄰空閑區(qū) C.有下鄰空閑區(qū)，但無(wú)上鄰空閑區(qū) D.有上鄰空閑區(qū)，也有下鄰空閑區(qū),分析與解答,本題的考核要點(diǎn)是可變分區(qū)管理系統(tǒng)的空閑分區(qū)回收問(wèn)題。當(dāng)用戶(hù)歸還一個(gè)空閑分區(qū)后，系統(tǒng)在掛入空閑分區(qū)鏈表時(shí)需要將相鄰空閑分區(qū)合并，形成一個(gè)大的空閑分區(qū)，因此涉及的內(nèi)容有： 1）無(wú)上鄰空閑區(qū)，也無(wú)下鄰空閑區(qū)的情況下，系統(tǒng)將回收的空閑分區(qū)掛入空閑鏈表，使空閑分區(qū)總數(shù)增加1。 2）有上鄰空閑區(qū)，但無(wú)下鄰空閑區(qū)的情況下，系統(tǒng)將回收的空閑分區(qū)并入上鄰分區(qū)

15、中，使空閑分區(qū)總數(shù)不增不減。 3）有下鄰空閑區(qū)，但無(wú)上鄰空閑區(qū)的情況下，系統(tǒng)將回收的空閑分區(qū)并入下鄰分區(qū)中，使空閑分區(qū)總數(shù)不增不減。 4）有上鄰空閑區(qū)，也有下鄰空閑區(qū)的情況下，系統(tǒng)將回收的空閑分區(qū)與上/下鄰分區(qū)合并為一個(gè)大分區(qū)，使空閑分區(qū)總數(shù)減1。,例16,16.在一個(gè)請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，一個(gè)作業(yè)的頁(yè)面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給該作業(yè)的物理塊數(shù)分別為3、4時(shí)，試計(jì)算采用下述頁(yè)面淘汰算法時(shí)的缺頁(yè)率（假設(shè)開(kāi)始執(zhí)行時(shí)主存中沒(méi)有頁(yè)面），并比較所得結(jié)果。 （1）最佳置換淘汰算法 （2）先進(jìn)先出淘汰算法 （3）最近最久未使用淘汰算法,題解,（1）根據(jù)所給頁(yè)面走向，使

16、用最佳頁(yè)面淘汰算法時(shí)，頁(yè)面置換情況如下所示。,缺頁(yè)率：7/12,（A）,題解,缺頁(yè)率：6/12,（B）,題解,（2）根據(jù)所給頁(yè)面走向，使用先進(jìn)先出頁(yè)面淘汰算法時(shí)，頁(yè)面置換情況如下所示。,缺頁(yè)率：9/12,（A）,題解,缺頁(yè)率：10/12,（B）,由上述結(jié)果可以看出，對(duì)先進(jìn)先出算法而言，增加分配給作業(yè)的內(nèi)存塊數(shù)反而使缺頁(yè)率上升，這種異常現(xiàn)象稱(chēng)為Belady現(xiàn)象。,題解,（3）根據(jù)所給頁(yè)面走向，使用最近最久未使用頁(yè)面淘汰算法時(shí)，頁(yè)面置換情況如下所示。,缺頁(yè)率：10/12,（A）,題解,缺頁(yè)率：8/12,（B）,由上述結(jié)果可以看出，增加分配給作業(yè)的內(nèi)存塊數(shù)可以降低缺頁(yè)率。,例17,17.有一頁(yè)式系統(tǒng)

17、,其頁(yè)表存放在主存中. (1)如果對(duì)主存的一次存取需要1.5m,試問(wèn)實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間是多少? (2)如果系統(tǒng)加有快表,平均命中率為85%,當(dāng)頁(yè)表項(xiàng)在快表中時(shí),其查找時(shí)間忽略為0,試問(wèn)此時(shí)的存取時(shí)間為多少?,解答,若頁(yè)表存入在內(nèi)存中,則要實(shí)現(xiàn)二次頁(yè)面訪問(wèn)需要兩次訪問(wèn)主存,一次是訪問(wèn)頁(yè)表,確定所存取頁(yè)面的物理地址,第二次才根據(jù)該地址存取頁(yè)面數(shù)據(jù). (1)由于頁(yè)表存在主存,因此,CPU必須兩次訪問(wèn)主存才能獲得所需數(shù)據(jù),所以實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間為:1.52=3m. (2)在系統(tǒng)增加了快表后,在快表中找到頁(yè)表項(xiàng)的概率為85%,所以實(shí)現(xiàn)一次頁(yè)面訪問(wèn)的存取時(shí)間為: 0.851.5+(1-0.85) 2 1.5=1.725m,例18,某請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)使用一