[最短寻道优先调度][电梯调度][先来先服务调度]

最短寻道优先调度（Shortest Seek Time First，SSTF）是一种磁盘调度算法，用于优化硬盘驱动器的读写操作。在计算机系统中，当多个读写请求被发送到磁盘时，SSTF算法会选择执行那些需要磁头移动最短距离的请求，以减少总的寻道时间。

工作原理如下：

当有新的磁盘访问请求到达时，SSTF会检查当前磁头位置，并选择离当前磁头位置最近的那个磁道上的请求进行服务。

一旦这个最近的请求被处理完，SSTF会再次寻找下一个离当前磁头位置最近的未处理请求，以此类推。

虽然SSTF可以减少平均寻道时间，但它可能导致某些请求被无限期地延迟，因为如果新到达的请求总是更接近当前磁头位置，那么某些远离当前磁头位置的请求可能永远不会得到服务。这种现象被称为“饥饿”（Starvation）。为了避免这种情况，一些操作系统可能会采用其他算法，如扫描算法（SCAN），它确保所有请求最终都会被处理。

SSTF算法适用于那些寻道时间是主要性能瓶颈的情况，但必须谨慎使用，以避免饥饿问题。

SCAN算法，又称为扫描算法或电梯算法，是磁盘调度中的一种重要算法，它的命名来源于其工作原理与电梯在多层建筑中上下移动时响应呼叫的方式相似。

在磁盘调度的上下文中，SCAN算法的目标是减少磁盘读写头的平均寻道时间，从而提高磁盘I/O操作的整体效率。以下是SCAN算法的基本步骤：

初始化：读写头开始于磁盘的一端，通常是磁盘的最内侧磁道（编号为0）或最外侧磁道。

单向扫描：读写头向一个方向移动，例如从内向外，依次处理所有在其路径上的请求。这意味着任何位于当前磁道和磁盘最外侧磁道之间的请求都会被处理。

反转方向并继续处理：当读写头到达最外侧磁道时，它会反转方向，从外向内移动，继续处理沿途的请求，直到回到最内侧磁道。

重复：该过程会重复进行，直到所有的请求都被处理完毕。

SCAN算法的关键在于它不会随机跳跃到磁盘的任意位置来处理请求，而是按照顺序处理，这减少了频繁的反向移动，从而降低了平均寻道时间。不过，这也意味着在扫描方向的另一端的请求可能需要等待较长的时间才能被处理，直到读写头再次扫描到那一端。

SCAN算法是公平的，因为它确保每个请求最终都会被处理，而且由于其有序的处理方式，它能够提供比其他一些算法更好的平均性能。然而，对于位于扫描路径两端的请求，它们的等待时间可能较长，这是SCAN算法的一个缺点。为了改善这一情况，可以使用SCAN算法的变体，如C-SCAN（循环扫描）或LOOK（仅限一次）算法。

FCFS调度，全称First-Come, First-Served scheduling，即先来先服务调度，是一种最基本的调度算法，不仅在磁盘调度中常见，也在作业调度、进程调度等场景中广泛使用。它的原则非常简单直观：

1. **请求按到达顺序排队**：所有到达的请求都会按照它们到达的先后顺序加入队列中。

2. **按顺序处理**：调度器将按照队列中请求的顺序逐一处理，即最先到达的请求将首先被处理，然后是第二个到达的请求，依此类推。

FCFS调度算法的优点是实现简单，易于理解，对所有请求来说也是公平的，因为它保证了先来的请求会被先处理，没有请求会被故意延迟。

然而，FCFS调度算法的主要缺点是它可能不是最有效的调度策略，尤其是在磁盘调度的情况下。例如，如果一系列请求分布在磁盘的不同位置，FCFS调度会导致读写头在磁盘上频繁地来回移动，产生大量的寻道时间，从而降低磁盘I/O的效率。

在进程调度中，FCFS可能导致长进程阻塞短进程，即使短进程可以在短时间内完成，但由于长进程的存在而不得不等待，从而降低了系统的整体吞吐量和响应时间。

尽管FCFS调度在某些情况下可能不是最优的选择，但在一些不需要特别优化或在资源有限的系统中，它仍然是一个可行的调度策略。此外，在某些实时系统中，保持任务执行的确定性和可预测性比最小化响应时间更为重要，这时FCFS调度也可能是一个合适的选择。