Lock free many-producer/single-consumer patterns: A work queue where the last one wins


Continuing our miniseries on lock-free many-producer/single-consumer patterns, we're going to look at the case where you have a work queue where there can be multiple work items, but each work item replaces the previous one.

You see this pattern when the work is something like Update. If you update with one set of data, and then update with a second set of data, then the second set of data overwrites the first set; you may as well not have bothered with the first one.

This is similar to our previous case, except that this time the tasks are not identical, so we can't just use a flag. But that's okay. We can use the data itself as the flag!

Data* PendingData;

void RequestUpdate(Data* data)
{
 Data* previousData =
    InterlockedExchangePointer(&PendingData, data);
 if (previousData == nullptr) {
  // You provide the WakeConsumer() function.
  WakeConsumer();
 } else {
  delete previousData;
 }
}

// You call this function when the consumer receives the
// signal raised by WakeConsumer().
void ConsumeUpdate()
{
 Data* currentData;
 while ((currentData = InterlockedExchangePointer(&PendingData,
                                          nullptr)) != nullptr) {
  Update(currentData);
  delete currentData;
 }
}

This is similar to the previous case, except that we're using a pointer instead of a flag. Again, we wake the consumer only on the transition from null to non-null. There is an extra wrinkle in that we need to delete the previous data if our update replaced a pending update that hasn't yet begun processing.

The idea here is that the PendingData variable contains the data that is being transferred from the producer to the consumer. The consumer goes into a loop checking if there is any pending data, and if so, udpating with it. If the producer can replace the data before the consumer sees it, then the producer has basically saved the consumer the work of updating with data that is already stale.

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

That was a little trickier. Maybe we'll take a break and do something slightly less tricky next time.

Comments (9)
  1. Brian_EE says:

    Not criticizing the content of the article, but just to point out that this technique of course assumes that the new data completely overwrites the previous data. For example: What if the consumer is updating a record in a database? Perhaps the first data is updating the value in column 2 and the 2nd data wants to update the value in column 4?

    1. Cullen says:

      @Brian_EE: It’s not assuming that each piece of data replaces the previous one. the article specifically states that, in the opening paragraph.

      “where there can be multiple work items, but each work item replaces the previous one”

      1. Brian_EE says:

        You are correct. I missed that he explicitly stated that. I’m blaming the fog caused by the cold/flu medicines…. (Yay, winter.)

  2. pc says:

    Typo: “udpating”

  3. Ben Voigt (Visual Studio and Development Technologies MVP with C++ focus) says:

    It should be pointed out that this algorithm is not lock-free unless you have a lock-free implementation of `Data::operator delete()`

    1. Kevin says:

      Taking a lock in a destructor is incredibly poor form.

      1. Ben Voigt (Visual Studio and Development Technologies MVP with C++ focus) says:

        Kevin, it’s not the destructor (which would be `Data::~Data()`, but `operator delete()`, the deallocation function which is the second behavior of using the C++ `delete` operator. Deallocation functions working on shared heaps (and Raymond’s code doesn’t respect thread affinity of allocations, so his allocator must be free-threaded) very often take a lock.

        1. Would you be happier if RequestUpdate merely returned a bool saying whether or not the caller should delete the pointer? The point is that the communication channel does not introduce a lock between the producers and the consumer. If there’s another lock somewhere else, well, that’s a different problem. (After all, Update() itself may take a lock.)

          1. Joshua says:

            Well I guess it depends on what you are using lock-free for. Reducing the size of your lock graph is a valid reason as you suggested.

Comments are closed.

Skip to main content