anki

3.1 磁盘的结构

3.1.2 磁盘的读/写操作

Q: 如何在磁盘中读/写数据？
A:

将磁头移动到要读/写的扇区所在的磁道。
磁盘旋转，使目标扇区从磁头下面划过。
磁头读取或写入扇区中的数据。

3.1.4 磁盘的物理地址

Q: 磁盘的物理地址如何表示？
A: 磁盘的物理地址用三元组表示：(柱面号，盘面号，扇区号)。

3.1.5 磁盘的分类

Q: 根据磁头是否可移动，磁盘可以分为哪两类？
A:

活动头磁盘：磁头可移动。
固定头磁盘：磁头不可移动。

Q: 根据盘片是否可更换，磁盘可以分为哪两类？
A:

可换盘磁盘：盘片可更换。
固定盘磁盘：盘片不可更换。

3.2 磁盘调度算法

1. 寻道时间

Q: 寻道时间如何计算？
A: 寻找时间（寻道时间）Ts：在读 / 写数据前，将磁头移动到指定磁道所花的时间。
寻道时间 = 启动磁头臂时间 + 移动磁头时间 = s + m * n，其中 s 是启动磁头臂时间，m 是移动一个磁道的时间，n 是需要跨越的磁道数。

2. 旋转延迟时间

Q: 旋转延迟时间如何计算？
A:旋转延迟时间是指磁头定位到要读/写扇区所需的时间。
旋转延迟时间 = (1/2) * (1/r) = 1/2r，其中 r 是磁盘转速。

3. 传输时间

Q: 传输时间如何计算？
A: 从磁盘读出或向磁盘写入数据所经历的时间。假设磁盘转速为 r，此次读 / 写的字节数为 b，每个磁道上的字节数为 N，则最终式子如下：
传输时间 = (1 / r) * (b / N) = b / (rN)，其中 r 是磁盘转速，b 是读/写的字节数，N 是每个磁道上的字节数。

最终总的存取时间为：Ta = Ts + 1/2r + b/(rN)。
结论：延迟时间和传输时间都与磁盘转速相关，且为线性相关，而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。
但是寻道时间是可以进行优化的，具体寻道时间是根据操作系统采用的磁盘调度算法所影响的。

3.2.2 磁盘调度算法概述

Q: 操作系统无法优化磁盘读/写操作的哪些时间？
A: 延迟时间和传输时间，因为它们与磁盘转速线性相关，而转速是硬件的固有属性。

Q: 操作系统可以通过什么方式优化磁盘读/写操作的时间？
A: 通过磁盘调度算法来减少寻道时间。

3.2.3 先来先服务 (FCFS) 算法

Q: FCFS 算法(先来先服务)的原理是什么？
A: FCFS 算法根据进程请求访问磁盘的先后顺序进行调度。
实际举例：
描述：假设磁头的初始位置是 100 号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184。
我们首先按照磁道的前后顺序进行排序（目的是更好看出之间顺序，排序的过程不算在算法中，之后算法不再包含这一步）：

可以看到起点是 100，左边是 90，右边是 150。
流程：接着我们按照 FCFS 的规则，按照请求到达的顺序，磁头需要依次移动到 55、58、39、18、90、160、150、38、184，实际就是一开始题目给出的依次顺序，最终移动的顺序如下图所示：

最终计算为：45+3+19+21+72+70+10+112+146 = 498 个磁道。
请求数量为 9，那么响应一个请求平均需要移动磁道数（平均寻找长度）：498 / 9 = 55.3 个磁道。

Q: FCFS 算法的优缺点是什么？
A: 优点：公平，如果请求访问的磁道比较集中的话，那么算法性能还是可以的。
缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，那么 FCFS 在性能上很差，寻道时间长。

3.2.4 最短寻道时间优先 (SSTF) 算法

Q: SSTF 算法(最短寻道时间优先)的原理是什么？
A: 最短寻找时间优先（SSTF）：该算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。

本质：就是贪心的算法的思想，只是选择眼前最优，但是总体未必最优。
举例：
描述：假设磁头的初始位置是 100 号磁道，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。
初始访问的磁道如下图为：

流程：从 100 开始出发，首先找离最近的磁道就是 90，接着还是找最近的，之后依旧是这个策略 58、55、39、38、18，后面才是 150、160、184。

磁头总共移动磁道数：(100-18) + (184-18) = 248 个磁道。
平均寻找长度（响应一个请求平均需要移动）：248 / 9 = 27.5 个磁道

Q: SSTF 算法的优缺点是什么？
A: 优点：性能比较好，平均寻找时间短。
缺点：可能会产生 “饥饿” 现象。
饥饿现象出现案例：若是在处理完 18 号磁道时本应该对应上图要访问 150 号，但此时突然又来了个访问 38 号磁道，此时由于 38 号磁道更近就会先去访问，若是此后陆陆续续来了一些相近的磁道，那么对于早来临的相对较远的磁道如 150、160、184，这些磁道就会出现饥饿情况迟迟不会被访问到永远得不到满足，从而产生了 “饥饿” 现象。
产生饥饿的原因：磁头在一个小区域内来回来去的移动，从而导致举例较远的磁道长时间无法被访问。

对于这个问题此时出现了扫描算法。

3.2.5 扫描 (SCAN) 算法

Q: SCAN 算法的原理是什么？
A: 对于最短寻找时间优先（SSTF）算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，此时可以规定：

扫描算法（SCAN）：只有磁头移动到最外侧磁道，才能够往内移动，移动到最内侧磁道的时候才能往外移动。
对于磁头移动的方式很像电梯，因此也叫做电梯算法。
核心：只有到了最边上的磁道才能改变磁头的移动方向。
举例：
描述：假设某磁盘的磁道为 0-200 号，磁头的初始位置是 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

流程：磁头首相往右边移动首先处理 150 磁道，接着再往右处理 160 磁道，之后同样如此，不够需要注意的是该算法要求磁头必须移动到最外侧的磁道才开始往内移动，虽然 184 号磁道的右边没有需要请求的磁道编号，此时依旧会向右移动直到移动到最外侧的 200 磁道才开始往内移动。此时会移动到 90 磁道为止开始进行读取，接着依次是 58、55、39、38、18。

磁头总共移动磁道数：(200-100) + (200-18) = 282 个磁道。
平均寻找长度（响应一个请求平均需要移动）：282 / 9 = 31.3 个磁道
最终的寻道时间比先来先服务算法好很多。

Q: SCAN 算法的优缺点是什么？
A: 优点：性能较好，平均寻道时间较短，不会产生饥饿现象。
缺点：
①只有到达最边上的磁道才能够改变磁头移动方向，事实上，处理了 184 号磁道的访问请求之后就不需要再往右移动磁头了。
②SCAN 算法对各个位置的磁道响应频率不平均。

例如：假设此时磁头正在往右移动，且刚刚处理过 90 磁道，那么下次处理 90 号磁道请求就需要等待磁头移动很长一段时间，而响应了 184 号磁道的请求之后，很快又可以再次响应 184 号磁道的请求了。
总结：对于靠近边上的磁道相对来说更好被重复访问到，对于中间的磁道当访问了一次又来临，只能够等待扫描到最边上后才能够返回过来扫描。

3.2.6 LOOK 调度算法

Q: LOOK 调度算法的原理是什么？
A:问题描述：扫描算法（SCAN）中，只有到达最边上的磁道时才能够改变磁头移动方向，事实上，处理了 184 号磁道的访问请求之后就不需要再往右移动磁头了。
Look调度算法：为了解决这个问题，如果在磁头移动方向上没有别的请求了，就可以立即改变磁头移动方向。

边移动边观察，因此叫做 LOOK。
核心说明：如果在磁头移动方向上没有别的请求，就可以立即改变磁头移动方向。
举例子：
描述：假设磁盘的磁道为 0-200 号，磁头初始位置为 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184。

流程：磁头同样是会向右移动，与扫描算法（SCAN）一样不断地向右移动，不过不同的是在访问了 184 号磁道后，由于右边没有需要请求的磁道号，那么此时就会直接改变磁头的移动方向，开始处理 90、58、55、39 等等，如下图所示：

磁头总共移动磁道数：(184-100) + (184-18) = 250 个磁道。
平均寻找长度（响应一个请求平均需要移动）：250 / 9 = 27.5 个磁道
优点：比起 SCAN 算法，不需要每次移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。

3.2.7 循环扫描 (C-SCAN) 算法

Q: C-SCAN 算法的原理是什么？
A: 问题描述：扫描算法（SCAN）中，对于各个位置磁道的响应频率不平均，而 C-SCAN 算法就是为了解决这个问题。
循环扫描算法（C-SCAN）：规定只有磁头朝某个特点方向移动时才处理磁道访问请求，而返回时直接快速移动到起始端而不处理任何请求。
描述：假设磁盘的磁道为 0-200 号，磁头初始位置为 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

流程：磁头首先会向右边的最近磁道进行服务，依次是 150、160、184，注意虽然右边的 200 并不是请求访问的磁道，但是根据该算法规则只有到了最边上的磁道才能改变磁头移动方向。磁头返回途中不处理任何请求。那么当访问到 200 后，会直接将磁头移动到 0 磁道（不会进行任何处理），之后才依次处理 18、38、39、55… 往后的磁道。

磁头总共移动磁道数：(200-100) + (200-0) + (90 - 0) = 390 个磁道。
平均寻找长度（响应一个请求平均需要移动）：390 / 9 = 43.3 个磁道
该算法十分平均体现在哪里？

例如当我们向右访问了 150 号磁道时，那么首先会先到达最右端，之后此时向左回到起始点（这个过程不会访问磁道），接着到最左边初始位置则开始读取磁道。

Q: C-SCAN 算法的优缺点是什么？
A: 优点：比起 SCAN 来，对于各个位置磁道的响应频率很平均。
缺点：只有到达最边上的磁道时才能够改变磁头移动方向，事实上，处理了 184 号磁道的访问请求之后就不需要再往右移动磁头了；并且，磁头返回时其实只需要返回到 18 号磁道即可，不需要返回到最边缘的磁道，另外比起 SCAN 算法，平均寻道时间更长。

3.2.8 C-LOOK 调度算法

Q: C-LOOK 调度算法的原理是什么？
A:为了解决 C-SCAN 算法缺点，提出了 C-LOOK 调度算法。
C-SCAN 算法的主要缺点是只有到达了最边上的磁道才能改变磁头移动方向，并且磁头返回时不许奥返回最边缘的磁道。
C-LOOK调度算法：就是为了解决这个问题，如果磁头移动的方向已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
描述：假设磁盘的磁道为 0-200 号，磁头初始位置为 100 号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问 55、58、39、18、90、160、150、38、184 号磁道。

流程：磁头首先会向右边的最近磁道进行服务，依次是 150、160、184，对于右边的 200 磁道由于并不是需要进行请求读取的，那么此时以后直接掉头移动到左侧的要访问的第一个位置（不做任何处理，对于左边的 0 虽然是边界但是不需要请求访问的）此时磁头会进行掉头之后才依次处理 18、38、39、55… 往后的磁道。

磁头总共移动磁道数：(184-100) + (184-18) + (90 - 18) = 322 个磁道。
平均寻找长度（响应一个请求平均需要移动）：322/ 9 = 35.8 个磁道
优点：比起 C-SCAN 算法，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。
评价：与 LOOK 算法十分类似：若是磁头移动的方向已经没有磁道访问请求了，此时可以让磁头立即返回。