A semaphore is a synchronization mechanism that provides functionality built on the semantics of wait and notify. Every object in Java is equipped with wait and notify methods.
Executing wait in a synchronized context tells the executing thread to go to sleep and wait to be woken up by a notification request. Executing notify in a synchronized context tells the scheduler to wake any other thread waiting on the monitor. notifyAll in Java does the same, but wakes up all waiting threads—whoever gets to the monitor first gets to execute, the rest must go back to sleep. notifyAll is generally safer to use since it avoids deadlocks better. Naturally, it comes with some additional overhead.
See also Deadlock and Monitor.