Programación concurrente libre de cerrojos

Uno de los problemas más importantes a la hora de hablar de programación es la concurrencia entre hilos. Como estudiante de Ingeniería Informática he tenido que realizar varios trabajos en los que me ha tocado buscar soluciones al típico problema del consumidor/productor. Una de las últimas aproximaciones que he realizado ha sido utilizando tipos atómicos o, lo que es lo mismo, soluciones libres de cerrojos. A continuación, muestro mi solución libre de cerrojos para un problema de un único consumidor y un único productor operando sobre un buffer circular. Esta implementación se corresponde con la solución que presenté a la práctica 2 “concurrencia y consistencia de memoria” de la asignatura Arquitectura de Computadores.

Presentación del problema

Nuestro escenario es el de un problema consumidor/productor donde únicamente existe un único hilo productor y un único hilo consumidor. Los datos producidos se tratan con una planificación FIFO y nuestra estructura de datos es un buffer circular de tamaño N. Contamos con una implementación inicial de dicho problema de manera secuencial y en C++ (“insertamos N

datos hasta que se llene el buffer posteriormente leemos los N datos hasta que se vacíe y así repetidamente hasta no tener datos que procesar”). Nuestro objetivo es crear una nueva versión concurrente de dicho buffer la cual sea totalmente libre de cerrojos aprovechando toda la potencia de los tipo de datos atómicos.

¿Que es un tipo de dato atomico?

Un tipo de dato atómico, es aquel que encapsula un tipo de dato básico para garantizarnos que sus operaciones de procesamiento no producen condiciones de carrera. Al ser ejecutadas de esta manera podemos aprovecharlos para garantizar sincronización entre diferentes hilos, que es justo lo que necesitamos para resolver nuestro problema.

¿Cual es la implementación de nuestro buffer circular?

Nuestro buffer cuenta con varias operaciones públicas que deberemos adaptar, además de dos punteros: uno que indica la cabecera del buffer, o lo que es lo mismo, cual sería el siguiente dato leído y otro que indica la cola del buffer, o lo que es lo mismo, donde sería almacenado el siguiente dato. Por lo tanto, la cabecera implementada de nuestro buffer podría ser de la siguiente forma:

class buffer {
public:
  // Constructs a buffer for n elements
  buffer(int n);
// Size of buffer
  int size() const noexcept;
// Put element x into buffer with marker last.
  void put(const T & x);
// Gets a pair wit next element and last indication.
  std::pair<T> get();
private:
  // Compute next position after p following circular order
  int next_position(int p) const noexcept;
// Next position to read
  int next_read_ = 0;
// Next position to write
  int next_write_ = 0;
};
Definido el escenario ya podemos enfrentarnos al problema: queremos que tanto el hilo productor como el hilo consumidor puedan trabajar concurrentemente (al mismo tiempo) sobre el buffer, de manera que sólo tenga que esperar alguno de los dos en caso de que el buffer esté lleno ("y por tanto no se podría insertar ningún dato") o el buffer esté vacío ("y por tanto no podríamos leer ningún dato").
Diseño de la solución
Una vez que nos hemos asegurado que entendemos el problema, y antes de empezar a diseñar la solución, es importante extraer dos restricciones importantes en las cuales basaremos toda nuestra solución.

• Únicamente el hilo productor puede actualizar (escribir) el valor del puntero “next_write” porque es el único que escribe sobre el buffer circular. Mientras tanto tan solo podrá leer el valor del puntero “next_read” para verificar que el buffer no esté lleno antes de escribir.
• Por consiguiente, únicamente el hilo consumidor puede actualizar el valor del puntero “next_read” a medida que va extrayendo datos del buffer, mientras que tan solo podrá leer el valor del puntero “next_write” para verificar que el buffer no esté vacío antes de intentar extraer un dato.

En base a estas premisas podemos diseñar una solución que asegure que el orden de lectura/escritura sobre ambos punteros es el correcto y, por tanto, cumplimos las dependencias de información para ambos hilos: el productor debe leer siempre el ultimo valor escrito por el consumidor en el puntero "next_read" y, a su vez, el consumidor lo mismo pero para el puntero "next_write".
Funcionamiento con tipos atómicos
Como ya se puede intuir, nos interesa mantener la consistencia de lecturas/escrituras en las variables "next_read" y "next_write". Por lo tanto, esas son las que se declararan como tipos atómicos. Pero antes de trabajar con ellas debemos tener en cuenta algunas cosas que nos serán de utilidad al tratarse de variables atómicas.
Consistencia de memoria en tipos atómicos
La potencia de los tipos atómicos reside en que podemos especificar diferentes modelos de memoria o, lo que es lo mismo, el orden de las operaciones de escritura/lectura que realicemos sobre nuestras variables y su visibilidad para los demás hilos en ejecución.
En nuestra version de C++ utilizada (v.11) existen tres tipos de modelos diferentes y cada uno de ellos cuenta con diferentes opciones de ordenación:

• Modelo de consistencia secuencial
• memory_order_seq_cst — Todas las operaciones están sincronizadas con todos los hilos. Todos los hilos observan el mismo orden en las operaciones gracias a que la sincronización global esta garantizada.
• Modelo de consistencia adquisición/liberación
• memory_order_acquire — Una operación de lectura con este orden asegura que ningún acceso a memoria en el hilo actual es reordenado ANTES de dicha operación (“si esto pasara podríamos leer un valor que no es el correcto”). Además, nos asegura que TODAS las escrituras realizadas en otros hilos sobre esta variable con orden de liberación (memory_order_release) son visibles ante nosotros (“de esta manera leemos siempre el último valor escrito -liberado-”).
• memory_order_release — Una operación de escritura con este orden asegura que ninguna operación sobre dicha variable en el hilo actual es reordenada DESPUÉS de dicha operación (“podríamos sobreescribir y perder el valor escrito”). Además, asegura que la escritura sobre esta variable es visible en TODOS los demás hilos que hayan realizado una lectura de adquisición (memory_order_acquire) sobre la misma. (“los hilos interesados, obtendrían el ultimo valor escrito-liberado-”)
• memory_order_acq_rel — Se trata del conjunto de los dos órdenes mencionados anteriormente.
• Modelo de consistencia relajada
• memory_order_relaxed — No ofrece ningún tipo de sincronización de las operaciones, tan sólo asegura la atomicidad.

Lectura y escritura sobre tipos atómicos

Para realizar una escritura sobre una variable atómica se utiliza el método store(...). De esta forma nos aseguramos que la variable toma el valor que le pasamos por parámetro ("T desired") y dicha operación es visible en otros hilos en el orden que nosotros hemos especificado ("std::memory_order order").
void store( T desired, std::memory_order order = std::memory_order_seq_cst );
Por su parte, una lectura se realiza con el método load(...) que únicamente recibe como parámetro el orden en que queremos que dicha operación sea visible en los demás hilos para mantener la consistencia de memoria.
T load( std::memory_order order = std::memory_order_seq_cst ) const;

Implementación de la solución

En base a las restricciones que hemos identificado en el diseño de la solución ("que hilo debe actualizar que variable y cual tan sólo debe leerla") y con la ayuda de los órdenes de memoria que nos proporciona C++ podemos realizar una primera implementación de la solución.
Insertar un dato
La función encargada de esta responsabilidad es: void put(const T &x);
void put(const T & x) noexcept{
  //#1 - Obtenemos la posición actual de escritura. 
  auto current_write = next_write_.load(std::memory_order_relaxed);
  //#2 - Calculamos la siguiente posición de escritura
  auto next_write = next_position(current_write);
  //#3 - Realizamos espera activa si el buffer esta lleno y por tanto no podemos escribir
  while(next_write == next_read_.load(std::memory_order_acquire));
  //#4 - Escribimos
  buf_[current_write] = x;
  //#5 - Actualizamos la variable de siguiente escritura
  next_write_.store(next_write,std::memory_order_release);
}

• #1 — Obtenemos la posición actual de escritura que guarda el puntero next_write y la obtenemos con un orden de consistencia de memoria relajado, porque TAN SÓLO NOSOTROS (el hilo productor, el único que llama a esta función) escribimos sobre esta variable y, por tanto, no es necesario mantener consistencia para nosotros mismos (siempre leeremos el ultimo valor porque es el que fue escrito por nosotros).
• #3 — El buffer esta lleno si la posición siguiente al último valor escrito coincide con el de siguiente lectura (si se da ese caso y escribimos, perderíamos el valor a leer). Justamente, el puntero de lectura lo actualiza el otro hilo (el hilo consumidor) por lo que debemos realizar una carga de la variable con orden de adquisición para que nos sea visible su ultima modificación de la variable (nos aseguraremos de que cuando él actualice dicha variable, realizara esa operacion de store con un orden de memoria de liberación -memory_order_release-).
• #5 — Actualizamos el valor del puntero de escritura con la siguiente posición. En este caso, nos interesa que todos los demás hilos que vayan a leer esta variable tengan visible esta escritura, por lo tanto, lo hacemos con orden de liberación (al igual que nosotros para la variable de next_read, el hilo del consumidor estará esperando nuestras liberaciones sobre la variable next_write).

Extraer un dato

La función encargada de esta responsabilidad es: T get();
T get() noexcept{
    //#1 Obtenemos la posición de lectura actual. 
    const auto current_read = next_read_.load(std::memory_order_relaxed);
    //#2 Realizamos espera activa si el buffer esta vacío y por lo tanto no podemos leer. 
    while(current_read == next_write_.load(std::memory_order_acquire));
    //#3 Obtenemos el valor
    auto value = buf_[current_read];      
    //#4 Actualizamos la siguiente posición de lectura 
    next_read_.store(next_position(current_read),std::memory_order_release);
    return value;
}

• #1 — Al igual que antes, el hilo consumidor es el único que actualiza el puntero de escritura, por lo tanto, podemos obtenerla con un orden de memoria relajado.
• #2 — Si el puntero de lectura actual es igual al puntero que indica donde debemos escribir el buffer esta vacío, por lo que esperamos a que esta condición no se cumpla. Observar que como es el otro hilo, el productor, el que modifica el puntero de escritura, debemos leer dicha variable con un orden de adquisición para poder tener visibles sus últimas escrituras (como comentamos anteriormente, él las realiza con un orden de liberación!).
• #4 — Finalmente, actualizamos el valor del puntero de lectura con un orden de liberación con el objetivo de que dicha escritura sea visible por el hilo productor.

Conclusiones

Hemos podido ver lo sencillo que es realizar una implementación concurrente libre de  cerrojos mediante los nuevos tipos atómicos de C++. El hecho de que se puedan especificar órdenes de memoria sobre variables concretas nos permite controlar la sincronización de las operaciones sobre estas variables en ambos hilos y, por lo tanto, asegurarnos de que el orden de las operaciones visibles para ambos es el correcto sin tener que ser el mismo, como ocurre en la versión secuencial.
Cualquier aporte es bienvenido y lo podéis dejar en la sección de comentarios.
Un saludo,
M.