Design di applicazioni Multi-Threading

Mentre la maggior parte del materiale disponibile si occupa principalmente delle primitive di programmazione multi-threading, questa raccolta di link e commenti è unica nel suo genere perché riguarda il design di applicazioni multi-threading.

Cerca di chiarire quali sono gli obiettivi generali del design di una applicazione multi-threading, descrive 5 modelli di programmazione delle applicazioni multi-threading cioè i 5 pattern applicativi architetturali e diversi design pattern per la programmazione multi-threading.

(immagine di http://www.galerieperrotin.com/ )

In sintesi

Ecco in estrema sintesi alcune delle indicazioni utili illuminanti e sorprendenti che sono discusse nel documento:

 

Di quali applicazioni stiamo parlando

Stiamo parlando di applicazioni Object Oriented eseguite su PC e Server comuni che usiamo ogni giorno. Hanno la architettura classica di Von Neumann. Sono PC o Server che possono avere un processore anche multi-core o 2 e più processori simmetrici paralleli.

E possono creare nuovi thread di esecuzione che procedono contemporaneamente (in modo simulato grazie allo scheduling del sistema operativo o realmente su differenti processori o core).

In dettaglio:

Su queste macchine il flusso di elaborazione avanza man mano che ogni istruzione viene eseguita dal microprocessore e il flusso cambia a seguito di una operazione di salto (un classico "IF" o un classico  "GOTO" ma a livello di assemly)  a difefrenza delle architetture dove il flusso procede in base ai dati elaborati. Il flusso di esecuzione dei dati è singolo (non ci sono 2 o più processori autonomi e separati con un proprio bus di accesso alla memoria) e anche il flusso dei dati (sono quelli letti dalla RAM del computer invece di essere letti da più RAM distinte anche su altri computer). Secondo la classificazione di Flynn questi PC e Server sono classificati come SISD.

Maggiori info e riferimenti qui: Progettazione di applicazioni multi-threading

Gli obiettivi del disegno di una applicazione multi-threading

Sono 2 i principali obiettivi che si inseguono quando si disegna una applicazione multi-thread:

- Progettazione di app. multi-threading: obiettivi

Qualche esempio pratico

Il disegno deve aiutare a rispondere con facilità a queste domande per ogni punto del codice in cui si guarda :

E deve definire le risposte a queste domande in modo consistente in tutta la applicazione:

 

Sullo Unit Testing di applicazioni multi-threading

  1. La presenza di operazioni concorrenti, che rendono difficoltoso controllare l'ordine in cui determinati eventi chiave possono verificarsi all'interno del contesto che vogliemo sottoporre a test
  2. l'interazione con il sistema operativo, il cui comportamento a livello di thread e processi può variare notevolmente da piattaforma a piattaforma, o anche sulla stessa piattaforma (se consideriamo la JVM come tale).

Il punto 1 fondamentalmente si risolve in un aumento della complessità della scrittura dei test: anzichè una sequenza di eventi che a partire dallo stato di partenza del test mi porta ad uno stato finale da controllare con le assert, nel caso di eventi concorrenti, prendendo in esame due flussi di esecuzione, ho fondamentalmente una sorta di prodotto cartesiano tra le possibili permutazioni di eventi.

A1, A2, A3 e B1, B2, B3 possono dare origine a A1, A2, A3, B1, B2, B3 come a A1, B1, B2, A2, A3, B3 e così via. In certi casi possiamo limitarci alle combinazioni plausibili, in altri dobbiamo verificare il comportamento del sistema anche nei casi non plausibili, A1, A3, B1, A2, ...

La complessità sta sia nell'inidividuazione delle possibili combinazioni, sia nella determinazione di quale sia efettivamente lo stato corretto per ciascuna combinazione. Se le esamini prima è design, se le metti nel test è TDD ma stiamo parlando della stessa cosa.

Ciò che ci interessa è l'ordine: per poter testare efficacemente, ci conviene tenere sotto controllo il tempo rendendo gli eventi chiave controllati da un automa. In altre parole, mockiamo il tempo per testare solo la logica, trasformando due sequenze parallele pseudo casuali in una collezione di possibili sequenze (quindi eliminando il parallelismo), ognina con un suo stato atteso. L'approccio è un po' brutale e non è sempre applicabile: se la catena è di 20 eventi il numero delle possibili permutazioni cresce molto rapidamente e la strategia potrebbe non essere più conveniente rispetto ad un ragionamento empirico o a regole progettuali che ci impediscano di avere catene lunghe di eventi.

Il punto 2 invece ci inguaia, perchè se anche ci sobbarchiamo la complicazione della gestione della concorrenza, riusciamo a testarla con una certa sicurezza solo avendo la garanzia che le primitive sottostanti sono consistenti. Questo ci viene garantito su sistemi transazionali o restando ad un determinato livello di astrazione, mente le cose si complicano se decidiamo (o siamo costretti) a sporcarci le mani con le primitive di sincronizzazione a "basso livello" (semafori e via dicendo). Mockare il sistema operativo è un problema di un ordine di complessità un po' diverso e probabilmente non è giustificabile dal contesto della nostra applicazione (se stessimo realizzando una VM, però magari si). L'altro problema è che la granularità degli eventi è più fine: non è sempre detto che sia possibile pilotarla efficacemente restando nel contesto di un linguaggio di alto livello, o (peggio) che la semplice osservazione del fenomeno influenzi il comportamento applicativo (bug che non avvengono in modalita debug - lo dice la parola stessa - o che non si verificano se stai guardando

Se la concorrenza è in genere un requisito, il livello a cui gestirla può in molti casi essere ancora una scelta, ragion per cui vogliamo renderci il più possibile in condizione di "fidarci" di una piattaforma testata. Sfruttando l'application server, o qualsiasi cosa sia applicabile e testata out of the box, o - in mancanza di questo - facendo scelte il più possibile ripetibili (e trasformandole in primitive) perchè ogni "intreccio" di programmazione concorrente a basso livello è una "bomba probabilistica" di combinazioni tra cui quella che forse un giorno manderà in crash la nostra applicazione.

Gli altri elementi che possono definire il contesto sono il livello di parallelismo: se il problema è la presenza di corse critiche siamo probabilmente in grado di simularle con 2 o 3 catene di eventi ben strutturate, ma se il problema sta nel parallelismo massiccio allora forse è il pardigma del nostro linguaggio ad essere messo in crisi.

                Fine delle considerazioni del Brando... ========

(immagine di http://www.galerieperrotin.com/ )

I 5 modelli di programmazione multi-threading: 5 pattern architetturali

Il modello a sincronizzazione e il modello a competizione

Sono i 2 modelli più famosi perché ricalcano quelli delle primitive di basso livello di programmazione della concorrenza: a scambio di messaggi o a sezione critica (a lock, o a contesa di accesso a risorse condivise), per questo sono ausati.

- Progettazione di app. multi-threading: modelli di programmazione

Questi modelli descrivono 2 opzioni/metafore di disegno della applicazione.

Le 2 principali primitive di basso livesso livello di programmazione della concorrenza funzionano una con lo scambio di messaggi send/receive con rendezvous e l'altra con le sezioni critiche cioè sono molto simili alle 2 metafore di disegno.  Sono comunque cose distinte e la scelta di una non influenza la scelta dell'altra.

Sul modello a sincronizzazione (scambio messaggi) dedi anche Axum (Axum, previously known as Maestro, is a Microsoft incubation language project meant to provide a parallel programming model for .NET through isolation, actors and message passing) Axum, Microsoft’s Approach to Parallelism

Dal thread su XP-IT Matteo dettaglia il modello a sincronizazione detto anche produttore-consumatore detto anche Message Passing :

Non avrai alcuna variabile globale condivisa. I processi comunicano  fra di loro esclusivamente passando messaggi. Non parliamo più di

thread, ma di processi, perché l'essenza di un thread è la condivisione della memoria con altri thread. Il passaggio di messaggi

è asincrono: un processo non si blocca mai in attesa che il ricevente abbia ricevuto il messaggio. La sincronizzazione, quando sia

desiderata, si realizza con un doppio scambio di messaggi avanti e indietro.

Il modello a Transaction Monitor

Degli esempi reali conosciuti sono il Syncronize del Java oppure l'attributo MethodImplOptions.Synchronized di .NET o le Activity di COM+  :

- Progettazione di app. multi-threading: modelli di programmazione

Dal thread su XP-IT Matteo dettaglia il modello a Transaction Monitor:

Il primo pattern che tutti quanti usiamo è il Transaction Monitor.

Salviamo tutto lo stato del sistema in un insieme di variabili globali, il cui unico punto di ingresso è il Transaction Monitor.

Il contratto è, per il codice applicativo

* il codice applicativo raggruppa le operazioni sui dati in una sequenza demarcata da "inizio" e "fine" transazione.

* il codice applicativo garantisce che se ogni transazione (ovvero  sequenze di operazioni elementari demarcate da inizio e fine) porti il sistema da uno stato logicamente consistente a un'altro stato logicamente consistente.

* il codice applicativo *non* fa alcun uso esplicito di mutex o semafori

Mentre per il Transaction Monitor il contratto è

* le transazioni possono essere eseguite in concorrenza, ma il risultato finale è indistinguibile da quello che otterremmo se  venissero eseguite separatamente una dopo l'altra

* più altri dettagli tipo che una transazione viene eseguita per intero oppure non viene eseguita per niente, e che una volta eseguita  il suo effetto è permanente.

Un esempio di implementazione del pattern (in questo caso a granilarità a livello di singolo oggetto) è il Monitor Object

Il modello a Process Monitor

Sempre dal thread su XP-IT Matteo dettaglia anche il modello a Process Monitor.

In Erlang si usa anche un'altro importante pattern: Process Monitor. Che dice:

Quando un'operazione fallisce per qualsiasi motivo, il processo che la sta eseguendo termina. Quando un processo termina, provoca la terminazione del processo che lo ha generato, e così via ricorsivamente fino a che non si termina l'intera applicazione, oppure non si arriva a un processo che ha dichiarato di gestire la terminazione dei suoi figli. Questo sostituisce il meccanismo delle eccezioni dei linguaggi convenzionali, che in Erlang non c'è. Non riesci ad aprire il file? Crash.

Con questo pattern, si partizionano i processi in due parti; c'è un insieme di processi che implementa le operazioni di business, e un insieme di processi che implementano il Process Monitor: fanno partire i processi applicativi, e li fanno ripartire quando crashano. Eventualmente li fanno ripartire anche quando restano bloccati per un tempo superiore al previsto.

Il modello a Concorrenza Transazionale

E' il modo più semplice e più conosciuto.

I Db relazionali definiscono un modello di programmazione e gestione della concorrenza che ogni applicazione deve seguire sempre. Il risultato è che ogni applicazioni multi-utente che fa accesso concorrente a un data-base è molto più semplici da scrivere/modificare/evolvere di una qualsiasi applicazioni multi-threading. E questo anche se i 2 tipi di applicazione hanno molte similitudini e molte cose in comune.

Sul thread in XP-IT questa volta è Stefano a suggerire di adottare il modello a Concorrenza Transazionale:

La concorrenza transazionale: sullo specifico di come approcciare lo sviluppo multithreading,

una buona base di partenza e' la concorrenza transazionale. Molti

concetti sono simili semplicemente sostituendo le istanze alle tuple

(ma immagino di non dirti nulla di nuovo ;) )

A conferma di questa evitenza pratica c'é anche questo studio accademico: Is Transactional Programming Actually Easier?, Department of Computer Science, University of Texas at Austin

Vedi anche Software Transactional Memory (STM.NET) di Microsoft

Design Pattern per la programmazione multi-threading

Disaccoppiare la gestione del multi-threading dalla logica di business

L'idea suggerita su XP-IT da Matteo è di separare la gestione del multi-threading (che è una programmazione di sistema) dalla logica di busimess (che è programmazione applicativa) in armonia con l'insegnamento del modello a concorrenza transazionale.

L'idea è di lasciare la gestione del multi-threadinga componenti del sistema o di terze parti ad esempio Web Server per la comunicazione di messaggi HTTP.

I pattern che seguono sono utili a separare queste due responsabilità:

 

Pattern Command

Io stavo pensando al pattern Command...

"Il Command pattern è uno dei design pattern che permette di isolare la porzione di codice che effettua un'azione (eventualmente molto complessa)

dal codice che ne richiede l'esecuzione; l'azione è incapsulata nell'oggetto Command.

L'obiettivo è rendere variabile l'azione del client senza però conoscere i dettagli dell'operazione stessa. "

http://it.wikipedia.org/wiki/Command_pattern

Mediator

il Mediator per comporre i comportamenti delle classi di business  con quelli del multi-threading (come il Command integra le 2

resposnabilità disaccoppiate business e multi-threading)

Facade

il Facade per nasconde dietro una facciata gli oggetti di business soggetti a multi-threading e li usa facendo prima le chiamate

opportune alle classi per il multi-threading in modo da produrre risultati corretti)

Proxy

il Proxy che inquesto caso fa una cosa simile al Facade ma più orientato al singolo oggetto di business

Decorator

  Il Decorator che aggiunge la resposabilità del multi-threading a una classe di business

TransactionScript + DataMapper

il DataMapper (http://www.martinfowler.com/eaaCatalog/dataMapper.html) per implementare singole operazioni sincronizzate su un oggetto di business e il TransactionScript

(http://www.martinfowler.com/eaaCatalog/transactionScript.html) per combinare più operazioni insieme e gestire anche il dead-lock

Half Sync/Half Async

Half-Sync/Half-Async

Leader/Followers

Leader/Followers

Session/Application

E' la versione più semplice del pattern precedente, che aiuta arealizzare il modello a concorrenza transazionale. E' lao steeo usato ad esempio da IIS (che gestisce ogni chiamata/task in diversi thread) con ASP e ASP.NET  in cui chli oggetti che possono essere acceduti in contemporanea vanno messi su Session (quando sono specifici di una sessione di un client) o su Application (quando sono condivisi da tutti i thread della applicazione) e su quelli vanno usate le opportune primitive di lock quando possono esserci conflitti di accesso. Quindi l'aggiunta di un layer di astrazione di questo servizio di "storage transazionale" può isolare l'implementazione del "servizio" con Sessio/Application e lock dalla Business logic che lo potrà cosi utilizzare in modo trasparente e disaccoppiato.

 

Active Object Pattern

Lo scopo di questo pattern è evidenziare quanti thread ci sono in una applicazione, distinguere i compiti di un thread da quelli di un altro e identificare come quando e chi crea nuovi thread:

Optimistick Locking , Transazioni di compensazione, Double-check e Read/write lock

Lo scopo di questi pattern è di ridurre la durata/superfice di lock/sincronizzazione

Cosi come è buona norma non aprire un form e chiedere input all'utente durante una transazione sul db (perché nulla vieta all'utente di lasciara il form in attesa e cosi bloccare l'intera base dati), è altrettanto buona norma durante un lock o una operazione di sincronizzazione non inviare o ricevere via socket o altre operazioni potenzialmente bloccanti perché ad esempio "problemi di rete" potrebbe far allungare di parecchio la durata del lock o della sincronizzazione bloccando l'intera applicazione. Quando cambiare l'ordine delle operazioni non è sufficente per fare questo, l'uso di code è luna soluzione semplice e efficace per spostare le operazioni potenzialmente bloccanti fuori dai momenti i lock e di sincronizzazione.

Ridurre la concorrenza strutturando diversamente i dati

Un esempio che viene dai db è quello di normalizzare i dati (per esempio eliminare una dipendenza funzionale o una ridondanza) diminuendo le operazioni che hanno bisogno di essere eseguite in transazione per garantire la consistenza dei dati. Similmente è possibile strutturare i dati in modo che anche le applicazioni multi-yreading abbiano una esigenza minore di sincronizzazione o concorrenza.

Sono studi teorici per individuare modi sistematici di applicare questa tecnica ad una ampia varietà di casistiche.

Modello a Concorrenza e a Sincronizzazione totalmente equivalenti

Intuitivamente il modello a scambio messaggi (detto anche an sincronizzazione, a produttore-consumatore e anche Message Passing) elminina la necessitá di accedere in modo concorrente a variabili condivise, in realtá i 2 modelli sono perfettamente equivalenti (per chi è curioso, la dimostrazione formale viene fatta  implementando un metodo avendo a disposizione l'altro e poi viceversa).

Ciò che accade invece è che il modello a scambio messaggi porta a strutturare i dati in modo diverso e la diversa struttura a volte porta ridurre la quantità di dati condivisi cosi come può accadere che in alcuni casi la aumenta.  Insomma se provare a esplorare entrambi i modi può suggerire strutturazioni dei dati più efficaci riguardo le necessità di locking, poi la scelta tra i due modelli può essere fatta tranquillamente in base alla metafora più adatta al problema/disegno in questione.

Prevenzione del deadlock: Ordered Lock, Wait All Lock, Mediator e Data Mapper

Gestione del deadlock

 

La terna Produttore-consumatore-buffer, Deadlock, Produttore-consumatore multipli e Send e Receive bloccanti

(immagine di http://www.galerieperrotin.com/ )

Sviluppi correnti

La teoria sulla programmazione concorrente, il lock, il deadlock è consolidata da tempo.

Gli sviluppi correnti percorrono in 2 direzioni:

  1. Implementare un framework o una estensione al linguaggio che metta a disposizione un modello di programmazione della concorrenza semplice da usare quasi quanto il modello a concorrenza transazionale cioè quello dei data base, e che dia però più flessibiltà per poter realizzare una varietà di applicazioni differenti (mentre quello per i db è dedicato a un dominio definito e specifico). Il framework dovrebbe spingere a separare la programmazione del multi-threading da quella di business.
  2. Ricerche accademiche su teorie per individuare modi estesi e sistematici di strutturare i dati, cioè l'informazione, per ridurre al minimo i dati a cui è necessario accedere in modo concorrente (un po come hanno fatto le forme normali per i db)

Libri

Questi sono alcuni libri che affrontano in parte l'argomento dal punto di vista del design: