Explicación al reto de concurrencia. Solución con StampedLock

0
1795
La mayoría de programadores encontró un punto ciego con la sentencia «arr[size++]=e;«. De alguna forma pensamos que el tamaño se actualizará después de la asignación. En este artículo veremos este bug básico de concurrencia y presentamos una solución con StampedLock de Java 8.

[box style=»1″]

Éste artículo es una traducción al castellano de la entrada original publicada, en inglés, por Dr. Heinz Kabutz en su número 242 de The Javatm Specialists’ Newsletter. Puedes consultar el texto original en Javaspecialists’ Newsletter #242: Concurrency Puzzle Explained, Solved With StampedLock

Este artículo se publica traducido en adictos, con permiso del autor, por David Gómez García, (@dgomezg) consultor tecnológico en Autentia, colaborador de JavaSpecialists e instructor certificado para impartir los cursos de JavaSpecialists en español.
[/box]


Bienvenidos a la edición número 242 de The Javatm Specialists’ Newsletter, enviado desde una lluviosa Creta. Siempre nos sorprendemos con las primeras lluvias de verdad de la temporada. ¿Cómo se atreve el agua a caer desde el cielo? ¿y qué es eso gris de ahí arriba?. Nuestros olivos necesitan un sorbo de agua para engordar sus frutos para la cosecha. Lamentablemente, gracias a los fuertes vientos, buena parte de nuestra cosecha está convirtiendose en compost. Bueno, quizá el próximo año podamos llenar nuestras cubas de nuevo. Hasta entonces, ¡racionaremos los suministros!Me alegra poder dar la bienvenida a Burkina Faso a la lista de paises suscriptores confirmados, dejando el contador en 138 paises.

El canal de Slack de Java Specialists (en inglés) está que se sale. Casi 2.000 miembros ya, intercambiando grandes ideas, aprendiendo cosas nuevas. Tenemos miembros en 22 husos horarios. Lo que significa que puedes encontrar a alguien para hablar de Java en tiempo real a cualquier hora del día o de la noche. Para unirte, rellena este formulario con tus datos y automágicamente recibirás una invitación de Slack (pero por favor, comprueba tu carpeta de SPAM).

NOVEDAD Hemos actualizado nuestro curso de «Advanced Topics» que cubre Reflection, Java NIO, Estructuras de datos, Gestión de memoria y algunos otros temas útiles para dominar si eres un experto en Java. Dos días de diversión y aprendizaje extremos: «Extreme Java – Advanced Topics». Este curso también lo impartimos en castellano.

El problema de concurrencia explicado, solucionado con StampedLock

Nos hemos divertido este último mes. Propuse un reto de concurrencia que ha tenido a expertos en Java de todo el mundo rascándose la cabeza. Tanto es así, que también publiqué algunas pistas útiles.

Lo que más me sorprendió de las respuestas es la cantidad que no se había molestado en ejecutar el código. En vez de ello, lo revisaron y pulsaron en «Responder». Ninguna de estas respuestas capturó el bug que lo hacía fallar de forma consistente. Lo peor es que perdieron una oportunidad fantástica de aprender algo nuevo.

Cuando se buscan errores de concurrencia, el primer paso es tratar de reproducirlo. Esto puede resultar bastante difícil. Por ejemplo, el código que me envió Jack no fallaba en mi MacBook Pro. Lo tuve que ejecutar en mi servidor 2-4-1 con una CPU más antigua para conseguir que el bug se reprodujese. Aquí tenéis una versión con un probabilidad mayor de hacer aparecer el fallo, adaptado para mi amigo Stuart Marks:

El fallo de concurrencia se manifiesta más fácilmente con el código modificado. Lo podemos reproducir de forma consistente. Es casi imposible hacer esto con errores de tipo happens-before. Esos suelen mostrar su fea cara en producción, no en un pequeño test como el nuestro. Los errores de visibilidad suelen aparecer y no se recupera uno de ellos, por ejemplo, si tenemos un bucle cerrado en el que leemos un campo desprotegido. En nuestro caso, el error es mucho más básico.

La segunda pista estaba en que ocurría incluso sin el remove(). Así que podiamos ignorar tranquilamente el método remove() y centrarnos en el método add().

Una tercera pista estaba en que el redimensionado no tenía nada que ver con el error. Incluso si dimensionamos desde el principio el array con un tamaño de 1.000, también podía fallar.

La primera respuesta correcta la dió Andreas Senft. Reconoció que se trataba simplemente de un error de concurrencia común que no tenía nada que ver con cachés, happens-before, visibilidad, etc… Simple y llanamente una condición de carrera en el método add(). Si miramos dentro de add(), veremos la sentencia arr[size++] = e;. La mayoría de programadores leen esto como «Asigna e en el elemento del array y actualiza el tamaño». En sus cabezas, esto es lo que ocurre:

Aunque sería más acertado verlo de la siguiente forma:

Ahora es obvio que size se actualiza primero y después se asigna el elemento en el array. Si, entre la llamada a size = size + 1; y arr[temp] = e; el hilo deja su tiempo de ejecución de CPU, el hilo de lectura podría tratar de leer un elemento que no existe todavía, dado que está bloqueado en un monitor diferente. Si reemplazamos el código por el siguiente, entonces los errores se producirán con menos frecuencia (pero todavía es incorrecto):

Demostrar que es también incorrecto será más complicado. El test que teníamos en el artículo anterior no será suficiente.

El problema con el código estaba en que tenemos distintos locks guardando campos que mantienen una invariante entre ellos. La motivación detrás de esto era tratar de evitar que los bloqueos de escritura bloqueen los hilos que sólo quieren leer. Pensé que éste sería un buen caso de uso para el StampedLock de Java 8. Si todo esto te resulta nuevo, ¿puedo sugerirte apuntarte a mi curso Extreme Java – Concurrency and performance for Java 8? (que también impartimos en español). ¡Aprenderás en tres días más de lo que crees que es posible!

IntList con StampedLock

StampedLock se añadió con Java 8 para darnos la posibilidad de realizar lecturas optimistas sobre campos. Esto es útil cuando tenemos varios campos con una invariante entre todos ellos. En nuestro ejemplo, esos son los campos arr y size.

IntList es el resultado de un trabajo en colaboración entre Peter Levart, Henri Tremblay, Hanko Gergely, Alex Snaps y yo mismo. Cada uno de nosotros ha ayudado a refinar un poquito la solución final. Es un trabajo en curso así que, por favor, decidme si encontráis una forma de mejorarlo todavía más. Casi seguro que tiene jugosos bugs aún por descubrir.

Para empezar tenemos size(). Dado que lo que nos preocupa es la visibilidad del campo size, lo único que necesitamos es llamar al método tryOptimisticRead(). Éste método realiza una lectura volatile sobre el campo dentro de un StampedLock, que tiene el mismo efecto que entrar en un bloque synchronized, y por tanto garantiza que veremos el valor correcto del campo size.

El método get() es el más complejo. Intentamos leer el elemento del array en una variable local entre las llamadas a tryOptimisticRead() y validate(), asegurándonos que no causamos un ArrayIndexOutOfBoundsException en el proceso. Si somos lo suficientemente rápidos, podemos hacerlo antes de que otro hilo obtenga el lock de escritura. Verás que intentamos la lectura optimista tres veces y, si no lo conseguimos, cambiamos a usar un lock de lectura pesimista. Este cambio puede ser bueno, pero también puede penalizarnos si lo hacemos demasiado.

La función trimToSize() se supone que nos muestra como podemos utilizar tryOptimisticRead() para evitar obtener un lock de escritura si no lo necesitamos.

El método add() es sencillo, casi como utilizar un ReentrantLock.

Tenemos dos funciones de borrado. El método remove() simple es análogo a add(), utilizando un lock pesimista para la lectura exclusiva. El método removeWithUpgrade() obtiene un lock de lectura y, si el índice no está fuera de rango, intentamos convertirlo en un lock de escritura. Un ReentrantReadWriteLock produciría un deadlock, pero con StampedLock lo conseguiremos. Este lock condicional de escritura es útil cuando tenemos una alta probabilidad de no necesitar el lock de escritura. De todas formas, en nuestro caso esperamos que la mayor parte de las veces el índice estará dentro del rango. Por eso, el método remove() sería probablemente una solución mejor. Más rápido y más fácil de comprender y de mantener.

Vamos al código. Divertíos. Discutiremos esto en el canal #newsletter del grupo JavaSpecialists.slack.com. Por favor, rellena tus datos aquí para unirte (sin cuotas, sin obligaciones, excepto «ser agradables»).

He ejecutado algunas pruebas de rendimiento comparando éste con una versión correctamente sincronizada del MyArrayList que usamos en el número anterior. El método get() es basicamente el doble de rápido y usa bastante menos CPU de sistema gracias a la reducción del número de cambios de contexto voluntarios. Los métodos add() y remove() son ligeramente más lentos, pero como esperaba, size() es ridículamente rápido. He añadido éste como un ejercicio a mi curso de concurrencia. Veamos cómo de bien se las apañan programadores Java buenos y experimentados cuando vean StampedLock por primera vez 🙂

Saludos

Heinz.

Dejar respuesta

Please enter your comment!
Please enter your name here