Moin, ich schaue gerade, wie ich am effizientesten Spinlocks auf dem AVR in C basteln kann. Compiler ist GCC. Naiver Ansatz: volatile char für das Lock. Sperren: while(1) { \ cli(); \ if(!_lock) { \ _lock = 1; \ sei(); \ break; \ } \ sei(); \ } Klassisches Busy-Waiting, atomizität von test-and-set wird sichergestellt durch deaktivieren aller Interrupts. Ansatz mit Compiler-Support: while(__atomic_test_and_set(&_lock, __ATOMIC_SEQ_CST)) ; So jetzt zum erzeugten Code: while(__atomic_test_and_set(&_lock, __ATOMIC_SEQ_CST)); 1048: 91 e0 ldi r25, 0x01 ; 1 104a: 80 91 ff 00 lds r24, 0x00FF 104e: 90 93 ff 00 sts 0x00FF, r25 1052: 81 11 cpse r24, r1 1054: fa cf rjmp .-12 ; 0x104a <ecs_init+0x2> Ich dachte zuerst, dass die Atomizität hier in der cpse-Instruktion liegt, aber lds/sts ist ja gar nicht atomar. Wieso ist das hier atomar, oder ist es das gar nicht? Und der naive Ansatz, der offensichtlich Atomar ist: 1056: f8 94 cli 1058: 80 91 ff 00 lds r24, 0x00FF 105c: 81 11 cpse r24, r1 105e: 07 c0 rjmp .+14 ; 0x106e <ecs_init+0x26> 1060: 81 e0 ldi r24, 0x01 ; 1 1062: 80 93 ff 00 sts 0x00FF, r24 1066: 78 94 sei ... 106e: 78 94 sei 1070: f2 cf rjmp .-28 ; 0x1056 <ecs_init+0xe>
Marian B. schrieb: > 1048: 91 e0 ldi r25, 0x01 ; 1 > 104a: 80 91 ff 00 lds r24, 0x00FF > 104e: 90 93 ff 00 sts 0x00FF, r25 > 1052: 81 11 cpse r24, r1 > 1054: fa cf rjmp .-12 ; 0x104a <ecs_init+0x2> > > Ich dachte zuerst, dass die Atomizität hier in der cpse-Instruktion > liegt, aber lds/sts ist ja gar nicht atomar. > Wieso ist das hier atomar, oder ist es das gar nicht? Nein, das ist nicht atomar, sondern hochgefährlicher Sondermüll. Wie du korrekt erkannt hast, droht eine race condition für den Fall, das während der zwei Takte, die die lds-Instruktion dauert, ein Interrupt ausgelöst wird (insbesondere natürlich der für den Task-Scheduler). > Und der naive Ansatz, der offensichtlich Atomar ist: > 1056: f8 94 cli > 1058: 80 91 ff 00 lds r24, 0x00FF > 105c: 81 11 cpse r24, r1 > 105e: 07 c0 rjmp .+14 ; 0x106e <ecs_init+0x26> > 1060: 81 e0 ldi r24, 0x01 ; 1 > 1062: 80 93 ff 00 sts 0x00FF, r24 > 1066: 78 94 sei > > ... > > 106e: 78 94 sei > 1070: f2 cf rjmp .-28 ; 0x1056 <ecs_init+0xe> Ja, das ist atomar, allerdings auch ziemlich ineffizient. Optimal ist (bei den gegebenenen Randbedingungen einer höchst suboptimalen Programmiersprache): wait: ldi r25,1 cli lds r24,0x00ff sei sts 0x00ff,r25 cp r24,r25 breq wait Das ist atomar (wenn es für dich nicht so aussieht->siehe Details der "sei"-Referenz), pollt alle zehn Takte und sperrt die Interrupts dabei nur für die Hälfte der Zykluszeit, also fünf Takte.
Probiere es mal hiermit:
1 | #include <util/atomic.h> |
2 | |
3 | dann
|
4 | |
5 | ATOMIC_BLOCK(ATOMIC_RESTORESTATE) |
6 | {
|
7 | |
8 | }
|
erzeugt CLI/SEI und setzt eine memory barrier für den compiler.
c-hater schrieb: > cli > lds r24,0x00ff > sei Hä? Ein einzelner LDS-Befehl ist auf dem AVR immer atomar, da kannst Du Dir das CLI/SEI gleich sparen. Hier der relevante Teil aus dem UM: "The interrupt execution response for all the enabled AVR interrupts is four clock cycles minimum. After four clock cycles the Program Vector address for the actual interrupt handling routine is executed. During this four clock cycle period, the Program Counter is pushed onto the Stack. The vector is normally a jump to the interrupt routine, and this jump takes three clock cycles. If an interrupt occurs during execution of a multi-cycle instruction, this instruction is completed before the interrupt is served. If an interrupt occurs when the MCU is in sleep mode, the interrupt execution response time is increased by four clock cycles. This increase comes in addition to the start-up time from the selected sleep mode." Edit: Ok, jetzt habe ich etwas gelernt: eine Eigenart des AVR ist es, dass der erste Befehl nach dem SEI noch vor einem Interrupt ausgeführt wird. Damit ist die komplette LDS/STS-Sequenz Atomar. Allerdings spart man sich in dem Code nur einen Zyklus "INT-Sperrzeit" auf Kosten der Verständlichkeit.
:
Bearbeitet durch User
Marian B. schrieb: > ich schaue gerade, wie ich am effizientesten Spinlocks auf dem AVR in C > basteln kann. Compiler ist GCC. Erstmal ist der Compiler eher egal, der Prozessortyp auch. Dir geht es darum, daß zwei zueinander asynchrone Prozesse sich gegenseitig etwas übermmitteln können ohne danebenzuhauen, gelle? Dein "Schulbuch"-Ansatz ist atomares Test und Set. Sowas KANN man zu programmieren versuchen, MUSS es aber nicht. Ich mache das anders, nämlich so, daß keiner der zwei beteiligten Prozesse dem anderen in seine Variablen was schreiben muß. Stattdessen haben beide Prozesse jeweils eine Synchronisier-Variable, die beide lesen, aber nur der Eigentümer schreiben darf. Die dient zum Handshake. abstraktes Beispiel: // Variablen char synch_A; char synch_B; struct irgendwas C; // das ist die Übergabevariable void Prozess_A (..) { ... if (synch_A==synch_B) { C = meineResultate; ++synch_A; } ... } void Prozess_B (...) { ... if (synch_A != synch_B) { TuWasMitC(C); // Übergabevariable verarbeiten synch_B = synch_A; } .. } Auf diese Weise können beide Prozesse völlig sicher auf C (oder sonstwas anderes) zugreifen, OHNE sich gegenseitig in die Quere zu kommen - und das Verfahren ist einfach, billig und sicher. W.S.
W.S. schrieb: > Auf diese Weise können beide Prozesse völlig sicher auf C (oder sonstwas > anderes) zugreifen, OHNE sich gegenseitig in die Quere zu kommen - und > das Verfahren ist einfach, billig und sicher. Dein Verfahren nenn man übrigens Mutex mit Semaphore. http://de.wikipedia.org/wiki/Mutex#Semaphor_oder_Monitor OP wollte ein Spinlock realisieren. Dafür kann es auch anderen Gründe geben.
:
Bearbeitet durch User
c-hater schrieb: > wait: > ldi r25,1 > cli > lds r24,0x00ff > sei > sts 0x00ff,r25 > cp r24,r25 > breq wait > > Das ist atomar (wenn es für dich nicht so aussieht->siehe Details der > "sei"-Referenz), pollt alle zehn Takte und sperrt die Interrupts dabei > nur für die Hälfte der Zykluszeit, also fünf Takte. Das sieht mir nach einer eleganten Lösung aus. Danke! W.S.: Schaue ich mir mal an. Wird halt schwierig, wenn mehr als zwei Prozesse beteiligt sind.
:
Bearbeitet durch User
Marian B. schrieb: > Ansatz mit Compiler-Support: > while(__atomic_test_and_set(&_lock, __ATOMIC_SEQ_CST)) > ; > > So jetzt zum erzeugten Code: > while(__atomic_test_and_set(&_lock, __ATOMIC_SEQ_CST)); > 1048: 91 e0 ldi r25, 0x01 ; 1 > 104a: 80 91 ff 00 lds r24, 0x00FF > 104e: 90 93 ff 00 sts 0x00FF, r25 > 1052: 81 11 cpse r24, r1 > 1054: fa cf rjmp .-12 ; 0x104a <ecs_init+0x2> > > Ich dachte zuerst, dass die Atomizität hier in der cpse-Instruktion > liegt, aber lds/sts ist ja gar nicht atomar. > Wieso ist das hier atomar, oder ist es das gar nicht? Atomar ist lediglich das __atomic_test_and_set, nicht das while() -- wie auch? Die Funktion wiederum entspricht der GCC-Doku:
1 | This built-in function performs an atomic test-and-set operation on |
2 | the byte at *ptr. The byte is set to some implementation defined |
3 | nonzero “set” value (hier 1) and the return value is true if and |
4 | only if the previous contents were “set”. |
Allerdings ist die libatomic für AVR nicht unterstützt, du hast zufälligerweise eine Funktion erwischt, die ohne libatomic.a auskommt: für die meisten anderen __atomic wirst du einen Linkerfehler bekommen. Die Implementierung der libatomic ist auch nicht gerade effizient, selbst wenn die bei avr-gcc dabei wäre, würdest du sie wohl nicht benutzen wollen; es sei denn, jemand steckt noch etwas Entwicklungsarbeit in das __atomic-Zeugs für avr-gcc.
Könntest du kurz erläutern, wieso das test-and-set vom GCC hier deiner Meinung nach atomar arbeitet? (Die while Schleife ist bzw. sollte auch nicht atomar sein.)
Johann L. schrieb: > Atomar ist lediglich das __atomic_test_and_set Nein, ist es nicht. > Die Funktion wiederum entspricht der GCC-Doku: > This built-in function performs an atomic test-and-set operation on > the byte at *ptr. Nein, genau das tut sie eben nicht.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.