Проблеми асинхронної паралельності

Асинхронне паралельне програмування є досить складним і таким, що приводить до помилок. Найчастіше помилки пов'язані із "забуванням" Р- та V- операцій або застосуванням неправильного семафора. Вони призводять до серйозних наслідків на стадії виконання програм. Із застосуванням моніторів існує небезпека зробити помилку вживання умовних змінних та операцій wait і signal. Аналіз показує, що помилки програмування синхронізації процесів можуть спричинити такі проблеми як несумісні дані та взаємоблокування (DeadLock/LiveLock.)

Несумісні дані

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

- втрачена модифікація даних (lost update problem);

- несумісний аналіз (inconsistent analysis problem);,

- не підтверджена залежність (uncommitted dependency problem).

Втрачена модифікація даних

Цю проблему пояснимо на такому прикладі: хай заробіток інженера становить 1000 гривень. Процес 1 має (поряд з іншим) збільшити заробіток на 50 гривень. Процес 2, що виконується паралельно з першим процесом, має збільшити заробіток на 10%. Залежно від порядку виконання або об'єднання обох процесів при їхньому виконанні, дістанемо різні результати.

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

Несумісний аналіз

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

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

Не підтверджена залежність

Можлива залежність від непідтверджених (uncommiteed) транзакцій - це типова проблема в банках даних. У зв'язку з тим, що транзакція може завершуватись успішно або ні, зміни глобальних даних, що виконуються транзакційно перед її успішним закінченням, завжди дійсні лише з застереженням. Якщо транзакція А вносить зміни в глобальні дані, транзакція В ці дані читає, а транзакція А наприкінці не завершується успішно (фіаско транзакції), то транзакція використовує некоректні дані.

У системах банків даних транзакції імплементуються як "атомарні операції". Транзакція може бути або успішною, або зазнає невдачі. Успішна транзакція оброблюється повністю (commitї), а транзакція, що супроводжується помилками, має бути повністю повернута у вихідне положення (rollback) для перезапуску. У випадку, коли до появи помилки вже виконані деякі операції в банку даних, їх треба зворотним методом повернути у стан, що відповідає стану справ до виконання цієї транзакції. Дотримання концепції транзакцій запобігає появі несумісних даних.

Блокування

Є два типи блокувань: DeadLocks і LiveLocks. DeadLocks описує стан, в якому всі процеси блоковані і не можуть самі вивести себе із стану блокування. У випадку LiveLocks йдеться про блокування активних процесів, тобто тих процесів, які хоч і не є в стані "блоковано", але виконують при цьому, наприклад, операції очікування і не можуть вийти із блокування.

Визначення DeadLocks (взаємне блокування)

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

Взаємні блокування (DeadLocks) з'являються, наприклад, тоді, коли всі процеси блоковані в черзі очікування семафора або умови. Можливе виникнення взаємоблокувань у разі застосування семафорів. Кожний з двох процесів використовує системні ресурси, наприклад термінал (ТЕ) і друкарську машинку (DR), але запити виконуються у формі р- операцій в різній послідовності. У той час, як P₁ запитує спочатку термінал, а потім друкарську машинку,P₂ намагається використати ці системні ресурси в зворотному порядку. Незважаючи на те, що кожний процес веде себе коректно з точки зору його особистих функцій, взаємодія двох процесів може привести до взаємоблокування (DeadLocks). Це трапляється не завжди, а тільки тоді, колиP₁ зайняв термінал, аP₂ - друкарську машинку. ТодіP₁ чекає в своїй Р- операції на друкарську машинку, яку зайнявP₂ і звільнить її лише тоді, коли він зможе зайняти термінал, який в свою чергу зайнятий процесомP₁. Тим самим обидва процеси опинились у взаємозалежності, із якої не зможуть звільнитись. Це означає, що настало взаємоблокування (DeadLocks). На рис.В.1 показано небезпеку взаємоблокування у вигляді програми.

Рис. В.1 Небезпека взаємоблокування

Передумови, за яких може з'явитись взаємоблокування:

1. Операційні засоби можуть використовуватися тільки на основі виключного права (ексклюзивно).

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

3. Операційні засоби не можуть забиратися у процесів в примусовому порядку.

4. Існує циркулярний ланцюг процесів, так що кожний процес використовує операційний ресурс, який замовляється наступним процесом цього ланцюга.

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

Розгляньмо приклади того, як не допустити передумов блокувань.

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

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

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

Балансування завантаження

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

У випадку простої моделі планування (scheduling - модель) застосовується статичний розподіл процесів між процесорами. Тобто на момент виконання не відбувається пересилки процесів, що вже розподілені, на інші процесори, що в даний момент менше завантажені.Наприклад, на початок обчислювальних процедур дев'ять процесів рівномірно розподілені між трьома наявними процесорами. Під час виконання всі процеси другого і третього процесорів блокуються в черзі очікування, а всі процеси першого процесора залишаються активними. Потужність паралельної системи падає до можливостей одного процесора, тоді як у даній ситуації можна було б продовжити паралельне виконання процесів.

Щоб уникнути подібних втрат продуктивності, розроблено інші моделі планування процесів, які забезпечують динамічний розподіл процесів між процесорами на момент їх виконання (dynamic load balancing) за допомогою перегрупування процесів, що були закріплені за певними процесорами (process migration) залежно від їхнього завантаження відносно деякого порогового числа (thres hold). Існують три принципово різних методи керування центральною операцією "міграції процесів".

1. Ініціатива адресата: процесори з малим завантаженням дають запит на обробку інших процесів. Цей метод ефективний у разі високого завантаження системи.

2. Ініціатива відправника: процесори з високим завантаженням роблять спробу віддати частину процесів, що їм підпорядковані. Цей метод ефективний у випадку невисокого завантаження системи.

3. Гібридний метод: перехід від ініціативи адресата до ініціативи відправника і навпаки залежно від глобального завантаження системі.

Переваги та недоліки методів балансування завантаження.

“+”: Досягається більше завантаження процесорів і не втрачається можлива паралельність.

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

“-“: Виникає високий обсяг функцій керування завантаженням процесорів.

“-“: Перенесення деякого процесу з одного процесора на інший, менше завантажений процесор ("міграція процесів"). Це дорога операція і має застосовуватися тільки для процесів, що виконуються довгий час; але дану властивість процесу не можна встановити на момент початку його виконання без спеціальної допоміжної інформації.

“-“: Усі методи балансування вступають в роботу надто пізно, а саме тоді, коли вже суттєво розладилося рівномірне завантаження процесорів. Деяке "передбачене балансування" неможливо реалізувати без допоміжної інформації про реальні витрати часу на виконання процесів.

“-“: У разі повного паралельного системного завантаження будь-яке його балансування втрачає сенс. Загальний обсяг ресурсів для балансування завантаження в даному випадку спричинить необгрунтовані витрати машинного часу.

 

Додаток Г