操作系统调度算法
进程调度器根据特定的调度算法，将不同的进程调度到 CPU 上执行。本章将讨论六种流行的进程调度算法 —
- First-Come, First-Served (FCFS) Scheduling
- Shortest-Job-Next (SJN) Scheduling
- Priority Scheduling
- Shortest Remaining Time
- Round Robin(RR) Scheduling
- Multiple-Level Queues Scheduling
这些算法分为非抢占式或抢占式。非抢占式算法设计为，一旦进程进入运行状态，就不能被抢占，直到完成其分配的时间；而抢占式调度基于优先级，调度器可以在高优先级进程进入就绪状态时，随时抢占低优先级运行进程。
First Come First Serve (FCFS)
- 按照先来先服务原则执行作业。
- 这是一个非抢占式、抢占式调度算法。
- 易于理解和实现。
- 其实现基于 FIFO 队列。
- 性能较差，因为平均等待时间较高。
每个进程的等待时间如下 —
| Process | Wait Time : Service Time - Arrival Time |
|---|---|
| P0 | 0 - 0 = 0 |
| P1 | 5 - 1 = 4 |
| P2 | 8 - 2 = 6 |
| P3 | 16 - 3 = 13 |
平均等待时间：(0+4+6+13) / 4 = 5.75
Shortest Job Next (SJN)
也称为最短作业优先，或 SJF
这是一个非抢占式、抢占式调度算法。
最小化等待时间的最佳方法。
在批处理系统中易于实现，因为所需 CPU 时间是已知的。
在交互式系统中无法实现，因为所需 CPU 时间未知。
处理器需要提前知道进程将花费多少时间。
给定：进程表及其到达时间、执行时间
| Process | Arrival Time | Execution Time | Service Time |
|---|---|---|---|
| P0 | 0 | 5 | 0 |
| P1 | 1 | 3 | 5 |
| P2 | 2 | 8 | 14 |
| P3 | 3 | 6 | 8 |
每个进程的等待时间如下 —
| Process | Waiting Time |
|---|---|
| P0 | 0 - 0 = 0 |
| P1 | 5 - 1 = 4 |
| P2 | 14 - 2 = 12 |
| P3 | 8 - 3 = 5 |
平均等待时间：(0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25
Priority Based Scheduling
优先级调度是一种非抢占式算法，是批处理系统中最常见的调度算法之一。
每个进程被分配一个优先级。优先级最高的进程优先执行，以此类推。
相同优先级的进程按照先来先服务原则执行。
优先级可以基于内存需求、时间需求或其他任何资源需求来决定。
给定：进程表及其到达时间、执行时间和优先级。这里 1 表示最低优先级。
| Process | Arrival Time | Execution Time | Priority | Service Time |
|---|---|---|---|---|
| P0 | 0 | 5 | 1 | 0 |
| P1 | 1 | 3 | 2 | 11 |
| P2 | 2 | 8 | 1 | 14 |
| P3 | 3 | 6 | 3 | 5 |
每个进程的等待时间如下 —
| Process | Waiting Time |
|---|---|
| P0 | 0 - 0 = 0 |
| P1 | 11 - 1 = 10 |
| P2 | 14 - 2 = 12 |
| P3 | 5 - 3 = 2 |
平均等待时间：(0 + 10 + 12 + 2)/4 = 24 / 4 = 6
Shortest Remaining Time
最短剩余时间 (SRT) 是 SJN 算法的抢占式版本。
处理器分配给最接近完成但可能被剩余时间更短的新就绪作业抢占的作业。
在交互式系统中无法实现，因为所需 CPU 时间未知。
常用于批处理环境中，需要优先处理短作业。
轮转调度
轮转调度是一种抢占式进程调度算法。
每个进程被分配一个固定时间片来执行，这个时间片称为quantum。
一旦进程执行了给定的时间段，它将被抢占，其他进程将执行给定的时间段。
使用上下文切换来保存被抢占进程的状态。
每个进程的等待时间如下 −
| 进程 | 等待时间 : 服务时间 - 到达时间 |
|---|---|
| P0 | (0 - 0) + (12 - 3) = 9 |
| P1 | (3 - 1) = 2 |
| P2 | (6 - 2) + (14 - 9) + (20 - 17) = 12 |
| P3 | (9 - 3) + (17 - 12) = 11 |
平均等待时间: (9+2+12+11) / 4 = 8.5
多级队列调度
多级队列不是一种独立的调度算法。它们利用其他现有算法来分组和调度具有共同特征的作业。
- 为具有共同特征的进程维护多个队列。
- 每个队列可以有自己的调度算法。
- 为每个队列分配优先级。
例如，CPU密集型作业可以调度在一个队列中，所有I/O密集型作业调度在另一个队列中。然后，进程调度器根据分配给队列的算法，交替从每个队列中选择作业并将其分配给CPU。