Go Down

Topic: Cooperative multitasking scheduler for Arduino. (Read 6213 times) previous topic - next topic

kommisar

Jul 18, 2010, 04:51 pm Last Edit: Jul 18, 2010, 04:53 pm by kommisar Reason: 1
Hi All,

My name is Alexander and I am a robot enthusiast for many years, but I just recently discovered great world of Arduino. It has a lot of sweet features but I really missed one - multitask environment. There are nice timesharing libraries, but I am talking about real multitasking.  So, I spent a couple of days writing small cooperative multitasking scheduler suitable for Arduino which I would like to share with you.  As I said, I am new to Arduino but I hope your expertise will help me to make my scheduler Arduino friendly and useful for community.
The scheduler provides the following features:

?      Prioritized cooperative multitask environment where each task runs in its own execution context;
?      Simple intertask communication and synchronization;
?      Small footprint: less than 100 bytes RAM and approximately 1,5Kbyte of program.
?      No dependence on system resources like timers and interrupts.

Currently it is implemented as a bunch of C functions, but as far as I understand in order to make it a library I have to migrate to CPP at some point.

The interface is the following:
Code: [Select]

#ifndef __ADOS_INCLUDE
#define __ADOS_INCLUDE
/*
 adOS - Cooperative multitasking scheduler for Arduino.
 Copyright (c) 2010 Alexander P. Kolesnikov. All right reserved.

 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.

 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.

 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

#ifdef __cplusplus
extern "C"{
#endif

#if !defined(NULL)
   #define NULL 0
#endif

typedef enum ados_status_t
{
   ADOS_STATUS_RESERVED,
   ADOS_STATUS_OK,
   ADOS_STATUS_ERROR,
   ADOS_STATUS_BAD_PARAM,
   ADOS_STATUS_NOT_READY,
}ados_status_t;

typedef enum ados_state_t
{
   ADOS_STATE_RESERVED,
   ADOS_STATE_READY_TO_RUN,
   ADOS_STATE_NOT_READY_TO_RUN,
   ADOS_STATE_SLEEP,
}ados_state_t;

typedef unsigned long ados_timestamp_t;
typedef unsigned char ados_priority_t;

typedef void(*ados_taskptr_t)();

typedef struct ados_tcb_t
{
   unsigned char*  m_stack;
   ados_taskptr_t  m_taskptr;
   ados_priority_t  m_priority;
   ados_timestamp_t  m_nexttimetorun;
   ados_state_t  m_state;
   volatile struct ados_tcb_t* m_next;
   volatile struct ados_event_t* m_waitingfor;
}ados_tcb_t;

typedef struct ados_event_t
{
   unsigned char   m_state;
   volatile void*  m_param;
}ados_event_t;

typedef struct ados_ctrl_t
{
   unsigned char*          m_stack;
   volatile ados_tcb_t*    m_firstcb;
   volatile ados_tcb_t*    m_currenttcb;
}ados_ctrl_t;

void ados_init();
void ados_start();

ados_status_t ados_addTask(volatile ados_tcb_t* tcb, ados_taskptr_t taskptr,
   unsigned char* stack, unsigned int stacksize, ados_priority_t priority);
void ados_sleep(unsigned long msec);

unsigned char ados_eventTest(volatile ados_event_t* event);
volatile void* ados_eventWaitFor(volatile ados_event_t* event, unsigned long timeout);
void ados_eventPulse(volatile ados_event_t* event, volatile void* param);
void ados_eventSet(volatile ados_event_t* event, volatile void* param);
void ados_eventReset(volatile ados_event_t* event);

#ifdef __cplusplus
} // extern "C"
#endif

#endif //__ADOS_INCLUDE


And this is an example:
Code: [Select]

/*
adOS.c -
Copyright (c) 2010 Alexander P. Kolesnikov.  All right reserved.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/
#include <inttypes.h>
#include "adOS.h"

#define MAIN_TASK_PRIO      0
volatile ados_tcb_t g_mainTcb;
unsigned char g_mainTaskStack[128]   = {0xE7};

#define SERVICE_TASK_PRIO      128
volatile ados_tcb_t g_serviceTcb;
unsigned char g_serviceTaskStack[96]  = {0xE7};

volatile unsigned char  g_command = 0;
volatile ados_event_t   g_event = {0};

void mainTask()
{
     ados_sleep(500); //give time for rest of tasks to start
     for(;;)
     {
           g_command = random(255);
           ados_eventSet(&g_event,&g_command);
           ados_sleep(5000);
     }
}

void serviceTask()
{
     unsigned char* t_command = NULL;

     ados_sleep(500);//give time for rest of tasks to start
     for(;;)
     {
               t_command = (unsigned char*)ados_eventWaitFor(&g_event, 0);
           ados_eventReset(&g_event);
           Serial.print(t_command);
           Serial.println();
     }
}

void setup()
{
     Serial.begin(115200);

     ados_init();
     ados_eventReset(&g_event);
     ados_addTask(&g_serviceTcb, serviceTask,
           g_serviceTaskStack, sizeof(g_serviceTaskStack), SERVICE_TASK_PRIO);
     ados_addTask(&g_mainTcb, mainTask,
           g_mainTaskStack, sizeof(g_mainTaskStack), MAIN_TASK_PRIO);
}

void loop()
{
     ados_start(); //no return from here
}

In the example a task called "main" sets an event every 5 sec. Service task waits for that event and prints out a command received with the event.

I will publish sources of the scheduler later on.

Best regards,
Alexander K.

leppie

Is it possible to supply the implementation code as well, please?

mowcius

Quote
i  would like to share with you

Arghh!

Go away. My inbox is full of enough notifications as it is

kommisar

Ok, this is the code (Part1):
Code: [Select]

/*
adOS.c - Cooperative multitasking scheduler for Arduino.
Copyright (c) 2010 Alexander P. Kolesnikov.  All right reserved.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/
#include "wiring.h"
#include <setjmp.h>
#include "adOS.h"

volatile ados_ctrl_t       g_ados_ctrl = {0};
unsigned char*                   g_newstackptr  = (unsigned char*)NULL;
unsigned char*                   g_oldstackptr  = (unsigned char*)NULL;
volatile ados_tcb_t*       g_newtcb = (volatile ados_tcb_t*)NULL;
ados_taskptr_t                  g_taskptr = (ados_taskptr_t)NULL;
jmp_buf                         g_jmpbuf;
unsigned char                   g_shedulerstarted = 0;

unsigned char                   g_idleTaskStack[64];
volatile ados_tcb_t       g_idleTcb = {0};

static void ados_lock()
{
}

static void ados_unlock()
{
}

static void ados_reSchedule()
{
     if (g_shedulerstarted)
     {
           volatile ados_tcb_t* t_tcb;

           ados_timestamp_t t_currenttime = millis();

           for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
           {
                 if (ADOS_STATE_SLEEP==t_tcb->m_state && t_tcb->m_nexttimetorun<=t_currenttime)
                 {
                       t_tcb->m_state = ADOS_STATE_READY_TO_RUN;
                 }
                 if (ADOS_STATE_READY_TO_RUN==t_tcb->m_state)
                 {
                       if (t_tcb==g_ados_ctrl.m_currenttcb)
                       {
                             return;
                       }
                       g_newstackptr = t_tcb->m_stack;
                       g_newtcb = t_tcb;
                       //save current contex in the stack
                       //store GP registers
                       asm volatile(
                             "push r0\n\t"
                             "push r1\n\t"
                             "push r2\n\t"
                             "push r3\n\t"
                             "push r4\n\t"
                             "push r5\n\t"
                             "push r6\n\t"
                             "push r7\n\t"
                             "push r8\n\t"
                             "push r9\n\t"
                             "push r10\n\t"
                             "push r11\n\t"
                             "push r12\n\t"
                             "push r13\n\t"
                             "push r14\n\t"
                             "push r15\n\t"
                             "push r16\n\t"
                             "push r17\n\t"
                             "push r18\n\t"
                             "push r19\n\t"
                             "push r20\n\t"
                             "push r21\n\t"
                             "push r22\n\t"
                             "push r23\n\t"
                             "push r24\n\t"
                             "push r25\n\t"
                             "push r26\n\t"
                             "push r27\n\t"
                             "push r28\n\t"
                             "push r29\n\t"
                             "push r30\n\t"
                             "push r31\n\t"
                       );
                       //store status register
                       asm volatile(
                             "in r0,__SREG__\n\t"
                             "push r0\n\t"
                       );
                       //store current SP
                       asm volatile(
                             "in r0, __SP_L__ \n\t"
                             "sts g_oldstackptr,r0 \n\t"
                             "in r0, __SP_H__ \n\t"
                             "sts (g_oldstackptr)+1,r0 \n\t"
                        );
                          g_ados_ctrl.m_currenttcb->m_stack = g_oldstackptr;
                       g_ados_ctrl.m_currenttcb = g_newtcb;
                       //switch to new task
                       //set SP to new task stack
                       asm volatile(
                             "lds r0, (g_newstackptr)+1 \n\t"
                             "out __SP_H__,r0 \n\t"
                             "lds r0, (g_newstackptr) \n\t"
                             "out __SP_L__,r0 \n\t"
                       );
                       //restore status register
                       asm volatile(
                             "pop r0 \n\t"
                             "out __SREG__,r0 \n\t"
                       );
                       //restore GP registers
                       asm volatile(
                             "pop r31\n\t"
                             "pop r30\n\t"
                             "pop r29\n\t"
                             "pop r28\n\t"
                             "pop r27\n\t"
                             "pop r26\n\t"
                             "pop r25\n\t"
                             "pop r24\n\t"
                             "pop r23\n\t"
                             "pop r22\n\t"
                             "pop r21\n\t"
                             "pop r20\n\t"
                             "pop r19\n\t"
                             "pop r18\n\t"
                             "pop r17\n\t"
                             "pop r16\n\t"
                             "pop r15\n\t"
                             "pop r14\n\t"
                             "pop r13\n\t"
                             "pop r12\n\t"
                             "pop r11\n\t"
                             "pop r0\n\t"
                             "pop r9\n\t"
                             "pop r8\n\t"
                             "pop r7\n\t"
                             "pop r6\n\t"
                             "pop r5\n\t"
                             "pop r4\n\t"
                             "pop r3\n\t"
                             "pop r2\n\t"
                             "pop r1\n\t"
                             "pop r0\n\t"
                       );
                       ados_unlock();
                       return;
                 }
           }
     }
     else
     {
           //save context
           //store GP registers
           asm volatile(
                 "push r0\n\t"
                 "push r1\n\t"
                 "push r2\n\t"
                 "push r3\n\t"
                 "push r4\n\t"
                 "push r5\n\t"
                 "push r6\n\t"
                 "push r7\n\t"
                 "push r8\n\t"
                 "push r9\n\t"
                 "push r10\n\t"
                 "push r11\n\t"
                 "push r12\n\t"
                 "push r13\n\t"
                 "push r14\n\t"
                 "push r15\n\t"
                 "push r16\n\t"
                 "push r17\n\t"
                 "push r18\n\t"
                 "push r19\n\t"
                 "push r20\n\t"
                 "push r21\n\t"
                 "push r22\n\t"
                 "push r23\n\t"
                 "push r24\n\t"
                 "push r25\n\t"
                 "push r26\n\t"
                 "push r27\n\t"
                 "push r28\n\t"
                 "push r29\n\t"
                 "push r30\n\t"
                 "push r31\n\t"
           );
           //store status register
           asm volatile(
                 "in r0,__SREG__\n\t"
                 "push r0\n\t"
           );
           //store current SP
           asm volatile(
                 "in r0, __SP_L__ \n\t"
                 "sts g_oldstackptr,r0 \n\t"
                 "in r0, __SP_H__ \n\t"
                 "sts (g_oldstackptr)+1,r0 \n\t"
           );
           g_ados_ctrl.m_currenttcb->m_stack = g_oldstackptr;
           g_ados_ctrl.m_currenttcb = (volatile ados_tcb_t*)NULL;

           longjmp(g_jmpbuf,1);
           //will return to ados_initTask caller
     }
}

static void ados_initTask(volatile ados_tcb_t* tcb)
{
     g_newstackptr = tcb->m_stack;
     g_taskptr = tcb->m_taskptr;
     g_ados_ctrl.m_currenttcb = tcb;

     //store GP registers
     asm volatile(
           "push r0\n\t"
           "push r1\n\t"
           "push r2\n\t"
           "push r3\n\t"
           "push r4\n\t"
           "push r5\n\t"
           "push r6\n\t"
           "push r7\n\t"
           "push r8\n\t"
           "push r9\n\t"
           "push r10\n\t"
           "push r11\n\t"
           "push r12\n\t"
           "push r13\n\t"
           "push r14\n\t"
           "push r15\n\t"
           "push r16\n\t"
           "push r17\n\t"
           "push r18\n\t"
           "push r19\n\t"
           "push r20\n\t"
           "push r21\n\t"
           "push r22\n\t"
           "push r23\n\t"
           "push r24\n\t"
           "push r25\n\t"
           "push r26\n\t"
           "push r27\n\t"
           "push r28\n\t"
           "push r29\n\t"
           "push r30\n\t"
           "push r31\n\t"
     );
     //store status register
     asm volatile(
           "in r0,__SREG__\n\t"
           "push r0\n\t"
     );
     if (!setjmp(g_jmpbuf))
     {
           //set SP to task stack
           asm volatile(
                 "lds r0, (g_newstackptr)+1 \n\t"
                 "out __SP_H__,r0 \n\t"
                 "lds r0, (g_newstackptr) \n\t"
                 "out __SP_L__,r0 \n\t"
           );
           g_taskptr();
     }
     else
     {
           //restore status register
           asm volatile(
                 "pop r0 \n\t"
                 "out __SREG__,r0 \n\t"
           );
           //restore GP registers
           asm volatile(
                 "pop r31\n\t"
                 "pop r30\n\t"
                 "pop r29\n\t"
                 "pop r28\n\t"
                 "pop r27\n\t"
                 "pop r26\n\t"
                 "pop r25\n\t"
                 "pop r24\n\t"
                 "pop r23\n\t"
                 "pop r22\n\t"
                 "pop r21\n\t"
                 "pop r20\n\t"
                 "pop r19\n\t"
                 "pop r18\n\t"
                 "pop r17\n\t"
                 "pop r16\n\t"
                 "pop r15\n\t"
                 "pop r14\n\t"
                 "pop r13\n\t"
                 "pop r12\n\t"
                 "pop r11\n\t"
                 "pop r0\n\t"
                 "pop r9\n\t"
                 "pop r8\n\t"
                 "pop r7\n\t"
                 "pop r6\n\t"
                 "pop r5\n\t"
                 "pop r4\n\t"
                 "pop r3\n\t"
                 "pop r2\n\t"
                 "pop r1\n\t"
                 "pop r0\n\t"
           );
           ados_unlock();
     }
}

void idleTask()
{
     ados_lock();
     ados_reSchedule();
     for(;;)
     {
           ados_lock();
           ados_reSchedule();
           delay(1);
     }
}

void ados_init()
{
     //add Idle task
     ados_addTask(&g_idleTcb, idleTask,
           g_idleTaskStack, sizeof(g_idleTaskStack), 255);
}

void ados_start()
{
     volatile ados_tcb_t* t_tcb;

     for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
     {
           ados_initTask(t_tcb);
     }
     //start scheduler
     g_shedulerstarted = 1;
     //switch to Idle task context
     g_idleTcb.m_state = ADOS_STATE_READY_TO_RUN;
     ados_reSchedule();
}

ados_status_t ados_addTask(volatile ados_tcb_t* tcb, ados_taskptr_t taskptr,
     unsigned char* stack, unsigned int stacksize, ados_priority_t priority)
{
     if (NULL==tcb || NULL==stack)
     {
           return ADOS_STATUS_BAD_PARAM;
     }
     ados_lock();
     tcb->m_stack = stack+stacksize-1;
     tcb->m_taskptr = taskptr;
     tcb->m_priority = priority;
     tcb->m_state = ADOS_STATE_NOT_READY_TO_RUN;
     if (NULL==g_ados_ctrl.m_firstcb)
     {
           tcb->m_next = g_ados_ctrl.m_firstcb;
           g_ados_ctrl.m_firstcb = tcb;
     }
     else
     {
           volatile ados_tcb_t* t_tcb;
           ados_tcb_t** t_prevtcb = (ados_tcb_t**)&g_ados_ctrl.m_firstcb;

           for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
           {
                 if (tcb->m_priority<=t_tcb->m_priority)
                 {
                       tcb->m_next = *t_prevtcb;
                       *t_prevtcb = (ados_tcb_t*)tcb;
                       break;
                 }
                 t_prevtcb = (ados_tcb_t**)&t_tcb->m_next;
           }
     }
     return ADOS_STATUS_OK;
}

void ados_sleep(unsigned long msec)
{
     if (0!=msec)
     {
           ados_lock();
           g_ados_ctrl.m_currenttcb->m_state = ADOS_STATE_SLEEP;
           g_ados_ctrl.m_currenttcb->m_nexttimetorun = millis() + msec;
           ados_reSchedule();
     }
}

kommisar

Part 2:
Code: [Select]

unsigned char ados_eventTest(volatile ados_event_t* event)
{
     return event->m_state;
}

volatile void* ados_eventWaitFor(volatile ados_event_t* event, unsigned long timeout)
{
     if (!event->m_state)
     {
           ados_lock();
           if (timeout)
           {
                 g_ados_ctrl.m_currenttcb->m_state = ADOS_STATE_SLEEP;
                 g_ados_ctrl.m_currenttcb->m_nexttimetorun = millis() + timeout;
           }
           else
           {
                 g_ados_ctrl.m_currenttcb->m_state = ADOS_STATE_NOT_READY_TO_RUN;
           }
           g_ados_ctrl.m_currenttcb->m_waitingfor = event;
           ados_reSchedule();
     }
     return event->m_param;
}

void ados_eventPulse(volatile ados_event_t* event, volatile void* param)
{
     volatile ados_tcb_t* t_tcb;

     ados_lock();
     event->m_param = param;
     for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
     {
           if (t_tcb->m_waitingfor==event)
           {
                 t_tcb->m_state = ADOS_STATE_READY_TO_RUN;
                 t_tcb->m_waitingfor = NULL;
           }
     }
     ados_reSchedule();
}

void ados_eventSet(volatile ados_event_t* event,volatile void* param)
{
     ados_lock();
     event->m_state = 1;
     ados_unlock();
     ados_eventPulse(event,param);
}

void ados_eventReset(volatile ados_event_t* event)
{
     ados_lock();
     event->m_state = 0;
     event->m_param = NULL;
     ados_unlock();
}


I have to notice, that it is kind of draft code. Next step is move on to CPP and create an Arduino library.

Best regards,
Alexander K.

leppie

Thanks Kommisar.

2 questions:

1. Why is SREG being saved and restored at task 'invocation'?
2. Why is the lock and unlock functions empty? (simply not completed yet?)

cr0sh

Regarding the store/restore of the registers/pointers, etc (inline asm): could these (apparently?) be done as a defined macro or something to clean up the code (on the library rewrite)...? I am not sure if that can be done with that kind of code, it's just a thought...

:)
I will not respond to Arduino help PM's from random forum users; if you have such a question, start a new topic thread.

kommisar

Hi leppie,

Really good questions!
Actually there is one answer to both of them - interrupts.
The main idea of the scheduler function is restore execution context of a task to exactly the same state then the task was hibernated. But, as usual, there is a catch - Global Interrupt Enable bit. It requires special attention while restoring SREG.
And again, the lock and unlock function are just placeholders for now because I don't sure how to handle SREG in most elegant way.  

Bottom line: it is almost ok for current quick-and-dirty solution but I am still looking for appropriate arrangement for SREG. And I hope next version will include proper protection mechanism.

Best regards,
Alexander K.

kommisar

Hi cr0sh,

You are completely right - the code has a lot of potential for optimization, and I will try my best to utilize it while preparing the library. But for now I prefer to keep it as editable as possible.

Best regards,
Alexander K.

kommisar

The following is the initial CPP version of the scheduler library.
The scheduler is implemented as a singleton. So, the scheduler object is created automatically upon the fits call of the scheduler API.
The scheduler provides cooperative multitasking, it means it is preemptive but with one limitation - task switch occurs only on the following system (scheduler API) calls:

  • ADOS->Start() - start scheduler. Should be called once after all tasks are registered in the scheduler by the ADOS ->AddTask()  call.
  • ADOS->Sleep() - put task to sleep for a number of milliseconds;
  • ADOS->EventPulse() - awake all the tasks waiting for the event without changing event state;
  • ADOS->EventSet()  - set event to signaled state and then pulse it;
  • ADOS->EventWaitFor() - wait until the event is pulsed or the timeout occurs.      

The following system calls don't lead to task preemption:

  • ADOS->Init() - initialize scheduler. Should be called once before any other system call;
  • ADOS ->AddTask() - register task in the scheduler. All the tasks should be registered before invoking ADOS->Start() system call;
  • ADOS->EventReset() - set event to nonsignaled state;
  • ADOS->EventTest() - check event state without locking on it.

Only the following system calls are allowed from interrupt context:

  • ADOS->EventPulse() - parameter 'fromisr' should be set to true;
  • ADOS->EventSet() - parameter 'fromisr' should be set to true;
  • ADOS->EventReset()
  • ADOS->EventTest()

The first two calls above invoked from an ISR don't lead to immediate preemption of the currently executed task. They just mark tasks as ready to run. Actual task switch happens when next system call from a task execution context is invoked.
There is a hidden system task called 'Idle'. It has lowest priority (255) and it runs in case when there is no any other task is ready to run. By default, 'Idle' task calls scheduler every 1 millisecond.


kommisar

Header 'adOS.h':
Code: [Select]

#ifndef __ADOS_INCLUDE
#define __ADOS_INCLUDE
/*
 adOS - Cooperative multitasking scheduler for Arduino.
 Copyright (c) 2010 Alexander P. Kolesnikov. All right reserved.

 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.

 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.

 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

extern "C" {
     #include <inttypes.h>
}

#define ADOS      cAdOS::GetInstance()

typedef enum ados_status_t
{
     ADOS_STATUS_RESERVED,
     ADOS_STATUS_OK,
     ADOS_STATUS_ERROR,
     ADOS_STATUS_BAD_PARAM,
     ADOS_STATUS_NOT_READY,
}ados_status_t;

typedef enum ados_state_t
{
     ADOS_STATE_RESERVED,
     ADOS_STATE_READY_TO_RUN,
     ADOS_STATE_NOT_READY_TO_RUN,
     ADOS_STATE_SLEEP,
}ados_state_t;

typedef unsigned long ados_timestamp_t;
typedef uint8_t ados_priority_t;

typedef void(*ados_taskptr_t)();

typedef struct ados_tcb_t
{
     uint8_t* m_stack;
     ados_taskptr_t m_taskptr;
     ados_priority_t m_priority;
     ados_timestamp_t m_nexttimetorun;
     ados_state_t m_state;
     volatile struct ados_tcb_t* m_next;
     volatile struct ados_event_t*   m_waitingfor;
}ados_tcb_t;

typedef struct ados_event_t
{
     uint8_t             m_state;
     volatile void*  m_param;
}ados_event_t;

typedef struct ados_ctrl_t
{
     uint8_t*                         m_stack;
     volatile ados_tcb_t*      m_firstcb;
     volatile ados_tcb_t*      m_currenttcb;
}ados_ctrl_t;

class cAdOS
{
public:
     void Init();
     void Start();

static cAdOS* GetInstance();

     ados_status_t AddTask(volatile ados_tcb_t* tcb, ados_taskptr_t taskptr,
           uint8_t* stack, unsigned int stacksize, ados_priority_t priority);
     void Sleep(unsigned long msec);

     uint8_t EventTest(volatile ados_event_t* event);
     volatile void* EventWaitFor(volatile ados_event_t* event, unsigned long timeout);
     void EventPulse(volatile ados_event_t* event, volatile void* param, bool fromisr=false);
     void EventSet(volatile ados_event_t* event, volatile void* param, bool fromisr=false);
     void EventReset(volatile ados_event_t* event);

private:
     cAdOS();

static cAdOS*      m_AdOS;
};

#endif //__ADOS_INCLUDE


kommisar

Example:
Code: [Select]

/*
adOS.c - Cooperative multitasking scheduler for Arduino.
Copyright (c) 2010 Alexander P. Kolesnikov.  All right reserved.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/
#include <inttypes.h>
#include "adOS.h"

#define MAIN_TASK_PRIO      0
volatile ados_tcb_t g_mainTcb;
unsigned char g_mainTaskStack[128]   = {0xE7};

#define SERVICE_TASK_PRIO      128
volatile ados_tcb_t g_serviceTcb;
unsigned char g_serviceTaskStack[96]  = {0xE7};

volatile unsigned char  g_command = 0;
volatile ados_event_t   g_event = {0};

void mainTask()
{
     ados_sleep(500); //give time for rest of tasks to start
     for(;;)
     {
           g_command = random(255);
           ados_eventSet(&g_event,&g_command);
           ados_sleep(5000);
     }
}

void serviceTask()
{
     unsigned char* t_command = NULL;

     ados_sleep(500);//give time for rest of tasks to start
     for(;;)
     {
       t_command = (unsigned char*)ados_eventWaitFor(&g_event, 0);
           ados_eventReset(&g_event);
           Serial.print(t_command);
           Serial.println();
     }
}

void setup()
{
     Serial.begin(115200);

     ados_init();
     ados_eventReset(&g_event);
     ados_addTask(&g_serviceTcb, serviceTask,
           g_serviceTaskStack, sizeof(g_serviceTaskStack), SERVICE_TASK_PRIO);
     ados_addTask(&g_mainTcb, mainTask,
           g_mainTaskStack, sizeof(g_mainTaskStack), MAIN_TASK_PRIO);
}

void loop()
{
     ados_start(); //no return from here
}

kommisar

Source 'adOS.cpp'
Code: [Select]

/*
adOS.c - Cooperative multitasking scheduler for Arduino.
Copyright (c) 2010 Alexander P. Kolesnikov.  All right reserved.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/
#include <WProgram.h>
#include "adOS.h"

extern "C" {
     #include <setjmp.h>
}

#define ADOS_STORE_SREG() \
     asm volatile(   \
           "in r0,__SREG__\n\t"      \
           "push r0\n\t"   \
     );

#define ADOS_RESTORE_SREG()  \
     asm volatile(  \
           "pop r0 \n\t" \
           "out __SREG__,r0 \n\t"  \
     );

#define ADOS_PUSH_REGISTERS() \
     asm volatile( \
           "push r0\n\t push r1\n\t push r2\n\t push r3\n\t" \
           "push r4\n\t push r5\n\t push r6\n\t push r7\n\t" \
           "push r8\n\t push r9\n\t push r10\n\t push r11\n\t" \
           "push r12\n\t push r13\n\t push r14\n\t push r15\n\t" \
           "push r16\n\t push r17\n\t push r18\n\t push r19\n\t" \
           "push r20\n\t push r21\n\t push r22\n\t push r23\n\t" \
           "push r24\n\t push r25\n\t push r26\n\t push r27\n\t" \
           "push r28\n\t push r29\n\t push r30\n\t push r31\n\t");

#define ADOS_POP_REGISTERS() \
     asm volatile( \
           "pop r31\n\t pop r30\n\t pop r29\n\t pop r28\n\t" \
           "pop r27\n\t pop r26\n\t pop r25\n\t pop r24\n\t" \
           "pop r23\n\t pop r22\n\t pop r21\n\t pop r20\n\t" \
           "pop r19\n\t pop r18\n\t pop r17\n\t pop r16\n\t" \
           "pop r15\n\t pop r14\n\t pop r13\n\t pop r12\n\t" \
           "pop r11\n\t pop r10\n\t pop r9\n\t pop r8\n\t" \
           "pop r7\n\t pop r6\n\t pop r5\n\t pop r4\n\t" \
           "pop r3\n\t pop r2\n\t pop r1\n\t pop r0\n\t");

#define ADOS_STORE_STACKPTR() \
     asm volatile( \
           "in r0, __SP_L__ \n\t" \
           "sts g_oldstackptr,r0 \n\t" \
           "in r0, __SP_H__ \n\t" \
           "sts (g_oldstackptr)+1,r0 \n\t");

#define ADOS_RESTORE_STACKPTR() \
     asm volatile( \
           "lds r0, (g_newstackptr)+1 \n\t" \
           "out __SP_H__,r0 \n\t" \
           "lds r0, (g_newstackptr) \n\t" \
           "out __SP_L__,r0 \n\t");

extern "C" {
     uint8_t*      g_newstackptr  = (uint8_t*)NULL;
     uint8_t*      g_oldstackptr  = (uint8_t*)NULL;
}

static uint8_t  g_oldSREG;
static volatile ados_ctrl_t g_ados_ctrl = {0};
static volatile ados_tcb_t* g_newtcb = (volatile ados_tcb_t*)NULL;
static ados_taskptr_t      g_taskptr = (ados_taskptr_t)NULL;
static jmp_buf g_jmpbuf;
static uint8_t g_shedulerstarted = 0;

static uint8_t g_idleTaskStack[64];
static volatile ados_tcb_t g_idleTcb = {0};

cAdOS * cAdOS::m_AdOS = NULL;

static void ados_lock()
{
     g_oldSREG = SREG & 0x80;
     cli();
}

static void ados_unlock()
{
     if (g_oldSREG)
     {
           sei();
     }
}

void* operator new(size_t size)
{
     return malloc(size);
}

static void ados_reSchedule()
{
     if (g_shedulerstarted)
     {
           volatile ados_tcb_t* t_tcb;

           ados_timestamp_t t_currenttime = millis();

           for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
           {
                 if (ADOS_STATE_SLEEP==t_tcb->m_state && t_tcb->m_nexttimetorun<=t_currenttime)
                 {
                       t_tcb->m_state = ADOS_STATE_READY_TO_RUN;
                 }
                 if (ADOS_STATE_READY_TO_RUN==t_tcb->m_state)
                 {
                       if (t_tcb==g_ados_ctrl.m_currenttcb)
                       {
                             break;
                       }
                       g_newstackptr = t_tcb->m_stack;
                       g_newtcb = t_tcb;
                       //save current contex in the stack
                       //store GP registers
                       ADOS_PUSH_REGISTERS();
                       //store status register
                       ADOS_STORE_SREG();
                       //store current SP
                       ADOS_STORE_STACKPTR();
                          g_ados_ctrl.m_currenttcb->m_stack = g_oldstackptr;
                       g_ados_ctrl.m_currenttcb = g_newtcb;
                       //switch to new task
                       //set SP to new task stack
                       ADOS_RESTORE_STACKPTR();
                       //restore status register
                       ADOS_RESTORE_SREG();
                       //restore GP registers
                       ADOS_POP_REGISTERS();                        
                       break;
                 }
           }
     }
     else
     {
           ados_lock();
           //save context
           //store GP registers
           ADOS_PUSH_REGISTERS();
           //store status register
           ADOS_STORE_SREG();
           //store current SP
           ADOS_STORE_STACKPTR();
           g_ados_ctrl.m_currenttcb->m_stack = g_oldstackptr;
           g_ados_ctrl.m_currenttcb = (volatile ados_tcb_t*)NULL;
           longjmp(g_jmpbuf,1);
           //will return to ados_initTask caller
     }
     ados_unlock();
}

static void ados_initTask(volatile ados_tcb_t* tcb)
{
     g_newstackptr = tcb->m_stack;
     g_taskptr = tcb->m_taskptr;
     g_ados_ctrl.m_currenttcb = tcb;

     //store GP registers
     ADOS_PUSH_REGISTERS();
     //store status register
     ADOS_STORE_SREG();
     if (!setjmp(g_jmpbuf))
     {
           //set SP to task stack
           ADOS_RESTORE_STACKPTR();
           ados_unlock();
           g_taskptr();
     }
     else
     {
           //restore status register
           ADOS_RESTORE_SREG();
           //restore GP registers
           ADOS_POP_REGISTERS();
           ados_unlock();
     }
}

void idleTask()
{
     ados_lock();
     ados_reSchedule();
     for(;;)
     {
           ados_lock();
           ados_reSchedule();
           delay(1);
     }
}

void cAdOS::Init()
{
     //add Idle task
     AddTask(&g_idleTcb, idleTask,
           g_idleTaskStack, sizeof(g_idleTaskStack), 255);
}

cAdOS::cAdOS()
{
}

void cAdOS::Start()
{
     volatile ados_tcb_t* t_tcb;

     for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
     {
           ados_initTask(t_tcb);
     }
     ados_lock();
     //start scheduler
     g_shedulerstarted = 1;
     //switch to Idle task context
     g_idleTcb.m_state = ADOS_STATE_READY_TO_RUN;
     ados_reSchedule();
}

cAdOS* cAdOS::GetInstance()
{
     if (NULL==m_AdOS)
     {
           m_AdOS = new cAdOS;
     }
     return m_AdOS;
}

ados_status_t cAdOS::AddTask(volatile ados_tcb_t* tcb, ados_taskptr_t taskptr,
     uint8_t* stack, unsigned int stacksize, ados_priority_t priority)
{
     if (NULL==tcb || NULL==stack)
     {
           return ADOS_STATUS_BAD_PARAM;
     }
     ados_lock();
     tcb->m_stack = stack+stacksize-1;
     tcb->m_taskptr = taskptr;
     tcb->m_priority = priority;
     tcb->m_state = ADOS_STATE_NOT_READY_TO_RUN;
     if (NULL==g_ados_ctrl.m_firstcb)
     {
           tcb->m_next = g_ados_ctrl.m_firstcb;
           g_ados_ctrl.m_firstcb = tcb;
     }
     else
     {
           volatile ados_tcb_t* t_tcb;
           ados_tcb_t** t_prevtcb = (ados_tcb_t**)&g_ados_ctrl.m_firstcb;

           for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
           {
                 if (tcb->m_priority<=t_tcb->m_priority)
                 {
                       tcb->m_next = *t_prevtcb;
                       *t_prevtcb = (ados_tcb_t*)tcb;
                       break;
                 }
                 t_prevtcb = (ados_tcb_t**)&t_tcb->m_next;
           }
     }
     ados_unlock();
     return ADOS_STATUS_OK;
}

void cAdOS::Sleep(unsigned long msec)
{
     if (0!=msec)
     {
           ados_lock();
           g_ados_ctrl.m_currenttcb->m_state = ADOS_STATE_SLEEP;
           g_ados_ctrl.m_currenttcb->m_nexttimetorun = millis() + msec;
           ados_reSchedule();
     }
}

uint8_t cAdOS::EventTest(volatile ados_event_t* event)
{
     return event->m_state;
}

volatile void* cAdOS::EventWaitFor(volatile ados_event_t* event, unsigned long timeout)
{
     if (!event->m_state)
     {
           ados_lock();
           if (timeout)
           {
                 g_ados_ctrl.m_currenttcb->m_state = ADOS_STATE_SLEEP;
                 g_ados_ctrl.m_currenttcb->m_nexttimetorun = millis() + timeout;
           }
           else
           {
                 g_ados_ctrl.m_currenttcb->m_state = ADOS_STATE_NOT_READY_TO_RUN;
           }
           g_ados_ctrl.m_currenttcb->m_waitingfor = event;
           ados_reSchedule();
     }
     return event->m_param;
}

void cAdOS::EventPulse(volatile ados_event_t* event,
     volatile void* param, bool fromisr)
{
     volatile ados_tcb_t* t_tcb;

     ados_lock();
     event->m_param = param;
     for (t_tcb=g_ados_ctrl.m_firstcb; NULL!=t_tcb; t_tcb=t_tcb->m_next)
     {
           if (t_tcb->m_waitingfor==event)
           {
                 t_tcb->m_state = ADOS_STATE_READY_TO_RUN;
                 t_tcb->m_waitingfor = NULL;
           }
     }
     if (!fromisr)
     {
           ados_reSchedule();
     }
}

void cAdOS::EventSet(volatile ados_event_t* event,
     volatile void* param, bool fromisr)
{
     ados_lock();
     event->m_state = 1;
     ados_unlock();
     EventPulse(event, param, fromisr);
}

void cAdOS::EventReset(volatile ados_event_t* event)
{
     ados_lock();
     event->m_state = 0;
     event->m_param = NULL;
     ados_unlock();
}

chaoui

hello
to use this last example with the cpp header you have substitute (ados_) by (ADOS->)
thanks

Alain Spineux

This small and very simple lib works very well !

I use it with FastSerail without any problem.

If your sketch freeze, try adding more memory to your stack.

adOS looks to be fast ! Be generous with ADOS->Sleep()  in
your code :-).

My own tasks require huge stack (most of them 256K) I have not
yet tried to know why.

Thanks Kommisar !

I tried to add task adding and removing after start but
without success :-( .

Here is the working and slightly modified example.
Code: [Select]
/*
adOS.c - Cooperative multitasking scheduler for Arduino.
Copyright (c) 2010 Alexander P. Kolesnikov.  All right reserved.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/
#include <inttypes.h>
#include "adOS.h"

#define MAIN_TASK_PRIO      0
volatile ados_tcb_t g_mainTcb;
unsigned char g_mainTaskStack[128]   = {0xE7};

#define SERVICE_TASK_PRIO      128
volatile ados_tcb_t g_serviceTcb;
unsigned char g_serviceTaskStack[96]  = {0xE7};

char hello[]="Hello World\n";

volatile unsigned char  g_command = 0;
volatile ados_event_t   g_event = {0};

void mainTask()
{
       int i=0;
     ADOS->Sleep(500); //give time for rest of tasks to start
     for(;;)
     {
           g_command = hello[i];
               if (g_command=='\n') i=0;
               else i++;
           ADOS->EventSet(&g_event,&g_command);
           ADOS->Sleep(1000);
     }
}

void serviceTask()
{
     unsigned char* t_command = NULL;

     ADOS->Sleep(500);//give time for rest of tasks to start
     for(;;)
     {
       t_command = (unsigned char*)ADOS->EventWaitFor(&g_event, 0);
           ADOS->EventReset(&g_event);
           Serial.print(*t_command);
     }
}

void setup()
{
     Serial.begin(115200);

     ADOS->Init();
     ADOS->EventReset(&g_event);
     ADOS->AddTask(&g_serviceTcb, serviceTask,
           g_serviceTaskStack, sizeof(g_serviceTaskStack), SERVICE_TASK_PRIO);
     ADOS->AddTask(&g_mainTcb, mainTask,
           g_mainTaskStack, sizeof(g_mainTaskStack), MAIN_TASK_PRIO);
}

void loop()
{
     ADOS->Start(); //no return from here
}



Go Up