Do more! Do better!

读《操作系统概念》:文件和文件系统

Posted on By zjk

1.文件

        先说文件定义,根据《操作系统概念》所言,文件是记录在外存上的相关信息具有名称的集合。这里有一点,文件是存放在外存的,这是由于内存的断电易失性质导致的,虽然内存速度快,但是仍然需要文件来稳定地存放文件。而对于用户来说,文件是逻辑外存地最小分配单元,即数据只能通过文件的方式写到外存。

    文件有一定的属性,一般来说包括:名称,标识符(唯一标签,通常为数字),类型,位置,大小,保护(决定访问控制信息),时间、日期和用户标识等。下图为笔者在ubuntu中随手测试的截图,可以看到从左依次可以看到访问控制,文件数、拥有者、所属的group、文件大小、建档日期、文件名等属性。所有文件的信息都保存在目录结构中,并随目录结构存放在外存中。

    文件作为一种抽象数据类型,显然需要定义一些基本的操作,具体应当包括:创建,写,读,重定位,删除,截短6个基本操作。这些文件操作总是涉及为给定文件搜索相关目录条目,这种情况下,操作系统维护一个包含所有打开文件的信息表——打开文件表,就会避免一些不必要的搜索操作。这个表的建立主要是通过在首次打开文件时,使用系统调用open()。

    这里讲一下open()系统调用。可以分为五步:(1)进程向os提供文件路径名(2)os查询硬盘上的文件属性(3)从硬盘返回文件属性(4)os把一个文件描述符和这个文件属性联系起来,一般来说是一个number(5)os把文件描述符返回给进程,这时进程就取得了这个文件,可以通过这个描述符访问文件具体内容。同样,进程同样维护一个内部的打开文件表,并指向系统表的相应条目。应当注意到,这个过程中实际上只涉及了路径名、文件属性,并没有具体的文件内容。

    此外,文件系统设计时,文件类型是必须考虑的,具体要考虑到文件类型的识别和系统支持与否。实现文件类型的常见技术是扩展名,一般包括在文件名当中,绝大多数os允许用户将文件命名为一组字符,加上dot,跟着是扩展部分。UNIX还采用了幻数的方法,作为辅助标识文件类型的手段。除此以外,针对不同的系统,如TOPS-20、Mac OS X等,在文件类型的处理上各有差异,此不赘述。而文件类型决定了文件的内部结构,以适应相应处理程序的要求。同时,文件结构也受到不同操作系统的要求。显然,os支持常用文件结构是有用的,但是支持过多就会导致系统过大和程序员混淆,过犹不及。

    文件是用来存储信息的,既然有了文件的属性信息、基本操作、类型结构等,下面就要谈及文件的访问,否则文件没有存在的意义。这里主要从访问方法的层面来分析。在支持多种访问方式的系统中,针对不同应用访问方法的选择尤为重要。(1)顺序访问(2)直接访问(3)其他访问,一般建立在直接访问方式之上,通常设计文件索引,包含各块指针的结构称为索引包。针对大文件,索引较大难以存放在内存中,可以创建多级索引,即为索引文件再创建索引。

    考虑到当今计算机文件系统十分庞大,文件数目繁多,故而产生了目录,目的是更好地组织文件并加以管理。目录应包含相关操作操作:搜索文件、删除文件、创建文件、遍历目录、重命名文件、跟踪文件系统,这些操作在设计目录逻辑结构时要着重考虑。定义目录结构地常用方案有:单层结构目录,双层结构目录,树状结构目录,无环图目录,通用图目录。前三种方案可以看作逐渐拓展,本质都属于树状结构。

    文件共享是一种十分有用的功能,一般不论怎样,面向用户地操作系统都需要提供文件共享功能。在多用户情景下,为了实现共享和保护,文件必须维护更多的文件属性,现在常用的方法是,拥有者和组的概念,拥有者有最高的权限,不同组可以设置不同的授权,在既定权限的限制下,可以实现同组、不同组用户之间的文件共享。针对远程文件进系统,有三种实现方式:(1)通过应用程序进行人工传输(2)分布式文件系统,可以直接访问远程目录(3)万维网,类似第一种,通过浏览器获取对远程文件的访问。

    文件在计算机系统中,需要有一定的方式保护其安全,包括可靠性和防止非法访问两方面。前者通常通过文件备份来实现。后者对不同的访问类型加以区分并进行限制。访问类型有:读、写、执行、添加、删除、列表清单。实现访问控制的手段最普通的方案就是为每个目录、文件增加一个访问控制表,针对每一个用户设置权限。这样比较没有效率,精简方法就是分组,这实际上在前面文件共享部分有所提及。如下最左侧的属性实际就是访问权限的设置。r是读,w是写,x是执行,三个为一组,从左到左右依次是拥有者、组成员、其他访问者的权限。

2.文件系统

    文件系统的结构包括不同的层次,I/O控制为最底层,基本文件系统负责向设备驱动程序发送一般命令,文件组织模块则知道文件机器逻辑和物理块,可以将逻辑块地址转化为物理块地址,逻辑文件系统管理元数据,包括文件系统的所有结构数据。通过分层结构管理,能减少重复代码。例如相同的I/O控制模块可以被多个文件系统采用。

    在磁盘上,文件系统可能包含的信息有:如何启动存储的操作系统、总的块数、空闲块的数目和位置、目录结构和具体文件。

    现代操作系统必须同时支持多个文件系统类型,如何把多个文件系统整合成一个目录结构是需要解决的问题,如果采用为每个类型编写目录和文件程序是一种显然的方法但是不能令人满意。我们可以采用一种方法,将基本系统调用的功能和实现细节分开,这就 是虚拟文件系统技术。在这种技术下,文件系统实现分为三层,第一层为文件

    系统接口,第二层是虚拟文件系统层,其目的有二:(1)定义一个清晰的VFS结构,分开文件系统的通用操作和具体实现(2)提供了在网络上唯一标识一个文件的机制。第三层实现文件系统类型或远程文件系统协议。

    目录分配和管理是文件系统中重要的一环。使用存储文件名和数据块指针的线性列表是最简单的方法,这种方法有致命的缺点是需要线性搜索,访问速度会比较慢。除此之外,另一个用于文件目录的结构是哈希表,根据文件名得到一个值,并返回一个指向线性列表中元素的指针,这就大大减少了目录搜索时间。

    磁盘本身是可以直接访问的,这就使灵活实现文件成为可能。为文件分配空间,以有效地使用磁盘和快速访问,就要求有一个合理的分配方法,通常的方法主要有三个:连续、链接和索引。

    连续分配要求每个文件在磁盘上占有一组连续的块。这种情况下,访问连续分配文件,磁盘的寻道数最小,故而寻道时间也最短。但是连续分配问题在于,访问另一个不同的新文件时有些困难,被选择来管理空闲空间的系统决定了这个任务如何完成。连续磁盘空间分配作为动态存储分配的一个具体应用,常用策略是首次适合和最优适合,模拟结果都比最坏适合要好。但是这些算法都有外部碎片问题。合并的方法可以解决这个问题,但代价是时间。另外,难以确定一个文件需要的空间大小。太小会导致文件难以扩展,即使预知,文件缓慢增长期间,也会造成很多碎片。修正的连续分配方案,在空间不足时,另一块被称为扩展的连续空间会被添加到原来的分配中。文件块的位置就成为开始地址、块数、加上指向下一个扩展的指针。

    链接分配则不存在上述连续分配的问题。链接分配下,每个文件是磁盘块的链表,这些磁盘块分布在磁盘的任何地方。目录包括文件头指针和尾部指针。这样扩展起来是非常方便的,只要有空闲块就可以增大文件。但是此方法也有缺点,即不能有效的支持文件的随机访问,必须从文件的开始读起。链接分配一种变种是FAT,目录条目含有文件首块的块号码,根据块号码索引的FAT条目包含文件下一个的块号码。这条链会一直继续到最后一块。

    索引分配将所有指针放在一起,通过索引块,解决了链接分配不用FAT就无法直接访问的问题。每个文件都有索引块,这是一个磁盘块地址的数组。这里存在一个需要解决的问题——索引块的大小该如何确定,有三种方案:(1)链接方案(2)多层索引(3)组合方案。

    空闲空间管理,一般来说,系统维护一个空闲空间链表来进行空闲空间管理。称为链表,但不一定表现为链表。通常,空闲空间表实现为位图或位向量,每块对应一位,空闲为1,占用反之。另一种方法是将所有空闲磁盘用链表链接起来,并将指向第一个空闲块的指针保存在磁盘的特殊位置。由于遍历不是一个经常性操作,所以也是可以接受的方案。对空闲链表的一个改进是将n个空闲块的地址存放在第一个空闲块中,前n-1个确实为空,最后一个包含另外n个空闲块的地址,这样的话,大量的空闲块地址可以很快的找到。另外一种方法是,记录第一块的地址和紧跟第一块的连续的空闲块的数量n,这样空闲空间表的每个条目包含磁盘地址和数量。虽然每个条目回会比原来需要更多的空间,但是表的长度会更短,这是因为连续块的数量常常大于1。

    由于文件和目录可保存在内存和磁盘上,所以必须确保系统失败不会导致数据丢失和数据的不一致性。所以我们需要一致性检查、备份和恢复。一致性检查程序将目录结构数据与磁盘数据块相比较,并试图纠正所发现的不一致,分配算法和空闲空间管理算法决定了检查程序所能发现的问题,以及如何纠正问题。

    此外,为了保证一致性,还可以采用基于日志的文件系统——执行一个特殊任务的一组操作称为事务,要执行事务时会先将元数据记录到日志上,这些修改一旦写到日志上,就会视为已提交,系统调用就可以返回到用户程序,以允许继续执行,而一旦事务已经完成,就会从日志文件里删除。这种情况下,如果系统崩溃,事务被中断,日志中的事务仍必须要完成,这就保证了文件系统结构的一致性。

参考文献:

[1] Abraham Silberschatz. 操作系统概念. 高等教育出版社, 2007.3.