操作系统(2)复习 第八章 磁盘存储器的管理
第八章 磁盘存储器的管理
1.外存的组织方式
(1)连续组织方式
(2)链接组织方式
(3)索引组织方式
连续组织方式
又称连续分配方式,要求为每一个文件分配一组相邻接的盘块。
把逻辑文件中的记录顺序地存储到邻接的各物理盘块中。
优点:
- (1) 顺序访问容易
- (2) 顺序访问速度快。
缺点:
- (1) 要求为一个文件分配连续的存储空间。
- (2) 必须事先知道文件的长度。
- (3) 不能灵活地删除和插入记录。
- (4) 无法实现动态增长文件。
链接组织方式
1.隐式连接
在文件目录的每个目录项中,都须含有指向链接文件第一个盘块和最后一个盘块的指针。
主要问题:只适合顺序访问,它对随机访问是及其低效的。
2.显式连接
把用于链接文件各物理块的指针显式地存放在内存的一张链接表中。该表称为文件分配表FAT
索引组织方式
1.单级索引组织方式
- 优点:支持直接访问
- 缺点:对于小文件,其索引块的利用率极低。
2.多级索引组织方式
- 若文件较大,存放索引表也需要多个盘块(索引盘块)。
- 索引盘块亦需要按顺序管理起来
若索引盘块数量较少用指针链接的方式即可;
若索引盘块较多,需对索引盘块也采用索引方式管理,形成多级索引。
多级索引下的文件大小:
- 若两级索引,盘块1KB,盘块号占4字节
一个盘块可存放的盘块号数有多少个
1KB/4B =(2^10)/4 = 2^8 = 256(个)
二级索引下的****文件可分配的最大盘块数
256 * 256 =(2^6) × (2^10)=64 K(个)
文件最大长度为
64K(个)*1KB=64MB - 若盘块大小为4KB,单级索引允许文件最大长度为4MB(4K/4* 4KB),二级索引则文件最大可达4GB(1K* 1K* 4KB)。
3.混合组织索引(增量式索引组织方式)
2.存储空间的管理
空闲表法
- 系统为外存上的所有空闲区建立一张空闲表
每个空闲区对应一个空闲表项
(表项包括序号、空闲区的第一个盘块号、空闲盘块数等。)
将所有空闲区按其起始盘块号递增的次序排列,如图。
属于连续分配方式,空闲盘区的分配与内存的分区(动态)分配类似,同样是采用首次适应算法和最佳适应算法等,它们对存储空间的利用率大体相当,都优于最坏适应算法。
空闲链表法
1.空闲盘块链:
- 将磁盘上的所有空闲空间,以盘块为单位拉成一条链。
因创建文件而请求分配空间时,系统从链首依次摘下适当数目的空闲盘块分配给用户。
因删除文件而释放存储空间时,系统将回收的盘块依次插入空闲盘块链的末尾。 - 分配和回收一个盘块的过程非常简单,但为一个文件分配盘块时,可能要重复操作多次。分配回收简单。链表长,大量分配时需要操作的指针多
2.空闲盘区链:
- 所有空闲盘区拉成一条链。每个盘区(可包含若干盘块)上含有:
指示下一空闲盘区的指针、本盘区大小等信息 - 分配通常采用首次适应算法。回收盘区时,将回收区与相邻的空闲盘区相合并。
为提高检索速度,可以采用显式方法,为空闲盘区建立一张链表放在内存中。 - 分配、回收操作涉及的链式数据结构的处理方便
链表长度不定,分配时操作的指针数量相对较少,但分配回收操作相对复杂。
位示图法
利用二进制的一位来表示一个盘块的使用情况。
值为0表示对应的盘块空闲,为1表示已分配。有的系统则相反。
磁盘上的所有盘块都有一个二进制位与之对应,这样由所有盘块所对应的位构成一个集合,称为位示图。
总块数=mn。可用mn个位数来构成位示图,可看成是二维数组(数据结构)。
盘块的回收
(1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为: i = (b - 1)DIV n + 1 j = (b - 1)MOD n + 1
(2) 修改位示图。令map[i, j] = 0。
成组链接法
大型文件系统,空闲表或空闲链表太长不方便管理操作。
UNIX系统中采用成组链接法,这是将两种方法结合而形成的一种空闲盘块管理方法。
中心思想:
所有盘块按规定大小划分为组;
组间建立链接;
组内的盘块借助一个系统栈可快速处理,且支持离散分配回收。
3.提高磁盘I/O速度
- 磁盘高速缓存
- 提前读
- 延迟写
- 优化物理块的分布
- 虚拟盘
4.廉价磁盘冗余阵列(RAID)
利用一台磁盘阵列控制器来管理和控制一组(几台到几十台)磁盘驱动器,组成一个大型磁盘系统。
- 大幅度增加了磁盘容量。
- 极大地提高了磁盘I/O速度和整个磁盘系统的可靠性
并行交叉存取
RAID的分级
- 0级 仅提供并行交叉存取
- 1级 具有磁盘镜像功能
- 3级 具有并行传输功能的磁盘阵列
- 5级 具有独立传送功能的磁盘阵列
- 6级和7级 设置了异步校验盘
RAID优点
- 可靠性高
- 磁盘I/O速度高
- 性价比高
5.提高磁盘可靠性的技术
第一级容错技术 STF-Ⅰ
- 双份目录和双份文件分配表
- 热修复重定向和写后读检验
第二级容错技术 STF-Ⅱ
- 磁盘镜像
- 磁盘双工