＋设为首页 ＋添加到收藏夹
下面,本文将简要介绍优先级调度与运行前调度方法. 【程序编程相关:经典陷害大全】
优先级调度与运行前调度概述 【推荐阅读:我认为学习linux的顺序】
大多数优先级调度方法均遵循两个基本假定:a)调度在进程运行时执行;b)进程分配有固定的优先级,当两个进程竞争同一处理器时,具有较高优先级的进程将获得处理器资源. 【扩展信息:MRTG配置完整全功略】
1.优先级调度方法
速率单调调度(rate monotonic scheduling)是最具代表性的优先级调度方法.该方法假定所有的进程都是周期性的,并且进程的主要特性在运行之前都已确定,即预先了解进程在最坏情形下的执行时间与周期.
设计工程师可根据进程的周期设定固定的优先级:周期越短,优先级越高.任何时候,只要所有进程中具有最高优先级的进程就绪,即可分配到处理器.而且在运行前,还可根据已知的进程特性进行可调度性分析.如果满足特定的方程,即可在运行中执行实际的调度,并假定运行中可以满足所有的时限要求.
优先级最高限度协议(priority ceiling protocol)的假定与速率单调调度相同,只是进程可能具有由旗语(semaphores)保护的临界区,并提供专门的协议来处理这些临界区.每个旗语均分配一个优先级最高限度值,优先级最高限度与使用该旗语的最高优先级进程具有相等的优先级.具有最高优先级的进程一旦就绪,即可分配到处理器资源.任何进程p进入其临界区之前,必须首先获取监控临界区的旗语s的优先级锁定.如果进程p的优先级不高于当前除p以外,其它进程锁定的旗语中具有最高优先级的最高限度,那么进程p将被阻塞,s上的锁定将被拒绝.当进程p阻塞了更高优先级的进程,那么p将继承被p阻塞的进程的最高优先级.
当p离开临界区,则进程p将恢复其进入临界区时的优先级.如果进程p不试图进入临界区,并且其优先级(继承或分配的优先级)高于另一正在执行的进程pi的优先级,则可占先运行.
如果满足以下条件,则速率单调调度(周期越短,优先级越高)可以调度(即满足所有时限要求)采用优先级最高限度协议的n个周期性进程:其中ci 表示执行时间,ti 表示周期,bi 表示最坏情形下由较低优先级进程引发的pi阻塞时间.
2.运行前调度方法
采用运行前调度,一般进程的调度是离线计算;同时,该方法还要求能够预先了解系统中进程的主要特性.
采用运行前调度的方法对周期性进程进行调度是可能的.该方法由调度的离线计算(computing off-line)与调度运行两部分组成,即离线计算周期值等于给定进程集周期的最小公倍数的全部周期进程的调度,并根据先前计算的调度策略执行周期性进程.
在运行前调度中,对给定的周期可离线地计算多个可选调度,而每个调度都对应于不同的操作“模式”.一个小的运行时间调度器可在对应于外部或内部事件的可选调度中进行选择,而小的运行时间调度器也可用来为数目较少,且时限极短的异步进程分配资源.
如果预先了解两个连续请求之间的最短时间,那么就可将异步进程转化为等价的周期性进程.因此,也可以采用运行前调度方法调度异步进程.
运行前调度与优先级调度的比较
下面将简要说明优先级调度方法的缺点.可以看到无论是速率单调调度还是优先级最高限度协议,优先级调度都无法为某类问题提供可行的解决方案,而采用运行前调度的最优算法则可以解决.这些缺点直接源于固定优先级调度方法中固有的基本假定,而不仅仅是基于该调度方法的某个特定运算或公式的特性.因此,这些缺点并不能通过某些设计巧妙的快速修复(quick fix)技术加以弥补.
1. 优先级调度方法难以处理复杂的应用约束问题
文章给出的可调度性分析假定所有的任务都是独立的,即任务之间不存在优先关系,并且释放时间等于周期的起始时间.我们很难延伸优先级调度方法的可调度性分析,来考虑那些通常在实时应用中存在的应用约束,如优先约束.释放时间不等于周期的起始时间.低抖动要求等.主要由于以下两个原因:
(a)附加的应用约束很可能与分配给进程的优先级相冲突,一般不可能将大型复杂系统中不同应用约束所需的诸多不同进程执行序列映射到严格的优先级层次.
... 下一页