teorica prog concurrente

Programacion concurrente (casi avanzada)

Fernando Schapachnik1

1Departamento de Computacion, FCEyN,Universidad de Buenos Aires, Buenos Aires, Argentina

Sistemas Operativos, primer cuatrimestre de 2011

Fernando Schapachnik Programacion concurrente (casi avanzada)

(2) De que se trata?

Vimos hasta ahora primitivas que sirven para programar enentornos concurrentes.

Sin embargo, si se busca eficiencia (y casi siempre se busca),con lo que tenemos es difcil lograrla en la practica.


(3) Motivos

Locking es lento.

Difcil de programar.

En programas real-time bloquearse no esta bueno.

Puede causar inversion de prioridades.

Puede causar convoying.

Representa un problema para la abstraccion composicional.

Ie: no puedo usar modulos alegremente sin saber que hacencon los locks porque podra tener problemas.


(4) Wait-free

Los algoritmos wait-free son aquellos donde el proceso que noaborta tiene garantizado que va a terminar,independientemente de lo que hagan los otros y de a quevelocidad corran.

En general se implementan en base a una primitiva llamadaCompareAndSwap:

Listing 1: Pseudocodigo de CASATOMIC b o o l compare and swap ( i n t dest , i n t v i e j o , i n t nuevo ){

b o o l cambi e= f a l s e ;

i f ( v i e j o==d e s t ){ d e s t= nuevo ;cambi e= t r u e ;}

r e t u r n cambi e ;}


(5) Wait-free (cont.)

En algun momento hubo mucho interes en estos algoritmospero:

+ Todos los algoritmos se pueden transformar en wait-free, atraves de unas transformaciones llamadas universalconstructions (decada del 80).

- La performance tenda a ser bastante mala (peor incluso queimplementaciones con locking ingenuas).

- Para muchas estructuras de datos basicas es necesariamemoria lineal en la cantidad de procesos.

Por ende no se usan mucho en la practica.


(6) Lock-free

Sin embargo, hay una subclase mas realista, que es la de losalgoritmos lock-free.

La diferencia conceptual es que algun proceso se puede trabar,pero el sistema como conjunto progresa.

Se suele llamar lock-free a los algoritmos que no usan mutexes.

Tambien suelen estar basados en CAS. Ejemplo:

i n t v a r ; // V a r i a b l e g l o b a l c o m p a r t i d a .v i e j o= v a r ;nuevo= f ( v a r ) ;wh i l e ( ! c a s (& var , v i e j o , nuevo ) ){

v i e j o= v a r ;// Dependiendo d e l a l g o r i t m o , h a c e r a l g o// con e l cambio de v a r .// Tal vez recomputar nuevo .// Eventua lmente h a c e r s l e e p ( ) .}


(7) Ejemplo

Vamos a ver una pila lock-free:

typede f s t r u c t {nodo pr im ;. . . .} p i l a ;

vo id a p i l a r ( p i l a p , elem e ){

nodo nuevo nodo= nuevo nodo ( e ) ;f i n= f a l s e ;wh i l e ( ! f i n ){

elem prox= p>pr im ;nuevo nodo>prox= prox ;

i f ( c a s (&(p>pr im ) , prox , nuevo nodo ) )// Lo pudo cambiar .f i n= t r u e ;

e l s e// Hay que s e g u i r i n t e n t a n d o . A l g u i e n cambio l a p i l a .

}}


(8) Ejemplo (cont.)

elem d e s a p i l a r ( p i l a p ){

nodo nodo pr im ;f i n= f a l s e ;wh i l e ( ! f i n ){

nodo pr im= p>pr im ;nodo prox= nodo prim>prox ;

i f ( c a s (&(p>pr im ) , nodo prim , prox ) )// Lo pudo cambiar .f i n= t r u e ;

e l s e// Hay que s e g u i r i n t e n t a n d o . A l g u i e n cambio l a p i l a .

}

r e t u r n nodo prim>elem ;}


(9) Problemas con lock-free

Sin embargo, no todo es color de rosa.

Los algoritmos lock-free son difciles de disenar.

Tienen otro problema:


(10) ABA

Pueden sufrir de un problema conocido como ABA.

Supongamos que P1 quiere desapilar, y justo antes de ejecutarel CAS se encuentra con la direccion A como tope de la pila yla direccion B como siguiente.

El scheduler cambia de proceso y se ejecuta P2 que:

Desapila por completo el elemento de la direccion A.Desapila el siguiente que estaba en la direccion B.Apila un nuevo elemento, al que le toca de nuevo la direccionA.Notar: el siguiente debera ser la direccion C .

Le toca de nuevo a P1, ejecuta el CAS.

Como el tope de la pila sigue siendo la direccion A, el CAS secompleta exitosamente, haciendo que se devuelva el elementode A (correcto) pero poniendo como siguiente a la direccion B(incorrecto!, debera ser C ).


(11) Evitando ABA

Un enfoque posible es dedicar algunos bits de los punteros aponer una marca incremental, para hacer que la comparacionno de igual.

El problema es que siendo pocos bits se puede dar la vuelta yvolver al mismo valor.

Para eso a veces se usa un CAS de mas de un word.

Otro enfoque, que fue propuesto por Valois, es usar nodosintermedios en la lista.

Algunas arquitecturas proveen Load-Link/Store-Conditional:

Load-Linked devuelve el valor de un registro.Store-Conditional lo graba si nadie escribio en esa direcciondesde el LL.


(12) Sirve lock-free?

Los resultados son mixtos.

+ Efectivamente son convenientes cuando no hay mutexes uotras primitivas disponibles.

+ Sirven en escenarios optimistas, donde la probabilidad decontencion real es baja.

- Si hay alta contencion, pueden convenir los locks.

? Algunos estudios indican que los resultados parecen dependerde la arquitectura.

? Todava no hay resultados concluyentes que permitancaracterizar a priori los resultados que se pueden obtener paracada tipo de arquitectura.


(13) Programando multicores

Hay algunas consideraciones especiales a la hora de programarmulticores (SMP en general).

Trabajar sobre memoria compartida produce invalidaciones decache.

Por ende, si es posible, conviene que cada procesador use supropia copia y mezclar los resultados al final.

Ademas, cuidado, porque las invalidaciones son de toda unalnea de cache.

En consecuencia, tal vez compartir un pedacito puede llevartener contencion de cache sobre datos privados.

Solucion: padding.


(14) Reorden de instrucciones

Los compiladores y los procesadores pueden reordenarinstrucciones o eliminarlas si creen que con eso incrementan laeficiencia.

Ejemplo: programa multithread. Variable int se usa comolock:

i f ( ! l o c k )l o c k= 1 ;s e c c i o n c r i t i c a ( ) ;l o c k= 0 ;

El compilador puede creer que nadie lee lock y por ende, comooptimizacion, evitar las escrituras.

Otras cosas similares son posibles.


(15) Reorden de instrucciones (cont.)

Al inicio: x = y = r1 = r2 = 0

Thread 1: (1) x= 1; (2) y= 1

Thread 2: (1) r2= y; (2) r1= x

Resultado valido: r1 = 0, r2 = 0 (2.1, 2.2, 1.1, 1.2)




Solucion: usar locks en assembler.


(16) Bibliografa

Avoiding Memory Problems in Multi-Core Programming,Akhter y Jason Roberts.

Intel R 64 Architecture Memory Ordering White PaperConcurrent programming without locks, Fraser y Harris.

Impossibility and Universal Results for Wait-FreeSynchronization, Herlihy.

A practical multi-word compare-and-swap operation, Harris,Fraser, Pratt.

On the inherent weakness of conditional synchronizationprimitives, Fich, Hendler, Shavit.


teorica prog concurrente

Documents