Programmazione Concorrente: Concetti di Base Valter Crescenzi [email protected] crescenz...
-
Upload
pasqualino-moretti -
Category
Documents
-
view
235 -
download
2
Transcript of Programmazione Concorrente: Concetti di Base Valter Crescenzi [email protected] crescenz...
![Page 1: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/1.jpg)
Programmazione Concorrente:Concetti di Base
Valter [email protected]
http://www.dia.uniroma3.it/~crescenz
Corso di Programmazione Concorrente
![Page 2: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/2.jpg)
Programmi e Flussi di Esecuzione
Programma: descrizione statica, ovvero che non cambia nel tempo, di un flusso di esecuzione
Flusso di Esecuzione: concetto dinamico, ovvero che evolve nel tempo un flusso di esecuzione scaturisce con l’esecuzione
di un programma da parte di un esecutore ad un medesimo programma possono corrispondere
molteplici flussi di esecuzione
Un flusso di esecuzione per poter avanzare necessita di risorse, prima tra tutte, l’esecutore
![Page 3: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/3.jpg)
Risorse
Servono per l’avanzamento dei flussi di esecuzione
L’esecutore è una di queste risorse, ma ne esistono di molti altri tipi
Consideriamo, per concretezza, esempi di risorse hardware, ma ragionamenti analoghi si possono fare anche con altri tipi di risorse, ad esempio risorse software
![Page 4: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/4.jpg)
Prerilasciabilità delle Risorse
Prerilasciabili si possono sottrarre al flusso di esecuzione che le sta
usando senza causare il fallimento dell’esecuzione in atto risorsa non seriale: molteplicità della risorsa > 1
es. memoria virtuale, processore virtuale
Non Prerilasciabili se sottratte al flusso di esecuzione che le sta usando,
l’esecuzione fallisce risorse seriali; molteplicità = 1
es. stampante, masterizzatore
Molteplicità di una risorsa: numero massimo di flussi di esecuzione che la possono usare concorrentemente senza comprometterne l'utilizzo
![Page 5: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/5.jpg)
Risorse di Molteplicità Finita
Per le risorse di molteplicità finita, affinché l’utilizzo risulti costruttivo, è necessario che gli accessi alla risorsa siano controllati
Si prevede Un gestore della Risorsa Un protocollo di accesso alla Risorsa
richiesta ed ottenimento della risorsa utilizzo della risorsa
rilascio della risorsa
![Page 6: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/6.jpg)
Programmazione Sequenziale
La programmazione è di solito insegnata con riferimento ad un esecutore sequenziale
Un esecutore sequenziale svolge una sola azione alla volta sulla base di un programma sequenziale
L’esecuzione di un programma sequenziale origina un flusso di esecuzione sequenziale che conferisce un ordinamento totale alle azioni eseguite
La programmazione di un esecutore concorrente, ovvero in grado di eseguire più istruzioni contemporaneamente, sebbene più difficile di quella tradizionale, ha forti motivazioni didattiche e pratiche
![Page 7: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/7.jpg)
Programmazione Concorrente: Motivazioni
Migliorare la comprensione di un SO che regola diverse attività parallele
Sfruttare le prestazioni ottenibili da architetture multi-processor un programma sequenziale non giova di una architettura
parallela Migliorare la reattività delle applicazioni all’input
dell’utente durante lunghe operazioni di I/O o di elaborazione
La maggiore naturalezza con la quale si possono scrivere alcune tipologie di applicazioni (server, robotica, giochi, simulazioni di attività concorrenti)
![Page 8: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/8.jpg)
Utilizzo dei Processori: Applicazione mono-thread
![Page 9: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/9.jpg)
Utilizzo dei Processori: Applicazione multi-thread
![Page 10: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/10.jpg)
Istruzione ed Area Memoria
Per ragionare a vari livelli di granularità, consideriamo astrattamente i due concetti di istruzione ed area di memoria Istruzione; alcune possibili esemplificazioni:
istruzione macchina istruzione firmware uno statement java un metodo di una classe java un intero programma una stored-procedure di un DBMS la scrittura di un blocco del gestore della concorrenza di un DBMS
Area di Memoria; alcune possibili esemplificazioni: un bit, un byte, una parola macchina un campo di una struttura dati, una struttura dati intera un attributo, una tupla, una tabella, un intero db un blocco di un dispositivo di memoria secondaria
![Page 11: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/11.jpg)
Flussi di Esecuzione Paralleli o Concorrenti
Un f.d.e. sequenziale definisce un ordinamento totale sulle istruzioni
Un f.d.e. parallelo definisce un ordinamento parziale sulle istruzioni su alcune istruzioni l’esecutore è libero di scegliere quali
iniziare prima e/o di eseguirle contemporaneamente
Esempio: consideriamo un banale programma per calcolare e stampare le prime quattro potenze di un valore X. Si supponga di disporre di tre sole tipologie di istruzione:
leggi <variabile> scrivi <variabile> <variabile> ← <variabile> * <variabile>
![Page 12: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/12.jpg)
Diagramma delle Precedenze
begin 1. leggi X; 2. scrivi X; 3. X2 ← X * X; 4. scrivi X2; 5. X3 ← X2 * X; 6. scrivi X3; 7. X4 ← X2 * X2; 8. scrivi X4;end
Algoritmo sequenziale
leggi X
scrivi X
scrivi X2 X3 ←X2*X
scrivi X3
scrivi X4
X2 ←X*X
X4←X2*X2
Algoritmo parallelo
![Page 13: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/13.jpg)
Esercizi
Esercizio: costruire un diagramma delle precedenze che esprima il massimo grado di parallelismo nel calcolo delle seguenti espressioni sullo stile dell’esempio appena visto:
a) (A+B)*(C+D)
b) A*X^4+B*X^3+C*X^2+D*X+E
c) ( -B-SQRT(B^2-4*A*C) )/(2*A)
![Page 14: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/14.jpg)
Esecuzioni Sequenziali e Parallele
Sia i una generica istruzione, in generale può essere divisibile in istruzioni più elementari
Siano Ii e Fi gli eventi di inizio e fine esecuzione
Date due istruzioni a e b consideriamo i 6 possibili ordinamenti in cui occorrono i quattro eventi Ia, Fa, Ib, Fb
Ia Ib Fa Fb
Ia Fa Ib Fb Ia Ib Fb Fa
Ib Fb Ia Fa Ib Ia Fa Fb
Ib Ia Fb Fa
esecuzioni sequenziali esecuzioni parallele
![Page 15: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/15.jpg)
Sequenze di Esecuzione Ammissibili
Una sequenza di esecuzione ammissibile è una sequenza di questi eventi che rispetta i vincoli espressi dal diagramma delle precedenze
Ad un certo diagramma delle precedenze corrispondono molteplici sequenze di esecuzione ammissibili
Ad es., con riferimento al precedente diagramma:
Ii1Fi
1Ii
2Ii
3Fi
2Fi
3Ii
4Ii
7Ii
5Fi
5Fi
7Fi
4Ii
6Fi
6Ii
8Fi
8
![Page 16: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/16.jpg)
Sequenze di Interleaving
Un caso speciale ma rilevante di sequenza di esecuzione ammissibile; consideriamo: un solo esecutore fisico istruzioni indivisibili due flussi di esecuzione sequenziali A e B con istruzioni
a1a2a3a4…
b1b2b3b4…
Diciamo sequenza di interleaving la sequenza scelta dall’esecutore, ad esempio: a1b1b2a2b3a3a4b4…
Analogamente per tre o più flussi di esecuzione
![Page 17: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/17.jpg)
Processori Virtuali
Astrazione dei servizi offerti dai sistemi operativi moderni
Molteplici esecutori virtuali possono essere implementati con uno o più processori fisici attraverso tecniche di context-switching
In base al numero di processori fisici disponibili ed al numero di f.d.e. esistenti, risultano possibili varie situazioni per farli avanzare concorrentemente interleaving overlapping una combinazione di queste due
![Page 18: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/18.jpg)
Overlapping ed Interleaving
L’esecutore può eseguire più istruzioni concorrentemente mediante
overlapping
interleaving
combinazione
CPUCPU00
CPUCPU11
CPUCPU00
CPUCPU00
CPUCPU00
CPUCPU00
CPUCPU00
CPUCPU11
CPUCPU11
CPUCPU00
t
t
t
t
t
t
Pa
Pb
Pa
Pb
Pa
Pb
![Page 19: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/19.jpg)
Legge di AmdahlF: frazione del lavoro serialeN: numero di processori
![Page 20: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/20.jpg)
Commenti alla legge di Amdahl E' un modello estremamente semplice ma efficace
per stimare il miglioramento ottenibile parallelizzando un algoritmo sequenziale
Trascura numerosissimi elementi (es. transitori, costi del contex-switching) ed in effetti è utilizzabile solo quando il problema è di dimensioni talmente grandi da renderli trascurabili
Ogni programma concorrente contiene sempre una percentuale di lavoro intrinsecamente non parallelizzabile
Ad esempio la componente che si occupa di sincronizzare i flussi tra cui è stato ripartito il lavoro
Questa componente seriale limita il massimo speed-up ottenibile e rende antieconomico aumentare il numero di processori fisici oltre un certo numero
![Page 21: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/21.jpg)
Fork & Join
Per esprimere attività concorrenti si possono usare diversi costrutti. Nella forma più semplice, bastano: fde_id = fork <program_id>crea un f.d.e. figlio di quello attuale mediante l’attivazione del programma specificato. Restituisce l’identificatore del f.d.e. figlio appena creato. Padre e figlio continuano indipendentemente il loro avanzamento. join fde_idil f.d.e. corrente rimane bloccato sino a quando non termina il f.d.e. con l'identificatore specificato
In genere ciascun flusso di esecuzione è dotato di proprie aree di memoria dati (record di attivazione) mentre il codice può essere condiviso. In questo caso si parla di programmi o procedure rientranti
![Page 22: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/22.jpg)
Traduzione di un Diagramma delle Precedenze con fork & join
concurrent Procedure P1
begin <corpo di P1>; endconcurrent Procedure P2
begin <corpo di P2>; end…begin P1;
fork P2; fork P3;
join P2; join P3;
P4;end
P3 P2
P1
P4
![Page 23: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/23.jpg)
Esercizi
Esercizio: tradurre con fork e join il diagramma delle precedenze per il calcolo e la stampa delle prime quattro potenze di un dato numero.
Esercizio: disegnare il diagramma delle precedenze per il calcolo e la stampa progressiva delle prime N potenze di un dato numero; tradurre con fork e join il diagramma delle precedenze trovato. Ragionare sulla presenza del ciclo di iterazione, come esprimerlo ed interpretarlo in un diagramma delle precedenze.
Esercizio: disegnare il diagramma delle precedenze per il calcolo del prodotto di due matrici interi; tradurre con fork e join il diagramma delle precedenze trovato.
![Page 24: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/24.jpg)
Esercizi
P3 P2
P1
P4
P2 P3
P1
P6
P4 P5
Esercizio: tradurre con fork e join i diagrammi delle precedenze mostrati accanto.
![Page 25: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/25.jpg)
Fork & Join: Espressività
Queste due primitive sono sufficienti a tradurre un qualsiasi diagramma delle precedenze
Vantaggi: flessibilità espressività
Svantaggi: basso livello di astrazione Rispetto al diagramma delle precedenze, il programmatore è
costretto a specificare la creazione dei flussi non impongono alcuna particolare struttura al
programma concorrente
![Page 26: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/26.jpg)
Altri Costrutti per Esprimere Programmi Concorrenti
cobegin P1 || P2 || … || Pn coend
P1 P2 Pn…
Esegue n istruzioni concorrentemente
Non sono sufficientemente espressive da esprimere qualsiasi diagramma delle precedenze
Risulteranno comode per esprimerne alcuni
![Page 27: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/27.jpg)
Quando Eseguire Concorrentemente?
Dato un programma sequenziale, non è difficile costruire un equivalente diagramma delle precedenze
Tuttavia è opportuno stabilire un criterio generale per capire se due istruzioni possono essere eseguite concorrentemente o meno: per ottenere diagrammi delle precedenze che
esprimono il massimo grado di parallelismo possibile per automatizzare il calcolo dei vincoli che esprimono
Quando è lecito eseguire
concorrentemente due istruzioni ia e ib ?
![Page 28: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/28.jpg)
Dominio e Rango
Indichiamo con A, B, … X, Y, … un’area di memoria Una istruzione i
dipende da una o più aree di memoria che denotiamo domain(i), ovvero dominio di i
altera il contenuto di una o più aree di memoria che denotiamo range(i) di i, ovvero rango di i
Ad es. per la procedura Pprocedure Pbegin X ← A + X; Y ← A * B;end
domain(P) = {A, B, X}
range(P)= {X, Y}
![Page 29: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/29.jpg)
Condizioni di Bernstein
Quando è lecito eseguire
concorrentemente due istruzioni ia e ib ?
se valgono le seguenti condizioni, dette Condizioni di Bernstein:
– range(ia) ∩ range(ib) = Ø
– range(ia) ∩ domain(ib) = Ø
– domain(ia) ∩ range(ib) = Ø
![Page 30: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/30.jpg)
Condizioni di Bernstein (2)
Si osservi che non si impone alcuna condizione su
domain(ia) ∩ domain(ib)
Sono banalmente estendibili al caso di tre o più istruzioni
Esempi di violazione per le due istruzioni: X ← Y + 1; X ← Y – 1; (violano la 1.) X ← Y + 1; Y ← X - 1 ; (violano la 2. e la 3.) scrivi X; X ← X + Y; (violano la 3.)
![Page 31: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/31.jpg)
Effetti delle Violazioni
Quando un insieme di istruzioni soddisfa le condizioni di Bernstein, il loro esito complessivo sarà sempre lo stesso indipendentemente dall’ordine e dalle velocità relative con cui vengono eseguite in altre parole, indipendentemente dalla particolare
sequenza di esecuzione seguita dai processori ovvero, sarà sempre equivalente ad una loro
esecuzione seriale
Al contrario, in caso di violazione, gli errori dipendono dall’ordine e dalle velocità relative generando il fenomeno dell’interferenza
![Page 32: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/32.jpg)
Esempio di Interferenza (1)
procedure Prenotabegin Ra ← POSTI - 1; POSTI ← Ra ;end
La disponibilità di un volo di una compagnia aerea è memorizzata in POSTI=1. Due signori nel medesimo istante ma da due postazioni distinte, chiedono rispettivamente di prenotare l’ultimo posto e di disdire la prenotazione già effettuata
Le due richieste vengono tradotte in queste sequenze di istruzioni elementari indivisibili:
procedure Disdicibegin Rb ← POSTI + 1; POSTI ← Rb ;end
![Page 33: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/33.jpg)
Esempio di Interferenza (2)
L’esecuzione concorrente da luogo ad una qualsiasi delle possibili sequenze di interleaving. Consideriamo un campione di tre sequenze:
Ra ← POSTI - 1;
Rb ← POSTI + 1;POSTI ← Rb ;POSTI ← Ra ;
(POSTI=0)
Ra ← POSTI - 1;POSTI ← Ra ;
Rb ← POSTI + 1;POSTI ← Rb ;
(POSTI=1)
Rb ← POSTI + 1;
Ra ← POSTI - 1;POSTI ← Ra ;POSTI ← Rb ;
(POSTI=2)
esecuzione sequenziale
![Page 34: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/34.jpg)
Interferenza
Si ha interferenza in presenza di due o più flussi di esecuzione almeno un flusso di esecuzione eseguente scritture
Perché un flusso esegue un cambio di stato dell’area di
memoria in maniera non atomica gli stati transienti che intercorrono tra quello iniziale a
quello finale sono visibili a flussi di esecuzione diversi da quello che li sta producendo
N.B. Le piattaforme a cui facciamo riferimento non offrono la possibilità di fare aggiornamenti atomici
![Page 35: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/35.jpg)
Origine dei Fenomeni di Interferenza
stato consistente
iniziale
stato consistente
finale
flusso di esecuzione
flusso di esecuzione scrittore
stato transiente
stato transiente
stato transiente
![Page 36: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/36.jpg)
Errori Dipendenti dal Tempo
L’interferenza causa errori particolarmente temibili perché dipendenti dalla sequenza di interleaving effettivamente eseguita
Temibili perché ciascuna sequenza di esecuzione può produrre
effetti diversi la scelta della particolare sequenza adottata è (dal
punto di vista del programmatore) casuale
![Page 37: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/37.jpg)
Caratteristiche degli Errori Dipendenti dal Tempo
irriproducibili: possono verificarsi con alcune sequenze e non con altre
indeterminati: esito ed effetti dipendono dalla sequenza
latenti: possono presentarsi solo con sequenze rare
difficili da verificare, e testare: perché le tecniche di verifica e testing si basano sulla
riproducibilità del comportamento
![Page 38: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/38.jpg)
Il Programmatore e gli Errori Dipendenti dal Tempo
Il programmatore non può fare alcuna assunzione: sulla particolare sequenza di interleaving eseguita, ovvero sulle velocità relative dei vari processori virtuali su un qualsiasi altro tipo di sincronismo legato alla specifica
implementazione dei processori virtuali
Un programma che implicitamente od esplicitamente basa la propria correttezza su ipotesi circa la velocità relativa dei vari processori, è scorretto
Esiste una sola assunzione che possono fare i programmatori sulla velocità dei processori virtuali…
![Page 39: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/39.jpg)
Assunzione di Progresso Finito
Tutti i processori virtuali hanno
una velocità finita non nulla
Questa assunzione è l’unica che si può fare sui processori virtuali e sulle loro velocità relative
![Page 40: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/40.jpg)
Starvation & Deadlock (1)
Esistono due diverse situazioni che possono invalidare l’assunzione di progresso finito starvation: quando un f.d.e. rimane in attesa di un
evento che pure si verifica infinite volte un sistema di f.d.e. che garantisce contro questa
evenienza si dice che gode della proprietà di fairness deadlock (o stallo): quando due o più f.d.e.
rimangono in attesa di eventi che non potranno mai verificarsi a causa di condizioni cicliche nei f.d.e. e nella richiesta di risorse esempio classico: un processo Pa possiede una risorsa
R1 e richiede una risorsa R2 già posseduta da un altro processo Pb; quest’ultimo a sua volta richiede l’uso di R1
![Page 41: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/41.jpg)
Starvation & Deadlock (2)
proprietà di fairness– Accezione stringente, non bastano argomentazioni
probabilistiche: se esiste anche una sola sequenza di esecuzione ammissibile in cui un flusso non avanza mai un algoritmo è considerato unfair
– Per semplicità chiamiamo unfair anche una simile sequenza Osservazioni: un algoritmo unfair ma che dal punto di
vista probabilistico sembra produrre solo seq. unfair con probabilità tendenti allo zero potrebbe nella pratica causare uno di questi scenari:
• Starvation: le seq. unfair diventa probabile a causa di fattori trascurati nella modellazione
• Forte varianza nei tempi di attesa di un f.d.e. >> deadlock (o stallo)
![Page 42: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/42.jpg)
Unfairness: conseguenze
Forte impatto nelle performance
Varianza dei tempi di esecuzione
Il contesto decide cosa risulta più opportuno
Varianza dei tempi di esecuzione
Tempo di esecuzione
![Page 43: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/43.jpg)
Divisibilità delle Istruzioni edAssunzione di Progresso Finito
Salvo diverso ed esplicito avviso in senso contrario, assumeremo che tutte le istruzioni di cui faremo uso, in qualsiasi linguaggio di programmazione utilizzato nel corso, astratto o concreto, siano divisibili
– N.B. anche le più elementari
Ipotesi diverse richiederebbero una conoscenza di dettaglio dei linguaggi e delle piattaforme utilizzate
![Page 44: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/44.jpg)
Interazione tra Flussi di Esecuzione Concorrenti
Due flussi di esecuzione possono essere: disgiunti interagenti
competizione: due o più flussi di esecuzione chiedono l’uso di una risorsa comune riusabile e di molteplicità finita
cooperazione: due o più flussi di esecuzione cooperano per raggiungere un obiettivo comune
![Page 45: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/45.jpg)
Competizione
La competizione occorre ogni qualvolta che c’è una risorsa riusabile condivisa e di molteplicità finita (spesso seriale) incrocio stradale sportellista alle poste stampante dipartimentale rete ethernet
In presenza di competizione è necessario “gestire” i possibili fenomeni di interferenza
![Page 46: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/46.jpg)
Caratteristiche Rilevanti dell’Esecutore
Quale strategia risulta più opportuna per gestire l’interferenza dipende largamente dalla tollerabilità degli effetti dalla rilevabilità dei fenomeni di interferenza dalla recuperabilità degli effetti eventualmente
cancellando, ripetendo e disfacendo alcune operazioni
Ad esempio i DBMS moderni possiedono interi sotto-sistemi unicamente dedicati alla gestione della concorrenza con diverse politiche
![Page 47: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/47.jpg)
Strategie per Gestire l’Interferenza
La strategia migliore per gestire l'interferenza dipende fortemente dal contesto, ed in particolare da almeno questi elementi La natura delle conseguenze La possibilità di recuperarla La possibilità di rilevare l'interferenza Il livello di competizione
Le strategie si classificano in Ottimistiche/try-and-see Pessimistiche/Conservatrici/check-and-act
![Page 48: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/48.jpg)
Strategie per Gestire l’Interferenza
Conseguenze inaccettabili
ad es. incrocio stradale trascurabili
applicazioni non critiche rilevabili e controllabili
ad es. iteratori rilevabili e recuperabili
ad es. rete ethernet
…
Strategie evitare qls interferenza
conservatrici ignorare
rilevare ed evitare
fail-fast rilevare e ripetere
ottimistiche
...
![Page 49: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/49.jpg)
Tecniche per la Gestione dell’Interferenza
Le strategie trovano concretezza in alcune tecniche di programmazione per la scrittura di codice privo di interferenza
immutabilità delle aree di memoria confinamento degli aggiornamenti
per flusso di esecuzione per aree di memoria …
esclusione delle sequenze di interleaving
(sincronizzazione)
![Page 50: Programmazione Concorrente: Concetti di Base Valter Crescenzi crescenz@dia.uniroma3.it crescenz Corso di Programmazione Concorrente.](https://reader036.fdocumenti.com/reader036/viewer/2022081504/5542eb57497959361e8c1e9f/html5/thumbnails/50.jpg)
Programmazione Concorrente ed Architetture degli Elaboratori
Architetture più diffuse SMP data-flow, per il calcolo vettoriale cluster
Scenario più comune e di riferimento per questo corso: pochi processori, f.d.e. a “grana grossa” Flussi di esecuzione sequenziali debolmente connessi ...Tuttavia alla fine del corso parleremo anche di framework
per la decomposizione parallela che a senso usare anche nello scenario opposto