Counting (and synchronizing) resources

[AbraKadabra]

I have the following problem:

I have a pool of resources with a fixed size and a bunch of client
threads that constantly need to use an arbitrary number of resources
for a small amount of time. Once a client is done using these resources
it would return them to the pool.

Specifically, I need to implement the following interface:


/**
* Take 'n' resources.
* Once the method returns, 'n' resources are available to the caller.
* If not enough resources are available, will block (at most 'timeout'
* milliseconds) until the requested number of resources is available.
*/
public void take(int n, long timeout) throws TimeoutExpiredException;

/**
* Return 'n' resources to the pool.
* If enough resources are now available, will wake blocked threads
* that now have sufficient resources in the same order in which they
* started blocking.
*/
public void put(int n);


Note the "fairness" requirement (blocked threads should be released in
the same order they started the block). Also note that these two
methods need to be thread-safe.

The question is: Is there way to use some high-level concurrency
mechanism to solve this problem?

I actually managed to solve it using locks and condition variables, but
of course, implementation was non-trivial.


Thanks,
AbraKadabra

 

[Gordon Beaton]

I have a pool of resources with a fixed size and a bunch of client
threads that constantly need to use an arbitrary number of resources
for a small amount of time. Once a client is done using these
resources it would return them to the pool.

You have described ordinary counting semaphores. They are available
since 1.5 in java.util.concurrent, or (prior to 1.5) in Doug Lea's
concurrent package (use Google).

/gordon

 

[Chris Uppal]

Note the "fairness" requirement (blocked threads should be released in
the same order they started the block). Also note that these two
methods need to be thread-safe.

The question is: Is there way to use some high-level concurrency
mechanism to solve this problem?

Does java.util.concurrent.Semaphore (introduced in 1.5) do what you want ?

-- chris

 

[AbraKadabra]

....yep. Seems like it does exactly what I want... and more.

Oh well, it was a nice exercise in locks and condition vars.

Thx!

 

[Robert Klemme]

Does java.util.concurrent.Semaphore (introduced in 1.5) do what you
want ?

-- chris

I doubt that they satisfy the fairness requirement as Object.notifyAll()
and notify() randomly pick a thread.

Apart from that this smells like a homework assignment...

robert

 

[AbraKadabra]

Actually it does! I also use a LinkedList of Requests and notify only
the first one, which if released, notifies the next and so on until the
woken up thread has insufficient resources and goes back to sleep.

To keep your conscience clean, it's not homework, but it represents an
OS limit on the maximum number of concurrently used file descriptors in
Linux. I have multiple threads doing socket selects and cannot surpass
that max number.

AbraKadabra

 

[Chris Uppal]

I doubt that they satisfy the fairness requirement as Object.notifyAll()
and notify() randomly pick a thread.

There's a "fairness" parameter to java.util.concurrent.Semaphore's constructor
that sets this aspect of its behaviour. (The JavaDoc for the constructor is
very unclear about that parameter's meaning but the class comment makes it
clear.)

-- chris

 

[=?ISO-8859-1?Q?Karl_=D8ie?=]

Save your self some typing and use an existing implementation:

http://jakarta.apache.org/commons/pool/

Karl Øie

 

[Oliver Wong]

Specifically, I need to implement the following interface:

/**
* Take 'n' resources.
* Once the method returns, 'n' resources are available to the caller.
* If not enough resources are available, will block (at most 'timeout'
* milliseconds) until the requested number of resources is available.
*/
public void take(int n, long timeout) throws TimeoutExpiredException;

Are you sure you don't mean "at LEAST 'timeout' milliseconds"? I think
the behaviour of sleep() is to sleep at LEAST a certain amount of time.

To have an "at most" restriction means you're entering into the domain
of Real Time Systems, which is relatively difficult to do. I think vanilla
Java has no support for real time systems (though unofficial extensions to
the Java language have been released that have some support for this).

- Oliver

 

[Gordon Beaton]

Are you sure you don't mean "at LEAST 'timeout' milliseconds"? I
think the behaviour of sleep() is to sleep at LEAST a certain amount
of time.

Realtime issues aside, I think he does intend to wait "at most" a
given time for the resource to become available. Compare this with
calling wait(timeout) (which the specified operation likely maps
directly onto), or reading from a socket when setSoTimeout() has been
called, etc.

/gordon

 

[Roedy Green]

The question is: Is there way to use some high-level concurrency
mechanism to solve this problem?

There is a whole mess of new tools in Java 1.5 for solving this sort
of thing in java .util.concurrency. See
http://mindprod.com/jgloss/queue.html
and wander around in the candy store.

 

[Wibble]

There is a whole mess of new tools in Java 1.5 for solving this sort
of thing in java .util.concurrency. See
http://mindprod.com/jgloss/queue.html
and wander around in the candy store.

ArrayBlockingQueue is particularly nice.