CPSC 329 Software Development Fall 2017

CPSC 329 Lab 8: Threads

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.

Objectives

Successful completion of this lab means that you:

Collaboration

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.

Due Date and Deliverables

due Tue Oct 31 at the start of class

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.


Setup

Create a project for this lab:

Provided Code

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.


Completing the Simulation

Thread Creation and Termination

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:

Once all of the people have reached their final destinations, the elevator threads should be shut down and the simulation should end:

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.

Thread.sleep(ms)

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:

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.

Thread Coordination

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.

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.

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.

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.

Race Conditions

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.

Eclipse Tips - Locating References

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.

Shared Variables

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:

Shared Objects

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:

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.

Identifying Race Conditions

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:

Another scenario occurs a state is expected to hold for multiple steps. For example:

Addressing Race Conditions

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.

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.

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.


Handin


Valid HTML 4.01!