Моделирование работы узла grid-системы на основе сетей Петри
Обчислювальний вузол Grid-системи досліджується із застосуванням апарату мереж Петрі. Побудовано модель роботи вузла та досліджено її структурні властивості, зокрема показано, що побудована мережа є обмеженою, живою та не містить недосяжних позицій. Для побудованої моделі проведено аналіз існування...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2008 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/209093 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Моделирование работы узла grid-системы на основе сетей Петри / А.Ю. Шелестов // Проблемы управления и информатики. — 2008. — № 1. — С. 104-113. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860221682881396736 |
|---|---|
| author | Шелестов, А.Ю. |
| author_facet | Шелестов, А.Ю. |
| citation_txt | Моделирование работы узла grid-системы на основе сетей Петри / А.Ю. Шелестов // Проблемы управления и информатики. — 2008. — № 1. — С. 104-113. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Обчислювальний вузол Grid-системи досліджується із застосуванням апарату мереж Петрі. Побудовано модель роботи вузла та досліджено її структурні властивості, зокрема показано, що побудована мережа є обмеженою, живою та не містить недосяжних позицій. Для побудованої моделі проведено аналіз існування властивостей взаємного виключення та рівноправ’я.
Processing node of the Grid system was investigated using Petri network approach. The model of the working node was constructed and its structural properties were investigated. In particular, it was shown, that constructed network is bounded, living and hasn’t the inaccessible places. For constructed model the feasibility analysis of the mutex and fairness properties was also performed.
|
| first_indexed | 2025-12-07T18:18:44Z |
| format | Article |
| fulltext |
© А.Ю. ШЕЛЕСТОВ, 2008
104 ISSN 0572-2691
УДК 681.63; 519.872
А.Ю. Шелестов
МОДЕЛИРОВАНИЕ РАБОТЫ УЗЛА
GRID-СИСТЕМЫ НА ОСНОВЕ СЕТЕЙ ПЕТРИ∗
Введение
Бурное развитие вычислительной техники и систем телекоммуникаций, со-
провождающееся усложнением инфраструктуры распределенных информацион-
но-аналитических систем, привело к необходимости развития средств и методов
моделирования подобных систем. Одна из наиболее активно развиваемых техно-
логий создания распределенных систем — Grid-технология, направленная на
обеспечение работы виртуальных организаций, решающих вычислительно слож-
ные задачи с использованием распределенных хранилищ данных и мощных вы-
числительных ресурсов [1].
Для моделирования подобных систем используют различные подходы, ни
один из которых не может обеспечить исчерпывающее описание, но каждый из
них представляет лишь один из аспектов функционирования или структуры си-
стемы. Достаточно полный обзор существующих моделей разного уровня аб-
стракции содержится в [1–3]. В данной работе для моделирования динамики та-
ких систем предлагается использовать математический аппарат сетей Петри [4],
поскольку Grid-система представляет собой набор взаимодействующих компо-
нентов (вычислительных узлов и хранилищ данных), которые могут функциони-
ровать параллельно и в работе которых должна быть обеспечена синхронизация.
Особое значение такие модели приобретают при исследовании Grid-систем
наблюдения Земли, поскольку в этих системах особое внимание уделяется синхро-
низации доступа к общим сегментам данных и распараллеливанию вычислений.
1. Предметная область и требования к модели
Grid-система представляет собой распределенную систему доступа и обра-
ботки данных, состоящую из таких основных компонентов.
1. Пользователи, формирующие запросы к системе.
2. Узлы, которые могут быть вычислительными узлами, выполняющими об-
работку данных, либо хранилищами данных. В качестве вычислительных узлов
могут рассматриваться однопроцессорные или многопроцессорные компьютеры
(в том числе мощные кластеры), а также распределенные вычислительные
устройства (например, Grid-кластеры — объединения вычислительных устройств
под управлением Grid). Хранилища данных обеспечивают кратковременное или
долговременное хранение данных, а также предоставляют доступ к ним. При этом
информация может либо находиться в распределенных базах данных, архивах или
реестрах, либо локализоваться в общей памяти (в случае многопроцессорной си-
стемы с общей памятью). В простейшем случае хранилищем может служить од-
нопроцессорный вычислительный узел (например, персональный компьютер) и
данные могут располагаться в его памяти.
3. Управляющие узлы (или планировщики). Это необходимый элемент каж-
дой Grid-системы, отвечающий за распределение заданий между ресурсами и
отыскание необходимых данных в распределенных хранилищах. Без этого эле-
∗ Работа выполнена в рамках темы НАН Украины «Интеллект» при поддержке гранта INTAS–
CNES–NSAU «Data Fusion Grid Infrastructure» (Ref. Nr 06-1000024-9154).
Проблемы управления и информатики, 2008, № 1 105
мента система теряет свойства Grid и перестает быть прозрачной для пользовате-
ля. Планировщики могут быть локальными и управлять конкретным вычисли-
тельным узлом или глобальными и отвечать за распределение задач и поиск ре-
сурсов среди всех компонентов системы.
Задача состоит в построении Grid-системы, обеспечивающей прозрачную для
пользователя обработку его запросов на поиск и обработку данных, в том числе
синхронизацию доступа к необходимым данным, обработку этих данных и предо-
ставление пользователю результатов обработки. Такая Grid-система относится к
Grid-системам смешанного типа — она одновременно и вычислительная, и ин-
формационная [1], поскольку содержит высокопроизводительные вычислитель-
ные узлы и обеспечивает доступ к данным распределенных хранилищ [3].
Синхронизация доступа к данным и их корректная обработка предполагает
наличие некоторых базовых свойств, а именно:
взаимное исключение (mutex) — синхронизация событий при обработке дан-
ных: два или более вычислительных узла не могут одновременно иметь доступ к
общей области данных;
равноправие (fairness) — отсутствие дискриминации заданий, т.е. если поль-
зователь сформировал запрос (задание) и отправил его в систему, то обязательно
наступит момент, когда это задание начнет выполняться и будет выполнено;
отсутствие тупиков (deadlock free) — в системе не может возникнуть ситу-
ация взаимной блокировки вычислений или доступа к данным (общим или рас-
пределенным).
Работу Grid-системы смешанного типа без детализации иллюстрирует рис. 1.
При отправке запроса пользователя в систему он попадает на управляющий
узел (УУ) — маршрутизатор, который выполняет распределение этого задания
между ресурсами системы (вычислительными узлами) и определяет местонахож-
дение необходимых данных. На рис. 1 вычислительные узлы и хранилища данных
показаны в виде элемента Узел. Этот же УУ обеспечивает синхронизацию при
распараллеливании задания между ресурсами или при выполнении операций до-
ступа к общей памяти.
С учетом высокой стоимости компонентов Grid-систем, прежде чем при-
ступать к созданию системы, обладающей указанными свойствами, необходимо
построить ее модель и исследовать ее свойства. Построим модель функциони-
рования вычислительного узла, работающего над общей памятью, и исследуем
свойства этой модели. Учитывая специфику работы Grid-системы и необходи-
мость синхронизации доступа к общим сегментам данных при организации парал-
лельных вычислений, для моделирования воспользуемся математическим аппара-
том сетей Петри.
Узел Узел Узел Узел Узел Узел
УУ УУ УУ
Запросы
Пользователи
Рис. 1
106 ISSN 0572-2691
2. Сети Петри. Основные определения
Введем основные понятия, связанные с моделированием распределенных си-
стем для разделения ресурсов с помощью сетей Петри (СП).
Определение 1. СП (согласно [4]) называется четверка элементов
C = (P, T, I, O), (1)
где P — конечное множество позиций, T — конечное множество переходов,
I — функция входов (отображение множества переходов во входные позиции),
O — функция выходов (отображение множества переходов в выходные позиции),
,0},,,,{ 21 >= npppP n (2)
,0},,,,{ 21 >= ntttT m (3)
,: PTI → (4)
.: PTO → (5)
Если ),( ji tIp = то ip — входная позиция j-го перехода; если ),( ji tOp = то
ip — выходная позиция j-го перехода.
Для наглядного представления СП используются графы.
Определение 2. СП — это двудольный ориентированный мультиграф
).,( AVG = (6)
В (6) },,,{ 21 nmuuuV += — множество вершин, },,,{ 21 raaaA = — ком-
плект направленных дуг (комплектом, согласно [4], называется множество, со-
держащее многократно повторяющиеся элементы). Вершинами графа служат не-
пересекающиеся множества позиций Р и переходов Т СП: V = P ∪ T, причем
P ∩ T = ∅. Направленные дуги соединяют связанные между собой позиции и пе-
реходы.
Определение 2 дает возможность наглядного графического представления
СП, на основе которого можно сформулировать еще одно определение СП, кото-
рое и будет использоваться в дальнейшем при исследовании свойств сети.
Определение 3. СП называется тройка элементов
C = (P, T, A), (7)
где Р и Т — множества позиций и переходов СП соответственно, А — матрица
инцидентности графа сети, связывающая позиции с переходами сети.
Если элемент ,0=ijA то i-я позиция и j-й переход не связаны между собой;
если ,0>= kAij то в результате запуска j-й перехода в i-й позиции добавляется
k фишек; если ,0<= kAij то в результате запуска j-й перехода из i-й позиции
убирается k фишек.
Разметкой СП µ называется присвоение фишек позициям сети (более строгое
определение см. в работе [4)].
Определение 4. Разметка µ СП C = (P, T, I, O) представляет собой функцию,
отображающую множество позиций на множество натуральных чисел:
.: NP →µ (8)
Проблемы управления и информатики, 2008, № 1 107
Разметку можно также определить как вектор
},,,,{ 21 nµµµ=µ (9)
где n — мощность множества позиций, ,Ni ∈µ .,,1 ni = Вектор µ определяет
для каждой позиции ip сети количество фишек в этой позиции .iµ
На графе разметка отображается соответствующим количеством точек в каж-
дой позиции. Точки называются маркерами, или фишками. Если фишек много
(больше трех), то их количество отображается числом.
3. Модель работы узла в виде СП
Модель работы вычислительного узла с четырьмя процессорами, обрабаты-
вающего задания пользователя под управлением планировщика в соответствии с
общей схемой (см. рис. 1), показана на рис. 2. Эта модель представляет собой од-
ноцветную СП вида (7), начальное состояние которой описывается разметкой
0M = (Proc, Want, Query, Block, Free, Busy, Wait, Work) = (4, 0, 0, 1, 1, 0, 0, 0).
Позиции и переходы в данной СП имеют следующую семантику:
Proc — свободные в данный момент времени процессоры;
Query — запрос на выполнение задания от пользователя;
Want — процессор активен и может начать работу;
Work — процессор получил доступ к общей памяти и выполняет вычисления;
Wait — активный процессор ожидает доступа к общей памяти;
Block — блокируется доступ к общей памяти и очереди ожидания, если они
заняты другими процессорами;
Free — УУ сигнализирует о снятии блокировки общей памяти;
Busy — УУ сигнализирует о том, что общая память заблокирована для
доступа.
Пользователи
УУ
treq
t6
t5
t4 t2
t3
t1
Proc Узел
Want
Work
Wait
Busy
Free
Block
Query
Рис. 2
При начальной разметке 0M = (4, 0, 0, 1, 1, 0, 0, 0) система находится в со-
стоянии покоя (который иногда называют состоянием сна). Из семантики позиций
следует и смысл переходов:
reqt — наличие запроса на обработку данных;
1t — один из свободных процессоров готов работать;
108 ISSN 0572-2691
2t — процессор получает доступ к общей памяти;
3t — активный процессор переходит в состояние ожидания;
4t — процессор завершил работу с общей памятью и она разблокирована;
5t — активный процессор из состояния ожидания переходит в состояние ра-
боты с общей памятью, при этом одновременно происходит разблокирование пе-
рехода активного процессора в состояние ожидания.
Переход 6t и позиция без наименования между переходом 3t и 6t введены в
результате модификации структуры СП и преобразования полуцикла в цикл. Это
сделано во избежание неоднозначностей в процессе последующего анализа сети.
При появлении запроса пользователя на выполнение задания срабатывает
сначала один из переходов ,reqt а затем переход .1t В результате этого один из
свободных процессоров переходит в состояние активности (готовности к работе),
т.е. в позицию Want. Если одновременно поступает два запроса, то выполнение
одного из них будет задержано отсутствием маркера в позиции Block. Дальней-
шая работа модели очевидна.
4. Исследование структурных свойств модели
Рассмотрим определения некоторых основных свойств СП.
Определение 5. Переход t живой, если он срабатывает при запуске сети из
любой начальной разметки:
.:)( tNR →µ∈µ∀
СП жива (активна), если живой (активный) каждый ее переход:
.)(:))(&( tpNRTtt →µ∈µ∈µ∀∀
Определение 6. Если существует разметка (маркировка) сети, из которой пе-
реход it никогда не запускается, то этот переход называется мертвым.
Определение 7. Для сети C = (P, T, I, O) разметка µ′ называется непосред-
ственно достижимой из µ, если существует такой переход ,Tt j ∈ при котором
результатом запуска перехода jt служит разметка :µ′
.),( µ′=µδ jt
На основе определения 7 можно сформулировать определения достижимой и
недостижимой позиций.
Определение 8. Позиция ip называется достижимой, если для любой началь-
ной разметки существует последовательность переходов, приводящая к тому, что
.0)( >µ ip
Определение 9. Если
,0)(:))(&(: =µ∈µ∈µ∀∀∃ ii pNRTttp
то позиция ip называется недостижимой.
Сначала исследуем структурные свойства построенной на рис. 1 СП, а имен-
но проверим выполнение свойства ограниченности, удостоверимся в отсутствии
мертвых (лишних) переходов и недостижимых позиций. Для подтверждения до-
стижимости всех позиций сети и доказательства ее активности необходимо по-
строить S- и T-инварианты сети.
Проблемы управления и информатики, 2008, № 1 109
S-инвариант — это линейное отношение на разметке подмножества позиций,
выражающееся в том, что сумма различных меток в позициях положительна. Если
в S-инвариант входят все позиции СП, то в построенной модели все позиции до-
стижимы. Т-инвариант соответствует последовательности срабатывания перехо-
дов, переводящей сеть из разметки М в ту же самую разметку М [5]. Если Т-ин-
вариант включает все переходы сети, то она жива.
Для определения S- и T-инвариантов сети построим целочисленную (n × m)-
матрицу инцидентности СП А (табл. 1), где n и m — мощности множеств Р и Т
соответственно. В матрице А: элемент ,1=ijA если при выполнении перехода j
фишка добавляется в позицию i; ,1−=ijA если при выполнении перехода j фиш-
ка убирается из позиции i; ,0=ijA если при выполнении перехода j количество
фишек в позиции i не изменяется.
Таблица 1
Позиции
Переходы
t0 t1 t2 t3 t4 t5 t6
Query 1 −1 0 0 0 0 0
Proc 0 −1 0 0 1 0 0
Block 0 −1 1 0 0 1 0
Want 0 1 −1 −1 0 0 0
Wait 0 0 0 1 0 −1 0
Work 0 0 1 0 −1 1 0
Free 0 0 −1 0 1 −1 0
Busy 0 0 1 −1 −1 1 1
Users −1 0 0 0 1 0 0
Dop 0 0 0 1 0 0 −1
Утверждение. Представленная на рис. 2 СП, которая описывает модель
функционирования вычислительного узла Grid-системы, ограниченная, живая и
не содержит недостижимых позиций.
Доказательство. Воспользуемся уравнением состояний
,0=Ax (10)
где А — целочисленная (n × m)-матрица инцидентности СП, n и m — мощности
множеств Р и Т соответственно, х — m-мерный вектор Париха [6]. С помощью
уравнения состояния (10) определим S- и T-инварианты СП. Это и даст возмож-
ность выявить мертвые переходы, недостижимые позиции и проверить ограни-
ченность сети.
Размерность матрицы инцидентности А в (10) для рассматриваемой СП со-
ставляет 10 × 7 (10 уравнений, 7 неизвестных), а вектора Париха х — 7. В соответ-
ствии с данными табл. 1, матрица инцидентности для этой СП имеет следующий
вид
−
−
−−
−−
−
−
−−
−
−
−
=
1001000
0010001
1111100
0110100
0110100
0101000
0001110
0100110
0010010
0000011
A .
110 ISSN 0572-2691
Для получения множества S- и T-инвариантов СП используется TSS-алго-
ритм [7, 8], который позволяет построить минимальную порождающую систему
решений однородной системы линейных диофантовых уравнений над множе-
ством натуральных чисел N.
Согласно [7, 8], TSS-алгоритм позволяет сгенерировать множество S- или
T-инвариантов. Входными данными алгоритма служат матрица системы S раз-
мерности qp × (p строк и q столбцов) с начальным множеством решений М. Ра-
бота TSS-алгоритма на языке псевдокода описывается следующим образом.
TSS(M, p, q, S)
begin
if M=∅ then M={e|e is canonical vector of Nq};
for i:= 1 to p do
(M:=TSS1(M, Li(x));
if M=∅ then (print (“NO SOLUTION”); STOP)
else CLEAN(M)
print(M)
end
TSS1(M, L(x))
begin
M0=∅; M+:=∅; M–:=∅;
forall e∈M do
(if SCP(e, L(x)) = 0 then M0:= M0∪ {e} else
if SCP(e, L(x)) > 0 then M+:= M+∪ {e} else M–:= M–∪ {e});
M':=M0;
if M+≠ ∅ ∧ M–≠ ∅ then
(forall u∈M+ do
(forall v∈M– do
e:=–L(v)u+L(u)v; M':= M'∪ {e}))
return(M')
end
В приведенном фрагменте псевдокода функция qiqiii xaxaxaxL +++= 2211)(
представляется вектором ),,,,( 21 iqii aaa SCP(x, y) означает скалярное произве-
дение векторов x и y, а процедура чистки CLEAN(M) удаляет лишние решения.
В соответствии с TSS-алгоритмом система диофантовых уравнений (10) име-
ет два решения:
.}0,1,1,1,0,1,1{,}0,0,1,0,1,1,1{ T
2
T
1 == xx
На основе решений этой системы можно построить T-инварианты (табл. 2).
Таблица 2
t0 t1 t2 t3 t4 t5 t6
1 1 1 0 1 0 0
1 1 0 1 1 1 1
Поскольку в табл. 2 нет ни одного столбца, содержащего только нулевые
элементы, то все переходы в СП живые при данной начальной разметке, т.е. каж-
дый переход в сети срабатывает хотя бы один раз. Несложно удостовериться, что
это свойство выполняется и для других возможных начальных разметок (варьиро-
ваться может количество фишек во входных позициях сети). Следствие этого
факта — отсутствие тупиков, т.е. в системе не может возникнуть ситуации взаим-
ной блокировки вычислений или доступа к данным (общим или распределенным).
Проблемы управления и информатики, 2008, № 1 111
Действительно, тупик возникает в СП, если нельзя запустить один или несколько
переходов. Поскольку все переходы живые (активные), то СП обладает третьим
требуемым свойством — в ней отсутствуют тупики.
Сгенерируем S-инварианты данной СП. Для этого найдем решения системы
уравнений
,0T =yA (11)
где А — целочисленная (n × m)-матрица инцидентности СП, Т — символ транспо-
нирования матрицы, y — n-мерный вектор.
Система диофантовых уравнений (11), содержащая 7 уравнений и 10 неиз-
вестных, имеет следующие решения:
,}0,0,0,1,1,0,0,0,0,0{ T
1 =y
,}0,0,0,0,0,1,1,1,0,0{ T
2 =y
,}0,0,0,0,1,1,1,0,1,0{ T
3 =y
,}0,1,0,0,1,1,1,0,0,1{ T
4 =y
,}1,0,1,1,0,0,0,0,0,0{ T
5 =y
,}1,0,1,0,0,1,1,0,1,0{ T
6 =y
.}0,1,0,0,1,1,1,0,0,1{ T
7 =y
Решения матрично-векторного уравнения (11) определяют S-инварианты СП
(табл. 3).
Таблица 3
Query Proc Block Want Wait Work Free Busy Users Dop
0 0 0 0 0 1 1 0 0 0
0 0 1 1 1 0 0 0 0 0
0 1 0 1 1 1 0 0 0 0
1 0 0 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 1
0 1 0 1 1 0 0 1 0 1
1 0 0 1 1 1 0 0 1 0
Из табл. 3 следует, что СП — ограниченная, поскольку все позиции в ней со-
ответствуют положительным инвариантам. Это означает, что ни в одной позиции
сети не может скапливаться бесконечное количество фишек. Из табл. 3 также
следует, что все позиции в сети достижимы, т.е. модель не содержит лишних по-
зиций.
Таким образом, модель вычислительного узла в виде СП живая, ограничен-
ная и все позиции в сети достижимы.
Утверждение доказано.
5. Исследование выполнимости свойств взаимного
исключения и равноправия
При доказательстве утверждения показано, что модель вычислительного узла
Grid-системы в виде СП обладает основными структурными свойствами подобных
моделей: ограниченностью, достижимостью и активностью (живостью), а сеть ха-
рактеризуется отсутствием тупиков, т.е. третье из базовых свойств моделей син-
112 ISSN 0572-2691
хронизации доступа к данным выполняется. Для исследования выполнимости
свойств взаимного исключения (mutex) и равноправия (fairness) необходимо по-
строить транзиционную систему [9], или граф достижимых разметок СП.
Для начальной разметки, определяемой соотношением
М0 = (Proc, Want, Query, Block, Free, Busy, Wait, Work) = (4, 0, 3, 1, 1, 0, 0, 0),
вид транзиционной системы СП, показанной на рис. 2, иллюстрирует рис. 3.
∗
(4, 0, 0, 1, 1, 0, 0, 0)
(3, 0, 0, 1, 0, 1, 0, 1)
t 4
(3, 0, 0, 0, 1, 0, 1, 0)
(2, 0, 0, 0, 0, 1, 1, 1)
t 5
t 4
(2, 1, 0, 0, 0, 1, 0, 1)
(3, 0, 1, 1, 0, 1, 0, 1)
t 3
t 1
(4, 0, 0, 1, 1, 0, 0, 0)
(3, 0, 0, 1, 0, 1, 0, 1)
t 1
(3, 0, 0, 0, 1, 0, 1, 0)
(2, 0, 0, 0, 0, 1, 1, 1)
t 2
t 1
(2, 1, 0, 0, 0, 1, 0, 1)
(3, 0, 1, 1, 0, 1, 0, 1)
t 3
t 4 t 5
t 4
Рис. 3
Простой анализ полученной транзиционной системы показывает, что свой-
ство взаимного исключения выполняется, поскольку в позиции Work во время
функционирования СП появляется не более одной фишки. Это же справедливо и
для позиции Wait. Таким образом, в режиме активного ожидания или работы
с общей памятью в каждый момент находится не более одного процессора. Коли-
чество фишек в этих позициях в транзиционной системе, представленной на
рис. 3, задается двумя последними элементами векторов разметки.
Свойство равноправия тоже, очевидно, выполняется, поскольку при появле-
нии в разметке µ активного процессора (один процессор в позиции Want) из этой
разметки достижима разметка ,µ′ при которой в позиции Want находится 0 фи-
шек. А это означает, что процессор рано или поздно получит доступ к соответ-
ствующему ресурсу (памяти, данным и т.п.).
Выводы
Представлена имитационная модель функционирования узла Grid-системы
на основе СП. Выбор математического аппарата для моделирования объясняется
необходимостью обеспечить синхронизацию доступа к общим ресурсам (дан-
ным) Grid-системы при выполнении параллельных вычислений. Для анализа
предлагаемой модели используются матрицы инцидентности и TSS-алгоритм
решения систем линейных диофантовых уравнений над множеством натураль-
ных чисел. Анализ построенной модели позволяет утверждать, что она обладает
необходимыми свойствами СП, т.е. модель живая, ограниченная и все ее пози-
ции достижимы. Доказано выполнение базовых свойств, необходимых для обес-
печения синхронизации доступа к данным и их корректной обработки в узлах
Grid-системы.
Дальнейшие исследования по данной проблематике связаны с построением
модели узла Grid-системы с учетом очереди возможных запросов, а также с моде-
лированием работы Grid-системы в целом.
Проблемы управления и информатики, 2008, № 1 113
А.Ю. Шелестов
МОДЕЛЮВАННЯ РОБОТИ ВУЗЛА
GRID-СИСТЕМИ НА ОСНОВІ МЕРЕЖ ПЕТРІ
Обчислювальний вузол Grid-системи досліджується із застосуванням апарату
мереж Петрі. Побудовано модель роботи вузла та досліджено її структурні вла-
стивості, зокрема показано, що побудована мережа є обмеженою, живою та не
містить недосяжних позицій. Для побудованої моделі проведено аналіз існу-
вання властивостей взаємного виключення та рівноправ’я.
A.Yu. Shelestov
MODELING OF THE GRID SYSTEM NODE
BEHAVIOR BASED ON PETRI NETS
Processing node of the Grid system was investigated using Petri network approach.
The model of the working node was constructed and its structural properties were
investigated. In particular, it was shown, that constructed network is bounded, living
and hasn’t the inaccessible places. For constructed model the feasibility analysis of
the mutex and fairness properties was also performed.
1. Krauter K., Buyya R., Maheswaran M. A Taxonomy and survey of GRID resource management
systems and distributed computing // Software-Practice and Experience, John Wiley & Sons,
Ltd. — 2001. — P. 1–10.
2. Менаске Д., Алмейда В. Производительность Web-служб. Анализ, оценка и планирова-
ние. — М. : ДиаСофт, 2003. — 480 с.
3. Куссуль Н.Н., Шелестов А.Ю., Лобунец А.Г. Применение методов операционного анализа
для оценки производительности GRID-систем // Кибернетика и вычисл. техника. —
2004. — Вып. 144. — С. 3–20.
4. Питерсон Дж. Теория сетей Петри и моделирование систем. — М. : Мир, 1984. — 264 с.
5. Дубинин В.Н., Зинкин С.А. Языки логического программирования в проектировании вычис-
лительных систем и сетей : Уч. пособие. — Пенза : Изд-во Пенз. гос. техн. ун-та, 1997. —
100 с.
6. Parikh R. On context-free languages // J. of the ACM. — 1966. — 13, N 4. — P. 570–581.
7. Кривой С.Л. Критерий совместности систем линейных диофантовых уравнений над мно-
жеством натуральных чисел // Доп. НАН України. — 1999. — № 5. — С. 107–112.
8. Krivoi S. A criteria of compatibility systems of linear diophantine constraints // Lecture Notes in
Comp. Science. — 2002. — N 2328. — P. 264–271.
9. Летичевський О.А. Сучасні проблеми кібернетики. Нормативний курс. Навчальна елек-
тронна бібліотека факультету кібернетики Київського національного університету ім. Тара-
са Шевченка. — www.unicyb.kiev.ua/Library.
Получено 10.12.2007
Введение
1. Предметная область и требования к модели
2. Сети Петри. Основные определения
3. Модель работы узла в виде СП
4. Исследование структурных свойств модели
5. Исследование выполнимости свойств взаимного исключения и равноправия
Выводы
|
| id | nasplib_isofts_kiev_ua-123456789-209093 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T18:18:44Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шелестов, А.Ю. 2025-11-12T19:20:26Z 2008 Моделирование работы узла grid-системы на основе сетей Петри / А.Ю. Шелестов // Проблемы управления и информатики. — 2008. — № 1. — С. 104-113. — Бібліогр.: 9 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209093 681.63; 519.872 10.1615/JAutomatInfScien.v40.i2.40 Обчислювальний вузол Grid-системи досліджується із застосуванням апарату мереж Петрі. Побудовано модель роботи вузла та досліджено її структурні властивості, зокрема показано, що побудована мережа є обмеженою, живою та не містить недосяжних позицій. Для побудованої моделі проведено аналіз існування властивостей взаємного виключення та рівноправ’я. Processing node of the Grid system was investigated using Petri network approach. The model of the working node was constructed and its structural properties were investigated. In particular, it was shown, that constructed network is bounded, living and hasn’t the inaccessible places. For constructed model the feasibility analysis of the mutex and fairness properties was also performed. Работа выполнена в рамках темы НАН Украины «Интеллект» при поддержке гранта INTAS–CNES–NSAU «Data Fusion Grid Infrastructure» (Ref. Nr 06-1000024-9154). ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Моделирование работы узла grid-системы на основе сетей Петри Моделювання роботи вузла Grid-системи на основі мереж Петрі Modeling of the grid system node behavior based on Petri nets Article published earlier |
| spellingShingle | Моделирование работы узла grid-системы на основе сетей Петри Шелестов, А.Ю. Методы обработки информации |
| title | Моделирование работы узла grid-системы на основе сетей Петри |
| title_alt | Моделювання роботи вузла Grid-системи на основі мереж Петрі Modeling of the grid system node behavior based on Petri nets |
| title_full | Моделирование работы узла grid-системы на основе сетей Петри |
| title_fullStr | Моделирование работы узла grid-системы на основе сетей Петри |
| title_full_unstemmed | Моделирование работы узла grid-системы на основе сетей Петри |
| title_short | Моделирование работы узла grid-системы на основе сетей Петри |
| title_sort | моделирование работы узла grid-системы на основе сетей петри |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/209093 |
| work_keys_str_mv | AT šelestovaû modelirovanierabotyuzlagridsistemynaosnoveseteipetri AT šelestovaû modelûvannârobotivuzlagridsisteminaosnovímerežpetrí AT šelestovaû modelingofthegridsystemnodebehaviorbasedonpetrinets |