《外存组织方式》由会员分享,可在线阅读,更多相关《外存组织方式(14页珍藏版)》请在金锄头文库上搜索。
1、 目前常用的外存分配方法有:目前常用的外存分配方法有:(1 1)连续组织方式)连续组织方式(2 2)链接组织方式)链接组织方式(3 3)索引组织方式)索引组织方式。8.1 外存的组织方式外存的组织方式8.1.1连续组织方式连续组织方式要求为每一个文件分配一组相邻接的盘块要求为每一个文件分配一组相邻接的盘块。把逻辑记录中的记录,顺序地存储到邻接的各物把逻辑记录中的记录,顺序地存储到邻接的各物理盘块中,这样形成的物理文件称为理盘块中,这样形成的物理文件称为顺序文件顺序文件。countcount31145728242016128329131721252961014182226301115192327
2、0mailmaillistlistf ftrtr目录目录Filecounttrmaillistfstart01419286length23642图图8-1 磁盘空间的连续组织磁盘空间的连续组织8.1.1连续组织方式连续组织方式主要优点:主要优点:顺序访问容易。顺序访问容易。支持直接存取。支持直接存取。访问速度快。访问速度快。8.1.1连续组织方式连续组织方式要求有连续的存储空间。要求有连续的存储空间。必须事先知道文件的长度。必须事先知道文件的长度。不能灵活地删除和插入记录。不能灵活地删除和插入记录。不利于动态增长的文件。不利于动态增长的文件。主要缺点:主要缺点:8.1.2链接组织方式链接组织方
3、式 Linked Allocation链接组织方式链接组织方式消除了外部碎片消除了外部碎片,故可以显著地,故可以显著地提高提高外存空间的利用率外存空间的利用率,且,且无需事先知道文件长度无需事先知道文件长度。此。此外,文件的外,文件的插入、删除,也十分方便插入、删除,也十分方便。这样形成的物理文件称为这样形成的物理文件称为链接文件链接文件。链接方式又可分为链接方式又可分为隐式链接隐式链接和和显式链接显式链接两种方式。两种方式。在文件目录的每个目录项中,都须含有指向连接文在文件目录的每个目录项中,都须含有指向连接文件第一个盘块和最后一个盘块的指针。件第一个盘块和最后一个盘块的指针。在每个盘块中都
4、含有一个指向下一个盘块的指针。在每个盘块中都含有一个指向下一个盘块的指针。1. 隐式链接隐式链接 Implicit Link8.1.2链接组织方式链接组织方式2218141062312723191511730481216202428159131721252930261 110101616-1-12525目录File start endjeep 9 25图图8-2磁盘空间的链接组织方式磁盘空间的链接组织方式1. 隐式链接隐式链接隐式链接组织方式的主要问题隐式链接组织方式的主要问题隐式链接组织方式的主要问题隐式链接组织方式的主要问题:只适合于顺序访问,对随机访问极其低效;通过链接指针将一大批离散的
5、盘块链接起来,可靠性差。 8.1.2链接组织方式链接组织方式1. 隐式链接隐式链接2.显式链接显式链接 Explicit Link把把用用于于链链接接文文件件物物理理块块的的指指针针放放在在内内存存的的一一张张链链接接表表中中。整个磁盘仅设置一张。整个磁盘仅设置一张。表的序号是物理盘块号。在每个表项中,存放链接指针。表的序号是物理盘块号。在每个表项中,存放链接指针。凡凡是是属属于于某某一一文文件件的的第第一一个个盘盘块块号号,均均作作为为文文件件地地址址被被填入相应文件的填入相应文件的FCBFCB的的“物理地址物理地址”字段中。字段中。 此表为此表为文件分配表文件分配表文件分配表文件分配表FA
6、TFATFATFAT(File Allocation Table) File Allocation Table) 。8.1.2链接组织方式链接组织方式MS-DOS的文件物理结构的文件物理结构对于对于200MB200MB的硬盘,若盘的硬盘,若盘块的大小为块的大小为KB,KB,每个表项需每个表项需2.52.5个字节,个字节,故需占用故需占用500KB500KB。FCB A2.显式链接显式链接FCB BFAT6 65 5EOFEOFEOFEOF1010111101234567891011图图8-3 8-3 显式链接方式显式链接方式两个问题:两个问题:不能支持高效的直接存取。不能支持高效的直接存取。F
7、ATFAT需占用较大的内存空间。需占用较大的内存空间。2.显式链接显式链接8.1.3 8.1.3 索引分配方式索引分配方式索引分配方式索引分配方式(Index Allocation)(Index Allocation)1.单级索引分配单级索引分配 索引分配方法索引分配方法为每个文件分配一索引块(表)索引块(表),把分配给该文件的所有盘块号,都记录在该索引块中。在建立一个文件时,须在为之建立的目录项中,填上指向该索引块的指针。 这样形成的物理文件称为这样形成的物理文件称为链接文件链接文件。File 块序号 jeep 19目录91611025-1-1-11904812162824201631272
8、3191511732510141822263091317212529图图8-6 索引组织方式索引组织方式1.单级索引分配单级索引分配8.1.4 小结小结(1)连续组织方式连续组织方式 可随机存取,访问速度快,顺序访问容易。可随机存取,访问速度快,顺序访问容易。 要求连续存储空间,需事先知道文件长度。要求连续存储空间,需事先知道文件长度。(2)链接组织方式链接组织方式不要求连续存储空间,插入删除方便,无需知道文件不要求连续存储空间,插入删除方便,无需知道文件长度长度。随机存取效率低,随机存取效率低,FATFAT表占较大内存空间。表占较大内存空间。(3)索引分配方式索引分配方式可随机存取,不要求连续存储空间,无需知道文件长可随机存取,不要求连续存储空间,无需知道文件长度。度。 文件较小时浪费存储空间。文件较小时浪费存储空间。