408考研逐题详解：2009年第24题

2009年第24题

下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）

A. 时间片轮转调度算法

B. 短进程优先调度算法

C. 先来先服务调度算法

D. 高响应比优先调度算法

解析

本题考查了进程调度的各个算法，应当掌握各算法的有关知识。

以下是对进程调度的四种经典算法（时间片轮转算法、短进程优先算法、先来先服务算法、高响应比算法）的详细阐述及特点比较：

1. 时间片轮转算法（Round Robin, RR）

   • 核心思想：将 CPU 时间划分为固定大小的时间片（如 10ms），就绪队列中的进程按 FIFO 顺序依次占用一个时间片。若进程在时间片内未完成，则回到队列末尾等待下一次调度。

   • 抢占性：抢占式。

   • 关键参数：时间片大小。若时间片过大，退化为先来先服务算法；若过小，会增加上下文切换开销，降低效率。

   • 优点：

     1. 公平性高：每个进程轮流获得时间片，适合交互式系统（如分时系统），用户体验好。
     2. 避免进程长期垄断 CPU。

   • 缺点：

     1. 时间片设置不当时，上下文切换频繁，效率下降。
     2. 对计算密集型进程（需长时 CPU）不友好，频繁中断导致额外开销。

   • 适用场景：分时操作系统（如早期 UNIX）、实时系统中的任务调度。

2. 短进程优先算法（Shortest Job First, SJF）

   • 核心思想：优先调度预计执行时间最短的进程，分为两种类型：

     1. 非抢占式（SJF）：一旦进程开始运行，直至完成或阻塞才释放 CPU。
     2. 抢占式（最短剩余时间优先，SRTF）：若新进程的剩余时间比当前进程更短，则抢占 CPU。

   • 调度依据：进程的执行时间（可通过历史数据预测）。

   • 优点：

     1. 平均周转时间最短，资源利用率高。
     2. 吞吐量较高，适合批处理系统。

   • 缺点：

     1. 可能导致饥饿：长进程若持续等待短进程，可能长期无法执行。
     2. 需预知进程执行时间（实际中难以准确获取）。

   • 适用场景：批处理系统（如早期大型机），对响应时间要求不高但需高效处理短任务的场景。

3. 先来先服务算法（First-Come, First-Served, FCFS）

   • 核心思想：按进程到达就绪队列的先后顺序进行调度，先到达的进程先获得 CPU，直至完成或阻塞。

   • 抢占性：非抢占式（仅当前进程主动释放 CPU 时才切换）。

   • 优点：

     1. 实现简单，无需复杂调度逻辑。
     2. 公平性体现在 “先来后到”，无饥饿问题（按顺序调度）。

   • 缺点：

     1. 效率低：长进程会阻塞后续短进程，导致短进程等待时间过长（护航效应）。
     2. 平均周转时间和等待时间较长。

   • 适用场景：批处理系统（如早期计算机）、对实时性要求低的场景。

4. 高响应比优先算法（Highest Response Ratio Next, HRRN）

   • 核心思想：在调度时计算每个进程的响应比，选择响应比最高的进程运行。

   • 响应比公式：
     $$\text{优先权}/\text{响应比}{R}_p=\frac{\text{等待时间}+\text{执行时间}}{\text{执行时间}}=1+\frac{\text{等待时间}}{\text{执行时间}}$$

   • 等待时间越长或执行时间越短，响应比越高。

   • 抢占性：非抢占式（仅在当前进程结束或新进程到达时重新计算响应比）。

   • 优点：

     1. 兼顾公平与效率：短进程因执行时间短响应比高，优先调度；长进程等待时间积累后响应比也会升高，避免饥饿。
     2. 动态调整优先级，适应性强。

   • 缺点：

     1. 每次调度需计算响应比，增加系统开销。
     2. 非抢占式，实时性较差。

   • 适用场景：批处理系统，需平衡长短作业的场景。

由上述知识可知，高响应比优先调度算法综合考虑了进程等待时间和执行时间。

本题答案：D