第4章_存儲(chǔ)管理

1、11第第 四四 章章諶諶 衛(wèi)衛(wèi) 軍軍清華大學(xué)清華大學(xué)操作系統(tǒng)操作系統(tǒng)22第四章第四章 存儲(chǔ)管理存儲(chǔ)管理1. 單道程序存儲(chǔ)管理單道程序存儲(chǔ)管理2. 分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理3. 頁式和段式存儲(chǔ)管頁式和段式存儲(chǔ)管理理4. 覆蓋技術(shù)與交換技覆蓋技術(shù)與交換技術(shù)術(shù)5. 虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù)33即使是簡單的、老的存儲(chǔ)管理方案仍然即使是簡單的、老的存儲(chǔ)管理方案仍然有必要掌握。有必要掌握。 有些老的概念仍然有用有些老的概念仍然有用使用何種存儲(chǔ)管理方案取決于硬件平臺(tái)使用何種存儲(chǔ)管理方案取決于硬件平臺(tái) 有些方案需要有些方案需要硬件支持硬件支持； 手持設(shè)備和嵌入式系統(tǒng)等新的硬件平臺(tái)可手持設(shè)備和嵌入式系統(tǒng)等新的硬

2、件平臺(tái)可能只有基本的硬件支持。能只有基本的硬件支持。44理想中的存儲(chǔ)器：理想中的存儲(chǔ)器：更大、更快、更便宜的更大、更快、更便宜的非易失性非易失性存儲(chǔ)器存儲(chǔ)器。實(shí)際中的存儲(chǔ)器實(shí)際中的存儲(chǔ)器：存儲(chǔ)器層次結(jié)構(gòu)存儲(chǔ)器層次結(jié)構(gòu)（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）實(shí)際中的存儲(chǔ)器實(shí)際中的存儲(chǔ)器：存儲(chǔ)管理？存儲(chǔ)管理？55我們主要考察我們主要考察內(nèi)存內(nèi)存（Main Memory）的）的管理。管理。664.1 單道程序存儲(chǔ)管理單道程序存儲(chǔ)管理內(nèi)存分為兩個(gè)區(qū)域：內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)系統(tǒng)區(qū)，用戶區(qū)用戶區(qū)。每次把一個(gè)應(yīng)用程序裝入到用戶

3、區(qū)運(yùn)行，每次把一個(gè)應(yīng)用程序裝入到用戶區(qū)運(yùn)行，由它和操作系統(tǒng)來共享內(nèi)存。當(dāng)它運(yùn)行由它和操作系統(tǒng)來共享內(nèi)存。當(dāng)它運(yùn)行結(jié)束后，操作系統(tǒng)再裝入一個(gè)新的程序結(jié)束后，操作系統(tǒng)再裝入一個(gè)新的程序把它覆蓋；把它覆蓋；優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡單簡單、開銷小，易于管理；、開銷小，易于管理；適合于單用戶、單任務(wù)的適合于單用戶、單任務(wù)的OS。77BIOS（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）三種實(shí)現(xiàn)方式三種實(shí)現(xiàn)方式單道程序存儲(chǔ)管理的缺點(diǎn)？單道程序存儲(chǔ)管理的缺點(diǎn)？88n每次只能運(yùn)行一個(gè)程序每次只能運(yùn)行一個(gè)程序n內(nèi)存資源的使用效率不高內(nèi)存資源的使用效率

4、不高程序程序較小較小時(shí)，會(huì)浪費(fèi)大量的內(nèi)存空間時(shí)，會(huì)浪費(fèi)大量的內(nèi)存空間nOS的保護(hù)的保護(hù)應(yīng)用程序的應(yīng)用程序的bug會(huì)破壞會(huì)破壞OSn地址空間有限地址空間有限即為物理內(nèi)存的大小即為物理內(nèi)存的大小99如何實(shí)現(xiàn)多道存儲(chǔ)管理，即在內(nèi)如何實(shí)現(xiàn)多道存儲(chǔ)管理，即在內(nèi)存中同時(shí)有多個(gè)進(jìn)程運(yùn)行，有哪存中同時(shí)有多個(gè)進(jìn)程運(yùn)行，有哪些問題需要考慮？些問題需要考慮？1010 內(nèi)存空間的管理內(nèi)存空間的管理 整個(gè)內(nèi)存區(qū)域如何劃分？整個(gè)內(nèi)存區(qū)域如何劃分？ 用什么數(shù)據(jù)結(jié)構(gòu)來管理內(nèi)存？用什么數(shù)據(jù)結(jié)構(gòu)來管理內(nèi)存？ 如何在有限的內(nèi)存空間中容納盡可能多如何在有限的內(nèi)存空間中容納盡可能多的進(jìn)程？的進(jìn)程？ 內(nèi)存的分配內(nèi)存的分配 新進(jìn)程到達(dá)時(shí)，

5、如何給它分配內(nèi)存？新進(jìn)程到達(dá)時(shí)，如何給它分配內(nèi)存？ 內(nèi)存的回收內(nèi)存的回收 進(jìn)程運(yùn)行結(jié)束時(shí)，如何回收其內(nèi)存？進(jìn)程運(yùn)行結(jié)束時(shí)，如何回收其內(nèi)存？1111 地址重定位地址重定位 程序員不知道當(dāng)他的程序被執(zhí)行時(shí)，將程序員不知道當(dāng)他的程序被執(zhí)行時(shí)，將會(huì)被放在內(nèi)存的什么位置；會(huì)被放在內(nèi)存的什么位置； 當(dāng)一個(gè)程序正在執(zhí)行時(shí)，可能被交換到當(dāng)一個(gè)程序正在執(zhí)行時(shí)，可能被交換到磁盤上，后來再返回內(nèi)存時(shí)，可能存放磁盤上，后來再返回內(nèi)存時(shí)，可能存放在不同的位置；在不同的位置； 對(duì)內(nèi)存的訪問必須轉(zhuǎn)換為實(shí)際的物理內(nèi)對(duì)內(nèi)存的訪問必須轉(zhuǎn)換為實(shí)際的物理內(nèi)存地址。存地址。1212 內(nèi)存保護(hù)內(nèi)存保護(hù) 一個(gè)進(jìn)程不能未經(jīng)許可去訪問其他進(jìn)程

6、一個(gè)進(jìn)程不能未經(jīng)許可去訪問其他進(jìn)程或或OS的內(nèi)存地址；的內(nèi)存地址； 內(nèi)存共享內(nèi)存共享 允許多個(gè)進(jìn)程訪問相同的一段內(nèi)存空間；允許多個(gè)進(jìn)程訪問相同的一段內(nèi)存空間； 最好允許每個(gè)進(jìn)程訪問一個(gè)程序的同一最好允許每個(gè)進(jìn)程訪問一個(gè)程序的同一份拷貝，而不是每個(gè)進(jìn)程都有自己獨(dú)立份拷貝，而不是每個(gè)進(jìn)程都有自己獨(dú)立的一份拷貝。的一份拷貝。1313 邏輯組織邏輯組織 程序的編寫是以模塊為單位；程序的編寫是以模塊為單位； 每個(gè)模塊的保護(hù)級(jí)別可能是不同的（只每個(gè)模塊的保護(hù)級(jí)別可能是不同的（只讀、只可執(zhí)行、可讀寫等）；讀、只可執(zhí)行、可讀寫等）； 模塊的共享。模塊的共享。 物理組織物理組織 分配給一個(gè)程序（包括其數(shù)據(jù)）的內(nèi)

7、存分配給一個(gè)程序（包括其數(shù)據(jù)）的內(nèi)存空間可能不夠用；空間可能不夠用； 磁盤存儲(chǔ)器更便宜、容量更大、且永久磁盤存儲(chǔ)器更便宜、容量更大、且永久保存。保存。1414Now，如何實(shí)現(xiàn)多道存儲(chǔ)管理？，如何實(shí)現(xiàn)多道存儲(chǔ)管理？n內(nèi)存的分配；內(nèi)存的分配；n內(nèi)存的回收；內(nèi)存的回收；n內(nèi)存的管理（數(shù)據(jù)結(jié)構(gòu)）。內(nèi)存的管理（數(shù)據(jù)結(jié)構(gòu)）。15154.2 分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理內(nèi)存分為兩大區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。內(nèi)存分為兩大區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。又把用戶區(qū)劃分為若干分區(qū)又把用戶區(qū)劃分為若干分區(qū)(partition)，分區(qū)大小可以相等，也可以不等。一個(gè)分區(qū)大小可以相等，也可以不等。一個(gè)進(jìn)程占用一個(gè)分區(qū)。進(jìn)程占用一個(gè)分區(qū)。特

8、點(diǎn)：適合于多道程序系統(tǒng)和分時(shí)系統(tǒng)，特點(diǎn)：適合于多道程序系統(tǒng)和分時(shí)系統(tǒng)，支持多個(gè)程序并發(fā)執(zhí)行；支持多個(gè)程序并發(fā)執(zhí)行；16164.2.1 固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理各個(gè)用戶分區(qū)的個(gè)數(shù)、位置和大小一旦確定以后，各個(gè)用戶分區(qū)的個(gè)數(shù)、位置和大小一旦確定以后，就就固定不變固定不變。為了滿足不同程序的存儲(chǔ)需要，各分。為了滿足不同程序的存儲(chǔ)需要，各分區(qū)的大小可相等，也可不等。區(qū)的大小可相等，也可不等。 分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)分區(qū)大小相等：只適合于多個(gè)相同程序的并發(fā)執(zhí)行（處理多個(gè)類型相同的對(duì)象）；行（處理多個(gè)類型相同的對(duì)象）； 分區(qū)大小不等：多個(gè)小分區(qū)、適量的中等分區(qū)、分區(qū)大小不等：多

9、個(gè)小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)；少量的大分區(qū)； 當(dāng)進(jìn)程到來時(shí)，根據(jù)它的大小，把它放置到相應(yīng)當(dāng)進(jìn)程到來時(shí)，根據(jù)它的大小，把它放置到相應(yīng)的輸入隊(duì)列當(dāng)中，等待合適的空閑分區(qū)。兩種實(shí)的輸入隊(duì)列當(dāng)中，等待合適的空閑分區(qū)。兩種實(shí)現(xiàn)方式：現(xiàn)方式：多個(gè)輸入隊(duì)列多個(gè)輸入隊(duì)列和和單個(gè)輸入隊(duì)列單個(gè)輸入隊(duì)列。1717多個(gè)輸入隊(duì)列多個(gè)輸入隊(duì)列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)700K400K100K0200K800K對(duì)于每一個(gè)用戶分區(qū)，對(duì)于每一個(gè)用戶分區(qū)，都有一個(gè)都有一個(gè)輸入隊(duì)列輸入隊(duì)列。當(dāng)。當(dāng)一個(gè)新的進(jìn)程到來時(shí)，一個(gè)新的進(jìn)程到來時(shí)，把它加入到某個(gè)輸入隊(duì)把它加入到某個(gè)輸入隊(duì)列當(dāng)中，該輸入隊(duì)

10、列所列當(dāng)中，該輸入隊(duì)列所對(duì)應(yīng)的分區(qū)，是能夠裝對(duì)應(yīng)的分區(qū)，是能夠裝下該進(jìn)程的最小分區(qū)。下該進(jìn)程的最小分區(qū)。缺點(diǎn)：可能出現(xiàn)小分區(qū)缺點(diǎn)：可能出現(xiàn)小分區(qū)的輸入隊(duì)列是滿的，而的輸入隊(duì)列是滿的，而大分區(qū)的輸入隊(duì)列卻空大分區(qū)的輸入隊(duì)列卻空著（著（如分區(qū)如分區(qū)1和分區(qū)和分區(qū)3的的的情形的情形），從而造成資），從而造成資源的浪費(fèi)。源的浪費(fèi)。180K1818單個(gè)輸入隊(duì)列單個(gè)輸入隊(duì)列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)700K400K100K0200K800K對(duì)于所有的用戶分對(duì)于所有的用戶分區(qū)，只有一個(gè)統(tǒng)一區(qū)，只有一個(gè)統(tǒng)一的輸入隊(duì)列。當(dāng)一的輸入隊(duì)列。當(dāng)一個(gè)新進(jìn)程到來時(shí)，個(gè)新進(jìn)程到來時(shí)，把它加入到

11、該輸入把它加入到該輸入隊(duì)列當(dāng)中，然后當(dāng)隊(duì)列當(dāng)中，然后當(dāng)某個(gè)分區(qū)空閑時(shí)：某個(gè)分區(qū)空閑時(shí)： 離隊(duì)首最近的、離隊(duì)首最近的、能裝入該分區(qū)的能裝入該分區(qū)的進(jìn)程被選中；進(jìn)程被選中； 搜索整個(gè)隊(duì)列，搜索整個(gè)隊(duì)列，選擇能裝入該分選擇能裝入該分區(qū)的最大進(jìn)程。區(qū)的最大進(jìn)程。1919如何實(shí)現(xiàn)固定分區(qū)存儲(chǔ)管理？如何實(shí)現(xiàn)固定分區(qū)存儲(chǔ)管理？數(shù)據(jù)結(jié)構(gòu)、分配、回收。數(shù)據(jù)結(jié)構(gòu)、分配、回收。2020固定分區(qū)的實(shí)現(xiàn)固定分區(qū)的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)：設(shè)置數(shù)據(jù)結(jié)構(gòu)：設(shè)置內(nèi)存分配表內(nèi)存分配表內(nèi)存分配：先放入輸入隊(duì)列，然后采用內(nèi)存分配：先放入輸入隊(duì)列，然后采用 最先匹配法、最佳匹配法最先匹配法、最佳匹配法 等算法。等算法。內(nèi)存回收：簡單內(nèi)存回收：簡

12、單分區(qū)號(hào)分區(qū)號(hào) 起始地址起始地址長度長度狀態(tài)狀態(tài)進(jìn)程名進(jìn)程名2121固定分區(qū)的缺點(diǎn)：固定分區(qū)的缺點(diǎn)： 內(nèi)存利用率不高，內(nèi)碎片造成很大浪費(fèi)。內(nèi)存利用率不高，內(nèi)碎片造成很大浪費(fèi)。所謂所謂內(nèi)碎片內(nèi)碎片，即進(jìn)程所占用分區(qū)之內(nèi)的未，即進(jìn)程所占用分區(qū)之內(nèi)的未被利用的空間（再小的進(jìn)程都要占用一整被利用的空間（再小的進(jìn)程都要占用一整個(gè)分區(qū)）。個(gè)分區(qū)）。 分區(qū)的總數(shù)固定，限制了并發(fā)執(zhí)行的程序分區(qū)的總數(shù)固定，限制了并發(fā)執(zhí)行的程序個(gè)數(shù)，不夠靈活。個(gè)數(shù)，不夠靈活。 進(jìn)程的保護(hù)（應(yīng)用程序可能破壞進(jìn)程的保護(hù)（應(yīng)用程序可能破壞OS和其他和其他應(yīng)用程序）應(yīng)用程序）固定分區(qū)的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，固定分區(qū)的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小開銷

13、小。2222 地址空間的大小有限：不能超過物理內(nèi)存地址空間的大小有限：不能超過物理內(nèi)存的大小。的大小。 如何提高內(nèi)存的利用效率？如何提高內(nèi)存的利用效率？如何確定分區(qū)的大小？如何確定分區(qū)的大?。糠謪^(qū)太小怎么辦？分區(qū)太小怎么辦？分區(qū)太大怎么辦（內(nèi)碎片）？分區(qū)太大怎么辦（內(nèi)碎片）？為此，人們又提出了為此，人們又提出了可變分區(qū)（動(dòng)態(tài)分區(qū)）可變分區(qū)（動(dòng)態(tài)分區(qū)）的存儲(chǔ)管理技術(shù)。的存儲(chǔ)管理技術(shù)。23234.2.2 可變分區(qū)存儲(chǔ)管理可變分區(qū)存儲(chǔ)管理分區(qū)不是預(yù)先劃分好的固定區(qū)域，而是動(dòng)態(tài)創(chuàng)建的。分區(qū)不是預(yù)先劃分好的固定區(qū)域，而是動(dòng)態(tài)創(chuàng)建的。在裝入一個(gè)程序時(shí)，根據(jù)它的需求和內(nèi)存空間的使用在裝入一個(gè)程序時(shí)，根據(jù)它的

14、需求和內(nèi)存空間的使用情況來決定是否分配。具體來說，系統(tǒng)生成后，操作情況來決定是否分配。具體來說，系統(tǒng)生成后，操作系統(tǒng)會(huì)占用內(nèi)存的一部分（一般在內(nèi)存地址低端），系統(tǒng)會(huì)占用內(nèi)存的一部分（一般在內(nèi)存地址低端），其余空間為一個(gè)完整的大空閑區(qū)。當(dāng)一個(gè)程序要求裝其余空間為一個(gè)完整的大空閑區(qū)。當(dāng)一個(gè)程序要求裝入內(nèi)存運(yùn)行時(shí)，系統(tǒng)從這個(gè)空閑區(qū)中劃分一塊分配給入內(nèi)存運(yùn)行時(shí)，系統(tǒng)從這個(gè)空閑區(qū)中劃分一塊分配給它，當(dāng)程序完成后釋放所占用的存儲(chǔ)區(qū)。隨著一系列它，當(dāng)程序完成后釋放所占用的存儲(chǔ)區(qū)。隨著一系列的內(nèi)存分配和回收，原來的一整塊大空閑區(qū)就形成了的內(nèi)存分配和回收，原來的一整塊大空閑區(qū)就形成了若干占用區(qū)和空閑區(qū)相間的布局

15、。若干占用區(qū)和空閑區(qū)相間的布局。2424操作系統(tǒng)操作系統(tǒng) 128K01024K128K空閑區(qū)空閑區(qū) 896K操作系統(tǒng)操作系統(tǒng) 128K01024K128K空閑區(qū)空閑區(qū) 576K進(jìn)程進(jìn)程1 320K448K2525操作系統(tǒng)操作系統(tǒng) 128K01024K128K空閑區(qū)空閑區(qū) 352K進(jìn)程進(jìn)程1 320K448K進(jìn)程進(jìn)程2 224K672K操作系統(tǒng)操作系統(tǒng) 128K01024K128K空閑區(qū)空閑區(qū) 64K進(jìn)程進(jìn)程1 320K448K進(jìn)程進(jìn)程2 224K672K進(jìn)程進(jìn)程3 288K960K空閑區(qū)空閑區(qū) 224K250K？2626操作系統(tǒng)操作系統(tǒng) 128K01024K128K空閑區(qū)空閑區(qū) 64K進(jìn)程進(jìn)程

16、1 320K448K進(jìn)程進(jìn)程4 128K672K進(jìn)程進(jìn)程3 288K960K576K空閑區(qū)空閑區(qū) 96K空閑區(qū)空閑區(qū) 320K 可變分區(qū)的特點(diǎn)：可變分區(qū)的特點(diǎn)： 在可變分區(qū)當(dāng)中，分區(qū)的個(gè)在可變分區(qū)當(dāng)中，分區(qū)的個(gè)數(shù)、位置和大小都是隨進(jìn)程數(shù)、位置和大小都是隨進(jìn)程的進(jìn)出而的進(jìn)出而動(dòng)態(tài)變化動(dòng)態(tài)變化的，非常的，非常靈活，避免了在固定分區(qū)中靈活，避免了在固定分區(qū)中因分區(qū)大小不當(dāng)所造成的因分區(qū)大小不當(dāng)所造成的內(nèi)內(nèi)碎片碎片，提高了內(nèi)存利用率。，提高了內(nèi)存利用率。 有有外碎片外碎片，即各個(gè)占用分區(qū)，即各個(gè)占用分區(qū)之間難以利用的空閑分區(qū)之間難以利用的空閑分區(qū)（通常是小空閑分區(qū)）；（通常是小空閑分區(qū)）； 使得內(nèi)存的

17、分配、回收和管使得內(nèi)存的分配、回收和管理更為復(fù)雜。理更為復(fù)雜。2727如何實(shí)現(xiàn)可變分區(qū)的存儲(chǔ)管理技術(shù)？如何實(shí)現(xiàn)可變分區(qū)的存儲(chǔ)管理技術(shù)？1. 內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)；內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)；2. 內(nèi)存的分配算法內(nèi)存的分配算法3. 內(nèi)存的回收方法內(nèi)存的回收方法4. 碎片問題碎片問題4.2.3 可變分區(qū)的實(shí)現(xiàn)可變分區(qū)的實(shí)現(xiàn)28281. 分區(qū)鏈表分區(qū)鏈表系統(tǒng)維護(hù)一個(gè)有序的分區(qū)鏈表，來跟蹤記錄每一個(gè)內(nèi)系統(tǒng)維護(hù)一個(gè)有序的分區(qū)鏈表，來跟蹤記錄每一個(gè)內(nèi)存分區(qū)的情況，包括該分區(qū)的狀態(tài)（已分配或空閑）存分區(qū)的情況，包括該分區(qū)的狀態(tài)（已分配或空閑）起始地址、長度等信息。起始地址、長度等信息。ABCDE0581418 202

18、62932占占 0 5空空 5 3占占 8 6占占144空空182占占206占占263空空293X空閑空閑起始起始 長度長度占用占用29292. 分區(qū)分配算法分區(qū)分配算法分區(qū)分配算法：當(dāng)一個(gè)新的進(jìn)程來到時(shí)，需分區(qū)分配算法：當(dāng)一個(gè)新的進(jìn)程來到時(shí)，需為它尋找某個(gè)空閑分區(qū)，其大小必須大于或?yàn)樗鼘ふ夷硞€(gè)空閑分區(qū)，其大小必須大于或等于該進(jìn)程的要求。若是大于要求，則將該等于該進(jìn)程的要求。若是大于要求，則將該分區(qū)分割成兩個(gè)分區(qū)，其中一個(gè)分區(qū)為要求分區(qū)分割成兩個(gè)分區(qū)，其中一個(gè)分區(qū)為要求的大小并標(biāo)記為的大小并標(biāo)記為“占用占用”，而另一個(gè)分區(qū)為余，而另一個(gè)分區(qū)為余下部分并標(biāo)記為下部分并標(biāo)記為“空閑空閑”。分區(qū)的先

19、后次序通。分區(qū)的先后次序通常是從內(nèi)存低端到高端。常是從內(nèi)存低端到高端。分區(qū)分配算法主要有：最先匹配法、下次匹分區(qū)分配算法主要有：最先匹配法、下次匹配法、最佳匹配法、最壞匹配法。配法、最佳匹配法、最壞匹配法。3030最先匹配法最先匹配法 (first-fit) ：假設(shè)新進(jìn)程對(duì)內(nèi)存大小的：假設(shè)新進(jìn)程對(duì)內(nèi)存大小的要求為要求為M，那么從分區(qū)鏈表的首結(jié)點(diǎn)開始，將每，那么從分區(qū)鏈表的首結(jié)點(diǎn)開始，將每一個(gè)一個(gè)“空閑空閑”結(jié)點(diǎn)的長度與結(jié)點(diǎn)的長度與M進(jìn)行比較，看是否進(jìn)行比較，看是否大于或等于它，直到找到第一個(gè)符合要求的結(jié)點(diǎn)大于或等于它，直到找到第一個(gè)符合要求的結(jié)點(diǎn)。然后把它所對(duì)應(yīng)的空閑分區(qū)分割為二個(gè)小分區(qū)。然后

20、把它所對(duì)應(yīng)的空閑分區(qū)分割為二個(gè)小分區(qū)，一個(gè)用于裝入該進(jìn)程，另一個(gè)仍然空閑。與之，一個(gè)用于裝入該進(jìn)程，另一個(gè)仍然空閑。與之相對(duì)應(yīng)，相對(duì)應(yīng)，把該結(jié)點(diǎn)也一分為二把該結(jié)點(diǎn)也一分為二，并修改相應(yīng)內(nèi)容，并修改相應(yīng)內(nèi)容。F查找的結(jié)點(diǎn)很少，因而查找的結(jié)點(diǎn)很少，因而速度快速度快；F算法的實(shí)質(zhì)是盡可能利用低地址部分的空閑算法的實(shí)質(zhì)是盡可能利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，區(qū)，而盡量地保證高地址部分的大空閑區(qū)，使其不被分割成小的區(qū)，這樣當(dāng)以后有大的使其不被分割成小的區(qū)，這樣當(dāng)以后有大的進(jìn)程到來時(shí)，有足夠大的空閑區(qū)來滿足它。進(jìn)程到來時(shí)，有足夠大的空閑區(qū)來滿足它。3131下次匹配法下次匹配法 (

21、next-fit) ：與最先匹配法的思路是相：與最先匹配法的思路是相似的，只不過每一次當(dāng)它找到一個(gè)合適的結(jié)點(diǎn)（似的，只不過每一次當(dāng)它找到一個(gè)合適的結(jié)點(diǎn)（分區(qū)）時(shí)，就把當(dāng)前的位置記錄下來。然后等下分區(qū)）時(shí)，就把當(dāng)前的位置記錄下來。然后等下一次新進(jìn)程到來的時(shí)候，就從這個(gè)位置開始繼續(xù)一次新進(jìn)程到來的時(shí)候，就從這個(gè)位置開始繼續(xù)往下找（到鏈表結(jié)尾時(shí)再回到開頭），直到找到往下找（到鏈表結(jié)尾時(shí)再回到開頭），直到找到符合要求的第一個(gè)分區(qū)。而不是象最先匹配法那符合要求的第一個(gè)分區(qū)。而不是象最先匹配法那樣，每次都是從鏈表的首結(jié)點(diǎn)開始找。樣，每次都是從鏈表的首結(jié)點(diǎn)開始找。F查找的結(jié)點(diǎn)很少，因而速度快；查找的結(jié)點(diǎn)很少

22、，因而速度快；F該算法使空閑分區(qū)分布得更均勻，但較大的該算法使空閑分區(qū)分布得更均勻，但較大的空閑分區(qū)不易保留。從性能上略遜于最先匹空閑分區(qū)不易保留。從性能上略遜于最先匹配法。配法。3232最佳匹配法最佳匹配法 (best-fit) ：將申請(qǐng)內(nèi)存的進(jìn)程裝入到：將申請(qǐng)內(nèi)存的進(jìn)程裝入到與其大小最接近的空閑分區(qū)當(dāng)中。算法的性能最與其大小最接近的空閑分區(qū)當(dāng)中。算法的性能最差，最大缺點(diǎn)是分割后剩余的空閑分區(qū)將會(huì)很小差，最大缺點(diǎn)是分割后剩余的空閑分區(qū)將會(huì)很小，直至無法使用，從而造成浪費(fèi)（，直至無法使用，從而造成浪費(fèi)（與固定分區(qū)是與固定分區(qū)是不同的不同的）。）。最壞匹配法最壞匹配法(worst-fit)：每次

23、分配時(shí)，總是將最大：每次分配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，其依據(jù)是當(dāng)?shù)目臻e區(qū)切去一部分分配給請(qǐng)求者，其依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割了一部分后可能仍是一一個(gè)很大的空閑區(qū)被切割了一部分后可能仍是一個(gè)較大的空閑區(qū)，從而避免了空閑區(qū)越分越小的個(gè)較大的空閑區(qū)，從而避免了空閑區(qū)越分越小的問題。這種算法基本不留下小的空閑分區(qū)，但較問題。這種算法基本不留下小的空閑分區(qū)，但較大的空閑分區(qū)也不被保留。大的空閑分區(qū)也不被保留。3333Lastallocatedblock (14K)BeforeAfter8K8K12K12K22K18K6K6K8K8K14K14K6K2K36K20KNext Fit

24、Free blockAllocated blockBest FitFirst Fit16K16K16KWorst Fit地址低端地址低端地址高端地址高端16K新進(jìn)程新進(jìn)程34343. 分區(qū)回收算法分區(qū)回收算法分區(qū)回收算法分區(qū)回收算法：當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放它所占：當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放它所占用的分區(qū)后，需要將相鄰的幾個(gè)空閑分區(qū)合并為一用的分區(qū)后，需要將相鄰的幾個(gè)空閑分區(qū)合并為一個(gè)大的空閑分區(qū)。具體來說，可分以下四種情況：個(gè)大的空閑分區(qū)。具體來說，可分以下四種情況：在分區(qū)回收后，可以很方便地更新分區(qū)鏈表。在分區(qū)回收后，可以很方便地更新分區(qū)鏈表。3535占占 0 5占占 5 3占占 8 6(a

25、)進(jìn)程進(jìn)程A進(jìn)程進(jìn)程X進(jìn)程進(jìn)程B空空空閑區(qū)空閑區(qū)50占占35占占68空空(b)進(jìn)程進(jìn)程A進(jìn)程進(jìn)程X空閑區(qū)空閑區(qū)50占占95空空進(jìn)程進(jìn)程A空閑區(qū)空閑區(qū)50空空35占占68空空(d)空閑區(qū)空閑區(qū)進(jìn)程進(jìn)程X空閑區(qū)空閑區(qū)140空空空閑區(qū)空閑區(qū)(c) 略略36364. 碎片問題碎片問題經(jīng)過一段時(shí)間的分配與回收后，內(nèi)存中存在著很多經(jīng)過一段時(shí)間的分配與回收后，內(nèi)存中存在著很多不連續(xù)的很小的空閑分區(qū)（外碎片）。當(dāng)一個(gè)新進(jìn)不連續(xù)的很小的空閑分區(qū)（外碎片）。當(dāng)一個(gè)新進(jìn)程到來時(shí)，這些小的空閑區(qū)都不足以滿足分配要求，程到來時(shí)，這些小的空閑區(qū)都不足以滿足分配要求，但其總和滿足分配要求。這就是（外）碎片問題。但其總和滿足

26、分配要求。這就是（外）碎片問題。內(nèi)存緊縮內(nèi)存緊縮（Compaction）：把所有的進(jìn)程盡可能）：把所有的進(jìn)程盡可能地往地址低端移動(dòng)，相應(yīng)的，那些空閑的小分區(qū)就地往地址低端移動(dòng)，相應(yīng)的，那些空閑的小分區(qū)就會(huì)往地址的高端移動(dòng)，從而形成一個(gè)大的空閑區(qū)。會(huì)往地址的高端移動(dòng)，從而形成一個(gè)大的空閑區(qū)。 所有進(jìn)程的移動(dòng)需要大量的所有進(jìn)程的移動(dòng)需要大量的CPU時(shí)間；時(shí)間； 如何解決程序移動(dòng)后，地址的重定位問題？如何解決程序移動(dòng)后，地址的重定位問題？37374.2.5 內(nèi)存中的程序執(zhí)行內(nèi)存中的程序執(zhí)行進(jìn)程執(zhí)行時(shí)的進(jìn)程執(zhí)行時(shí)的內(nèi)存分區(qū)布局內(nèi)存分區(qū)布局棧棧動(dòng)態(tài)堆空間動(dòng)態(tài)堆空間(malloc)數(shù)據(jù)數(shù)據(jù)代碼代碼低地址低

27、地址高地址高地址PCSP3838變量的存儲(chǔ)與作用域/* 全局變量，固定地址，其他源文件可見全局變量，固定地址，其他源文件可見 */int global_static;/* 靜態(tài)全局變量，固定地址，但只在本文件中可見靜態(tài)全局變量，固定地址，但只在本文件中可見 */static int file_static;/* 函數(shù)參數(shù)：位于棧幀當(dāng)中，動(dòng)態(tài)創(chuàng)建，動(dòng)態(tài)釋放函數(shù)參數(shù)：位于棧幀當(dāng)中，動(dòng)態(tài)創(chuàng)建，動(dòng)態(tài)釋放 */int foo(int auto_param)/ 代碼代碼 /*靜態(tài)局部變量，固定地址，只在本函數(shù)中可見靜態(tài)局部變量，固定地址，只在本函數(shù)中可見 */ static int func_static

28、; /* 普通局部變量，位于棧幀當(dāng)中，只在本函數(shù)可見普通局部變量，位于棧幀當(dāng)中，只在本函數(shù)可見 */ int auto_i, auto_a10; /* 動(dòng)態(tài)申請(qǐng)的內(nèi)存空間，位于堆當(dāng)中動(dòng)態(tài)申請(qǐng)的內(nèi)存空間，位于堆當(dāng)中 */ double *auto_d = malloc(sizeof(double)*5); return auto_i;39394.2.5 重定位和存儲(chǔ)保護(hù)重定位和存儲(chǔ)保護(hù)1. 地址映射（重定位）地址映射（重定位）1）物理地址物理地址也叫內(nèi)存地址、絕對(duì)地址，實(shí)地址；也叫內(nèi)存地址、絕對(duì)地址，實(shí)地址；把內(nèi)存分成很多個(gè)大小相等的存儲(chǔ)單元，每個(gè)把內(nèi)存分成很多個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一

29、個(gè)編號(hào)，這個(gè)編號(hào)稱為物理地址；單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為物理地址；物理地址可以直接尋址；物理地址可以直接尋址；物理地址的集合稱為物理地址空間（內(nèi)存地址物理地址的集合稱為物理地址空間（內(nèi)存地址空間），它是一個(gè)一維的線性空間?？臻g），它是一個(gè)一維的線性空間。40402 2）邏輯地址邏輯地址也叫相對(duì)地址，虛地址；也叫相對(duì)地址，虛地址；用戶程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目用戶程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為0，其余指令中的地址都是相對(duì)首地址來編址；，其余指令中的地址都是相對(duì)首地址來編址；不能用邏輯地址在內(nèi)存中讀取

30、信息。不能用邏輯地址在內(nèi)存中讀取信息。3 3）地址映射）地址映射為了保證為了保證CPU執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元，執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元，需要將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由需要將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接尋址的物理地址，這一過程稱為地址機(jī)器直接尋址的物理地址，這一過程稱為地址映射。映射。4141int x, y;x = 5;y = x + 3;源程序源程序編譯編譯鏈接鏈接裝入裝入分區(qū)分區(qū)0100200300.str 5, 200ldr R1, 200add R2,R1,3str R2, 204邏輯地址空間邏輯地址空間204xy1000.110012001300物理

31、地址空間物理地址空間str 5, 200ldr R1, 200add R2,R1,3str R2, 2041204xy有無問題？有無問題？4242為了保證為了保證CPU執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元，執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元，在裝入程序時(shí)必須進(jìn)行地址映射，將程序中的在裝入程序時(shí)必須進(jìn)行地址映射，將程序中的邏輯地址轉(zhuǎn)換為物理地址。這主要有兩種方式：邏輯地址轉(zhuǎn)換為物理地址。這主要有兩種方式：& 靜態(tài)地址映射（靜態(tài)重定位）：當(dāng)用戶程序靜態(tài)地址映射（靜態(tài)重定位）：當(dāng)用戶程序被裝入內(nèi)存時(shí)，直接對(duì)被裝入內(nèi)存時(shí)，直接對(duì)指令代碼指令代碼進(jìn)行修改，進(jìn)行修改，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以一次性實(shí)現(xiàn)邏輯

32、地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。后不再轉(zhuǎn)換。 在可執(zhí)行文件中，需在可執(zhí)行文件中，需列出列出各個(gè)需要重定位各個(gè)需要重定位的地址單元的位置。在裝入時(shí)，由一個(gè)裝的地址單元的位置。在裝入時(shí)，由一個(gè)裝入程序（加載程序）來完成；入程序（加載程序）來完成； 實(shí)現(xiàn)簡單，不需要硬件的支持；實(shí)現(xiàn)簡單，不需要硬件的支持； 程序裝入內(nèi)存后程序裝入內(nèi)存后不能移動(dòng)不能移動(dòng)。4343裝入分區(qū)裝入分區(qū)0100200300.str 5, 200ldr R1, 200add R2,R1,3str R2, 204邏輯地址空間邏輯地址空間204xy1000.110012001300物理地址空間物理地址空間str 5, 1200l

33、dr R1,1200add R2,R1,3str R2,12041204xy4444& 動(dòng)態(tài)地址映射（動(dòng)態(tài)重定位）：當(dāng)用戶程序被裝動(dòng)態(tài)地址映射（動(dòng)態(tài)重定位）：當(dāng)用戶程序被裝入內(nèi)存時(shí)，不對(duì)指令代碼做任何修改。而是在程入內(nèi)存時(shí)，不對(duì)指令代碼做任何修改。而是在程序序運(yùn)行運(yùn)行過程中，當(dāng)需要訪問內(nèi)存單元時(shí)再來進(jìn)行過程中，當(dāng)需要訪問內(nèi)存單元時(shí)再來進(jìn)行地址轉(zhuǎn)換（即在逐條執(zhí)行指令時(shí)完成轉(zhuǎn)換）。地址轉(zhuǎn)換（即在逐條執(zhí)行指令時(shí)完成轉(zhuǎn)換）。 為提高效率，此工作一般由硬件地址映射機(jī)為提高效率，此工作一般由硬件地址映射機(jī)制來完成，通常的做法是設(shè)置一個(gè)基地址寄制來完成，通常的做法是設(shè)置一個(gè)基地址寄存器（重定位寄存器），并把

34、進(jìn)程所在分區(qū)存器（重定位寄存器），并把進(jìn)程所在分區(qū)的起始地址裝入到該寄存器當(dāng)中；的起始地址裝入到該寄存器當(dāng)中； 在程序運(yùn)行過程中，當(dāng)需要訪問內(nèi)存單元時(shí)在程序運(yùn)行過程中，當(dāng)需要訪問內(nèi)存單元時(shí),硬件就自動(dòng)地將其中的相對(duì)地址加上基地址硬件就自動(dòng)地將其中的相對(duì)地址加上基地址寄存器的內(nèi)容，形成實(shí)際的物理地址，然后寄存器的內(nèi)容，形成實(shí)際的物理地址，然后按該地址去執(zhí)行。按該地址去執(zhí)行。4545裝入裝入分區(qū)分區(qū)0100200300.str 5, 200ldr R1, 200add R2,R1,3str R2, 204邏輯地址空間邏輯地址空間204xy1000.110012001300物理地址空間物理地址空間s

35、tr 5, 200ldr R1, 200add R2,R1,3str R2, 2041204xy+基地址寄存器基地址寄存器相對(duì)地址相對(duì)地址10002001.基地址寄存器基地址寄存器 在哪？在哪？2.何時(shí)填入何時(shí)填入1000？4646為了防止一個(gè)用戶程序去訪問其他用戶程序?yàn)榱朔乐挂粋€(gè)用戶程序去訪問其他用戶程序的內(nèi)存分區(qū)，保護(hù)操作系統(tǒng)免受用戶程序的的內(nèi)存分區(qū)，保護(hù)操作系統(tǒng)免受用戶程序的破壞，須進(jìn)行存儲(chǔ)保護(hù)。破壞，須進(jìn)行存儲(chǔ)保護(hù)。如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？能否與動(dòng)態(tài)地址映射集成在一起？能否與動(dòng)態(tài)地址映射集成在一起？2. 存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)4747最簡單的做法：在基地址寄存器的基礎(chǔ)上，再增加最簡單的做法：在基

36、地址寄存器的基礎(chǔ)上，再增加一個(gè)限長寄存器，記錄分區(qū)的長度。這兩者在一起，一個(gè)限長寄存器，記錄分區(qū)的長度。這兩者在一起，就定義了進(jìn)程所在的分區(qū)（就定義了進(jìn)程所在的分區(qū)（寄存器的值存放在哪？寄存器的值存放在哪？）進(jìn)程進(jìn)程B進(jìn)程進(jìn)程A操作系統(tǒng)操作系統(tǒng)100K100K基地址寄存器基地址寄存器限長寄存器限長寄存器邏輯地址必須邏輯地址必須小于限長寄存小于限長寄存器的值。硬件器的值。硬件保護(hù)這兩個(gè)寄保護(hù)這兩個(gè)寄存器，用戶程存器，用戶程序不能修改。序不能修改。0100K200K300K4848CPUMMU內(nèi)存內(nèi)存磁盤磁盤控制器控制器總線總線CPU組件組件存儲(chǔ)管存儲(chǔ)管理單元理單元CPU發(fā)送邏輯地址給發(fā)送邏輯地址

37、給MMUMMU發(fā)送物理地址給內(nèi)存發(fā)送物理地址給內(nèi)存動(dòng)態(tài)地址映射動(dòng)態(tài)地址映射49494.3 頁式和段式存儲(chǔ)管理頁式和段式存儲(chǔ)管理頁式存儲(chǔ)管理頁式存儲(chǔ)管理段式存儲(chǔ)管理段式存儲(chǔ)管理頁式管理與段式管理的比較頁式管理與段式管理的比較段頁式存儲(chǔ)管理段頁式存儲(chǔ)管理50504.3.1 頁式存儲(chǔ)管理頁式存儲(chǔ)管理分區(qū)存儲(chǔ)管理方案的一個(gè)特性是連續(xù)性，這將會(huì)分區(qū)存儲(chǔ)管理方案的一個(gè)特性是連續(xù)性，這將會(huì)導(dǎo)致導(dǎo)致碎片問題（內(nèi)碎片和外碎片）碎片問題（內(nèi)碎片和外碎片）。為有效地解決。為有效地解決這些問題，人們又提出了頁式存儲(chǔ)管理方案，其基這些問題，人們又提出了頁式存儲(chǔ)管理方案，其基本出發(fā)點(diǎn)是打破存儲(chǔ)分配的連續(xù)性，使得一個(gè)程序本

38、出發(fā)點(diǎn)是打破存儲(chǔ)分配的連續(xù)性，使得一個(gè)程序的邏輯地址空間可以分布在若干個(gè)離散的內(nèi)存塊上，的邏輯地址空間可以分布在若干個(gè)離散的內(nèi)存塊上，從而達(dá)到充分利用內(nèi)存，提高內(nèi)存利用率的目的。從而達(dá)到充分利用內(nèi)存，提高內(nèi)存利用率的目的。51511. 基本原理基本原理把物理內(nèi)存劃分為許多個(gè)固定大小的內(nèi)存塊，稱把物理內(nèi)存劃分為許多個(gè)固定大小的內(nèi)存塊，稱為為物理頁面物理頁面，或，或頁框頁框（page frame）；）；把邏輯地址空間劃分為大小相同的塊，稱為把邏輯地址空間劃分為大小相同的塊，稱為邏輯邏輯頁面頁面，或簡稱，或簡稱頁面頁面（page）；）；頁面大小為頁面大小為2n，一般在，一般在512字節(jié)到字節(jié)到8K字

39、節(jié)之間；字節(jié)之間；當(dāng)一個(gè)用戶程序裝入內(nèi)存時(shí)，以頁面為單位進(jìn)行當(dāng)一個(gè)用戶程序裝入內(nèi)存時(shí)，以頁面為單位進(jìn)行分配。若要運(yùn)行一個(gè)大小為分配。若要運(yùn)行一個(gè)大小為n個(gè)頁面的程序，需個(gè)頁面的程序，需要有要有n個(gè)空閑的物理頁面把它裝入，這些頁面不個(gè)空閑的物理頁面把它裝入，這些頁面不必是連續(xù)的。必是連續(xù)的。生活中的例子生活中的例子5252進(jìn)程進(jìn)程3 第第0頁頁進(jìn)程進(jìn)程2 第第2頁頁進(jìn)程進(jìn)程1 第第1頁頁進(jìn)程進(jìn)程1 第第0頁頁進(jìn)程進(jìn)程2 第第1頁頁進(jìn)程進(jìn)程2 第第0頁頁操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)操作系統(tǒng)0K1K2K3K4K5K6K7K8K9K10K0K1K2K進(jìn)程進(jìn)程1 地址空間地址空間進(jìn)程進(jìn)程2 地址空間地址空間

40、0K1K2K3K0K1K進(jìn)程進(jìn)程3 地址空間地址空間內(nèi)存內(nèi)存5353用于存儲(chǔ)管理的用于存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是什么？是什么？當(dāng)一個(gè)進(jìn)程到來時(shí)，如何給它當(dāng)一個(gè)進(jìn)程到來時(shí)，如何給它分配分配內(nèi)存？內(nèi)存？當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放釋放它所占用的內(nèi)它所占用的內(nèi)存空間后，如何回收內(nèi)存？存空間后，如何回收內(nèi)存？當(dāng)一個(gè)進(jìn)程被加載到內(nèi)存以后，它如何正當(dāng)一個(gè)進(jìn)程被加載到內(nèi)存以后，它如何正確運(yùn)行（確運(yùn)行（地址重定位地址重定位）？）？頁式存儲(chǔ)管理要解決如下問題：頁式存儲(chǔ)管理要解決如下問題：54542. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)頁表頁表：系統(tǒng)為每一個(gè)進(jìn)程都建立了一個(gè)頁：系統(tǒng)為每一個(gè)進(jìn)程都建立了一個(gè)頁表，頁

41、表給出了邏輯頁面號(hào)和具體內(nèi)存塊表，頁表給出了邏輯頁面號(hào)和具體內(nèi)存塊號(hào)（物理頁面號(hào)）之間的對(duì)應(yīng)關(guān)系。號(hào)（物理頁面號(hào)）之間的對(duì)應(yīng)關(guān)系。邏輯頁號(hào)邏輯頁號(hào)內(nèi)存塊號(hào)內(nèi)存塊號(hào)頁表頁表01n-1如何實(shí)現(xiàn)頁表？如何實(shí)現(xiàn)頁表？5555（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”） 邏輯邏輯地址空間地址空間頁表頁表物理內(nèi)存物理內(nèi)存物理頁面號(hào)物理頁面號(hào)5656物理頁面表物理頁面表：在系統(tǒng)中設(shè)立一張物理頁面：在系統(tǒng)中設(shè)立一張物理頁面表，用來描述內(nèi)存空間當(dāng)中，各個(gè)物理頁表，用來描述內(nèi)存空間當(dāng)中，各個(gè)物理頁面的分配使用狀況。具體

42、實(shí)現(xiàn)：位示圖，面的分配使用狀況。具體實(shí)現(xiàn)：位示圖，空閑頁面鏈表。空閑頁面鏈表。0310/10/10/10/10/1017空閑頁數(shù)空閑頁數(shù)位示圖位示圖內(nèi)存中共有內(nèi)存中共有256個(gè)物理個(gè)物理頁面，可以頁面，可以用字長為用字長為32位的位的8個(gè)字個(gè)字來構(gòu)成位示來構(gòu)成位示圖。圖。57573. 內(nèi)存的分配與回收內(nèi)存的分配與回收內(nèi)存的分配與回收算法與物理頁面表的具內(nèi)存的分配與回收算法與物理頁面表的具體實(shí)現(xiàn)方法有關(guān)。這里以位示圖為例。體實(shí)現(xiàn)方法有關(guān)。這里以位示圖為例。內(nèi)存的分配：內(nèi)存的分配： 計(jì)算一個(gè)進(jìn)程所需要的計(jì)算一個(gè)進(jìn)程所需要的頁面數(shù)頁面數(shù)N，并查，并查看位示圖，看是否還有看位示圖，看是否還有N個(gè)空閑頁

43、面?zhèn)€空閑頁面； 若有，則申請(qǐng)一個(gè)頁表，其長度為若有，則申請(qǐng)一個(gè)頁表，其長度為N，并并把頁表的起始地址填入把頁表的起始地址填入PCB； 分配分配N個(gè)空閑的物理頁面，將其編號(hào)填個(gè)空閑的物理頁面，將其編號(hào)填入頁表；入頁表； 修改位示圖（修改位示圖（01，空閑頁面數(shù)，空閑頁面數(shù)N）5858內(nèi)存的回收：當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放內(nèi)存的回收：當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束，釋放它所占用的內(nèi)存空間后，需要對(duì)這些物理它所占用的內(nèi)存空間后，需要對(duì)這些物理頁面進(jìn)行回收。頁面進(jìn)行回收。 對(duì)于每一個(gè)物理頁面，對(duì)于每一個(gè)物理頁面，根據(jù)它的編號(hào)計(jì)根據(jù)它的編號(hào)計(jì)算出它在位示圖當(dāng)中的相應(yīng)位置算出它在位示圖當(dāng)中的相應(yīng)位置，并將，并將相應(yīng)位的

44、值從相應(yīng)位的值從1改成改成0； 修改位示圖中的空閑頁面數(shù)：加上修改位示圖中的空閑頁面數(shù)：加上N。59594. 地址映射地址映射為什么要進(jìn)行地址映射？為什么要進(jìn)行地址映射？一個(gè)進(jìn)程的各個(gè)連續(xù)的邏輯頁面，被分散地一個(gè)進(jìn)程的各個(gè)連續(xù)的邏輯頁面，被分散地裝入到內(nèi)存的各個(gè)物理頁面當(dāng)中，在這種情裝入到內(nèi)存的各個(gè)物理頁面當(dāng)中，在這種情形下，怎樣才能保證程序能夠正確地運(yùn)行？形下，怎樣才能保證程序能夠正確地運(yùn)行？能否采用靜態(tài)地址映射方法？能否采用靜態(tài)地址映射方法？能否采用動(dòng)態(tài)地址映射方法？能否采用動(dòng)態(tài)地址映射方法？如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？60601. 對(duì)于給定的對(duì)于給定的邏輯地址邏輯地址，找到邏輯頁，找到邏輯頁面號(hào)

45、和頁內(nèi)偏移地址；面號(hào)和頁內(nèi)偏移地址；2. 查找頁表，找到相應(yīng)的物理頁面號(hào)查找頁表，找到相應(yīng)的物理頁面號(hào)；3. 計(jì)算最終的物理地址。計(jì)算最終的物理地址。6161邏輯地址的劃分邏輯地址的劃分把邏輯地址劃分為兩部分：邏輯頁面號(hào)和把邏輯地址劃分為兩部分：邏輯頁面號(hào)和頁內(nèi)偏移地址。這種劃分是由系統(tǒng)自動(dòng)完頁內(nèi)偏移地址。這種劃分是由系統(tǒng)自動(dòng)完成的，對(duì)用戶是透明的。由于頁面的大小成的，對(duì)用戶是透明的。由于頁面的大小一般為一般為2 2的整數(shù)次冪，因此，地址的高位部的整數(shù)次冪，因此，地址的高位部分即為頁號(hào)，低位部分即為頁內(nèi)偏移地址。分即為頁號(hào)，低位部分即為頁內(nèi)偏移地址。例如，頁面大小為例如，頁面大小為4KB4KB

46、。頁號(hào)頁號(hào) 頁內(nèi)地址頁內(nèi)地址6262邏輯地址為十六進(jìn)制的形式邏輯地址為十六進(jìn)制的形式6363邏輯地址為邏輯地址為十進(jìn)制十進(jìn)制的形式的形式計(jì)算方法：計(jì)算方法：頁號(hào)頁號(hào) 虛地址虛地址 / 頁大小頁大小位移量位移量 虛地址虛地址 % 頁大小頁大小例如：假設(shè)頁面大小為例如：假設(shè)頁面大小為2KB，計(jì)算邏輯地址，計(jì)算邏輯地址7145和和3412的邏輯頁面號(hào)和頁內(nèi)偏移地址。的邏輯頁面號(hào)和頁內(nèi)偏移地址。頁號(hào)：頁號(hào)：3412 / 2048 1頁內(nèi)偏移：頁內(nèi)偏移： 3412 % 2048 1364頁號(hào)：頁號(hào)：7145 / 2048 3頁內(nèi)偏移：頁內(nèi)偏移： 7145 % 2048 1001Why?6464X 頁表保

47、存在內(nèi)存當(dāng)中（頁表保存在內(nèi)存當(dāng)中（用戶用戶/內(nèi)核空間內(nèi)核空間?）;X 設(shè)置一個(gè)設(shè)置一個(gè)頁表基地址寄存器頁表基地址寄存器（Page-table base register，PTBR），用來指向頁表的），用來指向頁表的起始地址；起始地址；X 設(shè)置一個(gè)設(shè)置一個(gè)頁表長度寄存器頁表長度寄存器（Page-table length register，PTLR），用來指示頁表的），用來指示頁表的大小。大小。頁表的具體實(shí)頁表的具體實(shí)現(xiàn)現(xiàn)1. 硬件寄存器位于什么地方？硬件寄存器位于什么地方？2. 其內(nèi)容何時(shí)更新？誰更新？如何更新？其內(nèi)容何時(shí)更新？誰更新？如何更新？6565ProgramPagingMain Mem

48、oryVirtual AddressRegisterPage TablePageFrameOffsetP#Frame #Page Table PtrPage #OffsetFrame #Offset+頁式地址映射頁式地址映射疊加疊加1.需訪問幾次內(nèi)存？需訪問幾次內(nèi)存？2.頁表頁表？頁表頁表？6666頁表長度頁表地址控制寄存器頁號(hào)頁面號(hào)有效地址02132821C4物理地址81C4頁式地址映射舉例頁式地址映射舉例頁號(hào)頁號(hào)頁內(nèi)偏移量頁內(nèi)偏移量6767X 在現(xiàn)有的方案中，每一次訪問內(nèi)存（數(shù)據(jù)在現(xiàn)有的方案中，每一次訪問內(nèi)存（數(shù)據(jù)/指令）時(shí)，都要做指令）時(shí)，都要做兩次訪問兩次訪問內(nèi)存的工作。內(nèi)存的工作。這

49、樣，降低了存取速度，將會(huì)影響整個(gè)系這樣，降低了存取速度，將會(huì)影響整個(gè)系統(tǒng)的使用效率。統(tǒng)的使用效率。X 為縮短頁表的查找時(shí)間，可以采用一種特為縮短頁表的查找時(shí)間，可以采用一種特殊的快速查找硬件：殊的快速查找硬件：TLBTLB (Translation Lookaside Buffer) 或稱或稱associative memory,用來存放那些最常用的頁表項(xiàng)。用來存放那些最常用的頁表項(xiàng)。如何加快頁表的查詢速度？如何加快頁表的查詢速度？6868帶有帶有TLB的頁式地址映射的頁式地址映射（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operating Syst

50、em Concepts”）先先后后為什么管用？為什么管用？69695. 優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)： 沒有外碎片，內(nèi)碎片的大小不超過頁面沒有外碎片，內(nèi)碎片的大小不超過頁面的大?。坏拇笮。?一個(gè)程序不必連續(xù)存放；一個(gè)程序不必連續(xù)存放； 便于管理；便于管理；缺點(diǎn)：缺點(diǎn)： 程序必須程序必須全部全部裝入內(nèi)存；裝入內(nèi)存； 系統(tǒng)必須為系統(tǒng)必須為每個(gè)進(jìn)程每個(gè)進(jìn)程維護(hù)一張頁表。維護(hù)一張頁表。70704.3.2 段式存儲(chǔ)管理段式存儲(chǔ)管理 Why 段式存儲(chǔ)管理？段式存儲(chǔ)管理？頁式存儲(chǔ)管理（和分區(qū)存儲(chǔ)管理）只有一個(gè)頁式存儲(chǔ)管理（和分區(qū)存儲(chǔ)管理）只有一個(gè)邏輯地址空間，即一維的線性邏輯地址空間，即一維的線性連續(xù)空間連續(xù)空間

51、，從，從 0 到某個(gè)最大的邏輯地址。但是從程序員或到某個(gè)最大的邏輯地址。但是從程序員或系統(tǒng)管理的角度來說，一個(gè)程序是由一組模系統(tǒng)管理的角度來說，一個(gè)程序是由一組模塊（片段）所組成的，每個(gè)片段是一個(gè)邏輯塊（片段）所組成的，每個(gè)片段是一個(gè)邏輯單元，如：主程序、全局變量、棧、庫函數(shù)單元，如：主程序、全局變量、棧、庫函數(shù)等。等。7171存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)： 代碼段：一條條指令組成，代碼段：一條條指令組成，只讀，可執(zhí)只讀，可執(zhí)行行，無需寫回磁盤無需寫回磁盤； 數(shù)據(jù)段：全局變量，可修改，可讀寫，數(shù)據(jù)段：全局變量，可修改，可讀寫，需寫回磁盤；需寫回磁盤； 棧：行參、局部變量、棧：行參、局部變量、CPU寄存器、

52、返寄存器、返回地址，可讀寫回地址，可讀寫，是否可執(zhí)行？是否可執(zhí)行？存儲(chǔ)共享：存儲(chǔ)共享：在多個(gè)進(jìn)程之間，共享代碼和數(shù)據(jù)。在多個(gè)進(jìn)程之間，共享代碼和數(shù)據(jù)。72721. 基本原理基本原理對(duì)于程序當(dāng)中的每一個(gè)邏輯單元，設(shè)立一個(gè)完全對(duì)于程序當(dāng)中的每一個(gè)邏輯單元，設(shè)立一個(gè)完全獨(dú)立的地址空間，稱為獨(dú)立的地址空間，稱為“段段”。在每個(gè)段的內(nèi)部。在每個(gè)段的內(nèi)部，是一維的線性連續(xù)地址，從，是一維的線性連續(xù)地址，從0一直到某個(gè)最大的一直到某個(gè)最大的地址。每個(gè)段的大小一般是不相等的，它所包含地址。每個(gè)段的大小一般是不相等的，它所包含的的內(nèi)容內(nèi)容也是不一樣的；也是不一樣的；對(duì)于物理內(nèi)存來說，采用可變分區(qū)（動(dòng)態(tài)分區(qū)）對(duì)于

53、物理內(nèi)存來說，采用可變分區(qū)（動(dòng)態(tài)分區(qū)）的管理方法；的管理方法；當(dāng)一個(gè)程序需要裝入內(nèi)存時(shí)，以段為單位進(jìn)行分當(dāng)一個(gè)程序需要裝入內(nèi)存時(shí)，以段為單位進(jìn)行分配，配，把每一個(gè)段裝入到一個(gè)內(nèi)存分區(qū)當(dāng)中把每一個(gè)段裝入到一個(gè)內(nèi)存分區(qū)當(dāng)中，這些，這些內(nèi)存分區(qū)不必是連續(xù)的。內(nèi)存分區(qū)不必是連續(xù)的。73731423物理內(nèi)存空間物理內(nèi)存空間用戶空間用戶空間1324子函數(shù)子函數(shù)主函數(shù)主函數(shù)棧棧符號(hào)表符號(hào)表0n74742. 具體實(shí)現(xiàn)具體實(shí)現(xiàn)在段式存儲(chǔ)管理中，用戶空間的地址為二元地址在段式存儲(chǔ)管理中，用戶空間的地址為二元地址：(段號(hào)，段內(nèi)偏移段號(hào)，段內(nèi)偏移)。實(shí)現(xiàn)方式：。實(shí)現(xiàn)方式：(1)地址高端為地址高端為段號(hào)、低端為偏移；段

54、號(hào)、低端為偏移；(2)指令中顯式地給出段號(hào)和指令中顯式地給出段號(hào)和段內(nèi)偏移。段內(nèi)偏移。段表：系統(tǒng)為每一個(gè)進(jìn)程都建立了一個(gè)段表，它段表：系統(tǒng)為每一個(gè)進(jìn)程都建立了一個(gè)段表，它給出了進(jìn)程當(dāng)中的每一個(gè)段與它所對(duì)應(yīng)的內(nèi)存分給出了進(jìn)程當(dāng)中的每一個(gè)段與它所對(duì)應(yīng)的內(nèi)存分區(qū)之間的映射關(guān)系。區(qū)之間的映射關(guān)系。7575所對(duì)應(yīng)內(nèi)存分區(qū)的起始地址所對(duì)應(yīng)內(nèi)存分區(qū)的起始地址段長度段長度1400100063004004300400段號(hào)段號(hào)012段表段表比較頁比較頁表表7676段表的具體實(shí)現(xiàn)：段表的具體實(shí)現(xiàn)：段表保存在內(nèi)存當(dāng)中；段表保存在內(nèi)存當(dāng)中；設(shè)置一個(gè)設(shè)置一個(gè)段表基地址寄存器段表基地址寄存器（Segment-table b

55、ase register，STBR），用來指向內(nèi)），用來指向內(nèi)存當(dāng)中段表的起始地址；存當(dāng)中段表的起始地址；設(shè)置一個(gè)設(shè)置一個(gè)段表長度寄存器段表長度寄存器（Segment-table length register，STLR），用來指示段表的），用來指示段表的大小，即程序當(dāng)中的段的個(gè)數(shù)；大小，即程序當(dāng)中的段的個(gè)數(shù)；7777段式地址映射段式地址映射Base + dProgramSegmentationMain MemoryVirtual AddressRegisterSegment TableSegmentdS#Length BaseSeg Table PtrSeg #Offset = dSegme

56、nt Table+Physical Address與頁式地址映射的區(qū)別？與頁式地址映射的區(qū)別？7878段式地址映射舉例段式地址映射舉例段表起始地址段表地址寄存器虛擬地址11C4段號(hào)段內(nèi)地址段表段號(hào)始址015001340035C4內(nèi)存7979X 邏輯地址邏輯地址32位：位：16位段號(hào)位段號(hào)16位段內(nèi)偏移位段內(nèi)偏移;X 整數(shù)為整數(shù)為32位；位；X 地址以地址以16進(jìn)制描述。進(jìn)制描述。段式存儲(chǔ)管理舉例段式存儲(chǔ)管理舉例16位位16位位段號(hào)段號(hào)段內(nèi)偏移段內(nèi)偏移8080段段基地址基地址長度長度保護(hù)保護(hù)01000018C0只讀只讀1119003FF只讀只讀211D001FF讀寫讀寫300禁止訪問禁止訪問41

57、1F001000讀寫讀寫500禁止訪問禁止訪問600禁止訪問禁止訪問713000FFF讀寫讀寫mainSin240push X 10108360mov 4(sp), r2244call Sin364push r2248366488ret段表段表代碼代碼段段81818282X X在哪？（在哪？（Sin函數(shù)的參數(shù)）函數(shù)的參數(shù)）X 棧指針的當(dāng)前地址是棧指針的當(dāng)前地址是70FF0，物理地址是多少？，物理地址是多少？X 第一條指令在哪？第一條指令在哪？X Push X指令：將指令：將SP減減4，然后存儲(chǔ)，然后存儲(chǔ)X的值，那么的值，那么X被存儲(chǔ)在什么地方？被存儲(chǔ)在什么地方？X Call Sin指令：指令：

58、(1)當(dāng)前當(dāng)前PC值入棧；值入棧；(2)在在PC內(nèi)裝入內(nèi)裝入目標(biāo)目標(biāo)PC值。哪個(gè)值被壓入棧了？新的棧指針的值值。哪個(gè)值被壓入棧了？新的棧指針的值是多少？新的是多少？新的PC值是多少？值是多少？X “mov 4+(sp), r2”的功能是什么？的功能是什么？83833. 優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)優(yōu)點(diǎn)：優(yōu)點(diǎn)： 程序通過分段來劃分多個(gè)模塊，每個(gè)模程序通過分段來劃分多個(gè)模塊，每個(gè)模塊可以分別編寫和編譯，可以針對(duì)不同塊可以分別編寫和編譯，可以針對(duì)不同類型的段采取不同的保護(hù)，可以按段為類型的段采取不同的保護(hù)，可以按段為單位來進(jìn)行共享；單位來進(jìn)行共享； 一個(gè)程序不必連續(xù)存放，沒有內(nèi)碎片。一個(gè)程序不必連續(xù)存放，沒有內(nèi)碎片

59、。缺點(diǎn)：缺點(diǎn)：程序必須全部裝入內(nèi)存、外碎片等。程序必須全部裝入內(nèi)存、外碎片等。848485854.3.3 頁式管理與段式管理的比較頁式管理與段式管理的比較分頁與分段的出發(fā)點(diǎn)不同分頁與分段的出發(fā)點(diǎn)不同F(xiàn)頁式：為減少碎片，提高內(nèi)存的使用效率，頁式：為減少碎片，提高內(nèi)存的使用效率，因此把內(nèi)存劃分為許多個(gè)固定大小的物理頁因此把內(nèi)存劃分為許多個(gè)固定大小的物理頁面。相應(yīng)的，把邏輯地址空間也劃分為大小面。相應(yīng)的，把邏輯地址空間也劃分為大小相同的邏輯頁面；相同的邏輯頁面；F段式：為了實(shí)現(xiàn)程序當(dāng)中的各個(gè)邏輯單元的段式：為了實(shí)現(xiàn)程序當(dāng)中的各個(gè)邏輯單元的獨(dú)立性，便于它們的共享、保護(hù)和修改，從獨(dú)立性，便于它們的共享、

60、保護(hù)和修改，從而為每一個(gè)邏輯單元設(shè)立一個(gè)單獨(dú)的而為每一個(gè)邏輯單元設(shè)立一個(gè)單獨(dú)的“段段”。相應(yīng)的，在物理內(nèi)存的分配和回收上，采。相應(yīng)的，在物理內(nèi)存的分配和回收上，采用可變分區(qū)的存儲(chǔ)管理方法。用可變分區(qū)的存儲(chǔ)管理方法。8686程序員對(duì)所采用的存儲(chǔ)管理技術(shù)的關(guān)注：程序員對(duì)所采用的存儲(chǔ)管理技術(shù)的關(guān)注：F頁式：對(duì)于程序員而言，頁式存儲(chǔ)管理完全頁式：對(duì)于程序員而言，頁式存儲(chǔ)管理完全是透明的，不必關(guān)心。對(duì)邏輯地址空間的分是透明的，不必關(guān)心。對(duì)邏輯地址空間的分頁，是由系統(tǒng)自動(dòng)完成的。頁，是由系統(tǒng)自動(dòng)完成的。程序員甚至不知程序員甚至不知道分頁的發(fā)生道分頁的發(fā)生。F段式：程序員知道各個(gè)邏輯單元的存在，因段式：程序