Thread-Safe Counter
Problem
Several threads increase the same counter. Read the number of threads t and the number of increments c for each thread. Print the final counter value. The correct result is t * c, so no update may be lost.
Constraints
- 1 <= t <= 32
- 0 <= c <= 10^5
Examples
Input
4 1000
Output
4000
Solutions
counter++ is three steps: read, add, write. Two threads can read the same value and both write value + 1, so one update is lost. AtomicLong (Java) or a lock (Python) makes the update safe.
/*
* Problem : Count with many threads.
* Input : Threads t and increments c.
* Output : The final counter.
* Approach: Make each increment atomic.
* Time : O(t * c)
* Space : O(t)
* 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 long solve(long a, long b) {
// Step 1: AtomicLong makes each increment one single step that other threads can not interrupt.
// A normal long with counter++ is three steps (read, add, write), and threads can lose updates.
java.util.concurrent.atomic.AtomicLong counter = new java.util.concurrent.atomic.AtomicLong();
Thread[] workers = new Thread[(int) a];
// Step 2: Start t threads. Each one increments the counter c times.
for (int w = 0; w < workers.length; w++) {
workers[w] = new Thread(() -> {
for (long i = 0; i < b; i++) {
counter.incrementAndGet();
}
});
workers[w].start();
}
// Step 3: Wait for all threads.
for (Thread worker : workers) {
try {
worker.join();
} catch (InterruptedException error) {
Thread.currentThread().interrupt();
}
}
return counter.get();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
System.out.println(solve(a, b));
}
}
Hints (2)
- Why can counter++ lose an update?
- Which Java class gives atomic increments?