CH4-4.1主存器和4.2連續(xù)存儲管理

1、操作系統(tǒng)教程(第4版)第四章 存儲管理高等教育出版社 2008年4月1笫四章 存儲管理4.1 存儲器 4.2 連續(xù)存儲空間管理 4.3 分頁式存儲管理 4.4 分段式存儲管理 4.5 虛擬存儲管理 4.6 Intel x86分段和分頁存儲結(jié)構(gòu)4.7 Linux虛擬存儲管理 4.8 Windows2003虛擬存儲管理 2存儲管理的功能分配和去配：進(jìn)程可請求對主存區(qū)的獨(dú)占式使用，主存區(qū)的請求和釋放（即分配和去配）操作由存儲器管理完成。抽象和映射：主存儲器被抽象，使得進(jìn)程認(rèn)為分配給它的地址空間是一個(gè)大且連續(xù)地址所組成的數(shù)組；同時(shí)建立抽象機(jī)制支持進(jìn)程用邏輯地址來映射到物理主存單元，實(shí)現(xiàn)地址的轉(zhuǎn)換。隔離

2、和共享：系統(tǒng)負(fù)責(zé)隔離已分配給進(jìn)程的主存區(qū)，互不干擾，確保進(jìn)程對存儲單元的獨(dú)占式使用，以實(shí)現(xiàn)存儲保護(hù)功能；系統(tǒng)允許多個(gè)進(jìn)程共享主存區(qū)。存儲擴(kuò)充：物理主存容量不應(yīng)限制應(yīng)用程序的大小在這種情況下，超越隔離機(jī)制并授權(quán)進(jìn)程允許共享訪問，達(dá)到既能提高主存利用率又能共享主存某區(qū)的目的34.1 存儲器4.1.1存儲器的層次 4.1.2地址轉(zhuǎn)換與存儲保護(hù) 44.1.1 存儲器的層次寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動存儲介質(zhì)存儲管理設(shè)備管理速度快5存儲器的層次結(jié)構(gòu)功能：儲存以二進(jìn)位形式表示的程序和數(shù)據(jù)分類：內(nèi)存儲器/外存儲器內(nèi)存儲器外存儲器(簡稱外存或輔存)存取速度很快較慢存儲容量較小(因單位成本較高)

3、 很大(因單位成本較低) 性質(zhì)斷電后信息消失斷電后信息保持用途存放已經(jīng)啟動運(yùn)行的程序和需要立即處理的數(shù)據(jù)長期存放計(jì)算機(jī)系統(tǒng)中幾乎所有的信息與CPU關(guān)系CPU所處理的指令及數(shù)據(jù)直接從內(nèi)存中取出程序及相關(guān)數(shù)據(jù)必須先送入內(nèi)存后才能被CPU使用64.1.2 地址轉(zhuǎn)換與存儲保護(hù)(1)在多道程序環(huán)境下，程序要運(yùn)行必須為之創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程的第一件事，就是要將程序和數(shù)據(jù)裝入內(nèi)存。如何將一個(gè)用戶源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過以下幾步 :（1）編譯：由編譯程序（Compiler）將用戶源代碼編譯成若干個(gè)目標(biāo)模塊（Object Module）；（2）鏈接：由鏈接程序（Linker）將編譯后形成的

4、目標(biāo)模塊以及它們所需要的庫函數(shù)，鏈接在一起，形成一個(gè)裝入模塊（Load Module）；（3）裝入：由裝入程序（Loader）將裝入模塊裝入內(nèi)存。7程序的編譯、鏈接、裝入和執(zhí)行 鏈接動態(tài)重定位靜態(tài)重定位源程序模塊1源程序模塊2源程序模塊n目標(biāo)代碼1目標(biāo)代碼2目標(biāo)代碼n可重定位目標(biāo)代碼(裝載代碼)(輔存)編譯裝入執(zhí)行程序名字空間邏輯地址空間物理地址空間可執(zhí)行二進(jìn)制代碼(主存)庫代碼可執(zhí)行二進(jìn)制代碼(主存) 源程序中的符號名集合所限定的空間81)靜態(tài)鏈接：在裝入內(nèi)存前鏈接成一個(gè)大的裝入模塊module。但需要解決兩個(gè)問題，即： (1) 修改相對地址。 (2) 變換外部調(diào)用符號。2)裝入時(shí)動態(tài)鏈接：

5、邊裝入邊鏈接，即裝入一個(gè)模塊時(shí)，便去找它的調(diào)用模塊，如有便再裝入，同時(shí)修改目標(biāo)模塊中的相對地址。由于分開裝入：便于模塊更新修改；便于模塊的共享。3)運(yùn)行時(shí)動態(tài)鏈接:將對某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存或被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。程序的鏈接 程序鏈接示意圖 92. 程序的裝入絕對裝入方式可重定位裝入方式（靜態(tài)重定位）動態(tài)運(yùn)行時(shí)裝入方式（動態(tài)重定位）重要的術(shù)語： 邏輯地址，是目標(biāo)程序中的地址。這種地址一般以0為基地址，順序編址。一個(gè)作業(yè)或進(jìn)程的目標(biāo)程序（準(zhǔn)確地說應(yīng)是裝入模塊）的邏輯地址的集合稱

6、為該作業(yè)或進(jìn)程的邏輯地址空間，或稱地址空間或虛擬空間。邏輯地址也稱相對地址或虛擬地址。 物理地址，是物理存貯器的單元地址。物理地址的集合稱為物理地址空間，或稱存儲空間或?qū)嵉刂房臻g。物理地址也稱絕對地址或?qū)嵉刂贰?重定位（或地址轉(zhuǎn)換）：把裝入模塊中指令的邏輯地址以及數(shù)據(jù)的邏輯地址變換成內(nèi)存中物理地址的過程稱為重定位。101）絕對裝入：只能將目標(biāo)模塊裝入指定的內(nèi)存位置 缺點(diǎn)：（1）在程序中必須由程序員給出絕對地址?；蛘哒f此時(shí)的相對地址和絕對地址一樣；（2）要求程序員對內(nèi)存使用情況非常熟悉。事先知道自己的程序?qū)⒁b在什么地方；（3）只適合于單道程序環(huán)境。例如：某個(gè)程序員想在內(nèi)存200處編一個(gè)程序：M

7、ov ax,20435h200204Mov ax,20435h裝入程序邏輯地址相對地址內(nèi)存中進(jìn)程絕對地址物理地址.2002040112）可重定位的裝入：裝入時(shí)將邏輯地址轉(zhuǎn)換為物理地址(重定位)，邏輯地址從0開始。適合于多道程序環(huán)境。地址變換在裝入時(shí)一次性完成，以后不變，可看作是靜態(tài)重定位。Mov ax,25003650100025005000例如:準(zhǔn)備將程序裝入內(nèi)存10000處1000015000Mov ax,25003651100012500Mov ax,12500365注意：這種裝入后程序不便在內(nèi)存中移動。Why?123）動態(tài)運(yùn)行時(shí)裝入：模塊裝入內(nèi)存后沒有立即重定位，仍然是相對地址；只有當(dāng)

8、CPU執(zhí)行到具有相對地址的代碼時(shí)才去重定位，因此是動態(tài)重定位。Mov ax,2500365010002500500010000150001100012500Mov ax,25003652500相對地址10000重定位寄存器這種裝入后程序可以內(nèi)存中移動，但需要重定位寄存器的硬件支持。12500物理地址13 地址轉(zhuǎn)換與存儲保護(hù)(2)存儲保護(hù)（涉及防止地址越界和控制正確存取。）通常進(jìn)程運(yùn)行時(shí)所產(chǎn)生的所有主存訪問地址都應(yīng)進(jìn)行檢查，確保進(jìn)程僅訪問自己的主存區(qū)，這就是地址越界保護(hù)。依賴硬件，常用有有界地址和存儲鍵。進(jìn)程在訪問分配給自己的主存區(qū)時(shí)，要對訪問權(quán)限（如允許讀、寫、執(zhí)行等）進(jìn)行檢查。144.2 連

9、續(xù)存儲空間管理4.2.1 固定分區(qū)存儲管理 4.2.2 可變分區(qū)存儲管理 4.2.3 伙伴系統(tǒng)4.2.4 主存不足的存儲管理技術(shù)154.2.2 固定分區(qū)存儲管理固定分區(qū)存儲管理的基本思想：主存空間被劃分成數(shù)目固定不變的分區(qū)，各分區(qū)的大小不等，每個(gè)分區(qū)只裝入一個(gè)作業(yè)。若多個(gè)分區(qū)中都裝有作業(yè)，則它們可以并發(fā)執(zhí)行。系統(tǒng)一啟動后就已經(jīng)分好了分區(qū)。（支持多道程序設(shè)計(jì)的最簡單的管理技術(shù)）固定分區(qū)存儲管理的數(shù)據(jù)結(jié)構(gòu)：主存分配表，記錄主存儲器中劃分的分區(qū)及其使用情況。164.2.2 固定分區(qū)存儲管理作業(yè)進(jìn)入固定分區(qū)排隊(duì)策略（2種)：一種是每個(gè)分區(qū)有單獨(dú)的作業(yè)等待隊(duì)列，調(diào)度程序選中作業(yè)后，創(chuàng)建用戶進(jìn)程并將其排入

10、一個(gè)能夠裝入它的最小分區(qū)的進(jìn)程等待隊(duì)列尾部，當(dāng)此分區(qū)空閑時(shí)，就裝入隊(duì)首進(jìn)程執(zhí)行。另一種是所有等待處理的作業(yè)排成一個(gè)等待隊(duì)列，每當(dāng)有分區(qū)空閑時(shí)，就從隊(duì)首起依次搜索分區(qū)長度能容納的作業(yè)以便裝入執(zhí)行，為了防止小作業(yè)占用大分區(qū)，也可以搜索分區(qū)長度所能容納的最大作業(yè)裝入執(zhí)行。17固定分區(qū)存儲管理的地址轉(zhuǎn)換和存儲保護(hù)B下限寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)用戶分區(qū)1用戶分區(qū)2用戶分區(qū)3B+L2上限寄存器B+L2越界中斷用戶分區(qū)4用戶分區(qū)5用戶分區(qū)618固定分區(qū)分配 如何分配 （a）分區(qū)使用表：表中包含每個(gè)分區(qū)的起始地址、大小、狀態(tài)。 （b）分配方法：在分區(qū)使用表中找出一個(gè)能滿足要求的、尚未分配的分區(qū)。

11、將該分區(qū)分給程序、并修改分區(qū)使用表點(diǎn)擊鼠標(biāo)：對1k、9k、33k、121k作業(yè)分配內(nèi)存，并修改分區(qū)狀態(tài)浪費(fèi)（陰影部分）：7k23k87k211k總浪費(fèi)：328k操作系統(tǒng)0K20K28K60K180K512k-1分區(qū)1分區(qū)2分區(qū)3分區(qū)4內(nèi)存分區(qū)情況分區(qū)號起始地址大小狀態(tài)1未分配2未分配3未分配4未分配180k20k8k例題：某系統(tǒng)采用固定分區(qū)管理方式，內(nèi)存分區(qū)如圖?，F(xiàn)有大小為1k、9k、33k、121k要求進(jìn)入內(nèi)存，畫出他們進(jìn)入內(nèi)存的空間分配情況，說明主存浪費(fèi)多大。28k60k32k120k332k分區(qū)使用表1k9k33k121k已分配已分配已分配已分配194.2.2 可變分區(qū)存儲管理 可變分區(qū)

12、 存儲管理是按作業(yè)的實(shí)際大小來劃分分區(qū)，且分區(qū)個(gè)數(shù)也是隨機(jī)的,實(shí)現(xiàn)多個(gè)作業(yè)對主存的共享，進(jìn)一步提高主存資源利用率。系統(tǒng)剛啟動時(shí)并不分區(qū)。系統(tǒng)把作業(yè)裝入主存時(shí)，根據(jù)其所需要的主存容量查看是否有足夠的空間，如有，則按需要分割一個(gè)分區(qū)分配給此作業(yè)；若無，則令此作業(yè)等待主存資源。20可變分區(qū)存儲管理數(shù)據(jù)結(jié)構(gòu)用來描述空閑分區(qū)和已分配分區(qū)的情況。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：空閑分區(qū)鏈：以鏈表形式記錄每個(gè)空閑分區(qū)的情況?？臻e分區(qū)表：以表結(jié)構(gòu)形式記錄每個(gè)空閑分區(qū)的情況。21可變分區(qū)回收算法 回收內(nèi)存： 當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首地址，從空閑分區(qū)表（鏈）中找到相應(yīng)的插入點(diǎn)，將回收區(qū)插入到空閑

13、分區(qū)表（鏈）中的適當(dāng)位置。 此時(shí)，可能出現(xiàn)以下四種情況之一： 1. 回收區(qū)前連空閑區(qū) 2. 回收區(qū)后連空閑區(qū) 3. 回收區(qū)前、后連空閑區(qū) 4. 回收區(qū)前、后都不連空閑區(qū) A X B A B A X A X B B x 變?yōu)樽優(yōu)樽優(yōu)樽優(yōu)閄終止前X終止后黑色區(qū)域?yàn)榭臻e區(qū)，X作業(yè)撤離22鏈表空閑區(qū)管理方法空閑區(qū)開頭單元存放本空閑區(qū)長度及下個(gè)空閑區(qū)起始地址,把所有空閑區(qū)都鏈接起來,設(shè)置第一塊空閑區(qū)地址指針,讓它指向第一塊空閑區(qū)地址。申請空閑區(qū);歸還空閑區(qū)。23可變分區(qū)管理分配算法1）最先適應(yīng)分配算法 2）下次適應(yīng)分配算法3) 最優(yōu)適應(yīng)分配算法 4）最壞適應(yīng)分配算法5) 快速適應(yīng)分配算法 24（1）最先

14、適應(yīng)算法： 從空閑分區(qū)表或分區(qū)鏈（按照地址遞增次序排列）頭上開始查找，找到第一個(gè)滿足要求的分區(qū)為止，分配內(nèi)存，余下的部分然仍留在空閑分區(qū)表中。 優(yōu)點(diǎn)：傾向于優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū)；保留了高地址部分的空閑分區(qū)。 缺點(diǎn)：低地址部分不斷被劃分，留下很多碎片.（2）下次適應(yīng)算法 總是從未分配區(qū)的上次掃描結(jié)束處順序查找未分配區(qū)表或鏈表，直至找到第一個(gè)能滿足要求的空閑去為止。 例題：25例題：已知主存有256k容量，其中os占地端內(nèi)存20k，有下列作業(yè)序列：分析內(nèi)存分配情況和空閑分區(qū)表情況 作業(yè)1 要求 80k；作業(yè)2 要求 16k；作業(yè)3 要求 140k 作業(yè)1完成；作業(yè)3完成； 作業(yè)4 要求

15、60k；作業(yè)5 要求 120k操作系統(tǒng)0k20k256k-1空閑分區(qū)表分區(qū)號起始地址大小120k236k作業(yè)1來到操作系統(tǒng)0k20k256k-1空閑分區(qū)表分區(qū)號起始地址大小1100k156k作業(yè)1100k剛開始時(shí)26作業(yè)2 16k作業(yè)3 140k分別來到后空閑分區(qū)表分區(qū)號起始地址大小1100k156k操作系統(tǒng)0k20k256k-1作業(yè)1100k作業(yè)2作業(yè)3116k1116k140k0作業(yè)1 完成作業(yè)3 完成操作系統(tǒng)0k20k256k-1作業(yè)1100k作業(yè)2作業(yè)3116k空閑分區(qū)表分區(qū)號起始地址大小120k80k2116k140k作業(yè)4 60k作業(yè)5 120k（12k?)分別來到180k20k作

16、業(yè)4作業(yè)51236k20kback27（3）最佳適應(yīng)算法： 每次為作業(yè)分配內(nèi)存時(shí)，總是找一個(gè)既能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。 特點(diǎn)：為提高程序中查找速度，常常將分配表按照分區(qū)容量按照從小到大排列，查找時(shí)只需要從表首按順序查找最合適的。 缺點(diǎn)：都在找最合適的分割，常會剩下一些小碎片 例題：28例題：已知內(nèi)存分配情況如下圖。要求填寫空閑分區(qū)表，并分配如下作業(yè)序列 作業(yè)4 大小2k，作業(yè)5 大小6k， 作業(yè)6 大小2k操作系統(tǒng)作業(yè)10k20k256k-110k25k作業(yè)23k35k45k作業(yè)3156k48k100k分區(qū)號起始地址大小空閑分區(qū)表125k10k245k3k3100k156k作

17、業(yè)4247k1k作業(yè)5131k4k作業(yè)6133k2k改進(jìn)：空閑分區(qū)表（按大小排列，便于程序）分區(qū)號起始地址大小225k10k3100k156k145k3k29（4）最壞適應(yīng)算法 每次分配總是挑選出分配表（鏈）中最大的分區(qū)進(jìn)行分配（5）快速適應(yīng)算法 又稱為分類搜索算法，將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表。 30可變分區(qū)地址轉(zhuǎn)換與存儲保護(hù) 基址基址寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)空閑分區(qū)1用戶作業(yè)1空閑分區(qū)2限長限長寄存器限長越界中斷31多對基址/限長寄存器 進(jìn)程B虛CPU進(jìn)程A虛CPU物理主存進(jìn)程A私有空間進(jìn)程B私有空間共享區(qū)重

18、定位寄存器1限長寄存器1重定位寄存器2限長寄存器2重定位寄存器1限長寄存器1重定位寄存器2限長寄存器2 多對重定位寄存器支持主存共享324.2.3 伙伴系統(tǒng)(1)伙伴原理任何尺寸為2i的空閑塊都可被分為來那個(gè)尺寸為2i-1的空閑塊，這兩個(gè)空閑塊稱作伙伴?；锇橥ㄟ^對大塊的物理主存劃分而獲得假如從第0個(gè)頁面開始到第3個(gè)頁面結(jié)束的主存每次都對半劃分，那么第一次劃分獲得大小為2頁的伙伴，如0、1和2、3進(jìn)一步劃分，可以獲得大小為1頁的伙伴，例如0和1，2和30123012333 伙伴系統(tǒng)(2) 1伙伴系統(tǒng)原理 128k 256k 384k 512k 640k 768k 896k 1M A 128 25

19、6 512 AB64 256 512 AB64 C 128 512 128B64 C 128 512 128BD C 128 512 12864D C 128 512 256 C 128 512 1024342 Linux伙伴系統(tǒng)1) 以page結(jié)構(gòu)為數(shù)組元素的mem_map 數(shù)組2) 以free_area_struct結(jié)構(gòu)為數(shù)組元素的free_area數(shù)組3) 位圖數(shù)組(bitmap) 353 Linux基于伙伴的slab分配器(1)為什么要使用slab分配器?slab的結(jié)構(gòu)slab的操作 Slab舉例36為什么要使用slab分配器?內(nèi)核需要的主存量遠(yuǎn)遠(yuǎn)小于頁框大小，如inode、vma、t

20、ask_struct等，為了更經(jīng)濟(jì)地使用內(nèi)核主存資源，引入基于伙伴系統(tǒng)的slab分配器，基本思想：為經(jīng)常使用的小對象建立緩存，小對象的申請與釋放都通過slab分配器來管理，僅當(dāng)緩存不夠用時(shí)才向伙伴系統(tǒng)申請更多空間。 37Linux基于伙伴的slab分配器(2) cacheslabslabslabslabslabslabslabcachecacheslabslab滿slab半滿slab空slabslab分配器組成存pcb存inode存vma38例子task_struct slab內(nèi)核用全局變量存放指向task_struct slab的指針：kmem_struct_t *task_struct_c

21、achep;初始化時(shí)，在fork_init( )中調(diào)用kmem_cache_create( )函數(shù)創(chuàng)建高速緩存，存放類型為task_struct的對象。每當(dāng)進(jìn)程調(diào)用fork( )時(shí)，調(diào)用內(nèi)核函數(shù)do_fork( )，它再使用kmem_cache_alloc( )函數(shù)在對應(yīng)slab中建立一個(gè)task_struct對象。進(jìn)程執(zhí)行結(jié)束后，task_struct對象被釋放，返還給task_struct_cachep slab。39slab分配器主要操作 1）kmem_cache_create（）函數(shù)：創(chuàng)建專用cache，規(guī)定對象的大小和slab的構(gòu)成，并加入cache管理隊(duì)列；2）kmem_cache_alloc（）與kmem_cache_free（）函數(shù)：分別用于分配和釋放一個(gè)擁有專用slab隊(duì)列的對象；3）kmem_cache_grow（）與kmem_cache_reap（）函數(shù)：kmem_cache_grow（）它向伙伴系統(tǒng)申請向cache增加一個(gè)slab；kmem_cache_reap（）用于定時(shí)回收空閑slab；4)kmem_cache_destroy( )與kmem_cache_shrink( )：用于cache的銷毀和收縮；5)kmalloc（）與kfree（）函數(shù)：用來從通用的緩沖區(qū)隊(duì)列中申請