黃鳳艷

（赤峰學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，內(nèi)蒙古赤峰024000）

幾種頁面置換算法的基本原理及實(shí)現(xiàn)方法

黃鳳艷

（赤峰學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，內(nèi)蒙古赤峰024000）

本文介紹了計(jì)算機(jī)專業(yè)研究生考試中操作系統(tǒng)考研大綱要求的四種全局頁面置換算法的基本原理及實(shí)現(xiàn)方法.

頁面；置換算法；基本原理；實(shí)現(xiàn)方法

在多道程序的正常運(yùn)行過程中，屬于不同進(jìn)程的頁面被分散存放在主存頁框中，當(dāng)正在運(yùn)行的進(jìn)程所訪問的頁面不在內(nèi)存時(shí)，系統(tǒng)會(huì)發(fā)生缺頁中斷，在缺頁中斷服務(wù)程序中會(huì)將所缺的頁面調(diào)入內(nèi)存，如內(nèi)存已無空閑頁框，缺頁中斷服務(wù)程序就會(huì)調(diào)用頁面置換算法，頁面置換算法的目的就是選出一個(gè)被淘汰的頁面.把內(nèi)存和外存統(tǒng)一管理的真正目的是把那些被訪問概率非常高的頁存放在內(nèi)存中.因此，置換算法應(yīng)該置換那些被訪問概率最低的頁，將它們移出內(nèi)存.

1 最佳置換算法

基本原理：淘汰以后不再需要的或最遠(yuǎn)的將來才會(huì)用到的頁面.這是1966年Belady提出的理想算法，但無法實(shí)現(xiàn)，主要用于評(píng)價(jià)其他置換算法.

例：分配給某進(jìn)程的內(nèi)存頁面數(shù)是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，其內(nèi)存動(dòng)態(tài)分配過程如下：

70120304230321201 77722222222222222 0000004440000000 111333333331111

2 先進(jìn)先出置換算法

基本原理：總是選擇在內(nèi)存駐留時(shí)間最長(zhǎng)的一頁面將其淘汰.

實(shí)現(xiàn)方法：建立一個(gè)隊(duì)列，隊(duì)列長(zhǎng)度為系統(tǒng)分配給該進(jìn)程的內(nèi)存頁面數(shù).如果所訪問的頁面不在內(nèi)存中：當(dāng)內(nèi)存有空閑時(shí)，將訪問的頁面號(hào)；當(dāng)內(nèi)存沒有空閑時(shí)，淘汰隊(duì)首頁面，將訪問的頁面號(hào)插入隊(duì)尾.如果所訪問的頁面在內(nèi)存中則隊(duì)列無變化.

例：分配給某進(jìn)程的內(nèi)存頁面數(shù)是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

隊(duì)列變化如下所示：

3 最近最少使用置換算法

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

實(shí)現(xiàn)方法：建立一個(gè)堆棧，堆棧的容量為系統(tǒng)分配給該進(jìn)程的內(nèi)存頁面數(shù).當(dāng)正在運(yùn)行的進(jìn)程訪問某頁面時(shí)，如該頁面不在內(nèi)存時(shí)，則判斷內(nèi)存是否已無空閑頁框：①尚有空閑頁框，則將訪問的頁面入棧.②無空閑頁框，則淘汰棧底的頁面，然后將訪問的頁面入棧；如訪問的頁面在內(nèi)存中，則直接將它提到棧頂.

例：分配給某進(jìn)程的內(nèi)存頁面數(shù)是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

堆棧變化如下所示：

4 時(shí)鐘頁面置換算法

基本原理：把進(jìn)程已調(diào)入內(nèi)存的頁面鏈接成循環(huán)隊(duì)列，形成類似于鐘表面的環(huán)形表，用指針指向循環(huán)隊(duì)列中下一個(gè)將被替換的頁面.

實(shí)現(xiàn)方法：

①一個(gè)頁面首次裝入內(nèi)存時(shí)，其“引用位”置0；

②內(nèi)存中的任何一個(gè)頁面被訪問時(shí)，其“引用位”置1；

③淘汰頁面時(shí)，存儲(chǔ)管理從指針當(dāng)前指向的頁面開始掃描循環(huán)隊(duì)列，把所遇到的“引用位”是1的頁面的“引用位”清0，并跳過這個(gè)頁面；把所遇到的“引用位”是0的頁面淘汰，指針推進(jìn)一步；

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

例：分配給某進(jìn)程的內(nèi)存頁面數(shù)是3頁，頁面地址流如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1.

注：有星號(hào)的頁面表示其引用位為1，否則為0，“→”表示指針的當(dāng)前位置.

內(nèi)存動(dòng)態(tài)分配過程如下：

70120304230321201 77722224444333300 0000000222221111 111333330000222

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

〔2〕張堯?qū)W,史美林,張高.計(jì)算機(jī)操作系統(tǒng)教程(第3版)[M].清華大學(xué)出版社，2006.

TP316.7

A

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