03 Problema da exclusão mútua

Prévia do material em texto

Programação paralela e distribuída
03 - Problema da exclusão mútua
Prof. Laerte M. Rodrigues
laerte.rodrigues@ifmg.edu.br
Exclusão mútua
I Quando processamos dados compartilhados é importante a
sincronização para o acesso ao dado
I Um dado compartilhado sem o seu devido controle sempre
estará corrompido
I Considere o incremento da varíavel x = 0 dado que x = x+1
I Imagine que n threads irão incrementar a variável x
I Espera-se então x = n
Exclusão mútua
I Devido à acesso mútuo desta variável, o valor final pode ser
menor que
I1 #include <pthread.h>
2 #include <iostream >
3
4 #define NUM_THREADS 1000
5
6 using namespace std;
7
8 void *incremento_thread(void *p) {
9 (*( int*)p)+=1;
10 }
11
12 int main() {
13 pthread_t threads[NUM_THREADS ];
14 int *cont = new int;
Exclusão mútua
15
16 for(int i=0;i<NUM_THREADS;i++) {
17 pthread_create (& threads[i],NULL ,incremento_thread ,cont);
18 }
19
20 for(int i=0;i<NUM_THREADS;i++) {
21 pthread_join(threads[i],NULL);
22 }
23
24 cout << "Final de cont: " << *cont << endl;
25
26 return 0;
27 }
I Na prática, as instruções executadas em nível de máquina
são
Exclusão mútua
I LW $s0, 0($t0)
INC $s0
SW $s0, 0($t0)
I O fato do dado ter a necessidade de ser carregado num
registrador, alterado e posteriormente enviado na memória
principal pode existir consistência
I Considere as threads t0 e t1para o incremento
Exclusão mútua
I
t0 LW $s0, 0($t0)
t0 INC $s0
t1 LW $s0, 0($t0)
t1 INC $s0
t0 SW $s0, 0($t0)
t1 SW $s0, 0($t0)
I Esta situação é comum pois as vezes o sistema deverá
executar (independente do contexto) as operações de forma
ordenada
Exclusão mútua
I Seções do código que necessitam deste tipo de
comportamento são chamados de regiões críticas
I Garantir esta consistência é conhecida como problema da
exclusão mútua
Algoritmo de exclusão mútua
I A interface utilizada a partir deste momento serão as duas
rotinas
I void acquireCS(int tid): Solicita o acesso à região crítica
para a thread em questão
I void releaseCS(int tid): Libera o acesso à região crítica
I Ambos os métodos devem ser chamados na ordem acima
I Quando a thread solicitar o acesso à seção crítica e adquiríla, a
sua execução continuará normalmente
I Quando a região crítica estiver no fim, o acesso à ela deve ser
liberado
Algoritmo de exclusão mútua
I Para fins ilustrativos imagine o seguinte cenário
I n Threads serão criadas
I Cada Thread irá requisitar a CS (Critical Section) para ficar um
tempo aleatório dentro dela
I Após liberar a CS, a mesma irá dormir por um tempo aleatório e
requistar novamente
1 #include <pthread.h>
2 #include <iostream >
3 #include <unistd.h>
4 #include <ctime >
5 #include <cstdlib >
6
7 #define NUM_THREADS 3
8
Algoritmo de exclusão mútua
9 using namespace std;
10
11
12 void acquireCS(int tid) {
13 // CS Algorithm
14 }
15
16 void releaseCS(int tid) {
17 // CS Algorithm
18 }
19
20 void *my_thread(void *p) {
21 int id = *(int*)p;
22
23 while (1) {
24 int tsleep = rand() % 10;
25
26 cout << id << " require CS..." << endl;
Algoritmo de exclusão mútua
27 acquireCS(id);
28 cout << id << " in CS for " << tsleep << " secs" << endl;
29 sleep(tsleep );
30 releaseCS(tid);
31 sleep(rand ()%10);
32 }
33 }
34
35 int main() {
36 pthread_t threads[NUM_THREADS ];
37
38 for(int i=0;i<NUM_THREADS;i++) {
39 pthread_create (& threads[i],NULL ,my_thread ,new int(i));
40 }
41
42 for(int i=0;i<NUM_THREADS;i++) {
43 pthread_join(threads[i],NULL);
44 }
Algoritmo de exclusão mútua
45
46 return 0;
47 }
Algoritmo de Peterson
II Este algoritmo para controle da região crítica é feita por uma
variável compartilhada
I A idéia é similar à de 1 banheiro
I Entra somente 1 por vez
1 bool openDoor;
2
3 void acquireCS(int tid) {
4 while (! openDoor );
5 openDoor = false;
6 }
7
8 void releaseCS(int tid) {
9 openDoor = true;
10 }
Algoritmo de Peterson
II Neste caso, a varíavel openDoor pode não ser atribuída
corretamente
I Uma forma de resolver este problema é criar uma varíavel
que armazena o “interesse” de cada thread em entrar na CS
I Este método, apriori, é feito para 2 threads apenas
1 bool wantCS [] = { false , false };
2
3 void acquireCS(int tid) {
4 wantCS[tid] = true;
5 while(wantCS[1-tid]);
6 }
7
8 void releaseCS(int tid) {
9 wantCS[tid] = false;
10 }
Algoritmo de Peterson
II Ineficiente pois é passível de deadlock
I Uma estratégia também que pode ser utilizada sem afetar a
integridade de variáveis compartilhadas é o uso de turnos
I Cada thread terá a sua “vez” para entrar na CS
1 int turn = 0;
2
3 void acquireCS(int tid) {
4 while(turn%NUM_THREADS != tid);
5 }
6
7 void releaseCS(int tid) {
8 turn ++;
9 }
II Garante a integridade da variável turn
Algoritmo de Peterson
I Somente é alterada quando a CS for liberada
I Passível de inanição
I Para evitar o efeito de inanição para 2 threads, podemos
utilizar os conceitos de “querer” a região crítica + a idéia de
turno
I1 int turn = 0;
2 bool wantCS [] = { false , false };
3
4 void acquireCS(int tid) {
5 int j = 1 - tid;
6 wantCS[tid] = true;
7 turn = j;
8 while(wantCS[j] && turn == j);
Algoritmo de Peterson
9 }
10
11 void releaseCS(int tid) {
12 wantCS[i] = false;
13 }
I Este algoritmo resolve o problema de inaniação do caso
anterior (uma thread que nunca entra na CS)
I Mas não completamente, pois o fato do acesso à CS ser por
“cavalheirismo” é possível de inanição no início da execução
I Em geral os algoritmos de peterson resolvem “bem”
problemas com apenas 2 threads
I Na prática sempre temos mais de 2 threads em execução
Padaria de Lamport
I Um algoritmo muito utilizado para esta estratégia é o
algoritmo da padaria de Lamport (Lamport’s Bakery)
I Utiliza o conceito de “senha”
I A CS é liberada para a Thread com “menor senha”
I Nem sempre é possível garantir a integridade da senha, logo,
utiliza-se a Thread ID para este fim
Padaria de Lamport
1 bool choosing[NUM_THREADS ];
2 int number[NUM_THREADS ];
3
4 // Inicializa a senha de todas as threads
5 for(int i=0;i<NUM_THREADS;i++) {
6 choosing[i] = false;
7 number[i] = 0;
8 }
9
10 void acquireCS(int tid) {
11 // Passo 1: Retirada da senha
12 choosing[tid] = true;
13
14 for(int j=0;j<NUM_THREADS;j++) {
15 if(number[j] > number[tid]) {
16 number[tid] = number[j];
17 }
18 }
Padaria de Lamport
19
20 number[tid ]++;
21 choosing[tid] = false;
22
23 // Passo 2: Verifica se a thread atual Ãc© a "escolhida"
24 for(int j=0;j<NUM_THREADS;j++) {
25 while(choosing[j]); // Thread na porta para retirar senha
26
27 while(number[j]!=0 && (
28 number[j] < number[tid] ||
29 (number[j] == number[tid] && j < tid )))
30 // Esperar liberar CS
31 ;
32 }
33 }
34
35 void releaseCS(int tid) {
36 number[tid] = 0;
Padaria de Lamport
37 }
II As vantagens da padaria de lamport são
I Nenhuma thread irá entrar em inanição
I Todas as threads competem pela CS
I Somente entra aquela com menor senha e de fato “esperando”
I Problema n integridade da senha é resolvido pela thread de
menor ID