This repository has been archived by the owner on Aug 10, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
09.02-Barreiras_simétricas
92 lines (67 loc) · 3.63 KB
/
09.02-Barreiras_simétricas
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
Barreiras simétricas
=====================
* Problemas da barreira em árvore
- Os processos são diferentes (nós anteriores fazem mais coisas que
as folhas e as raízes)
- O idela seria ter uma solução que não diferenciasse os processos
(processos diferentes aumentam a chance de não chegar na barreira
na mesma hora)
* Barreiras simétricas
- O objetivo das barreiras simétricas é "simular" a existência
de uma árvore, mas sem ter processos especiais (como folhas
e raízes).
- Não vai ter um processo especial esperando todos os outros
chegarem na barreira.
- Cada processo espera apenas um outro (o que reduz o tempo de
espera)
- Mas serão necessários vários estágios para ter certeza que todos
chegaram à barreira.
* 1ª implementação: 2 processos (correta)
- Vamos começar analisando o problema para 2 processos
/* barreira do Worker i */ : /* barreira do Worker j */
<await (arrive[i] == 0);> : <await (arrive[i] == 0);>
arrive[i] = 1; : arrive[i] = 1;
<await (arrive[j] == 1);> : <await (arrive[j] == 1);>
arrive[j] = 1; : arrive[j] = 1;
- Conseguimos, facilmente, fazer um processo esperar um outro.
O problema será generalizar o número de processos para n != 2.
* 2ª implementação: N processos com estágios (correta, ineficiente)
- Para n != 2, precisaremos variar dependendo do estágio
- As barreiras simétricas variam a depender de como calcular o
processo contra o queal cada um vai se sincronizar a depender do
estágio.
- Borboleta -> distância do processo contra o qual comparar
é 2^(s-1), com 's' o estágio.
Worker 1 2 3 4 5 6 7 8
Estágio 1 ^-----^ ^-----^ ^-----^ ^-----^
Worker 1 2 3 4 5 6 7 8
Estágio 2 ^-----------^ ^-----------^
^-----------^ ^-----------^
Worker 1 2 3 4 5 6 7 8
Estágio 2 ^-----------------------^
^-----------------------^
^-----------------------^
^-----------------------^
- Observações
- Precisa de uma quantidade de processos que seja potência de 2.
- Se não houverem 2^n processos, temos que criar processo
"dummy", que só tenham implementado a execução da barreira.
* 3ª implementação: N processos com estágios (incorreta, eficiente)
- Criar processos "dummy" é ruim. O ideal é que o algoritmo
funcione para qualquer quantidade de processos.
- As barreiras simétricas variam a depender de como calcular o
processo contra o queal cada um vai se sincronizar a depender do
estágio.
- Disseminação -> o cálculo da distância é similar ao da
borboleta, mas usa o MÓDULO da quantidade de processos
Worker 1 2 3 4 5 6
'----.'----.'----.'----.'----.|
.-----------------------------'
Worker 1 2 3 4 5 6
'-----:----.'-----:----.'-----:-
| | : | | |
-:-----.'----:-----.'----:-----.'-
| | | | | |
Worker 1 2 3 4 5 6
- Observações
- NÃO precisa de 2^n processos.