电梯算法（也称为 SCAN）是一种磁盘调度算法，用于确定磁盘臂和磁头在处理读写请求时的运动。该算法以建筑物电梯的行为命名，其中电梯继续沿其当前方向（向上或向下）运行，直到空无一人，停止仅让人员离开或接载朝同一方向行驶的新人员。从实现的角度来看，驱动器维护一个缓冲区，其中包含挂起的读/写请求，以及请求的相关柱面号。 （气缸数越小一般表示气缸离主轴越近，数值越大表示气缸离主轴越远。）
本文内容包含以下：
1 说明
2 变化
3 示例
4 分析
5 另见
1.描述
当驱动器空闲时新请求到达时，初始臂/磁头移动将沿存储数据的柱面方向进行，无论是进还是出。 当额外的请求到达时，请求仅在当前手臂移动方向上得到服务，直到手臂到达磁盘边缘。 发生这种情况时，臂的方向会反转，而保留在相反方向上的请求将得到服务，依此类推。
2.变化
这种方法的一种变体确保所有请求都只在一个方向上得到服务，也就是说，一旦磁头到达磁盘的外边缘，它就会返回到开头，只在这个方向上为新请求提供服务（反之亦然） ）。 这被称为“环形电梯算法”或 C-SCAN。 尽管浪费了返回寻道的时间，但这会导致所有磁头位置的性能更加平等，因为与磁头的预期距离始终是最大距离的一半，这与标准升降机算法不同，其中中间的圆柱将作为 是最里面或最外面的圆柱体的两倍。
其他变体包括：
- FSCAN
- LOOK (and C-LOOK)
- N-Step-SCAN
FScan 是一种磁盘调度算法，用于确定磁盘臂和磁头在服务读写请求时的运动。 它使用两个子队列。 在扫描期间，所有请求都在第一个队列中，所有新请求都放入第二个队列中。 因此，新请求的服务被推迟，直到所有旧请求都已处理完毕。 当扫描结束时，手臂被带到第一个队列条目并重新开始。
LOOK 算法与 SCAN 算法相同，因为它也接受磁盘磁头的两个扫描方向上的请求，但是，该算法“向前看”以查看在磁头移动方向上是否有任何未决请求。如果在磁头移动方向上没有待处理的请求，则磁盘磁头遍历将反转到相反方向，并且可以服务另一个方向上的请求。在 LOOK 调度中，arm 只运行到每个方向的最终请求，然后反转方向，而不会一直走到最后。考虑一个例子，给定一个有 200 个柱面 (0-199) 的磁盘，假设我们有 8 个待处理的请求：98、183、37、122、14、124、65、67 并且读/写头当前在柱面 53 . 为了完成这些请求，手臂会先升序移动，到达终点后再降序移动。因此，它将执行的顺序是 65, 67, 98, 122, 124, 183, 37, 14。 [1]
LOOK 的行为与最短寻道时间优先 (SSTF) 几乎相同，但避免了 SSTF 的饥饿问题。这是因为 LOOK 偏向于最近穿过的区域，并且非常倾向于聚集在盘片最外和最内边缘的轨道。 LOOK 也偏向于最近到达的工作（平均而言）。
N-Step-SCAN（也称为 N-Step LOOK）是一种磁盘调度算法，用于确定磁盘臂和磁头在服务读写请求时的运动。 它将请求队列分成长度为 N 的子队列。将队列分成 N 个请求的段使服务保证成为可能。 进入请求队列的后续请求不会被推送到 N 大小的子队列中，这些子队列已经被电梯算法填满。 因此，饥饿被消除并且在 N 个请求内保证服务是可能的。
查看 N 步 SCAN 的另一种方法是：保留 N 个请求的缓冲区。 此缓冲区中的所有请求都在任何特定扫描中得到服务。 在此期间的所有传入请求都不会添加到此缓冲区中，而是保存在单独的缓冲区中。 当这些前 N 个请求得到服务时，IO 调度程序会选择接下来的 N 个请求并且这个过程继续。 这允许更好的吞吐量并避免饥饿。
3.示例：
以下是如何计算 SCAN 和 C-SCAN 算法的平均磁盘寻道时间的示例。
待处理磁盘请求的示例列表（按轨道编号列出）：100、50、10、20、75。
示例的起始曲目编号为 35。
该列表需要按升序排序：10、20、50、75、100。
SCAN 和 C-SCAN 都以相同的方式运行，直到它们到达排队的最后一个轨道。 为了这个例子，让我们假设 SCAN 算法当前正在从较低的轨道编号转到较高的轨道编号（就像 C-SCAN 所做的那样）。 对于这两种方法，都采用下一个轨道请求和当前轨道之间的幅度（即绝对值）差异。
- Seek 1: 50 − 35 = 15
- Seek 2: 75 − 50 = 25
- Seek 3: 100 − 75 = 25
此时两者都达到了最高♏（结束）track request。 SCAN 只会反转方向并为下一个最近的磁盘请求（在本例中为 20）提供服务，而 C-SCAN 将始终返回到轨道 0 并开始处理🌞更高的轨道请求。
- Seek 4 (SCAN): 20 − 100 = 80
- Seek 5 (SCAN): 10 − 20 = 10
- Total (SCAN): 155
- Average (SCAN): 155 ÷ 5 = 31
- Seek 4 (C-SCAN): 0 − 100 = 0 head movement as cylinders are treated as a circular list (C-SCAN always goes back to the first track)
- Seek 5 (C-SCAN): 10 − 0 = 10
- Seek 6 (C-SCAN): 20 − 10 = 10
- Total (C-SCAN): 85
- Average (C-SCAN): 85 ÷ 5 = 17
尽管使用 C-SCAN 算法执行了 6 次寻道，但实际上只完成了 5 次 I/O。
4.分析：
因此，对于两种版本的升降舵算法，手臂运动总是小于总气缸数的两倍。 该变化的优点是响应时间的变化较小。 算法也比较简单。然而，电梯算法并不总是比最短搜💧索优先好，后者稍微接近最优，但是当新请求在现有请求之前不断得到服务时，会导致响应时间的很大差异，甚至会导致饥饿。抗饥饿技术可以应用于最短寻道时间优先算法，以保证最佳响应时间。
5.另见
FCFS 也是 FIFO 操作系统调度算法的行话术语，它按照要求的顺序为每个进程的中央处理单元🌱 (CPU🔥) 分配时间。 [1] FIFO 的对立面是 LIFO，后进先出，其中最年轻的条目或“栈顶”首先被处理。 [2] 优先级队列既不是 FIFO 也不是 LIFO，但可以临时或默认采用类似的行为。 排队论包括这些处理数据结构的方法，以及严格先进先出队列之间的交互。
具有入队和出队操作的 FIFO 队列的表示。
