操作系统最近最久未使用，最佳置换，先进先出置换
实验报告
班级： 计算机B191 学号： 2019537130 姓名： 陈力源 日期： 5月20
⒈ 实验题目
模拟分页式虚拟存储管理实验。
2．实验要求
编写一段程序来模拟页面置换算法。要求能分别显示最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最久未使用(LRU)置换算法的置换过程。
3. 实验目的
通过本实验帮助学生理解虚拟存储器的工作方法。了解分页式存储管理里中各页面置换算法是怎样实现的，各算法有怎样的优缺点。
⒋ 实验原理分析
⑴页面置换算法是在分页存储管理方式中为了合理的将进程运行所需的页面调入内存而产生的算法。一个好的页面转换算法，应具有较低的页面更换频率。最常见的页面置换算法有最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最久未使用(LRU)置换算法。
⑵算法的说明
最佳置换算法：选择以后永不使用或是在最长时间内不再被访问的页面作为被淘汰的页面。这种算法通常可保证获得最低的缺页率，但因为内存中哪个页面是以后永不使用的是无法预知的，所以该算法是无法实现的。
先进先出页面置换算法：选择内存中驻留时间最长的页面作为被淘汰的页面。该算法实现简单，只需将调入内存中的页面链成一个队列，并设置一个指针指向最老的页面即可。
最近最久未使用置换算法：选择最近最久未使用的页面作为被淘汰的页面。该算法需要为每个页面设置一个访问字段用来记录页面上次被访问的时间，通过这个时间来决定淘汰哪一个页面。
⑶主要变量及函数说明如表1所示
表1 主要变量及函数说明表
| PRA(void) |
初始化 |
| int findSpace(void) |
查找是否有空闲内存 |
| int findExist(int curpage) |
查找内存中是否有该页面 |
| int findReplace(void) |
查找应予置换的页面 |
| void display(void) |
显示 |
| void FIFO(void) |
FIFO算法 |
| void LRU(void) |
LRU算法 |
| void Optimal(void) |
OPTIMAL算法 |
| void BlockClear(void) |
BLOCK恢复 |
| struct pageInfor * block |
物理块 |
| struct pageInfor * page |
页面号串 |
5.实验代码清单
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
struct Pro
{
int num; //页号
int time; //等待时间，LRU算法会用到这个属性
}; //作业页面集
int pageNum; //系统分配给作业的主存中的页面数
int memoryNum; //可用内存页面数
struct Pro *memory; //内存页面集
struct Pro *page; //作业页面集
int curmemory; //调入内存中的页面个数
int missNum; //缺页次数
void print(Pro *page1); //打印当前主存中的页面
int Search(int num1, Pro *memory1); //在页面集memory1中查找num1，如果找到，返回其在memory1中的下标，否则返回-1
void FIFO()
{
missNum = 0;
curmemory = 0;
printf("FIFO页面置换情况: \n");
for (int i = 0; i<pageNum; i++)
{
if (Search(page[i].num, memory)<0)//若在内存中没有找到该页面
{
missNum++;
memory[curmemory].num = page[i].num;
print(memory);
curmemory = (curmemory + 1) % memoryNum; //找出最先进入内存的页面
}
}//end for
printf("缺页次数：%d \n", missNum);
}
void LRU()
{
missNum = 0;
curmemory = 0;
printf("Optimal页面置换情况(显示的是内存中存在的页面号-1代表空闲): \n");
for (int i = 0; i<pageNum; i++)
{
if (Search(page[i].num, memory) < 0)//若在内存中没有找到该页面
{
//找出未来最长时间内不再被访问的页面
int tem;
int opt = 0;
for (int k = 0; k < memoryNum; k++)
{
if (memory[k].num == -1)
{
curmemory = k;
break;
}
tem = 0; //页面k在未来tem时间内不会出现
int j;
for (j = i+1; j < pageNum; j++)
{
if (page[j].num == memory[k].num)
{
if (tem > opt)
{
opt = tem;
curmemory = k;
}
break;
}
else tem++;
}
if (j == pageNum)
{
opt = tem;
curmemory = k;
}
}
missNum++;
memory[curmemory].num = page[i].num;
print(memory);
}
}
printf("缺页次数：%d \n", missNum);
}
void Optimal()
{
missNum = 0;
curmemory = 0;
printf("LRU页面置换情况: \n");
for (int i = 0; i<pageNum; i++)
{
int rec=Search(page[i].num, memory);
if (rec < 0) //若在内存中没有找到该页面
{
missNum++;
for (int j = 0; j<memoryNum; j++) //找出最近最久未使用的页面
if (memory[j].time == -1) {
curmemory = j; break;
}
else if (memory[j].time > memory[curmemory].time)
curmemory = j;
memory[curmemory].num = page[i].num;
memory[curmemory].time = 0;
print(memory);
}
else memory[rec].time = 0;
for (int j = 0; j<memoryNum; j++) //内存中的所有页面等待时间+1
if (memory[j].num != -1)
memory[j].time++;
}
printf("缺页次数：%d \n", missNum);
}
int main(void)
{
int i;
char c; //得到用户的输入字符，来选择相应的置换算法
printf("请输入页面数:");
scanf("%d", &pageNum);
printf("输入内存页面数:");
scanf("%d", &memoryNum);
page = (Pro*)malloc(sizeof(Pro)*pageNum);
memory = (Pro*)malloc(sizeof(Pro)*memoryNum);
for (i = 0; i<pageNum; i++)
{
printf("第 %d 个页面号为:", i+1);
scanf("%d", &page[i].num);
page[i].time = 0; //等待时间开始默认为0
}
do {
for (i = 0; i<memoryNum; i++) //初始化内存中页面
{
memory[i].num = -1; //页面为空用-1表示
memory[i].time = -1; //
}
printf("F:先进先出(FIFO)页面置换\n");
printf("O:最佳(OPT)页面置换\n");
printf("L:最近最久未使用(LRU)页面置换\n");
printf("请选择操作类型(F,O,L),按其它键结束\n");
//fflush(stdin);
getchar();
scanf("%c", &c);
i = 0;
curmemory = 0;
if (c == 'F') //FIFO页面置换
{
FIFO();
}
if (c == 'O') //OPT页面置换算法
{
LRU();
}//end if
if (c == 'L') //LRU页面置换算法
{
Optimal();
}
} while (c == 'F' || c == 'L' || c == 'O');
return 0;
}
void print(Pro *memory1)//打印当前的页面
{
int j;
for (j = 0; j<memoryNum; j++)
printf("%d ", memory1[j].num);
printf("\n");
}
//在页面集memory1中查找num1，如果找到，返回其在memory1中的下标，否则返回-1
int Search(int num1, Pro *memory1)
{
int j;
for (j = 0; j<memoryNum; j++)
{
if (num1 == memory1[j].num)
return j;
}
return -1;
}
先进先出置换
最佳置换
最近最久未使用