Page 56 - 6571

int m = 0;
co [i = 0 to n-1]
if (a[i]> m) # перевірка значення змінної m
<if (a[i]> m) m = a[i]; >

# повторна перевірка значення змінної m
Ідея полягає в тому, щоб спочатку перевірити нерівність, а

потім, якщо воно виконується, провести ще одну перевірку перед
оновленням значення змінної m. Дана перевірка може здатися

зайвою, але це не так. Наприклад, якщо деякий процес оновив
значення m, то частина інших процесів визначить, що їх значення
a[i] менші нового значення m, і не буде виконувати тіло опера-

тора if. Після подальших оновлень ще менша кількість процесів
визначать, що умова в першій перевірці задовольняє істині. Отже,
якщо перевірки самі по собі виконуються в певному випадковому

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

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

для отримання правильних результатів, якщо процеси і зчитують,
і записують спільні змінні. По-друге, для задання неподільності
дій вводиться використання символів « < » та « > ». По-третє,

описаний метод подвійної перевірки перед оновленням спільної
змінної досить корисний, особливо коли існує ймовірність того,
що перша перевірка дасть помилковий результат, і, отже, друга

перевірка не знадобиться.

Запитання для самоперевірки

1. Що розуміють під поняттям «стан» у паралельній

програмі?
2. Які дії у паралельній програмі називаються неподільними?
3. Що розуміють під історією виконання паралельної

програми?
4. Що таке критична секція у термінах паралельної програми?
5. У чому полягає суть синхронізації за умовою?
6. Що розуміють під властивістю паралельної програми?

55