maintest.txt

根据ascii码文件中各ascii字符出现的频率情况创建Haffman树

//main test for mem management stimulate program.//////////实验汉字
#include <windows.h>
#include <stdio.h>
#include <time.h>
#include "Ulti.h"
#include "EQueue.h"

#define DEBUG 1

//Strategy
#define FIFO 1
#define LRU  2
#define LFR  3
#define NUR  4

#define SHOW 1

#define PageSize 10
#define SIZE 320
#define VirtualPageSize 32
int  UseMemSize;

char *inFileName="inputData.txt";
char *outFileName="outputData.txt";

struct PageTableType
{
	int pageNum;
	int offset;
	int t;
};

typedef struct PageTableType *  PPageTableType;


int  instructionList[SIZE];

int  virtualMem[SIZE];//Count in page.
int* useMem;
PPageTableType UsePageTable;
PPageTableType VirtualPageTable;

int foundStrategy(char* inS);
int hasMoreSpace(PPageTableType inPageTable,int len);
int hasLocated(PPageTableType UsePageTable,int pageIndex);

PSingleRearSeqQueue gQueue;

int StrategyFun(int inStrategy);
int sFIFO(PSingleRearSeqQueue inQueue);
int sLRU();
int sLFR();
int sNUR();

void updateLRU(int);


int main(int argc,char* argv[])
{
	/*--------Open file--------*/
	FILE* inputFile;
	FILE* outputFile;
	
	int i;
	
	
	
	char Strategy[5];
	int  nStrategy;
	
	if((inputFile=fopen(inFileName,"rb"))==NULL)
	{	
		printf("open inputFile error\n");
		return -1;
	}
	
	if((outputFile=fopen(outFileName,"wb"))==NULL)
	{
		printf("open outputFile error\n");
		return -1;
	}
			
	printf("oepn files success \n");
	
	/*Create the PCB Table*/

	fscanf(inputFile,"useMem=%d\r\n",&UseMemSize);
	fscanf(inputFile,"strategy=%s\r\n",Strategy);

	Strategy[strlen(Strategy)]='\0';
	nStrategy=foundStrategy(Strategy);
	
	if(nStrategy==-1)
		return -1;
	
	/*1 make the random instrution current*/
	int m,m2;
	i=0;
	
	srand((unsigned int)time (NULL));
	while(i<SIZE)
	{
			m=(int)eRandom(316);		//[0,315]
			instructionList[i]=m;	
			i++;
			
			m2=(int)eRandom(m+1)+1;//[0,316]
			instructionList[i]=m2;
			instructionList[i+1]=m2+1;//[0,317]
			i+=2;
			
			m=m2;
			m2=(int)eRandom(m+2)+1;
			instructionList[i]=m2;
			i++;
	}
	
	for(i=0;i<SIZE;i++)
				if(instructionList[i]<0||instructionList[i]>=SIZE)
				{
						printf("error instruction produce\n");
						return -1;
				}
				else
				{
					printf("%d ",instructionList[i]);
					fprintf(outputFile,"%d ",instructionList[i]);
				}
				
	/*Init Mem Space*/
		printf("\nUseMemSzie(pages):%d\n",UseMemSize);
		fprintf(outputFile,"\r\nUseMemSzie(pages):%d\r\n",UseMemSize);

		int len;
		len=UseMemSize*PageSize;
		printf("len:%d",len);
		useMem=(int*)malloc(sizeof(int)*len);
		
		UsePageTable=(PPageTableType)malloc(sizeof(struct PageTableType)*UseMemSize);
	//	VirtualPageTable=(PPageTableType)malloc(sizeof(struct PageTableType)*VirtualPageSize);
		
		for(i=0;i<UseMemSize*PageSize;i++)
			useMem[i]=-1;
		
		for(i=0;i<SIZE;i++)
			virtualMem[i]=-1;

		for(i=0;i<UseMemSize;i++)
		{
			UsePageTable[i].pageNum=-1;
			UsePageTable[i].offset=-1;
			UsePageTable[i].t=-1;
		}


	/*2 main program*/
	int swapTimes=0;
	int pos;
	
	int offset;
	int pageIndex;
	int count;

	gQueue=createNullSingleRearSeqQueue();
	
	printf("Strategy:%d\n",nStrategy);
	fprintf(outputFile,"\r\nStrategy:%d\r\n",nStrategy);
	
	printf("---------main program start---------\n");
	fprintf(outputFile,"---------main program start---------\r\n");
	
	count=0;
	while(count<SIZE)
	{	
		pageIndex=instructionList[count]/PageSize;
		offset=instructionList[count]%PageSize;

		if(SHOW)printf("instructionNum:%d instructionInfo:%d pageIndex:%d offset:%d \n",count,instructionList[count],pageIndex,offset);
		fprintf(outputFile,"instructionNum:%d instructionInfo:%d pageIndex:%d offset:%d \r\n",count,instructionList[count],pageIndex,offset);


		//UseMemSize here means pageSize.
		if((pos=hasLocated(UsePageTable,pageIndex))!=-1)//[0,UseMemSize)
		{	//locate the property page Index.
			if(SHOW)printf("locate without swap(page in mem).\n");
			fprintf(outputFile,"locate without swap(page in mem).\r\n");
			UsePageTable[pos].pageNum=pageIndex;
			useMem[pos*PageSize+offset]=instructionList[count];
		
			switch(nStrategy)
			{
				case FIFO:
							break;
				case LRU:	updateLRU(pos);
								break;
				case LFR:
							break;
				case NUR:
							printf("not finished\n");
							break;
				default:
							printf("error index passin StragetyFun.\n");
							break;	
			}
		


		}
		else if((pos=hasMoreSpace(UsePageTable,UseMemSize))!=-1)
		{
				if(SHOW)printf("locate without swap(has empty mem space).\n");
					fprintf(outputFile,"locate without swap(has empty mem space).\r\n");
					useMem[pos*PageSize+offset]=instructionList[count];
					UsePageTable[pos].pageNum=pageIndex;
			switch(nStrategy)
			{	
				case FIFO:
							enQueue(gQueue,pos);
							//do locateion
									//pageIndex*PageSize+offset
							break;
				case LRU:	updateLRU(pos);
							break;
				case LFR:
							break;
				case NUR:
							printf("not finished\n");
							break;
				default:
							printf("error index passin StragetyFun.\n");
							break;						
			}
		}
		else
			{
				pos=StrategyFun(nStrategy);//got the swap out pageIndex in pageTable.
				if(SHOW)printf("swap out,swap Times:%d swap Out Page Index:%d\n",swapTimes,UsePageTable[pos].pageNum);
				fprintf(outputFile,"swap out,swap Times:%d swap Out Page Index:%d\r\n",swapTimes,UsePageTable[pos].pageNum);
				//Move UseMem to VirtualMem.
				for(i=0;i<PageSize;i++)
						virtualMem[UsePageTable[pos].pageNum*PageSize+i]=useMem[pos*PageSize+i];
				//locate new insruction into mem.
				UsePageTable[pos].pageNum=pageIndex;
				useMem[pos*PageSize+offset]=instructionList[count];
				
				swapTimes++;
			
				//the update in the algorithm datas
				switch(nStrategy)
				{
					case FIFO:	
								enQueue(gQueue,pos);
						
								break;
					case LRU:	updateLRU(pos);
								break;
					case LFR:
							break;
					case NUR:
							printf("not finished\n");
							break;
					default:
							printf("error index passin StragetyFun.\n");
							break;						
				}
			
			}
		count++;
	}

	float ans;
	ans=1-(float)swapTimes/(float)SIZE;
	
	printf("\nStrategy:%d,Effeciency:%f\n",nStrategy,ans);
	printf("---------main program end  ---------\n");
	
	fprintf(outputFile,"\r\nStrategy:%d,Effeciency:%f\r\n",nStrategy,ans);
	fprintf(outputFile,"---------main program end  ---------\r\n");
	
	fclose(inputFile);
	fclose(outputFile);

	printf("program ends successfully\n");
	getchar();
	return 0;
}


int foundStrategy(char* inS)
{
	if(strcmp(inS,"FIFO")==0)
		{
			gQueue=createNullSingleRearSeqQueue();
			return FIFO;
		}
	else if(strcmp(inS,"LRU")==0)
		return LRU;
	else if(strcmp(inS,"LFR")==0)
		return LFR;
	else if(strcmp(inS,"NUR")==0)
		return NUR;
	else 
		{
			printf("in foundStrategy,pass in Strategy is illegal!\n");
			return -1;
			}	
	}


int StrategyFun(int inStrategy)
{
	int rePos=-1;
	switch(inStrategy)
	{
		case FIFO:				rePos=sFIFO(gQueue);
								break;
		case LRU:				rePos=sLRU();
								break;
		case LFR:
								break;
		case NUR:
								printf("not finished\n");
								break;
		default:
								printf("error index passin StragetyFun.\n");
								break;						
		}
		
	return rePos;
}

int sFIFO(PSingleRearSeqQueue inQueue)
{
	return deQueue(inQueue);
}

int sLRU()
{
	int i,maxIndex;

	maxIndex=0;
	if(UsePageTable[0].pageNum==-1)
	{
		printf("in sLRU,Table[0].pageNum==-1\n");
		return -1;
	}
	for(i=1;i<UseMemSize;i++)
		if(UsePageTable[i].pageNum!=-1&&UsePageTable[maxIndex].t<UsePageTable[i].t)
			maxIndex=i;

	return maxIndex;
}



int hasMoreSpace(PPageTableType inPageTable,int len)
{
	int i;
	for(i=0;i<len;i++)
		if(inPageTable[i].pageNum==-1)
			return i;
	i=-1;
	//printf("i=%d",i);
	return i;
}

int hasLocated(PPageTableType UsePageTable,int pageIndex)
{
	int i;
	for(i=0;i<UseMemSize;i++)
		if(UsePageTable[i].pageNum==pageIndex)
			return i;
	return -1;
}

void updateLRU(int pos)
{
	int i;
		for(i=0;i<UseMemSize;i++)
								{
									if(i==pos)
										UsePageTable[i].t=0;
									else if(UsePageTable[i].pageNum!=-1)
									UsePageTable[i].t++;
								}
}