页框回收算法：阐述了内核回收页框的原因与策略。
反向映射：技术补充，介绍了内核使用的一种数据结构，借助该结构，内核可快速定位指向同一个页框的所有页表项。
PFRA实现：介绍 Linux 使用的页框回收算法。
交换：讲述了交换子系统，它将匿名页（并非文件的映射数据）保存到磁盘的内核部件。

页框回收算法

Linux 内核的页框回收算法（page frame reclaiming algorithm, PFRA）采取从用户态进程和内核高速缓存“窃取”页框的办法补充伙伴系统的空闲块列表。

页框回收算法的目标之一就是保存最少的空闲页框池以便内核可以安全地从“内存紧缺”的情形中恢复过来。

选择目标页

PFRA 的目标是获得页框并使之空闲。

PFRA 按照页框所含的内容，以不同的方式处理页框：

PFRA 设计

确定回收内存的候选页可能是内核设计中最精巧的问题，需要同时满足系统响应和对内存需求量大的要求。

PFRA 采用的几个总的原则：

• 首先释放“无害”页。先回收没有被任何进程使用的磁盘与内存高速缓存中的页，不需要修改任何页表项。
• 将用户态进程的所有页定为可回收页。除了锁定页，PFRA 必须能窃得任何用户态进程页，包括匿名页。这样，睡眠时间较长的进程将逐渐失去所有页框。
• 同时取消引用一个共享页框的所有页表项的映射，清空引用该页框的所有页表项，就可以回收该共享页框。
• 只回收“未用”页。使用简化的最近最少使用（LRU）置换算法，PFRA 将页分为“在用”与“未用”。如果某页很长时间没有被访问，那么它将来被访问的可能性较小，可被看作未用；另一方面，如果某页最近被访问过，那么它将来被访问的可能性较大，被看作在用。PFRA 只回收未用页。

LRU 算法的主要思想是用一个计数器来存放 RAM 中每一页的页年龄，即上次访问该页到现在已经过去的时间，PFRA 只回收任何进程的最旧页。
但 Linux 内核没有计数器这样的硬件，而是使用每个页表项中的访问标志位，在页被访问时，该标志位由硬件自动置位；而且，页年龄由页描述符在链表中的位置表示。

页框回收算法是几种启发式方法的混合：

• 谨慎选择检查高速缓存的顺序。
• 基于页年龄的变化排序。
• 区别对待不同状态的页。

反向映射

PFRA 的目标之一是能释放共享页框。为此，Linux 2.6 要能快速定位指向同一页框的所有页表项，该过程为反向映射。

反向映射解决的简单方式是在页描述符中引入附加字段，从而将某页描述符所确定的页框中对应的所有页表项连接起来。
为方便更新该链表，Linux 2.6 采用”面向对象的反向映射“技术。
对任何可回收的用户态页，内核保留系统中该页所在所有线性区（”对象“）的反向链接，每个线性区描述符存放一个指向一个描述符的指针，而该内存描述符又包含一个指向一个页全局目录的指针。
因此，这些反向链接使得 PFRA 能够检索引用某页的所有页表项。
因为线性区描述符比页描述符少，所以更新共享页的反向链接就比较省时间。

首先，PFRA 必须要确定待回收页是共享的或非共享的，以及是映射页或匿名页。
为此，内核要查看页描述符的两个字段：_mapcount 和 mapping。

_mapcount 字段存放引用页框的页表项数目。
初值为 -1，表示没有页表项引用该页框；如果为 0，表示页是非共享的；如果大于 0，表示页是共享的。
page_mapcount 函数接收页描述符地址，返回值为 _mapcount + 1（这样，如果返回值为 1，表明是某个进程的用户态地址控件存放的一个非共享页）。

mapping 字段用于确定页是映射的或匿名映射的。

• 如果 mapping 字段空，则该页属于交换高速缓存。
• 如果 mapping 字段非空，且最低位是 1，表示该页是匿名页；同时 mapping 字段中存放指向 anon_vma 描述符的指针。
• 如果 mapping 字段非空，且最低位是 0，表示该页是映射页；同时 mapping 字段指向对应文件的 address_space 对象。

Linux 的 address_space 对象在 RAM 中是对齐的，所以其起始地址是 4 的倍数。
因此其 mapping 字段的最低位可以用一个标志位来表示该字段的指针是指向 address_space 对象还是 anon_vma 描述符。
PageAnon() 参数为页描述符，如果 mapping 字段的最低位置位，则函数返回 1；否则返回 0。

try_to_unmap() 参数为页描述符指针，它尝试清空所有引用该页描述符对应页框的页表项。
如果从页表项中成功清除所有对该页框的应用，函数返回 SWAP_SUCCESS(0)；否则返回 SWAP_AGAIN(1)；出错返回 SWAP_FAIL(2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
1int try_to_unmap(struct page *page)

2{

3   int ret;

4   if(PageAnon(page))  // mapping 字段指向 aon_vma

5       ret = try_to_unmap_anon(page);  // 清空对页框的引用，处理匿名页

6   else  // mapping 字段指向 address_space

7       ret = try_to_unmap_file(page);   // 清空对页框的引用，处理映射页

8   if(!page_mapped(page))

9       ret = SWAP_SUCCESS;

10  return ret;

11}

12

13

匿名页的反向映射

匿名页经常由几个进程共享。
最常见的情形：创建新进程，父进程的所有页框，包括匿名页，同时也分配给子进程。
另外（不常见），进程创建线性区时使用两个标志 MAP_ANONYMOUS 和 MAP_SHARED，表明这个区域内的也将由该进程后面的子进程共享。

将引用同一页框的所有匿名页链接起来的策略：将该页框所在的匿名线性区存放在一个双向循环链表中。
注意：即使一个匿名线性区存有不同的页，也始终只有一个反向映射链表用于该区域中的所有页框。

当为一个匿名线性区分配第一页时，内核创建一个新的 anon_vma 数据结构，它只有两个字段：

• lock，竞争条件下保护链表的自旋锁。
• head，线性区描述符双向循环链表的头部。

然后，内核将匿名线性区的 vm_area_struct 描述符插入 anon_vma 链表。vm_area_struct 中对应链表的两个字段：

• anon_vma_node，存放指向链表中前一个和后一个元素的指针。
• anon_vma，指向 anon_vma 数据结构。

最后，内核将 anon_vma 数据结构的地址存放在匿名页描述符的 mapping 字段。

当已被一个进程引用的页框插入另一个进程的页表项时（如调用 fork() 时），内核只是将第二个进程的匿名线性区插入 anon_vma 数据结构的双向循环链表，而第一个进程线性区的 anon_vma 字段指向该 anon_vma 数据结构。
因此，每个 anon_vma 链表通常包含不同进程的线性区。

借助 anon_vma 链表，内核可快速定位引用同一匿名页框的所有页表项。
每个区域描述符在 vm_mm 字段中存放内存描述符地址，而该内存描述符又有一个 pgd 字段，其中存有进程的页全局目录。
这样，页表项就可以从匿名页的起始线性地址得到，该线性地址可以由线性区描述符及页描述符的 index 字段得到。

try_to_unmap_anon()

当回收匿名页框时，PFRA 必须扫描 anon_vma 链表中的所有线性区，检查是否每个区域都存有一个匿名页，而其对应的页框就是目标页框。
该工作通过 try_to_unmap_anon() 实现，参数为目标页框描述符，步骤：

1. 获得 anon_vma 数据结构的自旋锁，页描述符的 mapping 字段指向该数据结构。
2. 扫描线性区描述符的 anon_vma 链表。

对该链表中的每个 vma 线性区描述符调用 try_to_unmap_one()，参数为 vma 和页描述符。
如果返回 SWAP_FAIL，或如果页描述符的 _mapcount 字段表明已找到所有引用该页框的页表项，停止扫描。

1. 释放第 1 步得到的自旋锁。
2. 返回最后调用 try_to_unmap_one() 得到的值：SWAP_AGAIN（部分成功）或 SWAP_FAIL（失败）。

try_to_unmap_one()

被 try_to_unmap_anon() 和 try_to_unmap_file() 调用。

参数：

• page，指向目标页描述符的指针。
• vma，指向线性区描述符的指针。

1. 计算出待回收页的线性地址。

参数：线性区的起始线性地址（vma->vm_start）、被映射文件的线性区偏移量（vm->vm_pgoff）和被映射文件内的页偏移量（page->index)。
对于匿名页，vma->vm_pgoff 字段是 0 或者 vm_start/PAGE_SIZE；
page->index 字段是区域内的页索引或页的线性地址除以 PAGE_SIZE。

1. 如果目标页是匿名页，则检查页的线性地址是否在线性区内。如果不是，则结束并返回 SWAP_AGAIN。
2. 从 vma->vm_mm 得到内存描述符地址，并获得保护页表的自旋锁 vma->vm_mm->page_table_lock。
3. 成功调用 pgd_offset()、pud_offset()、pmd_offset() 和 pte_offset_map() 以获得对应目标页线性地址的页表项地址。
4. 执行一些检查来验证目标页可有效回收。

以下检查中，如果任何一项失败，跳到第 12 步，结束并返回一个有关的错误码：SWAP_AGAIN 或 SWAP_FAIL。
a. 检查指向目标页的页表项，失败时返回 SWAP_AGAIN，可能失败的情形：

• 指向页框的页表项与 COW 关联，而 vma 标识的匿名线性地址仍然属于原页框的 anon_vma 链表。
• mremap() 可重新映射线性区，并通过直接修改页表项将页移到用户态地址空间。这种特殊情况下，因为页描述符的 index 字段不能用于确定页的实际线性地址，所以面向对象的反向映射不能使用了。
• 文件内存映射是非线性的。

b. 验证线性区不是锁定（VM_LOCKED）或保留（VM_RESERVED）的。如果有锁定（VM_LOCKED）或保留情况之一出现，就返回 SWAP_FAIL。
c. 验证页表项中的访问标志位被清 0。如果没有，将它清 0，并返回 SWAP_FAIL。访问标志置位表示页在用，因此不能被回收。
d. 检查页是否始于交换高速缓存，此时它正由 get_user_pages() 处理。在这种情形下，为避免恶性竞争条件，返回 SWAP_FAIL。

1. 页可以被回收。如果页表项的 Dirty 标志置位，则将页的 PG_dirty 标志置位。
2. 清空页表项，刷新相应的 TLB。
3. 如果是匿名页，将换出页标识符插入页表项，以便将来访问时将该页换入。而且，递减存放在内存描述符 anon_rss 字段中的匿名页计数器。
4. 递减存放在内存描述符 rss 字段中的页框计数器。
5. 递减页描述符的 _mapcount 字段，因为对用户态页表项中页框的引用已被删除。
6. 递减存放在页描述符 _count 字段中的页框使用计数器。如果计数器变为负数，则从活动或非活动链表中删除页描述符，且调用 free_hot_page() 释放页框。
7. 调用 pte_unmap() 释放临时内核映射，因为第 4 步中的 pte_offset_map() 可能分配了一个这样的映射。
8. 释放第 3 步中获得的自旋锁 vma->vm_mm->page_table_lock。
9. 返回相应的错误码（成功时返回 SWAP_AGAIN）。

映射页的反向映射

映射页的面向对象对象反向映射所基于的思想：总是可以获得指向一个给定页框的页表项，方式就是访问相应映射页所在的线性区描述符。
因此，反向映射的关键是一个精巧的数据结构，该数据结构可存放与给定页框有关的所有线性区描述符。

与匿名页相反，映射页经常是共享的，因为不同的进程常会共享同一个程序代码。
因此，Linux 2.6 采用”优先搜索树“的结构快速定义引用同一页框的所有线性区。

每个文件对应一个优先搜索树。
它存放在 address_space 对象的 i_mmap 字段，该对象包含在文件的索引节点对象中。
因为映射页描述符的 mapping 字段指向 address_space 对象，所以总能快速检索搜索树的根。

优先搜索树 PST

PST 用于表示一组相互重叠的区间。
PST 的每个区间相当于一个树的节点，由基索引和堆索引两个索引标识。
基索引表示区间的起始点，堆索引表示终点。
PST 实际上是一个依赖于基索引的搜索树，并附加一个类堆属性，即一个节点的堆索引不会小于其子节点的堆索引。

Linux 中的 PST 的不同之处：不对称；被修改程存放线性区而不是线性区间。
每个线性区可被看作是文件页的一个区间，并由在文件中的起始位置（基索引）和终点位置（堆索引）所确定。
但是，线性区通常是从同一页开始，为此，PST 的每个节点还附带一个大小索引，值为线性区大小（页数）减 1。
该大小索引使搜索程序能区分同一起始文件位置的不同线性区。

但大小索引会大大增加不同的节点数，会使 PST 溢出。
为此，PST 可以包括溢出子树，该子树以 PST 的叶为根，且包含具有相同基索引的节点。

此外，不同进程拥有的线性区可能是映射了相同文件的相同部分。
当必须在 PST 中插入一个与现存某个节点具有相同索引值的线性区时，内核将该线性区描述符插入一个以原 PST 节点为根的双向循环列表。

讨论由 prio_tree_node 数据结构表示的一个 PST 节点。该数据结构在每个线性区描述符的 shared.prio_tree_node 字段中。
shared.vm_set 数据结构作为 shared.prio_tree_node 的替代品，可将线性区描述符插入一个 PST 节点的链表副本。
可用 vma_prio_tree_insert() 和 vma_prio_tree_remove() 分别插入和删除 PST 节点。
两个函数的参数都是线性区描述符地址与 PST 根地址。
对 PST 的搜索可调用 vma_prio_tree_foreach 宏实现，该宏循环搜索所有线性区描述符，这些描述符在给定范围的线性地址中包含至少一页。

try_to_unmap_file()

被 try_to_unmap() 调用，指向映射页的反向映射。

1. 获得 page->mapping->i_mmap_lock 自旋锁。
2. 对搜索树应用 vma_prio_tree_foreach() 宏，搜索树的根存放在 page->mapping->i_mmap 字段。

对宏发现的每个 vm_area_struct 描述符，调用 try_to_unmap_one() 对该页所在的线性区页表项清 0。
失败时返回 SWAP_FAIL，或者如果页描述符的 _mapcount 字段表明引用该页框的所有页表项都已找到，则搜索过程结束。

1. 释放 page->mapping->i_mmap_lock 自旋锁。
2. 根据所有的页表项清 0 与否，返回 SWAP_AGAIN 或 SWAP_FAIL。

如果映射是非线性的，则 try_to_unmap_one() 可能无法清 0 某些页表项，因为页描述符的 index 不再对应线性区中的页位置，try_to_unmap_one() 就无法确定页的线性地址，也就无法得到页表项地址。

唯一的解决方法是对文件非线性区的穷尽搜索。
双向链表以文件的所有非线性区的描述符所在的 page->mapping 文件的 address_space 对象的 i_mmap_nonlinear 字段为根。
对每个这样的线性区，try_to_unmap_file() 调用 try_to_unmap_cluster() 扫描该线性区地址所对应的所有页表项，并尝试将它们清 0。

因为搜索可能很费时，所以执行有限扫描，而且通过试探法决定扫描线性区的哪一部分，vma_area_struct 描述符的 vm_private_data 字段存有当前扫描的指针。
因此 try_to_unmap_fie() 在某些清空下可能会找不到待停止映射的页，这时，try_to_umap() 发现页仍然是映射的，则返回 SWAP_AGAIN，而不是 SWAP_SUCCESS。

PFRA 实现

页框回收算法必须处理多种属于用户态进程、磁盘高速缓存和内存高速缓存的页，且必须遵照几条试探法则，函数较多。

PFRA 有几个入口。实际上，页框回收算法的执行有三种基本情形：

• 内存紧缺回收，内核发现内存紧缺。
• 睡眠回收，在进入 suspend_to_disk 状态时，内核必须释放内存。
• 周期回收，必要时，周期性激活内核线程执行内存回收算法。

内存紧缺回收激活情形：

• grow_buffers() 无法获得新的缓冲区页。
• alloc_page_buffers() 无法获得页临时缓冲区首部。
• __alloc_pages() 无法在给定的内存管理区中分配一组连续页框。

周期回收由两种不同的内核线程激活：

• kswapd 内核线程，它检查某个内存管理区中空闲页框数是否已低于 pages_high 值。
• events 内核线程，它是预定义工作队列的工作者线程；PFRA 周期性地调度预定义工作队列中的一个任务执行，从而回收 slab 分配器处理的位于内存高速缓存中的所有空闲 slab。

最近最少使用（LRU）链表

属于进程用户态地址和空间或页高速缓存的所有页被分成两组：活动链表和非活动链表，它们被统称为 LRU 链表。
活动链表存放最近被访问过的页；非活动链表存放有一段时间没有被访问过的页。
显然，页必须从非活动链表窃取。

两个双向链表的头分别存放在每个 zone 描述符的 active_list 和 inactive_list 字段，nr_active 和 nr_inactive 字段表示存放在两个链表中的页数。
lru_lock 字段是一个自旋锁，保护两个链表免受 SMP 系统上的并发访问。

如果页属于 LRU 链表，则设置页描述符的 PG_lru 标志。
如果页属于活动链表，则设置 PG_active 标志，如果页属于非活动链表，则清 PG_active 标志。
页描述符的 lru 字段存放指向 LRU 链表中下一个元素和前一个元素的指针。

在 LRU 链表之间移动页

页描述符的 PG_referenced 标志把一个页从非活动链表移到活动链表所需的访问次数加倍；
也把一个页从活动链表移到非活动链表所需的“丢失访问”次数加倍。
如果在非活动链表中的一个页的 PG_referenced 标志置为 0：
第一次访问后置 1，但该页仍留在非活动链表。
第二次访问时发现该标志被设置，则把页移到活动链表。
但如果第一次访问后在给定时间间隔内没有再次访问，则页框回收算法可能重置 PG_referenced 标志。

mark_page_accessed()

把页标记为访问过。每当内核决定一个页是被用户态进程、文件系统层还是设备驱动程序引用时，该情况就会发生。

调用 mark_page_accessed() 的情况：

• 当按需装入进程的一个匿名页时。
• 当按需装入内存映射文件的一个页时。
• 当按需装入 IPC 共享内存区的一个页时。
• 当从文件读取数据页时。
• 当换入一个页时。
• 当在页高速缓存中搜索一个缓冲区页时。

mark_page_accessed() 执行下列代码：

1
2
3
4
5
6
7
8
9
1if(!PageActive(page) && PageReferenced(page) && PageLRU(page))

2{

3   activate_page(page);

4   ClearPageReferenced(page);

5}

6else if(!PageReferenced(page))

7   SetPageReferenced(page);

8

9

page_referenced()

PFRA 扫描一页调用一次 page_referenced()，如果 PG_referenced 标志或页表项中的某些 Accessed 标志置位，则返回 1；否则返回 0。
首先检查页描述符的 PG_referenced 标志，如果该标志置位则清 0。
然后使用面向对象的反向映射方法，对引用该页的所有用户态页表项中的 Accessed 标志位进行检查并清 0。

从活动链表到非活动链表移动页不是由 page_referenced() 实施，而是 refile_inactive_zone()。

refile_inactive_zone()

被 shrink_zone() 调用，shrink_zone() 对页高速缓存和用户态地址空间进行页回收。

refile_inactive_zone() 的工作很重要，因为从活动链表移到非活动链表就意味着页迟早被 PFRA 捕获。
如果该函数过激，就会由过多的页从活动链表移动到非活动链表，PFRA 就会回收大量的页框，系统性能就会受到影响。
但如果该函数太懒，就没有足够的未用页来补充非活动链表，PFRA 就不能回收内存。
因此，该函数可调整自己的行为：开始时，对每次调用，扫描非活动链表中少量的页，但当 PFRA 很难回收内存时，就在每次被调用时增加扫描的活动页数。

还有一个试探法可调整该函数的行为。
LRU 链表中有两类页：属于用户态地址空间的页、不属于任何用户态进程且在页高速缓存中的页。
PFRA 倾向于压缩页高速缓存，而将用户态进程的页留在 RAM 中。
该函数使用交换倾向经验值确定是移动所有的页还是只移动不属于用户态地址空间的页。

交换倾向值 = 映射比率 / 2 + 负荷值 + 交换值

映射比率是用户态地址空间所有内存管理区的页（sc->nr_mapped）占有可分配页框数的百分比。
mapped_ratio 值大时表示动态内存大部分用于用户态进程，小则表示大部分用于页高速缓存。

负荷值用于表示 PFRA 在管理区中回收页框的效率。
依据是前一次 PFRA 运行时管理区的扫描优先级，该优先级存放在管理区描述符的 prev_priority 字段。

交换值是一个用户定义常数，通常为 60。
系统管理员可在 /proc/sys/vm/swappiness 文件内修改该值，或用相应的 sysctl() 调整该值。

当管理区交换倾向值大于等于 100 时，页才从进程地址空间回收。
当系统管理员将交换值设为 0 时，PFRA 就不会从用户态地址空间回收页，除非管理区的前一次优先级为 0（不太可能）。
如果管理员将交换值设为 100，则 PFRA 每次调用该函数时都会从用户态地址空间回收页。

refill_inactive_zone()：

1. 调用 lru_add_drain() 把仍留在 pagevec 中的所有页移入活动与非活动链表。
2. 获得 zone->lru_lock 自旋锁。
3. 首次扫描 zone->active_list 中的页，从链表的底部开始向上，直到链表为空或 sc->nr_to_scan 的页扫描完毕。

每扫描一页，就将引用计数器加 1，从 zone->active_list 中删除页描述符，把它放在临时局部链表 l_hold 中。
但是如果页框引用计数器是 0，则把该页放回活动链表。
实际上，引用计数器为 0 的页框一定属于管理区的伙伴系统，但释放页框时，首先递减使用计数器，然后将页框从 LRU 链表删除并插入伙伴系统链表。
因此在一个很小的时间段，PFRA 可能会发现 LRU 链表中的空闲页。

1. 把已扫描的活动页数追加到 zone->pages_scanned。
2. 从 zone->nr_active 中减去移入局部链表 l_load 中的页数。
3. 释放 zone->lru_lock 自旋锁。
4. 计算交换倾向值。
5. 扫描局部链表 l_hold 中的页。

目的：把其中的页分到两个子链表 l_active 和 l_inactive 中。
属于某个进程用户态地址空间的页（即 page->_mapcount 为负数的页）被加入 l_active 的条件时：
交换倾向值小于 100，或者是匿名页但又没有激活的交换区，或者应用于该页的 page_referenced() 返回正数（该页最近被访问过）。而在其他情形下，页被加入 l_incative 链表。

1. 获得 zone->lru_lock 自旋锁。
2. 扫描链表 l_inactive 中的页。

把页移入 zone->inactive_list 链表，更新 zone->nr_inactive 字段，同时递减被移页框的使用计数器，从而抵消第 3 步中增加的值。

1. 扫描局部链表 l_active 中的页。

把页移入 zone->active_list 链表，更新 zone->nr_active 字段，同时递减被移页框的使用计数器，从而抵消第 3 步中增加的值。

1. 释放自旋锁 zone->lru_lock 并返回。

内存紧缺回收

当内存分配失败时激活内存紧缺回收。
在分配 VFS 缓冲区或缓冲区首部时，内核调用 free_more_memory()；
而当从伙伴系统分配一个或多个页框时，调用 try_to_free_pages()。

free_more_memory()

1. 调用 wakeup_bdflush() 唤醒一个 pdflush 内核线程，并触发页高速缓存中 1024 个脏页的写操作。

写脏页到磁盘的操作将最终包含缓冲区、缓冲区首部和其他 VFS 数据结构的页框变为可释放的。

1. 调用 sched_yield() 的服务例程为 pdflush 内核线程提供执行机会。
2. 对系统的所有内存节点，启动一个循环。

对每一个节点，调用 try_to_free_pages()，参数数一个“紧缺”内存管理区链表。

try_to_free_pages()

参数：

• zones，要回收的页所在的内存管理区链表。
• gfp_mask，用于识别的内存分配的一组分配标志。
• order，没有使用。

函数的目标是通过重复调用 shrink_caches() 和 shrink_slab() 释放至少 32 个页框，每次调用后优先级会比前一次提高。
有关的辅助函数可获得 scan_control 类型描述符中的优先级，以及正在进行的扫描操作的其他参数。
如果 try_to_free_pages() 没能在某次调用 shrink_caches() 和 shrink_slab() 时成功回收至少 32 个页框，PFRA 就无策了。
最后一招：out_of_memory() 删除一个进程，释放它的所有页框。

try_to_free_pages()：

1. 分配和初始化一个 scan_control 描述符，具体说就是把分配掩码 gfp_mask 存入 gfp_mask 字段。
2. 对 zones 链表中的每个管理区，将管理区描述符的 temp_priority 字段设为初始优先级 12，而且计算管理区 LRU 链表中的总页数。
3. 从优先级 12 到 0，执行最多 13 次循环，每次迭代执行如下子步骤：

a. 更新 scan_control 描述符的一些字段。
nr_mapped 为用户态进程的总页数；priority 为本次迭代的当前优先级；nr_scanned 和 nr_relcaimed 字段设为 0。
b. 调用 shrink_caches()，参数为 zones 链表和 scan_control 描述符，扫描管理区的非活动页。
c. 调用 shrink_slab() 从可压缩内核高速缓存中回收页。
d. 如果 current->reclaim_state 非空，则将 slab 分配器高速缓存中回收的页数追加到 scan_control 描述符的 nr_reclaimed 字段。
在调用 try_to_free_pages() 前，__alloc_pages() 建立 current->reclaim_state 字段，并在结束后马上清除该字段。
e. 如果已达到目标，则跳出循环到第 4 步。
f. 如果未达目标，但已扫描完成至少 49 页，则调用 wakeup_bdflush() 激活 pdflush 内核线程，并将页高速缓存中的一些脏页写入磁盘。
g. 如果函数已完成 4 次迭代而又未达目标，则调用 blk_congestion_wait() 挂起进程，一直到没有拥塞的 WRITE 请求队列或 100ms 超时已到。

1. 把每个管理区描述符的 prev_priority 字段设为上一次调用 shrink_caches() 使用的优先级，该值存放在管理区描述符的 temp_priority 字段。
2. 如果成功回收则返回 1，否则返回 0。

shrink_caches()

被 try_to_free_pages() 调用，参数：内存管理区链表 zones 和 scan_control 描述符地址 sc。

该函数的目的只是对 zones 链表中的每个管理区调用 shrink_zone()。
但对给定管理区调用 shrink_zone() 前，shrink_caches() 用 sc->priority 字段的值更新管理区描述符的 temp_priority 字段，这就是扫描操作的当前优先级。
而且如果 PFRA 的上一次调用优先级高于当前优先级，即该管理区进行页框回收变得更难了，在 shrink_caches() 把当前优先级拷贝到管理区描述符的 prev_priority。
最后，如果管理区描述符中的 all_unreclaimable 标志置位，且当前优先级小于 12，则 shrink_caches() 不调用 shrink_zone()，即在 try_to_free_pages() 的第一次迭代中不调用 shrink_caches()。
当 PFRA 确定一个管理区都是不可回收页，扫描该管理区的页纯粹是浪费时间时，则将 all_unreclaimable 标志置位。

shrink_zone()

两个参数：zone 和 sc。zone 是指向 struct_zone 描述符的指针；sc 是指向 scan_control 描述符的指针。
目标是从管理区非活动链表回收 32 页。
它每次在更大的一段管理区非活动链表上重复调用辅助函数 shrink_cache()。
而且 shrink_zone() 重复调用 refill_incative_zone() 来补充管理区非活动链表。

管理区描述符的 nr_scan_active 和 nr_scan_inactive 字段在这里起到很重要的作用。
为提高效率，函数每批处理 32 页。
因此，如果函数在低优先级运行（对应 sc->priority 的高值），且某个 LRU 链表中没有足够的页，函数就跳过对它的扫描。
但因此跳过的活动或不活动页数存放在 nr_scan_active 或 nr_scan_inactive 中，这样函数下次执行时再处理这些跳过的页。

shrink_zone() 具体执行步骤如下：

1. 递增 zone->nr_scan_active，增量是活动链表（zone->nr_active）的一小部分。

实际增量取决于当前优先级，其范围是：zone->nr_active/2$^{12}$ 到 zone->nr_active/2$^0$（即管理区的总活动页数）。

1. 递增 zone->nr_scan_inactive，增量是非活动链表（zone->nr_inactive）的一小部分。

实际增量取决于当前优先级，其范围是：zone->nr_active/2$^{12}$ 到 zone->nr_inactive。

1. 如果 zone->nr_scan_active 字段大于等于 32，函数就把该值赋给局部变量 nr_active，并把该字段设为 0，否则把 nr_active 设为 0。
2. 如果 zone->nr_scan_inactive 字段大于等于 32，函数就把该值赋给局部变量 nr_inactive，并把该字段设为 0，否则把 nr_inactive 设为 0。
3. 设定 scan_control 描述符的 sc->nr_to_recalim 字段为 32。
4. 如果 nr_active 和 nr_inactiv 都为 0，则无事可做，函数结束。

这不常见，用户态进程没有被分配到任何页时才可能出现这种情形。

1. 如果 nr_active 为正，则补充管理区非活动链表：

1
2
3
4
5
1sc->nr_to_scan = min(nr_active, 32)

2nr_active -= sc->nr_to_scan

3refill_inactive_zone(zone, sc)

4

5

1. 如果 nr_inactive 为正，则尝试从非活动链表回收最多 32 页：

1
2
3
4
5
1sc->nr_to_scan = min(nr_inactive, 32)

2nr_inactive -= sc->nr_to_scan

3shrink_cache(zone, sc)

4

5

1. 如果 shrink_zone() 成功回收 32 页，则结束；否则，跳回第 6 步。

shrink_cache()

shrink_cache() 是一个辅助函数，其目的是从管理区非活动链表取出一组页，把它们放入一个临时链表，然后调用 shrink_list() 对该链表中的每个页进行有效的页框回收操作。
参数与 shrink_zones() 一样，都是 zone 和 sc，执行的主要步骤：

1. 调用 lru_add_drain()，把仍然在 pagevec 数据结构中的页移入活动与非活动链表。
2. 获得 zone->lru_lock 自旋锁。
3. 处理非活动链表的页（最多 32 页），对于每一页，函数递增使用计数器；检查该页是否不会被释放到伙伴系统；把页从管理区非活动链表移入一个局部链表。
4. 把 zone->nr_inactive 计数器的值减去从非活动链表中删除的页数。
5. 递增 zone->pages_scanned 计数器的值，增量为在非活动链表中有效检查的页数。
6. 释放 zone->lru_lock 自旋锁。
7. 调用 shrink_list()，参数为第 3 步中搜集的页（在局部链表中）。
8. 把 sc->nr_to_reclaim 字段的值减去由 shrink_list() 实际回收的页数。
9. 再次获取 zone->lru_lock 自旋锁。
10. 把局部链表中 shrink_list() 没有成功释放的页放回非活动或活动来链表。

shrink_list() 有可能置位 PG_active 标志，从而将某页标记为活动页。
该操作使用 pagevec 数据结构对一组页进行处理。

1. 如果函数扫描的页数至少是 sc->nr_to_scan，且如果没有成功回收目标页数（sc->nr_to_reclaim > 0），则跳回第 3 步。
2. 释放 zone->lru_lock 自旋锁并结束。

shrink_list()

为页框回收算法的核心部分。
从 try_to_free_pages 到 shrink_cache() 的目的就是找到一组适合回收的候选页。
shrink_list() 则从参数 page_list 链表中尝试回收这些页，第二个参数 sc 是指向 scan_control 描述符的指针。
当 shrink_list() 返回时，page_list 中剩下的是无法回收的页。

1. 如果当前进程的 need_resched 字段置位，则调用 schedule()。
2. 执行一个循环，处理 page_list 中的每一页。对其中的每个元素，从链表中删除页描述符并尝试回收该页框。

如果由于某种原因页框不能释放，则把该页描述符插入一个局部链表。

1. 现在 page_list 已空，函数在把页描述符从局部链表移回 page_list 链表。
2. 递增 sc->nr_reclaimed 字段，增量为第 2 步中回收的页数，并返回该数。

shrink_list() 处理的每个页框只能有三种结果：

• 调用 free_cold_page()，把页释放到管理区伙伴系统，因此被有效回收。
• 页没有被回收，因此被重新插入 page_list 链表。但是，shrink_list 假设不久还能回收该页。

因此函数让页描述符的 PG_active 标志保持清 0，这样页将被放回内存管理区的非活动链表。

• 页没有被回收，因此被重新插入 page_list 链表。

但是，或是页正被使用，或是 shrink_list() 假设近期无法回收该页。
函数将页描述符的 PG_active 标志置位，这样页框将被放回内存管理区的活动链表。

shrink_list() 不会回收锁定页（PG_locked 置位）与写回页（PG_writeback 置位）。
shrink_list() 调用 page_referenced() 检查该页是否最近被引用过。

要回收匿名页，就必须把它加入交换高速缓存，那么就必须在交换区为它保留一个新页槽（slot）。

如果页在某个进程的用户态地址空间（页描述符的 _mapcount 字段大于等于 0），则 shrink_list() 调用 try_to_unmap() 寻找引用该页框的所有页表项。
当然，只有当该函数返回 SWAP_SUCCESS 时，回收才可继续。

如果是脏页，则写回磁盘前不能回收，为此，shrink_list() 使用 pageout()。
只有当 pageout() 不必进行写操作或写操作不久将结束时，回收才可继续。

如果页包含 VFS 缓冲区，则 shrink_list() 调用 try_to_release_page() 释放关联的缓冲区首部。

最后，如果一切顺利，shrink_list() 就检查页的引用计数器。
如果等于 2，则这两个拥有者就是：页高速缓存（如果是匿名页，则为交换高速缓存）和 PFRA 自己（shrink_cache() 第 3 步会递增引用计数器）。
这种情况下，如果页仍然不为脏，则页可以回收。
为此，首先根据页描述符的 PG_swapcache 标志的值，从页高速缓存或交换高速缓存删除该页，然后，执行函数 free_cold_page()。

pageout()

当一个脏页必须写回磁盘时，shrink_list() 调用 pageout()。

1. 检查页存放在页高速缓存还是交换高速缓存中。

进一步检查该页是否由页高速缓存与 PFRA 拥有。如果检查失败，则返回 PAGE_KEEP。

1. 检查 address_space 对象的 writepage 方法是否已定义。如果没有，则返回 PAGE_ACTIVATE。
2. 检查当前进程是否可以向块设备（与 address_space 对象对应）请求队列发出写请求。

实际上，kswapd 和 pdflush 内核线程总会发出写请求；
而普通进程只有在请求对象不拥塞时才会发出写请求，除非 current->bacing_dev_info 字段指向块设备的 backing_dev_info 数据结构。

1. 检查是否仍然是脏页。如果不是则返回 PAGE_CLEAN。
2. 建立一个 writeback_control 描述符，调用 address_space 对象的 writepage 方法以启动一个写回操作。
3. 如果 writepage 方法返回错误码，则函数返回 PAGE_ACTIVATE。
4. 返回 PAGE_SUCCCESS。

回收可压缩磁盘高速缓存的页

内核在页高速缓存之外还使用其他磁盘高速缓存，例如目录项耗时缓存与索引节点高速缓存。
当要回收其中的页框时，PFRA 就必须检查这些磁盘高速缓存是否可压缩。

PFRA 处理的每个磁盘高速缓存在初始化时必须注册一个 shrinker 函数。
shrinker 函数有两个参数：待回收页框数和一组 GFP 分配标志。
函数按照要求从磁盘高速缓存回收页，然后返回仍然留在高速缓存内的可回收页数。

set_shrinker() 向 PFRA 注册一个 shrinker 函数。
该函数分配一个 shrinker 类型的描述符，在该描述符中存放 shrinker 函数的地址，然后把描述符插入一个全局链表，该链表存放在 shrinker_list 全局变量中。
set_shrinker() 还初始化 shrinker 描述符的 seeks 字段，通俗地说，该字段表示：在高速缓存中的元素一旦被删除后重建一个所需的代价。

在 Linux 2.6 中，向 PFRA 注册的磁盘高速缓存很少。
除了目录项高速缓存和索引节点高速缓存外，注册 shrinker 函数的只有磁盘限额层、文件系统源信息块高速缓存和 XFS 日志文件系统。

从可压缩磁盘高速缓存回收页的 PFRA 函数叫做 shrink_slab()。
它由 try_to_free_pages() 和 balance_pgdat() 调用。

对于从可压缩磁盘高速缓存回收的代价与从 LRU 链表回收的代价之间，shrink_slab() 试图作出一种权衡。
实际上，函数扫描 shrinker 描述符的链表，调用这些 shrinker 函数并得到磁盘高速缓存中总的可回收页数。
然后，函数再一次扫描 shrinker 描述符的链表，对于每个可压缩磁盘高速缓存，函数推算出待回收页框数。
推算考虑的因素：磁盘高速缓存中总的可回收页数、在磁盘高速缓存中重建一页的相关代价、LRU 链表中的页数。
然后再调用 shrinker 函数尝试回收一组页（至少 128 页）。

从目录项高速缓存回收页框

shrink_dcache_memory() 是目录项高速缓存的 shrinker 函数。
它搜索高速缓存中的未用目录项对象，即没有被任何进程引用的目录项对象，然后将它们释放。

由于目录项高速缓存对象是通过 slab 分配器分配的，因此 shrink__dcache_memory() 可能导致一些 slab 变成空闲的，这样有些页框就可以被 cache_reap() 回收。
此外，目录项高速缓存索引节点起高速缓存控制器的作用，因此，当一个目录项对象被释放时，存放相应索引节点对象的页就可以变为未用，而最终被释放。

shrink_dcache_memory() 接收两个参数：待回收页框数和 GFP 掩码。
一开始，它检查 GFP 掩码中的 __GFP_FS 标志是否清 0，如果是则返回 -1，因为释放目录项可能触发基于磁盘文件系统的操作。
通过调用 prune_dcache()，就可以有效地进行页框回收。
该函数扫描未用目录项链表，一直获得请求数量的释放对象或整个链表扫描完毕。
对每个最近未被引用的对象，函数执行如下步骤：

1. 把目录项对象从目录项散列表、从其父目录中的目录项对象链表、从拥有者索引节点的目录项对象链表中删除。
2. 调用 d_iput 目录项方法或者 iput() 函数减少目录项的索引节点的引用计数器。
3. 调用目录项对象的 d_release 方法。
4. 调用 call_rcu() 函数以注册一个会删除目录项对象的回调函数，该回调函数又调用 kmem_cache_free() 把对象释放给 slab 分配器。
5. 减少父目录的引用计数器。

最后，依据仍然留在目录项高速缓存中的未用目录项数，shrink_dcache_memory() 返回一个值：
未用目录项数乘以 100 除以 sysctl_vfs_cache_pressure 全局变量的值。
该变量的系统默认值是 100，因此返回值实际就是未用目录项数。
但通过修改文件 /proc/sys/vm/vfs_cache_pressure 或通过有关的 sysctl() 系统调用，系统管理员可以改变该值。
把值改为小于 100，则使 shrink_slab() 从目录项高速缓存回收的页少于从 LRU 链表中回收的页。
反之，如果把值改为大于 100，则使 shrink_slab() 从目录项高速缓存回收的页多于从 LRU 链表中回收的页。

从索引节点高速缓存回收页框

shrink_icache_memory() 被调用从索引节点高速缓存中删除未用索引节点对象。
“未用”是指索引节点不再有一个控制目录对象。
该函数非常类似于 shrink_dcache_memory()。
它检查 gfp_mask 参数的 __GFP_FS 位，然后调用 prune_icache()，依据仍然留在索引节点高速缓存中的未用索引节点数和 sysctl_vfs_cache_pressure 变量的值，返回一个值。

prune_icache() 又扫描 inode_unsed 链表。
要释放一个索引节点，函数必须释放与该索引节点管理的任何私有缓冲区，它使页高速缓存内的不再使用的干净页框无效，然后通过调用 clear_inode() 和 destroy_inode() 删除索引节点对象。

周期回收

PFRA 用两种机制进行周期回收：kswapd 内核线程和 cache_reap 函数。
前者调用 shrink_zone() 和 shrink_slab() 从 LRU 链表中回收页；
后者则被周期性地调用以便从 slab 分配器中回收未用的 slab。

kswapd 内核线程

kswapd 内核线程是激活内存回收的另外一种机制。

kswapd 利用机器空闲的时间保持内存空闲页也对系统性能有良好的影响，进程因此能很快获得自己的页。

每个内存节点对应各自的 kswapd 内核线程。
每个这样的线程通常睡眠在等待队列中，该等待队列以节点描述符的 kswapd_wait 字段为头部。
但是，如果 __alloc_pages() 发现所有适合内存分配的内存管理区包含的空闲页框数低于“警告”阈值时，那么相应内存节点的 kswapd 内核线程被激活。
从本质上，为了避免更多紧张的“内存紧缺”的情形，内核才开始回收页框。

每个管理区描述符还包括字段 pages_min 和 pages_high。
前者表示必须保留的最小空闲页框数阈值；
后者表示“安全”空闲页框数阈值，即空闲页框数大于该阈值时，应该停止页框回收。

kswapd 内核线程执行 kswapd()。
内核线程被初始化的内容是：

1. 把线程绑定到访问内存节点的 CPU。
2. 把 reclaim_state 描述符地址存入进程描述符的 current->reclaim_state 字段。
3. 把 current->flags 字段的 PF_MEMALLOC 和 PF_KSWAP 标志置位，其含义是进程将回收内存，运行时允许使用全部可用空闲内存。

kswapd() 执行下列操作：

1. 调用 finish_wait() 从节点的 kswad_wait 等待队列删除内核线程。
2. 调用 balance_pgdat() 对 kswapd 的内存节点进行内存回收。
3. 调用 prepare_to_wait() 把进程设成 TASK_INTERRUPTIBLE 状态，并让它在节点的 kswapd_wait 等待队列中睡眠。
4. 调用 schedule() 让 CPU 处理一些其他可运行进程。

balance_pgdat() 执行下面步骤：

1. 建立 scan_control 描述符。
2. 把内存节点的每个管理区描述符中的 temp_priority 字段设为 12（最低优先级）。
3. 执行一个循环，从 12 到 0 最多 13 次迭代，每次迭代执行下列步骤：

a. 扫描内存管理区，寻找空闲页框数不足的最高管理区（从 ZONE_DMA 到 ZONE_HIGHMEM）。由 zone_watermark_ok() 进行每次的检测。如果所有管理区都有大量空闲页框，则跳到第 4 步。
b. 对一部分管理区再一次进行扫描，范围是从 ZONE_DMA 到第 3a 步找到的管理区。
对每个管理区，必要时用当前优先级更新管理区描述符的 prev_priority 字段，且连续调用 shrink_zone() 以回收管理区中的页。然后，调用 shrink_slab() 从 可压缩磁盘高速缓存回收页。

1. 用各自 temp_priority 字段的值更新每个管理区描述符的 prev_priorit y 字段。
2. 如果仍有“内存紧缺”管理区存在，且如果进程的 need_resched 字段置位，则调用 schedule()。

当再一次执行时，跳到第 1 步。

1. 返回回收的页数。

cache_reap()

PFRA 使用 cache_reap() 回收 slab 分配器高速缓存的页。
cache_reap() 周期性（大约每两秒一次）地在预定事件工作队列中被调度。
它的地址存放在每 CPU 变量 reap_work 的 func 字段，该变量为 work_struct 类型。

cache_reap() 执行下列步骤：

1. 尝试获得 cache_chain_sem 信号量，该信号量保护 slab 高速缓存描述符链表。

如果信号量已取得，就调用 schedule_delayed_work() 去调度该函数的下一次执行，然后结束。

1. 否则，扫描存放在 cache_chain 链表中的 kmem_cache_t 描述符。

对找到的每个高速缓存描述符，执行下列步骤：
a. 如果高速缓存描述符的 SLAB_NO_REAP 标志置位，则页框回收被禁止，因此处理链表中的下一个高速缓存。
b. 清空局部 slab 高速缓存，则会有新的 slab 被释放。
c. 每个高速缓存都有“收割时间”，该值存放在高速缓存描述符中 kmem_list3 结构的 next_reap 字段。
如果 jiffies 值仍然小于 next_reap，则继续处理链表中的下一个高速缓存。
d. 把存放在 next_reap 字段的下一次“收割时间”设为：从现在起的 4s。
e. 在多处理器系统中，函数清空 slab 共享高速缓存，那么会有新的 slab 被释放。
f. 如果有新的 slab 最近被加入高速缓存，即高速缓存描述符中 kmem_list3 结构的 free_touched 标志置位，则跳过该高速缓存，继续处理链表中的下一个高速缓存。
g. 根据经验公式计算要释放的 slab 数量。
基本上，该数取决于高速缓存中空闲对象数的上限和能装入单个 slab 的对象数。
h. 对高速缓存空闲 slab 链表中的每个 slab，重复调用 slab_destroy()，直到链表为空或者已回收目标数量的空闲 slab。
i. 调用 cond_resched() 检查当前进程的 TIF_NEED_RESCHED 标志，如果该标志置位，则调用 schedule()。

1. 释放 cache_chain_sem 信号量。
2. 调用 schedule_delayed_work() 去调度该函数的下一次执行，然后结束。

内存不足删除程序

当所有可用内存耗尽，PFRA 使用所谓的内存不足（out of memory，OOM）删除程序，该程序选择系统中的一个进程，强行删除它并释放页框。

当空闲内存十分紧缺且 PFRA 又无法成功回收任何页时，__alloc_pages() 调用 out_of_memory()。
out_of_memory() 调用 select_bad_process() 在现有进程中选择一个“牺牲品”，然后调用 oom_kill_process() 删除该进程。

select_bad_process() 挑选满足下列条件的进程：

• 它必须拥有大量页框，从而可以释放出大量内存。
• 删除它只损失少量工作结果（删除一个工作了几个小时或几天的批处理进程就不是个好主意）。
• 它应具有较低的静态优先级，用户通常给不太重要的进程赋予较低的优先级。
• 它不应是有 root 特权的进程，特权进程的工作通常比较重要。
• 它不应直接访问硬件设备，因为硬件不能处在一个无法预知的状态。
• 它不能是 swapper（进程 0）、init（进程 1）和任何其它内核线程。

select_bad_process() 扫描系统中的每个进程，根据以上准则用经验公式计算一个值，该值表示选择该进程的有利程度，然后返回最有利的被选进程描述符的地址。
out_of_memory() 再调用 oom_kill_process() 并发出死亡信号（通常是 SIGKILL），该信号发给该进程的一个子进程，或如果做不到，就发给进程进程本身。
oom_kill_process() 同时也删除与被选进程共享内存描述符的所有克隆进程。

交换标记

为减少交换失效的发生，Jiang 和 Zhang 将交换标记赋给系统中的单个进程，该标记可避免该进程的页框被回收，所以进程可继续运行，而且即使内存十分稀少。

交换标记的具体形式是 swap_token_mm 内存描述符指针。
当进程拥有交换标记时，swap_token_mm 被设为进程内存描述符的地址。

页框回收算法的免除以该简洁的方式实现了。
在“最近最少使用（LRU）链表”中可知，只有一页最近没有被引用时，才可从活动链表移入非活动链表。
page_referenced() 进行这一检查。
如果该页属于一个线性区，该区域所在进程拥有交换标记，则认可该交换标记并返回 1（被引用）。
实际上，交换标记在几种情形下不予考虑：

• PFRA 以代表一个拥有交换标记的进程在运行。
• PFRA 达到页框回收的最难优先级（0 级）。

grab_swap_token() 决定是否将交换标记赋给当前进程。
在以下两种情形下，对每个主缺页调用该函数：

• 当 filemap_nopage() 发现请求页不在页高速缓存中时。
• 当 do_swap_page() 从交换区读入一个新页时。

grap_swap_token() 在分配交换标记前要进行一些检查，满足以下条件时才分配：

• 上次调用 grab_swap_token() 后，至少已过了 2s。
• 在上次调用 grab_swap_token() 后，当前拥有交换标记的进程没再提出主缺页，或该进程拥有交换标记的时间超出 swap_token_default_timeout 个节拍。
• 当进程最近没有获得过交换标记。

交换标记的持有时间最好长一些，甚至以分钟为单位，因为其目标就是允许进程完成其执行。
在 Linux 2.6 中，交换标记的持有时间默认值很小，即一个节拍。
但通过编辑 /proc/sys/vm/swap_token_defaut_timeout 文件或发出相应的 sysctl() 系统调用，系统管理员可修改 swap_token_default_timeout 变量的值。

当删除一个进程时，内核调用 mmput() 检查该进程是否拥有交换标记，如果是则放开它。

交换

交换用来为非映射页在磁盘上提供备份。有三类页必须由交换子系统处理：

• 属于进程匿名线性区（例如，用户态堆栈和堆）的页。
• 属于进程私有内存映射的脏页。
• 属于 IPC 共享内存区的页。

交换子系统的主要功能总结如下：

• 在磁盘上建立交换区，用于存放没有磁盘映像的页。
• 管理交换区空间。当需求发生时，分配与释放页槽。
• 提供函数用于从 RAM 中把页换出到交换区或从交换区换入到 RAM 中。
• 利用页表项（现已被换出的换出页页表项）中的换出页标识符跟踪数据在交换区中的位置。

交换是页框回收的一个最高级特性。
如果需要确保进程的所有页框都能被 PFRA 随意回收，而不仅仅是回收有磁盘映像的页，就必须使用交换。
可以用 swapoff 命令关闭交换，但随着磁盘系统负载增加，很快磁盘系统就会瘫痪。

交换可以用来扩展内存地址空间，使之被用户态进程有效地使用，但性能比 RAM 慢几个数量级。

交换区

从内存中换出的页存放在交换区中，交换区的实现可以使用自己的磁盘分区，也可以使用包含在大型分区中的文件。
可定义几种不同的交换区，最大个数由 MAX_SWAPFILES 宏确定。

如果有多个交换区，就允许系统管理员把大的交换空间分布在几个磁盘上，以使硬件可以并发操作这些交换区；
这一处理还允许在系统运行时不用重新启动系统就可以扩大交换空间的大小。

每个交换区都由一组页槽组成，即一组 4096 字节大小的块组成，每块中包含一个换出的页。
交换区的第一个页槽用来永久存放有关交换区的信息，其个数由 swap_header 联合体描述。
magic 结构提供了一个字符串，用来把磁盘某部分明确地标记为交换区，它只含有一个字段 magic.magic，该字段含有一个 10 字符的“magic”字符串。
maginc 结构从根本上允许内核明确地把一个文件或分区标记成交换区，该字符串的内容就是“SWAPSPACE2”，通常位于第一个页槽的末尾。

创建与激活交换区

交换区包含很少的控制信息，包括交换区类型和有缺陷页槽的链表，存放在一个单独的 4KB 页中。

通常，系统管理员在创建 Linux 系统中的其它分区时都创建一个交换区，然后使用 mkswap 命令把这个磁盘区设置成 一个新的交换区。
该命令对刚才介绍的第一个页槽中的字段进行初始化。
由于磁盘中可能会有一些坏块，该程序还可以对其它所有的页槽进行检查从而确定有缺陷页槽的位置。
但是执行 mkswap 命令会把交换区设置成非激活的状态。
每个交换区都可以在系统启动时在脚本文件中被激活，也可以在系统运行之后动态激活。

每个交换区由一个或多个交换子区组成，每个交换子区由一个 swap_extent 描述符表示，每个子区对应一组页，它们在磁盘上是物理相邻的。
swap_extent 描述符由几部分组成：交换区的子区首页索引、子区的页数和子区的起始磁盘扇区号。
当激活交换区自身的同时，组成交换区的有序子区链表也被创建。
存放在磁盘分区中的交换区只有一个子区；但是，存放在普通文件中的交换区可能有多个子区，这是因为文件系统有可能没把该文件全部分配在磁盘的一组连续块中。

交换区描述符

每个活动的交换区在内存中都有自己的 swap_info_struct 描述符。

swap_map 字段指向一个计数器数组，交换区的每个页槽对应一个元素。
如果计数器值等于 0，则该页槽就是空闲的；如果计数器为正数，那么换出页就填充了这个页槽。
实际上，页槽计数器的值就表示共享换出页的进程数。
如果计数器的值为 SWAP_MAP_MAX（32767），那么存放在该页槽中的页就是“永久”的，并且不能从相应的页槽中删除。
如果计数器的值是 SWAP_MAP_BAD（32768），那么就认为该页槽是有缺陷的，不可用。

prio 字段是一个有符号的整数，表示交换子系统依据该值考虑每个交换区的次序。

sdev_lock 字段是一个自旋锁，它防止 SMP 系统上对交换区数据结构的并发访问。

swap_info 数组包括 MAX_SWAPFILES 个交换区描述符。
只有那些设置了 SWP_USED 标志的交换区才被使用，因为它们是活动区域。
图 17-6 说明了 swap_info 数组、一个交换区和相应的计数器数组的情况。

nr_swapfiles 变量存放数组中包含或已包含所使用交换区描述符的最后一个元素的索引。
这个变量有些名不符实，它并没有包含活动交换区的个数。

活动交换区描述符也被插入按交换区优先级排序的链表中。
该链表是通过交换区描述符的 next 字段实现的，next 字段存放的是 swap_info 数组中下一个描述符的索引。

swap_list_t 类型的 swap_list 变量包括以下字段：

• head，第一个链表元素在 swap_info 数组中的下标。
• next，为换出页所选中的下一个交换区的描述符在 swap_info 数组中的下标。

该字段用于在具有空闲页槽的最大优先级的交换区之间实现轮询算法。

交换区描述符的 max 字段存放以页为单位交换区的大小，而 pages 字段存放可用页槽的数目。
这两个数字之所以不同是因为 pages 字段并没有考虑第一个页槽和有缺陷的页槽。

最后，nr_swap_pages 变量包含所有活动交换区中可用的（空闲并且无缺陷）页槽数目，而 total_swap_pages 变量包含无缺陷页槽的总数。

换出页标识符

通过在 swap_info 数组中指定交换区的索引和在交换区内指定页槽的索引，可简单而又唯一地标识一个换出页。
由于交换区的第一个页（索引为 0）留给 swap_header 联合体，第一个可用页槽的索引就为 1。

swp_entry(type, offset) 宏负责从交换区索引 type 和页槽索引 offset 中构造出页标识符。
swp_type 和 swp_offset 宏正好相反，它们分别从换出页标识符中提取出交换区区索引和页索引。

当页被换出时，其标识符就作为页的表项插入页表中，这样在需要时就可以在找到该页。
要注意这种标识符的最低位与 Present 标志对应，通常被清除来说明该页目前不在 RAM 中。
但是，剩余 31 位中至少一位被置位，因为没有页存放在交换区 0 的页槽 0 中。
这样就可以从一个页表项中区分三种不同的情况：

• 空项，该页不属于进程的地址空间，或相应的页框还没有分配给进程（请求调页）。
• 前 31 个最高位不全等于 0，最后一位等于 0，该页被换出。
• 最低位等于 1，该页包含在 RAM 中。

注意，交换区的最大值由表示页槽的可用位数决定。
在 80×86 体系结构结构上，有 24 位可用，这就限制了交换区的大小为 2$^{24}$ 个页槽。

由于一页可以属于几个进程的地址空间，所以它可能从一个进程的地址空间被换出，但仍旧保留在主存中；
因此可能把同一个页换出多次。
当然，一个页在物理上只被换出并存储一次，但后来每次试图换出该页都会增加 swap_map 计数器的值。

在试图换出一个已经换出的页时就会调用 swap_duplicate()。
该函数只是验证以参数传递的换出页标识符是否有效，并增加相应的 swap_map 计数器的值。
执行下列操作：

1. 使用 swp_type 和 swp_offset 宏从参数中提取出交换区号 type 和页槽索引 offset。
2. 检查交换区是否被激活；如果不是，则返回 0（无效的标识符）。
3. 检查页槽是否有效且是否不为空闲（swap_map 计数器大于 0 且小于 SWAP_MAP_BAD）；

如果不是，则返回 0（无效的标识符）。

1. 否则，换出页的标识符确定出一个有效页的位置。

如果页槽的 swap_map 计数器还没有达到 SWAP_MAP_MAX，则增加它的值。

1. 返回 1（有效的标识符）。

激活和禁用交换区

一旦交换区被初始化，超级用户（任何具有 CAP_SYS_ADMIN 权能的用户）就可以分别使用 swapon 和 swapoff 程序激活和禁用交换区。
这两个程序分别使用了 swapon() 和 swapoff() 系统调用。

sys_swapon() 服务例程

参数：

• specialfile，指向设备文件（或分区）的路径名（在用户态地址空间），或指向实现交换区的普通文件的路径名。
• swap_flags，由一个单独的 SWAP_FLAG_PREFER 位加上交换区优先级的 31 位组成（只有在 SWAP_FLAG_PREFER 位置位时，优先级位才有意义）。

sys_swapon() 对创建交换区时放入第一个页槽中的 swap_header 联合体字段进行检查，执行下列步骤：

1. 检查当前进程是否具有 CAP_SYS_ADMIN 权能。
2. 在交换区描述符 swap_info 数组的前 nr_swapfiles 个元素中查找 SWP_USED 标志为 0（即对应的交换区不是活动的）的第一个描述符。如果找到一个不活动交换区，则跳到第 4 步。
3. 新交换区数组索引等于 nr_swapfiles：它检查保留给交换区索引的位数是否足够用于编码新索引。

如果不够，则返回错误代码；如果足够，就将 nr_swapfiles 的值增加 1。

1. 找到未用交换区索引：它初始化这个描述符的字段，即把 flags 置为 SWP_USED，把 lowest_bit 和 highest_bit 置为 0。
2. 如果 swap_flags 参数为新交换区指定了优先级，则设置描述符的 prio 字段。

否则，就把所有活动交换区中最低位的优先级减 1 后赋给这个字段（这样就假设最后一个被激活的交换区在最慢的块设备上）。如果没有其它交换区是活动的，就把该字段设置为 -1。

1. 从用户态地址空间复制由 specialfile 参数所指向的字符串。
2. 调用 filp_open() 打开由 specialfile 参数指定的文件。
3. 把 filp_open() 返回的文件对象地址存放在交换区描述符的 swap_file 字段。
4. 检查 swap_info 中其它的活动交换区，以确认该交换区还未被激活。

具体为，检查交换区描述符的 swap_file->f_mapping 字段中存放的 address_space 对象地址。
如果交换区已被激活，则返回错误码。

1. 如果 specialfile 参数标识一个块设备文件，则执行下列子步骤：

a. 调用 bd_claim() 把交换子系统设置为块设备的占有者。如果块设备已有一个占有者，则返回错误码。
b. 把 block_device 描述符地址存入交换区描述符的 bdev 字段。
c. 把设备的当前块大小存放在交换区描述符的 old_block_size 字段，然后把设备的块大小设成 4096 字节（即页的大小）。

1. 如果 specialfile 参数标识一个普通文件，则执行下列子步骤：

a. 检查文件索引节点 i_flags 字段中的 S_SWAPFILE 字段。如果该标志置位，说明文件已被用作交换区，返回错误码。
b. 把该文件所在块设备的描述符地址存入交换区描述符的 bdev 字段。

1. 调用 read_cache_page() 读入存放在交换区页槽 0 的 swap_header 描述符。

参数为：swap_file->f_mapping 指向的 address_space 对象、页索引 0、文件 readpage 方法的地址（存放在 swap_file->f_mapping->a_ops->readpage）和指向文件对象 swap_file 的指针。然后等待直到页被读入内存。

1. 检查交换区中第一页的最后 10 个字符中的魔术字符串是否等于“SWAPSPACE2”。如果不是，返回一个一个错误码。
2. 根据存放在 swap_header 联合体的 info.last_page 字段中的交换区大小，初始化交换区描述符的 lowest_bit 和 hightest_bit 字段。
3. 调用 vmalloc() 创建与新交换区相关的计数器数组，并把它的地址存放在交换区描述符的 swap_map 字段中。

还要根据 swap_header 联合体的 info.bad_pages 字段中存放的有缺陷的页槽链表把该数组的元素初始化为 0 或 SWAP_MAP_BAD。

1. 通过访问第一个页槽中的 info.last_page 和 info.nr_badpages 字段计算可用页槽的个数，并把它存入交换区描述符的 pages 字段。而且把交换区中的总页数赋给 max 字段。
2. 为新交换区建立子区链表 extent_list（如果交换区建立在磁盘分区上，则只有一个子区），并相应地设定交换区描述符的 nr_extents 和 curr_swap_extent 字段。
3. 把交换区描述符的 flags 字段设为 SWP_ACTIVE。
4. 更新 nr_good_pages、nr_swap_pages 和 total_swap_pages 三个全局变量。
5. 把新交换区描述符插入 swap_list 变量所指向的链表中。
6. 返回 0（成功）。

sys_swapoff() 服务例程

sys_swapoff() 服务例程使 specialfile 参数所指定的交换区无效。
sys_swapoff() 比 sys_swapon() 复杂，因为使之无效的这个分区可能仍然还包含几个进程的页。
因此，强制该函数扫描交换区并把所有现有的页都换入。
由于每个换入操作都需要一个新的页框，因此如果现在没有空闲页框，该操作就可能失败，函数返回一个错误码。

sys_swapoff() 执行下列步骤。

1. 验证当前进程是否具有 CAP_SYS_ADMIN 权能。
2. 拷贝内核空间中 specialfile 所指向的字符串。
3. 调用 filp_open() 打开 specialfile 参数确定的文件，返回文件对象的地址。
4. 扫描交换区描述符链表 swap_list，比较由 filp_open() 返回的文件对象地址与活动交换区描述符的 swap_file 字段中的地址，如果不一致，说明传给函数的是一个无效参数，返回一个错误码。
5. 调用 cap_vm_enough_memory() 检查是否由足够的空闲页框把交换区上存放的所有页换入。

如果不够，交换区就不能禁用，然后释放文件对象，返回错误码。
这只是粗略的检查，但可使内核免于许多无用的磁盘操作。
当执行该项检查时，cap_vm_enough_memory() 要考虑由 slab 高速缓存分配且 SLAB_RECLAIM_ACCOUNT 标志置位的页框，这样的页（可回收的页）的数量存放在 slab_reclaim_pages 变量中。

1. 从 swap_list 链表中删除该交换区描述符。
2. 从 nr_swap_pages 和 total_swap_pages 的值中减去存放在交换区描述符的 pages 字段的值。
3. 把交换区描述符 flags 字段中的 SWAP_WRITEOK 标志清 0。这可禁止 PFRA 向交换区换出更多的页。
4. 调用 try_to_unuse() 强制把该交换区中剩余的所有页都移到 RAM 中，并相应地修改使用这些页的进程的页表。

当执行该函数时，当前进程的 PF_SWAPOFF 标志置位。
该标志置位只有一个结果：如果页框严重不足，select_bad_process() 就会强制选中并删除该进程。

1. 一直等待交换区所在的块设备驱动器被卸载。

这样在交换区被禁用之前，try_to_unuse() 发出的读请求会被驱动器处理。

1. 如果在分配所有请求的页框时 try_to_unuse() 失败，那么就不能禁用该交换区。因此，sys_swapoff() 执行下列步骤：

a. 把该交换区描述符重新插入 swap_listl 链表，并把它的 flags 字段设置为 SWP_WRITEOK。
b. 把交换区描述符中 pages 字段的值加到 nr_swap_pages 和 total_swap_pages 变量以恢复其原址。
c. 调用 filp_close() 关闭在第 3 步中打开的文件，并返回错误码。

1. 否则，所有已用的页槽都已经被成功传送到 RAM 中。因此，执行下列步骤：

a. 释放存有 swap_map 数组和子区描述符的内存区域。
b. 如果交换区存放在磁盘分区，则把块大小恢复到原值，该原值存放在交换区描述符的 old_block_size 字段。
而且，调用 bd_release() 使交换子系统不再占有该块设备。
c. 如果交换区存放再普通文件中，则把文件索引节点的 S_SWAPFILE 标志清 0。
d. 调用 filp_close() 两次，第一次针对 swap_file 文件对象，第二次针对第 3 步中 filep_open() 返回的对象。
e. 返回 0（成功）。

try_to_unuse() 使用一个索引参数，该参数标识待清空的交换区。
该函数换入页并更新已换出页的进程的所有页表。
因此，该函数从 init_mm 内存描述符开始，访问所有内核线程和进程的地址空间。
这是一个比较耗时的函数，通常以开中断运行。
因此，与其它进程的同步也是关键。

try_to_unuse() 扫描交换区的 swap_map 数组。
当它找到一个“在用”页槽时，首先换入其中的页，然后开始查找引用该页的进程。
这两个操作顺序对避免竞争条件至关重要。
当 I/O 数据传送正在进行时，页被加锁，因此没有进程可以访问它。
一旦 I/O 数据传输完成，页又被 try_tu_unuse() 加锁，以使它不会被另一个内核控制路径再次换出。
因为每个进程在开始换入或换出操作前查找页高速缓存，所以这也可以避免竞争条件。
最后，由 try_to_unuse() 所考虑的交换区被标记为不可写（SWP_WRITEOK 标志被清 0），因此，没有进程可对该交换区的页槽执行换出。

但是，可能强迫 try_to_unuse() 对交换区引用计数器的 swap_map 数组扫描几次。
这是因为对换出页引用的线性区可能在一次扫描中消失，而在随后又出现在进程链表中。

因此，try_to_unuse() 对引用给定页槽的进程进行查找时可能失败，因为相应的线性区暂时没有包含在进程链表中。
为了处理该情况，try_to_unuse() 一直对 swap_map 数组进行扫描，直到所有的引用计数器都变为空。
引用了换出页的线性区最终会重新出现在进程链表中，因此，try_to_unuse() 中将会成功释放所有页槽。

try_to_unuse() 的参数为交换区 swap_map 数组的引用计数器。
该函数在引用计数器上执行连续循环，如果当前进程接收到一个信号，则循环中断，函数返回错误码。
对于数组中的每个引用计数器，try_to_unuse() 执行下列步骤：

1. 如果计数器等于 0（没有页存放在这里）或等于 SWAP_MAP_BAD，则对下一个页槽继续处理。
2. 否则，调用 read_swap_cache_async() 换入该页。

这包括分配一个新页框（如果必要），用存放在页槽中的数据填充新页框并把该页存放在交换高速缓存。

1. 等待，直到用磁盘中的数据适当地更新了该新页，然后锁住它。
2. 当正在执行前一步时，进程有可能被挂起。

因此，还要检查该页槽的引用计数器是否变为空，如果是，说明该交换页可能被另一个内核控制路径释放，然后继续处理下一个页槽。

1. 对于以 init_mm 为头部的双向链表中的每个进程描述符，调用 unuse_process()。

该耗时的函数扫描拥有内存描述符的进程的所有页表项，并用该新页框的物理地址替换页表中每个出现的换出页标识符。
为了反映这种移动，还要把 swap_map 数组中的页槽计数器减 1（触发计数器等于 SWAP_MAP_MAX），并增加该页框的引用计数器。

1. 调用 shmem_unuse() 检查换出的页是否用于 IPC 共享内存资源，并适当地处理该种情况。
2. 检查页的引用计数器。如果它的值等于 SWAP_MAP_MAX，则页槽是“永久的”。

为了释放它，则把引用计数器强制置为 1。

1. 交换高速缓存可能页拥有该页（它对应计数器的值起作用）。如果页属于交换高速缓存，就调用 swap_writepage() 把页的内容刷新到磁盘（如果页为脏），调用 delete_from_swap_cache() 从交换高速缓存删去页，并把页的引用计数减 1。
2. 设置页描述符的 PG_dirty 标志，并打开页框的锁，递减它的引用计数器（取消第 5 步的增量）。
3. 检查当前进程的 need_resched 字段；如果它被设置，则调用 schedule() 放弃 CPU。

禁用交换区是一件冗长的工作，内核必须保证系统中的其它进程仍然继续执行。
只要该进程再次被调度程序选中，try_to_unuse() 就从该步继续执行。

1. 继续到下一个页槽，从第 1 步开始。

try_to_unuse() 继续执行，直到 swap_map 数组中的每个引用计数器都为空。
即使该函数已经开始检查下一个页槽，但前一个页槽的引用计数器有可能仍然为正。
事实上，一个进程可能还在引用该页，典型的原因是某些线性区已经被临时从第 5 步所扫描的进程链表中删除。
try_to_unuse() 最终会捕获到每个引用。
但是，在此期间，页不再位于交换高速缓存，它的锁被打开，并且页的一个拷贝仍然包含在要禁用的交换区的页槽中。

一般认为该种情形可能导致数据丢失。如，某个“幽灵”进程访问页槽，并开始换入其中的页。
因为页不再位于交换高速缓存，因此，进程用从磁盘读取的数据填充一个新的页框。
但是，该页框可能不同于与“幽灵”进程共享页的那些进程曾经拥有的页框。

当禁用交换区时该问题不会发生，因为只有在换出的页属于私有匿名内存映射时，才会受到“幽灵”进程的干扰。
在这种情况下，用“写时复制”机制处理页框，所以，把不同的页框分配给引用了该页的进程是完全合法的。
但是，try_to_unuse() 将页标记为“脏”，否则，shrink_list() 可能随后从某个进程的页表中删除该页，而并不把它保存在另一个交换区中。

分配和释放页槽

搜索空闲页槽的第一种方法可以选择下列两种既简单又有些极端的策略之一：

• 总数从交换区的开头开始。

这种方法在换出操作过程中可能会增加平均寻道时间，因为空闲页槽可能已经被弄得凌乱不堪。

• 总是从最后一个已分配的页槽开始。

如果交换区的大部分空间都是空闲的（通常如此），那么这种方法在换入操作过程中会增加平均寻道时间，因为所占用的为数不多的页槽可能是零散存放的。

Linux 采用了一种混合的方法。
除非发生以下条件，否则 Linux 总是从最后一个已分配的页槽开始查找。

• 已经到达交换区的末尾。
• 上次从交换区的开头重新开始后，已经分配了 SWAPFILE_CLUSTER（通常是 256）个空闲页槽。

swap_info_struct 描述符的 cluster_nr 字段存放已分配的空闲页槽数。
当函数从交换区的开头重新分配时该字段被重置为 0。
cluster_next 字段存放在下一次分配时要检查的第一个页槽的索引。

为加速对空闲页槽的搜索，内核要保证每个交换区描述符的 lowest_bit 和 hightest_bit 字段是最新的。
这两个字段定义了第一个和最后一个可能为空的页槽，换言之，所有低于 lowest_bit 和高于 hightest_bit 的页槽都被认为已经分配过。

scan_swap_map()

在给定的交换区中查找一个空闲页槽并返回其索引。参数指向交换区描述符。
如果交换区不含有任何空闲页槽，就返回 0。

scan_swap_map()：

1. 首先试图使用当前的簇。

如果交换区描述符的 cluster_nr 字段是正数，就从 cluster_next 索引处的元素开始对计数器的 swap_map 数组进行扫描，查找一个空项。如果找到，就减少 cluster_nr 字段的值并转到第 4 步。

1. 执行到该步，或者 cluster_nr 字段为空，或者从 cluster_next 开始搜索后没有在 swap_map 数组中找到空项。

现在开始第二阶段的混合查找。
把 cluster_nr 重新初始化成 SWAPFILE_CLUSTER，并从 lowest_bit 索引处开始重新扫描该数组，以便试图找到有 SWAPFILE_CLUSTER 个空闲槽的一个组。如果找到，转第 4 步。

1. 不存在 SWAPFILE_CLUSTER 个空闲页槽的组。

从 lowest_bit 索引处开始重新开始扫描该数组，以便试图找到一个单独的空闲页槽。
如果没有找到空项，就把 lowest_bit 字段设置为数组的最大索引，hightest_bit 字段设置为 0，并返回 0（交换区已满）。

1. 已经找到空项。把 1 放在空项中，减少 nr_swap_pages 的值，如果需要就修改 lowest_bit 和 highest_bit 字段，把 inuse_page 字段的值加 1，并把 cluster_next 字段设置成刚才分配的页槽的索引加 1。
2. 返回刚才分配的页槽的索引。

get_swap_page()

通过搜索所有活动的交换区来查找一个空闲页槽。
返回一个新近分配页槽的换出页标识符，如果所有的交换区都填满，就返回 0，该函数要考虑活动交换区的不同优先级。

该函数需要经过两遍扫描，在容易发现页槽时可以节约运行时间。
第一遍是部分的，只适用于只有相同优先级的交换区。
该函数以轮询的方式在这种交换区中查找一个空闲页槽。
如果没有找空闲页槽，就从交换区链表的起始位置开始第二遍扫描。
在第二遍扫描中，要对所有的交换区都进行检查。

get_swap_page()：

1. 如果 nr_swap_pages 为空或者如果没有活动的交换区，就返回 0。
2. 首先考虑 swap_list.next 所指向的交换区（交换区链表是按优先级排序的）。
3. 如果交换区是活动的，就调用 scan_swap_map() 获得一个空闲页槽。

如果 scan_swap_map() 返回一个页槽索引，该函数的任务基本就完成了，但还要准备下一次被调用。
因此，如果下一个交换区的优先级和这个交换区的优先级相同（即轮询使用这些交换区），该函数就把 swap_list.next 修改成指向交换区链表中的下一个交换区。
如果下一个交换区的优先级和当前交换区的优先级不同，该函数就把 swap_list.next 设置成交换区链表中的第一个交换区（下次搜索时从优先级最高的交换区开始）。
该函数最终返回刚才分配的页槽所对应的换出页标识符。

1. 或者交换区是不可写的，或者交换区中没有空闲页槽。

如果交换区链表中的下一个交换区的优先级和当前交换区的优先级相同，就把下一个交换区设置成当前交换区并跳到第 3 步。

1. 此时，交换区链表的下一个交换区的优先级小于前一个交换区的优先级。

下一步操作取决于该函数正在进行哪一遍扫描。
a. 如果只是第一遍（局部）扫描，就考虑链表中的第一个交换区并跳转到第 3 步，这样就开始第二遍扫描。
b. 否则，就检查交换区链表中是否有下一个元素。如果有，就考虑这个元素并跳到第 3 步。

1. 此时，第二遍对链表的扫描已经完成，并没有发现空闲页槽，返回 0。

swap_free()

当换入页时，调用 swap_free() 以对相应的 swap_map 计数器减 1。
当相应的计数器达到 0 时，由于页槽的标识符不再包含在任何页表项中，因此页槽变为空闲。
交换高速缓存页也记录页槽拥有者的个数。

该函数只作用于一个参数 entry，entry 表示换出页标识符。函数执行下列步骤：

1. 从 entry 参数导出交换区索引和页槽索引 offset，并获得交换区描述符的地址。
2. 检查交换区是否是活动的。如果不是，就立即返回。
3. 如果正在释放的页槽对应的 swap_map 计数器小于 SWAP_MAP_MAX，就减少该计数器的值。

值为 SWAP_MAP_MAX 的项都被认为是永久的（不可删除的）。

1. 如果 swap_map 计数器变为 0，就增加 nr_swap_pages 的值，减少 inuse_pages 字段的值，如果需要就修改该交换区描述符的 lowest_bit 和 hightest_bit 字段。

交换高速缓存

向交换区来回传送页会引发很多竞争条件，具体说，交换子系统必须仔细处理如下情形：

• 多重换入。两个进程可能同时换入同一个共享匿名页。
• 同时换入换出。一个进程可能换入正由 PFRA 换出的页。

交换高速缓存的引入就是为了解决这类同步问题。
关键的原则是，没有检查交换高速缓存是否包括了所涉及的页，就不能进行换入或换出操作。
有了交换高速缓存，涉及同一页的并发交换操作总是作用于同一个页框的。
因此，内核可以安全地依赖页描述符的 PG_locked 标志，以避免任何竞争条件。

考虑一下共享同一换出页的两个进程这种情形。当第一个进程试图访问页时，内核开始换入页操作，第一步就是检查页框是否在交换高速缓存中，假定页框不在交换高速缓存中，内核会分配一个新页框并把它插入交换高速缓存，然后开始I/O操作，从交换区读入页的数据；
同时，第二个进程访问该匿名页，与上面相同，内核开始换入操作，检查涉及的页框是否在交换高速缓存中。
现在页框在交换高速 缓存，因此内核只是访问页框描述符，在 PG_locked 标志清 0 之前（即 I/O 数据传输完毕之前），让当前进程睡眠。

当换入换出操作同时出现时，交换高速缓存起着至关重要的作用。
shrink_list() 要开始换出一个匿名页，就必须当 try_to_unmap() 从进程（所拥有该页的进程）的用户态页表中成功删除了该页后才可以。
但是当换出的写入操作还在执行时，可能有某个进程要访问该页，而产生换入操作。
在写入磁盘前，待换出页由 shrink_list()存放在交换高速缓存。
考虑页 P 由两个进程（A 和 B）共享。
最初，两个进程的页表项都引用该页框，该页有 2 个拥有者，如图 a 所示。
当 PFRA 选择回收页时，shrink_list() 把页框插入交换高速缓存，如图 b 所示，现在页框有 3 个拥有者，而交换区中的页槽只被交换高速缓存引用。
然后 PFRA 调用 try_to_unmap() 从这两个进程的页表项中删除对该页框的引用。
一旦该函数结束，该页框就只有交换高速缓存引用它，而引用页槽的为这两个进程和交换高速缓存，如图 c 所示。
假定：当页中的数据写入磁盘时，进程 B 访问该页，即它要用该页内部的线性地址访问内存单元。
那么，缺页异常处理程序发现页框在交换高速缓存，并把物理地址放回 B 的页表项，如图 d 所示。
相反，如果缓存操作结束，而没有并发换入操作，shrink_list() 则从交换高速缓存删除该页框并把它释放到伙伴系统，如图 e 所示。

交换高速缓存可被视为一个临时区域，该区域存有正在被换入后缓存的匿名页描述符。
当换入或缓存结束时（对于共享匿名页，换入换出操作必须对共享该页的所有进程进行），匿名页描述符就可以从交换高速缓存删除。

交换高速缓存的实现

页高速缓存的核心就是一组基树，借助基树，算法就可以从 address_space 对象地址（即该页的拥有者）和偏移量值推算出页描述符的地址。

在交换高速缓存中页的存放方式是隔页存放，并有下列特征：

• 页描述符的 mapping 字段为 NULL。
• 页描述符的 PG_swapcache 标志置位。
• private 字段存放与该页有关的换出页标识符。

此外，当页被放入交换高速缓存时，页描述符的 count 字段和页槽引用计数器的值都增加，因为交换高速缓存既使用页框，也使用页槽。

最后，交换高速缓存的所有页只使用一个 swapper_space 地址空间，因此只有一个基树（有 swapper_space.page_tree 指向）对交换高速缓存中的页进行寻址。
swapper_space 地址空间的 nrpages 字段存放交换高速缓存中的页数。

换出页

向交换高速缓存插入页框

换出操作的第一步就是准备交换高速缓存。
如果 shrink_list() 确认某页为匿名页，且交换高速缓存中没有相应的页框（页描述符的 PG_swapcache 标志清 0），内核就调用 add_to_swap()。

add_to_swap() 在交换区中分配一个新页槽，并把一个页框（其页描述符地址作为参数传递）插入交换高速缓存。
函数执行下述步骤。

1. 调用 get_swap_page() 分配一个新页槽，失败（如没有发现空闲页槽）则返回 0。
2. 调用 __add_to_page_cache()，参数为页槽索引、页描述符地址和一些分配标志。
3. 将页描述符中的 PG_uptodate 和 PG_dirty 标志置位，从而强制 shrink_list() 把页写入磁盘。
4. 返回 1（成功）。

更新页表项

一旦 add_to_swap() 结束，shrink_list() 就调用 try_to_unmap()，它确定引用匿名页的每个用户态页表项地址，然后将换出页标识符写入其中。

将页写入交换区

为完成换出操作需执行的下一个步骤是将页的数据写入交换区。
这一 I/O 传输由 shrink_list() 激活，它检查页框的 PG_dirty 标志是否置位，然后执行 pageout()。

pageout() 建立一个 writeback_control 描述符，且调用页 address_space 对象的 writepage 方法。
而 swapper_state 对象的 writepage 方法是 swap_writepage() 实现。

swap_writepage() 执行如下步骤。

1. 检查是否至少有一个用户态进程引用该页。如果没有，则从交换高速缓存删除该页，并返回 0。

这一检查之所以必须做，是因为一个进程可能会与 PFRA 发生竞争并在 shrink_list() 检查后释放一页。

1. 调用 get_swap_bio() 分配并初始化一个 bio 描述符。

函数从换出页标识符算出交换区描述符地址，然后搜索交换子区链表，以找到页槽的初始磁盘扇区。
bio 描述符将包含一个单页数据请求（页槽），其完成方法设为 end_swap_bio_write()。

1. 置位页描述符的 PG_writeback 标志和交换高速缓存基树的 writeback 标记，并将 PG_locked 标志清 0。
2. 调用 submit_bio()，参数为 WRITE 命令和 bio 描述符地址。
3. 返回 0。

一旦 I/O 数据传输结束，就执行 end_swap_bio_write()。
该函数唤醒正等待页 PG_writeback 标志清 0 的所有进程，清除 PG_writeback 标志和基树中的相关标记，并释放用于 I/O 传输的 bio 描述符。

从交换高速缓存中删除页框

缓存操作的最后一步还是由 shrink_list() 执行。
如果它验证在 I/O 数据传输时没有进程试图访问该页框，就调用 delete_from_swap_cache() 从交换高速缓存中删除该页框。
因为交换高速缓存是该页的唯一拥有者，该页框被释放到伙伴系统。

换入页

当进程试图对一个已缓存到磁盘的页进行寻址时，必然会发生页的换入。
在以下条件发生时，缺页异常处理程序就会触发一个换入操作：

• 引起异常的地址所在的页是一个有效的页，即它属于当前进程的一个线性区。
• 页不在内存中，即页表项中的 Present 标志被清除。
• 与页有关的页表项不为空，但 Dirty 位清 0，这意味着页表项包含一个换出页标识符。

如果上面的所有条件都满足，则 handle_pte_fault() 调用相对建议的 do_swap_page() 换入所需页。

do_swap_page()

参数：

• mm，引起缺页异常的进程的内存描述符地址。
• vma，address 所在的线性区的线性区描述符地址。
• address，引起异常的线性地址。
• page_table，映射 address 的页表项的地址。
• pmd，映射 address 的页中间目录的地址。
• orig_pte，映射 address 的页表项的内容。
• write_access，一个标志，表示试图执行的访问是读操作还是写操作。

与其他函数相反，do_swap_page() 不返回 0。
如果页已经在交换高速缓存中就返回 1（次错误），如果页已经从交换区读入就返回 2（主错误），如果在进行换入时发生错误就返回 -1。
函数执行下述步骤：

1. 从 orig_pte 获得换出页标识符。
2. 调用 pte_unmap() 释放任何页表的临时内核映射，该页表由 handle_mm_fault() 建立。

访问高端内存页表需要进行内核映射。
3 释放内存描述符的 page_table_lock 自旋锁。

1. 调用 lookup_swap_cache() 检查交换高速缓存是否已经含有换出页标识符对应的页；

如果页已经在交换高速缓存中，就跳到第 6 步。

1. 调用 swapin_readhead() 从交换区读取至多 2n 个页的一组页，其中包括所请求的页。

值 n 存放在 page_cluster 变量中，通常等于 3。
其中每个页是通过调用 read_swap_cache_async() 读入的。

1. 再一次调用 read_swap_cache_async() 换入由引起缺页异常的进程所访问的页。

此步看起来多余，其实不然。
swapin_readahead() 可能在读取请求的页时失败，如，因为 page_cluster 被置为 0，或者该函数试图读取一组含空闲或有缺陷页槽（SWAP_MAP_BAD）的页。
另一方面，如果 swapin_readahead() 成功，这次对 read_swap_cache_async() 的调用就会很快结束，因为它在交换高速缓存找到了页。

1. 尽管如此，如果请求的页还是没有被加到交换高速缓存，那么，另一个内核控制路径可能已经代表这个进程的一个子进程换入了所请求的页。

这种情况的检查可通过临时获取 page_table_lock 自旋锁，并把 page_table 所指向的表项与 orig_pte 进行比较来实现。
如果二者有差异，则说明这一页已经被某个其它的内核控制路径换入，因此，函数返回 1（次错误）；否则，返回 -1（失败）。

1. 至此，页已经在高速缓存中。

如果页已经被换入（主错误），函数就调用 grab_swap_token() 试图获得一个交换标记。

1. 调用 mark_page_accessed() 并对页加锁。
2. 获取 page_table_lock 自旋锁。
3. 检查另一个内核控制路径是否代表这个进程的一个子进程换入了所请求的页。

如果是，就释放 page_table_lock 自旋锁，打开页上的锁，并返回 1（次错误）。

1. 调用 swap_free() 减少 entry 对应的页槽的引用计数器。
2. 检查交换高速缓存是否至少占满 50%（nr_swap_pages 小于 total_swap_pages 的一半）。

如果是，则检查页是否被引起异常的进程（或其一个子进程）拥有；如果是，则从交换高速缓存中删除该页。

1. 增加进程的内存描述符的 rss 字段。
2. 更新页表项以便进程能找到该页。

这一操作的实现是通过把所请求的页的物理地址和在线性区的 vm_page_prot 字段所找到的保护位写入 page_table 所指向的页表中完成。
此外，如果引起缺页的访问是一个写访问，且造成缺页的进程页的唯一拥有者，则函数还要设置 Dirty 和 Read/Write 标志以防无用的写时复制错误。

1. 打开页上的锁。
2. 调用 page_add_anon_rmap() 把匿名页插入面向对象的反向映射数据结构。
3. 如果 write_access 参数等于 1，则函数调用 do_wp_page() 复制一份页框。
4. 释放 mm->page_table_lock 自旋锁，并返回 1（次错误）或 2（主错误）。

read_swap_cache_async()

换入一个页。

参数：

• entry，换出页标识符。
• vma，指向该页所在线性区的指针。
• addr，页的线性地址。

在访问交换分区前，该函数必须检查交换高速缓存是否已经包含了所要的页框。
该函数本质上执行下列操作：

1. 调用 radix_tree_lookup()，搜索 swapper_sapce 对象的基树，寻找由换出页标识符 entry 给出位置的页框。

如果找到该页，递增它的引用计数器，返回它的描述符地址。

1. 页不在交换高速缓存。

调用 alloc_page() 分配一个新的页框。
如果没有空闲的页框可用，则返回 0（表示系统没有足够的内存）。

1. 调用 add_to_swap_cache() 把新页框的页描述符插入交换高速缓存，并对页加锁。
2. 如果 add_to_swap_cache() 在交换高速缓存找到页的一个副本，则前一步可能失败。

如，进程可能在第 2 步阻塞，因此允许另一个进程在同一个页槽上开始换入操作。
这种情况下，该函数释放在第 2 步分配的页框，并从第 1 步重新开始。

1. 调用 lru_cache_add_active() 把页插入 LRU 的活动链表。
2. 新页框的页描述符现在已在交换高速缓存。

调用 swap_readpage() 从交换区读入该页数据。
该函数与 swap_writepage() 相似，将页描述符的 PG_uptodate 标志清 0，调用 get_swap_bio() 为 I/O 传输分配与初始化一个 bio 描述符，再调用 submit_bio() 向块设备子系统层发出 I/O 请求。

1. 返回页描述符的地址。