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

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

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

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

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

Цели

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

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

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

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

Типы планировщиков операционной системы

См. также: Планировщик сети , Планирование ввода-вывода и Планировщик заданий.

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

Планировщик процессов

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

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

Долгосрочное планирование

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

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

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

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

Среднесрочное планирование

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

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

Краткосрочное планирование

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

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

Диспетчер

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

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

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

Дисциплины планирования

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

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

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

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

В усовершенствованных беспроводных сетях пакетной радиосвязи, таких как HSDPA (высокоскоростной нисходящий пакетный доступ) 3.5G сотовая система , каналозависимое планирование может использоваться для использования информации о состоянии канала . Если условия канала благоприятны, пропускная способность и спектральная эффективность системы могут быть увеличены. В еще более продвинутых системах, таких как LTE , планирование комбинируется с помощью каналозависимого попакетного динамического распределения каналов или путем назначения OFDMA нескольких несущих или других компонентов выравнивания частотной области пользователям, которые лучше всего могут их использовать.

Первый пришел, первый обслужен

Основная статья: FIFO (вычисления и электроника)

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

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

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

Приоритетное планирование

Основная статья: Первое планирование самого раннего срока

См. Также: Монотонное планирование сроков.

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

Сначала самое короткое оставшееся время

Основная статья: Кратчайшее оставшееся время

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

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

Упреждающее планирование с фиксированным приоритетом

Основная статья: Упреждающее планирование с фиксированным приоритетом

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

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

Круговое планирование

Основная статья: Циклическое планирование

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

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

Многоуровневое планирование очередей

Основная статья: Многоуровневая очередь

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

Планировщики, экономящие работу

Основная статья: Планировщик, сохраняющий работу

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

оптимизации

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

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

Ручное планирование

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

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

Выбор алгоритма планирования

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

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

планировщика процессов

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

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

OS/360 и его преемники

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

• Опция единого последовательного планировщика , также известная как программа первичного управления (PCP), обеспечивала последовательное выполнение одного потока заданий.
• Опция множественного последовательного планировщика , известная как мультипрограммирование с фиксированным числом задач (MFT), обеспечивала выполнение нескольких одновременных заданий. Выполнение определялось приоритетом, который имел значение по умолчанию для каждого потока или мог запрашиваться отдельно для каждого задания. В MFT версии II добавлены подзадачи (потоки), которые выполняются с приоритетом, основанным на приоритете родительского задания. Каждый поток заданий определял максимальный объем памяти, который мог использоваться любым заданием в этом потоке.
• Опция «Множественные планировщики приоритетов» , или «Мультипрограммирование с переменным количеством задач» (MVT) , с самого начала включала подзадачи; каждое задание запрашивало приоритет и необходимую ему память перед выполнением.

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

Окна

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

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

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

Классическая Mac OS и macOS

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

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

AIX

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

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

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

В AIX 5 реализованы следующие политики планирования: FIFO, циклический перебор и справедливый циклический перебор. Политика FIFO имеет три различные реализации: FIFO, FIFO2 и FIFO3. В AIX политика циклического перебора называется SCHED_RR, а политика справедливого циклического перебора — SCHED_OTHER.

Линукс

Линукс 1.2

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

Линукс 2.2

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

Сильно упрощенная структура ядра Linux, включающая планировщики процессов, планировщики ввода-вывода и планировщики пакетов.

Линукс 2.4

В Linux 2.4 использовался планировщик 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, используемое дистрибутивом. .

Linux 2.6.0 — Linux 2.6.22

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

Linux 2.6.23 — Linux 6.5

Работа Кона Коливаса, в первую очередь его реализация справедливого планирования под названием « Крайний срок вращающейся лестницы» (RSDL), вдохновила Инго Молнара на разработку Полностью справедливого планировщика (CFS) в качестве замены более раннего планировщика O (1) , отдав должное Коливасу в его объявлении. CFS — это первая реализация планировщика процессов справедливой организации очереди , широко используемая в операционных системах общего назначения.

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

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

Линукс 6.6

В 2023 году Питер Зийлстра предложил заменить CFS самым ранним подходящим планировщиком процессов с виртуальным дедлайном (EEVDF). Целью было устранить необходимость в исправлениях задержки CFS .

FreeBSD

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

NetBSD

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

Резюме

Операционная система	Упреждение	Алгоритм
Амига ОС	Да	Приоритетное циклическое планирование
FreeBSD	Да	Многоуровневая очередь обратной связи
Ядро Linux до версии 2.6.0	Да	Многоуровневая очередь обратной связи
Ядро Linux 2.6.0–2.6.23	Да	планировщик O(1)
Ядро Linux после 2.6.23	Да	Полностью честный планировщик
Ядро Linux 6.6 и новее	Да	Первое планирование виртуального крайнего срока на ближайшее время (EEDFF)
классическая Mac OS до 9	Никто	Кооперативный планировщик
Мак ОС 9	Некоторый	Вытесняющий планировщик для задач MP и совместная работа процессов и потоков.
macOS	Да	Многоуровневая очередь обратной связи
NetBSD	Да	Многоуровневая очередь обратной связи
Солярис	Да	Многоуровневая очередь обратной связи
Windows 3.1x	Никто	Кооперативный планировщик
Windows 95 , 98 , Я	Половина	Вытесняющий планировщик для 32-битных процессов и кооперативный для 16-битных процессов.
Windows NT (включая 2000, XP, Vista, 7 и Server)	Да	Многоуровневая очередь обратной связи

См. также

• Проблема выбора вида деятельности
• Старение (планирование)
• Автоматизированное планирование и составление графиков
• Циклический руководитель
• Динамическое планирование приоритетов
• Передний план-фон
• Прерываемая операционная система
• Наименьший резерв времени
• Расписание лотереи
• Инверсия приоритета
• Состояния процесса
• Теория массового обслуживания
• Монотонное планирование
• Планирование (производственные процессы)
• Стохастическое планирование
• Функция полезности времени

Ссылки

• Блажевич, Яцек; Экер, К.Х.; Пеш, Э.; Шмидт, Г.; Вегларц, Дж. (2001). Компьютерное планирование и производственные процессы (2-е изд.). Берлин [ua]: Шпрингер. ISBN  3-540-41931-4 .
• Столлингс, Уильям (2004). Внутреннее устройство операционных систем и принципы проектирования (четвертое изд.). Прентис Холл. ISBN  0-13-031999-6 .
• Информация об O(1)-планировщике Linux 2.6

Дальнейшее чтение

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