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

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

2024-07-20 07:37:13   220人阅读

 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算法


联系
我们