操作系統(tǒng)：第4章 存儲(chǔ)器管理 頁面置換算法

第四章存儲(chǔ)器管理虛擬存儲(chǔ)分配方式2/15回顧2.請(qǐng)求分段存儲(chǔ)管理1.請(qǐng)求分頁存儲(chǔ)管理基本分頁/段+請(qǐng)求調(diào)入+置換功能實(shí)現(xiàn)方式虛擬存儲(chǔ)器虛擬存儲(chǔ)器：僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲(chǔ)管理系統(tǒng)，它具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充。3/15頁面置換算法也稱為頁面淘汰算法，是用來選擇換出頁面的算法。4.8頁面置換算法4/154.8頁面置換算法3最佳（Optimal）置換算法124先進(jìn)先出（FIFO）置換算法最近最久未使用（LRU）置換算法時(shí)鐘（Clock）置換算法5/15最佳置換算法1算法思想： 選擇今后永遠(yuǎn)不用的頁面或者在最遠(yuǎn)的將來才用的頁面作為被淘汰頁面。不再用的很晚才用的稍后才用的6/15最佳置換算法150120304202314241451501505012032042142145缺頁率：9/20342(2)例：假定系統(tǒng)采用最佳置換算法。為某進(jìn)程分配了3個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁面走向?yàn)?,0,1,2,0,3,0,4,2,0,2,3,1,4,2,4,1,4,5,1，開始時(shí)3個(gè)物理塊均為空，表示出頁面置換過程，并計(jì)算缺頁率。7/15最佳置換算法1一種理想化的算法?？梢杂米魉惴ǖ脑u(píng)價(jià)標(biāo)準(zhǔn)。優(yōu)點(diǎn)：通?？梢员ＷC獲得最低缺頁率。缺點(diǎn)：無法實(shí)現(xiàn)。(3)優(yōu)缺點(diǎn)：8/15先進(jìn)先出置換算法12算法思想： 按照頁面進(jìn)入內(nèi)存的先后順序選擇被淘汰頁面。9/15先進(jìn)先出置換算法1250120304202314241451501505012312304231425缺頁率：14/20234302204431421125(2)例：優(yōu)點(diǎn)：直觀，實(shí)現(xiàn)簡(jiǎn)單。缺點(diǎn)：與進(jìn)程實(shí)際運(yùn)行規(guī)律不相適應(yīng)， 性能最差。(3)優(yōu)缺點(diǎn)：10/153以程序局部性原理為依據(jù)，根據(jù)頁面最近一段時(shí)間的使用情況預(yù)測(cè)未來趨勢(shì)。3最近最久未使用置換算法算法思想： 選擇最近最久未使用的頁面作為被淘汰頁面。11/153最近最久未使用置換算法50120304202314241451501505012032034123145缺頁率：12/20023024143142優(yōu)點(diǎn)：較理想的缺頁率。缺點(diǎn)：要求較多硬件支持。(2)例：(3)優(yōu)缺點(diǎn)：12/15時(shí)鐘置換算法4①為每頁設(shè)置一個(gè)訪問位，所有頁面連接成一個(gè)循環(huán)隊(duì)列。當(dāng)某頁被訪問時(shí)，其訪問位被置1。②在選擇一頁淘汰時(shí)，塊號(hào)頁號(hào)訪問位指針1402013開始訪問位=0？選擇該頁淘汰指針移動(dòng)到下一頁面置訪問位0YN③當(dāng)檢查到隊(duì)列中最后一個(gè)頁面時(shí)，若其訪問位為1，則返回隊(duì)首檢查第一個(gè)頁面。檢查頁的訪問位，若為0，就選擇該頁換出；若為1，則重新將它置0，暫不換出，再按照先進(jìn)先出算法檢查下一頁面。(1)算法思想2113/15時(shí)鐘置換算法501203042023142414515015050120320341035422032341431424204512(2)例：123000111524013缺頁率：14/2014/15練習(xí)159頁習(xí)題26分別采用四種頁面置換算法，計(jì)算頁面分配過程和缺頁率。15/15時(shí)鐘置換算法4(3)優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：較理想的缺頁率，較少的硬件支持。缺點(diǎn)：沒有考慮頁面的置換代價(jià)。16/15本章總結(jié)連續(xù)存儲(chǔ)分配方式單一連續(xù)分配固定分區(qū)分配