Pre-emptive scheduler

For an example of 8080/z80 task switching, see the routines "trapit" and "run" in the source code (DDTZ.MAC) for ddtz27. Interruption to and from a debugger is very definitely a task switch, with the additional complication of clearing and setting traps.

The switch involves saving all registers, in addition to the stack switch. The order of performance is important, to avoid altering any flags. In addition the switching code must be treated as a critical section and forbid any interrupts.

ddtz27.zip can be found at:

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
 Click to see the full signature
Reply to
CBFalconer
Loading thread data ...

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-

Reply to
Rick Lones

The definition of an "embedded system" is both subjective and a large gray area. Originally (like Constitutional "Original Intent") an "embedded system" was purely a machine control application often without display or keyboard such as a traffic signal controller or, at the high end, a numerical machine controller. The first application was typically an 80489 while the second an 8080 s-100 machine.

Then, as power and complexity grew, 80188's, PACE-16's, 16016's through

32032's, and now ARM's and Pentiums and beyond. A second track was marketing hype, shove a desktop motherboard into a NEMA-4 enclosure and call that, too, an 'embedded system.'

Our thresholds will undoubtedly differ. Mine requires a single-chip solution.

While I haven't viewed your kind offering, your explanation validates my original point: task switching can have a serious performance impact depending on methodology and/or language. If you compare the above description with a round-robin multitasker, which only requires one jump and, depending on implementation, one flag or pointer, you can easily see the performance gains possible.

Time-slice, premptive, multitasking has about the worst performance possible. That is what makes me scoff at the term "Embedded Windows."

Were you aware that the FDA has ruled against the use of windows in any life-support equipment?

-- Regards, Albert

---------------------------------------------------------------------- AM Research, Inc. The Embedded Systems Experts

formatting link
(916) 780-7623

----------------------------------------------------------------------

Reply to
Albert Lee Mitchell

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

formatting link
(916) 780-7623

----------------------------------------------------------------------

Reply to
Albert Lee Mitchell

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

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

formatting link
(916) 780-7623

----------------------------------------------------------------------

Reply to
Albert Lee Mitchell

... snip ...

This difference from cooperative tasking is largely because the cooperative system can prepare itself for a task switch, by saving everything in its own data space. You are largely moving the time from the master system to each of the subsidiary processes, with much code duplication.

However cooperative systems can exist on very primitive processors, where time slicing is essentially impossible. I have implemented such on PICs. The penalty is that the individual processes must follow very strict rules, including maximum path length.

No. Where are references for this?

--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
 Click to see the full signature
Reply to
CBFalconer

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

Reply to
Paul Keinanen

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 (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
 Click to see the full signature
Reply to
CBFalconer

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

Paul

Reply to
Paul Keinanen

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

Reply to
Paul Burke

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

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.

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 (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply to
Hans-Bernhard Broeker

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 (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
 Click to see the full signature
Reply to
CBFalconer

Yes and no. Yes cooperative tasking is faster, no it needn't incur additional overhead or code duplication.

Direct from the Surgeon General some 5 years ago at a Medical Electronics convention in Anaheim, CA. During the convention, as usually happens, a number of seminars were being held. My client sent me to two, one specifically for embedded systems in life support. The cost was significant so most attendees were individuals or pairs except for this one group of about a dozen or so who congregated on one side of front center.

After the third day the leader of that group timidly asked a question something like: "Is my understanding correct then that Windows cannot be verified and validated for FDA authorization." The surgeon general conferred with this staff and replied, "Correct."

A dozen (or more) jaws hit the ground and the room was deathly quiet. The message is that life-support systems cannot use any flavor of Windows. Perhaps that will change in the future but at this time you have to use a verifiable operating system and somehow validate it too.

-- Regards, Albert

---------------------------------------------------------------------- AM Research, Inc. The Embedded Systems Experts

formatting link
(916) 780-7623

----------------------------------------------------------------------

Reply to
Albert Lee Mitchell

Agreed. In fact that's been my position from the beginning.

True.

True, what's your point?

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

formatting link
(916) 780-7623

----------------------------------------------------------------------

Reply to
Albert Lee Mitchell

You're right, I was focusing narrowly and readily admit that the term "embedded system" is very subjective.

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

formatting link
(916) 780-7623

----------------------------------------------------------------------

Reply to
Albert Lee Mitchell

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

Mike Harding

Reply to
Mike Harding

I believe that is correct. The response by Rick was great, and short too!

Two things that need to be documented, and/or available when selecting a pre-emptive or a non pre-emptive scheduler/OS:

  1. ALL single threaded calls, APIs, and lib routines should specify if they

CAN be raised to the same execution/task priority as the calling task.

  1. No calls or library routines should require resources that may not be available, or that can be locked by a lower priority task, or some type of error message/status should be displayed to allow a graceful way to wait or die!

Note: The embedded programmer can screw this up even easier than the scheduler/OS :-)

These are not all of the problems, but they cover most of the big ones when

developing and/or switching between the two types (IMHO). Many real-time programs end up doing everything themselves to work-around these types of problems, simply because it's not working and documentation isn't available.

Does the term "double buffered" ring any bells? (ie-DOS,Win3.x,...) Or possibly "My Windoze system locked up again!" ?

Flames or jokes welcomed, we could keep this going and make an embedded cookbook!

Gary

Reply to
gary drummond

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

Reply to
George Neuner

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
 Click to see the full signature
Reply to
Michael N. Moran

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

Reply to
George Neuner

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.