操作系统课件第六章3

第六章文件管理操作系统Page12023/2/3第六章文件管理文件和文件系统文件的逻辑结构外存分配方式目录管理文件存储空间的管理文件共享与文件保护数据一致性控制Page22023/2/36.3外存分配方式

对于任何一个文件，都存在着以下两种形式的结构：

(1)文件的逻辑结构(FileLogicalStructure)。

(2)文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。Page32023/2/3外存分配方式如何才能有效地利用外存空间?如何提高对文件的访问速度?Page42023/2/3文件的物理结构外存的特点容量大，断电后仍可保存信息，速度较慢，成本较低两部分组成：驱动部分+存储介质种类很多外存空间组织与地址与存取方式非常复杂I/O过程方式非常复杂Page52023/2/3文件的物理结构用户对外存的要求使用：读写外存数据要求：方便、效率、安全在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作存取速度尽可能快，容量大且空间利用率高外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况以尽可能小的代价完成上述要求Page62023/2/3文件的物理结构文件的物理结构是指逻辑文件在存储设备（外存）上的存储组织形式，它与存储介质的存储特性有关一个文件存储介质，格式化后就分成许多大小相等的单位——存储块（物理盘块），一般来说，每个物理块是一个磁盘的扇区，512B。并给每个存储块有个编号，称为物理块号物理块是分配和传输信息的基本单位，其与外存设备有关，但与逻辑记录大小无关，如扇区、簇文件在逻辑上都可看作是连续的，但在物理设备上存放时却有不同的方式，如连续结构（顺序结构）、链接结构（串联结构）、索引结构、HASH文件等Page72023/2/36.1.2文件类型和文件系统模型1.文件类型5、按文件的物理结构分类（1）顺序文件。它是指把逻辑文件中的记录顺序地存储到连续的物理盘块中。（2）链接文件。它是指文件中的各个记录可以存放在不相邻接的各个物理盘块中，通过物理块中的链接指针，将它们连接成一个链表。（3）索引文件。它是指文件中的各个记录可存储在不相邻接的各个物理块中。Page82023/2/3外存分配方式连续分配链接分配索引分配Page92023/2/3连续分配连续分配(ContinuousAllocation)要求为每一个文件分配一组相邻接的盘块。一组盘块定义了磁盘上的一段线性地址在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件Page102023/2/3连续分配Page112023/2/3连续分配连续分配的主要优缺点优点结构简单，容易实现支持顺序存取和随机存取顺序存取速度快所需的磁盘寻道次数和寻道时间最少缺点要求有连续的存储空间，不利于动态扩充容易形成碎片，空间利用不充分必须事先知道文件的长度，用户不方便Page122023/2/3外存分配方式连续分配链接分配索引分配Page132023/2/3链接分配链接分配（ChainedAllocation）可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件这种文件结构不要求连续存放对于记录式文件一块中可包含一个逻辑记录或多个逻辑记录，也可以若干物理块包含一个逻辑记录链接方式隐式链接显式链接Page142023/2/3链接分配隐式链接文件名始址末址jeep925文件目录01234567891011121314151617181920212223242526272829303111016-125磁盘空间的链接式分配Page152023/2/3链接分配隐式链接每个物理块的最末一个字(或第一个字)作为链接字，它指出后继块的物理地址。链首指针存放在该文件目录中。文件的结尾块的指针为“∧”优点离散存储，空间利用率高顺序存取效率高缺点随机存取效率太低，若要访问第i个物理块，必须读出前i-1个Page162023/2/3链接分配显式链接为了克服链接文件的存取效率太低的问题，人们提出文件映照的技术，即把链接文件中的链接字集中在一结构中，这样既保持了链接文件的优点，也克服了其缺点，DOS、WINDOWS系统就采用了这样结构文件分配表（FileAllocationTable,FAT）Page172023/2/3链接分配文件分配表（FileAllocationTable,FAT）磁盘格式化后建立，从磁盘的第二个开始，有两个相同的FAT用于记录外存分配状况，每个盘块（或簇）占一项，放在内存中，整个系统一张FAT表的序号为物理盘块号或簇号，从0至N-1分配给一个文件的所有物理块都在该表中标出，文件的第一个盘块号记入文件的FCB中Page182023/2/3链接分配显式链接Page192023/2/3链接分配显式链接在FAT中每个物理块占一个表项，增加一个指针指向下一个物理块，最末一个物理块的指针为“∧”Page202023/2/3链接分配Page212023/2/3DOS磁盘盘区划分表Page222023/2/3DOS磁盘访问操作流程文件名磁盘目录表FDT磁盘参数表文件位置分配表FAT磁盘扇区定位扇区物理操作磁盘基数表Page232023/2/3链接分配实例对于1.2M磁盘，每个物理块大小为1KB，则共有1.2K个FAT表项，若每个表项占12位（1.5B），则共需1.8KB的空间来保存FAT。显式链接分配优点便于快速查找缺点FAT很大，需较大的内存空间Page242023/2/3链接分配主要优缺点优点消除了外部碎片，提高外存利用率文件动态增长时，可动态地为它分配盘块文件的增删改方便，不需事先知道文件长缺点存取速度慢只适于顺序存取，不适于随机存取可靠性差，若某一块指针出错，则链断开更多的寻道次数和寻道时间链接指针占用一定的空间Page252023/2/3外存分配方式连续分配链接分配索引分配Page262023/2/3索引分配一个文件的信息存放在若干不连续物理块中，另一种形式的非连续文件，文件数据存放的存储介质上的物理块号与文件的逻辑块号一一对应，系统为这样对应关系建立一个专用数据结构--索引表索引表：一个文件所有记录的关键字和其它地址的对照表一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块Page272023/2/3索引分配单级索引分配链接分配存在的问题不能支持高效的直接存取，要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。FAT需占用较大的内存空间索引分配为每个文件分配一个索引块，把分配给该文件的所有盘块号都记录在该索引块中在建立一个文件时，便为之建立的目录项中填上指向该索引块的指针支持直接访问对于大文件而言，该方式优于链式分配方式Page282023/2/3索引分配012345678910111213141516171819202122232425262728293031文件名索引表地址文件目录Jeep1991611025-1-1-119Page292023/2/3索引分配若每个盘块大小为1KB，每个盘块号占4B，则索引块中可存放256个盘块号，即采用这种索引方式时每个文件大小不能超过256KB索引表组织链接模式:一个盘块一个索引表,多个索引表链接起来多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中Page302023/2/3索引分配多级索引分配Page312023/2/3索引分配若每个盘块大小为1KB，每个盘块号占4B，则一级索引块中可存放256个盘块号，即对应256个二级索引块每个二级索引块可对应256个物理磁盘块，采用这种索引方式时每个文件大小不能超过256*256*1KB=64MB若每个盘块大小为4K，则最大文件大小为1K*1K*4K=4GBPage322023/2/3混合索引分配直接地址物理盘块索引块Page332023/2/3混合索引分配直接地址为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)~iaddr(9)来存放直接地址一次间接地址对于大、中型文件，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式多次间接地址当文件长度大于4MB+40KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式Page342023/2/3索引分配UNIX系统采用索引文件结构，UNIX系统采用多级间接索引结构，对小型文件采用直接索引，对大型文件采用间接索引，从而，既保证绝大多数的文件有高的存取效率，又能适应存取一些大型文件。（既保证了文件系统的高效率，又使其有很宽的适应面）Page352023/2/3Page362023/2/3索引分配索引结构优缺点优点：保持了链接结构的优点,又解决了其缺点：即能顺序存取,又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用外存空间缺点：较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间Page372023/2/3索引分配索引分配的主要问题需要较多外存空间来建立索引块对于小文件，空间浪费严重Page382023/2/3文件物理结构的比较连续文件的优点是不需要额外的空间开销，只要在文件目录中指出文件的大小和首块的块号即可，对顺序的访问效率很高。适应于顺序存取。缺点是动态地增长和缩小系统开销很大；文件创建时要求用户提供文件的大小；存储空间浪费较大。链式文件克服了连续文件的不足之处，但文件的随机访问系统开销较大。适应于顺序访问。DOS系统中改造了链式文件的结构，使其克服了链式文件的不足，但增加了系统的危险性。Page392023/2/3文件物理结构的比较索引文件既适应于顺序存访问，也适应于随机访问，