«

»

nov 09

Uso avanzato dei Mutex, i 5 Filosofi (C++0x – C++11)

Nell’articolo precedente ho parlato del mutex e del suo uso semplice con la lock_guard. in questo tratterò gli altri tipi di guard e l’uso avanzato dei mutex

unique_lock

Con unique_lock un mutex può fare molto di più di quello che permette la lock_guard :

  • Si può cercare di prenotarlo in maniera non bloccante ( se è libero lo si occupa, se non è libero non si attende)
  • Si può cercare di prenotarlo fornendo un timeout massimo di attesa ( se si tratta di un timed mutex ovviamente)
  • Si può accedere direttamente alle funzioni del mutex

e un sacco di altre cose per le quali vi rimando a una reference ( lo so, non è ufficiale… ma non ho trovato di meglio )

Timed mutex e la prenotazione con timeout massimo

Disponendo di un timed mutex potremmo per esempio eseguire questo:

std::timed_mutex m;
std::unique_lock<std::timed_mutex>
 lk(m,std::chrono::milliseconds(5));
if(lk)work()
}

Questa funzione prova ad accedere al mutex aspettando massimo 5 millisecondi, il valore della lock si usa per determinare se l’accesso è avvenuto o no

Accesso alle funzioni interne del mutex

Attraverso la unique_lock possiamo accedere alle funzioni del mutex, ma questa volta le eccezioni sono gestite.

std::mutex m;
void zona_critica()
{
 std::unique_lock<std::mutex> lk(m);
 // in questo momento il mutex è occupato
 lk.unlock();
 // in questo momento il mutex è libero
 lk.lock();
 //in questo momento il mutex è di nuovo occupato
}

Possiamo anche evitare che il mutex venga occupato all’allocazione della unique_lock utilizzando un costruttore diverso:

std::mutex m;
void zona_critica()
{
 std::unique_lock<std::mutex> lk(m,std::defer_lock_t());
 // in questo momento il mutex è libero
 lk.lock();
 // in questo momento il mutex è occupato
 lk.unlock();
 //in questo momento il mutex è di nuovo libero
}

Prenotazione multipla

Un problema molto comune nella programmazione concorrente è la necessita da parte di un processo di accedere in maniera esclusiva a più risorse, è un problema che se gestito male può causare facilmente deadlock o starvation in quanto se un processo che ha acquisito parte delle risorse necessarie attende altre risorse per continuare e queste risorse sono bloccate da altri processi anche loro in attesa tutti i processi restano bloccati in attesa l’uno dell’altro, in questo caso le stl ci vengono in aiuto dandoci un costrutto che permette di bloccare n mutex restando in attesa ma non bloccandoli

void prenota(std::mutex *a ,std::mutex *a)
 {
 std::unique_lock<std::mutex> lock_a(*a, std::defer_lock);
 std::unique_lock<std::mutex> lock_b(*b, std::defer_lock);
 std::lock(lock_a,lock_b);

 // fai qualcosa di critico
 }

Il problema dei 5 filosofi

Illustrazione originale dal testo di Dijkstra

Un problema molto interessante che illustra la potenzialità di questo costrutto è il problema dei 5 filosofi a cena, esso è stato formulato da Dijkstra intorno al 1965, per mettere alla prova le primitive di sincronizzazione dell’epoca ( i semafori fondamentalmente) il problema è questo (cito dal testo di Silberschatz) :

Si considerino cinque filosofi che passano la vita pensando e mangiando. I filosofi con­dividono un tavolo rotondo circondato da cinque sedie, una per ciascun filosofo. Al cen­tro del tavolo si trova una zuppiera colma di riso, e la tavola è apparecchiata con cinque bacchette. Quando un filosofo pensa, non interagisce con i colleghi; quan­do gli viene fame, tenta di prendere le bacchette più vicine: quelle che si trovano tra lui e i commensali alla sua destra e alla sua sinistra. Un filosofo può prendere una bacchetta alla volta e non può prendere una bacchetta che si trova già nelle mani di un suo vicino. Quando un filosofo affamato tiene in mano due bacchette contemporaneamente, man­gia senza lasciare le bacchette. Terminato il pasto, le posa e riprende a pensare.

“Il problema dei cinque filosofi è considerato un classico problema di sincronizzazione, non certo per la sua importanza pratica, e neanche per antipatia verso i filosofi da parte degli informatici, ma perché rappresenta una vasta classe di problemi di controllo della concorrenza, in particolare i problemi caratterizzati dalla necessità di assegnare varie risorse a diversi processi evitando situazioni di stallo e d’attesa indefinita.” la parola starvation deriva proprio da questo problema… se non si riesce a gestire la cosa i filosofi muoiono di fame ( to starve in inglese)

Una semplice soluzione consiste nel rappresentare ogni bacchetta con un mutex: un filosofo tenta di afferrare ciascuna bacchetta eseguendo un’operazione lock su quel mutex e la posa eseguendo una unlock.

Partendo da questo modello possiamo cominciare a cercare una soluzione, quella più immediata potrebbe esere:

un filosofo prende la bacchetta a destra, poi quella a sinistra e poi mangia

ma cosa succede se tutti prendono contemporaneamente la forchetta di destra? un deadlock, muoiono di fame aspettando che qualcuno liberi qualcosa ma nessuno libererà mai niente.

un’altra soluzione potrebbe essere:

Un filosofo di numero pari prende prima la forchetta di destra e poi quella di sinistra, un filosofo dispari il contrario

Ma questo è barare, scartiamola

Ci rendiamo conto che un filosofo deve rilasciare la bacchetta se non può prendere la seconda, qualcosa del tipo

Un filosofo prende la bacchetta di destra, poi cerca di prendere quella di sinistra (trylock) e se non può le posa entrambe e riprova in seguito

ma che succede se i filosofi partono insieme? l’algoritmo va in loop: tutti prendono quella di destra, nessuno può prendere quella a sinistra, tutti posano tutto e si ricomincia, le operazioni necessitano di essere eseguite in maniera atomica:

Un filosofo cerca di prendere entrambe le bacchette contemporaneamente, se non può aspetta

Questo comportamento non può essere costruito direttamente usando i singoli mutex, ma possiamo farlo con il nostro std::lock(lock_a,lock_b)

La soluzione tradizionale necessita della costruzione di un Monitor, ma non me ne occuperò qui, sfruttiamo a pieno le stl e riduciamo il problema a una cosa banale, con buona pace di Dijkstra

...
class Filosofo {
public :

    int id;
    mutex *destra;
    mutex *sinistra;
    Filosofo(int n, mutex *d, mutex *s) {
        id=n;
        destra=d;
        sinistra=s;
    }

    void pensa() {
        string argomenti[5]= {
            "Alla fame nel mondo",
            "Al punto G",
            "All origine dell Universo",
            "Al senso della vita",
            "Alla domanda la cui risposta e' 42"
        };
        cout << id << ": Sto pensando... " << argomenti[id] << endl;
        usleep( 10000 * ( rand() % 90 + 10 ));
    };

    void mangia() {
        printf("%d: Cerco le bacchette...\n",id);
        std::unique_lock<std::mutex> lock_a(*destra, std::defer_lock);
        std::unique_lock<std::mutex> lock_b(*sinistra, std::defer_lock);
        std::lock(lock_a,lock_b);
        printf("%d: Sto mangiando...\n",id);
        usleep( 30000 * ( rand() % 90 + 10 ));
        printf("%d: Poso le bacchette, sazio\n",id);
    };

    void operator()() {
        printf("%d: Penso quindi sono \n",id);
        usleep( 30000 * ( rand() % 90 + 10 ));
        for(int a=0; a<5; a++) {
            pensa();
            mangia();
        }
    }
};
...

La versione completa del codice si trova qui

per questo articolo è meglio fermarmi, sta diventando troppo lungo, le condition le tratto nel prossimo

References

Se siete interessati alla versione originale del problema di Dijkstra ,risolta interamente con i semafori, potete dare un occhiata a questo testo su google docs, se poi avete anche interessi archeologici c’è la scan della versione originale qui (vi avviso, Dijkstra coda in Agol xD)

Che Dio benedica l’università del texas e google docs, visto che la versione ufficiale nel sito della Springer costa 35€

Il testo di Silberschatz che citavo è “Sistemi operativi. Concetti ed esempi” di Abraham Silberschratz, Peter Baer Galvin, Greg Gagne. potete dargli un occhiata qui , è finora il miglior libro tradotto in italiano sui sistemi operativi in cui mi sia imbattuto

L’ambiente utilizzato

Man mano che ci inoltriamo nella parte più raffinata della libreria abbiamo bisogno di versioni sempre più recenti, stavolta ci serve la 4.6 di gcc oltre a tutte le lib descritte nell’articolo iniziale sui thread

Questo post fa parte di una serie, gli altri post riguardanti il Cpp0X sono:

Share Button

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

Puoi usare i seguenti tag ed attributi HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>