Mass story

Mass storage

磁盘结构

  • 磁道：能被磁头访问的一组同心圆
  • 扇区：磁道上的区域，数据存放的基本单位
  • 柱面：所有盘片同一磁头下的磁道集合

对磁道的划分有两种方法：

  1. 以同心圆的方式划分：磁盘要使用恒定角速度旋转

  1. 以磁道密度相等划分：磁盘转动的线速度相等，即角速度不断改变

磁盘格式化

  • 低级格式化（Low-level formatting

    • physical formatting
    • 为每个扇区使用特殊的数据结构进行填充，包括一个头 部、数据区域和一个尾部。
    • 头部和尾部包含一些控制信息，如扇区号、ECC码(校验码)等。
      低级格式化是与操作系统无关的格式化，属于物理级别的格式化，一个磁盘建立柱面划分扇区的过程就是在低级格式化中完成的，当大家买到一块硬盘时，低级格式化就已经完成了。当磁道损坏较高时应该进行低级格式化

  • 高级格式化（High-level formatting）

    • Logical formatting

    • 构建文件系统，在磁盘上初始化文件系统数据结构，如空 闲和 已分配空间表、一个空目录等。

      高级格式化一般是和操作系统有关的
      如windows电脑一般采用 NTFS 进行格式化 MAC系统一般采用EXT4 进行格式化

磁盘性能指标

  • 查找一个物理块的顺序：柱面号、磁头号和扇区号
    • 寻道时间Ts：将磁头定位到正确磁道(柱面)上所花的时 间，与盘片直径和传动臂速度相关，平均20ms。
    • 旋转延迟Tr：所查找的扇区转到磁头下所用的时间，与 磁盘的旋转速度有关，一个10,000 r/m的磁盘平均旋转延 迟为3ms。
    • 传送时间T：传送扇区内的数据的时间，同样取决于磁盘 的旋转速度，T = b/(rN) (b为要传送的字节数，N为一个 磁道中的字节数，r为转速)
  • 总的平均存取时间 Ta = Ts + Tr + T

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
条件假设: 
平均寻道时间为 5 ms，平均旋转延迟为 4 ms 
传输速率为 4 MByte/s，扇区大小是 1 KByte

如果随机访问一个扇区 
Ta = 5ms + 4ms + 0.25ms ≈ 10 ms 
总的存取速率为100 KByte/sec

如果要访问的扇区在同一个柱面 
Ta = 4ms + 0.25ms ≈ 5 ms → 200 KByte/sec 

如果下一个要访问的扇区正好和上次访问的扇区相邻 
Ta = 0.25ms → 4 MByte/sec
可以看出寻道时间和旋转延时相对于数据访问是要大得多

磁盘调度

disk io request

  • Whenever a process needs I/O to or from(读或书) the disk, it issues(发出) a system call to the operating system. The request specifies(指定) several(一些) pieces of information:
    • Whether this operation(操作) is input or output
    • What the disk address for the transfer(转移) is
    • What the memory address for the transfer is
    • What the number of sectors(扇区) to be transferred is

disk scheduling

  • For a multiprogramming system with many processes, the disk queue may often have several(多个) pending (未决) requests.

FCFS先来先服务

SSTF(Shortest seek time first)

每次寻道均寻找当前队列中，距离当前磁头所在磁道距离最近的柱面

这会导致磁臂粘连现象，这本质也是一种饥饿现象，磁头会读取当前柱面附近的柱面，从而导致与之较远的柱面长时间未被读取，产生饥饿

scan

扫描算法，会沿着当前方向一直寻找，直至到最端柱面，在此过程中若经过pending queue中存在的柱面号，则暂停寻找处理数据。
当进程所有访问的柱面是分散的时，采用scan算法时较好

c-scan

scan算法是会原路返回的，但是这一小段时间内pending队列中出现靠近柱面最端的概率并不大，故改进，当扫描到达柱面端时，从另一柱面端开始重新扫描

look

scan和c-scan算法，有些蠢，当对应方向之后没有要寻找的柱面时，磁头任然会继续移动直至柱面端点，look对此进行了改善，当对应方向之后没有需要寻找的柱面时，方向将会反转

  • FCFS is the simplest(最简单的).

  • SSTF is common and has a natural appeal but it may cause a starvation(饥饿) problem.

  • SCAN and C-SCAN perform better for systems that place a heavy load on the disk.

查看linux中当前的和支持的磁盘调度算法

1
#:~$cat /sys/block/sda/queue/scheduler

linux io scheduler

  • noop：it performs(施行) FCFS policy which is good enough for SSD.
  • deadline：it works by creating two queues: a read queue and a write queue. Each I/O request has a time stamp(时间戳) associated(关联) that is used by the kernel for an expiration(过期) time. When an I/O request reaches its deadline, it is pushed to(推到) the highest priority(优先级).
  • cfq：Complete(完全) Fairness(公平的) Queueing works by creating a perprocess I/O queue. The goal of this I/O scheduler is to provide a fair I/O priority to each process. While the CFQ algorithm is complex, the gist of this scheduler is that after ordering the queues to reduce disk seeking, it services these per-process I/O queues in a round-robin fashion.