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

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

ГУЦАЛОВ

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

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

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

АВТОРЕФЕРАТ

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

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

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

Научный руководитель: - доктор технических наук, профессор

Никифоров Виктор Викентьевич

Официальные оппоненты: - доктор технических наук, профессор

Воробьев Владимир Иванович

- кандидат технических наук, доцент Сидельников Виктор Викторович

Ведущая организация: - Государственный научный центр

России ЦНИИ робототехники и технической кибернетики

Защита диссертации состоится " Л " СиЛ^ 2004 г. в 17 часов на заседании Специализированного совета Д.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 рисунков (общий объем диссертации - 147 листов).

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

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

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

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

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

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

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

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

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

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

И=С.+ I

где

ГУ1 - ближайшее сверху к х целое число.

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

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

Для того, чтобы обеспечить возможность использования информации о

временных соотношениях между задачами, в вычислительную модель приложения был добавлен новый объект - транзакция Г/, который представляет из себя группу задач, совместно обрабатывающих событие et и связанных между собой фазовыми сдвигами Ф, которые отсчитываются относительно момента поступления события. Между событием et и транзакцией Г( устанавливается однозначное соответствие, более того однозначное соответствие устанавливается между экземпляром события е( и экземпляром транзакции Г(. Как следствие период ДГ/) транзакции Г/ равен периоду Т(е!) поступления в систему внешнего события е,. В рамках данной модели все задачи x,j нумеруются при помощи двух индексов: первый обозначает номер транзакции, к которой принадлежит задача, а второй - порядковый номер задачи внутри транзакции по возрастанию значений

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

КШ = №ъь) + 1)* M(ra4) * N2(rab)*... = (Na(rab) + 1)* П

где N,(T„b) — количество задач из транзакции Г(, имеющих более высокий приоритет, чем таь- Таким образом главным недостатком данного метода является необходимость полного перебора вариантов, что делает вычисления НП-трудной задачей.

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

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

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

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

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

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

задачу и время переключения контекста по завершении выполнения задачи; DI- максимальное время работы ядра при запрещенных прерываниях; DR-максимальное время работы ядра при запрещенном перепланировании.

Для учета влияния бессрочных задач в состав приложения вводится одна фоновая задача ядра ОСОН которая будет создавать наихудшие для задач реального времени условия выполнения. Назначение бессрочной задаче следующих параметров позволяет работать с ней по общим правилам: T„uif= D„„if= °о; Сша = max(DI*>*,DIi*>*,Dl'*,DR'*).

Относительных срок выполнения всех системных задач устанавливается равным их периодам:

^tinier i ^managtr ^monogtr

С точки зрения анализа выполнимости работа системы при запрещенных прерываниях и запрещенном перепланировании носит характер блокирования,

что является основанием для расширения множества ресурсов специальными членами для каждого из ядер. Для упрощения модели все ресурсы объединяются в одно множество Я' = Я1){г^,г£). Такое же объединение

производится и для задач:

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

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

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

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

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

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

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

задач р,,. Каждый элемент профиля х< (левые индексы опущены) задается парой параметров X/= кРь сг% где Р1 - приоритет элемента, С/ — его длина.

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

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

Rí,л-Ja+Ji

где 1(Фа/) — длина /-го элемента гладкого профиля транзакции Г„, а ЦГ/) -длина цепочки элементов профиля транзакции начиная с первого, приоритеты которых превышают приоритет анализируемого элемента гладкого профиля Фя / транзакции Га. Время отклика последующих элементов гладкого

профиля вычисляются по формуле (примем обозначение

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

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

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

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

Четвертая глава посвящена рассмотрению предлагаемых в диссертации методов программной оценки параметров реактивности операционных систем реального времени.

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

разности оценок совпадает с разностью истинных задержек, если

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1) В. В. Никифоров, В. А. Павлов, М. В. Данилов, А. В. Глазков, Н. В. Гуцалов. Адаптация ОС Linux к требованиям поддержки программных приложений во встроенных системах. // Программные продукты и системы №4, 2001. С. 19-23

2) Н. В. Гуцалов, В. В. Никифоров. Методы измерения реактивонсти систем реального времени.//Программные продукты и системы №4, 2001. С. 24-28

3) Н. В. Гуцалов. Экспериментальная оценка быстродействия версий ОС Linux. // Информационно-управляющие системы. - 2002. - №1. С. 30-35

4) Н. В. Гуцалов, В. В. Никифоров, М. П. Червинский. Средства повышения надежности и предсказуемости поведения программных комплексов для встроенных систем. // Информатизация и связь. - 2003. -№ 1-2. - С. 79-85

5) Н. В. Гуцалов, В. В. Никифоров, М. П. Червинский. Модель ядра реального времени для встроенных систем. // Информационные технологии и вычислительные системы.- 2003. - №1-2. — С. 62-78

6) Н. В. Гуцалов, М. В. Данилов. Анализ выполнимости задач двухъярдных приложений реального времени. // Обработка информации: системы и методы: Сборник научных статей /Под ред. С.С. Садыкова, Д.Е. Андрианова - М.: Горячая линия - Телеком, 2003. - С. 123-129

ЦДЛ № 69 - 462 ог 30.12.99 Формат бумаги 60 х 90 1/16«. Печ. л.1 Печать офсетная. Тираж 100 экз. Заказ № 032 Типография ООО «Анатолия». 199187, Санкт-Петербург В.О., 14 линия 39

»- 8422

ВВЕДЕНИЕ

ГЛАВА 1. МЕТОДЫ ОЦЕНКИ ВРЕМЕННЫХ ПАРАМЕТРОВ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ

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

1.2. Двухъядерные системы реального времени

1.3. Методы оценки времени отклика задач РВ

1.3.1. Формальная модель системы

1.3.2. Граничная плотность загрузки

1.3.3. Базовый метод вычисления времени отклика.

1.3.4. Вычисление времени отклика задач, использующих разделяемые ресурсы

1.3.5. Спорадико-периодические задачи.

1.3.6. Задержка регистрации задачи в системе

1.3.7. Вычисление времени отклика задач с произвольными сроками выполнения

1.3.8. Влияние издержек планирования ОСРВ на время отклика задач

1.3.9. Вычисление времени отклика задач с фазовыми сдвигами

1.4. Экспериментальная оценка временных параметров СРВ

1.4.1. Оценка временных параметров ОСРВ

1.4.2. Оценка временных параметров приложения РВ

1.5. Выводы по первой главе

ГЛАВА 2. ВЫЧИСЛИТЕЛЬНАЯ МОДЕЛЬ ПРИЛОЖЕНИЯ РЕАЛЬНОГО ВРЕМЕНИ,

УПРАВЛЯЕМОГО ДВУХЪЯДЕРНОЙ ОПЕРАЦИОННОЙ СИСТЕМОЙ

2.1. Структура анализируемого приложения

2.2. Определение временных параметров вычислительной модели

2.2.1. Период задачи

2.2.2. Задержка регистрации задачи

2.2.3. Смещение задачи

2.2.4. Назначение временных параметров произвольной задаче

2.2.5. Временные параметры вычислительной модели, характеризующие влияние ОС 69 ф 2.2.6. Разделяемые ресурсы

2.3. Назначение параметров планирования объектам системы

2.4. Вычисление времени отклика задачи

2.5. выводы по второй главе

ГЛАВА 3. ВЫЧИСЛЕНИЕ ВРЕМЕНИ ОТКЛИКА СОСТАВНЫХ ЗАДАЧ

3.1. Профиль транзакции

3.1.1. Внутренняя структура задачи

3.1.2. Понятие профиля транзакции

3.1.3. Алгоритм формирования профиля транзакции

3.1.4. Формирование профилей транзакций приложения, содержащего составные задачи

3.2. Вычисление времени отклика секции задачи

3.2.1. Вычислительная модель приложения

3.2.2. Сценарий критического момента

3.3. Применение метода имитационного моделирования для проведения анализа выполнимости приложения РВ

3.4. Выводы по третьей главе

ГЛАВА 4. МЕТОДЫ ЭКСПЕРИМЕНТАЛЬНОЙ ОЦЕНКИ ПАРАМЕТРОВ РЕАКТИВНОСТИ ОПЕРАЦИОННЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ

4.1. Периодическая техника измерения задержки обработки прерываний

4.1.1. Сценарий измерительного эксперимента

4.1.2. Способы непосредственного использования результатов измерений

4.1.3. Метод уточнения фазы измерительных прерываний

4.1.4. Оценка максимальной задержки при неизвестной фазе измерительных прерываний

4.1.5. Способ экспериментальной оценки минимальной задержки обработки прерываний

4.1.6. Продолжительность сеанса оценки максимальной задержки обработки прерываний

4.2. Спорадическая техника измерения задержки обработки прерываний

4.2.1. Основная идея метода спорадического измерения задержки обработки прерываний

4.2.2. Сценарий измерительного эксперимента

4.2.3. Оценка вероятности получения результатов с заданной точностью

4.2.4. Реализация измерительного эксперимента, использующего спорадическую технику

4.3. Сравнительный анализ методов измерения задержки обработки прерываний

4.4. Условия проведения измерительных экспериментов

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

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

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

Наиболее удачного совмещения требований реального времени с богатым составом сервисов удается добиться при использовании двухъядерных ОСРВ, развитие которых началось с 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 рисунков (общий объем диссертации- 147 листов).

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. H.Kopetz. Real-Time Systems. Design Principles for Distributed Embedded Applications. Dordrecht: Kluwer Academic Publishers, 1997.

2. A.Burns, and A.J.Wellings. Real-Time Systems and their Programming Languages. Addison-Wesley, 1990.

3. В.В.Никифоров. Разработка программных средств для: встроенных систем. СПб.: ЛЭТИ, 2000.

4. С.J.Fidge. Real-Time Schedulability Tests for Preemptive Multitasking. // Real-Time Systems, 1998, 14. P.61-93.

5. J.A.Stankovic. Real-Time Computing. Department of Computer Since, University of Massachusetts, 1992.

6. В.В.Никифоров, В.А.Павлов. Операционные системы реального времени для встроенных программных комплексов. //Программные продукты и системы.- 1999.- №4.- С.24-30.

7. Information technology Portable Operating System Interface (POSIX®) — The Institute of Electrical and Electronics Engineers, Inc., 1996

8. В. В. Никифоров, Н.В.Гуцалов М.П.Червинский. Модель ядра реального времени для встроенных систем. // Информационные технологии и вычислительные системы 2003. - №1-2. - 62-78 с.

9. В. В. Никифоров, Н.В.Гуцалов М.П.Червинский. Модель ядра реального времени для встроенных систем. // Информационные технологии и вычислительные системы 2003. - №1-2. - 62-78 с.

10. OSEK/VDX. Operating System. Version 2.0 revision 1. http://www.osek-vdx.org.

11. H.A.Hansson, H.Lawson, M.Stromberg and S.Larsson. "Basement: A Distributed Real-Time Architecture for Vehicle Applications.".// Journal of Real-Time Systems, Kluwer Academic Publishers, 1996.

12. E.Larsson, "Vehicle Internal Architecture BASEMENT Real-Time System: The Scheduling Tool", Master of Science Thesis DoCS 95/56, ProVIA-94204, Department of Computer Systems, Uppsala University 1995.

13. A.K.Mok. Fundamental Design Problems of Distributed Systems of The Hard-Real-Time Environment. Ph.D. Thesis, Cambridge, Massachusetts, 1983.

14. D.Comer. Operating System Design? XTNU Approach. Englewood Cliffs: Prentice Hall, Inc., 1984.

15. В.И.Воробьев. Математическое обеспечение ЭВМ в науке и производстве. Л.: Машиностроение, 1988. 190 с.

16. D.Rusling. The Linux Kernel. http://www.linux.org.

17. Linux MAN. http://www.linux.org.

18. Х.Кастер. Основы Windows NT и NTFS. M.: Издательский отдел "Русская редакция" ТОО "Channel Trading Ltd.", 1996.

19. D.A.Solomon. Inside Windows NT. Microsoft Press, 1998.

20. Windows NT Workstation 4.0. Real-Time Consult, 1999. http://www.realtim.e-info.be.

21. M.Timmerman, B.V.Beneden. L.Uhres. Is Windows CE 2.0 A Real Threat To The RTOS World? //Real-Time Magazine. 1998.- №3.- C.20-24.

22. J.Powell. Multitask Windows NT. Waite Group Press, 1993.

23. В.В.Никифоров, В.А.Павлов, М.В.Данилов, А.В.Глазков, Н.В.Гуцалов. Адаптация ОС Linux к требованиям поддержки программныхприложений во встроенных системах. //Программные продукты и системы.- 2001.- №4. с. 19-24.

24. В.В.Никифоров, М.В.Данилов, М.В.Осипов. Сопряжение пакетов программ общего назначения с задачами жесткого реального времени. //Программные продукты и системы. №4.- Тверь: 2000.- С. 19-25.

25. G.Bollella, K.Jeffay. Support For Real-Time Computing Within General Purpose Operating Systems. Department of Computer Since, University of North Carolina, 1995.

26. RTOS Evaluation Program. Real-Time Consult, 1998. http://www.realtime-info.be.

27. Н.В.Гуцалов. Экспериментальная оценка быстродействия версий ОС Linux. // Информационно-управляющие системы. 2002. - №1. с. 30-35.

28. Zentropix: Real-Time Linux Test Data, www.zentropix.com

29. N.Frampton, J.Tsao, J.Yen. Windows CE Evaluation Report. General Motors, Powertrain. www.arcweb.com

30. HyperKernel 4.3. Real-Time Consult, 2001. http://www.realtime-info.be.

31. Building Distributed Real-Time Systems With Windows NT And INtime. RadiSys Corporation, 1998. http://www.radisys.com.

32. The RTX Real-Time Subsystem For Windows NT. VenturCom Inc., 1999. http ://www. venturcom. com.

33. HyperKernel. Reference Manual. Imagination Systems, http ://www.imagination.com.

34. RTX 4.2. Real-Time Consult, 2001. http://www.realtime-info.be.

35. INtime 1.20. Real-Time Consult, 2001. http://www.realtime-info.be.

36. Technology Brief: Real-Time Systems With Microsoft Windows NT. Publication of the Microsoft Developer Network, Microsoft Corporation, 1995.

37. V.Yodaiken, M.Barabanov. A Real-Time Linux. New Mexico Institute of Technology, http://www.rtlinux.org.

38. V.Yodaiken, M.Barabanov. Real-Time Linux Application and Design. New Mexico Institute of Technology, http://www.rtlinux.org.

39. Embedix RealTime Programming Guide Version 1.0, Lineo, Inc., Sep 2000

40. TimeSys Linux/RT Version 1.2, Programmer's Manual, TimeSys Corp., 2000

41. R.Hill, B.Srinivasan, S.Pather, and D.Niehaus, Temporal Resolution and RealTime Extensions to Linux. Technical Report ITTC-FY98-TR-11510-03, Dept. of Electrical Engineering and Computer Science, University of Kansas, 1998.

42. Hard Hat Linux 2.0. Professional Edition. Reference Guide. MontaVista Software Inc: 2001. http://www.mvista.com/products/shared/ORG.pdf

43. Design of a Fully Preemptable Linux Kernel. http://www.linuxdevices.com/articles/AT4185744181 .html

44. V.Yodaiken. The RTLinux Manifesto. New Mexico Institute of Technology. http://www.rtlinux.org.

45. Z.Deng, J.W.-S.Liu. Scheduling Real-Time Applications In An Open Environment. Department of Computer Since, University of Illinois, 1997.

46. M.Barabanov. A Linux-Based Real-Time Operating System. New Mexico Institute of Technology, 1997. http.7/www.rtlinux.org.

47. H.Lycklama, D.L.Bayer. The MERT Operating System. Bell System Technical Journal, №57, 1978.

48. M.Goncalves. Is Real-Time Linux For Real? //Real-Time Magazine. 1999.-№4.- C.51.-14153. J.Norton, C.Roundy. Real-Time Linux Where Is It Now? //Real-Time Magazine. - 1999.- №3.- C.68-70.

49. М.В.Данилов. Обеспечение поддержки приложений реального времени операционными системами общего назначения. //Труды СПИИРАН, т.1 — СПб: СПИИРАН, 2001.

50. Н.В.Гуцалов, М.В.Данилов. Анализ выполнимости задач двухъярдных приложений реального времени. // Обработка информации: системы и методы: Сборник научных статей /Под ред. С.С. Садыкова, Д.Е. Андрианова М.: Горячая линия - Телеком, 2003. - 123-129 с.

51. M.Klein, J.P.Lehoczky and R.Rajkumar. "Rate-Monotonic Analysis for RealTime Industrial Computing," Computer, January 1994.

52. M. Klein, T. Ralya, B. Pollak, R. Obenza, M.G.Harbour. "A Practitioner's Handbook for Real-Time Systems Analysis". Kluwer Academic Pub., 1993.

53. J. Y.T.Leung, J. Whitehead. On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks. Perf. Eval. (Netherlands), 1982-2, C.237-250.

54. KJeffay, D.F.Stanat, C.U.Martel. On Non-Preemptive Scheduling of Periodic And Sporadic Tasks. Department of Computer Since, University of North Carolina, 1991.

55. ISO 1994. "Ada Reference Manual: Language and Standard Libraries". 6.0 Edition. International Standard КОЛЕС 8652, 1995.

56. A.Burns, AJ.Wellmgs. "Engineering a Hard Real-Time System: From Theory to Practice". Software Practice & Experience. 1995.

57. Y.Manabe, S.Aoyagi. "A Feasibility Decision Algorithm for Rate Monotonic Scheduling of Periodic Real-Time Tasks". Real-Time Technology and Application Symposium (RTAS'95), pp.212-218. 1995

58. В. В .Никифоров, M.B .Перевозчиков. Ранжирование периодов задач всистемах реального времени. //Программные продукты и системы.- 1999.-№4.- С. 16-20.

59. H.Kopetz. ТТР/А The Fireworks Protocol. University of Wien, 1994.

60. Liu, C. L. and Layland, J.W., "Scheduling Algorithms for Multiprogramming in a Hard Real-Time environment", JACM, Volume 20, Number 1, p. 46 61, 1973.

61. R.Obenza. Guaranteeing Real-Time Performance Using Rate Monotonic Analysis. Embedded Systems Conference, 1994. http://www.esc.com.

62. L.Sha, M.H.Klein, J.B.Goodenough. Rate Monotonic Analysis For Real-Time Systems. Embedded Systems Conference, 1991. http://www.esc.com.

63. Holmes, David, " Fixed Priority Scheduling Analysis (From Rate Monotonic to Arbitrary deadlines and Beyond)", School of Electrical Engineering, University of Technology, Sydney, 1994.

64. J.Lehoczky, L.Sha, Y.Ding. "The Rate Monotonic Scheduling Algorithm: Exact Characterisation and Average Case Behaviour". Proceedings of the RealTime Systems Symposium, 1989

65. J.Y.T.Leung, J.Whitehead. "On The Complexity of Fixed-Priority Scheduling of Periodic Real-Time Tasks". Performance Evaluation. Vol. 2, Part 4, Dec 1982. pp.237-250

66. N.C.Audsley. Deadline Monotonic Scheduling. Department of Computer Since, University of York, 1990.

67. M.Joseph, P.Pandya. " Finding Response Times in a Real-Time System", The Computer Journal, Volume 29 , Number 5, p. 390-395, 1986.

68. N.C.Audsley, A.Burns, M.F.Richardson, A.J.Wellings. "Hard Real-Time

69. RTRG/92/120 Department of Computer Science Report, University of York, Feb 92

70. В.В.Никифоров, М.В.Данилов. Статическая обработка спецификаций программных систем реального времени. //Программные продукты и системы. №4.- Тверь: 2000.- С. 13-19.

71. Tindell, К., " Using Offset Information to Analyse Static Priority Preemptively Scheduled Task Sets," YCS 182, Department of Computer Science, University of York (1992).

72. С.Сорокин. Системы реального времени. //Современные технологии автоматизации.- 1997,- №2.- С.22-29.

73. N.C.Audsley. Resource Control For Hard Real-Time Systems. University of York, 1991.

74. Э.Дийкстра. Взаимодействие последовательных процессов. В сб.: Языки программирования. /Под ред. Ф.Женюи.- М.: Мир, 1972.

75. С.Кейслер. Проектирование операционных систем для малых ЭВМ. М.: Мир, 1986.

76. А.Робачевский. Операционная система UNIX. СПб: BHV-Санкт-Петербург, 1998г.

77. L.Sha, R.Rajkumar, J.Lehoczky. " Priority Inheritance Protocols: An Approach to Real-Time Synchronisation". IEEE Transactions on Computers 39(9), Sep 1990, pp.1175-1185

78. Tindell, K., "Real Time Systems by Fixed Priority Scheduling", Course Book, Department of Computer Systems, Uppsala University, 1996

79. B.Dutertre. The Priority Ceiling Protocol: Formalization and Analysis Using ♦ PVS. SDL, Menlo Park, 1999.-14487. N.C.Audsley. "Flexible Scheduling of Hard Real-Time Systems". DPhil. Thesis, Dept. Computer Science, University of York, UK. August 1993

80. K.Tindell. Embedded Systems in the Automotive Industry. Northern RealTime Applications: 1998. http://www.nrtg.com

81. T.P.Baker. "Stack-Based Resource Allocation Policy for Realtime Processes," Real Time Systems Symposium. IEEE Computer Society Press, pp 191-200. 1990.

82. T.P.Baker. "Stack-Based Scheduling of Realtime Processes," Real Time Systems 3(1), March 1991

83. B.W.Lampson, D.D.Redell. Experiences With Processes And Monitors In Mesa. //Communications of the ACM. 1980, C. 105-117.

84. M.-I.Chen, K.-J.Lin. "Dynamic Priority Ceilings: a Concurrency Control Protocol for Real-Time Systems". Journal of Real-Time Systems. 2(4), 1990.

85. Tindell, K., " Fixed Priority Scheduling of Hard Real-Time Systems", PhD Thesis, Department of Computer Science, University of York, 1994.

86. N.C.Audsley. "Optimal Priority Assignment and Feasibility of Static Priority Tasks With Arbitrary Start Times," YCS164, Dept. Computer Science, University of York (1991).

87. A.Burns, K.Tindell, AJ.Wellings. Fixed Priority Scheduling with Deadlines Prior to Completion. Real-Time System Research Group, Department of Computer Since, University of York.

88. A.Burns. Preemptive Priority Based Scheduling: An Appropriate Engineering Approach. Real-Time System Research Group, Department of Computer Since, University of York.

89. N.C.Audsley, A.Burns, M.F.Richardson, A.J.Wellings. "Stress: a Simulator for Hard Real-Time Systems". Software Practice & Experience. 1994.

90. M.H.Klein, T.Ralya. "An Analysis of Input/output Paradigms for Real-Time Systems". Technical report CMU/SEI-90-TR-19. Software Engineering Institute. Carnegie Mellon University. 1990.

91. Jane W.S. Liu. "Real-Time Systems". Prentice Hall, 1st edition, ISBN: 0-13099651-3. June, 2000.

92. J.C.Palencia, M.G.Harbour. "Schedulability Analysis for Tasks with Static and Dynamic Offsets". Departamento de Electronica у Computadores, Universidad de Cantabria, SPAIN

93. J.Palencia, M.Harbour. "Exploiting Precedence Relations in the Schedulability Analysis of Distributed Real-Time Systems". University of Cantabria, Spain

94. K.Tindell, "Adding Time Offsets to Schedulability Analysis", Technical Report YCS221, Department of Computer Science, University of York, November 1994.

95. J.P.Lehoczky. "Fixed Priority Scheduling of Periodic Task Sets With Arbitrary Deadlines". Proceedings 11th IEEE Real-Time Systems Symposium, Lake Buena Vista, Florida, USA, Dec 1990, pp. 201-209

96. M.Timmenman, B.Beneden, L.Uhres. RTOS Evaluation Kick Off. // RealTime Magazine, no. 3, 1998.

97. J.C. Palencia Gutierrez, J. J. Gutierrez Garcia, and M.G.Harbour. "Best-Case

98. Analysis for Improving the Worst-Case Schedulability Test for Distributed

99. Hard Real-Time Systems". The proceedings of the 10 Euromicro Workshop on Real-Time Systems, Berlin, Germany, June 1998.

100. Tanenbaum, S.Andrew, " Distributed Operating Systems", Prentice Hall, 1995.-146109. K.Tindell, J.Clark. "Holistic Schedulability Analysis For Distributed Hard * Real-Time Systems". Technical Report YCS197. Real-Time Systems Research

101. Group, Department of Computer Science, University of York, 1993.

102. K.Tindell, A.Burns, A.J.Wellings. "Allocating Real-Time Tasks (An NP-Hard Problem made Easy)". Real-Time Systems 4(2). June 1992. pp.145-165

103. K.W.Tindell, A.Burns, A.J.Wellings. "Guaranteeing Hard Real Time End-to-End Communications Deadlines," RTRG/91/107, Department of Computer Science, University of York. 1991.

104. J.J. Gutierrez Garcia, M. Gonzalez Harbour, "Increasing Schedulability in Distributed Hard Real-Time Systems". Proceedings of the 7th Euromicro Workshop on Real-Time Systems, pp. 99-106. Odense, Denmark, June 1995.

105. J.C. Palencia Gutierrez, J.J. Gutierrez Garcia, and M.Gonzalez Harbour, "Onthe Schedulability Analysis for Distributed Hard Real-Time Systems".fh

106. Proceedings of the 9 Euromicro Workshop on Real-Time Systems, pp. 136* 143. Toledo, Spain, June 1997.

107. N.Weiderman. Hartstone: Synthetic Benchmark Requirements for Hard RealTime Application. Tecnical Report. Carnegie Mellon Software Engeneering Institute, www.sei.cmu.edu

108. E.Cota-Robles, J.P.Held. A Comparition of Windows Driver Model Latency Performance on Windows NT and Windows 98. USENIX Third Symposium on Operating System Design and Implementation OSDI'99. www, intel. com/ial/sm/usenix

109. В.В.Никифоров, Н.В.Гуцалов. Методы измерения реактивности систем реального време-ни.// Программные продукты и системы.- 2001.- №4.

110. J.Labrosse. "Inside Real-Time Kernels". Microtec. 1998.

111. В. В. Никифоров, Н.В.Гуцалов. Оценка эффективности адаптации ОС Linux к условиям работы в системах реального времени. // Труды международной конференции «Региональная информатика 2002».

112. Serizawa k., etc. Linux Kernel State Tracing Facility. Hitachi, Ltd., 2002. http://oss.hitach.co.ip

113. K.Yaghmour. Monitoring and Analyzing RTAI System Behavior Using the Linux Trace Toolkit, http://www, opersys. com.

114. P.Cloutier, P.Mantegazza, S.Papacharalambous, I.Soanes, S.Hughes. DIAPM-RTAI position paper, (http://www, rtai. org).

115. Результаты исследования известных методов анализа выполнимости приложений в системах реального времени.

116. Полученные соискателем лично результаты по методам проведения анализа выполнимости приложений, содержащих составные задачи и задачи с состоянием ожидания, выполняющихся под управлением двухъядерных ОС.

117. Примеры использования предлагаемых методов.

118. Заместитель заведующего кафедрой АСОИУ кандидат технических наук, доцент1. Н.А.Мустафин

119. УТВЕРЖДАЮ Генерадь^ый директор ЗАО/ ; ••, : ^KjPCggpna ЗАО»,1. В.С.Полутин 2003 года1. АКТо внедрении результатов диссертационной работы Н.В.Гуцалова «Методы экспериментальной оценки характеристик двуядерных систем реального времени»

120. Старший инженер ЗАО «Моторола ЗАО» У М.П.Червинскийч1. УТВЕРЖДАЮ Генеральныйдиректор7» c^J^^J 2003 года1. АКТо внедрении результатов диссертационной работы Н.В.Гуцалова «Методы экспериментальной оценки характеристик двуядерных систем реального времени»

121. Способ организации межъядерного взаимодействия операционной системы.

122. Метод спорадического измерения реактивности'системы.

123. Метод обработки результатов измерения временных характеристик приложения.

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

125. Ведущий инженер ЗАО «Информационные деловые услуги», кандидат технических наук Инженер ЗАО «Информационные деловые услуги», доктор физико-математических наук1. В.П.Морозов.1. В.Г.Маслов