昆明理工大学付湘琼《操作系统》第六章文件系统

1、1,第六章 文件系统,2,文件系统是对软件资源的管理。 文件系统是计算机组织、存取和保护信息的重要手段。 计算机的重要作用之一是快速处理大量信息。从而，信息的组织、存取和保管就成为一个极为重要的内容 本章讨论的问题：文件的组织结构、存取结构、文件的保护、文件系统空间。,第六章 文件系统,3,6.1 文件系统的概念,6.2 文件的逻辑结构与存取方法,6.3 文件的物理结构与存储设备,6.4 文件存储空间管理,6.5 文件目录管理,6.6 文件存取控制,6.7 文件的使用,6.8 文件系统的层次模型,4,6.1 文件系统的概念1文件系统的引入,早期的计算机系统，由于没有功能足够强的文件管理系统对外

2、部存储器中文件进行管理，所以对文件的使用相当复杂和繁琐。 特别是对于用户文件的组织和管理常常要用户亲自干预，比如要按照设备的物理地址安排的位置，组织相应的输入/输出指令，还应掌握存储空间上信息的分布等等，稍不注意就破坏原来已存入介质的文件信息。,5,尤其是在多道程序引入后,多个用户共享大容量的文件存储器。让用户自己协调管外存上的信息，难以办到，也不允许。 现在，OS都引入了文件系统。协助用户存取和管理他的信息，使得用户“按其文件名”存取信息十分方便。 目前各类计算机系统都十分重视文件管理的功能，即使在小型机甚至个人计算机中 ，OS的其它功能往往不见得很强，但相对来说都具有较强的文件管理功能。,

3、6,文件系统的功能： 1）实现从逻辑文件到物理文件的转换。 2）有效地分配和管理文件存储空间。 3）建立文件目录。 4）提供合适的存取方法，适应各种不 同的应用。 5）给用户提供一组文件操作。,7,文件的逻辑结构-呈现在用户面前的文件结构。 逻辑结构分为两种：一种是记录式文件，另一种为流式文件。 记录-每个逻辑文件按其信息的独立的逻辑意义可划分成若干个逻辑记录，简称记录。,6. 2 文件的逻辑结构与存取方法6.2.1 逻辑结构,8,记录是用户存取信息的基本单位，每个记录可以从0开始顺序编号，称之为逻辑记录号。 一个记录式文件由若干逻辑记录组成，每个逻辑记录的长度可以相等也可以不相等，因此在记录

4、式的文件里又可以由等长记录和变长记录组成。如学生登记表、职工登记表等就是记录式文件。,9,有序文件的相关数据集合，文件的长度以字节来计算.如源程序文件、中间代码文件、编辑程序等。 选取文件的逻辑结构遵循下述原则：,什么是流式文件？,10,用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少对已存储好的文件信息的变动。 当用户需要对文件信息进行操作时，给定的逻辑结构应使文件在尽可能短的时间内查找的记录或基本信息单位。 文件信息占据最小的存储空间。 是便于用户进行操作的。,11,常用的记录式结构文件：连续结构、多重结构、转置结构、顺序结构。 a.连续结构 把记录按生成的先后顺序连续排列的逻辑结

5、构。 特点:是适应性强。可用于所有文件。记录的排列顺序与记录的内容无关，利于记录的追加与变更。 缺点：搜索性能差，若要找出某个指定键的记录时，系统必须对文件全体进行搜索。,12,b.多重结构 一个包含n 个记录名、m 个键的文件构成一个m*n 维行列式。其中如果第I行和第j列所对应的位置上为1，则表示键ki 在记录R 中；反之，则表示键Ki不在记录Rj中。另外，同一个键也可以同时属于不同的记录。 c.转置结构 转置结构把含有相同键的记录全部指向该键。 d.顺序结构 给定顺序规则，把文件中的键按规定的顺序排列起来形成的文件。,13,6.2.2 文件的存取方法,所谓文件的存取方法是指读写文件存储器

6、上的一个物理块的方法，通常有三种存取方法 1）顺序存取方法 在记录式结构的系统中，顺序存取法就是严格的按照物理记录排列的顺序依次存取，如果当前存取的记录为Ri，则下次要存取的记录动的确定为Ri+1，可以认为，在文件存取过程中,总有一个位置指针指向欲要读取的记录。,14,对于定长记录结构，当前读写指针指出下一次要读写记录的首地址: rptr:=rptr+m rptr: 当前的读指针，m：记录长度 wptr:=wptr+m wptr:当前的写指针 顺序文件的存取，可采用预缓冲技术来加速文件的输入输出（生产者与消费者）。,15,2）直接存取方法 直接存取方法就是随机存取方法，允许用户随意存取文件中的

7、任何一个记录和上一次读写位置无关。 在直接存取文件访问时，用户除了给出文件名外，还应给出要读出的记录号。,16,定长：记录号I，长度m LAi*m 故读写第I个记录的首址为： rptr=addro+i*m wptr=addro+I*m (addro是I记录所在的物理地址，m为记录的长度),17,为了加快直接存取的速度,通常采用索引表。索引是按记录号的顺序排列的,索引表的内容包括记录长度和记录的物理地址,按这种结构查找,首先以记录号为索引,读出相应表目，找到了该记录的物理首地址后,就可以读写某个记录了。,18,3）索引顺序存取方法 前面的是用文件的记录在文件中的位置来编址，下面介绍的是按逻辑记录

8、中的某个数据项的值来编址，按键存取是一种用在复杂文件系统特别是数据管理系统中的存取方法。文件的存取是根据给定的键或记录名进行的。 按键存取法，首先搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理地址后进行存取。 对键或记录的搜索与其它数据搜索问题一样， 都属于表格搜索问题，为了避免大量的查找，采用 索引表来指示键与记录的逻辑地址之间的对应关系。,19,文件的物理结构是指逻辑文件在外存储器上的存储结构。 在文件系统中，文件的存储设备通常划分为若干个大小相等的物理块，每块长为512或1024字节。在记录式文件中，允许一块中存放一个或几个记录，也可以一个记录占几块。与逻辑文件相对应，常把外存

9、储器上的文件称为物理文件，把物理块称为物理文件，把物理块中的信息称为物理记录，它是内外存交换的基本单位。,6.3 文件的物理结构与存储设备6.3.1 文件的物理结构,20,常用的文件物理结构如下： 一连续区分配-连续文件 一个文件的连续信息依次存放在辅存的若干连续的物理块中，称连续结构，即逻辑记录Ri+1一定紧按放在逻辑记录Ri之后。 连续分配的文件。 二 .链接块方式-串联文件 这种结构将文件的逻辑记录顺序与磁盘上的存储空间顺序分开，为了提高辅存空间的利用率，将逻辑记录分配到不连续的物理块中去.,21,三.索引式-索引文件 索引结构是实现不连续分配的另一种方法. 索引结构为每个文件建立一张索

10、引表，每一表目指出文件每个记录的所存放的物理地址 优点：具备串联结构所有的优点，适合与随机存放. 缺点：增加了索引的开销，存取文件时首先要取得索引表，这样就要增加一次访盘操作，降低了文件访问的速度.,22,22,18,30,图 索引文件示意图,件文说明信息,索引表,23,四.HASH文件 HASh法是一种杂凑法，亦称散列法。 它是一种构造和查找符号表的常用技术，其基本思想是利用一个简单宜于实现的变换函数（HASH函数），把每个符号名唯一的变换成表中的表目位置.即：a=H(k) 其中，H为HASH函数，k为关键字（符号名），a为k在符号表中相应的表目位置，a又称HASH值，对于任一符号名，通过H

11、ASH变换直接得到a,比线性查找法大大加快了平均检索速度.,24,下面介绍一种简单的Hash方法： 把文件符号名中个字符进行ASCII代码“异或”，得到的HASH值a就是该文件在目录中的表目位置. H(k)=k1+k2+k3+.+km (这里的表示异或)其中,ki(I=1,2,3.m)为符号，例如文件名为ANDING,则 H(ANDING)=A+N+D+I+N+G=(1011)2=(11)10 即文件ANDING在目录中的表目位置为11。,25,6.3.2 文件存储设备,1顺序存取存储设备是严格依赖信息的物理位置进行定位和读写的存储设备，所以，从存取一个信息块到存取另一个信息块要花费较长的时间

12、。磁带机是最常用的一种顺序存储设备，由于它具有存储容量大，稳定可靠，可装卸和便于保存等优点，已被广泛用作存档的文件存储介质。,26,.,间隙,数据块,间隙,间隙,数据块,磁带 磁带：数据是以块的形式存放的。每个块同下一个块之间用一个间隙分开（比如说0.6英寸）。这个间隙使得磁带机在读到数据之前能加速到正常的速度，并使当读完块数据停下来之后，不会到达下一块。 磁带块中的每一个物理块记录都有一个唯一标识符号物理记录号，为了确定刚读入主存的物理记录是否就是要招的记录，可以将它的物理记录号同要找的物理记录进行比较。,27,磁带设备的数据传输率主要取决于下列因素： 1.信息密度（字苻数/英寸） 2.磁带

13、带速（英寸/秒） 3.块间间隙的大小 磁带的容量取决于磁道密度，记录间隙和带长。 平均来说，从磁道文件中任意存取一条记录所需要的时间，是读取全部磁带文件所需时间的一半。,28,指标 低挡 中档 高档 磁带密度 （字节/英寸） 800 1600 6250 带速 （英寸/秒） 75 125 200 块间间隙 （英寸） 0.6 0.6 0.3 传输率 （字节/秒） 60 200 1250,29,无论是程序还是数据，所有信息都是以文件形式存放在外存上。所以，这些外部存储器也称为文件存储器。外存上文件存放的空间也叫作“文件存储空间”。,6.4 文件存储空间管理,30,文件存储空间是系统与多个用户共享的资

14、源，用户只要给出文件名就可以实现按名存取。系统将外存空间分成若干大小相等的物理块，以块为单位来交换信息。因此，需要对外存的物理块进行管理。 比如，建立空闲管理表，标出哪些块正在使用，以便建立文件时能迅速、合理、方便地找出空白存储块进行分配。将文件释放出来的存储块回收，归还给系统。,31,文件存储空间的管理，实际上就是一个空闲块的组织和管理问题。三种常用的管理方法：空闲文件目录，空闲块链，位示图 （1）空闲文件目录。 空闲文件-盘空间上一个连续的未分配区域。 系统为所有这些空白文件单独建立一个目录。对于每个空白文件，就在这个目录中建立一个表目。表目的内容包括：第一空白块地址（物理块号）、空白块个

15、数，如下表：,32,33,当某用户提出请求分配存储空间时，系统依次扫描该空白文件目录的各表目，直到找到一个满足要求的空白文件为止。 当用户删除一个文件时，系统收回其文件空间。这时也要扫描空白文件目录，找出一个空表将其释放空间的第一个物理块号及占用的块号数填入该表目中。,34,这种空白文件目录的方法，类似内存分区的管理，当请求的块号数正好等于目录表目中的空白块数时，就把这些块全部分配给该文件并把该项标记为空项。如果该项中的块数多余请求的块数，则把多余的块号留在表中，并修改该表中的各项。同样，在释放过程中，如果被释放的物理块号与某一目录项中的物理块号相邻，还要进行合并空白文件。 这种方法仅当有少量

16、空白文件时才有较好的效果。如果存储空间中有大量的小的空白文件，则使该目录变得很大，因而效率大为降低。其次这种管理技术仅适用于连续文件。,35,（2）空闲块链 空闲块链把文件存储设备上的所有空闲块连接在一起，这是非连续结构。 当需要分配空白块时从链首处进行，所以在主存中要保存一个链首指针，它指向第一个空白块，当释放空白块时，则把这些块挂在空白块链尾上。 常用的链接方法有3种：按空闲区大小顺序链接方法、按释放先后顺序链接的方法、按成组链接法。,36,成组链法：先把文件存储设备中的所有空闲块按50块划分为一组。组的划分为从后往前顺序划分，其中，每组的第一块用来存放前一组中各个块的块号和总快数。由于第

17、一组的前面已无其他组存在，因此，第一组的块数为49块。不过，由于存储设备的空闲块不一定正好是50的整倍数，因而最后一组将不足50块，且由于该组后面已无另外的空闲块组，所以该组的物理块号与总块数只能放在管理文件存储设备用的文件资源表中。,37,这些方法的主要优点使得不连续的空白块得以有效利用，但在修改链接字时，要读几个盘，工作量较大。,38,（3）位示图 位示图是外存空间的存储映射图。 位示图是系统在内存中划分出的若干字节的集合，用来指示磁盘存储情况。位示图中的每一位（bit）对应外存空间的一个物理块。若该位为“1”，表示对应块被占用；若该位为“0”，表示对应物理块空闲。 位示图的大小由其对应的

18、文件存储设备的容量决定，当一个盘组的分块确定后，根据划分的总块数决定位示图由多少字节组成。,39,例：设想一个磁盘组共有16个柱面，每个柱面有16个磁头寻道，每个磁道分为16个扇区，那么整个磁盘空间的扇区数为： 16*16*16=4096（个） 如果一个扇区被定义为一个存储块，那么，用字长位16位的存储单元来构造位示图，共需要256个字。,40,0位,1位,16位,4096位,41,实现文件的按名存取，是文件管理系统的任务之一。文件目录是文件系统实现按名存取的一个好方法，系统为每个文件编制一个目录表，内容包括：文件名、物理地址、存取控制信息。 6.5.1 文件的组成 一个文件包括两部分：文件说

19、明和文件体。 文件体：文件本身的信息。 文件说明包括文件名、第一个物理块的地址、存取控制和有关信息。,6.5 文件目录管理,42,6.5.2 文件目录,文件目录可分为单级目录、二级目录和多级目录。 1、单级目录 表格形式 缺点：不允许重名，不允许别名、当目录项过多时，查找速度慢。 单级目录的读写处理过程在P190 图8。15 2、二级目录 系统设置一个主目录后，再为每个用户设立一个用户目录，这样就构成二级目录管理。,43,采用二级目录管理解决文件名的冲突问题。由于访问时按其用户名和文件名，即使文件名相同，但由于用户名不同，所以也能准确地区别着两个不同的文件。 解决别名问题。若ASS和ADD是同

20、一个文件，但可以用不同的名字访问。在两个用户文件目录表中，只要将文件物理位置一栏指向同一个文件的物理首地址就行了。这样有利于对同一文件的共享。 当系统的文件数固定时，二级目录比一级目录查找速度快的多。,44,0,1,3,2,4,5 6 7 8 9,10 11 12 13 14,. . . . . . . . . . . .,文件目录表,单级目录管理,45,本节介绍文件的存取控制问题。文件的存取控制是和文件的共享. 保护和保密三个不同而又相互联系的问题紧密相关的。前面各节中我们简单地提及了文件的共享，但未涉及倒文件的保护和保密。,6.6 文件存取控制,46,文件的共享是指不同的用户共同使用一个文

21、件。 文件保护则指文件本身需要防止文件的拥有者本人或其他用户破坏文件内容。 文件保密指未经文件拥有者许可，任何用户不得访问该文件。 这三个问题实际上是一个用户对文件的使用权，即读，写，执行的许可权问题。,47,具体地说，文件系统的存取控制部分应做到： 1)对于拥有读，写或执行权限的用户，应让其对文件进行相应的操作。 2)对于没有读，写或执行权限的用户，应禁止他们对文件进行相应的操作。 3)应防止一个用户冒充其它用户对文件进行存取。 4)应防止拥有存取权限的用户误用文件。 这些功能是由一组称为存取控制验证模块的程序提供的。,48,它们分三步验用户的存取操作。 1)审定用户的存取权限。 2)比较用

22、户权限的本次存取要求是否一致。 3)将存取要求和被访问文件的保密性比较，看是否有冲突。,49,一般可有下述4个方式来验证用户的存取操作，它们 1)存取控制矩阵； 2)存取控制表； 3)口令； 4)密码术。,50,系统设计人员根据需要选择其中一种或几种并将相应的数据结构置于文件说明（BFD等）中，在用户访问存取文件时，对用户的存取权限，存取要求的一致性以及保密性等进行验证。下面我们简单地介绍这4种方式。,51,（i）存取控制矩阵 存取控制矩阵方式以一个二维矩阵来进行存取控制。二维矩阵的一维是所有的用户，令一维是所有的文件。对应的矩阵元素则是用户对文件的存取控制权，包括读R，写W，和执行E，如图8

23、.20所示。,52,当用户向文件系统提出存取要求时，由存取控制验证模块根据该矩阵内容读本次存取要求进行比较，如果不匹配的话，系统拒绝执行。 存取控制矩阵的方法虽然在概念上比较简单，但是，当文件和用户比较多时，存取控制矩阵将变得非常庞大，这无论是在占用内存空间的大小上，还是在使用文件而对矩阵进行扫描的时间开销上都是不适当的。因此，在实现时往往采取某些辅助措施以减少时间和空间的开销。,53,用户,存 取数,文件名,A . C,存取控制矩阵,54,存取控制表以文件为单位，把用户按某种关系划分为若干组，同时规定每组的存取权限。这样，所有用户组对文件权限的集合就形成了该文件的存取控制表，如图下图所示。,

24、55,文件名,用户,56,每个文件都有一张存取控制表。在实现时，该表存放在文件说明中，也就是BFD的有关表目中。文件被打开时，由于存取控制表也相应地被复制到了内存活动文件中，因此，存取控制验证能高效进行。,57,3)口令方式 口令方式有两种。一种是当用户进入系统，为建立终端进程时获得系统使用权口令。显然，如果用户输入的口令（PASSWARD）与原来设置的口令不一致的话，该用户将被系统拒绝。,58,另一种口令方式是，每个用户在创建的文件设置一个口令，且将其置于文件说明中。当任一用户想使用该文件时，都必须首先提供口令。只有当两者相符时才允许存取。,59,显然，口令只有设置者自己知道，若允许其它用户

25、使用自己的文件，口令设置者可将口令赋予其它用户。这样，既可以做到文件共享，又可做到保密。而且，有于口令较为简单，占用的内存单元以及验证口令所费时间都将非常少。不过，相对来说，口令方式保密性能较差。,60,口令一旦被别人掌握，就可以获得同文件主同样的权利而没有任何等级差别。这就使得文件失窃的可能性大大增加。再者，当要修改某个用户的存取权限时，文件必须修改口令，这样，所有共享该文件的用户的存取权限都被取消，除非文件将新的口令通知他们。,61,（4）密码方式 防止文件泄密以及控制访问的另一种方法是密码方式。密码方式在用户创建源文件并将其写入存储设备时对文件进行译码解密。显然，只有能够进行译码解密的用

26、户才能读出被文件信息，从而起到文件保密的作用。文件的加密和解密都需要用户提供一个代码键（KEY）。加密程序根据这一代码键对用户文件进行编码变换，然后将其写入存储设备。在读文件时，只有用户给定的代码键与加密时的代码键相一致时，解密程序才能对加密文件进行解密，将其还原为源文件。加密处理过程如下图所示。,62,密码文件,用户指定代码键,存取要求指定代码,存储,用户,文件,用户文件,63,加密方式具有保密性强的优点，因为与口令不同，进行编码解码的代码键没有存放在系统中，而是由用户自己掌握的。但是，由于编码解码工作要耗费大量的处理时间，因此，加密技术是以牺牲系统开销为代价的。,64,上面各节主要从系统管

27、理的角度讨论文件系统。本节讨论文件系统对用户的接口。 文件系统以系统调用方式或命令方式为用户提供下列几类服务： 1）关于设置和修改用户对文件的存取权限的服务； 2）关于建立，改变和删除目录地服务； 3）关于文件共享，设置访问路径的服务； 4）创建，打开，读写，关闭，以及撤消文件的服务,6.7文件的使用,65,这些服务的调用名和参数都因系统不同而异。例如在UNIX系统中，chmod命令可用来改变一个或多个文件或目录的读写控制模式。读者可在UNIX环境下使用命令manchmod命令阅读到chmod命令的全部详细信息。另外，mkdir,cd,rmdir等命令则可用来建立，改变和删除指定的目录。有关这

28、些命令的详细信息，同样可由man命令从UNIX系统中得到，这里不作介绍。,66,有关对文件操作的命令都基于操作系统提供的系统调用。这些系统调用包括建立文件用的create, 读文件用的read，关闭文件用的close以及撤消文件用的delete等。 其中，create调用将根据用户提供的文件名和属性，在指定的文件存储设备上建立一个文件并把文件标识符返回给用户。而open调用则把文件存储设备上的有关文件说明信息复制到内存的活动文件目录表中。write调用将把从内存中某个位置开始的一段n字节长（字符流文件时）信息或n个记录经设备管理程序写入文件存储设备。read调用的功能与WRITE相反，它把指定

29、文件的几个字或记录读入内存中指定地区。,67,若文件暂时不用时，系统调用close关闭文件。close调用撤消活动文件表中相应表目。delete调用则在一个文件不再被访问时，删除该文件在文件存储设备上的有关说明信息，并释放该文件所占据的全部存储空间.,68,在上面各节中，我们从系统和用户两方面的角度，讨论了，文件系统的基本概念和功能。在这一节中，我们介召文件系统的一般层次模型，一般层次模型，以便使读者对文件系统形成一个完整的概念。 操作系统的层次结构的设计方法是Dijkstra于己于1967年提出的，1968年Madnick将这一思想引入了文件系统。,6.8文件系统的层次模型,69,层次结构法的优点是，可以按照系统所提供的功能来划分为各种不同的层次，下层为上层提供服务，上层使用下层的功能。这样，上下层之间彼此不需要了解对方的内部结构和实现方法，而只关心二者的接