TWiki> CS385spring11 Web>Homework6 (revision 1)EditAttach


Homework 6 - elevator scheduling

This is our first 10 point, 2 week homework. Compared to our previous (5 point) homeworks, there will be less emphasis on basic programming skills (which it is hoped you have acquired enough of by now), and more on algorithmic or system particulars. While the homework is due 2 weeks from now, you are encouraged to start early, so you can take full advantage of office hours.

This time, we continue our work with the elevator controller, based on my solution for hw5. See the lecture on Monday Feb 15 for a discussion of how that solution works.

However, this time, the multithreaded/concurrent programming aspects are less of a concern (they are mostly handled), and scheduling is our focus. A few things have changed, to make things a little more interesting:

  • like in a normal building, passengers are more likely to travel to or from the bottom floor.
  • passengers take several trips on the elevator, separated by a short random delay
  • each run has a fixed duration, rather than a fixed number of trips
  • our goal is to maximize throughput (number of trips), under different sets of constraints.

The provided homework template does a reasonable job of maximizing "throughput". However, it does this at the expense of fairness.

Trip Time Fairness

With the template solution, some trip requests take a long time to complete (from request to exiting at the requested floor), and others go quickly. The difference between min and max is often more than 20x. Provide a solution where the max trip duration is no more than 2x the mean trip duration, over all passengers.

Turn-in requirement: put your entire solution in a file called hw6i1.c

Turn-in requirement: put your entire solution in a file called hw6i2.c
Edit | Attach | Print version | History: r5 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2011-02-14 - 01:43:49 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF