17 Jun 2015

SeqLocks

Los seqlocks son una de las formas de sincronización más rápidas si hay muchos procesos que leen los datos compartidos durante la sección crítica y pocos que los escriben. Básicamente consisten en un lock y un contador que se encuentran idealmente en la misma línea de caché. El proceso que va a actualizar el dato durante la sección crítica (writer) incrementa atómicamente el contador antes de entrar y vuelve a incrementarlo al salir, de modo que el contador será un número impar (suponemos que está inicializado a cero) durante una sección crítica que implique actualización y par cuando esté fuera de la sección crítica.

Los procesos que sólo requieran acceso de lectura a las variables (readers) leen y almacenan el valor del contador antes y después de leer, reiniciando la sección crítica si los valores son diferentes (lo que indica que ha habido al menos un writer que ha actualizado el dato) o impares (lo que indica que hay una sección crítica en curso que puede modificar el dato).

La ventaja de este sistema es que, si los writers no son frecuentes, el rendimiento es bueno y escala bien, ya que los readers no invalidan líneas de caché, mientras que el writer sólo invalida el dato y una línea extra que idealmente debería contener tanto el lock como el contador.

La desventaja es que los readers no pueden hacer demasiado durante la sección crítica, ya que cualquier actualización irreversible (punteros, operaciones con memoria, escrituras...) impediría el poder reiniciar la sección ante un conflicto con un writer.

Un ejemplo de uso de los seqlocks es la implementación del STM NoRec, que se puede encontrar en el artículo NOrec: Streamlining STM by abolishing ownership records