June 28, 2008 – 3:16 am
Les llistes són una de les estructures de dades mes utilitzades i útils que existeixen. Hi ha múltiples formes d'implementar-les segons el llenguatge i paradigma on estiguem. A Python les podem trobar implementades de forma nativa, a c++ podem utilitzar els contenidors de la std i en C no tenim més remei que fer-nos la nostra pròpia implementació.
Les llistes ens permeten entre altres coses agrupar en una mateixa estructura de dades tot un conjunt d'objectes que no estan en posicions contínues de memòria. Mitjançant aquesta agrupació la llista ens permet entre d'altres coses iterar per a tots els seus membres sense preocupar-nos d'on és el següent element.
EL Kernel del linux utilitza multitud de llistes per a diferents propòsits, és el cas de la llista de de totes les estructures del tipus task_struct que representen els processos de la màquina.
Aquestes estructures cal preparar-les per entorn multithreadins, on molts threads poden competir per accedir a una llista. Per tal de millorar el trhoughtput s'han de construir mecanismes que permetin augmentar el rendiment i la concurrència d'accés de varis threads a la mateixa estructura de dades, en el cas que ens ocupa les llistes.
Una de les metodologies més utilitzades per aconseguir millorar la concurrència és l'anomenat disseny múltiples lectors i un sol escriptor, que també diré rw lock. Mitjançant aquesta aproximació el programari intenta millorar el rendiment d'accés a les llistes sense posar en perill la validesa de les dades. Aquest mecanisme permet que qualsevol thread lector que accedeixi a l'estructura ho realitzi de forma concurrent i amb qualsevol altre thread que també sigui lector, però només un i només un d'escriptor pugui entrar a accedir a la llista al mateix temps.
Aquest model es àmpliament utilitzat, i podríem dir que es una de les primeres mesures de millora d'eficiència que podem prendre sobre l'accés a aquesta estructura de dades.
Per tal de veure com poden canviar els rendiments d'accés a una llista amb aquesta metodologia o sense, he fet una petita implementació del mític rw lock i he intentat comparar com d'eficient és.
A la gràfica següent trobem a l'eix de les x el nombre de threads concurrents, i l'eix de les y el temps mig d'accés en milisegons que tarda de mitja un thread a travessar tota la llista.
Com podem veure hi ha 4 execucions diferents, una sense el rw lock implementat i de color vermell, i tres línies més de colors verda, blava i lila que si tenen implementat el rw lock. A les línies on hi ha implementada la mesura rw lock s'han diferenciat les proporcions de lectors i escriptors, la idea es veure com una proporció més elevada de lectors millora substancialment el temps mig global d'accés.
La llista que s'ha utilitzat és de mig milió d'elemets i la iteració ha consistit ha iterar sense accedir a cap dels seus elements.
Com podem observar no existeix una gran diferència entre la línia verda i la línia vermella. Això és degut a la proporció de threads escriptors de l'execució amb el rw lock activat. En aquest cas hi ha una proporció 1:1 entre lectors i escriptors, això provoca que el rendiment entre sistemes sigui quasi idèntic. Contràriament si que observem en els altres casos com el guany és significatiu i augmenta a mesura que augmentem el nombre de threads lectors.
Part del codi que implementa el rw lock utilitzat és el següent :
static void thread_write(void * p)
{
int id = (int) p;
struct list_head * e;
int count = 0;
struct timespec now, elapsed;
clock_gettime(CLOCK_REALTIME, &now);
pthread_mutex_lock(&myrwlock.access);
pthread_mutex_lock(&myrwlock.sync);
if ( myrwlock.n_readers > 0 )
{
myrwlock.w_wait = 1;
pthread_cond_wait(&myrwlock.signal, &myrwlock.sync);
}
FOREACHLIST(&mylist, e, count);
myrwlock.w_wait = 0;
pthread_mutex_unlock(&myrwlock.sync);
pthread_mutex_unlock(&myrwlock.access);
clock_gettime(CLOCK_REALTIME, &elapsed);
printf("w:%d:%d:%d.%d\n", id, count, elapsed.tv_sec - now.tv_sec, elapsed.tv_nsec - now.tv_nsec);
}
static void thread_read(void * p)
{
int id = (int) p;
struct list_head * e;
int count = 0;
struct timespec now, elapsed;
clock_gettime(CLOCK_REALTIME, &now);
pthread_mutex_lock(&myrwlock.access);
pthread_mutex_lock(&myrwlock.sync);
myrwlock.n_readers++;
pthread_mutex_unlock(&myrwlock.sync);
pthread_mutex_unlock(&myrwlock.access);
FOREACHLIST(&mylist, e, count);
pthread_mutex_lock(&myrwlock.sync);
if ( ( --myrwlock.n_readers == 0 ) && ( myrwlock.w_wait != 0 ) )
{
pthread_mutex_unlock(&myrwlock.sync);
pthread_cond_signal(&myrwlock.signal);
}
else
pthread_mutex_unlock(&myrwlock.sync);
clock_gettime(CLOCK_REALTIME, &elapsed);
printf("r:%d:%d:%d.%d\n", id, count, elapsed.tv_sec - now.tv_sec, elapsed.tv_nsec - now.tv_nsec);
}
Posted in Programacio | No Comments »
