Post on 11-Aug-2020
transcript
Programacao Concorrente e ParalelaSemaforos e Monitores
2010.2
Programacao Concorrente e Paralela
Notacao Andrews: atomicidade e await
para definir acoes atomicas, Andrews introduz a notacao 〈e〉para especificar sincronizacao, Andrews introduz a notacao:
〈await(B)S ; 〉
que significa que S so deve comecar a ser executado quandoB for verdadeira, e que S sera executado atomicamente
Programacao Concorrente e Paralela
Exemplo de sincronizacao: produtor/consumidor
tambem chamado de problema do buffer limitado
diversas variantes
buffer limitadıssimo!
Programacao Concorrente e Paralela
Exemplo de sincronizacao: 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;
}
}
Programacao Concorrente e Paralela
Implementacao de atomicidade
exclusao mutua e regioes 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 }
}
solucoes de exclusao mutua devem satisfazer as condicoesseguintes:
1 exclusao mutua2 ausencia de deadlock (ou livelock)3 ausencia de esperas desnecessarias4 entrada em algum momento (“eventual”em ingles)
como visto na ultima aula!
Programacao Concorrente e Paralela
Implementacao de espera por condicoes
complicado no caso geral
caso particular: barreiras
Programacao Concorrente e Paralela
Barreira com coordenador
processo extra para coordenar os demais:int arrive[1:n] = ([n] 0), continue[1:n] = ([n] 0);
process Worker[i = 1 to n] {
while (true) {
code to implement task i;
arrive[i] = 1;
<await (continue[i] == 1);>
continue[i] = 0;
}
}
process Coordinator {
while (true) {
for [i = 1 to n] {
<await (arrive[i] == 1);>
arrive[i] = 0;
}
for [i = 1 to n]
continue[i] = 1;
}
}
Programacao Concorrente e Paralela
Como implementar o await com protocolos de EM?
< S > implementado por
CSenter();
S;
CSexit();
e < await(B)S ;>? podemos testar a condicao dentro daregiao crıtica:
CSenter();
while (!B) (???)
S;
CSexit();
Programacao Concorrente e Paralela
await com protocolos de exclusao mutua
... se a alteracao da condicao B depender de outro processo entrarna regiao crıtica, nada feito...
podemos tentar:
CSenter();
while (!B) (CSexit; CSenter;)
S;
CSexit();
mas teremos grande disputa pela EM...
aqui poderıamos reaplicar o conceito de back-off
Programacao Concorrente e Paralela
Semaforos
exclusao mutua e sincronizacao por condicao
Dijkstra, E. W. 1968. The structure of the“THE”-multiprogramming system. Commun. ACM 11, 5(May. 1968), 341–346.proposto para sincronizacao entre processos do sistemaoperacional!
material baseado no Cap. 4 de FMPDP (Andrews)
Programacao Concorrente e Paralela
Definicao
sintaxe:
declaracao e inicializacao:
sem s;
sem lock = 1;
sem forks[5];
cada semaforo e associado a um valor inteiro nao negativomanipulacao: operacoes P e V
P(s): < await (s > 0) s = s - 1; >
V(s): < s = s - 1 >
semaforos binarios e semaforos geraispropriedades relativas a liveness dependem de especificacao de< await >
Programacao Concorrente e Paralela
Exclusao Mutua
sem em = 1;
process CS [i = 1 to n] {
P(em);
a = a + 1;
V(em);
}
implementada por um semaforo binario
Programacao Concorrente e Paralela
Cooperacao
Voltando ao problema do buffer limitadıssimo:int buf;
sem empty = 1, full = 0;
process Producer {
int dados;
while (p < n) {
/* produz dados */
P(empty);
buf = dados;
V(full);
}
}
process Consumer {
int dados;
while (c < n) {
P(full);
dados = buf;
V(empty);
/* consome dados */
}
}
exemplo de split binary semaphoreProgramacao Concorrente e Paralela
Cooperacao [cont]
e se tivermos varios produtores e varios consumidores?int buf;
sem empty = 1, full = 0;
process Producer {
int data;
while (p < n) {
/* produz dados */
P(empty);
buf = data;
V(full);
}
}
process Consumer {
int data;
while (c < n) {
P(full);
data = buf;
V(empty);
/* consome data */
}
}
ainda funciona!
Programacao Concorrente e Paralela
Cooperacao [cont]
e se tivermos uma estrutura de dados mais complexa?
int buf[SIZE]; int nxtfree = 0; int nxtdata = 0;
process Producer {
int data;
while (p < n) {
/* produz dados */
buf[nxtfree] = data;
nxtfree = (nxtfree+1)%SIZE;
}
}
process Consumer {
int data;
while (c < n) {
data = buf[nxtdata];
nxtdata = (nxtdata+1)%SIZE;
/* consome dados */
}
}
um processo de cada tipo x varios processos de cada tipo
Programacao Concorrente e Paralela
Buffer Limitado - 1 processo de cada tipo
int buf[SIZE]; int nxtfree = 0; int nxtdata = 0;
-- uso de semaforos contadores
sem empty = SIZE; sem full = 0;
process Producer {
int data;
while (p < n) {
/* produz dados */
P(empty);
buf[nxtfree] = data;
nxtfree = (nxtfree+1)%SIZE;
V(full);
}
}
process Consumer {
int data;
while (c < n) {
P(full);
data = buf[nxtdata];
nxtdata = (nxtdata+1)%SIZE;
V(empty);
/* consome dados */
}
}
Programacao Concorrente e Paralela
Buffer Limitado - n processos de cada tipo
int buf[SIZE]; int nxtfree = 0; int nxtdata = 0;
-- uso de semaforos contadores e de exclus~ao mutua
sem empty = SIZE; sem full = 0; sem exc = 1;
process Producer {
int data;
while (p < n) {
/* produz dados */
P(empty); P(exc);
buf[nxtfree] = data;
nxtfree = (nxtfree+1)%SIZE;
V(exc); V(full);
}
}
process Consumer {
int data;
while (c < n) {
P(full); P(exc);
data = buf[nxtdata];
nxtdata = (nxtdata+1)%SIZE;
V(exc); V(empty);
/* consome dados */
}
}
Programacao Concorrente e Paralela
Outros exemplos
filosofos
canibais e cozinheiros
estudo de padroes de problemas
em alguns casos o desenho de uma solucao por semaforos ebastante complicado
macacos e cipoproblema de leitores e escritores
escritores precisam de acesso exclusivo ao recursoleitores podem acessar o recurso concorrentemente com outrosleitores
Programacao Concorrente e Paralela
Passagem de Bastao
em alguns casos o desenho de uma solucao por semaforos ebastante complicado
exemplo: problema de leitores e escritores
escritores precisam de acesso exclusivo ao recursoleitores podem acessar o recurso concorrentemente com outrosleitores
Programacao Concorrente e Paralela
Leitores e Escritores
especificacao baseada em < await >
Programacao Concorrente e Paralela
A tecnica de passagem de bastao
Criamos:
um semaforo e associado a entrada nos comandos atomicos(< await(B)S ;> ou < S :>)
um semaforo sb e um contador db para cada condicao Bdistinta (inicializados com 0)
Cada < await(B)S ;> fica associado ao seguinte codigo:
P(e)
if (!B) { db++; V(e); P(sb);}
S;
SIGNAL
onde o trecho “SIGNAL” corresponde a passagem de bastao paraoutros processos que estejam em espera
Programacao Concorrente e Paralela
Voltando ao Buffer
int buf[SIZE]; int nxtfree = 0; int nxtdata = 0;
process Producer {
int data;
while (p < n) {
/* produz dados */
< await ((nxtfree+1)%SIZE != nxtdata)
buf[nxtfree] = data;
nxtfree = (nxtfree+1)%SIZE; >
}
}
process Consumer {
int data;
while (c < n) {
< await ((nxtfree != nxtdata)
data = buf[nxtdata];
nxtdata = (nxtdata+1)%SIZE; >
/* consome dados */
}
}Programacao Concorrente e Paralela
Solucao com Passagem de Bastao para Prod/Cons
mais complicada que a “ad-hoc”
... porem derivada de forma metodica...
Programacao Concorrente e Paralela
Problema da Barreira
int chegaram[NUMITERS] = {false,...,false}
process trab [i = 1 to n] {
...
for (iter = 0; iter < NUMITERS; iter++) {
trabalha;
barreira(iter);
}
}
void barreira (int iter) {
<chegaram[iter]++>
<await chegaram[iter] == NUMPROCS>
}
Programacao Concorrente e Paralela
Problema dos leitores e escritores
figuras Andrews
Programacao Concorrente e Paralela
Exercıcio
broadcast atomico:Imagine que existe um buffer com n posicoes. Um produtorpode depositar mensagens somente quando houver umaposicao livre e uma posicao so pode ser reutilizada quandotodos os C consumidores tiverem lido a mensagem. Cadaconsumidor deve receber as mensagens na ordem em queforam depositadas, mas pode faze-lo no momento em quedesejar.
programar com e sem passagem de bastao e mandar por emailpara 8/9
Programacao Concorrente e Paralela