tf::NonblockingNotifier Class Reference

class to create a non-blocking notifier More...

#include <taskflow/core/nonblocking_notifier.hpp>

Public Member Functions
	NonblockingNotifier (size_t N)
	constructs a notifier with N waiters
	~NonblockingNotifier ()
	destructs the notifier
size_t	num_waiters () const
	returns the number of committed waiters
size_t	capacity () const
	returns the maximum number of waiters supported by this notifier
void	prepare_wait (size_t wid)
	prepares the calling thread to enter the waiting set
void	commit_wait (size_t wid)
	commits a previously prepared wait operation
void	cancel_wait (size_t wid)
	cancels a previously prepared wait operation
void	notify_one ()
	notifies one waiter from the waiting set
void	notify_all ()
	notifies all waiter from the waiting set
void	notify_n (size_t N)
	notifies up to N waiters from the waiting set
size_t	size () const
	returns the number of waiters supported by this notifier

Static Public Attributes
static const uint64_t	STACK_BITS = 16
	Number of bits used to encode the waiter stack index.
static const uint64_t	STACK_MASK = (1ull << STACK_BITS) - 1
	Bit mask for extracting the waiter stack index.
static const uint64_t	PREWAITER_BITS = 16
	Number of bits used to encode the pre-waiter ticket.
static const uint64_t	PREWAITER_SHIFT = 16
	Bit shift of the pre-waiter ticket field.
static const uint64_t	PREWAITER_MASK = ((1ull << PREWAITER_BITS) - 1) << PREWAITER_SHIFT
	Bit mask for extracting the pre-waiter ticket field.
static const uint64_t	PREWAITER_INC = 1ull << PREWAITER_BITS
	Increment value for advancing the pre-waiter ticket.
static const uint64_t	EPOCH_BITS = 32
	Number of bits used to encode the epoch counter.
static const uint64_t	EPOCH_SHIFT = 32
	Bit shift of the epoch field.
static const uint64_t	EPOCH_MASK = ((1ull << EPOCH_BITS) - 1) << EPOCH_SHIFT
	Bit mask for extracting the epoch field.
static const uint64_t	EPOCH_INC = 1ull << EPOCH_SHIFT
	Increment value for advancing the epoch counter.

Friends
class	Executor

Detailed Description

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 protocol
if (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:

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 waiters
• PREWAITER_BITS is the count of waiters in the pre-waiting stage
• EPOCH_BITS is the modification counter

Reference: https://gitlab.com/libeigen/eigen/-/blob/master/Eigen/src/ThreadPool/EventCount.h

Constructor & Destructor Documentation

NonblockingNotifier()

tf::NonblockingNotifier::NonblockingNotifier ( size_t N )

inlineexplicit

constructs a notifier with N waiters

Parameters

N	number of waiters

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 2^STACK_BITS.

Member Function Documentation

cancel_wait()

void tf::NonblockingNotifier::cancel_wait ( size_t wid )

inline

cancels a previously prepared wait operation

Parameters

wid	identifier of the calling thread in the range of [0, N), where N represents the number of waiters used to construct this notifier

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.

capacity()

size_t tf::NonblockingNotifier::capacity ( ) const

inline

returns the maximum number of waiters supported by this notifier

The maximum number of waiters supported by this non-blocking notifier is equal to 2^STACK_BITS.

commit_wait()

void tf::NonblockingNotifier::commit_wait ( size_t wid )

inline

commits a previously prepared wait operation

Parameters

wid	identifier of the calling thread in the range of [0, N), where N represents the number of waiters used to construct this notifier

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.

notify_all()

void tf::NonblockingNotifier::notify_all ( )

inline

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.

notify_n()

void tf::NonblockingNotifier::notify_n ( size_t N )

inline

notifies up to N waiters from the waiting set

Parameters

N	maximum number of waiters to notify

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.

notify_one()

void tf::NonblockingNotifier::notify_one ( )

inline

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.

num_waiters()

size_t tf::NonblockingNotifier::num_waiters ( ) const

inline

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().

prepare_wait()

void tf::NonblockingNotifier::prepare_wait ( size_t wid )

inline

prepares the calling thread to enter the waiting set

Parameters

wid	identifier of the calling thread in the range of [0, N), where N represents the number of waiters used to construct this notifier

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.

size()

size_t tf::NonblockingNotifier::size ( ) const

inline

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.

---

The documentation for this class was generated from the following file:

• taskflow/core/nonblocking_notifier.hpp