Очередь без блокировки - PullRequest
Новая
       38

Очередь без блокировки

1 голос
/ 22 мая 2011

enter image description here enter image description here

Также я делаю реализацию c и в настоящее время имею структуру очереди: 

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;
 }

Но не уверен, как продолжить, сфункции очереди и очереди ...

  • Как будет выглядеть код?

Ответы [ 4 ]

2 голосов
/ 22 мая 2011

, а также недавний разговор на эту тему: https://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

2 голосов
/ 22 мая 2011

Ваш псевдокод может (и, скорее всего, имеет) страдать от проблемы ABA , поскольку проверяется только указатель, а не сопровождающая уникальная печать, вы найдете эту статью использования в этом отношении и в качестве общего руководства по реализации очереди без блокировок, с ее подводными камнями.

При работе с программированием без блокировок также полезно прочитать работы Херба Саттера, а такжеОн дает хорошие, проницательные объяснения того, что требуется, почему это требуется и его потенциальные слабые места (хотя следует помнить, что некоторые из его более старых публикаций / статей, как было обнаружено, содержат некоторые скрытые / непредвиденные проблемы).

0 голосов
/ 04 сентября 2018

Вы можете попробовать эту библиотеку, она встроена в c native. lfqueue

Например 

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);
0 голосов
/ 22 мая 2011

(оставив это здесь пока, но см. Редактирование.)

Вы знаете реализацию очереди без блокировки в C?

Я недавно написал очередь без блокировки(http://www.ideone.com/l2QRp). На самом деле я не могу гарантировать, что он работает правильно, но я не могу найти каких-либо ошибок, и я использовал его в нескольких однопоточных программах без проблем, поэтому естьв этом нет ничего слишком очевидного.

Пример тривиального использования: 

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);

Редактировать:

Как указал @Alexey Kukanov, queue_pop может завершиться неудачей, если выскочить tmp, освобожден, выделен снова и снова помещен между проверкой на нулевое значение и обменом: 

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

Я пока не уверен, как это исправить, но я (надеюсь) обновлю это, как только выясню этоА пока не обращайте на это внимания.

...