优秀课件笔记之文件系统

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

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

§7.1 文件系统的概念
§7.2 文件的逻辑结构与存取方法
§7.3 文件的物理结构与存储设备
§7.4 文件存储空间管理
§7.5 文件目录管理
§7.6 文件存取控制
§7.7 文件的使用
§7.8 文件系统的层次模型
本章小结

对大多数用户来说，文件系统是操作系统中最直
接可见的部分。计算机的重要作用之一就是能快速处
理大量信息，从而，信息的组织、存取和保管就成为
一个极为重要的内容。
文件系统是计算机组织、存取
和保存信息的重要手段
。本章主要讨论文件的组织结
构、存取结构、保护以及文件系统空间管理等问题。
3
§
7.1
文件系统的概念
1.
文件系统的引入
操作系统对计算机的管理包括两个方面：硬件
资源的管理和软件资源的管理。
硬件资源的管理包
括
CPU
的管理、存储器的管理、设备管理等，主要
解决硬件资源的有效和合理利用问题。软件资源的
管理则包括对各种系统程序（包括操作系统本身的
程序）、系统应用程序或工具（例如编辑程序、编
译程序等）、库函数及各种用户程序和数据的管理。
图
7.1
给出了资源管理的分类图。
4
图
7.1
操作系统的软硬件管理
显然，用户使用计算机来完成自己的某件任务
时，要碰到下列问题：
5
(1)
使用现有的软件资源来协助完成自己的任务
。
例
如，
编辑、
编译及链接程序来生成目标代码；
利
用系统调用库函数与实用程序来减少编程工作
,
避
开与硬件有关的部分等。
(2)
编制完成的或未完成的程序存放在什么地方
,
需要
访问的数据存放在什么地方，从而使得人们可以再
利用已有的软件资源。
事实上，这两个问题是一个怎样
对软件资源
（程序和数据）进行透明存放，并能令这些程序和
数据做到召之即来的问题。
在早期的计算机系统
中，由于硬件资源的限制，只能用卡片或纸带来存
放程序或数据。这些卡片和纸带都分别编号存放，
当用户需要使用它们时，再把这些卡片和纸带放在
读卡机上输入计算机。
6
显然，这些人工干预的控制和保存软件资源的方
法不可能做到透明存取，极大地限制了计算机的处理
能力和
CPU
等计算机硬件的利用率。
大容量直接存取的
磁盘存储器
以及顺序存取的
磁
带存储器
等的出现，为程序和数据等软件资源的透明
存取提供了物质基础。这导致了对软件资源管理质的
飞跃
——
文件系统的出现。
文件系统把相应的程序和
数据看作文件，并把它们存放在磁盘或磁带等大容量
存储介质上，从而做到对程序和数据的透明存取。
这
里，
透明存取是指不必了解文件存放的物理结构和查
找方法等与存取介质有关的部分，只需给定一个代表
某段程序或数据的文件名，文件系统就会自动地完成
对与给定文件名相对应文件的有关操作。
7
文件系统必须完成下列工作：
(1)
为了合理的存放文件，必需
对磁盘等辅助存储器
空间
(
或称文件空间
)
进行统一管理。
在用户创建
新文件时为其分配空闲区，而在用户删除或修改某
个文件时
,
回收和调整存储区。
(2)
为了
实现按名存取
，需要有一个用户可见的文件
逻辑结构，用户按照
文件逻辑结构
所给定的方式进
行信息的存取和加工。这种逻辑结构是独立于物理
存储设备的。
(3)
为了便于存放和加工信息，
文件在存储设备上应
按一定的顺序存放。
这种存放方式被称为
文件的物
理结构。
(4)
完成对存放在存储设备上的文件信息的查找
。
(5)
完成文件的共享和提供保护功能。
8
2.
文件与文件系统的概念
(1)
文件
上面已说过，
文件是一段程序或数据的集合
。这
是一种较为模糊的说法。
在计算机系统中，文件被解
释为一组赋名的相关联字符流的集合，或者是相关联
记录
(
一个有意义的信息单位
)
的集合。
文件的两种解释定义了两种文件形式。
赋名的字
符流文件是一种
无结构文件或流式文件
。
目前常用的
操作系统，例如
UNIX
操作系统，
MS-DOS
SDOM-
等均采用
无结构文件形式。
无结构文件由于采用字符流方式，
与源程序、目标代码等在形式上是一致的，因此，该
方式适用于源程序、目标代码等文件。由相关联记录
组成的文件中的有些基本信息单位是记录。
记录是由
N (N >1)
个字节组成的具有特定意义的信息单位
。
记
录式文件主要用于信息管理。
9
在有些操作系统中，从字符流文件的角度出发，设
备也被看作是赋予特殊文件名的文件。从而，系统可以
对设备和文件实施统一管理，以致大大简化设备管理程
序和文件系统的接口设计。
用户文件名由用户给定，它是一个
字母数字串
，有
些系统规定必须是英文字母打头且允许一些其他的符号
出现在文件名的非打头部分。例如
a.out
，
ccdos.exe
均为
合法文件名。
(2)
文件系统
操作系统中与管理文件有关的
软件和数据
称为
文件系
统
。它负责为用户建立文件，撤消、读写、修改和复制
文件，还负责完成对文件的按名存取和进行存取控制。
文件系统具有以下特点：
10
文件系统具有以下特点：
①
友好的用户接口
，用户只对文件进行操作，而不
管文件结构和存放的物理位置。
②
对文件
按名存取
，对用户透明。
③
某些文件可以被多个用户或进程所
共享
。
④
文件系统大都使用磁盘、磁带和光盘等大容量存储
器作为存储介质，因此，
可存储大量信息
。
3.
文件的分类
在文件系统中，为了有效、方便地管理文件，常
常把文件按其性质和用途等进行分类。
按文件的性质和用途可以分为三类：
11
按文件的性质和用途可以分为三类：
(1)
系统文件
该类文件
只允许用户通过系统调用来执行它们，而不允
许对其进行读写和修改。
这些文件主要由操作系统核
心和各种系统应用程序和数据所组成。
(2)
库文件
该类文件
允许用户对其进行读取、执行，
但不允许对
其进行修改。
库文件主要由各种标准子程序库组成。如
C
语言子程序库、
FORTRAN
子程序库等。
(3)
用户文件
用户文件
是用户委托文件系统保存的文件
。这类文件只
由文件的所有者或所有者授权的用户才能使用。用户文
件主要由源程序、目标程序、用户数据库等组成。
12
另外，
按组织形式，文件又可被画分为以下三类：
(1)
普通文件
普通文件既包括系统文件，也包括用户文件和库
函数文件、实用程序文件。
普通文件主要是指组织格
式为系统中所规定的最一般格式的文件
，例如由字符
流组成的文件。
(2)
目录文件
目录文件是
由文件的目录信息构成的特殊文件
。
即
该文件的内容不是各种程序或应用数据，而是用来
检索普通文件的目录信息。
(3)
特殊文件
在
UNIX
系统中，所有的输入、输出设备都被看
作特殊文件。
这组特殊文件在使用形式上与普通文件
相同，如查找目录、存取操作等。
13
除了按文件的用途和组织形式来分类外，还可以按
文件中的
信息流向
或
文件的保护级别
等分类。例
如，按信息流向可把文件分为：
输入文件、输出文
件、以及输入
/
输出文件等。
按文件的保护级别又
可分为：
只读文件、读写文件、可执行文件和不保
护文件等。
文件的分类主要是便于系统对不同的文件进行不同
的管理，从而提高处理速度和起到保护与共享的作
用。
例如，一个系统文件在读入内存时将被放在内
存的某一固定区且享受高的保护级别，从而不必像
一般的用户文件那样只有在内存用户可用区分得相
应的空闲区之后才能被调入内存。
14
§
7.2
文件的逻辑结构与存取方法
7.2.1
逻辑结构
文件的逻辑结构是用户可见结构
。
文件的逻辑结构
可分为两大类：字符流式的无结构文件
和
记录式的有
结构文件。
在文件系统设计时，选择何种逻辑结构才
能更有利于用户对文件信息的操作呢？
一般情况下，
选取文件的逻辑结构应遵循下述原则：
(1)
当用户对文件信息进行修改操作时，给定的逻辑
结构应能
尽量减少对已存储好的文件信息的变动
。
(2)
当用户需要对文件信息进行操作时，给定的逻辑
结构应使文件系统在
尽可能短的时间内查找到需要查
找的记录或基本信息单位。
(3)
应使文件信息占据最小的存储空间
。
(4)
应是便于用户进行操作的
。
15
显然，对于字符流的无结构文件来说，查找文件
中的基本信息单位，例如某个单词，是比较困难的。
但反过来，字符流的无结构文件管理简单，用户可以
方便地对其进行操作。所以，那些对基本信息单位操
作不多的文件较适于采用字符流的无结构方式，例
如，源程序文件、目标代码文件等。
除了字符流的无结构方式外，记录式的有结构文
件可把文件中的记录按各种不同的方式排列，构成不
同的逻辑结构，以便用户对文件中的记录进行修改、
追加、查找和管理等操作。
记录是一个具有特定意义的信息单位，它由该记
录在文件中的逻辑地址
(
相对位置
)
与记录名所对应的
一组键、属性及其属性值所组成。
图
7.2
是一个记录的
组成例。
16
图
7.2
记录组成例
17
图中，
1296
是名为
R
的记录在文件中的逻辑地
址，
‘
姓名
: A
’
是该记录的键，而
‘
性别
’
，
‘
出生年
月
’
，
‘
工资
’
等是该记录的属性，紧跟在这些后面的是
属性值。
一个记录可以有多个键名，每个键名可对应
于多项属性。
再者，根据各系统设计的要求不一样，
记录既可以是定长的，也可以是变长的
。
记录的长度
可以短到一个字符，也可以长到一个文件，这要由系
统设计人员确定。
常用的记录式结构文件有以下几种
:
(1)
连续结构；
(2)
多重结构；
(3)
转置结构；
(4)
顺序结构。
下面分别介绍这几种结构。
18
(1)
连续结构
连续结构是一种把
记录按生成的先后顺序连续排
列的逻辑结构。
连续结构的特点是适用性强，可用于
所有文件
，且记录的排列顺序与记录的内容无关。
这有利于记录的追加与变更。但是，连续结构文件的
搜索性能较差
，例如要找出某个指定键的记录时，系
统必须对文件全体进行搜索。
(2)
多重结构
如果
把记录按键和记录名排列成行列式结构
，则
一个包含
n
个记录名、
m
个
(m
≤
n)
个键的文件构成一
m
×
n
维行列式
(
如图
7.3)
。其中，如果第
i(1
≤
i
≤
m)
行和
第
j(1
≤
j
≤
n)
列所对应的位置上为
1
，则表示键
K
i
在记
录
R
j
中
;
反之，则表示键
K
i
不在记录
R
j
中。另外，
同
一个键也可以同时属于不同记录
。
19
图
7.3
文件的记录名和键构成的行列式
20
显然，如果只按行列式结构来排列记录，将会浪
费较多的存储空间。从而，我们把行列式中那些为零
的项去掉，并以键
K
i
为队首，以包含键
K
i
的记录为队
列元素来构成一个
记录队列
。对于一个有
m
个键的队
列来说，这样的队列有
m
个。这
m
个队列构成了该文
件的多重结构
(multi_list)
。
如图
7.4
所示。
(3)
转置结构
在图
7.4
的多重结构中，每个队列中和键直接相连
的只有一个记录。这种结构虽然在探索时要优于连续
结构，但在探索某一特定记录时，必须在找到该记录
所对应的键之后，再在该键所对应的队列中顺序查找。
与此相反，
转置结构把含有相同键的记录指针全部指
向该键，也就是说，把所有与同一键对应的记录的指
针连续地置于目录中该键的位置下
(
图
7.5)
。
转置结构
最适合于给定键后的记录搜索。
21
图
7.4
文件的多重结构
图
7.5
文件的转置结构
22
(4)
顺序结构
如果系统要求按某种优先顺序来搜索或追加、删
除记录，则最好采用顺序结构。如果给定了顺序规定
(
例如按字母顺序
)
，则
把文件中的键按规定的顺序排
列起来就形成了顺序结构文件。
例如，把人民日报上
登载的新闻按年月日为键做成记录放入文件中，并
以
时间先后顺序组成文件。
这样，如果要处理某段时间
内所发生的大事等问题，就会变得非常简单。例如用
户想了解两伊战争的情况，则只要把
1990
年
8
月
19
日
开始的两个月内的有关记录搜索到就行了。
23
7.2.2
存取方法
用户通过对文件的存取来完成对文件的修改、追
加和搜索等操作。
常用的存取方法有三种：
(1)
顺序存取法
(2)
随机存取法
(
直接存取法
)
(3)
按键存取法
顺序存取是按照文件的逻辑地址顺序存取
。在记
录式文件中，这反映为按记录的排列顺序来存取，例
如，若当前读取的记录为
R
i
，
则下一次读取的记录被
自动地确定为
R
i
的下一个相邻的记录
R
i+1
。
在无结构
的字符流文件中，顺序存取反映当前读写指针的变化。
在存取完一段信息之后，读写指针自动加或减去该段
信息长度，以便指出下次存取时的位置。
24
随机存取法允许用户根据记录的编号来存取文件
的任一记录，或者是根据存取命令把读写指针移到欲
读写处来读写。
UNIX
系统以及
MS-DOS
SDOM-
等操作系统
都采用顺序存取和随机存取等两种方法。
按键存取
是一种用在复杂文件系统，特别是数据
库管理系统中的存取方法。
文件的存取是根据给定的
键或记录名进行的。按键存取法首先搜索到要进行存
取的记录的
逻辑位置
，再将其转换到相应的
物理地址
后进行存取。
下面，介绍
按键存取的搜索方法
。
对文件进行搜索的目的是要查找出特定记录所对
应的逻辑地址，以便将其转换为相应的物理地址，实
现对文件的操作。
25
对文件的搜索包括两种：
键的搜索和记录的搜索
。
对
键的搜索是在用户给定所要搜索的键名和记录之后，
确定该键名在文件中的位置；而记录的搜索则是在搜索
到所要查找的键之后，在含有该键的所有记录中查找出
所需要的记录。
显然，对于不同的逻辑结构的文件，其
搜索方法和搜索效率都是不一样的。对指定记录
R
i
的搜
索过程如图
7.6
所示。
对于给定的
R
i
，首先，系统确定
R
i
所对应键名的记
录队列。如果在所查找的文件中不存在这样的队列，则
搜索算法结束返回，从而无法搜索到
R
i
。
如果找到
R
i
，
则返回其所对应的逻辑地址。如果找不到
R
i
，
则返回无
法找到
R
i
的有关信息。
26
图
7.6
记录
R
i
的搜索过程
27
对键或记录的搜索与其他数据搜索问题一样，都
属于
表格搜索
问题
。
有许多
搜索算法
用来解决表格搜
索问题。这些算法可以大致分为三种类型。即
(1)
线性
搜索法
(linear search)
，
(2)
散列法
(hash coding)
，
(3)
二
分搜索法
(binary search algorithm)
。
下面分别简单地
介绍这几种搜索算法。
(1)
线性搜索法
它
从第一个键或记录开始，依次和所要搜索的键
或记录相比较，直到找到所需要的记录为止。
线性搜
索法所需要的搜索时间与所搜索的表格大小的
1/2
成正
比。这是因为找到一个所需要的记录平均要和表中登
记的总项数的
1/2
项比较后才能得到。
线性搜索法的搜
索效率较低，在文件中记录个数较多时不宜采用
。
28
(2)
散列法
散列搜索法被被广泛用于现代操作系统的数据查
找。
散列法的核心思想是定义一个散列函数
h(k)
，
使
得对于给定的键
k
，
散列函数
h(k)
将其变换为
k
所对应
的逻辑地址。
在使用散列函数进行搜索时，
有时会出现两个不
同的输入值变换到同一地址的问题。
即对于
k
1
!=k
2
，
有
h(k
1
)=h(k
hk=(
2
)=A
。
显然，
k
1
和
k
2
中，至少有一个与
A
中的内容不一致。也就是说，
由散列变换得到的结果
并不是所要搜索的键。这种问题称为
散列冲突
。
解决
散列冲突的方法是采用
多次散列探索
。
例如，设
第
i
次散列变换的结果为
h
i
(k)
，
i=2,3
…
，
则可令
h
i
(k
) =(h
h=
1
(k) +
d
i
)(mod
t)
29
这里，
t
为被搜索表格长度，
d
i
为第
i
次搜索所得
地址与第
1
次搜索所得地址之间的距离。
d
i
的取值方法
很多，最简单的方法是设
d
i
为
i
的线性函数，即
d
i
=a
*
i
(a
为一大于零的常数
)
。这种方法称
线性散列法
。但
是，
使用线性散列法并不能完全解决散列冲突问题。
例如，对于
i!=j
，
k=1,2
…
，
如果
h
i
(k
1
)=h
j
(k
2
)
，则存在
h
i+k
(k
1
)=h
j+k
(k
2
)
。
解决散列冲突的另一个方法是
生成一组随机数
{r
1
,r
2
，
…
，
r
n
}
，
且令
d
i
=
r
i
。
显然，除了
h
1
(k
1
)=h
1
(k
2
)
可能存在之外，
h
1
(k
1
)=h
1+k
(k
2
)
的可能性很小，不过，
使用随机数的方法需要占用一定的存储空间来生成和
存放随机数组。
30
还有一个解决散列冲突的方法是采用
平方散列函数方
法
。即令：
h
i
(k) =(h
hk=)
1
(k)+c
ck+)
*
(i
*
i))(mod t)
这里，
t
是一个表示被搜索表格长度的素数，
c
是一个大于零的常数。可以证明，对于
j>1(mod t)
，
即使有
h
1
(k
1
)=h
j
(k
2
)
，
那么，对于
i=1,2
，
…
，
t-1
，
有
h
i
(k
1
)!=h
j+i
(k
2
)
。
(3)
二分搜索法
对于顺序结构排列的键或记录来说，二分搜索法
具有较高的搜索效率。设键
K
0
,K
1
,K
2
，
…
，
K
n
(n
>1)
按
键间距
d
排列，如果
K
0
的逻辑位置为
a
0
，
则有
K
i
的逻
辑位置为
a
0
+i
*
d
。
31
二分搜索法
首先把所要搜的键与队列的首尾键相
比较，如果和其中之一相等，则返回所搜索到的键的
逻辑位置。否则，再与队列
1/2
处的键比较，如果所
要搜索的键正好等于该键的话，则返回该键的逻辑地
址；否则，如果所要搜索的键
K
小于位于队列中央的
键的话，则继续搜索左边的半个队列。如果所要搜索
的键
K
大于位于队列中央的键的话，则继续搜索右边
的半个队列。这样，每次用以中央键画分的部分组成
新的队列反复进行上述搜索操作，直到找到为止。
这
一搜索过程如图
7.7
所示。
二分搜索法的好处是搜索效率高
。与线性搜索法
相比，当
n(
表长
)=16
时，它比线性搜索法约快二倍
;
当
n=1024
时，其平均搜索速度要快
50
倍。不过，
二
分搜索法需要事先把搜索对象按一定顺序排列。
32
图
7.7
二分搜索法的搜索过程
33
§
7.3
文件的物理结构与存储设备
文件系统采用哪种
存取方法和逻辑结构
，
实际上是和
物理存储介质
有关的。因此，本节
介绍文件的物理结构，同时也介绍常用的文件
存储设备。
34
7.3.1
文件的物理结构
在文件系统中，文件的存储设备通常画分为若干
个大小相等的物理块，每块长为
512
或
1024
字节。与
此相对应，为了有效地利用存储设备和便于系统管理
,
一般把文件信息也画分为与物理存储设备的物理块大
小相等的
逻辑块
。
从而，
以块作为分配和传送信息的
基本单位。
显然，对于字符流的无结构文件来说，每
一个物理块中存放长度相等的文件信息
(
存储文件尾
部信息的物理块除外
)
。但是，对于记录式文件来
说，由于记录长度既可以是固定的，也可以是可变
的，而且其长度不一定刚好等于其物理块的长度，从
而给由记录的逻辑地址到物理地址的变换带来了额外
的负担。
35
这里，为了简单起见，假设文件系统中每个记录
的长度是固定的，且其长度正好等于物理块的长度。
从而，对于记录式文件来说，利用上节讨论的搜索算
法得到的
逻辑地址正好与文件的逻辑块号一一对应
，
这就简化了所讨论问题的条件。
文件的物理结构是指文件在存储设备上的存放方
法。
事实上，由于文件的物理结构决定了文件信息在
存储设备上的存储位置，因此，
文件信息的逻辑块号
(
逻辑地址
)
到物理块号
(
物理地址
)
的变换也是由文件
的物理结构决定的。
常用的文件物理结构如下：
36
常用的文件物理结构如下：
(1)
连续文件
连续文件是一种最简单的物理文件结构，它
把一
个在逻辑上连续的文件信息依次存放到物理块中
。在
图
7.8
中，一个逻辑块号为
0,1,2,3
的文件依次存放在物
理块
10,11,12,13
中。
连续文件结构的优点是一旦知道
了文件在文件存储设备上的起址和文件长度，就能很
快地进行存取。
这是因为文件的逻辑块号到物理块号
的变换可以非常简单地完成。但是
连续文件结构在建
立文件时必须在文件说明信息中确定文件信息长度，
且以后不能动态增长。而且在文件进行某些部分的删
除后，又会留下无法使用的零头空间。
因此，
连续文
件结构不宜用来存放用户文件、数据库文件等经常被
修改的文件。
37
图
7.8
连续文件结构
38
(2)
串联文件
克服连续文件的缺点的办法之一是采用串联文件
结构。
串联文件结构用非连续的物理块来存放文件信
息。
这些非连续的物理块之间没有顺序关系，其中每
个物理块设有一个指针，指向其后续连接的另一个物
理块，从而使得
存放同一文件的物理块链接成一个串
联队列
。图
7.9
给出了串联文件的物理结构。
显然，使用串联文件结构时，不必在文件说明信
息中指明文件的长度，只需指明该文件的第一个块号
就行了。
串联文件结构的另一个特点是文件长度可以
动态地增长，只要调整连接指针就可在任何一个信息
块之间插入或删除一个信息块。
39
图
7.9
串联文件的物理结构
40
用串联文件结构时，逻辑块到物理块的转换由系
统沿串联队列查找与逻辑块号对应的物理块号的办法
完成。例如，在图
7.9
的文件结构中，如果用户所要进
行操作的逻辑块号为
2
，则系统从第一个物理块
20
开
始，一直沿串联队列搜索到队列中逻辑块号为
2
的第
三块时，得到其所对应的物理块号为
22
。
由于串联文件结构只能按队列中的串联指针顺序
搜索，因此，
串联文件结构的搜索效率较低
。
串连文
件结构一般只适用于逻辑上连续的文件，且存取方法
应该是顺序存取的。否则，为了读取某个信息块而造
成的磁头大幅度移动将花去较多的时间。
因此，
串联
文件结构不适宜随机存取。
41
(3)
索引文件
第三种文件物理结构是索引结构。
索引结构要求系
统为每个文件建立一张索引表，表中每一栏目指出文件
信息所在的逻辑块号和与之对应的物理块号。
索引表的
物理地址则由文件说明信息项给出。
索引结构如图
7.10
所示。
索引文件结构既可以满足文件动态增长的要求，又
可以较为方便和迅速地实现随机存取。
因为有关逻辑块
号和物理块号的信息全部放在一个集中的索引表中，而
不是像串联文件结构那样分散在各个物理块中。
42
图
7.10
索引文件示意图
43
在很多情况下，有的文件很大，文件索引表也就
较大。如果索引表的大小超过了一个物理块，那么我
们必须象处理其他文件的存放那样决定索引表的物理
存放方式，但这不利于索引表的动态增加；索引表也
可按串联方式存放，但这却增加了存放索引表的时间
开销。一种较好的解决办法是
采用间接索引
(
多重索
引
)
，也就是在索引表所指的物理块中存放的不是文
件信息，而是装有这些信息的物理块地址。
这样，如
果一个物理块可装下
n
个物理块地址的话，则经过一
级间接索引，可寻址的文件长度将变为
n
*
n
块。如果
文件长度还大于
n
*
n
块的话，还可以进行类似的扩
充，即二级间接索引。其原理如图
7.11
。
44
图
7.11
多重索引结构
45
不过，大多数文件不需要进行多重索引，也就是
说，这些文件所占用的物理块数的块号可以放在一个
物理块内。如果对这些文件也采用多重索引，则显然
会降低文件的存取速度。因此，
在实际系统中，总是
把索引表的头几项设计成直接寻址方式，也就是这几
项所指的物理块中存放的是文件信息；而索引表的后
几项设计成多重索引，也就是间接寻址方式。在文件
较短时，就可利用直接寻址方式找到物理块号而节省
存取时间。
46
索引结构既适用于顺序存取，也适用于随机存取。
索引结构的缺点是由于使用了索引表而增加了存储空
间的开销。
另外，
在存取文件时需要至少访问存储器
二次以上。其中，一次是访问索引表，另一次是根据
索引表提供的物理块号访问文件信息。由于文件在存
储设备的访问速度较慢，因此，如果把索引表放在存
储设备上，势必大大降低文件的存取速度。一种改进
的方法是，当对某个文件进行操作之前，系统预先把
索引表放入内存。这样，文件的存取就可直接在内存
通过索引表确定物理地址块号，而访问磁盘的动作只
需要一次。
47
7.3.2
文件存储设备
常用的存储设备有磁盘、光盘、磁带等。其中磁
盘又可分为硬盘和软盘。由于存储设备的特性决定了
文件的存取设备和方法，因此，这里介绍以磁带为代
表的顺序存储设备和以磁盘为代表的直接存储设备的
特性及有关存取方法。
1.
顺序存取设备
磁带是一种最典型的顺序存取设备
。顺序存取设
备
只有在前面的物理块被存取访问过之后，才能存取
后续的物理块的内容。
而且，为了在存取一个物理块
时让磁带机提前加速和不停止在下一个物理块的位置
上，磁带的两相邻的物理块之间设计有一个
间隙
将它
们隔开
(
图
7.12)
。
48
图
7.12
磁带的结构
磁带设备的存取速度或数据传输率与下列因素有关
：
(1)
信息密度
(
字符数
/
英寸
)
(2)
磁带带速
(
英寸
/
秒
)
(3)
块间间隙
如果带速高，信息密度大，且所需块间隙
(
磁头
启动和停止时间
)
小的话，则磁带存取速度和数据传
输率高，反之亦然。
49
另外，由磁带的读写方式可知，只有当第
i
块被
存取之后，才能对第
i+1
块进行存取操作。因此，
某
个特定记录或物理块的存取访问与该物理块到磁头当
前位置的距离有很大关系。
如果相距甚远，则要花费
很长的存取时间来移动磁头。因此，如果按随机方式
或按键存取方式存取磁带上的文件信息的话，其效率
不会很高。但是，磁带存取设备具有容量大，顺序存
取方式时存取速度高等优点。因此，磁带存取设备获
得了较为广泛的应用。
50
2.
直接存取设备
磁盘是最典型的直接存取设备
。磁盘设备
允许文
件系统直接存取磁盘上的任意物理块。
为了存取一个
特定的物理块，
磁头将直接移动到所要求的位置上
，
而不需要像顺序存取那样事先存取其他的物理块。
磁盘机一般由一些磁盘片组成的磁盘组组成
。其
中
每个磁盘片对应一个装有
读
/
写
磁头的磁头臂，磁
头臂上的两个读
/
写磁头分别对磁盘片的上下两面进
行读写。
系统在对磁盘进行初始化处理时，把每个磁
盘片分割成一些大小相等的扇区。在磁盘转动时经过
读
/
写磁头所形成的圆形轨迹称为磁道。
由于磁头臂
可沿半径方向移动，因此，磁盘上有多条磁道。
51
另外，人们通常
把所有磁盘片的相同磁道称为一
个柱面，
因此，
磁盘上每个物理块的位置可用
柱面号、
磁头号和扇区号
表示，这些地址和物理块号一一对应。
磁盘的结构如图
7.13
所示。
图
7.13
磁盘的结构
52
§
7.4
文件存储空间管理
存储空间管理是文件系统的重要任务之一。只有
有效地进行存储空间管理，才能保证多个用户共享文
件存储设备和得以实现文件的按名存取。
由于文件存
储设备是分成若干个大小相等的物理块，并以块为单
位来交换信息的，因此，文件存储空间的管理实质上
是一个空闲块的组织和管理问题，它包括空闲块的组
织，空闲块的分配与空闲块的回收等几个问题。
有下述
3
种不同的空闲块管理方法
。它们是：
(1)
空闲文件目录
(2)
空闲块链
(3)
位示图
53
(1)
空闲文件目录
最简单的空闲块管理方法就是
把文件存储设备中
的空闲块的块号统一放在一个称为空闲文件目录的物
理块中。
其中空闲文件目录的每个表项对应一个由多
个空闲块构成的空闲区，它包括空闲块个数，空闲块
号和第一个空闲块号等。
在系统为某个文件分配空闲块时，首先扫描空闲
文件目录项，如找到合适的空闲区项，则分配给申请
者，并把该项从空白文件目录中去调。如果一个空闲
区项不能满足申请者要求，则把目录中另一项分配给
申请者
(
连续文件结构除外
)
。如果一个空闲区项所含
块数超过申请者要求，则为申请者分配了所要的物理
块之后，再修改该表项。
54
当一个文件被删除，释放存储物理块时，系统则
把被释放的块号、长度以及第一块块号置入空白目录
文件的新表项中。
显然，在内存管理时讨论过有关空闲连续区分配
和释放算法。只要稍加修改就可用于空闲文件项的分
配和回收。
空闲文件项方法适用于
连续文件结构
的文件存储
区的分配与回收。
55
(2)
空闲块链
空闲块链是一种较常用的空闲块管理方法。空闲
块链
把文件存储设备上的所有空闲块链接在一起，当
申请者需要空闲块时，分配程序从链头开始摘取所需
要的空闲块，然后调整链首指针。反之，当回收空闲
块时，把释放的空闲块逐个插入链尾上。
空闲块链的链接方法因系统而异，
常用的链接方
法有
按空闲区大小顺序链接的方法
；
按释放先后顺序
链接的方法
；
以及按成组链接法
。其中成组链接法可
被看作空闲块链的链接法的扩展。
按空闲区大小顺序链接和按释放先后顺序链接的
空闲块管理在增加或移动空闲块时需对空闲块链做较
大的调整，因而需耗去一定的系统开销。
成组链法在
空闲块的分配和回收方面要优于上述两种链接法
。
56
成组链法首先把文件存储设备中的所有空闲块按
50
块
画分为一组
。组的画分为从后往前顺次画分
(
如
图
7.14)
。其中，
每组的第一块用来存放前一组中各块
的块号和总块数。由于第一组的前面已无其他组存
在，因此，第一组的块数为
49
块。
不过，
由于存储设
备的空间块不一定正好是
50
的整倍数，因而最后一组
将不足
50
块，且由于该组后面已无另外的空闲块组，
所以，该组的物理块号与总块数只能放在管理文件存
储设备用的
文件资源表
中。
57
图
7.14
成组链法的组织
在成组链法对文件设备进行了上述分组之后，系
统可根据申请者的要求进行空闲块的分配，并在释放
文件时回收空闲块。下面我们介绍
成组链法的分配和
释放过程。
58
首先，
系统在初启时把文件资源表复制到内存
，
从而使文件资源表中放有最后一组空闲块块号与总块
数的堆栈进入内存，并使得空闲块的分配与释放可在
内存进行。减少了启动
I/O
设备的压力。
与空闲块块号及总块数相对应，用于空闲块分配
与回收的堆栈有栈指针
P
tr
，
且
P
tr
的初值等于该组空
闲块的总块数。当申请者提出空闲块要求
n
时，按照
后进先出的原则，分配程序在取走
P
tr
所指的块号之
后，再做
P
tr
←
P
tr
-1
的操作。这个过程一直持续到所要
求的
n
块都已分配完毕或堆栈中只剩下最后一个空闲
块的块号。当堆栈中只剩下最后一个空闲块号时，系
统启动设备管理程序，将该块中存放的下一组的块号
与总块数读入内存之后将该块分配给申请者。然后，
系统重新设置
P
tr
指针，并继续为申请者进程分配空闲
块。
59
文件
存储设备的最后一个空闲块中设置有尾部标
识，以指示空闲块分配完毕。
如果用户进程不再使用有关文件并删除这些文件
时，回收程序回收装有这些文件的物理块。
成组链法
的回收过程仍利用文件管理堆栈进行回收。在回收
时，回收程序先做
P
tr
←
P
tr
+1
操作，然后把回收的物理
块号放入当前指针
P
tr
所指的位置。如果
P
tr
等于
50
，
则表示该组已经回收结束。此时，如果还有新的物理
块需要回收的话，回收该块并启动
I/O
设备管理程
序，把回收的
50
个块号与块数写入新回收的块中。然
后，将
P
tr
重新置
1
另起一个新组。
显然，
对空闲块的分配和释放必须互斥进行，否
则将会发生数据混乱。
60
(3)
位示图
空闲文件目录和空闲块链法在分配和回收空闲块
时，都需在文件存储设备上查找空闲文件目录项或链接
块号，这必须经过设备管理程序启动外设才能完成。
为
提高空闲块的分配回收速度，用位示图进行管理
。
系统首先从内存中画出若干个字节，为每个文件存
储设备建立一张位示图。
这张位示图反映每个文件存储
设备的使用情况。
在位示图中，每个文件存储设备的物
理块都对应一个比特位。如果该位为
“
0
”
，则表示所对应
的块是空闲块；反之，如果该位为
“
1
”
，则表示所对应的
块已被分配出去。
利用位示图来进行空闲块分配时，只需查找图中的
“
0
”
位，并将其置为
“
1
”
位。反之，利用位示图回收时只
需把相应的比特位由
“
1
”
改为
“
0
”
即
可。
61
§
7.5
文件目录管理
为了实现对文件的按名存取，首先，每个文件必须
有一个文件名与其对应。一般用户文件名由用户指
定，系统文件和特殊文件在系统设计时指定。
必须把文件名及其结构信息等按一定的组织结构排
列，以方便文件的搜索。把文件名和对该文件实施控
制管理的
控制管理信息
称为该文件的
文件说明
，并把
一个文件说明按一定的逻辑结构存放到物理存储块的
一个表目中。利用文件说明信息，可以完成对文件的
创建、检索以及维护作用。
因此，把
一个文件的文件
说明信息称为该文件的目录。对文件目录的管理就是
对文件说明信息的管理。
文件目录的管理要解决存储空间的有效利用，还要
解决快速搜索、文件命名冲突、以及文件共享问题
。
62
7.5.1
文件的组成
从文件管理角度看，
一个文件包括两部分：文件
说明和文件体。文件体指文件本身的信息
，它可能是
前面各节讨论的记录式文件或字符流式文件。
文件说
明有时也叫文件控制块
(FCB)
，
它至少包括
文件名
、
与
(
物理结构是连续结构时
)
文件名相对应的
文件内部
标识
以及文件信息在文件存储设备上
第一个物理块的
地址
（物理结构是边连续结构时）。
另外，根据系统
要求不同，它还包括关于文件逻辑结构、物理结构、
存取控制和管理信息等。这里的管理信息主要指访问
时间、以及记账信息等。
文件说明组成目录文件。文件系统利用目录文件
完成按名存取和对文件信息的共享与保护。
63
7.5.2
文件目录
文件目录可分为单级目录、二级目录和多级目录
。
单级目录是一种最简单、最原始的目录结构。如果
文件系统为存储设备的
所有文件建立一张目录表
，
每
个文件在其中占有一项用来存放文件说明信息。
该目
录表存放在存储设备的某固定区域，在系统初启时或
需要时，系统将其调入内存，
(
或部分调入内存
)
。文
件系统通过对该表提供的信息对文件进行创建、搜索、
删除等操作。
利用单级目录，文件系统就可实现对文件系统空
间的自动管理和按名存取。单级目录时的文件系统读
写处理过程如图
7.15
。
64
图
7.15
单级目录的读写处理过程
65
不过，由于在单级目录表中，各文件说明项都处
于平等地位，只能按连续结构或顺序结构存放。如果
两个不同的文件重名的话，则系统将把它们视为同一
文件。另外，由于单级目录必须对单级目录表中所有
文件信息项进行搜索，因而，
搜索效率也较低
。
为了改变单级目录中文件
命名冲突问题
和提高对
目录表的
搜索速度
，单级目录被扩充成二级目录。
二级目录结构中，各个文件的说明信息被组织成
目录文件，且以用户为单位把各自的文件说明画分为
不同的组。
然后，这些不同的组名有关存取控制信息
存放在
OK
主目录
(MFD)
的目录项中。与主目录
MFD
相对应，
用户文件的文件说明所组成的目录文件被称
为用户文件目录
(UFD)
。
这样，
由
MFD
和
UFD
就形成
二级目录。
二级目录的结构如图
7.16
。
66
图
7.16
二级目录结构
67
当用户要对一个文件进行存取操作或创建、删除
一个文件时，
首先从
MFD
找到对应的目录名，并从
用户名查找到该用户的
MFD
。
余下的操作与单级目
录时相同。
使用二级目录可以解决文件重名和文件共享问
题，并可获得较高的搜索速度
。由于二级目录时首先
从主目录
MFD
开始搜索，因此，从系统管理的角度
来看，
文件名已演变成为用户名
/
用户文件名
。从
而，即使两个不同的用户具有同名文件，系统也会把
它们区别开来。再者，利用二级目录，也
可以方便地
解决不同用户间的文件共享问题
，这只要
在被共享的
文件说明信息中增加相应的共享管理项和把共享文件
的文件说明项指向被共享文件的文件说明项即可
。
68
另外，与单级目录相比，如果单级目录表的长度
为
n
的话，则单级目录时的搜索时间与
n
成正比
;
在二
级目录时，由于ｎ的目录已被画分为ｍ个子集，则二
级目录的搜索时间是与ｍ＋ｒ成正比的。这里的ｍ是
用户个数，ｒ是每个用户的文件的个数。一般有ｍ＋
ｒ
≤
ｎ，从而
二级目录的搜索时间要快于单级目录
。
把二级目录的层次关系加以推广，就形成了多级
目录。
在多级目录结构中，除了最低一级的物理块中
装有文件信息外，其他每一级目录中存放的都是下一
级目录或文件的说明信息。由此形成层次关系，最高
层为根目录，最低层为文件。
多级目录构成
树形结
构
，如图
7.17
所示。
69
图
7.17
文件系统的树形结构
70
树形结构多级目录结构具有下列特点
：
(1)
层次清楚
。由于分支结构，不同性质、不同用户
的文件可以构成不同的子树，
便于管理
。不同层次、
不同用户的文件可以被赋予不同的存取权限，
有利于
文件的保护。
(2)
解决了文件重名问题
。文件在系统中的搜索路径
是从根开始到文件名为止的各文件名组成，因此，只
要在同一子目录下的文件名不发生重复，就不会由文
件重名而引起混乱。
(3)
查找搜索速度快
。在
7.2
节讨论的对文件中键名的
各种搜索方法
,
例如线性搜索法
,
散列法以及二分搜索
法都可用来对各级目录进行查找。
由于对多级目录的
查找每次只查找目录的一个子集，因此，其搜索速度
较单级、二级目录时更快。
71
7.5.3
便于共享的文件目录
文件系统的一个重要任务就是为用户提供共享文
件信息的手段。这是因为对于某一个公用文件来说，
如果每个用户都在文件系统内保留一份该文件的副
本，这将极大地浪费存储空间。如果系统提供了共享
文件信息的手段，则在文件存储设备上只需存储一个
文件副本，共享该文件的用户以自己的文件名去访问
该文件的副本就可以了。
从系统管理的观点看，有三种方法可以实现文件
共享。即：
(1)
绕道法
(2)
链接法
(3)
基本文件目录表
BFD
72
绕道法要求每个用户处在当前目录下工作，
用户
对所有文件的访问都是相对于当前目录进行的。
用户
文件的固有名
(
为了访问某个文件而必须访问的各个
目录和文件的目录名与文件名的顺序连接称为固有名
)
是由当前目录到信息文件通路上所有各级目录的目录
名加上该信息文件的符号名组成。
使用绕道法进行文
件共享时，用户从当前目录出发向上返回到与所要共
享文件所在路径的交叉点，再顺序下访到共享文件。
绕道法
需要用户指定所要共享文件的逻辑位置或到达
被共享文件的路径
。绕道法的原理如图
7.18
所示。
73
图
7.18
绕道法
74
绕道法要
绕弯路访问
多级目录，
搜索效率不高
。
为了提高共享其它目录中文件的速度，
另一种共享的
办法是在相应目录表之间进行链接。即将一个目录中
的链指针直接指向被共享文件所在的目录
。
链接法仍
然需要用户指定被共享的文件和被链接的目录
。
实现文件共享的一种有效方法是采用
基本文件目
录表
BFD
的方法
。
该方法把所有文件目录的内容分成
两部分：一部分包括文件的结构信息、物理块号、存
取控制和管理信息等，并由系统赋予唯一的内部标识
符来标识；另一部分则由用户给出的符号名和系统赋
给文件说明信息的内部标识符组成。
这两部分分别称
为
符号文件目录表
(SFD)
和
基本文件目录表
(BFD)
。
SFD
SDF
中存放文件名和文件内部标识符，
BFD
中存放除了
文件名之外的文件说明信息和文件的内部标识符。
这
样组成的多级目录结构如图
7.19
。
75
图
7.19
采用基本文件目录的多级目录结构
76
在图
7.19
中，为了简单起见，未在
BFD
表项中列
出结构信息、存取控制信息和管理控制信息等。另
外，在文件系统中，系统通常预先规定赋予基本文件
目录、空白文件目录、主目录
MFD
的符号文件目录
固定不变的唯一标识符，在图中它们分别为
0,1,2
。
采用基本文件目录方式可较方便地实现文件共享。
如果
用户要共享某个文件，则只需给出被共享的文件
名，系统就会自动在
SDF
SFD
的有关文件处生成与被共享
文件相同的内部标识符
id
，
例如在图
7.19
中，用户
Wang
和
Zhang
共享标识符为
6
的文件，对于系统来
说，标识符
6
指向同一个文件；而对
Wang
和
Zhang
两
用户来说
,
则对应于不同的文件名
b.c
和
f.c
。
77
7.5.4
目录管理
存放文件说明信息或目录管理说明信息的目录项
构成目录文件，这些文件同样存放在文件存储设备中。
在存取一个文件时，必须访问多级目录。如果访问每
级目录时都必须到文件存储设备上去搜索，浪费
CPU
处理时间、降低了处理速度，给输入输出设备增加了
负担。一种解决办法是
在系统初启时，把所有的目录
文件读入内存，由文件系统在内存完成对各级目录的
搜索。
这种方法需要大量的内存支持。显然是不可取
的。另一种
折中的方法
是：
把当前正在使用的那些文
件的目录表目复制到内存中。
为此，系统提供两种特
殊的操作把有关的目录文件复制到内存的指定区；以
及当用户不再访问有关信息文件时删去有关目录文件
的内存副本。
78
把文件存储设备上的目录文件复制到内存的操作称
为打开文件
(
fopen
fonpe
)
，
而把删除文件的内存副本的操作
称为关闭文件
(
fclose
lfceos
)
。
这两个操作一般以系统调用的
方式提供。
对于按
BDF
和
SDF
SFD
方式排列的多级文件目
录来说，系统按以下方式打开一个文件。
(1)
把主目录
MFD
中的相应表目，也就是
与待打开
文件相联系的有关表目复制到内存。
例如，若准备打
开图
7.19
中的文件
a.c
，
则将
MFD
中的第一项
(Wang)
复制到内存。
(2)
根据
(1)
所复制得到的标识符，再
复制此标识符
所指明的基本文件目录表
BDF
的有关表目
。例如图
7.19
中的
id=3
i3d=
的
BDF
中表目项。这个表目中包括有存
取控制信息、结构信息以及下级目录的物理块号等。
79
(3)
根据
(2)
所得到的子目录说明信息搜索
SFD
SDF
，
以找到与
待打开文件相对应的目录表项。如果找到的表目仍然是
子目录名，则系统将根据其对应的标识符
id
，
继续上述
复制过程，直到所找到的表目是待打开的文件名。例如
在图
7.19
中文件名
a.c
。
(4)
根据
(3)
所搜索到的文件名所对应的标识符
id
，
把相应
的
BDF
的表目项复制到内存。这样，
待打开文件的说明
信息就已复制到了内存中。由复制的文件说明，系统显
然可以方便地得到文件的有关物理块号。从而，系统可
对文件进行有关操作。
在完成了上述４个步骤之后，就说文件是被打开的
了。称这样的文件为
打开的文件或活动文件
。而且，
把
内存中存放活动文件的
SFD
SDF
表目的表称为活动名字表，
这个表每个用户一张。
另外，
把内存中存放活动文件的
BFD
表目的表称为活动文件表，这个表整个系统一张。
80
§
7.6
文件存取控制
本节介绍文件的存取控制问题。文件的存取控制
是和文件的共享、保护和保密三个不同而又相互联系
的问题紧密相关的。
文件的共享是指不同的用户共同使用一个文件
。
文件保护则指文件本身需要防止文件的拥有者本人
或其他用户破坏文件内容。
文件保密指未经文件拥有者许可，任何用户不得访
问该文件。
这三个问题实际上是一个用户对文件的
使用权限，
即读、写、执行的许可权问题
。
具体地说，文件系统的存取控制部分应做到：
81
具体地说，
文件系统的存取控制部分应做到
：
(1)
对于拥有读、写或执行权限的用户，
应让
其对文
件进行相应的操作。
(2)
对于没有读、写或执行权限的用户，
应禁止
他们
对文件进行相应的操作。
(3)
应防止一个
用户冒充
其他用户对文件进行存取。
(4)
应防止拥有存取权限的用户
误用文件
。
这些功能是由一组称为
存取控制验证模块
的程序
提供的。它们分
三步验证用户的存取操作
。
(1)
审定用户的存取权限。
(2)
比较用户权限的本次存取要求是否一致。
(3)
将存取要求和被访问文件的保密性比较，看是否
有冲突。
82
可有下述４个方式来验证用户的存取操作
,
它们是：
(1)
存取控制矩阵
;
(2)
存取控制表
;
(3)
口令
; (4)
密码术。
系统设计人员根据需要选择其中一种或几种并
将相应
的数据结构置于文件说明
(BFD
等
)
中，在用户访问存
取文件时，对用户的存取权限、存取要求的一致性以
及保密性等进行验证。
(1)
存取控制矩阵
存取控制矩阵方式
以一个二维矩阵来进行存取控
制。
二维矩阵的一维是所有的用户，另一维是所有的
文件。对应的矩阵元素则是用户对文件的存取控制
权，包括读Ｒ，写Ｗ，和执行Ｅ。如图
7.20
所示。
83
图
7.20
存取控制矩阵
84
当用户向文件系统提出存取要求时，由存取控制
验证模块根据该矩阵内容对本次存取要求进行比较，
如果不匹配的话，系统拒绝执行。
当文件和用户较多时，存取控制矩阵将变得非常
庞大，这无论是在占用内存空间的大小上，还是在为
使用文件而对矩阵进行扫描的时间开销上都是不合适
的。因此，在实现时往往采取某些辅助措施以减少时
间和空间的开销。
(2)
存取控制表
存取控制表
以文件为单位，把用户按某种关系画
分为若干组，同时规定每组的存取权限。
这样，所有
用户组对文件权限的集合就形成了该文件的存取控制
表，如图
7.21
所示。
85
图
7.21
存取控制表
每个文件都有一张存取控制表。在实现时，该表
存放在文件说明中，也就是
BFD
的有关表目中。文件
被打开时
,
由于存取控制表也相应地被复制到了内存活
动文件中
,
因此
,
存取控制验证能高效进行。
86
(3)
口令方式
口令方式有两种。
一种是
当用户进入系统，为建
立终端进程时
获得系统使用权的口令
。
另一种
口令方
式是，每个用户在创建文件时，
为每一个创建的文件
设置一个口令，且将其置于文件说明中
。显然，口令
只有设置者自己知道，若允许其他用户使用自己的文
件，口令设置者可将口令赋予其他用户。这样，既可
以做到文件共享，又可做到保密。而且，由于口令较
为简单，
占用的内存单元以及验证口令所费时间都将
非常少。
不过，相对来说，
口令方式保密性能较差
。
再者，当要修改某个用户的存取权限时，文件主必须
修改口令，这样，所有共享该文件的用户的存取权限
都被取消，除非文件主将新的口令通知用户
。
87
(4)
密码方式
防止文件泄密以及控制存取访问的的另一种方法是
密
码方式。
密码方式在用户创建源文件并将其写入存储
设备时对文件进行
编码加密
，在读出文件时对其进行
译码解密
。显然，只有能够进行译码解密的用户才能
读出被加密的文件信息，从而起到文件保密的作用。
文件的加密和解密都需要用户提供一个代码键
(KEY)
。
加密程序根据这一代码键对用户文件进行编
码变换，然后将其写入存储设备。在读取文件时，只
有用户给定的代码键与加密时的代码键相一致时，解
密程序才能对加密文件进行解密，将其还原为源文件。
加密处理过程如图
7.22
所示。
88
图
7.22
加密解密过程
• 加密方式具有
保密性强
的优点，因为与口令不同，
进行编码解码的
代码键
没有存放在系统中，而是由
用户自己掌握的。但是，由于编码解码工作要
耗费
大量的处理时间
，因此，
加密技术是以牺牲系统开
销为代价的。
89
§
7.7
文件的使用
本节讨论文件系统对用户的接口。
文件系统以
系统调用方式
或
命令方式
为用户提供
下列几类
服务
：
(1)
关于设置和修改用户对文件的存取权限的服务
;
(2)
关于建立、改变和删除目录的服务
;
(3)
关于文件共享、设置访问路径的服务
;
(4)
创建、打开、读写、关闭，及撤消文件的服务。
这些服务的调用名和参数都
因系统不同而异
。
有关对文件操作的命令都基于操作系统提供的系
统调用。这些系统调用包括建立文件用的
creat
，
读
文件用的
read
，
关闭文件用的
close
lceos
以及撤消文件用的
delete
等。
90
其中，
creat
调用将根据用户提供的文件名和属
性，在指定的文件存储设备上建立一个文件并把文件
标识符返回给用户。而
open
onpe
调用则把在文件存储设备
上的有关文件说明信息复制到内存的活动文件目录表
中
。
write
调用将把从内存中某个位置开始的一段ｎ
字节长
(
字符流文件时
)
信息或ｎ个记录经设备管理程
序写入文件存储设备
。
read
调用的功能与
write
相
反，它把指定文件的几个字节或记录读入内存中指定
地区。
若文件暂时不用时，
系统调用
close
lceos
关闭该文
件。
close
调用撤消活动文件表中相应表目
。
delete
ltede
调
用则在一个文件不再被访问时，删除该文件在文件存
储设备上的有关说明信息，并释放该文件所占据的全
部存储空间。
91
§
7.8
文件系统的层次模型
这一节将介绍文件系统的一般层次模型。
操作系统的层次结构的设计方法是
Dijkstra
ijtrakDs
于
1967
年提出的，
1968
年
Madnick
cakMdni
将这一思想引入了文件系统。
层次结构法的优点是，可以按照系统所提供的功能来
画分为各种不同的层次，下层为上层提供服务，上层
使用下层的功能。这样，上下层之间彼此无需了解对
方的内部结构和实现方法，而只关心二者的接口。
从
而，一个看上去十分复杂的系统将会由于层次的画分
而变得易于设计、易于理解和
易于实现
。而且，当系
统出现错误时，也
容易进行查错和调整
。因此，层次
化设计方法也使得系统的
管理和维护更加容易。
92
• 层次的画分是一个十分复杂的问题。如果层次画分
太少，分层的意义不明显。若层次画分太多，则各
层之间传递的参数会急剧增加，而且每一层的处理
会占去一定的系统开销，从而影响系统效率。因
此，
层次的画分要根据实际需要仔细地考虑
。
Madnick
cakMdni
把文件系统画分为
8
层
，如图
7.23
所示。
• 在图
7.23
中，
第
1
层是用户接口
，
该层根据用户对文
件的存取要求，把不同的系统调用加工改造成不同
的内部调用格式。
• 第
2
层符号文件系统层
。该层完成第
1
层所提供的功
能，并把第
1
层所提供的参数
——
用户文件名转换
成系统内部的唯一标识符
fd
，
该层的主要工作是搜
索文件目录，也就是搜索
SFD
SDF
，
以找到相应文件名
的表目以找到
fd
。
然后，
fd
将作为参数传给第
3
层。
93
图
7.23
文件系统的层次模型
94
• 第
3
层是基本文件系统层
。该层根据第
2
层的调用参
数
fd
，
找到文件的说明信息，包括存取控制表、文
件逻辑结构、物理结构以及第一个物理块地址等。
• 第
4
层是存取控制验证层
。该层的主要功能是根据
存取控制信息和用户访问要求，检验文件访问的合
法性，从而实现文件的共享、保护和保密。
• 第
5
层是逻辑文件系统层
。该层的主要功能是根据
文件的逻辑结构，找到所要进行操作的数据或记录
的相对块号。对于字符流的无结构文件来说，只要
把用户指定的逻辑地址按块长换算成相对块号就可
以了。但是，对于记录式有结构文件来说，由于用
户有时指定的是键名或记录名，因此，需首先由键
名
(
或记录名
)
搜索到相应的记录并得到对应的逻辑
地址之后，再将其转换为相对块号。
95
• 第
6
层是物理文件系统层
。该层把相对块号根据文
件的物理结构转换成物理地址。
• 第
7
层是文件存储设备分配模块和设备策略模块
。
文件存储设备分配模块实现对空闲存储块的管理，
包括分配、释放和组织。设备策略模块主要是把物
理块号转换成相应文件存储设备所要求的地址格
式，例如磁盘的柱面号、磁道号、盘区号等。然
后，根据具体的操作要求及必要的参数，准备启动
输入输出设备的命令。
第
8
层是启动输入输出层
。
由设备处理程序执行具体的读或写文件操作。
• 第
7
层和第
8
层是文件系统和设备管理程序的接口层。
96
本
章
小
结
• 文件系统为用户提供了按名存取的功能，以使得用
户能透明地存储访问文件。为了实现按名存取，文
件需要对文件存储设备进行合理的组织、分配和管
理；对存储在文件存储设备上的文件进行保护、保
密和提供共享的手段。另外，文件系统还要提供检
索文件或文件中记录的手段。
文件系统就是完成上
述功能的一组软件和数据结构的集合。
• 本章主要讨论了文件、文件系统的基本概念。
文件
是一组赋名的字符流的集合或一组相关联的记录的
集合。一个记录是有意义的信息的基本单位，它有
定长和变长两种基本格式。
本章在定长的假定下讨
论，但其结果也可以扩展到变长格式的情况。
97
• 文件按一定的逻辑结构组成逻辑文件，逻辑文件是用
户可见的抽象文件。
文件的逻辑结构可分为字符流式
无结构的连续文件、记录式有结构文件两大类。
其中
记录式文件又可分为连续结构、多重结构、转置结构
及顺序结构文件等。对于记录式文件来说，如果用户
在存取操作时指定的参数是键名或记录名的话
(
按键存
取
)
，有三种常用的方法可用来检索文件，它们是：线
性检索法、散列法和二分搜索法。
• 一个文件在存储设备上按一定的物理方式存放。文件
的物理结构受设备类型的影响
。例如，
磁带设备只适
合于连续存放和顺序存取，而磁盘设备既适合于连续
存放，也适合于串联存放和索引存放。磁盘设备上的
文件既可以是顺序存取的，也可以是直接存取或按键
存取的。
98
• 当用户创建一个文件时，首先要给该文件分配足够
的存储空间。
存储空间的管理方法有空白文件目录、
空闲块链和位示图法。
比较有影响的存储空间管理
方法是空闲块链中的
成组链法
。
• 文件名或记录名与物理地址之间的转换通过文件目
录来实现。有单级目录、二级目录和多级目录几种
目录结构。
二级目录和多级目录是为了解决文件的
重名问题和提高搜索速度而提出来的。
多级目录构
成文件树形结构。
另外，
为了便于共享，把目录项
中存放的文件说明信息画分为两部分：文件内部标
识符和文件名与存取控制信息以及结构信息等文件
说明信息部分。前者的集合称为符号文件表
SFD
SDF
，
后者的集合称为基本文件表
BFD
。
99
• 对文件的存取控制是和文件共享、保护和保密紧密
相关的。
存取控制可采用存取控制矩阵、存取控制
表、口令和密码的方法进行存取验证，以确定用户
权限。
• 最后，在本章中介绍了
文件系统的使用方法
和
文件
系统的层次模型。