More Web Proxy on the site http://driver.im/

research-article

Uniprocessor EDF scheduling of AVR task systems

Authors:

Sanjoy K. BaruahAuthors Info & Claims

ICCPS '15: Proceedings of the ACM/IEEE Sixth International Conference on Cyber-Physical Systems

Pages 159 - 168

https://doi.org/10.1145/2735960.2735976

Published: 14 April 2015 Publication History

Abstract

The adaptive varying-rate (AVR) task model has been proposed as a means of modeling certain physically-derived constraints in CPS's in a manner that is more accurate (less pessimistic) than is possible using prior task models from real-time scheduling theory. Existing work on schedulability analysis of systems of AVR tasks is primarily restricted to fixed-priority scheduling; this paper establishes schedulability analysis results for systems of AVR and sporadic tasks under Earliest Deadline First (EDF) scheduling. The proposed analysis techniques are evaluated both theoretically via the speedup factor metric, and experimentally via schedulability experiments on randomly-generated task systems.

References

[1]

R. Alur and D. Dill. A theory of timed automata. Theoretical Computer Science, 126: 183--235, 1994.

Digital Library

[2]

S. Baruah and Z. Guo. Mixed-criticality scheduling upon varying-speed processors. In Proceedings of the 34th IEEE Real-Time Systems Symposium (RTSS'13), 2013.

Digital Library

[3]

S. Baruah and Z. Guo. Scheduling mixed-criticality implicit-deadline sporadic task systems upon a varying-speed processor. In Proceedings of the 35th IEEE Real-Time Systems Symposium (RTSS'14), 2014.

[4]

S. Baruah, R. Howell, and L. Rosier. Feasibility problems for recurring tasks on one processor. Theoretical Computer Science, 118(1): 3--20, 1993.

Digital Library

[5]

S. K. Baruah, D. Chen, S. Gorinsky, and A. K. Mok. Generalized multiframe tasks. Real-Time Systems, 17(1): 5--22, 1999.

Digital Library

[6]

A. Bastoni, B. Brandenburg, and J. Anderson. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In Proceedings of the 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT'10), 2010.

[7]

J. Bengtsson, K. G. Larsen, F. Larsson, P. Pettersson, and W. Yi. Uppaal --- a Tool Suite for Automatic Verification of Real--Time Systems. In Proceedings of the Workshop on Verification and Control of Hybrid Systems III, pages 232--243, 1995.

Digital Library

[8]

A. Benveniste and G. Berry. The synchronous approach to reactive and real-time systems. Proceedings of the IEEE, 79(9): 1270--1282, 1991.

[9]

A. Benveniste, P. Caspi, S. A. Edwards, N. Halbwachs, P. Le Guernic, and R. de Simone. The synchronous languages 12 years later. Proceedings of the IEEE, 91(1): 64--83, 2003.

[10]

A. Biondi, A. Melani, M. Marinoni, M. Di Natale, and G. Buttazzo. Exact analysis of adaptive variable-rate tasks under fixed-priority scheduling. In Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS'14), 2014.

Digital Library

[11]

G. Buttazzo, E. Bini, and D. Buttle. Rate-adaptive tasks: Model, analysis, and design issues. In Proceedings of the International Conference on Design, Automation and Test in Europe (DATE'14), 2014.

Digital Library

[12]

D. Buttle. Real-time in the prime-time. In Keynote speech given at the 24th Euromicro Conference on Real-Time Systems (ECRTS'12), 2012.

[13]

R. I. Davis, T. Feld, V. Pollex, and F. Slomka. Schedulability tests for tasks with variable rate-dependent behaviour under fixed priority scheduling. In Proceedings of the 20th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'14), 2014.

[14]

N. Halbwachs. Synchronous programming of reactive systems. Kluwer Academic Publisherss, 1993.

Digital Library

[15]

K. Jeffay and D. Bennett. A rate-based execution abstraction for multimedia computing. In Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, 1995.

Digital Library

[16]

K. Jeffay and S. Goddard. A theory of rate-based execution. In Proceedings of the 20th IEEE Real-Time Systems Symposium (RTSS'99), pages 304--314, 1999.

Digital Library

[17]

J. Kim, K. Lakshmanan, and R. Rajkumar. Rhythmic tasks: A new task model with continually varying periods for cyber-physical systems. In Proceedings of the 3rd IEEE/ACM International Conference on Cyber-Physical Systems (ICCPS'12), pages 28--38, 2012.

Digital Library

[18]

C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1): 46--61, 1973.

Digital Library

[19]

A. K. Mok. Fundamental Design Problems of Distributed Systems for The Hard-Real-Time Environment. PhD thesis, Massachusetts Institute of Technology, 1983.

Digital Library

[20]

A. K. Mok and D. Chen. A multiframe model for real-time tasks. IEEE Transactions on Software Engineering, 23(10): 635--645, 1997.

Digital Library

[21]

V. Pollex, T. Feld, F. Slomka, U. Margull, R. Mader, and G. Wirrer. Sufficient real-time analysis for an engine control unit. In Proceedings of the 21st International Conference on Real-Time and Networked Systems (RTNS'13), pages 247--254, 2013.

Digital Library

[22]

V. Pollex, T. Feld, F. Slomka, U. Margull, R. Mader, and G. Wirrer. Sufficient real-time analysis for an engine control unit with constant angular velocities. In Proceedings of the International Conference on Design, Automation and Test in Europe (DATE'13), pages 1335--1338, 2013.

Digital Library

[23]

M. Stigge, P. Ekberg, N. Guan, and W. Yi. The digraph real-time task model. In Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'11), pages 71--80, 2011.

Digital Library

[24]

M. Stigge, P. Ekberg, N. Guan, and W. Yi. On the tractability of digraph-based task models. In Proceedings of the 22th Euromicro Conference on Real-Time Systems (ECRTS'11), pages 162--171, 2011.

Digital Library

[25]

D. Vivien. Lexus LFA instruments. Evo magazine, page 202, 2013.

Cited By

Yao NZhang F(2024)From instantaneous schedulability to worst case schedulability: a significant moment approachCyber-Physical Systems10.1080/23335777.2024.2426245(1-33)Online publication date: 25-Nov-2024
https://doi.org/10.1080/23335777.2024.2426245
Zhou QHuang JLi JLi Z(2022)Response Time Analysis for Hybrid Task Sets under Fixed Priority Scheduling2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS54340.2022.00017(108-120)Online publication date: May-2022
https://doi.org/10.1109/RTAS54340.2022.00017
Sadeghi MPhilippi MMahdian ASlomka F(2022)MIAT Efficient analysis of adaptive variable-rate tasks▪Journal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2022.102472127:COnline publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.sysarc.2022.102472
Show More Cited By

Index Terms

Uniprocessor EDF scheduling of AVR task systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling
    2. Software system structures
      1. Embedded software
      2. Real-time systems software

Recommendations

Preempt a Job or Not in EDF Scheduling of Uniprocessor Systems

The earliest-deadline-first (EDF) policy has been widely studied for the scheduling of real-time jobs for its effectiveness and simplicity. However, since each preemption incurs an additional delay to the execution of jobs, the effectiveness of EDF is ...
Uniprocessor Scheduling Strategies for Self-Suspending Task Systems
RTNS '16: Proceedings of the 24th International Conference on Real-Time Networks and Systems

We study uniprocessor scheduling for hard real-time self-suspending task systems where each task may contain a single self-suspension interval. We focus on improving state-of-the-art fixed-relative-deadline (FRD) scheduling approaches, where an FRD ...
Worst Case Response Time Analysis of Sporadic Task Graphs with EDF Non-preemptive Scheduling on a Uniprocessor
ICAS '07: Proceedings of the Third International Conference on Autonomic and Autonomous Systems

This paper considers the problem of non-preemptive hard real-time scheduling of sporadic task graphs on a uniprocessor with Earliest Deadline First (EDF) scheduling. A sporadic task graph associated to an application is characterized by a set of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCPS '15: Proceedings of the ACM/IEEE Sixth International Conference on Cyber-Physical Systems

April 2015

269 pages

ISBN:9781450334556

DOI:10.1145/2735960

General Chairs:
Alexandre Bayen
University of California, Berkeley
,
Michael Branicky
University of Kansas

Copyright © 2015 ACM.

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]

Sponsors

IEEE
IEEE-CSS: Control Systems Society
IEEE-CS\TCRT: TC on Real-Time Systems
IEEE Signal Processing Society
ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 April 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

ICCPS '15

Sponsor:

IEEE-CSS
IEEE-CS\TCRT
ACM
SIGBED

ICCPS '15: ACM/IEEE 6th International Conference on Cyber-Physical Systems

April 14 - 16, 2015

Washington, Seattle

Acceptance Rates

ICCPS '15 Paper Acceptance Rate 25 of 91 submissions, 27%;

Overall Acceptance Rate 25 of 91 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
250
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yao NZhang F(2024)From instantaneous schedulability to worst case schedulability: a significant moment approachCyber-Physical Systems10.1080/23335777.2024.2426245(1-33)Online publication date: 25-Nov-2024
https://doi.org/10.1080/23335777.2024.2426245
Zhou QHuang JLi JLi Z(2022)Response Time Analysis for Hybrid Task Sets under Fixed Priority Scheduling2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS54340.2022.00017(108-120)Online publication date: May-2022
https://doi.org/10.1109/RTAS54340.2022.00017
Sadeghi MPhilippi MMahdian ASlomka F(2022)MIAT Efficient analysis of adaptive variable-rate tasks▪Journal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2022.102472127:COnline publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.sysarc.2022.102472
Sun ZGuo MLiu X(2021)A Survey of Real-Time Scheduling on Multiprocessor SystemsTheoretical Computer Science10.1007/978-981-16-7443-3_7(89-118)Online publication date: 10-Nov-2021
https://doi.org/10.1007/978-981-16-7443-3_7
Sun JShi RWang KGuan NGuo Z(2020)Efficient Feasibility Analysis for Graph-based Real-Time Task SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.3012174(1-1)Online publication date: 2020
https://doi.org/10.1109/TCAD.2020.3012174
Liu YPeng CZhao YLi YZeng H(2020)Schedulability Analysis of Engine Control Systems With Dynamic Switching SpeedsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.295112439:10(2067-2080)Online publication date: Oct-2020
https://doi.org/10.1109/TCAD.2019.2951124
Peng CZhao YZeng H(2019)Dynamic Switching Speed Reconfiguration for Engine Performance OptimizationProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3317806(1-6)Online publication date: 2-Jun-2019
https://dl.acm.org/doi/10.1145/3316781.3317806
Feld TSlomka F(2019)A Sufficient Response Time Analysis Considering Angular Phases Between Rate-Dependent TasksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.287816338:11(2008-2021)Online publication date: Nov-2019
https://doi.org/10.1109/TCAD.2018.2878163
Shambharkar PBhambri SGoel ADoja M(2019)A Survey on Schedulability Analysis of Rate-Adaptive Tasks2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon)10.1109/COMITCon.2019.8862266(277-282)Online publication date: Feb-2019
https://doi.org/10.1109/COMITCon.2019.8862266
Xie GZeng GLi RLi KXie GZeng GLi RLi K(2019)Application on Automotive Cyber-Physical SystemsScheduling Parallel Applications on Heterogeneous Distributed Systems10.1007/978-981-13-6557-7_5(181-206)Online publication date: 7-Aug-2019
https://doi.org/10.1007/978-981-13-6557-7_5
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents