En la computación multiproceso , el problema de ABA ocurre durante la sincronización, cuando una ubicación se lee dos veces, tiene el mismo valor para ambas lecturas y "el valor es el mismo" se usa para indicar "nada ha cambiado". Sin embargo, otro hilo puede ejecutarse entre las dos lecturas y cambiar el valor, hacer otro trabajo, luego volver a cambiar el valor, engañando así al primer hilo haciéndole pensar que "nada ha cambiado" aunque el segundo hilo funcionó y viola esa suposición.
El problema de ABA ocurre cuando varios subprocesos (o procesos ) que acceden a datos compartidos se entrelazan. A continuación se muestra la secuencia de eventos que resultarán en el problema ABA:
- Proceso lee el valor A de la memoria compartida,
- se adelanta , permitiendo el proceso correr,
- modifica el valor de memoria compartida A al valor B y de nuevo a A antes de la preferencia,
- comienza la ejecución nuevamente, ve que el valor de la memoria compartida no ha cambiado y continúa.
Aunque puede seguir ejecutándose, es posible que el comportamiento no sea el correcto debido a la modificación "oculta" en la memoria compartida.
Un caso común del problema ABA se encuentra al implementar una estructura de datos sin bloqueo . Si un elemento se quita de la lista, se elimina y luego se asigna un nuevo elemento y se agrega a la lista, es común que el objeto asignado esté en la misma ubicación que el objeto eliminado debido a la asignación de memoria MRU . Por lo tanto, un puntero al nuevo elemento suele ser igual a un puntero al elemento antiguo, lo que provoca un problema de ABA.
Ejemplos de
Considere un ejemplo de software (escrito en C ++) de ABA usando una pila sin bloqueo :
/ * Pila ingenua sin bloqueo que sufre un problema ABA. * / Class Stack { std :: atomic < Obj *> top_ptr ; // // Muestra el objeto superior y le devuelve un puntero. // Obj * Pop () { while ( 1 ) { Obj * ret_ptr = top_ptr ; if ( ! ret_ptr ) return nullptr ; // Para simplificar, suponga que podemos asegurarnos de que esta desreferenciación es segura // (es decir, que ningún otro hilo ha aparecido en la pila mientras tanto). Obj * next_ptr = ret_ptr -> siguiente ; // Si el nodo superior sigue siendo ret, entonces suponga que nadie ha cambiado la pila. // (Esa afirmación no siempre es cierta debido al problema de ABA) // Reemplaza atómicamente top con next. if ( top_ptr . compare_exchange_weak ( ret_ptr , next_ptr )) { return ret_ptr ; } // La pila ha cambiado, empieza de nuevo. } } // // Empuja el objeto especificado por obj_ptr a la pila. // anular Push ( Obj * obj_ptr ) { while ( 1 ) { Obj * next_ptr = top_ptr ; obj_ptr -> siguiente = next_ptr ; // Si el nodo superior sigue siendo el siguiente, supongamos que nadie ha cambiado la pila. // (Esa afirmación no siempre es cierta debido al problema de ABA) // Reemplaza atómicamente top con obj. if ( top_ptr . compare_exchange_weak ( next_ptr , obj_ptr )) { return ; } // La pila ha cambiado, empieza de nuevo. } } };
Este código normalmente puede prevenir problemas de acceso concurrente, pero adolece de problemas ABA. Considere la siguiente secuencia:
La pila contiene inicialmente top → A → B → C
El hilo 1 comienza a correr pop:
ret = A;siguiente = B;
El hilo 1 se interrumpe justo antes del compare_exchange_weak
...
{ // El hilo 2 se ejecuta pop: ret = A ; siguiente = B ; compare_exchange_weak ( A , B ) // Éxito, arriba = B return A ; } // Ahora la pila está en la parte superior → B → C { // El hilo 2 se ejecuta pop de nuevo: ret = B ; siguiente = C ; compare_exchange_weak ( B , C ) // Éxito, arriba = C return B ; } // Ahora la pila está arriba → C eliminar B ; { // El hilo 2 ahora empuja A de nuevo a la pila: A -> siguiente = C ; compare_exchange_weak ( C , A ) // Éxito, top = A }
Ahora la pila está arriba → A → C
Cuando se reanuda el hilo 1:
compare_exchange_weak (A, B)
Esta instrucción tiene éxito porque encuentra top == ret (ambos son A), por lo que establece top a next (que es B). Como se ha eliminado B, el programa accederá a la memoria liberada cuando intente ver el primer elemento de la pila. En C ++, como se muestra aquí, acceder a la memoria liberada es un comportamiento indefinido : esto puede resultar en fallas, corrupción de datos o incluso simplemente parecer que funciona correctamente en silencio. Los errores de ABA como este pueden ser difíciles de depurar.
El problema real no es 'ABA', es decir, en el ejemplo no importa si el valor de A ha cambiado. El problema real se debe a que B se elimina de la lista y se libera la memoria que ocupa. Incluso si A no se ha cambiado, es decir, la lista enlazada está enlazada individualmente hacia atrás C-> B-> A y tail-> A, pero B es borrado y liberado por otro hilo, el problema anterior aún existe. Esto lleva a otro problema, es decir, si B es eliminado de la lista por otro hilo, la cola apuntaría al B eliminado. El 'Problema ABA' es, por lo tanto, realmente el 'Problema B' que no tiene mucho que ver con A.
Soluciones alternativas
Referencia de estado etiquetado
Una solución alternativa común es agregar bits de "etiqueta" o "sello" adicionales a la cantidad que se está considerando. Por ejemplo, un algoritmo que utiliza comparar e intercambiar en un puntero puede 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 e intercambio fallará, incluso si las direcciones son las mismas, porque los bits de la etiqueta no coincidirán. Esto a veces se llama ABAʹ porque 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 separado si se dispone de CAS de doble ancho.
Si el campo "etiqueta" se cierra, las garantías contra ABA ya no se mantienen. Sin embargo, se ha observado que en las CPU que existen actualmente y que utilizan 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, a efectos prácticos, suele ser suficiente tener entre 40 y 48 bits de etiqueta para garantizar que no se envuelva. 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]
Nodos intermedios
Un enfoque correcto pero costoso es usar nodos intermedios que no sean elementos de datos y así asegurar invariantes a medida que se insertan y eliminan elementos [Valois].
Recuperación diferida
Otro enfoque consiste en aplazar la recuperación de elementos de datos eliminados. Una forma de aplazar la recuperación es ejecutar el algoritmo en un entorno con un recolector de basura automático ; Sin embargo, un problema aquí es que si el GC no está libre de bloqueos, entonces el sistema general no está libre de bloqueos, aunque la estructura de datos sí lo esté.
Otra forma de aplazar la recuperación es utilizar uno o más indicadores de peligro , que son indicadores de ubicaciones que de otro modo no podrían aparecer en la lista. Cada indicador de peligro representa un estado intermedio de un cambio en curso; la presencia del puntero asegura una mayor sincronización [Doug Lea]. Los indicadores de peligro no tienen bloqueo, pero solo pueden rastrear como máximo un número fijo de elementos por hilo como en uso.
Otra forma más de diferir la reclamación es usar la actualización de lectura-copia (RCU) , que implica encerrar la actualización en una sección crítica del lado de lectura de RCU y luego esperar un período de gracia de RCU antes de liberar cualquier elemento de datos eliminado. El uso de RCU de esta manera garantiza que cualquier elemento de datos eliminado no pueda volver a aparecer hasta que se hayan completado todas las operaciones en ejecución. RCU no tiene bloqueos, pero no es adecuado para todas las cargas de trabajo.
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 pueden actualizarse atómicamente; si bien esta característica depende de la arquitectura, en particular, está disponible para arquitecturas x86 / x64 (x86 permite CAS de 64 bits, y todas las CPU modernas x64 permiten CAS de 128 bits) y z / Architecture de IBM (que permite CAS de hasta 128 bits).
Algunas arquitecturas proporcionan una instrucción condicional de tienda vinculada a la carga en la que la tienda se realiza solo cuando no hay otras tiendas de la ubicación indicada. Esto separa efectivamente la noción de "el almacenamiento contiene valor" de "el almacenamiento ha cambiado". Los ejemplos incluyen DEC Alpha , MIPS , PowerPC , RISC-V y ARM (v6 y posteriores).
Ver también
Referencias
- Dechev, Damian; Pirkelbauer, Peter; Stroustrup, Bjarne . "Matrices dinámicamente redimensionables sin bloqueo". CiteSeerX 10.1.1.86.2680 . Cite journal requiere
|journal=
( ayuda ) - Dechev, Damian; Pirkelbauer, Peter; Stroustrup, Bjarne . "Comprensión y prevención eficaz del problema de ABA en diseños sin bloqueo basados en descriptores" (PDF) . Cite journal requiere
|journal=
( ayuda )
- ^ Liebre 'No Bugs', CAS (Re) Actor para primitivas multiproceso sin bloqueo , sobrecarga # 142