Page 85 - 4868

83 Ошибка! Стиль не определен.

виконання своїм дочірнім вузлам, і так далі.
Специфічні дії, які повинен виконати вузол кожного виду, описані в
лістингу 1.15. Оператори await в даному випадку можна реалізувати у
вигляді циклів активного очікування.

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

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

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

вузол-лист L:
arrive[L] = 1;
<await (continue[L] == 1);>
continue[L] = 0;

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

кореневий вузол R:
<await (arrive[left] == 1);>
arrive[left] = 0;
< await (arrive[right] == 1);>
arrive[right] = 0;