CSC369 Synchronization Tutorial: Traffic Intersection Monitor with POSIX Threads

Introduction: Synchronization Meets Autonomous Driving

In the world of self-driving cars, coordination is everything. Just as Tesla's Full Self-Driving (FSD) system must navigate intersections without human input, your CSC369 assignment asks you to build a traffic intersection monitor that coordinates cars using POSIX threads. This tutorial will guide you through the core synchronization concepts—monitors, condition variables, and deadlock avoidance—using the intersection problem as a hands-on example. By the end, you'll understand how to implement car_arrive and car_cross without race conditions or memory leaks.

Understanding the Intersection Model

The intersection has four cardinal directions (N, S, E, W), each with a lane buffer (fixed-size queue) for incoming cars. Cars are represented by a tuple (id, in_dir, out_dir). The intersection is divided into four quadrants, each protected by a lock. A car's path through the intersection occupies one or two quadrants: for example, a car going straight occupies one quadrant, while a car turning left occupies two. Your monitor must ensure that no two cars occupy overlapping quadrants simultaneously.

Key Data Structures

Lane buffers: One per direction, implemented as a fixed-size array with head/tail indices.
Quadrant locks: Four pthread_mutex_t variables, one for each quadrant.
Condition variables: Used to signal cars when they can enter or cross.
Exit lists: Linked lists per exit direction (provided in starter code).

Policy 1: Lane Ordering

Once a car arrives, it is placed in its lane. It can only cross after all earlier cars in the same lane have crossed. This is enforced using a condition variable per lane: each car waits until it becomes the head of the lane.

void *car_arrive(void *arg) {
    Car *car = (Car *)arg;
    pthread_mutex_lock(&monitor.mutex);
    // Add car to lane buffer
    enqueue_lane(car->in_dir, car);
    // Wait until this car is at the head of the lane
    while (lane_head(car->in_dir) != car) {
        pthread_cond_wait(&monitor.lane_cond[car->in_dir], &monitor.mutex);
    }
    pthread_mutex_unlock(&monitor.mutex);
    return NULL;
}

Policy 2: Clear Path Before Crossing

Before entering the intersection, a car must ensure that all quadrants it will occupy are free. The compute_path function returns an array of quadrants (0-3) that the car will traverse. The car then attempts to lock those quadrants in a fixed order to avoid deadlock.

Deadlock Avoidance via Lock Ordering

To prevent deadlocks, always acquire quadrant locks in increasing order (e.g., quadrant 0 first, then 1, etc.). This is a classic technique used in database systems and operating systems. For example, a car going from North to South (occupying quadrant 0) would lock quadrant 0 first. A car turning left from North to East (occupying quadrants 0 and 1) would lock 0 then 1.

void *car_cross(void *arg) {
    Car *car = (Car *)arg;
    int *path = compute_path(car->in_dir, car->out_dir);
    int num_quads = path[0]; // first element is count
    // Lock quadrants in order
    for (int i = 1; i <= num_quads; i++) {
        pthread_mutex_lock(&monitor.quad_mutex[path[i]]);
    }
    // Cross (simulate with sleep)
    usleep(100);
    // Unlock quadrants
    for (int i = num_quads; i >= 1; i--) {
        pthread_mutex_unlock(&monitor.quad_mutex[path[i]]);
    }
    // Signal next car in lane
    pthread_mutex_lock(&monitor.mutex);
    dequeue_lane(car->in_dir);
    pthread_cond_signal(&monitor.lane_cond[car->in_dir]);
    pthread_mutex_unlock(&monitor.mutex);
    free(path);
    return NULL;
}

Implementing `compute_path`

This helper function determines which quadrants a car occupies based on its entry and exit directions. For simplicity, assume the intersection quadrants are numbered:

0: NW (cars from N to W or W to N)
1: NE (cars from N to E or E to N)
2: SW (cars from S to W or W to S)
3: SE (cars from S to E or E to S)

A car going straight (N to S) uses quadrants 0 and 2? Actually, careful: The quadrant assignment depends on the figure. In the typical model, a car going straight occupies the two quadrants that form its path. For example, N to S might use quadrants 0 and 2. A left turn (N to E) uses 0 and 1. A right turn (N to W) uses only 0. Implement based on the figure provided in your assignment.

int *compute_path(enum direction in_dir, enum direction out_dir) {
    int *path = malloc(3 * sizeof(int)); // max 2 quadrants + count
    // Example for N to S:
    if (in_dir == N && out_dir == S) {
        path[0] = 2; // two quadrants
        path[1] = 0;
        path[2] = 2;
    } else if (in_dir == N && out_dir == E) {
        path[0] = 2;
        path[1] = 0;
        path[2] = 1;
    } // ... other cases
    return path;
}

Testing with Helgrind

Valgrind's Helgrind tool is your best friend for detecting synchronization bugs. Run your program with valgrind --tool=helgrind ./traffic. It will report data races, lock ordering violations, and improper condition variable usage. For example, if you forget to acquire a mutex before signaling, Helgrind will flag it. Use it iteratively to refine your implementation.

Common Helgrind Errors

Data race: Two threads access shared data without synchronization.
Lock order violation: Threads acquire locks in different orders, leading to potential deadlock.
Mutex not locked on condition wait: Calling pthread_cond_wait without holding the associated mutex.

Avoiding Memory Leaks

The starter code explicitly says not to free the out_cars array. However, you must free any dynamically allocated memory for cars (after they cross) and the path array inside car_cross. Use free(car) after the car has been removed from the lane and its crossing is complete. Run valgrind --leak-check=full to verify.

Trend Connection: AI Traffic Management

Just as Waymo and Cruise use AI to coordinate autonomous fleets, your monitor enforces a policy that prevents deadlocks and ensures fairness. The quadrant locks mimic how real-world intersections use traffic lights to allocate right-of-way. By mastering POSIX synchronization, you're building skills that apply to high-frequency trading systems, multiplayer game servers, and even smart city infrastructure.

Conclusion

Implementing a traffic intersection monitor teaches you the fundamentals of concurrent programming: mutexes, condition variables, and deadlock avoidance. Use the lane buffers to enforce order, lock quadrants in a fixed sequence, and always signal the next waiting car. Test with Helgrind and valgrind to ensure correctness and no memory leaks. This assignment is your stepping stone to building robust multi-threaded systems.