实验三 页面置换算法
一. 实验目的：
1、熟悉虚存管理的各种页面淘汰算法
二、实验环境：
硬件环境：计算机一台，局域网环境；
软件环境：Windows XP及以上版本 Professional操作系统平台，Visual C++ 6.0专业版或企业版。
三 . 实验指导：
制定为进程分配的物理块数；给出该进程的调页顺序，然后采用不同的页面置换算法，给出具体的页面调用情况。
- 输入具体的物理块数；
- 给出进程的调页顺序；
- 选择具体的页面置换算法；
- 给出该页面置换算法的调页结果，并计算缺页率。
四、实验步骤（含流程图，实验过程分析等）
算法流程：
- 初始化一个大小为物理块数的数组，用于存储当前在内存中的页面。
- 遍历给定的引用串中的每个页面。
- 对于每个页面，检查它是否已经在数组中。如果是，则跳过该页面并继续遍历下一个页面。
- 如果该页面不在数组中，则需要进行页面置换。
- 重复步骤3和4，直到遍历完引用串中的所有页面。
- 计算缺页次数和缺页率。
五、实验结果及分析
图表 1 先进先出算法
图表 2 最近最久未使用算法
图表 3 最佳置换算法
六、实验源代码
#include<stdio.h>
#define N 100 //物理块数量上限
#define M 1000 //页面数量上限
int list[N], num; //队列存放物理块对应数据 ,物理块数量
int n, yebiao[M]; //n总数 ，yebiao[M]存放页面号引用串
int miss = 0, missl[N] = { 0 }; //缺页数，missl[n]判断缺页情况
int pro[N], prol[N] = { 0 }; //优先级
int temp; //最久-》存在时记录调用页面
int k = 0; //打印页面号
int cun[M][N], Re = 0; //存放物理块信息，用于后续输出
void init() {
Re = 0;
k = 0;
miss = 0;
for (int i = 0;i < n;i++) {
missl[i] = 0;
}
for (int i = 0; i < num; i++) {
list[i] = -1;
}
} //初始化，全部置为-1
void _print() {
printf("页面号： ");
for (int i = 0;i < n;i++) {
printf(" %d", yebiao[i]);
}
printf("\n\n");
for (int i = 0; i < num; i++) {
printf("物理块： ");
for (int j = 0;j < n;j++) {
if (cun[j][i] == -1) {
printf(" *");
}
else {
printf("%4d", cun[j][i]);
}
}
printf("\n");
}
printf("缺页位置：");
for (int i = 0;i < n;i++) {
if (missl[i] == 1) {
printf(" #");
}
else {
printf(" ");
}
}
k++;
printf("\n");
} //打印队列结果
void jilu() {
for (int i = 0;i < num;i++) {
cun[Re][i] = list[i];
}
Re++;
}
bool cunzai(int x) {
for (int i = 0;i < num;i++) {
if (x == list[i]) {
temp = i; //最近最久未使用存在时排序
return true;
}
}
return false;
} //判断是否在队列内
void inlist(int x) {
for (int i = 0;i < n;i++) {
list[i] = list[i + 1];
}
list[num - 1] = x;
} //进队列
void _printmiss() {
printf("缺页次数:%d \n缺页率:%d/%d\n", miss, miss, n);
}
void priority(int x) {
for (;x < n;x++) {
for (int i = 0;i < num;i++) {
if (list[i] == yebiao[x] && prol[i] == 0) {
pro[i] = x; // 队列i在页表中的位置越靠后优先级越高
prol[i] = 1;
}
}
}
for (int i = 0;i < num;i++) { //页表中不存在队列i 优先级最大
if (prol[i] == 0) {
pro[i] = 1000;
}
}
}//判断优先级
void prosort() {
int templ;
for (int i = 0;i < num - 1;i++) {
for (int j = 0;j < num - 1 - i;j++) {
if (pro[j] < pro[j + 1]) {
templ = pro[j];
pro[j] = pro[j + 1];
pro[j + 1] = templ;
templ = list[j];
list[j] = list[j + 1];
list[j + 1] = templ;
}
}
}
for (int i = 0;i < num;i++) { //复原
prol[i] = 0;
}
} //优先级排序
void optimal() {
init(); //初始化
int count = n;
int i = 0;
while (count != 0) {
if (i < num) {
list[i] = yebiao[i];
miss++;
missl[i] = 1;
}
else if (cunzai(yebiao[i])) {
}
else {
priority(i);
prosort();
inlist(yebiao[i]);
miss++;
missl[i] = 1;
}
jilu();
count--;
i++;
}
_print();
_printmiss();
}
void fifo() { //先进先出
init(); //初始化
int count = n;
int i = 0;
while (count != 0) {
if (i < num) {
list[i] = yebiao[i];
miss++;
missl[i] = 1;
}
else if (cunzai(yebiao[i])) {
}
else {
inlist(yebiao[i]);
miss++;
missl[i] = 1;
}
count--;
i++;
jilu();
}
_print();
_printmiss();
}
void lru() { //最近最久未使用
init(); //初始化
int count = n;
int i = 0;
while (count != 0) {
if (i < num) {
list[i] = yebiao[i];
miss++;
missl[i] = 1;
}
else if (cunzai(yebiao[i])) {
list[num] = list[temp];
for (int j = temp;j <= num;j++) {
list[j] = list[j + 1];
}
}
else {
inlist(yebiao[i]);
miss++;
missl[i] = 1;
}
jilu();
count--;
i++;
}
_print();
_printmiss();
}
int main() {
printf("请输入物理块数量:");
scanf("%d", &num);
printf("请输入要访问的页面总数:");
scanf("%d", &n);
printf("请输入要访问的页面号:");
for (int i = 0; i < n; i++) {
scanf("%d", &yebiao[i]);
}
int chose = 1;
while (chose) {
printf("请选择所需的置换算法:\n");
printf("1.FIFO 2.LRU 3.0PT 4.退出\n");
scanf("%d", &chose);
if (chose == 1) {
fifo();
}
if (chose == 2) {
lru();
}
if (chose == 3) {
optimal();
}
if (chose == 4) {
break;
}
}
}
/*
3
20
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
*/