Методы и алгоритмы статического конфигурирования и диспетчеризации во встроенных синхронных системах жесткого реального времени тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Перевозчиков, Максим Владимирович

• Перевозчиков, Максим Владимирович
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Перевозчиков, Максим Владимирович

Содержание.

Введение

Глава

Проблемы построения встроенных систем жёсткого реального времени и существующие пути их решения

1.1 Встроенные программные комплексы как системы реального времени

1.2 Предсказуемое поведение и надёжность программных систем реального времени.

1.3 Инструментальная и целевая части встроенной ОСРВ

1.4 Задачи и задания (экземпляры задач)

1.5 Методы планирования задач в системах реального времени

1.6 Временной анализ программных систем реального времени

1.7 Событийный и синхронный подходы к построению систем реального времени.

1.8 Проблемы построения и исполнения статических графиков.

1.9 Выводы к первой главе

Глава

Оптимизация общего периода функционирования приложения.

2.1 Оптимизация в простом смысле

2.2 Быстрый алгоритм оптимизации

2.3 Оптимизация в расширенном смысле

2.4 Выводы ко второй главе

Глава

Ранжирование задач

3.1 Двоично-ранжированное множество задач

3.2 Построение двоично-ранжированного набора задач

3.3 Диспетчеризация двоично-ранжированных задач.

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

3.5 Определение области применимости ритмической диспетчеризации для планирования невытесняемого набора двоично-ранжированных задач

3.6 Кратно-ранжированное множество задач

3.7 Выводы к третьей главе

Глава

Снижение накладных расходов ОСРВ

4.1 Схема сцепления заданий.

4.2 Модель накладных расходов диспетчера

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

4.4 Использование метода сцепления заданий для двоично-ранжированного множества задач

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

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

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

Современные технологичные производства представляют собой комплексные системы, состоящие из большого числа сложных подсистем, каждая из которых содержит сотни различных компонент. Для обеспечения необходимых для современных производств технологических и экономических показателей, все эти компоненты в комплексе должны слаженно и надёжно работать. При этом, на сегодняшний момент, одним из условий достижения необходимых показателей является применение в производстве компьютерных систем реального времени [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% (на выборке из 100000 проб для приложения из 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

113

Рис. 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

Список литературы диссертационного исследования кандидат технических наук Перевозчиков, Максим Владимирович, 2001 год

1. J. A. Stankovic. Real-Time Computing: A Critical Enabling Technology, University of Massachusetts, 1993

2. H. Kopetz, A. Damm, C. Koza, M. Mulazzani, W. Schwabl, C. Senft, R. Zainlinger. Distributed Fault-Tolerant Real-Time Systems: The MARS Approach, IEEE Micro, February 1989

3. OSEK/VDX — Time-Triggered Operating System, Specification Version 1.0, July 24th 2001

4. OSEK/VDX — Fault-Tolerant Communication, Specification Version 1.0, July 24th 2001

5. OSEK/VDX — OSEKtime Implementation Language, Specification Version 0.0.4, October 31st 2001

6. R. Davis. Dual Priority Scheduling: A Means of Providing Flexibility in Hard Real-Time Systems, University of York, 1995

7. J. A. Stankovic. Real-Time Computing, University of Massachusetts, April 1992

8. M. Humphrey, G. Wallace, J. A. Stankovic. Kernel-Level Threads for Dynamic, Hard Real-Time Enviroments, University of Massachusetts, May 1995

9. J. A. Stankovic, F. Wang. The Integration of Scheduling and Fault Tolerance in Real-Time Systems, University of Massachusetts, 1992

10. K. Jeff ay. Analysis of a Synchronization and Scheduling Discipline for Real-Time Tasks with Preemption Constraints, University of North Carolina at Chapel Hill, 1989

11. K. Jeff ay. Scheduling Sporadic Tasks with Shared Resources in Hard-Real-Time Systems, 13th IEEE Real-Time Systems Symposium, Phoenix, AZ, December 1992

12. D. Niehaus, J. A. Stankovic, K. Ramamritham. The Spring System Description Language, University of Massachusetts, February 1993

13. B. Allvin, K. Sandstrom, Ch. Eriksson. Constructive Feedback Turns Failure into Success for Pre-Run-Time Scheduled Systems, Malardalen Univesity, Sweden, August 1999

14. MCX11 — Microcontroller executive for the Motorola MC68HC11, Version 1.3, Barrett & Associates, Houston, April 1990

15. R. Gerber, S. Hong, M. Saksena. Guaranteeing Ent-to-End Timing Constraints by Calibrating Intermediate Processes, IEEE Real-Time Systems Symposium, December 1994

16. K. Ramamritham, J. A. Stankovic. Scheduling Algorithms and Operating Systems Support for Real-Time Systems, 1994

17. S. Chai, A. Agrawala. Scheduling Aperiodic and Sporadic Tasks in Hard Real-time Systems, Department of Computer Science, University of Maryland, 1997

18. J. Stankovic, M. Spuri, M. Di Natale, G. Buttazzo. Implication of Classical Scheduling Results for Real-Time Systems, vol. 28, № 6, 1994

19. J.-F. Hermant, L. Leboucher, N. Rivierre. Real-time fixed and dynamic priority driven scheduling algorithms: theory and experience, INRIA, research report № 3081, December 1996

20. D. Poirier, K. Jeffay. An Implementation and Application of the RealTime Producer/Concumer Paradigm, University of North Carolina at Chapel Hill, technical report №90-038, October 1990

21. B. Lamie. Preemption Threshold, Real-Time Magazine, №3, 1997

22. Y. Wang, M. Saksena. Scheduling Fixed-Priority Tasks with Preemption Threshold — An Attractive Technology? Concordia University Montreal, Canada, 2000

23. Ch. McElhone. Hybrid Algorithms for Dynamic Schedulability Testing, University of York, October 1994

24. К. Erciyes, Z. Soysert. A Multi-Level Task Allocation Scheme for Periodic Tasks of a Distributed Real-Time Systems, Ege University International Computing Institute, Turkey, 1996

25. L. Sha, M. H. Klein, J. B. Goodenough. Rate-Monotonic Analysis for Real-Time Systems, 1991

26. N. Audsley. Deadline Monotonic Scheduling, University of York, September 1990

27. A. Burns, К Tindell, A. J. Wellings. Fixed Priority Scheduling with Deadlines Prior to Completion, University of York, 1995

28. A. D. Ferrari. Real-Time Scheduling Algorithms. — Dr. Dobb's Journal, December 1994

29. M. Spuri. Analysis of Deadline Scheduled Real-Time Systems, INRIA, research report № 2772, January 1996

30. M. Spuri. Holistic Analysis for Deadline Scheduled Real-Time Distributed Systems, INRIA, research report № 2873, April 1996

31. R. Howell, S. Baruah, L. Rosier. Feasibility Problems for Recuring Tasks on One Processor, 11th Real-Time Systems Symposium, Lake Buena Vista, Florida, December 1990

32. K. Jeff ay, D. F. Stanat, C. U. Martel. On Non-Preemptive Scheduling of Periodic and Sporadic Tasks, 12th IEEE Real-Time Systems Symposium, Phoenix, AZ, December 1991

33. D. W. Gilles, J. W.-S. Liu, Scheduling Tasks with And/Or Precedence Constraints, University of Illinois, 1992

34. L. George, P. Muhlethaler, N. Rivierre. Optimality and non-preemptive real-time scheduling revisited, INRIA, research report № 2516, April 1995

35. R. Davis, K. Tindell, A. Burns Scheduling Slack Time in Fixed Priority Pre-emptive Systems, Real-Time System Symposium, December 1993

36. A. Burns. Pre-Emptive Priority Based Scheduling: An Appropriate Engineering Approach, University of York, 1995

37. L. George, N. Rivierre, M. Spuri. Preemptive and Non-Preemptive Real-Time Uni-Processor Scheduling, INRIA, research report № 2966, September 1996

38. D. Isovic, G. Fohler. Efficient Scheduling of Sporadic, Aperiodic, and Periodic Tasks with Complex Constraints, Malardalen Univesity, Sweden, November 2000

39. R. Howell, M. Venkatrao. On Non-Preemptive Scheduling of Recurring Tasks Using Inserted Idle Times, Kansas State University, 1994

40. M. Spuri, J. A. Stankovic. How to Integrate Precedence Constraints and Shared Resources in Real-Time Scheduling, University of Massachusetts, 1993

41. R. Gerber, S. Hong, M. Saksena. Guaraneeing Real-Time Requirements with Resource-Based Calibration of Periodic Processes, IEEE Transactions on Software Engineering, vol. 21, № 7, July 1995

42. S. K. Baruah, J. E. Gehrke, C. G. Plaxton, I. Stoica, H. Abdel-Wahab, K. Jeffay. Fair On-Line Scheduling of a Dynamic Set of Tasks on a Single Resource, 17th IEEE Real-Time Systems Symposium, December 1996

43. N. Audsley, A. Burns, M. Richardson, K. Tindell, A. J. Wellings. Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling, Software Engineering Journal, September 1993

44. K. Tindell. Adding Time-Offsets to Schedulability Analysis, University of York, 1995

45. K. Tindell. Using Offset Information to Analyse Static Priority PreEmptively Scheduled Task Sets, University of York, 1995

46. J. H. Anderson, S. Ramamurthy, K. Jeffay. Real-Time Computing with Lock-Free Shared Objects, University of North Carolina, 1997

47. N. Audsley, A. Burns. Real-Time System Scheduling, University of York, 1992

48. P. Puschner, A. Vrchoticky. An Assessment of Task Execution Time Analysis, Technische Universitat Wien, 1992

49. P. Puschner, Ch. Koza. Calculating the Maximum Execution Time of Real-Time Programs, Real-Time Systems, September 1989

50. R. Chapman. Worst-Case Timing Analysis via Finding Longest Paths in SPARK Ada Basic-Path Graphs, University of York, October 1994

51. P. Puschner, A. Schedl. Computing Maximum Task Execution Times — A Graph-Based Approach, Real-Time Systems, July 1997

52. P. Puschner, A. Vrchoticky. Problems in Static Worst-Case Execution Time Analysis, Technische Universitat Wien, 1998

53. N. Zhang, A. Burns, M. Nicholson. Pipelined Processors and Worst Case Execution Time, Real-Time Systems 5(4), 1993

54. P. Puschner, A. Schedl. A Tool for the Computation of Worst Case Task Execution Times, Technische Universitat Wien, 1994

55. H. Kopetz. Real-time Systems. Design principles for Distributed Embedded Applications. Kluwer Academic Publisher, Boston, 1997

56. J. A. Stankovic. Distributed Real-Time Computing: The Next Generation, University of Massachusetts, January 1992

57. J. A. Stankovic, K. Ramamritham. The Design of the Spring Kernel, 8th IEEE Real-Time Systems Symposium, San Jose, California, December 1987

58. J. A. Stankovic, K. Ramamritham. The Spring Kernel: A New Paradigm for Real-Time Operating System, ACM Operating System Review 23(3), July 1989

59. L. D. Molesky, K. Ramamritham, C. Shen, J. A. Stankovic, G. Zlokapa. Implementing a Predictable Real-Time Multiprocessor Kernel — The Spring Kernel, University of Massachusetts, May 1990

60. H. Kopetz, W. Merker. The Architecture of MARS, 15th Fault-Tolerant Computing Symposium, Ann Arbor, Michigan, June 1985

61. N. Audsley, K. Tindell, A, Burns. The End of The Line for Static Cyclic Scheduling, 5th Euromicro Workshop on Real-Time Systems, Oulu, IEEE Computer Soc. Press, 1993

62. A. Damm, J. Reisinger, W. Schwabl, H. Kopetz. The Real-Time Operating System of MARS, ACM Operating Systems Review 23(3), 1989

63. S. Poledna, G. Kroiss. The Time-Triggered Communication Protocol TTP/C, Real-Time Magazine, Q4 1998

64. H. Kopetz, G. Griinsteidl. TTP — A Protocol for Fault-Tolerant RealTime Systems, Computer, v. 27, №1, January 1994

65. H. Kopetz. TTP/A — The Fireworks Protocol, Research Report №23/1994, Technische Universiat Wien, September 1994

66. Ch. Ebner. Implementation of a TTP/A — Prototype, Research Report №2/1995, Technische Universiat Wien, February 1995

67. K. Tindell, J. Clark. Holistic Schedulability Analisys for Distributed Hard Real-Time Systems, University of York, 1994

68. D. Isovic, G. Fohler. Handling Sporadic Tasks in Off-line Scheduled Distributed Real-Time Systems, Malardalen Univesity, Sweden, July 1999

69. R. Gerber, S. Hang. Slicing Real-time Programs for Enhanced Sched-ulability, Department of Computer Science, University of Maryland, 1995

70. D. Isovic, G. Fohler. Online Handling of Firm Aperiodic Tasks in Time Triggered Systems, Malardalen Univesity, Sweden, June 2000

71. Ch. McElhone. Adapting and Evaluating Algorithms for Dynamic Schedulability Testing, University of York, February 1994

72. Y. Manabe, S. Aoyagi. A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling, Real-Time Systems, vol. 14, № 2, March 1998

73. R. Davis. Guaranteeing X in Y: On-line Acceptance Tests for Hard Aperiodic Tasks Scheduled by the Slack Stealing Algorithm, University of York, 1995

74. A. Girault, C. Lavarenne, M. Sighireanu, Y. Sorel. Fault-Tolerant Static Scheduling for Real-Time Distributed Embedded Systems, INRIA, research report № 4006, September 2000

75. R. Dobrin, G. Fohler. Attribute Assignment for the Integration of Off-line and Fixed Priority Scheduling, Malardalen Univesity, Sweden, November 2000

76. С. M. Bailey, A. Burns, A. J. Wellings, С. H. Forsyth. A Performance Analysis of a Hard Real-Time System. Real-Time Systems Research Group, Department of Computer Science, University of York, 1994

77. H. Kopetz. A Solution to an Automotive Control System Benchmark. Institute for Technical Informatics, Technical University, Vienna, Austria, research report № 4/1994, Apr 1994

78. С. М. Bailey, A. Burns, A. J. Wellings, С. Н. Forsyth. A Performance Analysis of a Hard Real-time System. Real-time Systems Research Group, Department of Computer Science, University of York, 1994

79. Г. Вагнер. Основы исследования операций, том 3, Мир, Москва, 1973

80. Д. Э. Кнут. Искусство программирования, том 2 Получисленные методы, 3-е изд. Издательский дом "Вильяме", Моска, 2000

81. Т. P. Baker. Stack-Based Scheduling of Real-Time Processes, RealTime Systems, March 1991

82. OSEK/VDX. Operating System. Version 2.0, revision 1. October 1997

83. R. Howell. Optimal Scheduling and Handling Potential Overload, Kansas State University, 1995

84. ERCOSek V3.0. User's Guide. ETAS Gmbh & Co. KG, Stuttgart, 1999

85. P. Ancilottiy G. Buttazzo, M. Natale, M. Spuri. Design and Programming Tools for Time-Critical Applications, Real-Time Systems, vol. 14, № 3, May 1998

86. H. Kopetz. A Solution to an Automotive Control System Benchmark. Institute for Technical Informatics, Technical University, Vienna, Austria, research report 4/1994 (April 1994)

87. D. McConnell, B. Lewis, L. Cray. Reengineering a Single Thread Embedded Missile Application onto a Parallel Processing Platform Using MetaH, Real-Time Systems, v. 14, № 1, January 1998