操作系統(tǒng)課程ppt課件(2)(編輯修改稿)
2025-06-08 08:20 本頁面
【文章內(nèi)容簡(jiǎn)介】 區(qū)空間。 ⑵ 系統(tǒng)缺少足夠的對(duì)換區(qū)空間。 ⑶ UNIX方式。 頁面調(diào)入策略 每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)（存在位為 “ 0” ），便向 CPU發(fā)出一缺頁中斷，中斷處理程序首先保留 CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤 I/O，將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法，從內(nèi)存中選出一頁準(zhǔn)備換出；如果該頁未被修改過（修改位為 “ O” ），可不必將該頁寫回磁盤；但如果此頁已被修改（修改位為 “ 1” ），則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為 “ 1” ，并將此頁表項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個(gè)頁面的調(diào)入過程對(duì)用戶是透明的。 頁面調(diào)入策略返回 虛擬存儲(chǔ)器3 頁面置換算法 最佳置換算法和先進(jìn)先出置換算法 由 Belady于 1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(zhǎng) (未來 )時(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予以淘汰。 最佳置換算法和先進(jìn)先出置換算法 置換時(shí)，選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁并予以淘汰。 最近最久未使用和最少使用置換算法 選擇最后一次訪問時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁并淘汰之。即淘汰沒有使用的時(shí)間最長(zhǎng)的頁。實(shí)現(xiàn)代價(jià)很高（時(shí)間戳或硬件方法）。 最近最久未使用和最少使用置換算法 2. LRU置換算法的硬件支持 ⑴ 寄存器 ? 為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為 : R=Rn1Rn2Rn3 … R 2R1R0 。 最近最久未使用和最少使用置換算法 2. LRU置換算法的硬件支持 （ 2）棧 ? 最近最久未使用和最少使用置換算法 LFU置換算法 選擇在最近時(shí)期使用最少的頁面作為淘汰頁。 LFU置換算法的頁面訪問圖，與 LRU置換算法的訪問圖完全相同；或者說，利用這樣一套硬件既可實(shí)現(xiàn) LRU算法，又可實(shí)現(xiàn) LFU算法。 這種算法并不能真正反映出頁面的使用情況，因?yàn)樵诿恳粫r(shí)間間隔內(nèi)，只是用寄存器的一位來記錄頁的使用情況，因此，在該時(shí)間間隔內(nèi)，對(duì)某頁訪問一次和訪問 1000次是完全等效的。 Clock置換算法 Clock置換算法 Clock置換算法 Clock置換算法 ★ 由訪問位 A和修改位 M可以組合成下面四種類型的頁面： 1類 (A=0, M=0): 該頁最近既未被訪問，又未被修改，是最佳淘汰頁。 ? 2類 (A=0, M=1)：該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。 ? 3類 (A=1, M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。 4類 (A=1, M=1): 最近已被訪問且被修改， 該頁可能再被訪問。 ★ 其執(zhí)行過程可分成以下三步： ? (1)從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找 A=0且 M=0的第一類頁面，將所遇到的第一個(gè)頁面作為所選中的淘汰頁。在第一次掃描期間不改變?cè)L問位 A。 ? (2)如果第一步失敗，則開始第二輪掃描，尋找 A=0且 M=1的第二類頁面，將所遇到的第一個(gè)這類
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1