lru.cpp

几个实现操作系统算法的小程序 有哲学家 算法 生产者消费者等算法的实现 供初学者学习参考

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

#define MAXPAGE 100
#define NUM 3

int time = 0;//完成时间
int page[NUM];//分配给进程的页块数

int AccessSeq(int * head);//读取页面访问序列
void InitPage(int * head);//页面初始化
void MovePage(int * head, int indix);//一个页面移动到队尾
int FullPage(int * head);//判断页面是否分配完
int MarchPage(int * page, int num);//判断页面是否命中
int LRU(int *page, int *head, int length);//LRU分配算法,输入是页块数,页面访问序列和序列长度,返回是缺页数

int main()
{
	int head[MAXPAGE], count;

	time = AccessSeq(head);//读取页面访问序列
	InitPage(page);//对页面初始化
	count = LRU(page, head, time);//计算缺页数

	printf("The finished time is: %d\n"
		"The page fault is: %d\n"
		"The page fault ratio is: %d%%\n", time, count, count*100/time);

	return 0;
}

int AccessSeq(int * head)
{
	FILE* fp;
	int indix, count;

	if(!(fp = fopen( "page.txt","r" )))
	{//文件读取失败
		printf("NO THAT FILE\n");
		exit(0);
	}

	fscanf(fp, "%d", &count);//读取访问序列长度

	for(indix = 0; indix < count; indix++)//获得页面访问序列
		fscanf(fp, "%d", &head[indix]);

	return count;//返回访问序列长度
}

void InitPage(int * page)
{//对页面进行初始化,未使用的页面为-1
	for(int i = 0; i < NUM; i++)
		page[i] = -1;
}

void MovePage(int * page, int indix)
{//将最近被访问到的页面移到队列的尾部
	int temp, pointer;

	temp = page[indix];
	pointer = FullPage(page);

	for(int i = indix; i < pointer - 1; i++)
		page[i] = page[i + 1];
	page[pointer - 1] = temp;//最近被访问到的页面移到队尾
}

int FullPage(int * page)
{//返回队列中还可分配页面的指针
	for(int i = 0; i < NUM; i++)
		if(page[i] == -1)
			return i;
	return NUM;
}

int MarchPage(int * page, int num)
{//返回队列中分配页面的指针
	for(int i = 0; i < NUM; i++)
		if(page[i] == num)
			return i;
	return -1;
}

int LRU(int * page, int * head, int length )
{//最近最久未使用置换算法
	int count = 0, pointer1, pointer2;

	for(int i = 0; i < length; i++)
	{
		if((pointer1 = MarchPage(page, head[i])) != -1)
		{//页面已分配,将分配的页面移到队尾
			MovePage(page, pointer1);
			continue;
		}
		else
			if((pointer2 = FullPage(page)) != NUM)//页面未被分配
				page[pointer2] = head[i];//从可分配的页面中分配一个页面
			else
			{//无可分配的页面,则将最久未使的页面替换掉
				page[0] = head[i];
				MovePage(page, 0);//将页面移动到队尾
				count++;//缺页数加1
			}
	}

	return count;//返回缺页数
}