[ACCEPTED]-Is multiple-producer, single-consumer possible in a lockfree setting?-lock-free

Accepted answer

Score: 10

Lock-free Multiple Producer Single Consumer 33 (MPSC) Queue is one of the easiest lock-free 32 algorithms to implement.

The most basic implementation 31 requires a simple lock-free singly-linked 30 list (SList) with only push() and flush(). The 29 functions are available in the Windows API 28 as InterlockedFlushSList() and InterlockedPushEntrySList() but 27 these are very easy to roll on your own.

Multiple 26 Producer push() items onto the SList using 25 a CAS (interlocked compare-and-swap).

The 24 Single Consumer does a flush() which swaps 23 the head of the SList with a NULL using 22 an XCHG (interlocked exchange). The Consumer 21 then has a list of items in the reverse-order.

To 20 process the items in order, you must simply 19 reverse the list returned from flush() before 18 processing it. If you do not care about 17 order, you can simply walk the list immediately 16 to process it.

Two notes if you roll your 15 own functions:

1) If you are on a system 14 with weak memory ordering (i.e. PowerPC), you 13 need to put a "release memory barrier" at 12 the beginning of the push() function and 11 an "aquire memory barrier" at the end of 10 the flush() function.

2) You can make the 9 functions considerably simplified and optimized 8 because the ABA-issue with SLists occur 7 during the pop() function. You can not 6 have ABA-issues with a SList if you use 5 only push() and flush(). This means you 4 can implement it as a single pointer very 3 similar to the non-lockfree code and there 2 is no need for an ABA-prevention sequence 1 counter.

Score: 3

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 2 reading a message, the consuming thread 1 just sets mailbox[i].ready = false; mailbox[i].owned = false; (in that order).

Score: 2

Here's a paper from the University of Rochester illustrating a non-blocking concurrent queue. The algorithm described in the 2 paper shows one technique for making a lockless 1 queue.

Score: 0

may want to look at Intel thread building 3 blocks, I recall being to lecture by Intel 2 developer that mentioned something along 1 those lines.

Source: stackoverflow.com

[ACCEPTED]-Is multiple-producer, single-consumer possible in a lockfree setting?-lock-free

Shared-memory IPC synchronization (lock-free)

In what circumstances lock free data structures are faster than lock based ones?

Lock Free Queue -- Single Producer, Multiple Consumers

Do lock-free algorithms really perform better than their lock-full counterparts?

C code of lock-free queue

boost c++ lock-free queue vs shared queue

Message Design Patterns

Use spring:message from JavaScript

SVN commit with a newline in message

git filter-branch --msg-filter to reword a pushed commit message