2.4.3 目录结构及索引节点
计算机对文件的组织和检索都与对目录的操作有关。
·搜索文件:当需要查找某个文件时,文件系统按照给定的文件名搜索目录文件,以查找匹配的目录项,将目录项中的文件的物理地址返回给操作系统,这就是“按名查找”。
·创建文件:当需要建立一个新文件时,文件系统将新建文件的描述填充到文件控制块,并作为目录项增加到目录文件中。
·删除文件:当需要删除一个文件时,文件系统将对应的目录项从目录文件中删除。
还有遍历系统文件、重命名文件等操作都对应为对目录的操作。因此目录文件本身的组织关系到系统对文件访问的效率,目录文件的结构设计对文件系统性能的影响至关重要。
文件目录结构经历的发展过程包括:最早的简单目录结构称为一级目录结构,随着文件系统的发展,出现了为每个用户提供一个目录的二级目录结构,当代操作系统都使用多级的树形目录结构。
1.一级目录结构
目录结构刚刚提出时,所有文件都包含在同一个目录中(图2-32),每个目录项直接指向一个文件,这种形式称为一级目录结构。其特点是构造简单,便于管理,能实现目录管理的基本功能——按名存取。
图2-32 一级目录结构
一级目录结构适用于早期的单用户操作系统,但是对于文件较多的多用户操作系统,系统可能存在数百个文件,此时一级目录结构的缺点也是很明显的,由于文件较多,目录文件过大,在目录中查找文件速度很慢;另外,多个用户的文件可能会重名,但是在一个目录文件中,它们必须有唯一的名字,显然重名是不允许的。
2.二级目录结构
为了解决一级目录不允许重名的问题,二级目录结构得以发展,系统为每个用户建立一个用户文件目录(UFD,User File Directory),每个UFD都有相似的结构,只保存用户自己的文件目录项。系统建立一个主文件目录(MFD,Main File Directory),记录每个用户目录的名字和指向用户文件目录UFD的指针,如图2-33所示。
二级目录结构做到了各个用户的目录相互独立,当一个用户访问自己的文件时,只需要搜索他自己的UFD,这样不仅检索速度较之检索整个系统文件的单级目录要快,而且不同用户也可以拥有相同的文件名字,解决了不同用户间的文件重名问题。但是由于用户文件独立隔离,造成了用户间共享文件困难,使用户合作缺乏灵活性。
图2-33 二级目录结构
3.树形目录结构
在目前的操作系统中,文件系统广泛采用的是多级目录结构,用户可以任意创建自己的子目录,系统中每个目录(或子目录)包括一组文件和子目录。一个目录也作为一个文件看待,它只是一个需要按特定方式访问的文件。所有目录具有同样的内部格式,并且用一个标识位来描述文件是目录(目录文件)或是文件(数据文件)。这样,系统的目录结构就成为一个树状结构,我们称之为树形目录结构,如图2-34所示。
图2-34 树形目录结构
在树形目录结构中,只有一个根目录,是每次操作系统初启运行时创建的,根目录可以拥有任意多个子目录或文件,每个子目录同样可以创建多个子目录或文件,创建子目录的目录就被称为该子目录的父目录。图中每个目录或文件都称为节点,圆形表示的是目录文件,方形表示的是数据文件,数据节点不可以有子节点,因此也称为叶子节点。
4.路径名
文件系统采用二级或多级目录后,能够为用户提供同名的文件,也能使一个文件有多个不同的名字,在这种情况下,仅仅使用文件名字就不能唯一指定一个文件了,因此操作系统定义了“路径名”的概念,并且用“设备名”+“路径名”来唯一标识一个文件(有的操作系统不需要给出设备名)。设备名是指一个相对独立的存储单位,如一个磁盘分区,或者一个文件卷。
所谓文件的路径名是指从根目录出发,一直到所要找的文件,把途经的各分支子目录名字(节点名)连接一起而形成的字符串,两个分支名(节点名)之间用分隔符分开。目前分隔符有两种,UNIX操作系统的分隔符为“/”,而Windows操作系统的分隔符为“\”。如UNIX操作系统下的一个文件的路径名记为“/user1/program/c/test.c”,Windows操作系统下的一个文件的路径名记为“c:\client1\program\jsp\test.jsp”,其中“c:”为存储设备名字。
虽然采用路径名可以无二义性地标识多级目录下的文件,但是,系统每次搜索文件都要从根目录开始,沿着路径查找文件目录,会耗费更多的查询时间,一次查询可能要经过若干次间接查找才能找到所要的文件,为此,系统引入了“当前目录”或“工作目录”的概念。用户当前工作的目录就称为当前目录或工作目录,用户访问这个目录下的文件,可以不必指定设备名和文件的路径,仅当访问其他目录下的文件时才要指定文件的路径名。用户可以通过系统调用改变工作目录。
在引入当前目录后,路径名就有两种形式:绝对路径名和相对路径名。绝对路径名是指从根开始给出路径上的目录名直到所指定的文件;相对路径名是指从当前目录开始定义路径。例如,在图2-34中,如果当前目录名是/prog/pas,那么相对路径名smart/list.pas与绝对路径名/prog/pas/smart/list.pas指向同一个文件。
很多系统还支持两种特殊的路径分量,一个是“.”,代表当前工作目录;另一个是“..”,指当前工作目录的父目录。根目录没有父目录,因此它的“..”指向自己。
5.索引节点
通常文件目录存储在磁盘上,当访问或检索文件时,操作系统先要将目录调入内存,之后才能进行检索,我们稍加分析可以发现,在检索目录文件的过程中,开始只用到了文件名,仅当按照文件名找到相应的目录项时,才需要读取该文件的其他属性。显然,这些属性信息在检索目录时,不需要调入内存。文件的属性信息占据目录的绝大部分存储量,减少将其读入内存将节省很多时间和空间,提高操作系统访问文件的效率,为此,UNIX操作系统最先把文件名与文件的其他属性信息分开,使文件属性信息单独形成一个数据结构,称为索引节点,简称为i节点,而文件目录中的目录项,仅由文件名和指向该文件对应的i节点的指针构成,如图2-35所示。
图2-35 引入索引节点后的目录结构
引入i节点后,大大提高了目录检索效率,假设一个系统,原来的FCB(一个目录项)为64 B,则600个目录项占用约40个盘块(设一个盘块为1 KB),每次查找一个文件需要访问约40个盘块,需要启动磁盘20次(这是最耗时的动作),如果引入i节点,则目录项约占16 B,1 KB的盘块可以存放64个目录项,这样为了查找一个文件,只需访问10个盘块,启动磁盘次数减少到原来的1/4,大大节省了系统开销。现在大部分操作系统采用索引节点结构的目录管理方法。