Mini roundabouts and deadlock

This is the first in a small series of articles using roundabouts to explore some ideas in computer science:

• Mini roundabouts and deadlock
• Magic roundabouts and starvation

In this article I’ll go into dependency, which can lead to deadlock.  For this I’ll be using the mini roundabout as an illustration.  In the next article I’ll use the magic roundabout or ring junction to illustrate starvation.  If you prefer your everyday illustrations of computer science to be in the kitchen rather than on the roads, I’ve used washing dishes to explain the stack and the queue.

Mini roundabout

I’m aware that roundabouts are more common in the UK than they are in other parts of the world.  So you might not immediately understand what a mini roundabout is, and why it might be useful for this article.

A mini roundabout is one of the smallest versions of a roundabout.  If you look at the roads that join at the roundabout (the feeder roads), often the edge of one road touches the edge of the next road rather than being spread apart around the circumference of a circle as in bigger roundabouts.  This closeness usually means that the drivers of the vehicles at the head of each road can see each other across the mini roundabout.

The rule for roundabouts in the UK is that you give way to traffic to your right.  If there’s no one to your right (or straight ahead, i.e. in your way), you can start moving.  You then travel around the roundabout in a clockwise direction until you leave it.

The problem I want to focus on is when vehicles travel along all the roads and arrive at the mini roundabout at the same time.  Imagine this has happened in the diagram below:

Technically, each vehicle could go, as the roundabout to their right is clear.  However, if all the drivers did this, it’s likely there would be a crash as the roundabout is too small to fit a vehicle from each road.  So, what often happens is the drivers are a little unsure of things and wait.  Vehicle A is waiting for vehicle C, vehicle B is waiting for vehicle A and vehicle C is waiting for vehicle B.  If you drew this as a diagram, where the arrow indicates ‘is waiting for’, it would look like this:

Five dining philosophers

There’s a classic thought experiment in computer science related to this, called the five dining philosophers.  Five philosophers are sat at the same round table.  In front of each philosopher is a bowl, and between one bowl and the next is a single fork.  The philosophers randomly split their time between thinking and eating.  When a philosopher wants to eat, they have to pick up the two forks next to their bowl (one to their left and one to their right).  The problem is that there are only five forks for the five philosophers – each fork is both the left fork for one philosopher and the right fork for another.

To make it simpler to talk about things later, here’s a diagram with philosophers and forks labelled. I’m not showing the bowls as they’re not important for this problem:

Can you come up with a choreography or protocol that will mean that hungry philosophers are as likely as possible to be able to eat?  The key thing here is, like the mini roundabout, there’s no police officer or waiter co-ordinating who does what when.  We need to come up with a set of rules that each participant can follow on their own, such that the overall activity that arises from this is as good as possible (for however we choose to define good).

A simple but poor example protocol is:

1. Wait till the fork on your left is free and then pick it up.
2. Once you have the left fork, wait till the fork on your right is free and then pick it up.
3. Eat
4. Put down both forks

If only one philosopher at a time wants to eat, things work quite simply.  If two to four philosophers want to eat at the same time, things will eventually work OK.  A philosopher whose neighbour on the right isn’t eating or trying to eat will immediately be able to get the left and right forks and so eat.  All other philosophers will get the fork to their left and then have to wait until the philosopher to their right has finished, puts down the fork that the first philosopher’s waiting for, and then they can eat.

So, in the case of four philosophers A-D trying to eat at the same time it starts like this:

The blue arrows show which fork or forks each philosopher has, and red arrows show which fork each philosopher is waiting for.  Eventually A finishes eating and so puts down both forks.  This frees up fork 1, so philosopher B can eat:

This process repeats such that when B’s finished C will eat, and when C’s finished D will eat.

However, if all five philosophers choose to eat at the same time, things break and stay broken forever.  This is like the mini roundabout case where all roads have a vehicle arrive at the mini roundabout at the same time. Each philosopher will pick up the fork to their left.  They will then start waiting for the fork to their right to become free.  However, nothing will trigger this to become true.  The philosophers are all stuck on line 2 of the protocol:

To put it in more computer science-y terms:

• Each philosopher depends on / has a dependency on the fork to their left and on the fork to their right;
• The forks are shared resources, i.e. there’s contention for them among more than one philosopher (if each philosopher had their own pair of forks there would be no problem);
• Across the set of philosophers, the dependencies on shared resources form a loop, i.e. there’s a circular dependency
• The circular dependency can result in deadlock – two or more actors (philosophers) are blocked by each other’s activity in such a way as they will stay blocked forever.

More than one actor being dependent on shared resources isn’t enough for deadlock.  There has to be a circular dependency for deadlock to happen.  Later on we’ll see how changing the pattern of dependencies away from circular is a cure for deadlock.

Other examples of deadlock

Imagine you are trying to learn a new subject.  Often the concepts in a subject relate to each other – which do you learn first?  You can’t learn concept A until you know concept B, but you can’t learn concept B until you know concept A.  The two learning activities depend on each other, and this circular dependency brings things to a halt.

I was once on a project management training course with a pair of unschedulable tasks – task A depended on the output of task B, but task B depended on the output of task A.

The classic example in computing is databases.  Imagine there’s a database table that holds people’s bank accounts.  Each row in the table holds the current balance for one account.  Two transfers need to happen: account A needs to transfer £20 to account B, and account B needs to transfer £50 to account A.

One way to implement a transfer between accounts source and destination of amount X is:

1. Lock source to prevent it from being updated by anyone else until we’re finished
2. Lock destination to prevent it from being updated by anyone else until we’re finished
3. Decrease source’s balance by X
4. Increase destination’s balance by X
5. Unlock destination
6. Unlock source

The problem happens when the two transfers I mentioned about (A to B and B to A) happen at the same time.  The process transferring to B will lock A and try to lock B.  The process transferring to A will lock B and try to lock A.  Both will succeed in locking their respective source account (step 1) but wait forever to lock their destination account (step 2).

Solutions

At a previous company, we had the risk of a database deadlock as I described above.  The solution we came up with was that accounts were locked in account number order, rather than source then destination.  This breaks the circular dependency, and turns it into a simple competition over account A.

The database will ensure that exactly one process will win, and all other processes will be put in a queue to wait for A to become free.  The winning process might have to wait for B to become free (for instance, if there’s another transfer happening from B to C), but eventually it will get the resources it needs, complete its operations and then release the locks that other processes are waiting on.

The only solution I can think of for the unlearnable concepts and unschedulable tasks is to break each into bits. The aim is for there to be at least a bit of task or concept A that doesn’t depend on task or concept B or vice versa.  You can do this introductory bit first.  With any luck, this will then allow a bit of the other task or concept to be tackled, and you can move back and forth between the two.

One solution to the five dining philosophers is similar to the database deadlock problem.  You number the forks (as I have in the diagram).  You then change the protocol from:

1. Pick up the fork on your left
2. Pick up the fork on your right

To:

1. Pick up the fork next to you with the bigger number
2. Pick up the fork next to you with the smaller number

For four of the five philosophers (B to E), these two protocols will mean the same thing in practice as the fork on their left has a bigger number than the fork on their right.  However, for philosopher A, the fork on their left has a smaller number than the fork on their right.  It’s this philosopher that breaks the circular dependency, and so deadlock is impossible.

As in the database modelling transfers between bank accounts, this arrangement has turned a circular dependency into a set of dependencies that includes a straightforward competition for fork 5.  Assuming that philosophers A and E can handle this competition amicably, things should work out OK.  The diagram below shows the case where E wins and A loses.  B is currently able to eat – compare this to the previous example where no-one was able to eat.  After B has finished, the order will be C, D, E, A.

Solutions involving random waits

Sometimes, waiting for a random amount of time and then trying again is a good enough solution.  As part of this, you have to give up any shared resources that might be blocking other actors, so that they have a chance to finish their activity and get out of your way.

There’s an interesting use of random waits in a case where there’s contention for a shared resource.  In a network like Ethernet, there’s a problem when two computers try to transmit at the same time – they talk over each over each other, which is known as collision.  Like with the vehicles at the roundabout and the dining philosophers, there’s no central co-ordinator.  Instead, each computer follows rules on its own, which we hope will produce a system whose behaviour is what we want.

Each computer starts transmitting, but also listens out to see if there was collision.  If there was collision, it stops, waits for a random amount of time, then tries again.  The interesting thing is what happens if the second and later attempts are also unsuccessful due to collisions.  The protocol (exponential backoff) says that the maximum value that the random number can have must double for each failed attempt.  I.e. the first wait is in the range 0 to 1, then 0 to 2, then 0 to 4 etc.

The chances are that a run of many failed attempts in a row is caused by lots of different computers trying to use the network at once (rather than just one other computer than you, that happens to be exactly matching each of your random waits).  In this case, each computer will independently throttle back, i.e. it will wait for roughly double as long before trying again.  If all computers on the network use this protocol, then they will independently judge the global busy-ness of the network and adapt their behaviour accordingly, without the need of a central co-ordinator.

Summary

There are situations in computing and life in general where things can be blocked based on competition for shared resources.  If the pattern of dependencies is circular, this blockage can become effectively permanent – a state known as deadlock.  If the dependencies can be reordered to avoid a cycle, it’s possible for the actors to share resources without blocking each other permanently and without needing a central co-ordinator to keep things moving.