Traffic Intersection Simulation using Multi Threading Algorithm

Question

This is a interview Question which was asked and wanted to find an efficient solution.

Problem

Consider a intersection of four roads as shown in the diagram. Each road is defined to have a direction. How would you solve the problem so as to improve the traffic condition and avoid deadlocks.

1. the intersection is divided into four quadrants [shown in yellow].
2. Cars enter the intersection at random from the four direction [0,1,2,3]
3. At the intersection each car can make a single move. the three possible moves are
   1. Go left
   2. Go straight
   3. Go right

e.g :

if a car enters from direction 2 and wants to take a left turn. it should pass through quandrant 2 , quandrant 1 and finally quandrant 0

Semi complete solution

Each quadrant marked in yellow has a semaphore associated with it. What I imagined was a 2 phase protocol wherein each car would

1. get list of quadrants it will pass through
2. lock each of the quadrants starting from the last quadrant
   3. In the above example the car from direction 2 would lock quadrant 0, quadrant 1 and then quadrant 2.
3. Move through the intersection
4. Release the locks acquired.
   3. The locks are released in the same order. quadrant 0, quandrant 1 and the quandrant 2

However the above solution is less than optimal as it results in a deadlock.

My Question is

1. What other /better way can this be achieved?
2. Can I implement this using a semaphore in C?
   2. If not what synchronization method should I be looking at?

Updates

1. I want a solution which allows multiple cars can enter the intersection and still avoid deadlock as well as collision.Having a single lock on the entire intersection would be less than optimized.

Answer 1

Your solution (as suggested in step 2) does not avoid deadlock.

Consider the case when from the four streets there are cars wanting to turn to their left. Then all the cars start locking different cuadrants:

from direction 0, it locks cuadrant 2. from direction 1, it locks cuadrant 3. from direction 2, it locks cuadrant 0. from direction 3, it locks cuadrant 1. -- deadlock --

You could avoid the deadlock by having a mutex shared by the four directions.