Sync (MetroREC)

I implemented the passenger boarding synchronization mechanism for the METROREC subway station, a Systems Programming assignment. Each passenger is a thread, each car is another thread, and the problem is to guarantee two things at once: nobody boards without a seat, and the car does not leave with a passenger it released still standing.

The assignment restricted the tools: only pthread_mutex_* and pthread_cond_*, a single lock per station, no semaphores and no busy waiting. The premise is one car at a time, with at most one car at the station.

The contract of the four functions

The runner (the test provided with the assignment) calls the station at four points. station_init prepares the structure. station_load_car(station, count) is called by the car thread with the number of seats and only returns when every passenger it released has confirmed boarding or when the seats run out. station_wait_for_car blocks the passenger until there is a car with a free seat. station_on_board is the confirmation that the passenger sat down.

A reservation is not a confirmation

This is the part that required thinking before writing code. Between reserving a seat and reporting that the passenger sat down, the passenger still has to move; several passengers can reserve before any of them calls station_on_board. If the car counted reservations, it would leave with people still standing in the aisle.

I solved it by treating boarding as a counter of pending confirmations: it goes up when a passenger reserves a seat and down when that passenger confirms. The car waits while the counter is above zero, that is, while there is someone it released who has not yet reported sitting down.

The station state

struct station holds everything the two sides need to know about each other:

• mutex — the single station lock, protects every field below;
• car_arrived — condition variable where passengers sleep waiting for a seat;
• passenger_boarded — condition variable where the car sleeps waiting for confirmations;
• car_present — 1 while a car is at the station;
• free_seats — seats this car can still reserve;
• waiting — passengers that entered station_wait_for_car and have not reserved yet;
• boarding — pending confirmations for this car.

The struct is fully defined in the header, not opaque, because the runner allocates the station on the main stack and needs the complete type for that.

The reservation

The passenger registers in waiting before sleeping, because the car needs to know how many people are already waiting at the moment it arrives. Then it stays in the loop until there is a car and a free seat.

void station_wait_for_car(struct station *station) {
    pthread_mutex_lock(&station->mutex);

    station->waiting++;

    while (!station->car_present || station->free_seats == 0) {
        pthread_cond_wait(&station->car_arrived, &station->mutex);
    }

    station->waiting--;
    station->free_seats--;
    station->boarding++;

    pthread_mutex_unlock(&station->mutex);
}

Leaving the loop is the reservation, and it happens inside the lock: decrementing waiting, decrementing free_seats and incrementing boarding are a single operation from the point of view of the other passengers. Without that, two passengers could see the same last free seat and reserve it twice.

Two condition variables

There are two different predicates: a passenger waits for “car present and free seat”, the car waits for “no pending confirmation”. With a single condition variable, a signal could wake the thread that was not waiting on that condition and the notification would be lost.

With two, each group is woken through its own channel. The car uses broadcast on car_arrived, because several passengers can board the same car; and it uses signal on passenger_boarded, because it is the only thread sleeping on that condition.

Closing the car

while (station->boarding > 0 || (station->free_seats > 0 && station->waiting > 0)) {
    pthread_cond_wait(&station->passenger_boarded, &station->mutex);
}

station->car_present = 0;
station->free_seats = 0;

pthread_mutex_unlock(&station->mutex);

The wait condition has two terms. The first is the contract obligation: do not leave with a pending confirmation. The second absorbs passengers who arrived right after the doors opened, instead of the car leaving with an empty seat and someone waiting.

Clearing car_present and free_seats before the unlock is what stops a late passenger from reserving a seat in a car that has already left. The shutdown happens while holding the lock, so nobody observes the state halfway through; the next car starts with a clean station.

A non-positive capacity is treated as zero. The contract does not define that case, and the choice was to offer no seats at all, so the car leaves empty.

Validation

The build uses -std=gnu11 -Wall -Wextra -Werror -pthread, so the implementation compiles with no warning at all. The provided runner creates 100 passenger threads, runs several cars with a seat count drawn between 0 and 49 and checks three situations: an empty car with nobody waiting, a car without seats while many people wait, and a car with more seats than passengers. The output ends with Looks good! when there is no divergence.

To look for intermittent failures I ran the test 60 times in a row, then 30 more pinned to a single core (taskset -c 0) and once under helgrind. Helgrind reported four race contexts, all in load_car_returned, a control flag of the runner itself: it is volatile, but its reads and writes are not atomic. No context was reported in sync_car.c.

Locally I also added an invalid case to the runner: station_load_car with a negative capacity must return immediately without letting anyone board. It passes, and the rest of the runner is unchanged.

Limitations

• One car at a time is a premise of the assignment. car_present and free_seats describe the current car; two simultaneous cars would require per-car state and a different shutdown rule.
• The runner is not part of the deliverable. It is the provided test, it holds the main used by the Makefile, and it only exists for the local build.
• The helgrind warnings belong to the runner, not to the station. That has to be said every time the result is quoted, otherwise it looks like the implementation has a race.

Improvement points

• Run helgrind from the first version. I left it to the end and spent most of the time distrusting my code when the report was pointing at a problem that was not mine.
• Add more boundary cases to the runner besides the negative capacity: capacity 1 with two passengers waiting, a car with zero seats and a single passenger, a sequence of empty cars.