第四章 文件系统
在多程序多用户的系统上，读取数据有以下问题：
- 如何找到信息？
- 如何防止一个用户读取另一个用户的数据
- 如何知道哪些块是空闲的？
通过前面的学习， 我们知道 操作系统对处理器进行抽象 建立了进程这个概念； 通过对物理存储器的抽象建立了 虚拟地址空间的概念， 现在，为了解决问题， 就创建了 文件 这个抽象概念。
操作系统处理文件的部分 称为文件系统。
4.1文件
文件命名：如homepage.html, 圆点前面是名字，圆点以后是文件扩展名，.html表示 这是一个html文件。在某些系统中，文件扩展名是一种约定，指定为某一类文件，但是操作系统并不强制采用这种形式，常见扩展名如下：
文件结构：常见三种方式：
- 无结构字节序列：全都是字节，其内容含义只有在用户程序中解释，UNIX和Windows都采用这种方法
- 记录序列：这种结构中，文件时有固定长度记录的序列，每个记录尤其内部结构
- 树：文件由一颗记录树构成，每个记录长度不一，每个记录的固定位置有一个键，通过键可以快速查找，一般在处理商业数据的大型计算机系统中使用。
文件类型：
- 目录（或者说文件夹）：每个目录也是一种文件， 是管理文件系统结构的系统文件
- 普通文件：一般分为ASCII文件和二进制文件。 ASCII文件的优势就是可以显示和打印， 也是普通用户常用的文件，如文本。二进制文件如视频图片等。
- 字符特殊文件（character special file）
- 块特殊文件（block special file）
下图是一个可执行二进制文件和一个存档普通文件的结构，可执行二进制文件的结构有：文件头、正文、数据、重定位位，符号表。
文件访问：
- 早期只有顺序访问
- 随机访问：按照关键字位置来访问记录， 可以任意跳转。有两种方式指示从何处开始读取文件，一种是read操作时给出开始文件位置，另一种是通过seek操作设置访问的位置。、
文件属性： 
文件操作： 常见操作有：create， delete，open，close，read，write，append，copy， seek，get attributes，set attributes, rename.其中seek用于随机访问文件，把当前位置指针指向文件中特定位置后，从该位置顺序读取数据。
4.2目录
文件系统通常提供目录或文件夹用于记录文件位置，通常，目录或者说文件夹本身也是文件
原文地址：https://blog.csdn.net/qq475703980/article/details/82533918
一级目录系统：在早期系统或者限制一些简单的嵌入式系统中，采用，目录只有一个层级，如下，方形表示目录文件，原型表示普通文件： 
层次目录系统：多数计算机系统都采用多层次目录系统，如下： 
路径名：在层次目录系统中，每个文件都有一个绝对路径名，它是从根目录到文件的路径，例如 /usr/ast/mailbox。不同系统的路径的分隔符不同，有 / 或者 \ 或者 > ， 如下： 
在操作系统的每个目录有两个特殊目录项： “.”和“..”， 读作dot和dotdot, dot指当前目录， dotdot指父目录：
目录操作：常用目录操作有 create， delete， opendir， closedir, readdir, rename, link， unlink等。
4.3文件系统的实现
4.2.1文件系统布局
文件系统放在磁盘上，多数磁盘划分为一个或多个分区，每个分区有一个独立的文件系统。磁盘的0号扇区称为主引导记录（Master Boot Record，MBR）,用来引导计算机。MBR的结尾是分区表，该表给出了每个分区的其实和结束位置。表中的一个分区标记为活动分区，计算机启动时，BIOS读入并执行MBR，MBR第一件事就是确定活动分区，然后读入它的第一个块，称为引导块（boot block），然后执行它。引导块中的程序将装载该分区中的操作系统。为了统一，每个分区都从第一个引导块开始，即使它并不包含操作系统，不过也不排除它未来不会安装操作系统。
除了都是从引导块开始，不同文件系统的磁盘分区的布局是不同的，下图是一种文件系统的结构布局， 第一个是超级块（superblock），包含了文件系统的所有关键参数，在计算机启动或者该文件系统首次使用时，超级快会被读入内存，其中的典型信息有：文件系统类型使用的魔数，文件系统中块的数量以及其他重要管理信息，示例图如下：
4.2.2文件的实现
文件存储的关键问题是记录各个文件分别用到哪些磁盘块，主要有：连续分配、聊表分配、采用内存中的表进行链表分配，i节点。
连续分配：把文件作为一串连续数据块存储在磁盘上。简单且效率高，但是随着时间分配，磁盘变得零碎，如果某个连续空间比较小，而文件比较大，就不会放入这个空间，造成浪费。最终形成很多磁盘空洞，这时，如果重新挪动位置压缩磁盘空间，代价就太大了。因此，这个比较适合一次性写入的介质。
链表分配：磁盘每个块的第一个字作为指向下一个块的指针，块的其他部分存放数据。 链表不会浪费空间，但是随机访问很慢。而且由于每个块保存了指针，剩余部分存储的字节就不再是2的整数次幂，而许多程序都是以2的整数次幂读取磁盘块，这也会降低效率。
采用内存中的表进行链表分配：对链表分配的优化，就是把每个磁盘块的指针，存放在内存的一个表中，就可以解决链表分配的不足。当有连续块是，就可存放在连续块中，当连续块不够，就指向其余空闲的块中。内存中这样的表格称为 文件分配表（File Allocation Table， FAT）。 示例图如下： 
不过这种方法的缺点就是必须把整个表存在内存中，如果磁盘很大，这个表就会特别大，因此FAT并不怎么适合大型磁盘中。
i节点：给每个文件赋予一个名字为 i节点（index-node）的数据结构，用来记录文件包含了哪些磁盘块。只要给定i节点，就能找到文件的所有块。这种方式的优势在于，只有文件被打开时，其i节点才在内存中，从而节省了内存。
如果每个i节点只能存储固定数量的磁盘地址，那么一个文件包含的磁盘块超过了固定数量怎么办呢？ 其中一种解决办法就是最后一个地址指向一个包含额外地址的底盘块，升级版是最后两个或三个地址都可以指向其他存放地址的磁盘块，示例图： 
4.2.3 目录的实现
要找到文件，就要根据路径名去找，路径就涉及到目录以及在何处去存放文件的属性。实现方式有两种：1.简单目录，即在目录文件中有一个固定大小的目录项列表，每个文件对应一项，，其中有（固定长度）的文件名、属性的结构体、磁盘块的位置的一个或多个地址。 2.对于采用了i节点的系统，可以把属性存放在i节点中，而不是目录项中，这样，目录项中就只需要存放文件名和i节点号了，这种方式更好。两种方式的目录项示例图如下：
还有另一个问题，就是文件名的长度以及文件名的保存。第一种简单的方式就是给予文件名一个固定的长度限制，同时给文件名分配固定大小的目录空间。但是如果文件名用不了这么多长度，就白白浪费了。第二种方式是 每个目录项前面部分是固定格式的数据，如目录项长度、文件属性，然后接上可变的任意长度的文件名，文件名以特殊字符（通常为0）结束。如下图图a, 这个方法的缺点就是每个文件项的大小不一，如果移走一个文件，再新来一个文件，新文件的文件项不一定刚好适合这个空隙。这和连续磁盘空隙类似。
* 第三种*方式就是目录项有一个固定长度，而将文件名放在目录后面的堆中，这样移走一个文件，下一个文件进来了，也刚好可以适合这个空隙。不过，就必须对堆进行管理。示例图如下： 
4.3.4共享文件
在上图中，目录C下有一个文件和目录B共享， 有两种方式，一种是链接（link）,共享文件的所有者是C，但是这个文件在C的目录项的计数为2，当在C目录下去删除共享文件时， 如果共享文件发现计数为2，就不会去删除这个文件，而是把计数减1，直到计数为0，才会删除。这个或者叫硬链接。例图如下： 
另一种方法为符号链接（symbolic linking），或者叫软连接，就是在B中新建一个文件，但这个文件只包含了链接的共享文件的路径名，可以指向共享文件。就类似于Windows的快捷方式， 指向了一个具体目录，删除快捷方式不会删除源文件。
4.3.5 日志结构文件系统
与现有文件系统不太匹配，暂未广泛 使用。
4.3.6日志文件系统
日志文件系统：保存一个用于记录系统下一步需要做什么的日志，这样，如果系统在即将完成任务时崩溃，重新启动后，可以通过查看日志，获取崩溃前计划完成的任务，并重新去完成它，完成后擦除日志项。
4.4 文件系统管理和优化
4.4.1 磁盘空间管理
1.块的大小， 这个通过研究曲线决定，目前最佳为64k, 如下图： 
2.记录空闲块
一种是采用磁盘块链表，链表中每个块包含尽可能多的空闲磁盘块号。 另一种方式是采用位图，n个块的磁盘就用n位的位图，每一位表示一个块，1表示使用，0表示未使用，如下图：
3.磁盘配额
为防止人们贪心占用过多空间，由管理员为每位用户分配最大拥有文件和块的数量。
4.4.2 文件系统备份
为了防止文件系统被破坏，通常需要对文件进行备份。主要是为了解决两个问题：
- 1.从以外的灾难中恢复
- 2.从错误中恢复
同时备份文件不要防在同一个地方，应在不同的地方保存，不过又会增加安保的难度，不过这个不在讨论之列。
为文件做备份费时费空间，因此要选择有意义的目录，如临时文件目录就不用备份了。备份一些特定目录或者重要目录。
其次，对前一次备份没做更改而再去备份也是一种浪费，因此有了增量转储的思想。最简单的增量转储形式就是每周或每月做一次全面备份，而每天只需要对从上一次转储后改变的文件备份即可。不过这个回复起来比较复杂。所以通常用更复杂的增量转储方法。
第三、既然转储文件时海量的，那么需不需要压缩也应该考虑。
第四、记录文件系统的瞬时快照，赋值关键数据结构，其余留待空闲时在备份
第五、非技术性问题，注意备份文件的安保。
物理转储：从磁盘第0块开始，直到最后一块， 全部复制
逻辑转储：从一个或几个指定目录开始，递归的转储给定日期以后更改的文件及目录。
4.4.3 文件系统一致性
一种处理方法就是磁盘块计数表，使用的块和空闲的块， 加起来， 各个位都为1，否则就是一致性出错。 
4.4.4 文件系统性能
1.高速缓存 ： 块告诉缓存逻辑上属于磁盘，但实际上基于性能考虑保存在内存中。告诉缓存块的换入换出，可参考第二章的FIFO算法，LRU算法等页面置换算法。 为了防止计算机系统崩溃导致文件系统破坏，UNIX无限循环没30s调用一次sync，强制将修改过的块立即写到磁盘，这样，就算系统崩溃，丢失数据不会超过30s。
2.块提前读
提前将即将调用的块写入告诉缓存，明显可以提升执行效率。通常使用与顺序读文件。对于随机读文件，先按照顺序提前读入，即使一开始错了也没关系，然后真正通过读入的块的文件关联性，去提前加载下一个块， 从而提升命中率。
3。减少磁盘臂运动
不是有可能顺序访问的块放在一起，最好在一个柱面上，较少磁臂运动时间。
4.4.5磁盘碎片整理
定期整理磁盘，减少碎片。当然， SSD固态硬盘除外，那只会减少SSD寿命。
4.5 文件系统实例
UNIX V7 文件系统
原文地址：https://blog.csdn.net/qq475703980/article/details/82533918
对于大型文件，通常采用前面讲 i节点 时，图4-13使用的方法，就是最后几个地址存放的是另外的块， 快中存放的还是文件块的地址。如果文件很大，可以使用两次间接块甚至三次间接块，如下图： 
例如查找目录 /usr/ast/mbox的过程，如下图，其中.表示当前目录的i节点号， ..表示父目录i节点号：
