第8章磁盘存储器管理.

1第八章磁盘存储器的管理2磁盘存储器管理8.1外存的组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制38.1外存的组织(分配）方式磁盘具有可直接访问的特性，利用磁盘来存放文件具有灵活性。在为文件分配外存空间时考虑的主要问题有：有效利用外存空间提高对文件的访问速率8.1.1连续组织8.1.2链接组织8.1.3FAT8.1.3NTFS技术8.1.4索引组织4文件的三大物理结构1连续分配（连续/顺序结构）2链接分配（链接结构）(FAT和NTFS技术)3索引分配（索引结构）①连续结构:文件信息存于外存储器的若干连续块中；②链接结构：文件信息散布在外存储器的若干不连续块中，由指针连接起来；③索引结构：文件信息散存于外存储器的若干块中，另外建立一个索引表，表中存有该记录在外存储器位置的对应关系58.1.1连续分配(又称“顺序分配”)1.连续分配方式（ContinuousAllocation）存储结构：文件分配一组连续的盘块文件地址：第一盘块号和文件长度（图8-1）外存碎片：通过紧缩将外存空闲空间合并成连续的区域2.连续分配的优缺点优点：①顺序访问容易②顺序访问速度快缺点：①要求有连续的磁盘空间②必须事先知道文件的长度P251TU8-11230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr153mail216list293f72目录trf图8-1磁盘空间的连续分配678.1.2链接组织（ChainedAllocation）存储结构文件分配到离散的盘块中，通过链接指针将这些离散的盘块链成一个链表。链接的形式1.隐式链接2.显式链接81.隐式链接每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针(图6-8)主要问题：只适合顺序访问，随机访问极其低效如要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块……，这样顺序地查找直至第i块。可见，随机访问的速度相当低。可靠性较差。只要其中的任何一个指针出现问题，都会导致整个链的断开。TU8-225123056749101181314151217181916212223202526272429303128filestartendjeep925目录101-116图8-2磁盘空间的链接式分配（隐式）9102.显式链接把链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张(图8-3所示)表中凡是属于某一文件的第一个盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。显著提高了检索速度，大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故该表有称为文件分配表(FileAllocationTable)MS-DOS的文件物理结构(FAT)TU8-3012345物理块号2FCBFAT0451图8-3显式链接结构11128.1.3FAT和NTFS技术早期MS-DOS的FAT文件系统引入“卷”，支持一个物理磁盘分成4个逻辑磁盘（卷、分区），每个分区都是一个能够被单独格式化和使用的逻辑单元，供文件系统分配空间时使用每个分区包含:文件系统信息+一组文件+空闲空间，并有单独存放目录和FAT表的区域1.FAT122.FAT163.FAT324.NTFS131.FAT121)以盘块为基本分配单位早期MS-DOS使用FAT12文件系统，每个分区中配有两张文件分配表FAT1和FAT2，FAT的每个表项中存放下一个盘块号，通过它将文件的所有盘块链接起来，而文件的第一个盘块号放在FCB中。•MS-DOS的文件物理结构图8-4•整个系统有一张文件分配表FATTU8-46EOF11105EOF0123456789FATFCBA4FCBB9图8-4MS-DOS的文件物理结构文件A占3个盘块，盘块号为4、6、11；文件B则占用9、10及5号3个盘块。每个文件的第一个盘块号放在自己的FCB中。14151.FAT12对1.2MB的软盘，盘块大小为512B，FAT中共含有2.4K个表项，由于每个FAT表项占12位，故FAT表占用3.6KB的存储空间以盘块为分配单位时最大磁盘容量问题每个FAT表项12位，FAT表中最多允许有4096项；盘块大小是512B,每个磁盘分区的容量为2MB(4096×512B)。一个物理磁盘支持4个逻辑分区，相应的磁盘最大容量仅为8MB。8MB对最早时期的硬盘还可应付，但很快容量就超过了，FAT12还能继续用?Yes.引入新的分配单位——簇。161.FAT12例如:簇仅有一个扇区时，磁盘的最大容量为8MB；簇包含两个扇区时，磁盘的最大容量可达16MB；簇包含八个扇区时，磁盘的最大容量可达64MB。2)簇的基本概念进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n个盘块簇包含扇区的数量与磁盘容量的大小直接有关171.FAT123)FAT12存在的问题所允许的磁盘容量存在着严重的限制，通常只能是几十个Megabytes，虽可继续增加簇的大小来提高最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。只能支持8+3格式的文件名1816位最大表项数65536(216)个，可将一个磁盘分区分为65536个簇。在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64，由此得出FAT16可以管理的最大分区空间为216×64×512=2048MB。2.FAT16问题FAT12所存在的问题的根本原因在于，FAT12表最多只允许4096个表项，亦即最多只能将一个磁盘分区分为4096个簇。随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。解决方法增加FAT表的表项数，即增加FAT表的宽度192.FAT16有改善，但改善有限。当磁盘容量较大时，使用FAT16，所形成的簇内碎片所造成的浪费会很大。例如当磁盘分区大小为8GB时，则每簇的大小达到128KB，这意味着内部零头最大可达到128KB。一般对1～4GB的硬盘来说，大约会浪费10％～20％的空间。为了解决这一问题，微软推出了FAT3220FAT系列文件系统的最后一个产品。FAT32文件系统的每一簇在FAT表中的表项占据4B(232)，FAT表可以表示4294967296项。FAT32中采用较小的簇，每个簇都固定为4KB，每个盘块仍为512B，FAT32分区格式可以管理的单个最大磁盘空间大到4KB×232=16TB。实际上，FAT32仅使用28位簇标识符，在簇大小为4KB时，最大磁盘空间大到1TB，若簇大小为8KB，则最大可为2TB。3.FAT3221三种FAT中簇大小与最大分区的对应关系块大小/KBFAT12/MBFAT16/MBFAT32/TB0.52142812841625618512216102423220482228.1.4NTFS技术1)NTFS新特征NTFS(NewTechnologyFileSystem)是一个专门为WindowsNT开发的、全新的文件系统，并适用于Windows2000/XP/2003及后续使用64位磁盘地址，理论上可支持2的64次方字节的磁盘分区在NTFS中可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为32767个字符；具有系统容错功能:出现故障或差错时，仍能保证系统正常运行；提供了数据的一致性；提供了文件加密、压缩等功能。23NTFS2)磁盘组织NTFS也是以簇作为磁盘空间分配和回收的基本单位。一个文件占用若干个簇，一个簇只属于一个文件通过簇间接管理磁盘，不需要知道扇区的大小，使NTFS具有与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是512字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。卷上簇的大小称为“卷因子”，它是在磁盘格式化时确定的，其大小也是物理磁盘扇区的整数倍，即一个簇包含2n个盘块，簇的大可以为512B、1KB、2KB……64KB248.1.5索引组织（IndexAllocation）链接分配方式解决了连续分配方式存在的问题，但出现了另外两个问题：1、不支持直接存取(FAT中顺序查找盘块号)2、FAT需占用较大的内存空间(只有将整个FAT调入内存，才能保证在FAT中找到文件的所有盘块号)1.单级索引分配2.多级索引分配3.增量式分配方式解决方法：FAT部分调入内存（基于这种想法，形成索引分配方法）251.单级索引分配每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块是个数组。文件的目录项中填上指向该索引块的指针(图8-6)支持高效的直接存取(索引表)主要问题：花费较多的外存空间（小文件）TU8-6123056749101181314151217181916212223202526272429303128countfile块序号jeep19目录91611025－1－1－119图8-6索引分配方式26272.多级索引分配当文件盘块号装满一个索引块时，需要再分配另一个索引块，可通过链指针将各索引块按序链接起来。当文件太大，其索引块太多，这种方法低效。解决方法：为索引块建立索引，称为第一级索引，形成两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式(图8-7)例如：盘块大小1KB，每个盘块号占4B，那么一个索引块中可存放256个盘块号。在两级索引时，最多可存放的盘块号总数N=256×256=64K个，允许的文件最大长度为64MB。TU8-7012……………105106254356357985105106254740356357…1125985360740…1125…主索引360第二级索引磁盘空间图8-7两级索引分配28293.增量式（混合）分配方式多种索引分配方式相结合而形成的一种分配方式。例如：系统既采用直接地址，又采用一级索引分配，或两级索引分配，甚至还采用了三级索引分配方式。这种混合索引分配方式在UNIX系统中采用。在UNIXSystemⅤ的索引结点中，共设置了13个地址项，即iaddr(0)～iaddr(12)(图8-8)。在BSDUNIX的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址modeowners(2)timestamps(3)sizeblockcounti.addr(0)i.addr(1)directblockssingleindirectdoubleindirecttripleindirectdatadatadatadata……datadata………datadatadatadata图8-8增量式（混合）索引方式3031直接地址：在索引结点中可设置10个直接地址项，即用iaddr(0)～iaddr(9)来存放直接地址。假如盘块大小为4KB，当文件不大于40KB时，便可直接从索引结点中读出该文件的全部盘块号一次间接地址：利用索引结点中的地址项iaddr(10)来提供一次间接地址(同二级索引：每个盘块号占4B,盘块个数1KB),。实质就是一级索引分配方式（大、中型文件，文件长达4MB）多次间接地址：文件大于4MB+40KB时，须采用二次间址分配方式。地址项iaddr(11)提供二次间接地址，实质是两级索引分配方式，此时文件最大长度可达4GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4TBunix操作系统上，如果一个块的大小是1KB,一个盘块号占4个字节(一个盘块有256个地址)。请把下面的文件字节偏移量转换为物理地址：（1）9999（2）18000（3）14000032P276，11（1）9999逻辑块号：9999/1024=9块内偏移量为:9999-9*1024=783逻辑块号＜10,直