[concurrency-interest] Enforcing ordered execution of critical sections?

Justin Sampson jsampson at guidewire.com
Mon Dec 22 15:57:53 EST 2014

Doug Lea wrote:

> Suppose you have thread 1 acquire(7), and then thread 2: acquire(5).
> With fairness, thread 2 waits for thread 1 to succeed before
> trying. Without fairness, they could be in any order, but still
> *some* order. So the net effect is not quite the same as
> the above loop, but closer than implying that the semaphore
> somehow sorts waiters by #permits, which it doesn't/can't.

It sounds like many of us might have expected for a semaphore to behave something like this:

synchronized void acquire(int permits) {
  while (state < permits) {
  state -= permits;

synchronized void release(int permits) {
  state += permits;

And it sounds like what's actually happening is more like a notify() rather than a notifyAll(), which is a perfect recipe for lost notifications whenever you have multiple threads that are actually waiting for different conditions to become true, as in the case we're discussing.

Is there any way for Semaphore's acquire() to propagate the notification if it wakes up and finds not enough permits, at least in the non-fair case?

That is, if the acquire(7) thread gets unparked and sees that there are fewer than 7 but more than 0 permits available, can it unpark the next thread before parking itself again, so that the next thread can try its acquire(5)? In the worst case you end up cycling through all the waiting threads, which is nasty, but sounds better to me than deadlocking unnecessarily, and only happens when _all_ of the threads are requesting more than 1 permit in acquire().

Of course, that would mean that using Semaphore to implement the OrderedExecutor idea in this thread ends up worse than many of the other solutions, except for its conciseness. :)


More information about the Concurrency-interest mailing list