Semaphore: Limit Parallel Workers
Problem
n tasks are started at the same time, but only p of them may work at once. Every task asks for a permit, works, and gives the permit back. While working, a task counts itself in an 'active' counter. Print done=N (the number of finished tasks) and then limit ok if the active counter never went above p, otherwise limit broken.
Constraints
- 1 <= n <= 20
- 1 <= p <= 20
Examples
Input
5 2
Output
done=5 limit ok
Solutions
A semaphore holds p permits. A task takes one before it works and returns it afterwards, so at most p tasks work at the same time and the others wait. The finally block makes sure that a failed task does not lose its permit.
JavaScript and TypeScript have no shared-memory threads here, so they follow the same steps in one thread.
/*
* Problem : Limit the workers.
* Input : n and p.
* Output : Two lines.
* Approach: Semaphore
* Time : O(n)
* Space : O(n)
* 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) {
int n = (int) a;
int permits = (int) b;
java.util.concurrent.Semaphore semaphore = new java.util.concurrent.Semaphore(permits);
java.util.concurrent.atomic.AtomicInteger active = new java.util.concurrent.atomic.AtomicInteger();
java.util.concurrent.atomic.AtomicInteger highest = new java.util.concurrent.atomic.AtomicInteger();
java.util.concurrent.atomic.AtomicInteger done = new java.util.concurrent.atomic.AtomicInteger();
Thread[] threads = new Thread[n];
for (int i = 0; i < n; i++) {
threads[i] = new Thread(() -> {
// Step 1: Ask for a permit. When all permits are taken, the thread waits here.
semaphore.acquireUninterruptibly();
try {
// Step 2: Count this task as active, and remember the highest value ever seen.
int now = active.incrementAndGet();
highest.accumulateAndGet(now, Math::max);
Thread.yield();
active.decrementAndGet();
done.incrementAndGet();
} finally {
// Step 3: Always give the permit back, also if the work failed.
semaphore.release();
}
});
threads[i].start();
}
for (Thread thread : threads) {
try {
thread.join();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
return new String[] {"done=" + done.get(), highest.get() <= permits ? "limit ok" : "limit broken"};
}
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)
- What happens to the (p + 1)th task?
- Why release in finally?