第六章 文件系统

文件系统概念文件逻辑结构与存取方法文件的物理结构与存储设备文件存储空间管理文件目录管理文件存取控制文件使用文件系统层次模型第8章文件系统(外存管理）信息是计算机系统中的重要资源。文件系统是操作系统中的一个重要组成部分，负责信息的组织、存储和访问。文件系统的功能就是提供高效、快速和方便的信息存储和访问功能。本章的主要内容就是信息的组织。8.1文件系统概念图8.1操作系统的软硬件管理8.1.1、文件系统的引入方便的文件访问和控制：以符号名称作为文件标识，便于用户使用；并发文件访问和控制：在多道程系统中支持对文件的并发访问和控制；统一的用户接口：在不同设备上提供同样的接口，方便用户操作和编程；多种文件访问权限：在多用户系统中的不同用户对同一文件会有不同的访问权限；优化性能：存储效率、检索性能、读写性能；差错恢复：能够验证文件的正确性，并具有一定的差错恢复能力；1、文件管理的目的1.文件概念文件体：文件本身的信息文件说明：文件存储和管理信息；如：文件名、文件内部标识、文件存储地址、访问权限、访问时间等文件是具有名字的一段程序或数据的集合，是相关字符流的集合或相关记录的集合。文件名是文件的标识符号。文件包括两部分：8.1.2文件与文件系统的基本概念文件系统是操作系统中管理文件的机构，是与管理文件有关的软件以及数据的统称，它负责为用户建立、撤销、读写、修改和复制文件，能提供文件存储和访问功能。2.文件系统基本概念3、文件系统特点友好的用户界面，用户只对文件操作，不管文件结构和存放的物理位置对文件按名存取，对用户透明某些文件可以被多个用户或进程共享使用磁盘、磁带或光盘等大容量存储器存储信息按存放时限分类根据系统保留文件的时间：临时文件、永久文件和档案文件。按设备类型分类根据文件存储介质的设备类型：磁盘文件、磁带文件、卡片文件和打印文件等。按文件的组织结构分类文件的逻辑结构：流式文件和记录式文件。文件的物理结构（物理文件）：顺序文件、链接文件和索引文件等。4、文件分类按文件的性质和用途划分系统文件。用户只能调用，不能修改库文件。允许用户读取和执行，不允许修改用户文件。文件的建立者能够拥有所有的权限4、文件分类（续）按组织形式，文件划分为普通文件。包括系统文件、用户文件和库函数文件和实用程序等目录文件。由目录信息构成的特殊文件。特殊文件。所有输入、输出设备组成的文件，系统在对这些设备处理时，将其看成文件处理。4、文件分类（续）文件的分类是为了更好地管理和使用，这样，不仅提高了文件的存取速度，对文件的共享和保护也有利一般系统级与用户级要进行不同的管理，例如，一个系统文件工作时要读入内存，放在内存的某一固定区，有较高的保护级别，一般用户不允许进入。而一般用户的用户文件是在另外管辖的可用区有空闲时才能被调入指定的内存用户区5、文件分类的原因8.1.3文件系统的结构和功能元素磁盘设备驱动程序磁带设备驱动程序基本文件系统基本I/O管理程序逻辑I/O堆顺序索引顺序索引哈希用户程序1、文件系统的结构启动该设备上的I/O操作，处理I/O请求处理与磁盘或磁带交换的数据块。负责所有文件I/O的开始或结束。选择执行文件的I/O设备，外存的分配；使用户和应用程序能够访问到记录。逻辑I/O处理的是文件记录。在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。设备驱动程序：负责启动该设备上的I/O操作，处理I/O请求的完成。基本文件系统（物理I/O层）：处理与磁盘或磁带交换的数据块。基本I/O管理程序：负责所有文件I/O的开始或结束。选择执行文件的I/O设备，外存的分配。2、文件系统结构元素逻辑I/O：使用户和应用程序能够访问到记录。物理I/O层处理的是数据块，逻辑I/O处理的是文件记录。它提供一种通用的记录I/O的能力。访问方法层：与用户最近的一层。在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。不同的访问方法反映出不同的文件结构和访问数据的不同方法。2、文件系统结构元素（续）文件访问：文件的创建、打开和关闭，文件的读写；目录管理：用于文件访问和控制的信息，不包括文件内容文件结构管理：划分记录，顺序，索引访问控制：并发访问和用户权限限额(quota)：限制每个用户能够建立的文件数目、占用外存空间大小等审计(auditing)：记录对指定文件的使用信息（如访问时间和用户等），保存在日志中3.文件系统服务功能元素4.文件系统实现的功能模块文件的分块存储：与外存的存储块相配合I/O缓冲和调度：性能优化文件定位：在外存上查找文件的各个存储块外存存储空间管理：如分配和释放。主要针对可改写的外存如磁盘。外存设备访问和控制：包括由设备驱动程序支持的各种基本文件系统如硬盘，软盘，CDROM等8.2文件的逻辑结构与存取方法文件组织讨论文件的内部逻辑结构，主要考虑因素是文件存储性能和访问性能。8.2.1文件的逻辑结构文件逻辑结构的设计要求：访问性能：便于检索；便于修改存储性能：向物理存储转换方便，节省空间，可靠性，维护简单文件的不同组织层次：域、记录、文件文件的逻辑结构是指从用户观点出发讨论文件内部的逻辑结构(logicalstructure)或用户访问模式；它可以独立于在外存上的物理存储。是用户可以直接处理的数据及其结构。（1）无结构文件文件体为字节流，不划分记录，顺序访问，每次读写访问可以指定任意数据长度。当前操作系统中常用的文件组织。1、文件逻辑结构分类概念：把文件中的记录按照各种不同的方式排列，构成不同的逻辑结构，方便用户对文件的各种操作。记录：一个具有特殊意义的信息单位，由该记录在文件中的逻辑地址（相对位置）与记录名所对应的一组关键字、属性及属性值组成。（2）、有结构文件－记录式文件图8.2记录组成典型记录的组成元素连续结构多重结构转置结构2、记录式结构文件分类概念：把记录按生成的先后顺序连续排列的逻辑结构。特点：适用性强，可用于所有文件，记录的排列顺序与记录内容无关，有利于记录的追加和变更。缺点：查找性能比较差（1）连续结构概念把记录按关键字和记录名排列成行列式结构，则一个包含n个记录名、m个关键字的文件构成一m×n维行列式。特点能根据关键字和记录名快速定位某条记录缺点浪费空间，n条记录需要m*n的空间改进措施：采用多重队列。将行列式中为0的项去除，以关键字ki为队首，以包含关键字ki的记录为队列元素构成一个记录队列。M个关键字就构成了多个队列。（2）多重结构文件记录式结构之多重结构及改进图图8.3文件的记录名和关键字构成的行列式图8.4文件的多重结构概念把含有相同关键字的记录指针全部指向该关键字，即把所有与同一关键字对应的记录指针连续置于目录中该关键字位置，是对多重结构的变化图8.5文件的转置结构（3）转置结构4、顺序结构（索引结构）概念：按照某种关键字排序进行存放优点：能够根据待查记录的关键字快速找到某个记录（1）累积文件——pile堆文件文件体为无结构记录序列，通过分隔符来划分记录，各记录大小和组成可变。新记录总是添加到文件末尾。如日志log，或电子邮件的邮箱文件(mailbox)。检索必须从头开始。是一种简单的文件组织方式，当数据难以组织时使用。4、记录式文件结构具体实例2、顺序文件文件体为大小相同、格式固定的排序记录序列。它由一个主文件和一个临时文件组成。记录按某个关键字域(keyfield)排序，存放在主文件(masterfile)中。新记录暂时保存在日志或事务文件等临时文件中(logfileortransactionfile)，定期归并入主文件，并按正确顺序产生一个新文件。访问时可以采用二分搜索。在顺序文件（主文件mainfile）的基础上，另外建立索引(index)和溢出文件(overflowfile)。这样做的目的是加快顺序文件的检索速度。在索引文件中，可将关键字域中的取值划分若干个区间（如A~Z可以划分为A到Z共28个区间），每个区间对应一个索引项，后者指向该区间的开头记录。新记录暂时保存在溢出文件中，定期归并入主文件。主文件中记录要求做到分块有序3、索引顺序文件3、索引顺序文件关键字逻辑地址姓名其它属性ABZAnBingAnKangAnQingBaoRongBiJingBonLong索引文件顺序文件索引顺序文件特点特点通过划分层次，在记录数量较大时，比顺序文件大大缩短检索时间。顺序文件是N/2(这时可使用折半查找)，而索引顺序文件（一级索引）是i/2+N/(2*i)，其中i为索引长度。索引还可以是多级的。如：有1000,000条记录的顺序文件的平均检索长度为500,000，而在添加一个有1000条索引项的索引文件后，平均检索长度为1000。索引顺序文件限制：基于文件的一个关键字域（属性）进行处理。当需要基于其他域而不是关键字域进行搜索一个记录时，将会受到限制；直接访问磁盘中任何一个地址已知的块。记录大小相同。由主文件和溢出文件组成。记录位置由哈希函数确定。检索时给出记录编号，通过哈希函数计算出该记录在文件中的相对位置。访问速度快，通常一次只访问一条记录。5、哈希文件或直接文件用户在一个文件上的操作：“读”和“写”。写：存储介质→内存读：内存→存储介质顺序存取法:按照文件信息的逻辑顺序依次存取。按记录的排列顺序来存取。如：为了存取记录Ri,必须先通过记录R1R2…Ri-1随机存取法(直接存取）:可以按任意的次序对文件进行读写操作。如可根据记录的编号来直接存取文件中的任意一个记录索引存取：对文件中的记录按某个数据项的值进行排列，从而可以根据键值来快速存取。8.2.2文件的存取方法概念又称索引存取，根据关键字来快速定位记录在文件中的位置，从而进行文件内容的修改。在具体的查找过程中，分为关键字搜索、记录的搜索或二者的结合搜索（见下图）1、关键字存取法对指定记录Ri的搜索过程如下：对文件中的内容进行存取，根据记录是否根据关键字进行排序，可划分为线性搜索法散列法二分搜索法（1）线性搜索法特点：最简单、最直观的搜索法。从第一个记录开发搜索，直到找到或在未找到情况下搜索到最后一个记录结束。搜索时间复杂度和文件中记录长度成正比。缺点：搜索效率低。2、记录搜索算法定义：根据关键字，采用相应的散列函数，得到某个记录在文件中的逻辑地址。如果有两个关键字对应的地址相同，则采用再散列或其他方法来解决地址冲突问题。特点：能够根据关键字快速定位相同关键字的记录，在最理想情况下能够一次定位。（2）散列法概念：首先要根据关键字大小进行排序，每次取记录中间值和待查关键字进行比较，以此类推。（3）二分搜索法文件的使用:文件的性质决定了文件的使用，也决定了存取方式的选择。例如，如源程序文件用顺序存取法、数据库文件用随机存取法存储介质的特性磁带：适合顺序存取。总是从磁头的当前位置开始读写磁带上的信息。磁盘：既可采用顺序存取方式，又可采用随机存取方式。3、文件存取方法的相关因素从文件在物理介质上的存放方式来研究文件。连续结构（顺序）串联结构索引结构8.3文件的物理结构与存储设备一个文件的信息存放在若干连续物理块中优点:简单，适用于一次性写入的操作支持顺序存取和随机存取，顺序存取速度快所需的磁盘寻道次数和寻道时间最少（因为由于空间的连续性，当访问下一个磁盘块时，一般无需移动磁头）目录文件名起始地址大小Hello.c22Zl.c95z.out21301518311、连续结构(顺序)缺点:文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）不利于文件插入和删除外部碎片问题（反复增删文件后）文件A第一个物理块号文件长度（4）文件说明信息10131211…...物理存储设备0123物理块号逻辑块号1.连续结构(顺序)（续）类似于数组1.连续结构－存储图示概念一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。第一个物理块号……文件说明信息2215物理存储设备0123物理块号逻辑块号连接指针25020152225思考：如何实现逻辑块号到物理块号的转换