KDP Exam (2026-02-18) Question 2

The Roller Coaster Problem. Assume there are $N$ passengers and $M$ cars in one roller coaster. Passengers alternate between walking around the amusement park and riding the roller coaster. One car can take at most $K$ passengers where $K < N$. Roller coaster ride can only begin if exactly $K$ passengers enter the roller coaster. Ensure that rides end in the order they began. Also ensure that passengers that waited longer to start their ride start earlier. Solve this problem using semaphroes.

#define N ... /* passenger count */
#define K ... /* car count */
 
Sem mutex = 1;
Sem canBoard = 0;
Sem canLeave = 0;
Sem allBoarded = 0;
Sem allLeft = 0;
 
int waitCount = 0;
int rideCount = 0;
 
void passenger() {
    while (true) {
        // ... walk around the amusement park ...
 
        // Arrive at car
        wait(mutex);
        waitCount += 1;
        if (waitCount >= K) {
            signal(canBoard);
        }
        signal(mutex);
        wait(canBoard);
 
        // Enter the car
        wait(mutex);
        waitCount -= 1;
        rideCount += 1;
        if (rideCount < K) {
            signal(canBoard);
        } else {
            signal(allBoarded);
        }
        signal(mutex);
 
        // ... ride the roller coaster ...
 
        // Leave the car
        wait(canLeave);
        wait(mutex);
        rideCount -= 1;
        if (rideCount > 0) {
            signal(canLeave);
        } else {
            signal(allLeft);
        }
        signal(mutex);
    }
}
 
void car() {
    while (true) {
        wait(allBoarded);
 
        // ... do the ride ...
 
        signal(canLeave);
        wait(allLeft);
    }
}