




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第四章 存儲(chǔ)器管理,4.1 程序的裝入和鏈接 4.2 連續(xù)分配方式 4.3 基本分頁存儲(chǔ)管理方式 4.4 基本分段存儲(chǔ)管理方式 4.5 虛擬存儲(chǔ)器的基本概念 4.6 請(qǐng)求分頁存儲(chǔ)管理方式 4.7 頁面置換算法,上節(jié)回顧,虛擬存儲(chǔ)器: 定義:P126 特征:多次性、對(duì)換性、虛擬性 P127 請(qǐng)求分頁存儲(chǔ)管理: 硬件支持:頁表機(jī)制、缺頁中斷機(jī)構(gòu)、地址變換機(jī)構(gòu) 物理塊分配策略與算法,4.6.2 內(nèi)存分配策略和分配算法,1. 最小物理塊數(shù)的確定,2. 物理塊的分配策略,在請(qǐng)求分頁系統(tǒng)中,可采取兩種內(nèi)存分配策略,即固定和可變分配策略。在進(jìn)行置換時(shí), 也可采取兩種策略,即全局置換和局部置換。于是可組合出以
2、下三種適用的策略。 1) 固定分配局部置換(Fixed Allocation, Local Replacement) 2) 可變分配全局置換(Variable Allocation, Global Replacement) 3) 可變分配局部置換(Variable Allocation, Local Replacemen,3. 物理塊分配算法,1) 平均分配算法 這是將系統(tǒng)中所有可供分配的物理塊,平均分配給各個(gè)進(jìn)程。 例如,當(dāng)系統(tǒng)中有100個(gè)物理塊,有5個(gè)進(jìn)程在運(yùn)行時(shí),每個(gè)進(jìn)程可分得20個(gè)物理塊。這種方式貌似公平,但實(shí)際上是不公平的,因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個(gè)進(jìn)程其大小為200頁
3、,只分配給它20個(gè)塊,這樣,它必然會(huì)有很高的缺頁率;而另一個(gè)進(jìn)程只有10頁,卻有10個(gè)物理塊閑置未用。,2) 按比例分配算法 這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個(gè)進(jìn)程,每個(gè)進(jìn)程的頁面數(shù)為Si,則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為: 又假定系統(tǒng)中可用的物理塊總數(shù)為m,則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi,將有: b應(yīng)該取整,它必須大于最小物理塊數(shù)。,3) 考慮優(yōu)先權(quán)的分配算法 在實(shí)際應(yīng)用中,為了照顧到重要的、緊迫的作業(yè)能盡快地完成, 應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分:一部分按比例地分配給各進(jìn)程;另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán),適當(dāng)?shù)卦黾?/p>
4、其相應(yīng)份額后,分配給各進(jìn)程。在有的系統(tǒng)中,如重要的實(shí)時(shí)控制系統(tǒng),則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。,4.6.3 調(diào)頁策略,1. 何時(shí)調(diào)入頁面,2. 從何處調(diào)入頁面,在請(qǐng)求分頁系統(tǒng)中的外存分為兩部分:用于存放文件的文件區(qū)和用于存放對(duì)換頁面的對(duì)換區(qū)。通常,由于對(duì)換區(qū)是采用連續(xù)分配方式,而事件是采用離散分配方式,故對(duì)換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣,每當(dāng)發(fā)生缺頁請(qǐng)求時(shí),系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存,可分成如下三種情況:,3. 頁面調(diào)入過程 頁面未在內(nèi)存時(shí),向CPU發(fā)出缺頁中斷 中斷處理程序保留CPU環(huán)境, 轉(zhuǎn)入缺頁中斷處理程序。 該程序通過查找頁表,得到該頁在外存的物理塊 能容納新頁
5、,啟動(dòng)磁盤I/O將缺頁調(diào)入內(nèi)存,修改頁表。 內(nèi)存已滿,選出準(zhǔn)備換出的頁面 如果此頁已被修改, 將它寫回磁盤 把所缺的頁調(diào)入內(nèi)存, 修改頁表中的相應(yīng)表項(xiàng),存在位為“1”,并將此頁表項(xiàng)寫入快表中。 形成所要訪問數(shù)據(jù)的物理地址,再去訪問內(nèi)存數(shù)據(jù)。,4.7 頁面置換算法,最佳置換算法 先進(jìn)先出算法 LRU算法 Clock算法 其他算法,頁面置換算法的設(shè)計(jì)目標(biāo),具有較低的頁面更換頻率 換出以后不再訪問的頁面或者較長時(shí)間不再使用的頁面,4.7.1 最佳置換算法和先進(jìn)先出置換算法,1. 最佳(Optimal)置換算法 Belady于1966年提出的一種理論上的算法,思想是選擇的被淘汰頁面以后將永不使用,或者
6、在最長(未來)時(shí)間內(nèi)不再被訪問。,假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊, 并考慮有以下的頁面號(hào)引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 進(jìn)程運(yùn)行時(shí), 先將7,0,1三個(gè)頁面裝入內(nèi)存。 以后, 當(dāng)進(jìn)程要訪問頁面2時(shí), 將會(huì)產(chǎn)生缺頁中斷。此時(shí)OS根據(jù)最佳置換算法, 將選擇頁面7予以淘汰。,1. 最佳(Optimal)置換算法優(yōu)缺點(diǎn),選擇被置換的頁面將是不再訪問的或者較長時(shí)間不再使用的 優(yōu)點(diǎn):可保證最低的缺頁率 缺點(diǎn):不可能很真正實(shí)現(xiàn),只可作為其他算法的評(píng)價(jià)參考 特點(diǎn):“往后看”,看未來,因此不可行,2. 先進(jìn)先出(FIFO)頁面置換算法,淘汰最先進(jìn)入內(nèi)存
7、的頁面,即選擇內(nèi)存駐留時(shí)間最長的頁面。 需要使用替換指針,2. 先進(jìn)先出(FIFO)頁面置換算法優(yōu)缺點(diǎn),優(yōu)點(diǎn):算法簡單 缺點(diǎn):性能不佳 特點(diǎn):只看“先后順序”,4.7.2 最近最久未使用(LRU)置換算法,1. 算法描述,選擇最近最久未使用的頁面。 使用訪問字段,1. LRU置換算法,假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊, 并考慮有以下的頁面號(hào)引用串:,1. LRU置換算法優(yōu)缺點(diǎn),優(yōu)點(diǎn):性能較好 缺點(diǎn):需要較多硬件支持 特點(diǎn): “向前看”,看過去的使用情況,2. LRU置換算法的硬件支持,LRU算法需要的元素 1、進(jìn)程各個(gè)頁面有多久未被訪問 2、如何快速找到最近最久未使用的頁面,1) 移位寄存器
8、1、使用移位寄存器記錄某進(jìn)程在內(nèi)存中每頁的使用情況 2、數(shù)據(jù)格式: R=Rn-1Rn-2Rn-3 R2R1R0 3、頁面被訪問一次,最高位Rn-1置1,每隔一定時(shí)間,寄存器右移一位 4、R值最小的頁面是被置換頁面,某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況,2) 棧,1、采用特殊的棧來保存當(dāng)前使用的各個(gè)頁面號(hào) 2、棧頂保留的是最新被訪問的頁 3、棧底保留的是最久未被訪問的頁,即置換目標(biāo),練習(xí),在一個(gè)請(qǐng)求分頁系統(tǒng)中,假定系統(tǒng)分配給一個(gè)進(jìn)程的內(nèi)存塊數(shù)為3,進(jìn)程的頁面走向?yàn)?,3,2,1,5,2,4,5,3,2,5,2。試用最近最久未使用置換算法(LRU),請(qǐng)畫圖表示訪問過程中發(fā)生的頁面置換過程,并計(jì)算缺
9、頁次數(shù)。(假定開始時(shí),物理塊為空,每次調(diào)入頁面都作為一次缺頁處理),4.7.3 Clock置換算法,1. 簡單的Clock置換算法,Clock置換算法是LRU算法的近似算法,也稱為最近未用算法。在簡單的Clock算法中,為每頁設(shè)置一訪問位,當(dāng)被訪問則設(shè)置為1,未訪問為0。,1. 簡單的Clock置換算法,1類(A=0, M=0):最近未被訪問,又未被修改,最佳淘汰頁。 2類(A=0, M=1):最近未被訪問,但已被修改頁。 3類(A=1, M=0):最近已被訪問, 但未被修改。 4類(A=1, M=1):最近已被訪問且被修改,最不應(yīng)淘汰頁。,訪問位A和修改位M可以組合成下面四種類型的頁面,1、
10、從當(dāng)前指針位置開始掃描循環(huán)隊(duì)列,尋找第1類頁面, 不改變?cè)L問位A。 2、第一步失敗,尋找第2類頁面,將所遇到的第一個(gè)這類頁面作為淘汰頁。 將所有掃描過的頁面的訪問位A都置0。 3、第二步也失敗,重復(fù)第一步,如果仍失敗,必要時(shí)再重復(fù)第二步,此時(shí)就一定能找到被淘汰的頁。,執(zhí)行過程可分成以下三步:,改進(jìn)型Clock置換算法優(yōu)缺點(diǎn),優(yōu)點(diǎn):減少了磁盤的I/O操作次數(shù) 缺點(diǎn):可能需要幾輪掃描,增加了系統(tǒng)開銷 特點(diǎn):使用兩個(gè)指標(biāo)判斷,訪問位+修改位,練習(xí),已知某進(jìn)程有4頁在內(nèi)存,頁碼為0,1,2,3,其A、M位分別為(1,1)(1,1),(0,1),(1,1),當(dāng)前指針指向2號(hào)頁,若采用改進(jìn)型Clock置換算法,選擇哪頁淘汰?選擇完成后,四個(gè)頁的A、M位分別為多少?,4.7.4 其它置換算法,最少使用(LFU: Least Frequently Used)置換算法 對(duì)每個(gè)頁面設(shè)置一個(gè)字段(移位寄存器),用來記錄頁面被訪問的頻率 若用移位寄存器實(shí)現(xiàn)算法,LFU與L
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 設(shè)施維護(hù)安全管理辦法
- 福建高速超限管理辦法
- 營運(yùn)企業(yè)計(jì)劃管理辦法
- 私立醫(yī)院捐贈(zèng)管理辦法
- 肩頸護(hù)理課件
- 醫(yī)院全員應(yīng)急培訓(xùn)課件
- 外聯(lián)禮儀培訓(xùn)課件
- 高中自助招生數(shù)學(xué)試卷
- 二零一九小升初數(shù)學(xué)試卷
- 高中提分?jǐn)?shù)學(xué)試卷
- 二手車輛購買協(xié)議范本
- 制造業(yè)暑假工合同
- 2024年湖北省中考英語試題(附答案)
- 瀘州老窖“濃香文釀杯”企業(yè)文化知識(shí)競賽考試題庫大全-上(單選題)
- 2024年4月自考02613單片機(jī)與接口技術(shù)試題
- 遷往各地的隴西李氏
- 1000MW超超臨界火電機(jī)組深度調(diào)峰研究
- 福建省公共建筑能耗標(biāo)準(zhǔn)
- 醫(yī)?;鸨O(jiān)管知識(shí)考試題庫300題(含答案)
- 冷庫pcuocu應(yīng)用培訓(xùn)
- 源網(wǎng)荷儲(chǔ)一體化綠色供電工業(yè)園區(qū)示范項(xiàng)目環(huán)評(píng)可研資料環(huán)境影響
評(píng)論
0/150
提交評(píng)論