Some Results of the Earliest Deadline Scheduling Algorithm

The problem of scheduling periodic time critical tasks on a monoprocessor computer system is examined. Such tasks consist of an infinite number of requests, each with a prescribed deadline. Tasks are assumed to meet their timing requirements when scheduled by the Earliest Deadline algorithm and pree...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on software engineering 1989-10, Vol.15 (10), p.1261-1269
Main Authors: Chetto, H., Chetto, M.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Application software
Computer programming
Control systems
Deadlines
Embedded systems
Fault tolerant systems
Processor scheduling
Real time
Real time systems
Schedules
Scheduling
Scheduling algorithm
Software engineering
Software performance
System performance
Systems design
Timing
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:The problem of scheduling periodic time critical tasks on a monoprocessor computer system is examined. Such tasks consist of an infinite number of requests, each with a prescribed deadline. Tasks are assumed to meet their timing requirements when scheduled by the Earliest Deadline algorithm and preemptions are allowed. The results are given of some investigations into the problem of making optimum use of the remaining processor idle time in scheduling periodic tasks either as soon as possible or as late as possible. The major results consist of the statement and proof of properties relating to localization and duration of idle time intervals. An efficient algorithm is developed for determining the maximum quantity of total idle time available between any 2 instants. In a real-time context, efficiency is necessary both for achieving the best use of the computer and for adhering to severe timing constraints relating to task executions.
ISSN:0098-5589
1939-3520
DOI:10.1109/TSE.1989.559777