13.5.2 缓存控制块buf的各种队列
由于buf记录了与缓存有关的各种管理信息（包括具体的I/O要求），所以系统总是通过管理buf来使用缓存的。
1、自由buf队列和自由buf队列控制块bfreelist
一个可被分配它用的buf，一定位于自由buf队列，这意味着该buf所对应的缓存现在是自由的，此种buf标志字b-flags中的B-BUSY标志均被清除。
每个处于自由buf队列中的buf结构相互使用av-forw和av-back形成双向勾链。 为了能真正管理起自由buf队列，显然需要对队列的首、尾加以管理，这将由自由buf队列控制块bfreelist来完成。为了整齐化一，系统让它也具有和一般buf相同的结构，只是用它里面的av-forw做自由buf队列的首指针，而av-back做自由buf队列的尾指针。于是，自由buf队列可如图13-30所示。
图13-30 自由buf队列
对自由buf队列，系统采用FIFO管理算法，一个缓存被释放时，相应于它的buf就被送入自由buf队列之尾；当请求一个缓存时，就从自由buf队列之首摘下一个buf，它所对应的缓存即被分配出去。 2、输入/输出请求队列
通过缓存进行输入/输出时，具体的I/O请求全都包含在buf结构中，它们是：操作类型（读或写）、信息源和目的地的地址、以及数据的传输量等。因此，buf既是缓存的控制块，又是I/O的请求块。也就是说，向主设备号相同的各设备提出的I/O请求所构成的输入/输出队列也由buf组成。由于位于I/O请求队列的buf肯定不会出现在自由buf队列中，故在I/O请求队列里的buf就借用av-forw来构成一个单向链，该队列的队首、队尾指针是该类设备的块设备表中的d-actf和d-actl。于是某块设备的输入/输出请求队列如图13-31所示。
图13-31 块设备的I/O请求队列
对于块设备的I/O请求队列，系统仍采用FIFO管理算法。要注意的是，系统中也有不通过缓存进行的输入和输出。回忆一下UNIX存储管理，在那里曾提及在磁盘上专门开辟了进程映像对换区，用以存放调出的进程映像非常内驻内存部分。这部分存
264
储资源归UNIX存储管理部分进行分配和释放，但它提出的输入/输入却要由设备管理部分来负责完成。由于它的I/O请求是指把对换区盘块中的内容送到内存的用户区指定处，与缓存没有关系，也以为了能提交这种不通过缓存进行的I/O请求，系统专门开设了一个名为swbuf的I/O请求块。swbuf的结构与buf结构一样，它也排列在块设备的I/O请求队列中，使用av-forw与它的前、后buf勾链。不同的是它里面的b-addr和b-xmen给出的不是哪个缓存的内存起址，而是分配给它的内存区起址。顺便再强调一下，swbmf和bfreelist是使用buf结构的二种特殊情况，它们和缓存没有关系。 3、设备buf队列
整个系统的缓存资源是有限的，为了实现对它的充分共享，UNIX做了如下考虑： 第一，一旦某缓存被释放，相应的buf就应立即进入自由buf队列，以作它用。 第二，一个已经位于自由队列的buf，在尚未移作它用之前，它里面的信息仍保持着缓存与某设备上盘块的对应关系。若此时系统根据需要能够退回来按原状继续使用它，那么就可省去重复的、且十分耗费时间的设备I/O操作过程，从而提高文件系统的工作效率。为了能方便地做这种“进”（移作它用）或“退”（继续按原状使用），UNIX在自由buf队列和I/O请求队列之外，又设置了一种新队列：设备buf队列。
每类块设备都有一个设备buf队列，队首和队尾分别是相应块设备表devtab中的b-forw和b-back。队列中的buf结构用其指针b-forw和b-back进行双向勾链。一个缓存被分配用来对某类块设备的某一盘块进行读、写时，与之对应的buf就进入了该类块设备的设备buf队列。即使在完成了I/O请求而被释放后（这时进入了自由buf队列），它仍然呆在这个设备buf队列里，除非再次分配用于别类块设备时止。
每当一个buf进入设备buf队列时，总是在该队列之首进行插入。
这里要注意的一个问题是，在系统初启时，每一个buf都没有分给任何实际的块设备，为此，系统增设了一个想象的设备NODEV，其首、尾指针就用bfreelist中的b-forw和b-back。于是NODEV队列和某类设备的设备buf队列如图13-32的所示。
图13-32 设备buf队列的初始态和演变
由于一个buf建立起某类设备的一个盘块与一个缓存之间的联系之后，它就一直呆在该类设备的设备buf队列里，直到这个缓存重分它用，因此对于一个buf来讲，任何时候都处在上述三个队列的两个之中：在自由buf队列和设备buf队列（包括NODEV
265
队列的情形），或在I/O请求队列和设备buf队列。
13.5.3 字符设备管理的数据结构
1、字符缓存和自由字符缓存队列
为字符设备设置字符缓冲的主要出发点是解决它们和CPU之间的速度不匹配问题。由于字符设备的共同特点是：工作速度慢，一次输入/输出请求的字符数量少且不固定，因此系统为字符设备设置了一个使用比较灵活、占用内存较小的缓冲机构。
系统在内存总共设置了100个字符缓存cblock，它们形成一个能够共享的缓总池cfree。每个字符缓存为8个字节，前两个字节为字符缓存指针c-next，后六个字节为该缓存的信息区info。
未被使用的字符缓存通过各自的c-next勾链成一个单向的自由字符缓存队列，其队首由一个名为cfreelist的指针指出，处于队列之尾的字符缓存的c-next取值null，图13-33给出了自由字符缓存队列的示意。
图13-33 自由字符缓存队列
系统视自由字符缓存队列为一栈，分配和释放均在队首进行。这里要注意的是，由于对字符缓存的管理比较简单，因而没有必要再设置专门的缓存控制块。 2、字符设备表和I/O字符缓存队列
和块设备类似，每个字符设备也都有一张设备表。但由于各类字符设备的特性判别很大，不可能设置统一形式的设备表。譬如说在UNIX系统里，纸带机的设备表仅三项内容，而终端机的设备表则含有十三项内容。
但它们共同之处是都包含有输入/输出字符缓存队列的控制块，该控制块均为clist结构，里面含三项内容。
(1) c-cc队列中可用字符计数； (2) c-cf指向队列中的第一个字符； (3) c-cl指向队列的最后一个字符。
于是，一个字符设备的输入/输出字符缓存队列的一般形式如图13-34所示。
图13-34 I/O字符缓存队列
由此可知，在整个系统中存在着多个I/O字符缓存队列。如果某一字符设备既有输入功能，又有输出功能，则它的设备表中就会有两个字符缓存队列控制块，一个控制输入字符缓存队列，一个控制输入字符缓存队列。
266
3、字符设备开关表
每个字符设备也有自己的设备开关，这些开关集合在一起，就形成字符设备开关表cdevsw。开关表中的每一表目与一个字符设备相对应，是该设备的开关。它包含五项内容，前四项分别是打开、关闭、读和写子程序的入口地址，第五项是专门为终端设置的，为设置并获得终端机特性子程序的入口地址，其余字符设备均没有此项。
13.5.4 字符缓存的管理
为了从字符缓存中取字符或往字符缓存中送字符时能够较为容易地判断出是否要释放字符缓存或申请字符缓存，UNIX系统在对cfreelist进行初始化时，采取了一定的措施，使每一个字符缓存的起始地址的最后三位为0。这实际上只需要确保第一个字符缓存cfree[0]的起始地址最后三位为0即可，因为每个字符缓存都由8个字节构成，这样排列下来，每个字符缓存起始地址的最后三位就都为0了（这也是每个字符缓存长度取为8个字节的原因之一）。
现在来看一下取字符和释放字符缓存的问题以及送字符和申请字符缓存的问题。 以图34为基础，根据c-cf指点，逐一从字符缓存里取出字符e和f，c-cc做计数调整，c-cf也依次下移。若发现c-cf的最低三位已为0时，这说明该字符缓存中的字符已全部取完，c-cf应指向下一字符缓存的第一个字符，即要把释放的这一个字符缓存中的c-next加工送给c-cf，这时图13-34就成为图13-35所示。
图13-35 取出e、f字符后的I/O字符缓存队列
若在图13-35的基础上，根据c-cl指点往字符缓存里送字符。显然，当c-cl加2而获取下一存放字符的位置时，会发现该地址的最后三位为0，这表示目前的字符缓存已经存满，需要先申请一个新的字符缓存才能把字符存入。于是去cfreelist申请一个新的字符缓存，链入到I/O字符缓存队列之尾，然后再根据调整后的c-cl送入字符。此时图35就成为图13-36所示。
图13-36 送入S后的I/O字符缓存队列
13.5.5 块设备的读写操作
通过缓冲技术，块设备的读写有三种方式、五个过程：
267
1、一般读、写方式，有二个过程：
bread (dev, blkno)——一般读过程，把物理块中的信息读入缓冲区
bwrite (bp)——一般写过程、把bp指定的缓冲区中的信息写到磁盘上，要等待写完成。
图13-37、13-38给出了一般读写方式的流程图。
图11-37 bread (dev, blkno) 流程
268