Информатика · объяснение и практика

Round Robin: очередь, первый отклик и завершение

Планирование Round Robin: квант, очередь готовых задач, время первого ответа и завершения на собственной трассе.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Операционные системы и память: углубление · Учебная карта

В маршруте Цифровая схема и работа вычислителя · 10 тем

Главная мысль

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

Явно задаём упрощённые условия

Пусть А и Б поступили одновременно в момент 0, очередь начинается с А. Им требуется соответственно 5 и 3 условные единицы процессорного времени. Квант равен 2, ввода-вывода и затрат на переключение нет. Эти ограничения позволяют проверить расписание на бумаге, не выдавая его за точную модель современной системы.

Сначала А работает с 0 до 2, затем Б с 2 до 4. У А осталось 3, у Б — 1. А получает следующий ход с 4 до 6. Б заканчивает с 6 до 7, не расходуя лишнюю единицу кванта; ждать его окончания пустым процессор не должен.

Продолжаем до завершения и считаем метрики

После завершения Б остаётся А с одной единицей. Она выполняется с 7 до 8. Суммарная занятость 8 совпадает с 5+3, а ни одна задача не получила больше требуемого времени. Это две независимые проверки трассы, полезные при сложной очереди с несколькими участниками.

Первый запуск А произошёл в 0, Б — в 2. При поступлении обеих в 0 их время до первого запуска равно 0 и 2. Полное время в системе равно 8 для А и 7 для Б. Эти числа отвечают на разные вопросы, поэтому раннее появление реакции не означает столь же раннего окончания всей работы.

Пример

А:0–2; Б:2–4; А:4–6; Б:6–7; А:7–8. Б заканчивает в 7, А — в 8.

Завершившаяся задача сразу уходит из очереди. Остаток её неиспользованного кванта не превращается в обязательный простой.

Цена слишком частых переключений

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

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

От чтения к действию

А теперь — вы

А и Б пришли в 0, А первая. Длительности 3 и 1, квант 2, накладных затрат нет. Когда заканчивается Б?

Частые вопросы

Каждый ход всегда длится ровно квант?

Нет. Завершение или блокировка могут закончить ход раньше; в этой модели задача работает до минимума из кванта и остатка.

Round Robin минимизирует любое время ожидания?

Нет. Его оценивают с учётом отклика, справедливости и расходов; разные цели требуют разных политик.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться