4 ms·

>'The key phrase is "only when" in the second sentence' Thank you for pointing this out. That makes sense. This is sort of like the idea that the fastest syst

>'The key phrase is "only when" in the second sentence' 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?

kccqzy 6y ago
The most common implementation of mutexes using futex() is that the userland simply spins a while waiting to acquire the mutex (just atomic operations, no system call). After a while the userland gives up spinning and makes the system call.
- bogomipz 6y ago
  Thanks this implementation detail is helpful. Cheers.
tialaramex 6y ago
The trick is, the memory address futex cares about is how you signal. Normally, in the "uncontended" case, everybody involved uses atomic memory access to manipulate this memory location (for example they set it to 1 as a flag to say somebody is in the mutually excluded code and then back to zero to say now nobody is in there) and they pay no kernel cost at all for this feature. The kernel has no idea the memory is even special. 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.
- bogomipz 6y ago
  Thanks for this insight. A couple quick questions: >"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?
  - jesboat 6y ago
    > 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.
    - tialaramex 6y ago
      On Linux. 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.
      - bogomipz 6y ago

kccqzy 6y ago

The most common implementation of mutexes using futex() is that the userland simply spins a while waiting to acquire the mutex (just atomic operations, no system call). After a while the userland gives up spinning and makes the system call.

bogomipz 6y ago
Thanks this implementation detail is helpful. Cheers.

tialaramex 6y ago

The trick is, the memory address futex cares about is how you signal. Normally, in the "uncontended" case, everybody involved uses atomic memory access to manipulate this memory location (for example they set it to 1 as a flag to say somebody is in the mutually excluded code and then back to zero to say now nobody is in there) and they pay no kernel cost at all for this feature. The kernel has no idea the memory is even special. 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.

bogomipz 6y ago
Thanks for this insight. A couple quick questions: >"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?
- jesboat 6y ago
  > 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.
  - tialaramex 6y ago
    On Linux. 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.
    - bogomipz 6y ago