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

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

БАРЬЕРНАЯ СИНХРОНИЗАЦИЯ С ПОМОЩЬЮ
БИНАРНОГО ДЕРЕВА (БАРЬЕР С ОБЪЕДИНЯЮЩИМ
ДЕРЕВОМ)
ROOT : < await (arrive[left] == 1); >
arrive[left] = 0;
< await (arrive[right] == 1); >
arrive[right] = 0;
continue[left = 1; continue[right] = 1;
INTERMEDIATE :
< await (arrive[left] == 1); >
arrive[left] = 0;
< await (arrive[right] == 1); >
arrive[right] = 0;
arrive[I] = 1;
< await (contineu[I] == 1); >
continue[I] = 0;
continue[left] = 1; continue[right] = 1;
LIST : arrive[L] = 1;
< await (continue[L] == 1); >
continue[L] = 0;
Замечание. Каждый из процессов (узлов дерева) может выполнять
также предписанную для него работу (здесь она не описана).
Легко видеть, что здесь используется столько же переменных,
сколько и в централизованной версии барьера, но высота дерева
пропорциональна log
2
n. Можно сделать программу еще эффектив-
нее, если корневой узел будет посылать единственное сообщение о
возможности продолжения работы всем остальным узлам (напри-
мер, флаг continue), а для сбрасывания флага можно провести
двойную буферизацию: иметь два флага и переключаться между
ними или изменять смысл флага на четных и нечетных итерациях
(0 на 1 и 1 на 0).
66

Страницы