Pages: 1 [2] 3 4 5   Go Down
Author Topic: SCoop - multitask and Simple COOPerative scheduler AVR & ARM  (Read 23527 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 1
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

here we go:

google code updated with SCoop library V1.1.1 XMass Pack, for enhancing the SCoopFifo object with atomic code portion.
this now enables using fifo in ISR like in example 4 of the pack.
thanks to fat16lib for finding the bug.
please download this version if you plan to use fifo in isr.

also include a new example 5 demonstrating a 500hz analog sampling with fifo logging and treatmet by a task without interrupts

time for the week end, I might do some followup as of 25/26th of december due to XMass week end with familly.

// BTW // regarding post above, linux type of OS is probably a nice alternative, especially for raspberry pi or PC on key with android for example. but for Teensy3 and Arduino DUE, the size of the program memory might not be ok, considering the large size of code generated by the ARM compiler... I still beleive that we have nice days ahead of us with Schedulers smiley

cheers
Logged

0
Offline Offline
Edison Member
*
Karma: 64
Posts: 1638
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I am not interested in sampling, the problem is that libraries required to log data can not be salted with enough yields() to get low jitter or worse, missed data points.  You don't need a scheduler to sample at 500 Hz, it's trivial.

You must learn something about the theory of SNR for ADC sampling.  Data is worthless if there is substantial jitter in the time between data points.

Your toy examples don't proving anything.  You must do real examples with popular Arduino libraries.  That's why I include a real data logging example.

Quote
but for Teensy3 and Arduino DUE, the size of the program memory might not be ok
I didn't mean running a true Linux/Unix I meant one of the many small kernels that are Linux like.  These kernels run on very small processors.  There are an amazing number of kernels out there.

Quote
I still beleive that we have nice days ahead of us with Schedulers
Your right, there are still lots people writing coop schedulers so you are not the last diehard.  People still write apps in assembler too.
« Last Edit: December 22, 2012, 05:21:01 pm by fat16lib » Logged

Offline Offline
Newbie
*
Karma: 1
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

hello

thanks for your advice about jitter and snr. myself I m quite aware of these theories and their effect typically in the audio world as I have invested in a Fifo board for my oppo player, just to dejitter the digital signal smiley and it makes an incredible difference.
FYI here is the product and I highly recommend it :http://audiopraise.com/vanity93/overview.php
(of course it is worthless if you do not put a DAC with clean clock after it)

that said, the examples are just written to show how to use the macros and objects of the library, I will not pretend giving state of the art coding technics in the whole sampling or digital treatment area. therefore if you suggest to change the prefix names of the examples by the word "toy" , feel free to log an issue in the google code project, but I suggest you flag it low importance as i would not change it before the next release planned early 2013.  smiley-cool

I hope we can get the full benefit of our mutual experience and collaboration in the coming post, for the benefit of the community.
merry Christmass to all !
Logged

0
Offline Offline
Edison Member
*
Karma: 64
Posts: 1638
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Yes, digital audio is truly amazing.  In another thread I cited audio ADC performance as an example.  The person I replied to wrote me off.  He said he was interested in "high quality ADCs".  If a 124dB, 384kHz Audio ADC isn't impressive what is.

Here is a jitter test sketch.  It only captures a counter since the test is how precise scheduling is.  It does not use an ISR since many devices/sensors can not be accessed in an ISR using popular Arduino libraries.  The I2C Wire library can't be used in an ISR and I2C devices are very common in the Arduino world.

It records the results to an SD.  I use my SD library but you can use the "Official Arduino SD library" it's an ancient version of my library with a wrapper to, as you say, "make it user friendly".

The only other library I use is ChibiOS.  I did a simple fifo with two semaphores and an array.  The data rate is slow, a point every 10,240 usec, since it is common for Arduino users to record things like accelerometers at about 100 Hz.

I ran the test for a number of minutes and there was no jitter between points.  micros() in AVR ticks every 4 usec so that limits the accuracy of the test.

Here is calculation of what 4 usec of jitter means in this case.  Here is the formula:
Quote
SNR due clock jitter:

SNR(dB) = -20*log(6.28*f*t)

f is the measurement frequency

t is the time jitter in seconds

For t = 4 usec and f about 98 Hz you get about 52 dB.  The SNR for an ideal 10-bit ADC is about 62 dB so even this much jitter degrades the signal.

I don't know a lot about audio but I have read about ADC clocks with jitter well below 100 femtoseconds.  Wow, not nano, not pico, but femto.  I guess you can lease a Galaxy FemtoSecond 77 fsec clock for $233 a month on a six year term.

Here is the sketch for ChibiOS and it is followed by a bit of the file.  I look forward to your sketch for this test so I can run it and produce a file.
Code:
#include <ChibiOS_AVR.h>
#include <SdFat.h>

// interval between points in units of 1024 usec
const uint16_t intervalTicks = 10;
//------------------------------------------------------------------------------
// SD file definitions
SdFat sd;
SdFile file;
//------------------------------------------------------------------------------
// Fifo definitions

// size of fifo
const size_t FIFO_SIZE = 20;

// count of data records in fifo
SEMAPHORE_DECL(fifoData, 0);

// count of free buffers in fifo
SEMAPHORE_DECL(fifoSpace, FIFO_SIZE);

// data type for fifo item
struct FifoItem_t {
  uint32_t usec;  
  int value;
  int error;
};
// array of data items
FifoItem_t fifoArray[FIFO_SIZE];

// head and tail index for fifo
size_t fifoHead = 0;
size_t fifoTail = 0;
//------------------------------------------------------------------------------
// 64 byte stack beyond task switch and interrupt needs
static WORKING_AREA(waThread1, 64);

static msg_t Thread1(void *arg) {
  int error = 0;
  int count = 0;
  while (1) {
    chThdSleep(intervalTicks);
    // get a buffer
    if (chSemWaitTimeout(&fifoSpace, TIME_IMMEDIATE) != RDY_OK) {
      // fifo full indicate missed point
      error++;
      continue;
    }
    FifoItem_t* p = &fifoArray[fifoHead++];
    if (fifoHead >= FIFO_SIZE) fifoHead = 0;
    p->usec = micros();
    p->value = count++;
    p->error = error;
    error = 0;
    
    // signal new data
    chSemSignal(&fifoData);
  }
  return 0;
}
//------------------------------------------------------------------------------
void setup() {
  Serial.begin(9600);
  Serial.println(F("type any character to begin"));
  while(!Serial.available());
  
  // open file
  if (!sd.begin() || !file.open("DATA.CSV", O_CREAT | O_WRITE | O_TRUNC)) {
    Serial.println(F("SD problem"));
  }
  
  // throw away input
  while (Serial.read() >= 0);
  Serial.println(F("type any character to end"));
  
  // start kernel
  chBegin(chSetup);
  while(1);
}
//------------------------------------------------------------------------------
void chSetup() {
  // start producer thead
  chThdCreateStatic(waThread1, sizeof(waThread1), NORMALPRIO + 2, Thread1, NULL);  
}
//------------------------------------------------------------------------------
// time in micros of last point
uint32_t last = 0;
void loop() {
  // wait for next data point
  chSemWait(&fifoData);
  
  FifoItem_t* p = &fifoArray[fifoTail++];
  if (fifoTail >= FIFO_SIZE) fifoTail = 0;
  
  file.print(p->usec - last);
  last = p->usec;
  file.write(',');
  file.print(p->value);
  file.write(',');
  file.println(p->error);
  
  // release space
  chSemSignal(&fifoSpace);
  
  if (Serial.available()) {
    file.close();
    Serial.println(F("Done"));
    while(1);
  }
}
Here is the file.  The first column is the time between points in micros(), the second is the counter, and the third is the number of missed points due to no fifo space.
Quote
10240,10,0
10240,11,0
10240,12,0
10240,13,0
10240,14,0
10240,15,0
10240,16,0
10240,17,0
10240,18,0
10240,19,0
10240,20,0
10240,21,0
10240,22,0
10240,23,0
10240,24,0
10240,25,0
10240,26,0
10240,27,0
10240,28,0
10240,29,0
10240,30,0
10240,31,0
10240,32,0
10240,33,0
10240,34,0
10240,35,0
10240,36,0
10240,37,0
10240,38,0
10240,39,0
10240,40,0
10240,41,0
10240,42,0
10240,43,0
« Last Edit: December 23, 2012, 05:06:28 pm by fat16lib » Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 32
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hey good to see the SCoop - I haven't been able to try it out yet - but fantastic to see something published.
I've put a simple multi-loop tasker together myself - based on the TinyOs.net way of doing it. However I haven't had time to be able to test it out or publish.
I look forward to checking out SCoop.
IMHO the value of a co-operative scheduler, is to have a simple move into multi-tasking.
It seems to me the value of pre-emptive schedulers is to be able to do system level heavy lifting - especially for buffered IO process tcp/ip interrupts, and to be able to meet other hard deadlines.  The cost of the pre-emptive scheduler, IMHO, is high in terms of system complexity and maintaining stability.
In a previous life with a 100 realtime software engineers, the Software VP owned the pre-emptive schedulers priorities to stop just anyone optomizing it for their functional systems.  In fact most of the processes ran at the same priority, and just the few processes that were managing the hardware redundancy and I/O had higher priorities.

My experience in software has been to simplify the design and use as simple as possible primitives to implement it. For this type of design event based designing is extremely valuable .  That is encouraging a discussion of what events are coming into the board and what are the outputs.  So having the ability to collect user input in a buffer via an interrupt and then process/schedule a task::loop to parse the input on a terminating  <CR> or '?' is very simple. Very simple primitives - user input collection - and the ability to schedule a task::loop. Also supports the architecture for low power processing.
Wishing everyone a nice seasonal holiday - Cheers Neil
Logged

0
Offline Offline
Edison Member
*
Karma: 64
Posts: 1638
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

neil12,

I agree with most of your observations.  Without training or close supervision of programmers, embedded systems with preemptive RTOSes get way too complex.  This is a problem with design, not the OS.

Typically 95% of an embedded system's code and execution time could run on a PC, Mac, or Linux. With that in mind  lets look at these two statements.
Quote
IMHO the value of a co-operative scheduler, is to have a simple move into multi-tasking.
Quote
The cost of the pre-emptive scheduler, IMHO, is high in terms of system complexity and maintaining stability.
Microsoft's Windows designers believed this and tried to stick with coop scheduling.  Microsoft finally introduced a minimal preemptive scheduler in Win95.  Now Mac, Linux, and Windows have preemptive schedulers for simplicity and reliability.

So I think most tasks in a mufti-threaded Arduino environment should run in coop mode or round-robin at the same priority.  I prefer round-robin because I think it's simplest since you don't need to yield.

For decades standard practice in groups I worked in was to use round-robin with a quantum that was often AC line frequency, 20 ms is still common.

Here is another interesting statement:
Quote

In a previous life with a 100 realtime software engineers, the Software VP owned the pre-emptive schedulers priorities to stop just anyone optomizing it for their functional systems.  In fact most of the processes ran at the same priority, and just the few processes that were managing the hardware redundancy and I/O had higher priorities.
Good plan.  There should be only a few task that don't run at normal priority and it is really unusual to need more than two levels above normal priority.

So why do you need a preemptive OS?  One reason is to be able to provide deterministic scheduling for a few key events, that's what distinguishes real-time systems.  

Another is to make an integrated device driver environment, so signaling between interrupt and non-interrupt routines can be abstracted in a HAL, hardware abstraction layer, with high performance drivers.  Modern chips like Cortex M are designed to get their best performance with a preemptive RTOS.

I believe a RTOS is necessary for new generation chips but the application programming environment should be as simple as possible.  

Of course embedded systems require semaphores, mutexes, messaging, queues, memory pools, and other stuff so processes can safely and efficiently cooperate.
« Last Edit: December 23, 2012, 04:37:55 pm by fat16lib » Logged

Offline Offline
Full Member
***
Karma: 0
Posts: 111
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Wow this looks promising,
Multitasking is why I left arduino, for other platforms that had integrated stable multitasking.
As you know C does not provide for multitasking, so you need to have things like Free RTOS which has compatibly issues with arduino, so thus the DuinOS was born. These are not solutions or even a good patch in my opinion, DuinOS is in Alfa and has little support. Free RTOS is like learning a new programing language, confusing and provides no real support for the 1st time user.This whole Idea of get this alfa, and download patch this and that, and maybe it will work, if you can figure it out, and doesn't crash on you is stupid. Occam-pi is another way to get multitasking out of your arduino but it's a totally new programing language with little support. In many ways I think Occam is far better programing environment then C or even RTOS at least when you learn to use it, its easy to move on to the multitasking. I sure hope you guys can work this out, but its never going to work if its not simple and fully integrated, something that I don't see happening soon.

Logged

0
Offline Offline
Edison Member
*
Karma: 64
Posts: 1638
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
I sure hope you guys can work this out, but its never going to work if its not simple and fully integrated, something that I don't see happening soon.
You are right but the Arduino company will decide what gets integrated, not users.  I expect Arduino to do something extremely simple.  Arduino users are mostly hobbyists looking for instant gratification so learning how to properly use an RTOS won't be appealing to most users.  Even a system like SCoop has too many features and is too complex.

FreeRTOS is the most popular open source RTOS with about 100,000 downloads per year.  It is a pretty typical RTOS in terms of features.  Billions of common electronic products now use systems like FreeRTOS.  Many of these products use commercial RTOSes.

Clearly a typical RTOS is not for you. 

There are lots of little open source efforts like SCoop and languages like Occam-pi.  Few of these efforts seem to be successful in the long term.

No magic tool or language will make you a good embedded system designer/programmer.  It's a lot more than a language, that's why good real-time systems engineers are highly paid and sought after.  It's a profession that takes talent, training/study, and experience.  That's why I think adding just a very few features for the simplest possible multitasking is what the Arduino company will do.  That way users won't be overwhelmed and will be have new capibilities.

FreeRTOS does run on Arduino without patches and performs well.  Support for FreeRTOS is not free and the few people that use it on Arduino don't seem to be very active in forums.
Logged

Global Moderator
Italy
Offline Offline
Brattain Member
*****
Karma: 332
Posts: 22811
Logic is my way
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I expect Arduino to do something extremely simple.  Arduino users are mostly hobbyists looking for instant gratification so learning how to properly use an RTOS won't be appealing to most users.  Even a system like SCoop has too many features and is too complex.
That's the reason why I wrote leOS, a very simple scheduler that do little jobs in background, using an interrupt-driver mechanism.
No preemptive, no cooperative... a "task" (or job, a better therm), waits until its time is reached and then the scheduler calls it. The job then runs until it has done its work and then it leaves the control back to the ISR, that terminates its work and returns the control at the main loop. A supervisor system checks if a task freezes, in such case it resets the microcontroller (useful in case your circuit runs in a place not easily accessible).

No complicated setups for the user, no complicated methods to add/modify/pause/delete jobs.
No separated editors/IDEs to use, just a simple library to include and use.


PS:
I would say a couple of words.
I followed this thread and the other ones where you, fat16lib, partecipated talking about RTOSs and I appreciated your ideas and your knowledge.
Thanks for every work you spent trying to explain us the oceans about RTOSs  smiley-sweat
« Last Edit: December 24, 2012, 02:00:54 am by leo72 » Logged


0
Offline Offline
Edison Member
*
Karma: 64
Posts: 1638
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

leo72,

I am sure efforts like leOS will work for some problems.  Maybe you have even found a Silver Bullet in the Holy Grail.

Quote
No preemptive, no cooperative... a "task" (or job, a better therm), waits until its time is reached and then the scheduler calls it. The job then runs until it has done its work and then it leaves the control back to the ISR, that terminates its work and returns the control at the main loop. A supervisor system checks if a task freezes, in such case it resets the microcontroller (useful in case your circuit runs in a place not easily accessible).

This approach is not general enough for many embedded multitasking situations.  RTOSes aren't complex unnecessarily.  Embedded systems deal with devices in ways that users of a PC, Mac, or Linux never see.

Of course simple apps don't need multitasking.  Arduino is doing fine for lots of things.  Adding multitasking to Arduino in a way that is reliable, simple, and easy for users to understand and apply will be tricky. 

Here are features that you might look for when evaluating an RTOS.  If you don't understand why an RTOS would have these things, you are not ready to write an RTOS replacement.

Quote
Abstract streams and channels
Binary semaphores
Condition variables
Core memory manager
Counting semaphores
Event flags
Hardware Abstraction Layer (HAL)
Heap allocator
I/O queues
Interrupts nesting
ISRs abstraction
Kernel base threading services
Mailboxes (message queues)
Memory pools allocator
Mutexes (priority inheritance)
Preemption
Priority based scheduling
Round robin scheduling
Static kernel
Synchronous messages
Threads registry
Timeout on wait primitives
Virtual timers
Zero latency interrupts

The question for Arduino is how much of this is needed internally to support sharing of resources and devices for multitasking and how much is presented to users in new APIs.

Every time I think about the current Arduino environment I find problems.  A coop scheduler doesn't avoid sharing problems.  If you put a yield inside existing libraries, two libraries like Enet and SD may access a shared resource like an SPI bus.  Two threads could be writing to a files and trash the SD cache.

If you add preemption or run code for String in an ISR you will trash the heap.  String uses malloc/free and these are not thread safe.

The exercise of porting ChibiOS and FreeRTOS to Arduino has opened my eyes to how primitive the current state is.  Arduino is like an old DOS system or the original MAC OS.  OS X is far away.   
Logged

Global Moderator
Italy
Offline Offline
Brattain Member
*****
Karma: 332
Posts: 22811
Logic is my way
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

fat16lib,
I undestands the problematics that relies in a RTOS and I don't want to raise me up to those coding levels  smiley-sweat

I think that an RTOS is more complex than I know but think that a "real" RTOS on a little MCU like the Atmega328 can be too complex for the normal usage too. Things like Scoop or avr-os reserve 256 byte of SRAM for each task... in a product that contains only 2048 byte of RAM. Too expensive in therms of resource consumption.

I am very very interested in such projects (Scoop, avr-os, RTuinOS, FemtoOS) but IMHO I consider them too complex for newbie users (like me...  smiley-sweat).

Thanks for your reply  smiley-wink
Logged


Offline Offline
Newbie
*
Karma: 1
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

SCoop V1.2 is out and brings lot of goodies smiley

SCoop V1 brougth the idea of easy cooperative scheduler by extensively using OOP and by providing a (hopefully) comprehensive user guide.
Several objects class like SCoopTask SCoopTimer SCoopEvent and SCoopFifo brings good support for serious but simple multitasking. With the 3 other complementary libraries (IOFilter, TimerUp&Down) this brings a set of features that makes Arduino experience even simpler

V1.2 is very much faster and brings performance close to what we get with very basic scheduler like the "Android" one provided with arduino 1.51 for Arduino DUE, but with much more features!

the yield() routine has been optimized and is now providing a mechanism to switch to next task without coming back to the main scheduler routine which saves lot of CPU time. the result is 15us total switching time on AVR and an amazing 3.2uS on Teensy 3.0 !
lets be fair, the Android version (included in SCoop pack) is still 40% faster but it does nothing else than swiching smiley

The concept of delaying yield() by several micros seconds called "quantum time" is still in place and makes a huge difference with traditional cooperative scheduler as this brings the benefit of some CPU resource allocations to tasks, and some predictability in the cycle length, like we have with preemptive RTOS. The micros() routine have been optimized for Arduino UNO (by reusing some tips from the Teensy core) and  this brings a very good 2.5us lead time to call yield() (AVR) and to check if it is time to switch or not to the nex task, so only <20% of a standard yield() which enable calling yield() everytime everywhere then.

New methods have been introduced to pause/resume timer, events or task, and to monitor their "state"

A new SCoopDelay object is introduced to rationalize timeout handling inside the library and it can be used in the main sketch (sort of simpler TimerDown)

last but not least, the SCoop pack is now provided with a copy of the standard Android Scheduler, ported for the AVR, and then compatible with both ARM or AVR platform and arduino < 1.5 (tested on 1.0.3) !
Then you have the choice : test and adopt the SCoop suite or quickly include the android scheduler.h and play multitask imediately also on AVR.

for mor details on the changes, please review the change log file as few but some important changes are NOT backward compatible with V1.1.1 including the basic defineTimer macro ...

every thing on GooGle code here:
https://code.google.com/p/arduino-scoop-cooperative-scheduler-arm-avr/

thanks for supporting us and providing your input or feedbacks

edit : change log in attachement
edit: all source code now on github : https://github.com/fabriceo/SCoop/tree/v1.2

* scoop change log.txt (8.26 KB - downloaded 55 times.)
« Last Edit: January 11, 2013, 09:36:23 am by maxidcx » Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 2
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I am sure this is a stupid question..

I have SCoop operating well, EtherMega, no issues, clean and simple install.

However, whenever I introduce a call to a subroutine from any myTask::loop (say to call a common logging routine) the code reboots.  This is not the case when subs are called from myTask::setup or from Timers.

Am I doing something wrong ;-p

rich..
Logged

Offline Offline
Newbie
*
Karma: 1
Posts: 25
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hello omegaman477
I d bet on a problem with a stack colision.

could you please try extending the size of the stack allocated to the task, say 512 and then trying again.
once it runs ok, you can reduce the size of the stack by monitoring it with the stackLeft() method.

if this doesnt work, then this might be link to the "3BYTESPC" but I would need a copy of .elf file to troubleshoot it

let me know and dont hesitate to attach or post your code, or PM if preffered
Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 2
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hello omegaman477
I d bet on a problem with a stack colision.

could you please try extending the size of the stack allocated to the task, say 512 and then trying again.
once it runs ok, you can reduce the size of the stack by monitoring it with the stackLeft() method.

if this doesnt work, then this might be link to the "3BYTESPC" but I would need a copy of .elf file to troubleshoot it

let me know and dont hesitate to attach or post your code, or PM if preffered

Increasing stack size had no effect.  Where are the ELF files located, I will IM them and the Source to you.

Thanks.
Logged

Pages: 1 [2] 3 4 5   Go Up
Jump to: