ОПТИМІЗАЦІЯ ПЛАНУВАННЯ ЗАВДАНЬ В РОЗПОДІЛЕНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ РЕАЛЬНОГО ЧАСУ.
DOI:
https://doi.org/10.18372/2310-5461.60.18267Ключові слова:
теорія планування, багатокритеріальна оптимізація, теорія черг, оптимальний розклад, позначені заявкиАнотація
Розподілені обчислювальні структури для виробничих та спеціальних цілей представляють ресурси м'яких або жорстких систем реального часу. Проблема планування завдань полягає в визначенні оптимального розподілу згідно із загальним критерієм корисності системи. У статті розглядаються методи побудови графіка, засновані на теорії планування. Показано, що найефективнішим кроком у цьому процесі є оптимізація діяльності підприємств або організацій на всіх рівнях - економічному, технічному, інформаційному і т.д., в умовах природних обмежень часових ресурсів. Оскільки оптимізація планування розкладу займає фундаментально важливе місце в процесі організації ефективної роботи розподіленої багатопроцесорної обчислювальної системи, розглядаються можливості використання цієї теорії при створенні оптимального розкладу на основі теорії черг зі звичайними і позначеними заявками. Теоретичною основою проблеми оптимізації планування є багаторівнева система з M блоками пам'яті та набором послуг N×M. З метою організації критеріїв оптимальності розкладу для забезпечення зручності опису, зберігання та програмної реалізації запропоновано умовний розподіл критеріїв на географічні, технічні або транзитні категорії із вказівкою відповідного пріоритетного значення. Враховуючи ці компоненти, отримано вираз для середнього часу очікування в черзі на заявку з позначкою. Представлена схема концептуального підходу до створення багатоядерного комп'ютера з розподілом періодичних та спорадичних завдань. Також представлена схема системи реального часу (СРЧ) в апаратній та програмній реалізації. Задачі в фоновому режимі в СРЧ активуються командами операційної системи реального часу (ОСРЧ) і вбудовуються в основні потоки. Вищезазначене демонструє універсальність запропонованого підходу до планування багатопроцесорної обчислювальної структури та його здатність відповідати вимогам користувача в реальному часі.
Посилання
Dziyauddin, R. A., Niyato, D., Luong, N. C., Mohd Atan, A. A. A., Mohd Izhar, M. A., Azmi, M. H., & Mohd Daud, S. Computation offloading and content caching and delivery in Vehicular Edge Network: A survey. Computer Networks. 2021. 197. 108228. - 22 p. https://doi.org/10.1016/j.comnet.2021.108228
Levner E. (Ed.) Multiprocessor Scheduling: Theory and Applications. - I-Tech Education and Publishing, Vienna, Austria, 2007. - 436 p.
Gawiejnowicz S. Models and Algorithms of Time-Dependent Scheduling, Second Ed. Springer-Verlag GmbH Germany, part of Springer Nature 2008, 2020. 538 p.
Okhremchuk O.S. Scheduling Optimisation Under Contradictions in Criteria Functions. Science-Based technologies, 2019. Vol. 2(42). p. 184 - 188. doi.10.18372/2310-5461.42.13750
Pinedo M.L. Scheduling: Theory, Algorithms, and Systems, Sixth Ed. Springer Nature Switzerland, 2022. 698 p.
Slomka F. Beyond the limitations of real-time scheduling theory: a unified scheduling theory for the analysis of real-time systems. Software-Intensive Cyber-Physical Systems, 2021. 35. p. 201–236. https://doi.org/10.1007/s00450-021-00429-1
Tanaev V.S., Sotskov Y.N., Strusevich V.A. Scheduling Theory. Multi-Stage Systems. Springer Science+Business Media, Dordrecht, 1994. 404 p.
Sinnen O. Task Scheduling for Parallel Systems, John Wiley & Sons, Inc., 2007. 296 p.
Chakrabarti A., Chakrabarti A., Sharma N., Balas V. (Eds.) Advances in Computing Applications. Springer Singapore, 2016. 299 p.
Tan D. Automatic determining optimal parameters in multi-kernel collaborative fuzzy clustering based on dimension constraint. Neurocomputing. 2021. 443. p. 58–74. doi.10.1016/j.neucom. 2021.02.0
Baruah S. Mixed-criticality scheduling theory: scope, promise, and limitations. IEEE Xplore Digital library, 2017. – 5 p. http://ieeexplore.ieee.org/Xplore
Xu, S., & Hall, N. G. Fatigue, personnel scheduling and operations: Review and research opportunities. European Journal of Operational Research. 2021. 295(3), 807–822. https://doi.org/10.1016/j.ejor.2021.03.036
Blazewicz J., Ecker K., Pesch E., Schmidt G., Sterna M., Weglarz J. Handbook on Scheduling: From Theory to Practice, Second Ed. Springer Nature Switzerland AG, 2019. 833 p.
Baital K. Dynamic Scheduling of Tasks for Multi-core Real Time Systems based on Optimum Energy and Throughput. ReView by River Valley Technologies - IET Review Copy, 2018. 12 p.
Baital, K. A. Dynamic Scheduling of Real-Time Tasks in Heterogeneous Multicore Systems. IET Comput. Digit. Tech. 2019. Vol. 13 Iss. 2, pp. 93-100. https://doi.org/10.1049/iet-cdt.2018.5114 .
Jinyi Xu J. Real-time task scheduling for FPGA-based multicore systems with communication delay. Microprocessors and Microsystems. 2022. Vol. 90. P. 104468.
Kohútka L. A New FPGA-Based Task Scheduler for Real-Time Systems. Electronics. 2023, 12(8), 1870. https://doi.org/10.3390/electronics12081870
Capota, E. A., Stangaciu, C. S., Micea, M. V., & Curiac, D.-I. Towards mixed criticality task scheduling in cyber physical systems: Challenges and perspectives. Journal of Systems and Software. 2019. 156. 204–216. https://doi.org/10.1016/j.jss.2019.06.099
Ben Messaoud, M. A thorough review of aircraft landing operation from practical and theoretical standpoints at an airport which may include a single or multiple runways. Applied Soft Computing. 2020. 106853. 88 p. https://doi.org/10.1016/j.asoc.2020.106853
Gerofi B. Performance and Scalability of Lightweight Multi-Kernel based Operating Systems. 2018 IEEE International Parallel and Distributed Processing Symposium. p. 116 - 125. doi.10.1109/IPDPS.2018.00022
Jansen K. Total Completion Time Minimization for Scheduling with Incompatibility Cliques Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021). p. 192 - 200.
