Page 101 - 6571

Дану проблему можна вирішити за допомогою двох
лічильників, один з яких збільшується до n, а інший зменшується
до 0. Їхні ролі міняються місцями після кожного етапу. Проте,

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

процес припиняє своє виконання, то він безперервно перевіряє
значення змінної count. У гіршому випадку n-1 процесів
очікуватимуть, поки останній процес не досягне бар’єру. У
результаті виникне серйозний конфлікт звернення до пам’яті,

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

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

бути відносно малим.

12.2 Прапорці та управляючі процеси

Одним із способів уникнення конфліктів звернення до

пам’яті є реалізація лічильника count за допомогою n змінних,
значення яких підсумовуються між собою. Нехай, наприклад,
існує масив цілих чисел arrive[1: n] з нульовими
початковими значеннями. Замінимо операцію інкременту

лічильника count в програмі операцією присвоєння
arrive[i] = 1. Тоді глобальним інваріантом буде наступний

предикат.
count == (arrive[l] + ... + arrive[n])

Конфліктів звернення до пам’яті можна уникнути, якщо

елементи масиву arrive зберігаються в різних рядках кеш-
пам’яті.
У програмі залишилося реалізувати оператор await і

обнулити елементи масиву arrive в кінці кожної ітерації. Одна
із реалізацій оператора await може мати наступний вигляд:

<await ((arrive[1] + ... + arrive[n]) == n);>

100