CSC 270 Assignment 3 Due Monday, November 25 at 6:10 in tutorial. The will be NO EXTENSIONS. Start NOW. You have 18 days. This assignment will take longer than you expect. Note on the grading scheme below that more marks are given for your design decisions and report than are given for the actual implementation! Check the newsgroup periodically for bug fixes. Bugs are guaranteed to appear in the code that I've provided (it's more than 2400 lines). When I find one, I'll post a fix. It is very unlikely that these fixes will be in parts of the code that you're modifying (since that's restricted to a few functions), so it should be easy for you to incorporate the fixes that I post. Elevator Scheduler ------------------ Your task is to implement part of an elevator simulation and to gather some statistics about it. The simulation has the following events: a person arrives, an elevator arrives, and an elevator departs. A working simulation is provided, which you will modify. A. Person Arrivals You must model arrival times on a particular floor with an exponential distribution. See page 37 of the Readings on how to generate the next arrival time. When a person arrives, they must choose a floor. If they aren't already on the ground floor (floor 0), there should be a 50% probability that they will choose the ground floor and equal probabilities that they choose any other floor (other than their current one). If they are on the ground floor, they should choose any other floor with equal probability. A.1 Modify the function Floor::schedule_next_appearance() to do this. Make sure that your mean arrival time is equal to the value of `mean_arrival_time'. A.2 Collect statistics about intervals between arrival times and about destination floors by adding a function (and variables) to the Statistics class. Call that function from Floor::schedule_next_appearance() whenever you choose the next arrival time and next destination floor. The Statistics::final_report() function should be modified to output the mean interval time and, for each floor, the fraction of the time that floor was chosen (as a number in [0,1]). A.3 Modify the Statistics class to gather other useful information and to report that in Statistics::final_report(). For example, a mean waiting time before boarding an elevator would be interesting, as would the variance of waiting times. You will be marked on the quality of your choices in what additional information to provide. You will not receive marks for quantity (and might lose marks if you provide too much quantity). B. Elevator Arrivals You must build an efficient elevator scheduling algorithm. The best algorithm (according to the tutor's tests) will be given a small prize. When an elevator arrives at a floor, it calls the function Controller::update_destinations(). In this function the controller decides what the future destinations of the elevator will be, as well as deciding whether it will change direction or become idle. When a person first appears on a floor, that person calls the function Controller::request_elevator(). In this function the controller records the request and might start up an idle elevator. B.1 Modify these two controller functions to implement your elevator scheduling algorithm. Your algorithm may make use of only the information in the requests, locations, desinations, and directions arrays. Your algorithm must cause an elevator to become idle if it arrives at a floor and there are no outstanding requests. It must choose to start up such an elevator at some point, too, but when to do so is your decision. Marks will be based on the correctness and efficiency of your algorithm. Your Assignment --------------- 1. Copy the C code into your directory: % cd % cp -r /u/jstewart/csc270/elev . 2. Go into that directory and compile the files: % cd elev % make 3. Run the working program that I've provided: % setenv LD_LIBRARY_PATH /usr/openwin/lib:/u/csc418h/include/Mesa/lib % elev % elev -- gives a list of program options % elev -m c colour mode (default is monochrome) % elev -i .5 report interval (larger = faster animation) % elev -dg no graphics % elev -f 4 -e 1 4 floors and 1 elevator You should probably put the `setenv' line above into your ~/.cshrc file. 5. Look at ALL the *.C and *.h files. Read ALL the comments at the tops of the functions and in the class definitions (in *.h). 6. Think about how you're going to do A.1, A.2, A.3, and B.1 above. Think lots. Time spent thinking will make subsequent programming much easier. Write down a description of your elevator algorithm, since that will clarify your ideas and will be included later in your report, anyway. 7. Implement A.1, A.2, A.3, and B.1 above. Do these one at a time, from the easiest task to the hardest, and test each thoroughly before proceeding to the next. 8. Write the report. Testing ------- Run tests of your algorithm with various configurations of floors and elevators and with various mean arrival times and random seeds. Record your statistical output. Report ------ Use clear and concise English in your report. Poor or obscure English will be penalized. R.1. Describe, without pseudocode, how you generate random arrival times and random floor choices that satisfy the constraints above. R.2. Describe, without pseudocode, your elevator algorithm. Discuss any special features that make it novel or efficient. R.3. Include your statistical output and discuss it. In particular, discuss the additional statistical output that you produced, why it is interesting, and what it tells about your simulations. Discuss the conditions under which your algorithm might not keep up with requests. What to hand in --------------- Hand in on paper: 1. Your reports described above. 2. Listings of ALL the files that you modified, and only those files. 3. Printed output of several samples of your statistical output. On the paper, write a brief explanation of the meaning of your output. 4. Tape the sheet below to an envelope put your assignment inside the envelope. Hand in with the `submit' command: 5. All the files necessary to compile and run your programs. This includes the Makefile, since the tutor will execute % make with the files that you submit. If the compilation fails, you lose marks. To submit, go into the elev directory. All the necessary files must be in that directory (including a README file, if you wish). Execute % make clean which removes all *.o and *~ files. Then execute % submit -N a3 csc270h * Neat Additional Modifications ----------------------------- Only consider this after you've completed the assignment and submitted it electronically and written the report and put it in the envelope! The elevator simulation can be modified in many ways. For example, you could have different types of person, based on the Person class, which are drawn differently and have different behaviours. You could add stairs and have people walk the stairs in some cases (this is not easy to implement). Only if you have time, modify the elevator simulation in some interesting way. The most interesting such simulation(s) will receive a small prize(s) and will be demonstrated to the class. For a good demonstration, there should be interesting graphics. If you choose to do this, submit all your modified code with the command submit -N extra csc270h * I'll accept this kind of submission (which doesn't get you any marks) up to four days after the assignment deadline. Be sure to include a small README file that explains to the tutors what your modifications are. Do NOT submit this modified code for the regular part of the assignment. That part should only address the requirements in A.1, A.2, A.3, and B.1. CSC 270, Assignment 3 Cover Page: due Monday, November 25 at 6:10 in tutorial Surname _______________________________ Given Names _______________________ Student Number ________________________ CDF Login _________________________ TA's name _____________________________ Tutorial location _________________ I declare that this assignment is my own work and is done in accordance with the University of Toronto Code of Behavior on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism described in the course policies. I discussed this assignment with the following people: ______________________________________________________ ______________________________________________________ ______________________________________________________ Signature ____________________________________________ GRADING ------- Design Decisions and Algorithms ------------------------------- R.1 Event generation method / 5 R.2 Elevator algorithm method / 20 R.3 Statistics discussion / 10 Report readability / 5 Implementation Correctness and Efficiency ----------------------------------------- A.1 Random event generation / 5 A.2 Arrival and destination statistics / 5 A.3 Additional statistics / 5 B.1 Elevator algorithm / 15 Program style / 5 Total / 75