Synchronization using wait and signal methods

Question

The java implementation of semaphore using manual wait and signal method does not seem to be working. What can be wrong?

class Runner extends Thread implements Runnable{

    public static int s=1;
    private static int c;
    private String tname;

    Runner(){
        tname=this.getName();
    }
    public void wait(int s){
        while(s==0)
            System.out.println(tname+" Waiting; s = "+s);
        s--;
        System.out.println(tname+" Wait over; s = "+s);
    }

    public void signal(int s){
        s++;
        System.out.println(tname+" Signalled; s ="+s);
    }

    public void run(){
        wait(s);
        //critical section begin
        go();
        //critical section end
        signal(s);
    }

    public void go(){
        int f=10;
        while(f-->0){
            c++;
            System.out.println(tname+" : Counter = "+c);
        }
    }

}

public class wns{
    public static void main(String[] args){
        Runner t1=new Runner();
        Runner t2=new Runner();
        t1.start();
        t2.start();
    }
}

I ran it on Ubuntu 14.04 LTS and got an unexpected output. Output

Thread-1 Wait over; s = 0
Thread-0 Wait over; s = 0
Thread-0 : Counter = 2
Thread-0 : Counter = 3
Thread-0 : Counter = 4
Thread-0 : Counter = 5
Thread-0 : Counter = 6
Thread-0 : Counter = 7
Thread-0 : Counter = 8
Thread-0 : Counter = 9
Thread-0 : Counter = 10
Thread-0 : Counter = 11
Thread-0 Signalled; s =2
Thread-1 : Counter = 1
Thread-1 : Counter = 12
Thread-1 : Counter = 13
Thread-1 : Counter = 14
Thread-1 : Counter = 15
Thread-1 : Counter = 16
Thread-1 : Counter = 17
Thread-1 : Counter = 18
Thread-1 : Counter = 19
Thread-1 : Counter = 20
Thread-1 Signalled; s =2

The value of s comes to be 2 even when it's being incremented once. Likewise when decremented it becomes 0 again with no effect on synchronization at all. Can someone explain me what's exactly happening here?

Answer 1

Neither thread is waiting.

Both threads enter the wait() method at roughly the same time. Both threads check to see if s == 0 at roughly the same time. Both threads decide that, yes, s does equal 0, at roughly the same time. Both threads then decrement s at roughly the same time. Decrement is not an atomic operation and with both threads trying it at the exact same time it is possible that only one of the decrements actually takes hold. (thus s is 0 after both have called decrement). Both threads then call signal at the same time. Both threads call the increment operator at roughly the same time. This time both increments happen to take hold and thus s is now 2.

True semaphores and mutexes typically require special processor calls to do an atomic test-and-set operation. Java does not give you access to that operation (although its synchronized mechanism surely uses it under the hood) and thus, you cannot write your own semaphore class without using some kind of Java locking mechanism (e.g. synchronized).

EDIT: I was wrong about one thing. Java does allow access to a compareAndSet method with the atomic primitive wrappers (e.g. AtomicInteger) located in the java.util.concurrent.atomic package. You can use these to create your own semaphore without using the synchronized keyword.

EXAMPLE: Just to drive the point home, if s were an AtomicInteger you could replace your while loop with:

boolean waiting = true;
while(waiting) {
  int stableSValue = s.get();
  if(stableSValue == 0) {
    System.out.println("Waiting.  S was 0");
  } else {
    if(s.compareAndSet(stableSValue, stableSValue-1)) {
      System.out.println("Wait done.");
      waiting = false;
    } else {
      System.out.println("Optimistic locking failure.  Trying again.");
    }
  }
}