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

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

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

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

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

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

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

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

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

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

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

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

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

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

Додаток Г