Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling

In prior work on soft real-time (SRT) multiprocessor scheduling, tardiness bounds have been derived for a variety of scheduling algorithms, most notably, the global earliest-deadline-first (G-EDF) algorithm. In this paper, we devise G-EDF-like (GEL) schedulers, which have identical implementations t...

Full description

Saved in:
Bibliographic Details
Published in:Real-time systems 2014, Vol.50 (1), p.5-47
Main Authors: Erickson, Jeremy P., Anderson, James H., Ward, Bryan C.
Format: Article
Language:English
Subjects:
Adjustment
Algorithms
Communications Engineering
Computer Science
Computer Systems Organization and Communication Networks
Control
Lateness
Linear programming
Mechatronics
Multiprocessing
Networks
Parameters
Performance and Reliability
Production scheduling
Robotics
Scheduling
Special Purpose and Application-Based Systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In prior work on soft real-time (SRT) multiprocessor scheduling, tardiness bounds have been derived for a variety of scheduling algorithms, most notably, the global earliest-deadline-first (G-EDF) algorithm. In this paper, we devise G-EDF-like (GEL) schedulers, which have identical implementations to G-EDF and therefore the same overheads, but that provide better tardiness bounds. We discuss how to analyze these schedulers and propose methods to determine scheduler parameters to meet several different tardiness bound criteria. We employ linear programs to adjust such parameters to optimize arbitrary tardiness criteria, and to analyze lateness bounds (lateness is related to tardiness). We also propose a particular scheduling algorithm, namely the global fair lateness (G-FL) algorithm, to minimize maximum absolute lateness bounds. Unlike the other schedulers described in this paper, G-FL only requires linear programming for analysis. We argue that our proposed schedulers, such as G-FL, should replace G-EDF for SRT applications.
ISSN:0922-6443
1573-1383
DOI:10.1007/s11241-013-9190-4