Semaphores

Counting synchronization primitive with resource assignment and FIFO queue

Overview

A Semaphore is a counting synchronization primitive that controls access to a limited pool of resources. Unlike a binary mutex, a semaphore maintains a counter that allows multiple threads to access the resource simultaneously (up to the counter limit).

When to Use Semaphores

Resource Pools

Managing access to N identical resources (e.g., printers, database connections)

Bounded Parallelism

Limiting concurrent access to avoid overwhelming a resource

Producer-Consumer

Coordinating between threads that produce and consume items

Rate Limiting

Throttling concurrent operations to a maximum count

How It Works

A semaphore maintains a count representing available resources:

• count > 0: Resources available, threads can proceed
• count = 0: All resources in use, new threads must wait

Operations

1. wait() - Acquire Resource

   Decrements count if > 0 and assigns a resource. If count = 0, thread blocks in FIFO queue.

2. signal() - Release Resource

   Releases the resource. If threads are waiting, transfers resource directly to the next in queue. Otherwise, increments count.

Semaphore vs Mutex: A mutex is essentially a binary semaphore (count = 1) with ownership semantics. Semaphores allow count > 1 and don’t enforce “only owner can release” rules.

Implementation

Here’s the complete semaphore implementation from the simulator:

source/js/core/semaphore.js

// Semaforo contador con cola FIFO y asignacion de recurso (impresoras).
export class Semaphore {
  constructor(initialCount) {
    // count representa cuantos hilos mas pueden entrar a "zona de impresion".
    this.count = Math.max(0, Number(initialCount) || 0);
    // Cola FIFO para respetar orden de llegada cuando se bloquean.
    this.queue = [];
    // Mapeo para recordar que impresora tiene cada hilo.
    this.assignments = new Map();
  }

  // Intenta tomar un token y una impresora libre.
  wait(thread, printers) {
    // Si el hilo ya tiene recurso asignado por transferencia, puede continuar.
    if (this.assignments.has(thread)) {
      // Devuelvo la misma impresora para que el hilo avance sin bloquearse de nuevo.
      return this.assignments.get(thread);
    }

    // Solo puedo asignar si hay tokens libres.
    if (this.count > 0) {
      // Busco primera impresora sin dueño.
      const printerIndex = printers.findIndex((printer) => !printer.owner);
      if (printerIndex === -1) return null;

      // Consumo token y asigno impresora al hilo.
      this.count--;
      this.assignments.set(thread, printerIndex);
      printers[printerIndex].owner = thread;
      return printerIndex;
    }

    // No hay token: se bloquea en cola.
    thread.state = "blocked";
    thread.blockedBy = this;
    if (!this.queue.includes(thread)) this.queue.push(thread);
    return null;
  }

  // Libera token/impresora y transfiere al siguiente hilo si existe.
  signal(thread, printers) {
    if (!this.assignments.has(thread)) {
      // Esto ayuda a detectar bugs: signal sin haber hecho wait.
      throw new Error("El hilo no tiene recurso asignado para signal");
    }

    // Obtengo impresora actual para liberarla.
    const releasedPrinter = this.assignments.get(thread);
    this.assignments.delete(thread);
    printers[releasedPrinter].owner = null;

    // Si hay cola, hago transferencia directa de la misma impresora.
    if (this.queue.length > 0) {
      const nextThread = this.queue.shift();
      // El siguiente pasa de bloqueado a listo.
      nextThread.state = "ready";
      nextThread.blockedBy = null;
      // Asigno impresora al siguiente sin subir count.
      this.assignments.set(nextThread, releasedPrinter);
      printers[releasedPrinter].owner = nextThread;
      return { releasedPrinter, nextThread };
    }

    // Si nadie espera, entonces si regreso token al semaforo.
    this.count++;
    return { releasedPrinter, nextThread: null };
  }

  // Devuelve el indice de impresora del hilo, o null si no tiene.
  getAssignedPrinter(thread) {
    return this.assignments.has(thread) ? this.assignments.get(thread) : null;
  }
}

Wait Operation

The wait() method handles resource acquisition:

Case 1: Already Assigned (lines 14-18)

If the thread was previously granted a resource via transfer, return it:

if (this.assignments.has(thread)) {
  return this.assignments.get(thread);
}

Case 2: Resources Available (lines 20-30)

If count > 0, find a free resource, decrement count, and assign:

if (this.count > 0) {
  const printerIndex = printers.findIndex((printer) => !printer.owner);
  if (printerIndex === -1) return null;
  
  this.count--;
  this.assignments.set(thread, printerIndex);
  printers[printerIndex].owner = thread;
  return printerIndex;
}

Case 3: All Resources Busy (lines 32-36)

Block the thread and add to FIFO queue:

thread.state = "blocked";
thread.blockedBy = this;
if (!this.queue.includes(thread)) this.queue.push(thread);
return null;

Signal Operation

The signal() method implements direct resource transfer:

Threads waiting - direct transfer

if (this.queue.length > 0) {
  const nextThread = this.queue.shift();
  nextThread.state = "ready";
  nextThread.blockedBy = null;
  
  // Transfer the same resource
  this.assignments.set(nextThread, releasedPrinter);
  printers[releasedPrinter].owner = nextThread;
  return { releasedPrinter, nextThread };
}

Direct Transfer Strategy: Like the mutex, the semaphore transfers resources directly to waiting threads without incrementing the count. This maintains FIFO fairness and prevents “line cutting.”

Resource Assignment Tracking

The semaphore uses a Map to track which resource each thread owns:

// assignments: Map<Thread, ResourceIndex>
this.assignments = new Map();

// Assign resource to thread
this.assignments.set(thread, printerIndex);

// Check if thread has resource
if (this.assignments.has(thread)) {
  return this.assignments.get(thread);
}

// Release resource
this.assignments.delete(thread);

This tracking enables:

• Validation: Ensuring threads only release resources they own
• Transfer: Knowing which specific resource to transfer to the next thread
• Query: Checking which resource a thread is currently using

Usage Example: Printer Pool

The printer scenario demonstrates a semaphore managing a pool of printers:

Scenario setup

import { Semaphore } from "../core/semaphore.js";
import { Thread } from "../core/thread.js";
import { Instructions } from "../core/instructions.js";

const printerCount = 3;
const semaphore = new Semaphore(printerCount);

const printers = Array.from({ length: printerCount }, (_, i) => ({
  id: i + 1,
  owner: null,
  completedJobs: 0,
  totalPages: 0,
}));

// Create print jobs
for (let i = 1; i <= jobCount; i++) {
  const instructions = [
    { type: Instructions.WAIT_SEM },
    { type: Instructions.PRINT, pages: 10 },
    { type: Instructions.SIGNAL_SEM },
    { type: Instructions.END },
  ];
  
  const thread = new Thread(`Trabajo-${i}`, instructions);
  engine.addThread(thread);
}

Counting Behavior

Let’s trace how the count changes with 3 printers and 5 jobs:

Key observation: The count never goes above the initial value (3) until all waiting threads are served.

FIFO Queue Management

The semaphore maintains strict FIFO ordering for fairness:

// Add to back of queue
if (!this.queue.includes(thread)) {
  this.queue.push(thread);
}

// Remove from front of queue
const nextThread = this.queue.shift();

This ensures:

• Fairness: Threads are served in arrival order
• No starvation: Every waiting thread will eventually get a resource
• Predictability: Execution order is deterministic

Common Pitfalls

Signal without Wait: Calling signal() without a corresponding wait() throws an error:

if (!this.assignments.has(thread)) {
  throw new Error("El hilo no tiene recurso asignado para signal");
}

Deadlock: If threads acquire resources and never release them, eventually all resources are exhausted and remaining threads block forever.

Count Overflow: In some implementations, calling signal() too many times can increment count beyond the initial value, creating “phantom resources.” This implementation prevents that with direct transfer.

Producer-Consumer Pattern

Semaphores are commonly used in pairs for producer-consumer synchronization:

const empty = new Semaphore(bufferSize); // Available slots
const full = new Semaphore(0);           // Available items

// Producer
empty.wait();  // Wait for empty slot
buffer.push(item);
full.signal(); // Signal item available

// Consumer
full.wait();   // Wait for item
const item = buffer.pop();
empty.signal(); // Signal slot available

Visualizing Semaphore Behavior

In the simulator, you can observe:

• Counter display: Current value of the semaphore count
• Resource status: Which thread owns each printer
• Queue visualization: Threads waiting in FIFO order
• Transfer animation: Resource moving from releasing thread to next waiter

Related Scenarios

Printer Pool

Multiple print jobs competing for a limited set of printers

Key Takeaways

1. Counting Primitive

   Semaphores allow N threads concurrent access (unlike binary mutex)

2. Resource Pool Management

   Tracks which specific resource each thread owns

3. Direct Transfer

   Resources move directly from releasing thread to next waiter

4. FIFO Fairness

   Waiting threads are served in arrival order

See Also

• Mutex - Binary version with ownership semantics
• Condition Variables - Signaling mechanism for more complex coordination
• Monitors - Combines mutex with condition variables