操作系统总结之文件系统实现

文件系统永远在外存中，存储大量数据。
文件能够原地改写，即能够读出一块，并修改，再写回。
外存和内存的传输的最小单位为block。
磁盘是随机存储器。
文件系统设计也是分层设计思想。从最底层开始讲起。
（1）I/O控制层，包括设备驱动程序（翻译高层命令控制硬件控制器）+中断处理程序。
（2）基本文件系统：发送高层命令给设备驱动程序用以对磁盘进行读写。
（3）文件组织模块：从逻辑块-->物理块，给基本文件系统使用。
（4）逻辑文件系统：管理元数据。元数据就是一些文件属性+文件名。
分层设计在计算机网络里也有提到，TCP/IP协议等。好处当然是能够清晰的划分各自的功能。
linux文件系统：ext3，4.
windows文件系统：FAT,NTFS.
一个文件系统包括：
（1）引导控制块（boot control block）是一个卷的第一块，如果该卷没有操作系统，则为空。
（2）卷控制块：卷的详细信息包括有多少块可以用、块大小等。
（3）目录：文件名+FCB(inode 索引节点)。
FCB在另一篇博客中已经讲到，包括一些文件的属性但是不包括文件名。
FCB==inode==Master File Table
内存中有一些信息是在文件系统被mount的时候加载进去的，比如目录，整个系统的打开文件表、单个进程的打开文件表。
文件系统被mount时可能就已经把所有FCB都分配好了，存在pool中。
UNIX中目录和文件是一起处理的，windows中目录和文件有不同的系统调用。
比如open一个新的文件，则创建一个FCB，在单个进程打开文件表，系统打开文件表等中适当加入记录，并返回一个句柄。
UNIX中称为文件描述符，windows中称为文件句柄。

一个磁盘能有多个分区，如果一个分区没有文件系统，则称为生的。
引导区如果有多个操作系统和多个文件系统，则通过启动加载器能够定位一个操作系统。
根分区包括操作系统和系统文件，在引导时导入内存。
当装入文件系统时，可以自动或手动装入。当装入文件系统时，操作系统需要判定是否有效，如果有效，则在装入表中填入文件系统的类型。

为了在不同文件系统中无缝移动，引入了VFS。
（1）VFS把文件系统的接口和具体实现分开。
（2）在NFS中，也要有一个唯一标识远程文件的标识符，因此vnode类似inode，保存远程文件属性。
因此通过vnode还是inode能区分本地和远程文件，再是通过特定文件类型来区分文件，因此我们可以正确的调用特定的操作。
VFS定义的4个主要对象类型：
（1）inode object。单独的文件。
（2）file object。打开的文件。
（3）superblock object。整个文件系统。
（4）dentry object。单独的目录条目。
对于每个对象类型都有一系列的操作。

目录实现有很多种，
（1）线性列表。
存储文件名和指向FCB的线性链表。
可以使用软件缓存来存储最近使用过的目录。
（2）哈希表。
给定一个文件名，通过哈希函数，快速找到指定目录。
缺点：哈希函数及哈希值都是预先给定，不能灵活变换。
解决方案：动态哈希即可扩展哈希、线性哈希等。或者使用溢出桶。

文件分配空间方法：
一、连续分配。
每个文件都是连续分配。分配时遵循首次适应方法。
目录是由（文件名，开始位置，长度）组成。
优点：直接访问。
缺点：
（1）外部碎片。
（2）确定文件大小。
解决方法：
（1）对于外部碎片，重新打包即把所有文件系统都复制到磁带上，清空整个磁盘，并重新分配连续空间。
（2）对于无法确定文件大小，则重新分配孔，但是费时；或者使用扩展连续空间。那么目录就是（文件名，开始位置，块数，第二个开始位置）组成。
二、链接分配。
目录为（文件名，文件起始指针，文件结尾指针）组成。
文件由链表组成。
优点：分配时只要有空闲块即可。没有外部碎片。
缺点：
（1）顺序访问而不能随机访问。
（2）指针需要空间。
（3）内部碎片。
（4）可靠性问题。因为由指针链接，只要有一个指针丢失，则文件就崩溃。
解决方法：
对于指针占用空间问题，需要利用更少的指针，则引入了cluster（簇），即一个簇由多个块组成。但是会加剧内部碎片问题。
对于可靠性，我们可以用FAT（文件分配表），目录为（文件名，开始块）组成。先在FAT找到指定块，再指向块的具体位置。
采用FAT会导致磁头寻道时间过长。
三、索引分配。
把所有索引放在一起，可以支持直接访问。
但是索引可能会在一个块不够存放，因此有了几种方法：
（1）链接方案：通过将索引块链接起来。
（2）多层索引。
（3）组合方案。例如Unix中的inode，在inode中有15个指针存在文件中，头12个指针为直接块。其他三个为间接索引块。第一个为一级间接块。依次类推，第三个为三级间接块。
如果文件不大，则可以直接访问。

对于空闲空间，我们也需要维护一个空闲空间链表。下面介绍几种方法实现。
（1）位向量。
通过已分配的块记为0，未分配的块记为1，则只需要简单的位运算就能得出第一个空闲块或者连续空闲块大小等结论。
缺点：所占空间太大。
（2）链表。
空闲空间通过链表连起来，第一个空闲块的地址缓存在内存中。
缺点：效率不高。
（3）组。
将n个空闲块的地址存在第一个空闲块中。
（4）计数。
空闲空间表中每个条目记录（起始，长度）的记录。