计算机操作系统第四版汤小丹梁红兵哲凤屏_第7章(2016-2017-1)

第八章磁盘存储器的管理第八章磁盘存储器的管理8.1外存的组织文件8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制第八章磁盘存储器的管理8.1外存的组织方式8.1.1连续组织方式 文件的物理结构直接与外存的组织方式有关；不同的外存组织方式，将形成不同的文件物理结构。 连续组织方式形成顺序式的文件结构。外存的组织方式：连续组织方式、链接组织方式、索引组织方式第八章磁盘存储器的管理1.隐式链接图8-2磁盘空间的链接式分配8.1.2链接组织方式 几个盘块组成一个簇，以簇为单位进行分配。第八章磁盘存储器的管理2.显式链接8.1.2链接组织方式 文件分配FAT(FileAllocationTable)存放分配给文件的所有盘块号。第八章磁盘存储器的管理8.1.5索引组织方式1.单级索引组织方式第八章磁盘存储器的管理2.多级索引组织方式8.1.5索引组织方式第八章磁盘存储器的管理2.多级索引分配两级索引分配第八章磁盘存储器的管理图8-8混合索引方式3.增量式索引组织方式8.1.5索引组织方式第八章磁盘存储器的管理(1)直接地址。为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)~iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据的盘块的盘块号。假如每个盘块的大小为4KB，当文件不大于40KB时，便可直接从索引结点中读出该文件的全部盘块号。3.增量式索引组织方式8.1.5索引组织方式第八章磁盘存储器的管理(2)一次间接地址。对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1K个盘块号，因而允许文件长达4MB。3.增量式索引组织方式8.1.5索引组织方式第八章磁盘存储器的管理(3)多次间接地址。当文件长度大于4MB+40KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4TB。3.增量式索引组织方式8.1.5索引组织方式第八章磁盘存储器的管理思考题1：请分别解释在连续分配方式、隐式链接分配方式、显式链接分配方式和索引分配方式中如何将文件的字节偏移量3500转换为物理块号和块内位移量（设盘块大小为1KB，盘块号需占4个字节）。第八章磁盘存储器的管理思考题2：存放在某个磁盘上的文件系统，采用混合索引分配方式，其FCB中共有13个地址项，第0~9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址：（1）该文件系统允许文件的最大长度是多少？（2）将字节的字节偏移量5000、15000转换为物理块号和块内偏移量。（3）假设某个文件的FCB已在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘？第八章磁盘存储器的管理8.2文件存储空间的管理8.2.1空闲表法和空闲链表法1.空闲表法2.空闲链表法空闲链表法：将所有空闲盘区拉成一条空闲链。根据构成链锁的基本元素，分空闲盘块链、空闲盘区链用于连续分配方式分配算法？ 序号 第一空闲盘块号 空闲盘块数 1 2 4 2 9 3 3 15 5 4 — —第八章磁盘存储器的管理8.2.2位示图法1.位示图2.盘块的分配顺序扫描位示图,找出一个或一组值为’0’的二进制。将所找到的一个或一组二进制位，转换成与之相应的盘块号修改位示图map[m,n]第八章磁盘存储器的管理3.盘块的回收(1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示图。令map[i,j]=0。8.2.2位示图法第八章磁盘存储器的管理8.2.3成组链接法第八章磁盘存储器的管理2.空闲盘块的分配与回收当系统要为用户分配文件所需的盘块时，盘块分配过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。8.2.3成组链接法第八章磁盘存储器的管理8.3提高磁盘I/O速度的途径主要从下列三方面提高对文件的访问速度： 改进文件的目录结构以及检索目录的方法来减少对目录的查找时间； 选取好的文件存储结构，以提高对文件的访问速度； 提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反。第八章磁盘存储器的管理8.3.1磁盘高速缓存(DiskCache)指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。高速缓存在内存中有两种形式：第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。第八章磁盘存储器的管理1.数据交付方式数据交付就是将磁盘高速缓存中的数据传送给请求者进程。系统可以采取两种方式，将数据交付给请求进程：(1)数据交付。这是直接将高速缓存中的数据，传送到请求者进程的内存工作区中。(2)指针交付。只将指向高速缓存中某区域的指针，交付给请求者进程。8.3.1磁盘高速缓存(DiskCache)第八章磁盘存储器的管理2.置换算法当高速缓存中已装满盘块数据时，需要运用置换算法将某些盘块过的数据先换出问题。目前，不少系统在其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：(1)访问频率。(2)可预见性。(3)数据的一致性。8.3.1磁盘高速缓存(DiskCache)第八章磁盘存储器的管理3.周期性地写回磁盘在UNIX系统中专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30s。这样，因系统故障所造成的工作损失不会超过30s的劳动量。8.3.1磁盘高速缓存(DiskCache)第八章磁盘存储器的管理8.3.2提高磁盘I/O速度的其它方法1.提前读(Read-Ahead)2.延迟写3.优化物理块的分布4.虚拟盘第八章磁盘存储器的管理8.3.3廉价磁盘冗余阵列(RAID)1.并行交叉存取RAID(RedundantArrayofInexpensiveDisk)系统利用一台磁盘阵列控制器统一管理和控制一组磁盘驱动器，组成一个大型磁盘系统。第八章磁盘存储器的管理8.4提高磁盘可靠性的技术(1)通过存取控制机制来防止由人为因素所造成的文件不安全性。(2)通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。(3)通过“后备系统”来防止由自然因素所造成的不安全性。为确保文件系统的安全性应采取三方面措施：第八章磁盘存储器的管理8.4.1第一级容错技术SFT-Ⅰ(SystemFault-Tolerance)1.双份目录和双份文件分配表在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表和FAT。2.热修复重定向和写后读校验 热修复重定向。系统将磁盘容量的很小一部分作为热修复重定向区，用于存放当发现磁盘有缺陷时的待写数据，并对写入该区的所有数据进行登记。(2)写后读校验方式。每次向磁盘中写入一个数据块后，又立即写入另一缓冲区，并将这两个缓冲区的内容进行比较，以保证它们的一致。第八章磁盘存储器的管理8.4.2第二级容错技术SFT-Ⅱ(1)磁盘镜像(DiskMirroring)主要用于防止由磁盘驱动器和磁盘控制器故障所导致的系统不能正常工作。第八章磁盘存储器的管理(2)磁盘双工(DiskDuplexing)。8.4.2第二级容错技术SFT-Ⅱ第八章磁盘存储器的管理8.5数据一致性控制8.5.1事务1.事务的定义事务是用于访问和修改各种数据项的一个程序单位，是一系列相关读和写操作。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以托付操作(CommitOperation)来终止事务。只要有一个读、写或修改操作失败，便须执行夭折操作(AbortOperation)，也称为回滚操作或取消操作。一个事务在对一批数据执行修改操作时，应该是要么全部完成，并用修改后的数据去代替原来的数据，要么一个也不修改。这体现了事务具有原子性。第八章磁盘存储器的管理2.事务记录(TransactionRecord)①事务名：用于标识该事务的惟一名字；②数据项名：它是被修改数据项的惟一名字；③旧值;④新值8.5.1事务3.恢复算法(1)undo<Ti>。把所有被事务Ti修改过的数据恢复为修改前的值(2)redo<Ti>。把所有被事务Ti修改过的数据设置为新值.原子操作借助于称为事务记录的数据结构来实现。用来记录在事务运行时数据项修改的信息，称为运行记录(Log).第八章磁盘存储器的管理8.5.2检查点1.检查点(CheckPoints)的作用使对事务记录表中事务记录的清理工作经常化，即每隔一定时间便做一次下述工作：首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中；其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中；然后是将事务记录表中的<检查点>记录，输出到稳定存储器中；最后是每当出现一个<检查点>记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。第八章磁盘存储器的管理2.新的恢复算法恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始，返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。如果把所有在事务Ti以后开始执行的事务表示为事务集T，则新的恢复操作是：对所有在T中的事务TK,如果在事务记录表中出现了<TK托付>记录，则执行redo<TK>操作；反之，如果在事务记录表中并未出现<TK托付>记录，则执行undo<TK>操作。8.5.2检查点第八章磁盘存储器的管理8.5.3并发控制1.利用互斥锁实现“顺序性”2.利用互斥锁和共享锁实现顺序性由于事务具有原子性，各个事务的执行必然是按某种次序一次进行的，只有在一个事务执行完后，才允许另一事务执行。这种特性称为顺序性，实现事务顺序性的技术称为并发控制。第八章磁盘存储器的管理8.5.4重复数据的数据一致性问题1.重复文件的一致性为了保证数据的安全性，一般把关键文件或数据结构分别存储在不同的地方。应保证主文件的数据与各备份文件中的数据相一致。第八章磁盘存储器的管理2.链接数一致性检查为每个盘块建立一个表项，其中含有该索引结点号的计数值。在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较，如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。8.5.4重复数据的数据一致性问题