News for hackers. Stuff that matters.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by ROARosen on Wednesday April 28, 2021 @10:18AM (#26969642)
Can someone please ELI5 what is a mutex?
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by __init on Wednesday April 28, 2021 @10:42AM (#26969915)
(Edited because I transposed "mutex" and "semaphore" in my mind.)

A mutex is a lock -- if multiple users attempt to access a resource simultaneously, they each attempt to acquire the lock serially, and those not first are excluded (blocked) until the current holder releases the lock.

Mutexes are typically implemented with semaphores:

First a more developer-oriented explanation (because I imagine that's what you really want):

A semaphore locks a shared resource by implementing two operations, "up" and "down". First, the semaphore is initialized to some positive integer, which represents how many concurrent "users" (typically threads) can use that resource. Then, each time a user wants to take advantage of that resource, it "down"s the semaphore , which atomically subtracts one from the current value -- but the key is that the semaphore's value can _never_ be negative, so if the value is currently zero, "down"ing a semaphore implies blocking until it's non-zero again. "Up"ing is just what you'd imagine: atomically increment the semaphore value, and unblock someone waiting, if necessary.

Semaphores are generally seen as a fundamental primitive (one reason being that locks/mutexes can be implemented trivially as a semaphore initialized to one), but they also have broad use as a general synchronization mechanism between threads.

For a true ELI5 of semaphores (I enjoy writing these):

Imagine everyone in class needs to write something, but there are only three pencils available, so you devise a system (a system of mutual exclusion, per se) for everyone to follow while the pencils are used: First, you note how many pencils are available -- three. Then, each time someone asks you for one, (which we call "down"ing the semaphore) you subtract one from the number in your head and give them a pencil. But if that number is zero, you don't have any pencils left, so you ask the person to wait. When someone returns and is done with their pencil, you hand it off to someone waiting, or, if nobody is waiting, you add one to that number in your head and take the pencil back ("up"ing the semaphore). It's important that you decide to only handle one request at a time (atomicity) -- if you tried to do too many things at once, you might lose track of your pencil count and accidentally promise more pencils than you have.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by MayeulC on Wednesday April 28, 2021 @11:04AM (#26970192)
> First, you note how many pencils are available -- three. Then, each time someone asks you for one, (which we call "down"ing the mutex) you subtract one from the number in your head and give them a pencil

Isn't that a semaphore rather than a mutex?

For ELI5 on semaphores, it's like going at the train station, airport, or Mc Donald's: There is a single queue for multiple counters. Everyone is given a paper with a number, and once a counter is free, the one with the lowest number can walk to it. A semaphore is just the number of free counters, it decreases when someone goes to one, and increases when one leaves. If the semaphore is zero, there is no free spot, and people will have to queue.

It's quite close to another synchronization primitive, barriers: if you have to wait for n tasks to finish, you make one with n spots, and release everyone when all the spots are filled.

To me, mutexes are semaphores, but with only one counter: there is only exactly one or zero resources available. If you take the mutex, others will have to wait for you to be done before they can take it. They can queue in any fashion, depending on the implementation: first come, first served; fastest first; most important first; random; etc.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by __init on Wednesday April 28, 2021 @11:36AM (#26970585)
Oh no, you're absolutely right. My sleep-deprived brain has confused the names -- thanks for the heads up. I'll edit my post.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by e_proxus on Wednesday April 28, 2021 @03:24PM (#26973067)
But it can’t be turtles all the way down? Isn’t a semaphore counter also shared state that needs to be protected if several threads want to “down” the value? Can it become negative?
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by gpderetta on Wednesday April 28, 2021 @03:41PM (#26973245)
Well at the bottom of the turtle stack you have harware primitives that guarantee atomicity of a bunch of word sized arithmetic operations (at the minimum CAS or LL/SC).
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by ROARosen on Wednesday April 28, 2021 @12:41PM (#26971359)
Thanks, great analogue there, it really helped it 'click'!

Please excuse my ignorance...

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by marcodiego on Wednesday April 28, 2021 @10:23AM (#26969700)
Mutex is named after "mutual exclusion" a primitive that is used to guarantee that some parts of code will run exclusively, never at the same time. This is important for good performance and synchronization on multiple threaded programs.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by hyperman1 on Wednesday April 28, 2021 @01:05PM (#26971655)
A mutex is the software equivalent of the lock on your toilet door. There is a zone in your code where only 1 thread at a time is allowed. So before entering, you lock the mutex. Now either you are allowed in or are added to a set of waiters. When you leave, you unlock the mutex, and 1 other waiter is allowed to enter.

This sounds easy, but is in practice wrought eith peril. You need high performance, not waste too much cpu time on sleepers, some notion of fairness when you have lots of waiters, minimal memory usage, etc...

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by xxs on Wednesday April 28, 2021 @04:12PM (#26973612)
My ELI5 version of that locking mechanism, e.g. mutex, uses a toilet and the disaster if multiple people try taking the dump at the same time.