Page 46 - 4868

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

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

значення змінної m, яка дорівнює нулю). Отже, всі процеси будуть
намагатися оновити значення змінної m. Апаратне забезпечення пам’яті
виконуватиме оновлення в порядку деякої черги, оскільки запис елемента в
пам’ять – це неподільна операція. Кінцевим значенням змінної m буде
значення a[i], присвоєне їй останнім процесом.
У програмі, представленій вище, зчитування і запис змінної m є
окремими операціями. Для роботи з таким рівнем паралельності необхідно
використати синхронізацію для поєднання окремих дій в одній неподільній
операції. Це демонструє наступна програма.
int m = 0;
co [i = 0 to n-1]
<if (a[i] > m) m = a[i];>

Кутові дужки в цьому фрагменті коду вказують, що кожен оператор if
виконується як неподільна операція, тобто перевіряє поточне значення m і
відповідно з умовою оновлює його в одній неподільній дії.
На жаль, остання програма – це майже те ж саме, що і послідовне
рішення. У послідовній програмі елементи масиву a перевіряються у
встановленому порядку – від a[0] до a[n-1]. В останній програмі елементи
масиву a перевіряються в довільному порядку, оскільки у довільному
порядку виконуються процеси. Але через синхронізацію перевірки все ще
виконуються по одній.

Основнезавдання – забезпечити, щоб оновлення змінної m були
неподільними операціями, а значення змінної m було дійсно максимальним.
Припустимо, що порівняння виконуються паралельно, але оновлення даних
виконуються по одному, як в наступній програмі.
int m = 0;
co [i = 0 to n-1]
if (a[i]> m)
<m = a[i];>

Результат виконання даної програми насправді буде тим же, що і першої
паралельної програми. Кожен процес здатний порівняти своє значення
елемента з масиву a із змінною m і потім обновити значення змінної m. І хоча
оновлення m є неподільною операцією, проте така неподільність фактично
забезпечується на апаратному рівні.
Отже, вихід полягає в поєднанні останніх двох програм. Можна
безпечно виконувати паралельні порівняння, оскільки це дії, які тільки
зчитують змінні. Але необхідно забезпечити, щоб при завершенні програми
значення m дійсно було максимальним. Це досягається в наступній програмі.

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