1、先来先服务(FCFS)2、短作业优先(SJF)3、高响应比优先(HRRN)
先来先服务(FCFS,First Come First Server)
1、算法思想:主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子)。
2、算法规则:按照作业(或进程)到达的先后顺序进行服务。
3、FCFS用于作业(或进程)调度时考虑的方面:1、用于作业调度时,考虑的是哪个作业先到达后备队列。2、用于进程调度时,考虑的是哪个进程先到达就绪队列。
4、FCFS是非抢占式的算法(上一个进程结束后才运行下一个进程)。
5、FCFS的优点:公平、算法实现简单。FCFS的侃奋眈唁缺点:排在长作业(或进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。所以,FCFS算法对长作业有力,对短作业不利。例如:排队坐车,有的人坐一站,有的人坐到终点站。坐一站的人或许坐车5分钟到目的地,做到终点站的人或许需要50分钟。这样的话,如果他们等的时间越长对坐一站的人来说体验极差,因为坐车5分钟,等车半小时,而对于坐到终点站的人来说等20分钟还可以接受,毕竟坐车都要50分钟。
6、FCFS算法不会导致饥饿(概念见下面注意事项)。
短作业优先(SJF,Shortest Job First)
1、算法思想:追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间。
2、算法规则:最短的作业(或进程)优先得到服务(所谓“最短”是指要求服务时间最短)。
3、SJF即可用于作业调度,也可用于进程调度。用于进程调度时称为“短进程优先(SPF,Shortest Process First)算法”。
4、SJF和SPF是非抢占式的算法。但是也有抢占式的版本:最短剩余时间优先算法(SRFN,Shortest Remaining Time Next).
5、SJF的优点:“最短的”平均等待时间、平均周转时间。SJF的缺点:不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业(或进程)的运行时间是由用户提供的,并不一定真实,不一定做到真正的短作业优先。
6、SJF算法会导致“饥饿”。如果有源源不断的短作业(或进程)到来,可能使长作业(或进程)长时间得不到服务,产生“饥饿”现象。如果一直得不到服务,则称作业(或进程)“饿死”。
高响应比优先(HRRN,Highest Response Ratio Next)
1、算法思想:要综合考虑作业(或进程)的等待时间和要求服务的时间。
2、算法规则:在每次瓢遥费涓调度时先计算各个作业(或进程)的响应比,选择响应比最高的作业(或进程)为其服务。响应比=(等待时间+ 要求服务时间)/ 要求服务 时间
3、HRRN即可用于作业调度,也可用于进程调度。
4、HRRN是非抢占式的算法。因此只有当前运行的作业(或进程)主动放弃处理机时,才需要调度,才需要计算响应比。
5、HRRN综合考虑了等待时间和运行时间(要求服务时间犬匮渝扮)。等待时间相同时,要求服务时间段的优先(SJF的优点)。要求服务时间相同时,等待时间长的优先(FCFS的优点)。
6、HRRN不会导致“饥饿”。对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题。