页面置换算法之最佳置换算法的模拟(C++)

这篇具有很好参考价值的文章主要介绍了页面置换算法之最佳置换算法的模拟(C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

实验要求

1)设计模拟实现OPT、FIFO和LRU页面置换算法中的任意一种。

OPT算法:需要发生页面置换时,算法总是选择在将来最不可能访问的页面进行置换。

FIFO算法:算法总是选择在队列中等待时间最长的页面进行置换。

LRU算法:如果某一个页面被访问了,它很可能还要被访问;相反,如果它长时间不被访问,那么,在最近未来是不大可能被访问的。

2)完成算法代码。

3)运行程序,算出结果。

设计思路

  模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时使用OPT算法进行页面置换的情形。其中内存页面大小可手动输入进行设置,虚页的个数可以事先给定(例如10个),对这些虚页访问的页地址流(其长度可以事先给定,例如20次虚页访问)可以由程序随机产生,也可以手动输入。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。

实验结果与分析:

 最佳置换算法:一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,那么如果发生缺页中断时,就将该页面换出,以便存放后面调入内存中的页面。
程序进入时可通过程序设定物理块大小
接着输入虚页长度,即程序运行时页面号引用串长度

程序有两种页地址流产生方式,分别为系统随机产生和手动输入

最后输出总的命中次数和命中率

页面置换算法之最佳置换算法的模拟(C++)

 页面置换算法之最佳置换算法的模拟(C++)

 页面置换算法之最佳置换算法的模拟(C++)文章来源地址https://www.toymoban.com/news/detail-465299.html

源程序  

#include<iostream>
#include<cstring>
 
using namespace std;

const int N = 1e3 + 10;
int h[N], data[N], temp[N];//分配的物理块  虚页流 存储该页面未来要被访问的时间 
int n, m;//物理块大小  虚页的长度
double sum;//总命中次数 

void init()
{
	cout << "最佳置换算法OPT 请输入物理块大小" << endl;
	cin >> n;
	cout << "请输入虚页长度" << endl;
	cin >> m; 
	cout << "请选择页地址流产生方式\n1.系统随机生成,2.手动输入" << endl;
	int op;
	cin >> op;
	if(op == 1)//随机生成 
	{
		for(int i = 1; i <= m; i ++) 
		{
			data[i] = ( rand() % (9 - 1 + 1 ) ) + 1;//产生[1,9]的随机数 
			cout << data[i] << ' ';	
		}
		cout << endl;
	}  	
	else if(op == 2)//手动输入 
	{
		for(int i = 1; i <= m; i ++) cin >> data[i];
	}
	
	cout << "当前到达页号  ";
	for(int i = 1; i <= n; i ++)
		cout << "物理块 " << i << "  ";
	cout << "       是否产生缺页" << endl; 
} 

void show(int k, bool flag)//当前虚页块位号 是否产生缺页 
{
	cout << data[k] << "           ";
	for(int i = 1; i <= n; i ++)
	{
		if(h[i] == 0) cout << "空           ";
		else cout << h[i] << "           ";	
	} 
	
	if(flag) cout << "未产生缺页";
	else cout << "产生缺页"; 
	
	cout << "\n----------------------------------------------------------------" << endl;
}

int main()
{
	init();//初始化
	
	for(int i = 1; i <= m; i ++)//对虚页流进行处理 
	{
		bool flag = false;//当前内存中是否有该页面 
		
		int j = data[i];//该页面下标
		
		for(int k = 1; k <= n; k ++)//遍历物理块
			if(h[k] == j)//当前内存中有该页面 
			{
				flag = true;
				//cout << "here" << endl;
				sum ++;//命中次数加1 
				break;	
			} 
			
		bool temp_flag = flag;//保存标志位
		 
		if(!flag)//当前内存中无该页面,需调用页面置换算法(先检查有无空白物理块)
		{
			for(int k = 1; k <= n; k ++)
				if(h[k] == 0)//当前有空白物理块,将该页面置于此处 
				{
					h[k] = j;
					//cout << "here" << endl;
					flag = true;//此时flag代表该页面放入内存没 
					break;
				}
		}
		
		if(!flag)//无空白物理块, 采用OPT算法 
		{
			memset(temp, 0x3f, sizeof temp);//temp用来存放下一次被访问的位置,默认为0x3f代表未来不被访问
			
			for(int q = 1; q <= n; q ++)//遍历物理块 
				for(int k = i + 1; k <= m; k ++)//遍历后续页面流
					if(data[k] == j)//找到下一次被访问的位置 
					{
						temp[q] = k; 
						break;	
					} 
			
			int max = temp[1], t = 1;//最大访问位置,及其下标 
			for(int k = 2; k <= n; k ++)//遍历物理块,找到最晚被访问的页面
				if(temp[k] > max)
				{
					t = k;
					max = temp[k];
				} 
				
			h[t] = j;//将该页面置换进入 
			
		}
		
		show(i, temp_flag);//打印输出数据 		
	}
	cout << "命中次数为 " << sum << " 虚页流长度 " << m << " 命中率为 " << sum / m;
	
	return 0;
}
 

到了这里,关于页面置换算法之最佳置换算法的模拟(C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 操作系统实验:页面置换算法——FIFO、LRU 代码实现

            最简单的页面置换算法是FIFO。 在分配内存页面数( AP )小于进程页面数( PP )时,最先运行的 AP个页面放入内存;当内存分配页面被占满时,如果 又需要处理新的页面,则将原来放的内存中的AP个页中 最先进入 的调出(FIFO),再将新页面放入;所使用的内存

    2024年02月08日
    浏览(33)
  • 操作系统-请求页式存储管理中常用页面置换算法模拟

    (1)先进先出调度算法(FIFO) 先进先出调度算法根据页面进入内存的时间先后选择淘汰页面,先进入内存的页面先淘汰,后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列,每次调度队首页面予以淘汰。 (2)最近最少调度算法(LRU) 先进

    2024年02月06日
    浏览(45)
  • 南京邮电大学算法与设计实验二:贪心算法(最全最新,与题目要求一致)

    三、实验原理及内容 实验原理: 1 、用贪心法实现求两序列的一般背包问题。要求掌握贪心法思想在实际中的应用,分析一般背包的问题特征,选择算法策略并设计具体算法,编程实现贪心选择策略的比较,并输出最优解和最优解值。 2 、用贪心法求解带时限的 ( 单位时间

    2024年02月05日
    浏览(46)
  • 南京邮电大学算法与设计实验四:回溯法(最全最新,与题目要求一致)

    要求用回溯法求解8-皇后问题,使放置在8*8棋盘上的8个皇后彼此不受攻击,即:任何两个皇后都不在同一行、同一列或同一斜线上。请输出8皇后问题的所有可行解。 用回溯法编写一个递归程序解决如下装载问题:有n个集装箱要装上2艘载重分别为c1和c2的轮船,其中集装箱i的

    2024年02月05日
    浏览(54)
  • 南京邮电大学算法与设计实验一:分治策略(最全最新,与题目要求一致)

    实验原理: 1、用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理,编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。 2、采用基于“五元中值组取中值分割法”(median-of-median-of-five partitioning)的线性时

    2024年04月17日
    浏览(103)
  • 虚拟内存页面置换算法(操作系统)

    通过这次实验,加深对虚拟内存页面置换概念的理解,进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。 问题描述: 设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物

    2024年02月04日
    浏览(51)
  • 计算机操作系统——页面置换算法

    声明 :本篇博客参考书籍《计算机操作系统》(西安电子科技大学出版社) 首先说说影响页面换进换出的效率的几个因素: (1)页面置换算法。该因素是影响页面换进换出效率的重要因素。一个好的页面置换算法可以使进程在运行过程中具有较低的缺页率,从而减少页面换

    2024年02月07日
    浏览(65)
  • LRU页面置换算法(C语言实现)

    1 、实验目的 ( 1 )熟悉虚拟存储器页面置换过程; ( 2 )通过编写和调试页面置换算法的模拟程序以加深对页面置换算法的理解; ( 3 )掌握 LRU 算法的原理; ( 4 )熟悉 OPT 和 FIFO 页面置换算法原理。 2 、 实验要求        编写并调试一个页面置换模拟程序,采用 LR

    2024年02月11日
    浏览(31)
  • 操作系统常见的十种页面置换算法

    OS常见页面置换算法整理 在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页

    2024年02月02日
    浏览(47)
  • 【操作系统】抖动、缺页中断率、页面置换算法

    对于进程P的一个长度为A的页面访问序列,如果进程P在运行中发生缺页中断的次数为F,则f = F/A称为缺页中断率。 1、进程分得的主存页框数:页框数多则缺页中断率低,页框数少则缺页中断率高。 2、页面大小:页面大则缺页中断率低,页面小则缺页中断率高。 3、页面替换

    2024年01月20日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包