Prev: A 16-bit/32-bit microprocessor specifically for UAV purpose
Next: What is Bit Spread?
From: Didi on 16 Apr 2010 16:33
On Apr 16, 9:37 pm, D Yuniskis <not.going.to...(a)seen.com> wrote:
> ...
> Note the non-believers who complained of my use of dynamic
> memory allocation in RT systems.  :>

It does not take much belief to see the usefulness of dynamic memory
allocation, just some (not very high) complexity of the task at
hand :-) .

>
> > So a task switcher that has an unpredictable task switch time can still
> > be real time _if_ that unpredictable switch time has an upper bound.
>
> Yes.  See above.  OTOH, if that scheduler examines *every* task in
> the system -- even those known to be "not READY" -- then its
> performance will be abysmal.

I believe most people put too much into task switch timing
for real time. While it has to be kept in sane limits, it is rarely
if ever the system limiting factor. Interrupt latency is.

Vladimirs original question was about fairness of lower priority
tasks. How I have implemented it in DPS (around 1994 and nearly
unchanged
since because of no necessity) can be looked up. I have yet to see
a scheme which could rival this one (which I have likely reinvented,
by 1994 all that stuff had all been long beaten to death; but
reinventing the obvious is often the fastest way :-) ).

Dimiter

------------------------------------------------------
Dimiter Popoff Transgalactic Instruments

http://www.tgi-sci.com
------------------------------------------------------
http://www.flickr.com/photos/didi_tgi/sets/72157600228621276/

Original message: http://groups.google.com/group/comp.arch.embedded/msg/2466b8305659745b?dmode=source
From: George Neuner on 17 Apr 2010 03:38
On Fri, 16 Apr 2010 10:06:32 -0700, D Yuniskis
<not.going.to.be(a)seen.com> wrote:

>Hi George,
>
>George Neuner wrote:
>> You don't have to remember much beyond what an interrupted task was
>> doing - it's register context - and information needed for scheduling:
>> priority, trigger events, time stamps, etc. Deadline scheduling needs
>
>You also need to track any resources the "task" (again, lets not
>pick nits on terms) owns. E.g., if it has taken a lock, it *still*
>holds the lock even while preempted! And, of course, other
>"physical resources" (memory).

Most RTOSes (though not all) define a "task" as something that is
lighter weight than the traditional notion of an OS process. I've
seen everything from register context threads to VMM separated
processes referred to as "tasks".

Things like memory typically aren't considered for scheduling,
although they could be. Many desktop/server OSes have a 2 level
scheduler: a primary that schedules register context threads and a
secondary that schedules processes (deciding whether the threads in a
process are included in the set scheduled by the primary.
This kind of separation was needed back in the days of swapping when
it was a big deal to restart a non-resident process. Demand paging
has all but eliminated memory as a factor for scheduling.


>> a shitload of scheduling data, but no RTOS I am aware of actually does
>> deadline scheduling.
>
>Look at MARTE and ERIKA. There may be others (as well as
>some that aren't "commercially available"). The problem is
>defining how generic you want that "deadline scheduling"
>to be.

I couldn't find a link to ERIKA, just to some projects that claim to
use it. MaRTE's EDF scheduling appears to be slightly more
predictable than Ada's, but Ada's task scheduler isn't particularly
sophisticated to begin with

In a real deadline scheduling system, when a task pends on an event
the scheduler needs to know:

- the actual deadline. This can take 2 forms: a maximum delay
before scheduling a run-to-completion task, or for a time sliced
task the time required to compute the response and the maximum
cutoff time for producing the response.
- whether the deadline is "hard" or "soft". It is an error to miss
a "hard" deadline. A "soft" deadline is a best effort response.
- how to deal with a deadline which is missed: e.g., ignore it,
restart the task, resume the task, etc.
- the priority of the task
- any ad hoc. other things the scheduler needs to know

A deadline scheduler has to guarantee that all "hard" deadlines are
met (for suitable hardware) and make best effort at meeting all the
"soft" deadlines. In a time slicing system the scheduler has to
decide which ready tasks can safely be delayed another quantum in
order to pick one to run.

As I said before, I know of no available RTOS that actually implements
deadline scheduling. It isn't simple, it is a global minimization
function on all the simultaneous time and resource constraints ... and
nobody does it. Nobody ever did it except maybe as a research
project. At best, RTOSes provide priority preemption and a promise of
maximum scheduling delay. If the application fits the predictability
model that this presents, that's fine - but it doesn't work for all
applications.

George
From: Vladimir Vassilevsky on 17 Apr 2010 06:29


George Neuner wrote:

> As I said before, I know of no available RTOS that actually implements
> deadline scheduling. It isn't simple, it is a global minimization
> function on all the simultaneous time and resource constraints ... and
> nobody does it. Nobody ever did it except maybe as a research
> project. At best, RTOSes provide priority preemption and a promise of
> maximum scheduling delay. If the application fits the predictability
> model that this presents, that's fine - but it doesn't work for all
> applications.

Sophisticated scheduling algorithm is no cheap to compute. While
optimizing the order of the tasks, it consumes the CPU resources by
itself. So, there is not much that could be gained compared to the
simplistic solutions like ratemonotonic; why bother?

In practice, there are few realtime tasks and many tasks that can wait;
the OS should not add the unnecessary overhead to every task. In the
other words, if you need this particular task to be realtime, you should
take care of it, not OS.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
From: D Yuniskis on 17 Apr 2010 14:52
Hi George,

George Neuner wrote:
> On Fri, 16 Apr 2010 10:06:32 -0700, D Yuniskis
> <not.going.to.be(a)seen.com> wrote:
>
>> George Neuner wrote:
>>> You don't have to remember much beyond what an interrupted task was
>>> doing - it's register context - and information needed for scheduling:
>>> priority, trigger events, time stamps, etc. Deadline scheduling needs
>> You also need to track any resources the "task" (again, lets not
>> pick nits on terms) owns. E.g., if it has taken a lock, it *still*
>> holds the lock even while preempted! And, of course, other
>> "physical resources" (memory).
>
> Most RTOSes (though not all) define a "task" as something that is
> lighter weight than the traditional notion of an OS process. I've

Most use the term *thread* to reference "lightweight process". :>
I use "thread" to describe active objects while "process" is a
(passive) container for resources (including threads).

A "task" can be some abstract concept pertaining to a "job
to be done" (I have used the term "job" in the past, as well).

Since all of these terms are nonstandard (a classic UNIX process
is single threaded, more modern Eunices support multithreaded
processes, "process control" divorces the term from this
context entirely, etc.), I always add the caveat to avoid
nit picking -- and, alert the reader that his idea of task/
process/thread/etc. may not coincide with the one being loosely
used, here.

> seen everything from register context threads to VMM separated
> processes referred to as "tasks".
>
> Things like memory typically aren't considered for scheduling,
> although they could be.

I added memory as it was an example of a *resource* that needs
to be "remembered" just like other parts of the "task's" state.
Your comment:

"You don't have to remember much beyond what an interrupted
task was doing - it's register context - and information
needed for scheduling: priority, trigger events, time stamps,
etc."

enumerated the sorts of things that have to be "remembered" in
a task's state. "It's register context", "what it was doing"
"[scheduling information]", etc. I was contending that there
are lots of *other* things that have to be "remembered" for
the task (i.e., everything that fits in the [process] container
that I alluded to).

> Many desktop/server OSes have a 2 level
> scheduler: a primary that schedules register context threads and a
> secondary that schedules processes (deciding whether the threads in a
> process are included in the set scheduled by the primary.
> This kind of separation was needed back in the days of swapping when
> it was a big deal to restart a non-resident process. Demand paging
> has all but eliminated memory as a factor for scheduling.
>
>>> a shitload of scheduling data, but no RTOS I am aware of actually does
>>> deadline scheduling.
>> Look at MARTE and ERIKA. There may be others (as well as
>> some that aren't "commercially available"). The problem is
>> defining how generic you want that "deadline scheduling"
>> to be.
>
> I couldn't find a link to ERIKA, just to some projects that claim to
> use it. MaRTE's EDF scheduling appears to be slightly more
> predictable than Ada's, but Ada's task scheduler isn't particularly
> sophisticated to begin with

Doesn't have to be sophisticated -- just predictable. :>

> In a real deadline scheduling system, when a task pends on an event
> the scheduler needs to know:
>
> - the actual deadline. This can take 2 forms: a maximum delay
> before scheduling a run-to-completion task, or for a time sliced
> task the time required to compute the response and the maximum
> cutoff time for producing the response.
> - whether the deadline is "hard" or "soft". It is an error to miss
> a "hard" deadline. A "soft" deadline is a best effort response.
> - how to deal with a deadline which is missed: e.g., ignore it,
> restart the task, resume the task, etc.
> - the priority of the task
> - any ad hoc. other things the scheduler needs to know
>
> A deadline scheduler has to guarantee that all "hard" deadlines are
> met (for suitable hardware) and make best effort at meeting all the
> "soft" deadlines. In a time slicing system the scheduler has to
> decide which ready tasks can safely be delayed another quantum in
> order to pick one to run.

The scheduler doesn't have to "guarantee" that these are met.
That's the job of the system designer. E.g., it you try to
schedule for 110% utilization, the scheduler *will* fail.

Some systems *can't* meet their deadlines 100% of the time.
This is especially true for systems with asynchronous
processing needs (event driven).

If you are designing a system that operates in steady state
all the time, then scheduling is much more predictable. E.g.,
RMA is a win, here -- though with much lower processor
utilization guarantees.

EDF is rather easy to implement and, in those systems where
"tasks" (in my "abstract" role) are in harmonious accord
with each other (e.g., you never exceed 100% utilization
even on the short term), can be quite effective.

> As I said before, I know of no available RTOS that actually implements
> deadline scheduling. It isn't simple, it is a global minimization
> function on all the simultaneous time and resource constraints ... and

You're trying to describe something that "can't work" -- with
unconstrained task requirements. E.g., I have three "tasks"
each needing 100 time units to complete and each must be
completed within 110 time units. "Coincidence" has caused
them to be started (asynchronous events!) at the same instant.
No scheduling algorithm "works" in overload.

OTOH, EDF *will* schedule all three of them properly
IN THE PRESENCE OF OTHER COMPETING TASKS *if* they
never exceed 100% utilization. (this is a relatively simple
exercise to do in your head -- and doesn't require lots of
analysis. It's analagous to a family getting ready
for work/school in the morning: "Who needs to be OUT THE DOOR
*first*? OK, *he* gets first crack at the bathroom (shared
resource). Once he's done (his deadline is met), "Who needs
to be out the door first?", again. I.e., if you don't have to
be "out the door" until afternoon, then you just aren't going
to be using the bathroom in the morning! :>

As long as the work to be done *can* be done in the time
available, EDF will make it happen. If it *can't* (i.e.,
the system is overloaded) then you're trying to have the
scheduler decide who *should* break and who *shouldn't*.

> nobody does it. Nobody ever did it except maybe as a research

Hmmm... you are aware of every RTOS in every product released?
:> Surely you are just commenting on commercial offerings?

E.g., I rely on CoW semantics in my distributed memory
system. I don't think many (any) commercial RTOS's support
this -- yet, clearly *someone* has "done it" (me! :> ).

> project. At best, RTOSes provide priority preemption and a promise of
> maximum scheduling delay. If the application fits the predictability
> model that this presents, that's fine - but it doesn't work for all
> applications.

And, if the system is overloaded, how is this "better"/worse?
From: D Yuniskis on 17 Apr 2010 15:03
Hi Vladimir,

Vladimir Vassilevsky wrote:
> George Neuner wrote:
>
>> As I said before, I know of no available RTOS that actually implements
>> deadline scheduling. It isn't simple, it is a global minimization
>> function on all the simultaneous time and resource constraints ... and
>> nobody does it. Nobody ever did it except maybe as a research
>> project. At best, RTOSes provide priority preemption and a promise of
>> maximum scheduling delay. If the application fits the predictability
>> model that this presents, that's fine - but it doesn't work for all
>> applications.
>
> Sophisticated scheduling algorithm is no cheap to compute. While
> optimizing the order of the tasks, it consumes the CPU resources by
> itself. So, there is not much that could be gained compared to the
> simplistic solutions like ratemonotonic; why bother?

Rate Monotonic doesn't guarantee the same levels of processor
utilization. It is only really useful with static priorities.
I.e., devices with fixed workloads that can be analyzed at
design time, etc. If you can get by with this, then why
use anything more complicated?

I have one MTOS that deals with things "brute force" -- context
switches are *almost* free... so, I invoke the scheduler
VERY often (e.g., more than 1KHz). Everything can run
at essentially the same "priority" and still be guaranteed
timely service (though you have to keep everything "short
and sweet" because your timeslice *will* be very short!).
I write code in that environment very differently than I
do in "fleshier" ones -- e.g., I may literally spin on
a condition variable instead of having the OS add support
for an event notification.

The trouble comes when you have to deal with more and varied
"tasks". Or, with asynchronous activations. Things that
cant easily be sorted out "on paper" ahead of time (though
with reservations, some of this can be alleviated).

> In practice, there are few realtime tasks and many tasks that can wait;
> the OS should not add the unnecessary overhead to every task. In the
> other words, if you need this particular task to be realtime, you should
> take care of it, not OS.

<frown> The OS is there to make the developer's job *easier*
by managing resources for him. If your OS is getting in the
way, then get a better OS! :>

You can always devolve to the "run everything time critical
in an ISR and leave the rest in the background..." :-(
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: A 16-bit/32-bit microprocessor specifically for UAV purpose
Next: What is Bit Spread?