第六章_文件管理

1、第六章第六章 文件管理文件管理内容提要内容提要l 文件管理的功能文件管理的功能l 文件和文件系统文件和文件系统l 文件的逻辑结构文件的逻辑结构l 文件的存储结构文件的存储结构l 目录管理目录管理l 文件存储空间管理文件存储空间管理l 文件的共享和保护文件的共享和保护文件管理的功能文件管理的功能（1）文件存储空间的管理文件存储空间的管理设置相应的数据结构，来记录文件存储空间的使用情况设置相应的数据结构，来记录文件存储空间的使用情况对存储空间的分配和回收的功能对存储空间的分配和回收的功能（2） 目录管理目录管理主要任务：为每个文件建立目录项，并对众多的目录项加以有效主要任务：为每个文件建立目录项，

2、并对众多的目录项加以有效的组织，以实现方便的按名存取的组织，以实现方便的按名存取实现文件共享实现文件共享提供快速的目录查询手段，以提高对文件的检索速度提供快速的目录查询手段，以提高对文件的检索速度（3） 文件的读文件的读/写管理写管理根据用户请求，从外存中读取数据；或将数据写入外存。根据用户请求，从外存中读取数据；或将数据写入外存。（4）文件的共享和保护文件的共享和保护防止未经核准的用户存取文件；防止冒名顶替存取文件；防止以防止未经核准的用户存取文件；防止冒名顶替存取文件；防止以不确切的方式使用文件。不确切的方式使用文件。6.1 6.1 文件和文件系统文件和文件系统1、文件、文件n 具有一定名

3、称的一组相关数据的集合。文件通常具有一定名称的一组相关数据的集合。文件通常存放在外部存储介质上（如磁盘、光盘等）存放在外部存储介质上（如磁盘、光盘等）n各种程序、数据集合各种程序、数据集合n一些低速的外部设备，如键盘、终端显示器和打一些低速的外部设备，如键盘、终端显示器和打印机等也被看做文件印机等也被看做文件文件n文件命名文件命名文件提供了一种将数据保存在外部存储介质上以便于文件提供了一种将数据保存在外部存储介质上以便于访问的功能。为了方便用户使用，每个文件都有特定访问的功能。为了方便用户使用，每个文件都有特定的名称。这样用户就不必关心文件存储方法、物理位的名称。这样用户就不必关心文件存储方法

4、、物理位置以及访问方式等，而可以直接通过文件名来使用文置以及访问方式等，而可以直接通过文件名来使用文件。件。文件名称的长度因系统而异。文件名称的长度因系统而异。有的文件系统不区分文件名的大小写，而有的则加以有的文件系统不区分文件名的大小写，而有的则加以区分。区分。有的文件系统只能使用有的文件系统只能使用ASCIIASCII字符命名文件，而有的则字符命名文件，而有的则可以使用可以使用UnicodeUnicode字符。字符。有的操作系统对不同的后缀有特定的解释，而有的则有的操作系统对不同的后缀有特定的解释，而有的则没有统一的规定。没有统一的规定。文件n文件的内部组织：记录和数据项文件的内部组织：记

5、录和数据项数据项：数据项是数据的最小单位。用来描述实体的数据项：数据项是数据的最小单位。用来描述实体的某个属性，如学生的学号，姓名等。有基本数据项和某个属性，如学生的学号，姓名等。有基本数据项和组合数据项之分组合数据项之分记录：记录是一组相关数据项的集合，用于描述一个记录：记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。如一个学生记录，由学号，姓对象在某方面的属性。如一个学生记录，由学号，姓名，年龄等组成。名，年龄等组成。文件：文件指具有一定名称的一组相关数据的集合。文件：文件指具有一定名称的一组相关数据的集合。 文件n文件属性：关于文件本身的说明信息或属性信息。文件属性：关于文件

6、本身的说明信息或属性信息。文件名称：供用户使用的外部标识。这是文件最基本的属性。文件名称：供用户使用的外部标识。这是文件最基本的属性。文件内部标识：是一个编号，可以方便的管理和查找文件。文件内部标识：是一个编号，可以方便的管理和查找文件。文件物理位置：文件在存储介质上所存放的物理位置文件物理位置：文件在存储介质上所存放的物理位置文件拥有者：操作系统通常为多用户的，不同的用户也拥有文件拥有者：操作系统通常为多用户的，不同的用户也拥有各自不同的文件，对这些文件的操作权限也不同。各自不同的文件，对这些文件的操作权限也不同。文件权限：文件的拥有者可以为自己的文件赋予各种权限。文件权限：文件的拥有者可以

7、为自己的文件赋予各种权限。文件类型：可以从不同角度对文件进行分类。文件类型：可以从不同角度对文件进行分类。文件长度：文件中数据的长度。文件长度：文件中数据的长度。文件时间：文件时间有很多。如文件创建时间、文件最后一文件时间：文件时间有很多。如文件创建时间、文件最后一次修改时间、文件最后一次执行时间，等。次修改时间、文件最后一次执行时间，等。文件属性n文件分类：可按不同的分类标准对文件进行分类文件分类：可按不同的分类标准对文件进行分类（1 1）按文件的逻辑结构划分）按文件的逻辑结构划分无结构文件无结构文件有结构文件有结构文件（2 2）按文件的物理结构分）按文件的物理结构分连续文件连续文件非连续文

8、件非连续文件链接文件链接文件索引文件索引文件文件分类（3 3）按文件的用途分）按文件的用途分系统文件系统文件库文件库文件用户文件用户文件 （4 4）按文件中数据的组织形式分）按文件中数据的组织形式分源文件源文件目标文件目标文件可执行文件可执行文件（5 5）按文件的存取控制属性分）按文件的存取控制属性分只执行文件只执行文件只读文件只读文件读写文件读写文件 文件分类n文件存取：用户在使用文件时按何种次序存取文件。文件存取：用户在使用文件时按何种次序存取文件。顺序访问：按从前到后的顺序对文件进行读写操作。顺序访问：按从前到后的顺序对文件进行读写操作。如磁带。如磁带。随机访问：也称直接访问。可以按任意

9、的次序对文件随机访问：也称直接访问。可以按任意的次序对文件进行读写操作。如磁盘。进行读写操作。如磁盘。索引访问：也称按键访问，这种方式对文件中的记录索引访问：也称按键访问，这种方式对文件中的记录按某个数据项的值来排列，从而可以根据键值来快速按某个数据项的值来排列，从而可以根据键值来快速存取。如索引表很长，则可以将索引表再加以索引，存取。如索引表很长，则可以将索引表再加以索引，以形成具有层次结构的多级索引。以形成具有层次结构的多级索引。文件存取文件存取n文件操作：文件系统向用户提供的各种调用接口。文件操作：文件系统向用户提供的各种调用接口。（1 1）创建文件）创建文件为文件分配必要的外存空间为文

10、件分配必要的外存空间为文件建立目录项，里面记录了新文件的文件名和在外存的为文件建立目录项，里面记录了新文件的文件名和在外存的地址地址（2 2）删除文件）删除文件系统从目录中找到要删除文件的目录项，并置空该目录项。系统从目录中找到要删除文件的目录项，并置空该目录项。回收该文件所占有的存储空间回收该文件所占有的存储空间 （3 3）读文件）读文件在系统调用中给出文件名和应读入的内存目标地址在系统调用中给出文件名和应读入的内存目标地址系统查找目录，找到指定的目录项，从中得到文件在外存中系统查找目录，找到指定的目录项，从中得到文件在外存中的位置的位置通过读指针，将外存中的数据读到内存缓冲区通过读指针，将

11、外存中的数据读到内存缓冲区文件的操作（4 4）写文件）写文件在系统调用中给出文件名及文件在内存中的源地址在系统调用中给出文件名及文件在内存中的源地址系统查找目录，找到指定的目录项系统查找目录，找到指定的目录项通过写指针，将内存缓冲区中的数据写到外存的文件中通过写指针，将内存缓冲区中的数据写到外存的文件中（5 5）截断文件）截断文件 如果一个文件的内容已经陈旧而需要全部更新，但文件名和文件属如果一个文件的内容已经陈旧而需要全部更新，但文件名和文件属性并没有发生变化时，可以截断文件，即将原来文件的长度置为性并没有发生变化时，可以截断文件，即将原来文件的长度置为0 0（6 6）设置文件的读）设置文件

12、的读/ /写位置写位置指用于设置文件读指用于设置文件读/ /写指针的位置，这样，每次读写指针的位置，这样，每次读/ /写文件时，不是写文件时，不是从文件的始端而是从所设置的位置开始操作，为文件提供随机存取从文件的始端而是从所设置的位置开始操作，为文件提供随机存取的能力。的能力。（7 7）打开文件）打开文件系统将指名文件的属性从外存拷贝到内存打开文件的一个表目中，系统将指名文件的属性从外存拷贝到内存打开文件的一个表目中，并将该表目的编号返回给用户并将该表目的编号返回给用户（8 8）关闭文件）关闭文件文件从打开文件表目中被删除掉文件从打开文件表目中被删除掉 文件的操作n文件结构：文件的组织形式，它

13、影响对文件的检索速文件结构：文件的组织形式，它影响对文件的检索速度。度。n文件系统的设计者一般从两种不同的观点去研究文件文件系统的设计者一般从两种不同的观点去研究文件的结构：一种是从用户使用角度去研究；的结构：一种是从用户使用角度去研究；另一种是从另一种是从系统实现的角度去研究。系统实现的角度去研究。文件的逻辑结构：这是从用户的观点出发所观察到的文件的逻辑结构：这是从用户的观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性。它独立于文件的物理特性。文件的物理结构：即文件的存储结构。指文件在外存文件的物理结构：

14、即文件的存储结构。指文件在外存上的存储组织形式。文件的物理结构和存储介质的存上的存储组织形式。文件的物理结构和存储介质的存储性能以及所采用的外存分配方式有关。储性能以及所采用的外存分配方式有关。 文件的结构文件的结构2、文件系统、文件系统n文件系统定义文件系统定义: 操作系统中与管理文件有关的软件和数据操作系统中与管理文件有关的软件和数据称为文件系统。它负责为用户建立文件，撤销、读写、修称为文件系统。它负责为用户建立文件，撤销、读写、修改和复制文件，方便用户按名存取，实现文件的共享和保改和复制文件，方便用户按名存取，实现文件的共享和保护。护。n文件系统的层次模型文件系统的层次模型该模型由许多不

15、同层构成该模型由许多不同层构成每一层都会使用下一层的功能特性来创建新的功能，每一层都会使用下一层的功能特性来创建新的功能，为上一层服务。为上一层服务。文件系统基本基本I/O控制层：由设备驱动控制层：由设备驱动程序和程序和I/O处理程序组成，负处理程序组成，负责启动该设备上的责启动该设备上的I/O操作，操作，处理处理I/O请求的完成。请求的完成。基本文件系统层：该层处理基本文件系统层：该层处理在磁盘间和磁带系统间交换在磁盘间和磁带系统间交换的数据块，关注数据块在磁的数据块，关注数据块在磁盘中的位置。盘中的位置。文件组织模块层：负责所有文件组织模块层：负责所有文件文件I/O的初始和终止的初始和终止

16、逻辑文件系统层：使用户和逻辑文件系统层：使用户和应用程序能够访问到记录应用程序能够访问到记录文件系统接口文件系统接口逻辑文件系统层逻辑文件系统层文件组织模块层文件组织模块层基本文件系统层基本文件系统层基本基本I/O控制层控制层物理磁盘物理磁盘文件系统层次模型文件系统层次模型文件系统的层次模型文件管理的要素文件管理的要素文件结构文件结构目录管理目录管理操作，操作，文件名文件名用户访问控制用户访问控制用户用户和程和程序命序命令令访问方法访问方法文件操文件操作函数作函数记录记录组块组块主存缓冲区主存缓冲区中的物理块中的物理块磁盘中的磁盘中的物理块物理块磁盘磁盘调度调度I/O文件文件分配分配空闲空闲空

17、间空间管理管理文件管理关注的问题文件管理关注的问题操作系统关注的问题操作系统关注的问题6.2 6.2 文件的逻辑结构文件的逻辑结构n文件逻辑结构的基本要求文件逻辑结构的基本要求能提高检索速度：文件由大批记录组成，对于能提高检索速度：文件由大批记录组成，对于记录的组织应有利于提高记录检索的速度。记录的组织应有利于提高记录检索的速度。便于修改：便于在文件中增加、修改、删除一便于修改：便于在文件中增加、修改、删除一条记录条记录降低文件的存储费用：即减少文件存储占用的降低文件的存储费用：即减少文件存储占用的存储空间。存储空间。n无结构的字节流式文件 这类文件是由先后到达的相关字节组成，文件内的信息不再

18、划分结构。如各种程序、文本文件等。n有结构的记录式文件 这类文件由若干个记录组成。 记录又分成定长记录和变长记录两种。 定长记录指文件中所有记录的长度都是相同的。 变长记录指文件中各记录的长度不相同。文件逻辑结构的类型文件逻辑结构的类型记录式文件中记录的组织记录式文件中记录的组织n顺序文件：由一系列记录按某种顺序(可以是按文件的创建时间或按关键字排序)排列所形成的文件。其中的记录可以是定长记录，也可以是变长记录。R0R1R2R3RiLLLLLL2L3L4LL(i 1)LRptr(a) 定长记录文件L0R0L1R1RiWptr(b) 变 长记录文件Li00L0L0 1L1L0 L1 2Li(Lk

19、 1)i1k0(Lk 1)ik0定长和变长记录文件定长和变长记录文件n要读或写一大批记录时，对顺序文件的存取效率是所有逻辑文件中最高的，因此顺序文件通常用于批处理应用中；n此外，也只有顺序文件才能存储在磁带上， 并能有效地工作。n在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。顺序文件所表现出来的性能就可能很差， 尤其是当文件较大时， 情况更为严重。顺序文件的优缺点顺序文件的优缺点索引文件（2）索引文件：系统中建立一张索引表，在表中为每个记）索引文件：系统中建立一张索引表，在表中为每个记录设置一个表项，以加快对记录的检索速度。录设置一个表项，以加快对记

20、录的检索速度。索引号0长度 m指针 ptrm01m1imi索引表R0R1Ri逻辑文件索引号0长度 m指针 ptrm01m1imi索引表R0R1Ri逻辑文件索引文件的组织索引文件的组织索引顺序文件（3）索引顺序文件：将顺序文件中的所有记录分成若干个）索引顺序文件：将顺序文件中的所有记录分成若干个组；为顺序文件建立一张索引表，在索引表中为每组中的组；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。向该记录的指针。 键An QiBao RongChen Lin逻辑地址姓 名An QiAn

21、 Kang其它属性Bao Rong逻辑文件索引顺序文件索引顺序文件 操作系统不了解也不关心文件的组织形式和内容，它所操作系统不了解也不关心文件的组织形式和内容，它所“看到的看到的”都是字节流。文件信息的实际意义是由用户级都是字节流。文件信息的实际意义是由用户级程序强加和关心的。程序强加和关心的。 6.3 6.3 外存分配方式外存分配方式n目前常用的外存分配方法有：连续分配、链接分配和索引目前常用的外存分配方法有：连续分配、链接分配和索引分配三种。分配三种。n通常，一个系统中，仅采用其中的一种方法来为文件分配通常，一个系统中，仅采用其中的一种方法来为文件分配外存空间。外存空间。n文件存储器的存储

22、空间，通常划分成若干个大小相等的块文件存储器的存储空间，通常划分成若干个大小相等的块(例如例如512个字节为一块个字节为一块)，叫物理块。，叫物理块。n在文件存储器上的文件称为物理文件，在文件存储器上的文件称为物理文件，n 存放文件记录的物理块叫物理记录。存放文件记录的物理块叫物理记录。 1、 连续分配连续分配 最简单的物理结构，它是把逻辑上连续的信息文件存贮在最简单的物理结构，它是把逻辑上连续的信息文件存贮在连续的物理块中的一种组织方式。连续的物理块中的一种组织方式。 连续分配n 最简单的物理结构，它是把逻辑上连续的信息文件存贮在连续的物理块中的一种组织方式。 123056749101181

23、3141512171819162122232025262724list29303128m ailcountfilestartlengthcount02tr143mail196list284f62目 录trf 优点：（1） 管理简单 只要记住文件所在的第一块位置及文件包括的块数即可；（2） 存取速度快 只要访问一次文件的管理信息，就可方便地存取到任一记录。缺点：（1） 不灵活 要求在文件创建时，就给出文件的最大长度，不利于文件的动态修改；（2） 产生碎片 连续分配n把逻辑上连续的信息文件存贮在不连续的物理块中。n根据指针所在的位置不同，分为隐式链接和显式链接两种。（1）隐式链接 存放信息的物理块

24、中设有一个指向下一个物理块指针。文件各块通过链指针链在一起。 链接分配隐式链接25123056749101181314151217181916212223202526272429303128filestartendjeep925目 录101-116n 存放信息的物理块中设有一个指向下一个物理块指针。文件各块通过链指针链在一起。 优点：（1）提高了磁盘空间利用率,不存在碎片问题（2）有利于文件的动态修改缺点： 只能顺序存取。 隐式链接n为了实现随机存取，可以把指针字从文件的各物理块中取出，放在一个表中，此表叫文件分配表FAT(File Allocation Table)。n系统工作时，文件分配表

25、被读到主存。n存取任一记录时在主存沿链查找，很快能定位文件中任一个记录的位置。显示链接012345物 理 块 号2FCBFAT0451显示链接6EOF11105EOF0123456789FATFCB A4FCB B9MS-DOS的文件物理结构的文件物理结构显示链接这个方法的主要缺点这个方法的主要缺点: 在系统工作期间，整个表必须在主存。占用内存太多。在系统工作期间，整个表必须在主存。占用内存太多。 以以100G磁盘为例，若每块按磁盘为例，若每块按512个字节计，则这个表个字节计，则这个表将占用将占用200M项。每项至少占用项。每项至少占用4个字节。因此，这个表要个字节。因此，这个表要占用占用8

26、00M字节的主存。字节的主存。 为了节省主存，盘文件映射（分配）表必须作为一个为了节省主存，盘文件映射（分配）表必须作为一个文件放在磁盘上。并要求存放该文件的各个盘块不要过于文件放在磁盘上。并要求存放该文件的各个盘块不要过于分散。否则，可能要读取多个存放盘文件映射表的物理块，分散。否则，可能要读取多个存放盘文件映射表的物理块，才能找到它们之间的对应关系，从而减少了它的优越性。才能找到它们之间的对应关系，从而减少了它的优越性。显示链接n链接分配方式虽然解决了连续分配方式所存在的问题， 但又出现了另外两个问题， 即： （1） 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中

27、顺序地查找许多盘块号。 （2）FAT需占用较大的内存空间。 n为了实现文件的随机存取，在文件目录表中为每个文件保留一个索引表块号，该索引块指出文件的逻辑块与物理块的映射关系。n现代操作系统几乎都提供索引结构索引分配123056749101181314151217181916212223202526272429303128countfile块 序 号jeep19目 录91611025 1 1 119索引分配方式索引分配方式单级索引分配单级索引分配01210510625435635798510510625474035635711259853607401125主索引360第二级索引磁盘空间多级索引分

28、配多级索引分配modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata混合索引分配混合索引分配（1）允许文件动态修改，增加了使用的灵活性；（2）可直接对文件进行存取。 缺点：（1）索引表要占用额外空间；（2）降低了文件的存取速度(至少需要访问存贮器二次：一次访问索引表，一次访问文件信息)。 索引结构文件的优点索引结构文件的优点 文

29、件的存贮介质是指存储文件信息的材料。它们是以块为单位进行信息的存储、传输。常用的存贮介质有磁带磁盘和光盘。其特点如下表所示：存储介质存储介质物理结构物理结构存取方式存取方式磁带磁带连续结构连续结构顺序存取顺序存取磁盘和光盘磁盘和光盘连续连续链接链接索引索引顺序顺序顺序顺序顺序顺序 随机随机6.4 6.4 目录管理目录管理 n目录管理要实现的功能：目录管理要实现的功能：实现实现“按名存取按名存取” ” 提高对目录的检索速度提高对目录的检索速度文件共享文件共享允许文件重名允许文件重名对目录管理的要求n文件控制块：文件控制块：用于描述和控制文件的数据结构用于描述和控制文件的数据结构文件管理者可以借助

30、文件控制块中的信息，对文件施以各种文件管理者可以借助文件控制块中的信息，对文件施以各种操作操作文件与文件控制块一一对应文件与文件控制块一一对应文件控制块的有序集合称为文件目录，即一个文件控制块就文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项是一个文件目录项文件控制块是文件存在的唯一标志文件控制块是文件存在的唯一标志文件控制块（FCB） 文件控制块中，包含文件的一些信息，这些信息被分成以文件控制块中，包含文件的一些信息，这些信息被分成以下四类下四类n基本信息基本信息文件名：由文件的创建者选择的名，在一个特定的目录中具文件名：由文件的创建者选择的名，在一个特定的目录中具有唯一

31、性有唯一性文件类型：例如文本文件、二进制文件等文件类型：例如文本文件、二进制文件等文件组织：系统所支持的不同组织形式文件组织：系统所支持的不同组织形式n地址信息地址信息起始地址：文件存放在外存的物理地址起始地址：文件存放在外存的物理地址已使用大小：文件的大小已使用大小：文件的大小分配大小：文件的最大长度分配大小：文件的最大长度文件控制块n存取控制信息存取控制信息文件主：拥有文件的控制权文件主：拥有文件的控制权访问控制：可包括有权限用户的用户名和口令访问控制：可包括有权限用户的用户名和口令允许的操作：控制读、写、执行等权限允许的操作：控制读、写、执行等权限n使用信息使用信息创建日期：文件首次存放

32、在目录中的时间创建日期：文件首次存放在目录中的时间读时间：最后一次读文件记录的时间读时间：最后一次读文件记录的时间修改时间：最后一次更新、插入或删除记录的时间修改时间：最后一次更新、插入或删除记录的时间备份时间：文件最后一次备份到其它存储介质的时间备份时间：文件最后一次备份到其它存储介质的时间文件控制块n目录文件：目录文件：为了加快对文件的检索，往往将文件控制块集中为了加快对文件的检索，往往将文件控制块集中在一起进行管理。这种文件控制块的有序集合就在一起进行管理。这种文件控制块的有序集合就叫文件目录。叫文件目录。文件控制块就是其中的目录项文件控制块就是其中的目录项 文件目录具有将文件名转换成该

33、文件在外存的物文件目录具有将文件名转换成该文件在外存的物理地址的功能，它实现文件名和存放盘块之间的理地址的功能，它实现文件名和存放盘块之间的映射映射目录文件的概念n为了检索目录的方便，把文件名和文件其它信息分开存放。使文件其它信息单独成为一个数据结构，我们把这种用于存放文件描述信息的数据结构称为索引结点，简称i结点。n文件目录中的每个目录项，仅由文件名和指向该文件所对应的i结点的指针构成。 索引结点（i结点）目录文件n搜索目录n创建目录n删除目录n显示目录n修改目录常用的文件目录组织形式：n单级目录结构n两级目录结构n多级树形目录结构目录结构目录结构n文件存储器上保存的全部文件建立一张目录表，

34、每个文件在表中占有一项。单级目录单级目录单级目录结构单级目录结构目录项1目录项2目录项3目录项n文件1文件2文件3文件n目录管理（续）目录管理（续） 文件目录的目录项包含如下一些信息：文件目录的目录项包含如下一些信息：n文件名：由创建者给出的文件名：由创建者给出的1n个字符个字符n文件类型：由文件扩展名给出，例如：文件类型：由文件扩展名给出，例如：.OBJ, EXE,BAS,C，PAS，ADA，n文件组织形式：连续、链接、或索引式文件组织形式：连续、链接、或索引式n文件的物理地址、文件大小、存取权限文件的物理地址、文件大小、存取权限n文件的拥有者：文件的拥有者：n文件的创建、修改和访问日期等等

35、。文件的创建、修改和访问日期等等。 单级目录结构n基本操作基本操作建立一个新文件时，在目录表中增加一个新目录项建立一个新文件时，在目录表中增加一个新目录项撤消一个文件时，删除该文件所对应的目录项撤消一个文件时，删除该文件所对应的目录项访问某个文件时，按文件名顺序查找目录，从而找访问某个文件时，按文件名顺序查找目录，从而找 到对应到对应文件的目录项文件的目录项n优点优点实现了按名存取实现了按名存取目录结构管理简单，它主要用于单用户操作系统目录结构管理简单，它主要用于单用户操作系统n缺点缺点文件多时，目录检索时间长文件多时，目录检索时间长 不允许文件重名不允许文件重名不便于实现文件的共享不便于实现

36、文件的共享n解决文件重名的一个办法是采用两级目录结构。它由一个主文件目录和若干个用户文件目录组成。n主文件目录中，每个用户目录文件都占有一个目录项，包括用户名和指向该用户目录文件的指针。n二级目录中，用户可以建立自己的文件目录。两级目录结构用户名用户名WangZhangGao指向子目录指针指向子目录指针Wang的用户目录的用户目录AlphaTestAlphaTestReportTestZhang的用户目录的用户目录ReportTestGao的用户目录的用户目录BetaDeviceMisxBetaDeviceMisx两级目录结构两级目录结构 主目录主目录两级目录结构n基本操作基本操作当一个新用户

37、开始使用文件系统时，系统为其在主文件目录当一个新用户开始使用文件系统时，系统为其在主文件目录表中找一个空表目，并为其分配一个存放用户文件目录的区表中找一个空表目，并为其分配一个存放用户文件目录的区域，然后把用户名和该区域的起始地址填写在该对应表目中。域，然后把用户名和该区域的起始地址填写在该对应表目中。用户建立一个新文件时，文件系统先按用户名在主目录中找用户建立一个新文件时，文件系统先按用户名在主目录中找到他的文件目录的地址，然后在用户目录表中为其建立一个到他的文件目录的地址，然后在用户目录表中为其建立一个目录项，填上文件名以及文件的管理和控制信息。目录项，填上文件名以及文件的管理和控制信息。

38、用户要访问他的一个文件时，先按用户名在主目录中找到他用户要访问他的一个文件时，先按用户名在主目录中找到他的文件目录位置，然后按文件名在用户文件目录中找到文件的文件目录位置，然后按文件名在用户文件目录中找到文件的有关信息，最后完成指定的文件操作。的有关信息，最后完成指定的文件操作。用户要撤消一个文件时，先按用户名在主目录中找到他的文用户要撤消一个文件时，先按用户名在主目录中找到他的文件目录位置，然后按文件名在用户文件目录中找到文件的目件目录位置，然后按文件名在用户文件目录中找到文件的目录项，释放文件所占用的块并撤消该目录项。当系统要撤消录项，释放文件所占用的块并撤消该目录项。当系统要撤消该用户时

39、，系统将该用户在主目录表中的目录项撤消。该用户时，系统将该用户在主目录表中的目录项撤消。 两级目录结构n两级目录结构的优点：两级目录结构的优点：解决了文件的重名（用户名解决了文件的重名（用户名| |文件名）问题和文件共享问题；文件名）问题和文件共享问题；降低了文件查找时间。降低了文件查找时间。不同用户可以使用不同的文件名访问系统中的同一个共享文不同用户可以使用不同的文件名访问系统中的同一个共享文件。件。n缺点：缺点：增加了系统空间开销。增加了系统空间开销。两级目录结构多级目录结构 n现代操作系统向用户提供现代操作系统向用户提供了功能更强，更加灵活的了功能更强，更加灵活的目录结构，就是层次式的目

40、录结构，就是层次式的目录结构，也叫树形目录目录结构，也叫树形目录结构。结构。n和二级目录类似，它有一和二级目录类似，它有一个主目录个主目录(又称根目录又称根目录)，在根目录下又有许多子目在根目录下又有许多子目录（树枝节点）和普通文录（树枝节点）和普通文件的记录（树叶节点），件的记录（树叶节点），每个子目录下依次也有许每个子目录下依次也有许多子目录或普通文件作为多子目录或普通文件作为其目录项。其目录项。 ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a89多级目录结构多级目录结构 路径名：也称绝对路径名，在树形目录结构中，路径名：也称

41、绝对路径名，在树形目录结构中， 从根从根目录到任何数据文件，目录到任何数据文件， 都只有一条惟一的通路。都只有一条惟一的通路。 在在该路径上从树的根该路径上从树的根( (即主目录即主目录) )开始，开始， 把全部目录文件把全部目录文件名与数据文件名，依次地用名与数据文件名，依次地用“/”/”连接起来，连接起来， 即构成即构成该数据文件的路径名该数据文件的路径名(path name)(path name)。 系统中的每一个系统中的每一个文件都有惟一的路径名。如：文件都有惟一的路径名。如：A/A/C/11A/A/C/11当前目录：用户根据自己的工作情况，在一段时间内，当前目录：用户根据自己的工作情

42、况，在一段时间内，指定某一级的一个目录作为当前目录。指定某一级的一个目录作为当前目录。相对路径名：从当前目录开始直到数据文件为止所构相对路径名：从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名成的路径名，称为相对路径名多级目录结构中的路径 n优点：优点：层次结构清晰，解决重名问题；层次结构清晰，解决重名问题；有利于文件分类；有利于文件分类；提高文件检索速度。提高文件检索速度。n缺点：缺点：管理复杂管理复杂按路径名逐层查找文件，需多次访问磁盘，影响速度按路径名逐层查找文件，需多次访问磁盘，影响速度 多级目录结构 6.5 文件存储空间的管理 （空闲磁盘空间的管理）n由于磁盘容量大，价格

43、便宜，计算机广泛地采用磁盘由于磁盘容量大，价格便宜，计算机广泛地采用磁盘作为文件的存贮器。作为文件的存贮器。n文件管理要解决的问题之一是如何为新创建的文件分文件管理要解决的问题之一是如何为新创建的文件分配存储空间。配存储空间。n文件存文件存储储器存器存储储空间的管理主要包括：空间的管理主要包括：为记录存储空间应设置相应的数据结构。为记录存储空间应设置相应的数据结构。提供对存储空间分配和回收算法。提供对存储空间分配和回收算法。n两种分配方式：连续分配和离散分配两种分配方式：连续分配和离散分配n文件存储空间的基本分配单位是磁盘块。文件存储空间的基本分配单位是磁盘块。空闲磁盘空间的管理n空闲分区表n

44、空闲分区链表n位示图n成组链接法空闲分区表n系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，其中包括空闲区的序号、第一个空闲盘块号、空闲盘块数等信息。 序号序号第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数12429331554空闲分区表空闲分区表空闲分区表n空闲分区表适合于可变大小分区的连续分配方式n为文件分配存储空间时，可以采用首次适应算法、循环首次适应算法、最佳适应算法查找空闲分区。n然后将该分区分配给文件，同时修改空闲分区表，删除相应表项。n当删除文件释放出空间时，系统回收其存储空间，并合并相邻空闲分区。空闲分区表n实现简单n但是，当存储空间中的空闲分区分布较分散

45、且数量较多时，空闲分区表将会很大，需要很大的内存空间，会降低空闲分区表的检索速度。n对于非连续存储的文件，合并空闲分区的操作并非必须，反而会影响其效率。n用专门的空闲分区表登记空闲分区信息会浪费一定的存储空间，而且不适合登记分散且数目很多的空闲分区，不利于基于存储块的链接文件和索引文件的存储空间分配。n可以通过指针将各个空闲分区连接起来，并记载各空闲分区大小，称为空闲分区链表。空闲分区链表 5 4 18 2 0 1 headn将外存中的所有空闲盘区链接起来，成为一个空闲链表 空闲盘块链 ：如果将磁盘上的所有空闲空间，以盘块为单位形成一条链，得到的是空闲盘块链。当为用户文件分配存储空间时，系统从

46、链首开始，依次取下适当数目的空闲盘块分配给该用户文件，当用户释放存储空间时，系统将回收的盘块依次插入链表的末尾。空闲盘区链：将磁盘上的所有空闲空间，以盘区为单位形成一条链，得到的是空闲盘区链。由于组成盘区的空闲盘块数目不定，因此链中的每个结点除有指向下一个盘区的指针之外，还要指明本结点的空闲盘块数。空闲分区链表n空闲分区链表适合于各种文件分配方法n如果基于存储块分配，则可以取空闲分区链的第一个存储块进行分配，并调整空闲分区链首指针和分区大小。n如果基于可变分区分配，可以采用首次适应算法，从链表头开始查找，找到的第一个适合的分区分配。然后，调整空闲分区链首指针和分区大小。n当删除文件释放存储空间

47、时，系统回收其存储空间，并将回收的分区链接到空闲分区链表中。空闲分区链表n一段时间后，可能会使空闲分区链表中包含太多小分区，使文件分配到的存储空间过分离散。n由于空闲分区长度等信息保存在存储块中，每次将存储块分配出去写入文件数据之前，必须首先读出其中的有关空闲分区信息，否则将丢失链接指针。如果一个文件需要很多空闲分区，这种操作模式将大大降低文件存储速度。空闲分区链表：问题n删除一个由许多离散小分区组成的文件时，将回收的小分区链接到空闲分区链表中需要很长时间。n若一个文件申请连续存储空间，则需要花费较长的时间查找相邻的空闲分区。n因此，这种空闲空间组织方法适合于非连续存储文件。空闲分区链表：问题

48、n位示图使用一个位向量(二进制中的一位)来表示磁盘中一个盘块的使用情况。n由所有存储块对应的位构成一个向量，称为位示图。n具有n个磁盘块的磁盘，其位示图有n位。图中为0的位对应于空闲块，为1的位对应于已被占用的块。n位示图可以描述为一个二维数组位示图位示图位示图 位示图n盘块的分配步骤：（1）顺序扫描位示图，从中找出一个或一组其值为0的二进制位；（2）通过映射关系找到这些二进制位所对应的盘块号；（3）修改位示图，对应位由0变为1。n盘块的回收步骤（1）回收盘块的盘块号转换成位示图中的行号和列号；（2）修改位示图，对应位由1变为0 。位示图n一个位示图需要占用的存储空间大小为： 磁盘容量（字节数

49、）/（8*数据块大小）n对于较小的磁盘，位示图占用的空间会很小。例如：一个20M的磁盘，每个盘块为1k字节时，它要求的映象表占20k位。这个表仅占3个盘块。 20k位/8=20*128字节 20*128字节/1k=2.5块3块 n但是，对于一个16GB的磁盘，若数据块大小为512字节，则位示图大小为4MB，大约需要占用8000个磁盘块的存储空间。很难一次性将该位示图全部装入内存。位示图n即使内存足够大，可以存放全部或绝大部分位示图数据，搜索一个很大的位示图将会降低文件系统的性能。n尤其当磁盘空间快用完，剩下的空闲磁盘块很少时，文件系统的性能将严重降低。位示图成组链接法 n空闲表法和空闲链表法，都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。n成组链接法是将上述两种方法结合而形成的一种空闲盘块管理方法，它兼顾了上述两种方法的优点而客服了两种方法均有的表太长的缺点。成组链接法 1004003993013001003002992022012991004003992013019907999790179007899780179997901空 闲 盘 块 号栈S.free019899n当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。n该过程首先从栈顶取出一空闲盘块号，将与之对应的盘块分配给