ИССЛЕДОВАНИЕ АЛГОРИТМОВ ПЛАНИРОВАНИЯ RMS, EDF, LLF В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

АННОТАЦИЯ

В данной работе рассмотрены алгоритмы планирования: RMS, EDF, LLF.  Целью данной работы является изучение, анализ и сравнение алгоритмов планирования, выявления их преимуществ и недостатков. В ходе исследования было выявлено, что при перегрузке процессора алгоритм RMS показал самые плохие результаты и время работы системы не превышает одного периода. Также было рассмотрено две вариации работы алгоритма EDF. Рассмотрена проблема выбора задач с одинаковым минимальным резервом для алгоритма LLF. Выявлено, что при выборе задачи с наименьшим порядковым номером ситуация «deadlock» возникает позже или совсем не возникает.

Ключевые слова: системы реального времени, статический алгоритм планирования, динамический алгоритм планирования, RMS, EDF, LLF, планировщик СРВ.

Введение

Система реального времени (СРВ) – это система, время отклика которой на внешние события настолько мало, что она может изменять ход этих событий [1]. Основной целью планирования в СРВ является выполнение процессов за заранее определённый интервал времени. Для того, чтобы это сделать необходимо выстроить задачи в такой последовательности, при которой все задачи будут исполняться за отведенное им время. Для построения таких последовательностей используют алгоритмы планирования СРВ. Целью данной работы является изучение, анализ и сравнение алгоритмов планирования, выявления их преимуществ и недостатков. Результаты исследований могут быть использованы при разработке различных систем реального времени. А именно отдать предпочтение тому или иному алгоритму, который является более подходящим для разрабатываемой системы.

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

Существуют два типа алгоритмов – статический (с фиксированным назначением приоритетов задач) и динамический (с изменяемыми приоритетами).

Рассматриваемые алгоритмы обладают следующими свойствами:

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

Наиболее важным динамическим алгоритмом является алгоритм EDF (Earliest Deadline First). Наибольший приоритет имеет та, еще не завершенная задача, для которой ближе всего очередная точка запуска. Если две задачи имеют одинаковые предельные сроки, то задача на исполнение может быть выбрана случайным образом. Приоритет является динамическим, поскольку он изменяется в течении работы алгоритма для одной задачи. Существует две разновидности этого алгоритма: EDF - без вытеснения и с вытеснением задач. Их главное отличие в том, что если в систему поступила задача с более высоким приоритетом, т.е. с ранним крайним сроком, то в случае работы системы по алгоритму EDF c вытеснением задач, исполняемая задача прервется и начнется исполняться поступившая задача, а в случае EDF без вытеснения текущая задача продолжит работу, а только после ее завершения поступившая задача займет процессор. Запуск алгоритма EDF (точка планирования) возникает каждый раз при завершении очередной задачи или переходе какой-либо задачи в состояние готовности.

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

Алгоритм RMS (Rate Monotonic Scheduling) является классическим примером алгоритма со статическим назначением приоритетов. Он используется как для периодических, так и для апериодических задач. Алгоритм RMS назначает приоритет задачи обратно пропорционально её периоду, а именно чем меньше период задачи, тем выше её приоритет.

Свойства алгоритма RMS [2]:

• задаче требуется равное процессорное время на каждом периоде;
• приоритеты у всех задач постоянны и различны;

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

Для проведения исследований была разработана программа «Имитатор планировщика задач СРВ». Имитатор поддерживает планирование задач по всем вышеупомянутым алгоритмам. Результатом планирования является временная диаграмма, на которой отображается поэтапное планирование по выбранному алгоритму. В имитаторе рассматривается самая тяжелая ситуация для процессора, когда каждая задача будет работать всё указанное для неё время.

Имитатор планировщика разработан на языке C# с использованием библиотеки LiveCharts. Интерфейс программы представляет собой область «Параметры задач», область «Параметры алгоритма планирования» и область отображения результатов планирования в виде временной диаграммы. В области «Параметры задач» задается время работы и период запуска для каждой задачи. В области «Параметры алгоритма планирования» выбирается алгоритм планирования, а также задается время планирования.

С помощью имитатора планировщика были проведены исследования алгоритмов планирования. Целью первого эксперимента было выяснить поведение рассматриваемых алгоритмов при перегрузках. Методика эксперимента: подбиралась такая группа задач, чтобы суммарная загрузка процессора превышала 100%. Нагрузка процессора рассчитывается по формуле:

                                                     (1)

где:   – время выполнения i-ой задачи, мс;

 – период запуска i-ой задачи, мс.

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

На вход имитатора планировщика подавалась группа задач с заданными для каждой задачи параметрами – временем выполнения и периодом запуска. Результатом планирования является временная диаграмма, на которой отображается ход планирования по выбранному алгоритму, а также время работы системы. В эксперименте рассматриваются алгоритмы RMS, EDF без вытеснения задач (EDF1), EDF с вытеснением задач (EDF2), LLF. Ниже (таблица 1) приведены некоторые результаты эксперимента.

Таблица 1.

Результаты первого эксперимента

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

Целью второго эксперимента было сравнение результатов работы двух разновидностей алгоритма EDF. На вход имитатора планировщика подавались группы задач с различным коэффициентом загрузки процессора от 0.558 до 0,975. Результатом планирования является временная диаграмма, на которой отображается ход планирования по выбранному алгоритму. Из полученных временных диаграмм было выявлено, что оба варианта алгоритма ведут себя одинаково (за исключением некоторых ситуаций, которые не влияют на ход планирования) при разной загруженности процессора. Из этого можно сделать вывод, что на краткосрочном промежутке времени для реальных систем алгоритм EDF без вытеснения будет эффективнее, так как не будет временных затрат на прерывание задач.

Целью третьего эксперимента было решение проблемы выбора задачи с одинаковым резервом для алгоритма LLF. В некоторых случаях в алгоритме LLF возникает ситуация, когда в ходе планирования у нескольких задач резерв, который является определяющим в выборе приоритетной задачи, одинаковый и он является минимальным. Тогда возникает проблема выбора следующей задачи для планирования. В исследовании было рассмотрено два варианта решения этой проблемы. Первое решение (LLF1) – при возникновении такой ситуации процессорное время предоставляется задаче с наименьшим порядковым номером, резерв которой является минимальным. Второе решение данной проблемы (LLF2) – произвольный выбор задач из задач с наименьшим резервом.

Были подобраны такие группы задач, в которых наблюдалась ситуация выбора между задачами с одинаковым наименьшим резервом. Имитатору планировщика задач подавалась эта группа задач и фиксировалось время работы системы до возникновения ситуации «deadlock». Имитатор работал с учетом первого способа решения проблемы, а потом на этих же данных, но уже с учетом второго способа. Некоторые результаты эксперимента приведены ниже (таблица 2).

Таблица 2.

Результаты третьего эксперимента

Результаты эксперимента показали, что при решении проблемы первым способом, ситуация «deadlock» возникает позже или совсем не возникает, чем при решении проблемы вторым способом.

Заключение

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

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

Было рассмотрено несколько способов решения проблем выбора задач с одинаковым резервом для алгоритма LLF. Выявлено, что при решении этой проблемы, путем выбора задачи с наименьшим порядковым номером, система показывает лучшие результаты и ситуация «deadlock» возникает позже или вообще не возникает.

Список литературы:

1. Блэкман, М. Проектирование систем реального времени. М.: Издательство «Мир», 1977. – 356 с.
2. Кобылянский, В. Г. Системы реального времени: учеб. пособие. Новосибирск: Изд-во НГТУ, 2015. – 84 с.
3. Laplante, Phillip A. Real-time systems design and analysis / Phillip A. Laplante, Seppo J. Ovaska. – Canada : the Institute of Electrical and Electronics Engineers, 2012. – 571 с.