Critical Sections selbst erstellen :) [3 Methoden]

Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
Benutzeravatar
PureFan
Beiträge: 19
Registriert: 10.09.2004 14:40
Kontaktdaten:

Critical Sections selbst erstellen :) [3 Methoden]

Beitrag von PureFan »

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: Alles auswählen


;-
;- 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
Zuletzt geändert von PureFan am 14.05.2005 14:29, insgesamt 3-mal geändert.
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
Benutzeravatar
Rings
Beiträge: 971
Registriert: 29.08.2004 08:48

Beitrag von Rings »

genial !!!

Einfach zu verstehen, einfach einzubauen.
Rings hat geschrieben:ziert sich nich beim zitieren
DarkDragon
Beiträge: 6267
Registriert: 29.08.2004 08:37
Computerausstattung: Hoffentlich bald keine mehr
Kontaktdaten:

Beitrag von DarkDragon »

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.
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Beitrag von NicTheQuick »

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.
Bild
Benutzeravatar
PureFan
Beiträge: 19
Registriert: 10.09.2004 14:40
Kontaktdaten:

Beitrag von PureFan »

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:
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!
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
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Beitrag von NicTheQuick »

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:
Bild
traumatic
Beiträge: 478
Registriert: 27.11.2004 15:42

Beitrag von traumatic »

Ja, sehr geil! :allright:
Benutzeravatar
deMattin
Beiträge: 87
Registriert: 30.08.2004 13:36
Wohnort: Ruhrpott
Kontaktdaten:

Beitrag von deMattin »

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...
walker
Beiträge: 278
Registriert: 29.08.2004 18:39
Wohnort: Bayern

Beitrag von walker »

Hi,

...funktioniert aber nur mit eingeschaltetem Debugger??
ansonsten bekomme ich den Fehler

Code: Alles auswählen

CALL _Sleep@4 error undefined Symbol
cu
Ulf
Benutzeravatar
Rings
Beiträge: 971
Registriert: 29.08.2004 08:48

Beitrag von Rings »

walker hat geschrieben:Hi,

...funktioniert aber nur mit eingeschaltetem Debugger??
ansonsten bekomme ich den Fehler

Code: Alles auswählen

CALL _Sleep@4 error undefined Symbol
cu
Ulf
logisch, da Sleep nich definiert wurde.
füge am anfang ein

Code: Alles auswählen

!EXTRN _Sleep@4
ein und es funktioniert (man muss dann nur per TaskManager den Process abschiessen)
Rings hat geschrieben:ziert sich nich beim zitieren
Antworten