页框回收和交换

1、目录介绍反向映射（reverse mapping）PFRA实现交换介绍PFRA：页框回收算法，全称是page frame reclaiming algorithm。用来从用户态进程和内核高速缓存回收页框来补充buddy系统的空闲块列表。基本上回收三种页匿名页：堆栈映射页：文件缓存页：目录、inode、slab高速缓存、交换高速缓存介绍PFRA基本策略：回收每个内存管理区的LRU链表中的最不常用的项（一般为32项）。回收可压缩磁盘高速缓存的页如果上面两项不足以解决内存紧缺，调用OOM删除程序释放页框反向映射（reverse mapping）PFRA中必须解决共享页框（多个进程共享）的回收定义：回

2、收页框时必须知道有哪些页表项指向这个页框（需要修改页表项）解决方法 简单：在页描述符中添加一个列表Linux解决办法：面向对象的反向映射分类：匿名页的反向映射映射页的反向映射面向对象的反向映射PFRA确定待回收页是共享的还是非共享的页描述符的_ mapcount -1,0，大于0三种PFRA确定待回收页类型页描述符的mapping 为空：高速缓存 不为空时判断最低位两种 1：匿名页 0：映射页API：PageAnon检查mapping最低位try_to_unmap尝试清空所有页表项面向对象的反向映射Int ret;If(PageAnon(page)Ret=try_to_unmap_anon(p

3、age);ElseRet=try_to_unmap_file(page);If(!page_mapped(page)Ret=SWAP_SUCCESS;RETURN RET;反向映射-匿名页数据结构：链表，连接所有的线性区描述符存放位置：页描述符的mapping字段struct anon_vma spinlock_t lock; struct list_head head; /第一个线性区 ;注意：每个线性区只有一个链表注意：每个线性区只有一个链表反向映射-匿名页反向映射-匿名页APITry_to_unmap_anon(page) 对每个链表中的线性区描述符vma，调用try_to_unmap_

4、one（vma，page）Try_to_unmap_one() 计算匿名页的线性地址，进而获得页表项地址 清空页表项，刷新TLB 换出到交换区 如果是匿名页要插入换出页标识符到页表项 插入present标志，递减_map_count反向映射-映射页数据结构：优先搜索树（priority search tree）（为何不用链表）为何不用链表）作用：快速定位引用同一页的所有线性区存放位置：address_space的i_mmap字段反向映射-映射页APITry_to_unmap_file(page) 对每个搜索树中查找到的的线性区描述符vma，调用try_to_unmap_one（vma，page

5、）Try_to_unmap_one() 计算匿名页的线性地址，进而获得页表项地址 清空页表项，刷新TLB， 如果dirty要换出到文件 插入present标志，递减_map_countPFRA实现三种基本情形：内存紧缺回收 分为缓冲区和页分配两种睡眠回收（基本相同，这里不再讨论）周期回收 使用内核线程，kswapd线程和events线程PFRA实现PFRA实现LRU链表属于进程用户态地址空间进程用户态地址空间或页高速缓存页高速缓存的所有页分为活动链表和非活动链表：双向链表每个内存管理区一个LRU链表 Zone描述符active_list和inactive_list字段 nr_active和nr

6、_inactive表示两个双向链表的数量很多API处理LRU链表PFRA实现-LRU链表之间移动PG_referenced标志和PG_active标志PFRA实现-LRU链表之间移动有三个函数负责在两个链表中移动页mark_page_accessed()：内核标记一个页被访问过，并且移动页到活动链表page_referenced()：检查：检查PG_referenced或页表或页表项中的项中的accessed标志，并且清标志，并且清0refill_inactive_zone()：实际把页从活动链表移：实际把页从活动链表移动到非活动链表（调用动到非活动链表（调用page_referenced）P

7、FRA实现-LRU链表之间移动refill_inactive_zone参数：参数：zone和和sc实际把页从活动链表移动到非活动链表实际把页从活动链表移动到非活动链表函数掠夺性不能太强或太弱，所以函数掠夺性不能太强或太弱，所以linux使它可使它可以调整自己的行为以调整自己的行为公式公式 交换倾向值交换倾向值=映射比率映射比率/2+负荷值负荷值+交换值交换值只有交换倾向值大于等于只有交换倾向值大于等于100才会从用户空才会从用户空间回收间回收PFRA实现-LRU链表之间移动refill_inactive_zone过程过程从活动链表的尾部出发，扫描nr_to_scan（来源于参数sc）个页，将其

8、移入局部链表中。计算交换倾向值对局部链表进行扫描（3次扫描） 第一次：把页分到l_active（用户态页（交换倾向值小于100，或匿名页但是无交换区，或page_referenced返回1）和l_inactive链表中。 第二次：将l_inactive中的页移入内存区的非活动链表 第三次：对l_active扫描，将所有页移入内存区的活动链表。PFRA实现-内存紧缺回收内存分配失败时激发PFRA实现-内存紧缺回收free_more_memory()：释放缓存内存这个函数写1024个脏页释放内存然后调用try_to_free_pages（）try_to_free_pages()内存管理区链表传给内

9、存管理区链表传给shrink_caches()并调用并调用调用调用shrink_slab回收可压缩内核高速缓存回收可压缩内核高速缓存shrink_caches()：释放所有的内存管理区：释放所有的内存管理区对链表中的每个内存管理区调用对链表中的每个内存管理区调用shrink_zonePFRA实现-内存紧缺回收shrink_zone()：释放内存管理区的：释放内存管理区的LRU1. 调用调用refill_inactive_zone()补充非活动链表补充非活动链表2. 调用调用shrink_cache回收非活动链表（如果回收回收非活动链表（如果回收的页数少于的页数少于32则返回则返回1）shrin

10、k_cache()：释放非活动链表：释放非活动链表将非活动链表的页（最多将非活动链表的页（最多32页）移入临时链表。页）移入临时链表。调用调用shrink_list回收这个临时链表中的页框。回收这个临时链表中的页框。把把shrink_list函数没有释放的页（临时链表的剩函数没有释放的页（临时链表的剩余项）放回活动链表和非活动链表。余项）放回活动链表和非活动链表。PFRA实现-内存紧缺回收Shrink_list()：释放shrink_cache生成的临时链表负责回收临时链表中的每一页。如果回收成功，则负责回收临时链表中的每一页。如果回收成功，则加入伙伴系统。加入伙伴系统。不成功：不成功： 没有

11、正在被使用，清空没有正在被使用，清空PG_active标志标志 正在使用，设置正在使用，设置PG_active标志标志匿名页处理：交换到交换高速缓存（匿名页处理：交换到交换高速缓存（add_to_swap）共享页处理：调用共享页处理：调用try_to_unmap脏页的处理：写入磁盘，脏页的处理：写入磁盘，pageout（）函数（）函数PFRA实现-内存紧缺回收Shrink_list流程PFRA实现-内存紧缺回收回收可压缩高速缓存例如：目录项高速缓存和inode高速缓存,磁盘限额层、文件系统元信息、XFS日志文件系统每个磁盘高速缓存初始化时必须注册每个磁盘高速缓存初始化时必须注册shrinker

12、函函数：回收函数数：回收函数内核中有内核中有shrinker描述符链表的结构描述符链表的结构shrink_slab() Shrink_dcache_memory()：目录项高速缓存 Shrink_icache_memory()： inode高速缓存 .PFRA实现-周期回收Kwapd线程和Cache_reap()函数两种。区别：Cache_reap()函数是周期执行的（2s一次）；kswapd线程是触发的。Cache_reap()函数回收的是slab分配器高速缓存；kswapd线程回收的是LRU链表和可压缩高速缓存。PFRA实现-周期回收Kwapd线程调用shrink_zone和shrink_

13、slab函数启动：_alloc_pages()发现空闲页框低于“警告值”停止：当空闲页框数量高于“安全”阀值，停止。内存管理区描述符的pages_min指警告阀值，pages_high表示“安全”阀值Cache_reap()函数：回收slab高速缓存PFRA实现-内存不足(OOM)PFRA无法得到足够内存继续执行调用内存不足程序，又称为OOM（out of memory）OOM负责杀死进程释放页框，out_of_memory，select_bad_process，oom_kill_processOOM选择进程策略已运行时间短页框多优先级低非root特权非内核线程非硬件相关（驱动）杀死：发送SI

14、GKILL信号PFRA实现-交换标记交换失效（swap thrashing）：由于内存小，页不断的换入换出2.6.9以后的内核中：将交换标记(swap token)赋予进程，避免页框回收grab_swap_token()函数负责将交换标记赋予函数负责将交换标记赋予进程进程PFRA看到进程拥有标记则不回收页框看到进程拥有标记则不回收页框修改进程持有标记的时间（执行完）修改进程持有标记的时间（执行完）可以修改可以修改/proc/sys/vm/swap_token_default_timeoutsysctl系统调用系统调用交换定义把页从内存写入到交换区（一般是磁盘，也可把页从内存写入到交换区（一般是

15、磁盘，也可以是文件）上以是文件）上需要交换的页匿名页进程私有映射的脏页IPC共享内存页实现检查present标志和换出页标识符（swapped-out page identifier）交换-基本结构交换区每个交换区有一组页槽，每个页槽4096KB，每个页槽保存一页。第一个页槽存放有关交换区的信息。第一个页槽永久存放有关交换区的信息 union swap_header struct char reservedPAGE_SIZE - 10; char magic10; /* SWAP-SPACE or SWAPSPACE2 */ magic; struct char bootbits1024; /

16、* Space for disklabel etc. */ unsigned int version; unsigned int last_page;/可有效使用的最后一个页槽 unsigned int nr_badpages;/坏的页槽个数 unsigned int padding125; unsigned int badpages1;/指定有缺陷页槽的位置 info;交换-基本结构交换子区每个交换区包含一个至多个交换子区交换子区代表磁盘上一组连续的页槽一组连续的页槽每个交换子区由一个swap_extent表示 子区首页槽索引、子区的页槽数、子区的起始磁盘扇区号换出页到交换区策略换出页到交换

17、区策略换出时尽量连续：通过搜索算法换出时尽量连续：通过搜索算法优先级高的交换区优先：通过优先级链表优先级高的交换区优先：通过优先级链表交换-基本结构交换区描述符描述交换区的结构struct swap_info_struct unsigned int flags;/标志活动和读写性 spinlock_t sdev_lock; struct file *swap_file; struct block_device *bdev; struct list_head extent_list;/交换子区链表 int nr_extents;/交换子区数量 struct swap_extent *curr_s

18、wap_extent; /当前交换子区 unsigned old_block_size; unsigned short * swap_map;/计数器数组 unsigned int lowest_bit; /搜索空闲页槽时开始的位置 unsigned int highest_bit;/搜索空闲页槽时结束的位置 unsigned int cluster_next; unsigned int cluster_nr; int prio; /* swap priority */ int pages; unsigned long max;/交换区大小 unsigned long inuse_pages;

19、 /已用页槽数 int next; /优先级列表中的下一个元素的索引;交换-基本结构交换区描述符类型的数组：swap_infoMAX_SWAPFILESnr_swapfiles定义的是数组中包含的所使用交换区的最后一个元素的索引优先级链表swap_list变量 Head：第一个元素的数组索引（优先级最高） Next：为换出页选中的下一个交换区的描述符的下标交换-基本结构交换-基本结构换出页标志符APIswp_entry：生成标识符swp_offset：提取页槽索引swp_type：提取交换区索引交换-基本结构换出页标志符当页换出的时候，换出页标示符就作为页的表项插入页表中共享页的换出：增加sw

20、ap_map的计数值页表项的三种情况空项：空前前31个最高位不全等于个最高位不全等于0，最后一位等于，最后一位等于0：交换区：交换区最低位等于最低位等于1：内存中：内存中交换区的最大值：64GB交换区的最大数量：128个交换-交换子系统交换子系统：linux管理所有交换区的系统。交换子系统主要功能：初始化与释放交换区管理交换区，分配与释放页槽将页换入与换出利用页表项中的换出页标识符查找页的位置交换-交换子系统（初始化）初始化交换区sys_swapon系统调用 参数为Speciealfile设备文件或者一个作为交换区的普通文件；Swapflags：一些标志位。 主要任务：初始化交换区描述符，最后

21、将描述符插入到数组和swap_list所指向的链表中。 返回值：成功返回0，失败返回其他。交换-交换子系统（禁用）禁用交换区sys_swapoff系统调用 参数为Speciealfile:设备文件或者一个作为交换区的普通文件。 主要任务：删除交换区描述符，并且调用try_to_unuse函数换入所有页。如果当前系统没有足够的页框则失败。 返回值：成功返回0，失败返回其他。try_to_unuse函数 参数：索引参数（标志待清空的交换区） 任务：换入页并且更新已换出页的进程的所有页表。（相当慢，因为需要搜索所有地址空间）交换-交换子系统（分配页槽）分配页槽一般思路：从头或者从第一个已分配页槽开始

22、Linux的思路 总是从最后一个已分配的页槽开始，除非 已经到达交换区的末尾 上次从交换区的开头重新分配之后，已经分配了SWAPFILE_CLUSTER（256）个空闲页槽相关数据结构（ 交换区描述符中的） cluster_nr：已分配空闲页槽数 Cluster_next：下一次分配时检查的第一个页槽索引 lowest_bit,highest_bit：第一个和最后一个可能为空的页槽交换-交换子系统（分配页槽）get_swap_page()函数查找所有的交换区来查找一个空闲页槽，它返回一个分配页槽的页标识符。如果所有交换区已满则返回0。过程：两遍扫描 第一遍：扫描相同优先级的交换区（swapli

23、st.next），对每个交换区调用scan_swap_map()，更新swaplist.next 第二遍（第一遍未找到）：从链表头开始访问交换区（ scan_swap_map() ），更新swaplist.next交换-交换子系统（分配页槽）scan_swap_map()函数作用：在指定交换区中查找一个空闲页槽参数：交换区索引返回值：空闲页槽索引或0过程：两遍查找 第一遍：从custer_next指向的索引开始查找swap_map数组。1放入swap_map相应项，更新cluster_next、cluster_nr、nr_swap_pages、inuse_page、lowest_bit、hig

24、htest_bit。 第二遍（第一遍未找到）：更新cluster_nr，从lowest_bit开始查找，直到highest_bit。找到、未找到。找到、未找到。交换-交换子系统（释放页槽）释放页槽Swap_free()函数对相应的swap_map计数器进行减1.当变为0，则相应页槽变为空闲。参数：换出页页标识符entry交换-交换子系统（交换高速缓存）交换的同步问题多重换入：两个进程同时换入同一个匿名页同时换入换出：一个进程要求换入，PFRA正在换出交换高速缓存（swap cache）解决这类同步问题一种内存中的高速缓存关键原则：没有检查交换高速缓存是否已经包关键原则：没有检查交换高速缓存是否

25、已经包含涉及的页，就不能进行换入换出。含涉及的页，就不能进行换入换出。交换-交换子系统（交换高速缓存）解决同步换入换入第一个进程的页时检查交换高速缓存，如换入第一个进程的页时检查交换高速缓存，如果不在则分配一个新页框，把页标识符中的果不在则分配一个新页框，把页标识符中的PG_locked置位（表示正在进行置位（表示正在进行IO）。接着进行）。接着进行IO第二个进程访问页，检查到页在交换高速缓存第二个进程访问页，检查到页在交换高速缓存中，但是中，但是PG_locked标志置位，那么让第二个进标志置位，那么让第二个进程睡眠等待程睡眠等待IO操作完成。操作完成。交换-交换子系统（交换高速缓存）解决同

26、时换入换出首先首先shrink_list将页换出到页高速缓存中，调用将页换出到页高速缓存中，调用ty_to_unmap函数清除页表项，然后磁盘函数清除页表项，然后磁盘IO开开始写入页。始写入页。磁盘磁盘IO时有进程访问页，则缺页异常程序会发时有进程访问页，则缺页异常程序会发现页在交换高速缓存中，于是就重置页表项指现页在交换高速缓存中，于是就重置页表项指向这个页框。向这个页框。交换-交换子系统（交换高速缓存）实现由页高速缓存数据结构（基树）和过程实现。由页高速缓存数据结构（基树）和过程实现。交换高速缓存中页描述符中交换高速缓存中页描述符中mapping字段为字段为null，PG_swapcach

27、e置位，置位，private字段存放页标识符。字段存放页标识符。当页被放入交换高速缓存时，页描述符的当页被放入交换高速缓存时，页描述符的count和页槽的计数器都增加。和页槽的计数器都增加。交换-交换子系统（交换高速缓存）Linux API：Lookup_swap_cache：参数：换出页标志符。在高速缓：参数：换出页标志符。在高速缓存中查找页并返回页描述符的地址。存中查找页并返回页描述符的地址。Add_to_swap_cache：把页插入高速缓存，会调用：把页插入高速缓存，会调用swap_duplicate（）增加页槽计数器。（）增加页槽计数器。_add_to_swap_cache：不调用：不调用swap_duplicate函数插入函数插入高速缓存。高速缓存。Delete_from_swap_cache：从高速缓存删除页。：从高速缓存删除页。Free_page_and_swap_cache：如果没有进程使用高速缓：如果没有进程使用高速缓存中的页，则删除该页并调用存中的页，则删除该页并调用swap_free函数递减计数函数递减计数器。器。Free_pages_and_swap_cache：对一组页进行以上操作。：对一组页进行以上操作。Free_swap_and_cache：释放一个交换表项。并且检查：释放一个交换表项。并且检查是否释放该页（必须