CODEWITHSUNDEEP
cqueuelock-free
edgarmtze
edgarmtze

Reputation: 25058

Lock-free queue

enter image description here enter image description here

Also I am doing a c implementation and currently have the structure of the 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;
 }

But not sure How to continue, with queue and dequeue functions...

Upvotes: 3

Views: 8474

Answers (5)

bittnkr
bittnkr

Reputation: 99

Sometime ago, I've found a nice solution to this problem. I believe that it the smallest found so far.

The repository has a example of how use it to create N threads (readers and writers) and make then share a single seat.

I made some benchmarks, on the test example and got the following results (in million ops/sec) :

By buffer size

throughput

By number of threads

enter image description here

Notice how the number of threads do not change the throughput.

I think this is the ultimate solution to this problem. It works and is incredible fast and simple. Even with hundreds of threads and a queue of a single position. It can be used as a pipeline beween threads, allocating space inside the queue.

The repository has some early versions written in C# and pascal. Im working to make something more complete polished to show its real powers.

I hope some of you can validate the work or help with some ideas. Or at least, can you break it?

Upvotes: 3

Oktaheta
Oktaheta

Reputation: 626

You may try this library it is built in c native. lfqueue

For Example

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

Upvotes: 0

David X
David X

Reputation: 4176

(Leaving this here for now, but see edit.)

Do you know a implementation of lock free queue in C?

I wrote lockless queue recently (http://www.ideone.com/l2QRp). I can't actually guarantee it works correctly, but I can't find any bugs and I've used it in a couple of single threaded programs without any problems, so there's nothing too obvious wrong with it.

Trivial usage example:

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

Edit:

As @Alexey Kukanov pointed out, queue_pop can fail if tmp is popped,freed,allocated again, and put again between checking for null and swapping:

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

I'm not yet sure how to fix this, but I'll (hopefully) update this once I figure it out. For now, disregard this.

Upvotes: 0

Joel Falcou
Joel Falcou

Reputation: 6357

and also the recent boost'con talk about this subject : https://github.com/boostcon/2011_presentations/raw/master/wed/lockfree_2011_slides.pdf

Upvotes: 2

Necrolis
Necrolis

Reputation: 26181

Your pseudo-code can (and most likely does) suffer from the ABA problem, as only the pointer is checked, and not an accompanying unique stamp, you'll find this paper of use in that regard and as a general guide to lock-free queue implementation, with its pitfalls.

When dealing with lock free programing, its also a good idea to read up on Herb Sutter's works, as He gives good, insightful explanations to whats required, why its required and its potential weak points (though beware that some of his older publications/articles where found to contain some hidden/unforseen problems).

Upvotes: 2

Related Questions