Войти
Время выполнения в худшем случае (WCET ) вычислительной задачи - это максимальное время, которое может потребоваться для выполнения задачи на конкретной аппаратной платформе.
Худшее Время выполнения case обычно используется в надежных системах реального времени, где понимание наихудшего временного поведения программного обеспечения важно для надежности или правильного функционального поведения.
В качестве примера компьютерной системе, которая контролирует поведение двигателя в транспортном средстве, может потребоваться реагировать на входные данные в течение определенного промежутка времени. Одним из компонентов, составляющих время отклика, является время, затрачиваемое на выполнение программного обеспечения - следовательно, если можно определить наихудшее время выполнения программного обеспечения, то разработчик системы может использовать его с другими методами, такими как анализ планируемости чтобы система реагировала достаточно быстро.
Хотя WCET потенциально применим ко многим системам реального времени, на практике гарантия WCET в основном используется системами реального времени, которые связаны с высокой надежностью или безопасностью. Например, в бортовом программном обеспечении необходимо уделить внимание программному обеспечению в соответствии с разделом 6.3.4 DO178B. Растущее использование программного обеспечения в автомобильных системах также вызывает потребность в использовании анализа программного обеспечения с помощью WCET.
При разработке некоторых систем WCET часто используется в качестве входных данных для анализа планируемости, хотя гораздо более распространенное использование WCET в критических системах - гарантировать, что заранее выделенное время бюджеты в системе с расписанием разделов, такой как ARINC 653, не нарушаются.
С первых дней встраиваемых вычислений разработчики встроенного программного обеспечения либо использовали:
Оба эти метода имеют ограничения. Сквозные измерения ложатся тяжелым бременем на тестирование программного обеспечения для достижения максимально длинного пути; Инструкции по подсчету применимы только к простому программному и аппаратному обеспечению. В обоих случаях запас на ошибку часто используется для учета непроверенного кода, приближения производительности оборудования или ошибок. Часто используется маржа в 20%, хотя для этой цифры используется очень мало обоснований, за исключением исторической достоверности («это сработало в прошлый раз»).
По мере усложнения программного и аппаратного обеспечения возникла потребность в поддержке инструментов. Сложность становится все более серьезной проблемой как при статическом анализе, так и при измерениях. Трудно судить, какой должна быть допустимая погрешность и насколько хорошо протестирована программная система. Аргументы системной безопасности, основанные на высокой отметке, достигнутой во время тестирования, широко используются, но их становится труднее обосновать, поскольку программное и аппаратное обеспечение становится менее предсказуемым.
В будущем, вероятно, потребуется, чтобы критически важные для безопасности системы требовали их анализа с использованием как статического, так и основанного на измерениях подходов.
Проблема нахождение WCET с помощью анализа эквивалентно проблеме остановки и поэтому в общем случае неразрешимо. К счастью, для систем, для которых инженеры обычно хотят найти WCET, программное обеспечение обычно хорошо структурировано, всегда завершается и его можно анализировать.
Большинство методов поиска WCET включают приближения (обычно округление в большую сторону при наличии неопределенностей), и поэтому на практике сам точный WCET часто считается недостижимым. Вместо этого различные методы поиска WCET дают оценки WCET. Эти оценки обычно пессимистичны, что означает, что предполагаемый WCET, как известно, выше, чем реальный WCET (что обычно является желаемым). Большая часть работы по анализу WCET направлена на снижение пессимизма в анализе, чтобы расчетное значение было достаточно низким, чтобы быть ценным для разработчика системы.
Анализ WCET обычно относится ко времени выполнения отдельного потока, задачи или процесса. Однако на современном оборудовании, особенно многоядерном, другие задачи в системе будут влиять на WCET данной задачи, если они совместно используют кеш, линии памяти и другие аппаратные функции. Кроме того, в анализе WCET следует учитывать такие события планирования задач, как блокировка или прерывания, если они могут возникать в конкретной системе. Поэтому важно учитывать контекст, в котором применяется анализ WCET.
Существует много автоматизированных подходов к вычислению WCET, помимо описанных выше ручных методов. К ним относятся:
Статический инструмент WCET пытается оценить WCET, исследуя компьютерное программное обеспечение, не выполняя его непосредственно на оборудовании. Методы статического анализа преобладали в исследованиях в этой области с конца 1980-х годов, хотя в промышленных условиях методы сквозных измерений были стандартной практикой.
Инструменты статического анализа работают на высоком уровне, чтобы определить структуру задачи программы, работая либо с фрагментом исходного кода, либо с дизассемблированным двоичным кодом исполняемый. Они также работают на низком уровне, используя временную информацию о реальном оборудовании, на котором будет выполняться задача, со всеми его специфическими функциями. Комбинируя эти два вида анализа, инструмент пытается определить верхнюю границу времени, необходимого для выполнения данной задачи на данной аппаратной платформе.
На низком уровне статический WCET-анализ усложняется наличием архитектурных функций, улучшающих среднюю производительность процессора : кеши инструкций / данных , предсказание переходов и конвейеры команд, например. Возможно, но становится все труднее определить жесткие границы WCET, если эти современные архитектурные особенности учтены во временной модели, используемой при анализе. Например, методы блокировки кэша могут использоваться для упрощения оценки WCET и обеспечения предсказуемости.
Органы сертификации, такие как Европейское агентство по авиационной безопасности, поэтому полагаются на комплекты проверки моделей.
Статический анализ дал хорошие результаты для более простого оборудования, однако возможное ограничение статического анализа заключается в том, что оборудование (в частности, ЦП) достигло сложности, которую чрезвычайно трудно моделировать. В частности, в процессе моделирования могут возникать ошибки из нескольких источников: ошибки в конструкции микросхемы, отсутствие документации, ошибки в документации, ошибки при создании модели; все приводит к случаям, когда модель предсказывает поведение, отличное от наблюдаемого на реальном оборудовании. Как правило, когда невозможно точно предсказать поведение, используется пессимистический результат, который может привести к тому, что оценка WCET будет намного больше, чем все, что было достигнуто во время выполнения.
Получение точной статической оценки WCET особенно сложно на многоядерных процессорах.
Существует ряд коммерческих и академических инструментов, реализующих различные формы статического анализа.
Основанные на измерениях и гибридные подходы обычно пытаются измерить время выполнения сегментов короткого кода на реальном оборудовании, которые затем объединяются в анализе более высокого уровня. Инструменты принимают во внимание структуру программного обеспечения (например, циклы, ветви), чтобы произвести оценку WCET более крупной программы. Причина в том, что в сложном программном обеспечении сложно протестировать самый длинный путь, но легче протестировать самый длинный путь во многих более мелких компонентах. Эффект наихудшего случая необходимо увидеть только один раз во время тестирования, чтобы анализ мог объединить его с другими событиями наихудшего случая в своем анализе.
Как правило, небольшие участки программного обеспечения можно измерить автоматически, используя такие методы, как инструментарий (добавление маркеров в программное обеспечение) или с помощью аппаратной поддержки, такой как отладчики и модули трассировки оборудования ЦП. Эти маркеры приводят к трассировке выполнения, которая включает как путь, пройденный через программу, так и время, в которое были выполнены различные точки. Затем трассировка анализируется, чтобы определить максимальное время, которое когда-либо потребовалось для выполнения каждой части программы, каково максимальное наблюдаемое время итерации каждого цикла и есть ли какие-либо части программного обеспечения, которые не были протестированы (Покрытие кода ).
Анализ WCET на основе измерений дал хорошие результаты как для простого, так и для сложного оборудования, хотя, как и статический анализ, он может страдать излишним пессимизмом в многоядерных ситуациях, когда трудно определить влияние одного ядра на другое.. Ограничение измерения состоит в том, что оно основано на наблюдении наихудших эффектов во время тестирования (хотя и не обязательно в одно и то же время). Может быть трудно определить, обязательно ли проверялись эффекты наихудшего случая.
Существует ряд коммерческих и академических инструментов, реализующих различные формы анализа на основе измерений.
Наиболее активные исследовательские группы находятся в Швеции (Мелардален, Линчёпинг), Германии (Саарбрюккен, Дортмунд, Брауншвейг), Франции (Тулуза, Сакле, Ренн), Австрии (Вена), Великобритания (Йоркский университет и Rapita Systems Ltd), Италия (Болонья), Испания (Кантабрия, Валенсия) и Швейцария (Цюрих). В последнее время тема временного анализа на уровне кода привлекла больше внимания за пределами Европы исследовательскими группами в США (Северная Каролина, Флорида), Канаде, Австралии, Бангладеш (MBI LAB и RDS), Королевстве Саудовская Аравия-UQU (HISE LAB) и Сингапур.
Первый международный WCET Tool Challenge прошел осенью 2006 года. Он был организован Университетом Мелардален и спонсирован сетью ARTIST2 Network of Превосходство в проектировании встроенных систем. Целью конкурса было изучить и сравнить различные подходы к анализу наихудшего времени выполнения. Участвовали все доступные инструменты и прототипы, способные определять безопасные верхние границы WCET задач. Окончательные результаты были представлены в ноябре 2006 г. на Международном симпозиуме в Пафосе, Кипр.
Второй вызов произошел в 2008 году.
