梁建明,金京林
(华南师范大学计算机学院, 广东广州 510631)
嵌入式实时操作系统,一方面需要具有低资源和低功耗的嵌入式系统特点,另一方面还需要满足实时性,以保证任务在可确定的相对短的时间内得到响应[1]. 在实时系统的任务调度中,调度策略最多的是采用优先级抢占式调度法[2]. μC/OS-Ⅱ是一种“硬实时”的嵌入式操作系统[3],是由Jean J Labrosse编写的一个源代码公开的抢占式实时内核[4],在嵌入式领域有着广泛的应用[5]. 它采用查表法的算法实现了最高优先级任务的快速查找,其查找的时间复杂度和任务数无关,但其空间复杂度会随着任务数的增加而呈几何级数的增长. 正因为这个关键因素,目前μC/OS-Ⅱ最大只能支持64个任务,而随着嵌入式应用的发展,会成为一个瓶颈.
本文在保持现有其它算法和数据结构不变的基础上,提出了一种查找最高优先级的新算法. 首先,为便于理解和比较新旧算法的区别,对现有的查找最高优先级的算法和主要数据结构进行了分析;然后,详细阐述了新算法的推导和实现过程;最后,对新旧算法在性能上作一些分析和比较.
μC/OS-Ⅱ目前能支持的最大任务数为64个,任务标识号同时也是任务优先级号,且唯一,与高优先级任务相比有较小的优先级号. 现有的算法是将这64个任务分为8组,每组包括8个任务. 图1为相关的数据结构示意图.

图1 现有算法的数据结构Figure 1 The data structure of existing algorithm
图1表明:任务优先级号Prio[6]是1个8比……