Background(背景)

1、Silberschatz, Galvin, and Gagne 1999 10.1Applied Operating System ConceptsModule 10: Virtual MemoryBackground（背景）背景）Demand Paging（請(qǐng)求頁(yè)式）請(qǐng)求頁(yè)式） Performance of Demand Paging（請(qǐng)求頁(yè)式的性請(qǐng)求頁(yè)式的性能）能） Page Replacement（頁(yè)置換）頁(yè)置換） Page-Replacement Algorithms（頁(yè)置換算法）頁(yè)置換算法） Allocation of Frames （頁(yè)框的分配）頁(yè)框的分配） Thrashing（顛

2、簸）顛簸） Other Considerations（其他考慮）其他考慮）Demand Segmenation（請(qǐng)求段式）請(qǐng)求段式）Silberschatz, Galvin, and Gagne 1999 10.2Applied Operating System ConceptsBackgroundVirtual memory separation of user logical memory from physical memory.（虛擬內(nèi)存虛擬內(nèi)存物理內(nèi)存和用戶邏輯內(nèi)存的區(qū)分）物理內(nèi)存和用戶邏輯內(nèi)存的區(qū)分） 局部性原理局部性原理(principle of locality) 時(shí)間局部性，

3、空間局部性時(shí)間局部性，空間局部性 Only part of the program needs to be in memory for execution （只有部分運(yùn)行的程序需要在內(nèi)存中）只有部分運(yùn)行的程序需要在內(nèi)存中）.Logical address space can therefore be much larger than physical address space（因此，邏輯地址空間能夠比物理地址空因此，邏輯地址空間能夠比物理地址空間大）間大）. Need to allow pages to be swapped in and out（必須允許必須允許頁(yè)面能夠被換入和換出）頁(yè)面能

4、夠被換入和換出）.Virtual memory can be implemented via（虛擬內(nèi)存能夠通過以下虛擬內(nèi)存能夠通過以下方法來(lái)實(shí)現(xiàn)）方法來(lái)實(shí)現(xiàn)）: Demand paging （請(qǐng)求頁(yè)式）請(qǐng)求頁(yè)式） Demand segmentation（請(qǐng)求段式）請(qǐng)求段式）Silberschatz, Galvin, and Gagne 1999 10.3Applied Operating System Concepts問題的提出問題的提出為了在內(nèi)存空間運(yùn)行超過內(nèi)存總?cè)轂榱嗽趦?nèi)存空間運(yùn)行超過內(nèi)存總?cè)萘康拇笞鳂I(yè)，或者同時(shí)運(yùn)行大量量的大作業(yè)，或者同時(shí)運(yùn)行大量作業(yè)，解決的方法是作業(yè)，解決的方法是從邏輯

5、上擴(kuò)從邏輯上擴(kuò)充內(nèi)存容量充內(nèi)存容量，這就是虛擬存儲(chǔ)技，這就是虛擬存儲(chǔ)技術(shù)所要解決的主要問題術(shù)所要解決的主要問題Silberschatz, Galvin, and Gagne 1999 10.4Applied Operating System Concepts程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需內(nèi)存，而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)交換要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)交換以以CPU時(shí)間時(shí)間和和外存空間外存空間換取昂貴內(nèi)存空間，換

6、取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)虛擬存儲(chǔ)器的基本思想虛擬存儲(chǔ)器的基本思想Silberschatz, Galvin, and Gagne 1999 10.5Applied Operating System Concepts虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念局部性原理局部性原理 在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以下幾點(diǎn)：局部性規(guī)律呢？原因可以歸

7、結(jié)為以下幾點(diǎn)：程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，大多數(shù)程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。仍是順序執(zhí)行的。子程序調(diào)用子程序調(diào)用將會(huì)使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分將會(huì)使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過5。程序中存在許多程序中存在許多循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對(duì)程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)連續(xù)的存儲(chǔ)空間的處理，如對(duì)連續(xù)的存儲(chǔ)空間數(shù)組的訪問，往往局限于很小的范圍內(nèi)。數(shù)

8、組的訪問，往往局限于很小的范圍內(nèi)。Silberschatz, Galvin, and Gagne 1999 10.6Applied Operating System Concepts時(shí)間局部性時(shí)間局部性：如果程序中的某條指令一旦：如果程序中的某條指令一旦執(zhí)行，則不久的將來(lái)該指令可能再次被執(zhí)執(zhí)行，則不久的將來(lái)該指令可能再次被執(zhí)行；如果某個(gè)存儲(chǔ)單元被訪問，則不久以行；如果某個(gè)存儲(chǔ)單元被訪問，則不久以后該存儲(chǔ)單元可能再次被訪問。產(chǎn)生時(shí)間后該存儲(chǔ)單元可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量局限性的典型原因是在程序中存在著大量的循環(huán)操作。的循環(huán)操作?？臻g局部性空間局部性：一旦程序訪問

9、了某個(gè)存儲(chǔ)單：一旦程序訪問了某個(gè)存儲(chǔ)單元，則在不久的將來(lái)，其附近的存儲(chǔ)單元元，則在不久的將來(lái)，其附近的存儲(chǔ)單元也最有可能被訪問。也最有可能被訪問。 即程序在一段時(shí)間即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。內(nèi)，其典型原因是程序是順序執(zhí)行的。局部性表現(xiàn)局部性表現(xiàn)Silberschatz, Galvin, and Gagne 1999 10.7Applied Operating System Concepts虛擬存儲(chǔ)的基本原理虛擬存儲(chǔ)的基本原理根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒有必

10、要把全部作業(yè)裝入內(nèi)存，而僅，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁(yè)面或段，將那些當(dāng)前要運(yùn)行的那部分頁(yè)面或段，先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤上時(shí)留在磁盤上 Silberschatz, Galvin, and Gagne 1999 10.8Applied Operating System Concepts程序在運(yùn)行時(shí)如果它所要訪問的頁(yè)程序在運(yùn)行時(shí)如果它所要訪問的頁(yè)（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行（段）已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去；下去；如果程序所要訪問的頁(yè)（段）尚未如果程序所要訪問的頁(yè)（段）尚未調(diào)入內(nèi)存（稱為缺頁(yè)或缺段），此調(diào)入內(nèi)存

11、（稱為缺頁(yè)或缺段），此時(shí)應(yīng)利用時(shí)應(yīng)利用OSOS所提供的所提供的請(qǐng)求調(diào)頁(yè)（段請(qǐng)求調(diào)頁(yè)（段）功能，將它們調(diào)入內(nèi)存，以使進(jìn)功能，將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。程能繼續(xù)執(zhí)行下去。虛擬存儲(chǔ)的基本原理虛擬存儲(chǔ)的基本原理Silberschatz, Galvin, and Gagne 1999 10.9Applied Operating System Concepts如果內(nèi)存已滿，無(wú)法再裝入新的頁(yè)（段），如果內(nèi)存已滿，無(wú)法再裝入新的頁(yè)（段），則還須再利用頁(yè)（段）的則還須再利用頁(yè)（段）的置換功能置換功能，將內(nèi)存，將內(nèi)存中暫時(shí)不用的頁(yè)（段）調(diào)出至磁盤上，騰出中暫時(shí)不用的頁(yè)（段）調(diào)出至磁盤上，騰出足夠的內(nèi)

12、存空間后，再將所要訪問的頁(yè)（段足夠的內(nèi)存空間后，再將所要訪問的頁(yè)（段）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，）調(diào)入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個(gè)大的用戶程序在較小的內(nèi)存空間便可使一個(gè)大的用戶程序在較小的內(nèi)存空間中運(yùn)行；也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程中運(yùn)行；也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實(shí)際內(nèi)存容量大得多，人們內(nèi)存容量，將比實(shí)際內(nèi)存容量大得多，人們把這樣的存儲(chǔ)器稱為把這樣的存儲(chǔ)器稱為虛擬存儲(chǔ)器虛擬存儲(chǔ)器。虛擬存儲(chǔ)的基本原理虛擬存儲(chǔ)的基本原理Silberschatz, Galvin, and Gag

13、ne 1999 10.10Applied Operating System Concepts虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征l離散性離散性：指在內(nèi)存分配時(shí)采用離散的分配方：指在內(nèi)存分配時(shí)采用離散的分配方式，它是虛擬存儲(chǔ)器的最基本的特征。式，它是虛擬存儲(chǔ)器的最基本的特征。l多次性多次性：指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)：指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行，即在作業(yè)運(yùn)行時(shí)沒有必要將其全部裝入，行，即在作業(yè)運(yùn)行時(shí)沒有必要將其全部裝入，只須將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)只須將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可。多次性是虛擬存儲(chǔ)器最重要的特征。存即可。多次性是虛擬存儲(chǔ)器最重要的特征。l對(duì)換性對(duì)換

14、性：指允許在作業(yè)的運(yùn)行過程中在內(nèi)存：指允許在作業(yè)的運(yùn)行過程中在內(nèi)存和外存的對(duì)換區(qū)之間換進(jìn)、換出。和外存的對(duì)換區(qū)之間換進(jìn)、換出。l虛擬性虛擬性：指能夠從邏輯上擴(kuò)充內(nèi)存容量，使：指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。Silberschatz, Galvin, and Gagne 1999 10.11Applied Operating System Concepts虛擬存儲(chǔ)器實(shí)現(xiàn)方式虛擬存儲(chǔ)器實(shí)現(xiàn)方式1)請(qǐng)求分頁(yè)系統(tǒng)請(qǐng)求分頁(yè)系統(tǒng)：在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了：在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能能和頁(yè)面置

15、換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干頁(yè)（而非全部程序）的用戶程序和數(shù)據(jù)，就只裝入若干頁(yè)（而非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過調(diào)頁(yè)功能和頁(yè)面置換功能，可以啟動(dòng)運(yùn)行，以后再通過調(diào)頁(yè)功能和頁(yè)面置換功能，陸續(xù)把將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)陸續(xù)把將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面置換到外存上，置換時(shí)以頁(yè)面為單位。面置換到外存上，置換時(shí)以頁(yè)面為單位。2)請(qǐng)求分段系統(tǒng)：請(qǐng)求分段系統(tǒng)：在分段系統(tǒng)的基礎(chǔ)上，增加了在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段請(qǐng)求調(diào)段和分段置換功能和分段置換功能所形成的段式虛擬存儲(chǔ)系統(tǒng)。它允許只所形成的

16、段式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動(dòng)運(yùn)行，以后再通過調(diào)段功能和置換功能將不運(yùn)行的啟動(dòng)運(yùn)行，以后再通過調(diào)段功能和置換功能將不運(yùn)行的段調(diào)出，同時(shí)調(diào)入將要運(yùn)行的段，置換以段為單位。段調(diào)出，同時(shí)調(diào)入將要運(yùn)行的段，置換以段為單位。3)請(qǐng)求段頁(yè)式系統(tǒng)：請(qǐng)求段頁(yè)式系統(tǒng)：它是在段頁(yè)式系統(tǒng)的基礎(chǔ)上，增加了它是在段頁(yè)式系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能所形成的段頁(yè)式虛擬存儲(chǔ)系統(tǒng)請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能所形成的段頁(yè)式虛擬存儲(chǔ)系統(tǒng)。Silberschatz, Galvin, and Gagne 1999 10.12Appl

17、ied Operating System ConceptsDemand PagingBring a page into memory only when it is needed（只有只有在一個(gè)頁(yè)需要的時(shí)候才把它換入內(nèi)存）在一個(gè)頁(yè)需要的時(shí)候才把它換入內(nèi)存）. Less I/O needed（需要很少的需要很少的I/O） Less memory needed （需要很少的內(nèi)存需要很少的內(nèi)存） Faster response（快速響應(yīng)）快速響應(yīng)） More users（多用戶）多用戶）Hardware Support invalid reference（無(wú)效的訪問）無(wú)效的訪問） abort（中止中

18、止） not-in-memory（不在內(nèi)存）不在內(nèi)存） bring to memory（換換入內(nèi)存）入內(nèi)存）Silberschatz, Galvin, and Gagne 1999 10.13Applied Operating System Concepts請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式它是在純分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了它是在純分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求請(qǐng)求調(diào)頁(yè)功能調(diào)頁(yè)功能、頁(yè)面置換功能頁(yè)面置換功能所形成的頁(yè)式虛所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)，它是目前常用的一種虛擬存擬存儲(chǔ)系統(tǒng)，它是目前常用的一種虛擬存儲(chǔ)器的方式。儲(chǔ)器的方式。l取頁(yè)取頁(yè)-將哪部分裝入內(nèi)存將哪部分裝入內(nèi)存l置頁(yè)置頁(yè)-將調(diào)入的

19、頁(yè)放在什么地方將調(diào)入的頁(yè)放在什么地方l淘汰淘汰-內(nèi)存不足時(shí)，將哪些頁(yè)換出內(nèi)存內(nèi)存不足時(shí)，將哪些頁(yè)換出內(nèi)存。Silberschatz, Galvin, and Gagne 1999 10.14Applied Operating System Concepts請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持1)請(qǐng)求分頁(yè)的頁(yè)表機(jī)制請(qǐng)求分頁(yè)的頁(yè)表機(jī)制 它是在純分頁(yè)的頁(yè)表機(jī)制上形成的，由于只它是在純分頁(yè)的頁(yè)表機(jī)制上形成的，由于只將程序的一部分調(diào)入內(nèi)存，還有一部分仍在將程序的一部分調(diào)入內(nèi)存，還有一部分仍在磁盤上，故需在頁(yè)表中再增加若干項(xiàng)，供程磁盤上，故需在頁(yè)表中再增加若干項(xiàng)，供程序序(數(shù)據(jù)數(shù)據(jù))在換進(jìn)、換出時(shí)參考

20、。在請(qǐng)求分頁(yè)系在換進(jìn)、換出時(shí)參考。在請(qǐng)求分頁(yè)系統(tǒng)中的每個(gè)頁(yè)表項(xiàng)如圖所示。統(tǒng)中的每個(gè)頁(yè)表項(xiàng)如圖所示。頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位P 訪問字段A 修改位M 外存地址Silberschatz, Galvin, and Gagne 1999 10.15Applied Operating System Concepts狀態(tài)位（存在位狀態(tài)位（存在位P）：用于指示該頁(yè)是否已調(diào)入內(nèi)存，供程用于指示該頁(yè)是否已調(diào)入內(nèi)存，供程序訪問時(shí)參考。序訪問時(shí)參考。訪問字段訪問字段A：用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問的次數(shù)，或用于記錄本頁(yè)在一段時(shí)間內(nèi)被訪問的次數(shù)，或最近已有多長(zhǎng)時(shí)間未被訪問，提供給置換算法選擇換出頁(yè)面最近已有多長(zhǎng)時(shí)間未

21、被訪問，提供給置換算法選擇換出頁(yè)面時(shí)參考。時(shí)參考。修改位修改位M：表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存表示該頁(yè)在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁(yè)都在外存上保留一份副本，因此，若未被修改，中的每一頁(yè)都在外存上保留一份副本，因此，若未被修改，在置換該頁(yè)時(shí)就不需將該頁(yè)寫回到外存上，以減少系統(tǒng)的開在置換該頁(yè)時(shí)就不需將該頁(yè)寫回到外存上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁(yè)重寫到外銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁(yè)重寫到外存上，以保證外存中所保留的始終是最新副本。存上，以保證外存中所保留的始終是最新副本。外存地址外存地址：用于指出該頁(yè)在外存上的地址，通常是物

22、理塊號(hào)：用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用。，供調(diào)入該頁(yè)時(shí)使用。請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持Silberschatz, Galvin, and Gagne 1999 10.16Applied Operating System Concepts請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持2）缺頁(yè)中斷機(jī)構(gòu)）缺頁(yè)中斷機(jī)構(gòu)在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問的頁(yè)面不在內(nèi)在請(qǐng)求分頁(yè)系統(tǒng)中，每當(dāng)所要訪問的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一缺頁(yè)中斷，請(qǐng)求存時(shí)，便要產(chǎn)生一缺頁(yè)中斷，請(qǐng)求OS將所缺頁(yè)調(diào)將所缺頁(yè)調(diào)入內(nèi)存。與一般中斷的主要區(qū)別在于：入內(nèi)存。與一般中斷的主要區(qū)別在于：缺頁(yè)中斷機(jī)構(gòu)在

23、指令執(zhí)行期間產(chǎn)生和處理中斷信缺頁(yè)中斷機(jī)構(gòu)在指令執(zhí)行期間產(chǎn)生和處理中斷信號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理號(hào)，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號(hào)。中斷信號(hào)。缺頁(yè)中斷返回到該指令的開始重新執(zhí)行該指令，缺頁(yè)中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷。Silberschatz, Galvin, and Gagne 1999 10.17Applied Operating System Concepts請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)

24、中的硬件支持3)地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)，是在分頁(yè)請(qǐng)求分頁(yè)系統(tǒng)中的地址變換機(jī)構(gòu)，是在分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，再為實(shí)現(xiàn)系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，再為實(shí)現(xiàn)虛擬存儲(chǔ)器而增加了某些功能所形成的，虛擬存儲(chǔ)器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁(yè)中斷，以及從內(nèi)存中換如產(chǎn)生和處理缺頁(yè)中斷，以及從內(nèi)存中換出一頁(yè)的功能等等，下圖給出了請(qǐng)求分頁(yè)出一頁(yè)的功能等等，下圖給出了請(qǐng)求分頁(yè)系統(tǒng)的地址變換過程。系統(tǒng)的地址變換過程。Silberschatz, Galvin, and Gagne 1999 10.18Applied Operating System Concepts 缺

25、頁(yè)中斷處理缺頁(yè)中斷處理 是 否 是 是 否 產(chǎn)生缺頁(yè)中產(chǎn)生缺頁(yè)中 否否 是 斷請(qǐng)求調(diào)頁(yè)斷請(qǐng)求調(diào)頁(yè) 開始（程序請(qǐng)求訪問一頁(yè)開始（程序請(qǐng)求訪問一頁(yè))越界中斷越界中斷CPU檢索快表檢索快表頁(yè)表項(xiàng)是否在快表中？頁(yè)表項(xiàng)是否在快表中？訪問頁(yè)表訪問頁(yè)表頁(yè)是否在內(nèi)存中？頁(yè)是否在內(nèi)存中？修改快表修改快表修改訪問位和修改位修改訪問位和修改位形成物理地址形成物理地址 地址變換結(jié)束地址變換結(jié)束保留保留CPU現(xiàn)場(chǎng)現(xiàn)場(chǎng) 從外存中找到缺頁(yè)從外存中找到缺頁(yè) 頁(yè)號(hào)頁(yè)號(hào)頁(yè)表長(zhǎng)度？頁(yè)表長(zhǎng)度？ 內(nèi)存滿否？?jī)?nèi)存滿否？選擇一頁(yè)換出選擇一頁(yè)換出 該頁(yè)是否被修改？該頁(yè)是否被修改？ 將該頁(yè)寫回外存將該頁(yè)寫回外存 將一頁(yè)從外存換入內(nèi)存將一頁(yè)從外

26、存換入內(nèi)存 修改頁(yè)表修改頁(yè)表 CPU從外存讀缺頁(yè)從外存讀缺頁(yè) 啟動(dòng)啟動(dòng)I/O硬件硬件 Silberschatz, Galvin, and Gagne 1999 10.19Applied Operating System ConceptsSteps in handling a page faultLoad M 0Free frameOperatingsystemPagetable1reference6 Restart instruction5 Reset page table3 page is on backing store2 trapPhysical memory4 bring in mis

27、sing pageSilberschatz, Galvin, and Gagne 1999 10.20Applied Operating System ConceptsSteps in handling a page fault1.we check an internal table(usually kept with the process control block) for this process,to determine whether the reference was a valid or invalid memory access.2.if the reference was

28、invalid, we terminate the process. If it was valid,but we have not yet brought in that page,we now page it in.3.we find a free frame(by taking one from the free-frame list,for example)4.we schedule a disk operation to read the desired page into the newly allocated frame.5 when the disk read is compl

29、ete, we modify the internal table kept with the process and the page table to indicate that the page is now in memory6. We restart the instruction that was interrupted by the illegal address trap.the process can now access the page as though it had always been in memorySilberschatz, Galvin, and Gagn

30、e 1999 10.21Applied Operating System ConceptsWhat happens if there is no free frame?Page replacement find some page in memory, but not really in use, swap it out（頁(yè)置換頁(yè)置換找到內(nèi)存中并沒有使用的某個(gè)頁(yè)，換出找到內(nèi)存中并沒有使用的某個(gè)頁(yè)，換出）. Algorithm（算法算法） Performance（性能）性能） want an algorithm which will result in minimum number of pag

31、e faults（找出一個(gè)導(dǎo)致最小缺頁(yè)數(shù)的算找出一個(gè)導(dǎo)致最小缺頁(yè)數(shù)的算法）法）.Silberschatz, Galvin, and Gagne 1999 10.22Applied Operating System Concepts頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略 為能使進(jìn)程運(yùn)行，必須事先將一部分要執(zhí)行的為能使進(jìn)程運(yùn)行，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調(diào)入內(nèi)存程序和數(shù)據(jù)調(diào)入內(nèi)存1)調(diào)入頁(yè)面的時(shí)機(jī)調(diào)入頁(yè)面的時(shí)機(jī) 預(yù)調(diào)頁(yè)策略：預(yù)調(diào)頁(yè)策略： 是一種主動(dòng)的缺頁(yè)調(diào)入策略，即將那些預(yù)計(jì)在不是一種主動(dòng)的缺頁(yè)調(diào)入策略，即將那些預(yù)計(jì)在不久的將來(lái)會(huì)被訪問的程序或數(shù)據(jù)所在的頁(yè)面，久的將來(lái)會(huì)被訪問的程序或數(shù)據(jù)所在的頁(yè)面，預(yù)先

32、調(diào)入內(nèi)存。由于預(yù)測(cè)的準(zhǔn)確率不高（預(yù)先調(diào)入內(nèi)存。由于預(yù)測(cè)的準(zhǔn)確率不高（50%），所以這種策略主要用于），所以這種策略主要用于進(jìn)程的首次調(diào)入進(jìn)程的首次調(diào)入。有的系統(tǒng)將預(yù)調(diào)頁(yè)策略用于請(qǐng)求調(diào)頁(yè)，有的系統(tǒng)將預(yù)調(diào)頁(yè)策略用于請(qǐng)求調(diào)頁(yè)，Silberschatz, Galvin, and Gagne 1999 10.23Applied Operating System Concepts頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略請(qǐng)求調(diào)頁(yè)策略：請(qǐng)求調(diào)頁(yè)策略： 是指當(dāng)進(jìn)程在運(yùn)行中發(fā)生缺頁(yè)時(shí)，就立即提是指當(dāng)進(jìn)程在運(yùn)行中發(fā)生缺頁(yè)時(shí)，就立即提出請(qǐng)求，由系統(tǒng)將缺頁(yè)調(diào)入內(nèi)存。目前的虛出請(qǐng)求，由系統(tǒng)將缺頁(yè)調(diào)入內(nèi)存。目前的虛擬存儲(chǔ)器中，大多采用此策

33、略。但這種策略擬存儲(chǔ)器中，大多采用此策略。但這種策略在調(diào)頁(yè)時(shí)須花費(fèi)較大的系統(tǒng)開銷，如需頻繁在調(diào)頁(yè)時(shí)須花費(fèi)較大的系統(tǒng)開銷，如需頻繁啟動(dòng)磁盤啟動(dòng)磁盤I/O。Silberschatz, Galvin, and Gagne 1999 10.24Applied Operating System Concepts頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略2)從何處調(diào)入頁(yè)面從何處調(diào)入頁(yè)面 在虛擬存儲(chǔ)系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件在虛擬存儲(chǔ)系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對(duì)換區(qū)（用于存放對(duì)換頁(yè)面）。通常區(qū)（用于存放文件）和對(duì)換區(qū)（用于存放對(duì)換頁(yè)面）。通常，對(duì)換區(qū)（連續(xù)分配）的磁盤，對(duì)換

34、區(qū)（連續(xù)分配）的磁盤I/O速度比文件區(qū)（離散分配）速度比文件區(qū)（離散分配）要高。要高。在在UNIX系統(tǒng)中，對(duì)于從未運(yùn)行過的頁(yè)面，都應(yīng)從硬盤文件系統(tǒng)中，對(duì)于從未運(yùn)行過的頁(yè)面，都應(yīng)從硬盤文件區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過而又被換出的頁(yè)面，可以從對(duì)換區(qū)區(qū)調(diào)入；對(duì)于曾經(jīng)運(yùn)行過而又被換出的頁(yè)面，可以從對(duì)換區(qū)調(diào)入；對(duì)于共享頁(yè)面，該頁(yè)面可能已由其它進(jìn)程調(diào)入內(nèi)存，調(diào)入；對(duì)于共享頁(yè)面，該頁(yè)面可能已由其它進(jìn)程調(diào)入內(nèi)存，此時(shí)就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。此時(shí)就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。Silberschatz, Galvin, and Gagne 1999 10.25Applied Operating System ConceptsPe

35、rformance of Demand PagingA page fault cause the following sequence to occur: 1. Trap to the operating system 2.Save the user registers and process state 3.Determine that the interrupt was a page fault 4. Check that the page reference was legal and determine the location of the page on the disk 5.Is

36、sue a read from the disk to a free frame: a.Wait in a queue for this device until the read request is serviced. b. Wait for the devices seek and/or latency time c. Begin the transfer of the page to a free frame 6. While waiting,allocate the cpu to some other user(cpu scheduling operation) Silberscha

37、tz, Galvin, and Gagne 1999 10.26Applied Operating System ConceptsPerformance of Demand Paging7.Interrupt from the disk(I/O completed)8.Save the registers and process state for the other user(if step 6 executed)9.Determine that the interrupt was from the disk10. Correct the page table and other table

38、s to show that the desired page is now in memory11.Wait for the cpu to be allocated to this process again12. Restore the user registers,process state,and new page table,then resume the interrupted instruction.Silberschatz, Galvin, and Gagne 1999 10.27Applied Operating System ConceptsPerformance of D

39、emand Paging以上步驟并不是在任何情況下都會(huì)發(fā)生的以上步驟并不是在任何情況下都會(huì)發(fā)生的這里主要的動(dòng)作是：這里主要的動(dòng)作是：處理缺頁(yè)中斷處理缺頁(yè)中斷從磁盤讀入所需的頁(yè)從磁盤讀入所需的頁(yè)重新開始被中斷的進(jìn)程重新開始被中斷的進(jìn)程其中最大的一部分時(shí)間為從磁盤讀入所需其中最大的一部分時(shí)間為從磁盤讀入所需的頁(yè)的頁(yè)Silberschatz, Galvin, and Gagne 1999 10.28Applied Operating System Conceptsl假定作業(yè)假定作業(yè)Ji共有共有m頁(yè)，系統(tǒng)分配給它的主存塊頁(yè)，系統(tǒng)分配給它的主存塊為為n塊，這里塊，這里mn。開始時(shí)，主存沒有裝入任開始時(shí)，

40、主存沒有裝入任何一頁(yè)的信息。如果作業(yè)何一頁(yè)的信息。如果作業(yè)Ji在運(yùn)行中成功訪問在運(yùn)行中成功訪問的次數(shù)為的次數(shù)為S，不成功的訪問次數(shù)為不成功的訪問次數(shù)為F(產(chǎn)生缺頁(yè)產(chǎn)生缺頁(yè)中斷的次數(shù)中斷的次數(shù))，則作業(yè)執(zhí)行過程中總的訪問次，則作業(yè)執(zhí)行過程中總的訪問次數(shù)為數(shù)為A.A=S（成功訪問的次數(shù)）成功訪問的次數(shù)）+F（不成功的訪不成功的訪問次數(shù)）問次數(shù)）作業(yè)作業(yè)Ji執(zhí)行過程中的缺頁(yè)率執(zhí)行過程中的缺頁(yè)率f=F/A。 缺頁(yè)率缺頁(yè)率Silberschatz, Galvin, and Gagne 1999 10.29Applied Operating System ConceptsPerformance of De

41、mand PagingPage Fault Rate 0 p 1.0（缺頁(yè)率缺頁(yè)率0 p 1.0） if p = 0 no page faults （如果如果p = 0 ，沒有缺頁(yè)）沒有缺頁(yè)） if p = 1, every reference is a fault（每次訪問都缺每次訪問都缺頁(yè)）頁(yè)）Effective Access Time (EAT)（有效存取時(shí)間）有效存取時(shí)間）EAT = (1 p) x memory access+ p (page fault overhead+ swap page out + swap page in + restart overhead)Silbers

42、chatz, Galvin, and Gagne 1999 10.30Applied Operating System ConceptsDemand Paging ExampleMemory access time = 1 microsecond （存取存取內(nèi)存的時(shí)間）內(nèi)存的時(shí)間）50% of the time the page that is being replaced has been modified and therefore needs to be swapped out（ 50%的時(shí)間，所置的時(shí)間，所置換的頁(yè)被修改，因此需要被換出）換的頁(yè)被修改，因此需要被換出）.Swap Pag

43、e Time = 10 msec （交換頁(yè)的時(shí)間）交換頁(yè)的時(shí)間）EAT = (1 p) x 1 + p (10) = 1 + 9P (in msec)Silberschatz, Galvin, and Gagne 1999 10.31Applied Operating System ConceptsPage ReplacementPrevent over-allocation of memory by modifying page-fault service routine to include page replacement（通過通過修改缺頁(yè)服務(wù)例程，來(lái)包含頁(yè)置換）修改缺頁(yè)服務(wù)例程，來(lái)包含

44、頁(yè)置換）.Use modify (dirty) bit to reduce overhead of page transfers only modified pages are written to disk（使使用修改（臟）位來(lái)防止頁(yè)面?zhèn)鬏斶^多用修改（臟）位來(lái)防止頁(yè)面?zhèn)鬏斶^多只有被修改的頁(yè)面才只有被修改的頁(yè)面才寫入磁盤）寫入磁盤）.Page replacement completes separation between logical memory and physical memory large virtual memory can be provided on a smaller p

45、hysical memory（頁(yè)置換完善了邏輯內(nèi)存和物理內(nèi)存的劃分頁(yè)置換完善了邏輯內(nèi)存和物理內(nèi)存的劃分在一個(gè)較小的在一個(gè)較小的物理內(nèi)存基礎(chǔ)之上可以提供一個(gè)大的虛擬內(nèi)存物理內(nèi)存基礎(chǔ)之上可以提供一個(gè)大的虛擬內(nèi)存.Silberschatz, Galvin, and Gagne 1999 10.32Applied Operating System ConceptsPage-Replacement AlgorithmsWant lowest page-fault rate（需要一個(gè)最需要一個(gè)最小的缺頁(yè)率）小的缺頁(yè)率）.Evaluate algorithm by running it on a parti

46、cular string of memory references (reference string) and computing the number of page faults on that string（通通過運(yùn)行一個(gè)內(nèi)存訪問的特殊序列（訪問序列過運(yùn)行一個(gè)內(nèi)存訪問的特殊序列（訪問序列），計(jì)算這個(gè)序列的缺頁(yè)次數(shù)），計(jì)算這個(gè)序列的缺頁(yè)次數(shù)）.Silberschatz, Galvin, and Gagne 1999 10.33Applied Operating System ConceptsPage-Replacement Algorithms在進(jìn)程運(yùn)行過程中，如果發(fā)生缺頁(yè)，此時(shí)內(nèi)存中又

47、在進(jìn)程運(yùn)行過程中，如果發(fā)生缺頁(yè)，此時(shí)內(nèi)存中又無(wú)空閑塊時(shí)，為了保證進(jìn)程能正常運(yùn)行就必須從內(nèi)無(wú)空閑塊時(shí)，為了保證進(jìn)程能正常運(yùn)行就必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)。但將哪存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)。但將哪個(gè)頁(yè)面調(diào)出，則須根據(jù)一定的頁(yè)面置換算法來(lái)確定個(gè)頁(yè)面調(diào)出，則須根據(jù)一定的頁(yè)面置換算法來(lái)確定。置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)。置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)乃惴赡軙?huì)導(dǎo)致進(jìn)程發(fā)生的算法可能會(huì)導(dǎo)致進(jìn)程發(fā)生“抖動(dòng)抖動(dòng)”（Thrashing)Thrashing)。即剛被換出的頁(yè)很快又被訪問，需重新調(diào)入，導(dǎo)即剛被換出的頁(yè)很快又被訪問，需重新調(diào)入，導(dǎo)致系統(tǒng)頻繁地更換

48、頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把致系統(tǒng)頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分時(shí)間花費(fèi)在完成頁(yè)面置換的工作上，我們稱大部分時(shí)間花費(fèi)在完成頁(yè)面置換的工作上，我們稱該進(jìn)程發(fā)生了該進(jìn)程發(fā)生了“抖動(dòng)抖動(dòng)”（顛簸）。（顛簸）。Silberschatz, Galvin, and Gagne 1999 10.34Applied Operating System ConceptsPage-Replacement Algorithms從理論上講，應(yīng)將那些以后不再被從理論上講，應(yīng)將那些以后不再被訪問的頁(yè)面換出，或把那些在較長(zhǎng)訪問的頁(yè)面換出，或把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再被訪問的頁(yè)面換出。時(shí)間內(nèi)不會(huì)再被訪問的頁(yè)面換出。

49、目前目前, ,存在多種置換算法存在多種置換算法, ,都是試圖都是試圖更接近理論上的目標(biāo)。更接近理論上的目標(biāo)。Silberschatz, Galvin, and Gagne 1999 10.35Applied Operating System ConceptsPage-Replacement Algorithms1.最佳算法最佳算法(OPT, optimal)2.最近最久未使用算法最近最久未使用算法(LRU,Least Recently Used)3.先進(jìn)先出算法先進(jìn)先出算法(FIFO) Belady現(xiàn)象現(xiàn)象4. LRU的的近似近似算法算法Silberschatz, Galvin, and Ga

50、gne 1999 10.36Applied Operating System Concepts頁(yè)面置換算法頁(yè)面置換算法 .最佳（最佳（Optimal）置換算法置換算法 它是一種理想化的算法，性能最好，但在實(shí)際上它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即難于實(shí)現(xiàn)。即選擇那些永不使用的，或者是在最選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)面置換出去長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)面置換出去。但是要確。但是要確定哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問的，定哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問的，目前來(lái)說是很難估計(jì)的，所以該算法通常用來(lái)評(píng)目前來(lái)說是很難估計(jì)的，所以該算法通常用來(lái)評(píng)價(jià)其它算法。

51、價(jià)其它算法。Silberschatz, Galvin, and Gagne 1999 10.37Applied Operating System Concepts頁(yè)面置換算法頁(yè)面置換算法最佳置換算法舉例最佳置換算法舉例例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁(yè)面號(hào)引用串：慮有以下的頁(yè)面號(hào)引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如如下頁(yè)圖所示，進(jìn)程運(yùn)行時(shí)先將下頁(yè)圖所示，進(jìn)程運(yùn)行時(shí)先將7，0，1三個(gè)頁(yè)面裝三個(gè)頁(yè)面裝入內(nèi)存。當(dāng)進(jìn)程訪問頁(yè)面入內(nèi)存。當(dāng)進(jìn)程訪問頁(yè)面2時(shí)，產(chǎn)生缺頁(yè)中斷，此時(shí)，產(chǎn)生缺頁(yè)中斷，

52、此時(shí)時(shí)OS根據(jù)根據(jù)最佳置換算法最佳置換算法，頁(yè)面，頁(yè)面7將在第將在第18次才被次才被訪問，是三頁(yè)中將最久不被訪問的頁(yè)面，所以被訪問，是三頁(yè)中將最久不被訪問的頁(yè)面，所以被淘汰。接著訪問頁(yè)面淘汰。接著訪問頁(yè)面0時(shí)，發(fā)現(xiàn)已在內(nèi)存中，而不時(shí)，發(fā)現(xiàn)已在內(nèi)存中，而不會(huì)產(chǎn)生缺頁(yè)中斷，以此類推。從圖可以看出，采會(huì)產(chǎn)生缺頁(yè)中斷，以此類推。從圖可以看出，采用最佳置換算法，只發(fā)生了用最佳置換算法，只發(fā)生了6次頁(yè)面置換次頁(yè)面置換。Silberschatz, Galvin, and Gagne 1999 10.38Applied Operating System Concepts最佳（最佳（Optimal）置換算法置換

53、算法發(fā)生了發(fā)生了6次面置換，次面置換，9次缺頁(yè)中斷。次缺頁(yè)中斷。頁(yè)面 引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 7 0 0 0 0 4 0 0 0 物 理 塊 1 1 3 3 3 1 1 缺頁(yè) x x x x x x x x x 置換 Silberschatz, Galvin, and Gagne 1999 10.39Applied Operating System Concepts 先進(jìn)先出（先進(jìn)先出（FIFOFIFO）置換算法置換算法該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法

54、實(shí)現(xiàn)簡(jiǎn)單，只須把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針即可。它是一種最直觀，性能最差的算法。 頁(yè) 面引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7 0 0 0 3 3 3 2 2 2 1 1 1 0 0 物 理塊 1 1 1 0 0 0 3 3 3 2 2 2 1 缺頁(yè) x x x x x x x x x x x x x x x 發(fā)生了 12 次頁(yè)面置換，缺頁(yè)次數(shù) 15 次。 Silberschatz, Galvin, and Gagne 1999 10.40Appli

55、ed Operating System Concepts 先進(jìn)先出（先進(jìn)先出（FIFO）置換算法置換算法BELADY 異?，F(xiàn)象：對(duì)頁(yè)面訪問序列 1 2 3 4 1 2 5 1 2 3 4 5 ，物理塊從 3 塊增加到4塊，缺頁(yè)次數(shù)增加。 頁(yè)面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 4 4 4 5 5 5 2 2 2 1 1 1 3 3 物理塊 3 3 3 2 2 2 4 缺頁(yè) x x x x x x x x x 發(fā)生了6次頁(yè)面置換，缺頁(yè)次數(shù)9次。 頁(yè)面引用 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 5 5 5 5 4 4 2 2 2 2 1 1

56、1 1 5 3 3 3 3 2 2 2 2 物理塊 4 4 4 4 3 3 3 缺頁(yè) x x x x x x x x x x 發(fā)生了6次頁(yè)面置換，缺頁(yè)次數(shù)10次。 Silberschatz, Galvin, and Gagne 1999 10.41Applied Operating System Concepts 最近最久未使用置換算法最近最久未使用置換算法該算法是選擇最近最久未使用的頁(yè)面予以淘汰，系統(tǒng)在每個(gè)頁(yè)面設(shè)置一 個(gè)訪問 字段， 用以記 錄這個(gè)頁(yè) 面自上 次被訪 問以來(lái) 所經(jīng)歷 的時(shí) 間T，當(dāng) 要淘汰 一個(gè)頁(yè) 面時(shí)， 選擇T 最 大的頁(yè) 面。但 在實(shí)現(xiàn) 時(shí)需要 硬件的 支持 （ 寄 存

57、器 或 棧 ） 。 利 用LRU算 法 對(duì) 上 例 進(jìn) 行 頁(yè) 面 置 換 的 結(jié) 果 如 下 ： 頁(yè)面引用 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 4 4 4 0 1 1 1 0 0 0 0 0 0 3 3 3 0 0 物 理 塊 1 1 3 3 2 2 2 2 2 7 缺 頁(yè) x x x x x x x x x x x x 發(fā) 生 了9次 面 置 換 ， 缺 頁(yè) 次 數(shù)12次 Silberschatz, Galvin, and Gagne 1999 10.42Applied Operating System ConceptsLea

58、st Recently Used (LRU) AlgorithmCounter implementation（計(jì)數(shù)器實(shí)現(xiàn)）計(jì)數(shù)器實(shí)現(xiàn)） Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter（每一個(gè)頁(yè)表項(xiàng)每一個(gè)頁(yè)表項(xiàng) 有一個(gè)時(shí)間域，給有一個(gè)時(shí)間域，給CPU增加增加一個(gè)計(jì)數(shù)器，每次訪問內(nèi)存，該計(jì)數(shù)器值加一個(gè)計(jì)數(shù)器，每次訪問內(nèi)存，該計(jì)數(shù)器值加1。如果某一。如果某一頁(yè)被訪問，則把計(jì)數(shù)器值拷貝到該頁(yè)的時(shí)間域中）頁(yè)被訪問，則把計(jì)數(shù)器值

59、拷貝到該頁(yè)的時(shí)間域中）. When a page needs to be changed, look at the counters to determine which are to change（當(dāng)需要當(dāng)需要進(jìn)行頁(yè)面置換時(shí)，查看頁(yè)表中每一頁(yè)的時(shí)間域，選擇該進(jìn)行頁(yè)面置換時(shí)，查看頁(yè)表中每一頁(yè)的時(shí)間域，選擇該值最小的頁(yè)面換出去值最小的頁(yè)面換出去.） 特點(diǎn)特點(diǎn)：每次內(nèi)存訪問時(shí)需增加一次寫內(nèi)存（寫頁(yè)表中某：每次內(nèi)存訪問時(shí)需增加一次寫內(nèi)存（寫頁(yè)表中某一頁(yè)的時(shí)間域）；頁(yè)面替換時(shí)需檢索頁(yè)表以找到時(shí)間域一頁(yè)的時(shí)間域）；頁(yè)面替換時(shí)需檢索頁(yè)表以找到時(shí)間域最小的頁(yè)面。最小的頁(yè)面。5435Silberschatz,

60、 Galvin, and Gagne 1999 10.43Applied Operating System ConceptsLRU Algorithm (Cont.)Stack implementation keep a stack of page numbers in a double link form（棧實(shí)現(xiàn)棧實(shí)現(xiàn)用一用一個(gè)雙向鏈表實(shí)現(xiàn)一個(gè)記錄頁(yè)號(hào)的棧）個(gè)雙向鏈表實(shí)現(xiàn)一個(gè)記錄頁(yè)號(hào)的棧）: Page referenced（被訪問的頁(yè)移到棧頂）被訪問的頁(yè)移到棧頂） 棧底的頁(yè)是最近最少被訪問的棧底的頁(yè)是最近最少被訪問的 No search for replacement（不用為置換進(jìn)不用為置換