第五章文件管理.ppt

《第五章文件管理.ppt》由会员分享，可在线阅读，更多相关《第五章文件管理.ppt（194页珍藏版）》请在三一文库上搜索。

1、文件管理 第五章,本章要点,文件管理系统 文件的基本概念、操作 文件目录 文件的逻辑组织与访问 文件记录与数据块的关系 文件共享 文件存储空间与空闲空间的管理,？ 问题,什么是文件？ 文件由什么组成？ 文件如何命名？ 如何保证文件数据的安全？ 对文件可以进行哪些操作？ 文件在磁盘上如何存储？ 磁盘的空白存储区如何管理 ？,5.1 文件系统概述,文件系统的功能,有效地管理文件的存储空间； 管理文件目录； 完成文件的读/写操作； 实现文件共享与保护； 为用户提供交互式命令接口和程序调用接口。,交互式文件系统的基本服务,用户可以创建、删除、读取或更新文件； 一个用户可以受控制地访问其他用户的文件；

2、可以控制不同用户对不同文件的访问权限； 用户可以根据实际需要重新构造文件； 允许用户在两个文件之间移动数据； 用户能备份文件，且能在文件被毁坏时，恢复文件； 用户可以通过符号名访问文件。,文件系统,是指，操作系统中的各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合。 有少数文件系统从操作系统中分离出来，独立于操作系统存在 绝大多数操作系统都包含文件管理系统部分。,5.2 文件系统与数据库管理系统,文件系统 vs. 数据库管理系统,数据库管理系统依赖文件系统 - 数据库管理系统负责：数据定义及操作 - 文件系统只处理无结构、无格式的字节流 数据库管理系统独立于文件系统,5.3

3、 文件,文件,文件是一种具有符号名的、相关联元素的有序集合 各种程序、数据集合 一些低速的字符设备，如键盘、终端显示器和打印机等也被看着文件,文件中的数据结构 字段或域（Field）,字段具有唯一的值 字段的基本属性：长度、数据类型 字段长度：固定、可变 复合字段：由若干子字段组成 如工资字段：基本工资、工龄工资、职称工资等,文件中的数据结构 记录（Record）,一组相关字段的集合 学生记录：学号、姓名、性别、班级、平均成绩、名次、获奖情况等。 记录长度：固定、可变。 可变长记录：字段长可变、字段数目可变 可变长记录：长度字段 记录：关键字，唯一地标识一条记录,数据库（Database）,数

4、据库是相关数据的集合，通常由若干数据库表格构成（数据库表格由若干记录构成，记录由若干字段构成）。 数据库还可以由一种或多种类型的文件组成。 数据库一般需要专门的数据库管理系统进行管理，数据库应用程序运行在数据库管理系统之上。,对记录的操作,检索所有记录 从文件的第一条记录开始顺序访问文件中的每一条记录。 检索一条记录 检索下一条记录 位置指针：记载当前访问的位置。 从位置指针开始访问逻辑上的下一条记录。 检索前一条记录 类似于“检索下一条记录”。访问位置指针的前一条记录。,对记录的操作,插入一条记录 如果文件中的记录存在某种顺序，那么，新记录必须插入到适当的位置，可能需要物理上移动已有的记录。

5、 删除一条记录 删除一条已有的记录，通常需要指定能唯一标识一条记录的关键字。删除操作常常为指定记录注明“被删除”标志，而非真正“抹去”。,对记录的操作,更新一条记录 首先访问指定记录，更新其一个或多个字段值，然后将更新的记录内容写回文件。但是，一般不会更新记录的主关键字的值。 检索某些记录 有时需要检索满足某种条件的若干条记录。例如，查询平均成绩90分以上的学生，查询某班的男生信息等。,文件的类型 按文件的逻辑结构分类,无结构文件 无结构文件可以看成是一个字节流，其文件元素为一个“字符”或“字节”，有时又称为字节流文件，或流文件。 有结构文件 有结构文件的文件元素是一条记录，文件由若干相关记录

6、组成。 根据记录的组织方式不同，可以分为堆文件、顺序文件、索引顺序文件、索引文件和直接（哈希）文件。,文件的类型 按文件的物理组织结构分类,连续文件 把文件中的信息顺序、连续地存储到若干相邻的存储块中。 非连续文件：链接文件、索引文件,文件的类型 按文件的物理组织结构分类,链接文件 文件中逻辑上连续的信息可以存储到分散各处的存储块中，各盘块通过其内的链接指针相连。 一个文件的所有盘块形成一个链表，或用专门的存储块记载一个文件的所有盘块的起始地址。 索引文件 文件中逻辑上连续的信息可以存储到分散各处的存储块中。 系统为每个文件建立一张索引表，一个索引表项记载一个存储块或一组连续存储块的起始地址。

7、,文件的类型 按文件的保护级别分类,只读文件 仅允许文件主及授权用户对其进行读操作的文件。 用户的某些文件也可以设置成只读属性，不允许修改。 执行文件 只允许授权用户调用执行，不允许读/写的文件，如系统调用等某些公用程序。,文件的类型 按文件的保护级别分类,读/写文件 只允许文件主及授权用户进行读或写的文件。 不保护文件 所有用户都可以访问的文件，不受系统的任何保护。,文件的类型 按文件的性质和用途分类,系统文件 指操作系统文件或其它系统文件。一般只能通过操作系统调用为用户服务。 用户文件 由用户的程序或数据组成的文件。 库文件 由系统提供给用户调用的各种标准过程、函数和应用程序等。这类文件允

8、许用户调用，但不允许用户修改，如Windows的应用程序编程接口API，C语言的标准I/O库函数及通信库函数等。,文件的类型 按文件中的数据形式分类,源文件 目标文件 可执行文件,文件的类型 多媒体文件,集成了数字、字符、格式化文本、可执行程序、图形、图像、声音等信息。 多媒体文件需要的存储空间比传统的数字字符文件大约要高出5倍以上。 例如，一页格式化的文本文件大约需要0.5KB 1KB的存储空间，但同样尺寸的一页彩色图像大约需要10MB 存储空间。 一般为变长记录文件。 多媒体文件文件系统不仅要保存数据，而且还要保存大量的数据类型说明信息。,对文件的操作,对整个文件的操作 建立文件、撤消文件

9、、打开文件、关闭文件、复制文件、修改文件名、打印或显示文件内容等 对文件中的数据项的操作 读操作、写操作、更新操作、插入操作、删除操作等,对文件的操作 打开文件（Open file ）,首先，根据文件名查找目录文件（由目录构成的文件），找到该文件的目录信息。 然后，将该目录信息装入主存，建立相应的文件控制块FCB，并将文件的当前使用信息填入FCB中。 最后，返回一个文件内部标识符。 如果该文件具有某种存取控制，如只读，或可读/写，则文件打开时，这种存取控制也将作为参数同时返回。,对文件的操作 关闭文件（Close file ）,将该文件FCB中的有关信息写入外存的目录信息中； 撤消其FCB；

10、释放文件占用的其它系统资源，切断用户与该文件的联系。,对文件的操作 建立文件（Create file）,分配必要的外存空间； 建立一个目录项，记录新文件的文件名、建立时间等信息。,对文件的操作 撤消文件（Destroy file ）,也称删除文件。系统删除一个文件必须至少完成两件事： 第一，判断该文件可否被删除。若可以被删除，则首先删除文件的目录项，否则，给出相应提示。 第二，回收该文件所占用的外存空间。,对文件的操作 复制文件（Copy file）,拷贝文件内容及其目录项。 首先查找目录文件，找到该文件的目录项，从中找出该文件的外存地址； 通过该地址找到文件内容； 然后，将其目录项及文件内容

11、，按指定的路径拷贝过去。,对文件的操作 修改文件名（Rename）,首先在目录文件中查找指定文件名的目录项； 然后将其中的文件名更换成新的文件名。,对文件的操作 读操作（Read）,给出文件名和所读字节数。 首先查找目录文件，找到指定文件的目录项，从中找出该文件的外存地址； 然后，从该文件读指针所指位置开始，读取指定长度的字节数到缓冲区，同时该文件的读指针顺延指定长度的位置。 最后，返回最新读指针位置值。如果读指针遇到文件结束标志，则给出相应提示信息。,对文件的操作 写操作（Write）,必须给出文件名和需要写的字节数。 系统从缓冲区中将指定长度的信息写入指定文件写指针位置； 将文件的写指针顺

12、延指定长度的位置。,对文件的操作 更新操作（Update）,更新文件中的数据项时，系统调用中必须给出文件名、更新数据项的原值及替换值。 首先从文件中查找指定数据项值，若找不到，则给出相应信息； 若找到，则用替换值更新原值。 用户可以指定更新次数或全部自动更新。,对文件的操作 插入操作（Insert）,在文件的指定位置添加新的数据项。 对于无结构文件，插入一个数据项以后，其后所有字符的索引号将作相应调整； 对于有结构文件，插入一个数据项，一般指增加一条记录，新记录之后的所有记录号也将作相应调整。,对文件的操作 删除操作（Delete）,删除文件中指定的数据项。 首先查找文件中指定数据项，再将其删

13、除。 若找不到，则返回相应信息。 用户可以指定删除数据项的位置，或将数据项在文件中的所有出现均删除。,5.4 文件目录,文件目录的内容,基本信息：文件名、文件类型、文件组织等； 地址信息：卷（存储文件的设备）、起始地址，（起始物理地址）、文件长度，（以字节、字或块为单位）等。 访问控制信息：文件所有者、访问信息（用户名和口令等）、合法操作等； 使用信息：创建时间、创建者身份、当前状态、最近修改时间、最近访问时间等。,FCB,目录内容的组织方式及分析,目录项：全部目录内容 目录项：部分目录信息，如文件名、文件大小、外存中的存储位置等，其余部分保存在文件头部,目录文件及操作,目录文件：多个文件的目

14、录项构成的一种特殊文件。 搜索目录 创建目录 删除目录 显示目录 修改目录,目录结构,单级目录结构 两级目录结构 层次目录结构 ：树型目录、无循环图,单级目录结构,所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项。,单级目录结构分析,实现简单，易于维护 问题： 重名问题 存放文件数量受限 当目录文件很大时，检索时间长 不便于实现文件共享,两级目录结构,主文件目录、用户文件目录,两级目录结构分析,一定程度解决了重名问题 提高了文件目录检索效率 简单的文件共享 问题：不便用户文件的逻辑分类；进一步解决重名、共享、检索效率等问题,层次目录结构 树型目录,无循环图结构,（root

15、）,dev,liu,user,bin,wei,src,tty01,tty02,lp,man,stt,dkt,kky,p01,moon,star,图5.4 UNIX的无循环图目录结构,文件路径,相对路径 绝对路径,5.5 文件的逻辑组织与访问,有结构文件与文件系统,大多数的文件系统是无结构文件系统 实际应用却需要处理各种数据结构，这些数据结构一般不依赖文件系统，而是由相应的应用程序提供。 例如，UNIX的文件系统，它本身不含任何数据结构。但是，UNIX却能支持使用有结构文件的应用程序，如各种基于UNIX操作系统的数据库管理系统、电子邮件系统等。 这类应用程序必须能定义自己的数据结构，并能实现记录

16、与字节流之间的转换。,type message = record to : array of address ; from : array of address ; subject : array of line ; cc : array of address; body : array of string ; Procedure getRecord (void) ; var msg : message ; begin msg = allocate(sizeof(message); msg . to = getAddress(); msg . from = getAddress(); msg

17、. cc = getAddress(); msg . subject = getLine(); msg . body = getString(); return(msg); end.,Procedure putRecord (void) ; var msg : message ; begin putAddress(msg . to); putAddress(msg . from); putAddress(msg . cc); putLine(msg . subject); putString(msg . body); end; 图5.5 一种电子邮件的格式定义,有结构文件与文件系统,配置在某些

18、大型计算机中的操作系统，如IBM MVS 、Macintosh的文件系统自身就能提供若干数据结构。 文件系统直接控制管理有结构文件，称为有结构文件系统，或高级文件系统,文件组织的一般原则,有利于快速访问文件记录 该原则适用于访问单条记录。若以批量方式访问文件，该原则不太重要。 易于更新 更新文件内容时，可能需要首先查找源数据，再进行修改。但是，对于 CD-ROM 文件，该原则这并不重要。 存储代价小 无冗余信息。但是，有时候必须牺牲适量的存储空间，以提高文件访问速度。 维护简单 可靠性高,有结构文件,堆文件 顺序文件 索引顺序文件 索引文件 直接（哈希）文件,堆文件（pile）,最简单的文件组

19、织方式。 可以是无结构的字节流文件，也可以是由记录构成的有结构文件。 组成堆文件的记录可以有不同的字段、不同的长度。因此，严格地说，堆文件应该属于无结构文件。 记录按到达先后次序存放，最开始存入的记录为第一条记录，接着存入第二条记录，第三条记录，其余依次类推。,堆文件（pile）,堆文件（pile）,有利于累计并保存大批量数据。 常用于存放刚采集到的、未被处理的数据，或存储后较少访问的数据，或者不便于组织的数据。 堆文件易于更新，因为更新数据直接追加到文件尾，无须插入到某个中间位置。 但是，堆文件的记录访问效率极低。因此，大多数应用程序都不采用该文件类型。,顺序文件 （Sequential F

20、ile）,由若干条逻辑记录按照其关键字的某种顺序排列而构成的文件。 是最常用的文件组织方式 每条记录都包含固定的字段，具有相同的长度。 每条记录都包含一个特殊字段关键字，不同记录的关键字是不同的。 记录按关键字排序，若关键字字段的类型是字符型，则按字母排序；若关键字字段是数值型，则按数字排序。,顺序文件 （Sequential File）,关键字,图5.7 顺序文件,顺序文件 （Sequential File）,常用于批量数据处理，这时文件的访问效率最高。 是唯一、同时适合在磁盘和磁带中存储的文件。 访问效率比堆文件高。当文件较小，可以将文件全部装入内存，利用某种快速的查找算法，如折半查找法、

21、插值查找法等快速查找指定的记录。,顺序文件 （Sequential File）,但是，访问一个大型顺序文件时，效率将会大大降低。 更新效率较低。因为记录必须插入到按关键字排序的某个位置，其后的各记录必须进行物理上的位移，效率非常低。 解决方法：单独建立一个日志文件，或事务文件。新记录首先放在日志文件中，通过周期性地执行批量更新操作，把日志文件合并到主文件中，并按原有的关键字顺序排列全部记录。,索引顺序文件 （Indexed Sequential File）,将主文件（顺序文件）的所有记录按照某种标准分组，例如，首字母相同的记录为一组；或按每小时或某固定长度的时间将记录分组；或者按固定条数的记录

22、为一组，为主文件建立一张索引表。 索引表记载每一组的第一条记录的关键字值和指向该记录的指针。 索引表和主文件（顺序文件）一起形成索引顺序文件。,向索引顺序文件插入记录,将记录直接插入顺序文件中，效率非常低。 建立备份文件。新记录首先插入备份文件中，系统再周期性地批量合并主文件和备份文件。 为主文件的每条记录增加一个指针域，指向备份文件的某一条记录，该指针域对应用程序透明。 插入新记录到备份文件时，修改新记录逻辑前序记录的指针：前序记录可能在主文件中，可能在在备份文件中,多级索引,若主文件非常大，只建立一级索引，则访问效率还是很低。 为了提高访问效率，可以为顺序文件建立多级索引，即为索引文件再建

23、立一张索引表，从而形成两级索引，依此类推。 根据实际需要还可以建立更多级索引。 访问信息时，总是从最高级索引表开始，逐级向低级索引表进行访问，最后访问到主文件中的某记录。,顺序文件 vs. 一级索引,例如 一个顺序文件：100万条记录，查找其中的一条记录平均需要访问50万条记录。 将该文件按1000条记录为一组，建立一级索引。查找索引表，平均需要查找500条记录。查找顺序文件中的某一组，平均需要查找500条记录。共计查找1000条记录。,一级索引,主文件,1000 000,1000,1000 * 1000 = 1000 000,顺序文件 vs. 二级索引,如果将该文件按100条记录为一组，为主

24、文件建立一级索引表。 再将一级索引表按100条记录为一组，建立一个二级索引。 首先查找二级索引表，平均需要查找50条记录。再查找二级索引表中某一组，平均需要查找50条记录。最后，查找顺序文件中的某一组，平均需要查找50条记录。 共计查找150条记录。,100万,索引文件（Indexed File）,文件中记录的访问并非总是按关键字进行，很多应用对记录的访问都是随机的。 例如，交互式查询系统往往需要根据用户给定的条件，查询文件中的某条或某几条记录，而非顺序访问文件的每一条记录。 主文件的记录不必按关键字排序 为文件建立一张索引表，主文件中的每一条记录在索引表中都有一个对应的表项，其中记载了相应记

25、录的索引值及指向记录的指针，并按索引值排序。,索引文件（Indexed File）,这相当于将主文件的记录逻辑上进行了排序，而无需将每一条记录进行物理上的位移，从而节省了大量的系统时间。 要查找文件记录，必须首先访问索引表，而索引表可以按索引号的顺序组织为顺序文件，访问记录时，可以通过计算得到每一条表项的地址，从而实现快速直接访问。,索引文件（Indexed File）,索引文件（Indexed File）,完备索引：为主文件的每条记录建一个索引项。 部分索引：仅为感兴趣的记录建立索引,索引文件（Indexed File）,有的应用系统会自动为文件按主关键字建立索引表。每当向文件中写入记录时，

26、其关键字就自动从记录体中分离出来，放入相应的索引表中，并用指针指向对应的记录起始地址。 实际应用中常常需要按不同条件查询记录信息，应允许为每一条记录按多个字段建立多个索引表，以提高实际应用中查询的效率。 索引表需要额外的系统空间/时间开销。但是，使用索引文件会大大提高记录的访问效率。 因此，索引文件广泛地用于商业信息管理系统,直接（哈希）文件,利用Hash函数，根据记录的关键字计算记录的存储位置，并按关键字访问记录 能提高记录的访问效率 常用于访问速率要求高、一次存取一条记录且记录为定长的文件。如文件目录、价格表、名单等文件记录的存取。,5.6 文件的物理组织存储空间的管理,文件存储空间分配的

27、有关问题,从逻辑组织的角度看，文件由若干记录构成； 从物理组织的角度看，文件由若干数据块组成。操作系统或文件管理系统负责为文件分配和管理数据块。 如何划分磁盘空间？ 如何为一个新建文件分配空间？ 如何为一个已存在的文件增加存储空间？ 用什么数据结构记载文件已分配到的数据块和空闲数据块？,预分配与动态分配,创建新文件时，需要分配存储空间。 一次性地为新文件分配足够的存储空间 先为文件分配一部分存储空间，以后再根据需要增加存储空间？ 前一种分配方法称为预分配，后一种分配方法称为动态分配。,预分配与动态分配,要求文件创建时必须申明需要的最大空间。 编译程序，拷贝文件，通过网络传输文件等，可以预先知道

28、文件的大小； 很多应用都不可能预先知道文件需要的最大空间。预先准确估计文件大小是不可能的。 如果估计的空间太小，无法满足文件的存储需要和存储空间的增长需要；如果估计太大，会浪费存储空间。 动态分配方法能满足文件存储空间的增长需要。,分区大小,外存空间被分成若干大小相同的数据块，类似于内存空间的分页管理技术。 分区 = 数据块 有利于提高外存空间的利用率，I/O性能较低。 可变大小的分区 分区 = 若干连续数据块,与分区大小有关的因素,文件中的数据相邻存储有利于提高性能； 若分区太小，文件分配到的分区数目将会很多。用于管理分区（已分配和未分配的）的数据结构如表格等将会很大，增加管理复杂度； 若分

29、区大小固定，将会简化空间的分配和回收； 若分区大小可变，或分区大小固定且较小，可以减少存储空间的浪费。 确定分区大小时，需要综合考虑以上若干因素。,可变大小的分区 vs.固定小分区,对于预分配方法，若采用小分区，预先分配给文件足够数量的小分区，可能使文件分配表很大。但由于文件空间不再增加，文件分配表将保持固定大小，不会改变。 若采用可变大小的连续分区模式。无须设置文件分配表，只需要记住文件存储空间的第一个数据块的地址和分区大小，就能定位一个文件。,基于可变的分区的分配算法,首次适应法 下次适应法 最佳适应法,文件存储空间的分配技术,连续分配和非连续分配 非连续分配：链接分配和索引分配,连续分配

30、,采用可变大小的连续分区、预分配技术 把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以进行顺序存取。 优点：简单、容易实现。,连续分配,文件分配表中为每个文件建立一个表项，其中记载文件的第一个数据块地址及文件长度。 对于顺序文件，连续读/写多个数据块内容时，性能较好。 能很快检索文件中的一个数据块。 例如，如果一个文件的第一个数据块的序号为x，需要检索文件的第y块，则该数据块在外存中的位置为x+y-1。,连续分配存在的问题,不利于文件尺寸的动态增长。 空间利用率不高：对于需要很长时间才能完成增长的文件，预先分配的较大存储空间也会在较长时间得不到有效利用,连续分配存

31、在的问题,该分配方案可能会导致磁盘碎片，严重降低外存空间的利用率。 解决方法之一，系统定期或不定期采用紧凑技术，将小分区合并为大的、连续分区，将文件占用空间合并在一起。,链接分配,连续分配的文件分区太大，不利于存储空间的有效利用。 非连续分配可以将文件分区划小，最小的文件分区基于一个数据块。 能显著提高存储空间的利用率。 链接分配方法可以按基于数据块的文件分区进行分配，为文件分配非连续的若干数据块，数据块之间用指针相连,链接分配,消除连续分配引起的外部碎片，提高了外存空间的利用率。 能适应文件尺寸的动态增长。 文件分配表中的目录项也非常简单，只需记载文件的第一个数据块地址和文件长度。,链接分配

32、,适合于文件的顺序存取，但对于随机存取却相当低效。 如果要访问文件的第i 个数据块，必须首先从文件分配表的相应目录项中找到该文件的第一个数据块地址，读出第一个数据块中包含的第二个数据块的指针。 然后，从第二个数据块中读出指向第三个数据块的指针。依次类推，直到找到第 i 1个数据块，从中读出指向第i 个数据块的指针。,链接分配,最后，读取第 i 个数据块的内容。如果一个文件包含成百上千个数据块，则需要花费很长的时间来访问接近链表尾的数据块。 大量数据块依靠块内指针逐一相连，其可靠性较差。 每个数据块必须包含指针信息，这将占用额外存储空间。,链接分配,为了提高文件检索速度及减少块内指针占用的存储空

33、间，有的操作系统将文件分区设置为若干个（数目相同或不同）连续的数据块，称之为簇(Cluster)。 这样，为文件分配存储空间时，以可变大小的分区为单位。文件的存储空间不再由若干离散的、小的数据块构成，而是由数目相对较少的、局部连续的文件分区组成。 每个文件的各个文件分区通过指针链接在一起。,链接分配,链接分配使文件的存储空间失去连续性，不便于文件的顺序访问。 为此，系统可以周期性地将每个文件的若干离散数据块进行整理，并修改文件分配表中文件的起始地址,图5.14 链接分配 （图5.13经过整理以后）,12,13,14,15,16,17,24,25,26,27,28,29,18,19,20,21,

34、22,23,30,31,32,33,34,35,7,8,9,10,11,6,FILE1,FILE2,索引分配,索引分配能解决连续分配和链接分配存在的诸多问题。 不需要在每个分区中花费额外存储空间存储链接指针，而是利用专门的索引结点存储索引信息。 索引分配可以基于大小固定的分区,索引分配,基于数据块的分区能消除外部碎片，但索引项较多，可能使一个数据块容纳不了一个文件的所有分区的索引。 基于可变分区的索引分配可以保证文件存储空间的局部连续性，有利于提高文件访问性能，减少文件的索引项。,索引分配,周期性地合并一些可变分区成为一个较大的连续分区，进一步减少文件的索引项。 合并整理不能减少基于数据块的索

35、引项，但可以使文件的存储空间连续，提高文件访问效率。,索引分配,如果文件的索引项太多，可以建立二级索引，甚至多级索引。 索引分配同时支持顺序访问和直接访问，因而是最普遍的一种文件存储分配技术。,索引分配的优点,支持文件的直接存取。当需要存取文件的第i号分区时，可以直接从索引表中找到第i个分区的数据块号或可变分区的起始数据块号。 能满足文件的动态增长需要，只需要更新索引结点的内容，就可以把新增加的分区记录下来。 利用多级索引，可以支持大型文件的存取。,索引分配存在的问题,对于一些较小的文件，例如，仅需要几个数据块的文件，采用索引分配方案也必须为之建立一个索引表，索引节点的利用率较低。 如果文件太

36、大，建立多级索引会花费很长时间，而且需要海量存储空间。,空闲空间的管理,空闲分区表 空闲分区链表 索引 位示图,空闲分区表,将存储空间中各个空闲分区登记在一张表中，一个分区对应一个表项，并将所有空闲分区按其起始存储块号递增的次序排列，见表 :,空闲分区表,适合于可变大小分区的连续分配方式。 为文件分配存储空间时，首先顺序查找空闲分区表中的各个表项，直至找到第一个大小适合的空闲分区。 可以采用首次适应分配算法、下次适应分配算法、最佳适应分配算法等。 然后，将该分区分配给文件，同时修改空闲分区表，删除相应表项。 当删除文件释放出空间时，系统回收其存储空间，合并相邻空闲分区,空闲分区表,实现简单。对

37、于最佳适应分配算法，可以将各空闲分区按照（长度）从小到大的顺序进行排列，而非空闲分区起始块号递增的顺序排列。再利用有效的查找算法，能很快找到需要大小的空闲分区。 但是，当存储空间中的空闲分区分布较分散且数量较多时，空闲分区表将会很大。需要很大的内存空间，会降低空闲分区表的检索速度。 对于非连续存储的文件，如基于数据块的链接文件，或基于数据块的索引文件，合并空闲分区的操作并非必须，反而会影响其效率。,空闲分区链表,用专门的空闲分区表登记空闲分区信息会浪费一定的存储空间，而且不适合登记分散且数目很多的空闲分区，不利于基于存储块的链接文件和索引文件的存储空间分配。 可以通过指针将各个空闲分区连接起来

38、，并记载各空闲分区大小，称为空闲分区链表。,空闲分区链表,适合于各种文件分配方法。 如果基于存储块分配，则可以取空闲分区链的第一个存储块进行分配，并调整空闲分区链首指针和分区大小。 如果基于可变分区分配，可以采用首次适应算法，从链表头开始查找，找到的第一个适合的分区则可分配。然后，调整空闲分区链首指针和分区大小。 当删除文件释放存储空间时，系统回收其存储空间，并将回收的分区链接到空闲分区链表中。,空闲分区链表: 问题,一段时间以后，可能会使空闲分区链表中包含太多小分区，使文件分配到的存储空间过分离散。 由于空闲分区长度等信息保存在存储块中，每次将存储块分配出去写入文件数据之前，必须首先读出其中

39、的有关空闲分区信息，否则将丢失链接指针。如果一个文件需要很多空闲分区，这种操作模式将大大降低文件存储速度。,空闲分区链表: 问题,删除一个由许多离散小分区组成的文件时，将回收的小分区链接到空闲分区链表中需要很长时间。 若一个文件申请连续存储空间，则需要花费较长的时间查找相邻的空闲分区。 因此，这种空闲空间组织方法适合于非连续存储文件。,索引,将空闲分区看作文件，按文件存储空间分配方法为空闲分区建立索引。 基于可变分区建立索引比基于存储块建立索引的效率高。 索引表中为每一个空闲分区建立一个索引项，根据索引项查找空闲分区，将会提高文件存储效率。 利用索引方法管理空闲空间，适合于各种文件分配法。,位

40、示图,利用二进制位0、1表示存储空间中存储块的使用状态。空闲分区:0，已分配分区:1（或者相反）。 由所有存储块对应的位构成一个向量，称为位示图，如图,011110000111111111001111000000011111 图5.17 位示图,位示图,可以容易地找到一个或一组连续的空闲分区。 分配空闲空间时，从位示图中查找标志位为0的位，并按照某种算法换算成对应的空闲存储块号及其物理位置，并修改对应位为1。 当删除文件释放存储空间时，将释放的所有数据块逐一换算成对应的位示图位置，并将其对应的二进制位的值修改为0。,位示图,一个位示图需要占用的存储空间大小为： 磁盘容量（字节数）/ （8 *

41、数据块大小） 对于容量较小的磁盘，位示图占用的空间会很小。 但是，对于一个16GB的磁盘，若数据块大小为512字节，则位示图大小为4MB，大约需要占用8000个磁盘块的存储空间。 很难一次性将该位示图全部装入内存,位示图,即使内存足够大，可以存放全部或绝大部分位示图数据，搜索一个很大的位示图将会降低文件系统的性能。 尤其当磁盘空间快用完，剩下的空闲磁盘块很少时，文件系统的性能将严重降低。,位示图,因此，大多数使用位示图的文件系统都需要另设一个辅助数据结构，用于汇总位示图的子区域内容。 可以将位示图按逻辑结构划分为若干子区域，一个子区域表示一个连续的空闲分区。 汇总表中记载连续空闲分区的个数和连

42、续空闲分区的长度。若需要为文件分配连续空间，则首先查找汇总表，快速找到合适的子区域，再将其对应的空闲分区分配出去。,5.7 逻辑文件与物理数据块之间的转换,字节流、记录与数据块之间的转换,无结构字节流文件：由若干字节组成，其内不含任何数据结构。其中每一个字节对应一个非负整数索引号。 文件指针指向文件中某个字节的位置。 而文件在存储介质上是以数据块为存储单位，一个数据块包含若干字节。 因此，无结构字节流文件系统必须提供一个字节流与数据块之间的转换接口，简称“流块转换器”，如图5.18(a)所示。,记录流转换器,有结构文件由若干记录构成，对应的物理数据块也是由记录构成。 因此，必须通过“记录块转换

43、器”将数据块转换成记录，或将记录转换为数据块，如图5.18(b),字节流、记录与数据块之间的转换,但是，并非所有的文件系统都提供了这两个转换接口，如MS DOS 及UNIX的文件系统仅提供“流块转换器”接口，而不提供“记录块转换器”接口。它们将数据结构的定义及转换功能留给了应用程序 一些大型计算机如IBM MVS及Apple Macintosh的文件系统支持有结构文件，并提供了“记录块转换器”接口。,记录如何组成数据块,为了简化I/O操作、缓冲区及外存空间的分配和管理，操作系统通常将外存划分为固定长度的数据块。 对记录的平均长度而言，数据块的长度如何确定呢？ 数据块越大，一次I/O传输的记录就

44、越多。而且，尺寸较大的数据块适合文件的顺序访问，可以减少I/O次数，加快文件传输速度。,记录如何组成数据块,但是，如果对文件进行随机访问，或文件访问的局部性很差。那么，采用大数据块，传输的部分记录将是无用的。 另外，大数据块需要更大的I/O 缓冲区支持，会增加缓冲区的管理复杂度。 所以，设置数据块的长度，需要综合考虑I/O传输性能、I/O缓冲区的管理以及文件访问方式等多种因素。,如何将记录组织成数据块,对于固定长数据块，根据记录长度固定还是可变，以及一条记录是否可以分开存储在不同数据块中，常有三种记录组块方法： 固定组块法 可变长跨块组块法 可变长非跨块组块法,固定组块法（Fixed bloc

45、king）,数据块由若干条固定长度的记录组成，一条记录必须完整地存储在一个数据块中 数据块中可能会存在一些不能容纳一条完整记录的空间，称为内部碎片。,图5.19 （a） 固定组块,固定组块法（Fixed blocking）,固定组块方法不利于存储空间的利用。 记录长度固定的顺序文件常采用固定组块法,可变长跨块组块法 （Variable-length spanned blocking）,允许记录被划分存储在不同数据块，用指针链接一条跨块存储记录所在的两个数据块，如图5.19(b)所示。,可变长跨块组块法 （Variable-length spanned blocking）,适合于各种长度的文件。

46、但是，这种技术很难实现。 另外，采用可变长跨块组块技术时，跨块记录的读/写会引起两次I/O操作。 修改这类文件（增加或删除记录）也非常困难。,可变长非跨块组块法 （ Variable-length unspanned blocking ）,可变长跨块组块法的I/O效率较低，增加了文件修改难度。 如果不允许记录跨块存储，则可以有效解决此问题。 可变长非跨块组块法的数据块由变长记录组成，不允许一条记录跨越两个数据块存储，如图5.19(c)。,5.8 文件共享,文件共享的控制,文件共享的有效控制涉及两个方面： 同时存取（Simultaneous Access） 存取权限（Access Rights）

47、,控制同时存取,允许多个用户同时读文件内容，但不允许同时修改，或同时读且修改文件内容。 共享用户之一修改文件内容时，可以将整个文件作为临界资源，锁定整个文件，不允许其他共享用户同时读或写文件。 也可以仅仅锁定指定的一条记录，允许其他共享用户读/写该文件的其它记录。后者的并发性能更好。 控制对文件的同时存取涉及进程的同步与互斥问题,控制存取权限,控制授权用户以合法的方式访问文件，包括： 无（None） 用户不知道文件的存在。用户无法获知该文件的目录信息，当然更不会知道文件的内容。 探知（Knowledge） 用户可以检测文件的存在和文件的文件主，还可以向文件主申请增加对该文件的存取权限。 执行（

48、Execution） 用户可以装载并执行程序，但不允许拷贝程序内容。,控制存取权限,读（Reading） 允许用户读文件内容，包括拷贝和执行文件。某些系统严格地将浏览文件内容和拷贝权限分开，可以控制文件只能被浏览（显示），不能被拷贝。 追加（Appending） 允许用户向文件添加数据，通常只能将数据添加到文件尾。但是，不能修改或删除文件内容。例如，超市收银员只能将新结帐的数据添加到文件中，不允许其修改或删除已有的数据。,控制存取权限,更新（Updating） 允许用户修改、删除、增加文件内容。包括创建文件、重写文件的全部或部分内容、移动文件的全部或部分数据等操作。 更改权限 (Changin

49、g protection) 一般只有文件主才能更改共享该文件的其他用户对该文件的存取权限。有的系统允许文件主将更改文件存取权限赋予其他某个用户，但必须限制授权用户更改的权限范围。 删除 (Deletion) 允许用户删除文件,注意,以上各级存取权限具有层次结构，后一种权限包含前一种及前面各种存取权限。例如，若赋予用户对文件的更新权限，则该用户同时拥有探知、执行、读、追加权限。 文件主通常指创建文件的用户。文件主拥有以上所列的全部权限，并且还可以对下列各类用户赋予存取权限：指定用户、用户组和该系统的所有用户。,文件共享的实现,实现文件共享的实质就是可以从不同地方打开同一个文件 打开文件的首要步骤就是找到文件的目录项，读取文件在外存的起始地址。 实现文件共享的方式：利用链接目录项实现法、利用基本文件目录实现法、利用索引节点实现法以及