计算机操作系统ch9.ppt

《计算机操作系统ch9.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统ch9.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机操作系统Operating System of Computer第九章第九章 磁盘存储器管理磁盘存储器管理v主要内容：主要内容：磁盘调度算法外存空间管理磁盘容错技术文件系统性能的改善数据一致性控制v知识点及要求：知识点及要求：掌握磁盘调度算法、外存空间管理、磁盘容错技术。掌握数据一致性控制。了解文件系统性能的改善方法。9.1 9.1 磁盘概述磁盘概述目前，几乎所有随机存取的文件，都是存放在磁盘上，磁盘I/O速度的高低将直接影响文件系统的性能。硬盘分为两种：硬盘分为两种：固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高。移动头磁盘：一个盘面只有一个磁头，变换

2、磁道时需要移动磁头，速度慢但成本低。侧视图侧视图柱面柱面扇区扇区磁臂磁臂磁头磁头俯视图俯视图磁道磁道扇区扇区v信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头v所有盘面中处于同一磁道号上的所有磁道组成一个柱面v每个扇区大小为512字节 v物理地址形式：v 柱面号v 磁头号v 扇区号柱面、磁头、扇区柱面、磁头、扇区20G：39813 柱面柱面 16 头头 63 扇区扇区60G：28733 柱面柱面 16 头头 255 扇区扇区典型参数典型参数磁盘的访问过程磁盘的访问过程由三个动作组成：v寻道：磁头移动定位到指定磁道v旋转延迟：等待指定扇区从磁头下旋转经过v数据传输：数据在磁盘与内

3、存之间的实际传输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 磁盘调度算法磁盘调度算法9

4、.2.1 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 9.2.2 最短寻道时间优先最短寻道时间优先v优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先v优点：改善了磁盘平均服务时间；v缺点：造成某些访

5、问请求长期等待得不到服务图解图解65，67，37，14，98，122，124，183磁头走过的总道数：磁头走过的总道数：23698，183，37，122，14，124，65，679.2.3 9.2.3 扫描算法扫描算法(电梯算法电梯算法)v克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。v具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。图解图解图解图解37，14，65，67，98，122，124，183磁头走过的总道

6、数：磁头走过的总道数：20898，183，37，122，14，124，65，67也称循环扫描算法。电梯算法杜绝了饥饿，但当请求对磁道的分布是均匀时，磁头回头，近磁头端的请求很少（因为磁头刚经过），而远端请求较多，这些请求等待时间要长一些。总是从0号柱面开始向里扫描。移动臂到达最后个一个柱面后，立即带动读写磁头快速返回到0号柱面。返回时不为任何的等待访问者服务。返回后可再次进行扫描。9.2.4 9.2.4 单向扫描调度算法单向扫描调度算法图解图解调度算法的选择调度算法的选择v实际系统相当普遍采用最短寻道时间优先算法，因为它简单有效，性价比好。v扫描算法更适于磁盘负担重的系统。v磁盘负担很轻的系统

7、也可以采用先来先服务算法。一般要将磁盘调度算法作为操作系统的单独模块编写，利于修改和更换。9.3 9.3 外存空间管理外存空间管理 外存空间管理主要就是空闲块的管理，有以下方法：v空闲表法v空闲链表法v位图法v成组链接法9.3.1 9.3.1 空闲表法空闲表法v与内存管理中的动态分区分配方式相同。v空闲盘块的分配与内存的动态分配类似，同样可以用首次、最佳、最坏适应法。盘块的回收也同内存的回收方式类似。起始空闲盘块号盘块数2493155。空闲块链是另一种空闲块的组织方法，它用一种链结构把所有空闲块链接在一起。分配：当系统建立文件需分配空闲块时，从链中摘取所需的空闲块，然后调整链首指针。回收：反之

8、，当回收空闲块时;把释放的空闲块逐个插入链首。9.3.2 9.3.2 空闲链表法空闲链表法v这种方法只需在系统中保留一个链首指针，令其指向第一个空闲块。v这种方法的优点是简单，但工作效率较低，因为每次在链上增加和移出空闲块时，需要做I/O操作。v例如把一空闲块插入链时，要把链首指针(原指向第一个空闲块)写该空闲块中，然后让链首指针指向该空闲块。从链中摘取空闲块时也要读取下一个空闲块的指针。9.3.3 9.3.3 位图法位图法系统为磁盘建立一张位图，在位图中每个物理块占1位，按物理块的顺序排列。1表示对应的物理块已占用，0表示空闲。分配时首先在位图中找到为分配时首先在位图中找到为0的位，然后转换

9、成对应的物理块号，的位，然后转换成对应的物理块号，分配给申请者，并把相应的位置为分配给申请者，并把相应的位置为1。回收时先将释放的物理块号转回收时先将释放的物理块号转换成相应的位，并把这一位置为换成相应的位，并把这一位置为0。位图的大小依据物理磁盘的容位图的大小依据物理磁盘的容量而定。如量而定。如360KB的软盘，每个物理块的软盘，每个物理块为为512字节，位图只占用字节，位图只占用90个字节。个字节。UNIX采用此法采用此法v在 UNIX中 中 有 一 个 整 型 数 组s_freel00和一个整型变量s_nfree。v将所有的空闲盘块分组，每100个空闲盘块为一组。最后一组的块号填入s_f

10、ree、块数赋于s_nfree。其余各组的块号则分别存放在它的下一组的第一个盘块中。9.3.4 9.3.4 成组链接法成组链接法图解图解假设共有假设共有387个空闲块个空闲块分配分配分分 配配 空空 闲闲 盘盘 块块 时，总 是 分 配s_frees_nfree所 指 的 盘 块，并 且s_nfree减1。当发现是直接管理的最后一个盘块时，即s_nfree=l时，就将该盘块中的索引表写入到s_nfree和s_free中，使得下一组变为直接管理。如此类推直到最后一组。释放释放释放空闲盘块释放空闲盘块时，将其块号登记在s_free表中第一个未被占用的项。例如，若s_nfree的原先值为87，则将释

11、放块号登记在s_free88中，然后s_nfree加1。若在登记之前发现s_free已满，则将s_free1至s_free100的内容复写到要释放的盘块中。这样原来直接管理的100空闲盘块变为由释放块间接管理。然后将此该释放块的块号填入s_free1 把s_nfree置为1。9.4 9.4 磁盘容错技术磁盘容错技术磁盘容错技术：vSFT-1：低级磁盘容错技术，主要用于防止磁盘表面发生缺陷所引起的数据丢失；vSFT-2：中级磁盘容错技术，主要用于防止磁盘驱动器和磁盘控制器故障引起的系统不能正常工作；vSFT-3：高级磁盘容错技术。9.4.1 9.4.1 第一级容错技术第一级容错技术1.双份目录和

12、双份文件分配表 v文件目录和文件分配表是文件管理所需的重要数据结构。v在系统每次启动时都要进行两份目录和分配表的检查。2.2.热修复重定向和写后读校验热修复重定向和写后读校验 磁盘表面有少量缺陷时，采取一些补救措施后可继续使用。这些措施主要用于防止将数据写入有缺陷的盘块中。v热修复重定向v写后读校验系统将一定的磁盘容量（如2%-3%）作为热修复重定向区。例如：系统要向第3柱2头1扇区写数据，但发现该扇区是坏的时，便将数据写到热修复区（如200柱16头1扇区）。以后要读3柱2头1扇区的数据时，便从200柱16头1扇区中读。热修复重定向热修复重定向写后读校验写后读校验为了保证所有写入到磁盘的数据都

13、能写入完好的盘块中，应该在每次写数据时，又立即从磁盘上读出该块数据，并同写前的数据进行对比（校验）。若两者不一致，则认为盘块有缺陷，便将该数据写入到热修复区。并对该坏盘块进行登记。9.4.2 9.4.2 第二级容错技术第二级容错技术 第一级容错只能用于防止磁盘表面部分故障造成的数据丢失。如果磁盘驱动器或磁盘控制器发生故障，则第一级容错就无能为力了。v1.磁盘镜像 v2.磁盘双工1.1.磁盘镜像磁盘镜像磁盘驱动器故障的容错。在同一磁盘控制器控制下，增设一个完全相同的磁盘驱动器。每次将数据写主磁盘时，同时将数据也写入到备份磁盘。一个磁盘驱动器发生故障时，必须立即发出警告，尽快修复。磁盘利用率为50

14、%2.2.磁盘双工磁盘双工磁盘控制器或控制器与CPU之间的通道故障的容错。将两台磁盘驱动器分别接到两个磁盘控制器上。两个磁盘上的数据完全相同。RAID(Redundant Arrays of Inexpensive Disk)。由伯克利提出，广泛用于大中型计算机和网络中。由一台磁盘阵列控制器控制一组磁盘驱动器，组成一个高度可靠、快速的大容量磁盘系统。v1.并行交叉存取 v2.RAID分级 v3.RAID的优点9.4.3 9.4.3 廉价磁盘冗余阵列廉价磁盘冗余阵列1.1.并行交叉存取并行交叉存取v加快访问速度v在系统中有多台磁盘驱动器（N）。v存放数据时，将数据的第一块放在第一个磁盘上，第N块

15、放在第N个磁盘上。v这样可以并行读写，极大地提高了速度。2.RAID2.RAID分级分级 RAID0RAID7vRAID0提供并行交叉存取（没有冗余能力）至少两个盘vRAID1两个盘，并行交叉存取，并把一个磁盘的数据镜像到另一个磁盘上。利用率50%。比传统镜像盘快。图图磁盘磁盘0磁盘磁盘1数据数据0数据数据1 1的备份的备份CPU数据数据1数据数据0 0的备份的备份vRAID3利用一个校验盘来完成容错。vRAID5无专门校验盘，校验数据分布在多个盘上。一个磁盘故障时，控制器可从其他尚存的磁盘上重新恢复/生成丢失的数据而不影响数据的可用性。常用于I/O较频繁的事务处理。v可靠性高。除了RAID0

16、，其余各级都采用了容错技术。某个磁盘损坏时，不会造成数据丢失。v速度快。可并行存取。v性能/价格比高。利用RAID技术实现的大容量快速存储器，同大型磁盘系统相比，体积和价格都是后都的1/3。可靠性更高。3.RAID3.RAID的优点的优点9.4.4 9.4.4 后备系统后备系统容量和安全性考虑，需要后备系统。v1.后备系统的类型 v2.拷贝方法1.1.后备系统的类型后备系统的类型v磁带机：最广泛。v硬盘：v光盘：很有前途。2.2.拷贝方法拷贝方法v完全转储：定期将所有文件拷贝到后援存储器。v增量转储：只转储修改过的文件，即两次备份之间的修改，减少系统开销。9.5 9.5 文件系统性能的改善文件

17、系统性能的改善文件系统的性能可表现在多个方面v文件的访问速度v数据的可共享性v文件系统使用的方便性v数据的安全和一致性。提高磁盘提高磁盘I/OI/O速度的方法速度的方法v磁盘高速缓存v优化数据分布v其它方法9.5.1 9.5.1 磁盘高速缓存磁盘高速缓存v磁盘的I/O速度要比内存低4-6个数量级v分配一些内存作为磁盘高速缓存可以极大地提高磁盘I/O速度。磁盘高速缓存的形式磁盘高速缓存的形式在内存中开辟一个单独的存储空间作为磁盘高速缓存。把所有未利用的内存空间变为一个缓冲池，供分页系统和磁盘I/O共享。数据交付数据交付 数据交付：将磁盘高速缓存中的数据传送给请求者进程。当有访问请求时，系统看所需

18、的块是否在高速缓存中。如果在，则可直接访问缓存。否则，首先要将块读到高速缓存，再拷贝到所需的地方。数据交付有两种方式：v数据交付：将数据从缓存传到进程空间v指针交付：将指向缓存中数据的指针传给进程。v如果高速缓存已满，则需要进行淘汰。v常用置换算法：最近最久未使用LRU、最少使用LFU等。置换算法置换算法周期性写回磁盘周期性写回磁盘vLRU算法中，那些经常被访问的盘块可能会一直保留在高速缓存中，而长期不被写回磁盘中。留下了安全隐患。v解决之道：周期性写回。周期性地强行将已修改盘块写回磁盘。周期一般为几十秒。9.5.2 9.5.2 优化数据的分布优化数据的分布v优化物理块的分布 v优化索引结点的

19、分布优化物理块的分布优化物理块的分布 优化一个文件的物理块分布，使访问该文件时，磁头的移动距离最小。v物理块连续分配可以减少磁头的移动。v增加物理块的大小也可减少磁头的移动。优化索引结点的分布优化索引结点的分布 访问文件时，先要访问索引结点，然后再访问文件数据。以前一般将索引结点集中放在磁盘的开始部分，使得索引结点同文件数据之间的平均距离是磁道数的一半。v因此可将索引结点放在中间位置。v进一步可将磁道分组，每组都有索引结点和文件数据。9.5.3 9.5.3 提高磁盘提高磁盘I/OI/O速度的其它方法速度的其它方法v提前读 v延迟写 v虚拟盘提前读提前读在访问文件时经常是顺序访问，因此在读当前块

20、时可以提前读出下一块。提前读已经被广泛应用：UNIX、OS/2、Netware等。延迟写延迟写修改缓存中的数据后一般应立即写回磁盘，但该盘块可能还会被修改，立即写回会带来很大的开销。置上延迟写标志。直到该盘块淘汰时或周期性写回时。延迟写也被广泛应用：UNIX、OS/2 等。虚拟盘虚拟盘利用内存仿真磁盘，又称RAM盘。虚拟盘同磁盘高速缓存的区别：v虚拟盘的内容完全由用户控制，用户可虚拟盘的内容完全由用户控制，用户可见。见。v缓存的内容完全由系统控制，用户不可缓存的内容完全由系统控制，用户不可见。见。9.6 9.6 数据一致性控制数据一致性控制 数据一致性的概念在数据库中出现较多。v事务v检查点v

21、并发控制9.6.1 9.6.1 事务事务1.事务（Transaction）的定义 v事务是用于访问和修改各种数据项的一个程序单位。v事务具有原子性：事务的操作要么全部完成，要么一个也不做。v事务的操作全部完成时要执行提交（commit）操作。事务失败时要执行退回（Rolled back）操作。2.2.事务记录事务记录v记录事务运行时所有对数据项的修改信息。v又称运行日志（Log）。v该记录包括：v事务名 事务的唯一标识v数据项名 被修改的数据项标识v旧值v新值v当一个事务提交时，将一个提交记录也写入事务记录表中。3.3.恢复算法恢复算法 当系统发生故障后，利用事务记录进行故障恢复。搜索整个事务

22、记录表：v对于已经提交了的事务，执行redo操作v对于未提交事务，执行undo操作9.6.2 9.6.2 检查点检查点1.检查点（Check points）的作用 随着系统的运行，事务记录表会变得越来越大，这样当发生故障时，搜索整个事务记录表来进行恢复就是一件非常费时的工作。因而引入检查点。系统每隔一段时间便写一条检查点记录到事务记录表，并进行恢复工作，即：对已经提交的事务执行redo，未提交的事务执行undo。这样在检查点这个时刻，系统中数据的一致性和完整性肯定能得到保证。2.2.新的恢复算法新的恢复算法在引入检查点后，当发生故障后，只需对最后一个检查点以后开始的事务执行恢复工作。9.6.3

23、 9.6.3 并发控制并发控制在多进程或多用户系统中，可能有多个事务在并发执行，这些事务对数据的修改应该是互斥的。（参见第二章进程同步）可以利用PV操作来实现互斥。但在数据库和文件服务器中，应用得最多的还是较简单且灵活的同步机制：锁。1.1.互斥锁互斥锁当事务访问一数据项时，给它上锁，访问完后开锁。2.2.互斥锁和共享锁互斥锁和共享锁v互斥锁可以简单实现事务的并发控制，但会影响并发度。v因为当一个事务读一个数据项进，另一事务应该也能读同一数据项，但上互斥锁时没有这种可能。v所以引入共享锁：事务读对象时申请共享锁，若该对象未上锁或上的是共享锁，则可以申请到。事务写对象时申请互斥锁，只有对象未上锁时才能申请到。