LRU算法
$Least Recently Used$ 算法，意为“最近最少使用”，这是操作系统内存管理部分重要的一个页置换算法。
解释：LRU chooses that page that has not been used for the longest period of time.
追溯Operating System
Operating System 中特别重要的三个页置换算法：

First-In-First-Out (FIFO) Algorithm
Optimal Algorithm
Least Recently Used (LRU) Algorithm

当然还有很多其他算法，比如LRU Approximation Algorithms，不提……
Optimal Algorithm 与 LRU Algorithm
Optimal Algorithm 为什么是“最优”呢？因为它着眼未来，但实际上，“未来并不可以准确预测”，所以不能在计算机上真正实现，但LRU是可以的。
LRU的思想，恰如其名，着眼于过去，它根据过去的使用做出判断。
简而言之，就是“谁最近没被用过，就把谁换出去”，栈和队列这样的数据结构就可以帮助我们实现这一点。

当然，也可以对页面的引用时间进行计时，通过计时进行页置换。
LRU算法实例
给出一个 reference string ：“7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1”，置换顺序如下：（注意下图前三次也是换进去的呀，每个页都是经历Demand Paging才得以从外存换入内存的）


栈实现的解读
比如下图，在 a → b 的时候，相当于把7号页从栈中抽出来放到栈底（注意栈底在顶部），从栈顶换出页，新换入的页插入栈底。（实际上就相当于队列结构啦）


洛谷P1540题
题目要求
P1540题目链接

分析
在有经验的人看来，确实，普通的模拟+使用队列作为辅助数据结构，一个小题。
问题是，你还想到了什么？

没错——LRU算法！
其实这题的背景本身就是OS的虚拟内存页置换算法啊！
AC代码（Java语言描述）
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        Scanner scanner = new Scanner(System.in);
        int limit = scanner.nextInt(), num = scanner.nextInt(), counter = 0, result = 0;
        while (queue.size() <= num && result < limit) {
            int temp = scanner.nextInt();
            if (!queue.contains(temp)) {
                queue.offer(temp);
                result++;
            }
            counter++;
        }
        for (int i = counter; i < num; i++) {
            int temp = scanner.nextInt();
            if (!queue.contains(temp)) {
                queue.poll();
                queue.offer(temp);
                result++;
            }
        }
        scanner.close();
        System.out.println(result);
    }
}

总结
LRU算法是一种重要的算法。比起算法本身，更重要的是领会到LRU算法的思想，并能在处理实际问题的时候得以启发，这样就很好啦！
另外，OS的LRU页置换算法也应该深刻理解，这是涉及计算机原理的重要知识。
希望对不懂LRU算法的读者一些启示，也希望帮助对洛谷P1540题理解不深的读者加深理解。

总之，希望对大家有所帮助！

	

LRU原理
在一般标准的操作系统教材里，会用下面的方式来演示 LRU 原理，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。
但是如果让我们自己设计一个基于 LRU 的缓存，这样设计可能问题很多，这段内存按照访问时间进行了排序，会有大量的内存拷贝操作，所以性能肯定是不能接受的。
那么如何设计一个LRU缓存，使得放入和移除都是 O(1) 的，我们需要把访问次序维护起来，但是不能通过内存中的真实排序来反应，有一种方案就是使用双向链表。 
实现LRU
1.用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
2.利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中(即数据被访问)，则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。
3.利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在(一般称为命中)，则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。对于第二种方法，链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。
基于 HashMap 和 双向链表实现 LRU 的
整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。
LRU 存储是基于双向链表实现的，下面的图演示了它的原理。其中 head 代表双向链表的表头，tail 代表尾部。首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。
下面展示了，预设大小是 3 的，LRU存储的在存储和访问过程中的变化。为了简化图复杂度，图中没有展示 HashMap部分的变化，仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下：
save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)
相应的 LRU 双向链表部分变化如下：
总结一下核心操作的步骤:
save(key, value)，首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
get(key)，通过 HashMap 找到 LRU 链表节点，因为根据LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。
 完整基于 Java 的代码参考如下
class DLinkedNode {    String key;    int value;    DLinkedNode pre;    DLinkedNode post;}
LRU Cache
public class LRUCache {    private Hashtable            cache = new Hashtable();    private int count;    private int capacity;    private DLinkedNode head, tail;    public LRUCache(int capacity) {        this.count = 0;        this.capacity = capacity;        head = new DLinkedNode();        head.pre = null;        tail = new DLinkedNode();        tail.post = null;        head.post = tail;        tail.pre = head;    }    public int get(String key) {        DLinkedNode node = cache.get(key);        if(node == null){            return -1; // should raise exception here.        }        // move the accessed node to the head;        this.moveToHead(node);        return node.value;    }    public void set(String key, int value) {        DLinkedNode node = cache.get(key);        if(node == null){            DLinkedNode newNode = new DLinkedNode();            newNode.key = key;            newNode.value = value;            this.cache.put(key, newNode);            this.addNode(newNode);            ++count;            if(count > capacity){                // pop the tail                DLinkedNode tail = this.popTail();                this.cache.remove(tail.key);                --count;            }        }else{            // update the value.            node.value = value;            this.moveToHead(node);        }    }    /**     * Always add the new node right after head;     */    private void addNode(DLinkedNode node){        node.pre = head;        node.post = head.post;        head.post.pre = node;        head.post = node;    }    /**     * Remove an existing node from the linked list.     */    private void removeNode(DLinkedNode node){        DLinkedNode pre = node.pre;        DLinkedNode post = node.post;        pre.post = post;        post.pre = pre;    }    /**     * Move certain node in between to the head.     */    private void moveToHead(DLinkedNode node){        this.removeNode(node);        this.addNode(node);    }    // pop the current tail.    private DLinkedNode popTail(){        DLinkedNode res = tail.pre;        this.removeNode(res);        return res;    }}
继承LinkedHashMap的简单实现：
LinkedHashMap底层就是用的HashMap加双链表实现的，而且本身已经实现了按照访问顺序的存储。此外，LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。
public class LRUCache<K, V> extends LinkedHashMap<K, V> {    private final int CACHE_SIZE;    // 这里就是传递进来最多能缓存多少数据    public LRUCache(int cacheSize) {        // 设置一个hashmap的初始大小，最后一个true指的是让linkedhashmap按照访问顺序来进行排序，最近访问的放在头，最老访问的就在尾        super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);        CACHE_SIZE = cacheSize;    }    @Override    protected boolean removeEldestEntry(Map.Entry eldest) {        // 当map中的数据量大于指定的缓存个数的时候，就自动删除最老的数据        return size() > CACHE_SIZE;    }}
那么问题的后半部分，是 Redis 如何实现，这个问题这么问肯定是有坑的，那就是redis肯定不是这样实现的。
Redis的LRU实现
如果按照HashMap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以Redis采用了一个近似的做法，就是随机取出若干个key，然后按照访问时间排序后，淘汰掉最不经常使用的，具体分析如下：
为了支持LRU，Redis 2.8.19中使用了一个全局的LRU时钟，server.lruclock，定义如下，
#define REDIS_LRU_BITS 24unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */
默认的LRU时钟的分辨率是1秒，可以通过改变REDIS_LRU_CLOCK_RESOLUTION宏的值来改变，Redis会在serverCron()中调用updateLRUClock定期的更新LRU时钟，更新的频率和hz参数有关，默认为100ms一次，如下，
#define REDIS_LRU_CLOCK_MAX ((1<lru */#define REDIS_LRU_CLOCK_RESOLUTION 1 /* LRU clock resolution in seconds */void updateLRUClock(void) {    server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) &                                                REDIS_LRU_CLOCK_MAX;}
server.unixtime是系统当前的unix时间戳，当 lruclock 的值超出REDIS_LRU_CLOCK_MAX时，会从头开始计算，所以在计算一个key的最长没有访问时间时，可能key本身保存的lru访问时间会比当前的lrulock还要大，这个时候需要计算额外时间，如下，
/* Given an object returns the min number of seconds the object was never * requested, using an approximated LRU algorithm. */unsigned long estimateObjectIdleTime(robj *o) {    if (server.lruclock >= o->lru) {        return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;    } else {        return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) *                    REDIS_LRU_CLOCK_RESOLUTION;    }}
Redis支持和LRU相关淘汰策略包括，
volatile-lru 设置了过期时间的key参与近似的lru淘汰策略
allkeys-lru 所有的key均参与近似的lru淘汰策略
当进行LRU淘汰时，Redis按如下方式进行的，
......            /* volatile-lru and allkeys-lru policy */            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)            {                for (k = 0; k < server.maxmemory_samples; k++) {                    sds thiskey;                    long thisval;                    robj *o;                    de = dictGetRandomKey(dict);                    thiskey = dictGetKey(de);                    /* When policy is volatile-lru we need an additional lookup                     * to locate the real key, as dict is set to db->expires. */                    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)                        de = dictFind(db->dict, thiskey);                    o = dictGetVal(de);                    thisval = estimateObjectIdleTime(o);                    /* Higher idle time is better candidate for deletion */                    if (bestkey == NULL || thisval > bestval) {                        bestkey = thiskey;                        bestval = thisval;                    }                }            }            ......
Redis会基于server.maxmemory_samples配置选取固定数目的key，然后比较它们的lru访问时间，然后淘汰最近最久没有访问的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于严格LRU算法，但是相应消耗也变高，对性能有一定影响，样本值默认为5。
出处：https://www.cnblogs.com/weknow619/p/10730653.html
	

操作系统
 相关代码：https://github.com/zhuzhenxxx/ostep-code
介绍
第一部分 虚拟化
1.抽象：进程
抽象：进程
进程API
进程创建：更多细节
进程状态
数据结构
小结
2.插叙：进程API
fork()系统调用
wait()系统调用
exec()系统调用
小结
3. 机制：受限直接执行
基本技巧
问题1：受限制的操作
问题2：在进程间切换
小结
4.进程调度
调度指标
先进先出（FIFO）
最短任务优先（SJF）
最短完成时间优先（STCF）
新度量指标：响应时间
轮转
结合I/O
无法预知
小结
5.多级反馈队列
MLFQ：基本规则
尝试1：如何改变优先级
尝试2：提升优先级
尝试3：更好的计时方式
MLFQ调优及其他问题
小结
6.比例份额
基本概念：彩票数表示份额
彩票机制
实现
一个例子
如何分配彩票
为什么不是确定的
小结
7.多处理器调度（高度）
背景：多处理器架构
别忘了同步
最后一个问题：缓存亲和度
单队列调度
多队列调度
Linux多处理器调度
小结
8.抽象：地址空间
早起系统
多道程序和时分共享
地址空间
目标
小结
9.插叙：内存操作API
内存类型
malloc()调用
free() 调用
常见错误
底层操作系统支持
调用其他
小结
10.机制：地址转换
假设
例子
动态（基于硬件）重定位
硬件支持：总结
操作系统的问题
小结
11.分段
分段：泛化的基址/接线
我们引用哪个段
栈怎么办
支持共享
细粒度与粗粒度的分段
操作系统支持
小结
12.空闲空间管理
假设
底层机制
基本策略
其他方式
小结
13.分页：介绍
例子
页表存在哪里
页表中有什么
分页也很慢
内存追踪
小结
14.分页：快速地址转换（TLB）
TLB的基本算法
示例：访问数组
谁来处理TLB未命中
TLB的内容
上下文切换时对TLB的处理
TLB替换策略
实际系统的TLB表项
小结
15.分页：较小的表
简单的解决方案：更大的页
混合方法：分段和分页
多级页表
反向页表
将页表交换到磁盘
小结
16.超越物理内存：机制
交换空间
存在位
页错误
页存满了怎么办
页错误处理流程
交换何时真正发生
小结
17.超越物理内存：策略
缓存管理
最优替换策略
简单策略：FIFO
另一简单策略：随机
利用历史数据：LRU
工作负载示例
基于历史信息的算法
近似LRU
考虑脏页
其他虚拟内存策略
抖动
小结
18.VAX/VMS虚拟内存系统
背景
内存管理硬件
一个真实的地址空间
也替换
其他漂亮的虚拟内存技巧
小结
并发
1.并发：介绍
实例：线程创建
为什么更糟糕：共享数据
核心问题：不可控的调度
原子性愿望
等待另一个线程
小结：操作系统为什么要研究并发
小结
2.插叙：线程API
线程创建
线程完成
锁
条件变量
编译和运行
小结
3.锁
锁的基本思想
Pthread锁
实现一个锁
评价锁
控制中断
测试并设置指令（原子交换）
实现可用的自旋锁
评价自旋锁
比较并交换
链接的加载和条件式存储指令
获取并增加
自旋过多怎么办
简单方法：让我出来吧，宝贝
使用队列：休眠替代自旋
不同操作系统，不同实现
两阶段锁
小结
4.基于锁的并发数据结构
并发计数器
并发链表
并发队列
并发散列表
小结
5.条件变量
定义和程序
生产者/消费者问题（有界缓冲区）
覆盖条件
小结
6.信号量
信号量的定义
二值信号量（锁）
信号量作为条件变量
生产者/消费者（有界缓冲区）
读者-写者锁
哲学家就餐问题
如何实现信号量
小结
7.常见并发问题
有哪些类型的缺陷
非死锁缺陷
死锁缺陷
小结
8.基于事件的并发（进阶）
基本想法：事件循环
重要API：select()、poll
使用select
为何更简单？无须锁
一个问题：阻塞系统调用
解决方案：异步I/O
另一个问题：状态管理
什么事情仍然很难
小结
持久性
1.I/O设备
系统架构
标准设备
标准协议
利用中断建设CPU开销
利用DMA进行更高效的数据传送
设备交互的方法
纳入操作系统：设备驱动程序
案例研究：简单的IDE磁盘驱动程序
历史记录
小结
2.磁盘驱动器
接口
基本几何形状
简单的磁盘驱动器
I/O时间：用数学
磁盘调度
小结
3.廉价冗余磁盘阵列（RAID）
接口和RAID内部
故障模型
如何评估RAID
RAID 0级：条带化
RAID 1级：镜像
RAID 4级：通过奇偶校验节省空间
RAID 5级：旋转奇偶校验
其他有趣的RAID问题
小结
4.插叙：文件和目录
文件和目录
文件系统接口
创建文件
读写文件
读取和写入，但不按顺序
用fsync()立即写入
文件重命名
获取文件信息
删除文件
创建目录
删除目录
硬链接
符号链接
创建并挂载文件系统
小结
5.文件系统的实现
思考方式
整体组织
文件组织：inode
目录组织
空闲空间管理
访问路径：读取和写入
缓存和缓冲
小结
6.局部性和快速文件系统
问题：性能不佳
FFS：磁盘意识是解决方案
组织结构：柱面组
策略：如何分配文件和目录
测量文件的局部性
大文件例外
关于FFS的其他几件事
小结
7.崩溃一致性：FSCK和日志
例子
解决方案1.文件系统检查程序
解决方案2.日志 或 预写日志
解决方案3.其他方法
小结
8.日志结构文件系统
按顺序写入磁盘
顺序而高效的写入
要缓冲多少
问题:查找inode
通过间接解决方案：inode映射
检查点区域
从磁盘读取文件：回顾
目录如何
一个新问题：垃圾收集
确定块的死活
策略问题：要清理哪些块，何时清理
崩溃恢复和日志
小结
9.数据完整性和保护
磁盘故障模式
处理潜在的扇区错误
检测讹误：校验和
使用校验和
一个新问题：错误的写入
最后一个问题：丢失的写入
擦净
检验和的开学
小结
10.分布式系统
通信基础
不可靠的通信层
可靠的通信层
通信抽象
远程过程调用RPC
小结
11.Sun的网络文件系统（NFS）
基本的分布式文件系统
交出NFS
关注点：简单快速的服务器崩溃恢复
快速崩溃恢复的关键：无状态
NFSv2协议
从协议到分布式文件系统
利用幂等操作处理服务器故障
提高性能：客户端缓存
缓存一致性问题
评估NFS的缓存一致性
服务器端写缓存的隐含意义
小结
12.Andrew文件系统（AFS）
AFS版本1
版本1的问题
改进协议
AFS版本2
缓存一致性
崩溃恢复
AFSv2的性能扩展性和性能
其他改进
小结
实验

	

题目：LRU(Least Recently Used)：最近最少使用，最近最久未使用，是操作系统常用的，是操作系统常用的一种页面置换算法，选择最近最久未使用的页面予以淘汰
运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用)缓存机制，它应该支持以下操作：获取数据get和写入数据put
获取数据get(key)，如果密钥(key)存在于缓存中，则获取密钥的值(总是正数)，否则返回-1
写入数据put(key,value)，如果密钥不存在，则写入其数据值，当缓存容量达到上限时，他应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间
进阶：你是否可以在O(1)时间复杂度内完成这两种操作
LRUCache cache = new LRUCache(2//缓存容量)
cache.put(1,1);
cache.put(2,2);
cache.get(1); //返回1
cache.put(3,3); //该操作会使密钥2作废
cache.get(2)；//返回-1(未找到)
cache.put(4,4); //该操作会使密钥1作废
cache.get(1)；//返回-1(未找到)
cache.get(3)；//返回3
cache.get(4)；//返回4
LRUCache的常见实现方式是：哈希表+双向链表思路：LRUCache的设计
代码
 1public class LRUCache {
 2    private Map map; 3    private int capacity; 4    // 虚拟头结点 5    private Node first; 6    // 虚拟尾结点 7    private Node last; 8 9    public LRUCache(int capacity) {10        map = new HashMap<>(capacity);11        this.capacity = capacity;12        first = new Node();13        last = new Node();14        first.next = last;15        last.prev = first;16    }1718    public int get(int key) {19        Node node = map.get(key);20        if (node == null) return -1;2122        removeNode(node);23        addAfterFirst(node);2425        return node.value;26    }2728    /**29     * @param node 将node节点插入到first节点的后面30     */31    private void addAfterFirst(Node node) {32        // node与first.next33        node.next = first.next;34        first.next.prev = node;3536        // node与first37        first.next = node;38        node.prev = first;39    }4041    /**42     * @param node 从双向链表中删除node节点43     */44    private void removeNode(Node node) {45        node.next.prev = node.prev;46        node.prev.next = node.next;47    }4849    public void put(int key, int value) {50        Node node = map.get(key);51        if (node != null) {52            node.value = value;53            removeNode(node);54        } else { // 添加一对新的key-value55            if (map.size() == capacity) {56                // 淘汰最近最少使用的node\57                removeNode(map.remove(last.prev.key));58//                map.remove(last.prev.key);59//                removeNode(last.prev);60            }61            map.put(key, node = new Node(key, value));62        }63        addAfterFirst(node);64    }6566    private static class Node {67        public int key;68        public int value;69        public Node prev;70        public Node next;7172        public Node(int key, int value) {73            this.key = key;74            this.value = value;75        }7677        public Node() {78        }79    }80}