Задания к практическим и лабораторным работам. Учебнометодическое пособие к практическим занятиям по дисциплине Математические модели информационных процессов и систем г р
 Скачать 1.72 Mb.
|
|
1 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДЕЛЕЙ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ Учебно-методическое пособие к практическим занятиям по дисциплине « Математические модели информационных процессов и систем» г р у б р е т е П - т к н а С 2 0 2 0 3 Цель практических занятий по дисциплине « Математические модели информационных процессов и систем» состоит в обеспечении углубленного изучения лекционного материала. В ходе этих работ студенты должны изучить основные архитектуры распределенных систем (РС), освоить способы программной реализации аналитических, аналитико-численных и имитационных моделей вычислительных сетей РС и провести научные эксперименты на этих моделях. Практические занятия № 1 и 2 ОБЗОР СУЩЕСТВУЮЩИХ РС В МИРЕ И В РОССИЙСКОЙ ФЕДЕРАЦИИ Цель работы: проведение анализа и изучение распределенных систем по следующим характеристикам: производитель, история развития, применение, архитектура, технические и функциональные характеристики . Программа работы 1.Изучение теоретического материала по литературным источникам и электронным ресурсам. 2. Подготовка реферата. Пояснения к работе 1.1. Введение Информационная система (ИС) — это основной объект прикладной информатики. Кроме информационных систем, этими объектами также являются разработчики и пользователи, обеспечива- ющие создание, функционирование и сопровождение ИС. К основным функциям информационной системы относятся: - ввод данных (сбор информации, прием ее из других ИС); - обработка данных (передача сообщений по линиям связи (ЛС); - хранение и поиск информации на рабочих станциях либо в автоматизированных рабочих местах (АРМ), а также на серверах баз данных (БД); 4 -вывод данных (формирование различных отчетов для пользователей; - передача информации в другие ИС). В литературе существует различные определения "архитектуры" информационных систем. Например, как архитектура – это организационная структура системы; архитектура – концепция, определяющая модель, структуру, выполняемые функции и взаимосвязь компонентов информационной системы; архитектура– это базовая организация системы, воплощенная в ее компонентах, в их отношениях между собой и с окружением, а также принципы, определяющие проектирование и развитие системы т.д. В рамках этих понятий была разработана классификация ИС по архитектуре. Она выглядит следующим образом: - централизованная архитектура; - архитектура "файл-сервер"; - архитектура "клиент-сервер"; - архитектура Web-приложений; - архитектура распределенных систем; - сервис-ориентированная архитектура (СОА); - архитектура “облачных” систем и сервисов. В архитектуре любой конкретной ИС часто можно найти сочетание нескольких выше приведенных общих архитектурных решений. 1.2.Архитектуры распределенных информационных систем Данный тип информационных систем (ИС) является достаточно сложным с организационной точки зрения [1]. Основная особенность распределенной системы заключается в том, чтобы хранить одинаковые локальные копии баз данных на всех автоматизированных рабочих местах (АРМ) системы. Схематически такую архитектуру можно представить следующим образом (рис.1.1)[2]. 5 Рис.1.1. Архитектура распределенных систем Практически весь основной объем данных, необходимый для функционирования предприятия, может быть размещен на одном мощном персональном компьютере. Поток исправлений и дополнений, генерируемый на этом компьютере, ничтожно мал по сравнению с общим объемом данных, используемым в его работе. Однако применение одного компьютера не может обеспечить многопользовательский режим системы. Поэтому, если хранить непрерывно используемые данные на разных компьютерах (узлах), и организовать обмен между ними исправлениями и дополнениями к хранящимся данным, то суммарный передаваемый трафик можно значительно сократить. Это позволяет: понизить требования к каналам связи между компьютерами (узлами) и чаще использовать для связи отдельных элементов неустойчивую связь типа Интернета, мобильную связь, коммерческие спутниковые каналы; обеспечить доступную стоимость эксплуатации такой связи. Конечно, реализация такой системы не элементарна, и требует решения ряда проблем, одна из которых – это своевременная синхронизация данных. Каждый узел независим, содержит только ту информацию, с которой должен работать, а актуальность данных во всей системе обеспечивается благодаря непрерывному обмену сообщениями с другими узлами. Еще одним из преимуществ такой схемы эксплуатации и архитектуры системы, является обеспечение возможности персональной ответственности за сохранность информации, так как данные, доступные на конкретном рабочем месте, находятся только на этом компьютере. Такая архитектура системы также позволяет организовать распределенные вычисления между клиентскими 6 машинами. Например, расчет какой-либо задачи, требующей больших вычислений, можно распределить между соседними АРМами благодаря тому, что они, как правило, обладают одной информацией в своих БД и, таким образом, добиться максимальной производительности системы. Распределенные системы с репликацией Данными между клиентскими приложениями и сервером баз данных (БД), передаются с помощью репликаций– передачи фрагментов обновляемых данных (рис.1.2) [2]. Рис.1.2. Архитектура распределенных систем с репликацией Репликация может быть синхронной или асинхронной. В случае синхронной репликации, если данная реплика обновляется, все другие реплики того же фрагмента данных также должны быть обновлены в одной и той же транзакции. Фактически это означает, что существует лишь одна версия данных. Синхронная репликация имеет тот недостаток, что она создаёт дополнительную нагрузку на сеть при выполнении всех транзакций в момент пиковых ситуаций в линиях связи (ЛС). При асинхронной репликации обновление одной реплики распространяется на другие узлы спустя некоторое время, а не в той же транзакции. Таким образом, при асинхронной репликации вводится задержка или время ожидания, в течение которого отдельные реплики могут быть фактически неидентичными. В большинстве случаев асинхронная репликация реализуется посредством чтения журнала транзакций или постоянной очереди тех обновлений, которые подлежат распространению. Преимущество асинхронной репликации состоит в том, что она реализуется при не сильно загруженном трафике. 7 К недостаткам этой схемы относится то, что данные в узле могут оказаться неактуальными с точки зрения пользователя в определенные моменты времени. Распределенные системы с элементами удаленного исполнения Существуют определенные особенности функционирования ИС, которые невозможно качественно реализовать на обычной распределенной системе репликативного типа. К ним можно отнести: - использование данных из баз данных, которые хранятся на удаленном сервере (узле); - использование данных из баз данных, хранящихся частично на разных серверах (узлах); - использование обособленного функционала, размещенного на выделенном сервере (узле). У каждой из описанных особенностей используется общий принцип: программа клиентского узла обращается к выделенному (удаленному) серверному узлу непосредственно или обращается к локальной базе, которая обеспечивает обращение к удаленному серверу (рис.1.3)[2]. Рис. 1.3. Архитектура распределенных систем с удаленным исполнением Задания по практическому занятию №1 Подготовить реферат по распределенным системам, существующим в Российской Федерации. Задания по практическому занятию №2 Подготовить реферат по распределенным системам, существующим во всем мире. 8 Практические занятия № 3,4,5 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ОТЛАДКА АНАЛИТИКО-ЧИСЛЕННЫХ МОДЕЛЕЙ РС ДЛЯ КАНАЛОВ С НИЗКИМ , СРЕДНИМ И ВЫСОКИМ УРОВНЯМИ СЕТЕВОГО ТРАФИКА Цель работы: изучение практических вопросов программной реализации аналитико-численных моделей РС на языках высокого уровня (ЯВУ) и проведение научных экспериментов на данных моделях . Программа работы 1. Разработка программы аналитико-численной модели РС на ЯВУ для каналов с низким и средним уровнями сетевого трафика. 2. Проведение научных экспериментов на данных программах- моделях. Пояснения к работе Рассмотрим построение и структуру программ, обеспечивающих реализацию моделей ВС распределенных систем со средним и низким уровнями сетевого трафика. Эти программы реализованы на языке ПАСКАЛЬ или Delphi, имеют модульную структуру и включают следующие унифицированные сегменты: - задания и ввода исходных параметров, промежуточных переменных; - формирования первоначальной матрицы пространства состояний источников; прореживания матрицы состояний с учетом ограничений; определения вектора начального приближения стационарного распределения вероятностей; - реализации итерационного метода определения вектора СРВ; - расчета и вывода характеристик сети либо системы массового обслуживания. Модель вычислительной сети РС для среднего уровня сетевого трафика имеет такой отличительный модуль, как сегмент 9 формирования инфинитезимальной матрицы, а модель вычислительной сети распределенной системы для низкого уровня сетевого трафика дополнительно к выше указанным сегментам включает: сегменты формирования матрицы фаз обслуживания и объединенной матрицы состояний источников с учетом фаз, сегмент формирования стохастической матрицы переходных вероятностей. Сегмент задания и ввода исходных параметров обеспечивает настройку моделей в диалоговом режиме на различные значения параметров ВС. Этот сегмент позволяет быстро и эффективно осуществлять подготовку программ в процессе машинных экспериментов на уровне выполнения загрузочных модулей. Сегмент формирования первоначальной матрицы пространства состояний реализует алгоритм генерации десятичных кодов в диапазоне (0,….,0; 0,….,0; 0,….,0; 0,….,0; 0,….,0), (0,….,0; 0,….,0; 0,….,0; 0,….,1),…., (0,….,2; 1,….,0; 2,….,1; 2,….,1;), ,…., (𝑊 𝑤𝑛𝑒ℎ 1 ,…., 𝑊 𝑤𝑛𝑒ℎ 𝑚 ; 𝑊 𝑤𝑛𝑒ℎ 1 ,…., 𝑊 𝑤𝑛𝑒ℎ 𝑚 ; 𝑊 𝑤𝑛𝑒ℎ 𝑙1 ,…,𝑊 𝑤𝑛𝑒ℎ 𝑚 ; 𝑊 𝑤𝑛𝑒ℎ 1 ,….,𝑊 𝑤𝑛𝑒ℎ 𝑚 ), предназначенных для идентификации различных состояний источников. Этот алгоритм является универсальным и может быть использован в любых стохастических моделях, формирующих пространство состояний. Программное описание этого сегмента приведено ниже. Первоначальная матрица пространства состояний поддерживается массивом : NM AB MK for I:=1 to AB do begin D:=I-1; for Z:=1 to MK do begin L:=0; MKZ:=M*K-Z; W11:=W1+1; G1:SP:=vstep(W11, MKZ); ST:=round(SP); D1:=D-ST*L; If D1=0 then begin D:=D1; NM[I][Z]:=L; goto G2; end else 10 if D1>=0 then begin L:=L+1; D2:=D1; goto G1; end else begin NM[I][Z]:=L-1; D:=D2; end; G2:end; end; Сегмент прореживания матрицы пространства состояний выполняет функцию удаления из первоначальной матрицы тех состояний, которые недопустимы либо отсутствуют в связи с определенными ограничениями. Для рассматриваемых моделей эти ограничения описаны в лабораторных работах № 2,4. Выход из итерационного алгоритма осуществляется по первой норме ошибки max |X (i) -X (i-1) | (i – номер итерации), которая не должна превышать бесконечно малую заданную величину . Метод простой итерации обеспечивает быструю сходимость за конечное число итераций. Сегмент расчета и вывода характеристик по формулам, описанным в лабораторных работах № 2,4, определяет: закон распределения сообщений в источнике, среднюю интенсивность источника, среднее число сообщений в системе (сети) массового обслуживания, среднее время ответа для каждого источника . Ниже представлен сегмент прореживания матрицы состояний для модели ВС со средним сетевым трафиком. Результирующая матрица состояний находится в массиве MS KK M K : forI:=1 toABdo forJ:=1 toM*Kdo MS[I][J]:=0; KK:=0; for I:=1 to AB do begin KK1:=0; II:=1; while II<=M do begin SI:=0; 11 IK:=II; while IK<=(M*K) do begin SI:=SI+NM[I][K]; IK:=IK+M; end; if SI=W1 then KK1:=KK1+1; II:=II+1; end; if KK1=M then begin KK:=KK+1; for IJ:=1 to (M*K) do MS[KK][IJ]:=NM[I][IJ]; end; end; Сегмент определения вектора начального приближения стационарного распределения вероятностей (СРВ) вычисляет вектор 0 0 0 0 1 ,..., , i N X X X X (N – длина вектора СРВ) по формуле 0 1 / N i ij i X p N , где ij p - элемент инфинитезимальной матрицы либо матрицы переходных вероятностей ij p , поддерживаемой массивом [ ][ ] RR N N : for J:=1 to N do X[J]:=0,0; for J:=1 to N do for I:=1 to N do X[J]:=X[J]+RR[I,J]; for J:=1 to N do X[J]:=X[J]/N; Следующий унифицированный сегмент реализует метод простой итерации над матрицей ij p для получения вектора СРВ, описываемого массивом X[N]: for ITER:=1 to N do begin BIG:=0.0; for J:=1 to N do begin SS:=0; for I:=1 to N do 12 SS:=SS+X[I]*RR[I][J]; if ABS(SS-X[J])>BIG then BIG:=ABS(SS-X[J]); X[J]:=SS; end; SUM:=0; for I:=1 to N do SUM:=SUM+X[I]; for I:=1 to N do X[I]:=X[I]/SUM; if BIG Основными сегментами в рассматриваемых моделях являются сегменты формирования инфинитезимальной матрицы и стохастической матрицы переходных вероятностей. Эти сегменты реализуют описанные в лабораторных работах № 1, 3 методы экспоненциальных сетей и вложенных цепей Маркова[3].На их выходе формируется матрица ij p , поддерживаемая массивом [ ][ ] RR N N . В процессе построения инфинитезимальной матрицы используются следующие процедуры: ga1 – вычисление интенсивности обработки прямых сообщений; ka1 – вычисление интенсивности передачи прямых сообщений по линии связи; int3 – вычисление интенсивности передачи ответных сообщений по линии связи; ca1 – вычисление интенсивности обслуживания сообщений; vstep – функция возведения в степень. Для формирования матрицы переходных вероятностей подключается встроенная функция возведения в степень STEP и процедура вычисления факториала VAK. 13 Задания по практическому занятию №3 1. Построить программную модель РС с низким уровнем сетевого трафика и радиальной структурой ВС. 2. Построить программную модель РС с низким уровнем сетевого трафика и кольцевой структурой ВС. 3. Построить программную модель РС с низким уровнем сетевого трафика и моноканальной структурой ВС. Задания по практическому занятию №4 1. Построить программную модель РС со средним уровнем сетевого трафика и радиальной структурой ВС. 2. Построить программную модель РС со средним уровнем сетевого трафика и кольцевой структурой ВС. 3. Построить программную модель РС со средним уровнем сетевого трафика и моноканальной структурой ВС. Задания по практическому занятию №5 1. Построить программную модель РС с высоким уровнем сетевого трафика и радиальной структурой ВС. 2. Построить программную модель РС с высоким уровнем сетевого трафика и кольцевой структурой ВС. 3. Построить программную модель РС с высоким уровнем сетевого трафика и моноканальной структурой ВС. 14 Практическое занятие № 6 АНАЛИЗ ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЕТИ РС НА БАЗЕ АНАЛИТИЧЕСКИХ И ИМИТАЦИОННЫХ МОДЕЛЕЙ Цель работы: анализ функционирования вычислительной сети РС на базе сравнительного эксперимента над их аналитическими и имитационными моделями. Программа работы 1. Изучение теоретического материала. 2. Разработка имитационных моделей. 3. Проведение сравнительного эксперимента аналитической и имитационной моделей вычислительной сети РС Пояснения к работе 6.1. Структуры вычислительной сети распределенных систем Простейшие структуры ВС – нульмерные, одномерные и двумерные [4]. Увеличение размерности структуры повышает структурную надёжность ВС. В самом деле, двумерные структуры предоставляют каждому вычислителю непосредственную связь с четырьмя соседними. В качестве примеров двумерных структур может служить «решетка» (точнее 2D-решетка) и тop (2D-тор). Следовательно, в системах с двумерной структурой при отказах некоторых узлов (вычислителей) и (или) связей между ними сохраняется возможность организации связных подмножеств исправных узлов. В n-мерных структурах каждый вычислитель связан с 2n соседними вычислителями. Ясно, что имеются технико- экономические и технологические ограничения в наращивании размерности структуры ВС. 15 Гиперкубы или структуры в виде булевых n-мерных кубов нашли широкое применение при построении современных высокопроизводительных распределенных ВС. Гиперкуб, по определению, это однородный граф, для которого справедливо |