Cualquier implementación de cola libre de bloqueo de un solo productor de un solo consumidor en C?

Question

Estoy escribiendo un programa con un hilo de consumidor y un productor, ahora parece que la sincronización de cola es una gran sobrecarga en el programa, y ​​busqué algunas implementaciones de cola sin bloqueo, pero solo encontré la versión de Lamport y una versión mejorada en PPoPP '08:

enqueue_nonblock(data) { 
    if (NULL != buffer[head]) { 
     return EWOULDBLOCK; 
    } 
    buffer[head] = data; 
    head = NEXT(head); 
    return 0; 
} 

dequeue_nonblock(data) { 
    data = buffer[tail]; 
    if (NULL == data) { 
     return EWOULDBLOCK; 
    } 
    buffer[tail] = NULL; 
    tail = NEXT(tail); 
    return 0; 
} 

Ambas versiones requieren un conjunto de pre-asignado para los datos, mi pregunta es que hay alguna, solo consumidor-productor único libre de bloqueo aplicación de colas que utiliza malloc() para asignar dinámicamente espacio ?

Y otra pregunta relacionada es, ¿cómo puedo medir la sobrecarga exacta en la sincronización de cola? Por ejemplo, cuánto tiempo lleva tomar pthread_mutex_lock(), etc.

Answer 1

Si le preocupa el rendimiento, agregar malloc() a la mezcla no ayudará. Y si no está preocupado por el rendimiento, ¿por qué no simplemente controlar el acceso a la cola a través de un mutex? ¿Has medido realmente el rendimiento de tal implementación? A mí me parece que estás yendo por la ruta familiar de la optimización prematura.

Answer 2

El algoritmo que muestra funciona porque aunque los dos subprocesos comparten el recurso (es decir, la cola), lo comparten de una manera muy particular. Como solo un hilo altera el índice principal de la cola (el productor) y solo un hilo altera el índice de cola (consumidor, por supuesto), no puede obtener un estado incoherente del objeto compartido. También es importante que el productor coloque los datos reales en antes de actualizando el índice principal y que el consumidor lea los datos que desea antes de actualizando el índice de cola.

Funciona tan bien como lo hace b/c la matriz es bastante estática; ambos hilos pueden contar con el almacenamiento de los elementos que están allí. Probablemente no pueda reemplazar la matriz por completo, pero lo que puede hacer es cambiar para qué se utiliza la matriz.

Es decir, en lugar de mantener los datos en la matriz, úselos para mantener los punteros a los datos. A continuación, puede malloc() y liberar() los elementos de datos, mientras pasa referencias (punteros) a ellos entre sus hilos a través de la matriz.

Además, posix admite leer un reloj de nanosegundos, aunque la precisión real depende del sistema. Puedes leer este reloj de alta resolución antes y después y solo restar.

Answer 3

Recuerdo haber visto uno que parecía interesante hace unos años, aunque parece que no puedo encontrarlo ahora. :(La implementación sin bloqueo que se propuso requirió el uso de un CAS primitive, aunque incluso la implementación de bloqueo (si no se quería usar la primitiva CAS) tenía características de perfusión bastante buenas --- los bloqueos solo impedían múltiples lectores o varios productores de golpear la cola al mismo tiempo, el productor todavía no compitió con el consumidor.

Recuerdo que el concepto fundamental detrás de la cola era crear una lista vinculada que siempre tenía un nodo "vacío" adicional en Este nodo adicional significaba que los indicadores de la cabeza y la cola de la lista solo se referirían a los mismos datos cuando la lista estaba vacía. Desearía poder encontrar el documento, no estoy haciendo justicia al algoritmo con mi explicación. ..

AH-ha!

He encontrado a alguien que transcribió the algorithm without the remainder of the article. Este podría ser un punto de partida útil.

Answer 4

He trabajado con una implementación de cola bastante simple que cumple con la mayoría de sus criterios. Usó un grupo de bytes de tamaño máximo estático, y luego implementamos mensajes dentro de eso. Había un puntero en la cabeza que un proceso se movería, y un puntero en la cola que el otro proceso movería.

Todavía se requieren bloqueos, pero usamos Peterson's 2-Processor Algorithm, que es bastante ligero ya que no implica llamadas al sistema. El bloqueo solo es necesario para áreas muy pequeñas y bien delimitadas: unos pocos ciclos de CPU a lo sumo, por lo que nunca bloqueará por mucho tiempo.

Answer 5

Creo que el asignador puede ser un problema de rendimiento. Puede intentar utilizar un asignador de memoria multihilo personalizado, que use una lista enlazada para mantener bloques liberados. Si sus bloques no son (casi) del mismo tamaño, puede implementar un "asignador de memoria del sistema Buddy", que es muy rápido. Tienes que sincronizar tu cola (buffer de anillo) con un mutex.

Para evitar demasiada sincronización, puede intentar escribir/leer múltiples valores a/desde la cola en cada acceso.

Si aún desea utilizar algoritmos sin bloqueos, debe utilizar datos preasignados o utilizar un asignador sin bloqueos. Hay un artículo sobre un asignador sin bloqueo "escalable asignación de memoria Dynamic Lock-Libre", y una implementación Streamflow

Antes de comenzar con la materia libre-Lock, mira: Circular lock-free buffer

Answer 6

Sí.

Existen varias colas de escritor múltiple de varios lectores sin candado.

He implementado una, por Michael y Scott, de su documento de 1996.

Voy a lanzar (después de algunas pruebas más) una pequeña biblioteca de estructuras de datos sin enclavamiento (en C) que incluirá esta cola.

Answer 7

La adición de malloc mataría cualquier ganancia de rendimiento que pueda obtener y una estructura basada en bloqueo sería igualmente efectiva. Esto es así porque malloc requiere algún tipo de bloqueo de CAS sobre el montón y, por lo tanto, algunas formas de malloc tienen su propio bloqueo, por lo que puede estar bloqueando el Administrador de memoria.

Para usar malloc que se necesita comprobar la validez asignar todos los nodos y gestionarlos con otra cola ...

Nota usted puede hacer algún tipo de matriz expandible que necesitaría para bloquear si se amplió.

Además, aunque están enclavadas, no tienen bloqueos en la CPU, colocan un bloqueo de memoria y bloquean la memoria durante el tiempo que dure la instrucción y, a menudo, detienen la tubería.

Answer 8

Debería mirar la biblioteca FastFlow