Two threads are waiting on a mutex. Which one is unblocked?

Question

Suppose there are three threads A, B, C and thread A has acquired a mutex lock and it is processing. If threads B and C try to acquire the same mutex, they will be blocked according to the mutex lock concept. But once thread A completes, which of the threads will be unblocked? Is there any scheduling policy?

Answer 1

The short answer is "it depends".

If there is truly nothing to distinguish thread B from thread C, then the answer on most scheduler implementations will likely be either "could be B or C, and you can't predict which one in advance", or "the one which tried to acquire the mutex first" (i.e. first-come, first-served).

However, there may be something which distinguishes them in some way, and that's where it gets more interesting. In particular, if the implementation supports priority scheduling, one of the threads may have a higher priority than the other, in which case the higher-priority thread should be scheduled first.

Sometimes the programmer will decide that thread B should have a higher priority than thread C. Some schedulers assign higher priorities to tasks which have earlier deadlines, or periodic tasks with shorter periods (known as rate-monotonic scheduling).

In other circumstances, even if two threads have the same nominal priority, the scheduler may give one a higher effective priority than the other.

For example, in a non-realtime system, a scheduler may decide that one thread is more of a background task than the other (e.g. in a pre-emptive multitasking environment, a thread which seems to exhaust its quantum is probably a "background thread"), and so should have a lower effective priority than a more "interactive" thread. This is a common heuristic to make a system more responsive (or appear more responsive!) because interactive jobs are given priority.

Another common scenario is if one of the threads is already holding a priority-aware synchronisation object (say, a priority inheritance mutex or a priority ceiling mutex). In that case, the thread may have its effective priority raised to ensure that it releases the critical object more quickly.