Содержание к диссертации
Введение
ГЛАВА I. Автоматизация анализа структур сложных систем как срещство повышения надежности их функционирования 9
1.1. Постановка задачи автоматизации структурного анализа сложных систем 9
I.I.I.Основные положения, связанные с проектированием сложных систем 9
1.1.2. Постановка общей задачи надежностного проектирования систем 12
1.1.3. Обзор существующих систем автоматизации проектирования 16
1.1.4. Постановка задачи автоматизации декомпозиции сложных систем 22
1.2. Обзор и анализ методов оценки надежности сложных систем (АСУ и ПО) 24
1.3. Надежность программного обеспечения 42
1.4. Связь надежности и анализа сложных систем . 46
1.5. Постановка задачи структурной декомпозиции сложных систем на примере ПО 52
1.5.1. Обзор методов анализа сложных систем 52
1.5.2. Постановка задачи 58
Выводы по первой главе 62
ГЛАВА П. Математическая модель задачи структурной декомпозиции сложных систем (ПО) 64
2.1. Анализ методов описания программ 64
2.2. Агрегативный подход к описанию сложных систем .. 71
2.3. Алгебра операции декомпозиции DEC 81
2.4. Алгоритмы декомпозиции 95
Выводы по второй главе НО
ГЛАВА Ш. Программная реализация метода декомпозиции сложных систем 112
3.1. Общее описание системы автоматизации проектирования СДКМС 112
3.2. Блок "Декомпозитор" (DEC) 118
3.2.1. Структура блока DEC 118
3.2.2. Информационное обеспечение блока DEC 123
3.3. Программное обеспечение блока "Декомпозитор".. 126
3.4. Язык декомпозиции как подмножество языка схем систем L 148
3.5. Экспериментальная проверка алгоритмов декомпозиции на примере ПО 154
Выводы по третьей главе 172
Заключение Литература .
Приложение i 187
Приложение П 219
- Постановка задачи автоматизации декомпозиции сложных систем
- Агрегативный подход к описанию сложных систем
- Общее описание системы автоматизации проектирования СДКМС
- Экспериментальная проверка алгоритмов декомпозиции на примере ПО
Введение к работе
В решениях ХХУТ съезда КПСС среди основных задач одиннадцатой пятилетки названа задача автоматизации проектно-конструк-торских и научно-исследовательских работ с применением ЭВМ.
Технический уровень и качество создаваемых машин, сооружений и систем определяются в ходе проектных, конструкторских и технологических разработок и зависят от проектировщика, объекта и процесса проектирования. Решающее влияние на показатели качества и надежности оказывает технология проектирования. Применение ЭВМ в процессе проектирования позволит повысить эффективность технологии за счет улучшения технико-экономических характеристик объектов (надежности, эффективности, устойчивости и др.), уменьшения затрат на производство и эксплуатацию изделий, сокращения процесса проектирования, использования формальных подходов в проектировании.
Применение ЭВМ в проектировании особенно эффективно тогда, когда от отдельных инженерных расчетов переходят к комплексной автоматизации, создавая для этой цели системы автоматизированного проектирования (САПР).
САПР включает комплекс средств автоматизации проектирования и коллектив людей, управляющих этим комплексом [32J.
Автоматизация проектирования (АП) призвана повысить быстродействие, универсальность, алгоритмическую надежность машинних методов проектирования и распространить эти методы на новые проектные операции.
В СССР и за рубежом работы по АП получили большое развитие. Так особенно значительные успехи по применению САПР достигнуты в радиоэлектронике, машиностроении и строительстве [45].
Существенный вклад в создание САПР внесли такие советские ученые и инженеры, как Н.П.Бусленко, М.А.Гаврилов, В.М.Глушков, М.Я.Матюхин и др. [16,23,26,27,82,83].
Одним из перспективных и актуальных направлений развития автоматизированного проектирования является АП сложных программных систем, таких как: программное обеспечение (ПО) АСУ, пакеты прикладных программ (ППП), операционные системы, трансляторы, системы управления базами данных и др. Работы по данному направлению ведутся в Институте проблем управления [63,64,75, 76,91,96,105], НПО "Ленэлектронмаш" [40,41] и в других организациях [8,9,47,49,53,85,86].
Потребности в ПО постоянно возрастают. Годовой прирост программной продукции для СССР и США составляет 15% и 23% соответственно [бЗ]. Затраты на разработку ПО составляют 60% общей трудоемкости разработки систем обработки данных (СОД) в целом, причем в текущем десятилетии предполагается их увеличение до 90% общей трудоемкости[бЗ]. Это обусловлено сложностью написания и отладки ПО, стоимостью перепрограммирования и т.д., т.е. слолшостью сопровождения ], и низкой производительностью труда программистов. По данным Союзсистемпрома капитальные затраты на разработку и внедрение АСУ предприятием, одной из основных компонент которой является ПО, составляют 800 тыс. рублей[77]. Так в США затраты на разработку ПО составили 20 млрд долларов в 1970 г. и к 1985 г. возрастут по прогнозам до 200 млрд долларов [63 ].
Все это послужило причиной создания САПР ПО, позволяющих снизить трудоемкость проектирования, повысить надежность и качество ПО. В последнее время вопросам надежности ПО уделяется большое внимание. Им посвящены работы таких советских и зарубежных ученых, как В.В.Дружинин, В.В.Липаев, В.В.Шураков,Т.Тей-ер, Э.Нельсон, Г.Майерс и др.[39,69-71,104,97,74,29,34,98,108 - 6 ИЗ, 116,118,120].
Для разработки САПР необходимо иметь формальные методы, описывающе как сами объекты, так и этапы проектирования. Тогда весь процесс проектирования сложных систем можно свести к машинным методам анализа и синтеза В диссертации предлагается формальный подход к описанию объекта и этапов проектирования, конструктивное решение которого реализуется в виде системы проектирования структур сложных систем (на логическом уровне) - "Системы декомпозиции, композиции и модификации сложных систем"(СДКМС). Разработки проводились совместно с группой МЭСИ, возглавляемой Т.Я.Данелян.
Настоящая работа посвящена разработке средств автоматизации анализа структур сложных систем, в частности, ПО АСУ, и исследованию влияния автоматизации процесса анализа на качество создаваемых систем.
В соответствии с этим в диссертационной работе решаются следующие задачи:
1. исследование и анализ моделей оценки надежности такого класса систем, как ПО;
2. исследование влияния автоматизации процесса анализа на надежность проектируемых систем;
3. анализ методов описания программ;
4. выбор и разработка инструментальных средств анализа сложных систем с последующим внедрением их для анализа ПО.
Методика исследования основана на применении теории графов, теории автоматов, математической теории надежности, теории схем программ, методов математической логики, теории сложных систем и теории агрегатов, а также положений и результатов теории и практики программирования.
Научная новизна работы определяется следующими результатами:
- построена модель оценки надежности ПО, учитывающая только отказы, связанные с ошибками в самих программах;
- сформулирован критерий корректности агрегативных схем (А-схем), описывающих программы;
- доказаны теоремы о полноте и независимости для системы базовых операций над А-схемами; эта система составляет базовую частичную универсальную алгебру или базовую алгебру агрегатов;
- показана вычислимость операции декомпозиции (элементной, объектной, уровневой) с использованием операций базовой алгебры агрегатов;
- разработаны алгоритмы декомпозиции схем ПО;
- построено языковое подмножество языка описания схем систем L , используемое при реализации алгоритмов декомпозиции в режиме интерпретатора и в интерактивном режиме.
Практическая ценность. Основные результаты диссертации получены автором в ходе выполнения работ по хоздоговорным темам №81028500 и №76847697 и госбюджетной теме "Разработка математического обеспечения САПР", ведущимся в МЭСИ. Разработанный комплекс программ составляет блок "Декомпозитор" системы СДКМС. Общий объем программ составляет более 3000 операторов ПИ/1, Блок может использоваться в автономном режиме.
Апробация работы и публикации. Результаты работы докладывались на семинарах кафедры "Высшая математика" МВ1У им.Н.Э.Баумана, на семинарах "Однородные вычислительные системы" при НТОРЭС им.А.С.Попова (февраль 1983 г.) и "Повышение эффективности оценок надежности в натурных и имитационных экспериментах" (Одесса, сентябрь 1983 г.), на Всесоюзной конференции "Анализ эффективности и качества проектирования и функционирования АСУ в народном хозяйстве" (Москва, октябрь 1983 г.), на научно-техническом семинаре "Надежность в технике" (Горький, октябрь 1983 г.).
По теме диссертации опубликовано 6 работ.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из 120 наименований и двух приложений. Работа содержит 135 страниц машинописного текста, 35 рисунков, 12 таблиц, 49 страниц приложения.
В работе над диссертацией большую помощь оказали научный руководитель профессор Г.Д.Карташов и доцент,кандидат экономических наук Т.Я.Данелян, которым автор выражает глубокую благодарность.
Постановка задачи автоматизации декомпозиции сложных систем
Сформулируем задачу автоматизации декомпозиции сложных систем [92]. Дано: пусть имеется некоторое множество систем S = {Sml. одного класса. Система состоит из совокупности взаимосвязанных объектов (элементов) ={l\l , Множество элементов системы и информационное множество Г составляют предметное множество V. ; Л = иГ, где: I-XuY , X - множество входных воздействий; У - множество выходных воздействий. Задано операционное множество W над объектами множества Е. Общую структуру системы р ( Sm) определим следующим образом: где jo.f ) Р (Sm) р (S ) информационная, объектная (элементная) и функциональная структуры системы. Для системы задаются функционал качества S" , функция управления Ф. Поведение системы можно описать с помощью функции & . Для элементов вс задаются показатели надежности R, . Задаются множество критериев Н » множество ограничений D , задаваемых пользователем или проектировщиком, множество ограничений К , накладываемых на систему средой реализации.
Для описания элементов системы 6 и связей между ними выбирается некоторый математический аппарат з6 ; М - множество ограничений, накладываемых на систему в зависимости от используемой математической модели.
Необходимо: автоматизировать (формализовать) процесс декомпозиции (анализа) некоторого класса систем S в целях реализации его на ЭВМ в соответствии с заданными ограничениями и критериями.
Для автоматизации процесса декомпозиции необходимо выполнить следующие этапы:
1. выбрать математическую модель, позволяющую адекватно описывать сложные системы;
2. разработать конструктивный способ задания структурных связей;
3. исследовать операционное множество, с помощью элементов которого можно выполнять структурное, информационное и функциональное преобразование систем, т.е. разработать алгебру систем;
4. выбрать средства, позволяющие определять оптимальность
и работоспособность системы в конкретных условиях ее функционирования при конкретных ограничениях, накладываемых на ресурсы и среду реализации;
5. разработать формальный язык описания и преобразования структур систем;
6. разработать ПО для выполнения анализа систем, т.е. разработать подсистему автоматизированного анализа.
Подсистема анализа не является замкнутой, она входит в качестве одного из основных блоков в состав системы СДКМС. Принципы ее разработки полностью согласуются с целью и принципами системы СДКМС, но в то же время подсистема анализа может функционировать и автономно.
Все вышеперечисленные этапы будут рассмотрены в работе в объеме, необходимом для автоматизации процесса декомпозиции.
Настоящая работа посвящена автоматизации декомпозиции структур такого класса сложных систем как ПО. Специфика проектирования ПО позволяет рассматривать его на уровне как алгоритмов, так и программ, представленных с помощью блок-схем.
Интерес к анализу сложных структур возник давно. Одна из первых работ в этой области,касавшаяся моделей нейронных сетей, - работа Дж. фон Неймана/ 79J - была опубликована в 1952 г. В ней рассматривалась проблема построения надежных систем из ненадежных элементов релейного типа. Идеи, изложенные в этой работе, были затем развиты Лоуэнщуссом, %ром и Шэнноном, которые рассмотрели широкий класс сетевых структур.
Одной из первых отечественных работ, в которой рассматривалась непосредственно структура информационно-управляющей системы, явилась работа fl02].
Рассмотрение систем со сложной сетевой структурой расширило круг вероятностно-временных характеристик функционирования: кроме показателей надежности,такие системы оказалось удобным характеризовать показателями эффективности. При отказах отдельных элементов и даже целых подсистем, система не всегда теряет работоспособность, зачастую снижается эффективность ее функционирования.
Так для АСУ основные факторы, влияющие на надежность, и элементы АСУ можно разделить на две группы (рие.1.2)[28]:
1. аппаратурные (технические), т.е. такие, которые не зависят от состояния аппаратуры и ее элементов;
2. неаппаратурные, которые не зависят от состояния аппаратуры, но влияют на функциональную надежность.
Агрегативный подход к описанию сложных систем
Агрегат является динамической системой, позволяющей единообразно описывать все элементы системы (дискретные, непрерывные, детерминированные, стохастические), и используется для описания широкого класса объектов [1б].
Понятие агрегата было введено Бусленко Н.П.[17].
Определение 2.IJJ7]. Агрегат есть объект, определяемый множествами Т,Х,Г, Y,Z и операторами (вообще говоря, случайными) Н и G (С= Т,Х,Г, V,Z , Н,(т ) , где Т - фиксированное подмножество множества действительных чисел, f",X,Y,Z - множества любой природы.Элементы указанных множеств называют так: ЬєТ -моментом времени, re еХ - входным, а є Г - управляющим, иеУ - выходным сигналами, 2с - состоянием. Состояние, входные, выходные и управляющие сигналы можно рассматривать как функции времени %(t)9 х(і), ЦІЇ), j(t)» Операторы Н и G реализуют функции (t) и ЧІЬ)» Элементы множеств Х,Г, Y поступают на определенный вход или выход агрегата.
При использовании агрегата для описания сложных систем систему рассматривают как совокупность конечного числа агрегатов С: 9 jJt со связями между ними, а агрегат - как элемент системы. Взаимодействие агрегатов соответствует ряду предположений
Предположение 2.1. Взаимодействие между системой и внешней средой и между агрегатами внутри системы осуществляется посредством передачи сигналов; взаимные влияния, имеющие место вне механизма обмена, не учитываются.
Предположение 2.2. Для описания сигнала достаточно некоторого конечного набора характеристик. Так, входной сигнал ХбХ
. Сигналы, поступающие в агрегаты системы из внешней среды, являются выходными сигналами агрегата Со вида
Предположение 2.4. Элементарные сигналы передаются в системе независимо друг от друга по элементарным каналам; каждый элементарный канал, подключенный к выходу агрегата С; , способен передавать только элементарные сигналы, принадлежащие одному из мно-жеств Yf. . Вход агрегата представляют как совокупность п входных контактов ("клемм); контакт X;. предназначен для приема эле ментарных сигналов Х-1. (t)eX L. , t; " 4,П;. Управляющий вход аг ф с\ ( )
Предположение 2.5. К каждому входному или управляющему контакту подключается только один элементарный канал, к выходному контакту может быть подключено любое конечное число элементарных каналов при условии, что ко входу одного и того же агрегата направляется только один из этих каналов.
Оператор R , называемый оператором сопряжения, реализует отображение [Хг] - ЕХЛ-f с областью определения во множестве [XJ и областью значений во множестве [Ye] Y = R (X ), і, к = О, і,..., N , которое данному контакту Л; е L л І J А ставит в соответствие единственный контакт Ye є [Yg] , соединенный с ним элементарным каналом.
Общее описание системы автоматизации проектирования СДКМС
Система СДКМС является инструментальным средством проектировщика и предназначена для АП сложных систем, в частности, ПО АСУ. Система СДКМС разрабатывается в МЭСЙ под руководством Да-нелян Т.Я.
Структурная схема системы СДКМС представлена на рис. 3.1 [93].
Блок I "Композитор" реализует оператор сопряжения R ( по Бусленко). Блок П "Модификатор" реализует оператор MOD, осуществляющий модификацию системы. Блок Ш "Декомпозитор" выполняет операцию декомпозиции DEC . Блок ІУ "Имитатор" осуществляет имитационное моделирование разработанной системы. Блок У "Вывод результатов" относится к вспомогательным блокам. Он может включаться по желанию пользователя после каждого блока. Блок УІ "Библиотекарь" выполняет все работы, связанные с созданием, корректировкой и сопровождением базы агрегатов BAZA и банка агрегативных структур BASA . Связь между блоками выполняется с помощью переключателей P2,F3, Р6, Р5. Система СДКМС работает в трех режимах:
1. интерактивном режиме работы с пользователем;
2. режиме интерпретации программы, написанной на языке описания схем систем L ;
3. автономном режиме, когда каждый блок работает самостоятельно как отдельная подсистема.
В первом случае для активизации процесса автоматизированного проектирования используются основные и служебные директивы так называемого языка управления заданием (ЯУЗ), который является порождением языка описания схем систем L . С помощью основных директив активизируют основные блоки системы: декомпозиции (Ш), композиции (і), модификации (П), имитационного моделирования (1У), библиотекарь (УТ). Дополнительные (служебные) директивы используются для активизации процесса обмена информа мацией при принятии решений в ходе проектирования, а также для включения в работу того или иного блока СДКМС по желанию пользователя.
Во втором режиме активизация блоков системы осуществляется интерпретатором языка описания схем систем L на основании программы, написанной на языке L .
В автономном режиме каждый основной блок функционирует отдельно. Их активизация осуществляется по желанию пользователя.
Lw -язык - это функциональный язык. Каждый оператор L -языка - операция из операционного множества \л/ алгебры А-схем. Синтаксис и семантика операторов L -языка разработаны [93], но интерпретатор и транслятор с языка L2 пока еще не реализованы.
Каждому оператору-функции L -языка соответствует подпро - 115 грамма-функция или подпрограмма-процедура, которые составляют библиотеку вычислительных функций (Ш ). Подпрограммы записываются в библиотеку в виде загрузочных модулей.
Кроме операций над А-схемами конструктивные средства L -языка содержат операторы спецификации программы, оператор описания А-схем, оператор безусловного перехода.
Операция декомпозиции DEC, которая является составной операцией, множество базовых операций W и операции, используемые для анализа А-схем, образуют языковое подмножество LpEC языка описания А-схем L2, необходимое для реализации процесса декомпозиции.
При реализации оператора ЇЕС используют BAZA и BASA. В ASA содержит различные конструкции из элементарных агрегатов, содержащихся в BAZA.
BAZA и BASA имеют трехуровневую структуру [92].
Существуют следующие уровни: уровень агрегатов и А-систем (BAZA\BASA ) ; уровень функций агрегатов (BAZA ) и функций А-систем (BASA"); уровень программ агрегатов (BAZAT и программ А-систем (BASA ). Кроме того, существует общий уровень, к которому относятся каталоги BAZA и BASA, содержащие справочную информацию и систему ссылок, для реализации связей между уровнями. Связи между наборами данных для ВА2А и BASA показаны на рис.3.2, 3.3. Но в то же время каждый уровень может иметь отдельный вход.
Учитывая, что BAZA и BASA являются абстракцией реальных систем, существуют банки или библиотеки для конкретного класса систем, например, библиотеки алгоритмов и или программ J для таких классов систем, как алгоритмы и программы.
Экспериментальная проверка алгоритмов декомпозиции на примере ПО
Для экспериментальной проверки алгоритмов декомпозиции была использована подсистема "Оперативный учет" одного из московских предприятий. Подсистема состоит из пяти комплесов задач, которые функционируют в следующих режимах: ежедневном, месячном, квартальном, годовом. Связь между комплексами задач иллюстрируется рис.3.23.
Были рассмотрены следующие задачи подсистемы: "Формирование сводки выполнения плана по выпуску продукции в отпускных ценах по фабрике" (WPLAN) , "Оперативный учет по сдаче продукции цехом за месяц" (OUCbH) , "Отчет о выполнении месячного тематического плана цехом за месяц" (0WPL) , "Оперативный учет изготовленной продукции цехом за месяц" . В скобках указано имя А-системы, которая описывает задачу.
Входной информацией для блока "Декомпозитор" являются таблицы: "Описание агрегатов А-системы" - LIST (рис.3.6) и "Описание связей А-системы" - TABR (рис.3.7).
На основе имеющихся алгоритмов и блок-схем, используя агре-гативный метод, каждая из задач была описана хаж А-система, т.е. представлена с помощью двух вышеназванных таблиц. Описания каждой из задач в виде А-системы приведены в табл. 3.4 - 3.II.
Имена А-систем для рассматриваемых задач были заданы пользователем произвольно, но так, чтобы не было повторяющихся имен, а имена агрегатов должны быть уникальными только для одной задачи (А-системы).
Каждому блоку блок-схемы (пункту алгоритма) соответствует агрегат, который в свою очередь также может быть А-системой.
Функция агрегата и А-системы проставляется в соответствии с классификатором функций для рассматриваемого класса систем, а именно: ПО АСУ»
Информационным входам/выходам агрегата ставится в соответствие имя переменной. Для единообразия описания агрегата управляющие входы/выходы тоже имеют имя, которое получают конкатенацией символа " F и номера входа/выхода. Число входов и выходов агрегата не ограничивается.
Таблицы описания А-системы с помощью модуля WW0D вводят с ПК или дисплея. В результате, как указывалось в 3.4, будут получены три индексно-полседовательных файла: TBR, SPRV, LIST.
Учитывая, что при работе блока "Декомпозитор" обычно рассматривается больше одной А-системы, была предложена следующая идентификация А-систем: имя А-системы не должно превышать б символов (последний символ - пробел,), тогда имена файлов TBR,
SPRV и LIST образуются присоединением к имени А-системы слева соответственно символов I , о , Ь . Например, имя А-системы - WPLAN , а имена файлов - TWPLAN, SWPLAN,
LWPLAN. Таким образом, проектировщику необходимо следить только за тем, чтобы А-системы, которые он рассматривает, имели различные имена.
После ввода описания А-систем они проверяются на корректность с помощью модуля C0RR. Для рассматриваемых задач в результате выполнения модуля C0RR были выявлены такие ошибки, как: неверное имя переменной, наличие нескольких начальных и конечных агрегатов, изолированные агрегаты, отсутствие указанного в описании агрегата выхода или входа и др. Если ошибки в описании А-системы отсутствуют, то на печать выводятся только имена начального и конечного агрегатов. А-система подвергается декомпозиции, если влей отсутствуют ошибки. Результаты выполнения модуля C0RR приведены в приложении П.
Декомпозиция в целях выявления типовости агрегатов выполняется с помощью модуля WTBIBL с использованием базы агрегатов ВАИА и банка агрегативных структур BASA . Использование В ASA позволяет выполнять структуризацию исходной А-си-отемы автоматически. Для типовых агрегатов и структур в библиотеках программ имеются отлаженные программы. Для агрегатов, которые не являются типовыми, необходимо создавать программы. Результаты работы модуля WTBIBL выводятся на печать в виде таблицы (рис. 3.22) и приведены в приложении П.
При выполнении модуля DECL строится список линейных компонент А-системы. Необходимо отметить, что компоненты, содержащие только один агрегат, в список не входят. Результаты выполнения модуля DECL для каждой А-системы представлены в приложении П.
Используя модуль RED , линейные компоненты были заменены на их представляющие агрегаты, которым присваивается имя, полученное конкатенацией символов LK и порядкового номера компоненты. В результате построена новая А-система, представляющая собой редукцию исходной А-системы и описываемая индеке-но-последовательными файлами RSPRV, RLIST, RTBR . Для того, чтобы отличать эти файлы от исходных, к имени файла слева присоединяется символ R . Вновь построенные описания А-сис-тем распечатаны для всех задач в виде таблиц LIST и TABR с помощью модуля PECHSH и приведены в приложении П.
А-система, полученная в результате редукции исходной А-системы, в свою очередь тоже может быть подвергнута декомпози - 171 ции.
Модуль RED позволяет укрупнять рассматриваемую А-систе-му, что часто бывает необходимо выполнять при проектировании сложных систем.
Пользователь может сам задавать подсистему (подсхему), которая подлежит замене представляющим агрегатом.
При выполнении модуля PVE осуществляется выделение элементов рассматриваемой А-сиетемы. Для этих элементов составляется их описание и указываются связи с другими элементами системы.
Использование модуля PVE очень удобно при необходимости получения информации о построенных в модуле RED представляющих агрегатах.
