11 ms·

Can someone please ELI5 what is a futex? Is it like a mutex?

hulitu 5y ago
As far as i remember a futex is a fast mutex
corbet 5y ago
See https://lwn.net/Articles/823513/ https://lwn.net/Articles/823513/ for a look at both the old and proposed new futex interfaces.
achernya 5y ago
futex is a Fast Userspace muTEX. It's the syscall to help implement a mutex when there are two or more threads waiting on the lock to let other processes/threads schedule and do useful work during the wait.
hyperman1 5y ago
Futex stands for fast userspace mutex. It is a basic building block for implementing a mutex (amongst others). 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.
- xxs 5y ago
  >"context switch to and from the kernel" 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.
- ece 5y ago
  ESYNC is the way this is currently done, it's hit and miss in that it doesn't work unless the number of open files is set high enough for some games. It's also slower than this proposal.
- deleted 5y ago
  [deleted]
gpderetta 5y ago
A futex is an ephemeral list of waiting threads or processes keyed on an address. It can be used to implement any synchronization or signaling primitive, like mutexes, condition variables, semaphores, etc.
- tialaramex 5y ago
  This is a really nice insight into the kernel's model of what's going on. It's probably not the best way for an absolute beginner to think about why they want this, but it's much better than some of the other explanations if you have trickier technical or performance questions, and it makes it obvious why it's clever and why you need the OS kernel to actually implement it.
whoisburbansky 5y ago
It's a primitive that lets you build mutexes; you've got an atomic integer in userspace, attached to a wait queue in kernel space. Eli Bendersky has a pretty good rundown: https://eli.thegreenplace.net/2018/basics-of-futexes/ https://eli.thegreenplace.net/2018/basics-of-futexes/
- bogomipz 5y ago
  This is a good post thanks. One thing confuses me is that these two sentences seem to contradict each other: >"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-syscall-3.html https://0xax.gitbooks.io/linux-insides/content/SysCall/linux...
  - kccqzy 5y ago
    It's not a contradiction. The two sentences are perfectly clear to me. Of course futex() is itself a system call, but in case of no contention you don't need to invoke the system call. That's why futex() is an improvement. The key phrase is "only when" in the second sentence.
    - gpderetta 5y ago
      IMHO The nice thing about futexes is not that they allow to fast path uncontended sinchronization. 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.
DSingularity 5y ago
Okay, consider a multi-threaded program. These programs have multiple threads running on multiple cores. Sometimes you want to coordinate the execution of multiple threads in such programs. A common example is when a thread is in a "critical section" where it is only safe for one thread to access/modify state. Sometimes threads will have to wait for each other. This is where the futex comes in. Instead of the thread to wait while using the processor it can tell the OS that it needs to wait for this futex to become free. The OS will then suspend the thread and find another one to schedule in its place.
- bogomipz 5y ago
  Ah Interesting. So is the concept of futex() similar to how a process in kernel mode will yield the CPU by putting itself on a wait_queue and call the schedule() function before it issues an I/O request then? I realize that one is userspace and the other kernel but would the above be the right mental model?
  - gpderetta 5y ago
    Yes, a futex is basically a waitqueue abstraction coupled with a TOCTOU guard.
ROARosen 5y ago
Can someone please ELI5 what is a mutex?
- marcodiego 5y ago
  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.
- __init 5y ago
  (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.
Iwan-Zotow 5y ago
it is thing behind/inside mutex. It is making uncontested mutex acquire/release ops pure userspace thingy.
brandmeyer 5y ago
The best introduction is probably the original presentation paper from 2002. Fuss, Futexes, and Furwoks: Fast Userlevel Locking in Linux https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf 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 https://www.akkadia.org/drepper/futex.pdf https://www.akkadia.org/drepper/futex.pdf
- MaxBarraclough 5y ago
  I see Drepper resisted the urge to pluralise futex to futices.
bogomipz 5y ago
I just found this article which I think is really helpful as it has some good historical context as well: "Detailed approach of the futex" http://www.rkoucha.fr/tech_corner/the_futex.html http://www.rkoucha.fr/tech_corner/the_futex.html

As far as i remember a futex is a fast mutex

See https://lwn.net/Articles/823513/ https://lwn.net/Articles/823513/ for a look at both the old and proposed new futex interfaces.

achernya 5y ago

futex is a Fast Userspace muTEX. It's the syscall to help implement a mutex when there are two or more threads waiting on the lock to let other processes/threads schedule and do useful work during the wait.

hyperman1 5y ago

Futex stands for fast userspace mutex. It is a basic building block for implementing a mutex (amongst others). 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.

xxs 5y ago
>"context switch to and from the kernel" 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.
ece 5y ago
ESYNC is the way this is currently done, it's hit and miss in that it doesn't work unless the number of open files is set high enough for some games. It's also slower than this proposal.
deleted 5y ago
[deleted]

gpderetta 5y ago

A futex is an ephemeral list of waiting threads or processes keyed on an address. It can be used to implement any synchronization or signaling primitive, like mutexes, condition variables, semaphores, etc.

tialaramex 5y ago
This is a really nice insight into the kernel's model of what's going on. It's probably not the best way for an absolute beginner to think about why they want this, but it's much better than some of the other explanations if you have trickier technical or performance questions, and it makes it obvious why it's clever and why you need the OS kernel to actually implement it.

whoisburbansky 5y ago

It's a primitive that lets you build mutexes; you've got an atomic integer in userspace, attached to a wait queue in kernel space. Eli Bendersky has a pretty good rundown: https://eli.thegreenplace.net/2018/basics-of-futexes/ https://eli.thegreenplace.net/2018/basics-of-futexes/

bogomipz 5y ago
This is a good post thanks. One thing confuses me is that these two sentences seem to contradict each other: >"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-syscall-3.html https://0xax.gitbooks.io/linux-insides/content/SysCall/linux...
- kccqzy 5y ago
  It's not a contradiction. The two sentences are perfectly clear to me. Of course futex() is itself a system call, but in case of no contention you don't need to invoke the system call. That's why futex() is an improvement. The key phrase is "only when" in the second sentence.
  - gpderetta 5y ago
    IMHO The nice thing about futexes is not that they allow to fast path uncontended sinchronization. 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.

DSingularity 5y ago

Okay, consider a multi-threaded program. These programs have multiple threads running on multiple cores. Sometimes you want to coordinate the execution of multiple threads in such programs. A common example is when a thread is in a "critical section" where it is only safe for one thread to access/modify state. Sometimes threads will have to wait for each other. This is where the futex comes in. Instead of the thread to wait while using the processor it can tell the OS that it needs to wait for this futex to become free. The OS will then suspend the thread and find another one to schedule in its place.

bogomipz 5y ago
Ah Interesting. So is the concept of futex() similar to how a process in kernel mode will yield the CPU by putting itself on a wait_queue and call the schedule() function before it issues an I/O request then? I realize that one is userspace and the other kernel but would the above be the right mental model?
- gpderetta 5y ago
  Yes, a futex is basically a waitqueue abstraction coupled with a TOCTOU guard.

ROARosen 5y ago

Can someone please ELI5 what is a mutex?

marcodiego 5y ago
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.
__init 5y ago
(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.

Iwan-Zotow 5y ago

it is thing behind/inside mutex. It is making uncontested mutex acquire/release ops pure userspace thingy.

brandmeyer 5y ago

The best introduction is probably the original presentation paper from 2002. Fuss, Futexes, and Furwoks: Fast Userlevel Locking in Linux https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf 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 https://www.akkadia.org/drepper/futex.pdf https://www.akkadia.org/drepper/futex.pdf

MaxBarraclough 5y ago
I see Drepper resisted the urge to pluralise futex to futices.

bogomipz 5y ago

I just found this article which I think is really helpful as it has some good historical context as well: "Detailed approach of the futex" http://www.rkoucha.fr/tech_corner/the_futex.html http://www.rkoucha.fr/tech_corner/the_futex.html