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

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

ОГЛАВЛЕНИЕ

Основные термины и условные сокращения

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

1.1. Обзор подходов к планированию задач в системах жесткого реального времени

1.1.1. Классификация алгоритмов планирования задач реального времени

1.1.2. Классическая теория частотно-монотоннного анализа

1.1.3. Развитие идей частотно-монотонного анализа для мультипроцессорных систем реального времени
1.2. Модели распределения вычислительных ресурсов при статическом мультипроцессорном планировании

1.2.1. Традиционные модели распределения вычислительных ресурсов

1.2.2. Современные модели распределения вычислительных ресурсов .. 35 Выводы по главе
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. Разработка методов анализа выполнимости объектов планирования
Выводы по главе

3. Исследование особенностей применения разработанной методики в реальных системах жесткого реального времени
3.1. Уточнение методов анализа выполнимости объектов планирования для применения в реальных системах
3.1.1. Влияние переключений исполнительных ресурсов на оценку эффективности планирования
3.1.2. Взаимодействие объектов планирования
3.1.3. Устранение допущений в формировании моделирующих объектов при неравномерном распределении принудительных вытеснений
3.2. Анализ характеристик предложенных методов
Выводы по главе
4. Практическое использование разработанной методики
4.1. Решение производственных задач с использованием методики повышения эффективности распределения вычислительных ресурсов
4.2. Внедрение результатов диссертационного исследования
Выводы по главе
Заключение
Список использованных источников
Приложение 1. Свидетельство о государственной регистрации программы для эвм
Приложение 2. Акты о внедрении

ОСНОВНЫЕ ТЕРМИНЫ И УСЛОВНЫЕ СОКРАЩЕНИЯ
Deadline - крайний (предельный) срок завершения исполнения задачи.
EDF- алгоритм планирования «ближайший предельный срок первым».
Global Scheduling - глобальное мультипроцессорное планирование.
IEC - международная электротехническая комиссия.
ISO - международная организация по стандартизации.
Laxity - запас времени.
Laxity-driven scheduling - планирование, основанное на вычислении запаса времени (преимущественно с динамическими приоритетами).
LLF - алгоритм планирования «задача с наименьшим запасом времени первая».
Partitioned Scheduling - раздельное мультипроцессорное планирование.
POSIX (от англ. Portable Operating System Interface for Unix) — стандарт, регламентирующий переносимые интерфейсы ОС семейства Unix.
RM-US, SM-US, RMZL, FPZL - алгоритмы глобального мультипроцессорного планирования.
RMA (от англ. Rate-Monotonic Analysis) - частотно-монотонный анализ.
RMFF, RMNF, RMBF, FFDUF, RM-FFDU, RMST, RMGT, RMFF-WC, RMNF-WC, RMBF-WC, RMDP - алгоритмы раздельного мультипроцессорного планирования.
RMS - алгоритм частотно-монотонного планирования.
RTA (от англ. Response Time Analysis) - анализ времени дтклика.
Время выполнения задачи в худшем случае (от англ. Worst-Case Execution Time) - характеристика задачи, определяющая требуемое ей количество ресурсов исполнительного ресурса в отсутствии вытеснений.
Время отклика - характеристика задачи, определяющая максимальное время существования задания при условии наличия вытеснений и возникновении критического сценария.

планирования. Таким образом, становится очевидным [28], что традиционные подходы рассматривают мультипроцессорную систему как совокупность независимых ИР. Авторами работы [28] также было доказано, что по эффективности применения в мультипроцессорных СРВ методы глобального планирования могут превосходить дисциплины раздельного планирования, особенно при учете того факта, что при их использовании снижается число переключений исполнительного ресурса. В данном аспекте устоявшееся мнение об относительно низкой эффективности процедур глобального статического планирования при использовании в обозначенных условиях не верно. Отметим, что существует класс дисциплин, относящихся к классу раздельных лишь частично: EKG [31], [56], Ehd2-SIP [85], EDDP [83], DM-PM [82], PDMS HPTS [86], SPA [97].
1.2.2. Современные модели распределения вычислительных ресурсов
Работа В. Andersson, S. Baruah и J. Jonsson [26] позволяет пересмотреть применимость частотно-монотонного планирования в мультипроцессорных СРВ. В результате проведенного исследования был предложен алгоритм, именуемый авторами RM-US. Доказано [28], что при идентичных условиях данный метод может превосходить рассмотренные ранее дисциплины раздельного планирования. RM-US позволяет успешно выполняться системам задач при глобальном мультипроцессорном планировании, при наличии легких задач и, так называемых, называемых тяжелых. Стоит отметить, что процедура является прямой наследницей RMS. Успешное выполнение гарантируется при ограничении суммарной вычислительной нагрузки величиной:
^3^2' (1-6>
Выражение (1.6) в узком смысле является аналогом UB - теста (1.1) для RM-US планирования в мультипроцессорных СРВ. В рамках данного вида