47
把逻辑字节地址转换成相对块号和块内相对字 节地址。 公式是： 相对块号=(逻辑字节地址/物理块尺寸)+相 对起始块号=(1500/1000)+6=1+6=7 块内相对字节地址=逻辑字节地址%物理块 尺寸=1500%1000=500 命令（3）转换成： READ（FCB，7，500，A） （4）
trip le in di rect
…
…
…
dat a dat a
dat a dat a
26
27
28
索引文件——相关计算
假设一个物理块大小为1KB，每个索引表项为3个 字节，则每个盘块可存放341个盘块号。
1、直接寻址的文件大小为10*1KB 2、一级间接寻址的文件大小为341*1KB 3、二级间接寻址的文件大小为341*341*1KB 4、三级间接寻址的文件大小为341*341*341*1KB
FA T
0 4
5 1
图 8-3 显式链接结构
12
8.1.3 FAT技术
FAT：文件分配表， 将一个文件离散的存储在外存上，将链接
各物理块的指针显式的登记在一张文件分 配表FAT中，FAT整个系统一张，每个表项 序号为对应物理块号，表项内容为文件下 一个物理块的指针。 文件首个物理块地址被登记在文件目录中。
28
list
29
30
31
目录
fil e start
cou nt 0
tr 14
mail 19
list 28
f
6
len gth 2 3 6 4 2
5
8.1.1 连续分配
6
8.1.2 链接文件
一个链接文件结构是按顺序由串联的块组成 的，即文件的信息按存储介质的物理特性存 于若干块中。
每个物理块的最末一个字(或第一个字)作为 链接字，它指出后继块的物理地址。链首指 针存放在该文件目录中。文件的结尾块的指 针为“∧”。
10 0
99
0
79 99
…
79 01
40 0
79 00
…
39 9
78 99
…
30 1
78 01
79 99
79 01 42
2. 空闲盘块的分配与回收
43
补充：“按名存取”的实现
“按名存取”的思想 用户访问文件时，系统根据文件名查文件目录， 找到它的FCB。经过合法性检查，从FCB里得 到该文件所在的物理地址，然后进行所需要的存 取操作。
44
扇区号：
0
1
0
1
0
MYFILE的起址
4
5
1
磁
道
号8
9
2 456
12
13
3
块内相对字节地址
2 2 逻辑字节地址
第3个记录
6
7
0123
10
11
相对块号
14
15
文件名:MYFILE 文件在辅存位置:6 (相对起始块号) 文件物理结构:连续文件 文件长度:7(逻辑记录个数) 逻辑记录尺寸:500B 文件性质:暂存 文件主:ZONG 使用者:ZONG 存取控制:只读

类似于存储管理中的页式
10
2. 显式链接(FAT)
为了克服链接文件的存取效率太低的问 题，提出文件映照的技术，把链接文件 中的链接字集中在一结构中，既保持了 链接文件的优点，也克服了其缺点。
DOS、WINDOWS系统就采用了FAT结构。
11
FCB 2
物 理 块号 0 1 2 3 4 5
不要求连续存放。 对于记录式文件一块中可包含一个逻辑记录
或多个逻辑记录，也可以若干物理块包含一 个逻辑记录。
7
8.1.2 链接文件1. 隐式链接
目录
0 4 8 12 16 1 20 24 28
1 10 2
3
5
6
7
9 16 10 25 11
13
14
15
17
18
19
21
22
23
25 -1 26
2、文件A占用硬盘的第11,12,16,14四个盘 块，文件A中各盘块链接情况如何？
17
8.1.5 索引文件
索引文件结构 文件结构的数据结构是
文件的索引表，每个文 件有一个索引表，表中 每个表目包括：逻辑块 号，物理块号。 索引表位置：文件目录 中，文件的开头等。 索引表大小:固定大小， 非固定大小。
2
8.1 外存组织方式
3
8.1外存组织方式
文件的物理结构指文件在存储介质上组 织结构，有三种基本结构： 连续文件结构 链接文件结构 索引文件结构
4
8.1.1 连续分配
cou nt
0
1
2
3
4
5
6
f 7
8
9
10
11
12
13
14
tr 15
16
17
18
19
20
mail
21 22
23
24
25
26
27
27
29
30
31
fil e start end jeep 9 25
图 8-2 磁盘空间的链接式分配 8
8.1.2 链接文件
9
8.1.2 链接文件
评价：
1.存储空间利用率高；
2.文件创建时用户不必指出文件的大小；
3.文件动态扩充和修改容易。
4.顺序存取效率高，随机存取效率太低，如 果访问文件的最后的内容，实际上是要访问 整个文件。
2、转换为相应的盘块号
i行，j列对应的盘块号

b=n*(i-1)+j
3、修改位示图 map[i,j]=1
39
位示图
盘块回收：
1、将盘块号转换为位示图中的行号和列号

i=(b-1) div n+1

j=(b-1) mod n+1
2、修改位示图
40
8.2.3 成组链接法
UNIX系统的空闲块的管理 在UNIX系统中每个子文件系统（一片软盘、
第1道第3块中的信息读至内存缓冲区 根据500,将缓冲区中500B往后的500B内容读
当用户删除一个文件时，系统收回其文 件空间。扫描空闲区目录，找出一个空 表将其释放空间的第一个物理块号及占 用的块号数填入该表目中。
33
2.空闲块链法
空闲块链把文件存储设备上的所有空闲块连 接在一起。
当需要分配空闲块时从链首处进行，在主存 中要保存一个链首指针，指向第一个空闲块， 当释放空闲块时，把这些块挂在空闲块链尾 上。
2.FAT16： FAT表项16位，簇大小为4， 8，…,64个扇区
3.FAT32： FAT表项32位，簇大小为8个扇区
15
8.1.3 FAT文件
FAT表的计算 –任给定一磁盘空间会计算FAT表的所占 空间大小
16
FAT表的计算
1、盘块大小1K，硬盘大小500M，文件照 映方式下，FAT占多大？
文件MYFILE的FCB内容 45
2.“按名存取”的实现过程
要读文件MYFILE第3个记录，存放到数组A： A[0]，A[1]，…，A[499]中。程序里发读命令：
READ（MYFILE，3，A） （1）
文件系统通过命令中提供的文件名MYFILE查
文件目录，找到了文件MYFILE的FCB后，系
18
(1) 单级索引文件方式
将多个索引表块按链接文件的方式串联起来。 例 每个索引表项占4个字节(可表示物理块号
的范围从0～232)，若物理块的大小为512字节， 则一个物理块可存放127个索引表项和一个链 接字。
19
cou nt
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 18
一个硬盘的分区，一卷磁带）格式化后的结 构如图，其中特别块是存放该子文件系统的 管理信息，包括空闲块管理信息。

41
… … … … …
1. 空闲盘块的组织
10 0
空 闲 盘块 号
40 0
栈
39 9
30 1 S.free 10 0
0 300 30 0
1 299
29 9 98 202 99 201
20 1
48
把相对块号转换成物理地址:道号和块号。 公式是： 道号=相对块号/每道块数=7/4=1 块号=相对块号%每道块数=7%4=3 命令（4）转换成： READ（FCB，1，3，500，A）（5） 文件系统实现了由逻辑记录到物理记录的转换。
49
READ命令实现 申请1000B缓冲区,找到磁盘DCB,启动磁盘,把
13
8.1.3 FAT技术
FCB A 4
FCB B 9
FA T
0
1
2
3
6
4
EOF
5
11
6
7
8
10
9
5
EOF
- MS-DOS
图 8 4
的 文 件 物 理 结 构
14
8.1.3 FAT技术——相关计算
磁盘块（扇区）大小，FAT表项大小，簇的大 小——磁盘容量
1.FAT12：FAT表项12位，簇大小为1，2，4， 8个扇区等
19
20
21 22
23
24
25
26
27
28 29 30
31
目录