进程调度
关于进程调度需要先了解什么是进程,进程可以简单理解为正在运行的程序。而进程调度的两个关键性指标则是:响应时间与周转时间。
响应时间:
进程未运行到下次被选中运行的时间间隔。如:创建进程到第一次调度到进程的时间。再比如:进程切换后到下一次调度到该进程的时间间隔。
响应时间体现了交互感,如:敲下键盘到屏幕上出现对应的字符,自然是时间越短越好。即响应时间越短,交互性越好。
周转时间:
进程从启动开始到执行结束的时间间隔。周转时间可以体现性能,周转时间越短,从进程执行到结束所等待的时间越短。
性能和公平往往是互相矛盾的,优化性能必然会降低公平性,反之亦然。进程调度就是不断去平衡两者之间的关系,去权衡利弊。
进程的调度算法分为:先进先出(FIFO)调度算法、最短任务优先(SJF)调度算法、最短完成时间优先(STCF)调度算法、Round—Robin调度算法、高响应比优先调度算法、多级反馈队列调度算法。
先进先出(FIFO)调度算法:
设:有三个进程A、B、C,当他们的运行时间一致(10s)时:
平均周转时间: (10 + 20 + 30)/ 3 = 20s
平均响应时间: (0 + 10 + 10)/ 3 = 6.67s
当A进程运行时间为100s时:
平均周转时间: (100 + 110 + 120)/ 3 = 110s
平均响应时间: (0 + 100 + 110)/ 3 = 70s
此时,FIFO的缺点就很明显了。若耗时较短的进程放在耗时更长的进程之后,那么短进程将做出无谓的等待。
就像去超市买东西结账时,假如我们只买了一件商品,前面的人购物车堆满了商品。此时,我们都想让我们先结账,因为在我们看来,我们的结账速度很快。因此,这种效率很低。但如果超市开通一个新的零散结账通道给购买商品很少的客户,就可以提高效率。但很显然这是不可能的,因为超市无法对用户的商品购买量进行限制。
但这种零散结账的模式正是下一种算法:最短任务优先,让购买量较小的客户先结账。
最短任务优先(SJF)调度算法:
顾名思义,最短的进程先执行。按照上面的例子,如果A进程执行时间为100s,B、C不变仍为10s;A最长,所以最后执行。
平均周转时间: (10 + 20 + 120)/ 3 = 50s
平均响应时间: (0 + 10 + 20)/ 3 = 10s
但如果不是所有进程同时启动,而是随机启动,则此时最坏的情况就是A进程先执行,这时就又回到了最糟糕的情况:
平均周转时间: (100+(110-10) + (120 - 10))/ 3 = 103.3s
平均响应时间: (0 + (100-10) + (110-10))/ 3 = 63.3s
最短完成时间优先(STCF)调度算法:
在上一种算法中,仍然有可能回到最糟糕的情况。因此,我们假设进程的调度是可以抢占的,谁抢到优先权谁就先运行。那么短任务就可以在开始的时候直接运行,不需要等待很长时间,这就是最短完成时间优先调度算法。
因此,先进先出和最短任务优先都是非抢占式的,而最短完成时间是抢占式的调度算法。
关于抢占式,可能会有一些容易误解的地方。抢占式并不是说进程抢到CPU资源了,而是指优先级。进程调度实际上大部分都是由操作系统决定的,所谓抢占,只是表明该进程优先级要高一些,可能马上就会调度到它,下一个就是,同时也有可能除它以外还有优先级更高的进程或者和它同级的进程。
平均周转时间: (120 + (20-10) + (30-10))/ 3 = 50s
平均响应时间: (0 + 0 + 10)/ 3 = 3.3s
此算法在两项指标上都已经达到了最佳效果,这归功于抢占式。只要是抢占式,平均时间就不会比非抢占式的差。
Round—Robin调度算法:
其实,抢占式的响应时间还可以优化。在最短完成时间的基础上添加一个条件:指定每个进程最多运行固定的一段时间,轮询调度每一个进程,这就是“轮询调度”或“时间片轮转”。
这种“固定的时间段”就是“时间片”。如果要使用时间片的功能,就必然需要时间中断,并且时间片的长度必须是时钟周期的倍数。如: 时间中断是5s一次,那么时间片就是5s、10s、15s、20s ... ...
在上个算法的基础上添加2s的时间片,且三个进程同时启动:
平均周转时间: (120 + (30-2) + 30)/ 3 = 59.3s
平均响应时间: (0 + 2 + 4)/ 3 = 3s
高响应比优先调度算法:
高响应比优先调度算法(Highest Reponse Ratio First, HRRF)是非抢占式的,它同时考虑了每个进程的响应时间与周转时间。每次调度时,从所有进程中选出响应比最高的进程进行调度。
响应比 = (周转时间 + 响应时间)/ 周转时间
多级反馈队列调度算法:
多级反馈队列调度算法不需要事先知道各进程所需要的执行时间,实施过程如下:
1.设置多个就绪队列,并为其赋予不同的优先级。
2.赋予各队列中进程的时间片各不相同,优先级越高,时间片越小。
3.当一个新进程进入内存后,放入第一级队列末尾,按照FCFS原则等待调度。轮到该进程执行时,若能在该时间片内完成,便可以准备撤离系统;若在一个时间片结束时未能完成,则将其转入第二级队列末尾继续等待调度;若再不行则转入第三级队列末尾,以此类推。
4.当第一级队列为空时,才调度第二级队列;若在处理第n级队列中的某进程时,有一个新进程进入较高级队列中,则系统讲正在运行的进程放回第n级队列末尾,先执行较高级队列中的进程。
![](https://www.xuedaoniu.com/wp-content/themes/xuedaoniu/assets//img/xuexi/qrs_rgzn2.jpg)