操作系统第7章

第7章文件系统7.1文件系统的概念7.2文件的逻辑结构与存取方法7.3文件的物理结构与存储设备7.4文件存储空间管理7.5文件目录管理7.6文件存取控制7.7文件的使用7.8文件系统的层次模型本章小结习题7.1文件系统的概念1.文件系统的引入操作系统对计算机的管理包括两个方面：硬件资源的管理和软件资源的管理。图7.1操作系统的软硬件管理用户的遇到的问题：(1)使用现有的软件资源来协助完成自己的任务。(2)编制完成的或未完成的程序存放在什么地方,需要访问的数据存放在什么地方，从而使得人们可以再利用已有的软件资源。事实上，这两个问题是一个怎样对软件资源（程序和数据）进行透明存放存储器的出现，为程序和数据等软件资源的透明存取提供了物质基础。这导致了对软件资源管理质的飞跃——文件系统的出现。文件系统必须完成下列工作：(1)为了合理的存放文件，必需对磁盘等辅助存储器空间(或称文件空间)进行统一管理。(2)为了实现按名存取，需要有一个用户可见的文件逻辑结构，用户按照文件逻辑结构所给定的方式进行信息的存取和加工。这种逻辑结构是独立于物理存储设备的。(3)为了便于存放和加工信息，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。(4)完成对存放在存储设备上的文件信息的查找。(5)完成文件的共享和提供保护功能。2.文件与文件系统的概念(1)文件在计算机系统中，文件被解释为一组赋名的相关联字符流的集合，或者是相关联记录(一个有意义的信息单位)的集合。流式文件记录式文件(2)文件系统操作系统中与管理文件有关的软件和数据称为文件系统。它负责为用户建立文件，撤消、读写、修改和复制文件，还负责完成对文件的按名存取和进行存取控制。文件系统具有以下特点：①友好的用户接口，用户只对文件进行操作，而不管文件结构和存放的物理位置。②对文件按名存取，对用户透明。③某些文件可以被多个用户或进程所共享。④文件系统大都使用磁盘、磁带和光盘等大容量存储器作为存储介质，因此，可存储大量信息。3.文件的分类按文件的性质和用途可以分为三类：(1)系统文件该类文件只允许用户通过系统调用来执行它们，而不允许对其进行读写和修改。这些文件主要由操作系统核心和各种系统应用程序和数据所组成。(2)库文件该类文件允许用户对其进行读取、执行，但不允许对其进行修改。库文件主要由各种标准子程序库组成。如C语言子程序库、FORTRAN子程序库等。(3)用户文件用户文件是用户委托文件系统保存的文件。这类文件只由文件的所有者或所有者授权的用户才能使用。用户文件主要由源程序、目标程序、用户数据库等组成。另外，按组织形式，文件又可被画分为以下三类：(1)普通文件普通文件既包括系统文件，也包括用户文件和库函数文件、实用程序文件。普通文件主要是指组织格式为系统中所规定的最一般格式的文件，例如由字符流组成的文件。(2)目录文件目录文件是由文件的目录信息构成的特殊文件。即该文件的内容不是各种程序或应用数据，而是用来检索普通文件的目录信息。(3)特殊文件在UNIX系统中，所有的输入、输出设备都被看作特殊文件。这组特殊文件在使用形式上与普通文件相同，如查找目录、存取操作等。还可以按文件中的信息流向或文件的保护级别等分类。例如，按信息流向可把文件分为：输入文件、输出文件、以及输入/输出文件等。按文件的保护级别又可分为：只读文件、读写文件、可执行文件和不保护文件等。7.2文件的逻辑结构与存取方法7.2.1逻辑结构文件的逻辑结构可分为两大类：字符流式的无结构文件和记录式的有结构文件。选取文件的逻辑结构应遵循下述原则：(1)当用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少对已存储好的文件信息的变动。(2)当用户需要对文件信息进行操作时，给定的逻辑结构应使文件系统在尽可能短的时间内查找到需要查找的记录或基本信息单位。(3)应使文件信息占据最小的存储空间。(4)应是便于用户进行操作的。字符流的无结构文件：查找文件中的基本信息单位，是比较困难的，但管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，例如，源程序文件、目标代码文件等。记录式的有结构文件可把文件中的记录按各种不同的方式排列，构成不同的逻辑结构，以便用户对文件中的记录进行修改、追加、查找和管理等操作。记录是一个具有特定意义的信息单位，它由该记录在文件中的逻辑地址(相对位置)与记录名所对应的一组键、属性及其属性值所组成。图7.2是一个记录的组成例。图7.2记录组成例常用的记录式结构文件有以下几种:(1)连续结构连续结构是一种把记录按生成的先后顺序连续排列的逻辑结构。连续结构的特点是适用性强，可用于所有文件，且记录的排列顺序与记录的内容无关。这有利于记录的追加与变更。但是，连续结构文件的搜索性能较差，例如要找出某个指定键的记录时，系统必须对文件全体进行搜索。(2)多重结构如果把记录按键和记录名排列成行列式结构图7.3文件的记录名和键构成的行列式把行列式中那些为零的项去掉，并以键Ki为队首，以包含键Ki的记录为队列元素来构成一个记录队列。对于一个有m个键的队列来说，这样的队列有m个。这m个队列构成了该文件的多重结构(multi_list)。图7.4文件的多重结构(3)转置结构把所有与同一键对应的记录的指针连续地置于目录中该键的位置下。转置结构最适合于给定键后的记录搜索。(4)顺序结构把文件中的键按规定的顺序排列起来就形成了顺序结构文件。7.2.2存取方法用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。常用的存取方法有三种：(1)顺序存取法(2)随机存取法(直接存取法)(3)按键存取法对文件的搜索包括两种：键的搜索和记录的搜索。图7.6记录Ri的搜索过程几种搜索算法(1)线性搜索法(linearsearch)，(2)散列法(hashcoding)，(3)二分搜索法(binarysearchalgorithm)。(1)线性搜索法线性搜索法的搜索效率较低，在文件中记录个数较多时不宜采用。(2)散列法散列法的核心思想是定义一个散列函数h(k)，使得对于给定的键k，散列函数h(k)将其变换为k所对应的逻辑地址。在使用散列函数进行搜索时，有时会出现两个不同的输入值变换到同一地址的问题。这种问题称为散列冲突。解决散列冲突的方法是采用多次散列探索。(3)二分搜索法对于顺序结构排列的键或记录来说，二分搜索法具有较高的搜索效率。二分搜索法的好处是搜索效率高。与线性搜索法相比，当n(表长)=16时,它比线性搜索法约快二倍;当n=1024时，其平均搜索速度要快50倍。不过，二分搜索法需要事先把搜索对象按一定顺序排列。图7.7二分搜索法的搜索过程7.3文件的物理结构与存储设备7.3.1文件的物理结构(1)连续文件连续文件是一种最简单的物理文件结构，它把一个在逻辑上连续的文件信息依次存放到物理块中。连续文件结构的优点是存取速度快。缺点：不能动态增长。会留下无法使用的零头空间。不宜用来存放经常被修改的文件。图7.8连续文件结构(2)串联文件采用非连续的物理块来存放文件信息。使得存放同一文件的物理块链接成一个串联队列。图7.9给出了串联文件的物理结构。文件长度可以动态地增长，只要调整连接指针就可在任何一个信息块之间插入或删除一个信息块。串联文件结构的搜索效率较低。串连文件结构一般只适用于逻辑上连续的文件，且存取方法应该是顺序存取的图7.9串联文件的物理结构(3)索引文件为每个文件建立一张索引表，表中每一栏目指出文件信息所在的逻辑块号和与之对应的物理块号。索引表的物理地址则由文件说明信息项给出。索引结构如图7.10所示。索引文件结构既可以满足文件动态增长的要求，又可以较为方便和迅速地实现随机存取。索引结构的缺点是由于使用了索引表而增加了存储空间的开销。另外，在存取文件时需要至少访问存储器二次以上。一种改进的方法是，当对某个文件进行操作之前，系统预先把索引表放入内存。图7.10索引文件示意图图7.11多重索引结构7.3.2文件存储设备以磁带为代表的顺序存储设备以磁盘为代表的直接存储设备1.顺序存取设备-磁带图7.12磁带的结构磁带设备的存取速度或数据传输率与下列因素有关：(1)信息密度(字符数/英寸)(2)磁带带速(英寸/秒)(3)块间间隙如果带速高，信息密度大，且所需块间隙(磁头启动和停止时间)小的话，则磁带存取速度和数据传输率高，反之亦然。2.直接存取设备-磁盘磁盘上每个物理块的位置可用柱面号、磁头号和扇区号表示，这些地址和物理块号一一对应。磁盘的结构如图7.13所示。图7.13磁盘的结构7.4文件存储空间管理3种不同的空闲块管理方法。它们是：(1)空闲文件目录 (2)空闲块链 (3)位示图(1)空闲文件目录最简单的空闲块管理方法就是把文件存储设备中的空闲块的块号统一放在一个称为空闲文件目录的物理块中。其中空闲文件目录的每个表项对应一个由多个空闲块构成的空闲区，它包括空闲块个数，空闲块号和第一个空闲块号等。空闲文件项方法适用于连续文件结构的文件存储区的分配与回收(2)空闲块链空闲块链是一种较常用的空闲块管理方法。空闲块链把文件存储设备上的所有空闲块链接在一起，当申请者需要空闲块时，分配程序从链头开始摘取所需要的空闲块，然后调整链首指针。反之，当回收空闲块时，把释放的空闲块逐个插入链尾上。常用的链接方法按空闲区大小顺序链接的方法按释放先后顺序链接的方法按成组链接法(3)位示图7.5文件目录管理把文件名和对该文件实施控制管理的控制管理信息称为该文件的文件说明，并把一个文件说明按一定的逻辑结构存放到物理存储块的一个表目中把一个文件的文件说明信息称为该文件的目录。对文件目录的管理就是对文件说明信息的管理。7.5.1文件的组成从文件管理角度看，一个文件包括两部分：文件说明和文件体。文件体指文件本身的信息，它可能是前面各节讨论的记录式文件或字符流式文件。文件说明有时也叫文件控制块(FCB)，它至少包括文件名、与(物理结构是连续结构时)文件名相对应的文件内部标识以及文件信息在文件存储设备上第一个物理块的地址（物理结构是边连续结构时）。另外，根据系统要求不同，它还包括关于文件逻辑结构、物理结构、存取控制和管理信息等。这里的管理信息主要指访问时间、以及记账信息等。文件说明组成目录文件。文件系统利用目录文件完成按名存取和对文件信息的共享与保护。7.5.2文件目录文件目录可分为单级目录、二级目录和多级目录。单级目录是一种最简单、最原始的目录结构。文件系统为存储设备的所有文件建立一张目录表，每个文件在其中占有一项用来存放文件说明信息。单级目录时的文件系统读写处理过程如图7.15。命名冲突问题和目录表的搜索速度图7.15单级目录的读写处理过程二级目录结构图7.16二级目录结构另外，与单级目录相比，如果单级目录表的长度为n的话，则单级目录时的搜索时间与n成正比;在二级目录时，由于ｎ的目录已被画分为ｍ个子集，则二级目录的搜索时间是与ｍ＋ｒ成正比的。这里的ｍ是用户个数，ｒ是每个用户的文件的个数。一般有ｍ＋ｒ≤ｎ，从而二级目录的搜索时间要快于单级目录。多级目录图7.17文件系统的树形结构树形结构多级目录结构具有下列特点：(1)层次清楚。(2)解决了文件重名问题。(3)查找搜索速度快。7.5.3便于共享的文件目录从系统管理的观点看，有三种方法可以实现文件共享。即：(1)绕道法(2)链接法(3)基本文件目录表BFD绕道法:用户从当前目录出发向上返回到与所要共享文件所在路径的交叉点，再顺序下访到共享文件。绕道法需要用户指定所要共享文件的逻辑位置或到达被共享文件的路径。绕道法的原理如图7.18所示。绕道法要绕弯路访问多级目录，搜索效率不高链接法：即将一个目录中的链指针直接指向被共享文件所在的目录。链接法仍然需要用户指定被共享的文件和被链接的目录。图7.18绕道法实现文件共享的一种有效方法是采用基本文件目录表BFD的方法。该方法把所有文件目录的内容分成两部分：一部分包括文件的结构信息、物理块号、存取控制和管理信息等，并由系统赋予唯一的内部标识符来标识；另一部分则由用户给出的符号名和系统赋给文件说明信息的内部标识符组成。这两部分分别称为符号文件目录表(SFD)和基本文件目录表(BFD)。SFD中存放文件名和文件内部标识符，BFD中存放除了文件名之外的文件说明信息和文件的内部标识符。这样组成的多级目录结构如图7.19。图7.19采用基本文件目录的多级目录结构7.5.4目录管理7.6文件存取控制文件的共享是指不同的用户共同使用一个文件。文件保护则指文件本身需要防止文件的拥有者本人或其他用户破坏文件内容。文件保密指未经文件拥有者许可，任何用户不得访问该文件。这三个问题实际上是一个用户对文件的使用权限，即读、写、执行的许可权问题。具体地说，文件系统的存取控制部分应做到：(1)对于拥有读、写或执行权限的用户，应让其对文件进行相应的操作。(2)对于没有读、写或执行权限的用户，应禁止他们对文件进行相应的操作。(3)应防止一个用户冒充其他用户对文件进行存取。(4)应防止拥有存取权限的用户误用文件。这些功能是由一组称为存取控制验证模块的程序提供的。它们分三步验证用户的存取操作。(1)审定用户的存取权限。(2)比较用户权限的本次存取要求是否一致。(3)将存取要求和被访问文件的保密性比较，看是否有冲突。可有下述４个方式来验证用户的存取操作,它们是：(1)存取控制矩阵; (2)存取控制表;(3)口令; (4)密码术。(1)存取控制矩阵存取控制矩阵方式以一个二维矩阵来进行存取控制。二维矩阵的一维是所有的用户，另一维是所有的文件。对应的矩阵元素则是用户对文件的存取控制权，包括读Ｒ，写Ｗ，和执行Ｅ。如图7.20所示。在占用内存空间的大小上和对矩阵进行扫描的时间开销上都是不合适的。图7.20存取控制矩阵(2)存取控制表存取控制表以文件为单位，把用户按某种关系画分为若干组，同时规定每组的存取权限。这样，所有用户组对文件权限的集合就形成了该文件的存取控制表，如图7.21所示。图7.21存取控制表每个文件都有一张存取控制表。在实现时，该表存放在文件说明中，也就是