数据缓冲区高速缓冲

当进程想要从一个文件上存取数据时，内核把文件中的数据移入内存后，该进程便能观察它，修改它，然后请求将数据再次保留到文件系统中．

但是，慢的磁盘传输速率会使系统响应时间加长，吞吐率降低．因此，内核通过保持一个称为数据缓冲区高速缓冲的内存数据缓冲区池来试图减少对磁盘的存取频率．

当从磁盘中读数据的时候，内核试图先从高速缓冲中读．如果数据已经在该高速缓冲中，则内核可以不必从磁盘上读．如果数据不在该高速缓冲中，则内核从磁盘上读数据，并将其缓冲起来．所使用的算法试图把尽可能多的好数据保存在高速缓冲中．类似的，要往磁盘写的数据也被暂存于高速缓冲中，以便如果内核随后又试图读它时，它能在高速缓冲中．内核也通过判定是否数据必须真的需要存储到磁盘上，或数据是否是将要很快被重写的暂时性数据，来减少磁盘写操作的频率．高层内核算法让高速缓冲模块把数据预先缓冲起来，或延迟写数据以扩大高速缓冲的效果．

下面就来探讨下内核用于操纵高速缓冲中的缓冲区的算法．

缓冲头部

一个缓冲区由两个部分组成：

1. 含有磁盘上的数据的存储器数组　
2. 用来标识该缓冲区的缓冲头部（buffer header）

一个缓冲区的数据与文件系统上一个逻辑磁盘块中的数据相对应，并且内核通过考察缓冲头部中的标识字符来识别缓冲区内容．缓冲区是磁盘块在内存中的拷贝，磁盘块的内容映射到该缓冲区中．但该映射不仅是临时的，在同一时刻决不能将一个磁盘块映射到多个缓冲区．
例如：一个磁盘块映射了A和B两个缓冲区．内核把数据分别写入A和B，如果内核把缓冲区往磁盘上拷贝时，颠倒了顺序，正则磁盘块将包含不正确的数据．

缓冲头部包含一个设备号字段与一个块号字段，这两个字段指明了文件系统与磁盘上的数据的块号，并且唯一地表示了该缓冲区．设备号是逻辑文件系统号1．一个缓冲区状态是如下条件的组合：

• 缓冲区当前为＂上锁＂
• 缓冲区包含有效数据
• 内核在把某缓冲区重新分配出去之前必须把该缓冲区内容写到磁盘上，这一条件叫做延迟写
• 内核当前正在从磁盘往缓冲区读信息或把缓冲区的内容写到磁盘上
• 一个进程当前正在等待缓冲区变为闲

缓冲区结构

内核按最近最少使用算法把数据缓存于缓冲池中．内核维护一个缓冲区的空闲表，它保存被最近使用的次序．空闲表是缓冲区的双向链接循环表，具有一个哑缓冲区头标，以标志缓冲区空闲表的开始和结束．

当内核想要一个任意的空闲缓冲区时，它从空闲表的头部取出一个缓冲区．但是如果它标识出缓冲池中的一个特定块（延迟写）的话，它会从空闲表的中间取出一个缓冲区．
当内核把一个缓冲区还给缓冲池时，它通常把该缓冲区追加到空闲表的尾部，偶尔也将其插入到空闲表的头部（在出错的情况下），但是从来不会在中间插入．
当内核不断的额从空闲表上取下缓冲区时，装有有效数据的缓冲区会越来越近地移动到空闲表的头部．因此，离空闲表的头部近的缓冲区比里空闲表的头部远的缓冲区是最近最少使用的．

当内核存取一个磁盘时，它使用是当代额设备号和块号的组合去找相应的缓冲区．它并不是去搜索整个缓冲区池．它把缓冲区组织成一个个队列，这些队列是以设备号和块号来散列的．

缓冲区池中的每个磁盘块，存在于且存在于一个散列队列中，并且仅在那个散列队列中呆一阵．然而，如果一个缓冲区为空闲状态，则它也可以在空闲表中．总的来说，一个缓冲区总是在某个散列队列上，但是它可以在或不在空闲表中．

缓冲区的检索

读写磁盘块的算法使用算法getblk来对池中的缓冲区进行分配．算法getblk中内核把一个缓冲区分配给磁盘块时可能出现的五中典型情况：

1. 内核发现该块在它的散列队列中，并且它的缓冲区的空闲的；
2. 内核在散列队列中找到该块，并且，在试图从空闲表分配一个缓冲区；　
3. 内核在散列队列中找到该块，并且，在试图从空闲表分配一个缓冲区的时候，在空闲表中找到一个已标上了＂延迟写＂标记的缓冲区．内核必须把＂延迟写＂缓冲区的内容写到磁盘上，并分配另一个缓冲区；
4. 内核在散列队列中找不到该块，并且空闲缓冲区表已空；
5. 内核在散列队列中找到该块，但它的缓冲区当前为忙．

算法 getblk
输入：
    文件系统号
    块号
输出：
    现在能被磁盘块使用的上了锁（不让其他进程使用）的缓冲区
{
    while (没找到缓冲区)
    {
        if (块在散列队列中)
        {
            if (块忙)  /* 第五种情况　*/
            {
                sleep(等候＂缓冲区变为空闲＂事件);
                continue;
            }
            为缓冲区标记上＂忙＂; /* 第一种情况 */
            从空闲表上摘下缓冲区;
            return(缓冲区);
        }
        else  /* 块不在散列队列中 */
        {
            if (空闲表上无缓冲区)  /* 第四种情况 */
            {
                sleep(等候"任何缓冲区变为空闲"事件);
                continue;
            }
            从空闲表上摘下缓冲区;
            if (缓冲区标记着延迟写）  /* 第三种情况 */
            {
                把缓冲区异步写到磁盘上;
                continue;
            }
            /* 第二种情况－－找到一个空闲缓冲区 */
            从旧散列队列中摘下缓冲区;
            把缓冲区投入新散列队列;
            return(缓冲区);
        }
    }
}           

第一种情况

内核在标记有blkno 0 mod 4的队列上搜索第4块．找到该缓冲区后，内核把它从空闲表中摘下2，而将第5块和第28块相连接并留在空闲表中．

第二种情况

　第三种情况

内核也必须从空闲表中分配一个缓冲区，然而，它发现，从空闲表中摘下的缓冲区已被标记上了＂延迟写＂，因此，它必须在使用该缓冲区之前，将该缓冲区的内容写到磁盘上．内核开始了一个往磁盘的异步写，并且试图从空闲表上分配另一个缓冲区．当异步完成时，内核把缓冲区释放，并把它放到空闲表头．在异步写之前该缓冲区以及从空闲表尾部出发迁移到了空闲表头部．假设在异步写之后，内核把该缓冲区放到空闲表尾部，则该缓冲区会做一次多余的贯穿空闲表的移动，这就与最近最少使用算法相违背了．

第四种情况

第五种情况

　释放缓冲区

算法  　brelse
输入：
    上锁态的缓冲区
输出：
    无
{
    唤醒正在等待＂无论哪个缓冲区变为空闲＂这一事件发生的所有进程;
    唤醒正在等待＂这个缓冲区变为空闲＂这一事件发生的所欲进程;
    提高处理及执行级以*中断;
    if (缓冲区内容有效且缓冲区非＂旧＂)
        将缓冲区送入空闲表尾部;
    else
        将缓冲区送入空闲表头部;
    降低处理机执行级以允许中断;
    给缓冲区解锁;
}

内核把释放的缓冲区放到空闲表尾；但是如果发生一个I/O错误或者内核明确地在该缓冲区上标志上＂旧＂，则内核把该缓冲区放到空闲表头部．

读磁盘块与写磁盘块

算法  bread   /* 读块　*/
输入：
    文件系统号
输出：
    含有数据的缓冲区
{
    得到该块的缓冲区（算法　getblk）;
    if (缓冲区数据有效)
        return (缓冲区)
    启动磁盘读;
    sleep(等待＂读盘完成＂事件);

---

1. 一套系统装置可以有若干物理设备，每个物理磁盘设备包含一个或多个文件系统．把一个磁盘分成几个文件系统可以使得管理人员易于管理存储在那儿的数据．内核在逻辑级上只涉及文件系统，而不涉及磁盘，把每个文件系统都当作由一个逻辑设备号标识的逻辑设备．由磁盘驱动程序实现逻辑设备（文件系统）地址与物理设备（磁盘）地址之间的转换． ↩
2. 一个缓冲区不能既处于忙状态又位于空闲表中． ↩