código C de la cola de

Question

sin bloqueo Cómo podría implementar este pseudocódigo cola sin bloqueo en C?

ENQUEUE(x) 
    q ← new record 
    q^.value ← x 
    q^.next ← NULL 
    repeat 
     p ← tail 
     succ ← COMPARE&SWAP(p^.next, NULL, q) 
     if succ ≠ TRUE 
      COMPARE&SWAP(tail, p, p^.next) 
    until succ = TRUE 
    COMPARE&SWAP(tail,p,q) 
end 

DEQUEUE() 
    repeat 
     p ← head 
     if p^.next = NULL 
      error queue empty 
    until COMPARE&SWAP(head, p, p^.next) 
    return p^.next^.value 
end 

¿Cómo se utiliza la Built-in functions for atomic memory access

__sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...) 

Actualmente tengo

typedef struct queueelem { 
    queuedata_t data; 
    struct queueelem *next; 
} queueelem_t; 

typedef struct queue { 
    int capacity; 
    int size; 
    queueelem_t *head; 
    queueelem_t *tail; 
} queue_t; 

queue_t * 
queue_init(int capacity) 
{ 
    queue_t *q = (queue_t *) malloc(sizeof(queue_t)); 
    q->head = q->tail = NULL; 
    q->size = 0; 
    q->capacity = capacity; 
    return q; 
} 

Answer 1

http://www.liblfds.org

de dominio público, sin licencia, la implementación de algoritmos portátil sin bloqueo en C.

construye fuera de la caja para Windows y Linux.

Usa GCC en Linux, por lo que usa los intrínsecos (bueno, aparte de CAS de 128 bit, no hay un ensamblaje en línea de uso intrínseco para eso).

Contiene la cola S M &.Eche un vistazo al código fuente y vea cómo se hace.

Answer 2

Aunque no es exactamente C, echa un vistazo a la biblioteca proposed Boost.Lockfree. Las partes internas son bastante fáciles de asimilar y podrían transferirse a C, o, por el contrario, podría envolver Boost.Lockfree en una API C y usar eso.

De manera similar, Boostcon 2010 tuvo mucha discusión sobre la programación de bloqueo y STM que vale la pena mirar si le interesa este tema. No puedo encontrar un enlace a los videos, pero valió la pena ver las conversaciones de Intel, IBM y AMD, ya que están lidiando con STM en el nivel de la CPU.

Answer 3

Suena como lo que quiere que se llama un bloqueo de cola de MCS (aunque engañosamente llamada, es realmente lock-libre, no espere libre), y hay algunas buenas pseudo-código disponible aquí: http://www.cs.rochester.edu/research/synchronization/pseudocode/ss.html#mcs

Answer 4

Si su objetivo es el código de producción, simplemente no haga eso; usa bloqueos

En your previous question, usted tiene suficiente información para explicar por qué. Corregir las implementaciones sin bloqueo incluso de estructuras de datos simples como cola y pila en ausencia de recolector de basura son engañosas y sofisticadas debido a the (in)famous ABA problem. Lamentablemente, algunos documentos de investigación no tienen en cuenta a ABA por las razones que sean; su pseudocódigo parece tomado de uno de esos documentos. Si lo traduce a C y utiliza la memoria asignada de montón para los nodos, causará errores indeterministas si se usa en código real.

Si usted está haciendo esto para ganar experiencia, entonces no se esperaba tan semejantes a solucionarlo para usted. Debes leer todos los materiales citados y mucho más, asegúrate de comprender todos los matices de los algoritmos sin bloqueo como ABA, estudiar diversas técnicas para abordar el problema, estudiar implementaciones existentes sin cerrojo, etc.

finalmente, poca orientación para la traducción de la pseudo-código dado en C:

q^.value ← x significa q_elem->data = x;
repeat ... until COMPARE&SWAP(head, p, p^.next) es equivalente a do {...} while (!__sync_bool_compare_and_swap(q_obj->head, q_elem, q_elem->next);

donde q_obj es una instancia de tipo queue_t (es decir, una cola) y q_elem es una instancia del tipo queueelem_t (es decir un nodo de cola).

Answer 5

Uso C para escribir una implementación de la cola de bloqueo sin errores.

lfq.

Es compatible con muchos productores, muchos consumidores.

Utilice el indicador de compilación -O0 para evitar la optimización de gcc.