osch8磁盘存储器管理

29
8.2 文件存储空间的管理
实现文件系统的关键问题是记录各个文件分别 用到了哪些磁盘块。
为文件分配外存空间时所要考虑的主要问题：

(1) 有效地利用外存空间。

(2) 提高对文件的访问速率。
30
8.2 文件存储空间的管理
文件存储空间管理的方法： –空闲块表 –空闲块链 –位示图 –成组链接法
…
…
…
…
…
磁盘 空间 0 1 2
10 5 10 6
25 4
35 6 35 7
98 5
24
(3) 混合索引方式（增量索引组织方式）
UNIX系统采用多级间接索引结构，对小型 文件采用直接索引，对大型文件采用间接 索引，既保证绝大多数的文件有高的存取 效率，又能适应存取一些大型文件。
25
mod e
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
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系统中每个子文件系统（一片软盘、
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.顺序存取效率高，随机存取效率太低，如 果访问文件的最后的内容，实际上是要访问 整个文件。
0
108
1
210
…
…
126
123
127
136
…
0
165
1
169
…
…
126
233
127
289
…
…
…
…
块号 108# 210#
136#
165# 169#
289#
23
…
…
主索 引 36 0 74 0
11 25
…
第二 级索引 36 0 10 5 10 6 25 4
74 0 35 6 35 7
11 25
98 5
第1道第3块中的信息读至内存缓冲区 根据500,将缓冲区中500B往后的500B内容读
统就把该命令改变成为：
READ（FCB，3，A）
（2）
命令验证合法后，系统就开始进行把对文件的读
/写请求从逻辑结构映射到物理结构的工作。
46
把逻辑记录号3转换成相应的逻辑字节地址， 即相对于该文件起点的字节数。 公式是： 逻辑字节地址=逻辑记录号*逻辑记录长度 =3*500=1500 命令（2）转换成： READ（FCB，1500，A） （3）
19
20
21 22
23
24
25
26
27
28 29 30
31
目录
fil e
块 序号
jeep
19
9
16
1
19
10 25
－1
－1
－1
20
索引号 0 1
索 引 表 块 (18#) 26 32
…
…
103
126
58
127
108
128
210
…
…
254
111
…
…
…
…
块号 26# 32# 103#
108# 210# 111#
37
位示图
例：一个磁盘组共有16个柱面，每个柱面有 16个磁头寻道，每个磁道分为16个扇区，那 么整个磁盘空间的扇区数为：
16*16*16=4096（个） 如果一个扇区被定义为一个存储块，用字
长位16位的存储单元来构造位示图，共需要 256个字。
38
位示图
盘块分配：
1、扫描位示图，找到一个或一组值为0 的二进制位
文件MYFILE的FCB内容 45
2.“按名存取”的实现过程
要读文件MYFILE第3个记录，存放到数组A： A[0]，A[1]，…，A[499]中。程序里发读命令：
READ（MYFILE，3，A） （1）
文件系统通过命令中提供的文件名MYFILE查
文件目录，找到了文件MYFILE的FCB后，系

类似于存储管理中的页式
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
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
2、文件A占用硬盘的第11,12,16,14四个盘 块，文件A中各盘块链接情况如何？
17
8.1.5 索引文件
索引文件结构 文件结构的数据结构是
文件的索引表，每个文 件有一个索引表，表中 每个表目包括：逻辑块 号，物理块号。 索引表位置：文件目录 中，文件的开头等。 索引表大小:固定大小， 非固定大小。
48
把相对块号转换成物理地址:道号和块号。 公式是： 道号=相对块号/每道块数=7/4=1 块号=相对块号%每道块数=7%4=3 命令（4）转换成： READ（FCB，1，3，500，A）（5） 文件系统实现了由逻辑记录到物理记录的转换。
49
READ命令实现 申请1000B缓冲区,找到磁盘DCB,启动磁盘,把
一个硬盘的分区，一卷磁带）格式化后的结 构如图，其中特别块是存放该子文件系统的 管理信息，包括空闲块管理信息。

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
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
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里得 到该文件所在的物理地址，然后进行所需要的存 取操作。
34
（2Leabharlann Baidu空闲块链
管理块 58
58# 78
78# 98
98# 100
100# 102
102#
35
8.2.2 位示图法
位示图例 36
位示图
位示图是外存空间的存储映射图。 位示图是系统在内存中划分出的若干字节
的集合，用来指示磁盘存储情况。 位示图的大小由其对应的文件存储设备的
容量决定，当一个盘组的分块确定后，根据 划分的总块数决定位示图由多少字节组成。
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 存取控制:只读
ow ners (2)
ti me st amps (3 )
dat a
size dat a
block count
i.ad dr (0)
dat a
i.ad dr (1)
di rect b lo cks
dat a
… …
dat a
sin gl e i nd irect
dat a
double indirect
FA T
0 4
5 1
图 8-3 显式链接结构
12
8.1.3 FAT技术
FAT：文件分配表， 将一个文件离散的存储在外存上，将链接
各物理块的指针显式的登记在一张文件分 配表FAT中，FAT整个系统一张，每个表项 序号为对应物理块号，表项内容为文件下 一个物理块的指针。 文件首个物理块地址被登记在文件目录中。
当用户删除一个文件时，系统收回其文 件空间。扫描空闲区目录，找出一个空 表将其释放空间的第一个物理块号及占 用的块号数填入该表目中。
33
2.空闲块链法
空闲块链把文件存储设备上的所有空闲块连 接在一起。
当需要分配空闲块时从链首处进行，在主存 中要保存一个链首指针，指向第一个空闲块， 当释放空闲块时，把这些块挂在空闲块链尾 上。
21
例
在连续分配方式、链接分配方式、FAT 分配方式、索引分配方式中如何将文件 的字节偏移量3500转换为物理块号、块 内位移量？假设盘块大小1KB，盘块号 占4B。
22
(2) 多级索引分配
索 引 号 索 引 表 块 (36#)
0
26
1
32
…
…
126
103
127
58
…
索 引 号 索 引 表 块 (2968##))
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 链接文件
一个链接文件结构是按顺序由串联的块组成 的，即文件的信息按存储介质的物理特性存 于若干块中。
每个物理块的最末一个字(或第一个字)作为 链接字，它指出后继块的物理地址。链首指 针存放在该文件目录中。文件的结尾块的指 针为“∧”。
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占多大？
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个扇区等
31
8.2.1空闲表法
系统为所有空闲区建立一张表。对于每 个空闲区，建立一个表目。表目的内容 包括：第一空白块地址（物理块号）、 空白块个数。
序号
第一个空闲 空闲块数 块号
状态
1
18
5
可用
2
29
8
可用
3
105
19
可用
4
—
—
未用 32
1 空闲块表
当某用户提出请求分配存储空间时，系 统依次扫描该空闲区的各表目，直到找 到一个满足要求的空闲区为止。
第八章 磁盘存储器的管理
8.1 外存的组织方式 8.2 文件存储空间的管理 8.3 提高磁盘I/O速度的途径
1
8.1 外存组织方式
一个文件存储介质，格式化后就分成许多大 小相等的单位－－存储块（物理盘块）。
在现代计算机系统中，一般来说，每个物理 块是一个磁盘的扇区，512字节，并给每个存 储块有个编号，称为物理块号。