How absl::Mutex's conditional critical sections handle reader wakeups

Question

I was wondering where it would be best to ask about something like this, so I asked this question on Meta (https://meta.stackexchange.com/questions/304981) and was directed here, so here goes.

I was really curious about what sort of optimizations were built into Google's implementation of conditional critical sections with absl::Mutex (https://github.com/abseil/abseil-cpp/blob/master/absl/synchronization/mutex.h). In particular i was wondering how they handle reader wakeups when a reader's condition becomes true. Do they wake up all the other readers in the wait list as well? This line seems to signal that they do.. Doesn't that risk an O(n) traversal each time and also risk thundering herds in a write priority mutex?

Answer 1

I think it is important to set out the differences between design and implementation optimization. It seems that absl:: gives priority to better design by providing an implementation that supports those designs, as opposed to providing better optimized components. Sometimes the better design is inherently better performing than the clumsier one, so the result is optimized on both factors (synergy). Absiel.io discusses this in greater detail.

From looking at their source, absl does not appear to attempt magic to avoid broadcasting to the pending readers, thus yes, the thundering herd remains an issue. In general, no implementation can address that problem in a meaningful way; it is a design problem.

By embedding the condition as part of the lock, absl: does permit the programmer to avoid, or design around, that problem. There is still a herd, but the lock implementation is able to thin it plan 9 nod here . If you design your reasons for awakening well, for example bits in a mask, you can safely use shared/exclusive locks without worrying about spurious wake-ups impacting your performance.

This is the essence of a ‘design optimization’: the problem is more explicitly described in the source and the resulting implementation is of higher quality (performance, scaling, ...) than otherwise.

Plan9. Condition variables are equivalent to the unix kernel notion of sleep ( not the time one ) and wakeup. When you detect that an object is not in the state you need, you perform some action to initiate bringing it to that state, then wait until that state is achieved. For example, you might lookup an object in a cache, and upon discovering it isn’t there, create an invalid one and request that it be made valid. This permits a sort of symmetry between all of the cache participants: they lock the object, evaluate or update its state, then simultaneously unlock the object and wait for further changes to it.

The ugly problem is that there is a: no such thing as simultaneously, and b: the lock handling is error prone (am I holding any other locks? can this lead to deadlock?) and not well expressed in the program. Plan9’s sleep and wakeup elegantly merged these, so that at the point where the condition is checked it is impossible for anybody to affect the object. In fact, the point of the referenced paper is how hard it is to enforce that simple contract. Complicated contracts in a multi processing environment are best avoided for example.

The critical optimization (in absl:) is that it is not necessary to go through the expensive context switch operation to determine that the object is in the wrong state, then go back to sleep. If the code that is choosing to wake you up can verify that the object state is one you are likely interested in, so much the better. A function call/method invocation is 100s of times faster than a context switch.

Absl This section addresses both how the candidates for wakeup are chosen, and how the herd is culled. This section produces the broadcast.

So the former section selects elements from the list waiters, and the latter section wakes them up. If you look at line 2203’s else condition, it shows how a writer will terminate the list -- w_walk->wake is not true, and wr_wait has been set. In addition, the earlier tests at 2015 and 2023 prevent building this list if it is a write-wakeup.

monitors

obj.enter();
while (obj.state != StateIWant) {
    obj.wait();
}
...
obj.exit();

Requires this thread to execute the guard condition. The action of moving this blocked thread may be 1000s of times the cost of executing the condition. In contrast:

obj.wait(^{return obj.state == StateIWant;});
...
obj.exit();

would permit the wait call to evaluate the condition in the context of whichever thread was permitting the wait (ie. calling exit), thus avoiding the expensive context switches in the useless cases.