操作系统 (2) （进程调度/进程调度程序的类型/进程调度的三种类型/调度算法）-3.典型进程调度算法

先来先服务（First-Come, First-Served, FCFS）： 按照进程到达的顺序进行调度。简单易实现，但可能导致较长的等待时间，尤其是出现长作业时。

• 优点：
  • 位置公平性（Positional Fairness）： 简单易实现，进程按照它们的到达顺序被执行，不会跳过任何一个进程。
• 缺点：
  • 倾向长进程： FCFS 倾向于长时间运行的进程，短进程可能要等待很长时间（类似超市结账时，一个顾客带着大量商品结账）。
  • 倾向 CPU-bound 进程： CPU-bound 进程容易占用更多的 CPU 时间，导致 I/O-bound 进程长时间等待，降低系统的整体效率。

短作业优先（Shortest Job Next, SJN）： 优先调度预计执行时间最短的进程，可以减少平均等待时间，但需要估计执行时间，可能导致“饥饿”问题。

• 优点：
  • 最优周转时间： 在已知各进程执行时间的情况下，SJF 能够实现最优的平均周转时间，是一种非常高效的调度策略。
• 缺点：
  • 饥饿问题（Starvation）： 在 SJF 中，长进程可能因为不断有新的短进程到达而得不到 CPU 资源，导致“饥饿”。
  • 公平性和可预测性不足： SJF 偏向于短进程，长进程的用户无法预测进程何时能够获得 CPU 资源。
  • 需要知道执行时间： SJF 要求预先知道或估计每个进程的运行时间，但在实际中，准确估计执行时间并不总是容易实现。

时间片轮转（Round Robin, RR）： 为每个进程分配固定的时间片（time slice），时间片耗尽后，切换到下一个进程。适用于多任务环境，能提供较好的响应时间。

• 2. 时间片（Quantum）选择的重要性 时间片的大小直接影响系统的响应性和效率：

  • 小时间片：
    • 提高响应时间： 确保每个进程都能迅速获得 CPU 时间，适合交互式系统，需要快速响应用户输入。
    • 增加上下文切换： 频繁的抢占会导致更多的上下文切换，增加系统开销，降低 CPU 效率。
  • 大时间片：
    • 提高吞吐量： 减少上下文切换的次数，进程可以长时间占用 CPU，更好地完成长时间的计算任务。
    • 增加响应时间： 可能导致进程长时间等待，尤其在多进程系统中，进程必须等更长时间才能再次获得 CPU。

• 3. 优点

  • 改善响应时间：
    • RR 可以确保每个进程在一段时间内都会得到执行机会，防止进程被“饿死”，适用于交互式系统，保证及时的用户反馈。
  • 适合多用户的时间共享系统：
    • 每个进程都有均等的机会使用 CPU，非常适合多用户、多任务的操作系统，确保资源公平分配。
  • 公平性：
    • 每个进程都有平等的机会获得 CPU，防止任何进程垄断 CPU 时间。与基于优先级的调度不同，低优先级进程不会被饿死。
• 缺点
  • 频繁的上下文切换：
    • 可能退化为 FCFS：
      • 如果时间片过大，RR 会变得类似于先来先服务（FCFS），因为进程在时间片内有足够的时间完成执行，不会被抢占。
    • 倾向于 CPU-bound 进程：
      • 因为 CPU-bound 进程可以充分利用整个时间片，它们会被重新排入队列等待执行。而 I/O-bound 进程通常需要短暂的 CPU 时间来发起 I/O 操作，因此它们在队列中等待的时间较长，获得 CPU 时间的机会相对减少。
    • 当时间片较小时，上下文切换频率会增加，导致 CPU 资源用于保存和恢复进程状态的开销增加，降低系统效率。

• 优先级调度（Priority Scheduling）： 按照进程的优先级进行调度，优先级高的进程先执行。可能导致低优先级进程饥饿。

• 优点

  • 改善重要任务的响应性：
    • 该算法确保高优先级或重要的进程能够尽快被执行，从而提高了对关键任务的响应时间。例如，实时任务或紧急 I/O 操作可以获得更高的优先级。
  • 灵活性：
    • 通过为不同进程分配不同的优先级，操作系统可以灵活地处理多种类型的任务。实时进程可以被分配更高的优先级，而后台任务可以分配较低的优先级。
  • 适合实时系统：
    • 优先级队列调度特别适用于实时系统（如嵌入式系统或多媒体应用），这些系统需要确保高优先级任务能够及时执行，避免延迟。

  • 3. 缺点

  • 可能发生饥饿（Starvation）：
    • 如果系 统中不断有高优先级的进程到达，低优先级进程可能一直得不到执行机会，陷入“饥饿”状态。这在抢占式优先级调度中尤为严重，因为低优先级进程随时可能被抢占。
  • 低优先级进程的响应时间增加：
    • 虽然高优先级任务能获得低响应时间，但低优先级进程可能需要等待很长时间。如果新的高优先级进程不断到达，低优先级进程将被反复抢占，导致其响应时间显著增加。
  • 抢占式优先级调度的高开销：
    • 当高优先级进程到达时，正在运行的低优先级进程会被抢占，这需要频繁的上下文切换，增加了系统开销。尤其是当高优先级进程的 CPU 运行时间很短但到达频率较高时，系统效率会受到明显影响。