Grokking Multithreading and Concurrency for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Problem 17: Traffic-Light-Controlled Intersection Synchronization
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Overview

The problem at hand is to ensure the smooth and safe movement of vehicles and pedestrians through a four-way intersection using traffic lights. Each direction of vehicle traffic and each direction of pedestrian traffic is represented as an individual thread, resulting in a total of eight threads. The challenge lies in synchronizing these threads such that there's no collision, and the flow is efficient.

Concurrency & Synchronization Insights

  1. Concurrency: With multiple vehicle and pedestrian threads running in parallel, there's a risk of a "collision" if two or more threads attempt to pass through the intersection at the same time.
  2. Synchronization Requirement: The traffic lights should ensure that only one direction of vehicle traffic (or possibly more, depending on the type of intersection) can proceed through the intersection at once. Similarly, pedestrian lights should ensure safe crossing, keeping in mind they may have separate signals. Pedestrians must wait if vehicles are moving, and vice versa.
initialize traffic lights for each direction as RED
initialize pedestrian lights for each direction as DON'T WALK

FUNCTION ControlTraffic():
    WHILE true:
        FOR each direction:
            Turn vehicle light to GREEN for that direction
            Allow vehicles to pass for a set duration
            Turn vehicle light to YELLOW, then RED for that direction
            Turn pedestrian light to WALK for that direction
            Allow pedestrians to cross for a set duration
            Turn pedestrian light to DON'T WALK for that direction

FUNCTION VehicleThread(direction):
    WHILE true:
        IF traffic light for that direction is GREEN:
            Let vehicle pass through the intersection
            Wait for a short duration before the next vehicle

FUNCTION PedestrianThread(direction):
    WHILE true:
        IF pedestrian light for that direction is WALK:
            Let pedestrian cross the road
            Wait for a short duration before the next pedestrian

START ControlTraffic() as a separate thread
FOR each direction:
    START VehicleThread(direction) as a separate thread
    START PedestrianThread(direction) as a separate thread

Algorithm Walkthrough

Let's walk through the traffic simulation code you provided, focusing on the synchronization aspects.

Initialization

  • trafficLights: An array representing the state of traffic lights in all directions. Initially set to RED.
  • pedestrianLights: An array representing the state of pedestrian lights in all directions. Initially set to RED.
  • trafficLocks: An array of mutexes for synchronizing access to each direction's traffic light.
  • pedestrianLocks: An array of mutexes for synchronizing access to each direction's pedestrian light.
  • controlThread: A thread to control the overall traffic light system.
  • vehicleThreads: Threads representing the vehicle flow in each direction.
  • pedestrianThreads: Threads representing the pedestrian flow in each direction.

Execution

The program runs an infinite loop with three main parts: traffic control, vehicle simulation, and pedestrian simulation.

1. Traffic Control (ControlTraffic thread)

  • Iterates through each direction.
  • Locks the traffic light mutex for the current direction.
  • Sets the traffic light to GREEN, waits for 5 seconds, then sets to YELLOW, waits for 2 seconds, and finally sets to RED.
  • Unlocks the traffic light mutex.
  • Does a similar process for the pedestrian light, but without the YELLOW state.

2. Vehicle Simulation (VehicleThread)

  • Runs in an infinite loop for each direction.
  • Checks if the traffic light for its direction is GREEN.
    • If GREEN, it prints a message indicating a vehicle is passing and waits for 1 second.
    • If not, it does nothing (busy waiting).

3. Pedestrian Simulation (PedestrianThread)

  • Runs in an infinite loop for each direction.
  • Checks if the pedestrian light for its direction is GREEN.
    • If GREEN, it prints a message indicating a pedestrian is crossing and waits for 1 second.
    • If not, it does nothing (busy waiting).

Synchronization Aspects

  • trafficLocks:

    • Ensures exclusive access to the traffic light state for each direction.
    • Prevents vehicles from checking/changing the state of the light while it's being controlled.

  • pedestrianLocks:

    • Ensures exclusive access to the pedestrian light state for each direction.
    • Prevents pedestrians from checking/changing the state of the light while it's being controlled.

Final Result

The program simulates a traffic light system, managing traffic and pedestrian lights for multiple directions. It uses mutex locks to synchronize access to shared resources (the state of the lights), ensuring that the state is changed in a controlled and thread-safe manner. Vehicle and pedestrian threads check the state of the lights in a loop, and react accordingly when the lights are GREEN. However, it's worth noting that the program currently uses busy waiting for the vehicle and pedestrian threads, which could be improved with condition variables or other synchronization mechanisms to reduce CPU usage.

Flow Chart
Flow Chart
Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible