multithreading atomic stm

multithreading - ¿Cómo implementar software de memoria transaccional?



atomic stm (5)

Algunos artículos pueden ser realmente difíciles de leer, pero dos que son muy claros y concisos son:

Bloqueo transaccional II, Dave Dice, Ori Shalev, Nir Shavit, que describe el algoritmo STM "TL2" en términos de cualquier idioma.

Deuce: Memoria transaccional de software no invasivo en Java, Guy Korland, Nir Shavit, Pascal Felber, que explica un transformador de clase de tiempo de carga que transforma clases regulares de java en clases en memoria que tienen un código de byte adicional para hacer STM. Esto es relevante para la pregunta, ya que el documento explica cómo el código sin STM se puede transformar mecánicamente en código que hace STM en cualquier idioma OO.

El marco Deuce le permite conectar el algoritmo real que desea utilizar; incluyendo el algoritmo TL2. Como el marco de trabajo de Deuce es Java, la siguiente discusión utiliza la terminología de Java, pero solo asume que estás escribiendo en un lenguaje OO.

A continuación se esbozará el enfoque TL2. Los artículos tienen enlaces a enfoques alternativos, pero el estudio de un algoritmo responde muchas preguntas.

¿Cómo implementas STM? La parte que me resulta misteriosa es que, dado un fragmento de código arbitrario, necesita una forma de volver después y determinar si los valores utilizados en cada paso eran válidos.

Una breve respuesta de cómo TL2 hace STM es la "contabilidad" y luego solo se utilizan los bloqueos de escritura en el momento de la confirmación. Lea el papel para los detalles finos, pero el contorno de un pincel de cartón es el siguiente. Todas las propiedades que puede usar en el código original tendrían un getter y setter. En el código transformado también habría un número de versión de la propiedad y un código adicional agregado al captador y configurador. Debe registrar la versión de cada atributo que lea dentro de la transacción como el "conjunto de lectura" de la transacción. Puede hacer esto haciendo que cada captador agregue la versión del atributo que se ve en una lista enlazada de threads local. También es necesario almacenar en búfer las escrituras como el "conjunto de escritura" en un threadlocal hasta que se confirme. Tenga en cuenta que los métodos de obtención deben verificar y devolver un valor de conjunto de escritura de subproceso local para un campo determinado, si tiene uno. De esa manera, verá sus escrituras no confirmadas en sus lecturas, pero ningún otro hilo las verá hasta que las confirme.

En el momento de la confirmación, toma bloqueos de escritura contra cada atributo que está a punto de escribir. Mientras tenga los bloqueos, compruebe que su conjunto de lectura todavía sea válido; que los atributos que leyó en su transacción no se han actualizado a una versión superior por otra transacción. Si es así, es posible que su lógica de negocios no sea válida, ya que puede tener lecturas incoherentes, por lo que debe revertir toda la transacción. Si se aprueban las comprobaciones finales, se comprometen al vaciar su conjunto de escritura, eliminar las versiones de esos atributos, liberar los bloqueos de escritura y borrar finalmente las listas de subprocesos de lectura de conjunto de escritura y lectura.

El documento explica que el algoritmo puede abortar temprano si detecta que se ha escrito un atributo que se está leyendo desde que comenzó el tx. El documento tiene algunos trucos para acelerar las transacciones de solo lectura. Incluso tiene un truco para descubrir qué bloques son de solo lectura y cuáles de lectura y escritura. Cualquiera que exprese interés en tales cosas debería disfrutar de los dos documentos.

El marco de trabajo de Deuce en el documento anterior muestra cómo cambiar a todos tus captadores y definidores al inyectar un nuevo código de bytes de Java en tus clases durante el tiempo de carga. Otros idiomas podrían tener un compilador o preprocesador especial que realice la misma transformación mecánica del código normal en código habilitado para STM. Específicamente con Deuce, sus objetos de código fuente pueden tener pares de establecedores getter simples, pero las clases transformadas en tiempo de ejecución han enriquecido a los setters que hacen el trabajo de libros.

Transformar el código regular en código STM (especialmente en tiempo de ejecución) es interesante, pero si necesita escribir una estructura de datos habilitada para STM, no necesita ninguna salsa mágica. En su lugar, simplemente cree una clase de Ref con un get() y un set(x) y cree que cada relación entre sus objetos de estructura de datos se compone de Ref de Ref . En la get y set de su clase de Ref puede hacer el trabajo de subprocesos de subprocesos. Luego, puede implementar una versión simple de "TL2" o cualquier otro algoritmo que funcione bien para sus estructuras de datos y su concurrencia de lectura frente a escritura.

Esto también parece sugerir que, al igual que con cualquier otra solución de "bloqueo", desea mantener sus secciones críticas lo más pequeñas posible (para disminuir la probabilidad de un conflicto), ¿tengo razón?

TL2 tiene un período crítico para mantener los bloqueos de escritura y luego hacer las comprobaciones finales y las escrituras, que es fácil de comprender y optimizar sin ningún entendimiento de la lógica empresarial de la aplicación. Si asigna a cada número una propiedad única, puede evitar de manera trivial el interbloqueo tomando bloqueos en orden ascendente. Es importante tener en cuenta que toda la lógica de su negocio se realiza de forma especulativa, asumiendo que las comprobaciones de confirmación se aprobarán. No mantiene bloqueos mientras está haciendo una lógica de negocios lenta y arbitraria. Puede realizar varias búsquedas de servicios web o llamadas de base de datos lentas y no realizará ningún bloqueo hasta que se confirme. Claramente, los profesionales se van a afinar en la sección crítica genérica.

El documento deja claro que el algoritmo puede abortar más a menudo que la lógica de negocios específica lo requiere. El algoritmo genérico no sabe si las lecturas sucias específicas no afectarán el resultado de escritura real. La lógica manuscrita que entiende la lógica de negocios real podría conocer casos especiales cuando no se necesita una reversión para un conjunto dado de lecturas sucias. Sin embargo, si tiene mucho código para escribir y una aplicación donde la probabilidad de retroceso es muy baja, un enfoque genérico de STM puede generar menos errores y un buen rendimiento.

Además, ¿puede STM simplemente detectar "otro subproceso ingresado en esta área mientras se estaba ejecutando el cálculo, por lo tanto el cómputo no es válido" o puede detectar realmente si se usaron valores precocidos (y por suerte a veces dos subprocesos pueden ejecutar la misma sección crítica simultáneamente sin necesidad de retroceso)?

El enfoque de TL2 se basa en los datos leídos o escritos, no en el código que lo hace. Es lo que se obtiene y se establece y lo que cuenta; y si algún otro hilo pisó sus dedos de los pies antes de vaciar todas las escrituras. Todo lo que se requiere del código es que tenga un begin() , commit() y rollback() en la lógica de negocios para iniciar, finalizar y abortar la transacción. Incluso ese código puede ser generado. Con Java, puede marcar sus métodos con la anotación @Transactional en los métodos y luego generar el código que envuelve sus invocaciones de método en un try / catch / finalmente que hace que comience / commit / rollback como java idiómico. Deuce inyecta dicha lógica en el tiempo de carga de clase.

Una vez más, no necesita dicha salsa mágica para comenzar / confirmar / revertir en sus propias estructuras de datos habilitadas por STM. Puede ser explícito y poner todo ese derecho en el código lógico de su estructura de datos para crear sus propias clases habilitadas STM explícitamente en cualquier idioma OO.

En términos de instrucciones atómicas reales de bajo nivel y cercas de memoria (supongo que se utilizan), ¿cómo implementa STM?

La parte que me resulta misteriosa es que, dado un fragmento de código arbitrario, necesita una forma de volver después y determinar si los valores utilizados en cada paso eran válidos. ¿Cómo haces eso y cómo lo haces eficientemente? Esto también parece sugerir que, al igual que con cualquier otra solución de "bloqueo", desea mantener sus secciones críticas lo más pequeñas posible (para disminuir la probabilidad de un conflicto), ¿tengo razón?

Además, ¿puede STM simplemente detectar "otro subproceso ingresado en esta área mientras se estaba ejecutando el cálculo, por lo tanto el cómputo no es válido" o puede detectar realmente si se usaron valores precocidos (y por suerte a veces dos subprocesos pueden ejecutar la misma sección crítica simultáneamente sin necesidad de retroceso)?

La implementación de STM de GHC se describe en la sección seis de:

Transacciones de memoria composable . Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPoPP''05: Simposio ACM SIGPLAN sobre Principios y Práctica de la Programación Paralela, Chicago, Illinois, junio de 2005

Y la sección cinco de:

Memoria transaccional con invariantes de datos . Tim Harris, Simon Peyton-Jones. Marzo 2006 TRANSACT ''06

La respuesta más simple es "depende". Hay toneladas de implementaciones radicalmente diferentes que funcionan de forma prácticamente imaginable.

La parte que me resulta misteriosa es que, dado un fragmento de código arbitrario, necesita una forma de volver después y determinar si los valores utilizados en cada paso eran válidos. ¿Cómo haces eso y cómo lo haces eficientemente?

Una solución es utilizar el control de versiones. Cada vez que se modifica un objeto, se actualiza su número de versión. Mientras la transacción se está ejecutando, usted valida la versión de cada objeto accedido, y cuando la transacción se confirma, verifica que los objetos aún son válidos. Esta validación puede ser una simple comparación de enteros (si transaction_start_version >= object_version , el objeto es válido), por lo que puede hacerse de manera bastante eficiente.

Esto también parece sugerir que, al igual que con cualquier otra solución de "bloqueo", desea mantener sus secciones críticas lo más pequeñas posible (para disminuir la probabilidad de un conflicto), ¿tengo razón?

Muy probable. Creo que algunas implementaciones han tomado la ruta de asumir / exigir que todo sea ​​una transacción, pero sí, en la mayoría de las implementaciones, las transacciones son fragmentos de código especialmente marcados, y mientras más larga sea la transacción, mayor será la posibilidad de que surja un conflicto. hacer que las transacciones se deshagan.

Además, ¿puede STM simplemente detectar "otro subproceso ingresado en esta área mientras se estaba ejecutando el cálculo, por lo tanto el cómputo no es válido" o puede detectar realmente si se usaron valores precocidos (y por suerte a veces dos subprocesos pueden ejecutar la misma sección crítica simultáneamente sin necesidad de retroceso)?

El último. Tenga en cuenta que la idea en TM es proteger los datos , en lugar de codificarlos .

Diferentes rutas de código pueden acceder a la misma variable en diferentes transacciones. Esto tiene que ser detectado por el sistema TM. No hay una noción real de "esta área", ya que se refiere al código, en lugar de a los datos. Al sistema TM no le importa qué código se está ejecutando, rastrea qué datos se están modificando. De esa manera, difiere completamente de las secciones críticas (que protegen el código, en lugar de los datos)

Le sugiero que vea esta presentación: http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

En la segunda mitad, explica cómo actualizar los valores sin dejarlos en un estado indefinido. Por ejemplo, si tiene un árbol que desea actualizar en estilo STM, no cambia la versión anterior. Digamos que el tree es un puntero a la raíz del árbol. Lo único que creas son los nodos que cambiaron (pero pueden referirse a los nodos en la instantánea original del árbol).

Luego haces una comparación e intercambio en el puntero del tree . Si tuvo éxito, entonces todos verán su nuevo árbol y el viejo puede ser recogido en la basura. Si no lo ha hecho, entonces repite el proceso y el árbol que acaba de construir es basura recolectada.

La gran idea es que no necesita detectar si alguien más cambió el tree hasta que realmente intercambie los valores nuevos y antiguos, por lo que no hay "conflictos" o "valores obstruidos" de la programación multiproceso típica.