增量式索引组织方式

第八章磁盘存储器的管理目标：掌握文件存储的基本概念和实现过程连续分配、链接分配和索引分配连续分配：连续分配是何种为文件分配存储块的方式？如何对连续分配的文件进行顺序访问或随机访问？这种分配方式有何优缺点？链接分配：链接分配是何种为文件分配存储块的方式？隐式链接分配方式是为了解决什么问题而引入的，它有何不足之处？显式链表结构是如何解决上述不足的，它较适合用哪种场合？这两种分配方式是如何将多个离散的盘块链成一个链表的。索引分配：索引分配是何种为文件分配存储块的方式？为什么要引入索引分配方式，采用索引分配方式时应如何对文件进行访问？当文件很大时又应如何处理？混合索引分配方式是为了解决什么问题而引入的？此时，应如何将文件的逻辑地址转换成物理地址？本章要点（1/5）位示图法和成组链接法位示图法：位示图法的概念。使用位示图如何来进行磁盘块的分配或回收，这种管理方式有何优点？成组链接法：成组链接法的概念。它是如何将盘块进行分组并将各个盘块组链成一个成组链的？它应如何进行盘块的分配和回收，这种管理方式有什么优点？本章要点（2/5）磁盘容错技术SFT-I：引入SFT-I的目的是什么？双份目录和双份文件分配表措施主要是用来解决什么问题？热修复重定向和写后读校验措施又是用来解决什么问题，它们分别是如何解决上述问题？SFT-II：引入SFT-II的目的是什么？磁盘镜像可用来解决什么问题？它对磁盘I/O的速度有什么影响？而磁盘双工是为了解决什么问题而引入的，它对磁盘I/O的速度又有哪些影响？本章要点（3/5）文件系统的数据一致性事务：事务的概念。事务是如何保证数据的一致性的？事务操作和原语操作之间存在着什么区别？在事物操作中引入检查点主要是为了解决什么问题？为什么多个事务的执行具有顺序性？如何实现事务的顺序性？盘块号的一致性检查：盘块一致性检查的目的是什么？盘块号一致性检查软件应如何设置每个盘块的空闲盘块号计数器和数据盘块号计数器的值，为什么这两个计数器的值必须互补？在检查过程中可能出现哪些异常现象，分别应如何解决？本章要点（4/5）文件系统的数据一致性链接计数的一致性检查：为什么要引入链接计数的一致性检查？一致性检查软件是通过什么和文件索引结点中的链接计数字段的比较来进行一致性检查的？在检查过程中可能会出现哪些异常现象，分别应如何解决？本章要点（5/5）8.1外存的组织方式8.2文件存储空间的管理

8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制本章内容对磁盘存储器管理的主要任务和要求是：有效地利用存储空间；采用合理的文件分配方式提高磁盘的I/O速度；采用磁盘调整缓存等提高磁盘系统的可靠性。冗余措施后备系统8磁盘存储器的管理8.1外存的组织方式8.1外存的组织方式

连续组织方式需要连续的磁盘空间文件物理结构是顺序式的文件结构链接组织方式可以为文件分配不连续的磁盘空间，用链接指针链接文件物理结构是链接式文件结构索引组织方式可以为文件分配不连续的磁盘空间，采用索引组织方式文件物理结构是索引式文件结构常用的外存组织方式有：8.1.1连续组织方式

连续分配方式（磁带，磁盘都可采用）每个文件分配一组相邻盘块，通常位于一条磁道上。文件结构：顺序文件结构物理文件：顺序文件文件对应目录项（属性）中包含：始址、总块数、最后一块字节数。优点：顺序访问容易；访问速度快缺点：要求连续空间，一段时间后需利用紧凑消除磁盘碎片必须事先知道文件长度，文件不易动态增长；为保持有序性，文件不能灵活地删除和插入记录。图8-1磁盘空间的连续组织方式连续分配方式

图8-1磁盘空间的连续组织方式（紧凑之后）连续分配方式

8.1.2链接组织方式链接组织方式将一个文件放在不连续的物理块中，每个物理块通过指针链接起来。优点：消除了外部碎片，提高了外存利用率；方便对文件进行插入、删除和修改记录操作。无须事先知道文件长度，根据文件当前需要分配必须的盘块；动态增长时可再分配盘块；缺点：不能支持高效地直接存取链接方式又可分为以下两种：隐式链接显式链接文件目录的每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针。特点：只适合顺序访问，对随机访问效率极低；只通过链接指针来将一大批离散的盘块链接起来，可靠性较差。1、隐式链接

1、隐式链接

图8-2磁盘空间的链接式分配块号下一页下一页的指针（块号）9116162113101042525无-10123页4把用于链接的指针显式存放在内存的一张表(FAT)中，查找在内存中进行。利用文件分配表FAT，记录文件的盘块号。2、显式链接

图8-3显式链接结构8.1.3FAT技术微软公司早、中期推出的操作系统都是采用FAT技术MSDOS：FAT12、FAT16Windows95、Windows98：FAT32WindowsNT/2000/XP：NTFSFAT引入了卷；支持将一个物理磁盘分成四个逻辑磁盘，每个逻辑磁盘就是一个卷（也称分区）；一个卷中包含了文件信息、一组文件以及空闲空间；每个卷专门有一个单独的区存放目录、FAT表和逻辑驱动器字母。图8-4MS-DOS的文件物理结构1、FAT12早期的FAT12文件系统以盘块为基本分配单位每个分区都配有两张相同的文件分配表FAT1和FAT2FAT的每个表项中存放下一个盘块号文件的第一个盘块号放在文件的FCB中每个FAT表项为12位，最多允许有4096个表项，假定每个盘块为512B，每个磁盘分区的容量为2MB，一个物理磁盘最大的容量为8MB1、FAT12以簇为单位的FAT12文件系统簇(cluster)是一组相邻的扇区，为一个虚拟扇区；以簇作为盘块分配的基本单位；簇的大小一般是2n个盘块MS-DOS中簇的容量：1、2、4、8个扇区优点：FAT表占用的存储空间减少；减少访问FAT表的存取开销。缺点：簇内碎片增大；磁盘容量受限，通常只能为数十MB只支持短文件名（8+3）。如果簇的容量为8个扇区，则一个物理磁盘最大的容量为?答案为：最大分区空间为212*8*512B=16MB；物理磁盘最大容量为64MB2、FAT16每个FAT表项为16位，最多允许有65536(64K)个表项簇的容量：4、8、…、64个扇区可以管理的最大分区空间：64KB*64*512B=2GB3、FAT32每个FAT表项为32位，每一簇在表项中占4字节簇的容量：4KB~32KB（即8~64个扇区）可以管理的最大分区空间：232-4*4KB=1TB（设簇的容量为4KB）缺点：文件分配表的扩大，使得运行速度慢于FAT32；FAT32有最小管理空间的限制(4KB)，不支持容量小于512MB的分区；单个文件的长度不能大于4GB；不能保持向下兼容。扇区容量扇区数（盘块数）FAT12FAT16FAT320.5KB12MB1KB24MB2KB48MB128MB4KB816MB256MB1TB8KB16512MB2TB16KB321024MB（1GB）2TB32KB642048MB（2GB）2TB图8-5FAT中簇的大小与最大分区的对应关系8.1.4NTFS的文件组织方式使用64位磁盘地址；支持长文件名：单个文件名255个字符以内；全路径名为32767个字符。具有系统容错功能；能保证系统中数据一致性；提供了对文件加密、压缩等功能。1、NTFS新特征以簇作为磁盘空间分配和回收的基本单位卷上簇的大小也称为“卷因子”，由格式化命令指定；簇的大小可以为：512B、1KB、…、64KB；≤512MB的小磁盘，默认簇大小为512字节；1GB的磁盘，默认簇大小为1KB2GB的磁盘，默认簇大小为4KB簇的定位采用逻辑簇号(LCN)或虚拟簇号(VCN)LCN以卷为单位，整个卷中所有的簇按顺序编号VCN以文件为单位，属于某个文件的簇按顺序编号2、磁盘组织以卷为单位，卷中所有文件信息、目录信息及可用的未分配空间信息，均以记录的形式存储在MFT中。主控文件表(MFT)每个文件一条记录；MFT本身占有一条记录；每条记录固定为1KB；每条记录称为一个文件的元数据，也称文件控制字；每个元数据都将其对应文件的所有信息（包括文件的内容等）组织在所对应文件的一组属性中：文件小，属性直接记录在元数据中；文件大，元数据中只记录文件的一部分属性，其余的保存在其他簇中，将链接指针存在元数据中。3、文件组织8.1.5索引组织方式

链接组织方式存在的问题：不能高效直接存取；FAT需占较大的内存。解决方案：为每个文件分配一个索引块，记录文件的所有盘块号。特点：支持直接访问：文件较大时有利；文件较小时浪费外存空间（还需为小文件建索引块）1、单级索引组织方式图8-6索引分配方式1、单级索引组织方式单级索引组织方式存在的问题：当文件较大时，索引块太多，查找速度减慢解决方案：当索引太大时，则需建立多级索引设一个盘块大小为1KB，每个盘块号占4byte。则2级索引存放的文件的盘块号总数为：256×256=64K，故文件的最大长度为64K×1KB=64MB设一个盘块大小为4KB，每个盘块号占4byte。则2级索引存放的文件的盘块号总数为：1KB×1KB=1MB，故文件的最大长度为1M×4KB=4GB2、多级索引组织方式2、多级索引组织方式图8-7两级索引分配增量式索引组织式的基本思想直接寻址：对于小文件（最多占10个盘块），将文件的每一个盘块地址都直接放到FCB（或索引结点）中；一次间址：对中等文件，采用单级索引组织方式，FCB中存放的是文件的索引表；二次/三次间址：对大型和特大型文件，采用两级和三级索引组织方式。增量式索引组织方式：又称为混合组织方式，既采用了直接寻址方式，又采用了单级和多级索引组织方式（间接寻址）。UNIX系统中采用了这种组织方式。3、增量式索引组织方式UNIXSystemV的组织方式索引结点设有13个地址项，iaddr(0)~iaddr(12)；设每个盘块大小为4KB，一索引项占4字节；直接地址：用iaddr(0)~iaddr(9)来存放直接地址，称为直接盘块号，小文件（<40K)可直接从索引结点读出文件的全部盘块。一次间接地址：利用索引结点中的地址项iaddr(10)来提供一次间址，一次间址块可存放1K个盘块号，允许文件长达4MB。多次间接地址：当文件长度大于4MB+40KB时，用地址项iaddr(11)提供二次间址，文件最大长度可达4GB。地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4TB。3、增量式索引组织方式图8-8混合索引方式8.2文件存储空间的管理8.2文件存储空间的管理为文件分配磁盘时，需要的数据结构包括：文件分配表（FAT）磁盘分配表（DAT）磁盘空间的基本分配单位：磁盘块文件存储空间的管理方法：空闲表法和空闲链表法位示图法成组链接法8.2.1空闲表法和空闲链表法

1、空闲表法（属于连续分配方式）分配：首次/循环首次/最佳/最坏回收：判断是否合并。由于连续分配比较快，因此对对换空间及小文件的管理适用。图8-9空闲盘块表序号第一空闲盘块号空闲盘块数12429331554——2、空闲链表法空闲盘块链将磁盘上的所有空闲空间以盘块为单位串成一条链，每一个盘块都有指向后继盘块的指针。优点：用于分配和回收一个盘块的过程非常简单缺点：可能该链很长，在为一个文件分配盘块时，可能要重复操作多次，分配和回收效率很低。空闲盘区链将磁盘上的所有空闲盘区串成一条链，每个盘区含有：用于指示下一个空闲盘区的指针、指明本盘区大小的信息一个盘区含多个盘块，类似于内存分区分配与回收(合并)分配通常采用首次适应算法，为了提高对空闲盘区的检索速度，可采用显式链接方法。8.2.2位示图法位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况，0表示盘块空闲，1表示已分配。1、位示图图8-10位示图2、盘块的分配：顺序扫描，找一个或一组=0的块；根据找到的行/列得以盘块号。b=n(i-1)+j；(n代表每行的位数)修改位图，令map[i,j]=1。3、盘块的回收：由磁块号得(i,j)i=(b-1)div(n+1)j=(b-1)mod(n+1)修改位图：令map[i,j]=0特点：易于访问；占空间少，可放入内存，查找速度快。8.2.3成组链接法

空闲表法和空闲链表法都不适用于大型文件系统。UNIX系统中采用的是成组链接法，将上述两种方法相结合形成一种空闲盘块管理方法。s-nfree:空闲块数s_free[100]：空闲块块号s_flock：锁位空闲盘块号栈文件区中的所有空闲盘块，被分成若干个组将每一组含有的盘块总数N和该组所有的盘块号，记入其前一组的第一个盘块的S.free(0)~S.free(99)中。将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)~S.free(99)中。1、空闲盘块的组织

1、空闲盘块的组织图8-11空闲盘块的成组链接法2、空闲盘块的分配与回收1）分配首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。2、空闲盘块的分配与回收

2）回收将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。8.3提高磁盘I/O速度的途径8.3提高磁盘I/O速度的途径提高对文件的访问速度，有三种途径：改进文件的目录结构以及检索目录的方法，以减少对目录的查找时间；选取好的文件存储结构，以提高对文件的访问速度；提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中。最主要的技术是采用磁盘高速缓存。8.3.1磁盘高速缓存(DiskCache)磁盘高速缓存是指在内存中为磁盘盘块设置的一个缓冲区，在缓冲区中保存了某些盘块的副本；逻辑上是磁盘、物理上是驻留在内存中的盘块；固定大小和可变大小。设计磁盘高速缓存时需要考虑的问题：如何将磁盘高速缓存中的数据传送给请求进程；采用什么样的置换策略；已修改的盘块数据在何时被写回磁盘。数据交付：指将磁盘高速缓存中的数据传送给请求者进程数据交付方式：数据交付：直接将高速缓存中的数据传送到请求者进程的内存工作区中。指针交付：只将指向高速缓存中某区域的指针交付给请求者进程。常用算法：最近最久未使用算法LRU最近未使用算法NRU最少使用算法LFU1、数据交付方式2、置换算法置换时需考虑的因素：访问频率；可预见性；数据的一致性。置换的策略：对于会严重影响到数据一致性的盘块数据和很久都可能不再使用的盘块数据，都放在LRU链的头部，使它们优先写回磁盘。经常被访问的盘块一直保留在调整缓存中，会移至LRU的链尾；一直未被访问的元素有可能移到链首，会被写回磁盘。在UNIX中用系统调用SYNC实现2、置换算法3、周期性地写回磁盘

8.3.2提高磁盘I/O速度的其它方法提前读延迟写访问频率高的磁盘块放在替换队列的尾部，减少回写次数优化物理块的分布目的是减小磁头移动距离簇分配方式：一个簇为多个连续的块虚拟盘虚拟盘：利用内存空间仿真磁盘，又称为RAM盘虚拟盘可以接受所有标准的磁盘操作，常用于存放临时文件和磁盘高速缓存区别：虚拟盘由用户控制；磁盘高速缓存由系统控制。8.3.3廉价磁盘冗余阵列

廉价磁盘冗余阵列RAID（RedundantArraysofInexpensiveDisk）：是利用一台磁盘阵列控制器，来统一管理和控制一组（几台到几十台）磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统1、并行交叉存取

图8-12磁盘并行交叉存取方式通过把多个磁盘组织在一起，作为一个逻辑卷提供磁盘跨越功能。通过把数据分成多个数据块，并行写入/读出多个磁盘，以提高访问磁盘的速度。通过镜像或校验操作，提供容错能力。2、RAID的分级RAID0仅提供并行交叉存取。具有并行读写功能，提高了磁盘的I/O速度，但无冗余校验功能。RAID1提供磁盘镜像功能。具有并行读写功能，提高了磁盘的I/O速度，但磁盘的利用率仅50%。RAID3具有并行传输功能的磁盘阵列。用一台奇偶校验盘容错。RAID5具有独立传输功能的磁盘阵列。每个驱动区有自己独立的数据通道。无专门的校验盘，校验信息以螺旋方式分布在每个盘上。RAID6RAID7RAID6设有一个专用的、快速访问的异步校验盘。RAID7是对RAID6的改进。所有盘都有较高的传输率及优异的性能提供并行交叉存取；能有效提高磁盘I/O速度；无冗余校验功能，磁盘系统的可靠性差。RAID0中逻辑磁盘与物理磁盘间的映射关系具有镜像功能；具有并行读写功能，提高了磁盘的I/O速度，但磁盘的利用率仅50%。采用了早期的错误检测与修正技术----汉明码（HammingCode）校验技术进行即时数据校验，冗错性较好；一个硬盘在一个时间只存取一位的信息，但具有极高的数据传输率；RAID2中的硬盘数量取决于所设定的数据存储宽度；系统成本极高，对冗余的数据传输率要求较高。注：汉明码的数量与数据位的数量之间比例公式为，2P≥P+D+1，P代表汉明码的个数，D代表数据位的个数具有并行传输功能的磁盘阵列；用一台奇偶校验盘容错；磁盘利用率为（N-1）/N；常用于科学计算和图像处理。独立的数据硬盘与共享的校验硬盘；按数据块为单位进行存储；在不同硬盘上的同级数据块也都通过XOR进行校验，结果保存在单独的校验盘；相对较高的读取传输率，极差的写入传输率（在写入时要等一个硬盘写完后才能写一下个，并且还要写入校验数据）。具有独立传输功能的磁盘阵列；每个驱动区有自己独立的数据通道；无专门的校验盘，校验信息以螺旋方式分布在每个盘上；常用于I/O较频繁的事务处理。设置了一个专用的、可快速访问的异步校验盘；具有独立的数据访问通道；具有比RAID3级及RAID5级更好的性能，但性能改进很有限；价格昂贵。3、RAID的优点

可靠性高。(2)

磁盘I/O速度高。(3)性能/价格比高。

8.4提高磁盘可靠性的技术8.4提高磁盘可靠性的技术确保文件系统安全性措施：存取控制机制：防止人为因素系统容错技术：防止系统因素后备系统：防止自然因素容错技术：通过在系统中设置冗余部件的办法，提高系统可靠性的一种技术。磁盘容错技术：通过增加冗余的磁盘驱动器、磁盘控制器等，来提高磁盘系统的可靠性的一种技术。磁盘容错技术分为三级：SFT-I是低级磁盘容错技术SFT-II是中级磁盘容错技术SFT-III是系统高级容错技术SFT-I是最基本的磁盘容错技术，主要用于防止磁盘表面发生缺陷所引起的数据丢失，包括：1、双份目录和双份文件分配表2、热修复重定向和写后读校验热修复重定向：系统将磁盘容量的很小一部分（2%~3%）作为热修复重定向，用于存放当发现磁盘有缺陷时的待写数据。写后读校验方式。8.4.1第一级容错技术SFT-ISFT-II主要用于防止磁盘驱动器和磁盘控制器故障所引起的系统不正常工作，包括：1、磁盘镜像(DiskMirroring)图8-13磁盘镜像示意8.4.2第二级容错技术SFT-II2、磁盘双工(DiskDuplexing)

图8-14磁盘双工示意集群：是一组相互独立的、通过高速网络互联的计算机，它们构成统一的计算机系统，并以单一系统的模式加以管理。一个客户与集群相互作用时，集群像是一个独立的服务器。集群系统的工作模式有：热备份模式互为备份模式公用磁盘模式8.4.4基于集群技术的容错功能两台完全相同的服务器，一主一从，各装入一块网卡，通过一条镜像服务器链路MSL连接。平时主服务器运行，备份服务器监视。主服务器出现故障，备份服务器自动切换成主服务器。如果采用FDDI单模光纤，两台服务器间的距离可达20公里。系统中必须设置某种机制检测主服务器中数据的改变。优点：提高了可用性，易于实现，支持远程热备。缺点：系统使用效率只有50%。1、双机热备份模式图8-15双机热备份模式两台服务器均为在线服务器，各自完成自己的任务，它们之间通过某种专线连接；服务器上的两台硬盘，一个用于装载系统程序和应用程序，另一个用于接收另一台服务器发来的备份数据。优点：两台服务器都可处理任务，系统效率高。2、双机互为备份模式图8-16双机热备份模式将多台计算机连接到一台公共的磁盘系统上，每台计算机使用磁盘的一个卷。某台计算机发生故障，系统将重新进行配置，根据某种策略选择另一台替代机器，替代机器对发生故障的机器的卷拥有所有权，可接替故障计算机所承担的任务。优点：消除了信息复制的时间，减少了网络和服务器的开销3、公用磁盘模式配备后备系统的原因：磁盘系统不够大，无法容纳系统运行过程中所有的数据；措施：把暂时不需要但仍然有用的数据存放在后备系统中。防止系统发生故障或病毒。措施：将比较重要的数据存放在后备系统中。后备系统的常用设备：磁带机硬盘光盘驱动器8.4.5后备系统8.5数据一致性控制8.5.1事务

1.事务的定义事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看作是一系列相关读和写操作。被访问的数据可以分散地存放在同一文件的不同记录中，也可放在多个文件中。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以托付操作(CommitOperation)来终止事务。只要有一个读、写或修改操作失败，便须执行夭折操作(AbortOperation)。读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导致的。事务操作具有“原子性”。事务记录存储在稳定存储器中，用来记录在事务运行时数据项修改的全部信息，又称为运行记录（log）。记录包含下列字段：事务名：

用于标识该事务的惟一名字；数据项名：

它是被修改数据项的惟一名字；旧值：

修改前数据项的值；新值：

修改后数据项将具有的值。事务记录表中的每一记录，描述了在事务运行中的重要事务操作：修改操作、开始事务、托付事务、夭折事务等2、事务记录(TransactionRecord)3、恢复算法

恢复算法可利用以下两个过程：

(1)undo〈Ti〉。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。

(2)redo〈Ti〉。该过程能把所有被事务Ti修改过的数据，设置为新值。如果系统发生故障，系统应对以前所发生的事务进行清理。8.5.2检查点

引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化。事务记录清理工作的步骤：首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中；将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中；将事务记录表中的〈检查点〉记录，输出到稳定存储器中；每当出现一个〈检查点〉记录时，系统便执行恢复操作，利用redo和undo过程实现恢复功能。1、检查点(CheckPoints)的作用

2、新的恢复算法

恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始，返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。如果把所有在事务Ti以后开始执行的事务表示为事务集T，则新的恢复操作要求是：对所有在T中的事务TK,如果在事务记录表中出现了