How does mutex lock work

Instantly share code, notes, and snippets. Last active May 2, Code Revisions 7 Stars 5 Forks 1. Embed What would you like to do? Embed Embed this gist in your website. Share Copy sharable link for this gist. Learn more about clone URLs. Download ZIP. What is a mutex and how does it work. What is a mutex and how does it work Imagine a big office your program , with many assets shared resources and many employees threads. So, in order to pee safely, the following rules must apply: Everybody who wants to pee, must check the label and enter only when it is "free" with setting the label to "engaged" simultaneously lock mutex.

Various operating systems diverge at this point, and will likely change as time goes on. Under Linux, there is a system call futex which provides mutex like semantics. If there is no contention, the call is resolved in userspace. If there is contention, the call is delegated to the OS to handle in a safe, albeit far costlier manner. The OS handles the waiting as part of the process scheduler. There are a few points of interest when it comes to the cost of a mutex.

The most vital point is the waiting time. Your threads should spend only a fraction of their time waiting on mutexes. If they are waiting too often, then you are losing concurrency. In a worst-case scenario many threads always trying to lock the same mutex may result in performance worse than a single thread serving all requests.

The overhead costs of a mutex relate to the test-and-set operation and the system call that implements a mutex. The test-and-set is likely a minuscule cost; being essential to concurrent processing, CPU vendors have a strong incentive to make it efficient. This is used in all high-level mutexes and may have a higher cost than the test-and-set operation.

Most costly however is the system call. Not only do you suffer the context switch overhead, the kernel now spends some time in its scheduling code. Categories: Efficiency , Programming. Tagged as: concurrency , concurrent programming , contention , cpu memory , critical data , efficiency , fundamental operations , linux , lock , mutex , Programming.

Thus, it gives great performance, without ending up in a long spin loop. They all handle contention poorly. Either they yield under contention with Sleep , meaning that they stay idle too long, or they spin in a busy loop for hundreds or thousands of milliseconds, wasting power and causing priority inversions.

Use the operating system primitives. A critical section is a bit higher level, but definitely useful in the same way.

However achieved, non-contention handled strictly in user-space is basically a requirement nowadays, otherwise safe threaded code is too slow. Both wasting resources and screwing up the memory visibility as you say.

The actual locking is handled by the OS. Thanks for the article, simple and helpful. I have a question, is it random choice, who will get the ownership, if couple or more threads are waiting on a lock mutex? A program must be designed to avoid contention, or in a queue-like system, just not care which thread awakes.

It should not rely on any fairness to the lock allocation. I have one question in regards to waiting scenario: If we want to use CAS instruction in User Space, then what is the harm if we: 1 Use counter in while loop, and yield CPU, if counter exceeds threshold value.

When we know that lock section may be bit big. I assume that price to pay is the context switch, but we can never avoid it, as we need CPU to have some useful work rather than waiting.

Spinning with a CAS is useful in some situations, and I did it on one of my projects. There are a couple things to note:. They are genrally only useful when you have threads that can a lot of processing without needing to otherwise wait.

One thread must release its mutexes when it discovers that deadlock would otherwise be inevitable. In Example , thread 1 locks mutexes in the prescribed order, but thread 2 takes them out of order. To make certain that there is no deadlock, thread 2 has to take mutex 1 very carefully; if it were to block waiting for the mutex to be released, it is likely to have just entered into a deadlock with thread 1.

If it is not, thread 2 returns immediately, reporting failure. At this point, thread 2 must release mutex 2, so that thread 1 can lock it, and then release both mutex 1 and mutex 2.

Example and Example show how to take three locks at once, but prevent deadlock by taking the locks in a prescribed order. This example uses a singly linked list structure with each node containing a mutex. To remove a node from the list, first search the list starting at ListHead which itself is never removed until the desired node is found.

In a well planned program contention should be quite low; you should be designing your code so that most attempts to lock the mutex will not block. There are two reasons why you want to avoid contention. The first is simply that any thread waiting on a mutex is obviously not doing anything else — possibly resulting in unused CPU cycles.

The second reason is more interesting for high performance code. Locking a currently unlocked mutex is extremely cheap compared to the contention case. We have to look at how the mutex works to understand why. As mentioned before, the data of a mutex is simply an integer in memory.

If you wish to lock the mutex you can simply check if it is zero and then assign one. The mutex is now locked and you are the owner of it. The trick is that the test and set operation has to be atomic. If two threads happen to read 0 at the exact same time, then both would write 1 and think they own the mutex. Without CPU support there is no way to implement a mutex in user space: this operation must be atomic with respect to the other threads. This function takes the address of the integer, and two integer values: a compare and set value.

If the compare value matches the current value of the integer then it is replaced with the new value. In C style code this might like look this:. The caller determines what happens by the return value. It is the value at the pointer provided prior to the swap.

If this value is equal to the test value the caller knows the set was successful.