Was ist ein skalierbares Schloss?

Question

Was ist ein skalierbares Schloss? Und wie unterscheidet es sich von einem nicht skalierbaren Schloss? Ich habe diesen Begriff zum ersten Mal im Zusammenhang mit dem TBB rw-lock gesehen und konnte nicht entscheiden, welches ich verwenden soll.

Gibt es außerdem ein rw-lock, das Leser gegenüber Schreibern priorisiert?

Answer 1

Es gibt keine formale Definition des Begriffs "scalable lock" oder "non-scalable lock". Was damit gemeint ist, ist dass einige Sperralgorithmen, -techniken oder -implementierungen auch dann vernünftig funktionieren, wenn es zu viel Konkurrenz um das Schloss gibt, und einige nicht.

Manchmal liegt das Problem im Algorithmus. Eine naive Implementierung der Prioritätsererbung kann zum Beispiel O(n) Arbeit erfordern, um ein Schloss freizugeben, wobei n die Anzahl der wartenden Threads ist. Das bedeutet O(n^2) Arbeit für jeden wartenden Thread, der bedient wird.

Manchmal liegt das Problem am Hardware. Einfache Spinlocks (z.B. Implementierungen, bei denen die Lock-Cache-Zeile geteilt ist und die Erwerber nicht nachgeben) skalieren auf SMP-Hardware mit einem einzigen Bus-Verbindungsstück nicht, da das Schreiben in eine Cache-Zeile erfordert, dass die CPU die Cache-Zeile erwirbt und die CPU-Verbindungspunkt der Engpass ist. Wenn n CPUs versuchen, das gleiche Schloss zur gleichen Zeit zu erwerben, kann es zu O(n) Busverkehr kommen, um das Schloss zu erwerben. Wieder bedeutet das O(n^2) Zeit, bis alle n CPUs zufrieden gestellt sind.

Im Allgemeinen sollten Sie nicht-skalierten Sperren ausweichen, es sei denn, zwei Bedingungen sind erfüllt:

1. Die Konkurrenz ist gering.
2. Der kritische Abschnitt ist sehr kurz.

Sie müssen wirklich wissen, dass die beiden Bedingungen erfüllt sind. Ein kritischer Abschnitt kann kurz sein in Bezug auf Codezeilen, aber nicht kurz in Bezug auf die Wall-Zeit. Wenn Sie Zweifel haben, verwenden Sie ein skalierbares Schloss und beheben Sie später alle, die nachweislich Leistungsprobleme verursachen.

Was Ihre letzte Frage betrifft, bin ich nicht über ein Standard-Lese-Schreib-Schloss informiert, das Leser bevorzugt. Tatsächlich geben die meisten APIs keine Richtlinie vor, einschließlich pthreads (ärgerlicherweise).

Mein erster Kommentar ist, dass Sie es wahrscheinlich nicht wollen. Wenn Sie viele Konflikte haben, die eine Partei gegen die andere bevorzugen, verringert dies die Durchsatzleistung, und wenn Sie keine hohen Konflikte haben, macht es keinen Unterschied. Der einzige Grund, den ich mir vorstellen kann, kein rw-Schloss mit einer komplett fairen Richtlinie zu verwenden, ist, wenn Sie Thread-Prioritäten haben, die beachtet werden müssen, damit der Thread mit der höchsten Priorität bevorzugt wird.

Aber wenn Sie unbedingt möchten, können Sie auch Ihr eigenes erstellen. Alles, was Sie brauchen, sind ein paar Flags (eine für "Leser können jetzt gehen" und eine für "ein Schreiber kann jetzt gehen"), Bedingungsvariablen, die die Flags schützen, ein einzelnes Mutex, das die Bedingungsvariablen schützt, und ein paar Zähler, die anzeigen, wie viele Leser und Schreiber warten. Das sollte alles sein, was Sie brauchen; die Implementierung sollte recht lehrreich sein.