cstoragecontrol.cpp

演示几种存储控制器的算法

#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#define  clear_period 5
const int ap = 3;
const int pp = 5;
const int n = 100;
int count = 0;
int diseffect = 0 , total_instruction = 0;

void initial(int * page)
{
	int i;

	for (  i = 0 ; i < ap ; i ++)page[i] = -1;

	diseffect = 0 ; total_instruction = 0;
}

float rt( int dis , int tt )
{
	return 1 - (float)dis/(float)tt;
}

void nurfunction(bool * flagused, int * k)
{
	int i = 0 , j = 0 , m[ap+1] ;

	for ( i = 0 ; i <= ap ; i++) m[i] = 0;

	for ( i = 0 ; i < ap ; i++){if ( flagused[i] == false ){ j ++; m[j] = i ;}}

	*k = m[1];	
}

void optfunction( int * pagecontrol , int * page , int * k  )
{
	bool flag = false;
	int j = 0, m = 0 ;
	
	for ( int i = 0 ;i < ap ; i++ )
	{
		flag = false;
		for (  j = *k + 1  ; j < n ; j++ )
		if( flag == false )
		{
			if( page[i] == pagecontrol[j]) flag = true;
            else if(j == n-1)
			{
				m = i;
				break;
			}
		}
	}
	*k = m;
}

int lookfor( int *page , int data)
{
     int j = 0, flag = -1;
	 for ( ; j < ap ; j ++)
	 {
		 if (page[j] == data)
		 {
			 flag = j ;
			 break;
		 }
	 }
	 return flag;
}

void fifo( int * dis ,int * tt , int * pagecontrol,int * page)
{
	int j = 0, i = 0 ;
	for (; i < n ; i ++)
	{		
		if (lookfor(page,pagecontrol[i]) == -1)
		{
			for ( j = ap - 1 ; j > 0 ; j --)
			{
				page[j] = page [j-1];
			}
			page[0] = pagecontrol[i];
			(*dis)++;
	    		
		} 
		(*tt)++;
	}
}

void lru(int * dis ,int * tt , int * pagecontrol, int * page)
{
	int j = 0  , k = 0 ,i = 0;
	for (; i < n ; i ++)	
	{
		 k = lookfor(page,pagecontrol[i]);
		if (k == -1)
		{
			for ( j = ap - 1 ; j > 0 ; j --)
			{
				page[j] = page [j-1];
			}
			page[0] = pagecontrol[i];
			(*dis)++;
		} 
		else{	
				for ( j = k ; j > 0 ; j --)
			{
				page[j] = page [j-1];
			}	
			 page[0] = pagecontrol[i];
		}
		(*tt)++;
	}
}

void nur( int * dis ,int * tt , int * pagecontrol, int * page)
{
	bool flagused[ap] ;
	
	int j = 0,i = 0 , k = -1 , clear_i = -1;

	for ( i = 0 ; i < ap ;i ++)flagused[i] = false;

	for ( i = 0 ; i < n ; i ++)
	{
			if ( count < clear_period)
		{ 
			k = lookfor(page,pagecontrol[i]); 
			if ( k == -1)
			{
				if ( i < 3){
					for ( j = ap - 1 ; j > 0 ; j --)
						page[j] = page [j-1];
					page[0] = pagecontrol[i];
				}
				else nurfunction(flagused,&clear_i);
				page[clear_i]=pagecontrol[i];
				(*dis)++;
				count ++;
			}
			else flagused[k] = true;
			(*tt)++;				
		}
		else {  count = 0; 
				for ( j = 0 ; j < ap ;j ++)flagused[j] = false;
				clear_i = -1;
				i--;
		}
		
	}
}

void opt( int * dis ,int * tt , int * pagecontrol,  int * page)
{
	int j = 0,i = 0 ,k = -1,clear_i = -1 ;
	for (; i < n ; i ++)
	{
		clear_i = i;
		k = lookfor(page,pagecontrol[i]);
 		if ( k == -1)
		{
			if ( i < 3)
			{
				for ( j = ap - 1 ; j > 0 ; j --)
				{
					page[j] = page [j-1];
				}
				page[0]=pagecontrol[i];
			}
			else
			{
				optfunction(pagecontrol,page,&clear_i) ;
				page[clear_i] = pagecontrol[i];
            }
			(*dis)++;		
		} 
		(*tt)++;
	}
}

int main()
{
	int page[ap],pagecontrol[n];
	float fiforate = 0.0 ,lrurate = 0.0 ,nurrate = 0.0 , optrate = 0.0;
	
	for (int i = 0 ; i < n ; i ++)pagecontrol[i] = rand()%pp;

	initial(page);
	fifo(&diseffect,&total_instruction,pagecontrol,page);
	fiforate = rt(diseffect,total_instruction);
	
	initial(page);	
	lru(&diseffect,&total_instruction,pagecontrol,page);
	lrurate = rt(diseffect,total_instruction);

	initial(page);
	nur(&diseffect,&total_instruction,pagecontrol,page);
	nurrate = rt(diseffect,total_instruction);

	initial(page);
	opt(&diseffect,&total_instruction,pagecontrol,page);
	optrate = rt(diseffect,total_instruction);
    
	cout << "fifo命中率 ："<< fiforate * 100 << "%" <<endl;
	cout << "lru 命中率 ："<< lrurate * 100 << "%" <<endl;
	cout << "nur 命中率 ："<< nurrate * 100 << "%" <<endl;
	cout << "opt 命中率 ："<< optrate * 100 << "%" <<endl;
	
	return 0;
}