авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

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

-- [ Страница 1 ] --

На правах рукописи

ГУЦАЛОВ

Никита Валерьевич

МЕТОДЫ ОЦЕНКИ ВРЕМЕНИ ОТКЛИКА ЗАДАЧ В ДВУХЪЯДЕРНЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Санкт-Петербург

2004

Работа выполнена в Санкт-Петербургском институте информатики и автоматизации Российской академии наук (Статус государственного учреждения)

Научный руководитель: - доктор технических наук, профессор Никифоров Виктор Викентьевич
Официальные оппоненты: - доктор технических наук, профессор Воробьев Владимир Иванович
- кандидат технических наук, доцент Сидельников Виктор Викторович
Ведущая организация: - Государственный научный центр России ЦНИИ робототехники и технической кибернетики

Защита диссертации состоится " " ___________ 2004 г. в ___ часов на заседании Специализированного совета Д.002.199.01 при Санкт-Петербургском институте информатики и автоматизации Российской академии наук по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского института информатики и автоматизации Российской академии наук.

Автореферат разослан " " ___________ 2004 г.

Ученый секретарь

Специализированного совета Д.002.199.01

кандидат технических наук А.Л. Ронжин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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





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

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

  1. Анализ известных методов обеспечения своевременного выполнения задач в системах реального времени.
  2. Построение вычислительной модели приложения, управляемого двуядерной ОСРВ, которая учитывает влияние ядер ОС на продолжительность выполнения заданий.
  3. Разработка методов анализа выполнимости приложений, учитывающих особенности внутренней структуры задач.
  4. Разработка методов анализа выполнимости приложений, включающих задачи с состоянием ожидания.
  5. Разработка программных методов экспериментальной оценки параметров реактивности ОСРВ.

Методы исследований. При проведении исследований и разработок в диссертационной работе были использованы подходы и методы теории множеств, комбинаторного анализа, математической логики, теории графов, структур данных и системного программирования, анализа выполнимости многозадачных СРВ, экспериментальной оценки характеристик производительности и реактивности ОС реального времени (ОСРВ).

На защиту выносятся:

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

Научная новизна. Научная новизна диссертации заключается в следующем:

  1. Разработана вычислительная модель приложения, управляемого двухъядерной операционной системой реального времени, которая позволяет учитывать влияние ядер операционной системы на время отклика прикладных задач за счет использования временных параметров операционной.
  2. Разработан подход к анализу выполнимости приложений, содержащих задачи с нетривиальной внутренней структурой. Учет внутренней структуры задач позволяет добиться существенного снижения неоправданного пессимизма оценок выполнимости.
  3. Разработан алгоритм вычисления времени отклика составных задач реального времени, который обладает меньшей трудоемкостью вычислений по сравнению с аналогичными методами; трудоемкость снижена за счет исключения из рассмотрения информации, являющейся избыточной с точки зрения анализа выполнимости.
  4. Предложен метод анализа выполнимости приложений, содержащих задачи с состоянием ожидания, в рамках которого исходные схемы задач преобразуются к схемам, которые не содержат операторов ожидания и установки условий.
  5. Разработан метод экспериментальной оценки параметров реактивности операционных систем реального времени средствами целевой аппаратной платформы, которые позволяют отказаться от использования измерительной аппаратуры за счет применения специальных методов планирования экспериментов.

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

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

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

Реализация результатов работы. Материалы диссертации используются в ходе занятий со студентами по дисциплине "Программирование встроенных СРВ" на базовой кафедре Санкт-Петербургского государственного электротехнического университета (ЛЭТИ) им. Ульянова (Ленина) "Автоматизации исследований" при СПИИРАН.

Предложенные в диссертации методы программной оценки реактивности ОСРВ были использованы в рамках проекта Санкт-Петербургского центра разработки программного обеспечения компании «Моторола» по сравнительной оценке версий ОС Linux, адаптированных к поддержке задач жесткого реального времени.

Предложенный метод анализа выполнимости приложений, содержащих составные задачи, был использован в ЗАО "Информационные деловые услуги" при создании комплекта инструментальных средств разработки приложений реального времени на базе интегрированной двухъядерной ОСРВ.

Апробация работы. Основные результаты диссертации представлялись на III ежегодном техническом семинаре Санкт-Петербургской лаборатории отдела разработки ПО фирмы Моторола "Technology Day - 2002" (СПб, июнь 2002), VIII Санкт-Петербургской Международной Конференции "Региональная Информатика - 2002" (СПб, ноябрь 2002), XIV конференции "Экстремальная робототехника" (СПб, апрель 2003), заседаниях Городского семинара "Информатика и компьютерные технологии" (СПб, май 2003 года и апрель 2004 года), VII Всероссийской научно-практической конференции "Актуальные проблемы защиты и безопасности" (СПб, апрель 2004).

Публикации. Основные результаты диссертации опубликованы в 6 печатных работах.

Структура и объем работы. Диссертация содержит введение, четыре главы, заключение, список литературы (124 наименования); 3 таблицы и 39 рисунков (общий объем диссертации – 148 листов).

СОДЕРЖАНИЕ РАБОТЫ

В первой главе описывается объект исследований – двухъядерная операционная система реального времени и приводятся наиболее значимые результаты в области оценки временных параметров систем реального времени.

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

Для устранения данных недостатков была разработана интегрированная двухъядерная ОСРВ. Она обладает двумя основными отличиями от ОСРВ, построенных по ПФЗ: во-первых, ядрами ОСОН и ОСРВ используются различные приоритетные уровни процессора для снижения степени влияния ядра ОСОН на реактивность ядра ОСРВ; во-вторых в операционной системе организуется интегрированный планировщик, благодаря чему задачи ОСОН могут на общих основаниях осуществлять синхронизацию с задачами ОСРВ при доступе к разделяемым ресурсам с использованием протоколов, основанных на понятии пороговых приоритетов.

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

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

Для проведения анализа выполнимости строится вычислительная модель анализируемого приложения, в которой выделяются наиболее значимые для анализа параметры реальной системы. С точки зрения вычислительной модели анализируемое приложение состоит из множества задач A = {1, 2, …, n}. В рамках простейших вычислительных моделей рассматриваются приложения РВ, в которых любая задача порождается в системе регулярно через равные промежутки времени. Такие задачи называются строго периодическими и их период обозначается Ti. Задача рассматривается как единый и неделимый поток управления, который характеризуется максимально возможным временем выполнения, обозначаемым Ci. Необходимость своевременного выполнения задачи обуславливает наличия еще одного параметра – относительного срока выполнения, который является директивной величиной и определяется исходя из внешних условий функционирования СРВ. Относительный срок выполнения задачи i обозначается как Di.

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

,

где x - ближайшее сверху к x целое число.

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

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

Для того, чтобы обеспечить возможность использования информации о временных соотношениях между задачами, в вычислительную модель приложения был добавлен новый объект – транзакция i, который представляет из себя группу задач, совместно обрабатывающих событие ei и связанных между собой фазовыми сдвигами , которые отсчитываются относительно момента поступления события. Следовательно между событием ei и транзакцией i устанавливается однозначное соответствие, более того однозначное соответствие устанавливается между экземпляром события ei и экземпляром транзакции i. Как следствие период T(i) транзакции i равен периоду T(ei) поступления в систему внешнего события ei. В рамках данной модели все задачи ij нумеруются при помощи двух индексов: первый обозначает номер транзакции, к которой принадлежит задача, а второй – порядковый номер задачи внутри транзакции по возрастанию значений ij.

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

Nv(ab) = (Na(ab) + 1)* N1(ab) * N2(ab)*… = (Na(ab) + 1)* Ni(ab), где

Ni(ab) – количество задач из транзакции i, имеющих более высокий приоритет, чем ab. Таким образом главным недостатком данного метода является необходимость полного перебора вариантов, что делает вычисления НП-трудной задачей.

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

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



Pages:   || 2 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.