Содержание к диссертации
Введение
1. Распределенная вычислительная система .; ; 10
1.1 Функциональная Распределенная Вычислительная Система .10
1.2 Многомашинная.система 13
1.3 Классификация распределенных вычислительных систем 14
1.4 Требования к распределенным системам;.. 16
1.5 Проблемы проектирования РВС 17
1.6 Модели эффективности РВС 18
1.7 Постановка задачи. 21
1.8 Выводышо первой главе 23
2. Производительность толерантной распределенной вычислительной сети с переменным числом модулей 24
2.1 Постановка задачи 25
2.2 Система дифференциальных уравнений для? изучения переходного процесса поведения РВС . : 26
2.3 Система обыкновенных уравнений для изучения поведения РВС для? стационарного случая... 29
2311. Точное решение: : 29
2.3.2. Реализация схемы определения вероятностей 31
2.3:3. Числовой пример:.. 43
2.4 Приближенное решение 46
2.411.Система уравнений.. 46
2.4.2. Оценка эффективности приближенной модели 49
2.5 Выводы по второй главе 53
3. Анализ оценки производительности гетерокопиииои ТРВЄ при выполнении двухтипных задач 54
3.1 Развитие аналитической модели оценки индексов производительности гетерокопиииои толерантной распределенной вычислительной системы ГеТРВС
3.2 Модель времени выполнения двухтипных функциональных задач в зависимости от числа ВМ ГеТРВС 54
3.3 Конечно-разностное уравнение 56
3.4 Переходной режим функционирования 61
3.5 Стационарный режим функционирования 72
3.6 Оценка производительности - среднее число задач и среднее время выполнения задач 76
3.7 Экспериментальные результаты 78
3.8 Выводы по третьей главе 84
4. Имитационное моделирование распределенной вычислительной системы
4.1 Алгоритм моделирования 87
4.2 Распечатка программы 88
4.3 Анализ результатов моделирования 94
4.4 Выводы по четвертой главе 95
Заключение 96
Литератураq
- Классификация распределенных вычислительных систем
- Система дифференциальных уравнений для? изучения переходного процесса поведения РВС
- Конечно-разностное уравнение
- Распечатка программы
Классификация распределенных вычислительных систем
Условием функционирования распределенных вычислительных систем специального назначения является информационная безопасность, под которой понимается защищенность информации и поддерживающей инфраструктуры от случайных и преднамеренных воздействий, способных нанести ущерб владельцам или пользователям информации. Ущерб от нарушения информационной безопасности коммерческой информации может привести к крупным финансовым потерям и даже к полному закрытию компании. Трудно недооценить ущерб при разглашении информации, имеющей различный гриф секретности государственных органов.
Существует множество определений, связанных с рассматриваемой тематикой. Приведем некоторые характеризующие развитие понимания распределенной системы. В самом общем случае распределенная система — это связанная совокупность единиц обмена информацией. Более развитую модель называют Системой распределенной обработки -называется вычислительная структура, обладающая следующими характеристиками:
Функциональная Распределенная Вычислительная Система (ФРВС) — вычислительная структура, объединяющая в сеть микропроцессоры, интеллектуальные терминалы, персональные компьютеры и другие устройства. Все интеллектуальные элементы являются многофункциональными и могут выполнять различные программные модули.
Основным критерием распределения функций является частота использования соответствующей функции, которая гарантирует оптимальное размещение ее по отношению к источнику транзакций и высокую скорость выполнения.
Преимущества такого подхода очевидны - малое время отклика и низкая стоимость связи. Дополнительным преимуществом может считаться более высокая степень готовности, надежности и защищенности.
При проектировании и реализации ФРВС основными являются следующие три проблемы: . - выделение функций, остающихся централизованными и поэтому требующих распределения; - размещение распределенных функций; - создание мощной и гибкой однородной ФРВС с настраиваемыми функциями. РВС, используя многие компьютеры, каждый из которых выполняет часть полной задачи, достигает вычислительного результата намного быстрее, чем используя отдельный компьютер. В дополнение к более высокому уровню вычислительной мощности, РВС также позволяет многим пользователям взаимодействовать открыто. Различные формы распределенного вычисления учитывают различные уровни открытости.
Исходя из вышеприведенного определения, независимые (т.е. не обменивающиеся сообщениями) приложения в вычислительной сети не образуют распределенную систему. В централизованных вычислительных системах для совместной работы используется общая память, в то время как в распределенных вычислительных системах для этой цели можно использовать только обмен сообщениями.
Любая РВС также должна удовлетворять следующим требованиям пользователя: Функциональность: Данное требование означает, что распределенная система должна предоставлять больше возможностей, чем соответствующая централизованная вычислительная система.
Качество обслуживания: Распределенная система должна обеспечивать высокое качество обслуживания, которое является комплексной характеристикой и может рассматриваться состоящей из четырех составляющих: производительности, надежности, доступности и безопасности.
Многомашинная система[40] - это вычислительный комплекс, включающий в себя несколько компьютеров (каждый из которых работает под управлением собственной операционной системы),- а также программные и аппаратные средства связи компьютеров, которые обеспечивают работу всех компьютеров комплекса как единого целого. Эффективная работа любой многомашинной системы определяется двумя главными компонентами: - высокоскоростным»механизмом связи процессоров;. - системным программным обеспечением, предоставляющимшользователям-и программным приложениям прозрачный доступ к ресурсам всех компьютеров, входящих-в-многомашинную систему. Многомашинные системы обеспечивают высокую отказоустойчивость за счет дублирования- устройств и. производительность за счет организации параллельных вычислений, но» по сравнению с мультипроцессорными системами возможности параллельной обработки ограничены: эффективность резко снижается если.параллельно выполняемые задачи тесно связаны1 между собой по данным, так как связь между компьютерами многомашинной системы менее тесная, чем между процессорами в мультипроцессорных системах.
Территориальная распределенность в многомашинных системах не обеспечивается, а ограничивается длиной связи между процессорным блоком и дисковой подсистемой. 1.3 Классификация распределенных вычислительных систем
В соответствии с общей классификацией вычислительных систем [46,52,54], разработанной организацией ACM {Association for Computing Machinery) , PBC разделяются на следующие категории: В известной, классификации вычислительных систем; предложенной Флинном, системы- различаются по виду используемых ими потоков команд и данных. РВС в соответствии с этой классификацией попадают в- группу MIMD-систем (множественный» поток команд и множественный поток данных). Однако системы- этого класса значительно отличаются друг от друга с точки, зрения топологии, организации управления, типов, обрабатывающих узлов и методов размещения данных.
MIMD-система содержит много процессоров, которые (как правило, асинхронно) выполняют разные команды над разными данными. Подавляющее большинство современных высокопроизводительных ЭВМ. на верхнем уровне-иерархии-имеют архитектуру MIMD.
Для МІМО-систем в, настоящее время общепризнанна классификация, основанная на; используемых способах организации оперативной памяти в этих системах. По этой классификации, прежде всего, различают мультипроцессорные вычислительные системы (или-мультипроцессоры) или вычислительные-системы с разделяемой памятью и мультикомпьютерные вычислительные системы (мультикомпьютеры)! или вычислительные системы с распределенной памятью (multicomputers, distributed memory systems).
Система дифференциальных уравнений для? изучения переходного процесса поведения РВС
Состояние; (п, 0) дает последнее уравнение для определения вероятности Рп,о. Наконец; условие нормировки обеспечивает нахождение базовой; вероятности Pd. i,n-d+i и, тем самым, всех вероятностей:
В соответствии с приведенным алгоритмом решения системы линейных уравнений в работе разработана его программная реализация, приведенная в Приложении 2.
Оценка эффективности приближенной модели На основе полученных решений- выполнена оценка точности приближенной модели по отношению І к точной модели, властности, для среднего числамодулей, выполняющих функциональные задачи На рис. 2.4- 2.10 приведены результаты расчетов среднего числа модулей, выполняющих функциональные задачи, для точной и приближенной моделей с широкой вариацией значений параметров: интенсивностей работающих ВМ и контролирующих ВМ J , вероятности г не работоспособности ВМ, интенсивности восстановления работоспособности ВМ (п-Ч) при числе п=5 ВМ и d =3 копий одной задачи. Очевидно, что максимальная прогрешность приближенной моделей при изменении значений параметров в интервалах, n=5, d=3, Т(П-І-І) = О-4, Д, = 1, г=0.1, JU =(2,3,4,5,6,7,8), составляет около 4%. Скорость вычислений по приближенной модели увеличивается в О (п/2) раз по отношению к точной модели.
Погрешность, Выводы по второй главе 1. Предложена модель толерантной распределенной вычислительной сети (РВС), вычислительные модули (ВМ) которой могут находиться в одном из трех возможных состояниях: работоспособном - рабочем и работоспособном — контролируемом и не работоспособном (из-за функционального отказа или телекоммуникационной не доступности). При этом предполагается возможность восстановления работоспособности ВМ. 2. На основе предложенной модели выполнена оценка эффективности распределенной вычислительной сети с переменным числом ВМ. 3. Получены решения для не стационарного и стационарного случаев поведения РВС. Для не стационарного случая решение представлено в преобразованиях Лапласа, для не стационарного случая решение представлено в виде рекуррентной процедуры особенно эффективной для большого числа ВМ. 4. Предложена приближенная модель толерантной РВС с переменным числом ВМ. На основе полученных решений выполнена оценка точности приближенной модели по отношению к точной модели. Показана пригодность по точности приближенной модели. Скорость вычислений по приближенной модели увеличена в 0(п/2) раз по отношению к точной модели. 3. Анализ оценки производительности гетерокопийной ТРВС при выполнении двухтипных задач
В разделе развивается аналитическая модель оценки индексов производительности гетерокопийной толерантной распределенной вычислительной системы ГеТРВС с ограниченным числом вычислительных модулей, предназначенной для выполнения двухтипных задач при динамическом изменении их числа. Функционирование ВС состоит в выполнении двухтипных задач с разным числом копий для задач первого и второго типов. При этом, так как длявыполнения одной і -ой задачи требуется число d, копий, задача і —го (і ,= 1, 2) типа для своего выполнения требует d, вычислительных модулей (ВМ). Такая толерантная ВС в работе [12,13,18] названа гетерокопийной ТРВС.
Для оценки производительности [3,5,6] РВС используются различные индексы производительности. Мы получим решение для ТРВС, на основании которого определяются различные индексы производительности РВС, в частности, среднее число задач и среднее время выполнения задач.
При этом здесь решение получено для произвольных значений числа копий dt, і = 1, 2, в отличие от работы [26], где число копий задач ограничено значениями dj = 2nd2 = 3.
Пусть РВС содержит п ВМ, w 1. Выполненная задача і -го (Г= 1, 2) типа по завершению инициирует задачи первого типа с вектором вероятности г , где Г1 = 1Т10 + ТП + Г12 + Г1П + Г112 + Т122 J = 1
Каждая инициированная задача начинает выполняться при наличии свободного ВМ, иначе она становится в очередь к ВМ. Пусть время Тв выполнения вычислительным модулем ВМ задач і -го (г= 1, 2) типа является случайной величиной с экспоненциальной функцией распределения с параметром " і и 2 , соответственно. Имея ввиду трудность математического исследования нестационарного режима функционирования системы, с одной стороны, и интерес к характеристикам системы в условиях, когда система функционирует достаточно долго, с другой стороны; будем считать, что завершение выполняемой задачи при отсутствии в этот момент в системе других выполняемых задач обязательно приводит к инициированию одной и более задач.
Другое условие, которое, мы также примем: число существующих задач в системе не может быть больше максимального числа задач первого типа п+\ и максимального числа задач второго типа rc+Z .
Конечно-разностное уравнение
При разработке аналитической модели оценки производительности РВС с ограниченным числом вычислительных модулей, предназначенной для выполнения двухтипных задач с динамическим изменением их числа, на основе конечно — разностных уравнений получим систему дифференциальных и систему обыкновенных уравнений, соответственно, для переходного и стацонарного процесса поведения распределенной ВС. находятся в состоянии ожидания, ( )+ .(»- )+ \ k = l,hl,l = l,h2 _ вероятность того, что активны і задач первого типа и (n-i) задач второго типа, і dx+ j d2 n, a k (первого) и 1 (второго типа) задач находятся в состоянии ожидания.
Метод построения модели: в начале построения модели следует определить системные ограничения, а затем решить, какие элементы GPSS следует использовать для моделирования этих ограничений. В рассматриваемой вычислительной системе единственным ограничением является число задач в системе. Предположим, что, используя блок GENERATE (генерация первой задачи) с ограничением на число порождаемых им транзактов, в начале прогона в модель вводили бы необходимое число транзактов, используя блок ASSIGN (занесение в параметр 1 типа задачи ) , далее блок TEST, работающего в режиме отказа, находится задача первого типа или задача второго типа. Транзак задач первого типа попадает на блок SAVEVALUE (Z1) , иначе на блок SAVEVALUE (Z2) .Блок SAVEVALUE может быть использован как в режиме замещения величины, так и в режиме накопления и уменьшения. В режиме накопления предыдущее значение сохраняемой величины увеличивается на значение. Когда транзак задач (1-ого или 2-ого) типа входит в модель, он делает выборку из распределения времени работы модули , записывая полученные величины соответственно в первый и второй параметры. Затем в блоке «SELECT Е 3,1,3,0,F,MKA3» номер параметра с равным значением заносится в 3-й параметр.
Используя блок STORAGE моделируется выполнение задачи (1-ого или 2-ого) типов в канальном устройстве (разного числа копий для задач первого и второго типов)..
Обсуждение: Логика моделирования, в модели используется один блок TEST в режиме условной передачи, а другой блок TEST в режиме отказа. Заметим также, что оба сегмента модели взаимодействуют друг с другом с помощью сохраняемой величины блок SAVEVALUE. Модель существенно зависит от внешних условий. Двумя источниками случайностей являются данный запрос и приведенное время. Каждое соответствующее распределение представлено функцией , и у каждой функции в качестве аргумента свой датчик случайных чисел.
Когда транзакт входит в модель, он поступает в блок SAVEVALUE, в котором вычисляется величина переменной Z1 и Z2 (для задач 1-ого типа и 2-ого типа) и ZADT1 и ZADT2 (подсчет числа выполненных задач 1-ого типа и 2-ого типа). Затем транзакт переходит к блоку TERMINATE (блок 9), заканчивая моделирование. В программе можно установить необходимое количество задач, которые требуют решения, это можно сделать в блоке START .
Из полученной статистики следует, что при данных начальных условиях количество решенных задач ( на вариант n=10,dl=4,d2=3) - равно 311, из них: задач первого типа 152 , а задач второго типа 159 . Время моделирования процесса составило: Absolute Clock: 350.1541 .
Для сравнения с аналитическим методом моделирования подсчитано среднее число задач при ограниченном числе вычислительных блоков: С12=1.1254 , в то время как в аналитическом методе получено С12= 1,632 результаты, полученные аналитическим методом моделирования и моделирование в среде GPSS, практически близко совпадают. При А =1 //2 =1 ,оценке производительности системы с разным количеством вычислительных блоков получено в таблицах 4.1. Таблица 4.1 Количествомодули и числокопии типазадач среднее числозадач(моделированиев среде GPSS) среднее числозадач(моделированиев среде GPSS) n=9,dl=3,d2=2 1.4.015 2 n=10,dl=4,d2=3 1.1254 1,632 4.4 Выводы по четвертой главе 1. Предложена обобщенная имитационная модель параметрической ГеТРВС при выполнении двухтипных задач на основе системы моделирования GPSS. 2. Рассмотрены оценки производительности параметрической ГеТРВС и время выполнения моделирования. 3. Показана согласованность результатов имитационного и аналитического моделирования - среднее число задач и среднее время выполнения задач.
Распечатка программы
Анализ результатов эксперимента позволяет сделать вывод о достижении поставленной задачи для вычислительных систем с несколькими десятками вычислительных узлов. Предполагается, что при большом количестве узлов поведение модели будет аналогичным. При этом изменение адекватности по отношению к наиболее распространенным моделям было несущественным. Благодаря эффективности предложенного подхода его использование в системах планирования распределенных гетерогенных вычислительных систем является оправданным.
В работе[30] рассматривается проектирование распределенных систем реального времени (СРВ) разработчик проекта вынужден использовать эволюционные подход, когда исходная модель системы последовательно трансформируется так, чтобы ее конечный вариант соответствовал системе с приемлемыми характеристиками. В1 представление модели СРВ предложено осуществлять на языке структурного1 моделирования (языке SME), а математическими программные средства построения.и.эволюции модели названы-SML технологией. Существенным для SME технологии- является то, что в ней большая часть трансформаций осуществляется аналитическими методами, а имитационное моделирование используется на заключительной стадии эволюции модели. Решению одной из задач аналитического моделирования на начальном этапе эволюции модели СРВ"посвящена данная работа. Задача заключается в том, чтобы для представленного варианта модели оценить способность соответствующей СРВ - выполнить заданную совокупность прикладных функций (ПФ) по управлению объектом с соблюдением условий динамики его функционирования.
В работе[37] рассматривается изложены концептуальные основы построения распределенных вычислительных Систем(ВС) с программируемой структурой . Описаны модели функционирования ВС и континуальный метод расчета показателей их эффективности . Приведены результаты по анализу и синтезу структур распределенных ВС .Предложены стратегии обеспечения стохастический оптимального функционирования распределенных ВС в режимах параллельного мультипрограммирования . Показано, что рассматриваемая концепция позволяет создавать технико - экономически эффективные и живучие супер ВС.
Современные супер ВС (пространственно сосредоточенные и распределенные ) полностью основываются на модели коллектива вычислителей . Для них характерно, в частности, следующее : больше масштабность (массовый параллелизм) , масщтабируемость и стохастический характер ресурсов . Анализ и оптимизация функционирования супер ВС относятся к числу сложный проблем, которые не могут быть решены при помощи традиционного аппарата теории массового обслуживания и методов математического программирования .
В работе[29] предлагается математическая модель для расчета показателей осуществимости решения задач потока на распределенных вычислительных системах (ВС) . При анализе эффективности функционирования вычислительных системах (ВС), как сосредоточенных, так и распределенных, используются показатели осуществимости решения задач . В зависимости от сложности задач и характера их поступления выделяют следующие режимы работы ВС: решение сложной задачи , обслуживание потока задач, обработка задач набора.
Построенная модель функционирования ВС в режиме обработки задач пакета позволила получить: Аналитические выражения для вероятности того , что в определенный момент времени пакет состоит из нерешенных задач . Оценки для среднего размера пакета . Формулы для расчета математического ожидания и дисперсии числа задач в пакете. В работе [5,6]рассматривается метод оценки эффективности ГоТРВС (с одинаковым числом копий для задач первого и второго типов) при выполнении двухтипных задач на основе развития, разработанной в интегрированной модели TPBG, выполняющей функциональные однотипные задачи.
Разработка модернизированной:: интегрированной модели предполагает адаптацию модели числа виртуальных. ВМ и разработку новой модели времени выполнения функциональных задач в зависимости от числа виртуальных ВМ;.
Первая модель учитывает, деградацию РВЄ с течением времени и метод обеспечения ее толерантности. Вторая модель рассматривает РВС как систему с динамическим изменением числа задач, время выполнения которых определяется в зависимости от числа; ВМ; Выполнение задачи ВМ возможно при выполнении двух обстоятельств: 1) готовности задачи, к выполнению по получению входные данных, и 2) наличии свободного ресурса -вычислительного модуля (ВМ).
. В работе [24] рассматривается построение модели; возвратного восстановления с учетом: возможности программных распространяющихся сбоев и распределенного характера- системы мониторинга, невозможности определения истинных причин сбоя, максимальной;прозрачности, системы, восстановления для разработчика и конечного пользователям Для практической реализации построенной модели и исследования особенностей ее поведения был выбран класс многоагентных систем.
В данной работе основное внимание уделено определению функционирования и разработке моделей эффективности ТРВС с переменным числом ВМ и с переменным числом функциональных и служебных задач.
Переменное число ВМ обусловлено тем, что ВМ может находиться в одном из трех возможных состояниях: не работоспособном, работоспособном - рабочем и работоспособном - контролируемом. Так же предполагается возможность восстановления работоспособности ВМ. Неработоспособное состояние ВМ может быть обусловлено невозможностью выполнения функциональных задач или телекоммуникационной его недоступностью. Периоды временной телекоммуникационной недоступности модулей являются естественными для мобильных ТРВС, в частности, для ТРВС, образующих космические (спутниковые) группировки. В свою очередь, в работоспособном состоянии ВМ может выполнять рабочие и служебные задачи. Выполнение служебных задач должно быть связано с обеспечением толерантности вычислительных систем.
Важным обстоятельством функционирования ТРВС реального времени является учет того, что выполнение задач возможно при наступлении двух обстоятельств: готовности задачи к выполнению и наличии свободного ресурса. Задачи могут отличаться по числу инициируемых задач, по времени их выполнения, так и по числу порождаемых копий, необходимых для обеспечения свойства толерантности за счет N- версионного программирования.
На жизненном цикле толерантной распределенной вычислительной сети, РВС, ее вычислительные модули, ВМ, могут находиться в работоспособном и не работоспособном состоянии. Не работоспособное состояние- ВМ может быть обусловлено не возможностью выполнения функциональных задач или телекоммуникационной его недоступностью. Периоды временной телекоммуникационной недоступности модулей являются- естественными для мобильных РВС, в частности, для РВС, образующих космические (спутниковые) группировки.
В свою очередь, в работоспособном состоянии ВМ может выполнять рабочие (функциональные) и некоторые служебные задачи. Выполнение служебных задач может быть связано с внутри сетевым обменом или с обеспечением толерантности РВС. Для обеспечения, толерантности РВС может быть использован функциональный подход, при котором контроль состояния вычислительных модулей реализуется программными средствами, используя диагностирующее тестирование или d - копийное выполнение задач.
