Magic roundabouts and starvation

This is the second 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 starvation, using the wonder / horror that is the Magic Roundabout (like Duff’s device for road junctions). Unfortunately, this won’t involve anything from the excellent TV series called The Magic Roundabout. It will feature some diagrams of rather dubious quality, which are almost as poor as those in my article on statistics.

Unfair access to roundabouts

As well as deadlock, as described in the previous article, roundabouts can suffer from unfair access.  Unlike in deadlock there are vehicles using the roundabout, but the problem is that some of the roads that meet at the roundabout dominate the other roads.

Imagine there are two roads that meet at a roundabout.  There’s a major road (A-C) running north / south and a minor road (B-D) running east / west.  This is a normal-sized roundabout, rather than a mini roundabout as I used in the previous article.

Vehicles coming south on road A will see there is no traffic trying to continue around the top part of the roundabout, so they can enter – this is the blue line below.  They will carry on around the roundabout and exit onto road C going south.  Similarly, vehicles coming north on road C will see there is no traffic trying to continue around the bottom part of the roundabout, so they can enter – the orange line below.  They will carry on around the roundabout and exit onto road A going north.

Compare this to vehicles going east on road D (the red line).  The roundabout is full of vehicles trying to go C -> A, which means the roundabout by the end of D is already full.  The vehicles trying to enter at D will have to wait until a break in the C -> A traffic.  If there’s enough of this traffic, the wait could be very long.  The same thing can occur with vehicles going west on road B (the green line) – they are blocked by A -> C traffic.

The problem here is a lack of fairness.  To put it in more computer science-y terms:

• East / west traffic and north / south traffic are competing for a shared resource (the roundabout);
• East / west traffic is suffering from starvation (much lower than expected / no access to the shared resource).

The magic roundabout

One solution to this problem would be to use traffic lights.  Either the roundabout could be replaced with e.g. a crossroads controlled by traffic lights, or traffic lights could be added to the junctions that make up the roundabout.

Another solution is the magic roundabout, also known as the ring junction.  One way to think of a normal roundabout is:

1. There is a one-way road bent around into a circle;
2. Feeder roads meet this circle at give-way T junctions (on the way onto the roundabout) and a simple side-road junction (on the way off the roundabout).

In these terms, a magic roundabout could be described as:

1. There is a two-way road bent around into a circle;
2. Feeder roads meet this circle at mini roundabouts.

As a diagram, it looks like this:

As well as being a large sea of tarmac stretching out in many directions with confusing jumbles of painted lines and street furniture, there is an important practical difference from a normal roundabout.  It’s possible to travel anti-clockwise around the roundabout (on the inner lane) as well as the more normal clockwise (on the outer lane).

If vehicles travel on only the outer lane, then there’s no real difference from a normal roundabout.  However, if vehicles go around the roundabout in both directions using both lanes, interesting things start to happen.  If we go back to the previous pair of roads, now meeting at a magic roundabout, and show just the north / south traffic but with traffic split 50 / 50 over the lanes of the roundabout, it looks like this:

If you look at the mini roundabout at the end of D, there’s half of the south to north traffic going around the ‘outside’ of the mini roundabout, and half of the north to south traffic going around the ‘inside’ of the mini roundabout.  Due to the way the feeder roads to this mini roundabout are arranged, the traffic on D trying to come east can effectively ignore the traffic on the inside of the mini roundabout.  It’s only the south to north traffic that gets in its way, and now this is half of what it was before (the other half of the south to north traffic has gone around the other side of the magic roundabout).

This reduction of traffic in the way of traffic trying to enter from D means it’s more likely to be able to get onto the mini roundabout.  Once it’s on the mini roundabout it has the choice to go clockwise or anti-clockwise around the magic roundabout.

The same thing happens at the other side of the magic roundabout – traffic trying to go west from B now has only half of the north to south traffic in its way.  (Any south to north traffic on the mini roundabout isn’t in its way, and the other half of the north to south traffic is on the other side of the magic roundabout.)  It’s also more likely to be able to get onto the mini roundabout and then around the magic roundabout as a whole.

If you want to read more about magic roundabouts, there’s a 99% Invisible article about them.

Lifts

There’s an interesting example of starvation that’s possible in lifts (elevators).  Imagine you’ve designed the lift so that it always processes the request that will send it the shortest distance.  (The idea is that this will mean it completes requests quickly, and becomes available for fresh requests quickly as a result.)  This might seem like a good idea, but there’s the possibility of starvation.

In a building with 10 floors, the lift is on floor 6.  Someone gets in and presses the button for floor 7.  While the lift’s moving, 2 things happen:

1. Someone on floor 1 asks to go up;
2. Someone on floor 7 asks to go down.

When the lift gets to floor 7, the person in the lift gets out and the person waiting there gets in and presses the button for floor 6.  The lift sets off, and while it’s moving someone on floor 6 asks to go up.  When the lift arrives on floor 6 the person in the lift gets off and the person waiting gets in and presses the button for floor 7.

Floor 7 is only 1 floor away, whereas floor 1 is 5 floors away, so the lift goes up to floor 7.  If there were a stream of people on floors 6 and 7 repeating requests like this, the lift will never go to floor 1 as it will always be further away than another request.  Floor 1 will suffer from starvation.

High / low priority queues

In systems that process queues there’s a potential problem if there’s more than one queue and the queues have different priority.

One way to implement high vs. low priority is to say that if there’s a request on the high priority queue it must be processed, and the low priority queue is only looked at when the high priority queue is empty.  However, if requests to the high priority queue arrive at least as quickly as the previous request is processed (such that the high priority queue is never empty), the low priority queue will never be looked at.  I.e. the low priority queue suffers from starvation.

There are at least two solutions to this.  One is to add a request’s age to the decision making.  This could be either by changing the rules (e.g. if there’s a low priority request older than X, it beats high priority requests) or by having something shunt low priority requests to the high priority queue if they’re older than X.

The other solution is possible if there are many workers that process the queues.  If there are e.g. 3 workers, you could say that:

1. Workers A and B process high priority requests first, and will process low priority request only if there are no high priority requests
2. Worker C is the other way around – low priority requests first, then high priority requests.

This means that high priority requests will on average be processed twice as quickly as low priority requests, i.e. there’s still a benefit to priority, but it’s not as binary as in the previous approach.

Summary

Starvation is a problem to do with shared resources, where some parts of the system get less access than desired or even none at all.  It’s unlike deadlock, where the system has stopped – in starvation there is still activity but it’s not being shared in the desired way.