Comment on "A pre-run-time scheduling algorithm for hard real-time systems"

Author

Abdelzaher, Tarek F. ; Shin, Kang G.

Author_Institution

Real-Time Comput. Lab., Michigan Univ., Ann Arbor, MI, USA

Volume

23

Issue

9

fYear

1997

Firstpage

599

Lastpage

600

Abstract

In Shepard and Gagne (1991), a branch-and-bound implicit enumeration algorithm is described whose purpose is to generate a feasible schedule, if any, for each processor on a multiprocessing node running hard real-time processes. The optimization criterion is to minimize process lateness defined as the difference between the process completion time and deadline. We show in this correspondence that this algorithm does not always succeed in finding a feasible solution, and describe the reason why the algorithm might fail.

Keywords

minimisation; multiprocessing systems; parallel algorithms; processor scheduling; real-time systems; tree searching; branch-and-bound implicit enumeration algorithm; deadline; hard real-time systems; multiprocessing node; optimization; pre-run-time scheduling algorithm; process completion time; process lateness minimization; processor scheduling; Application software; Computational modeling; Costs; Processor scheduling; Real time systems; Runtime; Scheduling algorithm; Software maintenance; Stochastic processes; Timing;

fLanguage

English

Journal_Title

Software Engineering, IEEE Transactions on

Publisher

ieee

ISSN

0098-5589

Type

jour

DOI

10.1109/32.629495

Filename

629495