李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第 22 讲 磁盘存储器的管理(1) 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/

教学目标与内容 教学目标 教学内容 理解外存的组织形式 理解文件存储空间管理 了解提高磁盘I/O速度的途径 外存的组织形式 文件存储空间管理 计算机科学与技术系 信息与教育技术中心 2/

复习 文件目录 文件共享方式 3/

外存的组织形式 外存分配考虑的因素 有效利用外存空间 提高文件的访问速度 外存分配方式 连续分配 链接分配 索引分配 4/

连续分配 要求为每一个文件分配一组相邻接的盘块。 图 8-1 磁盘空间的连续分配 5/ 5/

连续分配的主要优缺点 连续分配的主要优点如下： 连续分配的主要缺点如下： 顺序访问容易。 顺序访问速度快。 要求有连续的存储空间。 必须事先知道文件的长度。 不能灵活地删除和插入记录 6/ 6/

链接分配 通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表。 隐式链接 图 8-2 磁盘空间的链接式分配 7/

隐式链接分配问题 指针需要占用存储空间 适合于顺序访问，随机访问效率低 可靠性较差 引入“簇”的概念 8/ 8/

显式链接 图 8-3 显式链接结构 9/ 9/

FAT12为例 以盘块为基本分配单元 图 8-4 MS-DOS的文件物理结构 10/ 10/

对于1.2MB的软盘，设每个盘块大小为512字节，FAT表中的每一项为12位，则FAT表能够访问的最大分区空间为多少？FAT表自身需要占用多大的存储空间？ 11/ 11/

索引分配 单级索引分配 链接分配方式虽然解决了连续分配方式所存在的问题， 但又出现了另外两个问题， 即： 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。 FAT需占用较大的内存空间。 12/ 12/

不足之处 花费较多的外存空间 小文件，索引块利用率低 图 8-6 索引分配方式 13/ 13/

多级索引分配 图 8-7 两级索引分配 14/ 14/

文件存储空间的管理 空闲表法和空闲链表法 空闲表法  图 8-9 空闲盘块表  序号 第一空闲盘块号 空闲盘块数 1 2 4 9 3 15 5 — 图 8-9 空闲盘块表 15/

文件存储空间的管理 存储空间的分配与回收 空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项， 直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法， 即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。 16/

文件存储空间的管理 空闲表法和空闲链表法 空闲链表法  空闲盘块链 空闲盘区链 17/

文件存储空间的管理 位示图法 位示图  图 8-10 位示图 18/

文件存储空间的管理 位示图法 盘块的分配 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+j 式中， n代表每行的位数。 修改位示图， 令map［i,j］=1。 19/

文件存储空间的管理 位示图法 盘块的回收 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为： i=(b-1)DIV n+1 j=(b-1)MOD n+1 修改位示图。 令map ［i,j］=0。  20/

文件存储空间的管理 成组链接法 空闲盘块的组织 图 8-11 空闲盘块的成组链接法

文件存储空间的管理 成组链接法 空闲盘块的分配与回收 当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底， 即S.free(0)，这是当前栈中最后一个可分配的盘块号。 22/

文件存储空间的管理 由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。 然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。 23/

在系统回收空闲盘块时，须调用盘块回收过程进行回 收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执 行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时， 表 示栈已满，便将现有栈中的100个盘块号， 记入新回收的盘块 中，再将其盘块号作为新栈底。 24/

提高磁盘I/O速度的途径 磁盘高速缓存 是指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高速缓存是一组在逻辑上属于磁盘， 而物理上是驻留在内存中的盘块。 高速缓存在内存中可分成两种形式。第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。 25/

磁盘高速缓存(Disk Cache) 数据交付方式 系统可以采取两种方式， 将数据交付给请求进程： 数据交付。这是直接将高速缓存中的数据， 传送到请求者进程的内存工作区中。 指针交付。只将指向高速缓存中某区域的指针， 交付给请求者进程。 后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存存储空间到进程的内存工作区的时 26/ 26/

置换算法 由于请求调页中的联想存储器与高速缓存(磁盘I/O中)的工作情况不同，因而使得在置换算法中所应考虑的问题也有所差异。因此，现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外， 还考虑了以下几点 访问频率。 可预见性。 数据的一致性。

周期性地写回磁盘 在UNIX系统中专门增设了一个修改(update)程序， 使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30 s。这样，因系统故障所造成的工作损失不会超过30 s的劳动量。而在MS-DOS中所采用的方法是：只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”(write-through cache)。 MS-DOS所采用的写回方式，几乎不会造成数据的丢失， 但须频繁地启动磁盘。

提高磁盘I/O速度的其它方法 提前读(Read-Ahead) 延迟写 优化物理块的分布 虚拟盘

廉价磁盘冗余阵列 并行交叉存取 图 8-12 磁盘并行交叉存取方式 30/

RAID的分级 RAID 0级。 RAID 1级。 RAID 3级。 RAID 5级。 RAID 6级和RAID 7级。 31/

RAID的优点 可靠性高。 磁盘I/O速度高。 性能/价格比高

作业 P247 21-26 33/