Войти
В вычислениях планирование - это метод, с помощью которого работа назначается ресурсы, завершающие работу. Работа может представлять собой элементы виртуальных вычислений, такие как потоки, процессы или потоки данных, которые, в свою очередь, запланированы на аппаратные ресурсы, такие как процессоры, сетевые ссылки или карты расширения.
Планировщик - это то, что выполняет действия по планированию. Планировщики часто реализуются таким образом, что они загружают все ресурсы компьютера (как в балансировке нагрузки ), позволяют нескольким пользователям эффективно совместно использовать системные ресурсы или для достижения целевого качества обслуживания. Планирование является фундаментальным для самих вычислений и неотъемлемой частью модели выполнения компьютерной системы; концепция планирования позволяет иметь многозадачность компьютера с помощью одного центрального процессора (ЦП).
Расписание er может преследовать одну или несколько целей, например: максимизация пропускной способности (общего объема работы, выполненной за единицу времени); минимизация времени ожидания (время от подготовки работы до первой точки ее начала выполнения); минимизация задержки или времени отклика (время от подготовки работы до ее завершения в случае пакетной активности или до тех пор, пока система не ответит и не передаст первый результат пользователю в случае интерактивного деятельность); или максимизация справедливости (равное время ЦП для каждого процесса или, в более общем случае, подходящее время в соответствии с приоритетом и рабочей нагрузкой каждого процесса). На практике эти цели часто противоречат друг другу (например, пропускная способность против задержки), поэтому планировщик найдет подходящий компромисс. Предпочтение измеряется любой из проблем, упомянутых выше, в зависимости от потребностей и целей пользователя.
В средах реального времени, таких как встроенные системы для автоматического управления в промышленности (например, робототехника ), планировщик также должен гарантировать, что процессы могут соответствовать крайним срокам ; это очень важно для поддержания стабильности системы. Запланированные задачи также могут быть распределены на удаленные устройства по сети и управляться через административный сервер.
Планировщик - это модуль операционной системы, который выбирает следующие задания, которые будут допущены в систему, и следующий процесс для запуска. Операционные системы могут иметь до трех различных типов планировщиков: долгосрочный планировщик (также известный как планировщик допуска или высокоуровневый планировщик), среднесрочный или среднесрочный планировщик и краткосрочный планировщик. Названия указывают на относительную частоту, с которой выполняются их функции.
Планировщик процессов - это часть операционной системы, которая определяет, какой процесс запускается в определенный момент времени. Обычно у него есть возможность приостановить запущенный процесс, переместить его в конец очереди выполнения и запустить новый процесс; такой планировщик известен как упреждающий планировщик, в противном случае это кооперативный планировщик.
Долгосрочное планирование, или планировщик допуска, решает, какие задания или процессы должны быть допущены в очередь готовности (в основной памяти); то есть, когда делается попытка выполнить программу, ее допуск к набору выполняющихся в данный момент процессов либо санкционируется, либо задерживается долгосрочным планировщиком. Таким образом, этот планировщик определяет, какие процессы должны выполняться в системе, и степень параллелизма, которая должна поддерживаться в любой момент времени - должны ли выполняться одновременно много или несколько процессов и как разделение между интенсивным вводом-выводом и ЦП -интенсивные процессы должны быть обработаны. Долгосрочный планировщик отвечает за управление степенью мультипрограммирования.
В общем, большинство процессов можно описать как с привязкой к вводу-выводу или с привязкой к ЦП. Процесс, связанный с вводом-выводом, - это процесс, который тратит больше времени на ввод-вывод, чем на вычисления. Процесс, связанный с процессором, напротив, нечасто генерирует запросы ввода-вывода, тратя больше времени на вычисления. Важно, чтобы долгосрочный планировщик выбирал хорошее сочетание процессов, связанных с вводом / выводом и процессами. Если все процессы связаны с вводом-выводом, очередь готовности почти всегда будет пустой, и краткосрочный планировщик будет мало что делать. С другой стороны, если все процессы привязаны к ЦП, очередь ожидания ввода-вывода почти всегда будет пустой, устройства останутся неиспользованными, и снова система будет несбалансированной. Таким образом, система с наилучшей производительностью будет иметь комбинацию процессов, связанных с процессором и вводом-выводом. В современных операционных системах это используется, чтобы гарантировать, что процессы реального времени получают достаточно процессорного времени для выполнения своих задач.
Долгосрочное планирование также важно в крупномасштабных системах, таких как пакетная обработка системы, компьютерные кластеры, суперкомпьютеры и фермы рендеринга. Например, в параллельных системах, совместное планирование взаимодействующих процессов часто требуется для предотвращения их блокировки из-за ожидания друг друга. В этих случаях программное обеспечение специального назначения планировщик заданий обычно используется для поддержки этих функций в дополнение к любой базовой поддержке планирования допуска в операционной системе.
Среднесрочный планировщик временно удаляет процессы из основной памяти и помещает их во вторичную память (например, жесткий диск ) или наоборот., что обычно называется «заменой» или «заменой» (также неправильно как «пейджинг вне» или «пейджинг в»). Среднесрочный планировщик может принять решение заменить процесс, который не был активен в течение некоторого времени, или процесс с низким приоритетом, или процесс, который часто вызывает сбой страницы, или процесс, который занимая большой объем памяти, чтобы освободить основную память для других процессов, переставляя процесс обратно позже, когда доступно больше памяти, или когда процесс был разблокирован и больше не ожидает ресурса. [Stallings, 396] [Stallings, 370]
Сегодня во многих системах (тех, которые поддерживают сопоставление виртуального адресного пространства с вторичным хранилищем, отличным от файла подкачки) среднесрочный планировщик может фактически выполнять роль долгосрочный планировщик, обрабатывающий двоичные файлы как «выгруженные процессы» после их выполнения. Таким образом, когда требуется сегмент двоичного файла, он может быть заменен по запросу или «ленивой загрузкой». [Stallings, 394]
Краткосрочный планировщик (также известный как планировщик ЦП) решает, какой из готовых процессов в памяти должен быть выполнен (выделен CPU) после тактового сигнала прерывания, прерывания ввода-вывода, рабочего системного вызова или другой формы сигнала . Таким образом, краткосрочный планировщик принимает решения о планировании гораздо чаще, чем долгосрочный или среднесрочный планировщики - решение о планировании должно как минимум приниматься после каждого временного интервала, а они очень короткие. Этот планировщик может быть вытесняющим, подразумевая, что он способен принудительно удалять процессы из ЦП, когда он решает выделить этот ЦП другому процессу, или без вытеснения (также известный как «добровольно» или «совместно». оперативный "), и в этом случае планировщик не может" принудительно "вывести процессы из ЦП.
Планировщик с вытеснением полагается на программируемый интервальный таймер, который вызывает обработчик прерывания, который работает в режиме ядра и реализует функцию планирования.
Еще одним компонентом, который участвует в функции планирования ЦП, является диспетчер, который представляет собой модуль, который передает управление ЦП процессу, выбранному краткосрочным планировщиком. Он получает управление в режиме ядра в результате прерывания или системного вызова. Функции диспетчера включают следующее:
Диспетчер должен работать как можно быстрее, поскольку он вызывается при каждом переключении процесса. Во время переключения контекста процессор фактически бездействует некоторое время, поэтому следует избегать ненужных переключений контекста. Время, которое требуется диспетчеру для остановки одного процесса и запуска другого, называется задержкой отправки.
Дисциплины планирования - это алгоритмы, используемые для распределения ресурсов между сторонами, которые одновременно и асинхронно запрашивают их. Дисциплины планирования используются в маршрутизаторах (для обработки пакетного трафика), а также в операционных системах (для распределения процессорного времени между обоими потоками и процессы ), дисководы (планирование ввода-вывода ), принтеры (диспетчер очереди печати ), большинство встроенных систем и т. д.
Основными целями алгоритмов планирования являются минимизация нехватки ресурсов и обеспечение справедливости между сторонами, использующими ресурсы. Планирование решает проблему определения того, какому из невыполненных запросов следует выделить ресурсы. Есть много разных алгоритмов планирования. В этом разделе мы познакомим вас с некоторыми из них.
В пакетно-коммутируемых компьютерных сетях и других статистическом мультиплексировании понятие алгоритма планирования используется как альтернатива организации очереди пакетов данных в порядке очереди.
Самыми простыми алгоритмами планирования с максимальными усилиями являются циклический перебор, справедливая организация очереди (алгоритм планирования max-min fair ), пропорционально справедливое планирование и максимальная пропускная способность. Если предлагается дифференцированное или гарантированное качество обслуживания, в отличие от обмена данными с максимальными усилиями, может использоваться взвешенная справедливая организация очереди.
В усовершенствованных беспроводных сетях пакетной радиосвязи, таких как HSDPA (высокоскоростной пакетный доступ по нисходящей линии связи) 3.5G сотовая система, планирование в зависимости от канала может использоваться, чтобы воспользоваться информацией о состоянии канала . Если условия канала являются благоприятными, пропускная способность и спектральная эффективность системы могут быть увеличены. В даже более продвинутых системах, таких как LTE, планирование комбинируется с помощью зависящего от канала посыльного динамического распределения каналов или путем назначения OFDMA мульти- несущие или другие компоненты выравнивания частотной области пользователям, которые могут их лучше всего использовать.
Образец пула потоков (зеленые прямоугольники) с очередью (FIFO) ожидающих задач (синий) и очередью завершенных задач (желтый) Первый пришел - первый ушел (FIFO ), также известный как первый пришел - первым обслужен (FCFS), является простейшим алгоритмом планирования. FIFO просто ставит процессы в очередь в том порядке, в котором они поступают в очередь готовности. Обычно это используется для очереди задач, например, как показано в этом разделе.
Самый ранний крайний срок (EDF) или наименьшее время до завершения алгоритм динамического планирования, используемый в операционных системах реального времени для помещения процессов в приоритетную очередь. Каждый раз, когда происходит событие планирования (завершение задачи, выпуск новой задачи и т. Д.), В очереди будет производиться поиск процесса, ближайшего к ее крайнему сроку, который будет следующим по расписанию для выполнения.
Аналогично самое короткое задание сначала (SJF). С помощью этой стратегии планировщик упорядочивает процессы с наименьшим расчетным временем обработки, остающимся следующими в очереди. Это требует углубленных знаний или оценок времени, необходимого для завершения процесса.
Операционная система назначает фиксированный ранг приоритета каждому процессу, а планировщик выстраивает процессы в очереди готовности в порядке их приоритета. Процессы с более низким приоритетом прерываются входящими процессами с более высоким приоритетом.
Планировщик назначает фиксированную единицу времени для каждого процесса и циклически перебирает их. Если процесс завершается в течение этого временного интервала, он завершается, в противном случае он переносится в расписание после предоставления возможности всем другим процессам.
Используется для ситуаций, в которых процессы легко разделить на разные группы. Например, общее разделение делается на передние (интерактивные) процессы и фоновые (пакетные) процессы. Эти два типа процессов имеют разные требования к времени отклика и, следовательно, могут иметь разные потребности в планировании. Это очень полезно при проблемах разделяемой памяти.
A Планировщик с сохранением работы - это планировщик, который всегда пытается поддерживать занятость запланированных ресурсов, если есть отправленные задания, готовые к планированию. Напротив, планировщик, не сохраняющий работу, - это планировщик, который в некоторых случаях может оставлять запланированные ресурсы свободными, несмотря на наличие заданий, готовых к планированию.
Существует несколько задач планирования, цель которых состоит в том, чтобы решить, какое задание отправляется на какую станцию и в какое время, так чтобы общее время выполнения было минимальным :
Очень распространенный метод во встроенных системах - это планирование заданий вручную. Это может быть сделано, например, с временным мультиплексированием. Иногда ядро делится на три или более частей: ручное планирование, вытеснение и уровень прерывания. Точные методы планирования заданий часто являются собственностью.
При разработке операционной системы программист должен подумать, какой алгоритм планирования будет работать лучше всего для того, что система собирается увидеть. Не существует универсального «лучшего» алгоритма планирования, и многие операционные системы используют расширенные или комбинации описанных выше алгоритмов планирования.
Например, Windows NT / XP / Vista использует многоуровневую очередь обратной связи, комбинацию упреждающего планирования с фиксированным приоритетом, циклического перебора и первого входа, первоочередные алгоритмы. В этой системе потоки могут динамически увеличивать или уменьшать приоритет в зависимости от того, был ли он уже обслужен или долго ждал. Каждый уровень приоритета представлен своей собственной очередью с циклическим планированием среди потоков с высоким приоритетом и FIFO среди потоков с более низким приоритетом. В этом смысле время отклика для большинства потоков невелико, а короткие, но важные системные потоки завершаются очень быстро. Поскольку потоки могут использовать только одну единицу времени циклического перебора в очереди с наивысшим приоритетом, голодание может стать проблемой для более длинных потоков с высоким приоритетом.
Используемый алгоритм может быть таким простым, как циклический перебор, в котором каждому процессу дается одинаковое время (например, 1 мс, обычно между 1 мс и 100 мс) в списке циклов. Итак, процесс A выполняется в течение 1 мс, затем процесс B, затем процесс C, затем снова процесс A.
Более продвинутые алгоритмы учитывают приоритет процесса или важность процесса. Это позволяет некоторым процессам использовать больше времени, чем другим. Ядро всегда использует все ресурсы, необходимые для обеспечения правильного функционирования системы, и поэтому можно сказать, что оно имеет бесконечный приоритет. В системах SMP считается, что сходство процессора увеличивает общую производительность системы, даже если это может привести к более медленной работе самого процесса. Обычно это повышает производительность за счет уменьшения перегрузки кеша.
IBM OS / 360 были доступны с тремя разными планировщиками. Различия заключались в том, что варианты часто рассматривались как три разные операционные системы:
Более поздние версии виртуального хранилища 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 9 использует совместное планирование для потоков, где один процесс управляет несколькими взаимодействующими потоками, а также обеспечивает упреждающее планирование для многопроцессорных задач. Ядро планирует многопроцессорные задачи, используя алгоритм упреждающего планирования. Все процессы диспетчера процессов выполняются в рамках специальной многопроцессорной задачи, называемой «синей задачей». Эти процессы планируются совместно с использованием алгоритма циклического планирования ; процесс передает управление процессором другому процессу, явно вызывая такое, как WaitNextEvent. Каждый процесс имеет свою собственную копию, которая совместно планирует потоки этого процесса; поток передает управление процессором другому потоку, вызывая YieldToAnyThreadили YieldToThread.
. macOS использует многоуровневую очередь обратной связи с четырьмя диапазонами приоритета для потоков - нормальный, системный высокий приоритет, только режим ядра, и в реальном времени. Потоки планируются заранее; macOS также поддерживает совместно запланированные потоки в своей реализации Thread Manager в Carbon.
В AIX версии 4 есть три возможных значения для политики планирования потоков:
Потоки в первую очередь представляют интерес для приложений, которые в настоящее время состоят из нескольких асинхронных процессов. Эти приложения могут снизить нагрузку на систему, если преобразовать их в многопоточную структуру.
В AIX 5 реализованы следующие политики планирования: FIFO, циклический и справедливый циклический. Политика FIFO имеет три различных реализации: FIFO, FIFO2 и FIFO3. Политика циклического перебора называется SCHED_RR в AIX, а справедливая циклическая переборка называется SCHED_OTHER.
Сильно упрощенная структура ядра Linux, которая включает в себя планировщики процессов, планировщики ввода-вывода и планировщики пакетов В 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, используемого в дистрибутиве.
В версиях с 2.6.0 по 2.6.22 ядро использовало планировщик O (1), разработанный Инго Молнар и многие другие разработчики ядра во время разработки Linux 2.5. Для многих ядер во временных рамках Кон Коливас разработал наборы исправлений, которые улучшили взаимодействие с этим планировщиком или даже заменили его его собственными планировщиками.
Работа Кон Коливаса, наиболее значимая его реализация «справедливого планирования » под названием «Крайний срок вращающейся лестницы» вдохновила Инго Мольнара на разработку Полностью справедливый планировщик в качестве замены более раннего O (1) планировщика, как указано в заявлении Коливаса. CFS - первая реализация планировщика процессов со справедливой очередью, широко используемого в операционных системах общего назначения.
Completely Fair Scheduler (CFS) использует хорошо- изучен классический алгоритм планирования, называемый справедливой очередью, первоначально изобретенный для пакетных сетей. Справедливая организация очередей ранее применялась к планированию ЦП под именем планирование шага. Планировщик CFS справедливой организации очередей имеет сложность планирования O (журнал N), где N - количество задач в очереди выполнения. Выбор задачи может быть выполнен за постоянное время, но для повторной вставки задачи после ее выполнения требуется O (log N) операций, потому что очередь выполнения реализована как красно-черное дерево.
Brain Fuck Scheduler (BFS), также созданный Кон Коливасом, является альтернативой CFS.
FreeBSD использует многоуровневую очередь обратной связи с приоритетами от 0 до 255. 0–63 зарезервированы для прерываний, 64–127 для верхней половины ядра, 128–159 для пользовательских потоков в реальном времени, 160–223 для пользовательских потоков с разделением времени и 224–255 для простаивающих пользовательских потоков. Также, как и в Linux, он использует активную настройку очереди, но также имеет очередь ожидания.
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, когда процесс выполняется с использованием своего кванта времени, ему дается новый приоритет и он снова помещается в очередь. Solaris 9 представил два новых класса планирования, а именно класс с фиксированным приоритетом и класс справедливого распределения. The threads with fixed priority have the same priority range as that of the time-sharing class, but their priorities are not dynamically adjusted. The fair scheduling class uses CPU shares to prioritize threads for scheduling decisions. CPU shares indicate the entitlement to CPU resources. They are allocated to a set of processes, which are collectively known as a project.
| Operating System | Preemption | Algorithm |
|---|---|---|
| Amiga OS | Yes | Prioritized round-robin scheduling |
| FreeBSD | Yes | Multilevel feedback queue |
| Linux kernel before 2.6.0 | Yes | Multilevel feedback queue |
| Linux kernel 2.6.0–2.6.23 | Yes | O(1) scheduler |
| Linux kernel after 2.6.23 | Yes | Completely Fair Scheduler |
| classic Mac OS pre-9 | None | Cooperative scheduler |
| Mac OS 9 | Some | Preemptive scheduler for MP tasks, and cooperative for processes and threads |
| macOS | Yes | Multilevel feedback queue |
| NetBSD | Yes | Multilevel feedback queue |
| Solaris | Yes | Multilevel feedback queue |
| Windows 3.1x | None | Cooperative scheduler |
| Windows 95, 98, Me | Half | Preemptive scheduler for 32-bit processes, and cooperative for 16-bit processe s |
| Windows NT (including 2000, XP, Vista, 7, and Server) | Yes | Multilevel feedback queue |
