Semaphore how to block and unblock

Question

For an assignment I have to create a counting semaphore in Java. I have so far created this bare bones class

public class Semaphore {
    int value;

    public Semaphore(int value) {
        this.value = value;
    }

    public static void wait(Semaphore s) {
        s.value--;
        if (s.value < 0) {
            // block
        }
    }

    public static void signal(Semaphore s) {
        s.value++;
        if (s.value <= 0) {
            // unblock one process that is blocked on semaphore
        }

    }   
}

Now what I'm confused is how exactly do I block on wait() and conversely how do I unblock one thread on signal()? I was reading that there is a blocked queue but where would I keep reference to that queue?

Answer 1

In your waiting method (which should be called something else than wait), you need to check that your value is zero, if it is zero, you just keep waiting. This is achieved in the following:

public synchronized void P() throws InterruptedException 
{
    while (value == 0) 
    {
        wait();
    }
    value--;
}

Your method doesn't take a Semaphore object. You just use the value field in your Semaphore class.

The method checks that while the value is 0, it waits for the value to be changed. So the thread from where you call the method will have to wait. Otherwise if the value is not zero, the thread can enter its critical section and the value is decremented until it reaches zero again, which is when the thread blocks.

Your signal method needs to increment the value, and notify the thread who is waiting that the value has changed to see if it can enter its critical section. The signal method is implemented in the following:

public synchronized void V() 
{
    value++;
    notify();
}

The naming I used for the methods comes from the the names Dijkstra used for semaphores (Just in case you're confused by them).

You shouldn't call the blocking method wait as it will get confused with the wait method from Object.