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



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

ДАШЕВСКИЙ Владимир Павлович

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

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

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

Научный руководитель

доктор технических наук, профессор Торгашев Валерий Антонович

Официальные оппоненты

доктор технических наук, профессор Никифоров Виктор Викентьевнч

кандидат технических наук Васильевский Александр Сергеевич

Ведущая организация

ГУЛ «НИИ «Рубин»

Защита диссертации состоится « диссертационного совета Д.002.199.01

_2004г. на заседании при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178, Санкт-Петербург, В.О., 14-я линия, д. 39.

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

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

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

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

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

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

Создание новых методов анализа выполнимости задач в СРВ с учетом различных стохастических факторов является актуальной темой для исследования. Более точные методы расчета СРВ позволят сократить требования к производительности процессоров и снизить стоимость проектируемой системы.

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

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

- исследовать известные методы организации выполнения задач в СРВ;

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

- предложить способы учета влияния кэш-памяти процессоров на своевременное выполнение задач в СРВ.

Методы и средства исследования. Для проведения исследований в диссертационной работе использовались методы теории множеств, теории вероятностей, комбинаторика, дискретная математика, пакеты программ Mathematica, Microcal Origin, Statistica. Для разработки собственных программ использовались средства Microsoft Visual Studio и Code Composer Studio.

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

1. Метод вероятностного анализа задач в СРВ.

2. Модель релаксации производительности процессора при переключении контекстов задач.

3. Методики экспериментального определения параметров быстрой и медленной релаксации.

4. Способы учета параметров релаксации при анализе выполнимости задач.

Научная новизна полученных результатов:

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

- Базовый метод анализа выполнимости обобщен для задач с буферизацией запросов и порождения нескольких экземпляров одной задачи. Использование этих средств позволяет повысить эффективность функционирования СРВ.

- Предложена релаксационная модель восстановления производительности

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

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

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

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

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

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

Реализация результатов работы. Предложенные в диссертации методы анализа выполнимости задач в СРВ были использованы при расчете многоканального шлюза для IP-телефонии, встраиваемого в телефонные станции CORAL фирмы TADIRAN.

Апробация работы. Результаты исследований, включенных в диссертацию, докладывались на IX Санкт-Петербургской Международной конференции «Региональная информатика - 2002» (Санкт-Петербург, 2002), IV международной научно-технической конференции «Интеллектуальные и многопроцессорные системы - 2003», (Дивноморское, Россия, 2003), I Всероссийской научной конференции «Методы и средства обработки информации - 2003» (Москва, 2003), 2 научных семинарах СПИИРАН.

Публикации. Материалы диссертации опубликованы в 5 печатных работах.

Структура и объем работы. Диссертация содержит введение, пять глав, заключение, список литературы из 87 наименований. Общий объем работы -140 стр. Работа содержит 26 рисунков и 12 таблиц.

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

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

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

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

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

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

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

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

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

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

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

Методы вероятностного анализа по сложности существенно превосходят методы детерминированного анализа. Если в методах детерминированного анализа вычисления производятся над временными характеристиками задач, выражаемыми одним числом, то в методах вероятностного анализа приходится t оперировать распределениями этих величин, что требует большего количества вычислительных ресурсов. Основной > и многократно повторяемой операцией большинства методов вероятностного анализа является вычисление свертки, которое позволяет получить распределение суммы двух независимых случайных величин, исходя из распределения" каждой из. них в отдельности. В СРВ с вытесняющей, многозадачностью - вычисление свертки приходится. проводить несколько. раз на определенном множестве контрольных точек. Анализ предложенных, в литературе алгоритмов вероятностного анализа позволяет сделать следующую оценку их вычислительной сложности:

где т - количество контрольных точек, - оценка сложности алгоритма

вычисления свертки. В зависимости от методов вычисления свертки О^ может быть оценено как О(п), 0(п 1п п), 0(п2), где п - количество точек в дискретном представлении функций распределения. Обычные значения для п — 100. Л 000/для W-5..100.

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

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

Для каждой задачи УУ( из набора 5={ 1=1...И} независимыхпериодических задач с указанными вероятностными характеристиками, задаваемыми с

помощью профилей времени выполнения требуется оценить снизу

вероятностьр, завершения задачи до назначенного ей срока Dv

В приводимых ниже формулах предполагается, что задачи пронумерованы в порядке убывания приоритета, то есть из ;'</ следует, что приоритет задачи Ж, выше приоритета задачи

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

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

где Су - случайное время выполнения Х-ю экземпляра задачи Г* - период повторения задачи У/ц. Условием успешного завершения любого запроса задачи \У, является выполнение неравенства

для некоторого /6 [0, (п1 +1)7]].

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

Упорядочим эти точки в виде неубывающей последовательности Ьо,...,Ь„; Ъ0=0, Ьт=0,. Между двумя соседними точками и количество слагаемых остается постоянным, а функция плотности распределения события м>/;|<} на отрезке выражается формулой

1 В диссертационной работе профилем времени выполнения называется функция плотности распределения времени выполнения.

р,(!,Л= ® ® /4 (/), / = 1,К ,т

Ы1

где знаком ®обозначена операция свертки

(/®я)(0 = ¡/Ш(1-т)С1Т

(6)

В работе показано, что для оценки снизу вероятности выполнения задачи в срок достаточно произвести проверку условия (3) во всех точках множества {Ь,}. Таким образом, искомая вероятность

Р(Я/¿Ц) > р, = тах £'р,(г,№,

«О

(7)

где - время отклика системы при решении задачи Щ.

Упорядочение точек множества, {Ьу) позволяет производить вычисление сверток в выражении (5) последовательно, что уменьшает сложность вычислений. Исследование сложности алгоритма вероятностного анализа дает следующую оценку в случае непрерывной функции//*,).

где — сложность анализа задачи — оценка сложности вычисления

свертки для дискретно заданной функции распределения с количеством точек-

к - шаг дискретизации при задании профиля времени выполнения, т - количество контрольных точек в множестве [Ь},]=0..т}:

¿-1

-Е

*=1

(Ю)

Сравнение полученной оценки сложности (8) с оценками сложности для существующих методов (1) показывает, что их сложность приблизительно в т раз больше сложности предложенного базового метода вероятного анализа. Система, имеющая порядка десяти задач с различными периодами, обычно имеет т в диапазоне от 5 до 100. Таким образом, предложенный метод более эффективен с вычислительной точки зрения по сравнению с существующими методами.

Для оценки точности вероятностного анализа была реализована программа численного моделирования набора задач, набирающая-статистику выполнения задач в течение большого отрезка модельного времени. Сравнение результатов вероятностного анализа с численным экспериментом показывает, что:

- Вероятность, полученная с помощью предлагаемого метода, действительно не превосходит значения, полученного в результате численного эксперимента;

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

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

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

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

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

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

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

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

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

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

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

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

1. определялась бы только ее алгоритмом и входными данными;

2. не зависела бы от внутреннего состояния процессора;

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

Величиной, удовлетворяющей этим требованиям, является вычислительная работа, соответствующая каждому экземпляру задачи при определенных входных данных. Из-за непредсказуемых простоев ядра процессора при обращении к кэшпамяти выполнение вычислительной работы осуществляется с различной-производительностью, зависящей от времени. Зависимость производительности процессора от времени в отсутствие переключений контекста задач будем называть этаюнньш профилем производительности (рис. 1, а). Естественно предположить, что рост промахов в кэш-памяти, вызванный переключением контекста (рис. 1, б), приведет к снижению производительности и, как следствие, увеличению времени выполнения задачи.

рМ

II

г

I

а

б

Рис. 1. Производительность процессора как функция времени, модулированная переключениями контекста (а - без переключений контекста, б - при наличии переключений I и II)

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

1. переключение контекста задач действительно приводит к временному снижению и последующей релаксации производительности.

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

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

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

Рис. 2. Релаксация производительности для алгоритма голосового кодера, выполненного по рекомендации 0.723 Таким образом, медленная релаксация представляет собой совокупность коротких по времени процессов быстрой релаксации, вызванных одним переключением контекста. Это говорит о тесной связи процессов медленной релаксации производительности с вложенностью процедур и объемами их стековых кадров.

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

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

h{t)

(11)

где f(t), g(t) - профили эффективного времени выполнения, p(t) - профиль релаксации производительности. Чем меньше оказывается время между соседними переключениями контекста, тем сильнее сказывается падение производительности на увеличении времени выполнения задач. Таким образом, учет процессов быстрой релаксации может быть произведен аналитически с помощью двух изменений в базовом методе анализа выполнимости:

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

2. Вычисление сверток необходимо производить по формуле (11), вместо формулы (6).

0,0 0,3 0,6 0,9 1,2 1,5 1.8 2,1" 2,4 2,7 3,0

0,0 0,3 0,6 0,9 1,2 1,5 1,8 2,1 2,4 2,7 3,0 Момент наступления прерывания, мс

Рис. 3. Профиль времени выполнения кодера по рекомендации &723 в зависимости от момента наступления прерывания, очищающего содержимое кэш-памяти

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

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

Пятая глава посвящена практическому применению развитых в работе методов анализа выполнимости задач при проектировании многоканального шлюза IP-телефонии. Данный шлюз используется в телефонных станциях CORAL фирмы TADIRAN (Израиль). Конструктивно шлюз включает схему интерфейса с шиной расширения телефонной станции, хост-процессор, обеспечивающий работу сетевых протоколов и четыре сигнальных процессора фирмы Texas Instruments TMS320C6201, обеспечивающих обработку до 30 каналов телефонной связи.

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

Из требований обеспечения 30 каналов на один шлюз следует, что каждый DSP должен обеспечивать 8 каналов связи. Однако, детерминированный анализ задач, исходя из наихудших параметров задач, показывает, что один процессор не в состоянии справляться с обработкой 8 каналов. Причина этого заключается в наличии большого объема кэш-памяти (до 128 Кб) в одном DSP. Измерения времени выполнения алгоритмов обработки аудиоданных при отключении кэширования показывают почти пятикратное возрастание времени обработки одного 30-миллисекундного кадра аудиоданных, с 3,6 до 16,5 мс. С учетом полной перезагрузки кэш-памяти при смене задач, которая занимает 11% времени выполнения самих задач, детерминированный анализ гарантирует только 7 каналов на DSP. Учет влияния переключения контекста на время выполнения задач на основе релаксационной модели позволяет обосновать, что для выполнения одной задачи достаточно 3,6 мс. Таким образом, учет стохастических

факторов позволяет обосновать поддержку до Üü =8 каналов на одном DSP.

L 3.6 ас J

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

телефонной станции. Необходимую вероятность соблюдения сроков выполнения задач можно определить, исходя из исследований разборчивости речи в распределенной системе передачи речи по сетям с коммутацией пакетов. Известно, что разборчивость речи сохраняется на приемлемом уровне при потере 5-10% пакетов, так что вероятность нарушения непрерывного ввода-вывода информации должна быть не хуже 95 % .

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

Для проведения вероятностного анализа необходимо выбрать модельный профиль времени выполнения. Поскольку задачи всех каналов одинаковые, то все они могут быть описаны общим профилем времени выполнения. Время выполнения задачи компрессии и декомпрессии голоса зависит от активности говорящего абонента. В случае, если речь на входе кодера отсутствует, то времени для обработки требуется существенно меньше. Оказывается, что даже в речи непрерывно говорящего человека детектируется до 15 % случаев отсутствия голосовой активности. При подавлении эхо производится настройка параметров эхокомпенсатора, которая занимает дополнительное время примерно в 5 % случаев. На основе изучения статистики времен выполнения задач обработки аудиоданных для проведения анализа выполнимости были сформированы модельные профили, представленные на рис. 4. Были исследованы профили с 10 и 15 %-ной долей неречевых пакетов (рис. 4, а и б, соответственно).

Р

Р

76%

67%

10%

9%

5%

1с

1.1 ±0,05 2,8 ±0,05 3,0 ±0,1 3,6 ±0,05

1,1 ±0,05 2,8 ± 0,05 3,0 ±0,1 3,6 ±0,05

а

б

Рис. 4. Модельные профили распределения

(а - для 10% доли неречевых пакетов, б - для 15% доли неречевых пакетов)

Результаты вероятностного анализа представлены в таблицах 1 и 2. Как показывает анализ, имеет смысл ограничиться лишь наборами от 8 до 10 задач,

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

Таблица 1. Вероятность выполнения в срок N задач с 10%-ной долей неречевых

пакетов

N Относительный срок выполнении задач

D = 1T D = 2Т D = 3T D = 4T

8 1.0000 1.0000 1.0000- 1.0000

9 09999 1.0000- 1.0000 1.0000

10 06433 0.7369 0.7974 0 8374

Таблица 2. Вероятность выполнения в срок N задач с 15%-ной долей неречевых пакетов <

N Относительный срок выполнения задач

D = IT D = 2Т D = 3T D = 4T

8 1.0000 1.0000 1.0000 1.0000

9 0.9999 1.0000 1.0000 1.0000

10 0.8025 0 9087 09529 0.9749

Как видно из таблиц, один процессор в состоянии справляться с решением 8 и 9 задач, однако 10 задач в наихудшем случае решить невозможно. Использование буферизации позволяет повысить вероятность своевременного решения задач. При 15% доле неречевых пакетов процессор вполне может справляться с обработкой 10 каналов.

Таким образом, с помощью разработанных в диссертации методов показано, что для организации 30 каналов обработки аудиоданных в одном шлюзе IP-телефонии достаточно четырех DSP для обеспечения работы в наихудшем случае (8 каналов на процессор). Однако можно ограничиться всего тремя процессорами. Из расчетов следует, что каждый процессор способен поддерживать до 10 каналов с незначительным снижением качества сигнала в наихудшем случае и нормальной работой в среднем.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Развитые в работе методы были использованы при разработке программного обеспечения для многоканального шлюза IP-телефонии, применяемого для связи удаленных телефонных станций CORAL с помощью средств сети internet. От подрядчика фирмы TADIRAN, фирмы Organiq Engineering, получен акт о внедрении результатов диссертационной работы в телефонных станциях CORAL.

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

1. В.П. Дашевский. Вероятностный анализ задач с произвольными сроками выполнения в системах реального времени. //Материалы IV международной научно-технической конференции «Интеллектуальные и многопроцессорные системы», Дивноморское, Россия, 22-27 сентября 2003, том 2, С. 119-125.

2. В.П. Дашевский. Вероятностный анализ задач с буферизацией запросов в системах реального времени. //Труды I Всероссийской научной конференции «Методы и средства обработки информации», Москва, 1-3 октября 2003, С. 87-93.

3. В.П. Дашевский. Методика вероятностного анализа набора задач в системах реального времени с фиксированными приоритетами. // Изд. «Политехника», журнал «Информационно-управляющие системы», №4,2003, С. 15-23.

4. В.П. Дашевский. О некоторых аппанатных особенностях процессоров семейства TMS320C6000. //Материалы IV международной научно-технической конференции «Интеллектуальные и многопроцессорные системы-2003», Дивноморское, Россия, 22-27 сентября 2003, том 1, С. 243-247.

5. В.П. Дашевский. Сравнение основных дисциплин планирования в системах реального времени. // Труды СПИИРАН, Выпуск 1, Том 3, 2003, С. 91-98.

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

Введение.

Глава 1. Организация выполнения задач в СРВ.

1.1. Модель многозадачной СРВ.

1.1.1. Состояния задачи и переходы между ними.

1.1.2. Требования реального времени в вычислительных системах.

1.1.3. Используемые обозначения.

1.2. Планирование в СРВ.

1.2.1. Методы оценки эффективности планирования.

1.2.2. Парадигмы планирования.

1.3. Анализ выполнимости задач в СРВ.

1.3.1. Основные понятия, применяемые для анализа выполнимости.

1.3.2. Методы детерминированного анализа.

1.3.3. Стохастические факторы в системах реального времени.

1.3.4. Методы вероятностного анализа.

1.4. Постановка задачи диссертации.

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

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

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

1. исследовать известные методы организации выполнения задач в СРВ;

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

3. предложить способы учета влияния кэш-памяти процессоров на своевременное выполнение задач в СРВ.

Методы и средства исследования. Для проведения исследований в диссертационной работе использовались методы теории множеств, теории вероятностей, комбинаторика, дискретная математика, пакеты программ Mathematica, Microcal Origin, Statistica. Для разработки собственных программ использовались средства Microsoft Visual Studio и Code Composer Studio. Научная новизна полученных результатов.

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

2. Базовый метод анализа выполнимости обобщен на случай задач с буферизацией запросов и порождения нескольких экземпляров одной задачи. Использование этих средств позволяет повысить эффективность функционирования СРВ.

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

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

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

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

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

Реализация результатов работы. Предложенные в диссертации методы анализа выполнимости задач в СРВ были использованы при расчете многоканального шлюза для IP-телефонии, встраиваемого в телефонные станции CORAL фирмы TADIRAN.

Апробация результатов диссертации. Результаты исследований, включенных в диссертацию, докладывались на — II международной научно-технической конференции «Интеллектуальные и многопроцессорные системы», ИМС'2001, Дивноморское, октябрь 2001;

- IX Санкт-Петербургской Международной конференции «Региональная информатика-2002», РИ-2002, Санкт-Петербург, ноябрь 2002);

- IV международной научно-технической конференции «Интеллектуальные и многопроцессорные системы», ИМС'2003, Дивноморское, сентябрь 2003;

- I Всероссийской научной конференции «Методы и средства обработки информации», МСО'2003, Москва, октябрь 2003;

- на 2 научных семинарах СПИИРАН.

Публикации. Материалы диссертации опубликованы в 6 печатных работах [81, 83, 78, 82, 79, 80].

Структура и объем работы. В главе 1 приведены наиболее значимые результаты, полученные к настоящему времени в области теории проектирования программного обеспечения для СРВ. На основе проведенного исследования сформулирована задача диссертации.

В главе 2 представлен базовый метод вероятностного анализа независимых периодических задач, выполняемых в СРВ с вытесняющей многозадачностью и фиксированными приоритетами задач. Базовый метод позволяет учитывать стохастические факторы предметной области и оценивать снизу вероятность выполнения в срок каждой задачи при условии, что относительный срок задач не превышает их периода, а время переключения контекста задач пренебрежимо мало по сравнению со временем их выполнения. В главе 3 представлены два важных обобщения базового метода анализа выполнимости. Показано, что при определенных условиях организации задач в СРВ (буферизации запросов и множественной активации экземпляров задачи) базовый алгоритм анализа выполнимости может быть использован для получения оценки снизу вероятности решения задач в срок. Использование рассмотренных методов организации задач позволяет повысить оценку вероятности и эффективность функционирования системы. В главе 4 рассмотрены способы повышения точности базового метода вероятностного анализа при помощи учета неявного взаимного влияния задач, выполняющихся на одном процессоре. Предложена релаксационная модель функции производительности процессора и способы экспериментального измерения параметров релаксационной модели реальных процессоров на примере сигнальных процессоров фирмы Texas Instruments. Использование этих результатов позволило усовершенствовать базовый метод анализа выполнимости.

Глава 5 посвящена практическому применению разработанных в диссертации методов. В ней рассматривается применение вероятностного анализа выполнимости задач при разработке программного обеспечения для многоканального шлюза IP-телефонии, предназначенного для связи удаленных телефонных станций CORAL. Использование вероятностного анализа позволило сократить требования к числу процессоров шлюза.

выход

Рис. 21. Упрощенная схема обработки данных прямого потока

Рис. 22. Упрощенная схема обратного потока

Обработка данных прямого потока каждого из каналов заключается в следующем. После ввода одного кадра длительностью 30 мс (на частоте дискретизации 8000 Гц это соответствует массиву из 240 16-разрядных чисел) производится компенсация эхо принятого сигнала в соответствии с рекомендацией G.165.4 После компенсации эхо производится выделение тоновых сигналов DTMF, применяемых для кодирования цифровых клавиш при тоновом наборе. Необходимость выделения тоновых сигналов, их кодирования, а затем последующего восстановления обусловлена двумя причинами. Во-первых, при передаче по сети возможна потеря пакетов, что может привести к разрыву тоновых сигналов и неправильному их детектированию на удаленной стороне. Во-вторых, алгоритмы сжатия голоса с потерями, как правило, сильно искажают гармонические сигналы, что приводит к существенному снижению качества сигналов тонового набора. Поэтому приходится выделять эти сигналы и кодировать отдельно от остальных. Вслед за выделением DTMF и других сигналов, управляющих оборудованием линий связи, производится детектирование речевой активности абонентов. В случае, если активность обнаружена, данные подаются на один из речевых кодеров, выполненных в соответствии с рекомендациями G.711, G.723, G.729.5 Использование речевых кодеров позволяет сократить объем данных, передаваемых по сети от 2 до 20 раз. В случае отсутствия речевой активности фиксируется перерыв передачи, и данные в сеть временно не посылаются. Данные для отправки упаковываются в соответствии с протоколом RTP [54], который разрабатывается специально для синхронизации мультимедийных приложений реального времени. После упаковки данные передаются в HOST-процессор, откуда они отправляется в сеть.

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

4 Данная рекомендация разработана организацией ITU-T.

5 Данные рекомендации разработаны организацией ITU-T. обработки одного кадра речи в прямом потоке приходится на функцию кодера, вызов которой осуществляется лишь при выполнении нескольких условий. Обнаружение тоновых сигналов производится быстрее всего и устраняет необходимость дальнейшей обработки. При отсутствии тоновых сигналов время обработки зависит от решения, принятого детектором речевой активности (voice activity detector). Экспериментально полученные данные о времени работы алгоритмов кодера G.723 представлены на рис. 23, а. Как показали измерения, даже при нормальной речи говорящего примерно 10-15 % кадров приходятся на отсутствие речевой активности. В этом случае время работы кодера сокращается примерно в 3,5 раза.

0.30

0.00

Время работы кодера G.723, мс

0.05 0,10 0.15 0.20 0.25 Время работы декодера G.723, мс о.зо а) б)

Рис. 23. Профиль времени выполнения функций кодека G.723

Обработка данных в обратного потока каждого из каналов заключается в следующем (рис. 22). Пакеты с упакованными данными каждого канала поступают из HOST-процессора и складываются в адаптивный буфер, предназначенный для выравнивания задержки доставки пакетов по сети и восстановления порядка их следования. Каждые 30 мс диспетчер производит проверку наличия данных в буфере, готовых для воспроизведения в текущем периоде обратного потока. В случае, если данные в буфере есть, диспетчер вызывает функции декодера речи или генерации тоновых сигналов. Если данных в буфере нет, то вызывается либо интерполятор речи, либо генератор комфортного шума (comfort noise generator), в зависимости от того, является ли пропавший пакет фрагментом речи или паузы между словами. На выходе всех алгоритмов появляется воспроизведенный кадр аудиоданных длительностью 30 мс, который отправляется на проигрывание в область памяти, используемую для вывода данных в последовательный порт с помощью контроллера DMA.

В отличие от прямого потока данные обратного потока могут поступать нерегулярно, поскольку существуют потери пакетов в сети и задержки их доставки. Однако синхронизация прямого потока одного абонента и обратного потока второго абонента требует формирования выходных данных с темпом один кадр в 30 мс вне зависимости от наличия данных, пришедших из сети. Для обеспечения синхронизации приходится прибегать к интерполяции пропавших речевых пакетов по данным предыдущих пакетов и генерации комфортного шума. Существует несколько способов умышленного изменения параметров синхронизации, которое просто необходимо в определенных ситуациях. Так, например, в результате стихийного возрастания (завершения) постороннего компьютерного трафика через промежуточные узлы, связывающие шлюзы двух абонентов, возможно скачкообразное увеличение (уменьшение) задержки доставки пакетов при сравнительно малой дисперсии времени доставки. В случае увеличения задержки это явление может приводить к эффекту тотального опаздывания пакетов. В случае уменьшения задержки это может приводить к внезапному заполнению адаптивного буфера пакетов, вплоть до его переполнения. И в том, и в другом случае наблюдаются искажения или полное исчезновение полезного сигнала. Для борьбы с подобными явлениями применяется механизм перевода часов приемника, суть которого состоит в выбрасывании или, наоборот, повторении пакетов, отмеченных признаком тишины, то есть, незаметно для пользователя. Более «плавный» перевод часов может быть реализован на уровне вывода данных в последовательный порт. Если вместо кадра длиной 240 отсчетов, отправлять туда кадр длиной 239 или 241 отсчет, то время вывода кадра будет уменьшаться или возрастать, что эквивалентно переводу часов на один период частоты дискретизации (125 мкс). При этом, пропуски и добавления одного отсчета практически незаметны на слух, так что плавный перевод часов может применяться вне зависимости от содержимого пакетов. Однако, несмотря на возможные пропуски при приеме пакетов и наличие обратной связи, регулирующей среднее количество пакетов в адаптивном буфере, задача обработки обратного канала может также считаться периодической, с переменным временем обработки. Как и в случае с прямым каналом, наибольшая доля времени приходится на вызов функции декодера. Экспериментально полученные данные о времени работы алгоритмов декодера G.723 представлены на рис. 23, б. Видно, что обработка кадров тишины обходится по времени в 1,4-1,5 раза дешевле, чем полное восстановление речи.

5.3.1. Требования реального времени при обработке аудиоданных

Анализ потоков аудиоданных показывает, что в системе имеется до 30 задач реального времени, где одна задача соответствует одному каналу с установленным соединением. Обработка каждого канала должна производиться регулярно, с периодом 30 мс. Ввиду доминирования времени выполнения задач речевого кодера и декодера над остальными задачами целесообразно предъявлять требования реального времени именно к ним.

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

JUL

Регистр передачи последовательного порта

Кольцевой буфер вывода

Рис. 24. Организация вывода аудиоданных через последовательный порт с помощью контроллера DMA

В качестве примера источника требований реального времени рассмотрим организацию вывода данных через последовательный порт с помощью контроллера DMA (см. рис. 24). Для каждого канала вывода в памяти располагается буфер, вмещающий достаточно большое количество отсчетов (примерно 3-4 целых кадра длиной в 240 временных отсчетов). Контроллер DMA настраивается таким образом, чтобы поочередно считывать из буфера слова данных и записывать их в регистр передачи данных последовательного порта синхронно с завершением передачи. При достижении конца буфера указатель чтения DMA автоматически переставляется на начало буфера и чтение продолжается. После декодирования информации (задаче вывода соответствует функция декодера) и получения одного кадра аудиоданных процессор записывает его в буфер на место, куда указывает указатель записи CPU. После записи массива чисел указатель записи CPU передвигается аналогично указателю чтения DMA. Таким образом, для задачи вывода требование непрерывного потока обработанных данных в последовательный порт заключается в такой организации работы CPU, чтобы указатель чтения DMA никогда не догонял указатель записи CPU. Максимальная задержка обработки информации функциями декодера определяется количеством отсчетов, на которое запись CPU опережает чтение DMA. Ясно, что, выбрав достаточно большой размер кольцевого буфера, можно регулировать опережение записи в широком диапазоне и, тем самым, практически произвольно ре1улировать относительный срок выполнения задачи декодера.

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

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

5.4. Вероятностный анализ набора задач одного DSP

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

5.4.1. Постановка задачи вероятностного анализа для кодирования и декодирования потоков аудиоданных

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

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

Итак, наименьшее требуемое число задач на одном процессоре равно 8. Уменьшение числа процессоров приводит к увеличению максимально возможного числа задач на каждом из них. При условии трех процессоров число задач возрастет до 10, а при условии всего двух процессоров на каждый процессор придется по 15 задач. Таким образом, число задач при вероятностном анализе целесообразно варьировать в диапазоне 8. 15.

Период повторения всех задач, как уже было отмечено в разделе 5.3.1, равен 30 мс. Относительный срок их выполнения также представляет собой варьируемую величину. Минимальным значением для нее традиционно является период повторения задач, а максимальное значение определяется ресурсами памяти, выделенной для буферов ввода-вывода и полной задержкой в распространении информации. В проекте шлюза IPG-30, ресурсы памяти

Ф позволяют рассматривать относительный срок в диапазоне от 1 до 3 периодов повторения задач. Допустимая минимальная задержка распространения (для случая локальной сети) равняется 150 мс. Это дает ограничение на относительный срок в диапазоне от 1 до 5 периодов повторения задач. Таким образом, целесообразно варьировать относительный срок в диапазоне De[T,3T). Поскольку задачи одинаковы, что относительный срок выполнения задается одинаковым для всех задач, как и период повторения запросов.

Необходимую вероятность соблюдения сроков выполнения задач можно определить, исходя из исследований разборчивости речи в распределенной системе передачи речи по сетям с коммутацией пакетов. Известно, что разборчивость речи сохраняется на приемлемом уровне при потере 5-10% пакетов [29,11,53]. Таким образом, вероятность нарушения непрерывного ввода-вывода информации должна быть не хуже 95 % .

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

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

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

Наиболее трудоемкой по времени выполнения задачей является обработка с использованием аудио-кодека, выполненного по рекомендации G.723.

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

76%

10%

9%

5% 1

67%

15%

13%

5% 1 С

1,1 ±0,05

1,1 ±0,05

2,8 ±0,05 3,0 ±0,1 3,6 ±0,05 б)

2,8 ±0,05 3,0 ±0,1 3,6 ±0,05 а)

Рис. 25. Модельные профили выполнения для задач.

При расчете задачи обработки на одном процессоре исследовались модельные профили времени выполнения, соответствующие доле неречевых кадров 10% (рис. 25 а) и 15 % (рис. 25 б). При этом, примерно в 5% случаев речевых пакетов производится подстройка коэффициентов для компенсации эхо, что еще увеличивает время выполнения. Для упрощения расчетов предполагается, что профили времени выполнения состоят из трех участков с равномерным распределением. Время выполнения, приведенное на рисунке, дано в миллисекундах.

5.4.3. Результаты анализа для разного количества задач

Анализ выполнимости задач требует назначения им приоритетов. Традиционными правилами назначения приоритетов задачам являются правила выбора приоритетов монотонно по периоду выполнения задачи [37,35] и монотонно по относительным срокам [2,6]. Однако оба этих правила не могут быть применены в данном случае, поскольку все задачи обработки аудиоданных являются одинаковыми и должны иметь одинаковый приоритет. Для проведения анализа в такой ситуации удобно воспользоваться следующим приемом: сначала назначить произвольно приоритеты задач так, чтобы каждому уровню приоритета соответствовало не более одной задачи, затем выполнить анализ выполнимости. Результаты анализа выполнимости для задачи с наименьшим приоритетом будут представлять собой оценку выполнимости всех задач, поскольку все они равноправны. При выполнении задач с одинаковым приоритетом в режиме без вытеснения анализ их выполнимости полностью соответствует анализу выполнимости задач с приоритетами, где выбор приоритетов определяется порядком поступления задач и зависит от фазы поступления запросов на решение задач.

Детерминированный анализ задач, исходя из наихудших параметров задач, показывает, что один процессор не в состоянии справляться с обработкой 8 каналов. Причина этого заключается в наличии большого объема кэш-памяти (до 128 Кб) в одном DSP TMS320C6201. Измерения времени выполнения алгоритмов обработки аудиоданных при отключении кэширования показывают почти пятикратное возрастание времени обработки одного кадра, с 3,6 до 16,5 мс. То есть, при отключенной кэш-памяти потеря производительности весьма существенна, - можно гарантировать выполнение лишь одного канала на DSP. Оценка наихудшего случая перезагрузки всей кэш-памяти позволяет получить лучший результат. Как видно из графика, представленного на рис. 14 (см. раздел 4.1.2), перезагрузка всей кэш-памяти занимает примерно 11 % всего времени обработки одного кадра в случае кодека рекомендации G.723. То есть, наихудшее время обработки одного кадра составит порядка 3,6-1,11 = 4 мс. Следовательно, в наихудшем случае один процессор сможет поддерживать только

30 мс 7 каналов, а не 8. Таким образом, детерминированный анализ

4 мс выполнимости без учета стохастических факторов вычислительной среды не позволяет обосновать, что для обработки 30 каналов в одном шлюзе достаточно даже четырех DSP, а не трех. Учет влияния переключения контекста на время выполнения задач на основе релаксационной модели позволяет обосновать, что для выполнения одной задачи достаточно 3,6 мс. Таким образом, более точный учет стохастических факторов позволяет обосновать поддержку до 30 мс

3,6 мс 8 каналов.

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

Множество контрольных точек при анализе одинакового набора периодических задач имеет очень простую структуру, в него входят только точки вида xk=kT, £еN.

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

Результаты вероятностного анализа представлены в таблицах И и 12. Как показывает анализ, имеет смысл ограничиться лишь наборами от 8 до 10 задач, поскольку уже для 11 задач средняя загрузка становится больше 1, то есть непрерывная работа всех задач будет в принципе невозможна.

Заключение

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

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

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

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

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

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

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

7. Предложена система поправок к методам анализа выполнимости, связанных со стохастическим взаимным влиянием задач при выполнении на одном микропроцессоре. Использование поправок позволяет более точно оценить вероятность своевременного выполнения задач.

8. Разработано программное обеспечение для многоканального шлюза IP-телефонии, применяемого для связи удаленных телефонных станций CORAL с помощью средств сети internet. При разработке программного обеспечения автором использовались развитые в работе методы вероятностного анализа задач с учетом влияния кэш-памяти на время выполнения задач.

1. А. К. Atlas and Л. Bestavros. Statistical rate monotonic scheduling. Proceedings of the 19th Real-Time System Symposium, December 1998, pp. 123-132.

2. N. C. Audsley. Deadline Monotonic Scheduling. YCS.146, Department of Computer Science, University of York, September 1990.

3. N. C. Audsley. Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times. Department of Computer Science, University of York, November 1991.

4. N. C. Audsley. Resource Control for Hard Real-Time Systems: A Review. Real-Time Systems Research Group, Department of Computer Science, University of York, UK, August 1991.

5. N. C. Audsley, A. Burns, R.I. Davies, K.W. Tindell, and A.J. Wellings. Fixed Priority Preemptive Scheduling: An Historical Perspective. Journal of Real-Time Systems, vol. 8, 1995, pp. 173-198.

6. N. C. Audsley, A. Burns, M.F. Richardson, K.W. Tindell, and A.J. Wellings. Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling. Software Engineering Journal, 8(5): 284-292, September 1993.

7. N.C. Audsley, A. Burns, M.F. Richardson, A.J. Wellings. Hard Real-Time Scheduling: The Deadline-Monotonic Approach Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, USA (15-17 May 1991).

8. S. Biyabani, J. A. Stankovic, K. Ramamritham. The Integration of Deadline and Criticalness in Hard Real-Time Scheduling. Proceedings of 9*h Real-Time Systems Symposium, December 1988, pp. 152-160.

9. G. Bernat, A. Colin, S. Petters. WCET Analysis of Probabilistic Hard Real-Time Systems. The 23rd IEEE International Real-Time Systems Symposium, December 3-5, 2002, Austin, Texas. (USA)

10. A. Bestavros, D. Spartiotis. Probabilistic Job Scheduling for Distributed Real-Time Applications. Proceedings of the 1st IEEE Workshop in Real-Time Applications, New York, May 1993.

11. J.C. Bolot. End-to-End Packet Delay and Loss Behavior in the Internet. Proceedings of the ACMSIG-COMM Conference, San Francisco, pp. 289-298, September 1993.

12. I. Broster, A. Burns, G. Rodriguez-Navas. Probabilistic Analysis of CAN with Faults. The 23rd IEEE International Real-Time Systems Symposium, December 3-5, 2002, Austin, Texas. (USA)

13. A. Burns. Scheduling Hard Real-Time Systems: A Review. Software Engineering Journal, no 6, 1991, pp. 116-128.

14. A. Burns. Preemptive Priority Based Scheduling: an Appropriate Engineering Approach. Advances in Real-Time Systems, Prentice Hall, 1995, pp. 225-248.

15. G. C. Butazzo. Hard real-time Computing Systems. Kluwer Academic, 1997

16. A. Cervin. Analyzing the Effects of Missed Deadlines in Control Systems. Real-Time Graduate Student Conference, Lund, March 8-9, 2001.htip: //www.artes. uu.se/events/gsconf01/papers/cervin.pdf

17. S. Chai, A. Agrawala. Scheduling Aperiodic and Sporadic Tasks in Hard Real-Time Systems. Department of computer science, University of Maryland, 1997

18. H. Chetto, M. Chetto. Some Results of the Earliest Deadline Scheduling Algorithm. IEEE Transactions on Software Engineering, 15(10), October 1989

19. M. L. Dertouzos, А. К. Мок. Multiprocessor On-Line Scheduling of Hard Real-Time Tasks. IEEE Transactions on Software Engineering, 15(12), December 1989.

20. J. L. Diaz, D. F. Garcia, K. Kim, C.-G. Lee, L. L. Bello, J. M. Lopez, S. L. Min, and O. Mirabella. Stochastic Analysis of Periodic Real-Time Systems. The 23rd IEEE International Real-Time Systems Symposium, December 3-5, 2002, Austin, Texas. (USA)

21. M. R. Garey, D. S. Johnson. Scheduling Tasks with Nonuniform Deadlines on Two Processors. Journal of the ACM, Vol. 23, No. 3, July 1976, pp. 461-467.

22. M. Garnder. Probabilistic Analysis and Scheduling of Critical Soft Real-Time Systems. PhD Dissertation, University of Illinois at Urbana-Champain, 1999

23. D. Haban, K. Shin. Application of Real-Time Monitoring to Scheduling Tasks with Random Execution Times. IEEE Transactions on Software Engineering, 16(12), December 1990.

24. M. G. Harmon, T. P. Baker and D. B. Whalley. A Retargetable Technique for Predicting Execution Time. Proceedings of the 13th IEEE Real-Time Systems Symposium, 1992, pp. 68-77.

25. C.-J. Hou, K.G.Shin. Load Sharing with Considerations of Future Arrivals in Heterogeneous Distributed Real-Time Systems. Proceedings of the Real-Time Systems Symposium, December 1991, pp. 94-103

26. E.Y.-S. Hu, A.Wellings and G.Bernat. A Novel Gain Time Reclaiming Framework Integrating WCET Analysis for Object-Oriented Real-Time Systems. Proceedings of the 2th International Workshop on Worst-Case Execution Time Analysis, WCET-2002.

27. Z. S. Hu, T. Zhou, and E. H.-M. Sha. Estimating probabilistic timing performance for realtime embedded systems. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 9(6): 833-844, December 2001.

28. N. Jayant. Effects of Packet Loss on Waveform Coded Speech. Proceedings of 5th Int. Conference on computer Communications, Atlanta, GA, pp. 314-329, October 1980.

29. E. D. Jensen, C.D. Locke, H. Tokuda. A Time-Driven Scheduling Model for Real-Time Operating Systems. Proceedings of the Real-Time Systems Symposium, 1985, pp. 112-122.

30. M. Joseph and P. Pandya. Finding response times in a real-time system. The Computer Journal — British Computer Society, 29(5): 390-395, October 1986.

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

32. J. Lehoczky. Fixed Priority Scheduling of Periodic task Sets with Arbitrary Deadlines. Proceedings of the IIth Real-Time Systems Symposium, Los Alamitos, December 1990, pp. 201-209.

33. J. Lehoczky, S. Ramos-Thuel. An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems. Proceedings of the 13th Real-Time Systems Symposium, 1992, pp. 110-123.

34. J. Leung, J. Whitehead. On the complexity of fixed-priority scheduling of periodic, realtime tasks. Performance Evaluation, 2, 1982, pp. 237-250.

35. C.L. Liu and J.W. Layland. Scheduling Algorithms for Multiprogramming in a Hard RealTime Environment. Journal of the ACM, pp. 46-61, 1973.

36. C. D. Locke. Best-Effort Decision Making for Real-Time Scheduling. Ph. D. Thesis Carnegie Mellon University, Pittsburgh, PA, May 1985.

37. G. K. Manacher. Production and Stabilization of Real-Time Task Schedules. Journal of the ACM, vol. 14, No. 3, July 1967, pp. 439-465

38. G. Manimaran. Resource Management With Dynamic Scheduling in Parallel and Distibuted Real-Time Systems. Ph. D. Thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, March 1998

39. S. Manolache, P. Eles, and Z. Peng. Memory and time-efficient schedulability analysis of task sets with stochastic execution time. Proceedings of the 13'h Euromicro Conference on Rel Time Systems, June 2001, pp. 19-26

40. S. Manolache, P. Eles, and Z. Peng. Schedulability Analysis of multiprocessor real-time applications with stochastic task execution times. Proceedings of the 2(fh International Conference on Computer Aided Design, November 2002

41. S. Manolache. Schedulability Analysis of Real-Time Systems with Stochastic Task Execution Times

42. А. К. Мок. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment. Ph.D Dissertation, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1983.

43. D. T. Peng, K. G. Shin. Static Allocation of Periodic Tasks with Precedence Constraints in Distibuted Real-Time Systems. Proceedings of the International Conference on Distibuted Computing, Junel989, pp. 190-198.

44. S. Punnekkat. Schedulability Analysis for Fault Tolerant Real-Time Systems. PhD Dissertation, University of York, 1997

45. P. Puschner and A. Burns. A review of WCET analysis. Real Time Systems: Special Issue on Worst-Case Execution-Time Analysis, 18(2/3), 2000, pp. 115-128.

46. K. Ramamritham. Allocation and Scheduling of Complex Periodic Tasks. ltfh International Conference on Distributed Computing Systems, Paris, France, June 1990.

47. K. Ramamritham, G. Fohler and J. M. Adan. Issues in Static Allocation and Scheduling of Complex Periodic Tasks. 10th IEEE Workshop on Real-Time Operating Systems and Software, May 1993.

48. K. Ramamritham, J. Stankovic, P.-F. Shiah. Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems. IEEE Transactions on Parallel and Distributed Systems, vol. 1, No. 2, April 1990, pp. 184-194

49. K. Ramamritham, J. Stankovic, W. Zhao. Distibuted Scheduling of Tasks with Deadlines and Resource Requirements. IEEE Transactions on Computers, 38(8):1110-23, August 1989

50. K. Ramamritham, J. Stankovic. Scheduling algorithms and Operating Systems Support for Real-Time Systems. Proceedings of the IEEE, vol. 82, no. 1, pp. 55-67, January 1994

51. R. Ramjee, J. Kurose, D. Towsley, H. Schulzrinne. Adaptive Playout mechanisms for packetized Audio Applications in Wide-Area Networks. Proceedings of the IEEE INFOCOM, Toronto, Canada, pp. 680-686, June 1994.

52. RTP: A Transport Protocol for Real-Time Applications. RFC 1889, http://www.faqs. org/rfcs/rfcl889. html

53. II. Simpson. Four-slot Fully Asynchronous Communication Mechanism. IEEE Proceedings Part E, 137(1), pp. 17-30, January 1990

54. L. Sha, J. Goodenough. Real-Time scheduling theory and Ada. Computer, vol. 23, no. 4, pp. 53-62, 1990

55. L. Sha, R. Rajkumar, J. Lehocky, K. Ramamritham. Mode Change Protocols for Priority-Driven Preemptive Scheduling. CMU/SEI-88-TR-34, Software Engineering Institute, November 1988.

56. L. Sha, R. Rajkumar, and J. Lehoczky. Priority Inheritance Protocols: An Approach to RealTime Synchronization. IEEE Transactions on Computers, 39(9): 1175-1185, September 1990.

57. L. Sha, R. Rajrumar, S.H. Son, C.H. Chang. A Real-Time Locking Protocol. IEEE Transactions on Computers, 40(7): 793-800, July 1991

58. L. Sha et al. Generalized Rate-monotonic Scheduling theory: A Framework for Developing Real-Time Systems. Proceedings of the IEEE, vol. 82, no. 1, January 1994

59. C. Shen, K. Ramamritham, J. A. Stankovic. Resource Reclaiming in Multiprocessor RealTime Systems. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(4):382-397.

60. J. A. Stankovic, M. Spun, M. Di Natale, G. Butazzo. Implications of Classical Scheduling Results for Real-Time Systems. IEEE Computer, June 1995, pp. 16-25.

61. J. A. Stankovic. Misconceptions About Real-Time Computing. IEEE Computer, vol. 21, No. 10, October 1988, pp. 10-19.

62. M. Spuri, G. Butazzo. Scheduling Aperiodic Tasks in Dynamic Priority Systems. Journal of Real-Time Systems, vol. 10, no. 2, 1996, pp. 1979-2012.

63. K. Tindell, H. Hansson. Real Time Systems by Fixed Priority Scheduling. DoCS, Uppsala University, 1997

64. K. Tindell, A. Burns, A. Wellings. Allocating Hard Real-Time Tasks (An NP-Hard Problem Made Easy). Real-Time Systems, vol. 4, No. 2, May 1992, pp. 145-165.

65. K. Tindell, A. Burns, A. Wellings. Guaranteeing Hard Real Time End-to-End Communications Deadlines. Technical Report RTRG/91/107, University of York, UK, December 1991.

66. S. Vestal. Fixed priority Sensitivity Analysis for Linear Compute Time Models. IEEE Transactions on Software Engineering, vol. 20, no. 4, April 1994, pp. 308-317.

67. TMS320C6000 Peripherals Reference Guide. Texas Instruments, SPRU190C, April 1999

68. TMS320C6000 Peripherals Reference Guide. Texas Instruments, SPRU190D, February 2001

69. TMS320C6000 Programmer's Guide. Texas Instruments, SPRU198F, February 2001

70. J. D. Ullman. Polynomial complete scheduling problems. Oper. Syst. Rev., vol. 7, No. 4, October 1973, pp. 96-101.

71. J. D. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, no. 10, October 1975, pp. 384-393.

72. W. Zhao, K. Ramamritham, J. Stankovic. Scheduling Tasks with Resource Requirements in Hard real-Time Systems. IEEE Transactions on Software Engineering, vol. SE-12, No. 9, September 1986, pp. 890-904.

73. E.C. Вентцель. Исследование операций. Москва, «Советскоерадио», 1972, 552 стр.

74. М. Данилов. Методы планирования выполнения задач в системах реального времени. Программные продукты и системы, №4, 2001, стр. 28-36.

75. В.П. Дашевский. Вероятностный анализ задач с буферизацией запросов в системах реального времени. Труды I Всероссийской научной конференции «Методы и средства обработки информации», Москва, 1-3 октября 2003, стр. 87-93.

76. В.П. Дашевский. Методика вероятностного анализа набора задач в системах реального времени с фиксированными приоритетами. Изд. «Политехника», журнал «Информационно-управляющие системы», №4, 2003, стр. 15-23.

77. В.П. Дашевский, И.В. Царев. Обобщенный подход к исследованию систем реального времени. Материалы VIII Санкт-Петербургской международной конференции «Региональная Информатика 2002», часть 1, стр. 31.

78. В.П. Дашевский. Сравнение основных дисциплин планирования в системах реального времени. Труды СПИИРАН, Выпуск 1, Том 3, 2002, стр. 91-98.

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

80. В.В. Никифоров, М.В. Перевозчиков. Ранжирование периодов задач в системах реального времени. Программные продукты и системы, №4, 1997, стр. 16-20.

81. М.В. Перевозчиков. Оптимизация общего периода выполнения приложения во встроенных системах реального времени. Программные продукты и системы, №4, 1997, стр. 20-24.

82. Утверждаю Руководитель предприятия (зам руководителя)1. АКТо внедрении результатов диссертационной работы

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

84. Реализация адаптивного алгоритма буферизации пакетов, который позволяет стабилизировать вероятность потери пакетов и повысить качество передаваемого акустического сигнала.