National Park Problem

A national park has a museum and a park for safari riding. There are M single-passenger cars and N visitors. Each visitor wanders around the museum for a while, and then lines up to take a ride in a safari car. When a car is available, it loads one passenger; waits for the visitor to signal that he/she is ready to start the ride; and travels around the park for a random amount of time before returning to the museum. If the M cars are all being used, a visitor who wants to ride must wait; if a car is ready to load but there are no waiting visitors, then the car must wait. After the ride in the park, the car signals the visitor when it is safe to exit the car, and the visitor leaves the park.

The algorithm skeleton described below simulates the above scenario. Complete the part denoted by ... in

the following algorithm by using semaphores to synchronize the N passenger processes and the M car processes. Assume the functions ride_around_park() and walk_around_museum() are given. Explain the purpose of each shared variable and semaphore.

Semaphore ...

int nFullCars = 0; // number of full cars

Process Visitor (i) {

walk_around_museum() ;

...

ride_around_park() ;

...

}

Process Car (j) {

do forever {

...

ride_around_park() ;

...

}

}

Requirements:

1) if i-th visitor is riding j-th car, the function ride_around_park() in Visitor(i) must be synchronized with the one in Car(j).

2) At any time, nFullCars tells how many cars are loaded with passengers.

3) At any time, at most one car can load passenger.

4) When the passenger exits from the car (unloading), the car must wait.