runtime: bound overtakes of lock2 sleepers #81968

The runtime.mutex implementation tracks sleeping Ms in a LIFO stack. In lock2, an M can push itself onto the stack right before going to sleep, and in unlock2's helper unlock2Wait the releasing M can obtain exclusive permission to pop entries off of that stack, pop an M, and wake it.

Dice and Kogan's Reciprocating Locks presents an alternative: the lock state tracks two LIFO stacks, the "arrival" stack and the "entry" stack. Threads in the slow path of lock add themselves to the "arrival" stack when they're ready to sleep. When a thread unlocks and sees that it needs to wake a waiter, it first tries popping one off of the "entry" stack. If that's empty, it grabs the entire "arrival" stack and installs it as the new "entry" stack, and then pops one off to wake.

That gives a bound to the number of times a sleeping thread can be overtaken by any other sleeping thread, which in turn (assuming, I suppose, a bounded number of threads at any moment) gives a bound on the total number of overtakes.

The design laid out in the paper doesn't allow barging. I think that for the runtime's general-purpose mutex we'll need to allow barging, even though it weakens the "FIFO in the long run" guarantee.

The runtime's general-purpose mutex should also continue to fit inside a single uintptr. I think we can make it work by hanging the "entry" stack off of the first entry in the "arrival" stack (and having unlock2Wake keep that up to date as new waiters arrive).

Overall, this may be able to reduce tail wait times and simplify the rules of unlock2Wake. (Today, we occasionally walk the entire list and wake the tail to reduce starvation.)

I plan to work on this for Go 1.28, though it's not yet at the top of my list and I haven't discussed yet with @golang/runtime . One of my first questions is probably "what's the rough deadline for a change like this, leading up to the release freeze".