Головна

Round Robin (RR)

  1.  Classification of Word-combinations grounded on the Principle of its Inner Structure
  2.  Moving Around Values
  3.  Surrounding Seas and Coastline
  4.  THE LONDON UNDERGROUND
  5.  Underground

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

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

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

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

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

Розглянемо попередній приклад з порядком процесів p0, p1, p2 і величиною кванта часу рівній 4. Виконання цих процесів ілюструється таблицею 3.2. Позначення "І" використовується в ній для процесу, що знаходиться в стані виконання, позначення "Г" - для процесів в стані готовність, порожні клітинки відповідають завершився процесам. Стану процесів показані протягом відповідної одиниці часу, т. Е. Колонка з номером 1 відповідає проміжку часу від 0 до 1.

 час
p0 И И И И Г Г Г Г Г И И И И И И И И И
p1 Г Г Г Г И И И И                    
p2 Г Г Г Г Г Г Г Г И                  

Таблиця 3.2.

Першим для виконання вибирається процес p0. Тривалість його CPU burst більше, ніж величина кванта часу, і тому процес виповнюється до закінчення кванта, т. Е. Протягом 4 одиниць часу. Після цього він поміщається в кінець черги готових до виконання процесів, яка набуває вигляду p1, p2, p0. Наступним починає виконуватися процес p1. Час його виконання збігається з величиною виділеного кванта, тому процес працює до свого завершення. Тепер черга процесів в стані готовність складається з двох процесів p2, p0. Процесор виділяється процесу p2. Він завершується до закінчення відпущеного йому процесорного часу, і чергові кванти відміряються процесу p0 - Єдиному, що не закінчив до цього моменту свою роботу. Час очікування для процесу p0 (Кількість символів "Г" у відповідному рядку) становить 5 одиниць часу, для процесу p1 - 4 одиниці часу, для процесу p2 - 8 одиниць часу. Таким чином, середній час очікування для цього алгоритму виходить рівним (5 + 4 + 8) / 3 = 5,6 (6) одиниці часу. Повний час виконання для процесу p0 (Кількість непустих стовпців у відповідному рядку) становить 18 одиниць часу, для процесу p1 - 8 одиниць, для процесу p2 - 9 одиниць. Середнє повне час виконання виявляється рівним (18 + 8 + 9) / 3 = 11,6 (6) одиницям часу.

Легко бачити, що середній час очікування і середнє повне час виконання для зворотного порядку процесів не відрізняються від відповідних часів для алгоритму FCFS і складають 2 і 6 одиниць часу відповідно.

На продуктивність алгоритму RR сильно впливає величина кванта часу. Розглянемо той же самий приклад c порядком процесів p0, p1, p2 для величини кванта часу дорівнює 1 (див. таблицю 3.3.). Час очікування для процесу p0 складе 5 одиниць часу, для процесу p1 - Теж 5 одиниць, для процесу p2 - 2 одиниці. У цьому випадку середній час очікування виходить рівним (5 + 5 + 2) / 3 = 4 одиницям часу. Середнє повне час виконання складе (18 + 9 + 3) / 3 = 10 одиниць часу.

 час
p0 И Г Г И Г И Г И Г И И И И И И И И И
p1 Г И Г Г И Г И Г И                  
p2 Г Г И                              

Таблиця 3.3.

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




 Структура обчислювальної системи |  Що таке ОС |  Коротка історія еволюції обчислювальних систем |  Системні виклики |  виняткові ситуації |  Монолітне ядро |  Листкові системи (Layered systems) |  Віртуальні машини |  Мікроядерна архітектура. |  змішані системи |

© um.co.ua - учбові матеріали та реферати