Алгоритм Round Robin

Алгоритм Round Robin (также известный как циклический алгоритм или алгоритм карусельного типа) — это один из простейших и наиболее распространённых алгоритмов планирования процессов в операционных системах, основанный на принципе разделения времени (time-sharing). Он относится к классу вытесняющих (preemptive) алгоритмов и обеспечивает равномерное распределение процессорного времени между всеми активными процессами в очереди.

Основные принципы работы

Алгоритм Round Robin предполагает, что все процессы, готовые к выполнению, помещаются в циклическую очередь (FIFO — First In, First Out). Каждому процессу выделяется фиксированный квант времени (time quantum или time slice) — небольшой интервал, в течение которого процесс может выполняться на центральном процессоре (ЦП). По истечении этого кванта, если процесс ещё не завершился, он вытесняется (прерывается) и помещается в конец очереди, а процессор передаётся следующему процессу в очереди.

Основные характеристики:

• Вытесняемость: Алгоритм является вытесняющим, так как процесс может быть прерван до завершения своего выполнения.
• Квант времени: Длительность кванта является ключевым параметром, определяющим эффективность алгоритма.
• Циклическая очередь: Все процессы обслуживаются по кругу, без приоритетов (в базовой реализации).
• Справедливость: Каждый процесс получает равную долю процессорного времени, что предотвращает «голодание» (starvation) — ситуацию, когда один процесс бесконечно долго не получает доступа к ЦП.

История и происхождение

Концепция разделения времени, лежащая в основе Round Robin, возникла в 1950-х — 1960-х годах с развитием многозадачных операционных систем. Одним из первых реализаций такого подхода стала система CTSS (Compatible Time-Sharing System), разработанная в Массачусетском технологическом институте (MIT) в 1961 году. В CTSS использовался фиксированный квант времени для обеспечения интерактивной работы нескольких пользователей одновременно. Название «Round Robin» происходит от французского выражения «ruban rond» (круглая лента), которое в английском языке стало обозначать петицию с подписями по кругу, а затем — любой циклический процесс или порядок.

Механизм работы

Работа алгоритма Round Robin может быть описана следующей последовательностью шагов:

1. Инициализация: Все процессы, поступающие в систему, помещаются в конец очереди готовых к выполнению процессов.
2. Выбор процесса: Планировщик (scheduler) выбирает первый процесс из начала очереди.
3. Выполнение: Процессу предоставляется управление ЦП на время, равное кванту времени.
4. Проверка состояния:

• Если процесс завершает свою работу до истечения кванта, он удаляется из очереди, и управление переходит к шагу 2.
• Если процесс блокируется (например, ожидая ввода-вывода), он временно покидает очередь готовых процессов и переходит в состояние ожидания. После завершения операции ввода-вывода он возвращается в конец очереди.
• Если квант времени истёк, а процесс ещё не завершён и не заблокирован, происходит прерывание от таймера. Процесс вытесняется и помещается в конец очереди готовых процессов.

1. Повторение: Планировщик переходит к шагу 2.

Выбор кванта времени

Длительность кванта времени является критическим параметром, влияющим на производительность системы. Оптимальное значение кванта зависит от характера выполняемых задач и аппаратных возможностей.

Влияние размера кванта:

• Слишком большой квант: Алгоритм вырождается в невытесняющий алгоритм First-Come, First-Served (FCFS). Процессы выполняются последовательно, время отклика для интерактивных задач (например, редактирование текста) становится неприемлемо большим, так как пользователь вынужден ждать завершения длительного фонового процесса.
• Слишком маленький квант: Приводит к чрезмерным накладным расходам на переключение контекста (context switch). Каждое переключение требует сохранения и восстановления состояния регистров, таблиц страниц памяти и других данных. Если квант времени меньше времени переключения контекста, значительная часть процессорного времени будет тратиться впустую на служебные операции, а не на выполнение полезной работы.

На практике в современных операционных системах (например, Linux, Windows) квант времени обычно составляет от 10 до 100 миллисекунд. Для интерактивных систем предпочтительны меньшие значения (10–20 мс), для серверных пакетной обработки — большие (50–100 мс).

Пример работы

Рассмотрим три процесса (P1, P2, P3) с временем выполнения (burst time) 24, 3 и 4 единицы времени соответственно. Квант времени равен 4 единицам.

1. Цикл 1: P1 выполняется 4 единицы (осталось 20). P2 выполняется 3 единицы (завершён). P3 выполняется 4 единицы (осталось 0, завершён).
2. Цикл 2: P1 снова выполняется 4 единицы (осталось 16).
3. Цикл 3: P1 выполняется 4 единицы (осталось 12).
4. Цикл 4: P1 выполняется 4 единицы (осталось 8).
5. Цикл 5: P1 выполняется 4 единицы (осталось 4).
6. Цикл 6: P1 выполняется 4 единицы (завершён).

Время завершения: P2 — 7, P3 — 10, P1 — 30. Среднее время ожидания (waiting time) для P1 = (0 + (10–4) + (14–8) + (18–12) + (22–16) + (26–20)) / 3 ≈ 9.3 единицы.

Преимущества и недостатки

Преимущества:

• Простота реализации: Алгоритм легко реализовать и понять.
• Справедливость: Каждый процесс получает равную долю процессорного времени, что исключает «голодание».
• Предсказуемость: Максимальное время ожидания для процесса можно оценить как (n-1) * q, где n — количество процессов, q — квант времени.
• Интерактивность: Обеспечивает приемлемое время отклика для интерактивных пользователей.

Недостатки:

• Зависимость от кванта: Неправильный выбор кванта может привести к снижению производительности.
• Накладные расходы: Частое переключение контекста снижает эффективность использования ЦП.
• Неэффективность для длительных задач: Длительные процессы (например, научные расчёты) могут замедляться из-за частых вытеснений, хотя это компенсируется справедливым распределением ресурсов.
• Отсутствие приоритетов: В базовой реализации все процессы равны, что может быть недостатком для систем, где важна обработка срочных задач.

Применение в современных системах

Round Robin широко используется в операционных системах общего назначения, особенно в тех, которые ориентированы на многопользовательский режим и интерактивную работу. Например:

• Linux: Планировщик CFS (Completely Fair Scheduler) использует идею справедливого распределения времени, хотя и не является чистой реализацией Round Robin. Однако в Linux существует класс планирования SCHED_RR для задач реального времени, который реализует именно циклический алгоритм с фиксированным квантом.
• Windows: Планировщик Windows использует вытесняющий алгоритм с приоритетами, но базовая концепция циклического обслуживания очередей одного приоритета также присутствует.
• Встроенные системы: Round Robin часто применяется в простых встроенных системах и микроконтроллерах, где требуется предсказуемое распределение времени между задачами.
• Сетевые технологии: Алгоритм используется для планирования пакетов в коммутаторах и маршрутизаторах (например, в алгоритмах Weighted Round Robin — WRR).

Модификации алгоритма

Существует несколько модификаций Round Robin, направленных на устранение его недостатков:

• Weighted Round Robin (WRR): Каждому процессу или очереди назначается вес, пропорционально которому выделяется квант времени. Это позволяет отдавать приоритет более важным задачам.
• Virtual Round Robin (VRR): Для процессов, часто блокирующихся на вводе-выводе, создаётся отдельная «вспомогательная» очередь. После завершения операции ввода-вывода процесс помещается не в конец основной очереди, а в эту вспомогательную очередь, которая обслуживается с более высоким приоритетом. Это улучшает использование ЦП.
• Multilevel Feedback Queue (MLFQ): Использует несколько очередей с разными квантами времени. Процессы могут перемещаться между очередями в зависимости от их поведения (например, интерактивные процессы получают меньший квант, а длительные — больший). Это гибридный подход, который часто применяется в современных ОС.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts». 10th edition. — Wiley, 2018.
• Stallings W. «Operating Systems: Internals and Design Principles». 9th edition. — Pearson, 2017.
• Love R. «Linux Kernel Development». 3rd edition. — Addison-Wesley, 2010.
• Олифер В. Г., Олифер Н. А. «Компьютерные сети. Принципы, технологии, протоколы». 5-е издание. — СПб.: Питер, 2016.