Programmazione concorrente e distribuita

Programmazione concorrente e distribuita

I processi a livello di sistema operativo non condividono la memoria per una questione di protezione. Java ha librerie per i thread, dove con il tempo sono nati costrutti sempre di più alto livello. Ancora non ci sono async e await di JavaScript (forse perché non possono farlo). Java è formidabile per i thread: sono semplici ed efficaci.

Thread in Java

Thread è sinonimo di componente attivo, mentre gli oggetti visti fino ad oggi sono passivi. Attivo significa che ha un suo flusso di controllo, e normalmente di componente attivo c’è il main thread. Run non ha parametri di ritorno ed è curioso perché è il metodo dove si definisce cosa deve fare il thread, ma non lo si chiama mai. Ci sono anche metodi statici come current_thread, che indica quale thread sta eseguendo in quel momento; essendo statico, posso chiamarlo anche senza istanziare un oggetto.

Fondamentale è capire la differenza tra run e start. Quando viene chiamato start (è un metodo che non va ridefinito) avviene la magia: si appoggia al sistema operativo che crea un thread e fa partire il metodo run. Chiamando run, si trasferisce solo il flusso di controllo a quel thread; se si chiama run anziché start, fa tutto il main.

Creazione e gestione dei thread

Ci sono due modi per creare un thread: estendere la classe Thread oppure passargli una lambda function (parametri, freccia e poi blocco), in pratica gli si passa direttamente il comportamento. Ha senso il secondo modo quando non si vuole rappresentarlo, ad esempio quando è di breve durata.

Se si chiama la join su di un thread, tutti i thread devono aspettare che lui sia finito. Ci sono metodi deprecati (se ne sconsiglia l’uso) della classe thread: stop, suspend, resume, destroy, ecc., che potrebbero portare a problemi di deadlock.

Quando si fa un programma multithread, la prima regola è sfruttare la massima capacità computazionale, usando quindi tutti i processori e core della macchina. In linea di principio, se un thread non rilascia mai la parola con wait, usa sempre un processore (un core). È da evitare perché riduce le performance e consuma batteria.

Lock, semafori e monitor

Lock, semafori e monitor sono di più alto livello rispetto al non usare niente. Se si usa ad esempio una variabile turno (while turn != 1), nell’esempio non si ha deadlock, ma si potrebbe avere che a un thread non venga mai data la parola perché non vuole entrare nella sua sezione critica. Se si usano le variabili “want” per ogni thread, si può andare in deadlock e non va bene.

L’unico che riuscì a trovare un algoritmo prima di semafori e monitor fu Dekker, che usava sia la variabile turno che le variabili want. Un solo processo alla volta può essere nella propria sezione critica per la mutua esclusione (ogni processo ha la propria sezione critica), non si deve mai creare una situazione di stallo (deadlock), e ogni processo prima o poi dovrà entrare. Queste tre proprietà sono alla base della concorrenza.

Si avrà quindi un meccanismo di più alto livello che permetterà di acquisire e rilasciare il lock, rendendo atomiche due istruzioni (test and set). In Java c’è l’attributo synchronized che permette di creare delle sezioni critiche. Per fare model checking c’è ad esempio il Java PathFinder, una versione della Java Virtual Machine che permette di testare tutti i possibili scenari di un programma Java.

In Java, ad ogni oggetto è associato un lock nativamente e c’è un meccanismo che è il synchronized per ottenere il lock a quell’oggetto. Quest’anno si insisterà molto sui monitor, ancora più che sui semafori, perché dice che i semafori li abbiamo già visti, quindi si insisterà più sull’uso di un approccio di più alto livello.

Synchronized e Java

Quando un thread riesce a prendere il lock su un certo oggetto, altri thread che concorrentemente cercano di ottenere il lock sullo stesso oggetto vengono bloccati in attesa che il primo thread esca. Ogni volta che un thread invoca un metodo etichettato synchronized, prima di tutto cerca di prendere il lock associato all’oggetto. Se il lock è già stato dato, questo thread viene sospeso in una entry set (insieme di thread sospesi in attesa di ottenere il lock).

Java non garantisce che ci sia una coda, ovvero un ordine. Questo potrebbe portare a problemi di starvation (con due thread non si hanno problemi), viene tenuto così senza ordine per massimizzare la portabilità dalla Java Virtual Machine ad altre piattaforme. Synchronized è di basso livello e lo useremo molto poco; conviene usarlo come vedremo negli oggetti passivi (quindi non dentro ai worker, i worker credo siano i thread).

Synchronized è appunto di basso livello e ha il problema che, ad esempio, non ha la possibilità di rilasciare il lock fino a che non ha finito, quindi se prende il lock e un thread si blocca, nasce un problema. Normalmente, quindi, si usano meccanismi di più alto livello come i lock o i monitor.

Tra i principali metodi per implementare i thread in Java, i più semplici sono i lock. Esiste l’interfaccia “Lock” e si usa la classe “ReentrantLock”. Bisogna sempre fare l’unlock dopo aver preso il lock e si mette di solito in “finally” così viene eseguito anche se avvengono eccezioni. Si usa ReentrantLock perché fa riferimento alla rientranza, ovvero la possibilità di richiedere più volte lo stesso lock senza bloccarsi (anche nel meccanismo di base di Java, ovvero con synchronized se chiamo più volte un metodo con synchronized, non succede nulla e non si blocca).

Fondamentale capire che se uno stato viene letto ma non modificato non ha senso gestire i thread con lock, ecc. Su GitHub si trova JPF (Java PathFinder) che permette di fare model checking direttamente sui programmi scritti in Java, sembra un po’ controintuitivo visto che di solito prima si crea il modello. Quello che fa è percorrere tutti i possibili scenari come farebbe un model checker; in pratica è una Java Virtual Machine che non solo manda in esecuzione il programma, ma tutti i suoi possibili scenari. JPF non è facile da installare, però il prof ha messo a disposizione una versione che è possibile usare senza bisogno di installarla.

Semafori

Con i semafori posso risolvere qualsiasi problema di coordinazione, ma rimango comunque ad un livello di astrazione molto basso, mentre i monitor sono di più alto livello e permettono di semplificare la programmazione. I semafori sono fondamentali, anche a livello concettuale, e saranno chiesti all’esame; inventati da Dijkstra, servono per sincronizzazione e competizione.

Il modello del semaforo, che può essere implementato ed esteso in tanti modi, è fatto da due componenti (wait e signal), un contatore (che parte da 0) ed un insieme di processi (che parte vuoto). Quindi vengono dati due metodi, due operazioni, wait e signal (indicati spesso con P e V). Wait detto informalmente è l’operazione con cui un processo chiede di poter ottenere il semaforo (il semaforo ha un contatore che ha valore >= 0, se il contatore ha valore > 0 corrisponde al semaforo verde, se è = 0 allora è rosso, un await sul semaforo rosso non decrementa il contatore ma va a sospendere il processo che ha chiamato la wait).

L’operazione di signal invece incrementa e dipende anche dal numero di processi in attesa. Se c’è almeno un processo nell’insieme dei processi in attesa, l’effetto della signal è scegliere un processo dall’insieme (arbitrario, non è una coda ma è un insieme), lo si toglie dall’insieme e lo si rende ready (lo si sblocca). Se c’è almeno un processo in attesa implica che il contatore sia = 0 perché se fosse > 0 allora non ci sarebbero processi nell’insieme. Se ho un semaforo = 0 e ho un processo che esegue una signal, quello che succede è che il semaforo si incrementa.

Ci sono 3 diversi tipi di semafori: mutex, generali e ad eventi. I mutex sono i più semplici: i semafori possono avere solo valori 0 o 1, se si chiamano mutex vengono sempre inizializzati a 1, e il loro uso tipico è per realizzare mutua esclusione. I semafori generali rappresentano un certo numero di permessi (o risorse) a disposizione. I semafori ad eventi vengono inizializzati a zero e vogliono realizzare l’accadimento di un evento.

Strong vs weak lo chiede all’esame, ma anche busy-wait. I semafori di solito sono weak, ovvero quando c’è un insieme per i processi in attesa (non c’è quindi un ordinamento). I semafori strong invece hanno una coda che permette di garantire che la signal prenda il primo della lista dei processi in attesa (non ci sarà mai starvation) e per forzare che un semaforo sia strong bisogna settare un valore true in un costruttore.

Un semaforo busy-wait usa il busy waiting senza bloccare i semafori, quindi non avrò né lista né insiemi, e non va a usare il sistema operativo. Non va mai usato tranne in contesti particolari di multiprocessori dove non voglio usare il sistema operativo.

L’uso dei semafori è diviso in due macrocategorie: mutua esclusione e sincronizzazione. I semafori non sono rientranti come invece i lock, perché il blocco non dipende da chi lo invoca ma dal valore del contatore, ed è facile fare errori di programmazione. Per il caso della sezione critica si usa un mutex, per la sincronizzazione (ovvero ordinare le azioni eseguite da processi diversi).

Se si usano la wait e la signal da un thread su uno stesso semaforo, allora è un problema di mutua esclusione. Per la sincronizzazione invece vengono usati wait e signal da thread diversi. Il problema più semplice di sincronizzazione avviene quando un’azione di un processo deve avvenire dopo l’azione di un altro processo.

Monitor

Usando i semafori, i programmi diventano molto complessi perché appunto sono di basso livello, aumentando il rischio di avere errori. Vengono perciò introdotti i monitor (sono lo strumento che più ha preso piede), che essendo di più alto livello permettono di realizzare mutua esclusione e sincronizzazione in modo più agevole. L’idea è quella di poter incapsulare all’interno di un modulo (che è all’incirca come una classe) i concetti di mutua esclusione e sincronizzazione senza che lo sviluppatore debba gestire a basso livello aspetti come i lock o i semafori.

Il nome fa riferimento a come veniva chiamato il kernel dei sistemi operativi (si diceva ad esempio entra in “monitor mode” per dire “kernel mode”). Il modulo di un monitor (che può essere visto anche come oggetto istanza di una classe) ha uno stato e un insieme di procedure mandate in esecuzione in modo mutualmente esclusivo.

L’esecuzione vincola il fatto che ci sia sempre solo un metodo, procedura, esecuzione alla volta, quindi se un monitor è acceduto da più processi concorrentemente, allora il monitor ha dei meccanismi per cui un solo processo alla volta può eseguire le procedure. È quindi come dire che le procedure di un monitor sono mandate in esecuzione in modo atomico, e quindi implicitamente una sezione critica. I processi che sono in attesa di entrare in un monitor perché c’è già un processo dentro sono sospesi in una entry set (in un insieme), in questo modo non devo più gestire io il mutex associato alla sezione critica.

I monitor sono componenti passivi, thread-safe, e garantiscono quindi anche un miglior design. Sono tuttavia meno flessibili rispetto ai semafori, con comunque ottime prestazioni. Non hanno una coda ma un insieme, quindi potrebbero esserci problemi di starvation. I monitor mettono a disposizione le condition variables per riuscire a gestire, oltre alla mutua esclusione, anche l’altro mondo relativo alla concorrenza, ovvero la sincronizzazione (eseguire una procedura subito dopo un’altra).

Le condition variables sono waitC e signalC, che non hanno però un valore o un contatore interno ma rappresentano proprio degli eventi. La sintassi della waitC è data dalla funzione a cui viene passata la condition variable, e significa aspetta, mettiti in attesa che arrivi una segnalazione relativa a quella condition. Mentre la signalC, se c’è qualcuno in coda, lo sblocca. Importante è capire che se faccio una signalC su una condizione e non c’era nulla in attesa, non succede nulla.

Fondamentale capire che non viene incrementato nessun contatore con la signalC e soprattutto con la waitC mi blocco sempre, mentre nei semafori mi bloccavo solo se il contatore era = 0. Non essendoci contatori nei monitor, bisogna quindi crearsi un flag se ce n’è bisogno, perché se viene prima la signal della wait ci si blocca.

Inoltre, la signal sveglia sempre e solo un processo. Se si hanno più processi, volendo esiste anche la signalAllC che li risveglia tutti, oppure si possono usare le signal in catena per ovviare a questo problema. Esistono poi 3 tipi di discipline quando avviene la signal: “signal e continue” (chi ha fatto la signal ha poi la precedenza e chi è stato svegliato viene messo in un’altra coda), “signal and urgent wait” (la disciplina originaria dei monitor dove chi fa la segnalazione si sospende in attesa che chi è stato svegliato faccia le sue cose ed esca dal monitor), “signal and wait” (chi ha fatto la segnalazione dà la precedenza a chi fa la wait e poi si mette in competizione con gli altri processi che devono ancora entrare).

Nella libreria di Java, fra i syncronizers oltre ad esserci i lock, ci sono i tryLock che provano ad ottenere i lock senza mai bloccarsi. Però bisogna stare attenti perché genera busy waiting. Ci sono anche i semafori che hanno un uso più legato alla mutua esclusione che però al posto di await ha “acquire” e al posto di signal ha “release”.

Con synchronized non ho il problema di ricordarmi di rilasciare il mutex, perché c’è praticamente un concetto di blocco di codice.

Come implementare i monitor

I monitor hanno due funzionalità di base. La prima è che ad ogni monitor è associato un lock, quindi quando si parla di monitor si parla di moduli (in caso di OOP, si parla di oggetti) in cui tutti i metodi devono essere mandati in esecuzione sempre in modo mutualmente esclusivo. Quindi all’interno di un monitor ci può essere al massimo un processo in esecuzione, in Java questo avviene sfruttando direttamente il metodo synchronized.

La seconda modalità, un po’ più complessa, riguarda le condition variables, cioè quei meccanismi che ci permettono di sincronizzare fra di loro i processi. Infatti, i thread servono sia a lato competizione che cooperazione. Per il primo approccio, quello di base, Java offre synchronized, wait, notify e notifyAll. Per questo approccio la prima regola di buona programmazione è implementare tutti i metodi pubblici synchronized (questo è il metodo pulito più diretto). Il problema di questo approccio è quello di avere praticamente una sola condition variable.

Il secondo approccio permette di avere più flessibilità; paradossalmente questo approccio permette di scrivere dei monitor migliori, avviene creando un mutex che funge da lock (si usa ReentrantLock) e delle condition variables (es. notEmpty) e facendo le wait sulle specifiche condition variables. In riassunto, qui non si ha una unica wait generale, non si usano i meccanismi base di Java (i metodi pubblici non sono più synchronized) perché la mutua esclusione la implemento con il mutex. È importante capire che si wrappa il codice che era all’interno del metodo pubblico tra la presa e il rilascio del mutex che fa da lock.

Le condition variables sono legate al lock del monitor, per questo quando le istanzio lo faccio sul loro lock. Buona norma è utilizzare il while invece dell’if perché Java nella sua documentazione parla di “spurious wake up” dei thread nella sua Java Virtual Machine a valle di alcune condizioni non ben definite. In Java si ha una variante della signal e continue, dove da quello che ho capito chi fa la signal si mette in competizione con anche gli altri thread. Nella documentazione di Java dice di usare sempre notifyAll anziché notify.

I monitor possono essere visti come un costrutto su cui costruire costrutti di più alto livello come latch, barriere, lavagne, ecc. Il latch per esempio è una forma di coordinamento per cui ho un processo che vuole bloccarsi in attesa prima che tutti gli altri processi abbiano svolto una certa operazione. Nel caso della barriera invece si hanno diversi processi che hanno un punto di sincronizzazione comune e tutti questi processi prima di eseguire l’istruzione successiva al punto di sincronizzazione devono essere arrivati al punto di sincronizzazione. La differenza tra i due è che nel latch solo un thread si blocca mentre nella barriera tutti i thread si bloccano.

Avendo i semafori, posso implementare dei monitor. Come prima cosa nell’analisi bisogna capire quali sono i compiti che possono essere indipendenti gli uni dagli altri, e qui si inizia a parlare di task (un pezzo di lavoro che viene fatto da un componente attivo). Un thread o anche un processo è più un’esecuzione di un singolo flusso di controllo, mentre il task è più un inquadramento a livello logico (un’unità di lavoro che deve essere fatta). Quindi come prima cosa si cercano di task da compiere e poi le loro dipendenze. Una volta fatto, allora si mettono in campo le architetture concorrenti (modi di organizzare il sistema), e qui si dividono i componenti attivi da quelli passivi; quelli attivi sono quelle entità che hanno la responsabilità.