/*本算法为LUR算法，基本需要为寄存器和栈，尤其是栈的英语为核心，栈中的页面号变化如下：
如果进程访问的某页面与栈中页面号相同，则将该页面号取出，将它压入栈顶，若没，则将栈底页面号取出，
该进程页面号压入栈顶。
*/
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 66565 //最大数量
#define SIZE 3 //页框
int page[MAX]; //物理块数组
int lack[MAX];
typedef struct //栈定义；
{
int top; //栈顶指针
int data[MAX+2]; //栈数据
}Stack;
void InitStack(Stack *&s) //栈初始化
{
s=(Stack *)malloc(sizeof(Stack));
s->top=-1;
}
void in_Stack(Stack *&s,int e,int j) //定位置入栈函数1（已经找到）
{
int i;
for(i=j;i<=s->top;i++)
{
s->data[i]=s->data[i+1]; //栈下移位
}
s->data[s->top]=e;
}
void out_Stack(Stack *s,int e) //定位置入栈函数2（没找到）
{
if(s->top==-1)
return ;
int i,j=0;
for(i=0;i<=s->top;i++)
{
if(s->data[i]==e)
{
j=i;
}
}
for(i=j;i<=s->top;i++)
{
s->data[i]=s->data[i+1];
}
s->data[s->top]=e;
}
void LUR(int p[],int n) //LUR算法函数
{
Stack *s;
InitStack(s);
int i,j,k,flag,size;
for(i=0;i<n;i++)
{
flag=-1;
if(s->top<SIZE) //栈未满时候
{
s->top++;
if(i==0) //当为0时候直接入栈；
{
page[0]=s->data[i]=p[i];
printf("%d m_stack: ",p[i]);
printf("%d---page:",s->data[i]);
printf("%d\n",page[0]);
continue;
}
for(j=0;j<=s->top;j++) //寻找栈中是否已该进程的页面号
{
if(s->data[j]==p[i])
flag=j;
}
if(flag==-1)//假如找不到
{
page[s->top]=s->data[s->top]=p[i]; //入栈
if(s->top==SIZE)
{
page[0]=p[i]; //页框满了的话与栈底页号互换
}
}
else
{
s->top--; //找到指针无须上移
in_Stack(s,p[i],flag);
lack[i]=1;
}
}
else //栈满时候
{
out_Stack(s,p[i]);
for(k=0;k<SIZE;k++)
{
if(page[k]==p[i])
{
lack[i]=1;
break;
}
}
for(k=0;k<SIZE;k++)
{
if(s->data[0]==page[k]) //查找栈底的物理块
{
page[k]=p[i];
}
}
}
//以下为输出
printf("%d m_stack: ",p[i] );
for(j=0;j<=s->top;j++)
printf("%d ",s->data[j]);
printf("---page:");
size=SIZE-1;
if(s->top<SIZE)
{
size=s->top;
}
if(lack[i]==0)
{
//printf(" ");
for(j=0;j<=size;j++)
printf("%d ",page[j]);
}
else
{
printf(" null");
}
printf("\n");
}
}
void main()
{
memset(lack,0,sizeof(lack));
int n,j,p[MAX]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
n=20;
for(j=0;j<=n;j++)
printf("%d ",p[j]);
printf("\n");
LUR(p,n);
}
PS:我竟然忘记放在电脑哪里了，名字又不记得。。还好找到，放在这里先
posted on 2013-05-09 22:55
天YU地___PS，代码人生 阅读(511)
评论(0) 编辑 收藏