ページ置換アルゴリズム
7063 ワード
もとは1人の師弟の出した問題で、ついでにこれをいっそう強固にして、経典のページの置換のアルゴリズム
#include<iostream>
#include<stdlib.h>
#include<time.h>
#define INVALID -1
#define TRUE 1
#define FALSE 0
using namespace std;
struct page //
{
int page_number; // ,
int hit; // ，
int counter; //
int time; //
};
page pageone[32];
struct page_connect
{
int page_number;//
int hit;
page_connect* next;
};
page_connect pagecon[32];
page_connect *free_head,*busy_head,*busy_tail;
int initialize(int);
int FIFO(int i);
int LRU(int i);
int OPT(int i);
int NRU(int i);
int arr[320];//arr
int pagetotal[320]; //pagetotal
int pageoffset[320]; //pageoffset
int main()
{
srand(unsigned(time(NULL))); //
int k=rand()%320; //
for(int i=0;i<320;i+=4)// 0-319
{
arr[i]=k;
arr[i+1]=arr[i]+1;
arr[i+2]=rand()%arr[i+1];
arr[i+3]=arr[i+2]+1;
int a=319-arr[i+3]-1;
k=rand()%a+arr[i+3]+1;
}
for(int i=0;i<320;i++)//
{
pagetotal[i]=arr[i]/10; //
pageoffset[i]=arr[i]%10; //
}
for(int i=0;i<320;i++)
cout<<arr[i]<<" "<<pagetotal[i]<<" "<<pageoffset[i]<<endl;
for(int i=4;i<32;i++)//i
{
cout<<"page frame="<<i;
FIFO(i);
LRU(i);
OPT(i);
NRU(i);
}
/*for(int i=0;i<320;i++)
int k=pagenum[i];
for(int j=0;j<n;j++)
if(pageone[j].page_number==k&&pageone[j].hit==1)
count++;
else if(pageone[j].hit==0)
{ pageone[j].hit=1;
pageone[j].page_number=k;}
return 0;*/
}
int initialize(int pagenum)// i
{
int i;
for(i=0;i<32;i++) // 32
{
pageone[i].page_number=INVALID; // ，INVALID ，
pageone[i].counter=0; // 0
pageone[i].time=-1; //
}
for(i=0;i<pagenum-1;i++) // pagecon[i] pagecon[i+1] ,
{
pagecon[i].page_number=i; // pagecon[i] i
pagecon[i].next=&pagecon[i+1];// i i+1
}
pagecon[pagenum-1].next=NULL; // next
pagecon[pagenum-1].page_number=pagenum-1; // pagenum-1
free_head=&pagecon[0]; // head ， 0
return 0;
}
int FIFO(int pagenum)// ， pagenum
{
int count=0;//count
page_connect *p; //
initialize(pagenum); //
busy_head=busy_tail=NULL; // ，
for(int i=0;i<320;i++)
{ if(pageone[pagetotal[i]].page_number==INVALID)//i ,
{ count++; // 1
if(free_head==NULL)//
{
p=busy_head->next;//p ，
pageone[busy_head->hit].page_number=INVALID;//
free_head=busy_head;// ，
free_head->next=NULL; // free ，
busy_head=p;//busy_head
}
p=free_head->next;// ， p
free_head->hit=pagetotal[i];
pagecon[pagetotal[i]].page_number=free_head->page_number;
free_head->next=NULL;
if(busy_tail==NULL)//
busy_tail=busy_head=free_head;// ，
else
{
busy_tail->next=free_head;
busy_tail=free_head;
}
free_head=p;
}
}
cout<<"FIFO hit rate="<<1-(double)count/320<<endl;//
return 0;
}
int LRU(int pagenum)// 。 。
{
int count=0;//count
int min,min_index,present_time;//min time ，min_index min
initialize(pagenum);
present_time=0;
for(int i=0;i<320;i++)
{
if(pageone[pagetotal[i]].page_number==INVALID)// ，
{
count++; // 1
if(free_head==NULL) //
{
min=10000; // 10000
for(int j=0;j<32;j++) // ， ，
{
if(min>pageone[j].time&&pageone[j].page_number!=INVALID)//
{
min=pageone[j].time;
min_index=j;//
}
free_head=&pagecon[pageone[min_index].page_number];//
pageone[min_index].page_number=INVALID;//
pageone[min_index].time=0;// 0
free_head->next=NULL; // next
}
pageone[pagetotal[i]].page_number=free_head->page_number;// i
pageone[pagetotal[i]].time=present_time;
free_head=free_head->next; //
}
}
else //
{
pageone[pagetotal[i]].time=present_time;//
present_time++;
}
}
cout<<"LRU hit rate="<<1-(double)count/320<<endl;//
return 0;
}
int OPT(int pagenum) // （OPT）， ，
{
int count=0; //
int max,max_page; //
int des,dest[32]; //
page_connect *p;
initialize(pagenum);
for(int i=0;i<320;i++)
{
if(pageone[pagetotal[i]].page_number==INVALID)//
{
count++; // 1
if(free_head==NULL) //
{
for(int j=0;j<32;j++)
{ if(pageone[j].page_number!=INVALID)//
dest[j]=10000; // ， j dest[j] 10000
else
dest[j]=0; // ， 0
}
for(int k=0;k<32;k++)
{
if((pageone[k].page_number!=INVALID)&&(dest[k]==10000)) // ，
dest[k]=k;
}
max=0;
for(int j=0;i<32;j++)
{
if(max<dest[j])// ， ，
{
max=dest[j]; //
max_page=j; //
}
free_head=&pagecon[pageone[max_page].page_number]; //
}
}
pageone[pagetotal[i]].page_number=free_head->page_number;//
free_head=free_head->next; //
}
}
cout<<"OPT hit rate="<<1-(double)count/320<<endl;//
return 0;
}
int NRU(int pagenum) //
{
int count=0;//
int day,flag,old_day;//day count
page_connect *p; //
initialize(pagenum);//
day=0;
for(int i=0;i<320;i++)
{
if(pageone[pagetotal[i]].page_number==INVALID)//
{
count++; // 1
if(free_head==NULL) //
{
flag=TRUE; //flag 1
old_day=day;
while(flag)
{
if(pageone[day].counter==0&&pageone[day].page_number!=INVALID)// 0
flag=FALSE; //
else
{
day++; //day
if(day==32)//day ，
day=0;
if(day==old_day) // 0
for(int j=0;j<32;j++)
pageone[j].counter=0;
}
}
free_head=&pagecon[pageone[day].page_number];// day
pageone[day].page_number=INVALID;//
free_head->next=NULL; //
}
pageone[pagetotal[i]].page_number=free_head->page_number;// ，
free_head->hit=pagetotal[i];// hit i
free_head=free_head->next;
}
else// ，
pageone[pagetotal[i]].counter=1;// counter 1
if(i%50==0)//i 50， counter 0，
for(int j=0;j<32;j++)
pageone[j].counter=0;
}
cout<<"NRU hit rate="<<1-(double)count/320<<endl;
return 0;
}