（三）外存管理

1. 磁盘

1.1. 磁盘的结构

• 磁盘可包含一个或多个盘片；

• 每个盘片有一个或两个存储面；

• 每个存储面上有若干个磁道，磁道之间留有必要的间隙；

• 扇区：将每个磁道等分为多个区域，每个区域称为扇区；

  • 扇区是磁道层次中最小的单位；

  • 扇区大小（命题）一般为 512B；

  • 扇区有独立编址；

• 柱面：若干个盘面的集合，如图中的个盘面 0 到 9 属于一个柱面；

• 簇：将多个扇区组成一个整体，称为簇。是数据分配的基本单位；

1.2. 分区和格式化

• 初始化磁盘和 OS 的过程

  • 物理格式化；

  • 分区；

  • 逻辑格式化；

  • 创建文件系统（NTFS，ext4，exFAT 等）；

  • 安装 OS，应用程序等；

1.3. 磁盘访问时间

• 磁盘在工作时以恒定速率高速旋转；

• 磁盘访问过程

  • 寻道：读写时，磁头要先移动到目标磁道上；

  • 等待（旋转延时）：等待目标扇区旋转到磁头下，才能开始读写；

  • 读写磁盘；

• 寻道时间 $T_s$：$T_s=m\times n+s$；

  • $m$：磁头移过一条磁道的时间，为常数。一般和磁盘驱动器有关；

  • $n$：需要移动的磁道数；

  • $s$：启动磁臂的时间；

• 旋转延时 $T_r$：指定扇区转到磁头下面需要的时间；

  • 一般约定：平均等待时间 $T_r=\frac{1}{2}T$，$T$ 为磁盘转一圈所需时间；

• 传输时间 $T_t$：将数据写入磁盘或从中读出数据所需时间；

  • $T_t=b/rN$，$b$ 为要读写的字节数，$r$ 为转速，$N$ 为一条磁道上的字节数；

1.4. 磁盘调度算法

• 先来先服务 FCFS

  • 最简单的调度算法；

  • 根据进程请求磁盘的先后次序进行调度；

• 最短寻道时间优先 SSTF

  • 每次都选择目标磁道和当前磁道距离最近的进程优先调度；

  • 不能保证全局平均寻道时间最短，但一般优于 FCFS；

• 扫描算法 SCAN

  • SCAN 算法要求磁头像电梯一样，由内到外移动和由外到内移动，并依次处理移动方向上含有目标磁道的进程请求，直到移动方向上没有其他请求，才反转移动方向；

  • SCAN 算法可以防止 SSTF 算法可能出现的进程饥饿问题（较远距离磁道的请求长时间得不到调度）

• 循环扫描算法 CSCAN

  • 规定磁头只能单向移动（由内到外或由外到内）；

  • 到达边界或移动方向上没有请求时，立即回到起点重新移动；

• N 步扫描 NStepSCAN

  • 磁臂粘着：指因为一个或几个进程高频访问同一磁道，导致磁臂长时间停留在此磁道附近；

    • 在 SSTF，SCAN，CSCAN 算法中都有可能出现；

    • 会使得间歇出现的其他磁道请求的移动时间大大增加，降低寻道效率；

  • NStepSCAN 算法

    • 将所有磁盘请求分为 N 个子队列；

    • 一个子队列中，按照 SCAN 算法处理每个请求；

    • 不同子队列，按照 FCFS 处理；

    • 正在处理某个队列时，若出现新的请求，则将其放入其他队列；

  • NStepSCAN 使得新请求被延迟处理，可有效防止磁臂粘着问题；

• FSCAN

  • 简化版的 NStepSCAN 算法；

  • 只分两个子队列：正在处理的请求队列，新加入的请求队列；

  • 新请求被延迟到下一次扫描处理；

2. 固态硬盘

2.1. 概述

• 固态硬盘源自闪存（Flash，多用于 U 盘），是半导体制成；

• 机械结构相对较少，随机读取快；

2.2. 读写特性

• 随机读取速度很快，但随机写入较慢；

  • 页的擦除需要较长的时间（ms 量级），远高于页的访问时间；

  • 若试图写入一个已经包含数据的页，那么必须将该页数据复制到新页，才能写入；

• 磨损均衡机制

  • 固态硬盘的每个存储单元都有擦写次数限制（寿命），超过之后该单元将不可用；

  • 磨损均衡：用于平衡固态硬盘内各个区块闪存颗粒的使用程度，延长闪存颗粒的平均寿命；