1

Programmazione Concorrente:insieme delle tecniche, metodologie e strumentiper il supporto all'esecuzione di sistemi software

composti da insiemi di attivita` svoltesimultaneamente.

2

Programmazione Concorrente:le origini

• La programmazione concorrente nasce negli anni 1960nell’ambito dei sistemi operativi.

• Introduzione dei canali o controllori di dispositivi :consentono l’esecuzione concorrente di operazioni di I/O edelle istruzioni dei programmi eseguiti dall'unita` dielaborazione centrale.

• Comunicazione tra canale ed unità centrale tramite il segnaledi interruzione.

• Come conseguenza dell’interruzione, parti di un programmapossono essere eseguite in un ordine non predicibile (->interferenze su variabili comuni).

3

• Successivamente furono introdotti i sistemi multiprocessore.Inizialmente costosi, ora ampiamente diffusi. Macchine massivelyparallel processors.

• I sistemi multiprocessore consentono a differenti processiappartenenti alla stessa applicazione di essere eseguiti in parallelo equindi all’applicazione di essere eseguita più velocemente.

Problemi:- Come suddividere un’applicazione in processi?- Quanti processi utilizzare?- Come garantire la corretta sincronizzazione delle loro operazioni?

Queste decisioni dipendono dal tipo di architettura hardware e daltipo di applicazione.

4

Tipi di architettura: Single processor

Primary memory

Level 2 cache

Level 1 cache

CPU

5

Shared- Memory Multiprocessors

Memory Memory

Interconnection network

. . .

Cache

CPU

Cache

CPU

. . .

6

• In sistemi a multiprocessore con un numero ridotto di processori (da2 a 30 circa), la rete di interconnessione è realizzata da un memorybus o da crossbar switch.

– UMA (Uniform Memory Access). Tempo di accesso uniforme daogni processore ad ogni locazione di memoria.

– Si chiamano anche symmetric multiprocessors (SMP).

• In sistemi con un numero elevato di processori (decine o centinaia) lamemoria è organizzata gerarchicamente (per evitare la congestionedel bus).– La rete di interconnessione è un insieme di switches e memorie

strutturato ad albero. Ogni processore ha memorie che sono piùvicine ed altre più lontane.

– NUMA (Non Uniform Access Time).

7

Distributed-memory Multicomputers andNetworks

Memory

Cache

CPU

Memory

Cache

CPU

Interconnection network

. . .

8

Distributed-memory: classificazione

• Multicomputer : I processori e la rete sono fisicamente vicini(nella stessa struttura): tightly coupled machine.– La rete di interconnessione rappresenta un cammino di

comunicazione tra i processori ad alta velocità e larghezza dibanda ( es. macchine a ipercubo).

• Network systems: i nodi sono collegati da una rete locale(es.Ethernet) o da una rete geografica (Internet): loosely coupledmultiprocessors.

• I nodi di una distributed memory machine possono essere o singoliprocessori o shared memory multiprocessor.

• Distributed shared memory: realizzazione distribuitadell’astrazione shared memory.

9

Tipi di applicazionia) multithreaded/multitasking:• Applicazioni strutturate come un insieme di processi

(thread) per semplificare la loro programmazione.• Sono caratterizzati dal fatto che esistono più processi

che non processori per eseguire i processi.• I processi sono schedulati ed eseguiti

indipendentemente.

Esempi di applicazioni:• Sistemi a finestre su PC o Workstation• Sistemi operativi time-sharing e multiprocessor• Sistemi real time e di controllo dei processi

10

Tipi di Applicazionib) Sistemi distribuiti• Le componenti dell’applicazione (intrinsecamente distribuite)

vengono eseguite su macchine collegate da una rete locale retelocale o geografica

• I processi comunicano scambiandosi messaggi.

Esempi di applicazioni:– File server in rete– Data-base systems per applicazioni bancarie etc..– Web server su Internet– Sistemi fault tolerant

• Tipica organizzazione : client- server.• I componenti in un sistema distribuito sono spesso

multithreaded applications

11

Tipi di Applicazionic) Applicazioni parallele:• Obiettivo: risolvere un dato problema più velocemente (o un

problema di dimensioni più elevate nello stesso tempo).• Sono eseguite su processori paralleli facendo uso di algoritmi

paralleli.

Esempi di applicazioni:• Applicazioni scientifiche che modellano e simulano fenomeni

fisici complessi (es. previsioni del tempo,evoluzione del sistemasolare etc..)

• Elaborazione di immagini. La creazione di effetti speciali neifilm, etc.

• Problemi di ottimizzazione di grandi dimensioni

12

Processi non sequenziali e tipi diinterazione

13

Algoritmo, programma, processo• Algoritmo: Procedimento logico che deve essere eseguito per

risolvere un determinato problema.• Programma: Descrizione di un algoritmo mediante un opportuno

formalismo (linguaggio di programmazione), che rende possibilel’esecuzione dell’algoritmo da parte di un particolare elaboratore.

• Processo: insieme ordinato degli eventi cui dà luogo unelaboratore quando opera sotto il controllo di un programma.

Elaboratore: entità astratta realizzata in hardware e parzialmente insoftware, in grado di eseguire programmi (descritti in un dato linguaggio).

Evento: Esecuzione di un’operazione tra quelle appartenenti all’insieme chel’elaboratore sa riconoscere ed eseguire; ogni evento determina unatransizione di stato dell'elaboratore

Un programma descrive non un processo, ma un insieme di processi,ognuno dei quali è relativo all’esecuzione del programma da partedell’elaboratore per un determinato insieme di dati in ingresso.

14

Processo sequenzialeSequenza di stati attraverso i quali passa l’elaboratoredurante l’esecuzione di un programma (storia di un processoo traccia dell’esecuzione del programma).

Esempio: valutare il massimo comune divisore tra due numerinaturali x e y:a) Controllare se i due numeri x e y sono uguali, nel qual

caso il loro M.C.D. coincide con il loro valoreb) Se sono diversi, valutare la loro differenzac) Tornare ad a) prendendo in considerazione il più piccolo

dei due e la loro differenza

15

Esempio: M.C.D. di x e y (numeri naturali)int MCD(int x, int y)

{ a = x; b = y;

while (a != b)

if (a > b) a = a – b

else b = b-a;

return a;

}

…

R=MCD(18,24);

66624--b

612181818-a

242424242424y

181818181818x

statoiniziale

statofinale

16

• Più processi possono essere associati allo stesso programma(istanze).

• Ciascuno rappresenta l’esecuzione dello stesso codice condati di ingresso diversi.

Esempi:• Il compilatore di un linguaggio può dare luogo a più processi,

ciascuno relativo alla traduzione di un particolare programma.• Il software di controllo può dare luogo a più processi che

controllano dispositivi uguali o diversi

17

Grafo di precedenza• Un processo può essere rappresentato tramite un

grafo orientato detto grafo di precedenza delprocesso

• I nodi del grafo rappresentano i singoli eventi delprocesso, mentre gli archi identificano leprecedenze temporali tra tali eventi

• Un evento corrisponde all’esecuzione diun’operazione tra quelle appartenenti all’insieme chel’elaboratore sa riconoscere ed eseguire

Es. MCD: essendo il processo strettamente sequenziale,il grafo di precedenza è ad Ordinamento Totale(ogni nodo ha esattamente un predecessore ed unsuccessore)

a = 18

b = 24

b = 6

a = 12

a = 6

18

Processi non sequenziali• L’ordinamento totale di un grafo di precedenza deriva dalla

natura sequenziale del processo (a sua volta imposta dallanatura sequenziale dell’elaboratore).

• In taluni casi l’ordinamento totale è implicito nel problema darisolvere; spesso è un’imposizione che deriva dalla naturasequenziale dell’elaboratore.

• Esistono molti esempi di applicazioni che potrebbero piùnaturalmente essere rappresentate da processi nonsequenziali.

Processo non sequenziale: l'insieme degli eventi che lodescrive e` ordinato secondo una relazione d'ordine parziale.

19

Esempio: valutazione dellʼespressione(3 * 4) + (2 + 3) * (6 - 2)

Grafo di precedenza adordinamento totale:

3 * 4 = 12

2 + 3 = 5

6 - 2 = 4

5 * 4 = 20

12 + 30 = 32

Grafo di precedenza adordinamento parziale:

3 * 4 = 12 2 + 3 = 5 6 - 2 = 4

5 * 4 = 20

12 + 30 = 32

INIZIO

FINE

20

Esempio – segue:

• La logica del problema non impone un ordinamento totalefra le operazioni da eseguire; ad esempio è indifferente chevenga eseguito (2 + 3) prima di eseguire (6 - 2) o viceversa.

• Entrambe le operazioni precedenti devono invece essereeseguite prima del prodotto dei loro risultati.

• Certi eventi del processo sono tra loro scorrelati daqualunque relazione di precedenza temporale il risultatodell’elaborazione è indipendente dall’ordine con cui gli eventiavvengono.

• Molti settori applicativi possono essere rappresentati daprocessi non sequenziali: sistemi in tempo reale, sistemioperativi, sistemi di simulazione, etc…

21

Esempio: Elaborazione di dati su un file sequenziale

elaborazioneNrec

Nrec

file 1 file 2

buffer B;

int i;

for(i=1; i<=N; i++)

{ lettura(B); /* L */

elaborazione(B); /* E */

scrittura(B); /* S */

}

Grafo di precedenza adordinamento totale:

inizio

L1

E1

S1

Ln

En

Sn

fine

22

Esempio – segue:

• La logica del problema impone due soli vincoli1. Le operazioni di lettura (o elaborazione o scrittura)

dovranno essere eseguite in sequenza sugli N record.2. Le operazioni di lettura, elaborazione e scrittura di un

record dovranno essere eseguite in quest’ordine.

• Non esiste alcuna relazione logica di precedenzatra la lettura dell’i-esimo e la scrittura dell’(i-1)-esimo.

• Il grafo degli eventi più naturale risulta esserequello ad ordinamento parziale.

23

Esempio – segue: grafo ad ordinamento parziale

inizio

L1

L2

L3

E1

E2

E3

fine

S1

S2

S3

Ln En Sn

• Vincolo di sincronizzazione:ordinamento di eventi

• Un arco che collega due nodirappresenta il vincolo diprecedenza tra icorrispondenti eventi

24

• L’esecuzione di un processo non sequenziale richiede:– elaboratore non sequenziale– linguaggio di programmazione non sequenziale

Elaboratore non sequenziale (in grado di eseguire piùoperazioni contemporaneamente):– architettura parallela, sistemi multielaboratori (a)– sistemi monoelaboratori (b)

P1

P2

t t

P1 P1

P2 P2

(a) (b)

Linguaggi non sequenziali (o concorrenti): Caratteristicacomune: consentire la descrizione di un insieme di attivitàconcorrenti tramite moduli sequenziali che possono essereeseguiti in parallelo (processi sequenziali)

25

Scomposizione di un processo nonsequenziale

• Scomposizione di un processo non sequenziale in uninsieme di processi sequenziali, eseguiti“contemporaneamente”, ma analizzati e programmatiseparatamente.

• Consente di dominare la complessità di un algoritmo nonsequenziale

• Le attività rappresentate dai processi possono essere:

• completamente indipendenti

• interagenti

26

e11

e12

e13

e21

e22

e23

e31

e32

e33

P1 P2 P3

• L’evoluzione di un processo non influenza quella dell’altro

Processi indipendenti

27

• Nel caso di grafi connessi ad ordinamento parziale, lascomposizione del processo globale in processi sequenzialiconsiste nell’individuare sul grafo un insieme P1….Pn disequenze di nodi (insiemi di nodi totalmente ordinati).

L1

L2

L3

E1

E2

E3

S1

S2

S3

P1

P2

P3

• Presenza di vincoli di precedenza tra le operazioni deiprocessi (espresse dagli archi) o vincoli di sincronizzazione

• In questo caso i tre processi non sono fra loro indipendenti(processi interagenti)

28

Processi interagenti• Le interazioni tra i processi di lettura, elaborazione e

scrittura sono relative ad uno scambio di informazioni. Idati su cui opera il processo di elaborazione sono forniti dalprocesso di lettura.

• Vincolo di sincronizzazione: vincolo imposto da ogni arco delgrafo di precedenza che collega nodi di processi diversi.

• I due processi, quando arrivano ad un punto di interazionecorrispondente ad uno scambio di informazioni, devonosincronizzarsi, cioè ordinare i loro eventi come specificatodal grafo di precedenza.

29

Tipi di decomposizione

• La decomposizione di un grafo di precedenza ad ordinamento parzialein un insieme di sequenze di nodi (processi) può essere fatta in varimodi.

ESEMPIO: Lettura, elaborazione e scrittura dell’i-esimo record(i=1,2,…,n)

• I vincoli di sincronizzazione sono gli archi verticali del grafo.• La scelta più idonea del tipo di decomposizione in processi sequenziali

di un’elaborazione non sequenziale è quella per la quale le interazionitra processi sono poco frequenti così da agevolare l’esecuzioneseparata della singole attività.

LiEi

Si

30

Interazione tra processi

Le possibile forme di interazione tra processiconcorrenti sono:– Cooperazione– Competizione– Interferenza

31

Interazione tra processiCOOPERAZIONE: comprende tutte le interazioni prevedibili e

desiderate, insite cioè nella logica dei programmi (archi, nel grafodi precedenza ad ordinamento parziale).

Prevede scambio di informazioni:• segnali temporali (senza trasferimento di dati)• dati (messaggi) comunicazione

In entrambi i casi esiste un vincolo di precedenza(sincronizzazione) tra gli eventi di processi diversi

32

Scambio di segnali temporali

Esempio:

• Processo P, costituito da tre operazioni p1, p2, p3; deveessere eseguito ogni due secondi.

• Processo Q, costituito da quattro operazioni q1, q2, q3,q4; deve essere eseguito ogni tre secondi.

• Processo O (orologio), ha il compito di registrare ilpassare del tempo e di attivare periodicamente i processiP e Q inviando segnali temporali.

• I nodi O1 , O2, … rappresentano le azioni del processo Oe denotano i secondi scanditi dall’orologio.

• Gli archi che collegano i nodi di O con i nodi di P (Q)rappresentano i vincoli di precedenza dovuti al fatto cheP (Q) deve essere riattivato ogni due (tre) secondi.

33

p’1

processo P processo O processo Q

p’2

p’3

p’’1

p’’2

p’’3

O1

O2

O3

O4

O5

O6

q’1

q’2

q’3

q’4

q’’1

q’’2

34

• Conclusa un'esecuzione, P (Q) deve attendere un nuovosegnale di attivazione prima di ricominciare.

• Relazione di causa ed effetto tra l’esecuzionedell’operazione di invio da parte del processo mittente el’esecuzione dell’operazione di ricezione da parte delprocesso ricevente.

• Vincolo di precedenza tra questi eventi (sincronizzazionedei due processi).

Comunicazione: è previsto uno scambio di dati.

Linguaggio di programmazione: deve fornire costruttilinguistici atti a specificare la sincronizzazione e laeventuale comunicazione tra i processi

35

COMPETIZIONE

La macchina concorrente su cui i processi sonoeseguiti mette a disposizione un numero limitato dirisorse condivise tra i processi.

La competizione ha come obiettivo il coordinamentodei processi nell’accesso alle risorse condivise.

Ad esempio, per risorse che non possono essere usatecontemporaneamente da più processi, è necessarioprevedere meccanismi di competizione.

Interazione prevedibile e non desiderata, manecessaria.

36

CompetizioneEsempio: Mutua esclusione

• Due processi P e Q devono usare in certi istanti una comune stampante

Sp={ps1, ps2,…, psn} e Sq={qs1, qs2,…,qsn}

sono le sequenze di istruzioni che P e Q devono rispettivamenteeseguire per produrre un messaggio sulla stampante

• Le due sequenze devono essere eseguite in modo mutuamente esclusivo

px ps1 ps2 psn pyprocesso P

qx qs1qs2

qsn qyprocesso Q

px e py (qx e qy) denotano rispettivamente l’ultima operazioneeseguita da P (Q) prima della stampa e la prima eseguita dopo lastampa.

Q usa la stampante

P usa la stampante

37

• L’interazione si estrinseca in un vincolo di precedenza tra eventi diprocessi diversi (psn deve precedere qs1), cioè in un vincolo disincronizzazione.

• Non è (come nel caso della comunicazione) un vincolo di causa edeffetto, cioè l’ordine con cui devono avvenire due eventi non èsempre lo stesso. Basta che sia verificata la proprietà di mutuaesclusione.

px ps1 ps2 psn py

qx qs1 qs2 qsn qyprocesso Q

processo P

Q usa la stampante

P usa la stampante

38

Sezione Critica• La sequenza di istruzioni con le quali un processo accede a un

oggetto condiviso con altri processi prende il nome di sezionecritica.

• Ad un oggetto puo` essere associata una sola sezione critica(usata da tutti i processi) o più sezioni critiche (classe di sezionicritiche).

• La regola di mutua esclusione stabilisce che:Sezioni critiche appartenenti alla stessa classe devono

escludersi mutuamente nel tempo.Nell'esempio precedente:• Sp e Sq sono sezioni critiche;• Sp e Sq appartengono alla classe di sezioni critiche associate alla

stampante;

39

Cooperazione: sincronizzazione diretta o esplicita

Competizione: sincronizzazione indiretta o implicita

Interferenza: interazione provocata da errori diprogrammazione:1. Inserimento nel programma di interazioni tra processi non

richieste dalla natura del problema

2. Erronea soluzione a problemi di interazione (cooperazione ecompetizione) necessarie per il corretto funzionamento delprogramma

E` un'interazione non prevista e non desiderata

• dipende dalla velocità relativa dei processi

• gli errori possono manifestarsi nel corsodell’esecuzione del programma a seconda delle diversecondizioni di velocità di esecuzione dei processi

(errori dipendenti dal tempo)

40

• Esempio di interferenza del primo tipo:

Solo P deve operare su una risorsa R. Per un errore diprogrammazione viene inserita in Q un’istruzione chemodifica lo stato di R. La condizione di errore sipresenta solo per particolari velocità relative deiprocessi.

• Esempio di interferenza del secondo tipo:

P e Q competono per una stampante. Si garantisce lamutua esclusione solo per la stampa della prima linea.La condizione di errore si presenta solo perparticolari velocità relative dei processi.

Uno degli Obiettivi fondamentali dellaprogrammazione concorrente è

l’eliminazione delle interferenze.

41

ARCHITETTURE E LINGUAGGI PER LAPROGRAMMAZIONE CONCORRENTE

42

Linguaggi per la programmazioneconcorrente

• Disponendo di macchine concorrenti (in grado dieseguire più processi sequenzialicontemporaneamente) e di un linguaggio diprogrammazione con il quale descrivere algoritmi nonsequenziali, è possibile scrivere e far eseguireprogrammi concorrenti.

• L’elaborazione complessiva può essere descritta comeun insieme di processi sequenziali asincroniinteragenti

43

Proprietà di un linguaggio per laprogrammazione concorrente

• Contenere appositi costrutti con i quali sia possibile dichiararemoduli di programma destinati ad essere eseguiti come processisequenziali distinti.

• Non tutti i processi costituenti un’elaborazione vengono eseguiticontemporaneamente. Alcuni processi vengono svolti se,dinamicamente, si verificano particolari condizioni. E’ quindinecessario specificare quando un processo deve essere attivatoe terminato.

• Occorre che siano presenti strumenti linguistici per specificarele interazioni che dinamicamente potranno aversi tra i variprocessi

44

Architettura di una macchina concorrente

• Difficilmente M ha una struttura fisica con tante unità dielaborazione quanti sono i processi da svolgerecontemporaneamente durante l’esecuzione di un programmaconcorrente.

• M è una macchina astratta ottenuta con tecniche software (ohardware) basandosi su una macchina fisica M’ molto piùsemplice (con un numero di unità di elaborazione moltominore del numero dei processi).

Programmi sorgentescritti nel linguaggio

LCompilatore di L

Programmi tradottinel linguaggio oggetto

per la macchina M

45

macchina astratta M

meccanismo di multiprogrammazionemeccanismo di sincronizzazione

macchina fisica M’ (hardware)

nucleo del sistema

Oltre ai meccanismi di multiprogrammazione e sincronizzazione è presente anche un meccanismo di protezione(controllo degli accessi alle risorse).

• Importante per rilevare eventuali interferenze tra iprocessi.• Può essere realizzato in hardware o in software nelsupporto a tempo di esecuzione.• Capabilities e liste di controllo degli accessi

46

• Il nucleo corrisponde al supporto a tempo di esecuzione delcompilatore di un linguaggio concorrente.

• Nel nucleo sono sempre presenti due funzionalità base:• meccanismo di multiprogrammazione• meccanismo di sincronizzazione e comunicazione

• Il primo meccanismo è quello preposto alla gestione delle unità dielaborazione della macchina M’ (unità reali) consentendo ai variprocessi eseguiti sulla macchina astratta M di condividere l’usodelle unità reali di elaborazione (scheduling)

• Il secondo meccanismo è quello che estende le potenzialità delleunità reali di elaborazione, rendendo disponibile alle unità virtualistrumenti mediante i quali sincronizzarsi e comunicare.

47

Architettura di MDue diverse organizzazioni logiche:

– Gli elaboratori di M sono collegati ad un’unica memoria principale(sistemi multiprocessore)

– Gli elaboratori di M sono collegati da una sottorete dicomunicazione, senza memoria comune (sistemi distribuiti).

Le due precedenti organizzazioni logiche di M definiscono due modelli diinterazione tra i processi:1. Modello a memoria comune, in cui l’interazione tra i processi avviene su

oggetti contenuti nella memoria comune (modello ad ambiente globale).

2. Modello a scambio di messaggi, in cui la comunicazione e lasincronizzazione tra processi si basa sullo scambio di messaggi sulla reteche collega i vari elaboratori (modello ad ambiente locale ).