Writing and testing multithreaded programs has always been difficult. This is the case because often the concurrency mechanism is coupled with program logic. One way to reduce this coupling is to abstract away as much of the concurrency concerns as possible. In this project you will implement a concurrency abstraction. We have provided you with a detailed specification with most of the details for this project. Here, you will find a general overview and we will stress some important issues.

Overview

The concurrency abstraction you will be required to write is a compound lock. Such an abstraction can be useful for a wide array of applications. For example, you could use such an abstraction to implement last Spring's Project 4. Note that it is not at all necessary to read that previous project description to understand this one.

Briefly, a compound lock is a lock which consists of zero or more component locks. Users may lock and unlock (acquire and release) individual component locks. Users may also lock and unlock the global lock (or the "whole" compound lock, if you will.) While the global lock is held, no component locks may be acquired until the global lock is released. While even a single component lock is held, the global lock may not be acquired.

Global lock acquisition requests have priority over component lock acquisition requests. That is, component lock acquisition requests should only complete if the global lock is released and there are no pending global lock acquisition requests. For example, say two threads A and B hold component locks. If a third thread C tries to acquire a component lock at this point, it will succeed. However, if thread D were to attempt to acquire the global lock first, then C's attempt would fail; it would need to wait until the global lock has been acquired and released by D.

Implementation

You will implement the CompoundLock interface in the source file CompoundLockImpl.java. The CompoundLockImpl class must have a zero-argument constructor.

As was explained in class, you will lose points for improper synchronization, busy-waiting, and over-synchronization.

To facilitate testing, there are a number of restrictions on how you many implement your project. You should use Java intrinsic locks and not the new Java 1.5 java.util.concurrent.locks package (indeed, importing the Lock interface under java.util.concurrent.locks would conflict with the Lock interface we have provided). In addition, do not use the standard Java Object.wait() method in your implementation. Instead, you must use the static Util.wait() method we have provided. In short, if you would have done o.wait(), you should instead do Util.wait(o). Otherwise, we will not be able to test your submission and you will lost points. You may, however, use the standard Java notify/notifyAll methods.

Testing

We have provided you with a framework (in threadController.jar) for writing multithreaded test cases. You can see an example of using this framework in PublicTests. You should use this framework when writing your StudentTests. One way to use this framework is outlined here.

You will need to import the following:

    import cmsc433.threadController.MultithreadedTestCase;
    import cmsc433.threadController.TestFramework;

    private class AnInnerClass extends MultithreadedTestCase {

        public AnInnerClass(...) {
            ...
        }

        public void initialize() {
            ...
        }

        public void thread0() {
            ...
        }

        public void thread1() {
            ...
        }

        public void finish() {
            ...
        }

    }

Finally, you will write your tests inside StudentTests, which will look something like:

    public void testATest() throws Throwable {
        ...
        TestFramework.runOnce(new AnInnerClass(...));
    }

For this reason, you will notice that many of the public tests attempt to reduce the possible thread schedulings, for example by implementing a barrier using Java 1.5's CountDownLatch class, and using the information gathered by Util.wait. For example, here is an except from the TwoLocksProvideMutualExclusion public test:

    volatile boolean v = false;
    Thread thread1;
    CountDownLatch latch1;

    public void initialize() {
      latch1 = new CountDownLatch(2);
    }

    public void thread0() {
      lock0.lock();
      barrier(latch1);
      Util.waitForThreadToWait(thread1);
      assertFalse(v);
      lock0.unlock();
    }

    public void thread1() {
      thread1 = Thread.currentThread();
      barrier(latch1);
      lock1.lock();
      v = true;
      lock1.unlock();
    }

Hints

Writing multithreaded programs is hard. Debugging becomes much harder because the behavior of the program can change from execution to execution. Finding bugs in multithreaded programs is, accordingly, an active area for research, and a number of useful tools have been developed. We strongly recommend that you use two of these tools to test your project before submitting it:

• FindBugs - A static bug finding tool
• checkSync - A dynamic race detection tool

Both of these tools can help you identify potential bugs in your project. By their nature they are both somewhat conservative. Things that they identify as problems may actually be OK. But, in general, if there is something that these tools don't like in your code, it is likely to be at least a poor design choice.

Of course, you'll get FindBugs warnings through SubmitServer.