操作系统实验:虚拟存储器 (C语言实现) 模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

一实验内容：

模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

二.实验题目：

模拟分页式存储管理中硬件的地址转换和产生缺页中断。

用先进先出（FIFO）页面调度算法处理缺页中断。

由于是模拟调度算法，所以，不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。

三.代码实现：

指令集包括pageNumber(页号) ,offset(单元号), operation(操作)三个成员组成，本次程序初始化指令集如下图所示：(该表已在“void Order_init() ”函数中预写入)

注:初始化(initial)时默认上表的0-3号页面已装入主存，且使用了内存块的第1，5，8，9块(Memory_used[Mnum])。

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

#define Pnum 7 //页表长度
#define Mnum 10 //主存块数
#define Onum 12 //指令集总数

struct Page_table 
{
	int pageNumber; //页号
	int memoryBlock; //主存块号
	int flag;  //标志位 0表示页不在主存 1表示页在主存
	int diskLocation; //磁盘位置
}page_table[Pnum];

struct Order_table
{
	int pageNumber;//页号
	int offset; //单元号
	char operation; //操作
}Order_table[Onum];
  
int before_page = -1;//保存被FIFO算法置换出的页号
int Memory_uesd[Mnum] = {1,0,1,1,1,0,1,1,0,0}; //数组下标表示块号，对应值为0表示未使用，
												//1模拟被非页占用 2模拟内存分配给模拟作业的块数，本次模拟分配4块，块号依次为1，5，8，9
int Memory_list[4] = { 0,1,2,3 }; //表示已被装入内存的页号，共四个位置,初始默认0，1，2，3页已装入 若未装入，则用-1占位
void show_page_table() //打印当前页表
{
	printf("【页表】:\n");
	int i = 0;
	for (i; i < Pnum; i++)
	{
		printf("页号:%d", page_table[i].pageNumber);
		printf("  块号:%2d", page_table[i].memoryBlock);
		printf("  标志位:%d", page_table[i].flag);
		printf("  磁盘位置:%.3d\n", page_table[i].diskLocation);
	}
	printf("\n");
}

void show_Memory_list() //打印已装入内存的页及其对应在内存中的块号
{
	int i = 0;
	for (i; i < 4; i++)
	{
		if (Memory_list[i] != -1)
		{
		printf("【%d】:第%d页-->第【%d】块\n",i,Memory_list[i],page_table[Memory_list[i]].memoryBlock);
		}
	}
}
void Order_init()  //指令集初始化
{
	//逻辑地址：pageNumber+offset
	//设置指令集  C:存 Q:取 Y：移位
	Order_table[0].operation = '+'; Order_table[0].pageNumber = 0; Order_table[0].offset = 70;
	Order_table[1].operation = '+'; Order_table[1].pageNumber = 1; Order_table[1].offset = 50;
	Order_table[2].operation = 'X'; Order_table[2].pageNumber = 2; Order_table[2].offset = 15;
	Order_table[3].operation = 'C'; Order_table[3].pageNumber = 3; Order_table[3].offset = 21;
	Order_table[4].operation = 'Q'; Order_table[4].pageNumber = 0; Order_table[4].offset = 56;
	Order_table[5].operation = '-'; Order_table[5].pageNumber = 6; Order_table[5].offset = 40;
	Order_table[6].operation = 'Y'; Order_table[6].pageNumber = 4; Order_table[6].offset = 53;
	Order_table[7].operation = '+'; Order_table[7].pageNumber = 5; Order_table[7].offset = 23;
	Order_table[8].operation = 'C'; Order_table[8].pageNumber = 1; Order_table[8].offset = 37;
	Order_table[9].operation = 'Q'; Order_table[9].pageNumber = 2; Order_table[9].offset = 78;
	Order_table[10].operation = '+'; Order_table[10].pageNumber = 4; Order_table[10].offset = 1;
	Order_table[11].operation = 'C'; Order_table[11].pageNumber = 6; Order_table[11].offset = 84;
}

void initial() //初始化
{
	//pageNumber初始化
	int i=0;
	for (i; i < Pnum; i++)
	{
		page_table[i].pageNumber = i;
	}
	//初始化假设0-3号页已装入主存 flag置为1,且对应Memory_used[]中的值也要修改
	//第0页
	page_table[0].flag = 1; page_table[0].memoryBlock = 5; page_table[0].diskLocation = 11;
	//第1页
	page_table[1].flag = 1; page_table[1].memoryBlock = 8; page_table[1].diskLocation = 12;
	//第2页
	page_table[2].flag = 1; page_table[2].memoryBlock = 9; page_table[2].diskLocation = 13;
	//第3页
	page_table[3].flag = 1; page_table[3].memoryBlock = 1; page_table[3].diskLocation = 21;
	//第4页
	page_table[4].flag = 0; page_table[4].memoryBlock = -1; page_table[4].diskLocation = 22;
	//第5页
	page_table[5].flag = 0; page_table[5].memoryBlock = -1; page_table[5].diskLocation = 23;
	//第6页
	page_table[6].flag = 0; page_table[6].memoryBlock = -1; page_table[6].diskLocation = 121;
	//模拟预装入过程
	Memory_uesd[1] = 2;
	Memory_uesd[5] = 2;
	Memory_uesd[8] = 2;
	Memory_uesd[9] = 2;
}

int check_inMemory(int page) //判断该页号是否已装入内存 返回1表示装入 -1表示未装入
{
	int flag=-1; //标识符初始化为-1
	if (page_table[page].flag == 1)
	{
		flag = 1;
	}
	return flag;
}

int check_fullList()  //找到模拟memory_list表中第一个空闲格的下标并返回，未找到则返回-1表示list表已满
{
	int flag = -1;
	int i = 0;
	for (i; i < 4; i++)
	{
		if (Memory_list[i] == -1) //找到第一个空块，并返回其下标
		{
			flag = i; 	
			break;
		}
	}
	return flag;
}

int check_fullBlock() //找到模拟内存中第一个空闲块的下标并返回 未找到则返回-1表示内存已全被使用
{
	int flag = -1;
	int i = 0;
	for (i; i < Mnum; i++)
	{
		if (Memory_uesd[i] == 0)
		{
			flag = i;
			break;
		}
	}
	return flag;
}

void FIFO(int page) //先进先出页面置换算法 传入参数为本次置换页面
{
	int i = 1;
	before_page = Memory_list[0];//保存被置换页号
	for (i = 1; i < 4; i++)
	{
		Memory_list[i - 1] = Memory_list[i];  //向前位移一位
	}
	Memory_list[3] = page; //插入新页
	//更新页表	
	page_table[page].memoryBlock = page_table[before_page].memoryBlock;
	page_table[page].flag = 1;
	page_table[before_page].memoryBlock = -1;//置为-1表示该页不存在对应主存块号
	page_table[before_page].flag = 0;//表示未装入
}

void operation_change(int i)  //将某些操作转换成中文打印  i为指令集内指令序号
{
	if (Order_table[i].operation == 'C')
	{
		printf("【提示】操作为:存\n"); //模拟操作
	}
	else if (Order_table[i].operation == 'Q')
	{
		printf("【提示】操作为:取\n");
	}
	else if (Order_table[i].operation == 'Y')
	{
		printf("【提示】操作为:移位\n");
	}
	else
	{
		printf("【提示】操作为:%c\n", Order_table[i].operation); //模拟操作
	}
}
void Running()  //运行函数
{
	//获取页面请求序列 程序默认采用Order中顺序
	//for循环取指令
	int i=0;
	int flag = 0; //表示第i条指令对应的页号是否装入内存
	int page_in = 0; //表示插入Memory_list的下标
	int block_in = 0; //表示插入Memory_used的下标
	for (i; i < Onum; i++)
	{
		if (check_inMemory(Order_table[i].pageNumber)==1)
		{
			printf("【指令】第%d条指令对应页号命中，形成物理地址:%4d", i+1,page_table[Order_table[i].pageNumber].memoryBlock*128+ Order_table[i].offset);//页表长为7，2^7=128		
			operation_change(i);
		}
		if (check_inMemory(Order_table[i].pageNumber) == -1)
		{				
			printf("\n[-----------------【页面中断程序】---------------]\n");
			printf("【指令】第%d条指令执行产生缺页中断，中断页号为：%d\n", i+1, Order_table[i].pageNumber); //发生缺页中断
			//page_table[Order_table[i].pageNumber].flag = 1;//将其调入主存，flag置为1
			//判断内存是否已满
			if (check_fullBlock() == -1) //内存全使用,没有空闲块 调用FIFO算法
			{			
				FIFO(Order_table[i].pageNumber);//执行FIFO算法
				printf("【提示】已进行页面置换,置换出的页号为：%d,装入的页号为：%d\n", before_page, Order_table[i].pageNumber);
				printf("【提示】此时装入内存中的页为:\n");
				show_Memory_list(); //打印
			}
			else//内存未完全使用，选择空闲块将页装入
			{
				page_in = check_fullList(); //block不为-1 list也不可能为-1
				Memory_list[page_in] = Order_table[i].pageNumber; //页号插入list表
				block_in = check_fullBlock(); //返回块号 一定不为-1
				//插入后更新页表数据
				page_table[Order_table[i].pageNumber].flag = 1;
				page_table[Order_table[i].pageNumber].memoryBlock = block_in;				
				printf("【提示】已将中断页装入内存,装入的页号为：%d\n", Order_table[i].pageNumber);
				printf("此时装入内存中的页为:\n");
				show_Memory_list(); //打印
			}
			//操作完成，现在已不缺页，可形成物理地址
			printf("【提示】中断执行后对应的物理地址为:%d", page_table[Order_table[i].pageNumber].memoryBlock * 128 + Order_table[i].offset);
			operation_change(i);
			printf("[-----------------【页面中断程序】---------------]\n");
		}
	}
}
void main()
{
	Order_init();//指令集初始化
	initial(); //作业初始化
	show_page_table();	//打印初始页表
	Running(); //运行函数
	system("pause");
}