У програмуванні циклічне планування (англ. Round-robin) є одним із алгоритмів планування процесів або комутації пакетів даних у мережі.
При роботі планувальника операційної системи інтервали часу, які часто називають квантами часу присвоюються кожному процесові або потокові однаковим чином у циклічному порядку, опрацьовуючи всі процеси без пріоритету (також відоме як [en]). Таке циклічне планування є простим, легким у виконанні, і без ресурсного голоду.
Планування Round-robin також можна застосувати і до інших задач, таких як диспетчеризація пакетів даних у комп'ютерних мережах.
Планування процесів
Для рівноправного чесного планування процесів, циклічний планувальник в основному виконує розподіл часу, даючи кожній задачі часовий проміжок або квант (його доступ до процесорного часу), і переривання задачі, якщо вона не завершила роботу за цей квант. Задача продовжує роботу наступного разу, коли їй буде виділено наступний квант процесорного часу. Якщо процес закінчує свою роботу, або змінює свій стан на стан очікування, у момент коли йому було виділено час, планувальник вибере наступний перший процес із черги тих, що готові до виконання. Якби такого планування часу не було, або якщо кванти часу були б великими по відношенню до тривалості задач, процес який би виконував великі тривалі задачі мав би більший пріоритет над іншими задачами.
Наприклад, якщо квант часу становить 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, , 2016.
- Stallings, William (2015). Operating Systems: Internals and Design Principles. Pearson. с. 409. ISBN .
- ; Galvin, Peter B.; Gagne, Greg (2010). Process Scheduling. (вид. 8th). (Asia). с. 194. ISBN .
5.3.4 Round Robin Scheduling
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U programuvanni ciklichne planuvannya angl Round robin ye odnim iz algoritmiv planuvannya procesiv abo komutaciyi paketiv danih u merezhi Priklad ciklichnogo planuvannya round robin iz koeficiyentom 3 Pri roboti planuvalnika operacijnoyi sistemi intervali chasu yaki chasto nazivayut kvantami chasu prisvoyuyutsya kozhnomu procesovi abo potokovi odnakovim chinom u ciklichnomu poryadku opracovuyuchi vsi procesi bez prioritetu takozh vidome yak en Take ciklichne planuvannya ye prostim legkim u vikonanni i bez resursnogo golodu Planuvannya Round robin takozh mozhna zastosuvati i do inshih zadach takih yak dispetcherizaciya paketiv danih u komp yuternih merezhah Planuvannya procesivDokladnishe Planuvalnik operacijnoyi sistemi Dlya rivnopravnogo chesnogo planuvannya procesiv ciklichnij planuvalnik v osnovnomu vikonuye rozpodil chasu dayuchi kozhnij zadachi chasovij promizhok abo kvant jogo dostup do procesornogo chasu i pererivannya zadachi yaksho vona ne zavershila robotu za cej kvant Zadacha prodovzhuye robotu nastupnogo razu koli yij bude vidileno nastupnij kvant procesornogo chasu Yaksho proces zakinchuye svoyu robotu abo zminyuye svij stan na stan ochikuvannya u moment koli jomu bulo vidileno chas planuvalnik vibere nastupnij pershij proces iz chergi tih sho gotovi do vikonannya Yakbi takogo planuvannya chasu ne bulo abo yaksho kvanti chasu buli b velikimi po vidnoshennyu do trivalosti zadach proces yakij bi vikonuvav veliki trivali zadachi mav bi bilshij prioritet nad inshimi zadachami Napriklad yaksho kvant chasu stanovit 100 milisekund a zadacha1 potrebuye 250 ms zagalnogo chasu dlya zavershennya vikonannya ciklichnij planuvalnik round robin prizupinit zadachu pislya prohodzhennya 100 ms i vidilit procesornij chas inshij zadachi Pislya togo yak inshi zadachi otrimali svoyu rivnu chastu po 100 ms kozhna zadacha1 otrimaye dlya vikonannya nastupnij interval chasu procesora i cikl povtoritsya znov Cej proces prodovzhuyetsya doki zadacha ne zavershit svoye vikonannya i bilshe ne potrebuvatime procesornogo chasu Zadacha1 Zagalnij chas na vikonannya 250 ms kvant chasu 100 ms Pershe vidilennya chasu vikonannya 100 ms Druge vidilennya chasu vikonannya 100 ms Tretye vidilennya chasu vikonannya 100 ms ale zadacha1 sama pripinit svoye vikonannya za 50 ms Zagalnij chas procesornogo chasu na zadachu1 250 ms Abi prodemonstruvati robotu ciklichnogo planuvannya rozglyanemo nastupnu tablicyu iz chasom pochatku i chasom vikonannya procesu iz kvantami chasu sho stanovlyat 100 ms Im ya procesu Chas pochatku Chas vikonannya P0 0 250 P1 50 170 P2 130 75 P3 190 100 P4 210 130 P5 350 50 Ciklichne planuvannya Inshim pidhodom ye podiliti vsi procesi na odnakovu kilkist kvantiv chasu takim chinom sho rozmir kvantu bude proporcijnim do trivalosti procesu Takim chinom vsi procesi zavershat robotu odnochasno PrimitkiArpaci 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 s 409 ISBN 978 0 13 380591 8 Galvin Peter B Gagne Greg 2010 Process Scheduling vid 8th John Wiley amp Sons Asia s 194 ISBN 978 0 470 23399 3 5 3 4 Round Robin Scheduling