| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
Public Member Functions | Static Public Attributes | Friends | List of all members
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 | ) |
| inline explicit

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 2STACK_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 2STACK_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