On the Compatibility of Exact Schedulability Tests for Global Fixed Priority Preemptive Scheduling with Audsley’s Optimal Priority Assignment Algorithm

Robert Ian Davis; Marko Bertogna; Vincenzo Bonifaci

doi:10.1007/s11241-015-9241-0

On the Compatibility of Exact Schedulability Tests for Global Fixed Priority Preemptive Scheduling with Audsley’s Optimal Priority Assignment Algorithm

Robert Ian Davis, Marko Bertogna, Vincenzo Bonifaci

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Audsley’s Optimal Priority Assignment (OPA) algorithm can be applied to multiprocessor scheduling provided that three conditions hold with respect to the schedulability tests used. In this short paper, we prove that no exact test for global fixed priority pre-emptive scheduling of sporadic tasks can be compatible with Audsley’s algorithm, and hence the OPA algorithm cannot be used to obtain an optimal priority assignment for such systems.

Original language	English
Pages (from-to)	1-10
Number of pages	10
Journal	Real-Time Systems
Early online date	25 Sept 2015
DOIs	https://doi.org/10.1007/s11241-015-9241-0
Publication status	Published - 2015

Keywords

Real time scheduling
Global fixed priority pre-emptive scheduling
Optimal priority assignment
Exact schedulability tests
Sporadic tasks
Periodic tasks

Access to Document

10.1007/s11241-015-9241-0

INRIA International Chair
Davis, R. I. (Principal investigator)
1/10/14 → 30/09/19
Project: Other project › Research collaboration
MCC: Mixed Criticality Embedded Systems on Many-Core Platforms
Burns, A. (Principal investigator), Bate, I. J. (Co-investigator), Davis, R. I. (Co-investigator), Soares Indrusiak, L. (Co-investigator) & Harbin, J. R. (Researcher)
EPSRC
1/04/13 → 30/09/16
Project: Research project (funded) › Research

Cite this

@article{2423f08e57fa490382b6f633b636092d,

title = "On the Compatibility of Exact Schedulability Tests for Global Fixed Priority Preemptive Scheduling with Audsley{\textquoteright}s Optimal Priority Assignment Algorithm",

abstract = "Audsley{\textquoteright}s Optimal Priority Assignment (OPA) algorithm can be applied to multiprocessor scheduling provided that three conditions hold with respect to the schedulability tests used. In this short paper, we prove that no exact test for global fixed priority pre-emptive scheduling of sporadic tasks can be compatible with Audsley{\textquoteright}s algorithm, and hence the OPA algorithm cannot be used to obtain an optimal priority assignment for such systems. ",

keywords = "Real time scheduling, Global fixed priority pre-emptive scheduling, Optimal priority assignment , Exact schedulability tests, Sporadic tasks , Periodic tasks",

author = "Davis, {Robert Ian} and Marko Bertogna and Vincenzo Bonifaci",

year = "2015",

doi = "10.1007/s11241-015-9241-0",

language = "English",

pages = "1--10",

journal = "Real-Time Systems",

issn = "0922-6443",

publisher = "Springer",

}

TY - JOUR

T1 - On the Compatibility of Exact Schedulability Tests for Global Fixed Priority Preemptive Scheduling with Audsley’s Optimal Priority Assignment Algorithm

AU - Davis, Robert Ian

AU - Bertogna, Marko

AU - Bonifaci, Vincenzo

PY - 2015

Y1 - 2015

N2 - Audsley’s Optimal Priority Assignment (OPA) algorithm can be applied to multiprocessor scheduling provided that three conditions hold with respect to the schedulability tests used. In this short paper, we prove that no exact test for global fixed priority pre-emptive scheduling of sporadic tasks can be compatible with Audsley’s algorithm, and hence the OPA algorithm cannot be used to obtain an optimal priority assignment for such systems.

AB - Audsley’s Optimal Priority Assignment (OPA) algorithm can be applied to multiprocessor scheduling provided that three conditions hold with respect to the schedulability tests used. In this short paper, we prove that no exact test for global fixed priority pre-emptive scheduling of sporadic tasks can be compatible with Audsley’s algorithm, and hence the OPA algorithm cannot be used to obtain an optimal priority assignment for such systems.

KW - Real time scheduling

KW - Global fixed priority pre-emptive scheduling

KW - Optimal priority assignment

KW - Exact schedulability tests

KW - Sporadic tasks

KW - Periodic tasks

U2 - 10.1007/s11241-015-9241-0

DO - 10.1007/s11241-015-9241-0

M3 - Article

SN - 0922-6443

SP - 1

EP - 10

JO - Real-Time Systems

JF - Real-Time Systems

ER -

On the Compatibility of Exact Schedulability Tests for Global Fixed Priority Preemptive Scheduling with Audsley’s Optimal Priority Assignment Algorithm

Abstract

Keywords

Access to Document

Projects

INRIA International Chair

MCC: Mixed Criticality Embedded Systems on Many-Core Platforms

Cite this