Skip to content

← Fearless Concurrency: Threads, Channels, Shared State step 21 of 24

Medium End-to-End

Barrier: keeping workers in lock step

Repair the barrier configuration in a parallel Game of Life simulation. The supplied code already divides rows among workers and calculates each generation. Its barrier can wait for threads that were never started.

pub fn life_generations(grid: Vec<Vec<u8>>, steps: usize, workers: usize) -> Vec<Vec<u8>>

Simulation rules

The input is a rectangular grid containing only 0 (dead) and 1 (alive). Count the eight neighboring positions around each cell, excluding the cell itself. Positions outside the grid count as dead; edges do not wrap.

  • A live cell survives with two or three live neighbors.
  • A dead cell becomes alive with exactly three live neighbors.
  • Every other cell is dead in the next generation.

Compute every cell from the previous generation. Return a grid with the same dimensions after exactly steps updates.

Return the input unchanged when steps == 0, there are no rows, or every row is empty. Treat workers == 0 as one requested worker. Inputs have manageable dimensions and step counts; ragged rows and nonbinary cell values are outside the exercise's contract.

For example, one update turns this vertical blinker into a horizontal one:

0 1 0       0 0 0
0 1 0  ->   1 1 1
0 1 0       0 0 0

A second update restores the original board. Changing the worker count must not change either result.

Count the workers that actually participate

For a nonempty, nonzero-width grid with updates to perform, the supplied code starts workers.max(1).min(rows) threads. Each receives a nonempty consecutive band of rows, with larger bands first when division is uneven.

Construct the barrier with that same participant count. The starter uses the requested worker count for the barrier but the capped count for thread creation. For three rows and eight requested workers, only three threads arrive at a barrier waiting for eight. The simulation cannot finish its first update.

This mismatch matters only when the simulation reaches a wait. Zero steps and empty dimensions return before creating threads or a barrier.

What a barrier provides

Barrier::wait blocks until the configured number of participants have arrived. The same barrier can be reused for successive rounds. Here each worker must call it once per generation, after finishing its assigned cells.

A worker may resume before another worker has returned from the same wait. The guarantee needed here is that all participants have arrived before any begins the next update, not that their instructions execute in unison.

Exactly one participant receives a result with is_leader() == true per round. That designation does not keep the other participants blocked while the leader performs extra work. If they depend on the leader's result, another synchronization step is needed before they use it.

Read one buffer and write the other

Updating cells in place would overwrite values that neighboring cells still need to read. The supplied implementation uses two complete buffers:

  • On even-numbered iterations, read buffer 0 and write buffer 1.
  • On odd-numbered iterations, read buffer 1 and write buffer 0.

During an iteration, each output cell has exactly one writer, and every worker reads only the old board. At the barrier, all reads and writes for that iteration are finished. Workers can then reverse the buffers' roles without overwriting data another worker still needs.

Each worker derives these roles from its own iteration counter, so there is no shared buffer selector to update. One barrier wait per iteration is sufficient for this scheme. After the scoped threads join, the result is in buffer steps % 2.

A design where a leader swaps shared buffer metadata would need to make that swap visible before other workers continue, commonly with a second barrier. The parity approach avoids that extra step here; it is not a universal performance guarantee.

Why this implementation uses atomic cells

AtomicU8 allows each worker to share references to both buffers while reading and writing cells through those references. The buffers' ownership stays outside the scoped threads.

Relaxed loads and stores are sufficient with this phase protocol: there is one writer per output cell, no reads from the output buffer during an update, and the barrier synchronizes completed writes before the next update reads them. Relaxed operations alone would not establish that ordering. The final thread joins also precede collecting the returned grid.

Atomics are one implementation choice. Disjoint mutable output slices can work in other designs, for example by creating a scoped set of workers for each generation. Persistent workers can also use a different ownership or message-passing design. A barrier does not override Rust's borrowing rules, and atomic cells do not automatically make the program faster.

The supplied buffers are already initialized correctly. A repeated-element expression such as vec![AtomicU8::new(0); n] would require Clone, which AtomicU8 does not implement; the iterator-based construction creates each cell separately.

Missing arrivals can block progress

Barrier::wait has no timeout or error result reporting a missing worker. If a participant exits or panics before a required arrival while other workers keep waiting, they can remain blocked. A panic after its final required wait does not create that particular missing arrival; process abort also differs from unwinding one worker.

Keep all participants on the same number of barrier rounds. For a larger application, plan how errors and cancellation will stop the whole group. This exercise's valid inputs do not require a worker-failure recovery protocol.