research-article

The BGW model for QoS aware scheduling of real-time embedded systems

Authors:

Mohamed Ould Sass,

Maryline Chetto,

Audrey QueudetAuthors Info & Claims

MobiWac '13: Proceedings of the 11th ACM international symposium on Mobility management and wireless access

Pages 93 - 100

https://doi.org/10.1145/2508222.2508236

Published: 03 November 2013 Publication History

Get Access

Abstract

Tasks in a real-time computing system are commonly periodic. Each instance generated by the invocation of a periodic task has normally a deadline constraint by which it must complete its execution in all circumstances. However, faults may be present in software, the electrical power supply may be depleted, the processor may be overloaded transiently etc. Any of these emergencies involves a situation where it is no longer possible to meet the deadlines of all the instances in the application.

In this paper, we discuss a general model for the application task set that permits the operating system to correctly manage the above emergency situations in accordance with specific parameters statically attached to every task in addition to its classical timing parameters. The model is inspired by the well-known Deadline Mechanism and Skip-Over model. We introduce the BGW model where each instance of any periodic task can get one of the three colours Black, Grey and White. A colour specifies that the instance has to imperatively execute the primary version, the instance has to execute at least one version among primary and alternate or the instance may be discarded. We briefly discuss implementation issues for this new model.

References

[1]

G.C. Buttazzo, Luca Abeni. Elastic Task Model for Adaptive Rate Control, The 19th IEEE Real-Time Systems Symposium, pp. 286--295, 1998.

Digital Library

Google Scholar

[2]

M. Chetto-Silly. The EDL Server for Scheduling Periodic and Soft Aperiodic Tasks with Resource Constraints, Real-Time Systems, 17(1), pp 87--111, 1999.

Digital Library

Google Scholar

[3]

H. Chetto and M. Chetto. An adaptive scheduling algorithm for faulttolerant real-time system. Software engineering journal May 1991.

Digital Library

Google Scholar

[4]

H. Chetto, M. Chetto. Some Results of the Earliest Deadline Scheduling Algorithm. IEEE Transactions on Software Engineering, Volume 15, Issue 10, pp. 1261--1270, 1989.

Digital Library

Google Scholar

[5]

M. Hamdaoui, P. Ramanathan, A dynamic priority assignement technique for streams with (m, k)-firm deadlines, IEEE Transactions on Computers, vol. 44, no. 12, pp. 14431451, 1995.

Digital Library

Google Scholar

[6]

C.-C. Han, K.G. Shin, J. Wu. A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software Faults. IEEE Transactions on Computers, Vol. 52, no. 3, pp. 362--372, 2003.

Digital Library

Google Scholar

[7]

G. Koren, D. Shasha. Skip-over algorithms and complexity for overloaded systems that allow skips. Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS'95), Pisa, Italy, 1995.

Digital Library

Google Scholar

[8]

A.L. Liestman, R.H. Campbell, A Fault-Tolerant Scheduling Problem, IEEE Transactions on Software Engineering, vol. 12, no. 11, pp. 1089--1095, 1986.

Digital Library

Google Scholar

[9]

C.-L. Liu, J.-W. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. J. of the Association for Computing Machinery, 20(1), pp. 46--61, 1973.

Digital Library

Google Scholar

[10]

J. P. Lehozcky, L. Sha, Y. Ding. The rate-monotonic scheduling algorithm : exact characterization and average case behaviour. In Proceedings of the IEEE Real- Time Systems Symposium, pp. 166--171, 1989.

Google Scholar

[11]

A. Marchand, M. Chetto, Quality of Service Scheduling in Real-Time Systems, International Journal of Computers, Communications and Control, (ISSN 1841--9836), 3 (4), pp. 354--366, 2008.

Google Scholar

Cited By

View all

Vizzarri ADavide FCuevas ÁChatzimisios PDe Grande R(2016)QoE QoS Mapping for YouTube Services over LTE NetworkProceedings of the 14th ACM International Symposium on Mobility Management and Wireless Access10.1145/2989250.2989258(107-114)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.1145/2989250.2989258
Ismail HJawawi D(2014)A schedulability analysis for weakly hard real-time tasks in partitioning scheduling on multiprocessor systems2014 8th. Malaysian Software Engineering Conference (MySEC)10.1109/MySec.2014.6985998(108-112)Online publication date: Sep-2014
https://doi.org/10.1109/MySec.2014.6985998

Index Terms

The BGW model for QoS aware scheduling of real-time embedded systems
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks

Recommendations

A Fault-Tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems and Its Analysis

Many time-critical applications require dynamic scheduling with predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. In this paper, we propose an algorithm to dynamically schedule ...
Timing Analysis for Fixed-Priority Scheduling of Hard Real-Time Systems

This paper presents a timing analysis for a quite general hard real-time periodic task set on a uniprocessor using fixed-priority methods. Periodic tasks are composed of serially executed subtasks, where each subtask is characterized by an execution ...
Schedulability Analysis for Real-Time P-FRP Tasks under Fixed Priority Scheduling
RTCSA '15: Proceedings of the 2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications

This paper studies the schedulability of real-time tasks in the Priority-based Functional Reactive Programming (P-FRP) model under fixed priority scheduling, one of the influential scheduling policies. Since the abort-and-restart execution paradigm of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MobiWac '13: Proceedings of the 11th ACM international symposium on Mobility management and wireless access

November 2013

168 pages

ISBN:9781450323550

DOI:10.1145/2508222

General Chair:
Sotiris Nikoletseas
University of Patras and CTI, Greece
,
Program Chair:
Ángel Cuevas Rumín
Universidad Carlos III de Madrid, Spain

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: 03 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MSWiM '13

Sponsor:

SIGSIM

MSWiM '13: 16th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

November 3 - 8, 2013

Barcelona, Spain

Acceptance Rates

MobiWac '13 Paper Acceptance Rate 21 of 68 submissions, 31%;

Overall Acceptance Rate 83 of 272 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
43
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vizzarri ADavide FCuevas ÁChatzimisios PDe Grande R(2016)QoE QoS Mapping for YouTube Services over LTE NetworkProceedings of the 14th ACM International Symposium on Mobility Management and Wireless Access10.1145/2989250.2989258(107-114)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.1145/2989250.2989258
Ismail HJawawi D(2014)A schedulability analysis for weakly hard real-time tasks in partitioning scheduling on multiprocessor systems2014 8th. Malaysian Software Engineering Conference (MySEC)10.1109/MySec.2014.6985998(108-112)Online publication date: Sep-2014
https://doi.org/10.1109/MySec.2014.6985998

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

A Fault-Tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems and Its Analysis

Timing Analysis for Fixed-Priority Scheduling of Hard Real-Time Systems

Schedulability Analysis for Real-Time P-FRP Tasks under Fixed Priority Scheduling