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

research-article

Constant bandwidth servers with constrained deadlines

Authors:

Alessandro Biondi,

Tommaso Cucinotta,

Giorgio ButtazzoAuthors Info & Claims

RTNS '17: Proceedings of the 25th International Conference on Real-Time Networks and Systems

Pages 68 - 77

https://doi.org/10.1145/3139258.3139285

Published: 04 October 2017 Publication History

Abstract

The Hard Constant Bandwidth Server (H-CBS) is a reservation-based scheduling algorithm often used to mix hard and soft real-time tasks on the same system. A number of variants of the H-CBS algorithm have been proposed in the last years, but all of them have been conceived for implicit server deadlines (i.e., equal to the server period). However, recent promising results on semi-partitioned scheduling together with the demand for new functionality claimed by the Linux community, urge the need for a reservation algorithm that is able to work with constrained deadlines. This paper presents three novel H-CBS algorithms that support constrained deadlines. The three algorithms are formally analyzed, and their performance are compared through an extensive set of simulations.

References

[1]

L. Abeni, G. Lipari, and J. Lelli. 2014. Constant bandwidth server revisited. In Proceedings of the Embed With Linux 2014 Workshop (EWiLi 2014) (CEUR Workshop Proceedings), Vol. 1291. Lisboa, Portugal. http://ceur-ws.org/Vol-1291

[2]

L. Abeni, L. Palopoli, C. Scordino, and G. Lipari. 2009. Resource Reservations for General Purpose Applications. IEEE Transactions on Industrial Informatics 5, 1 (Feb 2009), 12--21.

[3]

S. K. Baruah, L. E. Rosier, and R. R. Howell. 1990. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-time systems 2, 4 (1990), 301--324.

Digital Library

[4]

A. Biondi, A. Balsini, and M. Marinoni. 2015. Resource Reservation for Real-time Self-suspending Tasks: Theory and Practice. In Proc. of the 23rd International Conference on Real Time and Networks Systems (RTNS '15). ACM, 10.

Digital Library

[5]

A. Biondi, G. C. Buttazzo, and M. Bertogna. 2015. Supporting component-based development in partitioned multiprocessor real-time systems. In Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS 2015). Lund, Sweden.

Digital Library

[6]

A. Biondi, G. C. Buttazzo, and M. Bertogna. 2016. Schedulability Analysis of Hierarchical Real-Time Systems under Shared Resources. IEEE Trans. Comput. 65, 5 (2016), 1593--1605.

Digital Library

[7]

A. Biondi, A. Melani, and M. Bertogna. 2014. Hard Constant Bandwidth Server: Comprehensive Formulation and Critical Scenarios. In Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems (SIES 2014). Pisa, Italy.

[8]

B. Brandenburg and M. Gul. 2016. Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations. In Proceedings of the 37th IEEE Real-Time Systems Symposium (RTSS 2016). Porto, Portugal.

[9]

B. B. Brandenburg and J. H. Anderson. 2007. Integrating Hard/Soft Real-Time Tasks and Best-Effort Jobs on Multiprocessors. In 19th Euromicro Conference on Real-Time Systems (ECRTS'07). 61--70.

Digital Library

[10]

A. Burns, R. Davis, P. Wang, and F. Zhang. 2012. Partitioned EDF scheduling for multiprocessors using a C=D task splitting scheme. Real-Time Systems 48 (2012), 3--33.

Digital Library

[11]

G. C. Buttazzo. 2011. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Third Edition. Springer.

Digital Library

[12]

M. Caccamo, G. Buttazzo, and L. Sha. 2000. Capacity sharing for overrun control. In Proc. of the 21st IEEE conference on Real-time systems symposium. Orlando, Florida, USA.

Digital Library

[13]

D. Casini, A. Biondi, and G. Buttazzo. 2017. Semi-Partitioned Scheduling of Dynamic Real-Time Workload: A Practical Approach Based On Analysis-driven Load Balancing. In Proceedings of the 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Dubrovnik, Croatia.

[14]

J.J. Chen, G. Nelissen, and W.H. Huang. 2016. A unifying response time analysis framework for dynamic self-suspending tasks. In 28th Euromicro Conference on Real-Time Systems (ECRTS). IEEE.

[15]

J.J. Chen, G. Nelissen, W.-H. Huang, M. Yang, K. Bletsas B. Brandenburg, C. Liu, P. Richard, F. Ridouard, N. Audsley, R. Rajkumar, and D. de Niz. 2016. Many suspensions, many problems: A review of selfsuspending tasks in real-time systems. Technical Report. Faculty of Informatik, TU Dortmund.

[16]

U. M. C. Devi and J. H. Anderson. 2005. Tardiness bounds under global EDF scheduling on a multiprocessor. In 26th IEEE International Real-Time Systems Symposium (RTSS'05). 12 pp.--341.

Digital Library

[17]

P. Emberson, R. Stafford, and R. Davis. 2010. Techniques for the synthesis of multiprocessor tasksets. In Proc. of the 2nd International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010). Brussels, Belgium.

[18]

N. Fisher, T. P. Baker, and S. Baruah. 2006. Algorithms for Determining the Demand-Based Load of a Sporadic Task System. In 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'06). Sydney, Australia.

Digital Library

[19]

J. Lelli, C. Scordino, L. Abeni, and D. Faggioli. 2016. Deadline Scheduling in the Linux kernel. Software: Practice and Experience 46, 6 (Jun 2016), 821--839.

Digital Library

[20]

L. Marzario, G. Lipari, P. Balbastre, and A. Crespo. 2004. IRIS: A New Reclaiming Algorithm for Server-Based Real-Time Systems. In 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2004). Toronto, Canada.

Digital Library

[21]

C. W. Mercer, S. Savage, and H. Tokuda. 1994. Processor capacity reserves for multimedia operating systems. In Proceedings of IEEE international conference on Multimedia Computing and System. Boston, Massachusetts, USA.

[22]

A. K. Mok, X. Feng, and D. Chen. 2001. Resource partition for real-time systems. In Proceedings Seventh IEEE Real-Time Technology and Applications Symposium (RTAS 2001).

Digital Library

[23]

R. Rajkumar, K. Juvva, A. Molano, and S. Oikawa. 1998. Resource kernels: A resource-centric approach to real-time and multimedia systems. In SPIE/ACM Conference on Multimedia Computing and Networking. San Jose, CA, USA.

Digital Library

[24]

I. Shin and I. Lee. 2004. Compositional real-time scheduling framework. In Proceedings of the 25th IEEE Real-Time Systems Symposium (RTSS 2004). Lisbon, Portugal.

Digital Library

[25]

F. Zhang and A. Burns. 2009. Schedulability Analysis for Real-Time Systems with EDF Scheduling. IEEE Trans. Computers 58, 9 (2009), 1250--1258.

Digital Library

Cited By

Luo XJiang XGuan NLiang HLiu SYi W(2023)Modeling and Analysis of Inter-Process Communication Delay in ROS 22023 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS59052.2023.00026(198-209)Online publication date: 5-Dec-2023
https://doi.org/10.1109/RTSS59052.2023.00026
Becker MDasari DCasini D(2023)On the QNX IPC: Assessing Predictability for Local and Distributed Real-Time Systems2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00030(289-302)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00030
Tang YGuan NJiang XDong ZYi W(2023)Reaction Time Analysis of Event-Triggered Processing Chains with Data Refreshing2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10248012(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10248012
Show More Cited By

Index Terms

Constant bandwidth servers with constrained deadlines
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded software
  2. Real-time systems
    1. Real-time operating systems

Recommendations

Scheduling Aperiodic Tasks Using Total Bandwidth Server on Multiprocessors
EUC '08: Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing - Volume 01

This paper presents real-time scheduling techniques for reducing the response time of aperiodic tasks scheduled with real-time periodic tasks on multiprocessor systems. Two problems are addressed in this paper: (i) the scheduling of aperiodic tasks that ...
Designing network servers within a hierarchical scheduling framework
SAC '15: Proceedings of the 30th Annual ACM Symposium on Applied Computing

As distributed applications are becoming more complex, compositionality achieves a stronger importance. Such property allows composing complex applications, integrating independently developed components while maintaining their properties upon ...
LLF Schedulability Analysis on Multiprocessor Platforms
RTSS '10: Proceedings of the 2010 31st IEEE Real-Time Systems Symposium

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '17: Proceedings of the 25th International Conference on Real-Time Networks and Systems

October 2017

318 pages

ISBN:9781450352864

DOI:10.1145/3139258

Program Chairs:
Enrico Bini
University of Turin, Italy
,
Claire Pagetti
ONERA/ENSEEIHT/TUHH, Toulouse, France

Copyright © 2017 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

RTNS '17

RTNS '17: 25th International Conference on Real-Time Networks and Systems

October 4 - 6, 2017

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
103
Total Downloads

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

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luo XJiang XGuan NLiang HLiu SYi W(2023)Modeling and Analysis of Inter-Process Communication Delay in ROS 22023 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS59052.2023.00026(198-209)Online publication date: 5-Dec-2023
https://doi.org/10.1109/RTSS59052.2023.00026
Becker MDasari DCasini D(2023)On the QNX IPC: Assessing Predictability for Local and Distributed Real-Time Systems2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00030(289-302)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00030
Tang YGuan NJiang XDong ZYi W(2023)Reaction Time Analysis of Event-Triggered Processing Chains with Data Refreshing2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10248012(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10248012
Dasari DBecker MCasini DBlas T(2022)End-to-End Analysis of Event Chains under the QNX Adaptive Partitioning Scheduler2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS54340.2022.00025(214-227)Online publication date: May-2022
https://doi.org/10.1109/RTAS54340.2022.00025
Casini DBiondi A(2022)Placement of Chains of Real-Time Tasks on Heterogeneous Platforms under EDF Scheduling2022 25th Euromicro Conference on Digital System Design (DSD)10.1109/DSD57027.2022.00029(149-156)Online publication date: Aug-2022
https://doi.org/10.1109/DSD57027.2022.00029
BlaB TCasini DBozhko SBrandenburg B(2021)A ROS 2 Response-Time Analysis Exploiting Starvation Freedom and Execution-Time Variance2021 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS52674.2021.00016(41-53)Online publication date: Dec-2021
https://doi.org/10.1109/RTSS52674.2021.00016
Belluardo LStevanato ACasini DCicero GBiondi AButtazzo G(2021)A Multi-Domain Software Architecture for Safe and Secure Autonomous Driving2021 IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA52859.2021.00017(73-82)Online publication date: Aug-2021
https://doi.org/10.1109/RTCSA52859.2021.00017
Casini DBiondi AButtazzo G(2020)Task Splitting and Load Balancing of Dynamic Real-Time Workloads for Semi-Partitioned EDFIEEE Transactions on Computers10.1109/TC.2020.3038286(1-1)Online publication date: 2020
https://doi.org/10.1109/TC.2020.3038286
Quinones ERoyuela SScordino CGai PPinho LNogueira LRollo JCucinotta TBiondi AHamann AZiegenbein DSaoud HSoulat RForsberg BBenini LMando GRucher L(2020)The AMPERE Project: : A Model-driven development framework for highly Parallel and EneRgy-Efficient computation supporting multi-criteria optimization2020 IEEE 23rd International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC49007.2020.00042(201-206)Online publication date: May-2020
https://doi.org/10.1109/ISORC49007.2020.00042
Casini DBiondi AButtazzo G(2020)Timing isolation and improved scheduling of deep neural networks for real‐time systemsSoftware: Practice and Experience10.1002/spe.284050:9(1760-1777)Online publication date: Jun-2020
https://doi.org/10.1002/spe.2840
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