Что такое шедулер в программировании

Scheduler

Что такое планировщик? Планировщик контролирует, когда начинается подписка и когда доставляются уведомления. Он состоит из трех компонентов.

• Планировщик — это структура данных. Он знает, как хранить и ставить задачи в очередь на основе приоритета или других критериев.
• Планировщик — это контекст выполнения. Он обозначает, где и когда задача выполняется (например, немедленно или в другом механизме обратного вызова, таком как setTimeout или process.nextTick, или в кадре анимации).
• Планировщик имеет (виртуальные) часы. Он предоставляет понятие «время» с помощью метода получения now() в планировщике. Задачи, запланированные в конкретном планировщике, будут придерживаться только времени, обозначенного этими часами.

Планировщик позволяет определить,в каком контексте выполнения будет доставлять уведомления Наблюдателю.

В приведенном ниже примере мы берем обычный простой Observable, который синхронно выдает значения 1 , 2 , 3 , и используем операторObservOn , чтобы указать observeOn async , который будет использоваться для доставки этих значений.

Который исполняется с выходом:

Обратите внимание, как уведомления got value. были доставлены just after subscribe , что отличается от поведения по умолчанию, которое мы видели до сих пор. Это связано с тем, что observeOn(asyncScheduler) вводит прокси-наблюдателя между new Observable и последним наблюдателем. Давайте переименуем некоторые идентификаторы, чтобы сделать это различие очевидным в примере кода:

proxyObserver proxyObserver вObservOn observeOn(asyncScheduler) asyncScheduler ) , и его функция next(val) выглядит примерно так:

Асинхронный планировщик работает с async или setTimeout , даже если заданная setInterval delay нулю. Как обычно, в JavaScript известно, что setTimeout(fn, 0) запускает функцию fn раньше всех на следующей итерации цикла обработки событий. Это объясняет, почему got value 1 доставляется в finalObserver сразу после того , как произошла just after subscribe

Метод Schedule schedule() Планировщика принимает аргумент delay , который относится к количеству времени относительно собственных внутренних часов Планировщика. Часы планировщика не обязательно должны иметь какое-либо отношение к фактическому времени настенных часов. Вот как временные операторы, такие как delay , работают не с фактическим временем, а со временем, продиктованным часами Планировщика. Это особенно полезно при тестировании, когда виртуальный планировщик времени может использоваться для имитации времени настенных часов, в то время как на самом деле синхронно выполняются запланированные задачи.

Scheduler Types

Асинхронный планировщик — это один из встроенных планировщиков, предоставляемых RxJS async Каждый из них может быть создан и возвращен с помощью статических свойств объекта Scheduler .

Scheduler	Purpose
null	Не пропуская ни одного планировщика,уведомления доставляются синхронно и рекурсивно.Используйте это для операций с постоянным временем или для рекурсивных операций хвоста.
queueScheduler	Расписания в очереди в текущем кадре событий (планировщик батутов).Используйте это для итерационных операций.
asapScheduler	Графики в очереди микро-задач,которая является той же самой,что и очередь,используемая для обещаний.В основном после текущего задания,но до следующего задания.Используйте это для асинхронных преобразований.
asyncScheduler	Расписания работают с setInterval . Используйте это для операций по времени.
animationFrameScheduler	Задание расписания,которое произойдет непосредственно перед следующим перерисовыванием содержимого браузера.Может быть использована для создания гладкой анимации в браузере.

Using Schedulers

Возможно, вы уже использовали планировщики в своем коде RxJS без явного указания типа планировщиков, которые будут использоваться. Это связано с тем, что все операторы Observable, имеющие дело с параллелизмом, имеют необязательные планировщики. Если вы не предоставите планировщик, RxJS выберет планировщик по умолчанию, используя принцип наименьшего параллелизма. Это означает, что выбирается планировщик, обеспечивающий наименьшее количество параллелизма, который удовлетворяет потребности оператора. Например, для операторов, возвращающих наблюдаемое с конечным и небольшим количеством сообщений, RxJS не использует планировщик, т . е. null или undefined . Для операторов, возвращающих потенциально большое или бесконечное количество сообщений, используется планировщик queue Для операторов, использующих таймеры, async используется.

Поскольку RxJS использует планировщик с наименьшим параллелизмом, вы можете выбрать другой планировщик, если хотите ввести параллелизм для повышения производительности. Чтобы указать конкретный планировщик, вы можете использовать те операторные методы, которые берут планировщик, например, from([10, 20, 30], asyncScheduler) .

Статические операторы создания обычно принимают планировщик в качестве аргумента. Например, from(array, scheduler) позволяет указать планировщик, который будет использоваться при доставке каждого уведомления, преобразованного из array . Обычно это последний аргумент оператора. Следующие статические операторы создания принимают аргумент планировщика:

• bindCallback
• bindNodeCallback
• combineLatest
• concat
• empty
• from
• fromPromise
• interval
• merge
• of
• range
• throw
• timer

Используйте subscribeOn , чтобы запланировать, в каком контексте будет выполняться вызов subscribe() .По умолчанию вызов subscribe() для Observable происходит синхронно и немедленно.Тем не менее, вы можете отложить или запланировать фактическую подписку для данного Scheduler, используя оператор экземпляра subscribeOn(scheduler) , где scheduler — это аргумент, который вы предоставляете.

ИспользуйтеObservOn observeOn чтобы запланировать, в каком контексте будут доставляться уведомления. Как мы видели в приведенных выше примерах, оператор observeOn(scheduler) вводит посредника Observer между исходным Observable и целевым наблюдателем, где посредник планирует вызовы целевого наблюдателя с помощью заданного вами scheduler .

Операторы экземпляра могут принимать планировщик в качестве аргумента.

Операторы, связанные со временем, такие как bufferTime , debounceTime , delay , auditTime , sampleTime , timeInterval , throttleTime , timeout , timeoutWith , windowTime берут Scheduler в качестве последнего аргумента, а в остальном по умолчанию работают с asyncScheduler .

Другие операторы экземпляра, которые принимают планировщик в качестве аргумента: cache , combineLatest , concat , expand , merge , publishReplay , startWith .

Обратите внимание, что и cache , и publishReplay принимают Scheduler, потому что они используют ReplaySubject. Конструктор ReplaySubjects принимает необязательный Scheduler в качестве последнего аргумента, потому что ReplaySubject может иметь дело со временем, что имеет смысл только в контексте Scheduler. По умолчанию ReplaySubject использует планировщик queue для предоставления часов.

О многозадачности и планировщике задач (шедулер)

Небольшой экскурс в проблемы многозадачности и реализации планировщиков.

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

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

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

Тут сразу у современного пользователя возникает вопрос: а где мышка, клавиатура и монитор? А это уже надстройки над нашим конвейером. Через прерывания контроллера переферийных устройств в стройный ряд инструкций и данных, летящих из памяти вклиниваются и аппаратные команды, которые заставляют наш конвейер прерваться и перейти к определённому адресу, где расположена программа-обработчик прерывания.

В Linux можно посмотреть статистику по прерываниям с помощью команды vmstat — под system есть колонка in (сокращение от interrupts) — количество прерываний в секунду (не все они аппаратные).

Данная команда будет выводить статистику каждую секунду 5 раз:

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

Важно, что только через прерывания компьютер и программы понимают, что во внешнем мире что-то произошло. К примеру, прошло какое-то время — по прерыванию от аппаратного таймера.

Как вы думаете, что произойдёт, если по какой-то причине перестанут поступать прерывания от таймера? Или таймер начнёт медленнее тикать?

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

Иллюзия многозадачности

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

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

И тут появляется планировщик

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

Поэтому наша программа-планировщик должна стараться раздавать имеющиеся кванты времени “справедливо”. При этом понятие “справедливо” — тоже довольно обширное. К примеру, пользователь будет недоволен, если воспроизведение фильма будет подвисать, при этом не сильно расстроится, если фоновая задача будет притормаживать.

Плюсом к этому будет грустно, если задача распределения ресурсов процессора будет съедать сильно много процессорного времени — неприятно, когда управленцы получают больше, чем исполнители.

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

И тут есть множество проблем для планировщика. Так, к примеру, нельзя определить, когда программа дойдёт до определённого момента (идеальный момент для переключения) чисто по алгоритмическим причинам.

К слову, может быть кто-то знает альтернативные подходы к реализации вычислительных систем, не процессор-шина-память?

Что-то может пойти не так и какая-то программа зависнет — что тут делать, как решать, что нужно передать управление, что делать с этой программой? Опять же, понять, что она реально зависла для произвольной программы мы не можем…

И тут остаётся использовать те самые аппаратные прерывания. Если программа сама не передаёт управление — через прерывание таймера мы можем понять, что время пришло переключить управление. Ну и в целом — можно по таймеру следить за “справедливостью” выделения процессорного времени. На него ориентироваться при планировании исполнения процессов.

Пара слов о проблемах реализации многозадачности

Работа с системными ресурсами напрямую предполагает работу программы в реальном режиме процессора, а не в защищённом. Работая в GNU/Linux нам невозможно получить доступ напрямую к любому участку памяти, а также работать с регистрами процессора типа sp, ip и т.д. без изменения кода ядра и его пересборки.

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

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

То есть она будет запускать другие программы, отдавать им или прерывать их исполнение, а между запусками хранить их состояние. Например, значения регистров процессора. Куда важнее, сохранить состояние регистра IP (instruction pointer) — регистра, который указывает на исполняемый в текущий момент код. И здесь важно, чтобы программа сохраняла его по условленному адресу в памяти при передаче управления. Тогда планировщик сможет использовать его для возврата управления.

Итого, нам нужно как минимум выделить некоторую память под список IP, соответствующих адресам текущих исполняемых команд в процессах. Кроме того — память компьютера доступна всем и сразу, так что нужно договориться, чтобы авторы программ писали в разных областях памяти, чтобы не залезать в чужую. Опять же нужно позаботиться о стеке процессов. В общем, масса проблем. Многие из них сейчас решаются аппаратными средствами, прочее же делает ОС.

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

Надеюсь, в общих чертах было ясно, какие действия необходимы и на сколько непросто написать даже такой примитивный планировщик?

Многозадачность и справедливость

Итак, представим, что у нас есть N процессов и 1 процессор. Нам нужно поделить время процессора между всеми процессами справедливым образом. То есть каждому по 1÷N. Однако, пусть мы и справедливы, и все процессы равны, но некоторые всё же “равнее” — есть процессы с низкой потребностью в отзывчивости и ресурсе CPU, есть же критичные — задержку работы которых пользователь сразу заметит. Поэтому процессы приоритезируются. Тогда наша формула принимает следующий вид: “Процент времени процесса = Приоритет ÷ Сумма приоритетов”.

Но это в идеальном мире. В реальности же процессы вольно или невольно стараются получить времени больше, или же отдают управление раньше (через тот же sched_yield), чем им выделено. Тем не менее, за условной “справедливостью” следить нужно.

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

Есть 2 основных подхода к многозадачности: кооперативный и вытесняющий. В кооперативной многозадачности процессы сами решают, когда они готовы отдать управление. В вытесняющей многозадачности планировщик ведёт подсчёт времени
исполнения процессов (с помощью таймера) и сам прерывает рабочий процесс, когда тот выходит за выделенный лимит.

Кооперативная многозадачность

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

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

Среди примеров ОС, работающих по такому принципу — Windows 3.* Кто-нибудь слышал или даже знаком с этой веткой Windows?

К примеру, для переключения между тредами может быть использована команда ThreadSwitch. Текущая задача остаётся активной (готовой) и передаёт управление следующей готовой задаче. Хоть внутри и выполняются низкоуровневые операции, для языка программирования высокого уровня данная функциональная возможность выглядит как обычная функция.

Из очереди тредов берётся новый из начала, текущий помещается в конец. Текущий стек сохраняется в предварительно подготовленный map (словарь номер_треда — адрес_стека_треда ), из этого же map берётся адрес стека для нового треда, кладётся в регистр SP (stack pointer), запускается новый тред.

К слову, и в Linux можно попросить ОС забрать управление у треда досрочно с помощью вызова pthread_yield .

Все помнят, что такое очередь? Как работает FIFO?

Аналогично работает async-await в современных языках программирования высокого уровня таких как ECMA Script, Python3 и т.д. На команде await управление передаётся следующему исполняемому потоку. Внутри событийной петли (по сути — той же очереди) они кружат, выполняясь один за другим.

Вытесняющая многозадачность

Из плюсов — бó‎льшая привязка к реальности (планировщик следит за реальным временем исполнения процесса), а значит более прогнозируемая отзывчивость. Также выше стабильность — если какой-то процесс завис — он будет «выедать» только отведённое ему время.

Однако, если размер кусков, на которые мы нарезаем процессорное время мал, то из-за частых смен задач (смен контекста) можно получить потерю производительности.

За счёт прогнозируемости и отзывчивости данный подход распространился на почти все современные ОС.

Говоря о расходе времени при переключении контекста, как вы думаете, на чём же больше всего теряется время?

Смена контекста (context switch)

Само собой, при смене контекста производится много работы. Часть из неё мы уже описали выше, но особого внимания заслуживает отдельный момент, который мы ещё не обсуждали.

Кеш процессора

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

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

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

Для примера, если запустить эту же программу но на одном ядре (пусть и в 8 потоков) — смены контекста также будут происходить, но кеш будет “горячим” — программа выполнится быстрее. Для запуска на определённых процессорах программ (или миграции) используется утилита taskset (или программно sched_setaffinity ).

Посмотреть же статистическую информацию о смене контекстов за секунду можно всё также в vmstat . Столбик system, раздел “cs” (от “context switch”).

nice и приоритет исполнения процессов

Если же мы хотим настроить приоритет программы, воспользуемся утилитой nice (или программно с setpriority ). С помощью неё можно указать ОС, с каким приоритетом мы бы хотели запустить программу. Приоритеты в Linux определяются цифрами от -20 до 19. Чем меньше — тем приоритетнее. Для установки приоритета ниже 0 необходимы права супер-пользователя (например, можно установить через sudo ).

Есть ещё процесс idle (процесс для простоя процессора, или же программа запущенная с политикой SCHED_IDLE ), приоритет которого ниже 19 и migration_thread (для вытеснения процесса с ядра для миграции его на другой процессор) — у него выше -20.

Для примера, запустим параллельно с разными приоритетами несколько экземпляров предыдущей программы:

И посмотрим на результат выполнения:

Идут почти в порядке приоритетов.

Также есть renice для изменения приоритета процессу, группе процессов или процессам определённого пользователя.

Посмотреть же приоритет запущенных процессов можно через утилиту ps , указав, что нам хочется видеть и столбик nice (NI):

Кванты времени

Говоря о смене контекстов при переключении задач, стоит сказать и о том времени, которое непосредственно выделяется. Кванты или time slice — единицы планирования, тот ресурс, за который борются процессы.

Для начала посмотрим настройки, которые можно использовать для тюнинга планировщика:

Особо нас интересует kernel.sched_min_granularity_ns — это как раз размер кванта времени, выделяемого за раз. На пользовательских машинах и серверах значения могут сильно отличаться. К примеру, на моём ноутбуке это 3мс, а на сервере 10мс. Меньше отзывчивость, зато меньше смен контекста.

При этом программа может отдать управление раньше, чем закончился выделенный квант — через sched_yield / pthread_yield .

Настройки, увиденные вами характерны для текущего планировщика по умолчанию Linux — CFS — Completely Fair Scheduler (полностью честный планировщик). Однако, до него было ещё несколько планировщиков, а также есть альтернативные.

Планировщики в Linux

К примеру, всё началось с планировщика O(n) — все задачи расположены в списке, каждому исходя из приоритета присвоено определённое количество тиков (tick), которые соответствуют time slice-ам. Ищем задачу с максимальным значением, исполняем, понижаем счётчик тиков задачи. Если не можем найти задачи с положительным счётчиком — поднимаем счётчик всем задачам, исходя из приоритета.

Очевидная проблема данного планировщика — при росте количества задач растёт и время работы планировщика. Причём растёт линейно. В теории сложности вычислений этот алгоритм относится к классу O(n) — рост времени вычисления растёт пропорционально количеству входных данных.

Также данный планировщик имеет проблемы при работе с несколькими процессорами — одна блокировка на одну очередь — то есть одновременно с ней может работать только один процессор.

В 2002-ом году в Linux стали использовать более продвинутый планировщик — O(1). Как можно догадаться, алгоритм работы был изменён. Время работы планировщика более не зависело от числа запущенных процессов. Теперь у каждого процессора было по паре списков. В первом отсортированном списке — текущие процессы, ожидающие выполнения, во втором — исчерпавшие своё время. Как только первый список заканчивался — они менялись местами.

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

Также имелись и проблемы с честным выделением ресурсов пользователям. Если один запустит 10 процессов, а другой 1, то разделение времени будет нечестым.

В ядре 2.6.23 появился новый планировщик CFS — Completely Fair Scheduler (полностью честный планировщик). Он уже оперирует не процессами, а сущностями планирования ( sched_entity ) — появилась возможность честнее разделять время между пользователями. Сам планировщик стал выделять время ближе к приоритетам.

Алгоритм стал несколько “дороже” — O(logN) — используется красно-чёрное дерево, что с ростом количества процессов заметно всё меньше и меньше. Планирование из одной структуры данных организовано довольно оптимально — для работы на многопроцессорных системах подходит также лучше. Именно он сейчас используется в Linux.

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

Так в Linux используется SCHED_DEADLINE с алгоритмом планирования по ближайшему сроку завершения (EDF — Earliest deadline first):

• планировщик ведёт список процессов, отсортированный по сроку завершения (deadline);
• в работу берётся готовый процесс, имеющий самый близкий deadline;
• при появлении нового процесса — пересортировка.

Программы же должны при запуске указывать через sched_setattr параметры runtime , deadline и period — время исполнения в худшем случае, срок завершения и период.

Планировщик ввода-вывода

Помимо ресурса процессора также немаловажен ресурс ввода / вывода. С появлением и распространением SSD дела стали лучше, чем при HDD (аж 10мс для перехода к нужному участку носителя), но всё равно это сильно медленнее, чем работа с памятью. Да и в целом ресурсами лучше зря не разбрасываться.

При работе с дисковой подсистемой используется планировщик ввода / вывода. Причём для разных устройств и задач подходят разные планировщики. Так CFQ (Completely Fair Queue) и deadline планировщики сначала будут буферизировать запросы на чтение / запись, чтобы сгруппировать запросы к устройству так, чтобы эффективнее с него считать. Например, чтобы за один оборот диска можно было прочитать сектора для разных процессов.

С другой стороны, если используется сетевое хранилище, или виртуальное — лучше использовать noop — планировщик, который не будет ничего придумывать, а просто писать / читать как есть. Пусть сетевое хранилище или хостовая система думает об эффективности, а мы не будем на это тратить CPU.

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

Записав же туда нужный планировщик с помощью echo — изменить на нужный.

Для приоритизации операций ввода-вывода используется ionice . Для начала разберёмся с классами планирования:

1. Real time — получают первыми доступ к диску. Использование данного класса может помешать работе других программ. Имеет 8 приоритетов.
2. Best effort (по умолчанию) — также имеет 8 приоритетов. Программы с одним приоритетом обслуживаются по очереди (round-robin).
3. Idle — получает доступ к диску, если другим он не нужен.

Приоритеты от 0 до 7. Меньше — приоритетнее.

Не все планировщики используют приоритеты. К примеру, deadline стремится к тому, чтобы ожидание операции не превышало определённого времени. Noop не делает ничего — просто выполняет операции последовательно. С другой стороны, тот же CFQ использует приоритеты — с ним ionice будет работать.

Go scheduler. Простыми словами

Меня зовут Ерванд Агаджанян, я backend developer в EMCD Tech. В данной статье расскажу о планировщике Go. Часть материала взял из книги Уильяма Кеннеди Ultimate Go. Вначале поговорим о планировщике OS, после перейдем к планировщику Go и сравним их.

Планировщик OS

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

Вот некоторые важные сущности, с которыми взаимодействует планировщик OS:

Состояния потоков (Thread States):

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

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

Executing. Поток размещен на ядре и выполняет свои машинные инструкции.

Типы выполняемой работы (Types Of Work):

CPU-Bound. Это работа, которая никогда не создает ситуации, где поток может быть помещен в состояние ожидания. Пример: вычисление числа pi до n-й цифры является CPU-Bound работой.

I/O-Bound. Это работа, которая заставляет потоки входить в состояние ожидания. Как пример, работа, которая заключается в запросе доступа к ресурсу по сети или совершении системных вызовов в операционную систему. Поток, которому необходимо получить доступ к базе данных, будет выполнять I/O-Bound работу.

Переключения контекста (Context Switching). Это физический акт обмена потоками на ядре. Переключение контекста происходит, когда планировщик вытягивает Executing поток из ядра и заменяет его Runnable потоком. Вытащенный поток может вернуться в состояние Runnable (если он все еще может работать) или в состояние Waiting (если он был заменен из-за запроса типа I/O-Bound). Переключение контекста считается дорогой операцией и происходит относительно медленно. Величина задержки, возникающая при переключении контекста, зависит от различных факторов. Если исходить из расчета, что машина выполняет 12 операций в наносекунду, а переключение контекста занимает

1500 наносекунд, то мы теряем 12 000 операций и более.
Если есть программа, ориентированная на работу с I/O-Bound, то переключение контекста будет преимуществом. Как только поток переходит в состояние Waiting, его место занимает другой поток в состоянии Runnable. Это позволяет ядру всегда выполнять работу, и является одним из самых важных аспектов планирования. Если программа сосредоточена на CPU-Bound работе, то переключение контекста станет кошмаром для производительности. Представьте, что у потока есть постоянная работа, и переключение контекста останавливает выполнение этой работы. Эта ситуация резко контрастирует с тем, что происходит с рабочей нагрузкой, связанной с вводом-выводом (I/O-Bound).

Планировщик Go

Как и в случае с планировщиком OS, мы не можем предсказать работу планировщика Go, так как он также недетерменирован. Это связано с тем, что принятие решений для этого планировщика находится не в руках разработчика, а в руках runtime Go.
Здесь также перечислим важные сущности, с которыми взаимодействует планировщик Go:

P, M, G.

P (processor) — логический процессор (не железо). Это условный контекст, который объединяет поток операционной системы (M) и очередь горутин. Количество горутин, привязанных к P неограниченно. По умолчанию количество P берётся из значения переменной среды GOMAXPROCS и равно количеству логических ядер компьютера.

M (machine thread) — поток OS. Он закреплён за P и имеет с ним отношение один к одному.

G (goroutine) — горутина

Coroutine. Каждой программе Go также дается начальная горутина (G). Goroutine — это, по сути, Coroutine, но это Go, поэтому мы заменяем букву C на G и получаем слово Goroutine. Можно думать о Goroutines как о потоках уровня приложения. Они во многом похожи на потоки ОС: например, точно так же, как потоки ОС включаются и выключаются в зависимости от контекста ядра, горутины включаются и выключаются в зависимости от контекста потока OS (M). Потоки OS располагаются на ядре OS, а горутины располагаются на потоках OS. Своеобразная пирамида.

Состояния потоков (Thread States). Тут очень много схожего с состояниями потоков OS:

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

Runnable: Горутине нужно время на M, чтобы она могла выполнять назначенные инструкции. Если есть много горутин, которым нужно время, то горутины должны ждать дольше, чтобы получить это самое время. Кроме того, индивидуальное количество времени, которое получает каждая горутина, сокращается по мере того, как все больше горутин соревнуются за время. Этот тип задержки планирования также может быть причиной низкой производительности.

Running. Горутина была помещена на M и выполняет свои инструкции.

Переключения контекста (Context Switching). В сравнении с переключением контекста OS, переключение контекста у планировщика GO — более легковесная операция:

200 наносекунд, при которых мы теряем

2 400 операций. То есть примерно в пять раз меньше.

GRQ, LRQ. В планировщике Go есть две разные очереди выполнения: глобальная очередь выполнения (Global Run Queue — GRQ) и локальная очередь выполнения (Local Run Queue — LRQ). Каждому P присваивается LRQ, которая управляет горутинами, назначенными для выполнения на P. Эти горутины по очереди включаются и выключаются в зависимости от контекста M, назначенного этому P.
GRQ предназначен для горутин, которые еще не были назначены для какого-либо P. Существует процесс перемещения горутин из GRQ в LRQ.

Теперь объединим все сказанное выше в одну схему:

На рисунке 1 в левом верхнем углу мы видим глобальную очередь горутин (GRQ), в которой на данный момент находится одна горутина. В центре картинки находится поток операционной системы (M), расположенный на ядре (Core), и к этому потоку прикреплен логический процессор (P). Видим, что на данный момент одна горутина находится в состоянии Running, так как она прямо сейчас расположена на потоке операционной системы (M). И видим, что у процессора (P) есть своя локальная очередь горутин (LRQ), на которой располагаются 3 горутины. Их состояние runnable.

Work stealing

Планировщик GO работает по принципу «кражи работы». Этот принцип помогает балансировать и распределять горутины по соответствующим процессорам (P).

На рисунке 2 мы видим многопоточную Go программу с двумя P, каждый из которых обслуживает по 4 горутины (G). Есть и глобальная очередь (GRQ) с единственной горутиной (G9). Что случится, если на одном из P все горутины закончат свою работу?

На рисунке 3 видно, что у P1 больше нет горутин. Ни в состоянии Running, ни в состоянии Runnable. Однако P2 в своей локальной очереди (LRQ) имеет целых 3 горутины.
P1, чтобы не простаивать, должен будет «украсть» у P2 горутины. Вот алгоритм кражи:

Следуя этому алгоритму, P1 должен проверить P2 на наличие у него горутин в LRQ. И при наличии взять половину:

Что мы и видим на рисунке 4.
Далее, что произойдет, если P2 закончит обслуживание всех своих горутин, а у P1 ничего не останется в LRQ?

На рисунке 5 видим, что у P1 есть одна горутина в состоянии Running и пустая LRQ. У P2 нет ни одной горутины и так же пустая LRQ.

На рисунке 6 видно, что P2 в таком случае возьмет горутину из GRQ.

Заключение

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

Что такое шедулер в программировании

CPU Scheduling and Scheduler: Part 1

“CPU scheduling is the basis of multiprogramming operating systems. By switching the CPU among processes, the operating system can make the computer more productive.”

Before dive into the scheduling algorithm first, let’s see some basic terms related to the process during its execution —

Arrival Time: Time at which the process enters in the ready queue.

Completion time: Time at which a process completes its execution.

Burst time: Total time required by a process for its execution. A typical process execution consists of a cycle of CPU execution and I/O wait. Process changes its state from CPU execution to I/O and vice versa. In other words, process execution begins with the CPU burst, followed by an I/O burst, then another CPU burst and so on. At last, its execution terminates with the CPU burst by making a system request to terminate the process execution.

So what exactly is the CPU Burst and I/O Burst?

CPU Burst: The duration for which a process gets control of the CPU and it is being executed in the CPU is the CPU burst time, and the concept of gaining the control of the CPU is the CPU burst.

I/O Burst: While the process is in the running state, it may ask for I/O operation, thus the process goes to the wait or block state, where the I/O will be processed and then it will be sent back to the ready state. The duration for which it is in the waiting state is called I/O Burst.

Turnaround Time: The interval from the time of submission of a process to the time of completion is called Turnaround time. In other words, it is total time spend by a process in the system.

TA = Completion Time — Arrival Time = Execution Time + Waiting Time

Waiting Time: Total time spent by the process in the ready queue waiting for its turn to get on the CPU.

Response time: Response time is the time from the submission of a request until the first response is produced.

CPU bound Process: The process which spends a lot of time on the CPU is called a CPU bound process. They do a lot of calculations with comparatively little data. They can be expected to hold the CPU for as long as the scheduler will allow. Users do not typically expect an immediate response from the computer when running CPU bound programs. They should be given lower priority by the scheduler.

I/O Bound Process: Processes that are mostly waiting for the completion of input or output are I/O Bound. They are the most interactive process where less calculation is performed on CPU in comparison to I/O Operations. These processes should be given higher priority by the scheduler.

Scheduling Queue: The operating system maintains all PCBs in Process Scheduling Queues. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue. The OS maintains the following process scheduling queue —

Job Queue: Each new process goes into the job queue. Process in the job queue resides on mass storage and avail the allocation of the memory.

Ready Queue: The set of all processes that are in main memory and are waiting for CPU allocation are kept in the ready queue. Ready Queue is generally maintained as a linked list. The queue header points to the first process PCB and tail points to the last process PCB. Each process PCB contain a pointer field that points to the next process PCB in the linked list.

Waiting Queue or Device Queue: The set of processes waiting for allocation of certain I/O device is kept in the waiting queue. Device Queue is also maintained using a linked list in a similar way as the ready queue.

This is all for the first part, in the next part, we will see some other concept related to CPU Scheduling.