Programação Concorrente

Programa¸c˜ao Concorrente e Paralela
Sem´aforos e Monitores

2010.2

Programa¸c˜ ao Concorrente e Paralela

Nota¸c˜ao Andrews: atomicidade e await

para definir a¸c˜oes atˆ omicas, Andrews introduz a nota¸c˜ao e para especificar sincroniza¸c˜ao, Andrews introduz a nota¸c˜ao: await(B)S; que significa que S s´ o deve come¸car a ser executado quando
B for verdadeira, e que S ser´a executado atomicamente

Programa¸c˜ ao Concorrente e Paralela

Exemplo de sincroniza¸c˜ao: produtor/consumidor

tamb´em chamado de problema do buffer limitado diversas variantes buffer limitad´ıssimo!

Programa¸c˜ ao Concorrente e Paralela

Exemplo de sincroniza¸c˜ao: produtor/consumidor int buf, p = 0, c = 0; process Producer { int a[n]; while (p < n) {
< await (p == c);> buf = a[p]; p = p+1;
}
} process Consumer { int b[n]; while (c < n) {
< await (p > c);> b[c] = buf; c = c+1;
}
}
Programa¸c˜
ao Concorrente e Paralela

Implementa¸c˜ao de atomicidade exclus˜ao m´ utua e regi˜ oes cr´ıticas process CS [i = 1 to n] { while (true) { protocolo de entrada; regi~ ao cr´ ıtica protocolo de saida; regi~ ao n~ ao cr´ ıtica }
}
solu¸c˜oes de exclus˜ao m´ utua devem satisfazer as condi¸c˜oes seguintes: 1
2
3
4

exclus˜ao m´ utua ausˆencia de deadlock (ou livelock) ausˆencia de esperas desnecess´arias entrada em algum momento (“eventual”em inglˆes)

como visto na u
´ltima aula!
Programa¸c˜
ao Concorrente e Paralela

Implementa¸c˜ao de espera por condi¸co˜es

complicado no caso geral caso particular: barreiras

Programa¸c˜ ao Concorrente e Paralela

Barreira com coordenador processo extra para coordenar os demais: int arrive[1:n] = ([n] 0), process Worker[i = 1 to n] while (true) { code to implement task arrive[i] = 1;
<await (continue[i] == continue[i] = 0;
}
} process Coordinator { while (true) { for [i = 1 to n] {
<await (arrive[i] == arrive[i] = 0;
}
for [i = 1 to n] continue[i] = 1;
}
}

continue[1:n] = ([n] 0);
{
i;
1);>

1);>

Programa¸c˜ ao Concorrente e Paralela

Como implementar o