Циклічне планування

У програмуванні циклічне планування (англ. Round-robin) є одним із алгоритмів планування процесів або комутації пакетів даних у мережі.[1][2]

Приклад циклічного планування «round-robin» із коефіцієнтом=3.

При роботі планувальника операційної системи інтервали часу, які часто називають квантами часу[3] присвоюються кожному процесові або потокові однаковим чином у циклічному порядку, опрацьовуючи всі процеси без пріоритету (також відоме як циклічне виконання). Таке циклічне планування є простим, легким у виконанні, і без ресурсного голоду.

Планування Round-robin також можна застосувати і до інших задач, таких як диспетчеризація пакетів даних у комп'ютерних мережах.

Планування процесів

Для рівноправного чесного планування процесів, циклічний планувальник в основному виконує розподіл часу, даючи кожній задачі часовий проміжок або квант[4] (його доступ до процесорного часу), і переривання задачі, якщо вона не завершила роботу за цей квант. Задача продовжує роботу наступного разу, коли їй буде виділено наступний квант процесорного часу. Якщо процес закінчує свою роботу, або змінює свій стан на стан очікування, у момент коли йому було виділено час, планувальник вибере наступний перший процес із черги тих, що готові до виконання. Якби такого планування часу не було, або якщо кванти часу були б великими по відношенню до тривалості задач, процес який би виконував великі тривалі задачі мав би більший пріоритет над іншими задачами.

Наприклад, якщо квант часу становить 100 мілісекунд, а задача1 потребує 250 мс загального часу для завершення виконання, циклічний планувальник round-robin призупинить задачу після проходження 100 мс і виділить процесорний час іншій задачі. Після того, як інші задачі отримали свою рівну часту (по 100 мс кожна), задача1 отримає для виконання наступний інтервал часу процесора і цикл повториться знов. Цей процес продовжується доки задача не завершить своє виконання і більше не потребуватиме процесорного часу.

  • Задача1 = Загальний час на виконання 250 мс (квант часу 100 мс.
  1. Перше виділення часу виконання = 100 мс.
  2. Друге виділення часу виконання = 100 мс.
  3. Третє виділення часу виконання = 100 мс але задача1 сама припинить своє виконання за 50 мс.
  4. Загальний час процесорного часу на задачу1 = 250 мс

Аби продемонструвати роботу циклічного планування, розглянемо наступну таблицю із часом початку і часом виконання процесу із квантами часу, що становлять 100 мс:

Ім'я процесуЧас початкуЧас виконання
P00250
P150170
P213075
P3190100
P4210130
P535050
Циклічне планування

Іншим підходом, є поділити всі процеси на однакову кількість квантів часу, таким чином, що розмір кванту буде пропорційним до тривалості процесу. Таким чином, всі процеси завершать роботу одночасно.

Примітки
  1. Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). Operating Systems: Three Easy Pieces [Chapter: Scheduling Introduction]. Arpaci-Dusseau Books.
  2. Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, ISBN 1107143217, 2016.
  3. Stallings, William (2015). Operating Systems: Internals and Design Principles. Pearson. с. 409. ISBN 978-0-13-380591-8.
  4. 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»
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.