第8章 磁盘存储器的管理

第六章文件管理第八章磁盘存储器的管理8.1外存的组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制第六章文件管理•文件的物理结构直接与外存的组织方式有关。–(1)连续组织方式–(2)链接组织方式–(3)索引组织方式8.1外存的组织方式第六章文件管理1.连续组织方式：为每一个文件分配一组相邻接的盘块，通常位于一条磁道上，读/写时不必移动磁头。8.1.1连续组织（分配）方式顺序文件第六章文件管理图8-1磁盘空间的连续分配第六章文件管理2.连续分配的主要优缺点主要优点：(1)简单,顺序访问容易，且支持顺序存取和随机存取(2)顺序存取速度快，所需的磁盘寻道次数和寻道时间最少。主要缺点：（1）要求有连续的存储空间。磁盘被无数次的划分后易形成外存的碎片，同样可用“紧凑”的方法解决。但花费大量机器时间。（2）必须事先知道文件的长度。（3）不能灵活地删除和插入记录。（4）对于那些动态增长的文件，很难知道文件的最终大小，很难为其分配空间；即使能知道最终大小，预分配会造成大量空间的长期闲置。第六章文件管理•概念:一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。分类：隐式链接、显示链接。8.1.2链接组织（分配）方式1.隐式链接采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。第六章文件管理图8-2磁盘空间的链接式分配25123056749101181314151217181916212223202526272429303128filestartendjeep925目录101-116文件第六章文件管理•缺点：–只适合顺序访问–随机访问效率极低，比如要访问文件的第100个盘块，则需要启动磁盘100次，每次需要几十ms。•解决方法：以簇为单位，假设一个簇包含4个块，这样访问文件的第100个盘块，则需启动25次磁盘，查找时间成倍减少；但增加了内部碎片。第六章文件管理2.显式链接图8-3显式链接结构012345物理块号2FCBFAT0451（文件分配表）文件分配表FAT——该表在整个磁盘仅设一张。把用于链接文件各物理块的指针显式地存放在内存的FAT表中。第六章文件管理MS-DOS的文件物理结构6EOF11105EOF0123456789FATFCBA4FCBB91011第六章文件管理•优点:（1）采取离散分配方式，消除了外部碎片问题，提高了磁盘空间利用率；（2）有利于文件动态增长，无须事先知道文件的大小。对文件的插入和删除也十分方便;•缺点：（1）存取速度慢，不适于随机存取（直接存取）;（2）可靠性问题，如指针出错;（3）更多的寻道次数和寻道时间;（4）链接指针占用一定的空间（隐式链接）;（5）FAT需占用较大的内存空间（显式链接）；3.链接组织方式优缺点第六章文件管理8.1.3FAT技术微软公司早、中期的操作系统采用FAT技术，主要有12位的FAT、16位的FAT、32位的FAT。引入“卷”的概念，一个卷即一个分区，最多可以有四个卷，每卷划出单独区域存放自己的目录、FAT表、逻辑驱动器字母。现代操作系统中，一个物理磁盘可以有多个卷，一个卷也可以由多个物理磁盘组成。第六章文件管理1. FAT121)早期的FAT12文件系统FAT12是以盘块为基本分配单位的。由于FAT是文件系统中最重要的数据结构，为了安全起见，在每个分区中都配有两张相同的文件分配表FAT1和FAT2。在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。第六章文件管理图8-4MS-DOS的文件物理结构第六章文件管理2)以簇为单位的FAT12文件系统如果把每个盘块(扇区)的容量增大n倍，则磁盘的最大容量便可增加n倍。但要增加盘块的容量是不方便和不灵活的。为此，引入了簇(cluster)的概念。优点：能适应磁盘容量不断增大的情况，还可以减少FAT表中的项数，减少FAT所占的内存空间。缺点：增加了簇内的碎片第六章文件管理2. FAT16FAT12表中的表项最多只允许4096个。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。3. FAT32由于FAT16表的长度只有65535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零头，也就应当增加FAT表的长度，这样也就由FAT16演变为FAT32。第六章文件管理第六章文件管理8.1.4NTFS的文件组织方式1.NTFS新特征NTFS(NewTechnologyFileSystem)是一个专门为WindowsNT开发的、全新的文件系统，并适用于Windows2000/XP及后续的WindowsOS。（1）使用了64位磁盘地址；（2）支持长文件名（单个文件255，绝对路径名32767）；（3）具有系统容错功能；（4）保证系统中数据的一致性。第六章文件管理2.磁盘组织NTFS是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，一个簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，即：使NTFS具有了与磁盘物理块大小无关的独立性。第六章文件管理3.文件的组织在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(MasterFileTable)中，该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。第六章文件管理8.1.5索引分配问题的引入：链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即：(1)不能支持高效的直接（随机）存取。(2)FAT需占用较大的内存空间。解决方法：在打开某个文件时，只需把该文件占用的盘块号调入内存即可，没必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。——索引分配方法。第六章文件管理1.单级索引组织方式一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在该索引表中。第六章文件管理索引结构优缺点：•优点：支持随机存取，满足了文件动态增长、插入删除的要求，不会产生外部碎片。•缺点：索引表本身带来了系统开销且索引块空间利用率低，不适合于小文件。第六章文件管理多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中。如：盘块大小1KB，每个盘块号占4B，单级索引允许的最大文件长度为：256*1KB=256KB二级索引允许的最大文件长度为：256*256KB=64MB2.多级索引组织方式第六章文件管理modeowners(2)timestamps(3)sizeblockcounti.addr(0)i.addr(1)directblockssingleindirectdoubleindirecttripleindirectdatadatadatadata¡¡datadata¡¡¡datadatadatadatai.addr(9)…图8-8UNIXSystemV混合索引方式3.增量式索引组织方式（P258）目的：照顾小、中、大、特大型作业第六章文件管理（1）直接地址。用i.addr(0)~i.addr(9)来存放直接地址。假如每个盘块的大小为4KB，支持的文件最大为40KB。（2）一次间接地址。当文件长度大于40KB时，要利用索引结点中的地址项i.addr(10)来提供一次间接地址。假如在一次间址块中可存放1K个盘块号，因而允许文件长达4MB+40KB。（3）多次间接地址。当文件长度更大时，需采用二次间址分配方式。用地址项i.addr(11)提供二次间接地址。文件最大长度可达4GB+4MB+40KB。同理，采用地址项i.addr(12)作为三次间接地址，其所允许的文件最大长度可达4TB+4GB+4MB+40KB。第六章文件管理8.2文件存储空间的管理1.空闲表法（空白文件目录）——连续分配方式将所有空闲块记录在一个表中，即空闲块表。2.空闲链表法把所有空闲块链成一个链。3.位示图法用一串二进制位反映磁盘空间中分配使用情况,每个物理块对应一位,分配物理块为1，否则为0。4.成组链接法空闲盘块分成若干组，然后将其链成一个链，利用空闲盘块号栈实现分配和回收。第六章文件管理1.空闲表法概念：属于连续分配方式。一个连续的未分配区域称为空闲区，将系统中所有空闲区的情况用一个表格记录。如：8.2.1空闲表法和空闲链表法序号第一空白块号空白块个数物理块号124（2，3，4，5）293（9，10，11）3155（15，16，17，18，19）4———第六章文件管理存储空间的分配：空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。存储空间的回收：当用户撤消一个文件时，系统回收该文件所占用的空间。类似于内存回收的方法。优点：分配速度高、可减少访问磁盘的I/O频率。应用：对换空间、文件较小时、多媒体文件。第六章文件管理2.空闲链表法（1）空闲盘块链：把其中所有的“空闲盘块”链在一起。优点：分配/回收一个盘块时简单。缺点：为一个文件分配盘块时，可能要重复操作多次。（2）空闲盘区链：把所有的“空闲区”（每个空闲区包含多个空闲块）拉成一条链。盘区分配/回收方法与内存的动态分区分配类似。常采用首次适应算法，为提高检索速度，可用显示链接方法，即在内存中建一张链接表。回收时相邻的合并。第六章文件管理8.2.2位示图法1.位示图(P261)图8-10位示图位示图，通常可用m*n个位数构成，并使m*n等于磁盘的总块数。用一串二进制位反映磁盘空间的分配使用情况,每个物理块对应一位,“1”表示对应的物理块已分配，“0”表示其对应的块未分配。第六章文件管理2.盘块的分配(P261)(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲块)。(2)将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j式中，n代表每行的位数。(3)修改位示图，令map［i,j］=1。第六章文件管理3.盘块的回收(P261)步骤：(1)将回收盘块的盘块号转换成位示图中的行号和列号。i=(b-1)DIVn+1商数加1j=(b-1)MODn+1余数加1(2)修改位示图。令map［i,j］=0。优点：(1)易找到一个或一组相邻接的空闲盘块（只需在位示图中找出几个连续为0的位即可）。(2)位示图小、占用空间少，因而可保存在内存中。节省了许多磁盘启动操作。此法常用于微型机和小型机中。第六章文件管理8.2.3成组链接法（自看）1.空闲盘块的组织图8-11空闲盘块的成组链接法100400399301300100300299…202201299…100400399…201301………9907999790179007899…78017999…7901空闲盘块号栈S.free019899第六章文件管理2.空闲盘块的分配与回收当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。第