操作系统第七章

1、 在现代计算机系统中在现代计算机系统中, ,要用到大量的程序和数据要用到大量的程序和数据, ,由于内存容量有限由于内存容量有限, ,又不能长期保存又不能长期保存, ,故平时总是把它故平时总是把它们以文件的形式存放在外存中们以文件的形式存放在外存中, ,需要时可随时将它们调需要时可随时将它们调入内存入内存. . 但是这些外存文件由用户管理不仅非常困难也不但是这些外存文件由用户管理不仅非常困难也不现实现实. .必须由操作系统管理必须由操作系统管理. .所以在操作系统中增加了所以在操作系统中增加了文件系统文件系统. . 信息是计算机系统中的重要资源信息是计算机系统中的重要资源, ,文件系统文件系统是

2、操作系统中的一个重要组成部分是操作系统中的一个重要组成部分. . 是负责信息是负责信息的组织、存储和访问。的组织、存储和访问。 文件系统的功能就是提供高效、快速和方便文件系统的功能就是提供高效、快速和方便的信息存储和访问功能。本章的主要内容就是信的信息存储和访问功能。本章的主要内容就是信息的组织。息的组织。 本章主要内容本章主要内容: 文件和文件系统文件和文件系统 文件逻辑机构文件逻辑机构 目录管理目录管理 文件共享文件共享 文件保护文件保护 7.1.1 文件、记录和数据项文件、记录和数据项 文件管理系统是指文件和对文件进行操文件管理系统是指文件和对文件进行操纵和管理的软件集合纵和管理的软件集

3、合. (1)数据项数据项: 基本数据项基本数据项:用于描述一个对象的某种属用于描述一个对象的某种属性的字符集合性的字符集合. 组合数据项组合数据项:若干个基本数据项组成若干个基本数据项组成.(2)记录记录: 记录是一组相关数据项的集合。用于描述一个对象某记录是一组相关数据项的集合。用于描述一个对象某方面的属性方面的属性.(3)文件文件: 文件是由创建者所定义，具有文件名的一组相关信息文件是由创建者所定义，具有文件名的一组相关信息的集合的集合.可分为有结构文件和无结构文件。可分为有结构文件和无结构文件。 用户观点：用户观点： 文件系统如何呈现在其面前：一个文件有什么组成，文件系统如何呈现在其面前

4、：一个文件有什么组成，如何命名，如何保护文件，可以进行何种操作等等。如何命名，如何保护文件，可以进行何种操作等等。 操作系统观点：操作系统观点： 文件目录怎样实现，怎样管理存储空间，文件存储文件目录怎样实现，怎样管理存储空间，文件存储位置，磁盘实际运作方式位置，磁盘实际运作方式(与设备管理的接口与设备管理的接口)等等。等等。数据项数据项n 数据项数据项2 数据项数据项1 记录记录n 记录记录2记录记录1文件文件 文件、记录和数据项间的层次关系文件、记录和数据项间的层次关系: 文件的除了有文件名之外，还具有文件属性文件的除了有文件名之外，还具有文件属性: 文件类型：从不同角度来规定文件的类型文件

5、类型：从不同角度来规定文件的类型; 文件长度：单位可以是字节、字或块文件长度：单位可以是字节、字或块,也可以是最大允许也可以是最大允许长度；长度； 文件的物理位置：用于指示文件在哪一个设备上及在该文件的物理位置：用于指示文件在哪一个设备上及在该设备的哪个位置设备的哪个位置; 文件的存取控制：文件的读、写、执行权限文件的存取控制：文件的读、写、执行权限; 文件的建立时间：创建文件的时间文件的建立时间：创建文件的时间; 文件的修改时间：修改文件的时间。文件的修改时间：修改文件的时间。1 1 文件名和扩展名文件名和扩展名 （1 1）文件名。）文件名。在不同的系统之间，对文件名的规定是不同的，在在不同

6、的系统之间，对文件名的规定是不同的，在一些老的系统中，名字的长度还会受到限制。一些老的系统中，名字的长度还会受到限制。 （2 2）扩展名。）扩展名。扩展名是添加在文件名后面的若干个附加字符，又扩展名是添加在文件名后面的若干个附加字符，又称为后缀名，用于指示文件的类型。称为后缀名，用于指示文件的类型。2 2 文件类型文件类型（1 1）按用途分类）按用途分类 系统文件：由系统软件构成的文件系统文件：由系统软件构成的文件. .有的系统文件只有的系统文件只允许用户读允许用户读, ,不能修改。有的系统文件不对用户开放不能修改。有的系统文件不对用户开放. . 用户文件：由用户的源代码、可执行文件或数据等用

7、户文件：由用户的源代码、可执行文件或数据等所构成的文件所构成的文件. .允许用户调用允许用户调用, ,但不能修改但不能修改. . 库文件：由标准子程序及常用应用程序组成文件，库文件：由标准子程序及常用应用程序组成文件，允许用户使用但不能修改。允许用户使用但不能修改。（2）按文件中的数据形式分类）按文件中的数据形式分类源文件：由源程序和数据构成的文件。源文件：由源程序和数据构成的文件。目标文件：把源程序经过相应语言的编译程序编译，但目标文件：把源程序经过相应语言的编译程序编译，但尚未经过链接程序链接的目标代码所形成的文件。尚未经过链接程序链接的目标代码所形成的文件。可执行文件：经编译后所产生的目

8、标代码，再由链接程可执行文件：经编译后所产生的目标代码，再由链接程序链接后形成的文件。序链接后形成的文件。（3）按存取控制属性分类）按存取控制属性分类只执行文件：只允许被核准的用户调用执行，既不允许读，只执行文件：只允许被核准的用户调用执行，既不允许读，更不允许写。更不允许写。只读文件：只允许文件主及被核准的用户去读，但不允许只读文件：只允许文件主及被核准的用户去读，但不允许写。写。读写文件：允许文件主和被核准的用户去读文件和写文件。读写文件：允许文件主和被核准的用户去读文件和写文件。(4)按文件的逻辑结构分类按文件的逻辑结构分类有结构文件有结构文件:由若干个记录所构成由若干个记录所构成,故又

9、称为记录式文件故又称为记录式文件.根据记录的长度分为定长记录文件和可变长记录文根据记录的长度分为定长记录文件和可变长记录文件件.无结构文件（流式文件）无结构文件（流式文件）:这是直接由字符序列构成的文这是直接由字符序列构成的文件件,故又称为流式文件故又称为流式文件.可以把流式文件看成是记录式可以把流式文件看成是记录式文件的特例文件的特例,即其每个记录中只含有一个字符即其每个记录中只含有一个字符.(5)(5)按文件的物理结构分类按文件的物理结构分类: :顺序文件顺序文件: :指把逻辑文件中的记录顺序地存储到连续地物指把逻辑文件中的记录顺序地存储到连续地物理盘块中理盘块中, ,这样顺序文件中所有记

10、录的次序这样顺序文件中所有记录的次序, ,与它们在介质与它们在介质上存放的次序是一致的上存放的次序是一致的. .链接文件链接文件: :指文件中的各个记录可以存放在不相邻的各个指文件中的各个记录可以存放在不相邻的各个物理盘块中物理盘块中, ,通过物理块中的链接指针将它们连接成一个链通过物理块中的链接指针将它们连接成一个链表表. .索引文件索引文件: :指文件中的各个记录可存储在不相邻的各个物指文件中的各个记录可存储在不相邻的各个物理块中理块中, ,如同分区存储管理一样如同分区存储管理一样, ,需为每个文件建立一张所需为每个文件建立一张所引表引表, ,来实现记录和物理块之间的映射来实现记录和物理块

11、之间的映射. .在索引表中为每个在索引表中为每个记录设置一个表项记录设置一个表项, ,其中存放该记录的记录号极其所在的物其中存放该记录的记录号极其所在的物理块号理块号. .文文 件件 系系 统统 接接 口口逻逻 辑辑 文文 件件 系系 统统基本基本I/O管理程序（文件组织模块）管理程序（文件组织模块）基本文件系统（物理基本文件系统（物理I/O层）层）I/O控制层（设备驱动程序）控制层（设备驱动程序）对对 象象 及及 其其 属属 性性 说说 明明对对象操纵对对象操纵和管理的软和管理的软件集合件集合 文件系统是操作系统的重要组成部分文件系统是操作系统的重要组成部分,所谓文所谓文件系统是指含有大量的

12、文件极其属性的说明件系统是指含有大量的文件极其属性的说明,对文对文件进行操作和管理的软件件进行操作和管理的软件,以及向用户提供的使用以及向用户提供的使用文件的接口等的集合文件的接口等的集合. 文件系统的模型文件系统的模型:7.1.37.1.3文件系统的层次结构文件系统的层次结构(1)对象极其属性说明对象极其属性说明:文件：文件是文件系统管理的直接对象文件：文件是文件系统管理的直接对象.目录目录:为了方便用户对文件的检索和存取为了方便用户对文件的检索和存取,在文件系统中必须在文件系统中必须配置目录配置目录.在目录中除包含文件名外在目录中除包含文件名外,号包含文件属性说号包含文件属性说明明.对目录

13、的组织和管理对目录的组织和管理,是方便用户和提高文件存取速是方便用户和提高文件存取速度的关键度的关键.磁盘磁盘(磁带磁带)存储空间存储空间:文件和目录必定占据存储空间文件和目录必定占据存储空间,对这部对这部分存储空间的有效管理分存储空间的有效管理,不仅能提高外存的利用率不仅能提高外存的利用率,而且而且能加速对文件的存取能加速对文件的存取.(2)对对象操纵和管理软件集合对对象操纵和管理软件集合: 软件集合是文件系统的核心软件集合是文件系统的核心,文件系统的大部分功能都是在文件系统的大部分功能都是在这一层上实现的这一层上实现的.其功能有其功能有:对文件存储空间的管理对文件存储空间的管理;对文件目录

14、的管理对文件目录的管理;地址映射地址映射;文件的读写管理文件的读写管理;文件的共享与保护文件的共享与保护. 在这些功能的实现中在这些功能的实现中,通常又进一步划分成几个层次通常又进一步划分成几个层次:I/O控制层控制层:最低层最低层,主要由磁盘驱动程序和磁带驱动程序组成主要由磁盘驱动程序和磁带驱动程序组成.故又称为设备驱动层故又称为设备驱动层. 基本文件系统基本文件系统: :又称为物理又称为物理I/OI/O层层. .该层主要用该层主要用于处理内存与磁盘或磁带机系统之间数据块的交于处理内存与磁盘或磁带机系统之间数据块的交换换. .基本文件系统无需了解所传送的数据块的内基本文件系统无需了解所传送的

15、数据块的内容或文件的结构容或文件的结构. . 基本基本I/OI/O管理程序管理程序: :又称为文件组织模块又称为文件组织模块. .该层该层完成与磁盘完成与磁盘I/OI/O有关的大量事务有关的大量事务, ,有有: :要选择文件所在的设备要选择文件所在的设备; ;进行文件逻辑块号到物理块号的转换进行文件逻辑块号到物理块号的转换; ;空隙盘块的管理空隙盘块的管理; ;I/OI/O缓冲区的指定缓冲区的指定; ; 逻辑文件系统逻辑文件系统. .(3)(3)文件系统的接口文件系统的接口: : 文件系统向用户提供两种接口文件系统向用户提供两种接口: : 命令接口命令接口; ; 程序接口程序接口. . 7.1

16、.4 7.1.4 文件操作文件操作(1)(1)最基本的文件操作最基本的文件操作: : 创建文件创建文件; ; 删除文件删除文件; ; 读文件读文件; ; 写文件写文件; ;设置文件的读设置文件的读/ /写位置写位置. .(2)(2)文件的文件的“打开打开”和和“关闭关闭”: :“打开打开”：指系统将指名文件的属性（包括该文件在：指系统将指名文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存中的一个打开外存上的物理位置）从外存拷贝到内存中的一个打开文件表的表目中。并将该表目的编号（或称为索引）文件表的表目中。并将该表目的编号（或称为索引）返回给用户。返回给用户。“关闭关闭”：将打开的文件

17、从打开文件表的表目中删除：将打开的文件从打开文件表的表目中删除掉。掉。（3 3）其它文件操作：）其它文件操作：对文件属性的操作；对文件属性的操作；对文件有关的目录的操作：创建目录，删除目录等。对文件有关的目录的操作：创建目录，删除目录等。 文件的逻辑结构：从用户观点出发所观察到的文件的组织文件的逻辑结构：从用户观点出发所观察到的文件的组织形式，是用户可以直接处理的数据及其结构，独立于文件形式，是用户可以直接处理的数据及其结构，独立于文件的物理特性。又称为文件组织。的物理特性。又称为文件组织。 文件的物理结构：又称为文件的存储结构。指文件在外存文件的物理结构：又称为文件的存储结构。指文件在外存上

18、的存储组织形式。不仅与存储介质的存储性能有关，而上的存储组织形式。不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。且与所采用的外存分配方式有关。 文件逻辑结构的设计要求：文件逻辑结构的设计要求： 访问性能：便于检索；便于修改访问性能：便于检索；便于修改; 存储性能：向物理存储转换方便，节省空间存储性能：向物理存储转换方便，节省空间; 文件的不同组织层次：域、记录、文件文件的不同组织层次：域、记录、文件.1 1 按文件是否有结构分类按文件是否有结构分类(1)(1)有结构文件有结构文件 在记录式文件中，所有的记录通常都是描述在记录式文件中，所有的记录通常都是描述一个实体集的，有着相同

19、或不同数目的数据项，一个实体集的，有着相同或不同数目的数据项，记录的长度可分为定长和不定长两类。记录的长度可分为定长和不定长两类。 另外根据用户和系统管理的需要可采用多种另外根据用户和系统管理的需要可采用多种方式来组织这些记录方式来组织这些记录, ,形成形成: : 顺序文件顺序文件: :一系列记录按照某种顺序排列所形成一系列记录按照某种顺序排列所形成的文件的文件, ,记录通常是定长的记录通常是定长的. . 索引文件索引文件: :记录可变长记录可变长; ; 索引顺序文件索引顺序文件: :既有索引表又为每一组记录中的既有索引表又为每一组记录中的第一个记录设置一表项第一个记录设置一表项. .(2)(

20、2)无结构文件无结构文件 文件体为字节流，不划分记录，顺序访问，文件体为字节流，不划分记录，顺序访问，每次读写访问可以指定任意数据长度。当前操作每次读写访问可以指定任意数据长度。当前操作系统中常用的文件组织。系统中常用的文件组织。 如如:大量的源程序大量的源程序; 库函数库函数. 在在UNIX系统中所有的文件都被看成流式文系统中所有的文件都被看成流式文件件.系统不对文件进行格式处理系统不对文件进行格式处理. 2 按文件的组织方式分类按文件的组织方式分类 （1）顺序文件：指由一系列记录按某种顺序）顺序文件：指由一系列记录按某种顺序排列所形成的文件。排列所形成的文件。 （2）索引文件：指为可变长记

21、录文件建立一）索引文件：指为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对张索引表，为每个记录设置一个表项，以加速对记录的检索速度。记录的检索速度。 （3）索引顺序文件：这是顺序文件和索引文）索引顺序文件：这是顺序文件和索引文件相结合的产物，在为每个文件建立一张索引表件相结合的产物，在为每个文件建立一张索引表时，并不是为每个记录建立一个索引表项，而是时，并不是为每个记录建立一个索引表项，而是为一组记录中的第一个记录建立索引表项。为一组记录中的第一个记录建立索引表项。 文件体为大小相同的排序记录序列。文件体为大小相同的排序记录序列。 它由一个主文件和一个临时文件组成。它由一个主文

22、件和一个临时文件组成。 记录大小相同，按某个关键字域记录大小相同，按某个关键字域(key (key field)field)排序，存放在主文件排序，存放在主文件(master file)(master file)中。中。新记录暂时保存在日志或事务文件新记录暂时保存在日志或事务文件(log file (log file or transaction file)or transaction file)中，定期归并入主文中，定期归并入主文件。件。(1)(1)顺序文件的排序方式顺序文件的排序方式串结构：按存入时间的先后排列。串结构：按存入时间的先后排列。顺序结构：文件中的所有记录按关键字排列。顺序结构

23、：文件中的所有记录按关键字排列。 对顺序结构文件有更高的检索效率对顺序结构文件有更高的检索效率. . 因为在检索串结构文件时因为在检索串结构文件时, ,每次都必须从头每次都必须从头开始开始. .逐个记录查找逐个记录查找, ,直到找到指定记录或查完直到找到指定记录或查完所有的记录为止所有的记录为止. .而对顺序结构文件而对顺序结构文件, ,可利用某可利用某种有效的查找算法种有效的查找算法, ,如折半查找法、插值查找法、如折半查找法、插值查找法、跳步查找法等方法来提高检索效率跳步查找法等方法来提高检索效率. .(2)(2)顺序文件的优缺点顺序文件的优缺点优点优点: : 简单简单; ; 支持顺序存取

24、和随机存取支持顺序存取和随机存取; ; 顺序存取速度快顺序存取速度快; ; 所需的磁盘寻道次数和寻道时间最少所需的磁盘寻道次数和寻道时间最少. .缺点缺点: : 文件不能动态增长文件不能动态增长, ,预留空间预留空间, ,浪费浪费; ;重新分配和移动重新分配和移动; ;不利于文件插入和删除不利于文件插入和删除; ;外部碎片问题外部碎片问题, ,存储压缩技术存储压缩技术. . 为了访问顺序文件中的一条记录，首先为了访问顺序文件中的一条记录，首先应找到该记录的地址。应找到该记录的地址。 查找记录地址的方法有：查找记录地址的方法有：隐式寻址方式隐式寻址方式显式寻址方式显式寻址方式R0R1I0I1Ii

25、R2R3RiR0R1RiRptrRptrllllll 0l 1l i0l2l3l4li l(i+1) l0l 0+1l 0+l 1+2(l k+1)(l k+1)K=0K=0ii - 1 定长记录文件；定长记录文件； 变长记录文件变长记录文件 隐式寻址方式隐式寻址方式 顺序文件中的记录可以是定长的，也可以是顺序文件中的记录可以是定长的，也可以是变长的变长的. . 对于定长记录的顺序文件，如果已知当前记对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑录的逻辑地址，便很容易确定下一个记录的逻辑地址。地址。 在读一个文件时，可设置一个读指针在读一个文件时，可设置一个读

26、指针Rptr，令它指向下一个记录的首地址，每当读完一个记令它指向下一个记录的首地址，每当读完一个记录时，便执行录时，便执行: Rptr ：= Rptr + l操作，使之指向下一个记录的首地址。操作，使之指向下一个记录的首地址。 在写一个文件时，也应设置一写指针在写一个文件时，也应设置一写指针Wptr，使之指向要写的记录的首地址。同样，在每写完使之指向要写的记录的首地址。同样，在每写完一个记录时，又执行以下操作：一个记录时，又执行以下操作： Wptr ：= Wptr + 1 记录大小不必相同，不必排序，存放在主文件记录大小不必相同，不必排序，存放在主文件(primary file)(primar

27、y file)中。索引文件与索引顺序文件的区中。索引文件与索引顺序文件的区别在于主文件不排序。另外建立索引，每个索引项别在于主文件不排序。另外建立索引，每个索引项指向一个记录，索引项按照记录中的某个关键字域指向一个记录，索引项按照记录中的某个关键字域排序。对同一主文件，可以针对不同的关键字域相排序。对同一主文件，可以针对不同的关键字域相应建立多个索引。索引文件的记录项通常较小，查应建立多个索引。索引文件的记录项通常较小，查找速度快，便于随机访问找速度快，便于随机访问(random access)(random access)。(1)(1)索引文件的优缺点索引文件的优缺点 优点：优点： 保持了链

28、接结构的优点保持了链接结构的优点, ,又解决了其缺点：又解决了其缺点： 既能顺序存取既能顺序存取, ,又能随机存取又能随机存取; ; 满足了文件动态增长、插入删除的要求满足了文件动态增长、插入删除的要求; ; 能充分利用外存空间。能充分利用外存空间。 缺点缺点: : 较多的寻道次数和寻道时间较多的寻道次数和寻道时间 索引表本身带来了系统开销索引表本身带来了系统开销; ; 内外存空间内外存空间, ,存取时间。存取时间。(2)索引表组织索引表组织链接模式链接模式: 一个盘块一个索引表，多个索引表链接起来一个盘块一个索引表，多个索引表链接起来.多级索引多级索引: 将一个大文件的所有索引表（二级索引将

29、一个大文件的所有索引表（二级索引)的地址的地址放在另一个索引表（一级索引放在另一个索引表（一级索引)中中.综合模式综合模式: : UNIX UNIX文件系统采用的是多级索引结构文件系统采用的是多级索引结构( (综合模式综合模式) )。每个文件的索引表为每个文件的索引表为1313个索引项，每项个索引项，每项2 2个字节。最前个字节。最前面面1010项直接登记存放文件信息的物理块号（直接寻项直接登记存放文件信息的物理块号（直接寻址）。址）。 如果文件大于如果文件大于1010块，则利用第块，则利用第1111项指向一个物理项指向一个物理块，该块中最多可放块，该块中最多可放256256个存放文件物理块的

30、块号（一个存放文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第次间接寻址）。对于更大的文件还可利用第1212和第和第1313项作为二次和三次间接寻址。项作为二次和三次间接寻址。 UNIXUNIX中采用了三级索引结构后，文件最大可达中采用了三级索引结构后，文件最大可达1616兆个物理块。兆个物理块。索引号01m1m0指针ptr长度mimiR0R1Ri.索引表索引表逻辑文件逻辑文件索引文件的组织索引文件的组织:1 1 索引顺序文件的特征索引顺序文件的特征 是顺序文件和索引文件相结合的产物是顺序文件和索引文件相结合的产物. .在在顺序文件（主文件顺序文件（主文件main filemain

31、file）的基础上，另）的基础上，另外建立索引外建立索引(index)(index)和溢出文件和溢出文件(overflow (overflow file)file)。这样做的目的是加快顺序文件的检索。这样做的目的是加快顺序文件的检索速度。速度。 在索引文件中，可将关键字域中的取值划在索引文件中，可将关键字域中的取值划分若干个区间（如分若干个区间（如AZAZ可以划分为可以划分为A A到到Z Z共共2626个个区间），每个区间对应一个索引项，后者指向区间），每个区间对应一个索引项，后者指向该区间的开头记录。新记录暂时保存在溢出文该区间的开头记录。新记录暂时保存在溢出文件中，定期归并入主文件。件中，

32、定期归并入主文件。关键字逻辑地址姓名其它属性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件顺序文件2 一级索引顺序文件一级索引顺序文件:3 3 多级索引顺序文件多级索引顺序文件 通过划分层次，在记录数量较大时，比通过划分层次，在记录数量较大时，比顺序文件大大缩短检索时间。顺序文件是顺序文件大大缩短检索时间。顺序文件是N/2(N/2(这时可使用折半查找这时可使用折半查找) )，而索引顺序文件，而索引顺序文件（一级索引）是（一级索引）是i/2 + N/(2i/2 + N/(2* *i)i)，其中，其中i i为索为索引长度。索引还可以是多级的。

33、如：有引长度。索引还可以是多级的。如：有1000,0001000,000条记录的顺序文件的平均检索长度条记录的顺序文件的平均检索长度为为500,000500,000，而在添加一个有，而在添加一个有10001000条索引项条索引项的索引文件后，平均检索长度为的索引文件后，平均检索长度为10001000。1 1 直接文件直接文件 采用前面几种文件结构对记录进行存取时，采用前面几种文件结构对记录进行存取时，都必须用给定的记录键值，先对线性表或链表都必须用给定的记录键值，先对线性表或链表进行检索，以找到指定记录的物理地址。进行检索，以找到指定记录的物理地址。 然而对于直接文件，则可根据给定的关键然而对

34、于直接文件，则可根据给定的关键字直接获得指定记录的物理地址。字直接获得指定记录的物理地址。1 1 哈希文件哈希文件 这是目前应用最为广泛的一种直接文件。这是目前应用最为广泛的一种直接文件。它利用它利用HashHash函数（散列函数）可将关键字转换函数（散列函数）可将关键字转换为相应记录的地址。为相应记录的地址。6.3 6.3 外存分配方法外存分配方法6.3.1 6.3.1 连续分配连续分配6.3.2 6.3.2 链接分配链接分配 6.3.3 6.3.3 索引分配索引分配 文件目录是一种数据结构，用于标识系统中的文件目录是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。文件及其物理

35、地址，供检索时使用。 目录是由文件说明索引组成的用于文件检索的目录是由文件说明索引组成的用于文件检索的特殊文件。文件目录的内容主要是文件访问的控制特殊文件。文件目录的内容主要是文件访问的控制信息（不包括文件内容）。目录管理是指目录访问信息（不包括文件内容）。目录管理是指目录访问和目录属性控制。和目录属性控制。 文件目录具有将文件名转换为该文件在外存文件目录具有将文件名转换为该文件在外存的物理位置的功能，这也正是文件目录所提供的的物理位置的功能，这也正是文件目录所提供的最基本的功能。对文件目录的管理有以下要求：最基本的功能。对文件目录的管理有以下要求： 实现实现“按名存取按名存取“； 提高对目录

36、的检索速；提高对目录的检索速； 文件共享；文件共享； 允许文件重名。允许文件重名。 1 文件控制块（文件控制块（FCB） 文件控制块是操作系统为管理文件而设置的文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信数据结构，存放了为管理文件所需的所有有关信息。息。 文件控制块是文件存在的标志。文件控制块是文件存在的标志。 文件控制块的内容：文件控制块的内容： 基本信息：文件名，文件物理位置，文件逻辑结构，文基本信息：文件名，文件物理位置，文件逻辑结构，文件物理结构。件物理结构。 存取控制信息：文件主的存取权限、核准用户的存取权存取控制信息：文件主的存取权限、核准用户的

37、存取权限及一般用户的存取权限。限及一般用户的存取权限。 使用信息：文件的建立日期和时间，文件最后修改日期使用信息：文件的建立日期和时间，文件最后修改日期和时间和当前使用信息（如已经打开文件的进程数据，和时间和当前使用信息（如已经打开文件的进程数据，是否会被其它进程锁住等）。是否会被其它进程锁住等）。文件名文件名扩展名扩展名属属 性性备备 用用时时 间间日日 期期第一块号第一块号盘块数盘块数MS-DOS的文件控制块的文件控制块 2 2 索引结点索引结点 索引结点的引入索引结点的引入: : 在有些系统中如在有些系统中如UNIXUNIX系统，把文件描述信息单独形系统，把文件描述信息单独形成一个称为索

38、引结点的数据结构，简称为成一个称为索引结点的数据结构，简称为i i结点；而在结点；而在文件目录的每个目录项，则仅由文件名及指向该文件文件目录的每个目录项，则仅由文件名及指向该文件所对应的所对应的i i结点的指针所构成。结点的指针所构成。文件名文件名1文件名2索引结点编号UNIX的文件目录磁盘索引结点主要内容包括：磁盘索引结点主要内容包括： 文件主标识、文件类型、文件存取权限、文件物文件主标识、文件类型、文件存取权限、文件物理地址、文件长度、文件连接计数和文件存取时间。理地址、文件长度、文件连接计数和文件存取时间。内存索引结点主要内容包括：内存索引结点主要内容包括： 索引结点编号、状态、访问计数

39、、文件所在设备索引结点编号、状态、访问计数、文件所在设备的逻辑设备号和链接指针。的逻辑设备号和链接指针。 1. 1.单级目录结构（一级目录结构）：单级目录结构（一级目录结构）： 整个目录组织是一个线性结构，系统中的所有文整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系件都建立在一张目录表中。它主要用于单用户操作系统。统。优点优点: : 简单，易实现简单，易实现. .缺点缺点: : 限制了用户对文件的命名，不允许文件重名限制了用户对文件的命名，不允许文件重名; ; 文件平均检索时间长文件平均检索时间长; ; 限制了对文件的共享限制了对文件的共享. .文件名

40、状态位物理地址文件其它属性AlphaReportText单级目录单级目录: : 2. 2.两级目录结构：两级目录结构： 在根目录下，每个用户对应一个目录（第二级目在根目录下，每个用户对应一个目录（第二级目录）；在用户目录下是该用户的文件，而不再有下级录）；在用户目录下是该用户的文件，而不再有下级目录。适用于多用户系统，各用户可有自己的专用目目录。适用于多用户系统，各用户可有自己的专用目录。录。 为改变一级目录文件目录命名冲突，并提高对目为改变一级目录文件目录命名冲突，并提高对目录文件检索速度而改进。录文件检索速度而改进。目录分为两级：目录分为两级： 一级称为主文件目录，给出用户名，用户子目录一

41、级称为主文件目录，给出用户名，用户子目录所在的物理位置；所在的物理位置； 二级称为用户文件目录（又称用户子目录），给二级称为用户文件目录（又称用户子目录），给出该用户所有文件的出该用户所有文件的FCBFCB。 优点：优点： 提高了检索目录的速度；提高了检索目录的速度； 在不同的用户目录中，可以使用相同文件名，只要在不同的用户目录中，可以使用相同文件名，只要在用户自己的在用户自己的UFDUFD中其文件名都是唯一的；中其文件名都是唯一的； 不同用户还可使用不同的文件名，来访问系统中的不同用户还可使用不同的文件名，来访问系统中的同一个共享文件。同一个共享文件。 缺点：增加了系统开销缺点：增加了系统开

42、销. .用户名WangZhangGaoAophaTestReportTestBetaDeviceMisx指向子目录指针Wang用户目录Zhang用户目录Gao用户目录AlphaTestTestReportBeta DeviceMisx两极目录结构两极目录结构 3 3 多级目录结构多级目录结构 或称为树状目录或称为树状目录(tree-like)(tree-like)。在文件数目较多时，。在文件数目较多时，便于系统和用户将文件分散管理。适用于较大的文件便于系统和用户将文件分散管理。适用于较大的文件系统管理。目录级别太多时，会增加路径检索时间。系统管理。目录级别太多时，会增加路径检索时间。通常把包括

43、三级在内的三级以上的文件目录结构称为通常把包括三级在内的三级以上的文件目录结构称为树型结构的目录树型结构的目录. .目录名：可以修改。目录名：可以修改。目录树：中间结点是目录，叶子结点是目录或文件。目录树：中间结点是目录，叶子结点是目录或文件。目录的上下级关系：目录的上下级关系： 当前目录当前目录(current directory, working directory)(current directory, working directory)； 父目录父目录(parent directory)(parent directory)； 子目录子目录(subdirectory)(subdirec

44、tory)； 根目录根目录(root directory)(root directory)等等. . 路径路径(path)(path)： 每个目录或文件，可以由根目录开始依次经由的每个目录或文件，可以由根目录开始依次经由的各级目录名，加上最终的目录名或文件名来表示各级目录名，加上最终的目录名或文件名来表示. . 优点：优点： 层次结构清晰，便于管理和保护层次结构清晰，便于管理和保护, ,解决重名问题解决重名问题, ,查找速度加快查找速度加快. . 缺点：缺点： 查找一个文件按路径名逐层检查，由于每个文件查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度。都放在外存，多次访盘

45、影响速度。ABC根目录EPABDFEDBGAEHIJKABCDELMNA 改进的多级目录：改进的多级目录： 为了提高目录检索速度，可把目录中的文件说明（文件为了提高目录检索速度，可把目录中的文件说明（文件描述符）信息分成两个部分：描述符）信息分成两个部分： 符号文件目录：符号文件目录： 由文件名和文件内部标识组成的树状结构，按文件名由文件名和文件内部标识组成的树状结构，按文件名排序排序. . 基本文件目录（索引节点目录）：基本文件目录（索引节点目录）： 由其余文件说明信息组成的线性结构，按文件内部标由其余文件说明信息组成的线性结构，按文件内部标识排序识排序. .1内部名ID其它信息地址2345

46、67891011基本文件目录(ID1)ID4ID5ID7ID9ID10ID11文件名ID3Tu-Lide8Tu-Qi根目录(ID2)文件名ID7Products5RoomsTu-Lide的目录(ID3)4Software6Tools文件名IDTools的目录(ID6)11SA-SD10Univer文件名ID10Univer5ClassroomTu-Lide的目录(ID3)9Tools基本文件目录基本文件目录:Tu-Lide的目录(ID3)ProductsRoomsSoftwareTools根目录(ID2)Tu-LideTu-QiTu-Lide的目录(ID8)UniverClassroomToo

47、lsTools的目录(ID6)SA-SDUniverID4ID5ID7ID9ID10ID11符号文件目录的层次结构符号文件目录的层次结构:对目录进行查询的方式：对目录进行查询的方式： 线性检索法和线性检索法和Hash方法方法线性检索法：线性检索法： 又称为顺序检索法，在单级目录中，利用用又称为顺序检索法，在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录户提供的文件名，用顺序查找法直接从文件目录表中找到指名文件的目录项。在树型目录中，用表中找到指名文件的目录项。在树型目录中，用户提供的文件名是由多个文件分量名组成的路径户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进

48、行查找。名，此时须对多级目录进行查找。114791468bal bindev496libetcusrtmp6119305126452666492176081132astjimerikdicksrcminixmboxbooksgrants 根目录结点6是/usr的目录132#块是/usr的目录结点26是/usr/ast目录496#块是/usr/ast目录在结点6中查找usr字段查找查找/usr/ast/mbox/usr/ast/mbox的步骤的步骤: :HashHash方法：方法： 如果建立了一张如果建立了一张 HashHash索引目录，利用索引目录，利用HashHash方法进行查方法进行查询。

49、询。 系统利用用户提供的文件名并将它变换为文件目录的系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找，将显著的提高索引值，再利用该索引值到目录中去查找，将显著的提高检索速度。检索速度。 在进行文件名转换时，可能把不同的文件名转换为相在进行文件名转换时，可能把不同的文件名转换为相同的同的HashHash值，解决此问题的方法是：值，解决此问题的方法是： 在利用在利用HashHash法索引查找目录时，如果目录表中相应的目录法索引查找目录时，如果目录表中相应的目录项是空的，表示系统中并无指定文件；项是空的，表示系统中并无指定文件； 如果目录表项中的文件名与指定文件名相

50、匹配，表示该目如果目录表项中的文件名与指定文件名相匹配，表示该目录项正式所要寻找的文件所对应的目录项，可以从中找到录项正式所要寻找的文件所对应的目录项，可以从中找到该文件的物理地址；该文件的物理地址； 如果在目录表项中的文件名与指定文件名不匹配，表示发如果在目录表项中的文件名与指定文件名不匹配，表示发生了冲突，此时需将生了冲突，此时需将HashHash值再加上一个常数（该常数应与值再加上一个常数（该常数应与目录的长度值互质），形成新的索引值，再返回到第一步目录的长度值互质），形成新的索引值，再返回到第一步重新开始查找。重新开始查找。 定义定义: : 一个文件被多个用户或程序使用。一个文件被多个

51、用户或程序使用。 目的：目的： 节省时间和存储空间，减少了用户节省时间和存储空间，减少了用户 工作量；进程间通过文件交换信息。工作量；进程间通过文件交换信息。 绕弯路法绕弯路法: :早期的早期的MULTICSMULTICS等操作系统中所采用的一种等操作系统中所采用的一种共享文件方法共享文件方法. .该方法中该方法中, ,允许用户获得一个允许用户获得一个“当前目当前目录录”. .用户所访问的所有文件都是相对于当前目录用户所访问的所有文件都是相对于当前目录; ; 当所访问的文件不在其当前目录下时当所访问的文件不在其当前目录下时, ,可以通过可以通过“向上走向上走”的方式去访问其上级目录的方式去访问

52、其上级目录. .为此用为此用“* *”表表示一个目录的父目录示一个目录的父目录. .假定当前目录为假定当前目录为F,F,若用户要访问若用户要访问E E的文件的文件J,J,可利用路径名可利用路径名* *.E.J,.E.J,还可以利用还可以利用* *. .* *.C.A.C.A来来访问文件访问文件, ,缺点：路径绕弯缺点：路径绕弯; ; 文件文件n,n,文件文件1 1：不同的文件名可以：不同的文件名可以 访问该文件。访问该文件。 连访法连访法: :在目录项之间进行链接在目录项之间进行链接. .一个目录中的目录项一个目录中的目录项直接指向另一目录中的目录项直接指向另一目录中的目录项. .在连访法实现

53、文件共享在连访法实现文件共享时时, ,应在文件说明中增加一连访属性应在文件说明中增加一连访属性, ,以指示文件说明以指示文件说明中的物理地址是一指向文件或共享文件的目录项的指中的物理地址是一指向文件或共享文件的目录项的指针针, ,应包括共享该文件的应包括共享该文件的“用户计数用户计数”, ,用于表示共有用于表示共有多少用户需要使用此文件多少用户需要使用此文件, ,仅当已无用户再需要此文件仅当已无用户再需要此文件时才可将此共享文件撤消时才可将此共享文件撤消. . 缺点：（缺点：（1 1）增加了连访属性）增加了连访属性 （2 2）增加）增加“用户计数用户计数” （3 3）文件）文件n,n,文件文件

54、1 1：不同的文件名可以：不同的文件名可以 访问该访问该文件。文件。 利用基本文件目录实现文件共享利用基本文件目录实现文件共享: : 在文件系统中设置一个基本目录，每在文件系统中设置一个基本目录，每个文件在该目录中均占有一个目录项，用个文件在该目录中均占有一个目录项，用于给出系统赋予的、对应于该文件名的唯于给出系统赋予的、对应于该文件名的唯一标识符（整数），以及该文件的有关说一标识符（整数），以及该文件的有关说明信息。明信息。0123456789Wang3Zhang1MistAlphaReportOaf7689空闲文件目录ID物理位置主文件目录MFD符号名 IDSqrtBeta56符号名 ID

55、符号名 ID主目录MFDZhang的SFDSqrt Wang的Beta Zhang的AlphaMistReportOafWang的SFD基本文件目录利用基本文件目录实现文件共享利用基本文件目录实现文件共享: 将诸如文件的物理地址及其它的文件属性等信息将诸如文件的物理地址及其它的文件属性等信息放在索引结点中。在文件目录中只设置文件名及指向放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针相应索引结点的指针.Test rTest rcount = 2文件物理地址Test索引结点Wang用户文件目录Lee用户文件目录基于索引结点的共享方式基于索引结点的共享方式: B为了共享为了共享C的一个文件的一个文件F，可以由系统创建一个，可以由系统创建一个LINK类型的新文件，将新文件类型的新文件，将新文件F写入写入B的用户目录中，的用户目录中，以实现以实现B的目录与文件的目录与文件F的链接。在新文件中只包含被链的链接。在新文件中只包含被链接文件接文件F的路径名，称这样的链接方法为符号链接的路径名，称这样的链接方法为符号链接（Symbolic Linking）。）。 优点：能够链接世界上任何地方的机器中的文件优点：能够链接世界上任何地方的机器中的文件 缺点：需要配置索引结点缺点：需要配置索引结点 查找费