folly::StripedThrottledLifoSem

Declared in <folly/synchronization/StripedThrottledLifoSem.h>

post() accepts an arbitrary stripe identifier; waits can consume posts from any stripe, and return the stripe identifier that was passed to the corresponding post().

Waits specify a preferred stripe: posts from that stripe will be consumed before posts from other stripes.

In other words, this behaves like an array of semaphores where posts are done on a specific entry while waits wait for any semaphore in the array, and return the entry from which the post was consumed.

This can be used to implement queues sharded by some notion of stripe, for example based on CPU cache topology.

Cross‐stripe handoffs are best‐effort, but not guaranteed: it is possible to have a stable state where there are both nonzero readers and positive value. This is because of a race in wait functions when trying to steal posts from other slices. For example, consider the situation where there are 2 stripes, both with no posts and no waiters. Then two threads perform concurrent post()/wait():

Thread 0 Thread 1 ‐‐‐‐‐‐‐‐ ‐‐‐‐‐‐‐‐ wait(0): try_wait on all stripes (fails) post(1): try_post on all stripes (fails) post on stripe 1 wait on stripe 0

In this case, the waiter on thread 0 will not wake up even though there is an available post on stripe 1, until some other operation unblocks this.

This implies that if this semaphore is used to control the queue of an executor, the executor is not technically work‐conserving. However, forward progress will happen as long as at least one thread eventually waits on each stripe, and if the executor has a steady submission rate such imbalanced states should only persist for very short time. This can be mitigated unconditionally by subscribing the semaphore to StripedThrottledLifoSemBalancer, which will periodically correct imbalances.

StripedThrottledLifoSem optionally supports storing a per‐stripe payload that is colocated with the semaphore state of the stripe, which can be useful to ensure that they share the cache line. The payload is initialized with the payloadArgs tuple passed to the constructor.

Created with MrDocs