Aktuelle Zeit: 07.07.2020 01:56

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]




Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
 Betreff des Beitrags: Critical Sections selbst erstellen :) [3 Methoden]
BeitragVerfasst: 20.04.2005 13:46 
Offline
Benutzeravatar

Registriert: 10.09.2004 14:40
NEU #2: Weitere Methode hinzugefügt, sie ist auf Seite 2 zu finden!

Einleitung
Immer wieder hört man, es sei absolut unmöglich selbst eine Alternative für Critical Sections zu erstellen, hiermit möchte ich belegen, das dies alles falsche Aussagen sind!

Was sind Critical Sections?
Die sog. Critical Sections dienen dazu, dass ein bestimmter Codeabschnitt nie gleichzeitig mit einem anderen bestimmten Codeabschnitt ausgeführt wird. Dies kann z.B. beim Bearbeiten von Strings nützlich sein (vor allem bei PureBasic), denn wenn dort mehrere Threads an einem String arbeiten führt das zum Abstürzen des Programms.

Wie kommt dieses Problem zustande?
Grund für dieses Problem ist vor allem der Speicherzugriff und die Gefahr, das wärend dem Ausführen des einen Threads der Prozessor auf einen anderen umschaltet. Anhand eines Beispieles könnte man es so erklären
MOV eax,[variable]
ADD eax,100
MOV [variable],eax

Angenommen unser Prozessor switcht nun nach dem 1. Befehl (MOV eax, ...) in einen anderen Thread der den gleichen Code beinhaltet und der zur Variable 100 addiert! Zurück beim anderen Thread hat sich EAX jedoch nicht geändert, deshalb wird hier in diesem Beispiel einmal zählen unterschlagen!
Hierbei kann das Programm zwar nicht abstürzen, aber die Ursache ist eigentlich die gleiche!

Ideen zur Lösung des Problems
Allgemein kann man nun sagen, das etwas Threadsicher ist, wenn nur EIN einziger Speicher-Zugriffs-Befehl für eine Variable verwendet wurde (oder es sich natürlich um verschiedene Speicherbereiche handelt)

Um trotzdem Strings/LinkedLists/Speicherbereiche/Globale Variablen verwenden zu können, die standartmäßig unsicher sind, hier einen Code für eine Critical Section, die (fast) ohne fremde APIs auskommt: der einzige Befehl der verwendet wird dient dazu, die CPU-Auslastung zu erniedrigen xD

Die hier beschriebene Lösung verwendet dafür den etwas weniger bekannten, jedoch seit dem 486er vorhandenen Befehl XADD

[XADD Ziel, Quelle], das für "exchange and add" steht führt nacheinander zwei Aktionen durch:
- Vertauscht den Inhalt der beiden Operatoren
- Addiert beide Operatoren und schreibt das Ergebnis in den ersten Operator zurück

Dadurch können wir den Variableninhalt auslesen und gleichzeitig manipulieren, ohne dabei den Thread unsicher werden zu lassen!

EDIT: Den folgenden Code am besten mit Debugger starten, da keine grafische Oberfläche vorhanden ist! Zum testen kann man z.B. einfach mal die Enters und Leavs auskommentieren, und man wird merken, das das Programm schon nach kurzer Zeit crasht!

Code:

;-
;- PureFan's Critical Sections *SPECIAL*
;-
;- Posted in: German PureBasic Board
;- Date:      20.04.05
;-

Structure Pure_CS
  In.l
  Out.l
EndStructure

Procedure Pure_InitCS(*PCS.Pure_CS)
  *PCS\In=0
  *PCS\Out=0
EndProcedure

Procedure Pure_EnterCS(*PCS.Pure_CS)
  !POP Edi           ;POP/PUSH dient zum schnellen Einlesen des Parameters *PCS in das Register EDI
  !PUSH Edi
  !XOR Esi,Esi
  !INC Esi           
  !XADD [Edi],Esi    ;XOR/INC/XADD liest zunächst den alten IN-Status in die Variable ESI aus
                     ;und erhöht diese danach um 1
 
  !.loop:
 
  !PUSH dword 1
  !CALL _Sleep@4     ;1msec warten
 
  !CMP [Edi+4],Esi   ;Wartet bis der OUT-Status dem gespeicherten Wert ESI entspricht
  !JNE .loop
EndProcedure
 
Procedure Pure_LeaveCS(*PCS.Pure_CS)
  !POP Edi
  !PUSH Edi
  !INC dword[Edi+4]  ;Erhöht den OUT-Status um 1
EndProcedure


;/
;/ Example for PureFan's Critical Sections
;/

Global SichereStrings.Pure_CS
Pure_InitCS(SichereStrings)

Global GlobalerString.s

Procedure String_Thread(Parameter)
  Repeat
    Pure_EnterCS(SichereStrings)
   
    lokaler_string.s=GlobalerString+"hallo"
    GlobalerString.s=Right(lokaler_string.s,100)
   
    Pure_LeaveCS(SichereStrings)
  ForEver
EndProcedure

For I=1 To 10
  CreateThread(@String_Thread(),I)
Next I

Repeat
  Pure_EnterCS(SichereStrings)
 
  lokaler_string.s=GlobalerString+"hallo"
  GlobalerString.s=Right(lokaler_string.s,100)
 
  Pure_LeaveCS(SichereStrings)
ForEver

_________________
Procedure x(a,b,c):If a:ProcedureReturn b:EndIf:ProcedureReturn c:EndProcedure:For I=0 To 6:T.s+Chr(I&1+x(((I&4)/4+(I&2)/2-I&1+1)&6,1,0)<<1+x(I&1-(I&4)/4,1,0)<<2+x((I+2)&7,0,1)<<3+((4-(I+1)&4)/4)<<4+x(3-(I+3)&3,1,0)<<5+64):Next I:Debug T


Zuletzt geändert von PureFan am 14.05.2005 14:29, insgesamt 3-mal geändert.

Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 20.04.2005 14:26 
Offline
Benutzeravatar

Registriert: 29.08.2004 08:48
genial !!!

Einfach zu verstehen, einfach einzubauen.

_________________
Rings hat geschrieben:
ziert sich nich beim zitieren


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 20.04.2005 17:53 
Offline
Benutzeravatar

Registriert: 29.08.2004 08:37
Gute Arbeit ;) weiter so!

_________________
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 20.04.2005 18:15 
Offline
Ein Admin
Benutzeravatar

Registriert: 29.08.2004 20:20
Wohnort: Saarbrücken
Sehr schön. Das kann ich gerade gut gebrauchen.

Wie lange wartet dieser Sleep-Befehl in der Warteschleife zwischen den einzelnen Überprüfungen?

Was ist, wenn die Pure_EnterCS()-Procedure zur selben Zeit aufegrufen wird und ein Taskswitch an den entscheidenen Stellen auftritt? Oder gibt es vielleicht gar keine entscheidenen Stellen?

Da ich mich in ASM nicht wirklich auskenne, würden mich ein paar Kommentare in deinem Code interessieren. Das Grundprinzip habe ich verstanden, aber die Details sicher nicht.

_________________
Ubuntu Gnome 20.04 LTS x64, PureBasic 5.72 x64 (außerdem 4.41, 4.50, 4.61, 5.00, 5.10, 5.11, 5.21, 5.22, 5.30, 5.31, 5.40, 5.50, 5.60, 5.71b2)
"Die deutsche Rechtschreibung ist Freeware, du darfst sie kostenlos nutzen – Aber sie ist nicht Open Source, d. h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen."


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 20.04.2005 18:46 
Offline
Benutzeravatar

Registriert: 10.09.2004 14:40
Thx für die Lobe @all ;)

Neben einfach zu verstehen und einzubauen ist es auch noch schnell und portierbar! Selbst bei Linux würde sie einwandfrei arbeiten! ;)

@NicTheQuick:

Zitat:
Wie lange wartet dieser Sleep-Befehl in der Warteschleife zwischen den einzelnen Überprüfungen?

!PUSH dword 1
!CALL _Sleep@4

Zwischen dein Einzelnen überprüfungen wird jeweils 1msec gewartet. Diese 1msec dient allerdings nur dazu, das Windows an dieser Stelle den Thread switched.. Wenn ihm eine Auslastung von 99% nichts ausmacht, kann man diese beiden Befehle auch einfach auskommentieren!

Zitat:
Was ist, wenn die Pure_EnterCS()-Procedure zur selben Zeit aufegrufen wird und ein Taskswitch an den entscheidenen Stellen auftritt? Oder gibt es vielleicht gar keine entscheidenen Stellen?


Durch die Verwendung von XADD gibt es keine gefährlichen Stellen mehr. Das ganze ist somit 100% crash-sicher, wenn alle kritischen Befehle in eine solche Sektion eingefügt werden!

Im Details geht das so:

Jeder Thread, der etwas ausführen will "zieht" sich sozusagen eine Wartenummer. Durch XADD wird garantiert, das jeder Thread eine einmalige Nummer hat, und keine doppelt verwendet wird. (Der Prozessor führt ja keine halben Befehle aus xD) Danach wartet die Prozedur bis der Thread an der Reihe ist. (Schleife mit Delay bis Wartenummer = *PCS\Out) Das Leave ist dann notwendig, um die Variable *PCS\Out zu erhöhen, damit der nächste Thread mit der Ausführung fortfährt.

Wenn es weitere Fragen gibt oder etwas unklar ist, könnt ihr gerne fragen ;)

_________________
Procedure x(a,b,c):If a:ProcedureReturn b:EndIf:ProcedureReturn c:EndProcedure:For I=0 To 6:T.s+Chr(I&1+x(((I&4)/4+(I&2)/2-I&1+1)&6,1,0)<<1+x(I&1-(I&4)/4,1,0)<<2+x((I+2)&7,0,1)<<3+((4-(I+1)&4)/4)<<4+x(3-(I+3)&3,1,0)<<5+64):Next I:Debug T


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 20.04.2005 19:03 
Offline
Ein Admin
Benutzeravatar

Registriert: 29.08.2004 20:20
Wohnort: Saarbrücken
Wunderbar erklärt. :allright:

Mehr wollte ich gar nicht wissen. Jetzt verstehen es sicherlich auch noch ein paar andere Leute mehr. <)

Jetzt bin ich mir auch sicher, dass der Code sicher ist und ich damit meine Threads sichern kann. :lol:

_________________
Ubuntu Gnome 20.04 LTS x64, PureBasic 5.72 x64 (außerdem 4.41, 4.50, 4.61, 5.00, 5.10, 5.11, 5.21, 5.22, 5.30, 5.31, 5.40, 5.50, 5.60, 5.71b2)
"Die deutsche Rechtschreibung ist Freeware, du darfst sie kostenlos nutzen – Aber sie ist nicht Open Source, d. h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen."


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 20.04.2005 19:37 
Offline

Registriert: 27.11.2004 15:42
Ja, sehr geil! :allright:


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 21.04.2005 00:24 
Offline
Benutzeravatar

Registriert: 30.08.2004 13:36
Wohnort: Ruhrpott
Wäre es nicht eigentlich eine Möglichkeit, sowas direkt im PB-Code (Compiler) von Fred einbauen zu lassen?
Also so eine Art Compiler-Directive, die dann alle kritischen String-Befehle automatisch in solche Critical Sections packt?
Sicherlich wären separate Stringpointer für jeden Thread die bessere Lösung, da man dann nur noch die globalen Variablen betrachten müsste, aber sowas wäre ja zumindest ein Lösung, die funktionieren sollte.

Es ist ja leider so, dass nicht für jeden unbedingt immer klar ist, was alles unter die Rubrik "threadunsicher" fällt (z.B. ja auch viele Gadget-Befehle).

Ich habe das String-Problem mit der SS_ThreadSync Lib (Skunksoft ThreadSync Lib) gelöst, aber hier (wie bei allen manuellen Lösungen), gibt es das Problem, dass eine einzige "vergessene" Absicherung dazu führen kann, dass das Programm nach x Durchläufen dann doch irgendwo Probleme macht, die man bei grossen Codes dann nur sehr schwer findet, da sie kaum reproduzierbar sind.
So z.B. bei einem Programm von mir, dass 10 bis 20 Tage auf einem Server problemlos durchläuft, dann aber gelegentlich hängen bleibt. Liegt das nun am Threadproblem oder an was anderem? Bei knapp 9000 Zeilen Code mit zig Routinen, von denen die meisten Stringbefehle enthalten, sucht man sich da 'nen Wolf ...

Was haltet ihr davon, Fred so eine Critical Section Lösung im Compiler für das Threadproblem des Stringpointers vorzuschlagen?

Gruß,
Martin

PS: Mir ist klar, dass man bei globalen Variablen auch bei separaten Stringpointern noch Vorkehrungen treffen müsste, dass 2 Threads nicht gleichzeitig an der gleichen Variabeln arbeiten - aber darum geht es mir hier erstmal nicht, sondern darum, dass in pb keine Stringbefehle parallel in Threads laufen dürfen - auch nicht, wenn in den Threads verschiedene Strings bearbeitet werden...


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 21.04.2005 13:26 
Offline

Registriert: 29.08.2004 18:39
Wohnort: Bayern
Hi,

...funktioniert aber nur mit eingeschaltetem Debugger??
ansonsten bekomme ich den Fehler
Code:
CALL _Sleep@4 error undefined Symbol


cu
Ulf


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags:
BeitragVerfasst: 21.04.2005 13:37 
Offline
Benutzeravatar

Registriert: 29.08.2004 08:48
walker hat geschrieben:
Hi,

...funktioniert aber nur mit eingeschaltetem Debugger??
ansonsten bekomme ich den Fehler
Code:
CALL _Sleep@4 error undefined Symbol


cu
Ulf

logisch, da Sleep nich definiert wurde.
füge am anfang ein

Code:
!EXTRN _Sleep@4


ein und es funktioniert (man muss dann nur per TaskManager den Process abschiessen)

_________________
Rings hat geschrieben:
ziert sich nich beim zitieren


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 17 Beiträge ]  Gehe zu Seite 1, 2  Nächste

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 9 Gäste


Sie dürfen keine neuen Themen in diesem Forum erstellen.
Sie dürfen keine Antworten zu Themen in diesem Forum erstellen.
Sie dürfen Ihre Beiträge in diesem Forum nicht ändern.
Sie dürfen Ihre Beiträge in diesem Forum nicht löschen.

Suche nach:
Gehe zu:  

 


Powered by phpBB © 2008 phpBB Group | Deutsche Übersetzung durch phpBB.de
subSilver+ theme by Canver Software, sponsor Sanal Modifiye