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 delay. Except for part 4, this delay grows linearly with the passenger number.
  • 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.

There are three test scenarios: make highload, make mediumload, and make lowload. Make sure your solution provides the desired performance on all three scenarios. The total number of trips should remain above 200, 450 and 1000 respectively.

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 100% over 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

Passenger Service fairness

With the above solution, the more aggressive passengers (those with lower numbers), get more trips and quicker trips. Provide a solution where the more aggressive passengers may get more trips, but on average need to wait longer for their trips (unless there are so many elevators that nobody needs to wait long!).

HINT: a round-robin scheduler solution would work well here.

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

Static passenger prioritization

The passengers that wait the longest between elevator trips 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 1/3 of the number of trips of 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 hw6i3.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: For the first request, all passengers have equal priority. After that, you'll need to compute the inter-arrival time of requests to determine priority. Use gettimeofday() to get the current time.

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

This topic: CS385spring11 > Homework6
Topic revision: r5 - 2011-02-25 - 05:31:19 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF