Sunday, June 19, 2011

Useful Tricks with Semaphores

Release doesn't have to be called by same thread as acquire

One interesting property of Semaphores in Java is that release doesn’t have to be called by the same thread as acquire. This means you could have a thread limiter that pools or creates threads based on a semaphore by calling acquire(). Then, the running thread could release its own semaphore permit when it completes. This is a useful property that we don’t have with normal mutexes in Java.

Dynamically increase or decrease the permits

Another trick is to increase or decrease the number of permits at runtime.
To increase the number of Permits
Contrary to what you might guess, the number of permits in a semaphore isn’t fixed, and a call to release() will always increment the number of permits, even if no corresponding acquire() call was made. Note that this can also result in bugs if you are incorrectly calling release() when no acquire() was made.

To decrease number of permits

To be specific, if 10 threads currently have permits and 7 is the new limit, we won’t try to communicate to any threads that they are now in violation of the new limit. What we can do is make sure that the next call to acquire() will block until enough threads (4, to be precise) have called release() to bring the number of outstanding permits to below the new limit. It’s not infeasible to interrupt threads that are holding permits beyond the new upper limit, but that’s beyond the scope of a simple semaphore.

If you wanted to reconfigure it to only allow 7 permits, you have several options:

  • You call acquire() three times. This might work, or it might block forever — if more than 7 permits are currently in use, one (or more) of your acquire() calls could block for an arbitrarily long amount of time. Checking availablePermits() isn’t going to help, either, since using that to gauge whether or not an acquire() call will block is a classic check-then-act race condition. Even if the race condition could be avoided, it doesn’t help: instead of blocking, you’ll just keep getting 0 back from availablePermits().
  • You could call drainPermits() repeatedly until at least 3 permits had been drained (and then release() any extra that were drained beyond the 3 you need). This could take an arbitrarily long time.
  • You could call tryAcquire() repeatedly until you’ve gotten 3 permits. This also could take an arbitrarily long time.

These approaches all share two flaws:

  1. Most importantly, they block until as many permits as you are trying to remove have become available
  2. They don’t really achieve the goal directly

To be precise, the goal is that the semaphore should release fewer permits to the threads that are using the semaphore to control access to the shared resource. Acquiring (and presumably not releasing) permits is one way to achieve the goal, but it is not necessarily the only way. Put another way, the thread that is executing the reconfiguration does not technically need to acquire permits (whether it be by acquire() or drainPermits() or tryAcquire(), etc) to fulfill this requirement, since it doesn’t need to access the shared resource that the semaphore is guarding. So we come to the last solution - Extending Semaphore to use reducePermits().

Some more useful methods

Finally, there are a few useful methods to be familiar with in Java’s Semaphore. The method acquireInterruptibly() will acquire a resource, reattempting if it is interrupted. This means no outside handling of InterruptedException. The method tryAcquire() allows us to limit how long we will wait for a permit – we can either return immediately if there is no permit to obtain, or wait a specified timeout. If you somehow have known deadlocks that you can’t fix easily or track down, you could help prevent locking up processes by using tryAcquire() with suitable timeouts.

No comments:

Post a Comment