外存分配方式

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