Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов и средств моделирования систем распределенной обработки информации (РОИ) 9
1.1. Анализ характеристик систем РОИ 9
1.2. Анализ процесса проектирования систем РОИ 19
1.3. Анализ формальных моделей, используемых для исследования систем РОИ 20
1.3.1. Анализ возможностей сетевых моделей 21
1.3.2. Классификация и характеристики низкоуровневых сетей Петри 29
1.3.3. Классификация и характеристики высокоуровневых сетей Петри 34
1.4. Сравнительный анализ средств имитационного моделирования систем РОИ 42
ГЛАВА 2. Разработка формального аппарата для представления моделей систем рои 51
2.1. Требования к формальному аппарату для представления моделей систем РОИ 51
2.2. Общее описание Е-сетей и модифицированных Е-сетей 53
2.3. Алгебра модифицированных Е-сетей 65
2.4. Алгоритм функционирования модифицированных Е-сетей . 11
2.5. Язык описания сетевой модели 83
2.6. Язык управления процессом моделирования 89
ГЛАВА 3. Разработка комплекса имитационного моделирования 98
3.1. Требования к комплексу имитационного моделирования Winsim 98
3.2. Выбор архитектуры комплекса имитационного моделирования Winsim 101
3.2.1. Креативная система 106
3.2.2. Реализация компилятора языка MDL 110
3.2.3. Исполнительная система 121
3.3. Анализ возможностей распараллеливания процессов имитационного моделирования на группе компьютеров в ЛВС 136
ГЛАВА 4. Применение комплекса winsim для исследования систем рои 146
4.1. Методика представления систем РОИ на языке MDL 146
4.2. Исследование модели локальной вычислительной сети с кольцевой топологией 156
4.3. Исследование модели локальной вычислительной сети типа Ethernet 167
4.4. Исследование распределенных алгоритмов взаимного исключения 176
4.4.1. Алгоритм Рикарта-Агравала 181
4.4.2. Алгоритм Трехеля 194
4.4.3. Алгоритм Судзуки-Касами 200
Выводы 209
Заключение 210
Литература 212
- Анализ характеристик систем РОИ
- Требования к формальному аппарату для представления моделей систем РОИ
- Требования к комплексу имитационного моделирования Winsim
- Методика представления систем РОИ на языке MDL
Введение к работе
Актуальность проблемы. В настоящее время интенсивно развиваются системы распределенной обработки информации, которые широко применяются во многих областях деятельности: в промышленности, в автоматизированных системах научных исследований, при управлении сложными транспортными средствами, в бортовых управляющих комплексах. Типичными примерами систем РОИ являются локальные и глобальные вычислительные сети, автоматизированные системы управления производством, распределенные операционные системы.
Основное преимущество распределенных систем по сравнению с централизованными - их принципиальная способность выполнять параллельные вычисления. Из других достоинств систем РОИ следует отметить возможность достижения высокой суммарной производительности, лучшее соотношение цена/качество по сравнению с централизованной системой аналогичной производительности, обеспечение постепенной деградации системы при отказе части входящих в нее вычислителей, повышение эффективности совместного использования ресурсов потребителями, достаточно высокая надежность при относительно невысокой стоимости, возможность реализации более гибких стратегий управления путем динамического изменения схем диспетчирования задач и реконфигурации системы.
Несмотря на успехи, достигнутые в области исследования и реализации систем РОИ, здесь существует много нерешенных проблем как теоретического, так и практического характера. Так как любая система РОИ представляет собой очень сложный объект, то, не имея ее работоспособной модели, такую систему очень трудно отладить и реализовать даже при наличии в ней 10-20 узлов. Постоянное развитие новых методов и средств реализации систем РОИ также требуют разработки новых формальных методов и средств исследования распределенных систем, которые могли бы служить практическим инструментом на стадии проектирования систем
РОИ, а также для устранения «узких» мест в уже существующих распределенных системах. Этой тематике и посвящена данная работа.
Цель работы. Целью диссертационной работы является разработка средств моделирования для исследования систем РОИ на основе формального аппарата класса расширенных сетей Петри - так называемых модифицированных Е-сетей.
Поставленная цель определяет следующие основные задачи диссертационной работы:
развитие перспективного формального аппарата для представления моделей систем РОИ на основе Е-сетей;
разработка принципов построения и алгоритмов функционирования комплекса имитационного моделирования на основе аппарата Е-сетей для описания и исследования систем РОИ;
программная реализации комплекса имитационного моделирования на основе аппарата Е-сетей для описания и исследования систем РОИ;
разработка методики построения и исследования Е-сетевых моделей систем РОИ;
разработка и исследование моделей систем РОИ.
Методы исследования. Для решения сформулированных задач использовались методы теории графов, сетей Петри, теории систем массового обслуживания, теории вероятностей, аналитического и имитационного моделирования дискретных систем.
Научная новизна. В ходе решения задач диссертационной работы получены следующие новые научные результаты, выносимые на защиту:
Введены новые операции над модифицированными Е-сетями и изучены их свойства.
Разработаны принципы организации и алгоритмы функционирования программного комплекса имитационного моделирования на основе модифицированных Е-сетей.
Реализована интегрированная среда разработки в составе комплекса имитационного моделирования Winsim и подсистема сборки модели.
Разработана методика представления систем РОИ в виде модифицированных Е-сетей.
Разработаны и исследованы сетевые модели локальных вычислительных сетей Token Ring и Ethernet и распределенных алгоритмов взаимного исключения Ршарта-Агравала, Трехеля и Судзуки-Касами.
Практическая ценность работы. Созданные программные инструментальные средства в виде комплекса имитационного моделирования Winsim, могут использоваться для автоматизации построения и исследования имитационных моделей систем РОИ, в частности, при проектировании и исследовании перспективных архитектур систем обработки данных, в том числе -высокопроизводительных распределенных систем. Этот комплекс может быть использован при изучении вузовских дисциплин, в которых рассматриваются организация вычислительных процессов, построение вычислительных сетей, организация параллельной и распределенной обработки информации. Предложенные в диссертационной работе способы распределенной реализации имитационного комплекса обеспечивают возможность эффективного моделирования систем практически неограниченных размеров и сложности. Разработанные и исследованные в работе Е-сетевые модели алгоритмов взаимного исключения могут быть использованы при анализе и модификации протоколов в распределенных системах. Обоснование применения математического аппарата систем массового обслуживания замкнутого типа для аналитического исследования этих алгоритмов позволяют проводить верификацию результатов имитационного моделирования и исследование эффективности подобных алгоритмов. В целом результаты диссертации, включая разработанные программно-инструментальные средства, позволяют практически применять перспективный формальный аппарат модифицированных Е-сетей для исследования систем РОИ и принимать на
этой основе обоснованные решения при выборе параметров, выявлении и устранении "узких" мест в системах РОИ.
Реализация и внедрение результатов работы. Основные результаты диссертационной работы используются в учебном процессе Московского государственного института электронной техники (технического университета) при изучении дисциплин "Вычислительные системы и сети" и "Теория вычислительных процессов" и в Восточносредиземноморском университете (Турция) в научных исследованиях и при изучении дисциплины "Имитационное моделирование систем", что подтверждено актами внедрения.
Апробация работы. Основные результаты диссертационной работы были апробированы на международных, всероссийских и межвузовских научно-технических конференциях и семинарах, что отражено в списке литературы. Разработанные с участием автора диссертации микрокомпьютерная система имитационного моделирования Микросим и комплекс имитационного моделирования Winsim, реализующие формальный аппарат модифицированных Е-сетей, прошли государственную регистрацию в РОСПАТЕНТ (регистрационные №№ 2002610187 и 2002610717). Комплекс Winsim зарегистрирован на международном Web-сайте [94] в списке программных продуктов, основанных на сетях Петри и их расширениях.
Публикации. Содержание диссертации отражено в 20 опубликованных работах, в том числе в двух свидетельствах РОСПАТЕНТа РФ.
Краткое содержание работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 132 наименований и четырех приложений.
В первой главе дана общая характеристика систем распределенной обработки информации, рассмотрены методы формализованного описания и моделирования систем РОИ. Особое внимание уделено при этом сетям Петри и их расширениям, среди которых для дальнейшего исследования выбраны Е-сети.
Во второй главе представлены элементы теории модифицированных Е-сетей как перспективного аппарата формализованного описания и моделирования систем РОИ; дано формальное определение структуры модифицированных Е-сетей, введены новые операции над модифицированными Е-сетями и изучены их свойства, описана семантика базовых структурных компонентов модифицированных Е-сетей; описаны языки, используемых в спецификации и решении Е-сетевых моделей - язык описания сетевых моделей MDL {Model Description Language) и язык управления процессом моделирования MCL (Modeling Control Language).
В третьей главе излагаются принципы построения, алгоритмы и особенности реализации комплекса имитационного моделирования Winsim. Проведен анализ возможностей распараллеливания процессов имитационного моделирования на группе персональных компьютеров в локальной вычислительной сети.
В четвертой главе приведена методика представления систем РОИ на языке MDL, дано описание ряда типовых компонентов систем РОИ; при помощи комплекса Winsim исследованы Е-сетевые модели локальных вычислительных сетей Token Ring и Ethernet и Е-сетевые модели распределенных алгоритмов взаимного исключения Рикарта-Агравала, Трехеля и Суд-зуки-Касами.
В приложениях приведен синтаксис языка описания сетевых моделей MDL и языка управления процессом имитационного моделирования MCL, описаны стандартные функции в языке MDL и представлены акты внедрения результатов диссертации.
Автор выражает искреннюю благодарность научному консультанту профессору А.Е. Костину и научному руководителю профессору Л.Г. Гагариной за помощь при работе над диссертацией.
Анализ характеристик систем РОИ
Системы РОИ характеризуются наличием нескольких центров обработки данных. К таким системам относятся сети вычислительные, телефонные, нейронные, а также другие системы обработки информации. Для целей настоящего исследования круг систем РОИ ограничим вычислительными системами. Под термином "система РОИ" понимают совокупность процессов, выполняющихся в различных узлах вычислительной сети и вовлеченных в координированное решение общей задачи путем прямой или косвенной (например, для систем РОИ с общей памятью) передачи сообщений. Таким образом, характерными чертами распределенной системы являются [82,123]: - множество процессов; - наличие вычислительной сети; - удаленность процессов друг от друга; - решение общей задачи; - обмен сообщениями. Исходя из вышеприведенного определения, независимые (т.е. не обменивающиеся сообщениями) приложения в вычислительной сети не образуют распределенную систему. Для системы РОЙ характерна асинхронная работа входящих в нее компьютеров, при этом каждый из компьютеров способен осуществлять обработку данных самостоятельно, независимо от других компьютеров системы. Распределенное программное обеспечение координирует работу компьютеров и разделяет программные и аппаратные ресурсы системы и данные. Грамотно спроектированная система РОИ выглядит для пользователя как единый мощный вычислитель, хотя она может быть рассредоточена на многих компьютерах, удаленных друг от друга на значительные расстояния. Разработка систем РОИ последовала за созданием в начале 1970-х гг. высокоскоростных локальных вычислительных сетей (ЛВС). В следующие два десятилетия толчок к дальнейшему развитию систем РОИ дали доступность высокопроизводительных персональных компьютеров, рабочих станций и серверов. В настоящее время тенденция к уходу от централизованных и многопользовательских компьютеров к распределенной обработке информации продолжается. Она была ускорена разработкой распределенного системного программного обеспечения, способствующего разработке распределенных приложений. Системы РОИ по сравнению с централизованными обладают следующими преимуществами [82, 123]: - лучшим соотношением цена/производительность: сеть рабочих станций обеспечивает большее количество операций в секунду, чем равный ей по цене мэйнфрейм; - более высокой производительность: п компьютеров теоретически могут обеспечить в п раз большую вычислительную мощность, чем одиночный компьютер; - разделением ресурсов: дорогие или не имеющиеся в достаточном количестве ресурсы могут использоваться многими компьютерами; - масштабируемостью: модульная структура облегчает замену или добавление процессоров и других ресурсов; - надежностью: репликация ресурсов и данных повышает отказоустойчивость системы. Важное значение при разработке и исследовании систем РОИ имеет их классификация, которая может проводиться по разным признакам. В различных схемах классификации систем РОИ наиболее часто используются такие признаки, как степень связности узлов распределенной системы друг с другом, способ коммуникации между узлами, способ и уровень декомпозиции общей задачи, однородность узлов и топологическая структура системы. В соответствии с общей классификацией вычислительных систем, разработанной организацией ACM (Association for Computing Machinery) в 1998 г. и дополненной в 2002 г. [124], системы РОИ разделяются на следующие категории:
Требования к формальному аппарату для представления моделей систем РОИ
Разрабатываемый формальный аппарат предназначается для специалистов, имеющих высокую квалификацию в области проектирования систем РОИ, но не обладающих специальными знаниями в области моделирования. Поэтому формальный аппарат должен быть достаточно развитым, чтобы обеспечить представление разнообразных компонентов систем РОИ, и в то же время достаточно простым, чтобы пользователь мог овладеть им без особого труда.
Формальный аппарат должен предлагать разработчику модели такую схему представления, которая облегчает переход от исследуемого объекта к модели этого объекта, является общей для различных классов моделируемых систем РОИ, обладает простотой интерпретации и обеспечивает автоматическое выполнение динамики модели.
Поскольку при проектировании современных систем РОИ в целях повышения их быстродействия широко используются принципы совместного выполнения различных операций во времени, формальный аппарат должен обеспечивать представление параллельных процессов, протекающих в моделируемой системе.
В формальном аппарате должны быть предусмотрены средства для иерархического представления отдельных компонентов модели и модели в целом, следуя структуре и функциям исследуемой системы РОИ. Эти средства должны обеспечивать желаемую степень детализации при описании различных частей системы. При этом в модели могут одновременно присутствовать компоненты разной степени детализации, потому что разработчик в редких случаях исследует систему РОИ только "сверху вниз" или "снизу вверх"; чаще ему приходится сосредоточивать свое внимание на отдельных частях системы, сохраняя достигнутую степень детализации остальных частей. Возможность иерархического представления освобождает разработчика от необходимости заранее фиксировать степень детализации модели и повышает обозримость модели.
Формальный аппарат должен обеспечивать представление исследуемой системы РОИ в двух формах: графической, которая является привычной и удобной для специалиста, и операторной, которая служит средством общения разработчика модели с системой моделирования на этапе построения и отладки модели. Существование этих двух форм облегчает документирование процесса разработки и использования модели.
Всем перечисленным требованиям удовлетворяет рассматриваемый в этой главе аппарат модифицированных Е-сетей, которые являются одним из расширений сетей Петри, рассмотренных в гл. 1. Сохраняя ряд достоинств сетей Петри, Е-сети позволяют в то же время выражать преобразования данных, время и контроль и поэтому могут служить в качестве развитого языка моделирования систем РОИ. В работе [99] доказано, что Е-сети могут моделировать машину Тьюринга, и, следовательно, применимы для описания любых алгоритмов, представимых машиной Тьюринга.
Требования к комплексу имитационного моделирования Winsim
Модифицированные Е-сети, описанные в предыдущей главе, были использованы в качестве формального аппарата представления моделей при разработке комплекса имитационного моделирования Winsim [15, 26, 27, 28, 29, 30], предназначенного для описания и анализа систем РОИ. Комплекс Winsim предназначен для имитационного моделирования с целью верификации и комплексной оценки эффективности систем параллельной и распределенной обработки данных, включая мультипрограммные и мультипроцессорные системы, локальные вычислительные сети, коммуникационные протоколы и т.п. Наиболее полно возможности Winsim раскрываются при моделировании сложных алгоритмов и систем обработки данных с выраженным параллелизмом протекающих в них процессов. Winsim пригоден для имитационного моделирования широкого класса дискретных систем распределенной обработки информации (вычислительные устройства, системы и сети, всевозможные коммуникационные, транспортные и складские системы, нейронные сети и т.п.). Формализованное описание объектов моделирования в Winsim осуществляется при помощи модифицированных Е-сетей на языке MDL (см. п. 2.5 и Приложение 1), имитационное моделирование Е-сетей выполняется интерпретатором (Е-сетевой машиной) в соответствии с алгоритмом, описанным в п. 2.4. Параметры для решаемых имитационных моделей задаются с помощью языка MCL, описанного в п. 2.6 и Приложении 2. Математическая модель, представленная в виде одного или нескольких сегментов на языке MDL (определение сегмента см. в п. 2.3 а также в п. 3.2), может быть использована для получения детальных сведений о функционировании и характеристиках моделируемой системы. Эти сведения получаются при помощи метода имитационного моделирования, в соответствии с которым следует преобразовать математическую модель в моделирующий алгоритм [2, 46, 47]. Для математической модели, представленной в терминах модифицированных Е-сетей на языке MDL, такой алгоритм, описанный в п. 2.4, реализуется Е-сетевой машиной. При этом описание структуры модифицированной Е-сети используется в качестве исходных данных для Е-сетевой машины, а функционирование модифицированной Е-сети имитируется Е-сетевой машиной в режиме интерпретации. Функции (процедуры), ассоциированные с различными элементарными сетями, преобразуются в машинный код, и при интерпретации модифицированной Е-сети они выполняются непосредственно. Е-сетевая машина должна действовать в составе соответствующего моделирующего комплекса, который, в дополнение к интерпретации Е-сетевой машины, должен обеспечивать формирование модели, ее компиляцию, сбор и предварительную обработку статистических данных, представляющих результаты моделирования, их хранение и выдачу пользователю в удобном для него виде. При имитации функционирования систем РОИ разработчик должен иметь возможность получать сведения о загруженности элементов системы, параметрах очередей, временах пребывания запросов в определенных местах системы, количестве обработанных запросов, временах прохождения запросов между определенными точками системы и т.п. [64] Помимо общих требований к возможностям системы имитационного моделирования на основе Е-сетей, изложенных в п. 1.4, отметим ряд дополнительных требований, предъявляемых к разрабатываемой системе, которые можно условно разделить на две группы. С точки зрения пользователя важнейшим требованием является простота общения с Winsim. Удовлетворению данного требования в значительной степени способствует удобный графический интерфейс для взаимодействия с пользователем интегрированной среды разработки комплекса Winsim и средства, предусмотренные в языках MDL и MCL. Другими требованиями, важными с точки зрения пользователя, является необходимость обеспечения: - возможности иерархической разработки модели; - вмешательства пользователя в процесс моделирования; - получения мгновенных "снимков" состояния любого элемента или совокупности элементов модели; - повторного запуска модели, начиная с любого указанного пользователем состояния; - получения достаточного объема статистической информации о работе модели; - документирования вариантов модели и результатов моделирования; - высокой скорости работы; - отсутствия жестких ограничений на размер модели. С точки зрения разработчика комплекс должен проектироваться как открытая система, допускающая развитие и модификацию ее структуры и функциональных возможностей. Для программной реализации Winsim следует выбрать язык программирования, обладающий широким спектром выразительных средств, обеспечивающий высокую скорость выполнения операций и допускающий перенос разработанного комплекса в другие операционные системы. В составе Winsim должны быть предусмотрены средства обработки динамических структур данных, генерации случайных чисел и управления наборами данных, хранящихся во внешней памяти.
Методика представления систем РОИ на языке MDL
При формализованном исследовании любой системы основными этапами являются [2, 11, 63]: 1) содержательное описание; 2) построение формализованной схемы; 3) разработка математической модели, которая затем исследуется либо аналитически либо при помощи метода имитационного моделирования.
На этапе содержательного описания получают исходные данные для построения Е-сетевой модели исследуемой системы. На данном этапе определяют назначение и состав системы, ее компоненты, характер запросов, схему их прохождения, обслуживания и т.п. Наличие содержательного описания системы позволяет перейти к следующему этапу - построению формализованной схемы.
Применительно к формализации систем в терминах Е-сетей второй этап включает в себя следующие шаги. 1. Декомпозиция всей системы на достаточно компактные функционально законченные модули. Каждый из таких модулей реализуется в виде сегмента Е-сети. В частном случае Е-сетевая модель может состоять из одного сегмента. 2. Затем для каждого из сегментов создается графическая Е-сетевая схема с использованием элементарных схем и Е-сетевых схем типовых компонентов систем РОИ, отражающая параллелизм и взаимодействие процессов в данном модуле, генерацию запросов (заявок), временные задержки, очереди, поглощение запросов, прерывание процессов, начальную маркировку позиций, а также связи данного модуля с остальными модулями системы.
На этапе разработки математической модели системы осуществляется спецификация наборов атрибутов для всех Е-сетевых схем, относящихся к данной системе, выбор законов распределения вероятностей для случайных величин, определение функций входного и выходного выбора, функций временной задержки и функций преобразования для всех тех элементарных сетей, для которых соответствующие функции, предусмотренные по принципу умолчания, не удовлетворяют разработчика модели. Для каждого модуля системы все эти сведения, вместе с Е-сетевой схемой модуля, образуют часть общей математической модели, называемой сегментом, который описывается на языке MDL.
Некоторые задачи бывает трудно представить только с использованием структурных методов представления, так как это приводит к сетевой модели большой размерности. Поэтому необходимо сочетание структурных и процедурных методов. Процедуры (функции) переходов позволяют повысить уровень инкапсуляции описания, заменяя собой целые подсети. Соотношение между степенью использования структурного и процедурного методов представления во многом определяется точкой зрения разработчика на предметную область, сложностью представления сетевой модели в целом.
Этап должен завершиться представлением каждого из сегментов, входящих в общую математическую модель, на языке описания моделей MDL. Таким образом, конечным результатом разработки математической модели системы в терминах Е-сетей служит один или несколько связанных друг с другом сегментов, представленных на языке MDL.
Полученные в ходе имитации результаты интерпретируются и анализируются разработчиком модели. При интерпретации результатов производится отображение полученных свойств модели на свойства реальной системы. Если при анализе получены удовлетворительные результаты, то на этом процесс проектирования с использованием комплекса Winsim заканчивается, появляется возможность перехода к следующим этапам проектирования. Если результаты неудовлетворительны, то производится возврат к более ранним этапам проектирования с модификацией исходных данных. Процесс проектирования итерационно продолжается до тех пор, пока не будут достигнуты положительные результаты.
Большой интерес представляют вопросы валидации сетевой имитационной модели. Валидация модели обычно определяется как доказательство того, что машинная модель в области ее применения обладает удовлетворительной степенью точности согласно с заданным применением модели. Валидация применяется на многих шагах процесса моделирования.
Похожие диссертации на Разработка средств моделирования для исследования систем распределенной обработки информации
