EmbeddedRelated.com
Forums
Memfault State of IoT Report

Rtos Design

Started by pachu September 4, 2004
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

Memfault State of IoT Report