Document Open Access Logo

A Hierarchical Scheduling Model for Dynamic Soft-Realtime System

Authors Vladimir Nikolov, Stefan Wesner, Eugen Frasch, Franz J. Hauck

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2017.7.pdf
  • Filesize: 1.06 MB
  • 23 pages

Document Identifiers

Author Details

Vladimir Nikolov
Stefan Wesner
Eugen Frasch
Franz J. Hauck

Cite As Get BibTex

Vladimir Nikolov, Stefan Wesner, Eugen Frasch, and Franz J. Hauck. A Hierarchical Scheduling Model for Dynamic Soft-Realtime System. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.7

Abstract

We present a new hierarchical approximation and scheduling approach for applications and tasks with multiple modes on a single processor. Our model allows for a temporal and spatial distribution of the feasibility problem for a variable set of tasks with non-deterministic and fluctuating costs at runtime. In case of overloads an optimal degradation strategy selects one of several application modes or even temporarily deactivates applications. Hence, transient and permanent bottlenecks can be overcome with an optimal system quality, which is dynamically decided. This paper gives the first comprehensive and complete overview of all aspects of our research, including a novel CBS concept to confine entire applications, an evaluation of our system by using a video-on-demand application, an outline for adding further resource dimension, and aspects of our protoype implementation based on RTSJ.

Subject Classification

Keywords
  • Real-Time
  • Scheduling
  • Hierarchical
  • Dynamic
  • ARTOS

Metrics

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

References

  1. L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In Proceedings 19th IEEE Real-Time Systems Symposium, RTSS'98, pages 4-13. IEEE Computer Society, 1998. URL: http://dx.doi.org/10.1109/REAL.1998.739726.
  2. L. Abeni, T. Cucinotta, G. Lipari, L. Marzario, and L. Palopoli. Qos management through adaptive reservations. Real-Time Syst., 29(2-3):131-155, March 2005. URL: http://dx.doi.org/10.1007/s11241-005-6882-0.
  3. K. Albers and F. Slomka. Efficient Feasibility Analysis for Real-Time Systems with EDF Scheduling. In Proceedings of the Conference on Design, Automation and Test in Europe - Volume 1, DATE'05, pages 492-497. IEEE Computer Society, 2005. URL: http://dx.doi.org/10.1109/DATE.2005.128.
  4. AREMA - Adaptive Runtime Environment for Multimode Applications. https://sourceforge.net/projects/arema/, September 2016.
  5. ARTOS. https://www.uni-ulm.de/en/in/vs/res/projects/artos/, April 2017.
  6. S. K. Baruah, A. K. Mok, and L. E. Rosier. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings 11th Real-Time Systems Symposium, pages 182-190, Dec 1990. URL: http://dx.doi.org/10.1109/REAL.1990.128746.
  7. A. Biondi, A. Melani, and M. Bertogna. Hard Constant Bandwidth Server: Comprehensive formulation and critical scenarios. In Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems (SIES 2014), pages 29-37, June 2014. URL: http://dx.doi.org/10.1109/SIES.2014.6871182.
  8. G. Bolella, B. Brosgol, P. Dibble, S. Furr, J. Gosling, D. Hardin, and M. Turnbull. The Real-Time Specification for Java. Addison-Wesley Longman Publishing Co., Inc., 2000. Google Scholar
  9. G. Buttazzo and E. Bini. Optimal dimensioning of a constant bandwidth server. In 2006 27th IEEE International Real-Time Systems Symposium (RTSS'06), pages 169-177, Dec 2006. URL: http://dx.doi.org/10.1109/RTSS.2006.31.
  10. G. Buttazzo, G. Lipari, L. Abeni, and M. Caccamo. Soft Real-Time Systems: Predictability vs. Efficiency. Springer US, 2005. URL: http://dx.doi.org/10.1007/0-387-28147-9.
  11. G. C. Buttazzo, G. Lipari, M. Caccamo, and L. Abeni. Elastic scheduling for flexible workload management. IEEE Trans. Comput., 51(3):289-302, March 2002. URL: http://dx.doi.org/10.1109/12.990127.
  12. M. Caccamo, G. Buttazzo, and L. Sha. Capacity sharing for overrun control. In Proceedings of the 21st IEEE Conference on Real-time Systems Symposium, RTSS'10, pages 295-304. IEEE Computer Society, 2000. Google Scholar
  13. S. Chakraborty, S. Kunzli, and L. Thiele. Approximate schedulability analysis. In 23rd IEEE Real-Time Systems Symposium, 2002. RTSS 2002., pages 159-168, 2002. URL: http://dx.doi.org/10.1109/REAL.2002.1181571.
  14. S. Chakraborty, M. Lukasiewycz, C. Buckl, S. Fahmy, N. Chang, S. Park, Y. Kim, P. Leteinturier, and H. Adlkofer. Embedded systems and software challenges in electric vehicles. In Proceedings of the Conference on Design, Automation and Test in Europe, DATE'12, pages 424-429. EDA Consortium, 2012. Google Scholar
  15. Concierge OSGi. http://concierge.sourceforge.net/, April 2009.
  16. T. Cucinotta, L. Palopoli, L. Abeni, D. Faggioli, and G. Lipari. On the integration of application level and resource level qos control for real-time applications. IEEE Transactions on Industrial Informatics, 6(4):479-491, Nov 2010. URL: http://dx.doi.org/10.1109/TII.2010.2072962.
  17. L. George, N. Rivierre, and M. Spuri. Preemptive and Non-Preemptive Real-Time Uni-Processor Scheduling. Research Report RR-2966, INRIA, 1996. Projet REFLECS. Google Scholar
  18. N. Henze. Stochastik für Einsteiger. Springer Fachmedien, Wiesbaden, 10 edition, 2013. URL: http://dx.doi.org/10.1007/978-3-658-03077-3.
  19. JamaicaVM. https://www.aicas.com/cms/en/JamaicaVM, February 2017.
  20. G. Koren and D. Shasha. Skip-over: algorithms and complexity for overloaded systems that allow skips. In Proceedings 16th IEEE Real-Time Systems Symposium, pages 110-117, Dec 1995. URL: http://dx.doi.org/10.1109/REAL.1995.495201.
  21. J. Lelli, C. Scordino, L. Abeni, and D. Faggioli. Deadline scheduling in the linux kernel. Software: Practice and Experience, 46(6):821-839, 2016. URL: http://dx.doi.org/10.1002/spe.2335.
  22. X. Lin, A. Mamat, Y. Lu, J. Deogun, and S. Goddard. Real-time scheduling of divisible loads in cluster computing environments. Journal of Parallel and Distributed Computing, 70(3):296-308, March 2010. URL: http://dx.doi.org/10.1016/j.jpdc.2009.11.009.
  23. G. Lipari and S. Baruah. A hierarchical extension to the constant bandwidth server framework. In Proceedings Seventh IEEE Real-Time Technology and Applications Symposium, RTAS'01, pages 26-35. IEEE Computer Society, 2001. URL: http://dx.doi.org/10.1109/RTTAS.2001.929863.
  24. J. W. S. Liu, W. K. Shih, K.-J. Lin, R. Bettati, and J.-Y. Chung. Imprecise computations. Proceedings of the IEEE, 82(1):83-94, Jan 1994. URL: http://dx.doi.org/10.1109/5.259428.
  25. C. Lu, J. A. Stankovic, S. H. Son, and G. Tao. Feedback control real-time scheduling: Framework, modeling, and algorithms*. Real-Time Syst., 23(1/2):85-126, July 2002. URL: http://dx.doi.org/10.1023/A:1015398403337.
  26. V. Nikolov. Ein hierarchisches Scheduling Modell für unbekannte Anwendungen mit schwankenden Ressourcenanforderungen. PhD thesis, Ulm University, 2016. URL: http://dx.doi.org/10.18725/OPARU-4099.
  27. V. Nikolov, F. J. Hauck, and L. Schubert. Ein hierarchisches Scheduling-Modell für unbekannte Anwendungen mit schwankenden Ressourcenanforderungen. In Betriebssysteme und Echtzeit, Informatik aktuell, pages 49-58. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48611-5_6.
  28. V. Nikolov, F. J. Hauck, and S. Wesner. Assembling a framework for unknown real-time applications with rtsj. In Proceedings of the 13th International Workshop on Java Technologies for Real-time and Embedded Systems, JTRES'15, pages 12:1-12:10. ACM, 2015. URL: http://dx.doi.org/10.1145/2822304.2822318.
  29. V. Nikolov, K. Kempf, F. J. Hauck, and D. Rautenbach. Distributing the Complexity of Schedulability Tests. In 21st IEEE Real-Time and Emb. Techn. and Appl. Symp., RTAS 2015, page 2. IEEE, 2015. Google Scholar
  30. V. Nikolov, S. Kächele, F. J. Hauck, and D. Rautenbach. Cloudfarm: An elastic cloud platform with flexible and adaptive resource management. In Proceedings of the 2014 IEEE/ACM 7th International Conference on Utility and Cloud Computing, UCC'14, pages 547-553. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/UCC.2014.84.
  31. V. Nikolov, M. Matousek, D. Rautenbach, L. D. Penso, and F. J. Hauck. ARTOS: system model and optimization algorithm. Technical Report VS-R08-2012, Inst. of Dist. Sys., University of Ulm, 2012. Google Scholar
  32. L. Palopoli, T. Cucinotta, L. Marzario, and G. Lipari. Aquosa - adaptive quality of service architecture. Softw. Pract. Exper., 39(1):1-31, January 2009. URL: http://dx.doi.org/10.1002/spe.v39:1.
  33. W. B. Powell. What you should know about approximate dynamic programming. Naval Research Logistics (NRL), 56(3):239-249, 2009. URL: http://dx.doi.org/10.1002/nav.20347.
  34. PREEMPT_RT. https://rt.wiki.kernel.org, January 2016.
  35. Wind River. A Smart Way To Drive ECU Consolidation. https://www.windriver.com/whitepapers/automotive/a-smart-way-to-drive-ecu-consolidation/, January 2017.
  36. RT-mutex implementation design. https://www.kernel.org/doc/Documentation/locking/rt-mutex-design.txt, January 2017.
  37. J. K. Strosnider, J. P. Lehoczky, and L. Sha. The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments. IEEE Transactions on Comp., 44(1):73-91, January 1995. URL: http://dx.doi.org/10.1109/12.368008.
  38. The Open Group and IEEE. IEEE Std 1003.1. The Open Group technical standard base specification, Issue 6, Base Definitions. http://www.opengroup.org/onlinepubs/009695399/mindex.html, 2004.
  39. A. Zerzelidis and A. J. Wellings. Getting more flexible scheduling in the RTSJ. In Ninth IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC'06), pages 8 pp.-, April 2006. URL: http://dx.doi.org/10.1109/ISORC.2006.38.
  40. A. Zerzelidis and A. J. Wellings. Getting more flexible scheduling in the RTSJ. In Proc. of the 9th IEEE Symp. on Obj.-Oriented Real-Time Distrib. Comp. - ISORC, pages 3-10, 2006. Google Scholar
  41. A. Zerzelidis and A. J. Wellings. A framework for flexible scheduling in the rtsj. ACM Trans. Embed. Comput. Syst., 10(1):3:1-3:44, August 2010. URL: http://dx.doi.org/10.1145/1814539.1814542.
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