Warum sind die meisten Mutex-Implementierungen unfair?

Mein Verständnis ist, dass die gängigsten Implementierungen eines Mutex (z. B. std :: mutex in C ++) keine Fairness garantieren - das heißt, sie garantieren nicht, dass in Streitfällen die Sperre von Threads in der Reihenfolge erworben wird, in der sie sich befinden genannt lock (). Tatsächlich ist es sogar möglich (wenn auch hoffentlich ungewöhnlich), dass einige der Threads, die darauf warten, den Mutex zu erwerben, ihn in Fällen hoher Konflikte möglicherweise nie erwerben.

Dies scheint mir ein nicht hilfreiches Verhalten zu sein - es scheint mir, dass ein fairer Mutex ein Verhalten ergeben würde, das eher dem entspricht, was ein Programmierer möchte / erwartet.

Der Grund dafür, warum Mutexe normalerweise nicht als fair implementiert werden, ist "Leistung", aber ich möchte besser verstehen, was dies bedeutet - insbesondere, wie die Lockerung der Fairness-Anforderungen des Mutex die Leistung verbessert? Es scheint, als wäre die Implementierung eines "fairen" Mutex trivial. Lassen Sie einfach lock () den aufrufenden Thread an das Ende der verknüpften Liste des Mutex anhängen, bevor Sie den Thread in den Ruhezustand versetzen, und lassen Sie Unlock () den nächsten Thread aus der Kopf der gleichen Liste und wecken Sie es auf.

Welche Erkenntnisse zur Mutex-Implementierung fehlen mir hier, um zu erklären, warum es als sinnvoll erachtet wurde, Fairness für eine bessere Leistung zu opfern?

Jim Sawyers Antwort zeigt auf eine Antwort: Wenn Sie Threads mit unterschiedlichen Prioritäten haben, wäre "faires" Verhalten falsch. Wenn Sie mehrere Threads haben, die ausgeführt werden könnten, sollte der Thread mit der höchsten Priorität im Allgemeinen ausgeführt werden.

Es gibt jedoch ein wenig diskutiertes Geheimnis der Betriebssystemimplementierung, das Sie beachten sollten: Gelegentlich führen Betriebssysteme Code als Benutzer aus, indem sie einen Benutzer-Thread entführen. Aus Sicherheitsgründen tun dies die meisten Betriebssysteme nur, wenn ein Thread blockiert ist. Wenn das Betriebssystem fertig ist, wird der Thread erneut angehalten. Dies hat normalerweise den Effekt, dass der Thread in den hinteren Bereich der Warteschlange verschoben wird.

Ein typisches Beispiel ist ein Signalhandler unter Unix, ein asynchroner System-Trap in VMS oder ein asynchroner Prozeduraufruf in Windows NT. Dies ist im Wesentlichen alles dasselbe: Das Betriebssystem muss den Benutzerprozess über das Eintreten eines Ereignisses informieren, und dies wird durch Ausführen von Code im Benutzerbereich behandelt.

Viele Betriebssystemdienste wie asynchrone E / A werden häufig zusätzlich zu dieser Funktion implementiert.

Ein weiteres Beispiel ist, wenn der Prozess von einem Debugger gesteuert wird. In diesem Fall kann das Debugging-System aus verschiedenen Gründen Code als Benutzeraufgabe ausführen.

"Prioritätsumkehrung" ist ein Grund dafür, dass Fairness unerwünscht sein kann. Ein Prozess mit niedriger Priorität trifft den gesperrten Mutex und schläft. Dann trifft es ein Prozess mit höherer Priorität und schläft auch. Wenn der Mutex entsperrt wird, welcher Prozess sollte als nächstes die Sperre erhalten?

Ein fairer Mutex verbringt mehr Zeit seines Lebens als ein unfairer Mutex, wenn alle anderen gleich sind. Weil ein Thread, der einen unfairen Mutex freigibt, ihn immer einfach entsperren kann. Ein Thread, der einen fairen Mutex freigibt, kann ihn jedoch nur entsperren, wenn die Warteschlange des Kellners leer ist. Andernfalls muss der Freigabe-Thread den Mutex für den nächsten Thread, auch bekannt als der erste Thread in der Kellner-Warteschlange, gesperrt lassen, der dann aus der Warteschlange entfernt und aktiviert wird. Der Mutex bleibt mindestens so lange gesperrt, bis der neu aufgeweckte Thread auf einer CPU geplant ist. Dies kann lange dauern, wenn viele aktuell ausführbare Threads vorhanden sind.

Und wenn der Freigabe-Thread sofort versucht, denselben Mutex wiederzugewinnen, muss er sich hinten in der Warteschlange des Kellners befinden und schlafen gehen. Dies wäre nicht geschehen, wenn der Thread den Mutex nicht von Anfang an freigegeben hätte. Dies ist daher ein Anreiz für längere "gierigere" kritische Abschnitte.