1 第九章磁盘管理 磁盘调度算法 文件分配 磁盘空间的管理 RAID 操 作 系 统 | 磁 盘 管 理 2 CUIT 徐虹 9．1磁盘I/O ?磁盘性能简述 ?数据的组织：盘、磁道、柱面和扇区。 ?磁盘的类型：固定磁头和移动磁头。 ?磁盘访问时间 ?寻道时间 ?旋转延迟时间 ?传输时间 操 作 系 统 | 磁 盘 管 理 3 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 4 CUIT 徐虹 ?磁盘调度算法 ?目标：平均寻道时间最短。 操 作 系 统 | 磁 盘 管 理 5 CUIT 徐虹 ?先来先服务FCFS（First—Come First—Served） ?原理：根据进程请求访问磁盘的先后次 序进行调度。 ?特点：公平、简单。平均寻道时间长。 操 作 系 统 | 磁 盘 管 理 6 CUIT 徐虹 2 操 作 系 统 | 磁 盘 管 理 7 CUIT 徐虹 ?最短寻道时间优先SSTF（Shortest Seek Time First） ?原理：选择有距当前磁头所在磁道最近的访问 磁道的进程。 ?特点：寻道时间最短，但导致某些进程发生“饥 饿”现象。 操 作 系 统 | 磁 盘 管 理 8 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 9 CUIT 徐虹 ?扫描算法（SCAN） ?原理：选择与当前磁头移动方向一致且距离最 近的进程。 ?特点：寻道性能较好，避免了进程“饥饿”现象。 操 作 系 统 | 磁 盘 管 理 10 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 11 CUIT 徐虹 ?循环扫描算法（CSCAN） ?规定磁头单向移动。 操 作 系 统 | 磁 盘 管 理 12 CUIT 徐虹 3 操 作 系 统 | 磁 盘 管 理 13 CUIT 徐虹 ?N-Step-SCAN算法 ?“磁臂粘着”现象：磁臂停留在某处不动。 ?将磁盘请求队列分成若干个长度为N的 子队列，磁盘调度将按FCFS算法依次 处理这些子队列。而每个队列的处理是 按SCAN算法，一个处理完毕再处理下 一个队列。 ?FSCAN算法 ?N-Step-SCAN算法的简化，只分为两个 队列。 ?当前请求I/O的进程队列：SCAN算法 ?扫描期间请求的进程队列：FCFS 操 作 系 统 | 磁 盘 管 理 14 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 15 CUIT 徐虹 9．2外存分配方法 ?连续分配（顺序文件） ?分配与回收 ?分配：把一个逻辑上连续的文件信息依 次存放在物理块中。 ?回收：碎片整理问题。 ?特点 ?优点：能很快进行存取。 ?缺点：不便于记录的增，删操作，不能 动态增长，存在碎片问题。 操 作 系 统 | 磁 盘 管 理 16 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 17 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 18 CUIT 徐虹 ?链接分配（串联文件） ?隐式链接 ?在文件的目录中记录该文件的第一和最 后一个盘块的指针，每个块中的指针指 向文件的下一物理块号。 ?优点：文件可动态增长，不需指明文件 长度，便于增删记录，节约空间。 ?缺点：只适合顺序存取，不宜于直接存 取，查找效率低。由于设置链接字而破 坏了物理信息的完整。 ?改进：将几个盘块组成簇（cluster）， 以簇为单位分配。 4 操 作 系 统 | 磁 盘 管 理 19 CUIT 徐虹 ?显示链接 ?将链接文件各物理块的指针显示地放 在内存的一张链接表中。在FCB的物理 地址中填写其首指针所对应的盘块号。 ?FAT（File Allocation Table）：文件 分配表，整个磁盘设置一张，放在内存 中。 ?缺点：不能直接存取；FAT占较大内 存空间。 操 作 系 统 | 磁 盘 管 理 20 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 21 CUIT 徐虹 ?索引文件 ?要求为每一文件建立一张索引表。每 个表目指出文件逻辑记录所在的物理 块号。 ?特点：方便地进行随机存取；增加了 索引表的空间开销，增加一次访问操 作。 ?串联文件方式组织 ?多重索引方式组织 操 作 系 统 | 磁 盘 管 理 22 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 23 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 24 CUIT 徐虹 ?综合组织方式 ?把索引表的头几项设计为直接寻址方式， 存放物理块号，后几项设计成多重索引。 综合组织方式适用于顺序存取和随机存取。 ?直接地址：iaddr(0) — iaddr(9) ?一次间接地址：iaddr(10) ?二次间接地址：iaddr(11) ?三次间接地址：iaddr(12) 5 操 作 系 统 | 磁 盘 管 理 25 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 26 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 27 CUIT 徐虹 9．3 文件存储空间管理 ?系统应能自动地为用户分配存储 空间，管理系统和用户的存储空 间，实现按名存取。 ?文件存储空间的管理包括空闲块 的组织分配和回收。 操 作 系 统 | 磁 盘 管 理 28 CUIT 徐虹 ?空闲表 ?空闲表 ?把一个连续未分配区域称为“空闲文件”， 系统为所有“空闲文件”单独建立一个目 录。 ?表目内容：序号，第一个空白块号，空 白块个数。 ?空间分配和回收 操 作 系 统 | 磁 盘 管 理 29 CUIT 徐虹 ?位示图 ?为文件存储器存储空间建立一张位示 图，用以反映整个空间的分配情况。 ?简单，速度快，占一定的空间。 ?盘块号与位示图行列的转换： 操 作 系 统 | 磁 盘 管 理 30 CUIT 徐虹 ?空闲块链 ?空闲盘块链 ?分配和释放顺序：从头分配，从尾回收。 ?空闲盘区链 ?分配：首次适应算法 ?回收：拼接问题 6 操 作 系 统 | 磁 盘 管 理 31 CUIT 徐虹 ?成组链接法 ?实现方法 对所有的空白块从尾倒着向前分组，第一 组99 块，随后每组100 块，每组的块数及相 应块号记录在前一组的第一块中。最后一组 （不足100 块）的数据登记在空闲盘块栈 （卷资源表）中。第二组的0 号单元的值仍 为100 ，1 号单元值为0 （文卷卷尾标志）， 表示无空闲块可分配。 操 作 系 统 | 磁 盘 管 理 32 CUIT 徐虹 ?分配和释放 ?系统工作后，把磁盘文件卷的卷资源复制 到内存指定区域。资源表中登记空闲块号 的区域是一种栈结构。其中，记载总块数 作为该空白块栈的指针ptr。 ?分配时，ptr-1，然后取出对应项作为这次 申请得到的物理块。如此下去，直到栈底。 当ptr=0 时，续入下一组的块号及总数，并 把该块分配出去。当ptr=0，且相应此表目 中的值为0 时，表示遇到卷尾标志。 ?当回收时，先登记块号，然后ptr +1，当 填满一组后，再回收一块时，把前一组的 内容记入该块内，ptr=0，并把这一块的块 号记入相应表目中。 操 作 系 统 | 磁 盘 管 理 33 CUIT 徐虹 ?特点 ?空白块号的登记不占用额外空间。 ?绝大部分分配和释放工作都在主存进 行。 ?把总块数作为空白块栈的指针使用， 是理想的存储结构。效率高。 操 作 系 统 | 磁 盘 管 理 34 CUIT 徐虹 9.4 磁盘容错技术 磁盘容错技术SFT （System Fault Tolerance）： 通过增加冗余的磁盘驱动器、磁 盘控制器等，来提高磁盘系统的 可靠性。 操 作 系 统 | 磁 盘 管 理 35 CUIT 徐虹 ?第一级容错技术SFT-1 ?用于防止磁盘表面发生缺陷所引 起的数据丢失。 ?双份目录和双份分配表 ?主目录和主分配表 ?备份目录和备份分配表 ?热修复重定向和写后读校验 ?热修复重定向（Hot-Fix Redirection） ?写后读校验（Read after Write Verification） 操 作 系 统 | 磁 盘 管 理 36 CUIT 徐虹 ?第二级容错技术SFT-2 ?磁盘镜像（Disk Mirroring） ?磁盘双工（Disk Dupluxing 7 操 作 系 统 | 磁 盘 管 理 37 CUIT 徐虹 ?独立磁盘冗余阵列RAID （Redundant Array of Independent Disks） ?利用一台磁盘阵列控制器统一管 理和控制一组（几台到几十台）磁 盘驱动器，组成一个高度可靠的、 快速的大容量磁盘系统。 ?并行交叉存取 操 作 系 统 | 磁 盘 管 理 38 CUIT 徐虹 ?RAID的分级 ?RAID 0级：仅提供并行交叉存取。 操 作 系 统 | 磁 盘 管 理 39 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 40 CUIT 徐虹 ?RAID 1级：具有磁盘镜像功能，利用并行特 性将数据块同时写入主盘和镜像盘。 操 作 系 统 | 磁 盘 管 理 41 CUIT 徐虹 ?RAID 2级：并行访问；strip只有一个 字或字节；用Hamming码校验。 操 作 系 统 | 磁 盘 管 理 42 CUIT 徐虹 RAID 3级：具有并行传输功能的磁盘阵列。 strip只有一个字或字节；用奇偶校验。 8 操 作 系 统 | 磁 盘 管 理 43 CUIT 徐虹 RAID 4级：独立访问，strip较大，以strip 为单位进行奇偶校验。 操 作 系 统 | 磁 盘 管 理 44 CUIT 徐虹 RAID 5级：具有独立传送功能的磁盘阵列。 奇偶校验分布在不同的磁盘上。 操 作 系 统 | 磁 盘 管 理 45 CUIT 徐虹 ?RAID 6级：两种不同的奇偶校验计算， 在不同的磁盘的不同块中。 操 作 系 统 | 磁 盘 管 理 46 CUIT 徐虹 ?RAID 的优点 ?可靠性高 ?磁盘I/O速度快 ?性能/价格比高 操 作 系 统 | 磁 盘 管 理 47 CUIT 徐虹 ?后备系统 ?类型 ?复制方法 ?周期性的全量转存 ?增量转存 ?以上两种方式配合使用。 操 作 系 统 | 磁 盘 管 理 48 CUIT 徐虹 ?文件系统的恢复过程 ?从最近一次全量转存中装入全部系 统文件，使系统得以重新起动，并在 其控制下进行后续的恢复工作。 ?从近到远从增量转存盘上恢复文件。 ?从最近一次全量转存盘中，恢复没 恢复过的文件。 9 操 作 系 统 | 磁 盘 管 理 49 CUIT 徐虹 9. 6 文件系统性能的改善 ?文件访问速度 ?数据的共享性 ?文件系统使用的方便性 ?数据的安全性 ?数据一致性 操 作 系 统 | 磁 盘 管 理 50 CUIT 徐虹 ?磁盘高速缓存 ?形式 ?独立的磁盘缓冲 ?缓冲池 ?数据交付 ?置换算法 ?周期性写回磁盘 操 作 系 统 | 磁 盘 管 理 51 CUIT 徐虹 ?优化数据的分布 ?优化物理块的分布 ?优化索引结点的分布 ?其它方法 ?提前读 ?延迟写 ?虚拟盘