使用java.util.LinkedList模拟实现内存页面置换算法--LRU算法-阿里云开发者社区

开发者社区> 技术mix呢> 正文

使用java.util.LinkedList模拟实现内存页面置换算法--LRU算法

简介:
+关注继续查看

一,LRU算法介绍

LRU是内存分配中“离散分配方式”之分页存储管理方式中用到的一个算法。每个进程都有自己的页表,进程只将自己的一部分页面加载到内存的物理块中,当进程在运行过程中,发现某页面不在物理内存块中(发生缺页异常)就需要从磁盘把相应的页面调入内存。而若内存已经满了的情况下,需要将内存中暂时不用的物理块页面 换出到磁盘(交换空间)中,那到底换出哪一页呢?LRU算法就是用来解决到底换出哪一页 的这个问题。

LRU算法是最近最少未使用算法。当内存缺页时,总是优先选出距离当前最久未使用的页面换出,并把当前的缺页换入。该算法可用栈模拟实现。

栈顶总是保存当前最近访问的页面号,栈底则总是保存最久未访问的页面号。对于下一个页面,有两种情况:

①命中,则需要:更新栈顶元素。即将当前命中的页面号放到栈顶。

②未命中,这里还需要考虑栈是否满了。1)若栈未满,直接将未命中的页面号放到栈顶即可。为什么要放到栈顶(LinkedList表头)呢?

因为,LRU每次总是选取最近最久未被访问的页面淘汰。某页面刚刚被访问,需要放到栈顶,以表示它不是“最近最久 未访问的页面”

2)栈已经满了,则需要选中一页换出(栈底元素是最久未访问的页面),然后再将新页面放入栈顶

 

二,代码实现

复制代码
import java.util.LinkedList;

public class LRU {

    private LinkedList<Integer> stack;//模拟页面'寄存器'
    private int size;//寄存器大小,表示一共可装入多少页面
    
    public LRU(int size) {
        stack = new LinkedList<>();
        this.size = size;
    }

    //LRU算法简单实现,返回一共未命中的次数
    public int lru(int[] pageNumbers)
    {
        if(size <= 0 || pageNumbers == null)
            throw new IllegalArgumentException("illegal arugments");
        
        if(pageNumbers.length <= size)
            return pageNumbers.length;
        
        int unhit = 0;
            
        for(int i = 0; i < pageNumbers.length; i++)
        {
            int index = isHit(pageNumbers[i]);
            if(index == -1)
                unhit = processUnHit(pageNumbers[i], unhit);
            else
            {
                processHit(pageNumbers[i], index);
            }
        }
        return unhit;
    }
    
    /**
     * 
     * @param pageNumber 判断 pageNumber是否hit
     * @return -1 表示 unhit, 其他表示hit
     */
    private int isHit(int pageNumber){
        return stack.indexOf(pageNumber);
    }
    
    /**
     * 当栈未满时,未命中的页面号直接入栈;栈满时,需要替换页面,先选中一个页面(栈底)删除,然后Push新页面
     * @param pageNumber 未命中的页面号
     * @param count 当前未命中次数
     * @return 更新后的未命中的次数
     */
    private int processUnHit(int pageNumber, int count){
        if(isFull())
            stack.removeLast();//删除最久未访问的页面
        stack.push(pageNumber);//放入最近访问的页面
        count++;//未命中的次数加1
        return count;
    }
    
    //处理命中的情况
    private void processHit(int pageNumber, int index){
            stack.push(stack.remove(index));
    }
    
    //判断'寄存器'栈是否已经满了
    private boolean isFull()
    {
        if(stack.size() < size)
            return false;
        else
            return true;
    }
    
    //test
    public static void main(String[] args) {
        int[] pageNumbers = {4,7,1,1,7,2,1};
        int size = 2;
        LRU lru = new LRU(size);
        System.out.println(lru.lru(pageNumbers));
    }
}
复制代码

 

三,复杂度分析

由于java.util.LinkedList 实现了栈的功能。push()方法总是将元素放到表头,pop()方法总是从链表的表头删除元素。在这里,链表的表头代表栈顶。

因此,当某页面号命中时,需要从链表中找到该页面的位置(index),然后删除该页面,并将它push到链表的表头。---processHit()方法

由于是链表,故寻找某页面的时间复杂度为O(N),最坏情况下扫描整个链表。

当页面未命中的,需要将页面号push到链表表头。push之前,先检查栈是否已经满了。若未满,直接push入栈,时间复杂度为O(1);如果栈已经满了,需要删除链表的表尾元素(相当于栈底元素--removeLast()时间复杂度也为O(1),因为LinkedList本质上是一个双向链表。)然后,再将该删除的元素push到栈顶--时间复杂度为O(1)

故未命中时,处理的总的时间复杂度还是O(1)


本文转自hapjin博客园博客,原文链接:http://www.cnblogs.com/hapjin/p/5687768.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
使用LRU算法缓存图片,android 3.0
<p class="edui-filter-align-left" style="color:rgb(54,46,43); font-family:Arial; font-size:14px; line-height:26px"> 在您的UI中显示单个图片是非常简单的,如果您需要一次显示很多图片就有点复杂了。在很多情况下<br> (例如使用 ListView, GridView 或者 
1636 0
Java反转IC卡16进制物理卡号算法
IC卡的物理卡号一般由16进制的字符组成,日常常见的有直读卡号和反转后的卡号,本文用一个简单的算法获取反转后的卡号。
52 0
通过Android逆向之签名算法分析看apk安全防护
android安全问题日益验证,作为一名移动安全渗透人员,有时需要对移动apk进行全面的渗透测试,而不能仅仅局限于apk本身,此时往往就需要结合静态分析和动态分析进行。
1604 0
凑单算法——基于Graph Embedding的bundle mining
本文描述如何在凑单场景突破找相似、发现惊喜的同时做到成交翻倍,实现体验和数据上的双赢。
13543 0
[Android]使用自定义JUnit Rules、annotations和Resources进行单元测试(翻译)
以下内容为原创,欢迎转载,转载请注明 来自天天博客:http://www.cnblogs.com/tiantianbyconan/p/5795091.html 使用自定义JUnit Rules、annotations和Resources进行单元测试 原文:http://www.thedroidsonroids.com/blog/android/unit-tests-rules-annotations-resources 简介 Unit Test并不只有断言和测试方法组成。
862 0
+关注
2969
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载