17 Jun 2015

Transactional Mutex Locks (TML)

TML es un STM muy ligero que introduce muy poca instrumentación, aunque a costa de obtener un rendimiento limitado en escenarios con alto porcentaje de escrituras.

Los metadatos necesarios para implementar TML se limitan a un lock global (gOrec) y un lock local por transacción (lOrec). El funcionamiento básico de TML es el siguiente:

  1. gOrec se inicializa a 0 al inicio del STM.
  2. lOrec se inicializa al valor de gOrec, siempre que sea par, lo que indica que no hay ninguna transacción activa que haya realizado una escritura.
  3. A la hora de leer un dato transaccionalmente, se guarda el dato en una variable compartida y se comprueba que ninguna otra transacción activa haya realizado alguna escritura. Como sólo hay un orec, no se mira si la dirección es o no correcta; si gOrec no es igual al lOrec de la transacción se aborta directamente. En caso contrario se devuelve el dato.
  4. A la hora de escribir un dato transaccionalmente, se comprueba si la transacción ha realizado alguna escritura (writer) o sólo ha hecho lecturas (reader), mirando si lOrec es impar. En el caso de que sea par (reader), se intenta promocionar la transacción a writer, para lo cual se realiza un CAS(gOrec, lOrec, lOrec+1). Es decir: se verifica que ninguna otra transacción que haya escrito y finalizado desde que se inició la transacción actual, en cuyo caso se incrementa gOrec, impidiendo que cualquier otra transacción activa pueda realizar una escritura (ya que gOrec es ahora impar), se realiza la escritura directamente en memoria compartida (eager) y se incrementa lOrec promocionando la transacción a writer. Cualquier escritura posterior no tiene que pasar por este proceso de nuevo, ya que al detectar que la transacción es writer (lOrec es impar), puede pasar directamente a escribir el dato. El resto de las tranascciones (reader) que quieran escribir abortarán al no poder completar el CAS, y abortarán igualmente al leer ya que tampoco cumplirán la condición lOrec == gOrec.
  5. La fase de commit es igualmente muy rápida, ya que las transacciones reader simplemente retornan, y las writer incrementan gOrec, que era impar, y lo convierten de nuevo en par, permitiendo que una nueva transacción pueda promocionar a writer.

De este modo, TML consigue ser un STM con muy baja instrumentación a costa de limitar su rendimiento en caso de escrituras. Sólo puede existir una transacción writer activa en TML, y cualquier lectura o escritura posterior por parte de una transacción reader ocasiona un aborto de la misma. La transacción writer se convierte de este modo en irrevocable, ya que una vez promocionada no aborta hasta su finalización.

En el artículo que presenta TML: Transactional Mutex Locks, se proponen varias optimizaciones a este algoritmo:

  • TML: Algoritmo básico. Usa thread-local-storage para almacenar los metadatos, y setjmp/longjmp para el rollback.
  • TML-tls: Usa directamente el heap para almacenar los metadatos, evitando pérdidas de rendimiento si el sistema operativo no soporta thread-local-storage de forma eficiente.
  • TML-jmp: Reemplaza el uso de setjmp/longjmp por un sistema de checkpoints y un jump incondicional.
  • TML-pwi: Dado que una vez que una transacción promociona a writer no puede ser abortada, evita cualquier instrumentación de un writer.
  • TML-rcc: Reduce la instrumentación en las lecturas en los casos en los que se realizan varias lecturas seguidas antes de operar con ellas de alguna manera. Para ello se elimina la instrumentación de todas las lecturas excepto la última (lo que puede llevar a problemas de opacity si no se elige bien dónde aplicar esta optimización).
  • TML-aou: Añade cierto soporte hardware (alert-on-update), que permite eliminar la instrumentación de las lecturas.

TML, aunque limitado, ha demostrado un buen rendimiento cuando hay muy pocas operaciones de escritura en el sistema transaccional.