package lockfree

  1. Overview
  2. Docs

Module Lockfree.Mpmc_relaxed_queueSource

A lock-free multi-producer, multi-consumer, thread-safe, 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 -

  • by using the fact that lock-freedom does not impose any constraints on partial methods. In simple words, an invocation of function that cannot logically terminate (`push` on full queue, `pop` on empty queue), it is allowed to *busy-wait* until the precondition is meet.

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.

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

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

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

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

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

Sourcemodule 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.