Part 0, 0 points: Create a new Java class, MySemaphore.java. Add a header (Javadoc) comment to the top of your file that includes the names of everyone in your group. E.g.:

/**
 * Implements a multi-token semaphore.
 * 
 * @author: Ella Borgin, Jim Stock
 */

Part 1, 0 points: Add the class header to your file:

public class MySemaphore {
    ... the code in the class will go here...
}

Part 2, 0 points: Add an integer field to your semaphore. I named mine numTokens:

    //the number of tokens available
    private int numTokens;

Part 3, 0 points: Add a constructor that takes an integer representing the number of tokens available when it's created. Users of your code should be able to create a semaphore like this:

MySemaphore s = new MySemaphore(2);

Part 4, 0 points: I'm not going to grade it, but I highly recommend you make a toString method, as you should when making a new Java class.

Part 5, 0 points: You will also need a getNumTokens() method that returns the number of available tokens in the semaphore.

Part 6, 0 points: Now it's time to write the two main methods: p() and v(). I'll give you a bad version of p() which you can update later. Note: p is short for the Dutch word proberen. This method blocks until the number of tokens the semaphore has becomes positive. (If there are already positive tokens, then it won't block at all.) When it's done blocking, it removes a token and then is done. Here's a very bad way to implement this that unnecessarily waits and is not thread safe:

public void p() {
    while(this.numTokens <= 0) {
        try {
            Thread.sleep(2000);
        } catch (Exception e) {
            throw new RuntimeException("sleeping failed!");
        }
    }
    this.numTokens --; //removes one token
}

Part 7, 0 points: Add a new method, v(), which is short for the Dutch word verhogen. This method represents the return of a token to the semaphore, so it should increment the field. It is okay for the number of tokens to go above the original number of tokens. That sounds simple, but it still needs to be thread-safe. Here is a terrible version of it that you can start with:

public void v() {
    this.numTokens++;
}

Part 8, 0 points: You should now be able to test your code with the SemaphoreTester.java code I wrote. I will use this code to test your submission, but it isn't enough to check that your code is actually thread-safe! I have set up assert statements in there, so if you want to make sure you're passing the tests, run it with the -ea flag, like this:

java -ea SemaphoreTester

java -ea SemaphoreTester 1000

Part 9, 0 points: Here's one possible sequence of steps that could cause a race condition. There is a semaphore with 1 token and two threads are simultaneously calling the p method.

1. The first thread reaches the condition of the while and evaluates it to be false.
2. The second thread reaches the condition of the while and also evaluates it to be false.
3. The second thread performs the subtraction, changing the number of tokens to 0.
4. The first thread performs the subtraction, changing the number of tokens to -1, an illegal value for the Semaphore.

Part 10, 10 points: You need to modify your code so that it is thread-safe; i.e. no race conditions can occur. In order to do this, you can use two Java synchronization tools:

• The synchronized keyword, which enforces that only one thread can be executing that method at a time.
• The wait(), notify(), and notifyAll() methods that are built in to every Java object. Check out the linked docs for information on what they do and how to use them.

Part 11, 10 points: In addition to making sure your code is correct, you also want to improve performance (speed). Make sure that there are no calls to Thread.sleep, nor System.out.println in your Semaphore class.

Part 12, 20 points: Ensure that your semaphore doesn't block on calls to p when there are tokens available. This part is tested in my SemaphoreTester code. If you pass those tests, you'll get credit for this.

Part 13, 20 points: Make sure that your semaphore blocks in p when there are no free tokens. This part is tested in the testing file. If you pass those tests, you'll get credit for this.

Part 14, 20 points: There is no efficient test that will always be able to find all the race conditions. (Detecting deadlocks is PSPACE-hard.) Nevertheless, I wrote a stress test to try to kill your Semaphore in my testing code. If your code passes those final stress tests (with whatever parameters I choose) then you will earn the points for this.

Part 15, 20 points: No possible race conditions or deadlocks! I am going to look at your code and see if I can find a potential race condition or deadlock. If I find one or if your code doesn't pass the previous part, then you won't earn points for this part. I am willing to look at your code beforehand and see if I can find problems, but:

• Your code should be well-written for readability. Follow regular conventions (e.g. proper indentation and good variable names).
• It's generally better to ask me in person so I can explain it by pointing and gesturing at the code (and writing on the whiteboard), and
• I expect that shortly before the project is due, many people will come and start asking me to check their code. Doing this check can take a non-trivial amount of time. Start early on this! Teams usually don't get these points because they didn't leave enough time for sufficient rounds of trial-and-error with feedback from me. It is on you to come early and often enough to get this working, not the other way around!

Part 16, 0 points: If your code runs fast enough when I test it, you'll earn up to 5 bonus points. If you submit your code, you can ask me to run it to see how fast it runs. I'm definitely willing to chat about potential ways to speed up your code!

Submitting your Project:

$ javac *.java
$ java -ea SemaphoreTester 15000