揭秘UNIX文件缓存(the buffer cache)(理论篇)

对于UNIX系统来说，最核心的是两个子系统，一个是File subsystem（文件子系统）,一个是process control subsystem(进程控制子系统)，请看下面这幅图：

这幅图基本上讲述了UNIX内核的基本架构，可以看到在file subsystem到block即device drivers(设备驱动)之间有一个明显的buffer cache，我们就来讲讲这个The buffer cache。
先分别讲一讲什么是buffer ，什么是cache。
buffer,中文译名为缓冲，故名思意，buffer的主要功能是为了防止短时间太多的吞吐造成I／O的破坏，起到了流量整形的作用。在the buffer cache里面，buffer体现在将文件流分别一个个大小相同的block，内核在通过buffer获取文件流的时候，不会因为想要获取的文件流的是大文件流还是小文件流，造成device drivers的堵塞。当然，buffer还不止这些作用，他的好处在文最后还会提到。
cache,中文译名为缓存。cache是为了弥补两边存储设备的存储速度的差异的中间存储内存，在file subsystem系统中，主存的存储速度要比硬盘快得多，如果直接内核直接从硬盘反复读取数据，性能会极大的下降。但是利用局部性原理，利用高速的cache暂时的保存数据，让数据能重复使用，减少内存直接与硬盘的交互次数。

那么，the buffer cache的到底是什么呢？
首先，the buffer cache是由一块块的buffer所组成的数据结构，这一块块的buffer含有大小形同的文件数据，记录buffer的相关信息，buffer头的结构如下图：

这个看到device num和block num,相关硬盘的device num和block num，表示现在这块buffer存储的数据是那一块block的,下面的status表示现在buffer的状态，是可用的，还是可读的，还是delay write(延迟写，后面会提到)的。
ptr to data area,表示执行buffer数据的指针。
下面分别是维护这些buffer的两个关键数据结构hash queue和free list的相关前后指针（双向链表）。
其次，我们介绍一下维护这些buffer的数据结构,hash queue和freelist.

FREELIST

空闲链表，空闲指的是空闲链表中维护的buffer是空闲的，是可读取其他block（文件）的信息的。那么the buffer cache，cache的功能主要体现在这个freelist上，根据局部性原理，当读取一块数据的时候，后面很大概率是读取这块数据，或者这块数据周围的数据。也就是说，我们很大概率会读取我们最近才读取的数据。
根据局部性原理，我们采用的算法就自然而然的想到了LRU（最少最近访问），一般要实现LRU有两种思路。一是，记录每一块buffer的访问时间，然后在每次取buffer的时候，遍历整个freelist找到时间最少的一块buffer。但是，一旦结点数一多，遍历的时候会成为性能的瓶颈。
所以，这里很巧妙的用双向链表实现了LRU。
请看下面操作freelist的图：

1.分配：当内核需要从freelist分配一个空间buffer的时候，freelist会从freelist的头部，就是图中buf1的位置取出一个buf。（当然，在内核要获取指定的buffer的时候，也可能从freelist的中间拿。）。
2.回收：当内核给进程用完分配出来的buffer的时候,buffer又为空闲状态，这时候刚用完的buffer添加在freelist的尾部，即图中buf n的位置。
（分配回收的伪代码会在下面马上给出，因为这些算法涉及到hash queue，想一起说）
通过从头分配，从尾回收的机制，会使得越近使用的buffer越靠近尾部，不使用的buffer越靠近头部。实现了LRU的思想，不常使用的优先被分配，常使用的保留，供以后的进程使用。

HASH QUEUE

解决了LRU的问题，又有一个新问题，内核如何根据block number在buffer pool寻找对应的buffer，是一个一个遍历寻找吗？遍历寻找一旦buffer一多，时间消耗的多，但是查找算法一旦复杂，又不符合内核本身要简洁，迅速的特点。buffer cache采用的是相对而言简单的寻找算法，hash queue。对应的hash映射算法也采用最简单而有效的取模运行。
具体的结构如下图所示：

当然，这里用的模数为4，不是一个特别合适的模数，因为在选取模数的时候尽量不要去2的幂或者10的幂数，因为如果在将数字变成二进制数字的时候，会发觉在数字特征中，只有后面几位的数字被利用起来，这个并不符合我们对hash的随机性的要求，我觉得比较合适的模数（也就是分组）为7。

那么，hash queue和freelist又有什么关系呢？对于hash queue来说，所有的buffer pool中所有的buffer都存在hash queue中，hash queue中可用的buffer又同时存在freelist中。也就是说，buffer一定在hash queue中，不一定在freelist中。

讲完了数据结构，就该讲用怎样的算法进行获取buffer，释放buffer了。
以下是获取buffer的函数getblk的伪代码：

以下是释放buffer的函数brelse的伪代码：

从以上的代码可以看出，在讨论内核的buffer的分配问题上是一定是逃不掉多进程的同步问题的。下面，针对图3.4的buffer allocation函数谈论在申请buffer的五种情况：
1 内核找到block在hash queue，并且包含这个block的buffer是空闲的。
2 内核无法在hash queue找到这个block,所以从freelist申请了一个buffer.
3 内核无法在hash queue找到这个block,并且在尝试从freelist申请一个buffer的时候发现这个freelist需要“delayed write”(延迟写)。内核必须把这个“delayed write”异步写回之后再从freelist申请。
4 内核无法再hash queue找到这个block,并且缓存的free list也是空的。
5 内核在hash blocks找到这个block，但是它的缓存现在正忙。

针对在申请buffer的五种场景分别做分析：
1.也就是最一般的情况,hash queue里面的buffer是空闲的，就意味着该buffer在freelist中，那么很简单，内核将该buffer取出，然后把该buffer从freelist上去除。
如下两图所示：

上图说的是，在buffer cache中找到了block 4，并且block_4也是空闲的，于是取出，然后从freelist去除block_4。
2.在现在的buffer中找不到对应的buffer,并且freelist不为空。那么，就需要从freelist中取出一个可用的buffer(不为delay write)，然后用这个buffer去硬盘中取对应block的数据。当然，在freelist分配的时候，我们要从freelist的头部取一个出来（取最不常使用的），然后把旧的buffer从hash queue去掉，把新分配的buffer加入hash queue
具体的操作如下图所示：

3.如果在freelist分配内存的过程中，遇到delay write的情况（这里面的delay write）（说的是在进程向往磁盘里面做write操作的时候，会现把要写的内容写在buffer中，buffer不会马上写回磁盘，而是在分配内存的时候，发现delay write然后写回，这样做的目的是在多次进行写操作的时候不会马上操作多次接触磁盘，而是只将最后一次写操作的结果写入磁盘中。当然，这也造成你写的东西不会马上存入磁盘，如果在delay write的过程中宕机，你的数据很可能就没写进去。）具体的写操作如下代码所示：

回到正题，当在freelist分配内存的时候，发觉freelist的buffer是delay write,那么异步的把数据写入硬盘，（这里的异步针对的是消息：即kernel发送写的消息，等不等待对应消息的回复）然后继续循环，进行寻找空的buffer。在buffer写完之后，状态成为free之后，应该放在freelist的头部，不能放在尾部，因为这些写完的buffer不是因为刚刚使用而被取走，所以应该放在头部。具体操作的例子如下；

下面的情况四和情况五就慢慢就复杂了。
4.内核找不到对应block的buffer，想从freelist分配，但是freelist也是空的。正常想来，这种情况就必须等待其他进程用完哪个buffer，然后将buffer分配过来用，对于进程来说，等待要么意味了让进程while()循环空转，但这又比较浪费cpu资源。所以，这里的等待对进程就意味着让该进程暂时睡眠直到有空闲buffer让出来。但是，不能在进程刚结束睡眠的时候就马上获取对应的buffer。可能出现这么一种情况，进程A在结束睡眠的同时，kernel调度到其他进程，其他进程申请与进程A相同的block的时候，因为hash queue里面只能有唯一一个block号的buffer，所以如果process A再申请就会冲突，所以在process A结束睡眠的时候，需要重新循环一次寻找buffer.
对于的图片如下图所示：

竞争条件的情况如下图所示：

接下来就是最难的情况五了
5.
关于这个竞争条件和hash queue的情况直接先看下面的图吧。

从这个进程图中可以看到进程B在获取block b这个过程中可以说是非常悲催了。先是进程A在hash queue中找不到对应的block，然后向freelist分配了一个buffer，在buffer向硬盘读取block信息的时候，进程进入睡眠，该buffer locked。这时候，内核调度到进程B，进程找到了这个block b，但是这个block b被锁住了，并且也不能在同一个hash queue中申请第二个相同的block，进程B只能等待A用完了，再获取block b,就在B进入睡眠的时候，这时候进程C又要申请一个新的buffer，对应的block为b’，这时候进程A用完了block b，调用了brelse()函数，唤醒了所有进程，这时候block如果被进程C要到，那么本来应该是block b的buffer变成了block b’,这明显不是进程B想要的。所以轮到进程B的时候，进程B不得不在寻找一遍hash queue，防止出现竞争条件。
当然，这5种情况虽然覆盖了大部分情况，还是有可能出现进程进程straving（饥饿）情况，这时候我想的是通过设置每一个进程的优先级，当进程每次循环的时候无法得到想要的buffer，优先级就加一，优先级越高的越早的被调度。

最后，在贴一段读取对应buffer的代码吧，了解了申请。读取就在申请的基础上进行读取。

这里添一下用buffer的好处吧，可以理解buffer是一个针对文件block的抽象接口，即内核需要的无论是一个文件还是一个innode都只需要通过buffer获取，统一了接口，不需要考虑硬盘是8地址还是4地址（举一个例子哈，举8还是4）这使得系统在可移植性，统一性上有着很好的表现，并且也能起到文件流流量整形的作用。

揭秘UNIX文件缓存（the buffer cache）第一篇理论篇暂时就到了，接下来的第二篇实践篇，我会尝试用C++写一个the buffer cache的仿真器出来。

来源：《the design of the unix operating system》