A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling

被引：9

作者：

Bonifaci, Vincenzo ^{[1
]}

Marchetti-Spaccamela, Alberto ^{[2
]}

Stiller, Sebastian ^{[3
]}

机构：

[1] Max Planck Inst Informat, Saarbrucken, Germany

[2] Sapienza Univ Roma, Rome, Italy

[3] Tech Univ Berlin, Berlin, Germany

来源：

ALGORITHMICA | 2012年 / 62卷 / 3-4期

关键词：

Sporadic task system; Multiprocessor; Real-time scheduling; Feasibility test; Earliest Deadline First; Approximation algorithm; SCHEDULABILITY ANALYSIS; EDF SCHEDULABILITY; GLOBAL EDF; SYSTEMS; TASKS;

D O I：

10.1007/s00453-011-9497-2

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model. We give an algorithm that, given a task system and epsilon > 0, correctly decides either that the task system can be scheduled using the Earliest Deadline First algorithm on m speed-(2-1/m+epsilon) machines, or that the system is not schedulable by any algorithm on m unit speed machines. This speedup bound is known to be the best possible for EDF. The running time of the algorithm is polynomial in the size of the task system and 1/epsilon. We also provide a generalized tight bound that trades off speed with additional machines.

引用

页码：1034 / 1049

页数：16

共 19 条

[1] Efficient feasibility analysis for real-time systems with EDF scheduling [J].