文档章节

先进先出(FIFO)置换算法

自由的角马
 自由的角马
发布于 2015/01/10 14:00
字数 618
阅读 99
收藏 0

定义

       这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,比如,含有全局变量、常用函数、例程等的页面,FIFO 算法并不能保证这些页面不被淘汰。

这里,我们只需要设置一个先进先出队列就可以。最先进入内存的页面最早被转换出去。

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

       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        
0        1        2        
1        2        0        
2        0        3        
2        3        0        
3        0        4        
0        4        2        
4        2        3        
2        3        0        
2        0        3        
0        3        2        
3        2        1        
3        1        2        
1        2        0        
2        0        1        
0        1        7        
1        7        0        
7        0        1        

先进先出(FIFO)置换算法模拟源代码

/**
 * 先进先出转换算法
 * @author Administrator
 *
 */
public class FIFO {
	/**
	 * 内存块的个数
	 */
	public static final int N = 3;
	/**
	 * 内存块数组
	 */
	Object[] array = new Object[N];
	private int size;
	/**
	 * 内存是非空为否
	 * @return
	 */
	public boolean isEmpty() {
		if(0 == size)
			return true;
		else
			return false;
	}
	
	public/**
	 * 内存是非空满
	 * @return
	 */ boolean isFulled() {
		if(size >= N) 
			return true;
		else 
			return false;
	}
	/**
	 * 元素(页框)的个数
	 * @return
	 */
	public int size() {
		return size;
	}
	/**
	 * 查找元素o在数组中的位置
	 * @param o
	 * @return
	 */
	public int indexOfElement(Object o) {
		for(int i=0; i<N; i++) { 
			if(o == array[i]) {
				return i;
			}
		}
		return -1;
	}	
	/*public void push(Object o) {
		Node p = new Node(o);
		//Node p2 = head;
		p.next = head;	
		head = p;
	}*/
	/**
	 * 页面转换
	 * @param obj
	 */
	public Object trans(Object obj){
		Object e = null;
		int t = 0;
		if(indexOfElement(obj) != -1) {
			t = indexOfElement(obj);
			for(int i=t; i<size-1; i++) {
				array[i] = array[i+1];
			}
			array[size-1] = obj;
		} else {
			if(!isFulled()){
				array[size] = obj;
				size ++;
			} else {
				for(int i=0; i<size-1; i++) {
					array[i] = array[i+1];
				}
				array[size-1] = obj;
			}
		}
		if( -1 == t) {
			return null;
		} else {
			return array[t];
		}
	}
	/**
	 * 输出内存区中的各数据
	 */
	public void showMemoryBlock() {
		for(int i=0; i<size; i++) {
			System.out.print(array[i] + "        ");
		}
	}
	
	/**
	 * 清空队列(页框)
	 */
	public void clear(){
		
	}
	/**
	 * @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};
		FIFO fifo = new FIFO();
		for(int i=0; i<iter.length; i++) {
			fifo.trans(iter[i]);
			fifo.showMemoryBlock();
			System.out.println();
		}
	}

}



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

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
缺页中断与页面置换算法

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

fx677588
2017/09/09
0
0
用LocalStorage实现一个LFU存储系统

前言 原文连接:github.com/qiu... 🤔Emm...好像没什么好说的,先厚着脸皮求个Star👉 LFUStorage吧! 什么是LFU LFU(least frequently used),是操作系统中虚拟页式存储管理的页面置换算...

_安歌
04/22
0
0
页面置换算 - FIFO、LFU、LRU

缓存算法(页面置换算法)-FIFO、LFU、LRU   在前一篇文章中通过leetcode的一道题目了解了LRU算法的具体设计思路,下面继续来探讨一下另外两种常见的Cache算法:FIFO、LFU 1.FIFO算法   ...

孟宇
2015/12/17
0
0
操作系统页面置换算法(opt,lru,fifo,clock)实现

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

余二五
2017/11/07
0
0
android开发常用的缓存策略详解(2)- 先进先出(FIFO)置换算法

那么什么是FIFO算法呢? 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面,按先后...

qq_35703234
2017/12/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

为什么要在网站中应用CDN加速?

1. 网页加载速度更快 在网站中使用CDN技术最直接的一个好处就是它可以加快网页的加载速度。首先,CDN加速的内容分发是基于服务器缓存的,由于CDN中缓存了不少数据,它能够给用户提供更快的页...

云漫网络Ruan
35分钟前
7
0
亚玛芬体育(Amer Sports)和信必优正式启动合作开发Movesense创新

亚玛芬体育和信必优正式启动合作开发Movesense创新,作为亚玛芬体育的完美技术搭档,信必优利用Movesense传感器技术为第三方开发移动应用和服务。 Movesense基于传感器技术和开放的API,测量...

symbiochina88
46分钟前
4
0
创龙TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA核心板规格书

SOM-TL437xF是一款广州创龙基于TI AM437x ARM Cortex-A9 + Xilinx Spartan-6 FPGA芯片设计的核心板,采用沉金无铅工艺的10层板设计,适用于高速数据采集和处理系统、汽车导航、工业自动化等领...

Tronlong创龙
46分钟前
4
0
好程序员Java学习路线分享MyBatis之线程优化

  好程序员Java学习路线分享MyBatis之线程优化,我们的项目存在大量用户同时访问的情况,那么就会出现大量线程并发访问数据库,这样会带来线程同步问题,本章我们将讨论MyBatis的线程同步问...

好程序员官方
52分钟前
6
0
IDEA 自定义方法注解模板

IDEA 自定义方法注解模板 1、使用效果 /*** 计算交易费用* @Author wangjiafang* @Date 2019/9/11* @param feeComputeVo* @return*/@PostMapping("/v1/fee_compute")public ApiResp......

小白的成长
52分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部