SCALETTA LEZIONE SERT E13 -- 10 gennaio 2013 **** Scheduler con job interrompibili **** 6 Implementazione di stack separati per ogni task 6.1 Modificare tasks.c per allocare gli stack nella sezione .bss +------------------------------------------------------------+ |#define STACK_SIZE 4096 | |char stacks[MAX_NUM_TASKS*STACK_SIZE] | | __attribute__ ((aligned (STACK_SIZE))); | |const char *stack0_top = stacks + MAX_NUM_TASKS*STACK_SIZE; | +------------------------------------------------------------+ 6.2 Modificare startup.S per caricare lo stack del task 0 +------------------------+ |[...] | |ldr sp,=stack0_top | |ldr sp,[sp] | |b _init | +------------------------+ 6.3 Rimuovere la definizione dello stack da sert.lds 6.4 Definire la variabile current che punta al descrittore di task in esecuzione: +------------------------------------------------------------+ |struct task *current; (in sched.c) | |extern struct task *current (in comm.h) | |current=&taskset[0]; (in tasks.c, init_taskset())| +------------------------------------------------------------+ 6.5 Il task 0 non e' un vero task periodico: e' l'"idle" task che lo scheduler seleziona quando non esistono altri job eseguibili nel sistema 6.5.1 Si puo' considerare il task 0 come in esecuzione durante l'inizializzazione 2 Implementazione del cambio di contesto 2.1 Definizione del cambio di contesto: 2.1.1 Registri AACS-clobbered r0-r3,r12,r14/lr: salvati dal gestore di interruzione sullo stack attivo al momento della interruzione 2.1.2 Registri non AACS-clobbered r4-r11, r13/sp: da salvare nel descrittore di task 2.1.3 Tecnicamente il cambio di contesto si considera effettuato quando si modifica il valore di r13/sp per indirizzare lo stack del task che deve (ri)cominciare ad essere eseguito 2.2 Aggiungere al descrittore di task in comm.h i campi per il salvataggio del contesto d'esecuzione +-----------------------------+ |struct task { | |[...] | | const char *name; | | unsigned long sp; | | unsigned long regs[8]; | |}; | +-----------------------------+ 2.3 Scrivere la funzione "naked" _switch_to() in sched.c: +-------------------------------------------------------+ |#include "ts7250.h" | |[...] | |void _switch_to(struct task *) __attribute__((naked)); | | | |void _switch_to(struct task *to) | |{ | | irq_disable(); | | save_regs(current->regs); | | load_regs(to->regs); | | switch_stacks(current, to); | | current = to; | | irq_enable(); | | naked_return(); | |} | +-------------------------------------------------------+ 2.3.1 L'attributo "naked" (specifico per l'architettura ARM) forza il compilatore a non generare alcun codice per l'invocazione e terminazione della funzione 2.3.2 Le macro irq_disable() e irq_enable() sono state gia' definite in ts7250.h 2.3.3 Scrivere la macro save_regs: +------------------------------------------------------+ |#define save_regs(regs) \ | | __asm__ __volatile__("stmia %0,{r4-r11}" \ | | : : "r" (regs) : "memory"); | +------------------------------------------------------+ 2.3.4 Scrivere la macro load_regs: +------------------------------------------------------+ |#define load_regs(regs) \ | | __asm__ __volatile__("ldmia %0,{r4-r11}" \ | | : : "r" (regs) : "r4", "r5", "r6", "r7", "r8", \ | | "r9", "r10", "r11", "memory"); | +------------------------------------------------------+ 2.3.5 Scrivere la macro switch_task: +------------------------------------------------------+ |#define switch_task(from, to) \ | | __asm__ __volatile__("str sp,%0\n\t" \ | | "ldr sp,%1\n\t" \ | | : : "m" ((from)->sp), "m" ((to)->sp) \ | | : "sp", "memory"); | +------------------------------------------------------+ 2.3.6 Scrivere la macro naked_return(): +------------------------------------------------------+ |#define naked_return() __asm__ __volatile__("bx lr"); | +------------------------------------------------------+ 2.4 Controllare il codice prodotto per _switch_to tramite il disassemblatore del cross-compiler (arm*objdump) 3 Inizializzazione del contesto d'esecuzione di un nuovo task 3.1 Consiste nel: 3.1.1 determinare lo stack per il task 3.1.2 inizializzare lo stack per il task 3.1.3 definire il punto d'inizio del programma del task 3.1.4 inizializzare il contesto salvato nel descrittore 3.2 Lo stack viene inizializzato in modo da essere analogo allo stack di un task che e' stato interrotto da una interruzione: +---+---+---+---+---+---+---+----+ STK |r0 |r1 |r2 |r3 |r12|r14|RET|spsr| +---+---+---+---+---+---+---+----+ N +4 +8 +12 +16 +20 +24 +28 3.4 Scrivere la funzione task_entry_point() in tasks.c +------------------------------------------------------------+ |void init_task_context(struct task *t, int ntask) | |{ | | unsigned long *sp; | | int i; | | | | sp = (unsigned long *)(stack0_top - ntask*STACK_SIZE); | | | | *(--sp) = 0UL; | | *(--sp) = (unsigned long) task_entry_point; | | *(--sp) = 0UL; | | *(--sp) = 0UL; | | *(--sp) = 0UL; | | *(--sp) = 0UL; | | *(--sp) = 0UL; | | *(--sp) = (unsigned long) t; | | t->sp = (unsigned long) sp; | | for (i=0; i<8; ++i) | | t->regs[i] = 0UL; | |} | +------------------------------------------------------------+ 3.5 I valori corrispondenti all'indirizzo di ritorno (RET) ed al registro r0 corrispondono all'esecuzione della funzione task_entry_point() con argomento l'indirizzo del descrittore del task stesso 4 Definizione del punto d'ingresso del codice di un task 4.1 Scrivere in tasks.c la funzione "naked" task_entry_point() +-------------------------------------------------------------+ |void task_entry_point(struct task *) __attribute__((naked)); | |void task_entry_point(struct task *t) | |{ | | for (;;) { | | if (t->valid == 0 || t->released == 0) | | _panic(); | | irq_enable(); | | t->job(t->arg); | | irq_disable(); | | --t->released; | | _sys_schedule(); | | } | |} | +-------------------------------------------------------------+ 4.2 La funzione esegue un ciclo senza fine: vi sara' una iterazione del ciclo per ciascun rilascio di un job del task 4.3 Il job viene eseguito con le interruzioni abilitate, ma nel resto della funzione le interruzioni sono disabilitate 4.4 Quando un job termina il campo t->released viene decrementato: questo campo conserva il medesimo significato che aveva con lo scheduler per job non interrompibili: indica il numero di job rilasciati e non ancora completati del task 4.5 La funzione _sys_schedule(), invocata in SYSTEM mode, permette di selezionare un nuovo task da eseguire quando un job del task termina 5 Modificare la funzione create_task() 5.1 Cominciare il ciclo per la ricerca di un descrittore libero saltando la posizione 0 (riservata all' "idle" task) +---------------------------------+ | for (i=1; i MAX_NUM_TASKS) | | _panic(); /* Should never happen */ | | if (!f->valid) | | continue; | | if (time_after_eq(now, f->releasetime)) { | | ++f->released; | | f->releasetime += f->period; | | trigger_schedule = 1; | | ++globalreleases; | | } | | ++i; | | } | |} | +------------------------------------------------------------+ 6.1 Cambiare il nome da schedule() a check_periodic_tasks() (meno ambiguo) 6.1.1 In comm.h modificare l'istruzione extern corrispondente 6.1.2 In isr_tick() [tick.c] modificare l'invocazione della funzione 6.2 Saltare il task 0: l'idle task non e' periodico 6.3 Aggiungere un flag global "trigger_schedule", necessario per forzare l'invocazione in modalita' SYSTEM della funzione dello scheduler 7 Utilizzando come base la funzione run_periodic_tasks(), scrivere in sched.c la funzione select_best_task() che seleziona il task periodico con job rilasciati di priorita' massima, ovvero il task 0 (idle task) se nessun task periodico e' eseguibile +----------------------------------------------------------------------+ |static inline struct task *select_best_task(void) | |{ | | int maxprio, i; | | struct task *best, *f; | | | | maxprio = MININT; | | best = &taskset[0]; | | for (i=0, f=taskset+1; i MAX_NUM_TASKS) | | _panic(); | | if (!f->valid) | | continue; | | ++i; | | if (f->released > 0 && f->priority > maxprio) { | | maxprio = f->priority; | | best = f; | | } | | } | | return best; | |} | +----------------------------------------------------------------------+ 7.1 Questa funzione e' eseguita con interruzioni abilitate, percio' esiste una "race condition" con check_periodic_tasks() sui campi f->relesed dei task: del problema si occupa la funzione invocante select_best_task 7.2 Notare che la ricerca del task periodico inizia dal task con TID=1, mentre il task 0 e' selezionato solo se nessun altro task e' eseguibile 8 Scrivere la prima versione della funzione schedule() per valutare se e' necessario selezionare un nuovo task da porre in esecuzione +----------------------------------------------+ |struct task *schedule(void) | |{ | | struct task *best; | | unsigned long oldreleases; | | do { | | oldreleases = globalreleases; | | best = select_best_task(); | | } while (oldreleases != globalreleases); | | trigger_schedule = 0; | | best = (best != current ? best : NULL); | | return best; | |} | +----------------------------------------------+ 8.1 La funzione fa uso di select_best_task() per selezionare il vincitore 8.2 La funzione restituisce l'indirizzo del descrittore del task vincitore, a meno che il task vincitore non sia gia' in esecuzione, nel qual caso la funzione restituisce NULL 8.3 La funzione e' invocata in modalita' SYSTEM 8.4 Il meccanismo per invocare schedule() in modo asincrono consiste nell'impostare il valore 1 in trigger_schedule (funzione check_periodic_tasks()) 8.5 Aggiungere la definizione extern per schedule() in comm.h 9 Modificare il gestore di interruzioni a basso livello _irq_handler() per invocare, se necessario, le funzioni schedule() e _switch_to() 9.1 Inseriamo la modifica nel percorso di "uscita" dall'interruzione, esattamente dopo le istruzioni eseguite in modalita' IRQ che ripristinano il contenuto del registro spsr: msr cpsr_c,#(IRQ_MODE|NO_INT) mov sp,r0 ldr r0,[sp,#(7*4)] msr spsr_cxsf,r0 9.2 Poiche' intendiamo eseguire schedule() ed il cambio di contesto in modalita' SYSTEM, controlliamo se il processore sta per rientrare in modalita' SYSTEM (e' possibile infatti che si stiano gestendo una o piu' interruzioni annidate): +--------------------------------+ | and r0,r0,#SYS_MODE | | teq r0,#SYS_MODE | | bne .Lnosched | |[...] | |.Lnosched: | | ldmfd sp,{r0-r3,r12,lr}^ | |[...] | +--------------------------------+ 9.3 Non e' necessario invocare schedule() a meno che la variabile globale trigger_schedule sia diversa da zero: +------------------------------+ |ldr r0,=trigger_schedule | |ldr r0,[r0] | |tst r0,r0 | |beq .Lnosched | +------------------------------+ 9.4 E' necessario finire la gestione dell'interruzione eseguendo schedule() invece del programma SYSTEM originariamente interrotto: +------------------------------+ |ldr lr,=_irq_schedule | |movs pc,lr | +------------------------------+ 9.5 All'inizio di _irq_schedule() la situazione di registri e stack e' la seguente: +---+---+---+---+---+---+---+---+---+---+---+---+---+----+---+---+----+----+ | | | | | | | | | | | | | | sp | lr| pc| | | |r0 |r1 |r2 |r3 |r4 |r5 |r6 |r7 |r8 |r9 |r10|r11|r12|r13 |r14|r15|cpsr|spsr| +---+---+---+---+---+---+---+---+---+---+---+---+---+----+---+---+----+----+ *SY| | | | | | | | | | | | | | N | * | | |////| | ? | ? | ? | ? | E | F | G | H | I | J | K | L | ? |----|---| * | ? |----| IR| | | | | | | | | | | | | | ? | ? | | | ? | +---+---+---+---+---+---+---+---+---+---+---+---+---+----+---+---+----+----+ STK| A | B | C | D | M | O |P+4| Q | X | Y | Z | +---+---+---+---+---+---+---+---+---+---+---+ N-32 +4 +8 +12 +16 +20 +24 +28 +32 +36 +40 9.6 Sullo stack si trova ancora il contenuto di tutti i registri che devono essere ripristinati: sottrarre 32 al valore del registro r13/sp relativo alla modalita' SYSTEM in modo da preservare questi valori durante l'esecuzione di schedule() ed, eventualmente, il cambio di contesto: +------------------------------+ |_irq_schedule: | |sub sp,sp,#32 | +------------------------------+ 9.7 Invocare la funzione schedule(): +------------------------------+ |ldr r12,=schedule | |mov lr,pc | |bx r12 | +------------------------------+ 9.7.1 Il valore restituito da schedule() e' nel registro r0 9.8 Controllare il valore restituito da schedule(): se e' NULL non occorre effettuare un cambio di contesto, quindi si riprende con il task che era in esecuzione al momento della interruzione +------------------------------+ |tst r0,r0 | |beq .Lnoswitch | +------------------------------+ 9.9 E' necessario cambiare il contesto di esecuzione: invocare la funzione _switch_to(), passando come parametro nel registro r0 il valore restituito da schedule() +------------------------------+ |ldr r12,=_switch_to | |mov lr,pc | |bx r12 | +------------------------------+ 9.9.1 Al termine della funzione _switch_to() lo stack e' stato cambiato: il registro r13/sp punta alla cima dello stack del task che deve essere posto in esecuzione 9.10 A questo punto l'esecuzione prosegue in comune con il caso in cui il cambio di contesto non era necessario: si recupera il valore dei registri dallo stack e si ricomincia l'esecuzione del task interrotto +------------------------------+ |.Lnoswitch: | |ldr r0,[sp,#(7*4)] | |msr cpsr_f,r0 | |ldmfd sp!,{r0-r3,r12,lr} | +------------------------------+ 9.10.1 Il registro cpsr non viene modificato dalle istruzioni seguenti 9.11 La situazione di stack e registri ora e' la seguente: +---+---+---+---+---+---+---+---+---+---+---+---+---+----+---+---+----+----+ | | | | | | | | | | | | | | sp | lr| pc| | | |r0 |r1 |r2 |r3 |r4 |r5 |r6 |r7 |r8 |r9 |r10|r11|r12|r13 |r14|r15|cpsr|spsr| +---+---+---+---+---+---+---+---+---+---+---+---+---+----+---+---+----+----+ *SY| | | | | | | | | | | | | |N-8 | O | | Q |////| | A | B | C | D | E | F | G | H | I | J | K | L | M |----|---| * |----|----| IR| | | | | | | | | | | | | | ? | ? | | ? | ? | +---+---+---+---+---+---+---+---+---+---+---+---+---+----+---+---+----+----+ STK|P+4| Q | X | Y | Z | +---+---+---+---+---+ N-8 +4 +8 +12 +16 9.12 E' necessario compiere due operazioni: 9.12.1 Saltare all'indirizzo P+4 contenuto sullo stack 9.12.2 Bilanciare lo stack, ossia aggiungere 8 al registro r13/sp 9.12.3 Evitare la modifica di altri registri tranne r13/sp e r15/pc 9.12.4 Cio' si ottiene con una singola istruzione macchina: +------------------------------+ |ldr pc,[sp],#(4*2) | +------------------------------+ 9.13.4.1 L'incremento del registro r13/sp avviene dopo che il suo valore e' stato utlizzato per caricare nel registro r15/pc 10 Scrivere la funzione _sys_schedule(), che invoca lo scheduler quando un job termina 10.1 La funzione e' sempre invocata in modalita' SYSTEM, quindi lo stack non contiene valori salvati dal gestore delle interruzioni 10.1.1 E' necessario salvare i valori dei registri AACS-clobbered sullo stack, ma senza avere a disposizione i registri della modalita' IRQ 10.2 Salvare il valore di ritorno contenuto nel registro r14/lr sullo stack (punta all'interno del ciclo in task_entry_point()) +------------------------------+ |str lr,[sp,#-(4*2)]! | +------------------------------+ 10.2.1 Notare il "!" che forza l'aggiornamento di r13/sp 10.2.2 Sottraendo 8 al registro r13/sp si lascia lo spazio per salvare il contenuto del registro cpsr (non si puo' salvarlo prima perche' non ci sono registri su cui operare) 10.3 Salvare il valore del registro cpsr nella locazione lasciata libera: +------------------------------+ |mrs lr,cpsr | |str lr,[sp,#4] | |ldr lr,[sp] | +------------------------------+ 10.4 Salvare il valore dei registri AACS-clobbered sullo stack: +------------------------------+ |stmfd sp!,{r0-r3,r12,lr} | +------------------------------+ 10.5 Ora la struttura dello stack e' identica a quella che si ha in seguito all'occorrenza di una interruzione: utilizziamo il codice della funzione _irq_schedule() per invocare lo scheduler ed, eventualmente, effettuare il cambio di contesto +------------------------------+ |b .Lnosub32 | +------------------------------+ 10.5.1 L'etichetta .Lnosub32 evita l'aggiornamento del registro r13/sp che in questo caso non e' necessario: +------------------------------+ |_irq_schedule: | | sub sp,sp,#32 | |.Lnosub32: | | ldr r12,=schedule | |[...] | +------------------------------+ 10.6 Aggiungere in comm.h la definizione extern per _sys_schedule() 11 Modificare la funzione main() per rimuovere l'invocazione di run_periodic_tasks() 11.1 E' necessario pero' aggiungere un ciclo senza fine a main(), che costituisce in pratica il programma del task 0 12 Provare il programma: sembra funzionare, ma... 13 Problema delle race condition: la funzione schedule() e' "rientrante" 13.1 Ad esempio: quando un job termina, viene invocata schedule(). Durante la sua esecuzione puo' arrivare un tick, che la interrompe e invoca nuovamente schedule() 13.2 E' necessario un meccanismo di sincronizzazione 13.3 Si utilizza un semplice "semaforo": +------------------------------------------------+ |struct task *schedule(void) | |{ | | static int do_not_enter = 0; | | struct task *best; | | unsigned long oldreleases; | | irq_disable(); | | if (do_not_enter != 0) { | | irq_enable(); | | return NULL; | | } | | do_not_enter = 1; | | do { | | oldreleases = globalreleases; | | irq_enable(); | | best = select_best_task(); | | irq_disable(); | | } while (oldreleases != globalreleases); | | trigger_schedule = 0; | | do_not_enter = 0; | | best = (best != current ? best : NULL); | | irq_enable(); | | return best; | |} | +------------------------------------------------+ =========