存储管理.cpp

一个操作系统存储管理的程序,十分精彩,同其他版本都不同.

#include <iostream.h>
#include <stdlib.h> 
#include <stdio.h>
#include <time.h>

#define INVALID -1 
#define null 0 

#define total_instruction 320 
#define total_virMem 32
#define min_virMem 4

typedef struct
{ 
    int pageNum;
	int memNum;
	int counter;
	int time; 
}page_type; 
page_type page[total_virMem]; 

struct mem_struct
{ 
	int pageNum,memNum; 
	struct mem_struct *next; 
}; 
typedef struct mem_struct mem_type; 

mem_type mem[total_virMem],*freeMen,*used_head,*usedp; 

int diseffect,a[total_instruction]; 
int pageNo[total_instruction]; 
void initialize(int); 
void FIFO(int); 
void LRU(int);
void LFU(int);
void OPT(int);

main() 
{ 
	int S,i; 
	//srand(time(0));
	S=rand()%total_instruction;
	for(i=0;i<total_instruction;i+=4) 
	{ 
		a[i]=S; 
		a[i+1]=S+1; 
		a[i+2]=(int)(a[i]*rand()/RAND_MAX); 
		a[i+3]=a[i+2]+1; 
		S=(int)((total_instruction-2-a[i+2])*rand()/RAND_MAX)+a[i+2]+2; 
	} 
	for(i=0;i<total_instruction;i++) 
	{ 
		pageNo[i]=a[i]/10; 
	//	cout<<"a["<<i<<"]="<<a[i]<<endl<<"pageNo["<<i<<"]="<<pageNo[i]<<endl;
	} 
	
	cout<<"PAGE    FIFO       LRU       LFU       OPT"<<endl;
	for(i=min_virMem;i<=total_virMem;i++) 
	{ 
		printf("%3d",i);
		FIFO(i); 
		LRU(i); 
		LFU(i);
		OPT(i);
		cout<<endl;
	}
	return 0;
} 

void FIFO(int total_page) 
{ 
	int i; 
	mem_type *p; 
	initialize(total_page); 
	used_head=usedp=null; 
	for(i=0;i<total_instruction;i++) 
	{ 
	//	cout<<"pageNo"<<page[i]<<"="<<pageNo[pageNo[i]].memNum<<endl;
		if(page[pageNo[i]].memNum==INVALID) 
		{ 
			diseffect+=1; 
			if(freeMen==null) 
			{ 
				p=used_head->next; 
				freeMen=used_head; 
				freeMen->next=null; 
				page[pageNo[used_head->pageNum]].memNum=INVALID;
				used_head=p; 
			} 
			p=freeMen->next; 
			freeMen->next=null; 
			freeMen->pageNum=pageNo[i]; 
			page[pageNo[i]].memNum=freeMen->memNum; 
			if(usedp==null) 
			{
				used_head=usedp=freeMen;
			}
			else 
			{ 
				usedp->next=freeMen; 
				usedp=freeMen; 
			} 
			freeMen=p; 
		} 
	} 
	printf("%10.4f",1-(float)diseffect/320); 
} 

void LRU(int total_page) 
  {
	initialize(total_page);
	int present_time=0; 
	for(int i=0;i<total_instruction;i++) 
	{
		if(page[pageNo[i]].memNum==INVALID) 
		{
			diseffect++; 
			if(freeMen==NULL) 
			{
				int min=32767,minj; 
				for(int j=0;j<total_virMem;j++) 
					if(min>page[j].time&&page[j].memNum!=INVALID) 
					{
						min=page[j].time;
						minj=j;
					} 
				freeMen=&mem[page[minj].memNum]; 
				page[minj].memNum=INVALID; 
				page[minj].time=-1; 
				freeMen->next=NULL; 
			} 
			page[pageNo[i]].memNum=freeMen->memNum; 
			page[pageNo[i]].time=present_time; 
			freeMen=freeMen->next; 
		} 
		else page[pageNo[i]].time=present_time; 
		present_time++; 
	} 
	printf("%10.4f%",1-(float)diseffect/320); 
} 

void LFU(int total_page) 
{
	int i,j,min,minpage; 
	initialize(total_page); 
	for(i=0;i<total_instruction;i++) 
	{ 
		if(page[pageNo[i]].memNum==INVALID) 
		{ 
			diseffect++; 
			if(freeMen==NULL) 
			{ 
				min=32767; 
				for(j=0;j<total_virMem;j++) 
				{
					if(min>page[j].counter&&page[j].memNum!=INVALID) 
					{
						min=page[j].counter;
						minpage=j;
					} 
					page[j].counter=0; 
				} 
				freeMen=&mem[page[minpage].memNum]; 
				page[minpage].memNum=INVALID; 
				freeMen->next=NULL; 
			} 
			page[pageNo[i]].memNum=freeMen->memNum; 
			freeMen=freeMen->next; 
		} 
		else  page[pageNo[i]].counter++; 
	}
	printf("%10.4f",1-(float)diseffect/320);
} 

void OPT(int total_page) 
{
	int i,j,max,maxpage,d,dist[total_virMem]; 
	initialize(total_page); 
	for(i=0;i<total_instruction;i++) 
	{ 
		if(page[pageNo[i]].memNum==INVALID) 
		{
			diseffect++; 
			if(freeMen==NULL) 
			{
				for(j=0;j<total_virMem;j++) 
					if(page[j].memNum!=INVALID)
						dist[j]=32767;
					else dist[j]=0; 
				d=1; 
				for(j=i+1;j<total_instruction;j++) 
				{
					if(page[pageNo[j]].memNum!=INVALID) 
						dist[pageNo[j]]=d; 
					d++; 
				} 
				max=-1; 
				for(j=0;j<total_virMem;j++) 
					if(max<dist[j]) 
					{
						max=dist[j];
						maxpage=j;
					}
				freeMen=&mem[page[maxpage].memNum];
				freeMen->next=NULL; 
				page[maxpage].memNum=INVALID; 
			} 
			page[pageNo[i]].memNum=freeMen->memNum; 
			freeMen=freeMen->next; 
		} 
	}
	printf("%10.4f%",1-(float)diseffect/320); 
} 


void initialize(int total_page) 
{ 
	int i; 
	diseffect=0; 
	for(i=0;i<total_virMem;i++) 
	{ 
		page[i].pageNum=i; 
		page[i].memNum=INVALID; 
		page[i].counter=0; 
		page[i].time=-1; 
	} 
	for(i=1;i<total_page;i++) 
	{
		mem[i-1].next=&mem[i];
		mem[i-1].memNum=i-1;
	} 
	mem[total_page-1].next=null;
	mem[total_page-1].memNum=total_page-1; 
	freeMen=&mem[0]; 
}