CodingGyan

Phases with a Barrier

hard Multithreading and Concurrency

Problem

n threads work in m phases. In each phase, every thread adds 1 to a shared counter, and then waits at a barrier until all n threads have arrived. After the barrier, every thread checks that the counter equals n times the phase number (nobody went ahead). Then all threads wait at the barrier a second time, before the next phase starts. Print phase K: ok for each phase K = 1..m if all checks passed. Input: n and m.

Constraints

  • 1 <= n <= 8
  • 1 <= m <= 10

Examples

Input

3 2

Output

phase 1: ok
phase 2: ok

Solutions

Best approachTime O(n m)Space O(n + m)

A barrier stops every thread until all n have arrived. After it, every thread sees the finished work of the others. Without the second barrier, a fast thread could add to the counter of the next phase while a slow thread is still checking the old phase.

Same code works in Java810172125Basic features only, so nothing changes between versions.

JavaScript and TypeScript have no shared-memory threads here, so they follow the same steps in one thread.

/*
 * Problem : Check the phases.
 * Input   : n and m.
 * Output  : One line per phase.
 * Approach: Barrier
 * Time    : O(n m)
 * Space   : O(n + m)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(long a, long b) {
        final int n = (int) a;
        final int phases = (int) b;
        java.util.concurrent.CyclicBarrier barrier = new java.util.concurrent.CyclicBarrier(n);
        java.util.concurrent.atomic.AtomicInteger counter = new java.util.concurrent.atomic.AtomicInteger();
        java.util.concurrent.atomic.AtomicIntegerArray wrong = new java.util.concurrent.atomic.AtomicIntegerArray(phases + 1);
        Thread[] threads = new Thread[n];
        for (int i = 0; i < n; i++) {
            threads[i] = new Thread(() -> {
                try {
                    for (int phase = 1; phase <= phases; phase++) {
                        // Step 1: Do the work of this phase, then wait until all n threads have done it.
                        counter.incrementAndGet();
                        barrier.await();
                        // Step 2: Past the barrier, the counter must show the work of all threads.
                        if (counter.get() != n * phase) {
                            wrong.incrementAndGet(phase);
                        }
                        // Step 3: A second barrier: no thread may start the next phase before everybody has checked.
                        barrier.await();
                    }
                } catch (InterruptedException | java.util.concurrent.BrokenBarrierException e) {
                    Thread.currentThread().interrupt();
                }
            });
            threads[i].start();
        }
        for (Thread thread : threads) {
            try {
                thread.join();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        String[] out = new String[phases];
        for (int phase = 1; phase <= phases; phase++) {
            out[phase - 1] = "phase " + phase + (wrong.get(phase) == 0 ? ": ok" : ": broken");
        }
        return out;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(String.join("\n", solve(a, b)));
    }
}
Hints (2)
  1. Why do we need a second barrier?
  2. What would the check show without any barrier?

Try these next