АСПЕКТИ ТИМЧАСОВИХ ОБМЕЖЕНЬ ПРИ ВИМІРЮВАННІ КІБЕРФІЗІЧЕСКІХ СИСТЕМ В ПРОМИСЛОВОСТІ
DOI:
https://doi.org/10.30977/BUL.2219-5548.2018.83.0.107Ключові слова:
система реального часу, кіберфізична система, планування, Індустрія 4.0, алгоритм Earliest Deadline First, алгоритм Rate MonotonicАнотація
Кіберфізичні системи (CPS) в Індустрії 4.0 складаються з обчислювального ядра, ядра зв’язку й фізичної системи. Обчислювальне ядро має строгі часові обмеження і являє собою систему реального часу (RTS). RTS, реалізовані в традиційному встаткуванні, використовуються в широкому спектрі додатків, таких як пристрої загального користування, відомі як Internet of Things (Iot), а також пристрої зв’язку, мобільні телефони або комп’ютери. Ці системи викликають великий інтерес через тенденцію до автоматизації систем і додатків для щоденного використання, наприклад, самокеровані автомобілі, автономні літаки, датчики й роботи для догляду за людьми похилого віку. Одна з основних особливостей RTS полягає в тому, що вони мають строгі часові обмеження, які повинні бути виконані, оскільки в протилежному випадку результати можуть бути катастрофічними. RTS виконуються в операційній системі реального часу (RTOS). Однієї з найбільш популярних операційних систем є Linux. У якості алгоритмів планування в Linux використовуються політики планування на основі пріоритетів First-In First-Out (FIFO) і Round Robin (RR), але вони недостатні для жорстких RTS. У цій статті пропонується інтегрування політик Rate Monotonic (RM) і Erliest Deadline First (EDF) у систему Linux для планування періодичних завдань у жорстких RTS. Tест на виконуваність розкладів в однопроцесорних RTS є co-NP-повной задачею у суворому смислу для нетривіальних обчислювальних моделей. Лехоцким був запропонований необхідний і достатній (точний) тест для політики RM. Він розглядає використання процесора набором періодичних задач, як функцію часу в критичний момент. Лю й Лейленд увели точний тест виконуваності EDF для будь-якого періодичного набору завдань і довели оптимальність його динамічного варіанта для однопроцесорних архитектур. Для ілюстрації CPS був розроблений прототип контролюючої системи, що полягає із трьох потоків (threads). Виконуваність розкладів отриманих з використанням EDF y RM була перевірено за допомогою обох тестів. Тести показали, що використовуючи політикові RM, один із трьох потоків не зміг виконатися до відповідного крайнього строку при першій же активації. Однак значення загального використання процесора показало, що набір задач може бути правильно запланований з використанням EDF. При цьому всі завдання виконувалися відповідно до встановлених строків; завдання не потребуючі виконання в реальному часі, були згруповані в незайнятому (Idle) часі й оброблялися тільки тоді, коли задачі реального часу не вимагали виконання; отриманий розклад аналогічний у двох досліджених гіперперіодах.Посилання
Rajkumar, R., Lee, I., Sha, L., Stankovic, J.. Cyber-Physical Systems: The Next Computing Revolution. In proceedings of Design Automation Conference. 731 – 736. 2010.
NITRD: Networking and Information Technology Research and Development Program. Cyber-Physical System (CPS) Vision Statement. Available on-line: https://www.nitrd.gov/nitrdgroups/index.php?title=File:Cyber_Physical_Systems_(CPS)_Vision_Statement.pdf. 2011.
Buttazzo, G. C. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Springer Publisher, 540 p.
Davis, R. I., Burns, A (2011). A Survey of Hard Real-time Scheduling for Multiprocessor Systems. ACM Computing Surveys, 43(4) 35:1–35:44.
Shi, J., Wan, J., Yan, H. and Suo, H. (2011). A Survey of Cyber-Physical Systems. In Proceedings of the International Conference on Wireless Communications and Signal Processing. Nanjing. China. 1 – 6. 2011.
Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., Baruah, S. (2004). A categorization of real-time multiprocessor scheduling problems and algorithms. Handbook on Scheduling Algorithms, Methods, and Models. Chapman Hall/CRC Publisher, 30 p.
Liu, C. L., Layland, J. W. (1973). Scheduling algorithms for multi-programming in a hard-real-time environment. Journal of the ACM, 20 (1), 46 – 61.
Burns, A. (1991). Scheduling hard real-time systems: a review. Software Engineering Journal 6 (3), 16 – 28.
Srovnal, V., Kotzian, J. (2008). Development of a flight control system for an ultralight airplane. In: Proceedings of the International Multiconference on Computer Science and Information Technology (IMCSIT 2008), Wisła, Poland, IEEE Computer Society.
Faggioli, D., Checconi, F., Trimarchi, M., Scordino, C. (2009). An EDF scheduling class for the Linux kernel. In: Proceedings of the 11th Real-Time Linux Workshop, Dresden, Germany, 8 p.
Yodaiken, V (1999). The RTLinux manifesto. In: Proceedings of the 5th Linux Conference, Raleigh, North Carolina, USA.
Koh, J. H., Choi, B. W. (2013). Real-time Performance of Real-time Mechanisms for RTAI and Xenomai in Various Running Conditions. International Journal of Control and Automation, 6 (1), 235 – 246.
Calandrino, J. M., Leontyev, H., Block, A., Devi, U. C., et al. (2006). LITMUS-RT: A testbed for empirically comparing real-time multiprocessor schedulers. In: Proceedings of the 27th Symposium on Real-Time Systems, Rio de Janeiro, Brazil, 11 – 26.
Rostedt, S., Hart, D. V. (2007). Internals of the RT patch In: Proceedings of the Linux Symposium, Ottawa, Canada, 161 – 172.
Faggioli, D., Trimarchi, M., Checconi, F., Bertogna, M., et al. (2009a). An implementation of the earliest deadline first algorithm in Linux. In: Proceedings of the ACM symposium on Applied Computing, Honolulu, USA, 1984 – 1989.
Lelli, J., Faggioli, D., Cucinotta, T. (2011). An efficient and scalable implementation of global EDF in Linux. In: Proceedings of the 7th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, Porto, Portugal, 6 – 15.
Dellinger, M., Garyali, P., Ravindran, B. (2011). CHRONOS Linux: A best-effort real-time multiprocessor linux kernel. In: 48th Design Automation Conference (DAC), NY, USA, 474 –479.
XENOMAI website. http://www.xenomai.org/. (Consulted at October 4, 2018)
RTAI website. https://www.rtai.org/. (Consulted at November 4, 2015)
VxWORKS website. http://windriver.com/products/vxworks/. (Consulted at October 4, 2018)
Ose homepage. http://www.enea.com/ose. (Consulted at October 4, 2018)
Marte os homepage. http://marte.unican.es/. (Consulted at October 4, 2018)
Amaro, V., Diaz-Ramirez, A., Flores-Rios, B., González-Navarro, F., Werner, F., Burtseva, L. A scheduling extension scheme of the earliest deadline first policy for hard real-time uniprocessor systems integrated on POSIX threads based on Linux. Computer Systems Science and Engineering, 33 1), 2018, 31 – 40.
GLIBC website. https://www.gnu.org/software/libc/. (Consulted at October 4, 2018)
Baruah, S. K., Rosier, L. E., Howell, R. R. (1990). Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems, 2 (4), 301 – 324.
Stankovic, J. A., Ramamritham, K., Spuri, M. (1998). Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms. Kluwer Academic Publishers.
Buttazzo, G. C. (2005). Rate Monotonic vs. EDF: Judgment day. Real-Time Systems, 29 (1), 5 – 26.
Lehoczky, J., Sha, L., Ding, Y. (1989). The Rate Monotonic scheduling algorithm: exact characterization and average case behavior. In: Proceedings of the Symposium on Real Time Systems, Santa Monica, CA, USA, 166 – 171.
Arduino-serial source page. https://github.com/todbot/arduino-serial. (Consulted at October 4, 2018)
