深入理解页交换算法：优化内存管理的关键

转自：深度Linux

页交换算法，也称为页面置换算法，是操作系统中用于管理虚拟内存的重要组成部分。当物理内存不足时，操作系统需要将部分页面（或者称为页）从内存中交换到磁盘上，以释放出空间供其他页面使用。

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

一、概述

• 在Linux操作系统中，当内存充足时，内核会尽量多地使用内存作为文件缓存（page cache）， 从而提高系统的性能。文件缓存页面会添加到文件类型的LRU链表中；当内存紧张时，文件缓存页面会被丢弃，或者把修改的文件缓存页面回写到存储设备中，与块设备同步之后便可释放出物理内存。

• 现在的应用程序转向内存密集型，无论系统中有多少物理内存都是不够用的，因此Linux操作系统会使用存储设备作为交换分区，内核将很少使用的内存换出到交换分区，以便释放出物理内存，这个机制称为页交换（swapping），这些处理机制统称为页面回收（page reclaim）。

• 在最近几十年操作系统的发展过程中，出现了很多页面交换算法，其中每个算法都有各自的优点和缺点。

• Linux内核中采用的页交换算法主要是经典LRU链表算法和第二次机会（second chance）法。

页面置换过程

页面置换的工作流程如图所示，主要包括以下4个步骤：

• 第1步：找出所需页面在磁盘上的位置。

• 第2步：找出一个空闲内存块。如果有空闲块，就用它；如果没有空闲块，就用页面置换算法选择一个可置换的内存块，把该页写到磁盘上，并相应地修改页表和存储块表。

• 第3步：把所需页面读入刚刚得到的内存空闲块，修改页表和存储块表。

• 第4步：重新启动该用户进程。

  

页面走向

• 置换算法的好坏直接影响系统的性能。若采用的置换算法不合适，可能出现这样的现象：刚被换出的页，很快又被访问，为把它调入而换出另一页，之后又访问刚被换出的页，……如此频繁地更换页面，以致系统的大部分时间花费在页面的调度和传输上。此时，系统好像很忙，但实际效率却很低。这种现象称为“抖动”。

• 好的页面置换算法能够适当降低页面更换频率（减少缺页率），尽量避免系统“抖动”。

• 为评价一个算法的优劣，可将该算法应用于一个特定的存储访问序列（也叫页面走向）上，并且计算缺页数量。

二、最佳置换算法（OPT）

• 最佳置换算法，其所选择的被淘汰的页面将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常可保证最低的缺页率。但是人们目前还无法与之，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是可以利用该算法取评价其他的算法。

算法思想

举例如下：

• 我们将页面队列存在一个Vector动态数组中。我们可以从图中得知：当发生页面置换时，就要寻找在未来最长时间内不再被访问的页面，将其置换出去，比如当内存中存在的页面为 7、0、1,且要访问页面2时，此时我们要寻找页面队列中将要访问到的页面2以后的页面队列（0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1）中，页面7、0、1哪个最久未被访问到，即寻找页面7、0、1在以后的队列中第一次出现的这三个页面的下标值最大的那一个。
• 因为页面7在后面的页面队列中再次被访问到是数组中下标为17的地方,页面0再次被访问到是数组下标为4的地方，页面1再次被访问的是数组中下标为13,所以页面7是未来最久才被访问的页面，所以将页面7置换出去，将页面2调入内存中。

具体算法

• 每个页面都有两个属性，一个是页面号id，一个是时间参数count（此属性在LRU中才会用到）

//pageId 要调入内存的页面号
//currentPoint 记录当前将要调入内存中页面所在页面队列中的下标号
void OPT::replace(int pageId, int currentPoint) {
    //cur为内存块下标,searchCounter纪录是否内存块搜索完毕
    //循环爆出最长为使用的页面
    int max = 0, perCount, outPageId = -1, cur = 0;
    int search_count[PRO_MEMORY];

    for (int i = 0; i < PRO_MEMORY; i++) {
    	//比如，从页面2后面的页面开始扫描记录页面7、0、1再次被访问的数组的下标号
        for (int j = currentPoint + 1; j < length; j++) {
            if (pages_OPT[i].getId() == usePageNumList_OPT[j]) {
                search_count[i] = j;
                break;
            }
        }
        if (search_count[i] == 0) {
            search_count[i] = length;
        }
    }
    //以上面内存中存在的是页面7、0、1为例。寻找页面7、0、1再次被访问的下标号最大的    //哪个页面
    for (int k = 0; k < PRO_MEMORY; ++k) {
        perCount = search_count[k];
        if (max < perCount) {
            max = perCount;
            cur = k;
        }
    }

    outPageId = pages_OPT[cur].getId();

    pages_OPT[cur].setId(pageId);
    cout << "页号ID：" << pageId << "正在放入内存，页号ID：" << outPageId << "被替换出去" << endl;
    ofs_OPT << "页号ID：" << pageId << "正在放入内存，页号ID：" << outPageId << "被替换出去\n";
}

###运行结果截图

三、先进先出法(FINO)

• 页面替换算法是操作系统中用于解决内存不足的问题的一种算法。在实现时，可将内存在等大块，称作页面，将进程所需的内存也分成等大的块，即页，当进程访问一个新页时，若内存已满，则需要选择一个已驻留的页，将其后备存储设备中的内容读入内存中，以使新页能够进入内存。页面替换算法中的「组 2」指的是先进先出算法（FIFO）。

• 这是最简单的页面替换算法。在该算法中，操作系统跟踪队列中内存中的所有页面，最旧的页面在队列的前面。当一个页面需要被替换时，队列前面的页面被选中进行删除。

• 示例-1。考虑页面引用字符串1、3、0、3、5、6 和 3 页槽。

• 最初所有的槽都是空的，所以当 1、3、0 到来时，它们被分配到空槽——> 3页错误。 当 3 出现时，它已经在内存中，所以 —> 0 Page Faults。然后是 5，它在内存中不可用，因此它替换了最旧的页槽，即 1。—>1页错误。 最后是 6，它在内存中也不可用，因此它替换了最旧的页槽，即 3 —>1页错误。

算法实现

• FIFO 算法简单易懂，实现方便。它基于队列数据结构来实现，将最先进入队列的页面置换出去，以便腾出空间给新页面使用。这里给出 FIFO 页面替换算法的示例代码

#include <iostream>
#include <queue>
using namespace std;

int FIFO(int pages[], int n, int capacity) {
    queue<int> pageQueue; 	// 用于存储页面的队列
    int pageFaults = 0; 	// 页面错误次数

    for (int i = 0; i < n; i++) {
        if (pageQueue.size() < capacity) { // 队列未满时直接插入页面
            if (!pageQueue.empty() && pageQueue.front() == pages[i]) {
                continue;
            }
            pageQueue.push(pages[i]);
            pageFaults++;
        } else { // 队列已满，进行页面替换
            if (pageQueue.front() != pages[i]) {
                pageQueue.pop();
                pageQueue.push(pages[i]);
                pageFaults++;
            }
        }
    }
    
    return pageFaults;
}

int main() {
    int pages[] = {2, 3, 1, 4, 5, 2, 1}; 		// 页面引用序列
    int n = sizeof(pages) / sizeof(pages[0]); 	// 页面引用序列长度
    int capacity = 3; 							// 页面帧数

    int faults = FIFO(pages, n, capacity);
    cout << "Total Page Faults: " << faults << endl;

    return 0;
}

• 这个示例使用了一个队列来模拟内存中的页面帧，当队列未满时直接插入页面，当队列已满时进行页面替换。每次发生页面错误（即访问不在内存中的页面）时，计数器增加。最后输出总的页面错误次数。

算法分析

• FIFO 页面替换算法的优点是简单易懂，实现方便。它不需要对进程访问的页面做特定的访问规划，因此适用于任何进程。另外，由于 FIFO 算法严格按照页面进入内存的顺序进行替换，所以可以保证每个页面的等待时间相同，避免了某些页面总是被替换的问题。

• 然而，FIFO 页面替换算法也存在明显的缺陷。由于该算法只关注页面进入内存的时间，而未考虑各页面的重要性和使用频率，因此会导致某些频繁使用的页面被不必要地替换出去，从而降低系统的性能。此外，FIFO 算法还容易受到局部性原理的影响，即刚刚被访问的页面很可能很快再次被访问，但由于 FIFO 算法只考虑页面进入内存的时间，因此可能导致这些重要页面被替换出去。

四、经典LRU链表算法

• LRU是Least Recently Used的缩写，意为最近最少使用。根据局部性原理，LRU假定最近不使用的页面在较短的时间内也不会频繁使用。在内存不足时，这些页面将成为被换出的候选者。内核使用双向链表来定义LRU链表，并且根据页面的类型将LRU链表分为LRU_ANON和LRU_FILE。每种类型根据页面的活跃性分为活跃LRU链表和不活跃LRU链表，所以内核中一共有如下5个LRU链表：

// 定义了各种 LRU 链表的类型
enum lru_list {
	// 不活跃匿名页面链表
    LRU_INACTIVE_ANON = LRU_BASE,
    // 活跃匿名页面链表
	LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
    // 不活跃文件映射页面链表
	LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
    // 活跃文件映射页面链表
	LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
    // 不可回收页面链表
	LRU_UNEVICTABLE,
	NR_LRU_LISTS
};

• LRU链表之所以要分成这样，是因为当内存紧缺时总是优先换出文件映射的文件缓存页面 （LRU_FILE链表中的页面），而不是匿名页面。因为大多数情况下，文件缓存页面不需要被回写到磁盘，除非页面内容修改了（称为脏页），而匿名页面总是要在写入交换分区之后，才能被换出。LRU链表按照内存节点配置，也就是说，每个内存节点中都有一整套LRU链表，因此内存节点的描述符数据结构（pglist_data）中有一个成员lruvec指向这些链表。枚举类型变量lru_list 列举出上述各种LRU链表的类型，lruvec数据结构中定义了上述各种LRU类型的链表：

// 定义了各种 LRU 链表
struct lruvec {
	struct list_head		lists[NR_LRU_LISTS];
	...
};

// 内存节点的数据结构
typedef struct pglist_data {
	// 每个内存节点中都有一整套 LRU 链表，由 lruvec 指向
	struct lruvec		lruvec;
} pg_data_t;

万事从图说起，经典LRU链表算法如下图所示：

为了使读者有更真切的理解，下文将根据流程图围绕源代码进行讲解这个过程：

将页面加入 LRU 链表

static void __lru_cache_add(struct page *page) {
	// 这里使用了页向量数据结构，借助一个数组来保存特定数目的页，可以对这些页面执行同样的操作
	// 页向量会以“批处理的方式”执行，比单独处理一个页面的方式效率要高
	struct pagevec *pvec = &get_cpu_var(lru_add_pvec);

	get_page(page);
	// pagevec_add() 函数首先往 pvec->pages[] 数组里添加页面，
	// 如果没有空间了，则调用 __pagevec_lru_add() 函数把原有的页面添加到 LRU 链表中
	if (!pagevec_add(pvec, page) || PageCompound(page))
		__pagevec_lru_add(pvec);
	put_cpu_var(lru_add_pvec);
}

void lru_cache_add(struct page *page) {
	...
	__lru_cache_add(page);
}

• lru_to_page(&lru_list)和list_del(&page->lru)函数的组合用于从LRU链表中获取页面。其中，lru_to_page()的实现如下：

#define lru_to_page(head) (list_entry((head)->prev, struct page, lru))

• lru_to_page()使用了(head)->prev，表示从链表的末尾获取页面。因此，LRU链表实现了 FIFO算法。最先进入LRU链表的页面在LRU中的时间会越长，老化时间也越长。

• 在系统执行过程中，页面总是在活跃LRU链表和不活跃LRU链表之间转移，不是每次访问内存页面都会发生这种转移，而是发生的时间间隔比较长。随着时间的推移，这会导致—种热平衡，最不常用的页面将慢慢移动到不活跃LRU链表的末尾，这些页面正是页面回收中最合适的候选者。

五、时钟置换算法

• 时钟置换算法可以认为是一种最近未使用算法，即逐出的页面都是最近没有使用的那个。我们给每一个页面设置一个标记位u，u=1表示最近有使用u=0则表示该页面最近没有被使用，应该被逐出。

• 按照1-2-3-4的顺序访问页面，则缓冲池会以这样的一种顺序被填满：

  

• 注意中间的指针，就像是时钟的指针一样在移动，这样的访问结束后，缓冲池里现在已经被填满了，此时如果要按照1-5的顺序访问，那么在访问1的时候是可以直接命中缓存返回的，但是访问5的时候，因为缓冲池已经满了，所以要进行一次逐出操作，其操作示意图如下：

  

• 最初要经过一轮遍历，每次遍历到一个节点发现u=1的，将该标记位置为0，然后遍历下一个页面，一轮遍历完后，发现没有可以被逐出的页面，则进行下一轮遍历，这次遍历之后发现原先1号页面的标记位u=0，则将该页面逐出，置换为页面5，并将指针指向下一个页面。 假设我们接下来会访问2号页面，那么可以直接命中指针指向的页面，并将这个页面的标记为u置为1。
  但是考虑一个问题，数据库里逐出的页面是要写回磁盘的，这是一个很昂贵的操作，因此我们应该优先考虑逐出那些没有被修改的页面，这样可以降低IO。 因此在时钟置换算法的基础上可以做一个改进，就是增加一个标记为m，修改过标记为1，没有修改过则标记为0。那么u和m组成了一个元组，有四种可能，其被逐出的优先顺序也不一样：

  • (u=0, m=0) 没有使用也没有修改，被逐出的优先级最高；

  • (u=1, m=0) 使用过，但是没有修改过，优先级第二；

  • (u=0, m=1) 没有使用过，但是修改过，优先级第三；

  • (u=1, m=1) 使用过也修改过，优先级第四。

六、总结

1. 基于局部性原理：根据程序执行的局部性原理，有时会发现页面的访问模式并不是完全随机的，而是存在一定的顺序性。因此，可以尝试基于这种局部性原理进行优化。例如，可以使用预取算法（如预读取、预测等）来提前将可能被访问到的页面加载到内存中。
2. 适应工作集模型：工作集模型指出一个进程在某个时间段内所访问的页面集合称为其工作集。通过了解每个进程的工作集情况，可以更好地管理和调度内存资源。例如，在缺页中断发生时，优先选择属于当前进程工作集中页面进行置换。
3. 页面替换策略：不同的页面替换算法对于不同的场景和工作负载具有不同的表现。常见的页面替换算法包括最近最少使用（LRU）、最不经常使用（LFU）、时钟（Clock）等。选择合适的页面替换策略可以显著影响性能。
4. 聪明地设置页面大小：页面大小对页交换算法也有一定影响。较小的页面大小可能导致更多的内存碎片和更频繁的页面置换，而较大的页面大小可能导致更多的内存浪费。因此，需要根据系统的实际情况和工作负载来选择合适的页面大小。
5. 压缩技术：压缩技术可以通过减小页面占用的物理内存空间来优化页交换算法。当一个页面被置换出去时，如果其内容能够进行压缩，则可以节省一定数量的物理内存空间。
6. 多级页表和反向页表：对于大型内存系统，使用多级页表或反向页表可以减少页表占用的内存空间，并加快查找某个虚拟地址对应的物理地址所需时间。