Диспетчер операционной системы
Диспетчер операционной системы (англ. scheduler, также диспетчер задач или планировщик) — это программный компонент в вычислительной технике, назначающий ресурсы для выполнения задач. К ресурсам относятся процессоры, сетевые каналы и карты расширения. Задачи, в зависимости от типа системы, могут представлять собой потоки, процессы или потоки данных.
Работает диспетчер с целью загрузить системные ресурсы максимально эффективно (например, с помощью балансировки нагрузки), обеспечить одновременный доступ нескольких пользователей к ресурсам, либо достичь заданного качества обслуживания.
Диспетчер операционной системы — фундаментальный компонент вычислительных систем, ключевой для реализации многозадачности и исполнительной модели: именно благодаря алгоритмам планирования возможно выполнение нескольких задач на одном процессоре, реализуя многозадачность.
Цели
Диспетчер может ставить перед собой следующие задачи:
- Максимизация пропускной способности — общего количества выполненных работ за единицу времени.
- Минимизация времени ожидания — промежутка между готовностью задачи к исполнению и фактическим началом её выполнения.
- Минимизация задержки или времени отклика — времени от готовности задачи до её полного завершения (для пакетных систем), или времени до выдачи первого результата пользователю (для интерактивных систем)[1].[2] [3][4]
- Максимизация справедливости — равномерное распределение времени процессора между задачами с учётом их приоритета и характера нагрузки.
На практике указанные цели могут противоречить друг другу (например, пропускная способность и задержка), поэтому диспетчер реализует определённый компромисс между ними, исходя из требований и ожиданий пользователя.
В системах реального времени, таких как встроенные системы промышленного контроля и робототехника, диспетчер обязан обеспечивать соблюдение жёстких временных ограничений (дедлайнов) для поддержания стабильной работы. Задачи могут также распределяться по удалённым устройствам через сеть и администрироваться централизованно.
Типы диспетчеров в операционной системе
Диспетчер представляет собой модуль операционной системы, выбирающий очередную задачу, которую необходимо допустить в систему, а также следующий процесс к запуску. Современные ОС обычно реализуют три типа диспетчеров: долгосрочный (принимающий), среднесрочный и краткосрочный. Названия отражают относительную частоту выполнения их функций.
Диспетчер процессов
Диспетчер процессов — часть операционной системы, определяющая, какой процесс должен исполниться в данный момент времени. Обычно он может приостанавливать работающий процесс, переводить его в конец очереди и запускать новый; такой диспетчер называется преемптивным, иначе — кооперативным[5].
Различают три уровня диспетчеризации: долгосрочная, среднесрочная и краткосрочная, в зависимости от частоты принятия решений[6].
Долгосрочный диспетчер
Долгосрочный диспетчер (или принимающий) определяет, какие задания или процессы будут помещены в очередь готовых задач (в оперативной памяти). При запуске программы разрешение на включение в группу выполняемых процессов даётся именно долгосрочным диспетчером. Он определяет степень многопрограммности — то есть, количество одновременно исполняемых процессов и их соотношение по характеру работы (ориентированные на ввод-вывод либо на процессор). Это позволяет поддерживать сбалансированную нагрузку системы.
Процессы обычно делятся на ориентированные на ввод-вывод и ориентированные на процессор. Если все процессы — ориентированные на ввод-вывод, очередь готовых задач будет почти всегда пуста, и краткосрочному диспетчеру практически нечего распределять; если же все процессы — процессорные, устройства ввода-вывода простаивают, и система теряет баланс. Наибольшая производительность достигается при грамотной смеси обоих типов. В современных ОС используются механизмы для выделения процессорного времени задачам реального времени[7].
Долгосрочный диспетчер особенно важен для крупных систем — пакетной обработки, кластеров, суперкомпьютеров и рендер-ферм. Для согласованной работы взаимодействующих процессов применяются специальные планировщики заданий.
Некоторые ОС добавляют новые задачи только при гарантии соблюдения всех дедлайнов по времени. Конкретный алгоритм решения о допуске задач называется механизмом контроля приёма[8].
Среднесрочный диспетчер
Среднесрочный диспетчер временно удаляет процессы из оперативной памяти во вторичное хранилище (например, на жёсткий диск), либо возвращает их обратно — операции выгрузки (swapping out) и загрузки обратно (swapping in). Обычно выгружает процессы, которые долго неактивны, имеют низкий приоритет, часто вызывают page fault или занимают много памяти. По освобождении ресурсов или изменении состояния процесса, тот может быть вновь загружен в ОЗУ.
В современных системах среднесрочный диспетчер часто совмещается по функциям с долгосрочным: двоичные файлы трактуются как выгруженные процессы, и необходимые сегменты подгружаются по мере надобности (так называемая ленивая загрузка или загрузка по прерыванию).
Краткосрочный диспетчер
Краткосрочный диспетчер (или диспетчер ЦП) определяет, какой из готовых процессов оперативной памяти будет запущен следующим — после аппаратного прерывания таймера, ввода-вывода, системного вызова или иного события. Такие решения принимаются намного чаще, чем на долгосрочном или среднесрочном уровнях — как минимум после каждого кванта времени, зачастую за доли миллисекунды. Диспетчер может работать в режиме преемптивного управления процессами (форсировано снимать процессора при необходимости) или в кооперативном режиме (процесс "уступает" процессор сам).
Диспетчеризация (dispatcher)
Дополнительным компонентом выступает диспетчер (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].
First come, first served (FCFS, FIFO)
Первым пришёл — первым обслужен (FIFO, FCFS) — простейший алгоритм планирования, помещающий задачи в очередь по мере поступления.
- Переключение контекста производится только после завершения процесса, очереди не требуют перестройки — минимальные накладные расходы.
- Пропускная способность может быть невысокой из-за эффекта "каравана" — длинные процессы задерживают короткие.
- Отсутствует "голодание" — все процессы гарантировано получат процессор.
- Время отклика, ожидания и обслуживания определяется порядком прихода и зачастую велико.
- Нет приоритезации, сложно обеспечивать дедлайны процессов.
- Система основана на очереди.
Приоритетное планирование
Наиболее ранний срок выполнения (Earliest Deadline First, EDF) — динамический алгоритм, применяемый в ОС реального времени; задачи помещаются в приоритетную очередь по сроку их исполнения. При возникновении события (появление новой задачи, завершение, освобождение ресурса) выбирается ближайший по сроку процесс.
Shortest remaining time first (SRTF)
Похоже на алгоритм Shorted Job First (SJF). Диспетчер выбирает задачу с наименьшим прогнозируемым временем до завершения. Для работы требует оценки или знания полного времени выполнения процессов.
- При появлении более короткой задачи текущий процесс прерывается, вызывая дополнительную нагрузку на систему.
- Обеспечивает максимальную пропускную способность в большинстве случаев.
- Время ожидания и отклика растёт для длинных процессов.
- Не учитывает дедлайны, долгие процессы могут "голодать" при большом потоке коротких заданий.
Fixed-priority pre-emptive scheduling
Операционная система назначает каждому процессу фиксированный приоритет. Низкоприоритетные задачи прерываются появлением более приоритетных.
- Накладные расходы — умеренные.
- Нет явных преимуществ в пропускной способности над FIFO.
- При немногочисленных уровнях приоритета система аналогична множеству очередей FIFO.
- Высокоприоритетные процессы обслуживаются быстрее, но возможна блокировка низкоприоритетных.
- Для задач с дедлайнами удобно повышать приоритет.
Циклическое планирование (round-robin)
Диспетчер выделяет каждому процессу фиксированный квант времени и по кругу переключает задачи. Если процесс завершился за отведённый период — его удаляют, иначе возвращают в очередь.
- Накладные расходы возрастают при коротких квантах.
- Баланс между FIFO и SJF: короткие задачи завершаются быстрее, длинные — медленнее, чем при SJF.
- Жёстких дедлайнов алгоритм обычно не гарантирует.
- "Голодание" процессов невозможно — процессы обслуживаются по времени прибытия.
Многоуровневое планирование
Используется, если процессы естественно делятся на классы (например, интерактивные и фоновые). Разным уровням может соответствовать индивидуальный алгоритм планирования.
Работоспособные диспетчеры (work-conserving scheduler)
Работоспособный диспетчер всегда старается занять доступные ресурсы, пока в очереди есть готовые к планированию задачи. Неработоспособные (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 и преемники
OS/360 поддерживал три диспетчера:
- Одиночный последовательный (PCP): последовательное выполнение потока заданий.
- Многопоточный последовательный (MFT): выполнение нескольких заданий, приоритет выбирается для каждого потока или задания отдельно.
- Многоприоритетный (MVT): предварительный выбор приоритета и памяти каждым заданием.
Позднее функция расширена диспетчером рабочих нагрузок (Workload Manager) для гибкой схемы распределения ресурсов процессора.
Windows
Ранние 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 и macOS
В Mac OS 9 применяется кооперативное планирование потоков внутри процесса и преемптивное — для параллельных задач. Все процессы Process Manager исполняются в особой "голубой задаче" и планируются по кооперативному алгоритму (по кругу); Thread Manager кооперирует потоки внутри процесса[14].
macOS использует многоуровневую очередь с четырьмя диапазонами приоритета: обычные, системные, только ядро, задачи реального времени[15]. Потоки планируются в преемптивном режиме, поддерживается и кооперативное выполнение в Thread Manager (Carbon)[14].
AIX
В AIX 4 поддерживаются три политики: FIFO (до блокировки или появления более приоритетного), Round Robin (с квантом 10 мс), и OTHER (по POSIX, реализован как RR для нефиксированных приоритетов). В AIX 5 реализованы FIFO, RR и справедливое планирование (SCHED_OTHER); FIFO бывает трёх вариантов[16].
Linux
- 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
В FreeBSD используется многоуровневая обратная связь с приоритетами 0–255: 0–63 для прерываний, 64–127 для ядра, 128–159 для потоков реального времени, 160–223 — обычные задачи, 224–255 — задачи простоя, также предусмотрена idle queue[25].
NetBSD
NetBSD: приоритеты 0–223, 0–63 — потоки по умолчанию (SCHED_OTHER), 64–95 — пользовательские потоки в режиме ядра, 96–128 — потоки ядра, 128–191 — потоки пользователя реального времени (SCHED_FIFO, SCHED_RR), 192–223 — программные прерывания.
Solaris
Solaris: многоуровневая очередь, приоритеты 0–169. 0–59 — основное время, 60–99 — системные потоки, 100–159 — задачи реального времени, 160–169 — низкоприоритетные прерывания. С версии Solaris 9 добавлены классы "фиксированного приоритета" и "справедливого распределения" (fair share class), где потоки получают ресурс в соответствии с назначенными долями CPU[7].
Сводная таблица
| Операционная система | Преемпция | Алгоритм |
|---|---|---|
| Amiga OS | Да | Приоритетное круговое планирование |
| FreeBSD | Да | Многоуровневая очередь с обратной связью |
| Ядро Linux до 2.6.0 | Да | Многоуровневая очередь с обратной связью |
| Linux 2.6.0–2.6.23 | Да | O(1) планировщик |
| Linux 2.6.23–6.6 | Да | Completely Fair Scheduler |
| Linux начиная с 6.6 | Да | EEVDF |
| классическая Mac OS до 9 версии | Нет | Кооперативный планировщик |
| Mac OS 9 | Частично | Преемптивный планировщик для многозадачных заданий, кооперативный — для потоков и процессов |
| macOS | Да | Многоуровневая очередь с обратной связью |
| NetBSD | Да | Многоуровневая очередь с обратной связью |
| Solaris | Да | Многоуровневая очередь с обратной связью |
| Windows 3.1x | Нет | Кооперативный планировщик |
| Windows 95, Windows 98, Windows Me | Частично | Преемптивный для 32-битных, кооперативный для 16-битных процессов |
| Windows NT (2000, XP, Vista, 7, Server) | Да | Многоуровневая очередь с обратной связью |
Примечания
- ↑ C. L., Liu; Layland, James W. (январь 1973). “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”. Journal of the ACM. ACM. 20 (1): 46—61. DOI:10.1145/321738.321743. S2CID 207669821.
We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.
Проверьте дату в|date=(справка на английском) - ↑ Kleinrock, Leonard. Queueing Systems, Vol. 2: Computer Applications. — Wiley-Interscience, 1976. — P. 171. — «For a customer requiring x sec of service, his response time will equal his service time x plus his waiting time.». — ISBN 047149111X.
- ↑ Feitelson, Dror G. Workload Modeling for Computer Systems Performance Evaluation. — Cambridge University Press, 2015. — «if we denote the time that a job waits in the queue by t_w, and the time it actually runs by t_r, then the response time is r = t_w + t_r.». — ISBN 9781107078239.
- ↑ Silberschatz, Abraham. Operating System Concepts / Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. — Wiley Publishing, 2012. — P. 187. — «В интерактивной системе временем отклика называется время от подачи запроса до получения первого ответа. Эта мера отвечает на вопрос, насколько быстро начинается реакция системы, а не сколько времени занимает полный вывод результата.». — ISBN 978-0470128725.
- ↑ Paul Krzyzanowski. Process Scheduling: Who gets to run next? cs.rutgers.edu (19 февраля 2014). Дата обращения: 19 июня 2023.
- ↑ Raphael Finkel. Chapter 2: Time Management // An Operating Systems Vade Mecum. — Prentice Hall, 1988. — P. 27.
- ↑ 1 2 3 Abraham Silberschatz. Operating System Concepts / Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. — John Wiley & Sons, Inc., 2013. — Vol. 9. — ISBN 978-1-118-06333-0.
- ↑ Admission Control for Independently-authored Realtime Applications. UWSpace. Дата обращения: 10 марта 2023.
- ↑ Guowang Miao. Fundamentals of Mobile Data Networks / Guowang Miao, Jens Zander, Ki Won Sung … [и др.]. — Cambridge University Press, 2016. — ISBN 978-1107143210.
- ↑ Early Windows. Дата обращения: 12 мая 2023.
- ↑ A Tale of Two Schedulers Windows NT and Windows CE. Архивировано 22 июля 2012 года.
- ↑ Windows Administration: Inside the Windows Vista Kernel: Part 1. Technet.microsoft.com (14 ноября 2016). Дата обращения: 9 декабря 2016.
- ↑ Archived copy. blog.gabefrost.com. Дата обращения: 15 января 2022. Архивировано 19 февраля 2008 года.
- ↑ 1 2 Technical Note TN2028: Threading Architectures. developer.apple.com. Дата обращения: 15 января 2019.
- ↑ Mach Scheduling and Thread Interfaces. developer.apple.com. Дата обращения: 15 января 2019.
- ↑ AIX CPU monitoring and tuning. ibm.com. Дата обращения: 11 августа 2011. Архивировано 11 августа 2011 года.
- ↑ 1 2 3 Jones, M. Inside the Linux 2.6 Completely Fair Scheduler. developer.ibm.com (18 сентября 2018). Дата обращения: 7 февраля 2024.
- ↑ Molnár, Ingo [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]. Список рассылки (13 апреля 2007).
- ↑ Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin. Happyli.org. Дата обращения: 9 декабря 2016.
- ↑ EEVDF Scheduler May Be Ready For Landing With Linux 6.6 (англ.). Phoronix. Дата обращения: 31 августа 2023.
- ↑ EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced (англ.). Phoronix. Дата обращения: 7 февраля 2024.
- ↑ An EEVDF CPU scheduler for Linux [LWN.net]. LWN.net. Дата обращения: 31 августа 2023.
- ↑ Sched_ext Merged For Linux 6.12 - Scheduling Policies As BPF Programs (англ.). Phoronix. Дата обращения: 10 февраля 2025.
- ↑ Pluggable CPU schedulers - openSUSE Wiki. en.opensuse.org. Дата обращения: 10 февраля 2025.
- ↑ Comparison of Solaris, Linux, and FreeBSD Kernels. Архивировано 7 августа 2008 года.
Литература
- Блажевич, Яцек. Planowanie procesów komputerowych i produkcyjnych (на польском) / Яцек Блажевич, К.Х. Эккер, Е. Пеш … [и др.]. — 2. — Springer, 2001. — ISBN 3-540-41931-4.
- Уильям Столлингс. Operating Systems Internals and Design Principles. — fourth. — Prentice Hall, 2004. — ISBN 0-13-031999-6.
- Информация о планировщике O(1) в Linux 2.6. GitHub. Дата обращения: 5 мая 2025.
Дополнительная литература
- https://pages.cs.wisc.edu/~remzi/OSTEP/ — Операционные системы: три лёгких главы (Remzi H. Arpaci-Dusseau и Andrea C. Arpaci-Dusseau, 2014). Гл.: Введение в планирование, Многоуровневая очередь, Пропорционально-справедливое планирование, Планирование для многопроцессорных систем
- http://www.cs.sunysb.edu/~algorith/files/scheduling.shtml — Краткое введение в алгоритмы планирования работ
- https://web.archive.org/web/20060613130106/http://oreilly.com/catalog/linuxkernel/chapter/ch10.html — Раздел 10 "Планирование процессов" в Understanding the Linux Kernel
- http://kerneltrap.org/scheduler — Kerneltrap: статьи о планировщике Linux
- https://web.archive.org/web/20110811094049/http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html#N100F6 — Мониторинг и настройка CPU в AIX
- https://github.com/bdaehlie/linux-cpu-scheduler-docs/ — Введение в реализацию планировщика CPU Linux 2.6.8.1 Josh Aas
- Complexity results for scheduling problems (Brucker, Knust): http://www.mathematik.uni-osnabrueck.de/research/OR/class/
- http://rtime.felk.cvut.cz/scheduling-toolbox — TORSCHE Scheduling Toolbox для Matlab (алгоритмы планирования и графы)
- https://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6226795 — Опрос алгоритмов планирования пакетов для сотовых сетей
- https://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/43438.pdf — Управление крупными кластерами (Borg, Google)