Paralelismo Alexandre Mota (acm@cin.ufpe.br). Paralelismo Representam a execução paralela de dois...

Paralelismo

Alexandre Mota(acm@cin.ufpe.br)

Paralelismo Representam a execução paralela de dois ou

mais processos: fluxos de controles independentes interações eventuais

Utilizados para conectar os componentes de um sistema distribuído: sistemas distribuídos a partir de componentes

seqüenciais sistemas distribuídos a partir de componentes

paralelos

Operadores de Paralelismo Concorrência pode ser expressa

em CSP através de: Composição paralela alfabetizada

P [ X || Y ] Q Composição paralela generalizada

P [| X |] Q Entrelaçamento

P ||| Q

Entrelaçamento Sejam P e Q processos CSP então

P ||| Q P e Q são executados em paralelo

sem sincronização (independentes) Útil para especificar arquiteturas

cliente-servidor Vários clientes e/ou servidores

Entrelaçamento P ||| Q

Oferece os eventos iniciais tanto de P quanto de Q, e espera até que haja uma comunicação

Após a comunicação de um evento a de P (Q), comporta-se como P’ ||| Q (P ||| Q’)

Na presença de mesmo evento, P ||| Q evolução em P ou Q é não-determinística

Processos Paralelos e Seqüenciais Sejam P = c?x:A -> P’ e Q = c?x:B -> Q’.

Então:

P ||| Q = c?x: A B -> if (x A B) then (P’ ||| Q) |~| (P ||| Q’) else if (x A) then (P’ ||| Q) else (P ||| Q’)

Lei Interessante Seja P um processo CSP. Então

P ||| STOP = P Esta lei decorre imediatamente do

slide anterior (step-law) if (x A) then (P’ ||| Q) Onde Q é o processo STOP

Este fato nos permite modelar tolerância a falhas

Cuidado Sejam P e Q processos CSP

recursivos. O processoP = P ||| Q

É infinito estruturalmente e FDR não consegue lidar com o mesmo

Já P = P’ ||| Q pode ser trabalhado sem problemas

Exercício 1. Como modelo uma coleção de

processos independentes entre si, mas que sejam identificáveis individualmente?

2. Como represento um sistema tolerante a falhas onde o sistema só deixa de funcionar quando todos os componentes falharem?

Composição Paralela Generalizada Sejam P e Q processos CSP então

P [| X |] Q P e Q são executados em paralelo

mas sincronizando nos eventos em X: Nos outros eventos semelhante ao

operador de entrelaçamento (independente)

Composição Paralela Generalizada Generaliza outros operadores:

P ||| Q = P [| {} |] Q P [ X || Y ] Q =

(P [| Events \ X |] STOP)[| X Y |] (Q [| Events \ Y |] STOP)

Não pode ser expresso através dos outros operadores

Composição Paralela Generalizada P [| X |] Q

Com A e B sendo respectivamente os eventos iniciais de P e Q, tem-se o seguinte conjunto de eventos:

C =(A \ X) U (B \ X) U (A B X)

Processos Paralelos e Sequenciais

Sejam P = c?x:A -> P’ e Q = c?x:B -> Q’. Então P [| X |] Q = c?x:C -> if (xX) then P’ [|X|] Q’ else if (xAB) then (P’ [|X|] Q) |~| (P [|X|] Q’) else if (xA) then (P’ [|X|] Q) else (P [|X|] Q’)

DeadlockP = (a -> b -> P) [] (b -> a -> P)

Q = (a -> c -> Q) [] (c -> a -> Q)

P [|Events|] Q = a -> STOP

Exercício 1. Como modelo um cliente-

servidor? Por exemplo, um supermercado com

vários caixas e vários servidores de acesso a cartão crédito/visa electron?

Restringindo Concorrência Os operadores de composição

paralela podem ser usados para restringir o comportamento dos processos: P [|X|] STOP comporta-se como P exceto

pela proibição da realização dos eventos em X

P [|X|] Q, onde Q só realiza os eventos em X, restringe o comportamento de P

Associatividade Sejam P, Q e R processos CSP, X e

Y conjuntos de sincronização. Então (P [|X|] Q) [|Y|] R P [|X|] (Q [|Y|] R)

Só quando X = Y esta associatividade é válida (P [|X|] Q) [|X|] R = P [|X|] (Q [|X|] R)

Multiway rendezvous Ocorre quando mais de dois

processos participam de interação em comum

Do ponto de vista de análise pode ser usado sem problemas

No nível de projeto deve ser evitado ou reescrito

O modelo CSP que será usado para mapear em JCSP não deve usar JCSP não suporta

Operadores Indexados Para P [ X || Y ] Q temos

|| i:{1..N} @ [A(i)] P(i) Para P ||| Q temos

||| i:{1..N} @ P(i) Para P [|X|] Q temos

[|X|] i:{1..N} @ P(i)

Cliente-Servidor Indexados Sejam Ci e Sj processos CSP e X um

conjunto de sincronização entre Ci e Sj. Então uma arquitetura cliente-servidor pode ser vista genericamente como (|||i=1..N Ci) [|X|] (|||j=1..K Sj)

Referências Roscoe, A.W. The Theory and

Practice of Concurrency. Prentice-Hall, 1998.

Hoare, C.A.R. Communicating Sequential Processes. Prentice-Hall, 1985.