磁盘基本划分

目录区包含文件目录，空闲表，位示图，超级块等用于文件管理的信息

空闲存储空间管理

操作系统需要跟踪磁盘上的可用空间，确保高效分配和回收操作系统需要跟踪磁盘上的可用空间，确保高效分配和回收。常用方法如下：

1. 空闲表法
   与内存分配的动态分配算法如出一辙，因此不再赘述。
   反正来来去去就是首次适应，最佳适应等策略，回收时注意合并压缩。

2. 空闲链表法
   原理：将所有空闲块通过指针或索引链接成一个链表，记录起始块和块数。
   优点：实现简单，适合动态分配。
   缺点：链表操作（遍历、拆分、合并）效率低，不适合大规模存储。

链表结构为0=>4=5=>6=>7=>......=>12=>14=>17=>......

3. 位图法（Bit Map）
   原理：用一个二进制位（Bit）对应磁盘上的一个物理块，0表示空闲，1表示已占用。
   优点：空间占用小，查询和分配速度块(位运算)，适合大容量，比如ext4文件系统。
   缺点：分配连续空间时需扫描多个位，可能效率较低。
   

4. 成组链接法
   原理:将空闲块分组，每组记录下一组的快号，最后一组指向NULL或-1。
   优点：结合位图和链表的优势，兼顾空间效率和分配速度，常用于高效文件系统。
   缺点：实现复杂。

空闲法，空闲链表，位视图法，成组链接法本质上是数据结构的翻来覆去。数组=>链表=>位图=>混合使用。
注意一点，这一节讲的是操作系统如何跟踪磁盘可用空间(空闲管理)，上一节的物理结构分配是操作系统如何占用物理空间(分配策略)。两者不要搞混了。

典型文件系统实现

1. Linux ext4
   采用成组链接法管理空闲块，inode 索引分配（支持三级索引），位图记录块状态。
2. Windows NTFS
   使用 B + 树管理元数据，主文件表（MFT）记录文件属性和索引，空闲空间通过位图和链表结合管理。
3. FAT32
   显式链接分配，通过 FAT 表记录块链接，适合简单存储设备（如 U 盘）。

文件的基本操作

1. 创建文件（created系统调用）
2. 删除文件(delete系统调用)
   在windows系统中，我们删除某个文件。会提示“暂时无法删除文件”。就是因为计数器还未归零
3. 读文件(read系统调用)
   根据读指针，读入数据量，内存位置，讲文件从外存写入内存
4. 写文件(write系统调用)
   根据写指针，写入数据量，内存位置，讲文件从内存写入外存
5. 打开文件(open系统调用)
   将FCB信息负责到系统的打开文件表中，再复制给需要打开的进程。
   进程的打开文件表特有的属性：读写指针，访问权限。
   系统的打开文件表特有的属性：打开计数器
6. 关闭文件(close系统调用)
   将进程的打开文件表中删除相应的表项
   回收分配给该文件的内存空间
   系统打开文件表，计数器-1。若count为0，则删除相应表项。

系统索引号，也被称为文件描述符(fd)

番外：磁盘

磁盘是计算机中常用的块存储设备，通过磁性介质持久化存储数据。

物理组成

1. 盘片（Platter）
   圆形薄片，表面涂有磁性材料，一般由多个盘片堆叠组成（如 2~5 片），每个盘片有上、下两个盘面（Side）。
2. 读写头（Head）
   每个盘面对应一个读写头，悬浮在盘片上方（不接触盘面），通过磁性感应读取数据或改变磁性写入数据。
3. 主轴/转轴（Spindle）
   盘片围绕主轴高速旋转（转速如 5400 转 / 分钟、7200 转 / 分钟）。
4. 磁盘臂/机械臂杆（Arm）
   带动读写头在盘片表面径向移动，定位目标磁道。
   

磁道，扇区

每个盘片被划分为一个个的磁道，每个磁道又划分为一个个扇区。

盘面，柱面

磁盘是由多个盘片叠起来,所有盘面中的垂直位置就叫柱面

因此磁盘的物理地址，可以由柱面号=>盘面号=>扇区号组成。

1. 根据"柱面号"移动磁臂，让磁头指向指定柱面
2. 激活指定盘面对应的磁头
3. 磁盘在旋转过中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读写。

磁盘调度

一次磁盘读写操作需要的时间如下：

1. 寻道时间
   启动磁臂(2ms)+移动磁头（0.2ms*n）。
2. 延迟时间
   通过旋转磁盘，使磁头定位到目标扇区所需要的时间。也就是转动磁盘所消耗的时间。
3. 传输时间
   从磁盘读/写数据所经历的时间。

从上面可以看出，延迟时间与传输时间。受限于物理限制，是没办法在软件层面上优化的。
只有寻道时间，移动磁头的过程。我们可以通过不同的调度算法，缩短磁头移动的路径。
寻道时间占主导（约 60%~80%）。当多个 I/O 请求同时等待处理时，通过合理安排请求顺序，可显著减少平均寻道时间，提升磁盘整体性能。

1. 先来先服务（First-Come, First-Served, FCFS）
   与软件层面的FCFS算法不同，比如内存是支持随机访问的，因此时间复杂度为O(1)。但硬件层面的FCFS需要考虑移动磁头的时间。
   原理：按照请求顺序，不考虑当前磁头位置
   优点：公平性好，实现简单
   缺点：磁头来回移动，平均寻址时间长，效率低

磁头当前位置：100
请求序列：98, 183, 37, 122, 14, 124, 65, 67
寻道顺序：100→98→183→37→122→14→124→65→67
总寻道距离：|100-98| + |98-183| + … + |65-67| = 2 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 597

2. 最短寻道时间优先（Shortest Seek Time First, SSTF）
   原理：选择离当前磁头位置最近未处理，优先处理。
   优点：减少平均寻道时间
   缺点：可能会导致饥饿，远方的扇区可能一直得不到调度。

初始位置 100，最近请求是 98 或 122（距离 2 或 22），选择 98；
处理后磁头在 98，最近请求是 67 或 65（距离 31 或 33），但实际更优为 122（距离 24）？需注意：SSTF 是找当前磁头位置的最近，而非已处理后的最近。
正确顺序：100→98（距离 2）→122（距离 24）→124（距离 2）→183（距离 59）→67（距离 116）→65（距离 2）→37（距离 28）→14（距离 23）
总寻道距离：2+24+2+59+116+2+28+23 = 256（比 FCFS 减少 56%）

3. 扫描算法（SCAN，电梯算法）
   原理：磁头在一个方向上移动的时候，沿途处理所有路径的请求。到达一端后反向移动。处理另一个方向的请求。
   类似电梯运行，一上一下，每一层都都会经过，有停靠请求就停，否则只经过。
   优点：减少来回移动，公平性优于SSTF。
   缺点：边缘的请求延迟较大，因为要等磁头移动过来。

（假设磁头当前在 100，方向 “向外”，最大磁道 200，请求序列同上）：
向外方向请求：122, 124, 183
处理顺序：100→122→124→183（到达外边缘 200 前），然后反向向内；
向内方向请求：98, 67, 65, 37, 14
总寻道距离：(122-100)+(124-122)+(183-124)+(183-98)+(98-67)+(67-65)+(65-37)+(37-14) = 22+2+59+85+31+2+28+23 = 252

4. 循环扫描算法（Circular SCAN, CSCAN）
   原理:与Scan类似，但磁头到达边缘后。直接跳回0磁道。不处理返回途中的请求，如同跳楼，先坐电梯升到顶楼，然后跳下来。
   优点：适合均匀分布访问的场景，避免Scan在反向时"空扫描"
   缺点：平均寻道时间高于SCAN，但公平性更好

示例（同上场景，假设高端 200，低端 0，方向向外）：
向外处理：122→124→183→200（假设到达高端），然后跳回 0，处理向内方向未完成的请求（98, 67, 65, 37, 14）。
总寻道距离需计算跳回开销，但实际中跳回时间不计入寻道（因不访问数据），主要处理单向请求。
优点：适合需要均匀分布访问的场景（如磁盘阵列），避免 SCAN 在反向时的 “空扫”。
缺点：平均寻道时间略高于 SCAN，但公平性更好。

5. Look算法
   原理：在SCAN/CSCAN算法中，只有到达边缘的磁道时，才改变磁头移动方向。如果磁头运行到一半时，发现后面已经没有请求了，这就造成了浪费。因此，Look算法的核心是边移动边观察，如果在移动方向上没有请求，就立即改变磁头方向。

磁盘初始化

磁盘初始化分配为三个步骤：

1. 低级格式化
   将磁盘的各个磁道划分为扇区，一个扇区通常分为头，数据区域，尾。三个部分。各个扇区头尾衔接形成链表。
   管理扇区的所需要的各种数据结构一般放在头中，尾一般存放下一个扇区的地址。
2. 磁盘分区
   每个分区由若干个柱面组成，就是我们熟悉的C盘，D盘，E盘。
3. 逻辑格式化
   创建文件系统，包括根目录，位示图，空闲分区表等。

初始化完成后，由BIOS装入初始化程序，找到硬盘中的MBR引导块。

磁盘坏块的处理

1. 软件层面
   可以在逻辑格式化时，对磁盘进行坏块检查。标明哪些扇区是坏扇区。并告诉操作系统（FAT表）。逻辑上对它屏蔽。
2. 硬件层面
   由磁盘内部控制器，维护一个坏块链条，在低级格式化时，就标记出坏块，并屏蔽。

固态硬盘

机械硬盘受限于物理限制，已经发展到了极限。尤其在随机读取方面，更是到达了瓶颈。
固态硬盘（Solid State Drive, SSD）是基于闪存芯片的存储设备，彻底摒弃了传统机械硬盘（HDD）的旋转盘片和磁头寻道结构，通过电信号直接读写数据，实现了存储性能的质的飞跃。

页（Page）：最小读写单位（4KB~16KB），等同于磁盘扇区
块（Block）：最小擦除单位（64~256 页），等同于磁盘磁道。