Solution Explanation

This problem focuses on designing a deadlock-free traffic light system at an intersection using concurrent programming techniques. The core challenge is to prevent cars from different roads from colliding at the intersection.

Approach

The solution uses a mutex lock (Lock in Python, synchronized in Java) to ensure that only one road's traffic light is green at any given time. The road variable keeps track of which road currently has a green light.

When a car arrives, it acquires the lock. If the car's roadId differs from the current road, it means the light needs to be switched. The turnGreen function is called to change the traffic light to green on the car's road, and the road variable is updated. Finally, the crossCar function allows the car to cross the intersection. After the car crosses, the lock is released, allowing other cars to proceed.

Code Explanation (Python)

The Python code uses the threading module's Lock class to implement a mutex. The carArrived method is synchronized with the lock:

from threading import Lock
 
class TrafficLight:
    def __init__(self):
        self.lock = Lock() # Initialize a lock
        self.road = 1 # Road A is initially green
 
    def carArrived(
        self,
        carId: int,
        roadId: int,
        direction: int,
        turnGreen: 'Callable[[], None]',
        crossCar: 'Callable[[], None]',
    ) -> None:
        self.lock.acquire() # Acquire the lock before entering the critical section
        if self.road != roadId:
            self.road = roadId
            turnGreen() # Change the light to green if needed
        crossCar() # Let the car cross
        self.lock.release() # Release the lock after finishing

Code Explanation (Java)

The Java code uses the synchronized keyword to achieve the same effect as Python's lock. The carArrived method is declared as synchronized, making it a critical section:

class TrafficLight {
    private int road = 1; // Road A is initially green
 
    public synchronized void carArrived(int carId, 
                                       int roadId, 
                                       int direction, 
                                       Runnable turnGreen, 
                                       Runnable crossCar) {
        if (roadId != road) {
            turnGreen.run(); // Change the light to green if needed
            road = roadId;
        }
        crossCar.run(); // Let the car cross
    }
}

Time and Space Complexity

• Time Complexity: The time complexity of the carArrived method is O(1) in both Python and Java because it performs a constant number of operations regardless of the input size. The lock acquisition and release operations are also constant time operations.

• Space Complexity: The space complexity is O(1) for both implementations. The TrafficLight class uses a constant amount of extra space to store the road variable and the lock.

Deadlock Prevention

The solution prevents deadlocks by using a single mutex lock. Only one car (from one road) can access the critical section (the intersection) at a time. This ensures that cars from different roads can't simultaneously try to cross, eliminating the possibility of deadlock. The order of acquiring and releasing the lock is consistent, further mitigating deadlock risks.