Ich untersuche die verschiedenen Arten von Speicherwiederherstellungsstrategien für blockierungsfreie Datenstrukturen in einer nicht-garbage-collected-Umgebung (wie C oder C ++).
In meinen Experimenten habe ich einige dieser Strategien erfolgreich umgesetzt - insbesondere sowohl die ruhende zustandsbasierte Reklamation (QSBR) als auch die epochebasierte Reklamation (EBR).
Meine Frage betrifft einen der Hauptunterschiede zwischen diesen beiden Strategien.
Erstens bin ich mir bewusst, wie sowohl QSBR als auch EBR funktionieren, und habe beide Strategien erfolgreich umgesetzt. QSBR und EBR sind sich tatsächlich sehr ähnlich. Beide sind Deferred Reclamation -Strategien - das heißt, sie vermeiden Race Conditions bei der Freigabe von Speicher durch einfaches Verschieben der tatsächlichen Freigabe, bis es bewiesen werden kann, dass es sicher ist, die Zuordnung des Speichers aufzuheben . Sowohl mit QSBR als auch mit EBR wird dies durch Verwendung eines globalen "Epochenzählers" und dann verschiedener thread-lokaler Epochenzähler für jeden beteiligten Thread erreicht.
Der Hauptunterschied zwischen QSBR und EBR besteht darin, dass Sie mit QSBR grundsätzlich angeben, wann ein Thread nicht Referenzen auf freigegebene Daten hat. Mit EBR geben Sie an, wenn ein Thread einen Verweis auf freigegebene Daten hat. In der Praxis sieht also Code, der EBR verwendet, eher wie ein herkömmlicher Mutex-Sperr- / Entsperr-Abschnitt aus, wie etwa:
%Vor%... während es bei QSBR eher heißt:
%Vor%
Sie sind sich sehr ähnlich. Ein Schlüsselaspekt, das ich nicht wirklich verstehe, ist jedoch, wie die gesamte Literatur darauf hinweist, dass QSBR in der Praxis einen großen Nachteil hat: Es erfordert application level Unterstützung, was bedeutet, dass es nicht wirklich geeignet ist in einer generischen Bibliothek.
Dies wird in unzähligen Zeitschriftenartikeln oder Bibliotheksdokumentationen erwähnt, wie zum Beispiel in Ссылка sagt es:
Die Tatsache, dass QSBR anwendungsabhängig ist, ist fundamental Unterschied zwischen QSBR und EBR. EBR erkennt per Definition die Gnade Perioden auf der Bibliotheksebene. QSBR verlangt dagegen, dass die Anwendungsbericht Ruhezustände an die QSBR-Bibliothek. Wie wir zeigen Abschnitt 5.2, dies gibt QSBR einen signifikanten Leistungsvorteil gegenüber
Die Dokumente für das User-Space-RCU-Projekt , das eine Variation von QSBR verwendet, sagen auch etwas ähnlich:
Allerdings muss jeder Thread periodisch rcu_quiescent_state () aufrufen, genau wie im Kernel, wo schedule () periodisch aufgerufen werden muss. Jeder Thread, der RCU lesenseitige kritische Abschnitte ausführen soll Rufen Sie auch rcu_register_thread () nach dem Erstellen von Threads auf rcu_unregister_thread () vor dem Thread-Exit. Diese Anforderungen sind klar eine strenge Beschränkung für das gesamte Anwendungsdesign, das z Beispiel, verbieten die Verwendung von QSBR RCU in den meisten Bibliothekscode, aber in Rückkehr liefert QSBR unerreichte Leistung.
Ich habe Schwierigkeiten zu verstehen, warum das ein solches Problem ist. Was ich hier zusammenfasse, ist, dass die Anwendung mit QSBR anzeigen muss, wenn sie in einen Ruhezustand eintritt. Aber ich verstehe nicht warum das ist so schwer auf der Bibliotheksebene zu tun?
Konnte eine blockierungsfreie Bibliothek, die Datenstrukturen wie Stapel und Warteschlangen bereitstellt, nicht einfach anzeigen, dass sie nach Abschluss jeder Operation in einen Ruhezustand übergeht? Warum gibt es all diese Vorbehalte gegenüber QSBR, die darauf hindeuten, dass es im Gegensatz zum Anwendungscode nicht einfach im Bibliothekscode zu verwenden ist?
In QSBR kann quiescent_state() an einer beliebigen Stelle aufgerufen werden, an der der aufrufende Thread keine Referenzen auf geteilte Objekte enthält. Andererseits muss in EBR ein Thread auf freigegebene Objekte innerhalb des kritischen Bereichs zugreifen, der mit enter_critical_section() und exit_critical_section versehen ist.
Was dieser Unterschied impliziert, ist:
QSBR kann EBR übertreffen, weil mit weniger häufiger Synchronisation verwendet werden kann . Ja, wie Sie gesagt haben, QSBR kann in ähnlicher Weise mit EBR verwendet werden, aber das bietet nicht die Effizienz QSBR behauptet.
In einer komplexen Anwendung kann das Erkennen eines Ruhezustands schwierig sein. Aus diesem Grund sind Techniken, die auf dem Ruhemodus basieren, wie die RCU-Verwendung, hauptsächlich auf bestimmte Umgebungen beschränkt, in denen ein natürlicher Ruhezustand vorliegt (z. B. Kontextwechsel im Linux-Kernel).
Tags und Links algorithm multithreading thread-safety memory-management lock-free