ThreadMentor: Bridge Crossing

Problem

Consider a narrow bridge that can only allow three vehicles in the same direction to cross at the same time. If there are three vehicles on the bridge, any incoming vehicle must wait as shown below.

When a vehicle exits the bridge, we have two cases to consider. Case 1, there are other vehicles on the bridge; and Case 2 the exiting vehicle is the last one on bridge. Case 1 is shown below. In this case, one vehicle in the same direction should be allowed to proceed.

Case 2 is more complicated and has two subcases. In this case, the exiting vehicle is the last vehicle on the bridge. If there are vehicles waiting in the opposite direction, one of them should be allowed to proceed. This is illustrated below:

Or, if there is no vehicle waiting in the opposite direction, then let the waiting vehicle in the same direction to proceed.

Given the problem above, run the vehicles are threads and design a monitor to ``control'' this bridge. More precisely, design a monitor with methods ArriveBridge() and ExitBridge(). When a vehicle arrives at the bridge, it invokes method ArriveBridge(), and when it exits the bridge, it invokes method ExitBridge().

Analysis

We shall assume that each vehicle thread will carry its direction (e.g. east-to-west or west-to-east). We also need a counter to keep track the number of vehicles on the bridge. With these information, it is not difficult to determine if a vehicle can be on the bridge. We check if the counter is zero. If the counter is zero, this vehicle can be safely on the bridge. If the counter is non-zero and less than the maximum count (i.e., 3), and the direction of this vehicle is the same as the direction of those on-bridge vehicles, this vehicle can also proceed. Otherwise, this vehicle must wait.

This brings up an important question: how do we block these vehicles? Because there are two moving directions, we need two condition variables. If the direction is 0 or 1, we can use a condition variable of two elements WaitingLine[2]. When a vehicle that has a direction i must wait, it waits on condition variable WaitingLine[i]. In addition to condition variables, we also need two counters, one for each direction so that when the last vehicle exits, it can determine which condition variable should be signaled. Therefore, when a vehicle must wait on a conditional variable, the counter associated with the moving direction of this vehicle is increased. After a vehicle is released from a condition variable, the corresponding counter must be reduced. In this way, we will be able to know if there are vehicles waiting in each moving direction.

Program

The following is the interface of this bridge monitor. Method isSafe() determines if a vehicle can be on the bridge safely. Private variable CurrentDirection keeps track the direction of the vehicles on the bridge, VehicleCount counts the number of vehicles on the bridge, and Waiting[2] counts the number of waiting vehicles in each direction.

#include "ThreadClass.h"

class BridgeMonitor: public Monitor 
{
     public:
          BridgeMonitor(char* Name);    // constructor  
          int isSafe(int Direction);
          void  ArriveBridge(int Direction);
          void  ExitBridge(int Direction);

     private:
          Condition *WaitingLine[2];    // blocks vehicles
          int  CurrentDirection;        // current direction of cars
          int  VehicleCount;            // # of vehicle on the bridge
          int  Waiting[2];              // # of east/west bound waiting
          char *Names[2];
};
Click here to download this file (bridge-mon.h)

The following is the implementation portion. The constructor makes this monitor a Hoare type, sets all counters to 0, and creates two condition variables. Method isSafe() receives a direction and does exactly what was discussed earlier.

Method ArriveBridge() is used when a vehicle arrives at the bridge. The vehicle must pass in its moving direction in Direction. In this method, isSafe() is called to determine if this vehicle can be on the bridge. If it can, vehicle count is increased by one and the control returns. After this, the vehicle will cross the bridge. If this vehicle cannot be on the bridge, it must wait on the condition variable corresponding to the moving direction (i.e., WaitingLine[Direction]). Before this waiting, the corresponding counter is increased to reflect this fact. Once a vehicle is released from its condition variable, the counter is decreased by one.

Method ExitBridge() is used when a vehicle exits the bridge. The vehicle must pass in its direction in Direction. Because this vehicle is no more on the bridge, the on-bridge vehicle count is reduced by one. If the new count is still greater than 0, meaning other vehicles are on the bridge, the condition variable of the same direction is signaled to release a vehicle that wishes to cross the bridge in the same direction. If the on-bridge vehicle count is 0, the condition variable of the other direction is signaled if there are waiting vehicles. Otherwise, the condition variable of the same direction is signaled.

There are two important questions. First, is the counting array Waiting[2] really necessary? Second, how would you do if this monitor is of Mesa type? Of course, changing if to while may work. Is there a better way to do it?

#include  <iostream.h>
#include  "ThreadClass.h"
#include  "bridge-Thrd.h"
#include  "bridge-mon.h"

BridgeMonitor::BridgeMonitor(char* Name): Monitor(Name, HOARE) 
{
     VehicleCount = 0;             // no vehicle on bridge
     Waiting[0] = Waiting[1] = 0;  // no vehicle waiting
     Names[0] = "EastWest";
     Names[1] = "WestEast";
     WaitingLine[0] = new Condition(Names[0]); // East->West waiting line
     WaitingLine[1] = new Condition(Names[1]); // West->East waiting line
};

int  BridgeMonitor::isSafe(int Direction)
{
     if (VehicleCount == 0)        // if no vehicle on bridge  
          return  TRUE;            // it is safe to cross            
     else if ((VehicleCount < MAX_VEHICLE) && (CurrentDirection == Direction))
          return  TRUE;            // if < max count in the same direction 
     else
          return  FALSE;           // otherwise, do not proceed
}

void  BridgeMonitor::ArriveBridge(int Direction)
{
     MonitorBegin();               
     if (!isSafe(Direction)) {     // is it safe to be on the bridge
          Waiting[Direction]++;    // no, wait at the bridge   
          WaitingLine[Direction]->Wait(); // block this vehicle
          Waiting[Direction]--;    // released
     }
     VehicleCount++;               // go on bridge             
     CurrentDirection = Direction; // set direction            
     MonitorEnd();                 // release monitor          
}

void  BridgeMonitor::ExitBridge(int Direction)
{
     MonitorBegin();                    // lock the monitor  
     VehicleCount--;                    // one vehicle exits        
     if (VehicleCount > 0) {            // have vehicles on bridge? 
          WaitingLine[Direction]->Signal(); // release the same direction
     }
     else {                             // no vehicle on bridge
          if (Waiting[1-Direction] != 0)    // opposite direction non-empty?
               WaitingLine[1-Direction]->Signal();  // release one of them
          else                          // release the same direction
               WaitingLine[Direction]->Signal();
     }
     MonitorEnd();                      
}
Click here to download this file (bridge-mon.cpp)

The thread portion is very simple. The following is the thread interface class. We have only one thread type that simulates a vehicle.

#include "ThreadClass.h"

#define   MAX_CROSSING  20
#define   MAX_THREADS   20
#define   MAX_VEHICLE   3                // max vehicle on bridge    
#define   TRUE          1
#define   FALSE         0

class Vehicle: public Thread 
{
     public:
          Vehicle(int id, int max_run);

     private:
          void ThreadFunc();
          int ID;
          int Max_Run;
};
Click here to download this file (bridge-Thrd.h)

Each vehicle iterates a number of times. In each iteration, it uses a random number in the range of 0 and 1 to determine the bridge crossing direction. Then, it displays its intention, calls method ArriveBridge(Direction). This vehicle may be blocked in the monitor if it cannot be on the bridge. Once the call returns, this vehicle is on the bridge for a while and calls ExitBridge(Direction) to get off the bridge. The following shows the implementation.

#include  <iostream.h>
#include  "ThreadClass.h"
#include  "bridge-Thrd.h"
#include  "bridge-mon.h"

static BridgeMonitor Bridge("Bridge");

void  Filler(char x[], int n)
{
     int  i;

     for (i = 0; i < n*2; i++)
          x[i] = ' ';
     x[i] = '\0';
}

Vehicle::Vehicle(int id, int max_run)
{
     ID = id;
     Max_Run = max_run;
     ThreadName.seekp(0, ios::beg);
     ThreadName << "Vehicle" << id << '\0';
}

void Vehicle::ThreadFunc()
{
     Thread::ThreadFunc();
     int     Direction;
     char    *Dir[2] = { "<--", "-->" };
     char    space[200];
     int     i;

     Filler(space, ID);
     cout << space << ThreadName.str() << " started ..." << endl;
     for (i = 1; i <= Max_Run; i++) {        // for each crossing   
          Delay();                           // rest for a while         
          Direction = rand() % 2;            // a random direction    
          cout << space << ThreadName.str() 
               << "(" << i << ") arrives at the bridge in direction " 
               << Dir[Direction] << endl;
          Bridge.ArriveBridge(Direction);    // arrive at the bridge 
          cout << space << ThreadName.str() 
               << "(" << i << ") crosses the bridge" << endl;
          Delay();                           // crossing the bridge
          Bridge.ExitBridge(Direction);      // exit the bridge 
          cout << space << ThreadName.str() 
               << "(" << i << ") is done" << endl;
     }
     cout << space << ThreadName.str() << " is gone forever ..." 
          << endl;
     Exit();
}
Click here to download this file (bridge-Thrd.cpp)

The following is the main program. After reads in the command line input, it initializes the random number seed and creates vehicle threads. Then, it waits until all vehicle threads terminate.

#include  <iostream.h>
#include  "ThreadClass.h"
#include  "bridge-Thrd.h"

void  main(int argc, char *argv[])
{
     Vehicle *OneVehicle[MAX_THREADS];  // vehicle classes 
     int     Threads;                   // # of vehicles   
     int     Max_Run, i;    

     if (argc != 3) {
          cout << "Use " << argv[0] 
               << " #-of-iterations #-of-vehicles" << endl;
          exit(0);
     }
     Max_Run = abs(atoi(argv[1]));
     Threads = abs(atoi(argv[2]));

     // validate user's input
     if (Threads > MAX_THREADS) {
          cout << "The no. of vehicles is too large.  Reset to " 
               << MAX_THREADS << endl;
          Threads = MAX_THREADS;
     }
     for (i = 0; i < Threads; i++) {               
          OneVehicle[i] = new Vehicle(i+1, Max_Run);
          OneVehicle[i]->Begin();
     }
     for (i = 0; i < Threads; i++)      // wait for vehicles       
          OneVehicle[i]->Join();
     Exit();
}
Click here to download this file (bridge-main.cpp)