最近最少使用演算法（LRU）——頁面置換

原創

上一篇博客寫了先進先出演算法（FIFO）——頁面置換：http://www.cnblogs.com/chiweiming/p/9058438.html

此篇介紹最近最少使用演算法（LRU）——頁面置換，與上一篇的代碼大同小異，只是用了不同的方法從頁面隊列

中選出需要淘汰出的頁面。（題目闡述看我上一篇博客）

還是辣個慄子：

現記憶體頁面為：　　15　　31　　24　　17　　18　　5　　9　　26　　4　　21

部分地址流為：　　4　　31　　24　　17　　18　　26　　17　　5　　5　　9　　31　　18　　18　　21　　15　　8

頁面 8 為下一個需要調入進去的頁面，由於記憶體頁面已滿，需要使用LRU調出一個最近未被使用頁面。

尋找淘汰頁面的方式如下：

從頁面 8 往前看，遇到與記憶體頁面中相同的頁面即把它移除（即不淘汰它），等到移除了 max_page-1 個頁面之

後，剩下最後一個未被移除的頁面即是需要淘汰出去的。

在上面例子中，依次將 15 21 18 31 9 5 17 26 24 （已經9個），剩下最後一個 4 即是需要淘汰出去的頁面。

可以用這樣的偽代碼去實現：用一個數組 flag 來備份記憶體頁塊號中的頁面，從 8 往前看，依次將之前的數和數組

里的數比較，若匹配成功，則將數組裡面此位置 -1 ，等到置了 max_page-1 個 -1 後跳出；再從 flag 中篩選出不

是 -1 的值（即要淘汰出的頁面），再拿此值和當前記憶體頁面隊列中的值比較，匹配成功則將此頁面調出去，將頁

面 8 調入。

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define max_page 10    //記憶體頁面數

int Page[320]={0};    //虛擬存儲區,存儲320條指令,32個頁面 
int Page_flu[320]={0};    //存儲320個頁地址流
int count=0;    //計算隨機產生的指令條數
double lack_page=0;    //記錄缺頁數 
int count_page=max_page;     //計算隊列空頁面個數 
int flag[max_page+1]={0};    //存儲記憶體塊中的頁面號 
int ff=0;

struct Memo{    //用結構體存儲記憶體頁面塊
    int num;     //給每個頁面編號,方便將其從隊列中找到並調出
    int a;
    struct Memo *next;
};

int Judge_Page(int value){    //輸入指令,返回指令對面的頁面號 
    return value/10;
}

int scan_queen(struct Memo *hear,int value){    //value代表頁面號,掃描隊列,缺頁返回0,否則返回1
    struct Memo *move;
    move=hear->next;
    while(move!=NULL){
        if(move->a==value){
            return 1;
        }
        move=move->next;
    }
    return 0;
}

void print(struct Memo *hear){    //輸出記憶體頁面
    struct Memo *move;
    move=hear->next;
    printf("當前頁面隊列為： ");
    while(move!=NULL){
        printf("%d ",move->a);
        move=move->next;
    }
    printf("\n");
}

void insert(struct Memo *hear,int value,int ZL,int x){    //將頁面value調入記憶體,ZL為對應指令,x為頁面value在頁地址流中的序號 
    if(count_page>=1){    //記憶體頁面空間充足
        struct Memo *move;
        move=hear->next;
        while(move->a!=-1){
            move=move->next;
        }
        move->a=value;    //將頁面調入
        count_page--;
        printf("頁面 %d 被調入————對應指令為: %d \n",value,ZL);
    }
    else{    //記憶體空間不足，使用LRU選出需調出的頁面後，將頁面value後調入
        struct Memo *move;
        move=hear->next;
        int i=0;
        for(i=1;i<=max_page;i++){
            flag[i]=move->a;    //將記憶體塊中的頁面號放入flag備份 
            move=move->next; 
        }
        int t=0;
        for(t=x-1;t>=0;t--){    //迴圈結束後flag裡面只有一個不為0,把此頁面調出即可
            for(i=max_page;i>=1;i--){
                if(Page_flu[t]==flag[i]){
                    flag[i]=-1;
                    ff++;
                    break;
                }
            }
            if(ff==max_page-1){
                break;
            }
        }
        for(i=1;i<=max_page;i++){    //選出被淘汰出的頁面號
            if(flag[i]!=-1){
                ff=flag[i];    //備份要淘汰出的頁面號 
                break;
            }
        }
        move=hear->next;
        while(move!=NULL){
            if(move->a==ff){
                int j=0;
                printf("前20個地址流為："); 
                for(j=x-20;j<=x-1;j++){
                    printf("%d ",Page_flu[j]);
                }
                printf("\n");
                printf("頁面 %d 被調出,頁面 %d 被調入----指令為：%d \n",ff,value,ZL);
                move->a=value;    //將頁面插入
                break; 
            }
            move=move->next;
        }
    }
    
    ff=0;
    print(hear);    //調入後輸出記憶體隊列 
}

void LRU(struct Memo *hear){
    int i=0;
    for(i=0;i<=319;i++){    //迴圈掃描頁面
        if( scan_queen(hear,Page_flu[i])==0){    //判斷是否缺頁
            lack_page++;
            insert(hear,Page_flu[i],Page[i],i);    //缺頁將頁面調入記憶體
        }
        else{    //不缺頁
            printf("指令 %d 對應頁面 %d 已在記憶體\n",Page[i],Page_flu[i]);
        }
        //不缺頁無需操作
    }
}

void Pro_Page(){    //形成頁地址流函數 
    int m=0;    //在[0,319]的指令地址之間隨機選取一起點m
    m=rand()%320;
    
    Page[count]=m;
    count++;
    if(count==320){
        return;
    }
    int m_=0;    //在前地址[0,m+1]中隨機選取一條指令並執行
    m_=rand()%(m+1);
    
    Page[count]=m_;
    count++;
    if(count==320){
        return;
    }
    Page[count]=m_+1;
    count++;
    if(count==320){
        return;
    }
    int m__=0;
    m__=(m_+2)+rand()%( 319-(m_+2)+1 );    //在後地址[m_+2,319]的指令地址之間隨機選取一條指令並執行
    Page[count]=m__;
    count++;
    if(count==320){
        return;
    }
    
    Pro_Page();
}

void Flu(){    //將指令轉換為頁地址流
    int i=0;
    for(i=0;i<=319;i++){
        Page_flu[i]=Judge_Page( Page[i] );
    }
}

int main(){
    struct Memo Stu[max_page+1];
    struct Memo *hear;
    hear=&Stu[0];
    //*************************************
    int i=0;
    for(i=0;i<=max_page;i++){    //形成記憶體頁面隊列
        if(i==max_page){
            Stu[i].a=-1;
            Stu[i].next=NULL;
            Stu[i].num=i;
            break;
        }
        Stu[i].next=&Stu[i+1];
        Stu[i].a=-1;
        Stu[i].num=i;
    }
    //*************************************
    srand(time(0));    //放在Pro_Page函數外面
    Pro_Page();    //形成頁地址流
    Flu();    //形成頁地址流 
    /*
    printf("頁地址流：\n");
    for(i=0;i<=319;i++){    //輸出頁地址流
        printf("%d ",Page[i]);
        if(i%3==0 && i!=0){
            printf("\n");
        }
    }
    printf("\n");
    */
    //*************************************
    
    LRU(hear);
    printf("缺頁次數為： %0.0lf\n",lack_page);
    printf("命中率為：%lf\n",1-lack_page/320);
    
    return 0;
}

（部分結果截圖）

08:31:06

2018-05-22