Scheduler

[The Man]

Hallo, hier soll es um die Erarbeitung gehen, wie auf einem AVR (hier ein Mega8) ein Scheduler implementiert werden kann. Im unteren ausklappbarem Code steht der Post, wie ich diesen Thread ursprünglich angefangen habe. Die eigentlichen Aktionen gehen erst bei Eintrag #6 los.

Vorraussetzung für diesen Thread ist, dass man Assembler versteht und weiß, was bei einem Interrupt im AVR vor sich geht.
Auch sollen hier nicht die Philosophien diverser Scheduler, Multitasksystem oder Betriebssysteme erörtert werden.
ich denke allerdings nicht, das eine Vorstellung davon, was ein Scheduler ist zwangsweise nötig ist. Im Sinne des induktiven Lernens also villeicht interessant. Es soll um ein How-To gehen, das ganz unten anfängt - weil das auch mein Startpunkt in Sachen Scheduler auf AVR ist ;-)
Es sei nur kurz gesagt, dass die Grundidee eines Schdulers ist folgende ist:

Es gibt ein Sammelsorium an Aufgaben/Funktionen. In bestimmten Zeitabständen wird ein so genannter Scheduler aufgerufen, oft in Form einer ISR. Dadurch wird natürlich ein gerade laufende Funktion unterbrochen. Der Scheduler in der ISR kann dann anhand "irgendwelcher" Informationen entscheiden, ob es villeicht sinnvoll ist, erstmal eine andere Funktion aufzurufen, bevor zur ersten zurückgeprungen wird.




Hallo da,

ich bin auf dem Weg zum ersten mal zu einem Scheduler zu greifen. Ich weiß wohl, dass das was ich erreichen will der Norm nach aus Scheduler und Dispatcher besteht.

Hintergrund:
Ich habe an der UART vom Mega8 eine GPS Antenne und will auf Basis eines Zielortes, des eigenen Standortes und dem Kurs über Grund eine Zielpeilung machen. Das geht auch schon und man kann sich vorstellen, dass die Aufgabe in Funktionen unterteilt ist "gathering_data()", "compute_lan_lon_diff();", "divide_y_by_x"();" usw...

Jetzt soll das Teil aber bald noch mehr können. Ich habe vor einen Interrupt auf Basis des Timer2 mit 20kHz laufen zu lassen, wo der Scheduler läuft und entscheidet, wenn etwas anderes anliegt, ob zuerst das erledigt werden sollte.

Problem:
Jetzt komm ich gedanklich nicht weiter, wie ich das tatsächlich umsetzte. Ich habe etwas Bauchschmerzen mit der Idee, aus der ISR heraus vom Scheduler/Dispatcher eine Funktion aufzurufen.
Wie bekomme ich es also hin, dass nach Ablauf der ISR nicht in eine der GPS Funktionen zurückgesprungen wird, sondern erstmal an eine andere Stelle?
Muss ich da am Stack für den Programmcounter rumspielen und die Adresse einer anderen Funktion "reinmogeln"?

viele Grüße,
The Man

[markusj]

Muss ich da am Stack für den Programmcounter rumspielen und die Adresse einer anderen Funktion "reinmogeln"?
Ja aber: Hast du es schon mit kooperativem Multitasking probiert? Das für viele Fälle aus und dürfte einfacher/weniger Fehleranfällig sein.

mfG
Markus

[The Man]

Danke für die Antwort!!

Ich habe mir eben den WIKI Beitrag über Koop. Multitasking durchgelesen. Ich habe den Eindruck, er ist etwas unglücklich formuliert. Nach dem wie ich es verstanden habe, gibt es dort auch einen Interrupt, aber jeder Prozess läuft auf jeden Fall erstmal zu Ende (wie Round Robin). Ich sehe da nicht so ganz den Sinn eines Interruptes. Dann könnte man während eines Prozesses den Interrupt auch sperren und den Sprung Overhead sparen.
http://webcache.googleusercontent.com/search?hl=de&gbv=2&rlz=1R2GGIE_de&gs_sm=e&gs_upl=756l756l0l3253l1l1l0l0l0l0l269l269l2-1l1l0&q=cache:znX5tv4D_rYJ:http://de.wikipedia.org/wiki/Multitasking+kooperativem+Multitasking&ct=clnk
Naja, jedenfalls ging es mir ja um die Frage, wie ich einem Prozess "die CPU entziehen" kann. Auf den AVR´s kann ich es mir nicht anders vorstellen, als nach der ISR den PC zu ändern.

[markusj]

Koop. Multitasking braucht eigentlich gar keinen Interrupt und kann auch in der Hauptschleife laufen. Und richtig, eine harte Unterbrechung kriegst du nur hin, wenn du die Rücksprungaddresse und den Stackpointer verbiegst. Außerdem musst du jedes Mal den kompletten Registersatz sichern bzw. wiederherstellen, du kriegst also einen schönen Overhead von über 30 Bytes die du für den Kontext brauchst. Je Thread.

mfG
Markus

[Hubert.G]

So ein Stack verbiegen und Register sichern, verbraucht einiges an Takte und RAM, von der Sicherheit ganz abgesehen.
Wäre es nicht besser in der ISR ein Flag zu setzen, dieses Flag im main und auch sonst an geeigneten Stellen abzufragen und bei bedarf in die gewünschte Funktion zu springen?

[The Man]

So,

ich mache mir weitere Gedanken und fange mal an, erste "Investigations" zu posten.
Vom Prinzip her wird das so laufen, dass in einer ISR, wahrscheinlich Timer2 Match oder Timer0 OVF, am Ende der ISR der Programmcounter verbogen werden muss zu der Adresse, wo eine aufzurufende Funktion steht.
Jetzt ist es in C ja so, das der Compiler einem das sichern vom Status- und den Workingregistern abnimmt. Die erste Frage die sich also stellt ist, wie man nach seinem C-Code dem Compiler vor dem vom ihm eingefügten Rücksprung aus dem Interrupt (reti) zuvokommt.

Ich habe zunächst ein ganz simples Programm auf Basis des Timer2 Comp Match Interruptes gemacht, wo einfach nur eine globale Variable um 1 erhöht wird. Damit wollte ich erstmal ein Gefühl kriegen, was der Compiler eigentlich "normalerweise" so treibt. Dazu dann erstmal der C Code und dann der ASM Code, den ich in der Datei im Projektpfad/default in der .Iss Datei gefunden habe. (ich weiß, diese Subtrktion von 255 und test auf 0 Flag bit im ASM code ist komisch - könnte an der stdint.h liegen - bitte dieses hier nicht zu kommentieren, weil es darum nicht gehen soll).



#include <avr/io.h>
#include <avr/interrupt.h>
#include <stdint.h>
uint8_t cnt = 0;
SIGNAL (TIMER2_COMP_vect)//TIMER1_COMPA_vect)
{
cnt++;
}
int main(void)
{
TCCR2 = 0b00001010;
OCR2 = 100;
TIMSK = 0b10000000;//input cp int enable, int on match A enable
main2:
goto main2;
return 0;
}

Daraus entstandener ASM Code:




schedule_try1.elf: file format elf32-avr
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 0000007c 00000000 00000000 00000074 2**1
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .bss 00000001 00800060 00800060 000000f0 2**0
ALLOC
2 .debug_aranges 00000020 00000000 00000000 000000f0 2**0
CONTENTS, READONLY, DEBUGGING
3 .debug_pubnames 00000032 00000000 00000000 00000110 2**0
CONTENTS, READONLY, DEBUGGING
4 .debug_info 000000b3 00000000 00000000 00000142 2**0
CONTENTS, READONLY, DEBUGGING
5 .debug_abbrev 00000081 00000000 00000000 000001f5 2**0
CONTENTS, READONLY, DEBUGGING
6 .debug_line 000000c5 00000000 00000000 00000276 2**0
CONTENTS, READONLY, DEBUGGING
7 .debug_frame 00000030 00000000 00000000 0000033c 2**2
CONTENTS, READONLY, DEBUGGING
8 .debug_str 0000009f 00000000 00000000 0000036c 2**0
CONTENTS, READONLY, DEBUGGING
Disassembly of section .text:
00000000 <__vectors>:
0: 12 c0 rjmp .+36 ; 0x26 <__ctors_end>
2: 21 c0 rjmp .+66 ; 0x46 <__bad_interrupt>
4: 20 c0 rjmp .+64 ; 0x46 <__bad_interrupt>
6: 20 c0 rjmp .+64 ; 0x48 <__vector_3>
8: 1e c0 rjmp .+60 ; 0x46 <__bad_interrupt>
a: 1d c0 rjmp .+58 ; 0x46 <__bad_interrupt>
c: 1c c0 rjmp .+56 ; 0x46 <__bad_interrupt>
e: 1b c0 rjmp .+54 ; 0x46 <__bad_interrupt>
10: 1a c0 rjmp .+52 ; 0x46 <__bad_interrupt>
12: 19 c0 rjmp .+50 ; 0x46 <__bad_interrupt>
14: 18 c0 rjmp .+48 ; 0x46 <__bad_interrupt>
16: 17 c0 rjmp .+46 ; 0x46 <__bad_interrupt>
18: 16 c0 rjmp .+44 ; 0x46 <__bad_interrupt>
1a: 15 c0 rjmp .+42 ; 0x46 <__bad_interrupt>
1c: 14 c0 rjmp .+40 ; 0x46 <__bad_interrupt>
1e: 13 c0 rjmp .+38 ; 0x46 <__bad_interrupt>
20: 12 c0 rjmp .+36 ; 0x46 <__bad_interrupt>
22: 11 c0 rjmp .+34 ; 0x46 <__bad_interrupt>
24: 10 c0 rjmp .+32 ; 0x46 <__bad_interrupt>
00000026 <__ctors_end>:
26: 11 24 eor r1, r1
28: 1f be out 0x3f, r1 ; 63
2a: cf e5 ldi r28, 0x5F ; 95
2c: d4 e0 ldi r29, 0x04 ; 4
2e: de bf out 0x3e, r29 ; 62
30: cd bf out 0x3d, r28 ; 61
00000032 <__do_clear_bss>:
32: 10 e0 ldi r17, 0x00 ; 0
34: a0 e6 ldi r26, 0x60 ; 96
36: b0 e0 ldi r27, 0x00 ; 0
38: 01 c0 rjmp .+2 ; 0x3c <.do_clear_bss_start>
0000003a <.do_clear_bss_loop>:
3a: 1d 92 st X+, r1
0000003c <.do_clear_bss_start>:
3c: a1 36 cpi r26, 0x61 ; 97
3e: b1 07 cpc r27, r17
40: e1 f7 brne .-8 ; 0x3a <.do_clear_bss_loop>
42: 13 d0 rcall .+38 ; 0x6a <main>
44: 19 c0 rjmp .+50 ; 0x78 <_exit>
00000046 <__bad_interrupt>:
46: dc cf rjmp .-72 ; 0x0 <__vectors>
00000048 <__vector_3>:
#include <stdint.h>
uint8_t cnt = 0;
SIGNAL (TIMER2_COMP_vect)//TIMER1_COMPA_vect)
{
48: 1f 92 push r1
4a: 0f 92 push r0
4c: 0f b6 in r0, 0x3f ; 63
4e: 0f 92 push r0
50: 11 24 eor r1, r1
52: 8f 93 push r24
cnt++;
54: 80 91 60 00 lds r24, 0x0060
58: 8f 5f subi r24, 0xFF ; 255
5a: 80 93 60 00 sts 0x0060, r24
}
5e: 8f 91 pop r24
60: 0f 90 pop r0
62: 0f be out 0x3f, r0 ; 63
64: 0f 90 pop r0
66: 1f 90 pop r1
68: 18 95 reti
0000006a <main>:
int main(void)
{
TCCR2 = 0b00001010;
6a: 8a e0 ldi r24, 0x0A ; 10
6c: 85 bd out 0x25, r24 ; 37
OCR2 = 100;
6e: 84 e6 ldi r24, 0x64 ; 100
70: 83 bd out 0x23, r24 ; 35
TIMSK = 0b10000000;//input cp int enable, int on match A enable
72: 80 e8 ldi r24, 0x80 ; 128
74: 89 bf out 0x39, r24 ; 57
76: ff cf rjmp .-2 ; 0x76 <main+0xc>
00000078 <_exit>:
78: f8 94 cli
0000007a <__stop_program>:
7a: ff cf rjmp .-2 ; 0x7a <__stop_program>




Mit der Anweisung "asm volatile("ret");" am ende der ISR wird der Assemblerbefehl ret vor das Restaurieren und das reti gequetscht.
Warum ich hier jetzt "ret" und nicht reti verwende, dazu an anderer Stelle mehr. Hier gehts erstmal nur um Machbarkeiten.



#include <avr/io.h>
#include <avr/interrupt.h>
#include <stdint.h>
uint8_t cnt = 0;
SIGNAL (TIMER2_COMP_vect)//TIMER1_COMPA_vect)
{
cnt++;
asm volatile("ret");
}
int main(void)
{
TCCR2 = 0b00001010;
OCR2 = 100;
TIMSK = 0b10000000;//input cp int enable, int on match A enable
main2:
goto main2;
return 0;
}


ASM Code




schedule_try2.elf: file format elf32-avr
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 0000007e 00000000 00000000 00000074 2**1
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .bss 00000001 00800060 00800060 000000f2 2**0
ALLOC
2 .debug_aranges 00000020 00000000 00000000 000000f2 2**0
CONTENTS, READONLY, DEBUGGING
3 .debug_pubnames 00000032 00000000 00000000 00000112 2**0
CONTENTS, READONLY, DEBUGGING
4 .debug_info 000000b3 00000000 00000000 00000144 2**0
CONTENTS, READONLY, DEBUGGING
5 .debug_abbrev 00000081 00000000 00000000 000001f7 2**0
CONTENTS, READONLY, DEBUGGING
6 .debug_line 000000cd 00000000 00000000 00000278 2**0
CONTENTS, READONLY, DEBUGGING
7 .debug_frame 00000030 00000000 00000000 00000348 2**2
CONTENTS, READONLY, DEBUGGING
8 .debug_str 0000009f 00000000 00000000 00000378 2**0
CONTENTS, READONLY, DEBUGGING
Disassembly of section .text:
00000000 <__vectors>:
0: 12 c0 rjmp .+36 ; 0x26 <__ctors_end>
2: 21 c0 rjmp .+66 ; 0x46 <__bad_interrupt>
4: 20 c0 rjmp .+64 ; 0x46 <__bad_interrupt>
6: 20 c0 rjmp .+64 ; 0x48 <__vector_3>
8: 1e c0 rjmp .+60 ; 0x46 <__bad_interrupt>
a: 1d c0 rjmp .+58 ; 0x46 <__bad_interrupt>
c: 1c c0 rjmp .+56 ; 0x46 <__bad_interrupt>
e: 1b c0 rjmp .+54 ; 0x46 <__bad_interrupt>
10: 1a c0 rjmp .+52 ; 0x46 <__bad_interrupt>
12: 19 c0 rjmp .+50 ; 0x46 <__bad_interrupt>
14: 18 c0 rjmp .+48 ; 0x46 <__bad_interrupt>
16: 17 c0 rjmp .+46 ; 0x46 <__bad_interrupt>
18: 16 c0 rjmp .+44 ; 0x46 <__bad_interrupt>
1a: 15 c0 rjmp .+42 ; 0x46 <__bad_interrupt>
1c: 14 c0 rjmp .+40 ; 0x46 <__bad_interrupt>
1e: 13 c0 rjmp .+38 ; 0x46 <__bad_interrupt>
20: 12 c0 rjmp .+36 ; 0x46 <__bad_interrupt>
22: 11 c0 rjmp .+34 ; 0x46 <__bad_interrupt>
24: 10 c0 rjmp .+32 ; 0x46 <__bad_interrupt>
00000026 <__ctors_end>:
26: 11 24 eor r1, r1
28: 1f be out 0x3f, r1 ; 63
2a: cf e5 ldi r28, 0x5F ; 95
2c: d4 e0 ldi r29, 0x04 ; 4
2e: de bf out 0x3e, r29 ; 62
30: cd bf out 0x3d, r28 ; 61
00000032 <__do_clear_bss>:
32: 10 e0 ldi r17, 0x00 ; 0
34: a0 e6 ldi r26, 0x60 ; 96
36: b0 e0 ldi r27, 0x00 ; 0
38: 01 c0 rjmp .+2 ; 0x3c <.do_clear_bss_start>
0000003a <.do_clear_bss_loop>:
3a: 1d 92 st X+, r1
0000003c <.do_clear_bss_start>:
3c: a1 36 cpi r26, 0x61 ; 97
3e: b1 07 cpc r27, r17
40: e1 f7 brne .-8 ; 0x3a <.do_clear_bss_loop>
42: 14 d0 rcall .+40 ; 0x6c <main>
44: 1a c0 rjmp .+52 ; 0x7a <_exit>
00000046 <__bad_interrupt>:
46: dc cf rjmp .-72 ; 0x0 <__vectors>
00000048 <__vector_3>:
#include <stdint.h>
uint8_t cnt = 0;
SIGNAL (TIMER2_COMP_vect)//TIMER1_COMPA_vect)
{
48: 1f 92 push r1
4a: 0f 92 push r0
4c: 0f b6 in r0, 0x3f ; 63
4e: 0f 92 push r0
50: 11 24 eor r1, r1
52: 8f 93 push r24
cnt++;
54: 80 91 60 00 lds r24, 0x0060
58: 8f 5f subi r24, 0xFF ; 255
5a: 80 93 60 00 sts 0x0060, r24
asm volatile("ret");
5e: 08 95 ret
}
60: 8f 91 pop r24
62: 0f 90 pop r0
64: 0f be out 0x3f, r0 ; 63
66: 0f 90 pop r0
68: 1f 90 pop r1
6a: 18 95 reti
0000006c <main>:
int main(void)
{
TCCR2 = 0b00001010;
6c: 8a e0 ldi r24, 0x0A ; 10
6e: 85 bd out 0x25, r24 ; 37
OCR2 = 100;
70: 84 e6 ldi r24, 0x64 ; 100
72: 83 bd out 0x23, r24 ; 35
TIMSK = 0b10000000;//input cp int enable, int on match A enable
74: 80 e8 ldi r24, 0x80 ; 128
76: 89 bf out 0x39, r24 ; 57
78: ff cf rjmp .-2 ; 0x78 <main+0xc>
0000007a <_exit>:
7a: f8 94 cli
0000007c <__stop_program>:
7c: ff cf rjmp .-2 ; 0x7c <__stop_program>


Man kann im ASM code also deutlich sehen, wo sich das händisch eingefügte "ret" auswirkt. So würde er also aus der ISR abhauen, ohne das global Interrupt enable Bit wieder zu setzten und die register zu restaurieren.

to be continued...

[Hubert.G]

Wie oft denkst du, kannst du das machen bevor der Stack überläuft.
Hast du dir meinen Vorschlag schon mal überlegt? Das ist die gängigste und sicherste Methode.

[sternst]

Sorry, auch wenn das jetzt ein wenig hart klingen mag, aber dein ganzer Ansatz (einfach mal in der ISR die Rücksprungadresse zu ändern) ist totaler Murks. Es ist völlig illusorisch zu denken, auf die Art ein Multitasking einfach realisieren zu können. Das führt unweigerlich zu Chaos und Absturz. Wenn du preemptives Multitasking haben willst, dann führt absolut kein Weg an einem kompletten Kontext-Wechsel vorbei.

Deine eigentliche erste Aufgabe ist es also nicht, zu überlegen "wie komme ich am Ende der ISR zu einer anderen Funktion" (das ist total irrelevant, denn das passiert beim echten Kontext-Wechsel ganz von alleine), sondern zu überlegen "was gehört eigentlich alles zum Kontext".