Page 84 - 4868

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

код рішення задачі i;
arrive[i] = 1;
<await (continue[i] == 1);>
continue[i] = 0
}
}
process Coordinator {
while (true) {
for [i = 1 to n] {
< await (arrive[i] == 1);>
arrive[i] = 0;
}
for [i = 1 to n] continue[i] = 1;
}
}
Хоча в програмі 1.14 бар’єрна синхронізація реалізована таким чином,

що конфлікти звернення до пам’яті не виникають, проте у даного рішення є
дві небажані властивості. По-перше, потрібен додатковий процесор.
Синхронізація з активним очікуванням ефективна, якщо тільки кожен процес
виконується на окремому процесорі, так що процесу Coordinator потрібен
свій власний процесор. Проте, можливо даний процесор доцільніше було б
використовувати для іншого робочого процесу.
Другий недолік використання керуючого процесу полягає в тому, що час
виконання кожної ітерації процесу Coordinator, і, отже, кожного
екземпляра бар’єрної синхронізації пропорційний числу процесів Worker. У
ітераційних алгоритмах дуже часто всі робочі процеси мають ідентичний
код. Це означає, що якщо кожен робочий процес виконується на окремому
процесорі, то всі вони підійдуть до бар’єра приблизно в один і той же час.
Таким чином, всі прапорці arrive будуть встановлені практично одночасно.
Однак процес Coordinator перевіряє прапорці в циклі, по черзі очікуючи,
коли буде встановлений кожен із них.

12.3. Бар’єр з об’єднуючим деревом
Обидві проблеми можна вирішити, об’єднавши дії керуючого і робочих
процесів так, щоб кожен робочий процес був одночасно і керуючим.
Організуємо робочі процеси в дерево (рис. 1.15). Сигнал про те, що процес
підійшов до бар’єра (прапорець arrive[i]), відсилається вгору по дереву, а

сигнал про дозвіл продовжити виконання (прапорець continue[i]) – вниз
по дереву.
Вузол робочого процесу очікує, коли до бар’єра підійдуть його дочірні
процеси, після чого повідомляє батьківському вузлу про те, що він також
підійшов до бар’єру. Коли всі дочірні процеси кореневого вузла підійдуть до
бар’єра, то це означатиме, що всі інші робочі вузли також підійшли до
бар’єра. Тоді кореневий вузол зможе повідомити дочірнім процесам, що вони
можуть продовжити виконання. Ті, у свою чергу, дозволять продовжити