Java thread execution order after unlock

Let's say I have 2 threads, t1 and t2, and a lock object, m. Thread t1 is in an infinite loop, where at each iteration, it grabs a lock on m, does some work, unlocks m and starts over immediately. During one iteration, t2 requests a lock on m but gets blocked by t1 and has to wait. Now, when t1 unlocks m, is it guaranteed that t2 will obtain the next lock on m? or can t1 sneak ahead of it at the next iteration?

Generally, is there a queue set up for waiting threads? If t1 has the lock, and all remaining threads also want开发者_运维问答ing that lock get blocked in the following order: t2, t3, ..., will the remaining threads continue execution in the order that they were blocked (e.g. t2 runs, then t3, etc.)?

(I briefly perused the java spec and couldn't find the answer. If it's in there, please let me know, and I will go back to read more carefully.)

Thanks! (First SO post, woohoo!)

Yes, there is a queue and it can be fair or not. Fair queues are more expensive and non-fair are faster (who wins the CAS wins the lock). check java.util.concurrent.locks.AbstractQueuedSynchronizer for further info.

will the remaining threads continue execution in the order that they were blocked (e.g. t2 runs, then t3, etc.)?

The main issue is that they are executed concurrently/simultaneously, you can't truly define order for 2 events that are executed in the same time. But w/ fair (unrecommended due to extra costs) locks any thread that manages to enlist itself for the lock will get eventually get to own it.

No, there are no such guarantees. You can advise Java to be ReentrantLock objects to be fair, but that's advisory and does not guarantee any order.

In general, you cannot (without explicit synchronization to achieve it) guarantee such an order, because t2 could have been interrupted before it even acquired the thread, and it's solely up to the OS to decide which thread gets resumed when.

No there is no guarantee for most purposes. You'll notice some of the java.util.concurrent abstractions offer the option of a "fair lock" - which does more or less guarantee each thread waiting on a lock will eventually be called (not a specific order). Without fairness, there is no guarantee. OTOH, fairness is EXTREMELY expensive. (See Java Concurrency In Practice for some benchmarks), and usually, probablistic likelihood is good enough.

You can guarantee order by using fair Semaphore. Standard built-in Java locks/monitors aren't fair a do not queue orders in a fair manner.

Semaphore sem = new Semaphore(1, true);

//usage:
sem.acquire();
try {
  //holding a lock
  //of course both threads share the same semaphore
} finally {
  sem.release();
}

With locks theoretically T1 can take a lock in next iteration again after releasing it, despite the fact that T2 already waits for it. Unlikely, but possible.