15 Jan 2014

Implementando Reducciones en TinySTM (I) - Transacciones ordenadas

El primer cambio necesario para la implementación de reducciones es implementar un orden total en TinySTM. En los STM normales, las transacciones no son ordenadas, esto es: cuando una transacción en ejecución llega al final sin conflictos, realiza su commit y termina. Las transacciones son independientes unas de otras, por lo que si el programador quiere establecer un orden entre las mismas, tendrá que hacerlo explícitamente en su código mediante directivas de sincronización.

Al implementar un orden total en TinySTM, conseguiremos que una transacción sólo pueda terminar cuando le toca. Cada transacción tendrá asociada un número que establece su orden. Un reloj global discreto mantiene el orden en todo momento, de modo que en un momento dado sólo puede terminar la transacción cuyo orden coincide con el orden del reloj global (desde ahora GC) en ese instante.

Cuando la transacción tiene el orden podrá realizar su commit y, si no ha habido conflictos o éstos se pueden resolver, terminará. Una vez terminada la transacción n, el GC se incrementará hasta n+1, con lo que la transacción n+1 tendrá ahora la posibilidad de terminar.

En mi implementación del orden global se han asumido las siguientes limitaciones:

• No puede haber más de una transacción con el mismo número de orden.
• Si el número de orden es 0, la transacción se comportará exactamente igual que una transacción clásica, de este modo compatibilizamos el modelo clásico de TinySTM con el nuevo.
• Una transacción con orden n no puede commitar hasta que no hayan terminado las transacciones [0..n-1]. Por tanto no se puede haber "huecos" entre dos número de orden, ya que en ese caso el sistema transaccional se detendría esperando a que termine una transacción que no existe.
• Si se usa orden, todas las transacciones deben ser ordenadas.