Методы и алгоритмы статического конфигурирования и диспетчеризации во встроенных синхронных системах жесткого реального времени

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

Современные технологичные производства представляют собой комплексные системы, состоящие из большого числа сложных подсистем, каждая из которых содержит сотни различных компонент. Для обеспечения необходимых для современных производств технологических и экономических показателей, все эти компоненты в комплексе должны слаженно и надёжно работать. При этом, на сегодняшний момент, одним из условий достижения необходимых показателей является применение в производстве компьютерных систем реального времени [1].

Одними из важнейших требований, предъявляемых к современным системам реального времени являются предсказуемость и надёжность (устойчивость к ошибкам времени исполнения). Известно, что для широкого круга задач, наиболее удовлетворяющими этим требованиям являются системы синхронного типа, предложенные к использованию учёными Венского Технического Университета [2]. В настоящие время европейским автомобильным консорциумом разрабатывается набор документов [3] - [5], определяющих стандард для встроенных систем жёсткого реального времени синхронного типа приминительно к автоt мобильной промышленности.

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

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

Задачи исследования. Для осуществления поставленной цели в диссертационной работе поставлены и решены следующие задачи:

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

2. Разработка методов диспетчеризации и моделей динамических планировщиков для операционных систем синхронного типа;

3. Разработка алгоритма оценки выполнимости приложений с помощью предложенных методов диспетчирования для случая не-вытесняемых задач;

4. Определение области применимости разработанных методов диспетчеризации для выполнения невытесняемых приложений;

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

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

Новые научные результаты. Научная новизна диссертационной работы состоит:

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

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

3. в разработанном алгоритме оценки выполнимости невытесня-емого двоично-ранжированного приложения (в общем случае оценка выполнимости множества невытесняемых задач является iVP-полной проблемой, сложность же разработанного алгоритма эквивалентна 0(N), где N — число задач в приложении), и проведённой экспериментальным путём (на основе разработанного алгоритма) оценке применимости ритмической диспетчеризации для выполнения невытесняемых двоично-ранжированных задач;

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

Апробация работы. Основные теоретические и практические положения диссертации были доложены:

1. На ежегодных научно-технических конференциях корпорации Моторола (Motorola Software Engineering Symposium), Phoenix, Arizona, USA, 2000 — 2001 гг.

2. На 25-й международной конференции компьютерного прогам-много обеспечения и приложений (25th Annual International Computer Software & Applications Conference, IEEE Computer Society), Chicago, Illinois, USA, 08.10 — 12.10.2001 r.

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

1. В. В. Никифоров, М. В. Перевозчиков. Ранжирование периодов задач в системах реального времени. II Программные продукты и системы, МНИИПУ 1999, № 4, с. 16 — 20.

2. М. В. Перевозчиков. Оптимизация общего периода выполнения приложения во встроенных системах реального времени. II Программные продукты и системы, МНИИПУ 1999, № 4, с. 20 -23.

3. Ya. Domaratsky, М. Perevozchikov. Highly Dependable Time-Triggered Operating System: Static Scheduling Approach and Effective.

Run-Time Implementation (Восоконадёжная синхронная операционная система: подход к статическому планированию и эффективная реализация динамической части). // Dedicated Systems Magazine, Dedicated Systems Experts, Brussels, Q4 2000, pp. 77 -84.

4. M. В. Перевозчиков, Я. А. Домарацкий, А. А. Альховик. Эффективное конфигурирование приложений во встроенных системах реального времени. II Программные продукты и системы, МНИИПУ 2000, № 4, с. 25 — 29.

5. Ya. Domaratsky, М. Perevozchikov, A. Ingulets, A. Alkhovik. BackEnd Software for Highly Dependable Real-Time Control Systems. (Встроенное программное обеспечение для высоконадёжных систем управления реального времени). // Proc. of 25th Annual International Computer Software & Applications Conference «COMP-SAC'01», IEEE Computer Society, October 2001, Chicago, Illinois, USA, pp. 237 — 244.

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав с выводами, заключения, списка литературы, включающего 89 наименований, и четырёх приложений. Основная часть работы изложена на 111 страницах машинописного текста. Работа содержит 17 рисунков и 15 алгоритмов.

4.5 Выводы к четвёртой главе.

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

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

106 наихудшее и наилучшее время выполнения заданий равны. Тогда данный метод теоретически может сцепить все выполняющиеся задания в одну чепочку. В этом случае в системе вообще не будет происходить переключение контекстов и, таким образом, будет достигнута макисмальная производительность. Однако и для другого предельного случая (когда информация о наихудших временах исполнения неизвестна, и необходимо исходить из их нулевых значений) данный метод позволяет по крайней мере вдвое сократить число переключений контекстов (например, для системы из [88]).

Дополнительно, в данной главе описан пример использования метода сцепления заданий для диспетчеризации двоично-ранжированных задач с нулевыми фазами активаций. Объединение этих двух методов позволяет, с одной стороны, использовать неявную форму представления статического графика, позволяющую существенно сократить используемую память, и, с другой стороны, обеспечить постоянное время системного цикла, не зависящее от числа задач в системе. Таким образом достигается эффективное с точки зрения производительности и требуемой памяти решение для диспетчеризации приложения для встроенной ОСРВ синхронного типа.

Заключение

.

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

Во второй главе данной работы описывается метод решения проблемы физической ограниченности доступного объёма памяти для представления статического графика активаций. В этой главе введена нотация значений допусков на величину периодов исполнения задач и разработан метод оптимизации общего периода функционирования приложения, использующий возможность изменения действительного значения периода задачи в пределах его допусков. Данный метод позволяет при введении даже небольших допусков существенно сократить общий период выполнения приложения, а значит и размер памяти, необходимой для его представления. Наиболее благоприятным случаем для данного метода оптимизации является набор задач, среди периодов которых существуют такие, величины которых являются взаимнопрос-тыми числами. Например, для системы из [78] введение допуска величиной всего в 5% позволяет сократить общий период функционирования приложения более чем в 40 раз.

В главе описаны два алгоритма оптимизации. Первый быстрый сложности 0(iV2) алгоритм поиска оптимального в простом смысле значения общего периода функционирования приложения может применяться только для приложений с относительно небольшой загрузкой процессора. Действительная величина этой загрузки в каждом конкретном случае определяется величинами допусков на значения периодов задач. Критерий применимости данного алгоритма описывается соотношением (2.14). Второй алгоритм последовательного приближения при поиске оптимального в расширенном смысле значения общего периода функционирования приложения учитывает время выполнения заданий, и, поэтому, может быть применён для приложений с загрузкой процессора вплоть до 100%.

Третья глава посвящена методам ранжирования приложений. В ней описаны двоичное и кратное ранжирование задач. Основными достоинствами ранжированных приложений являются следующие их свойства:

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

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

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

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

Второй метод строит двоично-ранжированное множество задач исходя из временных ограничений, специфицированных пользователем для каждой конкретной задачи (величины номинального периода и его допусков). Данный метод похож на подход к отысканию оптимального в простом смысле значения общего периода функционирования приложения, описанного в Главе 2, и также реализуется с помощью алго2 ритма сложности 0(N).

Также в данной главе описаны два типа диспетчеров -— с нулевыми фазами активации и ритмический диспетчер. Преимущество ритмического диспетчера перед диспетчером с нулевыми фазами в том, что время его нахождения в системном цикле не зависит от числа рангов в приложении. Другим важным свойством ритмической диспетчеризации является то, что она является эффективным методом планирования двоично-ранжированных невытесняемых задач. В главе приведены результаты проведённых статистических исследований области применимости ритмической диспетчеризации для планирования невытесняемых задач, которые показывают, что вероятность выполнимости двоично-ранжированного множества невытесняемых задач для случая монолитных рангов близка к 1 при загрузке процессора вплоть до 70% (на выборке из 100 000 проб для приложения из 10 рангов при загрузке.

70% вероятность выполнимости составила -0.996), и всегда равна 1 для приложения, содержащего не больше трёх двоичных рангов.

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

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

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

Ill емую память, и, с другой стороны, обеспечить постоянное время диспетчеризации, не зависящее от числа задач (рангов) в системе. Таким образом достигается эффективное с точки зрения производительности и требуемой памяти решение для диспетчеризации приложения для встроенной ОСРВ синхронного типа, поскольку метод сцепления задания обеспечивает в худшем случае 2N +1 (где N — число двоичных рангов в системе) переключений контекстов на общем периоде функционирования приложения вне зависимости от числа задач в приложении.

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

Перечень иллюстраций.

Рис. 2.1 Множество допустимых значений общего периода функционирования приложения для задачи с номинальным периодом 7 и допуском +/- 1. 39.

Рис. 2.2 Схема отыскания оптимального в простом смысле значения общего периода функционирования приложения. 41.

Рис. 2.3 Зависимость величины действительного периода задачи от значения общего периода функционирования приложения. 45.

Рис. 3.1 Множество допустимых значений базового временного интервала для задачи с периодом 27 и допуском +/— 4. 59.

Рис. 3.2 Диаграмма активации двоичных рангов с нулевыми смещениями. 63.

Рис. 3.3 Диаграмма ритмической активации двоичных рангов. 65.

Рис. 3.4 Параметры алгоритма анализа выполнимости набора невытесняемых двоично-ранжированных задач. 68.

Рис. 3.5 Сумма времени выполнения пакета (/ - 1)-го ранга и задач /-го ранга не превышают величину периода (/ - 1)-го ранга. 69.

Рис. 3.6 Сумма времени выполнения пакета (/ - 1)-го ранга и задач /-го ранга превышают периода (/ — 1)-го ранга не больше чем на величину его пороговой зедержки. 70.

Рис. 3.7 Сумма времени выполнения пакета (/ - 1)-го ранга и задач /-го ранга превышают периода (/ - 1)-го ранга больше чем на величину его пороговой зедержки. 71.

Рис. 3.8 Область распределения А^-мерной случайной величины. 74.

Рис. 3.9 Результаты экспериментов для множества невытесняемых двоично-ранжированных задач в случае монолитных рангов. 76.

Рис. 3.10 Результаты экспериментов для сбаллансированного множества невытесняемых двоично-ранжированных монолитных рангов. 77.

Рис. 3.11 Временная диграмма активации кратных рангов с нулевыми смещениями. 79.

Рис. 4.1 Пример работы стекового диспетчера. 83.

Рис. 4.2 Схема активации задач цепочками. 86.

Рис. 4.3 Модель накладных расходов диспетчера. 90.

Перечень алгоритмов.

Алг. 2.1 Быстрый алгоритм отыскания оптимального в простом смысле значения общего периода функционирования приложения. 43.

Алг. 2.2 Алгоритм последовательного приближения для отыскания оптимального в расширенном смысле значения ESOP. 49.

Алг. 3.1 Алгоритм определения области допустимых значений базового временного интервала. 60.

Алг. 3.2 Диспетчер для множества двоично-ранжированных задач с нулевыми фазами активации. 62.

Алг. 3.3 Ритмический диспетчер. 64.

Алг. 3.4 Алгоритм анализа выполнимости набора невытесняемых двоично-ранжированных задач в случае монолитных рангов. 72.

Алг. 3.5 Алгоритм генерирования случайной равномерно распределённой загрузки процессора по рангам. 74.

Алг. 3.6 Алгоритм диспетчеризации кратных рангов с нулевыми фазами активации. 79.

Алг. 4.1 Алгоритм проверки Критерия I. 97.

Алг. 4.2 Алгоритм вычисления времени актвиации задачи в соответствии с Критерием II. 99.

Алг. 4.3 Алгоритм добавления задачи в существующую цепочку. 100.

Алг. 4.4 Алгоритм создания новой цепочки. 100.

Алг. 4.5 Алгоритм обновления временных параметров после изменения или добавления цепочки. 101.

Алг. 4.6 Алгоритм статического планирования. 104.

Алг. 4.7 Диспетчер для множества двоично-ранжированных задач с нулевыми фазами активации со сцеплением заданий. 105.