Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования
Рассмотрен метод проектирования грид-системы на основе транзиционных систем и их синхронных произведений. Полученная глобальная транзиционная система транслируется в сеть Петри (СП). С помощью СП проверяется корректность проектных решений, в частности отсутствие тупиков, мертвых переходов и т.д. Роз...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2017 |
| Автори: | , , , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/144690 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования / С.Л. Крывый, Ю.В. Бойко, С.Д. Погорелый, А.Ф. Борецкий, Н.Н. Глыбовец // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 122-133. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144690 |
|---|---|
| record_format |
dspace |
| spelling |
Крывый, С.Л. Бойко, Ю.В. Погорелый, С.Д. Борецкий, А.Ф. Глыбовец, Н.Н. 2019-01-01T20:35:26Z 2019-01-01T20:35:26Z 2017 Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования / С.Л. Крывый, Ю.В. Бойко, С.Д. Погорелый, А.Ф. Борецкий, Н.Н. Глыбовец // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 122-133. — Бібліогр.: 6 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144690 004.75 Рассмотрен метод проектирования грид-системы на основе транзиционных систем и их синхронных произведений. Полученная глобальная транзиционная система транслируется в сеть Петри (СП). С помощью СП проверяется корректность проектных решений, в частности отсутствие тупиков, мертвых переходов и т.д. Розглянуто метод проектування грід-системи на основі транзиційних систем та їхніх синхронних добутків. Отримана глобальна транзиційна система транслюється в мережу Петрі (МП). За допомогою МП перевіряють коректність проектних рішень, зокрема відсутність тупиків, мертвих переходів тощо. The authors consider the method of designing grid systems based on transition systems and their products. The resulting global transition system is translated into a Petri net, which is used to verify the correctness of the design decisions. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Програмно-технічні комплекси Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования Проектувания грід-структур на основі транзиційних систем з обгрунтуванням правильності їх функціонування Design of grid structures based on transition systems with justification of the correctness of their functioning Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования |
| spellingShingle |
Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования Крывый, С.Л. Бойко, Ю.В. Погорелый, С.Д. Борецкий, А.Ф. Глыбовец, Н.Н. Програмно-технічні комплекси |
| title_short |
Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования |
| title_full |
Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования |
| title_fullStr |
Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования |
| title_full_unstemmed |
Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования |
| title_sort |
проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования |
| author |
Крывый, С.Л. Бойко, Ю.В. Погорелый, С.Д. Борецкий, А.Ф. Глыбовец, Н.Н. |
| author_facet |
Крывый, С.Л. Бойко, Ю.В. Погорелый, С.Д. Борецкий, А.Ф. Глыбовец, Н.Н. |
| topic |
Програмно-технічні комплекси |
| topic_facet |
Програмно-технічні комплекси |
| publishDate |
2017 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Проектувания грід-структур на основі транзиційних систем з обгрунтуванням правильності їх функціонування Design of grid structures based on transition systems with justification of the correctness of their functioning |
| description |
Рассмотрен метод проектирования грид-системы на основе транзиционных систем и их синхронных произведений. Полученная глобальная транзиционная система транслируется в сеть Петри (СП). С помощью СП проверяется корректность проектных решений, в частности отсутствие тупиков, мертвых переходов и т.д.
Розглянуто метод проектування грід-системи на основі транзиційних систем та їхніх синхронних добутків. Отримана глобальна транзиційна система транслюється в мережу Петрі (МП). За допомогою МП перевіряють коректність проектних рішень, зокрема відсутність тупиків, мертвих переходів тощо.
The authors consider the method of designing grid systems based on transition systems and their products. The resulting global transition system is translated into a Petri net, which is used to verify the correctness of the design decisions.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/144690 |
| citation_txt |
Проектирование грид-структур на основе транзиционных систем с обоснованием правильности их функционирования / С.Л. Крывый, Ю.В. Бойко, С.Д. Погорелый, А.Ф. Борецкий, Н.Н. Глыбовец // Кибернетика и системный анализ. — 2017. — Т. 53, № 1. — С. 122-133. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT kryvyisl proektirovaniegridstrukturnaosnovetranzicionnyhsistemsobosnovaniempravilʹnostiihfunkcionirovaniâ AT boikoûv proektirovaniegridstrukturnaosnovetranzicionnyhsistemsobosnovaniempravilʹnostiihfunkcionirovaniâ AT pogorelyisd proektirovaniegridstrukturnaosnovetranzicionnyhsistemsobosnovaniempravilʹnostiihfunkcionirovaniâ AT boreckiiaf proektirovaniegridstrukturnaosnovetranzicionnyhsistemsobosnovaniempravilʹnostiihfunkcionirovaniâ AT glybovecnn proektirovaniegridstrukturnaosnovetranzicionnyhsistemsobosnovaniempravilʹnostiihfunkcionirovaniâ AT kryvyisl proektuvaniâgrídstrukturnaosnovítranzicíinihsistemzobgruntuvannâmpravilʹnostííhfunkcíonuvannâ AT boikoûv proektuvaniâgrídstrukturnaosnovítranzicíinihsistemzobgruntuvannâmpravilʹnostííhfunkcíonuvannâ AT pogorelyisd proektuvaniâgrídstrukturnaosnovítranzicíinihsistemzobgruntuvannâmpravilʹnostííhfunkcíonuvannâ AT boreckiiaf proektuvaniâgrídstrukturnaosnovítranzicíinihsistemzobgruntuvannâmpravilʹnostííhfunkcíonuvannâ AT glybovecnn proektuvaniâgrídstrukturnaosnovítranzicíinihsistemzobgruntuvannâmpravilʹnostííhfunkcíonuvannâ AT kryvyisl designofgridstructuresbasedontransitionsystemswithjustificationofthecorrectnessoftheirfunctioning AT boikoûv designofgridstructuresbasedontransitionsystemswithjustificationofthecorrectnessoftheirfunctioning AT pogorelyisd designofgridstructuresbasedontransitionsystemswithjustificationofthecorrectnessoftheirfunctioning AT boreckiiaf designofgridstructuresbasedontransitionsystemswithjustificationofthecorrectnessoftheirfunctioning AT glybovecnn designofgridstructuresbasedontransitionsystemswithjustificationofthecorrectnessoftheirfunctioning |
| first_indexed |
2025-11-25T07:11:26Z |
| last_indexed |
2025-11-25T07:11:26Z |
| _version_ |
1850506671088992256 |
| fulltext |
Ñ.Ë. ÊÐÛÂÛÉ, Þ.Â. ÁÎÉÊÎ, Ñ.Ä. ÏÎÃÎÐÅËÛÉ, À.Ô. ÁÎÐÅÖÊÈÉ, Í.Í. ÃËÛÁÎÂÅÖ
ÓÄÊ 004.75 ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ ÃÐÈÄ-ÑÒÐÓÊÒÓÐ ÍÀ ÎÑÍÎÂÅ
ÒÐÀÍÇÈÖÈÎÍÍÛÕ ÑÈÑÒÅÌ Ñ ÎÁÎÑÍÎÂÀÍÈÅÌ
ÏÐÀÂÈËÜÍÎÑÒÈ ÈÕ ÔÓÍÊÖÈÎÍÈÐÎÂÀÍÈß
Àííîòàöèÿ. Ðàññìîòðåí ìåòîä ïðîåêòèðîâàíèÿ ãðèä-ñèñòåìû íà îñíîâå
òðàíçèöèîííûõ ñèñòåì è èõ ñèíõðîííûõ ïðîèçâåäåíèé. Ïîëó÷åííàÿ ãëî-
áàëüíàÿ òðàíçèöèîííàÿ ñèñòåìà òðàíñëèðóåòñÿ â ñåòü Ïåòðè (ÑÏ). Ñ ïî-
ìîùüþ ÑÏ ïðîâåðÿåòñÿ êîððåêòíîñòü ïðîåêòíûõ ðåøåíèé, â ÷àñòíîñòè îò-
ñóòñòâèå òóïèêîâ, ìåðòâûõ ïåðåõîäîâ è ò.ä.
Êëþ÷åâûå ñëîâà: ãðèä-ñòðóêòóðà, òðàíçèöèîííûå ñèñòåìû, äèîôàíòîâûå
óðàâíåíèÿ.
ÂÂÅÄÅÍÈÅ
 ñâÿçè ñ òåì, ÷òî ñëîæíîñòü ïðîãðàììíîãî îáåñïå÷åíèÿ ïîñòîÿííî âîçðàñòàåò,
âîçíèêàåò âàæíàÿ ïðîáëåìà ïîñòðîåíèÿ êîððåêòíîãî ìàòåìàòè÷åñêîãî îáåñïå-
÷åíèÿ è ñîîòâåòñòâóþùåãî îáîðóäîâàíèÿ ñ ïðàâèëüíûì è íàäåæíûì ôóíêöèî-
íèðîâàíèåì. Ýòà ïðîáëåìà ðàññìàòðèâàëàñü â ðàáîòå [1], ãäå ïðåäëàãàëèñü ìå-
òîäû ïðîåêòèðîâàíèÿ ÈÒ-èíôðàñòðóêòóð. Èçëîæåííûå ìåòîäû îòíîñèëèñü
ïðåæäå âñåãî ê ïàðàëëåëüíûì, ðàñïðåäåëåííûì è îáëà÷íûì âû÷èñëåíèÿì
è òîëüêî ÷àñòè÷íî êàñàëèñü ãðèä-âû÷èñëåíèé. Ãðèä-ñèñòåìû â íàñòîÿùåå âðåìÿ
ÿâëÿþòñÿ íàèáîëåå âîñòðåáîâàííûìè âû÷èñëèòåëüíûìè ñòðóêòóðàìè â ñâÿçè
ñ íåîáõîäèìîñòüþ âûïîëíÿòü áîëüøîå êîëè÷åñòâî âû÷èñëåíèé âûñîêîé ñëîæ-
íîñòè íà ãåîãðàôè÷åñêè ðàñïðåäåëåííûõ âûñîêîïðîèçâîäèòåëüíûõ êîìïëåêñàõ.
Ãðèä-ñèñòåìû ïîçâîëÿþò ïîëüçîâàòåëþ ñ åãî ðàáî÷åãî ìåñòà çàïóñêàòü çàäàíèÿ
è ïîëó÷àòü ðåçóëüòàòû âûïîëíåíèÿ òàêèõ çàäàíèé. Ïðè ýòîì ïîëüçîâàòåëü ìî-
æåò íå çíàòü, íà êàêîì èç äîñòóïíûõ ðåñóðñîâ âûïîëíÿåòñÿ åãî çàäàíèå. Çàäà÷à
ïîëüçîâàòåëÿ ñîñòîèò â òîì, ÷òîáû ñôîðìóëèðîâàòü îïèñàíèå ñâîåãî çàäàíèÿ
â ñîîòâåòñòâèè ñ ïðàâèëàìè, âûïîëíåíèå êîòîðûõ ïîçâîëèò ïîëó÷èòü äîñòóï ê
âû÷èñëèòåëüíîé ñðåäå. Êîíòðîëü çà âûïîëíåíèåì òàêèõ ïðàâèë âîçëàãàåòñÿ íà
ñïåöèàëèçèðîâàííîå ïðîìåæóòî÷íîå ïðîãðàììíîå îáåñïå÷åíèå (ÏÏÎ), ïîëó÷èâ-
øåå íàçâàíèå middleware. ÏÏÎ ÿâëÿåòñÿ ïðîìåæóòî÷íûì çâåíîì ìåæäó ïîëüçî-
âàòåëåì è ãðèä-èíôðàñòðóêòîðîé.
 íàñòîÿùåé ñòàòüå ïðåäñòàâëåíà ìîäåëü ãðèä-ñèñòåìû, êîòîðàÿ àáñòðàãèðî-
âàíà îò ñïîñîáîâ òðàíñìèññèè óïðàâëÿþùèõ êîìàíä ÏÏÎ, ñâÿçàííûõ ñ îñîáåí-
íîñòÿìè âû÷èñëèòåëåé â ñòðóêòóðå, íà îñíîâå òðàíçèöèîííûõ ñèñòåì, ê êîòîðûì
îòíîñÿòñÿ è ñåòè Ïåòðè (ÑÏ).
Ñòðóêòóðà ðàáîòû ïðåäñòàâëåíà ñëåäóþùèì îáðàçîì.  íà÷àëå ñòàòüè èçëî-
æåí ìåòîä ïðîåêòèðîâàíèÿ, áàçèðóþùèéñÿ íà èñïîëüçîâàíèè òðàíçèöèîííûõ
ñèñòåì è èõ ñèíõðîííîì ïðîèçâåäåíèè. Äàëåå îïèñûâàåòñÿ ïðåîáðàçîâàíèå ïîëó-
÷åííîãî ñèíõðîííîãî ïðîèçâåäåíèÿ â ÑÏ. Âûïîëíÿåòñÿ àíàëèç ñâîéñòâ ñåòè Ïåò-
ðè, êîòîðàÿ ìîäåëèðóåò âñþ ñèñòåìó â öåëîì. Â ïðîöåññå ïðîåêòèðîâàíèÿ ñèñòåì
122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1
© Ñ.Ë. Êðûâûé, Þ.Â. Áîéêî, Ñ.Ä. Ïîãîðåëûé, À.Ô. Áîðåöêèé, Í.Í. Ãëûáîâå ö, 2017
îïðåäåëåíèå ñèíõðîííîãî ïðîèçâåäåíèÿ âûïîëíÿåòñÿ ïðîåêòèðîâùèêîì, à èñ-
ïîëüçîâàíèå ÑÏ, êàê èñïîëíÿåìîé ñïåöèôèêàöèè, ÿâëÿåòñÿ ñðåäñòâîì ïðîâåðêè
ïðàâèëüíîñòè ïðèíÿòûõ ïðîåêòíûõ ðåøåíèé. Ìåòîä ïðîåêòèðîâàíèÿ âíà÷àëå èë-
ëþñòðèðóåòñÿ íà ïðîñòîì ïðèìåðå, à çàòåì ïðèìåíÿåòñÿ ê ïðîåêòèðîâàíèþ
ãðèä-ñòðóêòóðû è îáîñíîâàíèþ åå ñâîéñòâ.
ÒÐÀÍÇÈÖÈÎÍÍÛÅ ÑÈÑÒÅÌÛ È ÑÅÒÈ ÏÅÒÐÈ
Ââåäåì íåîáõîäèìûå îïðåäåëåíèÿ è ïîíÿòèÿ.
Îïðåäåëåíèå 1. Òðàíçèöèîííîé ñèñòåìîé (ÒÑ) íàçûâàåòñÿ ÷åòâåðêà
A S T s� ( , , , , )� � 0 , ãäå S — êîíå÷íîå èëè áåñêîíå÷íîå ìíîæåñòâî, ýëåìåíòû êîòîðî-
ãî íûçûâàþòñÿ ñîñòîÿíèÿìè; T — êîíå÷íîå èëè áåñêîíå÷íîå ìíîæåñòâî, ýëåìåíòû
êîòîðîãî íûçûâàþòñÿ ïåðåõîäàìè; � è � — äâà îòîáðàæåíèÿ èç T â S , ñòàâÿùèå â ñî-
îòâåòñòâèå êàæäîìó ïåðåõîäó t T� äâà ñîñòîÿíèÿ: �( )t è �( )t , êîòîðûå íàçûâàþòñÿ
ñîîòâåòñòâåííî íà÷àëîì è êîíöîì ïåðåõîäà t ; s S0 � — íà÷àëüíîå ñîñòîÿíèå ÒÑ.
Òðàíçèöèîííàÿ ñèñòåìà A S T s� ( , , , , )� � 0 íàçûâàåòñÿ êîíå÷íîé, åñëè ìíî-
æåñòâà S è T êîíå÷íû. Äàëåå áóäåì ðàññìàòðèâàòü òîëüêî êîíå÷íûå ÒÑ. Îíè èçî-
áðàæàþòñÿ â âèäå îðãðàôà, âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ ñîñòîÿíèÿ ÒÑ, à äóãà-
ìè — ïåðåõîäû.
Ôóíêöèè � è � áóäåì çàïèñûâàòü â âèäå òðîéêè ( , , )s t s� , ãäå s s S, � � , t T� ,
�( )t s� , �( ) .t s� �
Ïóòåì äëèíû n ( )n � 0 â ÒÑ A S T s� ( , , , , )� � 0 íàçûâàåòñÿ ïîñëåäîâàòåëü-
íîñòü ïåðåõîäîâ t t tn1 2, , ,� òàêèõ, ÷òî äëÿ ëþáîãî i i n, 1 � � , èìååò ìåñòî ðà-
âåíñòâî � �( ) ( )t ti i� �1 . Àíàëîãè÷íî áåñêîíå÷íûì ïóòåì íàçûâàåòñÿ áåñêîíå÷íàÿ
ïîñëåäîâàòåëüíîñòü ïåðåõîäîâ t t tn1 2, , , ,� � òàêèõ, ÷òî äëÿ ëþáîãî i � 1 èìååò
ìåñòî ðàâåíñòâî � �( ) ( )t ti i� �1 .
Îïðåäåëåíèå 2. Ïóñòü X — íåêîòîðûé àëôàâèò. Ïîìå÷åííîé ÒÑ (ÏÒÑ) íà-
çûâàåòñÿ ïÿòåðêà A S T s h� ( , , , , , )� � 0 , ãäå ( , , , , )S T s� � 0 ÿâëÿåòñÿ ÒÑ, h — îòî-
áðàæåíèå èç T â X , ïðèïèñûâàþùåå êàæäîìó ïåðåõîäó t åãî îòìåòêó h t X( ) � .
Èíòóèòèâíî îòìåòêà ïåðåõîäà îçíà÷àåò äåéñòâèå èëè ñîáûòèå, êîòîðîå ïðî-
âîöèðóåò ýòîò ïåðåõîä. ÏÒÑ ìîæåò áûòü è íåäåòåðìèíèðîâàííîé. Â çàäàííîì
ñîñòîÿíèè îäíî è òî æå äåéñòâèå ìîæåò ïðîâîöèðîâàòü äâà ðàçíûõ ïåðåõîäà
â äâà ðàçíûõ ñîñòîÿíèÿ, ò.å. èç � �( ) ( )t t� � è h t h t( ) ( )� � íå ñëåäóåò, ÷òî t t� �.
Êîíå÷íûé X -àâòîìàò (ÊÀ) ïðåäñòàâëÿåò ñîáîé ÒÑ. Äåéñòâèòåëüíî, ïóñòü
A A X f a� ( , , , )0 — êîíå÷íûé X -àâòîìàò. Òîãäà åìó ñîîòâåòñòâóåò ÒÑ
A A T a hT � ( , , , , , )� � 0 , ãäå t T� , ïðè ýòîì åñëè f a x a( , ) � �, òî t a x a� �( , , ) è
h t x( ) � , ãäå �( )t a� , �( )t a� �.
Ïðîèçâåäåíèå ÒÑ. Ïóñòü A An1, ,� — òðàíçèöèîííûå ñèñòåìû, ãäå
A S Ti i i i� ( , , � , � i
ia, )
0
, i n�1, ,� .
Îãðàíè÷åíèåì ñèíõðîíèçàöèè íàçûâàåòñÿ ïîäìíîæåñòâî Ò ìíîæåñòâà
( ) ( ) \ ( , , )T Tn1
{ } { } { }� � � �� � ,
ãäå � — òîæäåñòâåííûé ïåðåõîä, êîòîðûé îçíà÷àåò îòñóòñòâèå êàêîãî-ëèáî äåé-
ñòâèÿ â ÒÑ. Ýëåìåíòû èç Ò íàçûâàþòñÿ ãëîáàëüíûìè ïåðåõîäàìè. Åñëè
t t tn� �( , , )1 � Ò è ti � �, òî ñ÷èòàþò, ÷òî ÒÑ Ai ó÷àñòâóåò â ïåðåõîäå t.
Êîðòåæ A A An� ( , , , )1 � T íàçûâàåòñÿ ïðîèçâåäåíèåì ÒÑ, à ÒÑ A An1, ,�
íàçûâàþòñÿ êîìïîíåíòàìè A. Èíòóèòèâíî ãëîáàëüíûé ïåðåõîä t t tn� ( , , )1 � ìî-
äåëèðóåò âîçìîæíûå ïåðåõîäû â A An1, ,� . Åñëè ïåðåõîä ti � �, òî ÒÑ Ai íå
ó÷àñòâóåò â ãëîáàëüíîì ïåðåõîäå t.
Ãëîáàëüíûì ñîñòîÿíèåì A A A An� ( , , , , )1 2 � T íàçûâàåòñÿ n-êà ( , , , )s s sn1 2 � ,
ãäå s Si i� , à ñîñòîÿíèå ( , , , )s s sn
0
1
0
2
0
� íàçûâàåòñÿ íà÷àëüíûì ñîñòîÿíèåì TC A.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 123
Øàãîì âû÷èñëåíèé A íàçûâàåòñÿ òðîéêà ( , , )s t s� , ãäå s s� ( 1, s sn2 , , )� è
� � � � �s s s sn( , , , )1 2 � — ãëîáàëüíûå ñîñòîÿíèÿ, à t t t tn� ( , , , )1 2 � — ãëîáàëüíûé
ïåðåõîä, êîòîðûé óäîâëåòâîðÿåò � �i n{ }1 2, , ,� òàêèì óñëîâèÿì:
— åñëè ti � �, òî s ti i� �( ) è � �s ti i�( );
— åñëè ti � �, òî � �s si i .
Ãëîáàëüíûé ïåðåõîä t íàçûâàåòñÿ äîïóñòèìûì â ãëîáàëüíîì ñîñòîÿíèè s, åñëè
ñóùåñòâóåò ãëîáàëüíîå ñîñòîÿíèå �s òàêîå, ÷òî ( , , )s t s� ÿâëÿåòñÿ øàãîì âû÷èñëåíèÿ.
Ïîñëåäîâàòåëüíîñòü ãëîáàëüíûõ ïåðåõîäîâ t t tk1 2, , , ,� � íàçûâàåòñÿ ãëîáàëü-
íûì âû÷èñëåíèåì, åñëè ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü ãëîáàëüíûõ ñîñòîÿíèé
s0 , s sk1, ,� ,… òàêàÿ, ÷òî ( , , )s t si i i
1 — øàã âû÷èñëåíèé äëÿ êàæäîãî
i k�{ }1 2, , ,� .
Ìíîãèå ñâîéñòâà ïðîèçâåäåíèÿ ÒÑ ìîæíî èññëåäîâàòü ìîäåëèðîâàíèåì ñå-
òÿìè Ïåòðè.
Ïðîèçâåäåíèå òðàíçèöèîííûõ ñèñòåì è ñåòè Ïåòðè. Ñåòü Ïåòðè ( , , , )P T F M0
ìîäåëèðóåò ïðîèçâåäåíèå A A A A Tn� ( , , , , )1 2 � òðàíçèöèîííûõ ñèñòåì Ai �
� ( , , , , )S T si i i i
i� �
0
, ãäå A Ai j� � � ïðè i j� , i j n, , , ,�1 2 � , åñëè P S� 1
S S n2 � ; T � Ò , F s t ti� �{( , ) | ,� s ti i� � ( )} {( , ) |t s ti � � è s ti i� � ( )}
äëÿ íåêîòîðîãî i n�{ }1 2, , ,� , ãäå ti îçíà÷àåò i-þ êîìïîíåíòó t T� ;
M s s sn
0 0
1
0
2
0
� ( , , , )� .
Íåòðóäíî çàìåòèòü, ÷òî ñåìàíòèêà ïðîèçâåäåíèÿ ÒÑ è ñåìàíòèêà ÑÏ, êîòîðàÿ åãî
ìîäåëèðóåò, ñîãëàñîâàíû, ò.å. ïîñëåäîâàòåëüíîñòü ãëîáàëüíûõ ïåðåõîäîâ t t tk1 2 �
ïðåäñòàâëÿåò ñîáîé ãëîáàëüíóþ èñòîðèþ ïðîèçâåäåíèÿ ÒÑ A òîãäà è òîëüêî òîãäà,
êîãäà îíà ÿâëÿåòñÿ äîïóñòèìîé ïîñëåäîâàòåëüíîñòüþ ñðàáàòûâàíèé ïåðåõîäîâ â ÑÏ.
Ïðåäñòàâëåíèå ïðîèçâåäåíèÿ ÒÑ â âèäå ÑÏ ïîçâîëÿåò ïðèìåíèòü ìåòîäû àíàëè-
çà ñâîéñòâ ÑÏ äëÿ àíàëèçà ñâîéñòâ ïðîèçâåäåíèÿ ÒÑ.
Ìîäåëèðîâàíèå ïðîèçâåäåíèÿ X -àâòîìàòîâ ñ ïîìîùüþ ïðîèçâåäåíèÿ ÒÑ
âûïîëíÿåòñÿ çà äâà ýòàïà. Íà ïåðâîì ýòàïå àâòîìàòû ìîäåëèðóþòñÿ ñîîòâåòñòâó-
þùèìè ÒÑ, à íà âòîðîì — ïðîèçâåäåíèåì ïîëó÷åííûõ ÒÑ. Çàòåì òàêàÿ ÒÑ ìîäå-
ëèðóåòñÿ ñîîòâåòñòâóþùåé ÑÏ.
Ïðîèëëþñòðèðóåì ñêàçàííîå íà ïðèìåðå.
Ïðèìåð 1. Ïóñòü èìååì X -àâòîìàòû À1 (ðèñ. 1, à) è À2 (ðèñ. 1, á) è ñîîòâåò-
ñòâóþùèå ÒÑ T1 è T2 äëÿ àâòîìàòîâ À1 (ðèñ. 2, à) è À2 (ðèñ. 2, á). Â ýòèõ ÒÑ èìå-
åì ìíîæåñòâà ïåðåõîäîâ:
t i t i t d t d t1 2 3 4 50 1 1 2 2 1 1 0 0� � � � �( , , ), ( , , ), ( , , ), ( , , ), ( , d t i, ), ( , , )2 2 06 � ,
u a f a u a t b u b t b u b f a1 2 3 4� � � �( , , ), ( , , ), ( , , ), ( , , ).
Ïðåäïîëîæèì, ÷òî ïðîåêòèðîâùèê îïðåäåëèë îãðàíè÷åíèÿ ñèíõðîíèçàöèè
Ò � {( , ), ( , ), ( , ), ( , ), ( , ), ( , ), (t t t u t u t t u1 2 3 2 4 4 5 6 1� � � �, )u3 }.
Òîãäà ïðîèçâåäåíèå ÒÑ îïðåäåëÿ-
åòñÿ êàê A T T� ( , , )1 2 Ò . Ñîîòâåò-
ñòâóþùàÿ ÑÏ, ìîäåëèðóþùàÿ ñèí-
õðîííîå ïðîèçâåäåíèå A, ïðåä-
ñòàâëåíà íà ðèñ. 3.
Ïóñòü íà÷àëüíàÿ ðàçìåòêà ÑÏ
ñòàâèò â ìåñòà 0 è a ïî îäíîé ôèø-
êå. Íå ÿâëÿåòñÿ î÷åâèäíûì òî, ÷òî
ïðè ýòîé ðàçìåòêå ÑÏ èìååò òóïèê,
ê êîòîðîìó ïðèâîäèò ïîñëåäîâà-
òåëüíîñòü ãëîáàëüíûõ ïåðåõîäîâ
( , ), ( , ), ( , )t t u t5 3 2 2� � .
124 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1
20 1
d
d d
i i
i
Ðèñ. 1
ba
t
f
tf
à á
20 1
t5
t4 t3
t1 t2
t6
Ðèñ. 2
ba
u2
u4
u3u1
à á
Äåéñòâèòåëüíî, ýòà ïîñëåäîâàòåëüíîñòü ñðàáàòûâàíèé ïåðåõîäîâ ïðèâîäèò
ê ðàçìåòêå ÑÏ, ïîêàçàííîé íà ðèñ. 4, ïðè êîòîðîé â ÑÏ íåâîçìîæåí íè îäèí ïåðå-
õîä. Ñëåäîâàòåëüíî, àâòîìàòû ïîïàäàþò â ñîñòîÿíèå ( , )2 b , èç êîòîðîãî â T íå ñó-
ùåñòâóåò ïåðåõîäîâ. Íàëè÷èå òóïèêà â ÑÏ îçíà÷àåò îøèáêó ðàçðàáîò÷èêà, è âàæ-
íûì ÿâëÿåòñÿ îáíàðóæåíèå ïîäîáíîãî òèïà îøèáîê íà ýòàïå ïðîåêòèðîâàíèÿ.
Ñèòóàöèè òàêîãî òèïà èäåíòèôèöèðóþòñÿ â ÑÏ, ÷åì è îáóñëîâëåíî èõ èñ-
ïîëüçîâàíèå.
ÐÀÇÐÀÁÎÒÊÀ ÃÐÈÄ-ÑÒÐÓÊÒÓÐÛ
Ðàáîòà ïîëüçîâàòåëÿ â ãðèä-ñèñòåìå ñîñòîèò â ñëåäóþùåì. Ïîëüçîâàòåëü ïîñû-
ëàåò çàïðîñ ê ÏÏÎ íà ðåãèñòðàöèþ â ãðèä-ñèñòåìå, ïîëó÷àåò ïåðñîíàëüíûé
öèôðîâîé ñåðòèôèêàò, ðåãèñòðèðóåòñÿ â âèðòóàëüíîé îðãàíèçàöèè (ÂÎ), ïîäãî-
òàâëèâàåò è çàïóñêàåò ñâîè çàäàíèÿ. Ïîäãîòîâêà çàäàíèé ñîñòîèò â ôîðìèðîâà-
íèè ôàéëîâ-îïèñàíèé çàäàíèé, ïîäãîòîâêè âõîäíûõ äàííûõ, ñîçäàíèÿ ïðîêñè
ñåðòèôèêàòà. Ïîñëå ýòèõ ïîäãîòîâèòåëüíûõ äåéñòâèé çàäàíèÿ îòïðàâëÿþòñÿ
â ãðèä è â çàâèñèìîñòè îò çàãðóæåííîñòè ðåñóðñîâ âûïîëíÿþòñÿ èëè ñòàâÿòñÿ
â î÷åðåäü íà âûïîëíåíèå [2, 3, 5, 6].
Îñíîâíûå òðåáîâàíèÿ ïðè ðàçðàáîòêå ãðèä-ñèñòåìû — êîððåêòíîñòü åå
ôóíêöèîíèðîâàíèÿ, êîíòðîëü çà ïðàâèëüíîñòüþ âûïîëíåíèÿ óñëîâèé ðàáîòû
â ñèñòåìå, ïðàâèëüíîñòü âû÷èñëåíèé è âîçâðàò ðåçóëüòàòîâ âûïîëíåíèÿ çàäàíèÿ
ïîëüçîâàòåëþ â ñëó÷àå èõ óñïåøíîãî çàâåðøåíèÿ. ×òîáû â ãðèä-ñèñòåìå ýòè òðå-
áîâàíèÿ óäîâëåòâîðÿëèñü, íåîáõîäèìî ïðèáåãíóòü ê ôîðìàëüíûì ìåòîäàì ïðî-
âåðêè èõ âûïîëíåíèÿ, ÷òî îáóñëîâëèâàåò ïîñòðîåíèå ñîîòâåòñòâóþùåé ìàòåìà-
òè÷åñêîé ìîäåëè, íà êîòîðîé è âûïîëíÿåòñÿ ýòà ïðîâåðêà. Ïîñêîëüêó ïîñòðîèòü
ìîäåëü ãðèä-ñèñòåìû ñ ó÷åòîì âñåõ ïðèñóùèõ åé îñîáåííîñòåé ïðàêòè÷åñêè
íåâîçìîæíî ââèäó åå áîëüøîé ñëîæíîñòè, òî òàêîå ïîñòðîåíèå âûïîëíÿåòñÿ íà
íåêîòîðîì óðîâíå àáñòðàêöèè.
Òàêèì îáðàçîì, ðàáîòà â ãðèä-ñèñòåìå íà÷èíàåòñÿ ñ âûïîëíåíèÿ äâóõ ïðîòîêî-
ëîâ: ðåãèñòðàöèè â ãðèä-ñèñòåìå è ïîäãîòîâêè çàäàíèÿ. Âûïîëíåíèå äåéñòâèé,
ïðåäóñìîòðåííûõ ýòèìè ïðîòîêîëàìè, îäíîðàçîâûå. Ýòî çíà÷èò, ÷òî åñëè ïðîòîêî-
ëû ðåãèñòðàöèè è ïîäãîòîâêè çàäàíèÿ âûïîëíèëèñü óñïåøíî, òî áîëüøå íèêàêèå äåé-
ñòâèÿ ñ íèìè íå âûïîëíÿþòñÿ. Åñëè æå äåéñòâèÿ ïî ðåãèñòðàöèè ïî êàêèì-ëèáî
ïðè÷èíàì íå âûïîëíèëèñü, òî îá ýòîì ñîîáùàåòñÿ ïîëüçîâàòåëþ, è îí ïîâòîðÿåò ïî-
ïûòêó ðåãèñòðàöèè. Ïðåäñòàâèì äåéñòâèÿ îáîèõ ïðîòîêîëîâ â âèäå òðàíçèöèîííûõ
ñèñòåì [1, 4], êîòîðûå äîñòàòî÷íî î÷åâèäíû â ñèëó ñâîåé ïðîñòîòû.
1. Ïðîòîêîë ðåãèñòðàöèè â ãðèä-ñèñòåìå. Äåéñòâèÿ ýòîãî ïðîòîêîëà ñî-
ñòîÿò â ñëåäóþùåì. Ïðåæäå ÷åì ïîëó÷èòü äîñòóï ê âû÷èñëèòåëüíûì ðåñóðñàì,
íåîáõîäèìî çàðåãèñòðèðîâàòüñÿ â ñèñòåìå è ïîëó÷èòü ñåðòèôèêàò. Ñ ýòîé öåëüþ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 125
b
a
1(t5, �)
0
2
(t1, �)
(t2, �)
(�, u3)
(t6, u1)
(t3, u2)
(t4, u4)
Ðèñ. 3
b
a
1(t5, �)
0
2
(t1, �)
(t2, �)
(�, u3)
(t6, u1)
(t3, u2)
(t4, u4)
Ðèñ. 4
ïîëüçîâàòåëü ñî ñâîåãî ðàáî÷åãî
ìåñòà ïîñûëàåò çàïðîñ íà ðåãèñòðà-
öèþ â ãðèäå, ïîëó÷àåò ïîäïèñàííûé
äîâåðåííûì öåíòðîì ñåðòèôèêàò è
òåì ñàìûì ðåãèñòðèðóåòñÿ â ñèñòå-
ìå. Ýòè äåéñòâèÿ ìîäåëèðóþòñÿ
ïðîñòîé ÒÑ À a à à à1 0 1 2 3� ({ , , , },
{ , , , }t t t t1 2 3 4 , � �1 1, , a0 ) (ðèñ. 5).
Èíòåðïðåòàöèÿ ìåñò è ïåðåõî-
äîâ â äàííîé ÒÑ ñëåäóþùàÿ: a0 —
ôîðìèðîâàíèå çàïðîñà (ãåíåðàöèÿ
ñåðòèôèêàòà ïîëüçîâàòåëåì); t1 —
çàïðîñ íà ðåãèñòðàöèþ (îòïðàâêà
ñåðòèôèêàòà â äîâåðåííûé öåíòð),
ãäå �1 1 0( )t a� , �1 1 1( )t a� ; a1 —
îáðàáîòêà çàïðîñà (ïðîâåðêà ïîëüçîâàòåëÿ); t2 — ïðîöåññ ðåãèñòðàöèè (ïîä-
ïèñü ñåðòèôèêàòà), ãäå �1 2 1( )t a� , �1 2 2( )t a� ; a2 — àíàëèç ïðîöåññà ðåãèñòðà-
öèè; t3 — ðåãèñòðàöèÿ âûïîëíåíà, ãäå �1 3 3( )t a� , �1 3 4( )t a� ; a3 — ðåãèñòðà-
öèÿ ïîëüçîâàòåëÿ (ïîëó÷åíèå ïîëüçîâàòåëåì ïîäïèñàííîãî ñåðòèôèêàòà), t4 —
ðåãèñòðàöèÿ íå âûïîëíåíà (îòêàç â ïîäïèñè), ãäå �1 4 2( )t a� , �1 4 0( )t a� .
Åñëè ðåãèñòðàöèÿ âûïîëíåíà óñïåøíî (ñîñòîÿíèå a3 â ÒÑ), òî ñèñòåìà ðå-
ãèñòðàöèè èíôîðìèðóåò ïîëüçîâàòåëÿ è ÏÏÎ î ëåãàëüíîì ïîëüçîâàòåëå. Åñëè ðå-
ãèñòðàöèÿ ïî êàêèì-ëèáî ïðè÷èíàì â ñèñòåìå íå âûïîëíåíà, òî â ñîñòîÿíèè a2
ñèñòåìà ðåãèñòðàöèè âûïîëíÿåò äåéñòâèå t4 , êîòîðîå èíôîðìèðóåò ïîëüçîâàòåëÿ
î òîì, ÷òî îí íå ïðîøåë ðåãèñòðàöèè â ñèñòåìå.
Âòîðûì ýòàïîì ðàáîòû â ãðèä-ñèñòåìå åñòü ïîëó÷åíèå ÷ëåíñòâà â îäíîé èëè
íåñêîëüêèõ äîñòóïíûõ âèðòóàëüíûõ îðãàíèçàöèÿõ. Â ðàìêàõ äàííîé ñòàòüè ðàñ-
ñìàòðèâàåòñÿ ñèòóàöèÿ ÷ëåíñòâà ïî óìîë÷àíèþ â îäíîé èç ÂÎ.
2. Ïðîòîêîë ïîäãîòîâêè çàäàíèÿ. Ïðîéäÿ óñïåøíî ðåãèñòðàöèþ è ïîëó÷èâ
öèôðîâîé ñåðòèôèêàò äîñòóïà ê ãðèä-ñòðóêòóðå, ïîëüçîâàòåëü ïðèñòóïàåò ê âû-
ïîëíåíèþ ïðîòîêîëà ïîäãîòîâêè ñâîåãî çàäàíèÿ. Ïðè ýòîì ïðåäóñìàòðèâàåòñÿ
ñëåäóþùàÿ ïîñëåäîâàòåëüíîñòü äåéñòâèé: à) ñîçäàòü ôàéë-îïèñàíèå çàäàíèÿ;
á) ïîäãîòîâèòü äàííûå; â) îïðåäåëèòü ìåñòî ðàñïîëîæåíèÿ äàííûõ (çàãðóçêà
ñ ëîêàëüíûõ íîñèòåëåé èëè èç ãðèä-õðàíèëèù); ã) ñîçäàòü ïðîêñè ñåðòèôèêàò ñ
íåîáõîäèìûìè àòðèáóòàìè äîñòóïà.
Ïðîòîêîë ìîäåëèðóåòñÿ òðàíçèöèîííîé ñèñòåìîé À2 1 2 3 4 5 6 7� ({ , , , , , , },
{ , , , , }r r r r r1 2 3 4 5 , � �2 2 1, , ) (ðèñ. 6).
Èíòåðïðåòàöèÿ ìåñò è ïåðåõîäîâ â äàííîé ÒÑ òàêîâà: 1 — ñòàðò ôîðìèðîâà-
íèÿ çàäàíèÿ, r1 — ñîçäàíèå ôàéëà-îïèñàíèÿ çàäàíèÿ, 2 — ñòàðò ïîäãîòîâêè äàí-
íûõ, ôàéë-îïèñàíèÿ ñîçäàí, r2 — ïîäãîòîâêà äàííûõ, 3 — àíàëèç ðàñïîëîæåíèÿ
äàííûõ, r3— ïîäãîòîâêà äàííûõ íà ëîêàëüíûõ íîñèòåëÿõ, 4 — ëîêàëüíûå äàí-
íûå ãîòîâû, r4— ïîäãîòîâêà äàííûõ èç ãðèä-õðàíèëèù, 5 — äàííûå èç õðàíè-
ëèù ãîòîâû, r5 — ñîçäàíèå ïðîêñè ñåðòèôèêàòà ñ íåîáõîäèìûìè àòðèáóòàìè
äîñòóïà, 6 — ñîñòîÿíèå ãîòîâíîñòè äàííûõ èç ãëîáàëüíûõ ãðèä-õðàíèëèù, 7 — ñî-
ñòîÿíèå ãîòîâíîñòè äàííûõ ñ ëîêàëüíûõ íîñèòåëåé.
Ïðè ïåðåõîäå â ñîñòîÿíèå 6 ÒÑ äîëæíà èíôîðìèðîâàòü ïîëüçîâàòåëÿ î ãî-
òîâíîñòè çàäàíèÿ è ÏÏÎ îá ýòîé ãîòîâíîñòè. Ñ ýòîé öåëüþ ââîäÿòñÿ äîïîëíè-
òåëüíûå ñîñòîÿíèÿ â ìîäåëè, ïðåäñòàâëÿþùåé ñèíõðîííîå ïðîèçâåäåíèå
ïðèâåäåííûõ ÒÑ, â âèäå ñåòè Ïåòðè.
126 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1
a0 a1
t1 t2 t3
a2 a3
t4
Ðèñ. 5
1 2 3
7
r1 r2
r3 4
5r4
r5
r5
6
Ðëîê.
Ðãëîá.
Ðèñ. 6
ÑÅÒÅÂÀß ÌÎÄÅËÜ ÏÐÎÒÎÊÎËÎÂ ÐÅÃÈÑÒÐÀÖÈÈ È ÏÎÄÃÎÒÎÂÊÈ ÇÀÄÀÍÈß
Ïîñòðîèì ìîäåëü ðåãèñòðàöèè è ïîäãîòîâêè çàäàíèÿ â âèäå ñèíõðîííîãî ïðî-
èçâåäåíèÿ äâóõ ÒÑ: À À1 2* ñ ãëîáàëüíûìè ïåðåõîäàìè:
T t t t r t r r r� {( , ), ( , ), ( , ), ( , ) ( , ), ( , ), ( ,1 2 3 1 4 2 3 4� � � � � � ), ( , ), ( , )}� �r r5 6 .
Ïî ýòîé ÒÑ ñòðîèì ñåòü Ïåòðè, êîòîðàÿ ìîäåëèðóåò ñèíõðîííîå ïðîèçâåäå-
íèå ÒÑ îáåèõ ñèñòåì (ðèñ. 7). Â ýòîé ÑÏ êðîìå ìåñò ñèíõðîííîãî ïðîèçâåäå-
íèÿ âûøåïðèâåäåííûõ ÒÑ ïîÿâëÿþòñÿ ìåñòà, ïîëó÷åííûå â ðåçóëüòàòå âûïîë-
íåíèÿ ñèíõðîííîãî ïðîèçâåäåíèÿ äàííûõ ÒÑ, à òàêæå ÒÑ, êîòîðàÿ ìîäåëèðóåò
âû÷èñëèòåëüíóþ ñðåäó (ïî ìåñòàì 10, 11, 12 è 14 ñîåäèíÿþòñÿ îáå ñåòè).
ÒÑ âû÷èñëèòåëüíîé ñðåäû è ñèíõðîííîå ïðîèçâåäåíèå ñîîòâåòñòâóþùèõ ÒÑ
ââèäó ãðîìîçäêîñòè íå ïðèâîäÿòñÿ, à îòäåëüíûå ìîìåíòû òàêîãî ïðîöåññà
ïðîäåìîíñòðèðîâàíû ðàññìîòðåííûì âûøå ïðèìåðîì. Íèæå ïðåäñòàâëåí
îêîí÷àòåëüíûé ðåçóëüòàò ïðîåêòèðîâàíèÿ â âèäå ñåòè Ïåòðè ñ îïèñàíèåì ìåñò
è ïåðåõîäîâ â íåé:
ìåñòî 3 ñîîòâåòñòâóåò ïîëüçîâàòåëþ À, êîòîðûé èíèöèàëèçèðóåò (ñòàâèò
ôèøêó â ýòî ìåñòî) íà÷àëî ðàáîòû ñ ãðèä-ñèñòåìîé;
ìåñòî 4 èíôîðìèðóåò ïîëüçîâàòåëÿ î ïîëó÷åíèè ñåðòèôèêàòà è ãîòîâíîñòè
çàäàíèÿ ê âûïîëíåíèþ;
ìåñòà 2 è 10 èíôîðìèðóþò ïîëüçîâàòåëÿ è ÏÏÎ ñîîòâåòñòâåííî îá óñïåø-
íîì ïðîõîæäåíèè ïðîöåññà ðåãèñòðàöèè è ïîëó÷åíèè ñåðòèôèêàòà;
ìåñòî 11 (Ðëîê.) îçíà÷àåò ëîêàëüíîñòü äàííûõ, à ìåñòî 12 (Pãëîá.) îçíà÷àåò,
÷òî äàííûå íà íîñèòåëÿõ íàõîäÿòñÿ â õðàíèëèùàõ;
ìåñòî 14 îçíà÷àåò, ÷òî ñîçäàí ïðîêñè ñåðòèôèêàò ñ ïàðàìåòðîì k.
ÌÎÄÅËÜ ÂÛ×ÈÑËÈÒÅËÜÍÎÉ ÑÐÅÄÛ
Ïðè ïîñòðîåíèè ìîäåëè âû÷èñëèòåëüíîé ñðåäû (ÂÑ) ãðèä-ñèñòåìû áóäåì ïðåä-
ïîëàãàòü, ÷òî âñå âû÷èñëèòåëüíûå ñðåäñòâà ðàíæèðîâàíû ÷èñëàìè k k km1 2, , ,� ,
ãäå m — êîëè÷åñòâî âû÷èñëèòåëåé, k ³ — ïàðàìåòðû âû÷èñëèòåëÿ ³. Îïèøåì
âíîâü ïîÿâèâøèåñÿ ìåñòà:
ìåñòà 15, 16, …, s — õðàíèëèùà äàííûõ ( , , , )Ä Ä Ä1 2 � s ;
ìåñòî 17 — íàéäåí âû÷èñëèòåëü ñ íóæíûìè ïàðàìåòðàìè (ìåñòà 22, 23) (âû-
÷èñëèòåëü ñ ïàðàìåòðàìè k1 (ìåñòî 24) íå èìååò òðåáóåìûõ ïàðàìåòðîâ ( ))k k1 � ;
ìåñòà 20, 21, 22, 23, 24, 25 ñîîòâåòñòâóþò âû÷èñëèòåëþ è åãî çàíÿòîñòè;
ìåñòî 18 — äàííûå çàãðóæåíû;
ìåñòî 19 — âû÷èñëåíèÿ;
ìåñòî 27 — ñîñòîÿíèå àâàðèè;
ìåñòî 26 — ñîñòîÿíèå âîññòàíîâëåíèÿ ðàáîòîñïîñîáíîñòè êëàñòåðà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 127
Ðåçóëüòàò âû÷èñëåíèé
îò ïåðåõîäà t15
5 6 7 8
9
13
Èíôîðìàöèÿ î ðåãèñòðàöèè 11
10
12
14
1
(t3, r1)
2
3
4
At1
t2 t3 t4 t5
t6
t19
t8
t9
t7
k
(t1, �) (t2, �)
(t4, �)
(a0,1)
(a1,1) (a2,1) (a3,2)
(�, r2)
(�, r4)
(a3,5)
(�, r6)
Pãëîá.
Pëîê.
(�, r5)
(a3,3)
(�, r3)
(a3,4)
Ðèñ. 7
Ïåðåõîäû: t10 — èíèöèàëèçàöèÿ òðåáóåìûõ äàííûõ íà íîñèòåëÿõ; t11 — ïî-
èñê âû÷èñëèòåëÿ; t12 — èíèöèàëèçàöèÿ è çàãðóçêà ëîêàëüíûõ äàííûõ; t13 — çà-
ãðóçêà äàííûõ èç õðàíèëèù; t14 — çàïóñê âû÷èñëåíèé; t15 — îêîí÷àíèå âû÷èñ-
ëåíèé; t16 — èíèöèàëèçàöèÿ àâàðèéíîãî ñîñòîÿíèÿ è âîçîáíîâëåíèå ïàðàìåòðîâ
çàäàíèÿ è äàííûõ â öåëÿõ ïîèñêà äðóãîãî èñïðàâíîãî âû÷èñëèòåëÿ ñ íóæíûìè
ïàðàìåòðàìè è âîçîáíîâëåíèå âû÷èñëåíèé; t17 — èíèöèàëèçàöèÿ âîçîáíîâëåíèÿ
ðàáîòîñïîñîáíîñòè êëàñòåðà; t18 — âîññòàíîâëåíèå ðàáîòîñïîñîáíîñòè êëàñòåðà.
 ïðèâåäåííîé ÑÏ ïåðåõîäû, ïîäîáíûå ïåðåõîäó t12 , ñðàáàòûâàþò ïðè óñëî-
âèè èñïðàâíîñòè âû÷èñëèòåëÿ (îòñóòñòâèå ôèøêè â ìåñòå 27), åãî íåçàíÿòîñòè (íà-
ëè÷èå ôèøêè â ìåñòå 22) è íàëè÷èÿ òðåáóåìûõ ïàðàìåòîâ (â ìåñòå 23 íàõîäèòñÿ
k k� 2 ôèøåê).  ñîîòâåòñòâèè ñ ýòèìè óñëîâèÿìè âûáèðàåòñÿ âû÷èñëèòåëü ñ òðåáó-
åìûìè ïàðàìåòðàìè.  ñëó÷àå çàíÿòîñòè èëè íåèñïðàâíîñòè âû÷èñëèòåëÿ èùåòñÿ
äðóãîé íåçàíÿòûé è èñïðàâíûé âû÷èñëèòåëü ñ íóæíûìè ïàðàìåòðàìè, íà êîòîðîì
è âûïîëíÿåòñÿ çàäàíèå ïîëüçîâàòåëÿ (â ïðèâåäåííîì ïðèìåðå ÑÏ ïåðåõîä �t11 íå
ñðàáàòûâàåò, ïîñêîëüêó k k1 � ). Åñëè âû÷èñëèòåëü ñ òðåáóåìûìè ïàðàìåòðàìè
â äàííûé ìîìåíò îòñóòñòâóåò, òî çàäàíèå ïîëüçîâàòåëÿ æäåò ñâîåé î÷åðåäè.
Ñåòåâàÿ ìîäåëü ãðèä-ñèñòåìû, ñîñòîÿùàÿ èç òðåõ êëàñòåðîâ ñ ýëåìåíòàìè,
ïðåäñòàâëåíà íà ðèñ. 8.
ÎÁÎÑÍÎÂÀÍÈÅ ÑÅÒÅÂÎÉ ÌÎÄÅËÈ ÃÐÈÄ-ÑÈÑÒÅÌÛ
Ïîñòðîèâ ñåòü Ïåòðè, êîòîðàÿ ìîäåëèðóåò ãðèä-ñèñòåìó, ïîëó÷àåì âûïîëíÿå-
ìóþ ñïåöèôèêàöèþ äàííîãî ïðîåêòà òàêîé ñèñòåìû, êîòîðàÿ ÿâëÿåòñÿ ïðè ýòîì
è ìàòåìàòè÷åñêîé ìîäåëüþ ïðîåêòèðóåìîé ãðèä-ñòðóêòóðû. Òåïåðü çàäà÷à ñî-
ñòîèò â òîì, ÷òîáû ïðîâåðèòü êîððåêòíîñòü ïîñòðîåííîé ìîäåëè. Ïåðâîå çàäà-
íèå ñâîäèòñÿ ê òîìó, ÷òîáû óáåäèòüñÿ â æèâó÷åñòè òàêîé ñèñòåìû, ò.å. ÷òî
â ïîñòðîåííîé ìîäåëè âñå ïåðåõîäû ïðèíèìàþò ó÷àñòèå â ïðîöåññå åå ôóíêöè-
128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1
…
k
12
Pãëîá. t10
Ä1
15
10
14
11 Pëîê.
1
Ä2
16
Äs
k
k1
t11
t12
18
19
k
k
k
t16
t15
20
25
24
k2
23
t18 26
t11'
t1722
k3 27
21
t11''
17 t13
t14
Ðèñ. 8
îíèðîâàíèÿ (âñå ïåðåõîäû æèâûå). Åñëè íåêîòîðûå ïåðåõîäû â ÑÏ íå ñðàáàòû-
âàþò, òî ýòî ñâèäåòåëüñòâóåò î òîì, ÷òî â ïðîåêòå ñèñòåìû ÷òî-òî âûïîëíåíî
íåïðàâèëüíî èëè äàííûå ïåðåõîäû èçáûòî÷íû. Ýòî îòíîñèòñÿ è ê ìåñòàì ÑÏ.
Åñëè íåêîòîðûå ìåñòà ââèäó íàëè÷èÿ ìåðòâûõ ïåðåõîäîâ íåäîñòèæèìû â ïðîöåñ-
ñå ôóíêöèîíèðîâàíèÿ ÑÏ, òî ýòî òàêæå ñâèäåòåëüñòâóåò î äåôåêòàõ ïðîåêòà.
Ïðîâåðêà æèâó÷åñòè ÑÏ âûïîëíÿåòñÿ äâóìÿ ñïîñîáàìè: ñ ïîìîùüþ ïîñòðî-
åíèÿ ãðàôà äîñòèæèìûõ ðàçìåòîê ÑÏ è ïóòåì àíàëèçà èíâàðèàíòîâ ïåðåõîäîâ.
Ïîñòðîåíèå ìíîæåñòâà èíâàðèàíòîâ ïåðåõîäîâ ñâîäèòñÿ ê ðåøåíèþ óðàâíåíèÿ
ñîñòîÿíèÿ â ìíîæåñòâå íàòóðàëüíûõ ÷èñåë âèäà Ax � 0, ãäå A — ìàòðèöà èíöè-
äåíòíîñòè ÑÏ, à x — âåêòîð, çíà÷åíèÿ êîîðäèíàò êîòîðîãî ðàâíû êîëè÷åñòâó
ñðàáàòûâàíèé ñîîòâåòñòâóþùèõ ïåðåõîäîâ. Åñëè íåêîòîðàÿ êîîðäèíàòà âî âñåõ
âåêòîðàõ ðåøåíèÿõ ðàâíà íóëþ, òî ýòî çíà÷èò, ÷òî äàííûé ïåðåõîä íå ñðàáàòûâà-
åò â ïðîöåññå ôóíêöèîíèðîâàíèÿ ÑÏ (ïåðåõîä ìåðòâûé), êàêîâà áû íè áûëà
íà÷àëüíàÿ ðàçìåòêà ñèñòåìû.
Äëÿ äàííîé ÑÏ, ãäå ïðåäïîëàãàåòñÿ íàëè÷èå òðåõ êëàñòåðîâ-âû÷èñëèòåëåé
( )n � 3 , óðàâíåíèå ñîñòîÿíèÿ èìååò ìàòðèöó ðàçìåðà 19 27
, ïîñêîëüêó â ÑÏ èìå-
åòñÿ 19 ïåðåõîäîâ è 27 ìåñò:
Ïðèìåíÿÿ TSS-àëãîðèòì [4] äëÿ ðåøåíèÿ óðàâíåíèÿ ñîñòîÿíèÿ ñ âûøåïðèâå-
äåííîé ìàòðèöåé, ïîëó÷àåì òàêèå åãî ðåøåíèÿ, êîòîðûå ÿâëÿþòñÿ èíâàðèàíòàìè
ïåðåõîäîâ:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 129
Íîìåð ïåðåõîäà
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
2
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
4
1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
5 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
7 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 1
1
1 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 1 0 0 0
11 0 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 3 3 0
3 0 0 0 0 3 0 0 0
15 0 0 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0
16 0 0 0 0 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0
17 0 0 0 0 0 0 0 0 0 0 1
1
1 0 0 0 0 0 0
18 0 0 0 0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 0
19 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1
1 0 0 0
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 1 0
23 0 0 0 0 0 0 0 0 0 0
3 0 0 0 3 0 0 3 0
24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0
27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0
Í
î
ì
åð
ì
åñ
òà
Ñ
Ï
Êàê âèäíî èç ïðèâåäåííûõ ðåøåíèé, ïåðåõîäû 16, 17, 18 ÿâëÿþòñÿ ìåðòâûìè,
ïîñêîëüêó íè ðàçó íå ñðàáàòûâàþò â ïðîöåññå ôóíêöèîíèðîâàíèÿ ÑÏ. Ýòè ïå-
ðåõîäû ñâÿçàíû ñ àâàðèéíûì ñîñòîÿíèåì âû÷èñëèòåëÿ, à ýòî çíà÷èò, ÷òî â ñëó-
÷àå àâàðèè âû÷èñëèòåëÿ âîçîáíîâëåíèÿ âû÷èñëåíèé ïðîèñõîäèòü íå áóäåò. Ïðè-
÷èíà, ïî êîòîðîé ýòè ïåðåõîäû íå ñðàáàòûâàþò, ñâÿçàíà ñ íåîáõîäèìîñòüþ âîñ-
ñòàíîâëåíèÿ ïàðàìåòðîâ âû÷èñëèòåëÿ è âîññòàíàâëåíèÿ äàííûõ çàäàíèÿ. Èíûìè
ñëîâàìè, â ïðîåêòå ãðèä-ñòðóêòóðû, îïèñûâàåìîé äàííîé ìàòåìàòè÷åñêîé ìî-
äåëüþ, íåîáõîäèìû äåéñòâèÿ ïî âîññòàíîâëåíèþ êàê ïàðàìåòðîâ ïîëüçîâàòåëü-
ñêîé çàäà÷è, òàê è åå äàííûõ.
Êîððåêöèÿ ÑÏ ñâÿçàíà ñ ïåðåäà÷åé èíôîðìàöèè î âîçîáíîâëåíèè ÷òåíèÿ
äàííûõ (÷òî îçíà÷àåò ïîñûëêó â ìåñòî 12 èëè â ìåñòî 11 ôèøêè â çàâèñèìîñòè
îò ìåñòà íàõîæäåíèÿ ýòèõ äàííûõ). Êîððåêöèÿ ïðèâîäèò ê óðàâíåíèþ ñîñòîÿíèÿ
ñ òàêîé ìàòðèöåé A:
 äàííîé ñèòóàöèè ýòà ìàòðèöà ñîîòâåòñòâóåò ñëó÷àþ âîññòàíîâëåíèÿ ëîêàëü-
íûõ äàííûõ, î ÷åì ñâèäåòåëüñòâóþò ðåøåíèÿ óðàâíåíèÿ ñîñòîÿíèÿ ñ ïðèâå-
äåííîé ìàòðèöåé:
130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1
Íîìåð ïåðåõîäà
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0
1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
2 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
4 1 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0
5 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1
7 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
9
0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
11 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0
12 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 3 3 0 3 0 0 0 0 3 0 0 0
15 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 0
16 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0
17 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
18 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0
19 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0
20 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 1 0
23 0 0 0 0 0 0 0 0 0 0 3 0 0 0 3 0 0 3 0
24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
27 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 0
Í
î
ì
åð
ì
åñ
òà
Ñ
Ï
Íîìåð ïåðåõîäà
x
x
x
x
1
2
3
4
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 0 1 0 0 1 1 0 1 1
�
�
�
�
( ),
( 0 0 0 0
1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0
),
( ),
( ).
Êàê âèäèì, âñå ïåðåõîäû â òàêîé ñåòè æèâûå, ÷òî ñâèäåòåëüñòâóåò î æèâîñòè
âñåé ÑÏ â öåëîì. Ïåðâûé èíâàðèàíò îïèñûâàåò ñèòóàöèþ, êîãäà ðåãèñòðàöèÿ
â ãðèä-ñèñòåìå íå âûïîëíèëàñü (ñðàáàòûâàþò ïåðåõîäû 2, 3 è 19). Âòîðîé èí-
âàðèàíò îïèñûâàåò ñèòóàöèþ óñïåøíîé ðåãèñòðàöèè, ïîëó÷åíèÿ ñåðòèôèêàòà,
ëîêàëüíîñòü äàííûõ è óñïåøíîå âûïîëíåíèå âû÷èñëåíèé (ñðàáàòûâàþò ïåðå-
õîäû 2, 3, 4, 5, 6, 8, 11, 12, 14, 15 è 1). Òðåòèé èíâàðèàíò îïèñûâàåò òó æå
ñèòóàöèþ, íî ñ äàííûìè íà íîñèòåëÿõ (ñðàáàòûâàþò ïåðåõîäû 2, 3, 4, 5, 7, 9,
10, 11, 13, 14, 15 è 1). ×åòâåðòûé èíâàðèàíò îïèñûâàåò àâàðèéíóþ ñèòóàöèþ
è ïîêàçûâàåò, ÷òî ïîâòîðíîé ðåãèñòðàöèè è ïîëó÷åíèÿ ñåðòèôèêàòà íå òðåáó-
åòñÿ, à íåîáõîäèìî òîëüêî ñíîâà âîññòàíîâèòü ïàðàìåòðû è ïîâòîðíî çàãðó-
çèòü ëîêàëüíûå äàííûå (ñðàáàòûâàþò ïåðåõîäû 11, 12, 14, 16, 17, 18). Åñëè
âîññòàíàâëèâàþòñÿ äàííûå ñ íîñèòåëåé, òî èíâàðèàíòû èìåþò âèä
y
y
y
y
1
2
3
4
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 0 1 0 0 1 1 0 1 1
�
�
�
�
( ),
( 0 0 0 0
1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0
),
( ),
( ).
Âîññòàíîâëåíèþ ïîäëåæàò ïàðàìåòðû âû÷èñëèòåëÿ è ïîâòîðíàÿ çàãðóçêà äàí-
íûõ ñ íîñèòåëåé. Òàêèì îáðàçîì, ïåðâîå ñâîéñòâî — ñâîéñòâî æèâîñòè —
â ýòîé ìîäåëè âûïîëíÿåòñÿ. Îòñþäà ñëåäóåò, ÷òî â äàííîé ìîäåëè âûïîëíÿåò-
ñÿ ñâîéñòâî ñïðàâåäëèâîñòè, êîòîðîå ñîñòîèò â òîì, ÷òî åñëè çàäàíèå íàõî-
äèòñÿ â ãðèä-ñèñòåìå, òî îíî ðàíî èëè ïîçäíî áóäåò âûïîëíÿòüñÿ. Ýòî ñëåäóåò
î÷åâèäíûì îáðàçîì èç òîãî, ÷òî ñîîòâåòñòâóþùèå ïåðåõîäû, âåäóùèå ê ñâîáîä-
íûì âû÷èñëèòåëÿì, áóäóò âûïîëíÿòüñÿ òî÷íî òàêèì æå îáðàçîì, êàê è â ïðèâå-
äåííîì ïðèìåðå.
Ïîëó÷åííûå ðåøåíèÿ óðàâíåíèÿ ñîñòîÿíèÿ ïîçâîëÿþò ñôîðìóëèðîâàòü òà-
êîå óòâåðæäåíèå.
Òåîðåìà 1. ÑÏ, ìîäåëèðóþùàÿ ãðèä-ñèñòåìó, ÿâëÿåòñÿ æèâîé, è â íåé âû-
ïîëíÿåòñÿ ñâîéñòâî ñïðàâåäëèâîñòè.
ÑÂÎÉÑÒÂÎ ÎÃÐÀÍÈ×ÅÍÍÎÑÒÈ È ÑÏÐÀÂÅÄËÈÂÎÑÒÈ
Ðàññìîòðèì âûïîëíèìîñòü ñâîéñòâà îãðàíè÷åííîñòè ÑÏ, êîòîðîå ïîäòâåðæ-
äàåò âûïîëíèìîñòü ñâîéñòâà ñïðàâåäëèâîñòè. Ñâîéñòâî îãðàíè÷åííîñòè îçíà-
÷àåò, ÷òî â ÑÏ íå ñóùåñòâóåò ìåñò, â êîòîðûõ ôèøêè ìîãóò íàêàïëèâàòüñÿ
â íåîãðàíè÷åííîì êîëè÷åñòâå. Òàêàÿ ñèòóàöèÿ ñîîòâåòñòâóåò ñëó÷àþ, êîãäà â
ãðèä-ñèñòåìå ïîñòîÿííî ÷òî-òî ïðîèñõîäèò, íî ïðè ýòîì íè÷åãî íå âû÷èñëÿ-
åòñÿ (ñèñòåìà öèêëèò).
Äëÿ èññëåäîâàíèÿ ýòîãî ñâîéñòâà ñåòè Ïåòðè íåîáõîäèìî ðåøèòü ñèñòåìó
ëèíåéíûõ îäíîðîäíûõ äèîôàíòîâûõ óðàâíåíèé â ìíîæåñòâå íàòóðàëüíûõ ÷è-
ñåë âèäà A yT
� 0, ãäå A T — ìàòðèöà, òðàíñïîíèðîâàííàÿ ê ìàòðèöå èíöèäåíò-
íîñòè À. Ðåøåíèÿ òàêîé ñèñòåìû íàçûâàþòñÿ èíâàðèàíòàìè ìåñò, è åñëè âñå
ìåñòà â ÑÏ ïîêðûâàþòñÿ ïîëîæèòåëüíûìè çíà÷åíèÿìè, òî ÑÏ îãðàíè÷åíà.
 äàííîì ïðèìåðå òðàíñïîíèðîâàííàÿ ìàòðèöà èìååò ñëåäóþùèé âèä:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 131
Ðåøåíèÿ ñèñòåìû A yT
� 0 èìåþò âèä:
Èç ïîëó÷åííûõ ðåøåíèé î÷åâèäíûì îáðàçîì èìååì îãðàíè÷åííîñòü ÑÏ, ïî-
ñêîëüêó âñå åå ìåñòà ïîêðûâàþòñÿ ïîëîæèòåëüíûìè çíà÷åíèÿìè. Îòñþäà âû-
òåêàåò ñëåäóþùåå óòâåðæäåíèå.
Òåîðåìà 2. ÑÏ, ìîäåëèðóþùàÿ ãðèä-ñèñòåìó, îãðàíè÷åíà è â íåé âûïîëíÿ-
åòñÿ ñâîéñòâî ñïðàâåäëèâîñòè.
ÇÀÊËÞ×ÅÍÈÅ
Íîâûå èíôîðìàöèîííî-òåõíîëîãè÷åñêèå èíôðàñòðóêòóðû, òàêèå êàê ãðèä-ñèñòå-
ìû, îáëà÷íûå âû÷èñëåíèÿ, ïîçâîëèëè ñ íîâûõ ïîçèöèé ðàññìîòðåòü ðàçëè÷íûå
àñïåêòû êîëëåêòèâíîé ðàáîòû íàó÷íûõ ñîîáùåñòâ, ÷òî ïðèâåëî ê çíà÷èòåëüíîìó
óñëîæíåíèþ ñóïåðêîìïüþòåðíûõ âû÷èñëåíèé. Äëÿ îðãàíèçàöèè êîððåêòíîé êîë-
ëåêòèâíîé ðàáîòû íåîáõîäèìî ñîçäàâàòü ñðåäñòâà ôîðìàëèçîâàííîãî ïðîåêòèðî-
âàíèÿ íîâûõ ïðèëîæåíèé äëÿ íàçâàííûõ ñðåä.
 ñòàòüå èñïîëüçîâàí ìàòåìàòè÷åñêèé àïïàðàò òðàíçèöèîííûõ ñèñòåì äëÿ
ôîðìèðîâàíèÿ ñîâîêóïíîñòè ïðîòîêîëîâ âçàèìîäåéñòâèÿ ñ ãðèä-ñèñòåìàìè: ðåãè-
ñòðàöèè â ãðèä-ñèñòåìå; ïîäãîòîâêè çàäàíèÿ; ðåãèñòðàöèè è ïîäãîòîâêè çàäàíèÿ.
Êðîìå òîãî, ðàçðàáîòàíà àäåêâàòíàÿ ìîäåëü ñóïåðêîìïüþòåðíîé âû÷èñëèòåëüíîé
ñðåäû â âèäå ÑÏ, ÷òî ïîçâîëèëî ñòðîãî äîêàçàòü ñâîéñòâà îãðàíè÷åííîñòè, æèâó-
÷åñòè è ñïðàâåäëèâîñòè ïðîåêòèðóåìîé ñðåäû.
132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1
p
p
p
p
p
p
p
p
p
p
p
p
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10
�
�
�
�
�
�
�
�
�
�
�
�
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0( 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0
),
( ),
( 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
),
( 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0 0 0 0 0 0 0 0
),
( ),
( 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0
1 0 1 0 1
),
( ),
( 1 1 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
),
( 0 0
3 0 3 0 3 3 3 3 3 0 0 0 3 1 0 0 3 3 3 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
),
( ),
( 0 0 0 1 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 0 0 1 0 0 3 3
),
( ).
Íîìåð ïåðåõîäà
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
1 1 1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0
3 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 1 0 0 0 0 1 0 1 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 1 0 0 0 0 0 0 0 1 1 3 0 0 0 0 0
0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0
1 0 0 0 3 0 0 1 0 0 0 0 0 3 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 0 0 0 0 0
15 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 3 0 0 0 0
16 0 0 0 0
0 0 0 0 0 1 1 0 0 3 0 0 0 0 1 0 0 0 0 0 0 0 1
17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1
18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 0 0 1 0
19 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
Íîìåð ìåñòà ÑÏ
Í
î
ì
åð
ï
åð
åõ
î
ä
à
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Áîéêî Þ.Â., Âîëîõîâ Â.Ì., Ãëèáîâåöü Ì.Ì., ªðøîâ Ñ.Â., Êðèâèé Ñ.Ë., Ïîãîð³ëèé Ñ.Ä., Ðîë³ê Î.².,
Òåëåíèê Ñ.Ô., ßñî÷êà Ì.Â. Ìåòîäè òà íîâ³òí³ ï³äõîäè äî ïðîåêòóâàííÿ, óïðàâë³ííÿ ³ çàñòîñóâàííÿ
âèñîêîïðîäóêòèâíèõ ²Ò-³íôðàñòðóêòóð. Çà ðåä. À.Â. Àí³ñ³ìîâà. Êè¿â: Êè¿â. íàö. óí-ò ³ì. Òàðàñà
Øåâ÷åíêà, 2016. 448 ñ.
2. Áîéêî Þ.Â., Çèíîâ’ºâ Ì.Ã., Ñâ³ñòóíîâ Ñ.ß., Ñóäàêîâ Î.Î. Óêðà¿íñüêèé àêàäåì³÷íèé ãð³ä: äîñâ³ä ñòâî-
ðåííÿ ³ ïåðø³ ðåçóëüòàòè åêñïëóàòàö³¿. Ìàòåìàòè÷åñêèå ìàøèíû è ñèñòåìû. 2008. Ò. 1, ¹ 1.
Ñ. 67–84.
3. Ñëþñàð Å.À. Àâòîìàòèçèðîâàííàÿ ñëóæáà ðåïëèêàöèè ôàéëîâ äëÿ îðãàíèçàöèè âûñîêîé äîñòóïíîñòè
äàííûõ â ãðèä-èíôðàñòðóêòóðå. ÓÑèÌ. 2012. ¹ 4 (240). Ñ. 63–74.
4. Êðèâèé Ñ.Ë. ˳í³éí³ ä³îôàíòîâ³ îáìåæåííÿ òà ¿õ çàñòîñóâàííÿ. ×åðí³âö³: Áóêðåê, 2015. 224 ñ.
5. Ïîãîð³ëèé Ñ.Ä., Áîéêî Þ.Â., Ëåâ÷åíêî Ð.²., Ìàð’ÿíîâñüêèé Â.À. Ìåòîäè êëàñòåðíèõ îá÷èñëåíü.
Çà ðåä. Ñ. Ä. Ïîãîð³ëîãî. Êè¿â, 2013. 416 ñ.
6. Ñóäàêîâ Î.Î., Áîéêî Þ.Â. GRID ðåñóðñè ³íôîðìàö³éíî-îá÷èñëþâàëüíîãî öåíòðó Êè¿âñüêîãî íàö³î-
íàëüíîãî óí³âåðñèòåòó ³ìåí³ Òàðàñà Øåâ÷åíêà. Ïðîáëåìè ïðîãðàìóâàííÿ. Ìàòåð³àëè V ì³æíàðîäíî¿
íàóêîâî-ïðàêòè÷íî¿ êîíôåðåíö³¿ ç ïðîãðàìóâàííÿ ÓêðÏÐÎÃ’2006 (Êè¿â, 23–25 òðàâíÿ 2006 ð.). Êè¿â,
2006. ¹ 2–3. Ñ. 165–169.
Íàä³éøëà äî ðåäàêö³¿ 04.04.2016
Ñ.Ë. Êðèâèé, Þ.Â. Áîéêî, Ñ.Ä. Ïîãîð³ëèé, Î.Ô. Áîðåöüêèé, Ì.Ì. Ãëèáîâåöü
ÏÐÎÅÊÒÓÂÀÍÈß ÃвÄ-ÑÒÐÓÊÒÓÐ ÍÀ ÎÑÍβ ÒÐÀÍÇÈÖ²ÉÍÈÕ ÑÈÑÒÅÌ
Ç ÎÁÃÐÓÍÒÓÂÀÍÍßÌ ÏÐÀÂÈËÜÍÎÑÒ² ¯Õ ÔÓÍÊÖ²ÎÍÓÂÀÍÍß
Àíîòàö³ÿ. Ðîçãëÿíóòî ìåòîä ïðîåêòóâàííÿ ãð³ä-ñèñòåìè íà îñíîâ³ òðàí-
çèö³éíèõ ñèñòåì òà ¿õí³õ ñèíõðîííèõ äîáóòê³â. Îòðèìàíà ãëîáàëüíà òðàí-
çèö³éíà ñèñòåìà òðàíñëþºòüñÿ â ìåðåæó Ïåòð³ (ÌÏ). Çà äîïîìîãîþ ÌÏ ïå-
ðåâ³ðÿþòü êîðåêòí³ñòü ïðîåêòíèõ ð³øåíü, çîêðåìà â³äñóòí³ñòü òóïèê³â, ìåðò-
âèõ ïåðåõîä³â òîùî.
Êëþ÷îâ³ ñëîâà: ãð³ä-ñòðóêòóðà, òðàíçèö³éí³ ñèñòåìè, ä³îôàíòîâ³ ð³âíÿííÿ.
S.L. Kryvyi, Y.V. Boyko, S.D. Pogorilyy, O.F. Boretskyi, M.M. Glybovets
DESIGN OF GRID STRUCTURES BASED ON TRANSITION SYSTEMS
WITH JUSTIFICATION OF THE CORRECTNESS OF THEIR FUNCTIONING
Abstract. The authors consider the method of designing grid systems based on
transition systems and their products. The resulting global transition system is
translated into a Petri net, which is used to verify the correctness of the design
decisions.
Keywords: grid-structure, transition systems, Diophantine equations.
Êðûâûé Ñåðãåé Ëóêüÿíîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî,
e-mail: sl.krivoi@gmail.com.
Áîéêî Þðèé Âëàäèìèðîâè÷,
êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî,
e-mail: boyko@univ.net.ua.
Ïîãîðåëûé Ñåðãåé Äåìüÿíîâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð, çàâåäóþùèé êàôåäðîé Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà
èìåíè Òàðàñà Øåâ÷åíêî, email: sdp@univ.net.ua.
Áîðåöêèé Àëåêñàíäð Ôðàíöåâè÷,
àññèñòåíò êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî,
e-mail: o.boretskyi@knu.ua.
Ãëûáîâåö Íèêîëàé Íèêîëàåâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, äåêàí Íàöèîíàëüíîãî óíèâåðñèòåòà «Êèåâî-Ìîãèëÿíñêàÿ
àêàäåìèÿ», e-mail: glib@ukma.kiev.ua.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 1 133
|