Threads and semaphores in TPSIT: concurrency explained

End of September 2026, technical institute, computer science and telecommunications track: in Year 4, TPSIT (Technologies and Design of IT and Telecommunications Systems) opens the year with processes and threads, then quickly arrives at concurrency proper: that of programs that do several things at once and can interfere with one another. The first test, often a written paper plus a practical test at the computer, falls in five to eight weeks, so between the end of October and November.

If in Year 4 you have already tackled classes in C++ in Systems (I talk about it in Classes and objects in Year 4 computing), here the conceptual jump is different: it is no longer organising data inside an object, it is making several flows of execution coexist that read and write the same variables without treading on each other’s toes.

Program, process and thread

The first block is terminological, and must be kept well distinct because it is the starting point of every later question:

• Program: the written code, static, sitting on disk: a sequence of instructions that isn’t running anything.
• Process: a program in execution, with its own isolated memory space (variables, stack, heap) and its own resources assigned by the operating system. Two different processes don’t share memory, unless there are explicit mechanisms for communication between processes.
• Thread: a flow of execution inside a process. A process can have several threads, and these threads share the same memory space of the process that contains them. It is precisely this sharing that is the source of all the problems we will see.

A process can be in different states during its life: ready (waiting for the CPU), running, blocked (waiting for a resource, for example input from the keyboard), terminated. The operating system moves from one process to another with the context switch: it saves the state of the running process and restores that of the next, an operation that has a cost in machine time even if it takes only a few microseconds.

Why concurrency creates problems: the race condition

The problem arises exactly from the sharing of memory between threads. Imagine two threads that both execute the instruction x = x + 1 on the same shared variable x, starting from x = 0. It seems obvious that the final result is x = 2, but it isn’t guaranteed, because x = x + 1 is not a single atomic operation: it breaks down into three separate steps at CPU level:

1. Read the current value of x into a register.
2. Increment the register by 1.
3. Write the register back into x.

If the operating system interrupts the first thread exactly after step 1 (read) and starts the second thread, this interleaving happens:

Both threads read x = 0 before the other wrote its increment, so the final result is x = 1, not x = 2: one increment has been lost. This phenomenon is called a race condition: the final result depends on the unpredictable order in which the threads are scheduled, and changes from one run to the next, which is why these bugs are among the hardest to reproduce and fix.

The stretch of code where the shared resource is accessed (here, the three instructions of read-increment-write) is called the critical section. The problem of concurrency always comes down to guaranteeing mutual exclusion: only one thread at a time can execute the critical section on a given resource.

Dijkstra’s semaphores

The classic tool for guaranteeing mutual exclusion is the semaphore, introduced by Edsger Dijkstra. A semaphore is an integer variable associated with two atomic operations (indivisible, not interruptible halfway):

• P (from the Dutch proberen, “to try”; in English often wait): decrements the semaphore; if the resulting value is negative, the thread blocks and waits.
• V (from the Dutch verhogen, “to increase”; in English often signal): increments the semaphore, and if there are waiting threads it unblocks one.

A mutex (mutual exclusion) is simply a binary semaphore, that is one that can take only the values 0 and 1: it represents a resource that can be owned by one thread at a time. The classic pattern for protecting a critical section is:

mutex.wait()      # P: enter the critical section
# ... critical section ...
mutex.signal()    # V: leave the critical section

In Python this is written with threading.Lock, which is conceptually a mutex:

import threading

lock = threading.Lock()
x = 0

def increment():
    global x
    with lock:      # acquires the lock, releases it automatically on exit
        x = x + 1

In C with the pthread library the same pattern uses pthread_mutex_lock and pthread_mutex_unlock around the critical section. Many schools use Java for these examples (synchronized, wait()/notify()): the concepts are identical, only the syntax changes. Here we see them in Python and C because those are the languages we work in.

The producer-consumer problem

It is the classic example that brings together mutual exclusion and synchronisation: a producer generates data and puts it into a buffer of limited size, a consumer takes it out and processes it. You need three semaphores:

• mutex (binary, initialised to 1): protects access to the buffer.
• empty (initialised to N, the capacity of the buffer): counts how many free spaces there are.
• full (initialised to 0): counts how many items are ready to be consumed.

Producer pseudocode:

repeat:
    produce_item()
    empty.wait()      # wait for a free space
    mutex.wait()      # enter the critical section on the buffer
    insert_into_buffer(item)
    mutex.signal()
    full.signal()     # signal that an item is ready

Consumer pseudocode:

repeat:
    full.wait()        # wait for an item to be ready
    mutex.wait()       # enter the critical section on the buffer
    item = take_from_buffer()
    mutex.signal()
    empty.signal()     # signal that space has been freed
    consume(item)

The order of the two wait() calls before mutex.wait() is not accidental: first you wait for the resource to be available (space or item), then you acquire the mutex to manipulate the buffer. Reversing this order is exactly the typical mistake I talk about below.

Deadlock and Coffman’s conditions

A deadlock is a situation in which two or more threads remain blocked forever, each waiting for a resource owned by another thread that is also blocked. The standard teaching example is the dining philosophers problem: five philosophers sit at a round table, between each pair there is a single fork, and to eat a philosopher needs both forks, the one on their left and the one on their right. If all five grab the fork on their left at the same time, each waits forever for the one on their right, already held by their neighbour: nobody eats any more.

A deadlock occurs only if all four Coffman conditions are present at the same time:

1. Mutual exclusion: at least one resource is owned exclusively by one thread at a time.
2. Hold and wait: a thread holds a resource while waiting for another.
3. No pre-emption: a resource can’t be taken from a thread by force, only the thread itself can release it.
4. Circular wait: there is a circular chain of threads, each waiting for a resource owned by the next in the chain.

Breaking even just one of these four conditions avoids the deadlock. In the philosophers’ case, for example, it is enough to require that at least one philosopher grabs the right fork first instead of the left, breaking the symmetry and therefore the circular wait.

The typical mistake

The most frequent mistake in producer-consumer is reversing the order of the waits: acquiring mutex first and only afterwards empty (or full). It looks like a stylistic detail, but it isn’t: if the producer acquires mutex and then blocks on empty.wait() because the buffer is full, it keeps the mutex locked, and the consumer, which needs precisely that mutex to free space in the buffer, can never get in. It is a deadlock produced by two lines swapped in place.

The other mistake, a more conceptual one, is to think “the race condition happens rarely anyway, in practice nobody notices”: it is true that on a fast machine the problematic interleaving may not show up for thousands of runs, but sooner or later it appears, typically in production, under load, at the worst moment. In a test, code that “almost always works” without a protected critical section is wrong all the same.

Three worked exercises

Exercise 1: which final values can x take? Two threads both execute, with no protection at all, the instruction x = x + 1 on a shared variable initialised to x = 0. Which final values are possible?

If the two executions never overlap (one thread completes read-increment-write before the other begins), the result is x = 2. If instead, as in the example seen above, both threads read x = 0 before either writes its increment, one update is lost and the result is x = 1. It is not possible to get x = 0 (neither thread can “not increment”) nor a value greater than 2 (each thread increments at most once). So the possible final values are 1 or 2, nothing else.

Exercise 2: completing the producer-consumer scheme. Given the producer pseudocode with a missing line, complete it:

repeat:
    produce_item()
    empty.wait()
    ______________      # line to complete
    insert_into_buffer(item)
    mutex.signal()
    full.signal()

The missing line is mutex.wait(): the mutex must be acquired after checking the availability of space (empty.wait()) and before manipulating the buffer, otherwise you risk the deadlock described above.

Exercise 3: recognising a deadlock. Two threads A and B must both access two resources, R1 and R2, protected by two separate mutexes. Thread A executes R1.wait() then R2.wait(). Thread B executes R2.wait() then R1.wait(). Can a deadlock occur? If so, which of the four Coffman conditions is best broken, and how?

Yes: if A acquires R1 and, before it proceeds, B acquires R2, then A stays blocked waiting for R2 (owned by B) and B stays blocked waiting for R1 (owned by A): a classic circular wait between just two threads. The simplest condition to break is circular wait: just impose on both threads the same order of acquiring resources (for example always R1 first, then R2, for B too). In this way a cycle of waiting can never form.

There is no dedicated practice test on this topic on the site yet, as for no other technical-school computing topic: you will find all those available, on other subjects, at /simulazioni/.

To understand where threads read and write, you need the basics of pointers and memory in C; for how the CPU that runs them works, the post on Von Neumann architecture.

If concurrency is creating more doubts than certainties, or you want to revise it together before the practical test, you will find all the subjects we follow at /materie/informatica/; the first introductory call of 30 minutes is free, you will find it at /contatti/.