# 文件管理
文件的属性
文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件
标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称
类型：指明文件的类型
位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）
大小：指明文件大小
创建时间、上次修改时间、文件所有者信息
保护信息：对文件进行保护的访问控制信息
文件内部数据组织方式
无结构文件（如文本文件）—— 由一些二进制或字符流组成，又称 "流式文件"
有结构文件（如数据库表）—— 由一组相似的记录组成，又称 "记录式文件"
记录是一组相关数据项的集合，数据项是文件系统中最基本的数据单位
其对应文件的逻辑结构
文件之间如何被组织起来
目录结构
操作系统向上提供的功能
- 创建文件（create 系统调用）
- 删除文件（delete 系统调用）
- 读文件（read 系统调用）
- 写文件（write 系统调用）
- 打开文件（open 系统调用）
- 关闭文件（close 系统调用）
文件如何放在外存
文件的物理结构
操作系统如何管理外存中的空闲块
存储空间的管理
操作系统需要提供的其他文件管理功能
文件共享：使多个用户可以共享使用一个文件
文件保护：如何保证不同的用户对文件有不同的操作权限
# 文件的逻辑结构
逻辑结构：在用户看来，文件内部的数据应该是如何组织起来的
物理结构：在操作系统看来，文件的数据是如何存放在外存的
# 无结构文件
按文件是否有结构分类，可以分为无结构文件、有结构文件
无结构文件：文件内部的数据就是一系列二进制流或字符流组成，又称 "流式文件"，如.txt 文件
# 有结构文件
有结构文件：由一组相似的记录组成，又称 "记录式文件"。每条记录由若干个数据项组成，一般来说每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种
有结构文件的逻辑结构
- 顺序文件：文件中的记录一个接一个地顺序排列（逻辑上）。记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储
- 顺序存储 —— 逻辑上相邻的记录物理上也相邻（类似于顺序表）
- 可变长记录：无法实现随机存取，每次只能从第一个记录开始依次往后查找
- 定长记录：
- 可实现随机存取。记录长度为 L，则第 i 个记录存放的相对位置是 i*L
- 若采用串结构，无法快速找到某关键字对应的记录
- 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）
- 链式存储 —— 逻辑上相邻的记录物理上不一定相邻（类似于链表）
- 无论是定长 / 可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找
- 串结构：记录之间的顺序与关键字无关（通常按照记录存入的时间决定记录的顺序）
- 顺序结构：记录之间的顺序按关键字顺序排列
- 缺点：增加 / 删除一个记录比较困难（如果是串结构则相对简单）
- 顺序存储 —— 逻辑上相邻的记录物理上也相邻（类似于顺序表）
结论：定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录）。
- 索引文件
- 建立一张索引表以加快文件检索速度。每条记录对应一个索引项
- 文件中的这些记录在物理上可以离散地存放
- 索引表本身是定长记录的顺序文件，因此可以快速找到第 i 个记录对应的索引项
- 可将关键字作为索引号内容，若按关键字顺序排列，还可以支持按关键字折半查找
- 每当要增加 / 删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合
- 另外可以用不同的数据项建立多个索引表
- 解决了顺序文件不方便增 / 删记录的问题，同时让不定长记录的文件实现了随机存取，但索引表可能占用很多空间
- 索引顺序文件
- 索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是；并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项
- 索引顺序文件的索引项不需要按关键字顺序排列，这样可以极大地方便新表项的插入
- 多级索引顺序文件
- 为了进一步提高检索效率，可以为顺序文件建立多级索引表
# 文件目录
文件控制块
目录文件中的一条记录就是一个 "文件控制块（FCB）"
FCB 的有序集合称为 "文件目录"，一个 FCB 就是一个文件目录项。
FCB 中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读 / 可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）
最重要的，最基本的还是文件名、文件存放的物理地址
FCB 实现了文件名和文件之间的映射。使用户（用户程序）可以实现 "按名存取"
对目录进行的操作：
- 搜索：当用户需要使用一个文件时，系统要根据文件名搜索目录，找到各文件对应的目录项
- 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
- 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
- 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
- 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项
# 目录结构
单级目录结构
整个系统中只建立一张目录表，每个文件占一个目录项
单级目录实现了 "按名存取"，但是不允许文件重名
在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。
单级目录结构不适用于多用户操作系统
两级目录结构
两级目录结构分为主文件目录和用户文件目录
允许不同用户的文件重名。文件名相同但对应了不同的文件
两级目录结构允许用户的文件重名，也可以在目录上实现访问限制（检查此时登录用户是否匹配），但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类
多级目录
又称树形目录结构
不同目录下的文件可以重名
用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径是个字符串。各级目录之间用 / 隔开。从根目录出发的路径称为绝对路径。
很多时候，用户会连续访问同一目录内的多个文件，每次都从根目录开始查找，是很低效的，因此可以设置一个 "当前目录"
当用户想要访问某个文件时，可以用从当前目录出发的相对路径
引入当前目录和相对路径后，磁盘的 I/O 次数减少了，这就提升了访问文件的效率
树形目录结构可以很方便的对文件进行分类，层次结构清晰，也能够有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了 "无环图目录结构"
无环图目录结构
在树形结构的基础上，增加了一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点，用户提出删除结点的请求时，只是删除该用户的 FCB、并使共享计数器减 1，并不会直接删除共享结点
注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化
索引结点（FCB 的改进）
除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引节点
目录项中只包含文件名，索引节点指针，因此每个目录项的长度大幅减小
存放在外存中的索引结点称为 "磁盘索引结点"，当索引结点放入内存后称为 "内存索引结点"。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改，此时有几个进程正在访问该文件等
由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘 I/O 的次数就少了很多
# 文件的物理结构
类似于内存分页，磁盘中的存储单元也会被分为一个个 "块 / 磁盘块 / 物理块"。很多操作系统中，磁盘块的大小与内存块、页面的大小相同
内存与磁盘之间的数据交换（即读 / 写操作、磁盘 I/O）都是以 "块" 为单位进行的，即每次读入一块，或每次写出一块
# 文件块、磁盘块
在内存管理中，进程的逻辑地址空间被分为一个一个页面
同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为一个一个的文件的 "块"
于是文件的逻辑地址也可以表示为 (逻辑块号，块内地址) 的形式
操作系统为文件分配存储空间都是以块为单位的
用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射
# 文件分配方式 —— 连续分配
目录项中记录了起始块号，文件长度
连续分配方式要求每个文件在磁盘上占有一组连续的块
优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快
缺点：不方便文件扩展；存储空间利用率低，会产生磁盘碎片
# 文件分配方式 —— 链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块，分为隐式链接和显示链接两种
隐式链接
目录中记录了文件存放的起始块号和结束块号。除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户时透明的
优点：很方便文件拓展，不会有碎片问题，外存利用率高
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间
显示链接
把用于链接文件各物理块的指针显式地存放在一张表里，即文件分配表（FAT）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存
目录项中记录了起始块号
优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高
缺点：文件分配表的需要占用一定的存储空间
考试时默认的是隐式链接的链接分配
# 文件分配方式 —— 索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理的页表 —— 建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块
索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可），但索引表需要占用一定的存储空间
链接方案
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
缺点：若文件很大，索引表很长，就需要将很多个索引链接起来。想要找到 i 号索引块，必须先依次读入 0~i-1 号索引块，这就导致磁盘 I/O 次数过多，查找效率低下
多层索引
建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块
若采用多层索引，则各层索引表大小不能超过一个磁盘块
采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K+1 次读磁盘操作
缺点：即使是小文件，访问一个数据块仍然需要 K+1 次读磁盘
混合索引
多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级简介索引（指向两层索引表）。
优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少
重点
- 要根据多层索引、混合索引的结构计算文件的最大长度（Key：各级索引表最大不能超过一个块）
- 要能分析访问某个数据块需要的读磁盘次数（Key：FCB 中会存有指向顶级索引块的指针，因此可以根据 FCB 读入顶级索引块，每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件 —— 顶级索引快是否已经读入内存）
# 文件存储空间管理
# 存储空间的划分与初始化
存储空间的划分：将物理空间划分为一个个文件卷（逻辑卷、逻辑盘）
存储空间的初始化：将各个文件卷划分为目录区、文件区
目录区主要存放文件目录信息（FCB）、用于磁盘存储空间管理信息
文件区用于存放文件数据
# 存储空间管理 —— 空闲表法
如何分配磁盘块：为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法决定要为文件分配哪个区间
如何回收磁盘块：当回收某个存储区时需要有四种情况
- 回收区前后都没有相邻空闲区
- 回收区的前后都是空闲区
- 回收区前面是空闲区
- 回收区后面时空闲区
总之，回收时需要注意表项的合并问题
# 存储空间管理 —— 空闲链表法
空闲盘块链
以盘块为单位组成一条空闲链，空闲盘块中存储着下一个空闲盘块的指针
操作系统保存着链头、链尾指针
如何分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针
如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复操作多次
空闲盘区链
以盘区为单位组成一条空闲链，连续的空闲盘块组成一个空闲盘区，空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针
操作系统保存着链头、链尾指针
如何分配：若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据
如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾
离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高
# 存储空间管理 —— 位示图法
位示图：每个二进制位对应一个盘块。位示图一般用连续的字表示，字中每一位对应一个盘块，因此可以用（字号，位号）对应一个盘块号。
（字号，位号）=（i,j）的二进制位对应的盘块号 b=ni+j，b 号盘块对应的字号 i=b/n，位号 j=b% n
如何分配：若文件需要 K 个块
- 顺序扫描位示图，找到 K 个相邻或不相邻的 0
- 根据字号、位号算出相应的盘块号，将相应盘块分配给文件
- 将相应位设置为 1
如何回收：
- 根据回收的盘块号计算出相应的字号、位号
- 将相应二进制位设为 0
连续分配、离散分配都适用
# 存储空间管理 —— 成组链接法
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX 系统中采用了成组链接法对磁盘空闲块进行管理
文件卷的目录区中专门用一个磁盘块作为 "超级块"，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的 "超级块" 数据一致
超级块中每一组保存了下一组空闲盘块数以及该组所有的空闲盘块号，每一组最后一个空闲磁盘块保存了再下一组空闲磁盘块的信息
注意：
- 若已经没有下一组空闲块，则设置为特殊值 - 1
- 一个分组中的块号不需要连续，此处只是为了让大家更方便看出各个分组的数量
如何分配：
- 检查第一个分组的块数是否足够
- 如果足够，分配第一个分组中的空闲块，并修改相应数据
- 如果刚好足够，则将最后一个磁盘块中的下一分组的最后一个磁盘块信息（也就是链接信息）复制到超级块中，保证链接不中断
如何回收：
以回收单个块为例
如果第一个分组还没有满，就把这个空闲块放到第一个分组当中
如果第一个分组已经满了，需要将超级块的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组
# 文件的基本操作
# 创建文件
进行 Create 系统调用时，需要提供几个主要参数：
- 所需的外存空间大小（如：一个盘块，即 1KB）
- 文件存放路径
- 文件名
操作系统在处理 Create 系统调用时，主要做了两件事情：
- 在外存中找到文件所需的控件（使用查找空闲空间的算法，找到空闲空间）
- 根据文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息
# 删除文件
进行 Delete 系统调用时，需要提供几个主要参数：
- 文件存放路径
- 文件名
操作系统在处理 Create 系统调用时，主要做了几件事情：
根据文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项。
根据目录项记录的文件在外存中的存放位置、文件大小等信息，回收文件占用的磁盘块。（回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理）
从目录表中删除文件对应的目录项
# 打开文件
进行 open 系统调用时，需要提供几个主要参数：
- 文件存放路径
- 文件名
- 要对文件的操作类型（如：r 只读；rw 读写等）
操作系统在处理 open 调用时，主要做了几件事：
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限
- 将目录项复制到内存中的 "打开文件表" 中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明操作的文件
# 关闭文件
进程使用完文件后，要 "关闭文件"：
操作系统在处理 Close 系统调用时，主要做了几件事：
- 将进程的打开文件表相应表项删除
- 回收分配给该文件的内存空间等资源
- 系统打开文件表的打开计数器 count 减 1，若 count=0，则删除对应表项
# 读文件
进程使用 read 系统调用完成读操作。需要指明是哪个文件，还需要指明读入多少数据、指明读入数据要放在内存中的什么位置
操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中
# 写文件
进程使用 write 系统调用完成写操作。需要指明是哪个文件，还需要指明写出多少数据、指明写回外存的数据要放在内存中的什么位置
操作系统在处理 write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存
# 文件共享
操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一文件
注意：多个用户共享同一个文件，意味着系统中只有一份文件数据。并且只要某个用户修改了文件数据，其他用户也可以看到文件数据的变化。如果是多个用户都复制了同一个文件，那么系统中会有好几份文件数据。其中一个用户修改了自己的那份文件数据，对其他的用户的文件数据并没有影响
# 基于索引结点的共享方式（硬链接）
索引节点中设置一个链接计数变量 count，用于表示链接到本索引结点上的用户目录项数。
各用户的目录项指向同一个索引节点
某用户想删除文件时，只是删除该用户的目录项，count--
只有 count==0 时才能真正删除文件数据和索引节点，否则会导致指针悬空
# 基于符号链的共享方式（软链接）
用 link 型文件，记录共享文件的存放路径，类似于快捷方式
当访问 Link 文件时，操作系统会根据其中记录的路径层层查找目录，最终找到 link 文件路径记录的共享文件
即使软链接指向的共享文件已被删除，Link 型文件依然存在，只是通过 Link 型文件的路径去查找共享文件会失败（找不到对应目录项）
用于软链接的方式访问共享文件时要查询多级目录，会有多次磁盘 I/O，因此用软连接访问
# 文件保护
# 口令保护
为文件设置一个口令，用户请求访问时必须提供口令
口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入口令，操作系统会将用户提供的口令与 FCB 中存储的口令进行对比，如果正确，则允许该用户访问文件
优点：保存口令的空间开销不多，验证口令的时间开销也很小
缺点：正确的口令存放在系统内部，不够安全
# 加密保护
使用某个密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的解密
例如：异或加密
优点：保密性强，不需要在系统中存储密码
缺点：编码 / 译码，或者说加密 / 解密要花费一定时间
# 访问控制
在每个文件的 FCB（或索引节点）中增加一个访问控制表，该表中记录了各个用户可以对该文件执行哪些操作
对文件的访问类型可分为：读 / 写 / 执行 / 删除等
实现灵活，可以实现复杂的文件保护功能
精简的访问列表：以 "组" 为单位，标记各组用户可以对文件执行哪些操作
当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限（系统需要管理分组的信息）
