Теория распараллеливания и синхронизация. Демьянович Ю.К - 71 стр.

UptoLike

Составители:

Рубрика:

Итак, первоначально end[i] указывает на следующие элементы

списка, на первом этапе — на элементы, находящиеся на расстоя-

нии в две связи, на втором этапе — в 4 связи и т.д.(см. рис. 6).

Рис. 6. Схема изменений связей

Эта схема реализуется следующей программ ой.

ПОИСК КОНЦА ПОСЛЕДОВАТЕЛЬНОГО СПИСКА

int link[n], end[n];

process Find[i = 0 to n − 1] {

int new, d = 1;

end[i] = link[i]; # инициализация элементов end

barrier(i); # первоначальный барьер

while (d < n) {

new = null; # проверяем, нужно ли обновление end[i]

if (end[i]! = null and end[end[i]]! = null)

new = end[end[i]]; # присваивание для new

barrier(i); # барьерная синхронизация: нельзя обновлять

# end[i] раньше времени: нужно ждать

# другие процессы

if (new! = null) # обновить end[i]