En la computación multiproceso , el problema ABA ocurre durante la sincronización, cuando una ubicación se lee dos veces, tiene el mismo valor para ambas lecturas, y el hecho de que el valor leído sea el mismo dos veces se utiliza para concluir que no ha sucedido nada en el ínterin; sin embargo, otro hilo puede ejecutarse entre las dos lecturas y cambiar el valor, hacer otro trabajo y luego volver a cambiar el valor, engañando así al primer hilo para que piense que nada ha cambiado a pesar de que el segundo hilo realizó un trabajo que viola esa suposición.
El problema ABA se produce cuando varios subprocesos (o procesos ) que acceden a datos compartidos se intercalan. A continuación, se muestra una secuencia de eventos que ilustra el problema ABA:
Aunque puede continuar ejecutándose, es posible que el comportamiento no sea correcto debido a la modificación "oculta" en la memoria compartida.
Un caso común del problema ABA se presenta al implementar una estructura de datos sin bloqueos . Si se elimina un elemento de la lista, se lo elimina y luego se asigna y agrega un elemento nuevo a la lista, es común que el objeto asignado se encuentre en la misma ubicación que el objeto eliminado debido a la asignación de memoria MRU . Por lo tanto, un puntero al elemento nuevo suele ser igual a un puntero al elemento anterior, lo que causa un problema ABA.
Considere un ejemplo de software (escrito en C++) de ABA que utiliza una pila sin bloqueos :
/* Pila ingenua sin bloqueos que sufre del problema ABA.*/ class Stack { std :: atomic < Obj *> top_ptr ; // // Hace estallar el objeto superior y devuelve un puntero a él. // Obj * Pop () { while ( 1 ) { Obj * ret_ptr = top_ptr ; if ( ret_ptr == nullptr ) return nullptr ; // Para simplificar, supongamos que podemos asegurar que esta desreferencia es segura // (es decir, que ningún otro hilo ha hecho estallar la pila mientras tanto). Obj * next_ptr = ret_ptr -> next ; // Si el nodo superior sigue siendo ret, entonces supongamos que nadie ha cambiado la pila. // (Esa afirmación no siempre es verdadera debido al problema ABA) // Reemplaza atómicamente top por next. if ( top_ptr . compare_exchange_weak ( ret_ptr , next_ptr )) { return ret_ptr ; } // La pila ha cambiado, empezar de nuevo. } } // // Empuja el objeto especificado por obj_ptr a la pila. // void Push ( Obj * obj_ptr ) { while ( 1 ) { Obj * next_ptr = top_ptr ; obj_ptr -> next = next_ptr ; // Si el nodo superior sigue siendo el siguiente, entonces se supone que nadie ha cambiado la pila. // (Esa afirmación no siempre es verdadera debido al problema ABA) // Reemplazar atómicamente top con obj. if ( top_ptr . compare_exchange_weak ( next_ptr , obj_ptr )) { return ; } // La pila ha cambiado, empezar de nuevo. } } }; Este código normalmente puede evitar problemas de acceso simultáneo, pero presenta problemas de ABA. Considere la siguiente secuencia:
La pila inicialmente contiene top → A → B → C
El hilo 1 comienza a ejecutarse pop:
ret = A;siguiente = B;
El hilo 1 se interrumpe justo antes de compare_exchange_weak...
{ // El hilo 2 ejecuta pop: ret = A ; next = B ; compare_exchange_weak ( A , B ) // Éxito, top = B return A ; } // Ahora la pila es top → B → C { // El hilo 2 ejecuta pop de nuevo: ret = B ; next = C ; compare_exchange_weak ( B , C ) // Éxito, top = C return B ; } // Ahora la pila es top → C delete B ; { // El hilo 2 ahora vuelve a colocar A en la pila: A -> next = C ; compare_exchange_weak ( C , A ) // Éxito, top = A } Ahora la pila es top → A → C
Cuando se reanude el hilo 1:
comparar_intercambio_débil(A, B)
Esta instrucción tiene éxito porque encuentra top == ret (ambos son A), por lo que establece top en el siguiente (que es B). Como B se ha eliminado, el programa accederá a la memoria liberada cuando intente ver el primer elemento en la pila. En C++, como se muestra aquí, acceder a la memoria liberada es un comportamiento indefinido : esto puede provocar fallas, corrupción de datos o incluso simplemente parecer que funciona correctamente de manera silenciosa. Los errores de ABA como este pueden ser difíciles de depurar.
Una solución alternativa habitual es añadir bits de "etiqueta" o "sello" adicionales a la cantidad que se está considerando. Por ejemplo, un algoritmo que utilice la comparación y el intercambio en un puntero podría utilizar los bits bajos de la dirección para indicar cuántas veces se ha modificado correctamente el puntero. Debido a esto, la siguiente comparación y el intercambio fallarán, incluso si las direcciones son las mismas, porque los bits de etiqueta no coincidirán. Esto a veces se denomina ABAʹ, ya que la segunda A se hace ligeramente diferente de la primera. Estas referencias de estado etiquetadas también se utilizan en la memoria transaccional . Aunque se puede utilizar un puntero etiquetado para la implementación, se prefiere un campo de etiqueta independiente si está disponible CAS de ancho doble.
Si el campo "tag" se reinicia, las garantías contra ABA ya no existen. Sin embargo, se ha observado que en las CPU existentes actualmente y utilizando etiquetas de 60 bits, no es posible realizar un reinicio siempre que la vida útil del programa (es decir, sin reiniciar el programa) esté limitada a 10 años; además, se argumentó que, para fines prácticos, suele ser suficiente tener 40-48 bits de etiqueta para garantizar que no se produzca un reinicio. Como las CPU modernas (en particular, todas las CPU x64 modernas) tienden a admitir operaciones CAS de 128 bits, esto puede permitir garantías firmes contra ABA. [1]
Un enfoque correcto pero costoso es utilizar nodos intermedios que no sean elementos de datos y así garantizar invariantes a medida que se insertan y eliminan elementos [Valois].
Otro enfoque consiste en aplazar la recuperación de los elementos de datos eliminados. Una forma de aplazar la recuperación es ejecutar el algoritmo en un entorno que cuente con un recolector de basura automático ; sin embargo, el problema aquí es que si el recolector de basura no está libre de bloqueos, entonces el sistema en general no está libre de bloqueos, aunque la estructura de datos en sí lo esté.
Otra forma de aplazar la recuperación es utilizar uno o más punteros de riesgo , que son punteros a ubicaciones que de otro modo no pueden aparecer en la lista. Cada puntero de riesgo representa un estado intermedio de un cambio en curso; la presencia del puntero asegura una mayor sincronización [Doug Lea]. Los punteros de riesgo no tienen bloqueos, pero solo pueden rastrear como máximo una cantidad fija de elementos por hilo que estén en uso.
Otra forma de posponer la recuperación es utilizar la actualización de copia de lectura (RCU) , que implica encerrar la actualización en una sección crítica del lado de lectura de la RCU y luego esperar un período de gracia de la RCU antes de liberar los elementos de datos eliminados. El uso de la RCU de esta manera garantiza que cualquier elemento de datos eliminado no pueda reaparecer hasta que se hayan completado todas las operaciones que se están ejecutando actualmente. La RCU no tiene bloqueos, pero no es adecuada para todas las cargas de trabajo.
En lugar de utilizar una única instrucción de comparación e intercambio de todo el puntero, algunos procesadores tienen otras instrucciones diseñadas para ser más resistentes o inmunes al problema ABA.
Algunas arquitecturas proporcionan operaciones atómicas "más grandes" de modo que, por ejemplo, tanto los enlaces hacia adelante como hacia atrás en una lista doblemente enlazada se pueden actualizar atómicamente; si bien esta característica depende de la arquitectura, está disponible, en particular, para las arquitecturas x86/x64 (x86 permite CAS de 64 bits, y todas las CPU x64 modernas permiten CAS de 128 bits) y para z/Architecture de IBM (que permite CAS de hasta 128 bits).
Algunas arquitecturas proporcionan una instrucción condicional de almacenamiento vinculada a la carga en la que el almacenamiento se realiza solo cuando no hay otros almacenamientos de la ubicación indicada. Esto separa de manera efectiva la noción de "el almacenamiento contiene valor" de "el almacenamiento ha cambiado". Algunos ejemplos incluyen DEC Alpha , MIPS , PowerPC , RISC-V y ARM (v6 y posteriores). Dado que estas instrucciones proporcionan atomicidad utilizando la dirección en lugar del valor, las rutinas que utilizan estas instrucciones son inmunes al problema ABA. [2]
