Reply by Hans-Bernhard Broeker●October 1, 20042004-10-01
CBFalconer <cbfalconer@yahoo.com> wrote:
> Hans-Bernhard Broeker wrote:
> > I think you're missing the point. If the CPU needs for the
> > high-priority tasks ever become so high that a strictly
> > priority-oriented scheduler doesn't have any time left to distribute
> > to task below a certain level, then there's no room left for
> > gracefully doing something clever.
[...]
> I don't think it is quite that simple. In general, low priority
> tasks are low priority because the presence of buffers means that
> they can wait.
Or because what they're doing *is* low-priority work, in the actual
meaning of th word, i.e. it's not really important.
> So the failure condition is not that the low priority is waiting
> indefinitely, it is that the high priority finds that no further
> buffer space is available.
But changing scheduling algorithms wouldn't avoid that pitfall, it'd
just change the symptoms: from a (starved) low-priority task not
emptying the buffer to a (starved) high-priority task losing some of
the input it's supposed to put into that buffer.
The general FUBAR character of the situation doesn't change one bit if
you exchange the scheduler --- a "not enough CPU power available to do
everything that needs to be done" condition doesn't go away all by
itself.
--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply by CBFalconer●October 1, 20042004-10-01
Hans-Bernhard Broeker wrote:
>
... snip ...
>
> I think you're missing the point. If the CPU needs for the
> high-priority tasks ever become so high that a strictly
> priority-oriented scheduler doesn't have any time left to distribute
> to task below a certain level, then there's no room left for
> gracefully doing something clever. You've just hit the limit, and
> there *is* no graceful way of doing that any more than there is for,
> say, a race car to "gracefully" slide off the track and into the
> fenders because the driver tried to make a turn too fast. For those
> who watched TV in the 80's, the background story of a certain "Max
> Headroom" might ring a bell here.
I don't think it is quite that simple. In general, low priority
tasks are low priority because the presence of buffers means that
they can wait. So the failure condition is not that the low
priority is waiting indefinitely, it is that the high priority
finds that no further buffer space is available.
--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Reply by Hans-Bernhard Broeker●October 1, 20042004-10-01
Elko Tchernev <etchernevnono@acm.org> wrote:
> In such cases, it seems to me that the priority queue approach will
> not degrade gracefully, but can shut down the low-priority tasks for
> long time periods.
I think you're missing the point. If the CPU needs for the
high-priority tasks ever become so high that a strictly
priority-oriented scheduler doesn't have any time left to distribute
to task below a certain level, then there's no room left for
gracefully doing something clever. You've just hit the limit, and
there *is* no graceful way of doing that any more than there is for,
say, a race car to "gracefully" slide off the track and into the
fenders because the driver tried to make a turn too fast. For those
who watched TV in the 80's, the background story of a certain "Max
Headroom" might ring a bell here.
The alternative to starving low-priority tasks in such a situation is
to starve *high* priority ones. Which, if the word "priority" means
anything at all, would be clearly even worse.
Actually, this is why one school of watchdog implementation says that
the watchdog kicking task should have the lowest priority of all ---
in a situation like this, it'll be starved, and the doggy will bite
because there's nothing else left to be done that could make any
sense.
--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
> The logical conclusion from what you say is, that there's
>essentially two priority levels - the highest, which is the "must have"
>level, and all others - which become "nice to have", and _can_ be
>starved by the highest.
I am talking about realtime systems, which is the place that you
typically use strictly priority based scheduling. Quite a few embedded
systems are realtime, although not all realtime systems are embedded.
In a realtime system, the program is faulty, if the results do not
arrive in time when they are needed, no matter how correct the
calculations themselves are.
When there is not enough resources, do you use some "fair" scheduling
to avoid starving the low priority task and as a consequence the high
priority task does not meet the deadline ? Such system would be
useless for the intended purpose.
In a typical realtime system, the lowest priority null (idle) task
could consume more than 50 % on average over a long period. At periods
of high demand, the null task will be starved. You cold replace the
null task with a some other low priority "nice to have" work that can
be starved in the same way.
>All you say about computing power is true,
>however, sometimes you can't anticipate the actual computing
>requirements in the field, or maybe you _lack_ computing power to handle
>the theoretically maximum throughput, and are only able to handle the
>average (with buffering, let's say).
Buffering in a real time system is acceptable when the length of a
load burst as well as the frequency of occurrence of such bursts are
well defined.
For instance it is OK in a half duplex serial protocol to receive
bytes at a higher rate than the higher level could handle, since the
maximum length of the received frame is known and thus a sufficiently
large buffer can be allocated in the receiving routine to avoid
overwriting. Since in a typical half duplex protocol, the next request
will not arrive, before a response has been sent to the previous
request.
In some situation it may even be acceptable to delay transmitting the
response as a flow control method, but still the routines that handles
the reception of individual bytes must be fast enough to receive bytes
at the rate the line speed allows.
>In such cases, it seems to me that
>the priority queue approach will not degrade gracefully, but can shut
>down the low-priority tasks for long time periods. The round-robin with
>priority (where priority determines how long a task can run before being
>pre-empted, or switches on its own) offers more graceful degradation in
>high-load circumstances. It has the flexibility of distributing the CPU
>time between low-priority, continuously-running background tasks, and is
>much simpler to implement.
Such systems are usable only in situations, in which you have _no_
firm deadlines.
Paul
Reply by Elko Tchernev●September 30, 20042004-09-30
Paul Keinanen wrote:
> On Wed, 29 Sep 2004 19:01:04 -0400, Elko Tchernev
> <etchernevnono@acm.org> wrote:
>
>
>> How does any scheme that relies on priority queues avoid starvation
>>of low-priority tasks?
>
>
> Why should it even attempt to do that ?
>
> It is up to the designer of the system to ensure that there are enough
> computing power available to handle all incoming events at the maximum
> rate possible. For instance the maximum rate for UART interrupts
> depend on the serial line bit rate, the number of Ethernet end of
> frame interrupts depends on the speed of the link and the minimum
> message size and the number of timer interrupts depends on the crystal
> frequency and what division ratios are programmed into the counters.
>
> If sufficient computing power can not always be provided, the system
> designer has to decide _in_advance_ what functionality _is_ sacrificed
> during congestion. Typical examples for functionality to be sacrificed
> are various "nice to have" status displays etc., which does not
> affect the main purpose of the system.
>
> Thus, such "nice to gave" features should be put on the lowest
> priority, so if there is a high demand for processing power, these
> functionalities are automatically sacrificed by starving of resources
> and no extra application logic is required for that.
>
The logical conclusion from what you say is, that there's
essentially two priority levels - the highest, which is the "must have"
level, and all others - which become "nice to have", and _can_ be
starved by the highest. All you say about computing power is true,
however, sometimes you can't anticipate the actual computing
requirements in the field, or maybe you _lack_ computing power to handle
the theoretically maximum throughput, and are only able to handle the
average (with buffering, let's say). In such cases, it seems to me that
the priority queue approach will not degrade gracefully, but can shut
down the low-priority tasks for long time periods. The round-robin with
priority (where priority determines how long a task can run before being
pre-empted, or switches on its own) offers more graceful degradation in
high-load circumstances. It has the flexibility of distributing the CPU
time between low-priority, continuously-running background tasks, and is
much simpler to implement.
Reply by Paul Keinanen●September 30, 20042004-09-30
> How does any scheme that relies on priority queues avoid starvation
>of low-priority tasks?
Why should it even attempt to do that ?
It is up to the designer of the system to ensure that there are enough
computing power available to handle all incoming events at the maximum
rate possible. For instance the maximum rate for UART interrupts
depend on the serial line bit rate, the number of Ethernet end of
frame interrupts depends on the speed of the link and the minimum
message size and the number of timer interrupts depends on the crystal
frequency and what division ratios are programmed into the counters.
If sufficient computing power can not always be provided, the system
designer has to decide _in_advance_ what functionality _is_ sacrificed
during congestion. Typical examples for functionality to be sacrificed
are various "nice to have" status displays etc., which does not
affect the main purpose of the system.
Thus, such "nice to gave" features should be put on the lowest
priority, so if there is a high demand for processing power, these
functionalities are automatically sacrificed by starving of resources
and no extra application logic is required for that.
Paul
Reply by Jonathan Kirwan●September 29, 20042004-09-29
>How does any scheme that relies on priority queues avoid starvation
>of low-priority tasks?
In general? This cannot be answered. But in specific circumstances, it's
rather easy to imagine useful cases. Usually, the higher priority processes
will wait for messages or semaphores and are related to low-level hardware
interrupt routines which may put something in a buffer to be serviced by the
high priority routine (which the low-level code awakens when it captures
something to be processed.) In this case, the reason they are high priority is
so that they can pay attention to incoming data in a timely way and not so they
can just hog the CPU. Until data arrives, they aren't in the ready queue.
>This seems to be an inherent disadvantage versus
>the round-robin varying-time schemes.
Round robin is usually just time-based preemption when a quantum expires. Round
robin can operate, even in cases where different priorities are permitted for
processes, when more than one of the highest priority, ready-to-run processes
have the same priority. Admittedly, round robin does depend on at least two
processes having the same priority (or no priorities, at all) but round robin
and priority support aren't inherently mutually exclusive, unless all processes
always have different priorities assigned to them.
Jon
Reply by Elko Tchernev●September 29, 20042004-09-29
Martin Schoeberl wrote:
>>Why should the OS need to get regular momentary control of the CPU in
>>a preempt system ? The only reason for a reschedule of the tasks is
>>when a higher priority task has changed state from blocked (waiting
>>for something) to runnable. There are mainly two situations this can
>>happen, an other task activates a signal or sends a message that the
>>blocked task is waiting for or an interrupt service routine satisfies
>>a wait condition.
>
>
> The main purpose of the timer interrupt is representation of time and
> release of periodic tasks (that are very common e.g. control loops). The
> periodic tasks gives up execution after the work is done and blocks until
> the next period.
>
> One common implementation is a clock tick. The interrupt occurs at a
> regular interval (e.g. 10 ms) and a decision has to be taken whether a
> task has to be released. This approach is simple to implement, but there
> are two major drawbacks: The resolution of timed events is bound by the
> resolution of the clock tick and clock ticks without a task switch are a
> waste of execution time.
>
> A better approach is to generate timer interrupts at the release times of
> the tasks. The scheduler is now responsible to reprogram the timer after
> each occurrence of a timer interrupt. The list of sleeping threads has to
> be searched to find the nearest release time in the future of a higher
> priority thread than the one that will be released now. This time is used
> for the next timer interrupt.
>
How does any scheme that relies on priority queues avoid starvation
of low-priority tasks? This seems to be an inherent disadvantage versus
the round-robin varying-time schemes.
Reply by Martin Schoeberl●September 29, 20042004-09-29
> Why should the OS need to get regular momentary control of the CPU in
> a preempt system ? The only reason for a reschedule of the tasks is
> when a higher priority task has changed state from blocked (waiting
> for something) to runnable. There are mainly two situations this can
> happen, an other task activates a signal or sends a message that the
> blocked task is waiting for or an interrupt service routine satisfies
> a wait condition.
The main purpose of the timer interrupt is representation of time and
release of periodic tasks (that are very common e.g. control loops). The
periodic tasks gives up execution after the work is done and blocks until
the next period.
One common implementation is a clock tick. The interrupt occurs at a
regular interval (e.g. 10 ms) and a decision has to be taken whether a
task has to be released. This approach is simple to implement, but there
are two major drawbacks: The resolution of timed events is bound by the
resolution of the clock tick and clock ticks without a task switch are a
waste of execution time.
A better approach is to generate timer interrupts at the release times of
the tasks. The scheduler is now responsible to reprogram the timer after
each occurrence of a timer interrupt. The list of sleeping threads has to
be searched to find the nearest release time in the future of a higher
priority thread than the one that will be released now. This time is used
for the next timer interrupt.
Martin
----------------------------------------------
JOP - a Java Processor core for FPGAs:
http://www.jopdesign.com/
Reply by Spehro Pefhany●September 27, 20042004-09-27
On Mon, 27 Sep 2004 09:41:30 GMT, the renowned CBFalconer
<cbfalconer@yahoo.com> wrote:
>Spehro Pefhany wrote:
>> <radsett@junk.aeolusdevelopment.cm> wrote:
>>
>... snip ...
>>
>>> Pre-emption requires a timer? I understand time-slicing would
>>> but surely you can do preemption w/o a timer. Useful yes.
>>> Necessary?
>>
>> I don't see how. However, it need not consume the resource
>> entirely- other stuff could be chained off the same timer
>> interrupt.
>
>How little ingenuity show up these days. Back when many systems
>had neither timers nor interrupts, the thing to do was intercept a
>common system call, such as checking the status of an input
>keyboard, and count these to generate a timer tick.
That only show up because it's generated by a hardware timer interrupt
(probably one out of many interruts). Don't let all the layers of
software obscure the true inner workings.
Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
speff@interlog.com Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com