Traffic
Intersection
Concurrency · Semaphores · Deadlock prevention
A concurrent traffic intersection simulation in C using POSIX threads and semaphores. Sixteen car threads navigate a four-way single-lane intersection simultaneously — each acquiring exactly the semaphores its path requires, with no deadlock and no starvation.
The intersection has four single-lane approaches — north, south, east, and west. Each car is a pthread that is spawned the moment its arrival time is reached. The main loop polls elapsed time and creates threads in order, passing each car's struct as its argument.
Every car thread runs through three functions in sequence: ArriveIntersection, CrossIntersection, and ExitIntersection. Arrive handles all waiting and semaphore acquisition. Cross
releases the head-of-line lock and spins for the time the turn takes. Exit releases the location and
incoming-lane semaphores once the back-to-back count reaches zero.
A dedicated traffic light thread runs concurrently in an infinite loop, cycling north-south green for 18
seconds, yellow for 2 seconds, then east-west green for 18 seconds, and so on. The light state is a shared
enum that car threads read inside their sem_trywait loops.
void *Car(void *arg) { car *c = (car *)arg; /* Wait at head-of-line, then acquire the semaphores needed for this car's path. */ ArriveIntersection(c); /* Release head-of-line, spin for turn time. */ CrossIntersection(c); /* Decrement back-to-back count; release loc and incoming semaphores when count == 0. */ ExitIntersection(c); return NULL; }
void *TrafficLight() { bool ns_green; while (true) { ns_green = north_south_light == green; Spin(TIME_GREEN); // 18 s ns_green ? (north_south_light = yellow) : (west_east_light = yellow); Spin(TIME_YELLOW); // 2 s if (ns_green) { north_south_light = red; west_east_light = green; } else { west_east_light = red; north_south_light = green; } } }
The 12 semaphores are split into three types. Each type controls access at a different level of the intersection — the approach lane, the light gate, and the specific corner cells a car's path sweeps through.
ArriveIntersection, released at the start of CrossIntersection. Enforces FIFO within each single lane — only one car per
side can be negotiating the intersection at a time.ArriveIntersection via sem_trywait loop alongside
the light check. Released in ExitIntersection when the back-to-back count
reaches zero. Represents the exit-side lane a car will emerge into.south_west/south_east_loc
ArriveIntersection for the specific corner cell(s) a car's path occupies.
Released in ExitIntersection when the back-to-back count hits zero. Right
turns need none — they don't enter the center.Every car acquires its
semaphores using a sem_trywait loop that simultaneously checks the traffic
light state and the required semaphore availability. This avoids holding a semaphore while blocked on the
light — preventing the circular wait that would cause deadlock.
| From → To | Semaphores acquired |
|---|---|
| ^ → ^ straight | south_side_hol south_east_loc north_side_inc |
| ^ → < left | south_side_hol north_west_loc west_side_inc |
| ^ → > right | south_side_hol east_side_inc |
| v → v straight | north_side_hol north_west_loc south_side_inc |
| v → > left | north_side_hol south_east_loc east_side_inc |
| v → < right | north_side_hol west_side_inc |
| > → > straight | west_side_hol south_west_loc east_side_inc |
| > → ^ left | west_side_hol north_east_loc north_side_inc |
| > → v right | west_side_hol south_side_inc |
| < → < straight | east_side_hol north_east_loc west_side_inc |
| < → v left | east_side_hol south_west_loc south_side_inc |
| < → ^ right | east_side_hol north_side_inc |
Purple circles — incoming lane (inc)
Gold squares — intersection location (loc)
There are 12 count variables — one for each combination of direction and turn type (e.g. count_south_straight, count_west_left). When a car
successfully acquires its semaphores and begins crossing, it increments its count. When it exits, it
decrements.
The key condition: a car skips the sem_trywait loop entirely if its count is
already non-zero and the light is green. This means the location and incoming-lane semaphores are still
held from the previous car on that same path — so the new car simply piggybacks on that existing hold and
crosses without any additional acquisition.
The semaphores are only released in ExitIntersection when the count drops
back to zero — meaning the last car in the back-to-back group has finished crossing.
Right turns are a special case. The
back-to-back condition for straight and left turns checks light != green —
those moves require a green light. Right turns can be made on green or yellow, so the condition is
flipped: light == red. If the light isn't red, a right-turning car can go
immediately without even entering the wait loop, as long as its count is non-zero.
This also means right turns cannot back-to-back on red. If the light is red, the first right-turner must wait to acquire the exit-side incoming semaphore. The next right-turner behind it has to wait for the first to finish and release — it won't piggyback. This prevents a queue of right-turners from holding the incoming semaphore through an entire red phase, blocking the cross-traffic that has the green from using that exit lane.
sem_trywait loop. Even if
the car ahead just released the intersection, the next car must re-acquire everything from scratch.
count > 0 and the light is green, skip
acquisition entirely. The semaphores stay held until the last car in the group exits.// Only acquire semaphores if this is the // first car, or the light isn't green yet. if (count_south_straight == 0 || north_south_light != green) { int r = sem_trywait(&south_east_loc); int r1 = sem_trywait(&north_side_inc); while (north_south_light != green || !(r == 0 && r1 == 0)) { if (r == 0) sem_post(&south_east_loc); if (r1 == 0) sem_post(&north_side_inc); r = sem_trywait(&south_east_loc); r1 = sem_trywait(&north_side_inc); } } count_south_straight++;
count_south_straight--; if (count_south_straight == 0) { sem_post(&south_east_loc); sem_post(&north_side_inc); }
// Straight/left: condition is light != green. // Right turn: condition is light == red. // Green or yellow — right turn can proceed. if (count_south_right == 0 || north_south_light == red) { int r = sem_trywait(&east_side_inc); // Unlike straight/left, this loop does not check the // light — only whether the semaphore is available. // This is what allows right turns on red: the car // waits purely for the exit lane to be free. while (!(r == 0)) { r = sem_trywait(&east_side_inc); } } count_south_right++;
// NS phase — cars 0–9 (north-south light starts green) car_arr[0] = { .cid=0, .arrival_time= 1.0, .dir_original='^', .dir_target='^' }; car_arr[1] = { .cid=1, .arrival_time= 1.9, .dir_original='^', .dir_target='^' }; car_arr[2] = { .cid=2, .arrival_time= 3.2, .dir_original='^', .dir_target='<' }; car_arr[3] = { .cid=3, .arrival_time= 3.4, .dir_original='v', .dir_target='v' }; car_arr[4] = { .cid=4, .arrival_time= 4.1, .dir_original='v', .dir_target='>' }; car_arr[5] = { .cid=5, .arrival_time= 4.3, .dir_original='^', .dir_target='^' }; car_arr[6] = { .cid=6, .arrival_time= 5.6, .dir_original='>', .dir_target='^' }; car_arr[7] = { .cid=7, .arrival_time= 5.8, .dir_original='<', .dir_target='^' }; // Opposite left turns arriving simultaneously car_arr[8] = { .cid=8, .arrival_time=10.0, .dir_original='^', .dir_target='<' }; car_arr[9] = { .cid=9, .arrival_time=10.0, .dir_original='v', .dir_target='>' }; // EW phase — cars 10–15 (east-west light green after t=20) car_arr[10] = { .cid=10, .arrival_time=21.0, .dir_original='>', .dir_target='>' }; car_arr[11] = { .cid=11, .arrival_time=21.5, .dir_original='<', .dir_target='<' }; car_arr[12] = { .cid=12, .arrival_time=22.0, .dir_original='>', .dir_target='^' }; car_arr[13] = { .cid=13, .arrival_time=22.5, .dir_original='<', .dir_target='v' }; car_arr[14] = { .cid=14, .arrival_time=23.0, .dir_original='>', .dir_target='v' }; car_arr[15] = { .cid=15, .arrival_time=23.5, .dir_original='<', .dir_target='^' };