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

UptoLike

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

Рубрика:

§12 Построение симметричных барьеров

Недостаток барьера с объединяющим деревом в том, что процессы

имеют неодинаковую загрузку: 1) средние узлы загружены больше,

чем листья и корень; 2) кроме того, корень должен ждать, пока

сигналы прибытия пройдут через все дерево.

Симметричный барьер для n процессов строится из пар про-

стых двухпроцессорных барьеров. Пусть каждый процесс по дости-

жении барьера устанавливает собственный флаг; тогда симметрич-

ный барьер для них выглядит так:

# Фрагмент для барьера в W[i]

< await (arrive[i] == 0); >

# эта строка необходима, чтобы W[i] не установил флаг до того,

# как W[j] использовал эту становку флага на предыдуще м

# использовании барьера

arrive[i] = 1;

< await (arrive[j] == 1); >

arrive[j] = 0;

# Фрагмент для барьера в W[j]

< await (arrive[j] == 0); >

# см. предыдущий комментарий

arrive[] = 1;

< await (arrive[i] == 1); >

arrive[i] = 0;

Возникает вопрос: как связать эти двухпроцессорные барьеры

для того, чтобы получить барьер для n процессов.

Один из способов объединения (называемый барьер-бабочка)

представлен на следующем рисунке.