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().
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.
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) |
|
|
|