磁盘存储器管理PPT课件.ppt

1、内容内容磁盘磁盘I/OI/O外存分配方法外存分配方法空闲存储空间的管理空闲存储空间的管理磁盘容错技术磁盘容错技术文件系统性能的改善文件系统性能的改善数据一致性控制数据一致性控制第九章第九章 磁盘存储器管理磁盘存储器管理提高提高I/OI/O速度的主要途径：速度的主要途径：1.1.选择性能好的磁盘选择性能好的磁盘2.2.采用适当的调度算法采用适当的调度算法3.3.设置磁盘高速缓冲区设置磁盘高速缓冲区9.1.1 9.1.1 磁盘性能简述磁盘性能简述9.1.2 9.1.2 磁盘调度算法磁盘调度算法9.1 9.1 磁盘磁盘I/OI/O1.1.数据的组织数据的组织1.1.盘片（盘片（Platter Pla

2、tter）磁盘最基本的组成部分是由坚硬金属材料制成的涂以磁磁盘最基本的组成部分是由坚硬金属材料制成的涂以磁性介质的盘片，不同容量硬盘的盘片数不等。每个盘片有两性介质的盘片，不同容量硬盘的盘片数不等。每个盘片有两面，都可记录信息。面，都可记录信息。2.2.磁道磁道 (Tracks)(Tracks)盘片表面上以盘片中心为圆心，不同半径的同心圆称为盘片表面上以盘片中心为圆心，不同半径的同心圆称为磁道。磁道。3.3.扇区扇区(Sectors)(Sectors)盘片被分成许多扇形的区域，每个区域叫一个扇区，硬盘片被分成许多扇形的区域，每个区域叫一个扇区，硬盘每个扇区可存储盘每个扇区可存储512512字节

3、信息。字节信息。FAT32FAT32模式下，每个扇区的模式下，每个扇区的容量为容量为4KB4KB。每个扇区的大小相当与一个盘块。每个扇区的大小相当与一个盘块。4.4.磁头磁头(Heads)(Heads)每个盘片的每一面都会有一个读写头（每个盘片的每一面都会有一个读写头（read-write headread-write head），来读取相应盘面的内容。习惯用磁头号来区分。），来读取相应盘面的内容。习惯用磁头号来区分。9.1.1 9.1.1 磁盘性能简述磁盘性能简述9.1.1 9.1.1 磁盘性能简述磁盘性能简述5.5.柱面柱面 (Cylinders)(Cylinders)不同盘片相同半径的磁

4、道所组成的圆柱称为柱面。磁道不同盘片相同半径的磁道所组成的圆柱称为柱面。磁道与柱面都是表示不同半径的圆，在许多场合，磁道和柱面与柱面都是表示不同半径的圆，在许多场合，磁道和柱面可以互换使用。可以互换使用。扇区，磁道（或柱面）和磁头数构成了硬盘结构的基本扇区，磁道（或柱面）和磁头数构成了硬盘结构的基本参数，帮这些参数，帮这些 参数可以得到硬盘的容量，基计算公式为：参数可以得到硬盘的容量，基计算公式为：存储容量磁头数存储容量磁头数磁道（柱面）数磁道（柱面）数每道扇区数每道扇区数每扇区字节数每扇区字节数1.44M=28018512 1.44M=28018512 2 2磁盘的类型磁盘的类型1.1.固定

5、头磁盘固定头磁盘l每条磁道上都有一个读每条磁道上都有一个读/写磁头，所有的磁头被装入一个磁臂写磁头，所有的磁头被装入一个磁臂l通过这些磁头可以访问所有磁道，并进行并行读写通过这些磁头可以访问所有磁道，并进行并行读写l主要用于大容量磁盘主要用于大容量磁盘2.2.移动头磁盘移动头磁盘l每个盘面仅有一个磁头，被装入一个磁臂中每个盘面仅有一个磁头，被装入一个磁臂中l为能访问盘面上的所有磁道，该磁头必须移动以进行寻道为能访问盘面上的所有磁道，该磁头必须移动以进行寻道l只能串行读只能串行读/写，致使写，致使I/OI/O速度较慢速度较慢l结构简单，广泛应用中、小型磁盘，微机上的硬盘和软盘，都采结构简单，广泛

6、应用中、小型磁盘，微机上的硬盘和软盘，都采用移动磁头结构用移动磁头结构9.1.1 9.1.1 磁盘性能简述磁盘性能简述3 3磁盘访问时间磁盘访问时间1.1.寻道时间（寻道时间（seek timeseek time）T Ts s把磁头从当前位置移到指定磁道所经历的时间，一般为把磁头从当前位置移到指定磁道所经历的时间，一般为2 23030毫秒，平均约为毫秒，平均约为1010毫秒。毫秒。T Ts s=m*n+s=m*n+ss-s-磁盘的启动时间磁盘的启动时间,大约大约3ms3ms；m-m-每移动一条磁道所经历的时间，对一般磁盘：每移动一条磁道所经历的时间，对一般磁盘：m m0.3ms0.3ms，对高

7、速磁盘：，对高速磁盘：mm0.1ms0.1ms；n-n-移动的磁道数目；移动的磁道数目；9.1.1 9.1.1 磁盘性能简述磁盘性能简述2.2.旋转延迟时间旋转延迟时间（rotational latency timerotational latency time）T Tr r指定扇区移动到磁头下所经历的时间指定扇区移动到磁头下所经历的时间。T Tr r=1/2r=1/2r（平均情况下，需要旋转半圈）（平均情况下，需要旋转半圈）rr磁盘以秒计的旋转速度磁盘以秒计的旋转速度一个一个72007200（转（转/每分钟）的硬盘，则旋转延迟时间为每分钟）的硬盘，则旋转延迟时间为60100072002601

8、000720024.174.17毫秒。毫秒。一个一个54005400（转（转/每分钟）的硬盘，旋转延迟时间为每分钟）的硬盘，旋转延迟时间为60100054002601000540025.565.56毫秒。毫秒。一个一个300/600300/600（转（转/每分钟）软盘，平均旋转延迟时间为每分钟）软盘，平均旋转延迟时间为60100030026010003002100100毫秒毫秒,6010006002,60100060025050毫秒。毫秒。9.1.1 9.1.1 磁盘性能简述磁盘性能简述3.3.传输时间传输时间T Tt t数据从磁盘读出，或向磁盘写数据所经历的时间，约数据从磁盘读出，或向磁盘写

9、数据所经历的时间，约为零点几个毫秒为零点几个毫秒,可以忽略不计。可以忽略不计。T Tt tb/b/rNrNbb读写的字节数读写的字节数 r r磁盘以秒计的旋转速度磁盘以秒计的旋转速度NN一条磁道上的字节数一条磁道上的字节数访问时间访问时间T Ta a=T=Ts s+T Tr r+T Tt t=(m*n+s)+1/2r+b/=(m*n+s)+1/2r+b/rNrN9.1.1 9.1.1 磁盘性能简述磁盘性能简述移动磁头磁道为哪个进程服务移动磁头磁道为哪个进程服务旋转磁盘扇区为哪个进程服务旋转磁盘扇区为哪个进程服务目标各进程对磁盘的平均访问时间（主要是平均寻目标各进程对磁盘的平均访问时间（主要是平

10、均寻道时间，即平均移动的磁道数目）最小道时间，即平均移动的磁道数目）最小9.1.2 9.1.2 磁盘调度算法磁盘调度算法1.1.先来先服务先来先服务FCFSFCFS（First-Come,First-ServedFirst-Come,First-Served）最简单的最简单的磁盘调度算法，根据进程请求访问磁盘的先后次磁盘调度算法，根据进程请求访问磁盘的先后次序进行调度。序进行调度。1.1.优点优点公平、简单，每个进程的请求都能依次得到处理，不会公平、简单，每个进程的请求都能依次得到处理，不会出现某个进程长时间得不到满足的情况。出现某个进程长时间得不到满足的情况。2.2.缺点缺点未对寻道进行优化

11、平均寻道时间可能较长未对寻道进行优化，平均寻道时间可能较长9.1.2 9.1.2 磁盘调度算法磁盘调度算法9.1.2 9.1.2 磁盘调度算法磁盘调度算法磁头磁头从从100#100#磁道开始磁道开始被访问的下被访问的下一个磁道号一个磁道号移动距离移动距离（磁道数）（磁道数）5555454558583 3393919191818212190907272160160707015015010103838112112184184146146平均寻道长度：平均寻道长度：55.355.32 2最短寻道时间优先最短寻道时间优先SSTFSSTF（Shortest Seek Time FirstShortes

12、t Seek Time First）选择要访问的磁道与当前磁头所在的磁道距离最近的进程选择要访问的磁道与当前磁头所在的磁道距离最近的进程1.1.优点优点每次的寻道时间最短每次的寻道时间最短2.2.缺点缺点不能保障平均寻道时间最短不能保障平均寻道时间最短,出现进程出现进程“饥饿饥饿”现象现象9.1.2 9.1.2 磁盘调度算法磁盘调度算法9.1.2 9.1.2 磁盘调度算法磁盘调度算法从从100100磁道开始磁道开始被访问的下被访问的下一个磁道号一个磁道号移动距离移动距离（磁道数）（磁道数）909010105858323255553 3393916163838727218182020150150

13、13213216016010101841842424平均寻道长度：平均寻道长度：27.427.43 3扫描算法扫描算法SCANSCAN1.1.进程进程“饥饿饥饿”现象现象在在SSTFSSTF中，若不断有新进程到来，且其访问的磁道与当中，若不断有新进程到来，且其访问的磁道与当前磁道的距离较近，这种进程被优先执行，而老进程一直得前磁道的距离较近，这种进程被优先执行，而老进程一直得不到满足。不到满足。2.2.SCANSCAN算法算法不仅考虑访问的磁道与当前磁道的距离，更优先考虑的不仅考虑访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向，又称电梯调度算法。是磁头的当前移动方向，又称电梯调度

14、算法。l优点优点较好的寻道性能，又能防止较好的寻道性能，又能防止进程进程“饥饿饥饿”现象，被广泛应用与大现象，被广泛应用与大、中、小型机及网络中的磁盘调度、中、小型机及网络中的磁盘调度l缺点缺点可能使进程的请求被严重推迟可能使进程的请求被严重推迟9.1.2 9.1.2 磁盘调度算法磁盘调度算法9.1.2 9.1.2 磁盘调度算法磁盘调度算法从从100100磁道开始，向磁道号增加的方向移动磁道开始，向磁道号增加的方向移动被访问的下被访问的下一个磁道号一个磁道号移动距离移动距离（磁道数）（磁道数）150150505016016010101841842424909094945858323255553

15、 33939161638381 118182020平均寻道长度：平均寻道长度：27.827.89.1.2 9.1.2 磁盘调度算法磁盘调度算法4 4循环扫描算法循环扫描算法CSCAN(Circular SCAN)CSCAN(Circular SCAN)规定磁头单向移动，即使最小磁道号与最大磁道号紧邻，规定磁头单向移动，即使最小磁道号与最大磁道号紧邻，形成循环。形成循环。从从100100磁道开始，向磁道号增加的方向移动磁道开始，向磁道号增加的方向移动被访问的下被访问的下一个磁道号一个磁道号移动距离移动距离（磁道数）（磁道数）150150505016016010101841842424181816

16、61663838202039391 15555161658583 390903232平均寻道长度：平均寻道长度：27.527.59.1.2 9.1.2 磁盘调度算法磁盘调度算法5 5N N步扫描算法步扫描算法N-Step-SCANN-Step-SCAN、改进前几种算法可能出现磁头静止在一个磁道上，导致其改进前几种算法可能出现磁头静止在一个磁道上，导致其它进程无法及时进行磁盘它进程无法及时进行磁盘I/OI/O。把磁盘把磁盘I/OI/O请求队列分成长度为请求队列分成长度为N N的子队列，每次使用的子队列，每次使用FCFSFCFS处理子队列处理子队列，每个队列内部，每个队列内部，使用使用SCANSC

17、AN算法处理算法处理N N个请求。个请求。当当N N很大时，该算法的性能接近于很大时，该算法的性能接近于SCANSCAN算法。算法。当当N=1N=1时，该算法退化为时，该算法退化为FCFSFCFS算法。算法。6 6双队列扫描算法双队列扫描算法FSCANFSCAN对对N N步扫描算法的简化，即把磁盘步扫描算法的简化，即把磁盘I/OI/O请求分成两个队列，请求分成两个队列，当前请求磁盘当前请求磁盘I/OI/O的进程放入一个队列，新生成的磁盘的进程放入一个队列，新生成的磁盘I/OI/O请求放请求放入另一队列中。交替使用入另一队列中。交替使用SCANSCAN算法处理一个队列。算法处理一个队列。9.2

18、9.2 外存分配方法外存分配方法即文件物理组织方式，其目标：即文件物理组织方式，其目标：1.1.有效利用外存空间有效利用外存空间2.2.提高文件的访问速度提高文件的访问速度9.2.1 9.2.1 连续分配连续分配9.2.2 9.2.2 链接分配链接分配9.2.3 9.2.3 索引分配索引分配9.2.1 9.2.1 连续分配连续分配连续分配（连续分配（Continuous AllocationContinuous Allocation）要求为每一）要求为每一个文件分配一组相邻的盘块。个文件分配一组相邻的盘块。1 1优点优点1.1.顺序访问容易：连续的空间顺序访问容易：连续的空间2.2.顺序访问速

19、度快：一条或相邻的磁道上顺序访问速度快：一条或相邻的磁道上2 2缺点缺点1.1.要求有连续的存储空间：形成外碎片要求有连续的存储空间：形成外碎片；运行时进行修改、；运行时进行修改、删除也易形成外碎片。删除也易形成外碎片。2.2.必须事先知道文件的长度：装入时要求必须事先知道文件的长度：装入时要求；预估计小于实际；预估计小于实际文件，需中止文件，需中止COPYCOPY，重新估计；若文件动态增长，应该预重新估计；若文件动态增长，应该预留空间，但会造成空间使用效率低。留空间，但会造成空间使用效率低。9.2.1 9.2.1 连续分配连续分配 filefilelengthlengthstartstart

20、countcount2 20 0trtr3 31414mailmail6 61919listlist4 42828f f2 26 60 01 12 23 34 45 56 67 78 89 910101111121213131414151516161717181819192020212122222323242425252626272728282929303031319.2.2 9.2.2 链接分配链接分配引入：引入：与内存管理类似：与内存管理类似：进程占有连续的内存空间（内、外零头）进程占有连续的内存空间（内、外零头）离散地占有内存空间；离散地占有内存空间；文件占有连续的外存空间（碎片）文件占

21、有连续的外存空间（碎片）离散地占有外存空间；离散地占有外存空间；解决方法：解决方法：在每个盘块上设一链接指针，将同属于一个文件的多个离散盘块链在每个盘块上设一链接指针，将同属于一个文件的多个离散盘块链接成一个链表，由此所形成的物理文件接成一个链表，由此所形成的物理文件链接文件。链接文件。消除了外碎片，可以动态增、删、改。消除了外碎片，可以动态增、删、改。9.2.2 9.2.2 链接分配链接分配1 1隐式链接隐式链接在文件目录的每个目录项在文件目录的每个目录项FCBFCB中含有指向链接文件第一和中含有指向链接文件第一和最后一个盘块的指针最后一个盘块的指针 只适用于顺序访问，对随机访问效率极低，可

22、靠性差。只适用于顺序访问，对随机访问效率极低，可靠性差。改进：将几个盘块组成一个簇（改进：将几个盘块组成一个簇（ClusterCluster）,在进行分配时在进行分配时以簇为单位进行，链接文件的元素也以簇为单位，这样可以成以簇为单位进行，链接文件的元素也以簇为单位，这样可以成倍减少查找时间，也可减少指针占用的存储空间，但增大了内倍减少查找时间，也可减少指针占用的存储空间，但增大了内碎片。碎片。9.2.2 9.2.2 链接分配链接分配filefilestartstartendendjeepjeep9 925250 01 12 23 34 45 56 67 78 89 91010111112121

23、3131414151516161717181819192020212122222323242425252626272728282929303031311010161625251 1-1-19.2.2 9.2.2 链接分配链接分配2 2显式链接显式链接把用于链接文件各物理块的指针，显式的存放在内存的一把用于链接文件各物理块的指针，显式的存放在内存的一张链接表中，即文件分配表张链接表中，即文件分配表FATFAT（File Allocation TableFile Allocation Table）。）。P266P2661.1.不能支持高效的直接存取不能支持高效的直接存取2.2.FATFAT占用较大

24、的内存空间占用较大的内存空间9.2.2 9.2.2 链接分配链接分配4 49 96 6EOFEOF111110105 5EOFEOF0 01 12 23 34 45 56 67 78 89 910101111FCB AFCB AFCB BFCB BFATFAT MS-DOS/Windows98 FAT表结构1 1MS-DOSMS-DOS文件系统的文件物理结构采用文件系统的文件物理结构采用FATFAT表结构。该结构表结构。该结构为了克服链接文件随机读取任一逻辑块需要化费多次盘为了克服链接文件随机读取任一逻辑块需要化费多次盘I/OI/O操作的不足，将各盘块中的链接指针集中存放在盘的操作的不足，将各

25、盘块中的链接指针集中存放在盘的开始部分，构成一张表，称为开始部分，构成一张表，称为FATFAT表。表。FATFAT表每一项存放链表每一项存放链接指针（下一个簇号），每个接指针（下一个簇号），每个FATFAT表项占表项占1212位或位或1616位，称位，称为为FAT12FAT12或或FAT16FAT16。对于软盘因为容量小，簇数也少，采用对于软盘因为容量小，簇数也少，采用1212位位FATFAT表，对于硬盘则采用表，对于硬盘则采用1616位位FATFAT表。表。2 2FATFAT表文件系统原为小硬盘的目录结构而设计，由于簇的表文件系统原为小硬盘的目录结构而设计，由于簇的数目最多只能用数目最多只能

26、用1616位表示，即最多只能有位表示，即最多只能有6464K K个簇，要用个簇，要用FATFAT表管理大的磁盘分区，只能采取增大每簇所包含的扇表管理大的磁盘分区，只能采取增大每簇所包含的扇区数，一般根据磁盘的类型和容量大小来决定簇的大小，区数，一般根据磁盘的类型和容量大小来决定簇的大小，如下表所示。当然每簇包含扇区数增加，带来内如下表所示。当然每簇包含扇区数增加，带来内零零头的浪头的浪费，这对小文件特别严重。费，这对小文件特别严重。3 3Windows98Windows98为了减少内另头的浪费，可采取每簇的数目用为了减少内另头的浪费，可采取每簇的数目用3232位表示，减少每簇包含扇区数，这称为

27、位表示，减少每簇包含扇区数，这称为FAT32FAT32。FAT16 FAT16、FAT32FAT32文件系统簇和扇区关系也见下表所示。文件系统簇和扇区关系也见下表所示。MS-DOS/Windows98 FAT表结构-19.2.3 9.2.3 索引分配索引分配1 1单级索引分配单级索引分配为每个文件分配一个索引表，把分配给该文件的盘块号，为每个文件分配一个索引表，把分配给该文件的盘块号，记录在该索引表中。文件目录中，填上指向该索引表的指针。记录在该索引表中。文件目录中，填上指向该索引表的指针。1.1.优点优点l支持直接访问支持直接访问l不产生外碎片不产生外碎片2.2.缺点缺点l索引表在外存空间，

28、需为小文件也匹配索引块。索引表在外存空间，需为小文件也匹配索引块。9.2.3 9.2.3 索引分配索引分配filefile序号序号jeepjeep19190 01 12 23 34 45 56 67 78 89 910101111121213131414151516161717181819192020212122222323242425252626272728282929303031319 9161610102525-1-19.2.3 9.2.3 索引分配索引分配2 2多级索引分配多级索引分配 P268P268105105106106254254356356357357。0 01 12 210

29、5105106106254254356356357357985985第二级索引第二级索引磁盘空间磁盘空间98598536036074074011251125主索引主索引360360740740。112511259.2.3 9.2.3 索引分配索引分配3.3.混合分配方式混合分配方式由于由于8080以上文件是小文件，为了解决能高速存取小文件和管理大文件的矛盾，以上文件是小文件，为了解决能高速存取小文件和管理大文件的矛盾，UNIXUNIX将直接寻址、一级索引、二级索引和三级索引结合起来，形成了混合寻将直接寻址、一级索引、二级索引和三级索引结合起来，形成了混合寻址方式，如下图所示。址方式，如下图所示

30、UNIX System V UNIX System V 混合寻址方式混合寻址方式1 1在在UNIX S VUNIX S V的索引结点中设有的索引结点中设有1313个地址项个地址项didi_ _addraddr13,13,它们把所存的地址项分成两类，其中最后三个地址项分它们把所存的地址项分成两类，其中最后三个地址项分别是一级索引、二级索引和三级索引的指针，而前面别是一级索引、二级索引和三级索引的指针，而前面1010个为直接寻址的地址项，即存放文件逻辑块第个为直接寻址的地址项，即存放文件逻辑块第0 09 9块的块的盘块号。盘块号。2 2如每个盘块大小为如每个盘块大小为4 4KBKB时，当文件不大

31、于时，当文件不大于4040KBKB时，便可直时，便可直接从索引结点中读出该文件全部盘块号，这样读小文件接从索引结点中读出该文件全部盘块号，这样读小文件时速度快；如文件大于时速度快；如文件大于 40 40KBKB时，系统再逐步增加一级索时，系统再逐步增加一级索引、二级索引和三级索引，这样最大管理的文件为引、二级索引和三级索引，这样最大管理的文件为4040KBKB4MB4MB4GB4GB4TB4TB，达到管理大文件的目标。达到管理大文件的目标。五、例五、例 一一个个文文件件系系统统中中有有一一个个2020MBMB大大文文件件和和一一个个2020KBKB小小文文件件,当当分分别别采采用用连连续续、链

32、链接接、单单级级索索引引、二二级级索索引引和和UNIX UNIX SytemSytem V V 分分配方案时配方案时(每块大小为每块大小为40964096B,B,每块地址用每块地址用4 4B B表示表示)，问，问:1.1.各文件系统管理的最大的文件是多少各文件系统管理的最大的文件是多少?2.2.每每种种方方案案对对大大、小小二二文文件件各各需需要要多多少少专专用用块块来来记记录录文文件件的的物物理地址理地址(说明各块的用途说明各块的用途)?)?3 3如需要读大文件前面第如需要读大文件前面第5.55.5KBKB和后面（和后面（1616M M5.5KB5.5KB）信息，信息，则每个方案各需要多少次

33、盘则每个方案各需要多少次盘I/OI/O操作操作?这个范例是帮助读者深入比较文件物理组织的各种方案：顺这个范例是帮助读者深入比较文件物理组织的各种方案：顺序文件的连续分配、链接文件的链接分配、二级索引分配、序文件的连续分配、链接文件的链接分配、二级索引分配、链接索引分配和链接索引分配和UNIXUNIX的直接间接混合分配，明确各种分配的直接间接混合分配，明确各种分配方案的优缺点和方案的优缺点和UNIXUNIX分配方案的设计特点。分配方案的设计特点。例-解答1.各种分配方案的文件系统可管理的最大文件1 1 连续分配：不受限制，可大到整个磁盘文件区。：不受限制，可大到整个磁盘文件区。2 2 链接分配：

34、同上。：同上。3 3单级单级索引：同上。：同上。4 4 二级索引：由于盘块大小为：由于盘块大小为4 4KBKB，每个地址用每个地址用4 4B B表示，表示，一个盘块可存一个盘块可存1 1K K个索引表目，二级索引可管理的最大文个索引表目，二级索引可管理的最大文件容量为件容量为4 4KB1K1KKB1K1K4GB4GB，如要管理更大的文件需采如要管理更大的文件需采用三索引，它可管理用三索引，它可管理4 4TBTB大小文件。大小文件。5 5 UNIX混合分配：可管理的最大文件为：可管理的最大文件为4040KBKB4MB+4GB4MB+4GB4TB4TB。2.每种分配方案对20MB大文件和20KB小

35、文件各需要多少专用块来记录文件的物理地址?1连续分配：对大小二个文件都只需在文件控制块：对大小二个文件都只需在文件控制块FCBFCB中设中设二项，一是首块物理块块号，另一是文件总块数，不需二项，一是首块物理块块号，另一是文件总块数，不需专用块来记录文件的物理地址。专用块来记录文件的物理地址。例-解答1 1 链接分配：对大小二个文件都只需在文件控制块：对大小二个文件都只需在文件控制块FCBFCB中设中设二项，一是首块物理块块号，另一是文件总块数；同时在二项，一是首块物理块块号，另一是文件总块数；同时在每块存文件的物理块中设置存贮下一块块号的指针。每块存文件的物理块中设置存贮下一块块号的指针。2

36、2单级单级索引：对：对2020KBKB小文件只有小文件只有5 5个物理块大小，所以只需个物理块大小，所以只需一块专用物理块来作索引块，用来保存文件的各块物理块一块专用物理块来作索引块，用来保存文件的各块物理块块号。对于块号。对于2020MBMB大文件有大文件有5 5K K个物理块大小，由于链接索引个物理块大小，由于链接索引的每个索引块只能保存（的每个索引块只能保存（1 1K K1 1）个物理块块号（还有一个物理块块号（还有一个表目作索引块链接指针），所以它需要个表目作索引块链接指针），所以它需要6 6块专用物理块块专用物理块来作链接索引块，用于保存文件各块的物理地址。来作链接索引块，用于保存文

37、件各块的物理地址。3 3 二级索引：对大小文件都固定要用二级索引，对：对大小文件都固定要用二级索引，对2020KBKB小小文件，用一块作第一级索引，用另一块作二级索引，共用文件，用一块作第一级索引，用另一块作二级索引，共用二块专用物理块作索引块，对于二块专用物理块作索引块，对于2020MBMB大文件，用一块作第大文件，用一块作第一级索引，用一级索引，用5 5块作第二级索引，共用六块专用物理块作块作第二级索引，共用六块专用物理块作索引块。索引块。范例-解答 UNIX的混合分配：对对2020KBKB小文件只需在文件控制块小文件只需在文件控制块FCBFCB的的i_i_addraddr1313中使用前

38、中使用前5 5个表目存放文件的物理块号，不个表目存放文件的物理块号，不需专用物理块。对需专用物理块。对2020MBMB大文件，大文件，FCBFCB的的i_i_addraddr1313中使用中使用前前1010个表目存放大文件前个表目存放大文件前1010块物理块块号，用一级索引块物理块块号，用一级索引块一块保存大文件接着的块一块保存大文件接着的1 1K K块块号，还要用二级索引存块块号，还要用二级索引存大文件以后的块号，二级索引使用第一级索引大文件以后的块号，二级索引使用第一级索引1 1块，第二块，第二级索引级索引4 4块。总共也需要块。总共也需要6 6块专用物理块来存放文件物理块专用物理块来存放

39、文件物理地址。地址。3.为读大文件前面第5.5KB和后面（16M5.5KB）信息需要多少次盘I/O操作?1连续分配：为读大文件前面和后面信息都需先计算信息：为读大文件前面和后面信息都需先计算信息在文件中相对块数，前面信息相对逻辑块号为在文件中相对块数，前面信息相对逻辑块号为5.55.5K K4K=14K=1，后面信息相对逻辑块号为（后面信息相对逻辑块号为（1616M M5.5K5.5K）/4K=4097/4K=4097。再计算物理块号文件首块号相对逻辑块号，最后再计算物理块号文件首块号相对逻辑块号，最后化一次盘化一次盘I/OI/O操作读出该块信息。操作读出该块信息。例-解答1链接分配：为读大文

40、件前面：为读大文件前面5.5.5.5.KBKB的信息，只需先读一的信息，只需先读一次文件头块得到信息所在块的块号，再读一次第次文件头块得到信息所在块的块号，再读一次第1 1号逻辑号逻辑块得到所需信息。而读大文件后面块得到所需信息。而读大文件后面1616MBMB5.5KB5.5KB的信息，的信息，要先把该信息所在块前面块顺序读出，共化费要先把该信息所在块前面块顺序读出，共化费40974097次盘次盘I IO O操作，才能得到信息所在块的块号，最后化一次操作，才能得到信息所在块的块号，最后化一次I/OI/O操作读出该块信息。所以总共需要操作读出该块信息。所以总共需要40984098次盘次盘I IO

41、 O才能读才能读取（取（1616MB+5.5KBMB+5.5KB）字节信息。字节信息。2 2单级单级索引：为读大文件前面：为读大文件前面5.55.5KBKB的信息，只需先读一次的信息，只需先读一次第一块索引块得到信息所在块的块号，再读一次第第一块索引块得到信息所在块的块号，再读一次第1 1号逻号逻辑块得到所需信息，共化费辑块得到所需信息，共化费2 2次盘次盘I IO O操作。为读大文件操作。为读大文件后面（后面（1616MB+5.5KBMB+5.5KB）的信息，需要先化的信息，需要先化5 5次盘次盘I IO O操作依操作依次读出各索引块，才能得到信息所在块的块号，再化一次读出各索引块，才能得到

42、信息所在块的块号，再化一次盘次盘I/OI/O操作读出该块信息。共化费操作读出该块信息。共化费6 6次盘次盘I IO O操作。操作。例-解答1二级索引：为读大文件前面和后面信息的操作相同，首：为读大文件前面和后面信息的操作相同，首先进行一次盘先进行一次盘I IO O读第一级索引块，然后根据它的相对读第一级索引块，然后根据它的相对逻辑块号计算应该读第二级索引的那块，第一级索引块逻辑块号计算应该读第二级索引的那块，第一级索引块表目号表目号=相对逻辑块号相对逻辑块号1 1K K，对文件前面信息对文件前面信息1 11 1K K0 0，对文件后面信息对文件后面信息409740971 1K K4 4，第二次

43、根据第一级索引块第二次根据第一级索引块的相应表目内容又的相应表目内容又花花一次盘一次盘I IO O读第二级索引块，得到读第二级索引块，得到信息所在块块号，再信息所在块块号，再花花一次盘一次盘I IO O读出信息所在盘块，读出信息所在盘块，这样读取大文件前面或后面信息都只需要这样读取大文件前面或后面信息都只需要3 3次盘次盘I IO O操作。操作。例-解答1UNIX混合分配：为读大文件前面：为读大文件前面5.55.5KBKB信息，先根据它的信息，先根据它的相对逻辑块号，在内存文件控制块相对逻辑块号，在内存文件控制块FCBFCB的的i_i_addraddr1313第二第二个表目中读取信息所在块块号

44、而只化费一次盘个表目中读取信息所在块块号，而只化费一次盘I IO O操操作即可读出该块信息。为读大文件后在（作即可读出该块信息。为读大文件后在（1616MBMB5 5。5KB5KB）信息，先根据它的相对逻辑块号判断它是在信息，先根据它的相对逻辑块号判断它是在UNIXUNIX二二级索引管理范围，先根据级索引管理范围，先根据i_i_addraddr1111内容化一次盘内容化一次盘I IO O操作读出第一级索引块，再计算信息所在块的索引块号操作读出第一级索引块，再计算信息所在块的索引块号在第一级索引块的表目号为（在第一级索引块的表目号为（4097-9-10244097-9-1024）1024102

45、43 3，根据第一级索引块第，根据第一级索引块第3 3个表目内容再化费一次盘个表目内容再化费一次盘I IO O操操作，读出第二级索引块，就可以得到信息所在块块号，作，读出第二级索引块，就可以得到信息所在块块号，最后化一次盘最后化一次盘I IO O读出信息所在盘块，这样总共需要读出信息所在盘块，这样总共需要3 3次次盘盘I IO O操作才能读出文件后面的信息。操作才能读出文件后面的信息。例-解答9.3 9.3 空闲存储空间的管理空闲存储空间的管理9.3.1 9.3.1 空闲表法空闲表法9.3.2 9.3.2 空闲链表法空闲链表法9.3.3 9.3.3 位示图法位示图法9.3.4 9.3.4 成组

46、链接法成组链接法9.3.1 9.3.1 空闲表法空闲表法为外存上的所有空闲区建立一张空闲表，每个空闲区对为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个表目，包括序号、该区的起始空闲盘块号、空闲盘块数应一个表目，包括序号、该区的起始空闲盘块号、空闲盘块数目等，按起始空闲盘块号排序。目等，按起始空闲盘块号排序。分配：是一种连续分配方式，顺序查找空闲表，找到分配：是一种连续分配方式，顺序查找空闲表，找到第一个合适的空闲区，修改空闲表。第一个合适的空闲区，修改空闲表。回收：回收：将相应块按序填回表中，并与前后合并成大块。将相应块按序填回表中，并与前后合并成大块。特点：连续存放，易产生碎片。特点

47、连续存放，易产生碎片。序号序号第第1 1个空白块号个空白块号空白块数空白块数物理块号物理块号1 12 24 42,3,4,52,3,4,52 29 93 39,10,119,10,113 315155 515,16,17,115,16,17,18,198,194 49.3.2 9.3.2 空闲链表法空闲链表法1 1空闲盘块链空闲盘块链将磁盘上所有空闲存储空间，以盘块为单位链成将磁盘上所有空闲存储空间，以盘块为单位链成一个链表。一个链表。分配：从链首开始，依次摘下适当数目的空闲盘分配：从链首开始，依次摘下适当数目的空闲盘块进行分配。块进行分配。回收：依次链入链尾。回收：依次链入链尾。特点：分配

48、回收简单，空闲盘块链可能很长。特点：分配、回收简单，空闲盘块链可能很长。2 2空闲盘区链空闲盘区链将磁盘上所有空闲存储空间，以盘区（包括若干将磁盘上所有空闲存储空间，以盘区（包括若干盘块）为单位链成一个链表。盘块）为单位链成一个链表。分配：查找合适大小的盘区进行分配分配：查找合适大小的盘区进行分配回收：回收：与前后与前后盘区盘区合并合并特点：分配、回收复杂，空闲盘区链较短。特点：分配、回收复杂，空闲盘区链较短。9.3.3 9.3.3 位示图法位示图法1 1位示图位示图系统为文件存储空间建立一张位示图，如下图。位示图系统为文件存储空间建立一张位示图，如下图。位示图反映了整个存储空间的分配情况，

49、其中每一位对应一个物理块反映了整个存储空间的分配情况，其中每一位对应一个物理块，“1”1”表示对应块已被分配，表示对应块已被分配，“0”0”表示对应块为空白。表示对应块为空白。1 10 00 00 01 11 10 00 00 01 11 11 11 11 10 01 10 00 01 10 00 00 01 11 11 11 11 11 11 11 11 11 11 11 11 10 00 00 01 11 11 11 11 10 00 01 10 00 00 01 12 23 34 45 56 67 78 89 91010111112121313141415150 01 12 2位位 号号

50、字字号号9.3.3 9.3.3 位示图法位示图法2 2盘块的分配盘块的分配1.1.顺序扫描位示图，找到一个或一组为顺序扫描位示图，找到一个或一组为“0”0”的二进制位的二进制位2.2.将位号、字号转换为盘块号，进行分配：将位号、字号转换为盘块号，进行分配：块号块号=位数位数*字号字号+位号位号3.3.修改位示图，置修改位示图，置“1”1”。3 3盘块的回收盘块的回收1.1.将盘块号转换为位号、字号：将盘块号转换为位号、字号：字号字号=块号块号 DIV DIV 位数位数位号位号=块号块号 MOD MOD 位数位数2.2.修改位示图，置修改位示图，置“0”0”。9.3.4 9.3.4 成组链接法成