CS644 week 7: Multithreading

Last week

Link: /week6

Review

• Concepts: Network stack, UDP, TCP, ports
• Syscalls: socket.socket, socket.bind, socket.connect, socket.listen, socket.accept, socket.send, socket.recv

Solutions

• Make an HTTP request: week6/diy_http.py
• Write a UDP server: week6/udp_prot.py

Concurrency and parallelism

The program we have written so far have been sequential: each line executes after the next. Sequential programs are easy to write and think about. But sometimes we want to do work non-sequentially:

• Respond to user input while doing work in the background
• Handle multiple network requests at once
• Continue to do work while waiting on a blocking syscall, like waiting to acquire a lock

Concurrency is when different tasks execute independently of each other. If the tasks execute at the same time (because you have two or more CPU cores), then we have parallelism, but concurrency is possible and useful even if you only have one CPU core.

In fact, we've seen concurrency already: when we used fork to create a child process, the child and the parent executed concurrently (and possibly in parallel). It's not just processes that can execute concurrently, though: Linux allows you to spawn multiple threads of execution within the same process. And unlike processes, threads automatically share the same address space of values in memory, so it's easier for threads to communicate with each other.

Preemption and cooperation

Concurrent programming paradigms differ in whether or not the scheduler can forcibly interrupt a running task. Cooperative multitasking is when each task explicitly yields back to the scheduler. Preemptive multitasking is when tasks can be interrupted in the middle of doing work.

Multithreading on Linux (like process scheduling) is preemptive. If it weren't, then a buggy (or malicious) program with an infinite loop could freeze your system. But it makes it harder to write correct programs, because you must be prepared for your code to be interrupted at any point.

Threading in C and in Python

The syscall to start a thread is called clone:

int clone(
    int (*fn)(void*),
    void* stack,
    int flags,
    void* arg,
    ...
);

But unless you are writing your own language runtime or custom threading implementation, you probably won't call clone yourself. Instead, C programs use a threading library called pthreads.

pthreads is the basis of the Python threading module on Linux systems.

However, Python's implementation of threading, unlike pthreads, does not allow for multiple threads to run simultaneously. When Python code is running, it must hold a lock called the global interpreter lock (GIL), and only one thread can hold the GIL at once. So threads in Python are primarily a way to achieve concurrency while doing I/O, not to achieve parallelism for computationally intensive tasks.

Python threads are real OS threads, not "green" threads. A Python thread can be preempted by the OS at any time, but the GIL prevents another thread from running, e.g.,

SCHEDULER: start thread 1
PYTHON THREAD 1: acquire GIL - success
PYTHON THREAD 1: start running some code
SCHEDULER: stop thread 1, start thread 2
PYTHON THREAD 2: acquire GIL - blocked
SCHEDULER: stop thread 2, start some other thread
...
SCHEDULER: start thread 1
PYTHON THREAD 1: continues work

Python data structures

Builtin Python data structures like lists and dictionaries are thread-safe by virtue of the GIL. In free-threaded Python, each list and dictionary has its own lock to maintain thread safety.

Python code that you write is not necessarily thread-safe, even with the GIL, as we shall see later in the lesson.

The Python threading interface

The threading module

Threads in Python are managed by Thread objects from the threading module. The three essential methods are:

• The constructor: pass in target as the function to invoke in the thread, and args as the arguments to pass to the function
• Thread.start: spawn a new thread
• Thread.join: block until a thread exits

import time
import threading

def do_work(x, y):
  time.sleep(1)
  print("Computed:", x + y)

t1 = threading.Thread(target=do_work, args=(2, 2))
t2 = threading.Thread(target=do_work, args=(4, 4))
# Threads have _not_ yet started.

t1.start()
t2.start()
# Threads have now started. `start` returns immediately.

t1.join()
t2.join()
# Wait for the threads to finish. This should take 1 sec, not 2.

Unlike fork, Thread.start does not return twice. It returns immediately in the thread that called it, and concurrently starts executing the target function in a newly-spawned thread.

A thread exits when the target function returns. Unlike processes, threads do not have exit codes.

The _thread module

_thread is the lowest-level threading functionality that the Python standard library exposes. The core of the interface is just two things:

• A function to start a new thread
• A lock object

threading is written in pure Python on top of _thread, while _thread itself is written in C.

Exercise: Thread experiments

• What happens when a thread raises an exception instead of exiting normally?
• What if I fall off the end of my program without calling join on a running thread? Does Python wait for the thread to finish? What if you explicitly call sys.exit in the main thread?
• Write a program that lists the contents of a directory, spawns a thread for each file, and prints the size in bytes of each. Compare its running time to the equivalent synchronous program. (Try running it on /usr/bin, a directory with many files.)

Synchronization

Whenever it is possible for multiple actors to modify a shared resource, it is necessary to synchronize them so they don't step on each other's toes.

In multithreading, the shared resource is memory (and the data structures it contains) itself.

Suppose you had a subroutine that updates a pair of related maps:

class UserStore:
    def add_user(user_id, username):
        self.user_id_to_username[user_id] = username
        self.username_to_user_id[username] = user_id

What happens if the running thread gets preempted in between the two assignments? Another thread that accesses the UserStore may then see an inconsistent state of the world where a user exists in one map but not the other. Worse, suppose we have a delete_user method that gets called in the middle of add_user running. delete_user removes the user from the user_id_to_username map, then add_user resumes and adds the user to the username_to_user_id map – and now the inconsistency is permanent.

If we expect the UserStore to be used by multiple threads at once, we need a way to synchronize access to it – readers should not be able to read a data structure while a writer is writing to it, and two writers should not try to update the same data structure at once.

Synchronization brings back a little sequential execution into concurrency. You don't want too much synchronization or else you lose the benefits of concurrency. But you may need some to protect the integrity of your data structures.

Exercise: Locks

Copy the following code:

import json
import os

class JsonDb:
    def __init__(self):
        self.fd = os.open("db.json", os.O_RDWR | os.O_CREAT | os.O_TRUNC)

    def get(self, key):
        kv = self._read_all()
        return kv.get(key)

    def put(self, key, value):
        kv = self._read_all()
        kv[key] = value
        self._write_all(kv)

    def close(self):
        os.close(self.fd)

    def _write_all(self, kv):
        os.ftruncate(self.fd, 0)
        os.write(self.fd, json.dumps(kv).encode("ascii"))
        self._rewind()

    def _read_all(self):
        acc = bytearray()
        while True:
            buf = os.read(self.fd, 4096)
            if len(buf) == 0:
                break
            acc += buf

        self._rewind()
        s = acc.decode("ascii")
        return json.loads(s) if len(s) > 0 else {}  # file initially empty

    def _rewind(self):
        os.lseek(self.fd, 0, os.SEEK_SET)

The class JsonDb implements a simple key-value store on disk using the JSON data format. The two user-facing methods are get and put.

Exercise: Write some code that spawns many threads and demonstrates that JsonDb is not safe to use concurrently. Make sure to initialize JsonDb once, before spawning threads, since the __init__ method truncates the file.

Exercise: Make JsonDb thread-safe. (Hint: Try using locks.)

Locking caveats

Locking helps you protect the integrity of your data structures in the face of concurrent updates, but it comes with its own set of caveats.

Locks can result in deadlock, a situation where the system cannot make progress because two different actors are both waiting for each other.

The threading.Lock object in Python is not reentrant, meaning that if a thread call acquire when it already holds the lock, the thread will deadlock itself. This can be an easy mistake to make in a large program. Python has threading.RLock objects that are reentrant, at the cost of a small performance overhead.

If two threads acquire the same two locks in a different order, they could mutually deadlock each other. Suppose thread 1 is written to acquire lock A then lock B, and thread 2 is written to acquire lock B then lock A. This execution order results in a deadlock:

thread 1 acquires lock A: success
thread 2 acquires lock B: success
thread 1 acquires lock B: blocked on thread 2
thread 2 acquires lock A: blocked on thread 1

threading.Lock (and all the other synchronization primitives in the threading library) is only for threads within the same process. It does not help with multiple processes accessing the same resource (e.g., a file).

Locks can seriously hurt performance. In our toy JsonDb example, every operation is protected by a lock, which means multithreaded code that uses JsonDb runs no faster than single-threaded code (in fact, it likely runs significantly slower because of threading and locking overhead). In particular, readers needlessly block other readers. This problem at least can be solved with a reader–writer lock, which allows an unlimited number of readers as long as there is no writer (i.e., writers block writers and readers, readers block writers, but readers do not block other readers). Unfortunately, the Python standard library does not have a reader–writer lock implementation. And reader–writer locks can be susceptible to writer starvation, wherein a constant stream of incoming readers blocks a writer from ever acquiring the lock.

Safer concurrency

I hope that the preceding discussion has convinced you that writing correct multithreaded code, especially multithreaded code that shares mutable state, is not easy. Fortunately, shared-state multithreading is not your only option for software concurrency.

• Process-based parallelism: Processes have more overhead than threads, and you lose the ability to share memory, but you no longer need to worry about synchronizing access to memory (though you may need to worry about synchronizing access to other shared resources). It's also currently the only way to achieve computational parallelism in Python.
• Message-passing: Much of the trouble with multithreading comes from shared state and locking. An alternative to sharing mutable state between threads is to have them communicate via passing messages to each other. This largely removes the need for locking. Message-passing is the basis for the actor concurrency model, which you can use in Python via the Pykka framework, as well as the recommended approach in Go.
• Asynchronous programming: If your program is mainly I/O-bound (e.g., a web server), you may not need to use multiple threads at all. Linux has non-blocking interfaces for certain kinds of I/O, which allows you to use a cooperative rather than preemptive concurrency model and mitigate (though not necessarily entirely eliminate) the need for locks. We'll learn more about this later in the course.

Final project milestone

It's time to make the database multithreaded! Let's extend the network interface you added last week, to spawn a worker thread for each connection so that the server can handle multiple requests at once. Prove that it works by adding a long sleep to the request handler and show that new connections are still accepted.

Bonus material

• Deadlock Empire is an online game to "test yourself against the intricacies of multi-threaded programming" by completing programming challenges.
• The concurrent.futures module has a higher-level interface for writing concurrent programs, e.g., ThreadPoolExecutor.