第8章汤小丹,计算机操作系统,官方课件,第四版,计算机,操作系统,课件,.

1第八章磁盘存储器的管理第八章磁盘存储器的管理8.1外存的组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制习题2第八章磁盘存储器的管理 8.1外存的组织方式如前所述，文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有：(1)连续组织方式。(2)链接组织方式。(3)索引组织方式。3第八章磁盘存储器的管理8.1.1连续组织方式连续组织方式又称连续分配方式，要求为每一个文件分配一组相邻接的盘块。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2，…。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头。在采用连续组织方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。4第八章磁盘存储器的管理图8-1磁盘空间的连续组织方式5第八章磁盘存储器的管理连续组织方式的主要优点有：(1)顺序访问容易。(2)顺序访问速度快。6第八章磁盘存储器的管理连续组织方式的主要缺点如下：(1)要求为一个文件分配连续的存储空间。(2)必须事先知道文件的长度。(3)不能灵活地删除和插入记录。(4)对于那些动态增长的文件。7第八章磁盘存储器的管理8.1.2链接组织方式如果可以将文件装到多个离散的盘块中，就可消除连续组织方式的上述缺点。在采用链接组织方式时，可为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。链接组织方式的主要优点是：(1)消除了磁盘的外部碎片，提高了外存的利用率。(2)对插入、删除和修改记录都非常容易。(3)能适应文件的动态增长，无需事先知道文件的大小。8第八章磁盘存储器的管理1.隐式链接在采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。9第八章磁盘存储器的管理图8-2磁盘空间的链接式分配10第八章磁盘存储器的管理2.显式链接这是指把用于链接文件各物理块的指针显式地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，如图8-3所示。11第八章磁盘存储器的管理图8-3显式链接结构12第八章磁盘存储器的管理8.1.3FAT技术1. FAT121)早期的FAT12文件系统FAT12是以盘块为基本分配单位的。由于FAT是文件系统中最重要的数据结构，为了安全起见，在每个分区中都配有两张相同的文件分配表FAT1和FAT2。在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。13第八章磁盘存储器的管理图8-4MS-DOS的文件物理结构14第八章磁盘存储器的管理2)以簇为单位的FAT12文件系统稍加分析便可看出，如果把每个盘块(扇区)的容量增大n倍，则磁盘的最大容量便可增加n倍。但要增加盘块的容量是不方便和不灵活的。为此，引入了簇(cluster)的概念。15第八章磁盘存储器的管理2. FAT16FAT12对磁盘容量限制的原因在于，FAT12表中的表项有限制，亦即最多只允许4096个。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。16第八章磁盘存储器的管理3. FAT32由于FAT16表的长度只有65 535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零，也就应当增加FAT表的长度，为此需要再增加FAT表的宽度，这样也就由FAT16演变为FAT32。17第八章磁盘存储器的管理图8-5FAT中簇的大小与最大分区的对应关系18第八章磁盘存储器的管理8.1.4NTFS的文件组织方式1.NTFS新特征NTFS(NewTechnologyFileSystem)是一个专门为WindowsNT开发的、全新的文件系统，并适用于Windows2000/XP及后续的WindowsOS。19第八章磁盘存储器的管理2.磁盘组织NTFS是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，一个簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，即使NTFS具有了与磁盘物理块大小无关的独立性。20第八章磁盘存储器的管理3.文件的组织在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(MasterFileTable)中，该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。21第八章磁盘存储器的管理8.1.5索引组织方式1.单级索引组织方式链接组织方式虽然解决了连续组织方式所存在的问题(即不便于随机访问)，但又出现了另外两个问题，即：①不能支持高效的直接存取，要对一个较大的文件进行存取，须在FAT中顺序地查找许多盘块号；②FAT需占用较大的内存空间，由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。22第八章磁盘存储器的管理图8-6索引分配方式23第八章磁盘存储器的管理2.多级索引组织方式在为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS须再为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。24第八章磁盘存储器的管理图8-7两级索引分配25第八章磁盘存储器的管理3.增量式索引组织方式1)增量式索引组织方式的基本思想为了能较全面地照顾到小、中、大及特大型作业，可以采取多种组织方式来构成文件的物理结构。如果盘块的大小为1 KB或4 KB，对于小文件(如1 KB～10 KB或4 KB～40 KB)而言，最多只会占用10个盘块，为了能提高对数量众多的小型作业的访问速度，最好能将它们的每一个盘块地址都直接放入文件控制块FCB(或索引结点)中，这样就可以直接从FCB中获得该文件的盘块地址。26第八章磁盘存储器的管理2) UNIXSystemV的组织方式在UNIXSystemV的索引结点中设有13个地址项，即i.addr(0)～i.addr(12)，如图8-8所示。(1)直接地址。(2)一次间接地址。(3)多次间接地址。27第八章磁盘存储器的管理图8-8混合索引方式28第八章磁盘存储器的管理 8.2文件存储空间的管理8.2.1空闲表法和空闲链表法1.空闲表法1)空闲表空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表，如图8-9所示。29第八章磁盘存储器的管理图8-9空闲盘块表30第八章磁盘存储器的管理2)存储空间的分配与回收空闲盘区的分配与内存的分区(动态)分配类似，同样是采用首次适应算法和最佳适应算法等，它们对存储空间的利用率大体相当，都优于最坏适应算法。在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。31第八章磁盘存储器的管理2.空闲链表法1)空闲盘块链这是将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。2)空闲盘区链这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。32第八章磁盘存储器的管理8.2.2位示图法1.位示图位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。33第八章磁盘存储器的管理图8-10位示图34第八章磁盘存储器的管理2.盘块的分配根据位示图进行盘块分配时，可分三步进行：(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：b = n(i - 1) + j式中，n代表每行的位数。(3)修改位示图，令map[i,j] = 1。35第八章磁盘存储器的管理3.盘块的回收盘块的回收分两步：(1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i = (b - 1)DIV n + 1j = (b - 1)MOD n + 1(2)修改位示图。令map[i,j]= 0。36第八章磁盘存储器的管理8.2.3成组链接法1.空闲盘块的组织(1)空闲盘块号栈，用来存放当前可用的一组空闲盘块的盘块号(最多含100个号)，以及栈中尚有的空闲盘块(号)数N。顺便指出，N还兼作栈顶指针用。37第八章磁盘存储器的管理图8-11空闲盘块的成组链接法38第八章磁盘存储器的管理(2)文件区中的所有空闲盘块被分成若干个组，比如，将每100个盘块作为一组。假定盘上共有10000个盘块，每块大小为1KB，其中第201～7999号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为7901～7999；次末组为7801～7900，…，倒数第二组的盘块号为301～400；第一组为201～300，如图8-11所示。(3)将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)～S.free(99)中。这样，由各组的第一个盘块可链成一条链。39第八章磁盘存储器的管理(4)将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。(5)最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)～S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为99，不应是100，因为这是指可供使用的空闲盘块。其编号应为(1～99)，0号中放空闲盘块链的结尾标志。)40第八章磁盘存储器的管理2.空闲盘块的分配与回收当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。41第八章磁盘存储器的管理8.3提高磁盘I/O速度的途径(1)改进文件的目录结构以及检索目录的方法来减少对目录的查找时间；(2)选取好的文件存储结构，以提高对文件的访问速度；(3)提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反。其中的第1和第2点已在上一章或本章作了较详细的阐述，本节主要对如何提高磁盘的I/O速度作一简单介绍。42第八章磁盘存储器的管理8.3.1磁盘高速缓存(DiskCache)在设计磁盘高速缓存时需要考虑的问题有：(1)如何将磁盘高速缓存中的数据传送给请求进程；(2)采用什么样的置换策略；(3)已修改的盘块数据在何时被写回磁盘。43第八章磁盘存储器的管理1.数据交付(DataDelivery)方式如果I/O请求所需要的数据能从磁盘高速缓存中获取，此时就