4

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:

Community
  • 1
  • 1
Matej Briškár
  • 599
  • 4
  • 17
  • 2
    In it's core, a mutex is a kernel object, used by the kernel. It influences the state of a thread (runnable, waiting, ...) and that in turn is used by scheduler to make decisions. This is why mutexes are not really "cheap" and often combined with optimizations such as spin locks, which try to avoid a kernel call. – BitTickler Apr 14 '15 at 17:13

2 Answers2

5

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.
Victor Sorokin
  • 11,878
  • 2
  • 35
  • 51
  • Scheduler is triggered not only by the timer. More (3?!) code paths trigger the scheduler in linux kernel. Trying to obtain a mutex which is already taken is a showcase for that. – BitTickler Apr 14 '15 at 17:16
  • Just a question to know if I understand that correctly. It means that if my thread is blocked, it is still in charge until the scheduler will be woken up and see that the thread does nothing? – Matej Briškár Apr 14 '15 at 17:20
  • 2
    No - in OS agnostic terms -, your applications thread calls the kernel with "takeMutex()". In its implementation in kernel space, ``takeMutex()`` may see the mutex is already taken and invoke the scheduler in one form or another. The timer trigger for scheduler is what happens mostly to grant "fair" time slices to all threads in "running" state. – BitTickler Apr 14 '15 at 17:23
  • Thanks user, understood. I think there is also some support for semaphores that is very similar to this. – Matej Briškár Apr 14 '15 at 17:27
  • Yes, there is a whole set of "kernel objects", mutex being one of them. Depending on OS, this can also include file handles etc. – BitTickler Apr 14 '15 at 17:28
  • Yes, Kerrisk's book mentions that modern Linux systems imlpement semaphores using futexes. To check by yourself, you can examine code of C library (glibc). – Victor Sorokin Apr 14 '15 at 17:29
  • Semaphore, mutex, and futex are all interchangeable in the sense that, if you have any one of them, you can use it to implement the others. In Linux, the most primitive operation (i.e., the one provided by the kernel) is futex,, so all of the synchronization objects in a program running on Linux ultimately are implemented in terms of futex system calls. – Solomon Slow Apr 14 '15 at 17:43
3

That's a book level topic. Here's the book:

The Art of Multiprocessor Programming Maurice Herlihy, Nir Shavit ISBN-13: 978-0123973375

https://www.amazon.com/Art-Multiprocessor-Programming-Revised-Reprint/dp/0123973376/

And actually, here's another because there's more to user-level mutexes as provided by an operating system than just using the hardware primitives. User-level mutexes are intimately tied to the operating system's scheduling algorithms.

Understanding the Linux Kernel Daniel P. Bovet, Marco Cesati ISBN-13: 978-0596005658

http://www.amazon.com/Understanding-Linux-Kernel-Third-Daniel/dp/0596005652/

Solomon Slow
  • 25,130
  • 5
  • 37
  • 57