You can assume in SVR4, in the wake_one case, that you will be the only process awake, and so your acquisition will not be contested, and will not result in a sleep.

Logically, you can consider that there is one waiter and N-1 sleepers for every N processses trying to acquire a mutex.

This is normally handled [in the literature] by using a hybrid lock in a hierarchy.

That is, you attempt a fast lock, and if that fails, then you attempt a slow ("sleeping") lock. You are guaranteed a wakeup on release of a fast lock, and on release of a sleeping lock, so it's sixes,

Of course, it's a lot easier to just critical section.

Effectively, condition variables are critical sectioned in their manipulation through the use of a mutex.

In practice, there are some ugly areas in the Solaris SMP reentrant VFS code that necessitate trating the cond variable as if it were a mutext on a larger structure. This reduces concurrency considerably.

The main point about wake_one that's problematic is the deadly embrace deadlock, not the priority inversion deadlock, which can always be "opted out of" by lending (or making the wake_one more choosy about who it wakes, above and beyond the head of the wait queue).

The thing that makes a thundering herd expensive is less the herd than it is the traversal of the list; think about it: if I have the cycles to burn in the scheduler to pick someone to run, then I wasn't doing important other work anyway, and I might as well burn them in the herd, as opposed to other places I could burn them.

A spinlock fixes this by implementing back-off + retry, at least for sets of two locks. Sets of more locks are really problematic.

A lot of work was done in SVR4 ES/MP to, effectively, resolve the problem using Djikstra's "Banker's Algorithm" (that is, all the resources for sets of greater than two members, and in some cases, one member -- usually parent directory in a descending path lookup -- are allocated "up front", which is to say "at the same stack depth/in the same function" to permit state to be backed out easily in the case of a deadlock detection).

This stuff is really unsatisfying from the point of view of someone trying to write a reentrant ("kernel thread safe" or "kernel preemption safe") VFS provider of some kind, since it's really hard to know when the semantics applied by an upper level function might result in a problem. Other subsystems have similar issues, but most of my experience was with VFS providers, so I can't give you the PCMCIA device attach issues in SVR4 (maybe we can track down Kurt Mahon, though).

To Unsubscribe: send mail to majo...@FreeBSD.org with "unsubscribe freebsd-smp" in the body of the message