第7节 缓存和刷新机制

6.7.1 Linux使用的缓存

不管在硬件设计还是软件设计中，高速缓存是获得高性能的常用手段。Linux 使用了多种和内存管理相关的高速缓存。

1． 缓冲区高速缓存：

缓冲区高速缓存中包含了由块设备使用的数据缓冲区。这些缓冲区中包含了从设备中读取的数据块或写入设备的数据块。缓冲区高速缓存由设备标识号和块标号索引，因此可以快速找出数据块。如果数据能够在缓冲区高速缓存中找到，则系统就没有必要在物理块设备上进行实际的读操作。

内核为每个缓冲区维护很多信息以有助于缓和写操作，这些信息包括一个“脏（dirty）”位，表示内存中的缓冲区已被修改，必须写到磁盘；还包括一个时间 标志，表示缓冲区被刷新到磁盘之前已经在内存中停留了多长时间。因为缓冲区的有关信息被保存在缓冲区首部，所以，这些数据结构连同用户数据本身的缓冲区都 需要维护。

缓冲区高速缓存的大小可以变化。当需要新缓冲区而现在又没有可用的缓冲区时，就按需分配页面。当空闲内存变得不足时，例如上一节看到的情况，就释放缓冲区并反复使用相应的页面。

2． 页面高速缓存

页面高速缓存是页面I/O操作访问数据所使用的磁盘高速缓存。我们在文件系统会看到，read( )、write( )和mmap( )系统调用对常规文件的访问都是通过页面高速缓存来完成的。因为页面I/O操作要传输整页数据，因此高速缓存中所保留的信息单元是一个整页面。一个页面包 含的数据未必是物理上相邻的磁盘块，因此就不能使用设备号和块号来标识页面。相反，页面高速缓存中一个页面的标识是通过文件的索引节点和文件中的偏移量达 到的。

与页面高速缓存有关的操作主要有三种：当访问的文件部分不在高速缓存中时增加一页面，当高速缓存变得太大时删除一页面，以及查找一个给定文件偏移量所在的页面。

3．交换高速缓存

只有修改后的（脏）页面才保存在交换文件中。修改后的页面写入交换文件后，如果该页面再次被交换但未被修改时，就没有必要写入交换文件，相反，只需丢弃该 页面。交换高速缓存实际包含了一个页面表项链表，系统的每个物理页面对应一个页面表项。对交换出的页面，该页面表项包含保存该页面的交换文件信息，以及该 页面在交换文件中的位置信息。如果某个交换页面表项非零，则表明保存在交换文件中的对应物理页面没有被修改。如果这一页面在后续的操作中被修改，则处于交 换缓存中的页面表项被清零。 Linux 需要从物理内存中交换出某个页面时，它首先分析交换缓存中的信息，如果缓存中包含该物理页面的一个非零页面表项，则说明该页面交换出内存后还没有被修改 过，这时，系统只需丢弃该页面。

这里给出有关交换缓存的部分函数及功能：位于/ linux/mm/swap_state.c 中。

初始化交换缓冲，设定大小，位置的函数：

extern unsigned long init_swap_cache(unsigned long, unsigned long);

显示交换缓冲信息的函数：

extern void show_swap_cache_info(void);

加入交换缓冲的函数：

int add_to_swap_cache(unsigned long index, unsigned long entry)

参数index是进入缓冲区的索引（index是索引表中的某一项），entry是‘页面表项’（即此页面在交换文件中的位置记录，这个记录类似页面表项，参见交换机制）

复制被换出的页面：

extern void swap_duplicate(unsigned long);

当使用copy_page_tables()调用，来实现子进程在fork()时继承被换出的页面，可参阅交换机制一节。

从缓冲区中移去某页面

delete_from_swap_cache(page_nr);

4 硬件高速缓存

常见的硬件缓存是对页面表项的缓存，这一工作实际由处理器完成，其操作和具体的处理器硬件有关（但管理要由软件完成），对这一缓存接下来要进一步描述。

6.7.2 缓冲区高速缓存

Linux 采用了缓冲区高速缓存机制，而不同于其他操作系统的“写透”方式，也就是说，当你把一个数据写入文件时，内核将把数据写入内存缓冲区，而不是直接写入磁盘。

在这里要用到一个数据结构 buffer_head 它是用来描述缓冲区的数据结构，缓冲区的大小一般要比页面尺寸小，所以一页面中可以包含数个缓冲区，同一页面中的缓冲区用链表连接。回忆页面结构 page，其中有一个域buffer_head buffer就是用来指向缓冲区的，这个结构的详细内容请参见虚拟文件系统。

由于使用了缓冲技术，因此有可能出现这种情况：写磁盘的命令已经返回，但实际的写入磁盘的操作还未执行。

基于上述原因，应当使用正常的关机命令关机，而不应直接关掉计算机的电源。用户也可以使用 sync 命令刷新缓冲区高速缓存，从而把缓冲区中的数据强制写到磁盘中。在 Linux 系统中，除了传统的 update 守护进程之外，还有一个额外的守护进程 dbflush，这一进程可频繁运行不完整的 sync 从而可避免有时由于 sync 命令的超负荷磁盘操作而造成的磁盘冻结，一般的情况下，它们在系统引导时自动执行，且每隔30秒执行一次任务。

sync命令使用基本的系统调用sync()来实现。

dbflush 在 Linux 系统中由 update 启动。如果由于某种原因该进程僵死了，则内核会发送警告信息，这时需要手工启动该进程（/sbin/update）。

1. 页面缓存的详细描述。

经内存映射的文件每次只读取一页面内容，读取后的页面保存在页面缓存中，利用页面缓存，可提高文件的访问速度。如图6.19所示，页面缓存由 page_hash_table 组成，它是一个mem_map_t(即struct page 数据结构)的指针向量。页面缓存的结构是 Linux 内核中典型的哈希表结构。众所周知，对计算机内存的线性数组的访问是最快速的访问方法，因为线性数组中的每一个元素的位置都可以利用索引值直接计算得到， 而这种计算是简单的线性计算。但是，如果要处理大量数据，有时由于受到存储空间的限制，采用线性结构是不切合实际的。但如果采用链表等非线性结构，则元素 的检索性能又会大打折扣。哈希表则是一种折衷的方法，它综合了线性结构和非线性结构的优点，可以在大量数据中进行快速的查找。哈希表的结构有多种，在 Linux 内核中，常见的哈希结构和图6.19 的结构类似。要在这种哈希表中访问某个数据，首先要利用哈希函数以目标元素的某个特征值作为函数自变量生成哈希值作为索引，然后利用该索引访问哈希表的线 性指针向量。哈希线性表中的指针代表一个链表，该链表所包含的所有节点均具有相同的哈希值，在该链表中查找可访问到指定的数据。哈希函数的选择非常重要， 不恰当的哈希函数可能导致大量数据映射到同一哈希值，这种情况下，元素的查找将相当耗时。但是，如果选择恰当的哈希函数，则可以在性能和空间上得到均衡效 果。

在 Linux 页面缓存中，访问 page_hash_table 的索引由文件的 VFS（虚拟文件系统）索引节点 inode 和内存页面在文件中的偏移量生成。有关 VFS 索引节点的内容将虚拟文件中讲到，在这里，应知道每个文件的 VFS 索引节点 inode 是唯一的。

图6.19 Linux 页面缓存示意图

当系统要从内存映射文件中读取某一未加锁的页面时，就首先要用到函数：

find_page (struct inode * inode, unsigned long offset)。

它完成如下工作：

首先是在“页面缓存”中查找，如果发现该页面保存在缓存中，则可以免除实际的文件读取，而只需从页面缓存中读取，这时，指向 mm_map_t 数据结构的指针被返回到页面故障的处理代码；部分代码如下：

for (page = page_hash(inode, offset); page ; page = page->next_hash)

/*函数page_hash()是从哈希表中找页面*/

{if (page->inode != inode)

continue;

if (page->offset != offset)

continue;

/* 找到了特定页面 */

atomic_inc(&page->count);

set_bit(PG_referenced, &page->flags);/*设访问位*/

break; }

return page;

}

如果该页面不在缓存中，则必须从实际的文件系统映象中读取页面，这时Linux 内核首先分配物理页面然后从磁盘读取页面内容。

如果可能，Linux 还会预先读取文件中下一页面内容到页面缓存中，而不等页面错误发生才去“请页面”，这样做是为了提高装入代码的速度。(有关代码在filemap.c中， 如generic_file_readahead（）等函数），这样，如果进程要连续访问页面，则下一页面的内容不必再次从文件中读取了，而只需从页面缓 存中读取。

随着映象的读取和执行，页面缓存中的内容可能会增多，这时，Linux 可移走不再需要的页面。当系统中可用的物理内存量变小时，Linux 也会通过缩小页面缓存的大小而释放更多的物理内存页面。

2. 有关页面缓存的函数：

先看把读入的页面如何存于缓存，这要用到函数add_to_page_cache()，它完成把指定的“文件页面”记入页面缓存中。

static inline void add_to_page_cache(struct page * page,

struct inode * inode, unsigned long offset)

{ /*设置有关页面域，引用数，页面使用方式，页面在文件中的偏移 */

page->count++;

page->flags &= ~((1 << PG_uptodate) | (1 << PG_error));

page->offset = offset;

add_page_to_inode_queue(inode, page);/* 把页面加入inode节点队列*/

add_page_to_hash_queue(inode, page);/* 把页面加入哈唏表page_hash_table[]*/}

注：inode的部分请看虚拟文件章节。

哈唏表page_hash_table[]的定义：

extern struct page * page_hash_table[PAGE_HASH_SIZE];

下面是有关对哈唏表操作的部分代码：

static inline void add_page_to_inode_queue(struct inode * inode, struct page * page)

{ struct page **p = &inode->i_pages;/*指向物理页面*/

inode->i_nrpages++;/*节点中调入内存的页面数目增1*/

page->inode = inode; /*指向该页面来自的文件节点结构，相互连成链*/

page->prev = NULL;

if ((page->next = *p) != NULL)

page->next->prev = page;

*p = page; }

把页面加入哈唏表：

static inline void add_page_to_hash_queue(struct inode * inode, struct page * page)

{ struct page **p = &page_hash(inode,page->offset);

page_cache_size++;/*哈希表中记录的页面数目加1*/

set_bit(PG_referenced, &page->flags);/*设置访问位*/

page->age = PAGE_AGE_VALUE;/*设缓存中的页面‘年龄’为定值，为淘汰做准 备*/

page->prev_hash = NULL;

if ((page->next_hash = *p) != NULL)

page->next_hash->prev_hash = page; *p = page;

}

有关页面的刷新函数：

remove_page_from_hash_queue(page); /*从哈希表中去掉页面*/

remove_page_from_inode_queue(page); /*从inode节点中去掉页面*/

6.7.3翻译后援存储器(TLB)

页表的实现对虚拟内存系统效率是极为关键的。例如把一个寄存器的内容复制到另一个寄存器中的一条指令，在不使用分页时，只需访问内存一次取指令，而在使用 分页时需要额外的内存访问去读取页表。而系统的运行速度一般是被cpu从内存中取得指令和数据的速率限制的，如果在每次访问内存时都要访问两次内存会使系 统性能降低三分之二。

对这个问题的解决，有人提出了一个解决方案，这个方案基于这样的观察：大部分程序倾向于对较少的页面进行大量的访问。因此，只有一小部分页表项经常被用到，其它的很少被使用。

图6.20 翻译后援存储器

采取的解决办法是为计算机装备一个不需要经过页表就能把虚拟地址映射成物理地址的小的硬件设备，这个设备叫做TLB(翻 译后援存储器，Translation Lookside Buffer), 有时也叫做相联存储器(associative memory)，如图6.20所示 。它通常在MMU内部，条目的数量较少，在这个例子中是6个，80386有32个。

每一个TLB寄存器的每个条目包含一个页面的信息：有效位，虚页面号，修改位，保护码，和页面所在的物理页面号，它们和页面表中的表项一一对应，如图6.21所示。

图6.21用于加速分页面操作的TLB

当一个虚地址被送到MMU翻译时，硬件首先把它和TLB中的所有条目同时(并行地)进行比较，如果它的虚页号在TLB 中，并且访问没有违反保护位，它的页面会直接从TLB中取出而不去访问页表，如虚页面号在TLB但当前指令试图写一个只读的页面，这时将产生一个缺页异 常，与直接访问页表时相同。

如MMU发现在TLB中没有命中，它将随即进行一次常规的页表查找，然后从TLB中淘汰一个条目并把它替换为刚刚找到的页表项。因此如果这个页面很快再被 用到的话，第二次访问时它就能在TLB中直接找到。在一个TLB 条目被淘汰时，被修改的位被复制回在内存中的页表项，其它的值则已经在那里了。当TLB从页表装入时，所有的域都从内存中取得。

必须明确在分页机制中，TLB中的数据和页表中的数据的相关性，不是由处理器进行维护，而是必须由操作系统来维护，高速缓存的刷新是通过装入处理器（80386）中的寄存器CR3来完成的。（见刷新机制flush_tlb()）

这里要还提到命中率，即一个页面在TBL中找到的概率。一般来说TLB的尺寸大可增加命中率，但会增加成本和软件的管理。所以一般都采用8--64个条目的数量。

假如命中率是0.85，访问内存时间是120那秒，访TLB时间是15那秒。那么访问时间是：0.85*(15+120)+(1-0.85)*(15+120+120)=153那秒。

6.7.4刷新机制

1. 软件管理TLB

前面我们介绍的TLB管理和TLB故障的处理都完全由MMU硬件完成，只有一个页面不在内存时才会陷入操作系统。

而实际上，在现代的一些RISC机中，包括MIPS、Alpha，HP PA，几乎全部的这种页面管理工作都是由软件完成的。在这些机器中，TLB条目是由操作系统显式地装入，在TLB没有命中时，MMU不是到页表中找到并装 入需要的页面信息，而是产生一个TLB故障把问题交给操作系统。操作系统必须找到页面，从TLB中淘汰一个条目，装入一个新的条目，然后重新启动产生异常 （或故障）的指令。当然，所有这些都必须用很少指令完成，因为TLB不命中的频率远比页面异常大得多。

令人惊奇的是，如果TLB的尺寸取一个合理的较大值(比如64个条目)以减少不命中的频率，那么软件管理的TLB效率可能相当高。这里主要的收益是一个简单得多的MMU（最后介绍），它在CPU芯片上为高速缓存和其它能提高性能的部件让出了相当大的面积。

人们已经使用了很多方法来提高使用软件管理TLB机器的性能，有一个方法既能减少TLB的不命中率又能减少在TLB不命中确实发生时的开销。为了减少 TLB的不命中率，操作系统有时可以用它的直觉来指出那些页面可能将被使用并把他们预装入TLB中。例如，当一个客户进程向位于同一台机器的服务器进程发 出一个RPC请求时，服务器很可能即将运行。知道了这一点，在客户进程因执行RPC陷入时，系统就可以找到服务器的代码、数据、堆栈的页面，并在TLB中 提前为他们建立映射，以避免TLB故障的发生。

无论是硬件还是软件，处理TLB不命中的一般方法是对页表执行索引操作找出所引用的页面。用软件执行这个搜索的一个问题是保存页表的页面面本身可能就不在 TLB中，这将在处理过程中再一次引发一个TLB异常，这种异常可以通过保持一个大的(比如4K)TLB条目的软件高速缓存而得到减少，这个高速缓存保持 在固定位置，它的页面总是保持在TLB中，操作系统通过首先检查软件高速缓存可以大大减少TLB不命中的次数。

2. 刷新机制

用软件来管理TLB和其他缓存的一个重要的要求就是保持TLB和其他缓存中的内容的同步性，这样必须考虑在一定条件下刷新内容。

在Linux中刷新机制(包括TLB的刷新，缓存的刷新等等）主要要用来完成以下几个工作；

(1) 保证在任何时刻内存管理硬件所看到的进程的内核映射和内核页表一致；

(2) 如果负责内存管理的内核代码对用户进程页面进行了修改，那么用户的进程在被允许继续执行前,要求必须在缓存中看到正确的数据.

例如当正在执行write() 系统调用时，要保证页面缓存中的页面为新页，也就是要使缓存中的页面内容和写入文件的一致，就需要更新缓存中的页面。
3. 通常当地址空间的状态改变时，调用适当的刷新机制来描述状态的改变

在Linux中刷新机制的实现是通过一系列函数（或宏）来完成的,例如常用的两个刷新函数的一般形式为：

flush_cache_foo( );
flush_tlb_foo( );

这两个函数的调用是有一定顺序的，它们的逻辑意义是：

在地址空间改变前必须刷新缓存，防止缓存中存在非法的空映射。函数flush_cache_*（）会把缓存中的映射变成无效（ 这里的缓存指的是MMU中的缓存，它负责虚地址到物地址的当前映射关系;注意在这里由于各种处理器中MMU的内部结构不同，换存刷新函数也不尽相同。比如 在80386处理器中这些函数是为空——i386处理器刷新时不需要任何多余的MMU的信息，内核页表包含了所有的必要信息）。在刷新地址后，由于页表的 改变，必须刷新TBL以便硬件可以把新的页表信息装入TBL。

下面介绍一些刷新函数的作用和使用情况：

void flush_cache_all(void);

void flush_tlb_all(void);

这两个例程是用来通知相应机制，内核地址空间的映射已被改变，它意味着所有的进程都被改变了；

void flush_cache_mm(struct mm_struct *mm);

void flush_tlb_mm(struct mm_struct *mm);

它们用来通知系统被mm_struct结构所描述的地址空间正在改变;它们仅发生在用户空间的地址改变时；

flush_cache_range(struct mm_struct *mm,unsigned long start, unsigned long end);

flush_tlb_range(struct mm_struct *mm,unsigned long start, unsigned long end);

它们刷新用户空间中的指定范围。

void flush_cache_page(struct vm_area_struct *vma,unsigned long address);

void flush_tlb_page(struct vm_area_struct *vma,unsigned long address);

刷新一页面。

void flush_page_to_ram(unsigned long page);（如果使用i386处理器，此函数为空，相应的刷新功能由硬件内部自动完成）

这个函数一般用在写时复制，它会使虚拟缓存中的对应项无效，这是因为如果虚拟缓存不可以自动地回写，于是会造成虚拟缓存中页面和主存中的内容不一致。

图6-22 多个任务内存空间

例如,虚拟内存0x2000对任务1，任务2，任务3 共享，但对任务2只是可读，它映射物理内存0x1000,那么如果任务2要对虚拟内存0x2000执行写操作时，会产生页面错误。内存管理系统要给它重新 分配一个物理页面如0x2600, 此页面的内容是物理内存0x1000的拷贝，这时虚拟索引缓存中就有两项内核别名项0x2000分别对应两个物理地址0x1000和0x2600，在任务 2对物理页面0x2600的内容进行了修改后，这样内核别名即虚地址0x2000映射的物理页面内容不一致，任务3 在来访问虚地址0x2000时就会产生不一致错误。为了避免不一致错误，使用flush_page_to_ram使得缓存中的内核别名无效。

一般刷新函数的使用顺序如下：

copy_cow_page(old_page,new_page,address);

flush_page_to_ram(old_page);

flush_page_to_ram(new_page);

flush_cache_page(vam,address);

….

free_page(old_page);

flush_tlb_page(vma,address);

4.函数代码简介

大部分刷新函数都在include/asm/pttable.h中定义，这里就i386中__flush_tlb()的定义给予说明：

#define __flush_tlb() \

do { \

unsigned int tmpreg; \

\

__asm__ __volatile__( \

"movl %%cr3, %0; # flush TLB \n" \

"movl %0, %%cr3; \n" \

: "=r" (tmpreg) \

:: "memory"); \

} while (0)

这个函数比较简单，通过对CR3寄存的重新装入，完成对TLB的刷新。