Алгоритм паралельного виконання та синхронізації Е-мережі
В статті розглядаються принципи паралельного виконання Е-мережевих імітаційних моделей на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок в межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі NULL- повідомлен...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2005
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/58468 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм паралельного виконання та синхронізації Е-мережі / В.В. Литвинов, В.В. Казимир, І.Б. Гавсієвич // Мат. машини і системи. — 2005. — № 4. — С. 72-83. — Бібліогр.: 9 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-58468 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-584682014-04-05T10:18:19Z Алгоритм паралельного виконання та синхронізації Е-мережі Литвинов, В.В. Казимир, В.В. Гавсієвич, І.Б. Моделювання і управління великими системами В статті розглядаються принципи паралельного виконання Е-мережевих імітаційних моделей на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок в межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі NULL- повідомлень. Для досягнення поставленої мети формалізовано алгоритми роботи Е-мережевого переходу та планувальника при традиційному послідовному моделюванні, виділено паралельні процеси переходів і планувальника, а також розроблено їхній формальний опис за допомогою процесної алгебри CSP Т. Хоара. В статье рассматриваются принципы параллельного выполнения Е-сетевых имитационных моделей на основе процессо-ориентированной парадигмы и построения алгоритма синхронизации параллельных участков в рамках консервативного подхода с применением метода предотвращения взаимных блокировок на базе NULL-сообщений. Для достижения поставленной цели формализовано алгоритм работы Е-сетевого перехода и планировщика при традиционном последовательном моделировании, выделены параллельные процессы переходов и планировщика, а также разработано их формальное описание с помощью процессной алгебры CSP Т. Хоара. The paper is devoted to theoretical and practical problems of performing E-nets imitation models with using conservative approach. The E-nets transition’s algorithm and sequential scheduler’s algorithm were formalized. The parallel processes of transitions and scheduler were marked out and described on Hoare’s CSP language. 2005 Article Алгоритм паралельного виконання та синхронізації Е-мережі / В.В. Литвинов, В.В. Казимир, І.Б. Гавсієвич // Мат. машини і системи. — 2005. — № 4. — С. 72-83. — Бібліогр.: 9 назв. — укр. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/58468 681.3.06, 519.8 uk Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Моделювання і управління великими системами Моделювання і управління великими системами |
| spellingShingle |
Моделювання і управління великими системами Моделювання і управління великими системами Литвинов, В.В. Казимир, В.В. Гавсієвич, І.Б. Алгоритм паралельного виконання та синхронізації Е-мережі Математичні машини і системи |
| description |
В статті розглядаються принципи паралельного виконання Е-мережевих імітаційних моделей
на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок в
межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі NULL-
повідомлень. Для досягнення поставленої мети формалізовано алгоритми роботи Е-мережевого переходу
та планувальника при традиційному послідовному моделюванні, виділено паралельні процеси переходів і
планувальника, а також розроблено їхній формальний опис за допомогою процесної алгебри CSP Т. Хоара. |
| format |
Article |
| author |
Литвинов, В.В. Казимир, В.В. Гавсієвич, І.Б. |
| author_facet |
Литвинов, В.В. Казимир, В.В. Гавсієвич, І.Б. |
| author_sort |
Литвинов, В.В. |
| title |
Алгоритм паралельного виконання та синхронізації Е-мережі |
| title_short |
Алгоритм паралельного виконання та синхронізації Е-мережі |
| title_full |
Алгоритм паралельного виконання та синхронізації Е-мережі |
| title_fullStr |
Алгоритм паралельного виконання та синхронізації Е-мережі |
| title_full_unstemmed |
Алгоритм паралельного виконання та синхронізації Е-мережі |
| title_sort |
алгоритм паралельного виконання та синхронізації е-мережі |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2005 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/58468 |
| citation_txt |
Алгоритм паралельного виконання та синхронізації Е-мережі / В.В. Литвинов, В.В. Казимир, І.Б. Гавсієвич // Мат. машини і системи. — 2005. — № 4. — С. 72-83. — Бібліогр.: 9 назв. — укр. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT litvinovvv algoritmparalelʹnogovikonannâtasinhronízacííemereží AT kazimirvv algoritmparalelʹnogovikonannâtasinhronízacííemereží AT gavsíêvičíb algoritmparalelʹnogovikonannâtasinhronízacííemereží |
| first_indexed |
2025-07-05T09:41:58Z |
| last_indexed |
2025-07-05T09:41:58Z |
| _version_ |
1836799512333516800 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 72
УДК 681.3.06, 519.8
В.В. ЛИТВИНОВ, В.В. КАЗИМИР, І.Б. ГАВСІЄВИЧ
АЛГОРИТМ ПАРАЛЕЛЬНОГО ВИКОНАННЯ ТА СИНХРОНІЗАЦІЇ Е-МЕРЕЖІ
Abstract: The paper is devoted to theoretical and practical problems of performing E-nets imitation models with using
conservative approach. The E-nets transition’s algorithm and sequential scheduler’s algorithm were formalized. The
parallel processes of transitions and scheduler were marked out and described on Hoare’s CSP language.
Key words: distributed simulation, parallel program synchronization, E-nets, conservative approach, CSP.
Анотація: В статті розглядаються принципи паралельного виконання Е-мережевих імітаційних моделей
на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок в
межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі NULL-
повідомлень. Для досягнення поставленої мети формалізовано алгоритми роботи Е-мережевого переходу
та планувальника при традиційному послідовному моделюванні, виділено паралельні процеси переходів і
планувальника, а також розроблено їхній формальний опис за допомогою процесної алгебри CSP Т. Хоара.
Ключові слова: розподілене імітаційне моделювання, синхронізація паралельних програм, Е-мережі,
консервативна схема, CSP.
Аннотация: В статье рассматриваются принципы параллельного выполнения Е-сетевых имитационных
моделей на основе процессо-ориентированной парадигмы и построения алгоритма синхронизации
параллельных участков в рамках консервативного подхода с применением метода предотвращения
взаимных блокировок на базе NULL-сообщений. Для достижения поставленной цели формализовано
алгоритм работы Е-сетевого перехода и планировщика при традиционном последовательном
моделировании, выделены параллельные процессы переходов и планировщика, а также разработано их
формальное описание с помощью процессной алгебры CSP Т. Хоара.
Ключевые слова: распределенное имитационное моделирование, синхронизация параллельных программ,
Е-сети, консервативная схема, CSP.
1. Введення
Сучасні тенденції в області інформаційних технологій виносять на порядок денний питання
створення розподілених систем імітаційного моделювання (РСІМ), здатних реалізувати додаткові
переваги моделювання як методу дослідження складних систем [1, 2].
При створенні РСІМ необхідно враховувати:
– цільову апаратно-програмну платформу;
– математичну основу РСІМ;
– схему синхронізації паралельних ділянок;
– засоби реалізації РСІМ.
У роботі будемо орієнтуватися на розподілені апаратні платформи, що складаються із
звичайних персональних комп'ютерів, об'єднаних у локальні мережі, а також на MPI-кластери. Для
формалізованого опису структури й процесу функціонування в РСІМ будемо використовувати
математичний апарат Е-мереж [3, 4]. В роботі була обрана базова консервативна схема
синхронізації виконання паралельних процесів на базі NULL-повідомлень [5, 6]. Технологічною
базою побудови РСІМ послужить специфікація CORBA [7].
Метою даної статті є розробка принципів паралельного виконання Е-мережевих імітаційних
моделей на основі процесо-орієнтованої парадигми та створення алгоритму синхронізації
паралельних ділянок у межах консервативного підходу з застосуванням методу запобігання
взаємних блокувань на базі NULL-повідомлень.
2. Формальне визначення Е-мережі
Формально Е-мережу EN можливо визначити п’ятіркою:
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 73
0, µPostPre,T,P,EN = , (1)
де P – кінцева непуста множина позицій;
T – кінцева непуста множина переходів; множини переходів і позицій не
перетинаються, ∅=∩ PT ;
{ }1,0: →∪ PTPre – вхідна функція; ( ) 1, =ptPre – означає, що існує дуга, яка
веде з позиції Pp ∈ до переходу Tt ∈ ; ( ) 0, =ptPre – означає, що такої дуги не існує. Тоді
( ) ( ){ }1, =∈= ptPrePptIN – множина всіх вхідних позицій переходу Tt ∈ ;
{ }1,0: →∪ PTPost – вихідна функція; ( ) 1, =ptPost – означає, що існує дуга, яка
веде від переходу Tt ∈ у позицію Pp ∈ ; ( ) 0, =ptPost – означає, що такої дуги не існує. Тоді
( ) ( ){ }1, =∈= ptPostPptOUT – множина всіх вихідних позицій переходу Tt ∈ ;
{ }1,0: →Pµ – функція розмітки, що визначає маркування або стан
позиції; ( ) 0=pµ – означає, що позиція Pp ∈ вільна (не містить мітку); ( ) 1=pµ – означає,
що позиція зайнята (містить метку); 0µ – початкова розмітка мережі.
В даній роботі розглянемо базисний набір переходів, який визначається множиною типів
{ }Y"",X"",J"",F"",T""=D .
Будь-який перехід Tt ∈ можна описати:
для переходів типу T"" , F"" або J""
для переходу типа X""
=
,,,,
,,,,
,,,
ryzd
rxzd
zd
p
τ
τ
τ
для переходу Y"" ,
(2)
де Dd ∈ – тип переходу;
+ℜ∈τ – час затримки на переході;
z – процедура перетворення атрибутів;
rx , ry – результат обчислення керуючої процедури. Результат обчислення може бути
невизначеним – FAIL або належати множині вхідних (для переходу типу Y"" ) чи вихідних (для
переходу типу X"" ) позицій, ( ) { }FAIL∪∈ tOUTrx , ( ) { }FAIL∪∈ tINry .
Функція { }1,0: →TEnabled визначає, чи виконані умови спрацьовування переходу Tt ∈ ;
( ) 1=tEnabled – означає, що умови спрацьовування виконані й перехід готовий до
спрацьовування; ( ) 0=tEnabled – означає, що умови спрацьовування не виконані.
Визначення функції ( )tEnabled залежно від типу переходу наведено в табл. 1.
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 74
Таблиця 1. Визначення функції ( )tEnabled залежно від типу переходу
якщо ( )[ ] ( )[ ]01 =∧= outin µµ ( )
=
,0
,1
tEnabled
інакше,
де ( )tINin ∈ , ( )tOUTout ∈
якщо ( )[ ]∧=1inµ
( ) ( )[ ]0: =∈∀∧ outtOUTout µ ( )
=
,0
,1
tEnabled
інакше,
де ( )tINin ∈
якщо ( ) ( )[ ]∧=∈∀ 1: intINin µ
( )[ ]0=∧ outµ ( )
=
,0
,1
tEnabled
інакше,
“J”
out
IN(t)
де ( )tOUTout ∈
якщо ( )[ ]∧=1inµ
[ ] ( )[ ]0FAIL =∧≠∧ rxrx µ ( )
=
,0
,1
tEnabled
інакше,
де ( )tINin ∈ , ( )tOUTrx ∈
якщо [ ] ( )[ ]∧=∧≠ 1FAIL ryry µ
( )[ ]0=∧ outµ ( )
=
,0
,1
tEnabled
інакше, ry
out
IN (t)
“Y”
де ( )tINry ∈ , ( )tOUTout ∈
При спрацьовуванні Е-мережевого переходу відбувається переміщення міток із вхідних позицій у
вихідні за правилами, визначеними для різних типів переходів.
Зміна розмітки ( )pµ у нову розмітку ( )pµ′ , ( ) ( )[ ]tOUTtINp ∪∈∀ при спрацьовуванні
переходу Tt ∈ залежно від його типу, наведені в табл. 2.
Таблиця 2. Зміна розмітки мережі при спрацьовуванні переходу
( ) 0=′ inµ ,
( ) 1=′ outµ
( ) 0=′ inµ ,
( ) ( ) 1: =′∈∀ outtOUTout µ
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 75
Продовження табл.2
( ) 0=′ inµ ,
( ) 1=′ rxµ ,
( ) { }[ ] ( ) ( )outoutrxtOUTout µµ =′∈∀ :\
( ) 0=′ inµ ,
( ) 1=′ rxµ ,
( ) { }[ ] ( ) ( )outoutrxtOUTout µµ =′∈∀ :\
( ) 0=′ ryµ ,
( ) { }[ ] ( ) ( )ininrytINin µµ =′∈∀ :\ ,
( ) 1=′ outµ
Алгоритм роботи Е-мережевого переходу можна описати блок-схемою, що наведена на рис. 1.
3. Планування в традиційній послідовній системі імітаційного моделювання
Алгоритм роботи планувальника, що керує системою імітаційного моделювання, яка дозволяє
досліджувати моделі, описані за допомогою апарату Е-мереж, приведений на рис. 2 – 4.
На блок-схемах були використовуються такі позначення:
– time – поточний модельний час;
– EL – список подій; timet, – подія закінчення затримки переходу Tt ∈ ,
запланована на момент часу time (таким чином, у даному алгоритмі список подій містить
затримані переходи);
– Vkπ – проекція вектора V на k -у вісь; якщо W – множина векторів однакової
довжини, то Wkπ – множина проекцій усіх векторів з W на k -у вісь – { }WwwW kk ∈= ππ ;
– SCHEDULER1 – підпрограма, яка з множини пасивних (що не перебувають у стані
затримки) переходів виділяє ті, в яких виконані умови спрацьовування; обчислює час затримки на
переході; формує події та додає їх у список подій;
– SCHEDULER2 – підпрограма, яка з множини затриманих переходів виділяє ті, в яких
відбулися події закінчення затримки, оновлює список подій і дозволяє спрацьовування переходу.
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 76
Рис. 1. Алгоритм роботи переходу Tt ∈
Рис. 2. Алгоритм роботи планувальника
t T : [ <t, time > EL ]
Enabled(t) = 1
ні
Визначення часу затримки
EL = EL <t, time+ >
так
Початок затримки переходу t
ПОЧАТОК (time, EL)
EL =
КІНЕЦЬ ( EL )
Рис. 3. Алгоритм підпрограми SCHEDULER1
t T :
[ (<t, time > EL) ^ (time time) ]
EL" = EL" <t, time>
ПОЧАТОК (time, EL)
EL" =
КІНЕЦЬ ( EL" )
Закінчення затримки переходу t
Процедура перетворення z
Спрацьовування переходу
Рис. 4. Алгоритм підпрограми SCHEDULER2
4. Організація паралельного виконання імітаційних моделей
Представимо традиційну систему імітаційного моделювання, побудовану на базі Е-мереж, як
множину процесів ( )tTRANSITION та процес ( )ELtime,SCHEDULER і опишемо її формально
в межах теорії CSP [8], де
– ( )tTRANSITION – процес, реалізуючий роботу Е-мережевого переходу Tt ∈ ;
– ( )ELtime,SCHEDULER – процес, реалізуючий роботу планувальника.
Процес ( )tTRANSITION має такий алфавіт:
( ) { ail.t,conditionFt,condition.tTRANSITION =α (3)
,activate.tdelay.t,k.t,conditionO
}fire.ttion.t,transforma.t,deactivate .
Формальне визначення процесу ( )tTRANSITION приведено нижче:
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 77
( ) →= tcondition.tTRANSITION (4)
( )( tTRANSITIONail.tconditionF →
→→ τ!delay.tk.tconditionO
→→ .tdeactivatetimeactivate.t ?
( ) )tTRANSITIONfire.ttion.ttransforma →→ .
Стани процесу ( )tTRANSITION показані на рис. 5.
Множину паралельно працюючих переходів STRANSITION можна визначити:
( )tTRANSITIONSTRANSITION Tt∈= || . (5)
Процес ( )ELtime,SCHEDULER має такий алфавіт:
( ) { ail,conditionFcondition,ELtime,SCHEDULER =α (6)
}deactivatenextEvent,activate,delay,k,conditionO .
Формальне визначення процесу ( )ELtime,SCHEDULER приведено нижче:
( ) ( )ELtime,SCHEDULER1ELtime,SCHEDULER = □ (7)
( )ELtime,SCHEDULER2 ;
( ) [ →= ∉ tcondition.ELtime,SCHEDULER1 ELt| (8)
( )( ELtime,SCHEDULERail.tconditionF →
→→ τ?delay.tk.tconditionO
{ }( ) ) ]tELtime,SCHEDULERtimeactivate.t ∪→! ;
( ) [ →= ∈ tnextEvent.ELtime,SCHEDULER2 ELt| (9)
{ }( ) ]tELtime,SCHEDULER.tdeactivate \→ .
Стани процесу ( )ELtime,SCHEDULER показані на рис. 6.
Рис. 5. Стани процесу ( )tTRANSITION
conditionFail.t
condition.t conditionOk.t
activate.t ! time
SCHEDULER
(time, EL)
SCHEDULER1
(time, EL)
SCHEDULER2
(time, EL)
nextEvent
Рис.6. Стани процесу ( )ELtime,SCHEDULER
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 78
Запуск процесу планувальника можна визначити як
( )∅= ,SCHEDULERSCHEDULE 0 . (10)
Тоді всю систему в цілому можна визначити:
STRANSITIONSCHEDULESYSTEM = . (11)
Процес планувальника ( )ELtime,SCHEDULER і процес окремого переходу ( )tTRANSITION
працюють паралельно і синхронізують свою роботу шляхом одночасної участі в подіях з множини
подій, яка отримана в результаті перетину їхніх алфавітів:
( ) ( ) =∩ tTRANSITIONELtime,SCHEDULER αα (12)
{ k.t,conditionOail.t,conditionFt,condition.
}.tdeactivate,activate.tdelay.t, .
Використання традиційного планувальника, заснованого на глобальному списку подій при описаній
вище організації паралельного виконання, не є ефективним через велику кількість повідомлень між
планувальником і окремим переходом.
У даній роботі пропонується не використовувати глобальне керування модельним часом, а
реалізувати планування в кожному переході локально і розробити спеціальні механізми
синхронізації модельного часу між переходами.
5. Модифікації Е-мереж
На основі консервативної схеми синхронізації та методу запобігання взаємних блокувань на базі
NULL-повідомлень розробимо модифікації Е-мереж для синхронізації виконання паралельних
ділянок.
1. Введемо функцію Lvt – локальний модельний час переходу Tt ∈ :
+ℜ→TLvt : . (13)
2. Введемо функцію Ts – часова відмітка останньої події позиції Pp ∈ : одержання мітки,
видалення мітки, одержання NULL-повідомлення (див. далі):
+ℜ→PTs : . (14)
3. Введемо функцію
+ℜ→TLowBound : – нижня часова границя з усіх вхідних
повідомлень (повідомлень, отриманих від вхідних позицій) переходу Tt ∈ :
( ) ( )[ ] ( )tINininTstLowBound ∈∀= ,min . (15)
4. Розіб’ємо множину вхідних позицій ( )tIN переходу Tt ∈ на дві непересічні підмножини –
вхідних вільних ( )tINF і вхідних ( )tINB зайнятих позицій:
( ) ( ) ( ){ }1=∈= ptINptINB µ ,
( ) ( ) ( ){ }0=∈= ptINptINF µ , (16)
( ) ( ) ( ) ( ) ( )tINtINtINtINtIN FBFB =∪∅=∩ , .
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 79
5. Розіб’ємо множину вихідних позицій ( )tOUT переходу Tt ∈ на дві непересічні
підмножини – вихідних вільних ( )tOUTF і вихідних ( )tOUTB зайнятих позицій:
( ) ( ) ( ){ }1=∈= ptOUTptOUTB µ ,
( ) ( ) ( ){ }0=∈= ptOUTptOUTF µ , (17)
( ) ( ) ( ) ( ) ( )tOUTtOUTtOUTtOUTtOUT FBFB =∪∅=∩ , .
6. Введемо функцію { }1,0: →TveConservati – умова гарантії відсутності наведених
помилок (causality errors – помилки, що можуть виникати у разі паралельного імітаційного
моделювання) у майбутньому для переходу Tt ∈ ; ( ) 1=tveConservati – означає, що умова
виконується; ( ) 0=tveConservati – означає, що умова не виконується. Визначення функції
( )tveConservati залежно від типу переходу наведено в табл. 3.
Таблиця 3. Визначення функції ( )tveConservati залежно від типу переходу
( ) 1=tveConservati
( ) 1=tveConservati
( ) 1=tveConservati
якщо ( )[ :tOUTout B∈∀
( ) ( ) ]tMINoutTs OF> ( )
=
,0
,1
tveConservati
інакше,
де ( ) ( )[ ] )(,min tOUToutoutTstMIN FOF ∈∀=
якщо ( )[ :tINin F∈∀
( ) ( ) ]tMINinTs IB> ( )
=
,0
,1
tveConservati
інакше,
де ( ) ( )[ ] )(,min tINininTstMIN BIB ∈∀=
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 80
7. Введемо функцію
+ℜ→TActivateTS : – момент часу початку затримки переходу
Tt ∈ . Визначення функції ( )tActivateTS залежно від типу переходу приведено в табл. 4.
Таблиця 4. Визначення функції ( )tActivateTS залежно від типу переходу
( ) ( ) ( )[ ]outTsinTstActivateTS ,max= ,
де ( )tINin ∈ , ( )tOUTout ∈
( ) ( )( ,max inTstActivateTS =
( )( ) ( )[ ] )tOUToutoutTs ∈∀,max ,
де ( )tINin ∈
( ) ( )( ) ( )[ ]( ,,maxmax tINininTstActivateTS ∈∀=
( ) )outTs ,
де ( )tOUTout ∈
( ) ( ) ( )[ ]rxTsinTstActivateTS ,max= ,
де ( )tINin ∈ , ( )tOUTrx ∈
( ) ( ) ( )[ ]outTsryTstActivateTS ,max= ,
де ( )tINry ∈ , ( )tOUTout ∈
8. Внесемо зміну в спрацьовування переходу таким чином, щоб при зміні маркування позиції
Pp ∈ обновлялася її часова відмітка ( )pTs . Зміна розмітки ( )pµ у нову розмітку ( )pµ′ , а також
зміна часової відмітки ( )pTs на нову часову відмітку ( )psT ′ , ( ) ( )[ ]tOUTtINp ∪∈∀ при
спрацьовуванні переходу Tt ∈ залежно від його типу наведені в табл. 5.
9. Для запобігання взаємних блокувань (deadlock) введемо процедуру посилання нульових
(NULL) повідомлень, яку формально можна описати:
( ) ( ) ( ) ( ) ( )[ ]tLvtinsTinintINin B =′=′∈∀ ,: µµ ; (18)
( ) ( ) ( ) ( ) ( )[ ]tLvtoutsToutouttOUTout F =′=′∈∀ ,: µµ .
10. Модифікований алгоритм роботи Е-мережевого переходу Tt ∈ можна описати блок-
схемою, що приведена на рис. 7.
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 81
Таблиця 5. Зміни розмітки мережі та часових відміток позицій при спрацьовуванні переходу
залежно від його типу
( ) ( ) ( )tLvtinsTin =′=′ ,0µ ;
( ) ( ) ( )tLvtoutsTout =′=′ ,1µ
( ) ( ) ( )tLvtinsTin =′=′ ,0µ ;
( ) ( ) ( ) ( )[ ]tLvtoutsTouttOUTout =′=′∈∀ ,1: µ
“J”
out
IN(t)
( ) ( ) ( ) ( )[ ]tLvtinsTintINin =′=′∈∀ ,0: µ ;
( ) ( ) ( )tLvtoutsTout =′=′ ,1µ
( ) ( ) ( )tLvtinsTin =′=′ ,0µ ;
( ) ( ) ( )tLvtrxsTrx =′=′ ,1µ ;
( ) { }[ ]:\ rxtOUTout ∈∀
( ) ( ) ( ) ( )[ ]tTsoutsToutout =′=′ ,µµ
( ) ( ) ( )tLvtrysTry =′=′ ,0µ ;
( ) { }[ ]:\ rytINin ∈∀
( ) ( ) ( ) ( )[ ]inTsinsTinin =′=′ ,µµ ;
( ) ( ) ( )tLvtoutsTout =′=′ ,1µ
Тепер уся система складається з множини процесів ( )tNMTRANSITIO , реалізуючих роботу
модифікованого Е-мережевого переходу Tt ∈ . Цей процес має алфавіт:
( ) { ve.t,conservati,lowBound.ttNMTRANSITIO =α (19)
t,condition.veOk.tconservativeFail.t,conservati ,
,activate.tdelay.t,k.t,conditionOail.t,conditionF
}ges.t ,nullMessafire.ttion.t,transforma.t,deactivate .
Формальне визначення процесу ( )tNMTRANSITIO наведено нижче:
( ) →→= ve.tconservatilowBound.ttNMTRANSITIO (20)
( )( tN2MTRANSITIOveFail.tconservati →
→→ tcondition.veOk.tconservati
( )( tN2MTRANSITIOail.tconditionF →
→→ τ!delay.tk.tconditionO
→→ .tdeactivatetimeactivate.t ?
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 82
( ) )tN2MTRANSITIOfire.ttion.ttransforma →→ ;
( ) ( )tNMTRANSITIOes.tnullMessagtN2MTRANSITIO →= . (21)
Стани процесу ( )tNMTRANSITIO наведені на рис. 8.
Множину паралельно працюючих переходів NSMTRANSITIO можна визначити:
( )tNMTRANSITIONSMTRANSITIO Tt∈= || . (22)
Розроблені у роботі формальні описи на CSP також можуть бути використані для аналізу і
верифікації за допомогою спеціалізованих програм, таких як Process Behavior Exploration (ProBE) та
Failures-Divergence Refinement (FDR), розроблених Formal Systems (Europe) Ltd [9].
Рис. 7. Модифікований алгоритм роботи
Е-мережевого переходу Tt ∈
Рис. 8. Стани процесу MTRANSITION( t )
6. Висновок
В роботі розроблені принципи паралельного виконання Е-мережевих імітаційних моделей на основі
процесо-орієнтованої парадигми та створення алгоритму синхронізації паралельних ділянок в
межах консервативного підходу з застосуванням методу запобігання взаємних блокувань на базі
NULL-повідомлень.
Для досягнення поставленої мети формалізовано алгоритми роботи Е-мережевого
переходу та планувальника при традиційному послідовному моделюванні, виділено паралельні
процеси переходів і планувальника, а також розроблено їхній формальний опис за допомогою
процесної алгебри CSP Т. Хоара.
ISSN 1028-9763. Математичні машини і системи, 2005, № 4 83
Алгоритм паралельного виконання Е-мережевих моделей може бути реалізований в інших
розподілених системах імітаційного моделювання. Формальні описи паралельних процесів
переходів і планувальника мовою CSP можуть бути застосовані в подальших розробках і
верифікації паралельних програм.
СПИСОК ЛІТЕРАТУРИ
1. Литвинов В.В., Марьянович Т.П. Методы построения имитационных систем. – Киев: Наукова думка, 1991. –
115 с.
2. Гусев В.В., Марьянович Т.П., Пепеляев В.А. Основные принципы разработки системы технологической
поддержки распределенного моделирования // Проблемы программирования. – 2000. – № 1–2. Спец.выпуск. –
С. 620–625.
3. Казимир В.В., Демшевська Н.В., Азарова А.О. Мова специфікацій імітаційного моделювання та методика її
застосування // Вісник Вінницького політехнічного інституту. – 2000. – № 1. – С. 67–71.
4. Казимир В.В. Моделирование синтетического окружения для реактивных систем // Математичне
моделювання. – 2003. – № 2(10). – С. 24–32.
5. Bryant R.E. Simulation of Packet Communication Architecture Computer Systems. Computer Science Laboratory. –
Cambridge, Massachusetts: Massachusetts Institute of Technology, 1977. – 120 p.
6. Chandy K.M., Misra J. Distributed Simulation: A Case Study in Design and Verification of Distributed Programs //
IEEE Transactions on Software Engineering. – 1978. – N 5. – P. 440–452.
7. Object Management Group, The Common Object Request Broker: Architecture and Specification. – Object
Management Group, 2000. – 948 p.
8. Hoare C. Communicating sequential processes // Comm. ACM. – 1978. – N 21. – P. 666–677.
9. Roscoe A.W. The Theory and Practice of Concurrency. – Prentice Hall, 1997. – 450 p.
|