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

• Автор: Данилов, Михаил Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Санкт-Петербург
• Количество страниц: 140 с. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИИ

ГЛАВА 1. МЕХАНИЗМЫ ПЛАНИРОВАНИЯ ВЫПОЛНЕНИЯ ЗАДАЧ

ДЛЯ СИСТЕМ РЕАЛЬНОГО IШ

1Л. Системы реального времени

1.2. Особенности механизмов планирования для СРВ

1.2Л. Эффективность механизмов планирования для СРВ

1.2.2. оставляющие механизмов планирования для СРВ

1.3. Классификация механизмов планирования для СРВ

1.3.1. Классификация по распределению работ между составляющими механизма планирования

1.3.2. Классификация по алгоритму планирования

1.3.3. Классификация по дисциплине планирования
1.4. Алгоритмы планирования независимых задач
1.4.1. Формальная модель
1.4.2. Наиболее срочная первой
1.4.3. С наименьшим резервом первой
1.4.4. Планирование монотонное по частоте
1.4.5. Планирование монотонное по срокам
1.4.6. Алгоритм Оудсли
1.5. Алгоритмы планирования взаимодействующих задач
1.5.1. Отношения предшествования
1.5.2. Разделяемые ресурсы
1.6. Планирование в двухъядерных ОС
1.6.1. ОС общего назначения в СРВ
1.6.2. Принцип фоновой задачи
1.7. Управление памятью в СРВ
1.7.1. Системы управления памятью
1.7.2. Сборка мусора
1.7.3. Сборка мусора в СРВ
1.8. Выводы по главе 1
ГЛАВА 2. АСИММЕТРИЧНЫЕ ПРОТОКОЛЫ НАСЛЕДОВАНИЯ
ПРИОРИТЕТОВ
2.1. Асимметричный протокол наследования приоритетов .
2.1.1. Определение протокола
2.1.2. Свойства протокола
2.2. Асимметричный протокол пороговых приоритетов
2.2.1. Определение протокола
2.2.2. Свойства протокола
2.3. Примеры использования протоколов
2.3.1. Пример взаимной блокировки и ее предотвращения
2.3.2.1 ример многократного блокирования и его предотвращения
2.3.3. Пример составного блокирования и его предотвращения
2.3.4. Пример повышения эффективности планирования
2.4. Асимметричный протокол превентивного наследования приоритетов
2.4.1. Определение протокола
2.4.2. Свойства протокола
2.4.3. Пример использования протокола
2.5. Выводы по главе 2
ГЛАВА 3. СПЕЦИАЛИЗИРОВАННЫЕ МЕХАНИЗМЫ
ПЛАНИРОВАНИЯ ВЫПОЛНЕНИЯ ЗАДАЧ
3.1. Интегрированное планирование в двухъядерных ОС
3.1.1. Планирование обработки прерываний .
3.1.2. Использование особенностей программной модели процессора
3.1.3. Интегрированная схема планирования
3.1.4. Комбинированные механизмы защиты разделяемых ресурсов
3.2. Планирование групп логически связанных задач
3.2.1. Группы логически связанных задач
3.2.2. Протокол локально нсвытесняемых критических секций
3.5. Выводы по главе 3
ГЛАВА 4.1ГРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ МЕХАНИЗМОВ
ПЛАНИРОВАНИЯ ВЫПОЛНЕНИЯ ЗАДАЧ
4.1. Интегрированная двухъядерная ОС на базе ОС Ыпих
4.1.1. ОС Ыпих
4.1.2. Модификация ядра ОС Ыпих
4.1.3. Виртуальная машина
4.1.4. Интеграция механизмов планирования ядер ОС
4.1.5. Показатели эффективности ин тегрированной двухъядерной ОС
4.2. Сис тема ультразвуковой доплерографии сосудов мозга 5РЕСТИ1
4.2.1. Принципы ультразвуковой доплерографии
4.2.2. Постановка задачи
4.2.3. Разработка сис темы ЗРЕСТКА на базе двухъядерной ОС
4.3. Сборка мусора в группах логически связанных задач
4.3.1. Сборка мусора, основанная на приоритетах
4.3.2. Групповая сборка мусора
4.3.3. Назначение временных параметров сборщикам мусора
4.3.4. Модификация алгоритма Оудсли
4.4. Выводы по главе 4
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Диссертация содержит введение, четыре главы, заключение, список литературы (8 наименований); 4 таблицы и рисунков (общий объем диссертации - 0 листов). В первой главе на основании отечественных и зарубежных литературных материалов раскрываются особенности механизмов планирования выполнения задач в СРВ. Формулируется критерий определения эффективности механизма планирования для СРВ. Выполняется краткий анализ известных алгоритмов и протоколов планирования. ОС и планирования в системах, использующих механизм сборки мусора. Во второй главе рассматриваются разработанные автором протоколы защиты разделяемых ресурсов: асимметричный протокол наследования приоритетов, асимметричный протокол пороговых приоритетов и асимметричный протокол превентивного наследования приоритетов. Выполняется анализ свойств указанных протоколов. Приводится сравнение эффективности планирования, обеспечиваемой известными и предлагаемыми протоколами. Формулируются условия необходимые для повышения эффективности планирования при переходе к разработанным автором протоколам. В третьей главе рассматриваются разработанные автором методы повышения эффективности специализированных механизмов планирования. Выполняется детальный анализ недостатков описанного в первой главе принципа построения двухъядерных ОС на базе ОС общего назначения, принципа фоновой задачи. Предлагаются архитектурные решения, устраняющие эти недостатки. Рассматривается влияние предлагаемых решений на качественные характеристики двухъядерных ОС. Далее приводится способ декомпозиции многозадачного приложения РВ в виде групп логически связанных задач. Рассматривается, основанный на этом способе, специализированный протокол защиты разделяемых ресурсов - протокол локально невытесняемых критических секций. Четвертая глава посвящена рассмотрению примеров практического использования предлагаемых в диссертационной работе решений. В качестве примера использования предлагаемых методов планирования в двухъядерных ОС приводятся: (1) адаптация свободно-распространяемой ОС общего назначения Linux к требованиям жестких СРВ и (2) разработка программного обеспечения системы ультразвуковой доплерографии сосудов мозга SPECTRA. В качестве примера использования предлагаемого протокола локально невытесняемых критических секций приводится групповая сборка мусора -подход к планированию в системах со сборкой мусора. Далее рассматриваются математические модели, связанные с групповой сборкой мусора. В заключении делаются краткие выводы, в которых суммируются основные результаты диссертационной работы. ГЛАВА 1. МЕХАНИЗМЫ ПЛАНИРОВАНИЯ ВЫПОЛНЕНИЯ ЗАДАЧ ДЛЯ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ. Механизмы планирования выполнения задач - неотъемлемая составляющая любой ОС, во многом определяющая эффективность использования аппаратных ресурсов. Для разных классов систем критерии определения эффективности организации вычислений различны. Специфика процесса планирования в СРВ определяется требованием своевременного выполнения прикладных задач. По мере расширения практики применения СРВ расширялся и совершенствовался состав методов организации вычислений. В частности, расширялся состав, и повышалась эффективность используемых методов планирования выполнения задач. В данной главе приводятся наиболее значимые результаты, полученные к настоящему моменту в области планирования в СРВ. Системы реального времени. Согласно общепризнанному определению, системами реального времени называются системы, для которых специфицированы ограничения на время выполнения решаемых задач [3,4,5]. В зависимости от характера требований ко времени выполнения принято различать мягкие и жесткие СРВ. СРВ принадлежит к классу жестких, если нарушение установленных сроков выполнения задач недопустимо. СРВ называют мягкой, если получение результата выполнения задач после установленного срока приводит к снижению качества работы системы, но не влечет недопустимых последствий. С точки зрения планирования, СРВ мягкого типа отличает от жесткого только метод анализа соответствия системы исходным требованиям (анализ выполнимое ги). В данной главе преимущественно рассматриваются методы планирования общие для обоих типов СРВ.