LRU算法实验报告

实验题目

1. 最近最久未使用（LRU）置换算法原理 就是：当需要淘汰某页面时，选择当前 一段时间内最久未使用过的页先淘汰， 即淘汰距当前最远的上次使用的页。

   • 例如: 分配给该进程的页块数为3，一个20位 长的页面访问序列为 :12560,36536,56042,70435， 则缺页次数和缺页率按下图给出:
     

2. 假定分配给该进程的页块数为3，页面访问序 列长度为20。本实验可以采用数组结构实现， 首先随机产生页面序列，当发生请求调页时， 若内存已满，则需要利用LRU算法，将当前一 段时间内最久未使用过的页替换出去
   

思考题：比较LRU和其他置换算法各自的优缺点，能够 实现其他置换算法模拟设计，分析内存页面数的变化对各种置换算法命中率的影响

答：内存页面数越多，命中率越高。LRU算法可以减少页错误率,较易理解。最优算法页错误最低,且没有 Belady 异常,但是较难实现。FIFO算法容易理解和实现,但是页错误率较高

数据结构以及符号说明

int sequence[20];   //随机生成序列
bool missing[20];   //是否命中
class process_memory
{
public:
    int block[20][3];   // 20次读取，3个页块的内容
    //bool missing[20];
    int priority[3]; // priority[0]最先被替换
    int missing_number;   //未命中次数
    double missing_number_percentage; //未命中率

    process_memory()      //初始化
    {
        for (int i = 0; i < 20; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                this->block[i][j] = -1;  //-1表示页块为空
            }
        }
        //for (int i = 0; i < 20; i++)
        //{
        //    missing[i] = true;
        //}
        priority[0] = 0;          //最先被替换的是页块0
        priority[1] = 1;
        priority[2] = 2;
        missing_number = 0;
        missing_number_percentage = 0;
    }
    void percentage_count()          //计算命中率
    {
        missing_number_percentage = missing_number / 20.0;
    }
};

源代码及注释

#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;

int sequence[20];   //随机生成序列
bool missing[20];   //是否命中
class process_memory
{
public:
    int block[20][3];   // 20次读取，3个页块的内容
    //bool missing[20];
    int priority[3]; // priority[0]最先被替换
    int missing_number;   //未命中次数
    double missing_number_percentage; //未命中率

    process_memory()      //初始化
    {
        for (int i = 0; i < 20; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                this->block[i][j] = -1;  //-1表示页块为空
            }
        }
        //for (int i = 0; i < 20; i++)
        //{
        //    missing[i] = true;
        //}
        priority[0] = 0;          //最先被替换的是页块0
        priority[1] = 1;
        priority[2] = 2;
        missing_number = 0;
        missing_number_percentage = 0;
    }
    void percentage_count()          //计算命中率
    {
        missing_number_percentage = missing_number / 20.0;
    }
};

void Randomized_Sequence(int *sequence)      //随机生成序列，并且初始化记录是否命中的数组
{
    for (int i = 0; i < 20; i++)
    {
        sequence[i] = rand() % 10;
    }
    for (int i = 0; i < 20; i++)
    {
        missing[i] = true;
    }
}
void display(process_memory &example)       //展示表格、未命中数、未命中率
{
    cout << "======================================================================================================================================================" << endl;
    cout << "sequence | ";
    for (int i = 0; i < 20; i++)
    {
        cout << setw(4) << sequence[i] << " | ";
    }
    cout << endl;
    for (int j = 0; j < 3; j++)
    {
        cout << "block " << j << "  | ";
        for (int i = 0; i < 20; i++)
        {
            cout << setw(4) << example.block[i][j] << " | ";
        }
        cout << endl;
    }
    cout << "missing  | ";
    for (int i = 0; i < 20; i++)
    {
        if (missing[i])
            cout << "miss | ";
        else
            cout << "hit  | ";
    }
    cout << endl;
    cout << "======================================================================================================================================================" << endl;
    cout << "missing number     : " << setw(10) << example.missing_number << endl;
    cout << "missing percentage : " << setw(10) << example.missing_number_percentage << endl;
}
void priority_rank(process_memory &example, int j) // 页块j设为最后被替换的，调整优先级
{
    if (example.priority[0] == j)
    {
        int tem = example.priority[0];
        example.priority[0] = example.priority[1];
        example.priority[1] = example.priority[2];
        example.priority[2] = tem;
        return;
    }
    else if (example.priority[1] == j)
    {
        int tem = example.priority[1];
        example.priority[0] = example.priority[0];
        example.priority[1] = example.priority[2];
        example.priority[2] = tem;
        return;
    }
    else if (example.priority[2] == j)
    {
        int tem = example.priority[2];
        example.priority[0] = example.priority[0];
        example.priority[1] = example.priority[1];
        example.priority[2] = tem;
        return;
    }
    else
    {
        int tem = example.priority[0];
        example.priority[0] = example.priority[1];
        example.priority[1] = example.priority[2];
        example.priority[2] = tem;
        return;
    }
}
void LRU(int *sequence, process_memory &example)  //LRU算法处理输入序列
{
    for (int i = 0; i < 20; i++)
    {
        bool is_miss = true;
        for (int j = 0; j < 3; j++)
        {
            if (sequence[i] == example.block[i][j])    //命中页块j
            {
                example.block[i][j] = sequence[i];
                missing[i] = false;
                priority_rank(example, j);              //页块j应该是最后被替换的
                is_miss=false;
                break;
            }
            else
            {
                is_miss = true;
                continue;
            }
        }
        if (is_miss)               //未命中
        {
            example.block[i][example.priority[0]] = sequence[i]; //最应该被替换的被替换
            missing[i]=true;
            example.missing_number++;
            priority_rank(example, example.priority[0]);    //因为被替换，优先级调整
        }
        for (int j = 0; j < 3; j++)
        {
            example.block[i+1][j] =example.block[i][j];    //继承状态给下一个
        }
        
    }
    example.percentage_count();                   //计算未命中率
    return;
}

int main()
{
    //初始化
    Randomized_Sequence(sequence);               
    process_memory example=process_memory();    
    display(example);
    //LRU
    LRU(sequence,example);
    display(example);
    return 0;
}

初值以及运行结果