Locks are a good way to serialize parts of the program. Sections outside of locks can still run in parallel, increasing utility. Locks make threads wait until the lock is available. But what if the lock is never freed? This state is called a deadlock.

Here is an simple example:

lock()
while True:
    a = a + 1
unlock()

There is an infinite loop inside the critical section. Thus, once a thread enters here, other threads that want to run this code will wait forver.

Hopefully, no one would actually do something so silly. Let's observe a more likely scenario.

Suppose that thread A wants to append some text to 2 files: "names.txt" and "addresses.txt." We only want one thread writing to a file at a time, so that the data does not get mixed up. Thus, threads will acquire locks before changing files. So the thread can do:

lock('names')
append_to_file('names.txt', 'Taylor Smith')
unlock('names')
lock('addresses')
append_to_file('address.txt', '1 Main Street')
unlock('addresses')

But in this example, we have an additional condition: only one thread may write to two files, names.txt and addresses.txt, at a time. This is to ensure that the data in both files stays consistent. For example, if we want to add a new person, we add the person's name to names.txt and address to addresses.txt. We don't want anyone to see the intermediate state where the new name has been added to names.txt but the address has not yet been added to addresses.txt.

So how do we do this? We can do:

lock('names')
lock('addresses')
append_to_file('names.txt', 'Taylor Smith')
append_to_file('address.txt', '1 Main Street')
unlock('addresses')
unlock('names')

So far so good. Now suppose that around the same time, thread B also wants to append some text to "addresses.txt" and "names.txt." Thread B runs the following program:

lock('addresses')
lock('names')
append_to_file('names.txt', 'Victoria West')
append_to_file('address.txt', '77 Last Street')
unlock('names')
unlock('addresses')

Suppose the threads run around the same time, and the sequence of events happens to be as follows:

1. thread A acquires the 'names' lock.
2. thread B acquires the 'addresses' lock.
3. thread A tries to acquire the 'addresses' lock.
4. thread B tries to acquire the 'names' lock.

Thread A cannot acquire 'addresses' because B is holding the lock. And B tries to acquire 'names' but fails because thread A is holding it. Neither thread can proceed. We have a deadlock.

There are several ways to resolve this, but one way is to make sure that that the thread try to acquire locks in the same order. For example, if we change thread B's program to:

lock('names')
lock('addresses')
append_to_file('names.txt', 'Victoria West')
append_to_file('address.txt', '77 Last Street')
unlock('names')
unlock('addresses')

Now both threads will try to acquire the "names" lock first. One will acquire the lock and the other will wait until it is released. The thread that acquired "names" first will also acquire "addresses" first, since the other thread is still waiting on the "names" lock to be released. Thus, only one of the threads is waiting, and the deadlock is avoided.

lock('names')
append_to_file('names.txt', 'Adrian Day')
unlock('names')
lock('addresses')
append_to_file('address.txt', 'Adelaide')
unlock('addresses')

lock('names')
append_to_file('names.txt', 'Brian Summer')
unlock('names')
lock('addresses')
append_to_file('address.txt', 'Bristol')
unlock('addresses')

lock('names')
lock('addresses')
append_to_file('names.txt', 'Adrian Day')
append_to_file('address.txt', 'Adelaide')
unlock('addresses')
unlock('names')

lock('addresses')
lock('names')
append_to_file('names.txt', 'Brian Summer')
append_to_file('address.txt', 'Bristol')
unlock('names')
unlock('addresses')