### Lezione 14 - 23/10/2024
inizia mpi.

I middleware che si basano sul paradigma message passing, lo standard è mpi. in generale il middleware offre librerie per lo scambio di messaggi, che includono primitive punto punto o comunicazione collettiva tra più processi, operazioni per la gestione dei loop. Usiamo un linguaggio tradizionale come C o fortrean sequenziali.
Diventa complicato progettare l'applicazione.

Ci sono delle fasi. SUpponiamo di avere già dei pezzi di soluzione sequenziale, dobbiamo provare a decomporre l'algoritmo che risolve il problema in tanti task, infatti noi puntiamo prima di tutto a un task parallelism, quindi task eseguiti in parallelo su nodi diversi con dati diversi, per poter ottenere migliori performance. questa fase di decomposizione deve portare poi ad una fase di assegnazione dei task a un certo numero di processi, quindi quei task devono essere messi in più codici in tanti processi differenzi, quindi passiamo da task distribuiti a una serie di programmi sequenziali, questa è in teoria la fase più importante per stabilire chi deve fare cosa. Ovviamente i processi devono comunicare, cosi i task possono scambiarsi risultati ecc. Questa terza fase richiede utilizzo di primitive messe a disposizione dal middleware. A questo punto avremo un codice C ad esempio con delle chiamate a funzioni di tipo send, receive, ecc. Abbiamo quindi un codice distribuito, quindi anche se i processi sono indipendenti perchè su nodi diversi coi propri dati, possono collaborare tramite scambio di messaggi. L'ultimo passo è quello di prendere i processi e mapparli sui nodi, si può risolvere come un problema di ottimizzazione per migliorare tempi di comunicazione ecc.

vediamo mpi.

MPI è in realtà il tentativo, a valle di tante proposte (ognuno si faceva la propria libreria per le primitive ecc), si è pensato:
quali devono essere le primitive che servono a un programmatore e quali devono essere i parametri. Rocco era presente a questa discussione su quale dovessero essere le interfacce e le primitive di comunicazione!!!.
Il codice mpi è portabile.
Queste implementazioni rimate famose sono alcune fatte da degli accademici americani!. non sono sicure come a livello industriale ma sono best effort.

L'antenato di mpi è pvm, che consentiva a un insieme di macchine unix di essere utilizzata come un unica macchina parallela virtuale a memoria distribuita.
Bisognava far partire sui nodi un demone pvmd, che diventano nodi della macchina parallela virtuale, i demoni comunicavano tra di loro tramite socket e si scambiavano informazioni sullo stato della macchina, ossia dove sono in esecuzione i singoli processi.
Ciascun nodo della macchina parallela virtuale è una
risorsa di calcolo atomica, accessibile attraverso una serie
di primitive che possono essere incluse nei comuni
linguaggi procedurali (C e Fortran).
offriva anche delle primitive da mettere nel codice c e fortran, sempre primitive di send e receive, per i gruppi, e anche primitive per far partire un processo su un nodo qualsiasi della macchina virtuale.
era un middleware semplice da usare ma limitato a macchine unix.

Dopodichè simao arrivati a definire uin interfaccia standard, che è mpi.
Il codice è portabile, può funzionare anche su implementazioni mpi diverse.
mpich è un implementazione.
portabilità non significa interpoerabilità, perchè programmi con implementazioni diverse di mpi non si parlano!!.
Un altro difetto è la mancanza di primite per interagire con l'ambiente di esecuzione, esempio il punto di forza di pvm era di far partire un processo su un nuovo della macchina virtuale, ma in mpi queste primite di gestione delle risorse di calcolo non ci sono.

Vediamo il modello computazionale.
E' quello visto in generale, ma anziche usare un paradigma MPMD (multipleprogram multiple data), di solito di usa il paradgima SPMD (single program multiple data), quindi un unico codice C, e dopodichè al run si specifica quante istanze di quel processo far partire, come se fossero dei thread. Quindi quel codice verrà eseguito in più istanze su macchine diverse con dati diversi, come se lanciassimo tanti processi su macchine diverse, e le variabili saranno locali per ognuno, ogni processo avrà un id per differenziare delle attività. DI solito si usa SPMD quindi, ma si potrebbe usare anche MPMD, noi credo faremo SPMD.

le istanze del processo sono identificate da questo id che si chiama rango, e tutti fanno parte di un gruppo iniziale. tutto ciò avviene dopo la primitva mpi_init che fa partire il supporto a tempo di esecuzione di mpi.
Ovviamente il gruppo non rimarrà sempre lo stesso, se ne possono creare altri ecc.
Quinid esemmpio, compilo il codice mpi, e facciamo partire 10 istanze di questo processo, avremo 10 istanze istanziate sui vari nodi, ognuno con le proprie variabili private nella memoria locale del nodo.
I processi continunano a rimanere nel gruippo di partenza, ma anche ai nuovi che vengono eventualmente creati.
Il gruppo oltre a definire un insieme di processi, è associato al contesto di comunicazione, che si chiama COMUNICATOR, che è l'insieme di un gruppo+contesto; all'inizio, insieme al gruppo iniziale che contiene tutti i processi, ci viene fornito anche un comunicator (di solito è l'ultimo parametro delle primitive), che rappresenta il contesto di comunicator; nota che a ogni comunicator è sempre associato un gruppo e il contesto di comunicazione. Contesto di comunicazione vuol dire che noi possiamo avere per un gruppo possiamo avere più contesti di comunucazione, per differenziare la comunicazione, certi messaggi con lo stesso gruppo li mando con un comunicator, e altri messaggi dello stesso gruppo li mando con un altro comunicator.
mpi_init apre le danze.
Alcuni processi fanno una cosa e altri ne fanno un altra.

supponiamo di aver fatto mpi_init e di sapere il rango del processo (istanza),
Andiamo a vedere le primite di comunicazione.
- primitiva send: notiamo la presenza del comunicator alla fine, sicuramente devo inviare dei dati, quindi il primo parametro è un puntatore all'indizzo di memoria da dove prendere i dati che devo inviare, numero di dati e tipo di dati da mandare, rank del processo destinarario. vedremo datatype non è solo un tipo di dato primitivo o struct in c, ma è più complicato.

NOTA, IL RANGO NON È UN PID, SONO ASSOCIATI DELLE ISTANZE, IL RANGO SI ASSOCIA AL COMMUNICATOR. UN PROCESSO PUÒ AVERE RANGHI DIVERSI SE APPARTIENE A GRUPPI DIVERSI.

ogni processo ha una coda unica di messaggi per ogni communicator.

Vediamo la receive:
abbiamo sempre il communicator. puntatore al buffer per dati in arrivo.

scarrellata.

i printf quando li faremo sulla nostra macchina quindi 1 solo nodo, verranno visualizzati in un ordine un po a caso, cioè se vedo un printf prima non è detto che quell'operazione è stata fatta prima.

datatypes.
Tutte le primitive di comunicazione identificano la
struttura dati da trasferire specificando l’indirizzo base ed
un datatype.
il datatype lo posso creare con una primitiva.
ogni item che mando sarà di quel datatype, e indica quante volte dobbiamo applicare la regola.
ci sono le regole.

utilizzo dei datatype: trasposta di una matrice
programma mpi che in maniera distribuita effettua la trasposta.
abbiamo una matrice iniziale, che ad esempio il processo zero legge da file.
processo zero ha tutta la prima riga. il processo deve parlare con tutti gli altri per ricostruire una colonna.

### Lezione 15 - 23/10/2024
riprendiamo datatypes.

Più che tipi di dati sono delle regole attraverso quali impacchettiamo i byte della memoria nel messaggio.
ogni processo ha un certo numero di righe.
il processo 0 la legge da file e distribuisce le righe. la strisce è lunga numline per ogni processo, che sarà dim/n_proc.
alla fine i processi alla fine dovrà avere alla fine numline colonne.
aij lo scambio con aji. C'è un problema, dovremmo trasporre anche i singoli pezzi, ossia le matrici numline x numline. Con datatype questa ultima trasposta possiamo evitarla.

ogni matrice ha la propria matrice numline x dim
il trucco è mandare la singola matrice numline x numline già come colonne, cosi poi il processo ricevente se la salva come riga in indirizzi non consecutivi, e quindi abbiamo evitato di fare trasposta. In C le matrice sono memorizzate per righe.

mpi_type_vector
prendo numline elementi di tipo float, uno alla volta, e si sposta di dim ogni volta.
ho la prima regola per una colonna di numline, ma ogni send deve mandare tutto il blocchetto numxline x numline, quindi devo mandare in una sola send.
Se mando gli stessi dati con più send costa di più che se li mando tutti insieme.
col commit ho la regola pronta. prelevo numline float.

poi usa type_hvector
il parametri che ci dice di quanto spostarsi di quanto spostarsi, glielo diamo in termini di byte. il dataype quì è il blocco numlinexnumline float presi per colonne.

per chi riceve invece, quando arrivano numline x numline float, li deve mettere per righe non per righe consecutive.

ci sono 4 send e 4 receive
sarebbe meglio fare meglio tutte le send che sono sincrone, e poi le 4 riceve che in questo esempio sono bloccanti.
possono esserci deadlock.

datatype non sono tipi primitivi ma delle regole
se stanno in una send indica come prendere i dati e impacchettarli
nella riceve mi dicono come prenderli e metterli a posto.
la primitiva dice:
quanti pezzi prelevo, da quanti elementi elementari consecutivi, di quanto mi devo spostare in memoria dall'indirizzo di memoria precedente.

con mpirun lancio un certo numero di istanze di quel processo.
se fai mpi run -np 4 -l
-l ti stampa chi è il processo che fa le stampe.

l'ordine dei risultati è a caso.

gruppi
un gruppo è un insieme di processi, ma da solo serve poco, gli serve il contesto di comunicazione, oppure possiamo dargliene più di uno.
la creazione di un gruppo si può fare localmente, mentre le operazioni di creazione di un communicator sono di tipo collettivo.

mi estrae il gruppo.

coi communicator e gruppi posso fare partizionamento di lavoro.

### Lezione 16 - 29/10/2024
esercitazione mpi. silenzio assoluto.

### Lezione 17 - 30/10/2024
continuiamo mpi.

Le operazioni collettive coinvoglono più processi e c'è bisogno del concetto di gruppo. Ci sono delle primitive in cui a partire da un gruppo inziale possiamo creare nuovi gruppi. Sono operazioni locali. Bisogna estrarre il gruppo dal vecchio communicator, e specificare il nuovo gruppo specificando i ranghi del vecchio gruppo. nagg cpt nient.
con MPI_comm_group estrae il gruppo dal communicator.

Per evitare di estarre il gruppo ecc si può usare anche mpi_comm_split.
es se ho 9 processi, ne escono 3 communicator con 3 processi ciascuno.
Il fatto di appartenere a nuovi gruppi non cancella le appartenenze di partenza, ad esempio fanno sempre parte di mpi_comm_world.

Vediamo le comunicazioni collettive.

bisogna specificare il communicator per stabilire quali sono i processi coinvolti nella comunicazione. Il communicator lo passeremo a queste primitive che sono di tue tipi:
- asimmetriche: prevedono identificazione di un processo root. quindi oltre al communicator che definisce chi sono i processi, definisce anche chi è il processo root. La più semplice è la primitiva broadcast, che invia gli stessi dati a tutti i processi di appartenenza al communicator. Nella foto il processo 1 è quello che prende i dati dalla sua memoria e li manda a tutti gli altri. Di solito il datatype dei riceventi è uguale per tutti, poi vedremo qualche trucco. Tipicamente si può usare nella fase iniziale di comunicazione (es. un processo acquisisce dati iniziali e li vuole distribuire a tutti gli altri processi). Ci sono anche altre primitie asimmetriche come gather e scatter, c'è una distribuzione di informazioni, chi invia quindi invia un pezzo di informazioni agli altri, es. se root ha un vettore di 100 interi, tramite scatter distribuisce ad esempio i primi 25 interi al processo p0, poi p1, p2 e p3; la regola di distribuzione è in parti uguali e dipende dai ranghi. Di solito si usa quando un processo root avrà ad esempio un vettore o matrice che vuole distribuire dando un pezzo a ciascuno, ognuno farà una parte del lavoro. Scatter distribuisce e gather raccoglie i risultati. 
Queste primitie collettive devono essere eseguite da tutti i processi coinvolti, nonostante sembrerebbe lo faccia solo il root, lo devono fare tutti (ovviamente tutti passano lo stesso valore di root), quindi anche se è asimmetrica tutti la eseguono (non devo fare if myrank=root allora la eseguo). Quindi tutte le collettive comunque sincronizzano i processi, la broadcast termina quando tutti l'hanno portat a atermine, quindi le primitive di comunicazione e calcolo collettivo sincronizzano anche i processi. Nella foto, gli ultimi due parametri della scatter nota che sono root e communicator; i primi tre parametri ovviamente riguardano i dati da mandare, e riguarderanno solo il processo root, mentre i parametri di ricezione riguarderanno i riceveneti, come metteranno a posto i dati, sono uguali per tutti; se invece vogliamo differenziare un pò, possiamo usare mpi_scatterv:
i parametri di invio sono array, quindi posso diversificare il pezzo che mando a ciascun processo, esempio posso mandare 10 interi a p0, 20 a p1, 30 a p3, ecc, e gli spiazzamenti, li gestiamo tramite quel parametro displs che è sempre un array, che indica da dove iniziare a mandare i pezzi ai processi. Nel manuale fa anche vede come una primitiva collettiva si può trasformare in una comunicazione punto-punto. 
guarda come si vede la differenza tra scatter e scatterv capo.
nota che nell'esempio di scatterv ogni processo di fa un proprio datatype ognuno con 100-myrank elementi da ricevere e li mette in colonna. Le collettive le usiamo al posto delle punto-punto perchè speriamo le implementazioni siano più efficienti, rendo più leggibile il codice anziche fare un ciclo con delle send e recv. Si usano all'inizio di una operazione di distribuzione e alla fine quando devo ricostruire il risultato di un operazione di calcolo.
- simmetriche: le operazioni simmetiche sono primitive in cui è come se i processi sono tutti root, esempio all_gather, che mi consente di raccogliere pezzi di risultati elaborati singolarmenti; ognuno mette il proprio pezzo e alla fine tutti avranno lo stesso dato finale in memoria, il buffer finale avrà i contributi di tutti i processi, sempre con la stessa regola. L'ultima primitiva simmetriche è all_to_all, in cui c'è uno scambio tutti a tutti, simile a quanto visto con la trasposta, quindi tutti hanno un dato iniziale e ne ottengono un altro che sarà il risultato di uno scambio.

Vediamo le operazioni di calcolo collettive. Queste comunque richiedono delle operazioni di comunicazione, e consentono però di effettuare elaborazioni, ognuno mette un dato e poi viene fatta un operazione. Lo standard mpi non stabilisce la regola con cui si fa lo scambio.
Abbiamo operazioni di:
- reduce: ognuno mette un dato, viene fatta un operazione come max, somma, ecc, e viene restituito il risultato a un processo root o a tutti (tramite la versione all_reduce, quindi tutti mettono il proprio valore e il risultato viene restituito a tutti).
es. voglio fare somma di un vettore di interi, il vettore somma viene restituo al processo root in questo caso. op indica il tipo di operazione.
le ultime due operazioni sono utili, ritornarno il valore massimo o minimo collettivo e il rango del processo che inserito quel valore massimo o minimo. Il parametro op però lo possiamo anche definire noi, tramite altre primitive, ad esempio posso creare una formula ecc, però tale operazione deve sempre godere di proprietà commuttativa e associativa, ciò vuol dire che si possono combinare i valori in un ordine qualsiasi e anche raggruppandoli, questo influenza la qualità e le performance dell'implementazione.
- scan: l'operazione collettiva si effettua su sottinsieme di processi. ad esempio coinvolge i primi i processi.
non c'è root, bene

17 lezioni senza pausa bravo rocco!.

ha cacciato un esempio con MPI_Irecv che sarebbe una receive non bloccante, seguita da send e da mpi_wait, che prende in ingresso il parametro restituito dalla receive non bloccante, e in questo esempio ha anche creato un altro gruppo per far vedere.

Tra le altre cose messe a disposizione da mpi, abbiamo le topologie.
Ci sono primitive che consentono di creare topologie. Intendiamo dare una struttura topologica ai processi che fanno parte dell'applicazioni.
Se ad vogliamo vedere i processi non più come piatti (es. da 0 a 10), ma li vogliamo vedere topologicamente collocati ad esempio su una matrice o su un albero. Chiaramente queste topologie sono virtuali, quindi l'applicazioni è tale che i dati sono distribuiti a processi che possono stare lontani o vicini (es. processi che stanno sulla stessa riga di una matrice). Questo può rendere il codice più comprensibile. C'è quindi una struttura privilegiata tra processi, e questo può dare anche un idea tra informazioni scambiate tra processi vicini. Ricordiammo che l'ultima fase dell'app distribuita era il mapping dei processi sui nodi, e quindi se abbiamo un implementazione smart, possiamo allocare i processi vicini su nodi vicini, quindi la topologia virtuale la posso sfruttare nel mapping. Nodi vicini vuol dire nodi che hanno costi di comunicazione minore.
Queste cose sono difficili da implementare, chi ha definito lo standard giustamente nn se ne fotteva delle implementazioni.

Vediamo alcune topologie, alcune sono predefinite, quindi ci sono delle primitive per definire topologie a griglia classiche, di dimensioni qualsiasi, come matrici, cubi, ipercubi ecc.
Il valore restituo da una primitiva che crea una topologia è un nuovo communicator.
comm_old è il communicator iniziale, comm_cart è quello nuovo in cui c'è lo stesso gruppo di processi, ma che contiene informazioni sull'aspetto topologico di tipo griglia. Sicuramente oltre al communicator iniziale dobbiamo passare ndims, ossia di quante dimensioni deve essere la griglia, ad esempio in figura ci sono 12 processi inziziali, che vogliamo far diventare un gruppo di processi in un communicator che li vede topologicamente come una matrice 4x3.
il secondo paraemtro dims è un array che indica quanti elementi per ogni riga o colonna, parametro periods indica se è periodica, ossia ad esempio se il processo 0 è collegato all'ultimo, quindi se voglio chiudere le righe o le colonne; reorder è un parametro aggiuntivo che indica che i nostri 12 processi da questo momento in poi devono essere considerati con la nuova struttura topologica definita.
non avevo capito dims okkei.

12.49 a vulim frni oggi.

ovviamente ognuno può creare la topologia che vuole lui, ad esempio un grafo o un albero.

### Lezione 18 - 30/10/2024
14.23 riprendiamo. stamm a 5 di noi oggi o teng di faccia a rocco.

in MPI una topologia rappresenta un communicator in cui i processi hanno una relazione topologica, come a griglia, albero ecc.
Alcune topoligie sono predefinite, ma possiamo creare quello che vogliamo, ovviamente poi bisogna valutare le prestazioni.

Una volta creata la topologia, possiamo chiamare primitive per chiedere informazioni, come le coordinate ecc.
ad esempio cart_shift, vogliamo fare uno shift dei processi lungo una direzione e con un certo passo. Quindi ciascun processo attiva questa primitiva, e la primitiva restituisce rank source e rank dest, ossia quali saranno i processi con cui voglio parlare se voglio fare uno shift, nell'esempio 20 chiama la primitiva, vuole fare uno shift per colonne verso il basso di 2, quindi 18 diventa source e 22 destination.
Ovviamente sta roba la posso pure fare con qualche conto a mano e fare delle send e recv, ma ne perde la leggibilità del codice.

Vediamo un esempio di prodotto righe*colonne matrice con topologie e fatto in maniera distribuita.
Ogni blocchetto di matrice verrà distribuito a processi.
Vediamo un esempio con matrici 3x3.

Supponiamo le matrici A e B vengano lette interamente e suddivisa in blocchetti che sono A00 che và al processo 0, A01 và ad 1, ed anche per B, quindi ogni processo ha un blocchetto sia di A che di B.

Ogni processo deve potersi calcolare il proprio pezzo di C, a esempio il processo 0, che ha A00 e B00, può calcolare C00, ecc.

Vogliamo sicurmaente usare una topologia bidimensionale, quindi i 9 processi li collocchiamo nella matrice 3x3.

consideriamo c00, esso è dato da prima riga di A per prima colonna di B, quindi il processo 0 ha bisogno che i processi gli passino A01,A02,B10,B20, quindi i pezzi di A che stanno sulla sua riga, e pezzi di B che stanno sulla sua colonna, ovviamente lui dovrà anche inviare i suoi pezzi in possesso agli altri.
anche c01 ad esempio, il processo che ha A01 e B01 deve scambiarsi dati coi suoi vicini di riga e colonna.
Quindi le comunicazioni devono avvebnire tra processi della propria riga e della propria colonna, quindi possiamo pensare a una topologia.

Vediamo l'algoritmo sincronizzato come funzione.
per ogni processo devo fare 3 prodotti righe per colonne.
Dobbiamo fare 3 giri in questo esempio, o in generale la radice quadrata di n_proc giri.
Nel primo giro, i processi sulla prima riga fanno, in particolare il primo processo prende il suo pezzo di A e lo manda agli altri sulla sua riga. sulla seconda riga chi ha A11 farà broadcast, e infine sulla terza riga A22 farà il broadcast. Dopo il broadcast si fanno i calcoli e avremo caclolato il primo pezzo del risultato, sono 3 pezzi in totale.
per fare il secondo prodotto, ho bisogno di fare uno shift verso l'alto di tutte le Bij, e poi devo fare un altro broadcast (vedi fase due in verde). Per il terzo passo, devo rifare shift verso l'alto e broadcast, e cosi via per n volte, in base alle dimensioni della matrice.

Vediamo il codice mpi per questo algoritmo.
dblock sarebbe dim/n, quindi ogni processo ha la sua matrice A,B,C di dimensione DIM/n, ossia il proprio pezzo ognuno, e anche T che è una matrice di appoggio per i conti. A e B sono gli input. Supponiamo ci sia gia stata una distribuzione di A e B nel codice che non vediamo a tutti gli n processi; quindi supponiamo ogni processo abbià gia i dati in A e B.
A questo punto, dato che le comunicazione coinvolgono tutte una matrice dblock x dblock, viene create un data datatype (blocktype nel codice), che si usa sia nelle comunicazioni broadcast che di shift.
A questo punto dobbiamo creare la topologia bidimensionael nxn.
Si procede a costuire il nuovo communicator a cui assegniamo la topologia bidimensioanle, con ogni dimensione che avrà n elementi, lo fa con MPI_cart_create, con 2 dimensioni (bidimensionali), dims è un vettore che dice quanti elementi ci sono su ogni riga, in questo caso è un vettore con tutti n, periods è di tutti 1, quindi la topologia è chiusa.
A questo punto si creano dei communicator in cui vogliamo mettere solo i processi di ogni riga, perchè ci serve dopo nelle operazioni di broadcast, che riguardano solo i processi della stessa riga, cosi che quando ci saranno delle send non dobbiamo farle a tutti i processi. Lo facciamo con la primitica cart_sub, che consente di divididere la topologia bidimensionale per righe, quindi produce un communicator per riga; nota che ognu processo esegue questo codice, quindi ogni processo riceve il communicator che si chiama 'my_riga', quindi il processo 0 riceve un comm in cui si trova solo coi processi 1 e 2, ecc.

ogni processo nel nuovo communicator myriga_comm si calcola il nuovo proprio rango nel nuovo comm e le coordinate.
myriga=coord[0] indica quel processo su che riga sta.

L'ultima cosa da fare è capire chi sono i partner dello shift di B. abbiamo visto lo shift è verso l'altro, quindi ogni processo invia a chi sta sopra di lui e riceve da chi sta sotto di lui, e questa informazioni la chiediamo alla topologia con cart_shift, in cui specifichiamo di fare lungo la dimensione 0 (colonne), gli diamo il comm della topologia, di passo 1, in questo caso col segno -, quindi -1 indica verso l'altro (+1 era verso il basso), e la primitiva restituisce source e dest.
Finalmente iniziamo la comunicazione e la elaborazione.
Vediamo il ciclo fatto da 3 fasi, c'è un for di n interazioni, con n che è la radice quadrata di DIM. Ci serve ora capire chi fa broadcast, che però cambia ogni volta, la prima volta il broadcast lo fanno i processi sulla diagonale, le altre volte lo fanno i processi spostandosi di 1 a destra sulla riga, quindi 01,12,20. Ci calcoliamo quindi un root per ogni riga, e fa riferimento al communicator riga, che ci serve per passare insieme al communicator myriga_comm; il root lo calcola con root=(s+myriga)%n. DOpodiche il processo root copia la matrice A in una matrice di appoggio T. Dopodiche si procede a fare broadcast, a cui passa come communicator la riga, l'oggetto da trasferire è una matrice dblock x dblock. Dopodiche si procede con il primo prodotto, questa è la fase prettamente parallela. Dopodichè c'è la fase di shift, che sarebbe il roll nel codice.
Si usa mpi_sendrecv_replace, in cui si usa la stessa locazione di memoria per mandare e ricevere dati, in cui si manda sempre la matrice di datatype blocktype, e si usano dest e source fornite prima da cart_shift, all fine di questa primitiva, tutti i processi hanno un nuovo pezzo di B; all'iterazione successiva cambia chi farà il broadcast, dato che cambia root.
c'è un if(s<n-1) perchè l'ultimo shift non serve, potremmo anche farlo se vogliamo rimettere in B a posto tutti i valori iniziali.

Si può ovviamente fare pure senza le topologie, però peggiora il codice, peggiora il flusso di primitive di comunicazione.

faremo esercitazioni con calcolo e comunicazioni collettive, e topologie.

### Lezione 19 - 5/11/2024

Ci manca un solo paradigma per poter ufficialmente progettare e scrivere applicazioni distribiuite (client server, shared memory, message passing) e infine quello che si basa sul concetto di mobile computing, in cui abbiamo processi che durante l'applicazione si spostano sui nodi. E' un tipo di paradigma che ha molte potenzialità ma molti difetti che lo rendono poco adatto a chi vuole ottenere miglioramenti prestazionali per applicazioni scienitifche. Questo paradigma si sposa bene con gli agenti mobili che hanno avuto abbastanza successo (lo vedremo con JADE, per programmare col paradigma ad agenti). Prima di vedere quest ultimo paradigma però, dobbiamo entrare nella seconda parte del corso, ossia nella prima parte abbiamo visto come scrivere un app, adesso nella seconda parte vedremo problemi trasversali ai paradigmi, come naming, sincronizzazione distribuita (mutua esclusione ecc), che sono comuni a tutte le applicazioni distribuite. Il problema del naming lo abbiamo già incontrato in rpc e java rmi, riguarda la possibilità di usare nel codice non indirizzi ma nomi logici, come ad esempio in javarmi assegnavamo a dei servizi alcuni metodi remoti tramite un nome logico, che doveva schermare indirizzo ip e numero di parte in cui la parte server (es. di javarmi) si trova in attesa da parte del client.
Quando parliamo di naming, il nome logico è una stringa
Ogni risorsa è tipicamente usata in diversi punti di accesso, e ogni punto di accesso è identificamento da un indirizzo. Una risorsa può avere diversi endpoint associati a indirizzi diversi.

Un acccess point è un modo per accedere e operare sulla risorsa.

Ci interssa come, dato un nome logico (stringa) e dato il tipo di access point, come fa un sistema di naming a fare in modo efficace ed efficiente la traduzione.

Ci possono essere servizi centralizzati che tiene traccia delle corrispondenze, un server che tiene traccia dinamicamente delle associazioni.
Ovviamente essendo centralizzato il problema è l'affidabilità, es. se il registry di javarmi si interrompe e viene fatto ripartire, si perdono le informazioni precedenti. Un altro problema è collo di bottiglia, troppe richieste.

Ci può essere anche una soluzione centralizzata ma replicata, in cui si vuole mantenere la semplicità del sistema ma combattere un pò di affidabilità duplicando informazioni, anche se si creano problemi di consistenza, ci servono soluzioni per distribuire informazioni alle repliche; inoltre il sistema centralizzato ma replicato rende l'accesso più veloce, l'utente accede a una copia dei dati più vicina, quindi risolve anche colli di bottilgia,

Infine, c'è la soluzione distribuita più complessa da realizzare, ci vogliono protocolli più complicati.

Questo è in generale l'architettura di un sistema di naming, adesso dobbiamo vedere come è fatto il naming del dettaglio, es. come sono i nomi ecc.

Naming semplice, i nomi sono sequenze di caratteri che non aiutano il sistema di naming nella traduzione.
Strutturato come file system e dns.
Il terzo modo è usare un insieme di attributi, per semplificare la traduzione. Per ciascuno di questi modelli ci sono diversi modelli reali.

Vediamo alcuni esempi di soluzioni per sistemi di naming, partiamo da naming semplice.
traduzione di indirizzo ip e mac, in una rete locale quando un nodo vuole contattarne un altro sulla rete locale, o vuole contattare il gateway per mandare il messaggio all'esterno, si parte dall'ip del destinatario (es. in locale), e quell'indirizzo ip non serve a contattare l'host destinatario, perchè in realtà c'è bisogno l'indirizzo mac della macchina che ha come nome logico quell'ip.
Il sistema non è centralizzato ma distribuito in maniera basica, tramite il protocollo arp, in cui viene mandata una richiesta su quale macchina nella rete locale ha quell'ip mandando un messaggio di broadcast.

Un altro esempio è il mobile ip, in cui tipicamente ai portatili viene assegnato un doppio indirizzo, uno corrente e uno di casa.
Quando vengono inviati messaggi al pc che si è spostato, viene informato un terzo servizio che memorizza dove si è spostato quel nodo, e poi lo reindirizza lì. E' un approccio

Un altro esempio sono le DHT, in cui vogliamo risolvere il problema di gestione delle risorse in una rete, dobbiamo sapere qual è il peer che ha una copia dell'informazione che si sta cercando. In questi sistemi sia nodo che risorsa sono caratterizzati da un numero, si stabilisce quindi una regola di associazione tra risorse e nodi.
gli id si producono tramite hashing.
L'associazione in questo caso (chord), è che ogni nodo possiede le risorse dal nodo nella rete con il numero immediata successive, ad esempio nella foto le risorse 22-27 sono custodite dal nodo 28.
Ovviamente i nodi possono entrare e usicre dalla rete, ci sono dei meccanismi per riassegnare le risorse. Il naming in questo caso risolve una sorta di funzione 'succ', in cui viene richiesto chi è il succ di una risorsa, ossia il numero di nodo che custodisce quell'informazione. La traduzione non è cnetralizzata, è un sistema di peer computing distribuiti, ed in qualsiasi nodo viene fatta questa interrogazione, questo nodo deve essere in grado o di rispondere direttametne o chiedere ad un altro peer che conosce, questo meccanismo funziona perchè ogni nodo memorizza una tabella, in cui sulla prima colonna ci sono un numero di risorse, e sulla colonna affianco, che indica chi custodisce la risorsa i-esima (la formula è p (nodo corrente) + 2^i-1), la crescita quindi è esponenziale. La prima riga contiene sempre il nodo dopo quello attuale, ad esempio nella figura il prossimo nodo dopo il nodo 4 è il nodo 9. Questa tabella quindi memorizza informazioni vicine e qualcosa sui nodi lontani, cosi anche se viene chiesta una risorsa lontana, sà indirizzare la richiesta. Esempio nodo 28 in cui cerca la risorsa 12, si ferma alla riga 4 perchè sulla riga 5 c'è 14 che è maggiore di 12.
Anche qui i nomi non danno informazioni.

Un ultimo esempio di sistema di namign semplice, con nomi semplici, è l'approccio gerarchico. Più saliamo nella struttura gerarchica e più troviamo chi conosce le risorse nel sottoalbero di cui quel nodo è radice. Le foglie sono le risorse, i nodi contengono informazioni tali per cui posso trovare la risorsa che mi serve. root sà tutte le risoCi rse dove sono. Le risorse possono essere duplicati.
Un nodo radice di un sotto-albero contiene una entry per ogni entità E.
Il location record contiene un puntatore al directory node del successivo sotto-dominio del livello più basso che contiene l’entità E.
Vediamo la ricerca: si sale di livello finchè non troviamo qualcuno che conosce quella risorsa.
la risorsa cercata è quella rossa.
bisogna anche poter inserire una risorsa:

Vediamo il caso in cui i nomi hanno una struttura.
Nel caso il nome rifletta una struttura gerarchica, come nel caso del file system.
Tramite delle ricerce in directory e sottodirectory posso arrivare all'entry relativa a quel file, e poi devo accedere all'inode per gestire quel file.

Vediamo un esempio di spazio dei nomi distributo - DNS.
In questo caso, dato un nome logico, vogliamo ottenere un indirizzo ip, associato ad esempio a un webserver ecc.
In questo caso il nome logico non può essere qualsiasi ma è caratterizzato da una struttura, ad esempio c'è il toplevel domain, che indica il server a cui rivolgersi se non troppo l'indirizzo in una cache ecc. Il sistema è distribuito e replicato, perchè spesso la traduzione una volta risolta viene salvato in una cache in un server dns vicino a chi ha fatto una richiesta.
Tutti conoscono i dns server dei top level domain, nell'esempio se richiesto ftp.cs.vu.nl, se il dns server a cui ho chiesto non conosce l'associazione, bisogna rivolgersi al dns server che gestisce il top level domain in questo caso nl (quindi dell'olanda), che sicuramente conosce i dns server dei sottodomini del toplevel domain, ad adempio sicuramente conosce 'vu' nell'esempio. Una volta arrivati a cs, troviamo il responsabile della coppia nome logico/ip del server ftp che cercavamo, lo abbiamo fatto tramite i NOMI, che ci hanno aiutato.
Di solito la risposta ci viene fornita dal primo dns a cui abbiamo chiesto, ci può essere una variante ricorsiva che nagg cpt.

Naming su attributi.
L’entità è descritta in termini di coppie (attributo,
valore). Ad un’entità possono essere associati un
insieme di attributi
attributi.
• Il compito del sistema di naming è di restituire una
o più entità che corrispondano alla richiesta fatta
dall’utente in termini di uno o più attributi.
• I sistemi di namingg basati sugli
g attribuiti sono noti
come directory service.
• Si basano su diversi modelli per la descrizione
delle entità ( ad es. Resource Description
Framework RDF).

fine naming in 1 ora.

voliamo al mobile computing.
Ci sarà un middleware per scrivere applicazioni ad agenti mobili, e un supporto a tempo di esecuzione.

### La mobilità del codice nel calcolo
parallelo e distribuito

Il termine mobile computing si riferisce a cose diverse:
- mobilità di utente: possibilità di usare i propri dati o servizi a cui è abbonato in maniera indipendente dal punto di accesso alla rete o dal dispositivo usato (es. sim del teleofono, il gestore di telefonia mobile ci consente di usare il servizio e dal tipo di terminale usato), la scheda del decoder di sky ecc.
- mobilità di terminale, i terminali devono poter operare cambiando punto di accesso e tecnologia, è legato al concetto di ip mobile, quindi il dispositivo è ancora contattabile in base a dove si trova e indipendente dalla tecnologia (wireless ecc).
- mobilità di codice, quella che interessa a noi, ossia la possiblità di scrivere applicazioni distribuite in cui tipicamente uno o più processi dell'applicazione possono ad un certo punto sospendere la propria attività ed esecuzione su una macchina e riprenderlo su un altra macchina (strong mobility). Perchè spostarsi? ci sono diversi motivi; ci sono i crawler che vanno in giro a cercare informazioni per categorizzarle sui motori di ricerca; avere un codice che si sposta dove stanno i dati è più efficiente di un codice su un nodo che deve raccogliere dati; un esempio è appunto la ricerca di informazioni distribuite, anzichè collezionare dati sposto solo il codice (che è la parte leggera rispetto ai dati). Tipicamente il processo che si sposta, si sposta dove stanno i dati e si porta appresso lo stato dell'elaborazione precedente e quindi non riparte sempre da zero; questo era per la mobilità forte, e quindi il middleware che consente di spostare processi, non è banale da implementare, perchè spostare processi non vuol dire spostare solo il codice ma anche spostare stato di elaborazione, informazioni memorizzato, accessi a risorse; inoltre anche il processo che è un programma in esecuzione è diverso tra i sistemi operitivi (ognuno ha il proprio process control block, che contiene informazioni sui processi in esecuzione), cambiano anche spazi di indirzzamento, stack ecc, tutte queste non sono informazioni standardizzate che mi posso portare appresso, ci deve pensare il middleware; per questo questa mobilità forte è difficile, di solito di parla di MOBILITÀ DEBOLE, in cui non si sposta tutto il processo, ma solo il codice con qualche informazione aggiuntiva. La piattaforma che useremo noi, jade, ci offre una mobilità debole.
i Siti sono i nodi di elaborazione, i processi sono i componenti attivi, e i componenti passivi come file, codice, driver ecc.
Nei paradigmi che abbiamo visto, ad esempio in client server, non si sposta niente:
c'è un interazione tramite richieste.

esempio remote evalutation:
qui si spostano degli script, quindi sequenze di comandi.
In questo esempio loise ha solo la ricetta, quindi invia la ricetta a christine, che esegue tutto il resto e poi restituisce la torta.
simile a java rmi.

finalmente arriviamo alla mobilità del codice: MObile Agent
fixare slide.

recap paradigmi mobili. ci interessa mobile agent a noi. Il processo (non il codice) si sposta tra le macchine.

Il processo è ovviamente codice + stato di elaborazione (che si compone di stato di esecuzione, quindi program counter, stack, tutto ciò che è memorizzato nel process control block, e poi c'è anche una parte di data space, es. apre dei file).

Alcuni middleware consentono di scrivere applicazioni in cui ciò che si trasferisce tra un nodo all'altro è codice+stato di esecuzione.

strong non semplice da implementare.
weak Più semplice e altrettanto utile è quella debole, si sposta solo il codice.

baasta 10.49 amm fa 4 ore.

### Lezione 20 - 6/11/2024
esercitazione operazioni collettive mpi.

### Lezione 21 - 6/11/2024

14.15 orologio svizzero.
stanco stammo a 6 di noi triste

riprendiamo da slide di mobilità del codice.

abbiamo visto mobilità forte, in cui dovremmo spostare processo quindi codice più altre informazioni come stato di esecuzione.
esistono dei middleware per fare ciò, ma è complicato.

abbiamo poi i middleware che ci offrono mobilità debole, in cui viene trasferito solo codice (che senza stato di esecuzione riparte da zero), anche se in certi casi (come in jade), dato che il codice si trasferisce tramite la serializzazione di oggetti (quindi codice+dati, o comunque object state, quindi i campi degli oggetti con i propri valori), quindi quando avverrà il trasferimento, il supporto a tempo di esecuzione prende gli oggetti e li serializza.

Vediamo quali caratteristiche di questo paradigma di mobile computing lo possono rendere interessante per alcune app, e cosa invece lo rendono poco adatto per sfruttare il parallelismo.
Le problematiche sono legate sicuramente alla sicurezza, ci arriva codice dall'esterno senza sapere autore ecc; un altro problema è che spesso ci troviamo ad avere a che fare con nodi eterogenei, quindi con o.s diversi; i vantaggi invece sono che questo codice dovrebbe essere in grado di interfacciarsi col nodo che lo sta ospitando in quel momento, quindi applicazioni di questo tipo devono poter rendersi conto di quali sono in quel momento le prestazioni/carico dello specifico nodo in cui sono in esecuzione; load balancing dinamico, prendono decisione spontaneamente.
Un altra cosa utile di questo paradigma è il concetto di agente, a cui fornisce delle specifiche per effettuare dei determinati servizi.
fault tolerance, è in grado di accorgersi che un pezzo dell'app non è più funzionante e si può adattare.
Vediamo i campi applicativi che sfruttano questi vantaggi. In generale tutte le app in cui conta la località nell'accesso alle risorse, come se il processo/agente si sposta verso i dati; app in cui sono utili load balancing, fault tolerance; aggiungere intelligenza ai dati esempio, aggiunge informazioni a dei dati (es. un modulo da compilare, se oltre al modulo ho del codice che aiuta l'utente a compilare il modulo).

poco utile per parallelizzare applicazioni scientifiche.

Il paradigma mobilità del codice è collegato a un modello di programmazione chiamato modello ad agenti; se inoltre gli agenti sono mobili, il paradigma allora sfrutta il mobile computing; gli agenti però possono non dipendere per forza dalla mobilità.

Vediamo quali sono le caratteristiche affinche un app o un processo possa essere visto come un agente:
E' un programma/processo, in esecuzione in un determinato ambiente di esecuzione, che ha la capacità di effettuare in maniera autonoma (programmata), con la possibilità di decidere cosa fare in base a come cambia l'ambiente di esecuzione. Queste azioni autonome tipicamente hanno uno o più obiettivi ed è reattivo, quindi percepisce l'ambiente e risponde ai cambianti per raggiungere tali obiettivi; quindi deve poter capire i cambiamenti nel'ambiente di esecuzione e regolarsi di conseguenza; un agente deve essere anche proattivo, quindi deve essere in grado di prendere decisioni autonome per raggiungere gli obiettivi. Infine, le abilità sociali, è interagire con altri agenti o col programmatore.

queste sono le caratteristiche essenziali degli agenti.

jade ci offre un middleware per scrivere applicazioni ad agenti con in più la possibilità di mobilità.
momento curioso, se gli agenti li scriviamo con prolog, diventano intelligenti!!.

Si è cercato di ottenere un minimo di standardizzazione, che usano piattaforme e middleware diversi. La FIPA ha fornito delle indicazioni per chi vuole scrivere app ad agenti. Tutti i middleware che offrono supporto per app ad agenti devono avere questi componenti per essere aderenti allo standard (ci sono pochi vincoli nello standard). Il management component è una sorta di gestore, e tiene traccia di dove l'agente è in esecuzione, directory service contiene un elenco di servizi, quindi gli agenti possono registrare i propri servizi su questo componente, e altri agenti possono anche cercare agenti che offrono quel servizio; infine c'è un componente che permette agli agenti di parlare tra di loro, dovranno inviarsi dei messaggi. Bisogna gestire nascita e morte di agenti ecc.

Un altra standardizzazione è stata fatta anche per stabilire come gli agenti parlano tra di loro, tramite un linguaggio ACL, che standardizza le informazioni che vengono inviate tramite un messaggio tra agenti, che devono aiutare chi riceve il messaggio (sequenza di byte) a interpretarli.
Uno dei parametri principali è lo scopo del messaggio, si usano delle costanti che determinano l'obiettivo del messaggio inviato, quindi l'agente che lo riceve deve sapere perchè un agente gli ha inviato un messaggio.


abbiamo finito intro agenti e agenti mobili, adesso vediamo un middleware JADE.

JADE è un middleware sviluppato da TELECOM ITALIA, basato su java, open source, che consente di scrivere applicazioni ad agenti mobili in java (prestazioni non eccellenti ma portabili) e anche FIPA compliant, quindi segue quello standard. Esso offre un supporto a tempo di esecuzione, che contiene a sua volta gli agenti, che saranno i componenti visti prima, directory service ecc, quindi il supporto a tempo di esecuzione stesso è un agente, consente scambio di messaggi, creare agenti ecc. Oltre a cio, per ospitare l'app ad agenti, jade offre una libreria per scrivere app ad agenti mobili, sicuramente ci aspettiamo di trovare una classe Agent messa a disposizione!. Noi scriveremo classi che estendono agent!. Infine, jade include anche una suite di tool grafici per amministrare gli agenti graficamente.

vediamo l'architettura
abbiamo un insieme di container (non di virtualizzazione), quindi una sorta di daemon che è in grado di ospitare agenti sui diversi nodi, ci sono quindi una o due piattaforme, ed ogni piattaforma è fatta da tanti container, ogni container può ospitare agenti; ogni piattaforma deve avere un main container, che è un container che ospita i componenti essenziali, direcotry service, il componente gestore; quindi quando attiviamo una piattaforma stiamo attivando un main container con questi agenti essenziali, poi posso anche creare altri contianer sulla stessa piattaforma per diversi nodi.
Inoltre, il main container gestisce gli agenti su tutta la piattaforma, quindi l'ID dell'agente sarà tipo nome@nome_piattaforma, quindi l'agente gestore deve evitare agenti con lo stesso nome sulla stessa piattaforma, ovviamente possono esistere su piattaforme diverse.

gli agenti su un container possono spostarsi anche su altri container, anche su un altra piattaforma.

l'agente DF ha lo scopo di mettere in contatto agenti che non si conoscono.

Un applicazione jade è fatta da uno o più agenti, identificati da un nome unicovo. Sono dotati di alcuni comporamenti (cose che sanno fare), quindi quando nasce ha un suo pool di comportamenti attivi, che vengono eseguiti uno alla volta. Il supporto a tempo di esecuzione di ogni agente esegue un comportamento alla volta,

### Lezione 22 - 12/11/2024
rocco inizia nonostante siamo in 3 ma ha visto due borse vuote che stanno giu altri ragazzi. bravo!!

jade è un middleware.

Paradigma ad agenti o ad agenti mobili.
Gli agenti sono processi con caratteristiche speciali di: autonomia (prende decisioni in base all'ambiente circostante e informazioni da altri agenti per raggiungere con gli altri un obiettivo); devono poter interagire col sistema su cui sono in esecuzione in quel momento, devono poter prendere decisioni anche sull'ambiente in cui si trovano.

Per sfruttare questo paradigma ci serve un middleware.

Nel corso del tempo i middleware per gli agenti sono stati diversi, poi la fipa ha pensato di fare una standardizzazione, stabelendo delle regole di interperabilità tra sistemi ad agenti abbastanza minimalista, bastano quei 3 componenti visti nell'architettura: manager dei componenti, directory service (per far conoscere tra di loro gli agenti in base ai servizi che offrono), e infine l'agente relativo alla comunicazione (tramite scambio di messaggi).
Per la comunicazione, ci sono dei campi standardizzati da inserire nel messaggio.

Vediamo JADE come middleware.
Jade ci offre un supporto a tempo di esecuzione, che nella pratica vedremo saranno a loro volta agenti che si occupano di comunicazione tra agenti ecc; dopodichè abbiamo una libreria con delle classi che consentono di scrivere app ad agenti (è opensource, possono aggiungere anche delle nuove classi); infine, ci sono dei tool grafici per monitorare e debuggare.

per ogni piattaforma c'è un main container che ospita gli agenti principali (quei componenti fipa).
Con jade possiamo scrivere app ad agenti che lavorano su più piattaforme, ed ogni piattaforma avrà un nome o un numero, e almeno un main container che si occupa degli agenti di quella piattaforma, comunque gli agenti di piattaformi possono comunirare infatti l'id di un agente è tipicamente nome_agente@nome_piattaforma. Gli agenti si possono spostare o clonare (autonomamente o tramite quei tools).

Il DF è l'agente cui gli altri agenti possono pubblicare i loro servizi offerti.

Gli agenti li scriviamo noi, tali classi estenderanno la classe Agent di Jade, ma comunque gli agenti quando nascono non sanno ancora fare niente, finchè il programmatore non gli assegna uno o più comportamenti (cose che l'agente sa fare), ma non durano per sempre. UN comporamento può aggiungerne altri all'agente stesso; questi comportaemnti vengono eseguiti uno alla volta, (non c'è multithread).

Il supporto a tempo di esecuzione di jade, rende operativo questo schema, ossia questo ciclo di vita dell'agente.
Supponiamo di aver scritto diversi agenti e fatti partire in uno dei container della piattaforma; quando un agente nasce, la prima cosa che viene fatta è l'esecuzione del suo metodo setup(), che è un metodo della classe padre di cui dobbiamo fare overriding per il nostro agente; in metodo setup() di solito l'agente viene dotato di un tot comportamenti iniziali da attribuire all'agente. I comportamenti sono anche loro oggetti di classi che estendono classi di jade, dotate di due metodi originali:
- action()
- done()
QUindi dobbiamo sovrascrivere i metodi action() e done() di ciascun comportamento (con una nuova classe behaviour); e quindi l'agente avrà un tot di oggetti di tipo behaviour.
Cosa l'agente fa viene programmato nel metodo action(), e tali comportamenti vengono inseriti in una sorta di pool di comportamenti attivi di tutta l'applicazione; quindi nascita dell'agente significa, dopo aver fatto setup(), anche riempire il pool di agenti. Supponiamo quindi che sono nati diversi agenti, ognuno con i propri comportamenti, e tutti i comportamenti vanno nel pool, a questo punto lo schedulatore di jade, preleverà un comportamento di uno degli agenti dal pool e eseguire il suo metodo action(), e quando questo termina, subito dopo il supporto a tempo di esecuzione, di quel comportamento esegue il metodo done(), che indica se quel comportamento deve ancora far parte delle capacità dell'agente, o se non serve più, e ciò distingue i comportamenti che sono ATTIVI da quelli che sono terminati; se quindi done() restituisce di no, il comportamento viene ributtato nel pool di comportamenti.
Chiamali behaviour ti prego negli appunti.
Potrebbe esserci un agente senza comporamenti che però rimane in vita, infatti un agente non termina se finiscono i comportamenti, ma solo se viene lanciato il metodo doDelete(), che uccide l'agente.

Nei comportamenti si può interagire con gli altri agenti tramite scambi di messaggi con lo standard acl
Quindi l'agente fà solo quello che fanno i suoi comportamenti.
Per mandare i messaggi devono conoscere nome_agente@nome_platform.
gLI Agenti possono interagire anche con la piattaforma, e quindi con quegli speciali, per chiedere per esempio quali sono i container sulla piattaforma disponibili in quel momento e eventualmente spostarsi (sta roba si chiama AMS)

Ricordiamo che questa piattaforma ci offre una mobilità debole,
ifnatti quando noi spostiamo a mano un agente, esso riparte da zero, l'unica cosa che viene conservata è lo stato dell'agente, coi suoi comportamenti, quindi potremmo memorizzare informazioni nei comportamenti.
C'è anche la clonazione per gestire il load balancing e per adattarsi a cambiamenti all'interno della piattaforma, ad esempio se ci accorgiamo che si è aggiunto un container alla piattaforma, si può fare un clone.

andiamo più deep jade. cambiamo slide

Vediamo come si crea la piattaforma di esecuzione distribuita.
cambia la var di ambiente classpath.
Ci basta far partire
java jade.Boot –gui
per lanciare la piattaforma, in particolare un main container con l'opzione -gui con cui parte l'interfaccia grafica.

Se vogliamo arricchire la piattaforma di container, usiamo il comando
java jade.Boot -container
(li spawna sulla stessa piattaforma), si può fare anche su una macchina diversa, come vedi nell'ultimo comando con opzione -host.

scriviamo un agente che estende jade.core.Agent,
che sovrascrive il metodo setup() ossia il primo che viene eseguito.
Nota che questo semplice agente nasce, stampa nome, e fa doDelete() nel setup, quindi muore subito senza comportamenti.

Lo stesso agente con lo stesso .class può dare origine a più agenti con nomi diversi.

MO vediamo i comportamenti.
C'è la classe
jade.core.behaviours.Behaviour
i metodi principali sono action() e done() da sovrascrivere

Dobbiamo quindi creare un oggetto di tipo behaviour, e poi usare un metodo della classe agente che si chiama addbehaviour, che mettiamo nel setup() dell'agente.

addBehaviout() è un metodo della classe agente, ma si può usare anche nel metodo action() dei behaviour, quindi un comportamente può aggiungerne altri, ovviamente servirà un riferimento all'oggetto agente per farlo.


Abbiamo quindi detto che i comportamenti sono eseguiti in maniera sequenziale, la schedulazione esegue un comportamnento alla volta, per rendere le cose più semplici, se li eseguissimo in multithreading nascono problemi di sincronicazzione, mutua esclusione ecc, ed inoltre il fatto che sono eseguiti uno alla volta rende più semplice la parte di mobilità del codice.

Vediamo alcuni comportamenti:
oneshot done restituite true
cyclic done restituisce falso, il comportamento rimane attivo
infine i generic.
Il behaviour è sempre una classe, posso usare trucchi per far eseguire ogni volta qualcosa di diverso, es tramite uno switch.

ha differenti costruttori, in questo caso gli passiamo un riferimento all'agente, ha senso capo, serve a dare all'oggetto behaviour un riferimento all'oggetto agente di cui questo comportamento fa parte, questo riferimento viene memorizzato in un campo myAgent della classe Behaviour, infatti vedi che dopo fa myAgent.addBehaviour.

chatting su altre classi behaviout
ticketBehaviour è ciclico.
wakerBehaviour ha un tempo alla fine del quale attiva il comportamento.


i behaviour una vlta che hanno il myuagent possono comunicare con altri agenti.

per mandare messaggi dobbiamo creare oggi ACLMessagge
già nel costrutturore si specifica subito il purposal, dopodichè ci aggiungo ricevente ecc. alla fine fa setContent per riempire il messaggio e infine fa send(msg), send sempre della classe agent.

Spesso la ricezione di messaggi si affida a un comportamento ciclico, ma non è una soluzione valida dal putno di vista prestazionali, potrei andare a cercare messaggi che non arrivano e consumare risorse per nulle (attesa attiva di un messaggio), si usa il metodo block(), che è un metodo di Behaviour, che marca il behaviour come bloccato, vuol dire che quel behaviour ridiventa attivo quando arriva un nuovo messaggio a quell'agente. quindi evita di perde tempo per andare a guardare sempre nella stessa cosa di messaggi se questo non arriva.

Nella receive un filtro, che specifica il tipo di messaggio che vorrei ricevere.

# Lezione 23 - 12/11/2024
esercitazione jade

# Lezione 24 - 13/11/2024
esempio jade e inizio tempo

# Lezione 25 - 19/11/2024

sincronizzazione

gli eventi fanno parte della stessa problematica, vorremmo ordinarli ma non è possibile usando gli orologi dei singoli nodi, nonostante ci siano tecniche per sincronizzarli, ma dopo un po si sfaseranno lo stesso, ed in molti casi sapere se un evento si è verificato prima di un altro non è sempre necessario.

L'intuizione di lamport è stata di stabilire delle regole per cui, dati eventi di un app distribuita, in cui A si è verificato prima di B, questi devono avere un timestamp (data dell'evento) che riflette il fatto che si siano verificati prima.
Su quali eventi siamo sicuri si verifichi cio? eventi sequenziali in un processo sulla stessa macchina (happens before), altri eventi sono invio e ricezione messaggio su due macchine diverse (A invio si deve verificare prima di B ricezione) e il timestamp di A deve essere sempre minore di quello di B, questo però richiede qualcosa di aggiuntivo, dato che gli orologi sulle due macchine sono diverse, quindi bisogna aggiustare l'orologio della macchina ricevente (portandola di quanto basa avanti), in modo che l'evento B risulti sempre maggiore del timestmap di A.

nota nel caso C e D la regola non è verificata, quindi lamport impone di aggoustare l'orologio della macchina ricevente.

Questo però non serve a far capire in che ordine si verificano gli eventi, anche se uno ha un timestamp minore di un altro, non è detto siano in relazione happens before. non vale la doppia implicazione.

possiamo fare un ordinamento totale degli eventi, che è arbitrario
quindi da solo lamport serve a poco però ci da informazioni su cosa succede nell'ambiente distribuito, se lo riusciamo a sfruttare tramite protocolli o alcune regole nella nostra app, allora possiamo ottenere il risltato voluot, ossia stabilire una sincronizzazione condivisa nella nostra app distribuit,a senza avere orologi comuni o spazio di memoria comune anche.

un ordinamento reale non è mai possibile, ma noi siamo interessati a un ordinamento condiviso.
quando nasce un evento ci attacchiamo timestamp e numero di nodo, poi lo mandiamo a tutti tramite un messaggio, e tutti poi memorizzanno l'evento e poi li eseguano in un ordine condiviso con tutti gli altri, non devo eseguirli man mano che mi arrivano, potrebbero arrivarne altri con timestamp minore, però comunuqe vogliamo che a un certo punto sia in grado di eseguire le operazioni senza aspettarle tutte, ma che sia sicuro che quelle che sta eseguendo sono già ordinate in maniera condivisa, e per ottenere questo risultato ci serve un protocollo, che è il totally ordered multicasting, in cui abbiamo che chi riceve un messaggio con un evento deve mandare un ack non solo a chi gli ha inviato l'evento ma anche a tutti gli altri; se rispettiamo questo protocollo, e facciamo assunzioni sulla rete (i messaggi non si perdono, i messaggi arrivano in ordine, tcp capo); se tutto ciò è vero, la coda di messaggi di un singolo noto inizia a ordinarsi, ed inoltre si può cominciare ad eseguire l'operazione degli eventi sul proprio database a partire da quelli piu vecchi, quindi la coda è ordinato in senso crescente, si prende l'evento dalla cima della coda, nota che anche gli ack hanno timestamp, che in teoria potrebbe avere qualsiasi valore, ma se tutti rispettano lamport, allora avrà un timestamp maggiore.
es. se P1 manda un messaggio con C(15), gli ack saranno almeno C(16) inviati a tutti, e quindi poi il processo P1, prende l'evento, vede che ha tutti gli ack ricevuti, allora è sicuro che lo può consumare, perchè non potranno mai arrivare eventi da altre macchine con timestamp minore di C(16), questo perchè le macchine hanno mandato tutte un ack con C(16), quindi tutte quelle macchine non potranno mai mandare un messaggio con timestamp minore di C(16).

Lamport non cattura la casualità (causa effetto), ossia quella relazione che se A accade prima di B allora C(A) < C(B), ma questa relazione non la possiamo invertire, se guardo solo i timestamp non posso dire che A viene prima di B, quindi guardando solo i timestamp non posso invertire la relazione; la riesco a invertire se complichiamo un po l'etichetta dei tempi associati agli eventi, in particolare associamo un evento non solo un timestamp ma un vettore di timestamp. Vediamo come si costruisce il vettore di timestamp e che proprietà ha per sfruttarlo in applicazioni in cui è importante che queste etichette riflettano il concetto di causa effetto.

App distribuita in N processi, abbiamo vettori timestmaps di N elementi.
Se il processo non ha contatto con altri processi, incrementa o attacca il timestamp del proprio orologio soltanto al proprio elemento del vettore. Quando poi i processi interagiscono tramite messaggi, i vector timestamp devono essere aggiornati in base al timestamp associato agli eventi invio e ricezione, in particolare, chi riceve il messaggio avrà un vector timestamp deve considerare anche il vector time stamp relativo agli altri processi.
Notiamo quindi che se diciamo che l'evento ricezione ha timestamp [2,3,4] allora quell'evento è di 2 eventi sul processo1, 3 eventi sul processo2, e di 4 eventi sul processo3, quindi quei numeri indicano cosa è avvenuto prima o comunque di cosa l'evento è a conoscenza.
Quindi con questa regola riusciamo a invertire la relazione di lamport.
Se e1 ed e2 hanno timestamp vt1 e vt2 allora
e1  e2 se e solo se vt_1[j] <= vt_2[j] per ogni j

non possiamo dire che e1 viene prima di e2.

quidni ogni evento si porta il vector tiemstamps che indica la conseguenza per quell'evento.

prendiamo un esempio, es app di chat
i vector timestamps li usiamo quando gli eventi devono rispettare causa effetto, gli eventi sono ancora gli scambi di messaggi.

tutti devono vedere i messaggi e anche i messaggi che provocano altri messaggi, quindi dobbiamo garantire la visualizzazione in un ordine che rispetti causa-effetto, i messaggi sono reazioni ad altri messaggi.
in questo esempio i timestamp sono direttamente l'ordine dei messaggi.

P0 manda il primo timestamp, sono influenzati dalla rete quinid magari p1 lo riceve e risponde subito, e quindi manda (1,1,0) che è la conseguenza di (1,0,0), ora però in P2 potrebbe arrivare prima (1,1,0) e poi la causa (1,0,0), quindi, se non avessimo lamport e un algoritmo di controllo, i messaggi potrebbero essere visualizzati cosi come arrivano nella chat, e quindi si crea confusione, vedo prima la reazione e poi la causa, quindi ci serve una sorta di filtro, dobbiamo introdurre una regola per sfruttare i vector timestamp in modo che i messaggi vengano visti nell'oridne giusto, e quindi p2 non dovrebbe vedere (1,1,0) prima di (1,0,0), vediamo come si fa ciò:

quando mi arriva un messaggio e voglio inviarne uno nuovo, lo mando e scrivo il maggiore del vector timestamp degli altri processi, quindi scrivo nel messaggio la mia conoscenza.
Chi riceve il messaggio, lo può consumare solo se sa almeno quello che sapeva il processo che ha inviato tale messaggio, per fare ciò dobbiamo controllare il vector timestamp che ci arriva, ossia l'indice del messaggio relativo a chi invia, ossia se mi arriva un 5 messaggio da p2, devo aver visto 4 messaggi precedenti da p2, però non basta rispettare l'ordine dei messaggi, ma vogliamo che chi riceve il messaggio sappia lo stesso di chi lo manda, quindi dobbiamo guarda anche gli altri elementi del vettore, e lo dobbiamo confrontare con quello che abbiamo noi, e dobbiamo avere
vt(r)[i]Vk[i] per  i diverso da j
o abbiamo visto lo stesso o qualcosa in piu.

nel caso (1,1,0) a p2, quello me lo devo conservare perchè non ho visto il messaggio (1,0,0), e poi quando arriva questo lo può mostrare all'utente. viene rispettata causalità.

### Mutua esclsuione
vediamo se queste soluzioni di lamport e timestamps possono servirci a risolvere problemi di mutua esclusione e elezione

mutua esclusione: processi concorrenti che devono eseguire operazioni su una risorsa condivisa, è fondamentale che queste operazioni avvengano in mutua esclusione ossia una alla volta. niella regione critica entra un processo alla volta.

Nei sistemi distribuiti però non possiamo usare semafori, non abbiamo spazio condiviso. Le soluzioni prevedono o un sistema centralizzato, quindi un gestore che tiene traccia dell'occupazione di una regione critica, e quindi quando bisogna accedere a una risorsa condivisa chiedono al gestore. però sono semplici, c'è collo di bottiglia, e c'è il problema dell'affidabilità e tolleranza ai guasti

dobbiamo eleggere il gestore.
se un gestore non risponde più, avviene una nuova elezione per decidere chi sarà il prossimo ad assumere tale ruolo.

Vediamo un algoritmo centralizzato distribuito.
c'è un gestore, tutti i processi che vogliono accedere a una risorsa condivisa devono mandare una request al gestore, il quale rispondo con OK se la risorsa è libera.
Se non è libera, il gestore si salva in una coda le richieste; quando un processo finsice di usare una risorsa, manda una release al coordinatore, il quale poi estrae il primo elemento dalla sua coda e gli manda l'OK.


Vediamo un esempio di soluzione distribuita, senza coordinatore,
Ricart 1981
Come funziona?
• Quando un processo vuole entrare in una regione
critica, costruisce un messaggio includendo:
– NOME REGIONE CRITICA
– NUMERO DEL PROCESSO
– TEMPO CORRENTE (orologi logici)
• Manda il messaggio a tutti gli altri processi

un processo a cui arriva una richiesta del genere, se esso non sta in regione critica o non ha intenzione di entrarci, rispodne con OK, se invece anche lui sta facenda una richiesta analoga, vado a guardare i timestamp tra la mia richiesta e quella che mi è arrivata, se quella che mi è arrivata è minore della mia rispondo con OK, anche se sono uguali arbitrariamente ne scegliamo uno; se la mia richiesta viene prima non ti mando un messaggio di risposta ma me lo ricordo che mi hai mandato tale richiesta. Quando un processo esce dalla regione critica, deve inviare gli OK a tutti i processi che stanno nella sua coda

senza lamport potrebbe non funzionare
supponiamo un processo si sveglia e vuole entrare in regione critica, allora 0 e 2 trovano un messaggio con timestmap 5 minore di 8 e quindi devono dare OK, quindi entrano e la mutua esclusione non è garantita.
Con lamport ciò non succede, l'ok del processo1 deve avere un timestamp maggiore di 8, quindi l'evento successivo a quel ok, non potra mai avere timestamp 5, ma almeno maggiore di 8.

# Lezione 26 - 20/11/2024

le soluzioni centralizzate sono semplici da implementare ma ci sono colli di bottiglia e single point of failure.

nel centralizzato c'è una richiesta e un permesso concesso dal coordinatore. quando uno finisce di usare la risorsa allora verrà pescato il prossimo in attesa in coda. è fair perchè le richieste vengono servite nell'ordine in cui arrivano.

poi c'è un primo algoritmo distribuito basato su lamport, che funziona se vengono rispettati i vincoli di timestamp di lamport, il timestamp dell'evento di ricezione deve essere maggiore dell invio, altrimenti si portano avanti gli orologi.
c'è un messaggio inviato con timestamp e risorsa, quando si esce dalla regione critica si dà l'ok a tutti gli altri messaggi.
senza lamport si potrebbero verificare fallimenti, potrebbe nascere una richiesta con timestamp più piccolo dopo che un processo ha già inviato ok al processo che ha appena fatto richiesta, ma questo con lamport non succede perchè la richiesta da parte di un processo porta l'orologio del destinatrio un istante succesivo alla richiesta stessa.
N-1 messaggi di richiesta e N-1 messaggi di ok.
bisogna sapere quali sono i processi del gruppo.

vediamo un altro tipo di algoritmo distribuito
ho la disponibilità di un token, quindi ho il permesso di fare una determinata attività se posseggo un token o comunque un oggetto unico nel nostro sistema distribuiito, di solito è un messaggio speciale che il protocollo riconosce, se ho il token posso accedere alla risorsa condivisa. Per garantire che tutti possono accedere il token viene girato nella rete, quindi il gruppo di processi si organizza ad anello (ring topology) e quindi ognuno conosce chi viene prima e dopo nella topologia, e quindi il processo riceve il token da chi lo riceve, lo usa una sola volta, e poi lo passa al successivo.

è un algoritmo distribuito, nessuno ha un ruolo centrale. l'unicità del token garantisce la mutua esclusione, ed il fatto che il token non può essere usato 2 volte di seguito ci garantisce la democraticità dell'algoritmo, quindi un processo non deve aspettare all'infinito per accedere alla regione critica, non si verifica starvation e deadlock.

problema è la perdita di token o la presenza di un doppio token.

quello centralizzato è quello meno oneroso, ci bastano 3 messaggi (chiedo permesso, ottengo permesso, rilascio risorsa) per accedere alla regione critica, le problemantiche sono il crash del coordinatore

il primo distribuito basato su lamport, per ogni ingresso in regione richiede 2*(N-1) con N numero di processi, quindi più oneroso, non c'è problema del crash del coordinatore ma dei singoli processi,
infine il token ring, può avere un efficienza molto alta in termini di messaggi se nessuno entra (quindi consjuma risorse anche se i processi non lo stanno usando), e nel worst case un processo deve apsettare N-1 prima di poter entrare, i problemi sono la perdita di token e crash processi che non possono poi passarsi il token.

gli algoritmi centralizzati richiesto la scelta di un processo coordinatore, nel token ring si potrebbe assegnare un ruolo a un processo che si dovrà occupare di rigenerare il token se viene perso.

### Algoritmi di elezione
questi algoritmi mirano dinamicamente a determinare l'identità di un processo che ha un ruolo particolare, che è un coordinatore, in modo che l'identità del coordinatore venga resa nota a tutti i membri del gruppo, quindi c'è una fase di elezione in cui i processi decidono chi è il coordinatore, e una fase di distribuizione dell'informazione sul coordinatore a tutti i processi del gruppo. Questi algortimi li possiamo eseguire non solo a inizio app, ma ogni qual volta che qualcuno si accorge che il coordinatore non risponde più o è crashato, questa esigenza può nascere in tutti i processi, quindi l'algoritmo deve fornire a tutti l'informazione che un coordinatore è crashato.

### Bully Algorithm
in questo algoritmo i processi sono virtualmente oridnati, e quell'ordine rappresenta una gerarchia tra processi, e chi ha un ID più grande è quello che stoppa algoritmi di elezione dai processi sotto di lui

ci sono messaggi speciali di elezione:

se uno o più processi voglio indire un'elezione (es. in figura 7 è morto) che consiste nell'inviare un messaggio di election a tutti i processi che stanno sopra di lui nella gerarchia, quindi in figura 4 manda mesaggio a 5 6 e 7, ovviamente anche altri processi contemporanemanete possono avviare l'elezione con la stessa regola; chi riceve il messaggio di elezione, è gerarchicamente superiore a chi sta in vetta, e risponde con un messaggio di OK che in realtà blocca il processo gerarchicamente inferiore, e lui stesso poi manda i messaggi ai processi che stanno sopra di lui. Quindi è come se inizalemtne tutti si possono accorgere del crash e far partire l'elezione, poi quelli più bassi si stoperrano e quelli con ID più alto procedono, e questo procedimento procede finchè uno di questi processi ancora attivi, il più alto nella gerarchia sarà l'unico a non essere stoppato (perchè non riceve OK da quello più in alto di lui che è crashato), e a quel punto il protocollo termina dato che il processo non è stato bloccato (in figura 6 è l'ultimo, diventerà il nuovo coordinatore), manderà a tutti un messaggio per dire che è lui il nuovo coordinatore, quindi c'è una distribuzione dell'informazione finale.

### Algoritmo di elezione token ring
un altro algoritmo che sfrutta una topologia ad anello, ogni processo conosce il prcedente e il successivo a lui nell'anello, chi si accorge che manca il coordinatore avvia l'elezione, e la richiesta viene ogni volta mandata al successivo
se le rushato vabbe

### Algoritmo di elezione in ambienite senza fili
vuol dire che non tutti conoscono la composizione dell'applicazione (es. app di peer computingk, conosciamo una parte limitata dei nodi della applicazione, nessuno ha una visione globale dello stato del sistema), ed anche in questa situazione poteebbe essere utile eleggere una sorta di super peer, quinid un processo che ha delle funzioni speciali rispetto ad altri, quì però non abbiamo anelli o altre topologie. Abbiamo due fasi:
una prima fase di floating, un processo avvia l'elezione (in figura a) invia un messaggio a tutti i processi che conosce e a cui è virtualmente connesso, quindi in questa fase mando più messaggi più di quelli necessari, as. a manda a b e j, ecc. La regola è che chi riceve un messaggio di questo tipo, siccome lo può ricevere da più processi, pensa al nodo g in figura, riceve il messaggio sia da b che da j, quindi chi riceve più messaggi da nodi diversi, deve decidere chi è il padre, infatti dobbiamo costruire a partre da questa rete rappresentato come grafo, un albero (nell'albero ogni nodo ha un solo padre), quindi cerchiami di raggiungere tutti i nodi del grado e ognuno decide chi è il proprio genitore, costruendo quindi l'albero, la decisione viene presa inviando un ack a tutti tranne che al padre.

quindi il nodo che ha mandato messaggi, da quelli per cui non riceve ack sà che quelli sono i suoi figli
con questa tecnica riusciamo a raggiungere tutti i nodi del grafo e li organizziamo come un albero.

quanto è terminata questa fase iniziale di floating, a questo appunto abbiamo il nostro albero per l'algoritmo a partire dal grafo; la radice di questo albero è il nodo che ha fatto partire l'elezione, quindi abbiamo trasformato un grafo in un albero in cui il root è il nodo che ha dato via all'elezione. A che usiamo l'albero? per decidere chi deve diventare il coordinatore, ci serve un criterio per scegliere, per esempio vediamo in figura che i nodi sono etichettati (costo della rete ecc), quindi stabilito come pesare il singolo nodo, a questo punto si partirà dal basso ossia dalle foglie (nodi senza figli), quindi tutte le foglie inviano il proprio peso al nodo padre, ed i nodi padre sanno quanti figli hanno, quindi aspettano i pesi di tutti i figli, dopodichè confrontano i pesi di tutti i figli col proprio peso, e a loro volta mandano al loro padre quali figli del loro ramo è il migliore (peso maggiore).
il numero di messaggi è minimo, non c'è spreco a differenza del floating.
Una volta che c'è un nodo vincitore, nella figura il nodo h, deve farlo sapere a tutti, quindi c'è un messaggio di elezione terminata con il vincitore, che attraversa l'albero a partire dalla radice con le classiche regole dell'albero, ossia padre invia messaggi ai figli.

ce ne sono tanti in letteratura capo.

questo algortimo ad albero che abbiamo visto lo possiamo usare in sistemi peer to peer, quindi l'elezione riguarderà uno o più superpeer, che devono essere eletti secondo delle regole che rendono il superpeer ad esempio più facilmente raggiungibile o con capacità di banda superiore, dipende dalle regole della rete.
Sicomme i superpper possono nascere e morire, devono comunque essere in numero limitato ed essere distribuiti in rete. Ci sono tecniche per effettuare una distribuzione uniforme in rete, tramite algoritmi di elezione in sistemi di ampia scala, che funzionano calcolando una solta di repulsione o comuqnue distanza tra due superpeer, se ce ne sono due troppo vicini uno deve cedere il ruolo.

finiti algoritmi di mutua elezione e elezione capo.

voliamo ai sistemi transazionali distribuiti, che sono molto diffusi.

## Sincronizazazione delle transazioni

sono sistemi in cui ci sono più nodi, che ricevono richieste di operazioni (in generale semplici, es. gestione conto corrente, prenotazioni voli), in cui le richiesti sono semplici.
Questo è un problema importanitssimo perchè i sistemi trasnazioni sono anche loro fondamentali, quindi ciò ha portato allo sviluppo di tecniche di transazioni.

def: un sistema transazionale è in grado di gestire un numero molto grande di transazioni, in cui l'obiettivo di ogni sistema (sia esso centralizzato e distribuito, poi vedremo cosa cambia) è quello sicuramente di gestire correttamente le operazioni di transazione (es. evito di prenotare lo stesso posto a 2 persone diverse), ed oltre alla correttezza l'altro obiettivo (legato alla sync) è quello di garantire buone prestazioni, infatti le prestazioni in un sistema transazionale si misurano in produttività, ossia numero di transazioni al secondo che quel sistema è in grado di fare.

Consideriamo prima un sistema centrlaizzato, i dati sono sulla stessa macchina e arrivano insieme delle richieste che corrisponodo alle transazioni.

![Uploading file..._m2cgufalu]()
Una trasnazione è una sequenza di operazioni elementari, o si possono anche vedere come sequenze di operazioni di lettura e scrittura su dati o variabili, delimitati da un inizio e fine della transazione.
Tale sequenza di operazioni, delimitata da begin e end transaction, devono diventare nel sistema transazionale, una singola operazione atomica, che quindi o va a buon fine oppure fallisce, e se fallisce eventuali operazioni che sono state già fatte di quella transazione devono essere annullate, fare in modo che non sia mai esistita. Quindi ricordiamo, la transazione deve diventare atomica nel nostro sistema, quindi o succede (tutte le istruzioni insieme) o fallisce, e se fallisce tutte le istruzioni intermedie devono essere riportate allo stato precedente. Un sistema transazionle quindi è in grado di eseguire transazioni che arrivano da sistemi concorrenti (es. browser che gererano transazioni), e il sistema li deve gestire correttamente
![Uploading file..._o4ipnqzlf]()
le transazioni devono chiudersi o con un commit o con un rollback.

esempio prenotazione volo con scali
![Uploading file..._4bs13k9ke]()

nota che ci sono degli scali, la transazione deve funzionare interamente, alrimenti se fallisce, tutte le prenotazioni intermedie devono essere annullate.

Tutto ciò che abbiamo detto si traduce in 4 proprietà che il sistema transaizonale deve rispettare per le transazioni, ossia le proprietà ACID (noi vedremo nel dettaglio isolation per la sincronizzazione):
- atomicity: caratterizza il sistema, la transazione deve diventare un operazione atomica. Le transazioni terminano con un commit in caso di successo, altrmenti si verifica un rollback, che può essere richiesta dall'app stessa(suicide) o dal sistema (murder). il sistema transazinoael quindi deve occuparsi della corretta esecuzione della transazione e garantire atomicità.
- consistency: una transazione che richiede una serie di operazioni o modifiche di un archivio (db capo), richiede che le operazioni richieste dalla transazione non violino alcuni vincoli di consistenza del database; il componente che si occupa della gestione della consistenza è il DBMS.
- isolation: proprietà strettamente legata alle prestazioni, infatti essa richiede che le transazioni che arrivano da app concorrenti, e che quindi vengono eseguite dal sistema transazionale mescolando operazioni provenienti da transazioni diverse, devono comunque rispettare questa proprietà, che vuol dire che il sistema transazionale può mescolare operazioni di transazioni diverse, ma l'effetto deve essere equivalente a come se l'esecuzione delle transazioni fosse seriale, quindi eseguo la prima transazione con tutte le operazioni, poi eseguo la seconda transazione, e i risultati devono essere identici a se eseguo queste due transazioni anche se mischio le due operazioni. L'esecuzione di una transazione non può dipendere dall'esecuzione delle altre. L'isoltamento quindi lo potrei rispettare semplicemente eseguendo le esecuzioni in seriale senza mescolarle, e l'ordine non è importante dato che nessuno influenza le altre, però la serializzazione di transazioni fa perdere concorrenza e riduce le prestazioni (che però è l'obiettivo finale del nostro sistema, vogliamo prestazioni elevate), e quindi la parte del sistema transazione che si occupa dell'isolamento deve provare a ottenere concorrenza e quindi migliori prestazioni, senza perdere la proprietà di isolamento. Es. operazioni di modifiche di un conto corrente, se le operazioni si intrecciano tra di loro, potremmo avere il saldo del conto scorretto,
- durability: il sistema transazionale che il rsiulstato della transazione corretta sia memorizzato correttamente.

La consistenza è di solito demandata al DBMS, atomicità al relability control system, e l'isolation al Concurrency control system, di cui ci occuperemo

#### Concurrency Control Theory
il sistema di controllo della concorrenza è come se fosse un componente che in ingresso N transazioni, ed ogni transazione è a sua volta come composta da una sequenza di operazioni di lettura e scrittura su delle variabili in un database, quindi ogni transazione viene identificata con un id, e con lo stesso id si identificano anche tutte le operazioni di lettura e scrittura.
![Uploading file..._rc9jum02h]()
Al sistema di controllo della concorrenza quindi arrivano tali transazioni con ID, e esso deve garantire l'isolamento, quindi si occupa di mescolare le singole operazioni in un determinato ordine, e garantire che quell'ordine di esecuzione garantisca la proprietà di isolamento, quindi la sequenza finale sarà isolata, ossia è equivalente all'esecuzione seriale delle stesse transazioni; ricorda che l'ordine delle transazioni non è importante, se ho t1 e t2, t1 lo posso eseguire pure alla fine.
![Uploading file..._3mlt10j93]()
Il controllore di concorrenza lo possiamo vedere come una sorta di schedulatore, a cui arrivano le operazioni delle transazioni che sono etichettate con l'ID della transazione, ed tale sistema dovrà produrre un esecuzione di quelle operazioni (schedulazione) che rispettano l'isolamento, ossia equivalente a un esecuzione seriale.

Vediamo ora con qualche esempio di individuare come non tutti i mescolamenti di operazioni garantiscono l'isolamento, quindi con questi esempi ci accorgiamo subito del fatto che il risultato è scorretto, e non verifica l'isolamento, mo ci facciamo una scarrellata di queste anomalie per cui lo schedulatore non può mescolare le operazioni a testa sua.

- Update Loss: supponiamo due transazioni che riguardano una lettura seguita da una scrittura di una variabile x. Le transazioni e le operazioni arrivano etichettate e passano al sistema di gestione della concorrenza ossia quello schedulatore che abbiamo visto, che decide di eseguire le operazioni nell'ordine che vediamo in figura.
![Uploading file..._8qcnfenko]()
se parto da x=2, serialmente se eseguiamo le due trnasazioni avremmo x=4, ma nella sequenza di operazioni decide dallo schedulatore, alla fine otteniamio x=3, quindi abbiamo perso un aggiornamento, perchè entrambi leggono x=2 ed entrambi la incrementano (leggono entrambi x=2 perciò), quindi c'è un risultato non isolato, il risultato non è lo stesso di quella seriale, per via della concorrenza sbagliata.
Al sistema quindi, se arrivano due transazioni di questo tipo, è evitare che vengono mischiate in questa maniera.

- Dirty read: abbiamo le stesse due transazioni viste prima, però la sequenza di operazioni che viene garantita dallo schedulatore sembra apparentemetne corretta, perchè prima leggo e salvo per t1, però quì contempliamo un caso in cui la transazione non viene completata correttamente, quindi ci sarà l'abort, ma nel frattempo t2 aveva preso il valore modificato da t1, e quindi alla fine ci troviamo con un unica transazione eseguita con successo, quindi anziche avere x=3 se parto da x=2, otteniamo lo stesso x=4, e quindi il risultato non è corretto, perchè la prima transazione ha subito abort.
![Uploading file..._6kvvhgist]()

- inconsistent read: abbiamo sempre le stesse due transazioni, ma ora t1 fa due volte la lettura della variabile x, mentre t2 fa il suo solito incremento con lettura e scrittura e fa il commit; quindi quì t1 legge due valori diversi, mentre se la trasnazione fosse eseguita in maniera serializzata se faccio due letture devo leggere sempre lo stesso risultato, quindi anche qui il risultato non è isolato, ed il nostro sistema di controllo dovrebbe evitare queste sequenze di operazioni.
![Uploading file..._f9m8xwojr]()

- ghost update: supponiamo che ora t1 vada a controllare un vincolo di integrità, quindi leggere le variabili x,y,z e le somma, ed anche in questo caso, se in mezzo alla verifica di quel vincolo, si mescolano operazioni provenienti da t2, che non viola il vincolo, nota però che salva y e z nuovi, mentre t1 aveva già letto il vecchio y, e quindi alla fine il risultato è scorretto, la sequenza non è isolata.
![Uploading file..._7axre9cxr]()

Quindi, abbiamo visto che operazioni di transazioni diverse non possono essere mescolate a caso senza criterio, e l'obiettivo del controllore della concorrenza è mettere in sequenza operazioni di lettura e scrittura provenienti da transazioni diverse ed assicurarsi che quella sequenza (schedulazione) sia isolata. Ragioneremo sempre come operazioni di lettura e scrittura dati da un db, e quindi lo schedulatore deve riuscire a mettere bene insieme le operazioni.
siamo ancora nel caso centralizzato, le operazioni avvengono tutte sulla stessa macchina ed eseguite una dopo l'altra. Il controllore deve accorgersi se una sequenza è isolata o no, e o blocca quelle non corrette o le evita, vedremo ci sono due modi di lavorare per produrre schedulazioni in cui le operazioni vengono comunqeu mescolate ma sono isolate.

Quindi in un primo momento partiremo da un sistema centralizzato quindi operazioni che vengono eseguite una dopo l'altra, e inizialmente assumeremo che tutte le transazioni che arrivano terminano con commit, poi dopo toglieremo questo vincolo.
Dopodioche, contempletemo il caso in cui il sistema transazionale è distributio, quindi i dati, ad esempio x,y,z, non sono sulla stessa macchina ma su macchine diverse, e quindi le operazioni devono essere smistate a dove stanno i dati e verranno eseguite su nodi diversi, ma devo comunque ottenere lo stesso risultato in termini di correttezza e isolamento.

# Lezione 27 - 20/11/2024
triste oggi.

continuiamo transazioni capo.

caso di sistema di transazioni distribuito, abbiamo un insieme di operazioni provenienti da transazioni diverse, e il sistema deve garantire la proprietà di isolamento.

dobbiamo capire come fare la schedulazione di queste operazioni mantenendo l'isolamento.

procediamo facendo le ipotesi di iniziare a lavorare su una macchina sequenziale, poi vedremo il caso distribuito, quindi quella che è una sola schedulazione diventeranno diverse schedulazioni su macchine diverse.
Un altra semplificazione che facciamo è di non prendere in considerazioni le transazioni possano essere abortite, quindi supponiamo di lavorare con assunzioni che terminano con commit, poi dopo vedremo il caso generale. Cominciamo

Abbiamo detto che la proprietà di isolamento vuol dire che le transazioni non sono influenzate dalle altre transazioni. le schedulazioni seriali sono sicuramente isolate, perchè le operazioni sono fatte una dopo l'altra, non si mescolano. Quedto ci serve perchè noi abbiamo un problema di equivalenza tra risultato di una schedulazione seriale e il risultato di una schedulazione concorrente.

Se ci sono n transazioni, allora n! saranno il numero di schedulazioni seriali, ma se consideriamo il mescolamento di operazioni, ne avremmo molte di più, e solo quelle seriali sarebbero un poccolo sottoinsieme.

Abbiamo un modello ora, dobbiamo capire il concetto di equivalenza.

esempio
ogni transazione legge una var e poi la incrementano.
Vediamo 3 possibili schedulazioni (successioni di operazioni di lettura e scrittura, prima leggo e poi scrivo).
La prima è una schedulazione seriale, le altre due non lo sono, es schedule 3 avrà una x=5 per la terza, quindi gia si vede che non va bene.
Dobbiamo cercare di esprimere ciò in maniera formale per spiegare l'equivalenza.

Ci serve il concetto di **View Equivalent**
abbiamo relazioni di:
- leggi da: partiamo da operazioni di lettura, e per ognuna di queste andiamo a vedere quali sono le ultime operazioni di scrittura fatta su quella variabile, può riguardare anche la stessa transazione.

Quindi per la schedulazione, numeriamo tutte le relazioni leggi da.
Un altra cosa da guardare sono le scritture finali su una variabile.
A questo punto, possiamo dire che due schedulazioni sono view-equivalent se hanno le stesse relazioni leggi da e le stesse scritture finali sulle variabili.

esempio
es in schedule 2, r1(x) legge da w2(x) ecc.

Quindi, dato che abbiamo dei modelli sicuramenti validi, ossia le schedulazioni seriali, ed abbiamo un modo per confrontare due schedulazioni tra di loro, allora una schedulazione diremo che è isolata se è view equivalent a una delle schedulazioni seriali. se non ne trovo nessuna view equivalent non è isolanta.
Chiamimamo view-serializabile tutte le schedulazioni che sono view-equivalent a una seriale.

abbiamo trovato un insieme che oltre a quelle seriali sono isolate.

adesso quindi abbiamo un criterio per dire se una schedulazione va bene o no.

in questo esempio schedule 2 non è vsr perchè non è view equivalent a schedule 1, con r1(x) che legge da w2(x), che non troveremo in nessuna seriale. Le relazioni leggida non dipendono dall'ordine in cui sono eseguite le schedulazioni seriali (importante).
in schedule3, abbiamo r3(x) che legge da w2(x).

le schedulazioni vsr sono il sottoinsieme più ampio di schedulazioni isolate, le seriali fanno parte di queste; quindi un sistema di controllo della concorrenza che sarebbe in grado di generare un insieme di schedulazioni vsr sarebbe il migliore possibile, perchè ci farebbe ottenere il massimo della concorrenza e scarterebbe meno schedulazioni da quelle corrette. Questo è utile saperlo per valutare il tradeoff della capacità dello schedulatore di trovare schedulazioni isolate e il tempo che ci mette a trovarle, a un certo punto magari preferiamo uno schedulatore che ci mette meno tempo.

Tutto bello questo concetto di equivalenza, ma per capire anche se una schedulazione è buona o no, dobbiamo anche guardare la complessità dell'algoritmo (vedere se sono view equivalent è poco oneroso, tempo polinomiale), ma se questo poi lo molteplichiamo per n!, a quel punto il problema non è più risolvibile in tempo polinomiale, e quindi questo è solo un criterio di riferiemnto e non lo possiamo implementare, perchè è un problema NP completo, ed inoltra lavora a cose già fatte, ossia và a vedere la schedulazione dopo che già è stata eseguita, quindi già prodotta, e potremmo accorgerci che la schedulazione non è buona dopo che è stata eseguita. dovrebbe esse n*n! esplode, n! è la complessità
Ce lo teniamo come criterio ideale di isolamento, ma non è applicabile perchè ha complessità computazionale come un problema NP, e lavora a schedulazione gia eseguita.

prima di abbandonare questo criterio teorico, vediamo un esempio in cui, se lo applichiamo alle anomalie viste prima, sono 4 ma ci basta vederne solo tre, perche una è provocata dall'abort di una delle transazioni, ma qu' abbiamo ipotesi che non c'è abort, quindi quella la skippiamo.

S3 è view equivalent a S4.
S5 ad S6.
anomaly 4 sarebbe s9.

cerchiamo un criterio più utilizzabile.

eccolo qua **conflict-equivalent**
due schedulazioni sono conflict equivalent se hanno esattamente gli stessi conflitti. Un conflitto in una schedulazione è una coppia di operazioni non necessariamente consecutive (da transazioni diverse) sulla stessa variabile. quindi guardiamo la schedulazione e dobbiamo trovare due operazioni sulla stessa variabile relativa a transazioni diverse (read1(x) e write2(x) tipo), quindi ora il termine di paragone è prendere tutti i conflitti di una schedulazione e confrontarla con i conflitti di un altra (anche l'ordine è importante, read e write è diverso da write read).

guarda come si sta trovando i conflitti per ogni variabile su transazioni diverse.
S10 e S11 hanno gli stessi conflitti, quindi possiamo dire che sono conflict equivalent.
che ci serve il conflict-equivalent? come abbiamo ragionato prima, abbiamo il criterio di equivalenza lo usiamo per paragonare una schedulazione campione con tutte le possibili schedulazioni seriali, e se trovo una conflict-equivalent con una seriale (ne sono n!) allora la schedulazione è conflict serializabile ed è isolata.

conflict equivalent e view equivalent sembrano simili, devo comunqeu fare n! confronti, ma c'è una differenza: le schedulazioni conflict equivalent isolate, sono un sottoinsieme proprio delle schedulazione isolate rispetto alla view equivalent, quindi in realtà è peggio rispetto a view equivalent perchè ne scarto di più. Se csr è un sottonismee di vsr, ci sono delle schedulazioni vsr che non sono csr, quindi è buona, allora viene scartata, quindi è peggio.
Ma allora se è peggio perchè lo usiamo? perchè a differenza del vsr, per capire se una schedulazione è csr ci mettiamo meno tempo, non dobbiamo verificare con le n! schedulazioni, ci aiuta uno strumento che è un grafo di conflitto.
Prendiamo la schedulazione da testare, e guardiamo solo i conflitti su quella schedulazione, e ogni volta che trovo un conflitto disegno un arco tra i nodi che rappresentano le transazioni, quindi graficamente ogni conflitto sulla schedulazione produce un arco orientato (orientato perchè l'ordine tra read e write è importante), se il conflitto già ci sta è inutile che ridisegnamo l'arco. Si dimostra che se disegnamo il grafo dei conflitti, e verifico che tale grafo è aciclico, allora la schedulazione è conflict serializable.
Abbiamo fatto un passo avanti quindi, non dobbiamo fare confronti con n! schedulazioni seriali, ma risolviamo con un algoritmo con un algortimo che cerca cicli in un grafo di n nodi, che ha complessità polinomiale.

guarda capo ha disegnato il grafo dei conflitti.
S11 è seriale. (operazioni in sequenza tutte della stessa transazione).
S10 è conflict serializable ed isolata.

se guardiamo il grafo, oltre ad essere acicliclo, il percorso che tocca tutti i nodi senza richiudersi troviamo anche la seriale (potrebbe servirci averla chissa).

Rimane il problema che anche questo criterio lavora a posteriori, non va bene (vigile che fa andare le macchine a un incrocio e le fa ripartire da zero poi).
Quindi anche questo è una sorta di criterio teorico, ce ne serve uno ancora meno preciso ma che possa essere usato dal controllore della concorrenza in diretta. prima di vedere ciò vediamo un esempio.

S1 è seriale, quindi sia VSR che CSR.
S2 non è vsr, e non è nemmeno csr, se disegniamo il grafo dei conflitti troviamo ciclo tra 1 e 2.
S3 anche qui troviamo 2 1 e 2 1, ciclo.
S4 è vsr, le relazioni leggi da sono mantenute, e fa solo le scritture alla fine, però incappa nella non conflict serializable.
ancora c'è un ciclo tra 1-2 e 2-1.
quindi questa sarebbe scartata dal criteroio csr.

Vediamo se blocca anche le anomalie: una cosa che ci interessa è la completezza sicuramente ma ci preme che non faccia passare le anomalia, ossia non faccia passare le schedulazioni non isolate.

S7 non è csr.
S8 non è csr.
w2(z) e r1(z) e r1(y)-w2(y) ciclo 1-2 e 2-1. non è csr.

Abbiamo quindi trovato due criteri, uno meno accurato ma più veloce, ma comunque entrambi lavorano a posteriori, ci serve ora un criterio che sia in grado di lavorare man mano che arrivano le operazioni da transazioni diverse.

### Two-phase locking: 2PL
immergiamoci nel criterio che è collegata agli insiemi che già abbiamo trovato, ma a differenza di quei due criteri questo lavora in tempo reale.

Si basa su due meccanismi per funzionare:
- le transazioni prima di effettuare un operazione di lettura su una variabile devono chiedere il permesso di leggere quella variabile ad un gestore della concorrenza; quindi ogni transazione prima di leggere x chiede un permesso di lettura, e il gestore gli dirà di si oppure non risponde, r_lock
- se le transazioni vogliono fare un op di scrittura, devono chiedere il permesso w_lock al gestore, anche qui il gestore o gli da il permesso o non rispnode.
La differenza tra questi due permessi è che, r_lock può essere shared, ossia il gestore