File d’attente sans locking

entrez la description de l'image icientrez la description de l'image ici

De plus, je fais une implémentation c et ai actuellement la structure de la queue:

 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; } int CompareAndExchange (void **a, void *comparand,void *new) { int success = 0; pthread_mutex_lock(&CE_MUTEX); if ((*a) != comparand) { (*a) = new; //return TRUE success = 1; } pthread_mutex_unlock(&CE_MUTEX); //return FALSE return success; } 

Mais vous ne savez pas comment continuer, avec les fonctions de queue et de retrait de la queue …

  • A quoi ressemblerait le code?

Votre pseudo-code peut (et très probablement, souffrir) du problème ABA , car seul le pointeur est vérifié, et non un tampon unique, vous trouverez ce document utile à cet égard et comme guide général pour le locking. mise en œuvre de la queue libre, avec ses pièges

Quand il s’agit de programmation sans locking, c’est aussi une bonne idée de lire les œuvres de Herb Sutter, car il donne de bonnes explications perspicaces sur ce qui est demandé, pourquoi il en a besoin et ses points faibles potentiels (mais méfiez-vous des contient des problèmes cachés / imprévus).

et aussi le récent discours de boost’con sur ce sujet: https://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

(Laissant ceci ici pour l’instant, mais voir edit.)

Connaissez-vous une implémentation de la queue sans locking en C?

J’ai récemment écrit une queue sans locking ( http://www.ideone.com/l2QRp ). Je ne peux pas réellement garantir que cela fonctionne correctement, mais je ne trouve aucun bogue et je l’ai utilisé dans quelques programmes à un seul thread sans aucun problème, donc il n’y a rien de trop évident.

Exemple d’utilisation sortingvial:

 queue_t queue; int val = 42; queue_init(&queue,sizeof val); queue_put(&queue,&val); val = 0; queue_pop(&queue,&val); printf("%i\n",val); // 42 queue_destroy(&queue); 

Modifier:

Comme @Alexey Kukanov l’a souligné, queue_pop peut échouer si tmp est éjecté, libéré, alloué à nouveau et remis entre la vérification de la valeur NULL et la permutation:

  if(!tmp->next) return errno = ENODATA; /* can fail here */ } while(!sync_swap(q->head,tmp,tmp->next)); 

Je ne sais pas encore comment résoudre ce problème, mais j’espère le mettre à jour dès que j’aurai compris. Pour l’instant, ignorez cela.

Vous pouvez essayer cette bibliothèque, elle est construite en c native. queue

Par exemple

 int* int_data; lfqueue_t my_queue; if (lfqueue_init(&my_queue) == -1) return -1; /** Wrap This scope in other threads **/ int_data = (int*) malloc(sizeof(int)); assert(int_data != NULL); *int_data = i++; /*Enqueue*/ while (lfqueue_enq(&my_queue, int_data) == -1) { printf("ENQ Full ?\n"); } /** Wrap This scope in other threads **/ /*Dequeue*/ while ( (int_data = lfqueue_deq(&my_queue)) == NULL) { printf("DEQ EMPTY ..\n"); } // printf("%d\n", *(int*) int_data ); free(int_data); /** End **/ lfqueue_destroy(&my_queue);