lru.cpp

操作系统中的虚页调度算法

#include<stdio.h>
#include<stdlib.h>
# define OVERFLOW 0
# define OK 1
# define ERROR 0

typedef struct QNode{
  int ID;
  struct QNode * next;
}QNode,*QueuePtr;
typedef struct{
  QueuePtr front;
  QueuePtr rear;
}LinkQueue;
typedef struct{
  int *base;
  int *top;
  int stacksize;
}SqStack;
LinkQueue Q;
SqStack R,S;
int e1,e,i,k,length;
QueuePtr p,q;
int *data;
int STACK_INIT_SIZE;
LinkQueue InitQueue(LinkQueue &Q){
  Q.front=Q.rear=(QueuePtr)malloc(sizeof (QNode));
  if(!Q.front)
    exit(OVERFLOW);
  Q.front->next=NULL;
  return Q;
}
LinkQueue EnQueue(LinkQueue &Q,int i){
  p=(QueuePtr)malloc(sizeof (QNode));
  if(!p)
    exit(OVERFLOW);
  p->ID=data[i];
  p->next=NULL;
  Q.rear->next=p;
  Q.rear=p;
  return Q;
}
DeQueue(LinkQueue &Q,int &e){
  if(Q.front==Q.rear)return ERROR;
  p=Q.front->next;
  e=p->ID;
  Q.front->next=p->next;
  if(Q.rear==p)
     Q.rear=Q.front;
  free(p);
  return OK;
}
void file(){
 int size;
 printf("Please input the data:ID\n");
 printf("(Attention! ID !=0.if ID is 0,input is ending)\n");
  scanf("%d",&data[i]);
  while(data[i]!=0)
    { i++;
      scanf("%d",&data[i]);
    }
  size=i;
  InitQueue(Q);
   for(i=0;i<size;i++)
    EnQueue(Q,i);
}
int InitStack(SqStack &S){
  S.base=(int *) malloc (STACK_INIT_SIZE * sizeof (int));
  if(!S.base)exit(OVERFLOW);
  S.top=S.base;
  //S.stacksize=STACK_INIT_SIZE;
  return OK;
}
int GetTop(SqStack &S,int &e){
  if(S.top==S.base)return ERROR;
  e=*(S.top-1);
  return OK;
}
int Push(SqStack &S,int e){
  *S.top=e;
  S.top++;
  return OK;
}
int Pop(SqStack &S,int &e){
  if(S.top==S.base)return ERROR;
  --S.top;
  e=*S.top;
  return OK;
}
int print(SqStack &S){
  int *m;
  m=S.top;
  if(S.top==S.base)return OK;
  while(S.top!=S.base)//for(j=0;j<i;j++)
   { e=*(S.top-1);
     printf("    %d",e);
     S.top--;
   }
   S.top=m;
   return OK;
}
void main(){
  file();
  printf("Please input the number of the procedures:\n");
  printf("(The number should not be exceed 10)\n");
  scanf("%d",&STACK_INIT_SIZE);
  InitStack(S);
  printf("\nThe condition of the pcbs are:\n");
  DeQueue(Q,e1);
  Push(S,e1);
  length=1;
  i=1;
  while(Q.front!=Q.rear)
    {  printf("The %dth time of the of the pcbs are:",i);
       print(S);
       printf("\n");
       i++;
       DeQueue(Q,e1);
       while(S.top!=S.base)
	{ GetTop(S,e);
	  if(e!=e1)
	   { Pop(S,e);
	     Push(R,e);
	   }
	  if(e==e1)
	   { Pop(S,e);
	     length=length-1;
	     break;
	   }
	}
	 if(length<STACK_INIT_SIZE)
	  while(R.top!=R.base)
	   { Pop(R,e);
	     Push(S,e);
	   }
	 if(length==STACK_INIT_SIZE)
	  { Pop(R,e);
	    length=length-1;
	    while(R.top!=R.base)
	     { Pop(R,e);
	       Push(S,e);
	     }
	  }
	Push(S,e1);
	length++;
   }
   printf("The %dth time of the of the pcbs are:",i);
   print(S);
   printf("\n");

}