描述
分类
- FCFS(先来先服务)
- SJF(最短作业优先)
- PS(优先权调度)
- RRS(轮转调度)
- MQS(多级队列调度)
FCFS
先到先服务即先请求CPU的进程先分配到CPU,类似于FIFO队列.
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
对应的Gantt chart为:
| P1 | P2 | P3 |
|---|---|---|
| 24 | 27 | 30 |
SJF
最短作业优先调度算法将每个进程与其下一个CPU区间段相关联.当CPU为空时,它会赋给具有最短CPU区间的进程.如果两个进程具有相同的长度,那么可以使用FCFS调度来处理.
就绪队列无新进程到达
当就绪队列无新值到达时,按正常的程序执行.
| Process | Burst Time |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
对应的Gantt chart为:
| P4 | P1 | P3 | P2 |
|---|---|---|---|
| 3 | 9 | 16 | 24 |
就绪队列有新进程到达
SJF可以是抢占式或非抢占的,当一个新进程到达就绪队列而以前的进程正在执行时,就需要进行判断.与当前进程相比,新的进程比当前进程有更短的CPU区间,抢占SJF算法可抢占当前运行的进程,运行新的进程,而非抢占SJF算法会允许当前运行的进程先完成其CPU区间,然后在进行新的判断.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 6 |
| P2 | 1 | 8 |
| P3 | 2 | 7 |
| P4 | 3 | 3 |
对应Gantt chart为:
| P1 | P2 | P4 | P1 | P3 |
|---|---|---|---|---|
| 1 | 5 | 10 | 17 | 26 |
PS
每个进程都有一个优先级与其关联,具有最高优先级的进程会分配到CPU.具有相同优先级的进程按FCFS顺序调度.一般是数越小优先级越小(不完全是,根据系统而定).
| Process | Burst Time | Priority |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
对应的Gantt chart为:
| P2 | P5 | P1 | P3 | P4 |
|---|---|---|---|---|
| 1 | 6 | 16 | 18 | 19 |
RRS
RRS是专门为分时系统设计的.用RRS调度时,队列中没有进程被分配超过一个时间片(quantum)的CPU时间(除非它是唯一可运行的进程).如果进程的CPU区间超过一个时间片,那么该进程会被抢占,而被放回到就绪队列中.
设 quantum=4(ms)
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
对应Gantt chart为:
| P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 |
|---|---|---|---|---|---|---|---|
| 4 | 7 | 10 | 14 | 18 | 22 | 26 | 30 |
MQS
多级队列调度(暂时没弄明白,待续)