Scenario 1: Sleeping Barber Problem

The Sleeping Barber Problem was first proposed by Edsger W. Dijkstra in 1968. (E. W. Dijkstra, "Co-operating Sequential Processes", in F. Genuys (ed.), Programming Languages, Academic Press, 1968, pp. 43-112.)

Diagram of Barbershop
Three barbers work independently in a barber shop:

  1. Simulate each barber and each customer as a separate process.
  2. Altogether, 30 customers should try to enter.
  3. Use a random number generator, so a new customer arrives every 1, 2, 3, or 4 seconds. (This might be accomplished by an appropriate statement sleep(1+(rand()%4)); .
  4. Similarly, use a random number generator, so each haircut lasts between 3 and 6 seconds.
  5. Each barber should report when he/she starts each haircut and when he/she finishes each haircut.
  6. Each customer should report when he/she enters the barbershop. The customer also should report if he/she decides to leave immediately.
  7. Similarly, if the customer must stand or sit in the waiting room, the customer should report when each activity begins.
  8. Finally, the customer should report when the haircut begins and when the customer finally exits the shop.

Scenario 2: Baboons Crossing a Canyon

This problem is described in Operating Systems: Design and Implementation, Second Edition by Tannenbaum and Woodhull.

A student majoring in anthropology and minoring in computer science has embarked on a research project to see if African baboons can be taught about deadlocks. She locates a deep canyon and fastens a rope across it, so the baboons can cross hand-over-hand.

Passage along the rope follows these rules:

  1. Simulate until 50 baboons have crossed each way, then stop.
  2. baboons arrive every 1, 2, 3 or 4 seconds, randomly coming from either the east or the west with equal probability.
  3. traversal of the canyon takes 3, 4, 5 or 6 seconds with equal probability.
  4. all baboons currently on the rope crossing the canyon must be moving in the same direction
  5. Your solution should avoid starvation (i.e. making a baboon wait indefinitely). so, for example, when a baboon that wants to cross from the east arrives at the rope and finds baboons crossing from the west, he waits until the rope in empty, but no more baboons arriving from the west are allowed to start until at least one baboon has crossed the other way.

Scenario 3: Roller Coaster with Several Cars

This exercise is a slightly modified version of exercises 4.9 and 4.10 in Stephen Hartley, Concurrently Programming: The Java Programming Language.

An amusement part includes a roller coaster ride. Use of the roller coaster follows these rules.

  1. Values m, n, S, C, and W must be program constants that can be changed in one place in your simulation code.
  2. Run the simulation for 120 time units.
  3. Compute the average time that a passenger must wait to be seated after deciding to take a ride.
  4. Use semaphores for synchronization. (Additional communication via sockets is allowed, but do not use sockets unless such communication is clearly needed.)