LRU算法

简介

页面置换算法是请求分页存储管理中一个重要的因素。系统运行时，先进行内存分配：给进程分配一定的物理块数。然后将要页面依次调入内存，分配到物理块中。若物理块已满，就要采用页面置换算法选择一个页面置换出去，然后将所需要的下一个页面调入物理块中。

最近最久未使用页面淘汰算法（Least Recently Used，简称LRU）是淘汰最长时间未被访问的页面的算法。这是一种基于局部性原理的淘汰算法，该算法认为：如果一个页面刚被访问过，那么不久的将来被访问的可能性就大。

除了LRU算法，还有很多其它的算法，比如先进先出算法（FIFO），其做法是淘汰最早进入内存的页面，该算法认为：随着时间的推移，在内存中待的时间最长的页面，被访问的可能性最小。在实际中，这种算法有可能把经常要访问的页面淘汰出去。

思路分析

LRU算法流程图

模拟实现

程序同目录下的数据内容

data.txt

  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

银行家算法的C++模拟实现

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

const int MAXSIZE=1000;//定义最大页面数
const int NUM=3;//定义页框数（物理块数）

typedef struct node
{
    int loaded;   //记录该物理块存储的页面
    int time;     //记录该物理块没有被使用的时间
} page;

page pages[NUM]; //定义页框表 （物理块表）
int queue[MAXSIZE];
int quantity;

//初始化结构函数
void initial()
{
    int i;
    for(i=0;i<NUM;i++)
    {
        pages[i].loaded=-1;
    }
    for(i=0;i<MAXSIZE;i++)
        queue[i]=-1;
        quantity=0;
}

//读入页面流
void readData()
{
    FILE *fp;
    char fname[20];
    int i;
    cout<<"请输入页面流文件名:";
    cin>>fname;
    if((fp=fopen(fname,"r"))==NULL)
    {
        cout<<"错误,文件打不开,请检查文件名";
    }
    else
    {
        while(!feof(fp))
        {
            fscanf(fp,"%d ",&queue[quantity]);
            quantity++;
        }
    }
    cout<<"读入的页面流:";
    for(i=0;i<quantity;i++)
    {
        cout<<queue[i]<<" ";
    }
}

void addTime(){
    for(int i=0;i<NUM;i++){
        pages[i].time++;
    }
}

int findPageByLRU(){
    int i = 0;
    for(int j = 1;j < NUM; j++){
        if (pages[i].time < pages[j].time){
            i = j;
        }
    }
    return i;
}

//最近最少使用调度算法（LRU）
void LRU()
{
    int i,flag;
    int absence=0;  //记录缺页次数
    cout<<endl<<"----------------------------------------------------"<<endl;
    cout<<"最近最少使用调度算法（LRU）页面调出流:";
    for(i=0;i<NUM;i++)  //前3个进入内存的页面
    {
        pages[i].loaded=queue[i];
        pages[i].time=NUM-i;
    }
    absence=3;
    for(i=NUM;i<quantity;i++)
    {
        int j;
        flag=0;
        for(j=0;j<NUM;j++)  //判断当前需求的页面是否在内存
        {
            if(pages[j].loaded==queue[i])
            {
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            j = findPageByLRU();
            cout<<pages[j].loaded<<" ";
            pages[j].loaded=queue[i];
            absence++;
        }
        pages[j].time=0;

        addTime();
    }
    cout<<endl<<"总缺页数:"<<absence<<endl;
}


int main()
{
    cout<<"     /***********虚拟存储管理器的页面调度***********/"<<endl;
    initial();
    readData();
    LRU();

    return 0;
}

执行结果

result

参考资料

《计算机操作系统（第四版）》

操作系统LRU算法与C++模拟实现