Linux内核设计与实现(16)--页高速缓存和页回写

页高速缓存(cache)，是指Linux内核实现磁盘缓存，主要用来减少对磁盘I/O操作。

页回写，是指将页高速缓存中的变更数据刷新回磁盘的操作。

磁盘高速缓存之所以在任何现代操作系统中都非常重要，有两个原因：

（1）访问磁盘速度要远远低于访问内存速度—ms和ns，几个数量级的差距，处理器的L1和L2高速缓存则比内存访问更快；

（2）数据一旦被访问，就很有可能在短期内再次被访问到，即临时局部性原理。如果在第一次访问数据时就缓存它，就极有可能在短期内再次被高速缓存命中。

1. 缓存手段

页高速缓存是由内存中物理页面组成的，内容对应磁盘上的物理块。页高速缓存大小可以根据占用空闲内存动态调整。

缓存命中：当内核开始一个读操作，首先会检查需要的数据是否在页高速缓存中，如果在，就放弃访问磁盘，直接从内存读取，称为缓存命中。反之，若数据没在缓存中，称为缓存未命中，那么内核必须调度块I/O操作从磁盘去读取数据。

系统并不一定将整个文件缓存，缓存可以持有某个文件的全部内容，也可以存储其他文件的一页或多页，该缓存谁取决于谁被访问到。

1.1 写缓存：一般有三种策略

①nowrite, 不缓存：数据直接跳过缓存，写到磁盘，同时使缓存中的数据失效。这个策略很少用，因为不但不缓存写操作，还要额外费力使缓存数据失效。

②write-through cache, 写透缓存：写操作直接写到磁盘，同时跟新内存缓存，这样数据时刻和后备存储保持同步。

③回写，Linux采用的：写操作直接写到缓存中，后端存储不立刻更新，而是将页高速缓存中被写入的页面标记为“脏”，并被加入到脏页链表中。然后由一个回写进程周期的将脏页链表中的页写回到磁盘，最后清理“脏”页标识。通过延迟写磁盘，方便在以后的时间内合并更多的数据和再一次刷新，代价是复杂度很高。

1.2 缓存回收

缓存算法另一个重要内容是，缓存中的数据如何清除，即替换缓存中内容的策略，称为缓存回收策略。Linux的缓存回收是通过选择干净页（不脏）进行简单替换。

如果缓存中没有足够的干净页面，内核将强制性地进行回写操作，以腾出更多的干净可用页。理想的回收策略是应该回收那些以后最不可能使用的页面，理想的回收策略称为预测算法。

（1）最近最少使用

最少使用算法，简称LRU。LRU回收策略需要跟踪每个页面的访问轨迹（比如按时间访问为序的页链表），以便能回收最老时间戳的页面。

该策略良好的效果源自于缓存的数据越久未被访问，则越不大可能近期再被访问，而最近被访问的最优可能被再次访问。但是对于许多文件被访问一次，再不被访问的情景，LRU尤其失败。将这些页面放在LRU链的顶端显然不是最优，但是内核没有办法知道一个文件只会被访问一次，只知道过去访问了多少次。

（2）双链策略

Linux实现的是一个修改过的LRU, 也称为双链策略。Linux维护的不再是一个LRU链表，而是维护两个链表：活跃链表和非活跃链表。

处于活跃链表上的页面被认为是“热”的且不会被换出，而非活跃链表上的页面则是可以换出的。在活跃链表中的页面必须在其被访问时就处于非活跃链表中，两个链表都被伪LRU规则维护：页面从尾部加入，从头部一处，如同队列。两个链表维持平衡，当活跃链表过多超过非活跃链表，那么活跃链表头的页面将被重新移回到非活跃链表中，以便能被回收。双链方式解决了传统LRU算法的仅一次访问问题。这种双链方式叫做LUR/2，更普遍的是n个链表的，称作LRU/n。

2. Linux页告诉缓存

下面介绍具体的数据结构以及内核如何使用它们管理缓存：

2.1 address_space对象

页高速缓存中的页可能包含了多个不连续的物理磁盘块，所以不能用设备名和块号来做缓存数据索引，不然这是最简单的定位方法。

Linux页高速缓存对被缓存的页面范围定义非常宽泛，其目标是缓存任何基于页的对象，这包含各种类型的文件和各种类型的内存映射。

Address_space结构体与虚拟地址vm_area_struct的物理地址对等，当一个文件被多个vm_area_struct结构体标识，只有一个address_space数据结构，即可以有多问虚拟地址，但只能在物理上存一份。

在定义

struct address_space {
    struct inode        *host;        /* owner: inode, block_device */
    struct radix_tree_root    page_tree;    /* radix tree of all pages */
    spinlock_t        tree_lock;    /* and lock protecting it */
    unsigned int        i_mmap_writable;/* count VM_SHARED mappings */
    struct prio_tree_root    i_mmap;        /* tree of private and shared mappings */
    struct list_head    i_mmap_nonlinear;/*list VM_NONLINEAR mappings */
    spinlock_t        i_mmap_lock;    /* protect tree, count, list */
    unsigned int        truncate_count;    /* Cover race condition with truncate */
    unsigned long        nrpages;    /* number of total pages */
    pgoff_t            writeback_index;/* writeback starts here */
    const struct address_space_operations *a_ops;    /* methods */
    unsigned long        flags;        /* error bits/gfp mask */
    struct backing_dev_info *backing_dev_info; /* device readahead, etc */
    spinlock_t        private_lock;    /* for use by the address_space */
    struct list_head    private_list;    /* ditto */
    struct address_space    *assoc_mapping;    /* ditto */
    struct mutex        unmap_mutex; /* to protect unmapping */
} __attribute__((aligned(sizeof(long))));

i_mmap字段是一个有限搜索树，搜索范围包含了在address_space中所有共享的与私有的映射页面。I_mmap字段可帮助内核高效地找到关联的被缓存文件。

address_space结构往往会和某些内核对象关联，通常情况下，它会与一个索引节点关联，host域指向该索引节点。若不是索引节点，就设置为NULL。

2.2 address_sapce操作

a_ops域指向地址空间对象中的操作函数表在定义

struct address_space_operations {
    int (*writepage)(struct page *page, struct writeback_control *wbc);
    int (*readpage)(struct file *, struct page *);
    void (*sync_page)(struct page *);

    /* Write back some dirty pages from this mapping. */
    int (*writepages)(struct address_space *, struct writeback_control *);

    /* Set a page dirty. Return true if this dirtied it */
    int (*set_page_dirty)(struct page *page);

    int (*readpages)(struct file *filp, struct address_space *mapping,
            struct list_head *pages, unsigned nr_pages);

    int (*write_begin)(struct file *, struct address_space *mapping,
                loff_t pos, unsigned len, unsigned flags,
                struct page **pagep, void **fsdata);
    int (*write_end)(struct file *, struct address_space *mapping,
                loff_t pos, unsigned len, unsigned copied,
                struct page *page, void *fsdata);

    /* Unfortunately this kludge is needed for FIBMAP. Don't use it */
    sector_t (*bmap)(struct address_space *, sector_t);
    void (*invalidatepage) (struct page *, unsigned long);
    int (*releasepage) (struct page *, gfp_t);
    ssize_t (*direct_IO)(int, struct kiocb *, const struct iovec *iov,
            loff_t offset, unsigned long nr_segs);
    int (*get_xip_mem)(struct address_space *, pgoff_t, int,
                        void **, unsigned long *);
    /* migrate the contents of a page to the specified target */
    int (*migratepage) (struct address_space *,
            struct page *, struct page *);
    int (*launder_page) (struct page *);
    int (*is_partially_uptodate) (struct page *, read_descriptor_t *,
                    unsigned long);
    int (*error_remove_page)(struct address_space *, struct page *);
};

这些方法指针指向那些为指定缓存对象实现的页I/O操作，每个后备存储都通过自己的address_space_operation描述自己如何与页高速缓存交互，比如ext3文件系统在文件fs/ext3/inode.c中定义自己的操作表，这些方法提供了管理页高速缓存的各种行为。

一个页面的读操作过程如下：

首先Linux内核试图在页高速缓存中找到需要的数据，find_get_page()方法负责完成这个检查动作，index为偏移量

page = find_get_page(mapping, index);

mapping是指定的地址空间，index指定位置，返回页所在位置，若搜索页不在高速缓存中，返回NULL.，并且内核将分配一个新页面，然后将该搜索页加入到页高速缓存中。

Linux中所有的页I/O操作都是通过页高速缓存进行的。

2.3 基树

因为任何页I/O操作前，内核都要检查页是否已经在页高速缓存中，所以这种频繁进行的检查必须迅速、高效，否则搜索和检查页高速缓存的开销可能抵消页高速缓存带来的好处。（至少在缓存命中率很低的时候，是这样）

每个address_space对象都有一个唯一的基树(radix tree)，它保存在page_tree结构体中，基树是一个二叉树，只要指定了文件偏移量，就可以在基树中快速查找到希望的页。页高速缓存搜索函数find_get_page()会调用radix_tree_lookup()，该函数会在指定基树中搜索指定页面。（基树核心代码在lib/radix-tree.c定义）

2.4 以前的页散列表

2.6以前的版本，内核页高速缓存不是通过基树检索，而是维护了一个系统中所有页的全局散列表进行检索。对于一个给定的键值，如果页存储在缓存中，那么散列表中的一项会与其对应，如果页不再缓存中，散列函数返回null。

使用全局散列表主要存在四个问题：

1）由于使用单个的全局锁保护散列表，所以即使在中等规模的机器中，锁的争用情况也会相当严重，造成性能受损。

2）散列表需要包含所有页高速缓存中的页，可是搜索需要的只是和当前文件相关的那些页，所以散列表包含的页面相比搜索需要的页面要大得多

3）如果散列搜索失败，指向速度比希望的要慢得多，因为检索必须遍历指定散列键值对应的整个链表

4）散列表比其他方法会消耗更多内存。

2.6版本内核引入基于基树的页高速缓存，解决了这些问题。

3. 缓冲区高速缓存

2.4之前的内核中，有两个独立的磁盘缓存：页高速缓存和缓冲区高速缓存。一个磁盘块可以同时存于两个缓存中，这样导致必须同步操作两个缓存区，而且浪费了内存。

现在独立的磁盘块通过块I/O缓冲，也要被存入页高速缓存。通过缓存，磁盘块映射到它们相关的内存页，并缓存到高速缓存中。虽然如此，内核仍然需要在内存中使用缓冲来表示磁盘块。

4. flusher线程

由于页高速缓存的缓存作用，写操作实际上会被延迟。当页高速缓存中的数据比后台存储数据更新时，该数据就称作脏数据。在内存中累积起来的脏页最总必须被写回磁盘，在以下3中情况发生时，脏页被写回磁盘：

1）当空闲内存低于一个特定的阈值时，内核必须将脏页写回磁盘以便释放内存，因为只有干净（不脏的）内存才可以被回收。

2）当脏页在内存中驻留时间超过一个特定的阈值时，内核必须将超时的脏页写回磁盘，以确保脏页不会无限期地驻留在内存中。

3）用户进程调用sync()和fsync()系统调用时，内核会执行写回操作。

以上三个工作，旧内核中是由两个独立的内核线程分别完成的，在2.6内核中，由一群内核线程（flusher线程）执行这些工作。

首先，当空闲内存比dirty_background_ratio（这个阈值可以通过dirty_background_ratio sysctl系统调用设置）还低时，内核便会调用函数flusher_threads()唤醒一个或多个flusher线程，随后进一步调用bdi_writeback_all()开始将脏页写回磁盘，该函数需要一个参数—试图写回的页面数目，函数连续地写出数据，直到满足以下条件（除非没有剩下的脏页可被写回了）：

①已经有指定的最小数目的页被写出到磁盘

②空闲内存已经回升，超过了阈值dirty_background_ratio.

第二个目标，flusher线程后台例程会被周期性唤醒（和空闲内存是否过低无关），将那些在内存中驻留时间过长的脏页写出，确保内存中不会有长期存在的脏页。这样减少了系统崩溃时，内粗中还没写回的脏页的丢失。

系统管理员可以在/proc/sys/vm中设置回写相关的函数，也可以通过sysctl系统调用设置它们，pdflush相关的所有可设置变量如下：

flusher线程在文件mm/page-writeback.c和mm/backing-dev.c中，回写机制实现在fs/fs-writeback.c中。

4.1膝上型计算机模式

膝上型计算机模式是一种特殊的页回写策略，该策略主要意图是将硬盘转动的机械行为最小化，允许硬盘尽可能长时间的停滞，以此延长点此观点时间。该模式通过proc/sys/vm/laptop_mode文件配置，通常该配置文件内容为0，就是说膝上型计算机模式关闭，如果需要启用膝上型计算机模式，则向配置文件中写入1.

回写行为变化要求dirty_expire_internval和dirty_writeback_interval两阈值必须设置的更大，比如10分钟。因为磁盘运转不频繁，所以可以省电，但是系统崩溃时会丢失数据。

多数Linux发布版本会在计算机接上或拔下电池时，自动开启或关闭膝上型计算机模式及其它需要的回写可调制开关。当机器使用电源时，自动进入膝上型计算机模式，而在插上交流电源时回复到常规的回写模式。

4.2历史上的bdflush, kupdated和pdflush

在2.6版本前，flusher线程的工作分别由bdflush和kupdated两个线程共同完成。

当内存过低时，wakeup_bdflush()函数唤醒bdflush内核线程，在后台执行脏页回写操作。

bdflush和当前的flusher线程之间存在两个主要区别：

①系统中只有一个bdflush后台线程，而flusher线程数目是根据磁盘数量变化的。

②bdflush线程基于缓冲，它将脏缓冲写回磁盘，而flusher线程基于页面，将整个页写回磁盘。

kupdated例程周期性的写回脏页，它和pdflush线程的wb_writeback()函数提供同样的服务。

2.6内核中，bdflush和kupdated已经被pdflush（page dirty flush）线程取代。Pdflush线程的执行和今天的flusher线程类似，主要区别在于，pdflush线程数目是动态的，默认2到8个，具体多少取决于系统I/O负载。

pdflush线程与任何任务都无关，它们是面向系统所有磁盘的全局任务，这样做的好处是实现简单，但是pdflush线程很容易在拥塞的磁盘上绊住，而现代硬件拥塞是家常便饭。采用每个磁盘一个刷新线程可以使得I/O操作同步执行，简化了拥塞逻辑，页提高了性能。Flusher线程在2..6.32内核系统中取代了pdflush线程。

4.3避免拥塞的方法：使用多线程

使用bdflush线程最主要的一个缺点是，bdflush仅包含了一个线程，因此很有可能在页回写任务重时，造成拥塞。因为单一的线程有可能堵塞在某个设备的已拥塞请求队列上，而其他设备的请求队列却没法得到处理。单个bdflush线程也可能会堵塞在某个队列的处理上，不能使所有磁盘都处于饱和工作状态。

pdflush线程策略中，线程数是动态变化的，每一个线程试图尽可能忙地从每个超级块的脏页链表中回收数据，并且写回磁盘，这种方式避免了因为一个忙磁盘，而是的其余磁盘饥饿的情况。通常情况下这样是不错的，但是如果每个pdflush线程在同一个拥塞的队列上挂起了呢，这时多个pdflush不比单个线程好，为了减轻上诉影响，pdflush线程采用了拥塞回避策略：它们会主动尝试从那些没有拥塞的队列回写页，从而pdflush线程将其工作调度开来，防止了仅仅欺负某一个忙碌设备。

这种方式效果确实不错，但是拥塞回避并不完美，在现代操作系统中，因为I/O总线技术比其他部分相对发展缓慢，很多情况下，pdflush确实可以避免下个特定磁盘回写时间和期望时间和期望时间相对太久。当前的flusher线程模型和具体块设备关联，所以每个给定线程从每个给定设备的脏页链表收集数据，并写回到对应磁盘，回写更趋于同步了。并且由于每个磁盘对应一个线程，所以线程不需要采用复杂的拥塞避免策略。该方法提高了I/O操作的公平性，而且降低了饥饿风险。