Введение

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

Введение

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

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

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

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

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

Минимальный верхний предел

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

где U – коэффициент загрузки, Ci – время вычисления для задачи i, Ti – период выпуска (с дедлайном, наступающим через один период) для задачи i, а n – количество планируемых задач. Например, U ≤ 0,8284 для двух задач. При стремлении количества задач к бесконечности это выражение стремится к:

Следовательно, приблизительная оценка заключается в том, что RMS может гарантировать выполнение всех дедлайнов, если общая загрузка процессора, U, меньше 70%. Оставшиеся 30% процессорного времени можно выделить для задач с более низким приоритетом, не относящихся к задачам реального времени. Для небольших значений n или в случаях, когда U близко к этой оценке, следует использовать вычисленный порог загрузки. На практике для задачи Ci должно представлять собой худший случай (то есть максимальное) время вычисления, а Ti – худший случай дедлайна (то есть минимальный период), в течение которого должна быть выполнена вся обработка.

Верхняя граница для гармонических задач

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

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

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

Обмен ресурсами

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

Отключение преимущественного права

Примитивы OS ENTER CRITICAL и OS EXIT CRITICAL, которые блокируют прерывания ЦП в ядре реального времени, например, MicroC/OS II, а также семейство примитивов splx, обеспечивающих вложенное блокирование прерываний устройств (FreeBSD 5.x/6.x).

Перерыв в служении

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

Снижение неправильно расставленных приоритетов

Один из способов смягчения ситуации с неправильно расставленными приоритетами ИСР заключается в корректировке анализа путем уменьшения периода ИСР до периода самой короткой задачи, если это возможно. Наложение этого более короткого периода приводит к приоритетизации, соответствующей RMS, но также увеличивает коэффициент загрузки для ИСР и, следовательно, для общей загрузки системы, которая все еще может быть ниже допустимого предела, что позволяет доказать планируемость. В качестве примера рассмотрим аппаратный ИСР с временем вычисления 500 микросекунд и периодом 4 миллисекунд. Если самая короткая задача, управляемая планировщиком, имеет период 1 миллисекунду, то ИСР получит более высокий приоритет, но меньшую частоту, что нарушает правила RMS. Для целей доказательства планируемости установите период ИСР равным 1 миллисекунде и пересчитайте коэффициент загрузки для ИСР (что также увеличит общую загрузку системы). В этом случае период изменится с 4 миллисекунд на 1 миллисекунду. Этот коэффициент загрузки будет использоваться при суммировании общей загрузки системы для набора задач и сравнении с верхней границей для доказательства планируемости. Важно подчеркнуть, что корректировка периода ИСР выполняется только для целей анализа, а фактический период ИСР остается неизменным. Другой способ смягчения ситуации с неправильно расставленными приоритетами ИСР – использовать ИСР только для установки нового семафора/мьютекса, а ресурсоемкую обработку перенести в новый процесс, приоритет которого правильно установлен с использованием RMS и который будет блокироваться на новом семафоре/мьютексе. При определении планируемости от верхней границы допустимой загрузки следует вычесть резерв загрузки процессора, обусловленный активностью ИСР. ИСР с пренебрежимо малой загрузкой можно не учитывать.

Анализ гармонического набора задач

Поскольку задачи 2 и 3 можно рассматривать как подмножество гармоничных задач. Задача 1 формирует собственное подмножество гармоничных задач. Следовательно, количество подмножеств гармоничных задач, K, равно 2. Используя общий коэффициент загрузки, рассчитанный выше (0,81875), система признается планируемой.