Планирование с квантованием времени

Планирование с квантованием времени — это метод управления вычислительными процессами, при котором центральный процессор (ЦП) поочередно выделяет каждому активному процессу фиксированный или динамически изменяемый промежуток времени (квант), после чего происходит принудительное переключение на следующий процесс. Данный подход является основой для реализации вытесняющих алгоритмов планирования (preemptive scheduling) в многозадачных операционных системах, обеспечивая иллюзию одновременного выполнения нескольких программ на одном процессоре.

История

Концепция разделения времени (time-sharing) возникла в 1950-х — начале 1960-х годов в связи с необходимостью повышения эффективности использования дорогостоящих вычислительных машин. Первые системы, такие как Compatible Time-Sharing System (CTSS), разработанная в Массачусетском технологическом институте в 1961 году, и Multics (начало 1960-х), внедрили механизмы циклического переключения между задачами. В 1960-х годах данная модель была формализована в рамках теории планирования процессов, в частности в работах Фернандо Корбато и других исследователей. Широкое распространение планирование с квантованием времени получило с появлением операционных систем общего назначения (UNIX, начиная с Version 6, 1975 год; Microsoft Windows, начиная с Windows NT, 1993 год; Linux, с версии 0.01, 1991 год). В современных операционных системах данный метод является одним из базовых.

Основные принципы

Квант времени

Квант времени (time quantum, time slice) — это максимальный период, на который процессу предоставляется процессор без прерывания. Длина кванта является критическим параметром планировщика. Слишком большой квант приводит к снижению отзывчивости системы (интерактивные процессы долго ждут очереди). Слишком малый квант вызывает чрезмерные накладные расходы на переключение контекста (сохранение/восстановление регистров, обновление таблиц процессов). Типичные значения кванта в современных ОС колеблются от 10 до 100 миллисекунд. В некоторых системах квант может динамически изменяться в зависимости от поведения процесса (чем больше процесс использует ЦП, тем меньше его приоритет и квант; чем больше процесс ожидает ввода-вывода, тем приоритет повышается).

Переключение контекста

Переключение контекста (context switch) — это процедура сохранения состояния текущего процесса (счетчик команд, регистры, указатель стека) и восстановления состояния следующего выбранного процесса. Данная операция требует времени процессора и является накладным расходом. Основную часть времени занимает сохранение/восстановление регистрового файла и обновление кэша процессора. В среднем переключение контекста занимает от нескольких микросекунд (на современных архитектурах x86) до десятков микросекунд. Суммарные накладные расходы системы зависят от частоты переключений: чем меньше квант, тем выше доля процессорного времени, затрачиваемая на переключения.

Типы алгоритмов планирования с квантованием

Циклическое планирование (Round Robin, RR)

Наиболее простой и распространенный алгоритм. Все процессы помещаются в очередь FIFO (первым пришёл — первым обслужен). Планировщик поочередно выбирает процесс из начала очереди и запускает его на выполнение на один квант. По истечении кванта, если процесс не завершился и не был заблокирован (например, операцией ввода-вывода), он снова помещается в конец очереди. Таким образом, каждый процесс последовательно получает равную долю процессорного времени. Алгоритм Round Robin является вытесняющим, так как процесс принудительно отнимается от процессора по таймеру. Данный метод эффективен для систем с интерактивными пользователями, обеспечивая предсказуемое время ответа.

Многоуровневая очередь с обратной связью (Multilevel Feedback Queue, MLFQ)

Более гибкий алгоритм, используемый в большинстве современных ОС. Он организует несколько очередей с разными приоритетами и разными квантами времени. Новый процесс помещается в очередь наивысшего приоритета (с самым маленьким квантом). Если процесс не завершается в пределах своего кванта, его приоритет понижается, и он переводится в следующую очередь с более длинным квантом. Если процесс, находящийся в нижней очереди, сам освобождает процессор (блокируется по I/O), его приоритет может повышаться. Это позволяет интерактивным процессам (с частыми операциями ввода-вывода) получать процессор быстро, а долгие вычислительные процессы — реже, но с более крупным квантом для снижения накладных расходов. В Linux планировщик CFS (Completely Fair Scheduler) реализует подобную логику через взвешенную справедливую очередь.

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

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

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

Недостатки

• Накладные расходы: каждое переключение контекста требует процессорного времени и памяти (обновление кэша). Слишком малый квант делает накладные расходы значительными.
• Проблемы с процессами реального времени: для задач с жесткими временными ограничениями (управление станками, автопилоты) метод не гарантирует завершение расчета в заданный срок.
• Сложность настройки: выбор оптимального кванта и приоритетов для многоуровневых очередей требует тонкой настройки под конкретную нагрузку.
• Фрагментация кэша: частое переключение приводит к сбросу кэш-памяти, что снижает производительность вычислений.

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

Linux

В ядре Linux (начиная с версии 2.6.23) используется планировщик CFS, реализующий модифицированное «справедливое» квантование. Вместо фиксированного кванта CFS распределяет процессорное время пропорционально «весу» каждого процесса (низкий вес — меньше времени). Планировщик виртуализирует время: он записывает «виртуальное время работы» каждого процесса и выбирает тот, у кого это наименьшее. Переключение происходит по таймеру, обычно с периодом 4–8 мс (на настольных системах). Для процессов в реальном времени (SCHED_FIFO, SCHED_RR) квант времени задается явно (обычно 100–1000 мс).

Microsoft Windows

В Windows (NT-ядро) используется планировщик с многоуровневой очередью с обратной связью. Кванты времени по умолчанию:

• Для настольных версий (Windows 10/11): 2 такта системного таймера (обычно около 30–60 мс).
• Для серверных версий (Windows Server): дольше, до 120–180 мс, для повышения пропускной способности фоновых задач.

macOS (XNU)

Планировщик macOS использует гибридный подход: для интерактивных приложений — вытесняющий RR с квантом около 10 мс; для фоновых задач — честное разделение по аналогии с CFS.

Сравнение с другими методами планирования

Интересные факты

• В ранних версиях UNIX (Version 6, 7) планировщик использовал простую многоуровневую очередь с фиксированными квантами (по 100 мс) и приоритетом, зависящим от объема использованного процессорного времени.
• В операционной системе FreeRTOS (для микроконтроллеров) планирование с квантованием времени (Round Robin) является опциональным и включается отдельной конфигурацией configUSE_TIME_SLICING.
• В системах управления базами данных (СУБД), таких как Oracle, собственное планирование потоков иногда применяет квантование для равномерного распределения нагрузки между ядрами, что снижает задержки запросов.

Критика и ограничения

Основная критика метода связана с тем, что квантование времени — компромисс между справедливостью и эффективностью. Исследования (например, «The Case for Small Quantum» в 1970-х годах) показали, что уменьшение кванта ведет к квадратичному росту накладных расходов. Кроме того, для многопроцессорных систем с общим кэшем (NUMA-архитектуры) частое переключение может приводить к сильной деградации производительности из-за миграции процессов между ядрами. В таких системах современные планировщики (в Linux — с ядром 5.x и новее) стремятся закреплять процессы за конкретными ядрами (CPU pinning), чтобы минимизировать переключения контекста.

Источники:

• Таненбаум Э., Бос Х. «Современные операционные системы»
• Сильбершатц А., Гэвин П., Гэгн Г. «Операционные системы: внутреннее устройство и принципы проектирования»
• Документация ядра Linux (Documentation/scheduler/sched-design-CFS.rst)
• Документация Microsoft Windows (Microsoft Docs: «Windows Kernel-Mode Scheduler»)
• Статья «Round-robin scheduling» в журнале «IEEE Computer» (1973)