Class: AtomicRuby::AtomicQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/atomic-ruby/atomic_queue.rb,
sig/generated/atomic-ruby/atomic_queue.rbs,
ext/atomic_ruby/atomic_ruby.c

Overview

Note:

This class is NOT Ractor-safe as it stores mutable references to queued values that cannot be safely shared across ractors.

Provides a lock-free FIFO queue using atomic operations.

AtomicQueue is a multi-producer, multi-consumer queue backed by a singly-linked list of nodes with atomic head and tail pointers. Enqueueing and dequeueing use compare-and-swap operations so concurrent producers and consumers never block one another.

The queue is implemented as a Michael-Scott lock-free FIFO with a dummy sentinel node. Both #push and #pop are O(1). Nodes are Ruby-managed values, so the garbage collector reclaims dequeued nodes once no thread holds a reference to them.

Examples:

Basic usage

queue = AtomicQueue.new
queue.push(1)
queue.push(2)
puts queue.pop #=> 1
puts queue.pop #=> 2
puts queue.pop #=> nil

Producer/consumer coordination

queue = AtomicQueue.new
producers = 4.times.map do
  Thread.new { 100.times { |index| queue.push(index) } }
end
producers.each(&:join)
puts queue.size #=> 400

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ AtomicQueue

Creates a new empty queue.

Examples:

queue = AtomicQueue.new


44
45
46
 
# File 'lib/atomic-ruby/atomic_queue.rb', line 44

def initialize
  _initialize
end

Instance Method Details

#empty? ⇒ true, false

Returns true when the queue is empty.

This operation is atomic and thread-safe. The returned value reflects the state at the time of the call, but may change immediately after in concurrent environments.

Examples:

queue = AtomicQueue.new
puts queue.empty? #=> true
queue.push(1)
puts queue.empty? #=> false

Returns:

  • (true, false) —

    true when the queue has no values



131
132
133
 
# File 'lib/atomic-ruby/atomic_queue.rb', line 131

def empty?
  _empty_p
end

#pop ⇒ untyped?

Dequeues the value at the head of the queue, or returns nil when the queue is empty.

This operation is atomic and thread-safe. Multiple threads may pop concurrently without blocking one another.

Examples:

queue = AtomicQueue.new
queue.push(1)
queue.push(2)
puts queue.pop #=> 1
puts queue.pop #=> 2
puts queue.pop #=> nil

Returns:

  • (untyped, nil) —

    The dequeued value, or nil when the queue is empty



89
90
91
 
# File 'lib/atomic-ruby/atomic_queue.rb', line 89

def pop
  _pop
end

#push(value) ⇒ self Also known as: <<

Enqueues a value at the tail of the queue.

This operation is atomic and thread-safe. Multiple threads may push concurrently without blocking one another.

Examples:

queue = AtomicQueue.new
queue.push(1)
queue.push("two")
queue.push(nil)
puts queue.size #=> 3

Parameters:

  • value (untyped) —

    The value to enqueue

Returns:

  • (self) 


64
65
66
 
# File 'lib/atomic-ruby/atomic_queue.rb', line 64

def push(value)
  _push(value)
end

#size ⇒ Integer Also known as: length

Returns the number of values currently queued.

This operation is atomic and thread-safe. The returned value reflects the state at the time of the call, but may change immediately after in concurrent environments.

Examples:

queue = AtomicQueue.new
queue.push(1)
queue.push(2)
puts queue.size #=> 2

Returns:

  • (Integer) —

    The number of queued values



108
109
110
 
# File 'lib/atomic-ruby/atomic_queue.rb', line 108

def size
  _size
end