Вероятностные методы оценки выполнимости задач в системах реального времени тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Дашевский, Владимир Павлович

• Дашевский, Владимир Павлович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Дашевский, Владимир Павлович

Введение.

Глава 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. При разработке программного обеспечения автором использовались развитые в работе методы вероятностного анализа задач с учетом влияния кэш-памяти на время выполнения задач.

Список литературы диссертационного исследования кандидат технических наук Дашевский, Владимир Павлович, 2004 год

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. Реализация адаптивного алгоритма буферизации пакетов, который позволяет стабилизировать вероятность потери пакетов и повысить качество передаваемого акустического сигнала.