Le Condition

Le Condition sono un meccanismo di sincronizzazione che permette ai thread di sospendersi in attesa che avvenga un evento e di essere risvegliati quando l’evento accade, permettono quindi di creare delle code di attesa.

Nelle STL le condition sono oggetti della classe std::condition_variable , i metodi fondamentali per usarle sono tre:

• wait() permette di accodarsi alla condition
• notify_one() notify_all() permettono di risvegliare uno o tutti i thread in attesa sulla coda (nell’implementazione tradizionale dei pthread si chiamavano signal e broadcast)

A una Condition è sempre associato un mutex per evitare race condition che potrebbe creare un thread che si sta preparando a una wait mentre un altro thread esegue una signal, la signal potrebbe infatti avvenire contemporaneamente alla wait e venire quindi persa creando un deadlock, può essere usato un mutex qualunque o si può creare un mutex proprio della condition

Vediamone il funzionamento con un semplice codice: 10 thread si mettono in coda su una condition e un altro thread li sveglia uno per volta

#include <iostream>
#include <thread>
#include <cstdlib>
#include <mutex>
#include <condition_variable>

using namespace std;

class Worker
{
public :

    int numero;
    std::condition_variable *coda;
    mutex *m;
    Worker(int n, std::condition_variable *cond, mutex *mtx)
    {
        coda=cond;
        numero=n;
        m=mtx;
    }
    void operator()()
    {
        cout << "Thread"<< numero << " allocato, mi metto in coda" << endl;
        std::unique_lock<std::mutex> lk(*m);
        coda->wait(lk);
        cout << "Thread"<< numero << " risvegliato dalla coda" << endl;
    }
};

int main()
{
    std::condition_variable *coda= new condition_variable();
    mutex *m= new mutex();
    int a;

    std::thread* threads[10];

    for(a=0;a<10;a++){//creo
        threads[a]= new std::thread(Worker(a+1,coda,m));
        usleep( 100000 );
    }
    for(a=0;a<10;a++){//sveglio
        usleep( 1000 * ( rand() % 900));
        coda->notify_one();
    }
    for(a=0;a<10;a++)//aspetto termine
    {
        threads[a]->join();
        delete(threads[a]);
    }
};

Ma le cose non sono così semplici…

• Malgrado di solito non succeda le specifiche dei pthread non garantiscono che l’ordine in cui i thread si sveglino sia uguale a quello in cui si addormentano, quindi in caso di applicazioni dove l’ordine degli accessi è importante questo va verificato esplicitamente.
• Un altra cosa che potrebbe succedere ( e questa è più grave ) è che più di un thread venga liberato dalla coda, quindi i thread appena svegliati devono di nuovo verificare che la condizione che li ha fatti accodare sia stata soddisfatta ed eventualmente rimettersi in coda.

Il problema del barbiere addormentato

Un barbiere di Lisbona...

Vediamo un applicazione delle condition a un problema più complesso, il problema del barbiere addormentato di Dijkstra. il problema è definito in questo modo:

Un negozio di barbiere è costituito da una sala con una sola poltrona sulla quale si accomoda il cliente che viene servito e da una sala d’attesa con n sedie. Se non ci sono clienti da servire il bar­biere va a dormire. Se arriva un cliente e tutte le sedie della sala d’attesa sono occupate, il clien­te va via, mentre, se c’è una sedia libera e il barbiere è occupato, il cliente attenderà, seduto, il proprio turno. Se il barbiere sta dormendo (cioè è libero, senza clienti in attesa), il cliente lo sve­glia e viene servito subito.

La soluzione è più prolissa di quello che potrebbe sembrare a prima vista, tralaltro nell’implementarlo ho istintivamente usato un monitor anche se non ho accennato a questo tipo di costrutti, ne do soltanto una breve definizione OOP

Un monitor è un oggetto che incapsula la risorsa ed espone i metodi per accedervi in maniera sicura

In questo caso, come si vede nel sorgente sottostante, il contatore delle sedie occupate è nascosto dentro la classe Stanza che mette a disposizione i metodi per occupare e liberare una sedia mantenendoli sincronizzati attraverso un semaforo proprio della classe.

#include <iostream>
#include <thread>
#include <cstdlib>
#include <mutex>
#include <condition_variable>

using namespace std;

int dormi(float base, float variabile)
{
    int k=1000*1000;
    int base_i=(int)base*k;
    int variabile_i=0;
    if(variabile>0)variabile_i=rand() % (int)(variabile*k);
    usleep(base_i+variabile_i);
    return base_i+variabile_i;
};

class Stanza
{
private:
    int occupate;
    std::mutex monitor_m;

public:

    std::condition_variable attesa;

    std::mutex attesa_m;
    std::condition_variable poltrona;
    std::condition_variable letto;
    std::mutex barbiere;
    int sedie;

    int prenota()
    {
        std::unique_lock<std::mutex> lk(monitor_m);
        if(occupate>=sedie)return -1;
        occupate++;
        cout << occupate << " sedie occupate"<<endl;

        return occupate;
    }

    int guarda()
    {
        std::unique_lock<std::mutex> lk(monitor_m);
        return occupate;
    }

    int libera()
    {
        std::unique_lock<std::mutex> lk(monitor_m);
        occupate--;
        cout << occupate << " sedie occupate"<<endl;
        return occupate;
    }

    Stanza(int n_sedie)
    {
        this->sedie=n_sedie;
        occupate=0;
    }
};

class Barbiere
{
public :

    int numero;
    int azioni;
    Stanza *stanza;
    std::unique_lock<std::mutex> *barbiere;
    Barbiere(Stanza *st)
    {
        azioni=0;
        this->stanza=st;
        barbiere= new std::unique_lock<std::mutex>(stanza->barbiere,std::defer_lock_t());

    }
    void operator()()
    {
        while(true)
        {
            cout << "Barbiere controlla se ci sono clienti in attesa"<<endl;

            if(stanza->guarda()==0)
            {
                cout << "Barbiere si addormenta"<<endl;
                std::unique_lock<std::mutex> lk(stanza->barbiere);
                stanza->letto.wait(lk);
            }

            cout << ++azioni <<" Barbiere serve un cliente"<<endl;
            stanza->attesa.notify_one();
            dormi( 2 , 2 );
            stanza->poltrona.notify_one();
        }
    }
};

class Cliente
{
public :

    int numero;
    Stanza *stanza;
    std::unique_lock<std::mutex> *barbiere;
    Cliente(Stanza *st, int n)
    {
        stanza=st;
        numero=n;
        barbiere= new std::unique_lock<std::mutex>(stanza->barbiere,std::defer_lock_t());

    }
    void work()
    {
        cout << "Thread"<< numero << " allocato, entra dal barbiere" << endl;
        int s=stanza->prenota();

        if(s<0)
        {
            cout << "Thread"<< numero << " tutte le sedie sono occupate, esce" << endl;
            return;
        }
        else
        {
            if(s>0)
            {
                cout << "Thread"<< numero << " si siede e aspetta" << endl;
                if (s==1)
                {
                    cout << "Thread"<< numero << " sveglia il barbiere" << endl;
                    dormi(1,0);
                    stanza->letto.notify_one();
                }
                std::unique_lock<std::mutex> lk(stanza->attesa_m);
                stanza->attesa.wait(lk);
                cout << "Thread"<< numero << " si alza" << endl;
                stanza->libera();
            }

            barbiere->lock();
            cout << "Thread"<< numero << " si siete e si fa rasare" << endl;
            stanza->poltrona.wait(*barbiere);
            barbiere->unlock();
            cout << "Thread"<< numero << " esce" << endl;

        }

    }
    void operator()()
    {
        for(int a=0; a<2; a++)
        {
            work();
            cout << "Thread"<< numero << " va in giro a bighellonare" << endl;
            dormi(30,30);
        }
        cout << "Thread"<< numero << " muore" << endl;
    }
};

int main(int argc, char** argv)
{
    Stanza stanza(5);
    int a;

    std::thread* threads[15];

    std::thread* barbiere=new std::thread(Barbiere(&stanza));
    for(a=0; a<15; a++)   //creo
    {
        dormi(0,a);
        threads[a]= new std::thread(Cliente(&stanza,a+1));
    }
    for(a=0; a<15; a++)   //aspetto termine
    {
        threads[a]->join();
        delete(threads[a]);
    }
};

Il problema è risolto nel modo seguente:

Il barbiere:

1. Controlla se ci sono clienti in attesa (attraverso i metodi del Monitor)
2. se non ce ne sono si addormenta ( svegliandosi al punto 3)
3. se ce ne sono li rade e torna al punto 1

la rasatura consiste in:

• liberare un Cliente dalla coda della sala di attesa (attesa.notify_one) , il cliente liberato occupa la coda della poltrona
• radere il Cliente, liberarlo dalla coda della poltrona (poltrona.notify_one())

Il Cliente

1. Entra nella sala, cerca di sedersi
   1. Se può sedersi:
      1. Se è l’unica persona seduta sveglia il barbiere (letto.notify_one())
      2. va al punto 2
   2. Se non può sedersi esce dalla sala e va al punto 5
2. Si mette in attesa nella coda della sala (attesa.wait(lk))
3. una volta svegliato occupa il barbiere (barbiere->lock()) e si mette in attesa sulla sedia della poltrona (poltrona.wait(*barbiere)).
   il mutex sul barbiere evita il problema di una possibile signal non voluta ( vedi sopra il paragrafo “ma le cose non sono così semplici”)
4. una volta svegliato libera il barbiere ed esce dalla sala
5. va in giro a bighellonare e poi torna al punto 1

In questa implementazione sono possibili delle signal superflue su un barbiere già sveglio, ma sono irrilevanti

Con questo articolo ho concluso la serie sulla programmazione concorrente in Cpp0X Leggi tutto »