精华内容
下载资源
问答
  • Java缓存淘汰算法

    千次阅读 2020-12-14 09:50:35
    1、Redis缓存淘汰算法 2、Memcache缓存淘汰算法 3、Ehcache缓存淘汰算法 4、Guava缓存淘汰算法 5、Caffein缓存淘汰算法 1、Redis缓存淘汰算法 2、Memcache缓存淘汰算法 3、Ehcache缓存淘汰算法 4、...

    目录

    1、Redis缓存淘汰算法

    2、Memcache缓存淘汰算法

    3、Ehcache缓存淘汰算法

    4、Guava缓存淘汰算法

     4.1 Eviction by Size

    4.1  Eviction by Weight

    4.3   Eviction by Time

    4.4  Weak Keys

    4.5  Soft Values

    5、Caffein缓存淘汰算法

    5.1 Size-based

    5.1 Time-based

    5.3 Reference-based

    6、LFU淘汰算法的Java实现

    7、LRU淘汰算法的Java实现

    8、FIFO淘汰算法的Java实现


    1、Redis缓存淘汰算法

       摘自Redis原文:https://redis.io/topics/config

           If you plan to use Redis just as a cache where every key will have an expire set, you may consider using the following configuration instead (assuming a max memory limit of 2 megabytes as an example):

    maxmemory 2mb
    maxmemory-policy allkeys-lru
    #面试题 maxmemory-samples是干什么的?
    maxmemory-samples 5

    The following policies are available:  原文点击

    • noeviction: return errors when the memory limit was reached and the client is trying to execute commands that could result in more memory to be used (most write commands, but DEL and a few more exceptions).
    • allkeys-lru: evict keys by trying to remove the less recently used (LRU) keys first, in order to make space for the new data added.
    • volatile-lru: evict keys by trying to remove the less recently used (LRU) keys first, but only among keys that have an expire set, in order to make space for the new data added.
    • allkeys-random: evict keys randomly in order to make space for the new data added.
    • volatile-random: evict keys randomly in order to make space for the new data added, but only evict keys with an expire set.
    • volatile-ttl: evict keys with an expire set, and try to evict keys with a shorter time to live (TTL) first, in order to make space for the new data added.

    Redis4之后新增了两种 allkey-lfuvolatile-lfu 两种策略

    问题1: Redis为什么使用近似LFU算法?
    问题2:如何提高近似LFU算法精度?
    问题3:如何选择适合自己的maxmemory-policy?

    2、Memcache缓存淘汰算法

    https://memcached.org/blog/modern-lru/

    3、Ehcache缓存淘汰算法

            参考文档:参考原文

    <cache name="myCache"
          maxEntriesLocalDisk="10000" eternal="false" timeToIdleSeconds="3600"
          timeToLiveSeconds="0" memoryStoreEvictionPolicy="LFU">
    </cache>

     

    Note the following about the myCache configuration:

    • Accessing an entry in myCache that has been idle for more than an hour (timeToIdleSeconds) causes that element to be evicted.
    • If an entry expires but is not accessed, and no resource constraints force eviction, then the expired entry remains in place.
    • Entries in myCache can remain in the cache forever if accessed at least once per 60 minutes (timeToLiveSeconds). However, unexpired entries may still be flushed based on other limitations (see How to Size Caches).
    • In all, myCache can store a maximum of 10000 entries (maxEntriesLocalDisk). This is the effective maximum number of entries myCache is allowed. Note, however, that this value may be exceeded as it is overridden by settings such as pinning.

    memoryStoreEvictionPolicy支持以下淘汰策略:

    1. LRU - least recently used
    2. LFU - least frequently used
    3. FIFO - first in first out, the oldest element by creation time

    4、Guava缓存淘汰算法

            参考文档:参考原文

     4.1 Eviction by Size

          We can limit the size of our cache using maximumSize(). If the cache reaches the limit, the oldest items will be evicted.

    @Test
    public void whenCacheReachMaxSize_thenEviction() {
        CacheLoader<String, String> loader;
        loader = new CacheLoader<String, String>() {
            @Override
            public String load(String key) {
                return key.toUpperCase();
            }
        };
        LoadingCache<String, String> cache;
        cache = CacheBuilder.newBuilder().maximumSize(3).build(loader);
    
        cache.getUnchecked("first");
        cache.getUnchecked("second");
        cache.getUnchecked("third");
        cache.getUnchecked("forth");
        assertEquals(3, cache.size());
        assertNull(cache.getIfPresent("first"));
        assertEquals("FORTH", cache.getIfPresent("forth"));
    }

     

    4.1  Eviction by Weight

    We can also limit the cache size using a custom weight function. In the following code, we use the length as our custom weight function:

    @Test
    public void whenCacheReachMaxWeight_thenEviction() {
        CacheLoader<String, String> loader;
        loader = new CacheLoader<String, String>() {
            @Override
            public String load(String key) {
                return key.toUpperCase();
            }
        };
    
        Weigher<String, String> weighByLength;
        weighByLength = new Weigher<String, String>() {
            @Override
            public int weigh(String key, String value) {
                return value.length();
            }
        };
    
        LoadingCache<String, String> cache;
        cache = CacheBuilder.newBuilder()
          .maximumWeight(16)
          .weigher(weighByLength)
          .build(loader);
    
        cache.getUnchecked("first");
        cache.getUnchecked("second");
        cache.getUnchecked("third");
        cache.getUnchecked("last");
        assertEquals(3, cache.size());
        assertNull(cache.getIfPresent("first"));
        assertEquals("LAST", cache.getIfPresent("last"));
    }

    Note: The cache may remove more than one record to leave room for a new large one.

    4.3   Eviction by Time

    Beside using size to evict old records, we can use time. In the following example, we customize our cache to remove records that have been idle for 2ms:

    @Test
    public void whenEntryIdle_thenEviction()
      throws InterruptedException {
        CacheLoader<String, String> loader;
        loader = new CacheLoader<String, String>() {
            @Override
            public String load(String key) {
                return key.toUpperCase();
            }
        };
    
        LoadingCache<String, String> cache;
        cache = CacheBuilder.newBuilder()
          .expireAfterAccess(2,TimeUnit.MILLISECONDS)
          .build(loader);
    
        cache.getUnchecked("hello");
        assertEquals(1, cache.size());
    
        cache.getUnchecked("hello");
        Thread.sleep(300);
    
        cache.getUnchecked("test");
        assertEquals(1, cache.size());
        assertNull(cache.getIfPresent("hello"));
    }

    We can also evict records based on their total live time. In the following example, the cache will remove the records after 2ms of being stored:

    @Test
    public void whenEntryLiveTimeExpire_thenEviction()
      throws InterruptedException {
        CacheLoader<String, String> loader;
        loader = new CacheLoader<String, String>() {
            @Override
            public String load(String key) {
                return key.toUpperCase();
            }
        };
    
        LoadingCache<String, String> cache;
        cache = CacheBuilder.newBuilder()
          .expireAfterWrite(2,TimeUnit.MILLISECONDS)
          .build(loader);
    
        cache.getUnchecked("hello");
        assertEquals(1, cache.size());
        Thread.sleep(300);
        cache.getUnchecked("test");
        assertEquals(1, cache.size());
        assertNull(cache.getIfPresent("hello"));
    }

     

    4.4  Weak Keys

             Next, let's see how to make our cache keys have weak references – allowing the garbage collector to collect cache keys that are not referenced elsewhere.
    By default, both cache keys and values have strong references but we can make our cache store the keys using weak references using weakKeys() as in the following example:

    @Test
    public void whenWeakKeyHasNoRef_thenRemoveFromCache() {
        CacheLoader<String, String> loader;
        loader = new CacheLoader<String, String>() {
            @Override
            public String load(String key) {
                return key.toUpperCase();
            }
        };
    
        LoadingCache<String, String> cache;
        cache = CacheBuilder.newBuilder().weakKeys().build(loader);
    }

    4.5  Soft Values

             We can allow the garbage collector to collect our cached values by using softValues() as in the following example:

    @Test
    public void whenSoftValue_thenRemoveFromCache() {
        CacheLoader<String, String> loader;
        loader = new CacheLoader<String, String>() {
            @Override
            public String load(String key) {
                return key.toUpperCase();
            }
        };
    
        LoadingCache<String, String> cache;
        cache = CacheBuilder.newBuilder().softValues().build(loader);
    }
    Note: Many soft references may affect the system performance – it's preferred to use maximumSize().

     

    5、Caffein缓存淘汰算法

          参考文档:参考原文

    Caffeine provides three types of eviction: size-based eviction, time-based eviction, and reference-based eviction.

    5.1 Size-based

    // Evict based on the number of entries in the cache
    LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
        .maximumSize(10_000)
        .build(key -> createExpensiveGraph(key));
    
    // Evict based on the number of vertices in the cache
    LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
        .maximumWeight(10_000)
        .weigher((Key key, Graph graph) -> graph.vertices().size())
        .build(key -> createExpensiveGraph(key));

    5.1 Time-based

    // Evict based on a fixed expiration policy
    LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
        .expireAfterAccess(5, TimeUnit.MINUTES)
        .build(key -> createExpensiveGraph(key));
    LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
        .expireAfterWrite(10, TimeUnit.MINUTES)
        .build(key -> createExpensiveGraph(key));
    
    // Evict based on a varying expiration policy
    LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
        .expireAfter(new Expiry<Key, Graph>() {
          public long expireAfterCreate(Key key, Graph graph, long currentTime) {
            // Use wall clock time, rather than nanotime, if from an external resource
            long seconds = graph.creationDate().plusHours(5)
                .minus(System.currentTimeMillis(), MILLIS)
                .toEpochSecond();
            return TimeUnit.SECONDS.toNanos(seconds);
          }
          public long expireAfterUpdate(Key key, Graph graph, 
              long currentTime, long currentDuration) {
            return currentDuration;
          }
          public long expireAfterRead(Key key, Graph graph,
              long currentTime, long currentDuration) {
            return currentDuration;
          }
        })
        .build(key -> createExpensiveGraph(key));

    5.3 Reference-based

    // Evict when neither the key nor value are strongly reachable
    LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
        .weakKeys()
        .weakValues()
        .build(key -> createExpensiveGraph(key));
    
    // Evict when the garbage collector needs to free memory
    LoadingCache<Key, Graph> graphs = Caffeine.newBuilder()
        .softValues()
        .build(key -> createExpensiveGraph(key));

     

    6、LFU淘汰算法的Java实现

                             LFU(least frequently used) 最少使用率缓存 ,根据使用次数来判定对象是否被持续缓存  , 使用率是通过访问次数计算的。 
              ,当缓存满时清理过期对象。 , 清理后依旧满的情况下清除最少访问(访问计数最小)的对象并将其他对象的访问数减去这个最小访问数,以便新对象进入后可以公平计数。

    参考:HuTool工具包中的 cn.hutool.cache.impl.LFUCache 

    /**
    	 * 清理过期对象。<br>
    	 * 清理后依旧满的情况下清除最少访问(访问计数最小)的对象并将其他对象的访问数减去这个最小访问数,以便新对象进入后可以公平计数。
    	 * 
    	 * @return 清理个数
    	 */
    	@Override
    	protected int pruneCache() {
    		int count = 0;
    		CacheObj<K, V> comin = null;
    
    		// 清理过期对象并找出访问最少的对象
    		Iterator<CacheObj<K, V>> values = cacheMap.values().iterator();
    		CacheObj<K, V> co;
    		while (values.hasNext()) {
    			co = values.next();
    			if (co.isExpired() == true) {
    				values.remove();
    				onRemove(co.key, co.obj);
    				count++;
    				continue;
    			}
    
    			//找出访问最少的对象
    			if (comin == null || co.accessCount.get() < comin.accessCount.get()) {
    				comin = co;
    			}
    		}
    
    		// 减少所有对象访问量,并清除减少后为0的访问对象
    		if (isFull() && comin != null) {
    			long minAccessCount = comin.accessCount.get();
    
    			values = cacheMap.values().iterator();
    			CacheObj<K, V> co1;
    			while (values.hasNext()) {
    				co1 = values.next();
    				if (co1.accessCount.addAndGet(-minAccessCount) <= 0) {
    					values.remove();
    					onRemove(co1.key, co1.obj);
    					count++;
    				}
    			}
    		}
    		
    		return count;
    	}

    7、LRU淘汰算法的Java实现

               LRU (least recently used)最近最久未使用缓存,根据使用时间来判定对象是否被持续缓存 ,当对象被访问时放入缓存,当缓存满了,最久未被使用的对象将被移除。 
    ,此缓存基于LinkedHashMap,因此当被缓存的对象每被访问一次,这个对象的key就到链表头部。 这个算法简单并且非常快,他比FIFO有一个显著优势是经常使用的对象不太可能被移除缓存。
     缺点是当缓存满时,不能被很快的访问。

    参考:HuTool工具包中的 cn.hutool.cache.impl.LRUCache

    	/**
    	 * 只清理超时对象,LRU的实现会交给<code>LinkedHashMap</code>
    	 */
    	@Override
    	protected int pruneCache() {
    		if (isPruneExpiredActive() == false) {
    			return 0;
    		}
    		int count = 0;
    		Iterator<CacheObj<K, V>> values = cacheMap.values().iterator();
    		CacheObj<K, V> co;
    		while (values.hasNext()) {
    			co = values.next();
    			if (co.isExpired()) {
    				values.remove();
    				onRemove(co.key, co.obj);
    				count++;
    			}
    		}
    		return count;
    	}

     

    8、FIFO淘汰算法的Java实现

    元素不停的加入缓存直到缓存满为止,当缓存满时,清理过期缓存对象,清理后依旧满则删除先入的缓存(链表首部对象)。
     优点:简单快速 <br>
     缺点:不灵活,不能保证最常用的对象总是被保留

    参考:HuTool工具包中的 cn.hutool.cache.impl.FIFOCache

    /**
    	 * 先进先出的清理策略<br>
    	 * 先遍历缓存清理过期的缓存对象,如果清理后还是满的,则删除第一个缓存对象
    	 */
    	@Override
    	protected int pruneCache() {
    		int count = 0;
    		CacheObj<K, V> first = null;
    
    		// 清理过期对象并找出链表头部元素(先入元素)
    		Iterator<CacheObj<K, V>> values = cacheMap.values().iterator();
    		while (values.hasNext()) {
    			CacheObj<K, V> co = values.next();
    			if (co.isExpired()) {
    				values.remove();
    				count++;
    			}
    			if (first == null) {
    				first = co;
    			}
    		}
    
    		// 清理结束后依旧是满的,则删除第一个被缓存的对象
    		if (isFull() && null != first) {
    			cacheMap.remove(first.key);
    			onRemove(first.key, first.obj);
    			count++;
    		}
    		return count;
    	}

     

    展开全文
  • 常用的缓存淘汰算法
  • 最佳淘汰算法

    2020-05-01 17:42:15
    最佳淘汰算法 // C语言实现操作系统最佳淘汰算法 #include <stdio.h> #include <stdlib.h> #define length 20//定义数组长度 int bwoList[length];//淘汰序列 void initList(int arr[]) {//生成随机...

    最佳淘汰算法

    ```c
    // C语言实现操作系统最佳淘汰算法
    #include <stdio.h>
    #include <stdlib.h>
    
    #define length 20//定义数组长度
    int bwoList[length];//淘汰序列
    void initList(int arr[]) {//生成随机访问序列
        for (int i = 0; i < length; ++i) {
            int randNumber = rand() % 9 + 1;
            arr[i] = randNumber;
            if (i < length - 1)
                printf("%d ", arr[i]);
            else
                printf("%d\n", arr[i]);
        }
    }
    
    int findMax(int a, int b, int c) {//寻找三个数最大的元素
        int max = a;
        if (max < b)max = b;
        if (max < c)max = c;
        return max;
    }
    
    int BWO(int init[], int arr[]) {//最佳淘汰算法核心
        int countLoss = 0;//统计缺页次数
        int arr1 = length, arr2 = length, arr3 = length;//初始化所在位置,若访问序列有 则迭代更新
        for (int i = 3; i < length; ++i) {
            int flag = 0;//设定是否含有待访问标志
            for (int j = 0; j < 3; ++j) {
                if (arr[i] == init[j]) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {//待访问序列不含有所需数字
                countLoss++;//缺页次数更新
                for (int j = 0; j < 3; ++j) {
                    for (int k = 3; k < length; ++k) {
                        if (init[j] == arr[k]) {//寻找最远或者再未出现的元素
                            if (j == 0) {
                                arr1 = k;
                                break;
                            }
                            if (j == 1) {
                                arr2 = k;
                                break;
                            }
                            if (j == 2) {
                                arr3 = k;
                                break;
                            }
                        }
                    }
                }
                int max = findMax(arr1, arr2, arr3);
                if (arr1 == max) {
                    init[0] = arr[i];
                    bwoList[i] = arr[i];
                    continue;
                }
                if (arr2 == max) {
                    init[1] = arr[i];
                    bwoList[i] = arr[i];
                    continue;
                }
                if (arr3 == max) {
                    init[2] = arr[i];
                    bwoList[i] = arr[i];
                    continue;
                }
            }
        }
        return countLoss;
    }
    
    
    int main() {
        printf("\t欢迎来到最佳淘汰算法\n");
        printf("随机生成的访问序列为:");
        int arr[length];//存储随机访问序列
        initList(arr);
        int init[3];//存储预先装入序列
        int countLoss;//计算缺页次数
        for (int i = 0; i < 3; ++i) {
            init[i] = arr[i];
            arr[i] = 0;//表示该序列已访问
        }
        countLoss = BWO(init, arr);
        printf("--淘汰序列为:");
        int size = sizeof(bwoList) / sizeof(int);
        for (int i = 0; i < size; ++i) {
            if (i < size - 1 && bwoList[i] != 0) {
                printf("%d-->", bwoList[i]);
            } else if (bwoList[i] != 0) {
                printf("%d\n", bwoList[i]);
            }
        }
        printf("--缺页率为:%.2lf%%", (1.0 * countLoss / length) * 100);
    }
    

    运行结果

    在这里插入图片描述

    展开全文
  • 页面淘汰算法CLOCK.docx

    2021-09-12 03:54:21
    页面淘汰算法CLOCK.docx
  • 页面淘汰算法实验报告.doc
  • 对于动态页式存储管理 采用FIFO淘汰算法的实现 采用静态方法在程序中输入 当然动态的稍作改变即可实现
  • LRU算法–缓存淘汰算法

    千次阅读 2017-06-03 10:43:50
    LRU算法–缓存淘汰算法目录LRU算法缓存淘汰算法目录 什么是 LRU LRU 算法思想 为什么需要页面置换算法 分页原理图 假设使用 FIFO 先进先出 实现页面置换算法 LRU 算法原理图 使用双向链表实现LRU算法 Clock算法是...

    目录

    1. 什么是 LRU

    LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也很高”,反过来说“如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”,两种理解是一样的;常用于页面置换算法,是为虚拟页式存储管理服务的。

    2. LRU 算法思想

    达到这样一种情形的算法是最理想的:每次调换出的页面是所有内存页面中最迟将被使用的;这可以最大限度的推迟页面调换,这种算法,被称为理想页面置换算法。可惜的是,这种算法是无法实现的。
    为了尽量减少与理想算法的差距,产生了各种精妙的算法,最近最少使用页面置换算法便是其中一个。LRU 算法的提出,是基于这样一个事实:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到 。这个,就是著名的局部性原理——比内存速度还要快的cache,也是基于同样的原理运行的。因此,我们只需要在每次调换时,找到最近最少使用的那个页面调出内存。

    注意:操作系统分页处理使用的分页调度算法是LRU算法的近似实现:Clock算法

    3.为什么需要页面置换算法?

    • 内存是有限的,不可能把所有的页面都装进来
      – 缺页时需要进行页面置换

    • 页面置换的背后是个通用的问题
      –Web服务器的缓存
      –Redis ,memcached 的缓存
      –……

    4.分页原理图

    这里写图片描述

    5. 假设使用 FIFO (先进先出) 实现页面置换算法

    这里写图片描述

    很明显, 按照FIFO算法, 虽然一个页面被频繁访问, 它还是很有可能被置换出去。

    6. LRU 算法原理图

    这里写图片描述

    7. 使用双向链表实现LRU算法

    算法实现:

    public class LRUPageFrame {
        private static class Node{
            Node prev;
            Node next;
            int pageNum;
            Node(){
    
            }
        }
    
        private int capacity;//容量
    
        private int currentSize;
        private Node first;
        private Node last;
    
        public LRUPageFrame( int capacity ) {
            this.currentSize = 0;
            this.capacity  = capacity;
        }
    
        /**
         * 获得缓存中的对象
         * @param pageNum
         */
        public void access( int pageNum ){
            Node node = find( pageNum );
            if( node != null ){
                moveExistingNodeToHead(node);
            } else {
    
                node = new Node();
                node.pageNum = pageNum;
    
                // 缓存容器是否已经超过大小.
                if( currentSize >= capacity ){
                    removeLast(); 
                }
    
                addNewNodetoHead(node);
            } 
        }
        private Node find( int data ){
            Node node = first;
            while( node != null ){
                if( node.pageNum == data ){
                    return node;
                }
                node = node.next;
            }
            return null;
        }
    
    
        /**
         * 移动到链表头,表示这个节点是最新使用过的
         * @param node
         */
        private void moveExistingNodeToHead( Node node ){
            if( node == first ){
                return;
            } else if( node == last ){
                //当前节点是链表尾, 需要放到链表头
                Node prevNode = node.prev;
                prevNode.next = null;
                last.prev = null;
                last = prevNode;
            } else {
                //node 在链表的中间, 把node 的前后节点连接起来
                Node prevNode = node.prev;
                prevNode.next = node.next;
    
                Node nextNode = node.next;
                nextNode.prev = prevNode;
            }
            node.prev = null;
            node.next = first;
            first.prev = node;
            first = node;
        }
    
        /**
         * 删除链表尾部节点 表示 删除最少使用的缓存对象
         */
        private void removeLast(){
            Node prevNode = last.prev;
            prevNode.next = null;
            last.prev = null;
            last = prevNode;
            this.currentSize --;
        }
    
        private void addNewNodetoHead( Node node ){
            if( isEmpty() ){
                node.prev = null;
                node.next = null;
                first = node;
                last = node;
            } else {
                node.prev = null;
                node.next = first;
                first.prev = node;
                first = node;
            }
            this.currentSize ++;
        }
    
        private boolean isEmpty(){
            return (first == null) && (last == null);
        }
    
        public String toString(){
            StringBuilder buffer = new StringBuilder();
            Node node = first;
            while( node != null ){
                buffer.append( node.pageNum );
                node = node.next;
                if( node != null ){
                    buffer.append(",");
                }
            }
            return buffer.toString();
        }
    }
    

    测试用例:

    public class LRUPageFrameTest {
        @Test
        public void testAccess() {
            LRUPageFrame frame = new LRUPageFrame(3);
            frame.access(7);
            frame.access(0);
            frame.access(1);
            Assert.assertEquals("1,0,7", frame.toString());
            frame.access(2);
            Assert.assertEquals("2,1,0", frame.toString());
            frame.access(0);
            Assert.assertEquals("0,2,1", frame.toString());
            frame.access(0);
            Assert.assertEquals("0,2,1", frame.toString());
            frame.access(3);
            Assert.assertEquals("3,0,2", frame.toString());
            frame.access(0);
            Assert.assertEquals("0,3,2", frame.toString());
            frame.access(4);
            Assert.assertEquals("4,0,3", frame.toString());
            frame.access(5);
            Assert.assertEquals("5,4,0", frame.toString());
        }   
    }

    8.Clock算法是公认的很好的近似LRU的算法

    只有三个物理页面 逻辑页面的访问次序是:
    3、4、2、6、4、3

    这里写图片描述

    • 每个页加一个引用位, 默认值为0,无论读还是写,都置为1

    • 把所有的页组成一个循环队列

    • 选择淘汰页的时候,扫描引用位, 如果是1则改为0(相当于再给该页面一次存活的机会), 并扫描下一个;如果该引用位是0, 则淘汰该页, 换入新的页面

      脚注
      前两节内容节选自—— [ MinHow-个人博客 ]

    展开全文
  • 缓存淘汰算法之LRU

    2017-05-05 11:50:53
    缓存淘汰算法之LRU
  • 如果工作集中的实页总数已满,则采用某一淘汰算法实施页面置换。 要求:用链表表示虚存页面表和主存页面表,通过不断地调用指令,查看是否能够命中主存中的相关页面,并计算命中率。若出现页面置换情况,采用FIFO...
  • 主要介绍了golang实现LRU缓存淘汰算法的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 缓存是一个计算机思维,...一、缓存淘汰算法定义 缓存算法是指令的一个明细表,用于决定缓存系统中哪些数据应该被删去。 常见类型包括LFU、LRU、ARC、FIFO、MRU。 二、最不经常使用算法(LFU-Least Frequently Us...

    缓存是一个计算机思维,对于重复的计算,缓存其结果,下次再算这个任务的时候,不去真正的计算,而是直接返回结果,能加快处理速度。当然有些会随时间改变的东西,缓存会失效,得重新计算。

    一、缓存淘汰算法定义

    缓存算法是指令的一个明细表,用于决定缓存系统中哪些数据应该被删去。

    常见类型包括LFU、LRU、ARC、FIFO、MRU。

    二、最不经常使用算法(LFU-Least Frequently Used)

    这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法,最低访问数的条目首先被移除。这个方法并不经常使用,因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。


    三、最近最少使用算法(LRU-Least Recently Used

    这个缓存算法将最近使用的条目存放到靠近缓存顶部的位置。当一个新条目被访问时,LRU将它放置到缓存的顶部。当缓存达到极限时,较早之前访问的条目将从缓存底部开始被移除。这里会使用到昂贵的算法,而且它需要记录“年龄位”来精确显示条目是何时被访问的。此外,当一个LRU缓存算法删除某个条目后,“年龄位”将随其他条目发生改变。

    算法有两种策略(均以队列的方式实现),一种是不调整的,另外一种是随时进行调整的,即缓存命中后,将这个数据缓存项移到LRU队列的最前端。

    java中利用LinkedHashMap来实现LRU算法,需要覆写其中的removeEldestEntry(Map.Entry)方法即可。如果去看LinkedHashMap的源码可知,LRU算法是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置。

    LinkedHashMap自身已经实现了顺序存储,默认情况下是按照元素的添加顺序存储,也可以启用按照访问顺序存储,即最近读取的数据放在最前面,最早读取的数据放在最后面,然后它还有一个判断是否删除最老数据的方法,默认是返回false,即不删除数据,我们使用LinkedHashMap实现LRU缓存的方法就是对LinkedHashMap实现简单的扩展。

    //LinkedHashMap的一个构造函数,当参数accessOrder为true时,即会按照访问顺序排序,最近访问的放在最前,最早访问的放在后面
    public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
    }
    
    //LinkedHashMap自带的判断是否删除最老的元素方法,默认返回false,即不删除老数据
    //我们要做的就是重写这个方法,当满足一定条件时删除老数据
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return false;
            //return size() > MAX_CACHE_SIZE;   (改为这个)
    
    }

    四、自适应缓存替换算法(ARC-Adaptive Replacement Cache)

    在IBM Almaden研究中心开发,这个缓存算法同时跟踪记录LFU和LRU,以及驱逐缓存条目,来获得可用缓存的最佳使用。

    有人说是介于 LRU 和 LFU 之间,为了提高效果,是由2个 LRU 组成,第一个,也就是 L1,包含的条目是最近只被使用过一次的,而第二个 LRU,也就是 L2,包含的是最近被使用过两次的条目。因此, L1 放的是新的对象,而 L2 放的是常用的对象。所以,别人才会认为是介于 LRU 和 LFU 之间的,不过没关系,我不介意。

    被认为是性能最好的缓存算法之一,能够自调,并且是低负载的。也保存着历史对象,这样,就可以记住那些被移除的对象,同时,也可以看到被移除的对象是否可以留下,取而代之的是踢走别的对象。他的记忆力很差,但是很快,适用性也强。

    五、先进先出算法(FIFO-First in First out)

    FIFO是英文First In First Out 的缩写,是一种先进先出的数据缓存器,他与普通存储器的区别是没有外部读写地址线,这样使用起来非常简单,但缺点就是只能顺序写入数据,顺序的读出数据,其数据地址由内部读写指针自动加1完成,不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。

    image

    六、最近最常使用算法(MRU-Most Recently Used)

    这个缓存算法最先移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久,越容易被访问的情况。

    和 LRU 是对应的。会移除最近最多被使用的对象,你一定会问我为什么。好吧,让我告诉你,当一次访问过来的时候,有些事情是无法预测的,并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算,这就是为什么我是最好的选择。

    我是数据库内存缓存中是多么的常见!每当一次缓存记录的使用,我会把它放到栈的顶端。当栈满了的时候,你猜怎么着?我会把栈顶的对象给换成新进来的对象!

    七、Redis中使用的缓存总结

    Redis提供了下面几种淘汰策略供用户选择,其中默认的策略为noeviction策略:

    • noeviction:当内存使用达到阈值的时候,所有引起申请内存的命令会报错。
    • allkeys-lru:在主键空间中,优先移除最近未使用的key。
    • volatile-lru:在设置了过期时间的键空间中,优先移除最近未使用的key。
    • allkeys-random:在主键空间中,随机移除某个key。
    • volatile-random:在设置了过期时间的键空间中,随机移除某个key。
    • volatile-ttl:在设置了过期时间的键空间中,具有更早过期时间的key优先移除。

    我的微信公众号:架构真经(id:gentoo666),分享Java干货,高并发编程,热门技术教程,微服务及分布式技术,架构设计,区块链技术,人工智能,大数据,Java面试题,以及前沿热门资讯等。每日更新哦!

    参考资料:

    1. https://blog.csdn.net/youanyyou/article/details/78989956
    2. https://www.cnblogs.com/james111/p/7125353.html
    3. https://blog.csdn.net/w15249243295/article/details/52446845
    4. https://www.cnblogs.com/losing-1216/p/4953663.html
    展开全文
  • Redis常用淘汰算法: FIFO: First In First Out,先进先出算法,判断被存储的时间,离目前最远的数据优先被淘汰 LRU:Least Recently Used,最近最少使用算法,判断最近被使用的时间,目前最远的数据优先被淘汰; ...
  • 页面置换算法,或者称缓存淘汰算法,共有三种,即 FIFO,LRU, LFU。 1. FIFO(First In First Out) 这是最简单的,即先进先出算法,其实现方式已经很明显了,就是队列。在操作系统中, 作业调度就需要利用这一种...
  • 缓存淘汰算法-LRU算法

    2018-04-27 09:32:17
    转载自:缓存淘汰算法-LRU算法 &nbsp; 1.&nbsp;LRU1.1.&nbsp;原理 LRU(Least&nbsp;recently&nbsp;used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据...
  • 淘汰算法之FIFO (Fist in first out) 先进先出。
  • 淘汰算法之LFU(The Least Frequently Used)最不经常使用。
  • 当内存占用率达到 max memory 设置定的界限时(可能是80%),缓存组件则会执行用户设定的淘汰算法,淘汰旧数据,直到有足够的空闲内存,去存储新的键值对。 下面常用的淘汰算法: 1.LRU 最近最少...
  • 页面淘汰算法模拟实现与比较实验报告.zip
  • LRU缓存淘汰算法

    千次阅读 2018-10-14 10:15:48
    LRU,最近最少使用算法,即当要对数据进行淘汰时,先将最近最久未使用的数据淘汰(亦说最近最久未使用算法),是一种缓存淘汰算法。     意义:大家知道计算机的内存是有限的,当我们对一些数据一直缓存而不...
  • 操作系统中的页面淘汰算法程序,用C#编写的。
  • CEA:基于弱势种群保护抗早熟的聚类淘汰算法.pdf
  • 先进先出淘汰算法

    2020-05-01 18:54:50
    // C语言实现操作系统最佳淘汰算法 #include <stdio.h> #include <stdlib.h> #define length 20//定义数组长度 int bwoList[length];//淘汰序列 void initList(int arr[]) {//生成随机访问序列 for ...
  • 操作系统实验报告 课题页面淘汰算法 专 业 班 级 学 号 姓 名 年 月 日 目 录 TOC \o "1-3" \h \z \u HYPERLINK 一 实验目的 3 HYPERLINK 二 实验要求 3 HYPERLINK 三 背景知识 3 四 HYPERLINK 总体设计 4 HYPERLINK...
  • Redis算法(二)LRU数据淘汰算法 Redis淘汰策略: 当Reis使用的内存超过配置的maxmemory时,便会触发数据淘汰策略 数据淘汰策略: volatile-lru: 最近最少使用算法,从设置了过期时间的键中选择空转时间最长的键值对...
  • 简单时钟式淘汰算法

    2020-05-02 17:40:39
    // C语言实现操作系统简单时钟式淘汰算法 #include <stdio.h> #include <stdlib.h> #include <string.h> #define length 10//定义数组长度 typedef struct Node {//生成数据节点 int index; ...
  • 第 PAGE 8 页 共 NUMPAGES13 页 操作系统原理 上机作业报告 作业 页 面 淘 汰 算 法 作业编号 6 题目 页面淘汰/置换算法 作业要求 题目要求通过模拟...针对一个页框根据实验数据以OPT算法为参考研究FIFO页面淘汰算法LRU
  • 基于多级队列缓存淘汰算法的处理器全数字仿真优化.pdf
  • golang--算法--LRU 缓存淘汰算法

    千次阅读 2020-02-29 09:54:03
    说到链表一个经典的应用场景,那就是 LRU 缓存淘汰算法。 缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。缓存的大小有限,当...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,761
精华内容 28,304
关键字:

淘汰算法