Планирование (вычисления)

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

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

Планирование имеет основополагающее значение для вычислений как таковых и является неотъемлемой частью модели выполнения компьютерной системы; концепция планирования позволяет реализовать многозадачность компьютера с помощью одного центрального процессора (ЦП).

Планировщик может ставить перед собой одну или несколько целей, например:

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

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

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

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

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

Мы различаем долгосрочное планирование , среднесрочное планирование и краткосрочное планирование в зависимости от того, как часто должны приниматься решения. ^[6]

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

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

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

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

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

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

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

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

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

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

Диспетчер должен быть максимально быстрым, поскольку он вызывается во время каждого переключения процесса. Во время переключений контекста процессор фактически простаивает в течение части времени, поэтому следует избегать ненужных переключений контекста. Время, необходимое диспетчеру для остановки одного процесса и запуска другого, называется задержкой диспетчеризации . [ ^{7] : 155}

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

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

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

Простейшими алгоритмами планирования с наилучшими усилиями являются циклический перебор , справедливая организация очереди ( алгоритм справедливого планирования с максимальным и минимальным значениями ), пропорционально-справедливое планирование и максимальная пропускная способность . Если предлагается дифференцированное или гарантированное качество обслуживания , в отличие от связи с наилучшими усилиями, может использоваться взвешенная справедливая организация очереди .

В современных пакетных беспроводных сетях радиосвязи, таких как сотовая система HSDPA (High-Speed ​​Downlink Packet Access) 3.5G , планирование, зависящее от канала, может использоваться для использования информации о состоянии канала . Если условия канала благоприятны, пропускная способность и спектральная эффективность системы могут быть увеличены. В еще более современных системах, таких как LTE , планирование сочетается с динамическим распределением каналов , зависящим от канала, по пакетам , или путем назначения многонесущих OFDMA или других компонентов выравнивания в частотной области пользователям, которые могут использовать их наилучшим образом. ^[9]

First in, first out ( FIFO ), также известный как first come, first serve (FCFS), является простейшим алгоритмом планирования. FIFO просто ставит процессы в очередь в том порядке, в котором они поступают в очередь готовности. Это обычно используется дляочередь задач , например, как показано в этом разделе.

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

Earlyest deadline first (EDF) или least time to go — это динамический алгоритм планирования, используемый в операционных системах реального времени для помещения процессов в приоритетную очередь. Всякий раз, когда происходит событие планирования (завершение задачи, выпуск новой задачи и т. д.), в очереди будет выполнен поиск процесса, ближайшего к его крайнему сроку, который будет следующим запланированным для выполнения.

Аналогично стратегии shortest job first (SJF). С помощью этой стратегии планировщик размещает процессы с наименьшим предполагаемым временем обработки следующими в очереди. Это требует расширенных знаний или оценок о времени, необходимом для завершения процесса.

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

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

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

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

• Планирование RR влечет за собой значительные накладные расходы, особенно при небольшой единице времени.
• Сбалансированная пропускная способность между FCFS/FIFO и SJF/SRTF, более короткие задания выполняются быстрее, чем в FIFO, а более длинные процессы завершаются быстрее, чем в SJF.
• Хорошее среднее время отклика, время ожидания зависит от количества процессов, а не от средней продолжительности процесса.
• Из-за длительного времени ожидания в чистой системе RR сроки редко соблюдаются.
• Голодание не может произойти, поскольку приоритет не задан. Порядок распределения единиц времени основан на времени прибытия процесса, аналогично FIFO.
• Если интервал времени большой, он становится FCFS/FIFO, а если короткий, то он становится SJF/SRTF.

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

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

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

• Планирование работы в цехе  – есть n работ и m идентичных станций. Каждая работа должна быть выполнена на одной машине. Обычно это рассматривается как онлайн-задача.
• Планирование Open-shop  – есть n работ и m различных станций. Каждая работа должна провести некоторое время на каждой станции, в свободном порядке.
• Планирование Flow-shop  – есть n работ и m различных станций. Каждая работа должна провести некоторое время на каждой станции в заранее определенном порядке.

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

• Нет проблем с нехваткой ресурсов
• Очень высокая предсказуемость; позволяет реализовывать жесткие системы реального времени
• Почти никаких накладных расходов
• Может не подходить для всех приложений
• Эффективность полностью зависит от реализации

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

Например, Windows NT /XP/Vista использует многоуровневую очередь обратной связи , комбинацию фиксированного приоритета приоритетного планирования, циклического перебора и алгоритмов «первым пришел — первым обслужен». В этой системе потоки могут динамически увеличивать или уменьшать приоритет в зависимости от того, был ли он уже обслужен или находился в состоянии интенсивного ожидания. Каждый уровень приоритета представлен собственной очередью, с циклическим планированием среди потоков с высоким приоритетом и FIFO среди потоков с низким приоритетом. В этом смысле время отклика для большинства потоков короткое, а короткие, но критически важные системные потоки завершаются очень быстро. Поскольку потоки могут использовать только одну единицу времени циклического перебора в очереди с наивысшим приоритетом, голодание может стать проблемой для более длинных потоков с высоким приоритетом.

Используемый алгоритм может быть таким же простым, как циклический , в котором каждому процессу дается одинаковое время (например, 1 мс, обычно от 1 мс до 100 мс) в циклическом списке. Таким образом, процесс A выполняется в течение 1 мс, затем процесс B, затем процесс C, затем снова процесс A.

Более продвинутые алгоритмы учитывают приоритет процесса или важность процесса. Это позволяет некоторым процессам использовать больше времени, чем другим процессам. Ядро всегда использует все необходимые ему ресурсы для обеспечения надлежащего функционирования системы, и поэтому можно сказать, что оно имеет бесконечный приоритет. В системах SMP считается, что привязка процессора увеличивает общую производительность системы, даже если это может привести к более медленной работе самого процесса. Это обычно повышает производительность за счет снижения пробуксовки кэша .

IBM OS/360 была доступна с тремя различными планировщиками. Различия были таковы, что варианты часто считались тремя разными операционными системами:

• Опция единого последовательного планировщика , также известная как первичная программа управления (PCP), обеспечивала последовательное выполнение одного потока заданий.
• Опция Multiple Sequential Scheduler , известная как Multiprogramming with a Fixed Number of Tasks (MFT), обеспечивала выполнение нескольких параллельных заданий. Выполнение регулировалось приоритетом, который имел значение по умолчанию для каждого потока или мог быть запрошен отдельно для каждого задания. MFT версии II добавила подзадачи (потоки), которые выполнялись с приоритетом, основанным на приоритете родительского задания. Каждый поток заданий определял максимальный объем памяти, который мог использоваться любым заданием в этом потоке.
• Опция «Планировщики с несколькими приоритетами» или «Мультипрограммирование с переменным числом задач» (MVT) изначально включала подзадачи; каждое задание запрашивало приоритет и объем памяти, необходимые ему перед выполнением.

В более поздних версиях виртуального хранилища MVS в планировщик была добавлена ​​функция Workload Manager , которая распределяет ресурсы процессора в соответствии со сложной схемой, определяемой установкой.

Очень ранние системы MS-DOS и Microsoft Windows не были многозадачными и, как таковые, не имели планировщика. Windows 3.1x использовала невытесняющий планировщик, то есть он не прерывал программы. Он полагался на то, что программа завершала работу или сообщала ОС, что ей не нужен процессор, чтобы она могла перейти к другому процессу. Это обычно называется кооперативной многозадачностью. Windows 95 представила рудиментарный вытесняющий планировщик; однако для поддержки устаревших версий решила разрешить 16-битным приложениям работать без вытеснения. ^[10]

Операционные системы на базе Windows NT используют многоуровневую очередь обратной связи. Определено 32 уровня приоритета, от 0 до 31, при этом приоритеты от 0 до 15 являются обычными приоритетами, а приоритеты от 16 до 31 являются мягкими приоритетами реального времени, требующими привилегий для назначения. 0 зарезервирован для операционной системы. Пользовательские интерфейсы и API работают с классами приоритетов для процесса и потоков в процессе, которые затем объединяются системой в абсолютный уровень приоритета.

Ядро может изменять уровень приоритета потока в зависимости от его ввода-вывода и использования ЦП, а также от того, является ли он интерактивным (т. е. принимает и отвечает на ввод от людей), повышая приоритет интерактивных и ограниченных вводом-выводом процессов и понижая приоритет ограниченных ЦП процессов, чтобы увеличить скорость реагирования интерактивных приложений. ^[11] Планировщик был изменен в Windows Vista для использования регистра счетчика циклов современных процессоров для отслеживания точного количества циклов ЦП, выполненных потоком, а не просто использования процедуры прерывания интервального таймера. ^[12] Vista также использует приоритетный планировщик для очереди ввода-вывода, чтобы дефрагментаторы дисков и другие подобные программы не мешали операциям переднего плана. ^[13]

Mac OS 9 использует кооперативное планирование для потоков, где один процесс управляет несколькими кооперативными потоками, а также обеспечивает вытесняющее планирование для многопроцессорных задач. Ядро планирует многопроцессорные задачи с помощью алгоритма вытесняющего планирования. Все процессы Process Manager выполняются в рамках специальной многопроцессорной задачи, называемой синей задачей . Эти процессы планируются кооперативно с использованием алгоритма циклического планирования ; процесс передает управление процессором другому процессу, явно вызывая блокирующую функцию, такую ​​как WaitNextEvent. Каждый процесс имеет свою собственную копию Thread Manager, которая кооперативно планирует потоки этого процесса; поток передает управление процессором другому потоку, вызывая YieldToAnyThreadили YieldToThread. ^[14]

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

В AIX версии 4 существует три возможных значения политики планирования потоков:

• First In, First Out: После того, как поток с этой политикой запланирован, он выполняется до завершения, если только он не заблокирован, добровольно не уступает контроль над ЦП или поток с более высоким приоритетом не становится диспетчеризируемым. Только потоки с фиксированным приоритетом могут иметь политику планирования FIFO.
• Round Robin: Это похоже на схему round-robin планировщика AIX версии 3, основанную на 10-мс временных срезах. Когда поток RR получает управление в конце временного среза, он перемещается в конец очереди диспетчеризируемых потоков своего приоритета. Только потоки с фиксированным приоритетом могут иметь политику планирования Round Robin.
• ДРУГОЕ: Эта политика определена POSIX1003.4a как определяемая реализацией. В AIX версии 4 эта политика определена как эквивалентная RR, за исключением того, что она применяется к потокам с нефиксированным приоритетом. Пересчет значения приоритета работающего потока при каждом прерывании часов означает, что поток может потерять управление, поскольку его значение приоритета поднялось выше значения другого диспетчеризируемого потока. Это поведение AIX версии 3.

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

AIX 5 реализует следующие политики планирования: FIFO, round robin и fair round robin. Политика FIFO имеет три различных реализации: FIFO, FIFO2 и FIFO3. Политика round robin называется SCHED_RR в AIX, а fair round robin называется SCHED_OTHER. ^[16]

Linux 1.2 использовал политику циклического планирования . ^[17]

В Linux 2.2 добавлены классы планирования и поддержка симметричной многопроцессорной обработки (SMP). ^[17]

В Linux 2.4 ^[17] использовался планировщик O (n) с многоуровневой очередью обратной связи с уровнями приоритета от 0 до 140; уровни 0–99 зарезервированы для задач реального времени, а уровни 100–140 считаются хорошими уровнями задач. Для задач реального времени квант времени для переключения процессов составлял приблизительно 200 мс, а для хороших задач — приблизительно 10 мс. ^{[ необходима цитата ]} Планировщик проходил по очереди выполнения всех готовых процессов, позволяя процессам с наивысшим приоритетом идти первыми и проходить свои временные интервалы, после чего они помещались в просроченную очередь. Когда активная очередь пуста, просроченная очередь станет активной очередью и наоборот.

Однако некоторые корпоративные дистрибутивы Linux, такие как SUSE Linux Enterprise Server, заменили этот планировщик на обратную версию планировщика O(1) (который поддерживался Аланом Коксом в его серии Linux 2.4-ac Kernel) для ядра Linux 2.4, используемого в дистрибутиве.

В версиях 2.6.0–2.6.22 ядро ​​использовало планировщик O(1), разработанный Инго Молнаром и многими другими разработчиками ядра во время разработки Linux 2.5. Для многих ядер в то время Кон Коливас разработал наборы патчей, которые улучшили интерактивность с этим планировщиком или даже заменили его своими собственными планировщиками.

Работа Кона Коливаса, наиболее значительная из которых — его реализация справедливого планирования под названием Rotating Staircase Deadline (RSDL), вдохновила Инго Молнара на разработку совершенно справедливого планировщика (CFS) в качестве замены более раннему планировщику O(1) , в объявлении которого он упомянул Коливаса. ^[18] CFS — это первая реализация планировщика справедливого процесса очередизации, широко используемая в операционной системе общего назначения. ^[19]

CFS использует хорошо изученный классический алгоритм планирования, называемый справедливой очередью , изначально придуманный для пакетных сетей . Справедливая очередь ранее применялась к планированию ЦП под названием пошаговое планирование . Планировщик справедливой очереди CFS имеет сложность планирования , где N — количество задач в очереди выполнения . Выбор задачи может быть выполнен за постоянное время, но повторная вставка задачи после ее выполнения требует операций, поскольку очередь выполнения реализована как красно-черное дерево .${\displaystyle O(\log N)}$${\displaystyle O(\log N)}$

Планировщик Brain Fuck Scheduler , также созданный Коном Коливасом, является альтернативой CFS.

В 2023 году Питер Зейлстра предложил заменить CFS на планировщик процессов раннего допустимого виртуального крайнего срока (EEVDF). ^{[20] [21]} Цель состояла в том, чтобы устранить необходимость в исправлениях задержки CFS . ^[22]

FreeBSD использует многоуровневую очередь обратной связи с приоритетами от 0 до 255. 0–63 зарезервированы для прерываний, 64–127 для верхней половины ядра, 128–159 для пользовательских потоков реального времени, 160–223 для пользовательских потоков с разделением времени и 224–255 для бездействующих пользовательских потоков. Также, как и Linux, он использует активную настройку очереди, но также имеет и бездействующую очередь. ^[23]

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 для прерываний с низким приоритетом. В отличие от Linux, ^[23] когда процесс завершается с использованием своего кванта времени, ему присваивается новый приоритет и он возвращается в очередь. Solaris 9 представил два новых класса планирования, а именно класс с фиксированным приоритетом и класс справедливого распределения. Потоки с фиксированным приоритетом имеют тот же диапазон приоритетов, что и класс с разделением времени, но их приоритеты не корректируются динамически. Класс справедливого планирования использует доли ЦП для приоритезации потоков при принятии решений о планировании. Доли ЦП указывают на право на ресурсы ЦП. Они выделяются набору процессов, которые в совокупности называются проектом. ^[7]

• Операционные системы: три простых произведения Ремзи Х. Арпачи-Дюссо и Андреа К. Арпачи-Дюссо. Книги Арпачи-Дюссо, 2014. Соответствующие главы: Планирование: Введение Многоуровневая очередь с обратной связью Планирование с пропорциональным распределением Многопроцессорное планирование
• Краткое обсуждение алгоритмов планирования заданий
• Понимание ядра Linux: Глава 10 Планирование процессов
• Kerneltrap: статьи о планировщике ядра Linux
• Мониторинг и настройка ЦП AIX
• Введение Джоша Ааса в реализацию планировщика ЦП в Linux 2.6.8.1
• Питер Брукер, Сигрид Кнуст. Результаты сложности для задач планирования [2]
• TORSCHE Scheduling Toolbox для Matlab — это набор инструментов для планирования и графических алгоритмов.
• Обзор планирования пакетов сотовых сетей
• Управление крупномасштабным кластером в Google с помощью Borg