新闻  |   论坛  |   博客  |   在线研讨会
浅谈QNX的进程调度算法
xinjinlong | 2010-12-08 17:39:09    阅读:6878   发布文章

QNX的微内核提供的调度算法有:FIFO,轮询调度,适应调度,零星调度。前两种在任何一种OS中都会存在,再次不必多说,下面只对后两种进行说明:
适应调度( adaptive scheduling) 也存在QNX的其他版本中,如果一个线程在消耗完了自己的时间片时仍在运行,那么他的优先级就减一(优先级降低);即使他消耗完了另一时间片,此时他优先级也不会再下降,即只将一级;如果该线程被阻塞了,那么他的优先级立即回复为原来的优先级。

上图中A线程消耗完了自己的时间片后被降级,此时处于就绪状态的B线程获得了CPU资源。
由此可见这种算法不适合实时控制系统,它主要应用在后台有计算密集的任务并同时又要响应用户的交互信息,此时 ,计算计算线程可以有足够的CPU资源,同时对用户的请求又有很快的响应。
零星调度(sporadic scheduling)
实时任务可分为周期任务、非周期任务和零星任务。对于非周期任务和零星任务的调度方法通常是利用空闲时间及利用一个周期任务作为其服务器,定期地处理就绪的零星任务和非周期任务。
POSIX详细规定了适用于处理非周期性事件和零星事件以及静态优先级抢占调度条件下线程的零星调度策略。
系统调度零星事件的方法基本上有两种:基于空闲时间和基于服务器,无论哪种调度情况,首先要做可接受测试,进而对测试任务进行调度。
基于服务器的零星事件调度是指使用一个带宽预留服务器(p,e)专门调度零星事件,这个服务器一其他周期任务一起按照系统应用的调度策略被调度。消耗和补充规则确保每次到来的SS(零星服务器)都有确定的周期p和执行时间e。对于SS而言,最重要的是资源消耗和补充规则。负责的消耗和补充规则可以是SS的资源留更长的时间,补充资源更有竞争性,还可以平衡响应时间与执行时间的开销间的矛盾。
QNX在进程调度中新增加了此调度算法,采用是基于服务器的零星调度策略:
在这种算法之下一个线程动态可执行于正常优先级下和低优先级下。主要的可设定参数有:初始预算值(C) ,在正常优先级下允许执行的时间;低优先级(L) ,由于某种原因不可能再以正常优先级运行了,就将该线程的优先级降至此优先级;补充周期(T),只有在这个时间内线程才被允许消耗完它的初始预算值;最大补充周期数(M),对补充周期的发生次数进行限制。
实际上也主要是下面的这个结构体定义:
struct sched_param {
    int32_t  sched_priority;
    int32_t  sched_curpriority;
    union {
        int32_t  reserved[8];
        struct {   
            int32_t  __ss_low_priority; 
            int32_t  __ss_max_repl; 
            struct timespec     __ss_repl_period;  
            struct timespec     __ss_init_budget;  
        }           __ss;  
    }           __ss_un;   
}
#define sched_ss_low_priority   __ss_un.__ss.__ss_low_priority
#define sched_ss_max_repl       __ss_un.__ss.__ss_max_repl
#define sched_ss_repl_period    __ss_un.__ss.__ss_repl_period
#define sched_ss_init_budget    __ss_un.__ss.__ss_init_budget
各参数关系如下图所示:


当线程的优先级降低到低优先级时它有可能会被执行也有可能不被执行, 这取决于系统当时的其他线程的优先级了。一旦一个补充周期 T 的到来,该线程的优先级立即升至正常的优先级,这样只要适当的配置系统各主要线程的 C 和 T 就可以使得每个线程都可以在每个补充周期 T 内被执行 C 时间值,保证了该线程运行在正常优先级状态下消耗了 C/T% 系统资源。

下面从一个具体的实例来分析零星调度算法的工作过程:

在这个例子中预算值 C为 10msec,补偿周期T为40msec:
1、开始时本线程无阻塞的运行了3ms, 因此对应于这次运行的一个补充周期将会在第40ms处开始
2、该线程在第 6ms时又开始运行,此时它启动标记了另一个补充周期,并且在此期间它连续运行了 7ms,即消耗完了预算值 C;
3、由于预算值C被消耗完了,该线程的优先级主动降至设定的低优先级;另外一个补偿周期在46msec是发生;
4、在 40ms的时候,第一个补充周期结束了,此时它的优先级升至正常优先级;
5、该线程执行3ms然后又降至低优先级;
6、到 46ms 的时候重新给一个补充周期,此时它的优先级升至正常优先级,并执行 7ms
然后又转入低优先级
在这个调度算法控制之下,将一个线程需要执行的时间分拆成了若干段进行执行(这也就是
它名字的来由)。
这种算法通常应用在一个周期内具有执行时间上限的线程,可以使一个线程对非周期的事件进行服务而不要担心影响其他硬实时线程的执行期限。
总之:
第一:零星事件可以说都是实时事件
第二:保证每个补充周期可以搞定零星事件的执行时间,他也是可以被抢占的
第三:估计每个补充周期都有一次零星事件
下面是对此算法的一个验证结果:

*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。

参与讨论
登录后参与讨论
五湖四海皆朋友
最近文章
浅谈MIPS的MMU(二)
2016-08-16 19:33:41
浅谈MIPS的MMU(一)
2016-05-05 10:55:06
推荐文章
最近访客