调度算法学习

调度算法的评价指标

cpu利用率 = 忙碌时间 / 总时间
系统吞吐量 = 总完成作业 / 总时间，单位时间内完成作业数量
周转时间 = 作业完成时间 - 作业到达时间，包含各种等待时间
等待时间 = 进程建立之后等待到被服务的时间之和 + 在外存后备队列等待时间（进行时等待IO不算）
响应时间 = 用户提交请求到首次产生响应的时间

调度算法

先来先服务 FCFS

既可以用于作业调度、也可以用于进程调度

算法思想：
从公平的角度考虑，先到达后备队列的顺序，依次调度。优先选择等待时间最长的作业为其服务
用于作业调度时，考虑是哪个作业先到达后备队列；用于进程调度时，考虑哪个进程先到达就绪队列。

是否抢占：
非抢占式算法

优缺点：
优点：公平、算法实现简单
缺点：排在长作业（进程）后面的短作业需要等待很长的时间，带权中转时间很大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利。

不会出现饥饿现象。饥饿是指某个进程、作业长期得不到服务。

短作业优先 SJF

既可以用于作业调度、也可以用于进程调度。
对于进程调度来说称为短进程优先（SPF）

算法思想：
追求更少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间。所谓“最短”，是指要求服务时间最短。优先选择执行时间最短的作业为其服务。**
既可以用于作业调度，也可以用于进程调度。用于进程调度时称为短进程优先（shortest process first）

是否抢占：
SJF和SPF都是非抢占式算法。但是也有抢占式的版本—最短剩余时间优先算法（SRTN）。在SRTN算法中，每当有进程进入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前进程更短，则由新进程抢占处理机，当前进程重新回到就绪队列。

优缺点：
优点：较短的平均等待时间、平均周转时间
缺点：不公平。对短作业有利，对长作业不利。另外作业、进程的运行时间是由用户提供的，不一定能真正的做到短作业优先。
会出现饥饿现象。如果源源不断的有短作业/进程到来，可能会使长作业/进程长时间的得不到服务，产生饥饿现象。如果一直得不到服务，会饿死。

高响应比优先 HRRN

既可以用于作业调度、也可以用于进程调度。

算法思想：
综合考虑等待时间和要求服务时间
算法规则：在每次进程调度时，计算响应比 = (等待时间+要求服务时间) / 要求服务时间

是否抢占：**
非抢占式的调度算法。只有当当前进程主动放弃cpu的时候（正常、异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。

优缺点：
优点：综合考虑了等待时间和运行时间，等待时间相同时，要求服务时间短的优先（SJF优点）；要求服务时间相同时，等待时间长的优先（FCFS优点）。
缺点：对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

不会导致饥饿。

时间片轮转 RR

上面的三种算法一般适用于早期的批处理系统。
RR只用于进程调度，只有作业放入内存建立了相应的进程之后，才能被分配时间片。

算法思想：
时间片轮转调度算法一般用于分时系统。更注重响应时间。公平的轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到相应。

算法规则：
按照进程到达就绪队列的顺序，轮流的让各个进程执行一个时间片。若进程未在一个时间片内执行完，则剥夺处理机，重新进入就绪队列排队。

是否抢占：
若进程未在一个时间片时间间隔内完成，将被剥夺处理机使用权，因此时间片轮转算法属于抢占式算法。由时钟装置发出时钟中断来通知cpu时间片已到。

优缺点：
优点：公平，响应快
缺点：由于高频率的进程切换，有一定的开销。不能区分任务的紧急程度。
如果时间片太大，会使得每个进程都可以在一个时间片内完成，则时间片轮转调度退化为先来先服务调度算法，并且会大大增加进程响应时间。
如果时间片太小，进程频繁的切换会导致系统花费大量的时间来处理切换，进程的调度切换是有代价的。从而导致进程执行的时间比例减少。

不会导致饥饿

优先级调度算法

既可以用于作业调度也可以用于进程调度。
优先级分为动态优先级和静态优先级。

算法思想：
优先处理优先级高的作业、进程。如IO相关的进程优先级更高，系统进程优先级更高。

是否抢占：
抢占式、非抢占式都有。
非抢占式在进程主动放弃处理机是进行调度。
抢占式的优先级调度算法：每次调度时选择当前已到达且优先级较高的进程。除了当前进程主动放弃处理机时发生调度之外，当就绪队列发生改变也会检查是否发生抢占而调度。

优缺点：**
优点：用于优先级区分紧急程度、重要程度，适用于实时操作系统。
缺点：若有源源不断的高优先级作业进程到来，可能会导致饥饿。

多级反馈队列调度算法

流程及规则：
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
新进程到达时优先进入第1级队列，按照FCFS原则，排队等待时间片分配。若用完时间片进程未结束，则进程进入下一级队列的队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。
只有第k级队列为空时，才会为k+1级队头的进程分配时间片。
被抢占的处理机进程重新放回原队列队尾。

只能用于进程调度。

是否抢占？
抢占式的算法。在第k级队列的进程运行的过程中，若更上级的队列(1~k-1)中进入了一个新的进程，则由新进程处于优先级更高的队列，因此新进程会抢占处理机，原来运行的进程放入k级队列的队尾。

优缺点：
优点：各类型的进程相对公平（FCFS优点）；每个进程到达都可很快的响应（RR优点）；短进程只用较少的时间就可以处理完成（SPF优点）；
可以灵活地对各类进程的偏好程度，比如CPU密集型进程、IO密集型进程（将IO阻塞的进程放到原队列队尾，这样使IO进程处于较高优先级）。
缺点：会发生饥饿。

总结

早期的批处理系统，注重平均周转时间等。比起早起的批处理系统来说，分时操作系统、实时操作系统更注重系统的响应时间、公平性、平衡性等指标，因此时间片轮转、优先级调度、多级反馈队列调度算法（Unix使用）更适合这种交互式操作系统。