swapping

说明：本文中介绍的内核版本为2.6.11

名词汇总：

  1. 交换区(swap area)
  2. 页槽(page slot)
  3. swap in (换入)：是指页面从交换分区转移到内存之中
  4. swap out (换出)：是指页面从内存转移到交换分区中
  5. PFRA(page frame reclaiming algorithm)
  6. 交换子区(swap extent)

swapping子系统的主要功能总结如下:

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

交换区

从内存中换出的页存放在交换区(swap area)中，交换区的实现可以使用磁盘分区，也可以使用包含在大型分区中的文件。可以定义多个交换区，最大个数由MAX_SWAPFILES宏(通常被设置为32)确定。

每个交换区都由一组页槽(page slot)组成，也就是说，由一组4096字节大小的块组成，每块中包含一个换出的页。交换区的第一个页槽用来永久存放有关交换区的信息。

创建与激活交换区

通常，系统管理员在创建Linux系统中的其他分区时都创建一个交换分区，然后使用mkswap命令把这个磁盘区设置成一个新的交换区。该命令对刚才介绍的第一个页槽中的字段进行初始化。由于磁盘中可能会有一些坏块，这个程序还可以对其他所有的页槽进行检查从而确定有缺陷页槽的位置。但是执行mkswap命令会把交换区设置为非激活状态。每个交换区都可以在系统启动时在脚本文件中被激活，也可以在系统执行之后动态激活。
每个交换区都由一个或者多个交换子区(swap extent)组成，每个交换子区由一个
swap_extent描述符表示，每个子区对应一组页槽，它们在磁盘上是物理相邻的。当激活交换区自身的同时，组成交换区的有序子区链表也被创建。存放在磁盘分区中的交换区只有一个子区；但是存放在普通文件中的交换区则可能有多个子区，这是因为文件系统有可能没把该文件全部分配在磁盘的一组连续块中。

如何在交换区中分布页

当换出时，内核尽力把换出的页存放在相邻的页槽中，从而减少在访问交换区时磁盘的寻道时间，这是高效交换算法的一个重要因素。

交换区描述符

每个活动的交换区在内存中都有自己的swap_info_struct描述符，其结构如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
 * The in-memory structure used to track swap areas.
 * extent_list.prev points at the lowest-index extent.  That list is
 * sorted.
 */
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_swap_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;// 交换区优先级
	int pages;//可用页槽的个数
	unsigned long max;//交换区的大小，以页为单位
	unsigned long inuse_pages;//交换区内已用页槽数
	int next;// 指向下一个交换区描述符的指针
};

swap_map字段指向一个计数器数组，交换区的每个页槽对应一个元素。如果计数器值等于０，那么这个页槽就是空闲的；如果计数器为正数，那么换出页就填充了这个页槽，实际上，页槽计数器的值就表示共享换出页的进程数；如果计数器的值是
SWAP_MAP_BAD(等于32768)，那么就认为这个页槽是有缺陷的，也就是不可用的。
swap_info数组包括MAX_SWAPFILES个交换区描述符。

下图说明了swap_info数组、一个交换区和相应的计数器数组的情况。

换出页标识符

可以很简单地而又唯一地标志一个换出页，这是通过swap_info数组中指定交换区的索引和在交换区内指定页槽的索引实现的。由于交换区的第一个页(索引为0)用来存放有关交换区的信息，第一个可用页槽的索引就为1。换出页标识符的格式如下图所示:

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

  • 空项:该页相应的页框还没有分配给进程
  • 前31个最高位不全等于0，最后一位等于0:该页现在被换出
  • 最低位等于１:该页包含在RAM中

激活和禁用交换区

一旦交换区被初始化，超级用户就可以分别使用swapon 和swapoff 程序激活和禁用交换区，这两个程序分别使用了swapon()和swapoff()系统调用。

分配和释放页槽

在释放内存时，内核要在很短的时间内把很多页都交换出去。因此尽力把这些页存放在相邻的页槽中非常重要，这样就可以减少在访问交换区时磁盘的寻道时间。

swap cache

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

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

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

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

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

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

换出页

  1. 向swap cache插入页框
  2. 更新页表项
  3. 将页写入交换区
  4. 从swap cache中删除页框

换入页

当进程试图对一个已被换出的页进行寻址时，必然会发生页的换入。在以下条件全满足时，缺页异常处理程序会触发一个换入操作:

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

如果上面的所有条件满足，则handle_pte_fault()调用do_swap_page()函数换入所需的页。

参考资料：

  1. 《深入理解LINUX内核》第十七章第４节