优先级受限系统中可调度判定方法

在通信、雷达、导航以及各种消费类电子产品等民用和军事领域，嵌入式实时调度已逐渐成为电子电气系统的控制核心。针对同优先级任务使用FIFO调度的静态优先级系统，使用反例指出给定同优先级任务初始执行顺序的前提下，Katcher可调度判定条件的必要性不成立，提出并解析证明了FP可调度的充要条件。随机实验表明，对于高利用率下任务间执行时间差异较大的情况，约有15%的可调度任务集会被Katcher条件错判为不可调度。进一步的仿真和实例分析表明，Liu、Lehoczky、Bini等提出的条件不能判定相同优先级的情况，Katcher条件的必要性不成立，论文提到的条件能够正确判定任务集的可调度性。提出方法为实时系统调度的顶层设计提供了快速离线工具。

Schedulability analysis of fixed priority systems with limited priority levels

In the area of communication，radar，navigation and various electronic production，embedded real-time scheduling has became the control kernel of those electronic and electrical systems.In fixed priority systems where tasks with the same priority are queued in FIFO（First In First Out） order，counterexamples are used to point out that the necessary assertion of Katcher’s schedulability condition does not hold.A necessary and sufficient condition for fixed priority scheduling with limited priority levels is proposed and proved analytically.Stochastic analysis show that when the execution times of different tasks are remarkably distinct with each other，approximately 15% of schedulable task sets are misjudged by Katcher’s condition.Further simulations show that Liu’s condition，Lehoczky’s condition，and Bini’s condition cannot deal with tasks with the same priority，Katcher’s condition does not hold for its necessary assertion；meanwhile the condition provides the necessary and sufficient perspective of off-line schedulability checking.This method provides an off-line tool for top-down design of real-time scheduling with high utilization.