EssayAI
Блог
Блог
Естественные науки

Алгоритм планирования Round Robin: очередь и квант

8 ноября 2026Время чтения: 9 минут
#round robin#планирование процессов#операционные системы#квант времени#очередь
Алгоритм планирования Round Robin: очередь и квант

Алгоритм планирования Round Robin, или круговое планирование, по очереди выделяет готовым процессам ограниченное время работы процессора. Если процесс не успел закончить за свой квант, он возвращается в конец очереди и ждёт следующего круга. Благодаря этому длинная задача не занимает процессор целиком, пока остальные готовы к выполнению.

В калькуляторе можно изменить квант и длительность трёх процессов, поступающих одновременно. Он строит расписание и показывает время завершения и ожидания. Ниже разберём, как получить те же числа вручную и какие допущения влияют на результат.

Очередь готовых и квант времени

Планировщик выбирает работу из очереди готовых: в ней находятся процессы, которым сейчас нужен процессор и которые могут выполняться. Ожидающий диск или сетевой ответ процесс заблокирован и до готовности в эту очередь не входит. В учебных примерах слово «процесс» часто обозначает единицу планирования; в реальной системе ею нередко служит поток.

Пусть квант равен qq. Процесс получает не более qq единиц процессорного времени подряд. Если его оставшаяся работа меньше кванта, он завершится раньше. Если работа осталась, по окончании кванта процесс вытесняется и ставится в хвост очереди. Следующий готовый процесс получает процессор. Обычная очередь FIFO помогает представить это правило: добавление идёт в конец, выбор - из начала.

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

На видео видно полное расписание, а выделение последовательно проходит по его отрезкам. После завершения оно возвращается к началу для повторного просмотра: это повтор примера, а не обратный ход времени. Базовую идею выделения кванта описывает глава Scheduling: Introduction учебника Operating Systems: Three Easy Pieces.

Правило работы по шагам

Для одной очереди одинакового приоритета и одного процессора алгоритм можно записать так:

  1. Добавить поступившие готовые процессы в конец очереди.
  2. Извлечь процесс из начала. Если очередь пуста, процессор простаивает до следующего события готовности.
  3. Выполнить процесс до конца его работы, блокировки или исчерпания кванта - смотря что наступит раньше.
  4. Завершившийся процесс удалить; заблокированный ждать вне очереди; вытесненный с оставшейся работой добавить в конец очереди.
  5. Повторять выбор, пока остаётся работа.

Порядок событий на одной временной границе нужно оговорить. В примере ниже все приходят в нулевой момент, поэтому неоднозначности нет. В задачах с новыми поступлениями можно, например, сначала поставить в очередь прибывших к концу кванта, затем вернуть вытесненный процесс. Другая оговорённая конвенция способна дать другую диаграмму и другие времена. Удобно фиксировать состояние очереди после каждого события, как при трассировке алгоритма.

Пример: три процесса и квант 2 мс

Пусть процессы А, Б и В поступили в момент 00 в указанном порядке. Им нужно соответственно 55, 44 и 22 мс чистого процессорного времени. Квант q=2q = 2 мс. Для прозрачности переключение контекста считаем мгновенным, блокировок и новых поступлений нет.

Отрезок, мсПроцессЧто осталось после отрезка
0–2А3 мс
2–4Б2 мс
4–6В0 мс, процесс завершён
6–8А1 мс
8–10Б0 мс, процесс завершён
10–11А0 мс, процесс завершён

В начале очередь выглядит как А, Б, В. После первого отрезка А уходит в хвост, и очередь становится Б, В, А. После Б порядок - В, А, Б. В успевает выполнить всю работу за один квант и в очередь больше не возвращается. Последний отрезок А длится всего 1 мс: ждать конца выделенных 2 мс для завершения не нужно.

Диаграмма Round Robin при кванте 2 мс: А завершается в 11, Б в 10, В в 6 миллисекунд
Диаграмма Round Robin при кванте 2 мс: А завершается в 11, Б в 10, В в 6 миллисекунд

Время на диаграмме идёт слева направо. Суммарная полезная работа равна 5+4+2=115 + 4 + 2 = 11 мс, и в этой модели процессор занят непрерывно до момента 11. При добавлении цены переключений общая длительность увеличится; её нельзя вычислить без заданной стоимости и правила учёта переключений.

Ожидание, оборот и первый отклик

Для процесса ii обозначим момент прибытия через AiA_i, момент завершения через CiC_i, а требуемое процессорное время через BiB_i. Время оборота - это полный интервал от прибытия до завершения:

Ti=Ci−Ai.T_i = C_i - A_i.

Если процесс не блокируется и расходы переключения отдельно не учитываются, время ожидания в очереди равно Wi=Ti−BiW_i = T_i - B_i. В нашем примере моменты завершения А, Б, В равны 11, 10 и 6 мс. Значит, время ожидания составляет соответственно 11−5=611 - 5 = 6, 10−4=610 - 4 = 6 и 6−2=46 - 2 = 4 мс. Среднее ожидание равно (6+6+4)/3≈5,33(6 + 6 + 4)/3 \approx 5{,}33 мс.

Время первого отклика в этой модели - задержка от поступления до первого запуска. Она равна 0 мс для А, 2 мс для Б и 4 мс для В; среднее равно 2 мс. Отклик не равен завершению: А начинает сразу, но заканчивает последним. Если в задаче есть ввод-вывод, простое вычитание BiB_i из оборота включает также время блокировки; для ожидания именно в очереди нужно отдельно учесть все интервалы готовности.

Как проверить расчёт самостоятельно

Полезно вести рядом с диаграммой два списка: очередь готовых и оставшееся время каждого процесса. Перед очередным отрезком вычеркните первый элемент очереди; после отрезка уменьшите остаток ровно на длительность работы. Если остаток положителен и процесс не заблокировался, запишите его в хвост. Такая таблица особенно помогает, когда приход новых задач происходит во время исполнения: их помещают в очередь в момент прибытия, а не в начало следующего круга.

Проверьте также два контрольных соотношения. Сумма всех отрезков конкретного процесса должна равняться его потребности в процессорном времени. Время завершения не может предшествовать последнему отрезку этого процесса. В примере сумма отрезков А равна 2+2+1=52 + 2 + 1 = 5 мс, а Б выполняется дважды по 2 мс. В заканчивается в конце своего единственного отрезка. Если процессор простаивает, соответствующий промежуток нужно явно оставить пустым: это время не принадлежит ни одному процессу.

Как выбор кванта меняет поведение

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

Если квант не меньше каждой из оставшихся длительностей, процессы в нашем примере выполняются по очереди до завершения; расписание совпадает с FIFO. Для q=5q=5 порядок будет А, Б, В, а первые запуски - 0, 5 и 9 мс. При q=2q=2 они равны 0, 2 и 4 мс. Это сравнение относится к выбранной нагрузке, а не доказывает, что меньший квант всегда лучше: среднее время завершения и затраты на переключения могут измениться в противоположную сторону.

При фиксированном числе nn постоянно готовых процессов одного приоритета в идеальной модели между концом кванта процесса и его следующим запуском другие используют суммарно не более (n−1)q(n-1)q. Завершения уменьшают это ожидание. Новые поступления, приоритеты, блокировки и накладные расходы меняют условия оценки, поэтому переносить её на произвольную систему без оговорок нельзя.

Где применяется и с чем сравнивать

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

В Linux политика реального времени SCHED_RR чередует потоки одинакового статического приоритета по кванту; поток более высокого приоритета может вытеснить текущий. При возобновлении вытесненный таким образом поток использует оставшуюся часть своего кванта. Это описано в руководстве sched(7). Не следует считать, что все обычные приложения Linux планируются одной общей очередью Round Robin.

Планирование определяет, кому дать процессор, а семафоры помогают согласовать доступ процессов к общим ресурсам. Это разные задачи: регулярный запуск ещё не устраняет гонку данных. Аналогично конвейер команд процессора описывает организацию выполнения инструкций внутри процессора, а не порядок выбора готового процесса операционной системой.

Частые ошибки

  • Возвращать завершённый процесс в очередь. В хвост попадает только готовый процесс с оставшейся работой.
  • Путать ожидание с оборотом. Оборот включает и выполнение; отклик заканчивается уже при первом запуске.
  • Игнорировать блокировку. Ожидающий ввод-вывод процесс не конкурирует за процессор до возвращения в состояние готовности.
  • Не определить порядок событий на границе кванта. Одновременное прибытие и вытеснение могут изменить порядок очереди.
  • Считать переключение бесплатным во всех случаях. Так можно упростить учебный пример, но нельзя безусловно оценить реальное быстродействие.

FAQ

Может ли процесс завершиться до конца кванта?

Да. Квант задаёт верхнюю границу непрерывного исполнения в этой модели. Когда работы осталось меньше, процесс завершится сразу после её выполнения.

Гарантирует ли Round Robin одинаковое время ожидания?

Нет. На ожидание влияют порядок прибытия, длительности, квант и состояние очереди. В примере А и Б ждут по 6 мс, а В - 4 мс.

Что происходит, если готов только один процесс?

Он может получать процессор снова после своего кванта, если остаётся готовым. Реальные расходы зависят от реализации; отсутствие конкурента не означает, что обязательно происходит переключение на другой процесс.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Сегментная организация памяти: адреса и защита

Сегментная организация памяти: адреса и защита

Как работает сегментная организация памяти: номер сегмента, база, длина и смещение, проверка границ, пример трансляции адреса и сравнение со страницами.

8 ноября 20268 минут
Обход графа в ширину: очередь, слои и кратчайший путь

Обход графа в ширину: очередь, слои и кратчайший путь

Обход графа в ширину: как очередь раскладывает вершины по слоям, почему номер слоя равен кратчайшему расстоянию в невзвешенном графе, как восстановить путь по предкам и проверить двудольность.

24 сентября 202610 минут
Стек и очередь: чем LIFO отличается от FIFO

Стек и очередь: чем LIFO отличается от FIFO

Стек и очередь рядом: дисциплины LIFO и FIFO и порядок выхода элементов, очередь на кольцевом буфере за O(1), дек, таблица сложности операций и примеры применения.

24 сентября 20269 минут
Абсолютно неупругий удар: сохранение импульса

Абсолютно неупругий удар: сохранение импульса

Как найти скорость тел после абсолютно неупругого удара, применить закон сохранения импульса и вычислить потерю кинетической энергии на понятных примерах с формулами.

8 ноября 20268 минут
Абсолютное и избыточное давление: формулы и вакуум

Абсолютное и избыточное давление: формулы и вакуум

Абсолютное и избыточное давление, разрежение и вакуум: как выбрать начало отсчёта, перевести показания манометра и решить задачи с примерами в килопаскалях.

8 ноября 20268 минут
АЦП последовательного приближения: схема и принцип работы

АЦП последовательного приближения: схема и принцип работы

Разберите схему АЦП последовательного приближения: как компаратор, ЦАП и регистр определяют код по битам, как вычислить шаг квантования и оценить погрешность.

8 ноября 20268 минут