Semaphores

Semaphore is:

In computer science, a semaphore is a protected variable or abstract data type which constitutes a classic method of controlling access by several processes to a common resource in a parallel programming environment. A semaphore generally takes one of two forms: binary and counting. A binary semaphore is a simple "true/false" (locked/unlocked) flag that controls access to a single resource. A counting semaphore is a counter for a set of available resources. Either semaphore type may be employed to prevent a race condition.

en.wikipedia.org

Just to refresh some of my knowledge in concurrency let's see how to implement it in java.
We'll assume that we don't have java.util.concurrent package, and try to use wait(), notify() primitives. After some facing some errors and pitfalls, brainstorming with my colleagues I've got the following solution:

public class Semaphore {

    private int i;

    public Semaphore(int max) {
        if (max < 1)
            throw new IllegalArgumentException("should be natural number");
        this.i = max;
    }

    public synchronized void acquire() throws InterruptedException{
        while (i == 0){
            wait();
        }
        i--;
    }

    public synchronized void release() {
        i++;
        notify();
    }
}

We use counter to track how much treads acquire resource. Current solution is very basic has some limitations:

• doesn't deal with tread interruption, which can cause threads stuck, in case where all threads are waiting and last one is interrupted
  
• doesn't handle situation, when some tread will call redundant release() method, when no threads acquire semaphore
• doesn't guarantee order in which tread will be released. It could be implements using queue data structure, like bounded buffer.
• intensively uses synchronization
  

The most perfect 'educational' solution which I found is Doug's Lee implementation.

Constructing semaphore with with counter 1, we'll got mutex, which have effect similar to lock in java, except reentrancy and allows to acquire and release it from different treads.

Semaphore mutex = new Semaphore(1);

If you decide to dive into Semaphores, it might be useful to read papers of its founder, Dijkstra (not for the beginners):
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html

Java 1.5 Semaphore implementation, which doesn't use wait/notify and synchronized:
java.util.concurrent.Semaphore.java



Book about semaphores and synchronization problems:
http://greenteapress.com/semaphores
Best book about concurrency in java: "Java Concurency in practice"

An article about semaphore implementation:
http://www.javaworld.com/javaworld/javaqa/1999-11/02-qa-semaphore.html