About "java.util.concurrent.Semaphore" design ...

Thread view:

Red Orchid - 24 Nov 2006 21:56 GMT

(Reference: http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/Semaphore.html)

This is a part of the above page.

"...
Semaphores are often used to restrict the number of threads
than can access some (physical or logical) resource. ...

class Pool {
private static final MAX_AVAILABLE = 100;
private final Semaphore available = new Semaphore(MAX_AVAILABLE, true);

public Object getItem() throws InterruptedException {
available.acquire();
return getNextAvailableItem();
}

public void putItem(Object x) {
if (markAsUnused(x))
available.release();
}
... "

In the above code,
the semaphore "available" do not guarantee reliably
that "MAX_AVAILABLE" is 100.

Because "Semaphore" allows the following code.

<code>
int val = 2;
Semaphore sema = new Semaphore(val);
sema.release();

// sema.availablePermits() is 3.
</code>

The max number of permits available is controlled by
the calling number of "release()" too.

If a bug occur in connection with calling "release()",
"MAX_AVAILABLE" will become 100 + x.

I think that the current design of "Semaphore" is brittle in
a use of restricting the number of threads than can access
some resource.

What is your comment ?
Thanks.

Reply to this Message

Wesley Hall - 24 Nov 2006 23:09 GMT

> What is your comment ?

This is the documented behaviour and covers two points about Semaphores...

1) The thread that calls release need not be the thread the called
acquire. The API docs clearly state this in the documentation for the
release method when they say

"There is no requirement that a thread that releases a permit must have
acquired that permit by calling acquire(). Correct usage of a semaphore
is established by programming convention in the application."

There is also an indication as to why this is in the main documentation
for the class..

"When used in this way, the binary semaphore has the property (unlike
many Lock implementations), that the "lock" can be released by a thread
other than the owner (as semaphores have no notion of ownership). This
can be useful in some specialized contexts, such as deadlock recovery."

2) Calling release will increase the number of permits available above
and beyond the initial permit count. The constructor docs indicate this
with...

"permits - the initial number of permits available. This value may be
negative, in which case releases must occur before any acquires will be
granted."

I cannot immediately think of a situation where this would be useful,
but I am sure somebody could.

What is slightly misleading is the code example in the docs, where the
constant that is used to set the initial permit count is called
"MAX_AVAILABLE". This could be read to mean that the parameter expresses
the maximum available permits in the semaphore but it does not.
Presumably the author used this name because the value happened to
express the maximum permits in the example because extra calls to
release are not possible in the example code. That is to say they are
not possible (they may even been desired) in other code that uses the
semaphore class.

The key part in the docs is this...

"When used in this way, the binary semaphore has the property (unlike
many Lock implementations), that the "lock" can be released by a thread
other than the owner (as semaphores have no notion of ownership)."

You are saying that you don't want this behaviour and so perhaps 'Locks'
are more appropriate than Semaphores. Under java.util.concurrent.locks
you will find classes that support locks that can maintain information
as to the owner thread. Unfortunatly, the only useful concrete
implementation is LockSupport which can only maintain a single lock,
however, it should not be too difficult to use the classes provided in
the java.util.concurrent.locks package to create an implementation where
lock ownership is maintained so that releases can only be performed by
owning threads. This will give you the behaviour you desire.

Reply to this Message

Mike Schilling - 25 Nov 2006 00:14 GMT

> 2) Calling release will increase the number of permits available above
> and beyond the initial permit count. The constructor docs indicate this
[quoted text clipped - 6 lines]
> I cannot immediately think of a situation where this would be useful,
> but I am sure somebody could.

Perhaps to ensure that N pieces of complicated, asynchronous initialization
all succeed before a server is allowed to process requests.

Reply to this Message

Wesley Hall - 25 Nov 2006 00:59 GMT

>> 2) Calling release will increase the number of permits available above
>> and beyond the initial permit count. The constructor docs indicate this
[quoted text clipped - 9 lines]
> Perhaps to ensure that N pieces of complicated, asynchronous initialization
> all succeed before a server is allowed to process requests.

That'll do :)

Reply to this Message

Red Orchid - 25 Nov 2006 01:46 GMT

Wesley Hall <noreply@example.com> wrote or quoted in
Message-ID: <45677b9b$0$8718$ed2619ec@ptn-nntp-reader02.plus.net>:

> [snip]
> The key part in the docs is this...
[quoted text clipped - 7 lines]
> you will find classes that support locks that can maintain information
> as to the owner thread. ...

It seems that the ownership of lock is not helpful to the
implementation of restricting the number of threads.

Let's consider the following case.

- Mother thread P.
- Her children thread C0, C1, C2. // MAX_AVAILABLE = 3
- Her children process resources simultaneously.
- She is informed of when all the children finish their tasks.
- Resource R0, R1, ... , Rn // ex: n > 100

The implementation of this case will be like:

<code_0>

//
// Mother thread P
//

ResourceSupplier rsup = ...;

void process() {

while (true) {

Resource R = rsup.offer();

if (R == null) break;

new Child_Thread( R ).start();
}

// All the resource are processed.
}

void anyResourceProcessed() {
rsup.processed();
}

//
// Child_Thread
//

class Child_Thread extends Thread {

....

public void run() {

// process R

anyResourceProcessed();
}

}

//
// ResourceSupplier
// (Exceptions were ignored for simplicity.)
//

class ResourceSupplier {

int count = 0;
int MAX_AVAILABLE = 3;
Queue<Resource> queue = ... // R0, R1, ... , Rn

synchronized Resource offer() {

        if (count == MAX_AVAILABLE) {

            wait();
        }
        Resource R = queue.offer();

if (R != null) {

count++;
return R;
}

// Code_Bock_A
while (count > 0) {

        wait();
}

// All the resource are processed.
return null;
}

synchronized void processed() {

count--;
    notify();
}
}
</code_0>

That is,
The ownership of lock has no correlation with the implementation
of restricting the number of threads. Any child thread can wake
"offer()" up. The semaphore concept is needed.

With the current "java.util.concurrent.Semaphore",
the implementation of the above case will be difficult
(Specially the implementation of "Code_Bock_A" and
debugging).

Reply to this Message

Wesley Hall - 25 Nov 2006 02:08 GMT

> Wesley Hall <noreply@example.com> wrote or quoted in
> Message-ID: <45677b9b$0$8718$ed2619ec@ptn-nntp-reader02.plus.net>:
[quoted text clipped - 13 lines]
> It seems that the ownership of lock is not helpful to the
> implementation of restricting the number of threads.

It is very helpful in solving the problem you originally proposed. The
issue was (as I understand it) that you might have more calls to release
permits than permits available, resulting in a total number of permits
higher than the initial figure, but this is expected behaviour in
Semaphore.

By maintaining account of lock ownership, you would be able to prevent
threads that had not previously requested a permit, from successfully
calling release. The number of permits would not be able to grow beyond
the initial figure because you are keeping close account of where the
permits currently are. Semaphore does not do this, requesting permits
and releasing permits are 'loosely coupled' and intentionally so.

> Let's consider the following case.
>
[quoted text clipped - 3 lines]
> - She is informed of when all the children finish their tasks.
> - Resource R0, R1, ... , Rn // ex: n > 100

If you intention is to inform a 'parent thread' that all 'child' threads
have finished their tasks, and you know the exact number of child thread
that will run, then you are using the wrong class, semaphore is not for you.

You might want to try CountDownLatch. The first paragraph of the JavaDoc
for this class reads...

"A synchronization aid that allows one or more threads to wait until a
set of operations being performed in other threads completes."

<snip code example>

I am not exactly sure what you are getting at from this point, and the
code example wasn't very clear to me. I am sorry, I cannot comment on that.

Reply to this Message

Red Orchid - 25 Nov 2006 02:51 GMT

Wesley Hall <noreply@example.com> wrote or quoted in
Message-ID: <4567a58d$0$8739$ed2619ec@ptn-nntp-reader02.plus.net>:

> <snip code example>
>
> I am not exactly sure what you are getting at from this point, and the
> code example wasn't very clear to me. I am sorry, I cannot comment on that.

With the current "java.util.concurrent.Semaphore",
The implementation of the case will be like:

<code_1>
....
class ResourceSupplier {

int MAX_AVAILABLE = 3;
Semaphore sema = new Semaphore(MAX_AVAILABLE);

Resource offer() {

sema.acquire();
Resource R = queue.offer();

if (R != null) {

return R;
}

// Code_Bock_A
sema.acquire(MAX_AVAILABLE - 1)

// All the resource are processed.
return null;
}

void processed() {

sema.release();
}
}
</code_1>

If a bug of calling "processed()" occur somewhere in the entire source,
the max available value will become 3 + x and "offer()" will be blocked
endlessly by "sema.acquire(MAX_AVAILABLE - 1)".
In multithreaded environment, the debugging can be very difficult.

Thank for your comments.

Reply to this Message

Wesley Hall - 25 Nov 2006 03:15 GMT

> If a bug of calling "processed()" occur somewhere in the entire source,
> the max available value will become 3 + x and "offer()" will be blocked
> endlessly by "sema.acquire(MAX_AVAILABLE - 1)".

...but aren't you just saying... "Look... here is some buggy code where
I am use a API class improperly... and there is a bug!"

The Semaphore class is very clear on how it works, the documentation
states the behaviour in VERY precise terms. If you do not use the
Semaphore class in the way it was intended, of course you will have
bugs. I could easily ask you to pick an API class at random, and I could
write some code that would use that API class incorrectly and there
would be a bug. This doesn't mean the API class itself has bugs.

It seems to me that what you are saying is that you find the Semaphore
class unintuative. That is a different issue, and is fair enough. It
might even be fair to say the majority of developers may find the class
unintuative. That does not make it 'buggy' in the strictest sense.

Reply to this Message

About "java.util.concurrent.Semaphore" design ...

Free Magazines