Frage Syncronisierung von Thread?

Apeman

hustbaer schrieb:

Locks sind *immer* langsam.

wieso? bist du winapi-coder?

#define LOCK() scheduler_ticks &= ~ON; while(pending_tasks);
#define UNLOCK() scheduler_ticks |= ON;

ausserdem kommt's ja noch auf die aufruffrequenz der locks und unlocks an.
in der regel ist es in muktitasking-systemen besser, wenn eine resource oder critical section schnell wieder frei wird.

Jester

In der WinAPI gibt's afair auch atomare Int-Operationen. Das heißt, Du kommst ganz ohne Locks und Mutexes aus.

Apeman

Jester schrieb:

In der WinAPI gibt's afair auch atomare Int-Operationen. Das heißt, Du kommst ganz ohne Locks und Mutexes aus.

stimmt: http://msdn2.microsoft.com/en-us/library/ms683590.aspx

BorisDieKlinge

naja ich verwende das winapi critical_section gedöns... ist das so langsam? wie gehts schneller in der puren c++ syncronisierung?

#define LOCK() scheduler_ticks &= ~ON; while(pending_tasks);
#define UNLOCK() scheduler_ticks |= ON;

scheduler_ticks, pending_tasks und ON ?? was sind das für funktionen, kann mir das mal jemand erklären?

Apeman

BorisDieKlinge schrieb:

scheduler_ticks, pending_tasks und ON ?? was sind das für funktionen, kann mir das mal jemand erklären?

das ist nur pseudocode für sehr primitive 'critical sections'.
1. task switching stoppen.
2. abwarten bis alle tasks auf anderen prozessoren beendet sind.
3. critical section ausführen
4. task switching wieder einschalten.
vorteil: sehr schnell, durch die cs wird mit voller geschwindigkeit durchgerauscht, weil das task switching komplett deaktiviert ist.
nachteil: alle tasks sind gestoppt während die cs ausgeführt wird, auch solche, die damit nichts zu tun haben.
das war nur als beispiel gedacht, wegen hustbärs pauschalisierung, dass locks immer sehr langsam sein *müssen*. genau so hätte ich ein beispiel mit 'nem freescale S12X nennen können, der hardware-semaphoren hat und bei dem synchronisation von tasks praktisch keine CPU-zeit beansprucht, aber das wär' nun zu exotisch gewesen. sorry für die verwirrung, mit deinem problem hat das alles natürlich nichts zu tun.

hustbaer

Apeman schrieb:

BorisDieKlinge schrieb:

scheduler_ticks, pending_tasks und ON ?? was sind das für funktionen, kann mir das mal jemand erklären?

das ist nur pseudocode für sehr primitive 'critical sections'.
1. task switching stoppen.
2. abwarten bis alle tasks auf anderen prozessoren beendet sind.

Was im Schnitt etliche MILLIsekunden braucht.

3. critical section ausführen
4. task switching wieder einschalten.
vorteil: sehr schnell, durch die cs wird mit voller geschwindigkeit
durchgerauscht, weil das task switching komplett deaktiviert ist.

Wenn du das schnell nennst... naja. Da haben wir etwas andere Vorstellungen von "schnell". Schnell wäre für mich < 10nS oder sowas.

nachteil: alle tasks sind gestoppt während die cs ausgeführt wird, auch solche, die damit nichts zu tun haben.
das war nur als beispiel gedacht, wegen hustbärs pauschalisierung, dass locks immer sehr langsam sein *müssen*. genau so hätte ich ein beispiel mit 'nem freescale S12X nennen können, der hardware-semaphoren hat und bei dem synchronisation von tasks praktisch keine CPU-zeit beansprucht, aber das wär' nun zu exotisch gewesen. sorry für die verwirrung, mit deinem problem hat das alles natürlich nichts zu tun.

Locks müssen nicht immer langsam sein, gibt kein Gesetz welches das vorschreibt. Sie *sind* es bloss immer (zumindest bei > 1 CPU/Core mit shared memory).
Guck dir den Linux Kernel an, dort werden als Locks fast ausschliesslich Spin-Locks verwendet, und das bedeutet min. 1 atomic instruction pro Lock/Unlock Paar, auf vielen Plattformen sogar 2 atomic instructions.
Der Windows-Kernel verwendet genauso Spin-Locks. Und atomic instructions sind üblicherweise sehr sehr teuer, verglichen mit anderen Befehlen.

Ja, das ist eine Pauschalisierung, aber ich sehe nicht wo diese falsch ist.

hustbaer

Apeman schrieb:

Jester schrieb:

In der WinAPI gibt's afair auch atomare Int-Operationen. Das heißt, Du kommst ganz ohne Locks und Mutexes aus.

stimmt: http://msdn2.microsoft.com/en-us/library/ms683590.aspx

Jo, wobei der Grund dass Locks langsam sind ja die Verwendung von atomic instructions ist.
Faustregel für x86/x64 Systeme: wenn man mehr als 2 atomic instructions für irgendwas braucht kann man gleiche ne Spin-Lock nehmen weil's mit der Spin-Lock schneller sein wird als "Lock-Free".

Apeman

hustbaer schrieb:

Apeman schrieb:

BorisDieKlinge schrieb:

scheduler_ticks, pending_tasks und ON ?? was sind das für funktionen, kann mir das mal jemand erklären?

das ist nur pseudocode für sehr primitive 'critical sections'.
1. task switching stoppen.
2. abwarten bis alle tasks auf anderen prozessoren beendet sind.

Was im Schnitt etliche MILLIsekunden braucht.

warum sollte es? das 'warten' heisst ja nicht, dass andere tasks ihre komplette zeitscheibe verbraucht haben müssen, sondern es wird nur gewartet, bis sie angehalten wurden d.h. sie dürfen maximal ihren aktuellen maschinenbefehl ausführen und stoppen dann. ich verstehe nicht, wieso das *milli*sekunden dauern sollte?

jenz

kann mir mal einer erklären, warum man das mit mutexen serialisieren muss?
das hat ja wohl gar keinen sinn.

[quote="BorisDieKlinge"]

struct ThreadData{

 Mutex myMutex&

 int a,b;

 ThreadData(Mutex &m) : myMutex(m){}

 int GetA(){
   myMutex.lock();
   int tmp= a;
   myMutex.unlock();
   return tmp;
 }
int GetB(){
   myMutex.lock();
   int tmp= b;
   myMutex.unlock();
   return tmp;
 }

void SetA(int tmp){
 myMutex.lock();
 a=tmp;
 myMutex.unlock();
}
void SetB(int tmp){
 myMutex.lock();
 b=tmp;
 myMutex.unlock();
}

};

hustbaer

Apeman schrieb:

hustbaer schrieb:

Apeman schrieb:

BorisDieKlinge schrieb:

scheduler_ticks, pending_tasks und ON ?? was sind das für funktionen, kann mir das mal jemand erklären?

das ist nur pseudocode für sehr primitive 'critical sections'.
1. task switching stoppen.
2. abwarten bis alle tasks auf anderen prozessoren beendet sind.

Was im Schnitt etliche MILLIsekunden braucht.

warum sollte es? das 'warten' heisst ja nicht, dass andere tasks ihre komplette zeitscheibe verbraucht haben müssen,

doch

sondern es wird nur gewartet, bis sie angehalten wurden

wer soll sie denn anhalten?

d.h. sie dürfen maximal ihren aktuellen maschinenbefehl ausführen und stoppen dann.

falsch - woher sollen sie denn wissen dass sie stoppen sollen?

ich verstehe nicht, wieso das *milli*sekunden dauern sollte?

ist halt so.

hustbaer

jenz schrieb:

kann mir mal einer erklären, warum man das mit mutexen serialisieren muss?
das hat ja wohl gar keinen sinn.

doch das macht sinn, da du die sichtbarkeit von änderungen garantieren musst.

jenz

sichtbarkeit von änderungen garantieren?

was meinst du denn damit?

BorisDieKlinge

@Jenz: Andere frage, wie würdest du es tun? Was macht bei dir Sinn?

jenz

es werden nur ints gelesen bzw. geschrieben.

was soll da schief gehen?

da braucht man nichts synchronisieren.

vielleicht auf irgendwelchen exotischen geräten,
aber sonst sollte da doch nicht passieren können, oder liege ich da falsch?

hustbaer

jenz schrieb:

es werden nur ints gelesen bzw. geschrieben.

was soll da schief gehen?

da braucht man nichts synchronisieren.

vielleicht auf irgendwelchen exotischen geräten,
aber sonst sollte da doch nicht passieren können, oder liege ich da falsch?

Ohne volatile und/oder Mutex ist nichtmal garantiert ob der Compiler für die Zuweisung überhaupt Code generiert.
Ja, auf "exotischen" Geräten (z.B. PowerPC, DEC Alpha, ...) kann es passieren dass Änderungen am Speicher (eben "das Schreiben von ints") die CPU 1 macht von CPU 2 z.B. in der falschen Reihenfolge "gesehen" werden. Was je nachdem um was für Code es sich handelt katastrophale oder garkeine Folgen haben kann.

jenz

hustbaer schrieb:

Ohne volatile und/oder Mutex ist nichtmal garantiert ob der Compiler für die Zuweisung überhaupt Code generiert.

da hilft der mutex auch nicht. volatile muss sein.

hustbaer schrieb:

Ja, auf "exotischen" Geräten (z.B. PowerPC, DEC Alpha, ...) kann es passieren dass Änderungen am Speicher (eben "das Schreiben von ints") die CPU 1 macht von CPU 2 z.B. in der falschen Reihenfolge "gesehen" werden. Was je nachdem um was für Code es sich handelt katastrophale oder garkeine Folgen haben kann.

was hilft da der mutex?
da wird doch keine reihenfolge vorgegeben.

camper

jenz schrieb:

da hilft der mutex auch nicht. volatile muss sein.

nein. Bitte mach dich erst mit den Grundlagen ein wenig vertraut. volatile macht zugriffe auf eine variable beobachtbar. Und auch Aufrufe von I/O-Funktionen (zu denen mutex-locks gehören) sind beobachtbar. Folglich sind beide geeignet, "die Generierung von Code zu erzwingen". volatile wiederum ist völlig ungeeignet, die notwendige Semantik für geteilten Zugriff in mehreren Threads auszudrücken, da volatile-Zugriffe nur untereinander und innerhalb eines Threads geordnet sind - alles andere ist im Grunde undefiniert.

hustbaer schrieb:

Ja, auf "exotischen" Geräten (z.B. PowerPC, DEC Alpha, ...) kann es passieren dass Änderungen am Speicher (eben "das Schreiben von ints") die CPU 1 macht von CPU 2 z.B. in der falschen Reihenfolge "gesehen" werden. Was je nachdem um was für Code es sich handelt katastrophale oder garkeine Folgen haben kann.

was hilft da der mutex?
da wird doch keine reihenfolge vorgegeben.

Ein mutex - so wie andere Synchronisationsprimitive - etabliert eine zeitliche Ordnung von Zugriffen auf denselben (wie das geschieht, kann uns erst mal egal sein) - "vor, während, nach der anforderung des mutex" ist für eine bestmmmte Operation in allen Threads gleich. Da mutex locks, wie oben gesehen, beobachtbar sind und potentiell den globalen Zustand verändern, sind alle Zugriffe auf globale Zustände relativ zu diesem mutex-aufruf geordnet. Damit folgt, dass Datenzugriffe, die durch eine mutex geschützt werden, in allen Threads zeitlich gleich geordnet sind. Und das ist im Grunde, was Synchronisation bedeutet. volatile ist demgegenüber nahezu nutzlos.

Sichtbarkeit hat mittelbar auch etwas damit zu tun. Hier geht es im Grunde um die Identität von Objekten. Angenommen, wir haben in zwei Therads einen Pointer p auf z.B. ein int und dieser Pointer habe - wie auch immer er erlangt wurde - den gleichen Wert in beiden Threads. Bedeutet das dann, dass *p in beiden Threads auf das gleiche Objekt verweisen?:
Moderne Prozessoren haben alle einen Cache, der eine Kopie von Inhalten des Hauptspeichers enthält. Operation benutzen im Grunde nur diesen Cache und immer wenn sich dessen Inhalt verändert, muss der Prozessor den entsprechenden Hauptspeicherinhalt anpassen - das geschieht automatisch (und dieser Vorgang ist nebenbei in obigem Sinne zwischen verschiedenen Prozessoren durch die Hardware synchronisiert) ist aber nicht mit der Veränderung des Cacheinhalts identisch. Ein zweiter Prozessor (auf einem anderen Sockel und mit völlig getrennten Cache) muss nun dafür sorgen, dass er seinen Cacheinhalt - sofern dieser eine Kopie des gleichen Speicherplatzes enthält - ebenfalls anpasst. Das ist aber zeitlich und logisch völlig getrennt von der Operation, die die Änderung des Speichers verursacht hat. Für diese Anpassung ist ebenfalls die Hardware zuständig, aber sobald es keinen gemeinsamen Speicherbus mehr gibt (Stichwort NUMA) - oder das Busprotokoll das nicht so her gibt, kann der 2. Prozessor dieses Update nicht mehr zeitgleich mit dem 1. Prozessor durchführen. Beides ist in x86-Systemen weitgehend unproblematisch, da diese Architektur traditionell streng geordnet ist. Das muss nicht so bleiben, zumal eine solche Architektur schlecht skaliert. Was wir hier brauchen, ist eine memory barrier - vereinfacht gesagt synchronisiert diese zwischen Kopien des gleichen Objekts, während einen Mutex (zunächst) nur Zugriffe auf einer Kopie synchronisiert. Ein vollständiger Mutex wird in der Realität natürlich immer auch eine mamemory barrier mitbringen.

jenz

camper schrieb:

jenz schrieb:

da hilft der mutex auch nicht. volatile muss sein.

nein. Bitte mach dich erst mit den Grundlagen ein wenig vertraut. volatile macht zugriffe auf eine variable beobachtbar. Und auch Aufrufe von I/O-Funktionen (zu denen mutex-locks gehören) sind beobachtbar. Folglich sind beide geeignet, "die Generierung von Code zu erzwingen". volatile wiederum ist völlig ungeeignet, die notwendige Semantik für geteilten Zugriff in mehreren Threads auszudrücken, da volatile-Zugriffe nur untereinander und innerhalb eines Threads geordnet sind - alles andere ist im Grunde undefiniert.

hustbaer schrieb:

Ja, auf "exotischen" Geräten (z.B. PowerPC, DEC Alpha, ...) kann es passieren dass Änderungen am Speicher (eben "das Schreiben von ints") die CPU 1 macht von CPU 2 z.B. in der falschen Reihenfolge "gesehen" werden. Was je nachdem um was für Code es sich handelt katastrophale oder garkeine Folgen haben kann.

was hilft da der mutex?
da wird doch keine reihenfolge vorgegeben.

Ein mutex - so wie andere Synchronisationsprimitive - etabliert eine zeitliche Ordnung von Zugriffen auf denselben (wie das geschieht, kann uns erst mal egal sein) - "vor, während, nach der anforderung des mutex" ist für eine bestmmmte Operation in allen Threads gleich. Da mutex locks, wie oben gesehen, beobachtbar sind und potentiell den globalen Zustand verändern, sind alle Zugriffe auf globale Zustände relativ zu diesem mutex-aufruf geordnet. Damit folgt, dass Datenzugriffe, die durch eine mutex geschützt werden, in allen Threads zeitlich gleich geordnet sind. Und das ist im Grunde, was Synchronisation bedeutet. volatile ist demgegenüber nahezu nutzlos.

hallo hallo, vielleicht liest du einfach noch mal den ganzen thread???

es geht um int variablen, da wird ein mutex überhaupt keine codeerzeugung bewirken...

und die reihenfolge sehe ich immer noch nicht. klar, mit nem mutex können zwei threads/prozesse nicht gleichzeitig auf die variable zugreifen, aber das können sie bei ints sowieso nicht...
(edit)
natürlich prozesse können das, aber es ist völlig egal in dem hier gezeigten beispiel. es gibt keine "reihenfolge"
(/edit)

man muss lesen von a und b einfach nicht mit nem lock umgeben.

wenn ich mehrere schritte nacheinander abarbeiten will, dann muss ich das locken.
zum beispiel tauschen von zwei variablen:

pseudo

lock
int help = a;
a = b;
b = help;
unlock

aber nur das lesen von dem int???

gebt mir doch bitte mal ein beispiel...

BorisDieKlinge

@jenz: Das war eine Allgemeine frage, es können auch andere typen sein... Es ging lediglich darum, ob ich jedes mal lock bzw. unlock bei einem zugriff, oder ob ich die ganze struktur mit den daten komplett locke...

camper

jenz schrieb:

hallo hallo, vielleicht liest du einfach noch mal den ganzen thread???

denkst du nach, bevor du postest?

man muss lesen von a und b einfach nicht mit nem lock umgeben.
...
wenn ich mehrere schritte nacheinander abarbeiten will, dann muss ich das locken.

Ohne Begründung ist das nur so dahergesagt. Und nebenbei auch falsch. Selbst wenn der Zugriff als solcher atomar ist, wird das Lesen ohne Synchronisation den Inhalt vor oder nach (bezogen auf die absolute Zeit) der Änderung in einem anderen Thread liefern - das wird selten das sein, was man will.

BorisDieKlinge schrieb:

@jenz: Das war eine Allgemeine frage, es können auch andere typen sein... Es ging lediglich darum, ob ich jedes mal lock bzw. unlock bei einem zugriff, oder ob ich die ganze struktur mit den daten komplett locke...

Beides ist möglich und die Antwort hängt von der Nutzung ab und davon, welche Invarianten zwischen den Elementen der Struktur gelten sollen.