Was war der `FUTEX_REQUEUE` Fehler?

Question

Ich ordne die Linux FUTEX(2) Manpage wie erforderlich in Betriebssystemklassen zu lesen, als eine Warnung an die Schüler nicht selbstgefällig beim Entwurf von Synchronisations-Primitiven zu bekommen.

Der Systemaufruf futex() ist die API, die Linux bereitstellt, um Benutzern auf Thread-Synchronisationsbasiselementen zu ermöglichen, zu schlafen und bei Bedarf aufzuwachen. Die Manpage beschreibt die 5 verschiedenen Operationen, die mit dem Systemaufruf futex() aufgerufen werden können. Die zwei grundlegenden Operationen sind FUTEX_WAIT (die ein Thread verwendet, um sich in den Ruhezustand versetzen, wenn es versucht, ein Synchronisierungsobjekt zu erwerben und jemand hält es bereits) und FUTEX_WAKE (die ein Thread verwendet, um alle wartenden Threads aufzuwachen, wenn es eine Synchronisierung freigibt Objekt.)

Die nächsten drei Operationen sind, wo der Spaß beginnt. Die Manpage Beschreibung lautet wie folgt:

FUTEX_FD (present up to and including Linux 2.6.25) 
     [...] 
     Because it was inherently racy, FUTEX_FD has been removed 
     from Linux 2.6.26 onward. 

Das Papier "Futexes are Tricky" by Ulrich Dreper, 2004 beschreibt die Race-Bedingung (es ist ein Potential verpaßt Wakeup). Aber es gibt noch mehr:

FUTEX_REQUEUE (since Linux 2.5.70) 
     This operation was introduced in order to avoid a 
     "thundering herd" effect when FUTEX_WAKE is used and all 
     processes woken up need to acquire another futex. [...] 

FUTEX_CMP_REQUEUE (since Linux 2.6.7) 
     There was a race in the intended use of FUTEX_REQUEUE, so 
     FUTEX_CMP_REQUEUE was introduced. [...] 

Was war das Rennen in FUTEX_REQUEUE? Ulrichs Papier erwähnt es nicht einmal (das Papier beschreibt eine Funktion futex_requeue(), die unter Verwendung FUTEX_CMP_REQUEUE implementiert wird, aber nicht die FUTEX_REQUEUE Operation).

Answer 1

Es scheint, als ob die Race Condition durch die Implementierung von Mutex in Glibc und ihre Disparität mit Futexen verursacht wird. FUTEX_CMP_REQUEUE scheint nötig zu sein, um die komplizierteren glibc mutexes zu unterstützen:

Sie sind viel komplexer, weil sie viele weitere Funktionen, wie zum Beispiel Tests für Deadlock und rekursive Verriegelung unterstützen. Aus diesem Grund haben sie eine interne Sperre, die den zusätzlichen Zustand schützt. Diese zusätzliche Sperre bedeutet, dass sie die Multiplexfunktion FUTEX_REQUEUE aufgrund eines möglichen Rennens nicht verwenden können.

Quelle: http://locklessinc.com/articles/futex_cheat_sheet/