opt.cpp

C++写的操作系统原理及实现,模拟页面置换算法OPT的源码

#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "ctype.h"

//定义页,采用双向链表存储结构
struct page
{	
	unsigned int number;//页号
	unsigned int baseaddress;//页开始地址
	//其它信息
	struct page *nextpage,*priorpage;//下一页和前一页
};

//定义页表
struct pagetable
{	
	unsigned int pid;//进程号
	unsigned int pagenum;//页表大小
	unsigned int pagetablesize;//页表最大表目
	struct page *head;//页表头指针，指向头结点，头结点指向第一页
};

//OPT页面访问程序,函数调用时要传递过来页表pt，要访问的页面号accesspage，剩余页面列表restpage，剩余页数restpagenum，返回是否发生缺页中断（1是0否）
int access(struct pagetable *pt, unsigned int accesspage,unsigned int *restpage,unsigned int restpagenum)
{
	struct page *newpage;//新页面
	struct page *currentpage=pt->head->nextpage;//当前页
	struct page * replacedpage;//要淘汰的页
	unsigned int count=0;//计数器记录当前要淘汰的页面多少次之后才重新访问到
	unsigned int i;

	//在当前页中寻找要访问的页号
	while(currentpage!=NULL && currentpage->number!=accesspage)
	{
		currentpage=currentpage->nextpage;
	}

	//找到页号则打印√,并返回0
	if(currentpage!=NULL && currentpage->number==accesspage)
	{
		printf("√");
		return 0;
	}

	//没找到则判断页表是否已经满了,没满则调入新页并打印×返回1
	else if(pt->pagenum<pt->pagetablesize)
	{
		newpage=(struct page *)malloc(sizeof(struct page));
		newpage->number=accesspage;
		newpage->nextpage=newpage->priorpage=NULL;
		newpage->nextpage=pt->head->nextpage;
		if(pt->head->nextpage)
		{
			pt->head->nextpage ->priorpage=newpage;
		}
		pt->head->nextpage=newpage;		
		newpage->priorpage=pt->head;
		pt->pagenum++;
		printf("×");
		return 1;
	}

	//如页表已经满,则采用OPT算法进行淘汰选择
	else
	{
		currentpage=pt->head->nextpage;
		replacedpage=NULL;
		count=0;
		while(currentpage)
		{
			i=0;
			while(i<restpagenum&&restpage[i]!=currentpage->number)
			{
				i++;
			}
			if(count<i)
			{
				count=i;
				replacedpage=currentpage;
			}
			currentpage=currentpage->nextpage;
		}
		if(replacedpage->nextpage)
		{
			replacedpage->nextpage->priorpage=replacedpage->priorpage;
		}
		replacedpage->priorpage->nextpage=replacedpage->nextpage;
		free(replacedpage);
		newpage=(struct page *)malloc(sizeof(struct page));
		newpage->number=accesspage;
		newpage->nextpage=newpage->priorpage=NULL;
		newpage->nextpage=pt->head->nextpage; 
		if(pt->head->nextpage)
		{
			pt->head->nextpage->priorpage=newpage;
		}
		pt->head->nextpage=newpage;		
		newpage->priorpage=pt->head;		
		printf("×");
		return 1;
	}
}
main()
{
	struct pagetable pt;
	unsigned int accesspage;
	unsigned int totalabsence=0,totalpagenum=10;
	unsigned int restpage[100];
	unsigned int i=0;
	pt.pagenum=0;
	pt.pagetablesize=3;
	pt.head=(struct page*)malloc(sizeof(struct page));
	pt.head->nextpage=pt.head->priorpage=NULL;

	//从文件获取要读入的页面流
	FILE *fp;
	fp=fopen("IN.dat","r");
	if(fp==NULL)
	{
		printf("can not open file IN.DAT!");
		return;
	}
	while(!feof(fp))
	{		
		fscanf(fp,"%d",&restpage[i]);
		i++;
	}
	fclose(fp);
	totalpagenum=i;

	printf("this program for opt \n\n");
	//打印要访问的页
	for(i=0;i<totalpagenum;i++)
	{
		printf("%2d",restpage[i]);
	}

	printf("\n");
	
	//调用函数访问页
	for(i=0;i<totalpagenum;i++)
	{
		totalabsence+=access(&pt,restpage[i],restpage+i+1,totalpagenum-i);
	}

	printf("\nabsence times:%d\ntotal access times:%d\nabsence ratio:%.2f%%\n",totalabsence,totalpagenum,totalabsence*100.0/totalpagenum);
	getchar();
}