Page 105 - 6571

Рисунок 12.1 – Бар’єр з деревовидною структурою

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

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

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

описані в лістингу 15. Оператори await в даному випадку можна
реалізувати у вигляді циклів активного очікування.
Реалізація, наведена в лістингу 15, називається бар’єром з

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

проте він набагато ефективніший при великих значеннях n,
оскільки висота дерева пропорційна величині log n .
2

Лістинг 15 – Бар’єрна синхронізація за допомогою
об’єднуючого дерева

вузол-лист L:
arrive[L] = 1;
<await (continue[L] == 1);>
continue[L] = 0;
проміжний вузол I:

104