Відмінності між версіями «2. Round Robin (RR)»

Версія за 19:01, 26 квітня 2011

Модифікацією алгоритму FCFS є алгоритм, що одержав назву Round Robin (Round Robin — це вид дитячої каруселі в США) або скорочено RR. По суті справи це той же самий алгоритм, тільки реалізований в режимі планування що витісняє. Можна уявити собі всю безліч готових процесів організованою циклічно — процеси сидять на каруселі. Карусель обертається так, що кожен процес знаходиться біля процесора невеликий фіксований квант часу, в межах 10-100 мілісекунд (див. малюнок 3.2.). Поки процес знаходиться поряд з процесором, він одержує процесор в своє розпорядження і може виконуватися.

Рис 3.2. Процеси на каруселі.

Реалізується такий алгоритм так само, як і попередній, за допомогою організації процесів, що знаходяться в стані готовність, в чергу FIFO.

Планувальник вибирає для чергового виконання процес, розташований на початку черги, і встановлює таймер для генерації перепину після закінчення певного кванта часу. При виконанні процесу можливі два варіанти:

• Час безперервного використання процесора, потрібний процесу, (залишок поточного CPU burst) менше або рівен тривалості кванта часу. Тоді процес по своїй волі звільняє процесор до закінчення кванта часу, на виконання вибирається новий процес з початку черги і таймер починає відлік кванта наново.

• Тривалість залишку поточного CPU burst процесу більше, ніж квант часу. Тоді після закінчення цього кванта процес перепиняється таймером і поміщається в кінець черги процесів готових до виконання, а процесор виділяється для використання процесу, що знаходиться на її початку.

Легко показати, що середній час очікування і середній повний час виконання для алгоритму RR не відрізняються від відповідних часів для алгоритму FCFS. На продуктивність алгоритму RR сильно впливає величина кванту часу. При дуже великих величинах кванту часу, коли кожен процес встигає завершити свій CPU burst до виникнення перепину за часом, алгоритм RR вироджується в алгоритм FCFS. При дуже малих величинах створюється ілюзія того, що кожен з n процесів працює на своєму власному віртуальному процесорі з продуктивністю ~1/n від продуктивності реального процесора. Правда, це справедливо лише при теоретичному аналізі за умови нехтування часом перемикання контексту процесів. В реальних умовах при дуже малій величині кванту часу і, відповідно, дуже частому перемиканні контексту, накладні витрати на перемикання різко знижують продуктивність системи.