Basics of Futexes

Re:Basics of Futexes by ww520 on Friday July 13, 2018 @04:42PM (#17526518)

One thing important to remember about futex is that it is not a lock, despite its name similar to mutex. Futex is a conditional sleep mechanism. The kernel wakes up the caller when the futex flag's state changes. When awaken and returns from the futux() call, you don't get the lock. It just means the state of the lock has changed and it's time to check and attempt to acquire the lock again. Actually multiple threads sleeping on the futex flag can be awaken at the same time (depending on the FUTEX_WAKE command's parameter). All of them need to do compare-and-set to acquire the lock.

[ Parent | on HN ]

Re:Basics of Futexes by bogomipz on Friday July 13, 2018 @05:17PM (#17526770)

>"When awaken and returns from the futux() call, you don't get the lock.

Can you elaborate on this? That sentence isn't reading well for me.

>"Actually multiple threads sleeping on the futex flag can be awaken at the same time (depending on the FUTEX_WAKE command's parameter). All of them need to do compare-and-set to acquire the lock."

So whatever thread kernel schedules first will get the lock? I.e there is no fairness or weighting? Does this potentially cause a "thundering heard" when they're awakened at the same time?

[ Parent | on HN ]

Re:Basics of Futexes by ww520 on Friday July 13, 2018 @05:34PM (#17526917)

Essentially to implement a lock in the user mode, you do:

    while !compare_and_swap(&flag,0,1) // check if flag is free (0), lock it (1)
        futex_wait(&flag,0)            // sleep until flag changes

When futex_wait() returns, it just means the flag has been set back to 0 and the kernel wakes me up so I can check on it again. Another thread can come in and grab the lock in the meantime. That's why I need to loop back to check again. The atomic CAS operation is the one doing the lock.

In the old days, it's just a busy loop running the CAS check continually which is expensive.

    while !compare_and_swap(&flag, 0, 1)
        // busy loop running

With futex(), the lock-acquiring threads can go to sleep and waking up with the help of the kernel.

Yes, multiple threads can be wakened up, the nr_wake parameter in futex_wake [1] dictates how many threads to wake up. Yes, you can get a "thundering herd" problem. For fairness, see priority usage in my other comment https://news.ycombinator.com/item?id=17526849

[1] https://elixir.bootlin.com/linux/v4.18-rc4/source/kernel/fut...

[ Parent | on HN ]

Re:Basics of Futexes by bogomipz on Friday July 13, 2018 @06:55PM (#17527568)

Thanks for clarification and the examples. This makes sense. Cheers.

[ Parent | on HN ]