Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях
Определена актуальность проектного моделирования распределенной обработки информации в ЛВС. Приведена формализация вычислительной и рабочей нагрузки на ЛВС на основе аппарата сетевого планирования. Рассматривается модифицированная технология анализа параметров вероятностного сетевого графика на осно...
Збережено в:
| Дата: | 2004 |
|---|---|
| Автори: | , , , , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2004
|
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/83961 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях / О.В. Быченко, В.Д. Левчук, И.В. Максимей, С.Ф. Маслович, В.С. Смородин, В.И. Селицкий, А.М. Поташенко // Мат. машини і системи. — 2004. — № 3. — С. 132-413. — Бібліогр.: 13 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-83961 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-839612015-07-05T11:19:59Z Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях Быченко, О.В. Левчук, В.Д. Максимей, И.В. Маслович, С.Ф. Смородин, В.С. Селицкий, В.И. Поташенко, А.М. Програмно-технічні комплекси Определена актуальность проектного моделирования распределенной обработки информации в ЛВС. Приведена формализация вычислительной и рабочей нагрузки на ЛВС на основе аппарата сетевого планирования. Рассматривается модифицированная технология анализа параметров вероятностного сетевого графика на основе метода Монте-Карло. Излагается методика имитационного моделирования распределенной обработки информации в ЛВС. Визначено актуальнiсть проектного моделювання розподiленоϊ обробки iнформацiϊ в локальних мережах. Проведено формалізацiю обчислювального процесу і робочого навантаження (РН) на ЛОМ на основi апарату сiткового планування. Розглядається модифiкована технологiя аналiзу параметрiв iмовiрного сiткового графiка iмiтaцiϊ в ЛОМ. An actuality of project modeling of the information distributed processing in LAN is defined. The formalization of a calculating process and a working load to LAN on the base of the network planning method is given. A modified technology of the analysis of stochastic network schedule parameters on the base of a Monte–Carlo method is considered. The methodology of the simulation of the information distributed processing in LAN is stated. 2004 Article Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях / О.В. Быченко, В.Д. Левчук, И.В. Максимей, С.Ф. Маслович, В.С. Смородин, В.И. Селицкий, А.М. Поташенко // Мат. машини і системи. — 2004. — № 3. — С. 132-413. — Бібліогр.: 13 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/83961 681.3 ru Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Програмно-технічні комплекси Програмно-технічні комплекси |
| spellingShingle |
Програмно-технічні комплекси Програмно-технічні комплекси Быченко, О.В. Левчук, В.Д. Максимей, И.В. Маслович, С.Ф. Смородин, В.С. Селицкий, В.И. Поташенко, А.М. Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях |
| description |
Определена актуальность проектного моделирования распределенной обработки информации в ЛВС. Приведена формализация вычислительной и рабочей нагрузки на ЛВС на основе аппарата сетевого планирования. Рассматривается модифицированная технология анализа параметров вероятностного сетевого графика на основе метода Монте-Карло. Излагается методика имитационного моделирования распределенной обработки информации в ЛВС. |
| format |
Article |
| author |
Быченко, О.В. Левчук, В.Д. Максимей, И.В. Маслович, С.Ф. Смородин, В.С. Селицкий, В.И. Поташенко, А.М. |
| author_facet |
Быченко, О.В. Левчук, В.Д. Максимей, И.В. Маслович, С.Ф. Смородин, В.С. Селицкий, В.И. Поташенко, А.М. |
| author_sort |
Быченко, О.В. |
| title |
Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях |
| title_short |
Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях |
| title_full |
Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях |
| title_fullStr |
Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях |
| title_full_unstemmed |
Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях |
| title_sort |
имитационное моделирование распределенной обработки информации в локальных вычислительных сетях |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2004 |
| topic_facet |
Програмно-технічні комплекси |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/83961 |
| citation_txt |
Имитационное моделирование распределенной обработки информации в локальных вычислительных сетях / О.В. Быченко, В.Д. Левчук, И.В. Максимей, С.Ф. Маслович, В.С. Смородин, В.И. Селицкий, А.М. Поташенко // Мат. машини і системи. — 2004. — № 3. — С. 132-413. — Бібліогр.: 13 назв. — рос. |
| work_keys_str_mv |
AT byčenkoov imitacionnoemodelirovanieraspredelennojobrabotkiinformaciivlokalʹnyhvyčislitelʹnyhsetâh AT levčukvd imitacionnoemodelirovanieraspredelennojobrabotkiinformaciivlokalʹnyhvyčislitelʹnyhsetâh AT maksimejiv imitacionnoemodelirovanieraspredelennojobrabotkiinformaciivlokalʹnyhvyčislitelʹnyhsetâh AT maslovičsf imitacionnoemodelirovanieraspredelennojobrabotkiinformaciivlokalʹnyhvyčislitelʹnyhsetâh AT smorodinvs imitacionnoemodelirovanieraspredelennojobrabotkiinformaciivlokalʹnyhvyčislitelʹnyhsetâh AT selickijvi imitacionnoemodelirovanieraspredelennojobrabotkiinformaciivlokalʹnyhvyčislitelʹnyhsetâh AT potašenkoam imitacionnoemodelirovanieraspredelennojobrabotkiinformaciivlokalʹnyhvyčislitelʹnyhsetâh |
| first_indexed |
2025-07-06T10:51:04Z |
| last_indexed |
2025-07-06T10:51:04Z |
| _version_ |
1836894456529289216 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
132
УДК 681.3
О.В. БЫЧЕНКО, В.Д. ЛЕВЧУК, И.В. МАКСИМЕЙ, С.Ф. МАСЛОВИЧ,
В.С. СМОРОДИН, В.И. СЕЛИЦКИЙ, А.М. ПОТАШЕНКО
ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ
ИНФОРМАЦИИ В ЛОКАЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЯХ
Abstract: An actuality of project modeling of the information distributed processing in LAN is defined. The
formalization of a calculating process and a working load to LAN on the base of the network planning method is given.
A modified technology of the analysis of stochastic network schedule parameters on the base of a Monte–Carlo
method is considered. The methodology of the simulation of the information distributed processing in LAN is stated.
Key words: simulation technique, distribute processing of information, local computing networks, networks planning.
Анотація: Визначено актуальнiсть проектного моделювання розподiленоϊ обробки iнформацiϊ в локальних
мережах (ЛОМ). Проведено формализацiю обчислювального процесу (ОП) і робочого навантаження (РН) на
ЛОМ на основi апарату сiткового планування. Розглядається модифiкована технологiя аналiзу параметрiв
iмовiрного сiткового графiка iмiтaцiϊ в ЛОМ.
Ключові слова: імітаційне моделювання, розподілена обробка інформації, локальні обчислювальні мережі,
сіткове планування.
Аннотация: Определена актуальность проектного моделирования распределенной обработки
информации в ЛВС. Приведена формализация вычислительной и рабочей нагрузки на ЛВС на основе
аппарата сетевого планирования. Рассматривается модифицированная технология анализа параметров
вероятностного сетевого графика на основе метода Монте-Карло. Излагается методика имитационного
моделирования распределенной обработки информации в ЛВС.
Ключевые слова: имитационное моделирование, распределенная обработка информации, локальные
вычислительные сети, сетевое планирование.
1. Актуальность проектного моделирования распределенной обработки информации в
локальной вычислительной системе
В данной работе дан новый подход к построению имитационной модели (ИМ) рабочей нагрузки
(РН) на локальную вычислительную сеть (ЛВС) в виде графа вероятностей следования
взаимосвязанных процессов (ГВП), использующих вычислительные ресурсы различных узлов ЛВС
при имитации вычислительного процесса (ВП) в ЛВС.
Существует много публикаций [1, 2], в которых на аналитических моделях (АНМ)
исследуется изменение характеристики ВП под влиянием вариаций скоростей обработки
информации ( )pv на центральном процессоре (ЦП) и интенсивности поступления запросов
пользователей i-го типа ( )iλ , составляющих в совокупности рабочую нагрузку (РН) на узлах ЛВС. С
помощью этих зависимостей прогнозируется изменение коэффициентов загрузки ЦП ( )
ЦПη и
среднего времени обслуживания запросов РН ( )
жіΤ при обслуживании этих запросов
операционной системой (ОС) и программами пользователей, составляющими в совокупности
некоторый технологический процесс обработки информации (ТПОИ) на ЛВС. Однако в АНМ
зачастую трудно учесть наличие конкуренции запросов пользователей за одни и те же ресурсы
ЛВС и поэтому исследования ограничиваются верхними оценками откликов ( ЦПη и жіΤ ). При
проектном моделировании ВП в ЛВС верхних оценок указанных откликов уже недостаточно и
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
133
исследователям приходиться прибегать к использованию ИМ. В работах [3, 4] предложен
интересный подход к исследованию систем, основанный на сочетании аналитических и
имитационных методов исследований. В работах [5, 6] приведены примеры полностью
имитационного подхода к исследованию динамики использования ресурсов ЛВС. В [7] даны
результаты сравнения параметров ВП и РН при использовании двух типов ИМ. В первой ИМ
(МОД1) конкуренция запросов на ЦП отсутствует и ИМ ВП представляет собой многоканальную
многофазную систему массового обслуживания (СМО). Во второй ИМ (МОД2) учитывается наличие
конкуренции нескольких программных модулей (ПМj) за ресурс ЦП, когда в любой момент времени
ресурс ЦП может использоваться только одним из ПМj. Основной результат работы [7] состоял в
демонстрации возникновения существенной ошибки от применения АНМ при наличии конкуренции
запросов РН за ресурсы ЛВС. Была экспериментально показана возможность появления “эффекта
мультиобработки” при моделировании ВП традиционными средствами и методами теории
массового обслуживания. Однако простого перехода к ИМ уже недостаточно при исследовании
распределенной обработки информации в ЛВС. Как правило, очень часто информация, требующая
обработки по запросам пользователей, распределена в различных узлах ЛВС. Кроме того,
множество запросов пользователей на распределенные ресурсы ЛВС взаимосвязано таким
образом, что они не могут выполняться одновременно. Поэтому ВП в ЛВС представляет собой
непрерывную смену выполнения запросов на различных узлах ЛВС. При этом вероятностные ИМ
РН на ЛВС, построенные на основе идеи о полумарковском характере процесса формирования
запросов пользователей на ресурсы ЛВС [7, 8], уже не могут адекватно отобразить динамику
появления запросов на ресурсы ЛВС, расположенные в различных узлах ЛВС. Как видим,
имитационные методы становятся существенным этапом проектного моделирования ЛВС.
Поскольку имитация представляет собой весьма ресурсоемкую процедуру, то возникла
необходимость создания средств автоматизации моделирования сложных систем. В качестве
примера технологических возможностей средств автоматизации моделирования, предоставляемых
в распоряжение разработчиков программного обеспечения АСУ, укажем на работу [9]. В данной
статье вместо полумарковской ИМ предлагается использовать вероятностный ГВП, в котором явно
отображены состав и структура взаимосвязей между процессами, рождаемыми запросами
пользователей на разных стадиях реализации их исполнения и разных узлах ЛВС. Ниже излагается
концептуальная модель распределенной обработки в ЛВС на основе использования
вероятностного ГВП, сформулированы принципы формализации ВП в ЛВС на основе аппарата
сетевого планирования, рассмотрена методика имитации распределенной обработки информации
в ЛВС для случая, когда РН задана в виде вероятностного сетевого графа выполнения процессов
на различных узлах ЛВС.
2. Концептуальная модель распределенной обработки в ЛВС
Содержательное описание для отображения ВП с распределенной по сети информацией должно
существенно отличаться от подходов, предложенных в работах [7, 8]. Во-первых, необходимо
отобразить структуру ЛВС и особенности распределенной обработки информации, хранящейся в
различных узлах ЛВС. Во-вторых, в описании следует сочетать наличие взаимосвязи и
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
134
возможность параллельного использования распределенных по узлам ресурсов ЛВС. В третьих,
необходимо отобразить коллективный характер использования различными процессами
пользователей таких общих ресурсов ЛВС, как ЦПi и дисков (НДДi).
Перечисленные выше требования к составлению содержательного описания
распределенной обработки (СОДО) накладывают свою специфику и на концептуальную модель
(КОНМ) распределенной обработки (РОБ).
Прежде всего состав задаваемых параметров на моделирование должен включать две
группы характеристик, отображающих структуру РН на ЛВС (СТР РН) и определяющих состав
технологических процедур, задающих последовательность технологических операций из которых и
состоит ТПОИ на ЛВС (СОСТП). В качестве задаваемой информации (ЗИНФ) в КОНМ
используются те переменные имитации, которые не меняются в ходе имитационных экспериментов
(ИЭ), но определяют возможные диапазоны изменения общих ресурсов ИМ в узлах ЛВС.
Откликами имитации ВП в ЛВС с распределенными ресурсами служат две группы статистик
имитации: матрица статистик использования i-го типа ресурсов ЛВС RSijY в j-ых узлах ЛВС;
матрица статистик, определяющих качество обслуживания запросов пользователей l-го типа,
поступающих в ЛВС с j-ых узлов ЛВС ТЖljY . Целевой функцией имитационного моделирования k-
го варианта организации ЛВС является максимизация скалярной величины
( )ЕЖІjBПIjCKПIj
jlk
kW ∗Υ+Υ+Υ= ∑∑ 312111max δδδ ,
где 11δ и 21δ – весовые коэффициенты важности для исследователя статистик загрузки
соответственно ресурсов ЦП и НДД пользователями ЛВС l-го типа;
31δ – весовые коэффициенты важности статистик качества обслуживания пользователей l-го типа;
1312111 =++∑ δδδ
l
;
∗ΥТЖІj – приведенные к безразмерному виду на интервале [0, 1] обратные величины откликов
ТЖІjΥ ;
СКПІjΥ и ВПІjΥ – статистики использования ресурсов соответственно ЦП и НДД на j-ом узле ЛВС
запросами пользователей l-го типа.
3. Формализация ВП и РН на ЛВС на основе аппарата сетевого планирования
В предлагаемом ниже подходе к формализации РН и узлах ЛВС запросы пользователей на
ресурсы узлов ЛВС уже не представляются иерархической полумарковской имитационной
моделью, как это описано в работе [8]. Отход от такой формализации РН на ЛВС обусловлен двумя
обстоятельствами. Во-первых, все программные модули (ПМij), исполняемые на ЦП j-го узла ЛВС
уже имеют не чисто вероятностную природу, а имеют место детерминированные взаимосвязи
между ПМij, обусловленные структурой ГВП, хотя длительности выполнения самих ПМij на ЦПj и
НДДj являются случайными функциями. Во-вторых, в последовательности выполняемых
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
135
процессов, ПМij могут использовать ресурсы ЦПij и HДДj разных узлов ЛВС. Поэтому предлагается
использовать ГВП для имитации процесса появления запросов пользователей l-го типа на ресурсы
i-го типа j-ых узлов ЛВС.
В качестве базового элемента формализации ВП и РН на ЛВС вместо ПМij ,будем
использовать такое понятие, как микротехнологическая операция (МТХОij). Любой ТПОИ на ЛВС
представляется в виде ГВП на основе аппарата сетевого планирования. В общем виде
параметрами МТХОij могут быть следующие характеристики: расходы ресурсов ЦП ( )
ЦПijτ ;
расходы ресурсов HДД ( )
НДijV ; стоимость выполнения операции ( )ijС .
При этом предполагаются известными функциональные зависимости между расходом
ресурсов, стоимостью выполнения операции и времени их реализаций:
( )
ЦПijij τϕτ 1= , ( )cзjЦПij v,τ ; ( )
НДjНДijij vV ,2ϕτ = ; ( )
НДjcpijij vvC ,53ϕτ = .
Таким образом, в терминологии сетевого планирования на ГВП МТХОij соответствуют
действительным работам [10] или же ПМij при полумарковском представлении ВП в ЛВС [8].
Основными базовыми элементами вероятностного сетевого графика (ВСГ), отображающего
структуру рынка ЛВС, являются события (SOi). В соответствии с классическим определением
события на ВСГ каждое событие обладает следующими параметрами: номер события (i); ранние и
поздние сроки свершения событий (tРi и tПi); резерв свершения события (Ri). Вторым базовым
элементом ВСГ является понятие микротехнологической операции (МТХОij). В отличие от
традиционной технологии исследования сетевых графиков все параметры работ в предлагаемом
ниже подходе к исследованию ВСГ являются случайными величинами, задаваемыми
соответствующими функциями распределения F1 (τik); F2 (Vik); F3 (Сik). Поэтому каждая МТХОik
обладает следующими параметрами: ik – номера исходного (i) и завершающего работу событий (k);
F1 (τik); F2 (Vik); F3 (Сik). Будем называть времена выполнения МТХОik (τik) основными параметрами,
а остальные характеристики (Vik и Сik) являются вспомогательными. В соответствии с
традиционным представлением СГР необходимо указать j – номер узла ресурса ЦПj и HDDj,
которые используют для выполнения МТХОik . Таким образом, с помощью ВСГ и параметров
МТХОik задаются местонахождение ресурсов в ЛВС, длительности и стоимости их использования,
порядок их выполнения. Независимые друг от друга МТХОik выполняются параллельно, а
зависимые МТХОik запускаются только при свершении событий в моменты (tpi).
Определим понятие критического пути на ВСГ как последовательность МТХОik,
выполняемых на ресурсах различных узлов ЛВС, определяющего общее время свершения l-го
запроса пользователей ЛВС. Пример представления технологии реализации l-го запроса РН на
ЛВС в виде ВСГ приведен на рис. 1, а в табл. 1 указаны значения параметров МТХОik, из которых
составлен ВСГ реализации запроса пользователей l-го типа на ресурсы ЛВС, расположенных в
различных узлах ЛВС.
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
136
GENl
1 2
9
106 8
1243
5
7 11
POGl
MTXO12 MTXO26 MTXO68 MTXO8 10
MTXO10 12MTXO8 12
MTXO9 12
MTXO69
MTXO9 11
MTXO11 12
MTXO7 11
MTXO79
MTXO47
MTXO46
MTXO24MTXO13
MTXO14
MTXO35
MTXO34
MTXO57
λl
Рис. 1. Пример представления технологии реализации l-го запроса РН
на трех узлах ЛВС в виде вероятностного сетевого графика
Таблица 1. Значение вероятностных параметров МТХОik, реализуемых на узлах ЛВС по
технологии их выполнения, представленной на рис. 1
Номера
МТХОik
j- номера
узлов
ЛВС
F1(τik) M τik F2(Vik) MVik F3(Cik) M Cik
1.2 1 EXP (5,5) 10 PUA (50) 50 NOR (30,10) 30
1.3 2 NOR (15,10) 15 PUA (30) 30 NOR (40,10) 40
1.4 1 NOR (25,10) 25 PUA (40) 40 NOR (70,10) 70
3.4 2 EXP (5,5) 10 PUA (20) 20 NOR (90,10) 90
3.5 2 EXP (5,10) 15 PUA (10) 10 NOR (40,10) 40
2.6 3 NOR (17,20) 17 PUA (70) 70 NOR (30,10) 30
2.4 3 NOR (9,10) 9 PUA (20) 20 NOR (10,10) 10
4.7 3 EXP (5,5) 10 PUA (30) 30 NOR (10,10) 10
4.6 1 NOR (12,10) 12 PUA (30) 30 NOR (10,10) 10
5.7 3 NOR (15,10) 15 PUA (40) 40 NOR (10,10) 10
6.8 1 EXP (5,5) 10 PUA (50) 50 NOR (20,10) 20
6.9 1 EXP (5,3) 8 PUA (70) 70 NOR (30,10) 30
7.9 3 NOR (7,10) 7 PUA (90) 90 NOR (40,10) 40
7.11 2 NOR (12,10) 12 PUA (70) 70 NOR (70,10) 70
9.11 3 EXP (5,4) 9 PUA (30) 30 NOR (30,10) 30
8.10 1 NOR (17,10) 17 PUA (40) 40 NOR (90,10) 90
9.12 2 EXP (5,11) 16 PUA (90) 90 NOR (40,10) 40
11.12 3 EXP (5,5) 10 PUA (50) 50 NOR (50,10) 50
10.12 1 EXP (5,4) 9 PUA (40) 40 NOR (50,10) 50
8.12 1 EXP (5,5) 10 PUA (30) 30 NOR (30,10) 30
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
137
Если характеристики МТХОik постоянны, то аппарат сетевого планирования позволяет найти все
сроки свершения событий (tpi, tпi) и их резервы (Ri). Затем по известной методике [10]
рассчитываются значения параметров, выполняемых МТХОik: раннее начало (tрнik), позднее начало
(tПНik), раннее окончание (tПОik), позднее окончание (tпоik) МТХОik. Не представляет труда и поиск
критического пути (КРПs) для s-го варианта реализации запроса либо по временным, либо по
стоимостным показателям его выполнения. На рис. 2 и рис. 3 приведены примеры расчета
критического пути и резервов свершения событий при постоянных значениях (равным
математическим ожиданиям) соответственно по времени и стоимости выполнения МТХОik.
1
0
0
0
2
16
6
10
9
52
0
52
10
64
0
64
6
37
0
37
8
47
0
47
12
73
0
73
4
25
0
25
3
15
0
15
5
30
0
30 7
45
0
45
11
63
2
61
10 17
17
9
10
16
8
9
10
12
7
10
12
9
15
25
15
10
15
10
Рис. 2. Критический путь по времени реализации l-го запроса РН на ЛВС при постоянных значениях времени
выполнения МТХОik, равным математическим ожиданиям их распределений
1
0
0
0
2
110
80
30
9
220
10
210
10
250
0
250
6
140
0
140
8
160
0
160
12
300
0
300
4
130
0
130
3
40
0
40
5
180
100
80 7
170
30
140
11
250
10
240
30 30
90
50
30
40
30
30
50
70
40
10
10
10
40
70
40
90
10
20
Рис. 3. Критический путь в графе стоимостей реализации l-го запроса РН на ЛВС при постоянных значениях
стоимостей выполнения МТХОij, равным математическим ожиданиям их распределений
Любая МТХОik представлена ориентированными ребрами графа технологии обработки запросов
пользователей l-го типа на трех узлах ЛВС, а события изображаются в виде кружков, состоящих из
четырех секторов: в левом и правом секторах указаны соответственно tРi и tПi . В верхних секторах
приведены номера событий i, а в нижних секторах содержатся найденные резервы свершения
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
138
событий (Ri). Как следует из рис. 2 и рис. 3, критические пути по времени выполнения и стоимости
реализации на ЛВС запроса пользователей l-го типа совпали. Однако такое совпадение скорее
редкий случай. И уже совсем невозможно использовать аппарат календарного планирования для
случая, когда все параметры МТХОik являются случайными величинами. Вероятностный характер
сетевого графика, представленного на рис. 1, при произвольных типах распределений, указанных в
табл. 1, обуславливает необходимость постановки имитационных экспериментов (ИЭ) с
использованием процедур метода Монте-Карло. [11]. В таких случаях результат имитации
выполнения ВСГ при одних и тех же начальных значениях исследуемого ТПОИ также будет
вероятностным. Поиск же критических путей значительно усложняется по сравнению со случаем,
когда параметры МТХОik являются детерминированными величинами.
4. Расчет и анализ параметров ВСГ по методу Монте-Карло
Для решения проблем исследования вероятностных технологических процессов производства
(ТПП) с помощью ИМ был разработан программно-технологический комплекс имитации (ПТКИ)
ГПП [12]. Применение комплекса основано на формализации ГПОИ с помощью
модифицированного метода сетевого планирования и реализуется следующей
последовательностью этапов.
1. Запись параметров МТХОik, входящих в ВСГl реализации l-го типа запросов РН на ЛВС, в
информационную базу (ИБD) комплекса. При этом происходит преобразование описаний МТХОik во
внутреннее представление, контроль корректности описания ВСГl, вывод результатов этого
контроля на дисплей для устранения ошибок в описании ВСГl. Взаимодействие ПТКИ ТПП с
пользователем происходит на основе набора “меню” возможностей комплекса в режиме вопрос-
ответ. В итоге по завершении этого этапа синтаксические ошибки в ВСГl будут исправлены.
2. Расчет и анализ параметров ВСГl по методу Монте-Карло реализуется следующей
последовательностью шагов:
2.1. На s-ой реализации ВСГl ( 1=s , N ) разыгрываются все значения параметров МТХОik
( )iksiksiks CV ,,τ с помощью соответственно функций распределения ( ) ( ) ( )ikik CFVFF 321 ,,τ ,
представленных в табл. 1. В результате формируется s-я реализация ВСГl с детерминированными
параметрами МТХОik. (DСГς).
2.2. Моделируется выполнение ВСГs в режиме прямого изменения модельного времени t"0
при вычислении ранних сроков свершения событий ( )pist . Одновременно с этим моделируются
расход ресурсов ( )iksV и стоимости выполнения ( )iksC на реализацию МТХОik. Для вычисления
поздних сроков свершения событий ( )nist используется имитация с инверсным характером
изменения модельного времени t"0.
2.3. Рассчитываются резервы свершения событий Ris и типовые характеристики
напряженности выполнения работ при реализации ВСГl (tpнiks, tпнiks, tpoiks, tпoiks). Завершаются
расчеты характеристик s-ой реализации ВСГl по методу Монте-Карло нахождением критического
пути ДГСs (КРПsl) реализации l-го запроса на PH на ЛВС.
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
139
2.4. В результате имитации выполнения N реализаций ВСГl в ИБД комплекса будут
сформированы выборки значений параметров ВСГl для событий { }isgispis Rtt ,, для МТХОik
{ }isnispis Rtt ,, и для критического пути {КРПsl}. Таким образом, каждой s-ой реализации ВСГl в этих
выборках соответствуют s-ые номера параметров событий, МТХОik и критических путей КРПsl.
3. Оптимизация ВСГl по данным имитационного эксперимента (ИЭ) реализуется следующей
последовательностью шагов.
3.1. Формирование по выборкам функций распределений значений статистик имитации ВСГl
( )zF , математических ожиданий ( )zM и дисперсии )( zД . Здесь под z понимаются названия
перечисленных ранее характеристик выполнения МТХОik, сроков свершения событий и длины
критических путей в ВСГℓ.
3.2. Осуществляется анализ критических путей ВСГℓ. Каждый КРПsl представляет собой
последовательность МТХОik и событий SOBi, обладающих нулевым резервом времени их
свершения (Ril). В общем случае для N реализаций ВСГl может существовать множество {КРПsl}, в
котором только некоторые пары (SOBi , МТХОik) различные, а остальные пары не отличаются друг
от друга. Поэтому алгоритм анализа всех реализаций ВСГl представляет исследователю диапазон
различных событий, одновременно возникающих в ВСГl в одно и то же время t"0, и различных
реализаций {КРПśl} в ВСГl.
3.3. По результатам статистической обработки параметров {МТХОiks}, событий {SOBis} и
критических путей {КРПsl} исследователь может сформировать граф критических путей (GRКРПl),
используя для этой цели оценки вероятных значений коэффициентов напряженности МТХОik [10].
При этом определяется список событий, имеющих наибольшие резервы времени их свершения с
высокой вероятностью. Из этого списка выбираются МТХОik в качестве кандидатов для исключения
из графа критических путей.
3.4. Если множество {КРПsl}достаточно большое, то из него можно сформировать граф
критических путей (GR КПРl). В этом графе, состоящем из критических путей, могут появиться
вероятностные переходы (Рir) между уже обобщенными событиями OSOBir и OSOBr. Далее
реализуется процедура, аналогичная шагу 2, но с той лишь разницей, что анализу подвергается
уже граф критических путей. Очевидно, что придется осуществлять несколько итераций для
нахождения результирующего наиболее вероятного критического пути реализации l-го запроса РН
на ЛВС.
3.5. Информация, сформированная на каждом шаге этапа 3, хранится в ИБД ПТКИ ТПП и
может по запросу выводиться исследователю на экран дисплея в любом требуемом составе. Это
позволяет исследователю либо принять решение о завершении исследований, либо
корректировать в диалоговом режиме параметры МТХОik с учетом технологических ограничений на
их реализацию.
3.6. Меняются параметры модифицируемых МТХОik и осуществляется переход на
выполнение этапа 1. При этом возможно сравнение результатов, полученных на предыдущей
итерации, и принятие решений о завершении имитации выполнения ВСГl на ЛВС [12].
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
140
5. Методика имитационного моделирования распределенной обработки информации в ЛВС
Для имитации распределенной обработки информации в ЛВС в ПТКИ ТПП используется
транзактный способ представления структуры запросов l-го типа РН на ЛВС [13]. Для этой цели на
входе ИМ узлов ЛВС с помощью генератора транзактов GENl формируются информационные
транзакты (TRINl). В теле TRINl находится ВСГl реализации ТПОИ на ЛВС. GENl формирует на
входе j-го узла ЛВС TRINl c интенсивностью λl, которые затем обслуживаются моделью ВП в ЛВС.
Таким образом, на входе каждого узла ЛВС установлено столько GENl, сколько предусмотрено
типов запросов РН на узлах ЛВС в исследуемой технологии распределенной обработки запросов
пользователей на ресурсы ЛВС.
По информации, сосредоточенной в параметрах МТХОik и определяющей запросы
пользователей l-го типа на r-ом узле ЛВС на ресурсы узлов ЛВС, согласно ВСГl формируются
последовательности управляющих транзактов (UTRik), представляющие собой поток запросов на
ресурсы ЛВС. Каждый UTRikl представляет собой заказ к ОС ЛВС на ресурсы, в котором
указываются номер узла (j), на котором при выполнении МТХОijk ( ikC единиц стоимости), номер
выполняемой МТХОik (ik). Значения этих ресурсов разыгрываются при имитации выполнения ВСГl
по функциям распределения, представленным в табл 1.
Собственно выполнение очередной МТХОik (согласно графа ВСГl) имитируется на
устройствах обработки. При этом на j-ом узле может быть расходовано три типа ресурсов: ЦПj,
НДДj и МЕМj (здесь ЦПj , НДДj и МЕМj означают факт использования соответственно ЦП, НДД и
памяти j-го узла ЛВС). В рассматриваемой модели использования ресурсов ЛВС предусмотрен
монопольный захват ресурсов ЦПj и МЕМj и частичный захват ресурса НДДj объема ikV на время
выполнения МТХОik(τik). По завершении очередного выполнения МТХОik ресурсы j-го узла ЛВС
возвращаются и становятся доступными для очередного захвата следующей МТХОik. Времена
собственно реализации всех МТХОik при выполнении l-го запроса РН в общем случае
представляют сумму использования ресурсов узлов ЛВС:
tОЖseOЖНДДjОЖЦПjНДikцпikoswsetikl ττττττττ ++++++= .
где oswset ττ , – постоянные значения затрат времени соответственно на выполнение сетевых
операций по пересылке запросов пользователей l-го типа с r-го узла на выполнение на j-ом узле
ЛВС;
tОЖseOЖНДДjОЖЦПj τττ ,, – моделируемые значения времени ожидания запросов, сформированным по
инициативе UTRikl, на ресурсы j-го узла ЛВС (соответственно ЦПj, НДДj и устройства сетевого
доступа);
НДikцпik ττ , – конкретные значения времени использования ресурса ЦПj на НДДj, сформированные
по соответствующим функциям распределения из табл. 1.
В итоге по запросам UTRik на ИМ устройств обработки информации определяются значения
временных характеристик НДikцпikoswset ττττ ,,, . В очередях к ИМ устройств обработки UTRik
формируются суммарные времена ожидания освобождения ресурсов узлов ЛВС
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
141
( tОЖseOЖНДДjОЖЦПj τττ ,, ). Длительности выполнения сетевых операций )( setτ операционной системы
)( oswτ устанавливаются постоянными для конкретного варианта топологии ЛВС.
Динамику обслуживания TRINl и UTRik при выполнении s-ой реализации ВСГl можно
представлять следующим образом. Как только из TRINl определяется необходимость выполнения
МТХОik, формируется UTRik, который поступает к устройству j-го узла обработки. OSW j,
имитирующему выполнение управляющего модуля ОС ЛВС длительностью owsτ . Далее UTRik
поступает в очередь к ресурсу сетевого доступа (SETj), имитирующему пересылку запроса по сети
согласно заданной топологии ЛВС длительностью SETτ . Затем UTRik последовательно
обслуживается имитаторами основных ресурсов j-го узла ЛВС (ЦПj и НДДj). Для отображения
процесса монопольного захвата основных ресурсов j-го узла ЛВС используется система очередей
на их входе согласно обобщенной модели функционирования устройств обработки запросов на
ресурсы j-го узла, представленной на рис. 4.
POGU j
GEN l POG lUs M TXO j
λ l τ ОЖ T RIN l
τ ik l
TR IN l
GEN U j OSW SETj ЦП j НДД j
τ ОЖ OS τ OSW
τ ОЖ S ET j τ S ET j
τ ОЖ ЦП j τ ЦП j
τ ОЖ НДД j τ НДД j
UTR ik
Pusk GEN U j «Закрыть»
«Открыть»
USISP j
Рис. 4. Блок–схема связи устройства–имитатора IMITj выполнения МТХОik
с устройством–имитатором расхода ресурсов j-го узла ЛВС
После завершения обслуживания UTRik уничтожаются. В моменты освобождения устройства
обработки j-го узла ЛВС из входной очереди выбирается очередной UTRik и формируется сигнал
“Закрыть” устройство МТХОik, имитирующий начало выполнения МТХОik )( HIKt . В момент
уничтожения UTRik формируется сигнал “Открыть” устройство US МТХОik, имитирующий конец
выполнения МТХОik )( KIKt . Таким способом автоматически имитируется выполнение МТХОik
длительностью HIKKIKikl tt −=τ . Далее в случае, если очередь к устройству US МТХО не пустая,
выбирается из входной очереди следующий TRINl, формируется сигнал создания UTRik, по
которому из GENUj поступает UTRik во входную очередь к устройству обработки i-го узла ЛВС
(USISP) и весь цикл выполнения МТХОik парой транзактов TRINl и UTRik повторяется. На рис. 4
приведена обобщенная схема ИМ j-го узла ЛВС состояния из следующих процессов: генератора
TRINl (GENl), поглотителя TRINl (POGIl) генератора UTRik (GENUj), поглотителя UTRik (POGUl)
имитатора выполнения МТХОik (US МТХОik), имитаторов устройств – исполнителя (USISP) запросов
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
142
ресурсов ЛВС (OSWJ, SETJ, ЦПJ, НДДJ), которые связаны между собой системой входных очередей,
имитирующих функции ожидания UTRik захвата соответствующих ресурсов j-го узла ЛВС.
Предложенная технология обслуживания запросов РН l-го типа на ресурсы ЛВС зависит от
технологии сети. На рис. 5 приведены варианты компоновки ИМ технологии обработки информации
для технологий ЛВС типа “звезда”, когда ЛВС состоит из пяти узлов.
GENl1 POGIl
USMTXO1
λ1l
SET1
OSW1 ЦП1 НДД1
GENl2 POGI2
USMTXO2
λ2l
SET2
OSW2 ЦП2 НДД2
GENl5 POGI5
USMTXO5
λ3l
SET5
OSW5 ЦП5 НДД5
GENl4 POGI4
USMTXO4
λ4l
SET4
OSW4 ЦП4 НДД4
GENl3 POGI3
USMTXO3
λ3l
SET3
OSW3 ЦП3 НДД3
Рис. 5. Имитационная модель реализации ТПОИ в ЛВС
топологии «звезда», состоящая из пяти узлов
На рис. 5 не показаны генераторы и поглотители UTRikj устройств– имитаторов ВСГlj и
устройств-имитаторов выполнения запросов ресурсов узлов ЛВС (US МТХОj и USISPj.
6. Выводы
Изложенные методики имитации распределенной обработки в ЛВС обладают преимуществом в
использовании перед моделированием на основе полумарковских процессов для случаев
проектного моделирования ЛВС в тех случаях, когда реальная ЛВС еще не существует и решается
ISSN 1028-9763. Математичні машини і системи, 2004, № 3
143
задача выбора состава и размещения ресурсов узлов ЛВС, которые были бы адаптированы для
решения тех задач, которые преимущественно будут решаться на проектируемой ЛВС.
Полумарковский подход к представлению ИМ РН на ЛВС используется уже при наличии
действующей ЛВС и ставится задача перераспределения ресурсов узлов ЛВС при адаптации их к
РН на ЛВС.
СПИСОК ЛИТЕРАТУРЫ
1. Зайченко Ю.П., Зайченко Е.Ю., Поспелов И.В. Комплекс программ анализа и синтеза структуры
региональных и глобальных вычислительных сетей // УСиМ. – 2000. – № 5/6. – С. 71 – 87.
2. Зайченко Е.Ю. Анализ структуры глобальных вычислительных сетей. – Киев: ЗАО “Укрспецнонтпроект”,
1998. – С. 108.
3.Kovalenko I.N., Kuznetsov N.Y., Pegg Ph.A. Mathematical theory of
reliability of time-dependent systems, with practical applications. – Chichester: J.Wiley and Sons, 1997. – 303 p.
4.Коваленко И.Н., Наконечный А.Н. Приближенный расчет и оптимизация
надежности. – К.: Наукова думка, 1989. – 182 с.
5. Демиденко О.М., Максимей И.В., Агеенко И.В. и др. Имитационное моделирование вычислительного
процесса в узлах локальной сети // УСиМ. – 2000. – № 5/6. – С. 101 – 107.
6. Демиденко О.М., Максимей И.В. Проектное моделирование вычислительного процесса в локальных
вычислительных сетях. – Мн.: Белорусская Наука, 2001. – С. 252.
7. Демиденко О.М., Максимей И.В. Влияние конкуренции запросов пользователей за ресурсы вычислительной
системы на организацию вычислительного процесса // Математические машины и системы. – 2001. – № 2. –
С. 3 – 9.
8. Демиденко О.М. Технология мониторинга и адаптации вычислительного процесса под рабочую нагрузку на
локальную вычислительную сеть. – Мн.: Белорусская наука, 2002. – С. 193.
9. Литвинов В.В., Марьянович Т.П. Методы построения имитационных систем. – К.: Наукова думка, 1991. –
117 с.
10. Жогаль С.И., Максимей И.В. Задачи и модели исследования операций. – Ч. 1: Аналитические модели
исследования операций: Уч. пособие. – Гомель: БелГУТ, 1999. – С. 109.
11. Максимей И.В., Серегина В.С. Задачи и модели исследования операций. – Ч. 2.: Методы нелинейного и
стохастического программирования: Уч. пособие. – Гомель: БелГУТ, 1999.- С. 103.
12. Максимей И.В., Левчук В.Д., Маслович С.Ф. и др. О проблемной модификации программно-
технологического комплекса имитации технологических процессов производства // Известия Гомельского
государственного университета имени Ф. Скорины. – 2003. – № 3(18). – С. 38 – 41.
13. Максимей И.В., Левчук В.Д., Жогаль С.П. Задачи и модели исследования операций. – Ч. 3: Технология
имитации на ЭВМ и принятие решений: Уч. пособие. – Гомель: БелГУТ, 1999. – 150 с.
|