Before doing these problems, read in the
book about processes, synchronization, monitors, and mutual exclusion.
This is a team assignment. Work as a team and submit a single team
report. Work to contribute equally to the report.
The objective of this problem is to design a concurrent algorithm, in the form of monitor, that will control an elevator in a building. This outline will give the general overview of what is required. You will have to work out the details and make various design decisions along the way. When you get done you want a multi-threaded algorithm that is easily explained and you have a convincing argument that it will work correctly.
A building has 8 floors served by one elevator. Each floor has elevator call buttons for the rides available from that floor; the buttons are labelled UP and DOWN. Inside the elevator is a selector panel where each person selects the floor they wish to exit at. Each passenger always pushes the request button (and when inside the floor-selector button) even it another person already pushed it.
You can model a passenger as a looping thread. The loop contains two parts: a delay (representing the person doing other things) and an interaction with the elevator. When a passenger-thread comes to its elevator interaction section, it selects the two parameters i and j (floor of boarding and floor of exit) at random from among the 8 floors. It uses the function UP(i) to represent pushing the up-request button on floor i. It uses the function DOWN(i) in a similar way. The elevator may skip stops at floors whose only requests are in the opposite direction of the elevator's motion.
After pushing a call button, the passenger must wait until the elevator comes. Once inside the elevator, the passenger pushes a selector button to indicate the desired exit floor; this can be represented by the function SELECT(j). A passenger remains in the elevator until it stops at the selected floor. Only when the passenger finally exits the elevator does the passenger thread loop back and start again.
The state of the system at a given time can be represented by the elevator motion and the status of all requests. The elevator motion can be represented as one of the states (quiescent, up, down). Quiescent means that the elevator is stopped and no requests are pending. The set of request states can be represented as an 8x3 matrix, with one row for each floor and the columns UP, DOWN, SELECT. An entry represents the number of unsatisfied requests for that combination of floor and elevator-function. For example, if the row 3 contains (0,2,4) it means that no one has called for UP at floor 3, 2 have called for DOWN at floor 3, and 4 are in the elevator planning to get off at floor 3.
With this state representation it is easy to implement the "elevator policy" of moving in one direction until all requests are satisfied, before reversing direction. The controller can examine the request matrix at each floor and decide whether to continue moving in the same direction, reverse, or become quiescent.
For parameters, assume that the elevator takes 15 seconds to move from one floor to the next. When it stops, it takes each passenger planning to exit 2 seconds to get off, and 2 seconds for each passenger waiting to get on to get on.
If the elevator has embarked toward floor j and then, after it starts to move, a new request for floor k en route arrives, the elevator should stop at floor k. (Assume k is between the current elevator position and the destination floor j.)
In addition to the passenger threads, you may need a thread to represent the elevator car.
The controller should be robust in the sense that it does not get deadlocked when passengers do not do what they say. For example, someone could press UP(i) and then get on when the elevator stops moving down. Or, someone inside could press SELECT(j) and then get off at a floor other than j.