/*本算法為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，代碼人生 閱讀(574)
評論(0) 編輯 收藏