ОПТИМІЗАЦІЯ АЛГОРИТМІВ ПЛАНУВАННЯ ПРОЦЕСІВ В ОПЕРАЦІЙНИХ СИСТЕМАХ З ВИКОРИСТАННЯМ ІМІТАЦІЙНОГО МОДЕЛЮВАННЯ

Oleg Zaporozhets; Vladyslav Makarenko; Oleh Drozd

doi:10.26906/SUNZ.2026.1.192

Автор(и)

Oleg Zaporozhets
Vladyslav Makarenko
Oleh Drozd

DOI:

https://doi.org/10.26906/SUNZ.2026.1.192

Ключові слова:

планування процесів, операційні системи, дискретно-подійне моделювання, CFS, MLFQ, Round Robin

Анотація

Актуальність. Оптимізація планування процесів є критичною для сучасних ОС через різнорідні профілі навантаження, де компроміс між латентністю, пропускною здатністю та справедливістю неможливо надійно оцінити лише аналітично. Об’єкт дослідження: підсистема планування процесів (CPU scheduling) у мультизадачній операційній системі. Мета статті: розробити та обґрунтувати методику оптимізації й налаштування алгоритмів планування на основі імітаційного (дискретно‑подійного) моделювання та сформувати практичні рекомендації для різних профілів задач. Результати дослідження. Побудовано параметризовану DES‑модель однопроцесорної системи з потоком надходження процесів, ready‑чергою, I/O‑блокуваннями та накладними витратами контекстних переключень. Реалізовано й порівняно FCFS, SJF, Round Robin, пріоритетне планування, MLQ, MLFQ, модель справедливого планування, подібну до CFS, та адаптивний RR. Експериментально оцінено час очікування і відповіді, пропускну здатність, завантаження CPU, частку накладних витрат CS та справедливість (індекс Джейна) у чотирьох сценаріях навантаження: інтерактивному, CPU‑heavy, bursty та змішаному за пріоритетами. Висновки. Невитіснювальні стратегії демонструють конкурентні середні значення лише в окремих режимах, тоді як витіснювальні та адаптивні підходи краще відповідають вимогам змішаних навантажень, але потребують акуратного тюнінгу кванта часу, гранулярностей і механізмів протидії голодуванню. Симуляційний підхід забезпечує відтворюване порівняння та виявлення параметричних зон, що ведуть до небажаних режимів. Сфера використання отриманих результатів: вибір і налаштування політик планування в ОС загального призначення, навчальні симулятори та інструменти аналізу продуктивності.

Завантажити

Дані для завантаження поки недоступні.

Посилання

1. Arpaci-Dusseau R. H., Arpaci-Dusseau A. C. Operating Systems: Three Easy Pieces. CPU Scheduling (chapter). University of Wisconsin–Madison. URL: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf

2. IEEE. Portable Operating System Interface (POSIX) Base Specifications, Issue 7 (IEEE Std 1003.1-2017). DOI: https://doi.org/10.1109/IEEESTD.2018.8277153

3. Linux Kernel Documentation. CFS scheduler design. URL: https://docs.kernel.org/scheduler/sched-design-CFS.html

4. Zinoviev D. Discrete Event Simulation: It's Easy with SimPy! arXiv:2405.01562, 2024. DOI: https://doi.org/10.48550/arXiv.2405.01562.

5. Kerrisk M. sched (7) – Linux manual page. URL: https://man7.org/linux/man-pages/man7/sched.7.html

6. Lozi J. P., et al. The Linux scheduler. EuroSys 2016. DOI: https://doi.org/10.1145/2901318.2901326.

7. Linux Kernel Documentation. EEVDF scheduler. URL: https://docs.kernel.org/scheduler/sched-eevdf.html

8. Rasouli A., et al. MLFQ-RT: A multi-level feedback queue real-time scheduler for embedded systems. CODES+ISSS 2014. DOI: https://doi.org/10.1145/2656075.2656108.

9. Chen X. Calendar queue: a new real-time calendar-based priority queue. Journal of Parallel and Distributed Computing, 1992. DOI: https://doi.org/10.1016/0743-7315(92)90068-A.

10. Simpson K., et al. Simulation-based experimentation on scheduling algorithms. Heliyon, 2022. DOI: https://doi.org/10.1016/j.heliyon.2022.e10507.

11. Law A. M., Kelton W. D. Simulation Modeling and Analysis. 5th ed. McGraw-Hill Education, 2015. ISBN: 978- 0073401324. URL: https://search.worldcat.org/de/title/simulation-modeling-and-analysis/oclc/1022581268

12. Sargent R. G. Verification and validation of simulation models. In: Proceedings of the 2010 Winter Simulation Conference (WSC), 2010, pp. 166–183. DOI: https://doi.org/10.1109/WSC.2010.5679166.

13. Arpaci-Dusseau R. H., Arpaci-Dusseau A. C. Operating Systems: Three Easy Pieces. Scheduling: The Multi-Level Feedback Queue (chapter). URL: https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf

14. SimPy Documentation. Basic Concepts. Available: https://simpy.readthedocs.io/en/latest/simpy_intro/basic_concepts.html

15. Jain R., Chiu D.-M., Hawe W. A Quantitative Measure Of Fairness And Discrimination For Resource Allocation In Shared Computer Systems. arXiv:cs/9809099. DOI: https://doi.org/10.48550/arXiv.cs/9809099