Document Open Access Logo

Scheduling Replica Voting in Fixed-Priority Real-Time Systems

Authors Pietro Fara , Gabriele Serra , Alessandro Biondi, Ciro Donnarumma

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2021.13.pdf
  • Filesize: 0.88 MB
  • 21 pages

Document Identifiers

Author Details

Pietro Fara
  • Scuola Superiore Sant'Anna, Pisa, Italy
Gabriele Serra
  • Scuola Superiore Sant'Anna, Pisa, Italy
Alessandro Biondi
  • Scuola Superiore Sant'Anna, Pisa,Italy
Ciro Donnarumma
  • Rete Ferroviaria Italiana S.P.A., Rome, Italy
  • Scuola Superiore Sant'Anna, Pisa, Italy

Cite As Get BibTex

Pietro Fara, Gabriele Serra, Alessandro Biondi, and Ciro Donnarumma. Scheduling Replica Voting in Fixed-Priority Real-Time Systems. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ECRTS.2021.13

Abstract

Reliability and safety are mandatory requirements for safety-critical embedded systems. The design of a fault-tolerant system is required in many fields (e.g., railway, automotive, avionics) and redundancy helps in achieving this goal. Redundant systems typically leverage voting techniques applied to the outputs produced by tasks to detect and even tolerate failures. 
This paper studies the integration of distributed voting protocols in fixed-priority real-time systems from a scheduling perspective. It analyzes two scheduling strategies for implementing voting. One is attractive and friendly for software developers and based on suspending the task execution until the replica provides the data to be voted. The other one is inspired by the Logical Execution Time (LET) paradigm and requires introducing additional tasks in the system to accomplish voting-related activities. Queuing and delays introduced by inter-replica communication interfaces are also analyzed.
Experimental results are finally presented to compare the two strategies, showing that LET-inspired voting is much more predictable and hence more suitable than the other strategy for fixed-priority real-time systems.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Dependable and fault-tolerant systems and networks
  • Computer systems organization → Real-time systems
Keywords
  • Real-time systems
  • safety-critical systems
  • voting
  • redundancy
  • fault-tolerance
  • logical execution time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jaemin Baek, Jeonghyun Baek, Jeeheon Yoo, and Hyeongboo Baek. An n-modular redundancy framework incorporating response-time analysis on multiprocessor platforms. Symmetry, 11(8):960, 2019. Google Scholar
  2. Julian M Bass. Voting in real-time distributed computer control systems. PhD thesis, University of Sheffield, 1995. Google Scholar
  3. H Benítez-Pérez, G Latif-Shabgahi, HA Thompson, S Bennett, PJ Fleming, and JM Bass. Integration and comparison of fdi and fault masking features in embedded systems. IFAC Proceedings Volumes, 32(2):7712-7717, 1999. Google Scholar
  4. Guillem Bernat, Jose Miro-Julia, and Julian Proenza. A technique to analyze the tolerance to transient overloads of a fault-tolerant real-time system. In Proceedings 1997 High-Assurance Engineering Workshop, pages 221-226. IEEE, 1997. Google Scholar
  5. Guillem Bernat, Jose Miro-Julia, Julian Proenza, et al. Fixed priority schedulability analysis of a distributed real-time fault tolerant architecture. In PDPTA, pages 479-487, 1997. Google Scholar
  6. Dimitri Bertsekas and Robert Gallager. Data Networks (2nd Ed.). Prentice-Hall, Inc., USA, 1992. Google Scholar
  7. DM Blough and GF Sullivan. Voting using predispositions. IEEE Transactions on reliability, 43(4):604-616, 1994. Google Scholar
  8. Douglas M Blough and Gregory F Sullivan. A comparison of voting strategies for fault-tolerant distributed systems. In Proceedings Ninth Symposium on Reliable Distributed Systems, pages 136-145. IEEE, 1990. Google Scholar
  9. B. Brandenburg. Scheduling and locking in multiprocessor real-time operating systems. In Ph.D. dissertation, The University of North Carolina at Chapel Hill, 2011. Google Scholar
  10. D. Casini, A. Biondi, G. Nelissen, and G. Buttazzo. Partitioned fixed-priority scheduling of parallel tasks without preemptions. In 2018 IEEE Real-Time Systems Symposium (RTSS), pages 421-433, 2018. URL: https://doi.org/10.1109/RTSS.2018.00056.
  11. EN CEI. Cei en 50126-1. Railway Applications - The Specification and Demonstration of Reliability, Availability, Maintainability and Safety (RAMS). Part 1: Generic RAMS Process, 2019. Google Scholar
  12. EN CEI. Cei en 60730-1. Automatic electrical controls - Part1: General requirements, 2019. Google Scholar
  13. J. Chen, G. Nelissen, and W. Huang. A unifying response time analysis framework for dynamic self-suspending tasks. In 2016 28th Euromicro Conference on Real-Time Systems (ECRTS), pages 61-71, 2016. URL: https://doi.org/10.1109/ECRTS.2016.31.
  14. Daniel Davies and John F. Wakerly. Synchronization and matching in redundant systems. IEEE Computer Architecture Letters, 27(06):531-539, 1978. Google Scholar
  15. P. Emberson, R. Stafford, and R.I. Davis. Techniques for the synthesis of multiprocessor tasksets. In 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), pages 6-11, July 2010. Google Scholar
  16. Oytun Eriş, Uğur Yıldırım, Mustafa S Durmuş, Mehmet T Söylemez, and Salman Kurtulan. N-version programming for railway interlocking systems: Synchronization and voting strategy. IFAC Proceedings Volumes, 45(24):177-180, 2012. Google Scholar
  17. Saurabh Gohil, Aravind Basavalingarajaiah, and Varadharajan Ramachandran. Redundancy management and synchronization in avionics communication products. In 2011 Integrated Communications, Navigation, and Surveillance Conference Proceedings, pages C3-1. IEEE, 2011. Google Scholar
  18. Arpan Gujarati, Sergey Bozhko, and Björn B Brandenburg. Real-time replica consistency over ethernet with reliability bounds. In 2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 376-389. IEEE, 2020. Google Scholar
  19. T. A. Henzinger, B. Horowitz, and C. M. Kirsch. Giotto: a time-triggered language for embedded programming. Proceedings of the IEEE, 91(1):84-99, 2003. URL: https://doi.org/10.1109/JPROC.2002.805825.
  20. M. Joseph and P. Pandya. Finding Response Times in a Real-Time System. The Computer Journal, 29(5):390-395, January 1986. URL: https://doi.org/10.1093/comjnl/29.5.390.
  21. Hagbae Kim and Kang G Shin. Sequencing tasks to minimize the effects of near-coincident faults in tmr controller computers. IEEE transactions on computers, 45(11):1331-1337, 1996. Google Scholar
  22. Thomas Kugelstadt. Extending the spi bus for long-distance communication. Analog Applications Journal, 2011. URL: https://www.ti.com/lit/an/slyt441/slyt441.pdf.
  23. J.F. Kurose and K.W. Ross. Computer Networking: A Top-Down Approach. Pearson Education, Limited, 2010. URL: https://books.google.it/books?id=2hv3PgAACAAJ.
  24. Seong Woo Kwak and Byung Kook Kim. Task-scheduling strategies for reliable tmr controllers using task grouping and assignment. IEEE Transactions on Reliability, 49(4):355-362, 2000. Google Scholar
  25. G Latif-Shabgahi, JM Bass, and S Bennett. Complete disagreement in redundant real-time control applications. IFAC Proceedings Volumes, 31(4):223-228, 1998. Google Scholar
  26. G Latif-Shabgahi, Julian M Bass, and Stuart Bennett. A taxonomy for software voting algorithms used in safety-critical systems. IEEE Transactions on Reliability, 53(3):319-328, 2004. Google Scholar
  27. Stephen R McConnel and Daniel P Siewiorek. Synchronization and voting. IEEE Transactions on Computers, 100(2):161-164, 1981. Google Scholar
  28. P. Pazzaglia, D. Casini, A. Biondi, and M. Di Natale. Optimal memory allocation and scheduling for dma data transfers under the let paradigm. In 58th Design Automation Conference (DAC), 2021. Google Scholar
  29. Dai Shenghua and Li Yishi. Research on 2-out-of-2 multiplying 2 redundancy system used in high-speed train. In 2011 IEEE International Conference on Computer Science and Automation Engineering, volume 2, pages 483-486. IEEE, 2011. Google Scholar
  30. Martin L Shooman. Reliability of computer systems and networks. Wiley Online Library, 2002. Google Scholar
  31. Daniel Siewiorek and Robert Swarz. Reliable computer systems: design and evaluatuion. Digital Press, 2017. Google Scholar
  32. Daniel P Siewiorek and Priya Narasimhan. Fault-tolerant architectures for space and avionics applications. NASA Ames Research http://ic. arc. nasa. gov/projects/ishem/Papers/Siewi, 2005. Google Scholar
  33. Zhijun Tong and Richard Y Kain. Vote assignments in weighted voting mechanisms. IEEE Transactions on Computers, 40(5):664-667, 1991. Google Scholar
  34. Xilinx. Zynq-7000 soc: Dc and ac switching characteristics - ds191, 2018. URL: https://www.xilinx.com/support/documentation/data_sheets/ds191-XC7Z030-XC7Z045-data-sheet.pdf#G1940899.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact