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

Дипломний проект Система динамічного планування в розподілених обчислювальних мережах

Список термінів, скорочень та позначень

КМ — комп’ютерна мережа КС комп’ютерна система МК мікроконтролер ОС операційна система ПЗ програмне забезпечення ШІМ — широтно-імпульсний модулятор КМОН — комплементарний метал-оксидний-напівпровідник ПЗУ — постійний запам’ятовувач ЕСППЗУ — електронно програмовуваний постійний запам’ятовувач ЕОМ — електронна обчислювальна машина ВДТ — відео-дисплейний термінал

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

У зв’язку з цим набула популярності концепція розподіленої обчислювальної інфраструктури під назвою GRID.

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

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

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

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

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

1. Огляд існуючих рішень та обгрунтування теми дипломного проекту

1.1 Розподілені обчислювальні мережі

Розподілена обчислювальна мережа — група розміщених на великій відстані один від одного комп’ютерів, в тому числі як окремих, так і їх локальних мереж, з'єднаних лініями дротового та / або радіозв'язку.

Частковим випадком розподіленої обчислювальної мережі є GRID-система.

Під GRID-системою будемо розуміти апаратно-програмну інфраструктуру, яка забезпечує надійний, стійкий, повсюдний і недорогий доступ до високопродуктивних комп’ютерних ресурсів.

В роботі наведені критерії, на підставі яких розподілена система є GRID-системою. GRID-система — це така система, яка:

— Координує використання ресурсів за відсутності централізованого управління цими ресурсами;

— Використовує стандартні, відкриті, універсальні протоколи та інтерфейси;

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

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

Найбільш характерними властивостями такої апаратно-програмної інфраструктури є [3−6]:

— Масштаби обчислювальних ресурсів (обсяг пам’яті, кількість процесорів) багаторазово перевищують ресурси окремого комп’ютера або одного обчислювального комплексу;

— Гетерогенність середовища; до її складу можуть входити комп’ютери різної потужності, що працюють під управлінням різних операційних систем і зібрані на різній елементній базі;

— Просторовий розподіл інформаційно-обчислювального ресурсу;

— Об'єднання ресурсів, які не можуть керуватися централізовано (у випадку, якщо вони не належать одній організації);

— Використання стандартних, відкритих, загальнодоступних протоколів та інтерфейсів.

— Забезпечення інформаційної безпеки.

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

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

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

— Організація доступу користувачів до ресурсів;

— Забезпечення прозорості;

— Відкритість;

— Масштабованість.

Метою завдання організації доступу користувачів до ресурсів GRID-системи є полегшення взаємодії користувача із системою та обмін інформацією між ними.

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

— Прозорість доступу: до локальних або віддаленим об'єктів можна звертатися за допомогою однакових операцій;

— Прозорість місцезнаходження: об'єкти повинні бути доступні без необхідності знати їх фізичне місце розташування;

— Прозорість одночасності доступу: кілька користувачів повинні мати можливість одночасного доступу до даних, без небажаних наслідків;

— Прозорість копіювання: повинна існувати можливість копіювати дані з файлів або з інших об'єктів з метою підвищення ефективності або забезпечення доступності непомітно для користувачів;

— Прозорість при несправності: користувачі або прикладні програми повинні мати можливість завершити свої завдання, навіть у випадку несправностей апаратної або програмної частини;

— Прозорість при динамічних змінах конфігурації: система може динамічно змінювати свою конфігурацію, з метою підвищення ефективності і залежно від навантаження.

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

Масштабованість GRID-систем може вимірюватися за трьома різними показниками [13]:

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

— Система може масштабуватися географічно, тобто користувачі і ресурси можуть бути рознесені в просторі;

— Система може бути масштабованої в адміністративному сенсі, тобто бути проста в управлінні при роботі в безлічі адміністративно незалежних організацій.

Спосіб організації програмного забезпечення GRID заснований на відкритій архітектурі служб OGSA [8], у відповідністю з якою GRID кваліфікується як програмна система, що складається із розподілених компонентів — служб, що взаємодіють між собою за допомогою стандартних, відкритих і універсальних протоколів і інтерфейсів. Маючи на увазі головним чином GRID обчислювального типу, можна розглядати його функціонування як процес обслуговування стандартизованих запитів на виконання обчислень, оформлених у вигляді завдань для загальнопоширених операційних систем, причому виконання цих завдань відбувається на ресурсах, які вибираються із загального пулу. Перелічимо основні етапи обробки завдання [7]:

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

— Доставка виконуваних файлів і вхідних файлів на виконавчі ресурси.

— Виконання завдання.

— Після закінчення завдання — доставка результуючих файлів на сервери зберігання (зокрема, на робоче місце користувача).

Всі перераховані етапи обробки завдання виконуються автоматично, без участі суб'єкта, який видав запит, так що GRID являє собою єдину операційну середу.

Оскільки GRID — розподілене середовище, то, як показала практика, необхідні спеціальні служби, які виконують:

— Моніторинг і протоколювання процесу обробки запиту, що дозволяє в кожний момент отримувати інформацію про місцезнаходження та стан завдання, а також керувати його обробкою (видалення, модифікація);

— Забезпечення надійності - перезапуск завдання при збоях програмних або апаратних засобів на ресурсах і телекомунікації;

— Моніторинг і облік споживання ресурсів, на основі чого проводиться планування та діагностика збоїв устаткування.

1.2 Класифікація GRID систем Залежно від способу взаємодії елементів GRID-систем і передачі даних між ними, можна виділити такі основні види організації структури GRID-систем:

— Плоска;

— Стільникова (стільникова плоска або стільникова ієрархічна);

— Ієрархічна.

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

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

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

За типом ресурсів, що надаються, та видам прикладних задач, під рішення яких система оптимізована, GRID-системи поділяються наступним чином:

1) Обчислювальні GRID-системи (Computational Grid) — це тип систем, в яких основним комп’ютерним ресурсом є продуктивність процесора. Серед них можна виділити:

— «розподілені супер-обчислювальні системи» (Distributed Supercomputing);

— «високопродуктивні системи» (High Throughput), які функціонують в паралельному режимі на декількох вузлах.

2) Інформаційні GRID-системи (Data Grid) — це тип систем, в яких основним комп’ютерним ресурсом є обсяг пам’яті даних. Ці системи розглядаються як величезні сховища даних, які зазвичай тісно взаємопов'язані з обчислювальними GRID-системами.

3) Передавальні GRID-системи (Network Grid або Delivery Grid) — це тип систем, в яких вузлами є передавачі (маршрутизатори), що підвищують продуктивність і відмовостійкість мережі передачі даних між джерелом і приймачем.

4) Обслуговуючі GRID-системи (Service Grid) — до даної категорії відносяться системи, що мають сервіси, які не можуть бути забезпечені окремими робочими станціями, а саме:

— Динамічне агрегування даних і надання нових сервісів;

— Надання віртуального робочого простору для користувачів та програм;

— Надання інфраструктури для мультимедійних додатків реального часу.

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

1.3 Основні способи планування в GRID-системах В даний час існує три основних способи планування в Grid системі: централізований, децентралізований і ієрархічний.

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

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

При ієрархічному способі процес планування завдань розподілений на двох рівнях: глобальному і локальному. На глобальному рівні управління завдань здійснює метапланувальник GRID, а на локальному — менеджер ресурсів. На відміну від централізованих метапланувальники GRID-системи зазвичай не можуть безпосередньо управляти ресурсами мережі, але працюють як брокери чи агенти. Інформація про стан доступних ресурсів дуже важлива для метапланувальника GRID-системи для того, щоб виконати ефективне планування, особливо з урахуванням неоднорідної і динамічної природи GRID-мережі. Роль інформаційної служби GRID-системи (Grid information service (GIS)) — забезпечити такою інформацією планувальників GRID. GIS відповідальна за збір і прогноз інформації про стан ресурсу, такої як продуктивність процесора (процесорів) вузлів, розмір пам’яті, пропускна здатність мережі, готовність програмного забезпечення та завантаження вузла в певний період. GIS відповідає на запити для отримання інформації про ресурс або передає інформацію користувачам. Система моніторингу та контролю Globus (The Globus Monitoring and Discovery System (MDS)) — приклад GIS.

Крім інформації про ресурс від GIS, властивості задач (наприклад, приблизна кількість команд, вимоги до пам’яті та зберігання, залежність підзадач в завданні і обсяги комунікації) і продуктивність ресурсу для різних видів задач також необхідні для виконання ефективного планування. Отримання зазначених властивостей може бути забезпечено компонентою профілювання програми (Application profiling (AP)), а вимір продуктивності ресурсу для даного типу задачі - компонентою тестування (analogical benchmarking (AB)). На основі інформації, отриманої від AP і AB, а також на основі своєї моделі продуктивності проводиться оцінка вартості планування вузлів-кандидатів на виконання задачі, з яких планувальник вибирає оптимальний відповідно до цільової функції.

Модуль запуску і контролю (Launching and Monitoring LM) (також відомий як «компонувальник») здійснює передачу задачі на обрані ресурси, пересилаючи вхідні дані і виконувані файли, а в разі потреби і контролює виконання програм. LM Globus GRAM (Grid Resource Allocation and Management) — приклад такого модуля.

Локальний менеджер ресурсів головним чином відповідає за виконання зовнішніх (отриманих від метапланувальника) і локальних завдань, а також передає повідомлення для GIS з інформацією про стан ресурсів. У межах домену один або безліч місцевих планувальників працюють з конкретною локальної політикою управління ресурсами. Приклади таких локальних планувальників включають openpbs і Condor. Для збору інформації про локальний ресурс LRM використовують такі інструментальні засоби, як Network Weather Service, Hawkeye і Ganglia.

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

В GRID-системах планувальник задач реалізований як складова частина системи керування загрузкою (WMS — Workload Management System).

Завданням підсистеми управління завантаженням (WMS) є прийняття запитів на запуск завдань, пошук відповідних ресурсів і контроль їх виконання.

WMS. До складу WMS входять:

— Менеджер загрузки;

— Планувальник / брокер ресурсів;

— Адаптер завдань;

— Модуль, відповідальний за виконання фактичних операцій з управління завданнями;

— Монітор log-файлів WMS.

WMS розподіляє завдання по множині обчислювальних елементів. Обчислювальний елемент може працювати як у відповідністю з моделлю «нетерплячого планування» (push-модель), коли менеджер загрузки самостійно приймає рішення про посилку задачі на обчислювальний елемент, так і в режимі «лінивого планування» (pull-модель), коли обчислювальний елемент запитує завдання у WMS. Обидві стратегії планування мають свої переваги і недоліки. Вибір тієї чи іншої стратегії або їх комбінації залежить від призначення і характеристик роботи (зокрема, інтенсивності запуску задач, числа ресурсних центрів тощо) GRID-системи.

Більшість існуючих розробок в області диспетчеризації завдань в GRID-системах призначені для обслуговування кластеризованих ресурсів, у тому числі система WMS найбільшого на сьогоднішній день GRID проекту EGEE.

Як показано в брокер системи WMS реалізує централізовану схему планування, що працює в двох режимах розподілу завдань: жадного і лінивого (лінивий режим був вперше реалізований в проекті Alien [18]).

Інформаційна база жодного режиму, побудована на інформаційній службі MDS системи Globus Toolkit, недостатньо повна: вона не містить даних, що описують процесорні вузли, так що цей режим може використовуватися тільки в GRID з однорідними ресурсами. Співставлення характеристик ресурсів та завдань в лінивому режимі виконується на основі методу matchmaking і не має такого недоліку.

Система управління завданнями ARC проекту nordugrid представляє інтерес як приклад децентралізованої архітектури планування. У деяких системах знаходять застосування два нових механізму: резервування та міграції. Сценарій Moab Grid Scheduler виглядає наступним чином:

— Завдання GRID надходять в глобальну чергу;

— Планувальник посилає запити в кластери і отримує від них час можливих алокацій;

— Виходячи з отриманої інформації, вибирається кластер, відбувається резервування ресурсів, задача відправляється в кластер.

Moab, також як і CSF (Community Scheduler Framework), який також підтримує резервування в службі планування, не дає повного рішення, припускаючи, що програмне забезпечення на кластерах має засоби для прийняття рішень про те, коли можуть бути відведені ресурси для резервування. Системи gridway і gridlab Resource Management System (GRMS) використовують механізм перерозподілу завдань — міграцію. У gridway після того як глобальне завдання надіслано в кластер спеціальна служба здійснює його моніторинг. У випадку, якщо завдання не запущено, в локальному менеджері ресурсів за певний інтервал часу відбувається перепланування даного глобального завдання, і воно переміщається на інші ресурси.

Одна з перших систем, що використовує прогноз для вибору ресурсів — система Gallop, планування в якій здійснюється на основі передбачення вільної обчислювальної потужності за статистичними даними, для чого на кожному кластері Gallop встановлюються спеціальна компонента (Prophet), що виробляє локальний прогноз. Значну кількість публікацій присвячено прогнозуванню завантаження ресурсів на основі статистичної інформації.

Детерміноване планування розглядається в роботі [21], де досліджується ефективність використання попереднього резервування для багатопроцесорних задач. У запропонованій моделі планування прогноз обмежений одним кроком — часом звільнення ресурсів, який оцінюється по замовленому часу виконання завдань.

В обґрунтовується необхідність розширення функціональності сучасних систем планування функціями попереднього резервування ресурсів і складання розкладів запуску завдань. Автори описують відмінність між системами планування двох типів: традиційними — Queuing systems і системами, заснованими на розкладах — Planning systems. У той час як перші розподіляють завдання, виходячи з поточного стану ресурсів, другі ґрунтуються на повноцінному плані на майбутнє. На думку авторів такий підхід, що реалізований у системі CCS [23], сприяє застосуванню апарату попереднього резервування і відкриває перспективу для вирішення завдання управління паралельними задачами.

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

1.4 Огляд існуючих систем планування

1.4.1 Планувальник Maui

Початкове призначення системи планування Maui — оцінка ефективності завантаження ресурсів: отримуючи на вхід чергу завдань і використовуючи поточні настройки кластерного планувальника, вона видає почасовий розподіл завдань по ресурсах. Особливістю даного планувальника є використання алгоритмів зворотного заповнення (backfill) [27,28] і справедливого розподілу ресурсів (fairshare), які підвищують ефективність системи і зменшують час очікування в черзі. Обидва ці механізми є додатковими опціями, які можна використовувати.

Алгоритм зворотного заповнення — найкращий на сьогодні алгоритм для планування багатопроцесорних завдань. Перевагами даного алгоритму є:

— В умовах роботи у пріоритетній системі дозволяє уникнути зависання завдання, гарантуючи його запуск;

— Ефективно завантажує ресурси, дозволяючи уникнути їх фрагментації;

— Має прийнятні часові характеристики при роботі на великій кількості обчислювальних вузлів;

— Дозволяє працювати на безлічі гетерогенних ресурсів.

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

Принципи справедливого розподілу ресурсів між користувачами ґрунтуються на економічних концепціях з визначенням бюджету завдань.

Наявність системи автоматичного визначення пріоритетів завдань дозволяє давати ключовим користувачам перевагу при розподілі ресурсів. Maui — один з перших планувальників, в якому з’явився розширений менеджер статистики [30], що містить: повну історичну та поточну інформацію про завдання, чергах, планувальнику, стан системи і т.п. Ще одна властивість планувальника в тому, що Maiu має командний інтерфейс для зовнішнього або, так званого, адміністративного резервування.

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

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

1.4.2 Планувальник системи Ursala

Cистема Ursala використовує інтерфейс попереднього резервування, що гарантує виділення ресурсів і запуск завдання в замовлений Час, а також дистанційний інтерфейс з локальним планувальником, що дозволяє визначити можливість виконання завдання на відповідному обчислювальному вузлі. Система також дозволяє планувати багатопроцесорні завдання, але для цього користувач повинен явно вказати ресурси, на яких він хоче розмістити своє завдання. З зазначених обчислювальних вузлів в систему надходять списки часових інтервалів, в які завдання може бути запущено, після чого планувальник визначає кращий час запуску завдання на цих ресурсах. Таким чином, основний недолік цієї системи полягає в тому, що вона здійснює планування вимагаючи від користувача конкретизації ресурсів для запуску його завдання.

1.4.3 Брокер системи WMS

Брокер системи WMS (Workload Management System) реалізує централізовану схему планування. При цьому розрізняють два режими розподілу завдань: жадібний і ледачий, так само можливі комбіновані варіанти цих двох режимів.

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

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

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

1.4.4 Планувальник CSF

Планувальник CSF (Community Scheduler Framework) відноситься до централізованих планувальників через наявність глобальної черги завдань. Основний принцип планування, на якому заснований цей метод, — це попереднє резервування ресурсів. Вхідну черги завдань для планувальника формує одна з утиліт, що задає їм пріоритет відповідно до обраної політики розподілу. Планувальник має служби нотифікації, завдяки чому стежить за звільненням ресурсів і може здійснювати миттєве занурення. Планувальник CSF є відкритою реалізацією і включений в globustoolkit.

1.4.5 Система керування завданнями ARC

Система керування завданнями ARC (Advanced Resource Connector) використовується в проекті nordugrid. АРК реалізує фундаментальні служби Grid, такі як інформаційна служба, пошук і зіставлення ресурсів, спостереження за ресурсами, керування ресурсами. Система не використовує більшість служб, що входять до globustoolkit. Всі реалізовані нею служби надбудовуються над бібліотеками globustoolkit, проте працюють під захистом служби безпеки GSI.

У цілому дана система планування аналогічна жадібному режиму брокера WMS. Відмінностями від брокера є те, що планувальник входить до складу програмного забезпечення кожного робочого місця користувача, а планування і передача завдання в кластер виконується безпосередньо з місця видачі запиту.

1.4.6 Планувальник системи PAUA

Grid складається з ресурсів, які розрізнені по всьому світу. При цьому вони можуть бути як настільними, так і суперкомп’ютерами. Для отримання доступу до них необхідно створити запит до менеджера ресурсів.

Планувальник, використовуваний в системі PAUA, званий sitesheduler [34], так представляє розрізнені ресурси, щоб вони були доступні планувальникам. Це передбачає, що жоден з планувальників не може провести планування, не пройшовши через sitesheduler. Основними завданнями планувальника сайту є верифікація прав доступу до завдань Grid та виділення ресурсів для твору обчислень користувача завдань. Даний планувальник має такі особливості:

— Наявність служб, що кешують завдання і виконувані файли так, що планувальник може працювати, як проксі-сервіс;

— Наявність служби моніторингу ресурсів і прогноз виконання алокації;

— Представлення всіх об'єднаних ресурсів даної області у вигляді одного віртуального ресурсу, до якого буде здійснюватися запит.

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

1.4.7 Брокер GRB

GRB — брокер ресурсів Grid, який служить для контролю і керування завданнями користувачів. GRB містить такі компоненти [42]:

— Resource Broker Master (RBM) — це основний процес, який приймає від користувачів всі запити;

— Resource Broker Assistant (RBA) — це процес, породжуваний Resource Broker Master для обробки певного запиту від користувача, який здійснює функцію розподілу завдань по ресурсах;

— Job Registry (JR) — база даних, в якій зберігається вся інформація, потрібна GRB;

— Job Submission Service (JSS) — служба запуску задач на ресурсах та їх моніторингу;

— Grid Security Infrastructure (GSI) — інфраструктура безпеки;

— User Interface (UI) — інтерфейс користувача, що забезпечує взаємодію користувача з RBA.

RBА агент відповідає за прийом та обслуговування клієнтського запиту. При цьому він отримує від користувача задачу, характеристики необхідних ресурсів і шукає підходящий ресурс. В цілому він займається такими основними завданнями: приймає завдання, визначає список найбільш підходящих ресурсів і скасовує роботи.

Для виконання роботи користувача обробник запиту має взаємодіяти зі службою JSS, яка запускає і скасовує виконання завдання на ресурсі. При цьому взаємодія RBM та JSS засновано на тому, що RBM проводить опитування, чи не пришло від JSS повідомлення.

RBM — є основною ланкою в системі. Він приймає як запити користувачів, так і повідомлення про завершення та скасування роботи.

Основною метою брокера GRB є організація взаємодії всіх цих компонентів, які в сукупності дозволяють отримати високу ефективність завантаження і роботи системи.

1.4.8 Планувальник Moab Workload Manager

Робота Moab Workload Manager базується на декількох алгоритмах створення черги задач та вибору обчислювального вузла для кожної задачі.

Сценарій Moab Grid Scheduler виглядає наступним чином:

— Завдання GRID надходять в глобальну чергу;

— Планувальник посилає запити в кластери і отримує від них час можливих алокацій;

— Виходячи з отриманої інформації, вибирається кластер, відбувається резервування ресурсів, задача відправляється в кластер.

Moab, також як і CSF (Community Scheduler Framework), який також підтримує резервування в службі планування, не дає повного рішення, припускаючи, що програмне забезпечення на кластерах має засоби для прийняття рішень про те, коли можуть бути відведені ресурси для резервування.

2. Алгоритм динамічного планування задач

Незважаючи на широке визнання алгоритм планувальника Moab Workload Manager має певні недоліки, серед яких пошук ресурсу з початку списку та ігнорування такого параметру як кількість даних для задачі.

В даному розділі розглянуто базовий алгоритм по роботи системи та його модифікації з огляду на їх необхідність.

2.1 Алгоритм планувальника Moab Workload Manager

Moab Workload Manager є високорозвиненою системою планування та управління задачами, що призначена для кластерів, grid та систем on-demand/utility обчислень. На верхньому рівні, Moab застосовує задані політики і масову оптимізацію, щоб організувати виконання задач та сервісів задля оптимального використання можливостей мережі, обчислювальних та зберігаючих ресурсів. Moab дозволяє реалізувати справжні адаптивні обчислення завдяки тому, що обчислювальні ресурси можуть бути пристосовані до потреб, які постійно змінюються, то завдяки тому, що система може автоматично виправляти або видаляти несправні вузли.

Moab підвищує доступність системних ресурсів, має широкі можливості для діагностики ресурсів, забезпечує потужні функції qos / SLA, а також надає якісну візуалізацію продуктивності ресурсів через розширену статистику, звіти і графіки.

Moab працює практично з усіма основними утилітами керування та моніторингу ресурсів. Від апаратних систем моніторингу (таких як IPMI) до систем забезпечення і зберігання, Moab використовує статистику та власний досвід, щоб ці системи працювали найкраще.

Moab використовує свою глобальну інформацію для координації діяльності ресурсів та сервісів задля підвищення загальної продуктивності.

Moab функціонує, маніпулюючи множиною елементарних об'єктів, таких як задачі, вузли, резервування, структури qos (якість обслуговування), менеджери ресурсів, політики та ще декілька незначних елементарних та складових об'єктів.

Інформація про завдання надається планувальнику одним із менеджерів ресурсів, таких як loadleveler, PBS, Wiki, або LSF. Атрибути завдання включають в себе: власник, стан завдання, кількість і тип ресурсів, необхідних для завдання та межі часу, як довго ресурси будуть зайняті завданням. Завдання складається з однієї або кількох задач, кожна з яких потребує задану кількість ресурсів заданого типу. Наприклад, завдання може складатися з двох груп задач, перша з яких включає одну основну задачу (master) і потребує один вузол IBM SP з не менш як 512 МБ оперативної пам’яті, а друга містить набір залежних задач (slave) та потребує 24 вузла IBM SP з не менш як 128 МБ оперативної пам’яті. Кожна група складається з однієї або кількох задачі, де задача визначається як мінімальна самостійна одиницю ресурсів. За замовчуванням, кожна задача еквівалентна одному процесору. У середовищі SMP, тим не менш, користувачі можуть зв’язати один або кілька процесорів разом з певним обсягом пам’яті та інших ресурсів для однієї задачі.

Стани завдання:

DEFFERED — завдання, яке було відкладено планувальником Moab через неможливість виконати планування завдання в поточних умовах. Відкладені завдання затримуються на час DEFERTIME перед тим як знову розмістити їх у чергу завдань. Цей процес повторюється DEFERCOUNT разів, перш ніж завдання відправляється до відкинутих (HOLD) завдань.

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

IDLE — завдання в даний час у черзі і має право виконуватися, але не виконується.

MIGRATED — завдання, яке надіслано до віддаленого вузла, але яке ще не почалося виконуватися.

STAGED — завдання було перенесено на інший планувальник, але ще не почалося виконуватися.

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

RUNNING — задача в даний момент виконується програмою користувача.

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

CANCELLING — завдання було скасовано, і знаходиться в процесі очищення.

COMPLETED — завдання було виконано без помилок.

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

VACATED — завдання скасовано після часткового виконання через збій системи.

Moab визначає вузол як множину ресурсів з певним набором пов’язаних атрибутів. Це визначення аналогічно традиційному поняттю вузол, яке можна знайти в Linux кластері або суперкомп’ютері в яких вузол визначається як один або декілька процесорів, пов’язаних з пам’яттю, і, можливо, іншими обчислювальними ресурсами, такими як локальний диск, віртуальна пам’ять, мережеві адаптери, а також ліцензії на програмне забезпечення. Крім того, вузол описується різними параметрами, такими як тип архітектури або операційної системи. Вузли бувають різними в діапазоні розмірів від невеликих однопроцесорних комп’ютерів до великих систем симетричної багатопроцесорної обробки (SMP), де один вузол може складатися із сотень процесорів і великих обсягів пам’яті.

Типовий алгоритм обробки завдань в Moab:

1) Визначення списку доступних завдань На першому кроці планування визначаються які завдання є наявними та доступними. Визначаються завдання, які вже виконуються/виконані на вузлах, мають помилковий стан або мають незадовільні передумови (невиконані попередні завдання, або не готовий файл даних).

2) Пріоритетизація завдань Після того, як список доступних завдань створено, наступний крок полягає в визначенні відносних пріоритетів всіх завдань у списку. Пріоритет кожної задачі визначається на основі атрибутів задач, таких як власник, розмір завдання так час, який задача пробула в черзі.

3) Забезпечення виконання заданої політики регулювання Політика регулювання вказує, скільки завдань, вузлів, процесорів тощо дозволено використовувати в одиницю часу. Завдання, що порушують задану політику не використовуються для планування.

4) Визначити доступність ресурсів Для кожного завдання, Moab намагається знайти необхідні ресурси, які потрібні щоб виконати необхідні обчислення. Щоб встановити відповідність між задачами та ресурсами, вузол повинен володіти всіма атрибутами, які визначені в завданні, та відповідати обмеженню, заданому константою taskspernode (завдань на вузол). За замовчуванням taskspernode = 1. Зазвичай, Moab визначає що вузол має достатньо ресурсів, якщо ресурси не використовуються, та не призначені для виконання іншого завдання.

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

6) Розподіл задач по вузлам Після обрання ресурсів, Moab призначає завдання на реальні ресурси. Розподіл відбувається, як правило на основі простих алгоритмів розподілу завдань, таких як циклічний, але може бути також запрограмований на мові паралельного програмування (наприклад, MPI або PVM) задля мінімізації накладних витрат на міжпроцесну взаємодію.

7) Запуск роботи Коли ресурси відібрані і завдання призначені на реальні ресурси, планувальник повідомляє менеджер ресурсів де та як виконувати завдання. Після чого менеджер ресурсів фактично ініціює запуск завдання.

Як ми бачимо із пунктів 2 та 5, значною частиною алгоритму планування є спосіб пріоритетизації задач та політика призначення ресурсів.

Пріоритетизація відбувається шляхом створення черги задач за певним принципом. Moab підтримує декілька таких принципів. Ми розглянемо декілька базових:

1) Створення черги за принципом FIFO

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

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

3) Сортування завдань за вагою обчислень за збиванням

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

Політика призначення ресурсів визначає порядок, за яким будуть обиратися вузли для виконання кожної наступної задачі.

Moab передбачає використання багатьох режимів для призначення ресурсів. Розглянемо деякі з них:

1) CPULOAD — вузли обираються за мінімальною загрузкою обчисленнями. Цей режим ідеально підходить для систем, які складаються з вузлів з розділяємим часом та дозволяє починати виконувати завдання негайно.

2) FIRSTAVAILABLE — вузли обираються в порядку, в якому вони присутні в менеджері ресурсів. Це дуже простий та найшвидший алгоритм.

3) LASTAVAILABLE — вузли обираються в зворотному порядку, в якому вони присутні в менеджері ресурсів.

4) PRIORITY — вузли обираються за заздалегідь заданим пріоритетом.

5) MINRESOURCE — вузол обирається таким чином, щоб задовольняти найменшим вимогам задачі. Це дозволяє більш ефективно використовувати ресурси та їх можливості.

6) FASTEST — вузли обираються за їх потужністю. Цей режим дозволяє виконувати завдання якнайшвидше.

Опис алгоритму:

1) Визначення списку доступних завдань;

2) Пріоритетизація завдань та створення черги завдань згідно до обраного способу пріоритетизації завдань;

3) Створення списку ресурсів згідно до обраного режиму призначення ресурсів;

4) Вибір першого завдання з черги завдань;

5) Вибір першого вузла зі списку ресурсів;

6) Призначення обраного вузла обраному завданню;

7) Пересилка завдання на обраний вузол;

8) Якщо список доступних завдань не пустий — переходимо до п. 4;

2.2 Модифікований алгоритм планувальника Moab Workload Manager

При плануванні кожної наступної задачі Moab Workload Manager починає перегляд списку ресурсів з початку. Це призводить до того, що призначення ресурсів виконується нерівномірно: вузли в початку списку завжди будуть більш завантаженими, ніж у кінці. Також це призводить до зменшення швидкості планування через те, що при послідовному призначенні N задач на і-му шагу перші і-1 вузли буде вже гарантовано призначено, але планувальник все одно буде переглядати їх.

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

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

На рисунку 2.1 ми бачимо, що планувальник призначив задачу 1 та задачу 2 на перший та другий вузол відповідно. Задача 3 та задача 4 призначені на третій та четвертий вузол відповідно. Оскільки задача 1 та 2 перші в черзі планувальника, то їх передача почнеться раніше та вони займуть обидві лінії зв’язку планувальника. Тоді задачі 3 та 4, які мають менший обсяг даних Рисунок 2.1 Неоптимальне використання ліній зв’язку Третій та четвертий вузол відповідно. Оскільки задача 1 та 2 перші в черзі планувальника, то їх передача почнеться раніше та вони займуть обидві лінії зв’язку планувальника. Тоді задачі 3 та 4, які мають менший обсяг даних для передачі не будуть відправлені поки триває передача задач 1 та 2, які мають більший обсяг даних. В даному випадку, задачі 3 та 4 будуть чекати час 50/S, де S — швидкість передачі даних.

Якщо ж передавати спочатку ті задачі, які мають менший обсяг даних, то решта задач буде очікувати менший час перед передачею. В наведеному прикладі цей час складав би 10/S.

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

Третя модифікація тісно пов’язана з другою: призначати вузли, швидкість з'єднання з якими нижча, задачам з меншою кількістю даних. Це також дозволить зменшити час, який задачі проводять в черзі на відправлення до вузлів. Але, оскільки в деяких режимах роботи планувальника (FIRSTAVAILABLE та LASTAVAILABLE) ця модифікація призведе до повної зміни алгоритму вибору ресурсу, то для цих режимів вона не використовується. Для таких режимів як CPULOAD, PRIORITY, MINRESOURCE та FASTEST частіш за все для однієї задачі існує декілька варіантів призначення, які є рівноправними з точки зору обраного режиму вибору ресурсу. Наприклад, в режимі FASTEST може бути декілька вузлів з приблизно однаковою швидкодією. Цю модифікацію можна використовувати для вибору одного з них.

Підсумуємо все вищесказане. Модифікація базового алгоритму полягає в наступних трьох пунктах:

— Циклічний перегляд списку вузлів;

— Передача спочатку задач з меншою кількістю даних;

— Призначення вузлів, швидкість з'єднання з якими нижча, задачам з меншою кількістю даних.

Перевагами є:

— Більш рівномірна загрузка;

— Зменшення часу очікування задач на передачу і, як наслідок, зменшення часу, який задача перебуває в системі, та зменшення простою вузлів.

Серед недоліків можна виділити:

— Збільшення часу планування;

— Необхідність в зборі статистики швидкості підключення вузлів.

Опис модифікованого алгоритму:

1) Визначення списку доступних завдань;

2) Пріоритетизація завдань та створення черги завдань згідно до обраного способу пріоритетизації завдань;

3) Створення списку ресурсів згідно до обраного режиму призначення ресурсів;

4) Вибір групи завдань для планування з однаковим пріоритетом із черги завдань;

5) Сортування групи завдань за об'ємом даних для обробки;

6) Вибір групи вузлів із списку ресурсів, що мають однакові характеристики з точку зору обраного режиму призначення ресурсів;

7) Сортування групи вузлів за швидкістю з'єднання з планувальником;

8) Вибір завдання з найменшим об'ємом даних із групи;

9) Вибір вузла з найкращою швидкістю з'єднання з планувальником;

10) Призначення обраного вузла обраному завданню;

11) Якщо в групі завдань ще є завдання, то переходимо до п. 6;

12) Якщо список доступних завдань не пустий — переходимо до п. 5;

13) Сортування спланованих завдань за об'ємом даних;

14) Розсилка завдань на призначені вузли.

3. Розробка системи моделювання роботи GRID

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

В основу системи моделювання покладені принципи, за якими працює планувальник Moab Workload Manager.

Система містить реалізацію базового, модифікованого алгоритмів та має наступні функції:

— Створення та редагування структури GRID-системи;

— Читання та запис в файл структури GRID-системи;

— Генерація завдань для виконання;

— Вибір параметрів моделювання;

— Планування завдань;

— Моделювання роботи GRID-системи;

— Збір та відображення статистики.

В системі реалізовані наступні режими пріоритетизації завдань:

— Створення черги за принципом FIFO;

— Сортування завдань за вагою обчислень за зростанням;

— Сортування завдань за вагою обчислень за збиванням.

Можливі режими призначення ресурсів:

— FIRSTAVAILABLE — за порядком присутності в списку ресурсів;

— FASTEST — за потужністю вузлів.

Інтерфейс системи моделювання зображено на рисунку 3.1.

Рисунок 3.1 Зовнішній вигляд системи моделювання Система реалізована на мові програмування C# та має модульну структуру. Зв’язок між модулями зображено на рисунку 3.2.

Проект складається з трьох модулів.

Модуль Core — ядро системи. Воно представляє собою програмну модель GRID, містить реалізацію базового та модифікованого алгоритмів і безпосередньо відповідає за моделювання роботи GRID.

Рисунок 3.2 Зв’язок між модулями програми