Pre-emptive scheduler - Page 2

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Re: Pre-emptive scheduler
On Sat, 25 Oct 2003 02:59:44 -0700, Albert Lee Mitchell

Quoted text here. Click to load it

I would have thought that was blindingly obvious. Good to
see government making sensible decisions for a change.

Mike Harding


Re: Pre-emptive scheduler
Quoted text here. Click to load it

Uhh, there are many truly embedded processors that do have a stack
pointer register and which do allow to make task switches this way.
Just to add some more to my previous posters list:

Renesas M16C (16 bit CPU)
Renesas H8 series (and I'm quite sure all other former Hitachi CPU's)
Rabbit Semiconductor - all Rabbit CPU's (8 bit CPU)

etc. etc. It seems to me that the majority of CPU's is in fact using a
stack pointer register that can be loaded to ease task switching and
that there is only a minority of CPU's where this is not possible.

Markus

Re: Pre-emptive scheduler

Quoted text here. Click to load it

    There are more 8051 variants sold than all other controllers combined.
But to answer your implied question, yes, there are quite a number of
CPU's which permit pointer relocation but not all those are controllers,
most are processors used, correctly or not, in embedded control
applications.

    Of those many are from Asian sources which I dismiss as bad business
partners.  There have been too many horror stories of system manufacturers
having the rug pulled out from under them because Oki, Mitsubishi, Sony,
NEC and others have made marketing decisions which eliminated their source
of supply.  I do not design with sole-source Japanese products any longer.

    I owe my clients more than just good design work, I owe them a viable
product.  This is all-inclusive, availablity (hence Motorola even comes
under scrutny), cost, and reliability.  Unless you are considering very
high volumes you're going to be beneath the radar horizon of most Pacific
suppliers.  I don't have that fear with European or American vendors.

-- Regards, Albert
----------------------------------------------------------------------
AM Research, Inc.                  The Embedded Systems Experts
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------


Re: Pre-emptive scheduler
Quoted text here. Click to load it

[...]
Quoted text here. Click to load it


Huh? What ever gave you the idea I might have been talking about a
Pentium, of all things?

To give you a more realistic example: we're doing time-sliced
pre-emptive scheduling on an extended 8051 variant around here (DS
80C390, 4 tasks --> 4 stacks of 256 bytes each).

Quoted text here. Click to load it

Hmm.. and the 80186 isn't?  Or the 68000 family?  Or ARM?  And none of
those you do agree are "embedded controllers" has a modifiable stack
pointer?

Actually, even if the CPU stack _is_ too small for splitting it up to
be feasible, like the (128 minus other usage) bytes you get on a
classic 8051, you can still go and implement your own stack in main
memory, usually making it a trivial extension to support as many of
them as will fit into RAM.  

Nothing's requiring, say, a C compiler to actually use the CPU's
native stack as the C execution stack.  You just need _some_ thing
that behaves like a stack.

Copying around entire stack contents is thus almost certainly never
necessary unless you want to delve into systems that are, indeed,
simply too small or of brain-damaged design to support multi-tasking
of any sort.  I'm not arguing that such platforms can't exists --- I
certainly haven't seen every platform on the planet, for one thing.
But I strongly contend your point that they are a typical case.
--
Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Re: Pre-emptive scheduler

Quoted text here. Click to load it

    Agreed.  And that "something" invariably has a higher overhead penalty.

Quoted text here. Click to load it

    You are elevating this conversation to a higher plateau effectively
ruling out the majority of embedded control applications.  Defining terms
to exclude those which support my position as "brain dead" doesn't change
the fact that most embedded control systems _are_ tiny, single-chip
microcontrollers without external memory and without the features you tout.
 
-- Regards, Albert
----------------------------------------------------------------------
AM Research, Inc.                  The Embedded Systems Experts
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------


Re: Pre-emptive scheduler

Quoted text here. Click to load it

Nowhere near as high as having to copy entire CPU stack contents back
& forth, though.

Quoted text here. Click to load it


Am I?  Looking at your other replies in this thread, I'd rather say
you continuously keep lowering the barrier for what you're willing to
accept as being an "embedded system".  First, you dismissed Pentium.
Now you pull out of your hat distinctions between "controller"
vs. "processor", "asian" vs. wherever else's design shops, and what
not.

Quoted text here. Click to load it

I didn't do that!  Read my text again: The only occurence of "brain
dead" was in relation to purely hypothetical designs that might exist,
which have all the other ingredients needed to run pre-emptive
multitasking, yet due to some needless design limitation can't do it.

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

Re: Pre-emptive scheduler

Quoted text here. Click to load it

    Agreed.  In fact that's been my position from the beginning.
 
Quoted text here. Click to load it

    True.

Quoted text here. Click to load it

    True, what's your point?    
 
Quoted text here. Click to load it

    I'm sorry if I misunderstood.  Upon re-reading I guess I still
misunderstand for it appears as though you are dismissing all "small"
processor/controllers as "brain-dead" by inference.  I submit that even
tiny (smaller than "small") cpu's are capable of multitasking.  Of course
the architecture of both the silicon and s/w will determine performance
which is the topic we're discussing.
 
-- Regards, Albert
----------------------------------------------------------------------
AM Research, Inc.                  The Embedded Systems Experts
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------


Re: Pre-emptive scheduler


Quoted text here. Click to load it


68HC11 example of saving and restoring task context follows.  The OS is
a pre-emptive multitasker with timesliced round-robin scheduling among
tasks at the same priority level.  There are 4 priority queues handled
by the scheduler in this particular case, there could be more if needed.

*
*  Dispatch - load task context and resume
*
*  C prototype:
*     void Dispatch(void *StkFramePtr)
*  Inputs:
*     StkFramePtr - Address of task context pointer within TCB
*     User Stack on entry:
*        0 StkFrame->
*        1 BANKREG bank bits (BBBB 0000)
*        2 Interrupt frame
*  Outputs:
*     None.
*
Dispatch EQU   *
         XGDX              Address the context frame
         LDS   0,X         Load the stack pointer
*
         LDAA  SBANKREG     Pick up BANKREG
         ANDA  #($FF-BANK) Clear bank bits
         TSX               Address the stack
         ORAA  0,X         OR in new bank bits from stack
         STAA  OUTPORT0_ADDR  Perform bank switch
         STAA  SBANKREG
         PULA              Remove bank byte from stack
*
         RTI               Restore remaining context and resume

*
*  SaveInterruptContext - Pushes BANKREG (w/ bank bits) on the stack,
*                          then saves SP in the task's TCB.
*
*  This routine is only to be called from interrupt handlers.
*  It is assumed that the stack is as per entry to the handler,
*  i.e., no additional bytes have been pushed or popped except
*  for the return address from this routine.
*
*  C prototype:
*     void SaveInterruptContext(void *SaveArea)
*  Inputs:
*     SaveArea - address of TCB.StackPtr for current task
*     Stack on entry:
*        0 SP->
*        1 RtnAddr (SaveInterruptContext)
*        3 Interrupt frame
*  Outputs:
*     No Formal Outputs.
*     Stack on exit:
*        0 SP->
*        1 BANKREG bank bits (BBBB 0000)
*        2 Interrupt frame
*
SaveInterruptContext EQU   *
         XGDY              Get SaveArea addr into Y reg
         PULX              Get return address into X reg
  
         LDAA  SBANKREG     Pick up BANKREG
         ANDA  #BANK       Keep only bank bits
         PSHA              Save on stack

         STS   0,Y         Store SP to SaveArea
         JMP   0,X         Return to caller

So where's all the overhead?  The only complexity has to do with the
fact that the task could have been running banked code at the time it
was interrupted and pre-empted.  The standard interrupt frame has to be
extended by stacking the bank bits on top - no big deal at all.

Regards,
-rick-

Embedded systems (Was: Pre-emptive scheduler)
On Mon, 20 Oct 2003 01:13:05 -0700, Albert Lee Mitchell


Quoted text here. Click to load it

When was the expression "embedded system" used for the first time ?

As far as I understand, this expression refers to a system, in which
the end user does not necessary know that he/she is dealing with a
computer.

By this definitions, quite a few systems implemented by mini
computers, such as DEC PDP-11 or DG Nova computers, were embedded
systems, but as far as I remember, they were not called embedded
systems in those days.

Typically such systems consisted of a few boxes in a 19 inch rack with
cards full of 74(S)xx series chips.  Even in the mid 1980's such
systems could contain magnetic core memories instead of dynamic RAMs,
if radiation resistance was an issue.

Paul
  

Re: Pre-emptive scheduler
Quoted text here. Click to load it

Long before that.  We called them hard-wired special purpose
computers.  In 1963 I built one that had 16k of 24 bit words,
several highly linear A/D converters, displays, output magnetic
tape at 200 bpi, etc. from logic implemented with individual
transistors.  It occupied 4 bays of relay racks.  Design,
construction, checkout, documentation, delivery took about 9
frenzied months - an appropriate gestation period.  We had the A/D
systems, bought the memory (core), tape drives, and display CRTs
(but not their drivers) and built the rest.  Dynamic RAMs didn't
exist.

Simpler, more portable systems for the same basic purpose were
built in a box about the size of a scope, and appeared very
similar.  They only had 1k or 4k memories, which we built
ourselves.

About 15 years ago I designed a similar system.  It used a 64180,
some memory, and the front-end A/D converters.  It dumped memory
periodically to a remote PC for display, using LZW compression for
transmission.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Pre-emptive scheduler

Quoted text here. Click to load it

I assume these were big state machines with the next address stored
into each memory word ?

Paul


Re: Pre-emptive scheduler
Quoted text here. Click to load it

They were big state machines, but the memory was purely for data.
Several systems would normally be running at once.  Computers are
much simpler.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Pre-emptive scheduler
Quoted text here. Click to load it

AFAIK there a very little CPUs where you have to save the stack, e.g.
the system stack of c16x or an 6502 because one these CPU most
languages use normaly two stacks, one for the CPU (jsr/rts) and one
for the language (local variables).


---
42Bastian
Do not email to snipped-for-privacy@yahoo.com, it's a spam-only account :-)
We've slightly trimmed the long signature. Click to see the full one.
Re: Pre-emptive scheduler
On Fri, 17 Oct 2003 20:58:30 -0400, "Michael N. Moran"

Quoted text here. Click to load it

I'm chiming in late on this, but ...

Most 8-bit and some 16-bit pocessors restrict the hardware managed
stack to a fixed location - ie. the stack register is just an 8 or 16
bit offset.

If the fixed hardware stack is small (e.g., 6502) the entire stack may
have to be copied in and out at each context switch.  If the fixed
stack is large enough (e.g., 65816), you can create multiple logical
stacks within the extent and switch stacks  just by changing the stack
offset.

If the base address of the stack is adjustable or the memory model is
flat so the stack register is really just a pointer, then you have the
same case as the large fixed stack ... you switch stacks just by
changing the stack register.

George

Re: Pre-emptive scheduler
Quoted text here. Click to load it

My intended point was to dispute the implication that in
context switching in a pre-emptive multi-tasking kernel is
language specific (e.g. C) or that it requires the
copying of stack frames, and to assert instead that
preemptive context switching is processor dependent.

I certainly do not contend the fact that there are smaller
embedded processors (even popular and pervasive processors)
that carry this burden. I was simply debating the overly
broad statement
"...premptive multitaskers have a significant overhead ..."
for the record.

cheers,
mike


--
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
We've slightly trimmed the long signature. Click to see the full one.
Re: Pre-emptive scheduler
On Mon, 27 Oct 2003 09:37:53 -0500, "Michael N. Moran"

Quoted text here. Click to load it

Sorry for the misunderstanding.  My interpretation was the OP thought
context switching was particularly heavy when stack frames had to be
copied and  that you disagreed with this or were unaware that copying
might be required.   Most assuredly context switching is processor
dependent and is independent of development language.

WRT the OP's comment about "C with stack frames", framing does
increase the runtime size of the stack and 'C' is one of the few
languages whose compilers routinely allow control over stack framing.

Also, although it wasn't indicated, the OP might be using a 'C'
compiler that has built in support for tasking.  The couple I have
seen for 8-bit micros and DSPs did copy the stack in/out during a
context switch and it was possible to save significant time by not
framing.

George

Re: Pre-emptive scheduler
Quoted text here. Click to load it

[Rummage around for OS professor hat. Got it.]

A schedule is a software construct that is usually a part of an Operating
System. The primary purpose of a schedule is to select the next process
or job for execution on the CPU.

A pre-emptive scheduler has the ability to interrupt a running (and not
finished) job and replace it with another job. While a non-premptive scheduler
gives the scheduled job unlimited use of the CPU until it requests that
another job be run (generally the request is called a yield).

Quoted text here. Click to load it

For pre-emption there must be some hardware mechanism to cause the interrupt.
Generally this is some type of timer going off. But the actual scheduling
process occurs in software so...

Quoted text here. Click to load it

This is where the scheduling code would reside.

BAJ

Re: Pre-emptive scheduler
Quoted text here. Click to load it

There are also attempts to move the scheduler into hardware (AFAIK
this years microprocessor forum showed such).

---
42Bastian
Do not email to snipped-for-privacy@yahoo.com, it's a spam-only account :-)
We've slightly trimmed the long signature. Click to see the full one.
Re: Pre-emptive scheduler

Quoted text here. Click to load it


It's not the processor, it's what you do with it! You can use the
Pentium with RTLinux, ecos, ucos, etc.- I'm sure you'll agree that they
are embedded OS's.

And as for the 8051, well I've been using multitasking on those for
years, with 8k of EPROM and 2k of RAM. And on the 6801 (which I think is
a sort of primitive 6811) and 6809 before that!

Paul Burke


Re: Pre-emptive scheduler

Quoted text here. Click to load it

    You're right, I was focusing narrowly and readily admit that the term
"embedded system" is very subjective.
 
Quoted text here. Click to load it

    I, too.  In fact we've multitasked on the 8051 without additional RAM.
Of course the tasks were simple but I agree, it is quite feasible.

-- Regards, Albert
----------------------------------------------------------------------
AM Research, Inc.                  The Embedded Systems Experts
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------


Site Timeline