docs/classtf_1_1NonblockingNotifier.html
class to create a non-blocking notifier
A non-blocking notifier enables threads to wait for user-defined predicates without blocking locks or protecting the predicate with a mutex. Conceptually, it is similar to a condition variable, but the wait predicate is evaluated optimistically and does not require mutual exclusion.
A waiting thread follows this pattern:
wid = this\_waiter\_id();if (predicate) {return act();}notifier.prepare\_wait(wid);// enter the two-phase wait protocolif (predicate) {notifier.cancel\_wait(wid);return act();}notifier.commit\_wait(&w);// park (e.g., preempted by OS until notified)
A notifying thread performs:
wid = this\_notifier\_id;predicate = true;notifier.notify\_one(wid);
The notify operation is inexpensive when no threads are waiting. The prepare_wait and commit_wait operations are more costly, but they are only executed when the initial predicate check fails. The flow diagram for notifier and waiter is shown below:
TwoPhaseProtocolcluster_waiterWaiting Thread (Consumer)cluster_notifierNotifier Thread (Producer)Start A worker thread (wid)wanting to wait Check1 PredicateTrue? Start->Check1End waiter queue Act1 act() Check1->Act1 Yes Prepare Phase 1: prepare_wait(wid) Check1->Prepare No Act1->StartCheck2 PredicateTrue? Prepare->Check2Cancel cancel_wait(wid) Check2->Cancel YesCommit Phase 2: commit_wait(wid) Check2->Commit No Act2 act() Cancel->Act2Act2->StartCommit->EndNotifier A worker thread (wid)wanting to notify ModifyPredicatePredicate = TrueNotifier->ModifyPredicateNotify notify_one(wid)ornotify_all(wid)ModifyPredicate->Notify
The synchronization algorithm relies on two shared variables: a user-defined predicate and an internal state variable. To avoid lost wake-ups, the protocol follows a two-phase update-then-check pattern. A waiting thread publishes its intent to wait by updating the state before rechecking the predicate. Conversely, a notifying thread updates the predicate before inspecting the state. This interaction is governed by a memory barrier of sequential consistency that guarantees at least one thread will observe the other's progress. Consequently, the waiter either detects the work and stays active, or the notifier detects the waiter and issues a wakeup. It is impossible for both threads to miss each other's updates.
The state has the following layout, which consists of the following three parts:
STACK_BITS is a stack of committed waitersPREWAITER_BITS is the count of waiters in the pre-waiting stageEPOCH_BITS is the modification counterBitStateLayoutState64Epoch (32 bits)[EPOCH_BITS]Shift: 32Mask: EPOCH_MASKInc: EPOCH_INCPre-waiter Count (16 bits)[PREWAITER_BITS]Shift: 16Mask: PREWAITER_MASKInc: PREWAITER_INCPre-waiter Stack (16 bits)[STACK_BITS]Mask: STACK_MASKEpochRangeBits [63:32]Modification counterEpochRange->State64:b63_32PrewaiterRangeBits [31:16]Pre-waiter ticket countPrewaiterRange->State64:b31_16StackRangeBits [15:0]Committed waiter stack indexStackRange->State64:b15_0
Reference: https://gitlab.com/libeigen/eigen/-/blob/master/Eigen/src/ThreadPool/EventCount.h
static const uint64_t STACK_BITSNumber of bits used to encode the waiter stack index. static const uint64_t STACK_MASKBit mask for extracting the waiter stack index. static const uint64_t PREWAITER_BITSNumber of bits used to encode the pre-waiter ticket. static const uint64_t PREWAITER_SHIFTBit shift of the pre-waiter ticket field. static const uint64_t PREWAITER_MASKBit mask for extracting the pre-waiter ticket field. static const uint64_t PREWAITER_INCIncrement value for advancing the pre-waiter ticket. static const uint64_t EPOCH_BITSNumber of bits used to encode the epoch counter. static const uint64_t EPOCH_SHIFTBit shift of the epoch field. static const uint64_t EPOCH_MASKBit mask for extracting the epoch field. static const uint64_t EPOCH_INCIncrement value for advancing the epoch counter.
NonblockingNotifier(size_t N) explicit constructs a notifier with N waiters~NonblockingNotifier()destructs the notifier
auto num_waiters() const -> size_treturns the number of committed waitersauto capacity() const -> size_treturns the maximum number of waiters supported by this notifiervoid prepare_wait(size_t wid)prepares the calling thread to enter the waiting setvoid commit_wait(size_t wid)commits a previously prepared wait operationvoid cancel_wait(size_t wid)cancels a previously prepared wait operationvoid notify_one()notifies one waiter from the waiting setvoid notify_all()notifies all waiter from the waiting setvoid notify_n(size_t N)notifies up to N waiters from the waiting setauto size() const -> size_treturns the number of waiters supported by this notifier
constructs a notifier with N waiters
| Parameters |
|---|
| N |
Constructs a notifier that supports up to N waiters. The maximum allowable number of waiters can be acquired by calling capacity(), which is equal to 2STACK_BITS.
returns the number of committed waiters
| Returns | the number of committed waiters at the time of the call. |
A committed waiter is a thread that has completed the pre-waiting stage and is fully registered in the waiting set via commit_wait().
returns the maximum number of waiters supported by this notifier
The maximum number of waiters supported by this non-blocking notifier is equal to 2STACK_BITS.
prepares the calling thread to enter the waiting set
| Parameters |
|---|
| wid |
This function places the thread into the pre-waiting stage. After calling prepare_wait(), the thread must re-check the wait predicate and then complete the protocol by calling either commit_wait() or cancel_wait() with the same waiter identifier.
A thread in the pre-waiting stage is not yet considered a committed waiter, and its waiting status is considered incomplete. Failing to follow prepare_wait() with exactly one call to commit_wait() or cancel_wait() results in undefined behavior.
commits a previously prepared wait operation
| Parameters |
|---|
| wid |
This function completes the waiting protocol for a thread that has previously called prepare_wait(). Upon successful completion, the thread becomes a committed waiter and will park until being notified.
The thread must have re-checked the wait predicate before calling commit_wait(). Once committed, the thread may be awakened by notify_one(), notify_n(), or notify_all().
Each call to prepare_wait() must be followed by exactly one call to either commit_wait() or cancel_wait() using the same thread identifier.
cancels a previously prepared wait operation
| Parameters |
|---|
| wid |
This function aborts the waiting protocol for a thread that has previously called prepare_wait(). After cancellation, the thread does not become a committed waiter and will return to user-side control.
cancel_wait() must be called after the wait predicate has been re-checked and found to be false. This allows a thread to safely abandon waiting without blocking or being notified.
Each call to prepare_wait() must be followed by exactly one call to either commit_wait() or cancel_wait() using the same thread identifier.
notifies one waiter from the waiting set
Wakes up one waiter from the waiting set, including those in the pre-waiting stage.
The function is cheap when no threads are waiting.
notifies all waiter from the waiting set
Wakes up all waiters from the waiting set, including those in the pre-waiting stage.
The function is cheap when no threads are waiting.
notifies up to N waiters from the waiting set
| Parameters |
|---|
| N |
Wakes up at most N waiters from the waiting set. If N is greater than or equal to the maximum number of waiters in this notifier, this function behaves identically to notify_all().
The function is cheap when no threads are waiting.
returns the number of waiters supported by this notifier
| Returns | the number of waiters supported by this notifier |
The size of a notifier is equal to the number used to construct that notifier.