//sunny forever
while(life<end){
love++;
beAwesome :)}

1. 输入输出系统
2. 文件管理
3. 磁盘存储器管理
4. 文件系统实例
1. 4.1. Windows的文件系统
2. 4.2. Linux文件系统
  1. 4.2.1. ext4
  2. 4.2.2. 文件组织

操作系统(下)

字数：45986 写于：2020-08-10

最新更新：2020-08-10 阅读本文预计花费您132分钟

输入输出系统

I/O系统管理的主要对象是I/O设备及其设备控制器，其主要责任是管理这些设备，并为上层应用程序提供统一、可靠的访问方式

I/O系统的层次结构

I/O系统既与硬件密切联系，又与上层文件系统、用户直接交互，设计复杂，因此现代I/O系统普遍采用层次式结构，每一层利用下层提供的服务，负责实现某些子功能，并且屏蔽实现细节，向高层提供服务。

用户层I/O软件：位于最顶层的用户层，负责与用户直接交互，核心功能是实现与用户交互的接口，提供与I/O操作相关的库函数，并将用户请求翻译成格式化的I/O请求，通过系统调用请求操作系统内核服务，如：C语言中，向用户提供printf()库函数，会被翻译成write系统调用
设备独立性软件（设备无关软件）：位于内核层，负责实现用户程序和设备驱动器之间的统一接口，使I/O软件能独立于物理设备，以适配多类型的设备而不需要对I/O软件进行修改，其核心功能包括：向上层（用户层）提供统一的调用接口（如read、write系统调用）；提供权限访问控制和设备的保护；进行差错处理；设备的分配与回收；管理数据缓冲区；建立逻辑设备名到物理设备名的映射关系
设备驱动程序：位于内核层，主要负责对硬件设备的具体控制，将上层发出的一系列命令(如read/write)转化成设备能识别的操作(这些设备由不同厂商生产，有不同的指令和技术实现)，包括设置设备寄存器，检查设备状态等
中断处理程序：位于内核层最底部，负责处理I/O设备发来的中断请求信号，包括保存CPU上下文环境、转入执行中断处理程序、恢复CPU环境等
硬件：包含机械部件（I/O设备本身）及其电子部件（I/O设备控制器）
其中属于OS内核部分的设备独立性软件、设备驱动程序、中断处理程序统称为I/O核心子系统，负责I/O调度、设备保护、设备分配与回收、缓冲区管理等功能

下文按：硬件(I/O设备与I/O控制器)-中断处理程序-设备驱动-设备独立性软件-用户层软件顺序依次整理，其中中断处理程序参考《计算机组成原理》笔记

I/O设备与I/O控制器

I/O设备通常由执行I/O操作的机械部分和执行控制的电子部件组成，执行I/O操作的机械部分就是I/O设备，执行控制的电子部件则称为I/O控制器或适配卡(adapter)

I/O设备的分类

按照信息交换单位分为：
- 字符设备：又称为流设备，数据的存储和传输以字符为单位，传输速率较低，不可寻址，数据传输方式通常使用中断方式，典型设备有键盘、打印机等
- 块设备：数据的存取和传输以数据块(常见逻辑块大小为512 Bytes 或 4 KiB)为单位，因此即便进程只需要读取1Byte数据，CPU或DMA设备也会读取一整块数据到内存，再在内存中进行字节级读/写操作，写回时也将写入整个数据块。块设备的优点是传输速率高，可寻址，数据传输通常靠DMA方式，典型的块设备包括机械硬盘、固态硬盘、U盘和存储卡等
按照使用特性分为：
- 存储设备：即硬盘、U盘等
- 人机交互I/O设备：鼠标、键盘、屏幕等设备
- 网络通信设备：如调制解调器
按照传输速率分为：
- 低速设备：传输速率为每秒几字节至几百字节，如：鼠标、键盘
- 中速设备：传输速率为每秒几千至数十万字节，如：打印机等
- 高速设备：传输速率为每秒数十万至千兆字节，如：磁盘、光盘机
按设备的共享属性分：
- 独占设备：进程互斥访问
- 共享设备：一段时间内允许多个进程同时访问
- 虚拟设备：通过虚拟技术将一台独占设备变换为若干台逻辑设备，供多个用户（进程）同时使用

I/O控制器

I/O控制器又称为设备控制器或适配卡(adapter)，通常做成印刷电路卡形式，它是一个可编址的设备，控制多个设备时会有多个地址。工作时，I/O设备并不直接与CPU通信，而是与I/O控制器通信，即CPU控制I/O控制器，I/O控制器控制I/O设备

I/O控制器的功能

接收和识别CPU发出的命令：控制器中有相应的控制寄存器，用来存放接收的命令和参数，并对接收的命令进行译码
数据交换：控制器中有相应的数据寄存器，用于实现CPU与I/O控制器之间、I/O控制器与设备之间的数据交换，包括通过数据总线发送/接收数据
标识和报告设备状态：设置有状态寄存器，用于向CPU反映设备状态
地址识别：系统中的每个设备都有一个地址，设备控制器需要能够识别每个设备的地址；此外，为了使CPU能向I/O控制器中的寄存器读/写数据，这些寄存器也需要有唯一地址，因此I/O控制器需要配置地址译码器
数据缓冲区：内存的效率较高，I/O设备速率较低，因此I/O控制器中的缓冲区用于解决二者速度不匹配的问题
差错控制：用于检错I/O设备传送来的数据，并向CPU报告

I/O控制器的组成

I/O控制器既要与CPU通信，又要与设备通信，因此大部分I/O控制器由三部分组成：

设备控制器与CPU之间的接口：用于与CPU通信，该接口有三类信号线：数据线、地址线、控制线，其中数据线通常接入控制器中的数据寄存器(暂存数据)、控制/状态寄存器(存放CPU送来的控制信息或设备状态信息)
设备控制器与设备之间的接口：控制器有一个或多个设备接口，用于连接一个或多个设备，每个接口三种类型的信号：数据信号、控制信号、状态信号
I/O逻辑：通过控制线与CPU相连，负责接收和识别CPU的各种控制信号(控制信号可以暂存于控制寄存器内)，并对设备发出命令；同时根据CPU发来的地址信号选择I/O设备接口，因此还拥有地址译码功能

内存映像I/O

一个I/O控制器可能会连接多个I/O设备，并且拥有对应数量的数据寄存器、控制寄存器、状态寄存器。为了实现CPU与I/O控制器的通信(主要方式为CPU对这些寄存器的读写)，有以下两种方案：

内存映像I/O：内存单元地址和设备控制器寄存器地址联合编址，CPU可以像访问内存一样访问这些寄存器，该方式的优点是不需要专门的I/O访问指令，统一了对内存和对控制器的访问方法，简化了I/O编程
特定I/O指令：该方式用于早期计算机，包括一些大型计算机，该方式会为每个控制器寄存器分配一个I/O端口(即寄存器独立编址)，I/O端口通常是一个8位或16位的整数，CPU通过特定I/O指令访问这些端口，该方式的主要特点为内存地址空间与I/O端口空间相互独立，缺点是访问内存和访问设备需要使用两种不同的指令

设备驱动程序

不同设备内部的硬件特性不同，需要由驱动程序将上层（与设备无关的I/O软件）发出的的抽象命令（如read或write），转换为设备相关的低层操作序列

设备驱动程序的核心功能

将上层（与设备无关的I/O软件）发出的的抽象命令（如read或write），转换为设备相关的低层操作序列
检查I/O请求是否合法，了解设备当前状态（忙/闲）。若设备空闲则立即启动，若忙碌则将请求挂入设备等待队列
及时响应设备控制器发来的中断请求，并根据中断类型调用相应的中断处理程序

设备驱动程序的特点

与硬件紧密相关：驱动程序直接和设备控制器及硬件特性打交道，不同类型的设备需要不同的驱动程序
可重入性：驱动程序允许被多个进程重复调用，因此代码必须是可重入（Reentrant）的，并保证并发安全
部分固化：由于与硬件紧密相关，驱动程序的底层部分有时会用汇编语言编写，驱动程序的基本部分固化在设备的ROM中

驱动程序的执行流程

将抽象要求转为具体要求：将高层的read、write等命令，翻译成对设备控制器中具体寄存器的操作命令和数据格式
对服务请求进行校验：检查本次I/O请求的合法性，确保设备能执行该操作
检查设备状态：启动设备前，需要检查状态寄存器的值，确认设备处于就绪（空闲）状态才能启动，否则需要等待
传送必要参数：将数据传输的内存地址、数据长度等参数，设置到设备控制器的指定寄存器中，并配置通信接口的波特率、奇偶校验方式、停止位数目等参数
启动I/O设备：向设备控制器的命令寄存器发送启动命令，正式开始I/O操作

对I/O设备的控制方式

驱动程序与设备所采用的I/O控制方式紧密相关，I/O设备控制方式的演进，这直接影响了驱动程序的复杂度，常用的控制方式是中断方式和DMA方式

程序直接控制方式

该方式又称为程序查询方式或轮询的可编程I/O方式，其核心思想是：CPU向设备控制器发出I/O命令后，不断轮询设备状态寄存器，检查设备是否就绪或I/O是否完成，直到设备就绪后才进行数据传送。以读取数据为例，其工作流程为：

CPU向I/O控制器发出I/O指令，启动设备输入数据，并把I/O控制器中状态寄存器中的busy(忙/闲标志)位置为1
CPU反复轮询busy标志位，若为 1 ，表示I/O设备尚未输入完一个字/一个字符，CPU需要继续轮询；若为 0 ，表示I/O设备已经将数据送入I/O控制器的数据寄存器中
CPU从I/O控制器的数据寄存器读取数据，将其送入内存单元
完成一个字(或字符)的I/O，继续启动读取下一个数据

程序直接控制方式总结：

数据传送单位：一个字或一个字符
数据流向：对于读操作(写操作反之)，数据流向为I/O设备→I/O控制器数据寄存器→CPU数据寄存器→内存单元
优点：实现简单，不需要额外硬件支持
缺点：CPU和I/O设备只能串行工作；在整个查询期间和数据传输期间，CPU都无法继续执行原程序，在查询阶段，CPU “原地踏步”；CPU利用率极低，无法及时响应紧急事件。
应用领域：早期计算机系统或简单、慢速设备；以及极低速或简单的嵌入式系统中，例如单片机读取按键状态、检测传感器数据、驱动简单LCD等场景，由于数据量很小且系统结构简单，使用DMA或中断反而会增加设计复杂度

中断方式

程序中断方式下CPU在启动I/O设备后，不再反复查询和等待设备是否准备就绪，而是继续执行自身程序。当I/O设备准备就绪时，会主动向CPU发出中断请求，CPU响应后，暂停现行程序，转入中断服务程序，从I/O接口存取数据，待数据处理完成后，再返回到原程序的断点处继续执行。大致执行流程为：

CPU发出I/O命令并启动设备，随后转去执行其他进程
I/O设备控制器传输完一个数据单位后发出中断请求
CPU响应中断，保护现场，并执行中断处理程序，完成数据传送
CPU恢复现场，继续执行原程序

中断方式下，CPU只需要花费极短时间处理中断，例如：假设终端平均每100 ms产生一个字符，其中绝大部分时间用于等待用户输入，而将字符从I/O控制器数据寄存器读入CPU寄存器再送入内存单元I/O缓冲区的时间小于0.1ms，采用程序查询方式时，CPU约有99.9 ms处于忙等；采用中断方式时，CPU可利用这段时间执行其他任务，仅用约0.1 ms处理中断，成百倍地提高CPU利用率。

中断方式总结

数据传送单位：一个字或一个字符
数据流向：对于读操作(写操作反之)，数据流向为I/O设备→I/O控制器数据寄存器→CPU数据寄存器→内存单元，其中数据在CPU寄存器停留时间仅为CPU执行指令时的流经时间
优点：CPU与设备可以并行工作，不会出现“原地踏步”现象，CPU利用率明显提高，且能及时响应设备请求
缺点：每完成一个数据单位就要中断一次，中断频繁；CPU仍需介入数据传送，中断处理开销大
应用领域：慢速、中速字符设备或小批量数据传输，如键盘、鼠标等

DMA方式

DMA(Direct Memory Access，直接内存访问)增设DMA控制器，使数据能够直接在内存和设备之间传送，不需要CPU逐字干预。CPU只需要在开始前设置DMA参数，传送完成后由DMA控制器发出一次中断

DMA方式总结

数据传送单位：一个连续的数据块
数据流向：I/O设备→I/O控制器数据寄存器/DMA控制器数据寄存器→内存单元
优点：数据传输以块为单位，CPU接入频率进一步降低，CPU只在开始和结束时干预，数据传送过程中CPU可以做其他工作
缺点：需要专门的DMA硬件支持，且CPU需要读/写多个数据块时，依旧需要多次中断处理
应用领域：适用于大批数据的传送，如硬盘存取、网卡等

DMA知识点详见《计算机组成原理上》笔记

通道控制方式

通道是一种专门负责I/O控制的处理器，具有独立的通道指令系统，能执行存放在内存中的通道程序，控制多台设备进行I/O操作。CPU只需发出启动通道的I/O指令，之后由通道独立完成I/O控制，其工作流程为：

CPU根据I/O请求组织通道程序并放入内存；
CPU发出启动通道的I/O指令；
通道独立执行通道程序，控制设备完成I/O；
道完成或出错时向CPU发出中断；
CPU响应中断，进行善后处理。

方式总结

数据传送单位：一组数据块
数据流向：I/O设备→内存
优点：CPU、通道、I/O设备可以并行工作，资源利用率很高
缺点：实现复杂，需要专门的硬件通道支持
应用领域：中型机、大型机等

设备无关性I/O软件

设备无关性I/O软件又称设备独立性软件，位于用户层软件和设备驱动程序之间，主要目标是使应用程序独立于具体使用的物理设备，从而提高系统的可适应性和可扩展性，用户程序可以通过逻辑设备名（如/dev/printer）来请求I/O操作

设备无关软件的主要功能

统一接口与设备保护：使所有设备驱动程序与OS之间有统一接口，方便添加新的设备驱动程序；同时，用户访问设备时需要通过这些接口，可以防止用户直接访问设备，禁止无权用户使用设备，起到设备保护的作用
缓冲管理：缓和CPU与I/O设备之间的速度矛盾，为字符设备、块设备等各类设备配置不同的缓冲区
差错控制：由于I/O设备通常包含机械和电气部分，因此故障率远高于主机，因此错误处理原则是尽可能在低层（驱动程序）解决错误，高层只处理底层无法解决的错误，错误主要分为两类：
- 暂时性错误：由瞬时事件（如电源波动、网络数据包丢失）引起，可通过重试操作纠正
- 持久性错误：由硬件故障（如：磁盘有坏扇区）等引起，驱动程序无法解决时，由设备无关软件向系统报告错误信息
设备分配与回收：设备无关软件负责维护设备控制表等数据结构，负责设备分配与回收。对于独占设备，系统需统一分配。进程使用前需提出申请，设备空闲则分配，否则进程被阻塞并加入等待队列，待设备释放后被唤醒。对于共享设备，则由系统统一管理，支持多个进程交替使用
屏蔽设备差异，提供统一数据块：不同类型的设备数据交换单位不同，读写速度不同，设备无关软件负责隐藏这些差异，向高层软件提供大小统一的逻辑数据块

I/O系统接口

I/O系统接口位于设备独立性软件与用户层软件之间，根据设备类型的不同，分为以下接口：

流设备接口(字符设备接口)：流设备中数据的存储和传输以字符为单位，传输速率较低(每秒几千字节以下)，不可寻址，因此只能通过get/put系统调用按顺序从字符缓冲区存/取一个字符(数据部分)，通过in-control指令(如：Linux中的ioctl系统调用)来向设备发出控制请求(控制部分)，通常采用中断驱动方式，常见设备有鼠标、键盘等
块设备接口：块设备中数据的存储和传输以数据块为单位，传输速率较高，可寻址，即允许指定数据输入源地址和输出目标地址，可随机读写，因此可以使用read/write系统调用向读写指针所指位置写入数据，通过seek系统调用修改读写指针位置。块设备通常采用DMA方式，常见设备为磁盘
网络设备接口：又称为网络套接字(socket)接口，用于网络通信，可以使用socket系统调用创建一个网络套接字，并指明网络协议(如：TCP/UDP)，使用bind将套接字绑定到某个本地端口，使用connect将套接字连接到远程地址，使用read/write从套接字读/写数据

根据是否阻塞进程又分为：

阻塞I/O：应用程序发出I/O系统调用后，进程需转为阻塞态等待。eg:从键盘读一个字符get时，只要用户键盘输入未完成，进程就需要阻塞等待
非阻塞I/O：应用程序发出I/0系统调用，系统调用可迅速返回，进程无需阻塞等待。eg:用户进程向磁盘写数据执行write时，数据会从用户进程空间写入到内核缓冲区中，即便此时磁盘忙碌无法写入，用户进程提交写入请求后也可以返回，写入操作由内核后续执行，不会阻塞用户进程继续执行。

设备分配需要考虑的因素

系统分配设备时，需要考虑以下因素：

设备属性：
- 独占设备：一个时段只能分配给一个进程(如打印机)
- 共享设备：可同时分配给多个进程使用(如磁盘)，各进程往往是宏观上同时共享使用设备，微观上交替使用
- 虚拟设备：采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使(如采用SPOOLing技术实现的共享打印机)
设备分配算法：包括先来先服务、优先级高者优先、短任务优先等算法(参考进程调度算法思想)
设备分配方式：
- 安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒，可以避免死锁
- 不安全分配方式：进程发出I/O请求后，系统为其分配/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞

设备分配中的数据结构

设备控制表DCT

设备控制表DCT(Device Control Table)用于记录设备情况，系统会为每个设备配置一张DCT，包含以下字段：

设备类型：如:打印机/扫描仪/键盘
设备标识符：即物理设备名，系统中的每个设备的物理设备名唯一
设备状态：处于忙碌/空闲/故障
指向控制器表的指针：指向该设备所连接的控制器的控制表
重复执行次数：当设备工作错误时，通常会尝试重新执行，只有达到最大重复执行次数仍未成功时，才判定执行失败
设备队列的队首指针：指向正在等待使用该设备的进程队列(由进程PCB组成队列)

控制器控制表COCT

控制器控制表COCT(Controller Control Table)：系统为每一个控制器都设置了用于记录控制器情况的控制，包含以下字段：

控制器标识符
控制器状态：忙/空闲
与控制器相连接的通道表指针
控制器队列的队首指针
控制器队列的队尾指针

通道控制表CHCT

通道控制表CHCT(Channel Control Table)：每个通道都有一张通道控制表，包含以下字段：

通道标识符
通道状态：忙/空闲
与通道连接的控制器表首址
通道队列的队首指针
通道队列的队尾指针

系统设备表SDT

系统设备表SDT(System Device Table)：这是系统范围的数据结构，记录了系统中全部设备的情况，每
个设备占一个表目，其中包括有设备类型、设备标识符、设备控制表DCT及设备驱动程序的入口等项

逻辑设备表LUT

早期操作系统中，应用程序直接使用物理设备名，这导致程序与特定硬件强绑定，为解决此问题，I/O系统引入了逻辑设备名，应用程序在请求使用I/O设备时，只需要使用逻辑设备名，并通过逻辑设备表将逻辑设备名映射为物理设备名，方便系统硬件识别

逻辑设备表(Logical Unit Table)的表目包含三项：逻辑设备名、物理设备名、设备驱动程序的入口地址。当进程用逻辑设备名请求分配I/O设备时，系统根据当时的具体情况，为它分配一台相应的物理设备，并在逻辑设备表上建立一个表目，填上应用程序中使用的逻辑设备名和系统分配的物理设备名，以及该设备驱动程序的入口地址。当以后进程再利用该逻辑设备名请求I/O操作时，系统通过查找LUT，便可找到该逻辑设备所对应的物理设备和该设备的驱动程序。

逻辑设备名	物理设备名	驱动程序入口地址
/dev/tty	3	1024
/dev/printer	5	2046
……	……	……

逻辑设备表的设置方式

整个系统只设置一张LUT：该方式不允许LUT中有相同的逻辑设备名，通常用于单用户系统中
为每个用户设置一张LUT：当用户登录时，就为该用户建立一个进程，同时建立一张LUT，并将该表放入进程的PCB中

独占设备的分配流程

根据进程请求的逻辑设备名查找系统设备表SDT(用户编程时提供的逻辑设备名实际是“设备类型”)
根据SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程，并在逻辑设备表(LUT)中新增一个表项
找到所分配设备的设备控制表DCT，查找找到控制器控制表COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
根据COCT找到通道控制表CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程

用户层I/O软件

用户层I/O软件位于I/O软件体系结构中的最高层，它直接面向用户和应用程序，其核心工作可概括为两点：

提供库函数供开发者调用
应用SPOOLing技术将独占设备虚拟为共享设备

系统调用与库函数

用户层软件的主要职责之一就是为用户程序提供操作设备的途径，包括:

库函数：操作系统在用户层提供了一系列与I/O操作相关的库函数（如C语言的printf、scanf），作为应用程序编程接口（API）。开发者通过调用这些熟悉的库函数，而非复杂的内核服务，来便捷地请求I/O操作
系统调用：当应用程序需要执行某种I/O操作时，可以使用相应的系统调用。当OS捕获到应用程序中的该系统调用后，便将CPU的状态从用户态转换到核心态，然后转向操作系统中相应过程，由该过程完成所需的IO操作。执行完成后，系统又将CPU状态从核心态转换到用户态，返回到应用程序继续执行

假脱机(SPOOLing)技术

SPOOLing技术 (Simultaneous Peripheral Operation On-Line)又称为假脱机技术，它一种通过软件的方式，将独占设备（如打印机）改造为可供多个用户同时使用的共享设备，实现设备虚拟化的技术。

假脱机技术来源于20世纪50年代，为缓和CPU与低速I/O设备间的矛盾，工程师们引入了脱机输入、脱机输出技术，即用一台独立的外围控制机，预先将低速设备的数据读入高速磁盘（磁带），供CPU使用；或将CPU输出的数据先暂存磁盘，再由外围机输出，从而让CPU解脱。

后来，操作系统引入多道程序技术后，工程师不再使用专门的物理外围机，而是直接用两道常驻内存的程序来模拟它的功能：一道负责把低速设备数据送入磁盘（模拟输入），另一道负责把磁盘数据送出到设备（模拟输出），这样外围操作和CPU对数据的处理可以同时进行。这种在联机情况下，可以同时进行外围操作的技术即为假脱机技术

SPOOLing系统的组成

一个典型的SPOOLing系统由以下部分构成：

输入井和输出井：在磁盘上开辟的两个大存储空间：输入井用于暂存从低速输入设备输入的数据，输出井用于暂存用户进程的输出数据。输入/输出井中的数据一般以文件形式管理，这些文件称为井文件，一个文件仅存放一个进程的输入(或输出)数据，所有进程的输入(或输出)文件链接为一个输入(或输出)队列
输入缓冲区和输出缓冲区：在内存中开辟的缓冲区。用于缓和CPU与磁盘之间、磁盘与低速I/O设备之间的速度不匹配问题。数据从设备到磁盘（或反之），都会先经过内存缓冲区中转
输入进程和输出进程：常驻内存的进程。输入进程（SPi）模拟脱机输入时的外围控制机，负责将低速设备的数据送入输入井；输出进程（SPo）模拟脱机输出时的外围控制机，负责将输出井的数据送到低速设备
井管理程序：负责控制作业与磁盘井之间的信息交换，如在输入井/输出井中分配和释放存储空间

SPOOLing系统的工作过程

以打印为例，打印机属于独占设备，利用假脱机技术可以将其改造为一台可供多个用户共享的打印设备，提高设备利用率，假脱机打印机系统工作流程为：

申请存储：当用户进程请求打印时，SPOOLing系统并非直接分配打印机，而是由输出进程在磁盘的输出井中为其申请一块空闲存储区。
数据转移：将用户进程中要打印的数据，从进程缓冲区传送到刚刚申请到的输出井存储区中。对用户进程而言，这一步就相当于“打印完成”了，进程可以继续执行，无需等待真实的打印。
排队等待：输出进程为用户进程生成一张I/O请求表（打印请求表），填入打印要求，并将该表挂到请求打印队列上。
实际输出：当打印机空闲时，输出进程从请求打印队列中取出请求表，根据表的信息，从输出井中取出相应数据，送到内存输出缓冲区，最终交由打印机进行实际打

SPOOLing技术的优点

提高了I/O速度：用户进程对低速设备的操作，变成了对高速磁盘（输入/输出井）的操作，有效缓和了CPU与低速I/O设备的速度矛盾。
将独占设备改造为共享设备：系统并没有将物理打印机直接分配给任何进程，而是在输出井中为每个进程分配空间。这样，一台物理打印机就变成了可供多个进程“同时”使用的逻辑设备。
实现了虚拟设备功能：对于每个用户进程而言，它都感觉自己独占了一台打印机，而实际上它使用的是由SPOOLing技术虚拟出的逻辑设备

守护进程daemon

在利用假脱机系统实现打印机共享的方案中，可以取消原有的假脱机管理进程，改为为打印机建立一个守护进程，由守护进程执行原来假脱机管理进程的一部分功能。如：守护进程负责在磁盘缓冲区中为用户申请空闲盘块，将待打印数据送入其中，并将该盘块的首址返回给请求进程。其余部分则由请求进程自己完成：每个需要打印的进程需要生成一份打印请求文件，其中包含打印要求以及指向打印输出数据所在盘块的指针等信息，然后将该请求文件放入假脱机文件队列（目录）中。

守护进程是唯一允许直接使用打印机的进程。当有进程提出打印请求时，只需将请求文件放入假脱机文件队列中；如果守护进程正在睡眠，则将其唤醒。守护进程随后按照队列中的顺序，依次读取请求文件，根据其中的说明完成打印；打印完成后继续处理下一个请求，直到队列中的请求全部处理完毕，再次进入睡眠，等待新的打印请求。

这种方式的核心思想是：由守护进程统一管理独占设备，其他进程不能直接使用设备，只能将使用请求写入假脱机队列，由守护进程依次完成，从而将原本的独占设备改造为可供多个进程共享的设备。除了打印机守护进程外，还存在服务器守护进程、网络守护进程等其他类型的守护进程。

IOBuffering/缓冲区管理

现代操作系统中，I/O设备和处理机交换数据时几乎都会使用缓冲区。缓冲区是一个存储区域，可由专用的硬件寄存器组成(如：快表，成本高，容量小)，一般情况下更多的是利用内存作为缓冲区，下文主要介绍由内存组成的缓冲区的管理。

缓冲区的作用

缓和CPU与I/O设备速度不匹配的矛盾
减少对CPU的中断频率：当数据积累到一定量时才向CPU发起一次中断，从而减少中断次数，放宽对CPU中断响应时间的限制
解决数据粒度不匹配的问题：例如，I/O设备可能以字节流或块（为单位产生数据，而CPU和进程则处理不同大小的数据单元，缓冲区可以起到“适配器”的作用
提高CPU和I/O设备之间的并行性：CPU在计算的同时，I/O设备可以独立地向缓冲区填充或取出数据，实现并行操作

单缓冲区

单缓冲区（Single Buffer）指操作系统在内存中为I/O请求分配的一个缓冲区。以块输入为例，单缓冲区的工作方式为：数据先从I/O设备输入到系统缓冲区，再从系统缓冲区传送到用户工作区，最后由CPU读取处理用户工作区中的数据。注意：当缓冲区非空时，不能写入数据，只能读出；当缓冲区为空时，可以写入数据，但必须把缓冲区写满以后，才能传出数据(教材上的单缓冲区模型，I/O读写以一块或一行为数据单位进行缓冲，缓冲区大小也对应为一块或一行，为保证数据边界因此才有“缓冲区非完全空，不能写入”这一概念)。

以块设备输入为例，假设从I/O设备(如磁盘)传输一块数据到缓冲区的时间为T，OS将数据从缓冲区送到用户区的时间为M，CPU处理运算这块数据的时间为C，由于T和C是可以并行的，因此

当 T > C 时，系统处理数据的时间为 T+M
当 T < C 时，系统处理数据的时间为 C+M
即系统处理一个数据块的时间为 Max(C,T)+M

对于字符设备，输入时缓冲区用于暂存用户输入的一行数据，且输入期间用户进程挂起以等待数据输入完毕；输出时，用户进程将一行数据写入缓冲区后可以继续运行，当用户进程已有第二行数据输出，但第一行数据尚未提取完毕时，用户进程应阻塞。

双机通信时，如果使用单缓冲区，任一时刻只能实现单方向的数据传输。

双缓冲区

双缓冲（Double Buffer）又称为缓冲对换（Buffer Swapping），指引入两个缓冲区，一个缓冲区用于I/O设备输入/输出数据时，另一个用于CPU处理数据，两者交替使用。

同样以块设备输入为例：I/O设备传输数据到缓冲区的时间为T，OS将数据从缓冲区送到用户区的时间为M，CPU处理运算这块数据的时间为C，T和C是可以并行的，因此有：

当 T > C 时，系统处理数据的时间为 T
当 T < C 时，系统处理数据的时间为 C
即系统处理一个数据块的时间为 Max(C,T)

对于字符设备，采用双缓冲能消除用户进程等待的时间，用户输入完数据后，CPU执行第一行命令时，用户进程可以继续向第二个缓冲区输入第二行数据

双机通信时，需要在两个机器中各设置两个缓冲区，一个用于发送，一个用于接收，即可实现双向通信。

环形缓冲区

当数据的生产者和消费者之间的速度差异较大时，双缓冲仍然可能出现缓冲区不足的问题。环形缓冲区通过将多个缓冲区组成的环形队列的方式，进一步提升I/O效率。环形缓冲区有以下特点：

包含多个缓冲区，每个缓冲区大小相同
包含三种类型的缓冲区：
- 空缓冲区R：用于装入数据
- 满缓冲区G：已装满数据，等待CPU或进程取用的缓冲区
- 当前工作缓冲区C：计算进程当前正在使用的缓冲区
通常使用多个指针来管理环形缓冲区：
- Nexti指向输入进程下一次可使用的空缓冲区
- Nextg指向计算进程下一次可以取得的满缓冲区
- Current指向计算进程当前正在处理的工作缓冲区
- 随着输入和处理过程不断进行，这些指针沿环形缓冲区不断向前移动，到达末尾后重新回到开始位置

工作流程：

输入进程不断寻找空缓冲区（R）填入数据，使其变为已满缓冲区（G）。
CPU或用户进程从已满缓冲区（G）中取出数据进行处理，处理完后该缓冲区变为空缓冲区（R）

进程同步问题：

环形缓冲区本质上属于一个生产者—消费者问题。输入进程不断产生数据；计算进程不断取出并处理数据。因此除了缓冲区本身，还必须考虑两个进程之间的同步关系：

当Nexti追赶上Nextg时，说明输入速度较快，所有空缓冲区都已被装满，此时输入进程必须阻塞，等待计算进程处理完某个满缓冲区，并将其释放为空缓冲区。这种情况称为系统受计算限制
当Nextg追赶上Nexti时，说明计算速度较快，所有已经输入的数据都被计算进程处理完，此时计算进程必须阻塞，等待输入进程产生新的数据并释放相应的满缓冲区。这种情况称为系统受I/O限制

增加环形缓冲区的数量可以提高系统吸收瞬时速度差异的能力，但并不能从根本上消除生产者和消费者之间的同步关系。当一方长期明显快于另一方时，最终仍可能出现所有缓冲区被占满或全部为空的情况

缓冲池

单缓冲、双缓冲和环形缓冲区通常是为特定的生产者和消费者设置的，属于专用缓冲区，当系统规模较大、存在大量I/O操作时，如果每组生产者和消费者都建立自己的循环缓冲区，会消耗较多内存，而且不同缓冲区之间无法充分共享，容易出现某些缓冲区繁忙而另一些缓冲区空闲的情况。

缓冲池（Buffer Pool）包含多个由系统统一管理的公用缓冲区，可以被多个进程共享，且既可以用于输入，也可以用于输出。缓冲池与缓冲区的区别是缓冲区仅是一组内存块的链表，而缓冲池则包含用于管理缓冲区的数据结构和一组函数操作。

缓冲池的组成

缓冲池管理着多个缓冲区，缓冲区分为缓冲首部(存放缓冲区号、设备号、设备上的数据块号等信息)和缓冲体(存放数据)两部分，为方便管理，相同类型的缓冲区会链接为一个队列，因此缓冲池由以下三个队列组成：

空缓冲队列emq（Empty Buffer Queue）：由空闲可用的缓冲区组成
输入队列inq（Input Queue）：由装满输入数据的缓冲区组成，等待进程提取
输出队列outq（Output Queue）：由装满输出数据的缓冲区组成，等待设备处理
这些队列是临界资源，需要互斥访问，同步使用

为保证对上述队列的互斥访问，又同步剩余缓冲区资源数量，因此可为每个队列设置一个互斥信号量 MS(type)，设置一个资源信号量 RS(type)

void Getbuf(unsigned type){
    Wait(RS(type));  //请求一个资源
    Wati(MS(type)); //互斥访问，加锁
    B(number)=Takebuff(type); //从对应类型队列取下一个缓冲区，赋值给B
    Signal(MS(type)); //释放锁
}
void Putbuf(type,number){
    Wati(MS(type)); //互斥访问，加锁
    Addbuf(type,number); //将number指向的缓冲区B挂到type队列上
    Signal(MS(type)); //释放锁
    Signal(RS(type)); //添加一个资源
}

缓冲池的工作方式

从缓冲池的工作方式可以归纳为四种基本操作：

收容输入：输入进程从空缓冲队列emq取得一个空缓冲区，将其作为收容输入工作缓冲区hin，将数据装入其中，装满后挂在输入队列inq上
提取输入：计算进程从输入队列inq的队首取得一缓冲区，作为提取输入工作缓冲区(sin)，并从中提取数据。用完数据后，将其挂到空缓冲队列emq上
收容输出：计算进程从空缓冲队列emg的队首取得一空缓冲，作为收容输出工作缓冲区hout，向其装入输出数据，装满后将其挂在outq末尾
提取输出：输出进程从输出队列的队首取得一装满输出数据的缓冲区，作为提取输出工作缓冲区sout。在数据提取完后，将它挂在空缓冲队列末尾

磁盘存储器管理

磁盘结构参考《计算机组成原理上》笔记存储器章节

磁盘格式化

为了能在磁盘上存储数据，需要将磁盘作以下处理：

低级格式化：又称为物理格式化，将物理硬件组织为底层可识别、读写的扇区，该操作通常由硬盘厂商执行。该过程中，每条磁道会被格式化为若干个大小固定的扇区，并为每个扇区添加用于磁盘管理的数据结构和物理结构。通常情况下，一个扇区通常会被拆分为头部、数据存储区域、尾部三部分，头部和尾部用于存放当前扇区所处的磁道号(Track)、磁头号(Head)、扇区号(Sectors)、控制区CRC校验码等控制信息。数据区域用于存放数据、数据区CRC校验码等信息
分区：将整个磁盘的扇区划分成若干逻辑区域(卷)，并在磁盘的0号逻辑扇区建立主引导记录MBR，MBR中的分区表会记录这些分区的起始扇区和大小。此外，如果该磁盘安装了操作系统，操作系统所处的分区会被标记为活动分区，方便从硬盘引导操作系统。
高级格式化：又称为逻辑格式化，该过程会在该分区中建立文件系统，包括创建文件系统的根目录、初始化存储空间管理所用的数据结构(如位示图、空闲分区表)等

坏块管理

当某扇区出现硬件故障导致无法使用，通常需要进行以下坏块管理：

对于简单的磁盘，可以在逻辑格式化时(建立文件系统时)对整个磁盘进行坏块检查，在文件系统中标明哪些扇区是坏扇区，比如：在FAT表上标明。该管理方式坏块对操作系统不透明
对于复杂的磁盘，磁盘控制器(磁盘设备内部的硬件部件)会维护一个坏块链表。在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化。通常也会保留一些“备用扇区”，用于替换坏块，这种方案称为扇区备用，这种处理方式中，坏块对操作系统透明

磁盘访问时间

磁盘设备时以恒定速率旋转，读写时，磁头需要先移动到指定磁道上，并等待指定扇区开始位置旋转到磁头下，然后开始读写，因此磁盘访问时间分为以下三部分：

寻道时间Ts：把磁头(通过磁臂)移动到指定磁道上所花的时间，其中启动磁臂的时间为s，磁头跨越一个磁道的时间为m(与磁盘驱动器速度有关，通常是一个常数)，总共需要跨越n条磁道，则寻道时间(通常是5-30ms)：
$Ts = m × n + s$
旋转延迟时间Tτ：指定扇区旋转到磁盘下所需的时间，设磁盘转速为 r(这里的计算单位为转/秒，而机械硬盘转速通常为5400转/分或7200转/分)，则转一圈所需时间为1/r，找到目标扇区平均需要转半圈，因此旋转延迟时间为：
$Tτ= \frac{1}{2r}$
传输时间Tt：数据读出/写入磁盘的时间，其大小与每次读/写的字节数b、旋转速度r、一条磁道上的字节数N有关：
$Tt= \frac{b}{rN}$
因此磁盘访问时间Ta为：
$Ta = Ts + \frac{1}{2r} + \frac{b}{rN}$
寻道时间和旋转延迟时间通常固定，当每次输出的数据量很少时，传输时间占磁盘访问时间的少部分，输出数据量大时，数据传输时间占比增大，因此适当集中传输数据，能有效提高输出效率。

磁盘调度算法

好的磁盘调度算法可以减少寻道时间，以减少对文件的访问时间。

先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度，该算法实现简单，不会出现请求长期得不到满足的情况。缺点是未做寻道优化，磁头可能需要频繁跨越大量磁道，平均寻道时间可能较长，适合磁盘I/O请求较少的场合
最短寻道时间优先（SSTF）：优先服务所要访问的磁道与磁头当前所在磁道距离最近的请求，以使每次寻道时间最短，但该算法不能保证平均寻道时间最短，且如果不断有较近磁道的请求到达，较远磁道的请求可能长期得不到服务，出现“饥饿”现象

基于扫描的磁盘调度算法

扫描算法（SCAN）：该算法不仅考虑欲访问磁道与当前磁头的距离，更优先考虑磁头当前的移动方向。即磁头沿一个方向移动，依次服务该方向上所有请求，到达最远磁道后改变方向返回继续服务，选择进程的标准是在当前移动方向上，距离当前磁头位置最近的请求。该算法磁头移动规律很像电梯运行，因此又称电梯调度算法。该算法能解决“饥饿”问题，且有不错的寻道性能。但假设磁头刚越过某个磁道后，恰好有一个进程请求访问此磁道，则进程需要等待磁头返回，可能最多需要2T时间，其中T为由里向往或由外向里单向扫描完欲访问磁道所需的时间。
循环扫描算法（CSCAN）：规定磁头只能单向移动，如：自里向外移动时，如果磁头移到最外磁道访问完成后，立即移到最里的欲访问磁道。这样进程等待时间从2T减为 T+S，其中S为从最外磁道立即移到最立磁道的寻道时间。
磁臂粘着(Armstickiness)问题：SSTF、SCAN、CSCAN调度算法都可能出现磁臂停留在某处不动的情况，如：有多个进程对某一个磁道有较高访问率，这些进程反复请求对某一磁道的I/O操作，导致磁头一直没有移动
N步扫描(NStepSCAN)算法：将磁盘请求队列分成若干长度为N的子队列，各子队列内部采用SCAN算法，子队列间按FCFS调度。在处理某个子队列时，如果出现新的磁盘I/O请求，则将新请求放入其他队列，可有效防止“磁臂黏着”
FSCAN：NStepSCAN的特例（N=1），FSCAN算法只将磁盘请求队列分为两个子队列，即每次只处理一个子队列，处理期间的新请求加入另一个队列，也可有效防止”磁臂黏着”

减少延迟时间

知识点老，教材已删减

交替编号（Interleaving / Sector Skew）：如果物理扇区连续编号（0,1,2…），当磁盘控制器处理完扇区0的读写并准备读写扇区1时，需要一定的准备时间，但盘片是匀速转动的，磁盘控制器准备好时，磁头可能已经转过了扇区1的位置，必须等磁盘再转一圈，带来极大延迟。交替编号的思想是在物理层面上，相邻的扇区在磁道上并不连续排列。例如：将物理扇区编号为 1, 3, 5, 7…（交错因子为2），给磁盘控制器留出处理数据传输的时间。该设计主要用于早期磁盘控制器处理能力弱的磁盘，现代磁盘控制器处理速度极快，且内置缓存，静态的交错编号已很少见。
错位命名（Slip / Cylinder Skew）：当程序顺序读取完一个磁道的所有扇区，需要切换到相邻磁道继续读取。如果两个磁道的0号扇区都在同一径向角度（正对着），那么磁头移动到新磁道后，目标扇区可能刚刚转过磁头下方。因此错位命名的核心思想是相邻磁道的起始扇区位置会错开一定的角度。外圈磁道的起始点与内圈磁道的起始点不在一条半径上，而是沿着旋转方向偏移若干个扇区，方便磁头在磁道间移动时，可以无缝顺序读取。
磁盘地址结构设计：传统磁盘结构使用CHS寻址，使用（柱面号Cylinder，磁头号Head，扇区号Sector）这一三元组确定地址，当扇区号达到最大值(如：读完(00,00,000)到(00,00,111))后，通过修改磁头号即可切换到另外一个盘面的相同柱面(磁道)继续读/写，而不需要移动磁臂(有较大开销)，因此该磁盘地址格式相比根据物理逻辑寻址(磁头号，柱面号，扇区号)，即先决定盘面，再选择磁道，最后选择扇区，有更好的读写性能。

上述技术本质上都是利用对扇区物理布局的重新排列，补偿磁盘控制器处理、磁头切换或寻道等操作产生的时间延迟，这些概念主要针对传统机械硬盘的物理组织和早期磁盘优化，现代 HDD 对外通常提供的是LBA 逻辑块地址，操作系统一般不再直接管理“某个扇区实际位于盘片哪个角度”；具体的物理映射和很多优化已经由磁盘固件完成。

CHS寻址

早期操作系统访问机械硬盘时主要采用CHS寻址方式（Cylinder-Head-Sector，柱面-磁头-扇区），OS通过给定柱面号、磁头号和扇区号来定位硬盘上的物理扇区。CHS方式直接暴露了硬盘的物理几何结构，因此与硬盘的实际结构高度相关。随着硬盘容量增大以及坏扇区重映射等技术的发展，硬盘的实际物理布局越来越复杂，固定的 CHS 地址空间也受到容量和寻址范围的限制，因此逐渐不再适合作为OS访问硬盘的主要寻址接口。

LBA寻址

现代操作系统普遍采用LBA逻辑块寻址方式（Logical Block Addressing）访问磁盘。对于OS而言，磁盘设备向主机提供的是一个从 0 开始连续编号的逻辑块地址空间，其中 LBA 0、LBA 1、LBA 2……分别表示该设备上的第 0、1、2……个逻辑块。操作系统进行磁盘 I/O 时，只需向磁盘发出“从某个 LBA 开始读取或写入若干个逻辑块”的请求。之后磁盘内部的设备控制器随后根据设备的内部地址映射机制，将 LBA 转换为实际的物理存储位置：对于机械硬盘，最终定位到相应的物理磁道和扇区；对于固态硬盘，则通过闪存转换层（FTL）将 LBA 映射到相应的 NAND Flash 物理位置，如通道、芯片（Die）、块（Block）和页（Page）等。LBA通常是设备级的逻辑地址，每个独立的磁盘或SSD通常拥有自己的LBA空间(每个设备都从LBA 0开始编号)，多个磁盘并不会共享一个全局LBA地址空间。

机械硬盘LBA地址到物理地址的映射

对于机械硬盘，从逻辑地址到物理地址映射的核心逻辑是：根据磁盘物理结构和数学计算完成地址变换，不涉及动态映射表。具体而言，机械硬盘内部的扇区通常按照一定的数学规律组织排列(包括使用上文交替编号、错位命名等方式)，LBA 到物理位置的映射具有很强的规律性，硬盘控制器内置了固定的物理几何参数，包括每磁道扇区数（SPT）和每柱面磁头数（HPC）等参数，OS发出LBA逻辑地址（如：要读第10000号扇区）后，硬盘控制器固件按照一个固定的数学公式，把这个线性的LBA，换算成真正的物理位置，即CHS（柱面号Cylinder、磁头号Head、扇区号Sector），如某种数学映射关系可能为：

柱面号（C） = LBA ÷ （HPC × SPT）
磁头号（H） = （LBA ÷ SPT） % HPC
扇区号（S） = LBA % SPT + 1 (物理扇区编号通常从1开始，而LBA从0开始，因此需要+1)

现代机械硬盘还引入了动态技术，虽然物理映射仍是固定公式，但磁盘缓存固件可能会对 LBA 做轻微重排，并做好缺陷管理，如：硬盘会预留一部分扇区作为备用物理扇区，在发现某些坏扇区/缺陷区域后会进行重映射，将逻辑地址映射到备用区域而避开坏扇区，这样OS依旧可以使用原有逻辑地址访问磁盘，这种缺陷管通常依赖表实现，但该表只需要记录发生特殊映射的部分，而不会记录所有扇区的映射关系，与内存的全量通过页表管理截然不同。

固态硬盘

固态硬盘SSD（Solid State Drive）是一种以NAND Flash闪存芯片内部的浮栅晶体管作为主要存储介质的非易失性存储设备，从电可擦除ROM(EEPROM)技术发展而来。SSD向上层操作系统依旧通过LBA（逻辑块地址）方式提供访问接口，并对外暴露为标准的块设备，从而与传统的机械硬盘（HDD）在软件层面保持兼容，无需修改现有文件系统和应用程序

SSD的特点

相较于机械硬盘HDD（Hard Disk Drive），SSD有以下特点：

读写速度快，随机访问性能高，没有HDD的机械移动带来的寻道时间、旋转延迟
功耗和噪声通常低于机械硬盘
抗震动能力较强
存在擦写次数限制，一个块被擦除次数过多可能会坏掉，因此需要复杂的控制器和管理机制(磨损均衡技术)

NAND Flash存储原理

NAND Flash芯片(NAND是与非门Not AND的缩写)属于一种非易失性存储器（Non-Volatile Memory），其基本原理是利用存储单元中电子的状态来表示数据，断电后，存储的数据仍然可以保持，根据一个存储单元能够表示的比特数，可分为：

SLC（Single-Level Cell）：1 bit/cell(一个单元可表示2种状态)
MLC（Multi-Level Cell）：2 bit/cell(一个单元可表示4种状态)
TLC（Triple-Level Cell）：3 bit/cell(一个单元可表示8种状态)
QLC（Quad-Level Cell）：4 bit/cell(一个单元可表示16种状态)
PLC（Penta-Level Cell）：5 bit/cell(一个单元可表示32种状态)

一个 NAND 单元能够表示的状态越多，单位面积能够存储的数据越多，但通常也会带来更复杂的读写控制、更高的误码率、更长的写入/擦除延迟以及更低的擦写耐久度

组成

固态硬盘由以下部分组成：

闪存转换层FTL(Flash Translation Layer)：主要负责逻辑地址与 NAND Flash 物理地址之间的映射转换，将LBA逻辑地址转换为数据存储的块号、页号物理地址。此外，FTL还参与垃圾回收、磨损均衡、坏块管理、参与ECC检查等
存储介质：由多个闪存芯片(Flash Chip)组成，每个芯片包含多个块(block)(通常几百KiB到几MiB)，每个块包含多个页(page)(通常4-32KiB)

SSD的实际结构

实际 SSD 的内部结构比上述模型更加复杂。SSD 由SSD Controller（SSD控制器）管理多个 NAND Flash 存储单元，控制器通过多个Channel（通道）连接 NAND Flash，不同 Channel 可以并行进行数据传输。一个 Channel 上可以连接多个Package（闪存封装），一个 Package 内又可能包含多个Die（裸片）；每个 Die 内进一步划分为多个 Plane（平面），Plane 中包含多个Block ，Block 中包含多个 Page

SSD │ ├── SSD Controller（SSD控制器） │ ├── Channel 0 (通道，多个通道间可以并行数据传输) │ ├── Package (封装，即NAND闪存颗粒) │ │ ├── Die (裸片，大型独立NAND存储单元，可以独立参与 NAND Flash操作的硅片) │ │ │ ├── Plane (Die内部用于提升并行操作能力的组织单位) │ │ │ │ ├── Block (擦除的基本单位) │ │ │ │ │ ├── Page (读写的基本单位) │ │ │ │ │ └── ... │ │ │ │ └── ... │ │ │ └── ... │ │ └── ... │ └── ... │ ├── Channel 1 │ └── ... │ └── Channel 2 └── ...

其中，Channel、Package、Die 和 Plane 主要用于组织 NAND Flash 并实现多层次并行访问。SSD 控制器可以同时利用多个 Channel、Die 或 Plane 执行操作，从而提高整体存储带宽。这些属于 SSD 内部的硬件组织结构，操作系统通常无需直接感知，对于 OS 而言，SSD 主要表现为一个提供LBA 逻辑块地址空间的块设备

读写操作特性

SSD有三个基本操作：Read（读取）、Program（写入）(闪存中写入操作是通过施加高压脉冲将电子强行注入到浮栅晶体管内部实现的，并且由于电路串扰，必须一次性写入整页的数据，无法逐字节修改，因此记为Program)、Erase（擦除）:

读写通常以页(Page)为单位
擦除则需要以块(Block)为单位
要写的页如果有数据，则不能写入，需要将块内其他页全部复制到一个新的(擦除过的)块中，再写入新的页，因此会有读快、写慢特性

写入限制

闪存芯片修改数据时不支持像 RAM 一样的原地覆盖，当逻辑数据发生修改时，SSD需要采用以下步骤：

将修改后的新数据写入其他空闲的Page
将旧 Page 标记为 Invalid
由此，原逻辑地址LBA 100对应的原物理位置 Block 10 / Page 5，数据被修改后，将被重新映射为：LBA 100对应物理位置 Block 30 / Page 20

Block 擦除

由于 Flash 不能单独擦除某一个 Page，当需要重新利用包含失效 Page 的 Block 时，必须：

将有效数据搬迁到其他位置；
擦除整个 Block；
将擦除后的 Block 重新作为空闲 Block 使用

文件删除操作TRIM

操作系统（文件系统）删除文件时，将在逻辑地址（LBA）上将对应逻辑扇区标记为“空闲”，但SSD的FTL闪存转换层不会立即擦除数据，而是将文件所处物理页标记为 Invalid，为了防止这些无效数据在GC时一起被搬移到其他 Block 中，造成无效搬移，文件在被删除后，会执行以下流程：

操作系统会通过 SATA/NVMe 协议，向 SSD 发送TRIM 指令
SSD 收到 TRIM 指令后，FTL 立即在内部的映射表中，将这些 LBA 对应的物理页标记为 Invalid
SSD 在整理数据时(GC阶段)，将搬移有效 Page中的数据，而保留 Invalid 的 Page，等待整块 Block 都没有有效数据时，统一擦除

垃圾回收机制

随着写入不断进行，修改后的数据都会被写入到空闲页，旧页将被标记为Invalid，同时，被删除的数据页也会被标记为 Invalid，SSD 内部也会产生越来越多的 Invalid Page。由此垃圾回收GC(Garbage Collection)会回收包含大量无效 Page 的 Block，使其重新成为可写的空闲 Block，其过程为：

将需要回收的 Block 中有效 Page 搬迁到其他 Block
在整个 Block 都已经没有有效数据时，擦除整个 Block
Block 重新进入空闲 Block 池

写放大

写放大WA(Write Amplification)指SSD内部物理实际写入的数据量大于操作系统/主机逻辑要求写入的数据量的现象，WA的值为实际向 NAND Flash 写入的数据量与主机请求写入的数据量之比：

WA = \frac{NAND 实际写入量}{主机请求写入量}

产生写放大的原因包括：

Flash 不能原地覆盖
垃圾回收需要搬迁有效 Page
磨损均衡需要搬迁数据

e.g 主机要求写入 100 GB，NAND 由于需要进行数据搬移实际写入 150 GB，则 WA = 1.5

过量预留空间

SSD 通常不会将全部 NAND 空间都直接提供给用户，而会保留一部分内部空间用于：垃圾回收、磨损均衡、坏块替换等功能，这种内部预留空间即为过量预留空间(Over-Provisioning)

磨损均衡技术

磨损均衡的核心思想是使 Flash 中各 Block 的擦除次数尽可能均匀，避免少数 Block 被过度擦写而提前失效，它包括：

动态磨损均衡：写入数据时，优先选择累计擦除次数少的新闪存块
静态磨损均衡：如果某些块存放着长期不修改的数据(读操作居多)，会导致这些块擦除次数很少，而有的块则由于数据变更频繁而导致高磨损，因此SSD会监测数据块的磨损程度，将长期不修改的冷数据搬移到高磨损的块中，让低磨损的块空出来参与磨损

关于HDD和SSD的数据恢复

机械硬盘HDD：文件系统删除数据后，原有磁盘扇区中的数据通常不会立即被物理擦除。文件删除时，文件系统主要修改目录项、文件分配表、inode 等元数据，将原文件占用的逻辑扇区 LBA 标记为空闲，而对应物理扇区中的数据仍可能保留。由于 HDD 中 LBA 与物理扇区之间的对应关系相对稳定，恢复软件可以遍历磁盘的 LBA 地址空间，直接读取各逻辑扇区中的残留数据，再根据文件系统元数据、文件头、文件尾、数据结构等信息重建被删除的文件。因此，即使文件系统元数据已经损坏，只要原数据尚未被新数据覆盖，仍有较大的恢复可能性
固态硬盘SSD的数据恢复则更加复杂，SSD 删除数据后，除了文件系统层面的逻辑删除，还可能受到 TRIM、FTL 和垃圾回收（GC）机制的影响。文件删除后，文件系统会释放相应的 LBA；如果系统向 SSD 发送 TRIM，SSD 控制器会通过 FTL 得知这些 LBA 对应的数据已经不再需要，并将相应 NAND Page 标记为无效。此时旧 Page 中的数据在物理上可能尚未被 GC 擦除，但由于 LBA 与 NAND Block/Page 之间的映射由 FTL 动态维护，且 NAND Page 不直接向主机开放，普通恢复软件无法像 HDD 一样遍历底层 Page 并读取其中的数据。之后 SSD 执行 GC 时，还会搬迁仍有效的数据并擦除包含无效 Page 的整个 Block，使原有数据进一步被物理清除。因此，SSD 删除恢复不仅取决于数据是否已经被物理擦除，还受到 TRIM 导致的逻辑失效以及 FTL 动态地址映射的影响，恢复难度通常远高于 HDD

文件管理

文件与文件系统

文件指具有文件名的若干相同元素的集合，文件系统的管理功能是将其管理的程序和数据通过组织为一系列文件的方式实现的，因此文件是文件系统中最大的数据单位。文件本身包含两部分意义：

文件内容：文件真正的数据部分
文件属性/元数据：文件的属性信息，如：文件类型、大小、创建事件等

文件

文件分为有结构文件和无结构文件两种：

有结构文件：文件由若干记录组成，一条记录则由若干数据项组成，数据项是文件系统中最低级的数据组织形式。如：学生管理系统中，一个学生的信息即为一条记录，该记录可由学号、姓名、班级、成绩等数据项组成。通常在诸多数据项中选择一个或多个数据项以唯一地表示一个记录，则这些数据项称为关键字(key)，如：学号可以唯一标识一名学生，学号可作为关键字。有结构文件广泛用于数据库、信息管理系统等领域
无结构文件：又称为流式文件，文件长度以字节为单位，文件由二进制流或字符流组成，对文件的访问是通过读写指针指向下一个要访问的字符实现的，可执行文件、库函数等都属于无结构文件。

文件属性

一个文件通常包含文件名、标识符(inode)、文件类型、文件位置、文件大小、创建时间、上次修改时间、保护信息等文件属性

文件名和拓展名

文件名：不同文件系统对于文件名的要求不同，如：是否区分大小写，允许多长的文件名，但通常都不允许在同一目录下有两个同名文件
拓展名：又称为后缀名，拓展名是指文件名后添加的若干附加字符，它是文件名的组成部分，通常使用”.”分隔，用于方便系统和用户识别文件类型

文件类型

根据不同的区分方式，文件可以被分类成诸多不同的文件类型，如：根据读写权限可分为：只读文件、只写文件、可读写文件，而根据文件组织形式，可分为：

普通文件：由二进制码或ASCII码组成的文件，各类数据文件、代码文件、文本文件等大多数文件都属于普通文件
目录文件：由文件目录组成的文件
特殊文件：特指各类I/O设备，系统将这些I/O设备抽象为文件，并以文件形式提供给用户使用，只是对这些文件的操作由设备驱动程序来完成。

文件操作

创建文件：创建一个新文件时，会执行create系统调用，主要进行两件事：需要为该文件分配外存存储空间；分配一个索引结点，在对应的目录文件中为其建立一个目录项，保存文件名与索引结点(inode号)，并在索引结点存储文件属性信息
删除文件：需要执行Delete系统调用，该操作会回收文件占用的存储空间，然后删除目录中对应的目录项
打开文件：需要执行open系统调用，打开文件操作并不会把文件数据块（Data Blocks）直接读入内存，而是根据文件所在目录文件中的目录项，将指名文件的属性(包括文件大小、权限、在外存的物理位置)从外存拷贝到内存的打开文件表的一个表目中，并将该表目的索引号(在Unix/Linux中称为文件描述符 File Descriptor，在Windows中称为句柄)返回给用户。用户多次频繁进行文件操作时，OS可以根据用户提供的索引号，直接从打开文件表中获得文件信息，而不需要每次都查找路径和目录文件，从而节省大量的检索开销，并显著提高文件操作速度。为了支持多进程并发、共享文件，内存中的打开文件表通常采用两级结构：
- 系统级打开文件表（System-wide Open File Table）：整个OS只有一张，一个表项代表一个打开文件实例（open file description），表项记录了文件在磁盘的物理位置、文件大小、文件操作权限（如O_RDONLY、O_WRONLY、O_APPEND）、当前的读写指针（Offset）、引用计数等。同一文件可能拥有一个或多个表项，如：两个进程打开了同一个文件，它们的权限不同、读写指针位置不同，因此为系统为该文件创建了两个表项；又如：两个父子进程共享一个文件(通常子进程从父进程处继承而来)，包括打开状态、读写指针位置等，但它们有独立的进程文件描述符表，因此它们的fd会指向同一个系统文件打开表的表项
- 进程级文件描述符表（Per-process File Descriptor Table）：又称为进程级打开文件表，每个进程私有并维护一张表，一个进程可能同时打开多个文件(如：进程打开了3个文件，因此有fd 1,fd 2,fd 3三个表项)，表项内容是一个指针，指向系统级打开文件表的对应表目(fd 1表项的内容为对系统打开文件表某个表项的引用，1是进程级表的数组下标)
关闭文件：用户需要关闭文件时，需要执行close系统调用，文件系统会将系统打开文件表中的引用计数值减1，如果值已经为0，表明已经没有进程打开了该文件，因此会从打开文件表中删除对应的表项
读/写：文件执行读写时，会执行read/write系统调用，会修改打开文件表中当前文件对象中的读写指针，然后执行读/写操作
其他操作：OS还提供了一系列系统调用，用于进行文件元信息的修改、查询等操作

文件系统的层次结构

现代操作系统的文件系统通常采用分层设计，将复杂功能解耦为多个层次，每层只与相邻层交互

用户接口：向上层用户提供接口，包括read、write等系统调用，Shell命令接口、GUI接口
逻辑文件系统(Logical File System)：管理文件的元数据，提供文件和目录的逻辑视图，职责包括：
- 文件名解析：将路径名（如 /home/user/file.txt）解析为内部标识
- 目录管理:维护目录结构，实现文件名到文件控制块（FCB/inode）的映射
- 文件控制块管理：管理FCB或inode，存储文件元数据（大小、权限、创建时间等）
- 文件保护：检查访问权限（读/写/执行），实现访问控制
文件组织模块（File Organization Module/分配模块）：负责文件的物理组织和磁盘空间管理，维护空闲空间位图、成组链接表等数据结构，职责包括：
- 将文件内的逻辑块号映射为文件系统视角下的磁盘块号(即卷内块号，现代设备通常表现为逻辑区块地址LBA(Logical Block Address))
- 空闲空间管理：维护空闲空间位图、成组链接表等空闲空间管理结构；
- 负责磁盘块的分配与回收
物理文件系统(Basic File System/基本文件系统)：屏蔽硬件差异，向上层提供统一的块设备访问接口，将上层已经确定的磁盘块号/LBA组织成通用的块I/O请求，并交给设备驱动程序执行，同时管理内存中的磁盘缓冲区，向设备驱动程序发送读写磁盘块的通用命令
以下属于I/O系统内容，与文件系统密切相关
I/O控制层（设备驱动程序）：将物理文件系统提交的通用块I/O请求转换为具体设备和控制器所需要的命令或协议请求，并负责操作设备控制器，启动设备读写，处理中断，向上层报告操作完成或错误
物理设备层：控制磁盘（HDD/SSD）、磁带、光盘的读写，将LBA进一步转换为实际的物理位置（如：柱面、磁头、扇区），这些内部映射对上层透明

文件系统在内外存中的结构

文件系统在外存上的核心结构有：

FCB/索引结点（inode）：保存文件元数据，如文件大小、权限、所有者、时间戳、文件类型等，保存或描述文件数据块的位置
目录文件：本质上也是一种特殊文件，保存文件名到inode号/文件控制信息的映射，用于根据路径名查找文件
文件数据：文件的数据实际存储位置，它们位于若干磁盘块中

文件系统在内存中的核心结构有：

目录项缓存：主要缓存最近访问过的，加速文件名 → inode的路径解析和目录查找，加速路径名解析和目录查找
系统打开文件表：维护当前系统中的打开文件实例，表项保存打开文件实例的状态，例如当前文件偏移量、打开模式、引用计数，以及指向inode/文件对象等内核数据结构的引用
进程打开文件表：维护某个进程所打开的文件；以文件描述符（fd）/句柄作为索引；表项指向系统打开文件表中的相应表项/打开文件对象

文件的逻辑结构

系统中的所有文件都存在以下两种形式的文件结构：

逻辑结构(File Logical Structure)：用户视角看到的文件组织形式，它独立于文件的物理特性，是用户能直接处理的数据和结构，又称为文件组织(File Organization)。好的文件逻辑结构有利于文件的检索、修改，减少文件存储占用。
物理结构：又称为文件的存储结构，指文件存储在外存上形成的存储组织形式。

逻辑结构的类型

按文件是否有结构分为(具体介绍参考上文“文件”小节)：

有结构文件：文件由若干记录组成，记录又分为：
- 定长记录：文件中所有记录的长度相同，且记录中各数据项都在记录中处在相同的位置，具有相同顺序和长度。定长记录能有效提高检索记录的速度和效率，方便对文件进行修改。
- 变长记录：文件中各记录的长度不同，即记录中各数据项的数量不同、长度不同。由于记录无法等长存储，因此变长记录检索速度慢，不便于修改，但很适合某些场合需要。
无结构文件：文件由二进制流或字符流组成

有结构文件的组织方式

顺序文件

顺序文件(Sequential File)文件中的记录一个接一个按某种顺序排列(逻如按写入先后或按关键字排序)，记录可以是定长的或可变长的

顺序文件中记录可以按照不同的顺序排列：

串结构：记录排列的顺序与关键字无关，通常按存入时间的先后进行排序。检索记录时均需要从头开始，逐个查询，因此串结构文件检索费时。
顺序结构：记录按照关键字排序存放(如按英文字母顺序排序)，每条记录的关键字必须具有唯一性。在进行检索时，折半查找法、插值查找法、跳步查找法等方法提高检索效率，顺序结构文件可有更高的检索速度和效率

记录寻址

定长记录寻址：由于记录长度固定，因此可实现随机存取，如：记录长L，则第i个记录相对于首记录的地址是i*L。假设记录还能保证顺序结构，则可以在随机存取的基础上实现快速检索。
变长记录寻址：记录长度长短不一，无法直接计算地址，需要从头查看每个记录的长度。顺序文件下变长记录无法实现随机访问，只能依赖下文的索引文件。

索引文件

生活中的大多数场景需要通过变长记录存储信息，但变长记录随机访问i需要查找前i-1个记录，为解决这一问题，可通过建立一张索引表来加快文件检索速度。

索引文件(Index File)：为变长记录建立一张索引表，每个索引项对于一条记录，索引项按关键字排序，内容包含记录的关键字、记录长度、记录逻辑地址(指针)等。索引文件本身为定长记录顺序文件，这样就把对变长记录的检索转变成了对定长记录顺序文件的检索。其优点是：随机访问速度快，增删改只需修改索引，便于变长记录管理。缺点是：索引表占用额外空间，访问记录可能需要先查索引再读数据。可为同一顺序文件通过不同关键字建立多个索引表，以满足不同目的、不同检索需求，如：学生信息管理相同中，可根据学号建立一张索引表，也可以根据姓名建立索引表。

索引顺序文件

使用索引文件作为文件检索依据时，如果文件包含大量记录，索引文件长度也会暴涨，索引文件的查找也会带来巨大开销。

索引顺序文件(Index Sequential File)将记录分组，每组包含若干条按顺序排列的记录，只对每组建立一个索引项，索引项指向该组首记录，然后在组内顺序查找。其优点是索引表比普通索引文件小得多，查找效率比顺序文件高。

为了进一步提高检索效率，可以为顺序文件建立多级索引表

e.g.假设一个顺序文件所含记录数为 N 1.普通顺序文件，检索一个具有指定关键字的记录，平均需要查找N/2个记录。 2. 如果使用索引顺序文件，将 N 条记录平均分成 G 组，每组包含的记录数为 L = N/G。检索一个记录，为了找到记录所在组，平均需要查找G/2次，然后在组内平均查找 L/2 次记录，由此总平均查找次数为G/2+L/2。为了使得该值最小，可以动态调整G和L的值，根据均值不等式有：G+L≥2√GL。其中G*L=N，由此得索引顺序文件平均需要查找√N个记录 3. 使用多级索引顺序文件，可以进一步提高检索效率，参考下文

e.g.假设一个顺序文件含有10⁶个记录，当它作为索引顺序文件，找到一个记录平均需要查找1000条记录如果使用两级索引，先以100个记录为一组，由此低级索引表包含 10 ⁴个表项，为该索引表建立一张高级索引表，以100个表项为一组，则有10 ²个表项。为找到一条记录，平均需要50+50+50=150次查找，远比一级索引 1000 次小

直接文件和哈希文件

上述几种文件组织方式都是通过检索记录的关键字，从线性表或链表读取记录的物理地址。直接文件指可以根据给定的关键字直接获得记录的物理地址，该组织方式的重点在于用什么方法实现记录值到物理地址的转换。其中应用最广泛的一种直接文件是哈希文件，它通过哈希(散列)函数将关键字转换为对于记录的地址。但为了实现文件存储空间的动态分配，哈希函数所求得的不是记录的地址，而是一个目录表中相应表目的指针，然后根据表目的内容读出记录所在物理地址。该方式存取速度快，适合按键随机访问，缺点是存在哈希冲突，需要处理溢出，文件空间利用率取决于哈希函数和装载因子。

文件目录

文件控制块FCB

文件控制块FCB(File Control Block)是用于描述和控制文件的数据结构，方便文件系统通过通过该控制块描述和操作文件，一个文件通常对应一个文件控制块，文件控制块通常包含以下信息：

文件名
文件物理位置：文件在外存上的存储位置，包括起始块号、占用块数、文件字节数等
文件逻辑结构：文件是流式文件还是记录式文件
文件物理结构：文件是顺序文件、链式文件还是索引文件
文件的控制权限
文件的创建日期、上次修改日期
文件当前使用信息(打开该文件的进程数)等

文件目录

FCB的有序集合称为文件目录（Directory），集合中的每一个 FCB 称为一个目录项（Directory Entry），这些信息存储于文件目录的磁盘块上，通常，文件系统将目录视为特殊类型的文件，称为目录文件（Directory File），它有自己的inode号与inode块，由文件系统统一进行管理。

索引结点

索引结点是对FCB的改进

文件目录通常存放在磁盘上，当文件数量很多时，文件目录可能占用大量的磁盘块，且通过文件名检索目录时性能很差，主要原因就是FCB包含大量文件描述信息，而这些信息在进行文件名匹配时完全没用。

因此，现代文件系统采用将文件名与文件描述信息分开的方法，将文件描述信息单独整理为一个名为索引结点的数据结构，简称为i 结点(Unix系统)，而文件目录中的目录项仅保留文件名与该文件对应的i结点，由此可以大大减少目录项的占用和文件检索开销：

文件名	索引结点编号
a.txt	17
b.sh	25
mydir	31

磁盘索引结点

索引结点在现代文件系统中的实现虽有差异，但核心思想都一致：将文件名与文件的管理信息(文件属性、数据块地址等)分离存储，以减少目录项的大小。因此，索引结点承担了FCB职责，它们在不同文件系统的名称为：

inode（index node）：用于Linux 的ext2/ext3/ext4文件系统，它不包含文件名，由此天然可以使多个硬链接指向同一个inode，使同一文件拥有多个文件名
MFT（Master File Table）：用于在 Windows 的NTFS 文件系统，它可以包含文件名，并可以包含多个文件名作为值

磁盘索引结点通常存储以下内容：

文件所有者/所属组标识：拥有该文件的个人/组的标识符
文件类型
文件控制权限
文件物理地址：指出文件数据所在盘块的编号
文件大小：通常以字节为单位
文件连接数：本文件系统中所有指向该文件的文件名的计数
文件创建时间
文件存取时间：包括文件最近被访问时间、被修改时间、索引结点最近被修改时间等

内存索引结点

当文件被打开时，磁盘索引结点会被拷贝到内存索引结点中，并添加以下内容：

索引结点编号：用于标识内存索引结点
状态：标识 i 结点是否被上锁或修改
访问计数：当前有多少进程访问该 i 结点
文件所属文件系统的逻辑设备编号

简单文件目录

最简单的目录结构组织形式是单级目录和两级目录

单级文件目录

整个文件系统中只建立一张目录表，每个文件占一个目录项，含文件名、扩展名、文件长度、类型、物理地址等，额外设置一个状态位标识目录项是否空闲，它有以下特点：

创建一个新文件时，需要先检索所有目录项，保证新文件名在目录中是唯一的，然后建立一个空白目录项，填入信息，将状态位置为1
删除文件时，需要找到目录项，回收空间后清除

其优点是实现简单，但只能实现最基本的按名存取；缺点是查找速度慢；文件不允许重名；不便实现文件共享

两级文件目录

两级目录的结构为：

用户文件目录UFD(User File Directory)：每个用户都有单独的用户文件目录，由该用户所有文件的FCB组成
主文件目录MFD(Master File Directory)：系统建立管理，每个用户目录文件占一个目录项，含用户名和指向该用户目录文件的指针

该组织方式的优点是提高了检索速度；不同用户目录可使用相同文件名；不同用户可用不同文件名访问同一共享文件。缺点是一个用户无法访问其他用户文件；多用户间不便于共享文件。

树形结构目录

树形结构目录(Tree-Structured Directory)是现代OS中最通用且实用的文件目录形式，它包含以下结构：

根目录：又称为主目录，每个文件系统只能有一个根目录
父目录：每个文件和每个目录只能有一个父目录
树叶：数据文件
树的结点：除了树叶外的其他目录，即子目录
目录项可以是数据文件FCB，也可以是目录文件FCB

当前目录与路径

当前目录(Current Directory)：为每个进程设置，避免每次都从根目录检索
路径名(Path name)：从根目录到数据文件的唯一通路，各目录名与文件名用/连接
相对路径(relative path name)：从当前目录到数据文件的路径
绝对路径(absolute path name)：从根目录开始的完整路径

树形目录结构优缺点

优点：查询速度快；结构清晰；文件管理和保护更容易
缺点：查找文件需逐级访问中间结点，会增加磁盘访问次数；文件和子目录通过唯一父目录访问，不便于实现文件共享

目录查询技术

当用户要访问一个已存文件时，系统首先利用用户提供的文件名对目录进行查询，找出该文件的文件控制块或对应索引结点。然后，根据 FCB或索引结点中记录的文件物理地址(盘块号)，换算出文件在磁盘上的物理位置。最后，再通过磁盘驱动程序将所需文件读入内存。对目录进行查询的方式有两种：线性检索和Hash法。

线性检索

线性检索又称为顺序检查法，

单级目录中，直接根据用户提供的文件名，按顺序从文件目录中找到指定文件的目录项即可
在多级目录下，用户根据路径依次需要对多级目录依次进行查找，如：查找文件/usr/ast/mbox，查找流程为：
- 系统从根目录 / 的目录文件中找到 usr 目录的目录项，从目录项获得inode号，从usr的inode中找到 usr目录文件在外存存储位置
- 系统根据 usr 目录文件内容找到 ast 目录的inode号，从 ast 的inode找到ast目录文件在外存中的存储位置
- 系统根据 ast目录文件找到 mbox 的 inode号，由此从mbox的inode找到了该文件在外存的存储位置
- 如果查找过程中某个文件名不存在，则停止查找并返回未找到信息

Hash方法

该方法需要为文件目录建立Hash索引表，当目录中存在大量文件时，系统根据文件名计算哈希值，并利用该哈希值将文件映射到 Hash 表中的某个桶（bucket）。查找文件时，文件系统会对待查文件名执行相同的哈希计算，根据得到的哈希值直接定位当前目录 Hash 表中的对应桶，再在桶内查找目标目录项。这样文件的查找从目录下所有文件的线性检索O(n)转变为了对单个 Hash 桶内少量目录项的检索。

用于目录查询的 Hash 值通常是一个用于索引定位的整数或整数范围内的索引值，而不是像 SHA-256 等密码学哈希那样生成用于数据完整性验证的长摘要。因此，它不要求密码学意义上的抗碰撞等安全性质，也允许多个不同文件名映射到同一个桶。Hash法的特点：

检索速度快
不支持通过“*”、“?”等模式匹配功能
多个不同名文件可能会映射到同一Hash索引表项，即产生“冲突”

e.g.假设当前目录中有文件 A、B、C、D，设 Hash 表有 4 个桶，文件名经过 Hash 函数后得到对应的桶编号

文件名	Hash值/桶编号
A	1
B	2
C	3
D	1

此时 A 和 D 映射到了同一个Hash 桶 1，产生 Hash 冲突，Hash 桶可以通过链式结构等方式保存多个发生冲突的目录项 Hash索引表：

表项	值
桶1	A->D
桶2	B
桶3	C
桶4	Null

查找文件 D 时，系统首先对文件名 D 计算 Hash 值，得到 1，于是直接定位到桶 1；然后沿着桶 1 中的目录项依次比较实际文件名，先比较 A，发现不匹配，再比较 D，最终找到目标文件，在目录下有大量文件时，哈希法将文件查找范围缩小到了哈希桶内

文件共享

文件共享是指系统允许多个用户共同使用同一个文件，而不必为每个用户建立文件副本，这样可以节省存储空间，并方便用户之间通过文件交换信息，文件共享的实现主要有两种方法：

基于有向无循环图实现文件共享(硬链接)
利用符号链接实现文件共享(软链接)

基于有向无循环图实现文件共享

传统的树形目录结构要求一个文件或目录只能有一个父目录，为了实现文件共享，可以允许一个文件具有多个父目录，从而使多个用户的目录都可以指向同一个文件，此时目录结构不再是严格的树，而成为一个有向无循环图DAG（Directed Acyclic Graph）

如上图中

文件F8拥有三个父目录：D5、D6、D3，其中D5和D3还使用了相同名字p
目录D6有两个父目录D2和D1

硬链接

基于有向无循环图实现的文件共享在Linux中的表现为硬链接，该方式又称为基于索引结点的文件共享，其特点是：

目录项只保存文件名和指向文件索引结点的指针(inode号)，文件的物理地址、文件属性等信息存储于索引结点中
多个文件目录项可以引用同一个索引结点，指向同一个文件，以实现文件共享
索引结点中设置有链接计数count，表示链接到该索引结点的用户目录项数
删除某个目录中的文件只会使count值-1，只有count值为0系统才会真正删除文件
DAG图中允许目录有多个父目录，但Linux的文件系统中，不允许为目录创建硬链接，只允许为其软链接

利用符号链接实现文件共享

符号链接（Symbolic Link）有两种表现：

URL：用于计算机网络的符号链接，用户可以在HTML文件中嵌入符号链接，来在计算机网络上共享文件
文件系统中的符号链接，又称为软链接：符号链本身保存的是被共享文件的路径名(可通过readlink命令查看)，当用户访问符号链时，系统根据其中保存的路径找到真正的文件。这意味着只有所指向文件父目录的目录项才拥有指向其索引结点的指针，符号链接文件只是存储了一个路径。因此所指向文件的文件名、路径发生修改，软链接将无法找到该文件

文件保护

文件的安全性受到以下因素影响：

人为因素：人们有意或无意的行为使文件数据遭到破坏或丢失
系统因素：系统某部分出现异常（如磁盘故障）造成数据破坏或丢失
自然因素：随着时间推移，存放在磁盘上的数据逐渐消失

系统因素和自然因素通常通过容错技术、建立后备系统等手段防范，属于磁盘管理内容。文件系统中，文件保护的核心目标是解决对文件的读、写、执行等操作的许可问题，防止文件被未授权用户存取或窃取，确保文件数据的安全性。

访问类型

该部分内容补充自B站电子科技大学蒲晓蓉老师的《计算机操作系统》课程

不同类型的文件系统中，文件的访问类型和权限可能分为以下几种：

无权限(None)：用户甚至无法得知文件的存在，文件对部分用户不可见
探知(Knowledge)：用户可以得知文件存在，但无法进行更多操作
执行(Execution)：用户可以将文件装入内存并执行，但无法进行复制、修改等工作
读(Reading)：用户可以读、复制文件，部分情况下可能包含可执行权限
添加(Appending)：用户可以追加文件内容，但不能修改、删除原有内容(如：审计系统)
更新(Updating)：用户可以追加、修改、删除原有数据，并创建、重写文件
修改保护机制(Changing Protection)：能够修改其他用户对文件的权限
删除(Deletion)：能删除文件

保护域（Protection Domain）

访问权（Access Right）用于表示进程对某个对象(可以是文件、设备等)执行操作的权利，表示形式为(对象名,权集)，如：(F1, {R/W})表示某进程对件 F1 具有读和写的权利
保护域：简称为域，是进程对一组对象访问权的集合，规定了进程能访问的对象和能执行的操作，进程只能在指定域内执行操作，如：一个保护域包含两个文件对象及其访问权限：F3[R]、F4[RWE]，则当进程工作于该域时，对文件F3是只读的，对文件F4则同时有读、写、执行权限
一个进程在不同运行阶段，可能受限于不同的域，即进程运行时能从一个保护域切换到另一个域

访问矩阵（Access Matrix）

访问矩阵（Access Matrix）是一种抽象的访问控制模型，用于描述系统访问控制的二维表，其结构：

行代表域(Di)
列代表对象(Qj)
矩阵元素定义了在域 Di 中执行的进程能对对象 Qj 所施加的操作（访问权集合）

域\对象	F1	F2	F3	打印机
D1	R	R/W	-	-
D2	R	-	R/E	使用
D3	-	W	R/W	-

上述访问矩阵表示：

在 D1 中运行的进程可以读 F1，读写 F2；
在 D2 中运行的进程可以读 F1、读和执行 F3，并使用打印机；
在 D3 中运行的进程可以写 F2、读写 F3。

访问矩阵的实现

在现代计算机中，OS需要管理的域和对象数量可能很大，如：系统中可能有 100 个域，10⁵个对象，此时访问矩阵中将会有 10⁸个表项，存储和访问该矩阵都需要较大开销。而且大多数情况下，用户进程需要访问的对象都很有限，此时访问矩阵中大多数项都是空项，或者说它是一个高度稀疏矩阵，因此实际系统不会简单地保存整个矩阵，而是通过以下方法划分

访问控制表ACL

访问控制表ACL（Access Control List）：按列（对象）划分访问矩阵，即以对象为中心维护权限，该方法会为每个对象建立一张访问控制表，记录哪些用户/域拥有哪些访问权限。当对象是文件时，访问控制表放于 FCB 或索引结点中。

用户权限表

访问权限表（Capability List）：按行（域）划分访问矩阵，即为每个用户/域维护一个列表，记录这个主体可以访问哪些对象，以及可以进行什么操作

实际系统中的应用

目前大多数系统同时采用访问控制表和访问权限表，但通常访问控制表ACL的权重更大：

会为每个对象(文件/设备)建立访问控制表，如：Linux以文件为单位记录owner、group、other用户的权限，此外还能通过setfacl 命令为某个用户/组单独添加权限
当用户第一次访问时检查访问控制表，再为进程建立访问权限
之后进程可直接利用访问权限快速验证访问合法性，如：用户通过open系统调用打开一个文件，首次通过ACL做权限检查后，会为进程建立权限缓存(相当于建立一个临时的用户权限表，多个用户权限不同)，之后用户的文件操作不再需要通过ACL进行权限检查

虚拟文件系统VFS

各类设备上的文件系统的种类极其丰富，如：硬盘上的 ext4、NTFS、XFS，移动设备的FAT32、exFAT，内存中的 procfs、sysfs，网络存储的 NFS 等等，这些文件系统的内部组织方式和磁盘数据结构完全不同，会带来以下问题：

类似作用的数据结构实现细节不同，比如：ext4使用inode、directory entry、extent等结构，NTFS使用MFT、Attribute、RunDATA等数据结构
每个文件系统都有自己的访问方式，应用程序必须针对每种文件系统写不同的代码，如：open()系统调用会有ext4_open()、ntfs_open()…
OS内核系统调用层需要直接耦合每一种文件系统的具体实现，内核膨胀

VFS的核心思想：在内核中引入一个抽象层，让用户程序和系统调用以统一的方式访问所有文件系统，而无需关心底层究竟是哪种具体实现。

VFS介绍

虚拟文件系统VFS(Virtual File System)：又称为 Virtual Filesystem Switch，是操作系统内核中的一个中间软件层，属于OS的一部分，负责定义一套通用的文件模型和数据结构，将用户的统一请求转发给底层具体的文件系统去执行，它位于以下二者之间：

上层：用户空间的系统调用接口（open、read、write、close 等）
下层：各种具体的文件系统实现（ext4、NTFS、procfs 等）

VFS的职能

提供统一的系统调用接口

VFS 向用户空间暴露标准的POSIX 文件操作接口，如：open/close、read/write等，用户程序只需要调用同一套接口，VFS中的函数功能指针负责将这些功能指向不同的文件系统实现，以此屏蔽底层差异。

统一描述文件系统资源

VFS 定义了四种关键抽象对象，用来统一描述所有文件系统的资源，每种具体的文件系统需要实现对应的操作函数表（如 struct inode_operations），并注册到 VFS：

超级块（Superblock）：描述一个已挂载文件系统的整体信息
索引节点（Inode）：描述一个具体文件/目录的元数据（权限、大小、时间戳等）
目录项（Dentry）：描述文件路径，映射文件和inode，用于路径查找和缓存
文件对象（File）：描述一个已打开的文件，维护读写位置、打开模式等状态

文件系统的注册、挂载与卸载

一个OS时运行时可以同时存在多个文件系统，此时需要通过以下操作把多个独立的文件系统组织到同一个目录命名空间中

注册：文件系统驱动初始化时，向 VFS 注册自己
挂载：将某设备上的文件系统挂载到全局目录树的某个挂载点，VFS 创建对应的 super_block
卸载：清理资源，断开与全局命名空间的关联

磁盘存储器管理

OS中的磁盘管理主要涉及两种磁盘空间的管理:

对非空闲磁盘块的管理(即对文件数据块的管理/文件的物理结构)
对空闲磁盘块的管理()

文件的物理结构

文件的物理结构与外存的组织方式有关，通常有以下组织方式：

连续分配：为每个文件分配一片连续的磁盘空间
链接分配：为文件分配离散的盘块，通过链接指针串成链表
索引分配：为文件分配离散的盘块，通过索引表记录文件各盘块的地址

连续组织方式(连续分配)

连续组织方式又称为连续分配，该方式要求为文件分配相邻接的盘块，这种组织方式保证了逻辑文件中的记录顺序和存储器中的盘块占用顺序是一致的，文件FCB或索引结点中文件物理地址字段存储的是该文件第一个盘块号和文件长度（以盘块为单位）。

优点：
- 顺序访问容易：找到首盘块号后可以逐个盘块往下读写
- 顺序访问速度快：尤其在机械硬盘中，磁头移动距离最少
缺点：
- 要求连续存储空间：与内存的动态分配一样，随着文件增删，磁盘存储空间会出现碎片化问题，需要通过紧凑等技术拼接出连续存储空间
- 需事先知道文件长度：文件大小需预先确定，文件大小的确定有时只能估算，估算不准会造成空间不足或浪费
- 不能灵活删除和插入文件内容：为保证文件逻辑空间与物理空间的有序性，插入和删除文件内容需要物理移动相邻的内容
- 不适用于文件动态增长的场景：文件大小动态增长时，如果提前预分配，又会导致大量存储空间长期空闲

链接组织方式(链接分配)

链接组织方式：又称为链接分配，为文件分配离散的盘块，通过链接指针将同属于一个文件的离散盘块链接成链表，该方式又可分为隐式链接和显式链接

隐式链接

隐式链接：文件FCB或索引结点中记录文件存放的起始块号和结束块号(或起始块号和占用块数)，且每个文件磁盘块都会保存指向下一个磁盘块的指针。

优点
- 方便文件动态增长
- 外存利用率高，不会有碎片问题
缺点：
- 只适合顺序访问，不支持随机访问，查找效率低
- 可靠性差，任何一个指针损坏都会导致后续盘块丢失

e.g.文件aaa的索引结点记录了该文件的数据在磁盘中起始块号为9，结束块号为8，磁盘块9末尾的指针指向磁盘块2，依次加载可以找到该文件的所有磁盘块

显式链接(FAT)

显式链接：把链接各磁盘块的指针显式存放在内存的一张链接表中，称为文件分配表FAT（File Allocatioin Table）。FAT存储了所有磁盘块的链接关系，整个磁盘仅设一张FAT表，它表项是按序排序的，表项指出了链接在当前物理块后的下一个物理块号(如下图，其中“物理块号”字段可以隐含)。系统开机后，OS会将FAT读入内存，并常驻内存，以提高查找速度

优点：查找在内存中进行，显著提高检索速度，大大减少磁盘访问次数

缺点：不支持高效的直接存取；整个FAT需常驻内存，需占用较大内存空间

e.g.文件 aaa 的FCB或索引结点记录了文件起始块号为 2，随后通过FAB表读出该文件依次存放在磁盘块：2-5-0-1；FAB项的值为-1代表该块是文件结束块号文件 bbb 类似

索引组织方式(索引分配)

链接方式解决了连续方式的问题，但引入了新问题：

不支持高效直接存取，要存取一个较大的文件，需要在FAT中顺序查找很多盘块号
磁盘容量大时，FAT常驻内存会占用大量内存空间

实际上，在打开某个文件时，完全没必要把整个FAT调入内存，只需要把该文件占用的盘块号调入内存即可，由此衍生出文件的索引组织方式(索引分配)。索引分配同样允许文件离散分配在各磁盘块中，这些磁盘块号会被统一记录在一个或多个磁盘块中，这些磁盘块又称为索引块

单级索引组织方式

单级索引组织方式：为每个文件分配一个索引块（表），把分配给该文件的所有盘块号集中记录在索引块中，目录项中只需填上指向该索引块的指针。

优点：支持随机访问；外存利用率高，不会有碎片问题
缺点：即便文件很小，只占用少量数据磁盘块，也需要分配一个索引磁盘块，小文件的磁盘利用率低

多级索引组织方式

为一个大文件分配磁盘空间时，其索引表也很大，一个索引块可能装不下，而需要多个索引块，如果使用链接指针将它们链接起来，则会存在链式数据结构带来的问题：访问效率低。

多级索引组织方式：为这些索引块再建立一级索引块，称为第一级索引，将存放了索引表的索引块1、索引块2….等索引块的盘块号填入一级索引表中(类似于多久页表)，形成两级索引。如果文件非常大，还可以使用三级、四级索引。

优点：大大加快了大型文件的查找速度
缺点：随着索引级数增多，磁盘启动次数也增多

e.g.假设一个磁盘块大小为 4KB，盘块号占用4个字节，则一个索引块可以存放1024个盘块号 1.采用单级索引时，所允许的最大文件长度是：4KB × 1024=4MB 2.采用二级索引时，最多可存放盘块号总数为：1024 × 1024，所允许的最大文件长度是：4KB × 1024 × 1024 = 4GB

增量式索引组织方式

增量式索引组织方式：又称为混合索引，为全面照顾小、中、大、超大型文件，采用多种索引分配方式结合的方式，即一个文件的顶级索引表，同时包含直接地址(直接指向数据块，用于小文件，读盘次数少)、一级间接索引(指向一个索引磁盘块，存储有中大型文件的所有数据磁盘块号)、两级间接索引(指向两层索引表，用于超大型文件)。存储文件内容时，首先存入直接地址所指向的数据块中，超出部分依次存入一级间接索引、二级间接索引所管理的磁盘块中。增量式索引组织方式被广泛用于Windows的NTFS文件系统和Linux的ext系列文件系统。

e.g.在ext2/ext3文件系统中，inode中设有15个地址项，假设块大小为4KB，一个块地址占用4B： + i_block[0]~i_block[11]：12个直接块指针，直接指向数据块 + i_block[12]：一级间接指针，指向另一个索引块，索引块中才是指向数据块的指针 + i_block[13]：二级间接指针 + i_block[14]：三级间接指针 1. 直接块地址 12个直接指针，能寻址 12 × 4KB = 48KB 磁盘空间 2. 一级间接地址一个4KB磁盘块可以存储1024个块地址，由此一级间接地址能寻址： 1024 × 4KB = 4MB 磁盘空间 3. 二级间接地址 inode中的二级地址指向了一个磁盘块，该磁盘块中的盘块又指向1024个磁盘块，总共有：1024 × 1024 个索引由此能寻址：1024 × 1024 × 4KB = 4GB 磁盘空间 4. 三级间接地址同理，三级间接能寻址： 1024 × 1024 × 1024 × 4KB = 4TB 因此，理论上inode中记录的地址信息，支持单个文件最大大小为：48KB+4MB+4GB+4TB，但该值还受到inode中用于表示文件大小的位数限制

文件存储空间的管理

文件存储空间管理的核心任务是：记录哪些盘块已被使用、哪些盘块空闲，并提供盘块的分配与回收操作，以下是四种主要管理方法。

空闲表法

空闲表法属于连续分配方式，系统为外存上的所有空闲区建立一张空闲表。每个空闲区对应一个表项，包含表项序号、该空闲区的第一个盘块号、该区的空闲盘块数，所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表

该分配方法与内存的动态分区分配类似，可采用首次适应算法、循环首次适应算法等，回收时需将释放区与相邻的空闲区合并。该分配方式的特点是：分配速度较高，可减少访问磁盘的I/O频率；虽然连续分配方式在现代操作系统中较少采用，但在管理交换空间等领域仍占一席之地

空闲链表法

将磁盘上的所有空闲空间链接成链，分为两种形式：

空闲盘块链：以盘块为单位，将所有空闲盘块链接成一条链，分配空闲磁盘块时从链首依次摘下适当数目的空闲盘块分配给用户，回收时将释放的盘块依次插入链尾。优点是分配和回收单个盘块的过程非常简单；缺点是为文件分配多个盘块时，可能需要重复操作多次
空闲盘区链：：以盘区(若干盘块)为单位，将所有空闲盘区链接成一条链。每个盘区除含指向下一个盘区的指针外，还包含本盘区大小的信息。其分配方式与内存动态分区分配类似，通常采用首次适应算法，回收时需要将回收区与相邻的空闲盘区合并，为提高检索速度，可在内存中为空闲盘区建立一张显式链表。优点是分配和回收效率高，一次性能分配/回收多个盘块；空闲盘区链短；缺点是分配与回收过程复杂，涉及多个盘块/盘区的合并判断。

位示图法

位示图利用一位二进制位来表示磁盘中一个盘块的使用情况，如：值为0表示盘块空闲，值为1表示盘块已经占用(或者反过来)，磁盘上的所有盘块都有一个二进制位与之对应，所有位构成的集合即为位示图，通常用 m × n 个位数构成位示图，并描述为二维数组 map[m, n]，使 m × n 等于磁盘总块数。

盘块分配：

顺序扫描位视图，从中找到一个或一组值为0(空闲)的二进制位
计算出该二进制位所对应的盘块号：
- 若盘块号从 0 开始，i、j从1开始，位示图中第 i 行第 j 列对应的盘块号 b 为：b = ( i - 1 )n + j - 1(n代表每行的位数)。如：n=16，第1行第7列二进制位对应盘块：(1-1)×16+7-1=6
- 计算时要查看 i、j、b 分别从0开始还是从1开始计算，以调整该式子
修改位图，令map[i,j]=1

盘块回收：

将回收盘块号换算为位图中的行号和列号：
- 行号：i = (取整)[b/n] + 1
- 列号：j = b%n + 1
修改位图，令map[i,j]=0

成组链接法

成组链接法（Grouped Free Block Linking）曾是UNIX系统中采用的文件存储空间管理方法。它结合了空闲表和空闲链表的优点，适用于大型文件系统。成组链接法不是让每个空闲块只保存下一个空闲块的地址，而是让一个空闲块一次记录一组空闲块的地址，以解决空闲表或空闲链表太长的问题，减少访问磁盘以获取空闲块信息的次数。

成组链接法的工作方式

将所有空闲盘块分为若干个组，如：每100个盘块为一组，并将这些盘块号写入一个磁盘块中，所写入的最后一个盘块号是存储了下一组空闲盘号的磁盘块号(上图中红色标记的盘块号)
内存中以栈形式管理、分配空闲盘块，作为临界资源，栈会被上锁，一次只允许一个进程访问
上图中栈顶位于底部，栈顶是201，其指针号为99(指针范围为0-99)，因此栈顶指针也给出了当前组所剩余空闲盘数量
分配：当需要为文件分配空闲磁盘块时，从栈顶依次取出盘块号进行分配，如：依次取出201-202…，当取到磁盘块300时(栈指针指向0)，盘块300存储了下一组空闲磁盘块号，因此OS从300读入一组(100个)新的空闲盘块号
回收：当有磁盘块被释放，该盘块号会被添加到栈顶，如果当前栈长度已经达到100，则将现有栈中的100个盘块号写入新回收的盘块中，并将该盘块号作为新栈底

廉价磁盘冗余阵列RAID

廉价磁盘冗余阵列RAID(Redundant Array of Inexpensive Disks)：是将多个物理磁盘组合成一个逻辑单元，以提升性能、容量或数据冗余能力的技术，后被改名为独立磁盘冗余阵列(Redundant Array of Independent Disks)，该系统利用一台磁盘阵列控制器来统一管理和控制几十台磁盘驱动器，组成一个大型磁盘系统，以大幅增加磁盘容量，极大提高磁盘I/O速度和磁盘可靠性，其特点包括：

性能提升：数据分散到多块磁盘并行读写(并行交叉存取)
容量扩展：多块磁盘空间合并为一个大逻辑卷
数据冗余：通过镜像或校验码防止单点故障
成本优化：用多块廉价磁盘替代昂贵的大容量磁盘

RAID分级

RAID 0：仅提供交叉并行存取，以实现高速I/O，但无冗余校验功能，可靠性不高，用于临时数据、缓存、视频编辑等对性能要求高但可容忍丢失的场景
RAID 1：具有磁盘镜像功能，如：磁盘阵列中有8个盘时，4个为数据盘，4个为镜像盘。缺点是磁盘利用率只有50%，以磁盘容量为代价换取可靠性，用于系统盘、关键数据存储、数据库日志
RAID 3：具有并行传输能力，并使用1台奇偶校验盘完成数据校验，如：使用6个数据盘，1个校验盘，磁盘利用率为6/7
RAID 5：使用分布式奇偶校验，数据条带化分布，校验信息均匀分散(如：螺旋散步)在所有磁盘，而没有专用的校验盘，用于文件服务器、一般企业存储（读多写少）
RAID 6：在 RAID 5 基础上增加第二组校验码（通常用 Reed-Solomon 或 P+Q 算法），用于大容量磁盘阵列、归档存储、对可靠性要求极高的场景

文件系统实例

文件管理和磁盘管理在文件系统中的应用实例

Windows的文件系统

FAT技术

FAT（File Allocation Table，文件分配表）是基于显式链接分配方式实现的文件管理技术，即利用文件分配表FAT记录每个文件中所有盘块的链接，每个文件的FCB中只需记录其第一个盘块号，FAT表会依次指出后续盘块，该技术广泛用于微软公司早期的MS-DOS、Windows 9x系统。出于安全考虑，在每个分区中，通常保存着两份相同的FAT表（FAT1和FAT2），其中一份作为备份，防止因FAT损坏导致整个文件数据丢失

微软在FAT文件系统中引入了卷（Volume）的概念，卷是一个可以被文件系统独立格式化和使用的逻辑单元，一个物理磁盘可以被划分为多个卷，每个卷有各自独立的文件系统结构，卷中包含文件系统信息、文件和空闲空间，并有单独区域存放目录、FAT表、独立的逻辑驱动器号(如C:、D:、E:、F:)等信息。在常见配置中，一个分区对应一个卷，但分区(Partition)是对物理磁盘地址空间的划分，卷是操作系统用于独立管理和挂载的逻辑存储单元，二者并不等价。现代OS中，一个物理磁盘可以划分为多个卷，一个卷也可以由多个物理磁盘组成。此外，盘符(如C:)是Windows给这个卷提供的一个访问路径，卷可以没有盘符，而是直接挂载在诸如C:\Users\Admin\Data\这样的路径下

FAT12

在MS-DOS中，最早使用的是12位的FAT12，早期的FAT12以盘块为基本分配单位，对于一个1.2MB的软盘，每个盘块大小为512B，每个FAT共有2.4K个表项，每个表项占12位，因此FAT表占用3.6KB。

在以盘块为分配单位的FAT12中，由于每个FAT表项为12位，因此FAT表最多允许有2¹²(4096)个表项，每个盘块(扇区)大小为512B，则每个卷最大大小为：4096 × 512B = 2MB，早期的MBR分区表最多支持4个主分区，因此早期MBR+FAT的组合，支持的最大磁盘容量为8MB

簇

为了使文件系统支持更大空间的磁盘，微软引入了簇(cluster)的概念，簇是一组相邻的扇区，FAT文件系统将其视为一个虚拟扇区，在进行盘块分配时，以簇为基本单位，簇大小通常是2n个盘块，常见大小为：512B(一个扇区)、1KB(两个扇区)、2KB(四个扇区)、4KB(八个扇区)。当一个簇包含了8个扇区时，FAT12支持的磁盘最大容量可达64MB。

以簇为基本分配单位的FAT12文件系统的优点是能支持更大磁盘空间，且相较于以盘块为分配单位，簇可以减少FAT的表项，以减少访问FAT表的开销，缺点是会出现簇内碎片。此外，FAT12的显著缺点是只支持短文件名。

FAT16

FAT16将FAT表项位数增至16位，因此最大表项增至2¹⁶(65536)个，此外每个簇可以包含的盘块数最大为64，因此FAT16可以管理的最大卷空间为：65536 × 64 × 512 = 2048MB。由于一个簇的大小可以高达128KB，因此会带来巨大的簇内碎片，对于一个4GB的硬盘，可能会浪费10%-20%的空间。

FAT32

FAT32将表项位数增大为32位，每个簇固定为4KB(8个盘块)，因此FAT32可以管理的最大卷空间为：4KB × 2³² = 2TB，此外FAT32支持长文件名。

FAT32的不足：

由于FAT表的扩大，FAT32文件系统的运行速度比FAT16慢
FAT32有最小管理空间限制，它不支持小于512MB的分区
FAT32中用于表示文件大小的字段占用32位，因此FAT32的单个文件大小不能超过4GB-1字节

exFAT

exFAT（Extended File Allocation Table）是FAT32的后继者，其设计目标之一就是突破FAT32的4 GB单文件限制，以支持大型文件。exFAT中用于表示文件大小的字段扩展为64位，并允许很大的簇，由此提供对大文件和大存储设备的支持，被广泛用于Windows Vista SP1、Windows 7、U 盘、SD 卡以及大容量移动存储设备。

exFAT的另一个重要变化是采用位图表示一个簇是否已经被分配，传统 FAT12/16/32 中，FAT 本身既承担簇链管理，也承担空闲簇状态管理，而exFAT 引入分配位图(Allocation Bitmap)来标识簇的分配情况。

NTFS

NTFS（New Technology File System）是Windows NT内核及后续Windows系统（如2000/XP/Vista/10/11）专用的主流文件系统，引入了许多高级特性：

使用64位磁盘地址，但实际只使用其中的48位用于簇寻址，最大簇大小为64KB，因此理论最大卷容量为2⁴⁸ × 64KB =16 EB(约1600万TB)
文件大小字段占用64位，支持的单个文件大小上限与卷大小上限相同(1600万TB级别)
支持长文件名，单个文件名限制在255个字符以内，前路径名限制在32767个字符内
具备容错能力，数据恢复能力，在系统出现故障或差错时，仍能保证系统正常运行
提供文件加密、压缩等功能

磁盘组织

NTFS文件系统依旧以簇为磁盘分配和回收的基本单位，卷上簇大小称为卷因子，卷因子是在磁盘格式化时确定的，大小为物理扇区的整数倍，可以为512B、1KB…64KB。对于小于512MB的磁盘，默认簇大小为512B，1GB磁盘默认簇为1KB，2GB以上的磁盘，大多数情况下，默认簇大小为4KB，同一卷内簇大小固定，不同的卷可以指定不同的簇大小。

MFT

NTFS不再使用FAT表(显式链接组织方式)管理记录文件的磁盘块关系，而是改为使用MFT记录文件所属的盘块(增量式索引组织方式)

主控文件表MFT（Master File Table）是NTFS的核心数据结构，卷上每个文件/目录至少对应 1 条 MFT记录（大小固定为1KB），这些MFT记录又称为文件的元数据(metadata)或文件控制字，记录由若干属性（Attribute）组成，分为：

常驻属性（Resident）：数据直接存放在 1KB 的 MFT 记录内
非常驻属性（Non-Resident）：数据存放到外部簇，MFT 中只存寻址信息
这里的常驻并非指常驻内存，而是常驻MFT记录内

MFT表中，一个典型文件的 MFT 记录中可能包含：

文件名 $FILE_NAME
文件类型和基本属性
安全描述符等属性
文件数据 $DATA
其他与文件相关的属性

文件组织

MFT记录中，DATA属性负责描述文件内容的存储位置，对于小文件，$DATA本身甚至可以直接保存文件内容，对于大文件，$DATA 则保存描述文件数据块位置的信息，即如果文件很小，文件内容可以直接存在MFT表的DATA属性中(该类数据即为resident，常驻数据)，这可以减少磁盘访问次数，不需要再去寻找文件的数据簇，显著提高对小文件的存取效率。对于大文件，DATA不再保存数据，而是保存描述“文件逻辑数据块位于磁盘哪里”的Runlist(该数据为Non-resident，非常驻属性，MFT只给出寻址信息)，Runlist中包含两种地址：

虚拟簇号VCN（Virtual Cluster Number）：以文件为单位，将属于该文件的簇按顺序编号，VCN 与这些簇在磁盘上的实际位置没有直接关系
逻辑簇号LCN（Logical Cluster Number）：以卷为单位，将整个卷中所有簇按顺序编号

Runlist

当所操作的文件是大文件时，MFT记录中DATA属性存储的是Runlist/RunDATA，它负责记录文件的 VCN 区间与磁盘 LCN 区间之间的映射关系。实际上，虽然一般情况下所分配的簇是离散的，但也可能分配到一些连续的簇，因此在进行地址映射时，会将连续的簇合并为一个run(数据运行)，而不是为每一个簇都建立一个单独的映射，这样可以极大地压缩映射记录的数量。

e.g.一个文件大小为32KB，簇大小为4KB，需要8个簇，则有：文件逻辑结构：VCN 0 - VCN 7 实际分配到的磁盘位置为： VCN 0 → LCN 1000 VCN 1 → LCN 1001 VCN 2 → LCN 1002 VCN 3 → LCN 5000 VCN 4 → LCN 5001 VCN 5 → LCN 8000 VCN 6 → LCN 8001 VCN 7 → LCN 8002 上述映射关系可以压缩为三个 runs： Run 1：VCN 0～2 → LCN 1000～1002 Run 2：VCN 3～4 → LCN 5000～5001 Run 3：VCN 5～7 → LCN 8000～8002 Runlist会记录VCN的区间，以及对于的LCN 起始位置： Run 1：length=3，LCN = 1000 Run 2：length=2，LCN = 5000 Run 3：length=3，LCN = 8000 1. 当需要读取文件的某个偏移量时，如：读取VCN　6 时该簇属于Run 3，VCN偏移值为1，则可以计算出LCN=8000+1=8001 由此获得了该逻辑块对应的物理块号 2. 当文件内容发生变更，如：向文件中间插内容则原有文件内容的LCN号不需要发生改变，只要简单修改VCN到LCN的映射，即只需要修改MFT的DATA属性即可

Linux文件系统

ext4

一个简单的ext4文件系统分区布局如下

超级块（Superblock）：包含有关整个文件系统的信息：文件系统类型、卷的大小、块大小、inode数量、空闲空间等，是文件系统挂载和管理的基础
i-bmap：i-bmap（inode Bitmap）：inode 位图，以位图方式记录inode的分配、空闲情况，用于快速查找空闲 inode，以便创建新文件或目录
d-bmap（Data Block Bitmap）：数据块位图，以位图方式记录磁盘块的分配、空闲情况，用于快速查找空闲数据块，以便为文件分配存储空间
inode 表（inode Table）：集中存放文件和目录的 inode。每个inode保存对应文件的元数据以及文件数据块的定位信息，但通常不保存文件名，文件名由目录中的目录项负责管理。当要读取32号的inode时，会通过： inode表起始地址 + 32 × inode的大小计算出inode块的字节地址

文件组织

在ext4中，inode直接负责描述文件及其数据位置，ext4不再采用 ext2/ext3 中 inode 的直接地址、一级间接地址、二级间接地址和三级间接地址的多级索引设计，而是转向以extent（区段）为核心组织文件数据。

extent的组织思想与 NTFS 文件系统中的Run（Data Run）类似，都是将连续的逻辑数据块和连续的存储块组织为一个区段，以减少逐块记录地址所产生的开销。但 ext4 不使用 NTFS 中的 VCN 和 LCN 术语，而是使用文件内逻辑块号和文件系统块号描述数据的位置：

逻辑块号（Logical Block）：以文件为单位，将属于该文件的数据块按顺序编号，反映数据块在文件内的逻辑位置
文件系统块号（Filesystem Block）：以文件系统卷为单位，将卷中的数据块按顺序编号，用于表示数据块在该文件系统中的存储位置

e.g.在ext4文件系统中，一个文件大小为32KB，块大小为4KB，需要8个块，则有：文件逻辑结构：logical block 0 - 7 实际分配到的磁盘位置为： logical block 0 → physical block 1000 logical block 1 → physical block 1001 logical block 2 → physical block 1002 logical block 3 → physical block 5000 logical block 4 → physical block 5001 logical block 5 → physical block 8000 logical block 6 → physical block 8001 logical block 7 → physical block 8002 上述映射关系可以压缩为三个 extent： Extent #1 logical start = 0 length = 3 physical start = 1000 Extent #2 logical start = 3 length = 2 physical start = 5000 Extent #3 logical start = 5 length = 3 physical start = 8000 当需要读取文件的某个偏移量时，如：读取逻辑块　6 时该块属于extent #3，extent内逻辑偏移值为1，则可以计算出物理块号=8000+1=8001

z z z z z