Module Saturn.Relaxed_queue

A multi-producer, multi-consumer, thread-safe, bounded relaxed-FIFO queue.

It exposes two interfaces: Spin and Not_lockfree. Spin is lock-free formally, but the property is achieved in a fairly counterintuitive way -

Above interface is impractical outside specialized applications. Thus, Mpmc_relaxed_queue also exposes Not_lockfree interface. Not_lockfree contains non-lockfree paths. While formally a locked algorithm, it will often be the more practical solution as it allows having an overflow queue, etc.

type 'a t = private {
  1. array : 'a Stdlib.Option.t Stdlib.Atomic.t Stdlib.Array.t;
  2. head : int Stdlib.Atomic.t;
  3. tail : int Stdlib.Atomic.t;
  4. mask : int;

A queue of items of type 'a. Implementation exposed for testing.

val create : size_exponent:int -> unit -> 'a t

create ~size_exponent:int creates an empty queue of size 2^size_exponent.

module Spin : sig ... end

Spin exposes a formally lock-free interface as per the A lock-free relaxed concurrent queue for fast work distribution paper. Functions here busy-wait if the action cannot be completed (i.e. push on full queue, pop on empty queue).

module Not_lockfree : sig ... end

Non_lockfree exposes an interface that contains non-lockfree paths, i.e. threads may need to cooperate to terminate. It is often more practical than Spin, in particular when using a fair OS scheduler.