En un entorno informático multiproceso , los indicadores de peligro son un enfoque para resolver los problemas planteados por 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 libre de bloqueos que utilice la primitiva de comparar e intercambiar debe resolver el problema de ABA . Por ejemplo, en una pila sin candados 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 "B", y luego lo realiza . Desafortunadamente, en el medio de esta operación, otro hilo puede haber hecho dos estallidos y luego empujar A hacia arriba, resultando en 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 de la forma
Nodo * currentNode = this -> head ; // asumimos que la carga de "this-> head" es atomic Node * nextNode = currentNode -> next ; // asumimos 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 subproceso pueda hacer saltar 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 la memoria desasignada (que de hecho ya puede estar en uso por algún otro subproceso un propósito completamente diferente).
Los indicadores de peligro se pueden utilizar para abordar ambos problemas. En un sistema de punteros de peligro, cada subproceso mantiene una lista de punteros de peligro que indican a qué nodos está accediendo actualmente el subproceso. (En muchos sistemas, esta "lista" puede estar probablemente limitada a sólo uno [1] [2] o dos elementos.) Los nodos de la lista de punteros de peligro no deben ser modificados ni desasignados por ningún otro hilo.
Cada hilo de lectura posee un puntero compartido de un solo escritor / lector múltiple llamado "puntero de peligro". Cuando un hilo lector 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 ciertamente mantén tus
delete
manos fuera de él ".- Andrei Alexandrescu y Maged Michael, estructuras de datos sin bloqueo con punteros de peligro [2]
Cuando un hilo desea eliminar un nodo, lo coloca en una lista de nodos "para ser liberados más tarde", pero en realidad no desasigna la memoria del nodo hasta que ninguna otra lista de peligro del hilo contenga el puntero. Esta recolección manual de basura puede ser realizada por un hilo de recolección de basura dedicado (si la lista "para ser liberado más tarde" es compartida por todos los hilos); alternativamente, cada subproceso trabajador puede limpiar la lista "por liberar" como parte de una operación como "pop" (en cuyo caso cada subproceso trabajador puede ser responsable de su propia lista "por liberar").
En 2002, Maged Michael de IBM presentó una solicitud de patente estadounidense sobre la técnica del puntero de peligro, [3] pero la solicitud fue abandonada en 2010.
Las alternativas a los indicadores de peligro incluyen el recuento de referencias . [1]
Ver también
Referencias
- ^ a b c Anthony Williams. Concurrencia de C ++ en acción: multiproceso práctico. Manning: Shelter Island, 2012. Ver en particular el Capítulo 7.2, "Ejemplos de estructuras de datos sin bloqueo".
- ↑ a b Andrei Alexandrescu y Maged Michael (2004). "Estructuras de datos sin bloqueo con punteros de peligro" . Dr. Dobb's . (Artículo orientado a C ++)
- ^ Solicitud de EE. UU. 20040107227Maged M. Michael, "Método para la implementación eficiente de estructuras de datos dinámicas sin bloqueo con recuperación de memoria segura". Presentada el 3 de diciembre de 2002.
- Maged Michael (2004). "Punteros de peligro: recuperación de memoria segura para objetos sin candados" (PDF) . Transacciones IEEE en sistemas paralelos y distribuidos . 15 (8): 491–504. CiteSeerX 10.1.1.130.8984 . doi : 10.1109 / TPDS.2004.8 .
enlaces externos
- Bloques de construcción concurrentes : implementación en C ++ de Hazard Pointer (llamado "SMR") y otras estructuras de datos sin bloqueos. También tiene interfaces Java.
- Kit de simultaneidad : implementación en C de Hazard Pointer y estructuras de datos sin bloqueo
- Atomic Ptr Plus : biblioteca C / C ++ que tiene una implementación de puntero de peligro
- El cambio de paralelismo y el modelo de memoria de C ++: contiene la implementación de C ++ para Windows en los apéndices
- libcds : biblioteca C ++ de contenedores sin bloqueo e implementación de puntero de peligro