How is mutex internally implemented

Question

I've spent some time trying to understand how are mutexes implemented in several languages. There are multiple links describing the topic (*) but if I understand that correctly, all that hardware provides are some atomic operations that may help to distinguish who should be in turn now.

In software this is always used for busy waiting (try CAS or test-and-set and wait in while cycle if not successful), but how does the scheduler know that now I should take away the process/thread from CPU because all it does is that it waits? Is there some support in OS provided that for example Java synchronization uses in order to signal that "I am blocked, please let other Threads run instead"? I think it is, since busy-waiting is an alternative to use lock(); (so they should not be the same)

*Source:

• http://en.wikipedia.org/wiki/Mutual_exclusion
• How are mutex and lock structures implemented?

Answer 1

In Linux JDK soure C code uses pthread library which is part of standard C library. That, in turn, uses Linux kernel futex feature (man futex). As far as I can understand, this implemented using kernel scheduler to put calling thread to sleep and to wake it back when signal received.

Scheduler itself relies on timer interrupts (hardware) to work -- essentially, everytime timer interrupt arrives, scheduler has to check if current user-space thread wants/must be suspended and, if yes, it must choose some other thread.

Here few further links for much more clear and detailed explanation:

1. http://man7.org/linux/man-pages/man7/futex.7.html
2. http://www.quora.com/How-different-is-a-futex-from-mutex-conceptually-and-also-implementation-wise
3. Book by Robert Love's Linux Kernel Development (but, oddly enough, it does not contain a single mention of futex) and another book (which does contain futex mentions but mostly in references to external papers): Kerrisk's The Linux Programming Interface.