王铭伟, 吕华

（重庆邮电大学 通信与信息系统学院 重庆 400065）

0 引言

目前，大多机顶盒系统使用的Linux2.6内核中采用的是0（1）调度算法，此算法相对于Linux2.4核心的0（n）算法有了很大的改进。但由于在2.6内核中，仍然使用源自2.4核心的SCHED_FIFO（先入先出）和SCHED_RR（时间片轮转）作为对实时线程的调用的主要策略，对实时进程的调用效率上没有大的提升。在0（1）调度算法中，由于任务的优先级及抢占阈值都采用的是固定的整数[3]，并且等待任务的空闲时间遵循严格递减的规律[4]，造成了在任务执行过程中无法动态地分配CPU资源导致的实时性能降低。基于以上原因许多嵌入式系统中的Linux都引入了最小裕度算法，以期能达到动态分配优先级进而优化Linux2.6核心的实时调度性能的目的。不过，最小裕度算法也存在问题，若有两个优先级相近的进程同时运行，会出现两个线程间的频繁切换现象[5]。针对这一最小裕度算法的缺点，本文通过对其增加二级优先级进行了改进，使之能在一定程度下减小频繁切换造成的系统资源浪费[6]，并通过将之运用到机顶盒产品中，证明了该算法对于增强机顶盒系统实时性能方面的有效性。

1 最小裕度算法的改进与分析

1.1 最小裕度算法的改进

作为实时系统中较为常用的动态优先级调度算法，最小裕度优先(Least Slack First)调度算法是对最早截止期优先EDF算法的改进，根据任务所剩余的裕度（即剩余时间）的多少来分配优先级。裕度越少，任务就越紧急，就为之分配更高的优先级，以此保证紧急任务能够得到优先执行。……