首页 > 代码库 > 由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 };
7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 | ||
0 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | |
7 | 7 | 7 | 0 | 1 | 2 | 2 | 3 | 0 | 4 | 2 | 2 | 0 | 3 | 3 | 1 | 2 | 0 | 1 | 7 |
举例说明:第一行从左往右是要访问的页号,size值为3,每一列表示访问当前页后,cacheList中存在的页号以及各自的优先级别(从上往下默认为list从头至尾,按照LRU规则,头是最近访问的,尾是优先级别最低的,也就是最有可能会被置换),背景黄色说明产生了缺页中断。每一次访问当前页,size满时,当前页面若存在,虽然不产生页面置换,但是页面的优先级也会发生改变;若不存在,尾巴处的页面被置换,当前页面被插入list头。
ps:以前学LRU算法时,只要搞懂手算就可以(如上述举例图表),要想真正理解LRU算法,最好会写代码,考虑到用哪些数据结构来保存页号,使得增加,删除,替换改变页号的时间效率最好。下面是LeetCode中 LRU Cache的链接
https://oj.leetcode.com/problems/lru-cache/
由LeetCode的LRU Cache谈到操作系统中LRU算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。