Prev: A 16-bit/32-bit microprocessor specifically for UAV purpose
Next: What is Bit Spread?
From: D Yuniskis on 16 Apr 2010 13:06
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).

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

> If you have a simple run-to-completion model, then you only need one
> register context per priority level.

Without preemption, you only need one register context per processor!

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

Isn't that what makes it fun?? (pity the folks who can't
wake up to find something gnawing at their "creative center"
each day :> )
From: Vladimir Vassilevsky on 16 Apr 2010 13:17


D Yuniskis wrote:

> 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?
>>>>
>>> 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.
>
> Which begs the question: are you really looking for an RTOS
> or just an MTOS?

I have the best of both worlds: RTOS with MTOS capability. In addition
to the scheduling by priority, it allows for the round robin
time-slicing of the tasks with equal priority.

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

Here is a cheap solution: restart round-robin time slicing from a random
position in the corresponding list. Although it is not exactly fair, it
works very nicely and avoids several problems.



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

Vladimir Vassilevsky wrote:
> D Yuniskis wrote:
>> 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?
>>>>>
>>>> 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.
>>
>> Which begs the question: are you really looking for an RTOS
>> or just an MTOS?
>
> I have the best of both worlds: RTOS with MTOS capability. In addition
> to the scheduling by priority, it allows for the round robin
> time-slicing of the tasks with equal priority.

Well, RTOS *tends* to be a superset of MTOS -- it's an
MTOS that gives temporal guarantees on its services
(an MTOS just tries to share a processor using "some set
of criteria")

>>> 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?
>
> Here is a cheap solution: restart round-robin time slicing from a random
> position in the corresponding list. Although it is not exactly fair, it
> works very nicely and avoids several problems.

But then you can't make any RT *guarantees* -- since you
(your tasks) can't know "definitively" what resources
they will have made available to them (?) There is something
inherently non-deterministic built into the scheduler!

[in hindsight, should have crossposted all this to
comp.realtime -- even though its a wasteland]
From: Tim Wescott on 16 Apr 2010 13:36
D Yuniskis wrote:
> 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".

I'm going to get all pedantic, and probably start a flame war thereby.

A tasking kernel that doesn't use constant-time operations (like
inserting tasks into the ready list) can still be real-time. "Real
time" -- as I've seen it defined -- doesn't mean "consistent", "Real
time" means "has bounded maximum times for operations".

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.

Granted, the unpredictability makes verification by testing exceedingly
difficult, because how do you know if you're loading the thing all the way?

Your comment about "doesn't always call the scheduler" also doesn't (if
you're pedantic) necessarily violate "real time-ness", although it
certainly does -- in spades! -- make it fiendishly difficult to test
quality in.

IMHO there are few "real time" systems that are are actually correctly
tested or analyzed to verify that they are really meeting real time
criteria. For that matter, IMHO, there are a lot fewer systems that are
really, truly "hard" real time than we like to think -- because if there
were, there would be a lot fewer systems that actually worked!

--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com
From: Vladimir Vassilevsky on 16 Apr 2010 13:35


D Yuniskis wrote:

> Hi Vladimir,
>
> Vladimir Vassilevsky wrote:
>

>> I have the best of both worlds: RTOS with MTOS capability. In addition
>> to the scheduling by priority, it allows for the round robin
>> time-slicing of the tasks with equal priority.
>
>
> Well, RTOS *tends* to be a superset of MTOS -- it's an
> MTOS that gives temporal guarantees on its services
> (an MTOS just tries to share a processor using "some set
> of criteria")
>
>>>> 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?
>>
>>
>> Here is a cheap solution: restart round-robin time slicing from a
>> random position in the corresponding list. Although it is not exactly
>> fair, it works very nicely and avoids several problems.
>
>
> But then you can't make any RT *guarantees* -- since you
> (your tasks) can't know "definitively" what resources
> they will have made available to them (?) There is something
> inherently non-deterministic built into the scheduler!

The deadlines are guaranteed for RT tasks, corresponding to their
priority. Besides, I have a bunch of soft-RT and non-RT tasks which run
by time slicing. It is very convenient to have all that under the same
framework and same API.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
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?