操作系统课件第六章3.ppt

第六章文件管理，操作系统，第1页，2020/5/30，第六章文件管理，文件逻辑结构和文件系统文件外部存储分配模式目录管理文件存储空间管理文件共享和文件保护数据一致性控制，第2页，2020/5/30，6.3外部存储分配模式，对于任何文件，都有以下两种结构形式：(1)文件逻辑结构。(2)文件的物理结构，也称为文件的存储结构，是指文件在外部存储器上的存储组织。第3页，2020/5/30，外部存储的分配方法，如何有效利用外部存储空间？如何提高文件访问速度？第4页，2020/5/30，文件的物理结构，外部存储器的特征容量，即使在断电后也能存储信息的能力，较慢的速度和较低的成本是两个部分：驱动器部分中的存储介质的类型很多，外部存储空间的组织和地址以及访问模式非常复杂，输入/输出处理模式非常复杂，第5页，2020/5/30，文件的物理结构，用户对外部存储器使用的要求：对读取和写入外部存储数据的要求：方便，高效读写外部存储器不涉及硬件细节。使用逻辑地址和逻辑操作的访问速度尽可能快。存储在外部存储器中的信息安全可靠，容量大，空间利用率高。它便于共享、动态扩展和收缩、携带和拆卸，了解存储条件和使用条件，并以尽可能低的成本完成上述要求。第6页，2020/5/30，文件的物理结构，文件的物理结构是指逻辑文件在存储设备(外部存储器)上的存储组织形式。它与存储介质的存储特性有关。文件存储介质在格式化后被分成个大小相等的存储块(物理磁盘块)。一般来说，每个物理块是磁盘的一个扇区，512B。每个存储块都分配有一个编号，称为物理块编号。物理块是分发和传输信息的基本单元。它们与外部存储设备相关，但与逻辑记录大小无关。例如，扇区和簇文件可以被视为逻辑上连续的，但是它们以不同的方式存储在物理设备上，例如连续结构(序列结构)、链接结构(串行结构)、索引结构、HASH文件等。第7页，2020/5/30，6.1.2文件类型和文件系统模型；1.文件类型，5和(1)根据文件的物理结构分类的顺序文件。它指的是将逻辑文件中的记录顺序存储到连续的物理磁盘块中。(2)链接文件。这意味着文件中的每个记录可以存储在彼此不相邻的每个物理磁盘块中，并且它们通过物理块中的链接指针连接到一个链表中。(3)索引文件。这意味着文件中的每个记录都可以存储在不连续的物理块中。第8页，2020/5/30，外部存储分配模式，连续分配链接分配索引分配，第9页，2020/5/30，连续分配，连续分配要求为每个文件分配一组连续的磁盘块。一组磁盘块定义了当磁盘上的一段线性地址被连续分配时，逻辑文件中的记录可以顺序存储在相邻的物理磁盘块中。这样形成的文件结构称为顺序文件结构。此时的物理文件称为顺序文件。第10页，2020/5/30，连续分配，第11页，2020/5/30，连续分配。连续分配的主要优点和缺点是结构简单。很容易实现支持快速顺序访问和随机访问顺序访问所需的最小磁盘寻道次数和寻道时间。缺点是需要连续的存储空间，不利于动态扩展，容易形成碎片。由于空间利用率不足，文件的长度必须提前知道，这对用户来说很不方便。第12页，2020/5/30，外部存储分配模式，连续分配链接分配索引分配，第13页，2020/5/30，链接分配(链接分配)可以通过每个磁盘块上的链接指针将属于同一文件的多个离散磁盘块链接到链表中。这样形成的物理文件称为链接文件。这种文件结构不需要连续存储。对于记录的文件块，可以包括一个逻辑记录或多个逻辑记录。几个物理块也可以包括逻辑记录链接模式、隐式链接、显式链接、第14，2020/5/30页、链接分配、隐式链接、文件名起始地址和结束地址、jeep925、文件目录、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、25 隐式链接每个物理块的最后一个字(或第一个字)作为链接字，它指示后续块的物理地址。 链头指针存储在文件目录中。文件的结束块的指针是“”离散存储的优点、高空间利用率、高顺序存取效率以及低随机存取效率的缺点。要访问I物理块，必须读取第一个i-1，第16页，2020/5/30，链接分配和显式链接。为了克服链接文件访问效率低的问题，人们提出了一种文件映射技术，即将链接文件中的链接词集中到一个结构中。这不仅保留了链接文件的优点，还克服了它们的缺点。DOS和WINDOWS系统采用文件分配表(file allocation table，FAT)，第17页，2020/5/30，链接分配，磁盘格式化后建立的文件分配表(FAT)，从第二个磁盘开始。有两个相同的FATs用于记录外部存储的分配。每个磁盘块(或集群)占用一个项目，并存储在内存中。整个系统中FAT表的序列号是物理磁盘块号或簇号。分配给从0到N-1的文件的所有物理块都在表中标记。文件的第一个磁盘块号记录在文件的FCB中，第18页，2020/5/30，链接分配，显式链接，第19页，2020/5/30，链接分配，显式链接FAT中的每个物理块以说明一个条目，添加一个指向下一个物理块的指针，最后一个物理块的指针是“”，第20页，2020/5/30，链接分配，第21页，2020/5/30，磁盘分区表， 文件位置分配表FAT，扇区位置，扇区物理操作，磁盘基表，第23页，2020/5/30，链路分配，实例对于1.2M磁盘，每个物理块大小为1KB，有1.2K FAT表条目。 如果每个表项占用12位(1.5B)，则总共需要1.8KB的空间来节省FAT。显式链路分配的优点和缺点很容易快速找到。FAT非常大，需要很大的内存空间。第24页，2020/5/30，链接分配。它的主要优点和缺点消除了外部碎片。当外部存储利用率提高的文件动态增长时，可以方便地添加、删除和修改可以动态分配给它的磁盘文件。没有必要事先知道文件的长度。访问速度慢的缺点仅适用于顺序访问，不适用于随机访问。如果指针错了，则链断开，更多的查找次数和查找次数，链接指针占据一定的空间，页25，2020/5/30，外部存储器分配模式，连续分配链接分配索引分配，页26，2020/5/30，索引分配，一个文件的信息被存储在多个不连续的物理块中，另一种形式的不连续文件，存储文件数据的存储介质上的物理块号与文件的逻辑块号一一对应。系统为这种对应关系建立一个特殊的数据结构索引表索引表：一个文件中所有记录的关键字和其它地址的对照表。索引表是磁盘块地址数组，其中第I个条目指向文件的第I个块，第27页，2020/5/30，索引分配和单级索引分配链接分配不能支持高效的直接访问。为了直接访问较大的文件，必须在FAT中依次找到许多磁盘块号。FAT需要占用很大的内存空间。索引分配为每个文件分配一个索引块。分配给文件的所有磁盘块号都记录在索引块中。创建文件时，在为其创建的目录条目中填充指向索引块的指针，以支持直接访问。对于大文件，这种方法优于链式分配方法。第28页，2020/5/30，索引分配，文件名索引表地址，文件目录，JEEP 19、91611025-1-1-1、19、第29页，2020/5/30，索引分配，如果每个磁盘块大小为1KB，每个磁盘块编号占4B，则索引块中可以存储256个磁盘块编号，也就是说，使用此索引方法时，每个文件大小不能超过256KB索引表组织链接模式33366由多个索引表链接的多级索引：将一个大文件的所有索引表(辅助索引)的地址放在另一个索引表(主索引)中，第30页，2020/5/30，索引分配，多级索引分配，第31页，2020/5/30，索引分配。如果每个磁盘块大小为1KB，并且每个磁盘块号占用4B，则主索引块中可以存储256个磁盘块号。也就是说，对应于256个辅助索引块的每个辅助索引块可以对应于256个物理磁盘块。使用此索引方法时，每个文件的大小不能超过256*256*1KB=64MB。如果每个磁盘块大小为4K，则最大文件大小为1K * 1K * 4K=4GB，第32页，2020/5/30页，混合索引分配，直接地址，物理磁盘块，索引块，第33页，2020/5/30页，混合索引分配，直接地址为了提高文件的检索速度，可以在索引节点中设置10个直接地址项，即IADR (0)到IADR (9)用于存储一次直接地址。对于大型和中型文件，索引节点中的地址项IADR (10)可以重复使用一次来提供间接地址。该方法的实质是当文件长度超过4MB 40KB(主地址和10个直接地址项)时，系统还必须采用二次地址分配。此时，地址项iaddr(11)用于提供第二间接地址。这种方法的本质是一种两级索引分配方法，第34页，2020/5/30，索引分配。UNIX系统采用索引文件结构，UNIX系统采用多级间接索引结构，小文件采用直接索引，大文件采用间接索引。因此，它不仅保证了大部分文件的高访问效率，而且可以适应访问一些大文件。(不仅保证了文件系统的高效率，而且使其具有广泛的适应范围)，第35页，第2020/5/30页，第36页，第2020/5/30页，索引分配，索引结构的优点和缺点：保持了链接结构的优点，解决了链接结构的缺点：链接结构可以顺序和随机访问，满足了文件动态增长、插入和删除的要求。它还可以充分利用外部存储空间的缺点：更多的寻道次数和寻道次数，索引表本身带来系统开销，如：内部和外部存储空间，访问时间，页37，2020/5/30，索引分配，索引分配的主要问题需要更多的外部存储空间来构建索引块。对于小文件，空间浪费是严重的，第38页，2020/5/30，比较文件物理结构，连续文件的优点是它不需要额外的空间开销，只要文件大小和第一块的块数都在文件目录中指明，对序列的访问效率就非常高。适应顺序存取。缺点是动态增长和收缩系统非常昂贵。创建文件时，要求用户提供文件大小；存储空间的巨大浪费。链式文件克服了连续文件的缺点，但文件的随机存取系统开销很大。适应顺序存取。在DOS系统中，链文件的结构进行了改革，克服了链文件的不足，但增加了系统的危险性。第39页，2020/5/30，文件物理结构的比较索引文件适用于顺序访问和随机访问。这是一个相对较好的文件物理结