调度算法(一)
(1)前言
此处列举的三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用户来说,交互性很糟糕。
因此这三种算法一般适合用于早期的批处理系统,当然, FCFS 算法也常结合其他的算法使用,在现在也扮演着很重要的角色。而适合用于交互式系统的调度算法见(二)。
(2)FCFS 先来先服务 First Come First Serve
Ⅰ. 算法思想
主要从”公平“的角度考虑。
Ⅱ. 算法规则
按照作业/进程到达的先后顺序进行服务。
Ⅲ. 用于作业/进程调度
用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,或虑的是哪个进程先到达就绪队列。
Ⅳ. 是否可抢占
非抢占式的算法。
Ⅴ. 优缺点
- 优点:公平,算法实现简单。
- 缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。即,FCFS 算法对长作业有利,对短作业不利。
Ⅵ. 是否会导致饥饿
不会(前面的作业/进程总有执行完毕的时候)。
Ⅶ. 例子
(3)SJF 短作业优先 Shortest Job First / SPF 短进程优先 Shortest Process First / SRTN 最短剩余时间优先算法 Shortest Remaining Time Next
Ⅰ. 算法思想
追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间。
Ⅱ. 算法规则
最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短)。
Ⅲ. 用于作业/进程调度
即可用于作业调度(SJF),也可用于进程调度(SPF)。
Ⅳ. 是否可抢占
(没明确说明)默认是非抢占式的算法。
也有抢占式的版本—— SRTN 最短剩余时间优先算法 Shortest Remaining Time Next
Ⅴ. 优缺点
- 优点:“最短的”平均等待时间、平均周转时间。
- 缺点:不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业/进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先。
Ⅵ. 是否会导致饥饿
会。如果源源不断地有短作业/进程到来,可能使长作业/进程长时间得不到服务,产生“饥饿”短象。如果一直得不到服务,则称为“饿死”。
Ⅶ. 例子
1. 非抢占式(当某个作业/进程执行结束后再进行调度)
2. 抢占式(当有新进程加入就绪队列或当某个进程执行结束后立即进行调度)
Ⅷ. 补充
(4)HRRN 高响应比优先 Highest Response Ratio Next
Ⅰ. 算法思想
综合考虑作业/进程的等待时间和要求服务的时间。
Ⅱ. 算法规则
在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务。(响应比 >= 1)
Ⅲ. 用于作业/进程调度
即可用于作业调度,也可用于进程调度。
Ⅳ. 是否可抢占
非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时,才需要调度,才需要计算响应比。
Ⅴ. 优缺点
综合考虑了等待时间和运行时间(要求服务时间)。
等待时间相同时,要求服务时间短的优先(SJF 的优点)。
要求服务时间相同时,等待时间长的优先(FCFS 的优点)。
Ⅵ. 是否会导致饥饿
不会(对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题)。
Ⅶ. 例子
标签:抢占,作业,调度,算法,等待时间,进程 From: https://www.cnblogs.com/Wind730/p/18534398/schedule-algorithm-1-z1dxjxn