`Приложение: ответы на вопросы об адаптивном планировании потоков`

Ответы на часто задаваемые вопросы о планировщике потоков

Настоящее приложение содержит ответы на часто задаваемые вопросы о нюансах планировщика адаптивного партиционирования в ЗОСРВ «Нейтрино», а также на общие вопросы о партициях.

Статья включает:

Принципы планирования

Микроучет

Окно усреднения

Алгоритм планирования

Накладные расходы

Критически важные потоки и банкротство

Наследование

Бюджеты

Помещение потока в партицию

Системные аспекты ЗОСРВ «Нейтрино»

Сведения, которые изложены в настоящем приложении, носят ориентировочный характер и могут быть изменены в будущих релизах ЗОСРВ «Нейтрино».

Принципы планирования

Как планировщик потоков предоставляет партиции гарантированный минимальный бюджет CPU?

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

Обработчик прерываний часов вызывает планировщика потоков с периодом, который обычно составляет 1 миллисекунду. На каждом такте системных часов планировщик потоков выполняет следующие действия:

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

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

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

Когда планировщик потоков гарантирует партиции минимальный бюджет CPU?

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

Партиция готова расходовать не менее доли процессорного времени, соответствующей ее бюджету.
В многоядерных системах:
- let B( p ) — бюджет партиции p в процентах
- let R( p ) — количество готовых к выполнению потоков в нашей партиции, а
- let N — количество процессоров
Планировщик потоков гарантирует партиции p доступ к B( p ) процентам времени CPU в последнем окне усреднения, если:
```
R( p ) >= N * B( p ) / 100 
```
т.е. если в партиции достаточно готовых к выполнению потоков, чтобы загрузить все процессоры системы.
Планировщик не начислил резервное время ни одной партиции.

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

Верно ли, что если размер окна усреднения составляет 100 мс, время CPU усредняется с периодом в 100 мс?

С какой частотой контролируется соблюдение бюджетов партиций?

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

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

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

При каких системных допущениях работает планировщик потоков?

Планировщик потоков гарантирует партициям минимальные бюджеты CPU при следующих допущениях:

Обработчик прерываний часов выполняется периодически, т.е. пользователи не запрещают прерывания часов.
Счетчик ClockCycles() возрастает монотонно за исключением его циклического сброса счетчиков с недостаточной разрядностью.
Счетчик ClockCycles() увеличивается с постоянным периодом.
Полезная работа, выполняемая процессором, пропорциональна значению счетчика ClockCycles().
Счетчик ClockCycles() различных процессоров SMP-системы изменяются с одинаковой скоростью (при этом их значения могут отличаться друг от друга на постоянную величину).
Все процессоры SMP-системы работают с одинаковой частотой.
Разрешение функции ClockCycles() составляет не менее 1/200 периода системных часов.
Пользователь не совершает частые изменения размера окна усреднения.

Когда планировщик потоков вычисляет долю израсходованного времени CPU?

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

Насколько часто планировщик потоков вычисляет расход времени CPU?

Не реже, чем на каждом такте системных часов (как правило, раз в миллисекунду), а также при выполнении вызовов ядра, таких как отправка сообщений, импульсов и освобождение мьютекса. Например, в системе с процессором x86 с тактовой частотой 733MHz и интенсивным вводом/выводом планировщик вычисляет расход процессорного времени примерно 50 раз в миллисекунду.

При каких условиях планировщик обеспечивает жесткое реальное время?

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

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

Что такое режим свободного времени?

Что такое свободное время?

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

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

Обязательно ли возвращать предоставленное свободное время?

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

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

Затем активизируется партиция p2, которая ждет до тех пор, пока ее 10-миллисекундный перерасход бюджета перестанет учитываться в 100-миллисекундном окне усреднения. Время ожидания p2 составляет размер_окна − бюджет. В процессе ожидания партиция p2 фактически возвращает предоставленное ей свободное время.

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

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

Партиция p2 ждет до тех пор, пока ее расход времени CPU не перестает учитываться в 100-миллисекундном окне усреднения. В этом случае партиция p2 возвращает только размер_окна − бюджет, несмотря на то, что она выполнялась в течение минуты, когда партиция p1 была неактивна.

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

Исключением из вышеописанного принципа является свободное время, которое получено непосредственно перед изменением размера окна с помощью вызова SchedCtl( SCHED_APS_SET_PARMS, ... ). Поскольку при изменении размера окна память планировщика аннулируется, указанное свободное время не возвращается.

Как планировщик потоков работает на многопоточных процессорах (hyper threading)?

С точки зрения адаптивного партиционирования двухпоточный процессор эквивалентен многоядерной системе с двумя процессорами. Адаптивное партиционирование работает с допущением, что все виртуальные процессоры имеют одинаковую производительность. Это верно для SMP-систем, однако многопоточные процессоры работают с одинаковой производительностью только при условии, что они не простаивают. Планировщику потоков необходимо, чтобы производительность системы была пропорциональна показаниям счетчика ClockCycles().

Сколько времени выполняется поток с карусельным планированием?

В отсутствие планировщика потоков адаптивного партиционирования (т.е. при стандартном планировании ЗОСРВ «Нейтрино») поток с карусельного планирования:

немедленно вытесняется потоком с более высоким приоритетом
при отсутствии потоков с более высоким или равным приоритетом выполняется до тех пор, пока добровольно не передает управление
при наличии потока с равным приоритетом выполняется в течение четырех тактов (4 мс), после чего управление передается другому потоку

При использовании планировщика потоков адаптивного партиционирования поток с карусельного планирования:

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

Планировщик переопределяет размер кванта карусельного планирования. Если неизрасходованный бюджет партиции превышает 4 такта системных часов, планирование потоков осуществляется в обычном для ЗОСРВ «Нейтрино» режиме. При полной нагрузке следует исходить из того, что поток с карусельным планированием может быть вытеснен на каждом такте системных часов.

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

Сколько времени выполняется поток FIFO?

В отсутствии планировщика потоков — до тех пор, пока добровольно не передает управление или не вытесняется более приоритетным потоком.

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

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

Сколько времени выполняется поток со спорадическим планированием?

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

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

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

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

С какой периодичностью выполняется планировщик потоков?

С какой периодичностью планировщик потоков контролирует соблюдение бюджетов?

Планировщик потоков запускается и контролирует соблюдение бюджетов:

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

Периодичность активизации планировщика потоков зависит от интенсивности обмена сообщениями.

Как режимы экономии энергии влияют на планирование?

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

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

Как изменение периода системных часов с помощью функции ClockPeriod() влияет на планирование?

Изменение периода системных часов приводит к нарушению точности планирования, поскольку планировщик не реагирует на изменение длительности такта. Тем не менее, если вызвать функцию SchedCtl( SET_APS_PARMS, ... ) и указать ей текущий размер окна, планировщик пересчитывает все внутренние параметры, которые зависят от периода часов, и точность планирования восстанавливается.

Следует задавать размер окна после изменения периода системных часов.

Микроучет

Как устроен микроучет?

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

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

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

Для создания меток времени применяется системный вызов ClockCycles().

Насколько часто планировщик потоков выполняет микроучет?

Планировщик потоков выполняет микроучет:

при каждой передаче управления от одного потока другому
на каждом такте системных часов

Как работает функция ClockCycles()?

Функционирование планировщика потоков всегда зависит от процессора системы. В системах с архитектурой x86 ЗОСРВ «Нейтрино» использует счетчик тактов процессора, который встроен непосредственно в микросхему CPU и считывается одной командой.

В системах PowerPC ЗОСРВ «Нейтрино» считывает показания аналогичного счетчика с помощью нескольких команд. В вышеупомянутых системах значение, возвращаемое функцией ClockCycles(), инкрементируется приблизительно с тактовой частотой процессора (т.е. увеличивается на 3 миллиарда в секунду при тактовой частоте процессора 3 ГГц или на 1 миллиард при тактовой частоте процессора 1 ГГц).

Если в процессоре отсутствует счетчик тактов, ЗОСРВ «Нейтрино» эмулирует высокоточные часы и возвращает их показания с помощью вызова ClockCycles(). Например, на процессорах ARM операционная система считывает промежуточное значение таймера обратного отсчета, который применяется для генерации прерываний часов. Это значение позволяет отсчитывать время внутри текущего такта. «Нейтрино» складывает его с константой, которая определяется в начале такта часов, и формирует значение, которое возвращается функцией ClockCycles().

На одних процессорах (например, ARM), таймер обратного отсчета, который используется для эмуляции функции, ClockCycles(), находится вне микросхемы и считывается посредством медленных операций ввода/вывода. На других процессорах (например, MIPS) таймер обратного отсчета интегрирован в микросхему, и его считывание выполняется быстро.

Какова точность микроучета?

Какова точность функции ClockCycles()?

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

Какова точность учета времени потоков?

Она совпадает с разрешением функции ClockCycles(), которое зависит от платформы и, как правило, значительно меньше длительности такта часов.

В соответствии с требованиями к точности планирования потоков разрешение не должно превышать 1/200 периода часов, однако на платформе x86 оно находится в наносекундном диапазоне.

Окно усреднения

Как устроено окно усреднения?

Окно усреднения состоит из таблиц. У каждой партиции имеются две таблицы, в одной из которых регистрируется расход времени CPU в критически важном режиме, а в другой — суммарный расход времени CPU. Каждому такту часов соответствует одна запись в каждой таблице; если размер окна усреднения равен 100 мс, а период часов — 1 мс, таблицы включают в себя 100 записей. В каждой записи указан расход времени CPU в соответствующем такте. Пример:

[99ms ago][98 ms ago][97 ms ago]....[1 ms ago][current ms]

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

Сумма элементов таблицы всегда равна совокупному времени, которое израсходовано партицией в течение окна усреднения.

Когда планировщик вытесняет поток, он добавляет время его выполнения с момента запуска или начала последнего такта в элемент текущий такт таблицы. Если поток выполнялся в критически важном режиме, планировщик также регистрирует время его выполнения в записи текущий такт таблицы резервного времени партиции. Планировщик также регистрирует время выполнения в начале такта, однако после зачисления времени выполнения потока в счет соответствующей партиции (запись [текущий такт]) смещает таблицу. При смещении таблицы:

запись [99 мс назад] удаляется
все остальные записи сдвигаются на одну позицию влево (запись [98 мс назад] занимает место записи [99 мс назад] и т.д.).
Планировщик создает новую запись [текущий такт] с нулевым начальным значением

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

Что означает термин «алгоритм смещения окна»?

Окно усреднения смещается не физически, а логически:

Сумма всех записей таблицы хранится в отдельном поле used_cycles.
Индекс таблицы cur_hist_index указывает на запись [текущий такт].
При микроучете планировщик суммирует время CPU, которое израсходовано текущим потоком, с текущей записью таблицы и с указанным полем. Пример:
```
usage_hist[cur_hist_index] += delta_time;
used_cycles                += delta_time;
```
При смещении окна планировщик выполняет следующие действия:
- вычитает из суммы самую старшую по времени запись:
```
used_cycles -= usage_hist[(cur_hist_index + 1) MOD 100] 
```
- увеличивает индекс таблицы на единицу по модулю ее размера (например, 100):
```
cur_hist_index = (cur_hist_index + 1) MOD 100 
```
Эти действия выполняются для каждой партиции в таблицах учета обычного и критически важного режимов.

Можно ли изменять размер окна?

Как изменение размера окна влияет на планирование?

Размер окна можно изменять «на лету» с помощью вызова SchedCtl( SCHED_APS_SET_PARMS, ... ). Планировщик не создает новые таблицы посредством функции malloc(), но обнуляет содержимое всех существующих таблиц, поля суммарных значений и индексы таблиц.

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

Мы рекомендуем использовать размер окна по умолчанию или задавать его при запуске. Также не рекомендуется часто изменять размер окна.

Как максимальные задержки связи связаны с размером окна усреднения?

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

Например, если размер окна усреднения составляет 100 мс, а бюджет партиции p — 10%, партиция p исчерпывает свой бюджет через 10 мс непрерывного выполнения. Через 90 мс информация об этом удаляется из окна усреднения, партиция p получает бюджет и может выполняться снова.

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

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

Алгоритм планирования

Как планировщик потоков выбирает поток для выполнения?

Как работает алгоритм планирования?

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

Сначала рассмотрим несколько вспомогательных функций:

Функция COMPETING( p ) возвращает логическое значение True, если:
- в партиции p в текущий момент выполняется поток с ненулевым приоритетом
- в партиции p имеется готовый к выполнению поток с ненулевым приоритетом
Функция HAS_BUDGET( p ) возвращает логическое значение True, если:
```
cycles_used( p ) + cycles_left_in_current_tick <= budget_cycles( p ) 
```
где:

cycles_used( p )
Процессорное время, которое израсходовано партицией в текущем окне усреднения.
budget_cycles( p )
Размер окна усреднения, выраженный в значениях ClockCycles() (не в миллисекундах) и умноженный на бюджет партиции p в процентах.
Функция MAY_RUN_CRITICAL( p ) возвращает логическое значение True, если:
- партиция p имеет ненулевой резервный бюджет
- в последнем окне усреднения партиция p работала в критически важном режиме, и ее неизрасходованный резервный бюджет составляет не менее 1/32 периода системных часов
- среди потоков партиции p, которые готовы к выполнению или выполняются в текущий момент, самый приоритетный поток может выполняться в критически важном режиме
Функция HIGHEST_PRIO( p ) возвращает максимальный среди приоритетов потоков партиции p, которые выполняются или готовы к выполнению.
Если партиция имеет ненулевой бюджет, функция относительной доли свободного времени (RFF( p )) имеет вид:
```
1 - used_cycles( p ) / budget_cycles( p ) 
```
Если партиция имеет нулевой бюджет, RFF( p ) на постоянную величину меньше наименьшего из значений RFF() для всех остальных партиций с ненулевым бюджетом.

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

Неполная нагрузка (underload)

Когда COMPETING( p ) && (HAS_BUDGET( p ) || MAY_RUN_CRITICAL( p )) == True как минимум для одной партиции p.

Полная нагрузка (full load)

Когда COMPETING( p ) == True for all p, and HAS_BUDGET( p ) || MAY_RUN_CRITICAL( p ) == False для всех партиций p.

Свободное время (free time)

Когда COMPETING( p ) == False как минимум для одной партиции p с ненулевым бюджетом.

Простой (idle)

Когда COMPETING( p ) == False для всех партиций p.

Планировщик выбирает одну из функций оценки в зависимости от режима работы:

Неполная нагрузка: merit( p ) = (COMPETING( p ), HAS_BUDGET( p ) || MAY_RUN_CRITICAL( p ), HIGHEST_PRIO( p ), RFF( p ))
Полная нагрузка: merit( p ) = (COMPETING( p ), RFF( p ))
Свободное время (по умолчанию): merit( p ) = (COMPETING( p ), HAS_BUDGET( p ) || MAY_RUN_CRITICAL( p ), HIGHEST_PRIO( p ), RFF( p ))
Свободное время (SCHEDPOL_RATIO): merit( p ) = (COMPETING( p ), HAS_BUDGET( p ) || MAY_RUN_CRITICAL( p ), RFF( p ))
Простой: Не определена.

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

merit( p ) > merit( p' )

для всех партиций p', отличных от p.

Функции оценки возвращают кортежи и сравниваются между собой как кортежи. Пример:

(a, b) < (c, d) if (a < c) || ((a = c) && (b < d))

Как планировщик обнаруживает самый приоритетный поток в партиции?

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

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

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

Аналогичный механизм применяется в традиционном планировании ЗОСРВ «Нейтрино» и реализуется с помощью следующих макросов:

DISPATCH_SET()
DISPATCH_CLEAR()
DISPATCH_HIGHEST_PRI()

Как вычисляются функции относительной доли свободного времени (RFF, Relative Fraction Free)?

Для вычисления функции RFF() необходимо делить числа с плавающей точкой. Тем не менее, операции деления чисел с плавающей и даже фиксированной точкой не выполняются в ядре ЗОСРВ «Нейтрино», поскольку на некоторых платформах они являются очень трудоемкими.

ЗОСРВ «Нейтрино» вычисляет функцию, эквивалентную RFF(), используя только операции сложения и умножения.

Как алгоритм планирования работает без деления и операций над числами с плавающей точкой?

Для вычисления RFF() необходимо делить числа с плавающей точкой. Тем не менее, ЗОСРВ «Нейтрино» нужно не определять абсолютные значения RFF(), а сравнивать между собой RFF( p1 ), RFF( p2 ), ..., RFF( pn ).

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

relative_fraction_free( P ) или
```
RFF( P ) = 1 - cycles_used / budget_cycles 
```
Вместо поиска партиции p, для которой RFF( p ) > `RFF( p' )`, где p' отличается от p, вычисляется значение relative_fraction_used( p ) = RFU( p ) = cycles_used / budget_cycles и выполняется поиск партиции p, для которой RFU( p ) < `RFU( p' )`, где p' отличается от p.
Затем определяется функция, значения которой расположены в том же порядке, что и значения RFU():
- Так:
```
used_cycles( p0 ) / budget_cycles( p0 ) < used_cycles( p1 ) / budget_cycles( p2 ) < ... < used_cycles( pn ) / budget_cycles( pn ) 
```
- пусть
```
k = budget_cycles( p0 ) * budget_cycles( p1 ) * ... * budget_cycles( pn ) 
```
  тогда
- если все значения >0:
```
k / budget_cycles( p0 ) * used_cycles( p0 ) < k / budget_cycles( p1 ) * used_cycles( p1 ) < ... < k / budget_cycles( pn ) * used_cycles( pn ) 
```
- Значения c( p ) = K / budget_cycles( p ) для всех партиций p вычисляются однократно либо пересчитываются при изменении бюджета какой-либо из партиций. Эти значения сохраняются и не пересчитываются при планировании.
- При планировании ЗОСРВ «Нейтрино» вычисляет функцию
```
f( p ) = used_cycles( p ) * c( p ) 
```
  и сравнивает f( p ) с f( p' ), чтобы определить наилучшее значение RFF().

При этом возникают две проблемы:

Слишком большая разрядность

Для вычисления f( p ) = used_cycles( p ) * c( p ) необходимо перемножать 64-разрядные числа, но поскольку требуемая точность составляет 0,2%, ЗОСРВ «Нейтрино» делит все значения c( p ) на одинаковый коэффициент, при котором наибольшее значение функции является 16-разрядным. «Нейтрино» также сдвигает поле used_cycles( p ) до тех пор, пока его максимально возможное значение не становится 16-разрядным. Таким образом, при планировании ЗОСРВ «Нейтрино» вычисляет только функцию:

f( p ) = (used_cycles( p ) >> scaling_factor) * scaled_c( p )

Партиции с нулевым бюджетом

В вышеописанных алгоритмах ЗОСРВ «Нейтрино» требуется умножать и делить на ноль. Тем не менее, функция RFF() для партиции с нулевым бюджетом определяется как константа, которая меньше любого возможного значения RFF() партиции с ненулевым бюджетом. В «Нейтрино» RFU( p ) партиции с нулевым бюджетом определяется как константа, которая больше RFU(). Наибольшее значение f() равно размер_окна * c( pm ), где c( pm ) > c( p' ) для всех партиций p', отличных от pm.

Таким образом, «Нейтрино» вычисляет f() партиции с нулевым бюджетом по формуле:

f_zero = 1 + размер_окна * c( pm )

и масштабирует полученное значение для достижения требуемой разрядности.

Размер окна задается в количестве циклов.

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

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

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

поток t имеет наивысший приоритет в системе
поток t может выполняться в критически важном режиме
партиции p назначен ненулевой резервный бюджет
процессорное время, которое израсходовано всеми потоками партиции p в последнем окне усреднения, меньше ее резервного бюджета
партиция p исчерпала свой обычный бюджет
как минимум для одной партиции p', отличной от p, выполняется условие
```
COMPETING( p' ) && (HAS_BUDGET( p' ) || MAY_RUN_CRITICAL( p' )) == True 
```
Определения функций COMPETING(), HAS_BUDGET() и MAY_RUN_CRITICAL() представлены на этой странице в ответе на типичный вопрос "Как работает алгоритм планирования?".

Каковы численные ограничения в алгоритме планирования?

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

Не более 32 партиций из-за использования битовых масок и 32-разрядных целых чисел.
Не более 16 партиций из-за использования операции умножения 16-разрядных чисел при вычислении функции RFF().
Не более 8 партиций — эмпирически установленный предел, при котором планировщик экономно потребляет память и время CPU.
Бюджеты задаются с помощью целочисленных значений (например, 30% или 31%, но не 30.5%).
Количество потоков в партиции не ограничено.

Какова точность алгоритма планирования?

Под точностью понимается способность планировщика обеспечивать соблюдение бюджетов партиций системы при полной нагрузке. В ЗОСРВ «Нейтрино» точность планирования равна наибольшей из следующих величин:

0.5%
длительность такта часов (мс) либо размер окна (мс). При использовании окна размером 100 мс и такта по умолчанию точность составляет 1%

После установки размера окна усреднения x мс точность планирования не определена в течение последующих x мс.

Первое ограничение связано с тем, что для ускорения алгоритма планирования значение RFF() вычисляется с точностью до определенного количества разрядов.

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

На практике второе ограничение означает, что при изменении размера окна планировщик удаляет статистику использования процессорного времени. Следовательно, партиция (p) с самым приоритетным потоком выполняется в течение budget( p ) * размер_окна (ms), после чего управление передается другой партиции. По окончании окна всем партициям снова предоставляются гарантированные бюджеты. Таким образом, при размере окна усреднения 100 мс и бюджете партиции 40% планирования считается точной, если в течение последних 100 мс она израсходовала от 39 до 41 мс процессорного времени. Это происходит, если размер окна не изменялся на протяжении последних 100 мс. На практике точность планирования, как правило, значительно выше.

Когда планирование выполняется неточно?

В некоторых ситуациях, которые возникают при передаче сообщений, для уменьшения накладных расходов применяется сокращенный вариант алгоритма планирования. Он реализован с помощью внутренних функций планировщика ready_ppg(), block_and_ready_ppg() и adjust_priority_ppg().

Накладные расходы

На счет какой партиции зачисляются накладные расходы планирования?

К накладным расходам относятся все вызовы ядра, при которых происходит переключение потоков (например, обмен сообщениями и захват мьютексов). Обозначим первый выполняемый поток t1, а следующий поток — t2. Накладные расходы вызовов ядра, которые выполняются потоком t1 и приводят к его останову с последующей передачей управления потоку t2 распределяются между t1 и t2, однако большая их часть зачисляется на счет t1.

Действие	Партиция, которой начисляются расходы
Вход в ядро (начало системного вызова)	t1
Выполнение алгоритма планирования	t1
Переключение контекста	t2
Выход из ядра (завершение системного вызова)	t2

На счет какой партиции зачисляются накладные расходы по обработке прерываний?

Обработка прерываний состоит из двух частей, одна из которых выполняется в функции-обработчике, а другая — в потоке.

Обработка в потоке длится значительно дольше, чем в функции-обработчике. Обработчик прерывания определяет поток, которому передается событие прерывания.

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

Время работы потока зачисляется на счет партиции, в которой он выполняется, а время функции-обработчика — на счет партиции, которая выполняется в момент ее запуска.

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

Каковы затраты времени CPU на выполнение планировщика потоков?

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

Какой объем памяти требуется планировщику потоков?

Данные: Общая область памяти объемом несколько Кбайт + 2 Кбайт для каждой партиции.
Код: Около 18 Кбайт.

Код и данные планировщика потоков находятся в пространстве ядра.

Какие факторы увеличивают накладные расходы, связанные с планировщиком потоков?

В порядке важности:

количество операций планирования, которое зависит от интенсивности отправки сообщений, событий и сигналов, использования мьютексов и функций приостановки потоков
платформа — например, на процессорах ARM планировщик потоков работает заметно медленнее, поскольку для реализации функции ClockCycles() требуется выполнять операции ввода/вывода
длительность такта системных часов
количество партиций
использование масок потоков

Перечисленные факторы вызывают приблизительно линейный рост накладных расходов.

Следующие факторы не оказывают никакого влияния на трудоемкость планирования:

количество потоков
размер окна усреднения (кроме небольшого эффекта от изменения размеров окна)
бюджеты партиций
приоритеты потоков
алгоритмы планирования потоков

Критически важные потоки и банкротство

Каким образом планировщик отмечает критически важные потоки?

Как планировщик определяет, что поток является критически важным?

В ЗОСРВ «Нейтрино» имеется блок данных thread_entry, в котором хранится состояние каждого потока. Три бита состояния определяют:

разрешено ли потоку постоянно выполняться в критически важном режиме
разрешено ли потоку выполняться в критически важном режиме до блокировки
выполняется ли поток в критически важном режиме (и расходует резервный бюджет своей партиции) в текущий момент

Эти биты состояния устанавливаются следующим образом:

Разрешено постоянное выполнение в критически важном режиме: Когда пользователь вызывает для потока функцию SchedCtl() с флагом SCHED_APS_MARK_CRITICAL.
Разрешено выполнение в критически важном режиме до блокировки: Когда поток получает событие от обработчика прерывания, сообщение от другого потока, который может выполняться в критически важном режиме постоянно или до блокировки, либо событие, которое обработано с помощью макроса SIGEV_MAKE_CRITICAL().
Поток выполняется в критически важном режиме в текущий момент: Когда алгоритм планирования не может выполнять поток в обычном режиме.

Угрожают ли критически важные потоки безопасности системы?

Нет.

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

Когда планировщик проверяет банкротство?

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

Как планировщик обнаруживает банкротство?

ЗОСРВ «Нейтрино» сравнивает суммарное время выполнения партиции в критически важном режиме (в последнем окне усреднения) с назначенным ей максимальным резервным бюджетом. Для учета расхода резервного бюджета у каждой партиции имеется отдельное скользящее окно размером 100 мс, в котором для каждой миллисекунды указано, какую часть времени партиция выполнялась в критически важном режиме.

Наследование

Что такое наследование партиций?

Наследование партиций — это зачисление времени CPU, которое расходуется потоком, на счет партиции другого потока. Благодаря наследованию планировщик потоков является адаптивным.

Когда происходит наследование партиций?

Наследование партиций происходит в двух ситуациях:

когда один поток выполняется от имени другого

Когда клиентский поток отправляет сообщение серверному потоку, серверный поток работает от имени клиентского потока. В этом случае ЗОСРВ «Нейтрино» зачисляет время выполнения серверного потока (с момента приема сообщения до начала ожидания следующего сообщения) на счет партиции клиентского потока.

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

Как работает наследование партиций при использовании мьютексов?

Когда потоки становятся в очередь для получения доступа к мьютексу, ЗОСРВ «Нейтрино» не заставляет поток, который владеет мьютексом, ждать от имени потоков, ожидающих его освобождения. Таким образом, здесь отсутствует наследование партиций.

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

Таким образом, когда поток t1 владеет мьютексом и находится в партиции, которая исчерпала свой бюджет, а другой поток t2 пытается захватить этот мьютекс, ЗОСРВ «Нейтрино» сначала приостанавливает поток t2 до тех пор, пока t1 не освобождает мьютекс (классический принцип действия мьютекса), а затем заменяет партицию p1 на p2 до освобождения мьютекса, если бюджет партиции p2 не равен нулю. Этот алгоритм предотвращает длительные задержки, если партиция, которая владеет мьютексом, исчерпывает свой бюджет.

Насколько быстро выполняется наследование партиций?

Очень быстро.

В ЗОСРВ «Нейтрино» у каждого потока имеется блок данных thread_entry с указателем на партицию, в которой он находится. Таким образом, наследование реализуется путем изменения этого указателя. Как правило, у ЗОСРВ «Нейтрино» даже не возникает необходимость вносить изменения в микроучет, поскольку до и после наследования выполняется одна и та же партиция.

Почему наследование партиций при передаче сообщений безопасно?

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

Бюджеты

Можно ли динамически изменять бюджеты?

Бюджеты партиций можно изменять в любой момент времени.

Как изменение бюджета влияет на планирование?

Насколько быстро вступает в силу изменение бюджета?

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

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

Когда вступает в силу изменение бюджета партиции?

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

Что такое партиция с нулевым бюджетом?

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

Каким образом планировщик гарантирует, что сумма бюджетов всех партиций равна 100%?

При запуске ЗОСРВ «Нейтрино» создает первую партицию System с бюджетом 100%. Если поток, который выполняется в партиции, создает новую партицию, текущая партиция считается родительской по отношению к новой. Бюджет дочерней партиции всегда заимствуется из бюджета родительской партиции и не может уменьшать его до отрицательного значения. Так формируется иерархия партиций, которые делят между собой часть 100% бюджета исходной партиции System.

Каким образом планировщик предотвращает увеличение бюджета партиции ненадежным потоком?

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

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

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

Какими непрямыми действиями можно увеличивать бюджет партиции?

Для увеличения бюджета партиции можно:

часто изменять размер окна
предоставить партиции неограниченный резервный бюджет и объявить поток критически важным

Отключите защиту партиций в настройках планировщика, воспользовавшись привилегиями суперпользователя.

Для выполнения перечисленных действий необходимо отключать защиту партиций в настройках планировщика от имени пользователя root.

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

Увеличивать бюджет партиции (он не может превышать бюджет родительской партиции, даже если защита отключена).
Назначить потоку приоритет 255 (он может лишить ресурса CPU все остальные потоки своей партиции, но не потоки других партиций).
Назначить потоку алгоритм планирования FIFO и запускать цикл (этот поток может лишить ресурса CPU все остальные потоки своей партиции, но не потоки других партиций).
создать дочернюю партицию (ее бюджет не может превышать бюджет родительской партиции).

Помещение потока в партицию

Как включить поток в партицию?
Насколько быстро поток включается в партицию?: В ЗОСРВ «Нейтрино» у каждого потока имеется блок данных thread_entry с указателем на партицию, в которой он находится. Чтобы включить поток в партицию, достаточно присвоить значение этому указателю. Эта операция выполняется очень быстро, и наиболее трудоемкой ее частью является вход в ядро.

Системные аспекты ЗОСРВ «Нейтрино»

Почему ЗОСРВ «Нейтрино» не позволяет удалять партиции?: Гораздо безопаснее и эффективнее назначать партиции нулевой бюджет, а не удалять ее.

Чтобы удалить партицию, ЗОСРВ «Нейтрино» должна обнаружить все ее потоки (либо убедиться в их отсутствии) и переместить их в другую партицию.

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

Он реализован в виде статической библиотеки, которая встроена в procnto-*. Модуль procnto-* также содержит код стандартного планировщика ЗОСРВ «Нейтрино», однако при наличии планировщика адаптивного партиционирования инициализирует его вместо стандартного планировщика. Затем планировщик адаптивного партиционирования присваивает ряду указателей адреса своих функций, которые выполняют операции планирования (ready(), block() и др.), создает партицию System и возвращает ее модулю procnto-*.
Запрещает ли планировщик потоков прерывания ввода/вывода?: Да. Планировщик потоков запрещает прерывания с помощью функции InterruptDisable() при каждой операции микроучета. Длительность запрета прерываний незначительно превышает время выполнения вызова ClockCycles(). Сюда не входит запрет прерываний для синхронизации обработки прерываний часов, планирования, сбора статистики партиций и изменения бюджетов.
Ограничена ли частота сбора статистики с помощью вызова SchedCtl( SCHED_APS_PARTITION_STATS ) в связи с накладными расходами?: Единственные накладные расходы связаны с вызовом ядра SchedCtl().

Сбор статистики не блокирует прерывания и не задерживает смещение окна и выполнение планирования (на других процессорах SMP-системы). Корректность сбора статистики обеспечивается путем обнаружения конфликтов с последующей отменой и повторным выполнением операций API. Следует учитывать, что вызов SchedCtl( SCHED_APS_PARTITION_STATS, ... ) завершается с ошибкой EINTR только в маловероятном случае возникновения трех конфликтов подряд. Обычно эта ситуация возникает только в случае, если пользователь задал очень малый период часов, который нарушает надежность работы системы.

Предыдущий раздел: перейти