Na aula de 26/03, discutimos a implementação de barreiras e fiquei de apresentar a parte de barreiras simétricas em 2/4. Em vez disso, vou pedir que vocês implementem uma barreira simétrica neste laboratório.
A idéia da barreira simétrica é a sincronização em vários estágios. Em cada estágio várias duplas de processo se sincronizam. Com uma escolha adequada das duplas, se tivermos n processos (n potência de 2), ao final de log(n) estágios todos os processos podem ter se sincronizado direta ou indiretamente.
Um exemplo de padrão de sincronização é a barreira borboleta, comentada em sala na segunda-feira.
O núcleo do código de barreira que cada processo deve executar em cada estágio, dado por Andrews, é o seguinte:
# codigo de barreira do processo i
for [s=1 to num_stages] {
arrive[i] = arrive[i] + 1;
# determine neighbor j for stage s
while (arrive[j] < arrive[i]) skip;
}
Como nos demais algoritmos discutidos em sala, arrive é um array com uma posição por processo. Observe que agora, em vez de marcar com o valor 1 a chegada na barreira, cada processo incrementa a posição correspondente a ele nesse array. E, em vez de testar se a posição correspondente a seu "par" tem valor 1, ele verifica se o valor do contador do outro é no mínimo igual ao seu. Isso corresponde a testar se o outro já chegou no mesmo estágio de sincronização que ele. Com essa construção, nunca é necessário "desmarcar" um flag.
Execute as seguintes tarefas: