第五章 文件系统

1、第五章第五章 文件系统文件系统在现代计算机系统用，要用到大量的程在现代计算机系统用，要用到大量的程序和数据，因内存容量有限，且不能长序和数据，因内存容量有限，且不能长期保存，故而平时总是把它们以文件的期保存，故而平时总是把它们以文件的形式存放在外存中，需要时再随时将它形式存放在外存中，需要时再随时将它们调入内存。们调入内存。如果由用户直接管理外存上的文件，需如果由用户直接管理外存上的文件，需要用户熟悉外存特性，了解各文件的属要用户熟悉外存特性，了解各文件的属性，它们在外存上的位置，显然用户无性，它们在外存上的位置，显然用户无法承担，因此，在操作系统上增加了文法承担，因此，在操作系统上增加了文件

2、管理功能，即文件系统。件管理功能，即文件系统。第五章第五章 文件系统文件系统对大多数用户来说，文件系统是操作系对大多数用户来说，文件系统是操作系统中最直接可见的部分。计算机的重要统中最直接可见的部分。计算机的重要作用之一就是能快速处理大量信息作用之一就是能快速处理大量信息, ,从而从而信息的组织、存取和保管就成为一个极信息的组织、存取和保管就成为一个极为重要的内容。文件系统是计算机组织、为重要的内容。文件系统是计算机组织、存取和保存信息数据的重要手段。本章存取和保存信息数据的重要手段。本章主要讨论文件的组织结构、存取结构、主要讨论文件的组织结构、存取结构、保护以及文件系统空间管理等问题。保护以

3、及文件系统空间管理等问题。第五章第五章 文件系统文件系统文件结构文件结构文件目录管理文件目录管理文件存储空间管理文件存储空间管理文件共享与保护文件共享与保护目的与要求目的与要求：了解文件结构，访问方式，存：了解文件结构，访问方式，存储结构。掌握文件管理用的文件控制块和储结构。掌握文件管理用的文件控制块和文件目录结构。了解文件空间管理方法。文件目录结构。了解文件空间管理方法。重点与难点重点与难点：文件存放与访问方式，文件目：文件存放与访问方式，文件目录结构。录结构。第五章第五章 文件系统文件系统 为了方便使用、管理系统公共程序和数为了方便使用、管理系统公共程序和数据以及用户自己的程序和数据而引入

4、文据以及用户自己的程序和数据而引入文件。件。 为了对外存空间管理和对其上文件的按为了对外存空间管理和对其上文件的按名访问而引入文件系统。名访问而引入文件系统。第五章第五章 文件系统文件系统为什么引入文件和文件系统为什么引入文件和文件系统文件系统的功能文件系统的功能 (1) (1) 为了合理的存放文件，必需对磁盘等辅助存储为了合理的存放文件，必需对磁盘等辅助存储器空间器空间 ( (或称文件空间或称文件空间) ) 进行统一管理。在用户创进行统一管理。在用户创建新文件时为其分配空闲区，而在用户删除或修改建新文件时为其分配空闲区，而在用户删除或修改某个文件时某个文件时, ,回收和调整存储区。回收和调整

5、存储区。(2) (2) 实现按名存取，完成对存放在存储设备上的文实现按名存取，完成对存放在存储设备上的文件信息的查找。件信息的查找。(3) (3) 为了便于存放，文件在存储设备上应按一定的为了便于存放，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。顺序存放。这种存放方式被称为文件的物理结构。(4) (4) 完成文件的共享和提供保护功能。完成文件的共享和提供保护功能。5.1 5.1 文件组织结构文件组织结构5.1.15.1.1文件概念文件概念文件是由创建者所定义、具有文件名文件是由创建者所定义、具有文件名的一组相关的信息集合。的一组相关的信息集合。 文件的主要属性：文件的

6、主要属性： 文件名，文件类型，文件长度，创文件名，文件类型，文件长度，创建者，创建时间，修改时间，文件定建者，创建时间，修改时间，文件定位信息位信息 ，文件所包含的信息。，文件所包含的信息。5.1.2 5.1.2 文件的逻辑结构文件的逻辑结构 操作系统感知文件信息的组织形式叫文件的逻操作系统感知文件信息的组织形式叫文件的逻辑结构。它包括流式文件（无结构文件）和记辑结构。它包括流式文件（无结构文件）和记录式文件（有结构文件）两种，每种文件信息录式文件（有结构文件）两种，每种文件信息的逻辑单位分别是字节和记录。的逻辑单位分别是字节和记录。 流式文件（无结构文件）流式文件（无结构文件）： 是指对文件

7、内信息不再划分单位，它是依次的一串是指对文件内信息不再划分单位，它是依次的一串字节流构成的文件。字节流构成的文件。 记录式文件（有结构文件）：记录式文件（有结构文件）： 是用户把文件内的信息按逻辑上独立的含义是用户把文件内的信息按逻辑上独立的含义划分信息单位，每个单位称为一个记录。所划分信息单位，每个单位称为一个记录。所有记录通常都是描述一个实体集的，有着相有记录通常都是描述一个实体集的，有着相同或不同数目的数据项，记录的长度可分为同或不同数目的数据项，记录的长度可分为定长和不定长记录两类。定长和不定长记录两类。 记录是一组相关数据项的集合，用于描记录是一组相关数据项的集合，用于描述一个对象在

8、某方面的属性。一个记录述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对应包含哪些数据项，取决于需要描述对象的哪个方面。象的哪个方面。一个学生，当把他作为班上的一名学生一个学生，当把他作为班上的一名学生时，时， 对他的描述应使用学号、姓名、年对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过龄及所在系班，也可能还包括他所学过的课程的名称、的课程的名称、 成绩等数据项。成绩等数据项。 但若但若把学生作为一个医疗对象时，对他描述把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、的数据项则应使用诸如病历号、 姓名、姓名、 性别、性别、 出生年月、出生年月、

9、 身高、身高、 体重、体重、 血血压及病史等项。压及病史等项。显然，对于流式的无结构文件来说，查找文件显然，对于流式的无结构文件来说，查找文件中的基本信息单位，例如某个单词，是比较困中的基本信息单位，例如某个单词，是比较困难的。但反过来，流式的无结构文件管理简单，难的。但反过来，流式的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用流式基本信息单位操作不多的文件较适于采用流式的无结构方式，例如，源程序文件、目标代码的无结构方式，例如，源程序文件、目标代码文件等。文件等。记录式的有结构文件可把文件中的记录按各

10、种记录式的有结构文件可把文件中的记录按各种不同的方式排列，以便用户对文件中的记录进不同的方式排列，以便用户对文件中的记录进行修改、追加、查找和管理等操作，主要用于行修改、追加、查找和管理等操作，主要用于信息管理，如数据库系统中。信息管理，如数据库系统中。5.1.3 5.1.3 文件的物理结构文件的物理结构 逻辑文件在辅存的组织结构称为文件的物理结构。如何逻辑文件在辅存的组织结构称为文件的物理结构。如何组织它们主要依赖于文件存储器的物理特性，以及用户组织它们主要依赖于文件存储器的物理特性，以及用户对其文件的访问方式。对其文件的访问方式。 文件的访问方式文件的访问方式 顺序访问顺序访问 指用户从文

11、件初始数据开始依次访问文件中的信息。指用户从文件初始数据开始依次访问文件中的信息。经常被顺序访问的文件应该连续存储在文件存储器经常被顺序访问的文件应该连续存储在文件存储器上。操作系统自动记录文件访问的当前位置。上。操作系统自动记录文件访问的当前位置。 直接（随机）访问直接（随机）访问指用户随机访问文件中的某段信息。读指用户随机访问文件中的某段信息。读/ /写时直接写时直接给出要访问数据的逻辑位置（如第几个字节或第几给出要访问数据的逻辑位置（如第几个字节或第几个记录）及长度，由个记录）及长度，由OSOS将逻辑位置转换成物理位置将逻辑位置转换成物理位置并访问之。并访问之。 磁带磁带顺序访问设备顺序

12、访问设备要求文件顺序存放于带上。要求文件顺序存放于带上。 磁盘磁盘直接（随机）访问设备直接（随机）访问设备文件可顺序、链接文件可顺序、链接式或随机（通过类似页表的结构访问）存放式或随机（通过类似页表的结构访问）存放于设备上。于设备上。 5.1.3 5.1.3 文件的物理结构文件的物理结构为了便于存放于磁盘，文件可被等分成为了便于存放于磁盘，文件可被等分成块块文件系统将一个文件分块存放于外存，文件系统将一个文件分块存放于外存，文件控制块将包含文件的定位信息文件控制块将包含文件的定位信息 文件的物理结构包括顺序结构（连续结文件的物理结构包括顺序结构（连续结构）、链接结构、索引结构三种。构）、链接结

13、构、索引结构三种。 顺序结构（连续结构）顺序结构（连续结构） 文件顺序连续存放于文件存储器上文件顺序连续存放于文件存储器上（如磁带文件，光盘文件）。（如磁带文件，光盘文件）。特点特点: :实现简单实现简单顺序访问容易且速度快顺序访问容易且速度快要求有连续的存储空间，外部碎片多要求有连续的存储空间，外部碎片多必须事先知道文件的长度必须事先知道文件的长度012345678910111213141516171819202122232425262728293031文件名文件名 始址始址 块数块数count 0 2tr 14 3mail 19 6list 28 4f 6 2 文件目录文件目录countf

14、trmaillist磁盘空间磁盘空间（二）链接结构（二）链接结构 链接结构链接结构文件不连续地存放于文件存储器上，但使文件不连续地存放于文件存储器上，但使用指针按文件数据顺序将其链接起来。用指针按文件数据顺序将其链接起来。特点：特点：提高了磁盘空间利用率提高了磁盘空间利用率, ,不存在外部碎片问不存在外部碎片问题；题；文件操作灵活（添加、删除等），有利于文件操作灵活（添加、删除等），有利于文件长度动态变化。文件长度动态变化。（二）链接结构（二）链接结构1 1、隐式链接、隐式链接文件名文件名 始址始址 末址末址jeep 9 25文件目录文件目录01234567891011121314151617

15、181920212223242526272829303111016-125磁盘空间磁盘空间隐式链接问题：隐式链接问题： 只适合顺序访问，对随机访问是低效的。只适合顺序访问，对随机访问是低效的。 可靠性差，因为只要其中任何一个指针出现可靠性差，因为只要其中任何一个指针出现问题，都会导致整个链断开。问题，都会导致整个链断开。 指针占用空间。指针占用空间。2. 2. 显式链接显式链接 把用于链接文件各物理块的指针，显式把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表对地存放在内存的一张链接表中。该表对应整个磁盘，表的序号是物理盘块号。应整个磁盘，表的序号是物理盘块号。在每个表项中存

16、放链接指针，即下一个在每个表项中存放链接指针，即下一个盘块号。我们将该表称为文件分配表盘块号。我们将该表称为文件分配表FAT。大大减少了访问磁盘的次数，提高了检大大减少了访问磁盘的次数，提高了检索速度。索速度。2. 2. 显式链接显式链接 012345物 理 块 号2FCBFAT04516EOF11105EOF0123456789FATFCB A4FCB B9（三）索引结构（三）索引结构链接分配方式虽然解决了连续分配方式链接分配方式虽然解决了连续分配方式所存在的问题，所存在的问题， 但又出现了另外两个问但又出现了另外两个问题，题， 即：即： (1) 不能支持高效的直接存取。要对一个不能支持高效

17、的直接存取。要对一个较大的文件进行直接存取，须首先在较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。中顺序地查找许多盘块号。 (2) FAT需占用较大的内存空间。需占用较大的内存空间。（三）索引结构（三）索引结构索引结构索引结构文件不连续存放于文件存储器上，文件不连续存放于文件存储器上，使用一张索引表来定位文件中的数使用一张索引表来定位文件中的数据（类比页表）据（类比页表）特点：既能顺序存取，又能随机存取，特点：既能顺序存取，又能随机存取，支持文件长度动态变化，外存利用率高，支持文件长度动态变化，外存利用率高，但索引表需占额外空间。但索引表需占额外空间。单级索引结构：单级索引结构

18、： 为每个文件分配一个索引表，一个索引表就为每个文件分配一个索引表，一个索引表就是磁盘块地址数组是磁盘块地址数组, ,其中第其中第i i个条目指向文件个条目指向文件的第的第i i块块多级索引结构：多级索引结构：混合索引结构：混合索引结构：1 1、单级索引结构、单级索引结构012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目录文件目录Jeep 19 917 11025 19文件jeep的单级索引表问题：问题：每建立一个文件，分配一个索引表，占每建立一个文件，分配一个索引表，占用较多的外存空间。用较多的

19、外存空间。对于中小文件，一个索引表需要占用一对于中小文件，一个索引表需要占用一个盘块，空间浪费。个盘块，空间浪费。2. 2. 多级索引结构多级索引结构3. 3. 混合索引结构混合索引结构 将多种索引方式相结合而形成的一种分配将多种索引方式相结合而形成的一种分配方式。方式。 例如，系统中即采用了直接地址，有采用例如，系统中即采用了直接地址，有采用了一级索引方式，或两级索引方式，甚至了一级索引方式，或两级索引方式，甚至还采用了三级索引。还采用了三级索引。 这种方式在这种方式在UNIX系统中采用。系统中采用。 在在Unix System V的索引点中，共设置了的索引点中，共设置了13个地址项，即个地

20、址项，即iaddr(0)iaddr(12)。它们。它们把所有的地址项分成两类，即直接地址和把所有的地址项分成两类，即直接地址和间接地址。间接地址。modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata(1) (1) 直接地址直接地址 为了提高对文件的检索速度，为了提高对文件的检索速度， 在索引结点在索引结点中 可 设 置中 可

21、设 置 1 01 0 个 直 接 地 址 项 ， 即 用个 直 接 地 址 项 ， 即 用iaddr(0)iaddr(9)iaddr(0)iaddr(9)来存放直接地址。来存放直接地址。 换换言之，在这里的每项中所存放的是该文件言之，在这里的每项中所存放的是该文件数据的块号。假如每个块的大小为数据的块号。假如每个块的大小为 4 KB4 KB，当文件不大于当文件不大于40 KB40 KB时，便可直接从索引时，便可直接从索引结点中读出该文件的全部块号。结点中读出该文件的全部块号。(2) (2) 一次间接地址一次间接地址 对于大、对于大、 中型文件，中型文件， 只采用直接地址是只采用直接地址是不现实

22、的。不现实的。 为此，可再利用索引结点中为此，可再利用索引结点中的地址项的地址项iaddr(10)iaddr(10)来提供一次间接地址。来提供一次间接地址。这种方式的实质就是一级索引分配方式。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将图中的一次间址块也就是索引块，系统将分配给文件的多个块号记入其中。在一次分配给文件的多个块号记入其中。在一次间址块中可存放间址块中可存放1K1K个块号，个块号， 因而允许文因而允许文件长达件长达4 MB4 MB。 (3) (3) 多次间接地址。多次间接地址。 当文件长度大于当文件长度大于4 MB+40 KB4 MB+40 KB时时(

23、(一次间址与一次间址与1010个直接地址项个直接地址项) )， 系统还须采用二次间系统还须采用二次间址分配方式。这时，用地址项址分配方式。这时，用地址项iaddr(11)iaddr(11)提提供二次间接地址。该方式的实质是两级索供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中引分配方式。系统此时是在二次间址块中记入所有一次间址块的块号。在采用二次记入所有一次间址块的块号。在采用二次间址方式时，文件最大长度可达间址方式时，文件最大长度可达4 GB4 GB。 同同理，地址项理，地址项iaddr(12)iaddr(12)作为三次间接地址，作为三次间接地址， 其所允许的文件最大

24、长度可达其所允许的文件最大长度可达4 TB4 TB。 习题一设文件索引节点有设文件索引节点有8 8个索引项，其中个索引项，其中4 4个个地址项是直接地址索引，地址项是直接地址索引，3 3个地址项是一个地址项是一级间接地址索引，级间接地址索引，1 1个地址项是二级间接个地址项是二级间接地址索引。每个地址项大小为地址索引。每个地址项大小为4 4个字节，个字节，若磁盘索引块和磁盘数据块大小均为若磁盘索引块和磁盘数据块大小均为256256字节，则可表示的单个文件的最大长度字节，则可表示的单个文件的最大长度为多少为多少KB?KB? 习题二普通文件采用普通文件采用UNIXUNIX三级索引结构，即文件控制三

25、级索引结构，即文件控制块中给出块中给出1313个磁盘地址，前个磁盘地址，前1010个磁盘地址指出个磁盘地址指出文件前文件前1010块的物理地址，第块的物理地址，第1111个磁盘地址指向个磁盘地址指向一级索引表，一级索引表给出一级索引表，一级索引表给出256256个磁盘地址，个磁盘地址，即指出该文件第即指出该文件第1111块至第块至第266266块的物理地址；块的物理地址；第第1212个磁盘地址指向二级索引表，二级索引表个磁盘地址指向二级索引表，二级索引表中指出中指出256256个一级索引表的地址；第个一级索引表的地址；第1313个磁盘个磁盘地址指向三级索引表，三级索引表中指出地址指向三级索引表

26、，三级索引表中指出256256个二级索引表的地址。个二级索引表的地址。文件文件K K的第的第72667266块需要启动几级索引？块需要启动几级索引？ 习题三普通文件采用普通文件采用UNIXUNIX三级索引结构，即文件控制三级索引结构，即文件控制块中给出块中给出1313个磁盘地址，前个磁盘地址，前1010个磁盘地址指出个磁盘地址指出文件前文件前1010块的物理地址，第块的物理地址，第1111个磁盘地址指向个磁盘地址指向一级索引表，一级索引表给出一级索引表，一级索引表给出256256个磁盘地址，个磁盘地址，即指出该文件第即指出该文件第1111块至第块至第266266块的物理地址；块的物理地址；第第

27、1212个磁盘地址指向二级索引表，二级索引表个磁盘地址指向二级索引表，二级索引表中指出中指出256256个一级索引表的地址；第个一级索引表的地址；第1313个磁盘个磁盘地址指向三级索引表，三级索引表中指出地址指向三级索引表，三级索引表中指出256256个二级索引表的地址。个二级索引表的地址。访问文件访问文件K K的第的第72667266块需要启动几次磁盘？块需要启动几次磁盘？（假设已经找到了（假设已经找到了K K文件的地址）文件的地址） 5.2 5.2 文件目录管理文件目录管理 建立文件系统的作用在于对文件信息的建立文件系统的作用在于对文件信息的“按名存取按名存取”，力求查找简便，减少查找，力

28、求查找简便，减少查找时间。为了能对这些文件实施有效的管理，时间。为了能对这些文件实施有效的管理，必须对它们加以妥善组织，这主要是通过必须对它们加以妥善组织，这主要是通过文件目录实现的。文件目录是一种数据结文件目录实现的。文件目录是一种数据结构，用于标识系统中的文件及其物理地址，构，用于标识系统中的文件及其物理地址，供检索时使用。供检索时使用。对目录管理的要求如下：对目录管理的要求如下：实现实现“按名存取按名存取”。 提高对目录的检索速度。提高对目录的检索速度。 文件共享。文件共享。 允许文件重名。允许文件重名。1 1、文件控制块、文件控制块 为了能对一个文件进行正确的存取，必须为文件设置用为了

29、能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，即文件控制块。于描述和控制文件的数据结构，即文件控制块。 文件控制块（文件控制块（FCBFCB）的主要内容的主要内容 文件名文件名 创建者创建者 存放方式：说明该文件在辅存的结构，如顺序结构、存放方式：说明该文件在辅存的结构，如顺序结构、索引结构。索引结构。 文件物理位置信息：具体说明文件在辅存的物理位置文件物理位置信息：具体说明文件在辅存的物理位置和范围，对于不同的物理结构，应做不同的说明，如和范围，对于不同的物理结构，应做不同的说明，如索引表。索引表。 创建、修改时间、保存时间创建、修改时间、保存时间 口令：用于对文件

30、访问进行验证口令：用于对文件访问进行验证 操作限制：如读、写、执行权限说明操作限制：如读、写、执行权限说明文件目录文件目录：把所有的把所有的FCBFCB组织在一起，就组织在一起，就构成了文件目录，即文件控制块的有序构成了文件目录，即文件控制块的有序集合集合目录项：构成文件目录的项目，即目录项：构成文件目录的项目，即FCBFCB目录文件：为了实现对文件目录的管理，目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件存，这个文件就叫目录文件目录主要是为了系统快速实现目录主要是为了系统快速实现“按名存按名存取取”而引入的，查

31、目录是文件系统最频而引入的，查目录是文件系统最频繁的操作，因此目录的合理组织很重要繁的操作，因此目录的合理组织很重要. .文件目录通常是存放在磁盘上的，当文文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的件很多时，文件目录可能要占用大量的盘块。在查找目录的过程中，先将存放盘块。在查找目录的过程中，先将存放目录文件的第一个盘块中的目录调入内目录文件的第一个盘块中的目录调入内存，然后把用户所给定的文件名与目录存，然后把用户所给定的文件名与目录项中的文件名逐一比较。若未找到指定项中的文件名逐一比较。若未找到指定文件，便再将下一个盘块中的目录项调文件，便再将下一个盘块中的目录项调入

32、内存。入内存。在检索目录文件的过程中，只用到了文在检索目录文件的过程中，只用到了文件名，仅当找到了一个目录项时，才需件名，仅当找到了一个目录项时，才需从该目录项中读出该文件的物理地址。从该目录项中读出该文件的物理地址。而其它一些对文件进行描述的信息，在而其它一些对文件进行描述的信息，在检索目录时一概不用。显然这些信息在检索目录时一概不用。显然这些信息在检索目录时不需要调入内存。检索目录时不需要调入内存。采用将文件名与文件描述信息分开的办采用将文件名与文件描述信息分开的办法，即形成索引结点。法，即形成索引结点。2. 2. 索引结点索引结点UNIX的文件目录的文件目录 文件名文件名索引结点编号索引

33、结点编号文件名文件名1文件名文件名2使文件描述信息单独形成一个称为索引使文件描述信息单独形成一个称为索引结点的数据结构，简称为结点的数据结构，简称为i i结点。结点。5.2.15.2.1一级目录结构一级目录结构在整个文件系统中只建立一张目录表，在整个文件系统中只建立一张目录表，每个文件占用一个目录项。每个文件占用一个目录项。每个目录项就是一个文件的每个目录项就是一个文件的FCBFCB。目录表中包含所有文件的目录表中包含所有文件的FCBFCB。当要访问当要访问一个文件时，先按文件名在目录中找到一个文件时，先按文件名在目录中找到对应的文件对应的文件FCBFCB。一级目录结构示意图一级目录结构示意图

34、FCB1 FCB2 FCB3 FCBn 文件 1 文件 2 文件 3 文件 n 优点：优点：简单，易实现简单，易实现缺点：缺点：限制了用户对文件的命名限制了用户对文件的命名（存在（存在“命名冲命名冲突突”问题）问题）检索文件时平均检索时间长检索文件时平均检索时间长不适于多用户系统不适于多用户系统5.2.25.2.2二级目录结构二级目录结构 为克服单级目录结构存在的命名冲突问题，为克服单级目录结构存在的命名冲突问题，并提高对目录文件的检索速度而引入。并提高对目录文件的检索速度而引入。目录分为两级：目录分为两级：一级称为一级称为主文件目录主文件目录MFDMFD ，给出用户名，用户子目录所在的物理位

35、置；给出用户名，用户子目录所在的物理位置；二级称为二级称为用户文件目录用户文件目录UFDUFD （又称用户子（又称用户子目录），给出该用户所有文件的目录），给出该用户所有文件的FCBFCB。每。每个个UFDUFD在在MFDMFD中均设置一项，用以描述中均设置一项，用以描述UFDUFD的用户名及其物理位置。的用户名及其物理位置。特点：解决了文件的重名问题特点：解决了文件的重名问题; ; 可用于多用户系统可用于多用户系统; ; 顺序查找时间降低。顺序查找时间降低。FCB1FCB2FCB1FCB2 路径名路径名 将用户名与文件名连到一起组成路将用户名与文件名连到一起组成路经名。例如：经名。例如：/

36、/luoyu/test.cluoyu/test.c二级目录解决了将不同用户文件分开存二级目录解决了将不同用户文件分开存放并建目录进行索引的问题，但是如果放并建目录进行索引的问题，但是如果用户文件太多，在一个子目录下存放用用户文件太多，在一个子目录下存放用户所有文件同样也会存在户所有文件同样也会存在“重名重名”问题，问题，因此引入了树形目录（多级目录）。因此引入了树形目录（多级目录）。5.2.35.2.3树形目录结构（多级目录结构）树形目录结构（多级目录结构）对二级目录简单扩充可得三级或三级以上的多对二级目录简单扩充可得三级或三级以上的多级目录结构，即允许每一级目录中的级目录结构，即允许每一级目

37、录中的FCBFCB要么指要么指向文件，要么指向下一级子目录即可。这是当向文件，要么指向下一级子目录即可。这是当今主流今主流OSOS普遍采用的目录结构。普遍采用的目录结构。树形目录中有根目录，树中的每个文件具有唯树形目录中有根目录，树中的每个文件具有唯一的路径名。一的路径名。优点优点： 解决了命名冲突问题解决了命名冲突问题 层次结构清晰，便于对文件分类管理层次结构清晰，便于对文件分类管理 缺点：缺点：查找一个查找一个文件文件按按路径名路径名逐层检查，由于逐层检查，由于每个文件都放在外存，多次访盘影响速度每个文件都放在外存，多次访盘影响速度唯一确定文件的路径名太长，故引入唯一确定文件的路径名太长，

38、故引入当前目录当前目录 概念，提供相对于当前目录的相对路径名可加概念，提供相对于当前目录的相对路径名可加速文件速文件FCBFCB的查找。的查找。目录查询技术：目录查询技术：当用户要访问一个已存在文件时，系统首当用户要访问一个已存在文件时，系统首先利用用户提供的文件名对目录进行查询，先利用用户提供的文件名对目录进行查询，找出该文件的文件控制块；然后，根据找出该文件的文件控制块；然后，根据FCBFCB中所记录的文件物理地址，启动磁盘，将中所记录的文件物理地址，启动磁盘，将磁盘上的文件读入内存。磁盘上的文件读入内存。UNIXUNIX多级树形目录结构多级树形目录结构示意图示意图tty00devbinl

39、ibetcusrtty01shdate cc whopasswdUNIXfei1myfile.cgettyincludefei2testfile.c练习有一个文件系统有一个文件系统, , 根目录长驻内存根目录长驻内存, , 如图所示如图所示: :目录文件采用链接式目录文件采用链接式, , 每个磁盘块存放每个磁盘块存放1010个下个下级文件的描述级文件的描述, , 最多存放最多存放4040个下级文件个下级文件. . 若下若下级文件为目录文件级文件为目录文件, , 上级目录指向该目录文件上级目录指向该目录文件的第一块的第一块, , 否则指向普通文件的文件控制块否则指向普通文件的文件控制块. .目录

40、结构中文件或子目录按自左向右的次序排目录结构中文件或子目录按自左向右的次序排列列. . 普通文件采用三级索引形式普通文件采用三级索引形式, , 文件控制块中给文件控制块中给出出1313个磁盘地址个磁盘地址, , 前前1010个磁盘地址指出前个磁盘地址指出前1010块块的物理地址的物理地址, , 第第1111个磁盘地址指向一级索引表个磁盘地址指向一级索引表, , 一级索引表给出一级索引表给出256256个磁盘地址个磁盘地址, , 即指出该文即指出该文件第件第1111块至第块至第266266块的地址块的地址; ; 第第1212个磁盘地址个磁盘地址指向二级索引表指向二级索引表, , 二级索引表中指出

41、二级索引表中指出256256个一个一级索引表的地址级索引表的地址; ; 第第1313个磁盘地址指向三级索个磁盘地址指向三级索引表引表, , 三级索引表中指出三级索引表中指出256256个二级索引表的个二级索引表的地址地址. .(1) (1) 该文件系统中的普通文件最大可有多少块该文件系统中的普通文件最大可有多少块? ?(2) (2) 若要读文件若要读文件/A/D/K/Q/A/D/K/Q中的某一块中的某一块, , 最少要最少要启动磁盘几次启动磁盘几次? ? 最多要启动磁盘几次最多要启动磁盘几次? ?(3)(3)访问文件访问文件Q Q的第的第72667266块块, ,最少要启动磁盘几最少要启动磁盘

42、几次次? ? 最多要启动磁盘几次最多要启动磁盘几次? ?5.3 5.3 文件存储空间管理文件存储空间管理l存储空间管理是文件系统的重要任务之一。只存储空间管理是文件系统的重要任务之一。只有有效地进行存储空间管理，才能保证多个用有有效地进行存储空间管理，才能保证多个用户共享文件存储设备和得以实现文件的按名存户共享文件存储设备和得以实现文件的按名存取。由于文件存储设备是分成若干个大小相等取。由于文件存储设备是分成若干个大小相等的物理块，并以块为单位来交换信息的，因此，的物理块，并以块为单位来交换信息的，因此，文件存储空间的管理实质上是一个空闲块的组文件存储空间的管理实质上是一个空闲块的组织和管理问

43、题，它包括空闲块的组织，空闲块织和管理问题，它包括空闲块的组织，空闲块的分配与空闲块的回收等几个问题。的分配与空闲块的回收等几个问题。l有下述有下述3 3种不同的空闲块管理方法。它们是：种不同的空闲块管理方法。它们是：(1) (1) 空闲表法空闲表法(2) (2) 位示图法位示图法(3) (3) 成组链接法成组链接法(1) (1) 空闲表法空闲表法l空闲表法属于连续分配，它与内存的动态分配空闲表法属于连续分配，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一空间，即系统也为外存上的所有空闲区建立一张空闲表

44、，每个空闲区对应于一个空闲表项，张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号，该空闲区的第一个块号，其中包括表项序号，该空闲区的第一个块号，该区的空闲块数等信息。该区的空闲块数等信息。l在系统为某个文件分配空闲块时，首先扫描空在系统为某个文件分配空闲块时，首先扫描空闲表，如找到合适的空闲区项，则分配给申请闲表，如找到合适的空闲区项，则分配给申请者，并把该项从空闲文件目录中去掉。如果一者，并把该项从空闲文件目录中去掉。如果一个空闲区项所含块数超过申请者要求，则为申个空闲区项所含块数超过申请者要求，则为申请者分配了所要的物理块之后，再修改该表项。请者分配了所要的物理块之后，再修改该表项

45、。序号序号第一空闲盘第一空闲盘块号块号空闲盘块数空闲盘块数12429331554l当一个文件被删除，释放存储物理块时，系统当一个文件被删除，释放存储物理块时，系统则把被释放的块号、长度以及第一块块号置入则把被释放的块号、长度以及第一块块号置入空闲表的新表项中。空闲表的新表项中。l显然，在内存管理时讨论过有关空闲连续区分显然，在内存管理时讨论过有关空闲连续区分配和释放算法。只要稍加修改就可用于空闲表配和释放算法。只要稍加修改就可用于空闲表的分配和回收。的分配和回收。l空闲表方法适用于连续文件结构的文件存储区空闲表方法适用于连续文件结构的文件存储区的分配与回收。的分配与回收。(2) (2) 位示图

46、位示图l位示图是利用二进制的一位来表示磁盘中一个位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，当值为盘块的使用情况，当值为0 0时，表示对应的盘时，表示对应的盘块空闲；为块空闲；为1 1时，表示已分配。时，表示已分配。l磁盘上的所有盘块都有一个二进制位与之对应，磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，这样，由所有盘块所对应的位构成一个集合，成为位示图。成为位示图。(3) (3) 成组链接法成组链接法成组链法首先把文件存储设备中的所有空闲块成组链法首先把文件存储设备中的所有空闲块按按5050块划分为一组。块划分为一组。其中，每组的第一块用来存放

47、前一组中各块的其中，每组的第一块用来存放前一组中各块的块号和总块数。由于第一组的前面已无其他组块号和总块数。由于第一组的前面已无其他组存在，因此，第一组的块数为存在，因此，第一组的块数为4949块。不过，由块。不过，由于存储设备的空间块不一定正好是于存储设备的空间块不一定正好是5050的整倍数，的整倍数，因而最后一组将不足因而最后一组将不足5050块，且由于该组后面已块，且由于该组后面已无另外的空闲块组，所以，该组的物理块号与无另外的空闲块组，所以，该组的物理块号与总块数只能放在管理文件存储设备用的文件资总块数只能放在管理文件存储设备用的文件资源表中。源表中。在成组链法对文件设备进行了上述分组

48、之后，在成组链法对文件设备进行了上述分组之后，系统可根据申请者的要求进行空闲块的分配，系统可根据申请者的要求进行空闲块的分配，并在释放文件时回收空闲块。下面我们介绍并在释放文件时回收空闲块。下面我们介绍成组链法的分配和释放过程。成组链法的分配和释放过程。l首先，系统在初启时把文件资源表复制到内存，首先，系统在初启时把文件资源表复制到内存，从而使文件资源表中放有最后一组空闲块块号从而使文件资源表中放有最后一组空闲块块号与总块数的信息进入内存。与总块数的信息进入内存。l与空闲块块号及总块数相对应，用于空闲块分与空闲块块号及总块数相对应，用于空闲块分配与回收是指针配与回收是指针PtrPtr，且，且P

49、trPtr的初值等于该组空的初值等于该组空闲块的总块数。当申请者提出空闲块要求闲块的总块数。当申请者提出空闲块要求n n时，时，按照后进先出的原则，分配程序在取走按照后进先出的原则，分配程序在取走PtrPtr所所指的块号之后，再做指的块号之后，再做PtrPtr-1PtrPtr-1的操作。这个的操作。这个过程一直持续到所要求的过程一直持续到所要求的n n块都已分配完毕。块都已分配完毕。当内存中只剩下最后一个空闲块号时，系统启当内存中只剩下最后一个空闲块号时，系统启动设备管理程序，将该块中存放的下一组的块动设备管理程序，将该块中存放的下一组的块号与总块数读入内存之后将该块分配给申请者。号与总块数读

50、入内存之后将该块分配给申请者。然后，系统重新设置然后，系统重新设置PtrPtr指针，并继续为申请指针，并继续为申请者进程分配空闲块。者进程分配空闲块。5.4 5.4 文件访问系统调用文件访问系统调用操作系统提供文件创建、删除、打开、操作系统提供文件创建、删除、打开、关闭、读、写等系统调用作为用户编程关闭、读、写等系统调用作为用户编程接口。接口。5.5 5.5 文件共享与文件保护文件共享与文件保护AABBBBBCCCCC根目录?CCC包含有共享文件的文件系统包含有共享文件的文件系统 无环图目录结构无环图目录结构 可能会出现一个同样的文件，用户希望在可能会出现一个同样的文件，用户希望在不同的目录中

51、都能访问它。如果在树形目不同的目录中都能访问它。如果在树形目录结构中要达到这个要求，就必须生成两录结构中要达到这个要求，就必须生成两份文件副本，这样显然浪费了存储空间。份文件副本，这样显然浪费了存储空间。 引入无环图目录结构实现文件的共享。在引入无环图目录结构实现文件的共享。在树形目录结构中增加一些未形成环路的链，树形目录结构中增加一些未形成环路的链，当需要共享文件或共享子目录时，即可建当需要共享文件或共享子目录时，即可建立一个链的新目录项。立一个链的新目录项。 特点特点 方便文件共享。方便文件共享。 两个或多个两个或多个FCBFCB的一致性难保证，如删除的一致性难保证，如删除文件时，当文件修改而引起文件时，当文件修改而引起FCBFCB内容变化内容变化时。时。 root dict spell list root rade W7 list count p 无环图目录结构示意图无环图目录结构示意图为图中每个结点设置一个访问计数器，为图中每个结点设置一个访问计数器，每当图中增加了一条对某个结点的共享每当图中增加了一条对某个结点的共享链时，该结点的访问计数器加链时，该结点的访问计数器加1 1；每当需；每当需要删除某个结点时，该结点的访问计数要删除某个结点时，该结