folly::EventCount

class EventCount;

Description

See http://www.1024cores.net/home/lock-free-algorithms/eventcounts for details.

Event counts allow you to convert a non-blocking lock-free / wait-free algorithm into a blocking one, by isolating the blocking logic. You call prepareWait() before checking your condition and then either cancelWait() or wait() depending on whether the condition was true. When another thread makes the condition true, it must call notify() / notifyAll() just like a regular condition variable.

If "<" denotes the happens-before relationship, consider 2 threads (T1 and T2) and 3 events:

• E1: T1 returns from prepareWait

• E2: T1 calls wait (obviously E1 < E2, intra-thread)

• E3: T2 calls notifyAll

If E1 < E3, then E2's wait will complete (and T1 will either wake up, or not block at all)

This means that you can use an EventCount in the following manner:

Waiter: if (!condition()) { // handle fast path first for (;;) { auto key = eventCount.prepareWait(); if (condition()) { eventCount.cancelWait(); break; } else { eventCount.wait(key); } } }

(This pattern is encapsulated in await())

Poster: make_condition_true(); eventCount.notifyAll();

Note that, just like with regular condition variables, the waiter needs to be tolerant of spurious wakeups and needs to recheck the condition after being woken up. Also, as there is no mutual exclusion implied, "checking" the condition likely means attempting an operation on an underlying data structure (push into a lock-free queue, etc) and returning true on success and false on failure.