外存的分配方式

null6.3 外存的分配方式6.3 外存的分配方式 为文件分配外存空间要考虑主要问题是怎样才能有效地利用外存空间和如何提高对文件的访问速度。常用的外存分配方法： 连续分配（Continuous Allocation）：为每个文件分配一组相邻接的盘块； 链接分配（Chained Allocation）：通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链（链接文件）； 索引分配（Indexed Allocation）：为每个文件分配一个索引块（表），再把分配给该文件的所有盘块号都记录在这个索引块（盘块号的数组）中。null6.3.1. 连续分配连续分配方式 采用连续分配方式时，可把逻辑文件中的记录顺序地存储到相邻的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时物理文件称作顺序文件； 为了能使系统找到文件存放的地址，在目录中应记录该文件第一个盘块号和文件长度 如内存的动态分区分配，随着文件建立时的空间分配和文件删除时的空间回收，将使磁盘空间被分割成许多小块，这些较小的连续区（碎片）很难用来存储文件，可以采用“紧凑”的方法，将盘上的所有文件紧靠在一起，把所有的碎片拼接成一个大片连续的存储空间。null1. 连续分配连续分配方式的优缺点 优点 顺序访问容易 顺序访问速度快 缺点 要求有连续的存储空间，易产生外部碎片, 降低外存空间的利用率 必须事先知道文件的长度012345678910111213141516171819202122232425262728293031file start length count 0 2 tr 15 3 mail 21 6 list 29 3 f 7 2目 录countfcounttrmaillistnull6.3.2 链接分配 将文件存放在多个离散的盘块中,同一文件的盘块链接成一个链表,消除外部碎片,显著的提高了外存空间的利用率, 有利于文件插入和删除,有利于文件的动态扩充。 链接方式可分为显示链接和隐式链接两种形式。 1. 隐式链接 在文件目录的每个目录项中,都含有指向链接文件第一个盘块和最后一个盘块的指针,而在每个盘块中都含有指向下一个盘块的指针。null隐式链接 0101234567816925101112131415161718192021222324-125262728293031file start end jeep 9 25目 录1 缺点: 只适合顺序访问, 随机访问要从头查找极低效。可靠性差, 盘块的指针出现问题会导致链断开。更多的寻道次数和寻道时间。 解决方法:可将几个盘块组成一个簇, 减少查找指定块的时间，且减少指针所占空间。（内部碎片增大）null2. 显式链接把用于链接文件各物理块的指针，显式地存放在内存的一张链接表（称为文件分配表FAT-File Allocation Table）中，该表整个磁盘设置一张； 在表中，凡是属于某一文件的第一个盘块号，或者每条文件链的首指针对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。 查找记录在内存中进行，显著提高了检索速度，大大减少了访问磁盘的次数。FCB20451012345FAT物理块号文件分配表（FAT）文件分配表（FAT）把用于链接文件各物理块的指针，放在内存的一张链接表中，该表在整个磁盘只有一张，称为文件分配表（FAT）。 一个磁盘分区能分为多少块, 则FAT就有多少个表项 null例：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）null6.3.3 FAT和NTFS技术文件系统的分类 FAT文件系统：适用于早期的DOS和Window95，Windows98操作系统； NTFS（New Technology File System）文件系统：适用于后来的WindowsNT，Windows2000，WindowsXP和vista操作系统。null文件系统的发展 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个字符）；具有系统容错功能；提供数据一致性；还提供文件加密、文件压缩功能。null　　1．FAT12 　　1) 以盘块为基本分配单位 　　早期MS-DOS操作系统所使用的是FAT12文件系统，每个FAT表项占12位。在FAT的每个表项中存放下一个盘块号，文件的第一个盘块号放在自己的FCB中。 null图6-10　MS-DOS的文件物理结构 null对于1.2 MB的软盘，每个盘块的大小为512 B，在每个FAT中共含有2.4 K个表项，由于每个FAT表项占12位，故FAT表占用3.6 KB的存储空间。 以盘块为分配单位时，所允许的最大磁盘容量： 由于每个FAT表项为12位，因此，在FAT表中最多允许有4096个表项，如果采用以盘块作为基本分配单位，每个盘块(也称扇区)的大小一般是512字节，那么，每个磁盘分区的容量为2 MB(4096×512 B)。同时，一个物理磁盘支持4个逻辑磁盘分区，所以相应的磁盘最大容量仅为8 MB。null　　2) 簇的基本概念 　　为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n (n为整数)个盘块，在MS-DOS的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个扇区(1 KB)、四个扇区(2 KB)、八个扇区(4 KB)等。 一个簇应包含扇区的数量与磁盘容量的大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为8 MB；当一个簇包含两个扇区时，磁盘的最大容量可以达到16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到64 MB。null　　以簇作为基本的分配单位所带来的最主要的好处是，能适应磁盘容量不断增大的情况。值得注意的是，使用簇作为基本的分配单位虽可减少FAT表中的项数(在相同的磁盘容量下，FAT表的项数是与簇的大小成反比的)。这一方面会使FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头(它与存储器管理中的页内零头相似)。 null　　3) FAT12存在的问题 FAT12对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。 它只能支持8+3格式的文件名。 null2．FAT16 FAT12表最多只允许4096个表项，亦即最多只能将一个磁盘分区分为4096个簇。随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。 解决方法：应增加FAT表的宽度，将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65 536(216)个簇。 具有16位表宽的FAT表称为FAT16。 在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64，由此得出FAT16可以管理的最大分区空间为216 × 64 × 512 = 2048 MB=2GB。 　　null　　3．FAT32 　　FAT32是FAT系列文件系统的最后一个产品。每一簇在FAT表中的表项占据4字节(232)，FAT表可以表示4 294 967 296项，即FAT32允许管理比FAT16更多的簇。这样就允许在FAT32中采用较小的簇，FAT32的每个簇都固定为4 KB，即每簇用8个盘块代替FAT16的64个盘块，每个盘块仍为512字节，FAT32分区格式可以管理的单个最大磁盘空间大到4 KB×232 = 2 TB。 三种FAT类型的最大分区以及所对应的块的大小如图6-11所示。 null图6-11 FAT中簇的大小与最大分区的对应关系 null　　4．NTFS 　　NTFS文件系统：专门为Windows NT开发，的全新的文件系统，它使用64位的磁盘地址；支持长文件名（255个字符以内）全路径名（32767个字符）；具有系统容错功能；提供数据一致性；还提供文件加密、文件压缩功能。null6.3.4. 索引分配链接方式存在问题（1）不能支持高效直接存取（2）FAT需占用较大的内存空间。 1. 单级索引分配： 为每个文件分配一个集中存放的索引块(表),包含文件的所有物理块号，因而索引块实质就是磁盘块地址数组,其中第i项存放指向文件的第i块盘块号。在该文件的目录项中存储了指向该索引块的指针。 null索引分配方式支持直接存取。null优点： 避免了连续空间分配存在的外部碎片问题和文件长度受限制的问题，便于文件的增、删、改。 支持对任何一个文件块的直接访问。 缺点： 由于索引块的分配增加了系统存储空间的开销。每个文件都要单独分配一个索引块，小文件不适合。 另外，存取文件需要两次访问外存——首先要读取索引块的内容，然后再访问具体的磁盘块，因而降低了文件的存取速度。 null2. 多级索引分配 对于大文件，当分配的盘块号已装满一个索引块时，必须另分配索引块，各索引块通过指针连结起来，文件太大索引块太多时，检索索引块将是低效的，此时应为这些索引块再建立一级索引，形成两级索引，必要时还可建立更多级的索引分配方式。 null两级索引分配：适用于文件太大、索引太多的情况。360主索引740……1125二级索引磁盘空间1051062543603563577409851125………………012105106356357254985null如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时， 最多可包含的存放文件的盘块的盘块号总数N = 256 × 256 = 64 K个盘块号。由此可得出结论: 采用两级索引时，所允许的文件最大长度为64 MB。 倘若盘块的大小为4 KB，在采用单级索引时所允许的最大文件长度为4 MB；而在采用两级索引时所允许的最大文件长度可达4 GB。 null3. 混合索引分配方式 索引分配方式的索引块花费较多空间,小文件索引块利用率更低。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。null数据块数据块一次间 接地址二次间 接地址数据块数据块数据块数据块 地址数据块 地址数据块数据块数据块数据块……直接地址：提高文件的检索速度； 一次间接地址：针对大中型文件，允许文件长达4M； 多次间接地址：二次间接地址方式，支持文件长度可达4GB，三次间接地址，支持文件长度可达4TB。null题型分析：1、混合索引下计算最大文件 这类题目中，混合索引一般包括若干个直接索引、一个一级间接索引和一个二级间接索引项。计算步骤如下： 步骤一：计算直接索引对应的空间，直接索引项个数*物理块大小； 步骤二：计算一级间接索引对应的空间，(物理块大小/每个索引项占用的字节) *物理块大小； 步骤三：计算二级间接索引对应的空间，(物理块大小/每个索引项占用的字节)2*物理块大小； 步骤四：将上述各步骤计算所得空间相加，即得最大文件大小。 说明：对于n级间接索引，其对应的空间为(物理块大小/每个索引项占用的字节)n *物理块大小。null2、给定文件的实际大小，计算其实际占用磁盘空间 文件实际占用磁盘空间大小： （数据所需的物理块+索引所需的物理块）*物理块大小。 设每块可以存储的索引项个数为k，则k=(物理块大小/每个索引项占用的字节)。 步骤一：计算文件数据部分理论所需块数n，。 步骤二：首先使用直接索引，直接索引不产生索引块；计算直接索引之外的数据块m1=n-直接索引项个数。 步骤三：如果m1>0，则需要一个一级间接索引，索引需要1个索引块；计算一级间接索引之外的数据块m2=m1-k。null步骤四：如果m2>0，则需要一个二级间接索引，如果m2<=k2，索引需要 个索引块；否则索引需要（1+k）个索引块，然后，继续计算二级间接索引之外的数据块m3=m2-k2。 说明：一般题目在一个二级间接索引范围内，如果超出一个二级间接索引，则对m3继续做处理，可以采用再增加几个二级间接索引的方法，也可以采用三级间接索引。 步骤五：文件实际占用磁盘空间大小：（数据所需的物理块+索引所需的物理块）*物理块大小。索引所需的物理块为一级间接索引和二级间接索引所需的物理块之和。 null【例】某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项，假定物理块的大小是2K，每个索引项占用4个字节，试问： 【华南理工2004】 （1）该文件系统中最大的文件可以达到多大？ （2）假定一个文件的实际大小是128M字节，该文件实际占用磁盘空间多大（包括间接索引块）？null解： （1）本题目中，混合索引包括8个直接索引、一个一级间接索引和一个二级间接索引项。 步骤一：计算直接索引对应的空间，8*2K=16K； 步骤二：计算一级间接索引对应的空间，(2*1024/4) *2K=1M； 步骤三：计算二级间接索引对应的空间，(2*1024/4) *(2*1024/4) *2K=512M； 步骤四：将上述各步骤计算所得空间相加，即得最大文件大小：16K+1M+512M≈513M。null（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。null3、指定要读取一个文件中的具体位置的内容，计算需要访问磁盘的次数： 需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘1次）+1个数据块（访问磁盘1次）。 步骤一：计算要读取的内容所在的物理数据块号； 步骤二：确定该块属于哪种索引，是直接索引、一级间接索引还是二级间接索引； 步骤三：确定需要访问的索引块数，直接索引为0，一级间接索引为1，二级间接索引为2； 步骤四：需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘1次）+1个数据块（访问磁盘1次）。null【例】在UNIX操作系统中，给文件分配外存空间采用的是混合索引分配方式，UNIX系统中的某个文件的索引结点指示出了为该文件分配的物理块的寻找方法。在该索引结点中，有10个直接块（每个直接块都直接指向一个数据块），有1个一级间接块、1个二级间接块以及1个三级间接块，间接块指向的是一个索引块，每个索引块和数据块的大小均为4KB，而UNIX系统中地址所占空间为4B（指针大小为4B），假设以下问题都建立在该索引结点已经在内存中的前提下。 现请回答： （1）文件的大小为多大时可以只用到索引结点的直接块？ （2）该索引结点能访问到的地址空间大小总共为多大？（小数点后保留2位） （3）若要读取一个文件的第10 000B的内容，需要访问磁盘多少次？ （4）若要读取一个文件的第10MB的内容，需要访问磁盘多少次？null【分析】对于第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。null（3）步骤一：计算要读取的内容所在的物理数据块号：10 000B/(4*1024B)≈2.44，2号块，即第3块； 步骤二：第3块属于直接索引； 步骤三：确定需要访问的索引块数，直接索引为0； 步骤四：需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘1次）+1个数据块（访问磁盘1次），即0+1=1。 （4）步骤一：计算要读取的内容所在的物理数据块号：10 *1024K/4K=2560，2560号块，即第2561块； 步骤二：确定该块属于哪种索引，直接索引有10块、一级间接索引有1024（即，4*1024/4）块、二级间接索引有10242块，可见，2560在直接索引和一级间接索引之外且在二级间接索引范围内，因此该块属于二级间接索引； 步骤三：确定需要访问的索引块数，二级间接索引为2； 步骤四：需要访问磁盘的次数=需要访问的索引块数（每块访问磁盘1次）+1个数据块（访问磁盘1次），即2+1=3。null作业：1、存放在某个磁盘上的文件系统采用混合索引分配方式，其FCB中共有13个地址项，第0到9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址。如果每个盘块的大小为512字节，若盘块号需用3个字节来描述，而每个盘块最多存放170个盘块地址，则 （1）该文件系统允许文件的最大长度是多少？ （2）将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。 （3）假设某个文件的FCB已在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要访问几次磁盘？最多需要访问几次磁盘？思考题：思考题： 一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用连续、链接、二级索引和UNIX S V 分配方案时(每块大小为4096B,每块地址用4B表示)，问: 1.各文件系统管理的最大的文件是多少? 2.每种方案对大、小二文件各需要多少专用块来记录文件的物理地址(说明各块的用途) ? 解答：解答：1：各种分配方案的文件系统可管理的最大文件 连续分配：不受限制，可大到整个磁盘文件区。 链接分配：同上。 二级索引：由于盘块大小为4KB，每个地址用4B表示，一个盘块可存1K个索引表目，二级索引可管理的最大文件容量为4KB×1K×1K＝4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件。 UNIX混合分配：可管理的最大文件为40KB＋4MB+4GB＋4TB。解答：解答：2：每种分配方案对20MB大文件和20KB小文件各需要多少专用块来记录文件的物理地址? 连续分配：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件总块数，不需专用块来记录文件的物理地址。 链接分配：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件尾块数；同时在每块存文件的物理块中设置存贮下一块块号的指针。解答：解答： 二级索引：对大小文件都固定要用二级索引，对20KB小文件，用一块作第一级索引，用另一块作二级索引，共用二块专用物理块作索引块，对于20MB大文件，用一块作第一级索引，用5块作第二级索引，共用六块专用物理块作索引块。 UNIX的混合分配：对20KB小文件只需在文件控制块FCB的i_addr[13]中使用前5个表目存放文件的物理块号，不需专用索引块。对20MB大文件，FCB的i_addr[13]中使用前10个表目存放大文件前10块物理块块号，用一级索引块一块保存大文件接着的1K块块号，还要用二级索引存大文件以后的块号，二级索引使用第一级索引1块，第二级索引4块。总共也需要6块专用物理块来存放文件物理地址。