lru.cpp

C++写的操作系统原理及实现,模拟页面置换程序lru的源码

#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;//页表头指针，指向头结点，头结点指向第一页
};



//lru页面置换程序,函数调用时要传递过来页表pt，要访问的页面号accesspage，返回是否发生缺页中断（1是0否）
int access(struct pagetable *pt, unsigned int accesspage)
{
	struct page *newpage;//新页面
	struct page *currentpage=pt->head->nextpage;//当前页
	struct page *replacedpage;//要淘汰的页
	
	//在当前页中寻找要访问的页号
	while(currentpage&&currentpage->number!=accesspage)
	{
		currentpage=currentpage->nextpage;
	}

	//找到页号则打印√,并返回0
	if(currentpage!=NULL&&currentpage->number==accesspage)
	{
		//将当前结点从链表中取下
		if(currentpage->nextpage)
		{
			currentpage->nextpage->priorpage=currentpage->priorpage;
		}
		currentpage->priorpage->nextpage=currentpage->nextpage;
		//并放在链表头结点后
		currentpage->nextpage=pt->head->nextpage;
		if(pt->head->nextpage)
		{
			pt->head->nextpage->priorpage=currentpage;
		}
		pt->head->nextpage=currentpage;
		currentpage->priorpage=pt->head;	
		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;
	}

	//如页表已经满,则采用lru算法进行淘汰选择
	else
	{
		currentpage=pt->head->nextpage;
		replacedpage=NULL;
		while(currentpage->nextpage)
		{
			currentpage=currentpage->nextpage;
		}
		replacedpage=currentpage;
		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 lru \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]);
	}
	
	printf("\nabsence times:%d\ntotal access times:%d\nabsence ratio:%.2f%%\n",totalabsence,totalpagenum,totalabsence*100.0/totalpagenum);
	getchar();
}