logo

Приклад планування RR

У наступному прикладі є шість процесів з іменами P1, P2, P3, P4, P5 і P6. Час їхнього прибуття та час вибуху наведено нижче в таблиці. Квант часу системи дорівнює 4 одиницям.

ID процесу Час прибуття Час вибуху
1 0 5
2 1 6
3 2 3
4 3 1
5 4 5
6 6 4

Згідно з алгоритмом, ми повинні підтримувати готову чергу та діаграму Ганта. Структура обох структур даних буде змінена після кожного планування.

Готова черга:

Спочатку, у момент часу 0, надходить процес P1, який буде заплановано для часового інтервалу 4 одиниці. Отже, у черзі готовності буде лише один процес P1 при запуску з розрядним часом ЦП 5 одиниць.

P1
5

діаграма Ганта

P1 спочатку буде виконано для 4 одиниць.

в порядку
os RR Scheduling Приклад діаграми GANTT

Готова черга

Тим часом виконання P1, ще чотири процеси P2, P3, P4 і P5 надходять у готову чергу. P1 ще не завершено, йому потрібна ще 1 одиниця часу, тому його також буде додано назад до черги готовності.

P2 P3 P4 P5 P1
6 3 1 5 1

діаграма Ганта

Після P1, P2 буде виконано протягом 4 одиниць часу, що показано на діаграмі Ганта.

os RR Планування Приклад діаграми GANTT 1

Готова черга

Під час виконання P2 ще один процес P6 надходить у чергу готовності. Оскільки P2 ще не завершено, P2 також буде додано назад до черги готовності із залишковим часом пакету 2 одиниці.

P3 P4 P5 P1 P6 P2
3 1 5 1 4 2

діаграма Ганта

Після P1 і P2 P3 виконуватиметься протягом 3 одиниць часу, оскільки час його розвантаження ЦП становить лише 3 секунди.

Приклад планування os RR, діаграма GANTT 2

Готова черга

Оскільки P3 було завершено, отже, його буде припинено та не буде додано до черги готовності. Наступним процесом буде виконано P4.

P4 P5 P1 P6 P2
1 5 1 4 2

діаграма Ганта

Після цього будуть виконані P1, P2 і P3, P4. Його час вибуху становить лише 1 одиницю, що менше, ніж квант часу, тому він буде завершений.

Приклад планування os RR, діаграма GANTT 3

Готова черга

Наступним процесом у черзі готовності є P5 із 5 одиницями пакетного часу. Оскільки P4 завершено, його не буде додано назад до черги.

P5 P1 P6 P2
5 1 4 2

діаграма Ганта

P5 виконуватиметься протягом усього інтервалу часу, оскільки для цього потрібно 5 одиниць пакетного часу, що перевищує часовий інтервал.

Приклад планування os RR, діаграма GANTT 4

Готова черга

P5 ще не завершено; його буде додано назад до черги із залишковим часом пакету 1 одиниця.

P1 P6 P2 P5
1 4 2 1

Діаграма Ганта

Процесу P1 буде надано наступний хід для завершення його виконання. Оскільки для цього потрібна лише 1 одиниця часу вибуху, його буде завершено.

Приклад планування os RR, діаграма GANTT 5

Готова черга

P1 завершено та не буде додано назад до черги готовності. Наступний процес P6 вимагає лише 4 одиниці пакетного часу, і він буде виконано наступним.

P6 P2 P5
4 2 1

діаграма Ганта

P6 буде виконуватися протягом 4 одиниць часу до завершення.

Приклад планування os RR, діаграма GANTT 6

Готова черга

Оскільки P6 завершено, він не буде знову доданий до черги. У готовій черзі є лише два процеси. Наступний процес P2 вимагає всього 2 одиниці часу.

P2 P5
2 1

Діаграма Ганта

P2 буде виконано знову, оскільки для цього потрібно лише 2 одиниці часу, тому це буде завершено.

Приклад планування os RR, діаграма GANTT 7

Готова черга

Тепер єдиним доступним процесом у черзі є P5, який вимагає 1 одиницю пакетного часу. Оскільки інтервал часу складається з 4 одиниць, він буде завершений у наступному пакеті.

P5
1

діаграма Ганта

P5 виконуватиметься до завершення.

Приклад планування os RR, діаграма GANTT 8

Час завершення, час обробки та час очікування буде розраховано, як показано в таблиці нижче.

Як ми знаємо,

 Turn Around Time = Completion Time - Arrival Time Waiting Time = Turn Around Time - Burst Time 

ID процесу Час прибуття Час вибуху Час завершення Час обороту Час очікування
1 0 5 17 17 12
2 1 6 23 22 16
3 2 3 одинадцять 9 6
4 3 1 12 9 8
5 4 5 24 двадцять п'ятнадцять
6 6 4 двадцять один п'ятнадцять одинадцять

Середній час очікування = (12+16+6+8+15+11)/6 = 76/6 одиниць