Содержание к диссертации
Введение
Глава 1. Мигрирующие системы 13
1.1. Введение
1.2. Понятие мигрирующих систем 15
1.3. Свойства мигрирующих систем 16
1.4. Системы мобильных агентов 18
1.4.1. Введение
1.4.2. Основные понятия 19
1.4.3. Стандарты 21
1.4.4. Области применения 22
1.4.5. Сравнение с мигрирующими системами 23
1.5. Контекстно-ориентированные системы 25
1.5.1. Введение
1.5.2. Основные понятия 26
1.5.3. Области применения 28
1.5.4. Сравнение с мигрирующими системами 29
1.6. Системы перераспределения нагрузки 31
1.6.1. Введение
1.6.2. Основные понятия 32
1.6.3. Области применения 35
1.6.4. Сравнение с мигрирующими системами 36
1.7. Применение мигрирующих систем 37
1.8. Выводы 39
Глава 2. Архитектура и работа мигрирующих систем 42
2.1. Принцип работы мигрирующих систем
2.2. Обобщенная архитектура сервиса мигрирующей системы 45
2.2.1. Модуль взаимодействия с другими репликами сервиса 46
2.2.2. Очередь запросов , 48
2.2.3. Диспетчер запросов 55
2.2.4. Интерфейс с клиентами 57
2.2.5. Модуль обработки запросов 59
2.2.6. Модуль получения контекстной информации 62
2.2.7. Модуль принятия решений 63
2.2.8. Модуль репликации и дерепликации сервиса 68
2.2.9. Модуль удаленной загрузки и запуска приложений 72
2.3. Специализированные архитектуры мигрирующих систем 74
2.3.1. Архитектура мигрирующей системы для локальных сетей
2.3.2. Архитектура мигрирующей системы для глобальных сетей 77
2.4. Выводы 79
Глава 3. Математическое моделирование мигрирующих систем 80
3.1. Модель системы массового обслуживания
3.1.1. Определения
3.1.2. Ограничения, накладываемые на модель системы 81
3.1.3. Классификация. 82
3.1.4. Модель системы 83
3.2. Теоретико-множественно-событийная модель 93
3.3. Выводы 96
Глава 4. Имитационное моделирование мигрирующих систем 98
4.1. Методика построения мигрирующих систем
4.2. Архитектура системы моделирования 99
4.2.1. Задачи моделирования
4.2.2. Модель пользователя 100
4.2.3. Модель сети 102
4.2.4. Модель сервиса 104
4.2.5. Модуль сбора статистики 107
4.2.6. Модуль визуализации 109
4.2.7. Модуль хранения истории процесса моделирования 110
4.2.8. Случайные величины
4.3. Проектирование системы моделирования 112
4.3.1. Структура модели 113
4.3.2. Управление процессом моделирования 114
4.3.3. Модель сети 115
4.3.4. Модель узла 116
4.3.5. Модель сервиса 117
4.3.6. Модель реплики , , 122
4.3.7. Модель пользователя , 124
4.3.8. Модель запроса
4.3.9. Модель очереди 127
4.4. Эксперименты с системой моделирования 128
4.4.1. Анализ системы с одним сервисом в сети без отказов 4.4.2. Анализ системы в сети с отказами узлов 133
4.4.3. Анализ системы с несколькими сервисами 138
4.4.4. Определение параметров системы 142
4.4.5. Сравнение имитационной модели с моделью системы массового обслуживания 145
4.4.6. Оценка возможностей системы моделирования... 150
4.5. Выводы 153
Глава 5. Реализация прототипа мигрирующей системы 155
5.1. Инструменты разработки
5.2. Функции и структура системы 156
5.2.1. Консоль администратора (MSConsole) 158
5.2.2. Станция (MSStation) 163
5.2.3. Сервис (MSService) 165
5.2.4. Клиент (MSClient) 174
5.3. Исследование прототипа мигрирующей системы 179
5.4. Сравнение результатов имитационной модели и прототипа мигрирующей системы 181
5.5. Удаленная загрузка и запуск приложений средствами ОС 183
5.6. Выводы 184
Заключение 185
Список литературы
- Свойства мигрирующих систем
- Модуль взаимодействия с другими репликами сервиса
- Ограничения, накладываемые на модель системы
- Модуль хранения истории процесса моделирования
Введение к работе
Актуальность. Современные темпы развития корпоративных сетей и Internet требуют создания эффективного и надежного программного обеспечения, удовлетворяющего потребностям огромного числа пользователей. Сложность среды выполнения и отсутствие единой точки администрирования распределенных сетевых приложений привело к появлению программных систем, способных динамически адаптироваться к изменениям в сети, обеспечивая гибкое решение масштабируемости.
Одним из видов таких приложений являются мигрирующие системы. Они могут использоваться в различных прикладных областях для получения гибких, надежных и производительных программных комплексов, выполняющих обслуживание запросов внешних клиентов. Работа мигрирующих систем в первую очередь ориентирована на обслуживающие приложения без сложного внутреннего состояния, такие как Web-серверы со статическими Web-страницами, поисковые системы, Proxy-серверы, файловые серверы, доступные только для чтения. Наличие внутреннего состояния требует от распределенных компонентов мигрирующей системы координировать свои действия при изменении этого состояния для избежания конфликтов и сохранния целостности совместно используемых данных. С учетом этих ограничений мигрирующие системы могут успешно использоваться для серверов баз данных, почтовых серверов, файловых серверов с полным доступом при наличии, например, стандартных средств репликации баз данных.
Мигрирующие системы являются слабоизученной областью в сфере организации распределенных вычислений. Отсутствие теоретической базы и средств оценки характеристик различных архитектурных решений делают проектирование мигрирующих систем нетривиальной задачей. Важность выбора оптимальной архитектуры и определения параметров всех компонентов системы обусловлена сложной зависит мостью характеристик мигрирующей системы от тех решений, которые были приняты на этапах анализа и проектирования. Сложность разработки мигрирующих систем связана с их распределенным характером, работой в гетерогенной динамически изменяющейся среде и необходимостью автономно принимать решения с целью достижения оптимальных характеристик работы. Анализ существующих литературных источников показал, что хорошо изученными являются технологии, используемые при
10 построении мигрирующих систем, такие как мобильные агенты, динамическое перераспределение нагрузки, контекстно-ориентированные приложения. В общем случае представляет интерес возможность построения мигрирующей системы, в которой одновременно использовались бы все перечисленные технологии. Кроме того, в публикациях не рассматриваются модели и методы проектирования мигрирующих систем. Эти положения позволяют сформулировать цель работы следующим образом.
Цель работы. Целью работы является разработка обобщенной архитектуры и алгоритмов функционирования мигрирующих систем, использующих совокупность таких технологий как мобильные агенты, контекстно-ориентированные вычисления и системы перераспределения нагрузки, а также создание моделей и инструментов анализа, составляющих базу процесса проектирования мигрирующих систем. Для достижения поставленной цели в работе решаются следующие задачи: описание свойств мигрирующих систем и определение круга задач, для решения которых может использоваться данный класс распределенных приложений; разработка обобщенной и двух специализированных архитектур мигрирующих систем и сравнение характеристик, полученных для различных архитектурных решений; построение модели мигрирующей системы в рамках теории массового обслуживания, позволяющей исследовать ограниченное число процессов, протекающих в системе; построение формальной теоретике-множественно-событийной модели, включающей основные компоненты мигрирующей системы, среду ее выполнения и внешних пользователей, и определение множества событий, происходящих в системе; построение методики разработки мигрирующих систем на основе теоретико-множественно-событийных моделей; анализ, проектирование и реализация пакета программ для имитационного моделирования мигрирующих систем, учитывающего широкий круг параметров системы и ее окружения; проведение серии экспериментов, связанных с анализом и синтезом мигрирующих систем, и сравнение результатов, полученных с использованием теории массового обслуживания и системы имитации; - реализация прототипа мигрирующей системы обслуживания и сравнение характеристик прототипа с результатами, полученными для построенных моделей.
Предмет исследования. Объектом исследования являются мигрирующие системы, а предметом - методы анализа, моделирования, проектирования и реализации мигрирующих систем обслуживания.
Методы исследования. Для решения поставленных задач в работе используются методы теории множеств, теории систем массового обслуживания, теории автоматов, теории вероятности, исследования алгоритмов, моделирования, анализа и проектирования распределенных, многозадачных и многопоточных программных систем.
Научная новизна. В работе были получены следующие научные результаты: построена полностью децентрализованная обобщенная архитектура мигрирующих систем, отличающаяся тем, что она включает совокупность трех технологий — мобильных агентов, контекстно-ориентированных вычислений и перераспределения нагрузки, применяемых независимо в различных корпоративных системах; построена модель системы массового обслуживания, рассматривающая мигрирующую систему как обслуживающую систему, которая изменяет свое состояние под воздействием потоков событий. Модель позволяет уже на этапе проектирования получить такие характеристики системы как абсолютная пропускная способность или среднее время нахождения запроса в системе; построена формальная теоретико-множественно-событийная модель, описывающая как контекст выполнения, так и все компоненты мигрирующей системы, их взаимосвязь, события и операции, и позволяющая определять текущее состояние системы в зависимости от ее архитектуры и производимых воздействий; разработана методика построения мигрирующих систем на основе теоретико-множественно-событийных моделей, позволяющая выполнять анализ создаваемых распределенных мигрирующих приложений и получать их характеристики.
Достоверность. Достоверность полученных результатов подтверждается совпадением экспериментальных данных, полученных с помощью имитационной модели и разработанного прототипа мигрирующей системы.
Практическая значимость. В результате выполнения данной работы были получены следующие практические результаты: разработаны две специализированные архитектуры, дающие готовые проектные решения при реализации распределенных программных комплексов на основе мигрирующих систем, работающих в локальных и глобальных сетях; реализован пакет программ, позволяющий выполнять имитационное моделирование мигрирующих систем с целью получения характеристик для заданной архитектуры системы и параметров ее компонентов; написан прототип мигрирующей системы, позволяющий убедиться в корректности построенных моделей и методики, а также демонстрирующий использование методики на примере разработки распределенной системы поиска.
Апробация. Основные результаты работы докладывались на Международных конференциях по мягким вычислениям и измерениям (SCM) в 2002 - 2004 гг.
Публикации. По темам, связанным с проблематикой диссертации, опубликовано 6 печатных работ, включающих 3 статьи и 3 доклада на научно-технических конференциях:
Фомичев В. С, Холод И. И„ Першин А. В., Степанов А. Г. Поток сообщений в системах мобильных агентов // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2002). - СПб., 25 - 27 июня, 2002, СПбГЭ-ТУ.
Степанов А. Г. Свойства мигрирующих систем // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2003). - СПб., 25 - 27 июня, 2003, СПбГЭТУ.
Степанов А. Г. Применение моделей массового обслуживания для анализа мигрирующих систем // Материалы международной конференции по мягким вычислениям и измерениям (SCM'2004). - СПб., 17-19 июня, 2004, СПбГЭТУ.
Степанов А. Г., Фомичев B.C. Имитационная модель мигрирующей системы // Известия СПбГЭТУ «ЛЭТИ». - СПб., 2004.
Степанов А. Г., Фомичев B.C. Имитация мигрирующих систем обслуживания // Известия вузов. Приборостроение. - СПб., 5, 2005.
Степанов А. Г., Фомичев B.C. Пакет программ для имитации мигрирующих систем обслуживания // Известия вузов. Приборостроение. - СПб., 7,2005.
Свойства мигрирующих систем
Для описания объекта исследования был определен следующий набор свойств, наличие которых позволяет рассматривать обслуживающую систему как мигрирующую систему [98]: - мобильность кода и состояния (Code and State Mobility); - осведомленность в контексте (Context Awareness); - способность перераспределять нагрузку (Load Redistribution Facility); - автономность (Autonomy); - переносимость (Portability); - масштабируемость (Scalability); гибкость (Flexibility); - реагируемость (Reactivity); - активность (Activity).
Мобильность кода и состояния позволяет мигрирующим системам перемещаться по сети с одного узла на другой. Текущее состояние системы запоминается и пересылается вместе с ее кодом. После перемещения сохраненное состояние восстанавливается, и система возобновляет свое выполнение с точки останова.
Осведомленность в контексте обеспечивает мигрирующим системам возможность «чувствовать» среду выполнения. Обладая информацией о текущей и максимальной загрузке центрального процессора, уровне сетевого трафика, наличии других выполняющихся приложений, мигрирующие системы могут более точно выбирать свое местоположение, определять необходимость создания своих копий на других узлах сети и, как следствие, наиболее эффективно решать поставленные пользователем задачи.
Способность перераспределять нагрузку позволяет нескольким подсистемам мигрирующей системы, расположенным на разных узлах сети, распределять задачи пользователей (или отдельные части одной большой задачи) с учетом текущего и возможного состояния каждой подсистемы. Это свойство обеспечивает динамическое изменение производительности системы и значительно повышает ее надежность.
Автономность обеспечивает возможность работы мигрирующей системы без вмешательства системного администратора. Перед запуском системы администратор настраивает параметры ее работы, определяет начальный узел, на котором запускается система, и множество узлов, на которые она может быть перемещена. В дальнейшем система может работать самостоятельно.
Переносимость позволяет мигрирующим системам работать на различных программных и аппаратных платформах без перекомпиляции кода системы. Переносимость можно обеспечить двумя различными способами. Можно реализовать ее посредством использования интерпретируемых языков (Perl, Tel), обеспечив каждую вычислительную машину соответствующим интерпретатором. Можно использовать один из языков, поддерживающий раздельную компиляцию (Java, Oberon). Кроме того, язык должен поддерживать механизмы посылки, передачи, получения и выполнения кода [13].
Масштабируемость определяет способность мигрирующих систем гибко изменять свою производительность за счет перемещения на менее загруженный или более мощный узел сети или создания на других узлах своих копий, параллельно работающих с исходным экземпляром системы.
Гибкость означает возможность реализации в виде мигрирующей системы любой системы обслуживания, обрабатывающей потоки запросов пользователей. Мигрирующие системы определяют набор служб, связанных с приемом и отправкой запросов, сбором информации о среде выполнения, перемещением и т.д., а не классы решаемых задач.
Реагируемость является свойством системы, определяющим ее способность получать сигналы от внутренних и внешних источников. Сигнал может представлять собой как команду (например, от пользователя на перемещение), так и информационное сообщение (например, от операционной системы о завершении работы), на основании которого мигрирующая система может предпринять какие-то действия.
Активность определяет способность мигрирующей системы не просто реагировать на изменения внешней среды и обрабатывать команды, поступающие от пользователя и других систем, а также самой воздействовать на окружение, обеспечивая лучшие условия для своей работы.
Из перечисленных свойств основополагающими для мигрирующих систем являются первые три. Наличие остальных не является обязательным и определяется характером решаемой системой задачи. Полнота реализуемых в мигрирующей системе свойств может служить критерием, характеризующим ее качество.
В настоящее время наиболее полно концепция мобильности кода и состояния программных компонентов разработана в технологии мобильных агентов. Исследования в области агентских технологий начали проводиться в 70-х годах [48]. Эти исследования были связаны с работами по искусственному интеллекту. Можно выделить два основных этапа в истории исследования агентов. Первый начат около 1977 года и связан с исследованиями в области распределенного искусственного интеллекта. Тогда основное внимание было сосредоточено на агентах-консультантах. Второй этап начат относительно недавно, в начале 90-х годов, и характеризуется более широким кругом исследуемых типов агентов. Основной акцент сместился от агентов-консультантов к агентам, выполняющим некоторые действия от имени человека (агентам-представителям).
Модуль взаимодействия с другими репликами сервиса
Модуль взаимодействия с другими репликами обеспечивает механизм обмена информацией между всеми репликами сервиса. Выполняет следующие задачи: - поддерживает в актуальном состоянии информацию обо всех репликах, входящих в состав сервиса (доступность реплики, ее местоположение, загруженность реплики, производительность узла); обеспечивает синхронизацию данных в репликах (отслеживает изменения, происходящие, например, в очередях реплик).
Каждая реплика для обмена данными должна располагать информацией о местонахождении остальных реплик сервиса. Эта информация меняется динамически в процессе работы системы. Возможно несколько вариантов организации (рис. 2.4).
Вариант 1. Каждая реплика хранит список всех реплик сервиса (например, имя реплики, ее уникальных идентификатор (Replica IDentity, RID) и IP-адрес узла, на котором выполняется реплика).
Достоинства: - быстрый доступ к информации о любой реплике сервиса (список хранится локально); - отсутствие сетевого трафика при поиске информации о репликах.
Недостатки: - необходимость поддерживать актуальность хранимой информации о репликах (все изменения, связанные с созданием/удалением реплик должны отражаться во всех списках); - дополнительный сетевой трафик при создании/удалении реплик; - сложность обработки ситуации отказа реплик и узлов (при отказе не происходит автоматическое обновление списков реплик). Вариант 2. Список получается путем широковещательного опроса всех реплик сервиса (Broadcast Addressing). Каждая реплика «слушает» широковещательный канал и предоставляет информацию о себе по требованию.
Достоинства: не требуется хранение информации обо всех репликах сервиса, а также ее обновление при репликации/дерепликации; - актуальность информации обеспечивается автоматически (каждая реплика сама сообщает свое состояние остальным репликам); - решается проблема выявления неработоспособных реплик и узлов (отсутствие отклика на широковещательный запрос можно рассматривать как отказ соответствующей реплики).
Недостатки: дополнительная загрузка широковещательного канала, являющегося достаточно критичным ресурсом сети; - задержка при получении списка доступных реплик, связанная с необходи мостью широковещательного опроса по сети.
Вариант 3. Опрос реплик выполняется с использованием групповой адресации (Multicast Addressing), Групповой опрос аналогичен широковещательному за исключением того, что пакет получают не все машины подсети, а только подписавшиеся к определенной групповой рассылке.
Достоинства (по сравнению с широковещательным опросом): не используется широковещательный канал (запрос получает только установленный набор машин). Недостатки (по сравнению с широковещательным опросом): некоторые сетевые адаптеры не поддерживают режим групповой адреса ции. Если запрос на обслуживание поступает в систему в тот момент времени, когда система уже занята выполнением некоторой поступившей ранее задачи, то этот запрос помещается в очередь.
По количеству очередей, приходящихся на каждый сервис, возможны два варианта построения мигрирующих систем (рис. 2.5).
Вариант 1. Каждый сервис имеет единственную очередь. При поступлении очередного запроса на обслуживание данным сервисом он ставится в конец общей очереди. Основной сложностью работы с единственной очередью в полностью децентрализованной системе является хранение очереди. Возможны три способа: - очередь хранится независимо от реплик сервиса. Это может быть либо пассивная сущность (например, файл или база данных), либо активная сущность (например, приложение или сервис операционной системы); - копия очереди хранится в каждой реплике сервиса; - очередь хранится в одной из реплик сервиса. Эта реплика создается первой и не участвует в процедуре дерепликации (т.е. существует в течение всей жизни сервиса).
Первый и второй способы вносят элемент централизации в систему и поэтому в дальнейшем не рассматриваются. Недостатком этих способов является низкая надежность системы: при отказе узла, на котором находится очередь, все ожидающие обслуживания запросы будут потеряны. Приведенные далее достоинства и недостатки относятся к третьему способу. Достоинства: — высокая надежность за счет многократного резервирования очереди при ее хранении в каждой реплики сервиса (при отказе одной из реплик ни один находящий ся в очереди запрос не будет потерян); - отсутствует необходимость в перераспределении запросов при реплика ции/дере пликации сервиса.
Ограничения, накладываемые на модель системы
Переход системы из одного состояния в другое называется событием. Последовательность однородных событий, появляющихся в какие-то моменты времени, образует поток событий. Важной характеристикой потока событий является интенсивность X — среднее число событий, появляющееся в единицу времени.
Поток событий называется регулярным (детерминированным), если события в нем следуют через определенные заранее известные интервалы времени: 7/, 7 , ..., Т» ...,Т„. Если значения интервалов времени постоянны, то такой поток событий образует периодическую последовательность. Если значения интервалов времени являются значениями некоторой случайной величины, то такой поток называется потоком случайных событий.
Поток случайных событий называется стационарным, если его вероятностные характеристики не зависят от времени. Для стационарного потока интенсивность X есть величина постоянная.
Поток случайных событий называется потоком без последействия, если для любых непересекающихся временных интервалов xj и Т2 число событий, появляющихся на одном из них, не зависит от числа событий, появляющихся на другом, т.е. события в потоке являются независимыми.
Поток случайных событий называется ординарным, если события в нем появляются по одиночке, а не группами.
Поток случайных событий называется пуассоноеским, если число событий m в этом потоке, появляющихся на произвольном интервале т, распределено по закону Пуассона: т Р(т) = — е-\ (3.1) т\ где а - среднее число событий, появляющихся на интервале т. Пуассоновские потоки могут быть стационарными (к = const, а = Ат) и неста t +z ционарными (к = %{t) = var, а = произвольный момент времени). / Пуассоновский случайной поток называется простейшим, если он обладает свойствами стационарности, ординарности и отсутствием последействия.
Использование теории массового обслуживания (ТМО) накладывает ряд ограничений на моделируемые системы. В связи с этим, будем рассматривать модель мигрирующей системы, обладающей следующими параметрами: 1. мигрирующая система устанавливается в сети Н — {h\, h.2, ..., hn }, содержащей п узлов; связи между узлами образуют полный граф р = Н х Н, т.е. каждый узел сети связан со всеми остальными узлами; 2. мигрирующая система состоит из единственного сервиса s, т.е. множество сервисов S= {s }; 3. все реплики сервиса s являются активными; после миграции реплика является готовой к обслуживанию запросов; 4. в начальный момент времени / = 0 в системе не существует ни одной реплики; 5. узлы А,-, і = \,п сети Н могут выходить из строя; поток отказов узлов — простейший с интенсивностью и; 6. после отказа узла начинается его восстановление; поток восстановления узлов - простейший с интенсивностью ; 7. на каждом узле A(.,i = \,п сети Н может быть создана только одна реплика сервиса s; если на всех узлах сети уже существуют реплики сервиса s, то очередной запрос на репликацию получает отказ; 8. на вход системы поступают однотипные запросы rj, которые обслуживаются сервисом s; поток запросов - простейший с интенсивностью X; 9. поступивший в систему запрос rj может быть обслужен любой репликой Sj ,i-\tm сервиса s; поток обслуживания запросов - простейший с интенсивностью ц; 10. каждая реплика siti = \,m сервисам имеет очередь qt длиной /; 11. если сервис s имеет свободную (незанятую выполнением запроса) реплику sh то при поступлении в систему очередного запроса гу он направляется на обслуживание в реплику st; 12. если все реплики s;,i -\,т сервиса s заняты, то поступивший запрос Гу помещается в конец очереди реплики Si, имеющей наименьший индекс і и свободные места в очереди; 13. если очереди всех реплик 5,-, / = \,т сервиса s заполнены, то при поступлении очередного запроса rj выполняется процедура репликации (создается новая реплика st сервиса s); запрос rj помещается на обслуживание в реплику s , 14. если очереди всех реплик siti = \tm сервиса s заполнены, и процедура репликации невозможна (см. п. 7), то вновь поступивший запрос rj получает отказ; 15. если после завершения выполнения запроса /у реплика s,- оказывается пустой (не содержит запросов ни в своей очереди qif ни на обслуживании), то выполняется процедура дерепликации реплики s, (реплика Sj удаляется из системы); 16. если на узле hj выполняется реплика sk, и узел ht выходит из строя, то реплика Sk теряется (вместе с запросами, находящимися на обслуживании и в очереди qu реплики Sk).
Модуль хранения истории процесса моделирования
Система моделирования в процессе своего выполнения ведет файл истории (Log File), который содержит следующую информацию о работе приложения: - процедуру построения модели системы (перечень объектов мигрирующей системы, значения параметров каждого объекта, а также набор связей между отдельными объектами); - процесс моделирования (генерацию запросов пользователями, изменение состояния узлов сети, репликацию и дерепликацию сервисов, состояние очередей, результаты процедуры конвергенции, обслуживание запросов и др.); - информацию о возникающих ошибках (сохраняются данные как об ошибках, возникающих при создании модели и выполнении моделирования, так и о системных ошибках, например, связанных с невозможностью прочитать данные из файла или изменить значения ключа в реестре); - прочую служебную информацию (конфигурацию программного и аппаратного обеспечения, на котором выполняется система моделирования, действия пользователя, связанные с запуском, остановом и настройкой процесса моделирования и др.).
При моделировании различных аспектов поведения мигрирующих систем используются случайные значения, позволяющие придать вероятностный характер протекающим процессам. Примерами таких процессов в системе являются поступление запросов на обслуживание, отказ и восстановление узлов, передача информации по сети и другие.
В MSS используются следующие законы распределения дискретной случайной величины: - равномерный закон распределения; - экспоненциальный закон распределения.
Случайная величина имеет равномерное распределение на отрезке [а, Ь], если на этом отрезке плотность распределения вероятности случайной величины постоянна, т.е. если дифференциальная функция распределения j(x) имеет следующий вид [89]: О, при х а, /{х) = \\1{Ъ-а),пща х Ь, (4.1) О, при х Ь. Математическое ожидание и среднее квадратическое отклонение равномерно распределенной случайной величины соответственно определяются по следующим формулам: а + Ь Ъ-а ,, „ тк ,ст =—7=-. (4.2) х 2 х 2л/3 Генерация значений равномерно распределенной на отрезке [а, 6] случайной величины выполняется в два этапа [102]: 1. генерация случайной величины, равномерно распределенной на отрезке [0, 1] с использованием мультипликативного конгруэнтного метода. В качестве текущего значения ХІ случайного числа х выделяют остаток от деления произведения предыду щего случайного числах;./ и постоянного множителя и. на постоянное число т: X; ц, хм (mod т). (4.3) Для нормализации полученного значения (приведения к отрезку [0, 1]) необходимо х; разделить на постоянное число т\ 2, преобразование последовательности равномерно распределенных на отрез ке [0,1 ] значений xt случайного числа х к заданному распределению: Уі=Р-\хд, (4.4) где F x(x) — функция, обратная желаемой функции распределения F(y). Для получения последовательности значений уи равномерно распределенных на отрезке [а, Ь\, используется следующее соотношение: yt = a + {b - а)«д:,-. (4,5)
Случайная величина х имеет экспоненциальное (показательное) распределение, если ее функция плотности распределения вероятности задается следующим выражением: /(х)=Ь- ,прих 0, (46) [ 0, придти 0.
Выбор экспоненциального распределения в MSS обусловлен тем, что величина срока службы различных устройств и времени безотказной работы отдельных элементов этих устройств при выполнении определенных условий обычно подчиняется данному распределению.
Математическое ожидание и среднее квадрати ческое отклонение случайной величины, распределенной по экспоненциальному закону, определяются по следующим формулам: 11 ҐЛПЛ
Порядок генерации значений случайной величины при экспоненциальном законе распределения аналогичен равномерному закону с тем отличием, что для преобразования значений случайной величины используется следующее выражение: =-1п(х,.)/Х. (4.8)
Чтобы обеспечить повторяемость эксперимента при случайном характере протекающих процессов, в MSS предусмотрена возможность сохранения последовательностей значений случайных величин, сгенерированных в ходе работы системы моделирования. Эти последовательности могут быть поданы на вход системы при повторных экспериментах. Такой подход позволяет проводить серии экспериментов, оставляя неизменными параметры одних элементов мигрирующей системы и изменяя другие элементы.
Проектирование системы моделирования Основой для проектирования и программной реализации системы моделирования мигрирующих приложений (MSS) являются: - теоретико-множественно-событийная модель, задающая множество ключевых абстракций системы и наборы операций над этими абстракциями; - архитектура системы моделирования, определяющая совокупность реализуемых моделей в терминах наборов входных параметров и исследуемых характеристик системы.
В соответствии с теоретико-множественно-событийной моделью система представляет собой следующий набор ключевых объектов: - сеть (CNetwork), H(t) = { h\(f), h-fa), ..., hn{t\ р(ї) } - физическая среда вы полнения мигрирующей системы, состоящая из п узлов htг (/),/ = 1,п и связей между ними p$(t),ij = \%п\ - узел (CNode), ht(t)J = \,n — сетевое устройство, способное выполнять служебные (административные) и прикладные (пользовательские) задачи; - связь (Link), Pjj(t),i,j = Un —двунаправленное соединение, позволяющее передавать различного рода информацию между узлами h,(t) и hj(t); - сервис (CService), Sf(t)J = l,m - программный компонент, предоставляющий набор услуг внешним пользователям; - реплика (CRepHca), su(t),\ = l,k - копия сервиса st(t\i -\,т, расположенная в сети на некотором узле А (/), і = 1,я; - пользователь (CUser), щ(і)Іі = \,р — внешняя система, пользующаяся услугами сервиса Sj{t),) = \,т. В модели сделано допущение о том, что каждый пользователь «,. (t),i-\,p взаимодействует только с единственным сервисом s: (t)t j = 1,га; - запрос (CRequest), г (г) - набор исходных данных, которые создаются пользователем иДґ),і = 1,/ и определяют задачу, которую должен выполнить сервис sj(t),j = ltm;
