頁面置換算法

在地址映射過程中,若在頁面中發現所要訪問的頁面不在記憶體中,則產生缺頁中斷。當發生缺頁中斷時,如果作業系統記憶體中沒有空閒頁面,則作業系統必須在記憶體選擇一個頁面將其移出記憶體,以便為即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換算法。

常見的置換算法

最佳置換算法(OPT)

這是一種理想情況下的頁面置換算法,但實際上是不可能實現的。該算法的基本思想是:發生缺頁時,有些頁面在記憶體中,其中有一頁將很快被訪問(也包含緊接著的下一條指令的那頁),而其他頁面則可能要到10、100或者1000條指令後才會被訪問,每個頁面都可 以用在該頁面首次被訪問前所要執行的指令數進行標記。最佳頁面置換算法只是簡單地規定:標記最大的頁應該被置換。這個算法唯一的一個問題就是它無法實現。當缺頁發生時,作業系統無法知道各個頁面下一次是在什麼時候被訪問。雖然這個算法不可能實現,但是最佳頁面置換算法可以用於對可實現算法的性能進行衡量比較。

先進先出置換算法(FIFO)

最簡單的頁面置換算法是先入先出(FIFO)法。這種算法的實質是,總是選擇在主存中停留時間最長(即最老)的一頁置換,即先進入記憶體的頁,先退出記憶體。理由是:最早調入記憶體的頁,其不再被使用的可能性比剛調入記憶體的可能性大。建立一個FIFO佇列,收容所有在記憶體中的頁。被置換頁面總是在佇列頭上進行。當一個頁面被放入記憶體時,就把它插在隊尾上。

這種算法只是在按線性順序訪問地址空間 時才是理想的,否則效率不高。因為那些常被訪問的頁,往往在主存中也停留得最久,結果它們因變“老”而不得不被置換出去。

FIFO的另一個缺點是,它有一種異常現象,即在增加存儲塊的情況下,反而使缺頁中斷率增加了。當然,導致這種異常現象的頁面走向實際上是很少見的。

最近最久未使用(LRU)算法

FIFO算法和OPT算法之間的主要差別是,FIFO算法利用頁面進入記憶體後的時間長短作為置換依據,而OPT算法的依據是將來使用頁面的時間。如果以最近的過去作為不久將來的近似,那么就可以把過去最長一段時間裡不曾被使用的頁面置換掉。它的實質是,當需要置換一頁時,選擇在之前一段時間裡最久沒有使用過的頁面予以置換。這種算法就稱為最久未使用算法(Least Recently Used,LRU)。

LRU算法是與每個頁面最後使用的時間有關的。當必須置換一個頁面時,LRU算法選擇過去一段時間裡最久未被使用的頁面。

LRU算法是經常採用的頁面置換算法,並被認為是相當好的,但是存在如何實現它的問題。LRU算法需要實際硬體的支持。其問題是怎么確定最後使用時間的順序,對此有兩種可行的辦法:

1.計數器。最簡單的情況是使每個頁表項對應一個使用時間欄位,並給CPU增加一個邏輯時鐘或計數器。每次存儲訪問,該時鐘都加1。每當訪問一個頁面時,時鐘暫存器的內容就被複製到相應頁表項的使用時間欄位中。這樣我們就可以始終保留著每個頁面最後訪問的“時間”。在置換頁面時,選擇該時間值最小的頁面。這樣做, 不僅要查頁表,而且當頁表改變時(因CPU調度)要 維護這個頁表中的時間,還要考慮到時鐘值溢出的問題。

2.棧。用一個棧保留頁號。每當訪問一個頁面時,就把它從棧中取出放在棧頂上。這樣一來,棧頂總是放有目前使用最多的頁,而棧底放著目前最少使用的頁。由於要從棧的中間移走一項,所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下,移走一頁並把它放在棧頂上需要改動6個指針。每次修改都要有開銷,但需要置換哪個頁面卻可直接得到,用不著查找,因為尾指針指向棧底,其中有被置換頁。

因實現LRU算法必須有大量硬體支持,還需要一定的軟體開銷。所以實際實現的都是一種簡單有效的LRU近似算法。

一種LRU近似算法是最近未使用算法(Not Recently Used,NUR)。它在存儲分塊表的每一表項中增加一個引用位,作業系統定期地將它們置為0。當某一頁被訪問時,由硬體將該位置1。過一段時間後,通過檢查這些位可以確定哪些頁使用過,哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去,因為在之前最近一段時間裡它未被訪問過。

4)Clock置換算法(LRU算法的近似實現)

5)最少使用(LFU)置換算法

在採用最少使用置換算法時,應為在記憶體中的每個頁面設定一個移位暫存器,用來記錄該頁面被訪問的頻率。該置換算法選擇在之前時期使用最少的頁面作為淘汰頁。由於存儲器具有較高的訪問速度,例如100 ns,在1 ms時間內可能對某頁面連續訪 問成千上萬次,因此,通常不能直接利用計數器來記錄某頁被訪問的次數,而是採用移位暫存器方式。每次訪問某頁時,便將該移位暫存器的最高位置1,再每隔一定時間(例如100 ns)右移一次。這樣,在最近一段時間使用最少的頁面將是∑Ri最小的頁。

LFU置換算法的頁面訪問圖與LRU置換算法的訪問圖完全相同;或者說,利用這樣一套硬體既可實現LRU算法,又可實現LFU算法。應該指出,LFU算法並不能真正反映出頁面的使用情況,因為在每一時間間隔內,只是用暫存器的一位來記錄頁的使用情況,因此,訪問一次和訪問10 000次是等效的。

6)工作集算法

7)工作集時鐘算法

8)老化算法(非常類似LRU的有效算法)

9)NRU(最近未使用)算法

10)第二次機會算法

第二次機會算法的基本思想是與FIFO相同的,但是有所改進,避免把經常使用的頁面置換出去。當選擇置換頁面時,檢查它的訪問位。如果是 0,就淘汰這頁;如果訪問位是1,就給它第二次機會,並選擇下一個FIFO頁面。當一個頁面得到第二次機會時,它的訪問位就清為0,它的到達時間就置為當前時間。如果該頁在此期間被訪問過,則訪問位置1。這樣給了第二次機會的頁面將不被淘汰,直至所有其他頁面被淘汰過(或者也給了第二次機會)。因此,如果一個頁面經常使用,它的訪問位總保持為1,它就從來不會被淘汰出去。

第二次機會算法可視為一個環形佇列。用一個指針指示哪一頁是下面要淘汰的。當需要一個 存儲塊時,指針就前進,直至找到訪問位是0的頁。隨著指針的前進,把訪問位就清為0。在最壞的情況下,所有的訪問位都是1,指針要通過整個佇列一周,每個頁都給第二次機會。這時就退化成FIFO算法了。

作業系統頁面置換算法代碼

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h> #define TRUE 1

#define FALSE 0

#define INVALID -1

#define NUL 0

#define total_instruction 320 /*指令流長*/

#define total_vp 32 /*虛頁長*/

#define clear_period 50 /*清零周期*/

typedef struct{ /*頁面結構*/

int pn,pfn,counter,time;

}pl_type;

pl_type pl[total_vp]; /*頁面結構數組*/

struct pfc_struct{ /*頁面控制結構*/

int pn,pfn;

struct pfc_struct *next;

};

typedef struct pfc_struct pfc_type;

pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;

int diseffect,a[total_instruction];

int page[total_instruction], offset[total_instruction];

void initialize(int);

void FIFO(int);

void LRU(int);

void NUR(int);

int main()

{

int S,i;

srand((int)getpid());

S=(int)rand()%390;

for(i=0;i<total_instruction;i+=1) /*產生指令佇列*/

{

a[i]=S; /*任選一指令訪問點*/

a[i+1]=a[i]+1; /*順序執行一條指令*/

a[i+2]=(int)rand()%390; /*執行前地址指令m’*/

a[i+3]=a[i+2]+1; /*執行後地址指令*/

S=(int)rand()%390;

}

for(i=0;i<total_instruction;i++) /*將指令序列變換成頁地址流*/

{

page[i]=a[i]/10;

offset[i]=a[i]%10;

}

for(i=4;i<=32;i++) /*用戶記憶體工作區從4個頁面到32個頁面*/

{

printf("%2d page frames",i);

FIFO(i);

LRU(i);

NUR(i);

printf("\n");

}

return 0;

}

void FIFO(int total_pf) /*FIFO(First in First out)ALGORITHM*/

/*用戶進程的記憶體頁面數*/

{

int i;

pfc_type *p, *t;

initialize(total_pf); /*初始化相關頁面控制用數據結構*/

busypf_head=busypf_tail=NUL; /*忙頁面佇列頭,對列尾連結*/

for(i=0;i<total_instruction;i++)

{

if(pl[page[i]].pfn==INVALID) /*頁面失效*/

{

diseffect+=1; /*失效次數*/

if(freepf_head==NUL) /*無空33閒頁面*/

{

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID; /*釋放忙頁面佇列中的第一個頁面*/

freepf_head=busypf_head;

freepf_head->next=NUL;

busypf_head=p;

}

p=freepf_head->next; /*按方式調新頁面入記憶體頁面*/

freepf_head->next=NUL;

freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn;

if(busypf_tail==NUL)

busypf_head=busypf_tail=freepf_head;

else

{

busypf_tail->next=freepf_head;

busypf_tail=freepf_head;

}

freepf_head=p;

}

}

printf("FIFO:%6.4F",1-(float)diseffect/320);

}

void LRU(int total_pf)

{

int min,minj,i,j,present_time;

initialize(total_pf);present_time=0;

for(i=0;i<total_instruction;i++)

{

if(pl[page[i]].pfn==INVALID) /*頁面失效*/

{

diseffect++;

if(freepf_head==NUL) /*無空閒2頁面*/

{

min=32767;

for(j=0;j<total_vp;j++)

if(min>pl[j].time&&pl[j].pfn!=INVALID)

{

min=pl[j].time;

minj=j;

}

freepf_head=&pfc[pl[minj].pfn];

pl[minj].pfn=INVALID;

pl[minj].time=-1;

freepf_head->next=NUL;

}

pl[page[i]].pfn=freepf_head->pfn;

pl[page[i]].time=present_time;

freepf_head=freepf_head->next;

}

else

pl[page[i]].time=present_time;

present_time++;

}

printf("LRU:%6.4f",1-(float)diseffect/320);

}

void NUR(int total_pf)

{

int i,j,dp,cont_flag,old_dp;

pfc_type *t;

initialize(total_pf);

dp=0;

for(i=0;i<total_instruction;i++)

{

if(pl[page[i]].pfn==INVALID) /*頁面失效*/

{

diseffect++;

if(freepf_head==NUL) /*無空閒1頁面*/

{

cont_flag=TRUE;old_dp=dp;

while(cont_flag)

if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)

cont_flag=FALSE;

else

{

dp++;

if(dp==total_vp)

dp=0;

if(dp==old_dp)

for(j=0;j<total_vp;j++)

pl[j].counter=0;

}

freepf_head=&pfc[pl[dp].pfn];

pl[dp].pfn=INVALID;

freepf_head->next=NUL;

}

pl[page[i]].pfn=freepf_head->pfn;

freepf_head=freepf_head->next;

}

else

pl[page[i]].counter=1;

if(i%clear_period==0)

for(j=0;j<total_vp;j++)

pl[j].counter=0;

}

printf("NUR:%6.4f",1-(float)diseffect/320);

}

void initialize(int total_pf) /*初始化相關數據結構*/

/*用戶進程的記憶體頁面數*/

{

int i;

diseffect=0;

for(i=0;i<total_vp;i++)

{

pl[i].pn=i;pl[i].pfn=INVALID; /*置頁面控制結構中的頁號,頁面為空*/

pl[i].counter=0;pl[i].time=-1; /*頁面控制結構中的訪問次數為0,時間為-1*/

}

for(i=1;i<total_pf;i++)

{

pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之間的連線*/

}

pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;

freepf_head=&pfc[0]; /*頁面佇列的頭指針為pfc[0]*/

}

/*說明:本程式在Linux的gcc下和c-free下編譯運行通過*/

相關詞條

相關搜尋

熱門詞條

聯絡我們