Page 1 of 1

Programming state machines with Salvo

PostPosted: Fri Sep 27, 2002 6:08 am
by interested
Came across your products while searching for a RTOS to run on PIC 18 device. We have read much of the information you publish and believe to understand your products at a rudimentary level.

Our question relates to programming of state machines. That is, we are used to writing all of our embedded software in the classical state machine model and state transition diagrams. How would you implement this approach with Salvo.

To us, a task typically consists of many states with several possible transitions. A task can only be in one state at any given time. For each state we define an entry function, an action function, and one or more transition test functions. The state themselves signal to the task engine (part of a cooperative multitasking scheduler) when a transition to the next state has occured.

Having only a basic understanding of how your product works, it seems that one would have to have all state function waiting for their "number to be up", that is, they are waiting for their state to be the valid state for a task. The state function would then run and when a transition becomes valid, it would then signal which state is next and go back to waiting. Does this make sense? Are we barking up the wrong tree?

Thanks for your help. Your product does look very promising.


Re: Programming state machines with Salvo

PostPosted: Fri Sep 27, 2002 6:57 am
by aek
Hello.

State machines can "peacefully coexist" within a Salvo application. By that I mean that rather than have one large and complex state machine, you could have multiple state machines, each one associated with a single task. Using Salvo, you could then end up with a system that has multiple, concurrent state machines, and priorities associated with the individual state machines.

So a rudimentary state-machine-in-a-task might look like:

code:
void SM1_Task ( void )
{
/* initialize this SM */

while (1) {
switch (state) {
case SM1_STATE_1:
/* do stuff, including context-switches */
/* transition to next state */
break;
case SM2_STATE_2:
/* etc. */
break;
default:
/* unknown state */
break;
}
OS_Yield(); // return to scheduler
}
}


quote:
The state themselves signal to the task engine (part of a cooperative multitasking scheduler) when a transition to the next state has occured.
This is implemented with OS_Yield().

This method outlined above would be a "direct port" of your state machine approach to a Salvo multitasking application. Since you understand state machines very well, this might be the best (first) application of Salvo for you.

What it (the method above) does not do is take advantage of Salvo's event-driven approach. I.e. the state machines will be (most likely) always running. To have two or more state machine tasks, you would have to run them at the same priority.

An approach that would work better with Salvo, and from which you would begin to gain the benefits of Salvo, would be to have the various state machine tasks and state machine transitions be triggered by events. E.g. you might have a state machine that does X, but only occasionally. It would wait to start (e.g. by waiting on a binary semaphore), would then run, and when finished, would return to the waiting state, waiting for it to be "triggered" again. The Salvo benefit here is that while that state machine is not running, it consumes 0 processor cycles (i.e. there is absolutely no polling going on).

As you may have read in the documentation, Salvo follows two "golden rules" with regard to context-switching:

1) Every task must contain at least one context switch, and

2) Context-switches may only occur at the task level.

(This is how Salvo has such minimal RAM requirements).

So, for the scheduler to switch between tasks / state machine tasks, the context-switch must occur at the task level. But the state machines themselves can be as complex as you want -- it's just that control cannot pass to another, different state machine except from the "top level" of the state machine task. Therefore you can do things like delay a state machine (using OS_Delay() as long as you write the state machine such that the call to OS_Delay() occurs in the state machine task itself (i.e. not in a function called by the state machine task). Salvo services that do not contain "OS_" (e.g. OSSignalBinSem()) can be called from any level.

I hope this answered your (initial) questions. I'd be happy to discuss it further ... one thing that would help is for me to know what benefits you hope to gain / what problems you hope to solve by adding Salvo to your existing coding methodology.

Regards,

------------------


Re: Programming state machines with Salvo

PostPosted: Fri Sep 27, 2002 7:00 am
by aek
I wrote:
quote:
To have two or more state machine tasks, you would have to run them at the same priority.
By this I mean that if your only context switches are via OS_Yield(), all of the state machine tasks must run at the same priority (otherwise the highest-priority one always runs, and the others never do).

However, if you use other context-switchers, like OS_Delay() and OS_WaitXyz(), then you can use task priorities, since then there will be tasks that are delayed or waiting, during which time other eligible tasks can run.

Also, there are "minimal" Salvo libraries (the "m"-configuration ones) which support multitasking only with no priorities. These would be the ideal ones to use with multiple, same-priority state machine tasks.

------------------


Re: Programming state machines with Salvo

PostPosted: Fri Sep 27, 2002 8:06 am
by interested
Thanks for your quick reply. Your comments reflect pretty much what we thought to be the case.

We certainly agree that using Salvo to simply provide a mechanism to call the various state machines in a round robin fashion would seem to be a somewhat inappropriate use of Salvo. What we are hoping to gain from using Salvo is that we only expend processing power on tasks that actually are doing something, which you confirm Salvo does.

We don't really want to implement a state machine engine like your example code. We want a kernel that does something like it.

What we would like to preserve is the way that one state can transition to any other state very easily and that the transitions can be re-routed without having to re-write any code (except for the pointer to the next state entry function). In the same vein, it is very convenient to be able to insert new states at any point.

Currently, our state machine engine constantly scans the currently valid state for any transitions, even if the state is not really doing anything (other than checking for state transitions). This is clearly not the best way to maximize processor power. We would rather have the state simply "wait" for the next transition and tell the kernel to switch to the next state. Of course, we always have multiple state machines running.

I think it's this "transition to the next state" that we can't seem to reconcile with Salvo.

[This message has been edited by interested (edited September 27, 2002).]


Re: Programming state machines with Salvo

PostPosted: Fri Sep 27, 2002 8:54 am
by aek
Hello.

Note for this discussion. Salvo Lite has all of the functionality of Salvo LE and Pro, so you should be able to test anything we discuss here with Salvo Lite, assuming it does not require "extending" Salvo.

OK, I think I see the picture. So how about this approach:

Each state machine has a single task (and therefore priority) associated with it. Each state machine (SM) task looks like this:

code:
void SM1_task (void )
{
typeMySMStruct mySMStruct;
OStypeMsgP msgP;
/* init SM1 */

while (1) {
OS_WaitMsg(..., msgP, ...);
mySMstruct = (appropriate cast) msgP;

mySMStruct.fnP();
or
switch ( mySMStruct.state ) {
case SM1_STATE1:
SM1_STATE1_FN();
etc.
}
}
}


where typeMySMStruct is a struct that contains information for state machines, e.g. function pointers, states, etc. Basically the task waits for the message (or any other event, I just chose messages here) to be signaled, then runs that state, and then reverts to waiting for a transition. If one has already been specified (e.g. at the end of the current state), then it will run the next state as long as this SM task is the highest-priority eligible task.

So the idea here is that each state machine has a "stub" that's waiting to run the function associated with a particular state. Only it's completely general ... what you do is signal a message that contains information on the next state to run, e.g. a state number or a function pointer. In the case above we've used a struct that can contain any amount of data ...

You would probably associate each message with a particular SM task. Then, when you want that SM to run / when that SM transitions, you call OSSignalMsg() from anywhere in your code, and as an argument you pass a properly initialized struct that has the next transition in it.

The benefit of all this is that state transitions become events (a transition includes a call to OSSignalMsg()), and so you don't spend any time polling. You could also use, say, binSems instead, where a transition always means that newState = oldState+1, etc.

The bottom line is that you decide what sort of information accompanies the signalling of an event. You can make this as simple (state++) or as complex (state = stata_i) as you want.

You can signal events from foreground (ISR) or background (mainline, task, etc.) code.

I guess as system complexity grows, you will begin to see the benefit of the event-based approach. But keep in mind that the act of signaling and trips through the scheduler do take more cycles than simply polling a bit or byte. But if you need / want priorities, and your system is normally spending a lot of time polling for state transitions that do not happen, then you'll benefit from Salvo.

Also note that as a byproduct, you could easily have other tasks that are not SM tasks -- with appropriate priorities, etc. they can do other, somewhat "orthogonal" things in your system.

They key thing to realize is that the RTOS approach is very loosely-coupled, whereas the state machine and superloop approaches are very tightly-coupled. The SM tasks above are loosely coupled from a system point of view (because of waiting, priorities, and the presence of other tasks in the system), but their own behavior is very tightly coupled because they remain state machines.

------------------


Re: Programming state machines with Salvo

PostPosted: Mon Sep 30, 2002 3:35 am
by interested
Thanks, AEK. We understand your reply and appreciate your suggestions. We'll give your freeware version a try and do some preformance testing. It seems like having a single task performing the state machine engine function at a relatively low priority should give us what we want.

Re: Programming state machines with Salvo

PostPosted: Tue Jul 07, 2009 8:17 am
by tbims23822
www.drop-shopping.com is a premium website for cheap air jordans shoes and other more really nike air jordan shoes.We have varity of cheap air jordan shoes available for wholesale.Cheap China wholesale shoes including cheap Nike shoes and cheap jordan shoes,nike sneakers,nike sneakers discount,air jordan sneakers,air force sneakers.We supply nike sneakers,jordan sneakers,air jordan sneakers,air force sneakers wholesale.You can buy very cheap jordans shoes including cheap women shoes,cheap nike shoes,cheap running shoes from us.