research-article

Extending fixed task-priority schedulability by interference limitation

Authors:

José Manuel Marinho,

Stefan M. Petters,

Marko BertognaAuthors Info & Claims

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

Pages 191 - 200

https://doi.org/10.1145/2392987.2393012

Published: 08 November 2012 Publication History

Get Access

Abstract

While the earliest deadline first algorithm is known to be optimal as a uniprocessor scheduling policy, the implementation comes at a cost in terms of complexity. Fixed task-priority algorithms on the other hand have lower complexity but higher likelihood of task sets being declared unschedulable, when compared to earliest deadline first (EDF). Various attempts have been undertaken to increase the chances of proving a task set schedulable with similar low complexity. In some cases, this was achieved by modifying applications to limit preemptions, at the cost of flexibility. In this work, we explore several variants of a concept to limit interference by locking down the ready queue at certain instances. The aim is to increase the prospects of schedulability of a given task system, without compromising on complexity or flexibility, when compared to the regular fixed task-priority algorithm. As a final contribution, a new preemption threshold assignment algorithm is provided which is less complex and more straightforward than the previous method available in the literature.

References

[1]

S. Altmeyer, C. Maiza, and J. Reineke. Resilience analysis: tightening the crpd bound for set-associative caches. In LCTES 2010.

Digital Library

Google Scholar

[2]

M. Bertogna, G. Buttazzo, M. Marinoni, G. Yao, F. Esposito, and M. Caccamo. Preemption points placement for sporadic task sets. In ECRTS 2010.

Digital Library

Google Scholar

[3]

E. Bini and G. Buttazzo. Biasing effects in schedulability measures. In ECRTS 2004.

Digital Library

Google Scholar

[4]

A. Burns. Preemptive priority-based scheduling: an appropriate engineering approach. In S. H. Son, editor, Advances in real-time systems. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1995.

Digital Library

Google Scholar

[5]

U. Keskin, R. Bril, and J. Lukkien. Exact response-time analysis for fixed-priority preemption-threshold scheduling. In ETFA 2010.

Crossref

Google Scholar

[6]

W. Lamie. Preemption threshold. White paper, Express Logic. Available online.

Google Scholar

[7]

J. Marinho, V. Nélis, S. M. Petters, and I. Puaut. Preemption delay analysis for floating non-preemptive region scheduling. In DATE 2012.

Google Scholar

[8]

J. Marinho and S. M. Petters. Job phasing aware preemption deferral. EUC 2011.

Digital Library

Google Scholar

[9]

M. Saksena and Y. Wang. Scalable real-time system design using preemption thresholds. In RTSS 2000.

Digital Library

Google Scholar

[10]

Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In RTCSA 1999.

Digital Library

Google Scholar

[11]

G. Yao, G. Buttazzo, and M. Bertogna. Bounding the maximum length of non-preemptive regions under fixed priority scheduling. RTCSA 2009.

Digital Library

Google Scholar

[12]

G. Yao, G. Buttazzo, and M. Bertogna. Comparative evaluation of limited preemptive methods. In ETFA 2010.

Google Scholar

[13]

G. Yao, G. Buttazzo, and M. Bertogna. Feasibility analysis under fixed priority scheduling with limited preemptions. Journal Real-Time Systems, 47(3), 2011.

Digital Library

Google Scholar

Cited By

View all

Pinho LNélis VYomsi PQuiñones EBertogna MBurgio PMarongiu AScordino CGai PRamponi MMardiak M(2015)P-SOCRATESMicroprocessors & Microsystems10.1016/j.micpro.2015.06.00439:8(1190-1203)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.micpro.2015.06.004
Pinho LQuiñones EBertogna MMarongiu ACarlos JScordino CRamponi M(2014)P-SOCRATESProceedings of the 2014 17th Euromicro Conference on Digital System Design10.1109/DSD.2014.94(214-221)Online publication date: 27-Aug-2014
https://dl.acm.org/doi/10.1109/DSD.2014.94
Baldovin AMezzetti EVardanega TErnst RSokolsky O(2013)Limited preemptive scheduling of non-independent task setsProceedings of the Eleventh ACM International Conference on Embedded Software10.5555/2555754.2555772(1-10)Online publication date: 29-Sep-2013
https://dl.acm.org/doi/10.5555/2555754.2555772
Show More Cited By

Index Terms

Extending fixed task-priority schedulability by interference limitation
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling

Non-preemptive scheduling is usually considered inferior to preemptive scheduling for time critical systems, because the non-preemptive block would lead to poor task responsiveness. Although this is true in single-processor scheduling, we found by ...
Integration of Preemption Threshold and Quantum-Based Scheduling for Schedulability Enhancement of Fixed Priority Tasks
RTCSA '09: Proceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications

Fixed priority scheduling is an important real-time scheduling scheme widely used in practice. To improve the schedulability of fixed priority scheduling considerable effort has been made such as introduction of preemption threshold or deferred ...
Analysis on quantum-based fixed priority scheduling of real-time tasks
ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication

Fixed priority schedulers are widely used for real-time systems, and there were efforts to improve the schedulability. Preemption threshold scheduling is one of such efforts with a dual priority scheme. It increases the schedulability by introducing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

RTNS '12: Proceedings of the 20th International Conference on Real-Time and Network Systems

November 2012

216 pages

ISBN:9781450314091

DOI:10.1145/2392987

General Chairs:
Liliana Cucu-Grosjean
INRIA Nancy-Grand Est, France
,
Nicolas Navet
University of Luxembourg, Luxembourg
,
Program Chairs:
Christine Rochange
University of Toulouse/IRIT, France
,
James H. Anderson
University of North Carolina

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Social Fund
ARTEMIS JU

Conference

RTNS '12

Sponsor:

University of Lorraine
INRIA
GDR ASR

RTNS '12: 20th International Conference on Real-Time and Network Systems

November 8 - 9, 2012

Pont à Mousson, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
65
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pinho LNélis VYomsi PQuiñones EBertogna MBurgio PMarongiu AScordino CGai PRamponi MMardiak M(2015)P-SOCRATESMicroprocessors & Microsystems10.1016/j.micpro.2015.06.00439:8(1190-1203)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.micpro.2015.06.004
Pinho LQuiñones EBertogna MMarongiu ACarlos JScordino CRamponi M(2014)P-SOCRATESProceedings of the 2014 17th Euromicro Conference on Digital System Design10.1109/DSD.2014.94(214-221)Online publication date: 27-Aug-2014
https://dl.acm.org/doi/10.1109/DSD.2014.94
Baldovin AMezzetti EVardanega TErnst RSokolsky O(2013)Limited preemptive scheduling of non-independent task setsProceedings of the Eleventh ACM International Conference on Embedded Software10.5555/2555754.2555772(1-10)Online publication date: 29-Sep-2013
https://dl.acm.org/doi/10.5555/2555754.2555772
Baldovin AMezzetti EVardanega T(2013)Limited preemptive scheduling of non-independent task sets2013 Proceedings of the International Conference on Embedded Software (EMSOFT)10.1109/EMSOFT.2013.6658596(1-10)Online publication date: Sep-2013
https://doi.org/10.1109/EMSOFT.2013.6658596

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling

Integration of Preemption Threshold and Quantum-Based Scheduling for Schedulability Enhancement of Fixed Priority Tasks

Analysis on quantum-based fixed priority scheduling of real-time tasks