第八章磁盘存储器的管理.

第八章磁盘存储器的管理8.1外存组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制8.1外存的组织方式8.1.1连续组织方式1．连续分配方式——顺序式文件要求为每一个文件分配一组相邻接的盘块。通常都位于一条磁道上，进行读/写时不必移动磁头。顺序文件：把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，所形成的文件结构。连续分配保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。物理地址查询：目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(盘块数)。磁盘空间的连续分配1230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr153mail216list293f72目录trf外存碎片：随着空间的分配和空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件。紧凑：将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。2．连续分配的主要优缺点(1)顺序访问容易。从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。(2)顺序访问速度快。文件所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少。连续分配对文件访问的速度是几种存储空间分配方式中最高的一种。缺点：(1)要求有连续的存储空间。会产生出许多外部碎片，降低外存空间的利用率。定期利用紧凑方法消除碎片，需花费大量的时间。(2)必须事先知道文件的长度。在有些情况下，文件的大小只能靠估算。估计过小，就可能因存储空间不足不能存放。用户往往将文件长度估得比实际的大，严重地浪费外存空间。（3）对于动态增长的文件，采用预分配存储空间的方法，显然很低效。8.1.2链接组织方式——链接式文件1．隐式链接文件目录的每个目录项中，含有指向链接文件第一个盘块和最后一个盘块的指针。在每个盘块中都含有一个指向下一个盘块的指针。如果指针占用4个字节，对于盘块大小为512字节的磁盘，则每个盘块中只有508个字节可供用户使用。磁盘空间的链接式分配25123056749101181314151217181916212223202526272429303128filestartendjeep925目录101-116缺点：1)只适合顺序访问，对随机访问极其低效。必须从文件的第一个盘块读起，顺序查找至第i块。当i=100时，须启动100次磁盘，速度相当低。2)只通过链接指针将一大批离散的盘块链接起来，其可靠性较差，只要其中的任何一个指针出现问题，都会导致整个链的断开。2．显式链接显式链接：把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。称为文件分配表FAT。整个磁盘仅设置一张。表的序号即物理盘块号，从0到N。每个表项中存放指向下一个盘块号的链接指针。每个链首指针所对应的盘块号，填入相应文件的FCB的“物理地址”字段中。通过FAT表，将一个文件的所有的盘块链接起来，将文件的第一个盘块号放在各自的FCB中。显式链接结构012345物理块号2FCBFAT04518.1.3FAT和NTFS技术1．FAT121)以盘块为基本分配单位早期MS-DOS操作系统所使用的是FAT12文件系统。每个表项中存放下一个盘块号。若有1.2MB的软盘，每个盘块的大小为512B，在每个FAT中共含有2.4K个表项，由于每个FAT表项占12位，故FAT表占用3.6KB的存储空间。MS-DOS的文件物理结构6EOF11105EOF0123456789FATFCBA4FCBB9以盘块为分配单位时，所允许的最大磁盘容量。FAT-12系统：在FAT表中最多允许有4096个表项，以盘块(512字节)为分配单位；每个磁盘分区的容量为2MB。一个物理磁盘支持4个逻辑磁盘分区，所以相应的磁盘最大容量仅为8MB。2)簇的基本概念磁盘容量不断增大，在进行盘块分配时不再以盘块而是以簇(cluster)为基本单位。簇：一组连续的扇区，大小一般是2n个盘块，4扇区、8扇区等。簇包含扇区的数量与磁盘容量的大小直接有关。一个簇有一个扇区：磁盘的最大容量为8MB；一个簇有两个扇区：磁盘的最大容量为16MB；一个簇有八个扇区：磁盘的最大容量为64MB。在相同磁盘容量下，FAT表的项数与簇的大小成反比。以簇作为基本的分配单位的优点：(1)能适应磁盘容量不断增大的情况。(2)使FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；缺点：会造成更大的簇内零头。3)FAT12存在的问题(1)对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但相应的簇内碎片也将随之成倍地增加。(2)只能支持8+3格式的文件名。2．FAT16将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65536(216)个簇。FAT16:具有16位表宽的FAT表。FAT16的每个簇的盘块数:4、8、16、32、64。FAT16可以管理的最大分区空间：216×64×512=2048MB=2G。FAT16对FAT12的局限性有所改善，但改善很有限。当磁盘容量迅速增加时，形成的簇内碎片所造成的浪费也越大。例如，当要求磁盘分区的大小为8GB时，则每个簇的大小达到128KB，内部零头最大可达到128KB。为了解决这一问题，微软推出了FAT32。3．FAT32FAT16表的长度只有65535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零头，也就应当增加FAT表的长度。也就由FAT16演变为FAT32。FAT32是FAT系列文件系统的最后一个产品。每一簇在FAT表中的表项占据4字节，FAT表可以表示4294967296项(232)。允许在FAT32中采用较小的簇。FAT32的每个簇都固定为4KB(每簇用8个盘块代替FAT16的64个盘块),每个盘块仍为512字节。FAT32分区格式可以管理的单个最大磁盘空间大到2TBFAT中簇的大小与最大分区的对应关系块大小/KBFAT12/MBFAT16/MBFAT32/TB0.52142812841625618512216102423220482三种FAT类型的最大分区以及所对应的块的大小如下图所示。8.1.4．NTFS1)NTFS新特征NTFS：专门为WindowsNT开发的、全新的文件系统，并适用于Windows2000/XP/2003。NTFS特征：1）使用了64位磁盘地址，理论上可以支持264次方字节的磁盘分区；2）在NTFS中可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为32767个字符；3）具有系统容错功能；4）提供了数据的一致性；此外，NTFS还提供了文件加密、文件压缩等功能。2)磁盘组织以簇作为磁盘空间分配和回收的基本单位。一个文件占用若干个簇，一个簇只属于一个文件。通过簇来间接管理磁盘，可以不需要知道盘块(扇区)的大小，使NTFS具有了与磁盘物理扇区大小无关的独立性。在NTFS文件系统中，簇的大小使用4KB。8.1.5索引组织方式——索引式文件1．单级索引分配链接分配方式存在两个问题：(1)不能支持高效的直接存取。要在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。需要整个FAT表进内存。事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。将每个文件所对应的盘块号集中地放在一起。索引分配原理：为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中。目录表对应目录项中填上指向该索引块的指针。索引分配方式123056749101181314151217181916212223202526272429303128countfile块序号jeep19目录91611025－1－1－1192．多级索引分配当文件很大，索引块太多时，要为索引块再建立索引，便形成了两级索引分配方式。文件非常大时，还可用三级、四级索引分配方式。两级索引分配012……………105106254356357985105106254740356357…1125985360740…1125…主索引360第二级索引磁盘空间两级索引分配方式下各索引块之间的链接情况。如果盘块的大小为1KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时，最多可包含的存放文件的盘块的盘块号总数N=256×256=64K个盘块号。则采用两级索引时，所允许的文件最大长度为64MB。若盘块的大小为4KB，在采用单级索引时所允许的最大文件长度为4MB；而在采用两级索引时所允许的最大文件长度可达4GB。3．混合索引分配方式/增量式索引组织方式混合索引分配方式：将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式、两级索引分配方式、三级索引分配方式。混合索引分配方式已在UNIX系统中采用。在UNIXSystemⅤ的索引结点中，共设置了13个地址项，即iaddr(0)～iaddr(12)。都把所有的地址项分成两类：直接地址和间接地址。假如每个盘块的大小为4KB，索引块中每个索引项占4B。1)直接地址（文件在0~40KB之间）10个直接地址项：iaddr(0)～iaddr(9)，来存放直接地址。即每项中存放的是该文件的盘块号。2)一次间接地址(文件介于40K和4M之间）一个一级索引分配：地址项iaddr(10)提供一次间接地址。一次间址块中可存放1K个盘块号，因而允许文件长达4MB。3)多次间接地址—文件长度介于4MB+40KB和4G地址项iaddr(11)提供二次间接地址。采用二次间址方式时，文件最大长度可达4GB。地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4TB。混合索引方式modeowners(2)timestamps(3)sizeblockcounti.addr(0)i.addr(1)directblockssingleindirectdoubleindirecttripleindirectdatadatadatadata……datadata………datadatadatadata8.2文件存储空间的管理8.2.1空闲表法和空闲链表法1．空闲表法1)空闲表—连续分配方式系统为外存上的所有空闲区建立一张空闲表；每个空闲区对应于一个空闲表项：包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。所有空闲区按其起始盘块号递增的次序排列。查表后为每个文件分配一块连续的存储空间。空闲盘块表序号第一空闲盘块号空闲盘块数12429331554——对于文件系统，当文件较小(1～4个盘块)时，采用连续分配方式，为文件分配相邻接的几个盘块；当文件较大时，便采用离散分配方式。2)存储空间的分配与回收与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。分配：先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。回收：也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。2．空闲链表法将所有空闲盘区拉成一条空闲链。链表分成两种形式：空闲盘块链和空闲盘区链。(1)空闲盘块链。分配时从链首开始，依次摘下适当数目的空闲盘块分配给用户。将回收的盘块依次插入空闲盘块链的末尾。优点：分配和回收一个盘块的过程非常简单；缺点：为一个文件分配盘块时，可能要重复操作多次。(2)空闲盘区链。将磁盘上的所有空闲盘区拉成一条链。每个盘区上含有指向下一个空闲盘区的指针，以及本盘区大小(盘块数)的信息。分配：通常采用首次适应算法。回收