Kritische Abschnitte mit Multicore-Prozessoren

Question

Mit einem Single-Core-Prozessor, wo alle Ihre Threads von der einen einzigen CPU ausgeführt werden, die Idee, einen kritischen Abschnitt mit einer atomaren Test-und-Set-Operation auf einigen Mutex (oder Semaphor oder usw.) in der Erinnerung scheint einfach genug; Da Ihr Prozessor ein Test-and-Set von einer Stelle in Ihrem Programm aus ausführt, kann es nicht von einem anderen Punkt in Ihrem Programm ausgeführt werden, der als ein anderer Thread getarnt ist.

Aber was passiert, wenn Sie tatsächlich mehr als einen physischen Prozessor haben? Es scheint, dass eine einfache atomare Anordnung auf Befehlsebene nicht ausreichen würde, b/c mit zwei Prozessoren, die möglicherweise ihre Test-und-Set-Operationen gleichzeitig ausführen, was Sie wirklich brauchen, um die Atomizität beizubehalten, ist der Zugriff auf den geteilten Speicher des Mutex. (Und wenn der geteilte Speicherbereich in den Cache geladen wird, gibt es auch die gesamte Cache-Konsistenz-Sache.)

Dies scheint, als würde es weit mehr Overhead als der Single-Core-Fall entstehen, so hier ist das Fleisch von die Frage: Wie viel schlimmer ist es? Ist es schlimmer? Leben wir nur damit? Oder umgehen Sie es, indem Sie eine Richtlinie durchsetzen, nach der alle Threads innerhalb einer Prozessgruppe auf demselben physischen Kern leben müssen?

Answer 1

Multi-Core-/SMP-Systeme sind nicht nur mehrere miteinander verklebte CPUs. Es gibt explizite Unterstützung dafür, Dinge parallel zu machen. Alle Synchronisationsgrundelemente werden mit Hilfe von Hardware in der Art von atomic CAS implementiert. Die Anweisung sperrt entweder den Bus, der von CPUs und Speichercontrollern gemeinsam genutzt wird (und Geräte, die DMA ausführen) und aktualisiert den Speicher oder aktualisiert nur den Speicher, der auf cache snooping basiert. Dies führt wiederum dazu, dass der Algorithmus cache coherency eingreift und alle beteiligten Parteien zwingt, ihre Caches zu löschen.

Disclaimer - dies ist eine sehr grundlegende Beschreibung, es gibt mehr interessante Dinge hier wie virtuelle vs physische Caches, Cache-Write-Back-Richtlinien, Speichermodelle, Zäune, etc. etc.
Wenn Sie mehr darüber wissen möchten, wie OS kann diese Hardware-Einrichtungen verwenden - hier ist an excellent book zum Thema.

Answer 2

Sie benötigen ein Test-and-Set, das den Prozessor zwingt, alle anderen Kerne der Operation zu benachrichtigen, damit sie sich dessen bewusst sind. Ja, das bringt einen Overhead und du musst damit leben. Es ist ein Grund, Multithread-Anwendungen so zu gestalten, dass sie nicht zu oft auf Synchronisationsprimitive warten.

Answer 3

Nun, je nachdem, welche Art von Computern Sie im Haus herumliegen haben, tun Sie Folgendes: Schreiben Sie eine einfache Multithread-Anwendung. Führen Sie diese Anwendung auf einem einzelnen Kern (Pentium 4 oder Core Solo) aus und führen Sie sie dann auf einem Multicore-Prozessor (Core 2 Duo oder ähnlich) aus und sehen Sie, wie groß die Beschleunigung ist.

Zugegeben, dies sind unfaire Vergleiche, da Pentium 4 und Core Solo unabhängig von Kernen wesentlich langsamer sind als ein Core 2 Duo. Vergleichen Sie vielleicht zwischen einem Core 2 Duo und einem Core 2 Quad mit einer Anwendung, die 4 oder mehr Threads verwenden kann.

Sie erhöhen eine Anzahl gültiger Punkte. Multiple Prozessoren verursachen eine Menge Kopfschmerz und Overhead. Wir müssen jedoch nur mit ihnen leben, denn der Geschwindigkeitsschub der Parallelität kann sie weit überwiegen, wenn die kritischen Abschnitte lang genug sind.

Was Ihren letzten Vorschlag betrifft, alle Threads auf demselben physischen Kern zu haben, das besiegt den Punkt eines Multicore-Computers völlig!

Answer 4

Oder umgehen Sie es, indem Sie eine Richtlinie erzwingen, dass alle Threads innerhalb einer Prozessgruppe auf demselben physischen Kern leben müssen?

Das würde den ganzen Punkt Multithreading abbrechen. Wenn Sie eine Sperr-, Semaphor- oder andere Synchronisierungsmethoden verwenden, müssen Sie darauf vertrauen, dass das Betriebssystem sicherstellt, dass diese Operationen miteinander verknüpft sind, unabhängig davon, wie viele Kerne Sie verwenden.

Die Zeit für den Wechsel zu einem anderen Thread, nachdem eine Sperre freigegeben wurde, wird hauptsächlich durch die Kosten eines Kontextwechsels bestimmt. This Der SO-Thread beschäftigt sich mit dem Kontextwechsel-Overhead, also sollten Sie das überprüfen.

Es gibt einige andere interessante Themen auch:

• What are the differences between various threading synchronization options in C#?
• Threading best practices

Sie in diesem MSDN-Artikel lesen sollte auch: Understanding the Impact of Low-Lock Techniques in Multithreaded Apps.

Answer 5

Der Hersteller von Multicore-CPUs muss darauf achten, dass die verschiedenen Kerne sich selbst koordinieren, wenn sie Anweisungen ausführen, die atomaren Speicherzugriff garantieren.

Auf Intel-Chips haben Sie zum Beispiel die Anweisung 'cmpxchg'. Er vergleicht den an einem Speicherort gespeicherten Wert mit einem erwarteten Wert und tauscht ihn gegen den neuen Wert aus, wenn die beiden übereinstimmen. Wenn Sie der Anweisung 'lock' vorangehen, ist garantiert, dass sie in Bezug auf alle Kerne atomar ist.

Answer 6

Speicherzugriffe werden vom Speichercontroller gehandhabt, der sich um Multicore-Probleme kümmern sollte, d. H. Er sollte keinen gleichzeitigen Zugriff auf dieselben Adressen erlauben (wahrscheinlich entweder auf Speicherseiten- oder Speicherzeilenbasis). Sie können also ein Flag verwenden, um anzugeben, ob ein anderer Prozessor den Speicherinhalt eines Blocks aktualisiert (um einen Typ von Dirty Read zu vermeiden, bei dem ein Teil des Datensatzes aktualisiert wird, aber nicht alle).

Eine elegantere Lösung ist die Verwendung eines HW-Semaphorblocks, wenn der Prozessor über eine solche Funktion verfügt. Ein HW-Semaphor ist eine einfache Queue, die die Größe no_of_cores -1 haben kann. So ist es in TI's 6487/8 Prozessor. Sie können entweder den Semaphor direkt abfragen (und loopen, bis er freigegeben wird) oder eine indirekte Abfrage durchführen, die zu einem Interrupt führt, sobald Ihr Kern die Ressource erhält. Die Anfragen werden in der Warteschlange eingereiht und in der Reihenfolge geliefert, in der sie erstellt wurden. Eine Semaphor-Abfrage ist eine atomare Operation.

Cache-Konsistenz ist ein weiteres Problem und Sie müssen möglicherweise in einigen Fällen Cache-Writebacks und Refresh-Vorgänge durchführen. Aber das ist eine sehr Cache-Implementation-spezifische Sache. Mit 6487/8 mussten wir das bei einigen Operationen machen.