#include <stdio.h>
#define M 3 //物理页数
#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<M;i++){
mm[i].num =-1;
mm[i].time =0;
}
}
//取得内存中存在时间最久的位置
int GetMax(){
int max=-1;
int i;
for(i=0;i<M;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<N;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<M;i++){
if(mm[i].time>max){
max=mm[i].time;
pos=i;
}
}
return pos;
}
//检查某页是否在内存
int Equation(int fold){
int i;
for(i=0;i<M;i++){
if(mm[i].num == fold)
return i;
}
return -1;
}
//检查物理内存是否已满,-1表满，其他不满
int Check(){
int i;
for(i=0;i<M;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<M;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<p-1;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<N;i++){
scanf("%d",&A[i]);
}
//FIFO
for(i=0;i<N;i++){
B[i]=A[i];
}
for(i=0;i<N;i++){
FIFO( B[i] );
}
printf("FIFO的");
printf("调入队列为：");
for(i=0;i<K;i++)
printf("%3d",queue1[i]);
printf("\n缺页次数为：%6d\n缺页率：%16.6f\n\n",K,(float)K/N);
//LRU
INIT();
for(i=0;i<N;i++){
B[i]=A[i];
}
for(i=0;i<N;i++){
LRU( B[i] );
}
printf("LRU的");
printf("调入队列为：");
for(i=0;i<S;i++)
printf("%3d",queue2[i]);
printf("\n缺页次数为：%6d\n缺页率：%16.6f\n\n",S,(float)S/N);
//OPT
INIT();
for(i=0;i<N;i++){
B[i]=A[i];
}
for(i=0;i<N;i++){
OPT( B[i] );
}
printf("OPT的");
printf("调入队列为：");
for(i=0;i<T;i++)
printf("%3d",queue3[i]);
printf("\n缺页次数为：%6d\n缺页率：%16.6f\n\n",T,(float)T/N);
}
