Содержание к диссертации
Введение
1. Математическое моделирование параллельных вычислительных процессов в системах мониторинга 11
1.1 Анализ принципов организации вычислительных процессов в системах мониторинга 11
1.2 Сравнение способов построения и методов анализа моделей параллельных вычислительных процессов 40
1.3 Анализ инструментальных средств моделирования информационно-вычислительных систем и сетей 57
1.4 Задачи развития методов и средств анализа параллельных вычислительных процессов в системах мониторинга 66
2. Анализ параллельных вычислительных процессов с задержками в объединении синхронизируемых процедур двухуровневых схем принятия решений в системах мониторинга и управления 72
2.1 Формирование описания параллельных вычислительных процессов с задержками в объединении синхронизируемых процедур двухуровневых схем принятия решений 72
2.2 Формализация процесса отыскания групп совместных вершин для анализа параллельных процессов с задержками в объединении решающих правил 78
2.3 Инструментальные средства для анализа параллельных процессов по методу отыскания групп совместных вершин 87
2.4 Исследование характеристик параллельных вычислительных процессов по методу отыскания групп совместных веешин 99
выводы 104
3. Моделирование многоуровневых систем принятия решений с использованием метода свертки 105
3.1 Представление параллельных процессов с задержками в объединении синхронизируемых процедур многоуровневых схем принятия решений 105
3.2 Обоснование выбора метода для анализа мннгоороовнеых ссем принятия решений 101
3.3 Расширение метода свертки для анализа параллельных вычислительных процессов с задержками в объединении синхронизируемых процедур двухуровневых схем принятия
решений 109
3.3.1 Определение характеристик обнаружения событйй при отсутствии временных задерэюек в комплексировании решений 111
3.3.2 Характеристики обнаружения событйй при одинаковых ненулевых временных задержках комплексирования решающхх правич 115
3.3.3 Характеристики обнаружения событйй при произвольных временных задержках комплексирования решающхх правил 119
3.3.4 Характеристики обнаружения событйй при комплексировании последовательных фрагментов по функции «миз n» с бесконечными задержками.]!\
3.4 Формализация метода свертки для анализа параллельных вычислительных процессов с задержками в объединении синхронизируемых процедур многоуровневых схем принятия решений 125
3.5 Инструментальные средства для анализа многоуровневых логических моделей параллельных процессов по методу свертки 129
Выводы 131
4. Анализ характеристик качества функционирования систем мониторинга 132
4.1 Описание предметной области 132
4.2 Разработка моделей для исследования системы мониторинга 134
4.3 Определение и исследование характеристик вычислительных процессов 148
Выводы 156
5. Исследование системы мониторинга и управления поведением судна 158
5.1 Архитектура систем управления поведением судна 115
5.2 Построение математической модели процесса принятия решений в системе мониторинга и управления поведением судна 162
5.3 Исследование временных характеристик системы мониторинга и управления поведением судна 171
Выводы 177
Приложение. акты о внедрении основных результатов диссертационной работы 180
Литература
- Сравнение способов построения и методов анализа моделей параллельных вычислительных процессов
- Формализация процесса отыскания групп совместных вершин для анализа параллельных процессов с задержками в объединении решающих правил
- Обоснование выбора метода для анализа мннгоороовнеых ссем принятия решений
- Построение математической модели процесса принятия решений в системе мониторинга и управления поведением судна
Сравнение способов построения и методов анализа моделей параллельных вычислительных процессов
Развитие концепций администрирования информационно-вычислительных систем происходило не только вдоль архитектурной оси, но и в пространстве объектов, вовлекаемых в область действия управляющих средств. С точки зрения решаемых задач, администрирование централизованных мейнфреймовых систем можно назвать системным, что, в частности, означало существование единого образа вычислительной среды. В самом начале появления распределенных архитектур задачи управления заключались в контроле функционирования отдельных компонентов (сетевого оборудования, рабочих станций и серверов, периферийных устройств и т.п.), который, как правило, сводился к обычному сбору статистических данных об их работе без ведения каких-либо управляющих действий. Такой "переходный" тип управления не является в полном смысле слова сетевым администрированием. Последнее возникло лишь тогда, когда у оператора появилась возможность работать с представлением сети как единого целого. При этом был сделан качественный скачок от управления отдельными устройствами к анализу трафика в сегментах сети, управлению ее логической конфигурацией и настраиваемыми параметрами.
Следующий этап в развитии средств администрирования заключался в реализации функций управления информационными системами в целом, что подразумевает добавление к списку контролируемых объектов сетевых операционных систем, распределенных СУБД, хранилищ данных, приложений и даже непосредственно пользователей.
В соответствии с приведенным поэтапным развитием средств администрирования менялось и соотношение сетевой и системной компонент. Проблемы, возникшие в распределенных системах на заре их жизни, привлекли повышенное внимание к сетевому управлению. С экономических позиций это выразилось в резком увеличении спроса на платформы сетевого управления (Cabletron Spectrum, HP OpenView, IBM NetView, SunNet Manager и др.), служащих базой для запуска и работы управляющих приложений. Системное администрирование отошло на второй план и некоторое время соответствующее программное обеспечение выступало как набор автономных служб, внешних по отношению к приложениям и платформам сетевого управления. Через несколько лет ситуация изменилась вновь, после того, как стремительно растущее количество распределенных приложений, функционирующих в сети, перешагнуло некоторое пороговое значение. Возрастание роли системного администрирования в таком случае оказалось естественным и неизбежным, так же как и процесс интеграции системной и сетевой компонент управления, который заставил ведущих производителей срочно модернизировать свои продукты.
Конечная цель любых процедур управления - достижение параметров функционирования информационных систем, отвечающих потребностям пользователей. В связи с этим можно предположить, что в будущем и системное и сетевое администрирование объединятся для организации управления приложениями и качеством сервиса. Но пока полной интеграции не произошло имеет смысл рассматривать разные сферы администрирования отдельно, указывая их характерные особенности и обозначая направления и тенденции взаимного проникновения и интеграции.
Задачи, решаемые системами сетевого управления, можно разделить на две группы [3]: контроль за работой сетевого оборудования и управление функционированием сети как единого целого. Под первой группой задач, именуемой реактивным администрированием (reactive management), понимается мониторинг отдельных сетевых устройств - коммутаторов, маршрутизаторов и т.п., - настройка и изменение их конфигурации, выявление и устранение возникающих сбоев. Во втором случае реализуется мониторинг сетевого трафика, выявление тенденций его изменения, анализ событий, направленный на организацию системы приоритезации, превентивного решения проблем перегрузки канала (упреждающее, профилактическое, "проактивное" администрирование, proactive management). Здесь же формируется единое представление сети, стратегическое планирование ее конфигурации, учет сетевых ресурсов, управление IP-адресами и трафиком пользователей и т.п.
В результате необходимости контроля сети как единого целого возникло несколько архитектур платформ и приложений администрирования, наиболее распространенной из которых стала двухуровневая архитектура "менеджер -агенты". Программа-менеджер работает на управляющей консоли, постоянно взаимодействует с модулями агентов, запускаемыми на отдельных устройствах в сети. Агенты предназначены для локального сбора данных о значимых параметрах контролируемого ресурса, передачи и приеме информации менеджеру, внесение изменений в конфигурацию объекта по требованию менеджера.
Такая двухуровневая схема удобна, однако, ее применение в реальных условиях, особенно в сложных сегментированных сетях приводит к чрезмерному возрастанию служебного трафика. Как одно из решений этой проблемы была предложена трехуровневая схема, разработанная в рамках концепции доверенного (делегированного) управления. При доверенном управлении менеджеры промежуточного уровня (субменеджеры), управляют набором подчиненных им устройств и в то же время выполняют функции агентов по отношению к основному менеджеру, запущенному на управляющей станции. При этом субменеджер может управлять доверенными ему объектами с помощью своих собственных, нестандартных протоколов (например, протокол AgentX, используемый в так называемых расширяемых агентах [9,10]).
Впервые трехуровневая архитектура управления сетью была реализована в 1995 г. компанией SUN Microsystems в продукте Solstice. Сейчас ее применяют и другие производители, например, IBM (Tivoli Enterprise).
Необходимость контроля работы оборудования различных производителей в гетерогенной среде привела к унификации управляющих процедур, которая нащла отражение в создании протокола SNMP, ставшего базовым протоколом сетевого администрирования и транспортного средства в стандарте дистанционного мониторинга RMON.
Для унификации управления распределенными объектами было создано два протокола: SNMP (Simple Network Management Protocol - простой протокол управления сетью [11,12,13,14]), разработанный в 1988 г. и принятый в 1990 г. как стандарт Интернет, и широко применяющийся сейчас в IP-сетях, и СМОТ (Common Management Information Services and Protocol over TCP/IP [15]), являющийся стандартом ISO и применяющийся довольно редко. Большинство современных программ мониторинга и управления сетью используют в качестве базового средства протокол SNMP.
SNMP работает поверх стека UDP-IP-физический канал, позволяя собирать информацию о состоянии объектов в сети. Сам протокол определяет формат данных, а их обработка и интерпретация возлагаются на вышележащее программное обеспечение. Функционирование SNMP происходит согласно идеологии "клиент-сервер". На рис. 1-2 представлена схема взаимодействия управляющей станции (SNMP менеджера) и объекта управления [16].
При работе SNMP использует управляющую базу данных (Management Information Base - МІВ). Информация в МІB представляется в соответствии с нотацией ASN.1 (Abstract Syntax Notation). Имена переменных соответствуют стандартам ISO и CCITT и имеют иерархический характер. В [17] и [18] описаны структуры данных для МІB-1 и МІB-2 соответственно, не взаимоисключающих, но дополняющих друг друга базах.
Формализация процесса отыскания групп совместных вершин для анализа параллельных процессов с задержками в объединении решающих правил
В ряде работ рассматривается точное численное вычисление распределения T(G) с использованием семейств распределений, устойчивых (stable) относительно операций "max" и "+", т.е. их функции распределения устойчивы к умножению и свертке. Такие семейства включают кусочные (piecewise) полиномиальные распределения [49], экспоненциальные полиномиальные распределения (с рациональным преобразованием Лапласа) [50,51] и другие [52].
Вышеперечисленные семейства также устойчивы относительно операций минимизации, что позволяет использовать их для графов с функцией объединения "ИЛИ".
Приведенный алгоритм сведения гарантирует, что число произведений распределений и сверток, необходимых для преобразования графа, линейно зависит от размера графа. Однако, число коэффициентов в распределении обычно растет экспоненциально с увеличением числа выполняемых операций [53]. Это ведет к появлению проблем хранения данных и точности вычислений, что серьезно ограничивает практическое применение метода.
При анализе вычислительных процессов широко применяются марковские модели [54].
Основной принцип марковского анализа при исследовании вычислительных процессов заключается в получении характеристик исследуемого графа по эквивалентному ему марковскому графу [55].
При выполнении процессов каждая подзадача может находиться в одном из трех возможных состояний: 0 - начальном, т.е. подзадача еще не начала выполняться; / - промежуточном, - подзадача выполняется; v - конечном, , подзадача завершена.
Состояние PERT-сети в этом случае описывается кортежем размерности (N+M). Число возможных состояний сети, а следовательно, и размер распределения T(G) априори для параллельного графа составит Uk(vk +1) - произведение числа состояний всех входящих в него подграфов.
Развитием указанного подхода к анализу процессов является метод отыскания групп совместных вершин путем построения графа возможных реализаций [41].
С ростом N и М размерность задачи быстро растет, и данный факт ограничивает эффективность использования данного метода только относительно небольшими графами. Влияние указанного ограничения можно уменьшить, если принимать во внимание особенности топологии графа и тем самым уменьшать число возможных комбинаций состояний, однако, при этом увеличивается сложность вычислений и снижается универсальность метода. В [35] приведены некоторые математические соотношения для определения диапазона, в котором находятся вероятностные характеристики PERT-графов, учитывающие временные характеристики подзадач и общую топологию графа. Использующие эти соотношения методы оценок PERT-моделей преобразовывают исходную модель к последовательно-параллельному графу, как правило, большей размерности. Такой граф предполагается более легким для расчетов, несмотря на сложности, описанные выше.
Некоторые методы получения граничных оценок характеристик для стохастических графов описаны в [35]. Большинство из них предполагают предварительную трансформацию исходного графа в последовательно-параллельный, что значительно упрощает процедуру анализа. Недостатком данной группы методов является слишком большая неточность полученных оценок, поскольку методы дают лишь граничные значения.
Для получения статистических оценок временных характеристик вычислительных процессов широко используются методы имитационного моделирования. Наиболее часто используемый подход к имитации стохастических динамичecкиx систем - метод Монте-Карло, использующий списки событий и вычисляющий время начала и конца выполнения подпроцессов. По собранным статистическим данным вычисляется время выполнения большого числа графов (так называемый метод тиражирования). Основным недостатком имитационных методов моделирования является необходимость предварительного сбора и/или генерации достаточно большого объема статистических данных. Погрешность результатов, получаемых в результате имитационного моделирования, сильно зависит от качества и количества исходных статистических данных. Список работ по исследованию методов уменьшения погрешности приведен в [40].
Однако если для PERT-сетей существуют известные математические соотношения между моментами Х(к), кєУ, то возможно аналитическое моделирование системы. В этом случае время выполнения процесса может быть вычислено довольно быстро. Так, в [41,56] представлены соотношения для получения оценок вероятности времени выполнения параллельных процессов, в которых используется функция синхронизации «И».
Для представления сложных процессов, а также параллельных вычислений на параллельных архитектурах необходимо вводить различные функции синхронизации, отличные от функции "И", применяемой в традиционных PERT-моделях. Некоторые авторы предложили обобщения PERT-сетей, использующие набор логических функций объединения подзадач [57-59].
Так, в [53,45] используются модели с двумя типами синхронизационных примитивов: "И" и "ИЛИ". Кроме того, число дуг в графе может быть недетерминированным. Данный факт может трактоваться как возможность для задач не создавать зависимости (или обмена сообщениями) с другими задачами. В этом случае синхронизации и зависимости в графе должны быть тщательно выверены во избежание тупиковых ситуаций. Например, на рис. 1-7 допустимы только варианты а), Ь), с).
Обоснование выбора метода для анализа мннгоороовнеых ссем принятия решений
Качество систем мониторинга и, в первую очередь, такие их важнейшие свойства, как надежность и быстрота обнаружения и реагирования на происходящие события, необходимо обеспечивать на всех этапах жизненного цикла систем: проектирования, изготовления, функционирования. На первом этапе качественные показатели достигаются выбором конструкторско-технологических рещений. На втором этапе определяющим является строгое соблюдение технологических и метрологических норм. Обеспечение качества в процессе функционирования системы мониторинга требует текущего отслеживания процессов, происходящих в системе, с учетом реального масштаба времени.
Моделирование реально существующей или проектируемой системы мониторинга производится с целью получения оценок значимых характеристик системы (таких как, например, время реакции на внештатную ситуацию, объем требуемых ресурсов) при различных вариантах ее организации, выбора наиболее рационального (в ряде случаев, оптимального) решения с точки зрения заранее определенного набора критериев, устранения «узких мест» в системе.
Процесс моделирования процессов, протекающих в СМУ, можно условно разделить на следующие этапы: 1. Определение структуры СМУ. 2. Выбор модели для описания СМУ. 3. Проведение моделирования. 4. Обработка полученных при моделировании результатов.
На первом этапе необходимо четко представлять функциональную структуру моделируемой системы, основные ее компоненты и связи между ними. Составляется схема взаимодействия процессов, присущих СМУ. Определяются вопросы, ответы на которые должны быть получены после проведения моделирования. Например, сколько времени понадобится системе на обнаружение того или иного события и возможно ли его уменьшить? Какова устойчивость системы к появляющимся сбоям? Возможно ли снижение загрузки оборудования -сетевого трафика, требуемого объема памяти?
На втором этапе на основе информации, полученной ранее, выбирается тип модели, позволяющей анализировать процессы, протекающие в данной системе, с минимальными затратами на реализацию алгоритма моделирования. Затем строится модель СМУ выбранного типа.
Третий этап заключается непосредственно в проведении анализа построенной модели с помощью известных методов. Как правило, этот этап частично или полностью автоматизирован, получение численных характеристик исследуемой системы производится с помощью инструментального программного обеспечения.
На четвертом этапе анализируются полученные результаты моделирования. Его целью является получение ответов на поставленные на первом этапе вопросы. Эти вопросы могут иметь характер как количественный (оценки времени выполнения той или иной функции), так и качественный (выявление «узких мест» в системе). По результатам работы на данном этапе формируются основные выводы и, при необходимости, моделирование системы может быть продолжено по более расширенной программе или с использованием модифицированной модели.
При моделировании системы мониторинга сложного объекта решаются следующие задачи: 1) создание достоверных моделей состояния конкретных процессов, происходящих в наблюдаемом объекте, полнота которых достаточна для обеспечения заданного качества; 2) разработка стратегии наблюдения за параметрами процессов, достаточной для требуемой полноты моделей состояния; 3) разработка стратегии оценивания наблюдаемых параметров; 4) разработка стратегии принятия решения о происходящих событиях. Первая задача связана с моделированием конкретных объектов и разработкой на его основе моделей, определяющих требуемое качество. Вторая содержит множество подзадач оптимизации структуры системы мониторинга в соответствии с принятыми критериями качества (временными, точностными, надежностными, стоимостными и т.д.). Две последние проблемы базируются на вероятностно-статистической оценке параметров, проверке гипотез и принятии решений. В зависимости от характера наблюдаемого объекта и требуемого качества осуществляется выборочная оценка наблюдаемых параметров или строится система статистического контроля качества (statistical process control - SPC) с использованием современных методов, таких как, например, адаптивная робастная статистика [91] или последовательные методы обнаружения появляющихся событий [60].
В предыдущем параграфе было выделено три подхода к моделированию вычислительных процессов с точки зрения способа получения их характеристик и сформировано заключение о том, что там, где это возможно, предпочтительно использовать аналитические методы моделирования. Доля аналитической составляющей в современных системах моделирования вычислительных процессов сравнительно невелика, что объясняется сложностью получения адекватных соотношений для описания поведения большинства моделируемых объектов. Усиление математического аппарата для анализа вычислительных процессов позволит снизить временные и ресурсные затраты на получение их характеристик, увеличит универсальность используемого инструментария для исследования различных групп моделируемых объектов.
Таким образом, задача расширения математического аппарата для анализа вычислительных процессов является насущной и актуальной. Данная работа посвящена проблеме моделирования вычислительных процессов в системах мониторинга и управления. Модели, описывающие объекты подобного рода, должны учитывать: последовательно-параллельный характер процессов; иерархический характер моделируемой системы; комплексирование процессов младшего уровня иерархии на более высоком уровне с помощью различных правил, которые могут быть описаны логическими функциями; возможные временные зазоры, интервалы ожидания при объединении процессов нижних уровней.
Построение математической модели процесса принятия решений в системе мониторинга и управления поведением судна
Проверка работоспособности и корректности проведения анализа параллельных процессов проводилась следующим образом: 1. Выбор тестовой модели определенного типа (из указанных в п.п. 1-4). 2. Построение графа возможных реализаций модели вручную и расчет оценок временных характеристик модели по формулам (2-3-1) - (2-3-3). 3. Представление описания модели в формате исходных данных программы расчета. Указанное действие может осуществляться путем ввода графического образа модели в редакторе моделей либо вручную, либо с помощью набора утилит-генераторов формализованных описаний для типовых моделей. 4. Получение оценок временных характеристик модели с помощью программы расчета, реализующей метод отыскания групп совместных верщин. 5. Получение оценок временных характеристик модели с помощью программы, реализующей метод свертки. 6. Сопоставление результатов, полученных при выполнении п.п.2,4,5.
При проведении тестирования основной акцент делался на проверку корректности работы программы, поэтому использовались модели элементарных процессов. Общая структура таких процессов имеет вид, представленный на рис. 2-4. Более детальное описание моделей раскрыто в следующем параграфе.
Тестовый анализ всех типов указанных процессов подтвердил корректность работы программной реализации метода анализа параллельных процессов посредством отыскания групп совместных вершин. При проведении обширного эксвперимента с сопоставлением результатов, полученных методом свертки и методом отыскания групп совместных вершин, показало, что оба метода позволяют получить одинаковые оценки плотности распределения вероятностей времен окончания выполнения анализируемых процессов. При этом установлено, что факт совпадения результатов инвариантен относительно структуры вычислительного процесса и возможных значений статистических характеристик последовательных вычислительных процессов.
Для примера рассмотрим последовательно-параллельные процессы, показанные на рис.2-8, где FF - логическая функция разветвления (запуска) процессов; Fj - логическая функция объединения процессов; Si, 82,83 - временные задержки синхронизации 1, 2 и 3 подпроцессов соответственно. Последовательные подпроцессы 1, 2 и 3 обладают соответственно следующими плотностями распределения вероятностей времени выполнения: /,[1]=0.5;/і[2]=0.5 /2[1]=0.5;/2[2]=0.3;/2[1]=0.2 /з[1]=0.4;/з[2]=0.3;/з[1]=0.2;/3[2]=0.1.
Указанные числовые параметры моделируемых подпроцессов соответствуют ситуации обнаружения появившегося события, что является типичным случаем для систем мониторинга.
Наиболее интересными представляются случаи комплексирования последовательных подпроцессов согласно логической функции «И» с различными задержками ожидания синхронизации, а также комплексирование подпроцессов, ожидающих выполнения условий синхронизации неограниченное время и объединяемых по функции «М из N».
В табл. 2-1 представлены параметры описания моделей, взятых в качестве примеров, и найденные оценки математического ожидания времени выполнения анализируемого параллельного вычислительного процесса.
Подтвержденная корректность функционирования новых разработанных средств позволяет перейти к исследованию закономерностей в поведении временных характеристик параллельных вычислительных процессов.
С помощью инструментального программного обеспечения, представленного в предыдущих параграфах, проведено исследование временных характеристик параллельных вычислительных процессов. При этом задействован метод отыскания групп совместных вершин.
Поскольку на данном этапе работы целью исследования являлось выявление основных закономерностей поведения временных характеристик параллельных процессов с различными способами объединения последовательных фрагментов, то в качестве анализируемых моделей также использовались несложные типовые структуры, отражающие функциональные особенности как моделируемых, так и реальных процессов.
Исследование осуществлялось для моделей двухуровневых процедур принятия решений с параллельной обработкой данных. Эксперименты проводились в соответствии со следующим планом: 1. Сравнение времени выполнения процессов при различных способах объединения частных последовательных процессов. Здесь рассматривались четыре способа объединения: последовательное выполнение, объединение по "И" с нулевой и бесконечной задержками, по "ИЛИ". 2. Сравнение времени выполнения процесса, реализующего функцию объединения решающих правил по принципу "М из N" в зависимости от значения порога М. 3. Сравнение времени выполнения параллельного процесса при комплексировании решений по "И" с фиксированными задержками. 4. Варьирование задержек в диапазоне от нулевых до стремящихся к бесконечности.
При выполнении пунктов 1 и 2 плана рассмотрено 2 группы параллельных процессов, для которых характерны следующие особенности: 1) в частных последовательных подпроцессах вероятности обнаружения события в каждом из промежуточных состояний (то есть вероятности перехода к последней вершине) меньше 0.5;
