Programa˘c~ao Concorrente e Paralela - PUC-Rionoemi/pcp-10/aula3.pdf · Implementa˘c~ao de...

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


Exemplo de sincronizacao: produtor/consumidor

tambem chamado de problema do buffer limitado

diversas variantes

buffer limitadıssimo!


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;

}

}


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!


Implementacao de espera por condicoes

complicado no caso geral

caso particular: barreiras


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;

}

}


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();


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


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)


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 >


Exclusao Mutua

sem em = 1;

process CS [i = 1 to n] {

P(em);

a = a + 1;

V(em);

}

implementada por um semaforo binario


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!


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


Buffer Limitado - 1 processo de cada tipo


-- uso de semaforos contadores

sem empty = SIZE; sem full = 0;

process Producer {

int data;

while (p < n) {

/* produz dados */

P(empty);



V(full);

}

}

process Consumer {

int data;

while (c < n) {

P(full);



V(empty);

/* consome dados */

}

}


Buffer Limitado - n processos de cada tipo


-- 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);



V(exc); V(full);

}

}

process Consumer {

int data;

while (c < n) {

P(full); P(exc);



V(exc); V(empty);

/* consome dados */

}

}


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


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


Leitores e Escritores

especificacao baseada em < await >


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


Voltando ao Buffer


process Producer {

int data;

while (p < n) {

/* produz dados */

< await ((nxtfree+1)%SIZE != nxtdata)


nxtfree = (nxtfree+1)%SIZE; >

}

}

process Consumer {

int data;

while (c < n) {

< await ((nxtfree != 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...


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>

}


Problema dos leitores e escritores

figuras Andrews


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


Programa˘c~ao Concorrente e Paralela - PUC-Rionoemi/pcp-10/aula3.pdf · Implementa˘c~ao de...

Documents

Transcript of Programa˘c~ao Concorrente e Paralela - PUC-Rionoemi/pcp-10/aula3.pdf · Implementa˘c~ao de...