FPSL, FPCL and FPZL schedulability analysis
FPSL, FPCL and FPZL schedulability analysis
复制标题
DOI：
10.1007/s11241-012-9149-x
复制
发表时间：
2012-03
影响因子：
1.3
通讯作者：
Robert I. Davis;S. Kato
中科院分区：
文献类型：
--
作者：
Robert I. Davis;S. Kato
本文提出了多处理器实时系统的固定优先级直到静态松弛（FPSL），固定优先级直到临界松弛（FPCL）和固定优先级直到零松弛（FPZL）调度算法。FPZL类似于全局固定优先级抢占式调度;然而，只要任务达到零松弛状态，它就被赋予最高优先级。FPSL和FPCL是FPZL的变体，除了固定优先级调度之外，它们不引入额外的调度点。FPSL，FPCL和FPZL是最小动态算法，即作业的优先级在其执行过程中最多只能改变一次，限制了抢占次数.本文给出了这些算法的多项式时间和伪多项式时间充分可调度性检验.然后通过计算每个任务在最高优先级下可以执行的执行量的上限来改进测试。实证评估表明，FPSL，FPCL和FPZL是非常有效的，与显着更大的数量的任务集被认为是可验证的本文中得出的测试，比最先进的可验证性测试EDZL调度。
This paper presents the Fixed Priority until Static Laxity (FPSL), Fixed Priority until Critical Laxity (FPCL) and Fixed Priority until Zero Laxity (FPZL) scheduling algorithms for multiprocessor real-time systems. FPZL is similar to global fixed priority pre-emptive scheduling; however, whenever a task reaches a state of zero laxity it is given the highest priority. FPSL and FPCL are variants of FPZL that introduce no additional scheduling points beyond those present with fixed priority scheduling. FPSL, FPCL and FPZL are minimally dynamic algorithms, in that the priority of a job can change at most once during its execution, bounding the number of pre-emptions.Polynomial time and pseudo-polynomial time sufficient schedulability tests are derived for these algorithms. The tests are then improved by computing upper bounds on the amount of execution that each task can perform at the highest priority. An empirical evaluation shows that FPSL, FPCL, and FPZL are highly effective, with a significantly larger number of tasksets deemed schedulable by the tests derived in this paper, than by state-of-the-art schedulability tests for EDZL scheduling.