How are mutexes implemented?

Are some implementations better than others for specific applications? Is there anything you can earn by rolling out on your own?

+53
language-agnostic concurrency mutex
Sep 28 '09 at 8:01
source share
6 answers

Check out Wikipedia's description of the machine instruction Test-and-set , which talks about how atomic operations are performed at the machine level. I can imagine that most language-level mutex implementations are based on machine-level support, such as Test-and-set.

+29
Sep 28 '09 at 8:12
source share

Based on Adamsky’s test-and-set proposal, you should also take a look at the concept of “fast user space mutexes” or futexes .

Futexes have the desired property that they do not require a system call to the kernel in normal cases of locking or unlocking an uncontrolled mutex. In these cases, the user mode code successfully uses the atomic comparison and swap (CAS) operation to lock or unlock the mutex.

If CAS fails, the mutex is approved, and the kernel system call - sys_futex on Linux - must be used either to wait for the mutex (in case of blocking), or to wake up other threads (in case of unlocking).

If you are serious about implementing this yourself, make sure you also read the Ulrich Drepper paper .

+22
Oct 14 '09 at 17:05
source share

A mutex preferably works in the kernel of the operating system, while maintaining the amount of code around it as short as possible, so you can avoid being disconnected when switching tasks to another process. The exact implementation is therefore a bit secret. It's not hard. This is basically an object that has a logical field that it receives and sets.

  • When using a counter, it can become a semaphore.
  • A mutex is the starting point for a critical section that internally uses the mutex to see if it can enter the code section. If the mutex is free, it installs the mutex and executes the code, but only when the mutex is disabled. When a critical section notices that a mutex is locked, it may wait for the mutex to exit.

There are wrappers around the underlying mutex logic to wrap it in an object. Then add more wrapper objects so that they are accessible outside the kernel. And then another shell to make it available in .NET. And then several programmers will write their own wrapper code around all this for their own logical needs. The wrappers around the wrappers really make them a muddy territory.

Now, with this basic knowledge of the internal elements of the mutexes, I hope that you are going to use one implementation that relies on the kernel and the hardware underneath. They would be the most reliable. (If the hardware supports them.) If the mutex that you use does not work at this kernel / hardware level, it may still be reliable, but I would advise against using it if there is no alternative.

As far as I know, Windows, Linux and .NET will use kernel / hardware level mutexes.

The Wikipedia page I linked to explains more about internal logic and possible implementations. Preferably, the mutex is controlled by hardware, thereby doing all the reception / tuning of the mutex . (Just to make sure the system does not switch intermediate tasks).

+9
Sep 28 '09 at 8:52
source share

Interlocked.CompareExchange enough to implement spindlock. Although it is quite difficult to do it right. See Joe Duffy's Blog for an example of the intricacies involved.

+2
Sep 28 '09 at 8:33
source share

A bit of assembly to demonstrate atomically locking:

 ; BL is the mutex id ; shared_val, a memory address CMP [shared_val],BL ; Perhaps it is locked to us anyway JZ .OutLoop2 .Loop1: CMP [shared_val],0xFF ; Free JZ .OutLoop1 ; Yes pause ; equal to rep nop. JMP .Loop1 ; Else, retry .OutLoop1: ; Lock is free, grab it MOV AL,0xFF LOCK CMPXCHG [shared_val],BL JNZ .Loop1 ; Write failed .OutLoop2: ; Lock Acquired 
+1
Jan 02 '19 at 9:06
source share

I used Reflector.NET to decompile the source for System.Threading.ReaderWriterLockSlim , which was added to a recent version of the .NET framework.

It mainly uses Interlocked.CompareExchange , Thread.SpinWait and Thread.Sleep to achieve synchronization. There are several instances of EventWaitHandle (the kernel object) that are used in some circumstances.

Also added some complexity to support re-allocation in a single thread.

If you are interested in this area and work in .NET (or at least you can read it), you might find it rather interesting to check this class.

-one
Sep 29 '09 at 7:38
source share



All Articles