Day-23 CPU Scheduling Algorithm

CPU Scheduling Algorithm

tags: `IT铁人`

作用

因为同时处理很多的process，所以谁先谁後，或是轮流执行的方式就成为必须的讨论。

每个演算法都会有其优缺点，在考量不同的面相时会有不同的选择，比如单位时间的产量、特定process即时完成、不可造成process永远执行不到。

以下会一一讨论各个Algorithm。

FIFO

FIFO全名称为First In First Out，顾名思义就是先到先做，做完才轮到下一个process。

举例来说：

Process	Burst Time
P1	24
P2	3
P3	3

假设大家都是在t=0进来，依照数字的顺序执行，那麽P1会在t=24完成，P2在t=27完成，P3在t=30完成。

Average waiting time为(24+27)/3=17
Average turnaround time为(24+27+30)/3=27

前面可以看出来不论是等待时间，或是完成时间都较高，FIFO很单纯，具有下列特性。

1.简单，易实施
2.排班效能最差(Average waiting time及Average turnaround time最长)
3.可能会遭遇Convoy Effect(上面的P1导致)
4.公平(任何process都会轮到)
5.No Starvation(不会轮不到)
6.属於Non-preemptive法则(无法插队)

SJF

SJF的全名为Shortest-Job-First，顾名思义就是执行时间最短的先做。

举例来说：

Process	Burst Time
P1	6
P2	8
P3	7
P4	3

假设大家一样是在t=0进来，那麽P4会在t=3完成，P1会在t=9完成，P3会在t=16完成，P2会在t=24完成。

Average waiting time为(3+9+16)/4=7

SJF单纯讨论谁最快就先跑谁，具有以下特性：

1.排班效益最佳(Average waiting time最小)
2.不公平，偏好short job
3.对long-burst-time job可能有starvation(一直无法执行)
4.属於Non-preemptive法则
5.因为不好预测，所以不易实施

SRTF

SRTF全名为Shortest-Remaining Time First，跟SJF不同的地方在於他看的是剩下的时间，如果发现有process更快，系统会允许该process插队。

举例来说：

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

因为比较复杂，杰哥画图解释

在process进来时考虑剩下的执行时间，执行流程会变成上面的样子。

Average waiting time为(9+2+15)/4=13/2

计算时要考虑大家的到达时间，比前面的麻烦一点，SRTF有以下特性：

1.与SJF相比，有更好的排班效益，不过会付出更多的context switch代价
2.不公平
3.有starvation
4.preemptive法则

Priority Scheduling

Priority Scheduling会先给予每个process一个priority，根据priority决定谁可以先执行，遇到priority一样的话，则使用FIFO执行。

举例来说：

Process	Arrival Time	Burst Time	Priority
P1	0	10	5
P2	2	9	3
P3	5	3	1
P4	7	7	2

这个也复杂到需要画图解释

Average waiting time为(19+10+1)/4=15/2

Priority Scheduling单纯看Priority决定顺序，定义的方式由OS或是使用者定义，特性如下：

1.可参数化的法则(用Arrival time定义=>FIFO，用CPU burst time定义=>SJF)
2.不公平
3.可以Preemptive or Non-Preemptive
4.会有Starvation
5.可与RR结合(同样priority RR)

RR

RR的全名是Round-Robin，这个字也会用在循环赛，代表的意思就是大家轮流，也就是说每个process会轮流执行一段时间，如果提早结束或是时间到了，就会交给下一个process执行。

直接用下图举例说明：

Average waiting time为16/3

RR的轮流策略具有以下特性：

1.常用於Time-sharing system
2.公平(每一轮都FIFO order)
3.No Starvation
4.Preemptive(被迫放CPU)
5.RR效能取决於Quantum大小的制定(如果Quantum无限大=>FIFO，非常小=>context switch频繁导致CPU utilization趋近於0)
经验表示，如果Q的大小使80%的process在Q内完成，则效能很好。