package lockfree

You can search for identifiers within the package.

in-package search v0.2.0

lockfree
- Lockfree
  - Backoff
  - Michael_scott_queue
  - Mpmc_relaxed_queue
    
    Not_lockfree
    
    CAS_interface
    
    Spin
  - Mpsc_queue
  - Spsc_queue
  - Treiber_stack
  - Ws_deque
    
    M
    
    S

Legend:
Library
Module
Module type
Parameter
Class
Class type

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.

type 'a t = private {

array : 'a Stdlib.Option.t Stdlib.Atomic.t Stdlib.Array.t;
head : int Stdlib.Atomic.t;
tail : int Stdlib.Atomic.t;
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.