C++ / Diseñando un stack lock-free

Bienvenidos sean a este post, hoy veremos como utilizar tipos atomicos.

Hasta ahora hemos visto el tema de las brechas entre lineas de un codigo. Asi como tambien mediante bloqueos podemos asegurar que solo un thread pueda manejar los datos. Pero una de las claves importantes para todo esto es que debemos tener un stack que nos asegure que el valor empujado esta seguro para volver desde otro thread. En este post, implementamos un stack basados en bloqueos que envuelve un stack. Ahi comentamos que un stack no es una estructura de datos real sino un adaptador. Usualmente, cuando implementamos un stack elegimos entre un vector o un lista enlazada como una estructura de datos subyacente.

Veamos un ejemplo de un stack lock-free basado en una lista enlazada. Para ingresar un nuevo elemento en el stack, se involucra crear un nuevo nodo de la lista, para ello establece al proximo puntero al nodo head actual. Para luego establecer el nodo head para apuntar al nodo insertado recientemente. Esto que describimos es genial para un contexto de un solo thread, sin embargo si tenemos mas de un thread modificando el stack deberiamos comenzar a preocuparnos. Veamos los pasos basicos para ingresar un nuevo valor:

node* new_elem = new node(data);
new_elem->next = head_;
head_ = new_elem;

Primero declaramos al nuevo nodo que sera agregado en la lista enlazada. En el segundo paso, lo que hacemos es apuntar el puntero del siguiente elemento al del inicio. Y en el tercer paso asignamos al elemento inicial el nuevo nodo ingresado.. El tipo nodo es un struct interno que usamos en el stack para representar un nodo de lista. Veamos un ejemplo de definicion:

template <typename T>
class stack_lock_free
{
private:
  struct nodo {
    T datos;
    nodo* next;
    nodo(const T& d) : datos(d) {}
  }

  nodo* head_;
// esto continua con otras instrucciones...
};

Es la tipica clase que se utiliza para representar donde almacenara cual es el elemento inicial y el proximo nodo. Imaginemos que dos threads agregan un nodo al mismo tiempo. Si volvemos a los pasos basicos, cuando establecemos que el puntero del siguiente nodo apunte al elemento de inicio. A su vez, el otro thread hace lo mismo pero con un nuevo elemento, como podemos imaginarnos esto llevara a datos corrompidos. Algo crucial para un thread es que siempre debe tener el mismo head_ para los pasos 2 y 3. Una opcion que podemos usar para evitar la condicion de carrera entre estos dos pasos es implementar la operacion atomica de compare/exchange para garantizarnos que head_ no sea modificado cuando leamos el valor previamente. Vamos a modificar la propiedad head_ para hacerla atomica:

template <typename T>
class stack_lock_free
{
private:
  struct nodo {
    T datos;
    nodo* next;
    nodo(const T& d) : datos(d) {}
  }

  std::atomic<nodo*> head_;
// esto continua con otras instrucciones...
};

Simpllemente aplicamos la especializacion de atomic al nodo. Pasemos a ver como sera la implementacion del metodo push para nuestro puntero atomico head_:

void push(const T& data)
{
  nodo* new_elem = new nodo(data);
  new_elem->next = head_.load();
  while (!head_.compare_exchange_weak(new_elem->next, new_elem));
}

Aqui repetimos los mismos pasos que comentamos al inicio, donde primero generamos al nuevo elemento. Para el proximo nodo, le asignamos el valor de head_ mediante load. El ultimo bucle posee a compare_exchange_weak para asegurarnos que el puntero head_ posea el mismo valor que en el puntero del proximo nodo. Si es asi, procedemos a asignarlo a new_elem y solamente si este es exitoso podemos considerar que se ingreso el nuevo elemento en la lista. Veamos como implementar al metodo pop:

void pop(T& popped_element)
{
  nodo* old_head = head_;
  popped_element = old_head->datos;
  head_ = head_->next;
  delete old_head;
}

Otro codigo de tipo no-atomico donde creamos un objeto del tipo nodo y en este almacenamos el valor de head_, este sera para no perderlo, al elemento que recibimos para quitar le asignamos los datos que estan en el inicio de la lista enlazada. Al head_ le pasamos el objeto correspondiente al proximo nodo para reemplazar al actual y finalmente borramos el objeto que almacenamos. Como con el caso de push, si tenemos dos threads que lo intentan al mismo tiempo podemos caer en corrupcion de datos por una condicion de carrera. Modifiquemos el codigo anterior de la siguiente manera:

void pop(T& popped_element)
{
  nodo* old_head = head_.load();
  while (!head_.compare_exchange_weak(old_head, old_head->next));
  popped_element = old_head->datos;
}

Esto es similar a lo visto con la declaracion de push. Donde primero que haremos sera almacenar el elemento inicial mediante load para que sea de tipo atomico. El ciclo es igual donde si los dos datos son iguales procede a asignarlo y al argumento que recibimos le asignamos los datos del elemento inicial. Si bien no es la mas segura si es bastante practica aunque se puede mejorar. Con esto podemos decir que las implementaciones lock-free necesitan principalmente de tipos y operaciones atomicas.

En resumen, hoy hemos visto un diseño simple de un stack lock-free, como implementar de forma normal, de manera atomica, asi como aplicar ciertas reglas. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.