Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных
Рассматривается технология использования имитационных моделей вариантов организации ресурсов локальной вычислительной сети при проектировании структуры распределенной обработки данных. Розглядається технологія використання імітаційних моделей варіантів організації ресурсів локальної обчислю...
Gespeichert in:
| Veröffentlicht in: | Математичні машини і системи |
|---|---|
| Datum: | 2005 |
| Hauptverfasser: | , , , , , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2005
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/58457 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных / И.В. Максимей, В.Д. Левчук, О.И. Еськова, С.Ф. Маслович, Н.Н. Кончиц, В.И. Селицкий, В.В. Старченко // Мат. машини і системи. — 2005. — № 3. — С. 135-146. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-58457 |
|---|---|
| record_format |
dspace |
| spelling |
Максимей, И.В. Левчук, В.Д. Еськова, О.И. Маслович, С.Ф. Кончиц, Н.Н. Селицкий, В.И. Старченко, В.В. 2014-03-23T18:31:45Z 2014-03-23T18:31:45Z 2005 Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных / И.В. Максимей, В.Д. Левчук, О.И. Еськова, С.Ф. Маслович, Н.Н. Кончиц, В.И. Селицкий, В.В. Старченко // Мат. машини і системи. — 2005. — № 3. — С. 135-146. — Бібліогр.: 10 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/58457 681.3 Рассматривается технология использования имитационных моделей вариантов организации ресурсов локальной вычислительной сети при проектировании структуры распределенной обработки данных. Розглядається технологія використання імітаційних моделей варіантів організації ресурсів локальної обчислювальної мережі при проектуванні структури системи розподiленоϊ обробки даних. The technology of using imitation models of variants of organizing local net resource when proposed approach uniting conception of the net graph with methods of computer imitation. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління великими системами Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных Технологія імітаційного моделювання варіантів організації ресурсів локальної обчислювальної мережі при заданій структурі системи розподiленоϊ обробки даних Technology of imitation modeling of variants of organizing local computer networks resources for a given structure of distributed data processing system Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных |
| spellingShingle |
Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных Максимей, И.В. Левчук, В.Д. Еськова, О.И. Маслович, С.Ф. Кончиц, Н.Н. Селицкий, В.И. Старченко, В.В. Моделювання і управління великими системами |
| title_short |
Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных |
| title_full |
Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных |
| title_fullStr |
Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных |
| title_full_unstemmed |
Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных |
| title_sort |
технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных |
| author |
Максимей, И.В. Левчук, В.Д. Еськова, О.И. Маслович, С.Ф. Кончиц, Н.Н. Селицкий, В.И. Старченко, В.В. |
| author_facet |
Максимей, И.В. Левчук, В.Д. Еськова, О.И. Маслович, С.Ф. Кончиц, Н.Н. Селицкий, В.И. Старченко, В.В. |
| topic |
Моделювання і управління великими системами |
| topic_facet |
Моделювання і управління великими системами |
| publishDate |
2005 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Технологія імітаційного моделювання варіантів організації ресурсів локальної обчислювальної мережі при заданій структурі системи розподiленоϊ обробки даних Technology of imitation modeling of variants of organizing local computer networks resources for a given structure of distributed data processing system |
| description |
Рассматривается технология использования имитационных моделей вариантов организации
ресурсов локальной вычислительной сети при проектировании структуры распределенной обработки
данных.
Розглядається технологія використання імітаційних моделей варіантів організації ресурсів
локальної обчислювальної мережі при проектуванні структури системи розподiленоϊ обробки даних.
The technology of using imitation models of variants of organizing local net resource when proposed
approach uniting conception of the net graph with methods of computer imitation.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/58457 |
| citation_txt |
Технология имитационного моделирования вариантов организации ресурсов локальных вычислительных сетей при заданной структуре системы распределенной обработки данных / И.В. Максимей, В.Д. Левчук, О.И. Еськова, С.Ф. Маслович, Н.Н. Кончиц, В.И. Селицкий, В.В. Старченко // Мат. машини і системи. — 2005. — № 3. — С. 135-146. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT maksimeiiv tehnologiâimitacionnogomodelirovaniâvariantovorganizaciiresursovlokalʹnyhvyčislitelʹnyhseteiprizadannoistrukturesistemyraspredelennoiobrabotkidannyh AT levčukvd tehnologiâimitacionnogomodelirovaniâvariantovorganizaciiresursovlokalʹnyhvyčislitelʹnyhseteiprizadannoistrukturesistemyraspredelennoiobrabotkidannyh AT esʹkovaoi tehnologiâimitacionnogomodelirovaniâvariantovorganizaciiresursovlokalʹnyhvyčislitelʹnyhseteiprizadannoistrukturesistemyraspredelennoiobrabotkidannyh AT maslovičsf tehnologiâimitacionnogomodelirovaniâvariantovorganizaciiresursovlokalʹnyhvyčislitelʹnyhseteiprizadannoistrukturesistemyraspredelennoiobrabotkidannyh AT končicnn tehnologiâimitacionnogomodelirovaniâvariantovorganizaciiresursovlokalʹnyhvyčislitelʹnyhseteiprizadannoistrukturesistemyraspredelennoiobrabotkidannyh AT selickiivi tehnologiâimitacionnogomodelirovaniâvariantovorganizaciiresursovlokalʹnyhvyčislitelʹnyhseteiprizadannoistrukturesistemyraspredelennoiobrabotkidannyh AT starčenkovv tehnologiâimitacionnogomodelirovaniâvariantovorganizaciiresursovlokalʹnyhvyčislitelʹnyhseteiprizadannoistrukturesistemyraspredelennoiobrabotkidannyh AT maksimeiiv tehnologíâímítacíinogomodelûvannâvaríantívorganízacííresursívlokalʹnoíobčislûvalʹnoímerežíprizadaníistrukturísistemirozpodilenoιobrobkidanih AT levčukvd tehnologíâímítacíinogomodelûvannâvaríantívorganízacííresursívlokalʹnoíobčislûvalʹnoímerežíprizadaníistrukturísistemirozpodilenoιobrobkidanih AT esʹkovaoi tehnologíâímítacíinogomodelûvannâvaríantívorganízacííresursívlokalʹnoíobčislûvalʹnoímerežíprizadaníistrukturísistemirozpodilenoιobrobkidanih AT maslovičsf tehnologíâímítacíinogomodelûvannâvaríantívorganízacííresursívlokalʹnoíobčislûvalʹnoímerežíprizadaníistrukturísistemirozpodilenoιobrobkidanih AT končicnn tehnologíâímítacíinogomodelûvannâvaríantívorganízacííresursívlokalʹnoíobčislûvalʹnoímerežíprizadaníistrukturísistemirozpodilenoιobrobkidanih AT selickiivi tehnologíâímítacíinogomodelûvannâvaríantívorganízacííresursívlokalʹnoíobčislûvalʹnoímerežíprizadaníistrukturísistemirozpodilenoιobrobkidanih AT starčenkovv tehnologíâímítacíinogomodelûvannâvaríantívorganízacííresursívlokalʹnoíobčislûvalʹnoímerežíprizadaníistrukturísistemirozpodilenoιobrobkidanih AT maksimeiiv technologyofimitationmodelingofvariantsoforganizinglocalcomputernetworksresourcesforagivenstructureofdistributeddataprocessingsystem AT levčukvd technologyofimitationmodelingofvariantsoforganizinglocalcomputernetworksresourcesforagivenstructureofdistributeddataprocessingsystem AT esʹkovaoi technologyofimitationmodelingofvariantsoforganizinglocalcomputernetworksresourcesforagivenstructureofdistributeddataprocessingsystem AT maslovičsf technologyofimitationmodelingofvariantsoforganizinglocalcomputernetworksresourcesforagivenstructureofdistributeddataprocessingsystem AT končicnn technologyofimitationmodelingofvariantsoforganizinglocalcomputernetworksresourcesforagivenstructureofdistributeddataprocessingsystem AT selickiivi technologyofimitationmodelingofvariantsoforganizinglocalcomputernetworksresourcesforagivenstructureofdistributeddataprocessingsystem AT starčenkovv technologyofimitationmodelingofvariantsoforganizinglocalcomputernetworksresourcesforagivenstructureofdistributeddataprocessingsystem |
| first_indexed |
2025-11-27T08:14:37Z |
| last_indexed |
2025-11-27T08:14:37Z |
| _version_ |
1850805049476775936 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 135
УДК 681.3
И.В. МАКСИМЕЙ, В.Д. ЛЕВЧУК, О.И. ЕСЬКОВА, С.Ф. МАСЛОВИЧ, Н.Н. КОНЧИЦ,
В.И. СЕЛИЦКИЙ, В.В. СТАРЧЕНКО
ТЕХНОЛОГИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ВАРИАНТОВ
ОРГАНИЗАЦИИ РЕСУРСОВ ЛОКАЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ ПРИ
ЗАДАННОЙ СТРУКТУРЕ РАСПРЕДЕЛЕННОЙ СИСТЕМЫ ОБРАБОТКИ ДАННЫХ
Abstract: The technology of using imitation models of variants of organizing local net resource when proposed
approach uniting conception of the net graph with methods of computer imitation.
Key words: technology of imitation modeling, local computer nets, distributed data processing system.
Анотація: Розглядається технологія використання імітаційних моделей варіантів організації ресурсів
локальної обчислювальної мережі при проектуванні структури системи розподiленоϊ обробки даних.
Ключові слова: імітаційні моделі, локальні обчислювальні мережі, розподілена обробка даних.
Аннотация: Рассматривается технология использования имитационных моделей вариантов организации
ресурсов локальной вычислительной сети при проектировании структуры распределенной обработки
данных.
Ключевые слова: имитационные модели, локальные вычислительные сети, распределенная обработка
данных.
1. Введение
При проектном моделировании вычислительных систем (ВС) и локальных вычислительных сетей
(ЛВС) зачастую используются аналитические модели [1, 2], которые позволяют прогнозировать
поведение технологических процессов обработки информации. Однако в аналитических моделях
трудно учесть наличие конкуренции заказов пользователей за ресурсы ВС или ЛВС. Поэтому на
более поздних стадиях проектного моделирования таких систем исследователи вынуждены
использовать имитационные модели (ИМ). Один из подходов к исследованию сложных систем,
основанный на сочетании аналитических и имитационных методов исследований, рассмотрен в
работе [2]. Примеры полностью имитационного подхода к исследованию динамики использования
ресурсов ЛВС приведены в работах [3, 4]. Для случаев, когда вычислительный процесс (ВП) в ВС
или ЛВС представляет собой непрерывную смену исполнения запросов пользователей на
различных узлах ЛВС, используются вероятностные ИМ ВП и рабочей нагрузки (РН) на ЛВС [5, 6].
Модели, построенные на возможности их представления в виде полумарковского процесса
формирования запросов пользователей, уже не могут достоверно отобразить динамику появления
запросов со стороны РН на ресурсы ЛВС, которые расположены в различных узлах ЛВС. В данной
статье предлагается методологический подход, объединяющий концепцию анализа реализации
стохастического сетевого графа на основе методов компьютерной имитации. Целью работы
является изложение технологии имитации вариантов ВП для тех случаев, когда имеется
возможность представить состав и структуру взаимосвязей между компонентами ВП в виде
вероятностного сетевого графика (ВСГР) и использовать принцип формализации распределенной
обработки информации в ВС и ЛВС на основе сочетания аппарата сетевого планирования и
процедур метода стохастических испытаний.
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 136
2. Формализация ВП и РН на ЛВС на основе аппарата сетевого планирования
Все запросы пользователей, поступающие на обслуживание в ВС или ЛВС, можно разделить на
следующие типы:
1. Требования пакетной обработки на исследуемом s -ом узле ЛВС.
2. Запросы пользователей в режиме диалогового взаимодействия с ВП, обрабатываемые
на исследуемом s -ом узле ЛВС.
3. Требования удаленной пакетной обработки информации на других узлах сети.
4. Запросы пользователей удаленного диалогового режима.
5. Однократные взаимодействия между пользователями разных узлов типа сообщений.
6. Многократные взаимодействия между пользователями, находящимися на различных
узлах, которые сопровождаются передачей информации в обе стороны по сети.
В общем случае РН на узлах ЛВС представляет собой комбинацию различных типов
запросов пользователей.
По характеру обслуживания запросов пользователей используются следующие типы ИМ ВП
и РН на узлах ЛВС, отображающие:
1. Внутреннее обслуживание запросов РН первого и второго типов.
2. Внешнее обслуживание после пересылки запроса на другие узлы.
3. Смешанное обслуживание, когда запросы обрабатываются внутри узла, но при этом
присутствует однократная или многократная пересылка по сети результатов выполнения операций.
В работе [7] последовательность запросов пользователей на ресурсы узлов ЛВС
представлена иерархической системой полумарковских моделей. В этих ИМ ВП представляется
последовательностью программных модулей ( )ijПМ , реализующих запросы i -го типа на
центральном процессоре j-го узла ( )iCPU длительностью CPijτ и использующих ресурс жесткого
диска ( )jHDD объемом HDijV . Порядок реализации ijПМ определяется матрицей вероятностей
их следования друг за другом ijP . Последовательный характер смен ijПМ и вероятностная
природа расхода ими ресурсов узла ( CPijτ и HDijV ), а также дискретный характер реализации ВП
позволяли зачастую адекватно отображать процесс обработки информации внутри узла и
оценивать расходы ресурсов узлов ЛВС в виде полумарковского процесса. Когда
ijПМ выполняются на различных узлах, строго последовательный характер их следования в ЛВС
не соблюдается. Некоторые ijПМ могут выполняться на различных узлах ЛВС одновременно.
Кроме того, взаимосвязи ijПМ по информации в ряде случаев могут быть строго детерминированы
и порядок выполнения ijПМ в таких ситуациях будет обусловлен структурой базы данных сети.
Для отображения параллельно-последовательного характера использования ijПМ ресурсов
различных узлов ЛВС предложено использовать ВСГР, которые позволяют адекватно отобразить
динамику распределенного использования ресурсов jCPU и jHDD . Аналогами ijПМ и узлов
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 137
)( jUZ полумарковской модели (ПММ) в ВСГР являются микротехнологические операции
( ijMTXO ) и события )( jSOB . Выполнение ijMTXO обеспечивается расходом:
– ресурса jCPU ( CPijτ ), обрабатывающего информацию с производительностью )( CPjϑ ;
– ресурса jHDD ( HDijV ), обрабатывающего информацию с производительностью )( HDjϑ ;
– стоимости реализации операции ( ijc ).
В итоге основным параметром ijMTXO является время ее выполнения ( ijT ), а
дополнительными параметрами становятся ijc , CPijτ , HDijV . Параметрами ресурсов s-го узла ЛВС
являются их производительности sCPU и sHDD ( CPsϑ , HDsϑ ) и общий размер хранимой на HDD
информации ( sV
∑
). Этот общий ресурс каждого узла ЛВС одновременно используется многими
ijMTXO . Предлагаются известные регрессионные зависимости для определения времени
выполнения ijMTXO ( ijT ) по значениям параметров ijMTXO ( CPijτ , HDijV ) и производительности
оборудования ЛВС:
ijT =ϕ1( CPijτ , CPsϑ ); ijT =ϕ2( CPijτ , CPsϑ ) . (1)
В отличие от классического определения сетевого графика каждая ijMTXO в кBCГP ,
кроме времени ее выполнения, обладает набором следующих параметров ( ijT , CPijτ , HDijV , ijc ). При
этом все эти параметры представляют собой случайные величины. Поэтому при описании ijMTXO
в кBCГP ее параметры задаются соответствующими функциями распределения:
)(),(),(),( 4321 cFVFFTF ijHDijcpijij τ . (2)
В соответствии с классическим определением сетевого графика для события iSOB
вычисляются следующие статистики их реализации: разные и поздние сроки их свершения ( pit и
iПt ), резерв свершения события iR = iПt – pit . Независимые друг от друга ijMTXO выполняются
параллельно на разных узлах ЛВС, а зависимые друг от друга ijMTXO инициируются только при
свершении iSOB в моменты их запуска на имитацию ( pit ). Все особенности информационного
взаимодействия и порядок инициализации ijMTXO определяются структурой кBCГP . В тех
случаях, когда параметры ijMTXO являются постоянными величинами, BCГP вырождается в
обычный сетевой график, для анализа которого разработаны классические методики [7]. Целью
этих методик является определение критического пути КРП, нахождение резервов свершения
iSOB ( iR ), вычисление коэффициентов напряженности ( ijKн ) и коэффициентов резерва ( ijКр )
ijMTXO на сетевом графике. Под критическим путем в сетевом графике понимается
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 138
последовательность }{ ijMTXO , выполняемых на ресурсах узла ЛВС, у которых резервы
предыдущих и последующих событий ( iSOB и jSOB ) равны нулю. Как известно [7], КРП
определяет общее время выполнения запросов пользователей ЛВС ( kTkp ) в k-ом варианте
запроса пользователями ресурсов ЛВС.
В случае анализа статистик реализации обычного сетевого графика по известным
методикам [7] рассчитываются статистики реализации ijMTXO : раннее начало ( нijpt ), позднее
начало ( нijП
t ), раннее окончание ( poijt ), позднее окончание ( оijП
t ). В тех случаях, когда
характеристики выполнения ijMTXO являются случайными величинами, аппарат сетевого
планирования [7] не позволяет определить сроки свершения событий iSOB и резервы их
выполнения ( pit , iПt , iR ). Такая ситуация имеет место в тех случаях, когда ijMTXO реализуются
на разных узлах ЛВС и сами значения параметров ijMTXO необходимо задавать с помощью
соответствующих распределений их значений (2). Отметим, что на практике постоянство структуры
кBCГP и параметров }{ ijMTXO является редким исключением. Поэтому вероятностный характер
кBCГP и параметров }{ ijMTXO обуславливает необходимость постановки имитационных
экспериментов (ИЭ) с использованием процедур Монте-Карло [8].
3. Методика расчета и анализа параметров ВСГР на основе процедур Монте-Карло
Для решения проблем исследования вероятностных технологических процессов производства с
помощью ИМ был разработан программно-технологический комплекс имитации (ПТКИ ТПП) [9],
применение которого реализуется следующей последовательностью этапов.
Этап 1. Запись параметров ijMTXO , входящих в ВСГР k-го типа запросов РН на ЛВС в
информационную базу данных ПТКИ ТПП. При этом преобразуются описания ijMTXO во
внутреннее представление. Взаимодействие этого комплекса с пользователем осуществляется на
основе набора «меню» возможностей в режиме вопрос-ответ.
Этап 2. Расчет и анализ параметров ВСГРk по методу Монте-Карло реализуется
следующей последовательностью шагов.
Шаг 1. На l-ой реализации кBCГP (s=1,…, N) разыгрываются все значения параметров
ijMTXO (Tijl, τCPijl, VHDijl, cijl) с помощью соответствующих функций распределения (2).
кBCГP заменяется обычным сетевым графиком с постоянными значениями параметров
ijMTXO , к которому можно применить известную методику расчета и анализа статистик
реализации операций { ijMTXO } и свершения событий { iSOB } [7].
Шаг 2. Осуществляется расчет ранних сроков свершения событий (tрil). Формируются
статистики расходов ресурсов ЛВС (VHDijl), (τCPijl) и стоимости выполнения (cijl) при реализации
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 139
{ ijMTXO }. Вычисляются поздние сроки свершения событий (tпil) по известному алгоритму [7],
начиная с завершающего события в обратном порядке и кончая исходным событием.
Шаг 3. Рассчитываются резервы свершения событий {Ril} и типовые статистики выполнения
ijMTXO при реализации сетевого графика (tрнijl, tпнijl, tроijl, tпоijl). Завершается анализ l-ой реализации
кBCГP нахождением критического пути ( кIKPП ) при реализации k-го запроса РН на ЛВС.
Шаг 4. В результате имитации выполнения N реализаций кBCГP в базе данных комплекса
формируются выборки: значений статистик реализации событий {tрil, tпil, Ril}, статистик реализации
ijMTXO {tрнijl, tпнijl, tроijl, tпоijl}, критических путей { sIKPП }. Каждой l-ой реализации кBCГP в этих
выборках соответствуют l-ые номера статистик реализации { iSOB }, { ijMTXO }, { IкKPП }.
Этап 3. Оптимизация ВСГР по данным ИЭ реализуется следующей последовательностью
шагов.
Шаг 1. Формирование по выборкам математических ожиданий ( zM ) и выборочных
дисперсий zD . При желании можно по выборкам построить эмпирические функции распределений
( )ZF . Здесь под Z понимаем обозначение перечисленных ранее статистик свершения { iSOB },
выполнения { ijMTXO } и длины критических путей в кBCГP (TКРПk).
Шаг 2. Осуществляется анализ кKPП , представляющего собой последовательность
чередования ijMTXO и iSOB c нулевыми резервами времени их свершения ( 0=isR ). В общем
случае для N реализаций кBCГP может существовать множество { кKPП }, в котором только
некоторые пары ( iSOB , ijMTXO ) различны, а остальные могут не отличаться друг от друга.
Поэтому исследователю сообщается диапазон реализации iSOB , возникающих в BCГP в одно и
то же модельное время t0 при различных реализациях { кKPП } в кBCГP .
Шаг 3. С помощью статистической обработки результатов расчета статистик реализации
{ ijMTXO }, { iSOB }, { кKPП } формируются граф критических путей ( кGRKPП ) и множество оценок
значений коэффициентов напряженности выполнения { ijMTXO } [7]. Составляется также список
тех iSOB , которые имеют большие значения оценок математического ожидания резервов времени
их свершения ( iR ). Из этого списка выбираются те ijMTXO , которые фигурируют затем в качестве
кандидатов на изъятие от них резервов ресурсов для последующего направления этих ресурсов в
распоряжение ijMTXO , находящихся на наиболее вероятном критическом пути с целью
уменьшения времени его свершения.
Шаг 4. Если множество { кKPП } достаточно большое, то из него формируется граф
критических путей кGRKPП . Далее реализуется следующая итерация поиска наиболее
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 140
вероятного критического пути, когда вместо кBCГP исследуется уже сам кGRKPП . После
нескольких итераций число вероятных критических путей существенно сокращается, и далее
исследователь на основе анализа содержимого ветвей оставшегося графа кGRKPП может
определить, какая из них является наиболее вероятной.
Шаг 5. Информация, сформированная на каждом шаге этапа 3, хранится в базе данных
комплекса и может по запросу исследователя выводиться на экран дисплея в любом составе.
Наряду с изменением параметров модифицируемых ijMTXO осуществляется переход на
выполнение этапа 1.
4. Методика имитации распределенной обработки информации в ЛВС
Для имитации распределенной обработки информации в ЛВС можно использовать программно-
технологический комплекс имитации (ПТКИ), реализующий транзактный способ организации
квазипараллелизма на ЭВМ [9]. ПТКИ реализован на базе системы моделирования MICIC [10] и,
согласно ее положениям объекты моделирования компонуются из динамических элементов
(транзактов) и статических элементов (устройств). Транзакты движутся по ИМ от одного устройства
к другому, которые представляют собой обслуживающие приборы с управляющими входами [10].
Поэтому при имитации распределенной обработки информации транзакты представляют собой ИМ
запросов пользователей, а устройства являются ИМ реальных ресурсов узлов ЛВС. Направления
движения транзактов по ИМ должны отражать структуру сети и зависимости между ijMTXO
согласно кBCГP . Особенностью ИМ ВП в ЛВС является представление функционирования CPU в
виде имитаторов использования ресурсов центрального процессора s-го узла ЛВС на четырех
стадиях реализации ijMTXO : ввод запросов пользователей (INs) длительностью (tINs);
обслуживание и распределение запросов по ИМ операционной системой (OSs) длительностью
(tOSs); собственно обработка информации (CALKs) по заказам пользователя с использованием
ресурса CPU длительностью (tCALKs) и ресурса HDDs объемом (VHDijs); вывод результатов счета
пользователю или возврат транзакта на дообслуживание (OUTs). Передача информации между
узлами ЛВС имитируется устройствами (СПДs) длительностью (tСПДs). Транзакты в ИМ могут
обслуживаться подмоделями узлов ЛВС (ИМ UZLs) по различным траекториям, зависящим от типа
транзактов. Длительности пересылки информации по ИМ СПДs до начала моделирования
задаются матрицей средних времен пересылки информации ||tСПДs||. Итак, с помощью ИМ UZLs
моделируется конкуренция запросов пользователей за ресурсы различных узлов ЛВС. Для
отображения динамики взаимодействия ijMTXO при реализации их на различных узлах ЛВС
необходимо построить ИМ кBCГP и организовать взаимодействие ее с ИМ UZLs.
ИМ кBCГP в среде ПТКИ реализуется сочетанием двух типов имитаторов: имитаторы
событий в ВСГР ( iИSOB и jИSOB ), имитаторы микротехнологических операций ( ijИMTXO ).
Каждый имитатор событий на выходе может создавать информационные транзакты (INTRij),
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 141
содержащие в себе информацию о запросах ресурсов узлов ЛВС соответствующей ijMTXO в виде
функций распределения (2). Состав параметров ijИMTXO зависит от типа запроса пользователя
(typek). Имитаторы микротехнологических операций ( ijИMTXO ) по информации, содержащейся в
INTRij, создают управляющие транзакты ( ijUTR ), в которых содержится заказ ( ijIZ ) на ресурсы
узлов ЛВС, необходимых для выполнения ijMTXO при l-ой реализации кBCГP по методу Монте-
Карло. В ijIZ управляющего транзакта ijUTR содержится следующая информация:
=Z ij( ; s , INst , OSst , CALCslt , HDsIV , OUTsIt , ДsCt Π , stype , )перk ,
где ij – номера ijMTXO , соединяющих события iSOB с jSOB ;
s – номер узла ЛВС;
INst , OSst , CALCslt , HDsIV , OUTsIt , ДsCt Π – время обслуживания транзактов в устройствах
ресурсов s-х узлов ЛВС;
stype – тип транзактов (3, 4, 5);
перk – количество пересылок транзактов между узлами ЛВС при выполнении запросов на
ресурсы ЛВС от ijИMTXO .
Все ijUTR поступают на вход ИМ UZL соответственно номерам узлов ( s ), содержащимся в
телах заказов ( ijIZ ), на которых имитируется динамика расхода ресурсов ЛВС. После окончания
обслуживания в ИМ UZLs управляющие транзакты ijUTR возвращаются на имитаторы
микротехнологических операций ijИMTXO и затем ими уничтожаются. При этом фиксируются
времена жизни ijUTR (tжijl) и статистики длительности выполнения ijИMTXO (tМТijl) в l-ой
реализации кBCГP .
Методика имитации распределенной обработки информации в ЛВС с помощью множества
подмоделей {ИМ UZLs} и {ИМ кBCГP } (s-го номера узлов ЛВС, k-го номера типов запросов
пользователей) реализуется следующей последовательностью этапов реализации взаимодействия
алгоритмов кBCГP и алгоритмов обработки информации, распределенной по UZLs.
Этап 1. Имитация выполнения { ijИMTXO } согласно алгоритмам кBCГP . При
срабатывании спусковой функции в устройствах-имитаторах событий iИSOB (когда завершилась
обработка информации в ijИMTXO и hИMTXO , которые предшествуют в кBCГP этому событию)
на их выходах генерируются новые информационные транзакты TRINij, поступающие
соответственно на ijИMTXO . Каждая ijИMTXO формирует соответствующий управляющий
транзакт ijUTR . В результате первого этапа формируется множество { ijUTR }, элементы которого
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 142
созданы соответствующими ijИMTXO и которые поступают каждый на вход той ИМ UZLk, номер
которой указан в теле ijUTR .
Этап 2. Осуществляется имитация расхода ресурсов узлов ЛВС в ИМ UZLs множеством
{ ijUTR }, созданным на этапе 1. Процесс обслуживания каждого ijUTR на s -ом узле ЛВС
имитируется в ИМ UZLs следующей последовательностью шагов.
Шаг 1. Выбор ijUTR из общей очереди ИМ UZLs и имитация устройством-имитатором
процесса ввода информации (ИINs) длительностью (tINs).
Шаг 2. По окончании этой операции ijUTR поступает в очередь к устройству-имитатору
функционирования операционной системы (ИOSs) длительностью (tOSs), где определяется
направление движения ijUTR по устройствам-имитаторам ресурсов узлов ЛВС.
Шаг 3. Имитируется расход ресурса CPUs транзактами ijUTR на устройстве-имитаторе
CALCs длительностью (tCALCsijl). По завершении этой операции ijUTR либо возвращается на
дообслуживание в очередь к устройству ИINs, либо направляется к устройству-имитатору ИСПДs на
дообслуживание его на других узлах ЛВС, либо завершает свой цикл обслуживания на устройстве-
имитаторе вывода информации ИOUTs длительностью (tOUTs). Длительности операций пересылки
ijUTR через ИСПДs перед началом моделирования задаются матрицей средних времен пересылок
информации ||tСПДs||. По завершении запланированного числа пересылок ( ijkΠ ) транзакта ijUTR
внутри ИМ ЛВС имитируется возврат ijUTR на ijИMTXO .
Этап 3. Имитация завершения l реализации кBCГP осуществляется на устройстве-
имитаторе завершающего события (SOB POGLnk), где kn – номер завершающегося события k-го
запроса пользователя. Фиксируется статистика l-ой реализации кBCГP :
=kIST KPkIT( , { }iIiIpiI Rtt ,, Π , { }oijIpoijIHijIPHijI tttt ΠΠ ,,, , )kIKPП ,
где KPkIT – критическое время l-ой реализации кBCГP ;
{ }iIiIpiI Rtt ,, Π – статистики свершения событий i=1,…, kn в кBCГP ;
{ }oijIpoijIHijIPHijI tttt ΠΠ ,,, – определенные ранее статистики реализации ijMTXO ;
kIKPП – критический путь в l-ой реализации кBCГP .
Кроме формирования STkl контролируется момент окончания имитации реализаций кBCГP
(l≤ N ) по методу Монте-Карло [7] и либо организуется повторение следующей реализации IBCГP
с модификацией числа итераций (l:=l+1), начиная с этапа 1, либо осуществляется переход к этапу
4.
Этап 4. Обработка результатов имитации N реализаций кBCГP .
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 143
К началу этого этапа уже накоплена статистика реализации событий, микротехнологических
операций в виде соответствующих выборок статистик, сформирован граф критических путей
{GRКРП} и требуется по этим выборкам либо вычислить математические ожидания и дисперсии
статистик свершения событий и реализации микротехнологических операций, либо построить
эмпирические функции их распределений. Кроме того, на этапе 4 по GRRHG определяются
вероятные критические пути с оценкой вероятностей реализации каждого из этих путей согласно
методике, изложенной в разд. 3.
5. Имитационная модель распределенной обработки информации в ЛВС
Простейший пример ИМ ЛВС, состоящей из одной ИМ ВСГР1 и двух ИМ UZLs ( s =1,2), с
распределенной обработкой информации приведен на рис. 1, ИМ ВСГР1 состоит из 8 устройств-
имитаторов событий ( jИSOB ) i=1,…,8 и 11 устройств-имитаторов микротехнологических операций
ijИMTXO . В этой ИМ отображен параллельно-последовательный характер выполнения ijMTXO и
запуск ijИMTXO при свершении событий iИSOB . Каждая ijИMTXO генерирует управляющие
транзакты ijUTR , поступающие во входные очереди ОЧ11 и ОЧ21 соответственно ИМ UZL1 и ИМ
UZL2.
ИМ UZLs состоят из четырех устройств-имитаторов ресурсов CPU ЛВС (ИINs, ИOSs,
ИCALCs, ИOUTs) и имитатора устройства пересылки информации по ЛВС (СПДs). На вход ИМ UZLs
поступают две группы транзактов: TUZLs и ijUTR . Первая группа транзактов формирует
внутренние запросы узла ЛВС на ресурсы CPUs. Такие запросы рождаются либо при диалоговом
характере взаимодействия пользлвателей на узлах ЛВС, либо при пакетной обработке заказов
пользователей внутри узла ЛВС. Остальные типы запросов пользователей могут использовать
распределенную обработку информации в ЛВС, и динамика расхода ими ресурсов узлов ЛВС
определяется в ИМ кВСГР . Первый тип транзактов TUZls формируется на входе ИМ UZLs
генератором (GEN TUZLs), обслуживается наряду с ijUTR устройствами-имитаторами ресурсов
CPUs и затем либо уничтожается поглотителем (POGLs), либо возвращается на повторное
обслуживание в приоритетную очередь ОЧ3s узла ЛВС. По завершении цикла обслуживания ijUTR
устройство POGLs возвращает ijUTR соответственно на ijИMTXO в ИМ кВСГР . Как видно из
рис. 1, учет расхода ресурсов CPUs запросами первого типа позволяет отобразить конкуренцию
запросов пользователей ЛВС за ресурсы ЛВС.
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 144
Рис. 1. Имитационная модель распределенной обработки информации в ЛВС взаимодействия пользователей
на узлах ЛВС, либо при пакетной обработке заказов пользователей
GEN
TUZL1
POGL1
ИOS1
ИCALC1
ИIN1
ИОUT1
ОЧ31
ОЧ11
ОЧ21
ИСПД1
UTRij
UTRij
GEN
TUZL2
POGL2
ИOS2
ИCALC2
ИIN2
ИОUT2
ОЧ32
ОЧ12
ОЧ22
ИСПД2
UTRij
UTRij
ИМТХО12
ИSOB3
ИМТХО13
ИSOB1
GEN
ИSOB4
ИМТХО57
ИSOB7
ИМТХО78
ИМТХО68
ИSOB8
POGL0
ИМТХО46
ИМТХО54
ИSOB2
UTR23
ИМТХО23 UTR54 UTR67
UTR13
UTR12
UTR78
UTR68
ИМТХО67
ИSOB6
ИSOB5
UTR24 UTR46
UTR35 UTR57
TRIN13
TRIN12
ИМТХО24
ИМТХО35
TRIN24
TRIN35
TRIN46
TRIN68
TRIN23
TRIN54
TRIN57
TRIN78
TRIN67
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 145
6. Выводы
Основным результатом данной работы является иллюстрация нового подхода к исследованию
вычислительного процесса для случая распределенной обработки в ЛВС. Дополнительными
трудностями имитационного моделирования таких систем является необходимость учета
следующих аспектов: параллельно-последовательный характер взаимодействия программных
модулей, выполняемых одновременно по запросам пользователей на различных узлах ЛВС;
необходимость учета конкуренции запросов пользователей за ресурсы узлов ЛВС; требования
учета географии расположения информации, обрабатываемой по запросам пользователей на
различных узлах ЛВС; влияние состава и топологии ЛВС на организацию вычислительного
процесса в узлах сети. Для отображения этих разнородных требований при моделировании в сети
предложены новые принципы формализации и методики организации имитации ВП в ЛВС,
основанные на сочетании аппарата сетевого планирования, процедур метода статистических
испытаний, расширения транзактно-процессного способа имитации за счет информационной
подкраски транзактов и функциональной специализации имитаторов расхода ресурсов
распределенных по узлам ЛВС. Основной трудностью в реализации такого сочетания являлась
необходимость наложения структуры графа взаимосвязей между ПМij, в совокупности
отображающего модель РН на узлах ЛВС, на топологию связей ресурсов в сети и учета наличия
запросов пользователей узлов ЛВС, которые в приоритетном диалоговом режиме активно
используют ресурсы самих узлов ЛВС.
Большинство исследований ВП в ЛВС было основано на использовании полумарковских
моделей. Но такой подход эффективен только в тех случаях, когда ЛВС уже существует, известен
статистический портрет РН на узлах ЛВС и ставится задача имитационного моделирования для
перераспределения ресурсов узлов ЛВС при их адаптации к требованиям РН. Предложенные в
данной работе методики имитации распределенной обработки информации в ЛВС обладают
преимуществом перед имитацией с помощью полумарковских моделей в тех случаях, когда
реальная ЛВС еще не существует и решается задача выбора состава и размещения ресурсов
узлов ЛВС под требования РН на узлах ЛВС. На простейшем примере ИМ ВП в ЛВС, приведенном
на рис. 1, была проиллюстрирована возможность применения новой методики имитационного
моделирования распределенной обработки информации в ЛВС.
СПИСОК ЛИТЕРАТУРЫ
1. Зайченко Е.Ю. Анализ структуры глобальных вычислительных сетей. – К.: ЗАО «Укрспецнопроект», 1998.
– С.108.
2. Коваленко И.Н., Николаев А.Н. Приближенный расчет и оптимизация надежности. – К.: Наукова думка,
1989. – 182 с.
3. Демиденко О.М., Максимей И.В., Агеенко И.В. и др. Имитационное моделирование вычислительного
процесса в узлах локальной сети // УСиМ. – 2000. – №5/6. – С.101–107.
4. Демиденко О.М., Максимей И.В. Проектное моделирование вычислительного процесса в локальных
вычислительных сетях. – Мн.: Белорусская наука, 2001. – 252 с.
5. Демиденко О.М., Максимей И.В. Влияние конкуренции запросов пользователей за ресурсы
вычислительного процесса на организацию вычислительного процесса // Математические машины и системы.
– 2001. – № 2. – С. 3–9.
6. Демиденко О.М. Технология мониторинга и адаптации вычислительного процесса под рабочую нагрузку
на локальную вычислительную сеть. – Мн.: Белорусская наука, 2002. – 193 с.
7. Жогаль С.И., Максимей И.В. Задачи и модели исследования операций: Учебное пособие. – Ч. 1:
Аналитические модели исследования операций. – Гомель: БелГут, 1999. – 103 с.
ISSN 1028-9763. Математичні машини і системи, 2005, № 3 146
8. Максимей И.В., Серегина В.С. Задачи и модели исследования операций: Учебное пособие. – Ч. 2: Методы
нелинейного и стохастического программирования. – Гомель: БелГут, 1999. – 103 с.
9. Максимей И.В., Левчук В.Д., Маслович С.Ф. и др. О проблемной модификации программно-
технологического комплекса имитации технологических процессов производства // Известия Гомельского
государственного университета им. Ф. Скорины. – 2003. – № 3(18). –- С. 38–41.
10. Максимей И.В., Левчук В.Д., Жогаль С.П. Задачи и модели исследования операций: Учебное пособие. –
Ч. 3: Технология имитации на ЭВМ и принятие решений. – Гомель: БелГут, 1999. – 150 с.
|