操作系统课程设计：常用页面置换算法（OPT、FIFO、LRU）的实现及缺页率的计算（C语言）

名人说：莫听穿林打叶声，何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》
Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）

目录

• • • 一、效果图
    • 二、代码（带注释）
    • 三、说明

一、效果图

二、代码（带注释）

//创作者：Code_流苏（CSDN）
//未经允许，禁止转载发布，可自己学习使用
//代码实现时期：大二操作系统期末
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define N 320 //指令数
#define M 32 //页数
#define P 4 //内存块数
#define Q 10 //每页指令数
int i, m, m1, m2, choice;
int order[N]; //指令序列数组

//OPT算法
void OPT(int order[])
{
    int i, j, k, max, index, count = 0;
    int memory[P]; //内存块数组
    int flag[M]; //标记数组，记录每个页面是否在内存中
    int next[M]; //记录每个页面下一次出现的位置

    //初始化内存块和标记数组
    for (i = 0; i < P; i++)
        memory[i] = -1;
    for (i = 0; i < M; i++)
        flag[i] = 0;

    //遍历指令序列
    for (i = 0; i < N; i++)
    {
        int page = order[i] / Q; //计算当前指令所在的页面号
        if (flag[page] == 1) //如果页面已经在内存中，显示物理地址
        {
            printf("指令%d的物理地址为%d\n", order[i], memory[page] * Q + order[i] % Q);
        }
        else //如果页面不在内存中，发生缺页
        {
            count++; //缺页次数加一
            int empty = -1; //记录是否有空闲的内存块
            for (j = 0; j < P; j++)
            {
                if (memory[j] == -1) //找到空闲的内存块
                {
                    empty = j;
                    break;
                }
            }
            if (empty != -1) //如果有空闲的内存块，直接调入页面
            {
                memory[empty] = page;
                flag[page] = 1;
                printf("指令%d的物理地址为%d\n", order[i], empty * Q + order[i] % Q);
            }
            else //如果没有空闲的内存块，需要进行页面置换
            {
                //计算每个页面下一次出现的位置
                for (j = 0; j < M; j++)
                {
                    next[j] = N + 1; //默认为无穷大
                    for (k = i + 1; k < N; k++)
                    {
                        if (order[k] / Q == j) //找到下一次出现的位置
                        {
                            next[j] = k;
                            break;
                        }
                    }
                }
                //找到下一次出现最晚的页面，即最佳置换页面
                max = next[memory[0]];
                index = 0;
                for (j = 1; j < P; j++)
                {
                    if (next[memory[j]] > max)
                    {
                        max = next[memory[j]];
                        index = j;
                    }
                }
                //置换该页面，并显示物理地址
                flag[memory[index]] = 0;
                memory[index] = page;
                flag[page] = 1;
                printf("指令%d的物理地址为%d\n", order[i], index * Q + order[i] % Q);
            }
        }
    }
    printf("OPT算法的缺页率为%.2f%%\n", count * 100.0 / N); //显示缺页率
}

//FIFO算法
void FIFO(int order[])
{
    int i, j,  index, count = 0;
    int memory[P]; //内存块数组
    int flag[M]; //标记数组，记录每个页面是否在内存中
    int queue[P]; //队列数组，记录每个内存块中的页面进入的先后顺序

    //初始化内存块、标记数组和队列数组
    for (i = 0; i < P; i++)
        memory[i] = -1;
    for (i = 0; i < M; i++)
        flag[i] = 0;
    for (i = 0; i < P; i++)
        queue[i] = -1;

    //遍历指令序列
    for (i = 0; i < N; i++)
    {
        int page = order[i] / Q; //计算当前指令所在的页面号
        if (flag[page] == 1) //如果页面已经在内存中，显示物理地址
        {
            printf("指令%d的物理地址为%d\n", order[i], memory[page] * Q + order[i] % Q);
        }
        else //如果页面不在内存中，发生缺页
        {
            count++; //缺页次数加一
            int empty = -1; //记录是否有空闲的内存块
            for (j = 0; j < P; j++)
            {
                if (memory[j] == -1) //找到空闲的内存块
                {
                    empty = j;
                    break;
                }
            }
            if (empty != -1) //如果有空闲的内存块，直接调入页面，并更新队列
            {
                memory[empty] = page;
                flag[page] = 1;
                printf("指令%d的物理地址为%d\n", order[i], empty * Q + order[i] % Q);
                for (j = 0; j < P; j++)
                {
                    if (queue[j] == -1)
                    {
                        queue[j] = empty;
                        break;
                    }
                }
            }
            else //如果没有空闲的内存块，需要进行页面置换
            {
                //找到队列头部的内存块，即最先进入的内存块，作为置换对象
                index = queue[0];
                //置换该内存块中的页面，并显示物理地址
                flag[memory[index]] = 0;
                memory[index] = page;
                flag[page] = 1;
                printf("指令%d的物理地址为%d\n", order[i], index * Q + order[i] % Q);
                //更新队列，将队列头部的元素移到队尾
                for (j = 0; j < P - 1; j++)
                    queue[j] = queue[j + 1];
                queue[P - 1] = index;
            }
        }
    }
    printf("FIFO算法的缺页率为%.2f%%\n", count * 100.0 / N); //显示缺页率
}

//LRU算法
void LRU(int order[])
{
    int i, j, min, index, count = 0;
    int memory[P]; //内存块数组
    int flag[M]; //标记数组，记录每个页面是否在内存中
    int last[M]; //记录每个页面最近一次出现的位置

    //初始化内存块和标记数组
    for (i = 0; i < P; i++)
        memory[i] = -1;
    for (i = 0; i < M; i++)
        flag[i] = 0;

    //遍历指令序列
    for (i = 0; i < N; i++)
    {
        int page = order[i] / Q; //计算当前指令所在的页面号
        if (flag[page] == 1) //如果页面已经在内存中，显示物理地址，并更新最近一次出现的位置
        {
            printf("指令%d的物理地址为%d\n", order[i], memory[page] * Q + order[i] % Q);
            last[page] = i;
        }
        else //如果页面不在内存中，发生缺页
        {
            count++; //缺页次数加一
            int empty = -1; //记录是否有空闲的
            //内存块
            for (j = 0; j < P; j++)
            {
                if (memory[j] == -1) //找到空闲的内存块
                {
                    empty = j;
                    break;
                }
            }
            if (empty != -1) //如果有空闲的内存块，直接调入页面，并更新最近一次出现的位置
            {
                memory[empty] = page;
                flag[page] = 1;
                printf("指令%d的物理地址为%d\n", order[i], empty * Q + order[i] % Q);
                last[page] = i;
            }
            else //如果没有空闲的内存块，需要进行页面置换
            {
                //找到最近一次出现最早的页面，即最近最久未使用的页面，作为置换对象
                min = last[memory[0]];
                index = 0;
                for (j = 1; j < P; j++)
                {
                    if (last[memory[j]] < min)
                    {
                        min = last[memory[j]];
                        index = j;
                    }
                }
                //置换该页面，并显示物理地址，并更新最近一次出现的位置
                flag[memory[index]] = 0;
                memory[index] = page;
                flag[page] = 1;
                printf("指令%d的物理地址为%d\n", order[i], index * Q + order[i] % Q);
                last[page] = i;
            }
        }
    }
    printf("LRU算法的缺页率为%.2f%%\n", count * 100.0 / N); //显示缺页率
}

void menu()
{
	 while (1) //使用一个循环，让用户可以多次选择算法
	    {
	    	system("cls");
	        printf("请选择使用哪种算法：\n");
	        printf("1. OPT算法\n");
	        printf("2. FIFO算法\n");
	        printf("3. LRU算法\n");
	        printf("0. 退出程序\n");
	        printf("我的选择是：");
	        scanf("%d", &choice); //输入选择
	
	        switch (choice) //根据选择调用相应的算法
	        {
	        case 1:
	            printf("使用OPT算法：\n");
	            OPT(order);
	            break;
	        case 2:
	            printf("使用FIFO算法：\n");
	            FIFO(order);
	            break;
	        case 3:
	            printf("使用LRU算法：\n");
	            LRU(order);
	            break;
	        case 0:
	            printf("已退出程序，感谢您的使用！\n");
	            return ; //退出程序
	        default:
	            printf("输入错误，请重新输入\n");
	            break;
	        }
	        
	        printf("按任意键回到菜单页\n");
	        system("pause");
	        Sleep(100);
	    }
}

//主函数
int main()
{
    int flag=0;
    srand(time(NULL)); //设置随机数种子

    //生成指令序列
    m = rand() % N; //随机选取一条起始执行指令，其序号为m
    order[0] = m; //将其放入指令序列数组中
    for (i = 1; i < N; i++)
    {
        if (i % 4 == 1) //顺序执行下一条指令，即序号为m+1的指令
        {
            m++;
            order[i] = m;
        }
        else if (i % 4 == 2) //通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1
        {
            m1 = rand() % m;
            order[i] = m1;
        }
        else if (i % 4 == 3) //顺序执行下一条指令，即序号为m1+1的指令
        {
            m1++;
            order[i] = m1;
        }
        else //通过随机数，跳转到后地址部分[m1+2，319]中的某条指令处，其序号为m2
        {
            m2 = rand() % (N - m1 - 2) + m1 + 2;
            order[i] = m2;
        }
    }

    printf("指令序列为：\n");
    for (i = 0; i < N; i++)
        printf("%d ", order[i]);
    printf("\n");
	printf("是否进入菜单？(1代表是，0代表否)\n");
	printf("请输入您的选择：");
	scanf("%d",&flag);
	if(flag==1){
		menu();
	}
    return 0;
}

三、说明

上述代码实现的是一个模拟操作系统页面置换算法的程序。主要实现了三种页面置换算法：最佳置换（OPT）、先进先出（FIFO）和最近最久未使用（LRU）。此外，还包含一个生成指令序列的部分和一个简单的用户界面来选择不同的置换算法。下面是对代码主要部分的解释：

1. 程序流程：

• 首先，程序使用随机数生成器生成一个模拟的指令序列。
• 接着，程序提供了一个菜单，让用户选择要使用的页面置换算法。
• 根据用户的选择，程序将展示所选算法的页面置换过程和缺页率。

2. 页面置换算法的实现：

• OPT算法：在页面置换时，选择将来最长时间内不会被访问的页面进行置换。
• FIFO算法：按照页面进入内存的顺序进行置换，最先进入的页面最先被置换。
• LRU算法：在页面置换时，选择最长时间没有被访问的页面进行置换。

3. 关键变量：

• N：指令数。
• M：页数。
• P：内存块数。
• Q：每页指令数。
• order[]：存储指令序列的数组。
• memory[]：表示内存块的数组，存储当前各内存块中的页面。
• flag[]：标记数组，记录每个页面是否在内存中。

4. 生成指令序列：

   • 指令序列生成遵循一定的规则，以模拟程序的执行过程。

5. 用户交互：

   • 程序通过打印菜单和接收用户输入来控制算法的选择和程序的流程。

6. 输出：

   • 对于每一条指令，程序将输出其物理地址。
   • 在算法执行完毕后，程序将输出该算法的缺页率。

这个程序通过实际的模拟和数据，可以更好帮助我们理解各种页面置换算法的工作原理和性能差异。

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
点赞加关注，收藏不迷路！本篇文章对你有帮助的话，还请多多点赞支持！