Адаптивный алгоритм управления координатором в распределенных системах обработки информации

• Автор: Сан Ян Наинг У
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 142 с. : ил.

СОДЕРЖАНИЕ

СПИСОК СОКРАЩЕНИЙ ВВЕДЕНИЕ

1. АНАЛИЗ АЛГОРИТМОВ СИНХРОНИЗАЦИИ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

1.1. Характеристики распределенных вычислительных систем

1.1.1. Особенности распределенных вычислительных систем

1.1.2. Классификация распределенных вычислительных систем

1.2. Распределенные алгоритмы синхронизации

1.2.1. Особенности алгоритмов синхронизации в распределенных системах

1.2.2. Распределенные алгоритмы взаимного исключения

1.2.3. Распределенные алгоритмы управления координатором

2. АНАЛИЗ ПРОБЛЕМ ГРУППОВОЙ РАССЫЛКИ СООБЩЕНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
2.1. Групповая рассылка сообщений и области ее применения
2.1.1. Характеристики групповой рассылки
2.1.2. Надежная групповая рассылка
2.2. Модели и схемы групповой рассылки в распределенных системах
2.2.1. Типы деревьев маршрутизации групповой рассылки
2.2.2. Нахождение оптимального дерева маршрутизации
2.3. Алгоритмы групповой рассылки
2.3.1. Групповая рассылка на канальном уровне
2.3.2. Групповая рассылка на сетевом уровне
3. РАЗРАБОТКА АДАПТИВНОГО АЛГОРИТМА УПРАВЛЕНИЯ КООРДИНАТОРОМ ДЛЯ РСОИ С НАДЕЖНОЙ ГРУППОВОЙ РАССЫЛКОЙ
3.1. Описание адаптивного алгоритма управления координатором
3.1.1. Предпосылки и общая характеристика алгоритма
3.1.2. Формальное описание алгоритма
3.1.3. Анализ сложности алгоритма
3.2. Анализ сценариев работы алгоритма
3.3. Ограничения алгоритма
3.4. Реализация подсистемы голосования
3.4.1. Общая схема подсистемы
3.4.2. Реализация блока голосования в узле распределенной системы
СV
4. ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК АДАПТИВНОГО АЛГОРИТМА УПРАВЛЕНИЯ КООРДИНАТОРОМ
4.1.Имитационная модель для исследования адаптивного алгоритма управления координатором
4.1.1. Формальный аппарат имитационного моделирования
4.1.2. Структура имитационной модели
4.1.3. Модель коммуникационной подсистемы
4.1.4. Модель узла распределенной системы
4.2. Результаты имитационных экспериментов
4.2.1. Зависимость коммуникационной сложности от числа процессов
4.2.2. Зависимость коммуникационной сложности от изменений значений таймаутов
4.2.3. Зависимость коммуникационной сложности от числа процессов в адаптивном алгоритме
4.3.Исследование адаптивного алгоритма управления координатором к условиям переменного сетевого трафика
4.3.1. Влияние сетевого трафика на работу алгоритма управления координатором
4.3.2. Методы адаптации, основанные на сглаживании
4.3.3. Методы адаптации, основанные на нейронных сетях
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


На основе аналитического обзора средств и методов анализа алгоритмов показана актуальность разработки алгоритмов выбора координатора. Проведена классификация существующих алгоритмов выбора координатора. Разработан и исследован адаптивный алгоритм управления координатора в РСОИ, имеющий меньшую коммуникационную сложность, чем существующие алгоритмы, и адаптирующийся к условиям переменного сетевого трафика. Разработано формализованное описание и математическая модель подсистемы выбора координатора на основе адаптивного алгоритма. Разработана имитационная модель РСОИ для выбора координатора в терминах расширенных сетей Петри при помощи программного средства моделирования Vinsim. Реализована подсистема выбора координатора для РСОИ с использованием языка программирования С в ОС М1Х. Проведен анализ динамики изменения коммуникационной сложности алгоритма в зависимости от длительности тайм-аутов для разного количества процессов. Все работы но реализации и внедрению проводились при непосредственном участии автора. Результаты диссертационной работы используются в учебном процессе кафедры ИПОВС Московского государственного института электронной техники. Адаптивный алгоритм управления координатором в РСОИ в условиях надежной групповой рассылки, обеспечивающий низкий сетевой трафик. Формализованное описание, аналитическая и имитационная модель подсистемы выбора координатора для РСОИ, использующие адаптивный алгоритм управления координатором для РСОИ в условиях надежной групповой рассылки. Программная реализация блока голосования в узле РСОИ с использованием языка программирования С в операционной системе ЦГПХ. Результаты внедрения, экспериментальных исследований и апробация материалов диссертационной работы. Международная школа-конференция (по приоритетному направлению «Информационно-телекоммуникационные системы» с участием молодых ученых, аспирантов и студентов стран-членов СНГ) - Москва, МИЭТ, . Всероссийская межвузовская научно-техническая конференция студентов и аспирантов “Микроэлектроника и информатика - ” -Москва, МИЭТ, . Всероссийская межвузовская научно-техническая конференция студентов н аспирантов “Микроэлектроника и информатика - ” -Москва, МИЭТ, . XI Московская международная телекоммуникационная конференция студентов и ученых «Молодежь и наука» - Москва, МИФИ, . По результатам проведенных научных исследований опубликовано 8 печатных работ без соавторов, в том числе одна работа - в издании, входящем в перечень ВАК. Работа изложена на 2 страницах, содержит 8 таблиц и рисунка. В первой главе представлено описание предметной области, проведен анализ проблематики синхронных РСОИ. Выполнен обзор РСОИ и их классификации, проводимые по различным признакам, рассмотрены области применения распределенных систем различных типов. Проведен обзор существующих методов синхронизации процессов в РСОИ по различным классифицирующим группам, в частности, таким, как алгоритм взаимного исключения и выбора координатора. Во второй главе проведен анализ проблем групповой рассылки сообщений в распределенных вычислительных системах. Дана общая характеристика надежной групповой рассылки. Проведен анализ модели и схемы групповой рассылки в РСОИ, анализ типов деревьев маршрутизации групповой рассылки, а также методов нахождения оптимального дерева маршрутизации. Классифицированы алгоритмы групповой рассылки. В зависимости от уровня, который отвечает за создание дерева, а также его поддержание и использование для пересылки сообщений, можно создать дерево групповой рассылки на канальном , сетевом или прикладном уровне. В третьей главе разработано формальное описание адаптивного алгоритма голосования и разработана общая схема алгоритма. Даны главные аспекты предложенного алгоритма, типы сообщений и переменные, используемые в алгоритме. Разработана диаграмма состояния алгоритма для процесса РСОИ. Разработана реализация адаптивного алгоритма управления координатором в операционной системе ИЫ1Х, где процессы направляют сообщение через групповую рассылку с использованием сокетов 1ЮР и аналитическая модель адаптивного алгоритма.