计算机操作系统原理培训及实操第5章.pdf

《计算机操作系统原理培训及实操第5章.pdf》由会员分享，可在线阅读，更多相关《计算机操作系统原理培训及实操第5章.pdf（146页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 文 件 系 统第5章 文 件 系 统5.1 文件系统概述文件系统概述5.2 文件结构和文件存取文件结构和文件存取5.3 文件目录和目录检索文件目录和目录检索5.4 文件共享与保护的实现文件共享与保护的实现5.5 文件系统的用户接口文件系统的用户接口第5章 文 件 系 统5.1 文件系统概述文件系统概述5.1.1 文件文件 如上所述，文件系统的功能是通过把软件资源组织成若干个逻辑单位的方式来实现的。我们把这些逻辑单位称为文件。文件是一个具有符号名的一组相关联的字符的有序序列。从内容来看，有些文件组成的基本单位是一些有序的逻辑记录，如一个班级的学生档案数据；也有些文件是无记录无结构的相关联

2、元素的集合，如C语言的源程序；另外，一些慢速字符设备也可以被看作文件，因为这些设备传输的信息也是一组按顺序出现的字符序列。这些文件一般赋予由特殊字符组成的文件名。第5章 文 件 系 统1文件名文件名 顾名思义，文件名也称作文件标识符，是文件的名字，它是区别不同文件的标识符号。文件名是便于信息保存和读取的重要机制。为了便于管理，必须有文件的命名规则。不同系统中，文件命名规则略有不同。例如，在DOS系统中，要求文件名由18个字母或数字组成，而Windows 98/NT支持长达255个字符。有些文件系统中，要区分文件名的大小写，如UNIX；也有些不区分，如在DOS下，STUDENT和student是

3、同一个文件；在Windows 98中，保留用户起名时字母的大小写，但系统在处理时不作区分，如STUDENT和student虽然看起来外形不同，系统却认为它们是同一个文件。第5章 文 件 系 统 大多数文件系统中的文件名由两部分构成，它们之间用“.”隔开。前面的部分称为主文件名，后面的部分称为扩展名。扩展名提示文件的某些特征或文件内容的类别。UNIX中，甚至支持多个扩展名，例如student.c.Z 表示经过压缩了的C源程序。通常扩展名只是约定俗成的惯例，并不强迫用户使用。但有些例外，比如C编译器可能对非“.c”结尾的程序拒绝编译，而Widnows对于系统不认识的扩展名要求用户给出打开此文件的应

4、用程序名。表5-1列出了一些常用的文件扩展名。第5章 文 件 系 统表表5-1 文件扩展名文件扩展名扩展名含 义.cC源程序文件.bak备份文件.html超文本文档.mpgMPEG编码电影.hlp帮助文件.gifGIF格式图像.obj目标文件.txt文本文件.zip压缩文件.exe可执行文件第5章 文 件 系 统 2文件属性文件属性 除了文件名外，系统还给文件赋予其它特征信息以便于管理和控制存取，这些信息称为文件属性。文件属性通常包括文件当前的状态和使用标志，有些系统将它们和文件名一起放在特殊的数据结构中以便查询。表5-2列出了一些常用的文件属性。第5章 文 件 系 统表表5-2 文文 件件

5、属属 性性域含 义创建者文件创建者的用户名只读标志是否只读隐藏标志是否隐藏系统标志是否系统文件物理位置存放设备及存放位置记录长度内部记录的字节数文件长度文件的字节数创建时间文件创建的日期和时间最后存取时间最后一次存取的日期和时间保护文件存取权限的规定口令访问该文件所需的口令第5章 文 件 系 统 在DOS系统的文件系统中，每个文件都有一个记录文件名及所有属性的数据结构，称为目录项，由32个字节组成，表5-3是DOS中一个目录项的结构。表表5-3 DOS的文件属性的文件属性文件名 扩展名 属性 未用 建立时间 日期 首簇号 文件长度 字节 8 3 1 10 2 2 2 4 第5章 文 件 系 统

6、 3文件的类型文件的类型 从不同的角度可以对文件进行不同的分类。从系统角度来看，主要类型有正规文件、目录文件和设备文件。正规文件指包含用户信息或系统数据的文件；目录文件是管理文件的特殊系统文件；设备文件分为以字符为处理单位的字符设备文件和以块为处理单位的块设备文件。本章我们先研究正规文件，在5.3节中讨论目录文件，设备文件在UNIX系统中讨论。第5章 文 件 系 统 一般说来，正规文件从内容来看有ASCII码文件和二进制文件两种形式。前者由多行正文组成，可能用到回车符和换行符，后者是简单的二进制字节序列。ASCII码文件的优点是可以直接原样打印。对二进制文件的打印只能得到一堆乱码，但它们往往有

7、一定的内部结构。比如每个系统中的可执行的二进制文件，可能就包括文件头、正文、数据、重定位标识和符号表等部分。第5章 文 件 系 统 正规文件还可以进行如下分类：(1)按用途可以分为：系统文件、库文件与用户文件。系统文件是支持操作系统实现基本功能的文件，用户不能直接使用，只能通过系统调用为用户服务。库文件由标准子程序及常用的应用程序组成，允许用户调用，但不允许修改。用户文件是用户委托系统保存的文件，如源程序、目标程序、原始数据、计算结果等。(2)从系统保护角度分为：只读文件、读写文件、不保护文件。不同类型表明用户对不同文件的读写权限和系统对文件赋予的保护级别。第5章 文 件 系 统 (3)按文件

8、物理结构分为：连续文件、串联文件、索引文件。连续文件的文件信息存放在外存中连续的存储块中。串联文件则放在外存中以链接方式连接的存储块中，存储块在物理位置上并不一定连续。索引文件的文件位置由索引表指出。(4)按存放时间分为：临时文件、永久文件、档案文件。临时文件是解题过程中的“中间文件”，暂存在磁盘上，随用户撤离而撤消。永久文件一般在磁盘和作为档案的磁带上都有副本，以便于用户经常使用。档案文件只保留在磁带上，以备查证和恢复文件时使用。第5章 文 件 系 统 (5)按文件内部信息的结构分为：流式文件、记录文件。流式文件内部信息没有结构，它是一个字符流，有结束符。记录文件的内部可以划分为多个记录，用

9、户以记录为单位组织和使用信息。第5章 文 件 系 统5.1.2 文件系统文件系统 1文件系统的概念文件系统的概念 所谓文件系统，是指操作系统中涉及到文件管理的那部分软件、管理时用到的数据结构及其被管理的文件。从用户的角度看，文件系统的主要功能是实现“按名存取”，即用户只需要知道文件名，就可以存取文件的信息，而不需要知道它们具体的存放位置。从系统的角度看，文件系统是对文件存储器的存储空间进行组织、分配、回收，负责文件的存储并对存入的文件实施保护、检索的系统。具体地说，文件系统负责为用户建立文件，存入、读取、修改、转储文件，控制对文件的存取，当用户不再使用时撤消文件。由此可见，文件系统是以对用户“

10、透明”的方式实现对信息管理的一种有力的手段。第5章 文 件 系 统 2文件系统的功能文件系统的功能 文件系统虽然被用户使用，但它的任务首先是解决对文件存储器空间的有效管理问题，通常文件存储器上的物理空间是以物理块为单位进行分配的，这是构成文件组织形式的主要依据。文件系统的第二个任务是文件的命名和共享问题，即解决文件命名的冲突、重名及实现对文件共享的需要。文件系统的第三个任务是提供合适的存取方法，以适合不同的应用。但是文件系统对所管理的信息仅提供存取方式和保护，至于它们之间的结构关系并不关心，也无力对它们进行解释，这是与数据库系统对数据管理显然不同的地方。第5章 文 件 系 统 基于以上考虑，文

11、件系统应该实现如下功能：(1)通过各种数据结构记录系统中的全部信息，包括信息的名字、位置和存取权限等。(2)使用户可以方便灵活地进行信息存取，即用户无需考虑外存的信息组织，也无需记住信息在外存的存储和分布情况，完全实现按名存取。(3)提供安全可靠的保护措施，以避免各种故障或偶然性事故而产生的破坏行为，并防止授权或未授权的用户有意或无意地进行破坏性操作。(4)防止用户信息失窃，采取对文件进行加密等措施，为用户提供保密手段。(5)为节省空间，方便用户存取，协调相关用户共同完成某项任务，文件系统为用户提供共享功能。第5章 文 件 系 统5.2 文件结构和文件存取文件结构和文件存取5.2.1 文件逻辑

12、结构及文件存取文件逻辑结构及文件存取 1逻辑结构（用户观点）逻辑结构（用户观点）逻辑结构是从用户的角度观察到的文件结构。文件内的信息是由创建者定义的，有很多不同的类型。例如文本、数据、目标程序，图像等。试图执行一个文本文件和打印一个目标文件都是没有意义的。人们当然希望操作系统能够知道特定文件结构，以支持不同的文件操作。问题在于让操作系统知道具体的文件结构十分不便，不但会大大地增加操作系统的代码，也会使其自身十分不灵活，特别是出现新的结构会使它变得无能为力。所以，操作系统内部一般将文件视为无结构或简单结构的信息流，不对文件的信息项做任何解释。具体的信息处理由相应的应用程序提供。几种常用的逻辑结构

13、如图5-1所示。第5章 文 件 系 统图5-1 文件的三种逻辑结构(a)字符序列R1Rn S T U D E N T(b)记录序列(c)记录树第5章 文 件 系 统 (1)流式结构：在流式结构中文件是无结构的字符序列，它的信息单位是字节或字。操作系统不知道也不关心文件中的具体内容，它所见到的都是字节或字。UNIX和DOS均使用这种结构，Windows 95/98也基本采用这种方式，只是使用了长文件名。这种结构的特点是使用灵活、方便。用户程序可以在文件内加入任何内容，并且以方便的形式命名。这时，处理文件结构的任务由用户完成，如图5-1(a)所示。第5章 文 件 系 统 (2)记录式结构：在记录式

14、结构中文件由固定长度或可变长度的记录组成，即文件具有自身的记录结构，每条记录也有内部结构，如图5-1(b)所示。这时，文件读写的逻辑单位是一条记录。CP/M系统采用了固定长记录方式组织文件，它的记录长度为128个字符，也有些系统采用可变长的记录组织文件。第5章 文 件 系 统 (3)记录树结构：在记录树结构中，文件由一棵记录树构成，记录的长度通常是不定的。在记录的固定位置包含一个关键字域。记录树按关键字域进行排序，以便于对特定关键字进行快速查找。在记录树结构中由操作系统而不是由用户来决定记录放置的位置，这种结构广泛用于一些进行商业处理的大型计算机系统中，如图5-1(c)所示。第5章 文 件 系

15、 统 2文件的存取文件的存取 文件的存取方法是由文件的性质和用户使用文件的情况来决定的。用户根据文件的逻辑结构对文件进行存取，而不必了解文件具体存储的物理地址，那是由文件的物理组织来确定的。根据文件存取的次序通常可划分为两大类：顺序存取和直接存取。顺序存取是严格按记录或字节排列的顺序依次存取。直接存取也称随机存取，允许随意存取文件的任何记录或字节，而不管上一次存取到哪一条记录或哪一个字节。第5章 文 件 系 统 1)顺序存取 顺序存取方法是指按照记录的顺序依次存取。一般分为固定长度记录的顺序存取和可变长记录的顺序存取。显然，对于上述的两种文件，知道了当前记录的地址，确定下一个要存取的记录地址是

16、比较方便的，只要将记录指针顺序移动即可完成操作。如果文件是可读、可写的，可能读与写的位置不同，则需要分别定义读指针和写指针。存取一个记录后，对指针的位置做相应的修改，如图5-2所示。第5章 文 件 系 统图5-2 顺序存取记录的组织R0R1R2LLLwptr(rptr)R0R1R2wptr(rptr)L01L11L21(a)固定长记录(b)可变长记录第5章 文 件 系 统 对于图5-2(a)固定长记录的顺序文件，需要设置一个专用单元以存放记录长度L，并定义读指针rptr与写指针wptr，它们分别指向下一次读写的首地址。读指针与写指针的初值为第一个记录的首地址。每次读写后，读指针rptr与写指针

17、wptr修改如下：rptr=rptr+L;wptr=wptr+L;对于图5-2(b)可变长记录顺序文件，设第i条记录的长度为Li，存放于该记录前面的单元中，则每次读写后，读指针rptr与写指针wptr修改如下：rptr=rptr+Li+1;wptr=wptr+Li+1;第5章 文 件 系 统 有时为了加速文件的输入、输出，可采用预先缓冲技术，即用户要求读出记录Ri时，系统除Ri外，还预先将Ri的后几条记录读到内存的一个缓冲区中。这样，当用户提出读下一条记录的请求时，记录已在主存中，节约了读取时间。在IBM/370操作系统中提供了预先缓冲链接的方法，即把预读记录的缓冲区链接在一起，排队等待用户提

18、取。这种方法也称为排队顺序存取方法。第5章 文 件 系 统 2)直接存取 用户往往希望能直接得到某个记录。比如在按记录号查询的过程中，用户除了给出文件名外，还显式地指明所需要的记录号。这种存取方法一般通过直接计算或利用指针确定记录的位置，可分为固定长度记录的直接存取和可变长记录的直接存取。如图5-2(a)所示，当记录为固定长时，如果用户提出存取某记录，该记录的逻辑地址是LA=iL其中i为记录号，L为记录的长度，存放于专用单元中。第5章 文 件 系 统 如果记录本身是可变长的，如图5-2(b)所示，则必须从文件的首地址开始，依记录号顺序读出记录，以便查到各个记录的长度。显然，这种方法是十分低效的

19、。利用索引表可以提高存取速度。在索引表表目中存放记录的长度和指针，记录号按顺序排列，指针指向该记录的首地址。存取记录时，先以记录号为索引读出相应表目的指针，再按照指针确定的记录的逻辑地址和长度进行存取，如图5-3所示。因为存取前不能确定下几条记录的长度，因此直接存取方法不能采用预先缓冲技术。一种可以提高效率的方法是系统保存被请求的“上一个”记录号和地址，如果当前的请求大于“上一次”的记录号，则向后查找，否则从文件头开始查找。第5章 文 件 系 统图5-3 直接存取文件的索引表组织01234L0L1L2L3L4R0R1R2R3R4索引号长度指针文件记录第5章 文 件 系 统 3)按键存取 按关键

20、字进行信息查询的存取方法也是一种直接存取方法，目前使用十分普遍。在按键存取中，文件中的记录是按键值顺序存放的。键值通常是记录中某个重要数据项的值，它能区分不同的记录。例如学生的记录表文件，可以按照学号的顺序进行记录的存放和读取。为了提高检索速度，可以采用索引表来指明键和记录的逻辑地址之间的对应关系，如图5-4所示。这里将学号作为记录的键，根据索引表可以查找任何一个键值的记录地址。第5章 文 件 系 统图5-4 按键存取法键960019600296003逻辑地址0200400地址0200400960019600296003学号姓名张名李娜刘方性别男女男年龄252323成绩988975索引表记录表

21、第5章 文 件 系 统 在上述方法中，当记录个数很多时，索引表将十分庞大，检索速度较慢。通常采用的方法是将索引表按关键字分为多级。在主索引中指出二级索引表中一组表目的始地址，二级索引表中每个表目包含一个位置指针，指向文件中由一组记录组成的子集的开始单元。这样，经过多次访问和顺序查询可以查到相应记录的逻辑地址。虽然这种方法比较复杂，但是可以使用多个较小的索引表块，通常比顺序查询速度快。例如，在图5-5中，若要查询学号为9602的记录地址，先找到96索引数据块的逻辑地址，从而查到9601的地址，再经过顺序查询就可以得到9602的数据。第5章 文 件 系 统图5-5 按键存取的多级索引表逻辑地址96

22、01970198019901键96979899逻辑地址键96019610970197109801键96019610970197109801属性主索引二级索引第5章 文 件 系 统5.2.2 文件的物理结构（系统观点）文件的物理结构（系统观点）逻辑文件在外存的组织结构称为文件的物理结构。这种结构的组织依赖于文件存储器（磁带、磁盘、磁鼓等）的物理特性及用户对文件实施的具体操作。为了有效地管理文件的存储空间，文件系统中引入了“物理块”的概念。我们把文件存储空间划分成大小相等的块，文件的存储以块为单位进行。一个“块”一般可以存放一个或几个逻辑记录，块的长度通常等于磁盘扇区的长度。“块”是内存和外存之间

23、进行信息传输的基本物理单位。下面介绍几种常用的物理结构。第5章 文 件 系 统 1连续结构（连续文件）连续结构（连续文件）连续结构是指把逻辑文件中的连续信息存放到连续的物理块中，是连续区分配的一种方法。实现时，系统需要建立一个文件说明表，由文件说明表指出文件名及存放文件信息的第一个物理块的首地址和文件长度（即所占的块数）。这里假定逻辑记录长度和“物理块”大小是相等的。若一个连续文件由m条记录组成，起始记录的位置是第i个物理块，那么其它记录将依次被分配到i+1，i+2，i+m?1等物理块中，如图5-6所示。第5章 文 件 系 统图5-6 连续文件结构文件名 块数 首块号AMii1im1物理块号文

24、件说明表第5章 文 件 系 统 连续文件的优点是物理结构简单，访问文件时通过简单的计算就可得到文件的物理地址，有利于记录定位，存取速度快。连续文件的缺点是建立文件时必须指定文件长度，以后不能增加长度，这是因为与文件尾部相邻的物理块可能已经分配给别的文件了。如果文件长度变化较大，会造成存储空间的浪费或产生碎片，降低存储空间的利用率。与主存的分区式分配类似，采用连续结构分配时，文件存储空间也存在着“碎片”问题，可以采用“紧凑”技术解决。但是这种方法浪费时间，较少采用。第5章 文 件 系 统 连续文件适合的物理设备是顺序存取的磁带，而磁盘则不适于用连续文件处理。因为它的磁头始终处于旋转状态，当存取下

25、一条记录时，磁头可能已经越过位置。因此，在实际系统中，安排相邻记录的存储位置时，往往将它们交叉间隔分布在同一磁道上以节省定位时间。第5章 文 件 系 统 2链接结构（串联文件）链接结构（串联文件）为了克服连续结构的缺点，可以采用链接结构来形成串联文件，把逻辑文件中的连续信息存放到不连续的物理块中，这是非连续区分配的一种方法。实现时，系统需建立一个文件说明表，在文件说明表中指明文件名及存放文件的第一个物理块的首地址和所需块数，利用每个物理块的最后一个单元存放一个指针，指向下一个存放文件的物理块的首地址，指针为空时，表示文件结束。文件的信息内容一般分散在不连续的物理块中，但指针链接的前后两个物理块

26、中的信息在逻辑上是连续的。例如，假设物理块与记录等长，某文件有三个记录，存放在三个物理块中。在文件说明表中指出第一条记录所在的物理块的位置，以后便可以按链找到所有记录，直到物理块中出现文件结束标识为止，如图5-7所示。第5章 文 件 系 统图5-7 串联文件结构文件名 块数 首块号A35文件说明表8物理块51物理块8物理块1第5章 文 件 系 统 显而易见，采用链接方式指明物理块的位置，通过修改链接字，很容易根据需要对文件进行增删，所以节省存储空间。而且在建立文件时无需事先确定好文件的长度，需要增加记录时，只要在外存中有空闲的物理块即可。另外，采用这种文件结构，在任何记录之间插入或删除一个记录

27、时，只要调整有关的指针就可以了。MS-DOS中文件的物理结构就采用这种方式。所不同的是，链指针不是存放在物理块中，而是集中放在一个称为文件分配表（FAT）的数据结构中。DOS的磁盘空间的分配单位是“簇”，对于软盘而言，簇的大小为两个扇区（1 KB）。一个文件的首簇号放在文件目录的相应字段中，每个簇中存放着下一个簇的簇号，依次形成一个“簇号链”，最后一个簇中有文件结束的标识。第5章 文 件 系 统 链接结构的主要缺点是：文件的各个记录在磁盘上分布范围较广，即使顺序访问各个记录，花费的时间也比采用连续文件方式的查找时间长得多。如果用于非连续的随机访问记录，为查找某个记录的物理地址，需要从第一个物理

28、块开始，沿整个链依次进行，查找时间在访问中所占的比例较高，影响访问速度是在所难免的。另外，由于每个物理块都要有链接指针，使磁盘空间的利用率有所降低。对于上述链接结构的缺点，有些系统把链接字和文件信息分开存放，单独组成一张表并存放在外存。这样直接从表中读出物理块的地址，可以提高存取效率，于是就形成了下面将要介绍的索引文件。第5章 文 件 系 统 3索引结构（索引文件）索引结构（索引文件）1)简单索引结构 索引结构是另一种文件存储空间非连续区分配的方法。整个系统建立一文件说明表，其中的每一个表目指出文件名及存放文件索引表的物理块的首地址。系统将文件的全部记录散存于外存的物理块中，并为每一个文件建立

29、一张索引表，每个表目指出文件的记录号与存放的物理块号之间的对应关系，如图5-8所示。第5章 文 件 系 统图5-8 简单索引结构文件名索引表首址记录号物理块号019116230327记录1记录0记录3记录216块19块27块30块文件说明表索引表第5章 文 件 系 统 2)链接式索引结构 有时一个物理块存放不下一个文件的索引表，这时系统会再申请一个物理块继续存放，它的地址由前一个存放索引表的物理块的末地址指出，从而形成链接式索引结构。这样，可以将一个文件的索引表存放在多个物理索引块中，如图5-9所示。第5章 文 件 系 统图5-9 链接式索引结构文件说明表文件名索引表首址记录号物理块号0191

30、1623032748记录1记录0记录2记录3记录416块19块27块30块8块索引表第5章 文 件 系 统 假定一个索引项占2个字节，则512字节大小的物理块可以存放256个索引项。占用空间多于256个物理块的文件，其索引表就要使用多个物理块。例如，RDOS系统就是这样处理的，将多个用于索引的物理块用链接字链接起来。文件索引表是在建立文件时系统自动建立的，索引表往往按关键字的递增序列排序。这样，对文件的访问既可以按索引顺序进行，也可以按关键字进行。在增加或删除某个记录时，索引表必须进行修改。由于每次存取都涉及到索引表的查询，因此所用的查找策略对文件访问的效率有很大影响，通常采用顺序查找法或折半

31、查找法。第5章 文 件 系 统 索引结构除具有串联结构的所有优点之外，还克服了串联结构中必须按链接字顺序存取存储块信息的缺点，可以较为方便地进行随机存取，效率较高。它的缺点是增加了索引表的空间开销，同时在存取文件时首先要取得索引表，增加了一次访盘操作，从而降低了文件访问速度。也有些系统在文件存取之前将索引表放在内存中以节约访问时间，但是索引表较大时，可能需要分几次调入内存。第5章 文 件 系 统 3)多级索引结构 在UNIX文件系统中采用了一种特殊的索引结构多级索引结构，利用索引表指出索引块的物理位置，它可以根据文件的大小调整索引块的个数。在UNIX系统中，有关文件物理位置的信息保存在一个数据

32、结构索引结点（也称为结点）中，由数组i_addr(0)i_addr(12)组成。当系统中物理块长度为1 KB，每个物理块号占用4 B时，则每个物理块可以存放256个物理块的地址。第5章 文 件 系 统 在i_addr(0)i_addr(9)中的每一项直接存放一个物理块号，这些物理块中存储了文件的信息，文件长度可达10块，即10 KB。用i_addr(10)可以实现文件的一级索引结构。在i_addr(10)中，存放一个索引表块的块号，这是一级索引块。在这个索引表块中可以存放256个物理块号，而文件存储在这些物理块中，文件长度可达256+10块，即266 KB。第5章 文 件 系 统 i_addr

33、(11)可用以实现文件的二级索引结构。在i_addr(11)中存放一个索引表块的地址，这个索引表块中可以存放256个的物理块的地址，这些物理块是二级索引块，每个二级索引块中可以存放256个文件存储的物理块号，文件存放在这些物理块中文件长度可以达到256256+256+10块，约为64 MB。i_addr(12)可实现文件的三级索引结构，文件长度可达256256256+256256+256+10块，约为16 GB。第5章 文 件 系 统图5-10 多级索引结构i_addr(0)i_addr(1)i_addr(9)i_addr(10)i_addr(11)i_addr(12)i结点地址信息一级索引块

34、二级索引块三级索引块第5章 文 件 系 统 在多级索引结构中，如果要取出一个固定长记录文件的某一个记录时，必须经过计算才能找到记录存储的物理块号。假设，系统中物理块长为1 KB，每块可以存放256个物理块的地址，记录号从 0 计数。若块长与记录长相等，则查找的对应关系如下：记录号位于09之间，在 i_addr(0)i_addr(9)中查找；记录号位于10256+10之间，利用i_addr(10)查找；记录号位于256+10+1256256+256+10之间，利用i_addr(11)查找；记录号位于256256+256+10+1256256256+256256+256+10之间，利用i_addr

35、(12)查找。第5章 文 件 系 统 例如要查找250号记录所存储的物理块，因为10250256+10，所以要利用i_addr(10)进行查找。文件的09号记录存储的物理块号由i_addr(0)i_addr(9)指出。从10号记录开始，存储块的地址存在一级索引块中，文件的250号记录在一级索引块中的逻辑块号为250?9=241，所以250号记录的内容存放在一级索引块中第241个地址所指的物理块中。第5章 文 件 系 统 4散列结构（哈希文件）散列结构（哈希文件）还有一种物理组织形式是采用计算的方法进行寻址，通常称为Hash方法，也称为散列法或杂凑法。它利用Hash函数对记录中的键值进行计算处理

36、，然后转换为相应的物理地址。一般说来，由于地址的总数比可能的键值总数要少，不同的键值在Hash函数计算之后，可能得到相同的地址，这种现象称为“地址冲突”。通常，为了实现文件存储空间的动态分配，由Hash函数计算出的地址不是直接指示相应记录的存储位置，而是指向某个索引表的相应表目，由这个表目的指针指向那个记录所在的物理块。第5章 文 件 系 统 显然，具有相同Hash函数值的记录存放在同一个物理块中（假设一个物理块可以容纳多个记录），如某个物理块装满，进行溢出处理时，需要再分配一个物理块，以存储具有相同Hash函数值的记录，并用指针把这些物理块链接起来。当然，Hash函数构造不同，散列效果也不同

37、，好的Hash函数可以减少地址冲突，提高存取效率。在查找时，先计算某记录的哈希函数值，根据值的匹配找到索引表的相应表目，然后得到记录的物理地址。如果在第一个物理块中没有找到记录，还需按照溢出链进行查找，当冲突发生较多时，存取的深度增加，如图5-11所示。第5章 文 件 系 统图5-11 散列式结构ABCD记录的键Hash函数：f(x)索引物理块第5章 文 件 系 统5.2.3 记录成组技术记录成组技术 在讨论文件的物理结构时，还有一个比较现实的问题，就是当文件由记录构成，而逻辑记录的长度和物理块大小不相等或不是整倍数时该如何处理。由于文件的逻辑记录长度因文件的不同而异，而物理块的大小则和外存介

38、质有关，记录与物理块之间往往不是一一对应的关系。下面我们讨论在这种情况下，怎样进行记录的存放和读取。记录成组技术指将多个逻辑记录合成一组并保存在物理块上的方法。这时有两种不同的情况。第5章 文 件 系 统 1逻辑记录长度为物理块大小的整数因子逻辑记录长度为物理块大小的整数因子 当逻辑记录长度为物理块大小的整数因子时，即一个物理块可以装下整数个记录。例如，记录长度为200 B，物理块为1000 B，一个物理块中可以存放5个逻辑记录。计算记录所在的相对块号的方法是：相对块号=记录地址 DIN 物理块大小 对于连续文件和串联文件来说，知道了相对块号和文件首地址，顺序查找即可找到相应的物理块。第5章

39、文 件 系 统图5-12 相对块号作为索引相对块号物理块号08123256326第5章 文 件 系 统 对于连续文件和串联文件来说，知道了相对块号和文件首地址，顺序查找即可找到相应的物理块。对于索引文件，为了方便查找，要对索引表作适当的修改。一种方法是利用文件的相对块号作为索引，而不是记录号，如图5-12所示。这样，在记录查找过程中，首先计算某条记录所在的相对块号：相对块号=记录号 DIN 每个物理块存放的记录数再根据索引表查到相应的物理块号地址，最后确定该记录在物理块中的地址，从而得到最终的地址。对于哈希文件，一个物理块容纳多个记录正好可以把Hash函数值相同的记录放在同一个物理块中来处理键

40、值冲突，如果记录填满一个物理块时，则可申请一个新的物理块。第5章 文 件 系 统 2逻辑记录长度不为物理块大小的整数因子逻辑记录长度不为物理块大小的整数因子 一个物理块不能刚好装下整数个逻辑记录时，这种情况的处理较为复杂。例如记录大小为300 B，块大小为1000 B。解决这个问题的方法有三种：(1)空间空闲法，即只存放整数个记录，让剩余空间空闲。比如每条记录占用一个物理块的300 B，或放入3条记录之后不再存放。这种方法虽然简单，但是白白浪费了存储空间，是不可取的。(2)调整物理块的大小。可以根据文件记录长度改变磁盘的磁道、扇区划分格式，使其可以放下整数个记录。但一般说来，改变格式也不是十分

41、方便的，况且还涉及到其它问题，如已经存入的信息如何处理等，所以这种方法通常是不用的。第5章 文 件 系 统 (3)扩充软件法。这种办法允许记录跨物理块存储，并采用扩充软件功能的办法来适应记录的存取。如图5-13所示，第3条记录在物理块1和物理块2中各有一部分。具体算法如下：根据逻辑地址，确定第三条记录的始地址，即记录头；确定记录的首地址所在的物理块号；计算记录的首地址在物理块内的相对地址；计算记录在第一个物理块中的有效长度；计算记录剩余的长度，如果等于0，则说明读取完毕，否则计算出记录剩余部分的逻辑地址。第5章 文 件 系 统图5-13 记录跨物理块存储物理块1物理块2逻辑记录长为300 B物

42、理块长为1000 B记录1记录2记录3记录4第5章 文 件 系 统5.2.4 文件存储空间管理文件存储空间管理 在计算机系统中，文件存储于文件存储空间上。对文件存储空间的管理是系统设计者考虑的一个重要问题。文件的存储有两种策略，一种是为文件分配连续的存储空间，即连续的存储块，另一种是为文件分配不一定连续的块。为文件分配连续的存储空间的方法存在一些明显的问题：如果增加文件内容，使文件长度发生变化时，需要移动一些文件，以便得到一个能存储文件的较大空间，这肯定要增加系统开销；当删除文件内容时，会给文件存储空间留下大大小小的碎片，即出现零头问题，在存储器管理中我们也遇到同样的问题。所以，现在几乎所有的

43、文件系统都把文件存储空间分成固定大小的块来存储文件。存储文件的块与块之间不必相邻。这样，可以更有效地利用外存空间，但是分配和回收的速度可能会受到影响。第5章 文 件 系 统 1块大小的考虑块大小的考虑 由于文件是按块分配的，块的大小是一个十分重要的问题。如果块过大，可能会造成空间的浪费。块过小，意味着每个文件都由许多块组成，必然会影响文件的存取速度。一般系统中，文件存储块的大小常采用512 B、1 KB或2 KB。当然，随着时间的推移，用户对资源的需求在增加，块的大小也应随之改变。例如，1984年调查表明，UNIX系统的文件大小平均在1 KB左右，而到1997年，一般系统中文件的平均长度已升至

44、10 KB以上。第5章 文 件 系 统 2空闲块管理空闲块管理 块的大小选定后，接下来要考虑的是如何对文件存储空间的物理块进行分配和回收的问题。下面介绍三种方法。1)空白文件目录 把一个连续的未分配区域（可能包含若干个空闲块）看作一个文件，称为空白文件。系统为所有的空白文件建立一个目录，即空白文件目录。每个空白文件对应于空白文件目录中的一个表目，如图5-14所示。第5章 文 件 系 统图5-14 空白文件目录序号第一个空闲块号 空闲块个数空闲块号155214331845、6、7、8、914、15、1618、19、20、21第5章 文 件 系 统 当系统为某个新创建的文件分配存储空间时，按顺序从

45、空白文件目录中找出一个大小能满足要求的空白文件进行分配。文件存储空间的分配算法可以参考内存的可变式分区存储管理算法。当用户释放存储空间时，系统将回收的空间制作成一个新的空白文件表目，插入空白文件目录中，以备后用。如果回收的空间与空白文件目录插入点前后的空白文件地址相邻接，应予以合并。第5章 文 件 系 统 2)空闲块链接法 空闲块链接法可以分为：空闲盘块链、空闲盘区链及成组链接法。(1)空闲盘块链。空闲盘块链法是将文件存储空间上所有空闲盘块链接在一起，设一个指针，指向链头，当系统为某个新创建的文件分配存储空间时，从空闲盘块链首端摘下空闲盘块进行分配。当系统回收用户释放的存储空间时，将回收块链入

46、空闲盘块链的链头，如图5-15所示。第5章 文 件 系 统图5-15 空闲盘块链 空闲盘块链法的分配与回收过程都十分简单，但是空闲盘块链可能会很长。第5章 文 件 系 统 (2)空闲盘区链。空闲盘区链法是将若干连续的空闲盘块作为一个空闲盘区，每个区含有一个指向下一个空闲盘区的指针及本空闲盘区大小的说明，所有空闲盘区形成一个链，设一个指针，指向链头，如图5-16所示。图5-16 空闲盘区链第5章 文 件 系 统 采用空闲盘区链法，当系统为某个新创建的文件分配存储空间时，按顺序从空闲盘区链中找出大小能满足要求的空闲盘区进行分配。分配算法可以参考内存的可变式分区存储管理算法。当系统为某个新创建文件分

47、配存储空间时，从空闲盘区链摘下能放下文件的盘区予以分配，若盘区太大，则将盘区一分为二，一部分用于分配，而另一部分仍以空闲盘区的形式存在空闲盘区链中。当用户释放存储空间时，系统将回收的空间作为一个新的空闲盘区插入空闲盘区链中，以备后用。如果回收的空闲盘区与空闲盘区链插入点前后的空闲盘区地址相邻接，应予以合并。为了提高对空闲盘区链的查找速度，通常在内存建立空闲盘区的链表。空闲盘区链法的分配与回收过程比较复杂，但是空闲盘区链较短。第5章 文 件 系 统 (3)成组链接法。在UNIX系统中采用了一种改进的方法。它把文件存储空间的空闲盘块分组，再将每组具体的空闲盘块号及个数记录到另一组的第一个空闲盘块中

48、，组与组之间通过每组的第一块链接起来，将当前使用的一组空闲盘块号及块数放在空闲盘块号栈中。系统启动后，文件存储空间的分配与回收通过已进入内存的空闲盘块号栈进行；栈空时，将链接的下一组空闲盘块号及块数调入；栈满时，将栈中的空闲盘块号作为一组，加入链中，这就是成组链接法，如图5-17所示。第5章 文 件 系 统图5-17 空闲盘块的成组链接法401501491481121110123839专用块50200199198151149111第78组15050250249248201199151第77组20050039993998395139493901第2组395039993951第1组第5章 文 件

49、系 统 假设在系统初启时，文件存储空间已经划分为块，全部是空闲状态。对这些空闲块从尾到头进行分组，每组块数确定，例如50块，最后一组可能不足50块（假定有40块），这时每组中的空闲盘块号是连续的，工作一段时间以后就不连续了。每一组的第一块中暂存前面一组的总块数及具体空闲盘块号，其余的块完全是空闲的。最后一组（图5-17中第78组）的具体空闲盘块号及块数记在卷资源表（在专用块中）的空闲盘块号栈中。第1组少一块，其后面的第2组中的第一块（3950块）应存放第50个空闲盘块号的位置被标记为0，作为文件存储空间再无空闲块可分配的警戒。为了分配与回收的有序进行，空闲盘块号栈要作为临界资源使用，栈中块数可

50、以兼作栈顶指针用。系统开启后，卷资源表被复制到内存，空闲盘块号栈也随之进入，其后的分配与回收均在内存进行。第5章 文 件 系 统栈指针1栈指针栈指针为栈底?栈底为0?警戒标志出现,无法分配分配栈指针所指块号该块中的存放信息入栈，分配此块YYNN上锁否?等待NY栈指针1栈指针解锁返回上锁图5-18 成组链接法分配算法 第5章 文 件 系 统图5-19 成组链接法回收算法栈满否？栈中总块数及块号存入回收块中栈指针置为0回收块号记入栈底0项中栈指针1栈指针回收块号记入栈顶YN解锁返回上锁上锁否？等待YN第5章 文 件 系 统图5-20 成组链接法的一次回收过程48空闲盘块号栈957059014748