Монотонное планирование

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

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

Введение

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

• Нет совместного использования ресурсов (процессы не совместно используют ресурсы, ресурс , например аппаратный очередь или любой вид семафора блокировки или неблокировки ( ожидание занятости ))
• Детерминированные сроки в точности равны периодам
• Статические приоритеты (выполняемая задача с наивысшим статическим приоритетом немедленно вытесняет все остальные задачи)
• Статические приоритеты назначаются в соответствии с монотонными соглашениями о ставках (задачи с более короткими периодами/сроками имеют более высокий приоритет)
• Время переключения контекста и другие потоковые операции бесплатны и не влияют на модель.

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

Оптимальность

Назначение приоритета с монотонной скоростью является оптимальным при данных предположениях, а это означает, что если какой-либо алгоритм планирования со статическим приоритетом может уложиться во все сроки, то и алгоритм с монотонной скоростью тоже может это сделать. Алгоритм монотонного по срокам планирования также оптимален при равных периодах и сроках, ведь в этом случае алгоритмы идентичны; кроме того, монотонное планирование по срокам является оптимальным, когда сроки меньше периодов. Для модели задачи, в которой сроки могут превышать периоды, алгоритм Одсли, снабженный точным тестом на планирование для этой модели, находит оптимальное назначение приоритетов.

Верхние границы использования

Наименьшая верхняя граница

Лю и Лэйланд (1973) доказали, что для набора из n периодических задач с уникальными периодами существует приемлемое расписание, которое всегда будет соответствовать установленным срокам, если загрузка ЦП ниже определенного предела (в зависимости от количества задач). Тест на планирование для RMS:

$U=\sum _{i=1}^{n}{U_{i}}=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({2}^{1/n}-1)$

где U — коэффициент использования, C _i — время вычислений для процесса i , T _i — период выпуска (с крайним сроком на один период позже) для процесса i , а n — количество процессов, которые необходимо запланировать. Например, U ≤ 0,8284 для двух процессов. Когда число процессов стремится к бесконечности , это выражение будет стремиться к:

$\lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots$

Поэтому приблизительная оценка, когда ${n}\geq {10}$ заключается в том, что RMS может уложиться во все сроки, если общая загрузка ЦП U составляет менее 70%. Остальные 30% ЦП могут быть выделены для задач с более низким приоритетом, не выполняемых в режиме реального времени. Для меньших значений n или в случаях, когда U близко к этой оценке, следует использовать рассчитанную границу использования.

На практике для ${i^{th}}$ процесс, ${C_{i}}$ должно представлять наихудшее (т.е. самое продолжительное) время вычислений и ${T_{i}}$ должен представлять собой крайний срок для наихудшего случая (т. е. кратчайший период), в течение которого должна произойти вся обработка.

Связь с

В теории массового обслуживания T i _{называется} временем между прибытиями , а C _i называется временем обслуживания . Эти два параметра часто указываются как ставки:

$\lambda _{i}={1 \over T_{i}}$ - скорость прибытия, и

$\mu _{i}={1 \over C_{i}}$ это тариф за обслуживание.

Верхняя граница для гармоничных наборов задач

Лю и Лейланд отметили, что эту границу можно ослабить до максимально возможного значения 1,0, если для задач ${T_{m}}$, ${T_{i}}$ где ${T_{m}}{>}{T_{i}}$ и $i=1...m-1$, ${T_{m}}$ является целым числом, кратным ${T_{i}}$, то есть все задачи имеют период, который не просто кратен самому короткому периоду, ${T_{1}}$, но вместо этого период любой задачи кратен всем более коротким периодам. Это известно как гармонический набор задач . Примером этого может быть: $[{T_{1}},{T_{2}},{T_{3}},{T_{4}}]=[1,3,6,12]$. Лю и Лейланд признают, что не всегда возможно иметь гармоничный набор задач и что на практике вместо этого могут использоваться другие меры по смягчению последствий, такие как буферизация для задач с мягкими сроками или использование подхода динамического назначения приоритетов, чтобы позволить для более высокой границы.

на

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

$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq K({2}^{1/K}-1)$

В случае, когда период каждой задачи кратен периоду любой другой задачи, которая имеет более короткий период, набор задач можно рассматривать как состоящий из n гармонических подмножеств задач размером 1 и, следовательно, ${K}{=}{n}$, что делает это обобщение эквивалентным наименьшей верхней границе Лю и Лейланда. Когда ${K}{=}{1}$, верхняя граница становится равной 1,0, что соответствует полному использованию.

Стохастические границы

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

Гиперболическая граница

Гиперболическая граница является более жестким достаточным условием планируемости, чем то, которое было представлено Лю и Лейландом:

$\prod _{i=1}^{n}(U_{i}+1)\leq 2$,

где U _i — загрузка ЦП для каждой задачи. Это самая точная верхняя граница, которую можно найти, используя только коэффициенты использования отдельных задач.

Совместное использование ресурсов

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

Отключение приоритета

• The OS_ENTER_CRITICAL() и OS_EXIT_CRITICAL() примитивы, которые блокируют прерывания ЦП в ядре реального времени, например MicroC/OS-II
• The splx() семейство примитивов, которые встраивают блокировку прерываний устройства (FreeBSD 5.x/6.x),

Наследование приоритета

• Базовый протокол наследования приоритетов повышает приоритет задачи, которая удерживает ресурс, до приоритета задачи, которая запрашивает этот ресурс во время выполнения запроса. При выпуске ресурса восстанавливается первоначальный уровень приоритета до продвижения. Этот метод не предотвращает взаимоблокировки и страдает от цепной блокировки . То есть, если задача с высоким приоритетом последовательно обращается к нескольким общим ресурсам, ей, возможно, придется ожидать (блокировать) задачу с более низким приоритетом для каждого из ресурсов. Патч реального времени , заархивированный 13 октября 2020 г. на Wayback Machine, для ядра Linux включает реализацию этой формулы.

• Протокол максимального приоритета расширяет протокол наследования базового приоритета, назначая каждому семафору максимальный приоритет , который является приоритетом самого высокого задания, которое когда-либо будет иметь доступ к этому семафору. Задание не может вытеснить критический раздел с более низким приоритетом, если его приоритет ниже максимального приоритета для этого раздела. Этот метод предотвращает взаимоблокировки и ограничивает время блокировки не более чем длиной одного критического раздела с более низким приоритетом. Этот метод может быть неоптимальным, поскольку может вызвать ненужную блокировку. Протокол потолка приоритета доступен в VxWorks ядре реального времени . Он также известен как протокол наивысшего приоритета шкафчика (HLP).

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

	пессимистичный	оптимистичный
немедленный	OS_ENTER_CRITICAL() / OS_EXIT_CRITICAL()	splx(), самый высокий шкафчик
ленивый		протокол потолка приоритета, протокол наследования базового приоритета

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

Пример использования базового наследования приоритетов связан с « Mars Pathfinder ». ошибкой сброса что было исправлено на Марсе путем изменения флагов создания семафора, чтобы включить наследование приоритета.

Подпрограммы обслуживания прерываний

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

Смягчение ISR с неправильным приоритетом

Одним из методов уменьшения неправильного приоритета ISR является корректировка анализа путем сокращения периода ISR, чтобы он был равен периоду самого короткого периода, если это возможно. Введение этого более короткого периода приводит к установлению приоритетов, которые соответствуют RMS, но также приводят к более высокому коэффициенту использования для ISR и, следовательно, для общего коэффициента использования, который все еще может быть ниже допустимой границы, и, следовательно, можно доказать возможность планирования. В качестве примера рассмотрим аппаратный ISR, время вычисления которого равно ${C_{isr}}$ 500 микросекунд и период, ${T_{isr}}$, 4 миллисекунды. Если самая короткая задача, управляемая планировщиком, имеет период, ${T_{1}}$ Если значение составляет 1 миллисекунду, то ISR будет иметь более высокий приоритет, но более низкую скорость, что нарушает RMS. Для доказательства планируемости положим ${T_{isr}}={T_{1}}$ и пересчитать коэффициент использования для ISR (что также повышает общий коэффициент использования). В этом случае, ${U_{isr}}{=}{C_{isr}}/{T_{isr}}$ изменится с ${0.5ms}/{4ms}{=}0.125$ к ${0.5ms}/{1ms}{=}0.5$. Этот коэффициент использования будет использоваться при сложении общего коэффициента использования набора задач и сравнении с верхней границей для подтверждения возможности планирования. Следует подчеркнуть, что настройка периода ISR предназначена только для анализа и что истинный период ISR остается неизменным.

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

Примеры

Пример 1

Процесс	Время расчета C	Период выпуска Т
П1	1	8
П2	2	5
П3	2	10

В рамках RMS P2 имеет самую высокую скорость выпуска (т.е. самый короткий период выпуска) и поэтому будет иметь самый высокий приоритет, за ним следует P1 и, наконец, P3.

граница

Использование будет: ${\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725$.

Достаточное условие для $3\,$ Процессы, из которых можно сделать вывод, что система является планируемой, это:

$${U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976>0.693\ldots (0.693{\text{ is utilization bound for RMS for }}n=\infty \ldots )$$

Потому что $0.77976\geq 0.725$, а поскольку наличие ниже наименьшей верхней границы является достаточным условием, система гарантированно будет планируемой.

Пример 2

Процесс	Время расчета C	Период выпуска Т
П1	3	16
П2	2	5
П3	2	10

При RMS P2 имеет самую высокую скорость (т.е. самый короткий период) и, следовательно, будет иметь самый высокий приоритет, за ним следует P3 и, наконец, P1.

граница

Используя границу Лю и Лейланда, как в примере 1, достаточное условие для $3\,$ процессов, при которых можно сделать вывод о планируемости поставленной задачи, остается:

$${U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976$$

Общий объем использования составит: ${\frac {3}{16}}+{\frac {2}{5}}+{\frac {2}{10}}=0.7875$.

С $0.77976{<}0.7875$ определено, что система не может быть гарантированно запланирована с помощью границы Лю и Лэйланда.

Гиперболическая граница

Используя более жесткую гиперболическую границу следующим образом:

$\prod _{i=1}^{n}(U_{i}+1)=({\frac {3}{16}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10}}+1)=1.995\leq 2$

обнаружено, что набор задач является планируемым.

Пример 3

Процесс	Время расчета C	Период выпуска Т
П1	7	32
П2	2	5
П3	2	10

При RMS P2 имеет самую высокую скорость (т.е. самый короткий период) и, следовательно, будет иметь самый высокий приоритет, за ним следует P3 и, наконец, P1.

граница

Используя границу Лю и Лейланда, как в примере 1, достаточное условие для $3\,$ процессов, при которых можно сделать вывод о планируемости поставленной задачи, остается:

$${U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976$$

Общий объем использования составит: ${\frac {7}{32}}+{\frac {2}{5}}+{\frac {2}{10}}=0.81875$.

С $0.77976{<}0.81875$ определено, что система не может быть гарантированно запланирована с помощью границы Лю и Лэйланда.

Гиперболическая граница

Используя более жесткую гиперболическую границу следующим образом:

$\prod _{i=1}^{n}(U_{i}+1)=({\frac {7}{32}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10}}+1)=2.0475$

С $2.0{<}2.0475$ определено, что система не может быть гарантированно запланирована с помощью гиперболической границы.

задач

Потому что ${T_{3}}={2{T_{2}}}$, задачи 2 и 3 можно рассматривать как гармоническое подмножество задач. Задача 1 образует собственное подмножество гармонических задач. Следовательно, количество подмножеств гармонических задач K равно 2 .

$${U_{lub,harmonic}}=K(2^{\frac {1}{K}}-1)=2(2^{\frac {1}{2}}-1)=0.828$$

Используя рассчитанный выше общий коэффициент использования (0,81875), поскольку $0.81875<0.828$ система определена как планируемая.

См. также

• Дедлайн-монотонное планирование
• Deos — операционная система реального времени, разделенная во времени и пространстве, содержащая работающий монотонный планировщик скорости.
• Динамическое планирование приоритетов
• Первое планирование самого раннего срока
• RTEMS , операционная система реального времени с открытым исходным кодом, содержащая работающий планировщик монотонной скорости.
• Планирование (вычисления)
• Теория массового обслуживания
• Формула Кингмана

Дальнейшее чтение

• Бутаццо, Джорджио (2011), Вычислительные системы жесткого реального времени: алгоритмы и приложения предсказуемого планирования , Нью-Йорк, Нью-Йорк: Springer .
• Алан Бернс и Энди Веллингс (2009), Системы реального времени и языки программирования (4-е изд.), Аддисон-Уэсли, ISBN  978-0-321-41745-9
• Лю, Джейн В.С. (2000), Системы реального времени , Аппер-Сэддл-Ривер, Нью-Джерси: Прентис-Холл , Глава 6.
• Джозеф, М.; Пандия, П. (1986), «Определение времени отклика в системах реального времени», BCS Computer Journal , 29 (5): 390–395, doi : 10.1093/comjnl/29.5.390 .
• Ша, Луи; Гуденаф, Джон Б. (апрель 1990 г.), «Теория планирования в реальном времени и Ada», IEEE Computer , 23 (4): 53–62, doi : 10.1109/2.55469 , S2CID   12647942

Внешние ссылки

• Ошибка Mars Pathfinder от исследования @ Microsoft
• Что на самом деле произошло на марсоходе Pathfinder, автор Майк Джонс из The Risks Digest, Vol. 19, Выпуск 49
• [1] Фактическая причина ошибки Mars Pathfinder, указанная теми, кто действительно имел с ней дело, а не кем-то, чья компания и, следовательно, стоимость акций зависели от описания проблемы, или кем-то, кто слышал, как кто-то говорил о проблеме.