A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearch

Abstract

Although preemptive scheduling dominates non-preemptive scheduling from a schedulability perspective, the latter will often be chosen by developers of real-time systems with resource constraints due to the inherently lower system overheads, easier code implementation and timing analysis. This paper is concerned with the uniprocessor scheduling of periodic and sporadic tasks with arbitrary relative deadlines in real-time systems using the non-preemptive version of the Earliest Deadline First (npEDF) algorithm. Although npEDF is known to be optimal among the non-preemptive work-conserving schedulers, it can still be restrictive in the sense that there exists uniprocessor-feasible task sets (with arbitrarily low CPU utilization) that are not schedulable with npEDF. For such task sets, system developers are forced to either consider the use of an alternate scheduling strategy or refactor the task software in some beneficial way. One such beneficial way is to apply a concept known as 'task splitting'. However to date, little guidance has been available to assist developers with the latter process, and it is often performed on an ad-hoc basis. This paper will propose the application of a fast and efficient task splitting technique to assist developers with this software refactoring process, which can thus be used to maximize the achievable CPU utilization whilst retaining the benefits of non-preemption. Examples and experimental results are given to illustrate the performance of the algorithm. For random but representative task sets, the results also indicate that in the average case only a relatively small number of tasks require the application of task splitting to become schedulable under npEDF.

Original languageEnglish
Title of host publication11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012
Pages1984-1993
Number of pages10
Publication statusPublished - 1 Dec 2012
Event11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012 - Helsinki, Finland
Duration: 25 Jun 201229 Jun 2012

Publication series

Name11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012
Volume3

Conference

Conference11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012
Abbreviated titlePSAM11 & ESREL 2012
CountryFinland
CityHelsinki
Period25/06/1229/06/12

Fingerprint

Scheduling
Real time systems
Program processors

Cite this

Short, M. (2012). A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF. In 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012 (pp. 1984-1993). (11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012; Vol. 3).
Short, Michael. / A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF. 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012. 2012. pp. 1984-1993 (11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012).
@inproceedings{2fc20d0854544a2eaf798f010ff24fa0,
title = "A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF",
abstract = "Although preemptive scheduling dominates non-preemptive scheduling from a schedulability perspective, the latter will often be chosen by developers of real-time systems with resource constraints due to the inherently lower system overheads, easier code implementation and timing analysis. This paper is concerned with the uniprocessor scheduling of periodic and sporadic tasks with arbitrary relative deadlines in real-time systems using the non-preemptive version of the Earliest Deadline First (npEDF) algorithm. Although npEDF is known to be optimal among the non-preemptive work-conserving schedulers, it can still be restrictive in the sense that there exists uniprocessor-feasible task sets (with arbitrarily low CPU utilization) that are not schedulable with npEDF. For such task sets, system developers are forced to either consider the use of an alternate scheduling strategy or refactor the task software in some beneficial way. One such beneficial way is to apply a concept known as 'task splitting'. However to date, little guidance has been available to assist developers with the latter process, and it is often performed on an ad-hoc basis. This paper will propose the application of a fast and efficient task splitting technique to assist developers with this software refactoring process, which can thus be used to maximize the achievable CPU utilization whilst retaining the benefits of non-preemption. Examples and experimental results are given to illustrate the performance of the algorithm. For random but representative task sets, the results also indicate that in the average case only a relatively small number of tasks require the application of task splitting to become schedulable under npEDF.",
author = "Michael Short",
year = "2012",
month = "12",
day = "1",
language = "English",
isbn = "9781622764365",
series = "11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012",
pages = "1984--1993",
booktitle = "11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012",

}

Short, M 2012, A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF. in 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012. 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012, vol. 3, pp. 1984-1993, 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, Helsinki, Finland, 25/06/12.

A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF. / Short, Michael.

11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012. 2012. p. 1984-1993 (11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012; Vol. 3).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearch

TY - GEN

T1 - A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF

AU - Short, Michael

PY - 2012/12/1

Y1 - 2012/12/1

N2 - Although preemptive scheduling dominates non-preemptive scheduling from a schedulability perspective, the latter will often be chosen by developers of real-time systems with resource constraints due to the inherently lower system overheads, easier code implementation and timing analysis. This paper is concerned with the uniprocessor scheduling of periodic and sporadic tasks with arbitrary relative deadlines in real-time systems using the non-preemptive version of the Earliest Deadline First (npEDF) algorithm. Although npEDF is known to be optimal among the non-preemptive work-conserving schedulers, it can still be restrictive in the sense that there exists uniprocessor-feasible task sets (with arbitrarily low CPU utilization) that are not schedulable with npEDF. For such task sets, system developers are forced to either consider the use of an alternate scheduling strategy or refactor the task software in some beneficial way. One such beneficial way is to apply a concept known as 'task splitting'. However to date, little guidance has been available to assist developers with the latter process, and it is often performed on an ad-hoc basis. This paper will propose the application of a fast and efficient task splitting technique to assist developers with this software refactoring process, which can thus be used to maximize the achievable CPU utilization whilst retaining the benefits of non-preemption. Examples and experimental results are given to illustrate the performance of the algorithm. For random but representative task sets, the results also indicate that in the average case only a relatively small number of tasks require the application of task splitting to become schedulable under npEDF.

AB - Although preemptive scheduling dominates non-preemptive scheduling from a schedulability perspective, the latter will often be chosen by developers of real-time systems with resource constraints due to the inherently lower system overheads, easier code implementation and timing analysis. This paper is concerned with the uniprocessor scheduling of periodic and sporadic tasks with arbitrary relative deadlines in real-time systems using the non-preemptive version of the Earliest Deadline First (npEDF) algorithm. Although npEDF is known to be optimal among the non-preemptive work-conserving schedulers, it can still be restrictive in the sense that there exists uniprocessor-feasible task sets (with arbitrarily low CPU utilization) that are not schedulable with npEDF. For such task sets, system developers are forced to either consider the use of an alternate scheduling strategy or refactor the task software in some beneficial way. One such beneficial way is to apply a concept known as 'task splitting'. However to date, little guidance has been available to assist developers with the latter process, and it is often performed on an ad-hoc basis. This paper will propose the application of a fast and efficient task splitting technique to assist developers with this software refactoring process, which can thus be used to maximize the achievable CPU utilization whilst retaining the benefits of non-preemption. Examples and experimental results are given to illustrate the performance of the algorithm. For random but representative task sets, the results also indicate that in the average case only a relatively small number of tasks require the application of task splitting to become schedulable under npEDF.

UR - http://www.scopus.com/inward/record.url?scp=84873169191&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781622764365

T3 - 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012

SP - 1984

EP - 1993

BT - 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012

ER -

Short M. A fast and efficient task splitting technique to maximize utilization in uniprocessor systems scheduled with non-preemptive EDF. In 11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012. 2012. p. 1984-1993. (11th International Probabilistic Safety Assessment and Management Conference and the Annual European Safety and Reliability Conference 2012, PSAM11 ESREL 2012).