計(jì)算機(jī)存儲(chǔ)管理.ppt

1、存儲(chǔ)管理,本章內(nèi)容提要,引言 分區(qū)法 分頁(yè)技術(shù) 分段技術(shù) 段頁(yè)式技術(shù) 虛擬存儲(chǔ)器 請(qǐng)求分頁(yè)技術(shù) 頁(yè)面置換算法 內(nèi)存塊的分配和抖動(dòng)問(wèn)題 請(qǐng)求分段技術(shù) Linux系統(tǒng)的存儲(chǔ)管理,5.1 引 言,內(nèi)存（Main Memory或Primary Memory或Real Memory）也稱主存，是指CPU能直接存取指令和數(shù)據(jù)的存儲(chǔ)器。,內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位,5.1.1 用戶程序的地址空間,用戶程序的主要處理階段,主要處理階段 編輯 編譯 連接 裝入 運(yùn)行 有關(guān)概念 裝入程序 相對(duì)地址或邏輯地址 絕對(duì)地址或物理地址 程序裝入內(nèi)存的方式 絕對(duì)裝入方式 可重定位裝入方式 動(dòng)態(tài)運(yùn)行時(shí)裝入方式,5.1.2 重定

2、位,邏輯地址空間（簡(jiǎn)稱地址空間） 由程序中邏輯地址組成的地址范圍 內(nèi)存空間（也稱物理空間或絕對(duì)空間） 由內(nèi)存中一系列存儲(chǔ)單元所限定的地址范圍 重定位 程序和數(shù)據(jù)裝入內(nèi)存時(shí)，需對(duì)目標(biāo)程序中的地址進(jìn)行修改。這種把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過(guò)程稱作重定位 重定位方式 靜態(tài)重定位 動(dòng)態(tài)重定位,1靜態(tài)重定位 目標(biāo)程序裝入內(nèi)存時(shí)進(jìn)行地址變換,程序裝入內(nèi)存時(shí)的情況,靜態(tài)重定位示意圖,優(yōu)點(diǎn) :無(wú)需增加硬件地址轉(zhuǎn)換機(jī)構(gòu) 主要缺點(diǎn) :位置“釘死”；不便共享,2動(dòng)態(tài)重定位 程序執(zhí)行期間進(jìn)行重定位,動(dòng)態(tài)重定位示意圖,主要優(yōu)點(diǎn)：位置可變，不必連續(xù) ；易于共享 主要缺點(diǎn) ：需要附加硬件支持 ；軟件算法比較復(fù)雜,5.1.

3、3 對(duì)換技術(shù),對(duì)換兩個(gè)進(jìn)程示意圖,多道程序?qū)Q技術(shù)示例,5.2 分區(qū)法,分區(qū)分配是為支持多道程序運(yùn)行而設(shè)計(jì)的一種最簡(jiǎn)單的存儲(chǔ)管理方式。 5.2.1 固定分區(qū)法 分區(qū)個(gè)數(shù)固定不變，大小固定不變 劃分分區(qū)方式： 等分方式 差分方式,固定分區(qū)法,固定分區(qū)管理示意圖,分區(qū)說(shuō)明表,優(yōu)點(diǎn)：管理方式簡(jiǎn)單，所需操作系統(tǒng)軟件和處理開銷都小 缺點(diǎn) ：內(nèi)存空間利用率不高，碎片嚴(yán)重； 活動(dòng)進(jìn)程數(shù)目受限； 無(wú)法預(yù)知所需內(nèi)存大小,5.2.2 動(dòng)態(tài)分區(qū)法,1分區(qū)的分配,MVT的內(nèi)存分配和進(jìn)程調(diào)度情況,操作系統(tǒng)內(nèi)部設(shè)置一個(gè) 內(nèi)存登記表,動(dòng)態(tài)分區(qū)法,2數(shù)據(jù)結(jié)構(gòu) 常用的數(shù)據(jù)結(jié)構(gòu)形式： （1）空閑分區(qū)表 （2）空閑分區(qū)鏈 使用鏈指

4、針把所有的空閑分區(qū)鏈接成一條鏈,3分配算法,（1）最先適應(yīng)算法 空閑表是按地址排列的（即空閑塊地址小的，在表中的序號(hào)也?。?。 （2）最佳適應(yīng)算法 空閑表是以空閑分區(qū)的大小為序、按增量形式排列的，即小塊在前，大塊在后。 （3）循環(huán)適應(yīng)算法 最先適應(yīng)算法的變種。它不從空閑表的開頭查找，而從上次找到的可用分區(qū)的下一個(gè)空閑分區(qū)開始查找，從中選擇滿足大小要求的第一個(gè)空閑分區(qū)。,分配算法,三種算法分配16KB空閑分區(qū)之前和之后的內(nèi)存配置情況,4. 碎片問(wèn)題 “碎片”或“零頭”： 內(nèi)存中這種容量太小、無(wú)法利用的小分區(qū) 內(nèi)部碎片： 在一個(gè)分區(qū)內(nèi)部出現(xiàn)的碎片（即被浪費(fèi)的空間），如固定分區(qū)法會(huì)產(chǎn)生內(nèi)部碎片。 外部

5、碎片： 在所有分區(qū)之外新增的碎片,5.2.3 可重定位分區(qū)分配,1緊縮 緊縮（或拼湊） 可重定位分區(qū)法 緊縮時(shí)機(jī) 釋放所占分區(qū)時(shí) 分配進(jìn)程分區(qū)時(shí),可重定位分區(qū)的緊縮示意圖,2動(dòng)態(tài)重定位的實(shí)現(xiàn)過(guò)程 動(dòng)態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn) 硬件支持 基址寄存器 限長(zhǎng)寄存器,動(dòng)態(tài)重定位的實(shí)現(xiàn)過(guò)程,3. 可重定位分區(qū)法的優(yōu)缺點(diǎn),優(yōu)點(diǎn)： 可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設(shè)計(jì)，提高內(nèi)存的利用率。 缺點(diǎn)： 緊縮花費(fèi)了大量CPU時(shí)間 當(dāng)進(jìn)程大于整個(gè)空閑區(qū)時(shí)，仍要浪費(fèi)一定的內(nèi)存 進(jìn)程的存儲(chǔ)區(qū)內(nèi)可能放有從未使用的信息 進(jìn)程之間無(wú)法對(duì)信息共享,5.3 分頁(yè)技術(shù),5.3.1 分頁(yè)存儲(chǔ)管理的基本概念 （1）邏輯空間分

6、頁(yè) （2）內(nèi)存空間分塊 內(nèi)存塊或頁(yè)框 （3）邏輯地址表示,分頁(yè)技術(shù)的地址結(jié)構(gòu)示意圖,給定的邏輯地址是A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)p和頁(yè)內(nèi)地址d可按下式求得 p = INT(A/L) , d = A MOD L 式中，INT是向下整除的函數(shù)，MOD是取余函數(shù)。,分頁(yè)存儲(chǔ)管理的基本概念,（4）內(nèi)存分配原則 以塊為單位 每個(gè)頁(yè)面對(duì)應(yīng)一個(gè)內(nèi)存塊 內(nèi)存塊可不連續(xù),分頁(yè)存儲(chǔ)管理系統(tǒng)示意圖,（5）頁(yè)表,實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射,分頁(yè)存儲(chǔ)管理的基本概念,（6）內(nèi)存塊表 整個(gè)系統(tǒng)有一個(gè)內(nèi)存塊表。每個(gè)內(nèi)存塊在內(nèi)存塊表中占一項(xiàng)，表明該塊當(dāng)前空閑還是已分出去了。,分頁(yè)存儲(chǔ)管理的基本概念,5.3.2 分頁(yè)系統(tǒng)中的地

7、址映射,分頁(yè)系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu),每個(gè)進(jìn)程平均有半個(gè)頁(yè)面的內(nèi)部碎片,5.3.3 頁(yè)面尺寸,折中方案 設(shè)進(jìn)程的平均大小為s字節(jié)，頁(yè)面尺寸為p字節(jié)，每個(gè)頁(yè)表項(xiàng)占e字節(jié)。那么，每個(gè)進(jìn)程需要的頁(yè)數(shù)大約為s/p， 占用 s . e /p 字節(jié)的頁(yè)表空間。 每個(gè)進(jìn)程的內(nèi)部碎片平均為p/2。 因此，由頁(yè)表和內(nèi)部碎片帶來(lái)的總開銷是：,總開銷=,5.3.4 硬件支持,由硬件實(shí)現(xiàn)頁(yè)表的方式有多種，最簡(jiǎn)單的方式是由一組專門的寄存器來(lái)實(shí)現(xiàn)。 通常將頁(yè)表保存在內(nèi)存中，由一個(gè)頁(yè)表基址寄存器PTBR指向該頁(yè)表。整個(gè)系統(tǒng)只有一個(gè)PTBR。 帶來(lái)存取速度下降的矛盾 聯(lián)想存儲(chǔ)器，也稱快表（或Translation Lookasid

8、e Buffer, TLB）?？毂砻宽?xiàng)包括鍵號(hào)和值兩部分，鍵號(hào)是當(dāng)前進(jìn)程正在使用的某個(gè)頁(yè)面號(hào)，值是該頁(yè)面所對(duì)應(yīng)的物理塊號(hào)。,利用快表實(shí)現(xiàn)地址轉(zhuǎn)換示例,硬件支持,命中率 在快表中成功找到指定頁(yè)號(hào)的次數(shù)占總搜索次數(shù)的百分比,5.3.5 保護(hù)方式,（1）利用頁(yè)表本身進(jìn)行保護(hù) （2）設(shè)置存取控制位 （3）設(shè)置合法標(biāo)志,5.3.6 頁(yè)表的構(gòu)造,1多級(jí)頁(yè)表 大多數(shù)現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間，如232 264。在這種情況下，只用一級(jí)頁(yè)表會(huì)使頁(yè)表變得非常大。 一種方法是利用兩級(jí)頁(yè)表，即把頁(yè)表本身也分頁(yè)。,兩級(jí)頁(yè)表地址結(jié)構(gòu)示意圖,兩級(jí)頁(yè)表結(jié)構(gòu)示意圖,多級(jí)頁(yè)表,兩級(jí)頁(yè)表結(jié)構(gòu)的地址轉(zhuǎn)換,多級(jí)頁(yè)表,三級(jí)

9、頁(yè)表地址結(jié)構(gòu)示意圖,多級(jí)頁(yè)表,2散列頁(yè)表（Hashed Page Table） 以頁(yè)號(hào)作為參數(shù)形成散列值。散列表中每一項(xiàng)有一個(gè)鏈表，它把有相同散列值的元素鏈接起來(lái)。每個(gè)鏈表元素由三部分組成： 頁(yè)號(hào) 對(duì)應(yīng)的內(nèi)存塊號(hào) 指向鏈表中下一個(gè)元素的指針,散列頁(yè)表,散列頁(yè)表構(gòu)成及地址轉(zhuǎn)換過(guò)程,3倒置頁(yè)表,它是按內(nèi)存塊號(hào)排序的，每個(gè)內(nèi)存塊占有一個(gè)表項(xiàng)。每個(gè)表項(xiàng)包括存放在該內(nèi)存塊中頁(yè)面的虛擬頁(yè)號(hào)和擁有該頁(yè)面的進(jìn)程標(biāo)識(shí)符。,倒置頁(yè)表構(gòu)成及地址轉(zhuǎn)換過(guò)程,5.3.7 頁(yè)面共享,可再入代碼（或純碼）：在其執(zhí)行過(guò)程中本身不做任何修改的代碼，通常由指令和常數(shù)組成,三個(gè)進(jìn)程共享大小為三個(gè)頁(yè)面的編輯器的情況，每個(gè)進(jìn)程都有自己的

10、私有數(shù)據(jù)頁(yè)。,頁(yè)面共享示例,5.4 分段技術(shù),5.4.1 分段存儲(chǔ)管理的基本概念,分段地址空間,1分段 段是一組邏輯信息的集合。 每段都有自己的名字、長(zhǎng)度。 段號(hào),2程序的地址結(jié)構(gòu),邏輯地址要用兩個(gè)成分來(lái)表示： 段號(hào)s和段內(nèi)地址d 進(jìn)程的邏輯地址空間是二維的,分段技術(shù)地址結(jié)構(gòu)示意圖,3內(nèi)存分配,內(nèi)存以段為單位進(jìn)行分配，每段單獨(dú)占用一塊連續(xù)的內(nèi)存分區(qū)。各分區(qū)的大小由對(duì)應(yīng)段的大小決定。 4段表和段表地址寄存器 系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)段映射表，簡(jiǎn)稱“段表”。每個(gè)段在段表中占有一項(xiàng)，段表項(xiàng)中包含段號(hào)、段長(zhǎng)和段起始地址（又稱“基址”）等。 系統(tǒng)還要建立一個(gè)段表地址寄存器。它有兩部分： 該段表在內(nèi)存的起始

11、地址 該段表的長(zhǎng)度。,5分頁(yè)和分段的主要區(qū)別, 頁(yè)是信息的物理單位 段是信息的邏輯單位 頁(yè)的大小是由系統(tǒng)確定的 段的長(zhǎng)度因段而異 分頁(yè)的進(jìn)程地址空間是一維的 分段的進(jìn)程地址空間是二維的 分頁(yè)系統(tǒng)很難實(shí)現(xiàn)過(guò)程和數(shù)據(jù)的分離 分段系統(tǒng)卻可以很容易實(shí)現(xiàn)這些功能,5.4.2 地址轉(zhuǎn)換,分段地址轉(zhuǎn)換過(guò)程,5.4.3 段的共享和保護(hù),1段的共享 共享是在段一級(jí)實(shí)現(xiàn)的，任何共享信息可以單獨(dú)成為一段。 也可以只共享部分程序。,分段系統(tǒng)中段的共享,2段的保護(hù),段的保護(hù)措施包括以下三種： 存取控制 段表本身可起保護(hù)作用 表項(xiàng)中設(shè)置該段的長(zhǎng)度限制 段長(zhǎng) 段表地址寄存器中有段表長(zhǎng)度的信息 保護(hù)環(huán),5.5 段頁(yè)式技術(shù),5

12、.5.1 段頁(yè)式存儲(chǔ)管理的基本原理 等分內(nèi)存 地址空間分段 段內(nèi)分頁(yè) 邏輯地址結(jié)構(gòu) 內(nèi)存分配 段表、頁(yè)表和 段表地址寄存器,段頁(yè)式存儲(chǔ)邏輯地址結(jié)構(gòu)示意圖,5.5.2 地址轉(zhuǎn)換過(guò)程,段頁(yè)式系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu),5.6 虛擬存儲(chǔ)器,5.6.1 虛擬存儲(chǔ)器的概念 進(jìn)程在執(zhí)行之前要全部裝入內(nèi)存，這種限制是不合理的。 程序中往往含有不會(huì)被執(zhí)行的代碼 分配的內(nèi)存空間會(huì)大于它們的實(shí)際需要 一個(gè)程序的某些選項(xiàng)和特性可能很少使用 程序的執(zhí)行過(guò)程也顯示出局部性 按需分別調(diào)入內(nèi)存會(huì)帶來(lái)兩點(diǎn)好處： 用戶編制程序時(shí)不必考慮內(nèi)存容量的限制 在一定容量的內(nèi)存中就可同時(shí)裝入更多的進(jìn)程,虛擬存儲(chǔ)器（Virtual Memory）

13、 用戶能作為可編址內(nèi)存對(duì)待的虛擬存儲(chǔ)空間，它使用戶邏輯存儲(chǔ)器 與物理存儲(chǔ)器分離，是操作系統(tǒng)給用戶提供的一個(gè)比真實(shí)內(nèi)存空間大得多的地址空間。 實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)的物質(zhì)基礎(chǔ) 二級(jí)存儲(chǔ)器結(jié)構(gòu) 動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)（DAT） 虛擬存儲(chǔ)器實(shí)質(zhì)上是把用戶地址空間和實(shí)際的存儲(chǔ)空間區(qū)分開來(lái)。 它主要受到兩方面的限制： 指令中表示地址的字長(zhǎng) 外存的容量,虛擬存儲(chǔ)器的概念,5.6.2 虛擬存儲(chǔ)器的特征 虛擬擴(kuò)充 部分裝入 離散分配 多次對(duì)換,5.7 請(qǐng)求分頁(yè)技術(shù),5.7.1 請(qǐng)求分頁(yè)存儲(chǔ)管理的基本思想 是在單純分頁(yè)技術(shù)基礎(chǔ)上發(fā)展起來(lái)的 二者的根本區(qū)別在于請(qǐng)求分頁(yè)提供虛擬存儲(chǔ)器。 基本思想是： 當(dāng)一個(gè)進(jìn)程的部分頁(yè)面在內(nèi)存

14、時(shí)就可調(diào)度它運(yùn)行；在運(yùn)行過(guò)程中若用到的頁(yè)面尚未在內(nèi)存，則把它們動(dòng)態(tài)換入內(nèi)存。 為了標(biāo)示進(jìn)程的頁(yè)面是否已在內(nèi)存，在每個(gè)頁(yè)表項(xiàng)中增加一個(gè)標(biāo)志位。,5.7.2 硬件支持及缺頁(yè)處理,1頁(yè)表機(jī)制 頁(yè)表項(xiàng)通常包含下列5種信息：,典型的頁(yè)表表項(xiàng)示意圖,2缺頁(yè)中斷機(jī)構(gòu),指令執(zhí)行步驟與 缺頁(yè)中斷處理過(guò)程,5.7.3 請(qǐng)求分頁(yè)技術(shù)的性能,缺頁(yè)率p：表示缺頁(yè)中斷的概率（0p1） 等于缺頁(yè)次數(shù)與全部訪問(wèn)內(nèi)存次數(shù)之比 有效存取時(shí)間可表示為： 有效存取時(shí)間= (1-p)ma + p缺頁(yè)處理時(shí)間,缺頁(yè)導(dǎo)致以下一系列動(dòng)作（設(shè)當(dāng)前進(jìn)程為A）： 捕俘進(jìn)入操作系統(tǒng) 保存進(jìn)程A的各個(gè)寄存器和進(jìn)程狀態(tài)信息 確定該中斷是缺頁(yè)引起的 檢查

15、對(duì)該頁(yè)的訪問(wèn)是合法的，并確定該頁(yè)在磁盤上的地址 把該頁(yè)從盤上讀到空閑內(nèi)存塊中，其中包括在設(shè)備隊(duì)列中等待，直至該請(qǐng)求得到服務(wù)；等待盤尋道以及潛在時(shí)間；把該頁(yè)傳送到空閑內(nèi)存塊。 在等待盤I/O完成時(shí)，把CPU分給其他進(jìn)程（如進(jìn)程B） 盤I/O完成，發(fā)出盤中斷 保存進(jìn)程B的用戶寄存器和進(jìn)程狀態(tài) 確定該中斷來(lái)自磁盤 調(diào)整頁(yè)表和其他表格，標(biāo)明所需頁(yè)已放入內(nèi)存 進(jìn)程A就緒，等待分配CPU 調(diào)度到進(jìn)程A，則恢復(fù)它的各寄存器、進(jìn)程狀態(tài)和新的頁(yè)表，然后重新執(zhí)行前面被中斷的指令。,請(qǐng)求分頁(yè)技術(shù)的性能,缺頁(yè)中斷處理所花費(fèi)的時(shí)間主要有以下三部分： 處理缺頁(yè)中斷的時(shí)間 調(diào)入該頁(yè)的時(shí)間 重新啟動(dòng)該進(jìn)程的時(shí)間 將頁(yè)面從盤上

16、讀到內(nèi)存所花費(fèi)的時(shí)間包括： 磁盤尋道時(shí)間（即磁頭從當(dāng)前磁道移至指定磁道所用的時(shí)間） 旋轉(zhuǎn)延遲時(shí)間（即磁頭從當(dāng)前位置落到指定扇區(qū)開頭所用的時(shí)間） 數(shù)據(jù)傳輸時(shí)間 典型磁盤的旋轉(zhuǎn)延遲時(shí)間約為8 ms，尋道時(shí)間約為15 ms，傳輸時(shí)間是1 ms。,請(qǐng)求分頁(yè)技術(shù)的性能,5.8 頁(yè)面置換算法,5.8.1 頁(yè)面置換 1頁(yè)面置換過(guò)程,頁(yè)面置換過(guò)程,2頁(yè)面走向,抖動(dòng) 頻繁地更換頁(yè)面,以致系統(tǒng)的大部分時(shí)間花費(fèi)在頁(yè)面的調(diào)度和傳輸上。 盡量避免系統(tǒng)“抖動(dòng)” 存儲(chǔ)訪問(wèn)序列也叫頁(yè)面走向 對(duì)于給定的頁(yè)面大小，僅考慮其頁(yè)號(hào)，不關(guān)心完整的地址。 如果當(dāng)前對(duì)頁(yè)面p進(jìn)行了訪問(wèn)，那么，馬上又對(duì)該頁(yè)訪問(wèn)就不會(huì)缺頁(yè)。這樣連續(xù)出現(xiàn)的同一頁(yè)

17、號(hào)就簡(jiǎn)化為一個(gè)頁(yè)號(hào)。 如下地址序列（用十進(jìn)制數(shù)表示）： 0100，0432，0101，0612，0102，0103，0104，0101，0611，0102， 0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105 若每頁(yè)100個(gè)字節(jié)，則頁(yè)面走向簡(jiǎn)化為： 1，4，1，6，1，6，1，6，1，6，1,一般來(lái)說(shuō)，隨著可用塊數(shù)的增加，缺頁(yè)數(shù)將減少。,缺頁(yè)量與內(nèi)存塊數(shù)關(guān)系圖,統(tǒng)一采用下述頁(yè)面走向： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 并且假定每個(gè)作業(yè)只有三個(gè)內(nèi)存塊可供使用。,頁(yè)面走向,5.8.2 先進(jìn)先出法

18、（FIFO）,總是淘汰在內(nèi)存中停留時(shí)間最長(zhǎng)（年齡最老）的一頁(yè)，即先進(jìn)入內(nèi)存的頁(yè)，先被換出。,FIFO頁(yè)面置換序列,總共有15次缺頁(yè),優(yōu)點(diǎn)：容易理解，方便程序設(shè)計(jì)。 缺點(diǎn)： 性能并不很好，效率不高 存在Belady異?，F(xiàn)象，即缺頁(yè)率隨內(nèi)存塊增加而增加,關(guān)于一個(gè)頁(yè)面走向的FIFO淘汰算法的缺頁(yè)曲線,先進(jìn)先出（FIFO）法,5.8.3 最佳置換法（OPT）,最佳置換算法（Optimal Replacement, OPT）其實(shí)質(zhì)是：為調(diào)入新頁(yè)面而必須預(yù)先淘汰某個(gè)老頁(yè)面時(shí)，所選擇的老頁(yè)面應(yīng)在將來(lái)不被使用，或者是在最遠(yuǎn)的將來(lái)才被訪問(wèn)。,保證有最小缺頁(yè)率 OPT算法在實(shí)現(xiàn)上有困難,最佳頁(yè)面置換序列 僅出現(xiàn)9

19、次缺頁(yè)中斷,5.8.4 最近最少使用置換法（LRU）,以“最近的過(guò)去”作為“不久將來(lái)”的近似 實(shí)質(zhì)是：當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間里最久沒(méi)有使用過(guò)的頁(yè)面予以淘汰。,最近最少使用算法頁(yè)面置換序列,產(chǎn)生12次缺頁(yè),LRU算法需要實(shí)際硬件的支持。實(shí)現(xiàn)時(shí)的問(wèn)題是：怎樣確定最后訪問(wèn)以來(lái)所經(jīng)歷時(shí)間的順 序。有以下兩種可行的辦法： 計(jì)數(shù)器 棧,最近最少使用置換法,利用棧記錄目前訪問(wèn)最多的頁(yè)面示例,5.8.5 第二次機(jī)會(huì)置換法（SCR）,第二次機(jī)會(huì)置換法（Second Chance Page Replacement, SCR）是對(duì)FIFO算法的改進(jìn) 避免把經(jīng)常使用的頁(yè)面置換出去。 當(dāng)選擇某一頁(yè)面置換時(shí)

20、，就檢查最老頁(yè)面的引用位：如果是0，就立即淘汰該頁(yè)；如果該引用位是1，就給它第二次機(jī)會(huì)。,第二次機(jī)會(huì)法示例,5.8.6 時(shí)鐘置換法（Clock）,簡(jiǎn)單時(shí)鐘置換法,該算法又稱最近未使用置換法（Not Recently Used, NRU）,改進(jìn)的時(shí)鐘置換法 在頁(yè)表項(xiàng)中設(shè)置兩個(gè)狀態(tài)位： 引用位和修改位,時(shí)鐘置換法示意圖,5.8.7 最少使用置換法（LFU）,最少使用（Least Frequently Used，LFU）頁(yè)面置換算法是基于訪問(wèn)計(jì)數(shù)的頁(yè)面置換法。 為每個(gè)頁(yè)面設(shè)置一個(gè)軟件計(jì)數(shù)器 將每頁(yè)的引用位R的值加到對(duì)應(yīng)的計(jì)數(shù)器上。發(fā)生缺頁(yè)時(shí)，淘汰其計(jì)數(shù)值最小的頁(yè)。 老化（Aging）算法,5.8.8

21、 頁(yè)面緩沖算法,頁(yè)面緩沖算法（Page Buffering）是對(duì)FIFO簡(jiǎn)單置換算法的改進(jìn)。該算法維護(hù)兩個(gè)鏈表：一個(gè)是空閑頁(yè)鏈表，另一個(gè)是修改頁(yè)鏈表。 當(dāng)發(fā)生缺頁(yè)時(shí)，按照FIFO算法選取一個(gè)淘汰頁(yè)，并不是拋棄它，而是把它放入兩個(gè)鏈表中的一個(gè)。如果該頁(yè)未被修改，就放入空閑頁(yè)鏈表中；否則，把它放入修改頁(yè)鏈表中。 駐留集：進(jìn)程在內(nèi)存映像的集合,5.9 內(nèi)存塊的分配和抖動(dòng)問(wèn)題,5.9.1 內(nèi)存塊的分配 1最少內(nèi)存塊數(shù) 分給每個(gè)進(jìn)程的最少內(nèi)存塊數(shù)是指保證進(jìn)程正常運(yùn)行所需的最少內(nèi)存塊數(shù)，它是由指令集結(jié)構(gòu)決定的。 2內(nèi)存塊的分配 固定分配策略分配給進(jìn)程的內(nèi)存塊數(shù)是固定的，且在最初裝入時(shí)（即進(jìn)程創(chuàng)建時(shí)）確定塊

22、數(shù)。 可變分配策略允許分給進(jìn)程的內(nèi)存塊數(shù)隨進(jìn)程的活動(dòng)而改變。,頁(yè)面置換范圍 全局置換允許一個(gè)進(jìn)程從全體存儲(chǔ)塊的集合中選取淘汰塊，盡管該塊當(dāng)前分配給其他進(jìn)程，還是能強(qiáng)行占用。 局部置換是每個(gè)進(jìn)程只能從分給它的一組內(nèi)存塊中選擇淘汰塊。 局部置換可與固定分配策略相結(jié)合 局部置換可與可變分配策略相結(jié)合 全局置換只能與可變分配策略相結(jié)合,內(nèi)存塊的分配,3分配算法 （1）等分法內(nèi)存塊按進(jìn)程平分 （2）比例法 設(shè)進(jìn)程pi的地址空間大小為si，則總地址空間為 S=si 若可用塊的總數(shù)是m，則分給進(jìn)程pi的塊數(shù)是 ai m . si /S （3）優(yōu)先權(quán)法給高優(yōu)先級(jí)進(jìn)程分配較多內(nèi)存,5.9.2 抖動(dòng)問(wèn)題,整個(gè)系統(tǒng)

23、的頁(yè)面替換非常頻繁，以致大部分機(jī)器時(shí)間都用在來(lái)回進(jìn)行的頁(yè)面調(diào)度上，只有一小部分時(shí)間用于進(jìn)程的實(shí)際運(yùn)算。這種局面稱為系統(tǒng)“抖動(dòng)（Thrashing）”。 1產(chǎn)生抖動(dòng)的原因 內(nèi)存 不足 多道程序度高 CPU的利用率太低,CPU利用率與多道程序度之間的關(guān)系,2防止抖動(dòng)的方法 采用局部置換策略 利用工作集策略防止抖動(dòng) 掛起某些進(jìn)程 采用缺頁(yè)頻度法（Page Fault Frequency, PFF）,缺頁(yè)頻度的上限和下限,3工作集 測(cè)試表明，虛擬存儲(chǔ)系統(tǒng)的有效操作依賴于程序中訪問(wèn)的局部化程度。 （1）局部性模型 時(shí)間局部化是指一旦某條指令或數(shù)據(jù)被訪問(wèn)過(guò)，它往往很快又被再次訪問(wèn)。 空間局部化是指一旦某個(gè)位置被訪問(wèn)過(guò)，它附近的位置也可能很快要用到。