Semaphores in Java

What exactly is a semaphore ?
To use the wiki definition:

In computer science, particularly in operating systems, a semaphore is a variable 
or abstract data type that is used for controlling access, by multiple processes, 
to a common resource in a parallel programming or a multi-user environment.
A useful way to think of a semaphore is as a record of how many units of a particular 
resource are available, coupled with operations to safely (i.e., without race 
conditions) adjust that record as units are required or become free, and, if necessary, 
wait until a unit of the resource becomes available.
Semaphores are a useful tool in the prevention of race conditions; however, their 
use is by no means a guarantee that a program is free from these problems. Semaphores 
which allow an arbitrary resource count are called counting semaphores, while semaphores 
which are restricted to the values 0 and 1(or locked/unlocked, unavailable/available) 
are called binary semaphores. 

Java 5 provides us with a Counting Semaphore, that was developed by Doug Lee. I decided to develop a simple example class based on the java docs for the same:

class CarRental {
  private static final int TOTAL_CARS = 3;

  private Queue<String> cars = new LinkedList<String>();
  {
    for (int i = 1; i <= TOTAL_CARS; i++) {
      cars.offer("Car No : " + i);
    }
  }
  private final Semaphore availableCars = new Semaphore(TOTAL_CARS, true);
  
  // rent car method
 
  // return rented car method
}

The above car rental class has a collection of cars that it rents out to people. It uses semaphores here rather than wait notify to manage the availability of cars. The rent method is as below:

public String rentCar(String user) throws InterruptedException {
    System.out.println("Car has been requested by " + user + " ...");
    long time = System.currentTimeMillis();
    availableCars.acquire(); // non synchronized but blocking    
    long blockTime = System.currentTimeMillis() - time;
    System.out.println("A car is ready for use - [ " + blockTime + " ms ] ," + 
      " Retrieve from pool for " + user + " ...");
    String car = null;
    synchronized (cars) {
      car = cars.poll(); // non blocking
    }
    System.out.println("Car retrieved is " + car + " for user " + user);
    return car;
  }

As seen here to acquire a car, we first acquire a permit from our semaphore. The acquire method used here is a non synchronized method that will only return once we have a permit available. Kind of like a guarded block. So this code would simply block infinitely until a car is available. To prevent the same we have

  availableCars.acquireUninterruptibly(); // non synchronized, still blocking 
                                          // but does not throw InterruptedException

The documentation for the method is:

If no permit is available then the current thread becomes disabled for thread scheduling purposes 
and lies dormant until some other thread invokes the release method for this semaphore and 
the current thread is next to be assigned a permit.
If the current thread is interrupted while waiting for a permit then it will continue to wait, 
but the time at which the thread is assigned a permit may change compared to the time it would 
have received the permit had no interruption occurred. When the thread does return from this 
method its interrupt status will be set.

 As explained here we get a wait kind of behavior for our thread. This prevents wastage of CPU Time. To proceed with the example here is the returnCar method:

public void returnCar(String car, String user) {
    System.out.println("Car for return is " + car + " by user " + user + " ...");
    synchronized (cars) {
      cars.offer(car);
    }
    System.out.println("car [ " + car + " ] added to pool from user " + user);
    availableCars.release(); // non synchronized non blocking

  }

As seen above, we first return the car to the pool. Now we release our permit back to the semaphore. This is like sending a notify to all threads that a car is available in the pool. I decided to create Users to fetch cars from the pool:

class User implements Runnable {
  private CarRental carRental;
  private long carUseTime;

  public User(CarRental carRental, long carUseTime) {
    this.carRental = carRental;
    this.carUseTime = carUseTime;
  }

  @Override
  public void run() {
    String user = "[ " + Thread.currentThread().getName() + "]";
    String car = carRental.rentCar(user);
    // Using car for carUseTime milliseconds
    try {
      Thread.sleep(carUseTime);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    // Time to return car
    carRental.returnCar(car, user);
  }

}

The users as seen get a car from the rental, use it for a certain time and return it once done. Accordingly the main method is as below:

public static void main(String[] args) throws InterruptedException {
    CarRental carRental = new CarRental();
    new Thread(new User(carRental, 100), "Fred").start();
    new Thread(new User(carRental, 100), "Jane").start();
    new Thread(new User(carRental, 100), "Gina").start();
    new Thread(new User(carRental, 100), "Roger").start();
  }

The output of the code is :

Car has been requested by [ Fred] ...
A car is ready for use - [ 0 ms ] , Retrieve from pool for [ Fred] ...
Car retrieved is Car No : 1 for user [ Fred]
Car has been requested by [ Roger] ...
A car is ready for use - [ 0 ms ] , Retrieve from pool for [ Roger] ...
Car has been requested by [ Gina] ...
Car retrieved is Car No : 2 for user [ Roger]
A car is ready for use - [ 0 ms ] , Retrieve from pool for [ Gina] ...
Car retrieved is Car No : 3 for user [ Gina]
Car has been requested by [ Jane] ...
Car for return is Car No : 1 by user [ Fred] ...
car [ Car No : 1 ] added to pool from user [ Fred]
Car for return is Car No : 3 by user [ Gina] ...
car [ Car No : 3 ] added to pool from user [ Gina]
A car is ready for use - [ 101 ms ] , Retrieve from pool for [ Jane] ...
Car retrieved is Car No : 1 for user [ Jane]
Car for return is Car No : 2 by user [ Roger] ...
car [ Car No : 2 ] added to pool from user [ Roger]
Car for return is Car No : 1 by user [ Jane] ...
car [ Car No : 1 ] added to pool from user [ Jane]

As seen above the first three users came in and all got their cars immediately. Unfortunately when Jane arrived no cars where there, hence the wait (101 ms) to receive a car.
A question that came to mind when I started is "Why isn't there a need to synchronize on the semaphore methods ?". The ans : "For what ? "
A more appropriate answer is found in the java doc:

Note that no synchronization lock is held when acquire() is called 
as that would prevent an item from being returned to the pool. The 
Semaphore class has been built as a thread safe class which has code 
that works similar to the happens before relationship that we get 
with the synchronized keyword in java. Actions prior to "releasing" 
synchronizer methods such as Semaphore.release happen-before actions 
subsequent to a successful "acquiring" method such as Semaphore.acquire 
on the same synchronizer object in another thread.

Another question is "Now that we are using semaphores do we still need to synchronize our Car Pool ? "  Yes.
Our semaphores here are not the resource. Instead they are a limiter or a tracker telling code when it is safe to proceed towards a resource. Here our user threads will acquire the semaphore for the duration of their car use. This prevents too many users trying to ask for a car at once. The CarRental object must also use synchronized block while offering or removing cars so as to ensure that if two users ask for a car together they do not receive the same car. Scenarios such as two users receiving the same car to two different threads because they called the method simultaneously.