三、Linux缺页中断处理
1．请求调页中断：
进程线性地址空间里的页面不必常驻内存，例如进程的分配请求被理解满足，空间仅仅保留vm_area_struct的空间，页面可能被交换到后援存储器，或者写一个只读页面(COW)。Linux采用请求调页技术来解决硬件的缺页中断异常，并且通过预约式换页策略。
主缺页中断和次缺页中断，费时的需要从磁盘读取数据时就会产生主缺页中断。
每种CPU结构提供一个do_page_fault (struct pt_regs *regs, error_code)处理缺页中断，该函数提供了大量信息，如发生异常地址，是页面没找到还是页面保护错误，是读异常还是写异常，来自用户空间还是内核空间。它负责确定异常类型及异常如何被体系结构无关的代码处理。下图是Linux缺页中断处理流程：
图 Linux缺页中断处理
一旦异常处理程序确定异常是有效内存区域中的有效缺页中断，将调用体系结构无关的函数handle_mm_fault()。如果请求页表项不存在，就分配请求的页表项，并调用handle_pte_fault()。
第一步调用pte_present检查PTE标志位，确定其是否在内存中，然后调用pte_none()检查PTE是否分配。如果PTE还没有分配的话，将调用do_no_page()处理请求页面的分配，否则说明该页已经交换到磁盘，也是调用do_swap_page()处理请求换页。如果换出的页面属于虚拟文件则由do_no_page()处理。
第二步确定是否写页面。如果PTE写保护，就调用do_swap_page()，因为这个页面是写时复制页面。COW页面识别方法：页面所在VMA标志位可写，但相应的PTE确不是可写的。如果不是COW页面，通常将之标志为脏，因为它已经被写过了。
第三步确定页面是否已经读取及是否在内存中，但还会发生异常。这是因为在某些体系结构中没有3级页表，在这种情况下建立PTE并标志为新即可。
?
2．请求页面分配：
第一次访问页面，首先分配页面，一般由do_no_page()填充数据。如果父VMA的vm_area_struct－>vm_ops提供了nopage()函数，则用它填充数据；否则调用do_anonymous_page()匿名函数来填充数据。如果被文件或设备映射，如果时文件映射，filemap_nopage()将替代nopage()函数，如果由虚拟文件映射而来，则shmem_nopage()。每种设备驱动将提供不同的nopage()函数，该函数返回struct page结构。
?
3．请求换页：
将页面交换至后援存储器后，函数do_swap_page()负责将页面读入内存，将在后面讲述。通过PTE的信息就足够查找到交换的页面。页面交换出去时，一般先放到交换高速缓存中。
缺页中断时如果页面在高速缓存中，则只要简单增加页面计数，然后把它放到进程页表中并计数次缺页中断发生的次数。
如果页面仅存在磁盘中，Linux将调用swapin_readahead()读取它及后续的若干页面。
?
4．页面帧回收
除了slab分配器，系统中所有正在使用的页面都存放在页面高速缓存中，并由page->lru链接在一起。Slab页面不存放到高速缓存中因为基于被slab使用的对象对页面计数很困难。除了查找每个进程页表外没有其他方法能把struct page映射为PTE，查找页表代价很大。如果页面高速缓存中存在大量的进程映射页面，系统将会遍历进程页表，通过swap_out()函数交换出页面直到有足够的页面空闲，而共享页会给swap_out()带来问题。如果一个页面是共享的，同时一个交换项已经被分配，PTE就会填写所需信息以便在交换分区里重新找到该页并将引用计数减1。只有引用计数为0时该页才能被替换出去。
内存和磁盘缓存申请越来越多的页面但确无法判断如何释放进程页面，请求分页机制在进程页面缺失时申请新页面，但它却不能强制释放进程不再使用的页面。The Page Frame Reclaiming Algorithm(PFRA)页面回收算法用于从用户进程和内核cache中回收页面放到伙伴系统的空闲块列表中。PFRA必须在系统空闲内存达到某个最低限度时进行页面回收，回收的对象必须是非空闲页面。
?
可将系统页面划分为四种：
1)????? Unreclaimable不可回收的，包括空闲页面、保留页面设置了PG_reserved标志、内核动态分配的页面、进程内核栈的页面、设置了PG_locked标志的临时锁住的页面、设置了VM_LOCKED标志的内存页面。
2)????? Swappable可交换的页面，用户进程空间的匿名页面(用户堆栈)、tmpfs文件系统的映射页面（入IPC共享内存页面），页面存放到交换空间。
3)????? Syncable可同步的页面，入用户态地址空间的映射页面、保护磁盘数据的页面缓存的页面、块设备缓冲页、磁盘缓存的页面（入inode cache），如果有必要的话，需同步磁盘映像上的数据。
4)????? Discardable可丢弃的页面，入内存缓存中的无用页面（slab分配器中的页面）、dentry cache的页面。
?
PFRA算法是基于经验而非理论的算法，它的设计原则如下：
1)????? 首先释放无损坏的页面。进程不再引用的磁盘和内存缓存应该先于用户态地址空间的页面释放。
2)????? 标志所有进程态进程的页面为可回收的。
3)????? 多进程共享页面的回收，要先清除引用该页面的进程页表项，然后再回收。
4)????? 回收“不在使用的”页面。PFRA用LRU链表把进程划分为in-use和unused两种，PFRA仅回收unused状态的页面。Linux使用PTE中的Accessed比特位实现非严格的LRU算法。
?
页面回收通常在三种情况下执行：
1)????? 系统可用内存比较低时进行回收(通常发生在申请内存失败)。
2)????? 内核进入suspend-to-disk状态时进行回收。
3)????? 周期性回收，内核线程周期性激活并在必要时进行页面回收。
?
Low on memory回收有以下几种情形：
1)????? _ _getblk( )调用的grow_buffers( )函数分配新缓存页失败；
2)????? create_empty_buffers( )调用的alloc_page_buffers( )函数为页面分配临时的buffer head失败；
3)????? _ _alloc_pages( )函数在给定内存区里分配一组连续的页面帧失败。
?
周期性回收涉及的两种内核线程：
1)????? Kswapd内核线程在内存区中检测空闲页面是否低于pages_high的门槛值；
2)????? 预定义工作队列中的事件内核线程，PFRA周期性调度该工作队列中的task回收slab分配器中所有空闲的slab；
?
所有用户空间进程和页面缓存的页面被分为活动链表和非活动链表，统称LRU链表。每个区描述符中包括active_list和inactive_list两个链表分别将这些页面链接起来。nr_active和nr_inactive分别表示这两种页面数量，lru_lock用于同步。页描述符中的PG_lru用于标志一个页面是否属于LRU链表，PG_active用于标志页面是否属于活动链表，lru字段用于把LRU中的链表串起来。活动链表和非活动链表的页面根据最近的访问情况进行动态调整。PG_referenced标志就是此用途。
处理LRU链表的函数有：
add_page_to_active_list()、add_page_to_inactive_list()、activate_page()、lru_cache_add()、lru_cache_add_active()等，这些函数比较简单。
shrink_active_list ( )用于将页表从活动链表移到非活动链表。该函数在shrink_zone()函数执行用户地址空间的页面回收时执行。
?
5．交换分区：
系统可以有MAX_SWAPFILES的交换分区，每个分区可放在磁盘分区上或者普通文件里。每个交换区由一系列页槽组成。每个交换区有个swap_header结构描述交换区版本等信息。每个交换区有若干个swap_extent组成，每个swap_extent是连续的物理区域。对于磁盘交换区只有一个swap_extent，对于文件交换区则由多个swap_extent组成，因为文件并不是放在连续的磁盘块上的。mkswap命令可以创建交换分区。
图 交换分区结构
?
图 交换页结构
swp_type() 和swp_offset()函数根据页槽索引和交换区号得到type和offset值，函数 swp_entry(type,offset)得到交换槽。最后一位总是清0表示页不在RAM上。槽最大224(64G)。第一个可用槽索引为1。槽索引不能全为0。
一个页面可能被多个进程共用，它可能被从一个进程地址空间换出但仍然在物理内存上，因此一个页面可能被多