Una pila sin bloqueo se puede implementar como una lista enlazada individualmente. Esto parece simple hasta que tenemos que pensar en qué hacer con los nodos después de que se hayan reventado. Una estrategia es simplemente moverlos a una lista libre LIFO por pila (desde la cual los nodos se pueden reutilizar mediante operaciones push posteriores) hasta que finalmente todos los subprocesos terminen con la pila, momento en el cual un solo subproceso destruye todos los nodos en la pila y todos nodos en la lista libre. Boost.Lockfree utiliza esta estrategia. También lo hace la implementación C11 de Chris Wellons . Me referiré a este último porque es más fácil de leer y los detalles son esencialmente los mismos, ya que los átomos C11 son muy similares a los átomos C++11.
En la implementación de Wellons, que se puede encontrar en GitHub aquí , todos los objetos lstack_node no son atómicos. En particular, esto significa que todos los accesos al next miembro de un objeto lstack_node no son atómicos. Lo que no puedo entender es: ¿por qué tales accesos nunca compiten entre sí?
El next miembro se lee en lstack.c:30 . Está escrito en lstack.c:39 . Si estas dos líneas pueden ejecutarse simultáneamente en el mismo objeto lstack_node , entonces el programa contiene una carrera. es posible? Me parece posible:
lstack_pop , que llama a pop . Carga atómicamente el valor del nodo principal en la variable local orig . Ahora, orig.node es un puntero al nodo que estaba en la parte superior de la pila en este momento. (Tenga en cuenta que hasta este punto, solo se han modificado las variables locales, por lo que es imposible que algo que el subproceso 1 haya hecho hasta ahora haga que un CAS falle en cualquier otro subproceso). Mientras tanto...lstack_pop . pop tiene éxito y devuelve node , un puntero al nodo que se acaba de eliminar de la pila; este es el mismo nodo al que apunta orig.node en el subproceso 1. Luego comienza a llamar a push para agregar el node a la lista libre. El nodo principal de la lista libre se carga atómicamente, y el node->next está configurado para apuntar al primer nodo de la lista libre.orig.node->next en el subproceso 1. ¿Podría la implementación de Wellons simplemente ser incorrecta? Lo dudo. Si su implementación es incorrecta, entonces también lo es Boost, porque la única forma de arreglar (lo que me parece) la condición de carrera es hacer el next atómico. Pero no creo que la implementación de Boost pueda ser incorrecta de una manera tan básica sin que se haya notado y solucionado hasta ahora. Así que debo haber cometido un error en mi razonamiento.
Acabo de escribir un texto largo tratando de explicar por qué no puede haber una carrera, hasta que eché un vistazo más de cerca a cómo Wellson implementó la lista gratuita, ¡y llegué a la conclusión de que tienes razón!
El punto importante aquí es lo que mencionaste al comienzo de tu pregunta:
Esto parece simple hasta que tenemos que pensar en qué hacer con los nodos después de que se hayan reventado. Una estrategia es simplemente moverlos a una lista libre LIFO por pila hasta que finalmente todos los subprocesos terminen con la pila, momento en el cual un solo subproceso destruye todos los nodos en la pila y todos los nodos en la lista libre.
¡Pero no es así como funciona la lista libre en la implementación de Wellson! En su lugar, intenta reutilizar los nodos de la lista libre, pero next también debe ser atómico como observó correctamente. Si la lista libre se hubiera implementado como usted describió, es decir, los nodos reventados se agregarían a alguna lista libre ( sin modificar , es decir, la lista libre usa un puntero diferente al next ) y solo se liberaría una vez que ningún subproceso ya use la pila , entonces next podría ser una variable simple, ya que no cambiaría una vez que el nodo se haya insertado con éxito.
Eso no significa necesariamente que la cola sin bloqueo de impulso también sea incorrecta, pero no conozco el código lo suficientemente bien como para hacer una declaración calificada sobre la implementación de impulso.
FWIW: esto generalmente se conoce como el problema de recuperación de memoria. Este enfoque de lista libre es una solución simple, aunque generalmente no es práctico para escenarios del mundo real. Para un escenario del mundo real, probablemente desee utilizar un esquema de recuperación de memoria como indicadores de riesgo o recuperación basada en épocas. Puede echar un vistazo a mi biblioteca xenium donde he implementado varios esquemas de recuperación diferentes, así como estructuras de datos sin bloqueo que los usan. También se puede encontrar más información sobre el problema de recuperación de memoria y mis implementaciones en xenium en mi tesis Recuperación de memoria eficaz para estructuras de datos sin bloqueo en C++ .
La clave a tener en cuenta es que los siguientes campos son de solo lectura para cada nodo que se encuentra actualmente en una lista vinculada. El siguiente solo se puede modificar cuando el nodo se ha eliminado correctamente de una lista vinculada. Una vez que eso sucede, el subproceso que lo eliminó es 'propietario' y nadie más puede mirarlo con sensatez ( pueden leer un valor, pero ese valor se desechará cuando falle su compare_and_set). De modo que el subproceso propietario pueda modificar con seguridad el siguiente campo como parte de empujarlo en otra lista.
En su hipótesis, se está perdiendo el hecho de que los dos pops (realizados por los dos subprocesos) no pueden tener éxito y devolver el mismo nodo. Si dos subprocesos intentan aparecer simultáneamente, es posible que obtengan el mismo puntero de nodo, pero uno fallará en la instrucción atómica compare_and_set y regresará con un puntero de nodo diferente.
Esto requiere que las carreras de lectura/escritura sean "seguras", es decir, cuando tiene una carrera de lectura/escritura entre dos subprocesos, el lector puede obtener cualquier valor pero no fallará de otra manera (sin trampa u otro comportamiento indefinido), y no interferirá de otra manera con la escritura, pero ese tiende a ser el caso en la mayoría (¿todo?) El hardware. Siempre que el lector no dependa del valor leído durante una carrera, puede detectar la carrera después del hecho e ignorar ese valor.