How deterministic are Java semaphores guaranteed to be?

user_1151724 0
Viewed 182

The (Oracle) javadoc for Semaphore.release() includes:

If any threads are trying to acquire a permit, then one is selected and given the permit that was just released.

Is this a hard promise? This implies that if thread A is waiting in acquire() and thread B does this:

sem.release()
sem.acquire()

Then the release() should pass control to A and B will be blocked in acquire(). If these are the only two threads that can hold the semaphore and the doc statement is formally true, then this is a completely deterministic process: Afterward, A will have the permit and B will be blocked.

But this is not true, or at least it does seem that way to me. I haven't bothered with an SSCCE here since I am really just looking for confirmation that:

Race conditions apply: Even though thread A is waiting on the permit, when it is released it can be immediately re-acquired by thread B, leaving thread A still blocked.

These are "fair" semaphores if that makes any difference, and I'm actually working in kotlin.

kotlin race-condition multithreading semaphore java
1 Answers

In comments on the question Slaw pointed out something else from the documentation:

When fairness is set true, the semaphore guarantees that threads invoking any of the acquire methods are selected to obtain permits in the order in which their invocation of those methods was processed (first-in-first-out; FIFO). Note that FIFO ordering necessarily applies to specific internal points of execution within these methods. So, it is possible for one thread to invoke acquire before another, but reach the ordering point after the other, and similarly upon return from the method.

The point here is that acquire() is an interruptable function with a beginning and an end. At some point during its exception the calling thread secures a spot in the fairness queue, but when that is in relation to another thread concurrently accessing the same function is still indeterminate. Call this point X and consider two threads, one of which holds the semaphore. At some point another thread calls:

   sem.acquire()

There is no guarantee that the scheduler won't sideline the thread inside acquire() before point X is reached. If the owner thread then does this (this could be, eg., intended as some kind of synchronization checkpoint or barrier control):

   sem.release()
   sem.acquire()

It could simply release and acquire the semaphore without it being acquired by another thread even if that thread has already entered acquire.

The injection of Thread.sleep() or yield() between the calls might often work, but it is not a guarantee. To create such a checkpoint with that guarantee you need two locks/semaphores for an exchange:

  • Owner thread holds semA.
  • Client thread can take semB and then wait on semA.
  • Owner can release semA then wait on semB, which if another thread is really waiting for semA by holding semB, will block and guarantee semA can now be acquired by the client.
  • When the client is done, it releases semB, then semA.
  • When the owner is released from waiting on semB, it can acquire semA and release semB.

If these are properly encapsulated this mechanism is rock solid.

user_11517240
Related