Rtos Design

pachu <pachu_um@hotmail.com> wrote:

> No the algorithm for the scheduler is not an issue right
> now(cooperative or round robin or priority).......the problem is,
> allocating the stack area for each task.

You have no idea.  The type of scheduler very much is the issue here,
because if you chose the appropriate class of scheduling method for
this target platform, you wouldn't need any per-task stacks to begin
with.

The need for stack switching is a property of pre-emptive scheduling,
which simply isn't an appropriate scheduling technique for a classic
8051.

You can do it on some extended variants, though.  E.g. I'm working on
the DS80C390, whose 1KiB "internal XRAM" can be set up as 4
independent stacks quite nicely, each of them still being larger than
a classic 8051's stack.  But then, a '390 in 24 bit contiguous mode is
far from what people will think of hearing you speak of just "8051",
without further specification, so it's actually outside the stated
scope of your RTOS design.

And since you mentioned Keil tools already: even setting aside whether
an RTOS is a useful idea on an 8051 to begin with, it evades me why
would want to design your own RTOS instead of using existing ones,
including Keil's own RTX51.

-- 
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

On 6 Sep 2004 10:49:37 GMT, Hans-Bernhard Broeker
<broeker@physik.rwth-aachen.de> wrote:

>pachu <pachu_um@hotmail.com> wrote:
>
>> No the algorithm for the schedular is not an issue right
>> now(cooperative or round robin or priority).......the problem is,
>> allocating the stack area for each task.
>
>You have no idea.  The type of scheduler very much is the issue here,
>because if you chose the appropriate clase of scheduling method for
>this target platform, you wouldn't need any per-task stacks to begin
>with.
>
>The need for stack switching is a property of pre-emptive scheduling,

No, this isn't strictly true and it suggests you don't have a clear mental
model.

Pre-emptive scheduling can even be performed on CPUs that don't even support
stacks in their hardware architecture, such as the HP-2116 from the days of the
late 1960's and early 1970's, for example.  So it cannot be that stack switching
is a __property__ of pre-emptive scheduling.  In cases where there is no stack
at all, such as in the case of the HP-2116, it is only required that all of the
state get saved away and restored.  This doesn't necessitate stacks.  In the
case of the HP-2116, it involved extracting all of the first words of every
callable subroutine and saving those away.  Painful, yes.  But requiring a stack
architecture?  Not at all.

What pre-emptive scheduling requires is the ability to identify and preserve all
of the important state for an interrupted process in a fashion that will later
permit returning to it without having disturbed its progress.  The special
characteristic of pre-emption in all this is that the interrupted process does
NOT cooperate -- and this usually means that the amount of state that is
considered 'important' is larger than it would be, with cooperation.

In the presence of C compilers, the requirement of 'pre-emption' is usually even
greater, because there may be important state held in the static state of the
library system.  I've often encountered the case where floating point libraries
use static state in their computations and where this state *must* be preserved
when pre-emption is in play.

But switching stacks is NOT a property of pre-emption, precisely speaking.  It
just often is because is because it is a very efficient way, on most processors
supporting stacks, of preserving and restoring important process state.  The key
note here is *efficient*.  It would be perfectly possible to completely save all
of the ONLY stack, through copying to memory in an external per-process block,
for example.  But that would probably be very inefficient so that is one of the
reasons why it isn't often done.

And more, switching stacks is just as much a property (if one wants to argue
less precisely) in the case of cooperative, non-pre-emptive switching as it is
of pre-emptive.  Cooperative tasks are just as often implemented by switching
stacks, in my experience, if for no other reason than simply because all of the
same arguments that would press for separate stacks in the case of pre-emption
would similarly argue for them in the case of cooperative.  The main difference
in the two is the amount of important state.

(Assuming, of course, that pre-emption is even fully supported by the CPU
hardware/software environment.  And that isn't always a given.  For example, in
the case of MSP-430 microcontrollers supporting the hardware multiplier like the
MSP430F149, there is no way to be certain of saving and restoring the temporary
state of the multiplier in the face of pre-emption.  As a result of this
limitation, all use of the multiplier must either be wrapped by an
enable/disable prologue/epilogue or else pre-emption support cannot be
guaranteed.  Luckily, the C compiler vendors do this and anyone writing in
assembly needs to be certain to keep it in mind when they write their code.)

>which simply isn't an appropriate scheduling technique for a classic
>8051.

Well, I don't see a reason why pre-emption cannot be supported in the 8051.  The
hardware stack pointer *IS* limited to 256 bytes or 128 bytes (less room
required for registers, etc), depending on the processor (x51 versus x52, for
example.)  But placing software parameter stacks in external memory is perfectly
feasible.  And even if it weren't, I've done pre-emptive systems with small
numbers of processes on CPUs with less than 128 bytes of total RAM.  So I know
that declaring all such things as out-of-bounds for pre-emption is wrong-minded.
I understand why you imagine it isn't appropriate, but it's not always the case
you suggest here.

Jon

On 6 Sep 2004 09:01:36 GMT, Hans-Bernhard Broeker
<broeker@physik.rwth-aachen.de> wrote:

>And you're sure you know what you're doing?  To be perfectly frank,
>that doesn't really appear to be the case.

I agree.  Perhaps it's just for personal edification.

Jon

On Sat, 04 Sep 2004 21:30:27 +0100, ruffrecords
<ruffrecords@yahoo.com> wrote:

>> pachu wrote:
>> 
>>>        We were designing an RTOS for a general 8 bit microcontroller. 
>>> We have designed a round robin schedular.
>>>
>>> But i have question about the stack on 8051.
>>>
>>> My doubt is, we have our kernel (data, code) and also applications
>>> (data and code)
>>>
>>> Now we need to allocate seperate memory areas for the kernel and the
>>> application. How do we take care of the security in 8051.
>> 
>>> And also how do we give the stack area for each task in the
>>> application.
>>> Is if a good idea to give around 40 bytes for each task (IDATA
>>> memory). And when a new task is scheduled, save the current task 40
>>> bytes in external memory and reload the new tasks 40 bytes from
>>> external memory to IDATA. Somehow i dont like this idea, but are there
>>> any other ways to save the context of a task.
>> 
>>> Also how to achieve atomic operations in 8051.. (disable interrupts
>>> ????)
>> 
>
>Here is a completely different viewpoint.  An 8051 is so short of 
>resources that creating a general purpose RTOS for it is bound to 
>result in serious compromises.  With processors such as these, where 
>real time operations are required, in most cases the application is 
>relatively simple/understood so it is preferable to code the 
>application directly, using RTOS principles, rather than employ a 
>ready made general purpose RTOS.
>
>Ian

Another alternative you rarely see, but I have used it in the past
(with Z80 processors, so not quite so far down the food chain as the
8051, I admit), is to create a special purpose RTOS with different
"classes" of tasks.  In one case I created "comm tasks" that were
awfully near 100% I/O bound and they ran with interrupts disabled,
sharing the same stack and other resources -- they ran from one I/O
request to the next with very little multitasking overhead (about what
a real cooperative MT system would require), yet the rest of the
system was fully interrupt driven.

So interrupts were enabled only when the "task" was waiting for I/O.
If the tasks were any more complex or the real time constraints were
much more rigorous, this would have resulted in too much latency.  But
for the system being designed, it worked great.

The setup handled 24 2400 bps serial links, two 19200 serial links, a
PIO parallel printer interface and a whole lot of minor junk (LCD
display, keyboard, GPIO monitoring stuff, etc,) and never ran out of
steam.  At 2.4 MHz....

--Charles

Hello Hans-Bernhard Broeker,
                           First i would like to thank you, u really
gave me a good idea. But i have some more doubt. YOu can consider me
as an average person in RTOS concepts. So i might have asked some very
basic questions....please bear with me :-)

> You have no idea.  The type of scheduler very much is the issue here,
> because if you chose the appropriate class of scheduling method for
> this target platform, you wouldn't need any per-task stacks to begin
> with.
> 
> The need for stack switching is a property of pre-emptive scheduling,
> which simply isn't an appropriate scheduling technique for a classic
> 8051.
> 
pre-emption is done in cooperative, round-robin or priority based
right...i mean a task can be stopped or will give the processor (in
case of Co-operative)....anyhow i need to still save the context of
the currenlty running task and reload the context the next runnable
task. Let me know if i am wrong here...

> You can do it on some extended variants, though.  E.g. I'm working on
> the DS80C390, whose 1KiB "internal XRAM" can be set up as 4
> independent stacks quite nicely, each of them still being larger than
> a classic 8051's stack.  But then, a '390 in 24 bit contiguous mode is
> far from what people will think of hearing you speak of just "8051",
> without further specification, so it's actually outside the stated
> scope of your RTOS design.

This was really usefull hint u gave me.....Please bear with me if i
ask some wrong questions...i am still a beginer in RTOS,
From what i have read from keil and some architecture, the stack is
located in the scratchpad ram right ?? in the classic 8051 it starts
from 0x30 to 0x7f (idata). which is 80 bytes. Consider i have a 8051
variant from dallas or atmel which gives me a extra XRAM of say 1K,
how do you suggest me to utilize it for my tasks and as well as for my
kernel. Will the scenario be like when a task is running it is
allocated the full scratch pad ram for execution, and when i pre-empt
it, i need to swap the whole 80 bytes to the internal XRAM (a
predefined location for the task ) ??? or can i just use the scratch
pad ram for my kernel, and use the XRAM for the tasks, without doing
the swaping....did i ask something wrong ????


> it evades me why
> would want to design your own RTOS instead of using existing ones,
> including Keil's own RTX51.

I understand your point, anyone would ask the same question, and also
i am aware there a lot of rtos on the web free as well as commercial.
to a name a few, there is xmk, freeRTOS, RTOSUMPS, Salvo, CMX...and
may be more.... But still curiosity kills.....i feel understand the
concepts to the depth is only possible when you really work on it.

Jonathan Kirwan wrote:
> 
... snip ...
> 
> Well, I don't see a reason why pre-emption cannot be supported in
> the 8051.  The hardware stack pointer *IS* limited to 256 bytes or
> 128 bytes (less room required for registers, etc), depending on
> the processor (x51 versus x52, for example.)  But placing software
> parameter stacks in external memory is perfectly feasible.  And
> even if it weren't, I've done pre-emptive systems with small
> numbers of processes on CPUs with less than 128 bytes of total
> RAM.  So I know that declaring all such things as out-of-bounds
> for pre-emption is wrong-minded. I understand why you imagine it
> isn't appropriate, but it's not always the case you suggest here.

I've done it on a PIC.  The time resolution was something like 200
uSec, and the system was rather specialized, but it worked and was
maintainable.  By no stretch of the imagination was it a general
purpose RTOS.

-- 
"I'm a war president.  I make decisions here in the Oval Office
 in foreign policy matters with war on my mind." -         Bush.
"If I knew then what I know today, I would still have invaded
 Iraq. It was the right decision" -       G.W. Bush, 2004-08-02

pachu <pachu_um@hotmail.com> wrote:

> pre-emption is done in cooperative, round-robin or priority based
> right...

That sentence makes no sense.  You can have either pre-emptive, or
cooperative scheduling, but not both.  They're mutually exclusive.

> i mean a task can be stopped or will give the processor (in
> case of Co-operative)....anyhow i need to still save the context of
> the currenlty running task and reload the context the next runnable
> task. Let me know if i am wrong here...

This part of it is correct.  My argument about not needing to save or
switch stack contents if you're not doing pre-emption can be displayed
most easily by showing what a very minimalistic, non-preemptive
scheduling system might look like:

	while (1) {
	   run_task_1();
	   run_task_2();
	   run_task_3();
	}

That's all it really takes.  Or you could try for fancy and do it like
this

	while (1) {
	   int next_task_to_run = whatever();

	   /* run it: */
	   task_arrah[i]();
	}

In this type of task-switching, each task cooperates with the others
simply by returning from its task execution function as soon as it has
nothing left to do.  That way, there simply isn't anything on the call
stack to be saved, and thus no need to save or switch stack contents.

> From what i have read from keil and some architecture, the stack is
> located in the scratchpad ram right ?? in the classic 8051 it starts
> from 0x30 to 0x7f (idata). 

Depends on just how "classic", in the sense of "limited" you want to
be.  Putting it into actual IDATA-only space (I:0x80 to I:0xff) would
be the much more common choice, assuming your 8051 has the (nowadays)
usual 256 bytes of total memory (plus 128 SFRs, plus XDATA).

> which is 80 bytes. Consider i have a 8051 variant from dallas or
> atmel which gives me a extra XRAM of say 1K, how do you suggest me
> to utilize it for my tasks and as well as for my kernel.

By hand.  The method I outlined for the DS80C390 can't be adapted very
widely because most of these can't have the *real* call stack
(i.e. the stuff where an ACALL or LCALL opcodes deposits its return
address) in that XRAM area.  AFAIK the DS80C390 is special in that
regard.

But you can always fake the usual call stack, i.e. push return
addresses and parameters manually and then jump to the subroutine
instead of calling it, and reverse the same process manually instead
of a simple RET opcode.  That's what Keil's "reentrant functions" do.
But IMHO that's getting uncomfortably close to driving nails into the
wall by use of a circular saw.

> Will the scenario be like when a task is running it is
> allocated the full scratch pad ram for execution, and when i pre-empt
> it, i need to swap the whole 80 bytes to the internal XRAM (a
> predefined location for the task ) ??? 

If you want to run full-fledged pre-emptive scheduling, and don't want
to impose any restrictions by configuring the compiler to not use all
of that scratchpad RAM, then yes, that's what you'll end up having to
do.  But, as has been said here repeatedly, that's almost guaranteed
to be the wrong idea, regardless of what your application is finally
going to be doing.  Copying all that stuff back and forth is going to
cost you more than you can afford, in terms of CPU cycles.

> or can i just use the scratch pad ram for my kernel, and use the
> XRAM for the tasks, without doing the swaping....

Well, if you code carefully, you *can* keep all your per-task data in
XRAM, but that's not going to be particularly fast, either.
Navigating XRAM data is considerably slower than using normal
scratchpad RAM on a '51 --- you don't want to be doing all your work
in XRAM if you can help it.

You *really* should have a go at that book by Mr. Pont, and at Keil's
documentation.  You're currently in the process of re-inventing wheels
and coming up with rather ones lacking roundness.  The Keil docs would
help with the former, the book with the latter.

-- 
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Jonathan Kirwan <jkirwan@easystreet.com> wrote:
> On 6 Sep 2004 10:49:37 GMT, Hans-Bernhard Broeker
> <broeker@physik.rwth-aachen.de> wrote:

[...]
> >The need for stack switching is a property of pre-emptive scheduling,

> No, this isn't strictly true and it suggests you don't have a clear mental
> model.

Maybe --- I'm simply not old enough to ever have come across platforms
without a stack.

> Pre-emptive scheduling can even be performed on CPUs that don't even
> support stacks in their hardware architecture, such as the HP-2116
> from the days of the late 1960's and early 1970's, for example.  So
> it cannot be that stack switching is a __property__ of pre-emptive
> scheduling.

Now where's that grain of salt when you need it? :-) That you don't
have to switch or copy stacks, if there are no stacks to do that with,
should go without saying, shouldn't it?

We do happen to be talking about 8051s, though, which quite certainly
do have a stack, and therefore this stack _will_ to be switched or
saved, if you want to pre-empt a task on this platform.

-- 
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

On 6 Sep 2004 19:15:01 GMT, Hans-Bernhard Broeker
<broeker@physik.rwth-aachen.de> wrote:

>Maybe --- I'm simply not old enough to ever have come across platforms
>without a stack.

You must have seen the RCA 1802 :-).

It has 16 registers, of which all could be used as program counter. So
it was easy to have up to 16 separate subroutines each with an own
program counter. You could also view the system as up to 16
cooperative tasks, each with a separate program counter. 

When the program was running with say R7 as the program counter, to
call a subroutine/task that was written with say, R9 as the program
counter, simply specify which register to use as the program counter
with the SEP R9 instruction and the original PC register (R7) is no
longer updated. When the subroutine is going to "exit", it will jump
one byte before the actual start point and switch back to the original
register using the SEP R7 instruction and the calling routine
continues execution where it performed the call. With the jump ahead
of the actual subroutine, the subroutine PC (R9) is ready for the next
activation.

Thus, one can argue, are these routines subroutines or cooperative
tasks.

Paul
  

On 6 Sep 2004 19:15:01 GMT, Hans-Bernhard Broeker
<broeker@physik.rwth-aachen.de> wrote:

>Jonathan Kirwan <jkirwan@easystreet.com> wrote:
>> On 6 Sep 2004 10:49:37 GMT, Hans-Bernhard Broeker
>> <broeker@physik.rwth-aachen.de> wrote:
>
>[...]
>> >The need for stack switching is a property of pre-emptive scheduling,
>
>> No, this isn't strictly true and it suggests you don't have a clear mental
>> model.
>
>Maybe --- I'm simply not old enough to ever have come across platforms
>without a stack.

Understood.  But the point wasn't whether or not you were old enough to see such
things or not.  I was offering only one example that shows that the precision of
your point was lacking.

You said, "The need for stack switching is a property of pre-emptive
scheduling," and it was this point I took issue with, using just one possible
example of a great many others I could also provide.  Stack switching quite
simply is NOT a property associated 1:1 with pre-emptive scheduling.  Switching
stacks does not imply pre-emption; and pre-emption does not imply switching
stacks.  They are separate things and you were conflating them in your comments.
It was that I was addressing.

>> Pre-emptive scheduling can even be performed on CPUs that don't even
>> support stacks in their hardware architecture, such as the HP-2116
>> from the days of the late 1960's and early 1970's, for example.  So
>> it cannot be that stack switching is a __property__ of pre-emptive
>> scheduling.
>
>Now where's that grain of salt when you need it? :-) That you don't
>have to switch or copy stacks, if there are no stacks to do that with,
>should go without saying, shouldn't it?

We could get into that argument, of course.  But again, my point clearly remains
that switching stacks isn't a property of pre-emption.  In other words,
pre-emption is about saving and restoring the important context and it goes
further and provides implications about just what state is considered
'important'.  That *may* (and often does) imply switching stacks, where that is
convenient, of course.

But what I'd like you to take away from this is that conflating the two ideas
turns some very precise terms which are very useful and mushes them together
into a 'gooo' that is less helpful over a broad range of possibilities.  It's
better to keep the theories precise, than to glop them together without clarity.

>We do happen to be talking about 8051s, though, which quite certainly
>do have a stack, and therefore this stack _will_ to be switched or
>saved, if you want to pre-empt a task on this platform.

That again depends.  I can imagine a specific case in my mind on the 8051 where
pre-emption and a separate process is involved without the switching of stacks.

Point remains -- keep the concepts clean and use the right terms for the right
things.

Jon