Start Gate and Done Latch
Problem
n worker threads are created first, but none may start its job until the main thread opens a start gate (a latch with count 1). When the gate is open, worker i writes a[i] * 2 into a shared list. The main thread waits until all n workers are done (a latch with count n), then prints the list in increasing order.
Constraints
- 1 <= n <= 100
Examples
Input
3 3 1 2
Output
2 4 6
Solutions
The start latch makes all workers begin together, only when main says so. The done latch lets main wait without knowing the threads. Sorting at the end makes the output the same in every run, because the order of the workers is not fixed.
JavaScript and TypeScript have no shared-memory threads here, so they follow the same steps in one thread.
/*
* Problem : Run the gated workers.
* Input : n and the numbers.
* Output : The doubled numbers in increasing order.
* Approach: Latches
* Time : O(n log n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int[] solve(int[] a) {
// Step 1: The start latch begins at 1: workers wait for it. The done latch begins at n: main waits for it.
java.util.concurrent.CountDownLatch start = new java.util.concurrent.CountDownLatch(1);
java.util.concurrent.CountDownLatch done = new java.util.concurrent.CountDownLatch(a.length);
java.util.List<Integer> results = java.util.Collections.synchronizedList(new java.util.ArrayList<Integer>());
for (int i = 0; i < a.length; i++) {
final int value = a[i];
new Thread(() -> {
try {
// Step 2: Every worker waits here until the gate is open.
start.await();
results.add(value * 2);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
} finally {
// Step 3: Each worker counts the done latch down once, even if it failed.
done.countDown();
}
}).start();
}
try {
// Step 4: Open the gate, then wait for all workers to finish.
start.countDown();
done.await();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
java.util.List<Integer> copy = new java.util.ArrayList<Integer>(results);
java.util.Collections.sort(copy);
int[] out = new int[copy.size()];
for (int i = 0; i < out.length; i++) {
out[i] = copy.get(i);
}
return out;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
System.out.println(Arrays.stream(solve(a)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
}
}
Hints (2)
- Why sort at the end?
- What happens if a worker fails before it counts down?