Search code examples
messagelock-free

Is multiple-producer, single-consumer possible in a lockfree setting?

I have a bunch of threads that are doing lots of communication with each other. I would prefer this be lock free.

For each thread, I want to have a mailbox, where other threads can send it messages, (but only the owner can remove messages). This is a multiple-producer single-consumer situation. is it possible for me to do this in a lockfree / high performance matter? (This is in the inner loop of a gigantic simulation.)

Solution

  • Sure, if you have an atomic CompareAndSwap instruction:

    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;

    After reading a message, the consuming thread just sets mailbox[i].ready = false; mailbox[i].owned = false; (in that order).