Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса
Розв’язуються задачі знаходження мінімального загального часу виконання розподілених конкуруючих процесів з обмеженою кількістю копій структурованого програмного ресурсу в умовах необмеженого і обмеженого паралелізму...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84020 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса / Н.С. Коваленко, П.А. Павлов, М.И. Овсеец // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 105-117. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84020 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-840202015-07-03T03:02:39Z Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса Коваленко, Н.С. Павлов., П.А Овсеец, М.И. Кибернетика Розв’язуються задачі знаходження мінімального загального часу виконання розподілених конкуруючих процесів з обмеженою кількістю копій структурованого програмного ресурсу в умовах необмеженого і обмеженого паралелізму The execution time of distributed competing processes is found for a limited number of copies of the structured program resource under conditions of unlimited and limited parallelism. 2012 Article Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса / Н.С. Коваленко, П.А. Павлов, М.И. Овсеец // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 105-117. — Бібліогр.: 8 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84020 681.3.06 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Коваленко, Н.С. Павлов., П.А Овсеец, М.И. Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса Кибернетика и системный анализ |
| description |
Розв’язуються задачі знаходження мінімального загального часу виконання розподілених конкуруючих процесів з обмеженою кількістю копій структурованого програмного ресурсу в умовах необмеженого і обмеженого паралелізму |
| format |
Article |
| author |
Коваленко, Н.С. Павлов., П.А Овсеец, М.И. |
| author_facet |
Коваленко, Н.С. Павлов., П.А Овсеец, М.И. |
| author_sort |
Коваленко, Н.С. |
| title |
Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса |
| title_short |
Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса |
| title_full |
Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса |
| title_fullStr |
Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса |
| title_full_unstemmed |
Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса |
| title_sort |
асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84020 |
| citation_txt |
Асинхронные распределенные вычисления при ограниченном числе копий структурированного программного ресурса / Н.С. Коваленко, П.А. Павлов, М.И. Овсеец // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 105-117. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kovalenkons asinhronnyeraspredelennyevyčisleniâpriograničennomčislekopijstrukturirovannogoprogrammnogoresursa AT pavlovpa asinhronnyeraspredelennyevyčisleniâpriograničennomčislekopijstrukturirovannogoprogrammnogoresursa AT ovseecmi asinhronnyeraspredelennyevyčisleniâpriograničennomčislekopijstrukturirovannogoprogrammnogoresursa |
| first_indexed |
2025-07-06T10:56:15Z |
| last_indexed |
2025-07-06T10:56:15Z |
| _version_ |
1836894883868049408 |
| fulltext |
ÓÄÊ 681.3.06
Í.Ñ. ÊÎÂÀËÅÍÊÎ, Ï.À. ÏÀÂËÎÂ, Ì.È. ÎÂÑÅÅÖ
ÀÑÈÍÕÐÎÍÍÛÅ ÐÀÑÏÐÅÄÅËÅÍÍÛÅ ÂÛ×ÈÑËÅÍÈß ÏÐÈ
ÎÃÐÀÍÈ×ÅÍÍÎÌ ×ÈÑËÅ ÊÎÏÈÉ ÑÒÐÓÊÒÓÐÈÐÎÂÀÍÍÎÃÎ
ÏÐÎÃÐÀÌÌÍÎÃÎ ÐÅÑÓÐÑÀ
Êëþ÷åâûå ñëîâà: ðàñïðåäåëåííûé êîíêóðèðóþùèé ïðîöåññ, ïðîãðàììíûé ðåñóðñ,
àñèíõðîííûé ðåæèì, ñèíõðîííûé ðåæèì, îãðàíè÷åííûé ïàðàëëåëèçì, íåîãðàíè-
÷åííûé ïàðàëëåëèçì, îäíîðîäíàÿ ñèñòåìà, îäèíàêîâî ðàñïðåäåëåííàÿ ñèñòåìà.
ÂÂÅÄÅÍÈÅ
Âî ìíîãèõ ïðèëîæåíèÿõ, ñâÿçàííûõ ñ ïðîåêòèðîâàíèåì ìíîãîïðîöåññîðíûõ
ñèñòåì (ÌÑ), âû÷èñëèòåëüíûõ êîìïëåêñîâ (ÂÊ), ñèñòåìíîãî è ïðèêëàäíîãî
ïðîãðàììíîãî îáåñïå÷åíèÿ [1], îïòèìàëüíîé îðãàíèçàöèè ïàðàëëåëüíûõ âû-
÷èñëèòåëüíûõ ïðîöåññîâ, çíà÷èòåëüíûé èíòåðåñ ïðåäñòàâëÿþò çàäà÷è, êîãäà
ìíîæåñòâî êîíêóðèðóþùèõ ïðîöåññîâ ìîãóò èñïîëüçîâàòü íå îäíó, à íåñêîëü-
êî êîïèé ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà (ÏÐ). Ñëó÷àé, êîãäà â îá-
ùåé ïàìÿòè ìíîãîïðîöåññîðíîé ñèñòåìû èìååòñÿ îäíà êîïèÿ ÏÐ, ñ ðàçëè÷íûõ
ïîçèöèé èçó÷åí â ðàáîòàõ [2–8]. Ïðè ýòîì áûëè ðåøåíû çàäà÷è íàõîæäåíèÿ
ìèíèìàëüíîãî îáùåãî âðåìåíè âûïîëíåíèÿ ðàñïðåäåëåííûõ êîíêóðèðóþùèõ
ïðîöåññîâ, èñïîëüçóþùèõ ñòðóêòóðèðîâàííûé íà áëîêè ïðîãðàììíûé ðåñóðñ
â ðàçëè÷íûõ ðåæèìàõ âçàèìîäåéñòâèÿ ïðîöåññîâ, ïðîöåññîðîâ è áëîêîâ [2–6],
ïîëó÷åíû êðèòåðèè ýôôåêòèâíîñòè è îïòèìàëüíîñòè ñòðóêòóðèðîâàíèÿ ïðî-
ãðàììíûõ ðåñóðñîâ [7], ïðîâåäåí ñðàâíèòåëüíûé àíàëèç ðåæèìîâ âçàèìîäåé-
ñòâèÿ ïðîöåññîâ, ïðîöåññîðîâ è áëîêîâ [8], ðåøåí ðÿä îïòèìèçàöèîííûõ çàäà÷
ïî ðàñ÷åòó ÷èñëà ïðîöåññîâ, ìèíèìàëüíîãî ÷èñëà ïðîöåññîðîâ è äð. Èçó÷åíèå
ýòèõ è äðóãèõ çàäà÷, îòíîñÿùèõñÿ ê îïòèìàëüíîé îðãàíèçàöèè ïàðàëëåëüíûõ
âû÷èñëåíèé, ïðèîáðåòàåò îñîáóþ àêòóàëüíîñòü â ñëó÷àå, êîãäà â îáùåé ïàìÿ-
òè ÌÑ ìîãóò áûòü îäíîâðåìåííî ðàçìåùåíû c � 2 êîïèé ïðîãðàììíîãî ðåñóð-
ñà. Òàêîå îáîáùåíèå íîñèò ïðèíöèïèàëüíûé õàðàêòåð, ïîñêîëüêó îòðàæàåò
îñíîâíûå ÷åðòû ìóëüòèêîíâåéåðíîé îáðàáîòêè, à òàêæå ïîçâîëÿåò ñðàâíèòü
ýôôåêòèâíîñòü êîíâåéåðíîé è ïàðàëëåëüíîé îáðàáîòêè.
 íàñòîÿùåé ñòàòüå ñòðîèòñÿ è èññëåäóåòñÿ ìàòåìàòè÷åñêàÿ ìîäåëü îðãàíèçà-
öèè êîíêóðèðóþùèõ ïðîöåññîâ, èñïîëüçóþùèõ îãðàíè÷åííîå ÷èñëî êîïèé ïðî-
ãðàììíîãî ðåñóðñà. Ïðè ýòîì, èñïîëüçóÿ èäåè ìåòîäà ñòðóêòóðèðîâàíèÿ ïðîãðàì-
ìíûõ ðåñóðñîâ íà áëîêè ñ èõ ïîñëåäóþùåé êîíâåéåðèçàöèåé ïî ïðîöåññàì è ïðî-
öåññîðàì, èññëåäóþòñÿ îïòèìàëüíûå âðåìåííûå õàðàêòåðèñòèêè òàêîé îðãàíèçàöèè.
1. ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÌÎÄÅËÜ ÐÀÑÏÐÅÄÅËÅÍÍÛÕ ÂÛ×ÈÑËÅÍÈÉ
ÏÐÈ ÎÃÐÀÍÈ×ÅÍÍÎÌ ×ÈÑËÅ ÊÎÏÈÉ ÏÐÎÃÐÀÌÌÍÎÃÎ ÐÅÑÓÐÑÀ
Êîíñòðóêòèâíûìè ýëåìåíòàìè äëÿ ïîñòðîåíèÿ ìàòåìàòè÷åñêèõ ìîäåëåé ñèñòåì
ðàñïðåäåëåííûõ âû÷èñëåíèé ÿâëÿþòñÿ ïîíÿòèÿ ïðîöåññà è ïðîãðàììíîãî ðåñóðñà.
Ïðîöåññ áóäåì ðàññìàòðèâàòü êàê ïîñëåäîâàòåëüíîñòü áëîêîâ (êîìàíä, ïðî-
öåäóð) Q Q Qs1 2, , ..., , äëÿ âûïîëíåíèÿ êîòîðûõ èñïîëüçóåòñÿ ìíîæåñòâî ïðîöåñ-
ñîðîâ (ïðîöåññîðíûõ óçëîâ, îáðàáàòûâàþùèõ óñòðîéñòâ, èíòåëëåêòóàëüíûõ êëè-
åíòîâ). Ïðè ýòîì ïðîöåññ íàçûâàåòñÿ ðàñïðåäåëåííûì, åñëè âñå áëîêè èëè ÷àñòü
èç íèõ îáðàáàòûâàþòñÿ ðàçíûìè ïðîöåññîðàìè [2]. Äëÿ óñêîðåíèÿ âûïîëíåíèÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 105
© Í.Ñ. Êîâàëåíêî, Ï.À. Ïàâëîâ, Ì.È. Îâñååö, 2012
ïðîöåññîâ âû÷èñëåíèÿ ìîãóò îáðàáàòûâàòüñÿ ïàðàëëåëüíî, âçàèìîäåéñòâóÿ ïó-
òåì îáìåíà èíôîðìàöèåé. Òàêèå ïðîöåññû íàçûâàþòñÿ êîîïåðàòèâíûìè èëè âçà-
èìîäåéñòâóþùèìè ïðîöåññàìè.
Ïîíÿòèå ðåñóðñà ïðèìåíÿåòñÿ äëÿ îáîçíà÷åíèÿ ëþáûõ îáúåêòîâ âû÷èñëè-
òåëüíîé ñèñòåìû, êîòîðûå ìîãóò áûòü èñïîëüçîâàíû ïðîöåññàìè äëÿ ñâîåãî âû-
ïîëíåíèÿ. Ðååíòåðàáåëüíûå (ìíîãîêðàòíî èñïîëüçóåìûå) ðåñóðñû õàðàêòåðèçó-
þòñÿ âîçìîæíîñòüþ îäíîâðåìåííîãî èñïîëüçîâàíèÿ íåñêîëüêèìè âû÷èñëèòåëü-
íûìè ïðîöåññàìè. Äëÿ ïàðàëëåëüíûõ ñèñòåì õàðàêòåðíîé ÿâëÿåòñÿ ñèòóàöèÿ,
êîãäà îäíó è òó æå ïîñëåäîâàòåëüíîñòü áëîêîâ èëè åå ÷àñòü íåîáõîäèìî ïðîöåññî-
ðàì âûïîëíÿòü ìíîãîêðàòíî. Òàêóþ ïîñëåäîâàòåëüíîñòü áóäåì íàçûâàòü ïðîãðàì-
ìíûì ðåñóðñîì, à ìíîæåñòâî ñîîòâåòñòâóþùèõ ïðîöåññîâ — êîíêóðèðóþùèìè.
Ìàòåìàòè÷åñêàÿ ìîäåëü ðàñïðåäåëåííîé îáðàáîòêè êîíêóðèðóþùèõ âçàè-
ìîäåéñòâóþùèõ ïðîöåññîâ ïðè îãðàíè÷åííîì ÷èñëå êîïèé ïðîãðàììíîãî ðåñóð-
ñà âêëþ÷àåò p, p � 2 , ïðîöåññîðîâ ìíîãîïðîöåññîðíîé ñèñòåìû, êîòîðûå èìåþò
äîñòóï ê îáùåé ïàìÿòè; n, n � 2 , ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ;
s, s � 2 , áëîêîâ ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà; ìàòðèöó T tij� [ ] ,
i n�1, , j s�1, , âðåìåí âûïîëíåíèÿ áëîêîâ ïðîãðàììíîãî ðåñóðñà ðàñïðåäåëåííû-
ìè âçàèìîäåéñòâóþùèìè êîíêóðèðóþùèìè ïðîöåññàìè; 2 � �c p, ÷èñëî êîïèé
ñòðóêòóðèðîâàííîãî íà áëîêè ïðîãðàììíîãî ðåñóðñà, êîòîðûå ìîãóò îäíîâðå-
ìåííî íàõîäèòüñÿ â îïåðàòèâíîé ïàìÿòè, äîñòóïíîé äëÿ âñåõ p ïðîöåññîðîâ,
ïðè÷åì
p
c
�
�
�
�
� 2 ; � � 0 — ïàðàìåòð, õàðàêòåðèçóþùèé âðåìÿ äîïîëíèòåëüíûõ
ñèñòåìíûõ ðàñõîäîâ, ñâÿçàííûõ ñ îðãàíèçàöèåé êîíâåéåðíîãî ðåæèìà èñïîëüçî-
âàíèÿ áëîêîâ ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà ìíîæåñòâîì âçàèìî-
äåéñòâóþùèõ êîíêóðèðóþùèõ ïðîöåññîâ ïðè ðàñïðåäåëåííîé îáðàáîòêå.
Áóäåì òàêæå ïðåäïîëàãàòü, ÷òî ÷èñëî ïðîöåññîâ n êðàòíî ÷èñëó êîïèé ñ
ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà, ò.å. n mc� , m � 2 , ïðè ýòîì âçàèìî-
äåéñòâèå ïðîöåññîâ, ïðîöåññîðîâ è áëîêîâ ïðîãðàììíîãî ðåñóðñà ïîä÷èíåíî
ñëåäóþùèì óñëîâèÿì:
1) íè îäèí èç ïðîöåññîðîâ íå ìîæåò îáðàáàòûâàòü îäíîâðåìåííî áîëåå îä-
íîãî áëîêà;
2) ïðîöåññû âûïîëíÿþòñÿ â ïàðàëëåëüíî–êîíâåéåðíîì ðåæèìå ãðóïïàìè, ò.å.
îñóùåñòâëÿåòñÿ îäíîâðåìåííîå (ïàðàëëåëüíîå) âûïîëíåíèå ñ êîïèé êàæäîãî áëî-
êà â ñî÷åòàíèè ñ êîíâåéåðèçàöèåé ãðóïï èç ñ áëîêîâ ïî ïðîöåññîðàì è ïðîöåññàì;
3) îáðàáîòêà êàæäîãî áëîêà ïðîãðàììíîãî ðåñóðñà îñóùåñòâëÿåòñÿ áåç
ïðåðûâàíèé;
4) ðàñïðåäåëåíèå áëîêîâ ïðîãðàììíîãî ðåñóðñà ïî ïðîöåññîðàì äëÿ êàæäîãî
ïðîöåññà i lc q� � , i n�1, , l � 0, q c�1, , îñóùåñòâëÿåòñÿ öèêëè÷åñêè ïî ïðàâèëó:
áëîê ñ íîìåðîì j k
p
c
r�
�
�
�
�
� , j s�1, , k � 0, r
p
c
�
�
�
�
�
1, , ðàñïðåäåëÿåòñÿ íà ïðîöåñ-
ñîð ñ íîìåðîì q c r�
( )1 .
Ââåäåì ñëåäóþùèå ðåæèìû âçàèìîäåéñòâèÿ ïðîöåññîâ, ïðîöåññîðîâ è áëî-
êîâ ñ ó÷åòîì íàëè÷èÿ ñ êîïèé ïðîãðàììíîãî ðåñóðñà:
1) àñèíõðîííûé ðåæèì, ïðè êîòîðîì íà÷àëî âûïîëíåíèÿ î÷åðåäíîé ãðóïïû
èç ñ êîïèé áëîêà Q j , j s�1, , îïðåäåëÿåòñÿ íàëè÷èåì ñ ïðîöåññîðîâ è ãîòîâíîñòüþ
ýòîé ãðóïïû áëîêîâ ê âûïîëíåíèþ (ïðîãðàììíûé áëîê ñ÷èòàåòñÿ ãîòîâûì ê âû-
ïîëíåíèþ, åñëè îí íå âûïîëíÿåòñÿ íè íà îäíîì èç ïðîöåññîðîâ);
2) ïåðâûé ñèíõðîííûé ðåæèì, îáåñïå÷èâàþùèé ëèíåéíûé ïîðÿäîê âûïîë-
íåíèÿ áëîêîâ ïðîãðàììíîãî ðåñóðñà âíóòðè êàæäîãî ïðîöåññà áåç çàäåðæåê, ò.å.
106 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
äëÿ êàæäîãî ïðîöåññà i lc q� � ,
i n�1, , l � 0, q c�1, , ìîìåíò çàâåð-
øåíèÿ âûïîëíåíèÿ j-ãî áëîêà íà
( ( ))q c r�
1 -ì ïðîöåññîðå ñîâïà-
äàåò ñ ìîìåíòîì íà÷àëà âûïîëíå-
íèÿ ñëåäóþùåãî ( )j �1 -ãî áëîêà íà
( )q cr� -ì ïðîöåññîðå, j s�
1 1, ,
r
p
c
�
�
�
�
�
1, ;
3) âòîðîé ñèíõðîííûé ðåæèì,
ïðè êîòîðîì ñ êîïèé êàæäîãî áëî-
êà íåïðåðûâíî ïåðåõîäèò ïî ãðóï-
ïàì èç ñ ïðîöåññîâ, ò.å. ìîìåíò
îêîí÷àíèÿ îáðàáîòêè ñ êîïèé òå-
êóùåãî áëîêà ñîâïàäàåò ñ ìîìåí-
òîì íà÷àëà èõ îáðàáîòêè íà ñëåäó-
þùåé ãðóïïå èç ñ ïðîöåññîðîâ.
Íà ðèñ. 1–3 ïðåäñòàâëåíû äè-
àãðàììû Ãàíòà, èëëþñòðèðóþùèå
âûïîëíåíèå n � 4 ðàñïðåäåëåííûõ
êîíêóðèðóþùèõ ïðîöåññîâ, èñ-
ïîëüçóþùèõ c � 2 êîïèè ñòðóêòó-
ðèðîâàííîãî ïðîãðàììíîãî ðå-
ñóðñà â ÌÑ ñ p � 7 ïðîöåññîðàìè
â ðàññìîòðåííûõ âûøå ðåæèìàõ è
ñ çàäàííîé ìàòðèöåé âðåìåí âû-
ïîëíåíèÿ áëîêîâ ÏÐ ñ ó÷åòîì äî-
ïîëíèòåëüíûõ ñèñòåìíûõ ðàñõî-
äîâ T � �
�
�
�
�
�
�
3 1 4
2 2 1
1 3 3
4 1 2
.
Îïðåäåëåíèå 1. Ñèñòåìà n
ðàñïðåäåëåííûõ êîíêóðèðóþùèõ
ïðîöåññîâ íàçûâàåòñÿ íåîäíîðîä-
íîé, åñëè âðåìåíà âûïîëíåíèÿ áëî-
êîâ ïðîãðàììíîãî ðåñóðñà
Q Q Qs1 2, , ..., çàâèñÿò îò îáúåìîâ
îáðàáàòûâàåìûõ äàííûõ è/èëè èõ ñòðóêòóðû, ò.å. ðàçíûå äëÿ ðàçíûõ ïðîöåññîâ.
Îïðåäåëåíèå 2. Ñèñòåìó ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ áóäåì
íàçûâàòü îäíîðîäíîé, åñëè âðåìåíà âûïîëíåíèÿ Qj-ãî áëîêà êàæäûì i-ì ïðîöåñ-
ñîì ðàâíû ìåæäó ñîáîé, ò.å. t tij j� , i n�1, , j s�1, .
Îïðåäåëåíèå 3. Ñèñòåìó êîíêóðèðóþùèõ ïðîöåññîâ áóäåì íàçûâàòü îäèíà-
êîâî ðàñïðåäåëåííîé, åñëè âðåìåíà tij âûïîëíåíèÿ áëîêîâ Q j , j s�1, , ïðîãðàì-
ìíîãî ðåñóðñà êàæäûì i-ì ïðîöåññîì ñîâïàäàþò è ðàâíû ti äëÿ âñåõ i n�1, , ò.å.
ñïðàâåäëèâà öåïî÷êà ðàâåíñòâ t t t ti i is i1 2� � � �� äëÿ âñåõ i n�1, .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 107
p
11t
12t
13t
41t
42t
43t
21t
31t
22t
23t
33t
32t
1
3
7
6
5
4
11
2
0 1 2 3 4 5 6 7 8 9 10
Ðèñ. 1. Äèàãðàììà àñèíõðîííîãî ðåæèìà
T p n s cí
àñ ( , , , )
p
11t
12t
13t
41t
42t
43t
21t
31t
22t
23t
33t
32t
0 1 2 3 4 5 6 7 8 9 10 11
1
2
3
4
5
6
7
Ðèñ. 2. Äèàãðàììà ïåðâîãî ñèíõðîííîãî ðåæèìà
T p n s cí
1 ( , , , )
p
11t
12t
13t
41t
42t
43t
21t
31t
22t
23t
33t
32t
0 1 2 3 4 5 6 7 8 9 10 11
1
2
3
4
5
6
7
Ðèñ. 3. Äèàãðàììà âòîðîãî ñèíõðîííîãî ðåæèìà
T p n s cí
2 ( , , , )
2. ÌÈÍÈÌÀËÜÍÎÅ ÎÁÙÅÅ ÂÐÅÌß ÂÛÏÎËÍÅÍÈß ÍÅÎÄÍÎÐÎÄÍÛÕ
ÐÀÑÏÐÅÄÅËÅÍÍÛÕ ÏÐÎÖÅÑÑÎÂ Â ÀÑÈÍÕÐÎÍÍÎÌ ÐÅÆÈÌÅ
ÏÐÈ ÄÎÑÒÀÒÎ×ÍÎÌ ×ÈÑËÅ ÏÐÎÖÅÑÑÎÐÎÂ
Îáîçíà÷èì T p n s ñí
àñ ( , , , ) ìèíèìàëüíîå îáùåå âðåìÿ âûïîëíåíèÿ n íåîäíîðîä-
íûõ ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ ïðè îãðàíè÷åííîì ÷èñëå c êî-
ïèé ïðîãðàììíîãî ðåñóðñà â ìíîãîïðîöåññîðíîé ñèñòåìå ñ p ïðîöåññîðàìè
â àñèíõðîííîì ðåæèìå ñ ó÷åòîì ïàðàìåòðà � . Äëÿ âû÷èñëåíèÿ T p n s cí
àñ ( , , , )
ðàññìîòðèì ñëó÷àè íåîãðàíè÷åííîãî ( )s
p
c
�
�
�
�
�
è îãðàíè÷åííîãî ( )s
p
c
�
�
�
�
�
ïàðàë-
ëåëèçìà.
Ïóñòü èìååòñÿ ñèñòåìà n mc� , m � 2 , 2 � �c p, íåîäíîðîäíûõ ðàñïðåäåëåí-
íûõ êîíêóðèðóþùèõ ïðîöåññîâ, ïðè÷åì ÷èñëî áëîêîâ s ñòðóêòóðèðîâàííîãî
ïðîãðàììíîãî ðåñóðñà íå ïðåâîñõîäèò ÷èñëà ãðóïï ïðîöåññîðîâ ïî c ïðîöåññî-
ðîâ â êàæäîé, ò.å. 2 � �
�
�
�
�
s
p
c
.  ýòîì ñëó÷àå áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî
ñ÷èòàòü, ÷òî êàæäûé Q j -é , j s�1, , áëîê i-ãî ïðîöåññà, ãäå i lc q� � , i n�1, , l � 0,
q c�1, , çàêðåïëåí çà ( ( ))q c r�
1 -ì ïðîöåññîðîì, r
p
c
�
�
�
�
�
1, . Òîãäà äëÿ âûïîëíå-
íèÿ n ïðîöåññîâ äîñòàòî÷íî âçÿòü p
p
c
s�
�
�
�
�
ïðîöåññîðîâ, à îñòàëüíûå p
p
c
s
�
�
�
�
ïðîöåññîðîâ áóäóò íåçàäåéñòâîâàíû.
Ïóñòü T tij
� �� [ ] — n s� -ìàòðèöà âðåìåí âûïîëíåíèÿ áëîêîâ ïðîãðàììíîãî
ðåñóðñà êàæäûì i-ì ïðîöåññîì ñ ó÷åòîì ïàðàìåòðà � � 0, ãäå t tij ij
�
�� � , i n�1, ,
j s�1, . Äëÿ âû÷èñëåíèÿ ìèíèìàëüíîãî îáùåãî âðåìåíè T p n s cí
àñ ( , , , ) ìîæíî âîñ-
ïîëüçîâàòüñÿ ôóíêöèîíàëîì çàäà÷è Áåëëìàíà–Äæîíñîíà, êîòîðûé â äàííîì
ñëó÷àå áóäåò èìåòü âèä
T p n s cí
àñ ( , , , ) �
� �
� � � � � �
�
�
�max
( ) , ( ) ,1 1 1
1
1 2
1 2 1
1
u u u m q i c
i
u
q i c
s
t t
�
� � �
i u
u
q i c s
i u
m
t
s�
�
�
� �� �
�
�
�
�
�
1
2
1
1
�
( ) ,
, (1)
ãäå m
n
c
� , t t
q i c j q i c j�
�
� �
( ) , ( ) ,1 1
�
�, q c�1, , i m�1, , j s�1, , à u u us1 2 1, , ...,
—
öåëûå ÷èñëà.
Ïðèìåð 1. Ðàññìîòðèì èíòåðïðåòàöèþ ôîðìóëû (1) íà ÷èñëîâîì ïðèìåðå.
Ïóñòü p � 7, n � 6, s � 3, c � 2 , à âðåìåíà âûïîëíåíèÿ áëîêîâ ïðîöåññàìè çàäàíû
ìàòðèöåé T � �
�
�
�
�
�
�
�
�
3 1 4
2 2 1
1 3 3
4 1 2
3 2 1
1 4 1
. Òîãäà m � 3; ñëåäîâàòåëüíî, ôóíêöèîíàë (1) ïðèìåò âèä
T p n s cí
àñ ( , , , )� � � � �7 6 3 2
� �
� � � �
�
�
�
�max
( ) , ( ) ,1 3 1 2 1
1
1 2 2
1 2
1
1
2
u u q i
i
u
q i
i u
u
t t� �� ��
�
�
�
�
�
�
�
t
q i
i u
( ) ,1 2 3
3
2
� , q �1 2, .
108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Ïðè q �1 èìååì
max
( ) , ( ) ,1 3 1 2 1
1
1 2 2
1 2
1
1
2
� � � �
�
�
�
� ��
u u q i
i
u
q i
i u
u
t t� � �
�
�
�
�
�
�
�
�
� t
q i
i u
( ) ,1 2 3
3
2
�
� � �
� � �
�
�
� �max
, , ,1 3 2 1 1
1
2 1 2 2 1
1 2
1
1
2
u u i
i
u
i
i u
u
i
t t t� �
3
3
2
�
i u�
�
�
�
�
�
�
.
Åñëè u1 1� , òî u2 1 3� , ; åñëè u1 2� , òî u2 2 3� , ; åñëè u1 3� , òî u2 3� . Òîãäà
max
, , ,1 3 2 1 1
1
2 1 2 2 1 3
1 2
1
1
2
� � �
�
�
� �� �
u u i
i
u
i
i u
u
i
t t t� � �
i u�
�
�
�
�
�
�
�
2
3
�
� �
�
�
�
� � �
max
,
, , ,
t t t t
i
i
i
i
i
i
i2 1 1
1
1
2 1 2
1
1
2 1 3
1
3
2
� � �
1 1
1
1
2 1 2
1
2
2 1 3
2
3
2 1 1
1
1
, , ,
,
,� � �
�
i
i
i
i
i
i
i
t t
t
�
�
�
�
� � �� �
� � � �� � �
�
�
�
t t t t
i
i
i
i
i
i
i2 1 2
1
3
2 1 3
3
3
2 1 1
1
2
2 1, , , ,
,� � �
2
2
2
2 1 3
2
3
2 1 1
1
2
2 1 2
2
3
� �
� �
i
i
i
i
i
i
i
t
t t
�
�
�
�
� �
� �
�
� �
,
, ,
,
t t t t
i
i
i
i
i
i
i2 1 3
3
3
2 1 1
1
3
2 1 2
3
2
2 1 3
�
�
�
� � �� �
, , , ,
,� � � �
i�
�
�
�
�
�
�
�
�
�
�
�
�
3
3
�
� � � � � �
max
,
, , , , , , , ,
t t t t t t t t
1 1 1 2 1 3 3 3 5 3 1 1 1 2 3 2
� � � � � � � � � �
� � � � � �
� �
� � � � �
t t
t t t t t t
3 3 5 3
1 1 1 2 3 2 5 2 5 3 1 1
, ,
, , , , , ,
,
, t t t t
t t t t t
3 1 3 2 3 3 5 3
1 1 3 1 3 2 5 2 5
, , , ,
, , , ,
,� � � �
� � � �
� � �
� � � �
, , , , , ,
,
3 1 1 3 1 5 1 5 2 5 3
� � � � � �t t t t t� � � �
�
�
�
�
�
�
�
�
�
� � � � � � � �
� � � � � � � �
� � �
max
, ,
, ,
3 1 4 3 1 3 1 3 3 1
3 1 3 2 1 3 1 3 3 1
3 1 3 2 1 3 1 3 2 1� � � � �
�
�
�
�
�
�
,
max [ , , , , , ]12 11 10 11 10 10 12� .
Ïðè q � 2 èìååì
max
( ) , ( ) ,1 3 1 2 1
1
1 2 2
1 2
1
1
2
� � � �
�
�
�
� ��
u u q i
i
u
q i
i u
u
t t� � �
�
�
�
�
�
�
�
�
� t
q i
i u
( ) ,1 2 3
3
2
�
� � �
� � � � � �
� �max
, , ,1 3 2 1
1
2 2 2 3
1 2
1
1
2
2
u u i
i
u
i
i u
u
i
i u
t t t� � �
3
�
�
�
�
�
�
.
Åñëè u1 1� , òî u2 1 3� , ; åñëè u1 2� , òî u2 2 3� , ; åñëè u1 3� , òî u2 3� . Òîãäà
max
, , ,1 3 2 1
1
2 2 2 3
3
1 2
1
1
2
2
� � � � � �
� �� �
u u i
i
u
i
i u
u
i
i u
t t t� � ��
�
�
�
�
�
�
�
� �
� � � �
� � �
max
,
, , , ,
t t t t
i
i
i
i
i
i
i
i
2 1
1
1
2 2
1
1
2 3
1
3
2 1
1
1
� � � �� � �
� �
� �
� �
� �
� �
t t
t t
i
i
i
i
i
i
i
i
2 2
1
2
2 3
2
3
2 1
1
1
2 2
1
3
, ,
, ,
,� �
� � t t t t á
t
i
i
i
i
i
i
i
i
2 3
3
3
2 1
1
2
2 2
2
2
2 3
2
3
2
, , , ,
,� � � �
� � � �
� � � �� �
i
i
i
i
i
i
i
i
i
t t t t
, , , , ,
,
1
1
2
2 2
2
3
2 3
3
3
2 1
1
3
2
� � � �
� � � �
� � � �� � �
2
3
3
2 3
3
3
� �
i
i
i
t
� �
� ��
�
�
�
�
�
�
�
�
�
�
�
,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 109
�
� � � � � �
max
,
, , , , , , , ,
t t t t t t t t
2 1 2 2 2 3 4 3 6 3 2 1 2 2 4 2
� � � � � � � � � �
� � � � � �
� �
� � � � �
t t
t t t t t t
4 3 6 3
2 1 2 2 4 2 6 2 6 3 2 1
, ,
, , , , , ,
,
, t t t t
t t t t t
4 1 4 2 4 3 6 3
2 1 4 1 4 2 6 2 6
, , , ,
, , , ,
,� � � �
� � � �
� � �
� � � �
, , , , , ,
,
3 2 1 4 1 6 1 6 2 6 3
� � � � � �t t t t t� � � �
�
�
�
�
�
�
�
�
max
, ,
, ,
2 2 1 2 1 2 2 1 2 1
2 2 1 4 1 2 4 1 2 1
2 4 1 4
� � � � � � � �
� � � � � � � �
� � � � � � � �
�
�
�
�
�
�
1 2 4 1 4 1,
max [ , , , , , ]8 8 10 10 12 12 12� .
(Ïîä÷åðêíóòàÿ ñóììà îáîçíà÷àåò ìàêñèìàëüíîå âðåìÿ âûïîëíåíèÿ.)
Ñëåäîâàòåëüíî, ìèíèìàëüíîå îáùåå âðåìÿ âûïîëíåíèÿ n � 6 íåîäíîðîäíûõ
ðàñïðåäåëåííûõ âçàèìîäåéñòâóþùèõ êîíêóðèðóþùèõ ïðîöåññîâ, èñïîëüçóþ-
ùèõ c � 2 êîïèè ñòðóêòóðèðîâàííîãî íà s � 3 áëîêîâ ïðîãðàììíûé ðåñóðñ, â ìíî-
ãîïðîöåññîðíîé ñèñòåìå ñ p � 7 ïðîöåññîðàìè â àñèíõðîííîì ðåæèìå ñîñòàâèò
T p n s ñí
àñ ( , , , ) �12 . Ïðè ýòîì áóäåò èñïîëüçîâàíî øåñòü ïðîöåññîðîâ.
Ðàññìîòðèì àëãîðèòì, êîòîðûé ïîçâîëÿåò ðåøèòü çàäà÷ó îïðåäåëåíèÿ ìèíè-
ìàëüíîãî îáùåãî âðåìåíè T p n s ñí
àñ ( , , , ) âûïîëíåíèÿ íåîäíîðîäíûõ ðàñïðåäåëåí-
íûõ êîíêóðèðóþùèõ ïðîöåññîâ â àñèíõðîííîì ðåæèìå áîëåå ýôôåêòèâíî.
Ïî çàäàííûì s c, , m
n
c
� è
ìàòðèöå T t
q i c j
� ��
�
[ ]
( ) ,1
,
q c�1, , i m�1, , j s�1, , ñòðîèì
c-ñëîéíûé âåðøèííî–âçâå-
øåííûé ãðàô G c
1
. Êàæäûé
q-é, q c�1, , ñëîé ãðàôà G c
1
ñîñòîèò èç âåðøèí t
q i c j�
( ) ,1
� ,
i m�1, , j s�1, , êîòîðûå ðàñ-
ïîëîæåíû â óçëàõ ïðÿìîó-
ãîëüíîé m s� -ðåøåòêè, ïðè-
÷åì t
q1
� — âõîäíûå âåðøè-
íû, tq t s� ,
� — âûõîäíûå,
q c�1, , t m c�
( )1 (ðèñ. 4).
Äóãè â êàæäîì ñëîå q îòðà-
æàþò ëèíåéíûé ïîðÿäîê âû-
ïîëíåíèÿ áëîêîâ Q j , j s�1, ,
ïðîãðàììíîãî ðåñóðñà êàæ-
äûì ( ( ) )q i c�
1 -ì ïðîöåñ-
ñîì, q c�1, , i m�1, , à òàêæå
ëèíåéíûé ïîðÿäîê èñïîëüçîâàíèÿ êàæäîãî áëîêà âñåìè m ïðîöåññàìè. Òàêèì îá-
ðàçîì, èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 1. Ìèíèìàëüíîå îáùåå âðåìÿ âûïîëíåíèÿ n mc� , m � 2 , íåîäíî-
ðîäíûõ ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ, èñïîëüçóþùèõ 2 � �c p êî-
ïèè ñòðóêòóðèðîâàííîãî íà 2 � �
�
�
�
�
s
p
c
áëîêà ïðîãðàììíîãî ðåñóðñà ñ âðåìåíàìè
110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
��
11t �
12t �
st1
�
�
�
1,1 ct �
�
2,1 ct �
�
sct ,1�
�� �
�
�
1,1 tt �
�
2,1 tt �
�
stt ,1�
��
21t �
22t �
st2
�
�
�
1,2 ct �
�
2,2 ct �
�
sct ,2�
�� �
�
�
1,2 tt �
�
2,2 tt �
�
stt ,2�
��
1ct
�
2ct
�
cst
�
�
�
1,cct �
�
2,cct �
�
scct ,�
�� �
�
�
1,mct �
2,mct �
smct ,
�
�
Ðèñ. 4. Ãðàô Gc
1
âûïîëíåíèÿ áëîêîâ ïðè ó÷åòå äîïîëíèòåëüíûõ ñèñòåìíûõ ðàñõîäîâ [ ]tij
� , i n�1, ,
j s�1, , â ìíîãîïðîöåññîðíîé ñèñòåìå ñ p,
p
c
�
�
�
�
� 2 , ïðîöåññîðàìè â àñèíõðîííîì
ðåæèìå îïðåäåëÿåòñÿ äëèíîé êðèòè÷åñêîãî ïóòè â c-ñëîéíîì âåðøèííî–âçâåøåí-
íîì ãðàôå G c
1
èç íà÷àëüíîé âåð-
øèíû t
q1
� â êîíå÷íóþ t
q m c s�
( ) ,1
� ,
q c�1, , m
n
c
� .
Ïðèìåð 2. Èñïîëüçóÿ äàí-
íûå ïðèìåðà 1, íàéòè ìèíèìàëü-
íîå îáùåå âðåìÿ T p n s cí
àñ ( , , , ),
èñïîëüçóÿ àëãîðèòì íàõîæäåíèÿ
êðèòè÷åñêîãî ïóòè â c-ñëîéíîì
âåðøèííî–âçâåøåííîì ãðàôå G c
1
.
Ïî çàäàííûì n � 6, s � 3 è
ìàòðèöå T � ñòðîèì 2-ñëîéíûé
(c � 2) âåðøèííî–âçâåøåííûé
ãðàô G c
1
(ðèñ. 5). Êàæäûé ñëîé
ñîäåðæèò ms âåðøèí, ãäå m n c� �/ 3. Äëèíà êðèòè÷åñêîãî ïóòè â ãðàôå ðàâíà 12,
÷òî ñîâïàäàåò ñ ìèíèìàëüíûì îáùèì âðåìåíåì, ïîëó÷åííûì â ïðèìåðå 1.
3. ÀÑÈÍÕÐÎÍÍÛÉ ÐÅÆÈÌ ÂÛÏÎËÍÅÍÈß ÐÀÑÏÐÅÄÅËÅÍÍÛÕ ÊÎÍÊÓÐÈÐÓÞÙÈÕ
ÏÐÎÖÅÑÑΠ ÓÑËÎÂÈßÕ ÎÃÐÀÍÈ×ÅÍÍÎÃÎ ÏÀÐÀËËÅËÈÇÌÀ
Ðàññìîòðèì ñëó÷àé îãðàíè÷åííîãî ïàðàëëåëèçìà, ò.å. êîãäà ÷èñëî áëîêîâ
ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà áîëüøå ÷èñëà ãðóïï, èìåþùèõ ïî
ñ ïðîöåññîðîâ, ò.å. s
p
c
�
�
�
�
�
, s k
p
c
r�
�
�
�
�
� , k � 1 , 1 � �
�
�
�
�
r
p
c
.
Êàê è â ñëó÷àå, êîãäà â îáùåé ïàìÿòè ÌÑ èìååòñÿ îäíà êîïèÿ ïðîãðàììíîãî
ðåñóðñà, ìíîæåñòâî èç s áëîêîâ ðàçîáüåì íà ( )k �1 ãðóïïó ïî
p
c
�
�
�
�
áëîêà â êàæäîé,
çà èñêëþ÷åíèåì ( )k �1 -é ãðóïïû, êîòîðàÿ ñîäåðæèò r áëîêîâ [6]. Òîãäà ìàòðèöó
T tij
� �� [ ] , i n�1, , j k
p
c
r�
�
�
�
�
�
�
�
��
�
�
��1, , âðåìåí âûïîëíåíèÿ áëîêîâ ðàçáèâàåì íà
( )k �1 ïîäìàòðèöó T
l
� , l k� �1 1, , ðàçìåðà n
p
c
�
�
�
�
�
êàæäàÿ, çà èñêëþ÷åíèåì ïîñëåä-
íåé T
k�1
� , êîòîðàÿ áóäåò ñîäåðæàòü ïðè s, íå êðàòíîì
p
c
�
�
�
�
, òîëüêî r ñòîëáöîâ, à
îñòàëüíûå
p
c
r
�
�
�
�
ñòîëáöîâ áóäóò íóëåâûìè. Ïî êàæäîé ïîäìàòðèöå T
l
� ,
l k� �1 1, , ñòðîèì ( )k �1 -þ ëèíåéíóþ äèàãðàììó Ãàíòà, êàæäàÿ èç êîòîðûõ îòî-
áðàæàåò âî âðåìåíè âûïîëíåíèå î÷åðåäíûõ
p
c
�
�
�
�
áëîêîâ ñòðóêòóðèðîâàííîãî
ïðîãðàììíîãî ðåñóðñà íà ð
p
c
�
�
�
�
ïðîöåññîðàõ âñåìè n ïðîöåññàìè, èñïîëüçóþùè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 111
43 1
31 3
12 2
12 2
24 1
11 4
Ðèñ. 5. Ñ-ñëîéíûé âåðøèííî–âçâåøåííûé ãðàô Gc
1
ìè îãðàíè÷åííîå ÷èñëî ñ
êîïèé ñòðóêòóðèðîâàííî-
ãî ïðîãðàììíîãî ðåñóðñà.
Ïðè r � 0 ( )k �1 -ÿ äèàã-
ðàììà áóäåò îòðàæàòü
âûïîëíåíèå ïîñëåäíèõ r
áëîêîâ íà cr ïðîöåññî-
ðàõ. Íà ðèñ. 6 ïðåäñòàâ-
ëåíà äèàãðàììà Ãàíòà
äëÿ ÌÑ ñ ïàðàìåòðàìè
p � 7, n � 4, s � 3 , c � 2 ,
T � �
�
�
�
�
�
�
3 1 4 2 1 4 2 1
2 2 1 1 3 3 2 2
1 3 3 1 1 3 3 1
4 1 2 3 1 1 2 5
.
Cóììàðíîå âðåìÿ
âûïîëíåíèÿ âñåõ ïðîöåñ-
ñîâ, èñïîëüçóþùèõ ñ êî-
ïèé ÏÐ, â ýòîì ñëó÷àå
áóäåò îïðåäåëÿòüñÿ êàê
ñóììà äëèí êðèòè÷åñêèõ
ïóòåé â êàæäîé èç ïîñëå-
äîâàòåëüíî èäóùèõ íå-
ñîâìåùåííûõ äèàãðàì-
ìàõ Ãàíòà. Îäíàêî ýòî
âðåìÿ ìîæíî ñîêðàòèòü,
åñëè ïîñëåäîâàòåëüíî
ïîáëî÷íî ñîâìåùàòü äè-
àãðàììû Ãàíòà, íà÷èíàÿ
ñî âòîðîé äèàãðàììû, ïî
îñè âðåìåíè ñïðàâà íàëå-
âî íà ìàêñèìàëüíî âîç-
ìîæíóþ âåëè÷èíó, íå íàðóøàÿ òåõíîëîãè÷åñêèõ óñëîâèé àñèíõðîííîãî ðåæèìà.
 ðåçóëüòàòå ñîâìåùåíèÿ ïîëó÷èì ðåçóëüòèðóþùóþ ñîâìåùåííóþ äèàãðàììó Ãàí-
òà (ðèñ. 7).
 ðàáîòå [6] ïîêàçàíî, ÷òî ïîëó÷åííàÿ ñòðóêòóðà ðåçóëüòèðóþùåé ñîâìå-
ùåííîé äèàãðàììû Ãàíòà îïðåäåëÿåòñÿ ïðåäñòàâëåííûé íèæå ìàòðèöåé T * , êî-
òîðàÿ ñîñòîèò èç ïîäìàòðèö T T T
k1 2 1
� � �, , ...,
�
. Â ìàòðèöå T * ó÷òåíû êàê âñå ãîðè-
çîíòàëüíûå, òàê è âñå âåðòèêàëüíûå ñâÿçè ìåæäó áëîêàìè, à òàêæå ñâÿçè ìåæäó
áëîêàìè èç ðàçíûõ äèàãðàìì Ãàíòà. Îòìåòèì òàêæå, ÷òî ðåçóëüòèðóþùàÿ ìàòðè-
öà T * áóäåò èìåòü ðàçìåð ( ) ( )k n k
p
c
� � �
�
�
�
�
1 1 , ñ÷èòàòüñÿ áëî÷íîé, ñèììåòðè÷-
íîé, âåðõíåé äèàãîíàëüíîé îòíîñèòåëüíî âòîðîé äèàãîíàëè, òèïà Ãàíêåëåâîé ïî-
ðÿäêà k �1:
T * �
T T T T T
T T T T
T T T
k k
k
1 2 3 1
2 3 4 1
3 4 5
0
0 0
� � � � �
� � � �
� � �
�
�
�
� � � �
�
�
� �
�
�
T T
T
k k
k
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
0 0 0
0 0 0 0
, (2)
112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
p
11t
12t
14t
15t
16t
17t
18t
22t
21t
23t
24t
25t
26t
37t31t 34t
33t
32t
41t
43t
42t
35t
36t
27t
28t
38t
44t
45t
46t
47t
48t
220
1
2
3
4
5
6
Ðèñ. 7. Ñîâìåùåííàÿ äèàãðàììà Ãàíòà
T p n s cí
àñ( , , , )
p
11t
12t
13t
14t
15t
16t
17t
18t
22t
21t
23t
24t
25t
26t
37t31t 34t
33t
32t
41t
43t
42t
35t
36t
27t
28t
38t
44t
45t
46t
47t
48t
11 21
30
0
1
2
3
4
5
6
Ðèñ. 6. Íåñîâìåùåííàÿ äèàãðàììà Ãàíòà
T p n s cí
àñ( , , , )
ð
ãäå ïîäìàòðèöû T
l
� è T
k�1
� èìåþò âèä
T
t t t
l
l
p
c
l
p
c
l
p
c
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
1 1 1 1 1 2 1,( ) ,( ) ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �t t t
l
p
c
l
p
c
l
p
2 1 1 2 1 2 2,( ) ,( ) ,
�
c
n l
p
c
n l
p
c
t t
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
� � � �
,( ) ,( )1 1 1 2
� t
n l
p
c
,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
, l k�1, ,
T
t t t
k
k
p
c
k
p
c
k
p
c
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1 1 1 2 1
�
� �
, , ,
�
r
k
p
c
k
p
c
k
p
c
r
t t t
�
� �
0 0
2 1 2 2 2
�
�
, , ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
0 0
1 2
�
� � � � � � �
�t t t
n k
p
c
n k
p
c
n k
p
c
, , ,
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
r
� 0 0�
.
Ñ ïîìîùüþ ìàòðèöû T * ïîñòðîèì c-ñëîéíûé âåðøèííî–âçâåøåííûé ãðàô G c
2
,
àíàëîãè÷íûé ãðàôó G c
1
. Âåðøèíàì êàæäîãî ñëîÿ q ðàçìåðà ( ) ( )k m k
p
c
� � �
�
�
�
�
1 1 ãðà-
ôà G c
2
áóäóò ïðèïèñàíû âåñà t
q i c j�
( ) ,1
� , q c�1, , i k m� �1 1, ( ) , j s�1, . Âåðøèíû t
q1
�
áóäóò âõîäíûìè, à t
q k m c s� �
(( ) ) ,1 1
� — âûõîäíûìè, q c�1, . Èìååò ìåñòî ñëåäóþ-
ùàÿ òåîðåìà.
Òåîðåìà 2. Ìèíèìàëüíîå îáùåå âðåìÿ T p n s cí
àñ ( , , , ) âûïîëíåíèÿ n, n � 2 , íå-
îäíîðîäíûõ ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ, èñïîëüçóþùèõ ëèíåé-
íî ñòðóêòóðèðîâàííûé íà s, s � 2 , áëîêîâ ïðîãðàììíûé ðåñóðñ, ñ âðåìåíàìè âû-
ïîëíåíèÿ áëîêîâ ïðè ó÷åòå äîïîëíèòåëüíûõ ñèñòåìíûõ ðàñõîäîâ � � 0, çàäàâàå-
ìûõ ìàòðèöåé T tij
� �� [ ] , i n�1, , j s�1, , â ìíîãîïðîöåññîðíîé ñèñòåìå ñ p, p � 2 ,
ïðîöåññîðàìè è c � 2 êîïèÿìè ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà
( )
p
c
�
�
�
�
� 2 â àñèíõðîííîì ðåæèìå â ñëó÷àå íåîãðàíè÷åííîãî ïàðàëëåëèçìà
( )s
p
c
�
�
�
�
�
îïðåäåëÿåòñÿ äëèíîé êðèòè÷åñêîãî ïóòè èç íà÷àëüíîé âåðøèíû t
q1
�
â êîíå÷íóþ âåðøèíó t
q k m c s� �
(( ) ) ,1 1
� , q c�1, , ãðàôà G c
2
.
Ïðèìåð 3. Èñïîëüçóÿ çíà÷åíèÿ ïàðàìåòðîâ äèàãðàììû Ãàíòà, èçîáðàæåííîé
íà ðèñ. 6, íàéòè ìèíèìàëüíîå îáùåå âðåìÿ T p n s cí
àñ ( , , , ), ïðèìåíÿÿ àëãîðèòì íà-
õîæäåíèÿ êðèòè÷åñêîãî ïóòè â c-ñëîéíîì âåðøèííî–âçâåøåííîì ãðàôå G c
2
.
Òàê êàê
p
c
�
�
�
�
� 3, òî 8 2 3 2� �
�
�
�
�
� � � �s k
p
c
r ; ñëåäîâàòåëüíî, k � 2 , r � 2 .
Ìàòðèöó T � ðàçáèâàåì íà ïîäìàòðèöû T
l
� , l �1 3, , ðàçìåðà 4 3� êàæäàÿ. Ìàò-
ðèöà T * áóäåò ðàçìåðà ( )k n� �1 ( )k
p
c
�
�
�
�
�
�1 12 9� è èìåòü ñëåäóþùèé âèä:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 113
T * �
�
�
�
�
�
�
�
�
�
�
�
�
3 1 4
2 2 1
1 3 3
4 1 2
2 1 4
1 3 3
1 1 3
3 1 1
2 1 0
2 2 0
3 1 0
2 5 0
2 1 4
1 3 3
1 1 3
3 1 1
2 1 0
2 2 0
3 1 0
�
�
�
�
�
�
�
�
�
�
�
�
2 5 0
0 0 0
0 0 0
0 0 0
0 0 0
2 1 0
2 2 0
3 1 0
2 5 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
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
Ïîñòðîèì ïî ìàòðèöå T *
2-ñëîéíûé âåðøèííî–âçâåøåííûé
ãðàô G c
2
(ðèñ. 8). Äëèíà êðèòè÷å-
ñêîãî ïóòè ðàâíà 22.
4. ÂÐÅÌß ÂÛÏÎËÍÅÍÈß ÎÄÍÎÐÎÄÍÛÕ È ÎÄÈÍÀÊÎÂÎ ÐÀÑÏÐÅÄÅËÅÍÍÛÕ
ÊÎÍÊÓÐÈÐÓÞÙÈÕ ÏÐÎÖÅÑÑÎÂ
Ñîãëàñíî îïðåäåëåíèþ 2 ñèñòåìó ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ
áóäåì ñ÷èòàòü îäíîðîäíîé, åñëè âðåìåíà âûïîëíåíèÿ êàæäîãî áëîêà Q j ,
j s�1, , êàæäûì ïðîöåññîì ðàâíû, ò.å. t tij j
� �� , i n�1, , j s�1, .
Íà ðèñ. 9 ïðåäñòàâëåíà äèàãðàììà Ãàíòà, èëëþñòðèðóþùàÿ âûïîëíåíèå îäíî-
ðîäíûõ ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ ïðè îãðàíè÷åííîì ÷èñëå êîïèé
ïðîãðàììíîãî ðåñóðñà â ÌÑ
ñ ïàðàìåòðàìè p � 7, n � 4,
s � 3, c � 2 , T � �
�
�
�
�
�
�
3 1 4
3 1 4
3 1 4
3 1 4
.
Îöåíèì îáùåå âðåìÿ
âûïîëíåíèÿ n îäíîðîäíûõ
ðàñïðåäåëåííûõ êîíêóðèðó-
þùèõ ïðîöåññîâ â àñèíõðîí-
íîì ðåæèìå, èñïîëüçóþùèõ
ñ êîïèé ñòðóêòóðèðîâàííîãî
ïðîãðàììíîãî ðåñóðñà.
Ïóñòü ( , , ..., )t t ts1 2
� � � — äëè-
òåëüíîñòè âûïîëíåíèÿ êàæäîãî èç áëîêîâ Q j , j s�1, , ïðîãðàììíîãî ðåñóðñà
ñ ó÷åòîì íàêëàäíûõ ðàñõîäîâ �, t tj j
�
�� � , j s�1, . Îáîçíà÷èì T ts
j
s
j
s
�
�
�
�
1
äëè-
òåëüíîñòü âûïîëíåíèÿ âñåãî ïðîãðàììíîãî ðåñóðñà êàæäûì ïðîöåññîì. Ïîêà-
æåì, ÷òî â ýòèõ óñëîâèÿõ âû÷èñëåíèå îáùåãî âðåìåíè T p n s ñî
àñ ( , , , ) â ñëó÷àå íå-
îãðàíè÷åííîãî ïàðàëëåëèçìà ñâîäèòñÿ ê íàõîæäåíèþ îáùåãî âðåìåíè âûïîëíå-
íèÿ îäíîðîäíûõ ðàñïðåäåëåííûõ ïðîöåññîâ ïðè îäíîé êîïèè
ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà. Ïðè n mc� , m � 2 , 2 � �c p, âûïîë-
íåíèå ñ êîïèé ñòðóêòóðèðîâàííîãî ïðîãðàììíîãî ðåñóðñà â àñèíõðîííîì ðåæè-
114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
3
2
1
1
2
3
1
1
3
1
1
1
4
4
3
3
0
0
1
1
1
1
0
0
2
2
1
3
0
0
2
0
3
0
0
0
4
0
3
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
2
1
4
3
2
2
2
3
1
1
2
5
1
3
2
1
0
0
3
2
1
5
0
0
1
2
3
2
0
0
2
0
2
0
0
0
3
0
1
0
0
0
2
0
5
0
0
0
0
0
0
0
0
0
Ðèñ. 8. Ãðàô Gc
2
p
1t
3t
2t
1t
1t 1t
2t
2t
2t
3t 3t
3t
0 1 652 3 4 7 8 9 10 1211
1
2
3
4
5
6
7
Ðèñ. 9. Äèàãðàììà Ãàíòà àñèíõðîííîãî ðåæèìà (îäíî-
ðîäíûå ïðîöåññû)
T p n s cî
àñ( , , , )
ìå ðàâíîñèëüíî âûïîëíåíèþ ñ ãðóïï ïî m ïðîöåññîâ, êîíêóðèðóþùèõ çà èñïîëü-
çîâàíèå îäíîé êîïèè ïðîãðàììíîãî ðåñóðñà íà
p
c
�
�
�
�
ïðîöåññîðàõ.
Íà îñíîâàíèè ôîðìóëû [6] âû÷èñëåíèÿ îáùåãî âðåìåíè âûïîëíåíèÿ n îäíî-
ðîäíûõ êîíêóðèðóþùèõ ïðîöåññîâ, èñïîëüçóþùèõ îäíó êîïèþ ñòðóêòóðèðîâàí-
íîãî ïðîãðàììíîãî ðåñóðñà è ñ ó÷åòîì òîãî, ÷òî n mc� , m � 2, 2 � �c p, ïîëó÷àåì
T p mc s c T
p
c
m s T ms
o
àñ
o
àñ( , , , ) , , , (�
�
�
�
�
�
�
��
�
�
�� � �
1 1
�
) max
1� �j s
jt � . (3)
Äëÿ äîêàçàòåëüñòâà ôîðìóëû (3) âîñïîëüçóåìñÿ ôóíêöèîíàëîì (1) çàäà÷è
Áåëëìàíà–Äæîíñîíà, êîòîðûé äëÿ ñèñòåì îäíîðîäíûõ êîíêóðèðóþùèõ
ïðîöåññîâ ïðèìåò âèä
T p n s c t t
u u u m i
u
i us
o
àñ ( , , , ) max� �
� � � � � � �
�
1 1
1
2
1 2 1
1
1
�
� �
u
s
i u
m
j
j
s
j s
jt t m t
s
2
1 1 1
1� � �� �
�
�
�
�
�
� �
� � � �
�
� � ( ) max � ,
ãäå m
n
c
� , t tj j
�
�� � , j s�1, , à u u us1 2 1, , ...,
— öåëûå ÷èñëà.
 ñëó÷àå, êîãäà s
p
c
�
�
�
�
�
, s k
p
c
�
�
�
�
�
, k �1 , ìàòðèöà âðåìåí âûïîëíåíèÿ áëîêîâ
ïðîãðàììíîãî ðåñóðñà ñòðîèòñÿ àíàëîãè÷íî, êàê è ìàòðèöà T * . Îòëè÷èå ñîñòîèò
â òîì, ÷òî â êàæäîé èç ïîäìàòðèö T
l
� , l k�1, , ìàòðèöû T * âñå ñòðîêè ñîâïàäàþò.
Òîãäà, ïî àíàëîãèè ñ òåîðåìîé 2, îáùåå âðåìÿ T p n s cí
àñ ( , , , ) âûïîëíåíèÿ n ðàñïðå-
äåëåííûõ îäíîðîäíûõ êîíêóðèðóþùèõ ïðîöåññîâ ïðè îãðàíè÷åííîì ÷èñëå êî-
ïèé ïðîãðàììíîãî ðåñóðñà îïðåäåëÿåòñÿ äëèíîé êðèòè÷åñêîãî ïóòè èç
íà÷àëüíîé âåðøèíû â êîíå÷íóþ ñîîòâåòñòâóþùåãî ñåòåâîãî ãðàôà.
Åñëè s
p
c
�
�
�
�
�
, s k
p
c
r�
�
�
�
�
� , k � 1 , 1 � �
�
�
�
�
r
p
c
, òî ïîñëåäíÿÿ ïîäìàòðèöà T
k�1
�
ìàòðèöû T * áóäåò ñîäåðæàòü
p
c
r
�
�
�
�
íóëåâûõ ñòîëáöîâ.
Îïðåäåëåíèå 4. Îäíîðîäíîå ñòðóêòóðèðîâàíèå ïðîãðàììíîãî ðåñóðñà íà s
áëîêîâ ñ âðåìåíàìè âûïîëíåíèÿ ( , , , )t t ts1 2
� � �
� , t Tj
s
j
s
s
�
� �
1
�
, áóäåì íàçûâàòü ðàâ-
íîìåðíûì, åñëè t t t ts1 2
� � � �� � � �� .
Ñëåäñòâèå.  ñëó÷àå ðàâíîìåðíîãî ñòðóêòóðèðîâàíèÿ äëÿ âû÷èñëåíèÿ ìè-
íèìàëüíîãî îáùåãî âðåìåíè âûïîëíåíèÿ ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðî-
öåññîâ ïðè îãðàíè÷åííîì ÷èñëå êîïèé ïðîãðàììíîãî ïðîäóêòà èìåþò ìåñòî
ôîðìóëû
T p n s c
m s t
p
c
m s
km
p
c
p
àñ
{ }
( , , , )
( ) , min , ,
(�
�
�
�
�
�
�
�
�
�
1 �
�
�
�
�
�
�
� �
�
�
�
�
�
�
1 1
1
) , min , , , ,
(( )
t
p
c
m s s k
p
c
k
k
� { }
m r t
p
c
m s s k
p
c
r k r
p
�
�
�
�
�
� �
�
�
�
�
� � � �1 1 1) , min , , , ,� { }
c
�
�
�
�
�
�
�
�
�
�
�
�
� .
Ðàññìîòðèì ñèñòåìó îäèíàêîâî ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ.
Âðåìåíà âûïîëíåíèÿ âñåõ áëîêîâ ðàññìàòðèâàåìîé ñèñòåìû ñ ó÷åòîì íàêëàäíûõ
ðàñõîäîâ � êàæäûì i-ì ïðîöåññîì ñîâïàäàþò è ðàâíû ti
� , ò.å. ñïðàâåäëèâà öåïî÷êà ðà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 115
âåíñòâ t t
i i1 2
� �� �� � �tis
�
� ti
� äëÿ âñåõ i n�1, .
Íà ðèñ. 10 ïðåäñòàâ-
ëåíà äèàãðàììà Ãàíòà,
èëëþñòðèðóþùàÿ âûïîë-
íåíèå îäèíàêîâî ðàñïðå-
äåëåííûõ êîíêóðèðóþ-
ùèõ ïðîöåññîâ â ÌÑ
ñ ïàðàìåòðàìè p � 7, n � 4,
s � 3, c � 2, T � �
�
�
�
�
�
�
3 3 3
4 4 4
2 2 2
1 1 1
,
â ñëó÷àå íåîãðàíè÷åííîãî ( )s
p
c
�
�
�
�
�
ïàðàëëåëèçìà.
Îáîçíà÷èì T tq
q i c
i
m
�
��
�
�
� ( )1
1
ñóììàðíîå âðåìÿ âûïîëíåíèÿ êàæäîãî èç áëîêîâ
Q j , j s�1, , âñåìè m ïðîöåññàìè èç q-é ãðóïïû, à t tq
i m q i cmax ( )
max�
� � �
1 1
� — ìàêñèìàëü-
íîå âðåìÿ âûïîëíåíèÿ áëîêà èç ýòîé ãðóïïû, q c�1, . Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 3. Ìèíèìàëüíîå îáùåå âðåìÿ âûïîëíåíèÿ n, n � 2 , îäèíàêîâî ðàñ-
ïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ, èñïîëüçóþùèõ ñòðóêòóðèðîâàííûé íà
s, s � 2 , áëîêîâ ïðîãðàììíûé ðåñóðñ â ìíîãîïðîöåññîðíîé ñèñòåìå ñ p, p � 2 ,
ïðîöåññîðàìè â àñèíõðîííîì ðåæèìå ïðè îãðàíè÷åííîì ÷èñëå êîïèé ïðîãðàì-
ìíîãî ðåñóðñà, ñîñòàâëÿåò âåëè÷èíó T p n s coð
ac ( , , , ):
T p n s c
T s t s
p
c
q c
q q
oð
ac
ïðè
( , , , ) max
( ) max
�
�
�
�
�
�
�
� �1
1
�
èëè
ïðè ýòîì
s
p
c
T
p
c
t
kT
p
c
q q
q
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
,
;max�
�
�
�
��
�
�
�� �
�
�
�
�
� �
�
�
�
�
1 1t s k
p
c
k T
p
c
tq q
max m, ,ïðè
� ax
max
;
( ) ( ) , ,
q
q qk T r t s k
p
c
r k
r
p
c
� �
�
�
�
�
�
� �
� �
1 1 1
1
�
ïðè
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
, .maxT
p
c
tq q
�
Äëÿ äîêàçàòåëüñòâà ðàññìîòðèì ñíà÷àëà ñëó÷àé, êîãäà s
p
c
�
�
�
�
�
, èëè s
p
c
�
�
�
�
�
,
íî ïðè ýòîì T
p
c
tq q
�
�
�
�
�
�
max . Âîñïîëüçóåìñÿ ôóíêöèîíàëîì (1) çàäà÷è Áåëëìà-
íà–Äæîíñîíà, êîòîðûé äëÿ ñèñòåì îäèíàêîâî ðàñïðåäåëåííûõ êîíêóðèðóþùèõ
ïðîöåññîâ ïðèìåò âèä
T p n s c t
u u u m q i c
i
u
s
op
àñ ( , , , ) max
( )
�
� � � � � �
�
�
1 1
11 2 1
1
�
� � � �
�
�
�
�
�
�
�
�
�
�
� �
t t
q i c
i u
u
q i c
i u
m
s
( ) ( )1 1
1
2
1
� �
�
� �
� � �
T s tq
i m q i c�
�( ) max
( )
1
1 1
,
ãäå m n c� / , t t
q i c q i c�
�
� �
( ) ( )1 1
�
�, q c�1, , i m�1, , u u us1 2 1, , ...,
— öåëûå ÷èñëà.
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
p
2t 4t
1t 3t
1t 3t
1t 3t
2t 4t
2t 4t
1
2
3
4
5
6
7
0 1 652 3 4 7 8 9 10 1211
13
Ðèñ. 10. Äèàãðàììà Ãàíòà àñèíõðîííîãî ðåæèìà (îäèíàêîâî
ðàñïðåäåëåííûå ïðîöåññû)
T p n s cîp
àñ( , , , )
Äàëåå ðàññìîòðèì ñëó÷àé, êîãäà s k
p
c
�
�
�
�
�
, k �1 , è T
p
c
tq q
�
�
�
�
�
�
max . Âû÷èñëå-
íèå îáùåãî âðåìåíè T p n s cîð
àñ ( , , , ) â ýòîì ñëó÷àå ñ ïîìîùüþ ôóíêöèîíàëà çàäà÷è
Áåëëìàíà–Äæîíñîíà ïðèâîäèò ê ôîðìóëå
T p n s cîð
àñ ( , , , ) �
� �
� � � � � �
�
�
�
�
�
�
�max
( ) (1 1
11 2
1
1
u u u km q i c
i
u
q i
p
c
t t
�
�
� �
�
� �� �
�
�
�
�
�
�
�
�
�
�
�
1 1
1
2
1
) ( )c
i u
u
i u
km
q i c
p
c
t� �
�
�
� �
�
�
�
�
�
�
��
�
�
��kT
p
c
tq q
�
1 max .
Çäåñü t t
q i c km q i c�
� �
�
( ) ( )1 1
� � , q c�1, , i m�1, .
 ñëó÷àå, êîãäà s k
p
c
r�
�
�
�
�
� , k � 1 , 1 � �
�
�
�
�
r
p
c
è T
p
c
tq q
�
�
�
�
�
�
max , âû÷èñëåíèå
îáùåãî âðåìåíè ñ ïîìîùüþ ôóíêöèîíàëà çàäà÷è Áåëëìàíà–Äæîíñîíà ïðèâîäèò
ê òðåòüåé ôîðìóëå äëÿ âû÷èñëåíèÿ îáùåãî âðåìåíè âûïîëíåíèÿ îäèíàêîâî ðàñ-
ïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ ïðè îãðàíè÷åííîì ÷èñëå êîïèé
ïðîãðàììíîãî ðåñóðñà.
ÇÀÊËÞ×ÅÍÈÅ
Ðàññìîòðåííîå îáîáùåíèå ìàòåìàòè÷åñêîé ìîäåëè ñ îäíèì ñòðóêòóðèðîâàííûì
ïðîãðàììíûì ðåñóðñîì (êîíâåéåðîì) íà ñëó÷àé îãðàíè÷åííîãî ÷èñëà ïðîãðàììíûõ
ðåñóðñîâ ïîçâîëÿåò óñòàíîâèòü âçàèìîñâÿçè ìóëüòèêîíâåéåðíîé îáðàáîòêè ñ àíàëî-
ãè÷íîé îáðàáîòêîé ïðè îäíîì ïðîãðàììíîì êîíâåéåðå. Ïðè ýòîì ìîæåì ïîëó÷èòü
àíàëèòè÷åñêèå îöåíêè îáùåãî âðåìåíè âûïîëíåíèÿ êîíêóðèðóþùèõ ïðîöåññîâ ïðè
îãðàíè÷åííîì ïàðàëëåëèçìå è ïðîâåñòè ìàòåìàòè÷åñêîå èññëåäîâàíèå ýôôåêòèâíîñòè
è îïòèìàëüíîñòè ìóëüòèêîíâåéåðíîé îðãàíèçàöèè êîíêóðèðóþùèõ ïðîöåññîâ, îïðå-
äåëèòü ïîòåíöèàëüíûå âîçìîæíîñòè ðîñòà óñêîðåíèÿ âû÷èñëåíèé, âûïîëíèòü ñðàâ-
íèòåëüíûé àíàëèç ðàçëè÷íûõ ðåæèìîâ òàêîé îáðàáîòêè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê à ï è ò î í î â à Þ .  . , Ë å ò è ÷ å â ñ ê è é À . À . Ìàòåìàòè÷åñêàÿ òåîðèÿ ïðîåêòèðîâàíèÿ
âû÷èñëèòåëüíûõ ñèñòåì. — Ì.: Íàóêà, 1988. — 296 ñ.
2. Ê à ï è ò î í î â à Þ . Â . , Ê î â à ë å í ê î Í . Ñ . , Ï à â ë î â Ï . À . Îïòèìàëüíîñòü ñèñòåì îäèíàêîâî
ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 6. —
Ñ. 3–10.
3. Ê à ï è ò î í î â à Þ . Â . , Ê î â à ë å í ê î Í . Ñ . , Ï à â ë î â Ï . À . Îïòèìàëüíîñòü ñèñòåì îäèíàêîâî
ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 6. —
Ñ. 3–10.
4. Ê à ï è ò î í î â à Þ . Â . , Ê î â à ë å í ê î Í . Ñ . , Î â ñ å å ö Ì . È . Ýôôåêòèâíîñòü êîíâåéåðíîé
ðåàëèçàöèè êîíêóðèðóþùèõ ïðîöåññîâ ïðè îãðàíè÷åííîì ÷èñëå êîïèé ïðîãðàììíîãî ðåñóðñà //
Êèáåðíåòèêà. — 1989. — ¹ 3. — Ñ. 60–65.
5. È â à í í è ê î â Â . Ï . , Ê î â à ë å í ê î Í . Ñ . , Ì å ò å ë ü ñ ê è é Â . Ì . Î ìèíèìàëüíîì âðåìåíè
ðåàëèçàöèè ðàñïðåäåëåííûõ êîíêóðèðóþùèõ ïðîöåññîâ â ñèíõðîííûõ ðåæèìàõ // Ïðîãðàì-
ìèðîâàíèå. — 2000. — ¹ 5. — Ñ. 44–52.
6. Ê î â à ë å í ê î Í . Ñ . , Ì å ò å ë ü ñ ê è é Â . Ì . Î âðåìåíè ðåàëèçàöèè êîíêóðèðóþùèõ ïðîöåññîâ
ïðè ðàñïðåäåëåííîé îáðàáîòêå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1996. — ¹ 1. — Ñ. 54–64.
7. Ê î â à ë å í ê î Í . Ñ . , Ï à â ë î â Ï . À . Ñèñòåìû îäèíàêîâî ðàñïðåäåëåííûõ êîíêóðèðóþùèõ
ïðîöåññîâ â óñëîâèÿõ îãðàíè÷åííîãî ïàðàëëåëèçìà è èõ îïòèìàëüíîñòü // Äîêë. ÍÀÍ Áåëàðóñi. Ñåð.
ôiç.–ìàò. íàâóê. — 2006. — ¹ 2. — Ñ. 25–29.
8. Ï à â ë î â Ï . À . Àíàëèç ðåæèìîâ îðãàíèçàöèè îäèíàêîâî ðàñïðåäåëåííûõ êîíêóðèðóþùèõ
ïðîöåññîâ // Âåñòíèê ÁÃÓ. Ñåð. 1. — 2006. — ¹ 1. — Ñ. 116–120.
Ïîñòóïèëà 25.05.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 117
|