文件系统基础
文件的概念
一个文件有哪些属性？
文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件
标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
类型：指明文件的类型位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见)
大小：指明文件大小
创建时间、上次修改时间文件所有者信息
保护信息：对文件进行保护的访问控制信息
文件的逻辑结构
按文件是否有结构分类，可以分为无结构文件、有结构文件两种。
无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如：Windows操作系统中的.txt文件。
有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。
有结构文件在逻辑上可分为三种：顺序文件、索引文件、索引顺序文件
目录结构
文件控制块
FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项
FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。
最重要，最基本的还是文件名、文件存放的物理地址。
FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取
需要对目录进行哪些操作？
- 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
- 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
- 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
- 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
- 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名)
单级目录结构
早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。
单级目录实现了“按名存取”，但是不允许文件重名。
在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。
显然，单级目录结构不适用于多用户操作系统。
二级目录结构
早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，UserFlie Directory）。
多级目录结构（树形目录结构）
例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”。
在Linux中，“.”表示当前目录，因此如果“照片”是当前目录，则"自拍jpg"的相对路径为：“./2015-08/自拍.jpg”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道"2015-08"目录表的存放位置，从外存调入该目录，即可知道“自拍jpg”存放的位置了。
可见，引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。
用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。例如：自拍.jpg 的绝对路径是“/照片/2015-08/自拍.jpg”。
每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”。
在 Linux 中，“.”表示当前目录，因此如果“照片”是当前目录，则"自拍jpg"的相对路径为:“./2015-08/自拍.jpg”。
树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。
无环图目录结构
索引节点（FCB的改进）
当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。
相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。
文件的物理结构/文件分配方式
操作系统需要对磁盘块进行哪些管理？
- 对非空闲磁盘块的管理 （存放了文件数据的磁盘块）：“文件的物理结构/文件分配方式”要探讨的问题
- 对空闲磁盘块的管理：“文件存储空间管理”要探讨的问题
在内存管理中，进程的逻辑地址空间被分为一个一个页面
同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。
于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
操作系统为文件分配存储空间都是以块为单位的
用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射
连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。
读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
结论：连续分配的文件在顺序读/写时速度最快
结论：物理上采用连续分配的文件不方便拓展。
结论：物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。
连续分配（总结）
连续分配方式要求每个文件在磁盘上占有一组连续的块。
优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快
缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片
链式分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
隐式链接一一除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。
如何实现文件的逻辑块号到物理块号的转变？
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）...
从目录项中找到起始块号，若i>O，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。
结论：采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。
索引分配
如何实现文件的逻辑块号到物理块号的转换？
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）。
从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置。
可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定的存储空间。
①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
链接方案不支持直接访问。
逻辑结构 VS 物理结构
文件存储空间管理
空闲链表法
操作系统保存着链头、链尾指针。
如何分配：若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作
空闲链表法
操作系统保存着链头、链尾指针。
如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高
位示图：每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。
如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。
如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”
适用于离散分配和连续分配的情况。
文件的基本操作
文件共享
文件保护
口令保护
为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。
口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件
优点：保存口令的空间开销不多，验证口令的时间开销也很小。
缺点：正确的“口令”存放在系统内部，不够安全。
加密保护
访问控制
