ThreadMentor: The Roller Coaster Problem

Problem

Suppose there are n passengers and one roller coaster car. The passengers repeatedly wait to ride in the car, which can hold maximum C passengers, where C < n. However, the car can go around the track only when it is full. After finishes a ride, each passenger wanders around the amusement park before returning to the roller coaster for another ride. Due to safety reasons, the car only rides T times and then shot-off.

Suppose the car and each passenger are represented by a thread. How would you write a program, using semaphores only, that can simulate this system and fulfill the following requirements:

1. The car always rides with exactly C passengers;
2. No passengers will jump off the car while the car is running;
3. No passengers will jump on the car while the car is running;
4. No passengers will request another ride before they can get off the car.

Analysis

The first issue we face is How do we make sure that exactly C passengers are on the car? Do we need a counter? If we have a counter, how do we protect it from race conditions? If we use such a counter, then after C passengers are on board, all subsequent passengers must be blocked because we have had a full load. Therefore, this is a Count-down-and-lock scheme and a semaphore with initial value C suffices. So, we sort of solve the first issue with a semaphore. More precisely, each passenger must go through this semaphore. If the counter of this semaphore is non-zero, a passenger can pass through and is ready to be on the car. Otherwise, this passenger is blocked because the car has had a full load. Who is responsible to signal this lock so that other passengers can be on the car? Obviously, the car should do it. When the car becomes empty and is ready for the next ride, the car should signal this semaphore C times to release C passengers. This is the first wait/signal pair shown in the diagram below.

Is this good enough? No, it is not. If there are less than C passengers waiting to take a ride, the car will not have a full load and should not run. To make sure that C passengers will be in car before the car can run, we need a ticket counter, counting 1 passenger on board, 2 passengers on board, and so on. Once the C-th passenger's ticket is received, the car is allowed to go. So, we need a check-in semaphore. After a passenger is allowed to take a ride, he goes for check in. A counter, initially zero, is used to count the number of checked in passengers. After checks in, a passenger must allow the next passenger to check in. The only exception is the C-th passenger, he must also inform the car that all passengers have checked in and on board. In the diagram above, the second semaphore (i.e., red square) is the check-in semaphore. The signal sent by the C-th passenger notifies the car so that the car can run.

Now the car is running with C passengers on board. How could we forbid on board passengers to jump off before the car stops? Obviously, we need a semaphore, with initial value 0, for those on-board passengers to wait on. This is the third semaphore (i.e., red square) a passenger must wait on as shown in the diagram above. When the ride completes and the car stops, the car signals this semaphore C times to release all on board passengers. In the diagram above, the car releases its passengers one-by-one. More precisely, the car signals the semaphore that the on-board passengers are waiting on (simulating riding) and waits for the released passenger's notification indicating that he is off the car. But, why one-by-one? The car can certainly signal C times to release all C passengers and go back for the next ride. However, it is possible that after these C signals the car loops back and starts loading the next C passengers while the on-board passengers are still getting off the car. Worse, it is also possible that while passengers are unloading themselves the car may be running for the next ride. This is the reason that the car releases its passengers one-by-one.

In summary, a passenger joins the queue for a ride, waits for checking in after gets the permission to be on-board, signals the car if he is the C-th passenger checked in, releases the lock for the next passenger to check in, rides in the car until the car releases him at the end of this ride, notifies the car that he is off after receives the get-off-the-car notification, and finally loops back for the next ride. The car is simpler. We assume initially that it is empty and hence is immediately ready for a ride. Then, the car releases C passengers from the queue and waits until it is notified by the C-th passenger, runs for a while, notifies each passenger to get off the car and waits for their "I am off" notification, and finally loops back for the next run.

The following is the equivalent pseudo-code of the above diagram. We use a procedure Take-Ride() that encapsulates all the activities a passenger must take. Variable count is used to count the number of checked in passengers, initially zero. The initial value of semaphore Queue is C because it serves as a count-down-and-lock semaphore. Semaphore Boarding must have zero initial value because the car must be blocked until all passengers are on board. Semaphore Riding must also have initial value zero because without notification all passengers must remain on board. So is semaphore Unloading. Finally, semaphore Check-In has initial value 1.

Wait a minute, you might say, there is a potential race condition because variable count is not protected! There is no such race condition. Here is why.

• Note that exactly C passengers can pass through semaphore Queue.
• Semaphore Check-In, with initial value 1, serves as a lock. In fact, replacing it with a mutex lock would work perfectly fine. Therefore, at most one passenger can have access variable count at any time.
• The only other place where variable count is accessed is when the car starts to unload the passenger. The car simply resets this variable to zero. At this moment, all C passengers are blocked on semaphore Riding, and hence the car is the only thread that has access to variable count.
• Therefore, no race condition in this pseudo-code.

Program

Converting the above pseudo-code to a program is an easy job. Keep in mind that we have two types of threads: passengers and car. The following shows the definition of these two threads. Each passenger receives his ID and the car capacity from its constructor, and the car thread receives the car capacity and the number of rides that the car must perform.

#include "ThreadClass.h"

#define MAX_PASSENGERS   20   // Maximum number of passengers 
#define MAX_CAPACITY     10   // Maximum capacity of the car  
#define MAX_NO_RIDES     10   // Maximum number of car rides

class PassengerThread: public Thread 
{
     public:
          PassengerThread(int Number, int capacity);
          void TakeRide();
     private:
          int  passenger_Id;
          int  Capacity;      // capacity of the car  
          void ThreadFunc();
};

class CarThread: public Thread 
{
     public:
          CarThread(char *Name, int capacity, int noOfRides);
     private:
          void ThreadFunc();
          int  Capacity;      // capcity of the car  
          int  No_of_rides;   // number of times the car rides
};

There are two static variables that can only be used in this file and are not visible to other functions in other files. Variable On_board_passenger_counter counts the number of passengers on board. This is the variable count in the pseudo-code. Array On_board_passenger_ID[ ] stores the IDs of on board passengers. Each passenger thread contains a method TakeRide() that implements the activities of a passenger. In this way, each passenger thread simply loops forever. The car thread loops for No_of_rides times. For each iteration, it performs the tasks as shown in the above diagram and the pseudo-code. Note that after No_of_rides iterations, the car thread exits!

#include <iostream>

#include "roller-coaster.h"

// static data variables

static int On_board_passenger_ID[MAX_CAPACITY];   // IDs of on board passengers  
static int On_board_passenger_counter = 0;        // number of passengers on board

// static semaphores

static Semaphore Queue("WaitingQueue", 0);   // passenger waiting for a ride
static Semaphore CheckIn("CheckIn", 1);      // check in counter 
static Semaphore Boarding("Boarding", 0);    // controls the boarding process
static Semaphore Riding("Riding", 0);        // keep passengers on the car so 
static Semaphore Unloading("Unloading", 0);  // controlling the unloading process

strstream *Filler(int n)
{
     int  i;
     strstream *Space;

     Space = new strstream;
     for (i = 0; i < n; i++)
          (*Space) << ' ';
     (*Space) << '\0';
     return Space;
}

PassengerThread::PassengerThread(int Number,  int capacity)
{
     passenger_Id = Number;
     Capacity = capacity;
     ThreadName.seekp(0, ios::beg);
     ThreadName << "Passenger" << passenger_Id << '\0';
}

void PassengerThread::TakeRide()
{
     strstream *Space;

     Space = Filler(3);       // build leading spaces

     Queue.Wait();            // join the queue for a ride
     CheckIn.Wait();          // time to check in

     // save my name and increase the counter
     On_board_passenger_ID[On_board_passenger_counter] = passenger_Id;
     On_board_passenger_counter++;
     cout << Space->str() << ThreadName.str() 
          <<" is on board the car" << endl;

     // if I am the last one to be on board, boarding completes and the car is full
     if (On_board_passenger_counter == Capacity)  
          Boarding.Signal();   
     CheckIn.Signal();        // allow next passenger to check in
     Riding.Wait();           // I am riding in the car
     Unloading.Signal();      // get off the car
}

void PassengerThread::ThreadFunc() 
{
     Thread::ThreadFunc();

     while (1) {        
          Delay();       // wandering for a while
          TakeRide();    // take a ride
     }
     Exit();
}

CarThread::CarThread(char *Name, int capacity, int noOfRides)
          : Thread(Name)
{
     Capacity = capacity;
     No_of_rides = noOfRides;
}

void CarThread::ThreadFunc()
{
     Thread::ThreadFunc();
     int i, j;

     for (i = 1; i <= No_of_rides; i++) {               
          for (j = 1; j <= Capacity; j++)  
               Queue.Signal();          // allow CAPACITY passengers to check in
          Boarding.Wait();              // wait for boarding to complete

          // print on boarding passenger names
          cout << "The car is running for the " << i 
               << " time with passengers ";
          for (j = 0; j < Capacity; j++) 
               cout << " " << On_board_passenger_ID[j];
          cout << endl;
          Delay();                      // ride for a while

          On_board_passenger_counter = 0;  // start unloading passengers            
          for (j = 1; j <= Capacity; j++) {
               Riding.Signal();         // release a passenger
               Unloading.Wait();        // wait until this passenger is done
          }
          // definitely, the car is empty and goes for the next run
     }
     // done here and show messages
     cout << "The car is shot-off for maintenance" << endl;
     Exit();
}

The main program is easy. It creates the only car thread and a number of passenger threads and runs them. Finally, the main thread only joins with the car thread because only the car thread will exit. Once the car exits, the indicated number of iterations has been performed. Because the main thread exits right after the car thread exits, all passenger threads are terminated automatically as a result.

#include <iostream>
#include <stdlib.h>

#include "roller-coaster.h"

int main(int argc, char *argv[]) 
{
     int Capacity,            // capacity of the car 
         No_of_rides,         // number of times the car rides 
         No_of_passengers;    // number of passengers in the park 
     int i;
     PassengerThread *Passenger[MAX_PASSENGERS];

     if (argc != 4) {         // get user input
          cout << "Use " << argv[0] 
               << " #-of-Passengers car-capacity #-of-rides" << endl;
          exit(0);
     }
     else {
          No_of_passengers = abs(atoi(argv[1]));
          Capacity = abs(atoi(argv[2]));
          No_of_rides   = abs(atoi(argv[3]));
     }

     if (Capacity > No_of_passengers) { 
          cout << "Please check your input, car capacity "
               << "must be less than the no. of passengers" << endl;
          exit(1);
     }
     if (No_of_passengers > MAX_PASSENGERS) {
          cout << "The number of passengers is too large. " 
               << "Reset to " << MAX_PASSENGERS << endl;
          No_of_passengers = MAX_PASSENGERS;
     }
     if (Capacity > MAX_CAPACITY) {
          cout << "Car capacity is too large.  " 
               << "Reset to " << MAX_CAPACITY << endl;
          Capacity = MAX_CAPACITY;
     }

     CarThread Car("Car", Capacity, No_of_rides); // create and run the car
     Car.Begin();

     for (i = 1; i <= No_of_passengers; i++) {    // create and run passengers
          Passenger[i] = new PassengerThread(i, Capacity);
          Passenger[i]->Begin();
     }
     Car.Join();    // only join with the car
     Exit();
     
     return 0;
}