Comp314: Homework 2

You have seen how Java provides a variety of different synchronization primitives, including the primitive methods on Java.lang.Object like wait and notifyAll and the synchronized keyword. There are also much fancier features in the java.util.concurrent package. For this assignment, you will only need the primitive old-school Java primitives.

Your assignment is to implement a traffic light synchronizer. A simple traffic light allows cars going north and south at the same time, and you can also have cars going east and west at the same time, but you had better not mix any other combination, or you'll have some unpleasant collisions.

You will implement an interface that looks something like this:

class TrafficLight {
    public void setSwitchingSpeed(int millis);
    public void enterEast();
    public void enterWest();
    public void enterNorth();
    public void enterSouth();
    public void exit();
}

The idea is similar to a traffic light on a single-lane road intersection. The light is either green for north/south traffic and red for east/west traffic, or vice versa. We have no yellow light and no turns. When we're allowing north/south traffic, then threads in the north/south queues will be run in the order in which they arrived. One southbound car cannot enter the intersection until the previous southbound car has finished. Then, every so many milliseconds, as configured by setSwitchingSpeed, the traffic light will switch and allow traffic to go the other way.

Individual threads will each call one of the enter methods, which will then block. When it returns, the thread is now "in" the intersection and can do whatever it wants. You should code your threads to have various delays, using Thread.sleep() of tens of milliseconds. When the thread is ready to leave the intersection, it will call exit. Threads should print something useful when both entering and exiting the interaction, so you can see from the trace that the traffic light was working properly. Example:

light.enterEast();
System.out.println("Thread " + myThreadNumber + ": I'm going east!");
Thread.sleep(100);
system.out.println(Thread " + myThreadNumber + ": "I'm out!");
light.exit();

You'll want those delays to be deterministic, yet not all the same, which will help you with your testing.

Much like a genuine traffic light, you also want to be able to keep traffic flowing in one directly when there's nobody waiting to go the other way. That means you need to track whether you've passed the time to switch directions and whether or not you've got traffic waiting. If east/west traffic shows up while you've got north/south traffic going, then you need to wait for all the north/south traffic to finish up before you start letting east/west traffic go through.

You should have JUnit test cases that demonstrate and test for the following conditions:

  1. When one car is going eastbound, there is never a second car going eastbound at the same time (and variants for other compass directions).
  2. When one car is going eastbound, there is never any car going north or south (and variants for other compass directions).
  3. When there are cars in any of the four queues, there will always be at least one car going through the intersection.
  4. When there are cars in all four queues, everybody will eventually get through the intersection.
  5. When there are cars in all four queues, the direction of the light will change after the specified time period.

You will implement this by yourself. No partners. No pair programming. Furthermore, as we discussed at the beginning, you will implement this entirely without use of the java.util.concurrent classes, particularly something like java.util.concurrent.ExecutorService. Most likely, you'll have some inner methods that are synchronized on a lock object of some kind. When somebody exits, they acquire the lock, update the state, and notify everybody else that the state changed. Then, whoever is at the head of the queue gets to go next while the rest go back to sleep. You'll also probably have a separate thread that handles the direction switching. Since calls to exit could ostensibly come from multiple different threads, you'll probably find yourself calling Thread.currentThread to keep track of these things so you know, from who left, who gets to go next.

Clarifications

One student writes:

As I was working through h2, there were just a few things that were a little unclear to me from the instructions:

With regard to when to toggle the light: If, for example, the light is in north-south mode, and there are no cars in the north,south,east or west queues (i..e. there are no cars at the intersection for any direction) by the time a toggle should occur, should the light toggle and continue switching, or should the light remain in the current positions (ex. north-south) and stay in that position until cars for east or west arrive? example: The intersection is empty from the beginning and no cars ever arrive; should the light ever toggle?

In the case when there is no competition for the traffic light, i.e., there are no cars present at all, then it doesn't particular matter what the state of the light is. When a new car arrives, the light should immediately change to allow that first car through. This will, of course, establish the state of the light for subsequent cars and will start the timer running.

Because some threads *could* be holding the intersection slot, for a given direction, while the threads execute for a long time (i.e. longer than the toggle frequency time) possibly, what if the time duration that the threads hold the slot is longer than the toggle frequency? If, for example, threads for north-south were executing (and the north or south slots are locked), the light toggles to east-west (north/south threads already in intersection still executing), the light toggles again to north-south and the north/south thread finishes, leaves the intersection and a new north/south thread starts before the next toggle, this could mean that threads for east-west never execute possibly. Is this the desired way that the light should work? I realize this may mean that the time interval for toggling was chosen poorly, and that this situation could be avoided by adjusting the toggle frequency, but I want to know if this is the desired behavior, and if not, then what is the desired behavior?

The desired behavior is that the light doesn't change state when somebody is in the intersection. However, if the light state should have changed, then nobody else should be allowed in until the intersection is clear. Then you can toggle the state and allow traffic in the other direction. You would then start the timer after you toggle the light.

Do we have to follow the exact template for TrafficLight given in the h2 instructions?

I'm not going to be particularly particular on this point, but if your API is in any way different, you'd better have a good reason. Among other things, I specifically do not want the enter methods to take Runnable instances or anything else that smells like you've explicitly segregated out the computation that's supposed to happen when you're inside the intersection. The computation that occurs before the intersection, during the intersection, and after the intersection should all be within the same method body.