Fädeln Sie einen sicheren Vektor ein

8

Lassen Sie mich zunächst sagen, dass ich die meisten SO und andere Themen zu diesem Thema gelesen habe.

Wie ich Dinge verstehe, std :: vector wird Speicher neu zuweisen, wenn er neue Elemente zurückschiebt, was mein Fall ist, wenn ich nicht genügend Speicherplatz reserviert habe (was ist nicht mein Fall).

Was ich habe, ist ein Vektor von std :: shared_ptr, und dieser Vektor enthält eindeutige Objekte (oder genauer gesagt Zeiger auf eindeutige Objekte im Vektor).

Die Handhabung dieser Objekte über Zeiger ist um eine Factory & amp; Handler-Klasse, aber Zeiger auf die Objekte sind von außerhalb der Wrapper-Klasse zugänglich und können Memberwerte ändern. Es gibt kein Löschen zu irgendeinem Zeitpunkt.

Wenn ich Probleme, die in früheren SO-Fragen über std :: vector und thread safety aufgeworfen wurden, richtig verstehe, kann das Hinzufügen (push_back) neuer Objekte may vorherige Zeiger ungültig machen, da der Vektor intern Speicher neu zuordnen und kopieren kann alles vorbei, was für mich natürlich eine Katastrophe wäre.

Meine Absicht ist es, von diesem Vektor zu lesen, oft Objekte über die Zeiger zu ändern und neue Elemente aus asynchron laufenden Threads zum Vektor hinzuzufügen.

Also,

  1. Die Verwendung von atomaren oder Mutexen ist nicht genug? Wenn ich von einem Thread zurückdränge, kann ein anderer Thread, der ein Objekt über den Zeiger behandelt, am Ende ein ungültiges Objekt haben?
  2. Gibt es eine Bibliothek, die mit dieser Form von MT-Problemen umgehen kann? Der, über den ich lese, ist Intels TBB, aber da ich bereits C ++ 11 verwende, möchte ich die Änderungen auf ein Minimum beschränken, auch wenn es mehr Arbeit von mir bedeutet - ich möchte dabei lernen nicht nur kopieren und einfügen.
  3. Neben dem Sperren des Zugriffs beim Ändern von Objekten würde ich asynchronen parallelen Lesezugriff auf den Vektor wünschen, der nicht durch push_backs ungültig gemacht wird. Wie kann ich das erreichen?

Wenn es von Bedeutung ist, ist all das oben auf Linux (Debian Jessie) mit gcc-4.8 mit C ++ 11 aktiviert.

Ich bin offen für minimal invasive Bibliotheken.

Vielen Dank im Voraus: -)

    
Ælex 12.05.2014, 23:26
quelle

3 Antworten

7
  

das Hinzufügen (push_back) neuer Objekte kann vorherige Zeiger ungültig machen ...

Nein, diese Operation macht vorherige Zeiger nicht ungültig, es sei denn, Sie beziehen sich auf Adressen innerhalb des internen Datenmanagements der Vektoren (was eindeutig nicht Ihr Szenario ist).
Wenn Sie rohe Zeiger oder std::shared_ptr dort speichern, werden diese einfach kopiert und nicht ungültig.

Wie in den Kommentaren erwähnt, ist a std::vector aus mehreren Gründen nicht sehr geeignet, die Thread-Sicherheit für Erzeuger- / Verbrauchermuster zu garantieren. Das Speichern roher Zeiger, um die aktiven Instanzen zu referenzieren, ist nicht!

Eine Warteschlange wird es viel besser unterstützen. Was die Standards betrifft, können Sie std::deque für den Producer / Consumer verwenden, um ceratain Zugriffspunkte ( front() , back() ) zu haben.

Um den Thread dieses Zugriffspunkts sicher zu machen (um Werte zu pushen / zu puffen), können Sie ihn einfach in Ihre eigene Klasse einfügen und einen Mutex verwenden, um Einfüge- / Löschvorgänge für die gemeinsame Warteschlangenreferenz zu sichern Der andere (und wichtige, wie bei Ihrer Frage) Punkt lautet: Eigentümerschaft und Lebensdauer der enthaltenen / referenzierten Instanzen verwalten . Sie können das Eigentumsrecht auch an den Verbraucher übertragen, wenn dies für Ihren Anwendungsfall geeignet ist (also von overhead mit z. B. std::unique_ptr abgehen), siehe unten ...

Zusätzlich können Sie einen Semaphor (Bedingungsvariable) haben, um dem Consumer-Thread mitzuteilen, dass neue Daten verfügbar sind.

  

'1. Atomare oder Mutexe zu verwenden ist nicht genug? Wenn ich von einem Thread zurückdränge, kann ein anderer Thread, der ein Objekt über einen Zeiger behandelt, am Ende ein ungültiges Objekt haben? '

Die Lebensdauer (und damit die Thread-sichere Verwendung) der Instanzen, die in der Warteschlange (gemeinsam genutzter Container) gespeichert sind, müssen getrennt verwaltet werden (z. B. mit intelligenten Zeigern wie std::shared_ptr oder std::unique_ptr dort gespeichert) .

  

'2. Gibt es eine Bibliothek ...?

Es kann alles gut mit den vorhandenen Standard-Bibliothek Mechanismen IMHO erreicht werden.

Siehe Punkt 3. Siehe oben. Was ich dazu noch sagen kann, es klingt so, als würden Sie nach etwas wie einem rw_lock mutex fragen. Sie können dafür einen Ersatz mit einer geeigneten Bedingungsvariablen bereitstellen.

Fühlen Sie sich frei, nach mehr Klarheit zu fragen ...

    
πάντα ῥεῖ 12.05.2014, 23:46
quelle
3

Wenn Sie dem Container immer nur neue Elemente hinzufügen und dann darauf zugreifen, können Sie einen Vektor mit einer anderen Indirektion finden, so dass anstelle des internen Puffers für einen größeren der einmal zugewiesene Speicherplatz verwendet wird nie befreit und ein neuer Raum wird nur irgendwie thread-sicher angehängt.

Zum Beispiel kann es so aussehen:

%Vor%

Die Klasse enthält ein festes Array von Zeigern auf einzelne Speicherbereiche mit den Elementen, wobei die Größe exponentiell zunimmt. Hier ist die Grenze 6 Teile, also 63000 Artikel - aber das kann leicht geändert werden.

Der Container beginnt damit, dass alle Teilezeiger auf NULL gesetzt sind. Wenn ein Element hinzugefügt wird, wird der erste Chunk mit der Größe m_baseSize , hier 1000, erstellt und in m_parts[0] gespeichert. Nachfolgende Elemente werden dort geschrieben.

Wenn der Chunk voll ist, wird ein weiterer Puffer zugewiesen, der doppelt so groß ist wie der vorherige (2000), und in m_parts[1] gespeichert. Dies wird nach Bedarf wiederholt.

All dies kann mit atomaren Operationen gemacht werden, aber das ist natürlich schwierig. Es kann einfacher sein, wenn alle Schreiber durch einen Mutex geschützt werden können und nur Leser vollständig gleichzeitig sind (z.B. wenn das Schreiben eine viel seltenere Operation ist). Alle Leser-Threads sehen immer entweder NULL in m_parts[i] oder NULL in einem der Puffer oder einen gültigen Zeiger. Vorhandene Elemente werden niemals im Speicher verschoben, ungültig gemacht oder sonstwie.

Soweit es bestehende Bibliotheken betrifft, könntest du Thread-Bausteine ​​ von Intel sehen, insbesondere die Klasse concurrent_vector . Angeblich hat es diese Eigenschaften:

  • Zufälliger Zugriff nach Index. Der Index des ersten Elements ist Null.
  • Mehrere Threads können den Container erweitern und neue Elemente gleichzeitig anhängen.
  • Durch das Vergrößern des Containers werden vorhandene Iteratoren oder Indizes nicht ungültig gemacht.
Yirkha 13.05.2014 00:19
quelle
3

Wenn Sie die Frage erneut lesen, scheint die Situation etwas anders zu sein.

std::vector eignet sich nicht zum Speichern von Objekten , auf die Sie Referenzen beibehalten müssen, da ein push_back alle Verweise auf die gespeicherten Objekte ungültig machen kann. Aber Sie speichern eine Menge std::shared_ptr .

Die std::shared_ptr s, die darin gespeichert sind, sollten die Größenänderung korrekt handhaben (sie werden verschoben, aber nicht die Objekte, auf die sie zeigen), solange Sie in den Threads keine Referenzen auf std::shared_ptr s gespeichert haben der Vektor, aber Sie behalten Kopien von ihnen.

Bei Verwendung von std::vector und std::deque müssen Sie den Zugriff auf die Datenstruktur synchronisieren, da ein push_back , obwohl nicht referenzvalidierend, die internen Strukturen von deque verändert und somit nicht erlaubt ist um gleichzeitig mit einem Deque-Zugriff zu laufen.

OTOH, std::deque ist aus Performance-Gründen wahrscheinlich ohnehin besser geeignet; Bei jeder Größenänderung bewegen Sie sich um eine Menge von std::shared_ptr , die im Falle eines Kopierens / Löschens einen gesperrten Inkrement / Dekrement zum Refcount machen müssen (wenn sie verschoben werden - wie sie sollten - sollte dies weggelassen werden - aber < a href="https://stackoverflow.com/a/10953951/214671"> YMMV ).

Am wichtigsten ist jedoch, dass wenn Sie std::shared_ptr nur dazu verwenden, die möglichen Bewegungen im Vektor zu vermeiden, können Sie sie vollständig löschen, wenn Sie deque verwenden, da die Referenzen nicht ungültig sind, sodass Sie Ihre Objekte speichern können direkt in deque , anstatt die Heap-Zuweisung und die Indirektion / den Overhead von std::shared_ptr zu verwenden.

    
Matteo Italia 13.05.2014 00:00
quelle

Tags und Links