В вычислительной технике планирование — это действие по назначению ресурсов для выполнения задач . Ресурсами могут быть процессоры , сетевые соединения или карты расширения . Задачи могут быть потоками , процессами или потоками данных .
Планирование осуществляется процессом, называемым планировщиком . Планировщики часто разрабатываются таким образом, чтобы поддерживать занятость всех ресурсов компьютера (как при балансировке нагрузки ), позволять нескольким пользователям эффективно совместно использовать системные ресурсы или достигать целевого качества обслуживания .
Планирование имеет основополагающее значение для вычислений как таковых и является неотъемлемой частью модели выполнения компьютерной системы; концепция планирования позволяет реализовать многозадачность компьютера с помощью одного центрального процессора (ЦП).
Планировщик может ставить перед собой одну или несколько целей, например:
На практике эти цели часто конфликтуют (например, пропускная способность против задержки), поэтому планировщик реализует подходящий компромисс. Предпочтение измеряется любым из упомянутых выше факторов в зависимости от потребностей и целей пользователя.
В средах реального времени , таких как встроенные системы для автоматического управления в промышленности (например, робототехника ), планировщик также должен гарантировать, что процессы могут соответствовать срокам ; это имеет решающее значение для поддержания стабильности системы. Запланированные задачи также могут быть распределены на удаленные устройства по сети и управляться через административный бэкэнд.
Планировщик — это модуль операционной системы, который выбирает следующие задания для допуска в систему и следующий процесс для запуска. Операционные системы могут иметь до трех различных типов планировщиков: долгосрочный планировщик (также известный как планировщик допуска или высокоуровневый планировщик), среднесрочный или среднесрочный планировщик и краткосрочный планировщик . Названия указывают на относительную частоту, с которой выполняются их функции.
Планировщик процессов — это часть операционной системы, которая решает, какой процесс запустится в определенный момент времени. Обычно он имеет возможность приостанавливать запущенный процесс, перемещать его в конец очереди и запускать новый процесс; такой планировщик называется вытесняющим планировщиком , в противном случае это кооперативный планировщик . [5]
Мы различаем долгосрочное планирование , среднесрочное планирование и краткосрочное планирование в зависимости от того, как часто должны приниматься решения. [6]
Долгосрочный планировщик , или планировщик допуска , решает, какие задания или процессы должны быть допущены в очередь готовности (в основной памяти); то есть, когда делается попытка выполнить программу, ее допуск в набор текущих выполняемых процессов либо разрешается, либо задерживается долгосрочным планировщиком. Таким образом, этот планировщик определяет, какие процессы должны выполняться в системе, степень параллелизма, которая должна поддерживаться в любой момент времени — много или мало процессов должны выполняться одновременно, и как должно обрабатываться разделение между процессами, интенсивно использующими ввод-вывод, и процессами, интенсивно использующими процессор. Долгосрочный планировщик отвечает за управление степенью многопрограммирования.
В общем, большинство процессов можно описать как процессы, связанные с вводом-выводом или с процессором . Процесс, связанный с вводом-выводом, — это процесс, который тратит больше времени на ввод-вывод, чем на вычисления. Процесс, связанный с процессором, напротив, генерирует запросы ввода-вывода нечасто, используя большую часть времени для вычислений. Важно, чтобы долгосрочный планировщик выбирал хорошее сочетание процессов, связанных с вводом-выводом и связанных с процессором. Если все процессы связаны с вводом-выводом, очередь готовности почти всегда будет пустой, а краткосрочному планировщику будет нечего делать. С другой стороны, если все процессы связаны с процессором, очередь ожидания ввода-вывода почти всегда будет пустой, устройства останутся неиспользованными, и снова система будет несбалансированной. Таким образом, система с наилучшей производительностью будет иметь комбинацию процессов, связанных с процессором и связанных с вводом-выводом. В современных операционных системах это используется для того, чтобы гарантировать, что процессы реального времени получат достаточно процессорного времени для завершения своих задач. [7]
Долгосрочное планирование также важно в крупномасштабных системах, таких как системы пакетной обработки , компьютерные кластеры , суперкомпьютеры и фермы рендеринга . Например, в параллельных системах часто требуется совместное планирование взаимодействующих процессов, чтобы предотвратить их блокировку из-за ожидания друг друга. В этих случаях для поддержки этих функций обычно используется специализированное программное обеспечение планировщика заданий в дополнение к любой базовой поддержке планирования допуска в операционной системе.
Некоторые операционные системы разрешают добавлять новые задачи только в том случае, если они уверены, что все сроки в реальном времени все еще могут быть соблюдены. Конкретный эвристический алгоритм, используемый операционной системой для принятия или отклонения новых задач, — это механизм контроля допуска . [8]
Среднесрочный планировщик временно удаляет процессы из основной памяти и помещает их во вторичную память (например, жесткий диск ) или наоборот, что обычно называется подкачкой или закачкой (также неправильно называется подкачкой или закачкой ) . Среднесрочный планировщик может решить подгрузить процесс, который не был активен в течение некоторого времени, процесс с низким приоритетом, процесс, который часто вызывает сбои страниц , или процесс, который занимает большой объем памяти, чтобы освободить основную память для других процессов, подкачивая процесс обратно позже, когда будет доступно больше памяти, или когда процесс был разблокирован и больше не ждет ресурса.
Во многих современных системах (поддерживающих отображение виртуального адресного пространства на вторичное хранилище, отличное от файла подкачки) среднесрочный планировщик может фактически выполнять роль долгосрочного планировщика, рассматривая двоичные файлы как выгруженные процессы при их выполнении. Таким образом, когда требуется сегмент двоичного файла, он может быть выгружен по требованию или загружен лениво , что также называется подкачкой по требованию .
Краткосрочный планировщик (также известный как планировщик ЦП ) решает, какой из готовых процессов в памяти должен быть выполнен (выделен ЦП) после прерывания часов , прерывания ввода-вывода, вызова операционной системы или другой формы сигнала . Таким образом, краткосрочный планировщик принимает решения о планировании гораздо чаще, чем долгосрочные или среднесрочные планировщики — решение о планировании должно быть принято как минимум после каждого временного среза, а они очень короткие. Этот планировщик может быть упреждающим , подразумевая, что он способен принудительно удалять процессы из ЦП, когда он решает выделить этот ЦП другому процессу, или не упреждающим (также известным как добровольный или кооперативный ), в этом случае планировщик не может принудительно удалять процессы из ЦП.
Планировщик с вытеснением использует программируемый интервальный таймер , который вызывает обработчик прерываний , работающий в режиме ядра и реализующий функцию планирования.
Другим компонентом, участвующим в функции планирования ЦП, является диспетчер, представляющий собой модуль, который передает управление ЦП процессу, выбранному краткосрочным планировщиком. Он получает управление в режиме ядра в результате прерывания или системного вызова. Функции диспетчера включают в себя следующее:
Диспетчер должен быть максимально быстрым, поскольку он вызывается во время каждого переключения процесса. Во время переключений контекста процессор фактически простаивает в течение части времени, поэтому следует избегать ненужных переключений контекста. Время, необходимое диспетчеру для остановки одного процесса и запуска другого, называется задержкой диспетчеризации . [ 7] : 155
Дисциплина планирования (также называемая политикой планирования или алгоритмом планирования ) — это алгоритм, используемый для распределения ресурсов между сторонами, которые одновременно и асинхронно запрашивают их. Дисциплины планирования используются в маршрутизаторах (для обработки трафика пакетов), а также в операционных системах (для распределения времени ЦП между потоками и процессами ), дисководах ( планирование ввода-вывода ), принтерах ( спулер печати ), большинстве встроенных систем и т. д.
Главные цели алгоритмов планирования — минимизировать нехватку ресурсов и обеспечить справедливость между сторонами, использующими ресурсы. Планирование решает проблему принятия решения о том, какие из невыполненных запросов должны быть распределены ресурсами. Существует много различных алгоритмов планирования. В этом разделе мы представляем несколько из них.
В компьютерных сетях с коммутацией пакетов и других статистических мультиплексорах понятие алгоритма планирования используется как альтернатива организации очередей пакетов данных по принципу « первым пришел — первым обслужен» .
Простейшими алгоритмами планирования с наилучшими усилиями являются циклический перебор , справедливая организация очередей ( алгоритм справедливого планирования с максимальным и минимальным значениями ), пропорционально-справедливое планирование и максимальная пропускная способность . Если предлагается дифференцированное или гарантированное качество обслуживания , в отличие от связи с наилучшими усилиями, может использоваться взвешенная справедливая организация очередей .
В современных пакетных беспроводных сетях радиосвязи, таких как сотовая система HSDPA (High-Speed Downlink Packet Access) 3.5G , планирование, зависящее от канала, может использоваться для использования информации о состоянии канала . Если условия канала благоприятны, пропускная способность и спектральная эффективность системы могут быть увеличены. В еще более современных системах, таких как LTE , планирование сочетается с динамическим распределением каналов , зависящим от канала, пакет за пакетом , или путем назначения многонесущих OFDMA или других компонентов выравнивания в частотной области пользователям, которые могут использовать их наилучшим образом. [9]
First in, first out ( FIFO ), также известный как first come, first serve (FCFS), является простейшим алгоритмом планирования. FIFO просто ставит процессы в очередь в том порядке, в котором они поступают в очередь готовности. Это обычно используется дляочередь задач , например, как показано в этом разделе.
Earlyest deadline first (EDF) или least time to go — это динамический алгоритм планирования, используемый в операционных системах реального времени для помещения процессов в приоритетную очередь. Всякий раз, когда происходит событие планирования (завершение задачи, выпуск новой задачи и т. д.), в очереди будет выполнен поиск процесса, ближайшего к его крайнему сроку, который будет следующим запланированным для выполнения.
Аналогично стратегии shortest job first (SJF). С помощью этой стратегии планировщик размещает процессы с наименьшим предполагаемым временем обработки следующими в очереди. Это требует расширенных знаний или оценок о времени, необходимом для завершения процесса.
Операционная система назначает каждому процессу фиксированный приоритетный ранг, а планировщик упорядочивает процессы в очереди готовности в порядке их приоритета. Процессы с более низким приоритетом прерываются входящими процессами с более высоким приоритетом.
Планировщик назначает фиксированную единицу времени на процесс и циклически проходит по ним. Если процесс завершается в течение этого временного отрезка, он завершается, в противном случае он перепланируется, дав шанс всем остальным процессам.
Это используется в ситуациях, когда процессы легко разделить на разные группы. Например, обычное разделение делается между передними (интерактивными) процессами и фоновыми (пакетными) процессами. Эти два типа процессов имеют разные требования к времени отклика и, следовательно, могут иметь разные потребности в планировании. Это очень полезно для проблем с общей памятью .
Планировщик , сохраняющий работу, — это планировщик, который всегда пытается держать запланированные ресурсы занятыми, если есть отправленные задания, готовые к планированию. Напротив, планировщик, не сохраняющий работу, — это планировщик, который в некоторых случаях может оставлять запланированные ресурсы бездействующими, несмотря на наличие заданий, готовых к планированию.
Существует несколько задач планирования, в которых цель состоит в том, чтобы решить, какое задание должно быть отправлено на какую станцию и в какое время, чтобы общее время выполнения было минимальным:
Очень распространенным методом во встроенных системах является планирование заданий вручную. Это может быть сделано, например, в режиме временного мультиплексирования. Иногда ядро делится на три или более частей: ручное планирование, упреждающее и прерывающее. Точные методы планирования заданий часто являются фирменными.
При проектировании операционной системы программист должен учитывать, какой алгоритм планирования будет работать лучше всего для использования, которое собирается увидеть система. Универсального лучшего алгоритма планирования не существует , и многие операционные системы используют расширенные или комбинации алгоритмов планирования, указанных выше.
Например, 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-битным приложениям работать без вытеснения. [10]
Операционные системы на базе Windows NT используют многоуровневую очередь обратной связи. Определено 32 уровня приоритета, от 0 до 31, при этом приоритеты от 0 до 15 являются обычными приоритетами, а приоритеты от 16 до 31 являются мягкими приоритетами реального времени, требующими привилегий для назначения. 0 зарезервирован для операционной системы. Пользовательские интерфейсы и API работают с классами приоритетов для процесса и потоков в процессе, которые затем объединяются системой в абсолютный уровень приоритета.
Ядро может изменять уровень приоритета потока в зависимости от его ввода-вывода и использования ЦП, а также от того, является ли он интерактивным (т. е. принимает и отвечает на ввод от людей), повышая приоритет интерактивных и ограниченных вводом-выводом процессов и понижая приоритет ограниченных ЦП процессов, чтобы увеличить скорость реагирования интерактивных приложений. [11] Планировщик был изменен в Windows Vista для использования регистра счетчика циклов современных процессоров, чтобы отслеживать, сколько именно циклов ЦП выполнил поток, а не просто использовать процедуру прерывания интервального таймера. [12] Vista также использует приоритетный планировщик для очереди ввода-вывода, чтобы дефрагментаторы дисков и другие подобные программы не мешали операциям переднего плана. [13]
Mac OS 9 использует кооперативное планирование для потоков, где один процесс управляет несколькими кооперативными потоками, а также обеспечивает вытесняющее планирование для многопроцессорных задач. Ядро планирует многопроцессорные задачи с помощью алгоритма вытесняющего планирования. Все процессы Process Manager выполняются в рамках специальной многопроцессорной задачи, называемой синей задачей . Эти процессы планируются кооперативно с использованием алгоритма циклического планирования ; процесс передает управление процессором другому процессу, явно вызывая блокирующую функцию, такую как WaitNextEvent. Каждый процесс имеет свою собственную копию Thread Manager, которая кооперативно планирует потоки этого процесса; поток передает управление процессором другому потоку, вызывая YieldToAnyThreadили YieldToThread. [14]
macOS использует многоуровневую очередь обратной связи с четырьмя диапазонами приоритетов для потоков — нормальный, системный высокий приоритет, только режим ядра и реальное время. [15] Потоки планируются с упреждением; macOS также поддерживает кооперативно запланированные потоки в своей реализации Thread Manager в Carbon . [14]
В AIX версии 4 существует три возможных значения политики планирования потоков:
Потоки в первую очередь представляют интерес для приложений, которые в настоящее время состоят из нескольких асинхронных процессов. Эти приложения могут накладывать меньшую нагрузку на систему, если будут преобразованы в многопоточную структуру.
AIX 5 реализует следующие политики планирования: FIFO, round robin и fair round robin. Политика FIFO имеет три различных реализации: FIFO, FIFO2 и FIFO3. Политика round robin называется SCHED_RR в AIX, а fair round robin называется SCHED_OTHER. [16]
Linux 1.2 использовал политику циклического планирования . [17]
В Linux 2.2 добавлены классы планирования и поддержка симметричной многопроцессорной обработки (SMP). [17]
В Linux 2.4 [17] использовался планировщик O (n) с многоуровневой очередью обратной связи с уровнями приоритета от 0 до 140; уровни 0–99 зарезервированы для задач реального времени, а уровни 100–140 считаются хорошими уровнями задач. Для задач реального времени квант времени для переключения процессов составлял приблизительно 200 мс, а для хороших задач — приблизительно 10 мс. [ необходима цитата ] Планировщик проходил по очереди выполнения всех готовых процессов, позволяя процессам с наивысшим приоритетом идти первыми и проходить свои временные интервалы, после чего они помещались в просроченную очередь. Когда активная очередь пуста, просроченная очередь станет активной очередью и наоборот.
Однако некоторые корпоративные дистрибутивы Linux, такие как SUSE Linux Enterprise Server, заменили этот планировщик на обратную версию планировщика O(1) (который поддерживался Аланом Коксом в его серии Linux 2.4-ac Kernel) для ядра Linux 2.4, используемого в дистрибутиве.
В версиях 2.6.0–2.6.22 ядро использовало планировщик O(1), разработанный Инго Молнаром и многими другими разработчиками ядра во время разработки Linux 2.5. Для многих ядер в то время Кон Коливас разработал наборы патчей, которые улучшили интерактивность с этим планировщиком или даже заменили его своими собственными планировщиками.
Работа Кона Коливаса, наиболее значительная из которых — его реализация справедливого планирования под названием Rotating Staircase Deadline (RSDL), вдохновила Инго Молнара на разработку совершенно справедливого планировщика (CFS) в качестве замены более раннему планировщику O(1) , в своем объявлении он упомянул Коливаса. [18] CFS — это первая реализация планировщика справедливого процесса очередей, широко используемая в операционной системе общего назначения. [19]
CFS использует хорошо изученный классический алгоритм планирования, называемый справедливой очередью , изначально придуманный для пакетных сетей . Справедливая очередь ранее применялась к планированию ЦП под названием пошаговое планирование . Планировщик справедливой очереди CFS имеет сложность планирования , где N — количество задач в очереди выполнения . Выбор задачи может быть выполнен за постоянное время, но повторная вставка задачи после ее выполнения требует операций, поскольку очередь выполнения реализована как красно-черное дерево .
Планировщик Brain Fuck Scheduler , также созданный Коном Коливасом, является альтернативой CFS.
В 2023 году Питер Зейлстра предложил заменить CFS на планировщик процессов раннего допустимого виртуального крайнего срока (EEVDF). [20] [21] Цель состояла в том, чтобы устранить необходимость в исправлениях задержки CFS . [22]
FreeBSD использует многоуровневую очередь обратной связи с приоритетами от 0 до 255. 0–63 зарезервированы для прерываний, 64–127 для верхней половины ядра, 128–159 для пользовательских потоков реального времени, 160–223 для пользовательских потоков с разделением времени и 224–255 для бездействующих пользовательских потоков. Также, как и Linux, он использует активную настройку очереди, но также имеет и бездействующую очередь. [23]
NetBSD использует многоуровневую очередь обратной связи с приоритетами в диапазоне от 0 до 223. 0–63 зарезервированы для потоков с разделением времени (по умолчанию, политика SCHED_OTHER), 64–95 — для пользовательских потоков, вошедших в пространство ядра , 96–128 — для потоков ядра, 128–191 — для пользовательских потоков реального времени (политики SCHED_FIFO и SCHED_RR) и 192–223 — для программных прерываний .
Solaris использует многоуровневую очередь обратной связи с приоритетами в диапазоне от 0 до 169. Приоритеты 0–59 зарезервированы для потоков с разделением времени, 60–99 для системных потоков, 100–159 для потоков реального времени и 160–169 для прерываний с низким приоритетом. В отличие от Linux, [23] когда процесс завершается с использованием своего кванта времени, ему присваивается новый приоритет и он возвращается в очередь. Solaris 9 представил два новых класса планирования, а именно класс с фиксированным приоритетом и класс справедливого распределения. Потоки с фиксированным приоритетом имеют тот же диапазон приоритетов, что и класс с разделением времени, но их приоритеты не корректируются динамически. Класс справедливого планирования использует доли ЦП для приоритезации потоков при принятии решений о планировании. Доли ЦП указывают на право на ресурсы ЦП. Они выделяются набору процессов, которые в совокупности называются проектом. [7]
Мы определяем время ответа на запрос для определенной задачи как промежуток времени между запросом и окончанием ответа на этот запрос.
Для клиента, которому требуется x секунд обслуживания, время его ответа будет равно времени его обслуживания x плюс время его ожидания.
Если обозначить время ожидания задания в очереди как t w , а время его фактического выполнения как t r , то время отклика составит r = t w + t r .
В интерактивной системе время выполнения может быть не лучшим критерием. Часто процесс может выдавать некоторые выходные данные довольно рано и может продолжать вычислять новые результаты, пока предыдущие результаты выводятся пользователю. Таким образом, еще одной мерой является время от отправки запроса до получения первого ответа. Эта мера, называемая временем ответа, представляет собой время, необходимое для начала ответа, а не время, необходимое для вывода ответа.
{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )