第17章 回收页框

页框回收算法

内存及磁盘高速缓存抓取了那么多的页框但从未释放任何页框。因此，迟早所有的空闲内存将被分配给进程和高速缓存。Linux内核的页框回收算法（page frame reclaiming algorithm，PFRA）采取从用户进程和内核高速缓存“窃取”页框的办法补充伙伴系统的空闲块列表。

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

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

映射页：所谓“映射页”就是指该页映射了一个文件的某个部分。映射页差不多都是可同步的，为了回收页框，内核必须检查页是否为脏，而且必要时将页的内容写道相应的磁盘文件。

匿名页：所谓“匿名页”就是指它属于一个进程的某个线性区（例如，进程的用户态堆和堆栈中的所有页称为匿名页）。为了回收页框，内核必须将页中内容保存到一个专门的磁盘分区或磁盘文件，叫做“交换区”。所以匿名页都是可交换的。

PFRA设计

PFRA算法的候选页：磁盘高速缓存 页高速缓存以及属于进程用户态地址空间的页。

PFRA算法的原则：

1.首先释放无害页：在进程用户态地址空间的页回收之前，必须县回收没有被任何进程使用的磁盘和内存高速缓存的页

2.将用户进程的所有页定为可回收页：除了锁定页，PFRA必须能够窃得任何用户进程页。这样，睡眠较长时间的进程将会失去所有页框

3.同时取消引用一个共享页框的所有页表项的映射，就可以回收该共享页框

4.只回收未用页：使用简化的LRU算法，PFRA算法将页框分为在用（in_use）和未用（unused）

反向映射

PFRA的目标之一是回收共享页框。Linux 2.6内核能够快速定位指向同一页框的所有页表项。这个过程称为反向映射（reverse mapping）。

反向映射方法的简单解决之道，就是在页描述符中引入附加字段，从而将某页描述符所确定的页框中对应的所有页表项联接起来。但是，保持更新这样的链表将会大大增加系统开销。Linux 2.6采用”面向对象的反向映射”的技术。实际上，对任何可回收的用户态页，内核保留系统中该页所在所有线性区（“对象”）的反向链接，每个线性区描述符存放一个指针指向一个内存区描述符，而该内存描述符又包含一个指针 指向一个页全局目录（Page Global Directory）。因此，这些反向链接使得PFRA能够检索引用某页的所有页表项。

为确定页框是共享还是非共享的，匿名还是非匿名，内核要查看页描述符的两个字段：_mapcount和mapping。

_mapcount：引用页框的页表项数目。

                  为-1，表示没有页表项引用该页框

                  为0，表示是非共享页框，即只有一个页表项引用该页框大于0，表示页框是共享的

                  page_mapcount函数接受一个页描述符地址，返回值为map_count + 1

mapping：用于确定页框是映射页还是匿名页如果mapping

                 字段为空，则该页属于交换页如果mapping

                 字段非空，且最低位为1，则为匿名页，同时mapping字段中存放的是指向anon_vma描述符的指针

                  如果mapping字段非空，且最低位为0，则为映射页，同时mapping字段中存放的是指向对应文件的address_space对象。

PageAnon函数接受页描述符地址作为参数，如果mapping字段最低位置位（最低位为1）,则返回1，否则返回0。

匿名页的反向映射

线性区：进程使用的线性地址区间

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

当为一个匿名区分配第一页时，内核创建一个新的anon_vma数据结构，它只包含两个字段：lock和head。lock字段时竞争条件下保护链表的自旋锁，head字段时指向线性区描述符双向循环链表的头部。然后，内核将匿名线性区的vm_area_struct描述符插入到双向循环链表中。vm_area_struct包含两个字段：anon_vma_node和anon_vma。其中anon_vma_node字段存放指向链表中前一个和后一个元素的指针，而anon_vma字段指向anon_vma数据结构。最后，把指向anon_vma数据结构的指针指向页框描述符的mapping字段。如下图：

映射区页的反向映射与匿名页相反，映射页经常时共享的，这是因为不同的进程经常会共享同一程序代码。Linux 2.6依靠叫做“优先搜索树（priority search tree）”的结构来快速定位引用同一页框的所有线性区。如下图：

PFRA实现

页框回收算法必须处理多种属于用户态进程 磁盘高速缓存和页高速缓存的页

页框回收算法执行的三个路口：

1.内存紧缺回收：内核发现内存紧缺

2.睡眠回收：在进入suspend-to-disk状态时，内核必须释放内存

3.周期回收：必要时，周期性激活内核线程执行内存回收算法

最近最少使用（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_referencd标志。

PFRA使用mark_page_accessed()  page_referenced() refill_inactive_zone()函数在LRU链表之间移动页。

mark_page_accessed()函数

当内核必须把一个页标记为访问过时，就调用mark_page_accessed()函数。

page_referenced()函数

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

refill_inactive_zone()函数

refill_inactive_zone()函数由shrink_zone()函数调用，而shrink_zone()函数对页高速缓存和用户态地址空间地址进行页回收。此函数有两个参数：zone 和 sc。

zone：指针zone指向一个内存管理区的描述符

sc：指针sc指向一个scan_control结构

scan_control结构字段如下图：

     PFRA倾向于压缩页高速缓存，而将用户态进程的页留在RAM中。该函数按下列公式计算交换倾向值：

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

映射比率：用户态地址空间引用的页数占所有可分配页框的百分比

负荷值：依据是前一次PFRA运行时管理区的扫描优先级，这个优先级存放在管理区描述符的prev_priority字段。

负荷值与管理区前一次优先级的对应关系：                                                                                       管理区前一次优先级          12...7         6         5        4        3         2         1       0                              负荷值                                  0            1         3        6        12        25       50     100

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

2015.10.25:23:03

内存紧缺回收

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

free_more_memory()函数

free_more_memory()函数执行如下操作：

1.调用wakeup_bdflush()唤醒一个pdflush内核线程，并触发页高速缓存中1024个脏页的写操作。写脏页到磁盘的操作将最终使包含缓冲区 缓冲区首部和其他VFS数据结构的页框称为可释放的。

2.调用sched_yield()系统调用的服务例程，为pdflush内核线程提供指向机会。

3.对系统的所有内存节点，启动一个循环。对每一个节点，调用try_to_free_pages()函数，传给它的参数时一个“紧缺”内存管理区链表（在80x86结构中是ZONE_DMA和ZONE_NORMAL）

try_to_free_pages()函数

try_to_free_pages()函数接受如下三个参数：

zones：要回收的页所在的内存管理区链表

gfp_mask：用于失败的内存分配的一组分配标志

order：没有使用

该函数的目标就是通过重复调用shrink_caches()和shrink_slab()函数时方至少32个页框，每次调用后优先级会比前一次提高。有关的辅助函数可以获得scan_control类型描述符中的优先级，以及正在进行的扫描操作的其他参数。最低的 也是初始的优先级是12，而最高的 也是最终的优先级是0。如果try_to_free_pages()每能在某次（共13次）调用shrink_caches()和shrink_slab()函数时成功回收32个页框，PFRA就要黔驴技穷了。最后一招：删除一个进程，释放它的所有页框。这一操作由out_of_memory()函数执行。

shrink_caches()函数

shrink_caches()函数由try_to_free_pages()函数调用，它有两个参数：内存管理区链表zones和scan_control描述符地址sc。

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

shrink_zone()函数

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

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

shrink_cache()函数

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

shrink_list()函数