外存的分配方式课件

第六章

文

件

管

理16.3.1.连续分配连续分配方式采用连续分配方式时，可把逻辑文件中的记录顺序地存储到相邻的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时物理文件称作顺序文件；为了能使系统找到文件存放的地址，在目录中应记录该文件第一个盘块号和文件长度如内存的动态分区分配，随着文件建立时的空间分配和

文件删除时的空间回收，将使磁盘空间被分割成许多小

块，这些较小的连续区（碎片）很难用来存储文件，可

以采用“紧凑”的方法，将盘上的所有文件紧靠在一起，把所有的碎片拼接成一个大片连续的存储空间。第六章

文

件

管

理1.连续分配连续分配方式的优缺点优点顺序访问容易顺序访问速度快缺点要求有连续的存储空间，易产生外部碎片,降低外存空间的利用率必须事先知道文件的长度012345678910111213141516171819202122232425262728293031filecount2start

length0

2tr153mail216list293f72目录fcounttrmaillist第六章

文

件

管

理36.3.2链接分配将文件存放在多个离散的盘块中,同一文件的盘块链接成一个链表,消除外部碎片,显著的提高了外存空间的利用率,

有利于文件插入和删除,有利于文件的动态扩充。链接方式可分为显示链接和隐式链接两种形式。1.

隐式链接在文件目录的每个目录项中,都含有指向链接文件第一个盘块和最后一个盘块的指针,而在每个盘块中都含有指向下一个盘块的指针。第六章

文

件

管

理filejeepstart

end9

25目录隐式链接0110234567891610251112131415161171819202122232425-1262728293031缺点:只适合顺序访问,随机访问要从头查找极低效。可靠性差,盘块的指针出现问题会导致链断开。更多的寻道次数和寻道时间。解决方法:可将几个盘块组成一个簇,减少查找指定块的时间，且减少指针所占空间。（内部碎片增大）4第六章

文

件

管

理2.显式链接把用于链接文件各物理块的指针，显式地存放在内存的一张链接表（称为文件分配表FAT-File

Allocation

Table）中，该表整个磁盘设置一张；在表中，凡是属于某一文件的第一个盘块号，或者每条文件链的首指针对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。查找记录在内存中进行，显著提高了检索速度，大大减少了访问磁盘的次数。2FCB0451012345FAT5物理块号第六章

文

件

管

理文件分配表（FAT）把用于链接文件各物理块的指针，放在内存的一

张链接表中，该表在整

个磁盘只有一张，称为

文件分配表（FAT）。一个磁盘分区能分为多少块,则FAT就有多少个表项N-160

01

1N-1磁盘FAT第六章

文

件

管

理7例：200MB硬盘，盘块大小=1KB，共有200K个盘块，每个盘块在FAT表中占1个表项，FAT表共有200K个表项若每个表项占2.5个字节，则FAT共占500KB=200*2.5例：12G硬盘，盘块大小=4KB，若每个FAT表项占3个字节，

FAT表占多少字节？硬盘共有3M个盘块，每个盘块在FAT表中占1个表项，FAT表共有3M个表项，则FAT共占9M=3M*3文件分配表（FAT）第六章

文

件

管

理6.3.3

FAT和NTFS技术文件系统的分类FAT文件系统：适用于

Windows98操作系统；8期的DOS和Window95，NTFS（New

Technology

File

System）文件系统：适用于后来的WindowsNT，Windows2000，WindowsXP和vista操作系统。第六章

文

件

管

理文件系统的发展–FAT12：适用于期的MS-DOS操作系统，每个FAT表项占12位。最多4096个表项，若盘块512K，则每个分区容量2M，支持4个逻辑分区，相应磁盘最大容量为8M；–FAT16：增加了FAT表的表项到65536，可以管理最大分区空间2048M，和FAT12一样不支持长文件名；–FAT32：可以支持4294967296个FAT表项，可以管理最大磁盘空间达到2TB，但是由于文件分配表扩大，运行速度慢；

P219–NTFS文件系统：专门为Windows

NT开发，的全新的文件系统，它使用64位的磁盘地址；支持长文件名（255个字符以内）全路径名（32767个字符）；具有系统容错功能；提供数据一致性；还提供文件加密、文件压缩功能。9第六章

文

件

管

理1．FAT121)以盘块为基本分配单位期MS-DOS操作系统所使用的是FAT12文件系统，每个

FAT表项占12位。在FAT的每个表项中存放下一个盘块号，文件的第一个盘块号放在自己的FCB中。10第六章

文

件

管

理图6-10MS-DOS的文件物理结构11第六章

文

件

管

理对于1.2

MB

的软盘，每个盘块的大小为

FAT

中共含有2.4

K

个表项，由于每个

FAT表占用3.6

KB的存储空间。12512

B

，在每FAT

表项占以盘块为分配单位时，所允许的最大磁盘容量：由于每个FAT表项为12位，因此，在FAT表中最多允许有

4096个表项，如果采用以盘块作为基本分配单位，每个盘块

(也称扇区)的大小一般是512字节，那么，每个磁盘分区的容量为

2

MB

(4096

×

512 B)

。同时，一个物理磁盘支持4

个辑磁盘分区，所以相应的磁盘最大容量仅为8

MB。第六章

文

件

管

理2)

簇的基本概念为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的

扇区，在

FAT 中它是作为一个虚拟扇区，

簇的大小一般(n为整数)个盘块，在MS-DOS的实际运用中，簇的容量可以仅

有一个扇区(512

B)

、两个扇区(1

KB)

、四个扇区(2

KB)

、八个扇区(4

KB)等。一个簇应包含扇区的数量与磁盘容量的大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为

8

MB当一个簇包含两个扇区时，磁盘的最大容量可以达到

16

MB

；当一个簇包含了八个扇区时，磁盘的最大容量便可达到64

MB。13第六章

文

件

管

理以簇作为基本的分配单位所带来的最主要的好处是，能

适应磁盘容量不断增大的情况。值得注意的是，使用簇作为

基本的分配单位虽可减少FAT表中的项数(在相同的磁盘容量下，FAT表的项数是与簇的大小成反比的)。这一方面会使

FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头(它与存储器管理中的页内零头相似)。14第六章

文

件

管

理3)

FAT12存在的问题FAT12对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。它只能支持8+3格式的文件名。15第六章

文

件

管

理2．FAT16FAT12表最多只允许4096个表项，亦即最多只能将一个磁盘分区分为4096个簇。随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。解决方法：应增加FAT表的宽度，将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65536(216)个簇。具有16位表宽的FAT表称为FAT16。在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64，由此得出FAT16可以管理的最大分区空间为216

×

64

×

512

=2048

MB=2GB。16第六章

文

件

管

理3．FAT32FAT32是FAT系列文件系统的最后一个产品。每一簇在

FAT表中的表项占据4字节(232)，FAT表可以表示4

294

967296项，即FAT32允许管理比FAT16更多的簇。这样就允许在

FAT32中采用较小的簇，FAT32的每个簇都固定为4KB，即每簇用8个盘块代替FAT16的64个盘块，每个盘块仍为512字节，FAT32分区格式可以管理的单个最大磁盘空间大到4KB×232

=2

TB。三种FAT类型的最大分区以及所对应的块的大小如图6-11所示。17第六章

文

件

管

理图6-11

FAT中簇的大小与最大分区的对应关系18第六章

文

件

管

理4．NTFSNTFS

文件系统：专门为Windows

NT

开发，的全新的文件系统，它使用64位的磁盘地址；支持长文件名（255个字符以内）全路径名（32767个字符）；具有系统容错功能；提供数据一致性；还提供文件加密、文件压缩功能。19第六章

文

件

管

理206.3.4.索引分配链接方式存在问题（1）不能支持高效直接存取（2）FAT需占用较大的内存空间。1.

单级索引分配：为每个文件分配一个集中存放的索引块(表),包含文件的所有物理块号，因而索引块实质就是磁盘块地址数组,其中第i项存放指向文件的第i块盘块号。在该文件的目录项中存储了指向该索引块的指针。第六章

文

件

管

理012345678910111213141516171819202122232425262728293031目录file

块序号jeep

1991611025-1-1-12119索引表索引分配方式支持直接存取。第六章

文

件

管

理优点：避免了连续空间分配存在的外部碎片问题和文件长度受限制的问题，便于文件的增、删、改。支持对任何一个文件块的直接访问。缺点：由于索引块的分配增加了系统存储空间的开销。每个文件都要单独分配一个索引块，小文件不适合。另外，存取文件需要两次访问外存——首先要读取索引块的内容，然后再访问具体的磁盘块，因而降低了文件的存取速度。22第六章

文

件

管

理232.多级索引分配对于大文件，当分配的盘块号已装满一个索引块时，必须另分配索引块，各索引块通过指针连

结起来，文件太大索引块太多时，检索索引块将

是低效的，此时应为这些索引块再建立一级索引，形成两级索引，必要时还可建立更多级的索引分

配方式。第六章

文

件

管

理两级索引分配：适用于文件太大、索引太多的情况。360主索引740……1125二级索引360磁盘空间105106254356357740985…1125……………01210510635635725498524第六章文件管理如果每个盘块的大小为1

KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时，最多可包含的存放文件的盘块的盘块号总数N=256×256=64

K个盘块号。由此可得出结论:采用两级索引时，所允许的文件最大长度为64

MB。倘若盘块的大小为4

KB，在采用单级索引时所允许的最大文件长度为4

MB；而在采用两级索引时所允许的最大文件长度可达4

GB。25第六章

文

件

管

理3.混合索引分配方式索引分配方式的索引块花费较多空间,小文件索引块利用率更低。UNIX用混合索引模式避免此缺点。即将多种索引分配方式相结合而形成的一种分配方式。每个文件的索引结点含13个地址项

i.addr(0)~

i.addr(12),前10项存放直接地址(物理块号),假如盘块大小为4KB，当文件不大于40KB时，可从直接地址项得到文件所有的盘块号；若文件大于40kB，则用i.addr(10)指向单级索引块进行一次间接寻址,每个盘块号占4个字节，该块中最多可放1k个物理块号,文件可长达4MB; 还可用

i.addr(11)

和

i.addr(12) 作为二次和三次间接寻址,

文件最大长度分别可达4GB和4TB。26第六章

文

件

管

理模式拥有者时间戳大小块数量ｉ节点(直接块)一级间接块二级间接块三级间接块数据块数据块一次间接地址二次间接地址数据块数据块数据块数据块地址数据块地址数据块数据块数据块数据块……直接地址：提高文件的检索速度；一次间接地址：针对大中型文件，允许文件长达4M；多次间接地址：二次间接地址方式，支持文件长度可达4GB，三次间接地址，支持文件长度可达4TB。27第六章

文

件

管

理题型分析：1、混合索引下计算最大文件这类题目中，混合索引一般包括若干个直接索引、一个一级间接索引和一个二级间接索引项。计算步骤如下：步骤一：计算直接索引对应的空间，直接索引项个数*物理块大小；步骤二：计算一级间接索引对应的空间，(物理块大小/每个索引项占用的字节) *物理块大小；步骤三：计算二级间接索引对应的空间，(物理块大小/每个索引项占用的字节)2*物理块大小；步骤四：将上述各步骤计算所得空间相加，即得最大文件大小。说明：对于n级间接索引，其对应的空间为(物理块大小/每个索引项占用的字节)n

*物理块大小。28第六章

文

件

管

理2、给定文件的实际大小，计算其实际占用磁盘空间文件实际占用磁盘空间大小：（数据所需的物理块+索引所需的物理块）*物理块大小。

设每块可以存储的索引项个数为k，则k=(物理块大小/每个索引项占用的字节)。步骤一：计算文件数据部分理论所需块数n，。步骤二：首先使用直接索引，直接索引不产生索引块；计算直接索引之外的数据块m1=n-直接索引项个数。步骤三：如果m1>0，则需要一个一级间接索引，索引需要1个索引块；计算一级间接索引之外的数据块m2=m1-k。29第六章

文

件

管

理步骤四：如果m2>0，则需要一个二级间接索引，如果m2<=k2，索引需要 个索引块；否则索引需要（1+k）个索引块，然后，继续计算二级间接索引之外的数据块m3=m2-k2。说明：一般题目在一个二级间接索引范围内，如果超出一个二级间接索引，则对m3继续做处理，可以采用再增加几个二级间接索引的方法，也可以采用三级间接索引。步骤五：文件实际占用磁盘空间大小：（数据所需的物理块+索引所需的物理块）*物理块大小。索引所需的物理块为一级间接索引和二级间接索引所需的物理块之和。30第六章

文

件

管

理【例】某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项，假定物理块31的大小是2K，每个索引项占用4个字节，试问：工2004】（1）该文件系统中最大的文件可以达到多大？【华南理（2）假定一个文件的实际大小是128M字节，该文件实际占用磁盘空间多大（包括间接索引块）？第六章

文

件

管

理解：（1）本题目中，混合索引包括8个直接索引、一个一级间接索引和一个二级间接索引项。步骤一：计算直接索引对应的空间，8*2K=16K；步骤二：计算一级间接索引对应的空间，(2*1024/4)*2K=1M；步骤三：计算二级间接索引对应的空间，(2*1024/4)*(2*1024/4)

*2K=512M；步骤四：将上述各步骤计算所得空间相加，即得最大文件大小：16K+1M+512M≈513M。32第六章

文

件

管

理（2）设每块可以存储的索引项个数为k，则k=2*1024/4=512。步骤一：计算文件数据部分理论所需块数n，n=128*1024/2=65536；步骤二：首先使用直接索引，直接索引不产生索引块；计算直接索引之外的数据块m1=65536-8=65528。步骤三：m1>0，则需要一个一级间接索引，索引需要1个索引块；计算一级间接索引之外的数据块m2=65528-512=65016。步骤四：m2>0，则需要一个二级间接索引，m2<=k2，索引需要 个索引块。步骤五：文件实际占用磁盘空间大小：（65536+1+128）*2K≈128.25M。33第六章

文

件

管

理3、指定要读取一个文件中的具体位置的内容，计算需要访问磁盘的次数：需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘

1次）+1个数据块（访问磁盘1次）。步骤一：计算要读取的内容所在的物理数据块号；步骤二：确定该块属于哪种索引，是直接索引、一级间接索引还是二级间接索引；步骤三：确定需要访问的索引块数，直接索引为0，一级间接索引为1，二级间接索引为2；步骤四：需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘1次）+1个数据块（访问磁盘1次）。34第六章

文

件

管

理【例】在UNIX操作系统中，给文件分配外存空间采用的是混合索引分配方式，UNIX系统中的某个文件的索引结点指示出了为该文件分配的物理块的寻找方法。在该索引结点中，有10个直接块（每个直接块都直接指向一个数据块），有1个一级间接块、1个二级间接块以及1个三级间接块，间接块指向的是一个索引块，每个索引块和数据块的大小均为4KB，而UNIX系统中地址所占空间为

4B（指针大小为4B），假设以下问题都建立在该索引结点已经在内存中的前提下。现请回答：文件的大小为多大时可以只用到索引结点的直接块？该索引结点能访问到的地址空间大小总共为多大？（小数点后保留2位）若要读取一个文件的第10

000B的内容，需要访问磁盘多少次？若要读取一个文件的第10MB的内容，需要访问磁盘多少次？35第六章

文

件

管

理【分析】对于第1小题，当文件大小小于等于所有直接索引所引导的物理数据块之和时，可以只用到索引结点的直接块；对于第2小题，根据题型二中混合索引下计算最大文件的解题思路进行解答；对于第3、4小题，根据题型三中的解题思路进行解答。解：（1）直接块为10个，数据块的大小为4KB，10*4K=40K，因此，当文件大小小于等于40K时，可以只用到索引结点的直接块。（2）步骤一：计算直接索引对应的空间，10*4K=40K；步骤二：计算一级间接索引对应的空间，(4*1024/4)

*4K=4M；步骤三：计算二级间接索引对应的空间，(4*1024/4)2*4K=4G；步骤四：计算三级间接索引对应的空间，(4*1024/4)3*4K=4TG；步骤五：将上述各步骤计算所得空间相加，即得最大文件大小：40K+4M+4G+4TG≈4TG。36第六章

文

件

管

理步骤一：计算要读取的内容所在的物理数据块号：10

000B/(4*1024B)≈2.44，2号块，即第3块；步骤二：第3块属于直接索引；步骤三：确定需要访问的索引块数，直接索引为0；步骤四：需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘1次）+1个数据块（访问磁盘1次），即0+1=1。步骤一：计算要读取的内容所在的物理数据块号：10*1024K/4K=2560，2560号块，即第2561块；步骤二：确定该块属于哪种索引，直接索引有10块、一级间接索引有

1024（即，4*1024/4）块、二级间接索引有10242块，可见，2560在直接索引和一级间接索引之外且在二级间接索引范围内，因此该块属于二级间接索引；步骤三：确定需要访问的索引块数，二级间接索引为2；步骤四：需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘1次）+1个数据块（访问磁盘1次），即2+1=3。37第六章

文

件

管

理作业：1、存放在某个磁盘上的文件系统采用混合索引分配方式，其FCB中共有13个地址项，第0到9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址。如果每个盘块的大小为512字节，若盘块号需用3个字节来描述，而每个盘块最多存放170个盘块地址，则该文件系统允许文件的最大长度是多少？将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。假设某个文件的FCB