操作系统实验3—实现请求页式存储管理模拟程序
操作系统实验3—实现请求页式存储管理模拟程序
实验描述
实验内容：
编写一个请求页式存储管理程序，模拟请求页式存储管理方式下的内存分配和页面置换。
实验目的：
内存管理是操作系统中的核心模块，能够合理利用内存，在很大程度上将影响到整个计算机系统的性能。内存的分配和回收与内存管理方式有关。本实验要求学生独立设计并实现请求页式存储管理方式下的内存分配与页面置换模拟程序，以加深对页面置换算法和请求页式存储管理方式的理解。
实验要求：
- 可以随机输入分配给一个进程的内存块数，以及该进程的页面访问序列，具体信息见测试用例格式输入部分说明。
- 分别采用最佳算法OPT（当有多个页面可置换时，按照先进先出原则进行置换）、先进先出算法FIFO和最近最少使用算法LRU进行页面置换，其中LRU算法采用栈式方法实现。
- 显示页面变化时内存块装入页面列表的详细情况，并显示是否产生页面置换，并计算缺页次数及缺页率。具体信息见测试用例格式输出部分说明。
测试用例格式如下：
输入：
算法（1--OPT，2--FIFO，3--LRU）
内存块数
页面序列（页面1,页面2,页面3,...）
输出：
页面变化时内存块装入页面列表1-是否命中/页面变化时内存块装入页面列表2-是否命中/...
缺页次数
其中：
页面变化时内存块装入页面列表：
(1) 内存块1装入页面,内存块2装入页面,内存块3装入页面...，未装入任何页面时由"-”表示
(2) 是否命中：1-命中，0-缺页
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 1 3 1,2,3,4,1,2,5,1,2,3,4,5 | 1,-,-,0/1,2,-,0/1,2,3,0/1,2,4,0/1,2,4,1/1,2,4,1/1,2,5,0/1,2,5,1/1,2,5,1/3,2,5,0/3,4,5,0/3,4,5,1 7 | 1秒 | 64M | 0 |
| 测试用例 2 | 2 4 1,2,3,4,1,2,5,1,2,3,4,5 | 1,-,-,-,0/1,2,-,-,0/1,2,3,-,0/1,2,3,4,0/1,2,3,4,1/1,2,3,4,1/5,2,3,4,0/5,1,3,4,0/5,1,2,4,0/5,1,2,3,0/4,1,2,3,0/4,5,2,3,0 10 | 1秒 | 64M | 0 |
| 测试用例 3 | 3 3 1,2,3,4,1,2,5,1,2,3,4,5 | 1,-,-,0/1,2,-,0/1,2,3,0/2,3,4,0/3,4,1,0/4,1,2,0/1,2,5,0/2,5,1,1/5,1,2,1/1,2,3,0/2,3,4,0/3,4,5,0 10 | 1秒 | 64M | 0 |
设计思路
虽然每次输入的页面数据只有页面序号，但是在算法中需要计算每个页面访问过之后的优先级变化，以及当前页面下一次访问所需要的距离信息，所以采用结构体数组的形式将需要用到的信息全部存储起来。
临时数组在 LRU 算法中起辅助输出的作用。
struct Memory
{
int id; //序号
int priority; //最前面的内存优先级为0，往后依次加1
int distance; //下次访问与当前距离
}memory[1010], memory2[1010];//内存序列，临时数组
程序概要设计如下图所示：
- main（）函数是主程序的入口，控制程序流程，并按照输入的调度信号选择相应的算法模块进行运行
- input（）函数是输入函数，接受程序输入
- output（）函数是输出函数，将页面命中与缺页置换的信息进行输出
- OPT（）函数是最佳置换算法，根据已知的页面序列和优先级顺序算出最佳的页面调度方案
- FIFO（）函数是先进先出算法，根据页面的到来顺序进行页面置换
- LRU（）函数是最近最久未使用算法，根据页面的使用情况进行页面调度，这里使用了临时数组来辅助信息输出
int main(); //主程序入口
void input(); //输入函数
void output(int k);//输出函数
void OPT(); //最佳置换算法
void FIFO(); //先进先出算法
void LRU(); //最近最久未使用算法
上机代码
代码使用 C++ 语言进行编写
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string>
using namespace std;
struct Memory
{
int id;//序号
int priority;//最前面的内存优先级为0，往后依次加1
int distance;//下次访问与当前距离
}memory[1010], memory2[1010];//内存序列，临时数组
int que[1010];//页面序列
void input();//输入函数
void output(int k);//输出函数
void OPT();//最佳置换算法
void FIFO();//先进先出算法
void LRU();//最近最久未使用算法
int sig;//算法选择标志
int memoryk, num, total;//内存块数，页面数量，缺页次数
int pageFlag;//缺页标志
const int isPage = 1;//命中
const int noPage = 0;//缺页
int main()
{
//程序输入
input();
//选择算法
switch (sig)
{
case 1:OPT(); break;
case 2:FIFO(); break;
case 3:LRU(); break;
}
return 0;
}
void input()
{
//freopen("osin.txt", "r", stdin);
//freopen("osout.txt", "w", stdout);
sig = 0;
cin >> sig;//算法选择标志
memoryk = 0;
total = 0;
cin >> memoryk;//内存块数
num = 0;
char c;
while (scanf("%d", &que[num]))//输入页面序列
{
num++;
c = getchar();
if (c == '\n')//遇到换行符则输入结束
{
break;
}
else if (c == ',')//遇到逗号则继续读取
{
continue;
}
}
for (int i = 0; i < memoryk; i++)//内存初始化
{
memory[i].id = -1;
memory[i].priority = i;
}
}
void output(int k)
{
for (int i = 0; i < memoryk; i++)//输出内存中页面序列
{
if (memory[i].id != -1)//内存有页面
{
printf("%d,", memory[i].id);
}
else//内存没有页面
{
printf("-,");
}
}
if (k != num - 1)//没到最后一页
{
printf("%d/", pageFlag);
}
else//最后一页
{
printf("%d\n", pageFlag);
printf("%d\n", total);
}
}
void OPT()
{
int optFlag = 0;//OPT页面替换标志，替换下标为optFlag的页面
for (int i = 0; i < num; i++)
{
int tmp = 0;//内存块下标
while (tmp < memoryk)
{
if (que[i] == memory[tmp].id)//内存中有此页就输出
{
pageFlag = isPage;
output(i);
break;
}
if (memory[tmp].id == -1)//内存中无此页则加入内存
{
memory[tmp].id = que[i];
total++;
pageFlag = noPage;
output(i);
break;
}
tmp++;
}
//运行到此处证明找遍内存仍未命中页面
//淘汰下次访问距当前最远的那些页中序号最小的页，距离相等则淘汰优先级低的页
if (tmp == memoryk)
{
for (int j = 0; j < memoryk; j++)//距离初始化
{
memory[j].distance = 99999;
}
for (int j = 0; j < memoryk; j++)//计算距离
{
int dis = 0;
for (int k = i + 1; k < num; k++)//记录下一个序号相同页面的距离
{
dis++;
if (que[k] == memory[j].id)//更新距离
{
memory[j].distance = dis;
break;
}
}
}
int max_dis = memory[0].distance;//找最大距离
int min_prority = memory[0].priority;//找最小优先级
for (int k = 0; k < memoryk; k++)
{
if (memory[k].distance == max_dis)
{
if (memory[k].priority <= min_prority)
{
min_prority = memory[k].priority;
max_dis = memory[k].distance;
optFlag = k;
}
}
else if (memory[k].distance > max_dis)
{
min_prority = memory[k].priority;
max_dis = memory[k].distance;
optFlag = k;
}
}
//调整优先级
memory[optFlag].priority = memoryk;
for (int k = 0; k < memoryk; k++)
{
memory[k].priority--;
}
//缺页处理
memory[optFlag].id = que[i];
pageFlag = noPage;
total++;
output(i);
}
}
}
void FIFO()
{
int fifoFlag = 0;//FIFO页面替换标志，替换下标为fifoFlag的页面
for (int i = 0; i < num; i++)
{
int tmp = 0;//内存块下标
while (tmp < memoryk)
{
if (que[i] == memory[tmp].id)//内存中有此页就输出
{
pageFlag = isPage;
output(i);
break;
}
if (memory[tmp].id == -1)//内存中无此页则加入内存
{
memory[tmp].id = que[i];
total++;
pageFlag = noPage;
output(i);
break;
}
tmp++;
}
//运行到此处证明找遍内存仍未命中页面
//按照FIFO的顺序进行页面淘汰
if (tmp == memoryk)
{
if (fifoFlag == memoryk)//保证替换范围在[0-memoryk)之间
{
fifoFlag = 0;
}
//缺页处理
memory[fifoFlag].id = que[i];
fifoFlag++;
pageFlag = noPage;
total++;
output(i);
}
}
}
void LRU()
{
int empty;//内存块中是否含有空闲区
int lruFlag = 0;//LRU页面替换标志，记录第一个空闲区下标
int x;//临时数组下标
for (int i = 0; i < num; i++)
{
empty = 0;
lruFlag = 0;
for (int j = 0; j < memoryk; j++)//寻找空闲区
{
if (memory[j].id == -1)
{
empty = 1;
lruFlag = j;
break;
}
}
int tmp = 0;//内存块下标
while (tmp < memoryk)
{
if (memory[tmp].id == que[i])//内存中有此页
{
if (empty == 1)//有空闲区
{
x = 0;
//调整输出顺序
for (int k = tmp + 1; k < lruFlag; k++)
{
memory2[x].id = memory[k].id;
x++;
}
x = 0;
for (int k = tmp; k < lruFlag - 1; k++)
{
memory[k].id = memory2[x].id;
x++;
}
memory[lruFlag - 1].id = que[i];
//输出
pageFlag = isPage;
output(i);
break;
}
else//没有空闲区
{
x = 0;
//调整输出顺序
for (int k = tmp + 1; k < memoryk; k++)
{
memory2[x].id = memory[k].id;
x++;
}
x = 0;
for (int k = tmp; k < memoryk - 1; k++)
{
memory[k].id = memory2[x].id;
x++;
}
memory[memoryk - 1].id = que[i];
//输出
pageFlag = isPage;
output(i);
break;
}
}
tmp++;
}
//运行到此处证明找遍内存仍未命中页面
//淘汰上次使用距当前最远的页
if (tmp == memoryk)
{
if (empty == 1)//有空闲区
{
memory[lruFlag].id = que[i];//直接装入
pageFlag = noPage;
total++;
output(i);
}
else//淘汰页面
{
//调整输出顺序
int y = 0;
for (int k = 1; k < memoryk; k++)
{
memory2[y].id = memory[k].id;
y++;
}
y = 0;
for (int k = 0; k < memoryk - 1; k++)
{
memory[k].id = memory2[y].id;
y++;
}
memory[memoryk - 1].id = que[i];
//缺页处理
pageFlag = noPage;
total++;
output(i);
}
}
}
}
测试结果
程序采用黑盒测试的方式，提交到 OJ 系统上进行在线评测
可以看到，OJ 的测试用例全部通过
心得体会
通过本次实验，上机代码模拟实现了三种页面调度置换算法，对操作系统内部的页面置换方式有了更深刻的认识和感受。OPT 算法是理想型的算法，因为现实生活中根本不知道下一个到来的页面是哪一个，所以只能作为评判页面置换算法优劣的一个标准。LRU 算法的本质则是一种栈的实现。