close

Вход

Забыли?

вход по аккаунту

?

«Соревнования» в многопроцессорных компьютерных системах.

код для вставкиСкачать
УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 519.217.2
Е.В. Ларкин, д-р техн. наук, проф., зав. кафедрой, elarkin@mail.ru
(Россия, Тула, ТулГУ),
А.Н. Ивутин, канд. техн. наук, доц., alexey.ivutin@gmail.com
(Россия, Тула, ТулГУ)
«СОРЕВНОВАНИЯ» В МНОГОПРОЦЕССОРНЫХ
КОМПЬЮТЕРНЫХ СИСТЕМАХ
Рассмотрены вопросы исследования процессов в параллельных системах, в частности определениям времени ожидания уже завершившимися элементарными процессами, еще не завершенных процессов (эффект «соревнования»).
Ключевые слова: сеть Петри-Маркова, полушаг, «соревнования», функция распределения
Теория сетей Петри является хорошо известным и популярным
формализмом, предназначенным для работы с параллельными и асинхронными системами. Одним из основных направлений использования теории
сетей Петри является формальное описание и моделирование параллельных систем. Ключевым вопросом данной области является вопрос выполнимости и корректности модели. При создании параллельных систем необходимо выполнение условия гибкости модели и возможность
выполнения строго анализа ее свойств.
При построении моделей сложных систем со множеством состояний и переходов обязательным условием остаётся учёт таких её свойств
как: случайность времени выполнения операции, возможность одновременного выполнения групп операторов, а также стохастический характер
198
Управление, вычислительная техника и информационные технологии
переходов. Для учета всех основных особенностей систем такого типа в
наибольшей степени подходит математический аппарат сетей ПетриМаркова (СПМ) [1]. Идеальным инструментарием для анализа взаимодействия процессов в системах являются сети Петри, однако, являясь асинхронными по определению, модели указанного типа позволяют лишь ответить на вопросы о принципиальной достижимости состояний системы,
соответствующих заданным требованиям, но спрогнозировать моменты
наступления тех или иных состояний с помощью сетей Петри, в их классической интерпретации невозможно. Рядом авторов предпринимались попытки приспособить сети Петри для определения временных интервалов
(time extended Petri nets), однако даже в модифицированном варианте они
не позволяют учитывать все многообразие взаимодействий в системах исследуемого класса. Кроме того, ограничения в моделировании параллельных процессов с помощью сетей Петри заключаются в ограниченности логических условий продолжения процессов элементарной конъюнкцией,
что не учитывает всего многообразия взаимодействий субъектов.
Наиболее полно учет такого свойства, как параллельное развитие
стохастических взаимодействующих процессов во времени, может быть
осуществлено в Петри-Марковских моделях, в которых алгоритмы функционирования отдельных субъектов представляются в виде элементарных
подсетей Петри-Маркова с полумарковскими свойствами, а взаимодействие моделируется с помощью т.н. непримитивных переходов, для которых
определяется логическая функция взаимодействия [2]. Таким образом, в
моделях исследуемого типа на структуры, учитывающие параллелизм, накладываются стохастические и временные параметры элементарных полумарковских процессов и логические условия, замыкающие корпоративноконкурентный алгоритм функционирования системы. В целом модели,
сформированные подобным образом, являются естественным аналитическим описанием алгоритма, реализованного в параллельной системе с известной структурой. Степень дробления алгоритма на операторы позволит
достаточно просто оценивать временные и вероятностные характеристики
элементарных процессов, представленных соответствующими операторами, а также логику взаимодействия процессов в корпоративноконкурентной среде [3].
Параллельно функционирующие компоненты конкурентных систем
во временной области вступают в «соревнование», одним из аспектов которого является эффект ожидания момента наступления некоторой совокупности событий. Исследование соревнования связано с определением
времени ожидания уже завершившимися элементарными процессами, еще
не завершенных процессов. Любое соревнование может быть сведено к соревнованию двух процессов, которое моделируется сетью Петри, приведенной на рис. 1. В указанной сети позиции {ϕ, ψ} представляют собой модели соревнующихся процессов [4].
199
Управление, вычислительная техника и информационные технологии
и в общем случае f ϕ→ ψ (t ) ≠ f ψ → ϕ (t ) .
В часто встречающемся практическом случае K процессов разбиваются на две группы. Не нарушая степени общности, будем считать, что
первая группа имеет номера с первого по N-й, а вторая группа - с (N + 1)-го
по K-й. Плотности распределения времени выполнения соответствующих
групп процессов определяются зависимостями, получаемыми из (3):
N
N
m =1
k =1
k ≠m
f1↔ N (t ) = ∑ fˆ j ( mz ) j ( zn ) (t )∏ Fˆ j (kz ) j ( zn ) (t ) ,
K
K
m = N +1
k = N +1
k ≠m
(6)
f N +1↔ K (t ) = ∑ fˆ j ( mz ) j ( zn ) (t ) ∏ Fˆ j ( kz ) j ( zn ) (t ) ,
(7)
Плотности распределения времени ожидания первой группой момента, когда завершатся процессы второй группы, определяется зависимостью
∞
1(t ) ∫ f1↔ N (τ) f N +1↔ K (t + τ)dτ
0
∞
f (1↔ N )→( N +1↔ K ) (t ) =
.
(8)
∫ F1↔ N (t ) dFN +1↔ K (t )
t =0
Плотность распределения времени ожидания второй группой момента, когда завершатся процессы первой группы, определяется зависимостью
∞
1(t ) ∫ f N +1↔ K (τ ) f1↔ N ( t + τ )d τ
f (N +1↔ K )→ (1↔ N )( t ) =
0
∞
.
(9)
∫ FN +1↔ K ( t ) dF1↔ N ( t )
t =0
Однако следует отметить, что такой подход достаточно трудоемок
при большом числе заявок, кроме того, не позволяет учесть перекрестное
влияние заявок. В связи с этим предлагается способ ранжирования заявок,
лишенный описанного недостатка. Пусть в соревнование вступают N
процессов, с функцией вероятностей F(x) и плотностью распределения f(x)
(рис. 2).
Как отмечалось выше, для сети Петри логическое условие
выполнения полушага имеет вид элементарной конъюнкции (2, 3) и лишь в
этом случае вероятность f(x) имеет вид плотности распределения, т.е.
выполняется условие
d ∫ f ( x − m ) F ( x )dx
> 0.
(10)
dm
Рассматриваемые процессы являются независимыми, следовательно
вероятность того, что первый процесс будет находится в заданной позиции
201
Известия ТулГУ. Технические науки. 2012. Вып. 12. Ч. 2
определяется зависимостью
N
F(1) = 1 − ∏ (1 − Fn ) ,
(11)
n =1
где Fn —функция распределения времени изъятия n-й фишки из заданной
позиции.
Рис. 2. Функция и плотность распределения для задачи «соревнования»
N процессов
Из (12) может быть получена плотность распределения
N
N
dF(1)
= ∑ f k ∏ (1 − Fn ) .
dx
k =1 n =1
(12)
n ≠k
Взвешенная плотность распределения определяется зависимостью
N
f1 ∏ (1 − Fn ) .
n=2
Тогда, вероятность
определяется как
того,
∞
что
первым окажется k-й
N
pk = ∫ f k ∏ (1 − Fn ) .
0
процесс
(13)
n =1
n ≠k
В этом случае плотность распределения того, что первой в
«соревновании» придет заявка k определяется зависимостью:
N
f k ∏ (1 − Fn )
n =1
n ≠k
'
fk =
,
∞
N
∫ f k ∏ (1 − Fn )
0 n =1
n ≠k
202
(14)
Управление, вычислительная техника и информационные технологии
а математическое ожидание равно:
∞
Tk' = ∫ t ⋅ f k' dt .
(15)
0
Таким образом, повторяя данный алгоритм, последовательно
исключая лидеров может быть получен полный ранжированный список
процессов, участвующий в «соревновании».
Список литературы
1. Ларкин Е.В., Сабо Ю.И. Сети Петри-Маркова и отказоустойчивость авионики. Тула: Тул. гос. ун-т., 2004. 208 с.
2. Ларкин Е.В. Формирование сетей Петри-Маркова для моделирования параллельных систем //Математическое и программное обеспечение
вычислительных систем. М. Горячая линия-Телеком, 2006. С. 4 - 8.
3. Применение сетей Петри-Маркова при моделировании структурных отказов в системе // Известия ТулГУ. Сер. Вычислительная техника.
Информационные технологии. Системы управления. Вып. 4. Т. 3: Системы
управления. Тула: ТулГУ, 2003. С. 95 -103.
4. Формирование сетей Петри-Маркова для моделирования параллельных систем // Математическое и программное обеспечение вычислительных систем. М. Горячая линия-Телеком, 2006. С. 4 - 8.
E.V. Larkin, A.N. Ivutin
"COMPETITIONS" IN MULTIPROCESSOR COMPUTER SYSTEMS
The problems of the study of processes in parallel systems, in particular the
definitions of the waiting time has already completed the elementary processes that have not
yet completed process (effect of "competition") are reviewed.
Key words: Petri-Markov nets, half-step, “competition”, distribution function.
Получено 20.11.12
203
Документ
Категория
Без категории
Просмотров
3
Размер файла
404 Кб
Теги
многопроцессорных, соревнований, система, компьютерные
1/--страниц
Пожаловаться на содержимое документа