AVR-Chat

--- In AVR-Chat@yahoogroups.com, "Dave Hylands" <dhylands@b...> wrote:

> ... So, in an RTOS, the highest
> priority ready-to-run thread
> is always running...

This and the rest of your explanation applies to preemptive systems.

As there seems to be no objection to the direction this discussion 
thread is taking, perhaps I could state an opinion that preemption is 
frequently overkill and people who have not already learned an RTOS 
should consider cooperative systems.

Although the highest priority task cannot run until the currently 
running task voluntarily gives up the CPU, this is often perfectly 
acceptable. You just have to make sure all your tasks yield often 
enough for the high priority tasks to meet their deadlines. You can 
even use modified MRA to estimate schedulability.

The benefits of a cooperative system, such as ECROS, are:
*** no need for a stack per task, i.e. more tasks in less RAM
*** no special debugger awareness needed
*** none of the hard-to-learn task synchronizing stuff like 
semaphores, mutexes, critical sections, etc.
*** no need to protect shared data structures (except those shared 
with interrupts)

So, basically, you get something that is much easier to learn and use 
and is, in many cases, just as good as a preemptive RTOS. If 
something has to get done on a tight schedule, it's often possible to 
do it in an interrupt. Anyway, a cooperative RTOS beats the heck out 
of designing your own super-loop (unless you're really squeezed for 
resources). I think many people who use a super-loop do so because a 
preemptive RTOS is hard to learn to use safely and don't realize the 
cooperative RTOS is a third possibility.

Graham.

Hi Dave,

I don't know about AvrX, but most RTOS systems have a "ready" queue. At
each timer tick, or logical yield point (like giving a semaphore, or
when one thread blocks), the OS starts running the first entry on the
ready queue. The ready queue is normally maintained in priority order.
There's always an idle thread which does nothing and is always ready to
run.

The OS itself doesn't really do polling. Obviously, supporting devices
which don't generate interrupts would require some type of timer based
polling.

So, in an RTOS, the highest priority ready-to-run thread is always
running. Context switches occur whenever something causes a higher
priority blocked thread to become ready-to-run (say it's waiting on a
semaphore and a lower priority thread signals the semaphore). The timer
tick is used to round-robin equal priority threads.

For a UART, some thread is typically waiting for data, blocked on a
sempahore. The UART interrupt hanlder will detect that a new character
has arrived, stuff it in a queue and signal the semaphore, which may in
turn cause it to run (this is where the context switch would happen if
the thread which was waiting for a character from the UART is higher
priority than the currently running thread).

--
Dave Hylands
Vancouver, BC, Canada
http://www.DaveHylands.com/ 

> -----Original Message-----
> From: Dave VanHorn [mailto:dvanhorn@dvanhorn.org] 
> Sent: Tuesday, September 07, 2004 10:25 AM
> To: AVR-Chat@yahoogroups.com; AVR-Chat@yahoogroups.com
> Subject: RE: [AVR-Chat] Re: Teenagers should write code.
> 
> 
> 
> >
> >In your example, below, things that don't generate 
> interrupts need to be
> >polled.  There is no way to get around that.  In AvrX the 
> way to handle that
> >is  to put a little code into the timer interrupt handler 
> that generates the
> >"handshake" event when state changes and then have the task 
> wait on the
> >handshake event.
> 
> Ok, so the timer isr would then be doing the polling, 
> effectively, right?
> 
> As I understand it, you would do the status bit checking 
> during the timer int, and say "task 6 and task 8 are ready to 
> run", and I would assume, put their addresses on the stack in 
> reverse order? (or something like that)

--- In AVR-Chat@yahoogroups.com, Robert Adsett <subscriptions@a...> 
wrote:

> >The benefits of a cooperative system, such as ECROS, are:
> >*** no need for a stack per task, i.e. more tasks in less RAM
> 
> I don't understand this assertion ...

This is a great discussion thread. I confess I have not previously 
thought at length about differentiating cooperative kernels that can 
yield at arbitrary points versus those that require a function to run 
to completion. Mea Cupla. I agree with everything you said. In my 
defence, I did say "such as ECROS" and ECROS is of the run-to-
completion type. This is better for some applications and worse for 
others as compared to yielding at an arbitrary point. I think it does 
take the prize for ease-of-use and suitability to machines with very 
limited resources, though. By rebinding the task function at run time 
you can get very elegant state machine implementations which are not 
possible when you yield in the middle of the task. But, sending more 
text to the UART than can be buffered at any one time is easier if 
you can yield after each chunk.

So perhaps we have these approaches to real-time system design, in 
ascending order of sophistication/complexity/resource needs:

* ad-hoc
* super-loop
* cooperative run-to-completion RTOS
* cooperative yield-when-I-want-tp RTOS
* preemptive RTOS

Graham.

At 07:14 PM 9/7/04 +0000, you wrote:
>Although the highest priority task cannot run until the currently
>running task voluntarily gives up the CPU, this is often perfectly
>acceptable. You just have to make sure all your tasks yield often
>enough for the high priority tasks to meet their deadlines. You can
>even use modified MRA to estimate schedulability.
>
>The benefits of a cooperative system, such as ECROS, are:
>*** no need for a stack per task, i.e. more tasks in less RAM

I don't understand this assertion.  The co-operative multitasking I've 
worked with required a stack per task.  A run-to-completion system wouldn't 
and I can see that being described as a subset of co-operative multitasking 
(or a superset of loop of loops for that matter).

Given a co-operative function to give up control called yield() and the 
three tasks below I don't see how you could get away with a single 
stack.  Also feel free to visualize code around what's illustrated doing 
all sorts of useful stuff and local variables taking up stack space ;)

taska()
{
taska_fn1();
taska_fn2();
taska_fn3();
}

taska_fn1()
{
yield();
}

taska_fn2()
{
yield();
taska_fn4();
yield();
}

taska_fn3()
{
yield();
}

taska_fn4()
{
yield();
}

taskb()
{
taskb_fn1();
taskb_fn2();
taskb_fn3();
}

taskb_fn1()
{
yield();
}

taskb_fn2()
{
yield();
taskb_fn4();
yield();
}

taskb_fn3()
{
yield();
}

taskb_fn4()
{
yield();
}

taskc()
{
taskc_fn1();
taskc_fn2();
taskc_fn3();
}

taskc_fn1()
{
yield();
}

taskc_fn2()
{
yield();
taskc_fn4();
yield();
}

taskc_fn3()
{
yield();
}

taskc_fn4()
{
yield();
}

>*** no special debugger awareness needed

Oh, I don't know I've seen debuggers get confused in co-op systems when the 
stack switched.  However, not having the task switch willy-nilly on you is 
a great simplification.

>*** none of the hard-to-learn task synchronizing stuff like
>semaphores, mutexes, critical sections, etc.
>*** no need to protect shared data structures (except those shared
>with interrupts)

Again, I think it depends on the system.  The synchronizing primitives just 
don't need to protect against as much.  For instance a pipe between two 
cooperative tasks is quite useful.  I've certainly seen error in a co-op 
system where a structure should have been updated in an atomic fashion but 
an implicit yield occurred due to an OS call that caused the stack to 
switch to the consumer of the structure before the update was finished.

Robert

" 'Freedom' has no meaning of itself.  There are always restrictions,
be they legal, genetic, or physical.  If you don't believe me, try to
chew a radio signal. "

                         Kelvin Throop, III

At 10:38 PM 9/7/04 +0000, you wrote:
>So perhaps we have these approaches to real-time system design, in
>ascending order of sophistication/complexity/resource needs:
>
>* ad-hoc
>* super-loop
>* cooperative run-to-completion RTOS
>* cooperative yield-when-I-want-tp RTOS
>* preemptive RTOS

Pretty good summary and order.  I also notice that a number of the higher 
order approaches can include the lower order processes (either as a subset 
or an explicit task within a task).

Might be a good organization for a tutorial :)

Robert

" 'Freedom' has no meaning of itself.  There are always restrictions,
be they legal, genetic, or physical.  If you don't believe me, try to
chew a radio signal. "

                         Kelvin Throop, III

and we have this freeware...

http://www.avrfreaks.net/Freaks/freakshow.php?keyword_is_id=1&keywords=230