Pre-emptive scheduler

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

Translate This Thread From English to

Threaded View
Hi,

What really is a pre-emptive or a non pre-emptive scheduler? Are these
parts of the microcontrollers or the part of software that resides in
the ROM? Thanks

Rick


Re: Pre-emptive scheduler
writes
Quoted text here. Click to load it
Is this a home work question?

/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England    /\/\/\/\/\
/\/\/ snipped-for-privacy@phaedsys.org       www.phaedsys.org \/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

Re: Pre-emptive scheduler



Quoted text here. Click to load it

Not at all. It's something I've read about a lot in text and heard about
a lot in theory, but I still fail to grasp the real concept.

Rick


Quoted text here. Click to load it


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


Pre-emptive scheduling works by a 'master' task unconditionally
interrupting the current task whenever the master thinks it's time for
some other task to get to work.  Non pre-emptive scheduling relies on
each task yielding its control of the processor on its own,
i.e. *voluntarily*.

Neither of the concepts is typically found in its pure form, in
embedded systems.  Non Pre-emptive schedulers still have pre-emptive
watchdogs, and pre-emptive schedulers may allow tasks to stop the
master from pre-empting them by disabling interrupts --- but only for
good reasons, and for short time intervals.

Quoted text here. Click to load it

The latter.  The controller hardware helps with the implementation,
though, e.g. by having such things as timed interrupts.
--
Hans-Bernhard Broeker ( snipped-for-privacy@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Re: Pre-emptive scheduler
Thanks Hans! That definitely cleared my concepts about pre-emptive and
non pre-emptive scheduling

Rick


Re: Pre-emptive scheduler

Quoted text here. Click to load it


I think this one is called cooperative.
---
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

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.

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





Re: Pre-emptive scheduler

Quoted text here. Click to load it

    Good explanation.  To continue the thread, premptive multitaskers have
a significant overhead which should be considered.  Especially when running
C with stack frames, large amounts of data must sometimes be relocated to
a safe area and the next task moved into the working area.  Each context
change repeats this process.

    On the other hand some languages permit an almost instantaneous task
switch in some non-premptive scheduler (AKA cooperative, round-robin, et al.)
 
Quoted text here. Click to load it

    Non premptive schedulers often use a watchdog but not for prempting the
process, it's usually a hard reset.  Recovery from a stalled process in
embedded systems most often go through a cold boot to re-initialize the
system since it's impossible to determine why the process stalled or how
to handle a recovery.

    A non-premptive scheduler is also called a "round-robin multitasker"
among other terms.
 
Quoted text here. Click to load it

    Again, not all multitaskers require timers.  Much depends on how the code
was written and what language was used.

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

Pardon me if I disagree, but the preemptive systems that I
have implemented are not at all dependent upon the programming
language (e.g. C). The amount of state saved in a context
switch is a function of the specific micro-processor.

I would add that only time-sliced operating systems require
a periodic scheduler. In my experience, these are not the
kind of preemptive schedulers typically used in embedded
systems. Certainly, there are periodic tasks in such systems,
but they are generally not achieved through time-slicing.

The systems that I am accustomed to using have an event
driven priority based scheduling mechanism. In such a system,
any interrupt (not just a "quantum" interrupt) that causes
a higher priority task (typically blocked waiting for I/O)
to become "ready" will preempt the current task. Of course,
periodic timers interrupts qualify as well as myriad other
I/O device interrupts.


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

Quoted text here. Click to load it

    It seems that we disagree then.  When stack frames are used context
switch overhead becomes quite significant.  This is independent of
multitasker.

Quoted text here. Click to load it

    Right, we said that same thing.
 
Quoted text here. Click to load it

    Yes, there are probably more than the three examples discussed here.  I
have no experience with your variety, only premptive and cooperative.  In
a cooperative multitasker switch overhead can be under a half-dozen
instructions.  I've never seen any other methodology remotely as quick.
Especially on 8-bit micros.
 
-- Regards, Albert
----------------------------------------------------------------------
AM Research, Inc.                  The Embedded Systems Experts
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------


Re: Pre-emptive scheduler
On Sun, 19 Oct 2003 02:14:14 -0700, Albert Lee Mitchell

Quoted text here. Click to load it

This is true only if you talk about cache misses or reloading memory
mapping registers.

However, in a simple processor without caches or memory mapping
hardware, a context switch is just changing the stack pointer.
Reactivation of a new task after that, does not cost more than a
return from an interrupt.

Of course, if the cost of an interrupt is significant, then the cost
of a task switching is also significant.

Paul
 

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

When an interrupt occurs (or system-call/trap instruction
is executed), the kernel saves the state of the task by
copying the (processor specific) registers either to the
task's stack or (on some processors) to the "Task Control
Block (TCB)". Among the registers copied are the Stack Pointer.
The registers for the newly scheduled task are then copied
into the processor registers, and the new task is executed.
At no point in this sequence is there any language specific
"C" notion.

Quoted text here. Click to load it

Hmm. What I've described *is* preemptive. Its just not time-sliced.

Quoted text here. Click to load it

I agree that cooperative multitasking is generally faster
than preemptive multitasking. However, one also looses the
advantages of preemptive multi-tasking. Its an engineering
trade-off.

As often happens in this news group, much of our disagreement
has to do with the very broad persuit of "embedded" software.
Most of my work is with large and medium complexity 32-bit
embedded systems in which multi-tasking is an issue of
complexity management. However, I have also written very
large 8-bit systems (bank-switched 68HC11 yuk!) which
operated quite well using a preemptive kernel. Unless there
are specific real-time constraints where a preemptive
multitasking kernel cannot be tolerated, I will always
choose the preemptive approach.



--
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
Quoted text here. Click to load it

Esp. because whether or not pre-emption takes place is a question of
design.
But (doing support for an RTOS) I found that many programmers get
trapped because they "forget" (!?) that they're using an pre-emptive
system and design their software upon priorities instead of IPC.

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


You're missing the idea of CPUs where you don't have to copy the stack
status in the first place --- you can just *change* the address where
the CPU expects the stack to be, so each pre-empted context has its
own independant stack.  On such systems, constext switching can be
done by just moving around the stack pointer registers.

Which points back to the CPU as the main instance that decides how
complicated context switches actually are.


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

    Not missing a thing, the cpu's you speak of are not those with which I
work or consider "embedded systems."  Granted that the term has been badly
corrupted by marketing but I don't consider a Pentium to be an "embedded"
controller.

    6811's, 8051's, 80C16x's, etc., are embedded controllers by definition.
In their realm it is difficult or impossible for a number of reasons.
 
     If you consider Intel x86/Windows to be an "Embedded System" then I'd
agree otherwise I stand by my statements.
 
-- Regards, Albert
----------------------------------------------------------------------
AM Research, Inc.                  The Embedded Systems Experts
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------


Re: Pre-emptive scheduler
snipped-for-privacy@amresearch.com says...
Quoted text here. Click to load it

Would you consider e.g. Z80-based CPUs "embedded systems?" They
have a 16-bit stack pointer, making the task switching by stack
pointer swapping that Hans-Bernhard is talking about eminently
doable.

Christer Ericson
Sony Computer Entertainment, Santa Monica

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

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:

  <http://cbfalconer.home.att.net/download/cpm/

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

    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.
 
Quoted text here. Click to load it

    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
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------

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

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.

Quoted text here. Click to load it

No.  Where are references for this?

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

    Yes and no.  Yes cooperative tasking is faster, no it needn't incur
additional overhead or code duplication.
 
Quoted text here. Click to load it

    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
http://www.amresearch.com (916) 780-7623
----------------------------------------------------------------------


Site Timeline