Has this wheel already been invented?

On Mon, 19 Nov 2007 22:08:01 -0500, Robert Adsett
<sub2@aeolusdevelopment.com> wrote:

>In article <47417143.434778421@192.168.0.50>, Stephen Pelc says...
>> Send me an email address, and I'll ship you a manual. I should
>> warn you that it's all written in Forth ... because it works.
>
>You wrote the manual in Forth? Oh, my poor aching head :)

Tee, hee. But actually we did write the manual in Forth. The
manual is in the form of formal comments in the source code.
These are then extracted by our DocGen tool and processed to
generate PDF and HTML versions of the manual.

We're big fans of literate programming.

Stephen


-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

In article <d89f526c-bdf0-4367-b223-
3860607c294a@s36g2000prg.googlegroups.com>, edprochak@gmail.com says...
> On Nov 21, 12:43 pm, "Steve at fivetrees"
> <st...@NOSPAMTAfivetrees.com> wrote:
> > "Ed Prochak" <edproc...@gmail.com> wrote in message
> >
> > news:41808365-59d3-4fe2-ac77-98e726e2a164@b15g2000hsa.googlegroups.com...
> >
> >
> >
> > > If the system is cooperative, why would there be a  priority scheme?
> >
> > Slightly different use of the term "priority" - here, I mean "more
> > time-critical than other tasks". E.g. I may need to check a serial port
> > more often than I update the screen.
> >
> > > Cooperative multasking has a fatal flaw, especially for real-time
> > > systems. And the flaw is that every task must be aware of the time
> > > constraints of the others. IOW, you make what seems to be a simple
> > > programming change in task99 and suddenly task100 starts failing to
> > > meet its deadline intermittently. This isn't a failure of the
> > > superloop, but of the whole cooperative multasking model.
> >
> > Nah. This is basic stuff. For instance in the above, taking what I wrote
> > entirely literally could mean that continuous serial port data would
> > result in no screen activity. This is easily worked around - either by
> > ensuring that the serial port task skips a beat once in a while, or by
> > simply observing that serial ports tend to be slow ;).
> 
> So you actually are supporting my observation, that you would have to
> put delays or skips in one task (the serial port comm) to allow
> another task (screen updater) to work properly. With a decently
> designed preemptive system, the scheduler works it out based on the
> load at runtime.
> >
> > > You might want to check some OS theory before starting your
> > > development.
> >
> > Sure; it's always good to do some research. But also remember the KISS
> > principle.
> 
> That is what I am saying, in many cases a preemptive kernal can make
> the design much simpler by decoupling the tasks. And the overhead is
> no onerous. At one place I worked, there was a contractor tasked with
> implementing the software on a small daughter processor of our system.
> He came in with a superloop design. I was able to show him how the OS
> kernal we had would consume fewer CPU cycles than his superloop for
> the same task load.  With the advantage of interrupt driven I/O versus
> polling, it was a easy win for the preemptive kernal. And the tasks
> became simpler too.
> 

I can't imagine  any but the simplest system doing serial I/O without
interrupts.  Even my simplest 'super loops'  just look in the queue
for the data that the interrupt handler has put there.
> 
> So, if you want to toss quotes, I cannot pass up the familiar
> those who ignore the past are condemned to repeat it.   8^)
> 
> But more to engineering tastes, my College Chemistry Proffessor always
> said:
> if it works, use it!
> 
> So if it works, I'm not going to complain. I'm just pointing out a
> possibly better option.

The standard problems with preemptive RTOSs on small systems generally
end up with the amount of memory needed to save the machine state
for each task.  On an ARM,  that could mean stacking and restoring
64 bytes plus whatever is used for local variables for each task.

A super loop, with a combined variable stack, need only save and 
restore a smaller subset of the registers as each function is
called,  so the memory footprint is probably smaller.

My most recent project combined the super loop and a 'scheduler'
interrupt to handle some moderately complex interleaved data
collection:

The main loop looked for input in the serial Input queue and
processed commands as needed.  It also checked for input data
in the input queues and processed and stored that data as
needed.

Serial I/O was handled with standard interrupt-driven queues.

Analog input was collected and time stamped by a state machine called
from a 50Hz timer interrupt.  The state machine broke the ADC collection
into a series of request-data and read-data operations.  The data 
collected was put into a statically allocated memory queue,  from 
whence it was fetched by main loop.

The longest-running state of the timer ISR took about 400 
microseconds---or about 2% of the 20mSec between interrupts.

ADC collection was put in the timer ISR to maintain jitter-free
data collection, as writing the data to a CF card can sometimes
take more than 20mSec at those times when the FAT needs updating.
Converting and displaying a subset of the values in floating-
point format also sucked up the odd millisecond here and there!  ;-)

This was on a 68K processor at 16MHz.  Memory size was not
an issue.  The lack of an easily ported RTOS for the particular
hardware did mandate some variation of the super loop approach.


Mark Borgerson

In article <a14eae71-9b60-4cea-9be7-6041433a9948
@j20g2000hsi.googlegroups.com>, edprochak@gmail.com says...
> On Nov 21, 12:45 pm, "Steve at fivetrees"
> <st...@NOSPAMTAfivetrees.com> wrote:
> > "Ulf Samuelsson" <u...@a-t-m-e-l.com> wrote in message
> >
> > news:fhrj5c$mfo$2@aioe.org...
> >
> >
> >
> > > 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...
> 
> Only when there is work to do (and I do not agree it is MORE baggage,
> as you know).
> What happens in Round Robin when the system is idle? You essentially
> have a busy loop.
> A preemptive scheduler starts the null task which executes a halt
> instruction. The entire CPU goes idle until the next interrupt (likely
> the clock). Sure beats a busy wait loop.

When I'm in the mood to save power,  I generally turn down the CPU clock
speed  in the main loop and turn it back up when there is data to be
moved.   

I've also used the clock interrupt to allow the system to save power 
like this:

 while(!done){
	SleepUntilClock();  // low power sleep until clock tick
       while(DataAvailable()){
		GetInput(&mydata);
              ProcessOutput(&mydata);
	}
}

For this type of loop, you probably want a clock that ticks more than
once per second!  You also need interrupt-driven input handlers that
are smart enough to go to sleep when they are done with the input.
This approach is probably not suitable for very high speed 
data collection---where the collection takes more than
10 to 20% of the CPU bandwidth.

Mark Borgerson

"Ed Prochak" <edprochak@gmail.com> wrote in message 
news:4495b7cf-15f4-4db1-b4fb-5046c157b54f@e4g2000hsg.googlegroups.com...
> On Nov 21, 12:53 pm, "Steve at fivetrees"
> <st...@NOSPAMTAfivetrees.com> wrote:
>> My response to that is not that it can't be done; more than 
>> cooperative
>> is actually a better way to design (unless it's a multi-user
>> programmable system, or, as another poster has noted, the dynamics of
>> the team make the programming partitioning simpler and the entire 
>> team
>> can't be depended on maintain the kind of discipline needed to make
>> cooperative work properly).
>
> Ah, you have done real systems development, excellent.

Er, yeah. See http://www.sfdesign.co.uk ;). I'm practically an expert ;) 
;).

> About the smallest device I can remember working on was a comm
> daughterboard for a motor controller. Even that device had a few K of
> RAM (the comm buffer was exactly 1K). That was the device where I saw
> how the super loop could be very painful. The architecture requires
> the tasks to be limited to a max X CPU cycles. So every code change
> required counting cycles. If you went beyond X, you split the code
> into more task segments. (I had to program on it. I could not change
> the architecture, since it was a purchased product.) Tha thing was a
> real PITA. I am sure your designs are not like that one. (I'm sincere
> here.)

Eeep. That does indeed sound like a PITA.

The "discipline" thing about cooperative multitasking is that each 
task/process must relinquish control back to the superloop/roundrobin 
every N milliseconds, where N is the worst-case latency you want other 
tasks to have. Most of the time, this can be tens of milliseconds or 
less; but even this means that lengthy processes have to be broken up 
into state machines. This is a Good Thing. It means that you have to 
think more in system terms than in "it's all mine" terms.

However, counting cycles sucks. Someone really made a poor architectural 
decision on that one. Please don't let that bad experience colour your 
thinking.

Steve
http://www.fivetrees.com 

"Mark Borgerson" <mborgerson@comcast.net> wrote in message 
news:MPG.21af52c7f12328fe9896a8@newsgroups.comcast.net...
> In article <d89f526c-bdf0-4367-b223-
> 3860607c294a@s36g2000prg.googlegroups.com>, edprochak@gmail.com 
> says...
>> On Nov 21, 12:43 pm, "Steve at fivetrees"
>> <st...@NOSPAMTAfivetrees.com> wrote:
>> > "Ed Prochak" <edproc...@gmail.com> wrote in message
>> > news:41808365-59d3-4fe2-ac77-98e726e2a164@b15g2000hsa.googlegroups.com...
>> >
>> > > If the system is cooperative, why would there be a  priority 
>> > > scheme?
>> >
>> > Slightly different use of the term "priority" - here, I mean "more
>> > time-critical than other tasks". E.g. I may need to check a serial 
>> > port
>> > more often than I update the screen.
>> >
>> > > Cooperative multasking has a fatal flaw, especially for real-time
>> > > systems. And the flaw is that every task must be aware of the 
>> > > time
>> > > constraints of the others. IOW, you make what seems to be a 
>> > > simple
>> > > programming change in task99 and suddenly task100 starts failing 
>> > > to
>> > > meet its deadline intermittently. This isn't a failure of the
>> > > superloop, but of the whole cooperative multasking model.
>> >
>> > Nah. This is basic stuff. For instance in the above, taking what I 
>> > wrote
>> > entirely literally could mean that continuous serial port data 
>> > would
>> > result in no screen activity. This is easily worked around - either 
>> > by
>> > ensuring that the serial port task skips a beat once in a while, or 
>> > by
>> > simply observing that serial ports tend to be slow ;).
>>
>> So you actually are supporting my observation, that you would have to
>> put delays or skips in one task (the serial port comm) to allow
>> another task (screen updater) to work properly. With a decently
>> designed preemptive system, the scheduler works it out based on the
>> load at runtime.
>> >
>> > > You might want to check some OS theory before starting your
>> > > development.
>> >
>> > Sure; it's always good to do some research. But also remember the 
>> > KISS
>> > principle.
>>
>> That is what I am saying, in many cases a preemptive kernal can make
>> the design much simpler by decoupling the tasks. And the overhead is
>> no onerous. At one place I worked, there was a contractor tasked with
>> implementing the software on a small daughter processor of our 
>> system.
>> He came in with a superloop design. I was able to show him how the OS
>> kernal we had would consume fewer CPU cycles than his superloop for
>> the same task load.  With the advantage of interrupt driven I/O 
>> versus
>> polling, it was a easy win for the preemptive kernal. And the tasks
>> became simpler too.
>
> I can't imagine  any but the simplest system doing serial I/O without
> interrupts.  Even my simplest 'super loops'  just look in the queue
> for the data that the interrupt handler has put there.
>>
>> So, if you want to toss quotes, I cannot pass up the familiar
>> those who ignore the past are condemned to repeat it.   8^)
>>
>> But more to engineering tastes, my College Chemistry Proffessor 
>> always
>> said:
>> if it works, use it!
>>
>> So if it works, I'm not going to complain. I'm just pointing out a
>> possibly better option.
>
> The standard problems with preemptive RTOSs on small systems generally
> end up with the amount of memory needed to save the machine state
> for each task.  On an ARM,  that could mean stacking and restoring
> 64 bytes plus whatever is used for local variables for each task.
>
> A super loop, with a combined variable stack, need only save and
> restore a smaller subset of the registers as each function is
> called,  so the memory footprint is probably smaller.
>
> My most recent project combined the super loop and a 'scheduler'
> interrupt to handle some moderately complex interleaved data
> collection:
>
> The main loop looked for input in the serial Input queue and
> processed commands as needed.  It also checked for input data
> in the input queues and processed and stored that data as
> needed.
>
> Serial I/O was handled with standard interrupt-driven queues.
>
> Analog input was collected and time stamped by a state machine called
> from a 50Hz timer interrupt.  The state machine broke the ADC 
> collection
> into a series of request-data and read-data operations.  The data
> collected was put into a statically allocated memory queue,  from
> whence it was fetched by main loop.
>
> The longest-running state of the timer ISR took about 400
> microseconds---or about 2% of the 20mSec between interrupts.
>
> ADC collection was put in the timer ISR to maintain jitter-free
> data collection, as writing the data to a CF card can sometimes
> take more than 20mSec at those times when the FAT needs updating.
> Converting and displaying a subset of the values in floating-
> point format also sucked up the odd millisecond here and there!  ;-)
>
> This was on a 68K processor at 16MHz.  Memory size was not
> an issue.  The lack of an easily ported RTOS for the particular
> hardware did mandate some variation of the super loop approach.

Wot he said. Mark and I clearly could work together quite happily ;).

More seriously: no, I don't mean that I'd put delays *anywhere*. What I 
meant was that I'd ensure that higher-priority tasks couldn't DoS tasks 
which, although lower priority, still need to be run regularly. And, as 
Mark said, things like serial and "heartbeat" (timer) interrupts make 
life much rosier.

Steve
http://www.fivetrees.com 

Steve at fivetrees wrote:

<snip>

> However, counting cycles sucks. Someone really made a poor architectural 
> decision on that one.

I am currently working on a DSP with a deterministic cycle-counting,
time-slicing hard-realtime o/s; it does have provisions for 'background'
non-deterministic processes, but the hard-realtime architecture is
actually a refreshing change for me.  I enjoy knowing the timing
precisely for every task and every state vs. the complex considerations
of timing in a pre-emptive system.  I have no worries about jitter
or vagaries of ISR timings.  It is a different paradigm for me
but it is elegant and simple.

FWIW, I would have liked to program the Singer System-10 which also
was a hardware round-robin, hard interval real-time architecture.

Regards,

Michael

In article <5LqdnSAAjr8GhNvanZ2dnUVZ8tyqnZ2d@pipex.net>, 
steve@NOSPAMTAfivetrees.com says...
> "Mark Borgerson" <mborgerson@comcast.net> wrote in message 
> news:MPG.21af52c7f12328fe9896a8@newsgroups.comcast.net...
> > In article <d89f526c-bdf0-4367-b223-
> > 3860607c294a@s36g2000prg.googlegroups.com>, edprochak@gmail.com 
> > says...
> >> On Nov 21, 12:43 pm, "Steve at fivetrees"
> >> <st...@NOSPAMTAfivetrees.com> wrote:
> >> > "Ed Prochak" <edproc...@gmail.com> wrote in message
> >> > news:41808365-59d3-4fe2-ac77-98e726e2a164@b15g2000hsa.googlegroups.com...
> >> >
> >> > > If the system is cooperative, why would there be a  priority 
> >> > > scheme?
> >> >
> >> > Slightly different use of the term "priority" - here, I mean "more
> >> > time-critical than other tasks". E.g. I may need to check a serial 
> >> > port
> >> > more often than I update the screen.
> >> >
> >> > > Cooperative multasking has a fatal flaw, especially for real-time
> >> > > systems. And the flaw is that every task must be aware of the 
> >> > > time
> >> > > constraints of the others. IOW, you make what seems to be a 
> >> > > simple
> >> > > programming change in task99 and suddenly task100 starts failing 
> >> > > to
> >> > > meet its deadline intermittently. This isn't a failure of the
> >> > > superloop, but of the whole cooperative multasking model.
> >> >
> >> > Nah. This is basic stuff. For instance in the above, taking what I 
> >> > wrote
> >> > entirely literally could mean that continuous serial port data 
> >> > would
> >> > result in no screen activity. This is easily worked around - either 
> >> > by
> >> > ensuring that the serial port task skips a beat once in a while, or 
> >> > by
> >> > simply observing that serial ports tend to be slow ;).
> >>
> >> So you actually are supporting my observation, that you would have to
> >> put delays or skips in one task (the serial port comm) to allow
> >> another task (screen updater) to work properly. With a decently
> >> designed preemptive system, the scheduler works it out based on the
> >> load at runtime.
> >> >
> >> > > You might want to check some OS theory before starting your
> >> > > development.
> >> >
> >> > Sure; it's always good to do some research. But also remember the 
> >> > KISS
> >> > principle.
> >>
> >> That is what I am saying, in many cases a preemptive kernal can make
> >> the design much simpler by decoupling the tasks. And the overhead is
> >> no onerous. At one place I worked, there was a contractor tasked with
> >> implementing the software on a small daughter processor of our 
> >> system.
> >> He came in with a superloop design. I was able to show him how the OS
> >> kernal we had would consume fewer CPU cycles than his superloop for
> >> the same task load.  With the advantage of interrupt driven I/O 
> >> versus
> >> polling, it was a easy win for the preemptive kernal. And the tasks
> >> became simpler too.
> >
> > I can't imagine  any but the simplest system doing serial I/O without
> > interrupts.  Even my simplest 'super loops'  just look in the queue
> > for the data that the interrupt handler has put there.
> >>
> >> So, if you want to toss quotes, I cannot pass up the familiar
> >> those who ignore the past are condemned to repeat it.   8^)
> >>
> >> But more to engineering tastes, my College Chemistry Proffessor 
> >> always
> >> said:
> >> if it works, use it!
> >>
> >> So if it works, I'm not going to complain. I'm just pointing out a
> >> possibly better option.
> >
> > The standard problems with preemptive RTOSs on small systems generally
> > end up with the amount of memory needed to save the machine state
> > for each task.  On an ARM,  that could mean stacking and restoring
> > 64 bytes plus whatever is used for local variables for each task.
> >
> > A super loop, with a combined variable stack, need only save and
> > restore a smaller subset of the registers as each function is
> > called,  so the memory footprint is probably smaller.
> >
> > My most recent project combined the super loop and a 'scheduler'
> > interrupt to handle some moderately complex interleaved data
> > collection:
> >
> > The main loop looked for input in the serial Input queue and
> > processed commands as needed.  It also checked for input data
> > in the input queues and processed and stored that data as
> > needed.
> >
> > Serial I/O was handled with standard interrupt-driven queues.
> >
> > Analog input was collected and time stamped by a state machine called
> > from a 50Hz timer interrupt.  The state machine broke the ADC 
> > collection
> > into a series of request-data and read-data operations.  The data
> > collected was put into a statically allocated memory queue,  from
> > whence it was fetched by main loop.
> >
> > The longest-running state of the timer ISR took about 400
> > microseconds---or about 2% of the 20mSec between interrupts.
> >
> > ADC collection was put in the timer ISR to maintain jitter-free
> > data collection, as writing the data to a CF card can sometimes
> > take more than 20mSec at those times when the FAT needs updating.
> > Converting and displaying a subset of the values in floating-
> > point format also sucked up the odd millisecond here and there!  ;-)
> >
> > This was on a 68K processor at 16MHz.  Memory size was not
> > an issue.  The lack of an easily ported RTOS for the particular
> > hardware did mandate some variation of the super loop approach.
> 
> Wot he said. Mark and I clearly could work together quite happily ;).
> 
> More seriously: no, I don't mean that I'd put delays *anywhere*. What I 
> meant was that I'd ensure that higher-priority tasks couldn't DoS tasks 
> which, although lower priority, still need to be run regularly. And, as 
> Mark said, things like serial and "heartbeat" (timer) interrupts make 
> life much rosier.
> 
For sure.  I suppose that I'm set in my ways since I was teaching the 
advantages of interrupts to CS students in '84 and  using 
them as part of all my projects since before then.

Two of the most important things I do with a new processor are 

1.  Get interrupt-driven serial I/O working.

2.  Get the timer ISR working to give me a regular interrupt---usually
with an LED blink to confirm its operation.


#1 was a bit of a challenge on the AT91SAM7 series, since I wanted to
use the DMA capabilities of the chip.

#2 is a key element if you need  jitter-free data acquisition. (However
truly jitter-free operation can require a thorough knowledge of 
interrupt priorities and masking if there is a lot of data moving
through the serial port implemented in #1.)

This approach fills a large void between a foreground-only polling
loop and a true RTOS.  It's worked well for me for a couple
of decades, but I'm not totally resistant to change.  I have the
Micro-C/OSII book and disk on the shelf waiting for a few free
weeks.



Mark Borgerson

msg wrote:
> Steve at fivetrees wrote:
> 
> <snip>
> 
>> However, counting cycles sucks. Someone really made a poor
>> architectural decision on that one.
> 
> I am currently working on a DSP with a deterministic cycle-counting,
> time-slicing hard-realtime o/s; it does have provisions for 'background'
> non-deterministic processes, but the hard-realtime architecture is
> actually a refreshing change for me.  I enjoy knowing the timing
> precisely for every task and every state vs. the complex considerations
> of timing in a pre-emptive system.  I have no worries about jitter
> or vagaries of ISR timings.  It is a different paradigm for me
> but it is elegant and simple.
> 
> FWIW, I would have liked to program the Singer System-10 which also
> was a hardware round-robin, hard interval real-time architecture.
> 
An interesting machine, indeed. More data at
http://members.iinet.net.au/~daveb/Sys-10.html

>
> About the smallest device I can remember working on was a comm
> daughterboard for a motor controller. Even that device had a few K of
> RAM (the comm buffer was exactly 1K). That was the device where I saw
> how the super loop could be very painful. The architecture requires
> the tasks to be limited to a max X CPU cycles. So every code change
> required counting cycles. If you went beyond X, you split the code
> into more task segments. (I had to program on it. I could not change
> the architecture, since it was a purchased product.) Tha thing was a
> real PITA. I am sure your designs are not like that one. (I'm sincere
> here.)
>
> Later,
>   Ed
>

The hairiest think I worked on was processing an incoming 2 Mbit E1
containing 32 timeslots of 8 bits on a 16 bit HPC16400E.
(Basically a 3 MIPS machine)

The program used 32 tasks, each implementing a state machine.
No buffering involved, so you had  ~4 us to complete the task,
including the task switch.

That used a Round Robin scheduler.

-- 
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 

>>>> 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 ;).
>

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();
}


end is not pre-emptive, and does not need any context switch.
Only tasks that needs to be run are run.

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.
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.
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.

The simple round robin strategy sucks if you try to do the thing above.

> Steve
> http://www.fivetrees.com
>



-- 
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