Static-priority Real-time Scheduling: Response Time Computation is NP-hard

被引：39

作者：

Eisenbrand, Friedrich ^{[1
]}

Rothvoss, Thomas ^{[1
]}

机构：

[1] Ecole Polytech Fed Lausanne, Inst Math, CH-1015 Lausanne, Switzerland

来源：

RTSS: 2008 REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS | 2008年

关键词：

DIOPHANTINE APPROXIMATIONS;

D O I：

10.1109/RTSS.2008.25

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that response time computation for Rate-monotonic, preemptive scheduling of periodic tasks is NP-hard under Turing reductions. More precisely, we show that the response time of a task cannot be approximated within any constant factor, unless P = NP.

引用

页码：397 / 406

页数：10

共 20 条

[1] FIXED PRIORITY PREEMPTIVE SCHEDULING - AN HISTORICAL-PERSPECTIVE [J].

AUDSLEY, NC ;

BURNS, A ;

DAVIS, RI ;

TINDELL, KW ;

WELLINGS, AJ .

REAL-TIME SYSTEMS, 1995, 8 (2-3) :173-198

[2] An improved lower bound for approximating Shortest Integer Relation in l∞ norm (SIR∞) [J].

Chen, Wenbin ;

Meng, Jiangtao .

INFORMATION PROCESSING LETTERS, 2007, 101 (04) :174-179

[3] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[4] A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines [J].

Fisher, N ;

Baruah, S .

17TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS, PROCEEDINGS, 2005, :117-126

[5] DIFFERENCE BETWEEN CONSECUTIVE PRIMES [J].

HEATHBROWN, DR ;

IWANIEC, H .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1979, 1 (05) :758-760

[6]

HEATHBROWN DR, 1988, J REINE ANGEW MATH, V389, P22

[7] Diophantine approximations and integer points of cones [J].

Henk, M ;

Weismantel, R .

COMBINATORICA, 2002, 22 (03) :401-407

[8]

HENK M, 1997, ESA

[9] FINDING RESPONSE-TIMES IN A REAL-TIME SYSTEM [J].

JOSEPH, M ;

PANDYA, P .

COMPUTER JOURNAL, 1986, 29 (05) :390-395

[10] POLYNOMIAL-TIME AGGREGATION OF INTEGER PROGRAMMING-PROBLEMS [J].

KANNAN, R .

JOURNAL OF THE ACM, 1983, 30 (01) :133-145

← 1 2 →