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

广东工业大学 计算机学院网络工程系 刘冬宁第八章 磁盘存储器的管理Outline8.1 外存的组织方式8.2 文件存储空间的管理8.3 提高磁盘I/O速度的途径8.4 提高磁盘可靠性的技术（自学内容）8.5 数据一致性控制（自学内容）8.1外存的组织方式外存的组织方式8 8.1 1.1 1连续组织方式连续组织方式连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图8-1 示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count文件的第一个盘块号是0，文件长度为2，因此是在盘块号为0和1的两盘块中存放文件1的数据。图8-1磁盘空间的连续分配1230567491011813141512171819162122232025262724list29303128mailcountfilestart lengthcount 02tr153mail216list293f72目 录trf如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。例如，可以运行一个再装配例程(repack routine)，由它将磁盘A上的大量文件拷贝到一张软盘B或几张软盘(C，D，)上，并释放原来的A盘，使之成为一个空闲盘。然后再将软盘B(C，D，)上的文件拷回A盘上。这种方法能将含有多个文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。2连续分配的主要优缺点连续分配的主要优缺点连续分配的主要优点如下：(1)顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从b块开始存放的文件中的第i个盘块的内容，就可直接访问b+i号盘块。(2)顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。连续分配的主要缺点如下：(1)要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。(2)必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。在有些情况下，知道文件的大小是件非常容易的事，如可拷贝一个已存文件。但有时却很难，在此情况下，只能靠估算。如果估计的文件大小比实际文件小，就可能因存储空间不足而中止文件的拷贝，须再要求用户重新估算，然后再次执行。这样，显然既费时又麻烦。这就促使用户往往将文件长度估得比实际的大，甚至使所计算的文件长度比实际长度大得多，显然，这会严重地浪费外存空间。对于那些动态增长的文件，由于开始时文件很小，在运行中逐渐增大，比如，这种增长要经历几天、几个月。在此情况下，即使事先知道文件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存储空间长期地空闲着。8 8.1 1.2 2链接分配链接分配1 1隐式链接隐式链接在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。图6-8 中示出了一个占用5个盘块的链接式文件。在相应的目录项中，指示了其第一个盘块号是9，最后一个盘块号是25。而在每个盘块中都含有一个指向下一个盘块的指针，如在第一个盘块9中设置了第二个盘块的盘块号是16；在16号盘块中又设置了第三个盘块的盘块号1。如果指针占用4个字节，对于盘块大小为512字节的磁盘，则每个盘块中只有508个字节可供用户使用。图8-2磁盘空间的链接式分配25123056749101181314151217181916212223202526272429303128filestartendjeep925目 录101-116隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块，就这样顺序地查找直至第i块。当i=100时，须启动100次磁盘去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。2 2显式链接显式链接这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，如图6-9所示。表的序号是物理盘块号，从0开始，直至N-1；N为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT(File Allocation Table)。图8-3显式链接结构012345物 理 块 号2FCBFAT04518 8.1 1.3 3FATFAT和和NTFSNTFS技术技术1 1FATFAT12121)以盘块为基本分配单位早期MS-DOS操作系统所使用的是FAT12文件系统，在每个分区中都配有两张文件分配表FAT1和FAT2，在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。图8-4示出了MS-DOS的文件物理结构，这里示出了两个文件，文件A占用三个盘块，其盘块号依次为4、6、11；文件B则依次占用9、10及5号三个盘块。每个文件的第一个盘块号放在自己的FCB中。整个系统有一张文件分配表FAT。在FAT的每个表项中存放下一个盘块号。对于1.2 MB的软盘，每个盘块的大小为512 B，在每个FAT中共含有2.4 K个表项，由于每个FAT表项占12位，故FAT表占用3.6 KB的存储空间。图8-4MS-DOS的文件物理结构6EOF11105EOF0123456789FATFCB A4FCB B9现在我们来计算以盘块为分配单位时，所允许的最大磁盘容量。由于每个FAT表项为12位，因此，在FAT表中最多允许有4096个表项，如果采用以盘块作为基本分配单位，每个盘块(也称扇区)的大小一般是512字节，那么，每个磁盘分区的容量为2 MB(4096512 B)。同时，一个物理磁盘支持4个逻辑磁盘分区，所以相应的磁盘最大容量仅为8 MB。这对最早时期的硬盘还可应付，但很快磁盘的容量就超过了8 MB，FAT12是否还可继续用呢，回答虽是肯定的，但需要引入一个新的分配单位簇。2)簇的基本概念为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n(n为整数)个盘块，在MS-DOS的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个扇区(1 KB)、四个扇区(2 KB)、八个扇区(4 KB)等。一个簇应包含扇区的数量与磁盘容量的大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为8 MB；当一个簇包含两个扇区时，磁盘的最大容量可以达到16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到64 MB。由上所述可以看出，以簇作为基本的分配单位所带来的最主要的好处是，能适应磁盘容量不断增大的情况。值得注意的是，使用簇作为基本的分配单位虽可减少FAT表中的项数(在相同的磁盘容量下，FAT表的项数是与簇的大小成反比的)。这一方面会使FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头(它与存储器管理中的页内零头相似)。3)FAT12存在的问题尽管FAT12曾是一个不错的文件系统，但毕竟已老化，已不能满足操作系统发展的需要，其表现出来的主要问题是，对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。此外，它只能支持8+3格式的文件名。2 2FATFAT1616对FAT12所存在的问题进行简单的分析即可看出，其根本原因在于，FAT12表最多只允许4096个表项，亦即最多只能将一个磁盘分区分为4096个簇。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。由此可以得出解决方法，那就是增加FAT表的表项数，亦即应增加FAT表的宽度，如果我们将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65 536(216)个簇。我们把具有16位表宽的FAT表称为FAT16。在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64，由此得出FAT16可以管理的最大分区空间为216 64 512=2048 MB。由上述分析不难看出，FAT16对FAT12的局限性有所改善，但改善很有限。当磁盘容量迅速增加时，如果再继续使用FAT16，由此所形成的簇内碎片所造成的浪费也越大。例如，当要求磁盘分区的大小为8 GB时，则每个簇的大小达到128 KB，这意味着内部零头最大可达到128 KB。一般而言，对于14 GB的硬盘来说，大约会浪费1020的空间。为了解决这一问题，微软推出了FAT32。3 3FATFAT3232如同存储器管理中的分页管理，所选择的页面越大，可能造成的页内零头也会越大。为减少页内零头就应该选择适当大小的页面。在这里，为了减小磁盘的簇内零头，也就应当选择适当大小的簇。问题是FAT16表的长度只有65 535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零头，也就应当增加FAT表的长度。为此，需要再增加FAT表的宽度，这样也就由FAT16演变为FAT32。FAT32是FAT系列文件系统的最后一个产品。每一簇在FAT表中的表项占据4字节(232)，FAT表可以表示4 294 967 296项，即FAT32允许管理比FAT16更多的簇。这样就允许在FAT32中采用较小的簇，FAT32的每个簇都固定为4 KB，即每簇用8个盘块代替FAT16的64个盘块，每个盘块仍为512字节，FAT32分区格式可以管理的单个最大磁盘空间大到4 KB232=2 TB。三种FAT类型的最大分区以及所对应的块的大小如图8-5所示。图8-5 FAT中簇的大小与最大分区的对应关系块大小/KB FAT12/MB FAT16/MB FAT32/TB 0.5 2 1 4 2 8 128 4 16 256 1 8 512 2 16 1024 2 32 2048 2 4 4NTFSNTFS（自学内容自学内容）1)NTFS新特征NTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Windows 2000/XP/2003。NTFS具有许多新的特征：首先，它使用了64位磁盘地址，理论上可以支持2的64次方字节的磁盘分区；其次，在NTFS中可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为32 767个字符；第三，具有系统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行；第四，提供了数据的一致性，这是一个非常有用的功能，我们将在本章的最后一节介绍；此外，NTFS还提供了文件加密、文件压缩等功能。2)磁盘组织同FAT文件系统一样，NTFS也是以簇作为磁盘空间分配和回收的基本单位。一个文件占用若干个簇，一个簇只属于一个文件。通过簇来间接管理磁盘，可以不需要知道盘块(扇区)的大小，使NTFS具有了与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是512字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。在NTFS文件系统中，把卷上簇的大小称为“卷因子”，卷因子是在磁盘格式化时确定的，其大小同FAT一样，也是物理磁盘扇区的整数倍，即一个簇包含2n(n为整数)个盘块，簇的大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以为512 B、1 KB、2 KB，最大可达64 KB。对于小磁盘(512 MB)，默认簇大小为512字节；对于1 GB磁盘，默认簇大小为1 KB；对于2 GB磁盘，则默认簇大小为4 KB。事实上，为了在传输效率和簇内碎片之间进行折中，NTFS在大多数情况下都是使用4 KB。3)文件的组织在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(Master File Table)中。该表是NTFS 卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT 表中占有一行，其中还包括MFT 自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。在MFT表中，每个元数据将其所对应文件的所有信息，包括文件的内容等，都被组织在所对应文件的一组属性中。由于文件大小相差悬殊，其属性所需空间大小也相差很大，因此，在MFT表中，对于元数据的1 KB空间，可能记录不下文件的全部信息。所以当文件较小时，其属性值所占空间也较小，可以将文件的所有属性直接记录在元数据中。而当文件较大时，元数据仅记录该文件的一部分属性，其余属性，如文件的内容等，可以记录到卷中的其它可用簇中，并将这些簇按其所记录文件的属性进行分类，分别链接成多个队列，将指向这些队列的指针保存在元数据中。6 6.3 3.4 4索引分配索引分配1 1单级索引分配单级索引分配链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题：(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。当磁盘容量较大时，FAT可能要占用数兆字节以上的内存空间，这是令人难以接受的。事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。图8-6 示出了磁盘空间的索引分配图。图8-6索引分配方式123056749101181314151217181916212223202526272429303128countfile块 序 号jeep19目 录91611025111192 2多级索引分配多级索引分配当OS为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。图8-7示出了两级索引分配方式下各索引块之间的链接情况。如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时，最多可包含的存放文件的盘块的盘块号总数N=256 256=64 K个盘块号。由此可得出结论:采用两级索引时，所允许的文件最大长度为64 MB。倘若盘块的大小为4 KB，在采用单级索引时所允许的最大文件长度为4 MB；而在采用两级索引时所允许的最大文件长度可达4 GB。图8-7两级索引分配01210510625435635798510510625474035635711259853607401125主索引360第二级索引磁盘空间3 3混合索引分配方式混合索引分配方式所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。这种混合索引分配方式已在UNIX系统中采用。在UNIX System 的索引结点中，共设置了13个地址项，即iaddr(0)iaddr(12)，如图9-8所示。在BSD UNIX的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。图8-8混合索引方式modeowners(2)time stamps(3)sizeblock counti.addr(0)i.addr(1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata1)直接地址为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据所在盘块的盘块号。假如每个盘块的大小为 4 KB，当文件不大于40 KB时，便可直接从索引结点中读出该文件的全部盘块号。2)一次间接地址对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1 K个盘块号，因而允许文件长达4 MB。3)多次间接地址当文件长度大于4 MB+40 KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4 GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4 TB。8.2文件存储空间的管理文件存储空间的管理8 8.2 2.1 1空闲表法和空闲链表法空闲表法和空闲链表法1 1空闲表法空闲表法1)空闲表空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，如图8-9所示。图8-9空闲盘块表序 号 第一空闲盘块号 空闲盘块数 1 2 4 2 9 3 3 15 5 4 2)存储空间的分配与回收空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。在内存分配上，虽然很少采用连续分配方式，然而在外存的管理中，由于这种分配方式具有较高的分配速度，可减少访问磁盘的I/O频率，故它在诸多分配方式中仍占有一席之地。例如，在前面所介绍的对换方式中，对对换空间一般都采用连续分配方式。对于文件系统，当文件较小(14个盘块)时，仍采用连续分配方式，为文件分配相邻接的几个盘块；当文件较大时，便采用离散分配方式。2空闲链表法空闲链表法空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链和空闲盘区链。(1)空闲盘块链。这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。这种方法的优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复操作多次。(2)空闲盘区链。这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时，为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。8.2.2位示图法位示图法1位示图位示图位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用m n个位数来构成位示图，并使m n等于磁盘的总块数，如图8-10所示。位示图也可描述为一个二维数组map：Var map:array of bit；图8-10位示图 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 2 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 3 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 4 16 2盘块的分配盘块的分配根据位示图进行盘块分配时，可分三步进行：(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j 式中，n代表每行的位数。(3)修改位示图，令mapi,j=1。3盘块的回收盘块的回收盘块的回收分两步：(1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i=(b-1)DIV n+1j=(b-1)MOD n+1(2)修改位示图。令mapi,j=0。这种方法的主要优点是，从位示图中很容易找到一个或一组相邻接的空闲盘块。例如，我们需要找到6个相邻接的空闲盘块，这只需在位示图中找出6个其值连续为“0”的位即可。此外，由于位示图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行盘区分配时，无需首先把盘区分配表读入内存，从而节省了许多磁盘的启动操作。因此，位示图常用于微型机和小型机中，如CP/M、Apple-DOS等OS中。8.2.3成组链接法成组链接法1空闲盘块的组织空闲盘块的组织(1)空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号(最多含100个号)，以及栈中尚有的空闲盘块号数N。顺便指出，N还兼作栈顶指针用。例如，当N=100时，它指向S.free(99)。由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一把锁。图8-11左部示出了空闲盘块号栈的结构。其中，S.free(0)是栈底，栈满时的栈顶为S.free(99)。图8-11空闲盘块的成组链接法1004003993013001003002992022012991004003992013019907999790179007899780179997901空 闲 盘块 号 栈S.free019899(2)文件区中的所有空闲盘块被分成若干个组，比如，将每100个盘块作为一组。假定盘上共有10 000个盘块，每块大小为1 KB，其中第2017999号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为79017999；次末组为78017900；第二组的盘块号为301400；第一组为201300，如图 8-11右部所示。(3)将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)S.free(99)中。这样，由各组的第一个盘块可链成一条链。(4)将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。(5)最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为99，不应是100，因为这是指可供使用的空闲盘块，其编号应为(199)，0号中放空闲盘块链的结尾标志。2空闲盘块的分配与回收空闲盘块的分配与回收当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。8.3 8.3 提高磁盘提高磁盘I/0I/0速度的途径速度的途径5 5.6 6.3 3磁盘高速缓存磁盘高速缓存1 1磁盘高速缓存的形式磁盘高速缓存的形式这里所说的磁盘高速缓存，并非通常意义下的内存和CPU之间所增设的一个小容量高速存储器，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。高速缓存在内存中可分成两种形式。第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享。此时，高速缓存的大小显然不再是固定的。当磁盘I/O的频繁程度较高时，该缓冲池可能包含更多的内存空间；而在应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间。2 2数据交付方式数据交付方式数据交付(Data Delivery)是指将磁盘高速缓存中的数据传送给请求者进程。当有一进程请求访问某个盘块中的数据时，由核心先去查看磁盘高速缓冲器，看其中是否存在进程所需访问的盘块数据的拷贝。若有其拷贝，便直接从高速缓存中提取数据交付给请求者进程，这样，就避免了访盘操作，从而使本次访问速度提高46个数量级；否则，应先从磁盘中将所要访问的数据读入并交付给请求者进程，同时也将数据送高速缓存。当以后又需要访问该盘块的数据时，便可直接从高速缓存中提取。系统可以采取两种方式将数据交付给请求进程：(1)数据交付。这是直接将高速缓存中的数据，传送到请求者进程的内存工作区中。(2)指针交付。这是只将指向高速缓存中某区域的指针交付给请求者进程。后一种方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存到进程的内存工作区的时间。3 3置换算法置换算法如同请求调页(段)一样，在将磁盘中的盘块数据读入高速缓存时，同样会出现因高速缓存中已装满盘块数据而需要将该数据先换出的问题。相应地，也必然存在着采用哪种置换算法的问题。较常用的置换算法仍然是最近最久未使用算法LRU、最近未使用算法NRU及最少使用算法LFU等。由于请求调页中的联想存储器与高速缓存(磁盘I/O中)的工作情况不同，因而使得在置换算法中所应考虑的问题也有所差异。因此，现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：1)访问频率通常，每执行一条指令时，便可能访问一次联想存储器，亦即联想存储器的访问频率，基本上与指令执行的频率相当。而对高速缓存的访问频率，则与磁盘I/O的频率相当。因此，对联想存储器的访问频率远远高于对高速缓存的访问频率。2)可预见性在高速缓存中的各盘块数据，有哪些数据可能在较长时间内不会再被访问，又有哪些数据可能很快就再被访问，会有相当一部分是可预知的。例如，对二次地址及目录块等，在它被访问后，可能会很久都不再被访问。又如，正在写入数据的未满盘块，可能会很快又被访问。3)数据的一致性由于高速缓存是做在内存中的，而内存一般又是一种易失性的存储器，一旦系统发生故障，存放在高速缓存中的数据将会丢失；而其中有些盘块(如索引结点盘块)中的数据已被修改，但尚未拷回磁盘，因此，当系统发生故障后，可能会造成数据的不一致性。基于上述考虑，在有的系统中便将高速缓存中的所有盘块数据拉成一条LRU链。对于那些会严重影响到数据一致性的盘块数据和很久都可能不再使用的盘块数据，都放在LRU链的头部，使它们能被优先写回磁盘，以减少发生数据不一致性的概率，或者可以尽早地腾出高速缓存的空间。对于那些可能在不久之后便要再使用的盘块数据，应挂在LRU链的尾部，以便在不久以后需要时，只要该数据块尚未从链中移至链首而被写回磁盘，便可直接到高速缓存中(即LRU链中)去找到它们。4 4周期性地写回磁盘周期性地写回磁盘还有一种情况值得注意:那就是根据LRU算法，那些经常要被访问的盘块数据，可能会一直保留在高速缓存中，长期不会被写回磁盘。(注意，LRU链意味着链中任一元素在被访问之后，总是又被挂到链尾而不被写回磁盘；只是一直未被访问的元素，才有可能移到链首，而被写回磁盘。)例如，一位学者一上班便开始撰写论文，并边写边修改，他正在写作的论文就一直保存在高速缓存的LRU链中。如果在快下班时，系统突然发生故障，这样，存放在高速缓存中的已写论文将随之消失，致使他枉费了一天的劳动。为了解决这一问题，在UNIX系统中专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。一般是把两次调用SYNC的时间间隔定为30 s。这样，因系统故障所造成的工作损失不会超过30 s的劳动量。而在MS-DOS中所采用的方法是:只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘，并将这种高速缓存称为“写穿透、高速缓存”(write-through cache)。MS-DOS所采用的写回方式，几乎不会造成数据的丢失，但须频繁地启动磁盘。8 8.3 3.2 2提高磁盘提高磁盘I/OI/O速度的其它方法速度的其它方法1 1提前读提前读(Read(Read-ahead)ahead)用户(进程)对文件进行访问时，经常采用顺序访问方式，即顺序地访问文件各盘块的数据。在这种情况下，在读当前块时可以预知下一次要读的盘块。因此，可以采取预先读方式，即在读当前块的同时，还要求将下一个盘块(提前读的块)中的数据也读入缓冲区。这样，当下一次要读该盘块中的数据时，由于该数据已被提前读入缓冲区，因而此时便可直接从缓冲区中取得下一盘块的数据，而不需再去启动磁盘I/O，从而大大减少了读数据的时间。这也就等效于提高了磁盘I/O的速度。“提前读”功能已被广泛采用，如在UNIX系统、OS/2，以及在3 Plus和Netware等的网络OS中，都已采用该功能。2 2延迟写延迟写延迟写是指在缓冲区A中的数据，本应立即写回磁盘，但考虑到该缓冲区中的数据在不久之后可能还会再被本进程或其它进程访问(共享资源)，因而并不立即将该缓冲区A中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾。随着空闲缓冲区的使用，缓冲区也缓缓往前移动，直至移到空闲缓冲队列之首。当再有进程申请到该缓冲区时，才将该缓冲区中的数据写入磁盘，而把该缓冲区作为空闲缓冲区分配出去。当该缓冲区A仍在队列中时，任何访问该数据的进程，都可直接读出其中的数据而不必去访问磁盘。这样，又可进一步减小等效的磁盘I/O时间。同样，“延迟写”功能已在UNIX系统、OS/2等OS中被广泛采用。3 3优化物理块的分布优化物理块的分布另一种提高磁盘I/O速度的重要措施是优化文件物理块的分布，使磁头的移动距离最小。虽然链接分配和索引分配方式都允许将一个文件的物理块分散在磁盘的任意位置，但如果将一个文件的多个物理块安排得过于分散，会增加磁头的移动距离。例如，将文件的第一个盘块安排在最里的一条磁道上，而把第二个盘块安排在最外的一条磁道上，这样，在读完第一个盘块后转去读第二个盘块时，磁头要从最里的磁道移到最外的磁道上。如果我们将这两个数据块安排在属于同一条磁道的两个盘块上，显然会由于消除了磁头在磁道间的移动，而大大提高对这两个盘块的访问速度。4 4虚拟盘虚拟盘所谓虚拟盘，是指利用内存空间去仿真磁盘，又称为RAM盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行，不是在磁盘上而是在内存中。这些对用户都是透明的。换言之，用户并不会发现这与真正的磁盘操作有什么不同，而仅仅是略微快些而已。虚拟盘的主要问题是：它是易失性存储器，故一旦系统或电源发生故障，或系统再启动时，原来保存在虚拟盘中的数据将会丢失。因此，虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。虚拟盘与磁盘高速缓存的主要区别在于:虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。例如，RAM盘在开始时是空的，仅当用户(程序)在RAM盘中创建了文件后，RAM盘中才有内容。8 8.3 3.3 3廉价磁盘冗余阵列廉价磁盘冗余阵列1 1并行交叉存取并行交叉存取为了提高对磁盘的访问速度，已把在大、中型机中应用的交叉存取(Interleave)技术应用到了磁盘存储系统中。在该系统中，有多台磁盘驱动器，系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上。在以后，当要将一个盘块的数据传送到内存时，采取并行传输方式，将各个盘块中的子盘块数据同时向内存中传输，从而使传输时间大大减少。例如，在存放一个文件时，可将该文件中的第一个数据子块放在第一个磁盘驱动器上；将文件的第二个数据子块放在第二个磁盘上；将第N个数据子块，放在