Barreira de sincronização
Na programação simultânea , uma barreira de sincronização garante que um certo número de tarefas tenha passado por um ponto específico. Portanto, cada tarefa que chega a essa barreira terá que esperar até que o número especificado de tarefas tenha chegado a essa barreira.
Algoritmo de barreira única
Para obter este primeiro algoritmo de barreira de sincronização, você precisa de dois semáforos e uma variável:
- Um semáforo MUTEX(inicializado em 1) protegendo a variável.
- Um semáforo ATTENTE(inicializado em 0) usado para colocar as tarefas em espera.
- Uma variável Nb_Att(inicializada em 0) que permite contar o número de tarefas que já chegaram na barreira de sincronização.
Também é necessário definir a constante Nque indica o número de tarefas que devem chegar à barreira antes de abri-la.
Barriere :
P(MUTEX)
Nb_Att++
SI Nb_Att==N ALORS
POUR I DE 1 à N-1 FAIRE
V(ATTENTE)
FIN POUR
Nb_Att=0
V(MUTEX)
SINON
V(MUTEX)
P(ATTENTE)
FIN SI
Limitações do algoritmo
Este primeiro algoritmo está correto, mas não implementa uma barreira cíclica. Se as tarefas tiverem que ser sincronizadas várias vezes com uma barreira, será necessário usar 2 barreiras diferentes de forma alternativa. O cenário a seguir demonstra, usando um exemplo de contador, que a mesma barreira não pode ser reutilizada imediatamente:
- Um processo A entre os primeiros N-1 é pausado (por um mecanismo de preempção ) entre o V (MUTEX) e o P (WAIT) e não irá retomar o controle por um certo tempo.
- Todos os processos chegam à barreira. Quando o último processo chega, o semáforo WAIT é igual a - (N-2) (porque A não executou sua operação P (WAIT) ).
- O último processo a chegar executa N-1 vezes V (HOLD) e libera o mutex. O semáforo WAIT é então igual a 1.
- Um processo B é executado rapidamente e chega à segunda barreira de sincronização.
-
B executa o código de barreira e executa um P (HOLD) . Esta operação não é bloqueadora porque o semáforo ATTENTE é igual a 1 (o processo A ainda não realizou o P (WAIT) da primeira barreira).
O processo B terá, portanto, cruzado a segunda barreira de sincronização antes que todos os outros processos a tenham alcançado.
Algoritmo de barreira múltipla
Para remediar o problema mencionado acima e implementar uma barreira cíclica, é necessário introduzir um segundo semáforo que permitirá ao último processo aguardar até que todos os outros processos tenham realizado seu P (WAIT) antes de liberar o mutex. Deve, portanto:
- Um semáforo MUTEX(inicializado em 1) protegendo a variável.
- Um semáforo ATTENTE(inicializado em 0) tornando possível colocar as N-1ª tarefas em espera.
- Um semáforo PARTI(inicializado em 0) permitindo que a última tarefa seja colocada em espera.
- Uma variável Nb_Att(inicializada em 0) que permite contar o número de tarefas que já chegaram na barreira de sincronização.
Barriere :
P(MUTEX)
Nb_Att++
SI Nb_Att==N ALORS
POUR I DE 1 à N-1 FAIRE
V(ATTENTE)
FIN POUR
POUR I DE 1 à N-1 FAIRE
P(PARTI)
FIN POUR
Nb_Att=0
V(MUTEX)
SINON
V(MUTEX)
P(ATTENTE)
V(PARTI)
FIN SI
Portanto, se um processo estiver sendo executado mais rápido do que os outros, não será possível bloquear o mutex até que todos os processos tenham terminado.
Exemplos de uso
Barreiras de sincronização podem ser usadas para
- Garanta que uma ou mais tarefas executaram uma operação específica.
- Espere até que um conjunto de tarefas termine
Veja também