Visualizza il feed RSS

Do It Yourself

Embedded e Arduino Scheduler, Parte 1

Valuta questo inserimento
di pubblicato il 18-12-2015 alle 15:46 (4345 Visite)
Mentre rispondevo a messaggi del forum Arduino ho visto varie implementazioni di scheduler, con tante richieste di usare lo Scheduler di Arduino Due sulle altre Board.
Ho quindi deciso di provarci anche io, prenderemo in rassegna uno scheduler cooperativo, lo inseriremo nel core arduino ed infine implementeremo anche uno scheduler a prelazione.
Userò Arduino Uno(328p), anche se il codice con qualche piccola modifica andrà su qualsiasi tipo di chip.

Lo Scheduler:
Fino a qualche anno fa i microprocessori erano ad un solo core, questo significa che possono eseguire una sola istruzione alla volta e dunque un solo programma.
Ma spesso si voleva eseguire piu programmi o comunque si volevano fare eseguire piu cose contemporaneamente al chip, l'unica possibile soluzione era interrompere il programma in esecuzione e passare la palla al successivo programma, il software che fa ciò si chiama scheduler.
Lo scheduler permette di eseguire piu azioni in maniera pseudo parallela, pseudo perché nonostante abbiamo l'impressione che tutto lavori all'unisono invece viene eseguito in maniera sequenziale.
Per saltare da un compito ad un altro lo scheduler può usare due tecniche, la prima si chiama a cooperazione e la seconda a prelazione.
La cooperazione si ha quando sono i processi stessi a decidere di ridare l'esecuzione allo scheduler che a sua volta deciderà chi tornerà in esecuzione.
Nella prelazione invece non è il task attivo a decidere quando passare la palla, ma è lo scheduler che permetterà un tempo massimo di esecuzione di tale processo per poi bloccarlo e scegliere chi sarà il successivo processo in esecuzione.

Scheduler Cooperativo:
Iniziamo a parlare di scheduler cooperative che lo si ritrova spesso nel mondo embedded, forse perché è semplice da scrivere e da attuare.
Il piu semplice scheduler cooperativo:
codice:
void task1()
{
   //fai qualcosa
}

void task2()
{
   //fai qualcosa
}

void loop()
{
   task1();
   task2();
}
La funzione loop() svolgerà il compito dello scheduler che eseguira a ripetizione i due processi.
Se ci si sofferma anche solo un secondo si capirà che task2() verrà eseguito solo e soltanto dopo il task1() che dovrà quindi prendersi carico di questa responsabilità.
Questo è il problema che grava di piu sullo scheduler cooperativo, un processo che entra in un loop infinito bloccherà l'intero scheduling, un processo che impiegherà un minuto ritarderà di tale tempo l'avvio del prossimo task.
Quando si usano gli scheduler cooperativi i vari task dureranno sempre pochi millisecondi, quando un task richiede un tempo piu lungo di esecuzione si adotterà una macchina a stati, dove ogni stato durerà sempre pochi millisecondi, in questo modo il processo si auto suddividerà in piccoli processi ridando il controllo allo scheduler finito il corrente stato.
Come si intuisce tutto questo procedimento è critico e se non si è attenti si finisce per fare pasticcio.
Il piccolo frammento di codice proposto però è decisamente poco utile per un reale scheduler cooperativo, nella realtà servirà che i processi vengano eseguiti ad ogni preciso periodo di tempo, in caso che due processi debbano essere eseguiti allo stesso tempo uno possa avere priorità piu alta rispetto ad un altro e magari la possibilità di fermare e riprendere l'esecuzione del task.
Per scandire il tempo avremo bisogno di un timer e per contenere i dati useremo una struttura che conterrà le informazioni sul task.
Il timer sarebbe comodo usarne uno che permetta di leggere con precisione il suo tick e facilmente settabile su un valore voluto.Sul 328p il timer1/timer2 andrebbero benissimo, ma Arduino usa questi timer per delle librerie e riutilizzarli ci causerebbe seri problemi di compatibilità, ecco perché ho scelto di usare il watch dog che può essere usato alla stregua di un timer anche se con grosse limitazioni.
Andiamo a creare un nuovo progetto con l' IDE Arduino e aggiungiamo due schede, una dal nome “scheduler.h” e l'altra “scheduler.ino”, questi due moduli conterranno tutto ciò che ci serve per il nostro scheduler cooperativo.
file: "scheduler.h
codice:
#ifndef __SCHEDULER_H__
#define __SCHEDULER_H__

#include <stdint.h>
#include <avr/interrupt.h>
#include <avr/wdt.h>

#define WDT_PRESCALER  0
#define msToTick(MS) ((MS)>>4)

#define interrupt_scheduler()    ISR(WDT_vect,ISR_BLOCK)


#define TASK_MAX 16
#define TASK_EMPTY 0

typedef void(*loop_f)(void);

typedef enum{ TSK_STOP, TSK_WAIT, TSK_RUN} tskstate_e;

struct task
{
   uint8_t pid;
   uint8_t prio;
   tskstate_e state;
   uint8_t statemachine;
   uint32_t mytick;
   uint32_t tick;
   loop_f fnc;
};


void wdt_interrupt(uint8_t enable);
void scheduler_init(void);
void scheduler_yield(void);
uint8_t scheduler_startLoop(loop_f f);
uint8_t tsk_add(uint8_t pid, uint8_t prio, uint32_t tick, loop_f fnc );
void scheduler_delay(uint32_t ms);
uint8_t statemachine();
void statemachine_set(uint8_t s);

#endif
Iniziamo a descrivere cosa contiene:
WDT_PRESCALER” è la macro che setta il periodo del nostro tick, in questo caso essendo a 0 il watch dog interrupt verrà richiamato ogni 16 millisecondi.
msToTick” passatogli un tempo in millisecondi restituisce il tempo espresso in tick.
interrupt_scheduler” non fa altro che dare un nome piu significativo all'interrupt
TASK_MAX” definisce quanti task possiamo avere
TASK_EMPTY” è il valore di pid che corrisponde al task non utilizzato
loop_f” è il puntatore a funzione che definisce il modello di un task
tskstate_e” è una enumerazione che definisce i 3 possibili stati che può avere un processo.
struct task” è la struttura che definisce come è un task, conterrà tutto cio che ci serve:
.pid identifica il task
.prio la priorità
.state lo stato del task
.statemachine supporto per la macchina a stati
.mytick il sucessivo richiamo della funzione
.tick il periodo
.fnc il task
Infine abbiamo semplicemente i prototipi delle funzioni.

file: “scheduler.ino
codice:
#include "scheduler.h"
#include <stdint.h>
#include <avr/interrupt.h>
#include <avr/wdt.h>

static uint32_t _tick;
static uint8_t _ctask = TASK_MAX;
static struct task _task[TASK_MAX];
static uint8_t l0sm = 0;

interrupt_scheduler()
{
    ++_tick;
}

void wdt_interrupt(uint8_t enable) 
{ 
    cli(); 
    MCUSR &= ~(1 << WDRF);
    wdt_reset();
    if( 0 == enable )
    {
        WDTCSR |= (1<<WDCE) | (1<<WDE);
        WDTCSR = 0x00;
        sei();
        return;
    }
    
    WDTCSR = (1<<WDCE) | (1<<WDE);
    WDTCSR = (1<<WDIE) | WDT_PRESCALER;
    sei();
}

uint8_t tsk_add(uint8_t pid, uint8_t prio, uint32_t tick, loop_f fnc )
{
 
    uint8_t ip;

    if ( TASK_EMPTY != _task[TASK_MAX - 1].pid ) return 1;

    for ( ip = 0; TASK_EMPTY != _task[ip].pid && prio < _task[ip].prio  ; ++ip);

    uint8_t i;
    for( i = TASK_MAX - 1; i > ip; --i)
        _task[i] = _task[i-1];

    _task[ip].pid = pid;
    _task[ip].prio = prio;
    _task[ip].state = TSK_WAIT;
    _task[ip].statemachine = 0;
    _task[ip].tick = tick;
    _task[ip].mytick = _tick + tick;
    _task[ip].fnc = fnc;

    return 0;
}

void scheduler_init(void)
{
    uint8_t i;
    for ( i = 0; i < TASK_MAX; ++i)
        _task[i].pid = 0;
    
    wdt_interrupt(1);
}

void scheduler_yield(void)
{
    uint8_t oldtask = _ctask;
    uint8_t i;
    for ( i = 0; i < TASK_MAX && TASK_EMPTY != _task[i].pid; ++i)
    {
         if ( TSK_WAIT == _task[i].state && _tick >= _task[i].mytick )
         {
             _ctask = i;
             _task[i].state = TSK_RUN;
             _task[i].fnc();
             _task[i].state = TSK_WAIT;
             _task[i].mytick = _tick + _task[i].tick;
         }
    }
    _ctask = oldtask;
}

void scheduler_delay(uint32_t ms)
{
    uint32_t t = millis() + ms;
    while ( millis() < t ) scheduler_yield();
}

uint8_t statemachine()
{
    if ( _ctask < TASK_MAX ) return _task[_ctask].statemachine;
    return l0sm;
}

void statemachine_set(uint8_t s)
{
    if ( _ctask < TASK_MAX ) 
        _task[_ctask].statemachine = s;
    else
        l0sm = s;
}
Partendo ad analizzare il codice troviamo:
_tick” la variabile globale che memorizza quante volte l'interrupt è stato richiamato.
_ctask” mantiene in memoria il task in esecuzione, servirà solo per gestire la macchina a stati.
_task” il vettore che contiene tutti i nostri processi.
l0sm” è la macchina a stati del loop(), questo è separato perché il main loop non è dentro alla lista dei task, questo per rispettare Arduino.
interrupt_scheduler()” la ISR che viene richiamata ogni 16ms dove verrà solamente incrementata la variabile _tick.
wdt_interrupt()” abilita/disabilita il watch dog come interrupt ogni 16ms
tsk_add()” si aggiunge un task con i seguenti parametri:
pid, deve essere diverso da TASK_EMPTY ovvero != 0;
prio, la priorita da 0 a 255
tick, dopo quanti tick deve essere richiamata
fnc, la funzione che andrà ad essere eseguita.
Codesta funzione controlla che non sia pieno il vettore, in caso ritorna 1, va a ricercare la posizione dove inserire il task, sposta i task verso il basso ed inserisce il nuovo task.Praticamente non è altro che un vettore ordinato per priorità, dove la priorità con il numero maggiore sia all'indice 0 e qualla con priorità minore sia verso l'indice TASK_MAX.
scheduler_init()” azzera il vettore _task e fa partire il watch dog
scheduler_yield()” il cuore dello scheduler, verrà scandito tutto il vettore_task e quando trova un task in attesa(TSK_WAIT) se il tempo attuale _tick è uguale o superiore al tempo del task(.mytick) lo porterà in esecuzione.
scheduler_delay()” dato che la funzione delay() bloccherebbe tutto lo scheduler ho scritto una versione modificata in modo da poter eseguire il delay senza interrompere i restanti processi, la funzione infatti andrà a richiamare lo yield() che controllerà se c'è processo in attesa.
statemachine()” ritorna il valore della macchina a stati corrente
statemachine_set()” setta il valore della macchina a stati

Ora che ho introdotto sommariamente lo scheduler andiamo a provarlo
file: “testCooperative.ino
codice:
#include "scheduler.h"

void loop1()
{
    switch ( statemachine() )
    {
        case 0:
            pinMode(13,OUTPUT);
            statemachine_set(1);
        break;

        case 1:
            digitalWrite(13, HIGH);
            scheduler_delay(500);
            statemachine_set(2);
        return;

        case 2:
            digitalWrite(13, LOW);
            scheduler_delay(500);
            statemachine_set(1);
        return;

        default: 
            statemachine_set(0);
        break;
    }

    scheduler_yield();
}

void loop2(void)
{
    Serial.println("Loop2 work");
}

void setup()
{
    Serial.begin(9600);
    scheduler_init();
    tsk_add(100, 1,             1, loop1);
    tsk_add(101, 1, msToTick(700), loop2);
}

void loop() 
{
    Serial.println("Loop0 work");
    scheduler_delay(1500);
}
Andiamo prima di tutto a creare un task chiamato loop1(), tale funzione controllerà il valore della propria macchina a stati e in base allo stato corrente accenderà o spegnerà il led a bordo della scheda.
Loop2() scriverà semplicemente che sta girando.
Setup() inizializza la seriale, inizializza lo scheduler, aggiunge i due task, il primo con pid 100, priorità 1 che avrà periodo di un tick e dunque sarà richiamato ogni 16ms
Il secondo con pid 101, priorità 1 con periodo di 700ms.
Infine entriamo nel loop() che ciclerà inviando che sta funzionando e attenderà un secondo e mezzo.
Ora compiliamo e carichiamo, apriamo il monitor seriale e vedremo che tutti e tre i processi stanno lavorando insieme.

Conclusione:
Adesso potete divertivi a giocare con questo particolare scheduler cooperativo, particolare perché lavora quasi fosse una funzione ricorsiva, queso modello l'ho scelto appositamente perché ci permetterà di capire piu a fondo il successivo articolo che parlerà su come portare lo scheduler di Arduinio DUE sulla UNO.
Quindi nel frattempo divertitevi.

aggiornamento da 21-12-2015 a 18:58 di Master85

Categorie
Programmazione , Hardware , Open Source , Tecnologia

Commenti