| layout | title | category | description | tags |
|---|---|---|---|---|
post |
LRU |
数据结构 |
LRU... |
LRU 最近最少使用 |
内存的页管理有很多使用最近最少使用（LRU）的算法，这个算法实际上很简单，这里简单的说一下。这里涉及到局部性原理。局部性原理的意思就是认为在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。相反，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。
可以用简单的数组表示我们使用的页。
{% highlight c++ %} int a[22] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6, 6, 4}; {% endhighlight %}
例如先使用1，然后再使用2，那么我们就有[2, 1]这个数组。然后使用3，则有[3, 2, 1]这个数组。这个时候使用1，那么数组就会变为[1, 3, 2]，非常好理解。这个时候我们可以认为1是最常使用的，而2是最少使用。
如果假设这个数组长度为3，那么再加入的话，就会变成[4, 1, 3]，因为2是最少使用的，被我们换出了。如果我们不考虑换出的情况，可以简单的写一个lru便于了解。具体深入的和缓存各种其他结构理论上是一样的。
定义一个简单的结构，包含值和下一个结点的指针，其实用数组也可以实现，但我这里用链表更简单，因为很多情况下一个结点的结构不只是一个数值：
{% highlight c++ %} struct page { int value; page *next; }; {% endhighlight %}
然后初始化一个page实例，作为最初的node，node之后的结构才是整个数组的结构。
{% highlight c++ %} page init(const int value){ / init the first node */ page p = (page)malloc(sizeof(page)); p->value = value; p->next = NULL; return p; } {% endhighlight %}
插入一个数据，首先在链表中搜索，如果搜索到就替换结构，否则就在链表头node后添加当前page数据。如果对链表长度有限制，需要换出最少使用的页，这里仅仅是简单的算法，所以不过多限制。
{% highlight c++ %} int put(page node, const int value){ / 搜索结点 */ int r = search_page(node, value); if(r==1){ hit+=1; printf("hit value %d\n", value); return 1; } miss+=1; printf("miss value %d\n", value); page p = (page)malloc(sizeof(page)); p->value = value; p->next = NULL; if(node->next==NULL){ node->next = p; } else { p->next = node->next; node->next = p; } return 1; } {% endhighlight %}
搜索结点具体如下，简单的说就是把碰撞到的结点拿到跟结点后，然后改变next指针。这里有很多可以优化的地方。
{% highlight c++ %} int search_page(page *node, const int value){ page *p = node; page pre = node; if(!p->next){ return 0; } p = p->next; while(p) { if(p->value == value) { / replace / / 如果当前结点的next不为空，应该把pre的next设置为 当前结点的next, 否则pre结点的next设为NULL / if(p->next!=NULL) { pre->next = p->next; } else { pre->next=NULL; } if(node->next!=p){ / 交换结点 */ p->next = node->next; node->next = p; } return 1; } pre = p; p = p->next; } return 0; } {% endhighlight %}
我们可以用下面的方法来测试：
{% highlight c++ %} int main(){ page *node = init(-1); int total=22; int a[22] = {1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6, 6, 4}; for(int i=0;i<total;i++){ put(node, a[i]); print_node(node); } printf("total miss %d\n", miss); printf("total hit %d\n", hit); return 0; } {% endhighlight %}
我们可以看到最后的结果为[4, 6, 3, 2, 1, 7, 5]。当然，如果有换出操作的话，结果不是这样。因为hit和miss数据都会有变化1。这是一个简单的LRU算法帮助理解。代码可以在这个GIST上找到。可以自己实现长度限制并统计缺页换出次数。
Footnotes
-
当换出之后hit率会更少。 ↩