3 ms·

>"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 multip

>"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 ago
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 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 ago
  Thanks for clarification and the examples. This makes sense. Cheers.

ww520 8y ago

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 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 ago
Thanks for clarification and the examples. This makes sense. Cheers.