调度算法:
第一类就绪队列怎么排
第二类是每一次执行时间的长短的控制
第三类关于多种算法如何综合到一起
先来先服务算法
按着到就绪队列里的先后顺序来排队的在找就绪进程的时候也是按照这个先后顺序来。
按先来后到没有考虑到进程的特征
缺点:
1、平均等待时间波动非常大
2、资源的利用效率比较低
CPU密集型的进程会导致I/O设备闲置时,I/O密集型的进程也处于等待。
短进程优先
那它们是按照作业执行时间的长短来进行排队的。
考虑到进程的执行时间
选择执行时间最短的进程占用CPU进入运行状态
选择最短的时间,执行时间执行的时候才会准确的知道,所以要判断预期的执行时间
短剩余时间优先:
一个新的进程它预期的执行时间比当前正在执行的进程剩下那个时间还要短,那这时候允许它抢先
优点:
它具有一个最优平均周转时间的特征
缺点:
按照由短到长来排的,那这么长的就会一直得不到CPU的资源就会导致饥饿。
需要预知执行时间,但是要知道未来是很麻烦的
1、 问用户
2、用过去预测未来是执行时间的预估利用历史信息来预测预估未来的执行时间
高响应比优先算法
它考虑的是进程在就绪队列里的等待时间,依据等待时间的长短来考虑它排的这个队的情况
前面只考虑到进程执行时间的因素,高响应比优先是按照响应比R的值来排序
R = (W+S)/S
W是等待时间S是预估的执行时间
等的时间越长R因为它在分子,R会越来越大
等的时间越长它的优先级越高
在一定程度上就可以避免短进程优先里的长进程等待时间长的这种情况而导致出现饥饿
优点:
1、不允许强占
2、关注的是进程的等待时间
3、可以避免无限期的等待
时间片轮转算法
让各个进程轮流占用一个基本的时间片
在先来先服务的基础上,执行时间的最大长度限制
最长不能执行超过一个时间片在这之前 可以由于等待或者结束而让出CPU使用权
时间片:约定一个进时间片:程调度的基本时间单位是处理机资源分配的基本单位
它的基本工作原理
进程时间片结束的时候会有时钟中断,这时按照先来先服务算法切换到下一个就绪进程
缺点:
时间片轮转算法由于靠时钟中断,强行把正在执行的进程结束掉了,
有额外的上下文切换的开销
时间片设置
两个极端的情况
时间片很大大到可以任何一个进程都在一个时间片内能完成那这时候变成一个先来先服务了
而对于时间片短,大量时间是在做切换,上下文切换有很大的开销的.
在系统通常情况下,10毫秒左右一个时间片这个时间片上下文切换的开销呢是在百分之一左右
多级反馈队列
把就绪队列排成多个子队列
不同的子队列里,可以有不同的算法并且可以在多个队列之间调整一个进程所排的队列
比如:
前台 那是交互的应用要求时间片短
后台,计算时间比较长的
2、每个队列自己的调度算法
前台 用时间片轮转
后台 用先来先服务
3、队列之间:
固定优先级:
先处理前台,然后处理后台
可能导致饥饿
时间片轮转
每个队列分得一定的时间配额
保证它总的时间占一定比例
比如:
前台占80% 后台占20%
前台有作业的时候呢
它可以很好的得到及时的响应
后台也不至于完全处于饥饿的状态
在刚才的多级队列里,各个队列之间是没有交互的
多级反馈队列:
队列之间可以相互移动
可以在不同队列之间做调整,优先级越高,时间片越小;优先级越低,时间片越大。
CPU密集型的进程,优先级会逐步降低并且时间片会分的很大,切换的这个开销相对来说变小
而对于I/O密集型的进程会停留在高优先级上因为每一次它算的时间都很短
公平共享调度算法
它强调的是按照进程占用的资源的情况来进行调度保证我们每一个进程占用的资源呢是相对公平的,强调的是资源访问的公平。
1、用户和进程分组
2、保证不重要的用户组不能垄断资源
3、没有使用完的资源那就按比例分
4、没有达到资源使用率目标的组获得更高的优先级
总结:
多级反馈队列提供一套机制使得我多种算法可以集成到一起,在实际系统里用到的算法基本上是这种综合的算法
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)