Pre-emptive scheduler

In article , Rick writes

Is this a home work question?

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

\/\/ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

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.

The latter. The controller hardware helps with the implementation, though, e.g. by having such things as timed interrupts.

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

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

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

This is where the scheduling code would reside.

BAJ

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

Thanks Hans! That definitely cleared my concepts about pre-emptive and non pre-emptive scheduling

Rick

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

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.

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

(916) 780-7623

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

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
Kennesaw, GA 30144

"... abstractions save us time working, but they don't
  save us time learning."
Joel Spolsky, The Law of Leaky Abstractions

The Beatles were wrong: 1 & 1 & 1 is 1

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

Right, we said that same thing.

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

(916) 780-7623

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

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

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.

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

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
Kennesaw, GA 30144

"... abstractions save us time working, but they don't
  save us time learning."
Joel Spolsky, The Law of Leaky Abstractions

The Beatles were wrong: 1 & 1 & 1 is 1

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

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 bastian42@yahoo.com, it's a spam-only account :-)
Use @epost.de instead !

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 bastian42@yahoo.com, it's a spam-only account :-)
Use @epost.de instead !

I think this one is called cooperative.

--
42Bastian
Do not email to bastian42@yahoo.com, it's a spam-only account :-)
Use @epost.de instead !

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

--
42Bastian
Do not email to bastian42@yahoo.com, it's a spam-only account :-)
Use @epost.de instead !

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

(916) 780-7623

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

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

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

[...]

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

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