Linux内核文件cache管理机制介绍

1 操作系统和文件Cache管理

操作系统是计算机上最为重要的软件,他负责管理计算机的各种硬件资源,并将这些物理资源抽象成各种接口供上层应用使用。所以从程序的角度看,操作系统就好比是一个虚拟机,这个虚拟机不提供各种硬件资源的具体细节,而仅仅提供进程、文件、地址空间以及进程间通信等等逻辑概念。

对于存储设备上的数据,操作系统向应用程序提供的逻辑概念就是“文件”。应用程序要存储或访问数据时,只需要向这个文件读或者写入内容即可,而文件与物理存储设备的交互则由操作系统提供。

2 文件Cache的地位和作用

文件Cache是文件在数据内存中的副本,因此文件Cache管理与内存管理系统和文件系统相关:一方面文件Cache作为物理内存的一部分,需要参与内存的分配与回收。另一方面,cache中的数据来源于存储设备上的文件,需要通过文件系统与存储设备进行读写交互。

如图1所示,具体的文件系统,比如ext2/ext2,jfs,ntfs等等负责在文件Cache和存储设备之间交换数据,位于文件系统之上的虚拟文件系统VFS负责在应用程序和文件Cache之间通过read和write等接口交换数据。内存管理系统负责内存的分配与回收,同时虚拟内存管理系统(VMM)则允许应用程序和文件Cache之间通过memory map的方式交换数据。

Linux内核文件cache管理机制介绍

3 文件Cache的相关数据结构

在Linux的实现中,文件Cache分为两个层面,page cache和buffer cache。每一个page cache包含若干个buffer cache。VFS负责page cache和用户空间的数据交换;内存管理系统负责page cache的分配与回收,同时在使用memory map访问时负责建立映射。而具体的文件系统则与buffer cache进行交互,将外围存储设备上的数据和buffer cache之间进行交换。

在Linux内核中,文件的每个数据块最多只能对应一个page cache项,其通过两个数据结构管理,一个radix tree另一个就是双向链表。radix tree是一个搜索树,linux利用这个数据结构来通过文件内偏移快速丁文cache项。下图是radix tree的⼀一个⽰示意图,该radix tree 的分叉为4(22),树⾼高为4,⽤用来快速定位8位⽂文件内偏移。Linux(2.6.7)内核中的分叉为 64(26),树⾼高为6(64位系统)或者11(32位系统),⽤用来快速定位32 位或者64 位偏移,radix tree中的每⼀一个叶⼦子节点指向⽂文件内相应偏移所对应的Cache项。

另⼀一个数据结构是双向链表,Linux内核为每⼀一⽚片物理内存区域(zone)维护active_listinactive_list两个双向链表,这两个list主要⽤用来实现物理内存的回收。这两个链表上除了⽂文件Cache之外,还包括其它匿名(Anonymous)内存,如进程堆栈等。 

Linux内核文件cache管理机制介绍

Linux内核文件cache管理机制介绍

Linux内核文件cache管理机制介绍


4 文件Cache的预读和替换

Linux内核中文件预读算法的具体过程是这样的:对于每个文件的第一个读请求,系统读入所请求的页面并读入紧随其后的少数几个页面(不少于一个页面,通常是三个页面),这时的预读称为同步预读。对于第二次读请求,如果所读页面不在Cache中,即不在前次预读的group中,则表明文件访问不是顺序访问,系统继续采用同步预读;如果所读页面在Cache中,则表明前次预读命中,操作系统把预读group扩大一倍,并让底层文件系统读入group中剩下尚不在Cache中的文件数据块,这时的预读称为异步预读。无论第二次读请求是否命中,系统都要更新当前预读group的大小。此外,系统中定义了一个window,它包括前一次预读的group和本次预读的group。任何接下来的读请求都会处于两种情况之一:第一种情况是所请求的页面处于预读window中,这时继续进行异步预读并更新相应的window和group;第二种情况是所请求的页面处于预读window之外,这时系统就要进行同步预读并重置相应的window和group。图5是Linux内核预读机制的一个示意图,其中a是某次读操作之前的情况,b是读操作所请求页面不在window中的情况,而c是读操作所请求页面在window中的情况。

Linux内核中文件Cache替换的具体过程是这样的:刚刚分配的Cache项链入到inactive_list头部,并将其状态设置为active,当内存不够需要回收Cache时,系统首先从尾部开始反向扫描active_list并将状态不是referenced的项链入到inactive_list的头部,然后系统反向扫描inactive_list,如果所扫描的项的处于合适的状态就回收该项,直到回收了足够数目的Cache项。


5 文件Cache相关API及其实现

Linux内核中与文件Cache操作相关的API有很多,按其使用方式可以分成两类:一类是以拷贝方式操作的相关接口, 如read/write/sendfile等,其中sendfile在2.6系列的内核中已经不再支持;另一类是以地址映射方式操作的相关接口,如mmap等。

第一种类型的API在不同文件的Cache之间或者Cache与应用程序所提供的用户空间buffer之间拷贝数据,其实现原理如图7所示。

Linux内核文件cache管理机制介绍

第二种类型的API将Cache项映射到用户空间,使得应用程序可以像使用内存指针一样访问文件,Memory map访问Cache的方式在内核中是采用请求页面机制实现的,其工作过程如图8所示。

Linux内核文件cache管理机制介绍

首先,应用程序调用mmap(图中1),陷入到内核中后调用do_mmap_pgoff(图中2)。该函数从应用程序的地址空间中分配一段区域作为映射的内存地址,并使用一个VMA(vm_area_struct)结构代表该区域,之后就返回到应用程序(图中3)。当应用程序访问mmap所返回的地址指针时(图中4),由于虚实映射尚未建立,会触发缺页中断(图中5)。之后系统会调用缺页中断处理函数(图中6),在缺页中断处理函数中,内核通过相应区域的VMA结构判断出该区域属于文件映射,于是调用具体文件系统的接口读入相应的Page Cache项(图中7、8、9),并填写相应的虚实映射表。经过这些步骤之后,应用程序就可以正常访问相应的内存区域了。



上一篇:一个简单的Dump转文本工具—Dump2Text


下一篇:YUV 与 RGB的转换