计算机操作系统重点概念整理-第五章 文件管理【期末复习|考研复习】

第五章 文件管理 【期末复习|考研复习】

计算机操作系统系列文章传送门：
第一章 计算机系统概述
第二章 进程管理
第三章 进程同步
第四章 内存管理
第五章 文件管理
第六章 输出输出I/O管理

前言

给大家整理了一下计算机操作系统中的重点概念，以供大家期末复习和考研复习的时候使用。
参考资料是王道的计算机操作系统和西电的计算机操作系统。

五、文件管理

5.1 文件的基础概念

文件――就是一组有意义的信息/数据集合。
文件的属性：1、文件名。2、标识符（一个系统内文件标识符唯一）。3、类型。4、位置（文件存放路径）。5、大小。6、保护信息（对文件进行保护的访问控制信息）。7、时间、日期。
文件的所有信息都保存在目录结构中，而目录结构保存在外存上，文件信息在需要时才调入内存。通常目录条目包括文件名和其唯一的标识符，而标识符定位其他属性的信息。
Linux中文件分为普通文件-、目录文件d、字符设备文件c、块设备文件b、软链接l、 管道文件p、套接字s。

5.2 文件的逻辑结构

按照逻辑结构，文件分为有结构文件和无结构文件。
无文件结构（流式文件）以字节为单位，对于记录的访问只能通过穷举搜索的方式。对于基本信息单位操作不多的文件适合采用字符流无结构形式：如源程序文件、目标代码文件。
有结构文件的逻辑结构分为顺序文件、索引文件、索引顺序文件、直接文件/散列文件。

5.2.1 顺序文件

顺序文件:文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储（相当于数组）或链式存储（相当于链表）。
顺序存储又可以分为串结构（记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序）和顺序结构（记录之间的顺序按照关键字顺序排列）。定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取;若能再保证记录的顺序结构，则可实现快速检索(即根据关键字快速找到对应记录)。

5.2.2 索引文件

建立一张索引表来快速找到第i个记录。索引表本身是定长记录的顺序文件。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

5.2.3 索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是:并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。（ABCD为首字母的关键词中每个关键词的地址指向的是首字母为关键词的一组记录）。

5.3 文件的目录信息

5.3.1 文件控制块

目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个在该放在该目录下的文件。目录文件中的一条记录就是一个“文件控制块（FCB)。FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等)，使用信息（如文件的建立时间、修改时间等）。最重要，最基本的还是文件名、文件存放的物理地址。

5.3.2 索引节点

Linux系统采用了文件名和文件描绘信息分开的方法，文件描述信息单独形成一个称为索引节点的数据结构，简称i节点 。一个文件由目录项、inode和数据块组成。目录项：包括文件名和inode节点号。inode：又称文件索引节点，包含文件的基础信息以及数据块的指针。数据块：包含文件的具体内容。
文件是存储在硬盘上的，硬盘的最小存储单位叫做扇区 sector，每个扇区存储512字节。操作系统读取硬盘的时候，不会一个个扇区地读取，这样效率太低，而是一次性连续读取多个扇区，即一次性读取一个块block。这种由多个扇区组成的块，是文件存取的最小单位。块的大小，最常见的是4KB，即连续八个sector组成一个block。
文件数据存储在块中，那么还必须找到一个地方存储文件的元信息，比如文件的创建者、文件的创建日期、文件的大小等等。这种存储文件元信息的区域就叫做inode，中文译名为索引节点，也叫i节点。因此，一个文件必须占用一个inode，但至少占用一个block。

5.4 文件的目录结构

5.4.1 单级目录结构

整个系统只建立一张目录表，每个文件占一个目录项。单级目录实现了按名存续但不允许文件重名。显然单击目录结构不适于多用户操作系统。

5.4.2 二级目录结构

二级目录结构采用主文件目录和用户文件目录，允许不同用户文件中名，也可以在目录上实现访问限制（检查此时登录的用户名是否匹配）。但缺乏灵活性，用户不能对自己的文件进行分类。

5.4.3 多级目录结构（树形目录结构）

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。

5.4.4 无环图目录结构

无环图目录结构在树形目录结构的基础上增加了一些指向同一个节点的有向边，使整个目录形成一个有向无环图，可以使多用户之间更方便地进行文件共享。可以用不同的文件名指向同一个文件，甚至可以指向同一个目录。需要为每个共享节点设置一个共享计数器，记录此时共有多少个地方在此共享该节点。用户提出删除节点的请求时只是删除该用户的FCB并使共享计数器减1，并不会直接删除共享节点。只有当共享计数器减为0时，才删除节点。 共享文件不同于复制文件，在共享文件中由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据那么所有的用户都可以看到这个文件数据的变化。

5.5 文件共享

硬链接：一般情况下，文件名和inode号码是"一一对应"关系，每个inode号码对应一个文件名。但是，Linux系统允许，多个文件名指向同一个inode号码。这意味着，可以用不同的文件名访问同样的内容；对文件内容进行修改，会影响到所有文件名；但是，删除一个文件名，不影响另一个文件名的访问。这种情况就被称为"硬链接"（hard link）。inode信息中有一项叫做"链接数"，记录指向该inode的文件名总数，这时就会增加1。反过来，删除一个文件名，就会使得inode节点中的"链接数"减1。当这个值减到0，表明没有文件名指向这个inode，系统就会回收这个inode号码，以及其所对应block区域。
软链接：文件A和文件B的inode号码虽然不一样，但是文件A的内容是文件B的路径。读取文件A时，系统会自动将访问者导向文件B。因此，无论打开哪一个文件，最终读取的都是文件B。这时，文件A就称为文件B的"软链接"（soft link）或者"符号链接（symbolic link）。这意味着，文件A依赖于文件B而存在，如果删除了文件B，打开文件A就会报错：“No such file or directory”。这是软链接与硬链接最大的不同：文件A指向文件B的文件名，而不是文件B的inode号码，文件B的inode"链接数"不会因此发生变化。

5.6 文件实现——文件分配方式（文件物理结构）

在内存管理中，进程的逻辑地址空间被分为一个一个页面。在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射。块的大小为4KB。

5.6.1 连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB)。物理块号=起始块号＋逻辑块号。
优点:支持顺序访问和直接访问（即随机访问)；连续分配的文件在顺序访问时速度最快。缺点:不方便文件拓展;存储空间利用率低，会产生磁盘碎片。

5.6.2 链接分配——隐式链接

接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB)，从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块…
优点:很方便文件拓展，不会有碎片问题，外存利用率高。缺点:只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

5.6.3 链接分配——显式链接

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table)。一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项( FCB)，从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。
优点:很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。缺点:文件分配表的需要占用一定的存储空间。

5.6.4 索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表――建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB)，从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知道i号逻辑块在外存中的存放位置。可见，索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配一个空闲块，并增加一个索引表项即可)，但是索引表需要占用一定的存储空间。
对于索引表太大采用三种方式解决：
①链接方案 : 如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点:若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。②多层索引:建立多层索引(原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。缺点:即使是小文件，访问一个数据块依然需要K+1次读磁盘。③混合索引:多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表)、还包含两级间接索引(指向两层索引表)。优点:对于小文件来说，访问一个数据块所需的读磁盘次数更少。

5.6.5 三种分配方式总结

5.7 文件实现——文件存储空间管理（对空闲磁盘块的管理）

存储空间的划分:将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)。所谓的文件卷就相当于电脑上的C盘，D盘等。一个文件卷中，文件数据信息的空间（文件区）和存放文件控制信息FCB的空间（目录区）是分离的。逻辑卷在提供文件服务前必须对对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放逻辑卷等信息的超级块。文件存储设备分为许多大小相同的物理块并以块为信息为单位交换信息，因此文件存储设备管理实质上是对空闲块的组织管理，包括空闲块的组织、分配、回收等问题。

5.7.1 空闲表法

为一个磁盘创建一个表，来存储空闲磁盘块的位置。如何分配磁盘块 : 与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。回收时需要注意表项的合并问题。

5.7.2 空闲链表法

空闲链表发分为空闲盘块链和空闲盘区链。
空闲盘块链以盘块为单位形成1条空闲链，空闲盘块中存储着下一个空闲盘块的指针。操作系统保存着链头、链尾指针。如何分配:若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。如何回收:回收的盘块依次挂到链尾，并修改空闲链的链尾指针。适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。
空闲盘区链以盘区为单位形成1条空闲链，空闲盘区中的第一个盘块记录了盘区的长度、下一个盘区的指针。如何分配:若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。如何回收:若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

5.7.3 位示图法

位示图:每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。注意盘块号、字号、位号式从0还是1开始的。从0开始，n表示字长，则（位号，字号）=（i，j）对应的盘块号b=ni+j。b号盘块对应的字号为i=b/n，位号b%n。从1开始，n表示字长，则（位号，字号）=（i，j）对应的盘块号b=n(i-1)+j。b号盘块对应的字号为i=(b-1)/n+1，位号(b-1)%n+1。

5.7.4 成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。文件卷的目录区中专门用一个磁盘块作为“超级块”，超级块用来建立空闲空间管理表格和存放逻辑卷等信息，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。

Eg :需要1个空闲块：①检查此时超级块的块数是否足够。1<100，因此是足够的。②分配第一个分组（201）中的1个空闲块，并修改相应数据.
Eg :需要100个空闲块①检查此时超级块的块数是否足够。100=100，是足够的。②分配整个100个分组。但是由于300号块内存放了再下一组的信息，因此300号块（400-301）的数据需要复制到超级块中。

5.8 文件系统层次结构

假设某用户请求删除文件“D:/工作目录/学生信息.xlsx”的最后100条记录。1、用户需要通过操作系统提供的接口发出上述请求——用户接口。2、由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项――文件目录系统。3、不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块（存取控制验证层)。4、验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址――逻辑文件系统与文件信息缓冲区。5、知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址――物理文件系统。6、要删除这条记录，必定要对磁盘设备发出请求――设备管理程序模块。7、删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收――辅助分配模块。

5.9 磁盘组织与管理

5.9.1 磁盘的结构

磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据，磁盘的盘面被划分成一个个磁道。这样的一个“圈”就是一个磁道。一个磁道又被划分成一个个扇区，每个扇区就是一个“磁盘块”。传统一个扇区512B。所有盘面中相对位置相同的磁道组成柱面。可用(柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。

5.9.2 一次磁盘读/写操作需要的时间

寻找时间(寻道时间)Ts:在读/写数据前，将磁头移动到指定磁道所花的时间。
寻道时间Ts ：假设耗时为s;②移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则:寻道时间Ts = s + mn。
延迟时间Tr：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r(单位:转/秒，或转/分），则平均所需的延迟时间Tr=(1/2)(1/r)= 1/2r。5400转的硬盘，相当于一周11.1ms，Tr=5.55ms。
传输时间Tt:从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则:传输时间Tt = (1/r)*(b/N) = b/(rN)。
总的平均存取时间 T=Ts+ 1/2r + b/(rN)。

5.10 磁盘调度算法

5.10.1 先来先服务算法（FCFS）

优点：公平。缺点：如果大量进程竞争使用磁盘请求访问的磁道很分散则先来先服务在性能上很差寻道时间长。

5.10.2 短寻找时间优先（SSTF）

SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优)
优点：性能较好，平均寻道时间短。缺点：可能产生饥饿现象。

5.10.3 扫描算法（SCAN）

SSTF算法会产生饥饿的原因在于:磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN)的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。
优点：性能较好，平均时寻道时间较短，不会产生饥饿现象。缺点：只有到达最边上的磁道才能改变磁头移动方向，SCAN算法对于各个位置磁道响应频率不均匀。

5.10.4 LOOK调度算法

扫描算法（SCAN)中，只有到达最边上的磁道时才能改变磁头移动方向，LOOK调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。(边移动边观察，因此叫LOOK)。比SCAN的寻道时间更短。

5.10.5 循环扫描算法（C-SCAN）

SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
优点：比起SCAN来对于各个位置磁道响应频率很均匀。缺点：只有到达最边上磁道才能改变磁头的方向，寻道时间比SCAN算法更长。

5.10.6 C-LOOK调度算法

C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
优点：比起C-SCAN算法来说不需要每次移动到最内或最外侧才改变磁头使得寻道时间更短。

5.10.7 减少延迟的办法

磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”。
若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。0，1，2，3，4，5，6，7->0，4，1，5，2，6，3，7。
磁盘的物理地址式（柱面号、盘面号、扇区号），柱面到柱面需要磁头移动，比激活其他盘面的时间要长的多，因此是柱面号、盘面号、扇区号。

5.11 提高磁盘I/O速度的途径

5.11.1 磁盘高速缓存

在内存中为磁盘盘块设置一个缓冲区在缓冲区中保存某些盘块的副本.当出现一个访问磁盘的请求时由CPU先去看磁盘高速缓冲器上面所请求的盘块内容是否已在磁盘高速缓存中，如果在则从磁盘高速缓存中获取，这样就省去了启动磁盘的操作，如果不在则需要启动磁盘将所需要的磁盘内导入并将内容送给磁盘高速缓存。
数据交付的方式分为数据交付和指针交付。数据交付是直接将高速缓存中的数据传送到请求者进程的内存工作区中；指针交付只是将高速缓存中区域中的指针交付给请求使用者进程，进而节省了数据从磁盘高速缓存存储空间到进程内存工作的时间。
置换算法：较长使用的是最近最久未使用算法LRU，置换算法应当考虑访问的频率、可预见性和数据的一致性。内存是一种易失性的存储器一旦数据系统发生故障存放在缓存中的数据将会丢失，对于那些会严重影响到数据一致性的盘块数据和很久不可能再使用的盘块数据都尽量放在LRU链的头部。优先写回磁盘减少发生数据不一致的概率。
周期性写回磁盘：根据LRU算法那些经常要被访问的板块可能一直保存在高速缓存中长期不会写入磁盘，周期性的，强制性地将所有在高速缓存中的已修改的盘块的数据写回磁盘。

5.11.2 提高磁盘I/O的其他办法

1、提前读：如果是采用顺序访问的方式。便可预知下一次要读取的板块可以采用预先读的方式。2、延迟写 时缓冲区的数据本应立刻写回磁盘但考虑缓冲区的数据可能会被其他部分访问，则先挂到空闲缓冲区队列的尾部。3、优化物理块的分配采用链接组织和索引组织的方式，会增加磁头的移动距离，所以要定期对文件盘会进行优化。

5.11.3 RAID-廉价磁盘冗余阵列

该系统利用一个磁盘阵列控制器来统一管理和控制一组磁盘驱动器组成一个大的磁盘系统,RAID不仅增加了磁盘的容量而且极大地提高了磁盘的I/O速率和整个磁盘系统的可靠性。
采用并行交叉存取：用于提高访问内存速度的并行交叉存取技术应用到磁盘存储系统中以提升对磁盘的I/O速度。在该系统中系统将每一盘块中的数据分为若干子盘块数据再把每个磁盘块数据分别存储于不同的磁盘中相同的位置，以后将一个盘块的数据存入内存中采用并行传输的方法，时间大大减少。
RAID的优点：1、可靠性高，各级均采用了容错技术，当阵列中某一磁盘损坏时并不会造成数据的丢失。2、磁盘I/O速率高，由于采用了并行交叉存取方式，磁盘的I/O速率可提高N-1倍。3、性能价格比高，RAID的体积与相同容量的速度和大型磁盘系统相比，可靠性高。仅牺牲1/N的容量换取了高的可靠性。

下一章 第六章 输入输出管理

第六章 输出输出I/O管理