页面置换算法模拟 最近最久未使用（LRU）算法

最近最久未使用（LRU）算法是一种基于页面访问历史的页面置换算法。它选择最久未使用的页面进行置换。当需要访问一个不在内存中的页面时，如果内存已满，则选择最久未使用的页面进行置换。LRU算法通过记录页面的访问时间戳来判断页面的使用频率。

最优（OPT）算法是一种理论上的最优页面置换算法，但在实际系统中难以实现。它基于未来的页面访问序列来选择最佳的置换页面。OPT算法假设系统能够预知未来的页面访问情况，从而选择在未来最长时间内不会被访问的页面进行置换。由于OPT算法需要预知未来的信息，因此在实际系统中无法应用。

缺页率是指在处理页面访问过程中进行页面置换的频率。在本实验中，我们可以通过统计每次页面访问时是否发生缺页来计算缺页率。具体地，当需要访问一个不在内存中的页面时，如果内存已满，则需要进行页面置换，此时发生一次缺页；如果内存未满，则直接将页面加载到内存中，不发生缺页。通过统计每次页面访问时的缺页次数，我们可以计算出不同页面置换算法在不同内存容量下的缺页率，并据此评估其性能表现。

LRU页面置换算法的流程可以简单描述如下：

1、随机生成页面引用：首先随机生成一系列的页面引用，这些页面引用代表了进程请求访问的页面序号。在本例中，我们生成了10个0到7之间的随机页面序号。

    2、用户输入物理块个数：接下来，系统提示用户输入进程被分配的物理块个数，即内存中可以同时容纳的页面数量。用户输入的数值应当是一个合理的值，通常不超过系统定义的最大页面总数。

    3、初始化物理块状态数组：根据用户输入的物理块个数，我们初始化一个物理内存块数组，用于模拟内存中的物理块。每个帧都包含一个页面号和一个时间值，分别表示当前帧中存储的页面序号和该页面最近一次被放入内存中的时间。

    4、页面置换：对于每个页面引用，我们检查它是否已经在内存中（即帧数组中是否有匹配的页面号）。如果在，则继续处理下一个页面引用；如果不在，则发生页面错误（缺页），我们需要从内存中选择一个页面进行置换。LRU算法选择最近最少使用的页面进行置换，即找到最长时间未被访问的页面，并将其从内存中移除，然后将新的页面引用加载到空闲的帧中。

     缺页率计算：在整个页面引用序列处理完毕后，我们统计页面错误的次数，并计算缺页率。缺页率是页面错误次数与总页面引用次数的比值，它反映了内存管理策略的效率。缺页率越低，表示内存管理策略越有效。

代码实现部分：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define MAX_PAGES 8    //假设页面总数为8
#define MAX_REFERENCES 10   //假设随机生成10个页面引用
int pageFaultsNum = 0;//页面错误 （缺页）计数
int pageReplaceNum = 0;//页面置换次数

//也框结构体，用于存储页面号和调入内存的时间
typedef struct
{
    int pageNumber;
    int time;
} Frame;

//初始化页框数组
void initializeFrames(Frame frames[],int maxFrames)
{
    for(int i = 0;i < maxFrames; i++)
    {
        frames[i].pageNumber = -1;//初始时页面号为-1，表示空闲
        frames[i].time = -1;//最近依次被放入物理块的时间
    }
}

//生成0~9之间的随机页面序号
int genRandomPage()
{
    return rand() % MAX_PAGES;
}

//LEU页面置换算法，并计算缺页率
double lruPageReplacement(Frame frames[], int maxFrames, int referenceString[],int length)
{
    int frameFull = 0;//物理块已被装入个数
    pageFaultsNum = 0;//页面错误（缺页）计数清零
    pageReplaceNum = 0;//页面置换次数清零
    for(int i = 0;i < length; i++)
    {
        bool found = false;//标记页面是否在内存中
        int j = 0;
        for(j = 0;j< maxFrames;j++)
        {
            if (frames[j].pageNumber == referenceString[i])
            {
                found = true;//如果找到，则标记为已经找到，跳出循环
                break;
            }
        }
        //如果页面不在内存中，则发生页面错误（缺页），需要调入内存
        if(!found)
        {
            pageFaultsNum++;//把缺页次数+1
            if(frameFull<maxFrames)//物理块未满，可直接将页面装入
            {
                frames[frameFull].pageNumber = referenceString[i];
                frames[frameFull].time = i;
                frameFull++;
            }
            else//物理块已装满，需要置换一页出去
            {
                int smallTime = MAX_REFERENCES;
                int lruFrame = -i;
                for(int j = 0;j < maxFrames;j++)//遍历锁业物理块，选出时间最早的哪那个页面
                {
                    if(frames[j].time < smallTime)
                        {
                            smallTime = frames[j].time;
                            lruFrame = j;
                        }
                }
                //替换最近最久未使用的帧，新页号直接写入内存块中，并更新时间
                frames[lruFrame].pageNumber = referenceString[i];
                frames[lruFrame].time = i;
                pageReplaceNum++;//置换次数加1
            }
        }
        else
        {//该页已在内存，只需要更新一下使用时间
            frames[j].time = i;
        }
    }
    //计算缺页率
    printf("\n页面缺页次数为：%d\n",pageFaultsNum);
    printf("页面置换次数为：%d\n",pageReplaceNum);
    double pageFaultRate = (double)pageFaultsNum / length;

    return pageFaultRate;
}

int main()
{
    while(1)
    {
        srand(time(NULL));//初始化随机数生成器
        int referenceString[MAX_REFERENCES];//存储随机生成的页面引用
        for(int i = 0;i< MAX_REFERENCES;i++)
            referenceString[i] = genRandomPage();//生成随机页面序号

        int maxFrames;//进程被分配的物理块个数
        printf("请输入进程被分配的物理块个数（不超过%d）：",MAX_PAGES);
        scanf("%d",&maxFrames);

        printf("随机生成的页面引用序列为：");
        for(int i = 0;i <MAX_REFERENCES;i++)
            printf("%d ",referenceString[i]);

        if(maxFrames <= 0|| maxFrames > MAX_PAGES)
        {
            printf("输入的物理块的个数无效，请输入1到%d之间的整数。\n",MAX_PAGES);
            return 1;
        }
        Frame frames[maxFrames];//初始化页框数组
        initializeFrames(frames,maxFrames);

        //调用LRU页面置换算法并计算缺页率
        double pageFaultRate = lruPageReplacement(frames,maxFrames,referenceString,MAX_REFERENCES);
        //输出结果
        printf("缺页率为：%.2f%%\n\n",pageFaultRate * 100);
    }
    return 0;
}
 

运行结果：

在原设置（页面总数8，页面引用序列10）的基础上，将物理块数设为3。

手动推导缺页和置换的过程：

	7	2	5	5	5	5	1	6	5	0
1	7	7	7	7	7	7	1	1	1	0
2		2	2	2	2	2	2	6	6	6
3			5	5	5	5	5	5	5	5
是否缺页	缺缺	缺缺	缺缺				缺缺	缺缺		缺缺

缺页率： 6  / 10 = 60%

​​​​​​​在原设置（页面总数8，页面引用序列10）的基础上，将物理块数设为5。

并手动推导缺页置换的过程，验证缺页率结果是否正确：

	7	0	0	1	1	0	2	4	7	7
1	7	7	7	7	7	7	7	7	7	7
2		0	0	0	0	0	0	0	0	0
3				1	1	1	1	1	1	1
4							2	2	2	2
5								4	4	4
是否缺页	缺	缺		缺			缺	缺

缺页率：5 / 10 = 50%

​​​​​​​修改代码，使得页面总数为10，页面序列为20，设定物理块数为3。

并手动推导缺页置换的过程，验证缺页率结果是否正确：

	9	4	8	9	3	6	2	0	1	8	8	0	0	2	2	8	8	8	2	9
1	9	9	9	9	9	9	2	2	2	8	8	8	8	8	8	8	8	8	8	8
2		4	4	4	3	3	3	0	0	0	0	0	0	0	0	0	0	0	0	9
3			8	8	8	6	6	6	1	1	1	1	1	2	2	2	2	2	2	2
是否缺页	缺	缺	缺		缺	缺	缺	缺	缺	缺				缺						缺

缺页率：11 / 20 = 55%