Basic scheduling question

[jnz]

I'll state up front, I've used RTOSes, I don't really love them for the small projects I usually work on. In this case, state(like) machines work better with the resources available.

I tried to explain some scheduling elements in regards to super loops and cooperative tasks to someone and realized "I didn't have words good". Which means I need help understanding a couple things myself.


1. I have a round robin, but I only want X Y and Z tasks to run every a, b, and c times. What is that exactly called? Imagine using a hardware timer or systick to make sure X runs every 50ms. In the "down time" between these tasks, I can execute a task that can run all the time like checking buffers or handling UI. This so long as deadlines are met is predeterministic.

2. If #1 has a name, does it have a good example? If you are defining a struct of tasks and their periods/timeouts, is in the timer or systick ISR a good place to do this? Or is that specifically a bad place and this is something that should be placed/checked/iterated over in the superloop itself?

3. Issues with running a void pointer to each task? Typical cooperative scheduler where tasks are called by a pointer to their function? Obviously, if it can AT ALL be avoided this works best when not using function arguments. Assign a task pointer to a function, then task(). The issue here is that conventional knowledge say be wary of void pointers. But with a small tightly defined scheduler inside main() is this benign?

4. If I wanted to sleep between tasks, is there a good way to keep track of that? For example, say I have a cooperative scheduler where I have an array of tasks and a pointer to each function they represent. Next task isn't until 100ms from now, so do I do the math, figure out what's up next, set another timer for that amount of time, then shut the CPU down? In this case I'd still need a timer running likely wouldn't want to turn systick timer off. Seems like someone figured an elegant solution for this long ago.


Stupid stuff, I know. Thanks guys.

[NorthGuy]

(1) Depending on what is the individual tasks are doing, I would classify all the multitasking schemes into 3 big groups:

A. RTOS - a task (or thread) runs freely and, in a sense, oblivious of multitasking. The OS can interrupt it at any time, run another task, then return back to yours.

B. Cooperative scheduling - a task runs freely, but cannot be interrupted and switched unless it calls a blocking function. Once such function is called the scheduler may switch to other task. The task need to make a cooperative effort by calling blocking functions from time to time. IMHO, this is the nest method for embedded applications.

C. State machine (not to be confused with formal state machines) - a task keeps track of its own state. It is called periodically, the task figures out what to do depending on its state, does the required action and then leaves (after possibly updating the state). I think what you describe in (1) falls into this category. The scheduling is so simple that everyone just writes his own.

(2) <A> and <C> usually use some sort of timer interrupt producing "ticks", although only <A> needs them while <C> can do without.

(3) <A> and <B> require some sort of context saving, so the scheduler could return back to the task. The pointer will be part of the context and you cannot do without it. <C> typically just calls tasks one after other in a "superloop", so it doesn't require pointers. You can use a scheduler for <C>, but usually it is easier to let tasks decide for themselves whether they need to do something or not.

(4) I often use WDT (watch dog timer) which allows you to put a chip into a sleep for a known amount of time, but this usually means that you lose the track of time. Otherwise, you need some sort of external clock - an oscillator, watch crystal, RTCC etc. It all depends on your hardware.

[jnz]

Ok, most of that makes a lot of sense. I guess I had always called C a "state machine" as well, but knew it wasn't a "formal" statemachine so I didn't want to explain it to someone else with me just guessing.

I'm on top of most of this, just self-taught so never got the terminology. I've been using informal statemachines, and I think it's starting to make sense to go to a cooperative scheduler as I've already learned with RTOS that my projects are really too small to need it - and that RTOS really works best when you treat each thread like a separate statemachine and not a collection of each thread for each purpose.



Quick question about Coop schedulers...

The simplest one I've seen doesn't interrupt context on blocking. It's just a null pointer directed to your functions and calls them when they need to be called. I could "improve" upon this by adding the amount of time I can sleep until the next task, and for debugging I could save some data of what just ran and what will run next, easy stuff.... But saving context... How!? In your example if I wrote some blocking scheduler delay for 10ms and the system decides another thread should run - does the context switch back after my delay or does it wait until the more recently run code has finished?

Because in the former that's a lot of context switching and no guarantee of anything predeterministic, and the latter means my blocking scheduler delay could run for longer than I had intended. Both seem like they have issues.



Does anyone have an example of a small scheduler that uses context switching? I know Nordic has something like that on their BLE ARM chips, but also iirc they have a couple hardware or softdevice hooks to make that work.

[NorthGuy]

You can look at protothreads: http://dunkels.com/adam/pt/index.html

[nctnico]

You can look at protothreads: http://dunkels.com/adam/pt/index.html

Oh, please no protothreads! A sure way to shoot yourself in the foot (*) because it is just syntactic sugarcoating.

(*) Or the one who is next to maintain the project. Code should always clearly do what is in front of you and no stuff hidden in obscure macros.

[NorthGuy]

Code should always clearly do what is in front of you and no stuff hidden in obscure macros.

How's that different from calls to obscure functions in, say, RTOS?

IMHO, if you can't or don't want to use state machines, and the real scheduler/RTOS is too big for you, protothreads do great masquerading job and use very little resources.

[jnz]

Code should always clearly do what is in front of you and no stuff hidden in obscure macros.

How's that different from calls to obscure functions in, say, RTOS?

IMHO, if you can't or don't want to use state machines, and the real scheduler/RTOS is too big for you, protothreads do great masquerading job and use very little resources.

Seems like good points, I know nctnico knows his stuff so I'll be interested if he has more info.

I looked over proto for a second, seems like a little bit of the OS obscurity I'm trying to avoid but I mostly get the idea. Cooperative schedualer with context switching is not going to be a 20 line block of code like it is without context switching. I'll see if I can just write non-blocking and re-entrant code for now. But I'll look into it more.

[nctnico]

Code should always clearly do what is in front of you and no stuff hidden in obscure macros.

How's that different from calls to obscure functions in, say, RTOS?

IMHO, if you can't or don't want to use state machines, and the real scheduler/RTOS is too big for you, protothreads do great masquerading job and use very little resources.

The big difference is that an RTOS really does something you'd expect where protothreads are just a bunch of macros to turn your code into hidden switch/case statements. Either use well commented state machines or an RTOS which can do timeslicing. Don't pour sh*t over your code which makes it unreadable for the next person working on it. Hiding complex stuff in macros makes code generally harder to understand and not easier.

[NorthGuy]

The big difference is that an RTOS really does something you'd expect where protothreads are just a bunch of macros to turn your code into hidden switch/case statements.

I don't see much distinction. In the end, everything is compiled into assembler code and whether it's done with macros, functions, or anything else, is pretty much immaterial.

Hiding complex stuff in macros makes code generally harder to understand and not easier.

I use macros a lot. I am 100% sure that macros are a powerful tool which makes working with code much easier.

I'm not an expert in protothreads and I don't use them, but as far as I can see, this is a good example how macros can simplify the code. I noticed that many people have problems thinking in terms of state machines, and protothreads use macros in rather clever way to simplify the thinking for those people.

[andyturk]

To get a feel for what was happening with protothreads, a while back I hacked together an implementation using C++ and (of course) some macro trickery. It was a good exercise, and I'd recommend it for anyone considering going the protothread route. For me, protothreads are cute, but are a leaky abstraction that probably causes more harm than good.

One of the drawbacks of the protothread idea is that you can't rely on local variables in loops. Every time the program executes something that would have been a blocking call in a real RTOS, the protothread implementation does saves some magic state and then returns from the function. For example:

Code: [Select]

PTK_BEGIN();
int i;
for(i=0; i < 10; ++i) {
  do_something();
  PTK_SLEEP(100);
}
PTK_END();

That loop index isn't going to work the way you want because PTK_SLEEP() actually causes the entire function to return, losing the contents of every local variable. I thought C++ would be a nice way to get around this because by having threads be instances of a class, I could write the same kind of code, but use member variables instead of locals. That part worked out well.

However, there's some serious macro magic going on under the covers. If you have to step into those expansions during a debugging session, you're in for some turbulence. 

On the plus side, protothreads don't create as much memory pressure as "real threads" because there's only one stack to allocate. Another interesting feature is that it's pretty easy to simulate a protothread kernel under another operating system (e.g., Unix), so you can test out your code without having to run it on an embedded system.

The biggest drawback is having to re-write your code so that it doesn't use local variables that need to persist across scheduler operations (and convincing your co-workers to do the same). Debugging protothread code can be pretty painful too. IMO, it's far worse than stepping over an RTOS call because most modern debuggers can handle stepping over a function call (even if it results in a context switch) easily. They don't handle the macro trickery that lives underneath the macro facade of protothreads.

Code: [Select]

#define PTK_LABEL_AT_LINE_HELPER(n) PTK_LINE_##n
#define PTK_LABEL_AT_LINE(n) PTK_LABEL_AT_LINE_HELPER(n)
#define PTK_HERE PTK_LABEL_AT_LINE(__LINE__)

#if defined(PTK_DEBUG)
#define PTK_DEBUG_SAVE()                            \
  file = __FILE__;                                  \
  line = __LINE__;
#else
#define PTK_DEBUG_SAVE()
#endif

#define PTK_BEGIN()                                 \
    do {                                            \
      if (continuation != 0) goto *continuation;    \
      this->timer_expiration = TIME_NEVER;          \
    } while (0)

#define PTK_YIELD()                                 \
    do {                                            \
      state = YIELDED_STATE;                        \
      continuation = &&PTK_HERE;                    \
      PTK_DEBUG_SAVE();                             \
      return;                                       \
    PTK_HERE: ;                                     \
    } while (0)

#define PTK_SLEEP(duration)                         \
    do {                                            \
      kernel.lock();                                \
      state = SLEEPING_STATE;                       \
      kernel.unschedule(*this);                     \
      kernel.arm_timer(*this, (duration));          \
      continuation = &&PTK_HERE;                    \
      PTK_DEBUG_SAVE();                             \
      kernel.unlock();                              \
      return;                                       \
    PTK_HERE: ;                                     \
    } while (0)
     
#define PTK_END()                                   \
    do {                                            \
    thread_exit:                                    \
      ptk_end();                                    \
      void *pexit = &&thread_exit;                  \
      (void) pexit;                                 \
    } while (0)

I'm with nctnico on this one.

[nctnico]

The big difference is that an RTOS really does something you'd expect where protothreads are just a bunch of macros to turn your code into hidden switch/case statements.

I don't see much distinction. In the end, everything is compiled into assembler code and whether it's done with macros, functions, or anything else, is pretty much immaterial.

It is not and Andyturk provided a good explaination why protothreads are bad. What I would like to emphasize is that code should be simple to understand and simple to maintain. Hiding functionality in a macro may make the code look simpler but it doesn't always make it easier to understand and maintain. If you use protothreads then the next person who is going to work on your code needs to have a deep understanding of protothreads as well. Chances are that that person does not and also does not have the time to learn.

[NorthGuy]

It is not and Andyturk provided a good explaination why protothreads are bad.

So, you need to declare local variables as "static". I don't know why it is so scary. While working with RTOS, you may need to declare some variables as "volatile", or you may need to use mutexes to synchronize the threads. By any account, these are more difficult to understand and use correctly than to follow a simple requirement for static local variables.

If you use protothreads then the next person who is going to work on your code needs to have a deep understanding of protothreads as well.

Let me re-phrase this a little bit for you:

If you use RTOS then the next person who is going to work on your code needs to have a deep understanding of RTOS as well.

Wouldn't anybody agree on this statement? But I don't see how such bromides can prove your point, or any point at all.

[nctnico]

You appearantly fail to see Andyturk's point: using protothreads the code doesn't do what it looks like it is doing and therefore there are several pitfalls. Remember the only thing C macros do is search & replace text.

An OS on the other hand doesn't change the way a piece of code behaves. It is just there but it doesn't interfere so unless you are setting up the OS you don't really have to know anything about what it does under the hood in order to create a program which works. Millions of people are doing that every day.

[andyturk]

So, you need to declare local variables as "static". I don't know why it is so scary.

It's scary because the number of values changes and code that "worked" using normal C sematics could break just by running it in a protothread environment.

If you write everything for protothreads from the start, you might not have a problem, but that's like using another programming language which looks like C, but isn't.

[NorthGuy]

It's scary because the number of values changes and code that "worked" using normal C sematics could break just by running it in a protothread environment.

If you write everything for protothreads from the start, you might not have a problem, but that's like using another programming language which looks like C, but isn't.

When I start a new project, I always decide how the multitasking is going to be done, which is typically some sort of state machine, then I write my tasks accordingly. Otherwise, I would have to re-write my "tasks" later. When tasks are written as state machines they're easy to put together. Moreover, you can reuse the tasks in other projects without problems.

If the things are done this way, I would never need any new multitasking tools in the middle of the project. Because my tasks already have everything needed for multitasking, I wouldn't need protothreads. Moreover, it would be impossible to apply protothreads because I already have my own state machine.

I can imagine, if I decided to use protothreads from the beginning, it wouldn't be much different in terms of the process. I would end up with every task written for protothreads, I could reuse them in different projects, it would be easy to add a new task or to remove unneeded task.

Of course, if someone already wrote a number of single-threaded tasks and wants to put them together, the situation is different. You can use protothreads, or you can use RTOS, or you can re-write the tasks for state machines. In either cases, you face extra work and you're almost guaranteed to face some sort of problems. But, in this case, a mistake has been made long before, when the programmer wrote the code for his tasks without considering multitasking.

[macboy]

...

If you use protothreads then the next person who is going to work on your code needs to have a deep understanding of protothreads as well.

Let me re-phrase this a little bit for you:

If you use RTOS then the next person who is going to work on your code needs to have a deep understanding of RTOS as well.

Wouldn't anybody agree on this statement? But I don't see how such bromides can prove your point, or any point at all.

+1 !!

You appearantly fail to see Andyturk's point: using protothreads the code doesn't do what it looks like it is doing and therefore there are several pitfalls. ...

Not so many really. It's easy to understand what they do, therefore easy to consider the ramifications each time you "block" your function.

Remember the only thing C macros do is search & replace text.

That's great. Single-step style debugging, if necessary, can then be easy with the right editor... you can simply expand the macros within the editor and compile and step through the expanded code. It's not that complicated.

An OS on the other hand doesn't change the way a piece of code behaves. It is just there but it doesn't interfere so unless you are setting up the OS you don't really have to know anything about what it does under the hood in order to create a program which works. Millions of people are doing that every day.

I agree about that but I think you fail to realise that the use cases for Protothreads vs. a full blown RTOS are at opposite extremes. Protothreads can be used even in tiny little 8 bit micros with memory literally measured in Bytes (e.g. baseline or midrange PIC). They allow a person to write up a few simple non-blocking threads with minimal effort and minimal overhead. An RTOS can be a great solution if you have a 32 bit micro with at least many KB (or better, some MB) of memory, and you need to implement a non-trivial number of non-trivial tasks. I don't think there is any overlap at all between protothreads and a full modern RTOS. If you understand your problem, you quickly understand whether each one is or is not suitable. Never both. (I'd argue that if you throw an RTOS - and the requisite hardware - at a problem that could be solved with protothreads, then you are doing it wrong).

[nctnico]

I don't care about the technical details. I care about code which can be maintained by a new hire without screwing things up or asking a million questions because what he/she wrote doesn't work as expected. As Andyturk put it so clearly: keep what looks like C code work like C code.

@Nortguy: count the number of 'I's in your last post and then think about 'there is no I in team'.