Computer Science › Section G · Programming languages › Topic G.6

Programming concurrent activities

A web server answers thousands of visitors at once, and a game moves dozens of characters in the same instant. Programs like these are written as several activities running side by side, which brings real speed and responsiveness, and a new family of bugs.

Doing several things at once

A traditional program follows one sequence of instructions from start to finish. Many problems are easier to express as several activities that proceed together. A game might give each moving character its own small routine, started with that character's speed and position. A server might give each connected user a separate activity, so a slow user does not hold up the rest. Writing a program as multiple activities that are in progress at the same time is called concurrent programming, and languages need ways to start these activities, let them communicate, and keep them from interfering.

Concurrency and parallelism

Two words are often confused. Activities are concurrent when their lifetimes overlap, so each has started and not yet finished. They run in parallel only when they execute at literally the same instant, which requires several processor cores. On a single core, the operating system switches rapidly between activities, giving each a short time slice, so they appear simultaneous; this is the same time-sharing idea used for processes, described in the topic "Coordinating the machine: processes and scheduling". Modern processors have several cores, so concurrent programs can also run truly in parallel and finish sooner.

Threads

The usual unit of concurrent activity inside a program is a thread: an independent sequence of execution with its own position in the code and its own local variables. Java calls these threads; Ada calls them tasks. All the threads of one program share the same memory, which makes communication easy and also makes accidents possible. Starting a thread resembles calling a function, with one key difference. After an ordinary call, the caller waits until the function returns. After spawning a thread, the caller carries straight on, and both run concurrently. The caller can later wait for a thread to finish, which is called joining it.

Threads in Python

Python's standard threading module creates threads. With def fetch(name): containing time.sleep(1) and print(name, "done"), the line w = threading.Thread(target=fetch, args=("a",)) creates a thread that will run fetch("a"). Note that target is given the function itself, without brackets. Calling w.start() begins the thread and returns immediately; w.join() blocks until it has finished. One caution applies to the standard CPython interpreter: a global interpreter lock lets only one thread execute Python code at a time, so threads speed up programs that spend time waiting, such as for networks or files, rather than heavy calculation. Python 3.13 added an experimental build without this lock.

Worked example: waiting together

Each call to fetch sleeps for 1 second, standing in for a slow download. Steps: (1) Calling fetch("a"), fetch("b") and fetch("c") one after another takes about 1 + 1 + 1 = 3 seconds, because each call must finish before the next begins. (2) Instead, create three threads, one per name, then call start() on each. All three begin sleeping almost at once. (3) Call join() on each thread so the main program waits until all are done. (4) The waits overlap, so the total is about 1 second; measured with time.time(), the run takes about 3.0 seconds sequentially and about 1.0 second threaded. (5) The order of the "done" messages is not guaranteed, because the scheduler decides which thread runs when.

Shared data and race conditions

Trouble starts when threads update the same data. A statement such as seats = seats - 1 looks like one step, but the machine performs three: read the value, subtract, write the result back. If a second thread reads the value between the first thread's read and its write, one update can be lost. A bug whose outcome depends on the exact timing of threads is called a race condition. Race conditions are notoriously hard to find, because the program may work correctly thousands of times and then fail when the timing happens to line up differently.

Worked example: a lost update

A shared variable seats holds 5, and two booking threads, A and B, each run seats = seats - 1. Trace one unlucky interleaving. Steps: (1) A reads seats and gets 5. (2) Before A writes, the scheduler switches to B, which also reads 5. (3) B computes 4 and writes 4. (4) A, still holding its old reading of 5, computes 4 and writes 4. (5) Two bookings were made but seats shows 4, not 3, so one seat could be sold twice. (6) Had A finished all three steps before B began, the result would be 3. The fix is to make read, compute and write happen as one indivisible unit, so no other thread can slip in between.

Mutual exclusion and locks

Data that only one thread may use at a time has mutually exclusive access, and the code that touches it is a critical region. The common tool is a lock: a thread acquires it before entering the critical region, and any other thread trying to acquire it waits until it is released. In Python, lock = threading.Lock() creates one, and with lock: count += 1 acquires and releases it automatically around the update. Four threads each adding 1 to count 100,000 times under the lock always finish with exactly 400,000. Locks used carelessly cause new problems, such as deadlock, covered in the topic "Competition among processes: semaphores and deadlock".

Monitors: data that guards itself

Scattering lock calls through every part of a program that touches shared data is fragile: one forgotten lock corrupts everything. A more reliable design gives the data the job of controlling access to itself, so protection lives in one place. Such a self-guarding data item is called a monitor. In Java, every object can act as a monitor: methods declared synchronized can be running for only one thread at a time on a given object. Python's queue.Queue is built this way: threads can safely put items in and get them out without writing any locks themselves, which makes it a standard way to pass work between threads.

Common mistakes to avoid

Calling the function instead of passing it, as in target=fetch("a"), which runs it immediately in the main thread. Forgetting join(), so the main program uses results before the threads have produced them. Assuming threads run in the order they were started. Updating shared data without a lock because a statement looks like a single step. Treating concurrency and parallelism as the same thing. Expecting threads to speed up heavy calculation in standard Python, where the global interpreter lock prevents that.

Key takeaways

Concurrent programs contain several activities in progress at once; they are parallel only when separate cores run them at the same instant. A thread is an independent sequence of execution sharing its program's memory. Spawning a thread lets the caller continue, and joining waits for it to finish. Unprotected updates to shared data cause race conditions such as lost updates. Mutual exclusion, enforced with locks around critical regions, prevents them, and monitors place that protection inside the data itself, as with Java's synchronized methods and Python's queue.Queue.

Flashcards

Flashcard

Concurrent

Activities whose lifetimes overlap

Not necessarily at the same instant.

Test your understanding

Question 1 of 5

A laptop with one processor core runs a music player and a download at the same time. Which description is accurate?

Question 2 of 5

What is the key difference between calling a function and spawning a thread to run it?

Question 3 of 5

A shared counter holds 8. Two threads each run counter = counter + 2 with no lock, and both read 8 before either writes. What is the final value?

Question 4 of 5

Why is with lock: placed around count += 1 in a multithreaded Python program?

Question 5 of 5

Which is an example of a monitor?

← Previous topicNext topic →