Stability and Performance of List Scheduling with External Process Delays

J. S. Deogun, R. M. Kieckhafer, A. W. Krings

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

Non-preemptive static priority list scheduling is a simple, low-overhead approach to scheduling precedence-constrained tasks in real-time multiprocessor systems. However, it is vulnerable to anomalous timing behavior caused by variations in task durations. Specifically, reducing the duration of one task can delay the starting time of another task. This phenomenon, called Scheduling Instability, can make it difficult or impossible to guarantee real-time deadlines. Several heuristic solutions to handle scheduling instability have been reported. This paper addresses three main limitations in the state of the art in schedule stabilization. First, each stabilization technique only applies to a narrowly defined class of systems. To alleviate this constraint, we present an Extended Scheduling Model encompassing a wide range of assumptions about the scheduling environment, and address the stability problem under this model. Second, existing stabilization methods are heuristics based on a partial understanding of the causes of instability. We therefore derive a set of General Instability Conditions which are both necessary and sufficient for instability to occur. Third, solutions to scheduling instability range from trivial constraints on the run-time dispatcher through complex transformations of the precedence graph. We present scheduling simulation results comparing the average performance of several inherently stable run-time dispatchers of widely varying levels of complexity. Results show that for representative real-time workloads, simple low-overhead dispatchers perform nearly as well as a complex "minimally stabilized" dispatcher. Thus, complex schedule stabilization methods may be unnecessary, or even detrimental, due to their high computational overhead.

Original languageEnglish (US)
Pages (from-to)5-38
Number of pages34
JournalReal-Time Systems
Volume15
Issue number1
DOIs
Publication statusPublished - Jan 1 1998

    Fingerprint

Keywords

  • General instability conditions
  • Multiprocessor anomalies
  • Non-preemptive scheduling
  • Phantom tasks
  • Priority list scheduling
  • Scheduling stability

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering

Cite this