精编文件和设备管理示例课件.ppt

1、第第9章章 文件和设备管理示例文件和设备管理示例9.1 文件系统的特点与文件类别文件系统的特点与文件类别9.2 文件系统的数据结构及其关系文件系统的数据结构及其关系9.3 资源管理和地址映射资源管理和地址映射9.4 目录与搜索方法目录与搜索方法9.5 文件系统的系统调用文件系统的系统调用9.6 UNIX System 的中断和陷阱总控程序的中断和陷阱总控程序9.7 缓冲区管理缓冲区管理9.8 块设备驱动块设备驱动9.9 字符设备驱动字符设备驱动本章小结本章小结习题习题9.1 文件系统的特点与文件类别文件系统的特点与文件类别 9.1.1 特点特点 本章通过本章通过 UNIX 的文件系统来进一步深

2、入了解文件的文件系统来进一步深入了解文件系统与操作系统其他部分的关系以及文件系统的设系统与操作系统其他部分的关系以及文件系统的设计方法。从用户的角度看，计方法。从用户的角度看，UNIX文件系统具有如文件系统具有如图图9.1所示的树形层次结构：所示的树形层次结构：在图在图9.1中，根目录中，根目录root之下有之下有dev设备子目录，设备子目录，bin实实用程序子目录，用程序子目录，lib库文件子目录，库文件子目录，etc 基本数据和基本数据和维护实用程序子目录，维护实用程序子目录，tmp临时文件子目录，临时文件子目录，usr通通用子目录和用子目录和include 基本数据子目录等。而基本数据子

3、目录等。而 UNIX 子目录则存放子目录则存放UNIX操作系统核心程序自身。这些操作系统核心程序自身。这些子目录又由各自的子目录构成。子目录又由各自的子目录构成。图图9.1 UNIX文件系统的层次结构例文件系统的层次结构例文件系统被组织成树形结构之后，文件名由路径名文件系统被组织成树形结构之后，文件名由路径名给出。路径名确定一个文件在文件系统中的位置。给出。路径名确定一个文件在文件系统中的位置。一个完整的路径名由代表根目录的斜杠开始，到所一个完整的路径名由代表根目录的斜杠开始，到所指定的文件为止。例如在图指定的文件为止。例如在图9.1中，中，“/usr/users/shi/b.exe”确定了文

4、件确定了文件 b.exe在文件系统在文件系统中的位置。另外，路径名也可从正在执行进程的当中的位置。另外，路径名也可从正在执行进程的当前目录开始指定，例如，若在图前目录开始指定，例如，若在图9.1中的当前目录中的当前目录是是zhang 的话，路径名的话，路径名 a.exe与与/usr/users/zhang/a.exe具有相同的效果。具有相同的效果。一般来说，一般来说，UNIX文件系统还具有如下特点：文件系统还具有如下特点：UNIX的文件是无结构的字符流式文件。的文件是无结构的字符流式文件。文件可以动态地增长或减少。文件可以动态地增长或减少。文件数据可由文件拥有者设置相应的访问权限而受文件数据可

5、由文件拥有者设置相应的访问权限而受到保护。到保护。外部设备，例如终端用磁带、磁盘设备、键盘等都外部设备，例如终端用磁带、磁盘设备、键盘等都被看作文件。从而，设备可通过文件系统隐蔽掉设被看作文件。从而，设备可通过文件系统隐蔽掉设备特性。在文件系统中，设备文件占据着文件系统备特性。在文件系统中，设备文件占据着文件系统目录结构中相应的位置，用户程序按与存取其他文目录结构中相应的位置，用户程序按与存取其他文件时所使用的系统调用和语法来读、写设备文件。件时所使用的系统调用和语法来读、写设备文件。因此，用户程序既没有必要知道设备的内部特性，因此，用户程序既没有必要知道设备的内部特性，也不必在更换或增加设备

6、之后修改自己。也不必在更换或增加设备之后修改自己。9.1.2 文件的分类文件的分类UNIX文件可分为普通文件、目录文件和设备文件。文件可分为普通文件、目录文件和设备文件。普通文件即存储用户和系统的有关数据和程序的文普通文件即存储用户和系统的有关数据和程序的文件。它是无结构、无记录概念的字符流式文件。件。它是无结构、无记录概念的字符流式文件。目录文件则是由文件系统中的各个目录所形成的文目录文件则是由文件系统中的各个目录所形成的文件。这种文件在形式上同普通文件一样，由系统将件。这种文件在形式上同普通文件一样，由系统将其解释成目录。在其解释成目录。在UNIX系统中，一个目录文件由系统中，一个目录文件

7、由多个目录项组成，而每个目录项则由文件名及指示多个目录项组成，而每个目录项则由文件名及指示相应的文件说明信息表相应的文件说明信息表(i节点节点)的标识符的标识符id组成。组成。普通文件和目录文件都是无结构、无记录概念的字普通文件和目录文件都是无结构、无记录概念的字符流式文件。文件系统以符流式文件。文件系统以512 字节为一块，文件在字节为一块，文件在块内连续存放。对于普通文件和目录文件来说，文块内连续存放。对于普通文件和目录文件来说，文件的存放方式既可以是顺序存取的，也可以是直接件的存放方式既可以是顺序存取的，也可以是直接存取的。存取的。UNIX文件在文件系统中的存放采用的是文件在文件系统中的

8、存放采用的是索引结构方法，从而，对文件存储块的分配可以是索引结构方法，从而，对文件存储块的分配可以是非连续的，且文件长度可以动态变化。非连续的，且文件长度可以动态变化。设备文件与普通文件和目录文件不同，它除了在目设备文件与普通文件和目录文件不同，它除了在目录文件和文件说明信息表，也就是录文件和文件说明信息表，也就是 i结点中占据相结点中占据相应的位置之外，并不占有实际的物理存储块。因此，应的位置之外，并不占有实际的物理存储块。因此，对设备文件的读、写操作将实际上变为对设备的操对设备文件的读、写操作将实际上变为对设备的操作，而对设备文件的保护也将变成对设备的保护。作，而对设备文件的保护也将变成对

9、设备的保护。例如：例如：cp/dev/tty terminalread把在终端上敲进的字符把在终端上敲进的字符(设备文件设备文件/dev/tty是用户终端是用户终端)读入，并把它们复制到文件读入，并把它们复制到文件 terminalread上。上。9.2 文件系统的数据结构及其关系文件系统的数据结构及其关系9.2.1 文件系统的存储结构文件系统的存储结构 UNIX系统把文件信息存储在磁盘或磁带上，不过，系统把文件信息存储在磁盘或磁带上，不过，UNIX系统的磁盘文件组织也可以当作一个连续的系统的磁盘文件组织也可以当作一个连续的物理块构成的磁带物理块构成的磁带文件卷看待。在文件卷看待。在 UNIX

10、 系统系统中，一个物理存储器可包含一个或多个文件系统。中，一个物理存储器可包含一个或多个文件系统。这些文件系统可以被动态装卸。为了简单起见，假这些文件系统可以被动态装卸。为了简单起见，假定在一个计算机系统中只存在一个文件系统。定在一个计算机系统中只存在一个文件系统。文件系统由每块文件系统由每块 512字节或字节或 512字节的任意倍数所构字节的任意倍数所构成的逻辑块序列组成。在同一个文件系统中，这些成的逻辑块序列组成。在同一个文件系统中，这些逻辑块的大小完全相同。块长的选取将直接影响设逻辑块的大小完全相同。块长的选取将直接影响设备与主存之间的数据传输速率和内存的存储能力。备与主存之间的数据传输

11、速率和内存的存储能力。大的块长将使得内存和设备之间的数据传输更加容大的块长将使得内存和设备之间的数据传输更加容易，但反过来又使得内存页面长度增加，从而影响易，但反过来又使得内存页面长度增加，从而影响内存的有效存储能力。在内存的有效存储能力。在 UNIX 的许多版本中，大的许多版本中，大都采用每块都采用每块 512字节。字节。文件卷的结构如图文件卷的结构如图9.2所示。其中第所示。其中第 0#块是引导块块是引导块(boot block)。引导块中装有引导或初启操作系统引导块中装有引导或初启操作系统的引导代码。的引导代码。图图9.2 文件系统存储结构文件系统存储结构显然，在有多个文件系统的计算机系

12、统中，只有一显然，在有多个文件系统的计算机系统中，只有一个文件系统的引导块中装有引导代码，而其他的引个文件系统的引导块中装有引导代码，而其他的引导块则是空的。导块则是空的。块是超级块块是超级块(superblock)。超级块用来描述文件。超级块用来描述文件系统的状态，例如文件系统的大小、有关空闲区分系统的状态，例如文件系统的大小、有关空闲区分配和回收用的堆栈等。有关超级块的结构将在后面配和回收用的堆栈等。有关超级块的结构将在后面部分进一步介绍。部分进一步介绍。从从2块开始到块开始到 K+1#块为止的区域被用来存放文件说块为止的区域被用来存放文件说明信息，也就是明信息，也就是 BFD表。表。UN

13、IX系统把一个文件的系统把一个文件的说明信息称为说明信息称为 i节点或索引节点节点或索引节点(inode list)。索引节。索引节点表的大小由系统管理人员在进行系统配置时指定。点表的大小由系统管理人员在进行系统配置时指定。K+2#以后的块称为数据块，其中存放文件数据，包以后的块称为数据块，其中存放文件数据，包括目录文件数据。括目录文件数据。UNIX系统中文件系统的任一数系统中文件系统的任一数据块只能属于文件系统中某一个文件或空闲。据块只能属于文件系统中某一个文件或空闲。9.2.2 几种常用的数据结构几种常用的数据结构1.资源管理结构资源管理结构 filsys超级块中存放的最重要的数据结构是资

14、源管理结构超级块中存放的最重要的数据结构是资源管理结构 filsys。该结构中含有文件系统空闲块分配用堆栈。该结构中含有文件系统空闲块分配用堆栈及及 i节点分配用数据结构。在块设备作为文件卷安节点分配用数据结构。在块设备作为文件卷安装时，结构装时，结构filsys 的内容被复制到内存专用区中，的内容被复制到内存专用区中，以使得对空闲块和以使得对空闲块和 i节点的分配与回收能在内存进节点的分配与回收能在内存进行。当文件卷被卸下或需要重新读入或写出有关堆行。当文件卷被卸下或需要重新读入或写出有关堆栈的内容时，则将内存中的栈的内容时，则将内存中的 filsys 结构复制回超级结构复制回超级块中。块中

15、。UNIX System 中的中的 filsys 结构如下：结构如下：struct filsys 文件卷总块数；文件卷总块数；i 节点表块数；节点表块数；空闲块栈区空闲块栈区(小于或等于小于或等于50);空闲块栈指针；空闲块栈指针；空闲块栈互斥标志；空闲块栈互斥标志；空闲块总数；空闲块总数；空闲空闲 i节点数组指针；节点数组指针；空闲磁盘空闲磁盘 i节点指针；节点指针；空闲空闲 i节点数组互斥标志；节点数组互斥标志；空闲空闲 i节点总数；节点总数；filsys 的修改标志，等；的修改标志，等；filsys 结构被用来进行文件空闲块和结构被用来进行文件空闲块和 i节点项的分配节点项的分配与回收与

16、回收。2.i节点节点UNIX文件系统采用文件系统采用 SFD和和 BFD方式管理文件。其中方式管理文件。其中 SFD称为符号文件目录，存放文件名以及指示该文称为符号文件目录，存放文件名以及指示该文件的文件说明信息表标识符件的文件说明信息表标识符id。由文件名和指示文。由文件名和指示文件说明信息表的标识符件说明信息表的标识符id称为目录，把存放文件说称为目录，把存放文件说明信息和相应标识符的明信息和相应标识符的 BFD称为称为 i节点。节点。i节点又节点又分为磁盘分为磁盘 i节点和内存活动节点和内存活动 i节点。其中磁盘节点。其中磁盘 i节点节点以静态形式存放文件说明信息。磁盘以静态形式存放文件

17、说明信息。磁盘 i节点节点 dinode 结构包括：结构包括：struct dinode 文件模式；文件模式；与该与该 i节点联接的文件数；节点联接的文件数；用户标识用户标识;文件大小文件大小;存取权限存取权限;同组用户标识同组用户标识;该文件所用物理块的块号该文件所用物理块的块号;文件存取时间、修改时间和建立时间；文件存取时间、修改时间和建立时间；其中，文件模式表示文件类型，而用户标识符以及其中，文件模式表示文件类型，而用户标识符以及同组用户标识定义对该文件具有存取权的用户集合，同组用户标识定义对该文件具有存取权的用户集合，与该与该 i节点联接的文件数表示有多少个不同的文件节点联接的文件数表

18、示有多少个不同的文件名指向该文件。另外，该文件所用的物理块号是一名指向该文件。另外，该文件所用的物理块号是一个由个由 40 个字节组成的字符数组个字节组成的字符数组 di_addr40，它，它指明文件数据安放在逻辑盘上的位置。指明文件数据安放在逻辑盘上的位置。在在 UNIX System 中磁盘中磁盘 i节点的项占用节点的项占用64个字节。个字节。因此，一个长因此，一个长 512个字节的块可存放个字节的块可存放 8 个个 i节点项。节点项。系统在对文件进行各种操作时，为了减少设备的启系统在对文件进行各种操作时，为了减少设备的启动次数以及提高操作速度，总是把相应的磁盘动次数以及提高操作速度，总是

19、把相应的磁盘 i节节点复制到内存的特定区域点复制到内存的特定区域内存内存 i节点表中。节点表中。内存内存 i节点结构节点结构 inode除了包含磁盘除了包含磁盘 i节点结构的各项节点结构的各项之外，还包含了当前打开文件的状态信息。例如，之外，还包含了当前打开文件的状态信息。例如，内存内存 i节点的状态：包括该节点是否已被锁住，是节点的状态：包括该节点是否已被锁住，是否有进程等待访问该否有进程等待访问该 i节点等。节点等。总之，与总之，与 filsys 用于空闲区的分配与回收不一样，用于空闲区的分配与回收不一样，i节点主要用来存放文件的说明信息，以便进程利用节点主要用来存放文件的说明信息，以便进

20、程利用 i节点中的逻辑结构和物理结构信息搜索查找文件节点中的逻辑结构和物理结构信息搜索查找文件信息以及完成对文件信息的保护和共享。信息以及完成对文件信息的保护和共享。3.目录项目录项UNIX系统的目录项由文件名和磁盘系统的目录项由文件名和磁盘 i节点标识符节点标识符id组组成。其中文件名长度占成。其中文件名长度占14个字节，标识符个字节，标识符id占占 2个个字节。从而，在一个字节。从而，在一个 512字节的磁盘块中可以存放字节的磁盘块中可以存放32个目录项。个目录项。4.系统打开文件表和用户打开文件表系统打开文件表和用户打开文件表在在UNIX系统中，文件系统主要描述程序和数据的静系统中，文件

21、系统主要描述程序和数据的静的概念，而进程则反应这些程序和数据的动的特性。的概念，而进程则反应这些程序和数据的动的特性。进程怎样才能对文件发生作用呢？从用户的角度来进程怎样才能对文件发生作用呢？从用户的角度来看，用户程序可使用对文件系统进行操作的系统调看，用户程序可使用对文件系统进行操作的系统调用来完成。但是，从系统内部的角度来说，则需要用来完成。但是，从系统内部的角度来说，则需要有相应的数据结构来记录和控制打开文件的用户进有相应的数据结构来记录和控制打开文件的用户进程以及记录和控制那些共享同一文件的用户进程。程以及记录和控制那些共享同一文件的用户进程。为此为此 UNIX系统设置了用户打开文件表

22、和系统打开系统设置了用户打开文件表和系统打开文件表。文件表。用户打开文件表一般放在用户打开文件表一般放在 user 数据结构中。使用用数据结构中。使用用户打开文件表，一个进程可同时打开户打开文件表，一个进程可同时打开 20 个左右的个左右的文件。可打开的文件表项文件。可打开的文件表项 u_ofile中含有打开文件的中含有打开文件的描述符描述符fd，以及系统打开文件表的入口指针，以及系统打开文件表的入口指针fp等。等。系统打开文件表主要用来指明打开同一文件的不同系统打开文件表主要用来指明打开同一文件的不同进程和不同进程所使用的不同打开路径，以及这些进程和不同进程所使用的不同打开路径，以及这些不同

23、进程和不同打开路径所对应的读写指针。因此不同进程和不同打开路径所对应的读写指针。因此可以认为系统打开文件表是可以认为系统打开文件表是 i节点表的补充。系统节点表的补充。系统打开文件表的每一项包括文件标识、文件访问计数、打开文件表的每一项包括文件标识、文件访问计数、文件读写指针和文件内存文件读写指针和文件内存 i节点入口指针和访问标节点入口指针和访问标志等。其中文件标识与用户打开文件中志等。其中文件标识与用户打开文件中fp相连；文相连；文件访问计数指示共享该文件的进程数，当文件访问件访问计数指示共享该文件的进程数，当文件访问计数为计数为 0时，则表明已没有用户进程在使用该文件，时，则表明已没有用

24、户进程在使用该文件，从而可以释放有关资源。文件读写指针则分别指出从而可以释放有关资源。文件读写指针则分别指出各进程在同一文件中的读写位置。各进程在同一文件中的读写位置。资源管理结构、资源管理结构、i节点以及用户打开文件表和系统打节点以及用户打开文件表和系统打开文件表的关系如图开文件表的关系如图9.3所示：所示：图图9.3 文件系统中主要数据结构之间的关系文件系统中主要数据结构之间的关系在图在图9.3中，用户进程通过用户打开文件表中的文件中，用户进程通过用户打开文件表中的文件描述符描述符fd，找到系统打开文件表的入口地址，找到系统打开文件表的入口地址fp，再，再由系统打开文件表中对应项找到相关由

25、系统打开文件表中对应项找到相关 i节点的入口节点的入口指针，从而得到操作该文件所需的控制信息。有了指针，从而得到操作该文件所需的控制信息。有了 i节点中的控制信息，文件系统就可对磁盘数据区节点中的控制信息，文件系统就可对磁盘数据区中的文件进行所必需要的操作。另外，在图中的文件进行所必需要的操作。另外，在图9.3中，中，给出了两个不同用户进程共享同一文件的例子。这给出了两个不同用户进程共享同一文件的例子。这两个进程通过各自不同的文件描述符两个进程通过各自不同的文件描述符fdA和和fdB，找，找到系统打开文件表中不同的对应项，并通过系统打到系统打开文件表中不同的对应项，并通过系统打开文件表中的开文

26、件表中的 i节点指针而找到同一个内存节点指针而找到同一个内存i节点，节点，从而完成文件共享。从而完成文件共享。9.3 资源管理和地址映射资源管理和地址映射UNIX文件系统的资源管理包括空闲磁盘块的分配与文件系统的资源管理包括空闲磁盘块的分配与回收、回收、i节点和系统打开文件表的分配与回收等。节点和系统打开文件表的分配与回收等。关于空闲磁盘块的分配与回收，关于空闲磁盘块的分配与回收，UNIX系统采用成系统采用成组链法来管理空闲区。本节主要介绍磁盘节点和组链法来管理空闲区。本节主要介绍磁盘节点和内存节点以及系统打开文件表的分配和释放方法。内存节点以及系统打开文件表的分配和释放方法。9.3.1 磁盘

27、节点的分配与释放磁盘节点的分配与释放当一个新文件被建立时，在给该文件分配磁盘存储当一个新文件被建立时，在给该文件分配磁盘存储区之前，应为该文件分配存放该文件说明信息的磁区之前，应为该文件分配存放该文件说明信息的磁盘节点。反之，当从文件系统中删除某个文件时，盘节点。反之，当从文件系统中删除某个文件时，则要首先删除它的磁盘节点项。则要首先删除它的磁盘节点项。UNIX System 中的算法中的算法 ialloc 被用来为新建立的文件分配磁盘被用来为新建立的文件分配磁盘节点项。文件系统包含一个节点线性表，且每个节点项。文件系统包含一个节点线性表，且每个磁盘节点被顺序编号。节点线性表中存放这些磁盘节点

28、被顺序编号。节点线性表中存放这些被编号的节点的类型字段。如果一个节点的类被编号的节点的类型字段。如果一个节点的类型字段为，则说明这个节点是空闲的。显然，当型字段为，则说明这个节点是空闲的。显然，当一个进程需要一个新的节点时，它可以通过搜索一个进程需要一个新的节点时，它可以通过搜索节点线性表得到它所要得到的节点项。为改善节点线性表得到它所要得到的节点项。为改善系统性能，系统性能，UNIX System 在资源管理结构在资源管理结构 filsys 中设置了一个磁盘节点数组。该数组在系统初启中设置了一个磁盘节点数组。该数组在系统初启时随时随 filsys 结构一起被复制到内存的特定区中。结构一起被复

29、制到内存的特定区中。算法算法 ialloc 首先检查是否有其他进程在对磁盘节点首先检查是否有其他进程在对磁盘节点数组进行操作。如果有其他进程正在对磁盘节点数组进行操作。如果有其他进程正在对磁盘节点数组进行操作，则当前进程等待直到其他进程操作数组进行操作，则当前进程等待直到其他进程操作结束。在没有其他进程对磁盘节点数组进行操作结束。在没有其他进程对磁盘节点数组进行操作且磁盘节点数组非空时，系统从节点数组中分且磁盘节点数组非空时，系统从节点数组中分配一个节点给新创建的文件，然后，修改节点配一个节点给新创建的文件，然后，修改节点数组指针。紧接着，数组指针。紧接着，ialloc调用内存节点分配算调用内

30、存节点分配算法为新建立的文件分配内存节点后将内存节点法为新建立的文件分配内存节点后将内存节点初始化。在对内存节点进行了初始化之后，再将初始化。在对内存节点进行了初始化之后，再将内存节点的内容写回到磁盘节点中并修改磁盘内存节点的内容写回到磁盘节点中并修改磁盘空闲节点的计数。空闲节点的计数。有关有关 ialloc 算法，还有几个问题需要说明，首先是算法，还有几个问题需要说明，首先是节点数组中的节点号排列方法。系统从磁盘把节点数组中的节点号排列方法。系统从磁盘把节点按从小到大的顺序读进节点按从小到大的顺序读进i节点数组，如图节点数组，如图9.4：图图9.4 空闲节点数组空闲节点数组系统在为进程分配磁

31、盘节点时，按节点序号从系统在为进程分配磁盘节点时，按节点序号从小到大的原则分配。当空闲节点数组为空时，系小到大的原则分配。当空闲节点数组为空时，系统锁住节点数组，并从低到高地一个一个将磁盘统锁住节点数组，并从低到高地一个一个将磁盘上的索引节点号填入节点数组中，直到节点数上的索引节点号填入节点数组中，直到节点数组满额或再也找不到空闲节点。在节点数组满组满额或再也找不到空闲节点。在节点数组满额的同时，系统记住它所找到的最高序号的节点，额的同时，系统记住它所找到的最高序号的节点，并称之为并称之为“铭记铭记”节点。铭记节点是保存在节点。铭记节点是保存在节点数组中的最后一个节点节点数组中的最后一个节点(

32、最大最大)，如果系统分，如果系统分配到铭记节点时，则启动配到铭记节点时，则启动 I/O设备，从铭记节设备，从铭记节点开始，重新搜索磁盘上的空闲节点，然后写进点开始，重新搜索磁盘上的空闲节点，然后写进i结点数组。这可以确保系统不浪费时间去读那些结点数组。这可以确保系统不浪费时间去读那些已不含空闲节点的磁盘块。已不含空闲节点的磁盘块。其次是在系统为新建立的文件分配磁盘节点和内其次是在系统为新建立的文件分配磁盘节点和内存节点之后，要检查所分配的节点是否是真正存节点之后，要检查所分配的节点是否是真正的空闲节点。如果不是空闲节点，则要放弃本的空闲节点。如果不是空闲节点，则要放弃本次分配。至于为什么会出现

33、分配到已分配节点的次分配。至于为什么会出现分配到已分配节点的情况，则主要是由于资源共享引起的。情况，则主要是由于资源共享引起的。综上所述，可将算法综上所述，可将算法 ialloc 描述如下描述如下:ialloc:输入：文件系统设备号，文件属性，联接该文件的目录数输入：文件系统设备号，文件属性，联接该文件的目录数输出：上锁的磁盘节点输出：上锁的磁盘节点begin if i结点数组上锁结点数组上锁then等待开锁等待开锁fiif 节点数组空节点数组空then 锁住锁住i结点数组结点数组为搜索空闲节点取铭记节点为搜索空闲节点取铭记节点搜索磁盘；将空闲节点置入节点数组搜索磁盘；将空闲节点置入节点数组为

34、为i结点数组解锁结点数组解锁fi从节点数组中分配一节点从节点数组中分配一节点调用调用 iget 分配内存节点分配内存节点if iget返回的内存节点为非空闲节点返回的内存节点为非空闲节点then 把该节点的内容写回磁盘；释放该节点；把该节点的内容写回磁盘；释放该节点；重新申请磁盘节点重新申请磁盘节点else 将将 iget 返回的内存节点初始化返回的内存节点初始化将内容写回磁盘节点将内容写回磁盘节点空闲节点数减空闲节点数减fiend磁盘节点的释放过程磁盘节点的释放过程 ifree是是 ialloc 的反过程。但相的反过程。但相对来说，对来说，ifree 比较简单。比较简单。ifree 首先把空

35、闲节点首先把空闲节点数加，如果超级块的节点数组未被锁住且有空数加，如果超级块的节点数组未被锁住且有空表项，则表项，则 ifree把释放的节点号放入节点数组把释放的节点号放入节点数组后返回。如果节点数组已处于满额状态，则后返回。如果节点数组已处于满额状态，则 ifree将新释放的节点与铭记节点相比校。如果将新释放的节点与铭记节点相比校。如果新释放的节点小于铭记节点，则新释放的节点小于铭记节点，则 ifree将新释将新释放的节点作为铭记节点，并丢掉原来的铭记放的节点作为铭记节点，并丢掉原来的铭记节点，否则丢掉新释放的节点节点，否则丢掉新释放的节点(为什么？为什么？)。如果。如果超级块节点数组是被锁

36、住的，则此时系统正在进超级块节点数组是被锁住的，则此时系统正在进行磁盘节点搜索工作。行磁盘节点搜索工作。ifree 直接返回，以避免直接返回，以避免竞争条件竞争条件(有可能漏掉节点有可能漏掉节点)。9.3.2 内存节点的分配与释放内存节点的分配与释放当系统打开文件并对其进行搜索、读写等操作时，当系统打开文件并对其进行搜索、读写等操作时，为相应的文件分配一个内存节点，以便把对应磁为相应的文件分配一个内存节点，以便把对应磁盘节点信息复制到内存。一般来说，当系统创建盘节点信息复制到内存。一般来说，当系统创建一个文件之后，如果未关闭该文件的话，则该文件一个文件之后，如果未关闭该文件的话，则该文件已拥有

37、了相应的内存节点。此时，如果用户要对已拥有了相应的内存节点。此时，如果用户要对该文件进行相应的操作的话，系统只需增加已有内该文件进行相应的操作的话，系统只需增加已有内存节点的访问计数和做互斥处理即可。存节点的访问计数和做互斥处理即可。内存节点的分配由过程内存节点的分配由过程 iget 完成，完成，iget的输入是文的输入是文件系统所在的设备名和磁盘节点号。输出是对应件系统所在的设备名和磁盘节点号。输出是对应的上了锁的内存节点。的上了锁的内存节点。首先，首先，iget根据给定的磁盘节点号从内存节点数根据给定的磁盘节点号从内存节点数组中搜索相应的内存节点。组中搜索相应的内存节点。如果该节点已在内存

38、，则只需增加引用计数并锁定如果该节点已在内存，则只需增加引用计数并锁定该节点即可。否则，应从内存节点数组中分配该节点即可。否则，应从内存节点数组中分配一个节点并启动设备，将对应磁盘节点信息复一个节点并启动设备，将对应磁盘节点信息复制到内存节点后上锁返回。制到内存节点后上锁返回。另外，当一个文件被关闭时，系统释放其内存节另外，当一个文件被关闭时，系统释放其内存节点。点。UNIX系统中，释放内存节点的过程是系统中，释放内存节点的过程是iput。iput首先判内存节点的访问计数是否等于，如首先判内存节点的访问计数是否等于，如果访问计数等于的话，则表示当前没有其他用户果访问计数等于的话，则表示当前没有

39、其他用户使用该文件，只需把内存节点项的内容复制回磁使用该文件，只需把内存节点项的内容复制回磁盘节点后就可释放该内存节点项。如果访问计盘节点后就可释放该内存节点项。如果访问计数大于，则只需将访问计数减即可。数大于，则只需将访问计数减即可。再者，如果表示与该文件相联接的目录数的联接计再者，如果表示与该文件相联接的目录数的联接计数值为的话，则表示该文件已不再需要，数值为的话，则表示该文件已不再需要，iput释释放与该文件有关的所有磁盘块和磁盘节点。放与该文件有关的所有磁盘块和磁盘节点。9.3.3 系统打开文件表的分配与释放系统打开文件表的分配与释放在在 UNIX 系统中，用户之间除了采用存取权限控制

40、系统中，用户之间除了采用存取权限控制方式共享文件信息之外，对于享有存取权限的用户，方式共享文件信息之外，对于享有存取权限的用户，还可以采用如下方式共享文件：子进程共享父进程还可以采用如下方式共享文件：子进程共享父进程打开的所有文件；由系统调用打开的所有文件；由系统调用 link 将不同的文件将不同的文件进行联接等。对于这些不同的共享方式，用户和系进行联接等。对于这些不同的共享方式，用户和系统都需要有相应的数据结构与之相应。统都需要有相应的数据结构与之相应。UNIX系统系统中设置有系统打开文件表，存放各进程共享同一文中设置有系统打开文件表，存放各进程共享同一文件时的读写指针；用户打开文件表通过指

41、针件时的读写指针；用户打开文件表通过指针fp指向指向系统打开文件表。系统打开文件表。用户在读写、打开一个文件时，首先由用户在读写、打开一个文件时，首先由iget在内存在内存i节节点数组中分配一空闲项，并根据用户提供的文件名，点数组中分配一空闲项，并根据用户提供的文件名，找到与此文件对应的磁盘找到与此文件对应的磁盘i节点，然后将磁盘节点，然后将磁盘i节点节点复制到已分得的内存复制到已分得的内存i节点中。节点中。此时，此时，i节点访问计数等于节点访问计数等于1。如果磁盘。如果磁盘i节点已在内节点已在内存中，则对存中，则对i节点访问计数加节点访问计数加1。接着系统在系统打。接着系统在系统打开文件表中

42、为访问该文件的用户分配一系统打开文开文件表中为访问该文件的用户分配一系统打开文件表项。在分得系统打开文件表项后对该表项赋初件表项。在分得系统打开文件表项后对该表项赋初值以建立系统打开文件表和内存值以建立系统打开文件表和内存i节点的联系。同节点的联系。同时，在用户打开文件表中填写指向系统打开文件表时，在用户打开文件表中填写指向系统打开文件表的指针的指针fp和把对应的用户打开文件表项的序号和把对应的用户打开文件表项的序号fd送送给用户。经过上述操作，两个以上的用户共享某一给用户。经过上述操作，两个以上的用户共享某一文件时，将会分配得到与用户数相等的系统打开文文件时，将会分配得到与用户数相等的系统打

43、开文件表项，且这些表项指向同一内存件表项，且这些表项指向同一内存i节点。但在父、节点。但在父、子进程共享同一文件时，由于子进程是直接继承父子进程共享同一文件时，由于子进程是直接继承父进程打开文件，因此，进程打开文件，因此，i节点访问计数不变。节点访问计数不变。为了指明父、子进程共享同一文件的情况，在系统为了指明父、子进程共享同一文件的情况，在系统打开文件表项中设有共享文件计数项以指明父、子打开文件表项中设有共享文件计数项以指明父、子进程的个数。系统打开文件表项的分配由过程进程的个数。系统打开文件表项的分配由过程getf完成。完成。关闭文件时，根据用户提供的文件标识符关闭文件时，根据用户提供的文

44、件标识符fd找到对应找到对应的用户打开文件表项，从而得到指向系统打开文件的用户打开文件表项，从而得到指向系统打开文件表的指针表的指针fp。然后就可清除用户打开文件表项和把。然后就可清除用户打开文件表项和把系统打开文件表项共享文件计数项减系统打开文件表项共享文件计数项减1。JP1当共当共享计数项为享计数项为0时，则清除系统打开文件表项和将内时，则清除系统打开文件表项和将内存存i节点中共享计数项减节点中共享计数项减1。用户打开文件表项和系。用户打开文件表项和系统打开文件表项的释放分别由过程统打开文件表项的释放分别由过程close和和closef完完成。成。9.3.4 地址映射地址映射UNIX系统采

45、用索引结构存放文件物理块的地址。即系统采用索引结构存放文件物理块的地址。即在文件对应的在文件对应的i节点中，放有存放文件物理块号的节点中，放有存放文件物理块号的索引结构。由对应文件的逻辑字节偏移量计算出逻索引结构。由对应文件的逻辑字节偏移量计算出逻辑块号之后，就可搜索内存辑块号之后，就可搜索内存i节点中的地址索引结节点中的地址索引结构而得到文件的物理块号。构而得到文件的物理块号。UNIX system 把常规把常规文件分为小型、中型、大型和巨型文件分为小型、中型、大型和巨型4种。文件长度种。文件长度小于小于5K的为小型文件。对于小型文件，索引数组的为小型文件。对于小型文件，索引数组中的前中的前

46、30个字节被用来存放其物理块块号。文件长个字节被用来存放其物理块块号。文件长度大于度大于5K但小于但小于90K的文件为中型文件。对于中型的文件为中型文件。对于中型文件，文件，i节点的索引数组所指的前节点的索引数组所指的前10个物理块中存个物理块中存放文件信息，而索引数组所指的第放文件信息，而索引数组所指的第11个物理块中存个物理块中存放的则是存放文件信息的物理块块号放的则是存放文件信息的物理块块号(不包括前不包括前10个物理块块号个物理块块号)。文件长度大于文件长度大于90K但小于但小于14.54M的文件为大型文件。的文件为大型文件。于大型文件，于大型文件，UNIX System 采用二次间接

47、寻址的采用二次间接寻址的方法。即索引数组的和经第方法。即索引数组的和经第12项所指的物理块中存项所指的物理块中存放的既不是文件信息，也不是存放文件信息的物理放的既不是文件信息，也不是存放文件信息的物理块号，而是那些进行二次间接存放文件信息的物理块号，而是那些进行二次间接存放文件信息的物理块号。块号。对于更大的文件，称之为巨型文件。巨型文件采用对于更大的文件，称之为巨型文件。巨型文件采用三次间接的办法存放。三次间接的办法存放。索引数组中的直接块和间接块的关系如图索引数组中的直接块和间接块的关系如图9.5所示。所示。在用户进程搜索文件时，根据相应的在用户进程搜索文件时，根据相应的i节点信息，可节点

48、信息，可根据上述地址变换关系由逻辑文件中的相对地址找根据上述地址变换关系由逻辑文件中的相对地址找到实际文件信息所在的物理块。该转换算法由过程到实际文件信息所在的物理块。该转换算法由过程bmap完成。完成。图图9.5 文件映射关系文件映射关系9.4 目录与搜索方法目录与搜索方法UNIX系统中的目录文件是以普通文件存放，且文件系统中的目录文件是以普通文件存放，且文件的目录和说明信息采用了的目录和说明信息采用了SFD和和BFD结构方式以利结构方式以利于共享。这样，当用户搜索当前目录下的文件时，于共享。这样，当用户搜索当前目录下的文件时，可以直接从当前目录开始搜索，而当被搜索文件不可以直接从当前目录开

49、始搜索，而当被搜索文件不在当前目录下时，则从根目录开始按指定路径搜索在当前目录下时，则从根目录开始按指定路径搜索(已做过联接的其他目录下的文件被看作当前目录已做过联接的其他目录下的文件被看作当前目录下文件下文件)。由于。由于UNIX的文件系统采用树型结构，且的文件系统采用树型结构，且只有最低一级的叶才代表文件信息，因此，对文件只有最低一级的叶才代表文件信息，因此，对文件信息的搜索的大部分工作是对信息的搜索的大部分工作是对i节点和对目录文件节点和对目录文件的搜索。的搜索。UNIX System 对内存对内存i节点的搜索采用散列搜索法。节点的搜索采用散列搜索法。首先，系统把空闲内存首先，系统把空闲

50、内存i节点组成一个头指针为节点组成一个头指针为ifreelist链的链表，而已分配的内存链的链表，而已分配的内存i节点则按给定节点则按给定的散列函数分成不同的组。系统定义的散列函数为的散列函数分成不同的组。系统定义的散列函数为ihash(x)=&hinode(int)(x)&128。这里，。这里，x代表代表要搜索的要搜索的i节点号；节点号；ihash的功能是将那些与的功能是将那些与128进行进行模运算后余数相同的模运算后余数相同的i节点编为一组，每组的头指节点编为一组，每组的头指针为针为hinode。ihash的值即是的值即是i节点节点x的头指针的头指针hinode的地址。的地址。hinode