Resource reservation for real-time self-suspending tasks: theory and practice

ABSTRACT

Nowadays, the real-time domain cannot neglect modern hardware architectures and the programming paradigms developed to fully exploit their capabilities. This has shown the limitations of classical task models, like the periodic one proposed by Liu&Layland, and it is pushing for the adoption of more realistic task models and the development of new schedulability analyses to guarantee their timing constraints. Self-suspending tasks are representative of enhanced task models considering explicit suspensions of the execution, happening when a task has to interact with an external device (e.g., through I/O operations) or to access shared resources. Real-time analysis of such a task model cannot neglect to take also into account temporal isolation techniques like bandwidth reservations and hypervisors, required to manage the complexity of actual software and the need of a modular development. In this paper we present a novel scheduling algorithm (H-CBS-SO) that provides temporal isolation for real-time self-suspending tasks. We also propose the implementation of this algorithm in the Linux kernel. Finally, experimental results are presented aiming at evaluating the performance of the implementation in terms of run-time overhead.

References

1. Y. Abdeddaïm and D. Masson. The scheduling problem of self-suspending periodic real-time tasks. In Proceedings of 20th International Conference on Real-Time and Network Systems, Pont-à-Mousson, France, Nov 2012.
2. L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, Madrid, Spain, December 2-4 1998.
3. L. Abeni, L. Palopoli, C. Scordino, and G. Lipari. Resource reservations for general purpose applications. IEEE Transactions on Industrial Informatics, 5(1):12--21, February 2009.
4. H. Aydin, R. Melhem, D. Mosse, and P. M. Alvarez. Power-aware scheduling for periodic real-time tasks. IEEE Transactions on Computers, 53(4):584--600, May 2004.
5. S. Baruah. Resource sharing in EDF-scheduled systems: a closer look. In Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS'06), Rio de Janeiro, Brazil, December 5-8, 2006.
6. M. Bertogna, N. Fisher, and S. Baruah. Resource-sharing servers for open environments. IEEE Transactions on Industrial Informatics, 5(3):202--219, August 2009.
7. A. Biondi, A. Melani, and M. Bertogna. Hard constant bandwidth server: Comprehensive formulation and critical scenarios. In Proc. of the 9th IEEE International Symposium on Industrial Embedded Systems (SIES 2014), Pisa, Italy, 18-20 June, 2014.
8. A. Biondi, A. Melani, M. Bertogna, and G. Buttazzo. Optimal design for reservation servers under shared resources. In Proc. of the 26th Euromicro Conference on Real-Time Systems (ECRTS 14), Madrid, Spain, 9-11 July, 2014.
9. B. Brandenburg and J. Anderson. The omlp family of optimal multiprocessor real-time locking protocols. Design Automation for Embedded Systems, pages 1--66, 2012.
10. J. Lelli, D. Faggioli, T. Cucinotta, and S. Superiore. An efficient and scalable implementation of global edf in linux. In Proc. of the 7th Workshop on Operating Systems Platforms for Embedded Real-Time applications, Porto, Portugal, 2011.
11. G. Lipari and E. Bini. A methodology for designing hierarchical scheduling systems. Journal of Embedded Computing, 1(2):257--269, April 2005.
12. C. Liu and J. H. Anderson. An O(m) analysis technique for supporting real-time self-suspending task systems. In In Proc. of the 33rd Real-Time Systems Symposium 2012.
13. C. Liu and J. H. Anderson. Suspension-aware analysis for hard real-time multiprocessor scheduling. In In Proc. of the 25th EuroMicro Conference on Real-Time Systems (ECRTS 2013).
14. C. Liu and J. H. Anderson. Task scheduling with self-suspensions in soft real-time multiprocessor systems. In In Proc. of the 30th Real-Time Systems Symposium (RTSS 2009).
15. J. Liu, editor. Real-time systems. Prentice Hall, 2000.
16. R. Mall, editor. Real-time systems: theory and practice. Pearson Education, 2008.
17. M. Marinoni and G. Buttazzo. Elastic dvs management in processors with discrete voltage/frequency modes. IEEE Transactions on Industrial Informatics, 3(1):51--62, Feb 2007.
18. L. Marzario, G. Lipari, P. Balbastre, and A. Crespo. IRIS: A new reclaiming algorithm for server-based real-time systems. In Proc. of the IEEE Real-Time and Embedded Technology and Applications Symposium, Toronto, Canada, May 25-28 2004.
19. G. Nelissen, J. Fonseca, G. Raravi, and V. Nélis. Timing analysis of fixed priority self-suspending sporadic tasks. In Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS 2015), Lund, Sweden, July 2015.
20. R. Rajkumar, K. Juvva, A. Molano, and S. Oikawa. 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, January 1998.
21. P. Richard. On the complexity of scheduling real-time tasks with self-suspension on one processor. In Proc. of the 15th IEEE Int. Euromicro Conferecnce on Real-Time Systems (ECRTS 2003).
22. F. Ridouard, P. Richard, and F. Cottet. Negative results for scheduling independent hard real-time tasks with self-suspensions. In Proc. of the 25th IEEE Real-Time Systems Symposium (RTSS 2004).
23. F. Ridouard, P. Richard, and F. Cottet. Some results on scheduling tasks with self-suspensions. In Journal of Embedded Computing, 2006.
24. I. Shin and I. Lee. Periodic resource model for compositional real-time guarantees. In Proceedings of the 24th IEEE Real-Time Systems Symposium, pages 2--13, Cancun, Mexico, December 3-5, 2003.
25. I. Shin and I. Lee. Compositional real-time scheduling framework. In Proceedings of the 25th IEEE Real-Time Systems Symposium, pages 57--67, Lisbon, Portugal, December 5-8, 2004.