TWiki> CS385spring11 Web>Homework6 (revision 3)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 the 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 taken care of by the hw5 solution), 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.

HINT: for all of these, the complexity (as in run-time CPU consumption) of your solution is not of great importance: my solutions are quite inefficient, but still only use less than 15% of the CPU.

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.

HINT: a FIFO solution would probably work well here.

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

Static passenger prioritization

The passengers that use the elevator the least happen to be the most important passengers, and should get priority service. Here, you may assume that a higher-numbered passenger (as provided in passenger_request) is a higher-priority passenger. Provide a solution where higher-priority passengers reliably receive better service (shorter mean and max trip times) than lower-priority passengers, but make sure that no passenger completes less than half as many trips than the highest priority passenger.

HINT: here, a weighted round-robin solution may be a good idea.

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

Dynamic passenger prioritization

Here, do the same thing as in static passenger prioritization, but do not assume that the passenger number corresponds to their priority (we will use a modified main.c). Instead, have your solution base priority on inter-request time: passengers that issue frequent requests have lower priority than those that issue infrequent requests.

HINT: you'll need to compute the mean inter-arrival time of requests. To do this, use gettimeofday() to get times, and an exponentially weighted moving average (EWMA) to compute the mean over time.

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

Edit | Attach | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r3 - 2011-02-14 - 16:40:20 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF