Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Optimal reward-based scheduling for periodic real-time tasks
Autore:
Aydin, H; Melhem, R; Mosse, D; Mejia-Alvarez, P;
Indirizzi:
Univ Pittsburgh, Dept Comp Sci, Pittsburgh, PA 15260 USA Univ Pittsburgh Pittsburgh PA USA 15260 omp Sci, Pittsburgh, PA 15260 USA IPN, CINVESTAV, Secc Computac, Mexico City 07300, DF, Mexico IPN Mexico City DF Mexico 07300 c Computac, Mexico City 07300, DF, Mexico
Titolo Testata:
IEEE TRANSACTIONS ON COMPUTERS
fascicolo: 2, volume: 50, anno: 2001,
pagine: 111 - 130
SICI:
0018-9340(200102)50:2<111:ORSFPR>2.0.ZU;2-E
Fonte:
ISI
Lingua:
ENG
Soggetto:
IMPRECISE COMPUTATIONS; ALGORITHMS; DEADLINES;
Keywords:
real-time systems; imprecise computation; periodic task scheduling; deadline scheduling; reward maximization;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
29
Recensione:
Indirizzi per estratti:
Indirizzo: Aydin, H Univ Pittsburgh, Dept Comp Sci, Pittsburgh, PA 15260 USA Univ Pittsburgh Pittsburgh PA USA 15260 Pittsburgh, PA 15260 USA
Citazione:
H. Aydin et al., "Optimal reward-based scheduling for periodic real-time tasks", IEEE COMPUT, 50(2), 2001, pp. 111-130

Abstract

Reward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part. The mandatory part must complete before the task's deadline, while a nondecreasing reward function is associated with the execution of the optional part, which can be interruptedat any time. Imprecise computation and Increased-Reward-with-increased-Service models fall within the scope of this framework. In this paper, we address the reward-based scheduling problem for periodic tasks. An optimal schedule is one where mandatory parts complete in a timely manner and the weighted average reward is maximized. For linear and concave reward functions, which are most common, we 1) show the existence of an optimal schedule wherethe optional service time of a task is constant at every instance and 2) show how to efficiently compute this service time. We also prove the optimality of Rate Monotonic Scheduling (with harmonic periods), Earliest DeadlineFirst, and Least Laxity First policies for the case of uniprocessors when used with the optimal service times we computed. Moreover, we extend our result by showing that any policy which can fully utilize all the processors is also optimal for the multiprocessor periodic reward-based scheduling. Toshow that our optimal solution is pushing the limits of reward-based scheduling, we further prove that, when the reward functions are convex, the problem becomes NP-Hard. Our static optimal solution, besides providing considerable reward improvements over the previous suboptimal strategies, also has a major practical benefit: Run-time overhead is eliminated and existing scheduling disciplines may be used without modification with the computed optimal service times.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 28/03/20 alle ore 22:20:14