Threads

Mi sono ripromesso di alternare post teorici e pratici, e questa è la volta della pratica. Gli esempi di codice saranno in C/C++. Per chi non conosce questo linguaggio, ci sono anche troppi modi per mettersi in pari. Comunque, se proprio non avete voglia di studiare, provate a seguirmi lo stesso: non è rocket science! E’ solo semplice programmazione, e inoltre cercherò di spiegare tutto per benino e non fare troppo il noioso.

Ingredienti

  • Gli esempi che riporto sono per Unix/Linux, ma c’è una qualche possibiltà che funzionino anche su Windows se scaricate ed installate l’indispensabile Cygwin.
  • Un editor di testo (vi, emacs, gedit, kate, notepad, etc.)
  • Il compilatore Gnu gcc/g++
  • Un po’ di pazienza, eh.

Tempo di preparazione e difficoltà

15 minuti circa, i principianti potrebbero metterci un filino di più.

Procedimento

Se vogliamo scrivere del codice che sfrutti il parallelismo della macchina, dobbiamo prima di tutto individuare le parti di codice da mandare in parallelo. Purtroppo il linguaggio C/C++, al contrario di altri linguaggi di programmazione come Java, non supporta nativamente alcun costrutto per il parallelismo. Bisogna quindi arrangiarsi con delle librerie di funzioni. In questa puntata cominciamo con la libreria dei POSIX threads o semplicemente pthread.

Un thread è una funzione che può eseguire in parallelo con altre funzioni. In un programma sequenziale un pezzo di codice può ad un certo punto invocare una funzione per svolgere dei calcoli. Il flusso di esecuzione quindi fa un salto:passa dall’eseguire il codice sequenziale ad eseguire la funzione. Quando la funzione ha terminato la sua esecuzione, il processore ritorna ad eseguire le istruzioni immediatamente successive all’invocazione della funzione. In pratica, considerate il seguente programmino sequenziale:

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    while (a != b) {
        if (a < b) b = b - a;
        else a = a - b;
    }
    return a;
}

int main()
{
    int k1 = 12;
    int k2 =  8;
    int c = gcd(k1, k2);
    cout << "Massimo comun divisore: " << c << endl;
}

Per compilarlo, copiatelo in un editor e salvate il file chiamandolo, ad esempio, seq.cpp. Quindi, lanciate un terminale, spostatevi nella directory dove avete salvato il file, e compilate con il comando:

g++ seq.cpp -o seq

A questo punto, eseguite il programma, sempre da terminale, scrivendo:

./seq

e dovrebbe saltar fuori la scritta

Massimo comun divisore: 4

Questo è un programma sequenziale in C/C++, che parte sempre e immancabilmente eseguendo la funzione main. La quale, dopo aver dicharato e inizializzato le variabili k1 e k2, dichiara la variabile c, e gli assegna il risultato dell’invocazione della funzione gcd(). Mentre gcd() esegue il suo codice, la funzione main() non sta eseguendo! Solo quando gcd() ha completato la sua esecuzione con l’istruzione return, il main() può proseguire. In pratica, c’è sempre un solo flusso di esecuzione, e il processore lo segue pedissequamente, eseguendo le istruzioni una dopo l’altra.

In un sistema con più processori, potremmo voler eseguire alcune funzioni in parallelo. Per esempio, mentre calcoliamo il massimo comun divisore, potremmo voler calcolare anche il minimo comune multiplo su un altro processore. I due calcoli sono indipendenti, e possono essere portati avanti contemporaneamente. Per questo abbiamo bisogno di sdoppiare il flusso di esecuzione.

Per lanciare un funzione in parallelo, si usa la chiamata di libreria pthread_create(). Ecco l’esempio.

#include <iostream>
#include <pthread.h>
using namespace std;

int gcd(int a, int b)
{
    while (a != b) {
        if (a < b) b = b - a;
        else a = a - b;
    }
    return a;
}

int lcm(int a, int b)
{
    int d = 2;
    int l = 1;
    bool f = false;
    while (a != 1 || b != 1) {
        if (a % d == 0) { a /= d; f = true; }
        if (b % d == 0) { b /= d; f = true; }
        if (f) l *= d;
        else d++;
        f = false;
    }
    return l;
}

// struttura per passare i parametri al thread
struct Params{
    int p1, p2;
    int ret;
};

void *thread(void *arg)
{
    Params *p = (Params *)arg;
    p->ret = gcd(p->p1, p->p2);
    return 0;
}

int main()
{
    int k1 = 12;
    int k2 =  8;
    pthread_t tid;
    // parametri del thread
    Params p = { k1, k2, 0 };
    // creazione del thread
    pthread_create(&tid, 0, thread, &p);
    // intanto che lui esegue, faccio altro
    int l = lcm(k1, k2);
    cout << "Minimo comune multiplo: " << l << endl;
    // aspetta che il thread termini (se non ha già terminato)
    pthread_join(tid, 0);
    cout << "Massimo comun divisore: " << p.ret << endl;
}

Supponendo che abbiate copiato il codice in un file chiamato mcd_mcm.cpp, il comando per compilare questa volta è:

g++ mcd_mcm.cpp -lpthread -o mcd_mcm

Infatti, stavolta dobbiamo linkare la libreria dei pthread.

Veniamo al codice. Fino alla riga 27 abbiamo semplicemente le due funzioni per calcolare il massimo comun divisore con l’algoritmo di Euclide (funzione gcd()) e quello per calcolare il minimo comune multiplo (funzione lcm()). Purtroppo non possiamo direttamente parallelizzare queste funzioni. La libreria dei pthread, infatti, richiede che le funzioni che possono diventare dei thread abbiano un prototipo (ovvero una forma) ben precisa: devono prendere un parametro di tipo void *, e restituire un puntatore dello stesso tipo. Alla riga 35 abbiamo un esempio di funzione con il giusto prototipo.

Per far funzionare le cose, dobbiamo adattare il passaggio dei parametri: gcd() prende 2 interi, mentre thread() prende solo un parametro ma di tipo molto generico e malleabile. Quindi, mi sono dovuto inventato un modo per passare i parametri nel modo corretto tramite un adattatore (per fare un’analogia, è un po’ come usare l’adattatore da spina di corrente shuko a presa con 3 poli!). La struttura Params alle righe 30-33 serve appunto a memorizzare i parametri da passare alla funzione gcd(), e il valore di ritorno. Il codice del thread (righe 37-39) converte prima il parametro arg da puntatore generico (void) ad un puntatore a Params. Quindi, chiama la funzione gcd() passando come parametri i campi p1 e p2, e memorizza il risultato nel campo ret.

Vediamo ora la funzione principale main() (che, vi ricordo, è la prima a partire): prima preparo i parametri in una struttura Params (riga 48). Poi creo il thread (riga 50). Quando la pthread_create() ha terminato, il codice della funzione thread() comincia ad eseguire per conto suo, sperabilmente su un altro processore. Abbiamo sdoppiato il flusso di esecuzione!

La funzione pthread_create() prende 4 parametri: il primo è un parametro di uscita, e al ritorno della funzione conterrà un numero che indentifica il thread univocamente all’interno del sistema operativo; ci servirà tra poco. Il secondo parametro sono gli attributi del thread, e poiché per ora non ci interessano, ho specificato 0 (ovvero, voglio il comportamento di default). Il terzo parametro è il nome della funzione da lanciare in parallelo. Il quarto parametro verrà copiato pari pari nel parametro arg della funzione thread, ed infatti ho messo l’indirizzo della struttura p che avevo poc’anzi preparato.

Dato che il thread va per conto suo, la funzione main() continua ad eseguire in parallelo, e può ad esempio calcolare il minimo comune multiplo. Dopo aver finito, ci accertiamo che anche il thread() abbia finito, chiamando la funzione pthread_join(), che fa aspettare il main() fin quando il thread() non ha completato. Può succedere che la funzione thread() sia molto più veloce e finisca prima del main(): in tal caso la pthread_join() non fa niente. Come facciamo a specificare di quale thread vogliamo attendere la terminazione? Ovvio! passandogli la variabile tid che contiene l’identificatore unico del thread. E infine, stampiamo il risultato sul terminale.

Conclusioni

Abbiamo visto come mandare delle funzioni in parallelo al programma principale. A dire la verità, il programma che vi ho presentato è un po’ stupido, non trovate? Non è che il parallelismo sia stato inventato per fare queste cose! Nella prossima puntata, vedremo un esempio un po’ più calzante, in cui metteremo al lavoro sul serio i nostri dual-core.

Ditemi, l’avete trovato difficile? Lo so, è un ambiente di programmazione un po’ ostico, ma se avrete pazienza, fra un paio di post ve ne presenterò uno apparentemente molto più semplice.

Bibliografia minima

Se avete difficoltà con le funzioni di libreria che vi ho presentato, potete leggervi il manuale. Se avete installato le man pages sul vostro Linux, digitate sul terminale

man pthread_create

per avere la descrizione della funzione, dei suoi parametri, e dei suoi valori di ritorno. E così per ogni funzione della libreria pthread. Le man pages di posix sono nel pacchetto debian/ubuntu manpages-posix-dev.

Alternativamente, guardate un po’ qui.

E infine, se proprio non sapete fare a meno dell’italiano, ci sono gli appunti del corso di sistemi operativi, scritti anche dal sottoscritto. Buona lettura e a presto!

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • hronir  Il 27 maggio 2010 alle 22:58

    Vi seguo, eh?
    Ci sono differenze concettuali profonde fra la programmazione a thread e quella pensata per cluster di PC, e.g. via MPI? Forse solo quella che i thread sono pensati per parallelizzazioni sporadiche, “dove capita”, al volo, mentre codice per cluster scritto con MPI è pensato per una parallelizzazione più massiccia, in cui tutto il codice procede in parallelo e in cui sono i punti di contatto e di comunicazione/attesa reciproca ad essere più sporadici?

    • glipari  Il 28 maggio 2010 alle 09:02

      La differenza fondamentale è nel modello di interazione fra gli algoritmi. Nella programmazione a thread, il modello è “a memoria comune”, mentre in MPI il modello è a “message passing”. Mi spiego meglio.

      Nella programmazione a thread esistono delle variabili in memoria (ad esempio l’array di cui sopra) che sono condivise tra tutti i thread e tutti possono leggere/modificare. Ne esiste sempre e solo una sola copia globale, e tutti possono vedere in ogni momento quali sono i suoi valori. In altre parole, esiste un concetto di stato globale.

      Nella programmazione a “message passing”, invece, non esiste il concetto di stato globale, ma solo di stato locale. Ogni attività parallela ha le sue variabili, diverse da quelle degli altri, e completamente locali. Se vuole comunicare con gli altri task/thread/processi o come diavolo si chiamano, deve mandare dei messaggi.
      MPI è costruita in maniera efficiente per fare appunto questo.

      Nei cluster non è facile avere un concetto di memoria globale distribuita. Come si fa a rendere consistente il valore di una variabile attraverso vari nodi che comunicano via rete e possono essere anche dall’altra parte del mondo? Costerebbe molto in termini di implementazione. Ecco perché nei cluster e nel GRID è meglio MPI. Nei PC multicore, invece, c’è già un’unica memoria RAM condivisa e globale, mantenuta consistente via hardware, per cui è più semplice la programmazione multithread.

      Tutto dipende dal “livello” di interazione, come avrai già intuito, ma anche dal supporto hardware. Comunque ci torneremo spesso su questa cosa perché è cruciale per il futuro della programmazione sui multicore/manycore…. 🙂

  • hronir  Il 28 maggio 2010 alle 09:59

    Ecco, non avevo pensato alla memoria condivisa.
    Però la differenza che dici sta “sotto il cofano”, giusto? Voglio dire, nell’esempio qui sopra non c’è davvero alcuna variabile che è pensata per essere letta “whenever” da più di un thread. Anzi, il thread secondario per essere lanciato deve farsi la sua “sandbox” (void *arg) su cui pasticciare e in cui mettere poi il risultato per poterlo poi passare thread principale.
    Immagino quindi che la differenza che sottolinei stia nel come è implementato pthread rispetto a come è implementato MPI…
    O ci sono forse davvero dei modi, nel multithread, di avere davvero memoria condivisa? Intendo condivisa anche a livello algoritmico… (mi viene in mente un sistema di agenti indipendenti ed asincroni che comunicano via messaggi persistenti à la publish-subscribe…)

    • glipari  Il 28 maggio 2010 alle 11:49

      Si, c’è il modo per interagire a memoria condivisa sui thread. Se aspetti fino al prossimo post te lo dimostro: faremo un calcolo stupidissimo su un array gigantesco.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: