9.1 第九章磁盘管理 磁盘I/o >磁盘性能简述 磁盘调度算法 F数据的细织盘,磁道,柱面和扇区 文件分配 >磁盘访问时间 磁盘空间的管理 道时间 RAID 旋转延迟时间 传输时间 磁盘调度算法 目标:平均寻道时间最短 1|11F-…-+ 作系统盘管 DevIce HUt Timing of a Disk I/O Transfer (a) FIFO 先来先服务FCFs( First-Come (starting at track I00) 厚墨后薏法程请求访 问磁盘的先后次 accessed 特点:公平、简单,平均哥道时间长。 verage seek
1 第九章 磁盘管理 磁盘调度算法 文件分配 磁盘空间的管理 RAID 操 作 系 统 | 磁 盘 管 理 2 CUIT 徐虹 9．1 磁盘 I/O ¾磁盘性能简述 ¾数据的组织：盘、磁道、柱面和扇区。 ¾磁盘的类型：固定磁头和移动磁头。 ¾磁盘访问时间 ¾寻道时间 ¾旋转延迟时间 ¾传输时间 操 作 系 统 | 磁 盘 管 理 3 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 4 CUIT 徐虹 ¾磁盘调度算法 ¾目标：平均寻道时间最短。 操 作 系 统 | 磁 盘 管 理 5 CUIT 徐虹 ¾先来先服务FCFS（First—Come First—Served） ¾原理：根据进程请求访问磁盘的先后次 序进行调度。 ¾特点：公平、简单。平均寻道时间长。 操 作 系 统 | 磁 盘 管 理 6 CUIT 徐虹
最短寻道时间优先SSTF( Shortest seek (starting at track 100) 原理:选择有距当前磁头所在磁道最近的访闻 道的进程。 accessed traversed 特点:寻道时间最短,但导致某些进程发生“饥 作系统丨碰管理 23602 Average seek 27.5 扫描算法(SCAN) number) 原理:选择与当前磁头移动方向一致且距高最 ext tra 近的进程。 特点:寻道性能较好,避兔了进程饥饿现象 作系统盘管 16 reScAN Average seek 27.8 (d)C-SCAN (start ing at track I00. in the 循环扫描算法( CSCAN) number) 规定磁头单向移动。 accesse traversed Average seek
2 操 作 系 统 | 磁 盘 管 理 7 CUIT 徐虹 ¾最短寻道时间优先SSTF（Shortest Seek Time First） ¾原理：选择有距当前磁头所在磁道最近的访问 磁道的进程。 ¾特点：寻道时间最短，但导致某些进程发生“饥 饿”现象。 操 作 系 统 | 磁 盘 管 理 8 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 9 CUIT 徐虹 ¾扫描算法（SCAN） ¾原理：选择与当前磁头移动方向一致且距离最 近的进程。 ¾特点：寻道性能较好，避免了进程“饥饿”现象。 操 作 系 统 | 磁 盘 管 理 10 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 11 CUIT 徐虹 ¾循环扫描算法（CSCAN） ¾规定磁头单向移动。 操 作 系 统 | 磁 盘 管 理 12 CUIT 徐虹
Disk Scheduling Algorithms [WTEDS71 N-Step-SCAN算法 “磁臂粘着现象:磁背停留在某处不动 将磁盘请求队列分成若干个长度为N的 Selectin 队列,礅盘调度将按FCFS算法依次 For analyas and amulaen 处理这专手列。而个队列的处理 First an tirst out Proerty Conrel outai of dk uum 个队列。 FSCAN算法 Seleetion according to requested item: 一 N-Step-SCAN算法的简化,只分为两个 Shaan temre tm fira High ttilttahon, small Rark and farth over drk Frll trrve teatrtbu! 当前请求1O的进程队列:SCAN算法 扫描期间请求的进程队列:FCFS N-Iep-SCAl SCAN oE record at a hmt Servce guarantee at beginning of 外存分配方法 连续分配(顺序文件) 分配与回收 个逻辑上连续的文件信息依 次存放在物理块中。 回收:碎片整邏问题 一优点:能很快进行存取。 理-x 缺点:不便于记录的增,删操作,不能 Contiguous File Allocation 链接分配(串联文件) 口-哪 >隐式链接 在文件的目录中记录该文件的第一和最 宓2型22 件可动态增长,不需指明文件 便于增删 约空间 x□2-□2 缺点:只适合顺序存取,不宜于宜接 改进:将几个盘块组成簇( cluster) 以为单位分配 Contiguous File Allocation(After Compaction
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）， 以簇为单位分配
显示链接 将链接文件各物理块 显示地放 在内存的一张链接表 地址中填写其首指针所对应的盘块号 口m口 FAT( File Allocation Table):文件 分配,整个磁盘设置张,放在内存 中 缺点:不能宜接存取;FAT占较大内 存空间。 D30=0aDMD 索引文件 口 要求为每一文件建立一张索引表。每 个表目指出文件逻辑记录所在的物理 块号 |口心 特点:方便地进行随机存取;增加了 索引表的空间开销,增加一次访问操 作 |口x[、 □xxx >串联文件方式组织 多重索引方式组织 Indexed Allocation with Block portions 口口心 InE Nan Intex kxk 综合组织方式 口口口 把索引的头几项设计为直接寻址方式 存放物理块号,后几项设计成多重索引。 综合组织方式适用于顺序存取和随机存 地 2 addr(10) MDMDxDMDMD 二次间接地址 addr(11) ddr(12) Indexed Allocation with Variable-length portion
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)
Capacity of a UNIX File Number of Blocks Sinle Indireet 256K Triple Indrect 256×65K-16M 9.3文件存储空间管理 空闲表 空闲表 >系统应能自动地为用户分配存储 把一个连续 区域称为“空用文件 空间,管理系统和用户的存储空 间,实现按名存取。 作系统盘管 系统为所有“ 件单独建立一个目 一表目内容:序号,第一个空白块号,空 文件存储空间的管理包括空闲块 白块个数 的组织分配和回收。 空间分配和回收 位示图 空闲块链 为文件存储器存储空间建立一张位示 空闲盘块链 用以反映整个空间的分配情况 分配和释放顺序:从头分配,从尾回收 >简单,速度快,占一定的空间 >空闲盘区链 盘块号与位示图行列的转换 分配:首次适应算法 回收:拼接闻题
5 操 作 系 统 | 磁 盘 管 理 25 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 26 CUIT 徐虹 操 作 系 统 | 磁 盘 管 理 27 CUIT 徐虹 9． 3 文件存储空间管理 ¾系统应能自动地为用户分配存储 空间，管理系统和用户的存储空 间，实现按名存取。 ¾文件存储空间的管理包括空闲块 的组织分配和回收。 操 作 系 统 | 磁 盘 管 理 28 CUIT 徐虹 ¾空闲表 ¾空闲表 ¾把一个连续未分配区域称为“空闲文件”， 系统为所有“空闲文件”单独建立一个目 录。 ¾表目内容：序号，第一个空白块号，空 白块个数。 ¾空间分配和回收 操 作 系 统 | 磁 盘 管 理 29 CUIT 徐虹 ¾位示图 ¾为文件存储器存储空间建立一张位示 图，用以反映整个空间的分配情况。 ¾简单，速度快，占一定的空间。 ¾盘块号与位示图行列的转换： 操 作 系 统 | 磁 盘 管 理 30 CUIT 徐虹 ¾空闲块链 ¾空闲盘块链 ¾分配和释放顺序：从头分配，从尾回收。 ¾空闲盘区链 ¾分配：首次适应算法 ¾回收：拼接问题
成组链接法 >分配和释放 原复制 实现方法 块号 对所有的空白块从尾倒着向前分组 组99块,随后每组 应块号记录在前一组的第一块中。最后 足100块)的数据登记在空用盘 (卷资源表)中第二组的0号单元的值仍 作系统丨碰管理 分配时,ptr-1,然后取出对应项作为这次 申请得到 如此下去,宜到栈底 应此袭目 为100,1号单元值为0(文卷卷尾标志) 值为0时,表示遇到卷尾标志 表示无空闲块可分配。 当回收时,先登记块号,然 号记入相应表目中。 >特点 94磁盘容错技术 空白块号的登记不占用额外空间 绝大部分分配和释放工作都在主存进 磁盘容错技术SFT 行 把总块数作为空白块栈的指针使 是理想的存储结构。效率高 作系统盘管 (System Fault Tolerance) 通过增加冗余的磁盘驱动器、磁 盘控制器等,来提高磁盘系统的 可靠性 >第一级容错技术SFT-1 第二级容错技术SFT-2 用于防止磁盘表面发生缺陷所引 磁盘镜像( Disk Mirroring) 起的数据丢失 双份目录和双份分配表 >磁盘双工( Disk Duplexing 主目录和主分酸表 备份目录和备份分配表 热修复重定向和写后读校验 热修复定向( Hot-Fix 写后读校验( Read after write
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
独立磁盘冗余阵列RAID RAID0级:仅提供并行交叉存取。 (Redundant array of Independent Disks) 利用一台磁盘阵列控制器统一管 理和控制一组(几台到几十台)磁 strip 4 盘驱动器,组成一个高度可的 快速的大容量磁盘系统。 strip 14 并行交叉存取 fa RAID O(non-redundant RAID1级:具有微盘镜像功能,利用并行特 性将款滑块同时写入主盘和健像盘 作系跳 Data ma RAID Level 0 Array IMASS 一RAID2级:并行访问; strip只有一个 RAID3级:具有并行传输功能的盘阵列 字或字节;用 Hamming码校验 取字节用奇偶校验 国国国 (d)RAlD 3(bit-interleaved parity)
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只有一个字或字节；用奇偶校验
RAID4级;独立访间,sm教大,以smip 为单位进行奇偶校验 RAID5级:具有独立传送功能的盘阵列 奇偶校验分布在不同的磁盘上 block 6[block block s block I0 block P8.11 block s 霎團 black Il ock 12 block 13 block 1-4 block 15 P12-15 block 12 lock 14 block 15 lock Is block 19 RAlD 4(block-level parity ( n RAID 5 (block-level distributed parity) RAID6级:两种不同的奇偶校验计算 RAID的优点 在不同的磁盘的不同块 可性高 磁盘I/O速度快 性能/价格比高 后备系统 文件系统的恢复过程 类型 从最近一次全量转存中装入全部系 复制方法 统文件,使系统得以新起动,并在 周期性的全量转存 其控制下进行后续的恢复工作。 从近到远从增转存盘上恢复文件 增量转存 从最近次全转存盘中,恢复没 一以上两种方式配合使用
8 操 作 系 统 | 磁 盘 管 理 43 CUIT 徐虹 RAID 4级：独立访问，strip较大，以 strip 为单位进行奇偶校验。 操 作 系 统 | 磁 盘 管 理 44 CUIT 徐虹 RAID 5级：具有独立传送功能的磁盘阵列。 奇偶校验分布在不同的磁盘上。 操 作 系 统 | 磁 盘 管 理 45 CUIT 徐虹 ¾RAID 6级：两种不同的奇偶校验计算， 在不同的磁盘的不同块中。 操 作 系 统 | 磁 盘 管 理 46 CUIT 徐虹 ¾RAID 的优点 ¾可靠性高 ¾磁盘I/O速度快 ¾性能/价格比高 操 作 系 统 | 磁 盘 管 理 47 CUIT 徐虹 ¾后备系统 ¾类型 ¾复制方法 ¾周期性的全量转存 ¾增量转存 ¾以上两种方式配合使用。 操 作 系 统 | 磁 盘 管 理 48 CUIT 徐虹 ¾文件系统的恢复过程 ¾从最近一次全量转存中装入全部系 统文件，使系统得以重新起动，并在 其控制下进行后续的恢复工作。 ¾从近到远从增量转存盘上恢复文件。 ¾从最近一次全量转存盘中，恢复没 恢复过的文件
96文件系统性能的改善 磁盘高速缓存 文件访问速度 独立的磁盘缓冲 数据的共享性 文件系统使用的方便性 >数据的安全性 作系统丨碰管理 级冲池 数据交付 换算法 数据一致性 周期性写回磁盘 优化数据的分布 优化物理块的分布 优化索引结点的分布 其它方法 提前读 延迟写 虚拟盘
9 操 作 系 统 | 磁 盘 管 理 49 CUIT 徐虹 9. 6 文件系统性能的改善 ¾文件访问速度 ¾数据的共享性 ¾文件系统使用的方便性 ¾数据的安全性 ¾数据一致性 操 作 系 统 | 磁 盘 管 理 50 CUIT 徐虹 ¾磁盘高速缓存 ¾形式 ¾独立的磁盘缓冲 ¾缓冲池 ¾数据交付 ¾置换算法 ¾周期性写回磁盘 操 作 系 统 | 磁 盘 管 理 51 CUIT 徐虹 ¾优化数据的分布 ¾优化物理块的分布 ¾优化索引结点的分布 ¾其它方法 ¾提前读 ¾延迟写 ¾ 虚拟盘