Prosty wielozadaniowy system operacyjny dla mikroprocesorów 8-bitowych (i nie tylko).

1. Wstęp

Już w starożytnym Rzymie.... no dobra, to był żart ;-)

Od dawna już przemyśliwałem sobie, aby mieć jakiegoś gotowca na avr'a, który by mi maksymalnie
uprościł pisanie programów. Ale myśleć to jedno, a zrobić to drugie...
Zacząłęm więc szukać po internecie gotowch systemów operacyjnych na "małe" procesory.
Jest tego mnóstwo np:
Mnie jednak zainspirował jeden artykuł:

AVR Scheduler

w którym krok po kroku opisano zasadę tworzenia schedulera (planista), czyli innymi słowy mówiąc managera zadań (task).
Jest to tzw. Round Robin (w koło Macieju). Coś takiego podobnego funkcjonowało kiedyś w systemie operacyjnym MS Windows 3.1
i nic dziwnego bo ta wersja "okienek" była tylko nakładką graficzną na DOS, który był jednozadaniowy.
Był to tzw. system kooperatywny, tzn. w danym momencie aktywne mogło być tylko jedne zadanie. Tutaj też jest podobnie,
aktualne zadanie zajmuje w całości czas procesora (prócz przerwań oczywiście, które chodzą niezależnie). Dlatego też
pisząc program na ten systemik należy sobie dokładnie przemyśleć co i jak ma działać, w jakiej kolejności i co ile należy
wywoływać nasze zadanie, aby system kręcił się szybko i nic go nie stopowało.

2. Implementacja


// wskaźnik na funkcję bez argumentów
typedef void (*task_t)(void);


// basic task control block (TCB)
//    czyli blok kontroli zadań
typedef struct __tcb_t
{
    uint8_t id; // task ID
    task_t task; // pointer to the task
    // delay before execution
    uint16_t delay, period;
    uint8_t status; // status of task
} tcb_t;



// funkcje schedulera
void initScheduler(void);
void addTask(uint8_t, task_t, uint16_t);
void deleteTask(uint8_t);
uint8_t getTaskStatus(uint8_t);
void dispatchTasks(void);


// prototypy dla zadań
void Task1(void);
void Task2(void);

// the task list
tcb_t task_list[MAX_TASKS];

// licznik przerwań
uint16_t count = 0;

// scheduler function definitions

// inicjujemy listę zadań
void initScheduler(void)
{
    for(uint8_t i=0; i<MAX_TASKS; i++)
    {
        task_list[i].id = 0;
        task_list[i].task = (task_t)0x00;
        task_list[i].delay = 0;
        task_list[i].period = 0;
        task_list[i].status = STOPPED;
    }
}


// dodajemy (tworzymy) nowe zadnie
void addTask(uint8_t id, task_t task,
             uint16_t period)
{
    uint8_t idx = 0, done = 0x00;   
    while( idx < MAX_TASKS )
    {
        if( task_list[idx].status == STOPPED )
        {
            task_list[idx].id = id;
            task_list[idx].task = task;
            task_list[idx].delay = period;
            task_list[idx].period = period;
            task_list[idx].status = RUNNABLE;           
            done = 0x01;
        }
        if( done ) break;
        idx++;
    }

}


// usuwamy zadanie z listy
void deleteTask(uint8_t id)
{   
    for(uint8_t i=0;i<MAX_TASKS;i++)
    {
        if( task_list[i].id == id )
        {
            task_list[i].status = STOPPED;
            break;
        }
    }
}


// gets the task status
// returns ERROR if id is invalid
uint8_t getTaskStatus(uint8_t id)
{
    for(uint8_t i=0;i<MAX_TASKS;i++)
    {
        if( task_list[i].id == id )
            return task_list[i].status;
    }
    return ERROR;
}

// dispatches tasks when they are ready to run

void dispatchTasks(void)
{
    for(uint8_t i=0;i<MAX_TASKS;i++)
    {
        // check for a valid task ready to run
        if( !task_list[i].delay &&
             task_list[i].status == RUNNABLE )
        {
            // task is now running
            task_list[i].status = RUNNING;           
            // call the task
            (*task_list[i].task)();

            // reset the delay
            task_list[i].delay = task_list[i].period;
            // task is runnable again
            task_list[i].status = RUNNABLE;
        }
    }   
}   


Funkcja dispatchTasks() jest główną funkcją odpowiedzialną za przełączanie zadań
w tym schedulerze. Na początku sprawdzane są warunki, które implikują dalsze działanie.
Czyli jeśli DELAY zadania osiągnął wartość ZERO AND ma status RUNNABLE
to zmieniamy mu status na RUNNING (uruchomiony) i wywołujemy zadanie do wykonania:

(*task_list[i].task)();


po wykonaniu zadania odświeżamy czas opóźnienia:

task_list[i].delay = task_list[i].period;

i zmieniamy status na RUNNABLE.


// generates a "tick"
// each tick 100ms apart
ISR(TIMER0_OVF_vect)
{
    count ++;
    if( count == 392 )
    {
        count = 0;
        // cycle through available tasks
        for(uint8_t i=0;i<MAX_TASKS;i++)
        {               
            if( task_list[i].status == RUNNABLE )
                task_list[i].delay--;
        }
    }
}

// Task definitions

void Task1(void)
{
    static uint8_t status = 0x01;
    if( status )
        PORTD |= _BV(PD0);
    else
        PORTD &= ~_BV(PD0);
    status = !status;
}


void Task2(void)
{
    static uint8_t status = 0x01;
    if( status )
        PORTD |= _BV(PD1);
    else
        PORTD &= ~_BV(PD1);
    status = !status;
}



int main(void)
{
    // use 1/8 of system clock frequency
    TCCR0 = 0x02;
    // inital timer value = 0
    TCNT0 = 0;   
    // enable Timer0 Overflow interrupt
    TIMSK = _BV(TOIE0);
    // set PORTD bit0 and bit1 as outputs
    DDRD = _BV(PD0)|_BV(PD1); 

    // set up the task list
    initScheduler();

    // add tasks, id is arbitrary
    // task1 runs every 1 second
    addTask(1, Task1, 10);

    // task2 runs every 4 seconds
    addTask(2, Task2, 40);   

    // enable all interrupts
    sei();   
    for(;;)
        dispatchTasks();
    return 0; // will never reach here
}

W funkcji main() jak widać nie ma wiele kodu, całość sprowadza się do
zainicjowania Timera, który bedzie nam wyznaczał czas do przełączania zadań,
zainicjowania Schedulera, dodaniu zadań, włączeniu przerwań i... wpadnięciu w wieczną pętlę
dispatchTasks().
Jak widać kod prosty i przejrzysty.

3. Poprawki

Ma ten system jednak również sporo wad. Pierwsza z nich to taka, że jeśli źle napiszemy program
dla któregoś zadania to możemy nie dopuścić do "głosu" pozostałych zadań (scheduler nie ma mechanizmu
wywłaszczania).
Dlatego też na tego typu SO pisząc program trzeby przyjąć zupełnie inną filozofię niż jak się pisze
program żonglując funkcjami w pętli głównej funkcji main().

Nie możemy więc zrobić pętli oczekującej np. na przychodzący znak z portu szergowego, gdyż pozostałe zadania
 w tym czasie będą oczekiwać wykonania (zostają zagłodzone), nie mówiąc o tym, że przecież timer cały czas pracuje
i pozostałe zadania bedą cały czas miały zmniejszany DELAY, aż do zera... a nawet więcej (ale o tym niżej)

// cycle through available tasks
        for(uint8_t i=0;i<MAX_TASKS;i++)
        {               
            if( task_list[i].status == RUNNABLE )
                task_list[i].delay--;
        }
Prowadzi to również do innego błędu. Jeśli uda się nam jakieś zadanie "przetrzymać" zbyt długo,
tak że jakieś inne zadanie zgłosi gotowość do wykonania osiągając task_list[i].delay==0 to w przypadku kiedy
nie otrzyma swojego czasu do wykonania to licznik czasu DELAY "przekręci" się nam
"uint16_t period
" i przy następnym przerwaniu od timera będziemy mieli 65534 zamiast zadeklarowanego
przez nas opóźnienia. Możemy się przed tym zabezpieczyć (na wszelki wypadek):

        for(uint8_t i=0;i<MAX_TASKS;i++)
        {               
          if( task_list[i].status == RUNNABLE )
          {
             if( task_list[i].status != 0 ) // zabezpieczenie
                 task_list[i].delay--;
          }
        }

Da nam to gwarancję, że licznik opóźniej zadań zatrzyma się nam na zerze. Oczywiście
czasy się nam "rozjadą", ale przynajmniej program zachowa stabilność (o ile oczywiście nie zadziała
np. watchdog...).

Kolejną niepodzianką jaką może nam sprawić ten scheduler to funkcja usuwania zadania z kolejki.
Wyobraźmy sobie taką sytuację, że zadanie (task) po wykonaniu zechce unicestwić sam siebie.
Mamy więc sytuację np:

Dodajemy zadanie:
[...]
addTask(1, Task1, 10);
[...]

void Task1(void)
{
// tu coś robimy
    if(){}
  

// unicestwiamy nasze zadanie
    deleteTask(1);    // zadanie otrzymuje atrybut STOPPED

}

a jak się zachowa nasz scheduler?

            (*task_list[i].task)(); // tutaj jest teraz nasze zadanie

            // reset the delay
            task_list[i].delay = task_list[i].period;
            // task is runnable again
            task_list[i].status = RUNNABLE;


jak widzimy nasze zadanie dalej będzie działać ponieważ atrybut STOPPED
zostanie nadpisany przez linijkę:
            task_list[i].status = RUNNABLE;

Dla spokojności sumienia dobrze więc będzie zmodyfikować również ten fragment programu:

            if(task_list[i].status == RUNNING) // dopisany warunek poniewaz watek nie mogl zlikwidowac sam siebie
                // reset the delay
     {
         task_list[i].delay = task_list[i].period;
         task_list[i].status = RUNNABLE;
     }
      else
         task_list[i].status = STOPPED;


4. Na koniec

Jak wcześniej wspomniałem tego typu SO ułatwiają pisanie programu, ale również narzucają nam pewien rygor
w pisaniu oprogramowania. Trzeba sobie wprzód wszystko dokładnie przemyśleć i przeliczyć ile na dane zadanie możemy
przeznaczyć czasu i czy się nam to zadanie na pewno "wyrobi" w zadeklarowanym czasie.  W przeciwnym wypadku
nasz system będzie doprowadzał nas tylko do frustracji.  Główną wadą tego systemu RR jest brak możliwości wywłaszczania
jednego zadania przez drugie, dlatego jakby komuś tego było za mało to może się zainteresować innym systemem
ze wspólnym stosem SST Super Simple Tasker.