优秀课件笔记之文件和设备管理示例

1、本文所以内容来自 著名高校课件和学生笔记（校园里面经常见到有人高价买笔记）
2、任课教师不会提供参考文献，所以只能对作者表示感谢，如果引用了您的作品，可以用回复方式补充参考文献。
3、我不对文章无关问题进行解答，文章内容也比较难，我也很难解答您遇到的问题，如果发现BUG可以用回复方式帮我修正。
4、本课 计算机操作系统
，适用于计算机操作系统课、考研

本课其他部分的导航条见页面底部

§9.1 文件系统的特点与文件类别
§9.2 文件系统的数据结构及其关系
§9.3 资源管理和地址映射
§9.4 目录与搜索方法
§9.5 文件系统的系统调用
§9.6 UNIX System Ⅴ的中断和陷阱总控程序
§9.7 缓冲区管理
§9.8 块设备驱动
§9.9 字符设备驱动
本章小结

§9.1
文件系统的特点与文件类别
9.1.1
特点
本章通过
UNIX
的文件系统来进一步深入了解文件
系统与操作系统其他部分的关系以及文件系统的设计
方法。从用户的角度看，UNIX
文件系统具有如图9.1
所示的树形层次结构：
在图9.1
中，根目录root
之下有dev
vde
设备子目录，bin
实
用程序子目录，lib
库文件子目录，etc
基本数据和维
护实用程序子目录，tmp
临时文件子目录，usr
rus
通用
子目录和include
基本数据子目录等。而
UNIX
子目
录则存放UNIX
操作系统核心程序自身。这些子目录
又由各自的子目录构成。
图9.1 UNIX
文件系统的层次结构例
文件系统被组织成树形结构之后，文件名由路径名给
出。路径名确定一个文件在文件系统中的位置。一个
完整的路径名由代表根目录的斜杠开始，到所指定的
文件为止。例如在图9.1
中，“
/
usr/users/shi/b.exe
”
确
定了文件
b.exe
在文件系统中的位置。另外，路径名
也可从正在执行进程的当前目录开始指定，例如，若
在图9.1
中的当前目录是zhang
的话，路径名
a.exe
与
/
usr/users/zhang/a.exe
具有相同的效果。
一般来说，UNIX
文件系统还具有如下特点：
·
UNIX
INXU
的文件是无结构的字符流式文件。
·
文件可以动态地增长或减少。
·
文件数据可由文件拥有者设置相应的访问权限而受
到保护。
·
外部设备，例如终端用磁带、磁盘设备、键盘等都
被看作文件。从而，设备可通过文件系统隐蔽掉设备
特性。在文件系统中，设备文件占据着文件系统目录
结构中相应的位置，用户程序按与存取其他文件时所
使用的系统调用和语法来读、写设备文件。因此，用
户程序既没有必要知道设备的内部特性，也不必在更
换或增加设备之后修改自己。
9.1.2
文件的分类
UNIX
文件可分为普通文件、目录文件和设备文件。
普通文件即存储用户和系统的有关数据和程序的文件。
它是无结构、无记录概念的字符流式文件。
目录文件则是由文件系统中的各个目录所形成的文件。
这种文件在形式上同普通文件一样，由系统将其解释
成目录。在UNIX
系统中，一个目录文件由多个目录
项组成，而每个目录项则由文件名及指示相应的文件
说明信息表(i
节点)
的标识符id
组成。
普通文件和目录文件都是无结构、无记录概念的字符
流式文件。文件系统以512
字节为一块，文件在块内
连续存放。对于普通文件和目录文件来说，文件的存
放方式既可以是顺序存取的，也可以是直接存取的。
UNIX
文件在文件系统中的存放采用的是索引结构方
法，从而，对文件存储块的分配可以是非连续的，且
文件长度可以动态变化。
设备文件与普通文件和目录文件不同，它除了在目录
文件和文件说明信息表，也就是
i
结点中占据相应的
位置之外，并不占有实际的物理存储块。因此，对设
备文件的读、写操作将实际上变为对设备的操作，而
对设备文件的保护也将变成对设备的保护。例如：
＞cp /dev/
tty
terminalread
把在终端上敲进的字符(
设备文件/dev/
tty
是用户终端)
读入，并把它们复制到文件
terminalread
上。
§9.2
文件系统的数据结构及其关系
9.2.1
文件系统的存储结构
UNIX
系统把文件信息存储在磁盘或磁带上，不过，
UNIX
系统的磁盘文件组织也可以当作一个连续的物
理块构成的磁带——
文件卷看待。在
UNIX
系统
中，一个物理存储器可包含一个或多个文件系统。这
些文件系统可以被动态装卸。为了简单起见，假定在
一个计算机系统中只存在一个文件系统。
文件系统由每块
512
字节或
512
字节的任意倍数所构
成的逻辑块序列组成。在同一个文件系统中，这些逻
辑块的大小完全相同。块长的选取将直接影响设备与
主存之间的数据传输速率和内存的存储能力。大的块
长将使得内存和设备之间的数据传输更加容易，但反
过来又使得内存页面长度增加，从而影响内存的有效
存储能力。在
UNIX
的许多版本中，大都采用每块
512
字节。
文件卷的结构如图9.2
所示。其中第
0#
块是引导块
(boot block)
。
引导块中装有引导或初启操作系统的
引导代码。
图9.2
文件系统存储结构
显然，在有多个文件系统的计算机系统中，只有一个
文件系统的引导块中装有引导代码，而其他的引导块
则是空的。
１＃块是超级块(
superblock
srobkuclpe
)
。超级块用来描述文件系
统的状态，例如文件系统的大小、有关空闲区分配和
回收用的堆栈等。有关超级块的结构将在后面部分进
一步介绍。
从2
＃块开始到
K+1
#
块为止的区域被用来存放文件说
明信息，也就是
BFD
表。UNIX
系统把一个文件的说
明信息称为
i
节点或索引节点(
inode
list)
。索引节点
表的大小由系统管理人员在进行系统配置时指定。
K+2
#
以后的块称为数据块，其中存放文件数据，包
括目录文件数据。UNIX
系统中文件系统的任一数据
块只能属于文件系统中某一个文件或空闲。
9.2.2
几种常用的数据结构
1.
资源管理结构
filsys
超级块中存放的最重要的数据结构是资源管理结构
filsys
。该结构中含有文件系统空闲块分配用堆栈及
i
节点分配用数据结构。在块设备作为文件卷安装时，
结构filsys
的内容被复制到内存专用区中，以使得对
空闲块和
i
节点的分配与回收能在内存进行。当文件
卷被卸下或需要重新读入或写出有关堆栈的内容时，
则将内存中的
filsys
结构复制回超级块中。
UNIX System
Ⅴ
中的
filsys
结构如下：
struct
filsys
{
文件卷总块数；
i
节点表块数；
空闲块栈区(
小于或等于50);
空闲块栈指针；
空闲块栈互斥标志；
空闲块总数；
空闲
i
节点数组指针；
空闲磁盘
i
节点指针；
空闲
i
节点数组互斥标志；
空闲
i
节点总数；
filsys
的修改标志，等；
}
filsys
结构被用来进行文件空闲块和
i
节点项的分配
与回收。
2. i
节点
UNIX
文件系统采用
SFD
SDF
和
BFD
方式管理文件。其中
SFD
SDF
称为符号文件目录，存放文件名以及指示该文件
的文件说明信息表标识符id
。由文件名和指示文件说
明信息表的标识符id
称为目录，把存放文件说明信息
和相应标识符的
BFD
称为
i
节点。
i
节点又分为磁盘
i
节点和内存活动
i
节点。其中磁盘
i
节点以静态形式
存放文件说明信息。磁盘
i
节点
dinode
结构包括：
struct
dinode
{
文件模式；
与该
i
节点联接的文件数；
用户标识;
文件大小;
存取权限;
同组用户标识;
该文件所用物理块的块号;
文件存取时间、修改时间和建立时间；
}
其中，文件模式表示文件类型，而用户标识符以及同
组用户标识定义对该文件具有存取权的用户集合，与
该
i
节点联接的文件数表示有多少个不同的文件名指
向该文件。另外，该文件所用的物理块号是一个由
40
个字节组成的字符数组
di_addr
［40
］，它指明文
件数据安放在逻辑盘上的位置。
在
UNIX System
Ⅴ中磁盘
i
节点的项占用64
个字节。
因此，一个长
512
个字节的块可存放
8
个
i
节点项。
系统在对文件进行各种操作时，为了减少设备的启动
次数以及提高操作速度，总是把相应的磁盘
i
节点复
制到内存的特定区域——
内存
i
节点表中。
内存
i
节点结构
inode
除了包含磁盘
i
节点结构的各项
之外，还包含了当前打开文件的状态信息。例如，内
存
i
节点的状态：包括该节点是否已被锁住，是否有
进程等待访问该
i
节点等。
总之，与
filsys
用于空闲区的分配与回收不一样，
i
节点主要用来存放文件的说明信息，以便进程利用
i
节点中的逻辑结构和物理结构信息搜索查找文件信息
以及完成对文件信息的保护和共享。
3.
目录项
UNIX
系统的目录项由文件名和磁盘
i
节点标识符id
组
成。其中文件名长度占14
个字节，标识符id
占
2
个字
节。从而，在一个
512
字节的磁盘块中可以存放32
个
目录项。
4.
系统打开文件表和用户打开文件表
在UNIX
系统中，文件系统主要描述程序和数据的静
的概念，而进程则反应这些程序和数据的动的特性。
进程怎样才能对文件发生作用呢？从用户的角度来
看，用户程序可使用对文件系统进行操作的系统调用
来完成。但是，从系统内部的角度来说，则需要有相
应的数据结构来记录和控制打开文件的用户进程以及
记录和控制那些共享同一文件的用户进程。为此
UNIX
系统设置了用户打开文件表和系统打开文件表。
用户打开文件表一般放在
user
数据结构中。使用用
户打开文件表，一个进程可同时打开
20
个左右的文
件。可打开的文件表项
u_ofile
ileu_中含有打开文件的描
述符fd
，以及系统打开文件表的入口指针fp
等。
系统打开文件表主要用来指明打开同一文件的不同进
程和不同进程所使用的不同打开路径，以及这些不同
进程和不同打开路径所对应的读写指针。因此可以认
为系统打开文件表是
i
节点表的补充。系统打开文件
表的每一项包括文件标识、文件访问计数、文件读写
指针和文件内存
i
节点入口指针和访问标志等。其中
文件标识与用户打开文件中fp
相连；文件访问计数指
示共享该文件的进程数，当文件访问计数为
0
时，则
表明已没有用户进程在使用该文件，从而可以释放有
关资源。文件读写指针则分别指出各进程在同一文件
中的读写位置。
资源管理结构、i
节点以及用户打开文件表和系统打
开文件表的关系如图9.3
所示：
图9.3
文件系统中主要数据结构之间的关系
在图9.3
中，用户进程通过用户打开文件表中的文件
描述符fd
，找到系统打开文件表的入口地址fp
，再由
系统打开文件表中对应项找到相关
i
节点的入口指
针，从而得到操作该文件所需的控制信息。有了
i
节
点中的控制信息，文件系统就可对磁盘数据区中的文
件进行所必需要的操作。另外，在图9.3
中，给出了
两个不同用户进程共享同一文件的例子。这两个进程
通过各自不同的文件描述符fd
A
和fd
B
，找到系统打开
文件表中不同的对应项，并通过系统打开文件表中的
i
节点指针而找到同一个内存i
节点，从而完成文件共
享。
§9.3
资源管理和地址映射
UNIX
文件系统的资源管理包括空闲磁盘块的分配与
回收、
i
节点和系统打开文件表的分配与回收等。关
于空闲磁盘块的分配与回收，UNIX
系统采用成组链
法来管理空闲区。本节主要介绍磁盘ｉ节点和内存ｉ
节点以及系统打开文件表的分配和释放方法。
9.3.1
磁盘ｉ节点的分配与释放
当一个新文件被建立时，在给该文件分配磁盘存储区
之前，应为该文件分配存放该文件说明信息的磁盘ｉ
节点。反之，当从文件系统中删除某个文件时，则要
首先删除它的磁盘ｉ节点项。UNIX System
Ⅴ
中的
算法
ialloc
被用来为新建立的文件分配磁盘ｉ节点项。
文件系统包含一个ｉ节点线性表，且每个磁盘ｉ节点
被顺序编号。ｉ节点线性表中存放这些被编号的ｉ节
点的类型字段。如果一个ｉ节点的类型字段为０，则
说明这个节点是空闲的。显然，当一个进程需要一个
新的ｉ节点时，它可以通过搜索ｉ节点线性表得到它
所要得到的ｉ节点项。为改善系统性能，UNIX
System
Ⅴ
在资源管理结构
filsys
中设置了一个磁盘
ｉ节点数组。该数组在系统初启时随
filsys
结构一起
被复制到内存的特定区中。
算法
ialloc
首先检查是否有其他进程在对磁盘ｉ节点
数组进行操作。如果有其他进程正在对磁盘ｉ节点数
组进行操作，则当前进程等待直到其他进程操作结束。
在没有其他进程对磁盘ｉ节点数组进行操作且磁盘ｉ
节点数组非空时，系统从ｉ节点数组中分配一个ｉ节
点给新创建的文件，然后，修改ｉ节点数组指针。紧
接着，ialloc
调用内存ｉ节点分配算法为新建立的文
件分配内存ｉ节点后将内存ｉ节点初始化。在对内存
ｉ节点进行了初始化之后，再将内存ｉ节点的内容写
回到磁盘ｉ节点中并修改磁盘空闲ｉ节点的计数。
有关
ialloc
算法，还有几个问题需要说明，首先是ｉ
节点数组中的ｉ节点号排列方法。系统从磁盘把ｉ节
点按从小到大的顺序读进i
节点数组，如图9.4
：
图9.4
空闲节点数组
系统在为进程分配磁盘ｉ节点时，按ｉ节点序号从小
到大的原则分配。当空闲ｉ节点数组为空时，系统锁
住ｉ节点数组，并从低到高地一个一个将磁盘上的索
引节点号填入ｉ节点数组中，直到ｉ节点数组满额或
再也找不到空闲ｉ节点。在ｉ节点数组满额的同时，
系统记住它所找到的最高序号的ｉ节点，并称之为
“
铭记”
ｉ节点。铭记ｉ节点是保存在ｉ节点数组中的
最后一个ｉ节点(
最大)
，如果系统分配到铭记ｉ节点
时，则启动
I/O
设备，从铭记ｉ节点开始，重新搜索
磁盘上的空闲ｉ节点，然后写进i
结点数组。这可以
确保系统不浪费时间去读那些已不含空闲ｉ节点的磁
盘块。
其次是在系统为新建立的文件分配磁盘ｉ节点和内存
ｉ节点之后，要检查所分配的ｉ节点是否是真正的空
闲ｉ节点。如果不是空闲ｉ节点，则要放弃本次分配。
至于为什么会出现分配到已分配ｉ节点的情况，则主
要是由于资源共享引起的。
综上所述，可将算法
ialloc
描述如下:
ialloc
:
输入：文件系统设备号，文件属性，联接该文件的目录数
输出：上锁的磁盘ｉ节点
begin
if
i
结点数组上锁
then
等待开锁
fi
if
ｉ节点数组空
then
锁住i
结点数组
为搜索空闲ｉ节点取铭记ｉ节点
搜索磁盘；将空闲ｉ节点置入ｉ节点数组
为i
结点数组解锁
fi
从ｉ节点数组中分配一ｉ节点
调用
iget
分配内存ｉ节点
if
iget
返回的内存ｉ节点为非空闲ｉ节点
then
把该ｉ节点的内容写回磁盘；释放该ｉ节点；
重新申请磁盘ｉ节点
else
将
iget
返回的内存ｉ节点初始化
将内容写回磁盘ｉ节点
空闲ｉ节点数减１
fi
end
磁盘ｉ节点的释放过程
ifree
是
ialloc
的反过程。但相
对来说，ifree
比较简单。ifree
首先把空闲ｉ节点数
加１，如果超级块的ｉ节点数组未被锁住且有空表
项，则
ifree
把释放的ｉ节点号放入ｉ节点数组后返
回。如果ｉ节点数组已处于满额状态，则
ifree
将新
释放的ｉ节点与铭记ｉ节点相比校。如果新释放的ｉ
节点小于铭记ｉ节点，则
ifree
将新释放的ｉ节点作
为铭记ｉ节点，并丢掉原来的铭记ｉ节点，否则丢掉
新释放的ｉ节点(
为什么？)
。如果超级块ｉ节点数组
是被锁住的，则此时系统正在进行磁盘ｉ节点搜索工
作。ifree
直接返回，以避免竞争条件(
有可能漏掉ｉ
节点)
。
9.3.2
内存ｉ节点的分配与释放
当系统打开文件并对其进行搜索、读写等操作时，为
相应的文件分配一个内存ｉ节点，以便把对应磁盘ｉ
节点信息复制到内存。一般来说，当系统创建一个文
件之后，如果未关闭该文件的话，则该文件已拥有了
相应的内存ｉ节点。此时，如果用户要对该文件进行
相应的操作的话，系统只需增加已有内存ｉ节点的访
问计数和做互斥处理即可。
内存ｉ节点的分配由过程
iget
itge
完成，iget
itge
的输入是文
件系统所在的设备名和磁盘ｉ节点号。输出是对应的
上了锁的内存ｉ节点。
首先，iget
itge
根据给定的磁盘ｉ节点号从内存ｉ节点数
组中搜索相应的内存ｉ节点。
如果该节点已在内存，则只需增加引用计数并锁定该
ｉ节点即可。否则，应从内存ｉ节点数组中分配一个
ｉ节点并启动设备，将对应磁盘ｉ节点信息复制到内
存ｉ节点后上锁返回。
另外，当一个文件被关闭时，系统释放其内存ｉ节点。
UNIX
系统中，释放内存ｉ节点的过程是iput
。iput
首
先判内存ｉ节点的访问计数是否等于１，如果访问计
数等于１的话，则表示当前没有其他用户使用该文
件，只需把内存ｉ节点项的内容复制回磁盘ｉ节点后
就可释放该内存ｉ节点项。如果访问计数大于１，则
只需将访问计数减１即可。
再者，如果表示与该文件相联接的目录数的联接计数
值为０的话，则表示该文件已不再需要，iput
释放与
该文件有关的所有磁盘块和磁盘ｉ节点。
9.3.3
系统打开文件表的分配与释放
在
UNIX
系统中，用户之间除了采用存取权限控制
方式共享文件信息之外，对于享有存取权限的用户，
还可以采用如下方式共享文件：子进程共享父进程打
开的所有文件；由系统调用
link
将不同的文件进行
联接等。对于这些不同的共享方式，用户和系统都需
要有相应的数据结构与之相应。UNIX
系统中设置有
系统打开文件表，存放各进程共享同一文件时的读写
指针；用户打开文件表通过指针fp
指向系统打开文件
表。
用户在读写、打开一个文件时，首先由iget
itge
在内存i
节
点数组中分配一空闲项，并根据用户提供的文件名，
找到与此文件对应的磁盘i
节点，然后将磁盘i
节点复
制到已分得的内存i
节点中。
此时，i
节点访问计数等于1
。如果磁盘i
节点已在内存
中，则对i
节点访问计数加1
。接着系统在系统打开文
件表中为访问该文件的用户分配一系统打开文件表项。
在分得系统打开文件表项后对该表项赋初值以建立系
统打开文件表和内存i
节点的联系。同时，在用户打
开文件表中填写指向系统打开文件表的指针fp
和把对
应的用户打开文件表项的序号fd
送给用户。经过上述
操作，两个以上的用户共享某一文件时，将会分配得
到与用户数相等的系统打开文件表项，且这些表项指
向同一内存i
节点。但在父、子进程共享同一文件
时，由于子进程是直接继承父进程打开文件，因此，
i
节点访问计数不变。
为了指明父、子进程共享同一文件的情况，在系统打
开文件表项中设有共享文件计数项以指明父、子进程
的个数。系统打开文件表项的分配由过程getf
ftge
完成。
关闭文件时，根据用户提供的文件标识符fd
找到对应
的用户打开文件表项，从而得到指向系统打开文件表
的指针fp
。然后就可清除用户打开文件表项和把系统
打开文件表项共享文件计数项减1
。[JP1]
当共享计数
项为0
时，则清除系统打开文件表项和将内存i
节点中
共享计数项减1
。用户打开文件表项和系统打开文件
表项的释放分别由过程close
lceos
和closef
lfceos
完成。
9.3.4
地址映射
UNIX
系统采用索引结构存放文件物理块的地址。即
在文件对应的i
节点中，放有存放文件物理块号的索
引结构。由对应文件的逻辑字节偏移量计算出逻辑块
号之后，就可搜索内存i
节点中的地址索引结构而得
到文件的物理块号。UNIX system
Ⅴ把常规文件分为
小型、中型、大型和巨型4
种。文件长度小于5K
的为
小型文件。对于小型文件，索引数组中的前30
个字节
被用来存放其物理块块号。文件长度大于5K
但小于
90K
的文件为中型文件。对于中型文件，i
节点的索
引数组所指的前10
个物理块中存放文件信息，而索引
数组所指的第11
个物理块中存放的则是存放文件信息
的物理块块号(
不包括前10
个物理块块号)
。
文件长度大于90K
但小于14.54M
的文件为大型文件。
于大型文件，UNIX System
Ⅴ采用二次间接寻址的
方法。即索引数组的和经第12
项所指的物理块中存放
的既不是文件信息，也不是存放文件信息的物理块
号，而是那些进行二次间接存放文件信息的物理块号。
对于更大的文件，称之为巨型文件。巨型文件采用三
次间接的办法存放。
索引数组中的直接块和间接块的关系如图9.5
所示。
在用户进程搜索文件时，根据相应的i
节点信息，可
根据上述地址变换关系由逻辑文件中的相对地址找到
实际文件信息所在的物理块。该转换算法由过程
bmap
abpm
完成。
图9.5
文件映射关系
§9.4
目录与搜索方法
UNIX
系统中的目录文件是以普通文件存放，且文件
的目录和说明信息采用了SFD
SDF
和BFD
结构方式以利于
共享。这样，当用户搜索当前目录下的文件时，可以
直接从当前目录开始搜索，而当被搜索文件不在当前
目录下时，则从根目录开始按指定路径搜索(
已做过
联接的其他目录下的文件被看作当前目录下文件)
。
由于UNIX
的文件系统采用树型结构，且只有最低一
级的叶才代表文件信息，因此，对文件信息的搜索的
大部分工作是对i
节点和对目录文件的搜索。
UNIX System
Ⅴ对内存i
节点的搜索采用散列搜索法。
首先，系统把空闲内存i
节点组成一个头指针为
ifreelist
链的链表，而已分配的内存i
节点则按给定的
散列函数分成不同的组。系统定义的散列函数为
ihash(x
ixh()=&
hinode
［(int)(x)&128
］。这里，x
代表要
搜索的i
节点号；ihash
的功能是将那些与128
进行模
运算后余数相同的i
节点编为一组，每组的头指针为
hinode
。ihash
的值即是i
节点x
的头指针hinode
的地址。
hinode
是一个数据结构，其定义为
struct
hinode
{
struct
inode
*
i_forw
;
}
hinode
［128
］;
其中，i_forw
是内存i
节点中定义的散列函数指针，
有了该项就可使散列队列与相应的i
节点对应起来。
显然，只要给定了i
节点号，就可由上述散列函数找
到该i
节点所在散列队列的头指针地址。然后，可进
一步采用顺序搜索法从该散列队列中找出所要搜索的
i
节点地址。
至于对目录文件的搜索，即从目录文件中找到与指定
分量相匹配的文件名的搜索，则采用顺序搜索法。这
是因为一个目录文件中的内容总是较少的，从而不会
占用太多的搜索时间。
对文件的存取搜索是通过过程namei
ienam
完成的。namei
ienam
将给定的路径名转换为所要搜索文件的内存i
节点指
针。
首先，namei
ienam
判定搜索路径名是从根目录开始的绝对
路径名，还是从当前目录开始的相对路径名。如果是
绝对路径名，则将根目录置为目录变量，否则将当前
目录置为目录变量。其次，namei
ienam
以目录变量为依
据，搜索到该目录变量所对应的内存i
节点，并验证
存取许可权。如果该目录文件是可以存取的，则依次
将该目录变量所对应的目录文件块读入内存，并且顺
序搜索与路径名中目录变量的下一个分量相匹配的文
件名。如果未找到相应的分量，则表明文件系统中不
存在相应的文件或路径名有错。否则，如果路径名未
搜索完毕的话，则namei
ienam
反复将目录变量沿路径名下
移，且重复从搜索目录变量对应i
节点开始的上述操
作。当路径名搜索完毕，且已找到对应文件名时，返
回该文件名所对应的内存i
节点指针。
算法namei
ienam
可描述如下:
namei
:
输入
:
路径名
输出
:
上了锁的内存i
节点
begin
if
路径名从根目录开始
then
目录变量
=
根目录
i
节点变量
=
根i
节点
else
目录变量
=
当前目录
i
节点变量
=
当前目录i
节点
fi
while(
还有路径分量未搜索完毕)
do
目录变量
=
下一个分量
验证存取权限
根据i
节点变量中的说明信息，读入对应的目录文件块
顺序搜索目录文件块中的项
if
目录文件块中的一个登记项与目录变量相同
then
得到目录变量的内存i
节点号
释放i
节点变量中的i
节点
散列法搜索内存i
节点
i
节点变量
=
目录变量对应的i
节点
else
目录中无该分量，返回有关信息
fi
i
节点变量中i
节点上锁返回]
od
end
§9.5
文件系统的系统调用
本节从用户使用文件系统的角度介绍文件系统的动作。
UNIX
文件系统为用户提供的系统调用有打开和关闭
文件用的open
onpe
与close
lceos
，创建文件用的creat
，对打开
文件进行读写操作的read
和write
，对文件树进行操
作的chdir
crhdi
和chown
，改变文件属性的chown
，chmod
cohdm
和有关文件联接的link
，unlink
以及进行通信操作的
pipe
等。无论用户使用何种有关文件系统的系统调
用，都必须指定该系统调用所要进行操作的文件路径
名(
文件名)
或者文件描述符fd
。只有在指定了文件路
径名或文件描述符fd
之后，系统调用才能对有关文件
进行操作。
在用户进程使用系统调用时，首先，执行该系统调用
将使得系统产生一条称为陷阱(trap)
指令的信息，从
而启动中断和陷阱总控程序(
后述)
，使得系统由用户
态进入系统态执行。在陷阱指令启动中断和陷阱总控
程序的同时，系统调用的各参数写入user
erus
结构中对应
部分。然后，由中断和陷阱总控程序，系统进入执行
与系统调用有关的文件系统内部过程和缓冲区管理过
程等。文件系统的系统调用与其内部过程的执行关系
如图9.6
所示。
下面，以系统调用read
为例，进一步说明系统调用的
执行过程。
图9.6
文件系统的系统调用与低层算法
在使用系统调用read
之前，准备进行读操作的文件必
须是打开的。也就是说，在read
之前必须先使用系统
调用open
onpe
或creat
(
非管道文件时)
，并将该文件的访问
许可权设置成可读的，否则无法进行读操作。在调用
了系统调用open
onpe
之后，用户得到返回的进程标识符
fd
，且系统已将所要读文件的磁盘i
节点复制到内存i
节点中和建立了用户打开文件表、系统打开文件表与
内存i
节点之间的联系。例如，在系统调用open
onpe
打开
文件/user/users/
zhang
后的数据结构之间的关系如图
9.7
所示。这里，假定/user/users/
zhang
已在同一个进
程中被打开了3
次，且每次都设有不同的读写权限。
图9.7
打开文件的数据结构之间的关系
显然，在图9.7
例中，可以用文件标识符fd
1
、fd
2
或fd
3
读文件“
/user/users/
zhang
”
。设用文件标识符fd
1
将
count
个字符读到内存地址为buffer
ferbuf
的工作区中，则
系统调用read
的调用格式为
read(fd
feradd(
1
，buffer
ferbuf
，count);
在系统执行该系统调用时，首先产生陷阱指令而进入
硬件陷阱处理机构，并根据包含陷阱向量入口地址的
中断与陷阱总控程序来选择相应的处理程序和调用文
件系统的低层程序。在陷阱指令发生后，硬件将有关
参数从用户区送到user
erus
结构的u.u_arg
gu.数组中，以便
系统调用程序在核心栈上执行时能够使用这些参数。
在执行read
调用时，置入u.u_arg
gu.的参数是buffer
ferbuf
和
count
等。除此之外，系统还将user
erus
结构中的读写方
式设置为“
读”
，以及将user
erus
结构中的偏移量设置为系
统打开文件表中读指针所指的值以便指明读该文件时
的起始位置。
在设置了有关参数之后，系统由fd
1
找到fp
1
，并由fp
1
找到对应的内存i
节点。该搜索过程由过程getf
ftge
完成。
在找到了对应的内存i
节点之后，为了避免竞争条
件，系统将该i
节点锁定之后进入读操作。
读操作是一个循环过程。系统首先用算法bmap
abpm
将文
件的字节偏移量映射为磁盘块块号，并计算出在该块
中的起始位置和应读写字符长度。在把该块读入内存
用户地址buffer
ferbuf
之后，系统根据已读入的字符数，修
改user
erus
结构中的有关参数，然后重复读操作过程，直
到完全满足用户要求或fd
1
所指文件中不再含有数据。
读操作过程是由后述设备管理程序完成的。
系统调用read
的实现过程可描述如下:
read :
输入
:
文件描述符fd
用户内存地址buffer
要读字节数count
输出
:
复制到用户区的字节数
begin
在user
结构中设置用户区地址，字节偏移与字节计数等
由文件描述符fd
得到系统打开文件表指针
检查文件的可存取性
由系统打开文件表得到内存i
节点指针
锁定内存i
节点
repeat
将磁盘中数据读入内存buffer
中
until
读完count
字节或文件中不再存在字符
将内存i
节点解锁
返回已读入字符总数
end
§9.6 UNIX System
Ⅴ的中断和陷阱总控程序
1.
中断和陷阱总控过程
通常，在系统执行期间内，系统内发生的一些突发事
件要求处理机改变其控制流程去执行处理这些突发事
件的特定软件。这些突发事件被分为两类:
与当前执
行进程有关的事件称为陷入或陷阱，例如系统调用指
令、指令错、溢出等;
与当前执行进程无关但与整个
系统或其他进程有关的事件称为中断，例如I/O
数据
传送完成、时间片到等事件。
在UNIX System
Ⅴ中，系统对中断和陷阱的处理既
有相同的一面，又有不同的一面。
系统中有一个称为陷阱和中断向量表的系统控制块
SCB
SBC
。SCB
SBC
中存放有由陷阱和中断处理程序的入口地
址和对应的陷阱或中断名组成的陷阱或中断向量。
SCB
SBC
的部分内容如图9.8
所示。
当陷阱或中断发生时，处理机将自动地根据陷阱或中
断名找到对应处理程序的入口地址，从而转入去执行
相应的处理程序。中断和陷阱总控程序就是用来完成
上述功能的。
图9.8
部分陷阱和中断向量
向量地址(16
进制)
向
量
名说
明
00
保留
04
×macheck
机器校验
08
×kspinv
核心栈无效
0c
×powfail
电源失效
10
×privinflt
非法指令
14
×xfcflt
扩展功能调用指令
18
×respflt
保留操作数
1C
×resadlt
保留寻赴址方式
28
×tracep
跟踪自陷
2C
×bptflt
断点故障指令
40
×syscall
系统调用(
更换到用户心态)
4C
×chmu
系统调用(
更换到用户态)
CD
×clock
时钟中断
10C
×ubaint
单总线适配器中断
FD
×cdtrint
控制台磁带机接收中断
…
中断和陷阱处理的不同方面则包括以下几点。首先，
由于中断是与整个系统或非当前执行进程有关的，其
处理程序只能在系统的中断栈上执行。反之，由于陷
阱是与当前进程有关的事件，可以在当前执行进程的
核心栈上执行有关陷阱处理程序。再者，为了对不同
的中断和陷阱做出不同的反应，系统对每个中断和陷
阱设置有相应的优先级。当处理机转入陷阱处理时，
由于陷阱处理不做进程切换，因此，处理机状态字中
的中断优先级一般不用改变。但是，在有中断请求
时，系统只响应那些优先级高于状态字中的中断优先
级的中断。至于那些优先级低于状态字中的中断优先
级的中断，则被屏蔽。
因此，一般来说，进入陷阱处理程序与处理机状态字
中的中断优先级无关，而中断处理程序则只有处理机
状态字中的中断优先级低于请求中断的中断优先级时
才能进入。
中断和陷阱处理总控程序就是在系统内发生了中断或
陷阱事件之后，根据中断和陷阱的处理优先级，接收
来自于硬件中断或陷阱信号，并控制系统转入相应处
理过程以及恢复现场的程序模块。在UNIX System
Ⅴ中，中断和陷阱总控程序由一个用汇编语言编写成
的程序trap.s
构成。显然，用汇编语言编写中断和陷
阱总控程序的目的是出于提高效率和与硬件接口方便
的考虑。
总控程序含有几乎全部中断与陷阱向量的入口地址。
2.
中断分类
UNIX System
Ⅴ对中断作分类处理，
被分为5
类:
(1)
进程调度中断
进程调度中断是一个由软件事件引起的中断。由于
System
Ⅴ的调度程序在进程0
的核心栈上执行，在中
断栈或核心栈上执行的核心程序都不能直接调用进程
调度程序。从而，
在系统处理中断或陷阱的过程
中，若时钟片到等事件使得调度标志runrun
被设置
时，则在中断或陷阱处理结束时，产生进程调度中断
信号并调用过程Xreshed
serdhXe
进行调度处理。
(2)
时钟中断
主要是间隔时钟中断。时钟计数器以微秒为单位递增。
当计数器的值计数到16,667
微秒时，产生一次时钟中
断以启动时钟中断处理程序。
当时钟中断发生60
次，也就是累计时间达到1
秒时，
中断处理程序设置调度标志runrun
和计算各进程的
优先级等。
(3)
电源失效和恢复
(4)
机器故障中断
这几种中断的主要目的是进行现场保护与恢复，以及
有关检验等。因此，电源失效和机器故障中断都享有
较高的优先级。
(5)
设备中断
设备中断程序包括控制台中断、单总线适配器中断和
多总线适配器中断等部分。
3.
中断处理
中断处理包括三个部分，即通过总控程序进入中断处
理子程序;
中断处理子程序进行中断处理;
退出中断。
尽管中断和陷阱向量的入口地址都放在中断和陷阱总
控程序trap.s
中，但在中断和陷阱处理程序的进入与
退出方式上，二者的处理方法是不相同的。这是因为
陷阱处理要求陷阱发生指令与处理子程序之间传递较
多的参数，且中断处理子程序与陷阱处理子程序在不
同的堆栈上执行。
进入中断处理时，trap.s
除了用一条汇编指令保护有
关寄存器(
现场)
的内容之外，没有公共的入口处理程
序，各中断向量的入口处理也非常简单，只需用几条
过程调用指令就可实现。例如控制台磁带机接收中断
的入口处理程序为:
Xcdtrint
:
calls $0
，_
catrint
brb
int_ret1
te1_其中，Xcdtrint
为中断向量；calls
lscal
是过程调用指令；
_
catrint
是被调用过程名；而$0
则表示发生中断处理
时传递给被调用过程的参数个数，$0
表示此次中断处
理不需要外部参数。brb
int_ret1
te1_则表示中断处理完
毕，处理机空闲。
不同的中断对应有不同的中断处理程序。不过，在系
统进行中断处理后退出中断以及恢复被保护现场部分
的程序是一段公用代码。在这段代码中，首先，系统
恢复有关通用寄存器，并置处理机空闲标志。然后，
若中断是在用户态下发生且设置有再调度标志
runrun
，则请求进程调度中断将用户态改为核心态
以便执行调度程序。如果没有设置runrun
再调度标
志，或中断发生在核心态下，则系统返回原被中断处
继续执行。
4.
陷阱处理
与中断处理时不同，
UNIX System
Ⅴ中含有公共的
陷阱入口处理程序。首先，trap.s
中的有关程序区别
所发生的陷阱类型，并将陷阱的类型值和有关参数压
入堆栈。然后，调用公共的入口处理程序处理各种不
同的陷阱。
UNIX System
Ⅴ可处理12
种不同的陷阱。即：
SYSCALL
更换到核心态方式(
系统调用)
SEGFLT
转换无效
PROTFLT
访问违章
PRIVFLT
非法指令
RSADFLT
保留寻址方式
RSOPFLT
保留操作数
ARTHRP
算术自陷
TRCTRAP
跟踪自陷
BPTFLT
断点故障指令
XFCFLT
扩展功能调用指令
CMPTFLT
兼容方式
RESCHED
进程调度中断
对上述12
种陷阱处理可根据其发生的时机分为两种情
况:
即核心态方式下的陷阱处理和用户态方式下的陷
阱处理。
由于UNIX
系统规定，核心程序不使用系统调用，以
及UNIX System
Ⅴ的核心程序不搞请求调页，即所
有的核心代码全部在内存，从而上述各种陷阱一般不
会在核心态方式下发生。如果在核心态方式下发生了
陷阱，则系统认为是出现了故障，从而打印出一些用
户现场信息之后进入死循环，等待系统管理人员干预。
用户态下的陷阱处理可进一步分为三种情况，即系统
调用、地址转换无效和用户自定义处理(
软中断处理)
方式。
上述陷阱处理的公共程序是一个名为trap
的过程。其
调用形式为:
trap(sp
tsrapp(
，type
，code
，pc
，ps
)
其中，sp
为发生陷阱的进程用户栈指针，type
指明陷
阱类型，code
是确定系统调用序号的代码操作数，pc
为程序计数器的内容，ps
为处理机状态长字。trap
过
程的处理流程如图9.9
所示。
在图9.9
中，除了SYSCALL
SLACY
和SEGFLT(
地址转换无
效)
和RESCHED(
进程调度)
三种陷阱之外，其他9
种
陷阱都已转换成软中断方式处理。其中各种软中断所
使用的信号定义如下:
SIGILL
ISLGI
非法指令
SIGTRAP
SPTARGI
跟踪陷入
SIGBUS
SBUGI
访问违章
SIGFPE
SFPEGI
算术陷入
SIGSEGV
SVGIE
转换无效
SIGEMT XFC
SFETCGMXI
指令故障
图9.9 trap
程序处理流程图
系统提供标准软中断程序进行处理。图9.9
中有关
SEGFLT
SFLTGE
的处理是针对System
Ⅴ早期版本的。当进
程访问到一个不在内存中的页面时，硬件将产生转换
无效故障。在System
Ⅴ早期版本中，由于未采用请
求调页技术，即进程在执行前将所需页面全部调入内
存，从而产生转换无效的原因只能是用户栈满引起的。
因此，系统首先进行用户栈扩充，如成功则进程继续
执行，否则系统向该进程发生转换无效信号。
图9.9
中的另一种陷阱处理是有关系统调用的处理。
由于系统调用的处理需要更进一步调用核心程序来完
成用户所要求的功能，因此，系统调用的处理由如下
几步组成:
(1)
确定系统调用序号i
。
系统调用序号i
由下式确定: i = code & 0377
若0
＜i
＜64
，则i
是真正的系统调用序号；
若i
＞64
，则i
被赋值为0
；
若i=0
时表示该系统调用的参数传递方式为间接方
式，需通过间接参数指针再求系统调用号。
(2)
传递参数到user
erus
结构中。
当用户进程使用系统调用命令请求系统服务时，首先
在用户空间内提供系统调用所需要的参数变量表。当
陷阱发生时，系统将装有这些参数变量表地址的通用
寄存器压入用户核心栈，并将有关寄存器地址赋给
user
erus
结构中的u.u_aro
ou.指针，从而将参数变量表中内
容传送到user
erus
结构的u.u_arg
gu.中，使得系统调用处理
程序可以使用它们。
(3)
转入系统调用处理程序。
与系统调用号i
相对应，系统内有一张称为系统调用
表的数据结构表system
，该数据结构除了指出系统调
用所需要的参数变量个数以及经寄存器传送的参数变
量个数之外，还包含了该系统调用所对应的处理程序
入口地址。
(4)
系统调用处理完毕后计算当前进程的优先级。
(5)
若需重新调度，则执行调度程序，选择优先级高
的进程执行。
(6)
检查发生系统调用的进程是否收到了软中断信
号，如收到了软中断信号的话，则进行软中断处理。
(7)
返回。
§9.7
缓冲区管理
由于文件系统的物质基础是磁盘或磁带，因此，对文
件系统的一切存取操作，实质上都是通过对块设备的
读和写来实现的。慢的磁盘传输速率将直接影响系统
的处理时间和性能。为了调节文件系统的读写和系统
处理之间的速度不匹配的问题，以及为了减少启动磁
盘设备的次数，UNIX
系统设置了一个称为数据缓冲
区的数据结构。
同理，在键盘、显示器和打印机等字符设备与内存之
间也存在着频繁的数据流动，这些数据流动也伴随着
存取速度的不平衡，UNIX
系统也设置有字符缓冲区
以减少这种存取速度的不平衡。本节主要介绍块设备
缓冲区的实现原理。
9.7.1
缓冲池结构
UNIX System
Ⅴ有一个由200
个缓冲区组成的缓冲池。
每个缓冲区的长度可以是512
字节或1024
字节。假定
每个缓冲区长度等于512
字节。用于存放数据的区域
被称为缓冲数据区。用于控制的区域被称为缓冲控制
块或缓冲头部。对缓冲区的分配，搜索和存取都是通
过缓冲控制块实行。因此，缓冲池的结构具有两层意
思，一是每个缓冲控制块的构造，利用缓冲控制块中
的信息实施对缓冲区的操作;
二是缓冲区的队列构
造，利用这些构造，可以方便地对缓冲区进行操作。
缓冲控制块和缓冲数据区间具有一一对应的映射关
系，除了讨论缓冲控制块时之外，把缓冲控制块和缓
冲区统称为缓冲区。缓冲控制块的构成如图9.10
。
图9.10
缓冲控制块的结构
图9.10
所示的缓冲控制块中包含了一个逻辑设备号和
该缓冲区所对应的逻辑磁盘数据块号。另外，缓冲控
制块除了包含有指向缓冲数据区的指针之外，还包含
有两组用来构成不同缓冲队列结构的指针。这些指针
和队列将在后续部分中解释。再者，缓冲控制块中的
状态部分指明该缓冲区当前所处的状态。这些状态是
如下条件的组合。缓冲区当前为“
上锁”
或“
开锁”
状态;
缓冲区是否包含有效数据;
系统在把该缓冲区分配出
去之前是否必须把缓冲区中内容写到磁盘上(
延迟写);
系统当前是否正在从磁盘往磁盘缓冲区读信息或把缓
冲区的内容写到磁盘上;
以及一个进程是否正在等待
该缓冲区变为开锁等。
显然，由于缓冲区是独享资源，从而不允许多个进程
同时对一个缓冲区进行操作，因此缓冲控制块中设有
锁定位。另外，一个磁盘块在同一时间内也不能映射
到多个缓冲区上；否则，系统将会不知道哪一个缓冲
区中包含着当前数据而产生读写错误。
缓冲池结构由多个缓冲区队列组成，包括空闲缓冲区
队列、设备缓冲区队列和设备I/O
请求队列等。
空闲缓冲队列又称空闲av
队列，它是系统所拥有的所
有空闲缓冲区资源。在系统初始化时，所有的缓冲区
按序号高低挂在空闲av
队列上。当文件系统申请一个
缓冲区时，从空闲av
队列首部取下一个缓冲区，而一
个缓冲区被释放时则挂入空闲av
队列末尾。图9.11
给
出了空闲av
队列的构成情况。
图9.11
空闲缓冲队列结构
设备缓冲区队列又称设备b
链。设备b
链链接所有分
配给各类设备使用的缓冲区。每类设备都有自己的设
备b
链，每类设备的设备b
链按散列算法组成64
个队
列，每个队列头部都有自己的头标。
当系统为一个设备b_dev
vb_中的逻辑块号b
分配一个缓
冲区之后，若系统要存取一个设备b_dev
vb_上的逻辑块
b
时，利用下面散列算法构成或搜索散列队列:
i=( b_dev + b ) mod 64
其中i
为散列队列头标。设备b
链的结构如图9.12
。
在图9.12
所示的设备b
链结构中，省略了逻辑设备号
b_dev
vb_。而且，每个散列队列头标对应着一个块号以
64
取模后的余数所组成的缓冲区队列，这些缓冲区既
可能是空闲的，也可能正在被使用。
图9.12
设备b
链结构
为什么要将一个空闲缓冲区同时挂在空闲av
队列和设
备b
链队列中的理由是：
当系统需要存取某个磁盘的数据时，为了减少启动设
备的次数，总是先从设备缓冲b
链中寻找与之相对应
的数据块。如果该块不在b
链中，则从空闲av
链中按
最近最少使用算法，摘下一空闲缓冲区，改写缓冲控
制块中的块号之后挂入对应的散列队列，如果该块已
在b
链中，则系统不必启动磁盘。与此相似，当系统
释放某个缓冲区时，仍将该缓冲区放置在设备b
链
中，缓冲区内的数据则一直等到重新往该缓冲区内写
入新数据时才释放。这样，系统就可从设备b
链中搜
索到所有使用过的，但未被改写的特定缓冲区。
设备I/O
请求队列又称块设备av
链。每个物理块设备
都有一个I/O
请求队列，设备I/O
请求队列中的缓冲区
属于设备b
链，但不属于空闲av
队列。设备I/O
请求队
列是由正在请求该块设备进行读写操作的缓冲区所组
成的队列，其中的缓冲区使用与前面所述的缓冲控制
块不完全相同的I/O
缓冲控制块，以指示物理设备是
否正在使用以及有关寄存器的地址等。
设备I/O
请求队列为单向队列。
9.7.2
缓冲区的分配与释放
缓冲区的分配与释放包括缓冲区分配(
getblk
)
、空闲
缓冲区分配(
geteblk
)
以及释放缓冲区(
brelse
lsebr
)
操作。
当文件系统试图检索某一个数据块时，它首先判定所
要存取的逻辑设备号和逻辑块号，然后，检查该数据
块是否在缓冲池中。如果不在，则分配给它一个空闲
缓冲区。getblk
被用来分配缓冲区。
在把一个缓冲区分配给一个对应磁盘块时，将可能出
现5
种典型情况。即:
(1)
该数据块在设备b
链的散列队列中，且缓冲区是空
闲的；
(2)
设备b
链的散列队列中不存在对应的缓冲区，因
此，从空闲av
链首取一个缓冲区分配给该磁盘块；
(3)
在处理上述(2)
时，
如果空闲av
链的链首缓冲区是
一个标上了“
延迟写”
(
后述)
标记的缓冲区，则系统必
须将该缓冲区的内容写到磁盘上，并分配下一个缓冲
区后返回。
(4)
系统在散列队列中找不到该块，且空闲av
队列已
空时，进入等待状态。
(5)
系统在散列队列中找到了对应的数据块的缓冲
区，但此时该缓冲区已被锁定，系统仍进入睡眠状态
等待该缓冲区变为空闲。
geteblk
算法用来从空闲av
队列中取一个缓冲区。首
先检查空闲av
队列是否为空，若为空时睡眠等待。另
外，如果空闲av
队列中取下的缓冲区为延迟写的话，
需将该缓冲区的数据块先写回磁盘。geteblk
算法用
来把空闲av
队列中的缓冲区链入设备b
链队列。
当系统不再需要一个缓冲区，或当I/O
操作完成时，
系统调用brelse
lsebr
算法释放该缓冲区。当系统释放一个
缓冲区之后，它唤醒那些因为空闲av
队列空而睡眠的
进程。
9.7.3
缓冲区数据读写
对缓冲区的读写包括来自于两个方面。第一是从磁盘
块到缓冲区的读写，第二是从缓冲区到内存用户区的
数据流动。其中，缓冲区和内存用户区之间的数据流
动由算法iomove
完成，而缓冲区和磁盘块之间的数
据流动则由算法bread
，breada
和bwrite
iterbw
，bdwrite
iterbdw
以
及bawrite
iterbaw
完成。这些算法之间的关系如图9.13
所示。
首先，iomove
是被文件系统有关读写过程所调用的，
iomove
把指定的用户源地址中的指定长度的数据复
制到指定的缓冲区中，另外，也把指定缓冲区中的数
据复制到给定目的地址的内存用户区中。由于缓冲区
和内存用户区同在内存，因此，缓冲区和内存用户区
之间的数据流动不会出现速度不匹配问题。
图9.13
缓冲区的数据读写
从磁盘块读数据到缓冲区有二种方式。一种被称为一
般读(bread)
，另一种称为预先读(
breada
)
。一般读
bread
过程的输入是所要读的逻辑块号，输出是含有
读入数据的缓冲区指针。首先，bread
调用算法
getblk
得到对应的缓冲区。如果该缓冲区中的数据是
有效的，则不启动磁盘设备返回。否则，经设备驱动
程序启动磁盘读，且调用bread
的进程因等待读盘完
成而进入睡眠状态，待到读盘完成后返回缓冲区指针。
bread
过程可描述如下:
bread:
输入:
逻辑块号
输出:
含有数据的缓冲区指针
begin
调用getblk
得到缓冲区
if
缓冲区中数据有效
then
返回缓冲区指针
fi
启动磁盘读
if
读盘完成
then
返回缓冲区指针
fi
end
预先读breada
的输入是立即读的逻辑块号和异步读的
逻辑块号。breada
的输出则是装有立即读逻辑块号所
对应数据块的缓冲区指针。breada
过程等待立即读的
逻辑块号读入缓冲区，并启动磁盘异步读逻辑块。然
后返回立即读的逻辑块所对应的缓冲区的指针。
UNIX
系统使用预先读方式是因为在一个进程顺序地
读一个文件时，如果系统异步地请求第二个磁盘块，
则一旦需要这部分数据时，它们将在内存缓冲区中。
从而可以提高读数据的速度。
breada
可描述如下:
breada
:
输入:
立即读的逻辑块号和异步读的逻辑块号
输出:
含有立即读逻辑块的缓冲区指针
begin
if
第一块不在缓冲池中
then
调用getblk
得到缓冲区
if
缓冲区中数据无效
then
启动磁盘读
fi
fi
if
第二块不在缓冲池中
then
调用getblk
得到缓冲区
if
缓冲区中数据有效
then
释放缓冲区
else
启动磁盘读
fi
fi
if
第一块在缓冲池中
then
读第一块，返回该缓冲区指针
fi
if
第一个磁盘块读完成
then
返回该缓冲区指针
fi
end
这里，
当第二个数据块对应的缓冲区中数据有效
时，
breada
应释放该缓冲区，以便下次其他进程可
以申请得到该缓冲区。
把一个缓冲区的内容写到磁盘块上去的方法与读时类
似。首先，系统通知驱动程序说有一个缓冲区的内容
应该被输出，从而驱动程序选中对应的物理块以便进
行写操作。如果写是同步的，则调用者进程因等待写
操作完成而进入睡眠，且当写操作完成后再释放缓冲
区。如果写是异步或延迟写的，则系统启动传输，但
不等待传输完成而返回。算法bwrite
iterbw
可描述如下:
bwrite
:
输入
:
缓冲区指针
begin
启动磁盘写
if
缓冲区标志写是同步进行
then
等待传输完成后释放缓冲区
fi
if
缓冲区标志延迟写
then
将该缓冲区放入空闲av
队列
fi
end
bawrite
iterbaw
的功能是异步写一块。它由驱动程序启动传
输之后，不等传输完成而返回。bawrite
iterbaw
的输入是缓
冲区指针。bdwrite
iterbdw
的功能则是延迟地写一块，且不
启动传输而返回。标志了延迟写的缓冲区要等到
bwrite
iterbw
时启动传输设备而写到磁盘上。异步写的目的
是提高写盘速度，而延迟写的目的则是为了让数据块
在内存内待尽量多的时间，以减少不必要的I/O
操作。
但反过来，由于延迟写没有立即把数据写入磁盘，当
系统发生瘫痪等时将产生磁盘数据错误。
§9.8
块设备驱动
UNIX
系统中的设备可块设备和字符设备。管理这些
设备的程序模块被称为I/O
子系统。I/O
子系统控制完
成进程与外设之间的通信任务。其中，I/O
子系统的
核心部分是控制外设的设备驱动程序。本节主要介绍
UNIX
系统的块设备驱动原理。
从使用方式看，UNIX
的块设备有三种用法，即用于
交换系统、用于文件系统和用于字符设备。在交换系
统中，UNIX
系统设置有专用的数据结构和管理程
序，它们在功能上是与用作文件系统或字符设备相独
立。对于文件系统，UNIX System V
采用了200
个缓
冲区构成的缓冲池来支持设备和内存之间的数据交换。
本节将介绍设备驱动程序和调用它们的方法。用作字
符设备的块设备主要是那些具有很高存取速度的设备。
由于省去了缓冲区介入，从而具有高的数据传输速率。
使用这种“
原始”
的I/O
传送的驱动程序是从字符读写
过程直接调用块设备的策略接口(
后述)
。下面，分别
介绍驱动程序与系统管理员的接口，与文件系统的接
口以及驱动程序的动作原理等。
9.8.1
设备配置
在UNIX
系统中，每一类设备都对应有自己的驱动程
序。而且，每一个设备都有自己唯一的设备名，并能
像文件那样对其进行存取操作。因此，每个设备都作
为特殊文件在文件系统目录树中占据一个节点，只是
其i
节点的类型与普通文件不同而已。一个新设备和
系统的联接只能依靠系统管理员在系统允许的范围内
进行系统配置和使用相应的命令，例如mknod
来建立
特殊文件。
设备配置有三种办法进行。第一种办法是由管理员把
配置数据写入文件。配置数据通常以简单的形式规
定，然后由配置程序将它转换成适合编译的文件。这
个文件在生成核心代码时被编译和联接。
第二种办法是管理员在系统已经运行之后提供一些配
置信息，系统动态地修改内部配置表。第三种办法是
自定义设备允许系统知道哪些设备被安装上了，从而
填写自身的配置表。
mknod
命令被用来建立设备特殊文件。mknod
命令要
求管理员提供文件名，文件类型(
块设备或字符设备)
和主设备号，次设备号。例如:
mknod
/dev/
ttyb
C 2 13
创建一个设备名为/dev/
ttyb
的字符终端(C
代表字符设
备文件，b
表示块设备文件)
，该设备的主设备号是
2
，次设备号是13
。在UNIX
系统中，主设备号指示
一种设备类型，而次设备号则表示该类设备的一个单
元。
9.8.2
设备驱动程序的接口
块设备驱动程序把一个逻辑设备号和块号组成的文件
系统地址转换成物理设备上特定的物理块号，并启动
物理设备和控制器进行I/O
传输工作。驱动程序有两
个接口，和文件系统的接口以及与硬件的接口。驱动
程序和文件系统的接口是由块设备开关表和字符设备
开关表描述的。每一种设备类型在表中有若干表项，
这些表项在文件系统的有关系统调用被调用时引导系
统转向适当的驱动程序入口。
另外，硬件与驱动程序的接口是由机器的有关控制寄
存器或操纵设备的I/O
指令，以及中断向量组成的。
当一个设备控制器发出中断请求时，系统识别发出中
断请求的设备，并调用适当的中断处理程序。
驱动程序与文件系统和硬件的接口如图9.14
所示。
图9.14
驱动程序及其接口
块设备开关表和字符设备开关表如图9.15
所示。
图9.15
块设备和字符设备开关表
对于块设备开关表中的驱动程序，当文件系统调用有
关系统调用时，系统从文件描述符fd
找到系统打开文
件表项fp
以及内存i
节点。从i
节点信息中，可以检查
文件类型，从i
节点中抽出主设备号和次设备号并使
用主设备号作为索引表项进入开关表和调用到适当的
驱动程序。
系统调用open
onpe
打开一个对应设备，例如gdopen
gndope
打开
磁盘驱动器。该驱动程序使调用进程和被打开设备之
间建立联系，并初始化其他驱动程序用的数据结构。
返回之前当然还要检查打开的合法化，例如不能同时
有几个进程打开同一个打印机设备进行读写操作等。
打开一个设备相当于为一个进程分配一个设备。显
然，在使用缓冲池的文件系统中，除了刚开始时需要
打开磁盘设备之外，在缓冲区和磁盘块之间进行I/O
传输时不必打开设备。
系统调用close
lceos
断开用户进程与一个设备的连接。注
意，只有当没有其他进程打开此设备时才可以调用关
闭过程，否则会引起混乱。
关闭一个设备文件相当于释放一个进程所占有的设备。
缓冲区和设备之间的I/O
传输是利用策略接口strategy
过程完成。strategy
过程打开相应的磁盘启动程序并
调用过程_start
t_启动磁盘控制器和利用过程_
addr
将
磁盘物理块号转换为物理地址。然后，启动设备开始
I/O
传输并调用iowait
itaoiw
过程进行睡眠，直到I/O
传输完
成后再由控制器发出中断信号，系统响应中断后由中
断处理程序进行中断处理并由检验程序检验该次I/O
传输是否正确之后再唤醒睡眠进程并释放缓冲区。
设备与驱动程序的通信方法依赖于硬件。一般计算机
中大都设置有状态控制寄存器和数据缓冲寄存器。在
数据缓冲寄存器的数据发送完毕之后，状态控制器将
会通过总线发出传输完成中断信号，从而引起系统执
行一个中断处理程序。至于执行哪一个中断处理程
序，则要根据发出中断的设备和中断向量所决定的。
一般来说，中断向量所对应的中断处理程序都是针对
一类设备的，系统在调用设备中断处理程序时必须将
设备号和其他有关参数传递给它，以便识别引起中断
的特定设备单元。例如，图9.16
中的中断向量表的大
部分中断向量都对应着多个入口点。当某个外设，例
如tty07
发出中断之后，系统将利用中断机构传递来
的参数确定发出中断的次设备号并调用ttyintro
troynit
过程
处理中断。
图9.16
外围设备和中断向量
总之，块设备驱动程序必须把由逻辑设备号和块号组
成的文件逻辑地址翻译成块设备上的特定物理地址，
并启动块设备和相应的控制器来进行I/O
传输工作。
在传输完成时还要接受中断信号并完成相应的中断处
理。
§9.9
字符设备驱动
字符设备是指在I/O
传输过程中以字符为单位进行传
输的设备，例如键盘、打印机等。在UNIX
系统中，
字符设备以特别字符文件的方式在文件目录中占据一
个席位并拥有相应的内存i
节点。与块设备一样，i
节
点中的文件类型指明该i
节点所说明的是一个字符文
件，用户可以用与块设备相同的方式打开，关闭和读
写特别字符文件。下面先介绍有关字符设备管理的数
据结构后，再介绍UNIX
系统字符管理的基本方法。
9.9.1
数据结构
字符设备管理用到的数据结构主要有缓冲区结构、缓
冲队列的控制结构、字符设备开关表等。字符设备开
关表主要用来指明字符设备驱动程序入口地址。
与块设备相似，系统为字符设备的I/O
传输设置了字
符缓冲池。在UNIX System
tIeNUXmSys
Ⅴ中，字符缓冲池由150
个缓冲区cblock
组成，其中每个缓冲区可容纳64
个字
节。字符缓冲区由链指针，该缓冲区中第一个字符的
位置，该缓冲区中最后一个字符的位置以及字符区组
成，如图9.17
所示。
系统初启时，150
个缓冲区都链接在空闲缓冲区队列
cfreelist
上。与块设备的缓冲区管理时不同，系统分
配和释放空闲缓冲区都在队首进行。图9.18
是一个空
闲缓冲区队列的例子。
图9.17
字符缓冲区结构
分配给各种设备使用的字符缓冲区构成不同的I/O
缓
冲队列。每个I/O
缓冲队列由一个称为clist
的控制结
构作为队首。clist
包括I/O
缓冲队列中可用字符数，
队首字符缓冲区指针，队尾字符缓冲区指针三项。
I/O
缓冲队列的例子如图9.19
所示。
字符设备管理程序使用上述数据结构进行字符设备的
管理。
图9.18
空闲缓冲区队列
图9.19 I/O
字符缓冲队列的例
9.9.2
对字符缓冲区队列的操作
对字符缓冲区的操作分为对空闲缓冲队列的操作，对
I/O
缓冲队列的操作。这些操作共有6
种，即:
(1)
从空闲缓冲队列分配一个缓冲区给驱动程序。
(2)
把一个缓冲区释放后放入空闲缓冲队列。
(3)
从I/O
缓冲队列中提取一个字符，并调整该I/O
缓
冲队列的字符计数。
(4)
把一个字符放入I/O
缓冲队列中的最后一个缓冲区
的末尾。
(5)
从I/O
缓冲队列中每次移走一个缓冲区中的所有字
符或n(n>1)
1n)(>
个字符。
(6)
往I/O
缓冲队列中每次送一个缓冲区的字符或
n(n>1)
1n)(>
个字符。
这些操作由8
个过程完成。即:
getcf
ftcge
，putcf
fcput
，getc
tcge
，
putc
cput
，getcb
，putcb
cbput
，getcbp
和putcbp
。其中，getcf
ftcge
用来申请一空缓冲区;
putcf
fcput
用来释放一个空缓冲区。
在释放空缓冲区时，如果有进程因等待空缓冲而睡眠
的话，则唤醒该进程。getc
tcge
从I/O
缓冲队列中的第一
个缓冲区中移走第一个字符，putc
cput
则把单个字符送到
字符队列的末尾。getcb
和putcb
cbput
分别取出I/O
缓冲队
列中的头一个字符缓冲区和往I/O
缓冲队列的末尾链
入一个装有字符的缓冲区。getcbp
和putcbp
则分别从
I/O
缓冲队列的头部取出n
个字符以及往I/O
缓冲队列
的末尾写入n
个字符。图9.20
和图9.21
分别给出了从
I/O
缓冲队列中取走n
个字符前和后的例子。
图9.20
取n
个字符前的I/O
缓冲队列
图9.21
取n
个字符后的I/O
缓冲队列
9.9.3
终端驱动程序
1.
行规则程序
字符设备类型不同，其设备驱动程序也不同。这里以
终端驱动程序为例来描述字符设备驱动过程的基本原
理。
终端驱动程序控制终端和进程之间的字符数据流动。
为了使用户交互式的使用UNIX
系统，终端驱动程序
包含一个与行规则程序的内部接口。行规则程序对输
入输出数据提供格式变换功能。行规则程序有两种工
作方式，即标准方式和原始方式。在标准方式下，行
规则程序把在键盘上敲入的原始数据序列变换成系统
可以识别的标准形式。同样，它把进程输出的原始数
据变换成用户所期望的格式。在原始方式下，行规则
程序不做任何格式变换。
行规则程序的功能是:
(1)
通过分析将输入字符串变成行。
(2)
处理删除键，以便用户能够从逻辑上部分地删除
敲入的字符序列。
(3)
处理删除行的字符，从而使得在当前行上敲入的
所有字符无效。
(4)
处理输出字符格式，例如把表格和空格符号变为
空格字符序列。
(5)
把输入的字符回送到显示屏上。
(6)
为终端挂起，断线或响应用户敲入的delete
ltede
键向进
程发软中断信号。
(7)
允许不做格式变换的原始方式。
行规则程序把数据按行(
直到一个回车符为止)
缓冲起
来，并按标准方式或原始方式传输数据。
2.
标准方式下的终端驱动程序
与终端驱动程序对应的I/O
缓冲队列有三个：一个用
来存放输出数据；一个用来存放原始输入数据，这是
由终端中断处理程序放入的；一个用来存放已加工的
输入数据，这是经过行加工程序处理过的输入数据。
标准方式下的终端驱动程序分为读/
写部分和输入/
输
出处理部分。与之相对应，字符设备开关表中所确定
的过程分别为ttwrite
，ttread
，ttopen
tonpe
，ttclose
ltceos
和
ttioctl
iltoc
。
当进程向一个终端写数据时，由字符设备开关表调用
ttwrite
过程，从而由ttwrite
过程调用行规则程序来完
成写操作。首先，行规则程序从用户地址空间把欲输
出的数据放入输出缓冲队列，并对其进行加工处理。
当输出缓冲队列中的字符数大于某个上限，例如100
时，则启动外设并将数据送到终端，并使写进程睡眠。
当输出缓冲队列中的字符数小于某个下限，例如0
时，则唤醒有关睡眠进程继续写操作。过程ttwrite
可
描述如下:
ttwrite
:
begin
repeat
把用户空间数据复制到输出缓冲队列
行规则处理
if
输出缓冲队列中的字符长度大于上限值
then
启动外设和控制器输出数据
fi
until
待写数据全部输出完毕
end
在标准方式下从终端读数据是一个较复杂的操作。它
把原始输入缓冲队列加工成标准输入缓冲队列之后再
送到用户区。一般来说，进程想要读的字节数是系统
调用read
规定的，不过，行规则程序在收到回车符之
后就结束继续读的字符。这是因为行规则程序无法知
道用户准备敲入多少个字符。
对于终端读过程ttread
来说，如果当前在任一原始输
入缓冲队列中都没有数据，则读进程睡眠。当数据被
输入时，终端中断处理程序把数据放入原始输入缓冲
队列的同时，把数据放入输出缓冲队列以便回波到显
示器。当输入字符串中含有一个回车符时，中断处理
程序唤醒所有睡眠的读进程。当一个读进程执行时，
ttread
调用行规则程序从原始输入缓冲队列中移出字
符，并进行加工后将其放入标准输入缓冲队列。同
时，也将输出缓冲队列中的字符回波到显示器上。然
后，它把字符复制到用户地址空间，直到收到了回车
符或达到了系统调用read
中所给定的计数值。ttread
过程可描述如下:
ttread
:
begin
repeat
if
标准输入缓冲队列中有字符且欲读字节数未满足
then
把标准输入缓冲队列中字符复制到用户区
else if
标准输入缓冲队列中无字符
then
while
原始输入缓冲队列无字符
do
等待数据输入和回车符
od
repeat
调用行规则程序将原始输入缓冲队列中
字符处理加工后移至标准输入缓冲队列与输出缓冲队列
until
处理到回车符
fi
fi
until
收到回车符或达到了指定的计数值
end
驱动程序ttopen
tonpe
用来打开终端机并建立终端机与终端
进程之间的对应关系。而ttclose
ltceos
则关闭终端机。另
外，ioctl
iltoc
则用来控制缓冲区的分配与释放以及调整输
入缓冲队列等。
本
章
小
结
本章介绍了UNIX
中三个紧密联系又相互独立的部
分，文件系统、中断和陷阱总控以及设备管理。
首先，从文件的组织结构出发，介绍了设备在UNIX
系统中作为特殊文件存在的特点。然后介绍了UNIX
System
Ⅴ的磁盘块分配与回收算法、存放文件说明
信息的i
节点的分配与释放算法。再者介绍了用户进
程怎样通过用户打开文件表和系统打开文件表与文件
系统联接起来，从而对文件系统进行存取操作。在对
文件进行操作时，系统必须通过给定的路径名搜索到
所要操作文件所对应的内存i
节点，还介绍了该搜索
算法namei
ienam
。文件系统与用户的接口是系统调用。用
户可以利用各种系统调用来使用文件系统所提供的各
种功能。
系统调用必须通过陷阱指令启动中断和陷阱总控程序
之后，才能在处理机将执行模式变为系统态之后调用
文件系统低层算法进行相应的操作。中断处理和陷阱
处理有相同也有不同。本章解释了它们之间的区别。
最主要的区别是，中断是由与当前执行进程无关的事
件引起的，因而在系统中断栈上执行；而陷阱是由与
当前进程有关的事件引起的，因而在当前进程的核心
栈上执行。
系统中有一个称为陷阱和中断向量表的系统控制块
SCB
SBC
，其中存放有各种中断和陷阱的中断和陷阱向量。
由这些向量，系统找到对应的处理程序的入口地址。
UNIX System
Ⅴ的中断处理过程比陷阱处理简单，
它们没有公共的入口处理程序，而陷阱处理时则由公
共陷阱入口处理程序调用相应的处理程序。UNIX
System
Ⅴ可处理包括系统调用在内的12
种陷阱情况。
在介绍了文件系统和中断与陷阱总控过程之后，又介
绍了缓冲池的管理算法。对应于块设备和字符设备，
UNIX System
Ⅴ设置有不同的缓冲区以匹配传输速
度或减少I/O
设备的启动次数。块设备的缓冲区和字
符设备的缓冲区都具有不同的缓冲控制块和组成不同
的缓冲队列。另外，文件系统在存取一个逻辑块时，
对缓冲队列采用散列搜索法以提高搜索速度。
块缓冲区和磁盘块之间的数据传输有一般读、异步读、
一般写、异步写和延迟写等几种，它们各有特点。
块设备的驱动程序把一个逻辑设备上的块号变换成物
理设备上的特定块号，并启动物理设备和控制器进行
I/O
传输。在I/O
传输结束后接收控制器发来的中断信
号和进行中断处理。在UNIX
系统中，每一类设备都
有自己的驱动程序。设备驱动程序主要包括打开、关
闭、读、写和缓冲区的策略接口等几种。这些程序的
入口地址都放置在设备开关表中。
每一个设备都有自己的设备文件名。一个设备特殊文
件的生成只能依靠系统管理进行系统配置之后利用的
命令生成。
字符设备的驱动程序没有块号转换的任务，但与块设
备时相似，字符设备的驱动程序也必须把逻辑设备号
转换成实际的物理设备，并启动这些设备和控制器进
行I/O
传输。字符设备和驱动程序主要包括打开、关
闭、读、写和控制等几种。这些程序的入口地址放置
在字符设备开关表中。
与块设备管理不同的是，字符设备管理中有一个行规
则管理程序。该程序进行输入/
输出数据的格式变换
和处理。