Problema ABA

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de abril de 2021; las comprobaciones requieren 3 ediciones .

En la computación multitarea , el problema ABA ocurre durante la sincronización , cuando una celda de memoria se lee dos veces, el mismo valor se lee ambas veces y el signo "el valor es el mismo" se interpreta como "nada ha cambiado". Sin embargo, otro subproceso puede ejecutarse entre estas dos lecturas, cambiar el valor, hacer otra cosa y restaurar el valor anterior. Así, el primer hilo será engañado haciéndole creer que nada ha cambiado, aunque el segundo hilo ya ha destruido esta suposición.

El problema de ABA ocurre cuando varios subprocesos (o procesos ) acceden a la memoria compartida uno a la vez . Aquí hay un ejemplo de la secuencia de eventos que conducen al problema ABA:

Aunque puede seguir funcionando, es posible que su comportamiento sea incorrecto debido a otros cambios ocultos en la memoria compartida (que no ha rastreado).

Por lo general, el problema ABA se encuentra al implementar estructuras y algoritmos sin bloqueo . Si elimina un elemento de la lista , lo destruye y luego crea un nuevo elemento y lo vuelve a agregar a la lista, existe la posibilidad de que el nuevo elemento se coloque en el lugar del anterior. El puntero del nuevo elemento coincidirá con el puntero del antiguo, lo que generará un problema: la igualdad de signos no es la igualdad de los datos en su conjunto.

Ejemplo

Considere una pila sin bloqueo :

/* Una implementación ingenua de una pila sin bloqueo que sufre del problema ABA. */ pila de clase { objeto volátil * top_ptr ; // // Elimina el elemento superior y le devuelve un puntero. // Objeto * Pop () { mientras ( 1 ) { Obj * ret_ptr = top_ptr ; si ( ! ret_ptr ) devuelve NULL ; Obj * siguiente_ptr = ret_ptr -> siguiente ; // Si el elemento superior todavía está en reposo, suponga que nadie ha cambiado la pila. // (Esta afirmación no siempre es cierta debido al problema de ABA) // Reemplaza atómicamente top con next. if ( CompareAndSwap ( top_ptr , ret_ptr , next_ptr )) { volver ret_ptr ; } // De lo contrario, la pila cambió, intente nuevamente. } } // // Agrega obj_ptr a la parte superior de la pila. // Empuje vacío ( Obj * obj_ptr ) { mientras ( 1 ) { Obj * next_ptr = top_ptr ; obj_ptr -> siguiente = siguiente_ptr ; // Si el elemento superior sigue siendo el siguiente, suponga que nadie ha cambiado la pila. // (Esta afirmación no siempre es cierta, debido al problema de ABA) // Reemplaza atómicamente top con obj. if ( CompareAndSwap ( top_ptr , next_ptr , obj_ptr )) { volver ; } // De lo contrario, la pila cambió, intente nuevamente. } } };

Este código generalmente puede evitar problemas de concurrencia, pero sufre un problema de ABA. Considere la siguiente secuencia:

La pila inicialmente contiene arriba → A → B → C

El hilo 1 comienza a ejecutar pop:

ret = A; siguiente=B;

El subproceso 1 se interrumpe justo antes de CompareAndSwap ...

{ // El hilo 2 ejecuta pop: ret = A ; siguiente = B ; CompareAndSwap ( A , A , B ) // Buena suerte, top = B return A ; } // Ahora en la parte superior de la pila → B → C { // El subproceso 2 aparece de nuevo: ret = B ; siguiente = C ; CompareAndSwap ( B , B , C ) // Buena suerte, top = C return B ; } // Ahora en la cima de la pila → C delete B ; { // El subproceso 2 empuja A de vuelta a la pila: A -> siguiente = C ; CompareAndSwap ( C , C , A ) // Suerte, superior = A }

La pila ahora contiene top → A → C

El hilo 1 sigue funcionando:

Comparar e intercambiar (A, A, B)

Esta instrucción tiene éxito porque top == ret (ambos son iguales a A), establece top con next (que es igual a B). ¡Pero B fue destruido! Esto conducirá a malos resultados...

.Net te permite implementar la función CompareAndSwap (CAS) de forma atómica gracias al método Interlocked.CompareExchange().

bool estático privado CAS ( ref Node < T > ubicación , Nodo < T > nuevo valor , Nodo < T > comparador ) { // 1. si el comparador y la ubicación son iguales, entonces otro hilo no tocó la ubicación // 2. la ubicación lo hará se asignará a newValue // 3. El método devolverá el valor de ubicación anterior independientemente de la asignación // 4. copmarand comparará con el valor de ubicación anterior (es decir, oldLocation) // 5. si oldLocation(antiguo, devuelto) no se ha cambiado por otro hilo, entonces CAS devolverá true, porque coincide con el comparador var oldLocation = Interlocked . CompareExchange < Nodo < T >>( ubicación ref , nuevoValor , comparando ); // esta es una operación atómica return comparand == oldLocation ; }

Un ejemplo de una pila sin bloqueo para .Net usando una función CAS atómica:

public class SimpleStack < T > { private class Node < V > { public Node < V > Siguiente ; artículo V público ; } nodo privado < T > cabeza ; public SimpleStack () { cabeza = nuevo Nodo < T >(); } public void Push ( elemento T ) { Nodo < T > nodo = nuevo Nodo < T >(); nodo _ elemento = elemento ; hacer { nodo . siguiente = cabeza . siguiente ; } while ( CAS ( ref head . Next , node , node . Next ) == false ); // espera hasta que node.Next y head.Next apunten al mismo elemento. // Luego puede intercambiar punteros para que la cabeza apunte al nodo. Después de esa salida del bucle. } public T Pop () { Nodo < T > nodo ; hacer { nodo = cabeza . siguiente ; if ( nodo == nulo ) devuelve el valor predeterminado ( T ); } while ( CAS ( ref head . Next , node . Next , node ) == false ); // 1. No habrá problema ABA en CAS. // 2. node.Next no arroja una NullReferenceException (node ​​!= null), // porque la memoria se administra en .Net return node . artículo ; } }

El problema de ABA para esta implementación de pila en .net se vuelve irrelevante por el entorno del recolector de basura: no perdemos ni reutilizamos (en otro subproceso) la referencia al nodo (al acceder a node.Next en el CAS) si el subproceso #2 viene primero que el subproceso #1 realizará la operación Pop(). En entornos sin gestión de memoria, este problema es agudo y esta solución no es adecuada.

Soluciones alternativas

Una solución común es agregar bits de "marca" adicionales al valor que se está probando. Por ejemplo, un algoritmo que usa comparar e intercambiar punteros podría usar los bits inferiores de una dirección para comprobar cuántas veces se ha cambiado el puntero. Debido a esto, la próxima comparación e intercambio no funcionará porque los bits de marca no coincidirán. Esto no resuelve completamente el problema, ya que el valor de los bits de la etiqueta puede sufrir un ajuste cero . Algunas arquitecturas proporcionan una comparación e intercambio de dos palabras que permite una etiqueta más grande. Esto generalmente se llama ABA' porque el segundo valor de A es ligeramente diferente del primero.

El enfoque correcto pero costoso es utilizar nodos intermedios, que no son datos de usuario, pero proporcionan invariancia para las operaciones de adición y eliminación. [Valois].

Otro enfoque es utilizar uno o más indicadores de riesgo (indicadores de riesgo), indicadores que, en principio, no pueden aparecer en una estructura de datos. Cada indicador de peligro denota un estado intermedio de la estructura en el proceso de cambio; tener punteros requiere una mayor sincronización ( Dag Lee ).

Algunas arquitecturas proporcionan operaciones atómicas "ampliadas", de modo que, por ejemplo, es posible cambiar atómicamente ambas referencias a la vez, hacia adelante y hacia atrás, en una lista doblemente enlazada.

Algunas arquitecturas proporcionan una declaración condicional de almacenamiento vinculada a la carga en la que solo se puede escribir en una celda si no ha habido otras escrituras en la celda especificada. Esto separa efectivamente la función "la celda contiene un valor" de la función "la celda ha sido modificada". Los ejemplos de arquitectura son ARM , DEC Alpha , PowerPC .

Literatura

  1. Damian Dechev, Peter Pirkelbauer y Bjarne Stroustrup. Matrices redimensionables dinámicamente sin bloqueo
  2. Julian M Bucknall, Estructuras de datos sin bloqueo: la pila. [una]

Enlaces