Schreiben eine (Spinn -) Faden Barriere mit c++11 atomics
Ich versuche vertraut zu machen mich mit c++11 atomics, also versuchte ich zu schreiben, eine Barriere-Klasse für threads (bevor sich jemand beschwert sich über die nicht vorhandenen Klassen: das ist mehr für das lernen/selbst-Verbesserung, als durch irgendwelche tatsächlichen Bedarf). meine Klasse sieht im Grunde wie folgt:
class barrier
{
private:
std::atomic<int> counter[2];
std::atomic<int> lock[2];
std::atomic<int> cur_idx;
int thread_count;
public:
//constructors...
bool wait();
};
Alle Elemente werden mit null initialisiert, außer thread_count, die über die entsprechende Anzahl.
Ich habe implementiert die Funktion " warten (wie
int idx = cur_idx.load();
if(lock[idx].load() == 0)
{
lock[idx].store(1);
}
int val = counter[idx].fetch_add(1);
if(val >= thread_count - 1)
{
counter[idx].store(0);
cur_idx.fetch_xor(1);
lock[idx].store(0);
return true;
}
while(lock[idx].load() == 1);
return false;
Aber wenn man versucht, es mit zwei threads (thread_count
2) whe erste thread bekommt in der Warteschleife ganz gut, aber der zweite thread nicht entriegeln der Schranke (es scheint, dass es nicht sogar zu int val = counter[idx].fetch_add(1);
, aber ich bin nicht so sicher. Aber wenn ich mit gcc-atomic-Interna durch die Verwendung volatile int
statt std::atomic<int>
und schreiben wait
wie folgt:
int idx = cur_idx;
if(lock[idx] == 0)
{
__sync_val_compare_and_swap(&lock[idx], 0, 1);
}
int val = __sync_fetch_and_add(&counter[idx], 1);
if(val >= thread_count - 1)
{
__sync_synchronize();
counter[idx] = 0;
cur_idx ^= 1;
__sync_synchronize();
lock[idx] = 0;
__sync_synchronize();
return true;
}
while(lock[idx] == 1);
return false;
funktioniert es Prima. Von meinem Verständnis sollte es keine grundsätzlichen Unterschiede zwischen den zwei Versionen (mehr zu dem Punkt, wenn überhaupt sollte das zweite weniger wahrscheinlich, um zu arbeiten). Also, welches der folgenden Szenarios trifft zu?
- Ich hatte Glück mit der zweiten Implementierung und mein Algorithmus ist Mist
- Ich habe nicht ganz verstanden
std::atomic
und es gibt ein problem mit der ersten Variante (aber nicht die zweite) - Sollte es funktionieren, aber die experimentelle Implementierung für c++11-Bibliotheken ist nicht so ausgereift wie ich gehofft habe
Für den Datensatz ich bin mit 32-bit mingw mit gcc 4.6.1
Den aufrufenden code sieht wie folgt aus:
spin_barrier b(2);
std::thread t([&b]()->void
{
std::this_thread::sleep_for(std::chrono::duration<double>(0.1));
b.wait();
});
b.wait();
t.join();
Da mingw nicht whave <thread>
Header jet benutze ich eine selbst geschriebene version für, was im Grunde wickelt die entsprechenden pthread-Funktionen (bevor jemand fragt: ja, es funktioniert ohne die Barriere, so sollte es nicht ein problem mit der Verpackung)
Eine Einsicht wäre sehr geschätzt.
edit: Erklärung für den Algorithmus um es klarer:
thread_count
ist die Anzahl der threads, die warten, bis die Barriere (also wennthread_count
threads sind in der Barriere alle aus der Barriere).lock
ist auf eins gesetzt, wenn der erste (oder einer anderen) thread gibt der Barriere.counter
zählt, wie viele threads innerhalb der Barriere und ist atomar inkrementiert werden, einmal für jeden threadif counter>=thread_count
alle Gewinde im inneren der Barriere, so dass Zähler und Schloss werden auf null zurückgesetzt- sonst der thread wartet auf die
lock
zu null - in den nächsten Verwendung der Sperrschicht verschiedenen Variablen (
counter
,lock
) verwendet werden, sicherzustellen, gibt es keine Probleme, wenn threads, die warten immer noch auf den ersten Einsatz der Barriere (z.B. Sie hatte verdrängt, wenn die Sperre aufgehoben wird)
edit2:
Ich habe jetzt getestet mit gcc 4.5.1 unter linux, wo beide Versionen scheinen zu funktionieren, das scheint auf ein problem mit mingw ist std::atomic
, aber ich bin noch nicht ganz überzeugt, da der Blick in die <atomic>
header revaled, dass die meisten Funktionen rufen Sie einfach die entsprechende gcc-atomic Bedeutung, es sollte wirklich nicht bea Unterschied zwischen den beiden Versionen
- Ich habe nicht gespielt mit c++11 atomics noch, aber ich bin wirklich überrascht zu sehen, dass Sie mit GCC instrinsics (z.B.
__sync_fetch_and_add
). Ich würde sagen, diese sollten nicht mehr benötigte mit c++11? - Ich habe implementiert die version mit GCC-Interna, wenn das eine mit atomics hat nicht funktioniert, zum Vergleich (auch wenn beide nicht arbeiten, ich hätte angenommen, dass es etwas wirklich falsch mit meinem Algorithmus)
- Gibt es nicht eine race-condition in der
if load then store
? Sollte dies nicht einif (x.exchange(1))
oder sowas? - SB: eigentlich nicht, da der, wenn nicht sogar notwendig ist es,
store(1)
ohne dieif
sollte ebenso funktionieren, dalock
1 festgelegt ist, und es nur wieder nach jedem thread in der Barriere vorbei. Dieif(lock.load())
ist nur da, um zu vermeiden, unnecerry Schreibzugriff auf die cacheline (jetzt, dass ich denke, ich könnte beginnen, legen Sie die nächste Schleuse zu 1 in derif(val >= thread_count - 1)
Teil den gleichen Effekt zu erhalten - Ich denke, du hast Recht, ich war nicht Lesen Sie es sorgfältig genug.
- Sind Sie wirklich sicher, dass alles wird auf null initialisiert? Beachten Sie, dass die
std::atomic<int>
s nicht erhalten, auf null initialisiert, sofern Sie nicht explizit erwähnen diese arrays im Konstruktor der Initialisierungsliste, da std::atomic hat einen vom compiler generierten Konstruktor. Ich hatte einen gehen mit dieser auf 4.6.1 auf x86-64 hardware, und es funktioniert finden wenn alles auf null initialisiert. - Ja, ich bin mir ziemlich sicher, Sie werden mit null initialisiert (und ja, ich habe explizit initilized Sie dass). Haben Sie auf mingw oder eine native gcc? Wie ich bereits erwähnt funktionierte es einwandfrei unter linux (zumindest schien, Multi-Thread-debugging ist schwierig, nachdem alle). Baue ich tatsächlich das 32-bit-Binärdateien (mit-march=pentium4, um sicherzustellen Existenz von Befehlssatz-Erweiterungen (vor allem atomics)), so dass könnte der wichtige Unterschied zu
Du musst angemeldet sein, um einen Kommentar abzugeben.
Sieht es unnötig kompliziert. Versuchen Sie, diese einfachere version (gut, ich habe es noch nicht getestet, ich habe gerade meditiert auf ihn:))) :
EDIT:
@Grizzy, ich finde keine Fehler in der ersten (C++11) version und ich habe auch schon ausführen, wie ein hundert-Millionen-Synchronisierung mit zwei threads und vervollständigt es. Ich habe es auf einem dual-socket-quad-core-GNU/Linux-Maschine, aber, so bin ich eher geneigt zu vermuten, dass die option 3. - die Bibliothek (oder besser gesagt, seine port-win32) ist nicht ausgereift genug.
Ich habe keine Ahnung, ob dies eine Hilfe sein, aber der folgende Codeausschnitt von Herb Sutter Umsetzung einer gleichzeitigen Warteschlange verwendet einen spinlock basierend auf atomics:
In der Tat, die Norm stellt den Zweck gebauten Typ für diese Konstruktion, die erforderlich ist, um lock-freien Operationen
std::atomic_flag
. Mit, dass, den kritischen Abschnitt würde dann so Aussehen:(Die Sie verwenden können, zu erwerben und Speicher freigeben bestellen, wenn Sie bevorzugen.)
->
und__
pro Quadratzentimeter ist ein Segen. Und, Sie können Leerzeichen auch! Ich denke, ich werde gehen und Aufräumen, OPthis_thread::yield
kann funktionieren, aber das scheint falsch (wir wollen nicht deschedule, drehen Sie einfach effizienter.) Beachten Sie, dass die OP nicht wollen, um eine fertige Umsetzung.atomic<bool>
man könnte/sollte die Verwendungstd::atomic_flag
, die erforderlich ist, um lock-freie-Operationen (im Gegensatz zuatomic<bool>
).Hier ist eine elegante Lösung aus dem Buch C++ Concurrency in Action: Praktische Multithreading.
Hier ist eine einfache version von mir :
Verwendung : (von std::lock_guard Beispiel)
bool expected = false; while(!lockVal.compare_exchange_strong( expected,true ) );
nach dem ersten Aufrufcompare_exchange_strong
, den Wert vonexpected
wirdtrue
, und auf der nachfolgenden Drehungen die Sperre lassen den thread durch. Check out std::atomic<> Referenz. Korrekte Weg wäre:bool expected = false; while(!lockVal.compare_exchange_strong( expected,true ) ) expected = false;
expected
ist nicht die Klasse Mitglied. Jeder thread der Eingabe derLock()
Methode wird das Gesicht einer neuenexpected
variable. Es ist nur ein Wert auf dem stack, wird gereinigt werden, beim verlassen desLock()
Methode. So dass Sie nicht haben, um es zufalse
.expected
auf dem stack wird überschrieben durchcompare_exchange_strong
. Der Hinweis, den ich verlinkte, sagt: "Vergleicht den Inhalt der enthaltenen Wert mit gerechnet: - wenn "true", ersetzt die darin enthaltenen Wert mit val (wie speichern). - wenn false, wird es ersetzt voraussichtlich mit den enthaltenen Wert ." Diese Pausenexpected
für die next-Schleife, iteration.compare_exchange_strong
Funktion. Der Wert von LockVal ist wichtig.compare_exchange_strong
vergleicht den Wert von "lockVal' wenn esfalse
. Wenn nicht, dreht es sich, bis der lock entriegelt wird.expected
geändert werden, wenn der Vergleich fehlschlägt, wie der Hinweis, den ich zitierte klar. Ich schrieb nur hier, weil ich eigentlich versucht mit Ihrem code und es hat nicht geklappt, ich begann zu Lesen und kam zu den Schlussfolgerungen habe ich bereits oben erwähnt. Nehmen Sie es oder lassen Sie es, ich bin nicht hier, um zu streiten auf dem internet nur für das argument ' s sake.std::atomic::exchange()
stattcompare_exchange_strong
. Es ist einfacher.std::atomic<bool>
verwende ichstd::atomic_flag
mitstd::atomic_flag::test_and_set(std::memory_order_acquire)
für den Erwerb und diestd::atomic_flag::clear(std::memory_order_release)
für die Freigabe. Diese Technik wird Ihnen ein reines lockless Barriere.Ich weiß, der thread ist ein wenig alt, aber da es noch die erste google Ergebnis bei der Suche nach einem thread Barriere mit c++11 nur, ich möchte eine Lösung, entledigt sich der busy waiting mit der
std::condition_variable
.Im Grunde ist es die Lösung der Kälte, sondern von der
while
loop ist es mitstd::conditional_variable.wait()
undstd::conditional_variable.notify_all()
. In meinen tests scheint es zu funktionieren.Warum nicht std::atomic_flag (ab C++11)?
http://en.cppreference.com/w/cpp/atomic/atomic_flag
Hier ist, wie ich schreiben würde, mein Spinnen-thread Barriere Klasse:
Gestohlen direkt aus Google docs
spinlock.h
usage.cpp