存储管理--页面置换.cpp

关于模拟操作系统的存储管理页面置换程序,挺好的.

#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>

#define EMPTY -1
#define MBLOCK 33

int FIFO_tab[MBLOCK];  // 存放命中率
int LRR_tab[MBLOCK];
int OPT_tab[MBLOCK];
int LFR_tab[MBLOCK];
int NUR_tab[MBLOCK];

int n_block;

struct PageInfo
{
	int PageIndex;
	int count;
}Block[MBLOCK],Page[320];


void generatePageSequence()
{
	int i;
	int nextInstruction;

	for(i=0; i<320; i++)
	{
		switch(i%5)
		{
		case 0: nextInstruction = rand()%320; break;
		case 1: nextInstruction = (nextInstruction+1)%320; break;
		case 2: nextInstruction = rand()%nextInstruction; break;
		case 3: nextInstruction = (nextInstruction+1)%320; break;
		case 4: nextInstruction = nextInstruction + rand()%(320 - nextInstruction);
		}
	    Page[i].PageIndex = nextInstruction/10; 
	}
}

void Clear()
{
	int i;
	for(i=0; i<MBLOCK; i++)
	{
		Block[i].PageIndex = EMPTY;
		Block[i].count = 0;
	}
	for(i=0; i<320; i++)
		Page[i].count = 0;
}

int findPage(int index)
{
	int i;
	for(i=0; i<n_block; i++)
	{
		if(Block[i].PageIndex == index)
			return i;
	}
	return -1;
}

int findSpace()
{
	int i;
	for(i=0; i<n_block; i++)
	{
		if(Block[i].PageIndex == EMPTY)
			return i;
	}
	return -1;
}

int findMaxCount()
{
	int i;
	int maxCount = Block[0].count;
	int pos = 0;

	for(i=1; i<n_block; i++)
	{
		if(Block[i].count > maxCount)
		{
			maxCount = Block[i].count;
			pos = i;
		}
	}
	return pos;
}

int findMinCount()
{
	int i;
	int minCount = Block[0].count;
	int pos = 0;

	for(i=1; i<n_block; i++)
	{
		if(Block[i].count < minCount)
		{
			minCount = Block[i].count;
			pos = i;
		}
	}
	return pos;
}

int findMinVisit(int a[])
{
	int i;
	int min = a[ Block[0].PageIndex ];
	int pos = 0;

	for(i=0; i<n_block; i++)
	{
		if( a[ Block[i].PageIndex ] < min )
		{
			min = a[ Block[i].PageIndex ];
			pos = i;
		}
	}
	return pos;
}

void CountInc(int exception)
{
	int i;
	for(i=0; i<n_block; i++)
		Block[i].count++;
	Block[exception].count = 0;
}

int LookForward(int curPos)
{
	int i, j, maxPos, pos;
	int len[MBLOCK];
	for(i=0; i<n_block; i++)
	{
		for(j=curPos+1; j<320; j++)
			if(Block[i].PageIndex == Page[j].PageIndex)
				break;
		len[i] = j;
	}
	maxPos = len[0];
	pos = 0;
	for(i=1; i<n_block; i++)
	{
		if(len[i] > maxPos)
		{
			maxPos = len[i];
			pos = i;
		}
	}
	return pos;
}

void FIFO()
{
	int i;
	int space;
	int pos;

	for(i=0; i<320; i++)
	{
		if(findPage(Page[i].PageIndex) != -1)
			FIFO_tab[n_block] += 1;
		else
		{
			space = findSpace();
			if(space != -1)
			{
				Block[space].PageIndex = Page[i].PageIndex;
				CountInc(space);
			}
			else
			{
				pos = findMaxCount();
				Block[pos].PageIndex = Page[i].PageIndex;
				CountInc(pos);
			}
		}
	}
	Clear();
}

void LRR()
{
	int i;
	int space;
	int pos;
	int pageFind;

	for(i=0; i<320; i++)
	{
		pageFind = findPage(Page[i].PageIndex);
		if(pageFind != -1)
		{
			Block[pageFind].count = 0;
			LRR_tab[n_block] += 1;
		}
		else
		{
			space = findSpace();
			if(space != -1)
			{
				Block[space].PageIndex = Page[i].PageIndex;
				CountInc(space);
			}
			else
			{
				pos = findMaxCount();
				Block[pos].PageIndex = Page[i].PageIndex;
				CountInc(pos);
			}
		}
	}
	Clear();
}

/*

void LRR()
{
	int i;
	int space;
	int pos;
	int pageFind;

	for(i=0; i<320; i++)
	{
		pageFind = findPage(Page[i].PageIndex);
		if(pageFind != -1)
		{
			Block[pageFind].count++;
			LRR_tab[n_block] += 1;
		}
		else
		{
			space = findSpace();
			if(space != -1)
			{
				Block[space].PageIndex = Page[i].PageIndex;
				Block[space].count = 1;
			}
			else
			{
				pos = findMinCount();
				Block[pos].PageIndex = Page[i].PageIndex;
				Block[pos].count = 1;
			}
		}
	}
	Clear();
}
*/

void OPT()
{
	int i;
	int space;
	int pos;

	for(i=0; i<320; i++)
	{
		if(findPage(Page[i].PageIndex) != -1)
			OPT_tab[n_block] += 1;
		else
		{
			space = findSpace();
			if(space != -1)
				Block[space].PageIndex = Page[i].PageIndex;
			else
			{
				pos = LookForward(i);
				Block[pos].PageIndex = Page[i].PageIndex;
			}
		}
	}
	Clear();
}

void LFR()
{
	int i;
	int space;
	int pos;

	int VisitCount[MBLOCK];

	for(i=0; i<320; i++)
	{
		VisitCount[ Page[i].PageIndex ] += 1;

		if(findPage(Page[i].PageIndex) != -1)
			LFR_tab[n_block] += 1;
		else
		{
			space = findSpace();
			if(space != -1)
				Block[space].PageIndex = Page[i].PageIndex;
			else
			{
				pos = findMinVisit(VisitCount);
				Block[pos].PageIndex = Page[i].PageIndex;
			}
		}
	}
	Clear();
}

void NUR()
{
	int i, j;
	int space;
	int pos;
	int pageFind;
	int intervalTime = n_block - 1;

	for(i=0; i<320; i++)
	{
		for(j=0; i%intervalTime==0 && j<n_block; j++)
			Block[j].count = 0;

		pageFind = findPage(Page[i].PageIndex);
		if( pageFind != -1)
		{
			Block[pageFind].count = 1;
			NUR_tab[n_block] += 1;
		}
		else
		{
			space = findSpace();
			if(space != -1)
				Block[space].PageIndex = Page[i].PageIndex;
			else
			{
				for(pos=0; pos<n_block; pos++)
					if(Block[pos].count==0)
						break;
				Block[pos].PageIndex = Page[i].PageIndex;
			}
		}
	}
	Clear();
}

void Output_Result()
{
	int i;
	cout.precision(3);
	setw(8);
	cout<<"\tFIFO\tLRR\tOPT\tLFR\tNUR"<<endl;
	for(i=4; i<MBLOCK; i++)
	{
		cout<<i<<"\t";
	    cout<<FIFO_tab[i]/320.0<<"\t";
		cout<<LRR_tab[i]/320.0<<"\t";
		cout<<OPT_tab[i]/320.0<<"\t";
		cout<<LFR_tab[i]/320.0<<"\t";
		cout<<NUR_tab[i]/320.0;
		cout<<endl;
	}
}

int main()
{
	generatePageSequence();

	cout<<"***********************************"<<endl;
	cout<<"     先进先出的算法(FIFO)          "<<endl;
    cout<<"     最近最少使用算法(LRR)         "<<endl;
    cout<<"     最佳淘汰算法(OPT)             "<<endl;
	cout<<"     最少访问页面算法(LFR)         "<<endl;
	cout<<"     最近不经常使用算法(NUR)       "<<endl;
	cout<<"***********************************"<<endl;
	cout<<endl;
 
	for(n_block=4; n_block<=32; n_block++)
	{
		FIFO();
		LRR();
		OPT();
		LFR();
		NUR();
	}
	Output_Result();
	return 0;
}