Barriers

Overview

A Barrier is a synchronization primitive that blocks a group of threads until all of them reach a common synchronization point. Once all threads arrive, the barrier “opens” and releases all waiting threads simultaneously.

When to Use Barriers

Parallel Phases

Coordinating threads that work in lockstep phases (e.g., parallel algorithms)

Checkpoints

Synchronizing at specific points in execution (e.g., race checkpoints)

Bulk Synchronous

Implementing bulk synchronous parallel (BSP) programming model

Staged Pipelines

Ensuring all threads complete one stage before any enters the next

How It Works

A barrier operates on a fixed number of participants:

Each thread calls arrive() when it reaches the barrier
First N-1 threads block and wait
The Nth (last) thread triggers barrier opening
All waiting threads are released simultaneously

Barrier Lifecycle

Initialize

Create barrier with participant count N

Threads Arrive

Threads 1 through N-1 arrive and block

Last Thread Arrives

Thread N arrives, barrier opens

Release All

All N threads are unblocked simultaneously

Reset (Cyclic)

Barrier resets for potential next round

Cyclic Barriers: The implementation is cyclic, meaning after opening, the barrier resets its counter and can be reused for subsequent synchronization rounds.

Implementation

Here’s the complete barrier implementation from the simulator:

source/js/core/barrier.js

// Barrera ciclica simple: todos deben llegar para abrir paso.
export class Barrier {
  constructor(participants) {
    // Cantidad de hilos que deben sincronizarse en el checkpoint.
    this.participants = Math.max(1, Number(participants) || 1);
    // Cola FIFO de hilos bloqueados esperando apertura de barrera.
    this.waitingQueue = [];
    // Cantidad de llegadas en la ronda actual.
    this.arrived = 0;
    // Hilos con permiso concedido despues de abrir barrera.
    this.granted = new Set();
  }

  // Un hilo llega a la barrera y espera si aun no esta completo el grupo.
  arrive(thread) {
    // Si el hilo ya fue liberado por una apertura previa, pasa directo.
    if (this.granted.has(thread)) {
      this.granted.delete(thread);
      return { passed: true, opened: false, released: [] };
    }

    this.arrived += 1;

    // Si todavia no llegan todos, el hilo se bloquea.
    if (this.arrived < this.participants) {
      thread.state = "blocked";
      thread.blockedBy = this;
      if (!this.waitingQueue.includes(thread)) this.waitingQueue.push(thread);
      return { passed: false, opened: false, released: [] };
    }

    // Ultimo en llegar: abre barrera y despierta a todos los bloqueados.
    const released = [];
    while (this.waitingQueue.length > 0) {
      const waitingThread = this.waitingQueue.shift();
      waitingThread.state = "ready";
      waitingThread.blockedBy = null;
      this.granted.add(waitingThread);
      released.push(waitingThread);
    }

    // Reinicio contador para posibles rondas futuras de barrera.
    this.arrived = 0;
    return { passed: true, opened: true, released };
  }
}

Arrive Operation

The arrive() method handles three cases:

Case 1: Pre-granted Pass (lines 16-20)

If the thread was previously granted permission (from a barrier opening), it passes immediately:

if (this.granted.has(thread)) {
  this.granted.delete(thread);
  return { passed: true, opened: false, released: [] };
}

This prevents re-blocking when the thread is re-scheduled.

Case 2: Not Yet Complete (lines 22-29)

If not all participants have arrived, the thread blocks:

this.arrived += 1;

if (this.arrived < this.participants) {
  thread.state = "blocked";
  thread.blockedBy = this;
  if (!this.waitingQueue.includes(thread)) {
    this.waitingQueue.push(thread);
  }
  return { passed: false, opened: false, released: [] };
}

Case 3: Last to Arrive - Open Barrier (lines 31-43)

When the last participant arrives, the barrier opens and releases all waiting threads:

const released = [];
while (this.waitingQueue.length > 0) {
  const waitingThread = this.waitingQueue.shift();
  waitingThread.state = "ready";
  waitingThread.blockedBy = null;
  this.granted.add(waitingThread);
  released.push(waitingThread);
}

// Reset for next round
this.arrived = 0;
return { passed: true, opened: true, released };

Return Value

The arrive() method returns an object with:

passed: Whether this thread passed the barrier
opened: Whether this thread triggered the barrier opening
released: Array of threads that were released (if barrier opened)

// Thread 1, 2, 3 arrive (not last)
{ passed: false, opened: false, released: [] }

// Thread 4 arrives (last of 4)
{ passed: true, opened: true, released: [Thread1, Thread2, Thread3] }

// Released thread re-executes arrive
{ passed: true, opened: false, released: [] }

Permission Grant System

Like the monitor, the barrier uses a permission grant system:

Barrier Opens

When the last thread arrives, all waiting threads are added to the granted set

Threads Wake

Waiting threads transition from blocked to ready state

Thread Reschedules

When a thread runs again, it re-calls arrive()

Permission Check

Thread finds itself in granted set and passes immediately

// When barrier opens:
this.granted.add(waitingThread);

// When thread re-executes:
if (this.granted.has(thread)) {
  this.granted.delete(thread); // Consume permission
  return { passed: true, opened: false, released: [] };
}

Cyclic Behavior

The barrier is cyclic (reusable):

// Reset counter when barrier opens
this.arrived = 0;

This allows multiple barrier synchronizations:

// Round 1
thread.arrive(barrier); // All threads sync
// ... do work ...

// Round 2
thread.arrive(barrier); // All threads sync again
// ... do more work ...

Use case: Iterative parallel algorithms where threads repeatedly synchronize between iterations (e.g., parallel matrix multiplication, game simulation steps).

Usage Example: Race Checkpoint

The race scenario demonstrates barrier synchronization:

import { Barrier } from "../core/barrier.js";
import { Thread } from "../core/thread.js";
import { Instructions } from "../core/instructions.js";

const racerCount = 4;
const barrier = new Barrier(racerCount);

const race = {
  barrier,
  totalRacers: racerCount,
  passedCheckpointCount: 0,
  finishedCount: 0,
};

// Create racer threads
for (let i = 1; i <= racerCount; i++) {
  const instructions = [
    { type: Instructions.RUN_STAGE, stage: "to-checkpoint" },
    { type: Instructions.BARRIER_WAIT },
    { type: Instructions.RUN_STAGE, stage: "to-finish" },
    { type: Instructions.END },
  ];
  
  const racer = new Thread(`Corredor-${i}`, instructions);
  racer.role = "racer";
  racer.passedCheckpoint = false;
  racer.finishedRace = false;
  engine.addThread(racer);
}

Execution Timeline

Let’s trace 4 racers at a barrier:

FIFO Queue Management

The barrier maintains a FIFO queue:

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

// Release all from front
while (this.waitingQueue.length > 0) {
  const waitingThread = this.waitingQueue.shift();
  // ... release thread ...
}

While the barrier releases all threads simultaneously, the FIFO ordering determines:

The order in which threads are added to the granted set
The order in which they appear in the released array
Potentially, scheduling priority after release (implementation-dependent)

All-or-Nothing Semantics

Barriers implement all-or-nothing synchronization:

if (this.arrived < this.participants) {
  // Block: not ready yet
  return { passed: false, ... };
}

// All arrived: release everyone
while (this.waitingQueue.length > 0) {
  const waitingThread = this.waitingQueue.shift();
  waitingThread.state = "ready";
}

Key property: Either all threads are blocked, or all are released. There’s no partial release.

Common Pitfalls

Wrong Participant Count: If you create a barrier for N threads but only N-1 threads call arrive(), all threads block forever:

const barrier = new Barrier(5);
// Only 4 threads call arrive()
// All 4 block forever!

Thread Failure: If a thread crashes before reaching the barrier, all other threads block forever. Real implementations often provide timeout mechanisms.

Broken Barrier: If a thread arrives twice before the barrier opens, the count becomes incorrect:

barrier.arrive(thread); // arrived = 1
barrier.arrive(thread); // arrived = 2 (BUG!)

This implementation prevents it with the granted check.

Barrier vs Other Primitives

Barrier vs Semaphore

Semaphore: Controls resource access, allows N threads to proceed independently

semaphore.wait();  // Thread proceeds if count > 0

Barrier: Synchronization point, requires ALL threads to arrive

barrier.arrive();  // Thread blocks until ALL arrive

Barrier vs Join

Join: One thread waits for another specific thread to finish

thread1.join(thread2); // Thread1 waits for Thread2

Barrier: All threads wait for each other at a specific point

barrier.arrive(); // All threads wait for all others

Visualizing Barrier Behavior

In the simulator, you can observe:

Arrival counter: How many threads have arrived (e.g., “3/4”)
Waiting threads: Visual queue of blocked racers at checkpoint
Barrier opening: Animation of all threads released simultaneously
Cyclic reuse: Barrier resetting for potential next round

Parallel Algorithm Pattern

Barriers are essential in parallel algorithms with phases:

// Parallel matrix multiplication
for (let iteration = 0; iteration < maxIterations; iteration++) {
  // Phase 1: Each thread computes its portion
  computePartialResult();
  
  // Barrier: Wait for all threads to finish phase 1
  barrier.arrive();
  
  // Phase 2: Each thread uses results from all threads
  combineResults();
  
  // Barrier: Wait for all threads to finish phase 2
  barrier.arrive();
}

Without barriers, threads might read partial results from other threads, causing incorrect computations.

Race Checkpoint

Racers synchronizing at a checkpoint before continuing to the finish line

Key Takeaways

Synchronization Point

All threads must arrive before any can proceed

Fixed Participant Count

Barrier created with N threads, requires exactly N arrivals

Simultaneous Release

All waiting threads are released at once when barrier opens

Cyclic Reuse

Barrier resets after opening, can be used for multiple synchronization rounds

Permission Grant

Prevents re-blocking of threads after release

Getting Started

Synchronization Algorithms

Core Concepts

Scenarios

Overview

When to Use Barriers

Parallel Phases

Checkpoints

Bulk Synchronous

Staged Pipelines

How It Works

Barrier Lifecycle

Implementation

Arrive Operation

Return Value

Permission Grant System

Cyclic Behavior

Usage Example: Race Checkpoint

Execution Timeline

FIFO Queue Management

All-or-Nothing Semantics

Common Pitfalls

Barrier vs Other Primitives

Visualizing Barrier Behavior

Parallel Algorithm Pattern

Race Checkpoint

Key Takeaways

See Also

Getting Started

Synchronization Algorithms

Core Concepts

Scenarios

​Overview

​When to Use Barriers

Parallel Phases

Checkpoints

Bulk Synchronous

Staged Pipelines

​How It Works

​Barrier Lifecycle

​Implementation

​Arrive Operation

​Return Value

​Permission Grant System

​Cyclic Behavior

​Usage Example: Race Checkpoint

​Execution Timeline

​FIFO Queue Management

​All-or-Nothing Semantics

​Common Pitfalls

​Barrier vs Other Primitives

​Visualizing Barrier Behavior

​Parallel Algorithm Pattern

​Related Scenarios

Race Checkpoint

​Key Takeaways

​See Also

Overview

When to Use Barriers

How It Works

Barrier Lifecycle

Implementation

Arrive Operation

Return Value

Permission Grant System

Cyclic Behavior

Usage Example: Race Checkpoint

Execution Timeline

FIFO Queue Management

All-or-Nothing Semantics

Common Pitfalls

Barrier vs Other Primitives

Visualizing Barrier Behavior

Parallel Algorithm Pattern

Related Scenarios

Key Takeaways

See Also