实验三 页面置换算法
一. 实验目的：
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;}} //初始化，全部置为-1void _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;}}}/*3207 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1*/