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

2024-01-08 19:10:19

文章说明:

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;
}

文章来源:https://blog.csdn.net/qq_58538265/article/details/135396755
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。