Prev: A 16-bit/32-bit microprocessor specifically for UAV purpose
Next: What is Bit Spread?
From: Vladimir Vassilevsky on 16 Apr 2010 00:31

Suppose we have several active tasks with equal priorities. So, one task
runs for one timer tick, then the next task runs for another timer tick,
so on. Scheduler goes in a round robin manner.

At some moment, a higher priority task is activated. We execute this
task, and then we have to return back to the round robin scheduling of
the lower priority tasks.

Here is a problem: which of the lower priority tasks should be scheduled
after the interruption of the round robin loop?

The best solution would be start at the same place where the round robin
was preempted by higher priority task. But what if one round robin was
preempted by another round robin at higher priority? Remember all
positions for all possible cases? Doesn't look feasible.

The easiest would be restart round robin from task[0]. But, if round
robin gets preempted before making a full turn, the tasks at the end of
the list will never get executed.

We can restart round robin from random task in the loop. This is simple
enough; however I am wondering if there is more elegant or efficient
solution.


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

Vladimir Vassilevsky wrote:

> Suppose we have several active tasks with equal priorities. So, one task
> runs for one timer tick, then the next task runs for another timer tick,
> so on. Scheduler goes in a round robin manner.
>
> At some moment, a higher priority task is activated. We execute this
> task, and then we have to return back to the round robin scheduling of
> the lower priority tasks.
>
> Here is a problem: which of the lower priority tasks should be scheduled
> after the interruption of the round robin loop?
>
> The best solution would be start at the same place where the round robin
> was preempted by higher priority task. But what if one round robin was
> preempted by another round robin at higher priority? Remember all
> positions for all possible cases? Doesn't look feasible.

Typically, you keep a list of "tasks" (lets not argue terms)
at each priority level. The scheduler picks the first "ready"
task on the highest "non empty" queue of tasks.

I.e., if tasks A, B, C and D are at priority 5 (assume higher
numbers == higher priority) and no tasks are "ready" at any
higher priority, then the READY[5] queue looks like:
{A, B, C, D} (for example).

After A exhausts its timeslice (or yields it for whatever
purpose), the READY[5] queue looks like {B, C, D, A}. And,
assuming no higher priority tasks become ready, B will become
the active task.

When B is preempted (by something that causes the scheduler
to run, again), the scheduler examines the READY[] queues
again. If it finds something in a higher priority queue
(e.g., READY[9] = {X, Y, Z} -- perhaps these three tasks
became ready at the same instant... maybe all waiting on
an event that B signaled!), then it selects the first of
the tasks from *that* queue to become the active task.

The tasks in READY[9] will share the processor until:
- a task in a higher priority queue becomes active, or
- all READY[9] tasks sleep/die (for whatever reasons)
During this time, *none* of the READY[5] tasks will run.

How you deal with the fraction of a timeslice that B "lost"
when it was initially preempted is up to you.

Instead of having *a* "time remaining in this slice" that
is system wide, I have this value maintained in the
READY[] queue (you don't need it in each task as, by
definition, if another task in my queue is running, then
*I* have exhausted my time slice!) for each priority
level.

So, when B eventually regains control of the processor
(becomes the "active task"), whatever time remaining
in its slice is given to it.

I.e., you treat the actions of any higher priority tasks
AS IF they were interrupts -- the time they "consume"
is invisible to the executing tasks at the priority that
was preempted. (this model also makes it easy to think about
how the OS *should* work)

> The easiest would be restart round robin from task[0]. But, if round
> robin gets preempted before making a full turn, the tasks at the end of
> the list will never get executed.
>
> We can restart round robin from random task in the loop. This is simple
> enough; however I am wondering if there is more elegant or efficient
> solution.

HTH,
--don
From: George Neuner on 16 Apr 2010 04:55
On Thu, 15 Apr 2010 23:31:20 -0500, Vladimir Vassilevsky
<nospam(a)nowhere.com> wrote:

>
>Suppose we have several active tasks with equal priorities. So, one task
>runs for one timer tick, then the next task runs for another timer tick,
>so on. Scheduler goes in a round robin manner.
>
>At some moment, a higher priority task is activated. We execute this
>task, and then we have to return back to the round robin scheduling of
>the lower priority tasks.
>
>Here is a problem: which of the lower priority tasks should be scheduled
>after the interruption of the round robin loop?

Traditionally, the interrupted task is resumed from the point at which
it was interrupted. This works fine if there is one task per priority
level.

However, the moment you have multiple time sensitive tasks of equal
priority you really need to time slice and, if any of those tasks are
time sensitive, you may have to perform deadline scheduling - which
can get *very* complicated.


>The best solution would be start at the same place where the round robin
>was preempted by higher priority task. But what if one round robin was
>preempted by another round robin at higher priority? Remember all
>positions for all possible cases? Doesn't look feasible.
>
>The easiest would be restart round robin from task[0]. But, if round
>robin gets preempted before making a full turn, the tasks at the end of
>the list will never get executed.

Priority, fairness and run-to-completion are incompatible. You can
have any two, but not all three. With prioritization, time slicing is
required (but not sufficient) to implement (any kind of) fairness.
[If you don't believe that, I can refer you to OS textbooks and
research papers. OS internals are one of my "hobbies". 8-]


I'm not sure what you mean by "feasible".

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
a shitload of scheduling data, but no RTOS I am aware of actually does
deadline scheduling.

If you have a simple run-to-completion model, then you only need one
register context per priority level. If you are time slicing, you
need one per task. The other information is needed per task.


>We can restart round robin from random task in the loop. This is
>simple enough;

Then you've implemented time slicing ... only with arbitrarily long
slices: to task completion or to next priority change.


>however I am wondering if there is more elegant or efficient solution.

Nope ... only more complex solutions for more complex problems.


>Vladimir Vassilevsky
>DSP and Mixed Signal Design Consultant
>http://www.abvolt.com

George
From: Vladimir Vassilevsky on 16 Apr 2010 10:34


D Yuniskis wrote:

> Hi Vladimir,
>
> Vladimir Vassilevsky wrote:
>
>> Suppose we have several active tasks with equal priorities. So, one
>> task runs for one timer tick, then the next task runs for another
>> timer tick, so on. Scheduler goes in a round robin manner.
>>
>> At some moment, a higher priority task is activated. We execute this
>> task, and then we have to return back to the round robin scheduling of
>> the lower priority tasks.
>>
>> Here is a problem: which of the lower priority tasks should be
>> scheduled after the interruption of the round robin loop?
>>
>> The best solution would be start at the same place where the round
>> robin was preempted by higher priority task. But what if one round
>> robin was preempted by another round robin at higher priority?
>> Remember all positions for all possible cases? Doesn't look feasible.
>
>
> Typically, you keep a list of "tasks" (lets not argue terms)
> at each priority level.

Thanks, I see now. And for each list you remember who is the next to go.
This certainly works; however it requires maintaining lists and updating
them in the situations like temporary elevation of priority. Lots of
overhead. I hoped to find a light weight solution.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com





From: D Yuniskis on 16 Apr 2010 12:59
Hi Vladimir,

Vladimir Vassilevsky wrote:
>
> D Yuniskis wrote:
>> Vladimir Vassilevsky wrote:
>>
>>> Suppose we have several active tasks with equal priorities. So, one
>>> task runs for one timer tick, then the next task runs for another
>>> timer tick, so on. Scheduler goes in a round robin manner.
>>>
>>> At some moment, a higher priority task is activated. We execute this
>>> task, and then we have to return back to the round robin scheduling
>>> of the lower priority tasks.
>>>
>>> Here is a problem: which of the lower priority tasks should be
>>> scheduled after the interruption of the round robin loop?
>>>
>>> The best solution would be start at the same place where the round
>>> robin was preempted by higher priority task. But what if one round
>>> robin was preempted by another round robin at higher priority?
>>> Remember all positions for all possible cases? Doesn't look feasible.
>>
>> Typically, you keep a list of "tasks" (lets not argue terms)
>> at each priority level.
>
> Thanks, I see now. And for each list you remember who is the next to go.

Yes. You need *some* way on sorting out the "ready" tasks
from those that are "not ready" (disabled, blocking, etc.).
One way is to thread them onto a "ready list".

If you have just one list, though, they you have to keep
it sorted by priority *and* inserting another task into
this list is no longer a constant time operation (unless you
keep pointers to where each "group of tasks at a given
priority" begin -- i.e., a list of lists).

Which begs the question: are you really looking for an RTOS
or just an MTOS? E.g., an RTOS makes extra guarantees that
an MTOS need not. Many so-called RTOS's are really "fast-ish
MTOS's".

Often, MTOS's fail to be pedantic about invoking the
scheduler every time it *should* and, instead, leave
preemption to "selective conditions" -- sometimes, little
more than the jiffy! Still others blindly call
"reschedule()" each time there *might* be a need.
Coming up with efficient ways of knowing when you can
skip the reschedule() without impacting the system
requires a bit more "art".

> This certainly works; however it requires maintaining lists and updating
> them in the situations like temporary elevation of priority.

Yes. You also have to deal with cases where the "readymost" task
at a given priority (i.e., head of it's READY[] queue) is moved to
another priority level -- what do you do with the balance of its
(previously preempted) time slice?

And, there are different criteria that can be used besides
round robin/fixed priority to determine scheduling. In my
multimedia RTOS, this is a pluggable module and allows
me to change scheduling criteria at run-time based on the
nature of the tasks active at any given time (RR, RM, EDF,
etc.). The problem (for the system designer) is that you
often have a mixture of tasks with different and competing
scheduling algorithms. :<

> Lots of overhead. I hoped to find a light weight solution.

Look at the nature of your tasks. Think about what *could* happen
if any one of them became "starved" (completely or partially).
Would some *other* aspect of the system throttle its competitors
such that it would eventually regain processor share? (e.g.,
in a producer-consumer relationship, either party eventually ends
up *needing* the other and, in the absence of that "other",
effectively stops competing).
 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: A 16-bit/32-bit microprocessor specifically for UAV purpose
Next: What is Bit Spread?