МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ

Блочно-симметричные модели и методы проектирования систем обработки данных
МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ Модели и методы решения задач дискретного программирования при проектировании систем обработки данных На основе выбранного значения оценок вычисляются допустимые решения; Постановка задачи исследования Общая постановка блочно-симметричных задач дискретного программирования Декомпозиция прикладных задач и исходных документов систем обработки данных на этапе технического проектирования Проектирование модульных блок-схем систем обработки данных Частные задачи проектирования модульных блок-схем систем обработки данных Эффективный алгоритм решения блочно-симметричных задач проектирования модульных блок-схем обработки данных Постановка и решение многокритериальных задач разработки модульных блок-схем обработки данных Кульба В.В., Мамиконов А.Г. Синтез оптимальных модульных СОД.М.:Наука, 1986
158931
знак
0
таблиц
1
изображение

1.  МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ МОДУЛЬНЫХ СИСТЕМ ОБРАБОТКИ ДАННЫХ

В данном разделе проведен анализ формализованных моделей и методов проектирования модульных систем обработки данных (МСОД). Рассмотрены задачи предпроектного анализа предметной области, формирования исходных данных для проектирования систем обработки данных. Как правило, поставленные задачи сведены к задачам дискретного программирования, которые сложны и не часто позволяют решать задачи большой размерности. В разделе приведен краткий обзор методов решение задач дискретного программирования (ДП) [146].

На основе проведенного анализа моделей и методов проектирования СОД сформулированы задачи исследования.

1.1 Обзор моделей анализа и синтеза модульных систем обработки данных

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

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

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

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

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

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

В рамках этого направления рассмотрим известные подходы анализа и проектирование систем обработки данных.

Для разработки формализованных методов необходимо провести анализ предметной области, для которой разрабатываются системы обработки данных.

В результате анализа систем обработки данных выделяются множество функциональных задач и процедур обработки данных, множество информационных элементов, необходимых и достаточных для решения множества задач системы, а так же взаимосвязи между информационными элементами и процедурами обработки данных в процессе решения задач по обработке данных. В ряде случаев в процессе анализа оцениваются и выделяются такие количественные характеристики, как размеры информационных элементов и процедур, частоты функционирования программных модулей и функциональных задач, средние времена обращения к массивам базы данных и другие [14, 16, 18, 21, 24].

Уточним некоторые понятия.

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

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

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

Рассмотрим методы анализа систем обработки данных реального времени (СОД РВ), которые могут быть использованы при анализе систем других классов.

Процедуры обслуживания заявок в системах обработки данных реального времени (СОД РВ) неоднозначно определяются требуемым множеством выходных информационных элементов и детерминированной технологией их получения, а зависят от времени поступлении заявки на обработку, состава и взаимосвязей необходимых для ее обслуживания задач и от текущего состояния информационной базы, определяющего альтернативные возможности обработки данных. Для исследование этих возможностей необходим совместный анализ множество требований, предъявляемых поступающими на обработку заявками, используемых для их обслуживания задач обработки данных, алгоритмов их решения и используемых массивов. Для анализа структур информационных потоков и технологии обработки данных в СОД РВ используется совокупность взаимосвязанных матричных и графовых моделей, обеспечивающих формальный анализ технологий обработки данных как отдельной задачи СОД РВ, так и множества задач в целом [25-30, 33,38]

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

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

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

Пусть задано множество задач СОД РВ . Технологии решения каждой задачи соответствует направленный граф , где множество вершин графа, отражающих информационные элементы задачи ; - множество отношений между информационными элементами . Каждому графу  соответствует квадратная бинарная матрица смежности  размера . Элемент  матрицы  равен 1, если элементы и  графа  связаны отношениями , и равен 0 в противном случае.

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

.

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

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

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


Матрица  определяется на основе матрицы . При этом они связаны булевым уравнением

 

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

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

Взаимосвязь между процедурами обработки данных при обслуживании каждой заявки СОД РВ, наборами входных и промежуточных данных удобно представлять с помощью таблицы инциденции обработки множеств запросов , которая представляет собой матрицу вида


В матрице  каждая строка отображает процедуру обработки, а каждый столбец – использование всеми процедурами при решении  задачи рассматриваемого информационного элемента. В строке содержится информация о множестве входных и выходных данных, связанных с анализируемой процедурой. Анализ столбцов позволяет выявить входные и выходные информационные элементы рассматриваемой задачи . Элементы являются входными при решении  задачи, если  столбец матрицы  содержит единственную, отличную от нуля запись . Если -й столбец содержит запись , то соответствующий ему элемент  является выходным. Технологической матрицей смежности  при решении  задачи назовем квадратную бинарную матрицу, проиндексированную по обеим осям множествами . Матрица  имеет четыре подматрицы:  с размерами .

Нулевые элементы подматрицы  соответствует элементам, равным -1 в матрице , а не нулевые элементы подматрицы  соответствует элементам, равным +1 в транспонированной матрице . Таким образом, элемент  матрицы  равен 1, если элемент  является входным для процедуры , и элемент  равен 1, если элемент  является входным при решении  задачи. В противном случае элементы в позициях  и  равны 0. Единичный элемент в позиции ,  подматрицы  соответствует наличию единичных элементов в позиции  подматрицы  и в позиции  подматрицы , , что равносильно существованию информационного элемента , который является входным для процедуры , и выходным для процедуры  при решении  задачи. Для удобство формального описания будет считать, что главная диагональ подматрицы  заполнена единичными записями.

Используя матрицу , можно определить матрицу , которая содержит подматрицы , проиндексированы соответственно: .

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

.

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

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

.

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

В качестве моделей описания и анализа задач обработки данных при создании типовых модульных СОД также используется аналогичная совокупность графовых и матричных моделей. Методика анализа и структуризация исходной для синтеза системы типовых модулей СОД информации базируется на последовательном преобразовании матричных и графовых моделей алгоритмов решения задач обработки данных, содержащих всю необходимую информацию о взаимосвязях и отношениях между различными элементами отдельных задач. При формировании полного структурированного графа технологии решения задачи учитывается наличие в алгоритмах решения задач обработки данных циклических участков и альтернативных вариантов обработки, процедур обновления информационных элементов и процедур принятия решений. Полный структурированный граф и соответствующие ему матрицы смежности и достижимости позволяют описывать алгоритмы решения задач обработки данных в целом и отдельные их части с заданной степенью детализации [31,32,34,39,40]

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

На стадии предпроектного анализа ДС необходимо выполнить комплекс работ, основной из которых также является анализ решаемых пользователями задач, технологии их решения, определения требований пользователей к эффективности и качеству решения задач [40]. На этой стадии определяется необходимый набор процедур реализации комплекса диалоговых задач и требуемой для их решения информации.

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

Определение процедур обработки данных, анализ и структуризацию каждой диалоговой задачи целесообразно осуществлять с использованием дополнительной совокупности матричных и графовых моделей, обеспечивающих подготовку локальных сценариев (ЛС) диалога и других исходных данных, необходимых для технического проектирования оптимальных ДС [41].

Локальные сценарии диалога строятся на основе описанных пользователями (средствами языка описания задач – ЯОЗ) схем их решения, которые дополняют формами представления результатов проектирования систем. Схема решения каждой задачи представляется в виде совокупности взаимосвязанных таблиц решений (ТР), описывающих последовательность и содержание шагов диалога пользователя с ДС при решении задачи, используемую при этом информацию, а также требования пользователя к характеристикам процесса обработки запросов, выдаваемых на каждом шаге диалога. Совокупность таблиц решений однозначным образом отображается в граф локального сценария диалога (ГЛС). Каждая вершина ГЛС соответствует одной ТР, а направленные дуги – взаимосвязям между таблицами. Каждому ГЛС ставятся в соответствие матрица смежности и матрица достижимости, отражающие структуру и взаимосвязь узлов графа.

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

С учетом результатов анализа требований пользователей и локальных сценариев диалога формируетсся сценарий ДС в целом путем операции «наложения» упорядоченных узлов на каждом уровне. Для формализации, упорядочения и анализа сценария диалога всей системы также используется совокупность взаимосвязанных матричных и графовых моделей и методы оценки ГЕРТ-сетей.

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

Качественные изменения в структуре современных модульных СОД связаны с широким внедрением сетей ЭВМ, систем управления локальными и распределенными базами данных, а также новейших систем передачи данных.

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

Анализ в процессе проектирования распределенных баз данных (РБД) в модульных системах включает четыре взаимосвязанных этапа предпроектный анализ предметных областей пользователей, анализ предметных областей пользователей и построение внешних моделей, построение обобщенной внешней модели и построение канонической структуры РБД. Результатом анализа предметных областей пользователей является построение канонической структуры РБД, которая отражает наиболее существенные характеристики и устойчивые свойства данных и отношений между ними и является инвариантной по отношению к аппаратным и программным средствам ее реализации [35, 36, 37].

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

Целесообразность применения методов типизации при проектировании РБД определяется уровнем информационной и процедурной общности внешних моделей предметной области пользователей.

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

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

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

В процессе анализа модульных СОД широко используется аппарат сетей Петри [42]. Задачи анализа систем обработки данных, решаемых при помощи временных сетей Петри с разноцветными маркерами, включают задачи определения возможности и корректности реализацим любой функциональной задачи пользователя или заданного множества таких задач, возможности многократного использования процедур обработки данных выявления тупиковых ситуаций при совместной обработке информационных элементов. С использованием сетей Петри проводитсятакже анализ механизмов защиты в системах обработки данных [42, 43].

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

Рассмотрим методы синтеза модульных систем обработки данных разного назначения.

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

Для оптимизации процесса проектирования системы мспользуетя критерий минимума сложности межмодульного интерфейса. Оптимизация эксплуатационных характеристик может быть осуществлена в зависимости от конкретных обстоятельств по одному из следующих критеров: минумум времени обмена между оперативной и внешней памятью, снижение технологической сложности алгоритмов обработки данных, что является обобщением показателя «транспортного фактора» при реализации алгоритмов решения функциональных задач, предложенного Лангефорсом. Кроме того, для информационных систем существенным является максимум инфармационной производительности и обеспечение достоверности обработки данных [14-21, 30, 31, 44-60].

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

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

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

Рассмотрим методы синтеза оптимальных модульных систем обработки данных реального времени [25-30, 38, 54-66].

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

Учёт особенностей проектирования СОД РВ достигается введением в разработанные модели параметров, определяющих законы поступления заявок на обработку, дисциплины обслуживания и приоритетность заявок, взаимосвязи между заявками по решеаемым задачам.

Можно выделить следующие основные задачи модулного построения программного и информационного обеспечения СОД РВ: синтез оптимальных модульных СОД РВ с бесприоритетным обслуживанием заявок в режиме разделения времени на однопроцессорных ЭВМ, синтез систем РВ с приоритетным обслуживанием заявок в ОС реального времени на однопроцессорных ЭВМ, синтез оптимальных модульных СОД РВ на многопроцессорных ЭВМ.

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

При синтезе СОД РВ с приоритетным обслуживанием заявок необходимо учитывать разнообразие входных заявок различных типов, характеризующихся различной интенсивностью поступления, приоритетностью обслуживания [31, 67]. Требования пользователей на время обслуживания заявок значительно жестче по сравнению с задачами бесприорететного обслуживания, что требует размещения в оперативной памяти ряда программных процедур и данных, необходимых для обслуживания отдельных заявок. Взаимосвязи между заявками по составу решаемых задач в таких системах, как правило, весьма существенны. Повышение эффективности решения данных задач осуществляется в основном за счет сокращения числа и времени обмена между уровнями памяти обслуживании заявок [55, 67, 68].

Решение задач синтеза оптимальных СОД РВ с мультипроцессорным обслуживанием предполагает сокращение не только времени обмена между уровнями памяти , но и среднего процессорного времени решения задач за счет параллельной реализации процедур, модулей или заявок в целом [58, 59, 61, 65, 66].

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

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

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

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

Рассмотрим задачу синтеза оптимальной структуры программного и информационного обеспечения СОД РВ по критерию максимальной производительности системы в режиме разделения времени в процессе обслуживания входных потоков на решение задач. Задача формулируется следующим образом:

,

при ограничениях на: время обслуживание -й заявки для заданного алгоритма организации очереди


;

устойчивость режима функционирования системы

;

общее число дублируемых процедур

;

число процедур в составе модуля

;

число информационных элементов в составе массива базы данных

,

дублирование информационных элементов в массивах

;

однородность включения процедур в программные модули


;

общее число информационных элементов, используемых модулями задач

.

Переменные и обозначения в данной постановке определены следующим образом:

где  - булевая матрица взаимосвязей задач и процедур обработки данных,  и  - матрицы взаимосвязей информационных элементов с процедурами обработки данных соответственно при считывании и записи:

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

Среднее время решения -й задачи СОД РВ определяется следующим образом:

,

Где  - среднее процессорное время решения задачи; - среднее время поиска и перезаписи -го модуля из внешней памяти в оперативную память;  - среднее время считывания -го массива из внешней памяти;  - среднее время записи результатов обработки данных в -й массив. Среднее время решения всех задач обработки данных в СОД РВ определяется в соответствии с соотношением

.

Среднее время обслуживания заявки для алгоритма кругового циклического обслуживания с послеприбытием имеет вид


,

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

Поставлены и решены следующие задачи разработки оптимальных модульных СОД РВ: определение системы модулей программного и информационного обеспечения, формализуемой в виде блок-схемы обработки данных функциональных задач, использующих дисциплины диспетчеризации заявок с относительными, абсолютными и смешанными приоритетами; определение оптимальной и допустимой последовательности приоритетов уровней и выбор методов организации вычислительного процесса, определение структур базы данных и ее характеристик. В качестве основных критериев оптимальности рассматриваются минимум межмодульного интерфейса, минимум число обращений системы программных модулей к внешней памяти, минимум суммарного времени ожидания заявок на решения задач, минимум суммарного штрафа за ожидание заявок на решение задачи системы.

Задачи синтеза решены при ряде технологических и эксплуатационных ограничений, основными из которых являются ограничения на устойчивость режима функционирования системы, на среднее время ожидания заявок на решения задач, сложность интерфейса. Поставленные задачи синтеза модульных СОД РВ сведены к моделям целочисленного нелинейного программирования, для решения которых предложены алгоритмы, основанные на схеме «ветвей и границ».

Диалоговые системы. Современный уровень развития вычислительной техники и особенно персональных ЭВМ обусловил резкое расширение числа и возможностей диалоговых систем в модульных СОД, а также круга их пользователей.

Разработка эффективных диалоговых систем представляет собой комплексную проблему, включающую в себе анализ и типизацию информационных требований пользователей, синтез типовой модели диалога для заданного множества пользователей, информационные запросы которых принадлежат одной предметной области, синтез информационного и модульного программного обеспечения диалоговых систем (ДС) [130].

При синтезе оптимальных модульных ДС используется следующие системные и технические характеристики: затраты на разработку и внедрение системы в целом и ее подсистемы, время разработки и внедрения, эксплуатационные расходы, потери в системе от несвоевременного представления информации пользователю, конфигурация, качество и загрузка технических средств, используемых при решении задач пользователей, достоверность обрабатываемой информации, информационная производительность системы, надежность программного и технического обеспечения ДС, релевантность выполняемых системой запросов, время реакции ДС при выполнении запросов пользователей по заданным сценариям, время и удобство формирования пользователем запросов, степень приближения к работе в реальном масштабе времени (так режиме формирования запроса так и при реализации интерфейса ДС-БД) [131], объем оперативной памяти для размещения программных модулей и информационных массивов системы, быстродействие, время обращения к периферийному оборудованию, стоимость комплекса технических средств (КТС) и его комплектация с учетом эргономических требований, степень распределенности КТС в случае сетевой его архитектуры [56-57].

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

Наиболее общей задачей синтеза ДС является определение по заданным критериям эффективности сценарии (С), программного обеспечения (Р), информационного обеспечения (I) и комплекса технических средств (Г) диалоговой системы на основе анализа характеристик пользователей (П), решаемых ими задач (Ф) и требований пользователей к основным характеристикам решаемых задач.

К частным задачам синтеза ДС относятся определение оптимального сценария С диалоговой системы на основе локальных сценариев, выбор КТС из множества возможных, синтез Р и I на основе информации о сценарии С и характеристиках выбранного КТС.

Критерии эффективности при синтезе ДС целесообразно разбить на несколько уровней: ДС в целом, процесс диалога, обеспечивающие подсистемы ДС (программное, информационное и техническое обеспечение ДС),

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

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

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

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

При выборе технического обеспечения ДС целесообразно использовать в основном экономические показатели.

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

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

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

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

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

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

Задачи синтеза струтуры праграммного обеспечения ДС сведены к задачам нелинейного целочисленного программирование, для решения каторых используются метод «ветвей и границ» и другие методи [72].

Типизация разработки. Под тепизацией при разработке СОД понимается процесс анализа требований и харектеристик заданного множества обьектов автоматизации и выбора методов сведения многообразия индивидуальных проектных решений к огрониченному множеству решений, достаточно эффективно выполняющих требования объектов автоматизаций [31, 73, 74].

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

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

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

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

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

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

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

Задачи синтеза типовых модульных СОД сведены к задачам нелинейного и линейного целочисленного программирования и решаются с использованием известных стандартных пакетов и специальных методов, основанных на схеме «ветвей и границ».

Синтез структур баз данных. Создание модульных СОД нового поколения тесно связано с широким внедрением сетей ЭВМ, локальных и распределенных баз данных (РБД) и систем передачи информации [75-81].

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

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

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

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

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

В процесс проектирования РБД выделяются следующие взаимосвязанные этапы: синтез оптимальных логической структуры РБД, проектирование структуры сетевого каталога и проектирование логических структур локальных баз данных (БД). Синтезируемые оптимальная по заданному критерию эффективности логическая структура РБД, сетевой каталог и логические структуры локальных БД должны обеспечивать сохранение семантических свойств информационных элементов и связей между ними, зафиксированных в канонической структуре РБД с учетом ограничений, накладываемых параметрами локальных СУБД и аппаратных средств передачи данных, топологией ВС и требованиями различных режимов функционирования распределенных банков данных (РБнД).

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

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

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

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

Результатом решения задач данного этапа логического проектирования является оптимальная структура сетевого каталога обеспечивающая оптимальное количество сетевых обращений к нему в процессе реализаций запросов пользователей и корректировок каталога с учетом географического размещения пользователей в ВС и характеристик запросов а также оптимальное количество обменов между оперативной памятью и ВЗУ в процессе локального функционирования сетевого каталога в РБиД.

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

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

Поставлены и решены задачи синтеза оптимальных по заданным критериям эффективности логических и физических структур локальных баз данных. При проектировании оптимальных логических структур локальных баз данных возможны два подхода, каждый из которых детально исследован [69, 76, 79, 80].

Первый подход основывается на синтезе логических структур локальных баз данных, эффективность которых определяется единым критерием оптимальности функционирования РБД. Исходной информацией, используемой в этом случае при проектировании логических структур локальных БД являются характеристики логической структуры РБД и сетевого каталога. Проектирование осуществляется путем нормализации графа логической структуры отдельного узла ВС, формируемого в результате синтеза оптимальной логической структуры РБД и определения в графе несвязных и слабо связных подграфов, являющихся основой логических структур локальных БД, поддерживаемых конкретными СУБД.

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

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

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

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

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

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

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

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

Разработанные методы, модели, алгоритмы и комплексы программ нашли широкое практическое использование при проектировании модульных СОД различного класса и назначения.

С использованием полученных результатов сформулированы принципы построения и рассмотрены основные элементы, структура и алгоритмическое обеспечение автоматизированной системы проектирования оптимальных модульных СОД, а также имитационные модели для анализа технологии обработки информации на системном уровне. На этой основе разработаны системы автоматизированного проектирования СОД семейства “Модуль”.

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

 


Информация о работе «Блочно-симметричные модели и методы проектирования систем обработки данных»
Раздел: Информатика, программирование
Количество знаков с пробелами: 158931
Количество таблиц: 0
Количество изображений: 1

Похожие работы

Скачать
448518
14
55

... также невысока и обычно составляет около 100 кбайт/с. НКМЛ могут использовать локальные интерфейсы SCSI. Лекция 3. Программное обеспечение ПЭВМ 3.1 Общая характеристика и состав программного обеспечения 3.1.1 Состав и назначение программного обеспечения Процесс взаимодействия человека с компьютером организуется устройством управления в соответствии с той программой, которую пользователь ...

Скачать
308601
37
3

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

Скачать
113309
0
0

... . Особо стоит отметить наличие в СЗИ защиты загрузки операционной системы с гибких магнитных дисков и CD-ROM, которая обеспечивает защиту самих средств защиты от "взлома" с использованием специальных технологий. В различных СЗИ существуют программные и аппаратно-программные реализации этой защиты, однако практика показывает, что программная реализация не обеспечивает необходимой стойкости. ...

Скачать
129027
5
16

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

0 комментариев


Наверх