UNIX操作系统设计：缓冲区分配算法
文件子系统中的高层内核算法引用管理高速缓冲的算法。当它们试图检索一个块时，由高层算法决定它们想要存取的逻辑设备号和块号。举例来说，正如在第4章将要看到的那样，如果一个进程想要从一个文件中读数据，则内核需判定哪一个文件系统包含该文件，以及该文件系统中的哪一块包含该数据。当要从一个特定的磁盘块上读数据时，内核检查是否该块在缓冲区池中。如果不在，则分配给它一个空闲缓冲区。当要把数据写到一个特定磁盘块上时，内核检查是否该块在缓冲区池中。如果不在，则为那个块分配一个空闲缓冲区。读、写磁盘块的算法使用算法getblk（图3-4）来对池中的缓冲区进行分配。
图3-4 缓冲区分配算法
本节描述在算法getblk中内核把一个缓冲区分配给磁盘块时可能出现的五种典型情况。
（1）内核发现该块在它的散列队列中，并且它的缓冲区是空闲的。
（2）内核在散列队列中找不到该块，因此，它从空闲表中分配一个缓冲区。
（3）内核在散列队列中找不到该块，并且，在试图从空闲表中分配一个缓冲区（像第二种情况那样）的时候，在空闲表中找到一个已标上了“延迟写”标记的缓冲区。内核必须把“延迟写”缓冲区的内容写到磁盘上，并分配另一个缓冲区。
（4）内核在散列队列中找不到该块，并且空闲缓冲区表已空。
（5）内核在散列队列中找到该块，但它的缓冲区当前为忙。现在，让我们更详细地讨论每种情况。
当根据设备号和块号的组合在缓冲池中搜索一个块时，内核找到含有该块的散列队列。它沿着缓冲区链表搜索散列队列，直到（在第一种情况中）它找到了其设备号和块号与所要搜索的设备号和块号相匹配的缓冲区。内核检查该缓冲区是否空闲。如果是，则将该缓冲区标记上“忙”以使其他进程[2]不能存取它。然后内核从空闲表上摘下该缓冲区，因为一个缓冲区不能既处于忙状态又位于空闲表中。正如所见到的那样，如果当缓冲区忙时其他进程企图存取该块，则它们去睡眠，直至该缓冲区被释放时为止。图3-5描绘了第一种情况。在那儿，内核在标记有“blkno 0 mod 4”的队列上搜索第4块。找到该缓冲区后，内核把它从空闲表中摘下，而将第5块和第28块相邻接并留在空闲表上。
图3-5 缓冲区分配的第一种情况
在继续谈另外几种情况之前，让我们考虑在把一个缓冲区分配了之后对它会发生什么。内核可以把数据从磁盘读至缓冲区，并进而操控它，或把数据写到缓冲区，并且可能进而写到磁盘上。内核把标有“忙”的缓冲区留在那里，当它忙时，没有别的进程能存取它以及改变它的内容，因此可保持该缓冲区中的数据的完整性。当内核结束使用该缓冲区时，按照算法brelse（图3-6）释放该缓冲区。它唤醒那些因该缓冲区忙而睡眠的进程，也唤醒
图3-6 释放缓冲区算法
因空闲表上没有缓冲区而睡眠的那些进程。这两类唤醒意味着被投入睡眠的那些进程现在可以使用释放了的缓冲区了——虽然得到该缓冲区的第一个进程锁上了它并且阻止其他进程得到它（见2.2节和2.4节）。内核把该缓冲区放到空闲表尾部，但是如果发生了一个I/O错误或者内核明确地在该缓冲区上标记上“旧”，则内核把该缓冲区放到空闲表头部——本章的后面部分将看到这一点。现在，该缓冲区对于要索取它的所有进程都是空闲的。
正如当内核不再需要一个缓冲区时它引用算法brelse一样，在处理一个磁盘中断过程中，释放用于往磁盘写和从磁盘读的异步I/O的缓冲区时，也要引用该算法。这将在3.4节看到。当操控空闲表时内核把处理机执行级提高以禁止磁盘中断，从而防止了因嵌套调用brelse而引起的缓冲区指针的错误。如果当一个进程正在执行getblk时，一个中断处理程序引用brelse，则也会发生类似的坏结果。因此，在getblk中对全局有重要意义的地方也要提高处理机执行级。本章的练习详细探讨了这些情况。
在算法getblk中的第二种情况下，内核搜索应该包含该块的那个散列队列，但在那个散列队列上找不到该块。因为它不能“散列”在别处，所以该块不可能在另一个散列队列上，于是可以判定它不在高速缓冲中。因此，内核从空闲表中摘下第一个缓冲区。该缓冲区曾分配给另一个磁盘块，并且也正在某个散列队列上。如果该缓冲区没有被标记上延迟写（像随后将要描述的那样），则内核标记该缓冲区为忙，将它从当前所在的散列队列中摘出，把该缓冲头部的设备号和块号重新指定为当前进程正在搜索的磁盘块的设备号和块号，并且把该缓冲区放到正确的散列队列中。内核使用该缓冲区，但是并未记录该缓冲区从前包含有另一个磁盘块的数据。如果这时有一个进程搜索旧磁盘块，则它在池中将找不到这个旧磁盘块，它必须严格地按照前面所描述的那样，从空闲表中为这个旧磁盘块分配两个新缓冲区。当内核结束对该缓冲区的使用时，它按如上所描述的那样把该缓冲区释放。例如，在图3-7中，内核搜索第18块但是在标有“blkno 2 mod 4”的散列队列上没有找到它，因此，内核从空闲表上摘下第一个缓冲区（第3块），将它分配给第18块，并把它放到适当的散列队列中。
在算法getblk的第三种情况下，内核也必须从空闲表中分配一个缓冲区。然而，它发现从空闲表中摘下的缓冲区已被标记上“延迟写”，因此，它必须在使用该缓冲区之前，将该缓冲区的内容写到磁盘上。内核开始了一个往磁盘的异步写，并且试图从空闲表上分配另一个缓冲区。当异步写完成时，内核把该缓冲区释放，并把它放到空闲表头部。在异步写之前，该缓冲区已经从空闲表尾部出发迁移到了空闲表头部。假使在异步写之后，内核把该缓冲区放到空闲表尾部，则该缓冲区会做一次多余的贯穿空闲表的移动，这就与最近最少使用算法相悖了。举例来说，在图3-8中，内核没有找到第18块，但是，当它试图分配空闲表上的头两个缓冲区（每次一个）时，发现它们标记着延迟写。内核把它们从空闲表中摘下，为这两块启动往磁盘上写的操作。内核分配空闲表上块号为4的第三个缓冲区。它适当地重新对该缓冲区的设备号和块号字段赋值，并且把该缓冲区——现在就是标记着第18块的缓冲区放到它的新的散列队列中。
图3-7 缓冲区分配的第二种情况
图3-8 缓冲区分配的第三种情况
第四种情况（图 3-9）下，为进程A而动作着的内核没有在它的散列队列上找到该磁盘块，因此，像第二种情况那样，它试图从空闲表上分配一个新的缓冲区。然而，在空闲表上已没有缓冲区可供分配，因此，进程A去睡眠，直至另一进程执行算法brelse，释放一个缓冲区。当内核调度到进程A时，它必须为该块重新搜索散列队列。它不能立即从空闲表中分配缓冲区，因为可能有多个进程正在等候空闲缓冲区，并且可能其中有一个进程已经把一个新的空闲缓冲区分配给进程A所寻找的目标磁盘块了。因此，需要再次搜索该块，保证仅仅一个缓冲区包含有该块。图3-10描绘了两个进程间为一个空闲缓冲区而进行的竞争。
图3-9 缓冲区分配的第四种情况
图3-10 竞争缓冲区
最后一种情况（图3-11）是复杂的，因为它牵涉几个进程间的复杂关系。假设内核正在为进程A动作，搜索一个磁盘块，并分配一个缓冲区，但是在释放该缓冲区之前去睡眠了。举例来说，如果进程A试图读一磁盘块并且像第二种情况那样分配了一个缓冲区，则当它等候从磁盘上的I/O传输完成时，它将去睡眠。当进程A睡眠时，假设内核调度到第二个进程B，B试图存取那个缓冲区刚刚被进程A锁上了的磁盘块。进程B（进入第五种情况）将在散列队列上找到那个上了锁的块。因为使用上着锁的缓冲区是非法的，并且为一个磁盘块分配第二个缓冲区也是非法的，所以进程B在缓冲区上打上“有需求”的标记，然后去睡眠，等候进程A释放该缓冲区。
图3-11 缓冲区分配的第五种情况
进程A将最终释放该缓冲区并注意到该缓冲区有需求者。它唤醒在事件“缓冲区变为空闲”上睡眠的所有进程，其中包括进程B。当内核再次调度到进程B时，进程B必须证实该缓冲区是空闲的。另一进程C，可能一直等待同一个缓冲区；并且内核可能先于进程B而调度到C去运行；进程C可能已经去睡眠，而该缓冲区仍是上了锁的。因此，进程B必须确认该块真的是空闲的。
进程B也必须验证该缓冲区是否包含着它原来请求的磁盘块，因为可能会像第二种情况那样，进程C已经把该缓冲区分配给另一块了。当进程B执行时，它可能发现自己那时正等候着错误的缓冲区，因此必须再次搜索该磁盘块；如果它自动地从空闲表中分配一个缓冲区，那么将察觉不出另一个进程刚把一个缓冲区分配给该块的可能性。
最后，进程B将找到它的块，可能像第二种情况那样从空闲表中分配一个新缓冲区。例如，在图3-11中，一个正在搜索第99块的进程在它的散列队列上找到了它，但是该块被标记为忙。该进程睡眠直至该块变为空闲，并且随后重新开始该算法。图3-12描绘了对一个上了锁的缓冲区进行的竞争。
图3-12 竞争一个上了锁的缓冲区
缓冲区分配的算法必须是安全的：必须使进程不永远睡眠，必须使它们最终能得到一个缓冲区。因为内核在系统调用执行期间分配缓冲区，并在返回之前释放它们[3]，所以它保证等候缓冲区的所有进程都能醒来。在用户态下的进程不直接控制内核缓冲区的分配，因此，它们不能故意地“霸占”缓冲区。仅当内核等待着一个缓冲区与磁盘之间的I/O完成时，内核才失去对这个缓冲区的控制。可以想象，若一个磁盘驱动器是有问题的，造成它不能中断CPU，这就使内核总是不能释放该缓冲区。磁盘驱动程序必须对硬件发生这样的情况进行监视，并返回一个错误给内核，说明磁盘工作不正常了。简言之，内核能保证正在因一个缓冲区而睡眠的进程最终能被唤醒。
也可想象到这样的情况是可能的：一个进程总也不能存取一个缓冲区。比如，在第四种情况下，如果几个进程因等待一个缓冲区变为空闲而睡眠，内核不保证它们能按它们请求的次序获得缓冲区。当一个缓冲区变为空闲时，一个进程可能继续睡眠，也可能被唤醒，因为当其他进程首先获得了对该缓冲区的控制权时，它只能再次去睡眠。从理论上说，这种情形可能会永远继续下去，但在实际上，由于系统中一般都配置了很多缓冲区，所以这是不成问题的。
本文摘自《UNIX操作系统设计》，虽然很老的一本书，但是堪称经典。
Linux之父Linux Torvalds曾捧读的经典著作
UNIX操作系统经典著作，畅销多年
深度剖析UNIX操作系统内核的内部数据结构、算法和UNIX系统的问题
本书以UNIX系统为背景，全面、系统地介绍了UNIX操作系统内核的内部数据结构和算法。本书首先对系统内核结构做了简要介绍，然后分章节描述了文件系统、进程调度和存储管理，并在此基础上讨论了UNIX系统的问题，如驱动程序接口、进程间通信与网络等。在每章之后，还给出了大量富有启发性和实际意义的题目。
第 1章 系统概貌
第 2章 内核导言
第3章 数据缓冲区高速缓冲
第4章 文件的内部表示
第5章 文件系统的系统调用
第6章 进程结构
第7章 进程控制
第8章 进程调度和时间
第9章 存储管理策略
第 10章 输入 输出子系统
第 11章 进程间通信
第 12章 多处理机系统
第 13章 分布式UNIX系统
附录A 系统调用
索引
参考文献
