操作系统课件第7章 磁盘存储器管理.ppt

磁盘存储器管理 内容提要 磁盘I/O 外存分配方法 空闲存储空间的管理 磁盘容错技术 文件系统性能的改善 数据一致性 磁盘存储管理的主要任务 为文件分配必要的空间 合理组织文件存取方式 提高磁盘空间的利用率 提高对磁盘的I/O速度 采取必要的冗余措施，确保系统可靠性 磁盘I/O 几乎所有可随机存取的文件，都存 放在磁盘上。磁盘I/O速度的高低，将 直接影响到文件系统的性能。如何改善 磁盘I/O的性能，称为提高文件系统性 能的关键。 提高磁盘I/O速度的主要途径 选择性能好的磁盘 采用好的磁盘调度算法 设置磁盘高速缓冲区 磁盘数据组织 面 磁道 扇区 每个扇区包括两个字段：标识符字段和 数据字段 磁盘的分类 固定头磁盘 移动头磁盘 磁盘访问时间 寻道时间Ts 旋转延迟时间Tr 传输时间Tt 访问时间Ta 可表示为： 磁盘调度算法 先来先服务 最短寻道时间优先 扫描算法 循环扫描算法 先来先服务FCFS 这是最简单的磁盘调度算法 根据进程请求访问磁盘的先后次序进行 调度 优点是公平、简单，且每个进程的要求 都可得到处理 由于未对寻道进行优化，致使平均寻道 时间可能较长 最短寻道时间优先SSTF 该算法选择这样的进程，其要求访问的 磁道与当前磁头所在的磁道距离最近。 该算法不能保证平均寻道时间最短。 进程“饥饿”现象 SSTF算法虽然获得较好的寻道性能 ，但它可能导致某些进程“饥饿”。若 只要有新进程到达，且其所要访问的磁 道与磁头当前所在磁道的距离较近，这 种新进程的I/O请求必被优先满足。 SCAN算法 SCAN算法不仅考虑到欲访问的磁 道与当前磁道的距离，更优先考虑的是 磁头的当前移动方向。由于这种算法中 磁头移动的规律类似电梯的运行，又称 为电梯调度算法。 循环扫描算法CSCAN SCAN算法既能获得较好的寻道时 间，又能防止进程饥饿，故被广泛应用 。为防止访问刚移动过的磁道的进程被 严重推迟，CSCAN算法规定磁头单向移 动。 N-step-SCAN算法 在SSTF、SCAN和CSCAN几种调度 算法中，都可能出现磁臂停留在某处不 动的情况，称为磁臂粘着。N步SCAN 算法是将磁盘请求队列分成若干个长度 为N的子队列，磁盘调度将按FCFS算法 一次处理这些子队列。每处理一个队列 时，又按SCAN算法，对一个队列处理 完后，又处理其它队列，以避免粘着现 象。 FSCAN算法 FSCAN算法实质上是N步SCAN算法的 简化 它将磁盘请求队列分成两个子队列 一是当前所有请求磁盘I/O进程形成的 队列，按SCAN算法进行处理 另一个队列是新出现的进程队列，将它 们排入另一个等待处理的请求队列，新 请求都将被推出到下一次扫描时处理 分配外存空间的主要问题 怎样才能有效地利用外存空间 提高对文件的访问速率 常用的外存分配方法 连续分配 链接分配 索引分配 连续分配 FSCAN算法实质上是N步SCAN算法的 简化 它将磁盘请求队列分成两个子队列 一是当前所有请求磁盘I/O进程形成的 队列，按SCAN算法进行处理 另一个队列是新出现的进程队列，将它 们排入另一个等待处理的请求队列，新 请求都将被推出到下一次扫描时处理 磁盘空间的连续分配 count 0 12 3 4 56 7 f 89 1011 12131415 16171819 tr 20212223 24252627 28 2930 31 mail list filestartlength count tr mail list f 02 143 196 28 6 4 2 目录 连续分配的主要优点 顺序访问容易 顺序访问速度快 连续分配的主要缺点 要求有连续的存储空间 必须事先知道文件的长度 链接分配 在采用链接分配方式时，可通过在每 个盘块上的链接指针，将同属于一个 文件的多个离散的盘块链接成一个链 表，由此形成的物理文件称为链接文 件 链接分配采取离散分配方式，从而消 除了外部碎片 链接方式可分为：隐式链接和显式链 接两种 磁盘空间的连续分配 count 0 12 3 4 56 7 f 89 1011 12131415 16171819 tr 20212223 24 25 2627 28 2930 31 mail list filestartend jeep925 目录 1625 1 10 -1 隐式链接分配的主要问题 它只适于顺序访问，对随机访问是极 其低效的 只通过链接指针来将一大批离散的盘 块链接起来，其可靠性较差 为提高检索速度和减小指针所占用的 存储空间，可将几个盘块组成一个簇 显式链接 这是把用于链接文件各物理块的 指针，显式地存放在内存的一张链接 表。该表在整个磁盘仅设置一张，该 表称为文件分配表FAT。MS-DOS及 OS/2等操作系统都采用FAT。 显式链接结构 FCB 2 物理块号FAT 0 1 2 3 4 5 0 4 5 1 MS-DOS的文件物理结构 FCB A 4 0 FCB B 9 1 2 3 4 5 6 7 8 9 FAT 6 11 10 5 EOF EOF 链接分配方式存在的问题 不能支持高效地直接存取 FAT需占用较大的内存空间 索引分配的引入 为每个文件分配一个索引块，记录分 配给该文件的所有盘块号 索引分配方式支持直接访问 索引分配方式的主要问题，是可能花 费较多的外存空间 对较大文件而言，索引分配方式是优 于链接分配的；但对小文件而言，索 引块的利用率极低 索引分配方法 count 0 12 3 4 56 7 f 89 1011 12131415 161718 19 202122 23 24 25 26 27 28 2930 31 file块序号 jeep19 目录 1 9 16 1 10 25 1 1 1 19 两级索引分配 主索引 740 360 1125 360 740 1125 105 106 254 356 357 985 第二级索引 985 0 1 2 105 106 254 356 357 磁盘空间 空闲存储空间管理的引入 系统应为分配存储空间而设置相应的数 据结构 系统应提供对存储空间进行分配和回收 的功能 常用的空闲空间管理方法包括：空闲表 法、空闲链表法、位示图法及成组链接 法 空闲表法 系统为外存所有空闲区建立一张空闲表 ，每个空闲区对应一个空闲表项。 空闲表包括：序号、该空闲区 空闲盘块表 序号第一空闲盘块号空闲盘块数 1 2 3 4 24 93 155 空闲链表法 空闲链表法是将所有的空闲盘区拉成一 条空闲链。 有两种链表形式：空闲盘块链和空闲盘 区链 空闲盘块链 将空闲存储空间以盘块为基本单元拉成 一条链表 优点是用于分配和回收一个盘块的过程 非常简单 缺点是空闲盘块链可能很长 空闲盘区链 将所有的空闲盘区(每个盘区包含若干 个盘块)拉成一条链。在每个盘区上隐 含用于指示下一个盘区的指针外，还标 有指明本盘区大小的信息 盘区分配方法采用首次适应算法 该方法与空闲盘块链的优缺点刚好相反 ，即分配和回收过程较复杂，但空闲盘 区链较短。 位示图法 位示图是利用一位二进制数来表示磁盘 中一个盘块的使用情况 当其值是0时，表示盘块空闲；为1时， 表示盘块已分配。 由磁盘所有盘块所对应的位构成的集合 ，称为位示图。 位示图 1 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 16 Var map: array 1m, 1n 成组链接法 成组链接法结合了空闲表法和空闲 链法的优点，而克服了两种方法均有的 表太长的缺点，在UNIX中被采用。 空闲盘块的组织 空闲盘块栈，用来存放可用的空闲盘块 号和盘块数 所有空闲盘块被分成若干组 将每组含有的盘块数和该组所有的盘块 号记入前一组的第一盘块中 磁盘容错技术 容错技术是通过在系统中设置冗余部件 来提高系统可靠性的一种技术。 磁盘容错技术是通过增加冗余的磁盘驱 动器、磁盘控制器等，来提高磁盘系统 的可靠性。 磁盘容错技术通常也称为系统容错技术 磁盘容错技术的级别 SFT-是低级磁盘容错技术，主要用于 防止磁盘表面发生缺陷所引起的数据丢 失 SFT-是中级磁盘容错技术，主要用于 防止磁盘驱动器和磁盘控制器故障所引 起的系统不能正常工作 SFT-是高级系统容错技术 第一级容错技术 第一级容错技术SFT-是最早出现 的、也是最基本的一种磁盘容错技术。 它包含双份目录、双份文件分配表及写 后校验等措施。 双份目录和双份文件分配表 在不同的磁盘或磁盘的不同区域中，分 别建立两份目录表和FAT。 一份称为主目录及主FAT；另一份称为 备份目录及备份FAT。 一旦磁盘表面缺陷而造成损坏时，系统 启用备份文件目录及备份FAT，从而保 证磁盘上的数据仍是可访问的，并将损 坏区写入坏块表中。 热修复重定向 系统将一定的磁盘容量作为热修复重定 向区，用于存放当前盘块有缺陷时的代 写数据 对写入该区的所有数据进行登记，以便 于以后对数据进行访问。 写后读校验方式 为保证数据都能写入完好的盘块中，每 次写入一个数据块后，应立即从磁盘上 读出送入另一缓冲区，再将该缓冲区与 内存中仍保留的数据进行比较。 若两者相等，则此次写入成功；否则， 重写。 若重写后两者仍不一致，则表示该盘块 有缺陷。 第二级容错技术 SFT-只能用于防止由磁盘表面 部分故障造成的数据丢失。但如果磁盘 驱动器发生故障，则SFT-便无能为力 。为避免数据丢失，增设了磁盘镜像功 能。 磁盘镜像示意图 主机 磁盘控制器 通道 磁盘驱动器 磁盘双工 磁盘双工是指两台磁盘驱动器分别接到 两个磁盘控制器上，同样地使这两台磁 盘机镜像成对。 文件服务器同时将数据写到两个处于不 同控制器下的磁盘上，使两者有着完全 相同的位像图。 读数据时，可采取分离搜索技术。 磁盘双工示意图 主机 通道 磁盘驱动器 磁 盘 控制器 通道 磁 盘 控制器 廉价磁盘冗余阵列 廉价磁盘冗余阵列RAID是利用一 台磁盘阵列控制器，来统一管理和控制 一组磁盘驱动器，组成一个高度可靠的 、快速的大容量磁盘系统。现已经被广 泛地应用于大、中型计算机系统和计算 机网络中。 并行交叉存取 在该系统中，系统将每一盘块中的数据 分为若干个盘块数据，再把每一子盘块 的数据分别存储到各个不同磁盘中的相 同位置。 读取数据时，采用并行传输方式，将各 盘块的子盘块数据同时向内存传输，从 而使传输时间大大减少。 磁盘并行交叉存取方式 123N RAID的优点 可靠性高 磁盘I/O速度高 性能/价格比高 后备系统 虽然磁盘系统的容量很大，但系统 运行一段时间后，可能将磁盘装满。因 此，每隔一定的时间，就将磁盘上的大 部分数据，转储到后备系统中；而后备 系统中的数据，需每隔一段时间重新进 行拷贝，以防止由于自然因素使后备系 统中的数据逐渐消失。 后备系统的类型 磁带机 磁盘机 光盘机 拷贝方法 完全转储法：定期将磁盘上的整个文件 系统，拷贝到后备系统上。 增量转储法：在系统中应配置一张转储 时间表，在其中记录下每个文件最后一 次的转储时间。 如何提高文件访问速度 改进文件的目录结构以及检索目录的方 法，来减少对文件的查找时间 选择好的文件存储结构，以提高对文件 的访问速度 提高磁盘I/O速度，以提高对数据的传 送速度 数据一致性控制 当一个数据被分别存储到多个文件 中时，