面试题：进程管理之中等难度：并发进程调度策略

Question

请简述常见的进程调度策略，如先来先服务（FCFS）、短作业优先（SJF）、时间片轮转调度算法（RR）的工作原理，并分析它们各自的优缺点。

Answer 1

先来先服务（FCFS）

1. 工作原理：按照进程进入就绪队列的先后顺序进行调度，先进入队列的进程先获得 CPU 资源并执行，直到该进程完成或因某种原因阻塞才释放 CPU。
2. 优点：
   • 算法简单，实现容易，无需额外的信息来进行调度决策。
   • 公平性较好，每个进程都按照到达顺序依次执行，不会偏袒任何进程。
3. 缺点：
   • 对于长作业有利，而对短作业不利。若一个长作业先到达，后面的短作业可能需要等待很长时间才能执行，导致短作业响应时间过长。
   • 若 CPU 繁忙型作业先到达，I/O 繁忙型作业即使到达也需等待，可能使 I/O 设备长时间空闲，降低系统资源利用率。

短作业优先（SJF）

1. 工作原理：从就绪队列中选择预计运行时间最短的进程投入运行，在该进程运行完成或因阻塞而放弃 CPU 之前，不会被其他进程抢占。
2. 优点：
   • 平均周转时间和平均等待时间较短，尤其对短作业能快速完成，提高了系统的整体吞吐量。
   • 资源利用率较高，能让 CPU 更有效地被利用，减少 CPU 空闲时间。
3. 缺点：
   • 难以准确预估作业的运行时间，实际应用中可能无法精确按照短作业优先调度。
   • 对长作业不公平，若不断有短作业进入系统，长作业可能长时间得不到调度，出现“饥饿”现象。
   • 由于需要知道每个作业的运行时间，增加了系统开销。

时间片轮转调度算法（RR）

1. 工作原理：将 CPU 的处理时间划分成一个个固定长度的时间片，就绪队列中的进程轮流获得一个时间片的 CPU 使用权。当时间片用完后，无论该进程是否完成，都将被强制剥夺 CPU，重新回到就绪队列末尾等待下一次调度。
2. 优点：
   • 公平性好，每个进程都能在一定时间内获得 CPU 执行机会，不会出现某些进程长时间得不到调度的情况。
   • 响应时间快，能及时响应交互式进程，适合分时系统和交互式系统，用户体验较好。
3. 缺点：
   • 若时间片设置过短，进程上下文切换频繁，增加系统开销，降低 CPU 有效利用率。
   • 若时间片设置过长，RR 算法退化为 FCFS 算法，对短作业不利，响应时间变长。