页面置换算法及LRU、LFU算法实现

在地址映射过程中,一旦发现所要的页面不在内存中,立马产生缺页中断——选择淘汰某个页面(页面置换算法)。

最近最久未使用算法(LRU)

它是一种看过去的算法,英文名为Least Recently Used。

  • 基本思路:选择之前一段时间里最久没有使用过的页面予以置换。

效果是相当好的,但是存在如何实现它的问题,需要具体硬件的支持,大致有两种方法,

TODO:关于需要硬件支持,我还需要查阅更多的资料。——2019-07-19

  • 计数器。每个页增加一个时间字段,每次访问更新最新时间。缺点:每次需要查页表,更新时间值,还要考虑时间溢出问题。
  • 哈希表+双向链表。

采用哈希表+双向链表法,LRU Cache算法实现,

TODO:补一张结构图——2019-07-19

https://github.com/qingdujun/algorithm/blob/master/problems/146.%20LRU%20Cache.md

class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {

}

int get(int key) {
auto iter = map_.find(key);
if (iter == map_.end()) {
return -1;
}
//put key at the beginning
std::pair<int, int> page = *(map_[key]);
cache_.erase(map_[key]);
cache_.emplace_front(page);
//update iterator
map_[key] = cache_.begin();
return page.second;
}

void put(int key, int value) {
auto iter = map_.find(key);
if (iter == map_.end()) {
//full, erase the end node and update map_
if (cache_.size() >= capacity_) {
auto end_pair = cache_.back();
int end_key = end_pair.first;
map_.erase(end_key);
cache_.pop_back();
}
} else {
cache_.erase(map_[key]);
}
//insert the new node at the begin and update iterator
cache_.emplace_front(std::make_pair(key, value));
map_[key] = cache_.begin();
}

private:
int capacity_;
std::list<std::pair<int, int>> cache_;
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map_;
};

最少使用置换算法(LFU)

全称为Least Frequency Used。实现时可以在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率。

  • 基本思路: 如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小。

实现一个结合LRU的LFU算法,也就是说如果访问频率相同就使用LRU算法选择。

TODO:补充一张结构图——2019-07-19

https://github.com/qingdujun/algorithm/blob/master/problems/460.%20LFU%20Cache.md

class LFUCache {
public:
LFUCache(int capacity) : capacity_(capacity), min_freq_(1) {

}

int get(int key) {
if (cache_.find(key) == cache_.end()) {
return -1;
}
int value = cache_[key].first;
int freq = cache_[key].second;
++cache_[key].second;//++freq
freq_[freq].erase(iter_[key]);
freq_[freq+1].emplace_back(key);
iter_[key] = --(freq_[freq+1].end());
if (freq == min_freq_ && freq_[min_freq_].empty()) {
++min_freq_;
}
return value;
}

void put(int key, int value) {
if (capacity_ <= 0) {
return;
}
if (cache_.find(key) == cache_.end()) {
if (cache_.size() >= capacity_) {
int min_key = freq_[min_freq_].front();
freq_[min_freq_].pop_front();
cache_.erase(min_key);
iter_.erase(min_key);
}
min_freq_ = 1;
cache_[key] = std::make_pair(value, min_freq_);
freq_[min_freq_].emplace_back(key);
iter_[key] = --(freq_[min_freq_].end());
} else {
cache_[key].first = value;
get(key);
}
}

private:
int capacity_;
int min_freq_;
std::unordered_map<int, std::pair<int,int>> cache_; //<key, <value, freq>>
std::unordered_map<int, std::list<int>> freq_; //<freq, [key1, key2,...]>
std::unordered_map<int, list<int>::iterator> iter_;//<key, list<key>::iterator>
};

其他算法

最佳置换算法(OPT)

它是一种看未来的算法,一种理想算法效果是最好的、缺页中断率最低,但是不能被实现。

  • 基本思路:置换以后不再被访问,或者在将来最迟才被访问的页面。

先进先出算法(FIFO)

一个很古老的算法,目前几乎不被使用。而且它还会导致Belady现象——如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多,但缺页率反而提高的异常现象,这是一个违反直觉的现象。

Belady现象和抖动并不完全一样。抖动是指如果分配给进程的存储块数量小于进程所需要的最小值,进程的运行将很频繁地产生缺页中断。

工作集时钟算法

工作集算法利用了程序的局部性原理。页面替换算法一般分为:全局页面替换和局部页面替换。在请求分页策略中,一开始不给进程分配页。当进程需要的时候,才开始慢慢分配,直到页面数量趋于稳定。

有一种说法,这个页面数量就是工作集大小,工作集相当于一个滑动窗口一样。

  • 《操作系统设计哲学》一书上讲到:既然,页面置换算法本来就不是精确的,那么还费那么大力气。不如换种思路,就将页面分为工作集外和工作集内。当缺页时,从进程外换一个页面进来即可。

那么工作集时钟算法又是什么呢?其实,在实现工作集算法时是需要扫描页表的,那么每次都从开头开始扫描,这带来了不公平性。

时钟算法,将页表弄成一个环,每次从上一次结束的下一个位置开始扫描。这下公平了。


References:

[1] yinnnnnn, redis之父的博客翻译-Redis中的LRU算法改进

[2] ojshilu,Belady奇异现象和Thrashing抖动现象的比较

[3] 百度百科,页面置换算法

[4] Matrix海子,缓存算法(页面置换算法)-FIFO、LFU、LRU