¿Es posible un solo productor y múltiples productores en una configuración sin bloqueo?

Question

Tengo un montón de hilos que hacen mucha comunicación entre ellos. Preferiría esto estar libre de bloqueo.

Para cada hilo, quiero tener un buzón, donde otros hilos pueden enviarle mensajes, (pero solo el propietario puede eliminar mensajes). Esta es una situación de consumidor único de múltiples productores. ¿es posible para mí hacer esto en un asunto sin bloqueo/alto rendimiento? (Esto está en el bucle interno de una simulación gigantesca).

Answer 1

Claro, si usted tiene una instrucción atómica CompareAndSwap:

for (i = 0; ; i = (i + 1) % MAILBOX_SIZE) 
{ 
    if ((mailbox[i].owned == false) && 
     (CompareAndSwap(&mailbox[i].owned, true, false) == false)) 
     break; 
} 

mailbox[i].message = message; 
mailbox[i].ready = true; 

Después de leer un mensaje, el hilo de consumir solo establece mailbox[i].ready = false; mailbox[i].owned = false; (en ese orden).

Answer 2

es posible que desee ver los bloques de creación de subprocesos de Intel, recuerdo que una conferencia del desarrollador de Intel mencionó algo parecido.

Answer 3

Aquí hay un paper from the University of Rochester illustrating a non-blocking concurrent queue. El algoritmo descrito en el documento muestra una técnica para hacer una cola sin bloqueo.

Answer 4

Cola libre de múltiples productores Única consumidora (MPSC) La cola es uno de los algoritmos de bloqueo más fáciles de implementar.

La implementación más básica requiere una simple lista de enlace único sin bloqueo (SList) con solo push() y flush(). Las funciones están disponibles en la API de Windows como InterlockedFlushSList() e InterlockedPushEntrySList() pero son muy fáciles de rodar por su cuenta.

Múltiples elementos de empuje del productor() en el SList usando un CAS (interbloqueo de comparación y cambio).

El consumidor individual hace un color() que intercambia el encabezado del SList con un NULL usando un intercambio XCHG (intercambio entrelazado). El consumidor tiene una lista de artículos en el orden inverso.

Para procesar los elementos en orden, simplemente debe invertir la lista devuelta por flush() antes de procesarla. Si no le importa el orden, simplemente puede recorrer la lista de inmediato para procesarlo.

Dos notas si saca sus propias funciones:

1) Si usted está en un sistema con pedidos de memoria débil (es decir, PowerPC), hay que poner una "liberación barrera de memoria" al principio del empuje() función y una "barrera de memoria aquire" al final de la función flush().

2) Puede simplificar y optimizar considerablemente las funciones porque el problema ABA con SLists ocurre durante la función pop(). No puede tener problemas ABA con un SList si solo usa push() y flush(). Esto significa que puede implementarlo como un único puntero muy similar al código sin bloqueo y no es necesario contar con un contador de secuencia de prevención de ABA.