1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| 调度算法
FCFS 先到先服务
概念：先到达等待队列的进程或作业优先被服务，属于非抢占式算法。
特点：对长作业有利，对短作业不利（排在长作业后面的短作业需要等待很久，带权周转时间很大），这种问题称为「护航效应」（即耗时较少的潜在资源消费者被排在重量级的资源消费者之后）。但不会导致饥饿，因为新来的进程一定排在等待的进程后面执行。
SJF 最短任务优先
概念：在等待队列中需要时间最短的进程优先被服务，也属于非抢占式算法。
特点：如果A、B、C都在等待队列中，那么SJF确实可以使得三个进程的平均周转时间最短，属于最优调度算法；但如果短任务B、C在长任务A稍晚一刻到达，由于算法是非抢占式的，B、C仍然需要等待A运行完，导致护航效应。
STCF 最短完成时间优先
概念：即抢占式SJF。每当有进程加入导致就绪队列改变时，就需要调度，如果新到达的进程，剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。
特点：抢占式SJF可以使得所有进程在整体上具有最短的平均周转时间，但会导致长进程具有较高的响应时间，如果有源源不断的短作业到来，可能会使长作业长时间内得不到服务，产生饥饿现象。
响应比 = （等待时间 + 要求服务时间）/ 要求服务时间
特点：根据响应比计算公式可知，在等待时间相同时，要求服务时间短的作业优先被调度；在要求服务时间相同时，等待时间长的作业优先被调度。对于长作业来说，等待时间越久，响应比越大，更容易优先被服务，从而避免了长作业饥饿。但响应比的计算增加了系统开销。
RR 轮转调度
概念：按照各进程到达就绪队列的顺序，轮流地让各个进程执行一个时间片（time slice）， 让每个进程在一定时间间隔内都可以得到响应，反复执行直到所有任务完成，属于抢占式算法。其中时间片长度必须是时钟中断周期的整数倍，因为时间片到期的通知是由时钟中断指令发出的。
特点：应权衡时间片长度的选取，时间片越短，响应时间越好，但上下文切换过于频繁也会影响整体性能；而时间片太长，就会退化为FCFS，而且进程响应时间会增加。如果关心响应时间，带有合理时间片长度的RR算法就是非常好的调度算法；但如果关心周转时间，RR几乎是最差的，甚至可能比FCFS都差。
重视公平性，响应时间会比较短，但周转时间比较长；允许非公平，周转时间就比较短，但也要以响应时间为代价。实际上这两者的权衡是很常见的。
小结
FCFS是最简单的调度算法，SJF和STCF优化了周转时间，但对响应时间不利；RR优化了响应时间，但对周转时间不利。
但以上算法都采用了两个假设：作业没有I/O、每个作业的运行时间是已知的。这些假设也限制了它们的使用。
MLFQ 多级反馈队列调度算法
概念：MLFQ有多个独立的队列，每个队列都有不同的优先级，任何时刻，一个工作只能存在于一个队列中。MLFQ总是优先执行较高优先级的工作。同一队列中的任务具体相同的优先级，此时对这些工作采用RR算法。
FCFS 非
时间片 抢
最短进程优先SPN 非
最短剩余时间优先 抢
最高响应比优先 非
反馈 抢
|
