¿Estructuras de datos de árbol concurrentes de tiempo de actualización constante y sin bloqueo?

20

Últimamente he estado leyendo un poco de literatura y he encontrado algunas estructuras de datos bastante interesantes.

He investigado varios métodos diferentes para reducir el tiempo de actualización a peor tiempo de actualización [1-7].O(1)

Recientemente comencé a buscar estructuras de datos sin bloqueo para admitir el acceso concurrente eficiente.

¿Se ha utilizado alguna de estas técnicas de tiempo de actualización en el peor de los casos en la implementación de estructuras de datos sin bloqueo?O(1)

Pregunto porque; para mí, parecen la extensión práctica obvia de esta "mejora teórica".

  1. Tarjan, Robert Endre. "Actualización de un árbol de búsqueda equilibrado en O (1) rotaciones". Procesamiento de información Cartas 16, no. 5 (1983): 253-257.

  2. Driscoll, JR, N Sarnak, DD Sleator y RE Tarjan. “Hacer persistentes las estructuras de datos”. En las Actas del Decimoctavo Simposio Anual de ACM sobre Teoría de la Computación, 109–121. STOC '86. Nueva York, NY, EE. UU .: ACM, 1986.

  3. Levcopoulos, C. y Mark H. Overmars. "Un árbol de búsqueda equilibrado con O (1) peor tiempo de actualización del caso". Acta Inf. 26, no. 3 (noviembre de 1988): 269–277.

  4. Fleischer, Rudolf. Un árbol de búsqueda equilibrado simple con O (1) peor tiempo de actualización

  5. Dietz, Paul F y Rajeev Raman. “Un árbol de búsqueda de dedo de tiempo de actualización constante”. Cartas de procesamiento de información 52, no. 3 (1994): 147-154.

  6. Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas y Kostas Tsichlas. "Nuevos árboles de búsqueda equilibrados dinámicos con el peor tiempo de actualización constante". J. Autom. Lang. Peine. 8, no. 4 (julio de 2003): 607–632.

  7. Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis y Kostas Tsichlas. "Árboles óptimos de búsqueda de dedos en la máquina de puntero". J. Comput. Syst. Sci. 67, no. 2 (septiembre de 2003): 381–418.

reference-request data-structures time-complexity concurrency search-trees A
fuente
2
Considere agregar enlaces a los documentos como cortesía para las personas que desean investigar su problema.
Raphael
3
Bien, agregado en enlaces a los respectivos artículos.
AL
1
Sugiero volver a publicar en cstheory.SE (con un enlace aquí) si no obtiene una respuesta útil pronto.
JeffE
1
Gracias por la sugerencia. He vuelto a publicar: ¿estructuras de datos de árbol concurrentes sin bloqueo y con tiempo de actualización constante?
AL
Utilicé la biblioteca práctica de estructuras de datos sin bloqueo antes. Tienen cierto soporte de estructuras de datos de árbol sin bloqueo. Quizás tengas lo que estás buscando.
Reza

Respuestas:

4

O(1) no ayuda en sí mismo. En una estructura de datos sin bloqueo, debe haber una única instancia atómica cuando su estructura de datos parece cambiar. Todos los invariantes de representación deben estar vigentes tanto inmediatamente antes como inmediatamente después de ese instante atómico.

Esto significa que si está realizando una modificación en la estructura de datos, la característica importante es que puede hacer todas las modificaciones en una estructura de datos privada y luego intercambiar las modificaciones en una sola instrucción atómica.

La libertad de bloqueo suele ser más fácil cuando las estructuras de datos son inmutables ( puramente funcionales ). Simplemente mantenga un puntero global a la versión actual de la estructura de datos. Los lectores no necesitan bloquear nada. Las modificaciones a la estructura de datos se efectúan intercambiando el puntero global a una estructura de datos inmutable a otra.

Por ejemplo: si tiene un árbol equilibrado de árbol puramente funcional, usted:

  1. Registre el puntero global actual a la raíz del árbol.
  2. Cree un nuevo árbol que inserte o elimine un nodo. (Esto es logarítmico en tiempo y espacio en la cantidad de nodos actualmente en el árbol, e implica crear nuevos nodos desde el punto de modificación hasta la raíz, y solo señalar todo lo nuevo en las partes antiguas de la versión anterior de la estructura de datos. )
  3. Compare atómicamente e intercambie el puntero global a la raíz. (Tenga en cuenta que esto podría fallar si ha ocurrido otra modificación entre el momento en que registró el puntero raíz anterior y ahora. Si esto sucede, vuelva al paso 1 e intente nuevamente. Esto se denomina "control de concurrencia optimista").

Tenga en cuenta que la parte más importante es lo que dije anteriormente sobre la necesidad de mantener invariantes de representación. Por lo general, no es suficiente tener un algoritmo que atómicamente haga un cambio en el medio del árbol. ¿Por qué? Por ejemplo: puede tener un hilo lector que está en proceso de realizar un recorrido previo al pedido del árbol. Si modifica un nodo que es un antecesor del nodo que están leyendo actualmente, invalidará las condiciones previas que pensaron que habían aplicado. El lector debe poder trabajar con la estructura de datos exactamente como estaba antes de realizar el cambio, o exactamente como será después de que haya realizado el cambio. No hay algo en el medio.

Editar : como señaló @Raphael, existen técnicas para hacer que las estructuras de datos mutables estén libres de bloqueo. Una prueba por construcción de que esto siempre se puede hacer es: siempre que tenga un puntero global único a la "parte superior" de su estructura de datos, incluso si es mutable, siempre puede copiar toda la estructura de datos, realice sus modificaciones en el copie y luego, utilizando un control de concurrencia optimista, intente comparar e intercambiar el puntero a su estructura de datos recién creada para obtener el original. La belleza de las estructuras de datos funcionales basadas en árboles es que mantienen el costo de copiar en de una estructura de datos de tamaño .O ( N )O(log(N))O(N)

Lógica Errante
fuente
Creo que las técnicas de espera activa, por ejemplo, con comparar e intercambiar, generalmente se denominan "sin bloqueo", por lo que hay algunas salidas, incluso en la configuración mutable.
Raphael
No estoy familiarizado con el término espera activa (y Google no está ayudando). (Si está hablando del trabajo de Kogan y Petrank, eso muestra cómo convertir los algoritmos sin bloqueo en sin espera). Agregué una edición sobre cómo puede lidiar con la mutabilidad para la libertad de bloqueo en general.
Wandering Logic
Por "espera activa" me refiero a algo como while ( !P ) { noOp(); } doWork();dónde noOppuede ser a sleepo similar.
Raphael
En la parte Editar , mencionó la técnica para hacer que las estructuras de datos mutables estén libres de bloqueo. Como se indicó, copiamos toda la estructura de datos, hacemos modificaciones a la copia y luego usamos la primitiva CAS. Sin embargo, ¿cómo hacer que el Copypaso sea atómico? Parece ser otro problema difícil de atomic snapshot.
hengxin
@hengxin: piense en la primitiva CAS como un operador de "publicación". Antes de publicar la estructura de datos, solo el hilo que realiza las modificaciones tiene acceso a ella. Una vez que se publica la estructura de datos, es inmutable. El paso de copia no necesita ser atómico porque lo único que un hilo podría estar copiando es una versión publicada, que es inmutable. Si dos hilos intentan mutar simultáneamente, ambos copian la misma estructura de datos inmutable, modifican sus copias locales, y luego una de las operaciones de CAS tiene éxito y la otra falla. El que falla debe volver a copiarse y actualizarse.
Wandering Logic