Correct Semaphore Implementation in Java

[Frank Gerlach]

There seem to be quite a number of not very clean and simple
implementations
of java Semaphores in the internet. The following example is extremely
simple (the Java 1.5 implementation is overfeatured IMHO) and correct:

/** Semaphore class for managing limited resources (such as database
* connections)
* Author: Frank Gerlach ([email protected])
* Copyright: None. Use in any way you want.
* located at: http://www.geocities.com/gerlachfrank/Semaphore.java
*/
public class Semaphore{
int count;
/** Create the semaphore
* @param initialcount number of resource items to manage
*/
public Semaphore(int initialcount){
count=initialcount;
}

/** Acquire one resource item
*/
public void P(){
synchronized(this){
if(count==0){
try{
wait();
}catch(InterruptedException ie){
//this should never happen
System.err.println("caught InterruptedException in
wait()");
}
}
count--;
}
}

/** Release one resource item, thereby waking up a sleeping thread
* if free resource count was zero.
*/
public void V(){
synchronized(this){
count++;
if(count==1)notify();
}
}
}

 

[Andrea Desole]

I wouldn't say it's correct. There are two things that don't convince me:
1) a thread shouldn't be able to call V without calling P. You can't
release a resource if you don't get it
2) notify is not deterministic. It would be better to have a FIFO queue,
or there is a chance, altough small, that a thread will wait forever
I also know that some JVMs don't work as they should, and in some cases
a waiting thread can wake up without notify being called.
There are probably a lot of resources on the web about this

 

[Matt Humphrey]

There seem to be quite a number of not very clean and simple
implementations
of java Semaphores in the internet. The following example is extremely
simple (the Java 1.5 implementation is overfeatured IMHO) and correct:

/** Semaphore class for managing limited resources (such as database
* connections)
* Author: Frank Gerlach ([email protected])
* Copyright: None. Use in any way you want.
* located at: http://www.geocities.com/gerlachfrank/Semaphore.java
*/
public class Semaphore{
int count;
/** Create the semaphore
* @param initialcount number of resource items to manage
*/
public Semaphore(int initialcount){
count=initialcount;
}

/** Acquire one resource item
*/
public void P(){
synchronized(this){
if(count==0){
try{
wait();
}catch(InterruptedException ie){
//this should never happen
System.err.println("caught InterruptedException in
wait()");
}

I havn't worked with this for a while, but shouldn't it be
while (count == 0) {

because otherwise the arrival of a spurrious notify will cause the semaphore
to be granted when it is not yet ready. Alternatively (or in addition),
shouldn't the monitor be a private instance object and not "this" for
exactly the same reason?

Also, in many of the real applications I have worked on, Interrupted
Exceptions are not "should never happen" but a real fact of life and need
real handling. Shouldn't your design include something more meaningful,
such as either directly throwing InterruptedException so the application can
determine the appropriate course of action or something that lets them be
ignored or retried?

}
count--;
}
}

/** Release one resource item, thereby waking up a sleeping thread
* if free resource count was zero.
*/
public void V(){
synchronized(this){
count++;
if(count==1)notify();
}
}
}

Also, what about the order in which the signals are granted? This version
simply relies on notify to choose the order, which may not be in the order
they were requested. And, of course, there is the whole time-out issue--I
don't want a broken subprocess to break my app as a whole.

IMHO, I think the reason there are so many versions of Semaphore is that the
abstract concept (no matter how well implemented) is not sufficient and
people need different behaviors for different applications.

Cheers,
Matt Humphrey (e-mail address removed) http://www.iviz.com/

 

[Frank Gerlach]

I wouldn't say it's correct. There are two things that don't convince me:
1) a thread shouldn't be able to call V without calling P. You can't
release a resource if you don't get it

That is right. There is nothing in my implementation preventing abuse.
There should always be something like a P() .. V() brace in the using code.

2) notify is not deterministic. It would be better to have a FIFO queue,
or there is a chance, altough small, that a thread will wait forever Remote possibility
I also know that some JVMs don't work as they should, and in some cases
a waiting thread can wake up without notify being called.

Hmm. Can you elaborate on this ?

 

[Frank Gerlach]

I havn't worked with this for a while, but shouldn't it be
while (count == 0) {

because otherwise the arrival of a spurrious notify will cause the semaphore
to be granted when it is not yet ready. Alternatively (or in addition),
shouldn't the monitor be a private instance object and not "this" for
exactly the same reason?

The while() loop is NOT necessary. Actually, the notify() can only reach
the wait()ing thread when it already sleeps. This is assured by
synchronized(this)
,which acquires the monitor. Any notify()ing thread must first acquire the
monitor, which is not possible while the thread still runs in P().

Also, in many of the real applications I have worked on, Interrupted
Exceptions are not "should never happen" but a real fact of life and need
real handling. Shouldn't your design include something more meaningful,
such as either directly throwing InterruptedException so the application can
determine the appropriate course of action or something that lets them be
ignored or retried?

Hmm. Can you explain the exact circumstances of InterruptedException being
thrown ?

Also, what about the order in which the signals are granted? This version
simply relies on notify to choose the order, which may not be in the order
they were requested.

I do not exactly understand what you are referring to - is it that notify()
doesn't guarantee the order of sleeping threads woken up ?

And, of course, there is the whole time-out issue--I
don't want a broken subprocess to break my app as a whole.

You could also state that you do not want a segmentation violation to stop
a programm's execution. Yet all modern OSs terminate a programm which has
a pointer problem.

IMHO, I think the reason there are so many versions of Semaphore is that the
abstract concept (no matter how well implemented) is not sufficient and
people need different behaviors for different applications.

Maybe there is some truth in this, but for the plain-vanilla Semaphore there
are a number of implementation on the net (for example with notifyAll() or
while(count==0) ) which are at least too complex for the purpose.

 

[Frank Gerlach]

Also, in many of the real applications I have worked on, Interrupted

Exceptions are not "should never happen" but a real fact of life and need
real handling. Shouldn't your design include something more meaningful,
such as either directly throwing InterruptedException so the application can
determine the appropriate course of action or something that lets them be
ignored or retried?

I googled InterruptedException and cam up with this page:
http://www.milk.com/java-rants/rant01-interrupted.html
It basically states that the exception ONLY occurs when someone in the same
VM calls Thread.interrupt() on the thread in question. This page also
discusses four options of how to handle the exception. One is to consume it
(like I do, with an error message that points to the error of using
Thread.interrupt()), another is to rethrow it. I concede that throwing
an exception might be a viable option IF you really need to call Thread.interrupt().

 

[xarax]

"Matt Humphrey" <[email protected]> wrote in message
The while() loop is NOT necessary. Actually, the notify() can only reach
the wait()ing thread when it already sleeps. This is assured by
synchronized(this)
,which acquires the monitor. Any notify()ing thread must first acquire the
monitor, which is not possible while the thread still runs in P().

/snip/

The call to wait() releases the monitor. Think about what
could happen when multiple threads are calling P(). The
multiple threads will call wait(). Another thread will
subsequently call notify(), which will randomly awaken
one of the threads, not necessarily the first thread that
chronologically entered P(). Upon awakening, the thread
will then re-acquire the monitor.

The "while(count==0)" is required.

 

[Andrea Desole]

That is right. There is nothing in my implementation preventing abuse.
There should always be something like a P() .. V() brace in the using code.



Remote possibility

yes. I can't say how likely it is, but I also think it doesn't happen
very often. Still, it can happen.

Hmm. Can you elaborate on this ?

not really. It's something that someone showed me on a book (for more
information look on "Effective Java", by Joshua Bloch, item 50). It just
says that in many JVM implementations, apparently because of something
related to the Posix standard, this problem can occur. They are called
spurious wakeups. I think this is what Matt Humphrey in this thread
calls spurious notify. In fact, both Matt and the book are suggesting to
use a loop.

 

[xarax]

yes. I can't say how likely it is, but I also think it doesn't happen
very often. Still, it can happen.

not really. It's something that someone showed me on a book (for more
information look on "Effective Java", by Joshua Bloch, item 50). It just
says that in many JVM implementations, apparently because of something
related to the Posix standard, this problem can occur. They are called
spurious wakeups. I think this is what Matt Humphrey in this thread
calls spurious notify. In fact, both Matt and the book are suggesting to
use a loop.

The problem is not related to spurious wake-ups. The code
in the procure method P() was broken, because it only used
"if(count==0)" rather than "while(count==0)". The code poster
asserted a fallacy about the efficacy of the implementation,
that it was impossible to return from the "wait()" without
being immediately able to take ownership of the semaphore.

The while loop is required not due to spurious wake-ups,
but rather due to the fact that "wait()" releases the monitor
and then tries to re-acquire the monitor before returning to
the code that called wait(). A timing issue arises when two
or more threads concurrently attempting P() which will cause
the broken code to proceed with two threads holding the
semaphore. The while loop fixes that bug.

--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS for FREE!

 

[Andrea Desole]

The problem is not related to spurious wake-ups. The code
in the procure method P() was broken, because it only used
"if(count==0)" rather than "while(count==0)". The code poster
asserted a fallacy about the efficacy of the implementation,
that it was impossible to return from the "wait()" without
being immediately able to take ownership of the semaphore.

The while loop is required not due to spurious wake-ups,
but rather due to the fact that "wait()" releases the monitor
and then tries to re-acquire the monitor before returning to
the code that called wait(). A timing issue arises when two
or more threads concurrently attempting P() which will cause
the broken code to proceed with two threads holding the
semaphore. The while loop fixes that bug.

the code is synchronized, I don't see any problem with more threads
accessing P, except the lack of a FIFO queue. Can you be clearer? I'm
not sure I get this.

 

[blmblm]

I wouldn't say it's correct. There are two things that don't convince me:
1) a thread shouldn't be able to call V without calling P. You can't
release a resource if you don't get it

Well .... But semaphores are a rather general synchronization
mechanism that can be used for things other than "acquire a resource
/ release the resource." An example is a producer/consumer setup,
where you have one thread "producing" things and putting them in a
shared buffer, and another thread "consuming" them. A reasonable way
to make the consumer wait if there is nothing to consume is by using
a semaphore, with the producer doing "V" operations and the consumer
doing "P" operations.

2) notify is not deterministic. It would be better to have a FIFO queue,
or there is a chance, altough small, that a thread will wait forever
I also know that some JVMs don't work as they should, and in some cases
a waiting thread can wake up without notify being called.
There are probably a lot of resources on the web about this

A JVM that allows "wait" to complete without a corresponding "notify"
would be broken, no? Can anyone point to evidence that these exist?
Just curious.

[ snip ]

 

[xarax]

the code is synchronized, I don't see any problem with more threads
accessing P, except the lack of a FIFO queue. Can you be clearer? I'm
not sure I get this.

The code is not always synchronized, because wait() releases
the monitor. When notify() is called, the target thread becomes
dispatchable and it must compete with other threads to re-acquire
the monitor before returning from wait(). There may be another
thread already suspended at the outer synchronized block that
will get the monitor *after* the V() method exits and *before*
the wait() returns.

IIRC, the original posted Semaphore class is something
like this (please advise if there is any substantive
difference between this and the original code):
=====================================
public class Semaphore
{
private int count = 1;

public void procure()
throws InterruptedException
{
synchronized(this)
{
if(count == 0) /* Should be while(count==0) */
{
/* releases the monitor, then re-acquires later */
wait();
}
count--;
}
}

public void vacate()
{
synchronized(this)
{
if(count == 0)
{
notify();
}
count++;
}
}
}
=====================================

The design starts the semaphore.count field
at 1, which means that the semaphore is available.
Acquiring the semaphore changes the count to 0.
Releasing the semaphore changes the count to 1.

btw: I factored out the InterruptedException to
get rid of the recovery path. It's not relevant
to this discussion.

Now assume there are 3 threads, A, B, and C. Thread
A calls procure(), and the other threads are doing
something else so there is no contention for the
semaphore.

Thread A has acquired the semaphore and returned
from procure(). Now thread B calls procure(), which
acquires the monitor, checks for if(count==0) and sees
that another thread has already acquired the semaphore.
So, thread B calls wait(), which releases the monitor.

Now thread A calls vacate(), which acquires the
monitor. Then thread C calls procure(), which attempts
to acquire the monitor, but is blocked because thread
A already has the monitor. Meanwhile, thread B is still
waiting inside wait().

Thread A calls notify() which awakens thread B. Thread
B now attempts to re-acquire the monitor. Thread C is
still trying to acquire the monitor. Both thread B
and thread C are now competing for the monitor.

When thread A exits the vacate() method, the monitor
is released and it is unpredictable whether thread B
or thread C will acquire the monitor. If thread B
acquires the monitor, then all is well. However, if
thread C acquires the monitor, then it will see that
(count != 0) and it will proceed to change "count"
to 0, so that it will own the semaphore.

When thread C exits procure(), the monitor is released
and now thread B can acquire the monitor and return
from wait(). Since procure() does not loop back to
re-test the value of count (which is 0), thread B will
proceed to assume that it has acquired the semaphore
(thread C actually has acquired the semaphore). Thus,
both thread B and C will return from procure(), with
each thread believing that it has acquired the semaphore.

Both threads, believing they each have acquired the
mutex semaphore, will now enter their critical sections
and clobber each other.

In actual practice, the semaphore paradigm is much
more complicated, and is properly synchronized to avoid
the race condition described above. The above sample
Semaphore class is woefully broken to handle either
exclusive or shared semaphores.

Hope this helps.

--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS for FREE!

 

[Ann]

There seem to be quite a number of not very clean and simple
implementations
of java Semaphores in the internet. The following example is extremely
simple (the Java 1.5 implementation is overfeatured IMHO) and correct:

I guess it is fine to re-invent things if you have a lot of time
on your hands. Is there any practical application for your thing
that can't be achieved with normal methods?

 

[Chris Smith]

A JVM that allows "wait" to complete without a corresponding "notify"
would be broken, no? Can anyone point to evidence that these exist?
Just curious.

No, it would absolutely not be broken. Recent versions of the API
documentation even explicitly state that spurious wakeups are possible
for Object.wait().

From a practical standpoint, these can happen on UNIX operating systems
when a signal is delivered during a wait; signals typically abort
blocking system calls on UNIX and many UNIX implementations of pthreads
carry this over to condition variable behavior (though the pthreads spec
itself leaves the matter undefined). However, whether your code plans
to run on UNIX and related operating systems or not, the specification
for Java clearly leaves open the possibility of spurious wakeups, and
you should account for them by always using a predicate loop with your
wait/notify.

Even without this possibility, predicate loops are always a good idea --
especially in Java where objects' monitors are often subject to multiple
related uses.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Chris Smith]

I googled InterruptedException and cam up with this page:
http://www.milk.com/java-rants/rant01-interrupted.html
It basically states that the exception ONLY occurs when someone in the same
VM calls Thread.interrupt() on the thread in question. This page also
discusses four options of how to handle the exception. One is to consume it
(like I do, with an error message that points to the error of using
Thread.interrupt()), another is to rethrow it. I concede that throwing
an exception might be a viable option IF you really need to call Thread.interrupt().

If you're claiming to post code that's generally useful to others,
perhaps you shouldn't assume that they won't be interrupting threads.
InterruptedException may be impossible 90% or more of the time, but the
right thing to do is to throw it and let the caller decide.

That, plus the bug with "if (count == 0)", makes this a very poor choice
of Semaphore implementation. Fortunately, in the current version of
Java, there is already a Semaphore class available in
java.util.concurrent, and I would bet money that it actually works,
unlike yours.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Frank Gerlach]

The call to wait() releases the monitor. Think about what
could happen when multiple threads are calling P(). The
multiple threads will call wait(). Another thread will
subsequently call notify(), which will randomly awaken
one of the threads, not necessarily the first thread that
chronologically entered P(). Upon awakening, the thread
will then re-acquire the monitor.

The "while(count==0)" is required.

What happens if multiple threads are sleeping (wait()ing) in P(). A thread
doing V() will increase count to 1 and will then call notify() and exit
the synchronized block.AFTER that, EXACTLY ONE of the sleeping threads wakes up,
decrements count, which is now ZERO again. This means that the condition for
the other sleeping threads (count==0) is still satisfied.
Why the while() loop ??

 

[xarax]

What happens if multiple threads are sleeping (wait()ing) in P(). A thread
doing V() will increase count to 1 and will then call notify() and exit
the synchronized block.AFTER that, EXACTLY ONE of the sleeping threads wakes up,
decrements count, which is now ZERO again. This means that the condition for
the other sleeping threads (count==0) is still satisfied.
Why the while() loop ??

I already posted the explanation. The wait()
will release the monitor before going to sleep.

The problem is a race condition for re-acquiring
the monitor before wait() returns, versus another
thread that is calling P() and suspended at the explicit
"synchronized(this)". You are assuming that the
wait()'ing thread gets some special privilege
to re-acquire the monitor before any other
thread. In reality, wait() competes for re-acquiring
the monitor the same as any other thread attempting
synchronized().

So, you do not know which thread will acquire the monitor,
claim the semaphore, then release the monitor. When the
monitor is released, the wait() will return and also claim
the semaphore, which means that two threads will think they
have acquired the semaphore.

The while() is required. The if() is a defect, and it
has nothing to do with spurious awakenings. It has
everything to do with race conditions for re-acquiring
the monitor. The thread must go back to the start of
the "synchronized()" block and re-test everything the
same as if it was initially entering the synchronized
block.


--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS for FREE!

 

[Chris Smith]

Frank,

Even ignoring spurious wakeups (which are quite possible in a completely
working virtual machine and obviously require the predicate), there is
this scenario:

1. Semaphore is created with count set to 1.

2. Thread A executes P() and completes successfully. The count is now
set to 0.

3. Thread B enters P(), finds count to be 0, and goes to sleep
(releasing the monitor).

4. Thread A executes V(). Count is now 1, and thread B has been moved
from a blocked state to a runnable state.

5. Thread C enters P() and executes successfully (remember that Thread A
already incremented the count). The count is now 0 again.

6. Thread B is scheduled. It re-acquires the monitor, FAILS to check
count, decrements counts, and leaves. Count is now -1, and your
semaphore has failed.

You seem to be under the impression that a call to notify() causes the
monitor to be immediately given to the thread receiving the
notification, or that the thread receiving the notification is
immediately scheduled. Neither of those are true; the notified thread
merely becomes runnable, and it competes for a time slice on an equal
basis with any other thread, meaning that (as above) a thread C could
easily be scheduled first.

Hope that makes (one of) the problem(s) clear.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Matt Humphrey]

Frank,

Even ignoring spurious wakeups (which are quite possible in a completely
working virtual machine and obviously require the predicate), there is
this scenario:

1. Semaphore is created with count set to 1.

2. Thread A executes P() and completes successfully. The count is now
set to 0.

3. Thread B enters P(), finds count to be 0, and goes to sleep
(releasing the monitor).

4. Thread A executes V(). Count is now 1, and thread B has been moved
from a blocked state to a runnable state.

5. Thread C enters P() and executes successfully (remember that Thread A
already incremented the count). The count is now 0 again.

6. Thread B is scheduled. It re-acquires the monitor, FAILS to check
count, decrements counts, and leaves. Count is now -1, and your
semaphore has failed.

You seem to be under the impression that a call to notify() causes the
monitor to be immediately given to the thread receiving the
notification, or that the thread receiving the notification is
immediately scheduled. Neither of those are true; the notified thread
merely becomes runnable, and it competes for a time slice on an equal
basis with any other thread, meaning that (as above) a thread C could
easily be scheduled first.

Hope that makes (one of) the problem(s) clear.

Beautiful example, Chris. It's the best one I've seen for explaining why
receiving notify does not imply that the waiting condition has been met.

Cheers,
Matt Humphrey (e-mail address removed) http://www.iviz.com/

 

[Ann]

Beautiful example, Chris. It's the best one I've seen for explaining why
receiving notify does not imply that the waiting condition has been met.

You don't need an example if you just read the book!