第6章-文件系统要点课件.ppt

1、第六章 文件管理 信息是计算机系统中的重要资源，操作系统信息是计算机系统中的重要资源，操作系统中的一个重要组成部分，文件系统，负责信中的一个重要组成部分，文件系统，负责信息的组织、存储和访问。文件系统的功能就息的组织、存储和访问。文件系统的功能就是提供高效、快速和方便的信息存储和访问是提供高效、快速和方便的信息存储和访问功能。功能。 文件管理的目的文件管理的目的: (1) 方便的文件访问和控制：以符号名称作为文件方便的文件访问和控制：以符号名称作为文件标识，便于用户使用；标识，便于用户使用； (2) 并发文件访问和控制：在多道程序系统中支持并发文件访问和控制：在多道程序系统中支持对文件的并发访

2、问和控制；对文件的并发访问和控制； (3) 统一的用户接口：在不同设备上提供同样的接统一的用户接口：在不同设备上提供同样的接口，方便用户操作和编程；口，方便用户操作和编程； (4) 多种文件访问权限：在多用户系统中的不同用多种文件访问权限：在多用户系统中的不同用户对同一文件会有不同的访问权限；户对同一文件会有不同的访问权限； (5) 优化性能：存储效率、检索性能、读写性能；优化性能：存储效率、检索性能、读写性能； (6) 差错恢复：能够验证文件的正确性，并具有一差错恢复：能够验证文件的正确性，并具有一定的差错恢复能力；定的差错恢复能力；6.1 6.1 文件和文件系统文件和文件系统 6.1.1

3、6.1.1 文件、记录和数据项文件、记录和数据项 1 1、数据项、数据项 （1 1）基本数据项）基本数据项 ：可命名的最小数据单位，：可命名的最小数据单位，原子数据，有数据类型。原子数据，有数据类型。-数据库中的字段。数据库中的字段。如：学号、姓名、年龄等。如：学号、姓名、年龄等。 （2 2）组合数据项：由若干数据项组成，如工）组合数据项：由若干数据项组成，如工资。资。 2 2、记录：一组相关数据项集合，用于描述一、记录：一组相关数据项集合，用于描述一个对象在某方面的属性。主关键字（关键字）个对象在某方面的属性。主关键字（关键字）用于标识一个记录。用于标识一个记录。 3 3、文件、文件 文件：

4、文件：由创建者定义，具有文件名的一组相由创建者定义，具有文件名的一组相关元素的集合。文件名是文件的标识符号。关元素的集合。文件名是文件的标识符号。 有结构文件由若干相关记录组成；无结构文有结构文件由若干相关记录组成；无结构文件被看成是一个字符流。件被看成是一个字符流。 文件包括两部分：文件包括两部分：文件体：文件本身的信息；文件体：文件本身的信息；文件属性：文件存储和管理信息；如：文文件属性：文件存储和管理信息；如：文件名、文件内部标识、文件存储地址、访件名、文件内部标识、文件存储地址、访问权限、访问时间等；问权限、访问时间等； 文件属性：文件属性： （1 1） 文件类型文件类型 （2 2）

5、文件长度文件长度 （3 3） 文件的物理位置文件的物理位置 （4 4） 文件的存取控制文件的存取控制 （5 5） 文件的创建人、创建时间、修文件的创建人、创建时间、修改时间改时间6.1.2 文件类型文件类型 多种分类法：多种分类法： 1 1）用途：系统文件、用户文件、库文件）用途：系统文件、用户文件、库文件 2 2）文件中的数据形式：源文件、目标文件、）文件中的数据形式：源文件、目标文件、可执行代码文件。可执行代码文件。 3 3）存取属性：只执行文件、只读文件、读写）存取属性：只执行文件、只读文件、读写文件文件 4 4）文件逻辑结构：有结构文件（记录、数据）文件逻辑结构：有结构文件（记录、数据

6、项）、无结构文件（流式文件）项）、无结构文件（流式文件） 5 5）文件的存储结构：顺序文件、链接文件、）文件的存储结构：顺序文件、链接文件、索引文件索引文件6.1.3 文件操作 1. 1. 最基本的文件操作最基本的文件操作 （1 1）创建文件：分配外存空间，在文件系统）创建文件：分配外存空间，在文件系统的目录中建立一个目录项。的目录中建立一个目录项。 （2 2）删除文件：在目录中找到要删除文件的）删除文件：在目录中找到要删除文件的目录项并删除，同时回收空间。目录项并删除，同时回收空间。 （3 3）读文件：应用进程调用系统调用，系统）读文件：应用进程调用系统调用，系统查找该文件的目录项，确定外存

7、地址，目录查找该文件的目录项，确定外存地址，目录项中有读写指针。项中有读写指针。 （4 4）写文件：类似读文件。）写文件：类似读文件。 （5 5）截断文件：将目录项中文件的长度属性）截断文件：将目录项中文件的长度属性改为零，其它属性保留。改为零，其它属性保留。 （6 6）设置读写位置：前面的读写操作每次从）设置读写位置：前面的读写操作每次从文件的起始位置读写。本操作用于设置读写文件的起始位置读写。本操作用于设置读写指针，从需要位置开始。即将顺序存取改为指针，从需要位置开始。即将顺序存取改为随机存取。随机存取。 2. 2. 文件的打开和关闭操作文件的打开和关闭操作 打开：系统将指定文件的目录项复

8、制到内存打开：系统将指定文件的目录项复制到内存中打开文件表中为其建立一个表目，并将该中打开文件表中为其建立一个表目，并将该表目的编号（索引号）返回给进程。避免多表目的编号（索引号）返回给进程。避免多次访问外存获取文件属性信息。次访问外存获取文件属性信息。 关闭：将内存中对应的文件表目复制到外存关闭：将内存中对应的文件表目复制到外存目录表中，从内存打开文件表中删除对应的目录表中，从内存打开文件表中删除对应的目录项。目录项。 3. 其它文件操作其它文件操作 以系统调用的形式提供给用户，有：以系统调用的形式提供给用户，有： 1）关于文件属性的操作：改变文件名、改）关于文件属性的操作：改变文件名、改变

9、文件所有者、改变文件的访问权限等。变文件所有者、改变文件的访问权限等。 2）有关目录操作的：创建目录、删除目录）有关目录操作的：创建目录、删除目录等。等。 3）实现文件共享的操作）实现文件共享的操作 例：若一个用户进程通过例：若一个用户进程通过read系统调用读取系统调用读取磁盘文件，则下列关于此过程的叙述正确的磁盘文件，则下列关于此过程的叙述正确的是是 1. 若该文件的数据不在内存，则该进程进入若该文件的数据不在内存，则该进程进入睡眠等待状态睡眠等待状态 2. 请求请求read系统调用会导致系统调用会导致CPU从用户态从用户态切换到核心态。切换到核心态。 3. read系统调用的参数应该包含

10、文件的名称。系统调用的参数应该包含文件的名称。 3是错的，因为要先是错的，因为要先open得到一个文件句柄，得到一个文件句柄，之后有关文件的系统调用都用这个句柄。之后有关文件的系统调用都用这个句柄。6.2 文件逻辑结构 1. 1. 文件的逻辑结构（文件的逻辑结构（File Logical File Logical StructureStructure）: : 也称文件的组织（也称文件的组织（File OrganizationFile Organization），），是指从用户观点出发讨论文件组织结构，是是指从用户观点出发讨论文件组织结构，是用户可直接处理的数据及结构，独立于文件用户可直接处理的

11、数据及结构，独立于文件的物理特性。的物理特性。 文件逻辑结构的设计要求文件逻辑结构的设计要求： 访问性能：便于检索；便于修改访问性能：便于检索；便于修改 存储性能：向物理存储转换方便，节省空间存储性能：向物理存储转换方便，节省空间 2 2文件的物理结构：又称文件的存储结构，文件的物理结构：又称文件的存储结构，文件在外存上组织形式，与存储介质的存储文件在外存上组织形式，与存储介质的存储性能有关。性能有关。6.2.1 文件逻辑结构的类型 1 1、有结构文件、有结构文件记录式文件记录式文件 （1 1） 定长记录：寻址简单定长记录：寻址简单 （2 2） 变长记录：变长记录： 数据项数目不同：如论文中的

12、关键词等。数据项数目不同：如论文中的关键词等。 数据项本身长度不定，如病历中的病史。数据项本身长度不定，如病历中的病史。 有结构文件的组织方式：有结构文件的组织方式： （1 1）顺序文件：文件中的记录按照某种顺序排列，）顺序文件：文件中的记录按照某种顺序排列，适合于定长记录文件适合于定长记录文件 （2 2）索引文件：若记录长度可变，则建立一张索）索引文件：若记录长度可变，则建立一张索引表，每个记录一个表项，加快检索。引表，每个记录一个表项，加快检索。 （3 3）索引顺序文件：建立索引表，一组记录一个）索引顺序文件：建立索引表，一组记录一个表项表项 2 2、无结构文件、无结构文件 文件体为字节流

13、，不划分记录，顺序访问，文件体为字节流，不划分记录，顺序访问，每次读写访问可以指定任意数据长度，系统每次读写访问可以指定任意数据长度，系统不对文件进行格式处理，即流式文件。在不对文件进行格式处理，即流式文件。在UNIX系统中，所有文件（有结构或无结构）系统中，所有文件（有结构或无结构）都看成是流式文件。都看成是流式文件。6.2.2 顺序文件 (sequential file) 1 1、逻辑记录的排序、逻辑记录的排序 文件中的记录可按照任意顺序排序，分两种文件中的记录可按照任意顺序排序，分两种情况：情况： （1 1）串结构：记录顺序与关键字无关，存入）串结构：记录顺序与关键字无关，存入时间决定顺

14、序时间决定顺序 （2 2）顺序结构：记录按关键字排序，检索效）顺序结构：记录按关键字排序，检索效率高。率高。 顺序结构比串结构有更高的检索效率。顺序结构比串结构有更高的检索效率。 2 2、对顺序文件的读写：、对顺序文件的读写： （1 1） 定长记录：设置读或写指针每次读定长记录：设置读或写指针每次读/ /写写一个记录后一个记录后 ptrptr = = ptr+Lptr+L 使指针指向下一使指针指向下一个记录。个记录。 （2 2）变长记录：设置读或写指针每次读）变长记录：设置读或写指针每次读/ /写写一个记录后一个记录后 ptrptr = = ptr+Lptr+Li i 使指针指向下一使指针指向

15、下一个记录。个记录。 3 3、顺序文件的优缺点、顺序文件的优缺点 优点：批量处理数据，快！介质：磁带。优点：批量处理数据，快！介质：磁带。 缺点：对单个记录处理困难，插入或删除尤缺点：对单个记录处理困难，插入或删除尤其如此。其如此。6.2.3 索引文件(indexed file) 记录大小不必相同，不必排序，存放在主文记录大小不必相同，不必排序，存放在主文件件( (primary file)primary file)中。另外建立一张索引表，中。另外建立一张索引表，每个记录在表中对应一个索引项，索引项按每个记录在表中对应一个索引项，索引项按照记录中的某个关键字域排序。对同一主文照记录中的某个关键

16、字域排序。对同一主文件，可以针对不同的关键字域建立多个索引件，可以针对不同的关键字域建立多个索引表（注意：和多级索引并不相同）。索引文表（注意：和多级索引并不相同）。索引文件的记录项通常较小，查找速度快，便于随件的记录项通常较小，查找速度快，便于随机访问机访问( (random access)random access)。索引号索引号长度长度指针指针0m01m1.R0R1Ri索引表索引表逻辑文件逻辑文件6.2.4 6.2.4 索引顺序文件索引顺序文件 (indexed-sequential file) 是顺序文件和索引文件结合的产物。是顺序文件和索引文件结合的产物。 将顺序文件中的所有记录分为

17、若干组；为顺将顺序文件中的所有记录分为若干组；为顺序文件建立一张索引表，每组的第一个记录序文件建立一张索引表，每组的第一个记录在索引表中有对应表项。在索引表中有对应表项。 查找任意记录时，先据关键字查索引表（此查找任意记录时，先据关键字查索引表（此时可采用各种查找算法），找到所在组的第时可采用各种查找算法），找到所在组的第一个记录，之后顺序查找该组。一个记录，之后顺序查找该组。关键字逻辑地址姓名其它属性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件顺序文件6.2.5 6.2.5 直接文件和哈希文件直接文件和哈希文件 ( (hashed f

18、ilehashed file） 1. 直接文件直接文件 前面几种文件结构对记录进行存取时，都须前面几种文件结构对记录进行存取时，都须利用给定的记录键值，先对线性表或链表进利用给定的记录键值，先对线性表或链表进行检索，以找到指定记录的物理地址。行检索，以找到指定记录的物理地址。 直接文件是根据记录的键值直接就可获得记直接文件是根据记录的键值直接就可获得记录的物理地址。录的物理地址。 组织直接文件的关键在于实现从键值到物理组织直接文件的关键在于实现从键值到物理地址的转换。地址的转换。 2. 哈希文件哈希文件 哈希文件是应用最广泛的一种直接文件。哈希文件是应用最广泛的一种直接文件。 记录位置由哈希函

19、数确定。检索时给出记录记录位置由哈希函数确定。检索时给出记录键值，通过哈希函数计算出该记录在文件中键值，通过哈希函数计算出该记录在文件中的相对位置，通常是一个目录表中的表项，的相对位置，通常是一个目录表中的表项，该表目的内容指向相应记录所在的物理块。该表目的内容指向相应记录所在的物理块。 访问速度最快，但在主文件中有空闲空间浪访问速度最快，但在主文件中有空闲空间浪费。费。6.3 外存分配方式（文件实现） 目的：目的： （1）提高存储空间的利用率）提高存储空间的利用率 （2）提高文件的访问速度）提高文件的访问速度6.3.1 连续分配 每个文件分配一组相邻接的盘块，也称物理每个文件分配一组相邻接的

20、盘块，也称物理顺序文件。顺序文件。 主要问题：随着使用，磁盘碎片增多，性能主要问题：随着使用，磁盘碎片增多，性能下降，需要磁盘整理。下降，需要磁盘整理。 优点：顺序访问速度快，定位容易，只需记优点：顺序访问速度快，定位容易，只需记录第一个簇的位置。可以通过紧缩录第一个簇的位置。可以通过紧缩(compact)将外存空闲空间合并成连续的区将外存空闲空间合并成连续的区域。域。 缺点：需要连续的空间，当文件长度变化难缺点：需要连续的空间，当文件长度变化难于处理，即必须事先知道文件的长度。于处理，即必须事先知道文件的长度。连续分配连续分配6.3.2 链接分配 1、隐式链接、隐式链接 分配给文件的盘块不连

21、续，在每个簇中有指分配给文件的盘块不连续，在每个簇中有指向下一个簇的指针。目录中只存放第一和最向下一个簇的指针。目录中只存放第一和最后一块的簇号（盘块号）。后一块的簇号（盘块号）。 解决顺序文件的离散存储的问题。解决顺序文件的离散存储的问题。 链接分配只适合于顺序访问，随机访问效率链接分配只适合于顺序访问，随机访问效率差，可靠性差。差，可靠性差。链接分配链接分配 2、显示链接、显示链接 指针单独存放在一张表中，称文件分配表指针单独存放在一张表中，称文件分配表（FAT），），与文件对应的目录项中存放文件与文件对应的目录项中存放文件首块的地址，表中的序号与物理块号对应。首块的地址，表中的序号与物理

22、块号对应。文件分配表文件分配表 文件存储单位：簇（文件存储单位：簇（cluster）簇又称为部簇又称为部分分(portion) 文件的存储空间通常由多个独立的簇组成，而文件的存储空间通常由多个独立的簇组成，而每个簇包含若干个连续的外存存储单位（如扇每个簇包含若干个连续的外存存储单位（如扇区区sector），），如何确定每个簇的大小？如何确定每个簇的大小？ （1）簇的大小）簇的大小 两个极端：大到能容纳整个文件，小到一两个极端：大到能容纳整个文件，小到一个外存存储块（一个扇区）个外存存储块（一个扇区） 簇较大：提高簇较大：提高I/O访问性能，减小管理开销访问性能，减小管理开销 簇较小：簇内的碎片

23、浪费较小，特别是大量簇较小：簇内的碎片浪费较小，特别是大量小文件时有利。小文件时有利。簇的大小簇的大小 (2) 主要方法：两种主要方法：两种簇大小可变，其上限较大：簇大小可变，其上限较大：I/O访问性能访问性能较好。但簇大小可变，文件存储空间的管较好。但簇大小可变，文件存储空间的管理困难，因为要指明每个簇的尺寸。理困难，因为要指明每个簇的尺寸。簇大小固定，较小：文件存储空间使用灵簇大小固定，较小：文件存储空间使用灵活，但活，但I/O访问性能下降，文件管理所需访问性能下降，文件管理所需空间开销较大空间开销较大6.3.3 索引分配 1、单级索引（直接索引）、单级索引（直接索引） 为每个文件分配一个

24、索引块。记录分配给该为每个文件分配一个索引块。记录分配给该文件的所有盘块号，文件目录项中记录该索文件的所有盘块号，文件目录项中记录该索引块的盘块号。引块的盘块号。 问题：浪费外存空间，对小文件尤其如此。问题：浪费外存空间，对小文件尤其如此。索引分配索引分配 例：某文件系统的最大容量为例：某文件系统的最大容量为4TB，以磁盘，以磁盘块为基本分配单位，盘块大小为块为基本分配单位，盘块大小为1KB。FCB包含一个包含一个512B的索引表区。的索引表区。 （1）假设索引表区采用直接索引，索引表）假设索引表区采用直接索引，索引表区存放文件占有的磁盘块号。索引表项中块区存放文件占有的磁盘块号。索引表项中块

25、号最少占用多少字节？可支持的单个文件的号最少占用多少字节？可支持的单个文件的最大长度是多少字节？最大长度是多少字节？ 磁盘最多盘块数：磁盘最多盘块数：4TB / 1KB =2 32 所以需要所以需要4字节存放盘块号。字节存放盘块号。 文件最大长度文件最大长度 512/4 1KB 128KB (2) 假设索引表采用如下结构：第假设索引表采用如下结构：第07字节字节采用采用格式表示文件创建格式表示文件创建时预分配的连续存储空间，其中起始块号占时预分配的连续存储空间，其中起始块号占4B，块数占，块数占2B；剩余；剩余504B采用直接索引结采用直接索引结构，一个索引项占构，一个索引项占6B，则可支持的

26、单个文件，则可支持的单个文件最大长度是多少？为了使单个文件的长度达最大长度是多少？为了使单个文件的长度达到最大，请指出起始块号和块数分别占用字到最大，请指出起始块号和块数分别占用字节数的合理值并说明理由。节数的合理值并说明理由。 块数占块数占2B，单个文件的最大长度，单个文件的最大长度 2161KB 504/6 1KB65620KB 只要块数在只要块数在4B以上就可以表示连续以上就可以表示连续232个块，个块，使文件达到最大使文件达到最大4TB。 2、多级索引、多级索引 对于大文件，一个块装不下所有索引，需要对于大文件，一个块装不下所有索引，需要多个块。索引块之间的关系：链接；再多个块。索引块

27、之间的关系：链接；再创建索引，即索引块的索引创建索引，即索引块的索引多级索引。多级索引。多级索引分配多级索引分配outer-indexindex tablefiledirectory 3、混合方式、混合方式 如：如：BSD UNIX ，在一个文件索引结点中有，在一个文件索引结点中有如下内容：如下内容： （1） 直接地址：直接地址：10个，每个直接指向文件个，每个直接指向文件簇（簇（4KB），），即文件大小最大为即文件大小最大为40KB。 （2） 一级间接索引：一级间接索引：1个，指向下一级索个，指向下一级索引块，一个索引块存放引块，一个索引块存放1K个簇号，即个簇号，即4MB空间，此时文件的大

28、小最大为：空间，此时文件的大小最大为：4MB+40KB。 （3） 二级间接索引：二级间接索引：1个，个，1K个一级索引个一级索引块：块：1K*1K*4KB=4GB。 （4）三级间接索引：）三级间接索引：1个，个，1K个两次间接个两次间接索引，索引，1K*4GB=4TB。UNIX 混合文件存储方案混合文件存储方案 例：设文件索引节点中有例：设文件索引节点中有7个地址项，其中个地址项，其中4个地址项是直接地址索引，个地址项是直接地址索引，2个地址项是一个地址项是一级间接索引，级间接索引，1个地址项是二级间接索引，个地址项是二级间接索引，每个地址项大小为每个地址项大小为4B。若磁盘索引块和磁盘。若磁

29、盘索引块和磁盘数据块大小均为数据块大小均为256B，则可表示的单个文，则可表示的单个文件的最大长度是件的最大长度是 答：答： 1057KB 例题：例题： 某文件由某文件由100个盘块构成。设文件的目录项个盘块构成。设文件的目录项已在内存（若为索引分配，其索引块也在内已在内存（若为索引分配，其索引块也在内存）。计算对于连续、链接和索引分配下列存）。计算对于连续、链接和索引分配下列操作要多少次磁盘操作要多少次磁盘I/O。设在连续分配中，。设在连续分配中，文件头前无空闲盘块，文件末尾有。若写磁文件头前无空闲盘块，文件末尾有。若写磁盘，则要写的内容已在内存。文件中间盘块盘，则要写的内容已在内存。文件中

30、间盘块为第为第50个盘块。个盘块。 （1）在文件头增加一块）在文件头增加一块 （2）在文件中间增加一块）在文件中间增加一块 （3）在文件末尾增加一块）在文件末尾增加一块 （4）从文件头部删除一块）从文件头部删除一块 （5）从文件中间删除一块）从文件中间删除一块 （6）从文件末尾删除一块）从文件末尾删除一块 连续分配连续分配 a. 201 b. 101 c. 1 d. 0 ( reset the files starting location to be the current location plus 1 blocks.) e. 100 f. 0 ( just reset the size

31、of the file to be one block smaller)l链接分配链接分配la. 1 b. 52 each of the first 50 blocks would have to be read to obtain the link to the next block and 50 st block has to be rewritten. c. 3 or 102 d. 1 read the first block and extract its link. Store it in the directory. e. 51 f. 100 索引分配索引分配 a. 1 each

32、pointer in the index block must be moved down one location. Then a new pointer must be added at the beginning. Since the index blocks reside in memory. No I/O operations are needed except to write the new block. b. 1 c. 1 d. 0 e. 0 f. 0 例：下列文件物理结构中，适合随机访问且例：下列文件物理结构中，适合随机访问且易于文件扩展的是易于文件扩展的是 A 连续结构连续

33、结构 B 索引结构索引结构 C 链式结构且磁盘块定长链式结构且磁盘块定长 D 链式结构且磁盘块变长链式结构且磁盘块变长6.4 目录管理 目录是由文件说明组成的用于文件检索的一目录是由文件说明组成的用于文件检索的一个个特殊文件特殊文件。它是一种数据结构，用于标识。它是一种数据结构，用于标识系统中的所有文件及其物理地址。系统中的所有文件及其物理地址。 目录管理要求实现：目录管理要求实现： （1 1） 按名存取按名存取 （2 2） 快速检索：合理组织目录结构快速检索：合理组织目录结构 （3 3） 文件共享文件共享 （4 4） 文件重名的解决文件重名的解决6.4.1 文件控制块和索引节点 1 1、 文

34、件控制块（文件控制块（File Control BlockFile Control BlockFCBFCB） FCBFCB是文件存在的标识，是文件存在的标识，FCBFCB记录了系统对于记录了系统对于文件进行管理所需要的全部信息。文件进行管理所需要的全部信息。 一个文件控制块保存在文件目录中，作为一一个文件控制块保存在文件目录中，作为一个目录项。个目录项。 FCBFCB包含如下信息：包含如下信息： （1 1） 基本信息类基本信息类 文件名：字符串，通常在不同系统中允许文件名：字符串，通常在不同系统中允许不同的最大长度。可以修改。有些系统允许不同的最大长度。可以修改。有些系统允许同一个文件有多个别

35、名同一个文件有多个别名( (alias)alias)； 别名的数目；别名的数目； 文件的物理位置：文件的物理位置：文件卷或文件卷或设备号设备号盘块号盘块号盘块数（文件长度）盘块数（文件长度） 文件逻辑结构：记录式或流式等文件逻辑结构：记录式或流式等 文件物理结构：连续分配、链式方式、索文件物理结构：连续分配、链式方式、索引式、引式、 哈希文件哈希文件 （2 2） 存取控制信息类：存取控制信息类： 文件主的存取权限文件主的存取权限 核准用户的存取权限核准用户的存取权限 一般用户的存取权限一般用户的存取权限 （3） 使用信息类使用信息类 文件的建立日期和时间文件的建立日期和时间 文件的修改日期和时

36、间文件的修改日期和时间 当前使用信息：打开的进程数、修改状态当前使用信息：打开的进程数、修改状态等。等。 2 2、 索引节点（索引节点（I-nodeI-node） 1 1）索引节点的引入）索引节点的引入 在在UNIXUNIX中，将文件名和文件描述信息分开存中，将文件名和文件描述信息分开存放，即将放，即将FCBFCB拆分为两部分：拆分为两部分：文件目录部分：文件名字（字符）、索文件目录部分：文件名字（字符）、索引节点编号（指针）引节点编号（指针） I I节点：记录文件描述信息的部分（除节点：记录文件描述信息的部分（除去文件名）的数据结构。去文件名）的数据结构。 好处：加速文件名的检索。好处：加速

37、文件名的检索。 2 2） 磁盘索引节点磁盘索引节点 指存放在磁盘上的指存放在磁盘上的I-nodeI-node，磁盘上每一个文件都有磁盘上每一个文件都有唯一的唯一的I-nodeI-node，主要内容：主要内容： （1 1）文件主标识：拥有文件的个人或小组标识）文件主标识：拥有文件的个人或小组标识 （2 2）文件类型）文件类型 （3 3）文件存取权限）文件存取权限 （4 4）文件物理地址）文件物理地址 （5 5）文件长度）文件长度 （6 6）文件连接计数（共享）：指向该文件名的指）文件连接计数（共享）：指向该文件名的指针计数针计数 （7 7）文件存取时间）文件存取时间 3 3）内存索引节点）内存索

38、引节点当文件打开后，将磁盘上当文件打开后，将磁盘上I-nodeI-node拷贝到内拷贝到内存，以便使用。存，以便使用。除了上述内容，增加的主要内容：除了上述内容，增加的主要内容：（1 1）I-nodeI-node编号，即内存编号，即内存I-nodeI-node标识标识（2 2）状态：）状态：I-nodeI-node是否上锁或被修改等是否上锁或被修改等（3 3）访问计数）访问计数, ,多进程共享多进程共享（4 4）文件所在的逻辑设备号）文件所在的逻辑设备号6.4.2 目录结构 目录结构讨论目录的组织结构，设计目标是目录结构讨论目录的组织结构，设计目标是提高检索效率。提高检索效率。 1. 单级目录

39、结构单级目录结构 整个目录组织是一个线性结构，系统中的所整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中，每个文件占有文件都建立在一张目录表中，每个文件占用一个目录项。它主要用于单用户操作系统。用一个目录项。它主要用于单用户操作系统。 它具有如下的特点：它具有如下的特点：结构简单；结构简单；文件多时，目录检索时间长；文件多时，目录检索时间长；有命名冲突：不允许不同文件有相同的文有命名冲突：不允许不同文件有相同的文件名或一个文件有多个不同的文件名（不件名或一个文件有多个不同的文件名（不同用户对同一文件的命名）；同用户对同一文件的命名）；共享困难共享困难 2. 两级目录结构两级目录

40、结构 在主目录或根目录（第一级目录）下，每个在主目录或根目录（第一级目录）下，每个用户对应一个用户文件目录（第二级目录），用户对应一个用户文件目录（第二级目录），在用户目录下是该用户的文件，而不再有下在用户目录下是该用户的文件，而不再有下级目录。适用于多用户系统，各用户可有自级目录。适用于多用户系统，各用户可有自己的专用目录。己的专用目录。 优点优点： （1） 可以重名可以重名 （2） 提高检索速度提高检索速度 （3） 不同用户可使用不同的文件名来访不同用户可使用不同的文件名来访问系统中的同一个共享文件。问系统中的同一个共享文件。 3 3、多级目录多级目录 树状目录树状目录(tree-like

41、)或称为多级目录。在文或称为多级目录。在文件数目较多时，便于系统和用户将文件分散件数目较多时，便于系统和用户将文件分散管理。适用于较大的文件系统管理。目录级管理。适用于较大的文件系统管理。目录级别太多时，会增加路径检索时间。别太多时，会增加路径检索时间。ABC根目录EPABDFEDBGAEHIJKABCDELMNA 树型目录的优点：树型目录的优点：层次和隶属关系清晰，便于实现不同级别层次和隶属关系清晰，便于实现不同级别的存取保护和文件卷的动态装卸。的存取保护和文件卷的动态装卸。4. 4. 无循环图（无循环图（acyclic graphacyclic graph）目录）目录 无环图目录允许不同用

42、户共享子目录无环图目录允许不同用户共享子目录和文件。和文件。 共享文件（目录）不同于文件拷贝，系统中共享文件（目录）不同于文件拷贝，系统中只存在一个真正的文件，所有对文件的任何只存在一个真正的文件，所有对文件的任何改变都会被其他用户所见。改变都会被其他用户所见。 OS要确保无环图结构中没有环。这样可用简要确保无环图结构中没有环。这样可用简单的算法遍历目录结构并确定是否存在文件单的算法遍历目录结构并确定是否存在文件共享。共享。OS不希望多次遍历共享部分。不希望多次遍历共享部分。 有些算法可以检测图中的环，有些算法可以检测图中的环，每次建立新链每次建立新链接时执行环检查算法，如果没有环则可以设接时

43、执行环检查算法，如果没有环则可以设置链接置链接. 但由于目录结构位于磁盘上，算法运行费时。但由于目录结构位于磁盘上，算法运行费时。5. 5. 通用图目录通用图目录 通用图结构允许存在环。通用图结构允许存在环。 要避免遍历目录时多次搜索同一部分，限制要避免遍历目录时多次搜索同一部分，限制搜索时访问目录的次数。搜索时访问目录的次数。6.4.3 目录查询技术 当用户访问一个已存在文件时：当用户访问一个已存在文件时： 目录查询目录查询- -FCB(I-node)-FCB(I-node)-文件的物理地文件的物理地址（盘块号）址（盘块号）- -文件的物理位置（柱面、磁文件的物理位置（柱面、磁头号、扇区号）

44、。头号、扇区号）。 查寻方法：查寻方法：线性查询线性查询HashHash方法方法例如查询文件mbox的物理地址（盘块号），已知路径为：/usr/ast/mbox根目录114714968.bindevlibetcusrtmp节点6中查找usr字段节点6是/usr目录的I-node132132#快是/usr的目录61193051264580.dickerikjimastbaljack节点26是/usr/ast目录的I-node496406#快是/usr/ast的目录266649260811768.greeblckmboxradsrcexe 例：文件系统中，文件访问控制信息存储的例：文件系统中，文件

45、访问控制信息存储的合理位置是合理位置是 A FCB B FAT C 用户口令表用户口令表 D 系统注册表系统注册表 例：设置当前工作目录的主要目的是：例：设置当前工作目录的主要目的是： A 节省外存空间节省外存空间 B 节省内存空间节省内存空间 C 加快文件检索的速度加快文件检索的速度 D 加快文件的读写速度加快文件的读写速度6.5 文件存储空间的管理 要为新文件分配存储空间，系统必须以某种要为新文件分配存储空间，系统必须以某种数据结构记住存储空间的使用情况。数据结构记住存储空间的使用情况。 外存空闲空间管理的数据结构通常称为磁盘外存空闲空间管理的数据结构通常称为磁盘分配表分配表(disk a

46、llocation table)，分配的基分配的基本单位是簇。本单位是簇。6.5.1 空闲表法和空闲链表法和空闲链表法序号第一（起始）空闲盘块号空闲盘块数首次适应、下次适应首次适应、下次适应( (循环首次适应）、最佳、最循环首次适应）、最佳、最坏。坏。与内存不同，应以连续分配为主。一般采用首次适与内存不同，应以连续分配为主。一般采用首次适应算法，回收时合并。应算法，回收时合并。 1. 1. 空闲表法空闲表法 2 2 空闲链表法空闲链表法 每个空闲簇中有指向下一个空闲簇的指针，每个空闲簇中有指向下一个空闲簇的指针，所有空闲簇构成一个链表。不需要磁盘分配所有空闲簇构成一个链表。不需要磁盘分配表，节

47、省空间。每次申请空闲簇只需取出链表，节省空间。每次申请空闲簇只需取出链表开头的空闲簇即可（即首次适应）。有两表开头的空闲簇即可（即首次适应）。有两种形式：种形式： （1 1） 空闲簇（盘块）链接：以空闲盘块为空闲簇（盘块）链接：以空闲盘块为单位拉成一条链，为文件分配空间时要多次单位拉成一条链，为文件分配空间时要多次操作。操作。 （2）空闲区链接：每个盘区除了有指向下一空闲区链接：每个盘区除了有指向下一个盘区的指针，还应指明本盘区的大小。个盘区的指针，还应指明本盘区的大小。6.5.2 位示图法 1. 1. 位示图位示图( (bitmap)bitmap)：每每一位一位表示一个簇，表示一个簇，取值取

48、值0 0和和1 1分别表示空闲和占用。分别表示空闲和占用。 块磁道12.123101001 2. 盘块的分配盘块的分配 （1）顺序扫描位示图，找到一个或一组空）顺序扫描位示图，找到一个或一组空盘块。盘块。 （2）转换为对应的盘块号，公式如下：）转换为对应的盘块号，公式如下： 块号为块号为b，第第i行，第行，第j列，则列，则b=n*(i-1)+j n 为每行的位数。为每行的位数。 （3）修改位示图。）修改位示图。 3. 盘块的回收：已知盘块号盘块的回收：已知盘块号b，得对应的行，得对应的行列号，之后修改位示图对应位的值。列号，之后修改位示图对应位的值。 i=(b-1) DIV n + 1，j=(

49、b-1) MOD n + 16.5.3 成组链接法 空闲表法和空闲链表法不适应于大型文件系空闲表法和空闲链表法不适应于大型文件系统，因为表会太大。统，因为表会太大。 UNIXUNIX系统采用成组链接法，是空闲表法和空系统采用成组链接法，是空闲表法和空闲链表法的结合闲链表法的结合 1 1、空闲盘块的组织、空闲盘块的组织 （1 1）空闲盘块号栈。用于存放当前可用的一）空闲盘块号栈。用于存放当前可用的一组空闲盘块号，以及栈中尚有的空闲盘块数。组空闲盘块号，以及栈中尚有的空闲盘块数。最多最多100100个。个。 （2 2）所有空闲盘块分为若干组。每组最多）所有空闲盘块分为若干组。每组最多100100个

50、空闲盘块。个空闲盘块。 （3）将每一组含有的盘块总数）将每一组含有的盘块总数N和该组的所和该组的所有盘块号，记入其前一组的第一个盘块中，有盘块号，记入其前一组的第一个盘块中，这样，由各组的第一个盘块链成一个链。这样，由各组的第一个盘块链成一个链。 （4）第一组的盘块总数和盘块号，记入空）第一组的盘块总数和盘块号，记入空闲盘块栈中，作为当前可分配盘块。闲盘块栈中，作为当前可分配盘块。 （5）最后一组只有）最后一组只有99个盘块号，最后一个个盘块号，最后一个盘块号为盘块号为0，代表链表结束。，代表链表结束。成组链接法空闲盘号栈S.free100012300299298989920220110040