Моделювання Grid-вузла на основі мереж Петрі

The node of Grid system was investigated using the Petri network approach. A model of the working node was constructed and its structural properties were investigated. In particular, it is shown that the constructed network is bounded, alive and free of inaccessible places. Analysis of the mutex and...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
1. Verfasser:	Shelestov, A. Yu.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2009
Online Zugang:	https://journal.iasa.kpi.ua/article/view/107838
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	System research and information technologies
Завантажити файл:

Institution

System research and information technologies

_version_	1867334306524823552
author	Shelestov, A. Yu.
author_facet	Shelestov, A. Yu.
author_institution_txt_mv	[ { "author": "A. Yu. Shelestov", "institution": null } ]
author_sort	Shelestov, A. Yu.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-04-06T12:33:14Z
description	The node of Grid system was investigated using the Petri network approach. A model of the working node was constructed and its structural properties were investigated. In particular, it is shown that the constructed network is bounded, alive and free of inaccessible places. Analysis of the mutex and fairness properties was performed for the model.
first_indexed	2025-07-17T10:22:28Z
format	Article
fulltext	© А.Ю. Шелестов, 2009 52 ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 УДК 681.61 МОДЕЛИРОВАНИЕ GRID-УЗЛА НА ОСНОВЕ СЕТЕЙ ПЕТРИ А.Ю. ШЕЛЕСТОВ Исследуется узел Grid-системы с применением аппарата сетей Петри. Построена модель работы узла и рассмотрены ее структурные свойства. Пока- зано, что полученная сеть является ограниченной, живой и не содержит недос- тижимых позиций. Проведен анализ выполнимости свойств взаимного исклю- чения и равноправия. ВВЕДЕНИЕ Бурное развитие вычислительной техники и систем телекоммуникаций, со- провождаемое усложнением инфраструктуры распределенных информаци- онно-аналитических систем, привело к необходимости развития средств и методов их моделирования. Одной из наиболее активно развиваемых техно- логий создания распределенных систем является Grid-технология, направ- ленная на обеспечение работы виртуальных организаций, решающих вы- числительно сложные задачи с использованием распределенных хранилищ данных и мощных вычислительных ресурсов [1]. Для моделирования подобных систем используются различные подхо- ды, ни один из которых не может претендовать на исчерпывающее описа- ние, а представляет лишь один из аспектов функционирования или структу- ры системы. Достаточно полный обзор существующих моделей разного уровня абстракции содержится в [1–3]. В данной работе для моделирования динамики таких систем предлагается использовать математический аппарат сетей Петри [4], поскольку Grid-система представляет собой набор взаимо- действующих между собой компонентов (вычислительных узлов и храни- лищ данных), которые могут функционировать параллельно и в работе ко- торых должна быть обеспечена синхронизация. Большое значение такие модели приобретают при исследовании Grid- систем наблюдения Земли, поскольку в этих системах особое внимание уде- ляется синхронизации доступа к общим сегментам данных и распараллели- ванию вычислений. ПРЕДМЕТНАЯ ОБЛАСТЬ И ФОРМУЛИРОВКА ТРЕБОВАНИЙ К МОДЕЛИ Распределенные системы обработки данных наблюдения Земли имеют свои особенности. В частности, для таких систем характерно использование как распределенных вычислительных, так и информационных ресурсов (совме- стно используемых баз данных или хранилищ). Как правило, прикладные задачи, решаемые в системах обработки спутниковых данных (в том числе Grid-системах), предполагают обмен данными большого объема, использо- вание информации из различных географически удаленных друг от друга источников, синхронизацию потоков выполнения задач и доступ к общим Моделирование Grid-узла на основе сетей Петри Системні дослідження та інформаційні технології, 2009, № 3 53 хранилищам. Именно поэтому Grid-инфраструктуры, связанные с обработ- кой данных наблюдения Земли, выделяют в отдельный класс Grid-систем, исследованию которых посвящен проект DEGREE [5] в рамках программы EGEE. Подобные системы содержат следующие функциональные компо- ненты. 1. Метапланировщики (управляющие узлы) уровня всей системы в це- лом или ее отдельной, архитектурно значимой, части, которые обеспечива- ют передачу заданий (т.е. исполняемого программного кода и данных) на требуемый вычислительный ресурс (в терминах пакета gLite [6] — Computational Element, или вычислительный элемент) или ресурс хранения (Storage Element). В состав метапланировщика входят алгоритмы планиро- вания выполнения задач, которые могут отличаться для разных систем. Примеры метапланировщиков: GridWay [7] или WMS (gLite сегодня не находит широкого применения в исследовании Земли из космоса), GrAS [8]. Однако наиболее востребован GridWay, включенный в состав последних версий Globus Toolkit [9] и активно применяемый в гетерогенных системах. Метапланировщики являются надстройкой над базовой Grid-инфра- структурой (работающей под управлением программного обеспечения про- межуточного уровня) и взаимодействуют не с конкретными аппаратными ресурсами, а с представляющими эти ресурсы Grid-сервисами. Для выпол- нения своих функций метапланировщики используют данные, предос- тавляемые информационными сервисами Grid-инфраструктуры, что позво- ляет им учитывать общее состояние системы при принятии решений о распределении задач между Grid-ресурсами. Для отправки задач на кон- кретные ресурсы системы используются интерфейсы, предоставляемые сер- висами выполнения задач. 2. Локальные планировщики, например, Torque [10], PBS Pro [11], Sun Grid Engine [12], LSF [13], которые обеспечивают управление выполнением задач на локальном ресурсе и взаимодействуют с метапланировщиком. 3. Распределенные вычислительные узлы и ресурсы хранения данных. Доступ к ним и их использование должны быть синхронизированы, а на уз- лах с этими ресурсами установлены также Grid-сервисы программной ин- фраструктуры (MDS, GRAM, GridFTP, RFT и т.д.), которые могут предос- тавлять на верхний уровень информацию о состоянии данного ресурса и тем самым позволять реализацию эффективного планирования выполнения задач. Таким образом, выполнение задачи в Grid-среде является трехуровне- вым иерархическим процессом, на верхнем уровне которого находится ме- тапланировщик, на среднем — локальные планировщики, а на нижнем — физические вычислительные ресурсы. В частности, такая иерархия поддер- живается в системах на основе метапланировщика GridWay платформы Globus Toolkit или брокера ресурсов Resource Broker платформы gLite. Зада- чи пользователей поступают в очередь метапланировщика заданий. Этот компонент, используя информацию от информационных сервисов Grid- системы и отдавая команды сервисам передачи данных и управления зада- чами, распределяет задачи по ресурсам Grid-системы, реализуя некоторый алгоритм планирования с учетом статистики, предоставляемой информа- ционным сервисом MDS. А.Ю. Шелестов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 54 Все перечисленные выше компоненты и взаимосвязи между ними пока- заны на рис. 1. Поскольку задачи обработки данных наблюдения Земли характеризу- ются высокой вычислительной сложностью и большим объемом используе- мых данных, то очень важно обеспечить синхронизацию как отдельных по- токов выполнения, так и доступа к общим ресурсам, в частности хранилищам данных. В данной статье исследуется синхронизация доступа к общей памяти. При этом учитывается то, что в структуре Grid-системы наблюдается фрак- тальность, т.е. синхронизацию доступа необходимо обеспечивать как на уровне метапланировщика и доступа к общему хранилищу (одному из об- щих ресурсов системы), так и на уровне локального планировщика и досту- па к общей памяти вычислительных элементов. Ситуация, когда группа задач или потоков выполнения одновременно использует общее сетевое хранилище или общую память, является достато- чно распространенной в области обработки спутниковых данных и модели- рования окружающей среды. В частности, разовый запуск региональной метеорологической модели WRF для территории Украины требует более 10 Гбайт входных данных. Как правило, в современных сетевых системах хранения данных в ка- честве носителей информации используются жесткие диски, одним из ос- новных свойств которых является нелинейное снижение производительно- сти при увеличении числа параллельных запросов. Например, один жесткий диск позволяет выполнять однопоточное линейное чтение со скоростью ⋅⋅⋅ Рис. 1. Роль метапланировщика в Grid-инфраструктуре Моделирование Grid-узла на основе сетей Петри Системні дослідження та інформаційні технології, 2009, № 3 55 около 80 МБ/с, однако при считывании двух линейных потоков скорость каждого из них будет не более 30 МБ/с. С точки зрения суммарного времени выполнения задач предпочтительней последовательное считывание данных. Поэтому актуальна задача оптимизации доступа к общим ресурсам хра- нилища, в том числе путем блокировки параллельных процессов чте- ния/записи. Таким образом, задача состоит в построении Grid-системы, обеспечи- вающей прозрачную для пользователя обработку его запросов на поиск и обработку данных, в том числе синхронизацию доступа к необходимым данным, обработку этих данных и предоставление пользователю результа- тов обработки. Такая Grid-система относится к Grid-системам смешанного типа (одновременно вычислительная и информационная [1]), поскольку со- держит высокопроизводительные вычислительные узлы и обеспечивает доступ к данным распределенных хранилищ [3]. Синхронизация доступа к данным и их корректная обработка предпо- лагает выполнение некоторых базовых условий. Взаимное исключение (mutex) — синхронизация событий при обра- ботке данных: два или более вычислительных узла не могут одновременно иметь доступ к общей области данных (общему хранилищу или общей па- мяти). Здесь и ниже в качестве вычислительного узла будем понимать либо отдельный вычислительный элемент, либо один из процессоров, входящих в его состав. Равноправие (fairness) — отсутствие дискриминации заданий. Если пользователь сформировал запрос (задание) и отправил его в систему, то обязательно наступит момент, когда это задание начнет выполняться и бу- дет выполнено. Отсутствие тупиков (deadlock free) — в системе не может возникнуть ситуация взаимной блокировки вычислений или доступа к данным (общим или распределенным). На рис. 2 показана работа Grid-системы смешанного типа без детализа- ции, где видно, что при отправке запроса пользователя в систему он попада- ет на управляющий узел (УУ) (планировщик), который выполняет распре- деление этого задания между ресурсами системы (вычислительными узлами) и определяет местонахождение необходимых данных. На рис. 2 вы- числительные узлы и хранилища данных изображены в виде элемента Узел. Этот же УУ обеспечивает синхронизацию при распараллеливании задания между ресурсами или при выполнении операций доступа к общей памяти. Учитывая высокую стоимость компонентов Grid-систем, прежде чем приступать к построению системы с указанными свойствами, необходимо построить ее модель и исследовать свойства этой модели. Построим модель функционирования вычислительного узла, работаю- щего над общей памятью, и исследуем ее свойства. Учитывая специфику работы Grid-системы и необходимость синхронизации доступа к общим сегментам данных при организации параллельных вычислений, в качестве математического аппарата для моделирования воспользуемся аппаратом сетей Петри. А.Ю. Шелестов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 56 СЕТИ ПЕТРИ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ Введем основные понятия, связанные с моделированием распределенных систем с разделением ресурсов с помощью сетей Петри. Определение 1. Сетью Петри (согласно [4]) называется четверка эле- ментов ),,,( OITPС = , (1) где 0},,,,{ 21 >= npppP n… (2) — конечное множество позиций; 0},,,,{ 21 >= mtttT m… (3) — конечное множество переходов; PTI >: (4) — функция входов (отображение множества переходов во входные позиции); PTO >: (5) — функция выходов (отображение множества переходов в выходные пози- ции). Если )( ji tIp = , то ip — входная позиция j -го перехода. Если )( ji tOp = , то ip — выходная позиция j -го перехода. Для наглядного представления сетей Петри используются графы. Определение 2. Сеть Петри — это двудольный ориентированный мультиграф ),( AVG = , (6) Рис. 2. Модель информационных потоков в Grid-системе Моделирование Grid-узла на основе сетей Петри Системні дослідження та інформаційні технології, 2009, № 3 57 где },,,{ 21 nmuuuV += … — множество вершин; },,,{ 21 raaaA …= — ком- плект направленных дуг. (Комплектом называется множество, содержащее многократно повторяющиеся элементы [4].) Вершинами графа являются непересекающиеся множества позиций P и переходов T сети Петри. TPV ∪= , причем ∅=∩TP . Направленные дуги соединяют связанные между собой позиции и пе- реходы. Определение 2 обеспечивает наглядное графическое представление се- ти Петри, на основе которого можно сформулировать еще одно определение сети Петри, которое и будет использоваться в дальнейшем при исследова- нии свойств сети. Определение 3. Сетью Петри называется тройка элементов ),,( ATPC = , (7) где P и T множества позиций и переходов сети Петри соответственно; A — матрица инцидентности графа сети, связывающая позиции с перехо- дами сети. Если элемент 0=ijA , значит i -я позиция и j -й переход не связаны между собой. Если 0>= kAij , значит в результате запуска j -го перехода в i -й позиции добавляется k фишек. Если 0<= kAij , значит в результате запуска j -го перехода из i -й позиции убирается k фишек. Разметкой сети Петри µ называется присвоение фишек позициям се- ти [4]. Определение 4. Разметка µ сети Петри ),,,( OITPC = есть функция, отображающая множество позиций на множество натуральных чисел. NP →:µ . (8) Разметку можно также определить как вектор },,,{ 21 nµµµµ …= , (9) где n — мощность множества позиций, а Ni ∈µ , ni ,,1…= . Вектор µ оп- ределяет для каждой позиции pi сети количество фишек в этой позиции. На графе разметка отображается соответствующим числом точек в ка- ждой позиции. Точки называются маркерами или фишками. Если фишек много (больше трех), то их количество отображается числом. МОДЕЛЬ РАБОТЫ УЗЛА В ВИДЕ СЕТИ ПЕТРИ Модель работы вычислительного узла с четырьмя процессорами, обрабаты- вающего задания пользователя под управлением планировщика (глобально- го или локального уровня) в соответствии с общей схемой (рис. 2) показана на рис. 3. Эта модель представляет собой одноцветную сеть Петри вида (7), начальное состояние которой описывается разметкой )0,0,0,1,1,0,0,4()workwait,busy,free,block,query,want,proc,(0 ==M . А.Ю. Шелестов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 58 Позиции и переходы в данной сети Петри имеют следующую се- мантику: proc — свободные в данный момент времени процессоры; query — запрос на выполнение задания от пользователя; want — процессор активен и желает начать работу; work — процессор получил доступ к общей памяти и выполняет вы- числения; wait — активный процессор ожидает доступа к общей памяти; block — блокируется доступ к общей памяти и очереди ожидания, ес- ли они заняты другими процессорами; free — управляющий узел сигнализирует о снятии блокировки общей памяти; busy — управляющий узел сигнализирует о том, что общая память за- блокирована для доступа. Показанная на рис. 3 модель достаточно точно описывает процесс вы- полнения задач с большими потребностями в данных в Grid-окружении. При этом элементам модели соответствуют такие компоненты реальной системы: 1. Позиция query является представлением очереди задач метаплани- ровщика (или планировщика) Grid-системы, а метки в ней — представлени- ем задач в очереди (глобальной или локальной). 2. Метки в позиции proc соответствуют свободным вычислительным узлам Grid-системы (вычислительным элементам или процессорам). При начальной разметке )0,0,0,1,1,0,0,4(0 =M система находится в состоянии покоя (который иногда называют состоянием сна). Из семантики позиций следует и смысл переходов: запt — наличие запроса на обработку данных; 1t — один из свободных процессоров хочет работать; П ол ьз ов ат ел и Рис. 3. Модель вычислительного узла, работающего под управлением планиров- щика над общей памятью с глубиной очереди 1 Моделирование Grid-узла на основе сетей Петри Системні дослідження та інформаційні технології, 2009, № 3 59 2t — процессор получает доступ к общей памяти; 3t — активный процессор переходит в состояние ожидания; 4t — процессор завершил работу с общей памятью и она разблокиро- вана; 5t — активный процессор из состояния ожидания переходит в состоя- ние работы с общей памятью, при этом одновременно разблокируется пере- ход активного процессора в состояние ожидания. Переход 6t и позиция без наименования между переходами 3t и 6t введены в результате модификации структуры сети Петри и преобразования полуцикла в цикл. Это сделано во избежание неоднозначностей в процессе последующего анализа сети. При появлении запроса пользователя на выполнение задания срабаты- вает сначала один из переходов запt , а затем переход 1t . В результате этого один из свободных процессоров переходит в состояние активности (готов- ности к работе), т.е. переходит в позицию want. Если одновременно посту- пают два запроса, то выполнение одного из них будет задержано из-за от- сутствия маркера в позиции block. Дальнейшая работа модели очевидна. ИССЛЕДОВАНИЕ СТРУКТУРНЫХ СВОЙСТВ МОДЕЛИ Рассмотрим определения некоторых основных свойств сетей Петри. Определение 5. Переход t живой (активный), если он срабатывает при запуске сети из любой начальной разметки. tNR →∈∀ µµ :)( . Сеть Петри жива, если живым является каждый ее переход. tpNRTtt →∈∈∀∀ )(:))(&( µµµ . Определение 6. Если существует разметка (маркировка) сети, из кото- рой переход ti никогда не запускается,то он называется мертвым. Определение 7. Для сети ),,,( OITPC = разметка µ′ называется непо- средственно достижимой из µ , если существует такой переход Tt j ∈ , при котором результатом запуска перехода jt является разметка µ′ . µµδ ′=),( jt . На основе определения 7 можно сформулировать определения дости- жимой и недостижимой позиций. Определение 8. Позиция pi называется достижимой, если для любой начальной разметки существует последовательность переходов, приводящая к µ(pi)>0 . Определение 9. Если ip∃ такая, что 0)(:))(&( =∈∈∀∀ ipNRTtt µµµ , то позиция ip называется недостижимой. А.Ю. Шелестов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 60 Сначала исследуем структурные свойства построенной на рис. 1 сети Петри: проверим выполнение свойства ограниченности, удостоверимся в отсутствии мертвых (лишних) переходов и недостижимых позиций. Для подтверждения достижимости всех позиций сети и доказательства живости сети необходимо построить S - и T -инварианты сети. S -инвариант — это линейное отношение на разметке подмножества позиций, выражающееся в том, что сумма различных меток в позициях по- ложительна. Если в S -инвариант входят все позиции сети Петри, то в по- строенной модели все позиции являются достижимыми. T -инвариант соот- ветствует последовательности срабатывания переходов, переводящей сеть из разметки M в ту же самую разметку M [14]. Если T -инвариант содер- жит все переходы сети, то она жива. Для нахождения S - и T -инвариантов сети построим целочисленную n×m матрицу инцидентности сети Петри A (табл. 1), где n и m — мощно- сти множеств P и T соответственно. В матрице A элемент 1=ijA , если при выполнении перехода j фишка добавляется в позицию i . 1−=ijA , если при выполнении перехода j фишка убирается из позиции i . 0=ijA , если при выполнении перехода j число фишек в позиции i не изменяется. Т а б л и ц а 1 . Построение матрицы инцидентности сети Петри (рис. 2) Состояние сети Петри 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=xA , (10) где A — целочисленная n×m матрица инцидентности сети Петри; n и m — мощности множеств P и T соответственно; xA — m -мерный вектор Па- риха [15]. С помощью уравнения состояния (10) определим S - и T -инва- рианты сети Петри. Это и даст возможность выявить мертвые переходы, недостижимые позиции и проверить ограниченность сети. Моделирование Grid-узла на основе сетей Петри Системні дослідження та інформаційні технології, 2009, № 3 61 Размерность матрицы инцидентности A в (10) для данной сети Петри составляет 710× (10 уравнений, 7 неизвестных), а вектора Париха x — 7. В соответствии с табл. 1 матрица инцидентности для данной сети Петри бу- дет иметь вид ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ − − −− −− − − −− − − − = 1001000 0010001 1111100 0110100 0110100 0101000 0001110 0100110 0010010 0000011 A . Для получения множества S - и T -инвариантов сети Петри использу- ется TSS-алгоритм [16, 17], который позволяет построить минимальную по- рождающую систему решений однородной системы линейных диофантовых уравнений над множеством натуральных чисел N . Согласно [16, 17] TSS-алгоритм позволяет сгенерировать множество S - или T -инвариантов. Входными данными алгоритма являются матрица сис- темы S размерности qp × ( p строк и q столбцов) с начальным множест- вом решений M . Работа TSS-алгоритма на языке псевдокода описывается следующим образом. ),,,( SqpMTSS begin if ∅=M then }ofvectorcanonicalis\|{ qNeeM = ; for 1:=i to p do ))(,(1: xLMTSSM i= ; if ∅=M then (print (“NO SOLUTION”); STOP) else CLEAN )(M print(M) end ))(,(1 xLMTSS begin ∅=0M ; ∅=+ :M ; ∅=− :M ; forall Me∈ do (if 0))(,( =xLeSCP then }{: 00 eMM ∪= else if 0))(,( >xLeSCP then }{: eMM ∪= ++ else }{: eMM ∪= −− ); А.Ю. Шелестов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 62 0: MM =′ ; if ∅≠∧∅≠ −+ MM then (forall +∈Mu do (forall −∈Mv do vuLuvLe )()(: +−= ; }{: eMM ∪′=′ )) return )(M ′ end В приведенном фрагменте псевдокода функция += 11)( xaxL ii qiqi xaxa +++ …22 представляется вектором ),,,( 21 iqii aaa … , ),( yxSCP означает скалярное произведение векторов x и y , а процедура чистки CLEAN )(M удаляет лишние решения. В соответствии с TSS-алгоритмом система диофантовых уравнений (10) имеет два решения. Tx }0,0,1,0,1,1,1{1 = , Tx }1,1,1,1,0,1,1{2 = . На основе решений этой системы можно построить T -инварианты (табл. 2). Т а б л и ц а 2 . T-инварианты сети Петри (рис. 2) 0t 1t 2t 3t 4t 5t 6t 1 1 1 0 1 0 0 1 1 0 1 1 1 1 Поскольку в табл. 2 нет ни одного столбца, содержащего только нуле- вые элементы, значит все переходы в сети Петри являются живыми при данной начальной разметке, т.е. каждый переход в сети срабатывает хотя бы один раз. Несложно удостовериться, что это свойство выполняется и для других возможных начальных разметок (варьироваться может число фишек во входных позициях сети), следствием чего является отсутствие тупи- ков, когда в системе не может возникнуть ситуация взаимной блокировки вычислений или доступа к данным (общим или распределенным). Действи- тельно, тупик возникает в сети Петри, если нельзя запустить один или не- сколько переходов. Так как все переходы живые, то сеть Петри обладает третьим требуемым свойством — характеризуется отсутствием тупиков. Сгенерируем S -инварианты данной сети Петри. Для этого найдем ре- шения системы уравнений 0=ymA , (11) где A — целочисленная mn × матрица инцидентности сети Петри; m — символ транспонирования матрицы; y — n -мерный вектор. Моделирование Grid-узла на основе сетей Петри Системні дослідження та інформаційні технології, 2009, № 3 63 Система диофантовых уравнений (11), содержащая 7 уравнений и 10 неизвестных, имеет следующие решения: Ty }0,0,0,1,1,0,0,0,0,0{1 = , Ty }0,0,0,0,0,1,1,1,0,0{2 = , Ty }0,0,0,0,1,1,1,0,1,0{3 = , Ty }0,1,0,0,1,1,1,0,0,1{4 = , Ty }1,0,1,1,0,0,0,0,0,0{5 = , Ty }1,0,1,0,0,1,1,0,1,0{6 = , Ty }0,1,0,0,1,1,1,0,0,1{7 = . Решения матрично-векторного уравнения (11) определяют S -инва- рианты сети Петри (табл. 3). Т а б л и ц а 3 . S-инварианты сети Петри (рис. 2) 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 также следует, что все позиции в сети достижимы, т.е. модель не содержит лишних позиций. Таким образом, модель вычислительного узла в виде сети Петри живая, ограниченная и все позиции в сети достижимы. Утверждение доказано. ИССЛЕДОВАНИЕ ВЫПОЛНИМОСТИ СВОЙСТВ ВЗАИМНОГО ИСКЛЮЧЕНИЯ И РАВНОПРАВИЯ При доказательстве утверждения было показано, что модель вычисли- тельного узла Grid-системы в виде сети Петри обладает основными струк- турными свойствами подобных моделей: ограниченностью, достижимостью и активностью. При этом сеть характеризуется отсутствием тупиков (deadlock free), т.е. выполняется третье из базовых свойств моделей синхро- низации доступа к данным. Для исследования выполнимости свойств взаимного исключения (mutex) и равноправия (fairness) необходимо построить транзиционную систему [18] или граф достижимых разметок сети Петри. А.Ю. Шелестов ISSN 1681–6048 System Research & Information Technologies, 2009, № 3 64 Для начальной разметки, определяемой соотношением ,proc(0 =M )0,0,0,1,1,3,0,4()workwait,busy,free,block,query,want, = , транзиционная система сети Петри (рис. 3) показана на рис. 4. Простой анализ полученной транзиционной системы показывает, что свойство взаимного исключения (mutex) выполняется, поскольку в пози- ции work во время функционирования сети Петри появляется не более од- ной фишки, что справедливо и для позиции wait. Значит, в режиме актив- ного ожидания или работы с общей памятью в каждый момент находится не более одного процессора. Число фишек в этих позициях в транзиционной системе на рис. 3 задается двумя последними элементами векторов разметки. Свойство равноправия (fairness) тоже, очевидно, выполняется, по- скольку при появлении активного процессора (1 в позиции want) в размет- ке µ из нее достижима разметка µ`, при которой в позиции want находится 0 фишек. А это означает, что процессор рано или поздно получит доступ к соответствующему ресурсу (памяти, данным и т.п.). ВЫВОДЫ Представлена имитационная модель функционирования узла Grid-системы на основе сетей Петри. Выбор математического аппарата для моделирова- ния объясняется необходимостью обеспечить синхронизацию доступа к об- щим ресурсам (данным) Grid-системы при выполнении параллельных вы- числений. (4, 0, 3, 1, 1, 0, 0, 0) (3, 1, 2, 0, 1, 0, 0, 0) (3, 0, 2, 1, 0, 1, 0, 1) (2, 1, 1, 0, 0, 1, 0, 1) (2, 0, 1, 0, 0, 1, 1, 1) (3, 0, 1, 0, 1, 0, 1, 0) (4, 0, 0, 1, 1, 0, 0, 0) (3, 0, 0, 1, 0, 1, 0, 1) (3, 0, 0, 0, 1, 0, 1, 0) (2, 0, 0, 0, 0, 1, 1, 1) (2, 1, 0, 0, 0, 1, 0, 1) (3, 0, 1, 1, 0, 1, 0, 1) t1 t1 t3 t2 t3 t1 t4 t4 t5 t4 t5 t4 Рис. 4. Транзиционная система сети Петри, моделирующей работу узла Grid- системы Моделирование Grid-узла на основе сетей Петри Системні дослідження та інформаційні технології, 2009, № 3 65 Анализ предлагаемой модели выполняется с использованием матриц инцидентности и TSS-алгоритма решения систем линейных диофантовых уравнений над множеством натуральных чисел. Построенная модель обла- дает необходимыми свойствами сетей Петри — является живой, ограничен- ной и все ее позиции достижимы. Доказано выполнение базовых свойств, необходимых для обеспечения синхронизации доступа к данным и их корректной обработки в узлах Grid- системы. Дальнейшие исследования будут направлены на построение модели уз- ла Grid-системы с учетом очереди возможных запросов, а также на модели- рование работы Grid-системы в целом. Работа выполнена в рамках темы НАНУ «Интеллект» при поддержке гранта INTAS-CNES-NSAU «Data Fusion Grid Infrastructure» (Ref. Nr 06- 1000024-9154). ЛИТЕРАТУРА 1. Krauter K., Buyya R., Maheswaran M. A Taxonomy and Survey of GRID Resource Management Systems and Distributed Computing // Software-Practice and Ex- perience. — 2002. — № 32 — P. 135–164. 2. Менаске Д., Алмейда В. Производительность Web-служб. Анализ, оценка и планирование. — СПб. — ДиаСофт, 2003. — 480 с. 3. Куссуль Н.Н., Шелестов А.Ю., Лобунец А.Г. Применение методов операцион- ного анализа для оценки производительности GRID-систем// Кибернетика и вычислительная техника. — 2004. — Вып. 144. — С. 3–20. 4. Питерсон Дж. Теория сетей Петри и моделирование систем. — М.: Мир, 1984. — 264 с. 5. Dissemination and Exploitation of Grids in Earth science. — http://www.eu- degree.eu/. 6. EGEE gLite middleware. — http://glite.web.cern.ch/. 7. GridWay Metascheduler. — http://www.gridway.org/. 8. Коваленко В.Н., Коваленко Е.И., Шорин О.Н. Разработка диспетчера заданий грид, основанного на опережающем планировании. — М.: ИПМ РАН. — 2005. — 28 с. 9. Globus Toolkit. — http://globus.org/. 10. TORQUE resource manager. — http://www.clusterresources.com/pages/products/ torque-resource-manager.php. 11. PBS Professional. — http://www.pbsgridworks.com/PBSTemp1.3.aspx?top_nav_ name=Products&item_name=PBS%20Professional&top_nav_str=1. 12. Sun Grid Engine. — http://www.sun.com/software/gridware/. 13. Platform LSF. — http://www.platform.com/Products/platform-lsf-family/platform-lsf. 14. Дубинин В.Н., Зинкин С.А. Языки логического программирования в проектиро- вании вычислительных систем и сетей: Учеб. пособие. — Пенза: Изд-во Пенз. гос. техн. ун-та, 1997. — 100 с. 15. Parikh R. On Context-Free Languages // J. of the ACM. — 1966. — 13, № 4. — P. 570–581. 16. Кривой С.Л. Критерий совместности систем линейных диофантовых уравнений над множеством натуральных чисел// Доп. НАНУ. — 1999. — № 5. — С. 107–112. 17. Krivoi S. A criteria of Compatibility Systems of Linear Diophantine Constraints // Lecture Notes in Comp. Science. — 2002. — № 2328. — P. 264–271. 18. Летичевський О.А. Сучасні проблеми кібернетики. Нормативний курс. Навчальна електронна бібліотека факультету кібернетики Київського національного університету ім. Тараса Шевченка. — http://www.unicyb. kiev.ua/Library/. Поступила 12.10.2007
id	journaliasakpiua-article-107838
institution	System research and information technologies
keywords_txt_mv	keywords
language	Russian
last_indexed	2025-07-17T10:22:28Z
publishDate	2009
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/b2/e45c198b7dec408a198b21a4be0aedb2.pdf
spelling	journaliasakpiua-article-1078382018-04-06T12:33:14Z Grid node modeling based on Petri networks Моделирование Grid-узла на основе сетей Петри Моделювання Grid-вузла на основі мереж Петрі Shelestov, A. Yu. The node of Grid system was investigated using the Petri network approach. A model of the working node was constructed and its structural properties were investigated. In particular, it is shown that the constructed network is bounded, alive and free of inaccessible places. Analysis of the mutex and fairness properties was performed for the model. Исследуется узел Grid-системы с применением аппарата сетей Петри. Построена модель работы узла и рассмотрены ее структурные свойства. Показано, что полученная сеть является ограниченной, живой и не содержит недостижимых позиций. Проведен анализ выполнимости свойств взаимного исключения и равноправия. Досліджується вузол Grid-системи із застосуванням апарату мереж Петрі. Побудовано модель роботи вузла та досліджено її структурні властивості. Показано, що побудована мережа є обмеженою, живою та не містить недосяжних позицій. Проведено аналіз умов виконання властивостей взаємного виключення та рівноправ’я. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2009-09-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/107838 System research and information technologies; No. 3 (2009); 52-65 Системные исследования и информационные технологии; № 3 (2009); 52-65 Системні дослідження та інформаційні технології; № 3 (2009); 52-65 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/107838/102785 Copyright (c) 2021 System research and information technologies
spellingShingle	Shelestov, A. Yu. Моделювання Grid-вузла на основі мереж Петрі
title	Моделювання Grid-вузла на основі мереж Петрі
title_alt	Grid node modeling based on Petri networks Моделирование Grid-узла на основе сетей Петри
title_full	Моделювання Grid-вузла на основі мереж Петрі
title_fullStr	Моделювання Grid-вузла на основі мереж Петрі
title_full_unstemmed	Моделювання Grid-вузла на основі мереж Петрі
title_short	Моделювання Grid-вузла на основі мереж Петрі
title_sort	моделювання grid-вузла на основі мереж петрі
url	https://journal.iasa.kpi.ua/article/view/107838
work_keys_str_mv	AT shelestovayu gridnodemodelingbasedonpetrinetworks AT shelestovayu modelirovaniegriduzlanaosnovesetejpetri AT shelestovayu modelûvannâgridvuzlanaosnovímerežpetrí

Моделювання Grid-вузла на основі мереж Петрі

Institution

Ähnliche Einträge