Re: Fair scheduling of the equal priority tasks in RTOS

Hi Vladimir,

Vladimir Vassilevsky wrote:

D Yuniskis wrote:
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.

This is where I started.
In the addition to described, in my first MTOS the tasks could call scheduler if they have nothing to do; so they don't have to consume the entire time slice. So, the scheduler loop was spinning through all tasks with the variable rate (from =10ms to ~10us per full revolution). If none of the tasks had anything to do, I put the system to sleep till an interrupt.

Yes. You can even craft executives that save *no* "task"
state (other than PC) -- but that puts other constraints
on the way you write your application.

This approach is very simple. It is also free from priority resource deadlock problems, as every task gets time slice anyway.

Well, you can still have deadlock. You just don't have
"priority inversion" as everything is "flat".

The trouble comes when you have to deal with more and varied
"tasks". Or, with asynchronous activations.

I am already three major versions past that first round robin thingy :-) Round robin is supported as well as event driven priority scheduling.

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

If you make a fool to pray God, he will break his forehead.

Hmmm... I guess i don't understand the reference :<

You can always devolve to the "run everything time critical
in an ISR and leave the rest in the background..." :-(

I thought for a while about complete unification of interrupts and tasks. I.e. having them under the same abstraction. Unfortunately, that implies a lot of OS overhead.

I treat the "application layer" AS IF it was just N layers
of ISRs competing and coexisting. E.g., I try to design
APIs so there aren't arbitrary "can't be called from an ISR"
restrictions. Sometimes this affects the types of
objects that can be supported (as you need to keep the
interfaces "light").

The problem I always see with traditional "priority based"
scheduling is there are no hard and fast rules for
assigning priorities. Instead, folks tend to discover
belatedly that the structure of their system is "wrong"
and try to *make* it work by tweeking priorities. And,
this turns into a "tipping canoe" exercise -- you move one
way and the canoe starts to tip... so you move the other
way and it tips a different way, etc. I.e., there is
no "engineering" involved in picking the priority levels.

It's always amusing to see folks evaluate the *number* of
priority levels supported in an OS AS IF "more is better".
(Then 50,000 levels has *got* to be better than *20*!)

IME, an MTOS gives its biggest bang for buck by helping
you decompose an application into independant "tasks"
(using the meaning: "jobs") so you can focus on one
at a time without having to juggle all of them at once.
Beyond that, its a question of how much you want to
migrate application requirements into the OS's domain
instead of the application;s.
.

Relevant Pages

  • Re: Plz help me finding the logic for implementing the BCC2 and ECC2 in OSEK RTOS
    ... plus the support of more than one task with the same priority and multiple ... ECC2 is like ECC1 plus more than one task with the same ... priority and multiple activation of basic tasks. ... For your scheduling policy this means, ...
    (comp.arch.embedded)
  • Re: general newbie questions about MSP concepts
    ... First lesson: Project and the computer it runs on has an IQ of zero!!:) ... Second lesson is that planning precedes scheduling. ... Now add resources and you get the hours per week needed from each resource ... > if i increase the priority of a task, ...
    (microsoft.public.project)
  • Re: Sharing the timeslice
    ... PTHREAD_SCOPE_SYSTEM threads for the CPU. ... scheduling policy and the thread's priority. ... Priorities and Scheduling Policy ...
    (comp.arch.embedded)
  • Re: Wiseman and McGhie are Ranting Again
    ... of which is the clock tick that expires a time slice interval. ... > Then we can start playing around with Thread Priority. ... I think you are comparing pre-emptive and co-operative scheduling. ... then falls quiet and calls its Idle Loop. ...
    (microsoft.public.mac.office.word)
  • Re: Rate Monotonic Scheduling (RMS) vs. OS Scheduling
    ... one because almost everyone uses static priority for real time. ... RMS scheduling requires that the cpu only be loaded to some ... The problem with EDT is that it requires dynamic scheduling as ... The problem of EDF is also that you need to know who is the earliest ...
    (comp.arch)