1 Programmazione Concorrente e distribuita zBibliografia: zAncillotti- Boari. Principi e Tecniche di...

3

Primitive di concorrenza in architetture fortemente connesse

Scopo: nascondere le primitive di kernel e migliorare la correttezza e la leggibilità del programma

-RCC-Monitor-Path expression

Scopo: nascondere le primitive di kernel e migliorare la correttezza e la leggibilità del programma

-RCC-Monitor-Path expression

Scopo: rendere le primitive di kernel più efficaci, combinando il trsferimento di informazioni e la sincronizz.

-Scambio di messaggi-Pipes-Sockets-Canali-RPC

Scopo: rendere le primitive di kernel più efficaci, combinando il trsferimento di informazioni e la sincronizz.

-Scambio di messaggi-Pipes-Sockets-Canali-RPC

IPC

Primitive di sincronizzazione a basso livello

(kernel)Semafori, eventi

IPC

Primitive di sincronizzazione a basso livello

(kernel)Semafori, eventi

SO con memoria condivisa SO senza

memoria condivisa

4

Linguaggi concorrenti: Linguaggi concorrenti: memoria condivisa vs memoria condivisa vs scambio di messaggiscambio di messaggi

Un programma concorrente scritto in un linguaggio che prevede la memoria condivisa e’ adatto:

quando più processi del linguaggio sono realizzati all’interno di un unico processo di sistema

nei sistemi operativi che forniscono “multithreading”

nei sistemi operativi che permettono la condivisione di moduli (come Unix)

nei sistemi a tempo reale e sistemi di controllo “embedded”

5

Linguaggi concorrenti: Linguaggi concorrenti: memoria condivisa vs memoria condivisa vs scambio di messaggiscambio di messaggi

Un programma concorrente scritto in un linguaggio che prevede la memoria condivisa non e’adatto:

in sistemi multiutente in cui lo spazio degli indirizzi e’ separato e protetto

tra processi residenti su macchine diverse in un’architettura a rete

in sistemi distribuiti in cui e’ desiderabile mantenere un certa flessibilita’ sul loading dei processi (load balancing)

6

Concorrenza: hardware e software

La realizzazione di scambio di comunicazione tra processiprocessi puo’ essere effettuata secondo due modalita’ duali:

in modo proceduraleprocedurale monitor (se esiste condivisione di

memoria) rendez-vous-esteso (se non esiste

memoria condivisa)

con scambio di messaggiscambio di messaggi

7


Struttura di un sistema procedurale

Dominio chiamante

Processo

Call monitor-name

Procedure 1

Procedure 2

Procedure n

MONITOR

DATI

8


Struttura di un sistema a scambio di messaggi

Process

SEND (request)

WAIT (reply)

Process

SEND (request)

WAIT (reply)

Procedura n

Procedura 2

Procedura 1 DATI

Procedureinterne

WAIT

call requested procedure

SEND reply

Process

9

Scambio di messaggi:Classificazione

I meccanismi di comunicazione si possono classificare in base alle seguenti caratteristiche: designazione sorgente e

destinatariosimmetricaasimmetrica

tipo di sincronizzazionesend

• sincrona• asincrona• chiamata di procedura

receive• bloccante• non bloccante

10

Scambio di messaggi:Primitive asincrone

Comunicazione asimmetricaasimmetrica Send non bloccantenon bloccante Receive bloccantebloccante Ogni processo ha una unica unica

coda di messaggicoda di messaggi a lui inviati, gestita FIFO

Send (mes, proc)proc := Receive (mes)


11

WAITSEND

Processo A

Send (B,.. )

Processo B

Wait(., bid)

Primitive asincrone a scambio di Primitive asincrone a scambio di messaggiomessaggio

a livello kernela livello kernel

Le primitive di scambio di messaggi possono essere realizzate a livello di kernel (anche in un’

architettura a memoria condivisa).

12

Semafori vs Scambio di Semafori vs Scambio di messaggimessaggi

(per sistemi con memoria (per sistemi con memoria condivisa)condivisa)

In un kernel a scambio di messaggi il kernel deve gestire il pool dei bufferpool dei buffer, e le code dei messaggicode dei messaggi => maggior complessita’ delle primitive

di kernel maggior memoria a disposizione del

kernel

In un kernel con semafori lo scambio di informazioni tra i processi deve essere fatto a livello delle applicazionilivello delle applicazioni => l’ onere (di tempo d’ esecuzione e di

memoria) e’ a carico dei processi interessati

il kernel e’ piu’ snello

13

Implementazione di Scambio di messaggi

DimensioneDimensione dei messaggi dei messaggi lunghezza fissa a livello kernellunghezza fissa a livello kernel lunghezza variabile nei linguaggi ad lunghezza variabile nei linguaggi ad

alto livelloalto livello

BufferizzazioneBufferizzazione dei messaggi dei messaggi numero massimo della lunghezza numero massimo della lunghezza

delle codedelle code problema del deadlockproblema del deadlock messaggi persimessaggi persi

TecnicheTecniche di gestione della di gestione della memoria memoria messaggi grandi possono essere messaggi grandi possono essere

tenuti in segmenti o pagine passate tenuti in segmenti o pagine passate da sender a receiveerda sender a receiveer

tecniche copy-on-writetecniche copy-on-write

14

Primitive asincrone:Produttori-Consumatori

type tipo_messaggio_ricevuto = (dati,pronto)

type in_mess = record

case specie: tipo_messaggio_ricevuto of

dati : (informazione:T)

pronto: segnale

end

type out_mess: T

15


Process buffer;var coda_dati: <coda di elementi di tipoT>

coda_cons: <coda di nomi di processo>inf: Tcons, proc : processin : in_messout: out_mess

beginwhile true do

beginproc:= Receive (in)case in.specie ofdati: trattadato(informazione)pronto: trattasegnaleend

end

16


trattadato(informazione)

begin

if <coda_cons vuota>

then

put (informazione, coda_dati)

else begin

cons :=get(coda_cons)

out:= in.informazione

Send (out,cons)

end

end

17


trattasegnale

begin

if <coda_dati vuota>

then put(proc,coda_cons)

else

begin

inf :=get(coda_dati)

out:= inf Send (out,proc)

end

end

18


Process produttore_i

var mess: in_mess; contenuto: T;

begin

mess.specie:=dati

while true do

begin

<produci dato>

mess.informazione:= contenuto

Send (mess, buffer)

end

end

19


Process consumatore_j

var mess1: in_mess;

mess2: out_mess;

proc: process;

begin

mess1.specie:=pronto

while true do

begin

Send (mess1, buffer)

proc := Receive (mess2)

<consuma mess2 >

end

end

20


Variante primitiva Receive

si ricevono solo i messaggi che soddisfano la condizione B

se non esiste nessun messaggio che soddisfa la condizione B la Receive e’ bloccante

proc : = Receive (mess) when Bproc : = Receive (mess) when B

21


Problemi Problemi realizzativi delle realizzativi delle primitive con la primitive con la ReceiveReceive selettiva:selettiva:

analoghi a quelli della Regione Critica Condizionale:

il processo bloccato in attesa del verificarsi della condizione logica viene svegliato ogni qualvolta un nuovo messaggio viene inserito in coda => busy form of waiting.

22


Process buffer;var proc1, proc2 : process;

in1, in2: in_mess;out:= out_mess;

beginwhile true do

begin proc1:= Receive (in1)case in1.specie of dati: trattadato(informazione) pronto: trattasegnaleend

end

23


Trattadato (informazione)

begin

proc2:= Receive (in2)

when in2.specie=pronto

out:= in1.informazione

Send (out, proc2)

end

24


trattasegnale

begin

proc2 := Receive (in2)

when in2.specie = dati

out:= in2.informazione Send (out,proc1)

end

25

Variazioni su scambio di Variazioni su scambio di messaggio asincronomessaggio asincrono

Primitive di domanda e rispostaPrimitive di domanda e risposta Piu’ code di messaggi per Piu’ code di messaggi per

processoprocesso PortePorte Canali: Canali: mailbox autonoma (detta anche

global port) con un suo nome proprio Broadcast e multicastBroadcast e multicast

I canali possono fornire una comunicazione “from anyonefrom anyone” e/o “to everyoneto everyone” a tutti i processi di un gruppo definito al momento della configurazione (broadcastbroadcast)

MulticastMulticast : capacita’ di inviare un messaggio a tutti i processi di un dato gruppo

26

Variazioni su scambio di Variazioni su scambio di messaggiomessaggio

Piu’ code di messaggi per Piu’ code di messaggi per processoprocesso porte multiple per processoporte multiple per processo

Porta 0

Porta 1

Porta 2

Porta n

Op. 1

Op. 2

Op. n

Dati

Procedure interne

Risposte per il processo P

Messaggi per P, porta 1

Messaggi per P, porta 2

Messaggi per P, porta n

27


Porte di input e di output con Porte di input e di output con controllo dei tipicontrollo dei tipi

Porta di output Porta di input

Mittente

Send(m)

Ricevente

Wait(m)

Verifica di tipoa tempo di compilazione

Verifica di tipoa tempo di compilazione

Binding e verifica di tipoa tempo di configurazione

28


Una sola porta di input e molte di outputUna sola porta di input e molte di output

Porta di input

Ricevente

Wait(m)

Porta di output

Mittente

Send(m)

Porta di output

Mittente

Send(m)

Porta di output

Mittente

Send(m)

29


Ricevente

Wait(m)

Mittente

Send(m)

Mittente

Send(m)

Ricevente

Wait(m)

Mittente

Send(m)Global

Port

30

Primitive asincrone:porte multiple

Piu’ porteporte di ingresso:

port x: T;

Send (m) to x;

proc := Receive (m) from x;

port x: T;

Send (m) to x;

proc := Receive (m) from x;

31

Primitive asincrone:Comandi con guardia

Comandi con guardieComandi con guardie

<guardia> -----> <istruzione>

guardia: espressione logica +

(guardia logica)primitiva Receive (guardia di input)

32

Primitive asincrone: Comandi con guardia

La guardia viene valutata quando il comando viene eseguito; si possono avere i seguenti risultati:

guardia fallitafallitaguardia validavalidaguardia ritardataritardata

La guardia viene usata all’interno di comandi alternativi e di comandi ripetitivi.

33


comando alternativo

if B1 --> istruzione1�B2 --> istruzione2... � Bn --> istruzionenendSe esistono guardie valide ne viene scelta (in modo non deterministico) una

Se tutte le guardie sono fallite il comando viene abortito

Se tutte le guardie non fallite sono ritardate il processo si blocca in attesa dell’input.

e di comandi ripetitivi.

34


comando ripetitivo

do B1 --> istruzione1 � B2 --> istruzione2... � Bn --> istruzionenend

Il comando viene ripetuto fino a che tutte le guardie falliscono. In questo caso il comando termina.

35


Problemi realizzativi Problemi realizzativi delle primitive con porte delle primitive con porte multiple (e/o guardie):multiple (e/o guardie):

supporto run time deve fornire tante supporto run time deve fornire tante code quante sono le portecode quante sono le porte

comandi con guardia richiedono la comandi con guardia richiedono la realizzazione di risveglio di un realizzazione di risveglio di un processo in attesa su un insieme di processo in attesa su un insieme di porteporte

un processo deve sospendersi su un un processo deve sospendersi su un insieme di porteinsieme di porte

36


porte multiple

Process bufferport p-dati:T

p-controllo: signalvar inf: T

pronto:signalproduttore, consumatore:process

begindo produttore:= � Receive(inf) from p-dati;

consumatore:= Receive(pronto) from p-controllo;

Send (inf) to consumatore.inport consumatore:= � Receive(pronto) from

p-controllo; produttore:= Receive(inf)

from p-dati; Send (inf) to consumatore.inport

od

end

37


porte multiple

Process consumatore_j

port inport: T;

var pronto:signal;

inf: T;

buffer: process;

begin

while true do

begin

Send (pronto) to buffer.p-controllo;

buffer:= Receive (inf) from inport;

<consuma inf >

end

end

38


porte multiple


var inf: T;

begin

while true do

begin

<produci contenuto>

inf:= contenuto

Send (inf) to buffer.p-dati

end

end

39

Send asincrona:Produttori-Consumatori

con buffer limitato

Process bufferport p-dati:T

p-ctrl-p: signal p-ctrl-c: signal

var inf: Tok-p,ok-c,ok-s: signalproduttore, consumatore:processcontatore: integer (init. 0)

begindo

(contatore < N); produttore:= � Receive(ok-p) from p-ctrl-

p; contatore:= contatore + 1

Send (ok-s) to produttore.okport (contatore >0); consumatore:= � Receive(ok-c)

from p-ctrl-c;_ produttore:= Receive(inf)

from p-dati; contatore:= contatore - 1

Send (inf) to consumatore.inportodend

40

Send asincrona:Produttori-Consumatori

con buffer limitato


port okport: signal

var inf: T;

ok-p, ok-s: signal

buffer: process

begin

while true do

begin

<produci contenuto>

inf:= contenuto

Send (ok-p) to buffer.p-ctrl-p;

buffer:= Receive (ok-s) from okport

Send (inf) to p-dati

end

end

41

Send asincronaSistema Pipelining

Tre processi provvedono alla:

lettura di N record da un file

elaborazione dei recordcreazione di un nuovo file

con i record modificati INPUT

ELABORA

OUTPUT

42


Program pipelinevar file1, file2: file of T;

Process Input;var buf: T;begin

reset (file1);for i := 1 to N do

beginRead (file1, buf)Send (buf,Elabora)end

end

43


Process Elabora;var bufin, bufout: T;

proc: process;

beginfor i := 1 to N do begin

proc := Receive (bufin)bufout :=Elabora (bufin)Send (bufout,Output)end

end

44


Process Output;var buf: T;

proc: process;

beginrewrite (file2)for i := 1 to N do begin

proc := Receive (buf)write(file2, buf)end

end

45

Primitive sincrone a scambio di Primitive sincrone a scambio di messaggiomessaggio


SENDWAIT

Processo A

Send (B,.. )

Processo B

Wait(., bid)

46

Primitive sincroneRendez-vous

Stato di un processo che esegue la Send(BO: bloccato per output)

Stato di un processo che esegue la Receive (BI: bloccato per input)

E

BO

E

BI

Invocazione

SendTrasmissione

messaggio Invocazione

Receive

Ricezione

messaggio

47


Mitt

E

BO

BO

E

Ric

BI

BI

BI

E

Posso mandarti un messaggio?

OK! manda

messaggio

48

Primitive sincrone a scambio di Primitive sincrone a scambio di messaggiomessaggio


Le primitive sincrone a livello di kernel non richiedono la gestione dei buffer, ma non sono adatte a tutti i tipi di sincronizzazione tra processi (ad esempio client/server).

ClienteCliente

Send(request)

Wait (replay)

SERVIZIOSERVIZIO

Server

Wait (request)

<Do request>

Send(reply)

Processo di Interfaccia

49


Comunicazione asimmetricaasimmetrica Send bloccantebloccante Receive bloccantebloccante Non esistono code di code di

messaggimessaggi associati ai processi gestiti dal meccanismo di comunicazione



50

Primitive sincroneProduttore- Consumatore

Process buffer;var coda: queue of T;

proc : process;ccpronto, ppronto: boolean (init. false);dati: T;pronto: signal

beginwhile true do

begin proc:= Receive (pronto)case proc of produttore: trattaprod consumatore: trattaconsend

end

51


trattaprodbegin

if <coda piena>

then ppronto := true

else begin

proc := Receive (dati)

if cpronto then begin

Send (dati, cons)

cpronto := false

end

else put(dati,coda)

end

end

52


trattasegnale

begin

if <coda vuota>

then cpronto := true

else begin

dati:=get(coda)

Send (dati,cons)

if ppronto then

begin

proc: =Receive (dati)

put(dati, coda)

ppronto := false

end

end

end

53


Process produttore

var dati: T;

pronto: signal

begin

while true do

begin

<produci dato>

Send (pronto, buffer)

Send (dati, buffer)

end

end

54


Process consumatore

var dati: T;

pronto: signal;

proc: process;

begin

while true do

begin

Send (pronto, buffer)

proc := Receive (dati)

<consuma dati >

end

end

55


con guardie

Process buffertype p-pronto = signal

c-pronto= signalvar coda: queue of T

datipronti: p-prontodatirichiesti: c-prontoproc: processdati : T

begindo

�(coda nonpiena); proc:= Receive(datipronti) _ proc:= Receive(dati)

put (dati, coda);

�(coda nonvuota); proc:=Receive(datirichiesti) get(dati,coda)

Send (dati, consumatore)

odend

56


con guardie (senza uso del segnale datipronti)

Process buffervar coda: queue of T

proc: processdati : Tcpronto:signal

begindo

�(coda nonpiena); proc:= Receive(dati) ; put (dati, coda);

� (coda nonvuota); proc:=Receive(cpronto) get(dati,coda)

Send (dati, consumatore)

odend

57


Process produttore

var dati: T;

begin

while true do

begin

<produci dato>

Send (dati, buffer)

end

end

58

Primitive sincroneProduttore- Consumatoreguardie di input/output

Comandi con guardieComandi con guardie

per primitive sincroneper primitive sincrone

<guardia> -----> <istruzione>guardia: espressione logica

(guardia logica) +primitiva Receive (guardia di input)

oppure primitiva Send (guardia di output)

59


con guardie di input/output

Process buffervar coda: queue of T

proc: processdati : T

begindo

(� coda nonpiena); proc:= Receive(dati) ; put (dati, coda);

�(coda nonvuota); Send (first(coda),

consumatore) aggiorna coda

odend

60



Le guardie di output sono utili nel caso di sistemi client/server con piu’ di un server.

if Send� (richiesta, server1) --> ………;

Send� (richiesta, server2) --> ………;::

Send� (richiesta, serverN) --> ………;

endproc := Receive (risposta)

61



Att!!Att!!

Le guardie di output sono difficili da realizzaredifficili da realizzare e possono portare a deadlock.deadlock.

La validita’ di una guardia di output non garantisce che venga scelta l’istruzione associata alla guardia stessa

62

Primitive sincroneProblema del deadlock


Process Pvar x1,x2:T1; proc: processbegin x1:= valore if

Send � (x1,Q) --> …;� proc:= Receive(x2) -

> …;fi

end

Process Qvar x:T1; y : T2; proc:

processbeginy:= valore if

� proc:= Receive(x) -> Send � (y,R) --> …;fi

end

Process Rvar x:T1; y : T2; proc: processbeginy:= valore if

Send � (x,P) --> …;� proc:= Receive(y) -> …; fi

end

63


con buffer parallelo

Process produttorevar dati: T;begin

while true dobegin

<produci dato>Send (dati, buffer1)

endend

Process consumatorevar dati: T;

proc: process;begin

while true dobegin proc := Receive (dati)<consuma dati >

endend

64


con buffer parallelo

Process buffer-ivar dati: T;

proc: process;begin

while true dobegin proc := Receive (dati)Send (dati, buffer-(i+1)) end

end

Process buffer-Nvar dati: T;

proc: process;begin

while true dobegin proc := Receive (dati)Send (dati, consumatore) end

end

65

Primitive sincronecanali uno-uno

Send (mes, proc)Receive (mes, proc)Send (mes, proc)Receive (mes, proc)

•Comunicazione simmetricasimmetrica•Send bloccantebloccante•Receive bloccantebloccante•Mittente e ricevente devono conoscere il nome del processo con cui vogliono comunicare

66

Send sincronaSistema Pipelining

Program pipelinevar file1, file2: file of T;

Process Input;var buf: T;begin

reset (file1);for i := 1 to N do

beginRead (file1, buf)Send (buf, Elabora)end

end

67

Send sincronaSistema Pipelining

Process Elabora;var bufin, bufout: T;

proc: process;begin

for i := 1 to N do begin

Receive (bufin,Input)bufout :=elabora (bufin)Send (bufout,Output)end

end

68

Rendez- vous estesoRemote Procedure Call

Meccanismo di tipo sincrono in cui il processo che richiede un servizio ad un altro processo rimane sospeso rimane sospeso

fino al completamento del serviziofino al completamento del servizio..

mittente ricevente

chiamata

attesa

accept

Inizio rendez-vous

Fine rendez-vous

Parametri input

Parametri output

69

Rendez- vous estesoRemote Proceure Call

Primitiva dal lato clientecliente:call <servizio> (input, output)call <servizio> (input, output)

Primitiva dal lato servitoreservitore:

remote procedure <servizio> (in <…>out <…>)) var …; begin … end

accept <servizio> (in <…>out <…>))

--> S1, …,Sn

70

Rendez-vous estesoProduttore- Consumatore

Process buffervar buff: array[0..N-1] of T

testa, coda :0..N-1 (init. 0)cont: 0..N (init. 0)

begindo

�(cont < N); accept inserisci (in dato:T) -->

buff[coda]:= dato; end

cont := cont +1 coda := (coda +1) mod N;

�(cont > 0);accept preleva(out dato:T) _-->

dato:= buff[testa]; end cont := cont - 1 testa := (testa +1) mod N;

odend

71


Process produttore-i

var dati: T;

begin

while true do

begin

<produci dato>

call buffer.inserisci (dati)

end

end

72


Process consumatore-j

var dati: T;

begin

while true do

begin

call buffer.preleva(dati)

<consuma dati>

end

end

73

Rendez-vous estesoSegnalazione di sveglia

Process allarmevar tempo: integer

tempo-di-sveglia: array[1..N} of recordrisveglio:integerintervallo:integerend

begindo

� accept tick tempo := tempo + 1;

� accept richiesta-sveglia (in intervallo:integer) <inserimento tempo + intervallo

e intervallo in tempo di sveglia>

�(tempo = tempo di sveglia[1].risveglio);accept svegliami [tempo di sveglia[1].intervallo]; <riordinamento di tempo-di-sveglia>

odend

74

Rendez-vous estesoPipeline

Process Input;var buff: T;

...call Elabora.ricezione (buff)...

end

Process Elabora;var buff: T;

...accept.ricezione (buff) …call Output.ricezione (buff)…

end

Process Output;var buff: T;

...accept ricezione (buff) ...

end

75

Linguaggi di programmazione a scambio di messaggi

CSP

Communicating Sequential Communicating Sequential ProcessesProcesses

non e’ un vero e proprio linguaggio ma piuttosto un modello di interazione tra processi

notazione per la specifica di concorrenza

comunicazione sincrona

ricezione selettiva dei messaggi

76


CSP

Processi

<identificatore> :: <lista comandi><identificatore> :: <lista comandi>

Comando parallelo [<processo> [<processo>

//<processo>//…//<processo>]//<processo>//…//<processo>]

Invio di messaggi (Send) (Send)<destinatario> ! <espressione><destinatario> ! <espressione>

Ricezione di messaggi (Receive)(Receive)<sorgente> ? <variabile><sorgente> ? <variabile>

77


CSP

Schema di sincronizzazioneSchema di sincronizzazioneLa comunicazione puo’ essere stabilita se e La comunicazione puo’ essere stabilita se e solo se:solo se:

a) P contiene un comando di uscita e Q contiene a) P contiene un comando di uscita e Q contiene un comando di ingresso, ognuno specificante un comando di ingresso, ognuno specificante il nome del rispettivo partner il nome del rispettivo partner ((comunicazione simmetrica))

b) la variabile del comando di input e’ b) la variabile del comando di input e’ compatibile con l’ espressione del comando di compatibile con l’ espressione del comando di outputoutput

c) la sincronizzazione e’ a c) la sincronizzazione e’ a rendez-vous estesorendez-vous esteso

P :: P :: … ;… ; Q:: Q:: … ;… ;… … ;; … ;… ;Q!<exp>;Q!<exp>; P?<var> ;P?<var> ;… … ;; … ;… ;

(comandi corrispondenti)(comandi corrispondenti)

78


CSP

Schema di comunicazioneSchema di comunicazione Tra i due processi si individua un canale,

definito dalla terna:– nome mittentenome mittente– nome riceventenome ricevente– tipo del messaggiotipo del messaggio

La sequenzializzazione tra processi e’ data dai comandi alternativi alternativi e ripetitiviripetitivi con guardie: alternativo:

[ <guardia 1> --> <lista comandi1> …

<guardia � n> --> <lista comandi n>]

ripetitivo: * [<guardia 1> --> <lista comandi1> … <guardia � n> --> <lista comandi n>]

79


CSP

Linguaggi ispirati dai CSPLinguaggi ispirati dai CSPOCCAM (transputer)

processi comunicano tramite canali ad ogni canale è associato un tipo di

dato un canale connette due soli

processi: un processo di output ed un processo di input

comunicazione di tipo rendez-vous esteso

processi statici

80


CSP

Linguaggi ispirati dai CSPLinguaggi ispirati dai CSPOCCAM (sintassi)

ogni statement è considerato un processo

il programmatore deve esplicitare l’esecuzione parallela o sequenziale:

SEQ PARstat1 stat1stat2 stat2stat3

comunicazione denotata con ? e ! channel ? var channel ! value

81


CSP

Linguaggi ispirati dai CSPLinguaggi ispirati dai CSPOCCAM

Prodotto di matrici

1 2 3

4 5 6

7 8 9

1 0 2

0 1 2

1 0 0

4 2 6

10 5 18

16 8 30

*

=

82


CSP

Linguaggi ispirati dai CSPLinguaggi ispirati dai CSPOCCAM

Prodotto di matrici

44

11

77 88 99

SINKSINK

RISRIS

RIS

RIS

SRC SRC SRC

1,0,2 0,1,2 1,0,0

ZERO

ZERO

ZERO

2 3

5 6

SINK SINK

4,2,6 3,2,4 3,0,0

10,5,18 6,5,10 6,0,0

16,8,30 9,8,16 9,0,0

83


CSP

Linguaggi ispirati dai CSPLinguaggi ispirati dai CSPMoltiplicatore per matrici:

Prendere un elemento da NORDPassarlo a SUDMoltiplicarlo per valPrendere il valore somma parziale da ESTSommare aggiornare il valoreMandare il risultato OVEST

SSSS

val

NN

EEOO

84


CSP

Moltiplicatore in OCCAMa) WHILE TRUE

SEQnorth ? xsouth ! xeast ?sumsum := sum + a * xwest ! sum

b) north ? x WHILE TRUE

SEQ PAR

south ! xeast ? sumtmp := a * x

PARwest ! sum + tmpnorth ? x

85


DP

Distributed ProcessesDistributed Processes

linguaggio basato su RPC

proposto per applicazioni in tempo reale

un sistema e’ visto come un insieme di processi concorrenti che “vivono insieme” per tutta la durata del sistema

87


ADA

linguaggio studiato soprattutto per applicazioni in tempo reale

notazione per la specifica di concorrenza: task

comunicazione asimmetrica e sincrona

remote procedure call

88


ADA

Schema di comunicazioneSchema di comunicazionedalla parte del server:

accept <servizio> (in <…>out <…>))

do S1, …,Sn end

l’ accept puo’ essere selettiva:

selectaccept entry1 do, …, end

or accept entry2 do, …, end… or accept entryn do, …, endend select

89


ADA

si possono usare guardie logiche:

selectwhen B1 ---> accept

entry1 …, or when B2 --->accept entry2 …, …or when Bn ---> accept entryn …, end select

90


ADA

Schema di comunicazioneSchema di comunicazionedalla parte del client:

le chiamate alle entry del server sono effettuate con la notazione “.”

server. Entryname

e’ possibile una chiamata condizionale: select

<chiamata di una entry>else <comandi>

end select

la chiamata viene effettuata solo se il server e’ in attesa su quella entry

91


ADA

Esempio : Implementazione semaforo

task body SEMAPHORE is count : integerbegin

accept Init (N:integer) do count := Nloop

selectwhen count >0 =>

accept WAIT do count := count -1

endor

accept SIGNAL do count := count +1end

end select end loop

end SEMAPHORE

92


ADA

Moltiplicatore

task body MULTIPLIER isX, Sum: array[1. .n] A: integerNord, Sud, Est, Ovest: task

beginaccept Init (I:integer; N,S,E,O:channel) do

A:= INord:= N; Sud:= S; Est:= E; Ovest:= O

endloop

accept Input (Nord) (I: array[1. .n] ) do X:= IendSud.Output (X)accept Input (Est) (I: array[1. .n] ) do Sum := IendSum := Sum + A*XOvest.Output (Sum)

endend

93

Linguaggi di programmazione ADA

Implementazione del Rendez-vous

selectwhen B1 ---> accept entry1 …,

or when B2 ---> accept entry2 …, …or when Bn ---> accept entryn …, end select

ad ogni accept si associa una coda di processi in attesa (eventualmente un semaforo)

94


Linda

Linda è un linguaggio concorrente radicalmente diverso di precedenti

Nei linguaggi tipo Ada e Occam, i processi comunicano mediante un rendez-vous sincrono; essi sono accoppiati nel tempo e nello spazio:

tempo: sincronia spazio: indirizzo del canale

Linda permette un disaccoppiamento nel tempo e nello spazio; concetto fondamentale è lo spazio delle tuple (TS), che può essere visto come un insieme di sequenze tipate di dati (tupla):

(1, “A”) (integer, character) (1, 2) (integer, integer)

95


Linda

Le primitive di Linda sono: Output (T): aggiunge la tupla t allo

spazio di tuple Input (T): rimuove dallo spazio di

tuple una tupla matching con T, se tale tupla non esiste il processo viene sospeso

Read (T): come il precedente, ma senza rimozione

Try-Input (T): versione non bloccante dell’ Input (T)

Try-Read (T): versione non bloccante della Read (T)

96


Linda

Le tuple di Linda possono contenere parametri formali o attuali e, in maniera analoga alla chiamata di procedura, l’accoppiamento di due tuple corrispondenti, provoca il trasferimento dei valori attuali di una tupla nei parametri formali dell’altra. Es. lo statement di input

Input (I: integer, C: character)

sarà sospeso sino a che lo statement di output Output (1, “A”)avrà inserito la sua tupla a TS

97


Linda

Esempio1: Richiesta di uno specifico servizio da parte

di un processo. Le tuple hanno tre elementi: stringa che identifica richiesta di servizio intero che identifica il tipo di servizio identificativo di un processo

Input (“job”, J: job_id, 24) / Il processo 24 aspetta di

servire/

Output (“job”, 17, 24) / richiesta inviata al processo

24/

Output (“job”, 17, p: Process_id) / richiesta inviata a qualsiasi

processo/

98


Linda

Esempio2: Rendez-vous (tipo ADA):

accept Proc (I: in integer,

C: in character, B: out Boolean)

….

end

call Proc (65, “X”, B) Le tuple hanno i seguenti campi:

stringa contenente il nome del servizio nome del processo chiamante due parametri di input (intero e carattere)

Codice per la chiamata di procedura

Output (“Proc”, 24, 65, “X”) Input (24, B: boolean) Codice per l’accept

Input (“Proc”, Caller: p-id, I: integer, C: character)

Proc (I, C, B) Output (Caller, B)

99


Linda

Moltiplicatore in Lindamain process

Output (‘A’, 1, (1,2,3)) righe prima matrice

Output (‘A’, 2, (4,5,6))Output (‘A’, 3, (7,8,9))Output (‘B’, 1, (1,0,2)) colonne sec.

matriceOutput (‘B’, 2, (1,2,1))Output (‘B’, 3, (1,1,1))

Output (“Next”,1) Next job counter

for I in 1. .3 loopfor J in 1. .3 loop

Input (‘C’, I, J : integer, C: integer)Print C(I,J)

end loopend loop

100


Linda

Moltiplicatore in Lindaworker processes

task body Workers is-----dichiarazioni dati locali -----begin

loopInput (“Next”, Element)Output (“Next”, Element +1)exit when Element > 3*3I := (Element -1)/3 +1 J := (Element -1) mod 3 + 1Row-tuple := Read (`A`, I, V1)Col-tuple := Read (`B`, J` V2)X := prodotto_interno (V1, V2)Output (`C`, I, J, X)

end loopend Workers

1 Programmazione Concorrente e distribuita zBibliografia: zAncillotti- Boari. Principi e Tecniche di...

Documents

Transcript of 1 Programmazione Concorrente e distribuita zBibliografia: zAncillotti- Boari. Principi e Tecniche di...