存儲管理習題例11.某系統采用動態分區管理技術。某時刻在內存有三個空閑區，它們的首地址和大小分別是：空閑區1（100KB，10KB），空閑2（200KB，30KB），空閑區3（300KB，15KB），現有如下作業序列：作業1需要15KB，作業2需求16KB，作業3需求10KB。要求：（1）畫出該時刻內存分配圖。（2）用首次適應算法和最佳適應算法畫出此時的自由主存隊列結構。（1）將作業序列裝入主存之前，內存的分配圖如下所示：10KB30KB15KB100KB110KB-1200KB230KB-1300KB315KB-1（2）首次適應算法的自由主存隊列結構為：10KB30KB15KB鏈首指針100KB200KB300KB（2）最佳適應算法的自由主存隊列結構為：10KB15KB30KB鏈首指針100KB300KB200KB例22.在分頁系統中地址結構長度為16位,頁面大小為2K,作業地址空間為6K,該作業的各頁依次存放在2、3、6號物理塊中，相對地址2500處有一條指令store1,4500，請給出該作業的頁表和該指令的物理單元以及數據存放的物理單元。答案頁面大小為2K，即2048字節；作業地址空間6K，則占用頁數為3，編號為0、1、2，依次存放在2、3、6號物理塊中，作業頁表如下：相對地址為2500字節，應在第2500/2048=1號頁面，余數452即為頁內位移，所以對應的物理塊號為3，得到物理地址為2048*3+452=6596；相對地址4500/2048=2號頁面，頁內位移為404，對應的物理塊號為6，得到物理地址為2048*6+404=12692。021326例33.某操作系統的存儲管理采用頁式管理系統，系統的物理地址空間大小為32K，頁的大小是4K。假定某進程的大小為32頁，請回答如下問題：（1）寫出邏輯地址的格式。（2）如果不考慮權限位，該進程的頁表有多少項？每項至少多少位？答案頁面大小是4K，即212，進程大小是32頁，即25。（1）邏輯地址應有17位，其中0~11位是頁內位移，12~16位是頁號。（2）該進程頁表有32項，每項5位。例44.對一個將頁表放在內存中的分頁系統：（1）如果訪問內存需要（2）如果增加一個快表，且假定在快表中找到頁表項的概率高達90%，則有效訪問時間表又是多少（假定查找快表需花的時間為0）？答案每次訪問數據時，若不使用快表，則需要兩次訪問內存，即先從內存的頁表中讀出頁對應的塊號，然后再根據形成的物理地址去存取數據；使用快表時，若能從快表中直接找到對應的頁表項，則可立即形成物理地址去訪問相應的數據，否則，仍需兩次訪問內存。（1）有效訪問時間為：（2）有效訪問時間為：例55.在分頁存儲管理系統中，邏輯地址的長度為16位，頁面大小為4096字節，現有一邏輯地址為2F6AH，且0、1、2頁依次存放在物理塊5、10、11中，問相應的物理地址是多少？答案分析：在分頁存儲管理系統中進行地址轉換時，地址變換機構將自動把邏輯地址轉化為頁號和頁內地址，如果頁號不小于頁表長度，則產生越界中斷；否則便以頁號為索引去檢索頁表，從中得到對應的塊號，并把塊號和頁內位移分別送入物理地址寄存器的塊號和塊內位移字段中，形成物理地址。答案：由分析所給條件可知，分頁存儲管理系統的邏輯地址結構如下圖：邏輯地址2F6AH的二進制表示如下：0010111101101010頁號頁內位移由此可知邏輯地址2F6AH的頁號為2，小于頁表長度3，沒有越界，該頁存放在第11個物理塊中，用十六進制表示塊號為B，所以物理地址為BF6AH。頁號頁內位移0111215例66.現有一分頁虛擬存取管理系統，其頁表保存在寄存器中。若有一個可用的空頁或被替換的頁未被修改，則它處理一個缺頁中斷需要8ms。如果被替換的頁已被修改，則處理一個缺頁中斷需要20ms。內存存取時間為。假定70%被替換的頁被修改過，為保證有效存取時間不超過，可接受的最大缺頁率是多少？分析及答案分析：因為頁表放在寄存器中，所以訪問頁表的時間可以忽略不計。則存取時間就包括內存存取時間和處理缺頁中斷的時間。答案：如果P表示缺頁率，則有效訪問時間不超過2可表示為：因此可以計算出：例77.某虛擬存儲器的用戶空間共有32個頁面，每頁1KB，主存16KB。假定某時刻系統為用戶的第0、1、2、3頁分別分配的物理塊號為5、10、4、7，試將虛擬地址0A5C和093C變換為物理地址。答案虛擬地址為0A5C，對應的二進制數為：0000

1010

01011100。其中，頁內偏移量占10位地址碼，為25C。因第２頁存儲在４號塊中，其基地址為：0001000000000000,這樣，虛擬地址為十六進制的125C。虛擬地址為093C，對應的二進制數為：00001001

00111100。其中，頁內偏移量占10位地址碼，為13C。因第2號頁存儲在4號塊中，其基地址為：0001000000000000，010001

00111100。這樣，虛擬地址為十六進制的113C。例88.在采用頁式存儲管理的系統中，某作業J的邏輯地址空間為4頁（每頁2048字節），且已知該作業的頁面映像表（即頁表）如下：試借助地址變換（要求畫出地址變換圖）求出有效邏輯地址4865所對應的物理地址。頁號塊號02142638分析與解答邏輯地址4865指的是2號頁中偏移地址為769的存儲單元（4865-4096=769）。而內存6號塊的起始地址是12288（2048*6），因此對應的物理地址為13057（12288+769）。地址變換圖如下：頁表始址頁表長度頁號偏移地址02142638++頁表寄存器邏輯地址頁表物理地址13057122882769例99.設一段表如圖所示那么，邏輯地址（2，88）對應的物理地址是多少？邏輯地址（4，100）所對應的物理地址是多少？段號基地址段長02196001230014290100313275804195296分析與解答(1)2號段所占的內存空間基地址是90，段內地址是88，因此訪存的物理地址應當是二者相加：90+88=178。(2)在分段存儲管理系統中，段的長度是不固定的。因此段表內需要登記各段的實際長度，用以檢查CPU產生的訪存地址是否超界。題中第2部分給出的段內地址是100，而段的長度是96，因此將產生越界中斷，無任何物理地址產生。段號基地址段長02196001230014290100313275804195296段表始址段表長度段號段內地址++>段表寄存器越界中斷邏輯地址9017888例1010.某頁式存儲管理系統中，地址寄存器長度為24位，其中頁號占14位，則主存的分塊大小應該是多少字節？程序最多占有多少頁？分析與解答主存的分塊大小占10位，應為1K個字節，即210。程序最多可以占有16K個頁，即214。頁號位移量091023邏輯地址在分頁機制中，需要將用戶的線性地址空間劃分成二維地址空間。讓地址的高位部分作為頁號，低位部分作為分塊的大小，也稱位移量。例1111.某虛擬存儲器的用戶空間共有32個頁面，每頁1K，主存16K。假定某時刻系統為用戶的第0、1、2、3頁分配的物理塊號為5、10、4、7，而該用戶作業的長度為6頁，試將十六進制的虛擬地址0A5C轉換成物理地址。分析與解題邏輯地址有15位，其中高5位為頁號，低10位為頁內地址；物理地址有14位，其中高4位為塊號，低10位為塊內地址。邏輯地址(0A5C)16的頁號為(00010)2，即2，故頁號合法。從頁表中找到對應的內存塊號為4，即(0100)2;與頁內地址(1001011100)2拼接形成物理地址(01001001011100)2,即(125C)16。00010100101110001001001011100邏輯地址05A1CC52物理地址125C頁號2塊號4頁內地址25C塊內地址25C例12在一個使用交換技術(Swapping)的系統中,按地址從低到高排列的內存空間長度是:10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。對于下列順序段的請求：（1）12KB（2）10KB（3）15KB（4）18KB（5）12KB分別使用首次適配、最佳適配、最差適配和下次適配算法說明空間的使用情況，并說明對暫時不能分配情況的處理方法。分析與解題首次適配：（1）12KB：2#區（2）10KB：0#區（3）15KB：3#區（4）18KB：失敗（5）12KB：6#區最佳適配：1）12KB：6#區（2）10KB：0#區（3）15KB：7#區（4）18KB：3#區（5）12KB：2#區最差適配：1）12KB：2#區（2）10KB：3#區（3）15KB：7#區（4）18KB：失敗（5）12KB：6#區下次適配：1）12KB：2#區（2）10KB：3#區（3）15KB：7#區（4）18KB：失敗（5）12KB：6#區上述算法中，只有最佳適配算法是分配成功的，其他3種算法都在第4段請求（18KB）出現時分配失敗。當出現暫時不能分配的情況時，系統可以采用拼接技術，將內存中的進程移動到存儲器的一端，使夾雜于其間的空閑小空間移動到另一端，形成一個較大的可用空間，以滿足用戶的需求。例1313.某頁式存儲管理系統中，地址寄存器長度24位，其中頁號占14位，則主存的分塊大小應該是（）字節，程序最多占有（）頁。A.210B.10C.14D.214E.24F.224分析與解答本題的考核要點是內存分頁管理機制，主要涉及頁面長度的劃分方法。我們知道，在分頁機制中，需要將用戶的線性地址空間劃分成二維地址空間。讓地址的高位部分作為頁號，低位部分作為分塊的大小，也稱位移量，見下圖所示。主存的分塊大小占10位，應為1K個字節，即210。因此，第1個選項是A，程序最多可以占有16K個頁，即214，第2個選項是D。頁號位移量231090…………例1414.假設一個分頁存儲管理系統具有快表，多數活動頁表項都可以存在其中。如果頁表放在內存中，內存訪問時間是1μs,若快表的命中率是85%，則有效存取時間為多少？若快表的命中率為50%，那么有效存取時間為多少？分析與解答本題的考核要點是內存分頁存儲管理中，具有快表機制的訪問過程，涉及的內容有：1）當快表的命中率是85%時，有效存取時間為：0.85×1+(1-0.85)×(1+1)=1.15μm2）當快表的命中率是50%時，有效存取時間為：0.5×1+(1-0.5)×(1+1)=1.5μm例1515.在可變式分區分配方案中，某一作業完成后系統收回其主存空間，并與相鄰空閑區合并，為此需修改空閑區表，造成空閑數減1的情況是（）。A.無上鄰空閑區，也無下鄰空閑區B.有上鄰空閑區，但無下鄰空閑區C.有下鄰空閑區，但無上鄰空閑區D.有上鄰空閑區，也有下鄰空閑區分析與解答本題的考核要點是可變分區管理系統的空閑分區回收問題。當用戶歸還一個空閑分區后，系統在掛入空閑分區鏈表時需要將相鄰空閑分區合并，形成一個大的空閑分區，因此涉及的內容有：1）無上鄰空閑區，也無下鄰空閑區的情況下，系統將回收的空閑分區掛入空閑鏈表，使空閑分區總數增加1。2）有上鄰空閑區，但無下鄰空閑區的情況下，系統將回收的空閑分區并入上鄰分區中，使空閑分區總數