Rate-Monotonic Scheduling

Rate-Monotonic Scheduling (RMS) — это алгоритм статического приоритетного планирования задач реального времени, в котором приоритет задачи обратно пропорционален её периоду: чем короче период, тем выше приоритет. Алгоритм был разработан в 1973 году американскими учёными Чаном Лью и Джеймсом Лейландом (Chung Laung Liu, James W. Layland) и впервые опубликован в статье «Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment». RMS является одним из наиболее распространённых методов планирования для систем с жёстким реальным временем, где нарушение сроков выполнения задач недопустимо.

Основные принципы

Приоритеты

В RMS каждой задаче присваивается фиксированный приоритет, который не изменяется во время выполнения системы. Приоритет определяется исключительно периодом задачи: задача с периодом 10 мс получает более высокий приоритет, чем задача с периодом 20 мс. В случае равенства периодов приоритет может назначаться произвольно, например, по порядку поступления или по идентификатору задачи.

Вытеснение

Алгоритм является вытесняющим (preemptive): если в момент выполнения задачи с низким приоритетом поступает задача с более высоким приоритетом, текущая задача немедленно приостанавливается, и процессор переключается на выполнение более приоритетной задачи. После завершения высокоприоритетной задачи выполнение прерванной задачи возобновляется с точки прерывания.

Модель задач

RMS предполагает, что все задачи удовлетворяют следующим условиям:

• Каждая задача является периодической, то есть выполняется с постоянным интервалом (периодом).
• Время выполнения задачи (worst-case execution time, WCET) известно и фиксировано.
• Задачи независимы друг от друга, то есть не имеют общих ресурсов или зависимостей по данным.
• Время переключения контекста пренебрежимо мало или учитывается как часть времени выполнения.
• Срок выполнения задачи (deadline) равен её периоду: задача должна завершиться до начала следующего периода.

Теорема о планируемости

Достаточное условие

Для набора из n периодических задач, упорядоченных по возрастанию периодов (T1 ≤ T2 ≤ ... ≤ Tn), с временами выполнения C1, C2, ..., Cn, RMS гарантирует выполнение всех задач в срок, если выполняется неравенство:

\[ \sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{1/n} - 1) \]

где \( \frac{C_i}{T_i} \) — загрузка процессора i-й задачей (utilization). Левая часть представляет собой суммарную загрузку процессора. Правая часть — это граница Лью и Лейланда (Liu and Layland bound), которая при n → ∞ стремится к ln 2 ≈ 0,693. Таким образом, при бесконечном числе задач максимальная гарантированная загрузка составляет около 69,3%.

Необходимое условие

Для планируемости набора задач необходимо, чтобы суммарная загрузка не превышала 1 (100% процессорного времени). Однако это условие не является достаточным: даже при загрузке менее 100% возможны пропуски сроков из-за несоответствия периодам.

Точное условие

Если достаточное условие не выполняется, планируемость можно проверить с помощью теста временного анализа (response time analysis). Для каждой задачи вычисляется время отклика R_i — максимальное время от начала периода до завершения задачи. Если для всех задач R_i ≤ T_i, то набор планируем. Метод основан на итеративном решении уравнения:

\[ R_i = C_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i}{T_j} \right\rceil C_j \]

где hp(i) — множество задач с приоритетом выше, чем у задачи i. Решение ищется, начиная с R_i = C_i, и повторяется до сходимости или превышения T_i.

Преимущества

• Простота реализации: приоритеты назначаются статически, что не требует сложных вычислений во время выполнения.
• Предсказуемость: поведение системы полностью детерминировано при известных параметрах задач.
• Эффективность для малых наборов: при малом числе задач граница планируемости близка к 100% (например, для двух задач — 82,8%).
• Широкая поддержка: RMS реализован во многих операционных системах реального времени, таких как FreeRTOS, VxWorks, QNX.

Недостатки

• Ограниченная загрузка: при большом числе задач максимальная гарантированная загрузка составляет около 69,3%, что ниже, чем у некоторых других алгоритмов (например, Earliest Deadline First — EDF, который может достигать 100%).
• Чувствительность к перегрузке: при превышении границы планируемости возможны каскадные сбои, когда одна задача, не уложившаяся в срок, блокирует выполнение других.
• Непригодность для апериодических задач: RMS не предназначен для задач с нерегулярными периодами или спорадических задач; для них требуется модификация, например, серверы задач (sporadic servers).
• Зависимость от точности WCET: если время выполнения задачи превышает заложенное WCET, планируемость может нарушиться.

Применение

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

• Авионика: системы управления полётом, автопилоты, бортовые вычислители.
• Автомобильная электроника: блоки управления двигателем (ECU), системы торможения (ABS), подушки безопасности.
• Медицинское оборудование: кардиостимуляторы, инфузионные насосы, аппараты ИВЛ.
• Промышленная автоматизация: программируемые логические контроллеры (ПЛК), робототехника.
• Телекоммуникации: коммутаторы, маршрутизаторы, базовые станции.

Сравнение с другими алгоритмами

Earliest Deadline First (EDF)

EDF — динамический алгоритм, где приоритет задачи определяется по ближайшему сроку выполнения. EDF может достигать 100% загрузки процессора, но требует более сложного планировщика и может быть менее предсказуемым при перегрузках. RMS проще в реализации и более устойчив к кратковременным перегрузкам, так как приоритеты фиксированы.

Deadline Monotonic Scheduling (DMS)

DMS — обобщение RMS, где приоритет назначается по сроку выполнения, а не по периоду. Для задач, у которых срок меньше периода, DMS может быть эффективнее, так как учитывает реальные дедлайны. RMS является частным случаем DMS при равенстве дедлайна и периода.

Пример работы

Рассмотрим две задачи:

• Задача A: период T_A = 10 мс, время выполнения C_A = 4 мс.
• Задача B: период T_B = 15 мс, время выполнения C_B = 3 мс.

Суммарная загрузка: 4/10 + 3/15 = 0,4 + 0,2 = 0,6 (60%). Граница для двух задач: 2(2^{1/2} - 1) ≈ 0,828. Так как 0,6 ≤ 0,828, набор планируем по достаточному условию.

Приоритеты: у задачи A период меньше, поэтому она получает более высокий приоритет. В начале периода (t=0) запускается задача A, выполняется 4 мс. В t=4 задача A завершена, запускается задача B, выполняется до t=7. В t=10 начинается новый период задачи A, она вытесняет задачу B (если та ещё выполняется), и так далее. Все сроки соблюдаются.

Критика

Основная критика RMS связана с его консервативной границей планируемости. В реальных системах часто встречаются наборы задач с загрузкой, превышающей 69,3%, но при этом планируемые благодаря специфике периодов (например, гармонические периоды, где один период кратен другому). В таких случаях граница Лью и Лейланда является излишне строгой. Кроме того, алгоритм предполагает независимость задач, что редко выполняется на практике: задачи могут использовать общие ресурсы (память, шины данных), что требует введения механизмов синхронизации, таких как протоколы наследования приоритетов (Priority Inheritance Protocol, PIP) или потолочного приоритета (Priority Ceiling Protocol, PCP), которые усложняют анализ.

Интересные факты

• В оригинальной работе 1973 года Лью и Лейланд доказали, что RMS является оптимальным статическим алгоритмом среди всех алгоритмов с фиксированными приоритетами: если какой-либо статический алгоритм может запланировать набор задач, то RMS также сможет.
• Граница планируемости n(2^{1/n} - 1) монотонно убывает с ростом n: для n=1 она равна 1, для n=2 — 0,828, для n=3 — 0,779, для n=4 — 0,756, для n=5 — 0,743, для n=10 — 0,717, для n=100 — 0,695.
• RMS часто используется в учебных курсах по операционным системам и встроенным системам как классический пример алгоритма реального времени.

Источники

• Liu, C. L., & Layland, J. W. (1973). Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the ACM, 20(1), 46–61.
• Buttazzo, G. C. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Springer.
• Klein, M. H., Ralya, T., Pollak, B., Obenza, R., & Harbour, M. G. (1993). A Practitioner’s Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Springer.
• Sha, L., Rajkumar, R., & Lehoczky, J. P. (1990). Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers, 39(9), 1175–1185.