Split sensor readings across Python threads, compute partial summaries and merge them without race conditions or output that depends on thread timing.
Exam Code Python Operating systems Exam level Tested code
A weather station produces a list of integer temperature readings, in tenths of a degree. You must compute a global summary of the readings: their sum, minimum, maximum and count. The work is split among several threads, one per chunk of the list, and the partial results are merged afterwards.
Input. The first line holds two integers separated by a space. T is the number of threads to start (T ≥ 1) and N is the number of readings (N ≥ 0). The second line holds the N readings separated by spaces. If N is 0, that line may be empty or missing. Every reading is an integer whose absolute value is below 1,000,000,000.
Split. The readings are divided into T contiguous, consecutive chunks that keep the original order. Let q = N // T and r = N % T. The first r chunks hold q + 1 readings and the remaining T - r chunks hold q. If T > N, the last threads receive an empty chunk. Exactly T threads are always started. Each thread computes the summary of its own chunk: count, sum, minimum and maximum.
Merge. The program waits for every thread and then combines the partial summaries. An empty chunk must not affect the global minimum or maximum.
Output. First print one line per thread, in index order from 0 to T-1, with the format thread i: n=count sum=S min=M max=X. For an empty chunk print thread i: empty instead. Then print a final line total: n=count sum=S min=M max=X, or total: empty if there are no readings. The output must not depend on the order in which the threads finish.
Write a complete Python program that uses the threading module and reads from standard input.
Sample input
3 7
12 -5 30 8 0 25 -14Expected output
thread 0: n=3 sum=37 min=-5 max=30
thread 1: n=2 sum=8 min=0 max=8
thread 2: n=2 sum=11 min=-14 max=25
total: n=7 sum=56 min=-14 max=30- Correct split into contiguous chunks, including an uneven division and more threads than readings
- 0.75
- All threads created and joined, with no unprotected accumulation into a shared global variable
- 0.75
- Per-thread partial summary (count, sum, minimum, maximum) and a correct merge of the partials
- 1.0
- Input parsing and exact output format, including the empty case
- 0.5
Hints
Hint 1 · How do I work out where each thread's chunk starts and ends?
Loop over the thread indices from 0 to T-1 and keep a pointer start. Thread i gets q + 1 readings if i < r and q otherwise. Its chunk ends at start + size, and the next thread starts where this one ended. Check by hand that N = 7, T = 3 gives sizes 3, 2 and 2.
Hint 2 · Where does each thread store its result without clobbering the others?
Before you start any thread, allocate a list results of length T. Make thread i write only to position i. No two threads then touch the same slot, so you need no lock. Pass each thread its index through args in the threading.Thread constructor.
Hint 3 · How do I merge the partials, and what about empty chunks?
Call join() on every thread, then walk results in order. Represent an empty chunk as None and skip it while merging. Add up the counts and the sums, take the minimum of the minima and the maximum of the maxima. Print only from the main thread, never from the worker threads.
Solution
Explained solution
The solution follows the classic split, compute, merge pattern. The main thread reads the data and decides the bounds of each chunk. It then starts T threads and waits for all of them. Each thread writes its partial summary into its own slot of a shared list. No slot is ever written by two threads, so the only synchronisation needed is join.
Only the main thread prints, and only after the merge. That makes the output deterministic however the scheduler interleaves the threads.
import sys
import threading
def summarise(data, start, end, index, results):
"""Compute the summary of data[start:end] and store it in results[index]."""
if start >= end:
results[index] = None
return
count = 0
total = 0
lowest = data[start]
highest = data[start]
for k in range(start, end):
v = data[k]
count += 1
total += v
if v < lowest:
lowest = v
if v > highest:
highest = v
results[index] = (count, total, lowest, highest)
def fmt(res):
count, total, lowest, highest = res
return f"n={count} sum={total} min={lowest} max={highest}"
def main():
lines = sys.stdin.read().split("\n")
t, n = map(int, lines[0].split())
data = []
if n > 0:
data = list(map(int, lines[1].split()))
q, r = divmod(n, t)
results = [None] * t
threads = []
start = 0
for i in range(t):
size = q + 1 if i < r else q
end = start + size
th = threading.Thread(target=summarise,
args=(data, start, end, i, results))
threads.append(th)
th.start()
start = end
for th in threads:
th.join()
out = []
for i, res in enumerate(results):
if res is None:
out.append(f"thread {i}: empty")
else:
out.append(f"thread {i}: {fmt(res)}")
partials = [res for res in results if res is not None]
if not partials:
out.append("total: empty")
else:
count = sum(p[0] for p in partials)
total = sum(p[1] for p in partials)
lowest = min(p[2] for p in partials)
highest = max(p[3] for p in partials)
out.append(f"total: {fmt((count, total, lowest, highest))}")
print("\n".join(out))
main()The function summarise is the body of every thread. It receives the whole list, the bounds start and end of its chunk, its index and the shared results list. An empty chunk stores None. Otherwise the function walks its range once, accumulating count, sum, minimum and maximum, and stores the tuple in results[index]. Initialising lowest and highest with the first element of the chunk avoids arbitrary sentinel values.
In main, divmod(n, t) yields q and r. The loop over i computes each chunk's size, with q + 1 for the first r threads, and moves start forward to end. The chunks are therefore contiguous, cover the whole range and never overlap. Each thread is created and started in the same loop and kept in threads so it can be joined later.
The joins happen in a separate, second loop, and this matters. Calling join right after start would make the main thread wait for each worker before creating the next. The threads would run strictly one after another, which defeats the point of splitting the work.
The merge runs in the main thread after the joins. The list partials filters out the None entries, so an empty chunk cannot pollute the minimum or maximum. The partials are then combined with sum, min and max. There is no race because each thread writes only to its own slot. Waiting with join guarantees that the main thread reads finished results.
Now the tests. In the example, T = 3 and N = 7 give sizes 3, 2 and 2, and the total combines all seven readings. With T = 5, N = 3, threads 3 and 4 get empty chunks and print empty. With N = 0, every chunk is empty and so is the total. With one thread, that thread's line matches the total. The all-negative case checks that minimum and maximum are not initialised to zero.
Test cases
| Case | Input | Expected output | Actual output | Result |
|---|---|---|---|---|
| Example: 7 readings over 3 threads | 3 7
12 -5 30 8 0 25 -14 | thread 0: n=3 sum=37 min=-5 max=30
thread 1: n=2 sum=8 min=0 max=8
thread 2: n=2 sum=11 min=-14 max=25
total: n=7 sum=56 min=-14 max=30 | thread 0: n=3 sum=37 min=-5 max=30
thread 1: n=2 sum=8 min=0 max=8
thread 2: n=2 sum=11 min=-14 max=25
total: n=7 sum=56 min=-14 max=30 | OK |
| More threads than readings | 5 3
4 9 -2 | thread 0: n=1 sum=4 min=4 max=4
thread 1: n=1 sum=9 min=9 max=9
thread 2: n=1 sum=-2 min=-2 max=-2
thread 3: empty
thread 4: empty
total: n=3 sum=11 min=-2 max=9 | thread 0: n=1 sum=4 min=4 max=4
thread 1: n=1 sum=9 min=9 max=9
thread 2: n=1 sum=-2 min=-2 max=-2
thread 3: empty
thread 4: empty
total: n=3 sum=11 min=-2 max=9 | OK |
| No readings | 2 0
| thread 0: empty
thread 1: empty
total: empty | thread 0: empty
thread 1: empty
total: empty | OK |
| A single thread | 1 4
10 20 30 40 | thread 0: n=4 sum=100 min=10 max=40
total: n=4 sum=100 min=10 max=40 | thread 0: n=4 sum=100 min=10 max=40
total: n=4 sum=100 min=10 max=40 | OK |
| Even split, all negative values | 2 6
-7 -3 -9 -1 -8 -2 | thread 0: n=3 sum=-19 min=-9 max=-3
thread 1: n=3 sum=-11 min=-8 max=-1
total: n=6 sum=-30 min=-9 max=-1 | thread 0: n=3 sum=-19 min=-9 max=-3
thread 1: n=3 sum=-11 min=-8 max=-1
total: n=6 sum=-30 min=-9 max=-1 | OK |
Actual outputs: code compiled with Python 3.13.16 and run in an isolated container on 15 November 2026.
Complexity
Each element is visited exactly once, by exactly one thread, and the merge walks T partials. The total work is therefore O(N + T), and with a balanced split no thread handles more than ⌈N/T⌉ elements. In CPython, threads do not speed up a pure computation loop like this one because of the GIL, so wall-clock time stays proportional to N.
That is fine for this question, which is about the structure of the split and the merge. The same structure carries over unchanged to processes, or to threads in a runtime without a global lock. If you want to compare it with a language where threads do run in parallel, see the Java version of splitting work across threads.
Memory is O(N + T): the N readings, the list of T thread objects and the list of T results. Each thread also gets its own stack. Starting thousands of threads to process a handful of readings is therefore counterproductive.
Common mistakes
- Calling
join()immediately afterstart()inside the same loop. The threads then run one at a time and there is no real concurrency. - Splitting with
N // Tand ignoring the remainder. The lastN % Treadings are never processed and the total sum comes out wrong. - Initialising the minimum and maximum to 0 or to another fixed value. This fails when all readings are negative or all are positive. For the same reason, an empty chunk must not contribute a 0 to the global minimum.
- Having each thread update a shared global, for example
total += v, without a lock. That is a race condition, and the result can change from one run to the next. - Printing from the worker threads. The order of the lines then depends on the scheduler and the output is no longer deterministic.
- Forgetting the
N = 0case. Reading a missing second line, or accessingdata[start]for an empty chunk, raises anIndexError.
Variants
A single accumulator protected by a lock
Suppose that, instead of one slot per thread, all threads update a single shared dictionary holding count, sum, minimum and maximum. Every update must then happen inside with lock:, where lock = threading.Lock(). The lock is required because reading, comparing and writing back are not one atomic step.To limit contention, each thread should first compute its local summary and take the lock only once, at the end, to fold that summary into the global one. The result is identical, but you have added a critical section. The independent-slot solution avoids that cost entirely.
Dynamic distribution with a task queue
If the cost per reading were uneven, a static split could leave some threads idle while others still work. Cut the list into small blocks and put them in a queue.Queue. Each of the T threads keeps taking blocks until the queue is empty, appending its partials to a list of its own. At the end, merge all the partials.You gain load balancing. In exchange you pay a little more bookkeeping, and the processing order is no longer fixed in advance. The per-thread output lines would also have to be redefined.
On the syllabus
Concurrency, processes and threads belong to the systems curriculum in the US. The schedule of Carnegie Mellon's 15-213 Introduction to Computer Systems lists lectures on processes and multitasking. Stanford's CS110 Principles of Computer Systems covers the principles of computer systems, including processes. The materials of MIT's 6.033 Computer System Engineering address systems topics through to distributed systems. This exercise is practice material for those ideas using only Python's standard library; it does not claim that any of these courses sets it.
Further afield, the syllabus of UNAM's Introducción a las Ciencias de la Computación includes runtime memory management and runtime error handling, which form useful background for reasoning about shared data between threads.
Related articles from LaRebelión
Solved exercise: sorting and binary search with cost analysis in Python
Solved exercise: streaks and maximum in a list in Python
Solved exercise: dictionaries, sets and tuples in PythonArticle generated with AI.larebelion
Comentarios