页面置换算法；最佳置换算法、先进先出置换算法、最近最久未使用置换算法

一、实验目的和要求

1. 了解虚拟存储技术的特点。

2. 掌握请求页式存储管理的页面置换算法，如最佳（Optimal）置换算法、先进先出（Fisrt In First Out）置换算法和最近最久未使用（LeastRecently Used）置换算法。

二、实验内容

设计模拟实现OPT、FIFO和LRU页面置换算法的C语言程序。

1. OPT算法：需要发生页面置换时，算法总是选择在将来最不可能访问的页面进行置换。

2. FIFO算法：算法总是选择在队列中等待时间最长的页面进行置换。

3. LRU算法：如果某一个页面被访问了，它很可能还要被访问；相反，如果它长时间不被访问，那么，在最近未来是不大可能被访问的。

三、实验步骤

1. 使用C++语言编译程序。

2. 完成算法代码。

3. 运行程序，算出结果。

四、实验源程序

代码：

//’*’代表缺页#include <stdio.h>#include <iostream>#include <queue>#include <stack>#include <set>#include <string>#include <cstring>#include <cmath>#define MAX 1111int mark[MAX];using namespace std;typedef structpage_replacement_algorithm{char page;char interrupt;}PRA;char ans[MAX][MAX];void FIFO(){memset(ans,'0',sizeof(ans));queue<char> q;PRA pra[MAX];int n,m;printf("请输入页面走向(字符表示)和物理块数(整型):\n");scanf("%d %d",&n,&m);getchar();printf("请输入n个字符(不要有空格):\n");for(int i=0; i<n; i++){scanf("%c",&pra[i].page);q.push(pra[i].page);}queue<char> qq;int cnt = 0,tot = 0;for(int i=0; i<m; i++){qq = q;for(int j=0; j<=i; j++){ans[j][i] = qq.front();qq.pop();}pra[i].interrupt = '*';}q = qq;for(int j=m,i=0; j<n; j++,i=0){bool flag = true;while(i < m){ans[i][j] = ans[i][j-1];if(ans[i][j] == q.front()&& flag){q.pop();flag = false;}i++;}if(flag){pra[j].interrupt = '*';for(int r=0; r<m-1; r++)ans[r][j] = ans[r+1][j];ans[m-1][j] = q.front();q.pop();}else{pra[j].interrupt = ' ';}}printf("\n先进先出置换算法:\n");printf("%8s:","页面走向");for(int r=0; r<n; r++) printf("%3c ",pra[r].page);printf("\n");for(int i=0; i<m; i++){printf("%6s%2d:","物理块",i+1);for(int j=0; j<n; j++) printf("%3c ",ans[i][j]);printf("\n");}printf("%8s:","缺页中断");for(int r=0; r<n; r++) printf("%3c ",pra[r].interrupt);printf("\n");}void LRU(){memset(ans,'0',sizeof(ans));PRA pra[MAX];int n,m;printf("请输入页面走向(字符表示)和物理块数(整型):\n");scanf("%d %d",&n,&m);getchar();printf("请输入n个字符(不要有空格):\n");for(int i=0; i<n; i++) scanf("%c",&pra[i].page);for(int i=0; i<m; i++){for(int j=0; j<=i; j++){ans[j][i] = pra[j].page;}pra[i].interrupt = '*';}for(int i=m; i<n; i++){bool flag = true;for(int j=0; j<m; j++){ans[j][i] = ans[j][i-1];if(ans[j][i] == pra[i].page){pra[i].interrupt = ' ';flag = false;}}if(flag){pra[i].interrupt = '*';for(int j=0; j<m; j++);if(ans[j][i] == pra[i-m].page){ans[j][i] = pra[i].page;break;}}}}printf("最近最久未使用置换算法:\n");printf("%8s:","页面走向");for(int r=0; r<n; r++) printf("%3c ",pra[r].page);printf("\n");for(int i=0; i<m; i++){printf("%6s%2d:","物理块",i+1);for(int j=0; j<n; j++) printf("%3c ",ans[i][j]);printf("\n");}printf("%8s:","缺页中断");for(int r=0; r<n; r++) printf("%3c ",pra[r].interrupt);printf("\n");}void OPT(){memset(ans,'0',sizeof(ans));memset(mark,0,sizeof(mark));PRA pra[MAX];int n,m;printf("请输入页面走向(字符表示)和物理块数(整型):\n");scanf("%d %d",&n,&m);getchar();printf("请输入n个字符(不要有空格):\n");for(int i=0; i<n; i++) scanf("%c",&pra[i].page);for(int i=0; i<m; i++){for(int j=0; j<=i; j++){ans[j][i] = pra[j].page;}pra[i].interrupt = '*';}for(int i=m; i<n; i++){bool flag = true;for(int j=0; j<m; j++){ans[j][i] = ans[j][i-1];if(ans[j][i] == pra[i].page){pra[i].interrupt = ' ';flag = false;}}int im;bool Goto = true;int tot = 0;if(flag){pra[i].interrupt = '*';for(int t=i; t<n;t++){for(int j=0; j<m; j++){if(ans[j][i] == pra[t].page&& !mark[pra[i].page]){mark[pra[i].page] = 1;tot++;if(tot == 3){ans[j][i] =pra[i].page;Goto = false;break;}}else if(ans[j][i] !=pra[t].page) im = j;}if(!Goto) break;}if(tot<3) ans[im][i] =pra[i].page;}}printf("\n最佳置换算法:\n");printf("%8s:","页面走向");for(int r=0; r<n; r++) printf("%3c ",pra[r].page);printf("\n");for(int i=0; i<m; i++){printf("%6s%2d:","物理块",i+1);for(int j=0; j<n; j++) printf("%3c ",ans[i][j]);printf("\n");}printf("%8s:","缺页中断");for(int r=0; r<n; r++) printf("%3c ",pra[r].interrupt);printf("\n");}int main(){printf("*********************************************************************欢迎您！*********************************************************************\n");int ca = 0;do{printf("\n请选择置换算法或结束程序:\n");printf("0、结束程序\n1、最佳置换\n2、先进先出\n3、最近最久未使用\n");scanf("%d",&ca);if(ca == 1) OPT();if(ca == 2) FIFO();if(ca == 3) LRU();}while(ca);return 0;}

五、实验结果

最佳置换算法：