Гомельский государственный университет им. Ф. Скорины
Имитация распределенной обработки информации вычислительных системах и локальных вычислительных сетях
В.Д. Левчук, И.В. Максимей
С.Ф. Маслович, В.И. Селицкий
В.В. Старченко, О.В. Быченко
Гомель, Республика Беларусь
Аннотация
Предложено использовать для анализа вариантов организации распределенной обработки информации в вычислительных системах и локальных вычислительных сетях вероятностный граф реализации вычислительного процесса с явными связями типа вероятностных сетевых графиков.
Ключевые слова: вычислительный процесс, имитация, сетевой график, рабочая нагрузка, коэффициент загрузки.
Введение
Исследование изменений характеристик вычислительного процесса (ВП) при проектном моделировании вычислительных систем (ВС) и локальных вычислительных сетей (ЛВС) зачастую осуществляется с помощью аналитических моделей (АНМ). При этом ВП исследуется при изменении скоростей обработки информации (хp) на центральном процессоре (ЦП), интенсивности поступления запросов пользователей i-го типа (лi), составляющих в совокупности рабочую нагрузку (РН) на узлах ЛВС [1, 2]. Используя аналитические зависимости, прогнозируется изменение коэффициентов загрузки ЦП (зЦП) и среднего времени обслуживания запросов РН (Tжi) операционной системой (ОС) и программами пользователей, составляющих в совокупности технологический процесс обработки информации (ТПОИ). Однако в АНМ трудно учесть наличие конкуренции за ресурсы ЛВС и, поэтому исследования ограничиваются верхними оценками (зЦП) и (Tжi). При последующем исследовании ВС и ЛВС этих оценок уже недостаточно, поэтому исследователи вынуждены использовать имитационные модели (ИМ). В работах [3-5] приведены примеры полностью имитационного подхода к исследованию динамики использования ресурсов ЛВС и результаты сравнения использования двух типов ИМ ВП и РН на ЛВС.
Экспериментально показана возможность появления «эффекта мультиобработки» при моделировании ВП в ЛВС традиционными моделями СМО. Вместе с тем, простого перехода к ИМ уже недостаточно при исследовании вариантов организации распределенной обработки в ВС или ЛВС - очень часто необходима информация, требующая обработки по запросам пользователей и распределенная в различных узлах ЛВС. Поэтому ВП в ВС и ЛВС часто представляет собой непрерывную смену выполнения запросов на различных узлах ЛВС. При этом вероятностные ИМ ВП и РН на ЛВС с полумарковским характером процесса формирования запросов пользователей на ресурсы ЛВС [5, 6] уже не могут отобразить динамику появления запросов на ресурсы ЛВС, расположенные в различных узлах этой сети. Еще одна трудность исследования распределенной обработки в ЛВС заключается в том, что имитация представляет собой ресурсоемкую процедуру, и необходимы средства автоматизации основных этапов имитационного моделирования вариантов организации ВП в ЛВС. В данной статье авторами предлагается вместо полумарковской ИМ использовать вероятностный граф реализации вычислительного процесса (ВГВП), в котором явно отображается состав и структура взаимосвязей между процессами, рожденными запросами пользователей на различных стадиях реализации их исполнения в различных узлах ЛВС.
Формализация вычислительного процесса и рабочей нагрузки на ЛВС на основе аппарата сетевого планирования
Запросы пользователей, поступающие на обслуживание в ВС и ЛВС, можно разделить на следующие типы:
1) запросы на пакетную обработку на исследуемом s-м узле ЛВС;
2) запросы пользователей диалогового режима взаимодействия, находящиеся на исследуемом s-м узле ЛВС;
3) запросы на удаленную пакетную обработку на других узлах;
4) запросы пользователей удаленного диалогового режима;
5) запросы в узел ВС, означающие однократные сообщения от пользователей данного узла s к другим узлам ЛВС;
6) запросы пользователей s-го узла на многократное взаимодействие с пользователями из других узлов, сопровождаемые многократной передачей информации друг другу (в обе стороны) по сети.
Таким образом, РН, поступающая на ВС или ЛВС, принадлежит одному из таких типов или даже комбинации типов. Для исследования динамики взаимодействия РН с оборудованием ВС и ЛВС выделяются следующие типы ИМ по характеру обслуживания запросов пользователей.
1. Внутренняя. (Запросы обрабатываются только внутри узла). Для этой ИМ соответствуют первый и второй тип РН.
2. Внешняя. (Запросы обрабатываются на внешнем узле, т.е. всегда присутствует пересылка на другие узлы). Ей соответствуют третий, четвертый и пятый типы РН.
3. Смешанная. Запросы обрабатываются внутри узла, при этом всегда присутствует однократная или многократная пересылка результата выполнения k-й операции (конечного или промежуточного) на другой узел ЛВС.
Представим последовательность запросов пользователей на ресурсы узлов ЛВС уже не иерархической полумарковской ИМ, как это описано в работе [7]. Программные модули (ПМj), исполняемые на ЦП j-го узла ЛВС уже не имеют чисто вероятностную природу, а взаимосвязи между ПМij детерминированы и обусловлены структурой ВГВП, хотя длительность выполнения ПМij на ЦПj являются случайными функциями. Поэтому ВГВП более точно отображают динамику распределенного использования ресурсов ЦПj и жесткого диска (HDDj). ВГВП представляет собой вероятностный сетевой график, в котором работами являются микротехнологические операции (МТХОij), а узлами - события (SOBi). Параметрами МТХОij являются: расход ресурса ЦП (фЦПij), расход ресурса HDD (VHDDij), стоимость выполнения операции (Cij). При этом предполагаются известными функциональные зависимости между расходом ресурсов, стоимостью выполнения операции и временем их реализации:
фij = ц1(фЦПij, хcpj),
фij = ц2(VHDDij, хHDDj),
фij = ц3(Cij, хcpj, хHDDj). (1)
Таким образом, в терминологии сетевого планирования на ВГВП МТХОij соответствует действительным работам [8], тогда как они соответствуют программным модулям (ПМij) при полумарковском представлении ВП в ЛВС [6]. В соответствии с классическим определением ВГВП каждое SOBi обладает следующими статистиками его реализации: ранние и поздние сроки свершения событий (tpi и tпi); резерв свершения события (Ri). В отличие от традиционной технологии исследования сетевых графиков все параметры МТХОij являются случайными величинами, задаваемыми соответствующими функциями распределения F1ij(ф), F1ij(V), F1ij(C). Считаем, что фij являются основными параметрами МТХОij, а Vij и Cij - ее вспомогательными параметрами. С помощью задаваемых заранее структуры ВСВП и состава параметров МТХОij указывается местонахождение ресурсов в ЛВС, длительности и стоимости их использования и порядок их выполнения. Независимые друг от друга МТХОij выполняются параллельно, а зависимые МТХОij запускаются только при свершении SOBi в моменты их запуска на имитацию (tрi).
Определим понятие критического пути на ВСВП как последовательность {МТХОij}, выполняемых на ресурсах различных узлов ЛВС, определяющей общее время свершения l-го запроса пользователей ЛВС. Если характеристики выполнения МТХОij постоянны, то аппарат сетевого планирования позволяет определить все сроки свершения событий и резервы их выполнения (tpi, tпi, Ri). Затем по известной методике [7] рассчитываются статистики реализации МТХОij, раннее наличие (tpнij), позднее начало (tпнij), раннее окончание (tpоij), позднее окончание (tпоij). Сам критический путь реализации s-го варианта ВП также легко определяется, представляя при этом последовательность {МТХОij}, соединяющих SOBi с нулевым резервом их свершения. Однако, на практике постоянство структуры ВГВП и параметров {МТХОij} является редким исключением. Вероятностный характер ВГВП и параметров {МТХОij} обуславливает необходимость постановки имитационных экспериментов (ИЭ) с использованием процедур Монте-Карло [8]. В таких случаях результат имитации выполнения ВГВП при одних и тех же начальных значениях параметров ВП и РН на ЛВС также будет вероятностным.
Методика расчета и анализа параметров ВГВП на основе процедур Монте-Карло
Для решения проблем исследования вероятностных технологических процессов производства (ВТПП) с помощью ИМ был разработан программно-технологический комплекс имитации (ПТКИ) [9]. Применение ПТКИ ВТПП основано на изложенной формализации ВГВП и реализуется следующей последовательностью этапов.
Этап 1. Запись параметров МТХОij, входящих в ВСГ l-го типа запросов РН на ЛВС, в информационную базу данных (ИБД) ПТКИ. При этом происходит преобразование описаний МТХОij во внутреннее представление, контроль корректности описания ВСГl, вывод результатов этого контроля на дисплей для устранения ошибок в описании ВСГl. Взаимодействие ПТКИ с пользователем происходит на основе набора «меню» возможностей комплекса в режиме вопрос-ответ. В итоге, по завершении этого этапа синтаксические ошибки в ВСГl будут исправлены.
Этап 2. Расчет и анализ параметров ВСГl по методу Монте-Карло реализуется следующей последовательностью этапов.
2.1 На s-й реализации ВСГl (s = 1,…, N) разыгрываются все значения параметров МТХОij (фijs, Vijs, Cijs) с помощью соответствующих функций распределения F1ij(ф), F2ij(V), F3ij(C). В результате реализуется s-я реализация ВСГl с детерминированными параметрами МТХОij.
2.2 Моделируется выполнение ВСГl в режиме прямого изменения модельного времени t0 при вычислении ранних сроков свершения событий (tpis). Одновременно с этим моделируется расход ресурсов системы (Vijs) и стоимости выполнения (Cijs) при реализации МТХОij. Для вычисления поздних сроков свершения событий (tпis) используется имитация с инверсным характером изменения модельного времени t0.
2.3 Рассчитываются резервы свершения событий Ris и типовые статистики выполнения работ при реализации ВСГl (tрнijs, tпнijs, tроijs, tпнijs). Завершаются расчеты s-й реализации ВСГl по методу Монте-Карло нахождением критического пути (КРПls) реализации l-го запроса РН на ЛВС.
2.4 В результате имитации выполнения N реализаций ВСГl в ИБД ПТКИ будут сформированы выборки значений параметров ВСГl для событий (tpis, tпis, Ris), для МТХОij {tрнijs, tпнijs, tроijs, tпнijs}, для критического пути {КРПsl}. Таким образом, каждой s-й реализации ВСГl в этих выборках соответствуют s-е номера параметров событий, МТХОij и критических путей КРПsl.
Этап 3. Оптимизация ВСГl по данным ИЭ реализуется следующей последовательностью шагов.
3.1 Формирование по выборкам математических ожиданий (Мz) и выборочных дисперсий (Dz). Здесь под z понимают обозначение перечисленных статистик свершения SOBi, выполнение МТХОij и длины путей в ВСГl.
3.2 Осуществляется анализ КПРl, представляющих собой последовательность чередования МТХОij и SOBi, обладающих нулевым резервом времени их свершения (Ris). В общем случае для N реализаций ВСГl может существовать множество {КРПl}, в котором только некоторые пары (SOBi, МТХОij) различны, а остальные пары не отличаются друг от друга. Поэтому исследователю предоставляется диапазон реализации SOBi, одновременно возникающих в ВСГl в одно и тоже время t0 при различных реализациях {КРПl} в ВСГl.
3.3 Путем статистической обработки статистик реализации {МТХОij}, {SOBi} и {КРПl} формируется граф критических путей (GRКРПl) и оценки вероятностных значений коэффициентов напряженности МТХОij [10]. При этом определяется список SOBi, имеющих наибольшие резервы времени их свершения с высокой вероятностью. Из этого списка выбираются МТХОij в качестве кандидатов для исключения из графа критических путей.
3.4 Если множество {КРПl} достаточно большое, то из него формируется GRКРПl. Далее реализуется вторая итерация пока наиболее вероятного критического пути в ВГВП, когда вместо ВГВП исследуется уже GRКРПl. После нескольких итераций число вероятных критических путей существенно сократится, и далее исследователь на основе анализа содержания ветвей оставшегося GRКРПl может определить какая из них является наиболее вероятной.
3.5 Информация, сформированная на каждом шаге этапа 3, хранится в ИБД ПТКИ и может по запросу выводиться исследователю на экран дисплея в любом составе. Это позволяет исследователю более обосновано принять проектное решение в условиях неопределенности и риска.
3.6 Меняются параметры модифицируемых МТХОij, и осуществляется переход на выполнение этапа 1. При этом возможно сравнение результатов, полученных на предыдущей итерации ВГВП, и принимается решение о завершении имитации выполнения ВСГl на ЛВС по методике, изложенной в работе [10].
имитационный вычислительный процесс локальный сеть
Методика имитационного эксперимента распределенной обработки информации в ЛВС