language-agnostic queue atomic lockless

language agnostic - ¿Cómo construyo una cola sin cerrojo?



language-agnostic queue (5)

Hoy he pasado investigando las colas sin cerrojo. Tengo una situación de múltiples productores y consumidores múltiples. Implementé, para probar, un sistema que utilizaba el elemento de SLlock entrelazado en Win32 y duplicó el rendimiento de mi código basado en tareas con muchos subprocesos. Lamentablemente, sin embargo, deseo apoyar múltiples plataformas. El enclavamiento en múltiples plataformas no es un problema y puedo asumir con seguridad que puedo enclavar sin problemas. Sin embargo, la implementación real me pierde.

El gran problema parece ser que debes garantizar que una lista push / pop use solo una llamada entrelazada. De lo contrario, está dejando espacio para que otro hilo se filtre y arruine las cosas. No estoy seguro de cómo la implementación de Microsoft funciona bajo la cubierta y me encantaría saber más.

¿Alguien puede indicarme información útil (la plataforma y el lenguaje son bastante irrelevantes)?

Además de eso, me encantaría saber si es posible implementar un vector sin cerrojo. Eso tendría grandes cantidades de uso para mí :) ¡Salud!

Editar: Después de leer el artículo de DDJ sobre hierba, puedo ver una cola de bloqueo reducida que es bastante similar a la que ya tenía. Sin embargo, observo que al final hay documentos que pueden hacer la verdadera cola sin bloqueo usando una operación doble de comparación e intercambio (DCAS). ¿Alguien ha implementado una cola usando cmpxchg8b (o cmpxchg16b para el caso)?

Estoy reflexionando en este punto (no haber leído los documentos) pero podría usar este sistema para actualizar el puntero de la cabeza y la cola simultáneamente y así evitar cualquier problema con otro hilo saltando entre las 2 operaciones atómicas. Sin embargo, todavía necesitas obtener el siguiente puntero para probarlo contra el puntero de la cola para ver si acabas de modificar la cola. ¿Cómo se evita otro hilo cambiando esta información mientras el otro hilo se está preparando para hacerlo? ¿Cómo se implementa esto de manera sin cerraduras? ¿O es mejor leer la indescifrabilidad que es un trabajo de investigación? ;)

Creo que hay una discusión interesante sobre este tema aquí , especialmente este hilo.

Estos chicos lo han hecho, tal vez puedas encontrar algo de inspiración allí. Los otros archivos interesantes son yqueue.hpp y atomic_ptr.hpp

Probablemente podría implementar una cola de tamaño limitado con la menor dificultad ... Estuve pensando en ello últimamente y se me ocurrió este diseño, pero probablemente pueda encontrar muchas otras ideas interesantes: (ADVERTENCIA: ¡podría tener algunos problemas!)

  • la cola es una matriz de punteros a los elementos
  • tienes que administrar 2 punteros (cabeza, cola) que funcionan sobre la cola de la misma manera que un buffer circular
  • si head == tail , no hay elementos
  • si quieres enqueue(ptr) en enqueue(ptr) , Interlocked-Swap tail con NULL ( prev_tail es el valor intercambiado)
    • if prev_tail == NULL , intenta de nuevo
    • if prev_tail + 1 (con wraparound) == head , tu cola está llena
    • de lo contrario, ponga su ptr en *prev_tail y asigne prev_tail+1 a la tail ( prev_tail+1 cuidado con la envoltura del búfer)
  • para dequeue() hacer una copia tmp_head = head y check tmp_head == tail
    • si es verdadero, regresa porque la cola está vacía
    • si es falso
      • guardar *tmp_head como ptr
      • hacer un CAS: comparar la head con la head intercambio tmp_head con la head+1
      • si CAS falló - comienza toda la función
      • si tuvo éxito - devuelve ptr

Puede esperar en las operaciones de CAS de cabecera y cola, pero si no se disputa la cola, debe tener éxito la primera vez, sin bloqueos innecesarios.

Las colas de tamaño ilimitado son "un poco" más difíciles;) Pero debería poder crear una cola lo suficientemente grande para la mayoría de las necesidades.

La solución de viraptor se está bloqueando, no hay muchos productores / múltiples consumidores que no estén al tanto de la existencia de algotihms.

Es posible que desee echar un vistazo a la implementación de Herb Sutters de una cola de bloqueo bajo.

http://www.drdobbs.com/hpc-high-performance-computing/211601363

Utiliza los atomics de c ++ 0x pero sería (debería ser) fácil de implementar con sus operaciones atómicas de arquitecturas específicas (__sync_ * usando GNU, atomic_ * en solaris, etc.).