Skip to Main content Skip to Navigation
Reports

Systematic Searches for Global Multiprocessor Real-Time Scheduling

Olivier Buffet 1 Liliana Cucu-Grosjean 2 
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we address the problem of global real-time periodic scheduling on homogeneous multiprocessor platforms. A number of theoretical results have been obtained in the field of real-time systems, but mainly focusing on properties of specific algorithms in uniprocessor settings. The multiprocessor case has been considered only recently, with few resolution techniques proposed and experimented with up to now. In this paper we discuss several systematic search algorithms—exploring different search spaces—that exploit various features of the problem. These approaches are then evaluated experimentally on numerous randomly generated problems. This work shows (1) how two heuristic approaches can solve most (feasible and unfeasible) problems in no time, and (2) how to improve a state of the art algorithm by looking at jobs' laxities and by focusing the search on bottlenecks. We also discuss limitations of the proposed solvers and future work.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00519324
Contributor : Olivier Buffet Connect in order to contact the contributor
Submitted on : Sunday, September 19, 2010 - 10:40:28 PM
Last modification on : Wednesday, February 2, 2022 - 3:51:33 PM
Long-term archiving on: : Tuesday, October 23, 2012 - 4:21:00 PM

File

RR-7386.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00519324, version 1

Collections

Citation

Olivier Buffet, Liliana Cucu-Grosjean. Systematic Searches for Global Multiprocessor Real-Time Scheduling. [Research Report] RR-7386, INRIA. 2010, pp.17. ⟨inria-00519324⟩

Share

Metrics

Record views

97

Files downloads

104