В.В. Литвинов, д-р техн. наук, професор

І.В. Стеценко, канд. техн. наук, доцент

Інститут проблем математичних машин і систем, м. Київ, Україна

Черкаський державний технологічний університет, м. Черкаси, Україна

модель системи управління розподіленими обчислювальними ресурсами

Запропоновано використання Петрі-об’єктної технології моделювання для побудови імітаційної моделі системи управління розподіленими обчислювальними ресурсами. Побудовано модель розподілу обчислювальних ресурсів однорівневої грід-системи та здійснено дослідження ефективності вибраної стратегії управління.

Постановка проблеми. На сьогодні розроблені ефективні програмні та інструментальні засоби створення грід-систем. Найбільш відомими відкритими програмними продуктами, що забезпечують стандартний набір бібліотек для інтеграції користувачів, є Globus Toolkit та Sun Grid Engine. Комерційна версія останнього – Sun Grid Engine, Enterprise Edition, – призначена для управління ресурсами підприємств і спроможна обслуговувати кілька незалежних проектів та груп користувачів.

Основним питанням, що залишається недостатньо дослідженим, є алгоритми розподілу обчислювальних та інформаційних ресурсів, які знаходяться у спільному використанні користувачів грід-системи. Користувачі прагнуть отримувати бажані ресурси з найменшим часом очікування, а проектувальники систем управління забезпечують насамперед несуперечність прав доступу до ресурсів грід-системи, відсутність конфліктних ситуацій, відсутність відмов обслуговування.

Моделі статичного розподілу ресурсів не задовольняють потреби обчислювальних систем, тому є необхідність розробки моделі динамічного розподілу ресурсів.

Аналіз досліджень і публікацій. Огляд публікацій [1], [2], [3], [4] що розглядають розподіл ресурсів грід-систем, підтверджує наявність різноманітних підходів щодо розв’язання проблеми, а також про необхідність розробки ефективних способів моделювання різних стратегій управління ресурсами розподілених систем. Існуючі системи моделювання грід-систем, такі як MicroGrid, OptorSim, GridSim, SimGrid, мають ряд недоліків, пов’язаних з вузькою спеціалізацією, обмеженістю модельованої архітектури грід-систем, недостатньою гнучкістю у визначенні способу управління [5].

Мета дослідження. У цій публікації наведені результати моделювання системи управління розподіленими обчислювальними ресурсами з метою дослідження її ефективності та вибору параметрів управління. Використання Петрі-об’єктного підходу [6] дозволило розробити та дослідити модель динамічного розподілу обчислювальних ресурсів грід-системи.

Модель системи управління з блокуванням захоплення ресурсу. Кластерні системи можуть використовуватись для масиву послідовних програм, або розподілених програм, що використовують спільні дані, або паралельних програм. У роботі розглянуто [7] цей огляд архітектури кластерних систем та наведено аналіз програмних пакетів управління потоками завдань таких систем. Система управління кластера розподіляє обчислювальні ресурси кластера між завданнями, що надходять від користувачів. Система має черги завдань користувачів та виділяє необхідний обчислювальний ресурс для виконання завдання таким чином, щоб максимально задовольнити потреби користувачів.

Розглянемо найпростіший приклад розподілення обчислювальних ресурсів між трьома користувачами (рис.1). Зав­дання користувача A потребують використання всіх обчислювальних ресур­сів, а завдання інших користувачів можуть виконуватись одночасно. Модель системи представимо мережею Петрі з часовими затримками, з конфліктними та багатоканальними переходами, з інформаційними зв’язками (рис.1). Позиція представляє кількість доступного спільного ресурсу, позиції , , пред­ставляють буфер завдань A, B, C відповідно. Припускається, що у буфері завдань завжди є завдання для обчислення. Часові затримки в переходах , , відповідають часу виконання завдань користувачів A, B, C. Нерівномір­ність споживання ресурсів призводить до того, що при відсутності процесів управління завдання з меншою потребою ресурсу використовують ресурс у повній мірі, а завдання з більшою потребою знаходяться у нескінченному очікуванні вивільнення необхідного обсягу ресурсу. Завдання конфліктують за захоплення ресурсу настільки, що, наприклад, при часових затримках у переходах , , в середньому 1, 0,157 і 0,333 відповідно, завдання користувачів В і С, один раз захопивши ресурс і по черзі його вивільняючи, не дають завданням користувача А ніякої можливості зайняти ресурс. Присвоєння пріоритету переходу призводить до зайняття ресурсу виключно завданнями користувача А, отже не вирішує проблему розподілу ресурсів між завданнями. Присвоєння ймовірності запуску переходу також не вирішує проблему, оскільки не виникає конфлікт переходу з іншими переходами.

Введемо динамічне управління розподілом ресурсів, що здійснюється блокуванням можливості захоплення ресурсів на основі інформації про кількість виконаних завдань. Порівняння кількості виконаних завдань здійснюється переходом так, що в позиціях , , міститься інформація про різницю кількості виконаних завдань користувачів A, B, C у порівнянні з іншими завданнями. При більшій кількості виконаних завдань користувачів В і С приймається рішення про блокування виконання цих завдань (перехід ), а при більшій кількості виконаних завдань користувача А – рішення про зняття цього блокування (перехід ).

Дослідження імітаційної моделі системи управління дозволяє оцінити ефективність функціонування системи при різних значеннях параметрів управління. Введемо параметри управління, що відповідають умовам, за яких приймається рішення про блокування:

, , ,

де – вага дуги, що з’єднує позицію і перехід .

Результати експериментів наведені на рис. 2. За результатами виходить, що є найкращою комбінацією параметрів з точки зору найбільшої загальної кількості виконаних завдань, є найліпшою комбінацією параметрів з точки зору досягнення найменшої різниці у кількості виконаних завдань різних класів, а комбінацією є найоптимальнішою з точки зору найбільшої кількості виконаних завдань класу С.

а) б) в)

Рис. 2. Результати експериментального дослідження параметрів системи управління розподілом ресурсів при різних критеріях: а) загальна кількість виконаних завдань усіх класів; б) загальна
різниця у кількості виконаних завдань усіх класів; в) кількість виконаних завдань класу С

Модель системи управління з виділенням ресурсу планувальником завдань

Розглянемо однорівневу грід-систему, що складається з планувальника системи та розподілених обчислювальних ресурсів. Обчислювальні ресурси представлені комп’ютерами користувачів, а планувальник управляє розподілом ресурсів між користувачами системи так, щоб забезпечувати синхронізований та несуперечливий доступ користувачів грід-системи до спільних обчислювальних ресурсів. Планувальник взаємодіє не з апаратними ресурсами, а з грід-сервісами програмної інфраструктури, що встановлені у розподілених обчислювальних вузлах. Грід-сервіси з певним інтервалом часу, що називають тактом управління, надають планувальнику інформацію про поточний стан обчислювального ресурсу. Введення такту управління є необхідною умовою організації управління грід-систем.

Окрім несуперечливого та безвідмовного доступу до ресурсів, планувальнику ставиться також завдання забезпечення найбільш високої вдоволеності потреб користувачів, що вимірюється такими величинами як середній час очікування завдань, інтенсивність відмов обслуговування завдань користувача, інтенсивність споживання обчислювального ресурсу користувачами та іншими.

Рішення про виділення ресурсу приймається планувальником системи управління на початку кожного такту управління відповідно до заданого алгоритму розподілу обчислю­вальних ресурсів або відповідно до вибору тієї чи іншої політики розподілу. Програмний пакет Sun Grid Engine, Enterprise Edition (SGEEE), наприклад, надає можливість вибору однієї з чотирьох політик розподілу ресурсів між незалежно працюючими користувачами: політика розділених ресурсів, функціональна політика, політика „роботи до строку”, політика явного виділення ресурсів [9]. Поняття „справедливого” управління розподілом ресурсів пов’язують з таким розподілом ресурсів грід-системи, при якому віртуальний обчислювальний ресурс розподіляється між активними користувачами пропорційно їх внеску у загальний віртуальний обчислювальний ресурс [1]. Активні користувачі отримують доступ до віртуального ОР пропорційно своїй квоті:

, , (1)

де – квота і-ого користувача, що розраховується як частка ресурсу, внесеного користувачем у загальний віртуальний обчислювальний ресурс, – частка доступного віртуального ресурсу з урахуванням тільки активних користувачів, U – множина активних користувачів.

Модель системи управління грід-ресурсами побудована з застосуванням технології Петрі-об’єктного моделювання [6] і складається з Петрі-об’єктів “Планувальник”, “Користувач”, “Завдання”. Динаміка функціонування Петрі-об’єктів описується стохастичною мережею Петрі з часовими затримками, з багатоканальними та конфліктними переходами, з інформаційними зв’язками (рис. 3, 4, 5).

Перехід „Розпочати розподіл” здійснюється з часовою затримкою, що дорівнює тривалості такту управління. В результаті запуску переходу „Розрахунок частки доступного ресурсу” Петрі-об’єкта “Планувальник” встановлюються відповідні значення ймовірностей запуску переходів „А”, „В”, „С”, „D”. Вільний віртуальний обчислювальний ресурс, обсяг якого вимірюється в умовних процесорах чи в одиницях MIPS (Million Instruction Per Second), розподіляється випадковим чином між користувачами відповідно до заданих імовірностей.

Буфер завдань користувача може містити одне або кілька завдань. Виконання кожного завдання, що зберігається в буфері завдань, моделюється відповідним Петрі-об’єктом „Завдання”. Якщо наданого планувальником обсягу віртуального обчислювального ресурсу достатньо для виконання завдання, то завдання виконується. В іншому випадку завдання отримує відмову через відсутність достатньої кількості ресурсу в цьому такті управління.

Користувач може знаходитись у пасивному та активному стані, якщо користувач активний, то із заданою інтенсивністю він генерує завдання та потребу завдання в обчислювальному ресурсі. Кожне сформоване завдання відправляється в буфер завдань користувача або отримує відмову, якщо вільного місця в буфері завдань немає. Петрі-об’єкт “Користувач” містить інформацію про поточний стан користувача, кількість місць у буфері завдань, кількість відмов та обсяг невдоволеної потреби користувача.

Результати експериментального дослідження Петрі-об’єктної моделі системи управління грід-ресурсами представлені на рис. 6-9. Серії експериментів проводились з виділенням ресурсу з урахуванням інформації про активних користувачів (формула (1)) та без урахування інформації про активних користувачів (х_і = р_і = const), тобто динамічне та статичне управління розподілом ресурсів. Завдання користувачів В,С,D в усіх експериментах надходять з інтенсивністю 1 завдання/4 одиниці часу і потребують у середньому 20 MIPS обчислювального ресурсу, а завдання користувача А надходять з інтенсивністю 1 завдання/8 одиниць часу і потребують у середньому 100 MIPS. Для завдань користувачів В,С,D передбачений буфер завдань місткістю одне завдання, а для завдань користувачів А – місткістю два завдання.

З результатів виходить, що використання динамічного управління є доцільним тільки при достатньо великій кількості ресурсу. Так, для досліджуваної системи управління поліпшення характеристик функціонування забезпечується при кількості ресурсу користувача А більше 50 MIPS та більше.

Значний вплив на характеристики функціонування системи спричиняє тривалість циклу управління. Використання динамічного управління, у порівнянні зі статичним, дозволяє зменшити інтенсивність відмов. Збільшення обсягу ресурсу користувача А при різних значеннях тривалості циклу управління сильно впливає на зростання продуктивності системи при незначних обсягах ресурсів інших користувачів. Тривалість циклу управління сильно впливає на зменшення інтенсивності відмов при зростанні обсягу користувача А та великих обсягах ресурсів користувачів В,С,D.

а) б)

Рис. 6. Продуктивність при змінюванні тривалості циклу управління для різних значень обсягу ресурсу користувача А(обсяг ресурсу інших користувачів 5MIPS):а)статичне управління; б)динамічне управління

а) б)

Рис. 7. Інтенсивність відмов при змінюванні тривалості циклу управління для різних значень обсягу ресурсу користувача А (обсяг ресурсу інших користувачів 5MIPS): а) статичне
управління; б) динамічне управління

а) б)

Рис. 8. Продуктивність при змінюванні обсягу ресурсу користувача А для різних значень циклу (динамічного) управління: а) обсяг ресурсу інших користувачів 5MIPS; б) обсяг ресурсу інших користувачів 100 MIPS

а) б)

Рис. 9. Інтенсивність відмов при змінюванні обсягу ресурсу користувача А для різних значень циклу (динамічного) управління: а) обсяг ресурсу інших користувачів 5MIPS; б) обсяг ресурсу інших користувачів 100 MIPS

Таким чином, вибір стратегії управління і параметрів управління спричиняє значний вплив на характеристики функціонування системи. Відтворення системи управління розподіленими обчислювальними ресурсами з використанням стохастичних мереж Петрі з часовими затримками, з багатоканальними та конфліктними переходами дозволяє враховувати найдрібніші деталі процесу функціонування системи управління та об’єкту управління, такі як: динамічне захоплення обчислювального ресурсу, виділення доступного ресурсу користувача в кожному такті управління відповідно до його квоти, індивідуальні властивості користувачів грід-системи.

Висновки. У результаті наукового дослідження розроблені підходи щодо побудови імітаційної моделі системи управління розподіленими обчислювальними ресурсами, що дозволяє враховувати стратегію та параметри управління, індивідуальні якості користувачів, динамічне захоплення віртуального обчислювального ресурсу користувачами системи залежно від обраної стратегії управління. Дослідження імітаційної моделі управління розподіленими обчислювальними ресурсами дозволяє здійснити вибір стратегії управління та параметрів управління. Використання Петрі-об’єктної технології моделювання систем надає можливість конструювання складної грід-системи з довільною кількістю користувачів та завдань, що зберігаються в буфері завдань.

Список використаних джерел

1. Сайт Института проблем математики им. М. В. Келдыша Российской Академии наук Коваленко В. Н., Корягин Д. А. Организация ресурсов грид // Preprint, Inst. Appl. Math., the Russian Academy of Science. – Москва, 2004 [Электронный ресурс]. – Режим доступа: http://www.keldysh.ru/papers/2004/prep63/prep2004_63.html#_Toc85204258.

2. Шелестов А. Ю. Имитационная модель взаимодействия GRID-узлов с очередью доступа к общей памяти / А. Ю. Шелестов // Автоматика. Автоматизация. Электротехнические комплексы и системы. – Херсон: ХНТУ, 2008. – №1 (21). – С. 32-40.

3. Эвристики распределения задач для брокера ресурсов Grid / А. И. Аветисян, С. С. Гайсарян, Д. А. Грушин [и др.] // Труды Института системного программирования РАН. Том 5. – М., 2004. – С. 269-280.

4. Петренко А. І. Комп’ютерне моделювання грід-систем / А. І. Петренко // Электроника и связь 5’ Тематический выпуск «Электроника и нанотехнологии». – № 5. – К.: Политехника, 2010. – С. 40-48.

5. Sulistio A., Cibej U., Venugopal S., Robic B., Buyya R. A toolkit for modeling and simulating Data Grids: an extension to GridSim / Concurrency and Computation: Practice and Experience - Concurrency. – 0123 John Wiley & Sons, Ltd, 2008. – Vol.20, No 13. – P.1591-1609.

6. Стеценко И. В. Формальное описание систем средствами Петри-объектных моделей / И. В. Стеценко // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: зб. наук. пр. – № 53. – К.: ВЕК+, 2011. – С.74-81.

7. Аветисян А. И. Системы управления кластерами / А. И. Аветисян, Д. А. Грушин, А. Г. Рыжов // Труды Института системного программирования РАН. Том 3. – М., 2002. – С. 39-62.

8. Литвинов В. В. Распределенная система имитационного моделирования на основе архитектуры CORBA / В. В. Литвинов, В. В. Казимир, И. Б. Гавсиевич // Математичні машини і системи. – № 2, 3. – К., 2000. – С. 111-114.

9. Анни П. Этот Grid – неспроста… / П. Анни // Открытые системы. – №1. – М., 2003 [Электронный ресурс]. – Режим доступа: http://citforum.ru/nets/articles/egridn.shtml.