Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks

In this paper, we address the problem of the dynamic scheduling of skippable periodic task sets (i.e., period tasks allowing occasional skips of instances), together with aperiodic tasks. Scheduling of tasks is handled thanks to the merging of two existing approaches: the Skip-Over task model and th...

Full description

Saved in:
Bibliographic Details
Published in:Real-time systems 2006-02, Vol.32 (1-2), p.21-47
Main Authors: Marchand, Audrey, Silly-Chetto, Maryline
Format: Article
Language:English
Subjects:
Algorithms
Production scheduling
Response time (computers)
Skips
Task scheduling
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 this paper, we address the problem of the dynamic scheduling of skippable periodic task sets (i.e., period tasks allowing occasional skips of instances), together with aperiodic tasks. Scheduling of tasks is handled thanks to the merging of two existing approaches: the Skip-Over task model and the EDL (Earliest Deadline as Late as possible) aperiodic task server. The objective is to provide two on-line scheduling algorithms, namely EDL-RTO and EDL-BWP, in order to minimize the average response time of soft aperiodic requests, while ensuring that the QoS (Quality of Service) of periodic tasks will never be less than a specified bound. We also extend our results to the acceptance of sporadic tasks (i.e., aperiodic tasks with deadlines). We show that these novel scheduling algorithms have better performance compared to related algorithms regarding aperiodic response time and acceptance ratio.
ISSN:0922-6443
1573-1383
DOI:10.1007/s11241-006-4962-8