В вычислительной технике планирование — это действие по распределению ресурсов для выполнения задач . Ресурсами могут быть процессоры , сетевые каналы или карты расширения . Задачи могут быть потоками , процессами или потоками данных .
Деятельность по планированию осуществляется процессом, называемым планировщиком . Планировщики часто разрабатываются таким образом, чтобы все ресурсы компьютера были заняты (как при балансировке нагрузки ), позволяли нескольким пользователям эффективно совместно использовать системные ресурсы или достигали целевого качества обслуживания .
Планирование имеет фундаментальное значение для самих вычислений и является неотъемлемой частью модели выполнения компьютерной системы; концепция планирования позволяет обеспечить многозадачность компьютера с помощью одного центрального процессора (ЦП).
Планировщик может преследовать одну или несколько целей, например:
На практике эти цели часто конфликтуют (например, пропускная способность и задержка), поэтому планировщик реализует подходящий компромисс. Предпочтение измеряется любым из упомянутых выше факторов в зависимости от потребностей и целей пользователя.
В средах реального времени , таких как встроенные системы автоматического управления в промышленности (например, робототехника ), планировщик также должен гарантировать, что процессы могут уложиться в сроки ; это имеет решающее значение для поддержания стабильности системы. Запланированные задачи также можно распространять на удаленные устройства по сети и управлять ими через административную серверную часть.
Планировщик — это модуль операционной системы, который выбирает следующие задания, которые будут допущены в систему, и следующий процесс для запуска. Операционные системы могут иметь до трех различных типов планировщиков: долгосрочный планировщик (также известный как планировщик допуска или планировщик высокого уровня), среднесрочный или среднесрочный планировщик и краткосрочный планировщик . Названия указывают на относительную частоту выполнения их функций.
Планировщик процессов — это часть операционной системы, которая решает, какой процесс запустить в определенный момент времени. Обычно он имеет возможность приостановить запущенный процесс, переместить его в конец запущенной очереди и запустить новый процесс; такой планировщик известен как вытесняющий планировщик , иначе это кооперативный планировщик . [5]
Мы различаем долгосрочное планирование , среднесрочное планирование и краткосрочное планирование в зависимости от того, как часто необходимо принимать решения. [6]
Долгосрочный планировщик , или планировщик допуска , решает, какие задания или процессы должны быть допущены в очередь готовности (в основной памяти); то есть, когда делается попытка выполнить программу, ее допуск к набору выполняющихся в данный момент процессов либо разрешается, либо задерживается долгосрочным планировщиком. Таким образом, этот планировщик определяет, какие процессы должны выполняться в системе, степень параллелизма, которая должна поддерживаться в любой момент времени – много или несколько процессов должны выполняться одновременно, и как разделить между интенсивными операциями ввода-вывода и процессорными нагрузками. предстоит вести интенсивные процессы. Долгосрочный планировщик отвечает за контроль степени мультипрограммирования.
В общем, большинство процессов можно описать как связанные с вводом-выводом или с использованием ЦП . Процесс, связанный с вводом-выводом, — это процесс, который тратит больше времени на ввод-вывод, чем на вычисления. Процесс, связанный с ЦП, напротив, генерирует запросы ввода-вывода нечасто, тратя больше времени на вычисления. Важно, чтобы долгосрочный планировщик выбирал хорошее сочетание процессов, связанных с вводом-выводом и процессором. Если все процессы связаны с вводом-выводом, очередь готовности почти всегда будет пустой, и краткосрочному планировщику будет мало что делать. С другой стороны, если все процессы привязаны к процессору, очередь ожидания ввода-вывода почти всегда будет пустой, устройства останутся неиспользованными, и система снова окажется несбалансированной. Таким образом, система с наилучшей производительностью будет иметь комбинацию процессов, связанных с использованием ЦП и операций ввода-вывода. В современных операционных системах это используется для обеспечения того, чтобы процессы реального времени получали достаточно процессорного времени для завершения своих задач. [7]
Долгосрочное планирование также важно в крупномасштабных системах, таких как системы пакетной обработки , компьютерные кластеры , суперкомпьютеры и фермы рендеринга . Например, в параллельных системах часто требуется совместное планирование взаимодействующих процессов , чтобы предотвратить их блокировку из-за ожидания друг друга. В этих случаях для поддержки этих функций обычно используется специальное программное обеспечение планировщика заданий в дополнение к любой базовой поддержке планирования приема в операционной системе.
Некоторые операционные системы позволяют добавлять новые задачи только в том случае, если они уверены, что все сроки в реальном времени могут быть соблюдены. Конкретный эвристический алгоритм, используемый операционной системой для принятия или отклонения новых задач, представляет собой механизм контроля доступа . [8]
Среднесрочный планировщик временно удаляет процессы из основной памяти и помещает их во вторичную память (например, на жесткий диск ) или наоборот, что обычно называется выгрузкой или выгрузкой ( также неправильно называется выгрузкой или подкачкой ). . Среднесрочный планировщик может решить заменить процесс, который не был активен в течение некоторого времени, процесс с низким приоритетом, процесс, который часто вызывает страничные сбои , или процесс, занимающий большой объем памяти в чтобы освободить основную память для других процессов, заменив процесс обратно позже, когда будет доступно больше памяти или когда процесс будет разблокирован и больше не ожидает ресурса.
Сегодня во многих системах (тех, которые поддерживают отображение виртуального адресного пространства на вторичное хранилище, отличное от файла подкачки), среднесрочный планировщик может фактически выполнять роль долгосрочного планировщика, рассматривая двоичные файлы как выгружаемые процессы при их выполнении. . Таким образом, когда требуется сегмент двоичного файла, его можно заменить по требованию или отложенной загрузке , что также называется подкачкой по запросу .
Краткосрочный планировщик (также известный как планировщик ЦП ) решает, какой из готовых процессов в памяти должен быть выполнен (выделен ЦП) после тактового прерывания , прерывания ввода-вывода, вызова операционной системы или другой формы. сигнала . _ Таким образом, краткосрочный планировщик принимает решения о планировании гораздо чаще, чем долгосрочные или среднесрочные планировщики. Решение о планировании должно будет приниматься как минимум после каждого временного интервала, а они очень короткие. Этот планировщик может быть вытесняющим , что означает, что он способен принудительно удалять процессы из ЦП, когда он решает выделить этот ЦП другому процессу, или невытесняющим (также известным как добровольный или кооперативный ), и в этом случае планировщик не может принудительно отключить процессы от процессора.
Вытесняющий планировщик опирается на программируемый интервальный таймер , который вызывает обработчик прерываний , работающий в режиме ядра и реализующий функцию планирования.
Другим компонентом, который участвует в функции планирования ЦП, является диспетчер, который представляет собой модуль, который передает управление ЦП процессу, выбранному краткосрочным планировщиком. Он получает управление в режиме ядра в результате прерывания или системного вызова. Функции диспетчера заключаются в следующем:
Диспетчер должен работать как можно быстрее, поскольку он вызывается при каждом переключении процесса. Во время переключения контекста процессор какое-то время фактически простаивает, поэтому следует избегать ненужных переключений контекста. Время, необходимое диспетчеру для остановки одного процесса и запуска другого, называется задержкой диспетчеризации . [7] : 155
Дисциплина планирования (также называемая политикой планирования или алгоритмом планирования ) — это алгоритм, используемый для распределения ресурсов между сторонами, которые одновременно и асинхронно запрашивают их. Дисциплины планирования используются в маршрутизаторах (для обработки пакетного трафика), а также в операционных системах (для распределения времени ЦП между потоками и процессами ), дисках ( планирование ввода-вывода ), принтерах ( диспетчер очереди печати ), большинстве встроенных систем и т. д. .
Основные цели алгоритмов планирования — свести к минимуму нехватку ресурсов и обеспечить справедливость между сторонами, использующими ресурсы. Планирование решает проблему принятия решения о том, каким из невыполненных запросов должны быть выделены ресурсы. Существует множество различных алгоритмов планирования. В этом разделе мы представляем некоторые из них.
В компьютерных сетях с коммутацией пакетов и другом статистическом мультиплексировании понятие алгоритма планирования используется как альтернатива организации очереди пакетов данных в порядке очереди .
Простейшими алгоритмами планирования с максимальной эффективностью являются циклический перебор , справедливая организация очередей ( алгоритм справедливого планирования «максимум-миним»), пропорционально-справедливое планирование и максимальная пропускная способность . Если предлагается дифференцированное или гарантированное качество обслуживания , а не связь по принципу «максимальные усилия», можно использовать взвешенную справедливую организацию очереди .
В усовершенствованных беспроводных сетях пакетной радиосвязи, таких как сотовая система HSDPA (высокоскоростной пакетный доступ по нисходящей линии связи) 3.5G , для использования информации о состоянии канала может использоваться каналозависимое планирование . Если условия канала благоприятны, пропускная способность и спектральная эффективность системы могут быть увеличены. В еще более продвинутых системах, таких как LTE , планирование сочетается с каналозависимым попакетным динамическим распределением каналов или путем назначения нескольких несущих OFDMA или других компонентов выравнивания частотной области пользователям, которые лучше всего могут их использовать. [9]
«Первым пришел — первым обслужен » ( FIFO ), также известный как «первым пришел — первым обслужен» (FCFS), является простейшим алгоритмом планирования. FIFO просто ставит процессы в очередь в том порядке, в котором они поступают в очередь готовности. Обычно это используется дляочередь задач , например, как показано в этом разделе.
Самый ранний срок выполнения (EDF) или наименьшее время до завершения — это алгоритм динамического планирования, используемый в операционных системах реального времени для помещения процессов в приоритетную очередь. Всякий раз, когда происходит событие планирования (завершение задачи, выпуск новой задачи и т. д.), в очереди будет выполняться поиск процесса, ближайшего к его крайнему сроку, который будет следующим, запланированным для выполнения.
Аналогично принципу «Сначала самая короткая работа» (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. Каждый процесс имеет свою собственную копию диспетчера потоков, который совместно планирует потоки этого процесса; поток передает управление процессором другому потоку путем вызова YieldToAnyThreadили YieldToThread. [14]
macOS использует многоуровневую очередь обратной связи с четырьмя диапазонами приоритета потоков: нормальный, высокий приоритет системы, только режим ядра и режим реального времени. [15] Потоки планируются заранее; macOS также поддерживает совместно запланированные потоки в своей реализации Thread Manager в Carbon . [14]
В AIX версии 4 существует три возможных значения политики планирования потоков:
Потоки в первую очередь представляют интерес для приложений, которые в настоящее время состоят из нескольких асинхронных процессов. Эти приложения могут снизить нагрузку на систему, если их преобразовать в многопоточную структуру.
В AIX 5 реализованы следующие политики планирования: FIFO, циклический перебор и справедливый циклический перебор. Политика FIFO имеет три различные реализации: FIFO, FIFO2 и FIFO3. В AIX политика циклического перебора называется SCHED_RR, а политика справедливого циклического перебора — 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. Для многих ядер Кон Коливас разработал наборы патчей, которые улучшили интерактивность с этим планировщиком или даже заменили его своими собственными планировщиками.
Работа Кона Коливаса, в первую очередь его реализация справедливого планирования под названием « Крайний срок вращающейся лестницы» (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: архивная копия в заголовке ( ссылка )