文档章节

最佳(Optimal)置换算法模拟

自由的角马
 自由的角马
发布于 2015/01/10 13:59
字数 946
阅读 32
收藏 0

定义

       最佳(Optimal)置换算法是指,其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用该算法去评价其它算法。

算法过程

       现举例说明如下。

       假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串:

       7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

       进程运行时,先将7,0,1 三个页面装入内存。以后,当进程要访问页面2 时,将会产生缺页中断。此时OS根据最佳置换算法,将选择页面7 予以淘汰。这是因为页面0 将作为第5 个被访问的页面,页面1 是第14 个被访问的页面,而页面7 则要在第18 次页面访问时才需调入。下次访问页面0时,因它已在内存而不必产生缺页中断。当进程访问页面3时,又将引起页面1 被淘汰;因为,它在现有的1,2,0 三个页面中,将是以后最晚才被访问的。下图所示出了采用最佳置换算法时的置换图。由图可看出,采用最佳置换算法发生了6 次页面置换。


利用最佳页面置换算法时的置换图


最佳(Optimal)置换算法模拟源代码

package pageturning;

import java.util.ArrayList;
import java.util.List;


public class Optimal {
	/**
	 * 内存块的个数
	 */
	public static final int N = 3;
	/**
	 * 内存块数组
	 */
	private Object[] array = new Object[N];
	//内存块中元素的个数
	private int size;
	//元素i未来longest[i]个单位时间后将被使用
	private int[] longest = new int[N];
		
	//private Object[] procList;
	public Optimal() {
	}
	/**
	 * 判断内存区是否为空
	 * @return
	 */
	public boolean isEmpty() {
		if(size == 0) {
			return true;
		} else {
			return false;
		}
	}
	/**
	 * 判断内存区是否达到最大值
	 * @return
	 */
	public boolean isOutOfBoundary() {
		if(size >=N) {
			return true;
		} else {
			return false;
		}
	}
	/**
	 * 查找元素o在数组中的位置
	 * @param o
	 * @return
	 */
	public int indexOfElement(Object o) {
		for(int i=0; i<N; i++) { 
			if(o == array[i]) {
				return i;
			}
		}
		return -1;
	}	
	/**
	 * 找出未来最久的时间会被调用的元素的序号
	 * @param k 开始调用时的下标
	 * @param procList 整个进程对列的调用过程
	 * @return
	 */
	private int findTransIndex(final int k, final Object[] procList) {
		int transIndex = 0;
		int longest2 = 0;
		for(int j=0; j<size; j++) {
			longest[j] = Integer.MAX_VALUE;
		}
		for(int i=k+1; i<procList.length; i++) {
			for(int j=0; j<size; j++) {				
				if(procList[i] ==  array[j]) {
					if(longest[j] == Integer.MAX_VALUE) {
						longest[j] = i;
						if(longest2 < longest[j])
							transIndex = j;
					}
				} 
			}
		}
		for(int j=0; j<size; j++) {
			if(longest[j] == Integer.MAX_VALUE) {
				transIndex = j;
				break;
			}
		}
		return transIndex;
	}
	/**
	 * 有新的数据o需要申请内存
	 * @return 移出内存区的数据
	 */
	public Object push(Object[] procList, int k) {
		int t = -1; 
		if(!isOutOfBoundary() && indexOfElement(procList[k]) == -1){
			array[size] = procList[k];
			size ++;
		} else if(!isOutOfBoundary() && indexOfElement(procList[k]) != -1) { 
			t = indexOfElement(procList[k]);
		} else if(isOutOfBoundary() && indexOfElement(procList[k]) == -1){
			int transIndex = findTransIndex(k, procList);
			array[transIndex] = procList[k];
			t = transIndex;
		} else if(isOutOfBoundary() && indexOfElement(procList[k]) != -1){
			
		} 
		if( -1 == t) {
			return null;
		} else {
			return array[t];
		}
	}
	/**
	 * 输出内存区中的各数据
	 */
	public void showMemoryBlock() {
		for(int i=0; i<size; i++) {
			System.out.print(array[i] + "        ");
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer iter[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
		Optimal optimal = new Optimal();
		for(int i=0; i<iter.length; i++) {
			optimal.push(iter, i);
			optimal.showMemoryBlock();
			System.out.println();
		}
	}

}
输入 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1时,结果如下:
7        
7        0        
7        0        1        
2        0        1        
2        0        1        
2        0        3        
2        0        3        
2        4        3        
2        4        3        
2        4        3        
2        0        3        
2        0        3        
2        0        3        
2        0        1        
2        0        1        
2        0        1        
2        0        1        
7        0        1        
7        0        1        
7        0        1        

本文转载自:http://blog.csdn.net/luoweifu/article/details/8498027

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
操作系统页面置换算法(opt,lru,fifo,clock)实现

选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。 常见的置换算法有以下四种(以...

余二五
2017/11/07
0
0
缺页中断与页面置换算法

1 缺页中断:   进程线性地址空间里的页面不必常驻内存,在执行一条指令时,如果发现他要访问的页没有在内存中(存在位为0),那么停止该指令的执行,并产生一个页不存在异常,对应的故障处...

fx677588
2017/09/09
0
0
深入理解【缺页中断】及FIFO、LRU、OPT这三种置换算法

虚拟地址空间中,但是目前并未被加载在物理内存中的一个分页时,由中央处理器的内存管理单元所发出的中断。 操作系统的一部分。如果操作系统判断此次访问是有效的,那么操作系统会尝试将相关...

sunsky303
2018/06/22
0
0
内存管理(二)

一、虚拟存储技术 所谓虚拟存储技术是指:当进程运行时,先将其一部分装入内存,另一部分暂留在磁盘,当要执行的指令或访问的数据不在内存时,由操作系统自动完成将它们从磁盘调入内存的工作...

芥末无疆sss
2017/12/30
0
0
数据结构与算法 试题2.7 - 生成前N个自然数的一个随机置换

数据结构与算法 2.7 习题2.7 假设需要生成前N个自然数的一个随机置换。例如,{3,4,1,5,2}和{5,2,3,1,4}就是合法的置换,但{5,4,1,2,1}却不是,因为数1出现了两次而数3却没有。这个程序常用语...

邪恶的小Y
2016/06/07
225
0

没有更多内容

加载失败,请刷新页面

加载更多

【jQuery基础学习】05 jQuery与Ajax以及序列化

本文转载于:专业的前端网站➭【jQuery基础学习】05 jQuery与Ajax以及序列化 好吧,这章不像上章那么水了,总是炒剩饭也不好。 关于AJAX 所谓Ajax,全名Asynchronous JavaScript and XML。(也...

前端老手
22分钟前
9
0
CVE-2019-14287(Linux sudo 漏洞)分析

作者:lu4nx@知道创宇404积极防御实验室 作者博客:《CVE-2019-14287(Linux sudo 漏洞)分析》 原文链接:https://paper.seebug.org/1057/ 近日 sudo 被爆光一个漏洞,非授权的特权用户可以...

极客君
23分钟前
6
0
关于分布式,你需要知道的真相

目录 一、分布式锁 数据库的唯一索引 Redis 的 SETNX 指令 Redis 的 RedLock 算法 Zookeeper 的有序节点 二、分布式事务 2PC 本地消息表 三、CAP 一致性 可用性 分区容忍性 权衡 四、BASE 基...

李红欧巴
23分钟前
7
0
读书笔记:深入理解ES6 (附录B)

附录B:了解ES7(2016)   ES6经历了4年的发展,之后TC-39决定将发布周期转换为每年一版,以确保新语言特性能够更快地发展。   ES6中添加了三个语法特性,下面一一来讲。 第1节 指数运算...

张森ZS
29分钟前
13
0
计算机公开课推荐 2019.8

欢迎任何人参与和完善:一个人可以走的很快,但是一群人却可以走的更远。 ApacheCN 面试求职交流群 724187166 ApacheCN 学习资源 编程 哈佛 CS50:计算机科学导论 视频 MIT 6.00.1x:计算机科...

ApacheCN_飞龙
29分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部