Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

手撕操作系统中的页面置换算法

2020/10/31
Word count: 2,002 | Reading time: 8min

操作系统基础 内存换页算法

公平算法:

  • 随机算法、先来先出(FIFO)算法、第二次机会算法、时钟算法

非公平算法:

  • 最优OPT算法、NRU算法、LRU算法、工作集算法、工作集时钟算法

其中LRU算法会被面试的时候要求手撕, 因此本篇就稍微介绍一下LRU和LFU两个算法, 这两个算法除了在内存换页上会被使用到,

简单介绍一些算法:

随机更换算法

需要替换页面的时候,产生一个随机页面号,替换与该页面对应的物理页面。

先来先出(FIFO)算法

更换最早进入内存的页面。其中有Belady异常现象: 缺页率随内存块数增加而增加

最优OPT算法:

最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。
采用最佳置换算法通常可保证获得最低的缺页率

▲由于人们目前还无法预知,一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的。

Q: 既然无法实现, 那么他的价值是什么呢?

A: 他被作为评价一个内存换页算法效率的标榜

NRU算法

最近未使用算法(Not Recently Used,NRU),就是选择一个最近没有被访问的页面来替换,在所有的最近没有使用的页面里,按照各个页面的修改位和访问位的组合来进行划分。相比LRU需要较多硬件支持, NRU算法在页表项设置两个状态位:引用位R和修改位M

LRU

Q、什么是 LRU 算法?

A: Least Recently Used最近最久未使用算法,本质一种缓存淘汰策略。

计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。那么,什么样的数据,我们判定为「有用的」的数据呢?

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。

▲同时它也是一种换页算法, 在内存换页上需要较多的硬件支持(计数器or栈)

常见的缓存算法

  • LRU (Least recently used) 最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。
  • LFU (Least frequently used) 最不经常使用,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小。
    • LFU由于涉及频率, 因此在代码实现上有个计数器来统计出现次数T,在需要换页(缓存更新的时候)将替换掉最低T的key
  • FIFO (Fist in first out) 先进先出, 如果一个数据最先进入缓存中,则应该最早淘汰掉。

LRU算法与OPT算法比较

OPT是从“向后看”的观点出发的,即它是依据以后各页的使用情况进行判断,是理想状况;而LRU算法则是“向前看”的,即根据各页以前的使用情况来判断,而页面过去和未来的走向之间虽无必然的联系,但也有一定的预测关系。
总的来说,LRU算法是一种比较好的算法。

Q: 算法要求

LRU 算法实际上是让你设计数据结构:首先要接收一个 capacity 参数作为缓存的最大容量,然后实现两个 API,一个是 put(key, val) 方法存入键值对,另一个是 get(key) 方法获取 key 对应的 val,如果 key 不存在则返回 -1。其中, get(key)的时候会把这个新查询的key放到最前端

由于性能要求,get 和 put 方法必须都是 O(1) 的时间复杂度。

  • get需要O(1) --> hash or 线性表
  • put需要O(1) -->链表

Coding实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package lru;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
class Node {
Integer key;
Integer val;
// 双向列表: 前后向节点
Node nxt, prev;

public Node() {
}

Node(int k, int v) {
this.key = k;
this.val = v;
}

@Override
public String toString() {
return "Node{" +
"key=" + key +
", val=" + val +
'}';
}
}

class DoubleList{
private int size;
// 头尾空指针
private final Node head;
private final Node tail;

DoubleList() {
// 初始化
this.size = 0;
this.head = new Node();
this.tail = new Node();
this.head.nxt = tail;
this.tail.prev = head;
}

/**
* 将节点到头部, head->nxt = node;
* @param node 待插入节点
*/
public void addFirst(Node node){
// 4个指针关系
node.nxt = head.nxt;
node.prev = head;
head.nxt.prev = node;
head.nxt = node;
// 记得增加当前容器Size
this.size ++;
}

public void remove(Node node){
// 略过当前节点, 调整前后指针
node.nxt.prev = node.prev;
node.prev.nxt = node.nxt;
// 调整容器Size
this.size--;
}

public Node removeLast(){
// 删除尾节点, 为tail.prev
Node node = tail.prev;
// ▲笔误写错, 查了半小时
node.nxt= tail;
remove(node);
// 删除的时候还要在mp中删除索引, 因此要返回值
return node;
}

public int getSize() {
return this.size;
}

@Override
public String toString() {
return "DoubleList{" +
"size=" + size +
'}';
}
}


int capacity;
Map<Integer, Node> mp;
DoubleList list;

public LRUCache(int capacity) {
this.capacity = capacity;
list = new DoubleList();
mp = new HashMap<Integer, Node>();
}

/**
* 访问过的key对应的Node需要放到队首部(最近查询)
* @param key 键
* @return 有相应的key则返回对应Node的val, 无则返回-1
*/
public int get(int key) {
if ( mp.containsKey( key) ){
int res = mp.get(key).val;
// ★ 把当前访问的放到队首
put(key, res);
return res;
}
else return -1;
}

/**
* 1. 如果已有key, 则删除容器中原有的Node, 将其放到队首
* 2. 如果没有key,
* 2.1 如果容器已满, 则将队尾的排出, 再将新Node加在队首
* 2.2 如果容器未满, 则直接将新Node加在队首
* @param key
* @param value
*/
public void put(int key, int value) {
Node node = new Node(key, value);
if (mp.containsKey(key)){
list.remove(mp.get(key));
list.addFirst(node);
mp.put(key, node);
}else{
if ( list.getSize() == capacity ){
Node last = list.removeLast();
mp.remove(last.key);
}
list.addFirst(node);
mp.put(key, node);
}
}

@Override
public String toString() {
return "LRUCache{" +
"capacity=" + capacity +
", mp=" + mp.toString() +
", list=" + list.toString() +
'}';
}
}

LeetCode代码检验 : 146. LRU缓存机制

算法实现参考: LRU算法:手把手带你实现一个干啥都快的快乐算法, 思路挺清晰的, 只不过只有LRUCache的代码, 需要自己实现双向链表

LFU

LFU (Least frequently used) 最不经常使用,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小。

  • LFU由于涉及频率, 因此在代码实现上有个计数器来统计出现次数T,在需要换页(缓存更新的时候)将替换掉最低T的ke

算法实现思路:

  • O(1)查询: hash+
  • O(1)修改+频率排序:set

附录

参考链接:

Author: Mrli

Link: https://nymrli.top/2020/09/21/手撕操作系统中的页面置换算法/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
AutoLianliankan笔记
NextPost >
docsify使用记录
CATALOG
  1. 1. 操作系统基础 内存换页算法
    1. 1.1. 简单介绍一些算法:
      1. 1.1.1. 随机更换算法
      2. 1.1.2. 先来先出(FIFO)算法
      3. 1.1.3. 最优OPT算法:
      4. 1.1.4. NRU算法
    2. 1.2. LRU
      1. 1.2.1. Q、什么是 LRU 算法?
        1. 1.2.1.1. 常见的缓存算法
      2. 1.2.2. LRU算法与OPT算法比较
      3. 1.2.3. Q: 算法要求
      4. 1.2.4. Coding实现
    3. 1.3. LFU
  2. 2. 附录