Диспетчер операционной системы

Диспетчер может ставить перед собой следующие задачи:

• Максимизация пропускной способности — общего количества выполненных работ за единицу времени.
• Минимизация времени ожидания — промежутка между готовностью задачи к исполнению и фактическим началом её выполнения.
• Минимизация задержки или времени отклика — времени от готовности задачи до её полного завершения (для пакетных систем), или времени до выдачи первого результата пользователю (для интерактивных систем)^[1][2][3][4].
• Максимизация справедливости — равномерное распределение времени процессора между задачами с учётом их приоритета и характера нагрузки.

На практике указанные цели могут противоречить друг другу (например, пропускная способность и задержка), поэтому диспетчер реализует определённый компромисс между ними, исходя из требований и ожиданий пользователя.

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

Диспетчер представляет собой модуль операционной системы, выбирающий очередную задачу, которую необходимо допустить в систему, а также следующий процесс к запуску. Современные ОС обычно реализуют три типа диспетчеров: долгосрочный (принимающий), среднесрочный и краткосрочный. Названия отражают относительную частоту выполнения их функций.

Диспетчер процессов — часть операционной системы, определяющая, какой процесс должен исполниться в данный момент времени. Обычно он может приостанавливать работающий процесс, переводить его в конец очереди и запускать новый; такой диспетчер называется преемптивным, иначе — кооперативным^[5].

Различают три уровня диспетчеризации: долгосрочная, среднесрочная и краткосрочная, в зависимости от частоты принятия решений^[6].

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

Процессы обычно делятся на ориентированные на ввод-вывод и ориентированные на процессор. Если все процессы — ориентированные на ввод-вывод, очередь готовых задач будет почти всегда пуста, и краткосрочному диспетчеру практически нечего распределять; если же все процессы — процессорные, устройства ввода-вывода простаивают, и система теряет баланс. Наибольшая производительность достигается при грамотной смеси обоих типов. В современных ОС используются механизмы для выделения процессорного времени задачам реального времени^[7].

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

Некоторые ОС добавляют новые задачи только при гарантии соблюдения всех дедлайнов по времени. Конкретный алгоритм решения о допуске задач называется механизмом контроля приёма^[8].

Среднесрочный диспетчер временно удаляет процессы из оперативной памяти во вторичное хранилище (например, на жёсткий диск), либо возвращает их обратно — операции выгрузки (swapping out) и загрузки обратно (swapping in). Обычно выгружает процессы, которые долго неактивны, имеют низкий приоритет, часто вызывают page fault или занимают много памяти. По освобождении ресурсов или изменении состояния процесса, тот может быть вновь загружен в ОЗУ.

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

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

Дополнительным компонентом выступает диспетчер (dispatcher) — модуль, передающий управление выбранному краткосрочным диспетчером процессу. Его функции:

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

Время, необходимое для полной пересылки управления между процессами, называется латентностью диспетчеризации (dispatch latency)^[7].

Дисциплина планирования (или политика/алгоритм планирования) — это алгоритм распределения ресурсов между одновременными заявками. Применяется как в маршрутизаторах для распределения пакетов, так и в ОС (распределение времени процессора между потоками и процессами), дисковых подсистемах, очередях печати, встроенных системах и пр.

Основные задачи алгоритмов — недопущение голодания процессов (starvation) и обеспечение справедливости. В данной секции представлены самые распространённые алгоритмы.

В пакетных сетях и при статистическом мультиплексировании, под алгоритмом планирования подразумевают альтернативу классическим очередям по принципу FIFO (first-in, first-out — «первым пришёл — первым ушёл»).

Основные известные методы:

• Циклическое планирование (round-robin);
• Справедливое выравнивание очередей (fair queuing);
• Пропорционально-справедливое планирование (proportional-fair);
• Планирование по максимальному пропуску (maximum throughput);
• Взвешенное справедливое планирование (weighted fair queuing) — применяется при необходимости гарантировать качество обслуживания.

В современных беспроводных сетях, например HSDPA (3,5G), актуальны алгоритмы каналозависимого планирования (channel-dependent scheduling), учитывающие состояние канала связи. В расширенных стандартах (например, LTE Advanced), планирование реализуется на основе динамического выделения пакетов и распределения частотных диапазонов между пользователями^[9].

Первым пришёл — первым обслужен (FIFO, FCFS) — простейший алгоритм планирования, помещающий задачи в очередь по мере поступления.

• Переключение контекста производится только после завершения процесса, очереди не требуют перестройки — минимальные накладные расходы.
• Пропускная способность может быть невысокой из-за эффекта «каравана» — длинные процессы задерживают короткие.
• Отсутствует «голодание» — все процессы гарантировано получат процессор.
• Время отклика, ожидания и обслуживания определяется порядком прихода и зачастую велико.
• Нет приоритезации, сложно обеспечивать дедлайны процессов.
• Система основана на очереди.

Наиболее ранний срок выполнения (Earliest Deadline First, EDF) — динамический алгоритм, применяемый в ОС реального времени; задачи помещаются в приоритетную очередь по сроку их исполнения. При возникновении события (появление новой задачи, завершение, освобождение ресурса) выбирается ближайший по сроку процесс.

Похоже на алгоритм Shorted Job First (SJF). Диспетчер выбирает задачу с наименьшим прогнозируемым временем до завершения. Для работы требует оценки или знания полного времени выполнения процессов.

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

Операционная система назначает каждому процессу фиксированный приоритет. Низкоприоритетные задачи прерываются появлением более приоритетных.

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

Диспетчер выделяет каждому процессу фиксированный квант времени и по кругу переключает задачи. Если процесс завершился за отведённый период — его удаляют, иначе возвращают в очередь.

• Накладные расходы возрастают при коротких квантах.
• Баланс между FIFO и SJF: короткие задачи завершаются быстрее, длинные — медленнее, чем при SJF.
• Жёстких дедлайнов алгоритм обычно не гарантирует.
• «Голодание» процессов невозможно — процессы обслуживаются по времени прибытия.

Используется, если процессы естественно делятся на классы (например, интерактивные и фоновые). Разным уровням может соответствовать индивидуальный алгоритм планирования.

Работоспособный диспетчер всегда старается занять доступные ресурсы, пока в очереди есть готовые к планированию задачи. Неработоспособные (non-work conserving) допускают простой ресурсов даже при наличии ожидающих процессов.

Классические задачи: решение о размещении каждого задания на определённой станции во времени с целью минимизации общего времени выполнения (makespan):

• Job-shop scheduling — n заданий и m одинаковых станций, каждое задание выполняется на одной машине.
• Open-shop scheduling — n заданий, m разных станций, каждое задание выполняется на всех станциях в свободном порядке.
• Flow-shop scheduling — n заданий, m станций, последовательность операций фиксирована.

Во встроенных системах часто применяется ручное назначение задач, зачастую с разделением ядра на несколько уровней (ручной, прерываемый, прерывания).

• Не возникает голода.
• Высокая предсказуемость, применимо в системах жёсткого реального времени.
• Минимальные накладные расходы.
• Эффективность зависит от реализации.

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

Например, Windows NT/XP/Vista реализуют многоуровневую очередь с обратной связью — сочетание статического приоритета, round-robin и FIFO. Приоритет потоков изменяется динамически в зависимости от обработанности и времени ожидания.

Алгоритмы могут быть простыми, например, циклический обход, при котором каждому процессу выделяется равный квант времени (обычно 1—100 мс), или более сложными, учитывающими приоритет процессов.

В системах с несколькими процессорами (SMP) применяется аффинность процесса к процессору для повышения общей производительности за счёт уменьшения потерь на переключение контекста и работу кэша.

OS/360 поддерживал три диспетчера:

• Одиночный последовательный (PCP): последовательное выполнение потока заданий.
• Многопоточный последовательный (MFT): выполнение нескольких заданий, приоритет выбирается для каждого потока или задания отдельно.
• Многоприоритетный (MVT): предварительный выбор приоритета и памяти каждым заданием.

Позднее функция расширена диспетчером рабочих нагрузок (Workload Manager) для гибкой схемы распределения ресурсов процессора.

Ранние MS-DOS и версии Windows не поддерживали многозадачности и не имели диспетчера. Windows 3.1x использовала кооперативное планирование: приложения сами передавали управление ОС. С Windows 95 внедрён примитивный преемптивный диспетчер для 32-битных приложений, однако 16-битные программы запускались по старой модели^[10].

Семейство Windows NT — диспетчер многоуровневых очередей с обратной связью, 32 уровня приоритета: 0-15 — обычные, 16-31 — приоритеты «мягкого» реального времени, 0 — зарезервировано для ОС. Приоритет потоков и процессов может корректироваться динамически в зависимости от характера работы (интерактивность, I/O, и пр.)^[11]. В Windows Vista для учёта времени работы потоков по процессору используется аппаратный счётчик (Time Stamp Counter)^[12]. Vista также внедрила приоритезацию I/O-очереди, чтобы процессы обслуживания не мешали пользовательским^[13].

В Mac OS 9 применяется кооперативное планирование потоков внутри процесса и преемптивное — для параллельных задач. Все процессы Process Manager исполняются в особой «голубой задаче» и планируются по кооперативному алгоритму (по кругу); Thread Manager кооперирует потоки внутри процесса^[14].

macOS использует многоуровневую очередь с четырьмя диапазонами приоритета: обычные, системные, только ядро, задачи реального времени^[15]. Потоки планируются в преемптивном режиме, поддерживается и кооперативное выполнение в Thread Manager (Carbon)^[14].

В AIX 4 поддерживаются три политики: FIFO (до блокировки или появления более приоритетного), Round Robin (с квантом 10 мс), и OTHER (по POSIX, реализован как RR для нефиксированных приоритетов). В AIX 5 реализованы FIFO, RR и справедливое планирование (SCHED_OTHER); FIFO бывает трёх вариантов^[16].

• Linux 1.2 — круговое планирование^[17].
• Linux 2.2 — добавление классов планирования и многопроцессорность^[17].
• Linux 2.4 — O(n) планировщик, многоуровневая обратная связь (0-99 — задачи реального времени, 100—140 — обычные, «приятные» задачи), expired queue^[17].
• Linux 2.6.0 — 2.6.22 — O(1) планировщик Ingo Molnar-а, патчи для интерактивности от Con Kolivas.
• Linux 2.6.23 — 6.5 — Completely Fair Scheduler (CFS), вдохновлён работами Kolivas (Rotating Staircase Deadline, fair-share scheduling). Первая реализация справедливого планировщика для общего применения^[18][19].
• Linux 6.6 — с 2023 года введён планировщик EEVDF, призванный заменить патчи latency nice^[20][21][22].
• Linux 6.12 — поддержка userspace scheduler extensions, sched_ext, которые могут полностью заменять стандартный алгоритм^[23][24].

В FreeBSD используется многоуровневая обратная связь с приоритетами 0-255: 0-63 для прерываний, 64-127 для ядра, 128—159 для потоков реального времени, 160—223 — обычные задачи, 224—255 — задачи простоя, также предусмотрена idle queue^[25].

NetBSD: приоритеты 0-223, 0-63 — потоки по умолчанию (SCHED_OTHER), 64-95 — пользовательские потоки в режиме ядра, 96-128 — потоки ядра, 128—191 — потоки пользователя реального времени (SCHED_FIFO, SCHED_RR), 192—223 — программные прерывания.

Solaris: многоуровневая очередь, приоритеты 0-169. 0-59 — основное время, 60-99 — системные потоки, 100—159 — задачи реального времени, 160—169 — низкоприоритетные прерывания. С версии Solaris 9 добавлены классы «фиксированного приоритета» и «справедливого распределения» (fair share class), где потоки получают ресурс в соответствии с назначенными долями CPU^[7].