os CH11 文件系统实现
CH11 文件系统实现
最重要的是11.4和11.5！（考试）
11.1 File-System(organized) Structure
文件系统的定义如下：
是一种对放在外存内容进行管理的软件结构；当我的用户想要访问一个文件时，需要经历如下的层次结构：
慢慢地固态硬盘和闪存会淘汰磁盘
11.2 File-System Implementation
FCB：存储了一系列的文件性质信息
文件系统实现主要会在讲linux的时候详细展开
11.3 Directory Implementation
目录实现，主要讲如何检索一个文件，这里主要介绍两种实现方法： 1. 线性搜索，就是顺着目录一个一个找
2. hash搜索：
（建立一个hash函数，直接将我的名字经过h(x)计算后映射到表的一个位置，去那个位置查找） 一般外存用线性，内存用hash
11.4 Allocation Methods（文件物理结构，分配方法）
关注的是文件在外存上的存储结构，主要介绍如下的几种：
11.4.1 连续分配
continuous allocation很简单：就是逻辑上连续，物理上也连续
其特点如下：（也很好理解）
对于连续分配的寻址就很简单：
比方说要访问我的文件的第1000个byte，外存的每一块大小为512byte，那么直接1000/512可以确认访问哪个块的哪一个byte
对于连续分配出现文件增长的话，增长的就需要搬到后面去；然后最后把出现的碎片合并一下（碎片处理），如图所示：
作为改进，有一种修正的连续分配方法：
空间不够的时候，新的内容就放在一个被称为扩展的连续空间，会添加到原来的分配中；具体的如下：
11.4.2 链接分配(linked allocation)
外存中一个一个数据块，互相保存下一块的地址，互相指向，如下： 
其优缺点也很明显：增长容易、删除容易；但是不可以随即查找，必须要连续访问，很耗时间。
一个改进如下： 其会将所有的指针统一存放在一起，其分配簇而不是简单的block，如下： 分配簇(Cluster，若干个扇区)比分配块(block，一般是指一个扇区)更节省指针 占用的空间，减少访问时间。如：Windows
相当于，把多个block作为一个单位分配，可以节约指针
重点介绍FAT类文件系统 在接下来的内容里，认为簇（cluster）是最小的分配单位 
对于这样的一张Fill Allocation table，这里在这张表中每一个对应的位置放下一个簇的簇号；比如说这里，第一个是217，那么就在217行放618，表示下一个簇是618；然后在618里面放339，表示下一个簇是339；339为空，说明这就是最后一个。
下面介绍NTFS类文件系统
NTFS的核心结构是MFT（Master File Table）如图所示：
每一个大小为1k，其中存放着这个文件的属性等等关键信息；这个时候，如果这个文件本身很小，那么会索性将这个文件塞进去；但是如果这个文件比较大，那么主要部分放在后面，前面只放索引等信息即可
每个文件或目录至少会有一个MFT
11.4.3 索引分配(indexed allocation)
如图所示，也就是用一个索引
假设一个block是4K，direct block有13个，那么这一块的大小为134K 假设地址大小为4byte，那么一个block可以放1024个索引。因此： 一级的总大小为10244K=4MB 二级总大小为102410244K=4GB 三级为 ……（类似）
11.5 Free-Space Management
这个部分介绍空闲块的管理 现在主流使用Bitmap方法：
也就是说，维护一个表，数量和block数量一样；对于每一个，0表示空闲，1表示占用（注意这里是一个bit，要注意计算）
后面的部分没有仔细讲了；这里结合习题注意一点：
文件名和FCB的关系：应该是通过文件名来找到FCB，之后通过FCB可以检索到文件的存储结构等等的内容