OSページ置換アルゴリズム

アドレスマッピング中に、アクセスするページがメモリに含まれていないことがページに表示されると、欠落したページ中断が発生します.欠ページ割り込みが発生した場合、オペレーティングシステムは、呼び出されるページにスペースを空けるために、メモリからページを選択する必要があります.どのページを淘汰するかを選択するためのルールをページ置換アルゴリズムと呼ぶ.
    一般的なアルゴリズムには、最適置換アルゴリズム、先進的な先出しアルゴリズム、最近最も長く使用されていないアルゴリズム、clock置換アルゴリズムなどがある.本明細書では、FIFOおよびLRUアルゴリズムを使用します. 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
#define PageMAX 12
#define pMAX 10240.0//     
int PG[PageMAX];//     
int P[PageMAX];//    
int py[PageMAX];//    /*     1024*/ 
int page[3][PageMAX]={{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}};//      ，NULL      
int Q_flag=0;//         
int MZ;//      
void createPage()
{
	int i;
	srand(time(NULL)); 
	for(i=0;i<PageMAX;i++)
	{
		int j;
		j=1+(int)(pMAX*rand()/(RAND_MAX+rand()));
		PG[i]=j;
		P[i]=(int)j/1024;
		py[i]=j%1024;
	}
}
void LRU()
{
	int i,min,j,m,k;
	int flag[3]={0,0,0};
	MZ=0;
	for(i=0;i<PageMAX;i++)
	{
		printf("%5d",P[i]);
	}	
	putchar(10);
	for(i=0;i<PageMAX;i++)
	{
		min=0;
		if(i!=0)
		{
			for(j=0;j<3;j++)
			{
				page[j][i]=page[j][i-1];
			}
		}
		for(j=0;j<3;j++)
		{
			if(page[j][i]==P[i])
				{
					Q_flag=1;
					break;
				}
		}
		if(Q_flag==1)//zhong
		{
			MZ+=1;
			for(k=0;k<3;k++)
					flag[k]--;
			flag[j]=3;		
		}
		if(Q_flag==0)
		{
			for(m=0;m<3;m++)
			{
				if(flag[min]>flag[m])
				{
					min=m;
				//	break;
				}
			}
			page[min][i]=P[i];
			for(k=0;k<3;k++)
					flag[k]--;	
			flag[min]=3;			
		}
		Q_flag=0;	
	}
	putchar(10);
	for(i=0;i<3;i++)
	{
		for(j=0;j<12;j++)
		{
			if(page[i][j]!=-1)
				printf("%5d",page[i][j]);
			else
				printf("%5c",32);
		}
		putchar(10);
	}
	printf("    :%5d
",MZ);
	printf("   ：%0.2f%%
",(MZ/(float)PageMAX)*100);
}
void fifo()
{
	int i,min,j,k;
	int flag[3]={1,0,0};
	MZ=0;
	for(i=0;i<PageMAX;i++)
	{
		printf("%5d",P[i]);
	}	
	putchar(10);
	for(i=0;i<PageMAX;i++)
	{
		if(i!=0)
			for(j=0;j<3;j++)
			{
				page[j][i]=page[j][i-1];
			}
		for(j=0;j<3;j++)
		{
			if(page[j][i]==P[i])
				{
					Q_flag=1;
					break;
				}
		}
		if(Q_flag==0)
		{
			int min;
			for(k=0;k<3;k++)
			{
				if(flag[k]==1)
				{
					min=k;
					break;
				}
			}
			page[min][i]=P[i];
			int tmp;
			tmp=flag[2];
			flag[2]=flag[1];
			flag[1]=flag[0];
			flag[0]=tmp;	
		}
		if(Q_flag==1)
		{
			MZ+=1;
		}
		Q_flag=0;
	}
	putchar(10);
	for(i=0;i<3;i++)
		{
			for(j=0;j<12;j++)
			{
				if(page[i][j]!=-1)
					printf("%5d",page[i][j]);
				else
					printf("%5c",32);
			}
			putchar(10);
		}
	printf("    :%5d
",MZ);
	printf("   ：%0.2f%%
",(MZ/(float)PageMAX)*100);
}

int main()
{
	int i;
	createPage();
	printf("********************************************
");
	printf("      (   :1024B)：
");
	printf("     ：
");
	for(i=0;i<PageMAX;i++)
		printf("%6d",PG[i]);
	putchar(10); 
	printf("    ：
");
	for(i=0;i<PageMAX;i++)
		printf("%5d",py[i]);
	putchar(10);
	printf("    ：
");
	for(i=0;i<PageMAX;i++)
		printf("%5d",P[i]);
	putchar(10);
	printf("FIFO  ：
");		
	fifo();
	putchar(10);
	printf("LRU  :
");
	LRU();
	putchar(10);
	return 0;
}

   
海訳翻訳会社