Содержание к диссертации
Введение
Глава I. Проблема трассировки программ в современных отладочных и измерительных системах 13
1.1 Инструментальные методы и средства трассировки программ 13
1.2 Принципы рациональной трассировки потока управления в программах 26
1.3 Постановка задач рациональной трассировки программных событий в моделирующих системах с двухэтапной трассировкой 33
Выводы к главе I 54
Глава 2. Методы рационального размещения операторов трассировки элементарных программных событий 56
2.1 Разработка и исследование алгоритмов минимизации числа точек трассировки 57
2.2 Разработка и исследование алгоритмов минимизации длины слова трассировочной информации 82
2.3 Восстановление последовательности программных событий по управляющей трассе 94
Выводы к главе 2 99
Глава 3. Проблемы реализации методов рациональной трассировки программных событий 101
3.1 Особенности реализации методов рационального размещения операторов трассировки программных событий 102
3.2 Синхронизация трассировки потока управления и данныхП2
3.3 Методы динамического формирования схем элементарных nсобытий и управляющей трассы 116
Выводы к главе 3 133
Глава 4. Реализация системы отладки и измерения . 135
4.1 Разработка языковых средств трассировки и анализа программных событий 136
4.2 Особенности реализации алгоритмов динамического формирования схем элементарных событий . 143
4.3 Оценка эффективности методов рациональной трассировки программных событий 151
Выводы к главе 4 156
Заключение 158
Литература 161
Приложение I. Таблица элементарных программных событий ДИАМС/ЕС 173
Приложение 2. Описание команд моделирующей отладочной и измерительной системы в ДИАМС/ЕС 177
Приложение 3. Синтаксис сложного программного события, описанного с помощью регулярного выражения 183
Приложение 4. Некоторые тексты программ отладочной и измерительной системы 185
Приложение 5. Описание управляющих конструкций, использованных в обозначениях алгоритмов 226
Справки о внедрении 228
- Инструментальные методы и средства трассировки программ
- Разработка и исследование алгоритмов минимизации числа точек трассировки
- Особенности реализации методов рационального размещения операторов трассировки программных событий
- Разработка языковых средств трассировки и анализа программных событий
Инструментальные методы и средства трассировки программ
Важнейшей из характеристик программ является их поведение при выполнении на ЭВМ. Характер поведения программы проявляется во внешних производимых ей эффектах и определяется двумя факторами: с одной стороны, особенностями процессов и явлений, имеющих место в окружающей программу обстановке, и, с другой стороны, характером процессов, происходящих в самой программе. Первые представляют интерес с точки зрения управления поведением и использования программ, второй интересует, главным образом, разработчиков программ в процессе конструирования и наладки. Для выявления характера поведения программ разработаны специальные средства, обеспечивающие отслеживание процессов и явлений, происходящих во время выполнения программ. Эти средства называются средствами трассировки программ.
В настоящее время можно выделить два основных направления в развитии и использовании средств и методов трассировки программ. Первое направление связано с развитием и использованием средств и методов отладки программ [ f, 5" 5 Q ,55,28.]. Трассировка применяется в этом случае как средство получения информации о внутренних процессах и явлениях, которая затем используется при выяснении причин некорректного поведения тестируемой системы. Необходимость использования средств трассировки в процессе отладки объясняется исключительной способностью программ к длительному наследованию и, как следствие, значительному искажению первоначально возникших аномалий в поведении тестируемых программ.
Второе направление связано с разработкой методов и средств измерения количественных характеристик процессов,протекающих во время выполнения программ. К таким средствам относятся средства для измерения временных и ёмкостных характеристик реализованных алгоритмов и про грамм [39,26,33 08,5 ,42), средства оценки полноты тестирования [104,92,105} и др. Использование методов трассировки в этом случае объясняется чрезвычайной сложностью применения аналитических методов решения задач измерения.
Отдельно можно выделить область использования методов трассировки для нужд регистрации внешних по отношению к программному обеспечению явлений. К средствам регистрации, использующим методы трассировки, относятся средства ведения статистического учёта работы оборудования ЭВМ [3# , 50 J 9 средства учёта выполнения заданий в операционных системах [45", Е 1 J , системные журналы банков данных [3,29] и некоторые другие.
Несмотря на большое разнообразие существующих отладочных, измерительных и прочих систем, использующих методы трассировки, способов их реализации и режимов функционирования,можно выделить несколько основных принципов, используемых при проектировании средств трассировки. С точки зрения характера получаемой трассировочной информации,можно различать три способа трассировки: трассировку потока управления, трассировку данных и трассировку событий.
Разработка и исследование алгоритмов минимизации числа точек трассировки
Условия задачи о минимальной достаточной разметке предполагают поиск двух неизвестных: функции разметки /(с)и набора сечений С є. С(о). Однако задача значительно упрощяется, т.к. справедлива следующая
Теорема 2.1. Если / , о - произвольные однозначные функции разметки, а п - произвольная неоднозначная функция разметки такая, что существует хотя бы один достаточно размечающий граф ЭС НТТ {ц, п(с) j, где: Cf- С (о) , то число элементов в минимальных достаточно размечающих НТТ \Сз,$(Сцтл. \СО , О (с)(совпадает и не превосходит числа элементов в
Следовательно, HTTQ,7/(C)] является достаточно размечающим набором. Но тогда НТТ {tyT/(c)j - не минимальный достаточно размечающий НТТ, что противоречит условиям теоремы. Конец доказательства.
Таким образом, считая, что /(с) - однозначная функция разметки, будем искать такой набор сечений С и для которого бы НТТ[0»іпг-/(с)]являлся достаточно размечающим и содержал минимальное число точек трассировки. Будем полагать также, что приведенный набор сечений C(S) и полный набор сечений C(S) совпадают, и не учитывать пока ограничений пользователя на полноту трассировки.
Перейдём теперь к поиску решения. Рассмотрение начнём со случая, когда граф 5 ациклический.
Согласно [?05]для ациклического графа 6 задача сводится к поиску максимального подграфа 5т графа 5 , обладающего следующими свойствами:
Тогда НТТ{_ЧОІ»І, f(z\\содержит сечения, обладающие следующим свойством: если дуга (бс,Є/)еС, причём сєС , ТО(ОІО:)Є U-Un . Таким образом, даже для ациклического графа 5 получение НТТ j min » f(c)} является трудной задачей [Ю5]. Поэтому более целесообразен подход, при котором строится эвристический алгоритм, обеспечивающий быстрое получение оптимальных решений для какого-либо распространённого класса программ и решений, сколько-нибудь лучших, чем НТТ {_Со , ( 0для остальных классов программ.
Особенности реализации методов рационального размещения операторов трассировки программных событий
Во второй главе рассмотрена задача о минимальной достаточной разметке в предположении, что приведенный набор сечений графа ЭС совпадает с полным набором сечений. Исследуем особенности решения этой задачи в случае, если некоторые сечения графа ЭС недоступны для размещения точек трассировки.
Очевидно, что приведенный набор сечений не обязательно гарантирует существование достаточно размечающего НТТ. Как уже указывалось в разделе 1.3, в таком случае задачу о минимальной достаточной разметке следует решать как задачу о поиске минимального количества точек трассировки, различающих максимально возможное количество маршрутов в графе ЭС, т.е. всех маршрутов, которые различались бы точками трассировки, расположенными в каждом доступном сечении. Получаемый при решении этой задачи НТТ не гарантирует различия трасс всех возможных маршрутов и, следовательно, не может достоверно идентифицировать факт возникновения некоторых ЭС в программах пользователя. Строго говоря, вопрос о доступности сечений и, следовательно, об идентифицируемости ЭС должен рассматриваться на этапе проектирования средств трассировки при выборе набора регистрируемых ЭС. Очевидно, что выбор типов трассируемых ЭС должен производиться на основе анализа мест расположения соответствующих операторов трассировки и гарантировать с большой вероятностью возможность размещения этих операторов. В противном случае принципиальная возможность трассировки некоторых ЭС с помощью разрабатываемых средств трассировки практически не будет обеспечиваться в процессе эксплуатации. Таким образом, недоступность некоторых сечений графа ЭС для размещения в них точек трассировки следует рассматривать как маловероятное явление, и поэтому требования к эффективности размещения точек трассировки в этих условиях могут быть снижены.
Наиболее рациональным способом решения проблемы является разработка метода размещения точек трассировки в условиях ограниченной доступности сечений графа ЭС на основании методов, описанных во второй главе. Однако, прежде чем приступить к обсуждению этого метода, рассмотрим одну важную особенность принятого в качестве основного алгоритма рационального размещения точек трассировки - алгоритма 2.3. Работа этого алгоритма состоит из двух этапов. На первом этапе выполняется расстановка точек трассировки всех простых циклов, на втором - остальных точек трассировки с учётом уже расставленных на первом этапе. Последняя особенность алгоритма автоматически обеспечивает решение проблемы учёта предварительно размещённых операторов трассировки в программах инструментальных и операционных средств. Необходимость решения этой проблемы указывалась в разделе 1.3. Кроме того, отмеченное свойство алгоритма 2.3 может быть использовано, например, для организации трассировки последовательности ЭС за счёт трассировки абсолютно переменных аргументов, если операторы трассировки абсолютно переменных аргументов устроить таким образом, чтобы можно было выводить необходимую для трассировки последовательности ЭС информацию в управляющую составляющую БДТ. Указанное свойство алгоритма 2.3 может быть полезным и при расстановке НТТ в условиях ограниченной доступности сечений графа ЭС. Рассмотрим эту задачу подробнее.
Разработка языковых средств трассировки и анализа программных событий
ДИАМС/ЕС является диалоговой многотерминальной системой, ориентированной на программирование задач информационно-поискового характера и обеспечивает следующие прикладные возможности: программирование на процедурном языке высокого уровня с развитой системой команд, функций и операций[2б] ; выполнение команд пользователя в программном режиме или в режиме калькулятора; создание и ведение баз данных древовидной структуры; организацию логического ввода/вывода для нескольких типов периферийных устройств; коллективный доступ логически неограниченного числа пользователей к разделяемым по времени ресурсам системы с локальных терминалов; защиту системы и баз данных от несанкционированного доступа; создание асинхронных программ и организацию связи с другими ЭВМ.
Стандартно обеспечиваемые средства отладки предоставляют возможность приостанова выполнения программ с просмотром состояния и модификацией переменных в момент приостанова, возобновление выполнения и нестандартную обработку ненормальных завершений. Язык ДИАМС относится к классу интерпретируемых языков и допускает возможность модификации программ во время выполнения.
Перечисленные возможности ДИАМС/ЕС определяют необходимость использования разработанного в третьей главе диссертации метода и алгоритмов динамического формирования схемной и управляющей составляющих ДЦТ при построении моделирующей отладочной и измерительной системы с двухэтапной трассировкой и,кроме того, предполагают создание диалоговой системы отладки и измерения с интерпретируемыми языковыми средствами, встроенными в ДИАМС/ЕС.
Анализ языковых средств и режимов функционирования ДИАМС/ЕС приводит к организации системы элементарных программных событий с числом постоянных и относительно постоянных аргументов, не превышающим двух. В приложении I приведён полный перечень ЭС, трассируемых системой. Четыре события имеют абсолютно переменные аргументы. При выполнении присваиваний переменным пользователя и некоторым системным переменным в информационную составляющую БДТ заносятся два аргумента: имя переменной ( с индексами, если это элемент массива ), значение которой было изменено, но и новое значение. При выполнении команды уничтожения переменной пользователя в информационную составляющую заносится имя удаляемой переменной ( с индексами, если удаляется элемент или часть массива ), при выполнении команды захвата в монопольное использование поддерева базы данных - имя поддерева базы данных. Команды, вызывающие синхронизацию различных подзадач, например, команды захвата устройства и поддерева базы данных в монопольное использование и некоторые другие, приводят к генерации события "синхронизация подзадач" ( см.приложение І ), а в информационную составляющую записывается текущее состояние БДТ подзадачи, с которой была выполнена синхронизация.
