Programmazione concorrente e distribuita

Non-determinismo

Il non-determinismo implica che testare un programma concorrente è solitamente difficile dato che non è possibile determinare l'ordine assoluto dell'esecuzione delle istruzioni. Questi problemi sono definiti come Race Condition: tutte quelle situazioni in cui thread diversi operano su una risorsa comune ed in cui il risultato viene a dipendere dall'ordine in cui essi effettuano le loro operazioni. Le Race Condition si possono verificare in due condizioni: 1. Una risorsa deve essere condivisa tra due thread 2. Deve esistere almeno un percorso di esecuzione tra i thread in cui una risorsa è condivisa in modo non sicuro Per dimostrare la correttezza di un programma concorrente esistono due modi: - Dimostrare per induzione che il programma soddisfa tutte le condizioni sufficienti perché possa essere considerato sicuro (questo metodo spesso si dimostra troppo costoso) - Sviluppare il programma utilizzando strategie note chepermettono di evitare situazioni di race condition:

• Fare in modo che la risorsa condivisa sia in uno stato sicuro prima di consentire ad un altro thread di accedervi
• Bloccare l'accesso alle risorse condivise mentre sono in uno stato non sicuro è alla base delle strategie per ottenere programmi concorrenti sicuri

Per bloccare l'accesso agli oggetti si può utilizzare un semaforo. Il semaforo blocca l'accesso al primo thread che accede alla risorsa condivisa. Quando finisce di usare la risorsa, sblocca la risorsa, consentendo a un altro thread di accedere. Questo a sua volta bloccherà eventuali altri thread... I semafori sono di tipo binario (rosso o verde):

• Acquire: acquisire l'accesso bloccando altri task ed eventualmente ponendo in attesa il task chiamante, se il semaforo è rosso
• Release: rilascia la risorsa ed eventualmente riporta ready un task in attesa

Esistono tre diversi tipi di semafori:

• Contatori: il semaforo...

1. viene inizializzato a un valore intero positivo e a ogni richiesta viene decrementato (solo quando è zero il thread che fa una richiesta viene bloccato) e a ogni uscita viene incrementato (e se presente si sblocca un thread in attesa)
2. Binari: il semaforo può essere solo zero o uno (rosso o verde)
3. Generico n-ario: un mutex è un semaforo istanziato con valore 1

Synchronized

Ad ogni istanza della classe Object c'è un semaforo binario (indicato come lock), poiché ogni oggetto in Java estende la classe Object, ogni oggetto ha un suo lock.

La parola chiave synchronized applicata ad un metodo o ad una qualunque sezione di codice implica che:

• Quando si entra nel metodo/area synchronized si cerca di acquisire il lock associato all'oggetto
• Quando si esce dal metodo/area synchronized si rilascia il lock associato all'oggetto, quindi un eventuale thread in attesa può acquisire il lock ed entrare nel metodo/area

synchronizedSe un oggetto ha più di un blocco sincronizzato, comunque uno solo di questi può essere attivo. Un metodo synchronized può essere eseguito da un solo thread alla volta e quando un thread sta eseguendo un metodo synchronized nessun altro thread può eseguire alcun altro metodo synchronized dello stesso oggetto. I metodi synchronized hanno accesso esclusivo ai dati incapsulati nell'oggetto solo se a tali dati si accede esclusivamente con metodi synchronized. Di conseguenza i metodi non synchronized non sono esclusivi e quindi permettono l'accesso concorrente ai dati.Programmazione Concorrente e Distribuita Page 7sono esclusivi e quindi permettono l'accesso concorrente ai dati. La sincronizzazione è costruita attorno al lock intrinseco oppure a un monitor lock. Ogni oggetto ha associato con se stesso un lock intrinseco:• Thread che hanno bisogno di un accesso esclusivo ad un oggetto devono ottenere il lock intrinseco

sull'oggetto prima di accedervi e successivamente rilasciare il lock intrinseco quando ha finito con loro.

• Tra il tempo di acquisizione e di rilascio del lock un thread ha un lock intrinseco.
• Nel tempo in cui un thread ha un lock intrinseco, nessun altro lock può avere lo stesso lock. Gli altri thread vengono quindi bloccati mentre aspettano di acquisire il lock.

Quando un thread invoca il metodo synchronized, assume automaticamente il lock intrinseco dall'oggetto del metodo.

Quando viene invocato un metodo statico il thread acquisisce il lock intrinseco dalla classe dell'oggetto associato con la classe.

Metodi e blocchi synchronized non assicurano l'accesso mutualmente esclusivo ai dati "statici" dato che sono condivisi da tutti gli oggetti della stessa classe.

Per accedere in modo sincronizzato ai dati statici si deve ottenere il lock su questo oggetto di tipo Class (in Java ogni classe è assegnato un oggetto di classe Class):

• Si

può dichiarare un metodo statico come synchronized.

Si può dichiarare un blocco come synchronized sull'oggetto di tipo Class. Bisogna però stare attenti al fatto che il lock a livello classe non si ottiene quando ci si sincronizza su un oggetto di tale classe e viceversa.

Si può quindi ereditare da una classe non sincronizzata e ridefinire un metodo come synchronized che richiama semplicemente l'implementazione della superclasse. Questo assicura che gli accessi ai metodi nella sottoclasse avvengano in modo sincronizzato.

Tramite la sincronizzazione un thread può modificare in modo sicuro dei valori che potranno essere letti da un altro thread, ma un thread non può sapere se i valori sono stati modificati. Per questo motivo oltre a synchronized vengono usati altri meccanismi (wait) che mettano in attesa un thread e che lo risveglino quando le condizioni sono cambiate.

Il metodo wait e il metodo notifyIl metodo wait viene utilizzato per

mandare in attesa il thread chiamante e per rilasciare il lock sull'oggetto. Un thread può chiamare il metodo wait all'interno di un metodo sincronizzato, cioè quando detiene un lock.

La SVM (support vector machine) mantiene un elenco di tutti i thread che sono pronti per essere eseguiti ("Ready List"). Quando un thread va in wait la SVM lo sposta in una "Wait List" e rilascia il lock sull'oggetto. Quando un thread in attesa viene svegliato (notify) la SVM lo sposta nella ready list. Programmazione Concorrente e Distribuita Page 8

Una chiamata notify sposta un thread qualsiasi dal "wait set" di un oggetto al "ready set". Una chiamata a notifyAll sposta tutti thread dal "wait set" di un oggetto al "ready set".

Monitor

Il monitor è una struttura dati con tutti i metodi synchronized in modo che, in un dato momento, un solo thread può essere eseguito in qualsiasi metodo. In Java se un thread T1

soluzioni: 1. Problema: Deadlock Soluzione: Utilizzare il metodo `synchronized` per garantire l'accesso esclusivo ai metodi dell'oggetto O1. In questo modo, un solo thread può entrare in un metodo sincronizzato alla volta, evitando il deadlock. 2. Problema: Race condition Soluzione: Utilizzare il metodo `synchronized` per garantire l'accesso esclusivo ai metodi dell'oggetto O1. In questo modo, i thread dovranno attendere il proprio turno per eseguire i metodi sincronizzati, evitando race condition. 3. Problema: Concorrenza non controllata Soluzione: Utilizzare il metodo `synchronized` per garantire l'accesso esclusivo ai metodi dell'oggetto O1. In questo modo, i thread dovranno attendere il proprio turno per eseguire i metodi sincronizzati, evitando conflitti e garantendo la correttezza del programma. 4. Problema: Accesso simultaneo a risorse condivise Soluzione: Utilizzare il metodo `synchronized` per garantire l'accesso esclusivo ai metodi dell'oggetto O1. In questo modo, i thread dovranno attendere il proprio turno per accedere alle risorse condivise, evitando accessi simultanei e garantendo la coerenza dei dati. Ricorda che l'utilizzo del metodo `synchronized` può comportare una diminuzione delle prestazioni in caso di alta concorrenza. Pertanto, è importante valutare attentamente l'utilizzo di questa tecnica in base alle esigenze specifiche del tuo programma. Un problema ricorrente che si verifica frequentemente in programmazione concorrente è l'esigenza di coordinare le attività dei thread. Uno dei problemi più ricorrenti che si può ottenere lavorando con i thread è il Deadlock, cioè quando due thread A e B sono continuamente in attesa di un evento che può avvenire soltanto tramite l'altro thread. Esistono 4 condizioni necessarie affinché un deadlock si verifichi: 1. Mutual exclusion: solo un'attività concorrente per volta può utilizzare una risorsa 2. Hold and wait: devono esistere concorrenti che sono in possesso di risorse mentre stanno aspettando altre risorse da acquisire 3. No preemption sulle risorse: una risorsa può essere rilasciata solo volontariamente da un'attività concorrente 4. Circular wait: deve esistere una catena circolare di attività concorrenti tale che ogni attività mantiene bloccate delle risorse che contemporaneamente vengono richieste dai thread successivi Un deadlock può verificarsi in ogni programma concorrente. La principale causa dei deadlock è l'uso di circolarità nel lock degli oggetti. Esistono dei modi per evitare il Deadlock: - Deadlock prevention: evitare che almeno una delle quattro condizioni (sopra elencate) richieste per il deadlock non si verifichi mai - Deadlock removal: non si previene il deadlock ma lo si risolve quando ci si accorge che è avvenuto, ad esempio rendendo le risorse preemptible Programmazione Concorrente e Distribuita Page 9 - Paradigmi di Comunicazione giovedì 26 aprile 2018 14:41 Vari modi di comunicazione tra i thread Signals - Thread attende un segnale inviato da altro thread - Persistent signal: rimane impostato fino a quando un thread lo riceve - Transientrilascia uno o più thread in attesa, si perde se non ce ne sono in attesa

Due ruoli dei thread:

• Chi aspetta il segnale
• Chi invia il segnale atteso

L'interfaccia dei thread è separata, in modo che ogni thread può chiamare l'operazione più appropriata. Creiamo due interfacce con metodi distinti, e una classe astratta che li implementa, dove richiamerà i metodi definiti.

Buffer:

• Contiene dati che dopo essere stati letti verranno distrutti

Blackboard:

• Simile al buffer ma:
• Ha una lettura non distruttiva dei dati
• Messaggi lasciati sulla blackboard sono preservati fino a che non vengono cancellati, sovrascritti o invalidati
• La scrittura non è bloccante

Operazioni su blackboard:

• Messaggi scritti --> write()
• Messaggi cancellati --> clear()
• Blocco canale fino a che i dati rimangono non validi --> read()
• Se ci sono dati disponibili --> dataAvailable()