File = disk的抽象
文件组成
- 数据项
- 记录：一组数据项的集合，描述文件的属性
在OS中一般等于Data + Text
FCB
包含data block, size, perm, time等信息
文件目录项：FCB
文件目录：FCB的有序集合
inode
每个文件的inode指向其文件描述信息（元信息）
记录inode编号、文件大小、数据在磁盘中的位置等
与文件一一对应，被存储在磁盘中
在有些系统中，dentry = filename + &inode，又内核维护的一个数据结构，不存储在磁盘，仅缓存在内存中
category
- 磁盘索引结点
- 放在磁盘上，一个文件一个
- 内存索引结点
- 文件被打开后，被复制到内存中，且添加其他信息（看书）
目录项 和 索引节点是n对1关系，因为一个文件可能在文件系统中有多个alias，比如硬链接的实现
磁盘进行格式化时，会分为超级块、索引节点区和数据区
Super Block在挂载文件系统的时候被加载进内存，包含文件系统的详细信息，比如块个数、大小、空闲块等
索引节点区在文件被访问的时候才加载进来
文件操作
OS提供一些系统调用来访问文件
OS维护一个 打开文件表，每次通过open显式地在目录中搜索，找到对应文件并将其属性（包括其在外存上的物理地址）加到表中，然后把其表目的编号（索引，文件标识符，文件句柄）返回给用户，以供用户直接调用该文件
打开文件包含：文件（当前位置）指针，文件打开计数器、磁盘位置，访问权限
文件系统的基本操作单位是数据块，在Linux当中为4KB（8个扇区）
文件的逻辑结构
无结构 (流式，字节为单位)：将数据按顺序组织成记录
有结构
- 顺序文件
- 记录定长，顺序 / 链表形式
- 串结构：按时间排序
- 顺序结构：按关键词排序（可用二分法查，更快）
- 优点：在对记录进行批量操作时效率最高
- 缺点：经常增删改查的情况下不行
- 索引文件
- 索引表：索引号 + 长度 + 文件指针，按关键词排序
- 索引表本身是个定长记录文件
- 索引顺序文件
- 对（顺序存储的）逻辑文件分组，每组的第一个文件的(name, ptr)作为索引表中一个表项
- 查询过程：查关键词所在表，然后从ptr那儿开始顺序（二分）查找
- 可以建立多级查询
- 哈希
文件的物理结构
- 连续分配
- 每一个文件在磁盘上占有一组连续的块
- 目录表：文件name, addr, length
- 优点：存取速度块
- 缺点：顺序表的缺点（插入删除要移动附近的块，长度不宜动态增长，有外碎片）
- 链接分配
- 离散分配磁盘块，块间通过链表方式连接
- 隐式链接
- 每个文件块包含 数据 + 下一块文件的ptr
- 目录表：name, &begin, &end
- 缺点：只适合顺序访问，随机访问慢（访问文件的第i块：从第1个块一个个找），且指针寻址稳定性差
- 解决方案：几块组成一簇，以簇为单位访问（导致内碎片）
- 显式链接
- 把储存在每个块里的nextptr提出来，组成一张(盘块号，nextptr)的 文件分配表(FAT)
- 内存里存在唯一一张FAT
- 每一个盘块号都被记录，nextptr可以设置为特殊值，以标识 无next / 空闲
- 目录项记录文件起始盘块号
- 缺点：FAT太大
- 索引分配
- 改进FAT：每次只调 将要访问的文件 的索引块到内存里
- 优点：可以O(1)访问每一个块，没有外碎片
- 缺点：索引块容易过大
- 改进：混合索引分配
- 混合索引分配
- 根据文件大小不同，文件可选用的储存方式不同
- 优先访问直接块，存储数据块的地址，可以直接找到数据
- 直接块存不下了就访问一级间址：指向一个存有直接指向数据的指针的索引表（间接块），根据每个指针再访问到相应数据块
- 二三级间址同理，每一个i(i>1)级间址指向(i-1)级间址的索引表，最终的一级间址再指向间接块
目录结构
单级 / 两级（略）
树形：可以做到文件分类
无环图：便于实现文件共享
不同路径下单的文件可以指向同一文件，并维护一个引用计数器，删除文件只是减少计数器的值，为0才彻底删除
文件共享
硬链接
A用户创建一文件，目录项的文件指针指向索引结点（包含引用数count），索引结点指向文件；B用户共享文件时也把目录项的文件指针指向该索引结点，然后count++
有用户删这个文件的时候，只是把文件指针删掉，然后count--
软链接（符号链接）
真正的文件就一个，其他文件为Link文件，Link文件只保存路径（在网络文件共享的背景下是文件所在的网络地址+路径名），访问Link文件只是访问路径对应的文件，源文件删了就无法访问
文件系统
提供接口和映射外存
文件系统在磁盘里的结构
提高文件系统性能的方法：FCB分解、目录磁盘碎片整理、块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息优化分布、RAID技术
块高速缓存：在内存里设置一个缓存区，保存磁盘中某些块的副本（和普通cache一个道理）
组织方式：
双向链表表示块，哈希表使用块号进行散列寻址
访问某个块时，把块拿出来移到队尾
置换：换LRU
写入：一致性
日志文件系统（…）
访问磁盘次数问题
一个磁盘块大小 / 一个目录项(FCB)大小 = 一个块能装的FCB个数，以判断一个文件 / 目录需要多少个磁盘块表示
对于非inode形式：在内存里的某文件映像中找到待查找的目录项之后，在磁盘中查找其对应的文件中某个目录项的内容（根据该文件占据的磁盘块数，可能会多次查找），然后读到内存里，迭代
inode：FCB装的有inode号，在内存中通过inode读入该inode对应的FCB，在FCB中检索目标文件的inode号，然后把目标文件的inode读进来