Циклічне планування
У програмуванні циклічне планування (англ. Round-robin) є одним із алгоритмів планування процесів або комутації пакетів даних у мережі.[1][2]
При роботі планувальника операційної системи інтервали часу, які часто називають квантами часу[3] присвоюються кожному процесові або потокові однаковим чином у циклічному порядку, опрацьовуючи всі процеси без пріоритету (також відоме як циклічне виконання[en]). Таке циклічне планування є простим, легким у виконанні, і без ресурсного голоду.
Планування Round-robin також можна застосувати і до інших задач, таких як диспетчеризація пакетів даних у комп'ютерних мережах.
Планування процесів[ред. | ред. код]
Для рівноправного чесного планування процесів, циклічний планувальник в основному виконує розподіл часу, даючи кожній задачі часовий проміжок або квант[4] (його доступ до процесорного часу), і переривання задачі, якщо вона не завершила роботу за цей квант. Задача продовжує роботу наступного разу, коли їй буде виділено наступний квант процесорного часу. Якщо процес закінчує свою роботу, або змінює свій стан на стан очікування, у момент коли йому було виділено час, планувальник вибере наступний перший процес із черги тих, що готові до виконання. Якби такого планування часу не було, або якщо кванти часу були б великими по відношенню до тривалості задач, процес який би виконував великі тривалі задачі мав би більший пріоритет над іншими задачами.
Наприклад, якщо квант часу становить 100 мілісекунд, а задача1 потребує 250 мс загального часу для завершення виконання, циклічний планувальник round-robin призупинить задачу після проходження 100 мс і виділить процесорний час іншій задачі. Після того, як інші задачі отримали свою рівну часту (по 100 мс кожна), задача1 отримає для виконання наступний інтервал часу процесора і цикл повториться знов. Цей процес продовжується доки задача не завершить своє виконання і більше не потребуватиме процесорного часу.
- Задача1 = Загальний час на виконання 250 мс (квант часу 100 мс.
- Перше виділення часу виконання = 100 мс.
- Друге виділення часу виконання = 100 мс.
- Третє виділення часу виконання = 100 мс але задача1 сама припинить своє виконання за 50 мс.
- Загальний час процесорного часу на задачу1 = 250 мс
Аби продемонструвати роботу циклічного планування, розглянемо наступну таблицю із часом початку і часом виконання процесу із квантами часу, що становлять 100 мс:
| Ім'я процесу | Час початку | Час виконання |
|---|---|---|
| P0 | 0 | 250 |
| P1 | 50 | 170 |
| P2 | 130 | 75 |
| P3 | 190 | 100 |
| P4 | 210 | 130 |
| P5 | 350 | 50 |
Іншим підходом, є поділити всі процеси на однакову кількість квантів часу, таким чином, що розмір кванту буде пропорційним до тривалості процесу. Таким чином, всі процеси завершать роботу одночасно.
Примітки[ред. | ред. код]
- ↑ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction] (PDF), Arpaci-Dusseau Books
- ↑ Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, ISBN 1107143217, 2016.
- ↑ Stallings, William (2015). Operating Systems: Internals and Design Principles. Pearson. с. 409. ISBN 978-0-13-380591-8.
- ↑ Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2010). Process Scheduling. Operating System Concepts (вид. 8th). John_Wiley_&_Sons (Asia). с. 194. ISBN 978-0-470-23399-3.
5.3.4 Round Robin Scheduling