Can someone please ELI5 what is a futex? Is it like a mutex?
Afaik, if locking a mutex succeeds, futexes avoid a context switch to and from the kernel. The fast path happens completely in userspace. Only when a mutex lock causes a thread to sleep, the kernel is needed. All of this improves mutex performance.
There are other locking primitives than mutexes, and the current futex interface is not optimal for implementing common windows ones. Hence this proposal.
This is a common misconception, a "context" switch is a lot more expensive than a "mode" switch that goes from user mode to the kernel mode (and back).
Of course, if the futex has to wait, it'd be a context switch for real.
>"Before the introduction of futexes, system calls were required for locking and unlocking shared resources (for example semop)."
>"A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true"
The first indicates futexes are an improvement because they avoid the overhead of system call but the second states that futex() is a system call.
Is this similar to how a vDSO or vsyscall works where a page from kernel address space is mapped into all users processes? In other words is it similar to how gettimeofday works?[1]
[1] https://0xax.gitbooks.io/linux-insides/content/SysCall/linux...
The userspace fast path can in principle be implemented on top of any kernel only synchronization primitive (a pipe for example).
The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls. Any kernel state is created lazily when needed (i.e on the first wait) and destroyed automatically when not needed (i.e. when the last waiter is woken up). Coupled with the minimal userspace space requirements (just a 32 bit word) it means that futexes can be embedded very cheaply in a lot of places.
>The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls.
This is an extremely interesting and useful observation, thank you for making it.
Futexes are missing a lot of useful functionality - see the OP, and as another example it's very hard to integrate them with an event loop - so I've been dreading building anything with them, but I thought I needed it to get fast synchronization. But for my use cases, I already have setup and teardown calls. Maybe I can do fast userspace synchronization on top of some other kernel object - a pipe, or something, as you suggest.
Do you have any more to share about this observation, or pointers to any implementations of fast userspace synchronization on top of something other than futexes?
But there isn't really ever a reason to mix futexes and event loops. Futexes are not a synchronization primitive, just a waiting strategy. Decouple the two and you can integrate your synchronization primitives with an event loop while still using futexes for the non event-loop cases.
I'm not sure what you mean, can you elaborate? Suppose I had a mutex (synchronization) implemented with a futex, and a shared memory queue (waiting) implemented with a futex; suppose both are being used to coordinate between multiple processes. I guess you're suggesting that one of those two doesn't need to be integrated with an event loop? But why? Both of those seem useful to have as part of an event loop.
You have two options: you can use an eventfd to implement the queue full/empty event, or provide a generic notification interface (i.e. a callback). Any non event loop users wiuld simply have the callback signal a futex, but it allows for more complex use case: obviously you can wakeup the event loop from the callback, but you could resume a coroutine, send an async signal or whatever makes sense for the application.
Thank you for pointing this out. That makes sense. This is sort of like the idea that the fastest system call is the one that is never made. Can you say how does something in userland know if something "would" block without actually crossing the user/kernel boundary? Does the kernel expose a queue length counter or similar via a read-only page?
But in the contended case the flag is already set by somebody else, so you leave a sign (maybe you set it to 42) about the contention in the memory address, and you tell the kernel that you're going to sleep and it should wake you back up once whoever is blocking you releases. When whoever was in there is done, they try to put things back to zero, but they discover you've left that sign that you were waiting, so they tell the kernel they're done with the address and it's time to release you.
None of the conventional semantics are enforced by the operating system. If you write buggy code which just scribbles nonsense on the magic flag location, your program doesn't work properly. Too bad. The kernel does contain some code that helps do some tricks lots of people want to do using futexes, and so for that reason you should stick to the conventions, but nobody will force you to.
>"When whoever was in there is done, they try to put things back to zero, but they discover you've left that sign that you were waiting, so they tell the kernel they're done with the address and it's time to release you.
Did you mean to say "and it's time to release to you" here?
>"None of the conventional semantics are enforced by the operating system"
Ah OK, this is the part that I feel is maybe always left out of the things I've read on futex(). I guess this is just always implied then that some library implements these semantics correctly? And that library is generally going to glibc?
Yup. For example, the pthread_foo functions are futexes under the hood.
The POSIX threading API accommodates many possible implementations, and so in Linux many of the bits that look expensive (and might be on other systems) are more or less free thanks to futexes, e.g. setting up the mutex in Linux is just allocating an aligned 32-bit value on the heap and setting it to some initialising value, but on some systems it involves an OS system call to get a mutex handle.
This is the true benefit of the futex. The typical scheme for using it looks almost exactly like a well known trick for speeding up conventional mutual exclusion features that have low contention, which you'd see in say BeOS as the Benaphore, or described in several books about high performance programming. But those tricks all imply the expense of first obtaining a handle from the operating system for every such mutex whereas with a futex that part is free and you only talk to the operating system at all once there is contention for it to help you manage.
Do you have any links that document this trick in Linux? Is there name for it or search term I could use to find out more?
https://www.haiku-os.org/legacy-docs/benewsletter/Issue1-26....
Note that when I say "typical scheme for using it" I did not mean, that your program should implement such a scheme itself, instead futex is intended for the sort of people who implement the concurrency features in your language or APIs to use - and this is how they'd go about doing that to deliver the features you just use. So, for most of us this is interesting to know about but unlikely to impact our day-to-day practice.
Fuss, Futexes, and Furwoks: Fast Userlevel Locking in Linux
https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pd...
Another great paper that came after some additional experience by glibc developers:
Futexes are Tricky, by Ulrich Drepper
I realize that one is userspace and the other kernel but would the above be the right mental model?
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.
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.
Please excuse my ignorance...
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...
"Detailed approach of the futex"