Планирование (вычисление) - Scheduling (computing)

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

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

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

Цели

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

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

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

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

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

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

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

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

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

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

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

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

В среднесрочный планировщик временно удаляет процессы из основной памяти и помещает их во вторичную память (например, привод жесткого диска ) или наоборот, что обычно называют "заменой" или "заменой" (также неправильно как "пейджинг out »или« paging in »). Среднесрочный планировщик может решить заменить процесс, который не был активен в течение некоторого времени, или процесс с низким приоритетом, или процесс, который ошибка страницы часто, или процесс, который занимает большой объем памяти, чтобы освободить основную память для других процессов, заменяя процесс обратно позже, когда доступно больше памяти, или когда процесс был разблокирован и больше не ожидает ресурс. [Столлингс, 396] [Столлинг, 370]

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

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

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

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

Диспетчер

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

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

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

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

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

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

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

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

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

Первым прибыл - первым обслужен Эквивалент в русском языке: поздний гость гложет и кость

Основная статья: FIFO (вычисления и электроника)
Образец пул потоков (зеленые квадраты) с очередью (FIFO) ожидающих задач (синие) и очередью выполненных задач (желтые)

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

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

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

Основная статья: Первое планирование на самый ранний срок
Смотрите также: Дедлайн-монотонное планирование

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

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

Основная статья: Наименьшее оставшееся время

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

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

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

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

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

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

Планирование с циклическим перебором

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

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

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

Планирование многоуровневой очереди

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

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

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

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

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

Задачи оптимизации расписания

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

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

Планирование вручную

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

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

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

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

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

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

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

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

OS / 360 и последователи

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

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

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

Windows

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

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

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

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

Mac OS 9 использует совместное планирование для потоков, где один процесс управляет несколькими взаимодействующими потоками, а также обеспечивает упреждающее планирование для многопроцессорных задач. Ядро планирует многопроцессорные задачи, используя алгоритм упреждающего планирования. Все процессы диспетчера процессов выполняются в рамках специальной многопроцессорной задачи, называемой «синей задачей». Эти процессы планируются совместно с использованием циклическое планирование алгоритм; процесс передает управление процессором другому процессу, явно вызывая функция блокировки Такие как WaitNextEvent. У каждого процесса есть собственная копия Менеджер потоков который планирует потоки этого процесса совместно; поток передает управление процессором другому потоку, вызывая YieldToAnyThread или же YieldToThread.[12]

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

AIX

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

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

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

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

Linux

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

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

Работа Кон Коливаса, наиболее значимая его реализация "честный график «Срок действия вращающейся лестницы» вдохновил Инго Мольнара на разработку Полностью честный планировщик в качестве замены более ранней O (1) планировщик, ссылаясь на Коливаса в своем заявлении.[15] CFS - первая реализация честной очереди. планировщик процессов широко используется в операционных системах общего назначения.[16]

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

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

FreeBSD

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

NetBSD

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

Солярис

Солярис использует многоуровневую очередь обратной связи с приоритетами от 0 до 169. Приоритеты 0–59 зарезервированы для потоков с разделением по времени, 60–99 для системных потоков, 100–159 для потоков реального времени и 160–169 для прерываний с низким приоритетом. В отличие от Linux,[17] когда процесс завершается с использованием своего кванта времени, ему дается новый приоритет и он снова помещается в очередь. Solaris 9 представил два новых класса планирования, а именно класс с фиксированным приоритетом и класс справедливого распределения. Потоки с фиксированным приоритетом имеют тот же диапазон приоритетов, что и у класса с разделением времени, но их приоритеты не регулируются динамически. Класс справедливого планирования использует ЦП акции для определения приоритетов потоков при планировании решений. Доли ЦП указывают на доступ к ресурсам ЦП. Они относятся к набору процессов, которые вместе известны как проект.[6]

Резюме

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

Смотрите также

Примечания

  1. ^ К. Л., Лю; Джеймс У., Лейланд (январь 1973 г.). «Алгоритмы планирования для мультипрограммирования в среде жесткого реального времени». Журнал ACM. ACM. 20 (1): 46–61. Дои:10.1145/321738.321743. S2CID  207669821. Мы определяем время ответа на запрос для определенной задачи как промежуток времени между запросом и концом ответа на этот запрос.
  2. ^ Клейнрок, Леонард (1976). Системы массового обслуживания, Vol. 2: Компьютерные приложения (1-е изд.). Wiley-Interscience. п.171. ISBN  047149111X. Для клиента, которому требуется x секунд обслуживания, время его ответа будет равно времени обслуживания x плюс время ожидания.
  3. ^ Фейтельсон, Дрор Г. (2015). Моделирование рабочей нагрузки для оценки производительности компьютерных систем. Издательство Кембриджского университета. Раздел 8.4 (стр. 422) в версии 1.03 свободно доступной рукописи. ISBN  9781107078239. Получено 2015-10-17. если обозначить время ожидания задания в очереди через tш, а время его фактического пробега на tр, то время отклика r = tш + тр.
  4. ^ Зильбершац, Авраам; Галвин, Питер Баер; Гань, Грег (2012). Понятия операционной системы (9-е изд.). Wiley Publishing. п. 187. ISBN  978-0470128725. В интерактивной системе время выполнения работ может быть не лучшим критерием. Часто процесс может производить некоторые выходные данные довольно рано и может продолжать вычислять новые результаты, пока предыдущие результаты выводятся пользователю. Таким образом, другой мерой является время от подачи запроса до получения первого ответа. Этот показатель, называемый временем отклика, - это время, необходимое для начала ответа, а не время, необходимое для вывода ответа.
  5. ^ Пол Кржижановски (2014-02-19). «Планирование процессов: кто будет работать следующим?». cs.rutgers.edu. Получено 2015-01-11.
  6. ^ а б c Авраам Зильбершатц, Питер Баер Галвин и Грег Гань (2013). Понятия операционной системы. 9. John Wiley & Sons, Inc. ISBN  978-1-118-06333-0.CS1 maint: использует параметр авторов (связь)
  7. ^ Гуован Мяо; Йенс Зандер; Ки Вон Сон; Бен Слиман (2016). Основы мобильных сетей передачи данных. Издательство Кембриджского университета. ISBN  978-1107143210.
  8. ^ Ранние окна на Wayback Machine (индекс архива)
  9. ^ Шрирам Кришнан. «Сказка о двух планировщиках Windows NT и Windows CE». Архивировано из оригинал 22 июля 2012 г.
  10. ^ «Администрирование Windows: ядро ​​Windows Vista: часть 1». Technet.microsoft.com. 2016-11-14. Получено 2016-12-09.
  11. ^ [1]
  12. ^ а б «Техническое примечание TN2028: Архитектуры потоков». developer.apple.com. Получено 2019-01-15.
  13. ^ «Планирование Маха и потоковые интерфейсы». developer.apple.com. Получено 2019-01-15.
  14. ^ [2] В архиве 2011-08-11 на Wayback Machine
  15. ^ Мольнар, Инго (2007-04-13). «[patch] Ядро модульного планировщика и полностью справедливый планировщик [CFS]». Linux-ядро (Список рассылки).
  16. ^ Тонг Ли; Дэн Баумбергер; Скотт Хан. «Эффективное и масштабируемое многопроцессорное справедливое планирование с использованием распределенного взвешенного циклического перебора» (PDF). Happyli.org. Получено 2016-12-09.
  17. ^ а б «Сравнение ядер Solaris, Linux и FreeBSD» (PDF). Архивировано из оригинал (PDF) 7 августа 2008 г.

Рекомендации

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