操作系统实验五 存储管理

★观前提示：本篇内容为操作系统实验内容，代码等内容经测试没有问题，但是可能会不符合每个人实验的要求，因此以下内容建议仅做思路参考。

一、实验目的

1. 掌握虚拟内存的管理机制。
2. 了解虚拟存储技术的特点。
3. 掌握请求分页存储管理的页面置换算法。

二、实验内容

设计一个虚拟存储区和内存工作区，并使用以下置换算法计算访问命中率：先进先出页面置换算法、最近最少使用页面置换算法、最佳淘汰页面置换算法等。

1. 通过随机数产生一个指令序列，共320条指令。

2. 将指令序列变换为页地址流。

3. 设计一个虚拟存储区和内存工作区，并使用下列各种算法计算，当分配给作业的内存块数从4——32时，访问的命中率各是多少，并进行比较。

   ①先进先出的算法（FIFO）；
   ②最近最少使用算法（LRR)；
   ③最佳淘汰算法（OPT），先淘汰最不常用的页地址；
   ④最少访问页面算法（LFR）；（选做）
   ⑤最近最不经常使用算法（NUR）。（选做）
   其中①、②和③为必做内容，④和⑤为选做内容。

三、具体实现

1️⃣实验方案的选择
①先进先出的算法（FIFO）；
②最近最少使用算法（LRR)；
③最佳淘汰算法（OPT），先淘汰最不常用的页地址；
④最少访问页面算法（LFR）；
⑤最近最不经常使用算法（NUR）。

本次实验共实现以上五种页面置换算法，查询了书籍和相关资料之后，理解了几个算法的含义、以及它们的特点，
另外在老师所发文件源码的基础上，借助C++语言对以上五种算法进行了实现。详细步骤如下：

①创建test5.cpp文件

②编程如下

#include<iostream>
#include<ctime>
#include<random>

using namespace std;

#define TRUE 1
#define FALSE 0
#define INVALID -1
//#define NULL 0

#define total_instruction 320 //指令数量
#define total_vp 32 //页表数量
#define clear_period 50 //清0周期

struct pl_type { /*页表结构*/
	int pn, pfn, counter, time;
};
pl_type pl[total_vp]; //页表数组

struct pfc_type { /*内存表结构*/
	int pn, pfn;
	pfc_type* next;
};
pfc_type pfc[total_vp], * freepf_head, * busypf_head, * busypf_tail;

int diseffect; // 未命中次数
int a[total_instruction]; // 存储320条指令
int page[total_instruction]; // 每条指令对应的页表号
int offset[total_instruction];

int initialize(int);
int FIFO(int);
int LRU(int);
int NUR(int);
int LFU(int);
int OPT(int);

int main() {
	int s;
	srand(unsigned(time(0)));
	for (int i = 0; i < total_instruction; i += 4) { /*产生指令队列*/
		s = rand() % 320;
		a[i] = s + 1; //顺序执行一条指令
		a[i + 1] = rand() % (a[i] + 1); //执行前地址指令m'
		a[i + 2] = a[i + 1] + 1; //顺序执行一条指令
		a[i + 3] = rand() % (319 - a[i + 2]) + (a[i + 2] + 1); // 执行后地址指令

		if (a[i] > 319 || a[i + 1] > 319 || a[i + 2] > 319 || a[i + 3] > 319) {
			i -= 4;
		}
	}
	for (int i = 0; i < total_instruction; i++) { /*将指令序列变换成页表地址流*/
		page[i] = a[i] / 10;
		offset[i] = a[i] % 10;
	}
	for (int i = 4; i <= 32; i++) { /*用户内存工作区从4个页面到32个页面*/
		printf("---%2d page frames---\n", i);
		FIFO(i);
		LRU(i);
		NUR(i);
		LFU(i);
		OPT(i);
	}
	return 0;
}

int initialize(int total_pf) { /*初始化相关数据结构*/
	diseffect = 0;
	// 初始化页表
	for (int i = 0; i < total_vp; i++) {
		pl[i].pn = i;
		pl[i].pfn = INVALID; // 初始，该页不在内存中
		pl[i].counter = 0; // 访问次数或作为引用位
		pl[i].time = -1; // 时间
	}
	// 初始内存表,建立pfc[i-1]和pfc[i]之间的链接
	for (int i = 0; i < total_pf - 1; i++) {
		pfc[i].next = &pfc[i + 1];
		pfc[i].pfn = i;
	}
	pfc[total_pf - 1].next = NULL;
	pfc[total_pf - 1].pfn = total_pf - 1;
	freepf_head = &pfc[0]; //内存空页面队列的头指针为pfc[0]

	return 0;
}

int FIFO(int total_pf) { /*先进先出算法*/
	pfc_type* p;
	initialize(total_pf); //初始化相关页面控制用数据结构
	busypf_head = busypf_tail = NULL; //内存页的队列头，队列尾指针接
	for (int i = 0; i < total_instruction; i++) {
		if (pl[page[i]].pfn == INVALID) { //页表项不在内存中
			diseffect += 1; //失效次数
			if (freepf_head == NULL) { //内存无空闲页面
				p = busypf_head->next;
				pl[busypf_head->pn].pfn = INVALID;
				freepf_head = busypf_head; //释放忙页面队列的第一个页面
				freepf_head->next = NULL;
				busypf_head = p;
			}
			// 按FIFO方式调新页面入内存页面
			p = freepf_head->next; // 先保存内存表中当前位置的下一位置
			freepf_head->next = NULL;
			freepf_head->pn = page[i]; // 页表号
			pl[page[i]].pfn = freepf_head->pfn; // 内存块号

			if (busypf_tail == NULL) {
				// busypf_head指向最老的，busypf_tail指向最新的
				busypf_head = busypf_tail = freepf_head;
			}
			else {
				busypf_tail->next = freepf_head; //free页面减少一个
				busypf_tail = freepf_head;
			}
			freepf_head = p;
		}
	}
	printf("FIFO:%6.4f\n", 1 - diseffect / 320.0);

	return 0;
}

int LRU(int total_pf) { /*最近最久未使用算法（使用时钟计数器）*/
	int min, minj, present_time;
	initialize(total_pf);
	present_time = 0;
	for (int i = 0; i < total_instruction; i++) {
		if (pl[page[i]].pfn == INVALID) { //页面失效，不在内存中
			diseffect++;
			if (freepf_head == NULL) { //内存无空闲页面
				min = 32767;
				for (int j = 0; j < total_vp; j++) { //找出内存块中time的最小值
					if (min > pl[j].time && pl[j].pfn != INVALID) // 查询页表
					{
						min = pl[j].time;
						minj = j; // 记下内存块号
					}
				}
				freepf_head = &pfc[pl[minj].pfn]; //腾出一个单元（对应的内存块）
				pl[minj].pfn = INVALID;
				pl[minj].time = -1;
				freepf_head->next = NULL;
			}
			pl[page[i]].pfn = freepf_head->pfn; //有空闲页面,改为有效（内存块号）
			pl[page[i]].time = present_time;
			freepf_head = freepf_head->next; //减少一个free 页面
		}
		else {
			pl[page[i]].time = present_time; //命中则设置时间
		}
		present_time++;
	}
	printf("LRU:%6.4f\n", 1 - diseffect / 320.0);
	return 0;
}

int NUR(int total_pf) { /*最近未使用算法（每执行50条指令引用位清零一次）*/
	int dp, cont_flag, old_dp;
	initialize(total_pf);
	dp = 0;
	for (int i = 0; i < total_instruction; i++) {
		if (pl[page[i]].pfn == INVALID) { //页面失效，不在内存中
			diseffect++;
			if (freepf_head == NULL) { //无空闲页面
				cont_flag = TRUE;
				old_dp = dp;
				while (cont_flag) {
					// 查页表（对应引用位0，在内存中）
					if (pl[dp].counter == 0 && pl[dp].pfn != INVALID) {
						cont_flag = FALSE;
					}
					else {
						dp++;
						if (dp == total_vp) {
							dp = 0;
						}
						if (dp == old_dp) {
							// 第2轮扫描结束，失败（引用位全部置为0）
							for (int j = 0; j < total_vp; j++) {
								pl[j].counter = 0;
							}
						}
					}
				}
				freepf_head = &pfc[pl[dp].pfn]; //腾出一个单元（对应的内存块）
				pl[dp].pfn = INVALID;
				freepf_head->next = NULL;
			}
			pl[page[i]].pfn = freepf_head->pfn;
			freepf_head = freepf_head->next;
		}
		else {
			pl[page[i]].counter = 1; // 在内存中，“引用位”置为1
		}
		// 每执行50条指令，引用位清零一次
		if (i % clear_period == 0) {
			for (int j = 0; j < total_vp; j++) {
				pl[j].counter = 0;
			}
		}
	}
	printf("NUR:%6.4f\n", 1 - diseffect / 320.0);

	return 0;
}

int OPT(int total_pf) { /*最佳置换算法*/
	int max, maxpage, d, dist[total_vp];
	initialize(total_pf);
	for (int i = 0; i < total_instruction; i++) {
		if (pl[page[i]].pfn == INVALID) { //页面失效，不在内存中
			diseffect++;
			if (freepf_head == NULL) { //无空闲页面
				for (int j = 0; j < total_vp; j++) {
					if (pl[j].pfn != INVALID) {
						dist[j] = 32767; /* 最大"距离" */
					}
					else {
						dist[j] = 0;
					}
				}
				d = 1;
				for (int j = i + 1; j < total_instruction; j++) {
					if (pl[page[j]].pfn != INVALID && dist[page[j]] == 32767) {
						dist[page[j]] = d;
					}
					d++;
				}
				max = -1;
				for (int j = 0; j < total_vp; j++) {
					if (max < dist[j]) {
						max = dist[j];
						maxpage = j;
					}
				}
				freepf_head = &pfc[pl[maxpage].pfn];
				freepf_head->next = NULL;
				pl[maxpage].pfn = INVALID;
			}
			pl[page[i]].pfn = freepf_head->pfn;
			freepf_head = freepf_head->next;
		}
	}
	printf("OPT:%6.4f\n", 1 - diseffect / 320.0);

	return 0;
}

int LFU(int total_pf) { /*最不经常使用置换法*/
	int i, j, min, minpage;
	initialize(total_pf);
	for (i = 0; i < total_instruction; i++) {
		if (pl[page[i]].pfn == INVALID) { //页面失效，不在内存中
			diseffect++;
			if (freepf_head == NULL) { //无空闲页面
				min = 32767;
				for (j = 0; j < total_vp; j++) {
					if (min > pl[j].counter && pl[j].pfn != INVALID) {
						min = pl[j].counter;
						minpage = j;
					}
					//pl[j].counter = 0;
					//pl[j].counter >>= 1;
				}
				freepf_head = &pfc[pl[minpage].pfn];
				pl[minpage].pfn = INVALID;
				freepf_head->next = NULL;
			}
			pl[page[i]].pfn = freepf_head->pfn; //有空闲页面,改为有效
			pl[page[i]].counter++;
			freepf_head = freepf_head->next; //减少一个free页面
		}
		else {
			pl[page[i]].counter++; // 软件计数器（被访问次数）
		}
		// 定期右移
		if (i % 15 == 0) {
			for (int j = 0; j < total_vp; j++) {
				pl[j].counter >>= 1;
			}
		}
	}
	printf("LFU:%6.4f\n", 1 - diseffect / 320.0);

	return 0;
}

③编程完毕之后，借助"wq"进行保存并退出

④对test5.cpp进行编译

⑤编译完成后，对实验结果进行输出

2️⃣实验分析

在内存页面数较少（4 ~ 5页）时，五种算法的命中率差别不大，都是30%左右。在内存页面为7 ~ 18个页面之间时，5种算法的访内命中率大致在35% ~ 60%之间变化。但是，FIFO算法与OPT算法之间的差别一般在6 ~ 10个百分点左右。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，使命中率增加，从而算法之间的差别不大。比较上述5种算法，以OPT算法的命中率最高，NUR算法次之，再就是LFU算法和LRU算法，其次是FIFO算法。就本问题，在15页之前，FIFO的命中率比LRU的高。

四、实验总结

① 掌握了虚拟内存的管理机制。
②了解虚拟存储技术的特点，可以大大提高存储系统整体访问带宽，为存储资源管理提供了更好的灵活性。
③ 掌握了请求分页存储管理的页面置换算法， FIFO、LRR、OPT等等

2022.9.21记录：Code_流苏(CSDN)
如有任何疑问，评论回复，看到即回，欢迎大家多多交流学习！
★以上实验内容仅供参考。文章来源地址https://www.toymoban.com/news/detail-460601.html

到了这里，关于操作系统实验五 存储管理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！