计算机操作系统原理 ch7 文件系统

第七章文件系统文件和文件系统文件结构及其存取方式文件存储空间管理文件目录管理文件存取控制文件的使用文件系统的层次模型小结文件和文件系统引言文件及其分类文件系统及其功能引言在早期计算机系统中，人们直接用物理地址存放信息。存放信息时，要求用户指出并记住信息存放在哪个设备的哪些磁道、哪些扇区上。在多用户的环境中这几乎是不可能的，更是不能忍受的。实际上对用户来说，关心的不是信息的具体存放位置，而是存取方法的方便、可靠。不是信息的物理结构而是信息的逻辑结构。因此，引入文件和文件系统的概念，它是操作系统的重要组成部分。文件及其分类1、文件的定义文件是具有符号名而且在逻辑上具有完整意义的信息项的有序序列。信息项信息项……...信息项……...信息项编号：01……i……n-1读写指针在现代计算机操作系统中，为方便用户，把设备也作为文件来统一管理，从某种意义上说已拓宽了文件的含义。一般情况下，一个文件是一组逻辑上具有完整意义的信息集合，并赋以一个文件名。文件名是一个字符串。2、文件的分类（1）以文件的用途分类系统文件:指用操作系统的执行程序和数据组成的文件，这种文件不对用户开放，仅供系统使用。库文件：是指系统为用户提供的各种标准函数，标准过程和实用程序等。用户只能使用这些文件，而无权对其进行修改。用户文件:由用户的信息组成的文件，如源程序文件，数据文件等。这种文件的使用和修改权均属于用户。（2）从按文件的属性分类只读文件:只允许进行读操作。可读/写文件:允许进行读写操作。非保护文件:不作任何操作限制。可执行文件：用户可执行该程序，但不能修改。（3）按文件的性质分类普通文件:指一般的用户文件和系统文件。目录文件:指由文件目录项组成的文件。特别文件:有的系统把设备作为文件统一管理和使用，并为区别起见，把设备称为特别文件。UNIX操作系统把文件分成普通文件、目录文件和特别文件。3、文件属性用一组信息指定文件的类型、操作特性和存取保护等，把这组信息称为文件的属性。文件的属性一般存放在文件的目录项中。例如MS-DOS系统中，文件属性占目录项的一个字节，在这个字节中，01表示文件仅读，02表示隐含文件等。文件系统及其功能操作系统中负责管理文件的机构称为文件系统。也有的文献上叫信息系统。文件系统负责文件的创立、撤消、读写、修改、复制和存取控制等，并管理存放文件的各种资源。文件系统主要功能(1)按名存取(2)文件存储空间的分配和回收(3)对文件及文件目录的管理(4)提供操作系统与用户的接口(5)提供有关文件自身的服务文件的安全性、文件的共享机制等。文件的结构及其存取方式概述文件的逻辑结构及其存取方式文件的物理结构及其存储设备概述研究文件结构有两种观点：用户的观点（文件的逻辑结构）：主要研究用户思维中的抽象文件，为用户提供一种逻辑结构清晰、使用简便的逻辑文件。用户将按这种形式去存取、检索和加工文件。例如用户可将文件看作字节的集合。或者用户将文件看作记录的集合。实现的观点（文件的物理结构）：主要研究驻留在存储介质上的文件的结构。文件的物理结构：文件的各个字节在存储介质上是如何摆放的。文件的逻辑结构及其存取方式1、文件的逻辑结构文件的逻辑结构是用户可见结构。文件的逻辑结构可分为两大类：字符流式的无结构文件和记录式的有结构文件。在文件系统设计时，选择何种逻辑结构才能更有利于用户对文件信息的操作呢？一般情况下，选取文件的逻辑结构应遵循下述原则：(1)当用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少对已存储好的文件信息的变动。(2)当用户需要对文件信息进行操作时，给定的逻辑结构应使文件系统在尽可能短的时间内查找到需要查找的记录或基本信息单位。(3)应使文件信息占据最小的存储空间。(4)应是便于用户进行操作的。显然，对于字符流的无结构文件来说，查找文件中的基本信息单位，例如某个单词，是比较困难的。但反过来，字符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，例如，源程序文件、目标代码文件等。除了字符流的无结构方式外，记录式的有结构文件可把文件中的记录按各种不同的方式排列，构成不同的逻辑结构，以便用户对文件中的记录进行修改、追加、查找和管理等操作。记录是一个具有特定意义的信息单位，它由该记录在文件中的逻辑地址(相对位置)与记录名所对应的一组键、属性及其属性值所组成。下图是一个记录的组成例。图中，1296是名为R的记录在文件中的逻辑地址，‘姓名:A’是该记录的键，而‘性别’，‘出生年月’，‘工资’等是该记录的属性，紧跟在这些后面的是属性值。一个记录可以有多个键名，每个键名可对应于多项属性。再者，根据各系统设计的要求不一样，记录既可以是定长的，也可以是变长的。记录的长度可以短到一个字符，也可以长到一个文件，这要由系统设计人员确定。常用的记录式结构文件有以下几种:(1)连续结构(2)多重结构(3)转置结构(4)顺序结构(1)连续结构连续结构是一种把记录按生成的先后顺序连续排列的逻辑结构。优点：适用性强，可用于所有文件，且记录的排列顺序与记录的内容无关。这有利于记录的追加与变更。缺点：搜索性能较差，例如要找出某个指定键的记录时，系统必须对文件全体进行搜索。(2)多重结构如果把记录按键和记录名排列成行列式结构，则一个包含n个记录名、m个(m≤n)个键的文件构成一m*n维行列式。其中，如果第i(1≤i≤m)行和第j(1≤j≤n)列所对应的位置上为1，则表示键Ki在记录R中;反之,则表示键Ki不在记录Rj中。另外，同一个键也可以同时属于不同记录。文件的记录名和键构成的行列式显然，如果只按行列式结构来排列记录，将会浪费较多的存储空间。从而，我们把行列式中那些为零的项去掉，并以键Ki为队首，以包含键Ki的记录为队列元素来构成一个记录队列。对于一个有m个键的队列来说，这样的队列有m个。这m个队列构成了该文件的多重结构(multi_list)。如图a所示。(3)转置结构在图a的多重结构中，每个队列中和键直接相连的只有一个记录。这种结构虽然在检索时要优于连续结构，但在检索某一特定记录时，必须在找到该记录所对应的键之后，再在该键所对应的队列中顺序查找。转置结构把含有相同键的记录指针全部指向该键，也就是说，把所有与同一键对应的记录的指针连续地置于目录中该键的位置下(图b)。转置结构最适合于给定键后的记录搜索。图a文件的多重结构图b文件的转置结构(4)顺序结构如果系统要求按某种优先顺序来搜索或追加、删除记录，则最好采用顺序结构。如果给定了顺序规定(例如按字母顺序)，则把文件中的键按规定的顺序排列起来就形成了顺序结构文件。例如，把人民日报上登载的新闻按年月日为键做成记录放入文件中，并以时间先后顺序组成文件。这样，如果要处理某段时间内所发生的大事等问题，就会变得非常简单。例如用户想了解两伊战争的情况，则只要把1990年8月19日开始的两个月内的有关记录搜索到就行了。存取方法用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。常用的存取方法有三种：(1)顺序存取法(2)随机存取法(直接存取法)(3)按键存取法顺序存取是按照文件的逻辑地址顺序存取。在记录式文件中，这反映为按记录的排列顺序来存取，例如，若当前读取的记录为Ri，则下一次读取的记录被自动地确定为Ri的下一个相邻的记录Ri+1。在无结构的字符流文件中，顺序存取反映当前读写指针的变化。在存取完一段信息之后，读写指针自动加或减去该段信息长度，以便指出下次存取时的位置。随机存取法允许用户根据记录的编号来存取文件的任一记录，或者是根据存取命令把读写指针移到欲读写处来读写。UNIX系统以及MS-DOS等操作系统都采用顺序存取和随机存取等两种方法。按键存取是一种用在复杂文件系统，特别是数据库管理系统中的存取方法。文件的存取是根据给定的键或记录名进行的。按键存取法首先搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理地址后进行存取。下面，介绍按键存取的搜索方法。对文件进行搜索的目的是要查找出特定记录所对应的逻辑地址，以便将其转换为相应的物理地址，实现对文件的操作。对文件的搜索包括两种：键的搜索和记录的搜索。对键的搜索是在用户给定所要搜索的键名和记录之后，确定该键名在文件中的位置；而记录的搜索则是在搜索到所要查找的键之后，在含有该键的所有记录中查找出所需要的记录。显然，对于不同的逻辑结构的文件，其搜索方法和搜索效率都是不一样的。对指定记录Ri的搜索过程如图所示。对于给定的Ri,首先,系统确定Ri所对应键名的记录队列。如果在所查找的文件中不存在这样的队列，则搜索算法结束返回，从而无法搜索到Ri。如果找到Ri，则返回其所对应的逻辑地址。如果找不到Ri，则返回无法找到Ri的有关信息。对键或记录的搜索与其他数据搜索问题一样，都属于表格搜索问题。有许多搜索算法用来解决表格搜索问题。这些算法可以大致分为三种类型。即，(1)线性搜索法(linearsearch)，(2)散列法(hashcoding)，(3)二分搜索法(binarysearchalgorithm)。下面分别简单地介绍这几种搜索算法。(1)线性搜索法它从第一个键或记录开始，依次和所要搜索的键或记录相比较，直到找到所需要的记录为止。线性搜索法所需要的搜索时间与所搜索的表格大小的1/2成正比。这是因为找到一个所需要的记录平均要和表中登记的总项数的1/2项比较后才能得到。线性搜索法的搜索效率较低，在文件中记录个数较多时不宜采用。(2)散列法散列搜索法被被广泛用于现代操作系统的数据查找。散列法的核心思想是定义一个散列函数h(k)，使得对于给定的键k，散列函数h(k)将其变换为k所对应的逻辑地址。在使用散列函数进行搜索时，有时会出现两个不同的输入值变换到同一地址的问题。即对于k1!=k2，有h(k1)=h(k2)=A。显然，k1和k2中，至少有一个与A中的内容不一致。也就是说，由散列变换得到的结果并不是所要搜索的键。这种问题称为散列冲突。解决散列冲突的方法是采用多次散列探索。例如，设第i次散列变换的结果为hi(k)，i=2,3…，则可令hi(k)=(h1(k)+di)(modt)这里，t为被搜索表格长度，di为第i次搜索所得地址与第1次搜索所得地址之间的距离。di的取值方法很多，最简单的方法是设di为i的线性函数，即di=a*i(a为一大于零的常数)。这种方法称线性散列法。但是，使用线性散列法并不能完全解决散列冲突问题。例如，对于i!=j，k=1,2…，如果hi(k1)=hj(k2)，则存在hi+k(k1)=hj+k(k2)解决散列冲突的另一个方法是生成一组随机数{r1,r2，…，rn}，且令di=ri。显然，除了h1(k1)=h1(k2)可能存在之外，h1(k1)=h1+k(k2)的可能性很小，不过，使用随机数的方法需要占用一定的存储空间来生成和存放随机数组。还有一个解决散列冲突的方法是采用平方散列函数方法。即令：hi(k)=(h1(k)+c*(i*i))(modt)这里，t是一个表示被搜索表格长度的素数，c是一个大于零的常数。可以证明，对于j1(modt)，即使有h1(k1)=hj(k2)，那么，对于i=1,2，…，t-1，有hi(k1)!=hj+i(k2)。(3)二分搜索法对于顺序结构排列的键或记录来说，二分搜索法具有较高的搜索效率。二分搜索法首先把所要搜的键与队列的首尾键相比较,如果和其中之一相等，则返回所搜索到的键的逻辑位置。否则，再与队列1/2处的键比较，如果所要搜索的键正好等于该键的话,则返回该键的逻辑地址；否则，如果所要搜索的键K小于位于队列中央的键的话，则继续搜索左边的半个队列。如果所要搜索的键K大于位于队列中央的键的话,则继续搜索右边的半个队列。这样，每次用以中央键画分的部分组成新的队列反复进行上述搜索操作，直到找到为止。这一搜索过程如图所示。二分搜索法的搜索过程二分搜索法的好处是搜索效率高。与线性搜索法相比，当n(表长