Lock free many-producer/single-consumer patterns: A work queue with task coalescing


Today we're going to implement a very simple producer/consumer pattern: There are many producers who are producing work, and a single consumer who processes the work. The work is all identical, and it is idempotent. That means that doing the work twice is the same as doing it once.

You see this pattern when the work is something like Refresh. Refreshing once is the same as refreshing twice, as long as the single refresh is the last one.

The naïve way of doing this is to avoid the coalescing at all and have each refresh request notify the consumer to perform a refresh. This means, however, that if a thousand refresh requests come in rapid succession, the consumer thread will perform a thousand refreshes, nearly all of which were unnecessary.

A less naïve solution is to have a flag that says whether a refresh was requested. The first person to request a refresh wakes up the consumer. The second and subsequent people to request a refresh merely reminds the consumer that another refresh request arrived. When the consumer wakes up, it performs an atomic test-and-reset of the flag. If set, then it performs a refresh, and then it goes back and performs another test-and-reset of the flag to see whether a refresh request arrived while the previous one was in progress.

LONG RefreshRequested;

void RequestRefresh()
{
 if (!InterlockedExchange(&RefreshRequested, TRUE)) {
  // You provide the WakeConsumer() function.
  WakeConsumer();
 }
}

// You call this function when the consumer receives the
// signal raised by WakeConsumer().
void ConsumeRefresh()
{
 while (InterlockedExchange(&RefreshRequested, FALSE)) {
  Refresh();
 }
}

Note that we wake the consumer only on the transition from FALSE to TRUE. (In the lingo, the consumer is edge-triggered rather than level-triggered.) This reduces traffic between the two threads, which is important if your communication channel is something like Post­Message, because you don't want to spam the message queue with 10,000 identical messages. Not only does this cause Consume­Refresh to run 9,999 times more than necessary, but you run the risk of overflowing your message queue.

Remember, there is only one consumer, so if Wake­Consumer is called while Consume­Refresh is still running, the wake will not start a new consumer immediately. It will wait for the existing Consume­Refresh to complete before starting a new Consume­Refresh.

Okay, that scenario was easy. We're still warming up. More next time.

Comments (7)
  1. Neil says:

    OK, I'll bite; I can't see the point of the double test. In fact, I wouldn't even test the flag at wake up, since only a new refresh could cause a wake. The flag then remains set until the refresh completes, and only then would I reset it. (There's also probably a good reason why I'd still have to reset it atomically, but I'd have to go back and reread your previous posts to remind myself why.)

    1. Not sure where there is a double test. Each function has only one test. And in the consumer, if you test at the end of the loop instead of the beginning, you end up performing two refreshes in response to a single refresh request.

      1. Neil says:

        "If set, then it performs a refresh, and then it goes back and performs another test-and-reset of the flag to see whether a refresh request arrived while the previous one was in progress" is what I meant by double test. And in my mind, the consumer needs no tests at all, since the wake counts as the test. But the real answer to my question turns out to be that this is the base case of the pattern since otherwise the derived cases wouldn't make sense. (Where's that time machine when you need it?)

        1. Ah, I see. Yes, the next Wake will kick the consumer. The idea here is that since the Refresh code is now in cache, you may as well opportunistically do more updates while the going is still cheap. And, as you noted, it's a base case for future exploration where looping back may be non-optional. (The extra test is there in case there are spurious wakes. A number of synchronization primitives allow spurious wakes, so we may as well protect against them.)

          1. Neil says:

            Ah, spurious wakes and opportunistic refreshes, that makes much more sense now, thanks!

  2. Jan Ringoš says:

    In this case I'd probably just use SetEvent, although it's likely not as efficient.

  3. Kasper says:

    I once measured the speed of the lock construct. It's surprisingly fast and less confusing to the eye. See the measurements here http://firstclassthoughts.co.uk/Articles/Programming/DotNetLocksAreReallyFast.html

Comments are closed.

Skip to main content