第八章 磁盘存储器的管理

1、第八章第八章 磁盘存储器的管理磁盘存储器的管理8.1 外存组织方式外存组织方式8.2 文件存储空间的管理文件存储空间的管理8.3 提高磁盘提高磁盘I/O速度的途径速度的途径8.4 提高磁盘可靠性的技术提高磁盘可靠性的技术8.5 数据一致性控制数据一致性控制8.1 外存的组织方式外存的组织方式8.1.18.1.1连续组织方式连续组织方式1 1连续分配方式连续分配方式顺序式文件顺序式文件要求为要求为每一个文件分配一组相邻接的盘块每一个文件分配一组相邻接的盘块。 通常都通常都位于一条磁道上位于一条磁道上，进行读，进行读/ /写时不必移动磁头。写时不必移动磁头。 顺序文件：把逻辑文件中的记录顺序地存储

2、到邻接的各顺序文件：把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，所形成的文件结构。物理盘块中，所形成的文件结构。 连续分配保证了逻辑文件中的记录顺序与存储器中文件连续分配保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。占用盘块的顺序的一致性。 物理地址查询：目录项的物理地址查询：目录项的“文件物理地址文件物理地址”字段中，记字段中，记录该文件第一个记录所在的盘块号录该文件第一个记录所在的盘块号和文件长度和文件长度( (盘块数盘块数) )。磁盘空间的连续分配 1230567491011813141512171819162122232025262724list29303128

3、mailcountfilestart lengthcount 02tr153mail216list293f72目录trf外存碎片外存碎片：随着空间的分配和空间的回收，将使磁：随着空间的分配和空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件。来存储文件。 紧凑紧凑：将盘上所有的文件紧靠在一起，把所有的碎片：将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。拼接成一大片连续的存储空间。 将外存上的空闲空间进行一次紧凑，所花费的时间远将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间

4、多得多。比将内存紧凑一次所花费的时间多得多。 2 2连续分配的主要优缺点连续分配的主要优缺点(1) (1) 顺序访问容易。顺序访问容易。 从目录中找到该顺序文件所在的第一个盘块号，从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读从此开始顺序地、逐个盘块地往下读/ /写。写。(2) (2) 顺序访问速度快。顺序访问速度快。 文件所占用的盘块可能是位于一条或几条相邻的文件所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少。磁道上，这时，磁头的移动距离最少。 连续分配对文件访问的速度是几种存储空间分配连续分配对文件访问的速度是几种存储空间分配方式中方式中

5、最高最高的一种。的一种。 缺点：缺点：(1) (1) 要求有连续的存储空间。要求有连续的存储空间。 会产生出许多会产生出许多外部碎片外部碎片，降低外存空间的利用率。，降低外存空间的利用率。 定期利用紧凑方法消除碎片，需花费大量的时间。定期利用紧凑方法消除碎片，需花费大量的时间。 (2) (2) 必须事先知道文件的长度。必须事先知道文件的长度。 在有些情况下，文件的大小只能靠估算。在有些情况下，文件的大小只能靠估算。 估计过小，就可能因存储空间不足不能存放。估计过小，就可能因存储空间不足不能存放。 用户往往将文件长度估得比实际的大，严重地浪用户往往将文件长度估得比实际的大，严重地浪费外存空间。费

6、外存空间。 （3 3）对于）对于动态增长动态增长的文件，采用预分配存储空间的文件，采用预分配存储空间的方法，显然很低效。的方法，显然很低效。 8.1.28.1.2链接组织方式链接组织方式链接式文件链接式文件 1 1隐式链接隐式链接文件目录的每个目录项中，含有指向链接文件第一文件目录的每个目录项中，含有指向链接文件第一个盘块和最后一个盘块的指针。个盘块和最后一个盘块的指针。 在每个盘块中都含有一个指向下一个盘块的指针。在每个盘块中都含有一个指向下一个盘块的指针。 如果指针占用如果指针占用4 4个字节，对于盘块大小为个字节，对于盘块大小为512512字节的字节的磁盘，则每个盘块中只有磁盘，则每个盘

7、块中只有508508个字节可供用户使用。个字节可供用户使用。 磁盘空间的链接式分配 25123056749101181314151217181916212223202526272429303128filestartendjeep925目录101-116缺点：缺点： 1) 1)只适合顺序访问，对随机访问极其低效。只适合顺序访问，对随机访问极其低效。 必须从文件的第一个盘块读起，顺序查找至第必须从文件的第一个盘块读起，顺序查找至第i i块。块。 当当i=100i=100时，须启动时，须启动100100次磁盘，速度相当低。次磁盘，速度相当低。 2 2) )只通过链接指针将一大批离散的盘块链接起来，只

8、通过链接指针将一大批离散的盘块链接起来，其可靠性较差，只要其中的任何一个指针出现问题，其可靠性较差，只要其中的任何一个指针出现问题，都会导致整个链的断开。都会导致整个链的断开。 2 2显式链接显式链接 显式链接显式链接：把用于链接文件各物理块的指针，显式：把用于链接文件各物理块的指针，显式地存放在地存放在内存内存的一张链接表中。称为的一张链接表中。称为文件分配表文件分配表FATFAT。 整个磁盘仅设置一张整个磁盘仅设置一张。 表的序号即物理盘块号，从表的序号即物理盘块号，从0 0到到N N。 每个表项中存放指向下一个盘块号的链接指针。每个表项中存放指向下一个盘块号的链接指针。 每个链首指针所对

9、应的盘块号，填入相应文件的每个链首指针所对应的盘块号，填入相应文件的FCBFCB的的“物理地址物理地址”字段中。字段中。 通过通过FATFAT表，将一个文件的所有的盘块链接起来，表，将一个文件的所有的盘块链接起来，将文件的第一个盘块号放在各自的将文件的第一个盘块号放在各自的FCBFCB中。中。显式链接结构 012345物理块号2FCBFAT04518.1.3 FAT8.1.3 FAT和和NTFSNTFS技术技术1 1FAT12FAT121) 1) 以盘块为基本分配单位以盘块为基本分配单位 早期早期MS-DOSMS-DOS操作系统所使用的是操作系统所使用的是FAT12FAT12文件系统。文件系统

10、。 每个表项中存放下一个盘块号。每个表项中存放下一个盘块号。 若有若有1.2 MB1.2 MB的软盘，每个盘块的大小为的软盘，每个盘块的大小为512 B512 B，在每，在每个个FATFAT中共含有中共含有2.4 K2.4 K个表项，由于每个个表项，由于每个FATFAT表项占表项占1212位，位，故故FATFAT表占用表占用3.6 KB3.6 KB的存储空间。的存储空间。MS-DOS的文件物理结构 6EOF11105EOF0123456789FATFCB A4FCB B9 以盘块为分配单位时，所允许的最大磁盘容量。以盘块为分配单位时，所允许的最大磁盘容量。 FAT-12 FAT-12系统：系统

11、： 在在FATFAT表中最多允许有表中最多允许有40964096个表项，个表项， 以盘块以盘块( (512512字节字节) )为分配单位；为分配单位； 每个磁盘分区的容量为每个磁盘分区的容量为2MB2MB。 一个物理磁盘支持一个物理磁盘支持4 4个逻辑磁盘分区个逻辑磁盘分区，所以相应的，所以相应的磁盘最大容量仅为磁盘最大容量仅为8MB8MB。2) 2) 簇的基本概念簇的基本概念磁盘容量不断增大，在进行盘块分配时不再以盘块而磁盘容量不断增大，在进行盘块分配时不再以盘块而是以簇是以簇(cluster)(cluster)为基本单位。为基本单位。 簇：簇：一组连续的扇区，大小一般是一组连续的扇区，大小

12、一般是2 2n n个盘块个盘块，4 4扇区、扇区、8 8扇区等。扇区等。 簇包含扇区的数量与磁盘容量的大小直接有关。簇包含扇区的数量与磁盘容量的大小直接有关。 一个簇有一个扇区：磁盘的最大容量为一个簇有一个扇区：磁盘的最大容量为8MB8MB； 一个簇有两个扇区：磁盘的最大容量为一个簇有两个扇区：磁盘的最大容量为16MB16MB； 一个簇有八个扇区：磁盘的最大容量为一个簇有八个扇区：磁盘的最大容量为64MB64MB。 在相同磁盘容量下，在相同磁盘容量下，FATFAT表的项数与簇的大小成反比表的项数与簇的大小成反比。以簇作为基本的分配单位的优点：以簇作为基本的分配单位的优点：(1)(1)能适应磁盘

13、容量不断增大的情况。能适应磁盘容量不断增大的情况。(2)(2)使使FATFAT表占用更少的存储空间，并减少访问表占用更少的存储空间，并减少访问FATFAT表的表的存取开销，提高文件系统的效率；存取开销，提高文件系统的效率； 缺点：会造成更大的簇内零头。缺点：会造成更大的簇内零头。 3)FAT123)FAT12存在的问题存在的问题(1)(1)对所允许的磁盘容量存在着严重的限制对所允许的磁盘容量存在着严重的限制，通常，通常只能是数十兆字节，虽然可以用只能是数十兆字节，虽然可以用继续增加簇继续增加簇的大小来提的大小来提高所允许的最大磁盘容量，但相应的高所允许的最大磁盘容量，但相应的簇内碎片簇内碎片也

14、将随之也将随之成倍地增加。成倍地增加。 (2) (2)只能支持只能支持8+38+3格式的文件名。格式的文件名。 2 2FAT16FAT16将将FATFAT表的宽度增至表的宽度增至1616位，最大表项数将增至位，最大表项数将增至6553665536个，此时便能将一个磁盘分区分为个，此时便能将一个磁盘分区分为65536(65536(2 21616) )个簇。个簇。 FAT16: FAT16:具有具有1616位表宽的位表宽的FATFAT表。表。 FAT16 FAT16的每个簇的盘块数的每个簇的盘块数:4:4、8 8、1616、3232、6464。 FAT16FAT16可以管理的最大分区空间：可以管理

15、的最大分区空间：2 216166464512 = 512 = 2048MB=2G2048MB=2G。 FAT16FAT16对对FAT12FAT12的局限性有所改善，但改善很有限。的局限性有所改善，但改善很有限。 当磁盘容量迅速增加时，形成的簇内碎片所造成的当磁盘容量迅速增加时，形成的簇内碎片所造成的浪费也越大。浪费也越大。例如，当要求磁盘分区的大小为例如，当要求磁盘分区的大小为8GB8GB时，则每个簇的大时，则每个簇的大小达到小达到128KB128KB，内部零头，内部零头最大可达到最大可达到128 KB128 KB。 为了解决这一问题，微软推出了为了解决这一问题，微软推出了FAT32FAT32

16、。3 3FAT32FAT32FAT16FAT16表的长度只有表的长度只有65 53565 535项，随着磁盘容量的增项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内零头，加，簇的大小也必然会随之增加，为了减少簇内零头，也就应当增加也就应当增加FATFAT表的长度。表的长度。 也就由也就由FAT16FAT16演变为演变为FAT32FAT32。FAT32FAT32是是FATFAT系列文件系统的最后一个产品。系列文件系统的最后一个产品。 每一簇在每一簇在FATFAT表中的表项占据表中的表项占据4 4字节，字节，FATFAT表可以表示表可以表示42949672964294967296项项

17、(2(23232) )。 允许在允许在FAT32FAT32中采用较小的簇中采用较小的簇。 FAT32 FAT32的的每个簇都固定为每个簇都固定为4KB4KB( (每簇用每簇用8 8个盘块个盘块代替代替FAT16FAT16的的6464个盘块个盘块),),每个盘块仍为每个盘块仍为512512字节。字节。FAT32FAT32分区格式可以管理的单个最大磁盘空间大到分区格式可以管理的单个最大磁盘空间大到2TB2TB FATFAT中簇的大小与最大分区的对应关系中簇的大小与最大分区的对应关系 三种三种FATFAT类型的最大分区以及所对应的块的大小类型的最大分区以及所对应的块的大小如下图所示。如下图所示。 8

18、.1.8.1.4 4NTFSNTFS1)NTFS1)NTFS新特征新特征NTFSNTFS：专门为：专门为Windows NTWindows NT开发的、全新的文件系统，开发的、全新的文件系统，并适用于并适用于Windows 2000/XP/2003Windows 2000/XP/2003。 NTFS NTFS特征：特征： 1 1）使用了）使用了6464位位磁盘地址，理论上可以支持磁盘地址，理论上可以支持2 26464次方次方字节的磁盘分区；字节的磁盘分区； 2 2）在）在NTFSNTFS中可以很好地支持长文件名，单个文件中可以很好地支持长文件名，单个文件名限制在名限制在255255个字符以内，

19、全路径名为个字符以内，全路径名为3276732767个字符；个字符； 3 3）具有系统容错功能；）具有系统容错功能； 4 4）提供了数据的一致性；此外，）提供了数据的一致性；此外，NTFSNTFS还提供了还提供了文文件加密件加密、文件压缩文件压缩等功能。等功能。 2) 2) 磁盘组织磁盘组织以簇作为磁盘空间分配和回收的基本单位。以簇作为磁盘空间分配和回收的基本单位。 一个文件占用若干个簇，一个簇只属于一个文件。一个文件占用若干个簇，一个簇只属于一个文件。 通过簇来间接管理磁盘，可以不需要知道盘块通过簇来间接管理磁盘，可以不需要知道盘块( (扇扇区区) )的大小，使的大小，使NTFSNTFS具有

20、了与磁盘物理扇区大小无关的具有了与磁盘物理扇区大小无关的独立性。独立性。 在在NTFSNTFS文件系统中，文件系统中，簇的大小使用簇的大小使用4 KB4 KB。 8.1.58.1.5索引组织方式索引组织方式索引式文件索引式文件 1 1单级索引分配单级索引分配链接分配方式存在两个问题：链接分配方式存在两个问题：(1)(1)不能支持高效的直接存取。不能支持高效的直接存取。 要在要在FATFAT中顺序地查找许多盘块号。中顺序地查找许多盘块号。 (2)FAT (2)FAT需占用较大的内存空间。需占用较大的内存空间。 需要整个需要整个FATFAT表进内存。表进内存。 事实上，在打开某个文件时，只需把事实

21、上，在打开某个文件时，只需把该文件占用的盘该文件占用的盘块的编号块的编号调入内存即可，完全没有必要将整个调入内存即可，完全没有必要将整个FATFAT调入内调入内存。存。将每个文件所对应的盘块号集中地放在一起将每个文件所对应的盘块号集中地放在一起。 索引分配原理：为每个文件分配一个索引块索引分配原理：为每个文件分配一个索引块( (表表) )，再，再把分配给该文件的所有盘块号都记录在该索引块中。把分配给该文件的所有盘块号都记录在该索引块中。 目录表对应目录项中填上指向该索引块的指针。目录表对应目录项中填上指向该索引块的指针。索引分配方式 123056749101181314151217181916

22、212223202526272429303128countfile块序号jeep19目录91611025111192 2多级索引分配多级索引分配 当文件很大，索引块太多时，要为索引块再建立索当文件很大，索引块太多时，要为索引块再建立索引，便形成了两级索引分配方式。引，便形成了两级索引分配方式。 文件非常大时，还可用三级、四级索引分配方式。文件非常大时，还可用三级、四级索引分配方式。 两级索引分配 01210510625435635798510510625474035635711259853607401125主索引360第二级索引磁盘空间两级索引两级索引分配方式下各分配方式下各索引块之间的索引块

23、之间的链接情况。链接情况。 如果盘块的大小为如果盘块的大小为1KB1KB，每个盘块号占，每个盘块号占4 4个字节，个字节，则在一个索引块中可存放则在一个索引块中可存放256256个盘块号。这样，在两级个盘块号。这样，在两级索引时，索引时， 最多可包含的存放文件的盘块的盘块号总数最多可包含的存放文件的盘块的盘块号总数N =256N =256256=64K256=64K个盘块号。个盘块号。 则采用两级索引时，所允许的文件最大长度为则采用两级索引时，所允许的文件最大长度为64MB64MB。 若盘块的大小为若盘块的大小为4KB4KB，在采用单级索引时所允许，在采用单级索引时所允许的最大文件长度为的最大

24、文件长度为4MB4MB；而在采用两级索引时所允许的；而在采用两级索引时所允许的最大文件长度可达最大文件长度可达4GB4GB。 3 3混合索引分配方式混合索引分配方式/ /增量式索引组织方式增量式索引组织方式混合索引分配方式：将多种索引分配方式相结合而混合索引分配方式：将多种索引分配方式相结合而形成的一种分配方式。形成的一种分配方式。 例如，系统既采用了例如，系统既采用了直接地址直接地址，又采用了，又采用了一级索引一级索引分配方式、两级索引分配方式、三级索引分配方式分配方式、两级索引分配方式、三级索引分配方式。 混合索引分配方式已在混合索引分配方式已在UNIXUNIX系统中采用。系统中采用。 在

25、在UNIX System UNIX System 的索引结点中，共设置了的索引结点中，共设置了1313个地个地址项，即址项，即iaddr(0)iaddr(0)iaddr(12)iaddr(12)。 都把所有的地址项分成两类：直接地址和间接地址。都把所有的地址项分成两类：直接地址和间接地址。 假如每个盘块的大小为假如每个盘块的大小为 4 KB4 KB，索引块中每个索引，索引块中每个索引项占项占4B4B。1) 1) 直接地址（文件在直接地址（文件在040KB040KB之间）之间）1010个直接地址项：个直接地址项：iaddr(0)iaddr(0)iaddr(9)iaddr(9)，来存放直，来存放直

26、接地址。即每项中存放的是该文件的盘块号。接地址。即每项中存放的是该文件的盘块号。 2) 2) 一次间接地址一次间接地址( (文件介于文件介于40K40K和和4M4M之间）之间）一个一级索引分配：地址项一个一级索引分配：地址项iaddr(10)iaddr(10)提供一次间提供一次间接地址。一次间址块中可存放接地址。一次间址块中可存放1K1K个盘块号，因而允许文个盘块号，因而允许文件长达件长达4MB4MB。 3)3)多次间接地址多次间接地址文件长度介于文件长度介于4MB+40KB4MB+40KB和和4G4G 地址项地址项iaddr(11)iaddr(11)提供二次间接地址。提供二次间接地址。 采用

27、二次间址方式时，文件最大长度可达采用二次间址方式时，文件最大长度可达4GB4GB。 地址项地址项iaddr(12)iaddr(12)作为三次间接地址，其所允许的文作为三次间接地址，其所允许的文件最大长度可达件最大长度可达4 TB4 TB。 混合索引方式混合索引方式 modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata8.2文件

28、存储空间的管理文件存储空间的管理 8.2.18.2.1空闲表法和空闲链表法空闲表法和空闲链表法1 1空闲表法空闲表法1) 1) 空闲表空闲表连续分配方式连续分配方式 系统为外存上的所有系统为外存上的所有空闲区空闲区建立一张空闲表；建立一张空闲表； 每个空闲区对应于一个空闲表项：包括表项序号、每个空闲区对应于一个空闲表项：包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。该空闲区的第一个盘块号、该区的空闲盘块数等信息。 所有空闲区按其所有空闲区按其起始盘块号起始盘块号递增的次序排列。递增的次序排列。 查表后为每个文件分配一块连续的存储空间。查表后为每个文件分配一块连续的存储空间。空闲

29、盘块表空闲盘块表 对于文件系统，当文件较小对于文件系统，当文件较小(1(14 4个盘块个盘块) )时，采用时，采用连续分配方式，为文件分配相邻接的几个盘块；当文件连续分配方式，为文件分配相邻接的几个盘块；当文件较大时，便采用离散分配方式。较大时，便采用离散分配方式。 2)2)存储空间的分配与回收存储空间的分配与回收 与内存的动态分配类似，同样是采用首次适应算法、与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。循环首次适应算法等。 分配：先顺序地检索空闲表的各表项，直至找到第分配：先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用一个其大小能

30、满足要求的空闲区，再将该盘区分配给用户户( (进程进程) )，同时，同时修改空闲表修改空闲表。 回收：也采取类似于内存回收的方法，即要考虑回回收：也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。邻接者应予以合并。 2 2空闲链表法空闲链表法 将所有空闲盘区拉成一条空闲链。将所有空闲盘区拉成一条空闲链。 链表分成两种形式：链表分成两种形式：空闲盘块链空闲盘块链和和空闲盘区链空闲盘区链。(1)(1)空闲盘块链。空闲盘块链。 分配时从分配时从链首链首开始，开始，依次依次摘下适当数目的空闲盘块分摘下

31、适当数目的空闲盘块分配给用户。配给用户。 将回收的盘块依次插入空闲盘块链的末尾。将回收的盘块依次插入空闲盘块链的末尾。 优点：分配和回收一个盘块的过程非常简单；优点：分配和回收一个盘块的过程非常简单； 缺点：为一个文件分配盘块时，可能要重复操作多次。缺点：为一个文件分配盘块时，可能要重复操作多次。 (2)(2)空闲盘区链。空闲盘区链。 将磁盘上的所有将磁盘上的所有空闲盘区空闲盘区拉成一条链。拉成一条链。 每个盘区上含有指向下一个空闲盘区的指针，以及每个盘区上含有指向下一个空闲盘区的指针，以及本盘区大小本盘区大小( (盘块数盘块数) )的信息。的信息。 分配：通常采用分配：通常采用首次适应首次适

32、应算法。算法。 回收：将回收区与相邻接的空闲盘区相合并。回收：将回收区与相邻接的空闲盘区相合并。8.2.28.2.2位示图法位示图法1 1位示图位示图 位示图：利用二进制的一位来表示磁盘中一个盘块位示图：利用二进制的一位来表示磁盘中一个盘块的使用情况。的使用情况。 值为值为“0”0”：表示对应的盘块空闲；：表示对应的盘块空闲； 值为值为“1”1”：表示已分配。：表示已分配。 通常用通常用m m n n个位数来构成位示图，并使个位数来构成位示图，并使m m n n等等于磁盘的总块数。于磁盘的总块数。位示图位示图 位示图也可描述为一个二维数组位示图也可描述为一个二维数组mapmap：Var map

33、: array of bitVar map: array of bit； 2盘块的分配盘块的分配(1)顺序扫描位示图，从中找出一个或一组其值为顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位的二进制位(“0”表示空闲时表示空闲时)。(2) 将所找到的一个或一组二进制位转换成与之相应的将所找到的一个或一组二进制位转换成与之相应的盘块号。盘块号。 假定找到的其值为假定找到的其值为“0”的二进制位位于位示图的第的二进制位位于位示图的第i行、第行、第j列，则其相应的盘块号应按下式计算：列，则其相应的盘块号应按下式计算： b = n(i - 1) + j 思考：盘块号从几开始思考：盘块号从几开始

34、？ n代表每行的位数代表每行的位数。 (3) 修改位示图，令修改位示图，令mapi,j=1。 3盘块的回收盘块的回收(1) 将回收盘块的盘块号转换成位示图中的行号和将回收盘块的盘块号转换成位示图中的行号和列号。转换公式：列号。转换公式： i= (b - 1)DIV n + 1 j = (b - 1)MOD n + 1 (2) 修改位示图。令修改位示图。令mapi,j =0。优点：优点： 1) 很容易找到一个或一组相邻接的空闲盘块。很容易找到一个或一组相邻接的空闲盘块。 2)位示图很小，占用空间少，可保存在内存中。位示图很小，占用空间少，可保存在内存中。 常用于微型机和小型机中常用于微型机和小型

35、机中。 8.2.38.2.3成组链接法成组链接法1空闲盘块的组织空闲盘块的组织 (1)空闲盘块被分成若干组，如每空闲盘块被分成若干组，如每100盘块为一组。盘块为一组。 (2)第一组空闲盘块为当前可用的，用第一组空闲盘块为当前可用的，用空闲盘块号栈空闲盘块号栈来来存放其盘块号。存放其盘块号。S.free(0)是栈底，栈顶为是栈底，栈顶为S.free(99) 。 (3)将每一组含有的将每一组含有的盘块总数盘块总数N和该组所有的盘块号记和该组所有的盘块号记入其前一组的第一个盘块的入其前一组的第一个盘块的S.free(0)S.free(99)中。中。 由各组的第一个盘块可链成一条链由各组的第一个盘块

36、可链成一条链。 (4)最末一组只有最末一组只有99个盘块，记入其前一组的个盘块，记入其前一组的S.free(1) S.free(99)中，中，S.free(0)中存放中存放“0”，作为空，作为空闲盘块链的结束标志。闲盘块链的结束标志。 空闲盘块的成组链接法空闲盘块的成组链接法 1004003993013001003002992022012991004003992013019907999790179007899780179997901空闲盘块号栈S.free019899S.free(0)为栈底为栈底S.free(99)为栈顶为栈顶2.空闲盘块的分配与回收空闲盘块的分配与回收分配盘块：调用分配盘块

37、：调用盘块分配过程盘块分配过程来完成。来完成。 1)首先检查空闲盘块号栈首先检查空闲盘块号栈是否上锁是否上锁，如未上锁，便从，如未上锁，便从栈顶栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。然后将栈顶指针下移一格。 2)若该盘块号已是栈底，即若该盘块号已是栈底，即S.free(0)，调用，调用磁盘读过程磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，并把原栈底将栈底盘块号所对应盘块的内容读入栈中，并把原栈底对应的盘块分配出去。对应的盘块分配出去。 3)空闲盘块数减空闲盘块数减1。 系统回收系统回收:调用调用盘块回收过程

38、盘块回收过程。 1)将回收的盘块号记入空闲盘块号栈的顶部，并执行将回收的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加空闲盘块数加1操作。操作。 2)当栈中空闲盘块号数目已达当栈中空闲盘块号数目已达100时，将现有栈中的时，将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。新栈底。 8.3 提高磁盘提高磁盘I/O速度的途径速度的途径 8.3.1 磁盘高速缓存磁盘高速缓存设计磁盘高速缓存是要考虑的问题及解决办法：设计磁盘高速缓存是要考虑的问题及解决办法：1.如何将磁盘高速缓存中的数据传送给请求进程如何将磁盘高速缓存中的数据传送给请

39、求进程 1）数据交付）数据交付 2）指针交付）指针交付2.磁盘高速缓存满时如何置换磁盘高速缓存满时如何置换 LRU、LFU等算法等算法3.被修改的盘块数据何时写回磁盘被修改的盘块数据何时写回磁盘 如如UNIX系统中设置修改（系统中设置修改（update）程序，每）程序，每30s调用系统调用调用系统调用SYNC，强制性将所有磁盘高速缓，强制性将所有磁盘高速缓存中被修改过的盘块数据写回磁盘。存中被修改过的盘块数据写回磁盘。8.3.2 提高磁盘提高磁盘I/O速度的其他办法速度的其他办法 1.提前读提前读 2.延迟写延迟写 3.优化物理块的分布优化物理块的分布 根据根据位示图位示图进行文件盘块的分配，

40、尽量将属于同一个进行文件盘块的分配，尽量将属于同一个文件的盘块安排在一条磁道上或相邻磁道上。文件的盘块安排在一条磁道上或相邻磁道上。 4.虚拟盘虚拟盘 利用内存仿真磁盘，称为利用内存仿真磁盘，称为虚拟盘，虚拟盘，RAM盘盘，由于内存，由于内存是不稳定存储设备，因此是不稳定存储设备，因此只能存放临时文件只能存放临时文件。8.3.3 廉价磁盘冗余阵列（廉价磁盘冗余阵列（RAID） 原理：利用一台原理：利用一台磁盘阵列控制器磁盘阵列控制器来统一管理和控制一来统一管理和控制一组（几台到几十台）磁盘驱动器组成一个大型磁盘系统。组（几台到几十台）磁盘驱动器组成一个大型磁盘系统。 1.并行交叉存取并行交叉存

41、取 2.RAID分级：分级：07级级 1）0级：仅提供并行交叉存取级：仅提供并行交叉存取 2）1级：具有镜像功能。级：具有镜像功能。 3）3级：具有并行传输功能，只利用一台奇偶校验盘来级：具有并行传输功能，只利用一台奇偶校验盘来完成数据校验功能。完成数据校验功能。 4） 5级：每个磁盘能独立进行读写操作。级：每个磁盘能独立进行读写操作。 5）6级：设置一个专用的可快速访问的异步校验盘。级：设置一个专用的可快速访问的异步校验盘。 7级：阵列中所有磁盘都具有较高传输速率和优异性级：阵列中所有磁盘都具有较高传输速率和优异性能，价格较高。能，价格较高。3.RAID优点优点 1）可靠性高）可靠性高 2）

42、磁盘）磁盘I/O速度高速度高 3）性价比高）性价比高8.4.1 第一级容错技术第一级容错技术SFT-1双份双份目录和双份文件分配表目录和双份文件分配表在不同的磁盘上或在磁盘的不同区域中，建立在不同的磁盘上或在磁盘的不同区域中，建立(双份双份)目录表和目录表和FAT。 一旦由于磁盘表面缺陷而造成主文件目录或主一旦由于磁盘表面缺陷而造成主文件目录或主FAT的损坏时，系统便自动启用备份文件目录及备份的损坏时，系统便自动启用备份文件目录及备份FAT。 8.4 提高磁盘可靠性的技术提高磁盘可靠性的技术 2) 热修复重定向和写后读校验热修复重定向和写后读校验磁盘表面有少量缺陷时，可采取以下两个补救措施：磁

43、盘表面有少量缺陷时，可采取以下两个补救措施： (1) 热修复重定向热修复重定向：磁盘开辟一块区域，用于存放当：磁盘开辟一块区域，用于存放当发现磁盘有缺陷时的待写数据，并对写入该区的所有发现磁盘有缺陷时的待写数据，并对写入该区的所有数据进行登记，以便于以后对数据进行访问。数据进行登记，以便于以后对数据进行访问。 (2) 写后读校验方式：写后读校验方式：将写入磁盘的数据块送至另一将写入磁盘的数据块送至另一缓冲区中，比较缓冲区中，比较该缓冲区该缓冲区与与内存缓冲区中保留的数据内存缓冲区中保留的数据： 若两者一致，写入成功继续写下一个盘块；若两者一致，写入成功继续写下一个盘块； 否则，再重写。若重写后

44、两者仍不一致，则认为该否则，再重写。若重写后两者仍不一致，则认为该盘块有缺陷，将应写入该盘块的数据，写入到盘块有缺陷，将应写入该盘块的数据，写入到热修复热修复重定向区重定向区中。中。 8.4.2第二级容错技术第二级容错技术SFT-1.磁盘磁盘镜像镜像(Disk Mirroring) 在同一磁盘控制器下增设一个完全相同的磁盘驱动器。在同一磁盘控制器下增设一个完全相同的磁盘驱动器。 两个磁盘上两个磁盘上具有完全相同的位像图具有完全相同的位像图，把备份磁盘看作，把备份磁盘看作是主磁盘的一面镜子。是主磁盘的一面镜子。 每次向每次向主磁盘主磁盘写入数据时，都需要将数据再写到写入数据时，都需要将数据再写到

45、备份备份磁盘磁盘上。上。 当主磁盘驱动器发生故障时，切换备份磁盘使主机仍当主磁盘驱动器发生故障时，切换备份磁盘使主机仍能正常工作。能正常工作。 缺点：磁盘的利用率降至仅为缺点：磁盘的利用率降至仅为50%。磁盘镜像示意磁盘镜像示意 磁盘控制器主机通道磁盘驱动器2.磁盘磁盘双工双工(Disk Duplexing) 如果如果磁盘控制器或通道发生故障，便起不到数据保护磁盘控制器或通道发生故障，便起不到数据保护的作用。的作用。 磁盘磁盘双工：将两台磁盘驱动器分别接到两个磁盘控双工：将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘驱动器镜像成对。制器上，同样使这两台磁盘驱动器镜像成对。 同时同时

46、将数据写到两个处于不同控制器下的磁盘上，将数据写到两个处于不同控制器下的磁盘上，使两者有完全相同的位像图。使两者有完全相同的位像图。 某个某个通道或控制器发生故障，另一通道上的磁盘仍通道或控制器发生故障，另一通道上的磁盘仍能正常工作不会造成数据的丢失。能正常工作不会造成数据的丢失。 磁盘磁盘双工可并行地将数据写入磁盘，或读出数据。双工可并行地将数据写入磁盘，或读出数据。 磁盘磁盘双工示意双工示意主机磁盘控制器磁盘控制器通道通道磁盘驱动器3基于集群技术的容错功能基于集群技术的容错功能主要工作模式有三种主要工作模式有三种： 双机热双机热备份模式备份模式； 系统中有两台服务器，处理能力完全相同，一个

47、主服系统中有两台服务器，处理能力完全相同，一个主服务器平时正常工作，一台为备用服务器平时处于等待状务器平时正常工作，一台为备用服务器平时处于等待状态。态。 互为备份模式互为备份模式； 系统中有两台服务器，同时处于在线状态。系统中有两台服务器，同时处于在线状态。 公用磁盘模式。公用磁盘模式。8.4.4 后备系统后备系统 1.磁带机磁带机 2.硬盘硬盘 1）移动磁盘）移动磁盘 2）固定硬盘）固定硬盘 3.光盘驱动器光盘驱动器 1)只读光盘驱动器只读光盘驱动器 2)可读写光盘驱动器可读写光盘驱动器8.5数据一致性控制数据一致性控制 8.5.1事务事务 1事务的定义事务的定义事务事务:用于访问和修改各

48、种数据项的一个程序单位。用于访问和修改各种数据项的一个程序单位。 事务事务:可看作一系列相关读和写操作。可看作一系列相关读和写操作。 读和写操作全部完成时，以读和写操作全部完成时，以托付操作托付操作来终止事务。来终止事务。 只要有一个读只要有一个读,写或修改操作失败写或修改操作失败,便须执行便须执行夭折操作夭折操作。 读或写操作的失败可能是由于逻辑错误，也可能是系读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导致的。统故障所导致的。 一个夭折的事务，通常已执行了一些操作，为避免引一个夭折的事务，通常已执行了一些操作，为避免引起数据不一致性，须将刚被修改的数据项恢原。起数据不一致性，须将

49、刚被修改的数据项恢原。 此时，该事务此时，该事务“已被退回已被退回” 。 事务具有事务具有“原子性原子性”：在对一批数据执行修改操作时，：在对一批数据执行修改操作时，要么全部完成并用修改后的数据去代替原来的数据，要要么全部完成并用修改后的数据去代替原来的数据，要么一个也不修改么一个也不修改。事务的四个属性：事务的四个属性：A：原子性：原子性C：一致性：一致性I：隔离性：隔离性D：永久性：永久性2事务记录事务记录(Transaction Record)原子修改的实现：借助原子修改的实现：借助事务记录事务记录这种数据结构。这种数据结构。 事务记录事务记录：放在：放在稳定存储器稳定存储器中，用来记录

50、在事务运行中，用来记录在事务运行时数据项修改的全部信息，又称为时数据项修改的全部信息，又称为运行记录运行记录(Log)。 该记录中包括如下字段该记录中包括如下字段: 事务名事务名：用于标识该事务的惟一名字；：用于标识该事务的惟一名字； 数据项名数据项名：指被修改数据项的惟一名字；：指被修改数据项的惟一名字； 旧值旧值：修改前数据项的值；：修改前数据项的值； 新值新值：修改后数据项将具有的值。：修改后数据项将具有的值。 3恢复算法恢复算法利用两个过程利用两个过程:(1)undo。 把所有被事务把所有被事务Ti修改过的数据恢复为修改前的值。修改过的数据恢复为修改前的值。(2) redo。 把所有被

51、事务把所有被事务Ti修改过的数据设置为新值。修改过的数据设置为新值。 系统发生故障，对以前所发生的事务进行清理。系统发生故障，对以前所发生的事务进行清理。 把尚未清理的事务分成两类把尚未清理的事务分成两类: 1)各类操作都已完成的事务各类操作都已完成的事务:事务记录表中既包含了事务记录表中既包含了Ti开始开始记录，又包含了记录，又包含了Ti托付托付记录。记录。 则利用则利用redoTi过程，把被修改的数据设置成新值。过程，把被修改的数据设置成新值。 2)各个操作并未全部完成的事务各个操作并未全部完成的事务:在在Log表中表中只有只有Ti开始开始记录而记录而无无Ti托付托付记录。记录。 则用则用

52、undoTi过程，将被修改数据复原。过程，将被修改数据复原。 8.5.2检查点检查点1检查点检查点(Check Points)的作用的作用当系统发生故障时，必须去检查整个当系统发生故障时，必须去检查整个Log表，以确定表，以确定哪些事务需要设置新值，哪些事务需要复原。哪些事务需要设置新值，哪些事务需要复原。 随着时间的推移，随着时间的推移，LOG表中的事务记录过多，清理表中的事务记录过多，清理起来非常费时。起来非常费时。 设置设置检查点的目的：使事务记录的清理工作经常化。检查点的目的：使事务记录的清理工作经常化。 即每隔一定时间便做一次下述工作：即每隔一定时间便做一次下述工作： 1)将内存中将

53、内存中log表中的表中的所有记录所有记录输出到磁盘中；输出到磁盘中； 2)将内存的所有将内存的所有已修改数据已修改数据输出到磁盘中；输出到磁盘中； 3)将将log表中的表中的检查点检查点记录记录输出到磁盘中；输出到磁盘中； 4)每当出现一个每当出现一个检查点检查点记录时，系统便利用记录时，系统便利用redo和和undo过程实现恢复功能。过程实现恢复功能。 思考：思考：如果一个事务如果一个事务Ti在检查点前就做了托付，在在检查点前就做了托付，在系统出现故障时，还需再执行系统出现故障时，还需再执行redo操作吗？操作吗？ 2新的恢复算法新的恢复算法设置检查点的优点：设置检查点的优点： 出现故障时不

54、需要对出现故障时不需要对log表中的所有事务记录进行处理，表中的所有事务记录进行处理，只需对最后一个检查点之后的事务记录进行处理只需对最后一个检查点之后的事务记录进行处理,大大减少大大减少恢复处理的开销。恢复处理的开销。 新算法：把所有在事务新算法：把所有在事务Ti以后开始执行的事务表示为以后开始执行的事务表示为事事务集务集T: 对所有在对所有在T中的事务中的事务TK，如果在事务记录表中出现，如果在事务记录表中出现了了TK托付托付记录，则执行记录，则执行redoTK操作；反之，如果操作；反之，如果在事务记录表中并未出现在事务记录表中并未出现TK托付托付记录，则执行记录，则执行undoTK操作。

55、操作。 8.5.3(基于事务的基于事务的)并发控制并发控制1利用利用互斥锁互斥锁实现实现“顺序性顺序性” 为每一个共享对象设置一把互斥锁。为每一个共享对象设置一把互斥锁。 当事务当事务Ti访问某对象时，应先获得其互斥锁。访问某对象时，应先获得其互斥锁。 若成功，事务若成功，事务Ti便可对该对象执行读或写操作；而其便可对该对象执行读或写操作；而其它事务不能访问该对象。它事务不能访问该对象。 如果如果Ti需要对一批对象进行访问，则需要对一批对象进行访问，则Ti应先获得所有应先获得所有对象的互斥锁。对象的互斥锁。 如果成功，便可对这一批对象执行读或写操作；如如果成功，便可对这一批对象执行读或写操作；

56、如果其中某一个已被锁住，则果其中某一个已被锁住，则Ti应对此前已被应对此前已被Ti锁住的其锁住的其它对象进行开锁，宣布此次事务运行失败。它对象进行开锁，宣布此次事务运行失败。 2利用互斥锁和共享锁实现顺序性利用互斥锁和共享锁实现顺序性 互斥锁优点互斥锁优点:实现顺序性简单易行。实现顺序性简单易行。 互斥锁缺点：效率不高，不能实现多事务同时读。互斥锁缺点：效率不高，不能实现多事务同时读。 因而又引入共享锁因而又引入共享锁(Shared Lock)。 共享锁与互斥锁的区别共享锁与互斥锁的区别: 互斥锁互斥锁仅允许仅允许一个一个事务对相应对象执行事务对相应对象执行读读或或写写操作；操作； 共享锁共享

57、锁允许允许多个多个事务同时执行事务同时执行读读操作，不允许任何操作，不允许任何一个事务执行写操作。一个事务执行写操作。 当当设置了互斥锁和共享锁时设置了互斥锁和共享锁时 ： 若事务若事务Ti要对要对Q执行读操作，只需获得执行读操作，只需获得Q的共享锁。的共享锁。 如果如果Q已被互斥锁锁住，则已被互斥锁锁住，则Ti必须等待必须等待 。 若若Ti要对要对Q执行写操作，则执行写操作，则Ti还须获得还须获得Q的互斥锁。的互斥锁。 如果失败，须等待。如果失败，须等待。 利用共享锁和互斥锁来实现顺序性的方法，类似于利用共享锁和互斥锁来实现顺序性的方法，类似于读者读者写者问题的解法。写者问题的解法。 8.5

58、.4重复数据的数据一致性问题重复数据的数据一致性问题1重复文件的一致性重复文件的一致性(以以UNIX类型的文件系统为例类型的文件系统为例)UNIX文件目录文件目录,每个目录项中含有每个目录项中含有一个一个文件名文件名和和一个一个索引结点号索引结点号(指向一个索引结点指向一个索引结点)。 当有重复文件时，每个目录项由当有重复文件时，每个目录项由一个一个文件名文件名和和若干若干个个索引结点号索引结点号组成，每个索引结点号都是指向各自的索组成，每个索引结点号都是指向各自的索引结点。引结点。UNIX类型的目录类型的目录 文件名 i 结点 文件 1 17 文件 2 22 文件 3 12 文件 4 84 在有重复文件时，如果一个文件拷贝被修改，则必须在有重复文件时，如果一个文件拷贝被修改，则必须也同时修改其它几个文件拷贝。也同时修改其它几个文件拷贝。 实现方法：实现方法： 1)当一个文件被修改后查找文件目录，以得到其它当一个文件被修改后查找文件目录，以得到其它几个拷贝的索引结点号，从而找到各拷贝文件的物理位几个拷贝的索引结点号，从而找到各拷贝文件的物理位置，然后对这些拷贝做同样的修改；置，然后对这些拷贝做同样的修改；