实验三 页面置换算法

一.  实验目的：

1、熟悉虚存管理的各种页面淘汰算法

二、实验环境：

硬件环境：计算机一台，局域网环境；

软件环境：Windows XP及以上版本 Professional操作系统平台，Visual C++ 6.0专业版或企业版。

三 . 实验指导：     

　　制定为进程分配的物理块数；给出该进程的调页顺序，然后采用不同的页面置换算法，给出具体的页面调用情况。

1. 输入具体的物理块数；
2. 给出进程的调页顺序；
3. 选择具体的页面置换算法；
4. 给出该页面置换算法的调页结果，并计算缺页率。

四、实验步骤（含流程图，实验过程分析等）

算法流程：

1. 初始化一个大小为物理块数的数组，用于存储当前在内存中的页面。
2. 遍历给定的引用串中的每个页面。
3. 对于每个页面，检查它是否已经在数组中。如果是，则跳过该页面并继续遍历下一个页面。
4. 如果该页面不在数组中，则需要进行页面置换。
5. 重复步骤3和4，直到遍历完引用串中的所有页面。
6. 计算缺页次数和缺页率。

五、实验结果及分析

图表 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*/