第5章虛擬存儲(chǔ)器

1、v 5.1 虛擬存儲(chǔ)器概述虛擬存儲(chǔ)器概述v 5.2 請(qǐng)求分頁存儲(chǔ)管理方式請(qǐng)求分頁存儲(chǔ)管理方式v 5.3 頁面置換算法頁面置換算法v 5.4 “抖動(dòng)抖動(dòng)”與工作集與工作集v 5.5 請(qǐng)求分段存儲(chǔ)管理方式請(qǐng)求分段存儲(chǔ)管理方式1v 物理存儲(chǔ)器的結(jié)構(gòu)是個(gè)一維的線性空間，容量是有限的。物理存儲(chǔ)器的結(jié)構(gòu)是個(gè)一維的線性空間，容量是有限的。v 物理存儲(chǔ)器管理方式的特征：物理存儲(chǔ)器管理方式的特征： 一次性一次性：程序要全部一次性裝入內(nèi)存后才能運(yùn)行：程序要全部一次性裝入內(nèi)存后才能運(yùn)行 駐留性駐留性：程序裝入內(nèi)存后，一直駐留在內(nèi)存中，直至作：程序裝入內(nèi)存后，一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)速。業(yè)運(yùn)行結(jié)速。v 用戶程

2、序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時(shí)候要大得多。量大，有時(shí)候要大得多。v 如何將大于物理內(nèi)存容量的用戶程序裝入運(yùn)行？這就是如何將大于物理內(nèi)存容量的用戶程序裝入運(yùn)行？這就是提出研究虛擬存儲(chǔ)器的原因，或稱為虛擬存儲(chǔ)技術(shù)發(fā)展提出研究虛擬存儲(chǔ)器的原因，或稱為虛擬存儲(chǔ)技術(shù)發(fā)展的原動(dòng)力。的原動(dòng)力。2 指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲(chǔ)區(qū)域的指令地址或操作數(shù)地址分別局限于一定的存儲(chǔ)區(qū)域中。又可細(xì)分時(shí)間局部性和空間局部性。中。又可細(xì)分時(shí)間局部性和空間局部性

3、。v時(shí)間局限性時(shí)間局限性 一條指令被執(zhí)行了，則在不久的將來它可能再被一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行。執(zhí)行。v空間局限性空間局限性 若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)，與該若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)，與該存儲(chǔ)單元相鄰的單元可能被使用。存儲(chǔ)單元相鄰的單元可能被使用。3v 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 是采用是采用請(qǐng)求調(diào)入功能請(qǐng)求調(diào)入功能和和置換功能置換功能，把內(nèi)存與外存把內(nèi)存與外存有機(jī)的結(jié)合起來使用，從邏輯上有機(jī)的結(jié)合起來使用，從邏輯上為用戶提供一個(gè)比物為用戶提供一個(gè)比物理主存容量大得多的，可尋址的一種理主存容量大得多的，可尋址的一種“主存儲(chǔ)器主存儲(chǔ)器” ，這就是虛存。這就是虛

4、存。v 虛擬存儲(chǔ)器的容量虛擬存儲(chǔ)器的容量 是有限的；是有限的； 由內(nèi)存容量和外存容量之和所決定，受計(jì)算機(jī)的由內(nèi)存容量和外存容量之和所決定，受計(jì)算機(jī)的地址結(jié)構(gòu)限制。地址結(jié)構(gòu)限制。 以以CPU時(shí)間和外存空間換取昂貴內(nèi)存空間，這是時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。4v常規(guī)存儲(chǔ)器的特征常規(guī)存儲(chǔ)器的特征 一次性一次性 駐留性駐留性v虛擬存儲(chǔ)器特征虛擬存儲(chǔ)器特征 多次性多次性 對(duì)換性對(duì)換性 虛擬性虛擬性5v實(shí)現(xiàn)虛擬存儲(chǔ)器必須解決好以下有關(guān)問題實(shí)現(xiàn)虛擬存儲(chǔ)器必須解決好以下有關(guān)問題 主存輔存統(tǒng)一管理問題主存輔存統(tǒng)一管理問題 邏輯地址到物理地址的轉(zhuǎn)換問題邏輯

5、地址到物理地址的轉(zhuǎn)換問題 部分裝入和部分對(duì)換問題部分裝入和部分對(duì)換問題v虛擬存儲(chǔ)管理主要采用以下技術(shù)實(shí)現(xiàn)虛擬存儲(chǔ)管理主要采用以下技術(shù)實(shí)現(xiàn) 請(qǐng)求分頁存儲(chǔ)管理請(qǐng)求分頁存儲(chǔ)管理 請(qǐng)求分段存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理6v 基本原理基本原理 在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入部分頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它入部分頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁面。頁面。 當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面。據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面。

6、例例v 怎樣才能發(fā)現(xiàn)頁面不在內(nèi)存中呢怎樣才能發(fā)現(xiàn)頁面不在內(nèi)存中呢? ?怎樣處理這種情況呢怎樣處理這種情況呢? ? 采用的辦法是：擴(kuò)充頁表的內(nèi)容，增加駐留標(biāo)志位采用的辦法是：擴(kuò)充頁表的內(nèi)容，增加駐留標(biāo)志位和頁面輔存的地址等信息。通過產(chǎn)生缺頁中斷來處理和頁面輔存的地址等信息。通過產(chǎn)生缺頁中斷來處理. .7前進(jìn)前進(jìn)82022-5-8151413121110987654321060K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-

7、32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虛地址空間虛地址空間物理地址空間物理地址空間 虛頁虛頁頁框頁框返回返回v 頁號(hào)、內(nèi)存塊號(hào)、狀態(tài)位、外存地址、訪問位、修改位頁號(hào)、內(nèi)存塊號(hào)、狀態(tài)位、外存地址、訪問位、修改位 狀態(tài)位（中斷位）：表示該頁是在內(nèi)存還是在外存狀態(tài)位（中斷位）：表示該頁是在內(nèi)存還是在外存 訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）決定） 修改位：查看此頁是否在內(nèi)存中被修改過修改位：查看此頁是否在內(nèi)存中被修改過9頁號(hào)頁號(hào)狀態(tài)位狀態(tài)位輔存地址輔存地址訪問位訪問位 修改位修

8、改位物理塊號(hào)物理塊號(hào)101 11 10 00 01 11 11 10 00 00 00 00 00 01 11 1狀態(tài)位狀態(tài)位 在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生在內(nèi)存，則產(chǎn)生缺頁中斷缺頁中斷。操作系統(tǒng)接到此中斷信號(hào)。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存。存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存。此時(shí)應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成喚醒）此時(shí)應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成喚醒）如果內(nèi)存中有空閑塊，則分配一個(gè)塊，將要調(diào)入的如果內(nèi)存中有空閑塊，則分

9、配一個(gè)塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)頁表項(xiàng)目的駐留位頁裝入該塊，并修改頁表中相應(yīng)頁表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào)及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘若此時(shí)內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）汰頁在內(nèi)存期間被修改過，則要將其寫回外存）11 缺頁中斷和一般中斷都是中斷。缺頁中斷和一般中斷都是中斷。v 相同點(diǎn)：相同點(diǎn)： 保護(hù)現(xiàn)場保護(hù)現(xiàn)場 、中斷處理、中斷處理、 恢復(fù)現(xiàn)場恢復(fù)現(xiàn)場v 不同點(diǎn)：不同點(diǎn)： 一般中斷是一般中斷是一條指令完成后一條指令完成后檢查和處理中斷信號(hào)，缺頁檢查和處理中斷信號(hào)，缺頁中斷是中斷是一條指令執(zhí)行時(shí)一

10、條指令執(zhí)行時(shí)產(chǎn)生和處理中斷信號(hào)。產(chǎn)生和處理中斷信號(hào)。 缺頁中斷缺頁中斷返回到該指令的開始返回到該指令的開始重新執(zhí)行該指令，而一般重新執(zhí)行該指令，而一般中斷返回到該指令的中斷返回到該指令的下一條指令下一條指令執(zhí)行。執(zhí)行。 一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁中斷。如指令可能訪一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁中斷。如指令可能訪問多個(gè)內(nèi)存地址，這些地址在不同的頁中。問多個(gè)內(nèi)存地址，這些地址在不同的頁中。 12v 內(nèi)存分配策略分為兩種內(nèi)存分配策略分為兩種 進(jìn)程保持頁框數(shù)固定不變，稱進(jìn)程保持頁框數(shù)固定不變，稱固定分配固定分配; ;進(jìn)程分得進(jìn)程分得的頁框數(shù)可變，稱的頁框數(shù)可變，稱可變分配可變分配。v 固定分配固定

11、分配 進(jìn)程創(chuàng)建時(shí)，根據(jù)進(jìn)程類型和程序員的要求決定進(jìn)程創(chuàng)建時(shí)，根據(jù)進(jìn)程類型和程序員的要求決定頁框數(shù)，只要有一個(gè)缺頁中斷產(chǎn)生，進(jìn)程就會(huì)有一頁頁框數(shù)，只要有一個(gè)缺頁中斷產(chǎn)生，進(jìn)程就會(huì)有一頁被替換。即使內(nèi)存中有空閑的物理塊，也不分配給該被替換。即使內(nèi)存中有空閑的物理塊，也不分配給該進(jìn)程。進(jìn)程。v 可變分配可變分配 先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，進(jìn)程執(zhí)行先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊，進(jìn)程執(zhí)行的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進(jìn)程目前局部性多分些頁框以降低缺頁率，反之說明進(jìn)程目前局部性較好，可減少分給進(jìn)程的頁

12、框數(shù)。較好，可減少分給進(jìn)程的頁框數(shù)。13v 固定分配缺少靈活性，而可變分配的性能會(huì)更好些，固定分配缺少靈活性，而可變分配的性能會(huì)更好些，被許多操作系統(tǒng)采用。被許多操作系統(tǒng)采用。v 采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視活動(dòng)進(jìn)程的行為和進(jìn)程缺頁中斷率的情況，會(huì)增加活動(dòng)進(jìn)程的行為和進(jìn)程缺頁中斷率的情況，會(huì)增加系統(tǒng)的開銷。系統(tǒng)的開銷。14v全局置換全局置換 如果頁面置換算法的作用范圍是整個(gè)系統(tǒng)，稱全局如果頁面置換算法的作用范圍是整個(gè)系統(tǒng)，稱全局頁面置換算法，它可以在運(yùn)行進(jìn)程間動(dòng)態(tài)地分配頁頁面置換算法，它可以在運(yùn)行進(jìn)程間動(dòng)態(tài)地分配頁框。被置換的頁可以是

13、內(nèi)存中任一進(jìn)程的頁。框。被置換的頁可以是內(nèi)存中任一進(jìn)程的頁。v局部置換局部置換 如果頁面置換算法的作用范圍局限于本進(jìn)程，稱為如果頁面置換算法的作用范圍局限于本進(jìn)程，稱為局部頁面置換算法，它實(shí)際上需要為每個(gè)進(jìn)程分配局部頁面置換算法，它實(shí)際上需要為每個(gè)進(jìn)程分配固定的頁框。始終保持分配給該進(jìn)程的物理塊數(shù)不固定的頁框。始終保持分配給該進(jìn)程的物理塊數(shù)不變。變。15v 固定分配局部置換策略固定分配局部置換策略 進(jìn)程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進(jìn)程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進(jìn)程的頁面中選頁置換，保證進(jìn)程的頁框總數(shù)不變。進(jìn)程的頁面中選頁置換，保證進(jìn)程的頁框總數(shù)不變。v 策略難點(diǎn)策略難點(diǎn)

14、應(yīng)給每個(gè)進(jìn)程分配多少頁框應(yīng)給每個(gè)進(jìn)程分配多少頁框? ? 給少了，缺頁中斷率給少了，缺頁中斷率高；給多了，使內(nèi)存中能同時(shí)執(zhí)行的進(jìn)程數(shù)減少，進(jìn)高；給多了，使內(nèi)存中能同時(shí)執(zhí)行的進(jìn)程數(shù)減少，進(jìn)而造成處理器和其它設(shè)備空閑。而造成處理器和其它設(shè)備空閑。v 采用固定分配算法，系統(tǒng)把頁框分配給進(jìn)程，采用采用固定分配算法，系統(tǒng)把頁框分配給進(jìn)程，采用 平均分配平均分配 按比例分配按比例分配 優(yōu)先權(quán)分配優(yōu)先權(quán)分配16v 先每個(gè)進(jìn)程分配一定數(shù)目頁框，先每個(gè)進(jìn)程分配一定數(shù)目頁框，osos保留若干空閑頁保留若干空閑頁框，進(jìn)程發(fā)生缺頁中斷時(shí)，從系統(tǒng)空閑頁框中選一框，進(jìn)程發(fā)生缺頁中斷時(shí)，從系統(tǒng)空閑頁框中選一個(gè)給進(jìn)程，這樣產(chǎn)生

15、缺頁中斷進(jìn)程的內(nèi)存空間會(huì)逐個(gè)給進(jìn)程，這樣產(chǎn)生缺頁中斷進(jìn)程的內(nèi)存空間會(huì)逐漸增大，有助于減少系統(tǒng)的缺頁中斷次數(shù)。漸增大，有助于減少系統(tǒng)的缺頁中斷次數(shù)。v 系統(tǒng)擁有的空閑頁框耗盡時(shí)系統(tǒng)擁有的空閑頁框耗盡時(shí) ，會(huì)從內(nèi)存中選擇一，會(huì)從內(nèi)存中選擇一頁淘汰，該頁可以是內(nèi)存中任一進(jìn)程的頁面，這樣頁淘汰，該頁可以是內(nèi)存中任一進(jìn)程的頁面，這樣又會(huì)使那個(gè)進(jìn)程的頁框數(shù)減少，缺頁中斷率上升。又會(huì)使那個(gè)進(jìn)程的頁框數(shù)減少，缺頁中斷率上升。17 其實(shí)現(xiàn)要點(diǎn)如下其實(shí)現(xiàn)要點(diǎn)如下: :v 新進(jìn)程裝入主存時(shí)，根據(jù)應(yīng)用類型、程序要求，新進(jìn)程裝入主存時(shí)，根據(jù)應(yīng)用類型、程序要求，分配給一定數(shù)目頁框。分配給一定數(shù)目頁框。v 產(chǎn)生缺頁中斷時(shí)，

16、從該進(jìn)程駐留集中選一個(gè)頁面產(chǎn)生缺頁中斷時(shí)，從該進(jìn)程駐留集中選一個(gè)頁面替換。替換。v 不時(shí)重新評(píng)價(jià)進(jìn)程的分配，增加或減少分配給進(jìn)不時(shí)重新評(píng)價(jià)進(jìn)程的分配，增加或減少分配給進(jìn)程的頁框以改善系統(tǒng)性能。程的頁框以改善系統(tǒng)性能。18v何時(shí)頁面裝入主存何時(shí)頁面裝入主存 請(qǐng)求調(diào)頁策略請(qǐng)求調(diào)頁策略: :需要訪問程序和數(shù)據(jù)時(shí)，才把所在頁面裝需要訪問程序和數(shù)據(jù)時(shí)，才把所在頁面裝入主存。缺點(diǎn)是每次只調(diào)入一頁，處理缺頁中斷和調(diào)頁入主存。缺點(diǎn)是每次只調(diào)入一頁，處理缺頁中斷和調(diào)頁的系統(tǒng)開銷較大，增加磁盤的系統(tǒng)開銷較大，增加磁盤I/OI/O啟動(dòng)頻率。啟動(dòng)頻率。 預(yù)調(diào)頁策略預(yù)調(diào)頁策略: :系統(tǒng)系統(tǒng)預(yù)測(cè)預(yù)測(cè)進(jìn)程將要使用的頁面，使

17、用前預(yù)先進(jìn)程將要使用的頁面，使用前預(yù)先調(diào)入主存，每次調(diào)入若干頁面，而不是僅調(diào)一頁。缺點(diǎn)調(diào)入主存，每次調(diào)入若干頁面，而不是僅調(diào)一頁。缺點(diǎn)是如果調(diào)入的一批頁面中多數(shù)未被使用，則效率就很低是如果調(diào)入的一批頁面中多數(shù)未被使用，則效率就很低了，可見預(yù)調(diào)頁要建立在預(yù)測(cè)的基礎(chǔ)上。了，可見預(yù)調(diào)頁要建立在預(yù)測(cè)的基礎(chǔ)上。19v 缺頁中斷率缺頁中斷率 假定作業(yè)假定作業(yè)p p共計(jì)共計(jì)n n頁，系統(tǒng)分配給它的主存塊只有頁，系統(tǒng)分配給它的主存塊只有m m塊（塊（mnmn）。如果作業(yè)）。如果作業(yè)p p在運(yùn)行中成功的訪問次數(shù)在運(yùn)行中成功的訪問次數(shù)為為s s， 不成功的訪問次數(shù)為不成功的訪問次數(shù)為F F，則總的訪問次數(shù)為：，則

18、總的訪問次數(shù)為： A = S + FA = S + F 又定義：又定義：f = F / Af = F / A，稱，稱f f為缺頁中斷率。為缺頁中斷率。v 影響缺頁中斷率影響缺頁中斷率f f的因素有：的因素有： (1)(1)主存物理塊數(shù)主存物理塊數(shù) (2)(2)頁面大小頁面大小 (3)(3)程序的編制方法程序的編制方法 (4)(4)頁面置換算法頁面置換算法20 程序要將程序要將128128的數(shù)組置的數(shù)組置“0”。分給的主存只一塊，頁。分給的主存只一塊，頁面尺寸為每頁面尺寸為每頁128個(gè)字，數(shù)組中的元素每行存放在一頁中。若程個(gè)字，數(shù)組中的元素每行存放在一頁中。若程序如下：序如下： Var A: a

19、rray1.128 of array 1.128 of integer; for j := 1 to 128 do for i := 1 to 128 do Aij:=0 總共產(chǎn)生（總共產(chǎn)生（128*1281）次缺頁中斷。）次缺頁中斷。 如果重新編制程序如下：如果重新編制程序如下： Var A: array1.128 of array1.128 of integer; for i := 1 to128 do for j:= 1 to 128 do Aij := 0 總共產(chǎn)生（總共產(chǎn)生（1281）次缺頁中斷。）次缺頁中斷。21 當(dāng)要索取一頁面并送入到全滿的內(nèi)存中時(shí)，必當(dāng)要索取一頁面并送入到全滿的

20、內(nèi)存中時(shí)，必須把已在內(nèi)存中的某一頁淘汰掉。用來選擇淘汰哪須把已在內(nèi)存中的某一頁淘汰掉。用來選擇淘汰哪一頁的規(guī)則叫做置換算法。一頁的規(guī)則叫做置換算法。v最佳置換算法（最佳置換算法（OPT）v先進(jìn)先出頁面置換算法（先進(jìn)先出頁面置換算法（FIFO）v最近最久未使用算法（最近最久未使用算法（LRU）22 基本思想：淘汰以后不再需要的或最遠(yuǎn)的將來才會(huì)基本思想：淘汰以后不再需要的或最遠(yuǎn)的將來才會(huì)用到的頁面?？捎脕碜鳛楹饬扛鞣N具體算法的標(biāo)準(zhǔn)。用到的頁面?？捎脕碜鳛楹饬扛鞣N具體算法的標(biāo)準(zhǔn)。 【例例】采用固定分配局部置換策略，某程序在內(nèi)存采用固定分配局部置換策略，某程序在內(nèi)存中分配三個(gè)塊，訪問頁的走向?yàn)橹蟹峙淙?/p>

21、個(gè)塊，訪問頁的走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，計(jì)算缺頁次數(shù)和，計(jì)算缺頁次數(shù)和缺頁中斷率缺頁中斷率，假設(shè)開，假設(shè)開始時(shí)所有頁均不在內(nèi)存。始時(shí)所有頁均不在內(nèi)存。OPT 4 3 2 1 4 3 5 4 3 2 1 5塊塊1 4 4 4 4 4 4 4 4 4 2 1 1塊塊2 3 3 3 3 3 3 3 3 3 3 3塊塊3 2 1 1 1 5 5 5 5 5 5 x x x x x x x 共缺頁中斷共缺頁中斷7次次缺頁中斷率缺頁中斷率=7/12=58.33%23 基本思想：淘汰最先調(diào)入主存的那一頁，或者說在主基本思想：淘汰最先調(diào)入主存的那一頁，或者說在主存中駐留時(shí)間最長的那

22、一頁（常駐的除外）。存中駐留時(shí)間最長的那一頁（常駐的除外）。 【例例】采用固定分配局部置換策略，某程序在內(nèi)存中采用固定分配局部置換策略，某程序在內(nèi)存中分配三個(gè)塊，訪問頁的走向?yàn)榉峙淙齻€(gè)塊，訪問頁的走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，計(jì)算缺頁次數(shù)，假設(shè)開始時(shí)所有頁均不在，計(jì)算缺頁次數(shù)，假設(shè)開始時(shí)所有頁均不在內(nèi)存。內(nèi)存。FIFO 4 3 2 1 4 3 5 4 3 2 1 5塊塊1 4 4 4 1 1 1 5 5 5 5 5 5塊塊2 3 3 3 4 4 4 4 4 2 2 2塊塊3 2 2 2 3 3 3 3 3 1 1 x x x x x x x x x 共缺頁中斷共缺頁中斷

23、9次，缺頁中斷率次，缺頁中斷率=9/12=75%24這種算法實(shí)現(xiàn)簡單，但會(huì)淘汰經(jīng)常使用的頁面這種算法實(shí)現(xiàn)簡單，但會(huì)淘汰經(jīng)常使用的頁面 基本思想：根據(jù)程序局部性原理，那些剛被使用過的頁面，可能基本思想：根據(jù)程序局部性原理，那些剛被使用過的頁面，可能馬上還要被使用，而在較長時(shí)間里未被使用的頁面，可能不會(huì)馬上使馬上還要被使用，而在較長時(shí)間里未被使用的頁面，可能不會(huì)馬上使用到。用到。當(dāng)需要淘汰某一頁時(shí)，算法選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)當(dāng)需要淘汰某一頁時(shí)，算法選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒有使用過的頁先淘汰。最久沒有使用過的頁先淘汰。LRU 4 3 2 1 4 3 5 4 3 2 1 5塊塊1 4 4 4 1 1 1 5 5 5 2 2 2塊塊2 3 3 3 4 4 4 4 4 4 1 1塊塊3 2 2 2 3 3 3 3 3 3 5 x x x x x x x x x x共缺頁中斷共缺頁中斷10次次缺頁中斷率缺頁中斷率=10/12=83.33%25v基本原理基本原理 分段式虛擬存儲(chǔ)系統(tǒng)把作業(yè)的所有分段的副本分段式虛擬存儲(chǔ)系統(tǒng)把作業(yè)的所有分段的副本都存放