On Friday, in article <fi6ofm$8f8$1@aioe.org>
ulf@a-t-m-e-l.com "Ulf Samuelsson" wrote:
>>>>> Since power consumption is an issue, you do not want to waste time
>>>>> on a round robin scheduler.
>>>>
>>>> !!!!
>>>>
>>>> What a strange thing to say.
>>>>
>>>> A preemptive multitasker has *far* more baggage than a roundrobin. All
>>>> that task-saving and restoring...
>>>>
>>>
>>> Your comment is totally irrelevant, since I was not comparing
>>> round-robin vs preemptive multitasking.
>>
>> I stand by my response. Please explain how a round-robin can "waste time"
>> and hence waste power. Also please explain what you *were* explaining ;).
MOST of my comments below are aimed at the majority of the contributors
to this thread.
Ulf just happens to be the one being followed up, instead of multiple repeats.
>>
>
>while(TRUE) {
>
> while(!(task_state && ANY_COMPUTABLE)) {
> sleep(); /* wait for interrupts */
Assumption more generalisation
All embedded must save that much power, as the unit may be
mains powered or has to be running at all times.
All architectures and applications will not have
a problem with 'sleep' or 'halt' instructions stopping half
of the peripherals on their microcontroller.
> }
> cur = get_next_task();
> (cur->task)();
> }
This implementation *can* also be used for round robin scheduling as
no doubt the tasks exist in some list. Depending on application and
architecture even the sleep can be incorporated.
get_task could be any form of task list(s) scanning.
It does not exactly look that preemptive to me.
>}
>
>is faster than
>
>while(TRUE) {
> task00();
> task01();
> task02();
> ...
> task97();
> task98();
> task99();
>}
Compared against the worst example of round robin scheduling, that I have
never seen actually implemented.
Round Robin actually covers many different schemes, including multi layered
and time delayed.
ALL TASK scheduling involves some form of list of tasks which have to
be scanned
>end is not pre-emptive, and does not need any context switch.
>Only tasks that needs to be run are run.
That can be done even on round robin.
>The formers is especially effective when you run the task with
>a variable frequency.
>I.E: you could use a task to process an incoming data stream over
>a serial port, a character at a time.
If the architecture supports the low frequency without delays and potential
character loss, when changing frequencies.
>You have no control over when the task needs to be run.
>The interrupt routine will just receive the data into a buffer
>and make the task computable keeping the interrupt routine short.
That is true of any asynchronous input to a system, want to try it with
multiple video standards analog and digital format simultaneously.
>Other tasks set a S/W timer which in some cases needs to
>trigger the task at high frequency, and in other cases needs to
>trigger the task at low frequency.
So you are basically describing most regular timer driven events
that may or may not be directly interupt driven.
>The simple round robin strategy sucks if you try to do the thing above.
That is an implementation I have never seen implemented on many systems.
The simplest round robins have time delays of how many time ticks or
I/O wait state checks have to be done. Often I implement round robin
as two tables
Table 1 task start points
Table 2 Time count and flag (flag is positive for active
0 for stopped
-ve for errored status)
This way any tasks needing a state machine, have the flag variable
for the state machine 'counter'.
At each time tick the priority is sorted by order in the list, if this time
tick requires the task to be processed (count match and valid flag), then
the matching task entry is called.
It could be possible to use the sleep/halt wait if time was left over, but
often this adds unnecessary complexity.
THE ONLY DIFFERENECE SHOWN
==========================
So far everyone has gone on about power saving, claiming this was about
the scheduling that is performing this. Which is complete bunkum!!
The power saving is all about the idle task and if it can execute halt
or sleep modes.
This may or may NOT work depending on
Application
Architecture
If for example nothing happens on the processor but the bus needs to
arbitrated for DMA or other inbuilt peripherals still need to run
most architectures require the CPU to be in AWAKE mode to perform this
and many architectures do not actually have a HALT instruction.
--
Paul Carpenter | paul@pcserviceselectronics.co.uk
<http://www.pcserviceselectronics.co.uk/> PC Services
<http://www.gnuh8.org.uk/> GNU H8 & mailing list info
<http://www.badweb.org.uk/> For those web sites you hate
Has this wheel already been invented?
Started by ●November 17, 2007
Reply by ●November 23, 20072007-11-23
Reply by ●November 23, 20072007-11-23
From Wiki: "Round-robin is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority" -------------------------------------------- This is the same definition I am using. If anyone uses another definition of Round-Robin, then arguing with me on pros/cons is a waste of time, because we are talking about two different things. --- Best Regards, Ulf Samuelsson This is intended to be my personal opinion which may, or may not be shared by my employer Atmel Nordic AB
Reply by ●November 23, 20072007-11-23
In article <fi6ofm$8f8$1@aioe.org>, Ulf Samuelsson says...> > while(TRUE) { > > while(!(task_state && ANY_COMPUTABLE)) { > sleep(); /* wait for interrupts */ > } > cur = get_next_task(); > (cur->task)(); > } > } > > is faster than > > while(TRUE) { > task00(); > task01(); > task02(); > task03(); > task04(); > task05(); > task06(); > task07(); > task08(); > task09(); > ... > task97(); > task98(); > task99(); > } ><snip>> The simple round robin strategy sucks if you try to do the thing above.I would have considered both of the above round robin, non preemptive, run to completion systems. Robert -- Posted via a free Usenet account from http://www.teranews.com
Reply by ●November 26, 20072007-11-26
"Robert Adsett" <sub2@aeolusdevelopment.com> skrev i meddelandet news:MPG.21b13b44eef6553798981c@free.teranews.com...> In article <fi6ofm$8f8$1@aioe.org>, Ulf Samuelsson says... >> >> while(TRUE) { >> >> while(!(task_state && ANY_COMPUTABLE)) { >> sleep(); /* wait for interrupts */ >> } >> cur = get_next_task(); >> (cur->task)(); >> } >> } >> >> is faster than >> >> while(TRUE) { >> task00(); >> task01(); >> task02(); >> task03(); >> task04(); >> task05(); >> task06(); >> task07(); >> task08(); >> task09(); >> ... >> task97(); >> task98(); >> task99(); >> } >> > <snip> > >> The simple round robin strategy sucks if you try to do the thing above. > > I would have considered both of the above round robin, non preemptive, > run to completion systems. > > Robert >That is because you seems to assume "round robin === non-preemptive". In the "round robin" scheduler, you always run tasks in a certain order, which is quite different from your interpretation. -- Best Regards, Ulf Samuelsson This is intended to be my personal opinion which may, or may not be shared by my employer Atmel Nordic AB
Reply by ●November 26, 20072007-11-26
In article <fiea73$gpk$1@aioe.org>, Ulf Samuelsson says...> "Robert Adsett" <sub2@aeolusdevelopment.com> skrev i meddelandet > news:MPG.21b13b44eef6553798981c@free.teranews.com... > > In article <fi6ofm$8f8$1@aioe.org>, Ulf Samuelsson says... > >> > >> while(TRUE) { > >> > >> while(!(task_state && ANY_COMPUTABLE)) { > >> sleep(); /* wait for interrupts */ > >> } > >> cur = get_next_task(); > >> (cur->task)(); > >> } > >> } > >> > >> is faster than > >> > >> while(TRUE) { > >> task00(); > >> task01(); > >> task02(); > >> task03(); > >> task04(); > >> task05(); > >> task06(); > >> task07(); > >> task08(); > >> task09(); > >> ... > >> task97(); > >> task98(); > >> task99(); > >> } > >> > > <snip> > > > >> The simple round robin strategy sucks if you try to do the thing above. > > > > I would have considered both of the above round robin, non preemptive, > > run to completion systems. > > > > Robert > > > > > That is because you seems to assume "round robin === non-preemptive".Nope. The three adjectives I used are independant of one another (orthoganal if you will). Round-robin is more closely the opposite of prioritized(1).> In the "round robin" scheduler, you always run tasks in a certain order, > which is > quite different from your interpretation.Not necessarily. That will hold true only if no task ever suspends which is only true for one of your schedulers. To be round robin only requires that each ready task be executed in turn. With no suspension then that will lead to the order always being the same. Once you introduce suspension then obviously the order can be different once a task rejoins the task list without any effect. If you like just consider it a series of round robin schedulers, with a different schedule each time a task joins or leaves the task list. Robert 1 - I can imagine a non-preemptive, non prioritized schedular that just ran the last task or some random task but I don't see the use for that kind of scheduler. If there is maybe someone can point it out. I expect such systems to be rare on the ground (now watch someone come up with a commom counter example :) It is easy to imagine a preemptive round robin scheduler since they are quite common even in prioritized pre-emptive systems, sometimes they even time slice amoung tasks. -- Posted via a free Usenet account from http://www.teranews.com
Reply by ●November 27, 20072007-11-27
On Nov 23, 6:17 pm, "Ulf Samuelsson" <u...@a-t-m-e-l.com> wrote:> From Wiki: > > "Round-robin is one of the simplest scheduling algorithms for processes > in an operating system, which assigns time slices to each process in equal > portions and in order, handling all processes without priority" > > -------------------------------------------- > This is the same definition I am using. > If anyone uses another definition of Round-Robin, then > arguing with me on pros/cons is a waste of time, > because we are talking about two different things. > > --- > Best Regards, > Ulf Samuelsson > This is intended to be my personal opinion which may, > or may not be shared by my employer Atmel Nordic ABSome things I believe need to be made clear: There is the multitasking model preemptive versus cooperative and there is the scheduling algorithm priority driven and round robin are two examples. I am trying to get some thoughts together on this (and been back to work so time for those thoughts is limited). I'll post something soon. Ed
Reply by ●November 27, 20072007-11-27
On Nov 16, 11:31 pm, Jack Klein <jackkl...@spamcop.net> wrote:> There are all sorts of preemptive kernels, RTOS's, frameworks, out > there, open source and commercial. There are priority-driven > preemptive systems, time-sliced preemptive systems, and others. > > But preemptive systems have their costs, namely context switching > time, and context storing RAM. Even cooperative coroutines have > context switch and space overhead. > > On the other end of the scale is pure cooperative multitasking, as > exemplified by the classic "super loop": > > while (1) > { > task1(); > task2(); > /* ... */ > task99(); > task100(); > > } > > In most cases, each of these task calls some lower level routine > (timer, communication interface, whatever) to see if there's actually > any work for it to do. If not, is just returns. The advantage, of > course, is that there is no context overhead, either space or time. > > This can be detrimental to response time if an event comes in for a > task just after it has had its turn in the super loop. It won't see > its event until after every other task has been called, whether the > other tasks really have any useful work to do or not. > > What I need, and I am planning to develop, is a cooperative task > scheduler to replace the super loop. Inter task communication, and > ISR to task communication, will go through a kernel to set event > flags, timer flags, put messages in queues, etc., and the kernel will > track which tasks are actually ready because they have pending events. > > After any task returns, the scheduler will execute the highest > priority ready task. > > My question is, does anyone know of any kernel, RTOS, whatever, that's > implemented this way? I'd look at the documentation and API details > for any that exist, not their source code. > > Knowing whether or not this wheel has already been invented will be > handy when I reinvent it. > > -- > Jack Klein > Home:http://JK-Technology.Com > FAQs for > comp.lang.chttp://c-faq.com/ > comp.lang.c++http://www.parashift.com/c++-faq-lite/ > alt.comp.lang.learn.c-c++http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.htmlTake a look at csRtos. Originally developed for the atmel AVR by Glen Worstell, I ported a version to the PIC (16xxxx and 18xxxx families under CCS and Microchip C). Uses a lot less resources than a preemptive task switcher and allows for task priorities. It's a lot like the Salvo OS but has the big advantage of being free. The biggest restriction is you can't call OS subroutines from a subroutine, only from the task level, but that's not too hard to work around. I like using it because you wind up with simple linear code instead of large messy state machines (no flamewars please :-) , I still like state machines). If interested, google for csRtos. You should find Glen's original article, source code for the PIC I posted to the CCS sourcecode forum, and AVRfreaks seems to have a more advanced version. Mark
Reply by ●December 8, 20072007-12-08
mhahn@hvc.rr.com wrote:> Take a look at csRtos. Originally developed for the atmel AVR by Glen > Worstell, I ported a version to the PIC (16xxxx and 18xxxx families > under CCS and Microchip C). Uses a lot less resources than a > preemptive task switcher and allows for task priorities. It's a lot > like the Salvo OS but has the big advantage of being free. The biggest > restriction is you can't call OS subroutines from a subroutine, only > from the task level, but that's not too hard to work around. I like > using it because you wind up with simple linear code instead of large > messy state machines (no flamewars please :-) , I still like state > machines). > > If interested, google for csRtos. You should find Glen's original > article, source code for the PIC I posted to the CCS sourcecode forum, > and AVRfreaks seems to have a more advanced version.oh shit, it looks like i have reinvented the wheel once again, but this time i figured out the hub :-) more precisely, i (still) have to write some firmware for some machine, around a venerable 16F877 (with ALL the inherent limitations, grumblgrumbl) so a home-made "multi threaded kernel" is needed. I have a "working" system (proof of concept) with 3 independent threads, using less than 400 instruction words and i have no state machine anywhere :-) it's round-robin (though a thread could be added and removed dynamically, since the threads' linked list is in RAM), cooperative (NOT preemptive, but some IRQs communicate with some buffers) and i use many assembler tricks and lots of macros to make the code as small as possible, yet useful. I have a 1KHz (soft-)timer that can wake up threads. However, my application does not need priorities so i didn't implement them. More interestingly, i have overcome one painful limitation. Any thread can call a routine which can yield(), and this routine can also be executed by another thread : there is some support for code reentry. Here i quote from the csRtos source : > //1) Operating System calls that may result in task switches can occur > // only at the top level of a task. That is, you cannot make os calls > // from subroutines called within a task. so i have addressed that. My technique (which is maybe already used by others ?) works in asm and not C (or the compiler would DIE). In fact, i use dirty hacks to circumvent PIC16F's single hardware stack, at the expense of some code bloat. Finally, my client accepted that i release this multithreaded kernel) to the public (because it can be split easily from the rest of the application). So i'll certainly post it on my website when it's ready. happy hacking,> Markyg
Reply by ●December 13, 20072007-12-13
>On 2007-11-17, Jack Klein <jackklein@spamcop.net> wrote:>It's been invented many times. > >Here are a couple approaches I thought were interesting: > > http://www.sics.se/~adam/pt/ > >This is a threading model, but doesn't deal with scheduling. >I think you could run it on top of something like this to deal >with scheduling: > >http://www.embedded.com/columns/technicalinsights/190302110?_requestid=327672> >There are also many implementations of coroutines and >cooperative multi-tasking available. >I second both of these recommendations. You can get full source code for the SST (now called QK) at the web site run by one of the authors of the article (Miro Samek) www.quantum-leaps.com
