memory操作系統(tǒng)原理-資料下載頁
2025-05-10 18:54本頁面
【正文】 ? 一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。如指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。 167。 請求分頁技術(shù) 頁面置換算法 ? 最佳置換算法是由 Belady于 1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長 (未來 )時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。 ? 假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁 7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0，1， 7， 0， 1 167。 請求分頁技術(shù) 167。 請求分頁技術(shù) (FIFO)頁面置換算法 ? FIFO算法是最早出現(xiàn)的頁面置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中停留時間最長（年齡最老）的一頁予以淘汰 。 167。 請求分頁技術(shù) ? 為了說明 FIFO頁面置換算法相關(guān)的可能問題，考慮一下引用串： 1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5。 ? 注意到對 4個可用內(nèi)存塊的缺頁次數(shù)（ 10）比 3個內(nèi)存塊的缺頁次數(shù)（ 9）還要大。這種令人難以相信的結(jié)果稱為 Belady異?，F(xiàn)象，即缺頁次數(shù)隨內(nèi)存塊增加而增加。 167。 請求分頁技術(shù) (LRU)置換算法 ? 最近最久未使用置換算以“最近的過去”作為“不久將來”的近似，選擇最近一段時間內(nèi)最久沒有使用的頁面淘汰掉。它的實質(zhì)是：當需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以淘汰 。 167。 請求分頁技術(shù) 4. LRU的近似算法 （ 1）附加引用位算法 ? 通過在規(guī)定時間間隔里記錄引用位，能獲得額外順序信息?？梢詾槲挥趦?nèi)存中的每個頁表中的每一頁保留一個 8 bit的字節(jié)。在規(guī)定的時間間隔（如，每 100ms）內(nèi)，時鐘定時器產(chǎn)生中斷并將控制權(quán)交給操作系統(tǒng)。操作系統(tǒng)把每個頁的引用位轉(zhuǎn)移到其 8 bit字節(jié)的高位，而將其他位右移，并拋棄最低位。這些 8 bit移位寄存器包含著該頁在最近 8個時間周期內(nèi)的使用情況。如果移位寄存器含有 00000000，那么該頁在 8個時間周期內(nèi)沒有使用；如果移位寄存器的值為 11111111，那么該頁在過去每個周期內(nèi)都至少使用過一次。 ? 具有值為 11000100的移位寄存器的也要比值為 01110111的頁使用更為頻繁。如果將這 8 bit字節(jié)作為無符號整數(shù)，那么具有最小值的頁為LRU頁，可以被置換出去。如果這個數(shù)字不惟一，可以置換所有具有最小值的頁或在這些頁之間采用 FIFO來選擇替換。 167。 請求分頁技術(shù) （ 2）第二次機會置換法 第二次機會置換法 （ Second Chance Page Replacement, SCR）是對 FIFO算法的改進 ， 以避免把經(jīng)常使用的頁面置換出去 。當選擇某一頁面置換時 ， 就檢查最老頁面的引用位：如果是0， 就立即淘汰該頁；如果該引用位是 1， 就給它第二次機會 ，并選擇下一個 FIFO頁 。 當一個頁獲得第二次機會時 ， 其引用位清零 ， 到達時間設(shè)為當前時間 。 因此 ， 獲得第二次機會的頁 ， 在所有其他頁置換 （ 或獲得第二次機會 ） 之前 ， 是不會被置換的 。 另外 ， 如果一個頁經(jīng)常使用 ， 它的引用位總保持為 1， 那么它就不會被置換 。 167。 請求分頁技術(shù) （ 3）改進型二次機會置換法 由訪問位 A和修改位 M可以組合成下面四種類型的頁面： ? 1類 (A=0, M=0)：表示該頁最近既未被訪問，又未被修改， ? 2類 (A=0, M=1)：表示該頁最近未被訪問，但已被修改， ? 3類 (A=1, M=0)：最近已被訪問，但未被修改，該頁有可 ? 4類 (A=1, M=1)：最近已被訪問且被修改，該頁可能再被訪問。 167。 請求分頁技術(shù) 在進行頁面置換時，需要同時檢查訪問位和修改位，以確定該頁是四類頁面中的那一種。其執(zhí)行過程可分成以下三步： ? 從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找 A=0且 M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位 A ? 如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找 A=0且 M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置 0 ? 如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù) 0。然后重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能找到被淘汰的頁。 167。 請求分頁技術(shù) 例題分析： 例 1: 某頁式虛擬存儲管理系統(tǒng)的物理空間為 3K，頁面大小為 1K，一進程按下列地址順序引用內(nèi)存單元：363 363 11 358 289 36 2141700、 214 320 0、 110 1100。如果上述數(shù)字均為十進制，而內(nèi)存尚未裝入任何頁，試計算采用OPT、 LRU和 FIFO頁面置換算法的缺頁次數(shù)。 167。 請求分頁技術(shù) 例 2:內(nèi)存分配一頁，初始時矩陣數(shù)據(jù)均不在內(nèi)存；頁面大小為 128個整數(shù)；矩陣 A128X128按行存放。這兩個程序執(zhí)行時分別會產(chǎn)生多少次缺頁中斷？ 程序編制方法 1： for j:=1 to 128 for i:=1 to 128 A[i,j]:=0。 程序編制方法 2： for i:=1 to 128 for j:=1 to 128 A[i,j]:=0。 167。 請求分頁技術(shù) ?在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為 顛簸或抖動。 ?原因： ? 頁面淘汰算法不合理 ? 分配給進程的物理頁面數(shù)太少 重點概念和內(nèi)容提示 ? 地址映射、虛擬地址空間、絕對地址空間、靜態(tài)重定位和動態(tài)重定位、覆蓋、交換、虛擬存儲器、缺頁中斷、頁表和段表 ? 可變分區(qū)的放置算法 ? 分頁存儲管理的原理和地址變換 ? 分段存儲管理的原理和地址映射 ? 請求分頁的原理和頁面置換算法 源碼網(wǎng)： Thank You Very Much!
公司管理相關(guān)推薦
鄂ICP備17016276號-1