Lowlevel
Lowlevel => Lowlevel-Coding => Thema gestartet von: rizor am 17. March 2010, 16:09
-
Hallo zusammen,
ich habe ein Problem mit meinen Spinlocks.
Der Code stellt fest, dass ein Bereich gelockt ist, obwohl er es nicht ist.
Woran kann das liegen?
#define LOCKED 1
#define UNLOCKED 0
typedef volatile uint32_t lock_t;
void lock(lock_t *lock){
__asm__ __volatile__(
"mov %0 , %%ecx\n"
"loop: xor %%eax , %%eax\n"
"lock cmpxchg %%ecx , %1\n"
"jnz loop\n" : : "i"(LOCKED) , "m"(lock));
}
Habe mir auch lock angeschaut und der ist auf UNLOCKED gesetzt.
Kann mir nicht erklären, woran es scheitert.
gruß,
rizor
-
Hallo,
Kann mir nicht erklären, woran es scheitert.
Bist Du sicher das der cmpxchg wirklich mit dem gelesenen Wert vergleicht? Oder könnte "loop:" als Befehl interpretiert werden und nicht als Label?
Ich mach das immer so: mov eax,LOCKED // den Wert für gelockt in EAX laden
lloop: xchg [ecx],eax // ECX zeit auf die Lock-Speicherstelle, der XCHG-Befehl hat immer automatisch ein Lock-Prefix auch im Ring 3, ab jetzt ist auf jeden Fall gelockt
cmp eax,LOCKED // prüfen ob bereits gelockt war (von wo anders)
je lloop // wenn vorher bereits gelockt war dann wiederholen bis der andere freigegeben hat, ansonsten bin ich jetzt dran
(vorsicht Intel-Syntax)
zum entlocken wird einfach ein anderer Wert in die Lock-Speicherstelle geschrieben, das ist recht unkritisch.
Mit diesem 4-Zeiler hab ich schon oft auf SMP-System (unter Linux und Windows) gute Erfahrungen gemacht, OS-Funktionen nutze ich für so einen wichtigen Mechanismus prinzipiell nicht (höchstens wenn das OS den wartenden Thread pausieren lassen kann bis der aktuelle Lock-Besitzer diesen freigibt anstatt zu pollen, man könnte/sollte aber auch selber die aktuelle Zeitscheibe freigeben).
Grüße
Erik
edit: ich hab den ASM-Code besser formatiert
-
Ich würde gcc atomic builtins (http://gcc.gnu.org/onlinedocs/gcc-4.4.3/gcc/Atomic-Builtins.html) einer eigenen Implementierung vorziehen.
edit:
@erik: xchg ist aber ungeschickt auf einem echten Multi/Manycore-System, weil es den Cache thrasht, da es ohne Bedingung schreibt, was die anderen Cores die Cacheline kostet.
-
Hallo,
Ich würde gcc atomic builtins (http://gcc.gnu.org/onlinedocs/gcc-4.4.3/gcc/Atomic-Builtins.html) einer eigenen Implementierung vorziehen.
Womit Du Dich eben vom Compiler abhängig machst.
An welches Builtin hast Du den gedacht?
xchg ist aber ungeschickt auf einem echten Multi/Manycore-System, weil es den Cache thrasht, da es ohne Bedingung schreibt, was die anderen Cores die Cacheline kostet.
In der Cacheline, in welcher die Lock-Variable liegt, sollte natürlich nichts anderes rein. Ansonsten ist das mit dem Cacheline-Trashing für die Verwendung als Lock natürlich erwünscht. In normalem Code hat der XCHG-Befehl eben nichts zu suchen, der gcc verwendet ihn wimre auch gar nicht.
Grüße
Erik
-
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.
The “bool” version returns true if the comparison is successful and newval was written. The “val” version returns the contents of *ptr before the operation.
Womit Du Dich eben vom Compiler abhängig machst.
Das macht man beim OSDev sowieso, die Frage ist wohl eher wie gut kapselt man, damit man beim Wechseln nicht alles neuschreiben muss. Außerdem macht man sich ohne builtins von der Architektur abhängig, was ich unschöner finde bzw. was mehr Probleme macht.
In der Cacheline, in welcher die Lock-Variable liegt, sollte natürlich nichts anderes rein.
Und die Cacheline ist wie groß? Das ist sicherlich nicht nur Architektur, sondern sogar prozessor-/Modelabhängig.
-
Danke für die Ratschläge.
Versuche das gerade mit den builtins.
Wie genau muss dass denn aussehen?
Irgendwie brauchen die auch nur ihr "__builtin_"-Präfix.
Sieht das dann so aus: __builtin___sync_bool_compare_and_swap(...)?
Da wird mir gesagt, dass die Funktionen nicht gefunden werden
-
Ich hab gerade festgestellt, dass ich das in lightOS noch selber implementiert hatte, insofern kannst du dir da den cmpxchg-Code mal ansehen: hier (http://repo.or.cz/w/lightOS.git/blob/HEAD:/libarch/x86/atomic.c#l82).
Wie man das buildin verwendet siehst du zB bei pedigree (http://pedigree-project.org/projects/pedigree/repository/revisions/master/entry/src/system/include/Atomic.h#L120).
-
Danke.
Jetzt funktioniert es mit den Builtin-Funktionen
-
Hallo,
ich persönlich vertraue dem cmpxchg-Befehl nicht. Ohne Lock taugt er nicht und mit Lock funktioniert er nur in Ring 0 (für wichtige Dinge ist er also nur im Kernel nutzbar). Ich weiß das in der Befehlsdokumentation steht das er mit dem lock-präfix sicher ist. Aber wenn man sich dann ansieht wie die Status-Änderungen der Cache-Lines funktionieren dann hab ich da gewisse Zweifel, kann aber auch sein dass das lock-Präfix dort was dreht (und cmpxchg sich xchg ähnlich verhält). Das der xchg-Befehl sicher dafür sorgt das die betreffende Cache-Line aus allen Caches rausfliegt hat für mich einen beruhigenden Faktor. Außerdem ist xchg bestimmt schneller da er beim Zugriff auf den Speicher gleich die zu schreibenden Daten mitgeben kann (es wird ein spezieller Speicherzugriff "gibt mir die Daten von Adresse X und schreibe Y unmittelbar danach (atomisch) an diese Stelle" benutzt, PCI-Express kennt auch so einen Zugriff, ich glaube HyperTransport kennt sowas auch) und die Atomizität im Speicherkontroller entsteht. Beim cmpxchg sind es zwei ganz normale und unabhängige Speicherzugriffe (falls das nicht gar im Cache gemacht wird), der CPU-Kern ist dafür zuständig das dieser Befehl atomar bleibt (was z.B. von einem PCI-Busmaster unterlaufen werden kann).
Von den gcc buildins sind z.B. die ganzen __sync_fetch_and_operation und __sync_operation_and_fetch gar nicht für x86 implementierbar. ARM unterstützt sowas z.B. mit speziellen Lade- und Schreib-Befehlen (ldrex und strex). Der Lade-Befehl flusht alle betreffenden Cache-Lines und erzeugt im Speicher-Controller einen Lock (der Speicher-Controller merkt sich die Adresse, Größe und welcher CPU-Kern diesen Lock initiiert hat) und die CPU kann die gelesenen Daten über mehrere Befehle atomar verarbeiten. Beim Schreib-Befehl prüft der Speicher-Controller ob der Lock noch besteht (ein zwischenzeitlicher normaler Schreib-Befehl einer anderen CPU an die betreffende Stelle hebt den Lock auf) und nur wenn der Lock noch intakt ist werden die Daten auch tatsächlich geschrieben, außerdem wird der Lock-Zustand an die CPU zurückgemeldet und der Schreib-Befehl setzt passend die Flags. Durch Abfrage der Flags kann der gesamte Vorgang, ab dem Lese-Befehl, komplett wiederholt werden falls etwas nicht gklappt hat (der Lock gestört wurde). Dieses Konzept finde ich wirklich gut, weil damit eine ganze Menge an Problemen von vornherein sicher ausgeschlossen sind, und möchte was vergleichbares auch in meiner Plattform umsetzen.
An buildins find ich __sync_lock_test_and_set und __sync_lock_release deutlich interessanter obwohl dort wieder der Nachteil ist das diese keine richtige "memory barrier" sind. Zumindest das "Test and Set" dürfte recht zuverlässig funktionieren, ob dort für x86 der xchg-Befehl oder der bts-Befehlt benutzt wird müsste man mal prüfen, ob der bts-Befehl ähnlich strickt mit Cache umgeht wie xchg weis ich nicht aber falls er ein lock-Präfix benötigt ist er auch wieder nicht für Ring 3 interessant.
Der Vorteil meines Codes von gestern ist das er auf x86 immer und unter allen Umständen (in allen Ringen) zuverlässig funktioniert. Ich hab das mal in einer C++-Klasse implementiert welche unter Windows (User-Mode-Programm) mit VisualC++ und unter ThreadX (auf ARM-CPU) mit gcc funktionieren musste.
Das mit der Cache-Line-Größe ist natürlich ein Problem, aber in der Mutex-Klasse muss man den Speicher-Platz für die Lock-Variable (einzelnes Byte reicht) ja nicht per malloc() holen sondern könnte da was eigenes bauen das immer ganze Pages vom OS holt. Ich denke das dürfte recht einfach machbar sein und nur eben das holen/zurückgeben der Pages ist Target-Abhängig. Die Pages verwaltet man einfach mit der Bit-Tabelle und gibt jedes Byte einzeln an eine Mutex-Instanz. Zusätzlich könnte man diese Pages gleich noch als Non-Cacheable markieren so das die Cache-Fluches bleiben können.
Grüße
Erik
-
Warum sollte lock nur im Ring0 funktionieren?
ich persönlich vertraue dem cmpxchg-Befehl nicht. Ohne Lock taugt er nicht und mit Lock funktioniert er nur in Ring 0 (für wichtige Dinge ist er also nur im Kernel nutzbar). Ich weiß das in der Befehlsdokumentation steht das er mit dem lock-präfix sicher ist. Aber wenn man sich dann ansieht wie die Status-Änderungen der Cache-Lines funktionieren dann hab ich da gewisse Zweifel, kann aber auch sein dass das lock-Präfix dort was dreht (und cmpxchg sich xchg ähnlich verhält). Das der xchg-Befehl sicher dafür sorgt das die betreffende Cache-Line aus allen Caches rausfliegt hat für mich einen beruhigenden Faktor. Außerdem ist xchg bestimmt schneller da er beim Zugriff auf den Speicher gleich die zu schreibenden Daten mitgeben kann (es wird ein spezieller Speicherzugriff "gibt mir die Daten von Adresse X und schreibe Y unmittelbar danach (atomisch) an diese Stelle" benutzt, PCI-Express kennt auch so einen Zugriff, ich glaube HyperTransport kennt sowas auch) und die Atomizität im Speicherkontroller entsteht. Beim cmpxchg sind es zwei ganz normale und unabhängige Speicherzugriffe (falls das nicht gar im Cache gemacht wird), der CPU-Kern ist dafür zuständig das dieser Befehl atomar bleibt (was z.B. von einem PCI-Busmaster unterlaufen werden kann).
Mein Verständnis von Caches ist eher limitiert, aber ich sehe da kein Problem mit cmpxchg. Da die Cacheline ja nur in allen anderen CPUs geflusht werden muss, wenn wirklich geschriebene wird, aber das wird cmpxchg wohl auch machen. Der Vorteil ist halt, das cmpxchg nur schreibt wenn es wirklich durfte (d.h. wenn der Wert an der Stelle der erwartete ist). Das erscheint mir zum einen korrekt zum anderen wegen weniger Cache Thrashing effizienter.
Ich würde auch vermuten, dass das read in den Cache geht (was ja korrekt ist) und danach das write erst eine "richtige" Speicheroperation ist.
Von den gcc buildins sind z.B. die ganzen __sync_fetch_and_operation und __sync_operation_and_fetch gar nicht für x86 implementierbar.
Das ist falsch, für add/sub wird die xadd Instruktion (mit lock) verwendet, was mir auf den ersten Blick völlig korrekt erscheint. Für die anderen wird cmpxchg verwendet, was auch sicherlich korrekt ist.
Abgesehen davon würde gcc einen Funktioncall einfügen, wenn er es auf der Architektur nicht unterstützen kann und das würde man wohl merken.
edit: Noch eine kleine Randnotiz falls du es selbst versuchen willst. Wenn der Rückgabewert von den Operationen nicht verwendet wird, dann optimiert der gcc das zB zu einem add mit lock.
-
Hallo,
Warum sollte lock nur im Ring0 funktionieren?
Als ich das lock-Präfix das letzte mal im Ring 3 benutzt hatte gabs ne Illegal-OpCode-Exception, kann aber auch an was anderes gelegen haben, da will ich mich jetzt nicht genau festlegen. Ich hatte halt diesen Zusammenhang irgendwie im Gedächtnis.
... aber ich sehe da kein Problem mit cmpxchg. Da die Cacheline ja nur in allen anderen CPUs geflusht werden muss, wenn wirklich geschriebene wird
Richtige Atomizität (nennt man das eigentlich so?) muss mit dem Lese-Zugriff beginnen. Jetzt überlege mal was passiert wenn 2 CPUs gleichzeitig (das ist zwar nicht sehr wahrscheinlich aber doch möglich, ich denke als kritisches Zeit-Fenster können da etwa 4 CPU-Takte (vielleicht auch deutlich mehr) gelten) auf die Lock-Variable lesend zugreifen. Beide lesen das selbe ohne das einer vom anderen weiß. Wenn Du Dir die ARM-Implementierung ansiehst dann stellst Du fest das dort das Lock mit dem Lese-Befehl erstellt wird, die Lesebefehle werden spätestens im Speicher-Controller serialisiert (einer kommt eben als erster dran), wer dort verliert hat eben nicht den Lock. Beide Lese-Befehle liefern die selben Daten und beide CPUs werden gleichartig weitermachen aber nur bei einem wird der Schreib-Befehl zurückmelden das der Lock noch intakt war und beim anderen wird der ganze Code-Abschnitt, vom Lese-Befehl an, noch mal ausgeführt. Beim xchg-Befehl auf x86 wird die Atomizität im Speichercontroller damit erzeugt das dieser das Lesen der alten Daten und das Schreiben der neuen Daten als einen Zugriff atomar ausführt, ein gleichartiger Zugriff einer anderen CPU kommt eben danach und die bekommt beim Lesen auch sicher genau die Daten welche die erste CPU geschrieben hat. Beim Schreib-Part des cmpxchg-Befehls gibt es eben keine Rückmeldung das jemand anderes in der Zwischenzeit auch gelesen oder gar geschrieben hat. So könnten möglicherweise mehrere CPUs ermittelt haben das der Mutex/Spinlock/Semaphore vorher frei war und dann mehrere CPUs gleichzeitig drin sind. Idealer weise dürfte zwischen dem Lesen und dem zugehörigen Schreiben kein weiterer Zugriff, weder lesen noch schreiben, auf die Lock-Variable möglich sein, eben genau so wie es xchg immer macht. ARM hat das komplizierte mit einbeziehen des Speicher-Controllers, der ja gar nicht zur CPU gehört, nicht ohne Grund gemacht. Als kleine Optimierung könnte der Lesebefehl gleich zurückmelden ob der Lock überhaupt erstellt werden konnte, so das die CPU nicht vergeblich rechnen muss, so möchte ich es jedenfalls machen.
Der Vorteil ist halt, das cmpxchg nur schreibt wenn es wirklich durfte (d.h. wenn der Wert an der Stelle der erwartete ist).
Und genau da ist das Problem. Ich weiß nicht ob das lock-Präfix an diesem Verhalten nachbessert aber alles was ich bis jetzt über diesen Befehl gelesen hab lässt mich zweifeln. Möglicherweise sind meine Zweifel unbegründet, immerhin wird der cmpxchg-Befehl ja auch explizit für Semaphoren und Mutexes empfohlen und die Intel-Leute wissen hoffentlich was sie tun, aber ich persönlich bleibe (bei einer so elementaren/wichtigen Funktion) lieber auf der sicheren Seite.
Das erscheint mir zum einen korrekt zum anderen wegen weniger Cache Thrashing effizienter. Ich würde auch vermuten, dass das read in den Cache geht (was ja korrekt ist) und danach das write erst eine "richtige" Speicheroperation ist.
Wenn man davon ausgeht das Lock-Variablen prinzipiell nicht in den Cache dürfen, damit beim lesen auch immer der wirklich aktuelle Wert geliefert wird, dann ist xchg IMHO der effizientere Befehl.
Von den gcc buildins sind z.B. die ganzen __sync_fetch_and_operation und __sync_operation_and_fetch gar nicht für x86 implementierbar.
Das ist falsch, für add/sub wird die xadd Instruktion (mit lock) verwendet, was mir auf den ersten Blick völlig korrekt erscheint. Für die anderen wird cmpxchg verwendet, was auch sicherlich korrekt ist.
Okay, den Befehl kannte ich noch nicht. Das trifft aber nur auf __sync_fetch_and_add und __sync_fetch_and_sub zu. Die andere Variante __sync_add_and_fetch und __sync_sub_and_fetch gehen trotzdem nicht. Und alle anderen Rechenarten eben auch nicht. Oder gibt es da noch mehr Befehle die ich (noch) nicht kenne?
Wenn der Rückgabewert von den Operationen nicht verwendet wird, dann optimiert der gcc das zB zu einem add mit lock.
Das erwarte ich eigentlich auch.
Grüße
Erik
-
Warum sollte lock nur im Ring0 funktionieren?
Als ich das lock-Präfix das letzte mal im Ring 3 benutzt hatte gabs ne Illegal-OpCode-Exception, kann aber auch an was anderes gelegen haben, da will ich mich jetzt nicht genau festlegen. Ich hatte halt diesen Zusammenhang irgendwie im Gedächtnis.
Wenn das nur aufgrund des Privileglevels nicht funktioniert, sollte es aber einen GPF geben (wie bei IN, OUT, CLI, ...).
-
zu dem Zeug mit den Caches: Wie gesagt, ich habe wenig Ahnung davon, aber ich gehe davon aus, dass es funktioniert wenn es so in den Intel-Manuals steht und noch dazu von Compiler, etc. verwendet wird.
Außerdem bringt loch offensichtlich keine Exceptions. Ich habe wie oben erwähnt die Ops unter gcc compiliert, disassembliert und getestet. Das lief einwandfrei und verwendet lock. Einen Invalid Opcode liefert es nur dann, wenn man es mit beliebigen Instruktionen versucht zu verwenden. Eine Liste der erlaubten findet sich in den Intel Manuals unter der lock-Instruktion/Präfix.
Die andere Variante __sync_add_and_fetch und __sync_sub_and_fetch gehen trotzdem nicht. Und alle anderen Rechenarten eben auch nicht. Oder gibt es da noch mehr Befehle die ich (noch) nicht kenne?
Ohne es jetzt auszuprobieren, geht das doch genauso mit einem cmpxchg. Wenn es den Wert austauscht, dann weiß ich welcher Wert vorher dort stand.
edit: Ich wüsste ad hoc nicht wie du mit deinem xchg eine Semaphore implementierst.
edit2: aus den Intel Manuals
To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)
Das kommt dann wohl auf das gleiche wie das xchg raus.
-
Hallo,
aber ich gehe davon aus, dass es funktioniert wenn es so in den Intel-Manuals steht und noch dazu von Compiler, etc. verwendet wird.
Ist ein Argument. Mich persönlich überzeugt allein die Aussage "es geht" nicht, ich möchte auch das die Beschreibung "wie es geht" mir den Eindruck vermittelt das es "wirklich geht" und genau das vermisse ich bei cmpxchg. Ich sehe einfach nicht wie die vorhin beschriebenen Probleme absolut zuverlässig vermieden werden sollen. Aber das ist nur mein persönlicher subjektiver Eindruck, die absolute Wahrheit zu diesem Thema kenn ich auch nicht.
Ohne es jetzt auszuprobieren, geht das doch genauso mit einem cmpxchg. Wenn es den Wert austauscht, dann weiß ich welcher Wert vorher dort stand.
Jetzt verstehe ich was Du meinst: man lädt den Wert der im Speicher steht, verrechnet ihn und der cmpxchg-Befehl prüft am Schluss ob er zwischenzeitlich im Speicher modifiziert wurde. Wenn nein dann wird der neue Wert geschrieben und wenn ja dann wird der ganze Vorgang wiederholt. Hab ich das jetzt richtig verstanden?
Ich wüsste ad hoc nicht wie du mit deinem xchg eine Semaphore implementierst.
So wie ich gestern Nachmittag in meinem 4-Zeiler gezeigt hab. xchg schreibt immer den Wert für belegt. Falls der vorher schon drin war hat sich nichts geändert und falls nicht dann ist der Lock ab jetzt belegt. Falls der gelesene (alte) Wert belegt signalisiert dann war der Lock bereits (von wen anders) belegt und der Vorgang muss wiederholt werden, wenn vorher nicht belegt war dann ist der aktuelle Code jetzt der Eigentümer vom Lock.
Bevor ARM die tollen Lese- und Schreib-Befehle (mit dem Lock im Speicher-Controller) eingeführt hat war das die einzigste Möglichkeit auf ARM einen zuverlässigen Lock zu bauen, nur das der Befehl dort swp heißt (er ist aber genauso strickt atomar wir xchg von x86).
http://www.doulos.com/knowhow/arm/Hints_and_Tips/Implementing_Semaphores/
Grüße
Erik
-
Ohne es jetzt auszuprobieren, geht das doch genauso mit einem cmpxchg. Wenn es den Wert austauscht, dann weiß ich welcher Wert vorher dort stand.
Jetzt verstehe ich was Du meinst: man lädt den Wert der im Speicher steht, verrechnet ihn und der cmpxchg-Befehl prüft am Schluss ob er zwischenzeitlich im Speicher modifiziert wurde. Wenn nein dann wird der neue Wert geschrieben und wenn ja dann wird der ganze Vorgang wiederholt. Hab ich das jetzt richtig verstanden?
Ja hast du.
Ich wüsste ad hoc nicht wie du mit deinem xchg eine Semaphore implementierst.
So wie ich gestern Nachmittag in meinem 4-Zeiler gezeigt hab. xchg schreibt immer den Wert für belegt. Falls der vorher schon drin war hat sich nichts geändert und falls nicht dann ist der Lock ab jetzt belegt. Falls der gelesene (alte) Wert belegt signalisiert dann war der Lock bereits (von wen anders) belegt und der Vorgang muss wiederholt werden, wenn vorher nicht belegt war dann ist der aktuelle Code jetzt der Eigentümer vom Lock.
Ich meinte mit Semaphore (siehe auch Wikipedia (http://de.wikipedia.org/wiki/Semaphor_%28Informatik%29)) keine einfache Mutex, sondern einen Zähler. Der Zähler gibt die Zahl der Threads an die noch in den Bereich eintreten dürfen, d.h. es geht nicht nur darum ein Bit zu setzen oder zu löschen sondern auch darum korrekt zu zählen, das kann aber ein xchg nicht.
Man kann natürlich den Zähler über ne Mutex/Lock schützen, aber mit cmxchg geht es halt direkt.
-
Hallo,
edit2: aus den Intel Manuals
To simplify the interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is written into the destination. (The processor never produces a locked read without also producing a locked write.)
Das kommt dann wohl auf das gleiche wie das xchg raus.
Das erklärt aber nicht wie verhindert werden soll das wenn 2 CPUs per cmpxchg zur (fast) gleichen Zeit den Lesezugriff ausführen das diese dann unterschiedliche Daten bekommen damit eben nur eine von beiden denkt der Lock wäre noch frei. Wenn beide den Lock als frei betrachten (weil beide den selben Wert gelesen haben) werden auch beide sich als neuen Besitzer fühlen, daran ändern auch nichts die 2 Schreibzugriffe (egal in welcher Reihenfolge) die beide den selben Wert (für belegt) schreiben. (ich gehe hierbei von einem simplen Lock aus)
Ich bleibe dabei das ich noch keine schlüssige Begründung gelesen hab warum der cmpxchg-Befehl sicher immer zuverlässig funktioniert. Beim xchg kann man die Sicherheit recht einfach nachvollziehen (atomarer Daten-Austausch, so wie auch beim swp von ARM), beim cmpxchg fallen mir eben Möglichkeiten ein wo es schief geht. Solange diese Möglichkeiten nicht absolut nachvollziehbar ausgeschlossen werden verwende ich cmpxchg nicht. Das ist meine persönliche Entscheidung, was der Rest der Welt macht ist mir in diesem Punkt egal. Ich fürchte ohne einen kompetenten Mitarbeiter von Intel werden wir diese Frage nicht klären können.
Ich meinte mit Semaphore ....
Sorry, diese Begriffe bringe ich schon mal durcheinander. :oops:
Grüße
Erik
-
Es könnte sein, dass das Kapitel 7.1 in den Intel® 64 and IA-32 Architectures Software Developer’s Manual 3A dir die Lösung dazu verrät. Garantieren kann ichs natürlich nicht, da ich das gerade erst angefangen habe zu lesen und außerdem von Hardwaredingen nicht sonderlich viel verstehe. Ich zitiere trotzdem mal ein bisschen:
These mechanisms are interdependent in the following ways. Certain basic memory transactions (such as reading or writing a byte in system memory) are always guaranteed to be handled atomically. That is, once started, the processor guarantees that the operation will be completed before another processor or bus agent is allowed access to the memory location. The processor also supports bus locking for performing selected memory operations (such as a read-modify-write operation in a shared area of memory) that typically need to be handled atomically, but are not automatically handled this way. Because frequently used memory locations are often cached in a processor’s L1 or L2 caches, atomic operations can often be carried out inside a processor’s caches without asserting the bus lock. Here the processor’s cache coherency protocols insure that other processors that are caching the same memory locations are managed properly while atomic operations are performed on cached memory locations.
Das "[...] or bus agent" w+rde für mich bedeuten, dass deine PCI-Geräte kein Problem sind und der Rest bedeutet für mich, dass ich mich nicht darum kümmern muss wie genau es funktioniert, sondern das der Prozessor einfach dafür sorge trägt.
edit: Deine Paranoia bei genau dem Befehl verstehe ich ehrlich gesagt nicht wirklich... Bei jedem anderem vertraust du Intel, aber genau hier nicht? Außerdem wurde der Befehl exakt für Multiprozessorsysteme eingeführt. Da ist es unvorstellbar, dass es Randfälle geben soll die nicht abgedeckt sein sollen.
-
Das erklärt aber nicht wie verhindert werden soll das wenn 2 CPUs per cmpxchg zur (fast) gleichen Zeit den Lesezugriff ausführen das diese dann unterschiedliche Daten bekommen damit eben nur eine von beiden denkt der Lock wäre noch frei. Wenn beide den Lock als frei betrachten (weil beide den selben Wert gelesen haben) werden auch beide sich als neuen Besitzer fühlen, daran ändern auch nichts die 2 Schreibzugriffe (egal in welcher Reihenfolge) die beide den selben Wert (für belegt) schreiben. (ich gehe hierbei von einem simplen Lock aus)
Ich bleibe dabei das ich noch keine schlüssige Begründung gelesen hab warum der cmpxchg-Befehl sicher immer zuverlässig funktioniert. Beim xchg kann man die Sicherheit recht einfach nachvollziehen (atomarer Daten-Austausch, so wie auch beim swp von ARM), beim cmpxchg fallen mir eben Möglichkeiten ein wo es schief geht. Solange diese Möglichkeiten nicht absolut nachvollziehbar ausgeschlossen werden verwende ich cmpxchg nicht. Das ist meine persönliche Entscheidung, was der Rest der Welt macht ist mir in diesem Punkt egal. Ich fürchte ohne einen kompetenten Mitarbeiter von Intel werden wir diese Frage nicht klären können.
Das ganze funktioniert nach dem Cache-Prinzip.
Die CPUs haben Cache-Kohärenz-Protokolle, die genau das sichern.
Wenn eine CPU auf einen Speicher zugreifen möchte, meldet er sich als Owner an, falls es keinen Owner gibt.
Wenn es einen Owner gibt, schreibt er den Wert in den RAM und meldet sich als Owner ab.
Der neue wird dann Owner und schreibt dort etwas rein.
Wenn eine andere CPU diese Adresse im Cache hat, wird die auf dirty gesetzt und wenn nötig neu geladen, bzw. der Owner wird aufgefordert den aktuellen Wert in den RAM zu schreiben, damit alle wieder aktuelle Werte haben.
Dieses einfache Owner-Prinzip garantiert, dass so etwas wie zeitgleiches Schreiben nicht funktioniert.
Und das geht auch nicht, da die CPUs über einen eigenen Bus kommunizieren und jede CPU, die schreiben möchte und kein Owner ist, braucht von allen anderen CPUs eine Bestätigung.
Gruß,
rizor
EDIT:
Intel hatte in den Anfängen dieses Befehls eine Bug, der unter Umständen kurzzeitig falsche Werte im Cache haben könnte, darum sollte man nach dem Befehl kurz ein busywait haben und dann noch einmal abfragen.
Das gehört aber der Vergangenheit an.
-
erik hat nicht von zeitgleichem Schreiben gesprochen, sondern von dem Lese-danach-Schreiben während eines compare and exchange, d.h. es geht um
CPU0 liest
CPU1 liest
CPU1 schreibt
CPU0 schreibt
Dann kommt eventuell Mist raus, was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.
edit: Zahlen korrigiert :|
-
erik hat nicht von zeitgleichem Schreiben gesprochen, sondern von dem Lese-danach-Schreiben während eines compare and exchange, d.h. es geht um
CPU0 liest
CPU1 liest
CPU1 schreibt
CPU2 schreibt
Dann kommt eventuell Mist raus, was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.
Genau das kann nicht gehen, denn es gibt einen Owner und der verwaltet.
Wenn nun sagen wir CPU1 owner ist, darf CPU2 nicht schreiben und CPU0 bekommt nach "CPU1 schreibt" ein Dirty-Flag.
CPU2 darf erst schreiben, wenn sich 1 als Owner abmelden darf, somit werden die Befehle nacheinander ausgeführt.
Wenn nun CPU2 owner wär, dürfte CPU1 nicht einfach schreiben, sondern muss warten, bsi CPU2 fertig ist
-
Ich habe die Zahlen geändert, aber ich sehe nicht warum das MESI-Protokoll sowas verhindern würde (wenn man mal von Atomizität bei cmpxchg absieht).
-
Aber genau darauf basiert das.
Wenn du keine atomaren Befehle verwendest, kann es natürlich sein, dass zwischendurch ein anderer Owner wird und du nicht mitbekommst, dass jemand schon einen anderen Wert vreingeschrieben hast, da du ja danach nur noch auf Registern arbeitest (meistens)
-
Ich sags nochmal: erik bezweifelt, dass die Atomizität von Lese+Schreibbefehl hardwaretechnisch möglich ist. Ich stimme dir insofern zu, als dass ich das für unwahrscheinlich halte, va. weil sonst der Befehl cmpxchg komplett überflüssig ist.
-
Wieso soll der nicht atomar sein?
Atomar heißt ja nicht, dass das ganze in einem Takt durch zuziehen ist.
Es kann doch auch sein, dass er in den ersten paar Takten liest und danach schreibt.
Er darf in der Zeit halt nur nicht auf der IRQ-Leitung und der CPU-Kommunikations-Leitung lauschen.
Die müssen währenddessen einfach ignoriert werden, dann ist das ganze Atomar.
Die x86er haben ja auch kaum Befehle, die in einem Takt durchführbar sind
-
Hallo,
Es könnte sein, dass das Kapitel 7.1 in den Intel® 64 and IA-32 Architectures Software Developer’s Manual 3A dir die Lösung dazu verrät....
Genau das ist die Sorte Text die mir missfällt. Da steht einfach nur "vertrau uns". Wenn dort der Weg beschreiben wäre und dieser Weg wäre plausibel dann würde ich Intel auch tatsächlich vertrauen, aber so leider nicht.
Beim xchg-Befehl ist die Funktionsbeschreibung vollständig und nachvollziehbar aber vor allem auch Vertrauenerweckend (es lassen sich keine prinzipiellen Fehler o.ä. finden).
Deine Paranoia bei genau dem Befehl verstehe ich ehrlich gesagt nicht wirklich... Bei jedem anderem vertraust du Intel, aber genau hier nicht?
Das liegt einfach da ran das dieser Befehl so elementar wichtig ist aber man seine Zuverlässigkeit nicht wirklich prüfen kann. Eine ALU oder FPU kann man mit vielen Beispielrechnungen prüfen ob immer das richtige Ergebnis raus kommt, bei der Atomizität geht das nicht. Man kann zwar prüfen ob das Restrisiko nahe 0 ist, aber man kann eben nicht auf genau 0 prüfen.
Außerdem wurde der Befehl exakt für Multiprozessorsysteme eingeführt. Da ist es unvorstellbar, dass es Randfälle geben soll die nicht abgedeckt sein sollen.
Da gebe ich Dir zwar Recht, aber ich habe schon von verschiedenen Leuten gehört das die Cache-Kohärenz-Protokolle eine ziemlich komplizierte (und damit fehlerträchtige) Angelegenheit sind, deshalb bevorzuge ich Wege die mit wenig Aufwand und wenig Komplexität ein zuverlässiges Ergebnis bringen.
Da die betreffende Cache-Line eh bei jedem betreten des Lock getrasht wird (dann wird ja auch ein Schreibzugriff für die Statusänderung auf belegt durchgeführt) bin ich der Meinung das diese Lock-Variablen erst gar nicht in den Cache rein dürfen. Wenn die Lock-Variablen eh nicht im Cache sind dann ist der xchg-Befehl aber auch deutlich schneller. Gerade bei sehr vielen CPUs verursacht das Cache-Kohärenz-Protokoll aber einen erheblichen Overhead so das der cmpxchg-Befehl mit Sicherheit deutlich langsamer ist.
Dieses einfache Owner-Prinzip garantiert, dass so etwas wie zeitgleiches Schreiben nicht funktioniert.
Intel hat keinen "Owner", dort gibt es nur MESI ohne O. Außerdem springt das Cache-Kohärenz-Protokoll erst an wenn geschrieben wird, es könnte natürlich sein dass das lock-Präfix beim cmpxchg hier noch mal was dreht aber das geht aus den Intel-Dokus nicht hervor. Dort wird doch beschrieben das der cmpxchg erst dann nach außen spürbare Auswirkungen hat wenn auch geschrieben wird.
Was ist wenn bei beiden CPUs die Daten nicht im Cache sind? Dann kommen 2 ganz normale Speicher-Lese-Zugriffe. Ich kann nicht erkennen wie damit die Atomizität gewährleistet werden soll.
erik hat nicht von zeitgleichem Schreiben gesprochen,
Es geht mir darum das zwischen dem Lesen und dem Schreiben der einen CPU eine andere überhaupt die Lock-Variable lesen kann (ohne das eine von beiden CPUs das bemerkt). Der Lese-Zugriff der anderen CPU bringt die selben Daten und damit geht die andere CPU eben auch davon aus (so wie die erste CPU) das der Lock noch frei ist und fühlt sich hinterher als rechtmäßiger Besitzer (so wie auch die erste CPU). Daran ändert auch nichts das dann beide CPUs später einen "irgendwie gesicherten" Schreibzugriff durchführen (beide mit den selben Daten), dann ist es schließlich schon zu spät. Die Entscheidung (Lock bekommen oder nicht) wird zwischen dem Lese-Zugriff und dem Schreib-Zugriff getroffen und alles externe was zwischen diesen Zugriffen passiert beeinflusst diese Entscheidung eben nicht.
....was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.
So sollte es sein, aber den Intel-Dokus kann man nicht entnehmen das es wirklich so ist.
Atomar heißt ja nicht, dass das ganze in einem Takt durch zuziehen ist.
Es kann doch auch sein, dass er in den ersten paar Takten liest und danach schreibt.
Beides Richtig.
Er darf in der Zeit halt nur nicht auf der IRQ-Leitung und der CPU-Kommunikations-Leitung lauschen.
Die müssen währenddessen einfach ignoriert werden, dann ist das ganze Atomar
Hä? :? Ich will ja nicht unhöflich sein aber Du schreibst da wirres Zeugs.
Grüße
Erik
-
Was ist wenn bei beiden CPUs die Daten nicht im Cache sind? Dann kommen 2 ganz normale Speicher-Lese-Zugriffe. Ich kann nicht erkennen wie damit die Atomizität gewährleistet werden soll.
Und warum darf die eine CPU nicht während Lesen+Schreiben ein #LOCK hochziehen?
erik hat nicht von zeitgleichem Schreiben gesprochen,
Es geht mir darum das zwischen dem Lesen und dem Schreiben der einen CPU eine andere überhaupt die Lock-Variable lesen kann (ohne das eine von beiden CPUs das bemerkt). Der Lese-Zugriff der anderen CPU bringt die selben Daten und damit geht die andere CPU eben auch davon aus (so wie die erste CPU) das der Lock noch frei ist und fühlt sich hinterher als rechtmäßiger Besitzer (so wie auch die erste CPU). Daran ändert auch nichts das dann beide CPUs später einen "irgendwie gesicherten" Schreibzugriff durchführen (beide mit den selben Daten), dann ist es schließlich schon zu spät. Die Entscheidung (Lock bekommen oder nicht) wird zwischen dem Lese-Zugriff und dem Schreib-Zugriff getroffen und alles externe was zwischen diesen Zugriffen passiert beeinflusst diese Entscheidung eben nicht.
siehe oben, abgesehen davon bin ich nicht dumm, du brauchst das Problem nicht 3mal wiederholen, ich habe es auch beim ersten Mal verstanden, aber ich sehe nicht warum man das nicht in Hardware implementieren können sollte mit #LOCK zB.
....was aber nicht sein kann, dass das Lesen+Schreiben zusammen atomar ist.
So sollte es sein, aber den Intel-Dokus kann man nicht entnehmen das es wirklich so ist.
Das es atomar ist kann man den Dokus schon entnehmen, warum es funktioniert nicht, aber das ist auch nicht Ziel der Manuals.
-
Ist xchg wirklich so anders als cmpxchg? Also ich nehme mal an, dass auf dem Datenbus nicht gleichzeitig Daten in beide Richtungen fließen können. Der Befehl xchg muss auch erst lesen und dann schreiben. Damit müsste xchg an den selben Problemen wie die hier für cmpxchg beschriebenen leiden, sofern diese existieren.
Gerade bei sehr vielen CPUs verursacht das Cache-Kohärenz-Protokoll aber einen erheblichen Overhead so das der cmpxchg-Befehl mit Sicherheit deutlich langsamer ist.
Genauso langsam wie xchg, da die selben Protokolle verwendet werden.
A LOCK prefix typically costs more than a hundred clock cycles, even on single-processor systems. This also applies to the XCHG instruction with a memory operand.
-
xchg liest nicht, sondern vertauscht nur.
Ich... sehe...
-
Hallo,
Und warum darf die eine CPU nicht während Lesen+Schreiben ein #LOCK hochziehen?
Das darf sie schon. Aber es soll ja gerade der Vorteil von cmpxchg sein das erst beim Schreibzugriff, falls dieser überhaupt notwendig ist, entsprechende Sicherungsprotokolle benutzt werden. Das ist doch der Vorteil von cmpxchg gegenüber von xchg, oder irre ich da?
abgesehen davon bin ich nicht dumm, du brauchst das Problem nicht 3mal wiederholen, ich habe es auch beim ersten Mal verstanden, aber ich sehe nicht warum man das nicht in Hardware implementieren können sollte mit #LOCK zB.
Entschuldige bitte, aber ich hatte nicht den Eindruck das Du verstehst warum ich xchg vertraue und cmpxchg nicht. Bei cmpxchg hast Du immer gesagt das der Lesezugriff noch keine (wirksamen) Sicherheitsmaßnahmen ergreift (und sogar nur im Cache arbeiten könnte) und das finde ich einfach nicht vertrauenerweckend.
Ich habe nie gesagt das man cmpxchg nicht sicher implementieren kann (alle anderen CPU-Hersteller können sowas oder ähnliches ja schließlich auch), ich sage nur das Intel sich dazu ausschweigt und ich aufgrund dessen kein Vertrauen zum cmpxchg habe. Die Infos die man über cmpxchg findet sind wage bzw. widersprüchlich und das schreckt mich eben ab.
Das es atomar ist kann man den Dokus schon entnehmen, warum es funktioniert nicht, aber das ist auch nicht Ziel der Manuals.
Da haben wir offensichtlich verschiedene Ansichten bezüglich einer CPU-Dokumentation. Bei anderen Herstellern werden solche Mechanismen sehr ausführlich erläutert, ARM ist da nur ein Beispiel von vielen, was auch eindeutig die elementare Wichtigkeit solcher Details zeigt (SMP ist schließlich sehr im kommen). Bei Intel geht das offensichtlich nicht (jedenfalls nicht bei cmpxchg aber bei xchg schon) und das stört mich.
Ist xchg wirklich so anders als cmpxchg? Also ich nehme mal an, dass auf dem Datenbus nicht gleichzeitig Daten in beide Richtungen fließen können. Der Befehl xchg muss auch erst lesen und dann schreiben. Damit müsste xchg an den selben Problemen wie die hier für cmpxchg beschriebenen leiden, sofern diese existieren.
Beim xchg-Befehl werden die Schreibdaten gleich mit in die Lese-Anforderung rein gepackt. Die Atomizität entsteht im Speichercontroller weil dieser den einen Job, mit 2 gegensätzlichen Speicherzugriffen, atomar ausführt. Einen Speichercontroller so zu entwickeln das er Jobs (auch wenn sie aus mehreren Teilen bestehen) seriell ausführt ist ungleich einfacher als die Entwicklung eines zuverlässigem Cache-Kohärenz-Protokolls. Wenn die Lock-Variable in keinem Cache ist wird für xchg auch kein Cache-Kohärenz-Protokoll benötigt und wenn doch dann müssen die betreffenden Cache-Lines nur zurückgeschrieben oder invalidiert werden, das ist deutlich simpler und wahrscheinlich auch schneller.
A LOCK prefix typically costs more than a hundred clock cycles, even on single-processor systems. This also applies to the XCHG instruction with a memory operand.
Das ist auch kein Wunder weil der CPU-Kern ja vom absenden der speziellen Leseanforderung (mit den Schreibdaten) bis zur Antwort (mit den Lesedaten) untätig warten muss, 100 Takte sind da in größeren Systemen bestimmt noch optimistisch gerechnet. Wenn cmpxchg keine (IMHO unzulässigen) Optimierungen machen würde wäre es kein Stück schneller, da ich davon ausgehe (ohne es genau zu wissen) das sich cmpxchg mit lock-Präfix ähnlich verhält ist es sicher nicht schneller als xchg.
Ich sehe da eher noch ein anderes Performance-Problem: die Speicherstelle mit der Lock-Variable muss irgendwie vom Lesezugriff bis zum Schreibzugriff gesichert werden, in dieser Zeit können keine anderen CPUs auf diese Lock-Variable (oder die gesamte Cache-Line) zugreifen. Beim xchg wird der Speichercontroller nur so lange blockiert wie 2 DRAM-Zugriffe dauern (eigentlich nur 1 Zugriff plus ein paar Take fürs schreiben da die RAS/CAS-Zyklen ja nur einmal beim Lesezugriff benötigt werden).
Wirklich klären können wir das wohl nur mit einem kompetenten CPU-Entwickler von Intel.
Grüße
Erik
-
Hallo,
Und warum darf die eine CPU nicht während Lesen+Schreiben ein #LOCK hochziehen?
Weil es kein #LOCK-Signal mehr gibt. Das war früher, wo es noch einen einzigen zentralen Frondside-BUS gab an dem alle CPUs hingen, mal aktuell aber seit den Opterons mit dem HyperTransport-Netzwerk oder den Core i7 mit dem QPI-Netzwerk gibt es keine zentrale Stelle mehr über die alle Speicherzugriffe müssen und an der man ein #LOCK-Signal implementieren könnte. Diese Aufgabe muss jetzt das dezentralisierte Cache-Kohärenz-Protokoll übernehmen und das ist gerade bei vielen CPUs ein sehr komplexes System. Weder von Intel noch von AMD bekommt man da irgendwelche Infos wie das genau funktioniert. Da jedes Byte im Speicher aber einen Heimat-Speichercontroller hat würde es sich gerade hier anbieten den xchg-Mechanismus zu nutzen und die Lock-Variablen nie in einen Cache zu lassen.
Natürlich könnte der CPU-Kern beim cmpxchg-Befehl mit lock-Präfix vor dem Lesezugriff die betreffende Cache-Line zur exklusiven Nutzung reservieren. Aber was ist wenn mehrere CPUs sich zeitgleich dazu entschließen, dann müsste das Cache-Kohärenz-Protokoll einen Gewinner ermitteln und allen beteiligten diesen Gewinner mitteilen bevor auch nur der eigentliche Daten-Inhalt der betreffenden Cache-Line zur Gewinner-CPU geschickt wird. Das ist natürlich alles möglich (wenn auch etwas komplex) aber es ist sicher nicht schneller als xchg (selbst wenn hier Cache-Lines getrasht werden müssen). Genau da ist gerade der Widerspruch, da ja gesagt wird das cmpxchg nur im Schreibfall solch aufwendige Maßnahmen ergreift.
Entweder funktioniert der cmpxchg-Befehl nicht ordentlich oder Intel belügt uns was dessen Performance/Implementierung angeht, ich persönlich tippe auf letzteres. Vertrauen wird so definitiv nicht geschaffen.
Grüße
Erik
-
Das klingt ja immer mehr nach Verschwörungstheorie. Deine Meinung ist also, dass Intel - Hersteller von Prozessoren mit Milliarden Transitoren - vorsätzlich ein fehlerhaftes Lockingprotokoll implementiert, weil der korrekte Weg zu kompliziert wäre?
Edit: Außerdem lockt cmpxchg bereits beim Lesen.
-
Hallo,
Das klingt ja immer mehr nach Verschwörungstheorie. Deine Meinung ist also, dass Intel - Hersteller von Prozessoren mit Milliarden Transitoren - vorsätzlich ein fehlerhaftes Lockingprotokoll implementiert, weil der korrekte Weg zu kompliziert wäre?
Nein, ich denke schon das Intel es ordentlich macht, aber wenn Intel den cmpxchg-Befehl ordentlich implementiert dann ist er definitiv langsamer (und aufwändiger) als xchg. Ich schrieb doch eindeutig das ich Intel als Lügner und Geheimniskrämer betrachte.
da ich davon ausgehe (ohne es genau zu wissen) das sich cmpxchg mit lock-Präfix ähnlich verhält ist es sicher nicht schneller als xchg.
Hier hab ich mich geirrt. cmpxchg kann sich nicht so wie xchg verhalten weil es die gelesenen Daten ja erst prüft bevor eventuell ein Schreibzugriff ausgelöst wird. Die Simplizität von xchg, wegen seinem bedingungslosen schreiben, kann der cmpxchg-Befehl mit lock-Präfix gar nicht erreichen.
Edit
Edit: Außerdem lockt cmpxchg bereits beim Lesen.
Logisch betrachtet muss es ja auch so sein (schreib ich doch schon die ganze Zeit), aber dann frage ich mich woher der beworbene Performancevorteil kommt.
Grüße
Erik
-
Logisch betrachtet muss es ja auch so sein (schreib ich doch schon die ganze Zeit), aber dann frage ich mich woher der beworbene Performancevorteil kommt.
Hier im Thread wurde das geringere Cache Thrashing als Vorteil genannt. Außerdem ist die Semantik von cmpxchg eine andere als alles, was du mit xchg + weitere Befehle bauen kannst. Also es lassen sich zum Beispiel Algorithmen implementieren, die mit xchg nicht machbar sind, beziehungsweise bessere "Performance" (z.B. wait-freedom) haben.
-
Hallo,
Außerdem ist die Semantik von cmpxchg eine andere als alles, was du mit xchg + weitere Befehle bauen kannst. Also es lassen sich zum Beispiel Algorithmen implementieren, die mit xchg nicht machbar sind, beziehungsweise bessere "Performance" (z.B. wait-freedom) haben.
Das mit cmpxchg bestimmte Dinge "einfacher" (zumindest für den Assembler-Programmierer) gehen steht außer Frage. xchg ist nur für einfache Locks geeignet so wie eben ein klassischer Test-and-Set-Befehl, aber diese Aufgabe beherrscht xchg mit maximaler Effizienz.
Hier im Thread wurde das geringere Cache Thrashing als Vorteil genannt.
Okay, dann wollen wir uns das mal an einem Beispiel ansehen:
Ich bleibe bewusst bei einem einfachen Lock (0x00 für frei und 0x01 für belegt) und beziehe mich für die xchg-Variante auf meinen 4-Zeiler vom 17.03.
Folgende Umgebung: 8 CPUs (Anzahl der Kerne pro CPU lassen wir der Einfachheit halber mal bei 1), jede mit eigenem Speicher in einem modernem ccNUMA-CPU-Netzwerk (ob per HyperTransport oder QPI ist auch egal, ich denke die Unterschiede sind gering, auch wenn AMD und Intel das natürlich ganz anders darstellen).
A--B--C--D
| | | |
E--F--G--H
Die CPUs A und H wollen (fast) zeitgleich einen Lock betreten dessen Lock-Variable (einfaches Byte) im Speicher der CPU G liegt. Der Lock ist momentan frei, also 0x00. Falls die Cache-Line mit der Lock-Variable in einem Cache liegt (was nicht in jedem meiner Szenarien so ist) dann modifiziert in CPU D.
- xchg-Szenario:
Das Lock-Byte liegt in keinem Cache weil die betreffende Page als non-cachable markiert ist. Die CPUs A und H schicken jeweils eine Locked-Exchange-Anfrage an CPU G, die enthaltenden Schreibdaten sind jeweils 0x01. Eine von beiden Anfrage erreicht die CPU G als erstes und der Memory-Controller antwortet mit einer 0x00 für den Gewinner und mit 0x01 für den Verlierer. Die Gewinner-CPU weiß das der Lock vorher frei war und fühlt sich zu recht als neuer Eigentümer (in der Lock-Variable steht nun sicher 0x01) und die Verlierer-CPU weiß das der Lock bereits belegt war und versucht es noch mal. Ich denke das Szenario ist recht klar und mann kann sich ziemlich genau ausrechnen wie lange der xchg-Befehl dauert: 2 * Transport-Zeit der Messages und ein mal DRAM-Zugriff (fürs Lesen, das Schreiben auf eine bereits aktive DRAM-Zeile können wir jetzt mal vernachlässigen), insgesamt ist das einem normalem Lesezugriff sehr ähnlich. Selbst wenn der Speicher-Controller die Jobs umsortieren sollte ist das kein Problem, dann gewinnt eben die andere CPU. Ein Cache-Kohärenz-Protokoll ist nicht erforderlich weil ja non-cachable. Der Zeitbedarf für vorher frei und vorher belegt ist logischerweise immer gleich.
Falls die Lock-Variable in einem der Caches liegt, was bei einer als cachable gekennzeichneten Page ja sein kann, dann muss vorher natürlich eine Write-Backe-Message an alle CPUs übermittelt werden. Wie lange das dauert kann ich nicht genau sagen aber es ist möglicherweise eventuell länger als der xchg-Befehl an sich braucht. Die CPU, welche den xchg-Befehl ausführt, müsste entweder pauschal eine bestimmte Zeit warten oder von der entferntesten CPU eine Rückmeldung bekommen. Alternativ, zur Beschleunigung, könnte man die Locked-Exchange-Anfrage einfach hinter der Write-Back-Message hinterher schicken und alle CPUs müssten dafür sorgen das sich die Messages nicht überholen, das heißt das bei einer CPU wo die betreffende Cache-Line modifiziert ist diese zuerst geschrieben werden muss und dann die 2 Messages erst weitergeleitet werden dürften. Falls die Locked-Exchange-Anfrage (welche natürlich nicht vervielfältigt werden darf, im Gegensatz zur Write-Back-Message welche ja an alle CPUs gebroadcastet werden muss) von CPU A über CPU E geleitet wird und die modifizierte Cache-Line in CPU D ist dann wird das zwar etwas kompliziert aber ist bestimmt noch möglich, CPU G müsste die Locked-Exchange-Anfrage so lange verzögern bis alle Write-Backes durchgeführt wurden. Den Zeitbedarf für dieses Cache-Kohärenz-Protokoll kann ich nur schwer abschätzen, mit allen Optimierungen sollte es etwas weniger sein als der xchg-Befehl alleine benötigt.
- das ARM-Szenario mit ldrex und strex:
Auch hier ist die betreffende Page als non-cachable markiert. Der ldrex-Befehl holt aus dem Speicher das betreffende Byte und richtet im Memory-Controller der CPU G einen Hardware-Lock ein. Die CPU entscheidet dann anhand des gelesenen Wertes ob der (SW-verwaltete) Lock noch frei war und schreibt immer 0x01 per strex-Befehl zurück in den Speicher. Der strex-Befehl hebt auch wieder den Hardware-Lock im Memory-Controller der CPU G auf und meldet an die CPU (A oder H) den Erfolg zurück. Falls eine zweite CPU (H oder A) kurz nach dem Lesezugriff der ersten CPU auch dran kommt dann wird für den ldrex-Befehl dieser CPU kein Hardware-Lock erstellt und nach dem Schreibzugriff merkt diese das sie verloren hat (hier wäre es natürlich geschickter wenn bereits der ldrex-Befehl einen Fehler melden könnte) und wiederholt den gesamten Vorgang. Der Zeitbedarf ist ziemlich genau das doppelte der xchg-Variante, sind ja 2 komplette Zugriffe. Natürlich lasen sich zwischen den beiden Befehlen auch komplexere Dinge erledigen, mindestens alles was man mit cmpxchg auch machen kann. Der Mehrbedarf dürfte in Anbetracht heutiger CPU-Performance vernachlässigbar sein. Der Zeitbedarf für vorher frei und vorher belegt ist gleich weil die CPU leider erst nach dem abschließenden Schreibzugriff merkt ob sie erfolgreich war oder nicht (da ließe sich aber noch optimieren).
Falls die betreffende Cache-Line doch gecached ist gelten die selben Dinge wie bei xchg, nur das der zusätzliche Zeitaufwand prozentual gesehen geringer ist. Das Cache-Kohärenz-Protokoll muss vor/mit dem ldrex-Befehl erfolgen.
- cmpxchg-Szenario :
....... wer mag sich daran versuchen und zeigen wo cmpxchg mit lock-Präfix (und ohne Cache-Trashing) schneller ist? Ich lerne gerne noch dazu. :-D
Ich hab mal etwas gegrübelt und mir ist nichts eingefallen das cmpxchg wenigstens schneller als eine optimierte ARM-Variante machen würde, an die xchg-Variante dürfte cmpxchg erst recht nicht ran kommen, selbst dann nicht wenn man das Cache-Kohärenz-Protokoll in der ungünstigsten Variante annimmt.
Grüße
Erik
-
Das Cache-Thrashing-Argument kam ursprünglich nicht von mir. Ich hätte das besser ausdrücken sollen. Ich hab dieses Argument ohne groß drüber nachzudenken für schlüssig gehalten, weil weniger Schreibzugriffe weniger Write Backs erzeugen und damit weniger Thrashing. Das ist zumindest in deinem Modell, das ich für schlüssig halte, nicht der Fall.
-
Hallo,
Das Cache-Thrashing-Argument kam ursprünglich nicht von mir.
Stimmt, sorry.
Ich hab dieses Argument ohne groß drüber nachzudenken für schlüssig gehalten, weil weniger Schreibzugriffe weniger Write Backs erzeugen und damit weniger Thrashing. Das ist zumindest in deinem Modell, das ich für schlüssig halte, nicht der Fall.
Man könnte für den Zeitraum eines cmpxchg die Cache-Lines in den Caches der anderen CPUs "sperren" (dazu müsste es dann aber einen zusätzlichen Zustand im MESI geben) so das die CPU, welche den cmpxchg-Befehl ausführt, auf ihrer lokalen Kopie im Cache arbeiten kann. Dazu müssten vorher natürlich noch eventuelle Modifikationen von anderen CPUs (also aus dehren Caches) eingesammelt werden und davor müsste man bei mehreren gleichzeitigen Anfragen von verschiedenen CPUs, die alle einen cmpxchg (oder auch was anderes wie z.B. einen xchg) auf diese Speicherstelle machen wollen, noch einen Gewinner ermitteln (schon allein das ist nicht trivial, vor allem nicht bei mehr als 2 interessierten Teilnehmern). Nach dem Ende von cmpxchg müssten dann die anderen Cache-Lines wieder freigegeben werden (kein Schreibzugriff) oder invalidiert werden (Schreibzugriff erfolgt). Ob der ganze Aufwand in kürzerer Zeit als ein xchg durchgeführt werden kann wage ich stark zu bezweifeln, selbst die ARM-Variante zu unterbieten dürfte nahezu unmöglich sein. Nebst dessen das dieses aufwendige Cache-Kohärenz-Protokoll eine Menge Traffic, über das gesamte CPU-Netzwerk, erzeugt der die anderen CPUs am arbeiten hindert.
Einen wirklich konsistenten Überblick über die Situation einer bestimmten Cache-Line zu bekommen und zu sichern, so das dieser Überblick nicht von anderen CPUs oder anderen Bus-Mastern unterlaufen wird, stelle ich mir ziemlich schwierig vor. Da müssen eine ganze Menge an Komponenten mitspielen und es bedarf einer ordentlichen Portion extra Verwaltungs-Logik. Dann auch noch sicher zu stellen das es wirklich 100%-tig keine Lücken in diesem System gibt dürfte nahezu unmöglich sein. Ich denke schon das Intel, oder auch AMD, das tatsächlich hin bekommen könnten, aber ohne eine schlüssige Erklärung kann ich dem nicht vertrauen. Nebst dessen das ich einfache Lösungen, die oft (so wie in diesem Fall auch) schon wegen ihrer Simplizität sicherer sind, bevorzuge.
Ich selber möchte ja auch eine CPU, mitsamt Plattform, entwickeln und da ich ebenfalls SMP und CPU-lokalen Speicher vorgesehen hab (also ccNUMA), werde ich vor dem selben Problem stehen. Für den ersten Anlauf werde ich den Daten-Cache wohl im Memory-Controller lassen. Dort gibt es keinen Weg dran vorbei und es werden immerhin die DRAM-Latenzen kompensiert. Wenn der Cache in die eigentliche CPU wandern soll (natürlich noch im selben FPGA) dann wird es schwierig. Als einfaches Konzept könnte es gehen wenn die Cache-Line der aktuellen CPU immer exklusiv gehört. Wenn eine CPU auf Daten zugreifen will muss sie sich die betreffende Cache-Line zur exklusiven Nutzung besorgen, entweder beim Heimat-Memory-Controller oder bei einer anderen CPU welche diese Cache-Line momentan noch hat. Dazu muss der Memory-Controller aber für jede mögliche Cache-Line aus seinem Speicher eine Liste führen welche Cache-Line er "verliehen" hat. Außerdem könnte es sein das 2 verschiedene CPUs immer wieder auf (unterschiedliche Bytes in) eine Cache-Line lesend zugreifen und dann ständig die gesamte Cache-Line hin und her geschickt wird ohne das dazu eine reale Notwendigkeit besteht (allerdings wäre das auch ziemlich doofer Code, dagegen hab ich extra 64 Register vorgesehen). Ein wirklich gutes Konzept zu entwickeln das möglichst wenig Traffic erzeugt und gleichzeitig allen möglichen (und unmöglichen) Situationen gerecht wird ist gar nicht einfach, ich denke das wird nach der eigentlichen CPU die größte Schwierigkeit in meinem Projekt.
Grüße
Erik
-
Wenn ich mich mal einmischen dürfte.
Geht es nur um spinlocks im User-Code oder auch im Kernel-Code?
Also erstmal wäre es nicht wirklich toll, wenn ihr eine Spinlock nur über xchg programiert (der lock Präfix ist wie gesagt sehr teuer, vorallem wenn man das ständig macht). Nicht umsonst gibt es die Test-And-Set Variante.
Ich bin leider noch nicht so weit das ich mir schon ne Rübe darüber machen müsste wie ich im User-Code nen Lock ohne in den Kernel zu gehen hinbekomme, aber ich würde nie eine Spinlock im User-Code nutzen. Ich meine stellt euch mal die Situation vor, der Thread bekommt die Lock und gleich danach wird der Scheduler aufgerufen und der Thread ist nicht mehr an der Reihe. Das würde heißen das er den Lock hat und alle anderen die Versuchen ihn zu bekommen müssen warten (und zwar mit einem busy-wait, ganz schlecht) und das kann unter Umständen schon mal ne Weile dauern. Das Problem ist hier halt, das man im User-Code die Interrupts nicht ausschalten kann. Problematisch ist es natürlich wenn man den Lock nur für ein paar Instruktion (Assembler-Anweisungen) braucht. Da wäre eine Semaphore/Mutex natürlich totaler Overhead!
Ich nutze folgenden Code im Kernel für meine Spinlocks:
struct spinlock_t {
uint32t volatile lock;
uint32t flags;
};
static inline void spinAcquire(struct spinlock_t *spinlock) {
asm volatile("pushfl\n\t"
"1:\tcli\n\t"
"testl $1,(%%eax)\n\t"
"je 2f\n\t"
"popfl\n\t"
"pushfl\n\t"
"pause\n\t"
"jmp 1b\n\t"
".align 4,0x90\n\t"
"2:\tlock bts $0,(%%eax)\n\t"
"jc 1b\n\t"
"popl %[output]\n\t"
"cli"
:[output] "=q"(spinlock->flags)
:"a"(spinlock)
:"memory", "flags");
}
static inline void spinRelease(struct spinlock_t *spinlock) {
//look if ints were enabled or disabled
asm volatile(""
:
:
:"memory");
spinlock->lock= 0;
if(likely(spinlock->flags & 0x200))
asm volatile("sti");
}
Ist halt die Test-And-Set Variante mit dem Deaktivieren der Interrupts.
-
Hallo,
Geht es nur um spinlocks im User-Code oder auch im Kernel-Code?
Ich denke um beides.
Also erstmal wäre es nicht wirklich toll, wenn ihr eine Spinlock nur über xchg programiert (der lock Präfix ist wie gesagt sehr teuer, vorallem wenn man das ständig macht). Nicht umsonst gibt es die Test-And-Set Variante.
Der BTS-Befehl ist ohne lock-Präfix aber nicht Multi-CPU-sicher! Warum das so ist habe ich in diesem Thread nun erschöpfend genug erklärt. In Deinem Quell-Code benutzt Du ja schließlich auch das lock-Präfix. Wenn man die Sicherheit will muss man auch den Preis für das lock-Präfix bezahlen!
Ich bin leider noch nicht so weit das ich mir schon ne Rübe darüber machen müsste wie ich im User-Code nen Lock ohne in den Kernel zu gehen hinbekomme, aber ich würde nie eine Spinlock im User-Code nutzen.
Warum nicht? Wenn man den Spinlock nur braucht um 3 Speicherzugriffe durchzuführen (z.B. kleine Struktur atomar modifizieren) dann lohnen zwei teure SYSCALLs wahrlich nicht.
Ich meine stellt euch mal die Situation vor, der Thread bekommt die Lock und gleich danach wird der Scheduler aufgerufen und der Thread ist nicht mehr an der Reihe. Das würde heißen das er den Lock hat und alle anderen die Versuchen ihn zu bekommen müssen warten (und zwar mit einem busy-wait, ganz schlecht) und das kann unter Umständen schon mal ne Weile dauern.
Das ist natürlich ein Problem, für das es aber ein paar hübsche Lösungen gibt. Zum einen kann der wartende Thread nach jedem fehlgeschlagenen Versuch die restliche Zeitscheibe freigeben damit der Thread der den Lock gerade hat möglichst schnell wieder an die CPU kommt und fertig wird. Bei Locks die immer nur kurz belegt werden ist das die effizienteste Lösung. Bei Locks die länger belegt werden ist es meist günstiger dafür den OS-Kernel zu bemühen der den wartenden Thread schlafen legt und sofort aufweckt sobald der Lock freigegeben wird (noch im Freigabe-SYSCALL). Dort könnte man dann auch so tolle Sachen wie Prioritätsvererbung einbauen, damit der Low-Prio-Thread der gerade den Lock besitzt auf die selbe Prio angehoben wird wie der High-Prio-Thread welcher den Lock haben will damit dieser möglichst bald dran kommt.
Im Kernel-Mode gibt es andere Kriterien für die Wahl der richtigen Lock-Methode. Auf einer Single-CPU-Maschine muss man z.B. zwingenst die IRQs sperren für den gesamten Zeitraum wo man den Lock hat sonst kommt der nächste Dead-Lock schneller als man denkt. Auf Multi-CPU-Systemen könnte man das theoretisch auch anders machen, riskiert damit aber erhebliche Wartezeiten (im Kernel ist ja nur aktives Warten möglich).
Man muss sich eben genau den Verwendungszweck anschauen und dann das geeignetste Werkzeug benutzen.
Ich nutze folgenden Code im Kernel für meine Spinlocks:
....
Was mir auffällt ist das Du in der spinRelease-Funktion zwar eine Memory-Bariere (das erste Assembler-Macro) hast aber den eigentlichen Freigabe-Speicherzugriff erst danach ausführst, das bedeutet das dieser Freigabe-Speicherzugriff auch erst deutlich später kommen kann (auch nach dem zweiten Assembler-Macro). Ich finde dieser Freigabe-Speicherzugriff sollte in das erste Assembler-Macro rein. Durch die Befehle cli und sti ist Dein code auch nicht für User-Space-Programme geeignet, ein ordentliches OS wird die Nutzung dieser Befehle im User-Mode zuverlässig verhindern.
Grüße
Erik
-
Der BTS-Befehl ist ohne lock-Präfix aber nicht Multi-CPU-sicher! Warum das so ist habe ich in diesem Thread nun erschöpfend genug erklärt. In Deinem Quell-Code benutzt Du ja schließlich auch das lock-Präfix. Wenn man die Sicherheit will muss man auch den Preis für das lock-Präfix bezahlen!
Hier hast du mich ein wenig missverstanden. Was ich an dem Code den ich hier gesehen habe, zu beanstanden habe ist dass er ständig eine Schleife macht und ständig den Lock durchführt!
Deswegen sollte man ja auch die Test-And-Set Variante verwenden! Das man erst den Memorybus Locked wenn der Lock wahrscheinlich frei ist!
(im Kernel ist ja nur aktives Warten möglich)
Wie kommst du darauf? Also mein Kernel beherrscht Semaphores (ihm ist es auch egal ob es ein User oder ein Kernel-Thread, da eh alles im Kernel läuft). Also das im Kernel nur aktives warten möglich ist, ist erstmal Quatsch, das ist ne reine Implementations Sache!
-
Hallo,
Hier hast du mich ein wenig missverstanden. Was ich an dem Code den ich hier gesehen habe, zu beanstanden habe ist dass er ständig eine Schleife macht und ständig den Lock durchführt!
Der Code versucht ständig den Lock zu bekommen und jeder Versuch wird mit einem atomaren Speicher-Befehl durchgeführt (das muss ja auch so sein).
Deswegen sollte man ja auch die Test-And-Set Variante verwenden! Das man erst den Memorybus Locked wenn der Lock wahrscheinlich frei ist!
Das macht Dein Code aber auch nicht besser.
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. Die Wahrscheinlichkeit ist dann jedenfalls hoch, es sein den der Code ist im User-Mode und genau dazwischen schlägt der Scheduller (Timer-IRQ) zu.
Ich habe den Eindruck wir reden etwas an einander vorbei, poste doch mal Bitte konkreten Code um genau zu zeigen was Du meinst.
Also das im Kernel nur aktives warten möglich ist, ist erstmal Quatsch, das ist ne reine Implementations Sache!
Stimmt, man kann eine Thread auch im Kernel-Mode unterbrechen.
Grüße
Erik
-
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? :?
-
Genau das macht doch sein Code, oder sehe ich das falsch?
Richtig ;)
@erik
Ich meine Code wie diesen:
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.).
-
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
-
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:
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.
-
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.
-
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!
-
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
-
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.
-
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
-
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:
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 ;)
-
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:[.....][.....]
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
-
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.
-
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
-
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.
-
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? :wink:
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
-
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 ;) ).
-
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
-
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+).
-
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
-
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.
-
Hallo,
Mit solchen Infos ist Intel immer sehr zurückhaltend :(
Sag ich doch, ein fürchterlicher Geheimniskrämer der damit eigentlich nur seine zahlenden Kunden verärgert.
Wie das dann mit dem Cachekohärenzprotokolloverhead ist weiß ich nicht.
Aber genau darum geht es doch. Wenn eine bestimmte CPU eine bestimmte Cache-Line zur exklusiven Verwendung haben will dann muss diese CPU sicherstellen das diese Cache-Line in keiner anderen CPU vorhanden ist. Das geht nur über Broadcast oder über ein vollständiges Verzeichnis, da letzteres zu viel Speicher erfordert bleibt eben nur Broadcast übrig und das wird gerade bei vielen CPUs einiges an Last darstellen und reichlich Zeit benötigen.
Genauso haben alle anderen Threads mehr Bandbreite wenn du mit deinem Lock den Memorybus nicht zusätzlich belastest.
Es gibt keinen BUS mehr in einem modernen Multi-CPU-System! Oder meinst Du die Verbindung zwischen der CPU und den (eventuell mehreren) lokalen Speichermodulen? Das ist das einzigste was man noch als BUS bezeichnen könnte.
Außerdem gehe ich mal davon aus, das Intel dieses Vefahren nicht im Optimierungsguide angeben würde, wenn es effektiv nichts bringt.
Der Optimirungsguide ist sicher über mehrere CPU-Generationen gewachsen, ich glaube nicht das dort noch alles Up-To-Date ist.
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.
Wenn Deine Queue eine einfach verkettete Liste ist in der es in jedem Element einen "Next"-Pointer gibt dann kannst Du ein neues Element bauen (dort ist der Next-Pointer noch NULL) und dieses mit einem cmpxchg auf den Next-Pointer des letzten Listenelement anhängen (dort ist der Next-Pointer auch noch NULL). Das heißt der cmpxchg prüft ob der Next-Pointer im letzten Element noch NULL war und schreibt dann den Pointer für Dein neues Element an diese Stelle und wenn das fehlschlägt (weil jemand anderes schneller war) dann probierst Du das bei dem neuen letzten Element eben erneut. Du versucht also nicht ständig den selben Next-Pointer zu bearbeiten sondern gehst nach jedem Fehlschlag weiter. Doof wäre nur wenn Deine Message-Queue in dieser Zeit leer werden sollte.
Grüße
Erik
-
Es gibt keinen BUS mehr in einem modernen Multi-CPU-System! Oder meinst Du die Verbindung zwischen der CPU und den (eventuell mehreren) lokalen Speichermodulen? Das ist das einzigste was man noch als BUS bezeichnen könnte.
Ja, daran dachte ich. Das Problem mit dem Cachekohärenzprotokoll tritt ja "nur" auf, wenn der Lock freigegeben wurde ("nur" deshalb, weil dann ja die Cacheline mehrmals ungültig gemacht wird). Es kommt halt drauf an, wie lange man den Lock hat, bei 3-10 Assemblerinstruktionen kann es dann schon sein, das deine Variante vielleicht schneller ist, aber ich würde zumindest ne "pause" mit einsetzen. Denn gerade die neuen Core i-sowieso CPUs sollten wieder davon profitieren!
Der Optimirungsguide ist sicher über mehrere CPU-Generationen gewachsen, ich glaube nicht das dort noch alles Up-To-Date ist.
Ach der wird eigentlich laufend aktualisiert und genau da ist ja das Problem. Am Anfang schreiben sie, du sollst deine Loops so weit es geht unrollen und später schreiben sie, dass auf der Core Architektur das Loop unrolling nicht übertrieben werden sollte, weil die CPUs damit nicht mehr zurecht kommen ;) Aber zum Thema Spinlocks sagen sie auch, das es im Cache liegen soll, aber eine Lock alleine in einer Cacheline! Naja ich denke wir einigen uns darauf, das jeder das nimmt was er für besser hält ;)
Wenn Deine Queue eine einfach verkettete Liste ist in der es in jedem Element einen "Next"-Pointer gibt dann kannst Du ein neues Element bauen (dort ist der Next-Pointer noch NULL) und dieses mit einem cmpxchg auf den Next-Pointer des letzten Listenelement anhängen (dort ist der Next-Pointer auch noch NULL). Das heißt der cmpxchg prüft ob der Next-Pointer im letzten Element noch NULL war und schreibt dann den Pointer für Dein neues Element an diese Stelle und wenn das fehlschlägt (weil jemand anderes schneller war) dann probierst Du das bei dem neuen letzten Element eben erneut. Du versucht also nicht ständig den selben Next-Pointer zu bearbeiten sondern gehst nach jedem Fehlschlag weiter. Doof wäre nur wenn Deine Message-Queue in dieser Zeit leer werden sollte.
Genauso sieht meine Liste aus, aber wie ich es mir dachte, wird es wohl Probleme beim Löschen geben.
Ich habe ne doppelt verkettete Liste und speichere nur den Head ab. Der Pointer auf das letzte Element ist dann der Vorgänger vom Head, d.h. beim Löschen müsste ich 2 Pointer ändern und beim Einfügen müsste ich auch immer gucken ob der Head noch da ist. Also bleibe ich lieber bei ner Spinlock (ist ja auch nicht wirklich viel was hier passiert).
Ich bin mir nicht sicher ob es hierher passt, aber egal.
Was hälst du denn von Read-Write-Locks? Ich muss heute direkt mal nachgucken, ob es sowas auch als Semaphore gibt, habe ich nämlich noch nichts von gehört.
-
Hallo,
Das Problem mit dem Cachekohärenzprotokoll tritt ja "nur" auf, wenn der Lock freigegeben wurde ("nur" deshalb, weil dann ja die Cacheline mehrmals ungültig gemacht wird).
Anderes Szenario: 5 CPUs (von einigen mehr) wollen gleichzeitig einen Lock haben der momentan frei ist (was auch ein vorangegangener nicht-gelockter Lesebefehl bestätigt) und jede hat die betreffende Cache-Line im Zustand "Shared" im lokalen Cache. Um auf der Lock-Variable nun den gelockten cmpxchg (oder auch was anderes atomisches) auszuführen muss jede der CPUs die betreffende Cache-Line für sich exklusiv reservieren also wird ein "Read-For-Exclusive"-Broadcast an alle CPUs geschickt und auf alle Antworten gewartet. Jede der 5 CPUs erhält während sie auf Antworten wartet die Anfragen der jeweils 4 anderen CPUs. Nun muss nach irgendeinem Prioritätsschema ermittelt werden welche der 5 CPUs die Cache-Line für sich beanspruchen darf um sie in den Zustand "Exclusive" zu überführen, die anderen 4 CPUs müssen die Cache-Line invalidieren. Nachdem die erste CPU gewonnen hat und ihren gelockten Befehl ausführen konnte (die kümmert sich dann erst mal nicht weiter um die Cache-Line die dann "Modified" ist) geht das Spiel mit den restlichen 4 CPUs von vorne los, die wollen immer noch den einen gelockten Befehl ausführen. Das geht so lange bis auch die letzte der 5 CPUs ihren einen gelockten Befehl endlich ausführen konnte. Kannst Du Dir den Traffic auf dem CPU-Netzwerk annähernd ausmalen?
Dagegen sind 5 Anfragen die nur direkt an den betreffenden Heimat-Speicher-Controller geschickt werden, 5 Jobs im RAM-Controller (nur der erste Job muss die langen DRAM-Latenzen mitmachen, für die 4 folgenden Jobs ist die betreffende DRAM-Zeile noch aktiv) und 5 Antworten (nur die erste signalisiert "Lock erfolgreich bekommen") die wieder nur direkt zu den richtigen CPUs geschickt werden eine Kleinigkeit. Und deutlich schneller dürfte die Non-Cachable-Variante in diesem Szenario auch sein.
Es kommt halt drauf an, wie lange man den Lock hat
Ganz genau.
bei 3-10 Assemblerinstruktionen kann es dann schon sein, das deine Variante vielleicht schneller ist, aber ich würde zumindest ne "pause" mit einsetzen.
Meiner Meinung nach gibt es 4 Varianten:- kleine Schleife ohne irgendwas zur Unterbrechung (also z.B. der Code den ich ganz am Anfang vom Thread gepostet hatte): das lohnt sich IMHO bis etwa 5 Speicherzugriffe (von den eigentlichen Rechenbefehlen erwarte ich bei heutigen CPU-Leistungen keine nennenswerte extra Zeit)
- kleine Schleife mit einem pause-Befehl: das sollte sich für etwas längere Locks lohnen, wenn der zusätzliche pause-Befehl etwa doppelt so lange dauert wie der gelockte Befehl dann darf auch der Lock-Besitz etwa 3 mal so lange dauern als bei ohne pause-Befehl
- kleine Schleife mit Freigabe der Zeitscheibe, also anstelle des pause-Befehls ein sleep(0) oder ein anderer spezieller SYSCALL damit der aktuelle Thread geschedullt wird: das sollte sich für einen gelockten Vorgang lohnen der maximal etwa 5 bis 20 Zeitscheiben dauert
- Benutzung einer speziellen OS-Kernel-Funktion welche den wartenden Thread suspendiert und in eine Queue packt: damit gibt es dann keine Grenze mehr nach oben, die SYSCALLs sind zwar recht teuer aber dafür kostet das Warten gar nichts
Die nummerischen Werte entstammen meinem persönlichen Bauchgefühl und können in der Realität sicher je nach Plattform und Ausstattung etwas variieren.
Die ersten beiden Varianten sind auf einem Single-CPU-System eher nicht geeignet.
Man muss also immer das richtige Werkzeug wählen.
Der Optimirungsguide ist sicher über mehrere CPU-Generationen gewachsen, ich glaube nicht das dort noch alles Up-To-Date ist.
Ach der wird eigentlich laufend aktualisiert und genau da ist ja das Problem.
Eben, der sollte für jede CPU-Generation komplett neu geschrieben werden. Sicher kann man da viel 1:1 kopieren aber jedes kopierte Wort sollte von mehreren ausreichend qualifizierten Leuten geprüft werden damit sich nicht Schnee von Gestern durch mogelt.
Am Anfang schreiben sie, du sollst deine Loops so weit es geht unrollen und später schreiben sie, dass auf der Core Architektur das Loop unrolling nicht übertrieben werden sollte, weil die CPUs damit nicht mehr zurecht kommen ;)
Ich persönlich würde Loop-Unrolling sowieso nicht übertreiben weil das ne Menge Platz im Code-Cache kostet. Ich weiß aber auch das die Intel-Compiler diese Neigung teilweise sehr exzessiv ausleben und damit auch oft sehr gute Performance erreichen.
Aber zum Thema Spinlocks sagen sie auch, das es im Cache liegen soll, aber eine Lock alleine in einer Cacheline!
Was dann wieder pure Speicherverschwendung ist, außerdem weißt Du doch nicht zur Link-Zeit die Cache-Line-Größe des Zielrechners.
Naja ich denke wir einigen uns darauf, das jeder das nimmt was er für besser hält ;)
Full ACK! :wink:
Genauso sieht meine Liste aus, aber wie ich es mir dachte, wird es wohl Probleme beim Löschen geben.
Wenn Du Probleme beim leeren bekommst dann lass doch immer mindestens ein oder zwei Elemente drin und markiere sie nur als leer. Oder der Queue-Konsument hat einen eigenen Pointer in die Liste.
Ich habe ne doppelt verkettete Liste ...
Doppelt verkettete Liste geht IMHO nicht atomar.
Was hälst du denn von Read-Write-Locks? Ich muss heute direkt mal nachgucken, ob es sowas auch als Semaphore gibt, habe ich nämlich noch nichts von gehört.
Ich hab das mal auf Basis eines einfachen Locks (der die internen Verwaltungsstrukturen geschützt hat) implementiert. Es durften immer beliebig viele Leser gleichzeitig rein aber nur ein Schreiber und immer nur eine Sorte gleichzeitig. Die Schreiber hatten eine höhere Priorität. Das war wimre nicht sonderlich kompliziert.
Ich weiß gar nicht mehr wofür das damals benötigt wurde aber meine Kollegen haben sich nie beschwert, muss wohl ausreichend funktioniert haben. :wink:
Grüße
Erik
-
Die ersten beiden Varianten sind auf einem Single-CPU-System eher nicht geeignet.
Warum? Auf nem Single-CPU-System bekommst du ne Spinlock immer (ich gehe jetzt mal frech vom Kernel aus)! Denn wenn du schon ne Spinlock nutzt dann bitte auch die IRQs ausmachen. Wenn du das ganze für den Userspace betrachtest, dann würde ich es so lösen, das du ne bestimmte Anzahl an Versuchen unternimmst und dann an den Scheduler abgibts und beim nächsten Mal geht es wieder von vorne los.
Was dann wieder pure Speicherverschwendung ist, außerdem weißt Du doch nicht zur Link-Zeit die Cache-Line-Größe des Zielrechners.
Also was ich so an Code vom Intel-Compiler gesehen haben, macht der sich um Speicherverschwendung nicht wirklich ne Rübe ;)
Intel scheint in seinem Optimierungsguide sowieso davon auszugehen, das du alles immer nur auf einer bestimmten CPU laufen lässt und andere sind egal. (gut für Compilerprogrammierer sind die Infos schon wertvoll)
Du hattest mal was davon geschrieben, das AMD bei ihren aktuellen CPUs einen Teil des Level3 Caches dafür benutzt um die ganze Cachekohärenzprotokollsache zu minimieren. Dann frage ich mich schon was Intel mit ihren neuen Server-CPUs und bis zu 24MB Level3 Cache wollen, weil da müsste ja dann die Hölle los sein ;) Zumal diese CPUs gerade für viele Sockel-Mainboard ausgelegt sind.
-
Hallo,
Die ersten beiden Varianten sind auf einem Single-CPU-System eher nicht geeignet.
Warum? Auf nem Single-CPU-System bekommst du ne Spinlock immer (ich gehe jetzt mal frech vom Kernel aus)!
Sorry, ich bin vom User-Mode ausgegangen. Auf nem Single-CPU-System braucht man im Kernel keine Locks da reicht IRQs ausschalten auch. Im User-Mode ist es auf einem Single-CPU-System IMHO Zeitverschwendung mehrmals hintereinander zu versuchen einen Lock zu bekommen, ein Versuch pro Zeitscheibe sollte reichen.
Meine 4 Lock-Varianten sind aber offensichtlich noch nicht der Weisheit letzter Schluss, da bleibt noch Verbesserdungspotential.
Du hattest mal was davon geschrieben, das AMD bei ihren aktuellen CPUs einen Teil des Level3 Caches dafür benutzt um die ganze Cachekohärenzprotokollsache zu minimieren.
Ich galube aber nicht das sie damit das Problem komplett los sind, schon weil keine CPU den gesamten Traffic sieht. Es wird wohl nur etwas reduziert werden.
Dann frage ich mich schon was Intel mit ihren neuen Server-CPUs und bis zu 24MB Level3 Cache wollen, weil da müsste ja dann die Hölle los sein ;) Zumal diese CPUs gerade für viele Sockel-Mainboard ausgelegt sind.
Die Frage ist eher was "viele" Sockel sind. Ich persönlich habe den Eindruck das AMD da in etwas größerem Maßstäben denkt. Sieh Dir mal http://www.intel.com/technology/quickpath/demo/demo.htm an. Intel lebt IMHO davon das QPI nominal etwas schneller ist und damit etwas mehr Broadcast vertragen kann, außerdem machen größere Caches das Anfordern von externen Daten seltener. Ich denke bei Intel wird ein etwas höherer Anteil an Broadcast-Traffic unterwegs sein und dafür aber seltener echte Daten transferiert werden.
An der Stelle versucht AMD wohl anzusetzen, durch die lokalen Infos über fremde Cache-Lines muss eine simple Anfrage oft nicht an alle anderen CPUs gesendet werden sondern nur an die interessanten Kandidaten. Dadurch wird der Vorgang zwar nicht unbedingt beschleunigt erzeugt aber weniger Traffic so das anderes parallel schneller wird.
Verstehst Du denn jetzt warum ich bei vielen Sockeln eher zur Non-Cachable-Variante tendiere?
Grüße
Erik
-
Im User-Mode ist es auf einem Single-CPU-System IMHO Zeitverschwendung mehrmals hintereinander zu versuchen einen Lock zu bekommen, ein Versuch pro Zeitscheibe sollte reichen.
Du solltest vielleicht mal definieren was du unter einer Zeitscheibe verstehst. Also ich denke mal du meinst die Zeit die ein Thread vom Scheduler bekommt. So wie du es schilderst verstehe ich darunter das du nur einmal versuchen willst den Lock zu bekommen und dann abgibts, aber dann nimm bitte eine Semaphore! Denn wenn du beim nächsten mal wieder versuchst den Lock zu bekommen und ihn wieder nicht bekommst, kostet das nur unnötig Performance (TLB und so´n Zeug).
Ich kann so langsam nachvollziehen wieso du uncacheable besser findest. Ich habe gerade ne News auf Golem gelesen und fand die Idee ganz gut (ein oder mehrere Kerne nur für die Speicherverwaltung). Wenn man die Idee jetzt mal weiter denkt, dann macht es sich ganz gut, immer einen Kern für eine bestimme Aufgabe zu nehmen (nur was das OS so zur Verfügung stellt) und alle anderen Kerne können von den Programmen genutzt werden. Das sollte das Cacheproblem doch wesentlich verringern.
edit::
Auf nem Single-CPU-System braucht man im Kernel keine Locks da reicht IRQs ausschalten auch. Im User-Mode ist es auf einem Single-CPU-System IMHO Zeitverschwendung mehrmals hintereinander zu versuchen einen Lock zu bekommen, ...
Mein Kernel läuft dummerweise auf Single und Multi-CPU Systemen. Auch kannst du als Programmierer ja nicht wissen ob dein Spinlockcode jetzt auf nem Single-CPU System läuft oder nicht.
-
Als Programmierer nicht, aber wenn du das Locking zweimal implementierst, einmal als simples CLI/STI für Uniprozessor und einmal komplizierter für SMP, kannst du dynamisch umschalten. Ist halt nur noch ein Abstraktionsgrad mehr, ob sich das lohnt, kann ich nicht einschätzen.
Wenn der Kernel läuft, sollte er wissen, auf wievielen CPUs er läuft.
-
Als Programmierer nicht, aber wenn du das Locking zweimal implementierst, einmal als simples CLI/STI für Uniprozessor und einmal komplizierter für SMP, kannst du dynamisch umschalten. Ist halt nur noch ein Abstraktionsgrad mehr, ob sich das lohnt, kann ich nicht einschätzen.
Das könnte ich machen, wenn ich den Code nicht inlinen würde ;)
Ich habe es auch mal gebenchmarkt (auf nem K5-100) und was ich durch nur die Ints ausmachen sparen würde, würde durch den Funktionsaufruf wieder drauf gehen (Prob ist nur der K5 hat natürlich ne verdammt gute Integerleistung).
Wenn der Kernel läuft, sollte er wissen, auf wievielen CPUs er läuft.
Weiß meiner auch ;)
-
Hallo,
Du solltest vielleicht mal definieren was du unter einer Zeitscheibe verstehst. Also ich denke mal du meinst die Zeit die ein Thread vom Scheduler bekommt.
Ja.
So wie du es schilderst verstehe ich darunter das du nur einmal versuchen willst den Lock zu bekommen und dann abgibts, aber dann nimm bitte eine Semaphore!
Genau, auf einem Single-CPU-System wird sich der Status des Lock/Semaphore/sonstwas nicht ändern wenn der wartende Thread die eine CPU nicht wieder abgibt, das mehrfache probieren kostet nur Zeit und Energie (in Zeiten von Green-IT sollte man auch daran denken ;-) ). Was hat das nun wieder mit Semaphore zu tun?
Denn wenn du beim nächsten mal wieder versuchst den Lock zu bekommen und ihn wieder nicht bekommst, kostet das nur unnötig Performance (TLB und so´n Zeug).
Wenn der momentane Lock-Besitzer diesen nur kurz benötigt aber dummerweise gerade in diesem kurzen Code-Abschnitt vom Scheduller unterbrochen wurde dann ist das eben blöd und kostet etwas Performance. Aber deswegen noch mehr Performance für nen aufwändigen OS-Kernel-Service zu beanspruchen (der meist gar nicht nötig wäre) ist IMHO auch nicht zielführend. Einen passenden Service vom OS-Kernel zu nutzen lohnt IMHO erst wenn der Lock/Semaphore/sonstwas für längere Zeit beansprucht wird, ein wartender Thread also einige male vom Scheduller aufgerufen würde.
Ich kann so langsam nachvollziehen wieso du uncacheable besser findest. Ich habe gerade ne News auf Golem gelesen und fand die Idee ganz gut (ein oder mehrere Kerne nur für die Speicherverwaltung). Wenn man die Idee jetzt mal weiter denkt, dann macht es sich ganz gut, immer einen Kern für eine bestimme Aufgabe zu nehmen (nur was das OS so zur Verfügung stellt) und alle anderen Kerne können von den Programmen genutzt werden. Das sollte das Cacheproblem doch wesentlich verringern.
Diese Idee ist nicht neue, in dem von Dir verlinkten Dokument kann man von den 20 386ern auch nur maximal 18 nutzen, mindestens 2 behält das System für andere Dinge für sich. Prinzipiell ist das eine interessante Idee aber wenn das OS gerade nichts zu tun hat aber ein rechenintensives möglich viel CPU-Leistung will dann sollte es auch alle CPUs bekommen.
Mein Kernel läuft dummerweise auf Single und Multi-CPU Systemen. Auch kannst du als Programmierer ja nicht wissen ob dein Spinlockcode jetzt auf nem Single-CPU System läuft oder nicht.
Dann kompiliere den Kernel 2 mal (einmal für Single-CPU und ein mal für SMP) und lass den Boot-Loader den passenden nehmen. Die älteren NT-basierenden Windowsen haben das so gemacht (wie das in aktuellen Windowsen aussieht weiß ich nicht).
Als Programmierer nicht, aber wenn du das Locking zweimal implementierst, einmal als simples CLI/STI für Uniprozessor und einmal komplizierter für SMP, kannst du dynamisch umschalten.
2 mal implementieren ist gut aber ich würde das zur Compilezeit entscheiden lassen und eben 2 mal compilieren, das kosten zur Laufzeit wenigstens keine Performance. Alternativ könnte man auch sagen "Single-CPU stirbt eh aus, meinen Kernel gibt es nur als SMP-Version", dafür verzichtet man auf Single-CPU-System auf ein klein wenig Performance.
Wenn der Kernel läuft, sollte er wissen, auf wievielen CPUs er läuft.
Das Install-Programm sollte das auch wissen und den passenden Kernel beim Boot-Loader eintragen.
Ich habe es auch mal gebenchmarkt (auf nem K5-100) und was ich durch nur die Ints ausmachen sparen würde, würde durch den Funktionsaufruf wieder drauf gehen (Prob ist nur der K5 hat natürlich ne verdammt gute Integerleistung).
Echt, kann der K5 nicht so schnell Funktionen aufrufen? Gerade Code der von vielen Stellen benötigt wird profitiert oft nicht vom inlinen sondern davon nur ein mal da zu sein und auch nur ein mal im Cache zu liegen, es sei den der zu inlinende Code ist kleiner als der Funktionsaufruf selber (also bei x86 kleiner als 5 Byte). Was hat damit eigentlich die Integerleistung zu tun?
Grüße
Erik
-
Dann kompiliere den Kernel 2 mal (einmal für Single-CPU und ein mal für SMP) und lass den Boot-Loader den passenden nehmen. Die älteren NT-basierenden Windowsen haben das so gemacht (wie das in aktuellen Windowsen aussieht weiß ich nicht).
Ist nicht wirklich ne Option für mich (ist halt Einstellungssache ;) ). Problem ist speziell bei meinem Kernel, das er erst zur Laufzeit gelinkt wird und das würde heißen das ich nicht nur meinen Kernel 2mal bräcuhte sondern auch die "Module" die mindestens für den Kernel nötig sind (bei mir z.b. CPU, FPU, IRQ, PMM, Scheduler, Syscall und Timer) Das wird dann schon ein wenig umständlich.
Echt, kann der K5 nicht so schnell Funktionen aufrufen?
Wenn sie erstmal im Cache liegen dann bestimmt, aber ich kann nicht immer davon ausgehen, das alles im Cache liegt.
Gerade Code der von vielen Stellen benötigt wird profitiert oft nicht vom inlinen sondern davon nur ein mal da zu sein und auch nur ein mal im Cache zu liegen, es sei den der zu inlinende Code ist kleiner als der Funktionsaufruf selber (also bei x86 kleiner als 5 Byte).
Rein von der Anzahl an Instruktionen ist der Code Single-CPU Code mit Funktionsaufruf und SMP-Code ohne, aber mit best Case (was auf Single-CPU Systemem ja immer zutrifft) gleich "lang". Was du sparst (was aber auf älteren System nicht wirklich schlimm zu sein scheint) ist der gelockte Speicherzugriff. Am teuersten ist das CLI auf den älteren CPUs. Ich habe meinen Code auch mal auf meinem Q9550 gebencht und der ist selbst auf Taktebene wesentlich schneller als der K5 (was ich vorallem auf das CLI zurückführe).
Was hat damit eigentlich die Integerleistung zu tun?
Naja, alles was nicht FPU ist, ist halt Integerleistung. Ich hätte vielleicht sagen sollen das er ein verdammt gutes Verhältnis von Instruktionen pro Takt hat. Taktbereinigt zieht er halt auch viele spätere Generationen ab ;) (bei der Integerleistung, nicht bei der FPU).
Wenn der momentane Lock-Besitzer diesen nur kurz benötigt aber dummerweise gerade in diesem kurzen Code-Abschnitt vom Scheduller unterbrochen wurde dann ist das eben blöd und kostet etwas Performance. Aber deswegen noch mehr Performance für nen aufwändigen OS-Kernel-Service zu beanspruchen (der meist gar nicht nötig wäre) ist IMHO auch nicht zielführend. Einen passenden Service vom OS-Kernel zu nutzen lohnt IMHO erst wenn der Lock/Semaphore/sonstwas für längere Zeit beansprucht wird, ein wartender Thread also einige male vom Scheduller aufgerufen würde.
Das kommt auf die Schedulingstrategie an und was bei Sleep(0) wirklich passiert. Bei meinem OS würde das mit dem Abgeben (ich habe da nen extra Syscall für, nutze also kein Sleep(0)) funktionieren, zumindestens noch. Wenn ich meinen Scheduler mal ändern sollte (was sehr wahrscheinlich ist), dann sieht es schon wieder ganz anders aus.
-
Hallo,
Ist nicht wirklich ne Option für mich
War ja nur ein Vorschlag. Ich denke das man heutzutage nicht allzu viel verkehrt macht wenn man "nur" einen SMP fähigen Kernel hat.
Naja, alles was nicht FPU ist, ist halt Integerleistung.
Das ist aber schon eine recht merkwürdige Herangehensweise. :-D
Es gibt viele Befehle die nichts mit Rechnen oder Integern zu tun haben, z.B. die vielen MOV-Varianten inklusive der Speicherzugriffe.
Das auf älteren CPUs die Befehle cli/sti so langsam sind liegt IMHO da dran das damit die Flags als ganzes bearbeitet werden und die CPU dabei immer höllisch aufpassen muss das der Code nichts tut was er nicht tun darf. Aus diesem Grund ist (war) z.B. auch der Befehl popf ziemlich langsam. In der Zwischenzeit haben sich AMD und Intel sehr bemüht diese Engstelle deutlich zu beschleunigen, da x86 nur ein zentrales Flag-Set hat, und dort dummerweise auch noch die System-Flags mit drin sind, ist das von hoher Wichtigkeit.
Das kommt auf die Schedulingstrategie an und was bei Sleep(0) wirklich passiert.
Also bei sleep(0) solte das selbe passieren wie wenn der Timer-IRQ kommt, bei einem x86-SMP eben der IRQ vom Local-APIC-Timer.
In meiner Plattform soll auch jede CPU einen eigenen kleinen Timer haben der eine extra Kontext-Switch-Exception auslößt ohne dafür den IRQ-Controller o.ä. zu bemühen und weil das so direkt mit dem CPU-Kern verkoppelt ist gibt es zusätzlich einen extra Befehl der das selbe macht auch wenn der Timer noch nicht abgelaufen ist.
Bei meinem OS würde das mit dem Abgeben (ich habe da nen extra Syscall für, nutze also kein Sleep(0)) funktionieren, zumindestens noch. Wenn ich meinen Scheduler mal ändern sollte (was sehr wahrscheinlich ist), dann sieht es schon wieder ganz anders aus.
Der Scheduller in einem OS-Kernel sollte immer vernünftig mit Threads umgehen können die ihre restliche Zeitscheibe nicht komplett verbrauchen wollen, dafür gibt es sicher viele verschiedene sinnvolle Anwendungsszenarien.
Grüße
Erik
-
Es gibt viele Befehle die nichts mit Rechnen oder Integern zu tun haben, z.B. die vielen MOV-Varianten inklusive der Speicherzugriffe.
Da kannst du aber davon ausgehen, das wenn du ne CPU von einem anderem Hersteller auf das selbe Board packst der Speicherzugriff (so fern er nicht vom Cache abgefangen wird) gleich lang dauern.
Zumal was macht man denn im Endeffekt, was wirklich Leistung kostet? Es läuft immer auf das Rechnen (ein Vergleich ist nichts anderes) mit Zahlen zurück. Du holst ne Zahl, bearbeitest (rechnest damit) sie und schreibst sie wieder irgendwo hin und diese Zahlen sind halt Integerzahlen (auch fixed Point Zahlen sind im Endeffekt Integerzahlen).
War ja nur ein Vorschlag. Ich denke das man heutzutage nicht allzu viel verkehrt macht wenn man "nur" einen SMP fähigen Kernel hat.
Naja, mein Kernel soll ab Pentium aufwärts laufen und zu sagen ich hätte nur nen SMP Kernel ist nicht ganz zutreffend. Denn viele Sachen werden anders gemacht oder findest du erst gar nicht im Kernel, wenn er auf nem SMP System läuft.
Ich wollte meinen Kernel so klein wie möglich halten (also der Code und die Daten die nachher im Speicher liegen), aber die Komplexität nicht bis ins unendliche treiben und da muss man halt irgendwo Abstriche machen (deswegen Spinlocks die eher für SMP Systeme sind, da ist der Worst-Case niedriger als wenn ich Funktionen nutzen würde).
Also bei sleep(0) solte das selbe passieren wie wenn der Timer-IRQ kommt, bei einem x86-SMP eben der IRQ vom Local-APIC-Timer.
Das ist halt interpretations Sache. Ich stelle mir das halt so vor, das Programm liest die aktuelle Zeit, rechnet ein wenig rum und liest dann wieder die aktuelle Zeit, bildet die Differenz und macht mit der Differenz nen "sleep(diff)". Wenn der Wert der sleep übergeben wurde "0" ist (aus welchem Grund auch immer) und der Thread theoretisch noch Zeit übrig hätte, lasse ich ihn sofort wieder laufen. Ich weiß jetzt allerdings nicht wie sleep mit einem Wert von "0" definiert ist, könnte mir aber vorstellen dass das nirgends richtig steht (jetzt mal auf POSIX bezogen, obwohl ich den Standard nicht sehr mag).
-
Hallo,
Zumal was macht man denn im Endeffekt, was wirklich Leistung kostet? Es läuft immer auf das Rechnen ....
Wenn du das so betrachtest dann hat vieles mit Rechnen zu tun, obwohl z.B. cli/sti eher nicht und die Adressberechnungen bei Speicherzugriffen passieren heutzutage auch nicht mehr in der (Integer-)ALU. Aber lassen wir das sonst streiten wir noch bis die Forums-Datenbank platzt.
Ich stelle mir das halt so vor, das Programm liest die aktuelle Zeit, rechnet ein wenig rum und liest dann wieder die aktuelle Zeit, bildet die Differenz und macht mit der Differenz nen "sleep(diff)".
Hä, für was soll sowas gut sein? Damit lastest Du die CPU zu exakt 50% aus (die Pausenzeiten sind ja immer genau so lang wie die Arbeitszeiten). Also ich kann mir beim besten Willen nicht vorstellen wozu das nützlich sein soll, da solltest Du erst erklären was damit bezweckt werden soll.
Wenn der Wert der sleep übergeben wurde "0" ist (aus welchem Grund auch immer) und der Thread theoretisch noch Zeit übrig hätte, lasse ich ihn sofort wieder laufen.
Wieso? Der Thread hat doch explizit um eine Pause gebeten. Die Zeitangabe wird als Minimum und nicht als Maximum interpretiert. Wenn alle anderen Threads im System gerade nichts zu tun haben (also blockierend warten o.ä.) dann kommt Dein Thread sowieso schnell wieder dran.
Ich weiß jetzt allerdings nicht wie sleep mit einem Wert von "0" definiert ist, könnte mir aber vorstellen dass das nirgends richtig steht (jetzt mal auf POSIX bezogen, obwohl ich den Standard nicht sehr mag).
Bis jetzt hab ich das immer so erlebt das sleep(0) einfach nur die restliche Zeitscheibe frei gibt. Für Windows hab ich das gefunden: http://blog.m-ri.de/index.php/2010/01/23/was-denn-nun-switchtothread-sleep0-sleep1-2/, die 2 Kommentare stellen einiges klarer (vor allem der erste). Ein Sleep(0) ist natürlich nur dann sinnvoll wenn man davon aus gehen kann das es andere Threads gibt welche die CPU gerne nutzen würden, was beim warten auf einen mittelkurzen Lock natürlich gegeben ist.
Wie das mit sleep(0) bei POSIX ist weiß ich aber auch nicht genau. Ich hab mal für ein kleines RT-OS programmiert (das offiziell POSIX-Konform ist) und dort hat sleep(0) auch nur die aktuelle Zeitscheibe freigegeben und den Thread hinten an die entsprechende Scheduller-Liste angehängt (stand so in der Doku).
Es steht Dir natürlich frei das in Deinem OS fundamental anders zu implementieren, aber was versprichst Du Dir davon?
Grüße
Erik
-
Hä, für was soll sowas gut sein? Damit lastest Du die CPU zu exakt 50% aus (die Pausenzeiten sind ja immer genau so lang wie die Arbeitszeiten). Also ich kann mir beim besten Willen nicht vorstellen wozu das nützlich sein soll, da solltest Du erst erklären was damit bezweckt werden soll.
Ups, Denkfehler ;) Ich meinte natürlich sowas, das er die Berechnung in einer bestimmten Zeit haben will und wenn noch Zeit über ist, dann macht er nen sleep(restlicheZeit) (wobei halt auch 0 raus kommen könnte).
Bis jetzt hab ich das immer so erlebt das sleep(0) einfach nur die restliche Zeitscheibe frei gibt. Für Windows hab ich das gefunden: http://blog.m-ri.de/index.php/2010/01/23/was-denn-nun-switchtothread-sleep0-sleep1-2/, die 2 Kommentare stellen einiges klarer (vor allem der erste). Ein Sleep(0) ist natürlich nur dann sinnvoll wenn man davon aus gehen kann das es andere Threads gibt welche die CPU gerne nutzen würden, was beim warten auf einen mittelkurzen Lock natürlich gegeben ist.
Wie das mit sleep(0) bei POSIX ist weiß ich aber auch nicht genau. Ich hab mal für ein kleines RT-OS programmiert (das offiziell POSIX-Konform ist) und dort hat sleep(0) auch nur die aktuelle Zeitscheibe freigegeben und den Thread hinten an die entsprechende Scheduller-Liste angehängt (stand so in der Doku).
Es steht Dir natürlich frei das in Deinem OS fundamental anders zu implementieren, aber was versprichst Du Dir davon?
Ich kann das ganz leicht implementieren, indem ich bei sleep(0) einfach meinen Syscall zum abgeben aufrufe.
Der Grund warum das so bei meinem Scheduler (im Moment) nicht funktioniert ist, das ich immer am Anfang einer Liste adde (ist einfacher und geht schneller). Desweiteren kommt hinzu das ich mich noch nicht richtig mit scheduling Strategien auseinander gesetzt habe, aber soweit ich weiß ist meine niht ganz "normal". Da ich ne Ready- und ne Runqueue habe (wenn die Zeitscheibe eines Threads abgelaufen ist kommt er in die Runqueue, ist die Readyqueue leer, wird sie mit der Runqueue vertauscht, so dass alle bis auf die Idle-Threads min. einmal dran kommen).
Mal wieder back to topic, ich werd demnächst (sobald ich dazu komme) mal nen kleinen Benchmark machen, wie sich das Schreiben/Lesen auf uncachble Speicher auswirkt. Ich kann da leider nur testen, wie der best case aussieht, obwohl wohl eher der worst case (viele/alle CPUs wollen den Lock) interessanter wäre.
-
Hallo,
Ups, Denkfehler ;) Ich meinte natürlich sowas, das er die Berechnung in einer bestimmten Zeit haben will und wenn noch Zeit über ist, dann macht er nen sleep(restlicheZeit) (wobei halt auch 0 raus kommen könnte).
Das würde ich lieber mit einem periodischem Event machen. Da kannst Du Dich auch auf die Periodendauer verlassen, wenn Du selber immer mitrechnest akkumulieren sich Fehler auf. Wenn Du damit rechnest das 0 raus kommt musst Du auch damit rechnen das was negatives bei raus kommt. Auch da wäre der periodische Event die bessere Wahl, da könntest Du einzelne Ausreißer kompensieren falls Du im Durchschnitt immer deutlich unterm Zeitlimit bleibst.
Ich kann das ganz leicht implementieren, indem ich bei sleep(0) einfach meinen Syscall zum abgeben aufrufe.
Am besten noch in der libc.
Der Grund warum das so bei meinem Scheduler (im Moment) nicht funktioniert ist, das ich immer am Anfang einer Liste adde (ist einfacher und geht schneller).
Das ist bei einem Scheduler aber wahrlich keine gute Variante.
Desweiteren kommt hinzu das ich mich noch nicht richtig mit scheduling Strategien auseinander gesetzt habe, aber soweit ich weiß ist meine niht ganz "normal".
Ich hab mal in einem Scheduler für jede Priorität eine eigene Liste (simples und fixes Array) angelegt und für jede Liste einen Pointer gehabt der jedes mal wenn aus der Liste ein Thread dran kam inkrementiert wurde. Das ließe sich auch mit einer dynamischen einfach im Kreis verketteten Liste machen.
so dass alle bis auf die Idle-Threads min. einmal dran kommen).
Ich hab zwar auch nicht viel Ahnung von diesem Thema aber das klingt nicht nach einer guten Idee. Round-Robin kann man auch einfacher haben.
Mal wieder back to topic, ich werd demnächst (sobald ich dazu komme) mal nen kleinen Benchmark machen, wie sich das Schreiben/Lesen auf uncachble Speicher auswirkt.
Für die Lock-Variablen ist IMHO richtiges non-cachable die beste Variante. Wenn Du richtig kopieren möchtest (als Benchmark) dann würde ich mal "Write-Combining" probieren, das dürfte zumindest den Schreib-Teil beschleunigen. Eigentlich schade das es in aktuellen CPUs fürs Lesen keine Entsprechung zum "Write-Combining" gibt.
Ich kann da leider nur testen, wie der best case aussieht, obwohl wohl eher der worst case (viele/alle CPUs wollen den Lock) interessanter wäre.
Wie sich Dein OS auf einem SMP-System mit sehr vielen CPUs verhält kannst Du leider auch nur auf einem solchen System testen.
Grüße
Erik
-
Das würde ich lieber mit einem periodischem Event machen. Da kannst Du Dich auch auf die Periodendauer verlassen, wenn Du selber immer mitrechnest akkumulieren sich Fehler auf. Wenn Du damit rechnest das 0 raus kommt musst Du auch damit rechnen das was negatives bei raus kommt. Auch da wäre der periodische Event die bessere Wahl, da könntest Du einzelne Ausreißer kompensieren falls Du im Durchschnitt immer deutlich unterm Zeitlimit bleibst.
Ich muss dir ganz ehrlich sagen, irgendwie versteh ich grad nur Bahnhof ;)
Also stell dir vor du schreibst nen Framelimiter. Da holst du dir die aktuelle Zeit, berechnest den Frame, holst dir die nun aktuelle Zeit, bildest die Differenz und wartest gegebenenfalls (was für ein Wort ;) ).
Am besten noch in der libc.
Ich würde eher sagen, da auch ;) Denn du weißt nie was so ein Programmierer alles für Späße treibt.
Das ist bei einem Scheduler aber wahrlich keine gute Variante.
Wieso? Ich denke mal du hast mich nicht richtig verstanden (da ich dir Infos vorenthalten habe).
Also mein Scheduler hat 32 Prioritätswarteschlangen (die eher wie ein Stack aufgebaut sind), eine Idlewarteschlange und (jedenfalls bald) eine Realtimewarteschlange. Jede Warteschlange ist wie gesagt eher wie ein Stack aufgebaut, da ich immer am Anfang der Liste/Queue adde.
Dann habe ich noch 2 Arrays, einmal ReadyQueueArray und einmal RunQueueArray (beide sind halt Arrays mit 32 Elementen, 1 Element für eine Priorität). Hat ein Thread seine Zeitscheibe verbraucht, dann kommt er in das RunQueueArray, ist das ReadyQueueArray leer, wird geschaut ob das RunQueueArray Elemente enthält, wenn ja werden die beiden Arrays vertauscht und wenn nicht laufen entweder die Threads aus der IdleQueue oder der IdleThread.
Die Idee ist, das es ein O(1) Scheduler ist (an den alten Linuxscheduler angelehnt) und das jeder Thread seiner Priorität entsprechend dran kommt. So vermeide ich nebenbei auch, das ein Thread theoretisch das ganze System lahmlegen kann (vorausgesetzt die Priorität ist hoch genug).
Du könntest jetzt sagen, dass das sowieso nicht passieren dürfte, da man die Priorität ja ändern sollte, mach ich auch, aber immer nur im Bereich -5/+5 der am Anfang festgelegten Priorität. So will ich vermeiden, das ein CPU intensiver Thread ganz bis nach unten durchgereicht wird.
(Vielleicht sollte man dazu mal nen extra Thread aufmachen, wo dann über Schedulingstrategien diskutiert wird.)
Für die Lock-Variablen ist IMHO richtiges non-cachable die beste Variante. Wenn Du richtig kopieren möchtest (als Benchmark) dann würde ich mal "Write-Combining" probieren, das dürfte zumindest den Schreib-Teil beschleunigen. Eigentlich schade das es in aktuellen CPUs fürs Lesen keine Entsprechung zum "Write-Combining" gibt.
Wo ist jetzt der Unterschied zw. non-cacheable und uncachceable (ich wollte das einfach über die Flags in der Pagetable machen)?
Wenn ich dich richtig verstehe, meinst du das man mehrere Lesebefehle koppelt und dann erst den Speicher liest? Ich meine das geht ja schlecht, wenn du nur 1byte liest und daraufhin dann viele Bytes schreibst, müsstest du ja ewig warten, oder habe ich da am Write-Combining was falsch verstanden?
-
Hallo,
Sorry, für mein Delay, ich hab eine recht bewegte Woche hinter mir.
Also stell dir vor du schreibst nen Framelimiter. Da holst du dir die aktuelle Zeit, berechnest den Frame, holst dir die nun aktuelle Zeit, bildest die Differenz und wartest gegebenenfalls (was für ein Wort ;) ).
Genau so eine Anwendung schwebt mir auch vor. Üblicherweise löst man das Problem, das man regelmäßig bestimmten Code abgearbeitet haben möchte, damit das man von einem periodischen Event (der genau mit einer bestimmten Frequenz oder Periodendauer kommt) "angetriggert" wird.
Der User-Code sieht dann etwa so aus:event = EventCreatePeridoc(frequenz); //erstelle ein Event-Object das mit einer bestimmten Frequenz immer wieder angetriggert wird
while(true)
{
EventWait(event); //warte bis Event getriggert wurde, setzt den Event nach dem Warten wieder auf ungetriggert zurück, wenn der Event bereits getriggert wurde dann muss nicht gewartet werden
tuWas; //Code der regelmäßig ausgeführt werden soll
}Solange der Code immer schnell genug fertig wird wartet der Thread immer genau die Rest-Zeit ab und macht dann weiter, falls der Code ein klein wenig zu lange braucht dann macht er sofort weiter. Der Vorteil ist das die ganze Zeitrechnerei nicht im User-Space mit relativen Zeiten sondern direkt im Kernel mit absoluten Zeiten stattfindet, der Kernel errechnet den nächsten Trigger-Zeitpunkt nicht als Differenz sondern absolut aus dem Zeitpunkt der Event-Erstellung und der Frequenz bzw. Periodendauer. Da die Triggerfrequenz nicht unbedingt Teilergleich (nennt man das so, ich denke da gibt es nen besseren Begriff) mit der System-Timer-Frequenz ist kommt es zu einem gewissen Jitter wenn die Trigger-Zeitpunkte in das System-Zeit-Raster überführt werden müssen, aber wenn die Rechnung im Kernel ordentlich gecodet ist dann ergibt sich auch auf lange Sicht keine Abweichung. Wenn man hingegen immer die sleep-Funktion mit einer Differenz aufruft dann werden sich da unvermeidlich Fehler aufakkumulieren, außerdem kannst Du sleep nicht mit negativen Werten benutzen falls Dein Code mal ein klein wenig überzogen hat (dann wäre auch Dein neuer Start-Zeitpunkt falsch).
Wenn Du möchtest können wir dazu aber mal einen neuen Thread aufmachen da eine ausführliche Erklärung sonst doch zu arg Offtopig wird.
Am besten noch in der libc.
Ich würde eher sagen, da auch ;) Denn du weißt nie was so ein Programmierer alles für Späße treibt.
Ohja, ich kenn mich ja schließlich auch selber. ;)
da ich dir Infos vorenthalten habe
Offensichtlich, is nicht schlimm. ;)
Vielleicht sollte man dazu mal nen extra Thread aufmachen, wo dann über Schedulingstrategien diskutiert wird.
Gerne.
Zum diskutieren (und manchmal auch streiten) hab ich (fast) immer Lust. ;)
Wo ist jetzt der Unterschied zw. non-cacheable und uncachceable (ich wollte das einfach über die Flags in der Pagetable machen)?
Ich glaube da ist kein Unterschied.
Die Bits (wimre 3 Bits) in den Page-Descriptoren werden als Index in ein spezielles MSR interpretiert und dort gibt es dann mehr Möglichkeiten, zumindest auf aktuellen CPUs. Ich weiß jetzt nicht mehr welches MSR das ist aber das sollte sich bestimmt in den einschlägig bekannten Dokus finden lassen, dieses MSR ist aber so vorbelegt das damit die alte/direkte Funktionalität der Descriptor-Bits quasi nachgeahmt wird.
Wenn ich dich richtig verstehe, meinst du das man mehrere Lesebefehle koppelt und dann erst den Speicher liest? Ich meine das geht ja schlecht, wenn du nur 1byte liest und daraufhin dann viele Bytes schreibst, müsstest du ja ewig warten,
Hä, was meinst Du? Kann es sein das Du "Schreibbefehle" und "schreibst" meinst?
oder habe ich da am Write-Combining was falsch verstanden?
Mit "Write-Combining" ist gemeint das der Schreibbefehl nicht sofort ausgeführt wird, also nicht sofort eine Write-Message mit den Daten losgeschickt wird, sondern das es einen kleinen zusätzlichen Write-Buffer (meistens 2 oder 4 Cache-Lines o.ä.) gibt in den der Schreibbefehl erst mal geht (und nicht in den normalen Cache) und wenn dann nachfolgenden Schreibbefehle in die selbe Cache-Line gehen dann landen die auch erst mal in diesem Puffer. Diese Puffer werden später in den Speicher geschrieben, aber da erst mal mehrere einzelne Schreibbefehle gesammelt werden müssen weniger richtige Schreibzugriffe auf den Speicher durchgeführt werden. Beim Schreibteil vom Kopieren werden damit immer ganze Cache-Lines gesammelt und am Stück zum Speicher gesendet, daher profitiert x86 beim memcpy mit mehr als 2000 Bytes auch (fast) gar nicht von ausgerichteten Daten. Siehe auch http://en.wikipedia.org/wiki/Write-combining.
Grüße
Erik
-
Sorry, für mein Delay, ich hab eine recht bewegte Woche hinter mir.
Kein Prob, habe die Woche auch nichts wirklich zustande gebracht ;)
Der Vorteil ist das die ganze Zeitrechnerei nicht im User-Space mit relativen Zeiten sondern direkt im Kernel mit absoluten Zeiten stattfindet, der Kernel errechnet den nächsten Trigger-Zeitpunkt nicht als Differenz sondern absolut aus dem Zeitpunkt der Event-Erstellung und der Frequenz bzw. Periodendauer. Da die Triggerfrequenz nicht unbedingt Teilergleich (nennt man das so, ich denke da gibt es nen besseren Begriff) mit der System-Timer-Frequenz ist kommt es zu einem gewissen Jitter wenn die Trigger-Zeitpunkte in das System-Zeit-Raster überführt werden müssen, aber wenn die Rechnung im Kernel ordentlich gecodet ist dann ergibt sich auch auf lange Sicht keine Abweichung. Wenn man hingegen immer die sleep-Funktion mit einer Differenz aufruft dann werden sich da unvermeidlich Fehler aufakkumulieren, außerdem kannst Du sleep nicht mit negativen Werten benutzen falls Dein Code mal ein klein wenig überzogen hat (dann wäre auch Dein neuer Start-Zeitpunkt falsch).
Nur mal als kurze Antwort, hast du schonmal versucht sowas zu schreiben (und dabei das restliche System nicht aus den Augen verloren)? Ich weiß das bei meinem Code eine Abweichung (welche auf nem alten PC mit nur nem PIT bei so 2µs pro Scheduler-Aufruf liegt) auftritt und die sich dann summiert. Bei nem Multi-CPU System liegt es am I/O-Aufkommen (und Spinlock Aufkommen) wie ungenau diese Zeit ist.
Hä, was meinst Du? Kann es sein das Du "Schreibbefehle" und "schreibst" meinst?
Du meintest doch das es nicht schlecht wäre ne Art "Read-Combining" zu haben oder? Und da müsstest du ja auf die Daten warten, bis halt genug Lesebefehle zusammengekommen sind, oder? Obwohl mir gerade auffällt dass das dann beim Write-Combining das selbe Problem geben würde, aber es scheint ja zu funktionieren. Ich habe halt gerade ein Problem damit, was passiert wenn du nur ein Byte schreiben willst, die CPU kann ja nicht warten bis andere Schreibbefehle den Buffer voll gemacht haben, denn es kann ja sein, das andere CPUs auf diesen Wert zugreifen wollen (dann würde dir auch ne Spinlock zum Schützen von kritischen Bereichen nichts nutzen).
Ich mach dann mal nen Thread für Schedulingstrategien auf, müsste mich damit ja eh mal befassen.
-
Hallo,
Nur mal als kurze Antwort, hast du schonmal versucht sowas zu schreiben (und dabei das restliche System nicht aus den Augen verloren)?
Ja, ich hab es allerdings nicht nur versucht sondern auch getan. Hat wunderbar funktioniert, war aber nur eine CPU, mit mehreren CPUs hätte mein damaliger Hack auch nicht funktioniert.
Ich weiß das bei meinem Code eine Abweichung (welche auf nem alten PC mit nur nem PIT bei so 2µs pro Scheduler-Aufruf liegt) auftritt und die sich dann summiert. Bei nem Multi-CPU System liegt es am I/O-Aufkommen (und Spinlock Aufkommen) wie ungenau diese Zeit ist.
Das es einen Jitter gibt ist völlig klar, aber wenn Du eine monotone Zeitquelle hast (wie z.B. den HPET, der PIT geht sicher auch aber da musst Du Dich mit einem groben Zeit-Raster arrangieren das kaum über 1000 Hz liegen wird) kannst Du doch mit der gleichmäßig voranschreitenden Zeit gut rechnen.
Wo genau hast Du bedenken? Soll ich dazu einen neuen Thread aufmachen?
Du meintest doch das es nicht schlecht wäre ne Art "Read-Combining" zu haben oder?
Ja. Ich würde mir dafür wünschen das die Write-Buffer auch für Lesebefehle benutzt werden können. Dieser Write-Buffer ist eine Art Cache, parallel (oder auch nachgeschaltet um Cache-Line-Write-Backs das normalen Caches aufnehmen zu können) zum normalen Daten-Cache, mit ein paar wenigen voll-assoziativen Cache-Lines, einfach aufgrund seiner winzigen Größe werden Daten dort nicht lange drin bleiben. Modifizierte Lines in diesem "Mini-Cache" werden, sobald sie nicht mehr die "zuletzt benutzte" sind, möglichst bald in den Speicher geschrieben. Schreibzugriffe werden dadurch nur kurz verzögert und sind eben auch nicht immer in korrekter Reihenfolge nach außen sichtbar. Mit WC markiert man nur Speicherbereiche die zwar nicht wirklich gecachet werden sollen aber bei denen eine kurze Verzögerung und inkorrekte Reihenfolge kein Problem sind, bestes Beispiel ist der Frame-Buffer auf einer Grafikkarte. Die Befehle MFENCE und SFENCE lehren/flushen wimre auch diesen Write-Buffer. Wenn in so einer Write-Buffer-Line nur ein paar modifizierte Bytes drin sind dann werden eben nur die zum Speicher gesendet wenn die betreffende Line verschwinden soll.
Beim Zusammenfassen von Lesezugriffen, was man dann wohl eher mit "Read-Ahead" umschreiben dürfte, stelle ich mir vor das zwar auch immer gleich ganze Cache-Lines gelesen werden und nachvolgende Lesebefehle sich gegebenenfalls auch daraus bedienen (so das nach außen nur ein Lesebefehl sichtbar ist) aber diese Cache-Lines nicht in den normalen Cache kommen, um dort länger zu bleiben, sondern in den kleinen Mini-Cache, um dort möglichst bald wieder zu verschwinden.
Lock-Variablen darf man in solche Speicherbereiche natürlich nicht legen. Die müssen entweder komplett ungecached sein oder richtig dem Cache-Kohärenz-Protokoll unterliegen. Solche schwach gecachten Speicherbereiche kann man aber zumindest mit normalen Locks absichern wenn man sich der Befehle LFENCE, SFENCE und MFENCE bedient, glaube ich zumindest aber so fit bin ich diesbezüglich bei x86 nun auch wieder nicht.
Ich mach dann mal nen Thread für Schedulingstrategien auf, müsste mich damit ja eh mal befassen.
Ich werd mal drüber nachdenken und dann was schreiben.
Grüße
Erik
-
Wo genau hast Du bedenken? Soll ich dazu einen neuen Thread aufmachen?
Ein neuer Thread wäre nicht schlecht zu dem Thema (hatte ich zwar schon in einem anderem Board, aber neue Ideen sind immer willkommen). Mein Lieblingsbeispiel für Bedenken ist der PIT, weil der Zugriff alleine schon langsam ist (pro Zugriff in/out 838ns Verzögerung) und dann kann es durch das Ausschalten von den Ints auch noch zu einer zusätzlichen Verzögerung kommen und dadurch das ich den Timer (welchen ich auch immer nutze) im One-Shot-Modus benutze, kommen bei mir pro Scheduler Aufruf 5 Zugriffe (3x out, 2x in) auf den Timer (was beim PIT alleine schon ne Verzögerung von 4190ns ~ 4µs macht, pro Scheduleraufruf!). Ich bin da gerne offen für Vorschläge zur Verbesserung (gibt nur Beschränkungen die es erschweren).
Beim Zusammenfassen von Lesezugriffen, was man dann wohl eher mit "Read-Ahead" umschreiben dürfte, stelle ich mir vor das zwar auch immer gleich ganze Cache-Lines gelesen werden und nachvolgende Lesebefehle sich gegebenenfalls auch daraus bedienen (so das nach außen nur ein Lesebefehl sichtbar ist) aber diese Cache-Lines nicht in den normalen Cache kommen, um dort länger zu bleiben, sondern in den kleinen Mini-Cache, um dort möglichst bald wieder zu verschwinden.
Mit "Read-Ahead" kann ich schon mehr anfangen (und sowas haben wir ja auch in neueren CPUs). Ich weiß nicht, aber reicht nicht der Prefetcher?
-
Hallo,
Ein neuer Thread wäre nicht schlecht zu dem Thema
Okay, ich bemühe mich das zeitnah zu schaffen, zur Zeit ist das leider nicht einfach bei mir. :-(
Mein Lieblingsbeispiel für Bedenken ist der PIT, weil der Zugriff alleine schon langsam ist ....
Wenn Du denn PIT immer wieder manuell anlaufen lässt dann geht das natürlich nach hinten los. Du brauchst zwingenst eine gleichmäßige und monotone Zeitquelle (der Counter im HPET ist da genau das richtige) ansonsten kann man damit nichts genaues timen (und die SW-Uhr geht auch noch falsch).
Mit "Read-Ahead" kann ich schon mehr anfangen (und sowas haben wir ja auch in neueren CPUs). Ich weiß nicht, aber reicht nicht der Prefetcher?
Die Prefetcher usw. moderner CPUs funktionieren nur in "richtig" gecacheten Bereichen. Ich hätte aber gerne etwas das Lesebefehle ordentlich beschleunigt und diese Daten trotzdem nicht für unbestimmte (lange) Zeit im normalen Cache landen. Bei Zugriffen auf Memory-Mapped-I/O-Datenbereiche von PCI-Hardware könnte das echt was nutzen. Für den Frame-Buffer gibt es ja extra das Write-Combining aber für Dinge wo gelesen werden soll gibt es leider nichts entsprechendes.
Grüße
Erik
-
Wenn Du denn PIT immer wieder manuell anlaufen lässt dann geht das natürlich nach hinten los. Du brauchst zwingenst eine gleichmäßige und monotone Zeitquelle (der Counter im HPET ist da genau das richtige) ansonsten kann man damit nichts genaues timen (und die SW-Uhr geht auch noch falsch).
Es ist besser das alles in einem neuen Thread zu besprechen, sonst wird meine Antwort zu lang und zu Off!
Okay, ich bemühe mich das zeitnah zu schaffen, zur Zeit ist das leider nicht einfach bei mir. sad
Kein Prob, ich hab im Mom auch nicht so viel Zeit.
-
Hallo,
Es ist besser das alles in einem neuen Thread zu besprechen,
Ja, ist angefangen.
Okay, ich bemühe mich das zeitnah zu schaffen, zur Zeit ist das leider nicht einfach bei mir.
Kein Prob, ich hab im Mom auch nicht so viel Zeit.
Deine extrem kurze Reaktionszeit auf meine Postings finde ich jedenfalls etwas beängstigend. :wink:
Grüße
Erik
-
Deine extrem kurze Reaktionszeit auf meine Postings finde ich jedenfalls etwas beängstigend. wink
Du schreibst aber auch meistens dann wenn ich mal wieder vor dem Rechner sitze ;)