页面置换算法（FIFO+LRU+Clock）

题目：页面置换算法
一、实验目的
1、对页面置换做进一步的理解。
2、了解页面置换的任务。
3、通过编程掌握页面置换算法及缺页率。
4、了解Belady现象和抖动现象。
二、实验内容及要求
1、任意给出一组页面访问顺序（如页面走向是1、2、5、7、5、7、1、4、3、5、6、4、3、2、1、5、2）。
2、分配给该作业一定的物理块（如3块、4块等）。
3、利用FIFO、LRU和Clock页面置换算法模拟页面置换过程并计算其缺页率并分析结果。
4、通过给出特殊的页面访问顺序（如：1，2，3，4，1，2，5，1，2，3，4，5），分配不同的物理块，利用FIFO算法计算其缺页率，进一步理解Belady现象。

代码：

#include <iostream>
using namespace std;

//描述物理块的数据结构
typedef struct freeBlock
{
	int blockIndex;//物理块号
	int blockTime;//访问时间
	int modify;//修改位
	int flag;//访问位
	struct freeBlock*next;
}freeBlock;

//描述作业页面情况的数据结构	
typedef struct jobQueue
{
	int jobIndex;//作业页面号
	struct jobQueue*next;
}jobQueue;

//创建作业页面
jobQueue*jobCreate(jobQueue*head, int num)
{
	jobQueue*job = (jobQueue*)malloc(sizeof(jobQueue));
	job->jobIndex = num;
	job->next = NULL;
	if (!head)
		head = job;
	else
	{
		//如果存在下一个作业块指针就后移
		jobQueue*j = head;
		while (j->next)
			j = j->next;
		j->next = job;
	}
	return head;
}

//创建物理块
freeBlock*blockCreate(freeBlock*head)
{
	freeBlock*free = (freeBlock*)malloc(sizeof(freeBlock));
	free->blockIndex = -1;
	free->blockTime = 0;
	free->modify = 0;
	free->flag = 0;
	free->next = NULL;
	if (head)
		free->next = head;
	head = free;
	return head;
}
//检查J号作业是否在内存中
bool check(freeBlock*free, int j)
{
	freeBlock*f = free;
	while (f)
	{
		if (f->blockIndex == j)
			return true;
		f = f->next;
	}
	return false;
}

//FIFO页面置换算法
void FIFO(freeBlock*free, jobQueue*job, int numbers)
{
	int size = 0, Time = 0, time = 0, lackJobNumbers = 0, allJobNumbers = 0;
	jobQueue*jtest = job;
	freeBlock*ftest = free;
	allJobNumbers = numbers;
	//计算出有几个内存块
	while (ftest)
	{
		size++;
		ftest = ftest->next;
	}
	cout << "====================FIFO页面置换过程====================" << endl;
	while (jtest)
	{
		ftest = free;
		while (ftest)
		{
			//若内存块索引（标记）中为默认-1，也就是没有作业占用就将作业调入并改变索引值
			if (ftest->blockIndex == -1)
			{
				cout << "缺页中断，但有空闲物理块，调入" << jtest->jobIndex << "号页面" << endl;
				ftest->blockIndex = jtest->jobIndex;
				ftest->blockTime++;
				lackJobNumbers++;
				time = 0;
				break;
			}
			ftest->blockTime++;
			if (Time < ftest->blockTime)
				Time = ftest->blockTime;
			//time用于记录内存中已用内存块的数量
			time++;
			ftest = ftest->next;
		}
		ftest = free;
		//当time=内存物理块时也就是内存块中没有空闲内存块时进行置换（淘汰）
		while ((time == size) && ftest)
		{
			//若内存中没有空闲块就检查内存块中是否有此作业，有就不进行置换
			if (check(free, jtest->jobIndex))
			{
				cout << "当前内存中有" << jtest->jobIndex << "号页面，无需中断" << endl;
				time = 0;
				Time = 0;
				break;
			}
			//若此内存块被访问次数等于Time时也就是最久未使用时进行置换
			if (ftest->blockTime == Time)
			{
				cout << "缺页中断，且没有空闲物理块，调出" << ftest->blockIndex << "号页面，调入" << jtest->jobIndex << "页面" << endl;
				ftest->blockIndex = jtest->jobIndex;
				ftest->blockTime = 1;
				time = 0;
				Time = 0;
				lackJobNumbers++;
				break;
			}
			ftest = ftest->next;
		}
		jtest = jtest->next;
	}
	cout << "缺页率为" << (float)lackJobNumbers / (float)allJobNumbers * 100 << "%" << endl;
}

//LRU页面置换算法
void LRU(freeBlock*free, jobQueue*job, int numbers)
{
	//time用于记录调入某一作业时访问内存块的次数，Time用于记录某一内存块的被访问次数
	int size = 0, Time = 0, time = 0, lackJobNumbers = 0, allJobNumbers = 0;
	jobQueue*jtest = job;
	freeBlock*ftest = free;
	allJobNumbers = numbers;
	//记录内存物理块的数量
	while (ftest)
	{
		size++;
		ftest = ftest->next;
	}
	cout << "====================LRU页面置换过程====================" << endl;
	while (jtest)
	{
		ftest = free;
		while (ftest)
		{
			//若此内存块中有当前作业页面
			if (ftest->blockIndex == jtest->jobIndex)
			{
				cout << "当前内存中有" << jtest->jobIndex << "号页面，无需调入" << endl;
				ftest->blockTime = 0;
			}
			//若内存中没有当前作业就调入当前内存中且当前内存中有空闲内存块
			if (ftest->blockIndex == -1)
			{
				cout << "缺页中断，但有空闲物理块，调入" << jtest->jobIndex << "号页面" << endl;
				ftest->blockIndex = jtest->jobIndex;
				ftest->blockTime++;
				time = 0;
				lackJobNumbers++;
				break;
			}
			ftest->blockTime++;
			if (Time < ftest->blockTime)
				Time = ftest->blockTime;
			time++;
			ftest = ftest->next;
		}
		ftest = free;
		//当time=内存物理块时也就是内存块中没有空闲内存块时进行置换（淘汰）
		while ((time == size) && ftest)
		{
			//检查内存块中是否有当前作业页面，有就返回true，否则返回false
			if (check(free, jtest->jobIndex))
			{
				time = 0;
				Time = 0;
				break;
			}
			//若此内存块被访问次数等于Time时也就是最久未使用时进行置换
			if (ftest->blockTime == Time)
			{
				cout << "缺页中断，且没有空闲物理，调出" << ftest->blockIndex << "号页面，调入" << jtest->jobIndex << "页面" << endl;
				ftest->blockIndex = jtest->jobIndex;
				ftest->blockTime = 1;
				time = 0;
				Time = 0;
				lackJobNumbers++;
				break;
			}
			ftest = ftest->next;
		}
		jtest = jtest->next;
	}
	cout << "缺页率为" << (float)lackJobNumbers / (float)allJobNumbers * 100 << "%" << endl;
}

//CLOCK页面置换算法
void G_CLOCK(freeBlock*free, jobQueue*job, int numbers)
{
	//time用于记录调入某一作业时访问内存块的次数
	int size = 0, time = 0, lackJobNumbers = 0, allJobNumbers = 0;
	bool isFind_1 = false, isFind_2 = false;
	jobQueue*jtest = job;
	freeBlock*ftest = free;
	allJobNumbers = numbers;
	//记录内存物理块的数量
	while (ftest)
	{
		size++;
		ftest = ftest->next;
	}
	cout << "====================Clock页面置换过程====================" << endl;
	while (jtest)
	{
		ftest = free;
		while (ftest)
		{
			//若此内存块中有当前作业页面
			if (ftest->blockIndex == jtest->jobIndex)
			{
				cout << "当前内存中有" << jtest->jobIndex << "号页面，无需调入" << endl;
				break;
			}
			//若内存中没有当前作业就调入当前内存中且当前内存中有空闲内存块
			if (ftest->blockIndex == -1)
			{
				cout << "缺页中断，但有空闲物理块，调入" << jtest->jobIndex << "号页面" << endl;
				ftest->blockIndex = jtest->jobIndex;
				time = 0;
				lackJobNumbers++;
				ftest->flag = 1;
				break;
			}
			//给内存块修改位随机赋值0或1
			ftest->modify = rand() % 2;
			time++;
			ftest = ftest->next;
		}
		//当time=内存物理块时也就是内存块中没有空闲内存块时进行置换（淘汰）
		ftest = free;
		while (time == size && ftest != NULL)
		{
			//检查内存块中是否有当前作业页面，有就返回true，否则返回false
			if (check(free, jtest->jobIndex))
			{
				cout << "当前内存中有" << jtest->jobIndex << "号页面，无需调入" << endl;
				time = 0;
				break;
			}
			//查找访问位和修改为均为0的内存块
			if (ftest->modify == 0 && ftest->flag == 0)
			{
				cout << "缺页中断，且没有空闲物理块，调出" << ftest->blockIndex << "号页面，调入" << jtest->jobIndex << "页面" << endl;
				ftest->blockIndex = jtest->jobIndex;
				ftest->flag = 1;
				time = 0;
				isFind_1 = true;
				isFind_2 = true;
				lackJobNumbers++;
				break;
			}
			ftest = ftest->next;
		}
		//找到访问位为0修改为1的内存块，并将扫描到的访问位改为0
		if (time == size && !isFind_1)
		{
			ftest = free;
			while (ftest != NULL)
			{
				if (ftest->flag == 0 && ftest->modify == 1)
				{
					cout << "缺页中断，且没有空闲物理块，调出" << ftest->blockIndex << "号页面，调入" << jtest->jobIndex << "页面" << endl;
					ftest->blockIndex = jtest->jobIndex;
					ftest->flag = 1;
					isFind_1 = true;
					isFind_2 = true;
					time = 0;
					break;
				}
				else
					ftest->flag = 0;
				ftest = ftest->next;

			}
		}
		//未找到第二类页面，则将指针返回到开始位置，并将所有访问位复0.返回第一步
		if (time == size && !isFind_2)
		{
			ftest = free;
			while (ftest)
			{
				ftest->flag = 0;
				ftest = ftest->next;
			}
			ftest = free;
			while (ftest)
			{
				if (ftest->modify == 0 && ftest->flag == 0)
				{
					cout << "缺页中断，且没有空闲物理块，调出" << ftest->blockIndex << "号页面，调入" << jtest->jobIndex << "页面" << endl;
					ftest->blockIndex = jtest->jobIndex;
					ftest->flag = 1;
					time = 0;
					isFind_1 = true;
					isFind_2 = true;
					lackJobNumbers++;
					break;
				}
				ftest = ftest->next;
			}
		}
		jtest = jtest->next;
		time = 0;
		isFind_1 = false;
		isFind_2 = false;
	}
	cout << "缺页率为" << (float)lackJobNumbers / (float)allJobNumbers * 100 << "%" << endl;
}
void main()
{
	int jobNumbers, inPutNumbers, inPutBlockNumbers, choice = 0, i = 0;
	freeBlock*block = NULL;
	jobQueue*job = NULL;
	cout << "设定物理块数:";
	cin >> inPutBlockNumbers;
	for (i = 0; i < inPutBlockNumbers; i++)
		block = blockCreate(block);
	cout << "访问的页面总个数:";
	cin >> jobNumbers;
	cout << "页面访问顺序（页面走向）：";
	for (i = 0; i < jobNumbers; i++)
	{
		cin >> inPutNumbers;
		job = jobCreate(job, inPutNumbers);
	}
	cout << endl << endl;
	cout << "====================算法选择====================" << endl;
	cout << " 1 FIFO  2 LRU  3 CLOCK " << endl;
	cin >> choice;
	cout <<  endl;
	switch (choice)
	{
	case 1:FIFO(block, job, jobNumbers); break;
	case 2:LRU(block, job, jobNumbers); break;
	case 3:G_CLOCK(block, job, jobNumbers); break;
	default:exit(0);
	}
	cout << endl << endl;
}

运行结果：
1、FIFO

【Belady现象】



2、LRU

3、Clock