Threading Teil der Sprache?

SG1

StringBuffer/Builder schrieb:

Das bekannteste Beispiel dürfte hier java.lang.StringBuffer sein, diese Klasse ist nicht Threadsicher und damit veraltet.
Deswegen wurde mit Java 7 java.lang.StringBuilder eingeführt. StringBuilder IST threadsicher.

Äh... nein. StringBuffer IST threadsicher und deshalb langsam. Deshalb wurde mit Java 5(!) StringBuilder eingeführt.

das ist vielleicht für dich interessant: http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

Duplikateneliminator schrieb:

das ist vielleicht für dich interessant: http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

OK, die Beispiele sind relativ konstruiert, aber da ich auch so einen Kompilerbauer kenne, weiß ich, dass die allen möglichen Kram machen, wenn man ihnen nicht vorschreibt, dass Threading Teil der Sprache ist. Es ist also nicht wirklich ein technisches Problem, sondern ein kompilerbau-juristisches.

tntnet

StringBuffer/Builder schrieb:

C kam viele Jahre ohne Threading aus, erst seit dem neusten Standard ist es Teil der Sprache.

Inwiefern ist Threading Teil der Sprache C . Was bedeutet das überhaupt, dass Threading "Teil der Sprache" ist?

tntnet schrieb:

Was bedeutet das überhaupt, dass Threading "Teil der Sprache" ist?

Dass Threads und Synchronizations-Methoden per Definition zum Sprachstandard gehören und dass Kompilerbauer Nebenläufikeit beachten müssen. Ein Kompilerbauer darf nicht mehr sagen: ich kann das so optimieren, weil der Code bei sequentieller Abarbeitung das gleiche Ergebnis liefert und Multithreading kenne ich per Definition doch garnicht (siehe z.B. 4.3 Register promotion in dem paper oben).

@fredsprecher: teilweise hast du mit Kompilerbaujura wohl recht allerdings sind die Probleme nicht umbedingt so vernachlässigbar bzw. konstruiert. Das ist durchaus auch ein Problem (neben vielen anderen) bei automatischer Programmoptimierung bzw. Programmparallelisierung. Da will man ja auch ein bisschen an die Grenzen gehen.

Noch ein Paper, das vllt. interessant ist: Peter Buhr: "Are Safe Concurrency Libraries Possible?" (ich weiß allerdings nicht, ob das frei verfügbar ist).

tntnet schrieb:

StringBuffer/Builder schrieb:

C kam viele Jahre ohne Threading aus, erst seit dem neusten Standard ist es Teil der Sprache.

Inwiefern ist Threading Teil der Sprache C . Was bedeutet das überhaupt, dass Threading "Teil der Sprache" ist?

Solltest du kennen:
http://de.wikipedia.org/wiki/Varianten_der_Programmiersprache_C#C11

@SG1
Hm, okay. Kann sein.

tntnet

StringBuffer/Builder schrieb:

tntnet schrieb:

StringBuffer/Builder schrieb:

C kam viele Jahre ohne Threading aus, erst seit dem neusten Standard ist es Teil der Sprache.

Inwiefern ist Threading Teil der Sprache C . Was bedeutet das überhaupt, dass Threading "Teil der Sprache" ist?

Solltest du kennen:
http://de.wikipedia.org/wiki/Varianten_der_Programmiersprache_C#C11

Ich kann da nichts erkennen, dass Threading "Teil der Sprache" ist. In C11 kamen Funktionen für therading, atomics und Speicherausrichtung hinzu. Aber das sind doch, wenn ich das richtig verstehe, im Prizip auch nur Bibliotheksfunktionen. Dort steht nichts, was den Compiler selbst betreffen würde.

Marthog

Threading muss insofern Teil der Sprache sein, als dass bestimmte Optimierungen (Reihenfolge geaendert) nicht gemacht werden duerfen.
Ausserdem macht es schon einen Unterschied, ob eine Sprache mit dem ziel der Multithreadingunterstuetzung entwickelt wurde oder es nachgeruestet wird.

rapso

fredsprecher schrieb:

Ich habe mal die Aussage gehört, dass Threading Teil der Sprache sein muss, damit es sicher funktioniert, ohne dass dies groß begründet wurde. Weiß einer ein Beispiel wieso das so sein sollte? Im Ende sind es doch nur System Aufrufe um Threads/Mutexe... zu starten/sperren... Ist es das nicht egal, ob die per Library oder Sprachbestandteil aufgerufen werden.

Mit "Threading" sind dabei nicht hardware threads gemeint, denn du kannst auch 'threading probleme' mit nur einem thread bekommen wenn du z.b. co-routines verwendest.

das klassische beispiel ist

while(WaitForFlag==true)
{
}

wenn du den code so siehst, wuerdest du denken "endlosschleife". der compiler kann das auch erstmal annehmen.

auch wenn du sowas machst

while(WaitForFlag==true)
{
  CoRoutine();
}

kann ein compiler die annahme treffen es waere eine endlosschleife, obwohl du dort den 'thread' switchen willst wodurch sich "WaitForFlag" aendern koennte.

wenn nun die sprache (und manchmal nur der compiler) support fuer 'threading' bieten, geben sie dir entweder die garantie dass das obere nicht zu einer endlosschleife compiliert wird oder dass du wenigstens moeglichkeiten hast den code so zu schreiben dass er thread-safe compiliert wird.

das oben ist nur ein beispiel. es gibt noch viele andere faelle, z.b. ist java script eine sehr dynamische sprache und du kannst datentypen so veraendern dass sehr komplexe, andere codeablaeufe stattfinden. es ist fast unmoeglich java script vorzukompilieren. deswegen haben die JIT compiler unter der annahme von bedingungen optimierte code-stuecke, wenn du eine der bedingungen aenderst, kompiliert der JIT den bereich neu. damit natuerlich der compiler nicht bei jedem instruction pointer alle bedingungen pruefen muss, gibt es an den stellen wo die annahmen veraendert werden koennen (also zuweisungen von neuen werten) einen check. wenn du zwei threads laufen wuerden und ein innerer loop in einem optimierten teil spinnt, ausserhalb jemand ein flag aendert der ein neucompilieren benoetigen wuerde, wuerde der spinnende thread weder etwas davon erfahren noch koennte man es neucompilieren fuer die naechsten threads weil es parallel zwei verschiedene logics gebe.

deswegen hilft es nichts eine 'thread lib' zu erstellen oder zu binden, wenn die sprache dir solche garantieen nicht geben kann und die garantie kann dir auf sprach oder auf compiler ebene gegeben werden (bei c bzw c++ hat gcc 2.9.5x und VC++6 wirklich schnellen code generiert, aber fuer optimierungen oft annahmen getroffen die fatal fuer multithreading waren, nachfolge versionen waren erstmal etwas langsammer, haben aber die fehler nicht mehr erzeugt.) Eine notloesung ist es manchmal die optimierungen auszuschalten, weil dann annahmen fuer die CPU auf der das laeuft angenommen werden, was aber sehr schwierig bis unmoeglich wird, wenn die sprache vielleicht auf einer virtual machine laeuft. ein wert im speicher den du die ganze zeit liest kann bei einer VM bzw dem parser in eine temporaere tabelle gelegt werden und dort wird rein garnichts davon bemerkt ob ein anderer thread das modifiziert.

rapso schrieb:

while(WaitForFlag==true)
{
}
wenn du den code so siehst, wuerdest du denken "endlosschleife".

ich würde denken "wieso wird auf die ge-shared-te Resource "WaitForFlag" ungeschützt zugegriffen ?"

wenn man über einen Lock-Mechanismus zugreift, kann der Kompeiler es nicht mehr so ohne Weiteres wegoptimieren.

rapso

großbuchstaben schrieb:

rapso schrieb:
while(WaitForFlag==true)
{
}
wenn du den code so siehst, wuerdest du denken "endlosschleife".
ich würde denken "wieso wird auf die ge-shared-te Resource "WaitForFlag" ungeschützt zugegriffen ?"

wozu solltest du das in einem single-threaded environment annehmen? (wir zeigen hier ja erstmal auf, was passiert wenn threading nicht teil der sprache bzw nicht vom compiler supported wird). Du hast also aus compiler sicht eine variable und im scope vom loop wird sie nicht mehr beschrieben, ergo kannst du annehmen, dass es ein endlossloop ist falls sie anfangs true ist.
(mit RPC bzw signaling an sich kannst du das problem auch ohne volatile umgehen, aber damit hast du kein threading mehr auf sprach ebene, sondern auf prozess ebene, ergo of topic).

wenn man über einen Lock-Mechanismus zugreift, kann der Kompeiler es nicht mehr so ohne Weiteres wegoptimieren.

wenn du es per RPC ausliest, kann er es vermutlich auch nicht. aber es reicht wenn er annimmt die variable waere volatile und wenn die VM bzw CPU das auch unterstuetzt. (kleine microcontroller haben meistens keine atomics, aber programmierer simulieren oefter ueber co-routines 'threading', manchmal auch ueber interrupts, daher die eigentliche festsetzung dass volatile reicht).

das wirst du bei einer sprache aber selten mittels einer 'lib' hinzufuegen. die sprache muss dir die moeglichkeit bieten oder wenigstens erlauben die eigentliche sprache zu erweitern (in alten c compilern wurden atomics mit inline assembler hinzugefuegt und bis heute ist z.b. in gcc jede inline assembler stelle eine optimization barrier).

rapso schrieb:

großbuchstaben schrieb:

ich würde denken "wieso wird auf die ge-shared-te Resource "WaitForFlag" ungeschützt zugegriffen ?"

wozu solltest du das in einem single-threaded environment annehmen?

weil du von einem Multi-threaded environment sprichst:

obwohl du dort den 'thread' switchen willst wodurch sich "WaitForFlag" aendern koennte.

rapso schrieb:

die sprache muss dir die moeglichkeit bieten oder wenigstens erlauben die eigentliche sprache zu erweitern

das reicht zumindest mir aber nicht. Erst mit garantierter Atomarität der betreffenden Sprachmittel würde ich explizites Acquire/Release von shared resources sparen.

was, wenn zwischen dem CPU-Befehl "Flagwert lesen" und "Flag auf 0 testen" ein Threadwechsel zu einem Thread stattfindet, der das flag ändert, sodaß der nächste Schleifendurchlauf mit falscher Annahme über den tatsächlichen Zustand läuft?

es bleibt dabei, für mich ist die Grundfrage, welche von den verschiedenen Vorgängen auf den verschiedenen Ebenen (Library-Funktionen, Dedizierte Sprachmittel, erzeugter Assemblercode) garantiert atomar sind und welche nicht.

Sicherheitshalber könnte ich jeden Zugriff auf eine shared Resource mit einem acquire/release Mechanismus schützen. Sind die betreffenden acquire/release Mechanismen atomar ? Bis auf CPU-Ebene ? Könnte ein Interrupt durch ein unvorhergesehenes Ereignis einen laufenden acquire stören ? Nebenläufigkeit beweisbar sicher zu machen scheint mir nicht ganz unkompliziert.

rapso

großbuchstaben schrieb:

rapso schrieb:

großbuchstaben schrieb:

ich würde denken "wieso wird auf die ge-shared-te Resource "WaitForFlag" ungeschützt zugegriffen ?"

wozu solltest du das in einem single-threaded environment annehmen?

weil du von einem Multi-threaded environment sprichst:

obwohl du dort den 'thread' switchen willst wodurch sich "WaitForFlag" aendern koennte.

wie du selbst siehst, war das auf das zweite beispiel bezogen wo co-routines als beispiel gegeben wurden und gleich im naechsten satz sag ich dass die sprachen dir dafuer loesungen bieten muessen. dein atomic vorschlag ist natuerlich eine valide moeglichkeit. ich hielt es allgemein, da es, wie gesagt, auch ohne atomics geht.

rapso schrieb:

die sprache muss dir die moeglichkeit bieten oder wenigstens erlauben die eigentliche sprache zu erweitern

das reicht zumindest mir aber nicht. Erst mit garantierter Atomarität der betreffenden Sprachmittel würde ich explizites Acquire/Release von shared resources sparen.

naja, aber es geht aber nicht darum was dir reicht oder was du sparen moechtest, es geht um das prinzip wann eine sprache threading supportet und wann nicht und (neben dem eigentlichen multithreading) volatile variablen sind das minimum. diese existieren nur aus dem grund um ausserhalb deines 'threads' existierende bereiche zu lesen und zu schreiben fuer threads (ob von deinem prozess oder sogar von prozessen auf anderer hardware im system). welchen nutzen sollte volatile sonst haben?

was, wenn zwischen dem CPU-Befehl "Flagwert lesen" und "Flag auf 0 testen" ein Threadwechsel zu einem Thread stattfindet, der das flag ändert, sodaß der nächste Schleifendurchlauf mit falscher Annahme über den tatsächlichen Zustand läuft?

atomare befehle braucht man nicht fuers lesen (obwohl mit swapexchange es moeglich waere),entsprechend: ob atomar oder in den zwei schritten, in beiden faellen faehrt die schleife fort mit dem wissen da stand 0.

es bleibt dabei, für mich ist die Grundfrage, welche von den verschiedenen Vorgängen auf den verschiedenen Ebenen (Library-Funktionen, Dedizierte Sprachmittel, erzeugter Assemblercode) garantiert atomar sind und welche nicht.

Die eigentliche frage ist immer eine frage von ownership. Es geht nicht wirklich darum, ob eine operation atomar ist, sondern ob ownership von etwas fuer alle beteiligten erlangt bzw validiert werden kann.

Beispiel:

int Buffer[2048];//irgendwo global
.
.
.
AtomicSpinLock(Buffer[0]);
Buffer[2047]=fooOfThisThread;
AtomicUnlock(Buffer[0]);

jetzt hast du also atomics benutzt und bist total sicher, stimmts? nein, das ist falsch wenn du das allgemein annimmst. bei x64 binaries als beispiel aendert die CPU die schreibreihenfolge von unabhaengigen speicheraddressen. wenn also zwei threads laufen und Buffer[2047] beschreiben, kann es, sein dass der wert vom zweiten thread zuerst stored wird, obwohl die atomics selbst systemweit garantiert atomar abliefen.
Es reicht also nicht atomics zu haben, worauf es ankommt ist, dass ownership im system klar ist und dabei gibt es viele wege, fakt ist aber, dass auch systeme ohne atomics threads supporten. Ein klassisches beispiel ist das ABA-problem, es zeigt auf dass auch atomics nur ein werkzeug ist um ownership zu erhalten, weil ohne ownership (nur mit atomics) meistens das problem weiterbesteht.

Sicherheitshalber könnte ich jeden Zugriff auf eine shared Resource mit einem acquire/release Mechanismus schützen.

lass mich das mal auf PowerPC beantworten:

Sind die betreffenden acquire/release Mechanismen atomar ?

nein, es gibt keine atomics im acquire/release sinne.

Bis auf CPU-Ebene ?

meines wissens hat die CPU keine atomics.

Könnte ein Interrupt durch ein unvorhergesehenes Ereignis einen laufenden acquire stören ?

ja, das kann er. aber nicht nur ein interrupt, jeder schreibvorgang kann die ownership zerstoeren.

bei PowerPC laeuft das mit 'reservations' (was quasi eine volatile ownership ist). Du kannst damit atomics simulieren, aber reservations sind mit steigender prozess zahl effizienter (deswegen haben die neusten Intel CPUs jetzt auch reservations).

Die idee dabei ist dass du ownership 'anmeldest' beim memory controller und auf dem speicherbereich deine operationen durchfuehrst. wenn du fertig bist damit kannst du zum memory controller ein 'completion' schicken (manchmal faelschlicherweise als 'commit' bezeichnet), der controller antwortet dir dann, ob der bereich beschrieben wurde oder ob jemand anderes darauf schrieb und damit deine reservation invalide ist und der ganze vorgang invalide ist.

rapso schrieb:

jetzt hast du also atomics benutzt und bist total sicher, stimmts? nein, das ist falsch wenn du das allgemein annimmst. bei x64 binaries als beispiel aendert die CPU die schreibreihenfolge von unabhaengigen speicheraddressen.

wenn ein anderer Thread meinen Schreibvorgang stören kann, nachdem ich ihn "angemeldet" habe und bevor ich ihn als erledigt "abgemeldet" habe, ist mein Schreibvorgang aus meiner Sicht nicht mehr atomar. Ich habe ausdrücklich atomar auf die verschiedenen Ebenen bezogen, von Library-Funktionen bis auf CPU-Ebene.

Kellerautomat

rapso schrieb:

atomare befehle braucht man nicht fuers lesen

Doch, braucht man. Wer so eine Schleife schreibt, ist selbst schuld.

camper

tntnet schrieb:

StringBuffer/Builder schrieb:

tntnet schrieb:

StringBuffer/Builder schrieb:

C kam viele Jahre ohne Threading aus, erst seit dem neusten Standard ist es Teil der Sprache.

Inwiefern ist Threading Teil der Sprache C . Was bedeutet das überhaupt, dass Threading "Teil der Sprache" ist?

Solltest du kennen:
http://de.wikipedia.org/wiki/Varianten_der_Programmiersprache_C#C11

Ich kann da nichts erkennen, dass Threading "Teil der Sprache" ist. In C11 kamen Funktionen für therading, atomics und Speicherausrichtung hinzu. Aber das sind doch, wenn ich das richtig verstehe, im Prizip auch nur Bibliotheksfunktionen. Dort steht nichts, was den Compiler selbst betreffen würde.

Betrachte Abschnitte 5.1.2.3 und 5.1.2.4 - dort ist der entscheidende Fortschritt zu finden.

rapso

großbuchstaben schrieb:

rapso schrieb:

jetzt hast du also atomics benutzt und bist total sicher, stimmts? nein, das ist falsch wenn du das allgemein annimmst. bei x64 binaries als beispiel aendert die CPU die schreibreihenfolge von unabhaengigen speicheraddressen.

wenn ein anderer Thread meinen Schreibvorgang stören kann, nachdem ich ihn "angemeldet" habe und bevor ich ihn als erledigt "abgemeldet" habe, ist mein Schreibvorgang aus meiner Sicht nicht mehr atomar. Ich habe ausdrücklich atomar auf die verschiedenen Ebenen bezogen, von Library-Funktionen bis auf CPU-Ebene.

die von dir angemeldeten schreibvorgaenge waren atomar. damit war dein zugriff der zwischendurch passiert und nicht atomar war trotzdem nicht sicher. der zugriff war nur ein beispiel, es kann jede andere blackbox sein die du nicht komplett mit atomics ausschmueckst. Aus sicht der hardware waren nur die atomics volatile in dem fall.

oder suggerierst du gerade, dass du alle memory operationen atomar machen wuerdest um sicher zu gehen?

rapso

Kellerautomat schrieb:

rapso schrieb:

atomare befehle braucht man nicht fuers lesen

Doch, braucht man. Wer so eine Schleife schreibt, ist selbst schuld.

du spassmacher

rapso schrieb:

die von dir angemeldeten schreibvorgaenge waren atomar. damit war dein zugriff der zwischendurch passiert und nicht atomar war trotzdem nicht sicher. der zugriff war nur ein beispiel, es kann jede andere blackbox sein die du nicht komplett mit atomics ausschmueckst. [...]
oder suggerierst du gerade, dass du alle memory operationen atomar machen wuerdest um sicher zu gehen?

dein Einwand mit dem write reordering trotz Atomarität auf Anweisungsebene ist berechtigt. Ich habe aber trotzdem den Eindruck, wir meinen ungefähr das Gleiche.