|CPSC 329||Software Development||Fall 2017|
In this lab, you will be creating a multithreaded simulation of elevators moving people around a high rise building. (The bulk of the functionality has been provided for you; your task will be to create and coordinate the threads.) Such a simulation would be useful for evaluating how many elevators are needed, whether there should be express elevators that only serve certain floors, and the effectiveness of different elevator scheduling strategies.
Successful completion of this lab means that you:
Work in pairs (and one group of three) to complete this lab. Only one person needs to carry out the steps in the lab but everyone in the group should make sure they understand what is going on. There is no limit on collaboration with others, but you need to make sure that you understand for yourself how (and why) to do things.
One handin per group.
To hand in the lab, create a handin tag as directed. Make sure the names of your group members are in the commit comment.
Create a project for this lab:
Create a new Eclipse project called lab8.
Import the files from /classes/cs329/lab8 into the project. Make sure they end up under the src directory in the project.
Create a readme text file in the project. (It should go at the top level of the project, not in the src directory.) Add the names of your group to the file.
Share your project into the repository. (Name the folder lab8.) Remember to choose the correct repository layout, and to check the structure in the repository after sharing.
Other than an incomplete main program, the provided code is a complete implementation of a simulation of elevators moving in a high rise office building with passengers getting on and off. Elevator, Building, Floor, and Person represent those elements. ElevatorSim handles elevator movement, which is the following:
repeat if no buttons have been pressed, the elevator waits until it is summoned once summoned, the doors are closed (if they were open) the elevator moves up or down one floor if the button has been pushed for that floor, the elevator opens its doors the elevator waits for a fixed time to allow passengers to get on and off
PersonSim handles person movement, which is the following:
while the person has another floor they want to go to repeat the person summons an elevator to the current floor until an elevator arrives that has room the person gets on the elevator the person pushes the button for their desired floor when the elevator arrives at the desired floor, the person gets off the elevator the person does their business on that floor
Main contains the main program and SimConstants contains definitions for some constants used in the simulation.
Look through the classes, paying attention to the comments for the public methods in each class (and the comments for the class itself).
Once you get the program running (the main program is incomplete in the provided code), the program's output lets you follow along with what is happening in the simulation. Each line of output looks like the following:
1508725713212 Thread-1: [elevator] elevator 1 opening doors on floor 0
The first number is the current system time in milliseconds. The exact values aren't important, but the difference between two times lets you see the passage of time during the simulation. The next thing on the line is the name of the thread executing the code that printed the message. The rest of the line provides information about what is happening.
In a real-life office building, each person and elevator moves independently and simultaneously. (For simplicity, we'll ignore the possibility of more sophisticated coordination of individual elevators.) This means that each person and elevator will be controlled by a separate thread in the simulation. Create and start those threads:
Locate the first two TODO comments in Main:
Add code where indicated to create and start a thread for each elevator. ElevatorSim defines the code for each elevator thread to run.
Add code where indicated to create and start a thread for each person. PersonSim defines the code for each person thread to run.
Once all of the people have reached their final destinations, the elevator threads should be shut down and the simulation should end:
As directed by the first TODO comment in ElevatorSim, add the necessary code to ElevatorSim to allow it to be shut down.
Locate the last two TODO comments in Main and implement the steps described: wait until all of the person threads have completed, shut down each of the elevator threads, and wait until all of the elevator threads have been completed. Note that you will need access to objects created in the elevator and person thread creation loops in order to carry out these tasks - create Lists as needed to hold those objects so you can access them here.
At this point you should be able to run the program and see threads start up and run. There may be exceptions thrown. You will probably not see any threads complete, as person threads run until the person has visited all of their destination floors - and visiting floors requires being able to get on and off elevators, which is very unlikely at this stage since the elevators aren't waiting for anyone to get on and off. You may want to reduce the number of elevators and people in the simulation for testing purposes.
Commit your changes to the repository.
The steps of the simulation should not run as fast as possible - an elevator takes time to move between floors, it sits with its doors open for a while after arriving at a floor, people spend some time on a floor before calling the elevator again, etc. This can be done by temporarily suspending the currently-executing thread; use Thread.sleep(ms) to accomplish the following:
Locate the last two TODO comments in ElevatorSim and add the delays specified (the time it takes an elevator to move between floors and the time the doors remain open). Use the named constants in SimConstants for the length of each delay.
Locate the first and last TODO comments in PersonSim and add the delays specified (the time between successive summons and the time to visit a floor). Use the named constants in SimConstants for the length of each delay.
At this point you should be able to run the program and see delays at the appropriate times. There may still be exceptions thrown, and you likely will still not see any threads actually complete.
Commit your changes to the repository.
The simulation is lacking coordination between the elevator and person threads - for example, people need to wait for an elevator to arrive and open its doors before they can get on and off. wait() and notify()/notifyAll() are used for this.
First, deal with people who are waiting for an elevator to arrive at a floor so they can get on. Since we think of summoning an elevator to a floor and the elevator arriving at a floor, the Floor object associated with the floor where they are waiting is convenient for this coordination.
Locate the TODO comment in the summon method of Building. (summon is called by the person thread when a person summons an elevator.) Add code as directed to wait on the Floor object associated with the floor the elevator is summoned to (floors_[floor]).
Locate the TODO comment in the arrive method of Building. (arrive is called by the elevator thread when an elevator arrives at a floor.) Add code as directed to notify all of the passengers waiting on the Floor object associated with the floor the elevator arrives on (floors_[floor]).
Next, deal with passengers who are waiting for an elevator to arrive at a floor so they can get off. Since this is different from those who want to get on the elevator, we need to use a different object for the coordination - the passengers are waiting, so each passenger's Person object can be used for the coordination.
Locate the second TODO comment in PersonSim and add code as directed to wait on the person (person_).
Locate the TODO comment in the arrive method of Elevator. (arrive is called by the elevator thread when an elevator arrives at a floor.) Add code as directed to notify the threads waiting on each of the elevator's passengers.
One final piece of coordination is that an elevator that doesn't have any destinations (i.e. no buttons have been pushed) should sit and wait rather than continuing to move. Since this involves an elevator, the Elevator object associated with that elevator will be used for the coordination.
Locate the second TODO comment in ElevatorSim and add code as directed to wait on the elevator (elevator_) until it is summoned.
Locate the TODO comment in the pushButton method of Elevator. (pushButton is called by the person thread when a person gets on an elevator and also when a person summons an elevator to a floor. In both cases the elevator now has a destination and should start moving again.) Add code as directed to notify threads waiting on the elevator (this).
At this point you should be able to run the program and see people getting on and off elevators and travelling to different floors. You should also be able to see person threads complete, so the program should eventually finish. (You may want to reduce the number of people if you haven't already in order to make the simulation easier to follow.) There may still be problems due to race conditions (such as exceptions being thrown, people getting on full elevators, etc) but these should be relatively rare and the program should mostly run.
Commit your changes to the repository.
At this point, the program will probably run correctly most of the time - but correctness demands that it run correctly all of the time and so race conditions need to be identified and addressed.
To quickly locate everywhere a variable or method is used, place the cursor within an occurrence of the variable's (or method's) name, then right-click and choose References->Project. All of the occurrences of that variable/method name in the current editor window will be highlighted (so you can quickly locate them if you scroll through the window) and the Search tab shows a summary of where the variable/method is used in the whole project - double-click on a method name to go to the references within that method.
Find the occurrences of capacity_ in Elevator - locate one such occurrence (such as the declaration), then use the method described above to locate the rest. Explore a couple of those other occurrences.
Shared variables are variables which are accessed by more than one thread. Two kinds of problems can arise when one thread changes the variable's value - caching of the variable's value can prevent other threads from seeing the new value, and race conditions can result in inconsistent or incorrect results.
Only instance variables need to be considered as variables declared inside a method are local to that method call. To determine if an instance variable is shared, locate everywhere it is used directly (if the instance variable is private, this should be limited to the body of the class it belongs to) and then trace calls to the methods containing those references until you determine which thread(s) are responsible. For example:
Consider capacity_ in Elevator. Its value is set in the constructor and used in hasRoom(). Tracing where the Elevator constructor is used reveals that it is called by Building's constructor, which is in turn called within main before any threads are created. At this point there is no need to look farther - the only time the variable's value is changed is a point when there is only one thread in the program, so there are no race conditions involving capacity_.
Consider open_ in Elevator. Its value is initialized in the constructor but it is also set in open() and close(), and the variable is used (without changing its value) in several other methods. Tracing where each of the methods that reference open_ are used and then where those methods are used (and so forth) reveals that close() is called from ElevatorSim and doorsOpen() is called by Building's getElevator(), which is in turn called by Building's summon(), which is called from PersonSim. Since ElevatorSim and PersonSim threads run simultaneously and both work with the same set of Elevator objects, as long as there is at least one elevator thread and at least one person thread started in main, open_ needs some protection.
Consider passengers_ in Elevator. This is similar to capacity_ - its value is set in the constructor (which is ultimately called by main before any threads are created) and used elsewhere. Note that at this point we are only considering changes to the value of passengers_ itself (i.e. assignment statements of the form passengers_ = ...), not the effect of methods invoked on passengers_. As with capacity_, the only time passengers_'s value is set is when there is only one thread in the program so there is no problem.
Determine which other instance variables (besides open_) are shared variables in need of protection. List all of them (including open_) along with a brief reason why they need protection in your readme file.
Shared objects are objects which are accessed by more than one thread. Shared objects can result from shared variables (there's only one reference to the object but several threads can access that reference) or from there being multiple references to the object. For example:
Consider passengers_ in Elevator - the HashSet object is created in the constructor and methods are called on it in enter, exit, and hasRoom. There is only ever the one reference to a particular HashSet object, but Elevator objects are shared between person threads so multiple threads may end up calling enter, exit, and hasRoom on the same Elevator and thus passengers_ object.
Consider building_ in PersonSim and ElevatorSim - these instance variables are initialized from a Building object passed to the constructor, and examination of main shows that the same Building object is passed to all of the constructors. There are multiple references (each instance variable is a separate reference) to the same object, and those references are used by multiple threads.
Keep in mind that multiple references to an object can also result from returning the value of an instance variable.
Are either of these situations problematic? It depends on whether mutator methods are called on the shared objects - many threads looking at the same value at once is not a problem, but if even one thread changes the state of a shared object, there is the potential for it to change the state in the middle of something another thread is doing.
Identify all of the instances of shared objects (including the two given above) and, for each, describe whether or not it is a potentially problematic situation in need of protection. Write up your answers in the readme file.
The final thing to identify is cases where another thread changes values that one thread is relying on.
One situation occurs when a single task involves multiple steps. For example:
Consider Elevator's idle method - determining if the elevator is idle involves checking all of the buttons. But what if another thread caused a button to be pushed after it had been checked in idle? Then idle() could return true even though a button has been pressed. This is a problem because an idle elevator is waiting for a button press; if the button press and notification comes before the elevator begins to idle, then it has missed what is expected to wake it up. But can this scenario actually happen? Yes, because idle is called by ElevatorSim and pushButton (which changes a button's value to true) is called by PersonSim, and elevator objects are shared between threads so that idle and pushButton could be called on the same elevator object at the same time. (Note that unpushButton also changes a button's value, but this isn't a problem in this case for two reasons: unpushButton changes the value to false, and it is only called from ElevatorSim. The latter means that unpushButton can't be called on the same elevator where a call to idle is in progress because elevator objects are not shared between elevator threads, and the former doesn't cause incorrect operation of idle.)
Another scenario occurs a state is expected to hold for multiple steps. For example:
Consider PersonSim - when an elevator is returned by summon, the elevator is on the floor with its doors open; a subsequent check makes sure there is room for the person. All of these conditions are expected to still be true when enter is called - but that elevator object is shared with an elevator thread and potentially other person threads, which could very well close the doors or get on (and fill up) the elevator in the meantime.
Identify all of the race conditions (including the two above) and briefly describe the problem. Write up your answers in the readme file.
Commit your changes to the repository.
Since open_ (in Elevator) is a primitive type (boolean) and the value is only changed through writes rather than updates (i.e. the new value doesn't depend on the previous value), the potential issue is one of cached values and so volatile can be used to solve the problem.
Add volatile to the declaration of open_ in Elevator.
In other situations, however, synchronized blocks and/or methods are needed to provide mutual exclusion. The coordination of mutual exclusion is achieved by synchronizing on particular objects, so the first step is to determine the different sets of mutual exclusion and identify appropriate objects for synchronization. For example, Elevator's idle method requires that no entry of buttons_ be set to true while it is running. This means that the body of idle and the line in pushButton that stores true in a slot of the buttons_ array need to synchronize on the same object. But what object to use? The buttons_ array itself is convenient - but keep in mind that it can't be used again for a different case of mutual exclusion.
Add synchronized blocks around the whole body of idle and the assignment statement in pushButton in Elevator. (Making the methods synchronized methods would mean using the elevator object itself as the lock, and we've already used it for thread coordination.)
Address the rest of the shared variable, shared object, and race conditions you identified. Use volatile where you can and synchronize elsewhere. Protect as needed, but don't overprotect!
At this point, the program should run properly. Remember, though, that while testing can give you confidence that you've addressed the race conditions (particularly if previously-observed problems are no longer occurring), only careful reasoning can prove that you have handled all of the race conditions.
Commit your changes to the repository.
Make sure you've committed everything to the repository.
Hand in by creating a "handin" tag. Make sure the names of your group members are in the commit comment.