一种不影响任务集合可调度性的优先级映射算法  

A Priority Mapping Algorithm Without Affecting the Schedulability of Tasks Set

作　　者：王保进[1] 李明树[2] 

机构地区：[1]解放军信息工程大学信息工程学院,郑州450002 [2]中国科学院软件研究所互联网软件技术实验室

出　　处：《计算机研究与发展》2006年第6期1083-1089,共7页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2004AA1Z2050)~~

摘　　要：采用静态优先级调度的实时系统中,当任务个数多于优先级个数时,只能给多个任务分配相同的优先级·现有分配算法增大了高优先级任务的最坏情况响应时间,可能造成任务集合不可调度·利用抢占阈值的调度算法,能在提高任务集合可调度性的同时,使用较少的线程·但所用优先级个数没有减少·提出了一种优先级映射算法———阈值段间映射法(threshold segment mapping,TSM),以及与之配合的事件驱动线程框架·证明了TSM是严格排序的·仿真结果表明,在保证任务集合可调度的前提下,TSM使用了比现有映射算法更少的优先级·In practice, the schedulability of static priority scheduling may be reduced if priority levels of the system are insufficient. When the priority levels that a task set requires are more than the system can support, more than one task must be assigned the same priority. The priority mapping algorithms that have been used can augment the worst-case response time of task with higher priority, and may reduce the system schedulability. If keeping system schedulable, these algorithms may require more priority levels than the system can support. With preemption threshold scheduling model, the schedulability is improved as compared to both preemption and non-preemption scheduling models, and all tasks can be handled with the minimum number of event handling threads. But, the number of system priority levels that a thread needs does not be reduced. This paper presents a priority mapping algorithm called TSM （threshold segment mapping） and a thread implementation architecture with event-driven. It is shown that the TSM algorithm can maintain the strict order of tasks＇ priorities, and does not improve task＇s worst-case response time. The number of system priority levels used by the algorithm and architecture equals to that of threads. Simulations show that when maintaining system schedulability, the TSM algorithm uses less priority levels than existing priority mapping algorithms.

关 键 词：优先级映射 抢占阈值 非抢占组 事件驱动 严格排序 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]