Ich habe ein interessantes Datenstruktur-Design-Problem, das über meine derzeitige Expertise hinausgeht. Ich suche Datenstruktur oder Algorithmus Antworten zur Bewältigung dieses Problems.
Die Anforderungen:
(pointer address, size) Paaren (effektiv zwei Zahlen; die erste ist nützlich als Sortierschlüssel) an einem Ort (address, size) -Paare enthalten ist - das heißt, wenn das Paar einen Speicherbereich definiert, wenn der Zeiger innerhalb eines Bereichs liegt In der Liste. Threads werden seltener Einträge aus dieser Liste hinzufügen oder entfernen. Ich bin bestrebt, eine naive Implementierung zu vermeiden, wie zum Beispiel einen kritischen Abschnitt, um den Zugriff auf eine sortierte Liste oder einen Baum zu serialisieren. Welche Datenstrukturen oder Algorithmen könnten für diese Aufgabe geeignet sein?
Gekennzeichnet mit Delphi, da ich diese Sprache für benutze diese Aufgabe. Sprach-agnostische Antworten sind sehr willkommen.
Allerdings kann ich wahrscheinlich keinen Standard verwenden Bibliotheken in jeder Sprache ohne große Sorgfalt. Der Grund ist der Speicherzugriff (Zuweisen, Freigeben usw. von Objekten und deren internem Speicher, z Baumknoten usw.) wird streng kontrolliert und muss durch meine eigenen gehen Funktionen. Mein aktueller Code wird an anderer Stelle im selben Programm verwendet rot / schwarze Bäume und ein bisschen Trie, und ich habe diese selbst geschrieben. Objekt Die Knotenzuordnung wird durch benutzerdefinierte Speicherzuweisungsroutinen ausgeführt. Es geht über den Rahmen der Frage hinaus, wird aber hier zur Vermeidung erwähnt eine Antwort wie "benutze STL Struktur foo." Ich bin scharf auf eine algorithmische oder Struktur antworte das, solange ich die richtigen Referenzen oder Lehrbücher habe, Ich kann mich selbst implementieren.
Ich würde ein TDictionary<Pointer, Integer> (von Generics.Collections ) kombiniert mit einem TMREWSync (von SysUtils ) für den Mehrfachlese-Exklusivschreibzugriff verwenden. TMREWSync ermöglicht mehreren Lesern gleichzeitig den Zugriff auf das Wörterbuch, solange kein Writer aktiv ist. Das Wörterbuch selbst bietet O (1) Lookup von Zeigern.
Wenn Sie die RTL-Klassen nicht verwenden möchten, lautet die Antwort: Verwenden Sie eine Hash-Map in Kombination mit einem Synchronisationsobjekt mit mehreren Lese- und Schreibrechten.
BEARBEITEN : Sie haben gerade erkannt, dass Ihre Paare wirklich Speicherbereiche darstellen, also funktioniert eine Hash-Map nicht. In diesem Fall könnten Sie eine sortierte Liste verwenden (sortiert nach Speicheradresse) und dann die binäre Suche verwenden, um schnell einen passenden Bereich zu finden. Das macht das Nachschlagen O (log n) statt O (1) though.
Erforschen Sie ein wenig die Replikationsidee ...
Vom Standpunkt der Korrektheit aus werden Leser / Schreiber-Sperren die Arbeit machen. Jedoch, in der Praxis, während Leser in der Lage sein mögen, gleichzeitig und parallel fortzufahren mit dem Zugriff auf die Struktur, werden sie eine große Konkurrenz auf dem Schloss, für die offensichtlicher Grund, dass das Sperren selbst für den Lesezugriff ein Schreiben in das Schloss selbst beinhaltet. Dies wird die Leistung in einem Multi-Core-System und noch mehr in einem Multi-Socket zunichte machen System.
Der Grund für die geringe Leistung ist der Cache-Line-Invalidierungs- / Transferverkehr zwischen Kernen / Sockeln. (Als Randbemerkung, hier ist eine sehr neue und sehr interessante Studie zum Thema Alles, was Sie schon immer wissen wollten Synchronisation aber hatten Angst zu fragen ).
Natürlich können wir Zwischenkern-Cache-Übertragungen, ausgelöst durch Leser, vermeiden, indem wir machen eine Kopie der Struktur auf jedem Kern und Beschränkung der Leser-Threads auf den Zugriff nur die Kopie lokal zu dem Kern, den sie gerade ausführen. Dies erfordert einen Mechanismus, damit ein Thread seine aktuelle Kern-ID erhält. Es beruht auch darauf, dass der Betriebssystem-Scheduler keine unnötigen Threads über die Kerne hinweg bewegt, d. H. Um die Core-Affinität in gewissem Ausmaß zu erhalten. AFACT, die meisten aktuellen Betriebssysteme tun es.
Was die Autoren betrifft, so würde ihre Aufgabe darin bestehen, alle vorhandenen Replikate zu aktualisieren, indem sie jede Sperre zum Schreiben erhalten. Das Aktualisieren eines Baumes (anscheinend sollte die Struktur irgendein Baum sein) bedeutet eine temporäre Inkonsistenz zwischen Replikaten. Von dem Problem Beschreibung diese Nähte sind akzeptabel. Wenn ein Autor arbeitet, blockiert er die Leser auf einer einzigen Kern, aber nicht alle Leser. Der Nachteil ist, dass ein Autor die gleiche Arbeit ausführen muss viele Male - so oft wie es Kerne oder Steckdosen im System gibt.
PS.
Vielleicht, nur vielleicht, eine andere Alternative ist eine Art RCU-ähnliche Vorgehensweise, aber ich tue es nicht kennt gut, also höre ich einfach auf, nachdem ich es erwähnt habe:)
Mit Replikation könnten Sie: - eine Kopie Ihrer Datenstruktur (Liste mit binärer Suche, der erwähnte Intervallbaum, ..) (sagen wir die "ursprüngliche"), die nur für das Nachschlagen (Lesezugriff) verwendet wird. - Eine zweite Kopie, die "update", wird erstellt, wenn die Daten geändert werden sollen (Schreibzugriff). Also wird der Schreibvorgang in die Update-Kopie übernommen.
Wenn der Schreibvorgang abgeschlossen ist, ändern Sie einen "aktuellen" Zeiger von "Original" auf "Update". Bezieht man einen Zugriffszähler auf die "Original" -Kopie ein, kann dieser zerstört werden, wenn der Zähler wieder auf Null zurückgesetzt wird.
Im Pseudocode:
%Vor%Um die Antwort bezüglich der tatsächlich zu verwendenden Datenstruktur zu vervollständigen: Angesichts der festen Größe der Dateneinträge (zwei Integer-Tupel), die ebenfalls ziemlich klein sind, würde ich ein Array für die Speicherung und binäre Suche für das Nachschlagen verwenden. (Eine Alternative wäre ein ausgewogener Baum, der im Kommentar erwähnt wird).
Apropos Leistung: Wie ich verstehe, definieren "Adresse" und "Größe" Bereiche. Somit würde das Nachschlagen nach einer gegebenen Adresse innerhalb eines solchen Bereichs eine Additionsoperation von "Adresse" + "Größe" (zum Vergleich der abgefragten Adresse mit der Bereichsobergrenze) immer wieder beinhalten. Es kann leistungsfähiger sein, Anfangs- und Endadresse statt Start-Adresse und Größe explizit zu speichern, um diese wiederholte Addition zu vermeiden.
Lesen Sie die LMDB-Designpapiere unter Ссылка . Ein MVCC B + -Baum mit Lockless-Lese- und Copy-On-Write-Schreibvorgängen. Lesevorgänge sind immer Nullkopie, Schreibvorgänge können optional auch Nullkopie sein. Kann in der C-Implementierung problemlos Millionen von Lesevorgängen pro Sekunde verarbeiten. Ich denke, Sie sollten dies in Ihrem Delphi-Programm ohne Änderungen verwenden können, da die Leser auch keine Speicherzuweisung vornehmen. (Writer können einige Zuweisungen vornehmen, aber es ist möglich, die meisten zu vermeiden.)
Als Randbemerkung ist hier eine gute Lektüre über Speicherbarrieren: Memory Barriers : eine Hardware-Ansicht für Software-Hacker
Dies ist nur um einen Kommentar von @fast zu beantworten, der Kommentarraum ist nicht groß genug ...
@chill: Wo sehen Sie die Notwendigkeit, irgendwelche "Speicherbarrieren" zu platzieren?
Überall, wo Sie auf freigegebenen Speicher von zwei verschiedenen Kernen zugreifen.
Zum Beispiel kommt ein Schreiber, erstellt eine Kopie der Daten und ruft dann an
%Code%. Innerhalb release4Write erledigt der Schreiber die Aufgabe
release4write , um den gemeinsamen Zeiger mit dem Speicherort des neuen zu aktualisieren
Daten, dekrementiert den Zähler der alten Kopie auf Null und fährt mit dem Löschen fort.
Jetzt interveniert ein Leser und ruft current = data auf. Und innerhalb get4Read tut es get4Read . Da es keine Speicherbarriere gibt, liest dies den alten Wert von copy = current . Nach allem, was wir wissen, kann der Schreibvorgang nach dem Löschaufruf neu geordnet werden, oder der neue Wert von current kann sich immer noch in der Speicherwarteschlange des Brenners befinden oder der Leser hat es möglicherweise noch nicht
gesehen und verarbeitet eine entsprechende Cache-Invalidierungsanfrage und was nicht ...
Nun sucht der Leser glücklich in dieser Kopie der Daten
dass der Verfasser löscht oder gerade gelöscht wurde. Ups!
Aber, warte, es gibt noch mehr! : D
Bei geeigneter Verwendung, wenn die & gt; get .. () und release .. () -Funktionen, wo sehen Sie die Probleme auf gelöschte Daten oder mehrere löschen zugreifen?
Siehe das folgende Interleaving von Lese- und Schreiboperationen.
%Vor%Der Autor greift auf gelöschte Daten zu und versucht dann, sie wieder zu löschen. Doppel oops!
Tags und Links algorithm multithreading thread-safety delphi data-structures