En un entorno informático multiproceso , los punteros de riesgo son un enfoque para resolver los problemas que plantea la gestión dinámica de la memoria de los nodos en una estructura de datos sin bloqueos . Estos problemas generalmente surgen solo en entornos que no tienen recolección automática de basura . [1]
Cualquier estructura de datos sin bloqueos que utilice la primitiva de comparación e intercambio debe lidiar con el problema ABA . Por ejemplo, en una pila sin bloqueos representada como una lista enlazada intrusivamente, un hilo puede estar intentando sacar un elemento del frente de la pila (A → B → C). Recuerda el segundo valor desde arriba "B" y luego realiza . Desafortunadamente, en medio de esta operación, otro hilo puede haber hecho dos extracciones y luego haber empujado A de nuevo al principio, lo que da como resultado la pila (A → C). La comparación e intercambio logra intercambiar `head` con `B`, y el resultado es que la pila ahora contiene basura (un puntero al elemento liberado "B").compare_and_swap(target=&head, newvalue=B, expected=A)
Además, cualquier algoritmo sin bloqueo que contenga código con la forma
Nodo * currentNode = this -> head ; // suponga que la carga de "this->head" es atómica Nodo * nextNode = currentNode -> next ; // suponga que esta carga también es atómica
sufre otro problema importante, en ausencia de recolección automática de basura. Entre esas dos líneas, es posible que otro hilo pueda sacar el nodo al que apunta this->head
y desasignarlo, lo que significa que el acceso a la memoria a través currentNode
de la segunda línea lee memoria desasignada (que de hecho puede estar ya en uso por algún otro hilo para un propósito completamente diferente).
Los punteros de riesgo se pueden utilizar para solucionar ambos problemas. En un sistema de punteros de riesgo, cada subproceso mantiene una lista de punteros de riesgo que indican a qué nodos está accediendo actualmente el subproceso. (En muchos sistemas, esta "lista" puede estar limitada probablemente a un solo [1] [2] o dos elementos). Los nodos de la lista de punteros de riesgo no deben ser modificados ni desasignados por ningún otro subproceso.
Cada hilo de lectura posee un puntero compartido por un solo escritor y varios lectores llamado "puntero de peligro". Cuando un hilo de lectura asigna la dirección de un mapa a su puntero de peligro, básicamente está anunciando a otros hilos (escritores): "Estoy leyendo este mapa. Puedes reemplazarlo si quieres, pero no cambies su contenido y, por supuesto, no
delete
lo toques".— Andrei Alexandrescu y Maged Michael, Estructuras de datos sin bloqueos con punteros de riesgo [2]
Cuando un subproceso desea eliminar un nodo, lo coloca en una lista de nodos "que se liberarán más tarde", pero en realidad no libera la memoria del nodo hasta que ninguna otra lista de peligros de subprocesos contenga el puntero. Esta recolección manual de basura puede ser realizada por un subproceso de recolección de basura dedicado (si la lista "que se liberará más tarde" es compartida por todos los subprocesos); de manera alternativa, la limpieza de la lista "que se liberará" puede ser realizada por cada subproceso de trabajo como parte de una operación como "pop" (en cuyo caso cada subproceso de trabajo puede ser responsable de su propia lista "que se liberará").
En 2002, Maged Michael de IBM presentó una solicitud de patente estadounidense sobre la técnica del indicador de peligro, [3] pero la solicitud fue abandonada en 2010.
Las alternativas a los indicadores de riesgo incluyen el recuento de referencias . [1]