Модель работы локального планировщика на основе решения задач нелинейного булевого программирования
Рассмотрена имитационная модель работы грид-системы, позволяющая сравнивать существующие методы планирования выполнения заданий, и дано математическое описание исследуемых в модели характеристик. Приведен пример решения задачи на основе метода групповой выборки. Получены экспериментальные результаты...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2017 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/144797 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Модель работы локального планировщика на основе решения задач нелинейного булевого программирования / Е.С. Листровая, В.А. Брыксин, М.С. Курцев // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 129–140. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144797 |
|---|---|
| record_format |
dspace |
| spelling |
Листровая, Е.С. Брыксин, В.А. Курцев, М.С. 2019-01-04T18:29:06Z 2019-01-04T18:29:06Z 2017 Модель работы локального планировщика на основе решения задач нелинейного булевого программирования / Е.С. Листровая, В.А. Брыксин, М.С. Курцев // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 129–140. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144797 621.396 Рассмотрена имитационная модель работы грид-системы, позволяющая сравнивать существующие методы планирования выполнения заданий, и дано математическое описание исследуемых в модели характеристик. Приведен пример решения задачи на основе метода групповой выборки. Получены экспериментальные результаты, доказывающие преимущества метода планирования выполнения заданий на основе решения задач булевого нелинейного программирования. Розглянуто імітаційну модель роботи грід-системи, яка дозволяє порівнювати наявні методи планування виконання завдань, та дано математичний опис досліджуваних в моделі характеристик. Наведено приклад розв’язання задачі на основі методу групової вибірки. Отримано експериментальні результати, що доводять переваги методу планування виконання завдань на основі розв’язання задач булевого нелінійного програмування. The simulation model of grid system operation is considered, which allows comparing available job scheduling methods. The mathematical description of the characteristics analyzed in the model is given. An example of problem solution based on cluster sampling method is presented. The experimental results are obtained, which demonstrate the advantages of scheduling method based on the solution of Boolean linear programming problems. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Модель работы локального планировщика на основе решения задач нелинейного булевого программирования Модель роботи локального планувальника на основі розв’язання задач нелінійного булевого програмування Modeling local planner operation based on solution of nonlinear Boolean programming problems 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 |
Модель роботи локального планувальника на основі розв’язання задач нелінійного булевого програмування Modeling local planner operation based on solution of nonlinear Boolean programming problems |
| description |
Рассмотрена имитационная модель работы грид-системы, позволяющая сравнивать существующие методы планирования выполнения заданий, и дано математическое описание исследуемых в модели характеристик. Приведен пример решения задачи на основе метода групповой выборки. Получены экспериментальные результаты, доказывающие преимущества метода планирования выполнения заданий на основе решения задач булевого нелинейного программирования.
Розглянуто імітаційну модель роботи грід-системи, яка дозволяє порівнювати наявні методи планування виконання завдань, та дано математичний опис досліджуваних в моделі характеристик. Наведено приклад розв’язання задачі на основі методу групової вибірки. Отримано експериментальні результати, що доводять переваги методу планування виконання завдань на основі розв’язання задач булевого нелінійного програмування.
The simulation model of grid system operation is considered, which allows comparing available job scheduling methods. The mathematical description of the characteristics analyzed in the model is given. An example of problem solution based on cluster sampling method is presented. The experimental results are obtained, which demonstrate the advantages of scheduling method based on the solution of Boolean linear programming problems.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/144797 |
| citation_txt |
Модель работы локального планировщика на основе решения задач нелинейного булевого программирования / Е.С. Листровая, В.А. Брыксин, М.С. Курцев // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 129–140. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT listrovaâes modelʹrabotylokalʹnogoplanirovŝikanaosnoverešeniâzadačnelineinogobulevogoprogrammirovaniâ AT bryksinva modelʹrabotylokalʹnogoplanirovŝikanaosnoverešeniâzadačnelineinogobulevogoprogrammirovaniâ AT kurcevms modelʹrabotylokalʹnogoplanirovŝikanaosnoverešeniâzadačnelineinogobulevogoprogrammirovaniâ AT listrovaâes modelʹrobotilokalʹnogoplanuvalʹnikanaosnovírozvâzannâzadačnelíníinogobulevogoprogramuvannâ AT bryksinva modelʹrobotilokalʹnogoplanuvalʹnikanaosnovírozvâzannâzadačnelíníinogobulevogoprogramuvannâ AT kurcevms modelʹrobotilokalʹnogoplanuvalʹnikanaosnovírozvâzannâzadačnelíníinogobulevogoprogramuvannâ AT listrovaâes modelinglocalplanneroperationbasedonsolutionofnonlinearbooleanprogrammingproblems AT bryksinva modelinglocalplanneroperationbasedonsolutionofnonlinearbooleanprogrammingproblems AT kurcevms modelinglocalplanneroperationbasedonsolutionofnonlinearbooleanprogrammingproblems |
| first_indexed |
2025-11-26T13:21:02Z |
| last_indexed |
2025-11-26T13:21:02Z |
| _version_ |
1850622523853504512 |
| fulltext |
ÓÄÊ 621.396
Å.Ñ. ËÈÑÒÐÎÂÀß, Â.À. ÁÐÛÊÑÈÍ, Ì.Ñ. ÊÓÐÖÅÂ
ÌÎÄÅËÜ ÐÀÁÎÒÛ ËÎÊÀËÜÍÎÃÎ ÏËÀÍÈÐÎÂÙÈÊÀ
ÍÀ ÎÑÍÎÂÅ ÐÅØÅÍÈß ÇÀÄÀ× ÍÅËÈÍÅÉÍÎÃÎ
ÁÓËÅÂÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
Àííîòàöèÿ. Ðàññìîòðåíà èìèòàöèîííàÿ ìîäåëü ðàáîòû ãðèä-ñèñòåìû, ïî-
çâîëÿþùàÿ ñðàâíèâàòü ñóùåñòâóþùèå ìåòîäû ïëàíèðîâàíèÿ âûïîëíåíèÿ çà-
äàíèé, è äàíî ìàòåìàòè÷åñêîå îïèñàíèå èññëåäóåìûõ â ìîäåëè õàðàêòåðèñ-
òèê. Ïðèâåäåí ïðèìåð ðåøåíèÿ çàäà÷è íà îñíîâå ìåòîäà ãðóïïîâîé âûáîð-
êè. Ïîëó÷åíû ýêñïåðèìåíòàëüíûå ðåçóëüòàòû, äîêàçûâàþùèå ïðåèìóùåñòâà
ìåòîäà ïëàíèðîâàíèÿ âûïîëíåíèÿ çàäàíèé íà îñíîâå ðåøåíèÿ çàäà÷ áóëåâî-
ãî íåëèíåéíîãî ïðîãðàììèðîâàíèÿ.
Êëþ÷åâûå ñëîâà: ãðèä-ñèñòåìû, ïëàíèðîâàíèå, ðåñóðñ, êëàñòåð, ïàêåòíàÿ
îáðàáîòêà, ãðóïïîâàÿ âûáîðêà.
ÂÂÅÄÅÍÈÅ
Ñèñòåìû ïëàíèðîâàíèÿ âûïîëíåíèÿ çàäà÷ ðàçðàáîòàíû äëÿ ýôôåêòèâíîãî
è ãèáêîãî íàçíà÷åíèÿ ïîñòóïèâøèõ â î÷åðåäü çàäà÷ íà äîñòóïíûå âû÷èñëè-
òåëüíûå ðåñóðñû ðàñïðåäåëåííûõ ñèñòåì îáðàáîòêè äàííûõ (ÐÑÎÄ). Ïðè ôîð-
ìèðîâàíèè î÷åðåäè çàäàíèé â ÐÑÎÄ îñíîâíîé ïðîáëåìîé ÿâëÿåòñÿ òðó-
äîåìêîñòü íàñòðîéêè ïðîãðàììíîãî îáåñïå÷åíèÿ, âûïîëíÿþùåãî èõ íàçíà÷å-
íèå íà âû÷èñëèòåëüíûå ðåñóðñû. Òðóäîåìêîñòü çàâèñèò îò ñëåäóþùèõ
ôàêòîðîâ: 1) ðàçíîðîäíîñòü çàäà÷ ïî ðåñóðñíûì òðåáîâàíèÿì, àïïàðàòíàÿ ãåòå-
ðîãåííîñòü âû÷èñëèòåëüíûõ óçëîâ è ðàçëè÷íàÿ çàãðóçêà óçëîâ ÐÑÎÄ òðåáóþò
ñïåöèàëüíîãî ó÷åòà, ÷òî îáóñëîâëèâàåò ôîðìèðîâàíèå ñëîæíûõ ïîëèòèê ïëà-
íèðîâàíèÿ; 2) îòñóòñòâèå ïîëíîé èíôîðìàöèè î ðåñóðñíûõ òðåáîâàíèÿõ çàäà÷
çàòðóäíÿåò ïðèíÿòèå èíòåëëåêòóàëüíûõ ðåøåíèé ïî èõ ïëàíèðîâàíèþ.
Øèðîêîå ïðèìåíåíèå êëàñòåðíûõ, îáëà÷íûõ è ãðèä-ñèñòåì ñâÿçàíî ñ óâåëè-
÷åíèåì ÷èñëà ðåøàåìûõ ïðèêëàäíûõ çàäà÷ è çíà÷èòåëüíûì âîçðàñòàíèåì íàãðó-
çîê íà âû÷èñëèòåëüíûå ñèñòåìû.
Äåéñòâóþùèìè âåðñèÿìè ñèñòåì óïðàâëåíèÿ ïàêåòíîé îáðàáîòêîé (ÑÓÏÎ)
ÿâëÿþòñÿ: Platform LSF, Windows Compute Cluster Server, Condor, PBS, SGE,
TORQUE, LoadLever, MOSIX [1]. Îäíà èç íàèáîëåå âàæíûõ ôóíêöèé ÑÓÏÎ —
îáåñïå÷åíèå ìåõàíèçìà ïëàíèðîâàíèÿ ðàñïðåäåëåíèÿ çàäàíèé. Äàííàÿ ôóíêöèÿ
ìîæåò áûòü ðåàëèçîâàíà íåïîñðåäñòâåííî ðàçðàáîò÷èêàìè êîíêðåòíîé ÑÓÏÎ
ëèáî ñ ïîìîùüþ âíåøíèõ ïëàíèðîâùèêîâ — îòäåëüíî ðàçðàáîòàííûõ ïðîãðàì-
ìíûõ ñðåäñòâ (íàïðèìåð, Maui). Îñíîâà êàæäîãî ïëàíèðîâùèêà — àëãîðèòì, îò
êîòîðîãî çàâèñèò ýôôåêòèâíîñòü óïðàâëåíèÿ çàäàíèÿìè â öåëîì. Â [2–4] ïðèâåäå-
íà êîíöåïòóàëüíàÿ ñõåìà ïëàíèðîâàíèÿ ïàêåòîâ çàäàíèé â ðàñïðåäåëåííîé âû÷èñ-
ëèòåëüíîé ñðåäå, èñïîëüçóþùàÿ â êà÷åñòâå àëãîðèòìà ïëàíèðîâàíèÿ ðåøåíèå çàäà-
÷è î íàèìåíüøåì ïîêðûòèè (ÇÍÏ). Öåëü äàííîé ñòàòüè — ðàçðàáîòêà ïðîöåäóðû
ïëàíèðîâàíèÿ, ïîçâîëÿþùåé óìåíüøèòü ñóììàðíîå âðåìÿ îáðàáîòêè çàäàíèé
â î÷åðåäè è óâåëè÷èòü ñóììàðíûé êîýôôèöèåíò âàæíîñòè èñïîëüçîâàíèÿ ðåñóð-
ñîâ ïî ñðàâíåíèþ ñ ïðîöåäóðîé ïëàíèðîâàíèÿ íà îñíîâå ðåøåíèÿ ÇÍÏ.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È È ÌÎÄÅËÜ ÏËÀÍÈÐÎÂÀÍÈß
Ïðîöåññ îáðàáîòêè çàïðîñîâ â êëàñòåðå. Çàäà÷è â ãðèä-ñèñòåìå ïðåäñòàâ-
ëÿþò ñîáîé îáû÷íûé èñïîëíÿåìûé ôàéë (ñêðèïò, ïðîãðàììíûé êîä). Ñëóæáà-
ìè ãðèä îíè äîñòàâëÿþòñÿ íà èñïîëíèòåëüíûå ðåñóðñû, à ñîáñòâåííî âûïîë-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 129
© Å.Ñ. Ëèñòðîâàÿ, Â.À. Áðûêñèí, Ì.Ñ. Êóðöåâ, 2017
íåíèå ïðîèñõîäèò â ñðåäå èõ îïåðàöèîííîé ñèñòåìû (ÎÑ). Êàê ïðàâèëî, ïðî-
ãðàììà, ðàçðàáîòàííàÿ íà êîíêðåòíîì êîìïüþòåðå, íå òðåáóåò êàêèõ-ëèáî
ìîäèôèêàöèé äëÿ èñïîëüçîâàíèÿ â ãðèä. Îäíàêî ëþáàÿ ïðîãðàììà ðàññ÷èòàíà
íà îïðåäåëåííóþ ñðåäó âûïîëíåíèÿ: ÎÑ, àðõèòåêòóðó êîìïüþòåðà, îáúåìû
è õàðàêòåðèñòèêè åãî ðåñóðñîâ.
Ïëàíèðîâùèê äîëæåí ó÷èòûâàòü, ÷òî êëàñòåð ãðèä-ñèñòåìû ÿâëÿåòñÿ ãåòåðî-
ãåííîé èíôðàñòðóêòóðîé, â ñîñòàâ êîòîðîé âêëþ÷åíû êîìïüþòåðû ñ ðàçëè÷íîé àð-
õèòåêòóðîé è êîìïëåêòàöèåé. Ãåòåðîãåííîñòü ïðîÿâëÿåòñÿ â òîì, ÷òî ðàçíûå êëàññû
ðåñóðñîâ (ïðîöåññîð, îñíîâíàÿ ïàìÿòü, êýø-ïàìÿòü, äèñêîâàÿ ïàìÿòü) ðàçëè÷àþòñÿ
òèïîì (ïðîöåññîðû — àðõèòåêòóðîé) è õàðàêòåðèñòèêàìè (ïðîöåññîðû — ïðîèçâî-
äèòåëüíîñòüþ, ïàìÿòü — îáúåìîì). Â ñâÿçè ñ ýòèì èñïîëíèòåëüíûå ðåñóðñû íå ìî-
ãóò áûòü ïðîèçâîëüíûìè, à äîëæíû ñîîòâåòñòâîâàòü òðåáîâàíèÿì çàäàíèÿ.
Ðàññìîòðèì ïàðàìåòð ðåñóðñíîãî çàïðîñà, îïðåäåëÿþùèé âðåìÿ èñïîëüçîâà-
íèÿ ðåñóðñîâ, ò.å. âûïîëíåíèÿ çàäàíèÿ. Èçâåñòíî, ÷òî îöåíêà åãî ïîëüçîâàòåëÿìè
ðåäêî áûâàåò òî÷íîé, îäíàêî íàëè÷èå äàííîãî ïàðàìåòðà âàæíî ïî äâóì ïðè÷è-
íàì. Âî-ïåðâûõ, äàæå ïðèáëèçèòåëüíàÿ îöåíêà âðåìåíè âûïîëíåíèÿ ïîçâîëÿåò èñ-
ïîëüçîâàòü áîëåå ýôôåêòèâíûå àëãîðèòìû ïëàíèðîâàíèÿ; âî-âòîðûõ, ñîãëàñíî îá-
ùåïðèíÿòîé ïðàêòèêå ðàáîòû â ñèñòåìàõ ñ ðàçäåëÿåìûìè ðåñóðñàìè âðåìÿ âûïîë-
íåíèÿ (êàê è ðåñóðñíûé çàïðîñ â öåëîì) ñëóæèò çàùèòîé îò ïðîãðàììíûõ îøèáîê,
ïðåäñòàâëÿÿ ñîáîé îãðàíè÷åíèÿ (ïî îáúåìàì è âðåìåíè) íà ïîòðåáëÿåìûå ðåñóðñû,
ò.å. ïðè ïðåâûøåíèè óêàçàííûõ â çàïðîñå ëèìèòîâ çàäàíèå ïðèíóäèòåëüíî çàâåð-
øàåòñÿ. Îòìåòèì, ÷òî ïàðàìåòð âðåìåíè èñïîëíåíèÿ çàäàåòñÿ â ðàñ÷åòå íà îïðåäå-
ëåííóþ ïðîèçâîäèòåëüíîñòü ðåñóðñîâ. Êàê â ïðîöåññå ïëàíèðîâàíèÿ, òàê è ïðè çà-
ïóñêå çàäàíèÿ äîëæåí ïðîâîäèòüñÿ ïåðåñ÷åò âðåìåíè â ñîîòâåòñòâèè ñ êîíêðåòíû-
ìè èñïîëíèòåëüíûìè ðåñóðñàìè. Íà ïðàêòèêå ïîëó÷èëè ðàñïðîñòðàíåíèå
íåñêîëüêî ðàçíûõ ÿçûêîâ ðåñóðñíûõ çàïðîñîâ [2]. ßçûê RSL, ïðèìåíÿåìûé â ñèñ-
òåìå Globus Toolkit, îðèåíòèðîâàí íà çàïóñê êàê îäíîïðîöåññîðíûõ, òàê è ìíîãî-
ïðîöåññîðíûõ MPI-çàäàíèé. ßçûêè ClassAd ñèñòåìû Condor è JDL (WMS) ïîçâî-
ëÿþò îïðåäåëÿòü àëüòåðíàòèâíûå âàðèàíòû ðåñóðñíîãî çàïðîñà è ñïåöèôèöèðî-
âàòü ïîëüçîâàòåëüñêèå ïðåäïî÷òåíèÿ ïðè âûáîðå ðåñóðñîâ. Â ðÿäå ðàáîò [1–3]
ïðåäëàãàþòñÿ ñóùåñòâåííûå ðàñøèðåíèÿ ôîðìàëèçìà ÿçûêà çàïðîñîâ, íàïðàâëåí-
íûå íà ñïåöèôèêàöèþ ñâÿçàííûõ ìåæäó ñîáîé çàäàíèé è öåïî÷åê çàäàíèé.
Ïðè ïëàíèðîâàíèè îòáîð ðåñóðñîâ âûïîëíÿåòñÿ ïî èíôîðìàöèîííîé áàçå,
ñîäåðæàùåé ñâåäåíèÿ î ñîñòàâå è õàðàêòåðèñòèêàõ ðåñóðñîâ ãðèä. Ïåðåäà÷à ýòèõ
äàííûõ â èíôîðìàöèîííóþ áàçó îñóùåñòâëÿåòñÿ â îïåðàòèâíîì ðåæèìå ñïåöèà-
ëèçèðîâàííûìè ðàñïðåäåëåííûìè ñèñòåìàìè ìîíèòîðèíãà ðåñóðñîâ, èç êîòîðûõ
íàèáîëåå ïðèìåíÿåìûå — MDS è R-GMA. Ðåñóðñíûé çàïðîñ èñïîëüçóåòñÿ êàê
ôîðìàëüíûé êðèòåðèé îòáîðà, îäíàêî îí òîëüêî ñóæàåò ìíîæåñòâî âîçìîæíûõ
èñïîëíèòåëüíûõ ðåñóðñîâ.
Ðàññìîòðèì ïëàíèðîâàíèå íà îñíîâå ïðèîðèòåòîâ, ïðåäïîëàãàþùåå, ÷òî ðå-
ñóðñû äëÿ áîëåå ïðèîðèòåòíûõ çàäàíèé âûäåëÿþòñÿ ðàíüøå, ÷åì äëÿ ìåíåå ïðè-
îðèòåòíûõ. Â ýòèõ óñëîâèÿõ øèðîêî èñïîëüçóåìûå àëãîðèòìû òèïà FCFS (FIFO)
ðàáîòàþò ïî ïðèíöèïó âûäåëåíèÿ îñâîáîäèâøèõñÿ ðåñóðñîâ ñàìîìó ïðèîðèòåò-
íîìó çàäàíèþ èç î÷åðåäè, êîòîðîå ìîæåò íà íèõ ðàçìåñòèòüñÿ. Ïðè ýòîì áîëü-
øàÿ ÷àñòü ïðîöåññîðîâ áóäåò çàíÿòà ìåëêèìè çàäàíèÿìè, ò.å. âîçíèêàåò ôðàãìåí-
òàöèÿ ðåñóðñîâ. Äàæå åñëè çàäàíèå èìååò ñàìûé âûñîêèé ïðèîðèòåò, íåîáõîäè-
ìûé åìó îáúåì ðåñóðñîâ ìîæåò íå îáðàçîâàòüñÿ è, ñëåäîâàòåëüíî, çàäàíèå
íèêîãäà íå ñòàðòóåò. Äëÿ ñðåäû, îáñëóæèâàþùåé îäíîïðîöåññîðíûå çàäàíèÿ, òà-
êîé ïðîáëåìû íåò. Îíà ïîÿâëÿåòñÿ, êîãäà èìåþòñÿ ðàçäåëÿåìûå ðåñóðñû, íàïðè-
ìåð ïðè îáñëóæèâàíèè ìíîãîïðîöåññîðíûõ çàäàíèé. Àíàëîãè÷íàÿ ñèòóàöèÿ
âîçíèêàåò íà ìàøèíàõ ñ îáùåé ïàìÿòüþ, â ñðåäå ñ îáùèì ôàéëîâûì ïðîñòðàí-
ñòâîì è â äðóãèõ ñëó÷àÿõ, êîãäà ðåñóðñû äåëÿòñÿ ìåæäó çàäàíèÿìè, à íå âûäåëÿ-
þòñÿ ïîä çàäàíèå öåëèêîì.
130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
Ïëàíèðîâàíèå â ãðèä ðàññìàòðèâàåì êàê öèêëè÷åñêèé ïðîöåññ, âî âðåìÿ êî-
òîðîãî ôèêñèðîâàííîå íà ìîìåíò ïëàíèðîâàíèÿ ìíîæåñòâî çàäàíèé, íàõîäÿùèõ-
ñÿ â î÷åðåäè, îáðàáàòûâàåòñÿ è ðàñïðåäåëÿåòñÿ ïî ðåñóðñàì, ïðè ýòîì îïðåäåëÿ-
åòñÿ âðåìÿ âûäåëåíèÿ ðåñóðñîâ è èõ àäðåñà. Â äàííîì ïðîöåññå, êîòîðûé âûïîë-
íÿåòñÿ â êîíòåêñòå äèñïåò÷åðèçàöèè, îñóùåñòâëÿåòñÿ êîîðäèíàöèÿ ðàçäåëåíèÿ
ðåñóðñîâ ìåæäó çàäàíèÿìè ïîëüçîâàòåëåé. Â ñðåäå òàêîãî ìàñøòàáà, êàê ãðèä,
ïëàíèðîâàíèå ÿâëÿåòñÿ âàæíåéøèì ìåõàíèçìîì îáåñïå÷åíèÿ êà÷åñòâà îáñëóæè-
âàíèÿ, êîòîðîå âûðàæàåòñÿ, ïðåæäå âñåãî, â îáåñïå÷åíèè ïðèåìëåìîãî è ïðåä-
ñêàçóåìîãî âðåìåíè âûïîëíåíèÿ çàäàíèé ïîëüçîâàòåëÿ, à òàêæå ãèáêîñòè ïîëè-
òèêè ðàñïðåäåëåíèÿ ðåñóðñîâ â ñîîòâåòñòâèè ñ ïðèîðèòåòàìè.
Ðåñóðñû, èñïîëüçóþùèåñÿ â ðåæèìå ðàçäåëåíèÿ ìåæäó âëàäåëüöàìè è ïîëü-
çîâàòåëÿìè ãðèä, íàçûâàþò íåîò÷óæäàåìûìè. Ïðåèìóùåñòâî ãðèä ñ íåîò÷óæäàå-
ìûìè ðåñóðñàìè â òîì, ÷òî íå òðåáóåòñÿ çàòðàò íà ôîðìèðîâàíèå ñïåöèàëüíîé
ðåñóðñíîé áàçû è êëàñòåð ãðèä ìîæåò ñîçäàâàòüñÿ äèíàìè÷åñêè íà îãðàíè÷åííûé
ïåðèîä âðåìåíè â öåëÿõ ðåøåíèÿ êàêîé-ëèáî ïðîáëåìû, äëÿ êîòîðîé íå õâàòàåò
ðåñóðñîâ îòäåëüíûõ ÷ëåíîâ êîîïåðàöèè. Ñ òî÷êè çðåíèÿ ïëàíèðîâàíèÿ íåîò÷óæ-
äàåìîñòü ðåñóðñîâ óñëîæíÿåò ñèòóàöèþ, ïîñêîëüêó â ýòîì ñëó÷àå íà íèõ ïîñòó-
ïàåò äâà ïîòîêà çàäàíèé: ïîòîê èç ãðèä (ãëîáàëüíûé), óïðàâëÿåìûé ïëàíèðîâùè-
êîì; ëîêàëüíûé ïîòîê çàäàíèé, çàïóñêàåìûõ ñðåäñòâàìè, îòëè÷íûìè îò ïîëüçî-
âàòåëüñêèõ èíòåðôåéñîâ ãðèä. Íàïðèìåð, â óñëîâèÿõ êëàñòåðèçîâàííûõ ðåñóðñîâ
ëîêàëüíûå çàäàíèÿ ââîäÿòñÿ íåïîñðåäñòâåííî ÷åðåç èíòåðôåéñû ñèñòåìû ïàêåò-
íîé îáðàáîòêè. Òàêèì îáðàçîì, ëîêàëüíûå çàäàíèÿ íåïîäêîíòðîëüíû ïëàíèðîâ-
ùèêó, õîòÿ ñîçäàâàåìàÿ èìè çàãðóçêà ðåñóðñîâ äîëæíà ó÷èòûâàòüñÿ ïëàíèðîâùè-
êîì ïðè ðàñïðåäåëåíèè ãëîáàëüíûõ çàäàíèé.
Ôóíêöèîíèðîâàíèå ãðèä-ñèñòåì âû÷èñëèòåëüíîãî òèïà ìîæíî ðàññìàòðèâàòü
êàê ïðîöåññ îáñëóæèâàíèÿ ñòàíäàðòèçèðîâàííûõ çàïðîñîâ íà âûïîëíåíèå âû÷èñëå-
íèé, îôîðìëåííûõ â âèäå çàäàíèé äëÿ îáùåðàñïðîñòðàíåííûõ ÎÑ, ïðè÷åì âûïîë-
íÿþòñÿ ýòè çàäàíèÿ íà ðåñóðñàõ, âûáèðàåìûõ èç îáùåãî ïóëà. Ïåðå÷èñëèì îñíîâ-
íûå ýòàïû îáðàáîòêè çàäàíèÿ: ïðèñâîåíèå ïðèîðèòåòîâ çàäàíèÿì, ìîíèòîðèíã ñî-
ñòîÿíèÿ ðåñóðñîâ ñèñòåìû è âûïîëíåíèÿ çàäàíèé íà îñíîâå äàííûõ ñèñòåìû
íàáëþäåíèÿ; ïëàíèðîâàíèå âûáîðêè çàäàíèé èç î÷åðåäè; âûäåëåíèå èç îáùåãî ïóëà
èñïîëíèòåëüíûõ ðåñóðñîâ, íà êîòîðûõ çàäàíèå áóäåò âûïîëíÿòüñÿ; äîñòàâêà èñïîë-
íÿåìûõ è âõîäíûõ ôàéëîâ íà èñïîëíèòåëüíûå ðåñóðñû; âûïîëíåíèå çàäàíèÿ; ïî
îêîí÷àíèè îáðàáîòêè çàäàíèÿ äîñòàâêà ðåçóëüòèðóþùèõ ôàéëîâ íà ñåðâåðû õðàíå-
íèÿ (â ÷àñòíîñòè, íà ðàáî÷åå ìåñòî ïîëüçîâàòåëÿ).
Ïåðå÷èñëåííûå ýòàïû îáðàáîòêè çàäàíèÿ âûïîëíÿþòñÿ àâòîìàòè÷åñêè, áåç
ó÷àñòèÿ ñóáúåêòà, âûäàâøåãî çàïðîñ, ïîýòîìó êëàñòåðû ãðèä-ñèñòåì ïðåäñòàâëÿ-
þò ñîáîé åäèíóþ îïåðàöèîííóþ ñðåäó.
Õàðàêòåðèñòèêè ïðîöåññà îáðàáîòêè çàïðîñîâ â êëàñòåðå. Ïðè íàëè÷èè
îãðàíè÷åíèé íà ðàçìåð õðàíèìîé î÷åðåäè â ñèñòåìå ìîæåò âîçíèêíóòü ñèòóàöèÿ,
ïðè êîòîðîé î÷åðåäíîé çàïðîñ íà âûïîëíåíèå çàäàíèÿ, ïîñòóïèâøèé íà âõîä
ñèñòåìû, íå áóäåò ïðèíÿò ê îáñëóæèâàíèþ, ÷òî ïðèâåäåò ê åãî ïîòåðå èëè çàäåð-
æêå â îáñëóæèâàíèè. Ïîýòîìó àêòóàëüíîé ÿâëÿåòñÿ ðàçðàáîòêà ñèñòåìû ñ ïðèåì-
ëåìîé (òðåáóåìîé) ñêîðîñòüþ îáñëóæèâàíèÿ çàäàíèé, ïîñòóïàþùèõ ñ çàäàííîé
èíòåíñèâíîñòüþ.
Îòìåòèì äîïîëíèòåëüíûå òðåáîâàíèÿ ê ñèñòåìå óïðàâëåíèÿ: îäíîâðåìåí-
íûé äîñòóï ê ëþáîìó êîëè÷åñòâó ñâîáîäíûõ ðåñóðñîâ íà òåêóùèé ìîìåíò âðå-
ìåíè; íà îäíîì ðåñóðñå ñèñòåìû ìîæåò âûïîëíÿòüñÿ òîëüêî îäíî çàäàíèå.
Ïîä ðàçðåøåíèåì î÷åðåäè çàäàíèé áóäåì ïîíèìàòü ïðîöåññ ïîýòàïíîé âû-
áîðêè çàäàíèé èç î÷åðåäè, êîòîðûå íåîáõîäèìî è âîçìîæíî âûïîëíèòü íà äàí-
íîì ýòàïå. Çàäàíèÿ â î÷åðåäü ïîñòóïàþò â ëþáîé ìîìåíò âðåìåíè, íî åå ñîñòîÿ-
íèå îïðåäåëÿåòñÿ òîëüêî ìåæäó ýòàïàìè.
Äëÿ ðàçðåøåíèÿ î÷åðåäè íåîáõîäèìî îïðåäåëèòü íàèáîëåå ïðèåìëåìûé
ñïîñîá âûáîðêè çàäàíèé è íàèëó÷øèé ìåòîä åãî ðåàëèçàöèè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 131
Äëÿ îöåíêè ýôôåêòèâíîñòè âûáîðêè çàäàíèé ïðèìåíèì êîýôôèöèåíò èñ-
ïîëüçîâàíèÿ ðåñóðñîâ KÈÐ . Äàííûé êîýôôèöèåíò ïîêàçûâàåò, êàêàÿ ÷àñòü ðåñóð-
ñîâ èç îáùåãî êîëè÷åñòâà, ê êîòîðûì îáðàùàþòñÿ ðàçìåùåííûå â î÷åðåäè çàäà-
íèÿ, áóäåò èñïîëüçîâàíà. Åñëè KÈÐ � 0, òî íè îäèí ðåñóðñ íå çàäåéñòâîâàí,
à åñëè KÈÐ �1, òî èñïîëüçóþòñÿ âñå ðåñóðñû, äëÿ êîòîðûõ ñóùåñòâóþò çàäàíèÿ
íà òåêóùèé ìîìåíò. Îäíàêî íå âñåãäà âîçìîæíî âûáðàòü òàêèå çàäàíèÿ, ÷òîáû
áûëè çàäåéñòâîâàíû âñå ðåñóðñû. Ïîýòîìó ñòàâèòñÿ çàäà÷à âûáîðà òàêîãî ñïîñî-
áà ðàçðåøåíèÿ î÷åðåäè çàäàíèé, ïðè êîòîðîì KÈÐ ñòðåìèëîñü áû ê 1.  îáùåì
âèäå KÈÐ îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
K
N
N
ÈÐ
È
O
� , (1)
ãäå N È — êîëè÷åñòâî ðåñóðñîâ, çàäåéñòâîâàííûõ ïðè ðåàëèçàöèè îïðåäåëåí-
íîé âûáîðêè; N O — êîëè÷åñòâî ðåñóðñîâ, íà êîòîðûõ ìîæåò áûòü ðåøåíà
âûáîðêà çàäà÷ èç î÷åðåäè.
 äàííîì âèäå KÈÐ íå ó÷èòûâàåò ïðèîðèòåòîâ çàäàíèé, ïîýòîìó èõ íåîáõî-
äèìî ó÷åñòü â êîýôôèöèåíòå (1). Ïðè ýòîì ïðåäñòàâëåíèå êîýôôèöèåíòà KÈÐ
áóäåò çàâèñåòü îò âûáðàííîãî ñïîñîáà âûáîðêè, à òî÷íåå, òîëüêî ÷èñëèòåëü â (1).
Ïóñòü Yi — ìàêñèìàëüíàÿ âåëè÷èíà ïðèîðèòåòà çàäàíèé èç î÷åðåäè, îáðàùàþ-
ùèõñÿ ê ðåñóðñó Ri , òîãäà çíàìåíàòåëü ïðèìåò âèä
N Yi
i
M
O �
�
�
1
. (2)
Äëÿ îáñëóæèâàíèÿ çàäàíèé íàèáîëåå ïåðñïåêòèâíû ñïîñîáû ãðóïïîâîé âû-
áîðêè, ïðè ðåàëèçàöèè êîòîðûõ èç î÷åðåäè îáñëóæèâàåòñÿ íåñêîëüêî çàäàíèé îä-
íîâðåìåííî. Âûáèðàþòñÿ çàäàíèÿ, òðåáóþùèå îáðàáîòêè íà ðàçíûõ ðåñóðñàõ,
ñ ìàêñèìàëüíîé ñóììîé èõ ïðèîðèòåòîâ.  ñëó÷àå íàëè÷èÿ ðàâíîçíà÷íûõ çàäà-
íèé âûáèðàþò áîëåå «ñòàðûå».
Ïóñòü { }
�
X — ìíîæåñòâî âñåõ âàðèàíòîâ âûáîðêè çàäàíèé èç î÷åðåäè,
�
X —
îäèí èç âàðèàíòîâ âûáîðêè çàäàíèé, ïðè÷åì
�
� �X x x x xp N� { }1 2, , , , , , p N�1, , (3)
ãäå N — êîëè÷åñòâî çàäàíèé â î÷åðåäè, x p — áóëåâà ïåðåìåííàÿ, ðàâíàÿ 1,
åñëè çàäàíèå Ç ð âûáðàíî â äàííîì âàðèàíòå, è 0, åñëè íåò.
Ïóñòü � p — ïðèîðèòåò çàäàíèÿ Ç ð . Òîãäà ÷èñëèòåëü èç (1) ïðèìåò âèä
N x
p
N
p pÈ �
�
�
1
� . (4)
Ñ ó÷åòîì (2) è (4) ïîëó÷àåì KÈÐ ñëåäóþùåãî âèäà:
K
x
Y
p p
p
N
i
i
MÈÐ �
�
�
�
�
�
1
1
. (5)
Äëÿ òîãî ÷òîáû KÈÐ ïðèíÿë åäèíè÷íîå çíà÷åíèå, íåîáõîäèìî, ÷òîáû ÷èñëè-
òåëü (4) èç (5) áûë ðàâåí çíàìåíàòåëþ (2) èç (5). Íî ýòî ïðåäïîëàãàåòñÿ â ëó÷øåì
âàðèàíòå, à â îáùåì ñëó÷àå ÷èñëèòåëü äîëæåí ñòðåìèòüñÿ ê çíàìåíàòåëþ.
Ïîñêîëüêó çíàìåíàòåëü äëÿ êîíêðåòíîãî ìîìåíòà âðåìåíè — êîíñòàíòà, íåîáõî-
äèìî âûïîëíèòü òàêóþ âûáîðêó çàäàíèé
�
X èç î÷åðåäè, ÷òîáû ÷èñëèòåëü ïðèíÿë
ìàêñèìàëüíîå çíà÷åíèå, ïðè÷åì îíî íå äîëæíî ïðåâûñèòü çíàìåíàòåëü. Ýòî
132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
îçíà÷àåò, ÷òî íóæíî âûáðàòü èç î÷åðåäè êàê ìîæíî áîëüøåå êîëè÷åñòâî çàäàíèé,
êîòîðûå îáðàùàþòñÿ ê ðàçíûì ðåñóðñàì, è ÷òîáû ñóììà èõ ïðèîðèòåòîâ áûëà
ìàêñèìàëüíà. Ñòðåìëåíèå ê ìàêñèìóìó ñóììû ïðèîðèòåòîâ çàäàíèé ÿâëÿåòñÿ
ãëàâíûì êðèòåðèåì ïðè âûáîðå çàäàíèé èç î÷åðåäè.
ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÌÎÄÅËÜ ÏÐÎÖÅÄÓÐÛ ÏËÀÍÈÐÎÂÀÍÈß
ÍÀ ÎÑÍÎÂÅ ÌÅÒÎÄÀ ÃÐÓÏÏÎÂÎÉ ÂÛÁÎÐÊÈ
 ñîîòâåòñòâèè ñ (3) äëÿ îïèñàíèÿ ñóììû ïðèîðèòåòîâ � k âûáðàííûõ çàäàíèé xk
èñïîëüçóåì ôóíêöèîíàë (1)
F xk k
k
p
� �
�
� � max
1
. (6)
Ïóñòü Akg — áóëåâà ïåðåìåííàÿ, ðàâíàÿ 1, åñëè çàäàíèå Çk èñïîëüçóåò ðå-
ñóðñ Rg , è 0, åñëè íåò; Bg — êîëè÷åñòâî ðåñóðñîâ äàííîãî òèïà Rg . Òîãäà èñõî-
äÿ èç óñëîâèÿ, ÷òî â ëþáîé ìîìåíò âðåìåíè ëþáîé ðåñóðñ ìîæíî èñïîëüçîâàòü
äëÿ âûïîëíåíèÿ çàäàíèÿ, ïîëó÷àåì M îãðàíè÷åíèé âèäà
A x B g Mkg
k
p
k g
�
� � �
1
1, , . (7)
Ñëåäîâàòåëüíî, íåîáõîäèìî íàéòè òàêóþ âûáîðêó
�
X èç ìíîæåñòâà { }
�
X , äëÿ
êîòîðîé ôóíêöèîíàë (6) ïðèìåò ìàêñèìàëüíîå çíà÷åíèå ïðè âûïîëíåíèè âñåõ
îãðàíè÷åíèé (7). Ïîëó÷åíà çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ áóëåâûìè
ïåðåìåííûì.
Ðàçðåøåíèå î÷åðåäè çàïðîñîâ ïðè òàêîé ôîðìàëèçàöèè ïðîèñõîäèò ïîýòàï-
íî. Êàæäûé ýòàï ñîñòîèò èç îïðåäåëåíèÿ îïòèìàëüíîé âûáîðêè
�
X , åå îáñëóæè-
âàíèÿ è èçìåíåíèÿ ôóíêöèîíàëà (6) è îãðàíè÷åíèé (7) ñ ó÷åòîì èçìåíåíèé â î÷å-
ðåäè ïîñëå îáñëóæèâàíèÿ âûáîðêè.
Ðàññìîòðèì ìåòîä ãðóïïîâîé âûáîðêè íà ñëåäóþùåé çàäà÷å.
Èìååòñÿ î÷åðåäü èç ñåìè çàäàíèé, êàæäîå èç êîòîðûõ èìååò ñâîé ïðèîðèòåò
è òðåáóåò èñïîëüçîâàíèÿ ðåñóðñîâ îïðåäåëåííîãî òèïà (òàáë. 1). Ïî äàííûì
òàáë. 1 ñîñòàâèì òàáë. 2, â êîòîðîé äëÿ êàæäîãî ðåñóðñà îòìåòèì çàäàíèÿ, êîòî-
ðûå ê íåìó îáðàùàþòñÿ.
Ðàññìîòðèì ýòàïû ðåøåíèÿ äàííîé çàäà÷è.
Ýòàï 1. Çàïèøåì ôóíêöèîíàë (6), ïîäñòàâèâ çíà÷åíèÿ èç òàáë. 1:
F Ç Ç Ç Ç Ç Ç Ç� � � � � � � �1 2 3 4 5 6 73 2 2 4 max. (8)
Îãðàíè÷åíèÿ (7) ïðèìóò âèä
Ç Ç Ç1 � � �3 5 1, (9)
Ç Ç1 7 1� � , (10)
Ç Ç Ç3 4 7 1� � � . (11)
Îãðàíè÷åíèå (9) ñôîðìèðîâàíî äëÿ ðåñóðñà R1, (10) — äëÿ R3 , à (11) — äëÿ R4 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 133
Ò à á ë è ö à 1. Èñõîäíûå äàííûå
Çàäàíèÿ Ç1 Ç2 Ç3 Ç4 Ç5 Ç6 Ç7
Ïðèîðèòåòû 1 3 2 2 4 1 1
Ðåñóðñû R R1 3 R2 R R1 4 R4 R1 R5 R R3 4
Ò à á ë è ö à 2 . Îáðàòíûå èñõîäíûå äàííûå
Ðåñóðñû R1 R2 R3 R4 R5
Çàäàíèÿ Ç Ç Ç1 3 5 Ç2 Ç Ç1 7 Ç Ç Ç3 4 7 Ç6
Íà îñíîâàíèè ðåøåíèÿ çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ áóëåâûìè ïåðå-
ìåííûìè ïîëó÷àåì, ÷òî íà ýòàïå 1 íåîáõîäèìî îáñëóæèòü çàäàíèÿ Ç2 , Ç4 , Ç5 , Ç6 .
Ýòàï 2. Çàïèøåì ôóíêöèîíàë (6) ñ ó÷åòîì ðåçóëüòàòîâ ýòàïà 1:
F Ç Ç Ç� � � �1 3 7 max.
Îãðàíè÷åíèÿ (7) ïðèìóò âèä
Ç Ç1 � �3 1; Ç Ç1 7 1� � ; Ç Ç3 7 1� � .
Èç ðåçóëüòàòîâ ðåøåíèÿ çàäà÷è ñëåäóåò, ÷òî íåîáõîäèìî îáñëóæèòü çàäàíèå Ç3 .
Ýòàï 3. Àíàëîãè÷íî ïîëó÷àåì, ÷òî íà äàííîì ýòàïå íåîáõîäèìî îáñëóæèòü
çàäàíèå Ç1.
Ýòàï 4. Íà ýòîì ýòàïå íåîáõîäèìî îáñëóæèòü çàäàíèå Ç7 .
Òàêèì îáðàçîì, ðàññìîòðåííàÿ çàäà÷à ìåòîäîì ãðóïïîâîé âûáîðêè ðåøàåòñÿ
çà ÷åòûðå ýòàïà.
ÏÐÎÖÅÄÓÐÀ ÏËÀÍÈÐÎÂÀÍÈß ÏÀÊÅÒÎÂ ÇÀÄÀÍÈÉ Â ÃÐÈÄ-ÑÈÑÒÅÌÅ ÍÀ ÎÑÍÎÂÅ
ÌÅÒÎÄÀ ÃÐÓÏÏÎÂÎÉ ÂÛÁÎÐÊÈ Ñ ÈÍÄÈÂÈÄÓÀËÜÍÎÉ ÑÅÃÌÅÍÒÀÖÈÅÉ
Ïðè ðåàëèçàöèè äàííîãî ìåòîäà çàäàíèÿ, íàõîäÿùèåñÿ â î÷åðåäè, ðàçáèâàþòñÿ
íà ïîäçàäà÷è. Èç î÷åðåäè âûáèðàþòñÿ ïîäçàäà÷è, òðåáóþùèå äëÿ ðåàëèçàöèè
ðåñóðñû ðàçëè÷íûõ òèïîâ, ñ ìàêñèìàëüíîé ñóììîé èõ ïðèîðèòåòîâ.  ñëó÷àå
íàëè÷èÿ ðàâíîçíà÷íûõ ïîäçàïðîñîâ âûáèðàþò áîëåå «ñòàðûå».
Ïîäçàäà÷à — ÷àñòü çàäàíèÿ, òðåáóþùàÿ äëÿ ðåàëèçàöèè èñïîëüçîâàíèÿ ðå-
ñóðñà êîíêðåòíîãî òèïà. Åñëè çàäàíèå òðåáóåò K ðàçëè÷íûõ ðåñóðñîâ, òî îíî ðàç-
áèâàåòñÿ íà K ïîäçàäà÷.  òàêîì âàðèàíòå íóæíî âûáðàòü èç î÷åðåäè êàê ìîæíî
áîëüøåå êîëè÷åñòâî ïîäçàäà÷, îáðàùàþùèõñÿ ê ðàçíûì ðåñóðñàì, è ñóììà ïðè-
îðèòåòîâ ýòèõ ïîäçàäà÷ äîëæíà áûòü ìàêñèìàëüíîé. Ñòðåìëåíèå ê ìàêñèìóìó
ñóììû ïðèîðèòåòîâ ïîäçàäà÷ ÿâëÿåòñÿ ãëàâíûì êðèòåðèåì ïðè âûáîðå ïîäçàäà÷
èç î÷åðåäè.
Ïóñòü Çkg — ïîäçàäà÷à çàäàíèÿ Çk , îáðàùàþùåãîñÿ ê ðåñóðñó Rg ; Ckg —
ïðèîðèòåò ïîäçàäà÷è Çkg ; { }
�
X — ìíîæåñòâî âñåõ âàðèàíòîâ âûáîðà ïîäçàäà÷
èç î÷åðåäè,
�
X — îäèí èç âàðèàíòîâ âûáîðà ïîäçàäà÷. Ïðè÷åì
�
�X x x� { 11 12, ,
� �, , ,x xkg s}, ãäå k p�1, , g M�1, , p — êîëè÷åñòâî çàäàíèé â î÷åðåäè, M —
êîëè÷åñòâî ðåñóðñîâ, xkg — áóëåâà ïåðåìåííàÿ, ðàâíàÿ 1, åñëè ñîîòâåòñòâóþùàÿ
ïîäçàäà÷à Çkg âûáðàíà â äàííîì âàðèàíòå, è 0, åñëè íåò. Òîãäà ôóíêöèîíàë (6)
ïðèìåò âèä
F x C S C C S C
j
p
j n
j
p
j n( ) ( ) ( )� � �
� �
� �
1
1 1
1
1
2 2
2
1 2
�
� �� � � �
� �
� �C S C C S Ckj k n
k
j
p
nj n n
n
j
pk n
( ) ( )
1 1
max, (12)
ãäå Sr C S S Sn
r
pr
( ) � � � �1 2 � — ñóììà âñåõ âîçìîæíûõ ñî÷åòàíèé ïðîèçâåäå-
íèé ïåðåìåííûõ, ñîäåðæàùèõ r ðàçëè÷íûõ ïåðåìåííûõ â êàæäîì ïðîèçâåäå-
íèè Sr X X Xp k m� � ; p
n
r n r
r �
�
!
! ( )!
; Crj — êîýôôèöèåíòû â ïðîèçâåäåíèÿõ Sr,
ñîäåðæàùèõ r ïåðåìåííûõ.
Îãðàíè÷åíèÿ (7) ïðèìóò âèä
A x B g Mkg
k
p
kg g
�
� � �
1
1, , . (13)
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
Ïîëó÷èëè çàäà÷ó íåëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ áóëåâûìè ïåðåìåííûìè.
Äëÿ ðàññìîòðåííîãî ðàíåå ïðèìåðà ôóíêöèîíàë (12) ïðèìåò âèä
F Ç Ç Ç Ç Ç Ç Ç Ç� � � � � � � � �11 13 2 31 34 4 5 63 2 2 2 4
� � � � � �Ç Ç Ç Ç Ç Ç Ç Ç73 74 11 13 31 34 73 742 max,
à îãðàíè÷åíèÿ (7) ïðèìóò âèä
Ç Ç Ç11 � � �31 5 1; Ç Ç13 73 1� � ; Ç Ç Ç34 4 74 1� � � .
Ïðè ìåòîäå ãðóïïîâîé âûáîðêè ñ èíäèâèäóàëüíîé ñåãìåíòàöèåé ñôîðìèðî-
âàííàÿ î÷åðåäü ðàçðåøèòñÿ çà òðè ýòàïà.
Èñõîäÿ èç ðàññìîòðåííîãî ïðèìåðà, îòìåòèì: èñïîëüçîâàíèå ìåòîäà ãðóïïîâîé
âûáîðêè ñ èíäèâèäóàëüíîé ñåãìåíòàöèåé ïîçâîëÿåò ñîêðàòèòü êîëè÷åñòâî ýòàïîâ, çà
êîòîðûå ðàçðåøàåòñÿ î÷åðåäü, ÷òî ñîêðàùàåò ÷àñòîòó îòêàçîâ â îáñëóæèâàíèè çàäà-
íèé íà âõîäå ñèñòåìû ïðè ïèêîâîé íàãðóçêå; â öåëÿõ îáåñïå÷åíèÿ ýôôåêòèâíîé ðàáî-
òû óêàçàííûõ ìåòîäîâ íåîáõîäèìî â êà÷åñòâå ìàòåìàòè÷åñêîãî àïïàðàòà ïðèìåíÿòü
ìåòîäû ñ ìàëîé âðåìåíí�é ñëîæíîñòüþ äëÿ ðåøåíèÿ çàäà÷ ëèíåéíîãî è íåëèíåéíîãî
ïðîãðàììèðîâàíèÿ ñ áóëåâûìè ïåðåìåííûìè.
Ïðåäëàãàåòñÿ èñïîëüçîâàòü â êà÷åñòâå ìåòîäà ïëàíèðîâàíèÿ ðàíãîâûé àëãîðèòì
ðåøåíèÿ çàäà÷ íåëèíåéíîãî áóëåâîãî ïðîãðàììèðîâàíèÿ, ïðèâåäåííûé â [5].
ÐÀÇÐÀÁÎÒÊÀ ÈÌÈÒÀÖÈÎÍÍÎÉ ÌÎÄÅËÈ ÊËÀÑÒÅÐÀ ÃÐÈÄ-ÑÈÑÒÅÌÛ
Äëÿ ìîäåëèðîâàíèÿ ôóíêöèîíèðîâàíèÿ êëàñòåðà ãðèä-ñèñòåìû, ñòðóêòóðíàÿ ñõåìà
êîòîðîãî ïðåäñòàâëåíà íà ðèñ. 1, ôîðìèðóåòñÿ ìíîæåñòâî çàäà÷, êîòîðûå ïîäàþò-
ñÿ â ñèñòåìó â ïðîöåññå ìîäåëèðîâàíèÿ ðàáîòû. Óñòàíàâëèâàþòñÿ ïàðàìåòðû ñèñ-
òåìû (äëèíà ïóëà âõîäíûõ çàäà÷, ÷àñòîòà ïëàíèðîâàíèÿ, âðåìÿ çàäåðæêè è äðó-
ãèå) è çàäàåòñÿ ìåòîä ïëàíèðîâàíèÿ (ïðåäóñìîòðåíî íåñêîëüêî àëãîðèòìîâ ðåøå-
íèÿ ÇÍÏ, îáîçíà÷åííûõ ÌÑ, FCFS, è ìåòîä, îñíîâàííûé íà ðåøåíèè çàäà÷è
íåëèíåéíîãî áóëåâîãî ïðîãðàììèðîâàíèÿ, îáîçíà÷åííûé NLP).
Ïðîöåññ ìîäåëèðîâàíèÿ ðàáîòû êëàñòåðà ñîñòîèò èç ïîøàãîâîãî âûïîëíå-
íèÿ òðåõ îïåðàöèé: 1) èìèòàöèÿ ïîñòóïëåíèÿ çàäà÷ íà âõîä ñèñòåìû; èç îáùåãî
êîëè÷åñòâà çàäà÷ â ïóë çàãðóæàþòñÿ ïåðâûå mp çàäà÷; 2) ðàñïðåäåëåíèå çàäà÷ èç
î÷åðåäè ïóëà ìåæäó ðåñóðñàìè è âîçâðàò â ïóë íå ïîìåñòèâøèõñÿ çàäà÷; 3) èìè-
òàöèÿ ðåøåíèÿ çàäà÷ ñ èñïîëüçîâàíèåì ðåñóðñîâ; èìèòàöèÿ ðåøåíèÿ çàäà÷è çà-
êëþ÷àåòñÿ â âû÷èòàíèè îò çíà÷åíèÿ ñëîæíîñòè ðåøåíèÿ çàäà÷è çíà÷åíèÿ ïðîèç-
âîäèòåëüíîñòè ðåñóðñà, íà êîòîðîì ðåøàåòñÿ çàäà÷à (äàííàÿ îïåðàöèÿ ïðèíÿòà çà
óñëîâíóþ åäèíèöó âðåìåíè — òàêò; âñå âðåìåíí�å ïðîöåññû â ìîäåëèðîâàíèè
ðàáîòû êëàñòåðà èçìåðÿþòñÿ â ýòèõ åäèíèöàõ).
Ìîäåëèðîâàíèå ðàáîòû êëàñòåðà îñóùåñòâëÿåòñÿ ïîøàãîâî: 1) îïåðà-
öèÿ ¹ 1 — íà âõîä ñèñòåìû ïîäàåòñÿ çàäàííîå êîëè÷åñòâî çàäà÷; 2) îïåðà-
öèÿ ¹ 2 — ôîðìèðóåòñÿ ïàêåò çàäàíèé âûáðàííûì ìåòîäîì; 3) îïåðàöèÿ ¹ 3 —
èìèòèðóåòñÿ ïðîöåññ ðåøåíèÿ äëÿ âñåõ çàäà÷, íàõîäÿùèõñÿ íà òåêóùèé ìîìåíò
â ðåñóðñå; âûïîëíÿåòñÿ òàêîå êîëè÷åñòâî òàêòîâ, êîòîðîå áûëî ïîòðà÷åíî íà
ôîðìèðîâàíèå ïàêåòà çàäàíèé; 4) îïåðàöèÿ ¹ 3 — èìèòèðóåòñÿ ïðîöåññ ðåøå-
íèÿ çàäà÷ äî ìîìåíòà íàñòóïëåíèÿ ñëåäóþùåãî ïåðèîäà ïëàíèðîâàíèÿ èëè ïîêà
íå áóäóò ðåøåíû âñå çàäà÷è; 5) ïåðåõîä ê âûïîëíåíèþ øàãà 1.
Ýëåìåíòû ìîäåëè. Ìîäåëü âêëþ÷àåò ñëåäóþùèå ýëåìåíòû: ìíîæåñòâî çà-
äà÷ — íàáîð çàäà÷, êîòîðûå ïîäàþòñÿ â ãðèä-ñèñòåìó äëÿ ìîäåëèðîâàíèÿ ïðî-
öåññà åå ðàáîòû; ìíîæåñòâî ðåñóðñîâ — íàáîð ðåñóðñîâ, âûïîëíÿþùèõ ðåøåíèå
ìíîæåñòâà çàäà÷, ïîäàííûõ â ãðèä-ñèñòåìó; ïàðàìåòðû ìîäåëèðîâàíèÿ — íàáîð
ïàðàìåòðîâ, îïðåäåëÿþùèõ ðåæèì ðàáîòû è õàðàêòåðèñòèêè ìîäåëè ãðèä-ñèñòå-
ìû; ìåòîäû ïëàíèðîâàíèÿ — íàáîð ìåòîäîâ, ñ ïîìîùüþ êîòîðûõ ãðèä-ñèñòåìà
ðàñïðåäåëÿåò âõîäÿùèå âûçîâû ìåæäó ðåñóðñàìè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 135
Ïîä òåðìèíîì çàäà÷à ïîäðàçóìåâàåòñÿ ñòðóêòóðà ñ íàáîðîì ñëåäóþùèõ õà-
ðàêòåðèñòèê: óíèâåðñàëüíîñòü; òèïû ðåñóðñîâ, çàäåéñòâîâàííûõ äëÿ ðåøåíèÿ
çàäà÷è; ñëîæíîñòü ðåøåíèÿ; ïðèîðèòåò. Äàííûå õàðàêòåðèñòèêè çàäà÷ îïðåäåëÿ-
þòñÿ ïàðàìåòðàìè ìíîæåñòâà. Â ìîäåëè äëÿ ïðîöåññà ðàáîòû ãðèä-ñèñòåìû íå-
îáõîäèìî óñòàíîâèòü ñëåäóþùèå ïàðàìåòðû ìíîæåñòâà çàäà÷: êîëè÷åñòâî çà-
äà÷ — îáùåå êîëè÷åñòâî çàäà÷ â ìíîæåñòâå; êîëè÷åñòâî òèïîâ ðåñóðñîâ — ìàê-
ñèìàëüíîå ÷èñëî òèïîâ ðåñóðñîâ, êîòîðûå ìîæíî èñïîëüçîâàòü äëÿ ðåøåíèÿ
çàäà÷è. Äëÿ ñîâìåñòèìîñòè ïàðàìåòðîâ êîëè÷åñòâî òèïîâ ðåñóðñîâ â ìíîæåñòâå
çàäà÷ äîëæíî ñîâïàäàòü ñ àíàëîãè÷íûì ïàðàìåòðîì â ìíîæåñòâå ðåñóðñîâ, íà êî-
òîðûõ ïëàíèðóåòñÿ ðåøàòü äàííîå ìíîæåñòâî çàäà÷.
Óíèâåðñàëüíîñòü — ìàêñèìàëüíîå çíà÷åíèå óíèâåðñàëüíîñòè çàäà÷ âî âñåì
ìíîæåñòâå (îïðåäåëÿåò êîëè÷åñòâî òèïîâ ðåñóðñîâ, íà êîòîðûõ ìîæíî ðåøèòü çàäà-
÷ó). Çàêîí ðàñïðåäåëåíèÿ óíèâåðñàëüíîñòè — ñëó÷àéíûé çàêîí, ïî êîòîðîìó çàäà-
÷àì íàçíà÷àåòñÿ óíèâåðñàëüíîñòü. Ìàêñèìàëüíî âîçìîæíîå çíà÷åíèå îïðåäåëÿåòñÿ
ïàðàìåòðîì «óíèâåðñàëüíîñòü», ìèíèìàëüíîå çíà÷åíèå ñîîòâåòñòâóåò åäèíèöå.
Êîëè÷åñòâî óíèêàëüíûõ çàäà÷ — ïðîöåíò çàäà÷, êîòîðûå ìîãóò ðåøàòüñÿ
òîëüêî îäíèì ðåñóðñîì (ïðîöåíòíîå îòíîøåíèå ê îáùåìó êîëè÷åñòâó çàäà÷;
ïðèíèìàåò çíà÷åíèÿ îò 0 äî 100 %). Ñëîæíîñòü ðåøåíèÿ — ìàêñèìàëüíîå çíà÷å-
íèå ñëîæíîñòè ðåøåíèÿ çàäà÷ âî âñåì ìíîæåñòâå (îïðåäåëÿåò êîëè÷åñòâî òàêòîâ,
ïîòðà÷åííûõ íà ðåøåíèå çàäà÷è ðåñóðñîì ñ ïðîèçâîäèòåëüíîñòüþ 1 òàêò). Çàêîí
ðàñïðåäåëåíèÿ ñëîæíîñòè ðåøåíèÿ — ñëó÷àéíûé çàêîí, ïî êîòîðîìó çàäà÷àì íà-
çíà÷àåòñÿ ñëîæíîñòü ðåøåíèÿ. Ìàêñèìàëüíî âîçìîæíîå çíà÷åíèå ñëîæíîñòè
îïðåäåëÿåòñÿ ïàðàìåòðîì «ñëîæíîñòü ðåøåíèÿ», ìèíèìàëüíîå çíà÷åíèå ñîîòâåò-
ñòâóåò îäíîìó òàêòó. Ñóììàðíàÿ ñëîæíîñòü ðåøåíèÿ — ñóììà ñëîæíîñòåé ðåøå-
íèÿ âñåõ çàäà÷ ìíîæåñòâà. Äàííûé ïàðàìåòð íå çàäàåòñÿ ïîëüçîâàòåëåì, à ïîä-
ñ÷èòûâàåòñÿ ïðè ôîðìèðîâàíèè ìíîæåñòâà çàäà÷.
Ïðèîðèòåò — ìàêñèìàëüíîå çíà÷åíèå ïðèîðèòåòà çàäà÷ âî âñåì ìíîæåñòâå
(îïðåäåëÿåò âàæíîñòü ðåøåíèÿ çàäà÷è â óñëîâíûõ åäèíèöàõ). Çàêîí ðàñïðåäåëåíèÿ
ïðèîðèòåòà — ñëó÷àéíûé çàêîí, ïî êîòîðîìó çàäà÷àì íàçíà÷àåòñÿ ïðèîðèòåò.  ìî-
äåëè ïðåäóñìîòðåíà âîçìîæíîñòü èçìåíåíèÿ âñåõ ïàðàìåòðîâ ïî ðàçëè÷íûì ñëó÷àé-
íûì çàêîíàì: ðàâíîìåðíîìó, íîðìàëüíîìó, Ýðëàíãà, ýêñïîíåíöèàëüíîìó.
 ìîäåëè âîçìîæíî ðàçáèåíèå èñõîäíûõ çàäà÷ íà ïîäçàäà÷è, ïðè ýòîì ñóììàð-
íàÿ ñëîæíîñòü ðåøåíèÿ çàäà÷ îñòàåòñÿ ïðåæíåé, óâåëè÷èâàåòñÿ òîëüêî èõ êîëè÷åñ-
òâî. Ðåñóðñ ïðåäñòàâëÿåò ñòðóêòóðó ñ íàáîðîì òàêèõ õàðàêòåðèñòèê: òèï; ïðîèçâîäè-
òåëüíîñòü. Â ìîäåëè âîçìîæíî çàäàâàòü ñëåäóþùèå ïàðàìåòðû äëÿ ìíîæåñòâà ðå-
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
Âðåìÿ âûïîëíåíèÿ
Âðåìÿ îòâåòà
Âðåìÿ îæèäàíèÿ Âðåìÿ îáñëóæèâàíèÿ Âðåìÿ ðåøåíèÿ
Òàêò ðàáîòû
Îïåðàöèÿ ¹ 1
m — êîëè÷åñòâî âõîäíûõ çàäà÷
mp — äëèíà ïóëà (î÷åðåäè) çàäà÷
k — äëèíà áóôåðà ðåñóðñîâ
n — êîëè÷åñòâî ðåñóðñîâ
Ìíîæåñòâî
çàäà÷
1 2 …
… mm�1
Ïóë çàäà÷
(ïîìåùåíèå çàäà÷ â ïóë,
âõîä ñèñòåìû)
1 2 … mp�1 mp
Îïåðàöèÿ ¹ 2
(ðàñïðåäåëåíèå çàäà÷ ìåæäó
ðåñóðñàìè è âîçâðàò íå ïîìåñòèâ-
øèõñÿ â î÷åðåäü çàäà÷)
Îïåðàöèÿ ¹ 3
(èìèòàöèÿ
ïðîöåññà
ðåøåíèÿ çàäà÷)
Äëèíà áóôåðà
Âðåìÿ ôîðìèðîâàíèÿ
ïàêåòà çàäàíèé
Ìåòîäû ôîðìèðîâàíèÿ
ïàêåòîâ çàäàíèé
MC1
MC2
MC3
FCFS
k k�1 2… 1 1
k k�1 2… 1
k k�1 2… 1
2
… …
k k�1 2… 1
n�1
n
Ðåñóðñû
Ðèñ. 1. Ñòðóêòóðíàÿ ñõåìà ìîäåëè êëàñòåðà ãðèä-ñèñòåìû
ñóðñîâ: êîëè÷åñòâî ðåñóðñîâ — îáùåå êîëè÷åñòâî ðåñóðñîâ â ìíîæåñòâå;
êîëè÷åñòâî òèïîâ ðåñóðñîâ — ìàêñèìàëüíîå ÷èñëî òèïîâ ðåñóðñîâ. Ïðîèçâîäèòåëü-
íîñòü ðåñóðñà îïðåäåëÿåòñÿ êîëè÷åñòâîì òàêòîâ ñëîæíîñòè ðåøåíèÿ çàäà÷è, êîòîðîå
áóäåò âûïîëíåíî ðåñóðñîì çà 1 òàêò. Èìååòñÿ òàêæå âîçìîæíîñòü çàäàâàòü çàêîí
ðàñïðåäåëåíèÿ ïðîèçâîäèòåëüíîñòè, ïî êîòîðîìó ðåñóðñàì íàçíà÷àåòñÿ ïðîèçâîäè-
òåëüíîñòü. Êðîìå òîãî, â ìîäåëè àâòîìàòè÷åñêè ðàññ÷èòûâàåòñÿ ñóììàðíàÿ ïðîèçâî-
äèòåëüíîñòü (îáùàÿ ïðîèçâîäèòåëüíîñòü âñåõ ðåñóðñîâ ìíîæåñòâà).
Ðàçìåð áóôåðîâ âñåõ ðåñóðñîâ ìíîæåñòâà îïðåäåëÿåò êîëè÷åñòâî çàäà÷, êîòî-
ðûå ìîãóò áûòü ïîñòàâëåíû â î÷åðåäü íà ðåøåíèå ê ðåñóðñó.  ìîäåëè ïðåäóñìîò-
ðåíî äâà òèïà áóôåðà: ïîñëåäîâàòåëüíûé — çàäà÷è ïîñëåäîâàòåëüíî, ïî îäíîé, ðå-
øàþòñÿ ðåñóðñîì; ïàðàëëåëüíûé — âñå çàäà÷è â áóôåðå ðåøàþòñÿ ðåñóðñîì îäíî-
âðåìåííî. Ñôîðìèðîâàí íàáîð ïàðàìåòðîâ, îïðåäåëÿþùèõ ðåæèì ðàáîòû
è õàðàêòåðèñòèêè ìîäåëè ãðèä-ñèñòåìû. Â ìîäåëè çàäàþòñÿ ñëåäóþùèå ïàðàìåò-
ðû: çàäà÷è — ìíîæåñòâî çàäà÷, êîòîðîå ïîäàåòñÿ â ñèñòåìó â ïðîöåññå ìîäåëèðî-
âàíèÿ; ðåñóðñû — ìíîæåñòâî ðåñóðñîâ ñèñòåìû, íà êîòîðûõ ðåøàþòñÿ çàäà÷è ïðè
ìîäåëèðîâàíèè; èíòåíñèâíîñòü — ìàêñèìàëüíîå êîëè÷åñòâî çàäà÷, ïîñòóïàþùèõ
íà âõîä ñèñòåìû ïðè î÷åðåäíîì òàêòå ïëàíèðîâàíèÿ. Çàêîí ðàñïðåäåëåíèÿ èíòåí-
ñèâíîñòè — ñëó÷àéíûé çàêîí, ïî êîòîðîìó çàäà÷è ðàñïðåäåëÿþòñÿ äëÿ ïîñëåäîâà-
òåëüíîãî ïîñòóïëåíèÿ íà âõîä ñèñòåìû.
Ìàêñèìàëüíî âîçìîæíîå çíà÷åíèå èíòåíñèâíîñòè îïðåäåëÿåòñÿ ïàðàìåòðîì
«èíòåíñèâíîñòü», ìèíèìàëüíîå çíà÷åíèå — íîëü; îò÷óæäåííîñòü — ìàêñèìàëü-
íîå êîëè÷åñòâî âûøåäøèõ èç ñòðîÿ ðåñóðñîâ íà î÷åðåäíîì òàêòå ïëàíèðîâàíèÿ
(çàäàåòñÿ îò 0 äî 100 % îòíîñèòåëüíî êîëè÷åñòâà ðåñóðñîâ). Çàêîí ðàñïðåäåëåíèÿ
îò÷óæäåííîñòè — ñëó÷àéíûé çàêîí, ïî êîòîðîìó ðàñïðåäåëÿåòñÿ îò÷óæäåííîñòü
äëÿ êàæäîãî òàêòà ïëàíèðîâàíèÿ. Ìàêñèìàëüíîå çíà÷åíèå îò÷óæäåííîñòè îïðå-
äåëÿåòñÿ ïàðàìåòðîì «îò÷óæäåííîñòü», ìèíèìàëüíîå çíà÷åíèå — íîëü; äëèíà
ïóëà — ìàêñèìàëüíîå êîëè÷åñòâî çàäà÷, êîòîðûå ìîæåò ïîìåñòèòü ñèñòåìà äëÿ
äàëüíåéøåé îáðàáîòêè; çàäåðæêà — êîëè÷åñòâî òàêòîâ, çàòðà÷èâàåìûõ ñèñòåìîé
íà ïåðåäà÷ó çàäà÷è èç áóôåðà â ðåñóðñ íà ðåøåíèå; ÷àñòîòà ïëàíèðîâàíèÿ — êî-
ëè÷åñòâî òàêòîâ ìåæäó ïëàíèðîâàíèÿìè, à òàêæå ìåæäó ïîñòóïëåíèÿìè íîâûõ
çàäà÷ íà âõîä ñèñòåìû; êîýôôèöèåíò ïëàíèðîâàíèÿ — êîýôôèöèåíò, íà êîòîðûé
óìåíüøàåòñÿ êîëè÷åñòâî îïåðàöèé, âûïîëíåííûõ ïëàíèðîâùèêîì äëÿ ïåðåâîäà
îïåðàöèé, èñïîëüçîâàííûõ íà ïëàíèðîâàíèå â çàòðà÷åííîå âðåìÿ, êîòîðîå â ñèñ-
òåìå âûðàæàåòñÿ â óñëîâíûõ åäèíèöàõ — òàêòàõ.
Ðàññìîòðèì íàáîð ìåòîäîâ, ñ ïîìîùüþ êîòîðûõ ãðèä-ñèñòåìà ðàñïðåäåëÿåò
âõîäÿùèå çàäà÷è ìåæäó ðåñóðñàìè.  äàííîé ìîäåëè ñóùåñòâóåò âîçìîæíîñòü
ïðîâîäèòü èññëåäîâàíèÿ ñ ïðèìåíåíèåì ñëåäóþùèõ ìåòîäîâ ïëàíèðîâàíèÿ âû-
ïîëíåíèÿ çàäàíèé.
Ìåòîä ïëàíèðîâàíèÿ ÌÑ. Ìåòîä îñíîâàí íà ïîèñêå íàèìåíüøåãî ÷èñëà ðå-
ñóðñîâ, êîòîðûìè ìîæíî ðåøèòü âñå çàäà÷è, ò.å. ÇÍÏ. Äëÿ ïîèñêà íàèìåíüøåãî
÷èñëà ðåñóðñîâ èñïîëüçóåòñÿ ïðèáëèæåííûé ÷àñòîòíûé ìåòîä [1, 5].
Àëãîðèòì ðàáîòû ÌÑ: 1) îïðåäåëÿþòñÿ ñîîòâåòñòâèÿ ìåæäó çàäà÷àìè è ðå-
ñóðñàìè, êîòîðûå îíè èñïîëüçóþò; 2) ðåøàåòñÿ çàäà÷à ïîèñêà ìèíèìàëüíîãî ïî-
êðûòèÿ ÷àñòîòíûì ìåòîäîì; 3) çàäà÷è ïîìåùàþòñÿ â áóôåðû ðåñóðñîâ, âîøåä-
øèõ â ìèíèìàëüíîå ïîêðûòèå; 4) ïðîöåäóðà ïëàíèðîâàíèÿ çàêàí÷èâàåòñÿ, åñëè
ïîìåñòèëèñü âñå çàäà÷è, èíà÷å çàäà÷è âîçâðàùàþòñÿ â ïóë è âûïîëíÿåòñÿ ïåðå-
õîä ê «îïåðàöèè ¹ 2».
 ïðîöåññå ïëàíèðîâàíèÿ çàäà÷è, äëÿ ðåøåíèÿ êîòîðûõ íå îñòàëîñü ñâîáîä-
íûõ ðåñóðñîâ, âîçâðàùàþòñÿ îáðàòíî â ïóë.
Ìåòîä ïëàíèðîâàíèÿ FCFS. Ìåòîä îñíîâàí íà ïðèíöèïå «ïåðâûì ïðèøåë,
ïåðâûì îáñëóæèëñÿ».
Àëãîðèòì ðàáîòû FCFS: 1) îïðåäåëÿþòñÿ ñîîòâåòñòâèÿ ìåæäó çàäà÷àìè
è ðåñóðñàìè, íà êîòîðûõ îíè ìîãóò ðåøàòüñÿ; 2) âûáèðàåòñÿ ïåðâàÿ ïî ïîðÿäêó
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 137
çàäà÷à èç ïóëà è ïîìåùàåòñÿ â ïåðâûé ñâîáîäíûé ðåñóðñ, íà êîòîðîì îíà ìîæåò
áûòü ðåøåíà; åñëè òàêèõ ðåñóðñîâ íå îêàçàëîñü, çàäà÷à âîçâðàùàåòñÿ â ïóë;
3) ïðîöåäóðà ïëàíèðîâàíèÿ ïðåêðàùàåòñÿ ïîñëå îáðàáîòêè â ïóëå ïîñëåäíåé çà-
äà÷è.  äàííîì ìåòîäå íå èñïîëüçóåòñÿ áóôåð, çàäà÷è ñðàçó ïîñûëàþòñÿ íà ðå-
øåíèå ðåñóðñó, åñëè îí ñâîáîäåí.
Ìåòîä ïëàíèðîâàíèÿ NLP. Ìåòîä îñíîâàí íà ïîèñêå ðåøåíèÿ çàäà÷è íåëè-
íåéíîãî ïðîãðàììèðîâàíèÿ: àëãîðèòì íàõîäèò ìàêñèìàëüíîå êîëè÷åñòâî çàäà÷
ñ ñóììàðíûì ìàêñèìàëüíûì ïðèîðèòåòîì, êîòîðûå ìîãóò áûòü ïîìåùåíû â áó-
ôåð ñâîáîäíûõ ðåñóðñîâ.
Àëãîðèòì ðàáîòû NLP: 1) îïðåäåëÿþòñÿ ñîîòâåòñòâèÿ ìåæäó çàäà÷àìè è ðå-
ñóðñàìè, íà êîòîðûõ îíè ìîãóò ðåøàòüñÿ; 2) ðåøàåòñÿ çàäà÷à íåëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ; 3) çàäà÷è ïîìåùàþòñÿ â áóôåðû ðåñóðñîâ; åñëè îñòàëèñü çàäà÷è,
äëÿ êîòîðûõ åñòü ñâîáîäíûå ðåñóðñû, âûïîëíÿåòñÿ ïåðåõîä ê «îïåðàöèè ¹ 2»;
åñëè òàêèõ çàäà÷ íåò, ïðîöåäóðà ïëàíèðîâàíèÿ çàêàí÷èâàåòñÿ.  ïðîöåññå ïëàíè-
ðîâàíèÿ çàäà÷è, íå èìåþùèå ñâîáîäíûõ ðåñóðñîâ, êîòîðûå ìîãóò èõ ðåøèòü,
âîçâðàùàþòñÿ â ïóë.
Èññëåäóåìûå õàðàêòåðèñòèêè ðàáîòû ãðèä-ñèñòåìû. Â ïðåäñòàâëåííîé ìî-
äåëè â ïðîöåññå ðàáîòû ãðèä-ñèñòåìû ðàññìàòðèâàþòñÿ ñëåäóþùèå õàðàêòåðèñòèêè.
� Âðåìÿ âûïîëíåíèÿ — êîëè÷åñòâî òàêòîâ ðàáîòû ñèñòåìû, çà êîòîðîå ðå-
øåíî âñå ìíîæåñòâî çàäà÷, ïîäàííûõ íà âõîä ãðèä-ñèñòåìû.
� Âðåìÿ îòâåòà — ñðåäíåå êîëè÷åñòâî òàêòîâ çà êîòîðîå ðåøåíà îäíà çàäà÷à
â ðåæèìå ìîäåëèðîâàíèÿ ãðèä-ñèñòåìû.
� Ìàêñèìàëüíîå âðåìÿ îòâåòà — ìàêñèìàëüíîå êîëè÷åñòâî òàêòîâ, çà êîòî-
ðîå ðåøåíà îäíà çàäà÷à.
� Âðåìÿ îæèäàíèÿ — ñðåäíåå êîëè÷åñòâî òàêòîâ, êîòîðîå îæèäàëè çàäà÷è íà
âõîäå ñèñòåìû äî ïîñëåäóþùåé îáðàáîòêè.
� Âðåìÿ îáñëóæèâàíèÿ — ñðåäíåå êîëè÷åñòâî òàêòîâ, êîòîðîå çàäà÷è íàõî-
äèëèñü â áóôåðå íàçíà÷åííîãî ðåñóðñà äî íà÷àëà èõ ðåøåíèÿ äàííûì ðåñóðñîì.
� Âðåìÿ ïëàíèðîâàíèÿ — ñðåäíåå êîëè÷åñòâî òàêòîâ, êîòîðîå çàòðà÷åíî ñèñ-
òåìîé íà ïëàíèðîâàíèå.
� Êîýôôèöèåíò èñïîëüçîâàíèÿ — ñðåäíåå ãåîìåòðè÷åñêîå çíà÷åíèå êîýôôè-
öèåíòîâ èñïîëüçîâàíèÿ âñåõ ðåñóðñîâ (êîýôôèöèåíò èñïîëüçîâàíèÿ ðåñóðñà —
îòíîøåíèå ñóììû ïðèîðèòåòîâ âñåõ ðåøåííûõ çàäà÷ ýòèì ðåñóðñîì ê ñóììå
ïðèîðèòåòîâ âñåõ çàäà÷ èç âõîäíîãî ìíîæåñòâà, êîòîðûå ìîãëè áûòü ðåøåíû íà
äàííîì ðåñóðñå).
� Êîýôôèöèåíò çàãðóçêè — ñðåäíåå ãåîìåòðè÷åñêîå çíà÷åíèå êîýôôèöèåí-
òîâ çàãðóçêè âñåõ ðåñóðñîâ. Êîýôôèöèåíò ïðîèçâîäèòåëüíîñòè ðåñóðñà — îòíî-
øåíèå êîëè÷åñòâà ðåøåííûõ çàäà÷ ýòèì ðåñóðñîì ê êîëè÷åñòâó âñåõ çàäà÷ èç
âõîäíîãî ìíîæåñòâà, êîòîðûå ìîãëè áûòü ðåøåíû íà äàííîì ðåñóðñå.
� Êîýôôèöèåíò âàæíîñòè — ñðåäíåå ãåîìåòðè÷åñêîå îòíîøåíèÿ ñóììàðíî-
ãî ïðèîðèòåòà çàäà÷, ïîìåùåííûõ â áóôåðû â ðåçóëüòàòå ïëàíèðîâàíèÿ, ê ñóì-
ìàðíîìó ïðèîðèòåòó çàäà÷, íàõîäèâøèõñÿ â ïóëå.
� Êîýôôèöèåíò ñîõðàíåíèÿ âàæíîñòè — ñðåäíåå ãåîìåòðè÷åñêîå îòíîøåíèÿ
ñóììàðíîãî ïðèîðèòåòà çàäà÷, ïîìåùåííûõ â áóôåðû â ðåçóëüòàòå ïëàíèðîâàíèÿ
ïîñëå îòêàçà ñëó÷àéíîãî êîëè÷åñòâà ðåñóðñîâ, ê ñóììàðíîìó ïðèîðèòåòó çàäà÷,
ïîìåùåííûõ â áóôåðû â ðåçóëüòàòå ïëàíèðîâàíèÿ äî îòêàçà ðåñóðñîâ.
� Êîýôôèöèåíò óñêîðåíèÿ — îòíîøåíèå ðàñ÷åòíîãî âðåìåíè âûïîëíåíèÿ
çàäà÷, ðåøàåìûõ ïîñëåäîâàòåëüíî îäíèì ðåñóðñîì ñ ïðîèçâîäèòåëüíîñòüþ, ðàâ-
íîé ñðåäíåé ïðîèçâîäèòåëüíîñòè âñåõ ðåñóðñîâ ãðèä, êî âðåìåíè âûïîëíåíèÿ
ýòèõ çàäà÷ ãðèä-ñèñòåìîé.
Ïðèìåð ìîäåëèðîâàíèÿ. Ïðè çàäàííûõ çíà÷åíèÿõ (ðèñ. 2 è 3) è ïàðàìåòðàõ
ìîäåëèðîâàíèÿ (ðèñ. 4) ïîëó÷åííûå ðåçóëüòàòû ïðèâåäåíû â òàáë. 3.
138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
ÇÀÊËÞ×ÅÍÈÅ
Êàê ïîêàçûâàþò ðåçóëüòàòû ìîäåëèðîâàíèÿ, èñïîëüçîâàíèå â êà÷åñòâå àëãî-
ðèòìà ïëàíèðîâàíèÿ ïðåäëîæåííîãî â [6, 7] ìåòîäà ðåøåíèÿ çàäà÷è íåëèíåé-
íîãî áóëåâîãî ïðîãðàììèðîâàíèÿ ïîçâîëÿåò ñóùåñòâåííî óâåëè÷èòü òàêèå ïî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 139
Ðèñ. 2. Ïàðàìåòðû ìíîæåñòâà çàäà÷
Ðèñ. 3. Ïàðàìåòðû ìíîæåñòâà ðåñóðñîâ
Ðèñ. 4. Ïàðàìåòðû ìîäåëèðîâàíèÿ
Ò à á ë è ö à 3. Ðåçóëüòàòû ìîäåëèðîâàíèÿ ðàáîòû ãðèä-ñèñòåìû ïðè çàäàííûõ
ïàðàìåòðàõ
Ìåòîäû
ïëàíè-
ðîâàíèÿ
Ïîêàçàòåëè êà÷åñòâà ïëàíèðîâàíèÿ
Âðåìÿ
âûïîë-
íåíèÿ
(òàêò)
Âðåìÿ
îæè-
äàíèÿ
(òàêò)
Êîýôôè-
öèåíò
âàæíîñòè
Êîýôôè-
öèåíò
óñêî-
ðåíèÿ
Êîýôôè-
öèåíò
ñîõðà-
íåíèÿ
âàæíîñòè
Êîýôôè-
öèåíò
çàãðóçêè
Êîýôôè-
öèåíò
èñïîëü-
çîâàíèÿ
Ìàêñè-
ìàëüíîå
âðåìÿ
îòâåòà
(òàêò)
Âðåìÿ
îáñëóæè-
âàíèÿ
(òàêò)
MC 16157 36 0.626 1.226 0.781 0.384 0.38 5347 2095
FCFC 18762 196 0.188 1.056 0.763 0.334 0.334 2075 50
NLP 14206 5 0.999 1.395 0.868 0.453 0.454 4168 833
êàçàòåëè, êàê êîýôôèöèåíò âàæíîñòè, êîýôôèöèåíò ñîõðàíåíèÿ âàæíîñòè, êî-
ýôôèöèåíò óñêîðåíèÿ, è óìåíüøèòü âðåìÿ âûïîëíåíèÿ çàäàíèé è âðåìÿ
îæèäàíèÿ ïî ñðàâíåíèþ ñ èçâåñòíûìè ïðîöåäóðàìè ïëàíèðîâàíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ìèíóõèí Ñ.Â. Ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ ïëàíèðîâàíèÿ â ðàñïðåäåëåííûõ âû÷èñëèòåëüíûõ
ñèñòåìàõ. Õ.: Ùåäðàÿ óñàäüáà ïëþñ, 2014. 323 c.
2. Ïîíîìàðåíêî Â.Ñ., Ëèñòðîâîé Ñ.Â., Ìèíóõèí Ñ.Â., Çíàõóð Ñ.Â. Ìåòîäû è ìîäåëè ïëàíèðîâàíèÿ ðå-
ñóðñîâ â GRID-ñèñòåìàõ. Õ.: ÈÍÆÝÊ, 2008. 407 ñ.
3. Ëèñòðîâîé Ñ.Â., Ìèíóõèí Ñ.Â. Ïîäõîä è ìîäåëü ïëàíèðîâàíèÿ ðàñïðåäåëåíèÿ ðåñóðñîâ â Grid. Ìåæ-
äóíàðîäíûé íàó÷íî-òåõíè÷åñêèé æóðíàë «Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè». 2012. ¹ 5.
Ñ. 65–82.
4. Øåëåñòîâ À.Þ., Êóññóëü Í.Í., Ñêàêóí Ñ.Â. Grid-òåõíîëîãèè â ñèñòåìàõ ìîíèòîðèíãà íà îñíîâå ñïóò-
íèêîâûõ äàííûõ. Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. 2006. ¹ 1–2. Ñ. 259–270.
5. Êîâàëåíêî Â.Í., Êîâàëåíêî Å.È., Êîðÿãèí Ä.À., Ëþáèìñêèé Ý.Ç., Õóõëàåâ Å.Â., Øîðèí Î.Í.
Ãðèä-äèñïåò÷åð: ðåàëèçàöèÿ ñëóæáû äèñïåò÷åðèçàöèè çàäàíèé â Ãðèä. Ñá. äîêë. Ìåæäóíàð. êîíô.
«Ðàñïðåäåëåííûå âû÷èñëåíèÿ è Ãðèä-òåõíîëîãèè â íàóêå è îáðàçîâàíèè». Äóáíà, 2004. Ñ. 133–139.
6. Ñèìîíåíêî Â.Ï. Òåîðåòè÷åñêèå îñíîâû ïðîåêòèðîâàíèÿ äèíàìè÷åñêèõ ïðîñòðàíñòâåííûõ ïëàíèðîâ-
ùèêîâ íåîäíîðîäíûõ GRID ñèñòåì. Ýëåêòðîííîå ìîäåëèðîâàíèå. 2011. Ò. 33, ¹ 5. Ñ. 57–71.
7. Ìèíóõèí Ñ.Â. Ìåòîä ðàñïðåäåëåíèÿ ó÷åáíîé çàãðóçêè ñ èñïîëüçîâàíèåì íåëèíåéíîãî áóëåâîãî ïðî-
ãðàììèðîâàíèÿ. ²íôîðìàö³éí³ òåõíîëî㳿 â îñâ³ò³. 2010. Âèï. 5. Ñ. 104–108.
Íàä³éøëà äî ðåäàêö³¿ 17.02.2017
Î.Ñ. ˳ñòðîâà, Â.Î. Áðèêñ³í, Ì.Ñ. Êóðöåâ
ÌÎÄÅËÜ ÐÎÁÎÒÈ ËÎÊÀËÜÍÎÃÎ ÏËÀÍÓÂÀËÜÍÈÊÀ ÍÀ ÎÑÍβ ÐÎÇÂ’ßÇÀÍÍß ÇÀÄÀ×
ÍÅ˲ͲÉÍÎÃÎ ÁÓËÅÂÎÃÎ ÏÐÎÃÐÀÌÓÂÀÍÍß
Àíîòàö³ÿ. Ðîçãëÿíóòî ³ì³òàö³éíó ìîäåëü ðîáîòè ãð³ä-ñèñòåìè, ÿêà äîçâîëÿº
ïîð³âíþâàòè íàÿâí³ ìåòîäè ïëàíóâàííÿ âèêîíàííÿ çàâäàíü, òà äàíî ìàòåìà-
òè÷íèé îïèñ äîñë³äæóâàíèõ â ìîäåë³ õàðàêòåðèñòèê. Íàâåäåíî ïðèêëàä ðîç-
â’ÿçàííÿ çàäà÷³ íà îñíîâ³ ìåòîäó ãðóïîâî¿ âèá³ðêè. Îòðèìàíî åêñïåðèìåí-
òàëüí³ ðåçóëüòàòè, ùî äîâîäÿòü ïåðåâàãè ìåòîäó ïëàíóâàííÿ âèêîíàííÿ çàâ-
äàíü íà îñíîâ³ ðîçâ’ÿçàííÿ çàäà÷ áóëåâîãî íåë³í³éíîãî ïðîãðàìóâàííÿ.
Êëþ÷îâ³ ñëîâà: ãð³ä-ñèñòåìè, ïëàíóâàííÿ, ðåñóðñ, êëàñòåð, ïàêåòíå
îáðîáëåííÿ, ãðóïîâà âèá³ðêà.
E.S. Listrovaya, V.A. Bryksin, M.S. Kurtsev
MODELING LOCAL PLANNER OPERATION BASED ON SOLUTION
OF NONLINEAR BOOLEAN PROGRAMMING PROBLEMS
Abstract. The simulation model of grid system operation is considered, which
allows comparing available job scheduling methods. The mathematical description
of the characteristics analyzed in the model is given. An example of problem
solution based on cluster sampling method is presented. The experimental results
are obtained, which demonstrate the advantages of scheduling method based on
the solution of Boolean linear programming problems.
Keywords: grid systems, planning, resource, cluster, batch processing, sample group.
Ëèñòðîâàÿ Åëåíà Ñåðãååâíà,
êàíäèäàò òåõí. íàóê, äîöåíò êàôåäðû Íàöèîíàëüíîãî àýðîêîñìè÷åñêîãî óíèâåðñèòåòà
èì. Í.Å. Æóêîâñêîãî, Õàðüêîâ, e-mail: listravkina@gmail.com.
Áðûêñèí Âëàäèìèð Àëåêñàíäðîâè÷,
êàíäèäàò òåõí. íàóê, ñòàðøèé ïðåïîäàâàòåëü Óêðàèíñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà æåëåçíîäî-
ðîæíîãî òðàíñïîðòà, Õàðüêîâ, e-mail: vladimir.bryksin@gmail.com.
Êóðöåâ Ìàêñèì Ñåðãååâè÷,
àñïèðàíò Óêðàèíñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà æåëåçíîäîðîæíîãî òðàíñïîðòà, Õàðüêîâ,
e-mail: kurtsev_m@ukr.net.
140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5
|