目录

总结

操作系统调度算法

先来先服务 First Come First Served

  • 通过 FIFO 队列容易地实现

  • 缺点是平均等待时间往往很长

  • 非抢占式,需要等待程序运行完成或请求I/O

  • 有利于CPU繁忙作业和长作业,不利于I/O密集作业和短作业

短作业优先 Shortest Job First

  • 从队列中选择估计运行时间最短的任务,使之执行直到其放出cpu

  • 对长作业不利,可能饿死

  • 无法处理紧急作业

优先级调度

  • 从队列中选择优先级最高的进程,使之执行直到其放出cpu

  • 非抢占式:即使有优先级更高的任务进入队列,依旧执行当前执行中的任务

  • 抢占式:有优先级更高的任务进入队列时,停止执行中的任务,分配给优先级高的任务

  • 静态优先级:创建进程时确定,依赖进程类型,对资源的要求,用户要求

  • 动态优先级:根据进程运行状况动态调整优先级,依据主要为占用cpu时间长短,等待cpu的时间长短

高响应比优先调度

  • 综合平衡FCFS和SJF调度算法,从队列中选择响应比最高的任务

  • 当作业的等待时间相同时,要求服务时间越短则响应比越高

  • 当要求服务时间相同时,等待时间越长响应比越高

  • 兼顾长作业:等待时间越长其响应比越高

时间片轮转

  • 先来先服务,服务一定时间不管是否完成均后将其放到队列尾部

  • 时间片大小对性能影响很大。太大时将退化为FCFS算法,太小则频繁切换进程使真正执行用户线程的时间变短

多级反馈队列

  • 综合优先级调度和时间片轮转

  • 动态调整优先级和时间片大小

  • 为提高系统吞吐量和缩短平均周转时间而照顾短进程;为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程

  • 设置多个优先级队列,优先级依次降低,每个队列的时间片依次增加,优先级越高,时间片越小。最后一个队列中的时间片一般很大

  • 抢占式调度,有高优先级任务到达时,当前执行任务的优先级较低的话会停止执行,放到当前队列的尾部,转去执行高优先级任务

  • 规则1:如果A的优先级大于B的优先级,运行A不运行B

  • 规则2:如果A的优先级等于B的优先级,轮转运行A和B

  • 规则3:新工作进入系统时,放在最高优先级(最上层)队列

  • 规则4a:工作用完整个时间片后,降低其优先级(移入低一级队列)

  • 规则4b:如果工作在其时间片以内主动释放CPU,则优先级不变,使交互型工作快速运行

  • 会被用户欺骗:进程在时间片快结束时主动释放cpu的话(比如I/O一个无关文件),便可保持高优先级

  • 规则4:防止进程欺骗调度系统,只要某工作在某一层用完了时间片,就将其移入下一个队列,不管其主动释放了多少次cpu

  • 会有饥饿问题:如果有太多短任务,会导致后面队列中的场任务一直得不到执行

  • 规则5:每经过一段时间,就将系统中所有工作重新加入最高优先级。需要合理设置此时间

  • 可以防止进程饿死;也可以在cpu密集任务变成交互型任务时能被调度程序正确对待

  • 调度程序设置多少个队列?每一层队列配多大时间片?多久提升一次优先级以避免饿死?都是需要调优的