Ruhezustand basierte Reklamation vs epochenbasierte Reklamation

Question

Ich untersuche die verschiedenen Arten von Speicher-Reklamation Strategien für lock-freie Datenstrukturen in einer nicht-Garbage gesammelt Umgebung (wie C oder C++).

Bei meinen Versuchen, ich habe erfolgreich einige dieser Strategien umgesetzt - insbesondere sowohl Ruhezustand Based Reclamation (QSBR) und Epoch Based Reclamation (EBR).

Meine Frage betrifft einen der Hauptunterschiede zwischen diesen beiden Strategien.

Erstens, ich bin bewusst, wie sowohl QSBR und EBR Arbeit, und haben erfolgreich diese beiden Strategien umgesetzt. QSBR und EBR sind sich tatsächlich sehr ähnlich. Beide sind gestaffelte Rückgewinnung Strategien - das heißt, sie vermeiden Race Conditions bei der Freigabe Speicher durch einfach Verschiebung die tatsächliche Freigabe, bis es bewiesen werden kann, dass es sicher ist, die Speicherfreigabe. Mit QSBR und EBR wird dies erreicht, indem ein globaler "Epochenzähler" und dann verschiedene thread-lokale Epochenzähler für jeden beteiligten Thread verwendet werden.

Der Hauptunterschied zwischen QSBR und EBR besteht darin, dass Sie bei QSBR grundsätzlich angeben, wenn ein Thread nicht Referenzen auf freigegebene Daten hat. Mit EBR geben Sie an, wenn ein Thread einen Verweis auf freigegebene Daten enthält. So in der Praxis Code, der verwendet EBR landet mehr aussehen wie eine traditionelle Mutex Sperre/Entsperren kritischen Abschnitt, wie:

enter_critical_section(); 

/* do some cool lock-free stuff */ 

exit_critical_section(); 

... während bei QSBR, es ist eher wie:

/* do some cool lock-free stuff */ 

quiescent_state(); // this thread is done using shared data 

Also sind sie 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: Anwendungsebene Unterstützung, was bedeutet, dass es nicht wirklich für die Verwendung in einer generischen Bibliothek geeignet ist.

Dies ist in unzähligen Zeitschriftenartikeln oder Bibliotheks-Dokumentation erwähnt, wie zum Beispiel in http://www.cs.toronto.edu/~tomhart/papers/tomhart_thesis.pdf, heißt es:

Die Tatsache, dass QSBR ist applikationsabhängig der Grund Unterschied zwischen QSBR und EBR ist. EBR erkennt per Definition die Gracen Perioden auf Bibliotheksebene. QSBR erfordert dagegen, dass die Anwendung Ruhezustände an die QSBR-Bibliothek meldet. Wie wir in Abschnitt 5.2 zeigen, diese QSBR einen erheblichen Leistungsvorteil gegenüber

die Dokumentation zum User-space RCU project gibt, die eine Variation von QSBR verwendet, sagt auch etwas ähnliches:

jedoch jeder Thread muss rcu_quiescent_state(), wie im Kernel periodisch aufrufen, wobei schedule() periodisch aufgerufen werden muss. Jeder Thread, der RCU lesenseitige kritische Abschnitte ausführen soll, muss auch rcu_register_thread() nach der Thread-Erstellung und rcu_unregister_thread() vor dem Thread-Exit aufrufen. Diese Anforderungen eindeutig setzen eine strenge Einschränkung für die gesamte Anwendung Design, dass für Beispiel verbieten die Verwendung von QSBR RCU in den meisten Bibliothekscode, aber in Rückkehr, bietet QSBR unübertroffene 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 angeben, dass sie nach Abschluss jeder Operation in einen Ruhezustand übergeht? Warum gibt es all diese Vorbehalte gegenüber QSBR, die darauf hinweisen, dass es im Gegensatz zu Anwendungscode nicht einfach im Bibliothekscode zu verwenden ist?

Answer 1

In QSBR quiescent_state() kann an einer beliebigen Stelle aufgerufen werden, an der der aufrufende Thread keine Verweise auf gemeinsame Objekte enthält. Auf der anderen Seite, in EBR ein Thread muss Zugriff auf freigegebene Objekte innerhalb des kritischen Abschnitts kommentiert von enter_critical_section() und exit_critical_section.

Was dieser Unterschied impiles ist:

1. QSBR kann EBR übertreffen, weil kann mit weniger häufigen Synchronisation verwendet werden. Ja, wie Sie gesagt haben, QSBR kann in ähnlicher Weise mit EBR verwendet werden, aber das bietet nicht die Effizienz QSBR behauptet.

2. In einer komplexen Anwendung kann die Erkennung des Ruhezustands schwierig sein. Aus diesem Grund sind Ruhephasen-basierte Techniken wie die RCU-Verwendung hauptsächlich auf bestimmte Umgebungen beschränkt, in denen ein natürlicher Ruhezustand vorliegt (z. B. Kontextwechsel im Linux-Kernel).