第六章 文件管理
第六章 文 件 管 理
6.1 文件和文件系统
6.2 文件的逻辑结构
6.3 外存分配方式
6.4 目录管理
6.5 文件存储空间的管理
6.6 文件共享与文件保护
6.7 数据一致性控制
第六章 文件管理
6.1 文件和文件系统
6.1.1 文件、记录和数据项
1,数据项
(1) 基本数据项 。 这是用于描述一个对象的某种属性的
字符集, 是数据组织中可以命名的最小逻辑数据单位, 即
原子数据, 又称为数据元素或字段 。 它的命名往往与其属
性一致 。 例如, 用于描述一个学生的基本数据项有,学号,
姓名, 年龄, 所在班级等 。
第六章 文件管理
(2) 组合数据项 。 它是由若干个基本数据项组成的, 简
称组项 。 例如, 经理便是个组项, 它由正经理和副经理两个
基本项组成 。 又如, 工资也是个组项, 它可由基本工资, 工
龄工资和奖励工资等基本项所组成 。
基本数据项除了数据名外, 还应有数据类型 。 因为基本
项仅是描述某个对象的属性, 根据属性的不同, 需要用不同
的数据类型来描述 。 例如, 在描述学生的学号时, 应使用整
数； 描述学生的姓名则应使用字符串 (含汉字 )；描述性别时,
可用逻辑变量或汉字 。 可见, 由数据项的名字和类型两者共
同定义了一个数据项的, 型, 。 而表征一个实体在数据项上
的数据则称为, 值, 。 例如, 学号 /30211,姓名 /王有年, 性
别 /男等 。
第六章 文件管理
2,记录
记录是一组相关数据项的集合, 用于描述一个对象在某
方面的属性 。 一个记录应包含哪些数据项, 取决于需要描述
对象的哪个方面 。 而一个对象, 由于他所处的环境不同可把
他作为不同的对象 。 例如, 一个学生, 当把他作为班上的
一名学生时, 对他的描述应使用学号, 姓名, 年龄及所在
系班, 也可能还包括他所学过的课程的名称, 成绩等数据
项 。 但若把学生作为一个医疗对象时, 对他描述的数据项
则应使用诸如病历号, 姓名, 性别, 出生年月, 身高,
体重, 血压及病史等项 。
第六章 文件管理
3,文件
文件是指由创建者所定义的, 具有文件名的一组相关
元素的集合, 可分为有结构文件和无结构文件两种 。 在有
结构的文件中, 文件由若干个相关记录组成；而无结构文
件则被看成是一个字符流 。 文件在文件系统中是一个最大
的数据单位, 它描述了一个对象集 。 例如, 可以将一个班
的学生记录作为一个文件 。 一个文件必须要有一个文件名,
它通常是由一串 ASCII码或 (和 )汉字构成, 名字的长度因系
统不同而异 。 如在有的系统中把名字规定为 8个字符, 而在
有的系统中又规定可用 14个字符 。
第六章 文件管理
(1) 文件类型。
(2) 文件长度。
(3) 文件的物理位置。
(4) 文件的建立时间。
文件
记录 1 记录 2 ? 记录 n
数据项 1 数据项 2 ? 数据项 n
图 6-1 文件,记录和数据项之间的层次关系
第六章 文件管理
6.1.2 文件类型和文件系统模型
1,
1) 按用途分类
(1) 系统文件。
(2) 用户文件。
(3) 库文件。
第六章 文件管理
2) 按文件中数据的形式分类
(1) 源文件。
(2) 目标文件。
(3) 可执行文件。
第六章 文件管理
3)
(1) 只执行文件。
(2) 只读文件。
(3) 读写文件。
第六章 文件管理
2,文件系统模型
图 6-2 文件系统模型
第六章 文件管理
1)
文件管理系统管理的对象有,① 文件 。 它作为文
件管理的直接对象 。 ② 目录 。 为了方便用户对文件的
存取和检索, 在文件系统中必须配置目录 。 对目录的组
织和管理是方便用户和提高对文件存取速度的关键 。 ③
磁盘 (磁带 )存储空间 。 文件和目录必定占用存储空间,
对这部分空间的有效管理, 不仅能提高外存的利用率,
而且能提高对文件的存取速度 。
第六章 文件管理
2)
这是文件管理系统的核心部分 。 文件系统的功能大
多是在这一层实现的, 其中包括：对文件存储空间的管
理, 对文件目录的管理, 用于将文件的逻辑地址转换为
物理地址的机制, 对文件读和写的管理, 以及对文件的
共享与保护等功能 。
第六章 文件管理
3)
为方便用户使用文件系统, 文件系统通常向用户提供
(1) 命令接口 。 这是指作为用户与文件系统交互的接
口 。 用户可通过键盘终端键入命令, 取得文件系统的服
务 。
(2) 程序接口 。 这是指作为用户程序与文件系统的接
口 。 用户程序可通过系统调用来取得文件系统的服务 。
第六章 文件管理
6.1.3 文件操作
(1) 创建文件。
(2) 删除文件。
(3) 读文件。
(4) 写文件。
(5) 截断文件。
(6) 设置文件的读 /写位置。
第六章 文件管理
2,文件的“打开”和“关闭”操作
所谓, 打开,, 是指系统将指名文件的属性 (包括该文件
在外存上的物理位置 )从外存拷贝到内存打开文件表的一个表
目中, 并将该表目的编号 (或称为索引 )返回给用户 。 以后,
当用户再要求对该文件进行相应的操作时, 便可利用系统所
返回的索引号向系统提出操作请求 。 系统这时便可直接利用
该索引号到打开文件表中去查找, 从而避免了对该文件的再
次检索 。 这样不仅节省了大量的检索开销, 也显著地提高了
对文件的操作速度 。 如果用户已不再需要对该文件实施相应
的操作时, 可利用, 关闭, (close)系统调用来关闭此文件,
OS将会把该文件从打开文件表中的表目上删除掉 。
第六章 文件管理
3,其它文件操作
为了方便用户使用文件, 通常, OS都提供了数条有关
文件操作的系统调用, 可将这些调用分成若干类：最常用的
一类是有关对文件属性进行操作的, 即允许用户直接设置和
获得文件的属性, 如改变已存文件的文件名, 改变文件的拥
有者 (文件主 ),改变对文件的访问权, 以及查询文件的状态
(包括文件类型, 大小和拥有者以及对文件的访问权等 )；另
一类是有关目录的, 如创建一个目录, 删除一个目录, 改变
当前目录和工作目录等；此外, 还有用于实现文件共享的系
统调用和用于对文件系统进行操作的系统调用等 。
第六章 文件管理
6.2 文件的逻辑结构
对于任何一个文件,
（ 1）文件的逻辑结构 (File Logical Structure)。
(2) 文件的物理结构,又称为文件的存储结构,是指文
件在外存上的存储组织形式。
第六章 文件管理
6.2.1 文件逻辑结构的类型
1,有结构文件
(1) 定长记录。
(2) 变长记录。
(1) 顺序文件。
(2) 索引文件。
(3) 索引顺序文件。
第六章 文件管理
2,无结构文件
如果说大量的数据结构和数据库, 是采用有结构的文
件形式的话, 则大量的源程序, 可执行文件, 库函数等,
所采用的就是无结构的文件形式, 即流式文件 。 其长度以
字节为单位 。 对流式文件的访问, 则是采用读写指针来指
出下一个要访问的字符 。 可以把流式文件看作是记录式文
件的一个特例 。 在 UNIX系统中, 所有的文件都被看作是
流式文件；即使是有结构文件, 也被视为流式文件；系统
不对文件进行格式处理 。
第六章 文件管理
6.2.2 顺序文件
1,逻辑记录的排序
第一种是串结构, 各记录之间的顺序与关键字无关 。
通常的办法是由时间来决定, 即按存入时间的先后排列,
最先存入的记录作为第一个记录, 其次存入的为第二个记
录, …… 依此类推 。
第二种情况是顺序结构, 指文件中的所有记录按关键
字 (词 )排列 。 可以按关键词的长短从小到大排序, 也可以
从大到小排序；或按其英文字母顺序排序 。
第六章 文件管理
2,对顺序文件 (Sequential File)的读 /
R
0
R
1
R
2
R
3
?
R
i
?
L
L
L
L
L
L
2L
3L
4L
L
(i ＋ 1 ) L
R p t r
( a ) 定长记录文件
L
0
R
0
L
1
R
1
?
R
i
?
W p t r
( b ) 变 长记录文件
L
i
0 0
L
0
L
0
＋ 1
L
1
L
0
＋ L
1
＋ 2
L
i
∑(L
k
＋ 1)
i － 1
k ＝ 0
∑(L
k
＋ 1)
i
k ＝ 0
图 6-3 定长和变长记录文件
第六章 文件管理
3,
顺序文件的最佳应用场合, 是在对诸记录进行批量存取时,
即每次要读或写一大批记录 。 此时, 对顺序文件的存取效率是
所有逻辑文件中最高的；此外, 也只有顺序文件才能存储在磁
带上, 并能有效地工作 。
在交互应用的场合, 如果用户 (程序 )要求查找或修改单个记
录, 为此系统便要去逐个地查找诸记录 。 这时, 顺序文件所表
现出来的性能就可能很差, 尤其是当文件较大时, 情况更为严
重 。 例如, 有一个含有 104个记录的顺序文件, 如果对它采用顺
序查找法去查找一个指定的记录, 则平均需要查找 5× 103个记
录； 如果是可变长记录的顺序文件, 则为查找一个记录所需付
出的开销将更大, 这就限制了顺序文件的长度 。
第六章 文件管理
顺序文件的另一个缺点是, 如果想增加或删除一个
记录, 都比较困难 。 为了解决这一问题, 可以为顺序
文件配置一个运行记录文件 (Log File)或称为事务文件
(Transaction File),把试图增加, 删除或修改的信息记
录于其中, 规定每隔一定时间, 例如 4小时, 将运行记
录文件与原来的主文件加以合并, 产生一个按关键字排
序的新文件 。
第六章 文件管理
6.2.3 索引文件
对于定长记录文件, 如果要查找第 i个记录, 可直接根
据下式计算来获得第 i个记录相对于第一个记录首址的地址：
Ai=i× L
然而，对于可变长度记录的文件，要查找其第 i个记录
时，须首先计算出该记录的首地址。为此，须顺序地查找
每个记录，从中获得相应记录的长度 Li，然后才能按下式计
算出第 i个记录的首址。假定在每个记录前用一个字节指明
该记录的长度，则
?
?
?
??
1
0
i
i
ii iLA
第六章 文件管理
索引号
0
长度 m 指针 p t r
m
0
1 m
1
…
i m
i
…
索引表
R
0
R
1
…
R
i
…
逻辑文件
图 6-4 索引文件的组织
第六章 文件管理
6.2.4 索引顺序文件
键
A n Q i
B a o R o n g
C h e n Li n
逻辑地址 姓 名
A n Q i
A n K a n g
其它属性
B a o R o n g
?
逻辑文件
图 6-5 索引顺序文件
第六章 文件管理
6.2.5 直接文件和哈希文件
1,直接文件
对于直接文件, 则可根据给定的记录键值, 直接获得指
定记录的物理地址 。 换言之, 记录键值本身就决定了记录的
物理地址 。 这种由记录键值到记录物理地址的转换被称为键
值转换 (Key to address transformation)。 组织直接文件的关键,
在于用什么方法进行从记录值到物理地址的转换 。
第六章 文件管理
2,哈希 (Hash)文件
图 6-6 Hash文件的逻辑结构
f
H a s h 函数
目录表
键值
第六章 文件管理
6.3 外存分配方式
6.3.1 连续分配
1 2 3
0
5 6
7
4
9 10 11
8
13 14
15
12
17 18 19
16
21 22 23
20
25 26 27
24
l i s t
29 30 31
28
m a i l
c o u n t
f i l e s t a r t l e n g t h
c o u n t 0 2
tr 14 3
m a i l 19 6
l i s t 28 4
f 6 2
目录
tr
f
图 6-7 磁盘空间的连续分配
第六章 文件管理
2,连续分配的主要优缺点
(1) 顺序访问容易。
(2) 顺序访问速度快。
(1) 要求有连续的存储空间。
(2) 必须事先知道文件的长度。
第六章 文件管理
6.3.2 链接分配
1,隐式链接
图 6-8 磁盘空间的链接式分配
25
1 2 3
0
5 6 7
4
9
10
11
8
13 14 15
12
17 18 19
16
21 22 23
20
25
26
27
24
29 30 31
28
f i l e s t a r t e n d
j e e p 9 25
目录
10
1
- 1
16
第六章 文件管理
2,显式链接
图 6-9 显式链接结构
0
1
2
3
4
5
物理 块号
2
F C B F A T
0
4
5
1
第六章 文件管理
6
E O F
11
10
5
E O F
0
1
2
3
4
5
6
7
8
9
F A TF C B A
4
F C B B
9
图
6-
10MS
-DOS
的
文
件
物
理
结
构
第六章 文件管理
6.3.3 索引分配
1.
链接分配方式虽然解决了连续分配方式所存在的问题,
但又出现了另外两个问题,
(1) 不能支持高效的直接存取 。 要对一个较大的文件进
行直接存取, 须首先在 FAT中顺序地查找许多盘块号 。
(2) FAT需占用较大的内存空间。
第六章 文件管理
图 6-11 索引分配方式
1 2
3
0
5 6 7
4
9
10
11
8
13 14 15
12
17 18
19
16
21
22
23
20
25
26
27
24
29 30
31
28
c o u n t
f i l e 块序 号
j e e p 19
目录
9
16
1
10
25
－ 1
－ 1
－ 1
19
第六章 文件管理
2,多级索引分配
0
1
2
…
…
…
…
…
1 0 5
1 0 6
2 5 4
3 5 6
3 5 7
9 8 5
1 0 5
1 0 6
2 5 4
7 4 0
3 5 6
3 5 7
…
1 1 2 5
9 8 5
3 6 0
7 4 0
…
1 1 2 5
…
主索引
3 6 0
第二级索引
磁盘空间
图
6-
12
两
级
索
引
分
配
第六章 文件管理
图 6-13 混合索引方式
m o d e
o w n e r s ( 2 )
t i m e s t a m p s ( 3 )
s i z e
b l o c k c o u n t
i, a d d r ( 0 )
i, a d d r ( 1 )
d i r e c t b l o c k s
s i n g l e i n d i r e c t
d o u b l e i n d i r e c t
t r i p l e i n d i r e c t
d a t a
d a t a
d a t a
d a t a
…
…
d a t a
d a t a
…
…
…
d a t a
d a t a
d a t a
d a t a
第六章 文件管理
(1) 直接地址 。
为了提高对文件的检索速度, 在索引结点中可设置 10
个直接地址项, 即用 iaddr(0)~iaddr(9)来存放直接地址 。
换言之, 在这里的每项中所存放的是该文件数据的盘块的
盘块号 。 假如每个盘块的大小为 4 KB,当文件不大于 40
KB时, 便可直接从索引结点中读出该文件的全部盘块号 。
第六章 文件管理
(2) 一次间接地址 。
对于大, 中型文件, 只采用直接地址是不现实的 。
为此, 可再利用索引结点中的地址项 iaddr(10)来提供一
次间接地址 。 这种方式的实质就是一级索引分配方式 。
图中的一次间址块也就是索引块, 系统将分配给文件的
多个盘块号记入其中 。 在一次间址块中可存放 1K个盘块
号, 因而允许文件长达 4 MB。
第六章 文件管理
(3) 多次间接地址 。
当文件长度大于 4 MB+40 KB时 (一次间址与 10个直接
地址项 ),系统还须采用二次间址分配方式 。 这时, 用地
址项 iaddr(11)提供二次间接地址 。 该方式的实质是两级索
引分配方式 。 系统此时是在二次间址块中记入所有一次间
址块的盘号 。 在采用二次间址方式时, 文件最大长度可达
4 GB。 同理, 地址项 iaddr(12)作为三次间接地址, 其所允
许的文件最大长度可达 4 TB。
第六章 文件管理
6.4 目 录 管 理
(1) 实现“按名存取”。
(2) 提高对目录的检索速度。
(3) 文件共享。
(4) 允许文件重名。
第六章 文件管理
6.4.1 文件控制块和索引结点
1,文件控制块
(1) 基本信息类
① 文件名 ； ② 文件物理位置 ； ③ 文件逻辑结构 ；
④ 文件的物理结构
(2) 存取控制信息类
(3) 使用信息类
图 6-14 MS-DOS的文件控制块
文
件
名
扩
展
名
属
性
备
用
时
间
日
期
第
一
块
号
盘
块
数
第六章 文件管理
2,索引结点
1) 索引结点的引入
图 6-15 UNIX的文件目录
文件名 索引结点编号
文件名 1
文件名 2
… …
第六章 文件管理
2) 磁盘索引结点
(1) 文件主标识符
(2) 文件类型
(3) 文件存取权限
(4) 文件物理地址
(5) 文件长度
(6) 文件连接计数
(7) 文件存取时间
第六章 文件管理
3) 内存索引结点
(1) 索引结点编号。
(2) 状态。 指示 i
(3) 访问计数。 每当有一进程要访问此 i结点时,将该访问
计数加 1,访问完再减 1
(4)
(5) 链接指针。 设置有分别指向空闲链表和散列队列的指针。
第六章 文件管理
6.4.2 目录结构
1,单级目录结构
文件名 物理地址 文件说明 状态位
文件名 1
文件名 2
…
图 6-16 单级目录
第六章 文件管理
单级目录的优点是简单且能实现目录管理的基本功
能 ——按名存取,
(1) 查找速度慢
(2) 不允许重名
(3) 不便于实现文件共享
第六章 文件管理
2,两级目录
图 6-17 两级目录结构
用户名
W a n g
Z h a n g
G a o
指向子目录指针
W a n g 用户目录
A l p h a
T e s t
A l p h a
T e s t
R e p o r t
T e s t
Z h a n g 用户目录
R e p o r t
T e s t
G a o 用户目录
B e t a
D e v i c e
M i s x
B e t a
D e v i c e
M i s x
第六章 文件管理
(1) 提高了检索目录的速度
(2) 在不同的用户目录中,可以使用相同的文件名。
(3) 不同用户还可使用不同的文件名来访问系统中的同一
个共享文件
第六章 文件管理
3,多级目录结构
(1) 目录结构
图 6-18 多级目录结构
A B C
F E D
1
3A B D2 G A4
A C5
6 7
10 11
J N K12 J M K13 A H F14
15 16
b
17 18 19 20 21
a
8 9
第六章 文件管理
(2) 路径名 。
在树形目录结构中, 从根目录到任何数据文件, 都只
有一条惟一的通路 。 在该路径上从树的根 (即主目录 )开始,
把全部目录文件名与数据文件名, 依次地用, /”连接起来,
即构成该数据文件的路径名 (path name)。 系统中的每一个
文件都有惟一的路径名 。 例如, 在图 6-18 中用户 B为访问
文件 J,应使用其路径名 /B/F/J来访问 。
第六章 文件管理
(3) 当前目录 (Current Directory)。
当一个文件系统含有许多级时, 每访问一个文件, 都要
使用从树根开始直到树叶 (数据文件 )为止的, 包括各中间结
点 (目录 )名的全路径名 。 这是相当麻烦的事, 同时由于一个
进程运行时所访问的文件, 大多仅局限于某个范围, 因而非
常不便 。 基于这一点, 可为每个进程设置一个, 当前目录,,
又称为, 工作目录, 。 进程对各文件的访问都相对于, 当前
目录, 而进行 。 此时各文件所使用的路径名, 只需从当前目
录开始, 逐级经过中间的目录文件, 最后到达要访问的数据
文件 。 把这一路径上的全部目录文件名与数据文件名用, /”
连接形成路径名, 如用户 B的当前目录是 F,则此时文件 J的相
对路径名仅是 J本身 。 这样, 把从当前目录开始直到数据文
件为止所构成的路径名, 称为相对路径名 (relative path name)；
而把从树根开始的路径名称为绝对路径名 (absolute path name)。
第六章 文件管理
4,增加和删除目录
(1) 不删除非空目录 。 当目录 (文件 )不空时, 不能将其删
除, 而为了删除一个非空目录, 必须先删除目录中的所有文
件, 使之先成为空目录, 后再予以删除 。 如果目录中还包含
有子目录, 还必须采取递归调用方式来将其删除, 在 MS-
DOS中就是采用这种删除方式 。
(2) 可删除非空目录 。 当要删除一目录时, 如果在该目
录中还包含有文件, 则目录中的所有文件和子目录也同时被
删除 。
第六章 文件管理
6.4.3 目录查询技术
1,线性检索法
图 6-19 查找 /usr/ast/mbox的步骤
第六章 文件管理
2,Hash方法
一种处理此, 冲突,
(1) 在利用 Hash法索引查找目录时, 如果目录表中相应的
目录项是空的, 则表示系统中并无指定文件 。
(2) 如果目录项中的文件名与指定文件名相匹配, 则表
示该目录项正是所要寻找的文件所对应的目录项, 故而可从
中找到该文件所在的物理地址 。
(3) 如果在目录表的相应目录项中的文件名与指定文件
名并不匹配, 则表示发生了, 冲突,, 此时须将其 Hash值再
加上一个常数 (该常数应与目录的长度值互质 ),形成新的索
引值, 再返回到第一步重新开始查找 。
第六章 文件管理
6.5 文件存储空间的管理
6.5.1 空闲表法和空闲链表法
1,空闲表法
图 6-20 空闲盘块表
序号 第一空闲盘块号 空闲盘块数
1 2 4
2 9 3
3 15 5
4 — —
第六章 文件管理
(2) 存储空间的分配与回收 。
空闲盘区的分配与内存的动态分配类似, 同样是采用
首次适应算法, 循环首次适应算法等 。 例如, 在系统为某
新创建的文件分配空闲盘块时, 先顺序地检索空闲表的各
表项, 直至找到第一个其大小能满足要求的空闲区, 再将
该盘区分配给用户 (进程 ),同时修改空闲表 。 系统在对用
户所释放的存储空间进行回收时, 也采取类似于内存回收
的方法, 即要考虑回收区是否与空闲表中插入点的前区和
后区相邻接, 对相邻接者应予以合并 。
第六章 文件管理
2,空闲链表法
(1) 空闲盘块链。
(2) 空闲盘区链
第六章 文件管理
6.5.2 位示图法
1,位示图
图 6-21 位示图
第六章 文件管理
2,盘块的分配
(1) 顺序扫描位示图, 从中找出一个或一组其值为, 0”
的二进制位 (“0”表示空闲时 )。
(2) 将所找到的一个或一组二进制位,转换成与之相应
的盘块号。假定找到的其值为, 0”的二进制位，位于位示
的第 i行、第 j列，则其相应的盘块号应按下式计算：
b=n(i-1)+j
式中, n代表每行的位数 。
(3) 修改位示图,令 map［ i,j］ =1。
第六章 文件管理
3,盘块的回收
(1) 将回收盘块的盘块号转换成位示图中的行号和列
号 。
i=(b-1)DIV n+1
j=(b-1)MOD n+1
(2) 修改位示图。 令 map ［ i,j］ =1。
第六章 文件管理
6.5.3 成组链接法
1,
1 0 0
4 0 0
3 9 9
3 0 1
3 0 0
1 0 0
3 0 0
2 9 9
…
2 0 2
2 0 1
2 9 9
…
1 0 0
4 0 0
3 9 9
…
2 0 1 3 0 1
…
…
…
99
0
7 9 9 9
7 9 0 1
7 9 0 0
7 8 9 9
…
7 8 0 1
7 9 9 9
…
7 9 0 1
空闲盘块号
栈
S, f r e e
0
1
98
99
图
6-
22
空
闲
盘
块
的
成
组
链
接
法
第六章 文件管理
2.
当系统要为用户分配文件所需的盘块时, 须调用盘块分
配过程来完成 。 该过程首先检查空闲盘块号栈是否上锁, 如
未上锁, 便从栈顶取出一空闲盘块号, 将与之对应的盘块分
配给用户, 然后将栈顶指针下移一格 。 若该盘块号已是栈底,
即 S.free(0),这是当前栈中最后一个可分配的盘块号 。 由于
在该盘块号所对应的盘块中记有下一组可用的盘块号, 因此,
须调用磁盘读过程, 将栈底盘块号所对应盘块的内容读入栈
中, 作为新的盘块号栈的内容, 并把原栈底对应的盘块分配
出去 (其中的有用数据已读入栈中 )。 然后, 再分配一相应的
缓冲区 (作为该盘块的缓冲区 )。 最后, 把栈中的空闲盘块数
减 1并返回 。
第六章 文件管理
在系统回收空闲盘块时, 须调用盘块回收过程进行回
收 。 它是将回收盘块的盘块号记入空闲盘块号栈的顶部,
并执行空闲盘块数加 1操作 。 当栈中空闲盘块号数目已达
100时, 表示栈已满, 便将现有栈中的 100个盘块号, 记入
新回收的盘块中, 再将其盘块号作为新栈底 。
第六章 文件管理
6.6 文件共享与文件保护
A
A
B
B B B
B C
C
C
C
C
根目录
C CC
图 6-23 包含有共享文件的文件系统
第六章 文件管理
图 6-24 基于索引结点的共享方式
W a n g 用户文件目录
T e s t r
L e e 用户文件目录
T e s t r
c o u n t ＝ 2
文件物理地址
索引结点
T e s t
第六章 文件管理
图 6-25 进程 B链接前后的情况
C 的目录
o w n e r ＝ c
c o u n t ＝ 1
链接前
C 的目录
o w n e r ＝ c
c o u n t ＝ 2
建立链接后
B 的目录 B 的目录
o w n e r ＝ c
c o u n t ＝ 1
拥有者删除文件后
第六章 文件管理
6.6.2 利用符号链实现文件共享
在利用符号链方式实现文件共享时, 只是文件主才拥有
指向其索引结点的指针；而共享该文件的其他用户, 则只有
该文件的路径名, 并不拥有指向其索引结点的指针 。 这样,
也就不会发生在文件主删除一共享文件后留下一悬空指针的
情况 。 当文件的拥有者把一个共享文件删除后, 其他用户
试图通过符号链去访问一个已被删除的共享文件时, 会因系
统找不到该文件而使访问失败, 于是再将符号链删除, 此时
不会产生任何影响 。
第六章 文件管理
6.6.3 磁盘容错技术
(1) 通过存取控制机制来防止由人为因素所造成的文件
不安全性 。
(2) 通过磁盘容错技术, 来防止由磁盘部分的故障所造
成的文件不安全性 。
(3) 通过“后备系统”来防止由自然因素所造成的不安
全性。
第六章 文件管理
1,第一级容错技术 SFT-Ⅰ
1)
在磁盘上存放的文件目录和文件分配表 FAT,是文件
管理所用的重要数据结构 。 如果这些表格被破坏, 将导致
磁盘上的部分或全部文件成为不可访问的, 因而也就等效
于文件的丢失 。 为了防止这类情况发生, 可在不同的磁盘
上或在磁盘的不同区域中, 分别建立 (双份 )目录表和 FAT。
其中, 一份被称为主目录及主 FAT； 把另一份称为备份目
录及备份 FAT。
第六章 文件管理
2) 热修复重定向和写后读校验
(1) 热修复重定向 (Hot-Redirection)。
(2) 写后读校验 (Read after write Verification)方式。
第六章 文件管理
2,第二级容错技术 SFT-Ⅱ
(1) 磁盘镜像 (Disk Mirroring)。
磁
盘
控
制
器
主
机
通道
磁盘驱动器
图 6-26 磁盘镜像示意
第六章 文件管理
(2) 磁盘双工 (Disk Duplexing)。
图 6-27 磁盘双工示意
主
机
磁盘
控制器
磁盘
控制器
通道
通道
磁盘驱动器
第六章 文件管理
6.7 数据一致性控制
6.7.1 事务
1,事务的定义
事务是用于访问和修改各种数据项的一个程序单位 。 事
务也可以被看作是一系列相关读和写操作 。 被访问的数据可以
分散地存放在同一文件的不同记录中, 也可放在多个文件中 。
只有对分布在不同位置的同一数据所进行的读和写 (含修改 )操
作全部完成时, 才能再以托付操作 (Commit Operation)来终止
事务 。 只要有一个读, 写或修改操作失败, 便须执行夭折操
作 (Abort Operation)。 读或写操作的失败可能是由于逻辑错误,
也可能是系统故障所导致的 。
第六章 文件管理
2,事务记录 (Transaction Record)
·事务名：
·数据项名：
·旧值：
·新值,修改后数据项将具有的值。
第六章 文件管理
3,恢复算法
(1) undo〈 Ti〉 。 该过程把所有被事务 Ti修改过的数据,
恢复为修改前的值 。
(2) redo〈 Ti〉 。 该过程能把所有被事务 Ti修改过的数据,
设置为新值 。
如果系统发生故障,系统应对以前所发生的事务进行
清理。
第六章 文件管理
6.7.2 检查点
1,检查点 (Check Points)的作用
引入检查点的主要目的, 是使对事务记录表中事务记
录的清理工作经常化, 即每隔一定时间便做一次下述工作：
首先是将驻留在易失性存储器 (内存 )中的当前事务记录表中
的所有记录, 输出到稳定存储器中；其次是将驻留在易失
性存储器中的所有已修改数据, 输出到稳定存储器中；然
后是将事务记录表中的 〈 检查点 〉 记录, 输出到稳定存储
器中； 最后是每当出现一个 〈 检查点 〉 记录时, 系统便执
行上小节所介绍的恢复操作, 利用 redo和 undo过程实现恢复
功能 。
第六章 文件管理
2,新的恢复算法
恢复例程首先查找事务记录表, 确定在最近检查点以前
开始执行的最后的事务 Ti。 在找到这样的事务后, 再返回去
搜索事务记录表, 便可找到第一个检查点记录, 恢复例程便
从该检查点开始, 返回搜索各个事务的记录, 并利用 redo和
undo过程对它们进行处理 。
如果把所有在事务 Ti以后开始执行的事务表示为事务集 T，
则新的恢复操作要求是：对所有在 T中的事务 TK,如果在事务
记录表中出现了 〈 TK托付 〉 记录, 则执行 redo〈 TK〉 操作；
反之, 如果在事务记录表中并未出现 〈 TK托付 〉 记录, 则执
行 undo〈 TK〉 操作 。
第六章 文件管理
6.7.3 并发控制
1,利用互斥锁实现“顺序性”
2,利用互斥锁和共享锁实现顺序性
第六章 文件管理
6.7.4 重复数据的数据一致性问题
1,重复文件的一致性
图 6-28 UNIX类型的目录
第六章 文件管理
2,盘块号一致性的检查
图 6-29 检查盘块号一致性情况
第六章 文件管理
图 6-29 检查盘块号一致性情况
第六章 文件管理
3,链接数一致性检查
为每个盘块建立一个表项, 其中含有该索引结点号的计
数值 。 在进行检查时, 从根目录开始查找, 每当在目录中遇
到该索引结点号时, 便在该计数器表中相应文件的表项上加
1。 当把所有目录都检查完后, 便可将该计数器表中每个表
项中的索引结点号计数值与该文件索引结点中的链接计数
count值加以比较, 如果两者一致, 表示是正确的；否则,
便是发生了链接数据不一致的错误 。
第六章 文件管理
如果索引结点中的链接计数 count值大于计数器表中相应索
引结点号的计数值, 则即使在所有共享此文件的用户都不再使
用此文件时, 其 count值仍不为 0,因而该文件不会被删除 。 这
种错误的后果是使一些已无用户需要的文件仍驻留在磁盘上,
浪费了存储空间 。 解决的方法是用计数器表中的正确的计数值
去为 count重新赋值 。
反之, 如果出现 count值小于计数器表中索引结点号计数值
的情况时, 就有潜在的危险 。 假如有两个用户共享一个文件,
但是 count值仍为 1,这样, 只要其中有一个用户不再需要此文
件时, count值就会减为 0,从而使系统将此文件删除, 并释放
其索引结点及文件所占用的盘块, 导致另一共享此文件的用户
所对应的目录项, 指向了一个空索引结点, 最终是使该用户再
无法访问此文件 。 如果该索引结点很快又被分配给其它文件,
则又会带来潜在的危险 。 解决的方法是将 count值置为正确值 。
第六章 文 件 管 理
6.1 文件和文件系统
6.2 文件的逻辑结构
6.3 外存分配方式
6.4 目录管理
6.5 文件存储空间的管理
6.6 文件共享与文件保护
6.7 数据一致性控制
第六章 文件管理
6.1 文件和文件系统
6.1.1 文件、记录和数据项
1,数据项
(1) 基本数据项 。 这是用于描述一个对象的某种属性的
字符集, 是数据组织中可以命名的最小逻辑数据单位, 即
原子数据, 又称为数据元素或字段 。 它的命名往往与其属
性一致 。 例如, 用于描述一个学生的基本数据项有,学号,
姓名, 年龄, 所在班级等 。
第六章 文件管理
(2) 组合数据项 。 它是由若干个基本数据项组成的, 简
称组项 。 例如, 经理便是个组项, 它由正经理和副经理两个
基本项组成 。 又如, 工资也是个组项, 它可由基本工资, 工
龄工资和奖励工资等基本项所组成 。
基本数据项除了数据名外, 还应有数据类型 。 因为基本
项仅是描述某个对象的属性, 根据属性的不同, 需要用不同
的数据类型来描述 。 例如, 在描述学生的学号时, 应使用整
数； 描述学生的姓名则应使用字符串 (含汉字 )；描述性别时,
可用逻辑变量或汉字 。 可见, 由数据项的名字和类型两者共
同定义了一个数据项的, 型, 。 而表征一个实体在数据项上
的数据则称为, 值, 。 例如, 学号 /30211,姓名 /王有年, 性
别 /男等 。
第六章 文件管理
2,记录
记录是一组相关数据项的集合, 用于描述一个对象在某
方面的属性 。 一个记录应包含哪些数据项, 取决于需要描述
对象的哪个方面 。 而一个对象, 由于他所处的环境不同可把
他作为不同的对象 。 例如, 一个学生, 当把他作为班上的
一名学生时, 对他的描述应使用学号, 姓名, 年龄及所在
系班, 也可能还包括他所学过的课程的名称, 成绩等数据
项 。 但若把学生作为一个医疗对象时, 对他描述的数据项
则应使用诸如病历号, 姓名, 性别, 出生年月, 身高,
体重, 血压及病史等项 。
第六章 文件管理
3,文件
文件是指由创建者所定义的, 具有文件名的一组相关
元素的集合, 可分为有结构文件和无结构文件两种 。 在有
结构的文件中, 文件由若干个相关记录组成；而无结构文
件则被看成是一个字符流 。 文件在文件系统中是一个最大
的数据单位, 它描述了一个对象集 。 例如, 可以将一个班
的学生记录作为一个文件 。 一个文件必须要有一个文件名,
它通常是由一串 ASCII码或 (和 )汉字构成, 名字的长度因系
统不同而异 。 如在有的系统中把名字规定为 8个字符, 而在
有的系统中又规定可用 14个字符 。
第六章 文件管理
(1) 文件类型。
(2) 文件长度。
(3) 文件的物理位置。
(4) 文件的建立时间。
文件
记录 1 记录 2 ? 记录 n
数据项 1 数据项 2 ? 数据项 n
图 6-1 文件,记录和数据项之间的层次关系
第六章 文件管理
6.1.2 文件类型和文件系统模型
1,
1) 按用途分类
(1) 系统文件。
(2) 用户文件。
(3) 库文件。
第六章 文件管理
2) 按文件中数据的形式分类
(1) 源文件。
(2) 目标文件。
(3) 可执行文件。
第六章 文件管理
3)
(1) 只执行文件。
(2) 只读文件。
(3) 读写文件。
第六章 文件管理
2,文件系统模型
图 6-2 文件系统模型
第六章 文件管理
1)
文件管理系统管理的对象有,① 文件 。 它作为文
件管理的直接对象 。 ② 目录 。 为了方便用户对文件的
存取和检索, 在文件系统中必须配置目录 。 对目录的组
织和管理是方便用户和提高对文件存取速度的关键 。 ③
磁盘 (磁带 )存储空间 。 文件和目录必定占用存储空间,
对这部分空间的有效管理, 不仅能提高外存的利用率,
而且能提高对文件的存取速度 。
第六章 文件管理
2)
这是文件管理系统的核心部分 。 文件系统的功能大
多是在这一层实现的, 其中包括：对文件存储空间的管
理, 对文件目录的管理, 用于将文件的逻辑地址转换为
物理地址的机制, 对文件读和写的管理, 以及对文件的
共享与保护等功能 。
第六章 文件管理
3)
为方便用户使用文件系统, 文件系统通常向用户提供
(1) 命令接口 。 这是指作为用户与文件系统交互的接
口 。 用户可通过键盘终端键入命令, 取得文件系统的服
务 。
(2) 程序接口 。 这是指作为用户程序与文件系统的接
口 。 用户程序可通过系统调用来取得文件系统的服务 。
第六章 文件管理
6.1.3 文件操作
(1) 创建文件。
(2) 删除文件。
(3) 读文件。
(4) 写文件。
(5) 截断文件。
(6) 设置文件的读 /写位置。
第六章 文件管理
2,文件的“打开”和“关闭”操作
所谓, 打开,, 是指系统将指名文件的属性 (包括该文件
在外存上的物理位置 )从外存拷贝到内存打开文件表的一个表
目中, 并将该表目的编号 (或称为索引 )返回给用户 。 以后,
当用户再要求对该文件进行相应的操作时, 便可利用系统所
返回的索引号向系统提出操作请求 。 系统这时便可直接利用
该索引号到打开文件表中去查找, 从而避免了对该文件的再
次检索 。 这样不仅节省了大量的检索开销, 也显著地提高了
对文件的操作速度 。 如果用户已不再需要对该文件实施相应
的操作时, 可利用, 关闭, (close)系统调用来关闭此文件,
OS将会把该文件从打开文件表中的表目上删除掉 。
第六章 文件管理
3,其它文件操作
为了方便用户使用文件, 通常, OS都提供了数条有关
文件操作的系统调用, 可将这些调用分成若干类：最常用的
一类是有关对文件属性进行操作的, 即允许用户直接设置和
获得文件的属性, 如改变已存文件的文件名, 改变文件的拥
有者 (文件主 ),改变对文件的访问权, 以及查询文件的状态
(包括文件类型, 大小和拥有者以及对文件的访问权等 )；另
一类是有关目录的, 如创建一个目录, 删除一个目录, 改变
当前目录和工作目录等；此外, 还有用于实现文件共享的系
统调用和用于对文件系统进行操作的系统调用等 。
第六章 文件管理
6.2 文件的逻辑结构
对于任何一个文件,
（ 1）文件的逻辑结构 (File Logical Structure)。
(2) 文件的物理结构,又称为文件的存储结构,是指文
件在外存上的存储组织形式。
第六章 文件管理
6.2.1 文件逻辑结构的类型
1,有结构文件
(1) 定长记录。
(2) 变长记录。
(1) 顺序文件。
(2) 索引文件。
(3) 索引顺序文件。
第六章 文件管理
2,无结构文件
如果说大量的数据结构和数据库, 是采用有结构的文
件形式的话, 则大量的源程序, 可执行文件, 库函数等,
所采用的就是无结构的文件形式, 即流式文件 。 其长度以
字节为单位 。 对流式文件的访问, 则是采用读写指针来指
出下一个要访问的字符 。 可以把流式文件看作是记录式文
件的一个特例 。 在 UNIX系统中, 所有的文件都被看作是
流式文件；即使是有结构文件, 也被视为流式文件；系统
不对文件进行格式处理 。
第六章 文件管理
6.2.2 顺序文件
1,逻辑记录的排序
第一种是串结构, 各记录之间的顺序与关键字无关 。
通常的办法是由时间来决定, 即按存入时间的先后排列,
最先存入的记录作为第一个记录, 其次存入的为第二个记
录, …… 依此类推 。
第二种情况是顺序结构, 指文件中的所有记录按关键
字 (词 )排列 。 可以按关键词的长短从小到大排序, 也可以
从大到小排序；或按其英文字母顺序排序 。
第六章 文件管理
2,对顺序文件 (Sequential File)的读 /
R
0
R
1
R
2
R
3
?
R
i
?
L
L
L
L
L
L
2L
3L
4L
L
(i ＋ 1 ) L
R p t r
( a ) 定长记录文件
L
0
R
0
L
1
R
1
?
R
i
?
W p t r
( b ) 变 长记录文件
L
i
0 0
L
0
L
0
＋ 1
L
1
L
0
＋ L
1
＋ 2
L
i
∑(L
k
＋ 1)
i － 1
k ＝ 0
∑(L
k
＋ 1)
i
k ＝ 0
图 6-3 定长和变长记录文件
第六章 文件管理
3,
顺序文件的最佳应用场合, 是在对诸记录进行批量存取时,
即每次要读或写一大批记录 。 此时, 对顺序文件的存取效率是
所有逻辑文件中最高的；此外, 也只有顺序文件才能存储在磁
带上, 并能有效地工作 。
在交互应用的场合, 如果用户 (程序 )要求查找或修改单个记
录, 为此系统便要去逐个地查找诸记录 。 这时, 顺序文件所表
现出来的性能就可能很差, 尤其是当文件较大时, 情况更为严
重 。 例如, 有一个含有 104个记录的顺序文件, 如果对它采用顺
序查找法去查找一个指定的记录, 则平均需要查找 5× 103个记
录； 如果是可变长记录的顺序文件, 则为查找一个记录所需付
出的开销将更大, 这就限制了顺序文件的长度 。
第六章 文件管理
顺序文件的另一个缺点是, 如果想增加或删除一个
记录, 都比较困难 。 为了解决这一问题, 可以为顺序
文件配置一个运行记录文件 (Log File)或称为事务文件
(Transaction File),把试图增加, 删除或修改的信息记
录于其中, 规定每隔一定时间, 例如 4小时, 将运行记
录文件与原来的主文件加以合并, 产生一个按关键字排
序的新文件 。
第六章 文件管理
6.2.3 索引文件
对于定长记录文件, 如果要查找第 i个记录, 可直接根
据下式计算来获得第 i个记录相对于第一个记录首址的地址：
Ai=i× L
然而，对于可变长度记录的文件，要查找其第 i个记录
时，须首先计算出该记录的首地址。为此，须顺序地查找
每个记录，从中获得相应记录的长度 Li，然后才能按下式计
算出第 i个记录的首址。假定在每个记录前用一个字节指明
该记录的长度，则
?
?
?
??
1
0
i
i
ii iLA
第六章 文件管理
索引号
0
长度 m 指针 p t r
m
0
1 m
1
…
i m
i
…
索引表
R
0
R
1
…
R
i
…
逻辑文件
图 6-4 索引文件的组织
第六章 文件管理
6.2.4 索引顺序文件
键
A n Q i
B a o R o n g
C h e n Li n
逻辑地址 姓 名
A n Q i
A n K a n g
其它属性
B a o R o n g
?
逻辑文件
图 6-5 索引顺序文件
第六章 文件管理
6.2.5 直接文件和哈希文件
1,直接文件
对于直接文件, 则可根据给定的记录键值, 直接获得指
定记录的物理地址 。 换言之, 记录键值本身就决定了记录的
物理地址 。 这种由记录键值到记录物理地址的转换被称为键
值转换 (Key to address transformation)。 组织直接文件的关键,
在于用什么方法进行从记录值到物理地址的转换 。
第六章 文件管理
2,哈希 (Hash)文件
图 6-6 Hash文件的逻辑结构
f
H a s h 函数
目录表
键值
第六章 文件管理
6.3 外存分配方式
6.3.1 连续分配
1 2 3
0
5 6
7
4
9 10 11
8
13 14
15
12
17 18 19
16
21 22 23
20
25 26 27
24
l i s t
29 30 31
28
m a i l
c o u n t
f i l e s t a r t l e n g t h
c o u n t 0 2
tr 14 3
m a i l 19 6
l i s t 28 4
f 6 2
目录
tr
f
图 6-7 磁盘空间的连续分配
第六章 文件管理
2,连续分配的主要优缺点
(1) 顺序访问容易。
(2) 顺序访问速度快。
(1) 要求有连续的存储空间。
(2) 必须事先知道文件的长度。
第六章 文件管理
6.3.2 链接分配
1,隐式链接
图 6-8 磁盘空间的链接式分配
25
1 2 3
0
5 6 7
4
9
10
11
8
13 14 15
12
17 18 19
16
21 22 23
20
25
26
27
24
29 30 31
28
f i l e s t a r t e n d
j e e p 9 25
目录
10
1
- 1
16
第六章 文件管理
2,显式链接
图 6-9 显式链接结构
0
1
2
3
4
5
物理 块号
2
F C B F A T
0
4
5
1
第六章 文件管理
6
E O F
11
10
5
E O F
0
1
2
3
4
5
6
7
8
9
F A TF C B A
4
F C B B
9
图
6-
10MS
-DOS
的
文
件
物
理
结
构
第六章 文件管理
6.3.3 索引分配
1.
链接分配方式虽然解决了连续分配方式所存在的问题,
但又出现了另外两个问题,
(1) 不能支持高效的直接存取 。 要对一个较大的文件进
行直接存取, 须首先在 FAT中顺序地查找许多盘块号 。
(2) FAT需占用较大的内存空间。
第六章 文件管理
图 6-11 索引分配方式
1 2
3
0
5 6 7
4
9
10
11
8
13 14 15
12
17 18
19
16
21
22
23
20
25
26
27
24
29 30
31
28
c o u n t
f i l e 块序 号
j e e p 19
目录
9
16
1
10
25
－ 1
－ 1
－ 1
19
第六章 文件管理
2,多级索引分配
0
1
2
…
…
…
…
…
1 0 5
1 0 6
2 5 4
3 5 6
3 5 7
9 8 5
1 0 5
1 0 6
2 5 4
7 4 0
3 5 6
3 5 7
…
1 1 2 5
9 8 5
3 6 0
7 4 0
…
1 1 2 5
…
主索引
3 6 0
第二级索引
磁盘空间
图
6-
12
两
级
索
引
分
配
第六章 文件管理
图 6-13 混合索引方式
m o d e
o w n e r s ( 2 )
t i m e s t a m p s ( 3 )
s i z e
b l o c k c o u n t
i, a d d r ( 0 )
i, a d d r ( 1 )
d i r e c t b l o c k s
s i n g l e i n d i r e c t
d o u b l e i n d i r e c t
t r i p l e i n d i r e c t
d a t a
d a t a
d a t a
d a t a
…
…
d a t a
d a t a
…
…
…
d a t a
d a t a
d a t a
d a t a
第六章 文件管理
(1) 直接地址 。
为了提高对文件的检索速度, 在索引结点中可设置 10
个直接地址项, 即用 iaddr(0)~iaddr(9)来存放直接地址 。
换言之, 在这里的每项中所存放的是该文件数据的盘块的
盘块号 。 假如每个盘块的大小为 4 KB,当文件不大于 40
KB时, 便可直接从索引结点中读出该文件的全部盘块号 。
第六章 文件管理
(2) 一次间接地址 。
对于大, 中型文件, 只采用直接地址是不现实的 。
为此, 可再利用索引结点中的地址项 iaddr(10)来提供一
次间接地址 。 这种方式的实质就是一级索引分配方式 。
图中的一次间址块也就是索引块, 系统将分配给文件的
多个盘块号记入其中 。 在一次间址块中可存放 1K个盘块
号, 因而允许文件长达 4 MB。
第六章 文件管理
(3) 多次间接地址 。
当文件长度大于 4 MB+40 KB时 (一次间址与 10个直接
地址项 ),系统还须采用二次间址分配方式 。 这时, 用地
址项 iaddr(11)提供二次间接地址 。 该方式的实质是两级索
引分配方式 。 系统此时是在二次间址块中记入所有一次间
址块的盘号 。 在采用二次间址方式时, 文件最大长度可达
4 GB。 同理, 地址项 iaddr(12)作为三次间接地址, 其所允
许的文件最大长度可达 4 TB。
第六章 文件管理
6.4 目 录 管 理
(1) 实现“按名存取”。
(2) 提高对目录的检索速度。
(3) 文件共享。
(4) 允许文件重名。
第六章 文件管理
6.4.1 文件控制块和索引结点
1,文件控制块
(1) 基本信息类
① 文件名 ； ② 文件物理位置 ； ③ 文件逻辑结构 ；
④ 文件的物理结构
(2) 存取控制信息类
(3) 使用信息类
图 6-14 MS-DOS的文件控制块
文
件
名
扩
展
名
属
性
备
用
时
间
日
期
第
一
块
号
盘
块
数
第六章 文件管理
2,索引结点
1) 索引结点的引入
图 6-15 UNIX的文件目录
文件名 索引结点编号
文件名 1
文件名 2
… …
第六章 文件管理
2) 磁盘索引结点
(1) 文件主标识符
(2) 文件类型
(3) 文件存取权限
(4) 文件物理地址
(5) 文件长度
(6) 文件连接计数
(7) 文件存取时间
第六章 文件管理
3) 内存索引结点
(1) 索引结点编号。
(2) 状态。 指示 i
(3) 访问计数。 每当有一进程要访问此 i结点时,将该访问
计数加 1,访问完再减 1
(4)
(5) 链接指针。 设置有分别指向空闲链表和散列队列的指针。
第六章 文件管理
6.4.2 目录结构
1,单级目录结构
文件名 物理地址 文件说明 状态位
文件名 1
文件名 2
…
图 6-16 单级目录
第六章 文件管理
单级目录的优点是简单且能实现目录管理的基本功
能 ——按名存取,
(1) 查找速度慢
(2) 不允许重名
(3) 不便于实现文件共享
第六章 文件管理
2,两级目录
图 6-17 两级目录结构
用户名
W a n g
Z h a n g
G a o
指向子目录指针
W a n g 用户目录
A l p h a
T e s t
A l p h a
T e s t
R e p o r t
T e s t
Z h a n g 用户目录
R e p o r t
T e s t
G a o 用户目录
B e t a
D e v i c e
M i s x
B e t a
D e v i c e
M i s x
第六章 文件管理
(1) 提高了检索目录的速度
(2) 在不同的用户目录中,可以使用相同的文件名。
(3) 不同用户还可使用不同的文件名来访问系统中的同一
个共享文件
第六章 文件管理
3,多级目录结构
(1) 目录结构
图 6-18 多级目录结构
A B C
F E D
1
3A B D2 G A4
A C5
6 7
10 11
J N K12 J M K13 A H F14
15 16
b
17 18 19 20 21
a
8 9
第六章 文件管理
(2) 路径名 。
在树形目录结构中, 从根目录到任何数据文件, 都只
有一条惟一的通路 。 在该路径上从树的根 (即主目录 )开始,
把全部目录文件名与数据文件名, 依次地用, /”连接起来,
即构成该数据文件的路径名 (path name)。 系统中的每一个
文件都有惟一的路径名 。 例如, 在图 6-18 中用户 B为访问
文件 J,应使用其路径名 /B/F/J来访问 。
第六章 文件管理
(3) 当前目录 (Current Directory)。
当一个文件系统含有许多级时, 每访问一个文件, 都要
使用从树根开始直到树叶 (数据文件 )为止的, 包括各中间结
点 (目录 )名的全路径名 。 这是相当麻烦的事, 同时由于一个
进程运行时所访问的文件, 大多仅局限于某个范围, 因而非
常不便 。 基于这一点, 可为每个进程设置一个, 当前目录,,
又称为, 工作目录, 。 进程对各文件的访问都相对于, 当前
目录, 而进行 。 此时各文件所使用的路径名, 只需从当前目
录开始, 逐级经过中间的目录文件, 最后到达要访问的数据
文件 。 把这一路径上的全部目录文件名与数据文件名用, /”
连接形成路径名, 如用户 B的当前目录是 F,则此时文件 J的相
对路径名仅是 J本身 。 这样, 把从当前目录开始直到数据文
件为止所构成的路径名, 称为相对路径名 (relative path name)；
而把从树根开始的路径名称为绝对路径名 (absolute path name)。
第六章 文件管理
4,增加和删除目录
(1) 不删除非空目录 。 当目录 (文件 )不空时, 不能将其删
除, 而为了删除一个非空目录, 必须先删除目录中的所有文
件, 使之先成为空目录, 后再予以删除 。 如果目录中还包含
有子目录, 还必须采取递归调用方式来将其删除, 在 MS-
DOS中就是采用这种删除方式 。
(2) 可删除非空目录 。 当要删除一目录时, 如果在该目
录中还包含有文件, 则目录中的所有文件和子目录也同时被
删除 。
第六章 文件管理
6.4.3 目录查询技术
1,线性检索法
图 6-19 查找 /usr/ast/mbox的步骤
第六章 文件管理
2,Hash方法
一种处理此, 冲突,
(1) 在利用 Hash法索引查找目录时, 如果目录表中相应的
目录项是空的, 则表示系统中并无指定文件 。
(2) 如果目录项中的文件名与指定文件名相匹配, 则表
示该目录项正是所要寻找的文件所对应的目录项, 故而可从
中找到该文件所在的物理地址 。
(3) 如果在目录表的相应目录项中的文件名与指定文件
名并不匹配, 则表示发生了, 冲突,, 此时须将其 Hash值再
加上一个常数 (该常数应与目录的长度值互质 ),形成新的索
引值, 再返回到第一步重新开始查找 。
第六章 文件管理
6.5 文件存储空间的管理
6.5.1 空闲表法和空闲链表法
1,空闲表法
图 6-20 空闲盘块表
序号 第一空闲盘块号 空闲盘块数
1 2 4
2 9 3
3 15 5
4 — —
第六章 文件管理
(2) 存储空间的分配与回收 。
空闲盘区的分配与内存的动态分配类似, 同样是采用
首次适应算法, 循环首次适应算法等 。 例如, 在系统为某
新创建的文件分配空闲盘块时, 先顺序地检索空闲表的各
表项, 直至找到第一个其大小能满足要求的空闲区, 再将
该盘区分配给用户 (进程 ),同时修改空闲表 。 系统在对用
户所释放的存储空间进行回收时, 也采取类似于内存回收
的方法, 即要考虑回收区是否与空闲表中插入点的前区和
后区相邻接, 对相邻接者应予以合并 。
第六章 文件管理
2,空闲链表法
(1) 空闲盘块链。
(2) 空闲盘区链
第六章 文件管理
6.5.2 位示图法
1,位示图
图 6-21 位示图
第六章 文件管理
2,盘块的分配
(1) 顺序扫描位示图, 从中找出一个或一组其值为, 0”
的二进制位 (“0”表示空闲时 )。
(2) 将所找到的一个或一组二进制位,转换成与之相应
的盘块号。假定找到的其值为, 0”的二进制位，位于位示
的第 i行、第 j列，则其相应的盘块号应按下式计算：
b=n(i-1)+j
式中, n代表每行的位数 。
(3) 修改位示图,令 map［ i,j］ =1。
第六章 文件管理
3,盘块的回收
(1) 将回收盘块的盘块号转换成位示图中的行号和列
号 。
i=(b-1)DIV n+1
j=(b-1)MOD n+1
(2) 修改位示图。 令 map ［ i,j］ =1。
第六章 文件管理
6.5.3 成组链接法
1,
1 0 0
4 0 0
3 9 9
3 0 1
3 0 0
1 0 0
3 0 0
2 9 9
…
2 0 2
2 0 1
2 9 9
…
1 0 0
4 0 0
3 9 9
…
2 0 1 3 0 1
…
…
…
99
0
7 9 9 9
7 9 0 1
7 9 0 0
7 8 9 9
…
7 8 0 1
7 9 9 9
…
7 9 0 1
空闲盘块号
栈
S, f r e e
0
1
98
99
图
6-
22
空
闲
盘
块
的
成
组
链
接
法
第六章 文件管理
2.
当系统要为用户分配文件所需的盘块时, 须调用盘块分
配过程来完成 。 该过程首先检查空闲盘块号栈是否上锁, 如
未上锁, 便从栈顶取出一空闲盘块号, 将与之对应的盘块分
配给用户, 然后将栈顶指针下移一格 。 若该盘块号已是栈底,
即 S.free(0),这是当前栈中最后一个可分配的盘块号 。 由于
在该盘块号所对应的盘块中记有下一组可用的盘块号, 因此,
须调用磁盘读过程, 将栈底盘块号所对应盘块的内容读入栈
中, 作为新的盘块号栈的内容, 并把原栈底对应的盘块分配
出去 (其中的有用数据已读入栈中 )。 然后, 再分配一相应的
缓冲区 (作为该盘块的缓冲区 )。 最后, 把栈中的空闲盘块数
减 1并返回 。
第六章 文件管理
在系统回收空闲盘块时, 须调用盘块回收过程进行回
收 。 它是将回收盘块的盘块号记入空闲盘块号栈的顶部,
并执行空闲盘块数加 1操作 。 当栈中空闲盘块号数目已达
100时, 表示栈已满, 便将现有栈中的 100个盘块号, 记入
新回收的盘块中, 再将其盘块号作为新栈底 。
第六章 文件管理
6.6 文件共享与文件保护
A
A
B
B B B
B C
C
C
C
C
根目录
C CC
图 6-23 包含有共享文件的文件系统
第六章 文件管理
图 6-24 基于索引结点的共享方式
W a n g 用户文件目录
T e s t r
L e e 用户文件目录
T e s t r
c o u n t ＝ 2
文件物理地址
索引结点
T e s t
第六章 文件管理
图 6-25 进程 B链接前后的情况
C 的目录
o w n e r ＝ c
c o u n t ＝ 1
链接前
C 的目录
o w n e r ＝ c
c o u n t ＝ 2
建立链接后
B 的目录 B 的目录
o w n e r ＝ c
c o u n t ＝ 1
拥有者删除文件后
第六章 文件管理
6.6.2 利用符号链实现文件共享
在利用符号链方式实现文件共享时, 只是文件主才拥有
指向其索引结点的指针；而共享该文件的其他用户, 则只有
该文件的路径名, 并不拥有指向其索引结点的指针 。 这样,
也就不会发生在文件主删除一共享文件后留下一悬空指针的
情况 。 当文件的拥有者把一个共享文件删除后, 其他用户
试图通过符号链去访问一个已被删除的共享文件时, 会因系
统找不到该文件而使访问失败, 于是再将符号链删除, 此时
不会产生任何影响 。
第六章 文件管理
6.6.3 磁盘容错技术
(1) 通过存取控制机制来防止由人为因素所造成的文件
不安全性 。
(2) 通过磁盘容错技术, 来防止由磁盘部分的故障所造
成的文件不安全性 。
(3) 通过“后备系统”来防止由自然因素所造成的不安
全性。
第六章 文件管理
1,第一级容错技术 SFT-Ⅰ
1)
在磁盘上存放的文件目录和文件分配表 FAT,是文件
管理所用的重要数据结构 。 如果这些表格被破坏, 将导致
磁盘上的部分或全部文件成为不可访问的, 因而也就等效
于文件的丢失 。 为了防止这类情况发生, 可在不同的磁盘
上或在磁盘的不同区域中, 分别建立 (双份 )目录表和 FAT。
其中, 一份被称为主目录及主 FAT； 把另一份称为备份目
录及备份 FAT。
第六章 文件管理
2) 热修复重定向和写后读校验
(1) 热修复重定向 (Hot-Redirection)。
(2) 写后读校验 (Read after write Verification)方式。
第六章 文件管理
2,第二级容错技术 SFT-Ⅱ
(1) 磁盘镜像 (Disk Mirroring)。
磁
盘
控
制
器
主
机
通道
磁盘驱动器
图 6-26 磁盘镜像示意
第六章 文件管理
(2) 磁盘双工 (Disk Duplexing)。
图 6-27 磁盘双工示意
主
机
磁盘
控制器
磁盘
控制器
通道
通道
磁盘驱动器
第六章 文件管理
6.7 数据一致性控制
6.7.1 事务
1,事务的定义
事务是用于访问和修改各种数据项的一个程序单位 。 事
务也可以被看作是一系列相关读和写操作 。 被访问的数据可以
分散地存放在同一文件的不同记录中, 也可放在多个文件中 。
只有对分布在不同位置的同一数据所进行的读和写 (含修改 )操
作全部完成时, 才能再以托付操作 (Commit Operation)来终止
事务 。 只要有一个读, 写或修改操作失败, 便须执行夭折操
作 (Abort Operation)。 读或写操作的失败可能是由于逻辑错误,
也可能是系统故障所导致的 。
第六章 文件管理
2,事务记录 (Transaction Record)
·事务名：
·数据项名：
·旧值：
·新值,修改后数据项将具有的值。
第六章 文件管理
3,恢复算法
(1) undo〈 Ti〉 。 该过程把所有被事务 Ti修改过的数据,
恢复为修改前的值 。
(2) redo〈 Ti〉 。 该过程能把所有被事务 Ti修改过的数据,
设置为新值 。
如果系统发生故障,系统应对以前所发生的事务进行
清理。
第六章 文件管理
6.7.2 检查点
1,检查点 (Check Points)的作用
引入检查点的主要目的, 是使对事务记录表中事务记
录的清理工作经常化, 即每隔一定时间便做一次下述工作：
首先是将驻留在易失性存储器 (内存 )中的当前事务记录表中
的所有记录, 输出到稳定存储器中；其次是将驻留在易失
性存储器中的所有已修改数据, 输出到稳定存储器中；然
后是将事务记录表中的 〈 检查点 〉 记录, 输出到稳定存储
器中； 最后是每当出现一个 〈 检查点 〉 记录时, 系统便执
行上小节所介绍的恢复操作, 利用 redo和 undo过程实现恢复
功能 。
第六章 文件管理
2,新的恢复算法
恢复例程首先查找事务记录表, 确定在最近检查点以前
开始执行的最后的事务 Ti。 在找到这样的事务后, 再返回去
搜索事务记录表, 便可找到第一个检查点记录, 恢复例程便
从该检查点开始, 返回搜索各个事务的记录, 并利用 redo和
undo过程对它们进行处理 。
如果把所有在事务 Ti以后开始执行的事务表示为事务集 T，
则新的恢复操作要求是：对所有在 T中的事务 TK,如果在事务
记录表中出现了 〈 TK托付 〉 记录, 则执行 redo〈 TK〉 操作；
反之, 如果在事务记录表中并未出现 〈 TK托付 〉 记录, 则执
行 undo〈 TK〉 操作 。
第六章 文件管理
6.7.3 并发控制
1,利用互斥锁实现“顺序性”
2,利用互斥锁和共享锁实现顺序性
第六章 文件管理
6.7.4 重复数据的数据一致性问题
1,重复文件的一致性
图 6-28 UNIX类型的目录
第六章 文件管理
2,盘块号一致性的检查
图 6-29 检查盘块号一致性情况
第六章 文件管理
图 6-29 检查盘块号一致性情况
第六章 文件管理
3,链接数一致性检查
为每个盘块建立一个表项, 其中含有该索引结点号的计
数值 。 在进行检查时, 从根目录开始查找, 每当在目录中遇
到该索引结点号时, 便在该计数器表中相应文件的表项上加
1。 当把所有目录都检查完后, 便可将该计数器表中每个表
项中的索引结点号计数值与该文件索引结点中的链接计数
count值加以比较, 如果两者一致, 表示是正确的；否则,
便是发生了链接数据不一致的错误 。
第六章 文件管理
如果索引结点中的链接计数 count值大于计数器表中相应索
引结点号的计数值, 则即使在所有共享此文件的用户都不再使
用此文件时, 其 count值仍不为 0,因而该文件不会被删除 。 这
种错误的后果是使一些已无用户需要的文件仍驻留在磁盘上,
浪费了存储空间 。 解决的方法是用计数器表中的正确的计数值
去为 count重新赋值 。
反之, 如果出现 count值小于计数器表中索引结点号计数值
的情况时, 就有潜在的危险 。 假如有两个用户共享一个文件,
但是 count值仍为 1,这样, 只要其中有一个用户不再需要此文
件时, count值就会减为 0,从而使系统将此文件删除, 并释放
其索引结点及文件所占用的盘块, 导致另一共享此文件的用户
所对应的目录项, 指向了一个空索引结点, 最终是使该用户再
无法访问此文件 。 如果该索引结点很快又被分配给其它文件,
则又会带来潜在的危险 。 解决的方法是将 count值置为正确值 。
