磁盘存储器管理课件

v目前，几乎所有随机存取的文件，都是存放在磁盘上，磁盘I/O速度的高低将直接影响文件系统的性能。v硬盘分为两种：v固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高v移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低1 磁盘概述柱面柱面扇区扇区磁臂磁臂磁头磁头侧视图扇区扇区俯视图磁道磁道v信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头v所有盘面中处于同一磁道号上的所有磁道组成一个柱面v每个柱面8-32个扇区（一般为512字节）v物理地址形式：v 柱面号v 磁头号v 扇区号柱面、磁头、扇区例子：典型参数v20G：v 39813 柱面v 16 头v 63 扇区v60G：v 28733 柱面v 16 头v 255 扇区v由三个动作组成：寻道：磁头移动定位到指定磁道旋转延迟：等待指定扇区从磁头下旋转经过数据传输：数据在磁盘与内存之间的实际传输磁盘的访问过程*v寻道时间Ts：大约几ms到几十msv旋转延迟时间Tr：平均为转半圈的时间对于7200转/分，平均延迟时间为4.2msv数据传输时间Tt：目前磁盘的传输速度一般有几十M/s，传输一个扇区的时间小于0.05ms磁盘的访问时间分析v要提高磁盘的访问速度主要应从以下两方面入手：v数据的合理组织v磁盘的调度算法2 磁盘调度算法v当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效v公平：一个I/O请求在有限时间内满足v高效：减少设备机械运动所带来的时间浪费v主要算法：v1)先来先服务FCFSv2)最短寻道时间优先SSTFv3)扫描算法v4)单向扫描调度算法v按访问请求到达的先后次序服务v优点：简单，公平；v缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利2.1 先来先服务v假设磁盘访问序列：98，183，37，122，14，124，65，67v读写头起始位置：53v安排磁头服务序列v计算磁头移动总距离（道数）例图解98，183，37，122，14，124，65，67磁头走过的总道数：磁头走过的总道数：640FCFS调度算法v优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先v 优点：改善了磁盘平均服务时间；v 缺点：造成某些访问请求长期等待得不到服务2.2 最短寻道时间优先(SSTF)(Shortest Seek Time First)图解65，67，37，14，98，122，124，183磁头走过的总道数：磁头走过的总道数：23698，183，37，122，14，124，65，67SSTF调度算法1)进程进程“饥饿饥饿”现象现象SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(Starvation)现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必须优先满足。解决：对SSTF算法略加修改后所形成的SCAN算法，可防止老进程出现“饥饿”现象。2.3 扫描算法v克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向v具体做法：v当设备无访问请求时，磁头不动；v当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；v否则改变移动方向，并为经过的访问请求服务，如此反复SCAN图图解37，14，65，67，98，122，124，183磁头走过的总道数：磁头走过的总道数：20898，183，37，122，14，124，65，67 SCAN调度算法示例v也称单向扫描算法。v电梯算法杜绝了饥饿，但当请求对磁道的分布是均匀时，磁头回头，近磁头端的请求很少（因为磁头刚经过），而远端请求较多，这些请求等待时间要长一些。修改：总是从0号柱面开始向里扫描。移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到最外欲访问柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描 2.4 循环扫描调度算法CSCAN图解 CSCAN调度算法示例2.5 N-Step-SCAN和FSCAN调度算法 vSSTF、SCAN、CSCAN几种调度算法都可能出现磁臂停留在某处不动的情况，称为磁臂粘着(Arm-Stickiness)。v例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”。v在高密度磁盘上容易出现此情况。1）N-Step-SCAN算法vN-STEP-SCAN算法将磁盘请求队列分成若干个长度为N的子队列。v磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时，又是按SCAN算法。v当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。v当N值取得很大时，会使N步扫描法的性能接近于SCAN算法的性能；v当N=1时，N步SCAN算法便蜕化为FCFS算法。2）FSCAN算法v本算法是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列：v当前所有请求磁盘IO的进程形成的队列，由磁盘调度按SCAN算法进行处理。v在扫描期间，新出现的所有请求磁盘IO进程组成的等待处理的请求队列。从而使所有的新请求都将被推迟到下一次扫描时处理。调度算法的选择v实际系统相当普遍采用最短寻道时间优先算法，因为它简单有效，性价比好。v扫描算法更适于磁盘负担重的系统。v磁盘负担很轻的系统也可以采用先来先服务算法v一般要将磁盘调度算法作为操作系统的单独模块编写，利于修改和更换。v磁盘的I/O速度要比内存低4-6个数量级v分配一些内存作为磁盘高速缓存可以极大地提高磁盘I/O速度。v磁盘高速缓存是指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。v因此，这里的高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。5.6.3 磁盘高速缓存磁盘高速缓存的形式v在内存中开辟一个单独的存储空间作为磁盘高速缓存。v把所有未利用的内存空间变为一个缓冲池，供分页系统和磁盘I/O共享。数据交付v当有访问请求时，系统看所需的块是否在高速缓存中。如果在，则可直接访问缓存。否则，首先要将块读到高速缓存，再拷贝到所需的地方。v数据交付：将磁盘高速缓存中的数据传送给请求者进程。v数据交付有两种方式：v数据交付：将数据从缓存传到进程空间v指针交付：将指向缓存中数据的指针传给进程。置换算法v如果高速缓存已满，则需要进行淘汰。v常用置换算法：最近最久未使用LRU、最少使用LFU等。周期性写回磁盘vLRU算法中，那些经常被访问的盘块可能会一直保留在高速缓存中，而长期不被写回磁盘中，留下了安全隐患。v解决之道：v周期性写回。周期性地强行将已修改盘块写回磁盘。周期一般为几十秒。5.6.4 提高磁盘I/O速度的其它方法v 提前读 v 延迟写 v 虚拟盘v每次一道缓冲v磁盘扇区交叉编址提前读v在访问文件时经常是顺序访问，因此在读当前块时可以提前读出下一块。v提前读已经被广泛应用：UNIX、OS/2、Netware等。延迟写v修改缓存中的数据后一般应立即写回磁盘，但该盘块可能还会被修改，立即写回会带来很大的开销。v置上延迟写标志。直到该盘块淘汰时或周期性写回时。v延迟写也被广泛应用：UNIX、OS/2 等。虚拟盘v利用内存仿真磁盘，又称RAM盘。v虚拟盘同磁盘高速缓存的区别：v虚拟盘的内容完全由用户控制，用户可见。v缓存的内容完全由系统控制，用户不可见。优化物理块的分布 v另一个提高对文件访问速度的重要措施，是优化文件物理块的分布，使磁头的移动距离最小。v链接分配和索引分配方式，都允许将一个文件的物理块分散在磁盘的任意位置。v如果将一个文件的多个物理块，安排得过于分散，会增加磁头的移动距离。v对文件盘块位置的优化，应在为文件分配盘块时进行。每次一道(Track at a time)缓冲v寻道延迟通常比旋转延迟大得多，而且往往比传输时间长很多。v读一个扇区和读一条磁道差不多。v有些磁盘驱动程序通过维护一个秘密的每次一道的高速缓冲来利用这一特性，并不被独立于设备的软件所感知。v缺点：从高速缓冲到调用程序间的数据传输由CPU完成，而不是DMA完成。磁盘扇区的交叉编址v a)不采用交叉编址 (b)单交叉编址 (c)双交叉编址磁盘的出错v程序性错误（如请求读写不存在的扇区）v暂时性校验和错（如由灰尘引起）v永久性校验和错（磁盘块的物理损坏）v寻道出错v控制器错（如控制器拒绝接受命令）程序性错误v控制器检查发送的参数，并在参数非法时给出信息。v驱动程序可以停止运行；也可以将请求以出错结束。暂时性校验和错v重复操作几次。v如果一直存在错误，将该数据块标为坏块。坏块的处理方法：v使用坏块文件包含所有坏块；v由控制器使用保留磁道来替换坏块；寻道出错v磁盘臂的机械问题。v驱动程序发出一条指令把磁盘臂移到最外面，并将使控制器内部将当前柱面号复位为0。v如果还不能解决问题，则必须修理驱动器。5.6.5 廉价磁盘冗余阵列vRAID(Redundant Arrays of Inexpensive Disk)。由伯克利提出，广泛用于大中型计算机和网络中。v由一台磁盘阵列控制器控制一组磁盘驱动器，组成一个高度可靠、快速的大容量磁盘系统。v1、并行交叉存取 v2、RAID分级 v3、RAID的优点1、并行交叉存取 v加快访问速度v在系统中有多台磁盘驱动器（N）。v存放数据时，将数据的第一块放在第一个磁盘上，第N块放在第N个磁盘上。v这样可以并行读写，极大地提高了速度。2、RAID分级 vRAID0RAID7vRAID0 提供并行交叉存取（没有冗余能力）v 至少两个盘vRAID1 两个盘，并行交叉存取，并把一个磁盘的数据镜像到另一个磁盘上。利用率50%。比传统镜像盘快。vRAID3 利用一个校验盘来完成容错。数据数据0数据数据1 1的备份的备份CPU磁盘磁盘0数据数据1数据数据0 0的备份的备份磁盘磁盘1图3、RAID的优点v可靠性高。除了RAID0，其余各级都采用了容错技术。某个磁盘损坏时，不会造成数据丢失。v速度快。可并行存取。v性能/价格比高。利用RAID技术实现的大容量快速存储器，同大型磁盘系统相比，体积和价格都是后都的1/3。可靠性更高 时钟v时钟（clock），又称为定时器（timer）(1)时钟负责提供一天的时间 (2)防止一个进程垄断CPU 时钟既不是块设备，也不是字符设备，但时钟软件通常也采用设备驱动程序的形式时钟软件时钟硬件所做的工作是每隔一定的时间间隔产生一个中断；涉及时间的其他所有工作都必须由软件时钟驱动程序完成时钟驱动程序的任务：v维护日期时间；v防止进程的运行时间超出其允许的时间；v对CPU使用进行计帐；v处理用户进程提出的时间闹钟系统调用；v对系统某些部分提供监视定时器；v支持直方图监视和统计信息收集；v系统的其他部分也需要定时器，称为监视定时器（watchdog timer）。v例如，使用软盘时，系统必须驱动软盘的电机接通电源并等待大约500毫秒，使电机达到稳定速度