research-article

Local-Deadline Assignment for Distributed Real-Time Systems

Authors:

Thidapat Chantem,

Xiaobo Sharon HuAuthors Info & Claims

IEEE Transactions on Computers, Volume 64, Issue 7

Pages 1983 - 1997

https://doi.org/10.1109/TC.2014.2349494

Published: 01 July 2015 Publication History

Abstract

In a distributed real-time system (DRTS), jobs are often executed on a number of processors and must complete by their end-to-end deadlines. Job deadline requirements may be violated if resource competition among different jobs on a given processor is not considered. This paper introduces a distributed, locally optimal algorithm to assign local deadlines to the jobs on each processor without any restrictions on the mappings of the applications to the processors in the distributed soft real-time system. Improved schedulability results are achieved by the algorithm since disparate workloads among the processors due to competing jobs having different paths are considered. Given its distributed nature, the proposed algorithm is adaptive to dynamic changes of the applications and avoids the overhead of global clock synchronization. In order to make the proposed algorithm more practical, two derivatives of the algorithm are proposed and compared. Simulation results based on randomly generated workloads indicate that the proposed approach outperforms existing work both in terms of the number of feasible jobs (between 51% and 313% on average) and the number of feasible task sets (between 12% and 71% on average).

References

[1]

[Online]. Available: http://lpsolve.sourceforge.net/5.5/, 1999.

[2]

S. K. Baruah, L. E. Rosier, and R. R. Howell, “ Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor,” Real-Time Syst., vol. 2, no. 4, pp. 301–324, Oct. 1990.

Digital Library

[3]

R. Bettati, and J. W.-S. Liu, “End-to-end scheduling to meet deadlines in distributed systems,” in Proc. 12th Int. Conf. Distrib. Comput. Syst., Jun. 1992, pp. 452–459 .

[4]

E. Bini and G. C. Buttazzo, “Biasing effects in schedulability measures,” in Proc. 16th Euromicro Conf. Real-Time Syst., Jul. 2004, pp. 196 –203.

Digital Library

[5]

G. Buttazzo, E. Bini, and Y. Wu, “Partitioning parallel applications on multiprocessor reservations,” in Proc. 22nd Euromicro Conf. Real-Time Syst., Jul. 2010, pp. 24–33.

[6]

G. C. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. New York, NY, USA: Springer, 2005.

[7]

S. Cavalieri, “Meeting real-time constraints in CAN,” IEEE Trans. Ind. Inform., vol. 1, no. 2, pp. 124– 135, May 2005.

[8]

H. Chetto, M. Silly, and T. Bouchentouf, “ Dynamic scheduling of real-time tasks under precedence constraints,” Real-Time Syst. , vol. 2, no. 3, pp. 181–194, Sep. 1990.

Digital Library

[9]

H. Chetto and M. Chetto, “Scheduling periodic and sporadic tasks in a real-time system,” Inf. Process. Lett., vol. 30, no. 4, pp. 177–184, Feb. 1989.

Digital Library

[10]

R. P. Dick, D. L. Rhodes, and W. Wolf, “TGFF: Task graphs for free,” in Proc. 6th Int. Workshop Hardware/Softw. Codesign, Mar. 1998, pp. 97–101.

[11]

S. Gopalakrishnan, L. Sha, and M. Caccamo, “Hard real-time communication in bus-based networks,” in Proc. 25th IEEE Int. Real-Time Syst. Symp., Dec. 2004, pp. 405–414.

Digital Library

[12]

A. Hagiescu, U. D. Bordoloi, S. Chakraborty, P. Sampath, P. V. V. Ganesan, and S. Ramesh, “Performance analysis of FlexRay-based ECU networks,” in Proc. 44th Annu. Des. Autom. Conf., Jun. 2007, pp. 284–289.

Digital Library

[13]

S. Hong, T. Chantem, and X. S. Hu, “Meeting end-to-end deadlines through distributed local deadline assignments,” in Proc. 32nd IEEE Real-Time Syst. Symp., Dec. 2011, pp. 183–192 .

[14]

S. Hua, G. Qu, and S. S. Bhattacharyya, “Probabilistic design of multimedia embedded systems,” ACM Trans. Embedd. Comput. Syst., vol. 6, no. 3, pp. 1–24, Jul. 2007.

[15]

P. Jayachandran and T. Abdelzaher, “Transforming distributed acyclic systems into equivalent uniprocessors under preemptive and non-preemptive scheduling,” in Proc. 20th Euromicro Conf. Real-Time Syst., Jul. 2008, pp. 233–242.

Digital Library

[16]

P. Jayachandran and T. Abdelzaher, “Delay composition in preemptive and non-preemptive real-time pipelines,” Real-Time Syst., vol. 40, no. 3, pp. 290– 320, Dec. 2008.

Digital Library

[17]

J. Jonsson and K. G. Shin, “Robust adaptive metrics for deadline assignment in distributed hard real-time systems,” Real-Time Syst., vol. 23, no. 3, pp. 239–271, Nov. 2002.

Digital Library

[18]

H. Kopetz, Real-Time Systems Design Principles for Distributed Embedded Applications . New York, NY, USA: Springer, 2011.

[19]

J. Lee, I. Shin, and A. Easwaran,“ Convex optimization framework for intermediate deadline assignment in soft and hard real-time distributed systems,” J. Syst. Softw., vol. 85, no. 10, pp. 2331–2339, 2012.

Digital Library

[20]

C. Lin, T. Kaldewey, A. Povzner, and S. A. Brandt, “Diverse soft real-time processing in an integrated system,” in Proc. 27th IEEE Int. Real-Time Syst. Symp., Dec. 2006, pp. 369–378.

Digital Library

[21]

C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, vol. 20, no. 1, pp. 46– 61, Jan. 1973.

Digital Library

[22]

J. W. Liu, Real-Time Systems. Upper Saddle River, NJ, USA : Prentice-Hall, 2000.

Digital Library

[23]

S. Manolache, P. Eles, and Z. Peng, “Optimization of soft real-time systems with deadline miss ratio constraints,” in Proc. 10th IEEE Real-Time Embedded Technol. Appl. Symp., May 2004, pp. 562– 570.

[24]

D. Marinca, P. Minet, and L. George, “Analysis of deadline assignment methods in distributed real-time systems,” Comput. Commun., vol. 27, no. 15, pp. 1412–1423, Jun. 2004.

Digital Library

[25]

S. Samii, P. Eles, Z. Peng, and A. Cervin, “Quality-driven synthesis of embedded multi-mode control systems,” in Proc. 46th Annu. Des. Autom. Conf., July 2009, pp. 864–869.

Digital Library

[26]

N. Serreli, G. Lipari, and E. Bini, “The distributed deadline synchronization protocol for real-time systems scheduled by EDF,” in Proc. IEEE Conf. Emerging Technol. Factory Autom., Sep. 2010, pp. 1–8.

[27]

N. Serreli, G. Lipari, and E. Bini, “Deadline assignment for component-based analysis of real-time transactions,” in Proc. 2nd Workshop Compositional Real-Time Syst., Dec. 2009.

[28]

Y. Zhang and R. West, “End-to-end window-constrained scheduling for real-time communication,” in Proc. IEEE 10th Int. Conf. Embedded Real-Time Comput. Syst. Appl., Aug. 2004, pp. 143–152.

[29]

W. Zheng, Q. Zhu, M. Di Natale, and A. Vincentelli, “Definition of task allocation and priority assignment in hard real-time distributed systems,” in Proc. 28th IEEE Int. Real-Time Syst. Symp., Dec. 2007, pp. 161–170 .

Digital Library

Cited By

Li CLi ZLi TLi CWang B(2023)A Deterministic Embedded End-System Tightly Coupled With TSN ScheduleIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.324850042:11(3707-3719)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3248500
Leng CQiao YHu XWang H(2020)Co-scheduling aperiodic real-time tasks with end-to-end firm and soft deadlines in two-stage systemsReal-Time Systems10.1007/s11241-020-09352-156:4(391-451)Online publication date: 21-Jul-2020
https://dl.acm.org/doi/10.1007/s11241-020-09352-1
Parashar M(2018)Editor's NoteIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.287670430:1(1-1)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1109/TPDS.2018.2876704
Show More Cited By

Index Terms

Local-Deadline Assignment for Distributed Real-Time Systems
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
  2. Real-time 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

Index terms have been assigned to the content through auto-classification.

Recommendations

Deadline Assignment in EDF Schedulers for Real-Time Distributed Systems
Real-time distributed systems contain end-to-end flows, which are distributed actions composed of sequences of tasks activated through messages. Such flows usually have an end-to-end deadline but the internal tasks and messages do not have specific timing ...
Generalized Elastic Scheduling for Real-Time Tasks

The elastic task model is a powerful model for adapting periodic real-time systems in the presence of uncertainty. This work generalizes the existing elastic scheduling approach in several directions. First, it presents a general framework, which ...
Schedulability Analysis of Global Scheduling Algorithms on Multiprocessor Platforms

Research on real-time scheduling algorithms for multiprocessor systems is a hot topic, due to the recent popularity of multicore hardware platforms. When executing applications with dynamic requirements on symmetric multiprocessor platforms, a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 64, Issue 7

July 2015

298 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 July 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li CLi ZLi TLi CWang B(2023)A Deterministic Embedded End-System Tightly Coupled With TSN ScheduleIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.324850042:11(3707-3719)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3248500
Leng CQiao YHu XWang H(2020)Co-scheduling aperiodic real-time tasks with end-to-end firm and soft deadlines in two-stage systemsReal-Time Systems10.1007/s11241-020-09352-156:4(391-451)Online publication date: 21-Jul-2020
https://dl.acm.org/doi/10.1007/s11241-020-09352-1
Parashar M(2018)Editor's NoteIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.287670430:1(1-1)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1109/TPDS.2018.2876704
He KMeng XPan ZYuan LZhou P(2018)A Novel Task-Duplication Based Clustering Algorithm for Heterogeneous Computing EnvironmentsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.285122130:1(2-14)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1109/TPDS.2018.2851221
Agrawal MManchanda KAgarwal ASaraswat SGupta AGupta HDutta T(2018)A Supervised Approach-based Job Scheduling Technique for Distributed Real-Time Systems2018 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS)10.1109/ANTS.2018.8710168(1-6)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.1109/ANTS.2018.8710168
Singh ADziurzanski PMendis HIndrusiak L(2017)A Survey and Comparative Study of Hard and Soft Real-Time Dynamic Resource Allocation Strategies for Multi-/Many-Core SystemsACM Computing Surveys10.1145/305726750:2(1-40)Online publication date: 11-Apr-2017
https://dl.acm.org/doi/10.1145/3057267

View Options

View options

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents