操作系统页面置换算法
实验代码：
#include
#define M 4 //物理页数
#define N 20 //需要调入的页数
typedef struct page
{
int num;
int time;
}Page; //物理页项，包括调入的页号和时间Page mm[M]; //4个物理页
int queue1[20],queue2[20],queue3[20]; //记录置换的页int K=0,S=0,T=0; //置换页数组的标识
int pos=0;//记录存在最长时间项
void INIT(){
int i;
for(i=0;i mm[i].num =-1; mm[i].time =0; } } //取得内存中存在时间最久的位置 int GetMax(){ int max=-1; int i; for(i=0;i if(mm[i].time > max){ max=mm[i].time ; pos=i; } } return pos; } //检查最长时间不使用页面 int longesttime(int fold) { int i; int max=-1; for(i=fold;i if(mm[0].num!=i){ mm[0].time++; } if(mm[1].num!=i){ mm[1].time++; } if(mm[2].num!=i){ mm[2].time++; } if(mm[3].num!=i){ mm[3].time++; } } for(i=0;i if(mm[i].time>max){ max=mm[i].time; pos=i; } } return pos; } //检查某页是否在内存 int Equation(int fold){ int i; for(i=0;i if(mm[i].num == fold) return i; } return -1; } //检查物理内存是否已满,-1表满，其他不满int Check(){ int i; for(i=0;i if(mm[i].num == -1) return i; } return -1; } //先进先出 void FIFO(int fold){ int i; int a,b,c; a=Equation(fold); //页已存在 if(a != -1){} //页不存在 else{ b=Check(); //内存还有空闲 if(b != -1){ mm[b].num = fold; } //内存已满，需要置换 else { c=GetMax(); mm[c].num = fold; mm[c].time = 0; } queue1[K++]=fold; } for(i=0;i if(mm[i].num != -1){ mm[i].time ++; } } } void OPT(int fold) { int a,b,c; a=Equation(fold); if(a == -1){//页不在内存 b=Check(); //内存还有空闲 if(b != -1){ mm[b].num = fold; } //内存已满，需要置换 else{ c=longesttime(fold); mm[c].num = fold; mm[c].time = 0; } queue3[T++]=fold; } } void LRU(int fold) { int i; int a,b; int p; a=Equation(fold); if(a != -1)//页已在内存 { //把此项移动到链表最后一项 if(a==3)//此项已经在最后，不需要做任何改动 return; else { p=Equation(-1); if(p==-1)//链表是满的 { for(;a<3;a++) mm[a].num=mm[a+1].num; mm[3].num=fold; } else if(p<=3)//链表不满 { for(;a mm[a].num=mm[a+1].num; mm[a].num=fold; } } } else { b=Check(); if(b!=-1)//不满 mm[b].num=fold; else { for(i=0;i<3;i++) mm[i].num=mm[i+1].num; mm[3].num=fold; } queue2[S++]=fold; } } void main() { int A[N],B[N]; int i; INIT(); printf("请依次输入%d个页面号：\n",N); for(i=0;i scanf("%d",&A[i]); } for(i=0;i B[i]=A[i]; } for(i=0;i FIFO( B[i] ); } printf("FIFO的"); printf("调入队列为："); for(i=0;i printf("%3d",queue1[i]); printf("\n缺页次数为：%6d\n缺页率：%16.6f\n\n",K,(float)K/N); INIT(); for(i=0;i B[i]=A[i]; } for(i=0;i LRU( B[i] ); } printf("LRU的"); printf("调入队列为："); for(i=0;i printf("%3d",queue2[i]); printf("\n缺页次数为：%6d\n缺页率：%16.6f\n\n",S,(float)S/N); INIT(); for(i=0;i B[i]=A[i]; } for(i=0;i OPT( B[i] ); } printf("OPT的"); printf("调入队列为："); for(i=0;i printf("%3d",queue3[i]); printf("\n缺页次数为：%6d\n缺页率：%16.6f\n\n",T,(float)T/N); } 实验结果：