Rethinking the futex API

Posted Jun 23, 2020 22:01 UTC (Tue) by ras (subscriber, #33059)
In reply to: Rethinking the futex API by rweikusat2
Parent article: Rethinking the futex API

Thanks for that.

My point wasn't that thundering herd isn't a problem. It clearly is.

My point was that it is already solved by the current futex() API. You get to decide how many of those syscall(SYS_futex, &futex, FUTEX_WAIT)'s you wake up. It can be anywhere from 1 to all. The others just sit around, waiting for another FUTEX_WAKE.

To solve the pthread_cond_wait() case you just wake up one, so it could have been done without REQUEUE now. I'll grant you that not all that REQUEUE does, it also prevents the futex from seeing any future wakeups. But that could equally well be done from userspace using more futex's. Perhaps it's a speed optimisation (I do hope they benchmarked it), or more likely arranging or everyone to share information the kernel already had was hard so they took the easy way out.

Rethinking the futex API

Posted Jun 24, 2020 14:54 UTC (Wed) by rweikusat2 (subscriber, #117920) [Link] (1 responses)

The library implementation doesn't get to decide this: Application code can either use pthread_cond_signal to wake exactly on thread or pthread_cond_broadcast to wake all threads. With the naive implementation, the kernel goes through a linked list and wakes everything while tearing the list apart. All the awoken threads exit the kernel and compete for ownership of the same mutex. One of these threads will end up getting the mutex, the others all do system calls in order to enter the kernel again where kernel code than builds a new linked list of them which is attached to a different futex.

That's an insanely complicated way to transfer a linked list from a head pointer a in the kernel to another head pointer b in the kernel. It's much simpler if the kernel just wakes one thread and transfers the existing list to the other futex.

Rethinking the futex API

Posted Jun 24, 2020 19:17 UTC (Wed) by itsmycpu (guest, #139639) [Link]

> That's an insanely complicated way to transfer a linked list from a head pointer a in the kernel to another head pointer b in the kernel. It's much simpler if the kernel just wakes one thread and transfers the existing list to the other futex.

I'm not sure if you are discussing a more specific question, but just to point it out, for example a user space implementation of the producer/consumer model can (if so designed) just move a waiting entry from one producer's list to another producer's list without any wake ups or even kernel calls. (Except a wake call in the case one is ready.)