Содержание к диссертации
Введение
Глава 1. Проблемы моделирования и алгоритмизации управления системами обработки информации в условиях изменяющейся нагрузки . 11
1.1 Архитектура систем обработки информации и проблематика распределения их ресурса памяти . 11
1.2 Анализ данных и нестационарных нагрузок модульных систем обработки информации. 21
1.3 Сравнительный анализ существующих технологий распределения и балансировки нестационарной нагрузки. 27
1.4 Выводы по главе 1. 38
Глава 2. Динамическое управление качеством обслуживания программного модуля на основе гистерезисного метода с порогами коэффициента вариации 39
2.1 Модель потока входных данных программного модуля модульной системы обработки информации. 39
2.2 Построение и анализ математической модели процесса функционирования программного модуля в условиях изменяющейся нагрузки . 49
2.3 Обобщение модели для n-канальной системы и расчет основных характеристик и показателей разработанной модели. 56
2.4 Выводы по главе 2 64
Глава 3 Алгоритмизация динамического управления качеством обслуживания модульной системы обработки информации на основе двухуровневой схемы управления ресурсом памяти и гистерезисным методом с двумя типами порогов . 66
3.1 Механизм межмодульного распределения ресурса памяти в модульной системе обработки информации. 66
3.2 Организация функционирования МСОИ с использованием двухуровневой схемы межмодульного распределения ресурса памяти. 75
3.3 Особенности проектирования и алгоритмы работы глобального и локального менеджеров . 78
3.4 Оценка вычислительной сложности разработанного алгоритма. 88
3.5 Выводы по главе 3. 92
Глава 4 Экспериментальное исследование эффективности модели и комплекса алгоритмов управления качеством обслуживания модульной системы обработки информации . 94
4.1 Проектирование структуры имитационной модели модульной системы обработки информации 94
4.2 Элементы программной реализации механизма межмодульного распределения ресурса памяти на основе менеджеров . 98
4.3 Проверка адекватности разработанной имитационной модели. 110
4.4 Результаты экспериментального исследования распределения ресурса памяти системы. 114
4.5 Выводы по главе 4. 122
Заключение 123
Список терминов, сокращений и условных обозначений 126
Список использованных источников 130
Приложение 1 140
Приложение 2 141
Приложение 3 144
Приложение 4 149
Приложение 5 154
Приложение 6 159
Приложение 7 167
Приложение 8 171
Приложение 9 172
Приложение 10 173
Приложение 11 174
- Архитектура систем обработки информации и проблематика распределения их ресурса памяти
- Построение и анализ математической модели процесса функционирования программного модуля в условиях изменяющейся нагрузки
- Особенности проектирования и алгоритмы работы глобального и локального менеджеров
- Элементы программной реализации механизма межмодульного распределения ресурса памяти на основе менеджеров
Введение к работе
Актуальность темы
Увеличение пропускной способности современных транспортных инфраструктур, а также совершенствование и рост популярности сетевых сервисов, ориентированных на функционирование в режиме реального времени, повышают требования к системам обработки информации (СОИ), ориентированным на работу с подобными сервисами.
п подпотоков
Результаты обработки
подпотока 1
Результаты
обработки
подпотока 2
Результаты
обработки
подпотока n
Рисунок 1 - Обобщенная схема системы обработки информации
Этап разделения входного потока в таких системах предшествует этапу обработки подпотоков и является обязательным, поскольку разделенные подпотоки могут обрабатываться независимо. Обобщенная схема организации системы обработки информации представлена на рисунке 1.
В настоящее время технология виртуализации позволяет реализовать концепцию модульных СОИ, в которых узел обработки подпотока ассоциируется с программным модулем (ПМ), выполняющимся на этом узле, а очереди заявок на обработку размещаются в буферной памяти (БП) программного модуля, реализуемой в едином пространстве памяти узла обработки подпотока.
Архитектура модульных СОИ (МСОИ) широко используется в системах, решающих задачи оперативно-розыскных мероприятий, использование которых, обязывает операторов хранить голосовой и текстовый трафики абонентов. Особенностью подобных систем является функционирование в круглосуточном режиме, причем интенсивность обрабатываемых потоков информации зависит от таких факторов, как время суток, день недели, а также от инцидентов, происходящих в мировом/региональном масштабе. Увеличение интенсивности обрабатываемого ПМ подпотока до уровня, превышающего его производительность, является причиной скачкообразного увеличения размера очереди в БП ПМ, что можно представить как перегрузку ПМ (или узла обработки подпотока в целом), приводящую к потере обрабатываемой информации и, как следствие, снижению качества обслуживания МСОИ.
Анализ работ отечественных и зарубежных ученых показывает, что поставленная задача решается путем увеличения ресурса производительности на «проблемном» узле системы за счет родственных узлов или дополнительного разложения потока, что позволяет обозначить научную задачу - разработка модели и алгоритма управления качеством обслуживания системы обработки информации, позволяющих для существующих систем снизить потери обрабатываемой информации при скачкообразных возрастаниях интенсивности потока данных, без необходимости изменения состава и размещения их элементов, что определяет актуальность диссертационного исследования.
Цель и задачи исследования. Цель работы заключается в повышении качества функционирования системы обработки информации на основе разработки модели и алгоритмов управления ресурсом памяти системы в условиях изменяющейся нагрузки на программные модули системы обработки информации. Для достижения цели в диссертационной работе необходимо решить следующие задачи:
исследовать существующие модели и алгоритмы управления качеством обслуживания в системах обработки информации при скачкообразном возрастании интенсивности обслуживаемых ими подпотоков на предмет снижения потерь обрабатываемой информации;
разработать модель процесса функционирования программного модуля модульной системы обработки информации с целью определения влияния скачкообразного возрастания интенсивности обрабатываемого подпотока на его производительность;
осуществить алгоритмизацию процесса управления качеством обслуживания программного модуля, использующую механизмы управления общим ресурсом памяти модульной системы обработки информации;
разработать комплекс алгоритмов управления буферной памятью программных модулей, обеспечивающих снижение потерь обрабатываемой информации за счет применения решающей функции предложенной модели;
разработать имитационную модель процесса обработки заявок в модульной системе обработки информации для выполнения численных экспериментов, подтверждающих работоспособность предлагаемых моделей и алгоритма;
провести численные эксперименты и осуществить анализ эффективности использования предложенных моделей и алгоритмов.
Методы исследования. Научной основой для решения поставленной задачи являются: теория и методы математического моделирования, оптимизации, теория вероятностей и математической статистики, теория эффективности целенаправленных процессов, технологии объектно-ориентированного программирования, теория вычислительных систем и параллельных вычислений.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.01: п.3. «Разработка критериев и моделей описания и оценки эффективности решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», п. 5. «Разработка специального математиче-
ского и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации».
Научная новизна. В работе получены следующие результаты, отличающиеся научной новизной:
-
Разработана модель управления качеством обслуживания в системах обработки информации на основе моделирования нестационарного входного под-потока данных программного модуля аппроксимацией интервалов времени между смежными заявками гиперэкспоненциальным распределением второго порядка, позволяющая получить значение коэффициента вариации временных интервалов для использования в качестве дополнительного критерия принятия решения в ги-стерезисном методе реконфигурации ресурса памяти системы.
-
Разработана модель процесса обслуживания программным модулем подпотока данных с интервалами времени между заявками распределенными по гиперэкспоненциальному закону высших порядков на основе выведенной системы дифференциальных уравнений Чемпена-Колмогорова решение которой позволяет определять вероятности состояний системы обработки информации.
-
Предложена двухуровневая схема мониторинга программных модулей, основанная на множестве локальных менеджеров и глобального менеджера, обеспечивающие наблюдение за состоянием ресурса памяти элементов системы обработки информации и параметрами обрабатываемых подпотоков данных.
-
Разработан комплекс алгоритмов планирования перераспределения ресурса памяти программных модулей, основанный на методе управления страничной виртуальной памятью, отличающийся учетом фиксированного размера обрабатываемых пакетов данных и размещением буферов памяти в едином адресном пространстве.
-
Разработана имитационная модель процесса обслуживания подпотоков данных, обеспечивающая получение граничных значений их параметров, для случаев скачкообразного возрастания интенсивности.
Практическая значимость. Программная реализация компонентов системы управления буферами программных модулей системы обработки информации обеспечивает оперативное принятие превентивных мер по снижению потерь обрабатываемой информации в условиях изменяющейся нагрузки. Разработанные в диссертации модели и алгоритмы могут быть использованы для создания программного обеспечения, позволяющего повысить качество обслуживания в проектируемых, а также существующих системах обработки информации. На элементы программных средств получены два свидетельства о государственной регистрации и один патент на изобретение.
Реализация и внедрение результатов работы. Теоретические и практические результаты исследований, реализованные в виде специального программного модуля мониторинга и управления состоянием аппаратно-программным комплексом «Вектор-УС», получили внедрение в ООО «ТехАргос СпецСистемы» (Москва).
Апробация результатов диссертационного исследования. Результаты
диссертационного исследования обсуждались на следующих научно-технических
конференциях: XXI-й Международной открытой научно-практической
конференции «Modern informatization problems in economics and safety» (США, 2016); II-й Всероссийской военно-научной конференции «Актуальные проблемы подготовки военных специалистов в области отбора и обработки информации техническими средствами» (Санкт-Петербург, 2016); Х-й Всероссийской межведомственной научной конференции «Актуальные направления развития систем охраны, специальной связи и информации для нужд государственного управления» (Орёл, 2017); XXII-й Международной открытой научно-практической конференции «Modern informatization problems in simulation and social technologies» (США, 2017); XX научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» (Москва, 2017).
Публикации. По теме диссертационного исследования опубликовано 13 печатных работах (из них три научные статьи опубликованы в трех рецензируемых журналах, рекомендованных ВАК при Минобрнауки России), в том числе один патент на изобретение и два свидетельства Роспатента РФ о государственной регистрации программы для ЭВМ.
В работах, опубликованных в соавторстве, и приведенных в автореферате, личный вклад соискателя состоит: в [1, 9, 12] – модели, использующие в качестве базиса распределение фазового типа для описания ситуаций «пачечности» трафика; [4,5] – комплекс алгоритмов управления качеством обслуживания модульной системы обработки информации; [6, 11] – двухуровневая схема управления ресурсом буферной памяти программных модулей; [10, 13] – имитационная модель процесса обработки заявок в модульной системе обработки информации.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и 11 приложений. Работа изложена на 174 страницах машинописного текста, включая 53 рисунка, 2 таблицы и список литературы из 102 наименования.
Архитектура систем обработки информации и проблематика распределения их ресурса памяти
История развития вычислительных устройств показывает динамику усложнения структур таких систем. Начиная с 90-ых годов и до 2000-ых, наблюдается валовое повышения тактовой частоты процессора вычислительных узлов входящих в состав таких систем, что спровоцировано увеличением скорости передаваемых данных необходимых для обработки внутри них. Бытует мнение [73], что дальнейший рост частоты связан с проблемой тепловыделения, и новейшие виды процессоров и соответствующие им сложные системы охлаждения дают пророст в скорости вычислений, однако экономические затраты на такие вычислители, могут быть нецелесообразны для всех задач.
В зависимости от доступных средств и трудоемкости поставленных перед вычислителями задач, инженерами могут использоваться различные подходы к созданию архитектуры МСОИ. Одним из таких вариантов, является использование параллельных систем обработки информации для работы с сетевыми сервисами, ориентированных на функционирование в режиме реального времени, где каждый элемент такой системы которой может независимо от других компонентов системы решать свою задачу [74]. При этом существующие в настоящее время системы IP-телефонии, видеоконференцсвязи, мгновенного обмена сообщениями (instant messaging), а также подобные им сервисы, по сути, являются мультисервисными программными и программно-аппаратными системами. В них, наряду с приоритетным (в зависимости от их функционального назначения) сервисом, параллельно происходит обслуживание пользовательских заявок ряда других сервисов. Так, к примеру, в современных системах instant messaging параллельно с функцией текстового чата или IP-телефонии пользователь имеет возможность отправки множества данных различных форматов (графические, аудио и видео фрагменты, файлы произвольной структуры). Учитывая наметившиеся в последнее время тенденции в разработке сервисов, обеспечивающих повышенный уровень защиты персональных данных, подобные системы могут быть основаны, как на моделях «клиент-сервер» (шифрование клиент-сервер), так и на моделях peero-peer (сквозное шифрование). Последний подход означает, что система должна обеспечивать децентрализованное управление потоком мультисервисных сообщений. В общем же случае наблюдается комбинированное использование указанных моделей организации потоково-ориентированных сетевых сервисов.
Большая часть таких сетевых сервисов, кроме функционирования в режиме реального времени, функционируют по схеме 24/7, что накладывает на МСОИ требования по производительности и отказоустойчивости. К таким системам можно отнести программно-ориентируемые Центры обработки данных (далее – ЦОД), часто используемые в компаниях, чья деятельность зависит от быстрой и эффективной обработки больших объемов данных. Аналогичная ситуация с системами технических средств для обеспечения функций оперативо-разыскных мероприятий (далее – СОРМ) [1], условия и требования к которым в соответствии с Федеральным законом от 06.07.2016 № 374-ФЗ (пакет Яровой-Озерова) ужесточились в разы. Если в случаях с потерей данных в ЦОД, компании могут нести лишь финансовые потери, то для СОРМ, используемых спецслужбами в сети оператора связи, такие сбои, могут поставить под удар государственную безопасность. Как правило, такие МСОИ обслуживают сложноуплотненные потоки данных высокоскоростных магистральных волоконно-оптических каналов, а значит могут быть представлены как многоканальная система обработки информации с внутренней реализацией разделения этих потоков на подпотоки с минимальной задержкой [2]. При этом разделение обобщенного потока на подпотоки обычно выполняется либо на основе номера потока (например, для потоков с речевой нагрузкой), либо на основе адресной информации, присутствующей в заголовке пакетов. Также возможна реализация двухуровневого разделения, когда на первом уровне выделяются подпотоки на основе вида нагрузки (речь, видео, данные, др.), каждый из которых на втором уровне может быть разделен на производные подпотоки на основе адресной информации или номера потока.
Особенностью потоково-ориентированных сетевых сервисов, функционирующих в режиме близком к реальному времени (NRT, Near RealTime) является высокая эффективная скорость передачи данных, как в обобщенном сложноуплотненном потоке (десятки гигабит в секунду), так и выделенных подпотоках (сотни мегабит в секунду) [3]. При этом обработка данных в таких подпотоках должна осуществляться на контекстном уровне, что не позволяет реализовать механизмы ее отложенной обработки. Обобщенная схема организации МСОИ для потоково-ориентированных сетевых сервисов представлена на рисунке 1.
Из рисунка 1 видно, что функционально такая МСОИ может состоять из двух видов узлов:
1. Узел выделения подпотоков по заданным признакам.
2. Узел обработки подпотока выделенного типа.
При этом, в отличие от узлов обработки, узел выделения подпотоков в таких МСОИ представлен в единичном экземпляре, в силу того, что сложноуплотненный входной поток поступает только на один вход. Очевидно, что для эффективного функционирования узла выделения подпотоков требуется его особая реализация, поддерживающая алгоритмы разделения высокоскоростного потока на подпотоки с минимальной задержкой. вариантами такой реализации могут быть программно-аппаратные решения на базе программируемых логических устройств [75] (PLD, programmable logic device), архитектура которых не является предметом настоящего исследования.
Будем предполагать, что узел выделения подпотоков является генератором нагрузки для n-узловой распределенной вычислительной системы, а единицей нагрузки будем считать требующий обработки подпоток заявок определенного класса, поступающий на вход n-го узла обработки подпотока с заданной интенсивностью . Очевидно, что обобщенный сложноуплотненный поток содержит совокупность заявок разных классов, но при этом в рамках одного класса (подпотока) по времени обработки эти заявки будем считать неразличимыми.
Для стационарного режима функционирования такой МСОИ можно рассматривать следующие характеристики ее производительности [4]:
- загруженность – доля времени, в течение которой МСОИ обрабатывает заявки;
- очередь – среднее количество заявок на n-м узле обработки подпотока;
- пропускная способность – среднее количество заявок, обрабатываемых МСОИ в единицу времени;
- время пребывания – среднее время нахождения заявки на узле обработки (включая задержку обработки и само время обработки).
Производительность совместно работающих узлов зависит не только от структуры связи между ними, вычислительной мощности отдельных элементов системы, но и, в определяющей степени, от динамики вычислительного процесса, порождаемого запущенной на них программной составляющей.
В то же время, для организации архитектуры МСОИ, допускает их модульность, как с точки зрения разделения всей системы на подсистемы (хранения данных, вычислительную, сетевую и др.) так и с точки зрения ассоциации узла обработки не с вычислительной системой, а с ПМ, выполняющимся на этом узле. Представление вычислителя в виде ПМ допускает ситуацию создания универсального узла обработки, содержащего ПМ узлов обработки для всех классов заявок и специализированного на обработку подпотока заявок одного класса. Такой узел в условиях возникновения потерь заявок имеет возможность передачи (получения) части заявок из подпотоков других узлов МСОИ (механизм динамической балансировки загрузки).
Организация такого МСОИ может строится на единой платформе, представляющая собой аппаратно-программный комплекс управления МСОИ. Эта платформа обеспечивает совместную работы различных функциональных ПМ комплекса и специализированных устройств сбора данных из разных источников и устройств.
Построение и анализ математической модели процесса функционирования программного модуля в условиях изменяющейся нагрузки
Наиболее подходящей моделью такой МСОИ является сеть массового обслуживания (СеМО), представленная направленным графом [29]: G= N,E (9) где N={C, Q, S, Т} - множество вершин, С - множество истоков, соответствующих подпотокам класса заявок, Q - множество очередей, S -множество узлов обработки подпотоков, Т - множество стоков, соответствующих выходам заявок из МСОИ.
Очевидно, что в простейшем случае такая СеМО является (подпотоки заявкок поступают на ее вершины извне, а обработанные заявки выводятся из СеМО). Однако условиях потерь заявок определенного класса на узлах обработки и реализации механизма динамической балансировки загрузки множества S, МСОИ может быть представлена моделью СеМО смешанного типа (режим передачи заявок от одной СМО к другой).
При этом СеМО, моделирующая МСОИ без потерь заявок на узлах обработки только с большими ограничениями может быть представлена открытой сетью Джексона (допущение о неразличимости классов заявок, доказательство показательного распределения времени обработки заявок на узлах обработки и пуассоновского характера входных подпотоков заявок). Более подходящим для моделирования является обобщение сети Джексона - сеть ВСМР, допускающая присутствие подпотоков заявок разных классов. При этом, в зависимости от специфики работы МСОИ. ее узла обработки подпотоков могут быть описаны одним из допустимых для ВСМР сетей классов (FCFS, PS, IS, LCFS-PR) [30].
Тогда согласно BCMP теореме [84] узел обработки подпотоков могут рассматриваться независимо друг от друга и вероятность того, что на них находится заданное количество заявок, может быть получена как произведение соответствующих вероятностей для отдельных узлов (мультипликативное решение):
При этом интенсивность выхода заявок из стоков узла МСОИ определяется как: где, 4 г интенсивность выхода заявок, зависящая от вида ВСМР сети ( 0j,c - в случае одного входа или \r 0j,r – для заявок класса г на і-м узле обработки). На рисунке 15 представлена схема открытой СеМО, моделирующей МСОИ c i узлами обработки N входных подпотоков.
В моделях МСОИ на основе BCMP СеМО открытого типа для близких к реальному времени потоково-ориентированных сервисов достаточно проблематично представить ситуацию потери обрабатываемой заявки, связанную, либо с недостаточной пропускной способностью узла обработки подпотока, либо с его функциональным и/или физическим отказом. Кроме того, модели BCMP СеМО предполагают независимость рассмотрения процесса обработки подпотока заявок разных классов узлами обработки.
Такое представление узла обработки допускает ситуацию создания универсального узла обработки МСОИ, содержащего ПМ узлов обработки для всех классов заявок и специализированного на обработку подпотока заявок одного класса. Такой узел МСОИ в условиях возникновения потерь заявок имеет возможность передачи (получения) части заявок из подпотоков других узлов МСОИ (механизм динамической балансировки загрузки). Проблема моделирования таких узлов BCMP СеМО связана с, так называемым, парадоксом Браэрса [30], согласно которому в случае неоптимального распределения подпотоков по узлам обработки добавление дополнительных путей в СеМО приводит к существенному увеличению времени прохождения заявки от истоков к стокам СеМО. Парадокс Браэрса обусловлен выбираемым критерием равновесия, достигаемым в СеМО, который не во всех случаях может соответствовать глобальному оптимуму.
В силу такого ограничения для моделирования МСОИ, поддерживающих механизм динамической балансировки загрузки можно использовать еще одно обобщение открытых СеМО, допускающих мультипликативное решение, а именно G-СеМО [31]. В таких СеМО кроме обычных подпотоков заявок, именуемых положительными, вводятся подпотоки дополнительных заявок, именуемых, либо отрицательными заявками, либо триггерами.
В общем случае использование указанных вариантов моделей G-СеМО с уничтожением заявок на разных участках их стационарности может позволить более адекватно моделировать процессы потери данных при обслуживании узлами обработки подпотоков переменной интенсивности.
Однако их применение в конкретных вариантах МСОИ требует проведения развернутых исследований, а в силу того, что каждый узел имеет свою уникальную модульную структуру, в рамках исследования было принято остановиться на моделировании одного ПМ, для нахождения значения вероятности обслуживания заявки, ведь как было отмечено выше (2), именно этот показатель СеМО является частным для определения количества заявок, находящихся в системе.
В качестве простейшей модели ПМ, являющегося элементарной единицей СеМО, рассмотрим СМО вида Н2/М/1/п обслуживания трафика гиперэкспоненциальным распределением при ограничении, что время обслуживания заявки в устройстве обслуживания Гобсл=1/и = 1, имеет вид (Рисунок 16): Рисунок 16. СМО-модель H2 /M /1/n процесса обслуживания программным модулем трафика с гиперэкспоненциальным распределением
В рассматриваемой СМО с фиктивным приемным устройством, одним обслуживающим устройством и БП ограниченной емкости п,0 п ювходной поток однотипных заявок условно разбивается на две параллельные фазы, по которым заявки попадают в систему, причем интенсивности на каждой фазе различны. Заявка, закончившая процесс внешней генерации на фиктивном устройстве с положительной вероятностью /„ присоединяется к очереди в накопителе и с дополнительной вероятностью 1-f n покидает систему.
Дисциплина выбора заявок из очереди на обслуживание является любой из множества бесприоритетных дисциплин: FCFS, LCFS, RANDOM.
Использование уравнений Колмогорова для такой СМО требует разработки графа состояний, что в свою очередь приводит к необходимости использования метода фаз для сведения немарковской системы к марковской.
Рассмотрим СМО вида Я2/М1/3. Определимся с параметрами, используемыми для кодирования состояния марковского процесса и рассчитаем количество состояний для указанной СМО.
В качестве первого символа состояния будем использовать количество заявок в СМО (в приборе и накопителе), в качестве второго - номер фазы, с которой пришла заявка. Количество состояний при этом можно вычислить по формуле: K = k(N + 1) + k (12)
При поступлении заявки обязательно происходит переход в состояние с большим количеством заявок, а также возможна смена фаз поступления заявки (Рисунок 17).
Следующим шагом анализа модели является составление системы дифференциальных уравнений для описания отображенных состояний: ц,
Необходимо помнить, что после решения системы уравнений (13), найденные вероятности будут соответствовать состояниям определенной фазы, при том, что требуется найти состояния, учитывающие только количество заявок в системе. Это возможно при суммировании решений по различным фазам, но с одинаковым числом заявок:
Найденные таким образом безусловные вероятности являются важным этапом для нахождения остальных характеристик системы уравнений, а также производить расчеты для систем с большим количеством каналов и объемом БП.
Исследование зависимости вероятности блокировки (отказа ПМ) 1-/я от основных параметров системы и фиктивного приемного устройства, обеспечит возможность реализовать процедуру краткосрочного прогнозирования, тем самым выиграв время, для применения решающего правила по перераспределению ресурса БП.
Таким образом, появляется необходимость аналитического описания процесса обработки потока заявок с гиперэкспоненциальным распределением времени СМО с различным объемом БП, чтобы в дальнейшем использовать эту математическую модель для нахождения зависимостей основных входных характеристик от выходных.
Особенности проектирования и алгоритмы работы глобального и локального менеджеров
Дополнительно к ПМ, на узле обработки размещен локальный менеджер, который по своей сути выполняет функции мониторинга ПМ узла обработки.
Его задачей является мониторинг характеристик ПМ: текущий объем закрепленного за ним виртуального ресурса – N, степень его загруженности - и значения коэффициента вариации - v , элементарных подпотоков на входах этих ПМ узлов обработки, схема алгоритма работы представлена на рисунке 30.
Процедура формирования таблицы загрузки системы является вложенной в процедуру запуска глобального менеджера которая предшествует процедуре запуска локального. Значения этой таблицы загрузки используются локальным менеджером для считывания пороговых значений, о которых будет описано в главе чуть позже. Основной задачей локального менеджера является сравнение этих пороговых значений со значениями, полученными при мониторинге с последющим поднятием нужного флага (ФлагПи). Пример расчитанных пороговых значений для заявок 3 классов с разным качеством обслуживания представлены в приложении 1. Значение флага – описывает состояние ПМ и записывает его значение вместе с остальными параметрами входного потока в таблицу загрузки, находящуюся на стороне глобального менеджера. Это значение флага, в дальнейшем является ключевым параметром для срабатывания определенной ветки алгоритма глобального менеджера.
Необходимо остановится подробнее на моменте с поднятием локальным менеджером нужного флага, характеризующего его статус. В качестве основного правила определения статуса ПМ, применим алгоритм гистерезисного управления, хорошо зарекомендовавший себя при решении задач контроля перегрузки в центрах обработки данных (рисунок 31).
Первым этапом определения статуса, является установление режима, в котором функционирует ПМ: нормальном, перегрузки, и блокировки памяти, упрощенная схема СМО с использованием гистерезисов представлена на рисунке 32. Пока число контейнеров в системе не превышает порог Н, но превышает порог L система находится в нормальном режиме. Если число контейнеров превысило значение Н, система переходит в режим перегрузки, локальный менеджер регистрирует этот факт, и впоследствии на основании этого глобальный менеджер включит механизм перераспределения ресурса БП между обрабатывающими ПМ. Третий случай, когда число контейнеров не превышает порог L, то система находится в состоянии блокировки памяти, и количество закрепленного за ним ресурса, не снизится ниже этого порога, применительно к объекту исследования, данное значение предварительно заложено в глобальную таблицу загрузки.
Использование локальных менеджеров, является очень удобным приемом, так как он является самостоятельной интелектуальной единицей внутри узла обработки и обладает рядом свойств [43]:
- автономность. Менеджер выполняет строгий набор задач, и никакие кроме внутренних факторов узла не могут повлиять на его работоспособность;
- самостоятельность. Менеджер способен решать поставленный перед ним набор задач, причем производит планирование самостоятельно;
- адаптивность. Менеджер способен существовать в определенном окружении элементов вычислительного узла на котором он находится, и адаптироваться в зависимости от изменения состояния или количества этих элементов.
- социальность. Менеджер способен общаться с другими менеджерами для выполнения совместных операций, если это предусмотрено его набором задач.
По своей природе локальные менеджеры являются мультизадачными, и их функции и алгоритм их действий может быть ограничен только временным ресурсом.
Центральным звеном в организации двухуровневого управления МСОИ является глобальный менеджер. Его размещение в системах с подобной реализацией стараются подобрать исходя из надежности узлов – так как потеря вычислителя и так критическая ситуация для МСОИ, в случае, когда на этом вычислителе находился глобальный менеджер с глобальной и локальной таблицей загрузки полностью недопустима.
Для уменьшения вероятности таких случаев необходимо реализовывать репликацию образа глобального менеджера или запускать теневого глобального менеджера как уже описывалось в 1 главе при описании работы GFS.
Глобальный менеджер состоит из следующих частей (рисунок 33):
- ПМ мониторинга и прогнозирования;
- глобальная таблица загрузки;
- ПМ формирования стратегии.
После запуска МСОИ, инициализируется процедура запуска глобального менеджера, где первоочередно формируется глобальная таблица загрузки системы, в этой таблице содержатся все показатели функционирования всех ПМ и ключевые характеристики обрабатываемых ими элементарных потоков. Информация в глобальной таблице заполняется благодаря обмену информацией с локальной таблицей локального менеджера, находящейся непосредственно на узле обработке. В предложенном алгоритме, основным «маркером» для включения механизма распределения ресурса является флаг Z, описание процедуры которого является ядром данной главы. Глобальный менеджер реализует следующие функции:
1. Отслеживание по показателю v превышения порога гистерезиса коэффициента вариации для определения аномальной интенсивности подпотоков.
2. Сбор информации о значениях характеристик (r, N) ПМ всех узлов с целью определения режима их работы в соответствии со схемой гистерезисного управления очередью.
3. На основании полученных данных (пп. 1 и 2), определение статуса ПМ и в случае перегрузки ПМ и/или превышения порога v реализация механизма перераспределения ресурса БП ПМ.
За каждую из функций отвечает отдельный ПМ из состава менеджера, функциональная схема алгоритма работы которого представлена на рисунке 34. Необходимо отметить, что после запуска глобального менеджера, вычислительные узлы системы с ПМ и локальными менеджерами на борту функционируют параллельно, а считывание их локальных таблиц происходит поочередно, что устраняет ряд ошибок, связанных с редактированием одной таблицы двумя или более источниками.
Отличительной особенностью разработанного алгоритма является прогнозирование требуемого ресурса БП, для обеспечения минимальных потерь при обработке потока данных ПМ. Для этого разработанная во 2 главе математическая модель производит расчеты по вычислению вероятности отказа ПМ, и делает разработанный алгоритм «уникальным».
Процедура, отвечающая за «уникальность» алгоритма, приводится в действие в случае обнаружения соответствующего статуса (флаг X) хотя бы для одного из ПМ.
Для подтверждения вышесказанного, представим разработанный алгоритм, обладающий новизной и позволяющий рационально распределить ресурс БП между обрабатывающими ПМ (Рисунок 35).
Для работы представленного алгоритма, необходимо произвести считывание параметров ПМ, участвующих в перераспределении. Следующим этапом будет расчет показателей отказа всех ПМ и нахождения среднего его среднего значения, это необходимо для того, чтобы алгоритм обладал конечностью (19):
Элементы программной реализации механизма межмодульного распределения ресурса памяти на основе менеджеров
Таким образом, в рамках первого этапа имитационного моделирования и первой части имитационной модели удалось реализовать генерацию случайных значений временных интервалов между запросами с помощью генератора случайных чисел. Как и в случае с аналитическим описанием объекта, первым шагом было использование гиперэкспоненциального закона распределения второго порядка, это допущение позволило при создании концептуальной модели генератора достичь относительной простоты при описании его на неформальном языке. Такое описание было необходимо как самому исследователю, так и специалистам в этой области, которые будут развивать это направление в будущем.
Для программирования имитационной модели генератора было необходимо представить концептуальную модель генератора в виде схемы алгоритма его работы (рисунок 37) - эта схема является первой частью схемы логики работы всей имитационной модели.
Для начала работы генератора необходимо задать основные параметры закона распределения и время моделирования, после этого начинается процесс генерации временных интервалов, открывается цикл по всем ПМ и полученные данные сохраняются в двумерный массив. Цикл заканчивается после генерации всех временных интервалов для всех элементарных потоков ПМ, после чего генераторы заканчивают работу. Скриншот программы генерации заявок разработанного с помощью пакета Borland C++ Builder представлен на рисунке 38. В качестве примера были выставлены следующие параметры:
- интенсивность поступления заявок в 1 фазе – 0,1 заявка/с;
- интенсивность поступления заявок в 2 фазе – 0,9 заявка/с;
- вероятность наступления 1 фазы - 0,8;
- вероятность наступления 2 фазы – 0,2.
На данном скриншоте представлена плотность распределения вероятности случайной величины временного интервала между заявками и её визуальное отображение, функция обслуживания сгенерированного потока в этой части программы не реализована. Следует отметить, что генерация проходит в соответствии с математической моделью генератора описанного в 2 главе, и занимает может занимать достаточно большое время при выставленном большом значении времени моделирования. Раздельная программная реализация имитационной модели, позволяет разработчику отдельно заниматься отладкой генератора заявки от имитационной модели обработчика. Так как сгенерированная последовательность временных интервалов сохраняется в отдельном “.xlsx” файле для каждого генератора, есть возможность наглядно пронаблюдать «тяжелый хвост» распределения с помощью пакета офисных программ.
Для этого в созданном генератором файле, конфигурация которого представлена выше, произвелась сортировка по убыванию значения случайно величины и построен график отсортированного ряда содержащий 3026 элементов (рисунок 39).
Таким образом, можно считать, что имитационная модель генератора прошла этап верификации, то есть соответствует замыслу разработчика.
Для программной реализации имитационной модели ПМ работающий с выходом генератора, была разработана концептуальная схема вычислительного узла МСОИ представлена на рисунке 40 в виде схемы алгоритма. Основные параметры необходимые для функционирования схемы представлены в блоке «ввод исходных данных» на рисунке 37. Из схемы видно, что обработка ПМ сгенерированных последовательностей производится параллельно, в отличие от последовательной работы генератора.
Рисунок 40 - Схема функционирования вычислительного узла МСОИ Как можно увидеть на схеме, на каждом шаге увеличения модельного времени производится проверка значения модельного времени и времени опроса ПМ Tbal – это ключевое условие, запускающее механизм перераспределения ресурса БП между ПМ. Выбор значения Tbal существенно влияет на результаты моделирования с точки зрения эффективности разработанного алгоритма распределения ресурса так и с точки зрения затрат ресурсов компьютера на моделирование. Если выбрать значение Tbal достаточно большим, то результаты моделирования могут быть не показательными. С другой стороны, уменьшение этого значения, для повышения выигрыша от предложенного метода, может негативно сказаться на адекватности отражения реальных событий, а сама процедура распределения будет забирать большую часть ресурса системы, чем вся схема обработки сгенерированных потоков. Анализ чувствительности имитационной модели к параметру Tbal будет описан далее в тексте главы.
Ключевым элементом имитационной модели является та часть схемы, где реализованы функции глобального и локальных менеджеров. При наступлении времени моделирования кратного Tbal, цикл уходит на дополнительную ветвь, в которой каждый из локальных менеджеров сравнивает текущие параметры “подконтрольных” ПМ со значениями, полученным из служебной таблицы. Система поднятия флагов идентична описанной в 3 главе, а сама процедура распределения ресурса БП на схеме называется “процедурой балансировки”, и является отличительной новизной алгоритма. В случае поднятия флага, формируется и представляется список (list) ПМ, с которым для формирования стратегии распределения ресурса будет работать глобальный менеджер. Для этого сравнивается эталонные значения объема БП ПМ и его текущие значения, а также степень загруженности ПМ – это необходимо для того, чтобы БП распределялась как можно более равноверно между всеми вычислительными элементами. При создании этой схемы немаловажным моментом была минимизация количества составляющих её процедур, так как временные издержки подставили под сомнение адекватность отображаемых процессов. Вышеописанные процессы представлены в виде схемы на рисунке 41.
Для случая, когда хотя бы на одном ПМ поднят флаг, глобальный менеджер начинает выполнять свои функции по распределению ресурса памяти.
Обработка списка ранжированных ПМ производится циклично, с использованием алгоритма из 3 главы, причем цикл заканчивается, когда менеджер регистрирует отсутствие свободного ресурса памяти в системе.
Функционирование имитационной модели работы глобального менеджера происходит по схеме, представленной на рисунке 42.
Особенностью разработанного программного обеспечения является возможность отключать данную ветвь алгоритма, это необходимо для того, чтобы была возможность на имитации, при одинаковых входных параметрах, проверить выходные параметры системы в текущей конфигурации и с использованием предлагаемого алгоритма.
Таким образом соединив все части имитационной модели, получаем логическую схему имитационной модели МСОИ с возможностью межмодульного распределения ресурса памяти (Приложение 2).
Разработанная имитационная модель выполнена в видео программного обеспечения, скриншот которой представлен на рисунке 43.
Интерфейс программы позволяет достаточно удобно и гибко задавать параметры законов распределения, по которым будут работать генераторы, что делает программу ориентированной на применение сценарного подхода при проведении эксперимента. Каждая из строчек сценария соответствует своему элементарному потоку, а в столбцах записывается значение интенсивности в формате «время моделирования / заявок/с).
При нажатии на кнопку «сохранить конфигурацию», все выставленные параметры генераторов и обработчиков сохраняются в виде конфигурационного файла, что особенно удобно для проверки сценария на двух и более конфигурациях системы.
В результате моделирования определяются следующие параметры каждого из ПМ:
- Количество заявок, пришедшее на обработку ПМ;
- Количество успешно обработанных ПМ заявок;
- Количество потерянных при обработке заявок (ситуаций переполнения БП);
- Вероятность потери заявки на ПМ;
- Максимальная длина очереди.
Эти параметры, а также отчеты о работе генераторов и отчет глобального менеджера о ситуациях распределения ресурса отображаются в служебном поле программы (рисунок 44) и сохраняются в файле с расширением xslx в директории сценария.