Page 82 - 4868

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

будь-який з процесів знову спробує її збільшити.
Дану проблему можна вирішити за допомогою двох лічильників, один з
яких збільшується до 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);>
Але в такому випадку знову виникають конфлікти звернення до пам’яті,
причому таке рішення є досить неефективним, оскільки суму елементів
arrive[i] тепер постійно обчислює кожен очікуючий своєї черги процес

Worker.
Обидві проблеми (конфлікти звернення до пам’яті і обнулення масиву)
можна вирішити, використавши додатковий набір спільних значень і
додатковий процес Coordinator. Нехай кожен процес Worker замість того,
щоб підсумувати елементи масиву arrive, очікує, доки єдине логічне
значення не стане «істина». Нехай continue[1: n] – додатковий масив
цілих чисел з нульовими початковими значеннями. Після того як процес
Worker[i] присвоїть значення 1 елементу масиву arrive[i], він
переводиться в режим очікування до того часу, доки значенням змінної
continue[i] не стане 1.