Programmazione Distribuita PDF

Programmazione Distribuita  Programmazione Distribuita Capitolo 1 – Introduzione 1.1 I sistemi distribuiti Un sistema distribuito consiste di un insieme di macchine, ognuna gestita in maniera autonoma, connesse attraverso una rete. Ogni nodo del sistema distribuito esegue un...

Programmazione Distribuita  Programmazione Distribuita Capitolo 1 – Introduzione 1.1 I sistemi distribuiti Un sistema distribuito consiste di un insieme di macchine, ognuna gestita in maniera autonoma, connesse attraverso una rete. Ogni nodo del sistema distribuito esegue un insieme di componenti che comunicano e coordinano il proprio lavoro attraverso uno strato di software detto middleware, in maniera che l’utente percepisce il sistema come un’unica entità integrata. Diverse leggi empiriche elaborate negli anni hanno predetto la velocità di evoluzione dei vari sistemi. Ad esempio, la legge di Moore afferma che la densità dei transistor nei processori si raddoppia ogni 18 mesi. I sistemi distribuiti rappresentano, quindi, la strada per poter utilizzare al meglio quello che la tecnologia hardware continua a produrre, ma spesso si scontrano con varie difficoltà di progettazione, sviluppo, gestione ed evoluzione. Tra i vari problemi abbiamo l'elevato costo per produrre un software complesso e problemi dovuti alla difficoltà nella realizzazione di sistemi eterogenei e complessi. La priorità più importante per gli ambienti di sviluppo per sistemi distribuiti e la riusabilità e le integrabilità di soluzioni diverse. 1.2 Le leggi che regolano le Reti Lo sviluppo di una rete dipende dall’utilità che questa porta ad un insieme di utenti: quanto più sono utilizzabili i servizi, tanto maggiore è il loro valore commerciale. Il valore di una rete con riferimento al numero di connessioni è definito dalle leggi empiriche di Sarnoff, Metcalfe e Reed. Sarnoff’s law. Il valore o utilità di una rete broadcast è direttamente proporzionale al numero di utenti: 𝑉 = 𝑎 ∙ 𝑁 (lineare). Metcalfe’s law. Il valore di una rete è direttamente proporzionale al quadrato del numero degli utenti: 𝑉 = 𝑎 ∙ 𝑁 + 𝑏 ∙ 𝑁 2 (quadratico). In questo caso posso comunicare con ogni altro nodo della rete. Reed’s law. Il valore di una rete sociale è direttamente proporzionale ad una funzione esponenziale in 𝑁: 𝑉 = 𝑎 ∙ 𝑁 + 𝑏 ∙ 𝑁 2 + 𝑐 ∙ 2𝑁 (esponenziale). Quindi il valore di una rete cresce in modo esponenziale se è associata a gruppi con interessi comuni che condividono idee, interessi e obiettivi. 1.3 Caratteristiche di un Sistema Distribuito I sistemi distribuiti hanno varie caratteristiche tra cui: - Un sistema distribuito è remoto perché le sue componenti devono poter essere locali o remote, quindi potenzialmente localizzate su macchine diverse. - Un sistema distribuito è per sua natura concorrente, cioè abbiamo l'esecuzione contemporanea di due o più istruzioni su macchine diverse, e non esistono strumenti come lock e semafori che permettono di gestire in maniera più semplice la sincronizzazione. - Assenza di uno stato globale. Non esiste una maniera per poter determinare lo stato globale del sistema, in quanto la distanza e la eterogeneità del sistema non permette di definire con certezza lo stato in cui si trova ciascun nodo. - Malfunzionamenti parziali. Ogni componente del sistema distribuito può smettere di funzionare e questo non deve interferire con le funzionalità del sistema distribuito. 1 - Eterogeneità. Un sistema distribuito per sua stessa definizione è eterogeneo per tecnologia sia hardware che software. - Autonomia. Un sistema distribuito non ha un singolo punto dal quale può essere controllato, coordinato e gestito. - Evoluzione. I sistemi distribuiti devono essere flessibili nel migrare verso ambienti diversi senza costi eccessivi. - Mobilità. Così come gli utenti, anche i nodi e le risorse del sistema sono mobili. 1.4 Un modello di riferimento: RM-ODP Allo scopo di facilitare lo sviluppo dei sistemi distribuiti, è importante l'utilizzo di un modello comune che serva come astrazione per produttori, progettisti o sviluppatori. Infatti, ISO/IEC ha proposto un modello formale per le architetture dei sistemi distribuiti: questa specifica si chiama “The Reference Model of Open Distribuited Processing” (RM-ODP). L'obiettivo di questo modello è di favorire la diffusione dei servizi di un sistema distribuito in un ambiente eterogeneo. Il modello RM-ODP si basa ed integra il modello ISO/OSI, infatti, questo modello gestisce i problemi di comunicazione rispetto ai problemi di connessione che vengono trattati principalmente dal modello ISO/OSI. RM-ODP estende ed ingloba, il modello ISO/OSI, usando quest'ultimo come modalità per la comunicazione tra componenti eterogenee. 1.5 Requisiti non funzionali di un sistema distribuito La realizzazione di un sistema distribuito non è facile e comporta la necessità di considerare vari aspetti che non hanno a che fare direttamente con le funzionalità del sistema distribuito stesso ma hanno invece a che fare con i cosiddetti requisiti non funzionali, che indicano la qualità del sistema. Questi requisiti non funzionali specificano che la progettazione deve puntare realizzare sistemi distribuiti che: … siano aperti, in modo da supportare la portabilità per evitare di rimanere legati ad un singolo fornitore. … siano integrati così da incorporare al proprio interno sistemi e risorse differenti senza dover utilizzare strumenti ad-hoc. … siano flessibili per poter evolvere e far evolvere i sistemi distribuiti in maniera da integrare sistemi legacy al proprio interno. Un sistema distribuito dovrebbe anche poter gestire modifiche a run-time. … siano modulari in modo da permettere ad ogni componente di poter essere autonoma ma anche indipendente verso il resto del sistema. … supportino la federazione di sistemi, in modo da unire diversi sistemi dal punto di vista amministrativo oltre che architetturale. … siano facilmente gestibili, in modo da permettere il controllo, la gestione e la manutenzione per configurare i servizi, la qualità e le politiche di accesso. … siano scalabili perché qualsiasi sistema distribuito accessibile da Internet può essere soggetto a picchi di carico non prevedibili. Supporto per la qualità del servizio (Quality of Service): fornire i servizi con vincoli di tempo, di disponibilità e di affidabilità, anche in presenza di malfunzionamenti parziali. 2  … siano sicuri così che utenti non autorizzati non possono accedere a dati sensibili. … offrano la trasparenza mascherando i dettagli e le differenze del sistema sottostante. 1.6 Trasparenza: un Requisito non funzionale importante La definizione di trasparenza di un sistema equivale a dire che un sistema distribuito appare come un'unica entità all'utente. I vantaggi della trasparenza sono una maggior produttività attraverso l'astrazione del modello ed un alto riuso delle applicazioni sviluppate. Abbiamo diversi tipi di trasparenza, interconnessi su tre livelli: 1. Trasparenza (livello di base): di accesso, di locazione 2. Trasparenza (livello di funzionalità): di migrazione, di replica, di persistenza, di transazioni 3. Trasparenza (livello di efficienza): scalabilità, prestazioni, malfunzionamenti Trasparenza di accesso La trasparenza di accesso nasconde le differenze nella rappresentazione dei dati e nell’invocazione per permettere l’interoperabilità tra oggetti. Questo significa che gli oggetti devono essere accessibili attraverso la stessa interfaccia, sia che siano acceduti da locale sia che siano acceduti da remoto. In questo modo, un oggetto può essere spostato a run-time da un nodo ad un altro. Trasparenza di locazione La trasparenza di locazione non permette di utilizzare informazioni sulla locazione di un particolare componente nel sistema che viene identificato ed utilizzato in maniera indipendente dalla sua posizione. Questo tipo di trasparenza è fondamentale in quanto senza di esso non si potrebbero spostare componenti da un nodo ad un altro. Trasparenza di migrazione Il compito di questo tipo di trasparenza e quello di nascondere la possibilità che il sistema faccia migrare un oggetto da un nodo ad un altro. Questo viene utilizzato per ottimizzare le prestazioni del sistema come il bilanciamento del carico tra i nodi oppure riducendo la latenza o anche per anticipare i malfunzionamenti. La trasparenza di immigrazione dipende dalla trasparenza di accesso e dalla trasparenza di locazione. Trasparenza di replica Con questo tipo di trasparenza il sistema maschera il fatto che una singola componente viene replicata con un certo numero di copie dette repliche che vengono posizionate su altri nodi del sistema e che offrono esattamente lo stesso tipo di servizio della componente originale. Anche questo tipo di trasparenza dipende da quello di accesso e di locazione. Le repliche vengono utilizzate per diversi scopi: per le prestazioni in modo da minimizzare la latenza oppure sono utilizzate per poter far scalare il sistema in presenza di aumento del carico di lavoro. Trasparenza alle transazioni La trasparenza alle transazioni nasconde all'utente le attività che vengono svolte per assicurare la consistenza dello stato degli oggetti in presenza della concorrenza. Trasparenza ai malfunzionamenti La trasparenza ai malfunzionamenti nasconde ad un oggetto il malfunzionamento di oggetti con i quali sta interoperando. Questo tipo di trasparenza si poggia sulla trasparenza di replica, in quanto quest'ultima 3 fornisce la possibilità di poter ripetere le operazioni che si erano iniziate su una replica di un oggetto, potendo rieseguirle su un'altra replica. Ma si basa anche sulla trasparenza alle transazioni, in quanto operazioni complesse se interrotte a causa di un malfunzionamento non vengono confermate e quindi non alterano lo stato della risorsa e possono essere ripetute su un'altra replica. Trasparenza alla persistenza Questo tipo di trasparenza nasconde all'utente le operazioni che compie il sistema per rendere persistente un oggetto durante una fase di non utilizzo. Questo tipo di trasparenza si basa sulla trasparenza di locazione in quanto l'accesso indipendente dalla posizione fisica dell'oggetto permette una riattivazione dell'oggetto anche su nodi diversi da quelli su cui era stato de-attivato. Trasparenza alla scalabilità La scalabilità e uno dei principali motivi a favore di un sistema distribuito rispetto ad uno centralizzato. Un sistema viene detto scalabile quando in grado di poter servire carichi di lavoro via via crescenti senza dover modificare la propria architettura e proprio organizzazione. Progettare un sistema scalabile e necessario visto il gran numero di utenti. Trasparenza alle prestazioni Questo tipo di trasparenza rende il progettista/sviluppatore ignaro dei meccanismi che vengono utilizzati per ottimizzare le prestazioni del sistema durante la fornitura di servizi. In particolare, il sistema può provvedere ad implementare politiche di bilanciamento del carico spostando componenti da nodi più saturi a nodi meno saturi. La trasparenza alle prestazioni si appoggia sulla trasparenza alla migrazione, alla replica e alla persistenza. 1.7 Middleware ad Oggetti Distribuiti Chiesto in modo veloce I sistemi distribuiti basati su oggetti distribuiti sono uno degli strumenti utilizzati dei sistemi distribuiti per assicurare estendibilità, affidabilità e scalabilità, rendendo minimo lo sforzo per progettare, sviluppare e manutenere sistemi complessi. Gli oggetti distribuiti separano due aree della tecnologia software: - i sistemi distribuiti che puntano a realizzare un unico sistema integrato basato sulle risorse offerte da diversi calcolatori messi in rete; - lo sviluppo e la programmazione orientata agli oggetti che si focalizzano sulle modalità per ridurre la complessità dei sistemi. 4 Gli oggetti distribuiti hanno come obiettivo quello di realizzare servizi distribuiti riutilizzabili, efficienti, flessibili, sicuri e robusti sia per hardware che per software. Questa integrazione viene realizzata attraverso il middleware ad oggetti distribuiti, un software che risiede tra le applicazioni e lo strato del sistema operativo, protocolli di rete e hardware. È chiaro che possiamo programmare un sistema distribuito utilizzando le primitive di comunicazione di ogni singolo nodo, questo però risulta essere complesso e costoso; quindi, una soluzione è il middleware il quale fornisce le astrazioni appropriate per i programmatori. Il middleware ad oggetti distribuiti può essere suddiviso in 3 strati: 1. Middleware d'infrastruttura. Si occupa della comunicazione tra OS diversi e della gestione della concorrenza in maniera da essere portabile (un esempio è la Java Virtual Machine). 2. Middleware di distribuzione: automatizza compiti comuni per la comunicazione come: - il marshalling: invio di parametri per le invocazioni remote ad altri nodi; - multiplexing dello stesso canale di comunicazione per più invocazioni; - gestione della semantica delle invocazioni (unicast, multicast, attivazione on-demand); - riconoscimento gestione dei malfunzionamenti; 3. Middleware per i servizi comuni: serve a fornire servizi comuni a tutte le applicazioni distribuite e quindi riutilizzabili in tutti i contesti. Quindi, l'astrazione fornita dal middleware permette di focalizzarsi sullo sviluppo dell'applicazione, favorisce il riuso delle soluzioni adottate e rende sviluppo efficace ed efficiente. 1.8 Il progenitore: RPC Un meccanismo di base molto importante per consentire il dialogo di applicazioni presenti su macchine diverse è il meccanismo Remote Procedure Call (RPC) che permette ad una procedura in esecuzione su una macchina di invocarne un'altra che si trovasse su un'altra macchina (invocazione di procedure remote come se fossero locali). L'obiettivo era di facilitare il compito del programmatore il quale può concentrarsi sulla suddivisione delle funzionalità in procedure senza curarsi del fatto che siano remote o locali. Infatti, RPC è la prima tecnologia a fornire la traduzione dei tipi di dato a livello applicazione in maniera tale che: - fosse possibile trasmettere i dati utilizzando stream di byte su socket; - si superassero le differenze nella rappresentazione di interi e stringhe. Inoltre, RPC imponeva che fosse rispettata la sincronia dell'invocazione di funzioni (metodi) bloccando il client fino a quando il server non avesse risposto all'invocazione remota. Le invocazioni asincrone, invece, si hanno quando la funzione (processo, thread, …) chiamante continua la computazione, concorrentemente alla computazione della funzione chiamata. Le operazioni di sincronizzazione, marshaling, data representation e comunicazione tra client e server venivano implementate dai sistemi di RPC attraverso i client stub e server stub. La scrittura degli stub venne poi automatizzata, utilizzando un linguaggio chiamato Interface Definition Language (IDL). 5 Il passaggio da RPC agli Oggetti Distribuiti è stato motivato dell'evoluzione dei sistemi distribuiti divenuti più complessi, eterogenei e difficili da gestire e da manutenere a causa delle migliorie hardware e di comunicazione. Innanzitutto, RPC: - usava un paradigma procedurale e non ad oggetti; - i tipi di dato sono solamente elementari; - mancanza della gestione delle eccezioni. Con il passaggio al paradigma ad oggetti abbiamo nuovi meccanismi come il polimorfismo, l'ereditarietà, la gestione delle eccezioni che non offriva il paradigma procedurale. 1.9 Esempi di Middleware: CORBA, Java RMI,.NET Tre sono le famiglie basate su oggetti distribuiti: CORBA, Java RMI,.NET Remoting. CORBA Common Object Request Broker Application Viene chiesto CORBA è uno standard che permette ad oggetti distribuiti, scritti in diversi linguaggi e quindi eterogenei, di comunicare e collaborare per realizzare un'applicazione distribuita. L'architettura di CORBA si basa sull’invocazione di un servizio (metodo). Le implementazioni degli oggetti remoti possono essere in C, C++, Java, ed altri linguaggi per i quali esiste un binding con CORBA. Le invocazioni remote vengono realizzati attraverso Object Request Broker (ORB) chi si occupa di fornire diversi tipi di trasparenza a d'invocazione ma anche di fornire accesso a servizi di supporto. Enterprise JavaBeans (con Java RMI) Ha come obiettivo limitare la complessità per realizzare nuovi servizi basati su oggetti facilitandone il riuso. Abbiamo una netta separazione del layer di presentazione da quello di business in modo da bilanciare il carico attraverso le traparenze di migrazione, locazione, accesso, etc. Enterprise JavaBeans è un’architetture a componenti: una componente è un modulo software che può essere ricombinato anche sotto forma di binario a differenza di librerie, oggetti tradizionali etc. Il server che gestisce le componenti si chiama container (o application server). Inoltre, è un Middleware implicito. 6.NET Remoting.NET Framework è la soluzione di Microsoft per la realizzazione di applicazioni ed include un ambiente di esecuzione chiamato Common Laguage Runtime (CLR) in modo che le applicazioni possono essere scritte in uno dei linguaggi supportati da Microsoft..NET Remoting è una tecnologia per realizzare una comunicazione remota. Con questa tecnologia la parte di middleware di infrastruttura è assicurato dal CLR e la parte di middleware di servizi viene realizzata da altre librerie di.NET. 1.10 Componenti Distribuite Una componente distribuita è un blocco riutilizzabile di software che può essere usato in un sistema distribuito per realizzare funzionalità. All'interno di una componente risiedono servizi e applicazioni che espongono le proprie funzionalità tramite un'interfaccia. A differenza dei moduli software riutilizzabili (come gli oggetti), le componenti possono essere combinati sotto forma di eseguibili binari, piuttosto che sotto forma di azioni da compiere sul codice sorgente e, inoltre, il modello a componenti si basa sul cosiddetto middleware implicito contrapposto al middleware esplicito. Un esempio di middleware esplicito è Java RMI. Il middleware implicito è in grado di fornire servizi comuni ad ogni componente senza che essa debba esplicitamente richiederli all'interno del codice. Il server che gestisce la componente (detta application server o container) fornisce questi servizi sulla base delle richieste codificate non nel codice ma in un file di metadati di descrizione durante la fase di deployment, cioè quando la componente viene messa a disposizione sul server. In questa maniera i servizi vengono messi a disposizione in maniera trasparente allo sviluppatore di software della componente, realizzando una maggiore interoperabilità tra produttori di software diversi. Il middleware esplicito i servizi venivano esplicitamente richiesti dal progettista di applicazioni inserendo all’interno del codice le chiamate ai servizi forniti dal sistema. Questo presentava alcuni problemi: - Complessità; - mancanza di controllo del sistema su errori; - mancanza di portabilità. 7 Capitolo 2 – Programmazione Concorrente 2.1 Thread in Java Un thread è un percorso di controllo all’interno di un processo. Un processo, invece, è un programma in esecuzione con un unico percorso di controllo e con uno spazio di memoria privato. Molti sistemi operativi moderni permettono che è un processo possa avere più percorsi di controllo, ovvero possedere dei multi-thread. Un processo tradizionale è chiamato processo pesante (heavyweight process) in riferimento allo spazio di indirizzamento, mentre, i thread sono anche detti processi leggeri perché hanno un contesto più semplice rispetto ai processi. I thread sono shared memory: condividono la memoria per comunicare. Uno dei vantaggi principali della programmazione multithread è dato dal fatto che i thread appartenenti allo stesso processo condividono tra loro memoria e file aperti. In particolari circostanze, ogni thread può necessitare di una copia privata di certi dati, chiamata dati specifici dei thread. Nei sistemi multicore i thread possono essere eseguiti in parallelo, poiché ogni thread può essere assegnato ad un core specifico. 2.2 Multi-Threading Il multi-threading è una forma di parallelizzazione che consente l'elaborazione simultanea. Invece di assegnare un carico di lavoro elevato a un singolo core, i programmi threadizzati dividono il lavoro in più thread software. Questi thread vengono quindi elaborati in parallelo da diversi core della CPU per risparmiare tempo. La tecnologia Hyper-Threading è un'innovazione hardware che consente l'esecuzione di più thread su ciascun core. Più thread attivi significano più lavoro svolto in parallelo. Quando la tecnologia Hyper-Threading è attiva, la CPU genera due contesti di esecuzione per ogni core fisico. Questo significa che un singolo core fisico funziona come due "core logici", in grado di gestire diversi thread software. I problemi con i Multi-Core riguardano l’accesso alla memoria, infatti, si potranno avere: - cache misses (breve); - page faults (lungo); - context-switch dallo scheduler (molto lungo). 2.3 Dennard Scaling e il Power Wall Il Dennard Scaling afferma che, man mano che i transistor si riducono, la loro densità di potenza rimane costante, in modo che l'utilizzo di energia rimanga proporzionato all'area. Sfortunatamente, Dennard Scaling ignora i leakege current (perdite di energia) e il threshold voltage, che stabiliscono un limite di potenza per transistor. Questo limite definisce il power wall in cui la frequenza di un processore è stata limitata intorno ai 4 GHz fino al 2006. Quindi, con l’era del Dennard Scalling si puntava ad aumentare sempre più la frequenza dei processori trascurando i core. Solo successivamente (dopo il 2005) si è passati ad aumentare il numero di core mantenendo costante le frequenze di clock della CPU, infatti, tramite l’uso di più core le performance aumentarono grazie all’uso del parallelismo. 8 2.4 Programmazione Concorrente La programmazione distribuita implica la conoscenza della programmazione concorrente che coinvolge diversi processi che vengono eseguiti insieme. Abbiamo tre tipi di programmazione concorrente: 1. programmazione concorrente eseguita su calcolatori diversi; 2. processi concorrenti sulla stessa macchina (multitasking); 3. processo padre che genera processi figli per fork(); Quando parliamo di programmazione concorrente nello stesso processo ci riferiamo ai thread. 2.5 Multitask vs Multithread ❖ Il multitask crea l’illusione (per l’utente) di una macchina completamente dedicata ma durante l’interazione dell’utente con il proprio programma, il SO ha il tempo di servire altri utenti. ❖ Il multithread, invece, è l’estensione del multitask riferita ad un singolo programma in grado di eseguire più thread “contemporaneamente”. 2.6 Parallelismo e Concorrenza La concorrenza è una tecnica utilizzata per ridurre il tempo di risposta del sistema utilizzando una singola CPU. Un’attività è divisa in più parti e ogni parte viene elaborata contemporaneamente ma non nello stesso istante. Produce l’illusione del parallelismo, ma in realtà i pezzi di un’attività non vengono elaborati parallelamente. La concorrenza conferisce l’accesso a più parti delle risorse condivise e funziona su un thread quando sta facendo progressi utili; quindi, arresta il thread e passa a un thread diverso quando non sta facendo progressi utili. Il parallelismo è concepito allo scopo di aumentare la velocità di calcolo utilizzando più processori. È una tecnica per eseguire simultaneamente i diversi compiti nello stesso istante. Coinvolge diverse CPU che operano ed eseguono parallelamente attività al fine di aumentare la velocità di calcolo e migliorare la produttività. Il parallelismo determina la sovrapposizione delle attività di CPU e I/O in un processo con le attività di CPU e I/O di un altro processo. 2.7 Thread in Java I thread in Java sono oggetti, istanze quindi della classe Thread. L’evoluzione di Java ha portato a due modalità di gestione dei thread: 1. istanziare un oggetto Thread ogni volta che serve un task asincrono (creazione e gestione a cura del programmatore); 2. astrarre la gestione, passando un task ad un Executor. 9 Per scrivere i thread in Java bisogna: 1. estendere la classe java.lang.Thread; 2. riscrivere (override) il metodo run() nella sottoclasse di Thread; 3. creare un’istanza di questa classe derivata; 4. richiamare il metodo start() su questa istanza. 1) Esempio 2) Esempio 2.7.1 Metodi della classe Thread sleep(): cessa temporaneamente l’esecuzione del thread che lo esegue per un certo numero di millisecondi. È un metodo statico ciò vuol dire che può essere invocato sulla classe Thread e non sugli oggetti. join(): consente a un thread di attendere il completamento di un altro thread. Se t è un oggetto Thread il cui thread è attualmente in esecuzione, allora t.join() farà in modo che t venga terminato prima che l'istruzione successiva venga eseguita dal programma. È possibile anche specificare un periodo di attesa in millisecondi come parametro. join() risponde ad un interrupt generando InterruptException. start(): quando il programma chiama questo metodo, viene creato un nuovo thread e il codice all'interno del metodo run() viene eseguito nel nuovo thread. run(): se si chiama il metodo run() direttamente non verrà creato alcun nuovo thread e il codice all'interno di run() verrà eseguito direttamente nel thread corrente. Un'altra differenza tra start() e run()è che non è possibile chiamare start() due volte: una volta avviata, la seconda start() chiamata verrà lanciata IllegalStateExceptionin mentre è possibile chiamare il metodo run() più volte poiché è solo un metodo normale. 2.8 Gli Interrupt Un interrupt indica al thread di fermare quello che sta facendo e fare qualcosa altro ed è il programmatore a decidere cosa fare. Se un thread non invoca un metodo che lancia l'eccezione InterruptedException, allora il programmatore può controllare se è stato interrotto utilizzando Thread.interrupted(). 10 2.9 Gli Stati dei Thread (nella JVM) Un thread può trovarsi in uno dei seguenti stati: - NEW: un thread che non è ancora stato avviato. - RUNNABLE: un thread in esecuzione nella macchina virtuale Java. - BLOCKED: un thread bloccato in attesa di un blocco del monitor. - WAITING: un thread che attende indefinitamente che un altro thread esegua una determinata azione. - TIMED_WAITING: un thread in attesa che un altro thread esegua un'azione fino a un tempo di attesa specificato. - TERMINATED: un thread che è stato terminato. Un thread può trovarsi in un solo stato in un determinato momento. Questi stati sono stati della macchina virtuale che non riguardano gli stati dei thread del sistema operativo. 2.10 Comunicazione tra Thread I thread comunicano principalmente condividendo e accedendo a: - campi (tipi primitivi); - campi che contengono riferimenti a oggetti. I tipi di errori con la programmazione concorrente sono principalmente due: 1. Interferenza: si verifica quando due o più thread accedono concorrentemente provocando una race condition. La race condition si verifica quando il risultato di un’operazione dipende dall’ordine di esecuzione di diversi thread. Gli errori dovuti ad una race condition sono tipicamente transienti e difficili da riprodurre (debugging difficile). Inoltre, l’uso del debugger può alterare l’ordine di esecuzione dei task. Questi bug vengono anche detti Heisenbug che richiamano il principio di indeterminazione di Heisenberg in fisica quantistica (“Non è possibile misurare simultaneamente la posizione ed il momento di una particella”). 11 2. Inconsistenza della memoria: si verifica quando thread diversi hanno visioni diverse dei dati. Le cause possono essere: protocolli di coerenza di cache, ottimizzazioni hardware/software, etc. La soluzione è l’happens-before in cui la memoria scritta da un thread è visibile da un altro thread. Esempio: Il campo contatore è condiviso tra due thread, A e B - supponiamo che A incrementi il contatore: counter++; - supponiamo che subito dopo B esegue la stampa: System.out.println(counter); - … può capitare che la modifica di A non sia visibile a B (che stampa 0). - bisogna stabilire una relazione happens-before. Per stabilire una relazione happens-before usiamo la sincronizzazione, in particolare useremo i metodi start() e join() per introdurre una relazione happens-before. Thread.start(): gli effetti del codice sono visibili al nuovo thread; Thread.join(): metterà il thread corrente in attesa fino a quando il thread su cui è chiamato non termina. Se il thread viene interrotto, la join genererà un’InterruptedException. Esempio: Se t è un oggetto Thread il cui thread è attualmente in esecuzione, allora t.join() farà in modo che t venga terminato prima che l'istruzione successiva venga eseguita dal programma. Un’altra maniera è rendere la variabile volatile assicurando la relazione happens-before per ogni successiva lettura della variabile (da parte di qualsiasi thread). La volatile è usata quando il valore di una variabile viene scritto in memoria da un thread e tutti gli altri thread leggeranno tale valore. In questo modo non vengono utilizzati i meccanismi di caching e vengono disabilitate alcune ottimizzazioni di riordino delle istruzioni del compilatore. Infatti, dichiarando volatile una variabile si costringe il thread ad aggiornare di volta in volta il valore senza memorizzarlo in cache. Per risolvere questi problemi è necessaria la sincronizzazione che a sua volta genera problemi di contesa: cioè quando più thread cercano di accedere alla stessa risorsa simultaneamente (deadlock e livelock). 2.11 Legge di Amdahl: Speedup La legge di Amdahl viene usata per predire l'aumento massimo teorico di velocità che si ottiene usando più processori. Chiameremo speedup S di un programma X, il rapporto tra il tempo impiegato da un processore per eseguire X rispetto al tempo impiegato da n processori per eseguire X. Sia p la parte del programma X che è possibile parallelizzare con n processori, la parte parallela ha tempo 𝑝 mentre la parte sequenziale ha tempo (1 − 𝑝). 𝑛 Quindi, lo speedup che si ottiene eseguendo il programma X su n processori, dove p è la parte di X che si 𝟏 può parallelizzare è: 𝑺(𝒏) = 𝒑 (𝟏 − 𝒑) + 𝒏 La legge di Amdahl ci dice che la parte sequenziale del programma rallenta molto qualsiasi speedup che possiamo pensare di ottenere. Quindi, per velocizzare un programma non basta investire sull’hardware ma è assolutamente necessario impegnarsi a rendere la parte parallela predominante rispetto alla parte sequenziale. 12 2.12 Sincronizzazione: metodo synchronized() I metodi sincronizzati (synchronized) sono un costrutto del linguaggio Java, che permette di risolvere gli errori di concorrenza al costo di inefficienza. Per rendere un metodo sincronizzato, basta aggiungere synchronized alla sua dichiarazione: public synchronized void increment (){ c++; } Non è possibile che due esecuzioni dello stesso metodo sullo stesso oggetto siano interfogliate (sovrapposte). Quando un thread esegue un metodo sincronizzato per un oggetto, gli altri thread che invocano metodi sincronizzati dello stesso oggetto sono sospesi fino a quando il primo thread non ha finito. Quando un thread esce da un metodo sincronizzato, allora si stabilisce una relazione happens-before cioè i cambi allo stato, effettuati dal thread appena uscito sono visibili a tutti i thread. I costruttori non possono essere sincronizzati solo il thread che crea dovrebbe avere accesso all’oggetto in costruzione. synchronized(this), il thread è sincronizzato sull'oggetto corrente, quindi, si può avere un'istanza per thread. Ciò è utile per impedire a più thread di aggiornare un oggetto contemporaneamente, il che potrebbe creare uno stato incoerente. Lo stesso vale su un metodo statico sincronizzato. synchronized(SomeClass.class) è sincronizzato sulla classe dell'oggetto corrente in modo che solo un thread alla volta possa accedere a qualunque istanza di quella classe. Questo potrebbe essere utilizzato per proteggere i dati condivisi tra tutte le istanze di una classe dall'entrare in uno stato incoerente. 2.13 Lock intrinseci Un lock intrinseco o monitor lock è una entità associata ad ogni oggetto che garantisce sia accesso esclusivo sia accesso consistente (relazione happens-before). Un thread deve: - acquisire il lock di un oggetto; - rilasciarlo quando ha terminato. Quando il lock che possedeva viene rilasciato, viene stabilita la relazione happens-before. Quando un thread esegue un metodo sincronizzato di un oggetto ne acquisisce il lock, e lo rilascia al termine (anche se c’è una eccezione). 2.14 Sincronizzazione con Azioni Atomiche Sono azioni che non sono interrompibili e si completano (del tutto) oppure per niente. Si possono specificare azioni atomiche in Java per: - read e write su variabili di riferimento e su tipi primitivi (a parte long e double); - read e write su tutte le variabili volatile. Write a variabili volatile stabiliscono una relazione happens-before con le letture successive. Per usare le azioni atomiche bisogna importare java.util.concurrent.atomic. 13 2.15 Problemi di Sincronizzazione: Deadlock, Starvation, Livelock Un deadlock si verifica quando due thread sono bloccati, ognuno in attesa dell’altro. La starvation si verifica quando un thread non è in grado di ottenere un accesso alle risorse condivise e non è in grado di fare progressi. Ciò accade quando le risorse condivise non vengono rese disponibili per lunghi periodi da thread "avidi". Ad esempio, supponiamo che un oggetto ha un metodo sincronizzato che impiega molto tempo per essere restituito. Se un thread richiama frequentemente questo metodo, anche altri thread che richiedono un accesso sincronizzato frequente allo stesso oggetto verranno spesso bloccati. La livelock si verifica quando un thread agisce in risposta all'azione di un altro thread. Se l'azione dell'altro thread è anche una risposta all'azione di un altro thread, potrebbe verificarsi il livelock. Come con il deadlock, i thread livelock non sono in grado di fare ulteriori progressi. Tuttavia, i thread non sono bloccati: sono semplicemente troppo occupati a rispondersi l'un l'altro per riprendere il lavoro. Questo è paragonabile a due persone che tentano di incrociarsi in un corridoio: Alphonse si sposta alla sua sinistra per far passare Gaston, mentre Gaston si sposta alla sua destra per far passare Alphonse. Vedendo che si stanno ancora bloccando a vicenda, Alphone si sposta alla sua destra, mentre Gaston si sposta alla sua sinistra e così via. 2.16 Multithreading a grana fine e a grana grossa Nel multithread a grana fine, i thread emettono istruzioni in modo round-robin mentre nel multithreading a grana grossa, i thread emettono istruzioni fino a quando non si verifica uno stallo. Il multithreading a grana fine è un meccanismo di multithreading in cui il passaggio tra i thread avviene nonostante la mancanza di cache causata dall’istruzione del thread. Il multithreading a grana grossa è un meccanismo di multithreading in cui lo switch avviene solo quando il thread in esecuzione provoca uno stallo, sprecando così un ciclo di clock. Tale multithreading è meno efficiente del multithread a grana fine perché causa un gap / perdita di ciclo quando si passa da un thread all’altro. Inoltre, la grana grossa richiede meno thread per mantenere la CPU occupata rispetto al multithreading a grana fine. 2.17 Modello fork-join Nel calcolo parallelo , il modello fork-join è un modo per eseguire programmi paralleli attraverso un approccio divide et impera. In pratica, si suddivide l’attività in sottoattività più piccole e indipendenti fino a quando non sono abbastanza semplici da essere eseguite in modo asincrono. Dopodiché, inizia la parte "join", in cui i risultati di tutte le sottoattività vengono unite ricorsivamente in un unico risultato, o nel caso di un'attività che restituisce void, il programma attende semplicemente che ogni sottoattività venga eseguita. 14 2.18 Singleton Chiesto in modo veloce Il singleton è un noto design pattern della programmazione ad oggetti che permette di istanziare una ed una sola istanza di una classe. L’allocazione avviene solo quando l’oggetto è utilizzato per la prima volta (lazy allocation). Il singleton avrà un costruttore privato, perché non deve essere invocato dall’esterno, e un metodo pubblico statico getIstance() il quale istanzia un solo oggetto, verificando che sia stato creato per la prima volta, e lo restituisce. Inoltre, essendo una inizializzazione statica, si stabilisce una relazione happens-before con tutte le altre operazioni della classe. public static Singleton getInstance() { if (instance == null) { instance = new Singleton(); } return instance; } Questo metodo funziona se ci troviamo in ambito single-thread. Nella programmazione multi-thread si possono verificare condizioni di race condition perché due thread vogliono accedere nello stesso momento al metodo getIstance() e verranno creati due singleton. Una soluzione è di rendere getIstance() un metodo sincronizzato ma questo porta lo svantaggio di avere una grande inefficienza. Una soluzione migliore è il Double-checked locking: se non esiste l’istanza si entra in una sezione critica, si controlla che nel waiting non sia cambiata la situazione e se è il caso viene creato un nuovo Singleton e si esce dalla sezione critica. Una cosa importante è che il campo instance deve essere volatile per prevenire problemi di incoerenza della cache (solo con versioni dopo la JDK5). Questo metodo però non è funzionante al 100% per la mancanza di compatibilità con le versioni precedenti di Java. private static volatile Singleton instance; public static Singleton getInstance() { if (instance == null) { synchronized (Singleton.class) if (instance == null) { instance = new Singleton(); } } return instance; } 15