Semaphores

A synchronization primitive that controls access to shared resources through a counter mechanism, preventing race conditions in concurrent programs.

Overview

Semaphores are synchronization primitives that manage access to shared resources in concurrent systems. Edsger Dijkstra introduced semaphores in 1965 as a solution to critical section problems in operating systems. A semaphore maintains an integer counter that represents the number of available resource units and provides atomic operations to increment or decrement this counter.

The semaphore mechanism operates on two fundamental operations: wait (P operation, from Dutch "proberen" meaning "to test") and signal (V operation, from "verhogen" meaning "to increment"). When a thread requests a resource through the wait operation, the semaphore decrements its counter. If the counter reaches zero, subsequent wait operations block until another thread releases a resource through the signal operation.

Semaphores solve coordination problems that simpler mechanisms like mutexes cannot address alone. While a mutex provides binary locking (locked or unlocked), a semaphore counts multiple resource units. This distinction makes semaphores suitable for scenarios like connection pools, thread pools, or any situation requiring control over multiple identical resources.

# Conceptual semaphore behavior
semaphore = Semaphore.new(3)  # Initialize with 3 permits

# Thread 1
semaphore.wait   # Counter: 3 -> 2
use_resource
semaphore.signal # Counter: 2 -> 3

# Thread 2
semaphore.wait   # Counter: 2 -> 1
use_resource
semaphore.signal # Counter: 1 -> 2

The counter value determines semaphore behavior. A positive counter indicates available resources. Zero means all resources are in use but no threads are waiting. A negative counter (in some implementations) represents the number of blocked threads waiting for resources.

Semaphores appear in two primary forms: counting semaphores and binary semaphores. Counting semaphores manage multiple resource units with a counter that can range from zero to an arbitrary maximum. Binary semaphores restrict the counter to zero or one, functioning similarly to mutexes but with different semantics around ownership and signaling.

Key Principles

Semaphores enforce mutual exclusion and synchronization through atomic operations on an integer counter. The atomicity of wait and signal operations guarantees that no race conditions occur during counter modifications. The operating system or runtime ensures these operations complete without interruption, making them safe for concurrent access.

The wait operation tests the counter value and blocks if no resources are available:

wait(S):
  while S.value <= 0:
    block current thread
  S.value = S.value - 1

The signal operation increments the counter and wakes one blocked thread if any exist:

signal(S):
  S.value = S.value + 1
  if threads are blocked on S:
    wake one thread

The semaphore counter represents resource availability, not resource ownership. Unlike mutexes where the locking thread must unlock, any thread can signal a semaphore regardless of which thread called wait. This property enables coordination patterns where producer threads signal consumer threads without symmetric pairing.

Semaphore initialization establishes the maximum concurrency level. A semaphore initialized to N allows N threads simultaneous access to the protected resource. Setting the initial value to 1 creates a binary semaphore for mutual exclusion. Setting it to 0 creates a semaphore for pure synchronization where threads wait until another thread signals.

The fairness property determines how blocked threads receive resources when they become available. Fair semaphores use FIFO queuing to wake threads in the order they blocked. Unfair semaphores may wake any blocked thread, potentially causing starvation where some threads wait indefinitely while others repeatedly acquire resources.

Semaphores operate at a lower level than monitors or condition variables. They provide building blocks for constructing higher-level synchronization mechanisms. The simplicity of semaphores makes them efficient but also error-prone, as developers must manually ensure proper pairing of wait and signal operations.

The counting capability distinguishes semaphores from binary locks. A counting semaphore tracks multiple identical resources, such as database connections or worker threads. Each resource unit decrements the counter on acquisition and increments it on release. This counting mechanism prevents oversubscription of limited resources.

Semaphore semantics differ from mutex semantics in ownership. A mutex has an owner—the thread that acquired it must release it. A semaphore has no owner; any thread can call signal regardless of whether it previously called wait. This flexibility enables producer-consumer patterns where producer threads signal consumers they have never synchronized with directly.

Ruby Implementation

Ruby does not include a built-in Semaphore class in its standard library. Developers implement semaphores using Thread::Mutex and Thread::ConditionVariable, or use the concurrent-ruby gem which provides a tested implementation.

class Semaphore
  def initialize(size)
    @size = size
    @mutex = Thread::Mutex.new
    @cv = Thread::ConditionVariable.new
  end

  def wait
    @mutex.synchronize do
      while @size <= 0
        @cv.wait(@mutex)
      end
      @size -= 1
    end
  end

  def signal
    @mutex.synchronize do
      @size += 1
      @cv.signal
    end
  end
end

This implementation uses a mutex to protect the counter and a condition variable to block threads when no resources are available. The while loop in wait rechecks the condition after waking to handle spurious wakeups, where condition variables wake without an explicit signal.

The concurrent-ruby gem provides a production-ready Semaphore class:

require 'concurrent'

semaphore = Concurrent::Semaphore.new(5)

threads = 10.times.map do |i|
  Thread.new do
    semaphore.acquire
    puts "Thread #{i} acquired resource"
    sleep(rand)
    puts "Thread #{i} releasing resource"
    semaphore.release
  end
end

threads.each(&:join)

The Concurrent::Semaphore API uses acquire and release instead of wait and signal, following Java's naming convention. This implementation includes timeout support for acquire operations:

semaphore = Concurrent::Semaphore.new(2)

# Try to acquire with 1 second timeout
if semaphore.try_acquire(1)
  begin
    # Use resource
  ensure
    semaphore.release
  end
else
  puts "Could not acquire resource within timeout"
end

Ruby's Global Interpreter Lock (GIL) affects semaphore behavior. The GIL allows only one thread to execute Ruby code at a time, but threads can block on I/O or synchronization primitives. Semaphores remain useful in Ruby for coordinating I/O-bound operations, managing connection pools, and controlling access to external resources.

class ConnectionPool
  def initialize(max_connections)
    @semaphore = Concurrent::Semaphore.new(max_connections)
    @connections = []
  end

  def with_connection
    @semaphore.acquire
    connection = acquire_connection
    begin
      yield connection
    ensure
      release_connection(connection)
      @semaphore.release
    end
  end

  private

  def acquire_connection
    # Return existing or create new connection
  end

  def release_connection(connection)
    # Return connection to pool
  end
end

pool = ConnectionPool.new(10)

threads = 20.times.map do
  Thread.new do
    pool.with_connection do |conn|
      # Execute database query
    end
  end
end

The ensure block guarantees that semaphore release occurs even if exceptions occur during resource usage. This pattern prevents resource leaks that would permanently decrement the semaphore counter.

Ruby threads use native system threads, making semaphores effective for coordinating system resources. When Ruby code blocks on a semaphore, the underlying thread yields to the operating system, allowing other threads to run. This behavior makes semaphores suitable for managing file handles, network sockets, and other system resources.

Practical Examples

A download manager limits concurrent downloads to prevent overwhelming the network:

require 'concurrent'
require 'net/http'

class DownloadManager
  def initialize(max_concurrent)
    @semaphore = Concurrent::Semaphore.new(max_concurrent)
  end

  def download(url)
    @semaphore.acquire
    begin
      puts "Starting download: #{url}"
      uri = URI(url)
      response = Net::HTTP.get_response(uri)
      puts "Completed download: #{url} (#{response.body.length} bytes)"
      response.body
    ensure
      @semaphore.release
    end
  end
end

manager = DownloadManager.new(3)
urls = [
  'http://example.com/file1',
  'http://example.com/file2',
  'http://example.com/file3',
  'http://example.com/file4',
  'http://example.com/file5'
]

threads = urls.map do |url|
  Thread.new { manager.download(url) }
end

threads.each(&:join)

The semaphore limits three simultaneous downloads. When three downloads run, the fourth thread blocks until one completes. This prevents network saturation and respects server rate limits.

A worker pool processes tasks with limited concurrency:

class WorkerPool
  def initialize(worker_count)
    @semaphore = Concurrent::Semaphore.new(worker_count)
    @queue = Queue.new
  end

  def submit(task)
    @queue.push(task)
  end

  def start
    loop do
      task = @queue.pop
      @semaphore.acquire
      Thread.new do
        begin
          task.call
        ensure
          @semaphore.release
        end
      end
    end
  end
end

pool = WorkerPool.new(5)

# Submit tasks
100.times do |i|
  pool.submit(-> { 
    puts "Processing task #{i}"
    sleep(rand)
  })
end

# Start processing
Thread.new { pool.start }
sleep(10)  # Let tasks process

The semaphore ensures no more than five workers execute simultaneously. As workers complete tasks, they release permits, allowing new workers to start.

A rate limiter controls API request frequency using a semaphore that refreshes permits periodically:

class RateLimiter
  def initialize(requests_per_second)
    @semaphore = Concurrent::Semaphore.new(requests_per_second)
    @requests_per_second = requests_per_second
    start_refresh_thread
  end

  def execute(&block)
    @semaphore.acquire
    begin
      block.call
    ensure
      # Don't release here - let refresh thread handle it
    end
  end

  private

  def start_refresh_thread
    Thread.new do
      loop do
        sleep(1.0 / @requests_per_second)
        @semaphore.release rescue nil
      end
    end
  end
end

limiter = RateLimiter.new(10)  # 10 requests per second

100.times do |i|
  Thread.new do
    limiter.execute do
      puts "API request #{i} at #{Time.now}"
    end
  end
end

sleep(15)

The refresh thread periodically adds permits to the semaphore, maintaining the desired request rate. This pattern implements token bucket rate limiting.

A batch processor groups operations and uses a semaphore to coordinate batch completion:

class BatchProcessor
  def initialize(batch_size)
    @batch_size = batch_size
    @items = []
    @mutex = Thread::Mutex.new
    @semaphore = Concurrent::Semaphore.new(0)
  end

  def add_item(item)
    @mutex.synchronize do
      @items << item
      if @items.size >= @batch_size
        @semaphore.release
      end
    end
  end

  def process_batch
    @semaphore.acquire
    items_to_process = @mutex.synchronize do
      batch = @items.shift(@batch_size)
      batch
    end
    
    # Process batch
    puts "Processing batch of #{items_to_process.size} items"
    items_to_process.each do |item|
      # Process item
    end
  end
end

processor = BatchProcessor.new(10)

# Producer thread
Thread.new do
  100.times do |i|
    processor.add_item(i)
    sleep(0.01)
  end
end

# Consumer threads
3.times.map do
  Thread.new do
    10.times { processor.process_batch }
  end
end.each(&:join)

The semaphore blocks consumer threads until enough items accumulate for a full batch. The producer signals the semaphore when a batch is ready, coordinating asynchronous production and consumption.

Common Patterns

The producer-consumer pattern uses semaphores to coordinate threads that produce and consume items:

class ProducerConsumer
  def initialize(buffer_size)
    @buffer = []
    @mutex = Thread::Mutex.new
    @empty_count = Concurrent::Semaphore.new(buffer_size)
    @full_count = Concurrent::Semaphore.new(0)
  end

  def produce(item)
    @empty_count.acquire
    @mutex.synchronize do
      @buffer << item
      puts "Produced: #{item} (buffer size: #{@buffer.size})"
    end
    @full_count.release
  end

  def consume
    @full_count.acquire
    item = @mutex.synchronize do
      item = @buffer.shift
      puts "Consumed: #{item} (buffer size: #{@buffer.size})"
      item
    end
    @empty_count.release
    item
  end
end

pc = ProducerConsumer.new(5)

# Producer threads
producers = 2.times.map do |i|
  Thread.new do
    10.times do |j|
      pc.produce("item-#{i}-#{j}")
      sleep(rand * 0.1)
    end
  end
end

# Consumer threads
consumers = 3.times.map do
  Thread.new do
    7.times do
      pc.consume
      sleep(rand * 0.2)
    end
  end
end

(producers + consumers).each(&:join)

Two semaphores coordinate production and consumption. The empty_count semaphore tracks available buffer slots. The full_count semaphore tracks items ready for consumption. Producers wait for empty slots and signal full slots. Consumers wait for full slots and signal empty slots.

The readers-writers pattern allows multiple concurrent readers but exclusive writer access:

class ReadersWriters
  def initialize
    @readers = 0
    @mutex = Thread::Mutex.new
    @write_lock = Concurrent::Semaphore.new(1)
    @reader_lock = Concurrent::Semaphore.new(1)
  end

  def read
    @reader_lock.acquire
    @mutex.synchronize do
      @readers += 1
      @write_lock.acquire if @readers == 1
    end
    @reader_lock.release

    begin
      yield
    ensure
      @mutex.synchronize do
        @readers -= 1
        @write_lock.release if @readers == 0
      end
    end
  end

  def write
    @write_lock.acquire
    begin
      yield
    ensure
      @write_lock.release
    end
  end
end

rw = ReadersWriters.new
shared_data = { value: 0 }

# Reader threads
readers = 5.times.map do |i|
  Thread.new do
    10.times do
      rw.read do
        puts "Reader #{i} read: #{shared_data[:value]}"
      end
      sleep(rand * 0.1)
    end
  end
end

# Writer threads
writers = 2.times.map do |i|
  Thread.new do
    5.times do |j|
      rw.write do
        shared_data[:value] += 1
        puts "Writer #{i} wrote: #{shared_data[:value]}"
      end
      sleep(rand * 0.5)
    end
  end
end

(readers + writers).each(&:join)

The write_lock semaphore ensures exclusive writer access. The first reader acquires the write lock to block writers. Subsequent readers increment the counter without blocking. The last reader releases the write lock, allowing writers to proceed.

The barrier pattern synchronizes multiple threads at a rendezvous point:

class Barrier
  def initialize(thread_count)
    @thread_count = thread_count
    @arrived = 0
    @mutex = Thread::Mutex.new
    @barrier = Concurrent::Semaphore.new(0)
    @release = Concurrent::Semaphore.new(0)
  end

  def wait
    @mutex.synchronize do
      @arrived += 1
      if @arrived == @thread_count
        @thread_count.times { @release.release }
      end
    end
    
    @release.acquire
    
    @mutex.synchronize do
      @arrived -= 1
      if @arrived == 0
        @thread_count.times { @barrier.release }
      end
    end
    
    @barrier.acquire
  end
end

barrier = Barrier.new(5)

threads = 5.times.map do |i|
  Thread.new do
    puts "Thread #{i} phase 1"
    sleep(rand)
    barrier.wait
    puts "Thread #{i} phase 2"
    sleep(rand)
    barrier.wait
    puts "Thread #{i} phase 3"
  end
end

threads.each(&:join)

Threads block at the barrier until all threads arrive. The last arriving thread releases all blocked threads simultaneously. This pattern coordinates phases in parallel algorithms where each phase depends on completing the previous phase.

The multiplex pattern limits concurrent access to multiple resources:

class Multiplex
  def initialize(resource_count)
    @semaphore = Concurrent::Semaphore.new(resource_count)
  end

  def execute
    @semaphore.acquire
    begin
      yield
    ensure
      @semaphore.release
    end
  end
end

multiplex = Multiplex.new(3)

threads = 10.times.map do |i|
  Thread.new do
    multiplex.execute do
      puts "Thread #{i} using resource"
      sleep(1)
      puts "Thread #{i} finished"
    end
  end
end

threads.each(&:join)

The semaphore count determines maximum concurrency. This pattern applies to connection pools, thread pools, or any scenario requiring controlled parallelism.

Common Pitfalls

Deadlock occurs when threads circularly wait for resources. Consider two threads acquiring semaphores in different orders:

semaphore_a = Concurrent::Semaphore.new(1)
semaphore_b = Concurrent::Semaphore.new(1)

# Thread 1
Thread.new do
  semaphore_a.acquire
  sleep(0.1)  # Increase chance of deadlock
  semaphore_b.acquire
  # Never reaches here
  semaphore_b.release
  semaphore_a.release
end

# Thread 2
Thread.new do
  semaphore_b.acquire
  sleep(0.1)
  semaphore_a.acquire
  # Never reaches here
  semaphore_a.release
  semaphore_b.release
end

sleep(5)
puts "Deadlocked"

Thread 1 holds semaphore_a and waits for semaphore_b. Thread 2 holds semaphore_b and waits for semaphore_a. Neither thread progresses. Prevent deadlock by acquiring semaphores in consistent order across all threads:

# Both threads acquire in same order
def safe_acquire(semaphore_a, semaphore_b)
  semaphore_a.acquire
  semaphore_b.acquire
  begin
    yield
  ensure
    semaphore_b.release
    semaphore_a.release
  end
end

Forgetting to release semaphores causes resource leaks. Exceptions in critical sections particularly risk this:

semaphore = Concurrent::Semaphore.new(5)

# Dangerous - exception prevents release
def process_item(semaphore, item)
  semaphore.acquire
  # If this raises exception, semaphore never releases
  risky_operation(item)
  semaphore.release
end

# Safe - ensure guarantees release
def process_item_safe(semaphore, item)
  semaphore.acquire
  begin
    risky_operation(item)
  ensure
    semaphore.release
  end
end

Always wrap resource usage in begin-ensure blocks to guarantee semaphore release regardless of exceptions.

Starvation occurs when threads perpetually fail to acquire resources. Unfair semaphores allow newly arriving threads to acquire permits before long-waiting threads:

semaphore = Concurrent::Semaphore.new(1)

# High-priority threads constantly compete
10.times do
  Thread.new do
    loop do
      semaphore.acquire
      # Quick operation
      sleep(0.001)
      semaphore.release
      sleep(0.001)  # Brief pause
    end
  end
end

# Low-priority thread may starve
Thread.new do
  semaphore.acquire
  puts "Finally acquired!"
  semaphore.release
end

sleep(10)

The low-priority thread competes with ten aggressive threads. Without fairness guarantees, it may never acquire the semaphore. Use fair semaphores or implement application-level fairness mechanisms.

Priority inversion occurs when low-priority threads block high-priority threads:

semaphore = Concurrent::Semaphore.new(1)

# Low priority thread
low_priority = Thread.new do
  semaphore.acquire
  sleep(5)  # Long operation
  semaphore.release
end

# High priority thread
high_priority = Thread.new do
  sleep(0.1)  # Start slightly after low priority
  semaphore.acquire  # Blocks on low priority thread
  puts "High priority running"
  semaphore.release
end

The high-priority thread waits for the low-priority thread to complete. Priority inheritance protocols address this by temporarily elevating the blocking thread's priority, but Ruby's standard library does not implement this.

Spurious wakeups in custom semaphore implementations cause incorrect behavior without proper condition rechecking:

class BrokenSemaphore
  def initialize(size)
    @size = size
    @mutex = Thread::Mutex.new
    @cv = Thread::ConditionVariable.new
  end

  def wait
    @mutex.synchronize do
      if @size <= 0  # WRONG: should be while, not if
        @cv.wait(@mutex)
      end
      @size -= 1
    end
  end
end

Using if instead of while fails to recheck the condition after waking. Spurious wakeups cause threads to proceed when resources remain unavailable. Always use while loops when waiting on condition variables.

Signal-wait race conditions occur when signaling before waiting:

semaphore = Concurrent::Semaphore.new(0)

# Thread 1 signals first
Thread.new do
  semaphore.release
  puts "Signaled"
end

sleep(0.5)  # Ensure Thread 1 completes

# Thread 2 waits second - will block forever
Thread.new do
  puts "Waiting"
  semaphore.acquire  # Blocks forever
  puts "Acquired"
end

sleep(5)

The signal occurs before the wait, losing the notification. The waiting thread never wakes because the semaphore counter returns to zero. Initialize semaphores correctly for intended synchronization patterns.

Mismatched acquire-release counts corrupt semaphore state:

semaphore = Concurrent::Semaphore.new(3)

# Release without acquire
5.times do
  Thread.new do
    # Forgot to acquire!
    semaphore.release
  end
end

sleep(0.1)

# Now semaphore has 8 permits instead of 3
8.times do
  semaphore.acquire  # All succeed
end

Releasing without corresponding acquisition inflates the semaphore count beyond its intended maximum. This allows more concurrent access than designed, potentially overwhelming resources. Track acquire-release pairs carefully and consider using block-based patterns that guarantee proper pairing.

Reference

Core Operations

Semaphore Types

Common Patterns

Ruby Implementation

require 'concurrent'

# Create semaphore
semaphore = Concurrent::Semaphore.new(5)

# Acquire with ensure
semaphore.acquire
begin
  # Use resource
ensure
  semaphore.release
end

# Try with timeout
if semaphore.try_acquire(1.0)
  begin
    # Use resource
  ensure
    semaphore.release
  end
end

# Query available permits
available = semaphore.available_permits

Deadlock Prevention

Performance Characteristics

Error Scenarios

Integration with Ruby Constructs