操作系统第六章 文件管理

第六章文件管理本章要点：1）文件的概念,文件系统及其组成2）文件的逻辑结构与存储结构3）文件目录、索引结点和目录管理4）文件存储空间的分配与管理5）文件的共享与保护一、概述1）文件的概念*问题的提出计算机系统资源硬件：处理机、内存、外设其管理前已介绍软件：程序、数据如何存储,如何管理？*解决办法对程序、数据的关系或逻辑结构进行规范，使之便于存储、查找、访问。这些被规范了的，具有一定格式和结构的数据（程序）的集合称之为文件。*文件的定义：具有文件名的一组相关数据元素的集合。*文件的组成文件说明（属性）文件体*文件的结构逻辑结构：用户所能看到和可直接处理的文件的组织形式与结构。物理结构：文件在物理存储器上的组织形式与存储结构。*文件类型按性质与用途划分：系统文件，用户文件，库文件按数据的类型划分：源文件，目标代码文件，可执行文件，数据文件按数据的存取属性划分：只读文件，可读、写文件，只可执行文件按组织形式与处理方式划分：普通文件、目录文件、特殊文件文件说明文件体文件名，文件类型文件长度、文件的物理地址文件的使用情况信息…2）文件系统用于对文件进行组织、存储、共享、保护和管理的子系统。*文件系统的组成与结构文件系统接口管理程序集合文件、文件目录、文件存储空间文件系统模型3）文件操作用户通过文件系统的接口对文件所能实现的操作。*最基本操作创建文件删除文件读文件写文件设置文件读、写指针位置*打开文件与关闭文件*其他操作目录操作修改文件属性设置文件访问权限更改文件名…二、文件的逻辑结构记录式文件（又称有结构文件）流式文件（又称无结构文件）（1）记录式文件文件由若干记录组成，每个记录又由若干数据项组成。记录：数据的基本单位（也是存取访问的基本单位）数据项：数据的最小单位（指基本数据项）定长记录变长记录lllR0R1Ri…数据项1数据项2数据项n…定长记录文件R0R1R2Ri…l0l1l2li变长记录文件根据记录的不同排列方式和组织形式形成不同的逻辑文件：顺序文件索引文件索引顺序文件文件的存取方式：顺序存取直接存取（随机存取）1）顺序文件*组织结构串结构：记录按写入的时间顺序先后排列（又称无序结构）有序结构：记录按关键字（某数据项）的值有序排列*记录的查找顺序查找：适合于串结构，但查找速度较慢。折半查找、插值查找：适合于有序结构，可获得较高查找速度。*记录的存取（读写）访问顺序存取：对定长、变长记录文件均可，批量存取效率较高。直接存取：只适合定长记录，尽管变长记录亦可直接存取，但效率很低（必须依次顺序找到指定记录）。*记录的增加或删除存在一定难度，必须重新调整记录次序（缺点）。*优点：批量存取访问文件具有较高的速度。上述问题（比如变长记录直接存取问题）可采用索引文件结构来解决。2）索引文件*组织结构建立一张索引表，记录变长记录的长度及逻辑地址。关键字长度l指针PANBRWAl0l1li……索引表逻辑文件R0R1Ri……索引表本身是一个定长记录的顺序文件(直接查找较为方便)。*记录的查找、存取访问先查找索引表（可采用折半查找法查找索引表），再进行记录的存取（变长记录的直接存取方便了）。*记录的增加或删除只要修改索引表即可。添加记录置于文件尾部，在索引表中增加一表项，删除记录，一般只要删除索引表的表项即可。*缺点构造索引表增加了系统的存储开销(需辅助存储空间)。3）索引顺序文件（P211图6-5）顺序文件与索引文件的结合(每组记录建立一个索引项)。可减少索引表的长度。4）哈希（散列Hash）文件直接用关键字通过哈希函数快速查找到对应记录的地址。（2）流式文件结构文件由字符（字节数据）序列构成。可看作是特殊的记录式文件。三、文件的物理（存储）结构1）文件的存储方式连续分配存储方式离散分配存储方式链接分配方式索引分配方式2）连续分配方式文件被分割成若干部分，这些逻辑上连续的若干部分（称为逻辑块）被分别存放到磁盘的若干连续的物理盘块中（位于同一磁道或相邻磁道）*优点：有利于文件的顺序存取，且可获得较高的存取速度。*缺点：要求有足够大的连续盘块空间，不利于文件的动态增长，且易产生“磁盘碎片”。其所对应的物理文件称之为顺序文件或连续文件。3）链接分配方式为文件分配离散的盘块，其间（逻辑块间）的逻辑关系通过链接指针链接形成，链接方式有以下两种：*隐式链接：链接指针设置在物理盘块中。*显式链接：建立反映盘块链接关系的显式线性链表（或静态链表）。注、整个盘（文件卷）建立一张文件分配表（FAT），各文件通过静态链表链接在一起（P216图6-9）。*优点：无需足够大的连续盘块空间，有利于文件动态增长，还可减少磁盘碎片。*缺点：文件的直接存取需多次读盘获取链接地址（指针），因此不利于直接存取。采用显式链接需占用大量内存空间（链表或文件分配表FAT）。链接分配方式对应的物理文件又称之为串联文件。3）索引分配方式采用离散分配方式存储文件，为每个文件建立一张索引表，记录逻辑块与物理块的对应关系，通过查找索引表获得物理盘块地址。012349161102501234逻辑块物理块号文件索引块（盘块）*优点：方便直接存取（查找索引表后直接读/写盘块）。*缺点：索引表占用外存空间，需先读索引块，文件很大时，占用多个块，且查找索引表花费时间。索引表被存放在专门的盘块中，该盘块称为索引块。*索引表查找速度问题的解决采用两级索引，针对一般不太长文件采用多级索引，针对较长文件采用混合索引，长、短文件均适用*混合索引（UNIXOS采用）主索引存放在文件的索引结点之中，文件操作（打开）时被调到内存。019101112主索引表iaddr（0）~iaddr（9）iaddr（10）iaddr（11）iaddr（12）…索引结点直接地址一次间址二次间址三次间址索引分配方式对应的物理文件称为索引文件。4）三种分配方式比较连续链接索引空间要求较高（连续）不高不高存取方式顺序存取高速亦可直接存取只适合顺序存取顺序、直接存取均可缺点不利于文件动态增长，易产生磁盘碎片隐式链接不利于直接存取显式链接需占用内存空间（FAT表）索引表占用外存盘块空间，查索引表需花费一定时间文件结构归纳：逻辑结构物理结构概念与定义：用户所能看到和能够直接处理的数据的组织形式与结构文件在物理存储器上的组织形式与结构用户看不见的、根据不同分配方式形成的不同的物理文件形式：记录式文件流式文件顺序文件链接文件索引文件四、文件目录管理1）概述*目录及其作用目录：文件情况说明的集合，是一张表格，每个文件对应一个表项。作用：OS：通过文件目录对文件实施管理和操作；用户：借助文件目录对文件实施“按名存取”（访问文件）。*目录所包含的内容基本信息文件名，文件长度，文件结构，文件在外存的存储位置等。控制信息文件主的存取权限，核准用户或一般用户的权限等。使用信息文件建立（修改）日期、时间；当前共享使用该文件的用户（进程）数；文件是否被上锁，修改后是否未被拷贝到外存等。*文件控制块（FCB）文件被打开后,存放文件说明信息及存取控制信息的表。*目录的结构单级目录（简单文件目录）两级目录多级目录（树型文件目录）*目录管理的基本要求能实现“按名存取”的目标具有较高的查询（检索）速度可实现文件共享允许不同用户采用相同的文件名2）目录结构简介（1）单级目录结构文件名文件长度物理地址…状态F123K1Zs15K10Ls2K1…一个文件卷一张表格，每个文件占有一个目录项。*文件的建立和删除建立新文件：查目录，无同名文件则找一个空目录（状态为0）分配给新文件使用（填入相关说明信息）。删除文件：查目录，找到同名者，根据物理地址回收外存空间，将对应表目状态置为0（表目回收）。*优点：文件名与物理文件一一对应，可实现“按名存取”，目录结构简单，管理简单。*缺点：不允许重名，不便于共享（要求用户都用同一文件名访问）顺序查找速度较慢（当文件数很多时，平均查找表长一半）（2）两级目录结构用户名目录指针ZhangWangLi文件名物理地址Z1Z2文件名物理地址WaWb文件名物理地址LimWaZ1Z2WaWbLimWa主目录MFD（整个文件系统一张）用户文件目录UFD（每个用户一张表）*文件的建立和删除用户登录建立新文件：需分配主目录和用户文件目录空间。用户退出：需释放文件目录空间和对应主目录表目。建立、删除文件必须先查主目录，再查用户文件目录，然后实施操作。*优点提高了目录的查询（检索）速度；允许不同用户取相同文件名；可用不同文件名共享使用同一文件。*缺点当每个用户的文件数目很大时，查询速度会受到影响；共享不同用户的文件不是很方便（结构受影响）。（3）多级目录结构（三级或三级以上目录）主目录根目录子目录树的结点树型目录结构ABCABDFEDGAACJNKJMKAHF123456789101112131415161718192021*路径名从根结点（根目录）至数据文件结点通路上的结点名串例、15号文件的路径名为：/B/F/J（绝对路径名）8号文件的路径名为：/C/G*当前目录（值班目录）设置当前目录，访问文件可从当前目录开始，从而可缩短路径名的长度，提高文件查询速度。例、当前目录为12号子目录（文件），则15号文件的路径名为：J（相对路径名）*目录文件由子目录（分目录）数据构成的文件称为目录文件，其也必须有对应的文件名。*多级目录优点：具有较高的查询速度，特别是设置了当前目录，在当前目录下查找文件将更为快捷。*缺点：多级查找可能要多次读盘（读子目录文件），降低查找速度。3）索引结点为减少目录数据量，减少读盘次数，提高目录查询速度引入的新的数据结构即将文件名与文件说明信息分开存放。文件名Z1Ws索引结点编号文件长度文件结构物理地址文件长度文件结构物理地址Z1文件索引结点Ws文件索引结点Z1文件Ws文件……说明：索引结点实为文件说明表，因其中包含了索引文件的索引表，故称之为索引结点。现代操作系统大多采用树型目录结构，且都采用索引结点，记录文件的说明信息。磁盘索引结点：文件建立时生成。内存索引结点：文件操作，打开文件时建立。五、文件存储空间的分配与管理文件：存放于外存（磁盘）如何分配存储空间？分配方式以盘块为单位数据文件目录文件连续分配方式离散分配方式1）分配算法*基本要求：有利于外存空间的充分利用，具有较高的存取访问速度。*常用算法空闲表法空闲链表法位示图法成组链接法2）空闲表法*数据结构：建立一张空闲表，记录所有空闲盘区情况序号第一个空闲盘块号空闲盘块数124（2,3,4,5）293（9,10,11）3155（15,16,17,18,19）空闲表*盘块的分配与回收分配：查空闲表，找到一个足够大的空闲盘区，一分为二分配之回收：先进行回收盘区的邻接合并，再记入（修改）空闲表特点：可为文件分配连续盘块空间，但会产生磁盘碎片3）空闲链表法数据结构空闲盘区链表：以空闲盘区为单位链成一条链表空闲盘块链表：以盘块（空闲）为单位链成一条链表分配与回收（针对空闲盘块链）分配：查空闲链表，只要链表不空，便可根据文件需要的盘块数逐一摘下空闲盘块分配之。回收：将所有回收盘块一一插入（可插在链首）空闲盘块链。特点：为文件分配不连续的盘块空间，空间利用率高，但采用显式链表会占用大量内存空间，采用隐式链表会增加（分配时）读盘次数。空闲盘区链是空闲表的另一种结构形式，可采用类似可变分区分配算法为文件分配连续存储空间。4）成组链接法（UNIXOS采用）*数据结构100………300299202201019899栈顶100400399301300100500499401400299399201301第一组第二组成组链表最后一组……………………空闲盘块号栈（存放第一组的盘块的块号）*分配与回收（借助空闲盘块号栈）分配出栈。将栈顶盘块号分配出去；当分配到栈底盘块时，先将栈底盘块出栈，将该盘块数据读到内存空闲盘块号栈中，再将原栈底盘块分配出去。回收进栈。依次将回收盘块号压入栈中；当栈满时，若再