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

Чтя '

^ I 1' • - .. -' 4

'.' " ' " ' ' МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

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

УДК 519.685

Бочков Сергей Олегович

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

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

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

Москва - 1991

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

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

кандидат физико-математических наук Смелянский Руслан Леонидович

доктор физико-математических наук Томилин Александр Николаевич

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

доктор технических наук Сухомлин Владимир Александрович

доктор физико-математических наук Баранов Сергей Николаевич

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

Институт Кибернетики им. В.Ы.Глушкова АН УССР, г.Киев

Защита диссертации состоится 15 ноября 1991 г. в 11 ч. на заседании Специализированного Совета Д.053.05.38 N.4 при Московском государственном университете им. М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан !5~* [о .1991 Г.

Ученый секретарь специализированного совета Д.053.С5.38

профессор Н.П. Трифонов

Общая характеристика работы

Актуальность теш

Отладка как процесс поиска, локализации и исправления ошибок

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

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

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

Трудности, отладки программ для многопроцессорных вычислительных систем (ВС), для которых параллелизм описывается теорией взаимодействующих последовательных процессов (Ноаге c.A.R. Communicating sequential processes // Communications of the ACM.-1978.- V.21, N.8.- P.666-677.), связаны с тем, что разработанные методы и инструменты отладки последовательных программ не учитывают особенности параллельных программ и не предоставляют пользователю соответствующие средства. Важными задачами являются разработка методов отладки и автоматизация отладки параллельных программ.

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

Вопросами, связанными с различными аспектами автоматизации отладки программ, занимались многие отечественные и зарубежные ученые, например, Липаев В.В., Безбородов D.M.. Иценко Е.А.,

Brtnch Hansen P., Yiileden J., Degano R.

Работа выполнялась в рамках проводимых в лаборатории вычислительных. комплексов факультета Е!.!иК ЮТ исследований по теме "Исследование структур распределенных вычислительных систем и методов обработки информации в них", выполняемых по заданию ГННГ СССР И АН СССР, ГОС.per.N.0186011.2552.

Цель диссертационной работа

Цель настоящей работы - исследование возмозхностей автоматизации отладки программ на основе операционного описания их поведения.

Основные результаты работы

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

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

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

Научная новизна

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

2) Разработана экспериментальная автоматизированная система

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

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

Практическая ценность

1) Разработан и реализован отладчик для последовательных программ, написанных на языке Си. Отладчик работает на ЭВМ Электрони-ка-ео и СМ-4 под управлением ОС РАФОС, внедрен в 13 организациях.

2) Разработана и реализована экспериментальная автоматизированная система отладки параллельных програум в ОС ДИЛОС на ЭВМ СМ-4, внедренная в лаборатории вычислительных комшиясов факультета В№К МГУ.

Метода исследования. Теория формальных грамматик, теория алгоритмов, теория автоматов, теория трансляции, методы спецификации программ.

Апробация работы. Результаты диссертационной работы докладывались на конференциях молодых ученых факультета ВМиК МГУ (в 1987 и в 1988 гг.), на конференции "Применение микропроцессорной техники" (Свердловск, 1984), на конференции "Формальные модели параллельных вычислений" (Новосибирск, 1987), па семинарах рабочей группы по технологии разработки микропроцессорных вычислительных систем (Ташкент, 1588, Москва, 1988), на третьем региональном семинаре "Распределенная обработка информации" (Улан-Уде, 1989), неоднократно обсукдались на научных семинарах кафедры АСВК и лаборатории

вычислительных комплексов.

Публикации. Основные результаты диссертации изложены в 10 работах, список которых приводится в конце автореферата.

Структура диссертации. Диссертация состоит из введения, пяти глав, заключения, трех приложений и списка литературы из 72Г"наименова-ний. Общий объем диссертации без приложений - ¿^""страниц. Объем приложений - ¿^страниц.

Краткое содержание работы

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

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

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

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

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

Выбор иоделл поведения прогргкы. Существует два основных подхода к описанию работы программы: денотационный и операционный.

В денотационной подходе рассматривается отображение Ф:Х—>У набора входных данных в набор выходных, задаваемое программой. Это отображение состоит из последовательности отображений ф^ф^.-.ф^, производимых операторами программы. Состояние з1 определяется как результат отображения:

з. = ф. ( з. .), з. = { а , V. }, 1=1,... ,п,

V Т1 1-1 I I* I * * ' *

где а,- метка (номер) последнего выполненного оператора, V,-совокупность данных в момент завершения выполнения оператора.

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

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

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

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

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

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

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

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

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

Анализируются системы, базирующиеся как на операционном; так

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

Основные выводы проведенного анализа проблем и методов отладки:

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

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

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

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

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

Основные отличия отладчика (для сравнения выбрани наиболее широко известные отладчики для языка Си - Turbo Debugger фирмы Borland Int. И CodeView фирмы Microsoft):

a) Отладчик базируется на интерпретаторе, использующем специальное внутреннее представление программы, разработаное на основе языка логических схем Ляпунова, которое при изменении исходного текста программы корректируется без перетрансляции и перекомпановки программы.

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

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

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

e) Отладчик полностью написан на языке Си (содержит около 20000 строк) и является переносимым в новые ОС и на новые архитектуры ЭВМ.

Отладчик работает на ЭВМ типа СМ-4 и "Элекхроникa-SO" под

управлением операционной системы РАФОС. Пробные варианты отладчика были также запущены в ОС svs на ЭВМ ЕС-1045 (в этой версии отладчик позволял отлаживать свой собственный текст) и в ОС MS-DOS на эвм IBM-PC/at. Для распространения отладчика в этих системах необходимы дополнительно разработанный удобный интерфейс и сопровождение .

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

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

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

РЙДДЛ (Riddle W. An approach to software system behavior description // J.Computer Languages.- 1979-- Vol.4, N.1.- P.29-47.) предложил использовать для описания функционирования программного обеспечения аппарат event ехргезз1опз, который тоже является расширением аппарата регулярных выражений. Расширение Риддла заключается, во-первых, в добавлении операции тасовки {shuffle), Ео-вторых, в добавлении специальных символов синхронизации для операции тасовки, в-третьих, во введении операции dagger (тасовка цепочки самой с собой любое конечное число раз). Последняя операция выводит в масс рекурсивно перечислимых языков (порождаемых грамматиками типа 0). В той Ее работе отмечалось, что йспользова-

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

Предлагаемое в настояний работе расширение аппарата регулярных выражений имеет следующие характеристики:

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

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

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

4) вводится операция параллельной композиции (тасовки) для произвольного конечного числа языков.

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

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

программ, 2) простота и эффективность распознавания поведения, удовлетворяющего списанию.

Для задания модели поведения программы в рамках операционного подхода могут быть предложены различные механиста. В [7] описаны возможности применения темпоральных логин. В [ю] описаны возможности использования реляционного языка (техники баз данных).

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

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

Особое внимание уделяется способу введения .операции параллельной композиции, поскольку именно с параллелизмом связана особая сложность изучения поведения параллельных программ. Тем или иным способом еводя в язык описания модели операцию параллельной композиции, мы будем описывать тот или иной вид параллелизма (Смелянский Р.Л. Модель функционирования распределенных вычислительных систем // Вестн. Моск. Ун-та Сер.15. Еычисл.матем. и кибернетика.- 1990.- н.э.- 0.3-18.).

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

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

соответствия реального поведения программы модели, задаваемой пользователем,

В этой главе:

1) описывается алгоритм построения по специ{икациям программы конечного недетерминированного автомата специального вида для проверки соответствия между спецификациями и реальным поведением программы,

2) рассматриваются вопросы разработки автоматизированных систем-отладки для параллельных программ и в многопроцессорных ВС.

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

ЭСО реализована в ОС ДЕМОС (версия ОС UNIX) и является развитием отладчика ДИОС, описанного во второй главе. ЭСО предназначена для отладки программ, написаных на языке Си, состоящих из нескольких процессов, где процессы могут взаимодействовать при помощи стандартных средств ОС UNIX.

В свою очередь, ХО сама является многопроцессной системой, состоящей из следующих взаимодействующих частей:

- Главный процесс, который выполняет функции взаимодействия с программистом и управляет другими процессами ЭСО, а также осуществляет трансляцию программ, написанных на языке Си, во внутреннее представление интерпретатора.

- Набор процессов-интерпретаторов. Каждый интерпретатор выполняет один процесс пользовательской программы и собирает информацию о его выполнении.

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

В заключении формулируются основные результаты работы.

В приложении 1 содержится ратное руководство пользователя по отладчику ДИОС.

В приложении 2 содержится краткое руководство пользователя по экспериментальной автоматизированной системе отладки параллельных программ.

В приложении 3 приводится пример сеанса работы с экспериментальной системой отладки для поиска ошибки в параллельной про-

о

грамме.

Все представленные результаты получены автором самостоятельно и изложены в следующих работах:

1. Бочков С.О., Зелинский П.П., Смелянский Р. Л. Командный язык диалогового отладчика для языка Си // Труда семинара по микропроцессорной техники, Свердловск.- 1984.

2. Бочков С.О. Диалоговый символьный отладчик для языка Си // В Сб.: Технология программирования для микропроцессоров и микроЭВМ.- М. .-Знание, 1984.

3. Бочков С.О., Смелянский Р.Л. Символьный отладчик для языка Си // Микропроцессорные средства и системы.- 1987.- N.5.

4. Бочков С.О., Смелянский Р.Л. О двух моделях-отладки программ в распределенных вычислительных системах // Формальные модели параллельных вычислений /Под ред. В.Е.Котова. Новосибирск.- 1988.-с.159-165.

5. Бочков С.О., Смелянский Р.Л. Отладка программ в распределенных вычислительных системах (обзор) // Программирование.- 1988.-N.4.- С.68-81.

6. Бочков С.О. Две методики отладки программ для распределенных вычислительных систем на осноЕе анализа динамики'выполнения про-

граммы в терминах событий // Тр.Конф.Мол.Уч. факультета ВМиК МГУ 1987 г.- М..-ИЗД-В0 МГУ.- 1989.

7. Бочков С.О., Смелянский Р.Л. Средства описания поведения параллельных программ в целях отладки // Сб.: Вопросы технологии программирования.- Ленинград.- 1989.

8. Бочков С.О. Отладка параллельных программ на основе анализа динамических свойств // Сб.тез. докладов Третьего регионального семинара "Распределенная обработка информации", июль 1989 г.Новосибирск.- 1989.- С.33-35.

9. Бочков С.О., Кубрак В.А. Совместное использование интерпретации и трансляции при отладке программ // Программное обеспечение и модели системного анализа.- Ы:Кзд-во МГУ.- 1991.

10. Бочков С.О. Использование техники реляционных баз данных для анализа поведения параллельных программ // Программное обеспечение и модели системного анализа.- М:Изд-во МГУ.- 1991.

Подписано в печать 4.09.91 г. Формат 60x84/16. Объём 1,0 п.л. Тирак 100 экз. Заказ К 43. Бесплатно.

Ротапринт ШВЦ МГУ 119899, Москва, Ленинские горл.