Формалізацація процесу планування за методом RMRT-EDF з урахуванням обмежених ресурсів
DOI:
https://doi.org/10.20535/1560-8956.47.2025.340183Ключові слова:
RMRT-EDF, MPC, ресурсні обмеження, EDF, телеметрія, токен- модель, диспетчеризація задачАнотація
Розглянуто формалізацію процесу планування задач у середовищах з обмеженими обчислювальними ресурсами на основі гібридного підходу RMRT-EDF (Reactive Multi-Resource Token – Earliest Deadline First). Запропоновано дискретно- часову математичну модель, яка орієнтована на запуск кожної задачі не пізніше ніж через одну секунду після її надходження, з одночасним дотриманням багатовимірних обмежень на використання CPU, оперативної пам’яті та підсистем вводу/виводу. Планувальник інтерпретується як замкнена система автоматичного керування зі зворотним зв’язком: задачі проходять токен-фільтрацію ресурсів, після чого впорядковуються за принципом EDF. Кількість одночасних запусків регулюється адаптивним лімітом, сформованим за допомогою моделі прогнозного керування (Model Predictive Control) зі змінним горизонтом оптимізації. У моделі враховано можливість часткового відхилення термінів виконання з метою забезпечення стійкості системи при пікових навантаженнях.
Бібл. 18, табл. 1
Посилання
Корнага Я. І., Лемешко В.А. RMRT-EDF: реактивний мультиресурсний токен-планувальник для гарантованого запуску задач у реальному часі // InfoCom Advanced Solutions 2025. Київ, 2025. C.35-38. URL: https://ist.kpi.ua/wp-content/ uploads/2025/05/infocom-advanced-solutions-2025_compressed-3.pdf
Naseem Adnan AlsamaraiOsman Nuri Uçan, Improved Performance and Cost Algorithm for Scheduling IoT Tasks in Fog–Cloud Environment Using Gray Wolf Optimization Algorithm // Applied Sciences. – 2024. – Т. 14, № 4. – С. 1670. – DOI: 10.3390/app14041670. – Режим доступу: https://www.mdpi.com/2076-3417/14/4/1670
Abubakar Sani Jato Performance Evaluation of Operating Systems Scheduling Algorithms // ResearchGate. – 2024. – Режим доступу: https://www.researchgate.net/ publication/379263571_PERFORMANCE_EVALUATION_OF_OPERATING _SYSTEMS_SCHEDULING_ALGORITHMS.
Liang, F., Zhang, Z., Lu, H., Li, C., Leung, V. C. M., Guo, Y., & Hu, S. Resource Allocation and Workload Scheduling for Large-Scale Distributed Deep Learning: A Survey [Electronic resource] / F. Liang, Z. Zhang, H. Lu, C. Li, V. C. M. Leung, Y. Guo, S. Hu // arXiv preprint. – 2024. – June. – arXiv:2406.08115. – Mode of access: https://www.researchgate.net/ publication/381372558_Resource_Allocation_and_Workload_Scheduling_for_ Large-Scale_ Distributed_Deep_Learning_A_Survey.
Kumar, M. S., & Karri, G. R. EAEFA: An Efficient Energy-Aware Task Scheduling in Cloud Environment [Електронний ресурс] / M. S. Kumar, G. R. Karri // EAI Endorsed Transactions on Scalable Information Systems. – 2023. – Т. 11, № 3. – Режим доступу: https://www.researchgate.net/publication/374071179_EAEFA_An_Efficient_ Energy-Aware_Task_ Scheduling_in_Cloud_Environment
Bitam, S. Bees Life Algorithm for Job Scheduling in Cloud Computing [Електронний ресурс] / S. Bitam // Proceedings of the 2012 International Conference on Computer Engineering & Systems (ICCES). – 2012. – С. 186–191. – Режим доступу: https://www.researchgate.net/publication/287656786_Bees_life_algorithm_ for_job_scheduling_in_cloud_computing
Smesseim, A. Dynamic Thread Allocation for Distributed Jobs using Resource Tokens [Електронний ресурс] / A. Smesseim. – 2019. – 59 с. – Магістерська дисертація. – ETH Zurich. – Режим доступу: https://www.research-collection.ethz.ch/bitstream/handle/ 20.500.11850/362308/1/Smesseim_Ali.pdf
Al-Haidari, F., & Balharith, T. Enhanced Round-Robin Algorithm in the Cloud Computing Environment for Optimal Task Scheduling [Електронний ресурс] / F. Al-Haidari, T. Balharith // ResearchGate. – 2021. – Режим доступу: https://www.researchgate.net/publication/351453682_Enhanced_Round-Robin_Algorithm_in_the_Cloud_Computing_ Environment_for_Optimal_Task_Scheduling
Zhou, J., Liu, B., & Gao, J. A task scheduling algorithm with deadline constraints for distributed clouds in smart cities [Електронний ресурс] / Zhou, B. Liu, J. Gao // PeerJ Computer Science. – 2023. – Vol. 9. – Article e1346. – DOI: 10.7717/peerj-cs.1346. – Режим доступу: https://peerj.com/articles/cs-1346/
Abohamama, A. S., El-Ghamry, A., & Hamouda, E. Real-Time Task Scheduling Algorithm for IoT-Based Applications in the Cloud–Fog Environment [Електронний ресурс] / A. S. Abohamama, A. El-Ghamry, E. Hamouda // Journal of Network and Systems Management. – 2022. – Vol. 30, Article 54. – DOI: 10.1007/s10922-022-09664-6. – Режим доступу: https://www.researchgate.net/publication/361715957_Real-Time_Task_Scheduling_ Algorithm_for_IoT-Based_Applications_in_the_Cloud-Fog_Environment
Huang Y., Zhang S., Wang B. An Improved Genetic Algorithm with Swarm Intelligence for Security-Aware Task Scheduling in Hybrid Clouds // Electronics. – 2023. – Vol. 12, No. 9. – Article No. 2064. – DOI: https://doi.org/10.3390/electronics12092064
Garba, A. J., Gital, A. Y., Boukari, S., & Zambuk, F. U. (2023). Hybrid Meta-Heuristics Based Task Scheduling Algorithm for Energy Efficiency in Fog Computing. International Journal of Advanced Scientific Research and Engineering, 9(2), 1–8. https://doi.org/10.31695/IJASRE.2023.9.2.3
Wang J., Li S., Zhang X., Wu F., Xie C. Deep reinforcement learning task scheduling method based on server real-time performance // PeerJ Computer Science. – 2024. – Vol. 10. – Article e2120. – DOI: https://doi.org/10.7717/peerj-cs.2120
Liu C. L., Layland J. W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment // Journal of the ACM. – 1973. – Vol. 20, No. 1. – P. 46–61. – DOI: https://doi.org/10.1145/321738.321743.
Le Boudec J.-Y., Thiran P. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. – Berlin: Springer, 2001. – 274 p. – (Lecture Notes in Computer Science; Vol. 2050). – ISBN 978-3-540-42184-9
Buttazzo G. C. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. – 3rd ed. – New York: Springer, 2011. – 524 p. – (Real-Time Systems Series; Vol. 24). – ISBN 978-1-4614-0675-4. – DOI: 10.1007/978-1-4614-0676-1
S. A. A. Shah, M. A. Khan, M. A. Khan, and M. A. Khan. Designing and Implementing of Earliest Deadline First Scheduling Algorithm on Standard Linux // 2010 International Conference on Complex, Intelligent and Software Intensive Systems (CISIS). – 2010. – P. 107–112. – DOI: https://doi.org/10.1109/CISIS.2010.34
Zak S. H. An Introduction to Model-based Predictive Control (MPC) // ECE 680 – Fall 2017. – 2017. – 22 p. – Available at: https://www.researchgate.net/profile/Mohamed-Mourad-Lafifi/post/Model-Predictive-Control-examples/attachment/60202ac761fb570001029 f61/AS%3A988637009301508%401612720839656/download/An+Introduction+ to+Model-based+Predictive+Control+%28MPC%29.pdf
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
1.Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у нашому журналі.
2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована нашим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у нашому журналі.
3. Політика журналу дозволяє і заохочує розміщення рукопису роботи авторами в мережі Інтернет (наприклад, на arXiv.org або на особистих веб-сайтах). Причому рукописи статей можуть бути розміщенні у відкритих архівах як до подання рукопису до редакції, так і під час його редакційного опрацювання. Це сприяє виникненню продуктивної наукової дискусії, позитивно позначається на оперативності ознайомлення наукової спільноти з результатами Ваших досліджень і як наслідок на динаміці цитування вже опублікованої у журналі роботи. Детальніше про це: The Effect of Open Access.
