Linux内存管理：(六)页交换算法

文章说明：

Linux内核版本：5.0
架构：ARM64
参考资料及图片来源：《奔跑吧Linux内核》
Linux 5.0内核源码注释仓库地址：

zhangzihengya/LinuxSourceCode_v5.0_study (github.com)

1. 引言

在Linux操作系统中，当内存充足时，内核会尽量多地使用内存作为文件缓存（page cache），从而提高系统的性能。文件缓存页面会添加到文件类型的LRU链表中；当内存紧张时，文件缓存页面会被丢弃，或者把修改的文件缓存页面回写到存储设备中，与块设备同步之后便可释放出物理内存。现在的应用程序转向内存密集型，无论系统中有多少物理内存都是不够用的，因此Linux操作系统会使用存储设备作为交换分区，内核将很少使用的内存换出到交换分区，以便释放出物理内存，这个机制称为页交换（swapping），这些处理机制统称为页面回收（page reclaim）。

在最近几十年操作系统的发展过程中，出现了很多页面交换算法，其中每个算法都有各自的优点和缺点。Linux内核中采用的页交换算法主要是经典LRU链表算法和第二次机会（second chance）法。

2. 经典LRU链表算法

LRU是Least Recently Used的缩写，意为最近最少使用。根据局部性原理，LRU假定最近不使用的页面在较短的时间内也不会频繁使用。在内存不足时，这些页面将成为被换出的候选者。内核使用双向链表来定义LRU链表，并且根据页面的类型将LRU链表分为LRU_ANON和LRU_FILE。每种类型根据页面的活跃性分为活跃LRU链表和不活跃LRU链表，所以内核中一共有如下5个LRU链表：

// 定义了各种 LRU 链表的类型
enum lru_list {
	// 不活跃匿名页面链表
    LRU_INACTIVE_ANON = LRU_BASE,
    // 活跃匿名页面链表
	LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
    // 不活跃文件映射页面链表
	LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
    // 活跃文件映射页面链表
	LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
    // 不可回收页面链表
	LRU_UNEVICTABLE,
	NR_LRU_LISTS
};

LRU链表之所以要分成这样，是因为当内存紧缺时总是优先换出文件映射的文件缓存页面（LRU_FILE链表中的页面），而不是匿名页面。因为大多数情况下，文件缓存页面不需要被回写到磁盘，除非页面内容修改了（称为脏页），而匿名页面总是要在写入交换分区之后，才能被换出。LRU链表按照内存节点配置，也就是说，每个内存节点中都有一整套LRU链表，因此内存节点的描述符数据结构（pglist_data）中有一个成员lruvec指向这些链表。枚举类型变量lru_list 列举出上述各种LRU链表的类型，lruvec数据结构中定义了上述各种LRU类型的链表：

// 定义了各种 LRU 链表
struct lruvec {
	struct list_head		lists[NR_LRU_LISTS];
	...
};

// 内存节点的数据结构
typedef struct pglist_data {
	// 每个内存节点中都有一整套 LRU 链表，由 lruvec 指向
	struct lruvec		lruvec;
} pg_data_t;

万事从图说起，经典LRU链表算法如下图所示：

在这里插入图片描述

为了使读者有更真切的理解，下文将根据流程图围绕源代码进行讲解这个过程：

将页面加入 LRU 链表：

static void __lru_cache_add(struct page *page)
{
	// 这里使用了页向量数据结构，借助一个数组来保存特定数目的页，可以对这些页面执行同样的操作
	// 页向量会以“批处理的方式”执行，比单独处理一个页面的方式效率要高
	struct pagevec *pvec = &get_cpu_var(lru_add_pvec);

	get_page(page);
	// pagevec_add() 函数首先往 pvec->pages[] 数组里添加页面，
	// 如果没有空间了，则调用 __pagevec_lru_add() 函数把原有的页面添加到 LRU 链表中
	if (!pagevec_add(pvec, page) || PageCompound(page))
		__pagevec_lru_add(pvec);
	put_cpu_var(lru_add_pvec);
}

void lru_cache_add(struct page *page)
{
	...
	__lru_cache_add(page);
}

lru_to_page(&lru_list)和list_del(&page->lru)函数的组合用于从LRU链表中获取页面。其中，lru_to_page()的实现如下：

#define lru_to_page(head) (list_entry((head)->prev, struct page, lru))

lru_to_page()使用了(head)->prev，表示从链表的末尾获取页面。因此，LRU链表实现了 FIFO算法。最先进入LRU链表的页面在LRU中的时间会越长，老化时间也越长。

在系统执行过程中，页面总是在活跃LRU链表和不活跃LRU链表之间转移，不是每次访问内存页面都会发生这种转移，而是发生的时间间隔比较长。随着时间的推移，这会导致—种热平衡，最不常用的页面将慢慢移动到不活跃LRU链表的末尾，这些页面正是页面回收中最合适的候选者。

3. 第二次机会法

当系统内存短缺时，LRU链表尾部的页面将会离开并被换出。当系统再需要这些页面时，这些页面会重新置于LRU链表的开头。显然，这个设计不是很巧妙，在换出页面时，没有考虑该页面是频繁使用的，还是很少使用的。也就是说，频繁使用的页面依然会因为在LRU链表末尾而被换出。

第二次机会法的改进是为了避免把经常使用的页面置换出去，设置了一个访问状态位（硬件控制的位，PTE_YOUNG），所以要检查页面的访问位。如果访问位是0，就淘汰这个页面；如果访问位是1，就给它第二次机会，并选择下一个页面来换出。当该页面得到第二次机会时，它的访问位被清零，如果该页面在此期间再次被访问过，则访问位设置为1。

Linux内核使用下面这两个标志位来是实现第二次机会法：

PG_active：表示该页面是否活跃
PG_referenced：表示该页面是否被引用过

mark_page_accessed() 函数将页面标记为活跃：

如果 PG_active==0 && PG_referenced==1，则把该页面加入活跃LRU链表，并设置 PG_active=1，清除PG_reference 标志位
如果 PG_active==0，则设置 PG_referenced 标志位

在扫描不活跃 LRU 链表时，page_check_references() 这个函数会被调用：

// page 表示要处理的物理页面的page数据结构
// sc 表示内部用来控制页面扫描的数据结构
static enum page_references page_check_references(struct page *page,
						  struct scan_control *sc)
{
	...

	// page_referenced() 检查该页面访问、引用了多少个PTE（referenced_ptes）
	referenced_ptes = page_referenced(page, 1, sc->target_mem_cgroup,
					  &vm_flags);
	// TestClearPageReferenced() 函数返回该页面 PG_referenced 标志位的值（referenced_page），并且清除该标志
	referenced_page = TestClearPageReferenced(page);

	...

	if (referenced_ptes) {
		...
		// 在内存短缺的情况下，kswapd 巧妙地释放了短时间内只访问一次的大量文件缓存
		SetPageReferenced(page);

		// referenced_ptes > 1 表示那些第一次在不活跃LRU链表中的共享文件映射页面（共享文件缓存），
		// 它们应该晋升到活跃 LRU 链表中，因为它们应该在活跃 LRU 链表中多待一段时间，以便其他用户可以再次访问到。
		if (referenced_page || referenced_ptes > 1)
			return PAGEREF_ACTIVATE;

		...
	}

	...
}

page_referenced() 函数用于判断页面是否被访问过，并返回引用的PTE的个数，即访问引用这个页面的用户进程空间虚拟页面的个数，核心思想是利用 RMAP 系统来统计访问、引用 PTE 的用户个数：

int page_referenced(struct page *page,
		    int is_locked,
		    struct mem_cgroup *memcg,
		    unsigned long *vm_flags)
{
	...
	// 定义 rmap_one() 函数的指针
	struct rmap_walk_control rwc = {
		.rmap_one = page_referenced_one,
		.arg = (void *)&pra,
		.anon_lock = page_lock_anon_vma_read,
	};

	*vm_flags = 0;
	// 判断 page->_mapcount 是否大于或等于 0
	if (!page_mapped(page))
		return 0;

	// 判断 page->mapping 是否有地址空间映射
	if (!page_rmapping(page))
		return 0;

	...

	// 遍历所有映射该页面的 PTE
	rmap_walk(page, &rwc);
	*vm_flags = pra.vm_flags;

	...

	return pra.referenced;
}