操作系统(2) (进程调度/进程调度器类型/三种进程调度/调度算法)

目录

1. 介绍进程调度（Introduction to Process Scheduling）

2. 优先级调度（Priority Scheduling）

3. CPU 利用率（CPU Utilization）

4. 吞吐量（Throughput）

5. 周转时间（Turnaround Time）

6. 等待时间（Waiting Time）

7. 响应时间（Response Time）

8. 公平性（Fairness）

2. 进程调度器的类型（Types of Process Schedulers）

1. 长期调度（Long-term Scheduling）

2. 中期调度（Medium-term Scheduling）

3. 短期调度（Short-term Scheduling，Dispatcher）

3. 典型的进程调度算法（Typical Process Scheduling Algorithms）

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

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

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

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

1. 介绍进程调度（Introduction to Process Scheduling）

• 进程调度是操作系统的核心功能之一，负责管理多个进程对 CPU 的争用，以实现多任务处理。调度程序决定哪个进程在何时获得 CPU 资源，从而最大化系统性能和资源利用率。

2. 优先级调度（Priority Scheduling）

• 概念： 为每个进程分配一个优先级，优先级越高，越早得到 CPU 的调度。优先级可以由系统或用户指定，也可以根据进程行为和系统状态动态变化。
• 目标： 确保关键任务或时间敏感任务能优先得到处理，从而满足任务的紧急性需求。
• 注意： 优先级调度可能导致低优先级进程饥饿（一直得不到 CPU 资源），需要结合其他策略来确保公平性。

3. CPU 利用率（CPU Utilization）

• 目标： 提高 CPU 利用率，使 CPU 尽可能保持忙碌状态，减少闲置时间。高 CPU 利用率意味着更有效的资源使用。
• 调度算法的作用： 通过优化进程的执行顺序，减少 CPU 的空闲时间，确保系统能处理更多任务。

4. 吞吐量（Throughput）

• 概念： 吞吐量是指在一定时间内完成的进程数量。更高的吞吐量意味着系统在单位时间内处理了更多的任务。
• 目标： 调度算法应尽量最小化进程完成时间，以此来提高系统的吞吐量。尤其在批处理系统中，吞吐量是评估调度性能的重要指标。

5. 周转时间（Turnaround Time）

• 定义： 周转时间是从进程提交到完成所需的总时间，包括等待时间、执行时间和 I/O 操作时间。
• 目标： 进程调度应尽量最小化平均周转时间，以提升系统的响应性和用户满意度。
• 适用场景： 在多任务系统中，较短的周转时间意味着用户请求可以更快得到处理和完成。

6. 等待时间（Waiting Time）

• 定义： 等待时间是指一个进程在就绪队列中等待执行的总时间。
• 目标： 调度策略应尽量减少进程的等待时间，以避免资源的低效利用和系统性能的下降。
• 重要性： 长时间的等待会导致用户体验变差，特别是在交互式系统中。

7. 响应时间（Response Time）

• 定义： 响应时间是指从进程提交到产生第一次响应（如输出）的时间。
• 目标： 在交互式系统中，调度算法应最小化响应时间，确保系统能够及时反馈用户操作，提供良好的用户体验。
• 调度算法： 如时间片轮转（Round Robin），旨在提供低响应时间以满足交互式应用的需求。

8. 公平性（Fairness）

• 定义： 公平的调度算法确保所有进程都能公平地获得 CPU 时间，不会出现某个进程一直得不到执行的情况。
• 重要性： 公平性在多用户或多任务系统中特别重要，以保证不同用户或应用程序在竞争资源时都有机会得到合理的执行时间。

  ---

2. 进程调度器的类型（Types of Process Schedulers）

1. 长期调度（Long-term Scheduling）

• 作用：
  • 控制系统中的多道程序程度（Degree of Multiprogramming）： 决定哪些新进程可以进入系统。长期调度器通过选择一组新进程，来保持一个合适的 CPU 和 I/O 绑定进程的组合，以充分利用系统资源。
  • 平衡资源使用： 为了让 CPU 和 I/O 设备都保持忙碌状态，长期调度器会选择合适的 CPU-bound 和 I/O-bound 进程的组合进入系统。
• 触发：
  • 较少触发： 仅在创建新进程或系统负载发生显著变化时触发。这种调度发生不频繁，因为它主要决定哪些进程可以被“引入”到系统中。
• 目的：
  • 通过选择合适数量和类型的进程进入系统，优化整体系统性能，避免资源浪费或过载。

2. 中期调度（Medium-term Scheduling）

• 作用：
  • 控制多道程序程度和内存利用： 主要负责内存管理，决定哪些进程需要被**交换（Swapping）**到内存外，以缓解内存压力或调整多道程序的数量。
  • 交换（Swapping）： 当系统内存不足或系统负载过高时，中期调度器可以将某些进程暂时从主内存中移出（交换到硬盘），以腾出空间给其他进程。
• 触发：
  • 根据内存压力触发： 当系统内存紧张或需要调整多道程序程度时触发。这样可以确保系统在内存使用方面保持平衡，提高系统的响应速度。
• 目的：
  • 提高内存利用率，维持系统的响应性，确保在内存资源有限的情况下，进程可以顺利执行。

3. 短期调度（Short-term Scheduling，Dispatcher）

• 作用：
  • 管理就绪队列（Ready Queue）： 负责选择就绪队列中的下一个进程并将其分配给 CPU 执行。短期调度器（也叫调度器或分派器）是进程调度中最频繁的一部分。
  • 响应各种事件：
    • 时钟中断（Clock interrupts）： 例如，在抢占式系统中，当一个时间片到期时，调度器会被触发。
    • I/O 中断（I/O interrupts）： 当 I/O 操作完成时，调度器选择下一个进程。
    • 系统调用（System calls）： 当进程发出阻塞调用时，调度器决定哪个进程应立即获得 CPU。
    • 信号量操作（Semaphore operations）： 当资源变得可用时，调度器会唤醒等待中的进程。
• 触发：
  • 非常频繁： 在进程调度中触发频率最高，因此必须高效快速。
• 目的：
  • 最小化响应时间： 快速选择和分配进程，确保系统保持高效运转，提供及时的响应。

    ---

3. 典型的进程调度算法（Typical Process Scheduling Algorithms）

• 先来先服务（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 运行时间很短但到达频率较高时，系统效率会受到明显影响。
• 总结
• FCFS： 简单易实现，按到达顺序调度，具有位置公平性，但可能导致长进程或 CPU-bound 进程垄断资源。
• SJF： 提供最优的平均周转时间，优先处理短进程，但可能引发长进程的“饥饿”问题，而且需要准确的执行时间估计。
• 这两种算法都是非抢占式的，每种都有其适用场景。选择调度算法时，需要权衡系统的需求和进程特性。
• RR 调度算法通过固定的时间片轮流分配 CPU 时间，确保每个进程都能公平地获得 CPU 资源，是多用户、多任务操作系统中常用的调度策略。
• 时间片的选择至关重要：过小的时间片会导致频繁的上下文切换；过大的时间片会增加响应时间，并使 RR 退化为 FCFS。
• RR 的公平性使其适用于交互式系统，但必须在系统响应性和上下文切换开销之间找到平衡。

• 优先级队列调度算法是一种通过分配进程优先级来控制调度顺序的算法，适用于需要对关键任务进行及时响应的系统，特别是实时操作系统。
• 它在提高重要任务响应性和系统灵活性方面表现优异，但可能导致低优先级进程的“饥饿”和较高的上下文切换开销，因此需要权衡优先级分配策略，或者引入防止饥饿的机制（如老化（Aging））。