存儲(chǔ)器管理課件

1、存儲(chǔ)器管理課件第四章 存儲(chǔ)器管理存儲(chǔ)器管理課件4.1 4.1 概述概述v存儲(chǔ)體系存儲(chǔ)體系存儲(chǔ)層次結(jié)構(gòu)存儲(chǔ)層次結(jié)構(gòu) 依據(jù)訪問(wèn)速度的匹配關(guān)系、容量要求和價(jià)格，在存儲(chǔ)技術(shù)和CPU尋址技術(shù)許可的范圍內(nèi)組織合理的存儲(chǔ)結(jié)構(gòu)。容容量量增增大大，單單價(jià)價(jià)下下降降 訪訪問(wèn)問(wèn)速速度度加加快快 存儲(chǔ)器管理課件v存儲(chǔ)管理的任務(wù)存儲(chǔ)管理的任務(wù) 存儲(chǔ)分配和回收存儲(chǔ)分配和回收 地址變換地址變換( (地址重定位地址重定位) ) 存儲(chǔ)共享和保護(hù)存儲(chǔ)共享和保護(hù) 存儲(chǔ)器擴(kuò)充存儲(chǔ)器擴(kuò)充存儲(chǔ)器管理課件v 相關(guān)概念相關(guān)概念 邏輯地址邏輯地址： 物理地址物理地址： 地址空間地址空間： 存儲(chǔ)空間存儲(chǔ)空間： 地址重定位地址重定位： 目標(biāo)代碼的

2、相對(duì)編址目標(biāo)代碼的絕對(duì)編址目標(biāo)代碼用邏輯地址編址所限定的區(qū)域內(nèi)存若干存儲(chǔ)單元用物理地址編址所限定的區(qū)域當(dāng)程序被裝入內(nèi)存時(shí)，程序的邏輯地址被轉(zhuǎn)換成內(nèi)存的物理地址的過(guò)程存儲(chǔ)器管理課件 重定位的方式重定位的方式靜態(tài)重定位：目標(biāo)代碼裝入內(nèi)存時(shí)，一次性進(jìn)行 地址轉(zhuǎn)換。動(dòng)態(tài)重定位：目標(biāo)代碼裝入內(nèi)存時(shí)，先不進(jìn)行地 址轉(zhuǎn)換（即原代碼裝入），在執(zhí)行 時(shí)，再實(shí)施地址轉(zhuǎn)換。存儲(chǔ)器管理課件 地址重定位過(guò)程地址重定位過(guò)程例：0 0地址空間地址空間100025005000LOAD 1, 2500365存儲(chǔ)空間存儲(chǔ)空間1000011000LOAD 1, 25001250015000365+1 0 0 0 0重定位寄存器重定

3、位寄存器存儲(chǔ)器管理課件4.2 程序的裝入和鏈接程序的裝入和鏈接1）源程序轉(zhuǎn)換成可執(zhí)行程序過(guò)程）源程序轉(zhuǎn)換成可執(zhí)行程序過(guò)程 編譯編譯 鏈接鏈接 裝入裝入 庫(kù)函數(shù) 模塊 模塊 模塊 編 譯 程序 產(chǎn) 生的 目 標(biāo)模塊 鏈接程序 裝入模塊 裝入程序 內(nèi)存 第一步 第二步 第三步 存儲(chǔ)器管理課件2）程序的鏈接與裝入）程序的鏈接與裝入l程序的鏈接程序的鏈接（模塊拼接）靜態(tài)鏈接：裝入前先鏈接動(dòng)態(tài)鏈接：裝入時(shí)（或執(zhí)行時(shí)）才進(jìn)行鏈接l程序的裝入程序的裝入絕對(duì)裝入：目標(biāo)代碼與裝入位置地址相一致靜態(tài)重定位裝入：裝入時(shí)實(shí)現(xiàn)地址轉(zhuǎn)換動(dòng)態(tài)重定位裝入：待執(zhí)行時(shí)再進(jìn)行地址轉(zhuǎn)換 分配方式：連續(xù)分配或者離散分配分配方式：連續(xù)分

4、配或者離散分配存儲(chǔ)器管理課件4.3 連續(xù)分配方式連續(xù)分配方式p 單一連續(xù)區(qū)分配單一連續(xù)區(qū)分配p 固定分區(qū)分配固定分區(qū)分配p 可變（動(dòng)態(tài)）分區(qū)分配可變（動(dòng)態(tài)）分區(qū)分配p 可重定位分區(qū)分配可重定位分區(qū)分配p 伙伴系統(tǒng)伙伴系統(tǒng)存儲(chǔ)器管理課件 1）單一連續(xù)分配）單一連續(xù)分配 只能用于單用戶、單任務(wù)單用戶、單任務(wù)的操作系統(tǒng)中。 系統(tǒng)區(qū)：系統(tǒng)區(qū)：僅提供給操作系統(tǒng)使用，OS通常駐留在 內(nèi)存的低址部分； 用戶區(qū)：用戶區(qū)：指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間提供給某 一用戶使用。內(nèi)存內(nèi)存O.S0max用戶區(qū)用戶區(qū)存儲(chǔ)器管理課件2）固定分區(qū)分配）固定分區(qū)分配 算法思想算法思想內(nèi)存可用區(qū)劃分成若干個(gè)大小固定大小固定的分區(qū)，

5、這些分區(qū)大小可以相同也可不同大小可以相同也可不同，每個(gè)分區(qū)每個(gè)分區(qū)分別裝入一道作業(yè)一道作業(yè)的代碼（數(shù)據(jù)）。 算法實(shí)現(xiàn)算法實(shí)現(xiàn)建立一個(gè)分區(qū)說(shuō)明表分區(qū)說(shuō)明表來(lái)登記和管理整個(gè)內(nèi)存。在這個(gè)表中登記了每一個(gè)分區(qū)分區(qū)的大小，起始地大小，起始地址址和分配狀態(tài)分配狀態(tài)。存儲(chǔ)器管理課件分區(qū)說(shuō)明表已分配260K200KB4已分配120K40KB2未分配160K100KB3已分配100K20KB1分配狀態(tài)分配狀態(tài)起始地址起始地址大小大小分區(qū)號(hào)分區(qū)號(hào)操作系統(tǒng)1：作業(yè)A2：作業(yè)B34：作業(yè)C0100K120K160K260K460K例：例：分配：查分區(qū)說(shuō)明表，找到一個(gè)足夠大的空閑分區(qū)分配之回收：將回收分區(qū)對(duì)應(yīng)的分區(qū)說(shuō)明

6、 表狀態(tài)改為“空閑”。存儲(chǔ)器管理課件特點(diǎn)特點(diǎn)與單一連續(xù)分配相比，內(nèi)存利用率提高，內(nèi)存可同時(shí)裝入多道作業(yè)代碼，算法實(shí)現(xiàn)簡(jiǎn)單；分區(qū)一次性全部分配出去存在浪費(fèi)，產(chǎn)生內(nèi)碎片（分區(qū)內(nèi)不能被利用的小空間）。內(nèi)碎片（分區(qū)內(nèi)不能被利用的小空間）。存儲(chǔ)器管理課件3）可變分區(qū)分配）可變分區(qū)分配 算法思想算法思想按需分配：按需分配：每次從空閑分區(qū)中按作業(yè)大小分配一塊給該作業(yè)，然后將剩下的部分再作為空表塊留在空閑分區(qū)中。(分區(qū)的大小和個(gè)數(shù)不固定)算法實(shí)現(xiàn)算法實(shí)現(xiàn)建立相關(guān)空閑分區(qū)表，用來(lái)記錄每個(gè)空閑分區(qū)的大小、起始地址?？臻e分區(qū)的管理常采用鏈表形式。存儲(chǔ)器管理課件分區(qū)分配算法：分區(qū)分配算法：尋找某個(gè)空閑分區(qū)，其大小需大

7、于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個(gè)分區(qū)，其中一個(gè)分區(qū)分配給用戶，而另一個(gè)分區(qū)仍留在空閑分區(qū)鏈表中。p首次適應(yīng)算法首次適應(yīng)算法p循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法p最佳適應(yīng)算法最佳適應(yīng)算法p最差適應(yīng)算法最差適應(yīng)算法p快速適應(yīng)算法快速適應(yīng)算法存儲(chǔ)器管理課件n首次適應(yīng)算法首次適應(yīng)算法算法思想算法思想：將所有的空閑分區(qū)空閑分區(qū)按照地址遞增地址遞增的順序排列分配過(guò)程分配過(guò)程：每次分配時(shí)，從空閑分區(qū)鏈的鏈?zhǔn)祖準(zhǔn)组_(kāi)始查找， 找到符合要求的第一個(gè)分區(qū)，一分為二分配特點(diǎn)特點(diǎn)：較大的空閑分區(qū)可以被保留在內(nèi)存高地址空間； 但隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次 分配時(shí)從頭開(kāi)始查找，時(shí)間開(kāi)銷大

8、。存儲(chǔ)器管理課件n循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法算法思想算法思想：將所有的空閑分區(qū)按照地址遞增的順序排列，從上次分配的分區(qū)的下一個(gè)空閑分區(qū)起查找，找到符合要求的第一個(gè)分區(qū)分配過(guò)程分配過(guò)程：設(shè)置一個(gè)起始查找指針，指向上次分配的分區(qū)的下一個(gè)空閑分區(qū)，分配時(shí)總是從起始查找指針?biāo)赶虻谋眄?xiàng)開(kāi)始查找，找到第一個(gè)滿足要求的空閑區(qū)時(shí)，一分為二分配特點(diǎn)特點(diǎn)：該算法的分配和釋放的時(shí)間性能較好； 但較大的空閑分區(qū)不易保留。存儲(chǔ)器管理課件n最佳適應(yīng)算法最佳適應(yīng)算法算法思想算法思想：將空閑分區(qū)按容量遞增容量遞增順序排序，分配過(guò)程分配過(guò)程：每次分配時(shí)，從空閑分區(qū)鏈的鏈?zhǔn)祖準(zhǔn)组_(kāi)始查找， 找到符合要求的第一個(gè)分區(qū)，一分為

9、二分配特點(diǎn)特點(diǎn)：較大的空閑分區(qū)可以被保留； 但容易形成很多外碎片（分區(qū)之間不能被利用的空間）n 最壞適應(yīng)算法最壞適應(yīng)算法算法思想算法思想：將空閑分區(qū)按容量遞減順序排序分配過(guò)程分配過(guò)程：只需查找空閑區(qū)鏈最前面的空閑塊即可特點(diǎn)特點(diǎn)：分配的時(shí)候，只需查找一次，分配的算法很快； 但較大的空閑分區(qū)不被保留。存儲(chǔ)器管理課件 分區(qū)回收算法分區(qū)回收算法 如果釋放區(qū)與臨近的空閑區(qū)相連接，要將它們合并成較大的空閑區(qū)，否則空閑區(qū)將被分割得越來(lái)越小，最終導(dǎo)致不能利用。 上鄰接合并上鄰接合并 下鄰接合并下鄰接合并 上、下鄰接合并上、下鄰接合并 不鄰接處理不鄰接處理存儲(chǔ)器管理課件例：某系統(tǒng)內(nèi)存使用情況如下圖，若采用首次適

10、應(yīng)算例：某系統(tǒng)內(nèi)存使用情況如下圖，若采用首次適應(yīng)算法分配內(nèi)存，分別給出為某作業(yè)分配法分配內(nèi)存，分別給出為某作業(yè)分配50k空間和回收空間和回收作業(yè)作業(yè)4后的空閑分區(qū)鏈后的空閑分區(qū)鏈PL080k110k 50k350k 100k580k 60k080k110k160k300k350k450k500k580k640k80k50k100k60k作業(yè)作業(yè)3作業(yè)作業(yè)5作業(yè)作業(yè)9作業(yè)作業(yè)4作業(yè)作業(yè)7分配分配50k后后 回收作業(yè)回收作業(yè)4后后 PL50k30k110k50k350k 100k580k60kPL50k80k110k50k350k 150k580k60k初始時(shí)初始時(shí) 存儲(chǔ)器管理課件4 4）可重定位

11、分區(qū)分配）可重定位分區(qū)分配 算法思想算法思想 在可變分區(qū)分配算法的基礎(chǔ)上，采用動(dòng)態(tài)重定位方式裝入程序（數(shù)據(jù)）。當(dāng)無(wú)足夠大的分區(qū)供分配時(shí)，若總空閑存儲(chǔ)容量夠用，則將各分區(qū)中的內(nèi)容向內(nèi)存一端移動(dòng)（緊湊），使另一端形成一個(gè)大的空閑分區(qū)，然后再分配。算法流程（如下頁(yè)圖示）算法流程（如下頁(yè)圖示）存儲(chǔ)器管理課件與動(dòng)態(tài)分區(qū)分配算法基本相同，差別僅在于增加了緊湊功能。與動(dòng)態(tài)分區(qū)分配算法基本相同，差別僅在于增加了緊湊功能。請(qǐng)求分配請(qǐng)求分配u.size分區(qū)分區(qū)檢索空閑分區(qū)鏈檢索空閑分區(qū)鏈(表表)找到大于找到大于u.size的可用區(qū)？的可用區(qū)？按動(dòng)態(tài)分區(qū)方式按動(dòng)態(tài)分區(qū)方式進(jìn)行分配進(jìn)行分配修改有關(guān)的修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)

12、數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號(hào)返回分區(qū)號(hào)及首址及首址空閑分區(qū)總和空閑分區(qū)總和u.size?進(jìn)行緊湊形成連續(xù)進(jìn)行緊湊形成連續(xù)空閑區(qū)空閑區(qū)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)無(wú)法分配無(wú)法分配返回返回否否是是是是否否(圖圖4-10 動(dòng)態(tài)重定位分區(qū)分配算法流程圖動(dòng)態(tài)重定位分區(qū)分配算法流程圖)存儲(chǔ)器管理課件例：例：前例若要為作業(yè)10分配120k的存儲(chǔ)空間，因無(wú)足夠大分區(qū)（總空閑容量290k），則先進(jìn)行合并處理。030k170k220k270k350k640k作業(yè)作業(yè)3作業(yè)作業(yè)5作業(yè)作業(yè)9作業(yè)作業(yè)4作業(yè)作業(yè)7290k合并后空閑分區(qū)鏈為：合并后空閑分區(qū)鏈為：350k290k PL此時(shí)，就可以為作業(yè)此時(shí)，就可以為作業(yè)10分配

13、空間分配空間存儲(chǔ)器管理課件 算法實(shí)現(xiàn)算法實(shí)現(xiàn)為每個(gè)作業(yè)（分區(qū)）分配一個(gè)重定位寄存器重定位寄存器，用以存放對(duì)應(yīng)分區(qū)首地址分區(qū)首地址，以便實(shí)現(xiàn)動(dòng)態(tài)地址轉(zhuǎn)換；移動(dòng)后，只需修改重定位寄存器的值為新地址即可 優(yōu)、缺點(diǎn)優(yōu)、缺點(diǎn) 可實(shí)現(xiàn)動(dòng)態(tài)（可變）分區(qū)分配，又適時(shí)解決碎片問(wèn)題但移動(dòng)內(nèi)存需增加系統(tǒng)開(kāi)銷，增加輔助空間存儲(chǔ)器管理課件 5）伙伴系統(tǒng)）伙伴系統(tǒng)算法思想算法思想：將所有的空閑分區(qū)按照容量大小進(jìn)行分類，而且分區(qū)大小均為2的K次冪，對(duì)每一類具有相同大小的所有空閑分區(qū)均設(shè)立一個(gè)空閑分區(qū)雙向鏈表。分配過(guò)程分配過(guò)程：根據(jù)進(jìn)程長(zhǎng)度n找到能容納它的最小空閑區(qū)鏈表，取下第一個(gè)分區(qū)進(jìn)行分配。如果該分區(qū)容量比所需的要大，就

14、將其進(jìn)行平均分割，其中一個(gè)分區(qū)用于分配，另一個(gè)分區(qū)加入對(duì)應(yīng)大小的空閑分區(qū)鏈中。如果分割后的分區(qū)仍比所需分區(qū)大的話，按前敘方法繼續(xù)分割，直到滿足要求為止。特點(diǎn)特點(diǎn)：其分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間。存儲(chǔ)器管理課件4.4 基本分頁(yè)存儲(chǔ)管理方式基本分頁(yè)存儲(chǔ)管理方式1）算法思想和算法實(shí)現(xiàn)算法思想和算法實(shí)現(xiàn) 算法思想算法思想作業(yè)地址空間被分成大小相同的若干頁(yè)（頁(yè)面）內(nèi)存存儲(chǔ)空間被分成大小與頁(yè)相同的若干塊（物理塊）將連續(xù)的頁(yè)分配并存放到不連續(xù)的若干內(nèi)存塊中建立頁(yè)表，記錄每一頁(yè)對(duì)應(yīng)的存儲(chǔ)塊的塊號(hào)存儲(chǔ)器管理課件0213011526操作系統(tǒng)J2(0頁(yè))J2(1頁(yè))J

15、2(2頁(yè))J1(0頁(yè))J1(1頁(yè))J1J20123456頁(yè)面大小為1k邏輯地址空間物理地址空間頁(yè)面變換表存儲(chǔ)器管理課件 算法實(shí)現(xiàn)算法實(shí)現(xiàn)確定分頁(yè)的頁(yè)面大小確定分頁(yè)的頁(yè)面大小建立輔助數(shù)據(jù)結(jié)構(gòu)建立輔助數(shù)據(jù)結(jié)構(gòu)作業(yè)代碼裝入方式作業(yè)代碼裝入方式頁(yè)表：頁(yè)表：每個(gè)作業(yè)（進(jìn)程）一張表空閑塊鏈表空閑塊鏈表：記錄所有未分配空閑塊情況（供分配用）存儲(chǔ)分塊表存儲(chǔ)分塊表：記錄內(nèi)存每一塊的使用情況太大太大：存在頁(yè)內(nèi)碎片太小太?。喉?yè)表占用空間太多采用動(dòng)態(tài)重定位動(dòng)態(tài)重定位在執(zhí)行時(shí)實(shí)現(xiàn)地址轉(zhuǎn)換存儲(chǔ)器管理課件2 2）地址變換過(guò)程和地址變換機(jī)構(gòu)）地址變換過(guò)程和地址變換機(jī)構(gòu) 地址的機(jī)構(gòu)由兩部分組成:P(頁(yè)號(hào))和D(頁(yè)內(nèi)偏移量)。S

16、L+ 頁(yè)表控制寄存器頁(yè)表起始地址 頁(yè)表長(zhǎng)度PD 邏輯地址頁(yè)號(hào) 頁(yè)內(nèi)偏移量BD0. 頁(yè)號(hào) 塊號(hào)1.PB.地址寄存器 分頁(yè)系統(tǒng)利用頁(yè)表進(jìn)行地址變換，由CPU中的內(nèi)存管理單元(MMU,Memory Management Unit)完成地址變換過(guò)程如下圖所示:存儲(chǔ)器管理課件分頁(yè)存儲(chǔ)管理邏輯地址轉(zhuǎn)換成物理地址方法： 邏輯地址/頁(yè)大小 取整頁(yè)號(hào) 塊號(hào) 邏輯地址/頁(yè)大小 取余頁(yè)內(nèi)位移量塊號(hào)塊號(hào)*頁(yè)大小頁(yè)大小+頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量物理地址物理地址查頁(yè)表存儲(chǔ)器管理課件地址變換實(shí)例：地址變換實(shí)例：設(shè)一個(gè)設(shè)一個(gè)3頁(yè)長(zhǎng)的進(jìn)程具有頁(yè)號(hào)頁(yè)長(zhǎng)的進(jìn)程具有頁(yè)號(hào)0，1，2，其對(duì)應(yīng)的物，其對(duì)應(yīng)的物理塊號(hào)則為理塊號(hào)則為2，3，8，如

17、果每個(gè)頁(yè)面的長(zhǎng)度為，如果每個(gè)頁(yè)面的長(zhǎng)度為1KB，則邏輯地址則邏輯地址2500所對(duì)應(yīng)的物理地址為多少？所對(duì)應(yīng)的物理地址為多少？解答： 2500/1024=2頁(yè)號(hào) 2頁(yè)對(duì)應(yīng)物理塊號(hào)8 2500%1024=452頁(yè)內(nèi)偏移 物理地址為：81024+452=8644存儲(chǔ)器管理課件為了縮短頁(yè)表查找時(shí)間，可將當(dāng)前訪問(wèn)的頁(yè)表項(xiàng)裝入到地址變換機(jī)構(gòu)中的特殊高速緩沖寄存器高速緩沖寄存器，稱為聯(lián)想存儲(chǔ)器聯(lián)想存儲(chǔ)器或稱快表快表3）改進(jìn)的地址變換機(jī)構(gòu)）改進(jìn)的地址變換機(jī)構(gòu)存儲(chǔ)器管理課件4 4）內(nèi)存的分配與回收）內(nèi)存的分配與回收計(jì)算作業(yè)（進(jìn)程）所需的頁(yè)面數(shù)查是否有足夠空閑塊數(shù)的內(nèi)存供分配 查空閑塊鏈表，分配內(nèi)存塊分配頁(yè)表空間

18、，建立頁(yè)表修改空閑鏈表及空閑總塊數(shù)等數(shù)據(jù)根據(jù)頁(yè)表，回收（釋放）各內(nèi)存塊回收頁(yè)表修改相關(guān)數(shù)據(jù)項(xiàng)若若 夠夠 分配過(guò)程分配過(guò)程 回收過(guò)程回收過(guò)程存儲(chǔ)器管理課件5）分頁(yè)分配不足之處）分頁(yè)分配不足之處v碎片問(wèn)題，雖然大部分的問(wèn)題都解決了，但是每一個(gè)作業(yè)或者進(jìn)程的最后一頁(yè)基本都不能充分利用v分割分配并存放，使邏輯完整的模塊物理上不完整，不利于內(nèi)存信息（數(shù)據(jù)）共享主程序主程序子程序子程序數(shù)據(jù)數(shù)據(jù)0頁(yè)頁(yè)1頁(yè)頁(yè)2頁(yè)頁(yè)3頁(yè)頁(yè)存儲(chǔ)器管理課件4.5 4.5 基本分段存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式1）算法思想算法思想是根據(jù)程序的模塊結(jié)構(gòu)，把作業(yè)劃分為大小不同段。每段有一個(gè)段名（通常用段號(hào)代替），段號(hào)(S)從0開(kāi)始，每

19、一段內(nèi)也從0連續(xù)編址(偏移W)采用可變分區(qū)分配算法為每一段分配分區(qū)空間，段與段之間不一定連續(xù)但段內(nèi)地址是連續(xù)的建立段表，記錄每一段的段長(zhǎng)及段在內(nèi)存的起始地址存儲(chǔ)器管理課件將程序的地址空間劃分為若干個(gè)段，物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)，這些段不必連續(xù)M邏輯地址0KY0SH0LK2000S1000L3500長(zhǎng)度 段地址操作系統(tǒng)SKL物理地址012存儲(chǔ)器管理課件2）地址結(jié)構(gòu)和地址變換過(guò)程）地址結(jié)構(gòu)和地址變換過(guò)程 地址結(jié)構(gòu)地址結(jié)構(gòu) 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)段號(hào)段號(hào)段內(nèi)地址段內(nèi)地址二維地址段表寄存器段表寄存器段表始址段表始址段表長(zhǎng)度段表長(zhǎng)度+越界中斷越界中斷段號(hào)段號(hào)段長(zhǎng)段長(zhǎng)02118k30k段號(hào)段號(hào)段內(nèi)地址

20、段內(nèi)地址邏輯地址邏輯地址物理地址物理地址段段 表表25k段始址段始址10k50k75k+相加相加存儲(chǔ)器管理課件例：以下是基本分段存儲(chǔ)管理中的地址變換機(jī)構(gòu)，例：以下是基本分段存儲(chǔ)管理中的地址變換機(jī)構(gòu)， 1）說(shuō)明分段存儲(chǔ)管理方式的地址變換過(guò)程；）說(shuō)明分段存儲(chǔ)管理方式的地址變換過(guò)程； 2）若邏輯地址中的段號(hào)）若邏輯地址中的段號(hào)S=0，段內(nèi)相對(duì)地址為，段內(nèi)相對(duì)地址為500，給出地址，給出地址變換后對(duì)應(yīng)的物理地址值。變換后對(duì)應(yīng)的物理地址值。段表寄存器段表寄存器段表始址段表始址段表長(zhǎng)度段表長(zhǎng)度+越界中斷越界中斷段號(hào)段號(hào) 段長(zhǎng)段長(zhǎng) 0214k 2k段號(hào)段號(hào)S 段內(nèi)相對(duì)地址段內(nèi)相對(duì)地址邏輯地址邏輯地址 物理地

21、址物理地址段段 表表3k段始址段始址4k8k15k+解答：解答：1）地址變換過(guò)程：取邏輯地址中的段號(hào)查段表，從而得到對(duì)應(yīng)段在內(nèi)存的起始地址，再用此起始地址與邏輯地址中的段內(nèi)相對(duì)地址相加，從而獲得對(duì)應(yīng)的物理地址；2）指定的邏輯地址經(jīng)地址變換結(jié)構(gòu)變換后的物理地址是：4596 存儲(chǔ)器管理課件3 3）段式管理的數(shù)據(jù)結(jié)構(gòu)）段式管理的數(shù)據(jù)結(jié)構(gòu)4 4）改進(jìn)的地址變換機(jī)構(gòu)）改進(jìn)的地址變換機(jī)構(gòu)增設(shè)一個(gè)關(guān)聯(lián)寄存器，用于保存最近常用的段表項(xiàng)增設(shè)一個(gè)關(guān)聯(lián)寄存器，用于保存最近常用的段表項(xiàng)。一般情況下段比頁(yè)大，因而段表項(xiàng)的數(shù)目比頁(yè)表數(shù)目少，其所需的關(guān)聯(lián)寄存器也相對(duì)較小，可以顯著地減少存取數(shù)據(jù)的時(shí)間。 進(jìn)程段表進(jìn)程段表：描

22、述組成進(jìn)程地址空間的各段，可以是指向系統(tǒng)段表中表項(xiàng)的索引。每段有段基址(base address) 系統(tǒng)段表：系統(tǒng)段表：系統(tǒng)內(nèi)所有占用段 空閑段表：空閑段表：內(nèi)存中所有空閑段，可以結(jié)合到系統(tǒng)段表中。內(nèi)存分配算法可以采用最先適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法。存儲(chǔ)器管理課件 5 5）分段分配特點(diǎn)）分段分配特點(diǎn) 分段共享分段共享：可以按段為單位來(lái)進(jìn)行共享 分段保護(hù)分段保護(hù)：可以針對(duì)不同類型的段采取不同的保護(hù) 動(dòng)態(tài)鏈接動(dòng)態(tài)鏈接：通過(guò)動(dòng)態(tài)鏈接進(jìn)行代碼共享 動(dòng)態(tài)增長(zhǎng)動(dòng)態(tài)增長(zhǎng) 沒(méi)有內(nèi)碎片沒(méi)有內(nèi)碎片，外碎片要通過(guò)內(nèi)存緊縮來(lái)消除存儲(chǔ)器管理課件采用離散分配，采用動(dòng)態(tài)重定位實(shí)現(xiàn)地址轉(zhuǎn)換采用離散分配，采用動(dòng)態(tài)重定

23、位實(shí)現(xiàn)地址轉(zhuǎn)換不同之處不同之處分頁(yè)分頁(yè)分段分段地址空間劃分地址空間劃分物理（大小固定） 邏輯（大小可變）分配空間分配空間不連續(xù)的塊不連續(xù)的分區(qū)地址結(jié)構(gòu)地址結(jié)構(gòu)一維二維地址變換地址變換塊號(hào)與頁(yè)內(nèi)位段始地址與段內(nèi) 移量拼接相對(duì)地址相加共享性共享性不利于共享利于共享6 6）分頁(yè)與分段存儲(chǔ)管理的比較）分頁(yè)與分段存儲(chǔ)管理的比較存儲(chǔ)器管理課件可重入代碼：不允許任何進(jìn)程對(duì)其修改的共享代碼可重入代碼：不允許任何進(jìn)程對(duì)其修改的共享代碼v分頁(yè)共享分頁(yè)共享 每個(gè)共享進(jìn)程的頁(yè)表項(xiàng)中記錄共享代碼的所有物理塊號(hào)v分段共享分段共享 每個(gè)進(jìn)程的段表中記錄共享段的物理地址7）信息的共享）信息的共享存儲(chǔ)器管理課件4.6 4.6

24、段頁(yè)式存儲(chǔ)管理方式段頁(yè)式存儲(chǔ)管理方式引入：引入：分頁(yè)存儲(chǔ)管理能有效地提高內(nèi)存的利用率，而分段存儲(chǔ)管理則能很好地滿足用戶需要。將兩種存儲(chǔ)管理方式“各取所長(zhǎng)”后，則可以將兩者結(jié)合成一種新的存儲(chǔ)管理方式 “段頁(yè)式存儲(chǔ)管理” 。段頁(yè)式存儲(chǔ)管理既具有分段系統(tǒng)便于實(shí)現(xiàn)、分段可共享、易于保護(hù)、可動(dòng)態(tài)鏈接等優(yōu)點(diǎn)；又能像分頁(yè)系統(tǒng)那樣很好地解決內(nèi)存的外碎片問(wèn)題，以及為各個(gè)分段可不連續(xù)地分配內(nèi)存等問(wèn)題。存儲(chǔ)器管理課件算法思想算法思想作業(yè)地址空間先分段，每段再分頁(yè)作業(yè)地址空間先分段，每段再分頁(yè)內(nèi)存存儲(chǔ)空間按頁(yè)的大小分塊內(nèi)存存儲(chǔ)空間按頁(yè)的大小分塊為每段的若干頁(yè)分配存儲(chǔ)塊空間，并分塊存放為每段的若干頁(yè)分配存儲(chǔ)塊空間，并分

25、塊存放建立段表、頁(yè)表記錄作業(yè)段、頁(yè)與內(nèi)存塊的對(duì)應(yīng)信息建立段表、頁(yè)表記錄作業(yè)段、頁(yè)與內(nèi)存塊的對(duì)應(yīng)信息地址結(jié)構(gòu)地址結(jié)構(gòu) 地址結(jié)構(gòu)由段號(hào)、段內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)地址段號(hào)、段內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)地址三部分組成段號(hào)S段內(nèi)地址頁(yè)號(hào)P頁(yè)內(nèi)地址W存儲(chǔ)器管理課件段頁(yè)式存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)段頁(yè)式存儲(chǔ)管理的數(shù)據(jù)結(jié)構(gòu)段表：段表：記錄了每一段的頁(yè)表起始地址和頁(yè)表長(zhǎng)度頁(yè)表：頁(yè)表：記錄了每一個(gè)段所對(duì)應(yīng)的邏輯頁(yè)號(hào)與內(nèi)存塊號(hào)的對(duì)應(yīng)關(guān)系，每一段有一個(gè)頁(yè)表，而一個(gè)程序可能有多個(gè)頁(yè)表空閑內(nèi)存頁(yè)表：空閑內(nèi)存頁(yè)表：由于物理內(nèi)存采用分頁(yè)式的存儲(chǔ)管理，所以它的結(jié)構(gòu)同分頁(yè)式存儲(chǔ)管理物理內(nèi)存分配：物理內(nèi)存分配：同分頁(yè)式存儲(chǔ)管理存儲(chǔ)器管理課件段表及其頁(yè)表段表及其頁(yè)

26、表： 存儲(chǔ)器管理課件地址變換過(guò)程地址變換過(guò)程在段頁(yè)式存儲(chǔ)管理中，為了實(shí)現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)中需要同時(shí)配置段表和頁(yè)表。由于允許將一個(gè)段中的頁(yè)進(jìn)行不連續(xù)分配，因而使段表的內(nèi)容有所變化：它不再是段內(nèi)起始地址和段長(zhǎng)，而是頁(yè)表起始地址和頁(yè)表長(zhǎng)度。其變換過(guò)程如下圖所示：存儲(chǔ)器管理課件存儲(chǔ)器管理課件改進(jìn)的地址變換改進(jìn)的地址變換段頁(yè)式存儲(chǔ)管理中，為獲得一條指令或數(shù)據(jù)需三次三次訪問(wèn)內(nèi)存：第一次訪問(wèn)內(nèi)存中的段表，獲得頁(yè)表地址；第二次訪問(wèn)內(nèi)存中的頁(yè)表，獲得該頁(yè)所在的物理塊號(hào)，并將該塊號(hào)與頁(yè)內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；第三次訪問(wèn)才是真正根據(jù)所得的物理地址取出指令或者數(shù)據(jù)。 顯然，速度下降很多，于

27、是在地址變換機(jī)構(gòu)中引入一個(gè)聯(lián)想存儲(chǔ)器（快表或高速緩沖寄存器）聯(lián)想存儲(chǔ)器（快表或高速緩沖寄存器），每次訪問(wèn)內(nèi)存時(shí)，都是同時(shí)利用段號(hào)和頁(yè)號(hào)進(jìn)行檢索。存儲(chǔ)器管理課件存儲(chǔ)分配與管理方式小結(jié)存儲(chǔ)分配與管理方式小結(jié)v連續(xù)分配連續(xù)分配：?jiǎn)我贿B續(xù)區(qū)分配 固定分區(qū)分配 可變分區(qū)分配 可重定位分區(qū)分配v離散分配離散分配：基本分頁(yè)分配 基本分段分配 段頁(yè)式分配共同點(diǎn)：作業(yè)必須一次性全部裝入內(nèi)存共同點(diǎn)：作業(yè)必須一次性全部裝入內(nèi)存存儲(chǔ)器管理課件問(wèn)題：容量超過(guò)內(nèi)存總?cè)萘康淖鳂I(yè)無(wú)法運(yùn)行，容量超過(guò)內(nèi)存總?cè)萘康淖鳂I(yè)無(wú)法運(yùn)行， 多道作業(yè)總?cè)萘砍^(guò)內(nèi)存容量也無(wú)法運(yùn)行。多道作業(yè)總?cè)萘砍^(guò)內(nèi)存容量也無(wú)法運(yùn)行。解決：物理擴(kuò)充存儲(chǔ)器（容量

28、）物理擴(kuò)充存儲(chǔ)器（容量） 邏輯擴(kuò)充內(nèi)存邏輯擴(kuò)充內(nèi)存 虛擬存儲(chǔ)器虛擬存儲(chǔ)器存儲(chǔ)器管理課件4.7 4.7 虛擬存儲(chǔ)器的基本概念與實(shí)現(xiàn)虛擬存儲(chǔ)器的基本概念與實(shí)現(xiàn)1 1）虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入 作業(yè)調(diào)度時(shí)，僅裝入裝入其代碼的一部分到內(nèi)存一部分到內(nèi)存，待運(yùn)行需要時(shí)再裝入其余部分，同時(shí)還可將不再不再運(yùn)行的部分調(diào)出內(nèi)存運(yùn)行的部分調(diào)出內(nèi)存 變相地?cái)U(kuò)充了內(nèi)存容量變相地?cái)U(kuò)充了內(nèi)存容量, ,即實(shí)現(xiàn)了虛擬存儲(chǔ)器即實(shí)現(xiàn)了虛擬存儲(chǔ)器存儲(chǔ)器管理課件2 2）局部性問(wèn)題）局部性問(wèn)題 指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域， 即不會(huì)涉及整個(gè)地址空間。局部性表現(xiàn)在以下兩個(gè)

29、方面：時(shí)間局部性時(shí)間局部性：即一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)都集中在一個(gè)較短時(shí)期內(nèi)?？臻g局部性空間局部性：即當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。 即在一段時(shí)間間隔內(nèi)，僅裝入一部分代碼即在一段時(shí)間間隔內(nèi)，僅裝入一部分代碼, ,作業(yè)照樣能正作業(yè)照樣能正常運(yùn)行常運(yùn)行存儲(chǔ)器管理課件虛擬存儲(chǔ)的基本原理虛擬存儲(chǔ)的基本原理在程序裝入時(shí)，只需將當(dāng)前需要執(zhí)行的部分頁(yè)或段讀入到內(nèi)存，就可讓程序開(kāi)始執(zhí)行(部分裝入部分裝入)。在程序執(zhí)行過(guò)程中，如果需執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存（稱為缺頁(yè)或缺段），則由處理器通知操作系統(tǒng)將相應(yīng)的頁(yè)或段調(diào)入到內(nèi)存，然

30、后繼續(xù)執(zhí)行程序（請(qǐng)請(qǐng)求調(diào)入求調(diào)入）。另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁(yè)或段調(diào)出保存在外存上，從而騰出空間存放將要裝入的程序以及將要調(diào)入的頁(yè)或段（置換置換）3 3）虛存的原理與定義）虛存的原理與定義 存儲(chǔ)器管理課件虛擬存儲(chǔ)虛擬存儲(chǔ)器器的的定義定義是指具有是指具有請(qǐng)求調(diào)入請(qǐng)求調(diào)入功能和功能和置換置換功能，能從功能，能從邏輯邏輯上對(duì)內(nèi)存加上對(duì)內(nèi)存加以以擴(kuò)充擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。的一種存儲(chǔ)器系統(tǒng)。 邏輯容量由機(jī)器位數(shù)決定，容量為物理內(nèi)存和外存交邏輯容量由機(jī)器位數(shù)決定，容量為物理內(nèi)存和外存交換區(qū)容量之和，比實(shí)際容量大得多。換區(qū)容量之和，比實(shí)際容量大得多。 其運(yùn)行速度接近內(nèi)存速度其運(yùn)行速度接近內(nèi)存速

31、度 而每位的成本又接近外存。而每位的成本又接近外存。引入虛擬存儲(chǔ)技術(shù)的好處可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存存儲(chǔ)器管理課件覆蓋覆蓋 是一種解決小內(nèi)存運(yùn)行大作業(yè)的方法。一個(gè)作業(yè)通常由程序員事先組織好覆蓋結(jié)構(gòu)，若干程序段和數(shù)據(jù)段可以共享內(nèi)存區(qū)域，不同時(shí)調(diào)入內(nèi)存而是根據(jù)需要分別調(diào)入。覆蓋發(fā)生在一個(gè)作業(yè)內(nèi)。交換交換 在內(nèi)存空間緊張時(shí)，把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)調(diào)到外存上，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需的程序和數(shù)據(jù)調(diào)入內(nèi)存。根據(jù)對(duì)換的單位不同稱為“進(jìn)程對(duì)換”和“部分對(duì)換”。4 4）虛存的實(shí)現(xiàn)）虛

32、存的實(shí)現(xiàn)關(guān)鍵技術(shù)：覆蓋與交換技術(shù)關(guān)鍵技術(shù)：覆蓋與交換技術(shù)存儲(chǔ)器管理課件實(shí)現(xiàn)方式：實(shí)現(xiàn)方式：請(qǐng)求分頁(yè)請(qǐng)求分頁(yè)存儲(chǔ)管理-在基本分頁(yè)系統(tǒng)的基礎(chǔ)上增加請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能請(qǐng)求分段請(qǐng)求分段存儲(chǔ)管理-在基本分段系統(tǒng)的基礎(chǔ)上增加請(qǐng)求調(diào)段和段置換功能。5）虛存的特點(diǎn)）虛存的特點(diǎn) 多次性多次性 對(duì)換性對(duì)換性 虛擬性虛擬性存儲(chǔ)器管理課件4.8 4.8 請(qǐng)求分頁(yè)存儲(chǔ)管理請(qǐng)求分頁(yè)存儲(chǔ)管理1 1）算法思想與實(shí)現(xiàn)）算法思想與實(shí)現(xiàn) 算法思想算法思想作業(yè)分頁(yè)，內(nèi)存分塊，頁(yè)與塊的大小相等先裝入部分頁(yè)到內(nèi)存待運(yùn)行需要時(shí)再調(diào)入新的頁(yè)，淘汰舊的頁(yè)（交換） 算法實(shí)現(xiàn)算法實(shí)現(xiàn)軟、硬件支持軟、硬件支持：足夠大的外存及內(nèi)存，地址變換機(jī)構(gòu)等

33、相關(guān)管理軟件擴(kuò)充頁(yè)表功能擴(kuò)充頁(yè)表功能（增加頁(yè)表表項(xiàng)）增加增加缺頁(yè)中斷缺頁(yè)中斷及其處理功能及其處理功能存儲(chǔ)器管理課件2)2)頁(yè)表表項(xiàng)：增加換入換出所需的必要信息狀態(tài)位：頁(yè)表表項(xiàng)：增加換入換出所需的必要信息狀態(tài)位：存在位存在位（present bit，內(nèi)存頁(yè)和外存頁(yè)）修改位修改位(modified bit)訪問(wèn)統(tǒng)計(jì)訪問(wèn)統(tǒng)計(jì)：在近期內(nèi)被訪問(wèn)的次數(shù)，或最近一次訪問(wèn)到現(xiàn)在的時(shí)間間隔外存地址外存地址(disk address)頁(yè)號(hào)物理塊號(hào)存在位修改位訪問(wèn)統(tǒng)計(jì)外存地址10102200031510存儲(chǔ)器管理課件3 3）缺頁(yè)中斷及其處理過(guò)程）缺頁(yè)中斷及其處理過(guò)程缺頁(yè)中斷缺頁(yè)中斷由由CPU的地址變換機(jī)構(gòu)產(chǎn)生缺頁(yè)中

34、斷，然后調(diào)用操作系統(tǒng)的地址變換機(jī)構(gòu)產(chǎn)生缺頁(yè)中斷，然后調(diào)用操作系統(tǒng)提供的中斷處理程序。提供的中斷處理程序。缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和進(jìn)行處理，而不是在一條指令執(zhí)行完畢之后。所缺的頁(yè)面調(diào)入之后，重新執(zhí)行被中斷的指令。一條指令的執(zhí)行可能產(chǎn)生多次缺頁(yè)中斷。缺頁(yè)中斷的特殊性：缺頁(yè)中斷的特殊性：存儲(chǔ)器管理課件存儲(chǔ)器管理課件缺頁(yè)中斷請(qǐng)求缺頁(yè)中斷請(qǐng)求 保留保留CPU現(xiàn)場(chǎng)現(xiàn)場(chǎng) 在外存中找該頁(yè)在外存中找該頁(yè)內(nèi)存滿內(nèi)存滿y淘汰的頁(yè)修改過(guò)淘汰的頁(yè)修改過(guò)y修改頁(yè)寫(xiě)回外存修改頁(yè)寫(xiě)回外存 nOS負(fù)責(zé)從外存讀缺的頁(yè)負(fù)責(zé)從外存讀缺的頁(yè)啟動(dòng)啟動(dòng)I/O硬件硬件將頁(yè)從外存調(diào)入將頁(yè)從外存調(diào)入修改頁(yè)表修改頁(yè)表 指令重執(zhí)行指令重執(zhí)行 恢

35、復(fù)恢復(fù)CPU現(xiàn)現(xiàn) 場(chǎng)場(chǎng) n 在實(shí)際的在實(shí)際的OS中，中，由于啟動(dòng)由于啟動(dòng)I/O操作到操作到頁(yè)從外存裝入頁(yè)從外存裝入CPU要等待一定的時(shí)間，要等待一定的時(shí)間，所以往往引起缺頁(yè)所以往往引起缺頁(yè)的進(jìn)程要阻塞，讓的進(jìn)程要阻塞，讓出出CPU，其它進(jìn)程，其它進(jìn)程運(yùn)行，一旦調(diào)入結(jié)運(yùn)行，一旦調(diào)入結(jié)束，束，CPU立即被搶立即被搶占，引起缺頁(yè)的進(jìn)占，引起缺頁(yè)的進(jìn)程立即從阻塞狀態(tài)程立即從阻塞狀態(tài)占有占有CPU。（這同。（這同一般的進(jìn)程狀態(tài)轉(zhuǎn)一般的進(jìn)程狀態(tài)轉(zhuǎn)換不同）換不同）選擇一頁(yè)換出選擇一頁(yè)換出缺頁(yè)中斷處理過(guò)程缺頁(yè)中斷處理過(guò)程存儲(chǔ)器管理課件4 4）內(nèi)存塊的分配）內(nèi)存塊的分配固定分配固定分配：分配固定數(shù)目的內(nèi)存塊給作

36、業(yè)，以后不再改變可變分配可變分配：分配給作業(yè)的塊數(shù)不固定，可動(dòng)態(tài)改變平均分配按比例分配根據(jù)優(yōu)先權(quán)分配 最小物理塊的確定最小物理塊的確定 分配策略分配策略 分配方法分配方法存儲(chǔ)器管理課件5 5）內(nèi)存塊的調(diào)頁(yè)及置換策略）內(nèi)存塊的調(diào)頁(yè)及置換策略頁(yè)的調(diào)進(jìn)策略頁(yè)的調(diào)進(jìn)策略 決定什么時(shí)候?qū)⒁粋€(gè)頁(yè)從外存調(diào)入物理內(nèi)存 請(qǐng)求調(diào)入請(qǐng)求調(diào)入 提前（預(yù)）調(diào)入提前（預(yù)）調(diào)入 頁(yè)的淘汰與調(diào)出頁(yè)的淘汰與調(diào)出 又稱之為置換，在內(nèi)存已滿時(shí)決定將哪個(gè)虛頁(yè)從內(nèi)存中移出。該部分重點(diǎn)討論的問(wèn)題包括：p 置換方式置換方式p 置換的位置置換的位置p 置換的算法置換的算法存儲(chǔ)器管理課件n頁(yè)的置換方式：頁(yè)的置換方式：固定分配，局部置換固定分配

37、，局部置換可變分配，全局置換可變分配，全局置換可變分配，局部置換可變分配，局部置換n置換頁(yè)在外存的位置：置換頁(yè)在外存的位置：外存文件區(qū)外存文件區(qū)外存對(duì)換區(qū)外存對(duì)換區(qū)內(nèi)存內(nèi)存外存外存文件區(qū)文件區(qū)對(duì)換區(qū)對(duì)換區(qū)每次置換需查找文件每次置換需查找文件僅為內(nèi)存塊與盤塊的僅為內(nèi)存塊與盤塊的直接存取操作直接存取操作存儲(chǔ)器管理課件n頁(yè)面置換（淘汰）算法頁(yè)面置換（淘汰）算法l基本原則基本原則：l常用算法常用算法 最佳算法最佳算法 先進(jìn)先出算法先進(jìn)先出算法 最近最久未使用（最近最久未使用（LRULRU）算法）算法 ClockClock算法及其改進(jìn)算法算法及其改進(jìn)算法降低頁(yè)面更換率降低頁(yè)面更換率，應(yīng)把未來(lái)不再使用的或

38、短期內(nèi)較少使用的頁(yè)面調(diào)出，通常只能在局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測(cè)；相反會(huì)有“抖動(dòng)抖動(dòng)”存儲(chǔ)器管理課件v最佳算法（最佳算法（Optimal）思想思想：選擇“未來(lái)不再使用的”或“在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)的”頁(yè)面被置換。特點(diǎn)特點(diǎn)：這是一種理想情況，是實(shí)際執(zhí)行中無(wú)法預(yù)知的，因而不能實(shí)現(xiàn)，通常作為性能評(píng)價(jià)的依據(jù)。例：例：假設(shè)某作業(yè)訪問(wèn)頁(yè)面引用序列為：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1采用固定分配，局部置換淘汰方式（分配三個(gè)內(nèi)存塊）77707012012032432032017010120 30 42 3 03

39、2 12 0 1 701淘汰淘汰7淘汰淘汰1 淘汰淘汰0淘汰淘汰4淘汰淘汰3淘汰淘汰2存儲(chǔ)器管理課件例例1. 1. 設(shè)設(shè)M=3M=3，頁(yè)面走向如下圖所示，采用，頁(yè)面走向如下圖所示，采用FIFOFIFO。計(jì)算其缺。計(jì)算其缺頁(yè)中斷次數(shù)和缺頁(yè)率。頁(yè)中斷次數(shù)和缺頁(yè)率。512345341234P121110987654321時(shí)刻FM4+3+4+2+34-+1+23-+4+12-+3+41-+5+34-+534-534-2+53-+1+25-+125-由表可以算出缺頁(yè)中斷次數(shù)缺頁(yè)中斷次數(shù)F=9，而缺頁(yè)率：缺頁(yè)率：912=75%。 先進(jìn)先出算法（先進(jìn)先出算法（FIFO）思想：思想：選擇進(jìn)入內(nèi)存最早的頁(yè)面被置

40、換。存儲(chǔ)器管理課件例2. 設(shè)M=4，采用FIFO，其余同例其余同例1。計(jì)算其缺頁(yè)中斷次數(shù)計(jì)算其缺頁(yè)中斷次數(shù)和缺頁(yè)率。和缺頁(yè)率。512345341234P121110987654321時(shí)刻FM4+3+4+2+34+1+234-+1234-1234-5+123-+4+512-+3+451-+2+345-+1+234-+5+123-+由表可以算出缺頁(yè)中斷次數(shù)F=10，而缺頁(yè)率：1012=83%。存儲(chǔ)器管理課件 特點(diǎn)：特點(diǎn)：開(kāi)銷很低但性能較差。較早調(diào)入的頁(yè)往往是經(jīng)常被訪問(wèn)的頁(yè)，這些頁(yè)在FIFO算法下被反復(fù)調(diào)入和調(diào)出，產(chǎn)生BeladyBelady現(xiàn)象現(xiàn)象。 BeladyBelady現(xiàn)象現(xiàn)象：采用FIFO

41、算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁(yè)面，有時(shí)就會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)率反而提高的異?，F(xiàn)象。 BeladyBelady現(xiàn)象的原因現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問(wèn)內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問(wèn)的。存儲(chǔ)器管理課件v最近最久未使用算法最近最久未使用算法(LRU, Least Recently Used)(LRU, Least Recently Used)選擇內(nèi)存中最近最久未使用的頁(yè)面被置換。這是局部性原理的合理近似，性能接近最佳算法。需要硬件機(jī)構(gòu)來(lái)記錄頁(yè)面使用時(shí)間的先后關(guān)系，硬件機(jī)構(gòu)可以為：一個(gè)特殊的棧：一個(gè)特殊的棧：把被訪問(wèn)的頁(yè)面移到棧頂，于是棧底

42、的是最久未使用頁(yè)面。每個(gè)頁(yè)面設(shè)立移位寄存器每個(gè)頁(yè)面設(shè)立移位寄存器（作為計(jì)數(shù)器）：被訪問(wèn)時(shí)左邊最高位置1，定期右移并且最高位補(bǔ)0，于是寄存器數(shù)值最小的是最久未使用頁(yè)面。存儲(chǔ)器管理課件512345341234P121110987654321時(shí)刻FM4+3+4+2+34-+1+23-+4+12-+3+41-+5+34-+453-345-2+34-+1+23-+5+12-+算出缺頁(yè)中斷次數(shù)F=10，缺頁(yè)率f =1012=83。例例3. 3. 設(shè)設(shè)M=3M=3，頁(yè)面走向如下圖所示，采用，頁(yè)面走向如下圖所示，采用LRULRU。計(jì)算其缺。計(jì)算其缺頁(yè)中斷次數(shù)和缺頁(yè)率。頁(yè)中斷次數(shù)和缺頁(yè)率。存儲(chǔ)器管理課件5123

43、45341234P121110987654321時(shí)刻FM4+3+4+2+34+1+234-+4123-3412-5+341-+4531-3451-2+345-+1+234-+5+123-+由表可以算出缺頁(yè)中斷次數(shù)F=8，而缺頁(yè)率：812=67%。例例4. 4. 設(shè)設(shè)M=4M=4，頁(yè)面走向如下圖所示，采用，頁(yè)面走向如下圖所示，采用LRULRU。計(jì)算其缺。計(jì)算其缺頁(yè)中斷次數(shù)和缺頁(yè)率。頁(yè)中斷次數(shù)和缺頁(yè)率。特點(diǎn)：性能接近最佳算法；特點(diǎn)：性能接近最佳算法； 由于需要記錄頁(yè)面訪問(wèn)先后順序，硬件開(kāi)銷太大。由于需要記錄頁(yè)面訪問(wèn)先后順序，硬件開(kāi)銷太大。存儲(chǔ)器管理課件 也稱最近未使用算法也稱最近未使用算法(NRU

44、, Not Recently Used)(NRU, Not Recently Used)或二次機(jī)會(huì)或二次機(jī)會(huì)算法。算法。內(nèi)存中所有頁(yè)面鏈接成一個(gè)循環(huán)隊(duì)列，每頁(yè)有一個(gè)使用標(biāo)志位，若該頁(yè)被訪問(wèn)則置1，由硬件自動(dòng)完成。置換時(shí)，采用一個(gè)指針，從當(dāng)前指針位置開(kāi)始按照地址先后檢查各頁(yè)，尋找標(biāo)志位為0的頁(yè)面作為置換頁(yè)。指針經(jīng)過(guò)標(biāo)志位為1的頁(yè)面，將其改為0。最后指針停留在被置換頁(yè)的下一頁(yè)處。 Clock置換算法置換算法存儲(chǔ)器管理課件入口查尋指針前進(jìn)一步，指向下一個(gè)表目頁(yè)面訪問(wèn)位0?選擇該頁(yè)面淘汰是返回置頁(yè)面訪問(wèn)位“0”否塊號(hào)頁(yè)號(hào)訪問(wèn)位 指針0124034215650711替換指針存儲(chǔ)器管理課件存儲(chǔ)器管理課件v

45、改進(jìn)型改進(jìn)型Clock置換算法置換算法增加一個(gè)修改位M 由訪問(wèn)位A和修改位M可以組合成下面四種類型的頁(yè)面：1 1類類(A=0, M=0):(A=0, M=0): 表示該頁(yè)最近既未被訪問(wèn)， 又未被修改， 是最佳淘汰頁(yè)。2 2類類(A=0, M=1)(A=0, M=1)：表示該頁(yè)最近未被訪問(wèn)， 但已被修改， 并不是很好的淘汰頁(yè)。3 3類類(A=1, M=0)(A=1, M=0)：最近已被訪問(wèn)， 但未被修改， 該頁(yè)有可 能再被訪問(wèn)。4 4類類(A=1, M=1):(A=1, M=1): 最近已被訪問(wèn)且被修改， 該頁(yè)可能再被訪 問(wèn)。 存儲(chǔ)器管理課件其執(zhí)行過(guò)程可分成以下三步： (1) 從指針?biāo)甘镜漠?dāng)前

46、位置開(kāi)始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。 (2) 如果第一步失敗，即查找一輪后未遇到第一類頁(yè)面， 則開(kāi)始第二輪掃描，尋找A=0且M=1的第二類頁(yè)面，將所遇到的第一個(gè)這類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有掃描過(guò)的頁(yè)面的訪問(wèn)位都置0。 (3) 如果第二步也失敗，亦即未找到第二類頁(yè)面，則將指針?lè)祷氐介_(kāi)始的位置，并將所有的訪問(wèn)位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。 存儲(chǔ)器管理課件4.9 4.9 請(qǐng)求分段存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理1 1）算法思想與實(shí)現(xiàn)）算法思想與實(shí)現(xiàn)算法思想算法思想在簡(jiǎn)單段式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)段和段置換功能。算法實(shí)現(xiàn)算法實(shí)現(xiàn)關(guān)鍵是擴(kuò)充段表功能和缺段中斷處理段段號(hào)號(hào)段段