硬盘的物理结构：若干个磁道和扇区
文件系统：把一段长度可变的连续数据放到磁盘上，而且能通过文件夹/文件的名字实现内容检索
文件系统
如何找到数据在磁盘中的位置？
- 连续存储
- DOS 链式分配：文件以数据块单链表方式存储，文件头包括了第一块和最后一块的指针
-> 无法随机访问；可靠性差（链条断掉一个，后面的数据块就都丢了） - Linux 索引分配：每个文件创建一个 index table ，存着所有指向数据块的指针
index table 大小限制了决定了能索引多少个数据块——引入多级 index table（树状）
-> 可靠性仍然是问题（如果丢掉的是比较高级的 table）
怎么组织文件夹便于检索？
文件夹也是一种文件，记录文件之间的从属关系
内容是列表 <文件名，用户信息，文件长度，……，指向文件的指针（磁道和扇区号）>，树形结构
记录每一项是一个列表，还是一个普通文件
-> 最高级文件夹的磁道和扇区号应该存在哪里？
磁盘的某个固定位置会专门留出一个扇区，存储根文件列表在磁盘中的位置
挂载文件系统时依次加载：卷控制块 -> 目录节点 -> 文件控制块
进程访问文件数据前必须先显式执行“打开”操作，通知操作系统做好读写这个文件的准备（缓存文件的磁道号和扇区号），返回一个 handler
磁盘容量远大于内存容量，所以不可能把所有文件的内存信息都加载到内存里
每个被打开的文件都有一个描述符，记录目录项、打开计数、当前文件指针位置等
内核跟踪进程打开的所有文件，操作系统为每个进程维护一个打开文件表，另外还有一个系统级的打开文件表记录文件的磁盘位置，以免反复在磁盘上查找
一致性问题：文件系统只做建议的一致性保障，而非强制的，也没有保障读写的原子性和正确性
文件系统需要处理的最重要的问题之一是性能差异，因为磁盘和内存、CPU 之间存在巨大的性能代差，因此需要借助内存设计若干种缓存机制，以尽可能减少对磁盘的读写操作。
文件缓存机制
数据块缓存：所有对文件的操作先在 CPU 里缓存，稍后写入磁盘
问题：什么时候写入？——内存不够；要关机了；写了之后很久都没有再写
更多的问题：以多大的数据块缓存？“很久”是多久？
逻辑非常类似于虚拟内存管理中的页面置换
-> 合并成统一的页面缓存 page cache 机制，管理所有面向磁盘的读写操作，包括文件读写和虚拟页置换，都以 4k 为单位对齐，批量提交给操作系统
把文件读写请求都强制对齐成 4k，减少重复的读、合并相邻的写，由于局部性原理，会得到比较好的性能表现
用批量数据搬运弥补设备性能的速度代差
-> 如何设计 cache？
- 以 cacheline 为单位获取数据
- prefetch：用户读取是可预测的吗？
- prefetched data 放在内核空间中，但是不挂载在页表里，如果预测正确就会触发一个 minor page fault，下次预测就将窗口放大一倍；如果错误，步长就恢复到初始长度
- 有点像 计算机网络笔记03：传输层 中的 TCP 拥塞控制算法
数据被写到磁盘上的时候（经过页面缓存->磁盘缓存->磁盘），已经不知道它们的操作顺序了
逐个保障顺序的代价是读写性能被极大地牺牲了 -> barrier enabled I/O stack
性能优化
如何提升读写磁盘的性能？-> 我们唯一能控制的只有磁头的寻道时间
即：假设已经知道了要读取数据的磁道信息，应该如何将其提交给磁盘控制器，从而减少磁头的寻道时间？
磁盘调度算法优化访问请求顺序：
- 最短服务时间优先 SSTF（贪心）：每次都选择最短的移动轨迹 -> 可能会频繁换向
- 扫描算法 SCAN（电梯）：在一个方向上访问所有未完成的请求，走到结尾掉头
- 循环扫描算法 C-SCAN：只沿着一个方向前进，走到结尾跳回开头（类似阅读）
磁头黏着现象 - N 步扫描 N-step-SCAN：将磁盘请求分成长度为 N 的子队列
如何改进文件读写性能？
-> 假设用户 prefer 顺序读写，prefetch
不适配的话 application 就给操作系统发 advice，通常是关闭原本的 prefetcher，交给程序员主动完成读写操作
一些特殊问题
磁盘空间管理与容错
希望按照扇区大小管理磁盘每块数据的读写
矛盾：对硬盘的连续数据读写，一次读写的块越大，单个 bit 的均摊成本就越少，性能越高；但是每次操作的数据块越小，真正用到的数据占比（数据利用率）就越大
-> 现在的趋势是抛弃空间利用，更大程度发挥磁盘的性能，因为硬盘变得便宜了，但运行速率没有什么提升
类似物理内存空间，用表记录扇区的分配情况
问题：如果不小心写错了，和内存不一样，重启也无法抹去错误
文件一致性检查：用两张表 blocks in use 和 free blocks 分别表示，正常情况下二者完全互补
检测结果不一致时，操作系统也不知道哪个是对的，只能靠把前后的数据和其他文件的信息串联在一起，然后猜测着修复
共享文件管理
文件系统中用链接实现共享时，系统目录树结构会发生变化，变成有向无环图
共享文件的回收：
硬链接：在文件表头上增加一个 counter，记录它在几个文件夹下，为零时才把文件删掉
但是如果在某个文件夹下删除文件时 counter 忘了-1，最后就会出现固定的磁盘空间浪费（在所有文件夹下都找不到这个文件，但磁盘又无法回收它）
-> 快捷方式/符号链接 (linux)：文件浅拷贝
即，只得到了这个文件的指针；如果文件本身被回收了，指针就失效了
文件夹的快捷方式：如果子文件夹里有 parent 文件夹的快捷方式，就会造成文件目录循环
-> 如何保证没有循环？
只允许到文件的链接，不允许到文件夹的链接；循环检测算法
多文件系统兼容
文件系统的持久性带来数据用户的粘度，导致各个操作系统存在相似却不兼容的接口，用户之间的数据交互受到了阻碍
-> Linux 系统设计者为文件系统定义了统一的抽象接口 POSIX，定义了所有文件的 open/close/read/write 等操作，而且提供统一的缓存管理
所有文件系统都需要通过这套接口进行文件操作
文件系统挂载：可以把一个存储设备上文件树的 root 挂载在另一个文件系统的某个文件夹下面