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 徐虹 ¾空闲块链 ¾空闲盘块链 ¾分配和释放顺序：从头分配，从尾回收。 ¾空闲盘区链 ¾分配：首次适应算法 ¾回收：拼接问题