计算机操作系统Operating System of Computer第九章 磁盘存储器管理v主要内容：磁盘调度算法外存空间管理磁盘容错技术文件系统性能的改善数据一致性控制v知识点及要求：掌握磁盘调度算法、外存空间 管理、磁盘容错技术掌握数据一致性控制 了解文件系统性能的改善方法 9.1 磁盘概述目前，几乎所有随机存取的文件，都 是存放在磁盘上，磁盘I/O速度的高低将 直接影响文件系统的性能 硬盘分为两种： 固定头磁盘：每个磁道设置一个磁头 ，变换磁道时不需要磁头的机械移动， 速度快但成本高 移动头磁盘：一个盘面只有一个磁头 ，变换磁道时需要移动磁头，速度慢但 成本低侧视图柱面扇区磁臂磁头俯视图磁道扇区v信息记录在磁道上，多个盘片，正 反两面都用来记录信息，每面一个磁头v所有盘面中处于同一磁道号上的所 有磁道组成一个柱面v每个扇区大小为512字节 v物理地址形式：v 柱面号v 磁头号v 扇区号柱面、磁头、扇区20G：39813 柱面16 头63 扇区 60G：28733 柱面16 头255 扇区典型参数磁盘的访问过程由三个动作组成：v寻道 ：磁头移动定位到指定磁 道v旋转延迟：等待指定扇区从磁 头下旋转经过v数据传输：数据在磁盘与内存 之间的实际传输v寻道时间Ts：大约几ms到几十 msv旋转延迟时间Tr：对于7200转/ 分，平均延迟时间为4.2msv数据传输时间Tt：目前磁盘的 传输速度一般有几十M/s，传输一个 扇区的时间小于0.05ms磁盘的访问过程分析要提高磁盘的访问速度主要应从以下两方面入手：v数据的合理组织v磁盘的调度算法当多个访盘请求在等待时，采用一定的 策略，对这些请求的服务顺序调整安排，旨 在降低平均磁盘服务时间，达到公平、高效 公平：一个I/O请求在有限时间内满足 高效：减少设备机械运动所带来的时间 浪费v先来先服务v最短寻道时间优先v扫描算法v单向扫描调度算法9.2 磁盘调度算法9.2.1 先来先服务按访问请求到达的先后次序服 务v优点：简单，公平；v缺点：效率不高，相邻两次请 求可能会造成最内到最外的柱面寻 道，使磁头反复移动，增加了服务 时间，对机械也不利例假设磁盘访问序列：98，183， 37，122，14，124，65，67读写头起始位置：53安排磁头服务序列计算磁头移动总距离（道数）图解98，183，37，122，14，124，65，67 磁头走过的总道数：6409.2.2 最短寻道时间优先v优先选择距当前磁头最近的访问 请求进行服务，主要考虑寻道优先v 优点：改善了磁盘平均服务时间；v 缺点：造成某些访问请求长期等待得不到服务图解65，67 ，37，14，98， 122， 124， 183 磁头走过的总道数：23698，183，37，122，14，124，65，679.2.3 扫描算法(电梯算法)v克服了最短寻道优先的缺点，既考虑 了距离，同时又考虑了方向。
v具体做法：当设备无访问请求时，磁 头不动；当有访问请求时，磁头按一个 方向移动，在移动过程中对遇到的访问 请求进行服务，然后判断该方向上是否 还有访问请求，如果有则继续扫描；否 则改变移动方向，并为经过的访问请求 服务，如此反复图解图解37，14， 65，67 ， 98， 122， 124， 183 磁头走过的总道数：20898，183，37，122，14，124，65，67也称循环扫描算法电梯算法杜绝了饥饿，但当请求对磁道的 分布是均匀时，磁头回头，近磁头端的请求很 少（因为磁头刚经过），而远端请求较多，这 些请求等待时间要长一些 总是从0号柱面开始向里扫描移动臂到 达最后个一个柱面后，立即带动读写磁头快速 返回到0号柱面返回时不为任何的等待访问者 服务返回后可再次进行扫描9.2.4 单向扫描调度算法图解调度算法的选择v实际系统相当普遍采用最短寻道时间优先 算法，因为它简单有效，性价比好v扫描算法更适于磁盘负担重的系统v磁盘负担很轻的系统也可以采用先来先服 务算法一般要将磁盘调度算法作为操作系统的单独模块编写，利于修改和更换9.3 外存空间管理外存空间管理主要就是空闲块的管理，有以下方法：v空闲表法v空闲链表法v位图法v成组链接法9.3.1 空闲表法v与内存管理中的动态分区分配方式相同。
v空闲盘块的分配与内存的动态分配类似， 同样可以用首次、最佳、最坏适应法盘块 的回收也同内存的回收方式类似起始空闲盘块 号盘块数 24 93 155 空闲块链是另一种空闲块的组织方法， 它用一种链结构把所有空闲块链接在一起 分配：当系统建立文件需分配空闲块时 ，从链中摘取所需的空闲块，然后调整链首 指针 回收：反之，当回收空闲块时;把释放的 空闲块逐个插入链首9.3.2 空闲链表法v这种方法只需在系统中保留一个 链首指针，令其指向第一个空闲块 v这种方法的优点是简单，但工作 效率较低，因为每次在链上增加和 移出空闲块时，需要做I/O操作v例如把一空闲块插入链时，要把 链首指针(原指向第一个空闲块)写 该空闲块中，然后让链首指针指向 该空闲块从链中摘取空闲块时也 要读取下一个空闲块的指针9.3.3 位图法系统为磁盘建立一张位图，在位图中每个物 理块占1位，按物理块的顺序排列1“表示对应 的物理块已占用，“0“表示空闲分配时首先在位图中找到为“0“的位，然后转换成对应的物理块号，分配给申请者，并把相应的位置为 “1“回收时先将释放的物理块号转换成相应的位，并把这一位置为“0“ 位图的大小依据物理磁盘的容量而定。
如360KB的软盘，每个物理块为512字节，位图只占用90个字节UNIX采用此法v在UNIX中中有一个整型数组 s_free[l00]和一个整型变量s_nfreev将所有的空闲盘块分组，每100个 空闲盘块为一组最后一组的块号填入 s_free[ ]、块数赋于s_nfree其余各组 的块号则分别存放在它的下一组的第一 个盘块中9.3.4 成组链接法图解 假设共有387个空闲块分配分配空闲盘块时，总是分配 s_free[s_nfree]所指的盘块，并且s_nfree减1 当发现是直接管理的最 后一个盘块时，即s_nfree=l时，就将 该盘块中的索引表写入到s_nfree和 s_free[]中，使得下一组变为直接管理 如此类推直到最后一组释放释放空闲盘块时，将其块号登记在 s_free[]表中第一个未被占用的项例 如，若s_nfree的原先值为87，则将释放 块号登记在s_free[88]中，然后s_nfree 加1若在登记之前发现s_free已满，则 将s_free[1]至s_free[100]的内容复写 到要释放的盘块中这样原来直接管理 的100空闲盘块变为由释放块间接管理 然后将此该释放块的块号填入s_free[1] 把s_nfree置为1。
9.4 磁盘容错技术磁盘容错技术： vSFT-1：低级磁盘容错技术，主要 用于防止磁盘表面发生缺陷所引起的数 据丢失； vSFT-2：中级磁盘容错技术，主要 用于防止磁盘驱动器和磁盘控制器故障 引起的系统不能正常工作； vSFT-3：高级磁盘容错技术9.4.1 第一级容错技术1.双份目录和双份文件分配 表 v文件目录和文件分配表是文件管 理所需的重要数据结构v在系统每次启动时都要进行两份 目录和分配表的检查2.热修复重定向和写后读校验磁盘表面有少量缺陷时，采取一些补救措施后可继续使用这些措施主要用于防止将数据写入有缺陷 的盘块中v热修复重定向v写后读校验系统将一定的磁盘容量（如2%- 3%）作为热修复重定向区例如：系统要向第3柱2头1扇区写数据，但发现该扇区是坏的时，便将 数据写到热修复区（如200柱16头1扇 区）以后要读3柱2头1扇区的数据时 ，便从200柱16头1扇区中读热修复重定向写后读校验为了保证所有写入到磁盘的数据都 能写入完好的盘块中，应该在每次写数据时，又立即从磁盘上读出该块数据， 并同写前的数据进行对比（校验）若 两者不一致，则认为盘块有缺陷，便将 该数据写入到热修复区。
并对该坏盘块 进行登记9.4.2 第二级容错技术第一级容错只能用于防止磁盘表面部分故障造成的数据丢失如果磁盘驱动器或磁盘控制器发生故障，则 第一级容错就无能为力了v1.磁盘镜像 v2.磁盘双工1.磁盘镜像磁盘驱动器故障的容错 在同一磁盘控制器控制下，增设 一个完全相同的磁盘驱动器 每次将数据写主磁盘时，同时将 数据也写入到备份磁盘 一个磁盘驱动器发生故障时，必 须立即发出警告，尽快修复 磁盘利用率为50%2.磁盘双工磁盘控制器或控制器与CPU之间的通道故障的容错将两台磁盘驱动器分别接到两个 磁盘控制器上两个磁盘上的数据完全相同RAID(Redundant Arrays of Inexpensive Disk)由伯克利提出， 广泛用于大中型计算机和网络中由一台磁盘阵列控制器控制一 组磁盘驱动器，组成一个高度可靠、 快速的大容量磁盘系统v1.并行交叉存取 v2.RAID分级 v3.RAID的优点9.4.3 廉价磁盘冗余阵列1.并行交叉存取v加快访问速度v在系统中有多台磁盘驱动器（ N）v存放数据时，将数据的第一块 放在第一个磁盘上，第N块放在第N 个磁盘上v这样可以并行读写，极大地提 高了速度。
2.RAID分级RAID0—RAID7vRAID0 提供并行交叉存取（没 有冗余能力）至少两个盘vRAID1 两个盘，并行交叉存取， 并把一个磁盘的数据镜像到另一个磁 盘上利用率50%比传统镜像盘快 图磁盘0磁盘1数据0数据1 的备份CPU数据1数据0 的备份vRAID3 利用一个校验盘来完成容错vRAID5 无专门校验盘，校验数据分布在多个盘上 一个磁盘故障时，控制器可从其他尚存的磁盘上重新恢复/生成丢失的数据而不影响数据的可用性 常用于I/O较频繁的事务处理v可靠性高除了RAID0，其余各级都采用了容错技术某个磁盘损坏时，不会造成数据丢失v速度快可并行存取v性能/价格比高利用RAID技术实现的大容量快速存储器，同大型磁盘系统相比，体 积和价格都是后都的1/3可靠性更高3.RAID的优点9.4.4 后备系统容量和安全性考虑，需要后备系统 v1. 后备系统的类型 v2 .拷贝方法1.后备系统的类型v磁带机： 最广泛v硬盘： v光盘： 很有前途2.拷贝方法v完全转储：定期将所有文件拷贝到后援存储器v增量转储：只转储修改过的文件，即两次备份之间的修改，减少系统开销9.5 文件系统性能的改善文件系统的性能可表现在多个方 面v文件的访问速度v数据的可共享性v文件系统使用的方便性v数据的安全和一致性。
提高磁盘I/O速度的方法v磁盘高速缓存v优化数据分布v其它方法9.5.1 磁盘高速缓存v磁盘的I/O速度要比内存低4-6个数量级v分配一些内存作为磁盘高速 缓存可以极大地提高磁盘I/O速度磁盘高速缓存的形式在内存中开辟一个单独的存储空间作为磁盘高速缓存把所有未利用的内存空间变为 一个缓冲池 ，供分页系统和磁盘I/O共享数据交付数据交付：将磁盘高速缓存中的数据传 送给请求者进程当有访问请求时，系统看所需的块是否 在高速缓存中如果在，则可直接访问缓存 否则，首先要将块读到高速缓存，再拷贝 到所需的地方 数据交付有两种方式：v数据交付 ：将数据从缓存传到进程空间v指针交付 ：将指向缓存中数据的指针传 给进程v如果高速缓存已满，则需要进行淘汰v常用置换算法：最近最久未使 用LRU、最少使用LFU等置换算法周期性写回磁盘vLRU算法中，那些经常被访问的盘 块可能会一直保留在高速缓存中，而长 期不被写回磁盘中留下了安全隐患v解决之道：周期性写回周期性地 强行将已修改盘块写回磁盘周期一般 为几十秒9.5.2 优化数据的分布v优化物理块的分布 v优化索引结点的分布优化物理块。