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

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

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

Цели [ править ]

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

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

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

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

Планировщик процессов [ править ]

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

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

Долгосрочное планирование [ править ]

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

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

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

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

Среднесрочное планирование [ править ]

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

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

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

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

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

Диспетчер [ править ]

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

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

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

Планирование дисциплин [ править ]

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

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

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

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

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

Первым пришел, первым обслужен [ править ]

Первый пришел - первым вышел ( 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 была доступна с тремя разными планировщиками. Различия были таковы, что часто рассматривались варианты трех разных операционных систем:

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

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

Windows [ править ]

Очень ранние системы 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 и macOS [ править ]

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

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

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. ^[16]

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) на ядро ​​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) , указав Коливаса в его объявлении. ^[17] CFS - первая реализация планировщика процессов справедливой организации очередей, широко используемого в операционных системах общего назначения. ^[18]

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

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

FreeBSD [ править ]

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

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

Резюме [ править ]

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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