抢占式短作业优先调度算法例题

假设有四个进程需要调度，进程信息如下：

| 进程 | 到达时间 | 服务时间 |
|------|----------|----------|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |

其中“到达时间”表示进程到达调度器的时间， “服务时间”表示进程需要占用CPU的时间。

先来说一下抢占式短作业优先调度算法的思想：在所有进程中，选择服务时间最短的进程先执行，如果有新的进程到达且服务时间比当前正在执行的进程更短，则抢占CPU并执行新进程，如果新进程服务时间比当前正在执行的进程更长，则等待当前进程执行完毕后再执行新进程。

按照这个算法，我们可以得到进程的执行顺序如下：

| 时间片 | 当前进程 | 执行进程 | 剩余服务时间 |
|--------|----------|----------|----------------|
| 0 | - | P1 | 7 |
| 1 | P1 | P2 | 3 |
| 2 | P2 | P4 | 4 |
| 3 | P4 | P1 | 6 |
| 4 | P1 | P2 | 2 |
| 5 | P2 | P4 | 3 |
| 6 | P4 | P1 | 5 |
| 7 | P1 | P3 | 4 |
| 8 | P3 | P1 | 3 |
| 9 | P1 | P4 | 2 |
| 10 | P4 | P3 | 2 |
| 11 | P3 | P1 | 2 |
| 12 | P1 | P4 | 1 |
| 13 | P4 | P3 | 1 |
| 14 | P3 | P1 | 1 |
| 15 | P1 | P4 | 0 |
| 16 | P4 | P3 | 0 |
| 17 | P3 | - | - |

注：时间片从0开始计算，- 表示当前没有进程在执行。

根据上表，我们可以得到每个进程的等待时间、周转时间和带权周转时间：

| 进程 | 等待时间 | 周转时间 | 带权周转时间 |
|------|----------|----------|--------------|
| P1 | 14 | 22 | 2.75 |
| P2 | 0 | 3 | 0.75 |
| P3 | 14 | 15 | 1.67 |
| P4 | 2 | 14 | 2.8 |

因此，平均等待时间为 $(14+0+14+2)/4=7.5$，平均周转时间为 $(22+3+15+14)/4=13.5$，平均带权周转时间为 $(2.75+0.75+1.67+2.8)/4=1.7425$。