3 ms·
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 wa
by ww520 8y ago
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.
- bogomipz 8y ago>"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?
- ww520 8y agoEssentially 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 https://news.ycombinator.com/item?id=17526849 [1] https://elixir.bootlin.com/linux/v4.18-rc4/source/kernel/futex.c#L1515 https://elixir.bootlin.com/linux/v4.18-rc4/source/kernel/fut...
- bogomipz 8y agoThanks for clarification and the examples. This makes sense. Cheers.