一、 实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一 种常用的虚拟存储管理技术。 本实验的目的是通过请求页式管理中页面置换算法模拟设计，了 解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
二、 主要仪器设备、试剂或材料
VMare虚拟机
三、 实验内容
通过请求页式管理中页面置换算法模拟设计。
四、 实验思路及结果分析
（1）通过随机数产生一个指令序列，共 320 条指令。其地址按下 述原则生成：
①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分；
③25%的指令是均匀分布在后地址部分；
具体的实施方法是：
① 在[0，319]的指令地址之间随机选取一起点 m;
② 顺序执行一条指令，即执行地址为 m+1 的指令；
③ 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地 址为 m’;
④ 顺序执行一条指令，其地址为 m’+1；
⑤ 在后地址[m’+2，319]中随机选取一条指令并执行；
⑥ 重复①-⑤，直到执行 320 次指令。
//初始化数据
void Init()
{
srand((unsigned int)time(NULL));//生成随机种子
int index = 0;
int x = 0;
int y = 0;
int z = 0;
int i;
while (index < N)
{
x = rand() % N; //在[0，319]的指令地址之间随机选取一起点m
while (x > N - 2)
{
x = rand() % N;
}
instruction[index++] = x + 1;//顺序执行一条指令，即执行地址为m+1的指令（记录顺序）
y = rand() % (x + 1); //在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’
while (y > N - 3)
{
y = rand() % (x + 1);
}
instruction[index++] = y;
instruction[index++] = y + 1;// 顺序执行一条指令，其地址为m’ + 1
z = rand() % (N - (y + 2)) + y + 2; //在后地址[m’+2，319]中随机选取一条指令
instruction[index++] = z;
}
（2）将指令序列变换成页地址流，设：
①页面大小为 1K；
②用户内存容量为 4 页到 32 页；
③用户虚存容量为 32K。 在用户虚存中，按每页存放 10 条指令排列虚存地址，即 320 条 指令在虚存中的存放方式为：
第 0 条—第 9 条指令为第 0 页（对应虚存地址为[0，9]）；
第 10 条—第 19 条指令为第 1 页（对应虚存地址为[10，19]）；
。。。。。。。。。。。。。。。。。。。。。
第 310 条—第 319 条指令为第 31 页（对应虚存地址为[310， 319]）； 按以上方式，用户指令可组成 32 页。
for (i = 0; i < N; i++)
{
page[i] = instruction[i] / 10; //每条指令对应的页面
}
printf("随机生成的每条指令所在页面为：\n");
for (i = 0; i < N; i++)
{
if ((i % 10 == 0) && (i != 0))
printf("\n");
printf("%d\t", page[i]);
}
}
（3）计算并输出下述各种算法在不同内存容量下的命中率。
①FIFO 先进先出的页面淘汰算法
void FIFO(int n)
{
SqQueue Q;//生成队列
//初始化队列
Q.base = (int*)malloc(sizeof(int) * n);
if (!Q.base)
exit(1);
Q.front = Q.rear = 0;
double count = 0; //定义命中次数
int test;//test标志该页是否在内存中
for (int i = 0; i < N; i++)
{
test = 0;
int temp = Q.front;//标记队列的第一个
while (temp != Q.rear)
{
if (Q.base[temp] == page[i]) //查找该页是否在内存中
{
test = 1;//
break;
}
temp = (temp + 1) % n;
}
if (test == 1)//该页在内存中
{
count += 1; //命中数量+1
}
else //发生缺页中断
{
if ((Q.rear + 1) % n == Q.front) //如果内存已满
{
Q.front = (Q.front + 1) % n; //最先进去的页面淘汰，即出队操作
Q.base[Q.rear] = page[i]; //最新的页面进入内存，即入队操作
Q.rear = (Q.rear + 1) % n;
}
else //当内存没满
{
Q.base[Q.rear] = page[i]; //新的页面进入内存，即入队操作
Q.rear = (Q.rear + 1) % n;
}
}
}
printf("内存容量为%d页时命中率为%lf", n, count / N);
printf("\n");
free(Q.base);//释放资源}
②LRU 最近最少使用页面淘汰算法
void LRU(int n)
{
int i, j, k;
int* memory = NULL;
memory = (int*)malloc(sizeof(int) * n); //内存空间
int* sign = NULL;
sign = (int*)malloc(sizeof(int) * n); //标志内存中的页上次访问到现在的时间
double count = 0; //定义命中次数
int test, test2; //test标志该页是否在内存中，test2标志内存是否还有空间
int index; //设置为最久未访问页面的下标
for (i = 0; i < n; i++)
{
memory[i] = -1; //初始化数组
sign[i] = -1;
}
for (i = 0; i < N; i++)
{
//更新标记时间的值
for (j = 0; j < n; j++)
{
if (sign[j] != -1)
{
sign[j] += 1; //页面上次访问到现在时间+1
}
}
test = 0;
for (j = 0; j < n; j++)
{
if (memory[j] == page[i]) //查找该页是否在内存中
{
test = 1;
sign[j] = 0; //访问时间置0
break;
}
}
if (test == 1) //test=1，该页在内存中
{
count += 1; //命中+1
}
else //引发缺页中断
{
test2 = 0;
for (k = 0; k < n; k++)
{
if (memory[k] == -1) //检查是否还有内存空间
{
test2 = 1; //有多余空间，test2=1；
memory[k] = page[i]; //新的页面进入内存
sign[k] = 0; //访问时间置0
break;
}
}
if (test2 == 0) //如果内存已满
{
index = 0;
for (k = 0; k < n; k++)
{
if (sign[index] < sign[k])
index = k; //找出上次访问到现在最久的页面，找到下标index
}
memory[index] = page[i]; //替换该页面
}
}
}
printf("内存容量为%d页时命中率为%lf", n, count / N);
printf("\n");
free(memory);
free(sign);}
③OPT 最佳页面淘汰算法
void LFU(int n) {
int* memory = (int*)malloc(sizeof(int) * n); // 内存空间
int* refBit = (int*)malloc(sizeof(int) * n);
int* counter = (int*)malloc(sizeof(int) * n);
int hitCount = 0; // 命中次数
int initialHand = 0; // 初始hand位置
int found = 0; // 用于标记页面是否在内存中
int i, j;
int hand = 0;
// 初始化内存、引用位和访问时间
for (i = 0; i < n; i++) {
memory[i] = -1; // 假设初始时没有页面在内存中
refBit[i] = 0; // 引用位初始化为0
counter[i] = 0; // 访问时间初始化为0
}
// 遍历页面序列
for (i = 0; i < N; i++) {
int pageFault = page[i]; // 当前页面
// 查找页面是否在内存中
for (j = 0; j < n; j++) {
if (memory[j] == pageFault) {
found = 1; // 页面在内存中
refBit[j] = 0; // 访问了该页面，将引用位设置为0
counter[j] = 0; // 重置访问时间
break;
}
}
// 页面在内存中，增加命中次数
if (found) {
hitCount++;
found = 0; // 重置found标志，为下一个页面做准备
}
else {
// 页面不在内存中，发生缺页中断
found = 0; // 重置found标志，用于下面的循环
initialHand = hand = 0; // 初始化hand并设置initialHand
do {
// 如果R位为0，则替换当前页面
if (refBit[hand] == 0) {
memory[hand] = pageFault;
refBit[hand] = 1; // 设置新页面的R位为1
counter[hand] = 0; // 重置新页面的访问时间
break;
}
// 如果R位为1，则增加访问时间并继续查找
counter[hand]++;
// 继续查找下一个页面
hand = (hand + 1) % n;
// 检查是否已经遍历了所有页面
if (hand == initialHand) {
// 如果所有页面的R位都为1，则替换hand指向的页面（即最旧的页面）
int oldest = hand;
for (j = (hand + 1) % n; j != hand; j = (j + 1) % n) {
if (counter[j] > counter[oldest]) {
oldest = j;
}
}
memory[oldest] = pageFault;
refBit[oldest] = 1; // 设置新页面的R位为1
counter[oldest] = 0; // 重置新页面的访问时间
break;
}
} while (1); // 循环直到找到可替换的页面
}
}
// 计算并输出命中率
printf("内存容量为%d页时命中率为%lf\n", n, (double)hitCount / N);
// 释放内存
free(memory);
free(refBit);
free(counter);
}
④LFU 最不经常使用页面淘汰算法
void LFU(int n) {
int* memory = (int*)malloc(sizeof(int) * n); // 内存空间
int* refBit = (int*)malloc(sizeof(int) * n);
int* counter = (int*)malloc(sizeof(int) * n);
int hitCount = 0; // 命中次数
int initialHand = 0; // 初始hand位置
int found = 0; // 用于标记页面是否在内存中
int i, j;
int hand = 0;
// 初始化内存、引用位和访问时间
for (i = 0; i < n; i++) {
memory[i] = -1; // 假设初始时没有页面在内存中
refBit[i] = 0; // 引用位初始化为0
counter[i] = 0; // 访问时间初始化为0
}
// 遍历页面序列
for (i = 0; i < N; i++) {
int pageFault = page[i]; // 当前页面
// 查找页面是否在内存中
for (j = 0; j < n; j++) {
if (memory[j] == pageFault) {
found = 1; // 页面在内存中
refBit[j] = 0; // 访问了该页面，将引用位设置为0
counter[j] = 0; // 重置访问时间
break;
}
}
// 页面在内存中，增加命中次数
if (found) {
hitCount++;
found = 0; // 重置found标志，为下一个页面做准备
}
else {
// 页面不在内存中，发生缺页中断
found = 0; // 重置found标志，用于下面的循环
initialHand = hand = 0; // 初始化hand并设置initialHand
do {
// 如果R位为0，则替换当前页面
if (refBit[hand] == 0) {
memory[hand] = pageFault;
refBit[hand] = 1; // 设置新页面的R位为1
counter[hand] = 0; // 重置新页面的访问时间
break;
}
// 如果R位为1，则增加访问时间并继续查找
counter[hand]++;
// 继续查找下一个页面
hand = (hand + 1) % n;
// 检查是否已经遍历了所有页面
if (hand == initialHand) {
// 如果所有页面的R位都为1，则替换hand指向的页面（即最旧的页面）
int oldest = hand;
for (j = (hand + 1) % n; j != hand; j = (j + 1) % n) {
if (counter[j] > counter[oldest]) {
oldest = j;
}
}
memory[oldest] = pageFault;
refBit[oldest] = 1; // 设置新页面的R位为1
counter[oldest] = 0; // 重置新页面的访问时间
break;
}
} while (1); // 循环直到找到可替换的页面
}
}
// 计算并输出命中率
printf("内存容量为%d页时命中率为%lf\n", n, (double)hitCount / N);
// 释放内存
free(memory);
free(refBit);
free(counter);
}
⑤NUR 最近没有使用页面淘汰算法
void NUR(int n) {
int hitCount = 0; // 命中次数
int hand = 0; // 模拟循环队列的指针（hand in hand）
int i;
int* memory = NULL;
memory = (int*)malloc(sizeof(int) * n); //内存空间
int* refBit = NULL;
refBit = (int*)malloc(sizeof(int) * n);
// 初始化内存和引用位
for (i = 0; i < n; i++) {
memory[i] = -1; // 假设初始时没有页面在内存中
refBit[i] = 0; // 引用位初始化为0
}
// 遍历页面序列
for (i = 0; i < N; i++) {
int pageFault = page[i]; // 当前页面
int found = 0; // 标记页面是否在内存中
// 查找页面是否在内存中
for (int j = 0; j < n; j++) {
if (memory[j] == pageFault) {
found = 1; // 页面在内存中
refBit[j] = 0; // 访问了该页面，将引用位设置为0
break;
}
}
// 页面在内存中，增加命中次数
if (found) {
hitCount++;
}
else {
// 页面不在内存中，发生缺页中断
// 查找第一个R位为0的页面或者循环回到开始并重置所有R位
do {
if (refBit[hand] == 0) {
// 找到R位为0的页面，替换它
memory[hand] = pageFault;
refBit[hand] = 1; // 设置新页面的R位为1
break;
}
else {
// 如果没有找到，则继续查找下一个页面，或者重置所有R位
hand = (hand + 1) % n; // 循环队列
if (hand == 0) { // 如果回到开始，重置所有R位
for (int k = 0; k < n; k++) {
refBit[k] = 0;
}
}
}
} while (hand != 0 || refBit[hand] == 1); // 循环直到找到可替换的页面或回到开始
}
}
// 计算并输出命中率
printf("内存容量为%d页时命中率为%lf\n", n, (double)hitCount / N);
free(memory);
free(refBit);
}
（4）分析实验结果。 分析不同算法的表现和特点，分析是否出现 belady 现象。
FIFO表现：
FIFO算法的命中率较低，在所有算法中表现较差。
命中率随内存容量增加而提高，但中间可能出现 Belady现象。
示例：在内存容量从 25 页到 27 页时，命中率保持不变（79.69%），说明性能存在波动。
特点：
简单易实现，依据页面进入内存的时间顺序进行替换。
可能会出现 Belady现象，即增加内存反而导致命中率下降。
LRU表现：
LRU算法的命中率次优，接近OPT，能较好适应实际情况。
命中率随内存容量增加而稳定提升，从 4 页时的 31.25% 增加到 32 页时的 90%。
特点：
基于最近访问时间进行淘汰，较为贴近实际应用需求。
不会出现Belady现象，性能表现稳定。
OPT表现：
OPT算法的命中率最高，理论上是最优的算法。
在实验中，命中率随着内存容量增加而逐步提高，从 4 页时的 48.44% 增加到 32 页时的 90%。
特点：
需要预先知道未来的页面访问序列，因此不适用于实际系统。
作为衡量其他页面置换算法性能的基准。
LFU表现：
LFU算法命中率相对较低，并且在内存容量较大时表现不佳。
在内存容量从 17 页开始，命中率固定为 60.63%，说明频率统计的局限性导致性能无法提升。
特点：
基于访问频率进行淘汰，但频率统计可能无法反映实际的未来需求。
在一定情况下，可能无法充分利用增加的内存。
NUR表现：
NUR算法的命中率相对较低，性能在各算法中较差。
命中率从 4 页时的 25.94% 增加到 32 页时的 82.81%，整体提升幅度不如其他算法。
特点：
利用访问和修改位进行淘汰，受限于硬件支持和位信息的精度。
命中率的增长趋势较不稳定。
OPT 是理想参考标准，实际不可实现。
LRU 在实际场景中表现最佳，命中率接近OPT。
FIFO 存在Belady现象，不适合高性能需求的场景。
LFU、NUR 在特定条件下表现有限，命中率提升受约束。
Belady现象：
FIFO 是实验中唯一出现Belady现象的算法。
其他算法（OPT、LRU、LFU、NUR）均未观察到此现象。
五、讨论、心得
通过本次实验，我们对页面置换算法的性能有了深入了解。OPT作为理论最优算法，为其他算法提供了参考基准。LRU表现接近OPT，适合实际应用，能有效避免Belady现象。FIFO算法尽管实现简单，但易出现Belady现象，性能较差。LFU和NUR因其淘汰策略的局限性，在内存容量较大时命中率增长缓慢，表现不稳定。本实验表明，LRU在动态页面管理中具备较高的实用价值，而FIFO等简单算法虽然易于实现，但在高性能需求场景中并不适用。本实验加深了我们对算法优劣及应用场景的理解，为实际系统设计提供了指导。
完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 320 //指令数
#define MAX 500
int instruction[N]; //指令序列
int page[N]; //记录指令所在页面
//队列的顺序存储结构
typedef struct
{
int* base; //存储空间的基地址
int front;
int rear;
}SqQueue;
//初始化数据
void Init()
{
srand((unsigned int)time(NULL));//生成随机种子
int index = 0;
int x = 0;
int y = 0;
int z = 0;
int i;
while (index < N)
{
x = rand() % N; //在[0，319]的指令地址之间随机选取一起点m
while (x > N - 2)
{
x = rand() % N;
}
instruction[index++] = x + 1;//顺序执行一条指令，即执行地址为m+1的指令（记录顺序）
y = rand() % (x + 1); //在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’
while (y > N - 3)
{
y = rand() % (x + 1);
}
instruction[index++] = y;
instruction[index++] = y + 1;// 顺序执行一条指令，其地址为m’ + 1
z = rand() % (N - (y + 2)) + y + 2; //在后地址[m’+2，319]中随机选取一条指令
instruction[index++] = z;
}
for (i = 0; i < N; i++)
{
page[i] = instruction[i] / 10; //每条指令对应的页面
}
printf("随机生成的每条指令所在页面为：\n");
for (i = 0; i < N; i++)
{
if ((i % 10 == 0) && (i != 0))
printf("\n");
printf("%d\t", page[i]);
}
}
//最佳淘汰算法（最佳页面替换算法）P235
void OPT(int n)
{
int i, j, k;
int test, test2; //test标志该页是否在内存中，test2标志内存是否还有空间
int* next_time = NULL; //页面下次出现时间
next_time = (int*)malloc(sizeof(int) * n);
int* memory = NULL;//内存空间
memory = (int*)malloc(sizeof(int) * n);
int index = 0; //距离下次访问最远的页面的下标
double count = 0; //定义命中次数
for (i = 0; i < n; i++)
{
next_time[i] = -1; //初始化数组
memory[i] = -1;
}
for (i = 0; i < N; i++)
{
test = 0;
for (j = 0; j < n; j++)
{
if (memory[j] == page[i]) //查找该页是否在内存中
{
test = 1;
break;
}
}
if (test == 1) //test=1，该页在内存中
{
count += 1; //命中数+1
}
else//当发送缺页中断时
{
test2 = 0;
for (j = 0; j < n; j++) //缺页中断
{
if (memory[j] == -1) //检查是否还有内存空间
{
test2 = 1; //说明有多余空间，test2=1；
next_time[j] = MAX;
memory[j] = page[i]; //新的页面进入内存空间
break;
}
}
if (test2 == 0)//当内存空间已满时
{
for (int j = 0; j < n; j++)
{
next_time[j] = MAX;
for (k = i + 1; k < N; k++)
{
if (memory[j] == page[k])
{
next_time[j] = k - i; //求出内存中的页面下一次出现的位置
break;
}
}
}
for (j = 0; j < n; j++)
{
if (next_time[j] > next_time[index])
index = j; //找出距离下次访问最远的页面，求出下标index
}
memory[index] = page[i];//找到页面，替换该页面
}
}
}
printf("内存容量为%d页时，命中率为%lf", n, count / N);
printf("\n");
free(next_time);
free(memory);
}
//先进先出法（先进先出页面替换算法）
void FIFO(int n)
{
SqQueue Q;//生成队列
//初始化队列
Q.base = (int*)malloc(sizeof(int) * n);
if (!Q.base)
exit(1);
Q.front = Q.rear = 0;
double count = 0; //定义命中次数
int test;//test标志该页是否在内存中
for (int i = 0; i < N; i++)
{
test = 0;
int temp = Q.front;//标记队列的第一个
while (temp != Q.rear)
{
if (Q.base[temp] == page[i]) //查找该页是否在内存中
{
test = 1;//
break;
}
temp = (temp + 1) % n;
}
if (test == 1)//该页在内存中
{
count += 1; //命中数量+1
}
else //发生缺页中断
{
if ((Q.rear + 1) % n == Q.front) //如果内存已满
{
Q.front = (Q.front + 1) % n; //最先进去的页面淘汰，即出队操作
Q.base[Q.rear] = page[i]; //最新的页面进入内存，即入队操作
Q.rear = (Q.rear + 1) % n;
}
else //当内存没满
{
Q.base[Q.rear] = page[i]; //新的页面进入内存，即入队操作
Q.rear = (Q.rear + 1) % n;
}
}
}
printf("内存容量为%d页时命中率为%lf", n, count / N);
printf("\n");
free(Q.base);//释放队列
}
//最近最久未使用算法（最近最少使用页面替换算法）
void LRU(int n)
{
int i, j, k;
int* memory = NULL;
memory = (int*)malloc(sizeof(int) * n); //内存空间
int* sign = NULL;
sign = (int*)malloc(sizeof(int) * n); //标志内存中的页上次访问到现在的时间
double count = 0; //定义命中次数
int test, test2; //test标志该页是否在内存中，test2标志内存是否还有空间
int index; //设置为最久未访问页面的下标
for (i = 0; i < n; i++)
{
memory[i] = -1; //初始化数组
sign[i] = -1;
}
for (i = 0; i < N; i++)
{
//更新标记时间的值
for (j = 0; j < n; j++)
{
if (sign[j] != -1)
{
sign[j] += 1; //页面上次访问到现在时间+1
}
}
test = 0;
for (j = 0; j < n; j++)
{
if (memory[j] == page[i]) //查找该页是否在内存中
{
test = 1;
sign[j] = 0; //访问时间置0
break;
}
}
if (test == 1) //test=1，该页在内存中
{
count += 1; //命中+1
}
else //引发缺页中断
{
test2 = 0;
for (k = 0; k < n; k++)
{
if (memory[k] == -1) //检查是否还有内存空间
{
test2 = 1; //有多余空间，test2=1；
memory[k] = page[i]; //新的页面进入内存
sign[k] = 0; //访问时间置0
break;
}
}
if (test2 == 0) //如果内存已满
{
index = 0;
for (k = 0; k < n; k++)
{
if (sign[index] < sign[k])
index = k; //找出上次访问到现在最久的页面，找到下标index
}
memory[index] = page[i]; //替换该页面
}
}
}
printf("内存容量为%d页时命中率为%lf", n, count / N);
printf("\n");
free(memory);
free(sign);
}
//第二次机会页面替换算法（SCR）
void SCR(int n) {
int* memory = (int*)malloc(sizeof(int) * n); // 内存空间
int* refBit = (int*)malloc(sizeof(int) * n);
int* counter = (int*)malloc(sizeof(int) * n);
int hitCount = 0; // 命中次数
int initialHand = 0; // 初始hand位置
int found = 0; // 用于标记页面是否在内存中
int i, j;
int hand = 0;
// 初始化内存、引用位和访问时间
for (i = 0; i < n; i++) {
memory[i] = -1; // 假设初始时没有页面在内存中
refBit[i] = 0; // 引用位初始化为0
counter[i] = 0; // 访问时间初始化为0
}
// 遍历页面序列
for (i = 0; i < N; i++) {
int pageFault = page[i]; // 当前页面
// 查找页面是否在内存中
for (j = 0; j < n; j++) {
if (memory[j] == pageFault) {
found = 1; // 页面在内存中
refBit[j] = 0; // 访问了该页面，将引用位设置为0
counter[j] = 0; // 重置访问时间
break;
}
}
// 页面在内存中，增加命中次数
if (found) {
hitCount++;
found = 0; // 重置found标志，为下一个页面做准备
}
else {
// 页面不在内存中，发生缺页中断
found = 0; // 重置found标志，用于下面的循环
initialHand = hand = 0; // 初始化hand并设置initialHand
do {
// 如果R位为0，则替换当前页面
if (refBit[hand] == 0) {
memory[hand] = pageFault;
refBit[hand] = 1; // 设置新页面的R位为1
counter[hand] = 0; // 重置新页面的访问时间
break;
}
// 如果R位为1，则增加访问时间并继续查找
counter[hand]++;
// 继续查找下一个页面
hand = (hand + 1) % n;
// 检查是否已经遍历了所有页面
if (hand == initialHand) {
// 如果所有页面的R位都为1，则替换hand指向的页面（即最旧的页面）
int oldest = hand;
for (j = (hand + 1) % n; j != hand; j = (j + 1) % n) {
if (counter[j] > counter[oldest]) {
oldest = j;
}
}
memory[oldest] = pageFault;
refBit[oldest] = 1; // 设置新页面的R位为1
counter[oldest] = 0; // 重置新页面的访问时间
break;
}
} while (1); // 循环直到找到可替换的页面
}
}
// 计算并输出命中率
printf("内存容量为%d页时命中率为%lf\n", n, (double)hitCount / N);
// 释放内存
free(memory);
free(refBit);
free(counter);
}
//时钟页面替换算法（Clock）
void Clock(int n) {
int hitCount = 0; // 命中次数
int hand = 0; // 模拟循环队列的指针（hand in hand）
int i;
int* memory = NULL;
memory = (int*)malloc(sizeof(int) * n); //内存空间
int* refBit = NULL;
refBit = (int*)malloc(sizeof(int) * n);
// 初始化内存和引用位
for (i = 0; i < n; i++) {
memory[i] = -1; // 假设初始时没有页面在内存中
refBit[i] = 0; // 引用位初始化为0
}
// 遍历页面序列
for (i = 0; i < N; i++) {
int pageFault = page[i]; // 当前页面
int found = 0; // 标记页面是否在内存中
// 查找页面是否在内存中
for (int j = 0; j < n; j++) {
if (memory[j] == pageFault) {
found = 1; // 页面在内存中
refBit[j] = 0; // 访问了该页面，将引用位设置为0
break;
}
}
// 页面在内存中，增加命中次数
if (found) {
hitCount++;
}
else {
// 页面不在内存中，发生缺页中断
// 查找第一个R位为0的页面或者循环回到开始并重置所有R位
do {
if (refBit[hand] == 0) {
// 找到R位为0的页面，替换它
memory[hand] = pageFault;
refBit[hand] = 1; // 设置新页面的R位为1
break;
}
else {
// 如果没有找到，则继续查找下一个页面，或者重置所有R位
hand = (hand + 1) % n; // 循环队列
if (hand == 0) { // 如果回到开始，重置所有R位
for (int k = 0; k < n; k++) {
refBit[k] = 0;
}
}
}
} while (hand != 0 || refBit[hand] == 1); // 循环直到找到可替换的页面或回到开始
}
}
// 计算并输出命中率
printf("内存容量为%d页时命中率为%lf\n", n, (double)hitCount / N);
free(memory);
free(refBit);
}
//主函数
void main()
{
printf("----------------------------------初始化操作----------------------------------\n");
Init(); //初始化
printf("\n");
printf("---------------------------------最佳淘汰算法(OPT)---------------------------------\n");
for (int i = 4; i <= 32; i++)
{
OPT(i); //最佳淘汰算法,用户的内存容量4页到32页
}
printf("\n");
printf("--------------------------------先进先出算法(FIFO)---------------------------------\n");
for (int j = 4; j <= 32; j++)
{
FIFO(j); //先进先出算法,用户的内存容量4页到32页
}
printf("\n");
printf("------------------------------最近最久未使用算法(LRU)------------------------------\n");
for (int t = 4; t <= 32; t++)
{
LRU(t); //最近最久未使用算法,用户的内存容量4页到32页
}
printf("\n");
printf("------------------------------最不经常使用页面淘汰算法(LFU)------------------------------\n");
for (int b = 4; b <= 32; b++)
{
SCR(b); //第二次机会页面替换算法,用户的内存容量4页到32页
}
printf("\n");
printf("------------------------------最近没有使用页面淘汰算法(NUR)------------------------------\n");
for (int t = 4; t <= 32; t++)
{
Clock(t); //时钟页面替换算法,用户的内存容量4页到32页
}
system("pause");
}