2
\$\begingroup\$

My only requirement is time triggered cooperative scheduler. I heard they are more reliable and predictable.

If I want to use only the 'cooperative scheduler' of FreeRTOS for STM32F103 then is it possible to disable its:

  • Semaphores
  • Mutexes
  • Task-preemption logic

I want to strip down FreeRTOS to a simple cooperative scheduler that uses:

  • Single stack for all tasks
  • Global variables for inter-task communication.
\$\endgroup\$
  • 10
    \$\begingroup\$ If you want tasks to communicate via global variables, and to share the same stack, do you need a schedular at all? Can't you get away with a while(1) and service your "tasks" based on elapsed time or similar? \$\endgroup\$ – Colin May 30 at 11:05
  • 2
    \$\begingroup\$ Can you please try to not repeat your spelling mistakes from your (now deleted) previous question? I've corrected them for you there, but here you go: scheduler, semaphore \$\endgroup\$ – Marcus Müller May 30 at 11:06
  • 4
    \$\begingroup\$ It's not clear from your question what you do actually want from FreeRTOS. You don't want the stuff which makes an OS useful, and you want stuff which is difficult to achieve with multiple tasks (single stack for multiple tasks?!?). \$\endgroup\$ – brhans May 30 at 11:11
  • 4
    \$\begingroup\$ @brhans has a point: The way I'd define "task" from a CPU point of view is "thing with its own stack". Writing tasks in anything but assembler that could share a stack would be nearly impossible, and a nightmare in assembler. Even more, it would be a waste: ARM Cortex-M like your STM32 have hardware support for fast and easy stack switches. These CPUs were meant to have many stacks for many tasks that might preempt each other. You really gain nothing by not using that! \$\endgroup\$ – Marcus Müller May 30 at 11:20
  • 3
    \$\begingroup\$ Also, semaphores and mutexes really usually don't need any additional code from the OS – just atomic integer operations, which ARM supports. So, again, nothing that would bring anything to disable. \$\endgroup\$ – Marcus Müller May 30 at 11:21
1
\$\begingroup\$

I write O/S software. (Often, but not continuously as my only job.) it's just part of doing embedded work and always has been. (I have a configurable O/S that I use more often than not, these days. But I don't want to go to the trouble of trying to explain all the features and how to turn them off with #define statements.)

The following points you make are the reason I'm writing:

  1. Single stack for all tasks
  2. Global variables for inter-task communication

These things tell me a lot.

One of the more important reasons for separate stacks for threads has to do with isolating and simplifying code and helping make it more maintainable. The local state of a process is retained between switches (whether or not the system is co-operative or pre-emptive.) And this is a very nice advantage. Also, a cooperative switcher is really easy to write (only a tiny bit of assembly to swap stack contexts, usually.) But you say that's not required. So I'm fine with that.

So I'll offer something extremely simple to understand, implement, and use. I've documented it in comments at the top of a source code file I used years ago and I'll let that documentation stand on its own, for now. Feel free to ask questions, though. But I don't think it is hard to follow the concepts applied here. Note that this particular implementation (the code I drew this from) was targeting a SiLabs C8051F061, which is effectively just an 8051 core processor. So any comments about specific instructions are referring to it. Just so you know.

DESCRIPTION

This module provides the operating system for calling functions at timed
points in the measurement cycle.  It uses a delta-queue implementation for
a low overhead interrupt routine.


CIRCULAR LIST DESIGN

This module uses a short, singly-linked list to maintain a circular list.
Every slot in the list is in one of three queues:

    *   the "avail" list of slots that can be used to add a new
        function to be called later;

    *   the "sleep" list of functions that are still waiting for
        their time to come; and,

    *   the "ready" list of functions that have timed out but
        have not yet been executed.

Three queue head pointers are included to reference the first entry of
their particular queue.  All linked entries in the chain, starting at the
node indicated by the queue-head and following the next node pointer list
one after another until the first entry of the adjacent queue is seen,
belong to that queue.  If two adjacent queue heads reference the same
entry, then the "prior" queue is considered to be empty (there is an
exception noted later.)

Examine the following diagram.


    Sleep --------------------------------->  -> [] -> [] -> [] -,
                                             /                   |
    Ready ------------->  -> [] -> [] -> [] -                    |
                         /                                       |
    Avail ---> [] -> [] -                                        |
                                                                 |
               ^                                                 |
               |                                                 |
               '_________________________________________________'

The ready queue is "prior" to the sleep queue, the sleep queue is "prior"
to the avail queue, and the avail queue is prior to the ready queue.  This
concept is very much like the scissors-paper-rock game.  So if both the
sleep queue and ready queue head pointers reference the same node, then it
is the ready queue that is empty, since the ready queue is "prior" to the
sleep queue.

The queue head pointers advance in only one direction.

The avail queue head is advanced forward when an entry is inserted into
the sleep queue.  The effect of advancing the avail queue head is to both
remove an entry from the avail queue and add an entry to the sleep queue.

The ready queue head is advanced when a function that is ready to execute
is executed and should be removed from the ready queue.  The effect of
advancing the ready queue head is to both remove an entry from the ready
queue and add an entry to the avail queue.

The sleep queue head is advanced when a sleeping function times-out and
becomes ready to run.  The effect of advancing the sleep queue head is to
both remove an entry from the sleep queue and to add an entry to the ready
queue.

That represents the only three operations permitted.  The only case where
node entries may be re-ordered, though, is during insertion.  The other
two cases never need to re-order entries within a queue, but only advance
queue head pointers, instead.

So it is illegal to move an entry from the sleep queue to the avail queue
by backing up the avail queue's head.  Such an entry must first be moved
from the sleep queue to the ready queue and then from the ready queue to
the avail queue.  All nodes must move through the queues in this fashion.

Let's now examine the possible "states" of the three queues to point out
one more design issue.  Each queue may be either empty or not empty.  With
three queues, this leads to eight states.  The following table shows the
different combinations and compares the associated "head" pointers for the
queues with each other.  I've used a (+) to indicate a non-empty queue and
a (-) to indicate an empty one.


    Sleep  Ready  Avail  Pointer conditions   Description of condition
    --------------------------------------------------------------------

      -      -      -     A==R, R==S, S==A    Meaningless
      +      -      -     A==R, R==S, S==A    All slots are sleeping
      -      +      -     A==R, R==S, S==A    All slots are ready to run
      -      -      +     A==R, R==S, S==A    All slots are available
      -      +      +     A<>R, R<>S, S==A    No slots are sleeping
      +      -      +     A<>R, R==S, S<>A    No slots are ready to run
      +      +      -     A==R, R<>S, S<>A    No slots available
      +      +      +     A<>R, R<>S, S<>A    No empty queues


As you can see, four of the states are indistinguishable from each other
if the only thing you do is compare pointers.  This problem can easily be
resolved by insisting that the avail queue never be allowed to become
empty (a simpler choice than keeping either of the other two queues non-
empty.)  With that assertion made, we can conclude that when the three
queue head-pointers are equal to each other, the avail queue is full and
the other two queues are empty.


SLEEP QUEUE TIMER DESIGN

The sleep queue is handled as a delta-queue, so that the timer event only
needs to decrement the time for a single entry.  Each waiting function in
the sleep queue maintains a "delta" value which contains the number of
timer ticks required _after_ the preceding function in the sleep queue.
Doing recording only deltas, only the first entry on the sleep queue needs
to be examined by the timer event when counting time and deciding if the
function has timed out and needs to be moved to the ready queue.

This means that when inserting a function into the sleep queue, the time
delay initially given must be reduced by the time counts in all earlier,
waiting functions.  That's the stored value for that function.  Then the
function that follows this newly inserted function must also have it's
delta time adjusted for the remaining delay of the newly inserted one.

So if there were three functions, f1, f2, and f3, waiting for 1000, 1500,
and 2700 timer ticks to pass by then their delay counts would be set to
1000, 500, and 1200, respectively.  The timer would examine only the first
entry's value of 1000, counting it down to zero eventually, and then move
it to the ready queue.  In doing so, there would only be two more entries,
with 500 and 1200.  Then the 500 would count down.  When it did, a total
of 1500 counts would have occurred (1000 for the first function and now
another 500.)  Etc.

To keep things slightly faster still, a special variable called 'quantum'
holds the counter value for the first sleeping function.  So the value of
its remaining time is always in 'quantum' and not in the associated timer
for the node.  (It's copied from there when the sleep queue advances.)


FUNCTIONAL DESIGN

Aside from the init routine, there are three additional functions that
operate the queue system:

    dqueue_insert()     This function inserts functions at the
        appropriate point in the sleep queue.  This function is
        more complex and costs more to execute, since the list
        is singly-linked.  Besides, it must re-start the timer
        if the sleep queue emptied, earlier.

        Updates availq (and quantum, sometimes.)

    dqueue_execute()    This function empties out the ready queue
        when called.  All functions ready to run are executed once
        in a single event and the ready queue is always emptied.

        Updates readyq.

    dqueue_ISR()        This function times the currently waiting
        function and, if it times out, moves it from the sleep
        queue to the ready queue.  If more than one function
        becomes ready at one time, all those ready are moved at
        once so that either the sleep queue empties completely or
        else a waiting function with time remaining becomes the
        current one in the sleep queue.

        Updates sleepq (and quantum.)

The dqueue_init() function can be used to re-initialize the system while
it is operating.

Worthy of note is that the basic responsibility for each of the pointers
is divided neatly between the three different routines.  The insert
routine does NOT modify readyq or sleepq and it shouldn't.  The execute
routine does NOT modify availq or sleepq and it shouldn't.  The ISR event
does NOT modify availq or readyq and it shouldn't.  Each routine has clear
responsibilities and can depend upon the fact that only they are allowed
to change their respective queue pointers.

As you can see, this really isn't complicated. You can set up how many "avail" slots you require. It's fixed, doesn't change, and doesn't require the use of heap space. Just a fixed, global memory array. The queue holds the address pointer to a function that can be invoked. Only the top of the sleep queue gets a "decrement", so you don't have to worry about other sleeping processes. Once the top of the sleep queue counts down to zero, all functions in the sleep queue are moved to the run queue by a some movement of just one pointer. And then they are run, in-order, until the run queue is empty and the slots are moved back into the avail queue -- again by nothing more than a simple change of a single variable in global memory. The design is bullet-proof and has been used on a number of commercial products which have millions of instrument-years of operation behind them without a single reported bug. It just works.

And it is simple.

\$\endgroup\$
  • \$\begingroup\$ Can you tell how to write a "Cooperative Task Switcher", in C? \$\endgroup\$ – alt-rose May 31 at 7:02
  • 1
    \$\begingroup\$ @alt-rose You need a little bit of code to create some stack space (heap, static, or splitting up the existing single stack.) With that in hand, you need a way to create a process -- which mostly just stores some register info in a structure. Then you need a "switch()" function call. If round-robin is okay for you then you don't need to embellish further. Calling "switch()" just saves the important registers and the SP in the current proc structure and then loads the SP and important registers from the next proc structure and returns. It returns in the context of that next process. \$\endgroup\$ – jonk May 31 at 7:10
  • \$\begingroup\$ Stack switching is same as Task switching or they are different aspects of programing? \$\endgroup\$ – alt-rose May 31 at 7:18
  • \$\begingroup\$ @alt-rose A task is essentially what used to be called a "co-routine" decades back. Just switching stacks is only "switching contexts" between what are (by me, anyway) called "threads." A thread shares the same lifetime static variable space with other threads, but each retains a separate stack context. But a thread is not a task. (Not the way I teach these things, anyway.) So stack switching isn't to me the same as task switching. \$\endgroup\$ – jonk May 31 at 7:21
  • \$\begingroup\$ For a 32-bits ARM Cortex processor as STM32F103 or STM32F407 do they have separate physical memory spaces for TASK STACKS or do they use some x-amount of main SRAM memory for creating STACK instances? \$\endgroup\$ – alt-rose May 31 at 7:23
1
\$\begingroup\$

I actually wrote a very basic (minimalistic for sure) scheduler a few years back that has no reliance on an OS, just needs a timer interrupt to mark the passage of one millisecond at a time. Here's an article I wrote about it: https://shop.wickeddevice.com/2014/12/22/wildfire-lightweight-periodic-task-scheduler/. It would be super easy (trivial even) to port it to an ARM (from AVR). Tasks are defined apriori in an array of structs like this:

typedef struct {
  volatile uint16_t task_timer;
  uint16_t task_period;
  void (*task)(void);
} task_t;

The member variable task is the function you want called. The member variable task_period is how often you want to call it in milliseconds, and the task_timer variable is counted down to zero in order to determine when next to call task.

The basic 'Arduino-style' pattern looks something like this:

void setup(){
  initializeScheduler();
}

void loop(){
  executeTasks();
}

For posterity, here is the code from the linked article:

#include <avr/interrupt.h>
#include <util/atomic.h>

typedef struct {
  volatile uint16_t task_timer;
  uint16_t task_period;
  void (*task)(void);
} task_t;

////////////////////////////////////////////////////////////////////
//                                                                //
// define NUM_TASKS to be >= the actual number of tasks defined!  //
//                                                                //
////////////////////////////////////////////////////////////////////

#define NUM_TASKS (4)
task_t tasks[NUM_TASKS] = {0};

void initializeScheduler(){
  /////////////////////////////////////////////////////////////////////////////
  //                                                                         //
  // statically set up the tasks here, e.g.:                                 //
  // tasks[0].task_period = 500;   // execute once every 500ms (technically  //
  //                               // "no more frequantly than every 500ms") //
  // tasks[0].task = &exampleTask; // call the function exampleTask          //
  //                                                                         //
  /////////////////////////////////////////////////////////////////////////////

  TCCR3B = _BV(WGM32) | _BV(CS31) | _BV(CS30); // prescaler=64, enable CTC mode
  OCR3A = 250;                                 // compare match every 250 ticks
  TIMSK3 = _BV(OCIE3A);                        // enable compare match ISR
}

// initializeScheduler sets this ISR up to fire once per millisecond
ISR(TIMER3_COMPA_vect){
  for(uint8_t ii = 0; ii < NUM_TASKS; ii++){
    if(tasks[ii].task_timer > 0) tasks[ii].task_timer--;
  }
}

// call this from loop()
void executeTasks(){
  for(uint8_t ii = 0; ii < NUM_TASKS; ii++){
    if(tasks[ii].task != 0){
      if(tasks[ii].task_timer == 0){
        tasks[ii].task();
        ATOMIC_BLOCK(ATOMIC_RESTORESTATE){
          tasks[ii].task_timer = tasks[ii].task_period;
        }
      }
    }
  }
}

// task functions must take no arguments, e.g.
// void exampleTask(){
//  static uint8_t x = 0;
//  x ^= 1;
//  digitalWrite(A6, x);
// }
```
\$\endgroup\$
  • 1
    \$\begingroup\$ In my classes I use something very similar, for Cortex-M. It can be found at github.com/wovo/rtos . It provides both basic coroutines and task switching, and a cooperative rtos/scheduler on top of that. A IFAIK unique fetaure is that a task can wait only any combination of timers, closk, flags, and channels (=queues). \$\endgroup\$ – Wouter van Ooijen May 30 at 15:17
0
\$\begingroup\$

So, disabling features won't turn a general RTOS scheduler into a time-triggered scheduling algorithm.

Therefore, none of the things you ask are suited to achieve your goal.

Also, while in literature strictly time-slicing schedulers are easy to reason about, that's not necessarily the case in the real world:

That scheduling approach assumes there's no variability in the time you give a certain task to fulfill its role, and hence, you also assume that there's no hardware interrupts preempting tasks. This is not true for microcontrollers!

So, you ask for something that doesn't help you getting a system that doesn't work.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.