Скоростно-монотонное планирование - Rate-monotonic scheduling

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

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

Вступление

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

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

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

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

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

куда C_я время вычислений, Т_я - период выпуска (с крайним сроком на один период позже), и п - количество процессов, которые нужно запланировать. Например, U ≤ 0,8284 для двух процессов. Когда количество процессов стремится к бесконечность, это выражение будет иметь тенденцию к:

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

Таким образом, по приблизительным оценкам RMS может уложиться в все сроки, если загрузка ЦП составляет менее 69,32%. Остальные 30,7% ЦП можно выделить для задач с более низким приоритетом, не работающих в режиме реального времени. Известно, что случайно сгенерированная система периодических задач будет соответствовать всем срокам, когда загрузка составляет 85% или меньше,^[3] однако этот факт зависит от знания точной статистики задачи (периоды, крайние сроки), которая не может быть гарантирована для всех наборов задач.

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

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

куда U_я - загрузка ЦП для каждой задачи.

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

Как избежать инверсии приоритета

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

Отключение приоритетного обслуживания

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

Приоритетное наследование

• В протокол наследования базового приоритета^[7] повышает приоритет задачи, удерживающей ресурс, до приоритета задачи, которая запрашивает этот ресурс во время запроса. После освобождения ресурса исходный уровень приоритета перед продвижением восстанавливается. Этот метод не предотвращает взаимоблокировки и страдает от цепная блокировка. То есть, если задача с высоким приоритетом обращается к нескольким совместно используемым ресурсам последовательно, ей, возможно, придется ждать (блокировать) задачу с более низким приоритетом для каждого из ресурсов.^[8] В патч в реальном времени к Ядро Linux включает реализацию этой формулы.^[9]

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

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

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

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

Пример использования наследования базового приоритета связан с "Марс-следопыт сбросить ошибку " ^[12][13] что было исправлено на Марсе путем изменения флагов создания для семафора, чтобы включить наследование приоритета.

Пример

Процесс	Время исполнения	Период
P1	1	8
P2	2	5
P3	2	10

Утилизация будет: ${\displaystyle {\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725}$.

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

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

.

С ${\displaystyle 0.77976>0.693\ldots }$ система может быть или не планироваться.

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

Для задания гармоник можно использовать формулу Ei / Pi <1.

Смотрите также

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

Рекомендации

1. Лю, К. Л.; Лейланд, Дж. (1973), "Алгоритмы планирования для мультипрограммирования в среде жесткого реального времени", Журнал ACM, 20 (1): 46–61, CiteSeerX  10.1.1.36.8216, Дои:10.1145/321738.321743.
2. Bovet, Daniel P .; Чезати, Марко, Понимание ядра Linux, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 В архиве 2014-09-21 на Wayback Machine.
3. Lehoczky, J .; Sha, L .; Динг, Ю. (1989), "Алгоритм планирования с монотонной скоростью: точная характеристика и поведение среднего случая", Симпозиум IEEE по системам реального времени, стр. 166–171, Дои:10.1109 / REAL.1989.63567, ISBN  978-0-8186-2004-1.
4. Энрико Бини, Джорджио К. Бутаццо и Джузеппе М. Бутаццо (2003), "Монотонный анализ скорости: гиперболическая граница", Транзакции IEEE на компьютерах, 52 (7): 933–942, Дои:10.1109 / TC.2003.1214341
5. Leung, J. Y .; Уайтхед, Дж. (1982), "О сложности планирования с фиксированным приоритетом периодических задач в реальном времени", Оценка эффективности, 2 (4): 237–250, Дои:10.1016/0166-5316(82)90024-4.
6. Алан Бернс и Энди Веллингс (2009), Системы реального времени и языки программирования (4-е изд.), Addison-Wesley, стр. 391, 397, ISBN  978-0-321-41745-9
7. Лэмпсон, Б.В.; Ределл, Д. Д. (1980), "Опыт работы с процессами и мониторами в Мезе", Коммуникации ACM, 23 (2): 105–117, CiteSeerX  10.1.1.46.7240, Дои:10.1145/358818.358824.
8. Бутаццо, Джорджио (2011), Вычислительные системы жесткого реального времени: алгоритмы и приложения прогнозируемого планирования (Третье изд.), Нью-Йорк, Нью-Йорк: Springer, стр. 225
9. "Linux вики реального времени". kernel.org. 2008-03-26. Получено 2014-03-14.
10. Sha, L .; Rajkumar, R .; Lehoczky, J. P. (1990), "Протоколы наследования приоритетов: подход к синхронизации в реальном времени", Транзакции IEEE на компьютерах, 39 (9): 1175–1185, Дои:10.1109/12.57058.
11. Буттаццо, Джорджио (2011), Вычислительные системы жесткого реального времени: алгоритмы и приложения предсказуемого планирования (Третье изд.), Нью-Йорк, Нью-Йорк: Springer, стр. 212
12. http://research.microsoft.com/~mbj/Mars_Pathfinder/
13. http://anthology.spacemonkeys.ca/archives/770-Mars-Pathfinder-Reset-Bug.html

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

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

внешняя ссылка

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