頁面置換算法ppt課件(更新版)
【正文】 一個(gè)進(jìn)程的內(nèi)存塊數(shù)為 3， 進(jìn)程的頁面走向?yàn)?2， 3， 2， 1， 5， 2， 4， 5， 3，2， 5， 2。 訪問位 A和修改位 M可以組合成下面四種類型的頁面 頁面置換算法 從當(dāng)前指針位置開始掃描循環(huán)隊(duì)列 ， 尋找第 1類頁面 ， ?不改變?cè)L問位 A。 ?將所有掃描過的頁面的訪問位 A都置 0。（ 假定開始時(shí) ， 物理塊為空 ， 每次調(diào)入頁面都作為一次缺頁處理 ） 頁面置換算法 Clock置換算法 1. 簡(jiǎn)單的 Clock置換算法 Clock置換算法是 LRU算法的近似算法 ， 也稱為最近未用算法 。 頁面置換算法 頁面置換算法 1. 2. 先進(jìn)先出算法 3. LRU算法 4. Clock算法 5. 其他算法 頁面置換算法 頁面置換算法的設(shè)計(jì)目標(biāo) ?具有較低的頁面更換頻率 ?換出以后不再訪問的頁面或者較長(zhǎng)時(shí)間不再使用的頁面 頁面置換算法 1. 最佳 (Optimal) Belady于 1966年提出的一種理論上的算法 ， 思想是選擇的被淘汰頁面以后將永不使用 ， 或者在最長(zhǎng) （ 未來 ） 時(shí)間內(nèi)不再被訪問 。 通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán) ，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后 ， 分配給各進(jìn)程 。 于是可組合出以下三種適用的策略 。 這種方式貌似公平 ， 但實(shí)際上是不公平的 ， 因?yàn)樗纯紤]到各進(jìn)程本身的大小 。 通常 ， 由于對(duì)換區(qū)是采用連續(xù)分配方式 ， 而事件是采用離散分配方式 ， 故對(duì)換區(qū)的磁盤 I/O速度比文件區(qū)的高 。 此時(shí) OS根據(jù)最佳置換算法 ， 將選擇頁面 7予以淘汰 。 ?2類 (A=0, M=1)：最近未被訪問 ， 但已被修改頁 。 頁面置換算法 2. 頁面緩沖算法 (PBA： Page Buffering Algorithm) 采用可變分配和局部置換方式 當(dāng)一個(gè)進(jìn)程換進(jìn)換出頻率很低時(shí) ， 選擇頁面淘汰 ， 以備其他進(jìn)程使用 被淘汰頁面若發(fā)生修改 ， 放入已修改鏈表 ， 否則放入空閑鏈表 頁面置換算法 總結(jié) LRU算法 、 Clock算法 了解各種算法的特點(diǎn) 作業(yè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1