Races, deadlock, starvation, livelock

The GIL means only one thread runs at a time. Why can two threads still race?

Because one Python statement is several bytecode instructions, and the interpreter is free to switch threads between any two of them. The Python FAQ says as much: it offers to switch among threads only between bytecode instructions, and it lists i = i + 1 as not thread-safe. A counter update is a read, an add and a write, and a switch between the read and the write loses one of two additions. Check-then-act has the same shape: the check and the act are separate steps, so what the check learned can be out of date by the time the act runs. The GIL protects the interpreter’s own data structures. It does not make your two-step operation one step.

Is list.append thread-safe? Can I skip the lock?

In CPython today, a single append will not corrupt the list, and the Python FAQ lists it among the operations that are atomic. Two things go with that. It is a description of the current implementation rather than a language guarantee, and the free-threading HOWTO says so in as many words and recommends threading.Lock instead of relying on the internal locks of built-in types. And it only covers the one call: append is atomic, while “read the length, then append if there is room” is not. In a round, say both halves: yes in CPython today, and I would still take the lock, because the next reader of this code cannot tell which appends were safe by accident.

What is the difference between deadlock and livelock?

In a deadlock every thread is blocked and nothing is running: each holds something, each wants something another holds, nobody lets go, and the waiting forms a cycle. In a livelock every thread is running and nothing progresses: each one takes a lock, finds the other lock busy, lets go politely, and tries again in step with the other. A deadlock shows up in a thread dump as threads parked for ever. A livelock shows up as a busy process doing no work, which is harder to spot. The fix for the first is structural, usually a lock order. The fix for the second is to break the symmetry, usually a random backoff between retries.

When is message passing better than a lock?

When the state has one natural owner and the work is coarse enough to be worth a queue hop. Give the state to a single thread, let everybody else send it messages on a queue.Queue, and there is no shared mutable state left to race on: the reads and the writes all happen in one thread, in the order the messages arrived. What you pay is latency, a queue that has to be bounded and drained, and a shutdown path. A lock is better when the critical section is tiny and the callers need an answer immediately. The honest sentence for the room is that message passing trades shared-state bugs for queueing and latency.

Does Python’s Lock hand out fairness, like first come first served?

No. The threading documentation makes no ordering promise about which waiter gets a lock next, so a thread can be passed over repeatedly while others keep taking it. That is starvation, and it is a property of the scheduling rather than of your code. If you need an order, build one: a queue of requests served in arrival order, or a ticket scheme where each waiter takes a number and waits for it. The cheaper repair, and the one to reach for first, is to hold the lock for less time, so the question of who waits longest stops mattering.