Page 99 - 6571

9. У чому полягає перевага алгоритму поліклініки над алго-
ритмом квитка?
10. За яких умов паралельна програма переходить у стан го-
нок?

ЛЕКЦІЯ 12
МЕХАНІЗМ БАР’ЄРНОЇ СИНХРОНІЗАЦІЇ ПРОЦЕСІВ

12.1 Спільний лічильник

Багато задач можна вирішити за допомогою ітераційних ал-

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

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

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

алгоритму полягає у реалізації тіла для кожної ітерації за
допомогою оператора co. Якщо не враховувати властивість

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

while (true) {
co [i = 1 to n]
код рішення задачі i;
oc
}

На жаль, даний підхід досить неефективний, оскільки
оператор co породжує n процесів на кожній ітерації. Створити і
знищити процеси набагато дорожче, ніж реалізувати їх

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

ітерації.
process Worker[i = 1 to n] {

98