首页 > 代码库 > 由LeetCode的LRU Cache谈到操作系统中LRU算法

由LeetCode的LRU Cache谈到操作系统中LRU算法

 1 class LRUCache{ 2 public: 3     LRUCache(int capacity) { 4         size = capacity; 5     } 6     int get(int key) { 7         if(cacheMap.find(key)==cacheMap.end()) 8             return -1; 9         cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);10         cacheMap[key] = cacheList.begin();11         return cacheMap[key]->second;12     }13     void set(int key, int value) {14         if(cacheMap.find(key)!=cacheMap.end()){15             cacheList.splice(cacheList.begin(),cacheList,cacheMap[key]);16             cacheMap[key] = cacheList.begin();17             cacheMap[key]->second = value;18         }19         else{20             if(cacheList.size()==size){21                 cacheMap.erase(cacheList.back().first);22                 cacheList.pop_back();23             }24             cacheList.insert(cacheList.begin(),make_pair(key,value));25             cacheMap[key] = cacheList.begin();26         }27     }28 private:29     int size;30     list<pair<int,int>> cacheList;31     map<int,list<pair<int,int>>::iterator> cacheMap;32 };
举例
70120304230321201701
  120304230321201701
 0012030423032120170
77701223042203312017

 

举例说明:第一行从左往右是要访问的页号,size值为3,每一列表示访问当前页后,cacheList中存在的页号以及各自的优先级别(从上往下默认为list从头至尾,按照LRU规则,头是最近访问的,尾是优先级别最低的,也就是最有可能会被置换),背景黄色说明产生了缺页中断。每一次访问当前页,size满时,当前页面若存在,虽然不产生页面置换,但是页面的优先级也会发生改变;若不存在,尾巴处的页面被置换,当前页面被插入list头。

ps:以前学LRU算法时,只要搞懂手算就可以(如上述举例图表),要想真正理解LRU算法,最好会写代码,考虑到用哪些数据结构来保存页号,使得增加,删除,替换改变页号的时间效率最好。下面是LeetCode中 LRU Cache的链接

https://oj.leetcode.com/problems/lru-cache/

 

由LeetCode的LRU Cache谈到操作系统中LRU算法