1、C虛擬存儲器PPT課件4.6 虛擬存儲器的基本概念 前面所介紹的各種存儲管理方式具有一個共同前面所介紹的各種存儲管理方式具有一個共同的特點，即作業必須一次性全部裝入主存空間后才的特點，即作業必須一次性全部裝入主存空間后才能運行，直至作業運行結束后才釋放所占有的全部能運行，直至作業運行結束后才釋放所占有的全部主存資源。這樣就會出現以下情況：主存資源。這樣就會出現以下情況：1當主存空間不能滿足作業地址空間要求時，作業就不能裝當主存空間不能滿足作業地址空間要求時，作業就不能裝入主存，無法運行。入主存，無法運行。2當有大量作業要求運行時，由于主存容量有限，只能將少當有大量作業要求運行時，由于主存容量有

2、限，只能將少數作業裝入主存運行，而其他作業留在輔存上等待。數作業裝入主存運行，而其他作業留在輔存上等待。C虛擬存儲器PPT課件4.6.1 虛擬存儲器的引入虛擬存儲器的引入 常規存儲管理方式的特征是：常規存儲管理方式的特征是：一次性一次性、駐留性駐留性。局部性原理局部性原理 早在1968年PDenning就指出過，程序在執行時將呈程序在執行時將呈現出局部性規律，即在一段時間內，程序的執行僅局限于某現出局部性規律，即在一段時間內，程序的執行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區域內。個部分；相應地，它所訪問的存儲空間也局限于某個區域內。那么程序出現局部性規律原因可以歸結為以下幾

3、點： （1）程序在執行時，除了少部分的轉移和過程調用指令外，大多數仍是順序執行的。 （2）子程序調用將會使程序的執行由一部分內存區域轉至另一部分區域。但在大多數情況下，過程調用的深度都不超過5。 （3）程序中存在許多循環結構，循環體中的指令被多次執行。 （4）程序中還包括許多對數據結構的處理，如對連續的存儲空間數組的訪問，往往局限于很小的范圍內。C虛擬存儲器PPT課件局部性原理局部性原理：程序在執行時將呈現出局部性規律，即：程序在執行時將呈現出局部性規律，即在一較短的時間內，程序的執行僅局限于某個部分；在一較短的時間內，程序的執行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區域。具

4、相應地，它所訪問的存儲空間也局限于某個區域。具體地表現為：體地表現為：時間的局限性時間的局限性，如果程序中的某條指令一旦執行，如果程序中的某條指令一旦執行，則不久以后該指令可能再次執行；某個數據被訪問，則不久以后該指令可能再次執行；某個數據被訪問，則不久以后該數據可能被再次訪問。原因是在程序中則不久以后該數據可能被再次訪問。原因是在程序中存在著大量的循環操作。存在著大量的循環操作。空間的局限性空間的局限性，一旦程序訪問了某個存儲單元，在，一旦程序訪問了某個存儲單元，在不久以后，其附近的存儲單元也被訪問，即程序在一不久以后，其附近的存儲單元也被訪問，即程序在一段時間內所訪問的地址可能集中在一定的

5、范圍內。原段時間內所訪問的地址可能集中在一定的范圍內。原因是程序的順序執行。因是程序的順序執行。C虛擬存儲器PPT課件 根據局部性原理，一個作業在運行之前，沒有必要把全根據局部性原理，一個作業在運行之前，沒有必要把全部作業裝入內存，而僅將那些當前要運行的那部分頁面或段，部作業裝入內存，而僅將那些當前要運行的那部分頁面或段，先裝入內存便可啟動運行，其余部分暫時留在磁盤上。程序先裝入內存便可啟動運行，其余部分暫時留在磁盤上。程序在運行時如果它所要訪問的頁（段）已調入內存，便可繼續在運行時如果它所要訪問的頁（段）已調入內存，便可繼續執行下去；但如果程序所要訪問的頁（段）尚未調入內存執行下去；但如果程

6、序所要訪問的頁（段）尚未調入內存（稱為缺頁或缺段），此時程序應利用（稱為缺頁或缺段），此時程序應利用OS所提供的所提供的請求調頁請求調頁（段）功能（段）功能，將它們調入內存，以使進程能繼續執行下去。，將它們調入內存，以使進程能繼續執行下去。如果此時內存已滿，無法再裝入新的頁（段），則還須再利如果此時內存已滿，無法再裝入新的頁（段），則還須再利用頁（段）的用頁（段）的置換功能置換功能，將，將內存中暫時不用的頁（段）調出內存中暫時不用的頁（段）調出至磁盤上至磁盤上，騰出足夠的內存空間后，再將所，騰出足夠的內存空間后，再將所要訪問的頁（段）要訪問的頁（段）調入內存調入內存，使程序繼續執行下去。這樣，

7、便可使一個大的用，使程序繼續執行下去。這樣，便可使一個大的用戶程序在較小的內存空間中運行；也可使內存中同時裝入更戶程序在較小的內存空間中運行；也可使內存中同時裝入更多的進程并發執行。多的進程并發執行。從用戶角度看從用戶角度看，該系統所具有的內存容，該系統所具有的內存容量，將比實際內存容量大得多，人們把這樣的存儲器稱為虛量，將比實際內存容量大得多，人們把這樣的存儲器稱為虛擬存儲器。擬存儲器。3、虛擬存儲器的定義虛擬存儲器的定義C虛擬存儲器PPT課件 虛擬存儲器虛擬存儲器是指具有是指具有請求調入功能請求調入功能和和置換功能置換功能，能從邏輯，能從邏輯上對內存進行擴充的一種存儲器系統。實際上，用戶所

8、看到的上對內存進行擴充的一種存儲器系統。實際上，用戶所看到的大容量只是一種感覺，是虛的，其邏輯容量由大容量只是一種感覺，是虛的，其邏輯容量由內存內存和和外存容量外存容量之和之和決定，其運行速度決定，其運行速度接近于內存的速度接近于內存的速度，而，而成本接近于外存成本接近于外存，因而是一種性能非常優越的存儲器管理技術，被廣泛應用于各因而是一種性能非常優越的存儲器管理技術，被廣泛應用于各類計算機中。類計算機中。虛擬存儲器的特征虛擬存儲器的特征1）離散性（基礎）2）多次性（一個作業分多次調入）3）對換性（程序和數據的換入/換出）4）虛擬性（邏輯上擴充內存容量）C虛擬存儲器PPT課件4.6.2 虛擬存

9、儲器實現方式虛擬存儲器實現方式建立在離散分配基礎上建立在離散分配基礎上1.分頁請求系統分頁請求系統： 在分頁系統的基礎上，增加了在分頁系統的基礎上，增加了請求調頁功能請求調頁功能和和頁面置換頁面置換功能功能所形成的所形成的頁式虛擬存儲系統頁式虛擬存儲系統。它允許只裝入若干頁（而。它允許只裝入若干頁（而非全部程序）的用戶程序和數據，就可以啟動運行，以后再非全部程序）的用戶程序和數據，就可以啟動運行，以后再通過調頁功能和頁面置換功能，陸續把將要運行的頁面調入通過調頁功能和頁面置換功能，陸續把將要運行的頁面調入內存，同時把內存，同時把暫不運行的頁面置換到外存上暫不運行的頁面置換到外存上，置換時，置換

10、時以頁面以頁面為單位為單位。2.請求分段系統請求分段系統： 在分段系統的基礎上，增加了在分段系統的基礎上，增加了請求調段請求調段和和分段置換功能分段置換功能所形成的段式虛擬存儲系統。它允許只裝入若干段（而非全所形成的段式虛擬存儲系統。它允許只裝入若干段（而非全部段）的用戶程序和數據，就可以啟動運行，以后再通過調部段）的用戶程序和數據，就可以啟動運行，以后再通過調段功能和置換功能將不運行的段調出，同時調入將要運行的段功能和置換功能將不運行的段調出，同時調入將要運行的段，置換段，置換以段為單位以段為單位。C虛擬存儲器PPT課件虛擬存儲管理方式：為了滿足用戶對內虛擬存儲管理方式：為了滿足用戶對內存的

11、需要，進一步提高內存利用率，又存的需要，進一步提高內存利用率，又形成了多種虛擬存儲管理方式。其方式形成了多種虛擬存儲管理方式。其方式有：有：a.請求分頁式管理方式請求分頁式管理方式 ；b.請求分段式管理方式；請求分段式管理方式；c.請求段頁式管理方式。請求段頁式管理方式。C虛擬存儲器PPT課件 動態頁式管理是在分頁存儲管理基礎上發展起來動態頁式管理是在分頁存儲管理基礎上發展起來的的, ,增加了增加了請求分頁功能請求分頁功能和和頁面置換功能頁面置換功能實現虛擬存實現虛擬存儲系統。儲系統。指導思想：指導思想：在作業運行之前，在作業運行之前，不必不必把作業的整個地址把作業的整個地址空間空間全部裝入主

12、存全部裝入主存，而只要求當前需要的，而只要求當前需要的一部分裝入一部分裝入主存主存即可。這樣，對作業地址空間，當其即可。這樣，對作業地址空間，當其作業的大小作業的大小超過主存超過主存可用空間時，用頁式存儲管理實現虛擬存儲可用空間時，用頁式存儲管理實現虛擬存儲器管理。這個方案可以為每個用戶提供一個虛擬存儲器管理。這個方案可以為每個用戶提供一個虛擬存儲器，其器，其虛擬空間比主存的空間大虛擬空間比主存的空間大。這對編制大型程序。這對編制大型程序來說，帶來了很多方便。來說，帶來了很多方便。4.74.7請求分頁存儲管理方式請求分頁存儲管理方式( (動態頁式管理動態頁式管理) )C虛擬存儲器PPT課件1

13、1 請求分頁概念請求分頁概念 請求分頁技術當一個用戶程序要調入內存時，請求分頁技術當一個用戶程序要調入內存時，不是將該程序全部頁面裝入內存，而是只裝入部分不是將該程序全部頁面裝入內存，而是只裝入部分頁面到內存，就可啟動程序運行頁面到內存，就可啟動程序運行，在運行的過程中，在運行的過程中，如果如果發現要運行的程序或要訪問數據不在內存發現要運行的程序或要訪問數據不在內存，則，則向系統發出向系統發出缺頁中斷請求缺頁中斷請求，系統，系統在處理這個中斷時在處理這個中斷時，將在外存將在外存相應的頁調入內存相應的頁調入內存，該程序繼續運行該程序繼續運行。 為了實現請求分頁，系統需要有：為了實現請求分頁，系統

14、需要有：(1)(1)頁表機制頁表機制、(2)(2)缺頁中斷機構缺頁中斷機構、(3)(3)地址變換機構地址變換機構 (4)(4)頁面置換算法頁面置換算法C虛擬存儲器PPT課件（1 1）頁表機制）頁表機制 狀態位狀態位P:P:用于指示該頁是否已調入內存，用于指示該頁是否已調入內存，供程序訪問時參考供程序訪問時參考； 訪問字段訪問字段A:A:用于記錄本頁在一段時間內用于記錄本頁在一段時間內被訪問的次數被訪問的次數，或記，或記錄本頁最近已有多長時間未被訪問，供選擇錄本頁最近已有多長時間未被訪問，供選擇換出頁面時參考換出頁面時參考； 修改位修改位M:M:表示該頁在調入內存后是否被修改過，供表示該頁在調入

15、內存后是否被修改過，供置換頁面置換頁面時參考；時參考； 外存地址外存地址: :用于指示該頁用于指示該頁在外存上的地址在外存上的地址，供調入頁時使用。供調入頁時使用。頁號頁號物理塊號物理塊號 狀態位狀態位P P 訪問字段訪問字段A A 修改位修改位M M 外存地址外存地址C虛擬存儲器PPT課件C虛擬存儲器PPT課件（2 2）缺頁中斷機構）缺頁中斷機構 在請求分頁系統中，每當所要訪問的頁面不在內存時，在請求分頁系統中，每當所要訪問的頁面不在內存時，便產生一缺頁中斷，請求便產生一缺頁中斷，請求OSOS將所缺頁調入內存。特點：將所缺頁調入內存。特點： 1)1)在指令執行期間在指令執行期間產生和處理中斷

16、信號；產生和處理中斷信號； 2)2)一條指令在執行期間，可能產生一條指令在執行期間，可能產生多次缺頁中斷多次缺頁中斷B:A:指令指令TO BCopy A頁面頁面6 65 54 43 32 21 1C虛擬存儲器PPT課件 地址變換機構地址變換機構 缺頁中斷處理保留CPU現場從外存中找到缺頁內存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS命令CPU從外存讀缺頁啟動I/O硬件將一頁從外存換入內存修改頁表否是是否頁表項在快表中？CPU檢索快表訪問頁表否頁在內存？修改訪問位和修改位形成物理地址地址變換結束否頁號頁表長度?開始程序請求訪問一頁產生缺頁中斷請求調頁修改快表是越界中斷是是內存分配內存分配

17、1 1 最小物理塊數的確定最小物理塊數的確定( (由硬件結構和性能決定由硬件結構和性能決定) ) 最小物理塊數：最小物理塊數：能保證進程正常運行所需要的最小物理塊數。能保證進程正常運行所需要的最小物理塊數。2 2 物理塊的分配和置換物理塊的分配和置換 1)1)固定分配局部置換固定分配局部置換 2)2)可變分配全局置換可變分配全局置換 3)3)可變分配局部置換可變分配局部置換3 3 物理塊分配算法物理塊分配算法 1)1)平均分配平均分配 2)2)按比例分配按比例分配 各進程的頁面總和：各進程的頁面總和：S=(S1+S2+S3+S=(S1+S2+S3+Sn)+Sn) 每個進程所能分配到的物理塊：每

18、個進程所能分配到的物理塊：bi=(Sn/s)bi=(Sn/s)* *m m 3 3）考慮優先權的分配算法：一按比例；二按優先權）考慮優先權的分配算法：一按比例；二按優先權內存分配策略和分配算法內存分配策略和分配算法C虛擬存儲器PPT課件1 1、何時調入頁面、何時調入頁面 1)1)預調頁策略預調頁策略 系統根據作業（進程）運行的情況，預測哪些頁將要運行，在系統根據作業（進程）運行的情況，預測哪些頁將要運行，在其運行之前先行調入內存，這樣在程序運行的過程中就不會出現缺其運行之前先行調入內存，這樣在程序運行的過程中就不會出現缺頁中斷。這種方法從表面上看起來很好，但系統無法預計系統中作頁中斷。這種方法

19、從表面上看起來很好，但系統無法預計系統中作業的運行情況，難以實現。業的運行情況，難以實現。 2)2)請求調頁策略請求調頁策略 進程在執行的過程中，發現要執行的程序或處理的數據不在內進程在執行的過程中，發現要執行的程序或處理的數據不在內存，向系統提出調入相應程序的請求，系統響應用戶的請求。存，向系統提出調入相應程序的請求，系統響應用戶的請求。2 2、從何處調入頁面、從何處調入頁面文件區和對換區文件區和對換區1)1)系統擁有足夠的對換區空間系統擁有足夠的對換區空間對換區對換區2)2)系統缺少足夠的對換區空間系統缺少足夠的對換區空間對換區，文件區對換區，文件區3)UNIX3)UNIX方式方式對換區，

20、文件區對換區，文件區調頁策略調頁策略C虛擬存儲器PPT課件 頁面置換概念頁面置換概念 抖動（或稱顛簸抖動（或稱顛簸）：如果分配給進程的存儲塊數）：如果分配給進程的存儲塊數小于進程所需要的最小值，進程的運行將很頻繁地產小于進程所需要的最小值，進程的運行將很頻繁地產生缺頁中斷的現象，即就是同一個頁面頻繁的在主、生缺頁中斷的現象，即就是同一個頁面頻繁的在主、外存之間入頁和出頁這種現象。外存之間入頁和出頁這種現象。 為了防止抖動的產生，在頁面置換中，為了防止抖動的產生，在頁面置換中，一方面一方面要要采用合適的置換算法；采用合適的置換算法；另一方面另一方面在進行頁面淘汰或置在進行頁面淘汰或置換時，可以將

21、缺頁的進程鎖住，不讓其換出頁面，從換時，可以將缺頁的進程鎖住，不讓其換出頁面，從而防止抖動的發生。而防止抖動的發生。另一個辦法另一個辦法就是設置較大的內存就是設置較大的內存工作區。工作區。4.8 頁面置換算法C虛擬存儲器PPT課件頁面置換算法分類(1)最佳最佳置換置換算法（算法（OPT算法）算法） (2)先進先出算法（先進先出算法（FIFO算法）算法）(3)最近最久未使用（最近最久未使用（LRU）置換算法）置換算法(4) Clock置換算法置換算法(5)其他置換算法：最少使用和頁面緩沖其他置換算法：最少使用和頁面緩沖C虛擬存儲器PPT課件(1)最佳算法（OPT算法） 從內存中移出從內存中移出以

22、后不再使用的頁面以后不再使用的頁面或或選擇最選擇最長時間內不再被訪問的頁面長時間內不再被訪問的頁面予以淘汰。這樣產生予以淘汰。這樣產生的缺頁中斷次數最少，可獲得最低的缺頁中斷率。的缺頁中斷次數最少，可獲得最低的缺頁中斷率。但是由于無法預知哪個頁面是未來最長時間內不但是由于無法預知哪個頁面是未來最長時間內不被訪問的，所以該算法只是一種理論上的算法被訪問的，所以該算法只是一種理論上的算法. 注意：如果所訪問的頁還沒裝入內存，便將發注意：如果所訪問的頁還沒裝入內存，便將發生一次缺頁中斷，訪問過程中發生缺頁中斷生一次缺頁中斷，訪問過程中發生缺頁中斷的次數就是的次數就是缺頁次數缺頁次數，而缺頁次數除以總

23、的，而缺頁次數除以總的訪問次數，就是訪問次數，就是缺頁率缺頁率。C虛擬存儲器PPT課件7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1707107102302342302102107102302342342302302102102102107107C虛擬存儲器PPT課件(2)先進先出算法（FIFO算法）這種算法的基本思想是：總是先淘汰那些駐留這種算法的基本思想是：總是先淘汰那些駐留在內存時間最長的頁面，即先進入內存的頁面在內存時間最長的頁面，即先進入內存的頁面先被置換掉。理由是：最先進入

24、內存的頁面不先被置換掉。理由是：最先進入內存的頁面不再被訪問的可能性最大再被訪問的可能性最大。這種算法實現起來比較簡單。如下圖所示這種算法實現起來比較簡單。如下圖所示 ：C虛擬存儲器PPT課件7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 1 7 0 17 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 1 7 0 1707107210321032403240324032103210721072107最早進入最晚進入C虛擬存儲器PPT課件 采用采用FIFOFIFO算法還會產生一種奇怪現象，直觀上，分算法還會產生一種奇怪現象，直觀上，分配給作業的配給作業的物理

25、塊越多物理塊越多，進程執行時發生的，進程執行時發生的缺頁率就缺頁率就越小越小，但對，但對FIFOFIFO算法這個結論并不是絕對的。在某些算法這個結論并不是絕對的。在某些情況下，當分配的情況下，當分配的物理塊數增多反而導致更多的缺頁物理塊數增多反而導致更多的缺頁中斷中斷，這種現象稱為，這種現象稱為FIFOFIFO異常現象異常現象或稱或稱BeladyBelady現象，現象，即在即在未未給進程或作業給進程或作業分足分足它所要求的頁面數時，它所要求的頁面數時，有時會出有時會出現分配的物理塊數增多，缺頁次數反而增加的奇怪現象。現分配的物理塊數增多，缺頁次數反而增加的奇怪現象。（根本原因就是沒有考慮程序執

26、行的動態特征）（根本原因就是沒有考慮程序執行的動態特征） 某 進 程 共 有某 進 程 共 有 5 5 頁頁 , , 依 次 訪 問 頁 面 的 序 列依 次 訪 問 頁 面 的 序 列為為:1,2,3,4,1,2,5,1,2,3,4,5;:1,2,3,4,1,2,5,1,2,3,4,5;當系統為該進程分配的物理當系統為該進程分配的物理塊數塊數M=3M=3時時, ,缺頁中斷次數為缺頁中斷次數為9 9次次, ,其缺頁中斷率為其缺頁中斷率為9/12=75%9/12=75%; ;但是如果為進程分配的物理塊數但是如果為進程分配的物理塊數M=4M=4時時, ,缺頁中斷次數為缺頁中斷次數為1010次次,

27、,其缺頁中斷率為其缺頁中斷率為10/12=83.3%10/12=83.3%; ;C虛擬存儲器PPT課件123412555344123412225331234111255123444512345123334512341222345123111234512123412512345+(“+”表示產生一次缺頁中斷)C虛擬存儲器PPT課件 當需要淘汰某一頁時，算法選擇離當前當需要淘汰某一頁時，算法選擇離當前最近最近的一段時間的一段時間內內最久沒有使用最久沒有使用過的頁先淘汰。其理由是，過的頁先淘汰。其理由是，如果如果某頁被訪問某頁被訪問了，則它可能馬上還要被訪問，了，則它可能馬上還要被訪問，反之反之如果

28、該頁很長時間未被如果該頁很長時間未被訪問，則它在最近一段時間內也不會被訪問。為了記錄頁面訪問，則它在最近一段時間內也不會被訪問。為了記錄頁面自上次被訪問以來所經過的時間自上次被訪問以來所經過的時間, ,需要在頁表中增加一個需要在頁表中增加一個引用引用位標志位標志, ,在每次被訪問后將引用位置在每次被訪問后將引用位置0,0,重新計時重新計時。在發生缺頁。在發生缺頁中斷需要調入新的頁面時中斷需要調入新的頁面時, ,通過檢查頁表中各頁的通過檢查頁表中各頁的引用位引用位, ,選選擇最長時間沒有被訪問過的頁面淘汰擇最長時間沒有被訪問過的頁面淘汰, ,并且把主存中所有頁面并且把主存中所有頁面的引用位的引用

29、位全部清零全部清零, ,重新計時重新計時。因此。因此, ,要實現要實現LRU算法，需要算法，需要付出付出很大的系統開銷很大的系統開銷。在實際系統中，經常采用。在實際系統中，經常采用LRULRU的近似算的近似算法。法。(3).最近最久未使用置換算法（LRU）C虛擬存儲器PPT課件LRULRU近似算法是在頁表中為近似算法是在頁表中為每一頁增加一個引用位每一頁增加一個引用位, ,當該頁當該頁被訪問時被訪問時, ,由硬件將它的由硬件將它的引用位置為引用位置為1 1, ,操作系統選擇一個操作系統選擇一個時間周期時間周期T T, ,每隔一個周期每隔一個周期T,T,將頁表中所有頁面的引用位置將頁表中所有頁面

30、的引用位置0 0, ,這樣在時間周這樣在時間周期期T T內內, ,被訪問的頁面引用位為被訪問的頁面引用位為1 1, ,而沒有被訪問過的頁面的引用位而沒有被訪問過的頁面的引用位仍為仍為0 0。當產生缺頁中斷時當產生缺頁中斷時, ,可以從引用位為可以從引用位為0 0的頁面中選擇一頁調的頁面中選擇一頁調出出, ,同時將所有頁面的引用位全部置同時將所有頁面的引用位全部置0 0。實現：可利用一個特殊的實現：可利用一個特殊的棧棧來保存來保存當前使用的當前使用的各個頁面的頁面號。各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，再將每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，再將

31、它壓入棧頂。因此，它壓入棧頂。因此，棧頂棧頂始終是始終是最新被訪問最新被訪問的頁面的編號，而的頁面的編號，而棧棧底底則是則是最近最久未使用最近最久未使用頁面的頁面號。頁面的頁面號。 C虛擬存儲器PPT課件7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1707107210302403240324032123021710021032302230213102071107C虛擬存儲器PPT課件LRU近似算法這種算法，只要在存儲分塊表（或頁表）中設這種算法，只要在存儲分塊表（或頁表）中設一個一個“

32、引用位引用位”，當存儲分塊表中的某一頁被，當存儲分塊表中的某一頁被訪問時，該位由硬件自動置訪問時，該位由硬件自動置1，并由頁面管理，并由頁面管理軟件周期性把所有引用位置軟件周期性把所有引用位置0。這樣，在一個。這樣，在一個時間周期時間周期T內，某些被訪問過的頁面其引用位內，某些被訪問過的頁面其引用位為為1，而未被訪問過的頁面其引用位為，而未被訪問過的頁面其引用位為0。根據引用位的狀態來判別各頁面最近的使用情根據引用位的狀態來判別各頁面最近的使用情況。當需要置換一頁面時，選擇其引用位為況。當需要置換一頁面時，選擇其引用位為0的頁，如下圖所示的算法。的頁，如下圖所示的算法。LRU近似算法流程圖:L

33、RU近似算法舉例返回本節C虛擬存儲器PPT課件 （4 4）最近最不常用法）最近最不常用法(LFU)(LFU)：當需要淘汰時，應淘汰：當需要淘汰時，應淘汰被訪問次數最少被訪問次數最少的頁。一種簡單的方法式為每一頁設的頁。一種簡單的方法式為每一頁設置一個置一個計數器計數器，每當訪問一頁時，就把該頁對應的計，每當訪問一頁時，就把該頁對應的計數器加數器加1 1，每隔一定的時間周期，每隔一定的時間周期T,T,將所有計數器全部清將所有計數器全部清0 0。當發生缺頁中斷時，選擇。當發生缺頁中斷時，選擇計數值最小計數值最小的頁，把它淘的頁，把它淘汰，汰，同時同時把所有計數器把所有計數器清清0 0。C虛擬存儲器

34、PPT課件請求式分頁存儲管理性能分析舉例1程序設計的質量2頁面的大小3分配的內存塊數4頁面置換算法性能圖1 FIFO算法性能分析（m=3） 圖2 FIFO算法性能分析（m=4）圖3 LRU算法性能分析（m=3）圖4 LRU算法性能分析（m=4） 返回本節C虛擬存儲器PPT課件3 缺頁中斷率分析(1)分配給作業的主存塊數(2)頁面的大小(3)程序編程方法(4)頁面調度算法C虛擬存儲器PPT課件4.9 請求分段存儲管理方式1段表機制2缺段中斷機構3請求式分段動態地址變換過程4請求式分段存儲管理的優、缺點 與請求分頁系統類似，在分段的基礎上增加與請求分頁系統類似，在分段的基礎上增加請求調請求調段段

35、功能和功能和段置換段置換功能，便可形成具有虛擬存儲器功能的功能，便可形成具有虛擬存儲器功能的請求分段系統。請求分段系統。 為實現請求分段式存儲管理為實現請求分段式存儲管理,需要有一定的硬件和需要有一定的硬件和相應的軟件支持。所需要的硬件支持有相應的軟件支持。所需要的硬件支持有,段表機制段表機制、缺缺段中斷機構段中斷機構以及以及地址變換機構地址變換機構等。等。圖:分段的邏輯地址空間1段表 為了實現動態地址變換和存儲保護，系統要為每一個作業建立一張段表。段表是進行段調度的主要依據。段表中的每一個表目對應著作業地址空間的一個程序段，其一般格式為：段名段長段的基址存取方式訪問字段 A修改位M狀態位P擴

36、充位輔存始址C虛擬存儲器PPT課件2缺段中斷機構 在請求分段式存儲管理中,當所要訪問的段尚未調入主存時,則由缺段中斷機構產生一個缺段中斷信號,請求操作系統將所要訪問的段調入主存。處理過程如下。處理過程如下: (1)空間分配空間分配; (2)修改段表修改段表; (3)新的段被裝入后應讓作業重新執行被中斷的指令新的段被裝入后應讓作業重新執行被中斷的指令,這這時就能在主存中找到所要訪問的段時就能在主存中找到所要訪問的段,可以繼續執行下去。可以繼續執行下去。3請求式分段動態地址變換過程圖4.28 請求式分段動態地址變換C虛擬存儲器PPT課件4請求分段式存儲管理的優缺點請求式分段存儲管理有如下優點：（1

37、）可提供大容量的虛存 （2）允許動態增加段的長度 （3）便于段的動態鏈接 （4）便于實現程序段的共享 （5）便于實現存儲保護C虛擬存儲器PPT課件請求分段存儲管理的缺點是進行地址變換和實現緊湊操作要花費處理機時間，為管理各分段要設立若干表格，需提供額外的存儲空間，而且也會像請求分頁存儲管理一樣出現系統抖動現象。C虛擬存儲器PPT課件一、選擇題一、選擇題1、頁式虛擬存儲管理的主要特點是（頁式虛擬存儲管理的主要特點是（ ）。）。 A、不要求將作業裝入到主存的連續區域不要求將作業裝入到主存的連續區域 B、不要求將作業同時全部裝入到主存的連續區域不要求將作業同時全部裝入到主存的連續區域 C、不要求進行

38、缺頁中斷處理不要求進行缺頁中斷處理 D、不要求進行頁面置換不要求進行頁面置換2、局部性有兩種形式：時間局限性和（局部性有兩種形式：時間局限性和（ ）。）。 A、指令局部性指令局部性 B、數據局部性數據局部性 C、空間局部性空間局部性 D、以上全部以上全部3、虛擬存儲系統的基礎是程序的局部性理論，此理論的基本含義是（虛擬存儲系統的基礎是程序的局部性理論，此理論的基本含義是（ ）。）。 A、程序執行時對主存的訪問是不均勻的程序執行時對主存的訪問是不均勻的 B、代碼的順序執行代碼的順序執行 C、變量的連續訪問變量的連續訪問 D、以上全部以上全部4、作業在執行中發生缺頁中斷，經操作系統處理后，應讓其執行（作業在執行中發生缺頁中斷，經操作系統處理后，應讓其執行（ ）指令。）指令。 A、被中斷的前一條被中斷的前一條 B、被中斷的那一條被中斷