Multiple locks and missing wakeup.

[Edward Tomasz Napierała]

Let's say I have a kernel thread processing elements from a queue,
sleeping until there is work to do; something like this:

mtx_lock(&mtx1);
for (;;) {
	while (!LIST_EMPTY(&list1)) {
		elt = LIST_FIRST(&list1);
		do_stuff(elt);
		LIST_REMOVE(&list1, elt);
	}
	sleep(&list1, &mtx1);
}
mtx_unlock(&mtx1);

Now, is there some way to make it work with two lists, protected
by different mutexes?  The mutex part is crucial here; the whole
point of this is to reduce lock contention on one of the lists.  The
following code would result in a missing wakeup:

mtx_lock(&mtx1);
for (;;) {
	while (!LIST_EMPTY(&list1)) {
		elt = LIST_FIRST(&list1);
		do_stuff(elt);
		LIST_REMOVE(&list1, elt);
	}

	mtx_lock(&mtx2);
	while (!LIST_EMPTY(&list2)) {
		elt = LIST_FIRST(&list2);
		do_other_stuff(elt);
		LIST_REMOVE(&list2, elt);
	}
	mtx_unlock(&mtx2);

	sleep(&list1, &mtx1);
}
mtx_unlock(&mtx1);