幾種頁面置換算法的基本原理及實現方法

黃鳳艷

（赤峰學院計算機科學與技術系，內蒙古赤峰024000）

幾種頁面置換算法的基本原理及實現方法

黃鳳艷

（赤峰學院計算機科學與技術系，內蒙古赤峰024000）

本文介紹了計算機專業研究生考試中操作系統考研大綱要求的四種全局頁面置換算法的基本原理及實現方法.

頁面；置換算法；基本原理；實現方法

在多道程序的正常運行過程中，屬于不同進程的頁面被分散存放在主存頁框中，當正在運行的進程所訪問的頁面不在內存時，系統會發生缺頁中斷，在缺頁中斷服務程序中會將所缺的頁面調入內存，如內存已無空閑頁框，缺頁中斷服務程序就會調用頁面置換算法，頁面置換算法的目的就是選出一個被淘汰的頁面.把內存和外存統一管理的真正目的是把那些被訪問概率非常高的頁存放在內存中.因此，置換算法應該置換那些被訪問概率最低的頁，將它們移出內存.

1 最佳置換算法

基本原理：淘汰以后不再需要的或最遠的將來才會用到的頁面.這是1966年Belady提出的理想算法，但無法實現，主要用于評價其他置換算法.

例：分配給某進程的內存頁面數是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，其內存動態分配過程如下：

70120304230321201 77722222222222222 0000004440000000 111333333331111

2 先進先出置換算法

基本原理：總是選擇在內存駐留時間最長的一頁面將其淘汰.

實現方法：建立一個隊列，隊列長度為系統分配給該進程的內存頁面數.如果所訪問的頁面不在內存中：當內存有空閑時，將訪問的頁面號；當內存沒有空閑時，淘汰隊首頁面，將訪問的頁面號插入隊尾.如果所訪問的頁面在內存中則隊列無變化.

例：分配給某進程的內存頁面數是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

隊列變化如下所示：

3 最近最少使用置換算法

基本原理：淘汰的頁面是在最近一段時間內最久未被訪問的那一頁，它是基于程序局部性原理來考慮的，認為那些剛被使用過的頁面可能還要立即被使用，而那些在較長時間內未被使用的頁面可能不會立即被使用.

實現方法：建立一個堆棧，堆棧的容量為系統分配給該進程的內存頁面數.當正在運行的進程訪問某頁面時，如該頁面不在內存時，則判斷內存是否已無空閑頁框：①尚有空閑頁框，則將訪問的頁面入棧.②無空閑頁框，則淘汰棧底的頁面，然后將訪問的頁面入棧；如訪問的頁面在內存中，則直接將它提到棧頂.

例：分配給某進程的內存頁面數是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

堆棧變化如下所示：

4 時鐘頁面置換算法

基本原理：把進程已調入內存的頁面鏈接成循環隊列，形成類似于鐘表面的環形表，用指針指向循環隊列中下一個將被替換的頁面.

實現方法：

①一個頁面首次裝入內存時，其“引用位”置0；

②內存中的任何一個頁面被訪問時，其“引用位”置1；

③淘汰頁面時，存儲管理從指針當前指向的頁面開始掃描循環隊列，把所遇到的“引用位”是1的頁面的“引用位”清0，并跳過這個頁面；把所遇到的“引用位”是0的頁面淘汰，指針推進一步；

④掃描循環隊列時，如果遇到所有頁面的“引用位”均為1，指針就會環繞整個循環隊列一圈，把碰到的所有頁面的“引用位”清0；指針停在起始位置，并淘汰這一頁，然后指針推進一步.

例：分配給某進程的內存頁面數是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

注：有星號的頁面表示其引用位為1，否則為0，“→”表示指針的當前位置.

內存動態分配過程如下：

70120304230321201 77722224444333300 0000000222221111 111333330000222

〔1〕孫鐘秀.操作系統教程(第4版)[M].高等教育出版社, 2008.

〔2〕張堯學,史美林,張高.計算機操作系統教程(第3版)[M].清華大學出版社，2006.

TP316.7

A

1673-260X（2010）11-0018-02