第8章文件系统

第8章文件系统8.1文件系统的概念8.2文件的逻辑结构与存取方法8.3文件的物理结构与存储设备8.4文件存储空间管理8.5文件目录管理8.6文件存取控制8.7文件的使用8.8文件系统的层次模型本章小结习题•对多数用户来说，文件系统是OS中最直接可见的部分。•文件系统是计算机组织、存取和保存信息的重要手段。•本章主要讨论文件的组织结构、存取结构、保护以及文件系统空间管理等问题。8.1文件系统的概念1.文件系统的引入OS对计算机的管理包括两个方面：1)硬件资源的管理包括CPU的管理、存储器的管理、设备管理等;主要解决硬件资源的有效和合理利用问题。2)软件资源的管理包括:•对各种系统程序（包括OS本身的程序）的管理•系统应用程序或工具的管理•库函数及各种用户程序和数据的管理。图8.1操作系统的软硬件管理•用户使用计算机来完成自己的某任务时：(1)使用现有的软件资源来协助完成自己的任务。(2)编制完成的或未完成的程序存放在什么地方,需要访问的数据存放在什么地方，使得人们可以再利用已有的软件资源。•这两个问题是一个怎样对软件资源（程序和数据）进行透明存取问题。1)在早期的计算机系统中：•用卡片或纸带来存放程序或数据。•卡片和纸带都分别编号存放，当用户需要使用它们时，再把这些卡片和纸带放在读卡机上输入计算机。•不能做到透明存取。2)大容量直接存取的磁盘存储器以及顺序存取的磁带存储器等的出现。•为程序和数据等软件资源的透明存取提供了物质基础。•这导致了对软件资源管理质的飞跃—文件系统的出现。•文件系统把相应的程序和数据看作文件，并把它们存放在磁盘或磁带等大容量存储介质上，从而做到对程序和数据的透明存取。•透明存取:不必了解文件存放的物理结构和查找方法等与存取介质有关的部分，只需给定一个代表某段程序或数据的文件名，文件系统就会自动地完成对与给定文件名相对应文件的有关操作。文件系统必须完成下列工作：(1)为了合理的存放文件，必需对磁盘等辅助存储器空间(文件空间)进行统一管理。•在用户创建新文件时为其分配空闲区;•用户删除或修改某个文件时,回收和调整存储区。(2)为了实现按名存取，需要有一个用户可见的文件逻辑结构，用户按照文件逻辑结构所给定的方式进行信息的存取和加工。这种逻辑结构是独立于物理存储设备的。(3)为了便于存放和加工信息，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。(4)完成对存放在存储设备上的文件信息的查找。(5)完成文件的共享和提供保护功能。2.文件与文件系统的概念(1)文件•文件是一段程序或数据的集合。•在计算机系统中，文件被解释为一组赋名的相关联字符流的集合，或者是相关联记录(一个有意义的信息单位)的集合。•文件的两种解释定义了两种文件形式。1.赋名的字符流文件:无结构文件或流式文件。•UNIX，MS-DOS等均采用无结构文件形式。•无结构文件采用字符流方式，与源程序、目标代码等在形式上是一致的;•该方式适用于源程序、目标代码等文件。2.记录式文件•由相关联记录组成的文件;•基本信息单位是记录。•记录是由N(N1)个字节组成的具有特定意义的信息单位。•主要用于信息管理。•在有些OS中，从字符流文件的角度出发，设备也被看作是赋予特殊文件名的文件。系统可以对设备和文件实施统一管理，简化设备管理程序和文件系统的接口设计。•用户文件名由用户给定;•它是一个字母数字串，有些系统规定必须是英文字母打头且允许一些其他的符号出现在文件名的非打头部分。例如a.out，ccdos.exe。(2)文件系统•OS中与管理文件有关的软件和数据称为文件系统。•它负责为用户建立文件，撤消、读写、修改和复制文件，还负责完成对文件的按名存取和进行存取控制。•文件系统具有以下特点：①友好的用户接口;用户只对文件进行操作，而不管文件结构和存放的物理位置。②对文件按名存取，对用户透明。③某些文件可以被多个用户或进程所共享。④文件系统大都使用磁盘、磁带和光盘等大容量存储器作为存储介质，因此，可存储大量信息。3.文件的分类•按文件的性质和用途分为：•(1)系统文件•(2)库文件•(3)用户文件(1)系统文件•只允许用户通过系统调用来执行它们，而不允许对其进行读写和修改。•这些文件主要由OS核心和各种系统应用程序和数据所组成。(2)库文件•允许用户对其进行读取、执行，但不允许对其进行修改。•库文件主要由各种标准子程序库组成。如C语言子程序库、FORTRAN子程序库等。(3)用户文件•用户委托文件系统保存的文件。•只由文件的所有者或所有者授权的用户才能使用。•用户文件主要由源程序、目标程序、用户数据库等组成。3.文件的分类•按组织形式分为：•(1)普通文件•(2)目录文件•(3)特殊文件(1)普通文件•组织格式为系统中所规定的最一般格式的文件，例如由字符流组成的文件。•包括系统文件，用户文件和库函数文件、实用程序文件。(2)目录文件•由文件的目录信息构成的特殊文件。文件的内容不是各种程序或应用数据，而是用来检索普通文件的目录信息。(3)特殊文件•在UNIX系统中，所有的输入、输出设备都被看作特殊文件。•这组特殊文件在使用形式上与普通文件相同，如查找目录、存取操作等。•按信息流向可把文件分为:输入文件、输出文件输入/输出文件•按文件的保护级别可分为:只读文件读写文件可执行文件不保护文件•文件的分类主要是便于系统对不同的文件进行不同的管理，从而提高处理速度和起到保护与共享的作用。•例如，一个系统文件在读入内存时将被放在内存的某一固定区且享受高的保护级别，从而不必像一般的用户文件那样只有在内存用户可用区分得相应的空闲区之后才能被调入内存。8.2文件的逻辑结构与存取方法8.2.1逻辑结构•文件的逻辑结构是用户可见结构。•文件的逻辑结构可分为两大类：1.字符流式的无结构文件2.记录式的有结构文件。选取文件的逻辑结构应遵循的原则：(1)当用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少对已存储好的文件信息的变动。(2)当用户需要对文件信息进行操作时，给定的逻辑结构应使文件系统在尽可能短的时间内查找到需要查找的记录或基本信息单位。(3)应使文件信息占据最小的存储空间。(4)应是便于用户进行操作的。1.字符流的无结构文件：•查找文件中的基本信息单位(如某个单词)比较困难。•管理简单，用户可以方便地对其进行操作。•适于对基本信息单位操作不多的文件，例如，源程序文件、目标代码文件等。2.记录式的有结构文件：•把文件中的记录按各种不同的方式排列，构成不同的逻辑结构。•记录是一个具有特定意义的信息单位；•记录的组成:该记录在文件中的逻辑地址(相对位置)记录名所对应的一组键属性属性值。图8.2记录组成例•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在记录Rj中;反之,则表示键Ki不在记录Rj中。•同一个键也可以同时属于不同记录。•把行列式中为0的项去掉，并以键Ki为队首，以包含键Ki的记录为队列元素来构成一个记录队列。•行列式中有m个键，有m个这样的队列。•这m个队列构成了该文件的多重结构。图8.4文件的多重结构图8.5文件的转置结构(3)转置结构多重结构中：•每个队列中和键直接相连的记录只有一个。•在探索某一特定记录时：先找到该记录所对应的键之后；再在该键所对应的队列中顺序查找。•转置结构：把含有相同键的记录指针全部指向该键，即把所有与同一键对应的记录的指针连续地置于目录中该键的位置下。•转置结构最适合于给定键后的记录搜索。(4)顺序结构•如果系统要求按某种优先顺序来搜索或追加、删除记录，则最好采用顺序结构。•如果给定了顺序规定(例如按字母顺序)，则把文件中的键按规定的顺序排列起来就形成了顺序结构文件。例如：•把人民日报上登载的新闻按年月日为键做成记录放入文件中，并以时间先后顺序组成文件。•如果要处理某段时间内所发生的大事等问题，就会变得非常简单。8.2.2存取方法•用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。•常用的存取方法有三种：(1)顺序存取法(2)随机存取法(直接存取法)(3)按键存取法(1)顺序存取:按照文件的逻辑地址顺序存取。A.记录式文件：按记录的排列顺序来存取。若当前读取的记录为Ri，则下一次读取的记录被自动地确定为Ri的下一个相邻的记录Ri+1。B.无结构的字符流文件：按当前读写指针的变化来存取。在存取完一段信息之后，读写指针自动加或减去该段信息长度，以便指出下次存取时的位置。（2）随机存取法•允许用户根据记录的编号来存取文件的任一记录；•或者是根据存取命令移动读写指针到欲读写处来读写。•UNIX、MS-DOS等系统都采用顺序存取和随机存取等两种方法。（3）按键存取：用在复杂文件系统，特别是数据库管理系统中。•文件的存取根据给定的键或记录名进行.1)先搜索到要进行存取的记录的逻辑位置;2)将其转换到相应的物理地址后进行存取。•对文件进行搜索的目的：查找出特定记录所对应的逻辑地址。对文件的搜索包括两种：•键的搜索用户给定所要搜索的键名和记录之后，确定该键名在文件中的位置；•记录的搜索：在搜索到所要查找的键之后，在含有该键的所有记录中查找出所需要的记录。•对不同的逻辑结构的文件，其搜索方法和搜索效率不一样。•对指定记录Ri的搜索过程（如图8.6所示）。图8.6记录Ri的搜索过程•对键或记录的搜索都属于表格搜索问题。•搜索算法可以大致分为三种类型。(1)线性搜索法(linearsearch)(2)散列法(hashcoding)(3)二分搜索法(binarysearchalgorithm)。(1)线性搜索法•从第一个键或记录开始，依次和所要搜索的键或记录相比较，直到找到所需要的记录为止。•所需要的搜索时间与所搜索的表格大小的1/2成正比。•搜索效率较低，在文件中记录个数较多时不宜采用。(2)散列法•被广泛用于现代OS的数据查找。•核心思想：定义一个散列函数h(k)，使得对于给定的键k，散列函数h(k)将其变换为k所对应的逻辑地址。•散列冲突：•解决散列冲突的方法:①②③散列冲突：在使用散列函数进行搜索时，有时会出现两个不同的输入值变换到同一地址的问题。即对于k1!=k2，有h(k1)=h(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。•使用随机数的方法需要占用一定的存储空间来生成和存放随机数组。③还有一个解决散列冲突的方法是采用平方散列函数方法。hi(k)=(h1(k)+c*(i*i))(modt)•t是一个表示被搜索表格长度的素数，•c是