Методи та засоби ефективної обробки паралельних задач в комп’ютерних кластерних системах (стр. 7 )

Спільні змінні: а, захищена м’ютексом Ма;

b, захищена м’ютексом Mb

1 Потік Т1 begin
2	а ← а + 1 ;
3 end
4 Потік T2 begin
5	P(Ma)
6	а ← a + 1 ;
7 end
8 Потік T3 begin
9	P(Mb)
10	а ← a + 1 ;
11	V(Mb)
12 end

__________________________________________________________________

Рис. 1.4. Приклад паралельної програми, помилки в якій пов’язані з низькорівневою природою примітивів синхронізації

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

– Іншою проблемою є голодування потоків. Голодуванням (англ. starvation) називають ситуацію, в якій кілька потоків мають доступ до спільного ресурсу, але тільки деякі потоки отримують можливість працювати зі спільним ресурсом, інші потоки чекають необмежено довго.

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

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

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

Користуючись м’ютексами, програміст може дуже легко зробити одну з наступних помилок:

– забути виконати операцію Р (див. рис. 1.4, потік Т1);

– виконати операцію Р, але не виконати V (див. рис. 1.4, потік Т1);

– виконати операції Р та V, але над неправильним м’ютексом (див. рис. 1.4, потік Т1).

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

Наприклад, Гоаром були запропоновані монітори ще в 1974 році [19], як спроба структурувати операцію взаємного виключення через поєднання даних та підпрограм в одній сутності – моніторі. Кожна група підпрограм, якій необхідно вирішувати задачу взаємного виключення, включається до монітору. Під час виконання, монітор дозволяє виконання тільки однієї своєї підпрограми. Якщо під час виконання підпрограми монітору інший потік також викликає підпрограму цього самого монітору, цей другий потік блокується до тих пір, доки перший потік не завершить свій виклик.

З точки зору розміру критичної ділянки синхронізація на рівні підпрограм – це не завжди правильне рішення. Критична ділянка завжди повинна бути якнайменшою. Можливі наступні ситуації:

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

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

Класичний приклад такої ситуації – зміна кількості грошей на банківському рахунку. З точки зору об’єктно-орієнтованого дизайну, необхідно визначити клас «Рахунок», та методи «покласти гроші» та «зняти гроші». Але якщо цей клас зробити монітором, то в нас зникає можливість переводити гроші між двома рахунками. Дійсно, взаємне виключення для кожної операції виконується окремо, а між операціями можна спостерігати ситуацію коли в системі з одного рахунку гроші вже зняті, а на інший рахунок ще не зараховані. Тобто, повна сума грошей в системі неправильна.

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

В мові Java зроблена спроба вирішення цих проблем [20] за допомогою введення в мову оператору synchronized. Цей оператор дійсно додає виразності коду та розв’язує вищеназвані проблеми. З іншої сторони він суперечить самій ідеї монітору, так як дозволяє вирішувати задачі взаємного виключення для будь-якої операції на будь-якому моніторі, тим самим відкриваючи шлях до помилок, від яких Гоар прагнув позбутись за допомогою моніторів.

Але з іншої сторони, у самій наявності спільних ресурсів та постановці задачі взаємного виключення є принципова проблема. [21] Пояснимо її суть. Для коректної роботи зі спільними ресурсами необхідно вводити критичні ділянки в паралельну програму. Критичні ділянки виконуються послідовно. Це суперечить меті розпаралелювання. Наявність ділянок, що виконуються послідовно, також накладає принципові обмеження зверху на максимальне значення коефіцієнту прискорення (закон Амдала).

Названі вище проблеми призводять до іншої: складність написання коректних та ефективних програм в даній моделі. Це можна аргументувати тільки непрямо, так як об’єктивні критерії складності сформулювати складно. Серед непрямих індикаторів складності необхідно відмітити наявність великої кількості інструментів для пошуку тупиків та гонок. Існують інструменти статичного аналізу [22, 23], інструменти статичного аналізу на основі анотацій [24], інструменти динамічного аналізу [25] та інші засоби пошуку помилок в паралельних програмах, що використовують потоки та примітиви синхронізації безпосередньо. Великі обсяги досліджень в цьому напрямку та відсутність падіння інтересу до даної тематики свідчать про два факти:

– дана модель широко використовується на практиці, а тому пошук помилок в таких програмах становить інтерес;

– програми, що використовують дану модель, часто мають помилки.

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

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

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

Наприклад, модель з явним створенням потоків дозволяє потоку виконання Т1 створити потік виконання Т3, але делегувати очікування завершення роботи Т3 потоку виконання Т2. Приклад такої взаємодії потоків зображено на рис 1.5.

Рис. 1.5. Неструктуроване створення та завершення потоків

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

– Складність моделі з явним створенням потоків є більшою, ніж необхідно для розробки програм.

– Збільшується складність реалізації інструментів та бібліотек.

– Складність навчання інструментам та бібліотекам необґрунтовано збільшується.

– Це створює додаткові перешкоди та складності для автоматичного статичного аналізу таких програм.

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

Модель Fork/Join для програмування паралельних ЕОМ передбачає явне виділення операцій, що можуть бути виконані паралельно. [26] Програма починає виконуватись в одному потоку виконання. Потік виконання має можливість розгалуження на два потоки (операція fork, з англійської – виделка), після чого операції в обох потоках виконання виконуються паралельно без можливості взаємодії. Коли операції виконані, один з потоків виконання завершується (виконується операція join, з англійської – приєднання), і його результати обчислень стають доступними потоку виконання, який виконував операцію розгалуження.

Реалізації моделі Fork/Join є широко розповсюдженими на сьогоднішній день. Наприклад, вона реалізована в стандартному пакеті java. util. concurrent мови Java [20], для мов С та C++ існує реалізація під назвою Cilk [27], розроблена компанією Intel, для мов С, C++ та Fortran також існує розширення ОреnМР [28].

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

Нажаль, окремі реалізації даної моделі обмежують програміста настільки, що реалізувати ефективний спосіб розв’язання деяких класів задач стає фактично неможливо. Наприклад, ОреnМР 2.0 повноцінно підтримує регулярний паралелізм за допомогою директиви for, але підтримка нерегулярного паралелізму обмежена директивою sections, що дозволяє виконати паралельно фіксований набір операцій в фіксованій кількості потоків. Директива sections має наступні недоліки: