ch4-4.3分頁式存儲(chǔ)管理

1、第四章 存儲(chǔ)管理,4.3 分頁式存儲(chǔ)管理,4.3.1 分頁式存儲(chǔ)管理的基本原理 4.3.2 快表 4.3.3 分頁式存儲(chǔ)空間的分配和去配 4.3.4 分頁式存儲(chǔ)空間的頁面共享和保護(hù) 4.3.5 多級(jí)頁表 4.3.6 反置頁表,思想： 將進(jìn)程劃分成較小的單位，這些單位可以分散的駐留在內(nèi)存的“碎片”中，可以解決作業(yè)連續(xù)存儲(chǔ)時(shí)，各空閑分區(qū)較小，大作業(yè)不能裝入的問題。 進(jìn)程在內(nèi)存中不一定連續(xù)分配，但需一次全部裝入。,4.3.1 分頁式存儲(chǔ)管理基本原理,分頁存儲(chǔ)管理涉及的基本概念： 頁面：是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的區(qū)，稱為頁面或頁，并為各頁加以編號(hào)，從0開始。 頁框（頁幀）：把主存空

2、間分成與頁面相同大小的若干個(gè)存儲(chǔ)區(qū)，稱為物理塊或頁框， 也同樣從0開始依次編號(hào)。,4.3.1 分頁式存儲(chǔ)管理基本原理,內(nèi)存分配 在為進(jìn)程分配內(nèi)存時(shí)以塊為單位，將進(jìn)程中若干頁裝入到多個(gè)不相鄰的塊中，最后一頁常裝不滿一塊而出現(xiàn)頁內(nèi)碎片。,4.3.1 分頁式存儲(chǔ)管理基本原理,頁面大小 在分頁系統(tǒng)中的頁面大小應(yīng)適中。 頁面若太小，可使內(nèi)存碎片減小，提高內(nèi)存利用率，但也會(huì)使每個(gè)進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存； 此外，還會(huì)降低頁面換進(jìn)換出的效率。 如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進(jìn)換出的速度，但卻又會(huì)使頁內(nèi)碎片增大。 頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2

3、的冪，通常為512 B8 KB。,4.3.1 分頁式存儲(chǔ)管理基本原理,邏輯地址結(jié)構(gòu) 分頁存儲(chǔ)器的邏輯地址由兩部分構(gòu)成,4.3.1 分頁式存儲(chǔ)管理基本原理,地址長為32位，其中0-11位為頁內(nèi)地址，即每頁的大小為212=4KB； 12-31位為頁號(hào)，地址空間最多允許有220 =1M頁。,若給定一個(gè)邏輯地址空間中的地址為A，頁面的大小為L，則頁號(hào)P和頁內(nèi)地址d可按下式求得：,4.3.1 分頁式存儲(chǔ)管理基本原理,頁表 將頁號(hào)和頁內(nèi)地址轉(zhuǎn)換成內(nèi)存地址，必須要有一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來登記頁號(hào)和塊的對應(yīng)關(guān)系和有關(guān)信息，這樣的數(shù)據(jù)結(jié)構(gòu)稱為頁表。,4.3.1 分頁式存儲(chǔ)管理基本原理,頁號(hào) 塊號(hào),作業(yè)的地址空間,0

4、 1 2 3 4 5 6 78 9,內(nèi)存空間,頁表,記錄了頁面在內(nèi)存中對應(yīng)的塊號(hào) 頁表一般存放在內(nèi)存中 系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)頁表 頁表的基址及長度由頁表寄存器給出 訪問一個(gè)字節(jié)的數(shù)據(jù)/指令需訪問內(nèi)存2次(頁表一次,內(nèi)存一次)，所以出現(xiàn)內(nèi)存訪問速度降低的問題。,4.3.1 分頁式存儲(chǔ)管理基本原理,地址轉(zhuǎn)換 將用戶地址空間的邏輯地址變換為內(nèi)存空間中的物理地址 物理地址： 借助頁表將邏輯地址中的頁號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。 塊內(nèi)位移d=頁內(nèi)位移W,4.3.1 分頁式存儲(chǔ)管理基本原理,物理地址塊號(hào)B塊大小塊內(nèi)位移,頁表基址寄存器,4.3.1 分頁式存儲(chǔ)管理基本原理,4.3.2 快表,頁表放在內(nèi)存當(dāng)中

5、，所以，CPU每存取一個(gè)數(shù)據(jù)時(shí)需兩次訪問內(nèi)存： 訪問頁表 訪問存儲(chǔ)單元 為了提高速度，增加一個(gè)硬件關(guān)聯(lián)的存儲(chǔ)器，存放經(jīng)常使用的頁表表項(xiàng)。這個(gè)存儲(chǔ)器稱為快表（轉(zhuǎn)換后援緩沖TLB、聯(lián)想寄存器）。,4.3.2 快表,原理 邏輯地址的頁號(hào)，首先在快表中尋找，若找到(命中)就找出其對應(yīng)的物理塊；若未找到(未命中)，再到頁表中找其對應(yīng)的物理塊，同時(shí)將頁號(hào)和物理塊號(hào)登記到快表中。 若快表中內(nèi)容滿，則按某種算法淘汰某些頁。最簡單的策略是“先進(jìn)先出”，淘汰最先登記的頁。,具有快表的地址變換機(jī)構(gòu),假定訪問主存時(shí)間為100毫微秒，訪問快表時(shí)間為20毫微秒，快表為32個(gè)單元時(shí)命中率可達(dá)90%，按邏輯地址存取的平均時(shí)間

6、為： （10020）90%(100+100+20)(1-90%)130毫微秒 比兩次訪問主存的時(shí)間200毫微秒縮短了35%。,4.3.2 快表,4.3.3分頁式存儲(chǔ)空間的分配和去配,主存物理塊表：整個(gè)系統(tǒng)有一個(gè)物理塊表，描述物理內(nèi)存空間的分配使用狀況。 數(shù)據(jù)結(jié)構(gòu)：位示圖和鏈表； 用它來記錄內(nèi)存中每個(gè)塊的使用情況和當(dāng)前空閑塊的總數(shù)。,4.3.3分頁式存儲(chǔ)空間的分配和去配,分配算法： 計(jì)算一個(gè)進(jìn)程所需要的總塊數(shù) 查主存物理塊表，看看是否還有N個(gè)空閑塊 分配N個(gè)空閑塊，將頁號(hào)和塊號(hào)填入頁表 從空閑塊數(shù)中減去本次占用的塊數(shù)N。 修改主存物理塊表 否則，進(jìn)程等待,4.3.3分頁式存儲(chǔ)空間的分配和去配,去配算法 當(dāng)一個(gè)進(jìn)程執(zhí)行完成并退出內(nèi)存時(shí)要撤銷進(jìn)程頁表，同時(shí)修改主存物理塊表。 它的過程是：查找該進(jìn)程的進(jìn)程頁表，將其中的每一行取出，得到物理內(nèi)存的塊號(hào)，然后到主存物理塊表中去搜索，把所對應(yīng)的表項(xiàng)的值修改為空閑，以便后面可以繼續(xù)使用。,小結(jié),頁式存儲(chǔ)管理優(yōu)點(diǎn) 沒有外碎片，每個(gè)內(nèi)碎片不超過頁大小。 一個(gè)程序不必連續(xù)存放，便于改變程序占用空間的大?。ㄖ饕鸽S著程序運(yùn)行而動(dòng)態(tài)生成的數(shù)據(jù)增多，要求地址空間相應(yīng)增長，通常由系統(tǒng)調(diào)用完成而不是操作系統(tǒng)自動(dòng)完成）。,小結(jié),頁式存儲(chǔ)管理缺點(diǎn) 程序全部裝入內(nèi)存 各種表格要占用一定