Day18 page fault, LRU, second chance

前言

前几天我们讲到的都是关於虚拟记忆体的资讯，包含VMA的结构，malloc() , mmap() 等等，但是究竟虚拟记忆体该如何跟实体记忆体有实际的连结，怎麽在 mmap() 之後，让实体记忆体能够拿到资料，那就是今天要讲的内容 分页错误(page fault) ，以及当实体记忆体的位置不足时，要选择某些分页移回 swap space的方法。

分页错误(page fault)

在前两天借到 malloc() 与 mmap() 两个函数，他们只会在使用者空间内分配虚拟记忆体，但是没有实际建立虚拟记忆体与实体记忆体的映射关系，当CPU没有办法存取实体记忆体的时候就会发生分页错误(page fault)。
触发 Page Fault 的原因主要归类为几大类：

1. 使用共享记忆体的区域，但是还不存在虚拟位址与实体位址的对应，而产生的分页错误，这种错误只要在分页表中建立对应关系就好了。
2. 访问的地址在实体记忆体中不存在，需要从硬碟或是 swap分割槽读入才能使用，这种效能影响比较大，因为磁碟读取的速度真的太慢了。
3. 访问的记忆体位址非法，缺页错误会进而引发 SIGSEGN 讯号结束程序，这种分页错误会导致行程直接关闭。
   在 Linux 中会利用 do_page_fault 函数进行处理。

static int __kprobes do_page_fault(unsigned long addr, unsigned int esr,
				   struct pt_regs *regs)

addr : 代表分页异常发生时的虚拟位址，由FSR提供
esr ：代表发生时的异常状态，由ESR提供
regs：发生时的pt_regs。

记忆体回收

在Linux 中当记忆体充足的时候，kernel会尽量使用记忆体当作 page cache，进而提高系统的性能，这个页面会加入到文件类型的 LRU链表中，当记忆体不足时，page cache的介面会被舍际，或是把已经丢改过的page cache介面写回到储存设备中，写完便可释放该区段的记忆体，这个行为叫做记忆体回收(page reclaim)。Linux 中采用的记忆体回收演算法，主要是LRU演算法，和二次机会法(second chance)。

LRU演算法

LRU 是 Least Recently Used 的缩写，意味着最近最少使用，在Linux核心中使用双项链表实作LRU链表，并且根据分页的类型将LRU链表分为 LRU_ANON 和 LRU_FILE ，这两种列表又各自有活跃LRU链表与不活跃LRU链表，再加上不可回收页面链表，所以Linux核心中总共有五个LRU链表。
之所以要分为五种，是因为当记忆体不足时，会优先换出LRU_FILE链表中的页面，而不是 LRU_ANON的页面，因为大多数情况下的FILE是不需要写回硬碟，除非在使用过程中有某部分被修改才需要重新写回。
因为是一个双向链表，所以可以利用 head-> prev得到尾链表最尾端的node。示意图如下。

二次演算法

第二次机会演算法在经典的LRU上做了改进，在LRU设计中，并不会考虑该页面是否频繁被使用，如果某个频繁使用的页面，因为有多个新页面进入而被挤到链表的最尾端，他仍然有机会被换出，在某些情况下，会浪费许多的资源。
二次机会演算法是基於LRU演算法的状态下，在页面内多加入一个标记，如果这个是０代表这个页面是可以被替换的，如果这个页面是1 就给他第二次机会，并且判断下一个页面是否能够被换出，依序往下，直到找到可以被换出的页面。当给了某个页面第二次机会时，该标记会由1改为0；当某个页面再次被使用时，把0恢复为1，因此某个频繁被使用的页面他的标记会时常保持为1，也就不那麽容易被换出了。

OOM killer 机制

当上述两个回收机制也不能满足记忆体需求时，OOM killer就是最後一道防线了，他会选择记忆体占用量比较高的行程进行终止，进而释放记忆体。