Homework 5 - Concurrent Elevator Controller

A M -story highrise has N elevators in a single "elevator bank", each able to serve every floor of the building. Contrary from most elevator designs, there are no buttons to choose a destination floor inside the elevator. Instead, the elevator lobby at each floor has M individual "destination floor" buttons, and passengers choose their destination by pushing the appropriate button. Once a button is pushed, a display near the buttons tells the passenger which elevator door to wait by. In this assignment, elevators serve only one passenger at a time.

Your assignment is to create an elevator controller that ensures that all passengers receive service, minimizing the mean and max time between button push and arrival at the destination floor.

The code

The homework 5 template is a multithreaded program which simulates passengers and elevator travel. There is one thread per elevator, and one thread per passenger. There is a fixed number of passengers, that embark on a number of trips each. These threads interact with each other through a central elevator controller, which is your responsibility to implement.

The central controller responds to the following three function calls:

%CODE{ lang="c" }%

/* called whenever a passenger pushes a button in the elevator lobby. call enter / exit to move passengers into / out of elevator return only after the passenger has been delivered to requested floor */ void passenger_request(int passenger, int from_floor, int to_floor, void (*enter)(int, int), void(*exit)(int, int));

/* called whenever the doors are about to close. call move_direction with direction -1 to descend, 1 to ascend. must call door_open before letting passengers in, and door_close before moving the elevator */ void elevator_ready(int elevator, int at_floor, void(*move_direction)(int, int), void(*door_open)(int), void(*door_close)(int));

%ENDCODE%

Performance Expectations

The template code works correctly, but is terribly slow. In part, this is because passengers often "miss" the elevator (don't get in in time), or miss their floor (stay on the elevator). In part, it is because the elevator stops at every floor, and we only use one elevator.

For a full score, have a fully working solution that uses all available elevators, and finishes the final case in "make test" in at most 10 seconds. A more exact performance expectation will be provided shortly.

Notes

  • Every passenger pushes a button.
  • Passengers can't change their minds, and will wait until the elevator shows up, no matter how long it takes.
  • Passengers will stay in the elevator until they reach their desired floor, no matter how long it takes.
  • Elevators have finite capacity.
Edit | Attach | Print version | History: r13 | r11 < r10 < r9 < r8 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r9 - 2011-02-09 - 21:20:22 - Main.jakob
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF