操作系统笔记（王道考研） 第四章：文件管理

大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记，不知道2023版有没有新加什么内容，有的话后续再补上。

感谢我的室友HXN，他帮我写了一部分第五章的内容。

课程内容和西电平时讲课的内容大致重合，西电可能每章会多讲一点UNIX系统的实例，可以听完这课再快速过一遍老师的课件防止漏掉什么内容。

这门课讲的其实不算特别硬核，没怎么涉及具体的代码。不过我其实感觉操作系统是个大无底洞，能学到多深基本取决于愿意花多少时间和精力。如果有闲心，推荐看下南大蒋炎岩老师的《操作系统：设计与实现》和哈工大李治军老师的《操作系统》，讲的更深入，当然难度也相应的大的多。

 

其他各章节的链接如下：

操作系统笔记（王道考研） 第一章：计算机系统概述

操作系统笔记（王道考研） 第二章：进程管理（1）

操作系统笔记（王道考研） 第二章：进程管理（2）

操作系统笔记（王道考研） 第三章：内存管理

操作系统笔记（王道考研） 第四章：文件管理

操作系统笔记（王道考研） 第五章：输入输出（I/O）管理

其他各科笔记汇总

文件管理

初识文件管理

前情回顾

操作系统作为系统资源的管理者也需要对文件进行管理，文件也属于一种系统资源。

Word，PPT，PDF文档等等都是文件，各种各样的文件在我们面前呈现出不同的特性，操作系统需要关心这些特性。不同文件有不同的属性，故在使用文件的时候会有各种各样的差别

文件的属性

在一个系统当中肯定是有很多重名文件的，只是在同一文件夹下不允许有重名的文件，故用文件名并不能唯一地区分出每一个文件到底是哪一个。因此操作系统会在背后为各个文件设置一个唯一的标识符，标识符一般来说就是一连串数字和字母的组合，对用户来说毫无可读性，所以在上图的界面中也没有向用户展示出一个文件的标识符

这个文件平时是存放在外存也就是磁盘当中的，当我们双击打开这个文件的时候，操作系统需要从外存把文件的数据读入内存，因此操作系统也需要关心文件在外存当中存放的位置，只不过在外存当中存放的地址属性对用户是不可见的，只有操作系统需要关心

操作系统对系统当中的用户进行了分组，不同分组的用户对文件的操作权限是不同的。如果创建的文件不想让别的计算机用户来访问的话，就可以设置一下它的保护信息

文件内部的数据应该怎样组织起来？

无结构文件没有明显的结构特性

 

 

文件之间应该怎样组织起来？

操作系统应该向上提供哪些功能？

点击新建后，图形化交互进程其实是在背后调用了操作系统向上层提供的“create 系统调用”来完成文件创建的工作

创建文件之后，这个文件的数据就在外存当中了

双击test文件之后，操作系统先是默认自动地打开了.txt对应的应用程序，也就是记事本。这个应用程序又调用了操作系统向上提供的“read 系统调用”来实现了读文件的功能

平时我们编辑这个文件的时候，其实只是改变了文件在内存当中的副本的数据

 

从上往下看，文件应如何存放在外存？

操作系统在进行读写文件的时候也是以块为单位进行数据交换的

文件的物理结构探讨的是文件这些数据在物理上是应该怎么存放，怎么组织

文件的逻辑结构指的是文件的各个记录在逻辑上应该是什么样的一种组织关系

其他需要由操作系统实现的文件管理功能

文件的逻辑结构

 

所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的

类似于数据结构的“逻辑结构”和“物理结构”

如“线性表”就是一种逻辑结构，在用户角度看来，线性表就是一组有先后关系的元素序列，如：a,b,c,d,e …

“线性表”这种逻辑结构可以用不同的物理结构实现，如：顺序表/链表。顺序表的各个元素在逻辑上相邻，在物理上也相邻；而链表的各个元素在物理上可以是不相邻的。因此，顺序表可以实现“随机访问”，而“链表”无法实现随机访问

可见，算法的具体实现与逻辑结构，物理结构都有关（文件也一样，文件操作的具体实现与文件的逻辑结构，物理结构都有关）

无结构文件

有结构文件

 

根据有结构文件中的各条记录在逻辑上如何组织，可以分为顺序文件，索引文件，索引顺序文件三类

顺序文件

类比线性表，应该不难理解

若文件的记录是可变长的就必须在每个记录之前用一定的存储空间来表示记录的长度

在实际应用中为了减少磁盘的I/O次数，一般来说操作系统会管理一个日志文件，用该日志文件来记录对这个文件当中的各个记录进行修改的一些信息然后每隔一段比较长的时间再把这些信息统一地合并到外存当中的这个文件数据当中，比如说每隔一个小时才合并一次或者每隔十分钟才合并一次，这样就可以减少对于顺序存储的顺序进行增删改带来的一些开销

索引文件

索引表的各个表项在物理上是需要连续存放的，每一个索引表的表项大小都相等

索引顺序文件

索引顺序文件的顺序表其实是一个定长记录的串结构的顺序文件

索引顺序文件（检索效率分析）

多级索引顺序文件

 

文件目录

 

文件目录就是我们很熟悉的 Windows 操作系统的“文件夹”

 

这种一层一层的目录结构对于用户来说有什么好处？

文件之间的组织结构清晰，易于查找。编程时也可以很方便的用文件路径找到一个文件。如：

FILE *fp;
fp=fopen("F:\data\myfile.dat");
1
2

用户可以轻松实现“按名存取”

那从操作系统的角度来看，这些目录结构应该是如何实现的呢？

 

“按名存取”：按照文件的名字来操作一个文件

文件控制块

D，E盘是逻辑磁盘

打开电脑中的D盘根目录，会发现这个根目录下面有一系列的文件夹/文件目录和一些普通的文件。对于D盘这个根目录来说，它对应的目录文件如上图所示。其实就是用一个目录表来表示这个目录下面存放了哪些东西，在D盘当中的每一个文件和文件夹都会对应这个目录表当中的一个表项，这些一条一条的目录项本身就是一条一条的记录

目录文件本身就是一种有结构的文件，我们在这个地方看到的目录其实也是一种特殊的文件

 

 

目录结构 —— 单级目录结构

目录结构 —— 两级目录结构

目录结构——多级目录结构

又称树形目录结构

 

 

目录结构——无环图目录结构

在引用了共享功能之后，对于文件的删除就不能像以前那么简单（只要一个用户让删除一个文件就把这个文件的实际数据给删除），因为这个文件可能被多个用户所使用。为了解决这个问题，可以如上图所示，为每一个共享结点设置一个共享计数器

 

此时如果User1提出删除文件请求，操作系统只会把User1对应的目录项删除，并且让共享计数器减1，而这个文件的实际内容并不会被直接删除

只有共享计数器的值减为0时，就意味着这个文件不再被任何用户所使用，此时才可以把这个共享文件真正地删除

注意如果User1只是复制了一个User2的文件的话，其实它们俩所拥有的文件并不是同一个文件。当User1对自己的文件副本进行修改的时候，原来的文件数据并不会改变。共享文件则不然

索引结点（ FCB 的改进）

按照文件名来搜索目录的时候，并不需要关心除了文件名之外的其他所有信息

采用了索引结点这种机制之后，目录当中只包含文件名还有指向索引结点的指针这两个信息

 

 

文件的物理结构（文件的分配方式）

 

操作系统作为最接近硬件的软件层次需要对硬件，包括外存也就是磁盘进行管理。操作系统对磁盘的管理主要需要做两件事：

1.对非空闲磁盘块进行管理（存放了文件数据的磁盘块）

这是这一小节要探讨的“文件的物理结构/文件分配方式”的问题

2.对空闲磁盘块进行管理

这是之后的小节会探讨的“文件存储空间管理”的问题

 

文件物理结构/文件分配方式要探讨的就是文件的数据到底应该怎样存放在外存中，这些数据应该怎样被组织起来的问题

文件块，磁盘块

用户对于自己文件的这些逻辑块到底存放到了什么地方是不可知的，因此用户在操作自己的文件时使用的是（逻辑块号，块内地址）这样的形式。于是操作系统就需要负责把用户提供的逻辑块号和块内地址转换为这个文件块实际存放的物理块号和块内地址

文件分配方式 —— 连续分配

顺序访问：如果要访问逻辑块号2就必须先顺序地访问逻辑块号0和逻辑块号1，之后才能找到逻辑块号2

直接访问（随机访问）：如果要访问逻辑块号2并不需要访问其他的块，可以直接找到逻辑块号2存放的位置

读取某个磁盘块的时候需要把磁头放到那个磁盘块相应的位置

 

连续分配（总结）

文件分配方式 —— 链接分配

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块，然后用指针链接的方式把这些磁盘块都给串联起来。分为隐式链接和显式链接两种

链接分配 —— 隐式链接

 

总结如下

链接分配 —— 显式链接

 

总结如下

考试题目中遇到未指明隐式/显式的“链接分配”，默认指的是隐式链接的链接分配

文件分配方式 —— 索引分配

 

1.链接方案

在每个索引块当中用一定的空间存储指向下一个索引块的指针

由于各个索引块之间是用链接的方式连起来的，所以为了找到第2个索引块的块号操作系统需要首先把第1个索引块读入内存，然后才能根据索引块当中的指针找到第2个索引块的块号并且把第2个索引块读入内存

 

2.多层索引

在FCB中只需要记录它的顶级索引表存放的索引块号是多少

若采用三层索引，则文件的最大长度为

256*256*256*1KB=16GB

类似的，访问目标数据块，需要4次磁盘I/O

 

假如有一个文件很小，数据块只有1KB这么大，但是在物理上采用的是两层索引结构，那么读入这个文件1KB的内容依然需要3次读磁盘操作。故多层索引也存在一些小小的问题

 

3.混合索引

索引分配（总结）

 

逻辑结构VS物理结构

本节会举一些具体的例子，把逻辑结构和物理结构当中涉及到的一些很相似的概念进行对比

例：C语言创建无结构文件

如果在代码运行的目录下没有test.txt这个文件，调用fopen函数之后会自动给你新建一个

逻辑结构（从用户视角看）

物理结构（从操作系统视角看）

操作系统会根据它的文件管理策略来决定到底是用连续分配还是其他分配方式把这些文件的数据块存到磁盘里面

操作系统在处理Read系统调用请求时会把fgetc这个函数向它传递的逻辑地址转换为（逻辑块号，块内偏移量）的形式，然后再根据自己的存储分配策略把逻辑块号转换为与之对应的物理块号。这是操作系统在背后帮用户做的事情，对用户来说这些事情是不可知的，也没必要关心。用户作为文件的使用者只需要关心文件里各种各样的数据到底存放在哪一个逻辑地址里

例：C语言创建顺序文件

物理结构（从操作系统视角看）

作为用户只需要能够提供想要访问的记录所存放的逻辑地址，然后剩下的逻辑地址转换为逻辑块号，逻辑块号再转换为物理块号这些事情都是操作系统在背后帮我们完成的

懵逼点：顺序文件采用顺序存储/链式存储

静态链表

用户在创建一个文件的时候可以自己决定到底是用顺序存储的方式还是用链式存储的方式来存放这些记录。但是无论如何在用户的视角看来这些记录肯定都是占用了一整片的连续空间

链式存储的顺序文件采用连续分配…

要会区分文件的逻辑结构里提到的的链式存储和文件的物理结构里提到的链接分配

链式存储指的是在文件内部的那些记录的先后顺序是用链接指针连起来的，这是用户自己来设计的，操作系统并不管

链接分配中链接是操作系统做的事情，用户并不需要管。操作系统会把用户给出的这一整个很大的文件拆分成一个个的逻辑块，然后在磁盘里存放这些逻辑块时操作系统会用链接的方式来记录这些逻辑块之间的先后顺序

逻辑结构：索引文件

这种逻辑结构同样也是由文件的创建者自己来决定的

索引文件采用索引分配

要会区分文件的逻辑结构里提到的的索引文件和文件的物理结构里提到的索引分配

 

文件存储空间管理

在之前的小节中我们学习了文件的物理结构，也就是对非空闲磁盘块的管理。这一小节要学习的对存储空间的管理其实就是对空闲的那些磁盘块的管理

 

存储空间的划分与初始化

像FCB，索引结点这些就是存放在目录区当中的

用于磁盘存储空间管理的那些信息，那些数据结构也是存放在目录区当中的，就比如这一小节接下来会学习的空闲表，位示图之类的数据结构

存储空间管理 —— 空闲表法

适用于“连续分配方式”

 

参考内存管理中的动态分区分配思考系统会如何处理以下情况

Eg：新创建的文件请求3个块，采用首次适应算法

Eg：假设此时删除了某文件，系统回收了它占用的15，16，17号块

存储空间管理 —— 空闲链表法

 

像上例中链头是20号磁盘块，链尾是0号磁盘块

 

存储空间管理 —— 位示图法

连续分配，离散分配都适用

 

存储空间管理 —— 成组链接法

每一个分组的盘块数量有上限

分组的第一个磁盘块还需要记录下一组空闲盘块的一些信息

 

如何分配？

Eg：需要1个空闲块

超级块已经读入内存，进行检查时不需要读磁盘操作

 

 

Eg：需要100个空闲块

超级块其实充当了链头的作用，在这个链头当中永远要保持指向下一个分组的一些信息

 

如何回收？

Eg：假设每个分组最多为100个空闲块，此时第一个分组已经有99个块，还要回收一块

 

Eg：假设每个分组最多有100个空闲块，此时第一个分组已有100个块，还要再回收一块

把超级块当中的内容复制到新回收的块当中，这样新回收的块作为一个新的分组就拥有了指向下一个分组的这些链接的指针。由于超级块永远要指向第一个分组，所以要修改超级块的数据，让它指向第一个分组即新的回收块组成的新分组

 

文件的基本操作

 

创建文件

删除文件

打开文件

根据提供的文件存放路径在外存当中找到这个目录对应的目录表

用户对文件的访问权限的信息也是记录在目录项当中的，如果没有操作权限的话就可以拒绝用户打开文件终止处理

打开文件时并不会把文件的数据直接读入内存，只是把文件的目录项复制到内存的打开文件表当中

 

系统的打开文件表会记录所有的正在被其他进程使用的文件的一些信息

每个进程也会有自己的打开文件表

关闭文件

读文件

在对文件进行读写操作之前一定要先打开文件

这些参数的填充都是记事本这个进程在背后为用户完成的

写文件

文件共享

 

操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件

注意：多个用户共享一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化

如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响

基于索引结点的共享方式（硬链接）

基于符号链的共享方式（软链接）

存放路径也可以保存为“C:/User2/bbb”

 

来看一下Windows操作系统当中快捷方式的例子

 

假设此时User1和User2都不再需要使用文件1，由于此时count值变为了0，因此这个文件还有它的索引结点就可以直接被删除了

 

还是结合Windows操作系统为例

 

文件保护

 

操作系统需要保护文件的数据安全

口令保护

当用户想要访问一个文件时操作系统无论如何肯定要找到这个文件对应的FCB或者索引结点

加密保护

用密码和文件的原始数据依次做异或运算

系统当中保存的并不是文件的原始数据，而是对文件进行加密之后的这一份数据

访问控制

不同系统对操作类型的划分不一样

每一个用户都会从属于其中的一个或者两个分组，操作系统需要记录哪一个用户是属于哪一个分组

如果说这个文件主想要让某个用户也拥有读的权限的话，那么就可以由文件主把这个用户放到“文件主的伙伴”这个分组当中

Windows的访问控制

首先我们可以给自己的Windows电脑添加一个新的本地账户。像Windows10就可以在设置当中找到添加一个账户的选项

依次选择红框部分

会跳出一个让我们建立一个新的账户的页面， 因为要创建的是本地账户，所以点“添加一个没有Microsoft账户的部分”

在弹出的界面中可以输入想要设置的新账户的账户名，比如说“临时访客”

 

点下一步确认后，就可以在“家庭和其他成员”这个地方看到“临时访客”这个本地账户了

 

接下来可以随便打开电脑当中的一个文件或者文件夹，右键选择属性。然后在“安全”页签里可以看见Windows对各种用户的分组还有各个用户实行访问控制的界面

 

如果不想让“临时访客”用户访问“照片”文件夹，则

“临时访客”用户本来属于Users分组，Users分组本来是允许读取文件信息的，但我们又在”临时访客“这选择了拒绝读取这个文件，由于拒绝项的优先级高于允许项，所以虽然”临时访客“也属于Users分组，但是操作系统依然会认为“临时访客”这个用户不允许读取这个文件这个目录

 

切换成“临时访客”用户后，会发现无法打开“照片”文件夹

 

文件系统的层次结构

文件系统的层次结构

用户接口这一层要做的事情就是之前在”文件的基本操作“那一小节介绍的那些东西

打开一个文件无非就是把那个文件对应的目录项复制到打开文件表当中

如果采用索引文件这种逻辑结构，会为文件当中的各个记录建立一个索引表，为了查询到这些记录对应的逻辑地址就需要查询索引表，而在查询文件的索引表之前就需要先把索引表调入到内存的文件信息缓冲区当中

之前提到的所有这些准备最后都是为了操作外存或者说磁盘上的一些数据

 

不同层次与对应的小节：

用户接口 —— 文件的基本操作

文件目录系统 —— 文件目录

存取控制模块 —— 文件保护

逻辑文件系统与文件信息缓冲区 —— 文件的逻辑结构

物理文件系统 —— 文件的物理结构

辅助分配模块 —— 文件的存储空间管理

设备管理模块 —— 之后磁盘管理相关的那些小节

 

“文件系统实例” 一节无课件，记笔记比较困难。故此处略过不计

该节主要是用OneNote通过画一个很直观的例子把之前学的抽象的内容串起来。考试不可能考这么复杂和这么综合的问题，有兴趣可以自己去看视频

 

磁盘的结构

磁盘，磁道，扇区

如何在磁盘上读/写数据

磁头会由磁头臂带动，磁头的移动位置只有固定的两个方向

磁盘是由很多个盘片垒起来的

盘面，柱面

一个盘片正面可以是一个盘面，背面也可以是一个盘面

磁盘的物理地址

磁盘的分类

 

磁盘调度算法

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

先来先服务算法（FCFS）

最短寻找时间优先（SSTF）

扫描算法（SCAN）

LOOK 调度算法

循环扫描算法（C-SCAN）

C-LOOK 调度算法

 

减少延迟时间的方法

 

前情回顾

读完一个扇区之后，磁头需要有一小段时间做中间的准备，在这段时间内磁头不能读入任何数据

连续读入逻辑上相邻的几个扇区号对应的扇区需要转动好几圈磁盘，延迟时间会特别长

减少延迟时间的方法：交替编号

磁盘地址结构的设计

(00,000,000)$\sim$(00,000,111)：0号盘面的0号柱面的8个扇区

根据之前的分析知道，在转了一圈之后磁头可以依次读入0，1，2，3这几个扇区的数据。在转第二圈之后这个磁头又可以依次读入4，5，6，7这几个编号对应的扇区里的数据

启动磁头臂还有移动磁头是一种物理上的移动，它所花费的时间是比较高的

(000,00,000)$\sim$(000,00,111)：0号盘面的0号柱面的8个扇区

(000,01,000)$\sim$(000,01,111)：1号盘面的0号柱面的8个扇区

减少延迟时间的方法：错位命令

假设此时要读取物理地址为0的扇区到物理地址为8的扇区（即(000,00,000)$\sim$(000,01,000)）

首先要读取0号盘面最内侧磁道的所有扇区。故首先要把0号盘面的磁头激活，然后让磁盘开始旋转，旋转的过程中进行读写。通过之前的分析知道，它需要转两圈才可以把最内测的磁道读完，转了两圈后磁头指向的位置和开始时一样

但是之前说过在读取完一个扇区之后需要有一小段时间进行处理，并不能立即读取下一个扇区，而磁盘又是在不停旋转的，所以在读完了0号盘面的最后一个扇区之后磁盘继续旋转，在旋转过程中由于磁头还没有准备好读写数据，1号盘面的0号扇区也就是物理地址为8的这个扇区从磁头下面划过的过程中并不能直接把这块的数据读入。如果要读入这块的数据，只能等磁盘再转一圈，让这个扇区再次划过磁头下方。也就是说如果我们把这些盘面相对位置相同的这些扇区都设置为相同的编号，可能会增加延迟时间，为了解决这个问题，可以用错位命名的方式

 

磁盘的管理

 

磁盘初始化

磁盘刚被制造出来时其实是只被划分成了一个个的磁道，扇区的划分在出厂之前低级格式化时进行

之前说的“一个扇区可以存放的数据大小”其实指的是数据区域可以存放的大小

讲文件的物理结构时提到过链式结构，也就是把文件的那些数据块用链接的方式连起来。前一个数据块指向下一个数据块的指针就可以保存在尾部部分，也就是说链接指针并不需要占用数据区域，这样可以方便操作系统管理

Step3：进行逻辑格式化，创建文件系统。包括要创建这些根目录的目录文件

引导块

计算机开机时需要进行一系列初始化的工作，包括初始化CPU，初始化内存，还有初始化像寄存器之类的一些硬件部件。这些初始化工作是通过执行初始化程序（自举程序）完成的

磁盘完成了物理格式化，磁盘分区和逻辑格式化之后，就可以把操作系统的那些相关数据写到磁盘中了，也就是我们所谓的自己安装操作系统的过程

自举装入程序的复杂度不高，很小。所以可以保证自举装入程序不会出错不需要更改

坏块的管理

坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它

标记为坏块的这些块之后不再分配给任何一个文件

操作系统在对存储空间进行管理的时候肯定需要读取文件分配表FAT的内容

扇区备用：假如此时操作系统想要使用一个已经坏掉的块，在硬件的层次磁盘控制器硬件部件就会用其中某一个好的备用块来替换这个坏块