Thema: spinlocks

[bluecode]

Mann könnte natürlich in einer vorgelagerten Schleife mit nem einfachen Lese-Befehl (der nichts verändern darf) erst mal warten bis der Lock frei ist und dann mit dem richtigen bts-Befehl oder xchg-Befehl oder cmpxchg-Befehl versuchen den Lock tatsächlich zu bekommen.

Genau das macht doch sein Code, oder sehe ich das falsch?

[FlashBurn]

Genau das macht doch sein Code, oder sehe ich das falsch?

Richtig

@erik

Ich meine Code wie diesen:

Code: [Auswählen]

mov eax,1
mov edx,addrLock
.loop:
xchg [edx],eax
test eax,eax
jnz .loop
Dieser Code lockt den Bus bei jedem Schleifendurchlauf (und dürfte so ungefähr dem entsprechen was ich irgendwo am Anfang mal gelesen habe). Das kann ganz schnell zu einem Performace Problem werden. Deswegen ja auch die Test-And-Set Variante.

@all

Was mich mal interessieren würde, wozu ist der cmpxchg Befehl eigentlich gut (oder besser)? Ich meine mich würde mal ein Bsp. interessieren wo man durch ihn wirklich einen Gewinn hat. Als Bsp. wird oft genannt, wenn man eine Variable ändern möchte und diese Variable dann durch einen Lock geschützt werden müsste. Das sehe ich auch soweit ein, es macht mehr Sinn diesen  Befehl (oder halt cmpxchg8/16) einzusetzen, da man dann den Lock nicht benötigt. Was ich aber nicht weiß ist ein Bsp. wo ich einfach ne Variable ändern möchte. Mir fällt da spontan nur die Semaphore ein, aber da tut es auch ein "lock add [eax],1" oder "lock sub [eax],1", aber es muss ja auch einen Grund dafür geben das Intel die anderen beiden Befehle (8 und 16 von cmpxchg) eingeführt hat.

Wenn ich etwas mit einem Lock schütze dann ist das meistens ne Datenstruktur und da reicht es z.B. nicht wenn ich einfach nur z.b. die Wurzel eines Baumes ändere, wenn dann möchte ich den ganzen Baum irgendwie ändern (ist ein blödes Bsp.).

[erik.vikinger]

Hallo,

Genau das macht doch sein Code, oder sehe ich das falsch?

Da bin ich mir nicht mehr sicher. Zuerst war ich von den ganzen PUSHs und POPs irritiert und dann von ":[output] "=q"(spinlock->flags)" (deshalb dachte ich das bei "testl $1,(%%eax)\n\t" irgendwas in Abhängigkeit von den Flags aus dem Struct gemacht wird). Nach jetzt noch mal einigen Minuten Konzentration bin ich (fast) geneigt Dir recht zu geben.

Ich finde dieser Code ist scheußlich formatiert und sehr ungenügend kommentiert (und außerdem hasse ich AT&T-Syntax, da bekomme ich immer nen Drehwurm wegen der verkehrten Operanden-Reihenfolge).
Edit: ich will es noch mal ganz klar sagen: Man kann auch (Inline-)Assembler-Code lesbar und verständlich gestalten! Dazu wird nicht zwingenst eine Hochsprache benötigt.

Ganz unabhängig davon finde ich so eine vorgelagerte Schleife irgendwie sinnlos, klar wird beim warten möglicherweise etwas weniger Traffic auf dem CPU-Netzwerk erzeugt aber deshalb gibt doch der momentane Besitzer den Lock nicht schneller frei, oder irre ich da auch schon wieder?

Dieser Code lockt den Bus bei jedem Schleifendurchlauf (und dürfte so ungefähr dem entsprechen was ich irgendwo am Anfang mal gelesen habe).

2 mal Ja.

Das kann ganz schnell zu einem Performace Problem werden.

Theoretisch ja, aber ob das so groß ist kann ich nicht sagen. Müsste man mal nen Benchmark machen indem man einfach ein Single-Thread-Programm laufen lässt und einmal dazu ein anderes Programm startet das so lange einen Lock bekommen will, der gar nicht freigegeben wird, bis der Benchmark fertig ist und ein anderes mal eben nicht.

Ich denke das XCHG-Szenario von http://lowlevel.brainsware.org/forum/index.php?topic=2468.msg27736#msg27736 dürfte da nicht schlimmer sein als normale Lesezugriffe von der Vor-Schleife.

Deswegen ja auch die Test-And-Set Variante.

Was genau meinst Du mit diesem Satz? Für Deinen BTS-Befehl benutzt Du doch auch das LOCK-Präfix.

Was mich mal interessieren würde, wozu ist der cmpxchg Befehl eigentlich gut (oder besser)?

Es gibt zwar ein paar Anwendungsfälle wo der cmpxchg was nützt, aber viel fällt mir da nicht ein.

Mir fällt da spontan nur die Semaphore ein, aber da tut es auch ein "lock add [eax],1" oder "lock sub [eax],1",

Gerade bei einer Semaphore musst Du wissen wie viele schon drin sind und da reicht ein einfacher add nicht, auch nicht mit lock-Präfix.

Wenn ich etwas mit einem Lock schütze dann ist das meistens ne Datenstruktur

Wenn man ne richtige Datenstruktur schützt muss man immer zusätzlich einen Lock oder eine Semaphore vorsehen.


Grüße
Erik

[FlashBurn]

Wenn man ne richtige Datenstruktur schützt muss man immer zusätzlich einen Lock oder eine Semaphore vorsehen.

Der Meinung bin ich ja auch, nur als ich mich über den cmpxchg Befehl informieren wollte, wurde mir mal so ein Bsp. an den Kopf geknallt, das es doch besser ist diesen zu verwenden, wenn man nur eine Variable schützen möchte, als die Variable mit einem Lock zu schützen. Das leuchtet mir ja auch ein, aber warum sollte ich nur ne Variable ändern wollen die geschützt werden muss??

Da bin ich mir nicht mehr sicher. Zuerst war ich von den ganzen PUSHs und POPs irritiert und dann von ":[output] "=q"(spinlock->flags)" (deshalb dachte ich das bei "testl $1,(%%eax)\n\t" irgendwas in Abhängigkeit von den Flags aus dem Struct gemacht wird). Nach jetzt noch mal einigen Minuten Konzentration bin ich (fast) geneigt Dir recht zu geben.

Falls du dich besser fühlst, ich hasse die AT&T Syntax auch, aber GAS/GCC will du nunmal haben (ja ich weiß da gibts so´n switch der zur Intelsyntax wechselt).

Also die ganzen Push´s und Pop´s sind für die Flags, wenn du im Kernel nen Spinlock nutzt und die Ints ausschaltest und dann bei der Freigabe wieder anmachst, kann es sein das du das gar nicht "durftest", das sie bereits aus waren bevor du versucht hast den Lock zu bekommen.

Also als erstes speichere ich die Flags "pushfl", dann deaktiviere ich die Ints und dann gehe ich in eine Schleife wo ich gucke ob der Lock frei ist, ist das nicht der Fall aktiviere ich die ints wieder (obwohl das so nicht stimmt, ich setzte sie auf den Wert der vorher drin stand, deswegen auch "popfl; pushfl") und mache ne "pause" Ist der Lock frei, wird versucht über "lock bts ..." den Lock zu bekommen, hat das nicht geklappt, geht der ganze Spaß wieder von vorne los.

":[output] "=q"(spinlock->flags)" heißt dass das Register "[output]" (anstelle von %0 oder %1, weil ich es lesbarer finde) eins von allen 6 (deswegen auch "q") sein kann.
In EAX steht die Adresse des Locks und mit "testl $1,(%%eax)" teste ich ob der Lock frei ist oder nicht.

Ganz unabhängig davon finde ich so eine vorgelagerte Schleife irgendwie sinnlos, klar wird beim warten möglicherweise etwas weniger Traffic auf dem CPU-Netzwerk erzeugt aber deshalb gibt doch der momentane Besitzer den Lock nicht schneller frei, oder irre ich da auch schon wieder?

Ist erstmal richig, aber ... Das mit dem Lock kommt noch und durch die "pause" wird die CPU entlastet, verbraucht weniger Strom (bin mir net sicher ob das so stimmt), legt wirklich ne kleine Pause ein und belastet damit nicht den Speicherbus und falls du auf ner CPU mit Hyperthreading läufst, kann so der andere logische Kern die Einheiten besser nutzen (stell dir es wie ein ganz kurzes "hlt" vor).

Gerade bei einer Semaphore musst Du wissen wie viele schon drin sind und da reicht ein einfacher add nicht, auch nicht mit lock-Präfix.

Da hast du natürlich recht, ich weiß auch nicht woran ich da dachte. Das einzige was mir spontan einfällt ist, wenn du das mit dem counter einer Semaphore machst (also das gelockete add) dann könntest du etwas sowas machen:

Code: [Auswählen]

lock sub [eax],1
jae .locked
;versuche den spinlock für den Code zu bekommen
;füge den aktuellen thread der Queue hinzu und warte bis du aufgeweckt wirst
.locked:
;du darfst weiter machen
Ich bin mir jetzt aber nicht sicher ob das auch wirklich funktionieren würde. Was ich damit meine ist, das du nur versuchen musst den Spinlock der Semaphore zu bekommen, wenn du sowieso warten musst, ansonsten kannst du ja auch ganz einfach weiter machen. Beim Release dann das ganze umgekehrt, du machst nen gelocktes add und wenn es kleiner als 0 (also negativ) ist, versuchst du den Spinlock zu bekommen und weckst den nächsten Thread auf. So kann es im optimalen Fall passieren das du den Spinlock gar nicht bekommen musst. Wäre also nochmal nen Stück schneller/besser. Aber wie gesagt, ist jetzt ne spontane Idee (um mein Bsp. nicht als sinnlos dastehen zu lassen ) und müsste halt ausprobiert werden.

Was genau meinst Du mit diesem Satz? Für Deinen BTS-Befehl benutzt Du doch auch das LOCK-Präfix.

Der Punkt ist, das ich den Speicherbus nur locke, wenn ich vermute das der Lock frei ist. Du hingegen lockst den immer, bei jedem Zugriff. Soweit wie ich es verstanden habe, geht es darum, das alle anderen Zugriffe warten müssen bis du fertig bist und da man ja alles möglichst parallel macht bremst das halt tierisch die Performance. Weil ansonsten ja auch parallel aus dem Speicher gelesen werden kann, aber wenn du den Bus lockst ist das nicht mehr möglich. Ich hoffe ich war einigmaßen verständlich!

Ich meine die ganze Situation ist sowieso nur für SMP Systeme interessant, weil du auf nem 1 CPU System den Lock immer bekommst. Auf nem SMP System arbeiten alle CPUs gleichzeitig und greifen auch gleichzeitig auf den Speicher zu (und jetzt kommt der Buslock), es sei denn du lockst denn Bus, dann müssen alle auf dich warten.

[bluecode]

Wenn man ne richtige Datenstruktur schützt muss man immer zusätzlich einen Lock oder eine Semaphore vorsehen.

Der Meinung bin ich ja auch, nur als ich mich über den cmpxchg Befehl informieren wollte, wurde mir mal so ein Bsp. an den Kopf geknallt, das es doch besser ist diesen zu verwenden, wenn man nur eine Variable schützen möchte, als die Variable mit einem Lock zu schützen. Das leuchtet mir ja auch ein, aber warum sollte ich nur ne Variable ändern wollen die geschützt werden muss??

Eine einfach verkettete Liste lässt sich damit prima ohne Locks implementieren.

[FlashBurn]

Mir ist noch was eingefallen bezüglich Semaphore und "lock add/sub", Linux implementiert so seine Userspace Semaphore (oder Futex heißt das da glaub ich). Das läuft dann ungefähr so wie ich es beschrieben habe, nur das er halt nen "lock sub [eax],1" macht und wenn es kleiner 0 ist macht er nen Syscall in den Kernel und packt sich in die Warteschleife.

Eine einfach verkettete Liste lässt sich damit prima ohne Locks implementieren.

Ich weiß jetzt nicht genau wie das funktionieren würde, aber ich könnte mir vorstellen dass das nicht einfach ist und das es bei bestimmten Fällen mit einer Spinlock schneller gehen würde. Ich denke da speziell ans Entfernen.

Edit::

Noch mal zu dem lock Präfix. Ich hatte irgendwo mal gelesen, das dadurch der Memorybus für bis zu 100Takte für Lesen und Schreiben gesperrt ist und dadurch kann es sehr wohl passieren das ein anderer Thread der den Spinlock hat schneller fertig wird, wenn man den Memorybus nicht ständig lockt!

[erik.vikinger]

Hallo,

Mir ist noch was eingefallen bezüglich Semaphore und "lock add/sub", Linux implementiert so seine Userspace Semaphore (oder Futex heißt das da glaub ich). Das läuft dann ungefähr so wie ich es beschrieben habe, nur das er halt nen "lock sub [eax],1" macht und wenn es kleiner 0 ist macht er nen Syscall in den Kernel und packt sich in die Warteschleife.

Bist Du Dir sicher das Du richtig geschaut hast?
Das macht dann aber keinen besonders vertrauenerweckenden Eindruck, ich hätte den Linux-Leuten mehr zugetraut. Zwischen dem gelocktem sub und dem anschließendem Nachprüfen (ein normaler Speicherzugriff nehme ich an) könnte ja noch ein anderer Thread (oder gar der Scheduller-IRQ) dazwischen funken.

Noch mal zu dem lock Präfix. Ich hatte irgendwo mal gelesen, das dadurch der Memorybus für bis zu 100Takte für Lesen und Schreiben gesperrt ist und dadurch kann es sehr wohl passieren das ein anderer Thread der den Spinlock hat schneller fertig wird, wenn man den Memorybus nicht ständig lockt!

Den Hinnweis auf http://lowlevel.brainsware.org/forum/index.php?topic=2468.msg27736#msg27736 hatte ich schon gegeben? Ich will echt nicht behaupten das der Schreiber des Beitrags dort die absolute Wahrheit geschrieben hat aber es könnte schon recht dicht dran sein.


Grüße
Erik

[FlashBurn]

Bist Du Dir sicher das Du richtig geschaut hast?
Das macht dann aber keinen besonders vertrauenerweckenden Eindruck, ich hätte den Linux-Leuten mehr zugetraut. Zwischen dem gelocktem sub und dem anschließendem Nachprüfen (ein normaler Speicherzugriff nehme ich an) könnte ja noch ein anderer Thread (oder gar der Scheduller-IRQ) dazwischen funken.

Da sollte man dann wissen was die CPU Befehle so alles bewirken. Denn wenn du ne mathematische Operation durchfürhst werden auch immer die Flags aktualisiert und da kannst du dann sehen ob der neue Wert >= 0 ist.

Den Hinnweis auf http://lowlevel.brainsware.org/forum/index.php?topic=2468.msg27736#msg27736  hatte ich schon gegeben? Ich will echt nicht behaupten das der Schreiber des Beitrags dort die absolute Wahrheit geschrieben hat aber es könnte schon recht dicht dran sein.

Ich habe das ganze jetzt nur mal überflogen. Problem ist er geht von NUMA aus, was wir aufm Desktop nunmal noch nicht haben. Dann macht er es sich mit dem Lock ganz schön einfach . Der Punkt ist doch das viele Sachen bei nem Multi CPU System gleichzeitig ablaufen und halt nicht seriell.

Um es mal ganz logisch zu erklären, wieso musst du denn das lock Präfix verwenden? Weil es halt passieren kann das 2 CPUs den selben Wert ändern (gleichzeitig) und dann ja beide den Lock bekommen würden. Lockst du aber den Memorybus, werden alle Lese- und Schreiboperationen gestoppt bis der Memorybus nicht mehr gelockt ist (und das kann halt ziemlich "lange" dauern). Denn wenn es nicht sehr kostspielig wäre, wieso sind dann nicht alle Speicherzugriffe so wie mit dem lock Präfix.

Ich habe leider jetzt auch keine Quelle zur Hand wo man mal ganz genau beschrieben sieht was bei so nem lock Präfix nun passiert.

Aber man wird nicht umsonst diese Test-And-Set Variante entwickelt haben, damit das lock Präfix nicht alzu häufig auf den Memorybus angewendet wird.

[erik.vikinger]

Hallo,

Da sollte man dann wissen was die CPU Befehle so alles bewirken. Denn wenn du ne mathematische Operation durchfürhst werden auch immer die Flags aktualisiert und da kannst du dann sehen ob der neue Wert >= 0 ist.

Mist, erwischt. Da hatte ich tatsächlich nicht mit gedacht.

Ich habe das ganze jetzt nur mal überflogen.

Das könnte eventuell nicht gereicht haben.

Problem ist er geht von NUMA aus, was wir aufm Desktop nunmal noch nicht haben.

Da irrst Du seit deutlich über 5 Jahren. Der Hyper-Transport von AMD und QPI von Intel haben mehr mit Ethernet gemeinsam als mit nem klassischen CPU-Bus. Die sind nur stärker vernetzt als Ethernet, also es gibt oft viele Wege zum Ziel was man bei Ethernet eher vermeidet.

Dann macht er es sich mit dem Lock ganz schön einfach.

Also ich würde nicht sagen das er es sich einfach macht. Er hat IMHO schon recht genau hingesehen. Natürlich kann er sich auch mal geirrt haben.
Gibt es konkrete Punkte wo Du zweifelst?

Der Punkt ist doch das viele Sachen bei nem Multi CPU System gleichzeitig ablaufen und halt nicht seriell.

Ganz genau. Das hat er doch auch so beschrieben.

Um es mal ganz logisch zu erklären, wieso musst du denn das lock Präfix verwenden? Weil es halt passieren kann das 2 CPUs den selben Wert ändern (gleichzeitig) und dann ja beide den Lock bekommen würden. Lockst du aber den Memorybus, werden alle Lese- und Schreiboperationen gestoppt bis der Memorybus nicht mehr gelockt ist (und das kann halt ziemlich "lange" dauern).

Aha, hat das irgendwer in diesem Thread schon mal anders dargestellt?

Denn wenn es nicht sehr kostspielig wäre, wieso sind dann nicht alle Speicherzugriffe so wie mit dem lock Präfix.

Weil das locking eventuell auch Nebenwirkungen auf den Cache hat. Außerdem gehen viele Speicherzugriffe nur in eine Richtung, direkt im Speicher arbeiten zu können ist eine Fähigkeit die außer x86 kaum andere CPU-Architekturen haben.

Ich habe leider jetzt auch keine Quelle zur Hand wo man mal ganz genau beschrieben sieht was bei so nem lock Präfix nun passiert.

Er hat schon einige Quellen gelesen, darunter auch sehr viele Spezifikationen von AMD, Intel und etlichen mehr. Vielleicht ließt Du Dir mal den gesamten Thread aufmerksam durch.

Aber man wird nicht umsonst diese Test-And-Set Variante entwickelt haben, damit das lock Präfix nicht alzu häufig auf den Memorybus angewendet wird.

Was genau meist Du mit "Test-And-Set Variante"? Den BTS-Befehl oder irgendeine Vorgehensweise?


Grüße
Erik

[FlashBurn]

Da irrst Du seit deutlich über 5 Jahren. Der Hyper-Transport von AMD und QPI von Intel haben mehr mit Ethernet gemeinsam als mit nem klassischen CPU-Bus. Die sind nur stärker vernetzt als Ethernet, also es gibt oft viele Wege zum Ziel was man bei Ethernet eher vermeidet.

Ich weis nicht was du mit NUMA meinst, aber ich verstehe darunter das jede CPU ihren eigenen Speicher hat auf den Sie schnell zugreifen kann. Will sie auf Speicher zugreifen der nicht in ihrer "Nähe" liegt läuft das über den Speicherkontroller einer anderen CPU (also der CPU wo der Speicher in der "Nähe" liegt) und dieses Konzept haben wir noch nicht im Desktopbereich. Das wird bisher ausschließlich bei mehr Sockel Systemen angewand.

Was genau meist Du mit "Test-And-Set Variante"? Den BTS-Befehl oder irgendeine Vorgehensweise?

Also damit meine ich das man erst testet ob der Lock frei ist und erst dann versucht ihn zu bekommen. Das testen läuft dabei ohne lock Präfix ab und belastet den Memorybus also nicht so sehr wie einen Test mit lock Präfix. Wie gesagt, man nutzt diese Variante um die Zugriffe mit lock Präfix so weit es geht zu minimieren! Ich schreib einfach mal pseudo Code:

Code: [Auswählen]

VERSUCH:
ist der Lock frei?
ja -> gehe zu Label FREI;;
nein -> mache eine Pause und gehe dann wieder zu Label VERSUCH;;
FREI:
versuche den Lock zu bekommen;;
habe ich den Lock bekommen?
ja -> verlasse diesen Codeblock;;
nein -> gehe wieder zum Label VERSUCH;;
Du musst dir halt einfach vorstellen, der Thread der den Lock gerade hat, will halt oft aus dem Speicher lesen und dann auch mal schreiben. Ist der Memorybus gelockt, kann er beides in dem Moment nicht machen und muss warten -> d.h. er braucht effektiv mehr Zeit als er brauchen würde, wenn der Memorybus nicht gelockt ist. Das ist aber nicht die einzige Auswirkung, denn damit hälst du auch alle anderen CPUs auf, die gerade auf den Speicher zugreifen wollen, d.h. im Endeffekt "verlangsamst" du das ganze System mit dem ständigen locken des Memorybuses!

Das Problem mit dem genauen erklären ist, das ich mir leider auch nicht Vorstellen kann wie das im Speicher alles parallel ablaufen soll, aber ich kann mir folgendes vorstellen:

Also der xchg Befehl liest erstmal den aktuellen Wert aus dem Speicher (das braucht schonmal seine Zeit), hat er das getan, schreibt er den neuen Wert in den Speicher (was wieder seine Zeit braucht) und genau dazwischen kann es passieren das eine andere CPU (Thread) schneller war und schon nen anderen Wert geschrieben hat (weil das Lesen und Schreiben halt doch ne Weile dauert) und damit würden dann 2 CPUs den Lock haben. Ich versuche das ganze mal noch mehr zu veranschaulichen:

CPU1 liest Wert -> CPU2 liest Wert -> CPU1 schreibt Wert -> CPU2 schreibt Wert

Und jetzt mal mit Lock:

CPU1 sendet LOCK -> CPU1 liest Wert -> CPU1 schreibt Wert -> CPU1 löscht LOCK -> erst jetzt können wieder andere CPUs auf den Speicher zugreifen

Soweit wurde es ja auch beschrieben, was aber bisher nicht wirklich genannt wurde ist, das in der Zeit wo der LOCK aufrecht erhalten wurden viele weitere Speicherzugriffe hätten standfinden können! Diese unterbindest du in dem Moment mit dem LOCK und bremst das System aus.

Das Problem ist im Endeffekt das der RAM, auch wenn er wesentlich schneller als z.B. die HDD ist, immernoch ziemlich langsam ist. Ansonsten bräuchte man ja auch nicht die schnellen Level1 und Level2 Caches (oder jetzt sogar Level3 Caches). In der Zeit wo die CPU etwas aus dem RAM läd hätte sie auch schon viele andere Dinge machen können. Was ich jetzt nicht weiß, wie schnell die Cache Synchronisierung läuft (unter den einzelnen CPUs), dürfte aber auch mehr Zeit in Anspruch nehmen als eine Instruction auszuführen.

Was ich aber ehrlich zugeben muss, das mit dem Cachetrashing habe ich noch nicht verstanden, also was ihr damit meint und warum das schlecht ist

[erik.vikinger]

Hallo,

Ich weis nicht was du mit NUMA meinst, aber ich verstehe darunter das jede CPU ihren eigenen Speicher hat auf den Sie schnell zugreifen kann. Will sie auf Speicher zugreifen der nicht in ihrer "Nähe" liegt läuft das über den Speicherkontroller einer anderen CPU (also der CPU wo der Speicher in der "Nähe" liegt) und dieses Konzept haben wir noch nicht im Desktopbereich. Das wird bisher ausschließlich bei mehr Sockel Systemen angewand.

Ganz klares Jain. Für die Single-Socket-Version stelle es Dir als CPU-Netzwerk auf einem Chip vor, nur die Latenzen sind kleiner. AMD sprach von Anfang an von einem Switch (nicht Hub) der mehrere CPU-Kerne, mehrere Speicher-Controller und mehrere Hyper-Transport-Links in einem Opteron miteinander verbindet. CPUs kommunizieren heutzutage nicht mehr über einen klassischen BUS miteinander sondern über paket-orientierte geswitchte Links. Auch auf einem einzelnem Chip. Die Hyper-Transport-Spezifikation ist frei zugänglich, da steht sehr viel wissenswertes drin. Leider fehlt der Cache-Kohärenz-Teil für den wir uns in diesem Thread sehr interessieren würden.
Der Punkt ist das es immer die selben CPUs sind, egal ob nur ein Sockel da ist oder mehrere. Das Grundprinzip und seine Anwendung muss also immer identisch sein.

Ich schreib einfach mal pseudo Code:

Code: [Auswählen]

[.....][.....]

Danke, jetzt bin ich schlauer. Ich glaube ich weiß jetzt wie bluecode sich wohl gefühlt hat.

Das Problem mit dem genauen erklären ist, das ich mir leider auch nicht Vorstellen kann wie das im Speicher alles parallel ablaufen soll

Du hast den Beitrag, auf den ich jetzt schon 2 mal verwiesen habe gelesen? Ein paar Beiträge davor hab ich auch noch mehr zum xchg-Befehl geschrieben. Ich habe auch erläutert wie das z.B. auf der ARM-Architektur gemacht wird. Bitte lies diesen Thread am besten komplett.

aber ich kann mir folgendes vorstellen....

Das wurde in diesem Thread nun schon mehr als zwei mal erklärt.

was aber bisher nicht wirklich genannt wurde ist, das in der Zeit wo der LOCK aufrecht erhalten wurden viele weitere Speicherzugriffe hätten standfinden können!

Doch, genau darauf bin ich, u.a. im Zusammenhang mit dem xchg-Befehl, schon mehrmals eingegangen und habe erklärt warum das meiner Meinung nach nicht so ist. Das ein klassischer BUS-Lock andere Teilnehmer blockiert ist, denke ich zumindest, allen hier bewusst.

das mit dem Cachetrashing habe ich noch nicht verstanden

Wenn eine CPU auf eine bestimmte Speicherstelle einen gelockten xchg oder cmpxchg (mit Schreib-Vorgang) macht dann müssen vorher alle anderen CPUs die betreffende Cache-Line in den Speicher zurück schreiben (falls diese modifiziert wurde) und invalidieren. Ansonsten würde die betreffende CPU eventuell mit veralteten Daten arbeiten und das wäre fatal. Wenn so eine Cache-Line invalidiert wurde dann muss diese beim nächsten Zugriff erst wieder eingelesen werden was natürlich Zeit kostet. Das ist vor allem dann ärgerlich wenn in der betreffenden Cache-Line noch andere Variablen drin liegen die kein Lock, Semaphore o.ä. darstellen.
Einige hier haben geschrieben das der cmpxchg-Befehl das nur dann machen müsste wenn er auch tatsächlich schreibt, falls der Schreib-Zugriff ausbleibt würden die Caches der anderen CPUs nicht beeinflusst (das wäre natürlich ein Performance-Vorteil). Ich behaupte dass das mit den veröffentlichten Funktionsweisen nicht machbar ist. Ich behaupte auch das solche Tricks nicht notwendig sind und habe das auch in diesem Thread begründet (sie XCHG-Szenario und ARM-Szenario).


Grüße
Erik

[FlashBurn]

Ich muss mich mal korrigieren, ich meinte die ganze Zeit die Test-And-Test-And-Set Variante!

Da ich gerade (und heute allgemein) nicht alzu viel Zeit habe, will ich nur mal kurz aus nem Paper zitieren und den Link zu dem Paper posten:

While the lock is busy, spinning is done in the cache without consuming bus or networks cycles. When the lock is released, each copy is updated to the new value (distributed-write) or invalidated, causing a cache read miss that obtains the new value. The waiting processor sees the change in state and performs a test-and-set; if someone acquired the lock in the interim, the processor can resume spinning in its cache.

Der Link dafür ist: http://www.cs.washington.edu/homes/tom/pubs/spinlock.pdf

Das ergibt erstaunlicher Weise sogar viel Sinn Zusammengefasst heißt das, dass du wenn du nur liest und guckst ob der Wert sich verändert hat, das ganze in deinem Cache machen kannst und so den Memorybus nicht belastest, erst wenn der Lock freigegeben wurde, wird der neue Wert geschrieben und die CPU muss ihn sich holen. D.h. das warten auf den Lock findet immer im Cache statt! Aber wenn du jedesmal schreibst müssen die anderen CPUs ihre Caches invalidieren und es muss in den Speicher zurück geschrieben werden (was heißt das du mit jeder xchg Instruktion auf den Memorybus zugreifst und die Caches der anderen CPUs invalidierst). Ich weiß nun nicht in wie weit die Caches moderner CPUs optimiert sind, das sie erkennen das der neue geschriebene Wert dem alten entspricht und somit keine Änderung stattgefunden hat.

edit::

Jetzt wird mir auch so langsam klar was es mit dem cmpxchg auf sich hat. Im Endeffekt dürfte das genau diese Test-And-Test-And-Set Variante in einem Befehl (ohne schleife halt) sein.

[erik.vikinger]

Hallo,

Ich muss mich mal korrigieren, ich meinte die ganze Zeit die Test-And-Test-And-Set Variante!

Ahja, damit hattest Du bei mir einiges an Verwirrung gestiftet, der BTS-Befehl heißt ja schließlich "Bit-Test-and-Set".

Da ich gerade (und heute allgemein) nicht alzu viel Zeit habe, will ich nur mal kurz aus nem Paper zitieren und den Link zu dem Paper posten:

Keine Zeit zu haben ich normal, das geht jedem mal so, dann kommt der Beitrag eben etwas später. Aber deswegen konsequent die Bitte zu ignorieren das zuvor geschriebene richtig zu lesen empfinde ich persönlich als unhöflich.

[....]
Der Link dafür ist: http://www.cs.washington.edu/homes/tom/pubs/spinlock.pdf

Ist eigentlich schon mal das Alter dieses Dokuments aufgefallen? Die Tests führt der Autor mit einem System mit 20 386er durch. Über den genauen Aufbau können wir nur spekulieren aber ich vermute das jeder Prozessor mit einem Lokalen Cache-Controller direkt verbunden ist und diese 20 Cache-Controller alle gemeinsam an einem speziellen High-Speed-BUS hängen (was vor 20 Jahren "High-Speed" war darf sich jeder selbst ausmalen). Auf dem System-BUS des 386 (welcher in diesem Computer beim jeweiligen Cache-Controller zu Ende ist) kann man nicht erkennen ob ein gelockter Lesezugriff zu einem "xchg [mem],reg" oder "lock add [mem],reg" gehört (cmpxchg wurde erst mit dem Pentium eingeführt) so das keine spezifischen Optimierungen möglich sind. So das selbst ein simpler xchg immer 2 komplette (unabhängige) Bus-Transfers benötigt. Auch die Annahme das ein Lock so beliebt ist das auf diesen über 10 Threads gleichzeitig warten müssen deutet eher auf ein fundamentales SW-Design-Problem hin als auf ernsthafte und seriöse Forschung. Auch das "Backoff" keine adäquate Option ist hat Ethernet bereits deutlich genug bewiesen (siehe http://www.heise.de/newsticker/meldung/Computer-GAU-Das-Silvesterchaos-bei-der-Berliner-Feuerwehr-25744.html leider ist der richtige c't-Artikel nur gegen Geld zu lesen, da drin ist sehr deutlich beschrieben wie das alte Kollisionsbasierte Halb-Duplex-Ethernet unter hoher Last zusammenbricht), Ethernet wird heutzutage nur noch Voll-Duplex benutzt. Insgesamt hätte ich persönlich von einen Harvard-Absolventen und IBM-Mitarbeiter auch vor 20 Jahren was besseres als dieses Geschreibsel erwartet.

Heute wird das so gemacht: http://www.pcisig.com/specifications/pciexpress/specifications/ECN_Atomic_Ops_080417.pdf. Diese Erweiterung wurden in PCI-Express eingeführt damit auch z.B. eine GraKa (also die SW welche auf der GPU läuft) mit der normalen SW sich eine Critical-Section oder Semaphore teilen können (also mit den selben Werkzeugen bearbeiten können). Hyper-Transport kann sowas auch und QPI bestimmt ebenfalls. Deshalb bin ich auch der Meinung das ein xchg auf nicht gecachten Speicher genau so lange dauert wie ein normaler Lesezugriff auf den selben nicht gecachten Speicher. Auch ist der resultieren CPU-Netzwerk-Traffic der selbe. Bei mehreren CPUs den Cache kohärent zu halten dürfte signifikant mehr Traffic erzeugen. Eben weill nicht mehr jede CPU alle Speicherzugriffe aller anderen CPUs mitbekommt geht ein einfaches Cache-Snooping nicht mehr.

Das ergibt erstaunlicher Weise sogar viel Sinn

Für mich ergibt dieses Schriftstück nur einen Sinn: es soll den Status des Verfassers bei unwissenden Entscheidungsträgern erhöhen. Auch bei IBM ist sowas sicher ein brauchbares Werkzeug für die Karriere-Planung.

Zusammengefasst heißt das, dass du wenn du nur liest und guckst ob der Wert sich verändert hat, das ganze in deinem Cache machen kannst und so den Memorybus nicht belastest,

Das stimmt erstmal.

erst wenn der Lock freigegeben wurde, wird der neue Wert geschrieben

Nein! Wenn der ungelockte Lesevorgang den Status "Frei" ergeben hat muss dann für die echte atomische Operation noch mal gelesen werden und zwar gelockt. Es ist extrem wichtig das zwischen dem Lesen und dem zugehörigen Schreiben kein anderer gelockter Zugriff auf die Lock-Variable passieren kann, weder Lesen noch Schreiben (warum das so ist habe ich in diesem Thread nun schon mehrfach geschrieben, daher auch die Bitte diesen Thread richtig zu lesen). Bereits mit dem gelockten Lese-Zugriff geht bei den anderen CPUs die Cache-Line verloren. Ein Zustand "gültig aber vorübergehend gesperrt" habe ich bei Cache-Lines noch nicht gesehen (was nicht heißen soll das sowas unmöglich ist).

Aber wenn du jedesmal schreibst müssen die anderen CPUs ihre Caches invalidieren und es muss in den Speicher zurück geschrieben werden (was heißt das du mit jeder xchg Instruktion auf den Memorybus zugreifst und die Caches der anderen CPUs invalidierst).

Deswegen hab ich ja vorgeschlagen das Lock-Variablen immer in non-cachable Speicher liegen sollen. Damit entfällt das ganze Cache-Kohärenz-Protokoll. Wenn 2 CPUs per xchg versuchen das Lock zu bekommen so sind dafür ganz exakt 4 Messages erforderlich. Wenn beide CPUs mit der ungelockten Vor-Schleife das Frei erkennen und dann beide einen gelockten Zugriffsversuch unternehmen dürfte das Cache-Kohärenz-Protokoll ein vielfaches des Traffics erzeugen. Das Cache-Kohärenz-Protokoll erzeugt umso mehr Traffic je mehr CPUs beteiligt sind, so das ich persönlich die konsequente Vermeidung des ganzen Aufwands bevorzuge. Für Locks die für mehr als 10 Assemblerbefehle behalten werden sollen ist natürlich der pause-Befehl ein gute Methode den Traffic zu reduzieren, aber auf Kosten der Reaktionsgeschwindigkeit. Für noch längere Locking-Zeiten sollte man dann OS-Verwaltete Locks benutzen, das OS kann den wartenden Thread schlafen legen (bei mehren wartenden Threads kommen die in eine geordnete Queue/FIFO) und diesen aufwecken sobald der Lock freigegeben wurde. Damit hat man eine fertretbar kurze Reaktionszeit und erzeugt keine unnütze Last egal wie lange der Lock belegt bleibt. Es gilt also weiterhin das man sich zuerst die Benutzung des Locks genau ansehen muss um dann die richtige Methode zu wählen.

Ich weiß nun nicht in wie weit die Caches moderner CPUs optimiert sind, das sie erkennen das der neue geschriebene Wert dem alten entspricht und somit keine Änderung stattgefunden hat.

Das halte ich für ziemlich unwahrscheinlich.

Jetzt wird mir auch so langsam klar was es mit dem cmpxchg auf sich hat. Im Endeffekt dürfte das genau diese Test-And-Test-And-Set Variante in einem Befehl (ohne schleife halt) sein.

Dann müsste dieser Befehl aber 2 Lesezugriffe aussenden, den ersten ungelockt zum vorher nachschauen und (falls überhaupt erforderlich) den zweiten dann gelockt für die atomische Operation. Das ist natürlich möglich, deckt sich aber nicht mit der von Intel beschriebenen Funktionsweise.


Grüße
Erik

[FlashBurn]

Aber deswegen konsequent die Bitte zu ignorieren das zuvor geschriebene richtig zu lesen empfinde ich persönlich als unhöflich.

Sorry, wenn das so rüber gekommen ist, aber ich habe den Thread nun schon mehrmals gelesen, in der Hoffnung das ich wenn ich zu ende gelesen habe, nichts wieder vergessen habe

Ist eigentlich schon mal das Alter dieses Dokuments aufgefallen?

Ja, aber ich denke an der Grundaussage hat sich nichts geändert, außer das die Cachekohärenz besser (schneller) sein sollte.

Nein! Wenn der ungelockte Lesevorgang den Status "Frei" ergeben hat muss dann für die echte atomische Operation noch mal gelesen werden und zwar gelockt. Es ist extrem wichtig das zwischen dem Lesen und dem zugehörigen Schreiben kein anderer gelockter Zugriff auf die Lock-Variable passieren kann, weder Lesen noch Schreiben (warum das so ist habe ich in diesem Thread nun schon mehrfach geschrieben, daher auch die Bitte diesen Thread richtig zu lesen). Bereits mit dem gelockten Lese-Zugriff geht bei den anderen CPUs die Cache-Line verloren. Ein Zustand "gültig aber vorübergehend gesperrt" habe ich bei Cache-Lines noch nicht gesehen (was nicht heißen soll das sowas unmöglich ist).

Ich meinte ja mit dem Schreiben des neuen Wertes den xchg Befehl, hätte ich vielleicht deutlicher sagen sollen!

Deswegen hab ich ja vorgeschlagen das Lock-Variablen immer in non-cachable Speicher liegen sollen. Damit entfällt das ganze Cache-Kohärenz-Protokoll. Wenn 2 CPUs per xchg versuchen das Lock zu bekommen so sind dafür ganz exakt 4 Messages erforderlich. Wenn beide CPUs mit der ungelockten Vor-Schleife das Frei erkennen und dann beide einen gelockten Zugriffsversuch unternehmen dürfte das Cache-Kohärenz-Protokoll ein vielfaches des Traffics erzeugen. Das Cache-Kohärenz-Protokoll erzeugt umso mehr Traffic je mehr CPUs beteiligt sind, so das ich persönlich die konsequente Vermeidung des ganzen Aufwands bevorzuge. Für Locks die für mehr als 10 Assemblerbefehle behalten werden sollen ist natürlich der pause-Befehl ein gute Methode den Traffic zu reduzieren, aber auf Kosten der Reaktionsgeschwindigkeit. Für noch längere Locking-Zeiten sollte man dann OS-Verwaltete Locks benutzen, das OS kann den wartenden Thread schlafen legen (bei mehren wartenden Threads kommen die in eine geordnete Queue/FIFO) und diesen aufwecken sobald der Lock freigegeben wurde. Damit hat man eine fertretbar kurze Reaktionszeit und erzeugt keine unnütze Last egal wie lange der Lock belegt bleibt. Es gilt also weiterhin das man sich zuerst die Benutzung des Locks genau ansehen muss um dann die richtige Methode zu wählen.

Gut, dann würde mich aber interessieren wie du es bewerkstelligen willst, das die Locks in einem uncacheable Bereich liegen. Denn du musst dann ne ganze Page als uncacheable markieren und das für einen Lock? Zumal ich der Meinung bin, Caches gibt es nicht umsonst. Der Zugriff auf den RAM ist wirklich langsam! Ich glaube auch nicht das der Traffic für das Cachekohärenzprotokoll so schlimm ist, das er mehr braucht als nen Speicherzugriff (sollte max so lange dauern wie ein Cachezugriff)!
Genauso wird oft gesagt, das nicht 2 Locks in einer Cacheline liegen soll, aber wie soll man das bewerkstelligen?! Ich meine, die Cachelines sind nicht immer gleich groß und dann sollte auch nichts anderes in der Cacheline liegen und ich rechne nur mal hoch, in meinem Kernel sollten so ca. 50 allgemeine Locks und dann noch Locks für bestimmte Datenstrukturen (Threads, Tasks, Ports, ...) und dann jedes mal 64byte (als Bsp.)? Finde ich ein wenig arg viel!
Was du mit der Queue ansprichst ist dann schon eher ne Semaphore und zum Thema wann eine Spinlock und wann eine Semaphore einsetzen, habe ich mal ein paar Benchmarks gemacht. Ich habe dann für mich festgelegt, alles was kürzer als 2-3 Contextwechsel ist, kann man ruhig mit ner Spinlock schützen und das ist nicht gerade kurz (du darfst da dann auch noch die TLB Flushes mit einrechnen)!

Dann müsste dieser Befehl aber 2 Lesezugriffe aussenden, den ersten ungelockt zum vorher nachschauen und (falls überhaupt erforderlich) den zweiten dann gelockt für die atomische Operation. Das ist natürlich möglich, deckt sich aber nicht mit der von Intel beschriebenen Funktionsweise.

Ich würde sagen das es genau so funktioniert, im Endeffekt ist es ein cmp und ein xchg Befehl kombiniert in einem Opcode, damit der Decoder weniger machen muss (und es auch einfacher für wird). Anders macht es auch kein Sinn für mich.

[erik.vikinger]

Hallo,

Sorry, wenn das so rüber gekommen ist, aber ich habe den Thread nun schon mehrmals gelesen, in der Hoffnung das ich wenn ich zu ende gelesen habe, nichts wieder vergessen habe

Ist dieser Thread schon sooooo lang?

Ist eigentlich schon mal das Alter dieses Dokuments aufgefallen?

Ja, aber ich denke an der Grundaussage hat sich nichts geändert, außer das die Cachekohärenz besser (schneller) sein sollte.

Das ist wohl eher Wunschdenken. Bei einem einzelnen zentralen Frontside-BUS lief das Cache-Kohärenz-Protokoll etwa so ab: eine CPU sendet eine Speicheranfrage, falls die gewünschten Daten gar nicht im Cache sind oder als Shared getaggt sind, und alle anderen CPUs prüfen ob sie die betreffende Cache-Line eventuell selber im Cache modifiziert haben, wenn ja wird ein spezielle Snoop-Leitung aktiviert und die anfragende CPU unterbricht ihren BUS-Zyklus und gibt damit der anderen CPU die Möglichkeit die modifizierte Cache-Line zurück zu schreiben und danach wird die erste CPU das ganze noch mal probieren. Eben das klassische MESI-Protokoll. Mit dem Pentium Pro wurden dann Cache-2-Cache-Transfers eingeführt womit die CPU welche die gewünschen Daten bereits (modifiziert) im Cache hat direkt als Client, anstatt des RAM-Controllers, der Anfragenden CPU antworten kann, damit haben die CPUs auch vom Cache ihrer Nachbarn profitiert.

Auf einem dezentralisiertem System wo es keine zentrale Stelle gibt über die alle Daten laufen lässt sich sowas nicht bewerkstelligen. Es gibt kein Lock-Signal und auch kein Cache-Snoop-Signal mehr, das wird heute alles mit Messages erledigt. Gerade das Cache-Kohärenz-Protokoll muss oft Broadcasts einsetzen damit alle CPUs von den Statusänderungen der Cache-Lines erfahren bzw. damit sich eine CPU über den Gesamt-Status einer bestimmten Cache-Line informieren kann. Das Broadcasting erzeugt ne Menge Traffic auf dem CPU-Netzwerk, aus diesem Grund hat AMD das "HT assist" eingeführt (ein Cache-Snoop-Filter der beobachtet in welcher CPU welche Cache-Line liegt damit nur die interessanten CPUs direkt befragt werden müssen, weil das so toll ist opfert AMD dafür sogar ein ganzes MByte des teuren L3-Caches).

Gut, dann würde mich aber interessieren wie du es bewerkstelligen willst, das die Locks in einem uncacheable Bereich liegen.

Na die Lock-Variable alle in einer (oder mehreren Pages) sammeln. Für statische Variablen eine eigene Sektion anlegen und per Linker-Magie auf 4 kBytes ausrichten und passend auffüllen und für dynamische Lock-Variablen eben einen eigenen kleinen Speichermanager der immer ganze Pages holt und daraus viele Lock-Variablen macht. Bei Non-Cachable brauchst Du auch nicht auf die Cache-Line-Größe achten und kannst die Lock-Variablen dicht an dicht ablegen. Als Größe der Lock-Variablen würde ich die native Datengröße empfehlen (wegen den Beschränkungen in der PCI-Express-Spezifikation, es ist möglich das bei QPI oder HyperTransport ähnliche Einschränkungen existieren), also 32 Bit oder 64 Bit.

Zumal ich der Meinung bin, Caches gibt es nicht umsonst.

Das stimmt. Aber gerade für Lock-Variablen ist das Cache-Kohärenz-Protokoll eher störend weil man für gelockten Speicher-Zugriff die betreffenden Daten eben exklusiv benötigt und diese Exklusivität vorher aufwändig sicher gestellt werden muss und bei den anderen CPUs auch die Cache-Line killt. Dann lieber gleich auf den ganzen Mist verzichten.

Der Zugriff auf den RAM ist wirklich langsam!

Das stimmt zwar aber hat bisher nicht interessiert. Hier haben alle immer gesagt das gelockte Speicherzugriffe die anderen CPUs stören, wie lange so ein atomischer Befehl ansich braucht war bisher ziemlich egal. Aber gerade wegen den massiven Cache-Kohärenz-Traffics bin ich der Meinung das ungecachte Lock-Variablen auch für die anfragende CPU schneller sind. Erst mal viele andere CPUs zu fragen ob sie die betreffende Cache-Line modifiziert haben dauert wahrscheinlich länger als einfach direkt eine Anfrage mit einer atomischen Operation an den betreffenden Heimat-Speicher-Controller zu schicken. Diese eine Anfrage lässt sich auch einfach Routen, auf der Hin-Richtung ist die Speicher-Adresse das Routing-Kriterium und auf der Rück-Richtung die Initiator-CPU-ID. Stell Dir das Cache-Kohärenz-Protokoll mal vor wenn mehrere CPUs gleichzeitig auf eine Lock-Variable zugreifen wollen, bis die sich geeinigt haben wer überhaupt als erster dran kommt hätte der zuständige Heimat-Speicher-Controller die atomischen Speicher-Operationen längst alle der Reihe nach abgearbeitet. Von dem (Broadcast-)Traffic in diesem Szenario will ich gar nicht erst reden.

Ich glaube auch nicht das der Traffic für das Cachekohärenzprotokoll so schlimm ist, das er mehr braucht als nen Speicherzugriff (sollte max so lange dauern wie ein Cachezugriff)!

Schon das befragen aller CPUs nach einer bestimmten Cache-Line wird wohl mindestens etwa ähnlich lange dauern wie ein Speicherzugriff über eine entfernte CPU (eventuell abzüglich der DRAM-Latenzen).

Was du mit der Queue ansprichst ist dann schon eher ne Semaphore

Die Queue soll für die wartenden Threads sein damit das OS dann automatisch den nächsten rein lassen kann, unabhängig davon ob es sich um einen simplen Lock oder eine hübsche Semaphore handelt. Das sich sowas erst dann lohnt wenn der betreffende Lock/Semaphore/sonstwas länger belegt wird ist klar.

Dann müsste dieser Befehl aber 2 Lesezugriffe aussenden, den ersten ungelockt zum vorher nachschauen und (falls überhaupt erforderlich) den zweiten dann gelockt für die atomische Operation. Das ist natürlich möglich, deckt sich aber nicht mit der von Intel beschriebenen Funktionsweise.

Ich würde sagen das es genau so funktioniert, im Endeffekt ist es ein cmp und ein xchg Befehl kombiniert in einem Opcode, damit der Decoder weniger machen muss (und es auch einfacher für wird). Anders macht es auch kein Sinn für mich.

Es könnte natürlich sein das der cmpxchg so implementiert ist aber die von mir genannten Spezifikationen zeigen was anderes. Ließ Dir doch mal zumindest das PCI-Express-Dokument http://www.pcisig.com/specifications/pciexpress/specifications/ECN_Atomic_Ops_080417.pdf durch. Genau nach diesem Prinzip werden die Befehle sicher auch im CPU-Netzwerk von den Speicher-Controllern ausgeführt. Daher empfehle ich Non-Cachable für Lock-Variablen.


Grüße
Erik

[FlashBurn]

Nur mal so eben dazwischen geschoben (lese noch den Link) bevor ich es wieder vergesse

Du meintest ja das es ein SW Designfehler wäre, wenn z.b. 10 oder mehr CPUs gleichzeitig versuchen würde einen Lock zu bekommen. Ich nenne jetzt mal nur Bsp. die mir so spontan einfallen:

- Festplattentreiber (alle Threads die auf den CPUs laufen wollen gleichzeitig auf die Festplatte schreiben/lesen)
- Physikalischer Speichermanager (alle CPUs brauchen gleichzeit eine neue Page)
- Messagesystem (alle CPUs senden zur gleichen Zeit eine Message an z.B. den App-Server und die müssen ja der Reihe nach in die Queue gepackt werden)
- Netzwerk (alle CPUs senden/empfangen gleichzeitig)
- usw.

Also es gibt genug Fälle wo es passieren kann (auch wenn es mit steigender CPU Zahl immer unwahrscheinlicher wird) das alle CPUs,  dummerweise, die gleiche Lock haben wollen.

Meine Bsp. lassen sich alle (bei nem Mikrokernel) auf das Messagesystem reduzieren (also das nur der Lock für den Port (oder was vergleichbares) bekommen werden muss)! Bei nem monolithen Kernel, wo vieles im Kernel ist, wird es dann halt so laufen wie oben genannt.

Edit::

Schau dir mal den Optimierungsguide von Intel an, da steht auch was über Spinlocks (ansonsten ist es schön zu sehen, wie sie sich teils selbst wiedersprechen ).

[erik.vikinger]

Hallo,

Du meintest ja das es ein SW Designfehler wäre, wenn z.b. 10 oder mehr CPUs gleichzeitig versuchen würde einen Lock zu bekommen.

Ich meinte damit wenn es in einem Programm eine bestimmte Datenstruktur/Ressource gibt die aus vielen Threads nahezu ständig benötigt wird. Der Autor von dem Dokument von Dir ist davon ausgegangen das alle verfügbaren CPUs gleichzeitig auf einen Lock wollen und das ist einfach nicht praxisrelevant (auch wenn es theoretisch trotzdem mal passieren kann).

Ich nenne jetzt mal nur Bsp. die mir so spontan einfallen ....

Das sind natürlich alles reale Beispiele in denen es theoretisch tatsächlich passieren könnte das etliche CPUs gleichzeitig auf die selbe Ressource wollen, aber das ist schon extrem unwahrscheinlich. Außerdem kann man einige Beispiele davon etwas entschärfen wenn z.B. bei einem Virtual-File-System nicht ein globaler Lock sondern für jede Datei ein eigener Lock vorhanden ist, das alle CPUs gleichzeitig auf die selbe Datei wollen ist nochmal deutlich unwahrscheinlicher. Nebst dessen das alle Deine Beispiele von der Sache her recht aufwendige Dinge sind wo selbst ein etwas langsamerer Lock-Vorgang nicht wirklich ins Gewicht fällt. Das einzigste was mMn wirklich sehr zentral ist ist die Speicherverwaltung, da wird man kaum was dezentralisieren können.

Aber auch in der Situation das wirklich sehr viele CPUs gleichzeitig auf den selben Lock wollen bin ich der Meinung das der non-cachable-Weg der bessere ist, da muss einfach nur der zuständige Heimat-Speicher-Controller ein paar Jobs mehr seriell abarbeiten und wenn die alle auf die selbe Lock-Variable gehen lässt sich da bestimmt was optimieren (lange DRAM-Latenzen fallen bei einer noch offenen DRAM-Zeile jedenfalls nicht mehr an). Wenn X CPUs einen Lock haben wollen dann gibt es eben X mal mehr Messages und kein wildes Cache-Kohärenz-Broadcast-Gewitter. Wenn die vielen CPUs nicht irgendeinen Lock haben wollten würden sie eben was andres tun und damit bestimmt auch etwas das CPU-Netzwerk belasten.

Wenn man sehr viele CPUs bedienen möchte muss man auch die SW-Architektur etwas anpassen. Da sollte es z.B. nicht unbedingt einen zentralen "App-Server" (was auch immer Du damit meinst) geben sondern dann sollten dessen aufgaben etwas dezentralisiert werden. Da gibt es natürlich auch gewisse Grenzen aber so weit es möglich ist sollte man eben schon die Gegebenheiten berücksichtigen.


Grüße
Erik

[FlashBurn]

Außerdem kann man einige Beispiele davon etwas entschärfen wenn z.B. bei einem Virtual-File-System nicht ein globaler Lock sondern für jede Datei ein eigener Lock vorhanden ist, das alle CPUs gleichzeitig auf die selbe Datei wollen ist nochmal deutlich unwahrscheinlicher. Nebst dessen das alle Deine Beispiele von der Sache her recht aufwendige Dinge sind wo selbst ein etwas langsamerer Lock-Vorgang nicht wirklich ins Gewicht fällt.

Mit dem Festplattentreiber hast du mich falsch verstanden! Mir ist schon klar, dass es unwahrscheinlich ist, das viele CPUs auf ein und die selbe Datei zugreifen, aber bei einer Festplatte im System ist es gar nicht so unwahrscheinlich das alle mit einmal auf diese eine Festplatte zugreifen wollen (wie gesagt, muss sowieso serialisiert werden, läuft also auf ne Queue hinaus, was nicht lange dauern sollte).
Wo ich dir allerdings wiederspreche (und da muss ich sogar mal meinem Prof zustimmen ), dass ein langsamer Lock-Vorgang auf solche Prozesse keinen Einfluss hat, der ins Gewicht fällt. Denn du betrachtest jetzt immer nur den Lock-Vorgang an sich, aber was ist mit dem restlichem System? Das würde durchaus davon profitieren wenn das mit den Locks so schnell und effizient wie möglich passiert! Weil ja auch lesen/schreiben im uncacheable Memory Last auf dem Memorybus erzeugt und somit effektiv andere ausbremst.

Wenn man sehr viele CPUs bedienen möchte muss man auch die SW-Architektur etwas anpassen. Da sollte es z.B. nicht unbedingt einen zentralen "App-Server" (was auch immer Du damit meinst) geben sondern dann sollten dessen aufgaben etwas dezentralisiert werden. Da gibt es natürlich auch gewisse Grenzen aber so weit es möglich ist sollte man eben schon die Gegebenheiten berücksichtigen.

Mit App-Server (kannst du meinet wegen auch Gui-Server nennen) meine ich etwas was sich um die grafische Darstellung auf dem Bildschirm kümmert und wenn man halt nen großen Monitor hat und 10 Anwendungen laufen gleichzeitig und wollen was neu Zeichnen (und müssen dafür ne Message an den App-Server schicken (ich habe mir schon was einfallen lassen, damit genau das nicht passiert)) dann kann es leider doch passieren das alle CPUs in dem Moment was in die gleiche Queue packen wollen.

Ich habe dein Link gelesen und so wie es da steht, müsste das alles atomisch in einem Zug ablaufen. Aber ich entsinne mich auch irgendwo gelesen zu haben, dass das so nicht funktioniert, sondern das du dann explizit "lock cmpxchg" nehmen musstest (da gibts nen Thread auf sandpile.org dazu). Auch gibt es den Befehl schon seit dem 486 (steht zumindest jedes Mal da, 486+).

[erik.vikinger]

Hallo,

Wo ich dir allerdings wiederspreche (und da muss ich sogar mal meinem Prof zustimmen ), dass ein langsamer Lock-Vorgang auf solche Prozesse keinen Einfluss hat, der ins Gewicht fällt.

Ein Festplattenzugriff kann problemlos über 10ms dauern dann fallen die 100ns für den Lock nur wenig ins Gewicht. Was nicht heißt das man den Lock-Mechanismus völlig vernachlässigen darf aber einen signifikanten Einfluss hat er bei einem Festplattenzugriff IMHO nicht.

Denn du betrachtest jetzt immer nur den Lock-Vorgang an sich, aber was ist mit dem restlichem System? Das würde durchaus davon profitieren wenn das mit den Locks so schnell und effizient wie möglich passiert! Weil ja auch lesen/schreiben im uncacheable Memory Last auf dem Memorybus erzeugt und somit effektiv andere ausbremst.

Natürlich profitert das gesamte System davon wenn ein Lock möglichst wenig Last erzeugt und auch möglichst schnell passiert. Eben deshalb empfehle ich ja das non-cachable weil damit eine sehr kleine und gut deterministische Last entsteht und kein großer und unvorhersehbarer Cache-Kohärenz-Protokoll-Aufwand dazu kommt. Der Vorteil der verteilten RAMs heutiger PCs (ccNUMA) liegt ja darin das es viele Speicherbusse gibt so das die Last der vielen CPU-Kerne eben auch auf viele Speicher-Controller verteilt wird. Außerdem erzeugen auch andere Vorgänge in einer CPU nach außen hin Last, wenn die CPU nicht versuchen würde einen Lock zu bekommen dann würde sie eben was anderes tun. In der Zeit wo eine CPU auf die Antwort eines atomischen Lock-Zugriffs wartet könnte sie auch viele verschiedene Speicherzugriffe initiieren was auch ganz schön Last darstellt.

Mit App-Server (kannst du meinet wegen auch Gui-Server nennen) meine ich etwas was sich um die grafische Darstellung auf dem Bildschirm kümmert und wenn man halt nen großen Monitor hat und 10 Anwendungen laufen gleichzeitig und wollen was neu Zeichnen (und müssen dafür ne Message an den App-Server schicken (ich habe mir schon was einfallen lassen, damit genau das nicht passiert)) dann kann es leider doch passieren das alle CPUs in dem Moment was in die gleiche Queue packen wollen.

Natürlich kann es passieren das viele Prozesse gleichzeitig etwas in eine Queue packen wollen und da ist es sicher von Vorteil wenn der Lock-Mechanismus eine möglichst kleine Last erzeugt. Wenn Du dann aber mal 100 oder 1000 Prozesse hast die auf die selbe Ressource wollen wirst Du mit einer konzeptionellen Änderung wahrscheinlich eine viel größere Beschleunigung erfahren als wenn Du den Zeitverbrauch des Locking auf 0 reduzierst.

Ich habe dein Link gelesen und so wie es da steht, müsste das alles atomisch in einem Zug ablaufen. Aber ich entsinne mich auch irgendwo gelesen zu haben, dass das so nicht funktioniert, sondern das du dann explizit "lock cmpxchg" nehmen musstest

Entschuldige Bitte, da hatte ich mich unklar ausgedrückt. Ich schreibe die ganze Zeit von atomischen Operationen und da gehe ich implizit davon aus das der entsprechende Befehl immer mit lock-Präfix benutzt wird.

Auch gibt es den Befehl schon seit dem 486 (steht zumindest jedes Mal da, 486+).

Der Befehl wurde mit den ersten Pentiums eingeführt und anschließend in später erschienene 486 "zurückportiert", ebenso wie der cpuid-Befehl und der SMI-Mode (den gab es wimre aber nur in speziellen Embedded-Versionen des 486). Es gab sogar 386-Versionen mit cpuid.


Aber anstatt über die Auswirkungen von langsamen und schnellen Lock-Mechanismen zu diskutieren (ich gehe davon aus das dort keine nennenswerten Meinungsunterschiede bestehen) wüste ich gerne warum Du denkst (diesen Eindruck habe ich zumindest) das die gecachte Variante schneller ist. Du darfst dafür gerne das Basis-Szenario von http://lowlevel.brainsware.org/forum/index.php?topic=2468.msg27736#msg27736 verwenden.


Grüße
Erik

[FlashBurn]

Der Befehl wurde mit den ersten Pentiums eingeführt und anschließend in später erschienene 486 "zurückportiert", ebenso wie der cpuid-Befehl und der SMI-Mode (den gab es wimre aber nur in speziellen Embedded-Versionen des 486). Es gab sogar 386-Versionen mit cpuid.

Mit solchen Infos ist Intel immer sehr zurückhaltend

Aber anstatt über die Auswirkungen von langsamen und schnellen Lock-Mechanismen zu diskutieren (ich gehe davon aus das dort keine nennenswerten Meinungsunterschiede bestehen) wüste ich gerne warum Du denkst (diesen Eindruck habe ich zumindest) das die gecachte Variante schneller ist. Du darfst dafür gerne das Basis-Szenario von http://lowlevel.brainsware.org/forum/index.php?topic=2468.msg27736#msg27736  verwenden.

Naja, wie es schon in dem alten Dokument stand, du liest beim Testen erstmal nur aus deinem Cache, der Memorybus wird "geschont", damit hat der Thread der den Lock hat effektiv mehr Bandbreite zur Verfügung. Wie das dann mit dem Cachekohärenzprotokolloverhead ist weiß ich nicht. Genauso haben alle anderen Threads mehr Bandbreite wenn du mit deinem Lock den Memorybus nicht zusätzlich belastest. Außerdem gehe ich mal davon aus, das Intel dieses Vefahren nicht im Optimierungsguide angeben würde, wenn es effektiv nichts bringt.

Ich wäre ja an einer Variante wie man eine Queue implementiert mit Hilfe des cmpxchg Befehls! Dann könnte ich vielleicht die Locks für meine Messagequeue entschärfen.