Solved Java exam exercise: split an array among K threads, accumulate with synchronized and wait with join, with tested code and common mistakes.
Updated on
Exam Code Java Operating systems Exam level Tested code
A power substation logs N consumption readings, in kilowatts, and they must be analysed in parallel by K Java threads. A peak is any reading strictly greater than a threshold T. Compute the sum of all readings and the total number of peaks. Also report the partial result obtained by each thread.
Splitting the work. The readings are divided into K contiguous blocks that are as balanced as possible. Let base = N / K and remainder = N % K. Thread h, numbered from 0, receives base + 1 readings if h < remainder and base readings otherwise. Blocks are assigned in order: thread 0 starts at index 0, and each thread starts where the previous one ended. A thread may receive an empty block.
Synchronisation. Each thread scans only its own block and computes its sum and peak count in local variables. When it finishes, it contributes both values exactly once to a shared Accumulator object, whose methods must be synchronized. The main thread starts the K threads and waits for all of them with join() before printing anything. You may not use java.util.concurrent.
Input (standard input): a first line with three integers N K T, where 0 ≤ N ≤ 100000, 1 ≤ K ≤ 16 and 0 ≤ T ≤ 10^9. It is followed by N space-separated integers, each between 0 and 10^9. If N is 0, there is no further data.
Output (standard output): K lines, one per thread in order of id, in the format Thread h: [begin, end) sum=S peaks=P, where [begin, end) is the half-open index interval of the block. Then a final line Total: sum=S peaks=P with the values read from the accumulator. The output must be identical on every run, whatever order the scheduler runs the threads in.
Sample input
10 3 50
12 70 55 3 90 41 50 51 8 100Expected output
Thread 0: [0, 4) sum=140 peaks=2
Thread 1: [4, 7) sum=181 peaks=1
Thread 2: [7, 10) sum=159 peaks=2
Total: sum=480 peaks=5- Balanced split of the N readings into K contiguous blocks: the first N mod K threads get one extra element, and no index is lost or repeated
- 0.75
- Creation of the K threads, start() called on all of them before joining any, and correct join() before reading the results
- 0.75
- Shared accumulator protected by synchronized methods, with one contribution per thread rather than one per element
- 0.5
- Exact output format, long for the sums, and edge cases (N = 0, K > N)
- 0.5
Hints
Hint 1 · How do I compute block boundaries without gaps?
Keep a variable pos that starts at 0. For each thread h, its block starts at pos and has length base + (h < remainder ? 1 : 0). Then advance pos by that length. After the loop, pos must equal N exactly. Check by hand with N = 10 and K = 3: the sizes must be 4, 3 and 3.
Hint 2 · What needs protecting, and what does not?
The only shared state is in the accumulator: the total sum and the total peak count. Scanning a block uses local variables of run(). They live on each thread's own stack and need no lock. If each thread calls the synchronized method only once, at the end, contention is minimal. Calling it inside the loop would still be correct, but it throws away almost all the parallelism.
Hint 3 · Where do the join() calls go so the threads do not run one after another?
Use two separate loops. The first calls start() on every thread, and only then the second calls join() on every thread. If you call start() and join() in the same iteration, each thread finishes before the next one is created. To keep the output deterministic, print only after the second loop. Print in array order, not in the order the threads happen to finish.
Solution
Explained solution
The solution separates three responsibilities. The Accumulator class holds the shared state. The Worker class extends Thread and processes one block. The main method splits the work, launches the threads, waits with join() and prints the output. Each worker also stores its partial result in its own fields. That way the main thread can print it afterwards without depending on the execution order.
The pattern here is the classic fork–join shape: divide the work, launch the threads, wait for them, combine the results. If you are revising Java for exams more broadly, the top 10 university exam exercises in Java collects other typical questions worth practising alongside this one.
import java.io.IOException;
public class Main {
// Shared state: only touched through synchronized methods.
static class Accumulator {
private long sum;
private int peaks;
synchronized void contribute(long s, int p) {
sum += s;
peaks += p;
}
synchronized long sum() {
return sum;
}
synchronized int peaks() {
return peaks;
}
}
// Each worker processes the interval [begin, end) of the array.
static class Worker extends Thread {
private final int[] data;
private final int begin;
private final int end;
private final int threshold;
private final Accumulator acc;
private long localSum;
private int localPeaks;
Worker(int[] data, int begin, int end, int threshold, Accumulator acc) {
this.data = data;
this.begin = begin;
this.end = end;
this.threshold = threshold;
this.acc = acc;
}
@Override
public void run() {
long s = 0;
int p = 0;
for (int i = begin; i < end; i++) {
s += data[i];
if (data[i] > threshold) {
p++;
}
}
localSum = s;
localPeaks = p;
acc.contribute(s, p); // a single critical section per thread
}
}
public static void main(String[] args) throws IOException, InterruptedException {
String[] tok = new String(System.in.readAllBytes()).trim().split("\\s+");
int n = Integer.parseInt(tok[0]);
int k = Integer.parseInt(tok[1]);
int threshold = Integer.parseInt(tok[2]);
int[] data = new int[n];
for (int i = 0; i < n; i++) {
data[i] = Integer.parseInt(tok[3 + i]);
}
Accumulator acc = new Accumulator();
Worker[] workers = new Worker[k];
int base = n / k;
int remainder = n % k;
int pos = 0;
for (int h = 0; h < k; h++) {
int size = base + (h < remainder ? 1 : 0);
workers[h] = new Worker(data, pos, pos + size, threshold, acc);
pos += size;
}
for (Worker w : workers) {
w.start();
}
for (Worker w : workers) {
w.join();
}
StringBuilder sb = new StringBuilder();
for (int h = 0; h < k; h++) {
Worker w = workers[h];
sb.append("Thread ").append(h).append(": [").append(w.begin).append(", ").append(w.end)
.append(") sum=").append(w.localSum).append(" peaks=").append(w.localPeaks).append('\n');
}
sb.append("Total: sum=").append(acc.sum())
.append(" peaks=").append(acc.peaks()).append('\n');
System.out.print(sb);
}
}Reading. The program reads the whole input at once with readAllBytes() and splits it into tokens. This means N = 0 needs no special handling. After trim() there are exactly three tokens, and the loop that fills data never runs. The "no readings" test shows the result: two empty blocks [0, 0) and a total of zero.
Splitting. The loop over h computes size = base + (h < remainder ? 1 : 0) and creates each Worker with the interval [pos, pos + size). In the example, N = 10 and K = 3, so base = 3 and remainder = 1. Thread 0 gets 4 readings and the other two get 3 each. The intervals are [0, 4), [4, 7) and [7, 10). When K exceeds N, as in the test with 2 readings and 4 threads, base is 0 and the last two threads get empty blocks.
Each thread's work. Inside run(), the variables s and p are local and nobody else can see them. That is why the loop needs no lock. When it finishes, the thread copies its results into localSum and localPeaks. It then calls acc.contribute(s, p) exactly once. Because contribute is synchronized, the updates sum += s and peaks += p run under mutual exclusion on the accumulator's monitor. No update is lost, even if two threads finish at the same moment.
Starting and waiting. The two separate loops are what make the program parallel. The first calls start() on every worker, so all of them become runnable. The join() loop then blocks the main thread until each worker has finished. If a worker is already done, its join() returns immediately. The finishing order does not matter, because the output is built by walking workers by index.
Visibility. The main thread reads w.localSum without synchronized, and the read is still correct. The Java Memory Model states that every action of a thread happens before another thread returns from a join() on it. The totals are read through acc.sum() and acc.peaks(), which are also synchronized. Access to the shared object therefore stays uniform and does not rely on that subtler argument.
Types. The sum is a long. In the "sum that overflows int" test, the first block alone adds up to 2000000000 and the total reaches 3999999999. That value does not fit in an int, whose maximum is 2147483647. The peak count can stay an int, because it never exceeds N.
Test cases
| Case | Input | Expected output | Actual output | Result |
|---|---|---|---|---|
| Statement example | 10 3 50
12 70 55 3 90 41 50 51 8 100 | Thread 0: [0, 4) sum=140 peaks=2
Thread 1: [4, 7) sum=181 peaks=1
Thread 2: [7, 10) sum=159 peaks=2
Total: sum=480 peaks=5 | Thread 0: [0, 4) sum=140 peaks=2
Thread 1: [4, 7) sum=181 peaks=1
Thread 2: [7, 10) sum=159 peaks=2
Total: sum=480 peaks=5 | OK |
| Single thread | 5 1 0
0 1 2 3 0 | Thread 0: [0, 5) sum=6 peaks=3
Total: sum=6 peaks=3 | Thread 0: [0, 5) sum=6 peaks=3
Total: sum=6 peaks=3 | OK |
| More threads than readings | 2 4 5
7 5 | Thread 0: [0, 1) sum=7 peaks=1
Thread 1: [1, 2) sum=5 peaks=0
Thread 2: [2, 2) sum=0 peaks=0
Thread 3: [2, 2) sum=0 peaks=0
Total: sum=12 peaks=1 | Thread 0: [0, 1) sum=7 peaks=1
Thread 1: [1, 2) sum=5 peaks=0
Thread 2: [2, 2) sum=0 peaks=0
Thread 3: [2, 2) sum=0 peaks=0
Total: sum=12 peaks=1 | OK |
| No readings | 0 2 10 | Thread 0: [0, 0) sum=0 peaks=0
Thread 1: [0, 0) sum=0 peaks=0
Total: sum=0 peaks=0 | Thread 0: [0, 0) sum=0 peaks=0
Thread 1: [0, 0) sum=0 peaks=0
Total: sum=0 peaks=0 | OK |
| Sum that overflows int | 4 2 999999999
1000000000 1000000000 1000000000 999999999 | Thread 0: [0, 2) sum=2000000000 peaks=2
Thread 1: [2, 4) sum=1999999999 peaks=1
Total: sum=3999999999 peaks=3 | Thread 0: [0, 2) sum=2000000000 peaks=2
Thread 1: [2, 4) sum=1999999999 peaks=1
Total: sum=3999999999 peaks=3 | OK |
| Exact division | 6 2 3
1 2 3 4 5 6 | Thread 0: [0, 3) sum=6 peaks=0
Thread 1: [3, 6) sum=15 peaks=3
Total: sum=21 peaks=3 | Thread 0: [0, 3) sum=6 peaks=0
Thread 1: [3, 6) sum=15 peaks=3
Total: sum=21 peaks=3 | OK |
Actual outputs: code compiled with Java 21.0.12.1 (Temurin) and run in an isolated container on 16 October 2026.
Complexity
Time. Each reading is scanned by exactly one thread, so the total work is O(N), plus O(K) to create, start and join the threads. With P processors, the ideal wall-clock time is O(N/K + K) when K ≤ P. The grading sandbox has a single CPU, so the threads interleave and there is no real speed-up, but the result is identical. There are K critical sections, one per thread, each costing O(1).
Memory. The array data takes O(N) and is shared by reference: no thread copies its block. Each Worker adds O(1) fields plus its own stack, so the extra memory is O(K). For N = 100000 integers the array takes about 400 KB, far below any reasonable limit.
Common mistakes
- Calling
join()right afterstart()in the same loop. The result is still correct, but the threads run one after another and the parallelism the question asks for disappears. - Adding directly to a
static long totalfield fromrun()withoutsynchronized. The statementtotal += xis a read, an add and a write, so two threads can interleave and lose contributions. On top of that, writes to a non-volatilelongare not even guaranteed to be atomic. - Using
N / Kas the block size for every thread. The lastN % Kreadings are silently dropped. A related mistake is giving the whole remainder to the last thread, which does not follow the split the question specifies. - Calling
run()instead ofstart(). The code then executes sequentially on the main thread and no new thread is ever created. - Printing from inside
run(). The line order then depends on the scheduler and the output is no longer deterministic. - Using
intfor the sum. With readings up to 10^9, three values are enough to overflow it.
Variants
No shared object: each thread writes to its own slot
If each thread writes only to position id of two arrays, sums and peaks, no variable is written by two threads and synchronized is unnecessary. The main thread combines the results after the join() calls, which guarantee visibility. This is the most efficient version. A professor may still insist on the accumulator, precisely to assess mutual exclusion. The bounds begin and end are written before start(), which also creates a happens-before edge.
public class Main {
public static void main(String[] args) throws Exception {
String[] tok = new String(System.in.readAllBytes()).trim().split("\\s+");
int n = Integer.parseInt(tok[0]);
int k = Integer.parseInt(tok[1]);
int threshold = Integer.parseInt(tok[2]);
int[] data = new int[n];
for (int i = 0; i < n; i++) {
data[i] = Integer.parseInt(tok[3 + i]);
}
long[] sums = new long[k];
int[] peaks = new int[k];
int[] begin = new int[k];
int[] end = new int[k];
Thread[] threads = new Thread[k];
int base = n / k, remainder = n % k, pos = 0;
for (int h = 0; h < k; h++) {
begin[h] = pos;
pos += base + (h < remainder ? 1 : 0);
end[h] = pos;
final int id = h;
threads[h] = new Thread(() -> {
long s = 0;
int p = 0;
for (int i = begin[id]; i < end[id]; i++) {
s += data[i];
if (data[i] > threshold) p++;
}
sums[id] = s;
peaks[id] = p;
});
}
for (Thread t : threads) t.start();
for (Thread t : threads) t.join();
long total = 0;
int totalPeaks = 0;
StringBuilder sb = new StringBuilder();
for (int h = 0; h < k; h++) {
total += sums[h];
totalPeaks += peaks[h];
sb.append("Thread ").append(h).append(": [").append(begin[h]).append(", ").append(end[h])
.append(") sum=").append(sums[h]).append(" peaks=").append(peaks[h]).append('\n');
}
sb.append("Total: sum=").append(total).append(" peaks=").append(totalPeaks).append('\n');
System.out.print(sb);
}
}Producer and consumer with a bounded buffer
Another classic question replaces the static split with a dynamic one. A producer thread puts readings into a buffer of capacity C, and K consumers take them out and accumulate them. The buffer needs two synchronized methods. put waits with while (full) wait(); and take waits with while (empty) wait();. Both call notifyAll() after changing the buffer. Using while rather than if guards against spurious wake-ups. To terminate, the producer inserts K end markers, one per consumer, and the main thread joins all threads.
On the syllabus
Thread scheduling and process synchronisation are core operating-systems topics well beyond the English-speaking world. The syllabus of Operating Systems at Universidad Tecnológica Nacional (FRBA) lists threads in process scheduling and inter-process communication and synchronisation. The programme of IIC2333 Operating Systems and Networks at Pontificia Universidad Católica de Chile covers synchronisation and communication between processes. This exercise practises exactly that material: launching threads, waiting for them and protecting a shared resource.
Process management also appears in the syllabus of ELO321 Operating Systems Theory at Universidad Técnica Federico Santa María, which includes deadlock. The syllabus of CC3301 Systems Software Programming at Universidad de Chile focuses on heavyweight processes with fork, exec and pipes. That makes a useful contrast: processes there do not share memory and talk through pipes, whereas here the threads share one array and access must be synchronised.
Related articles from LaRebelión
Solved exercise: Java serialization with transient fields
Solved exercise: interfaces, default methods and multiple implementation in Java
Solved exercise: polymorphism and dynamic binding in JavaProduced with AI support and reviewed by the newsroom
Comentarios
Publicar un comentario