Common name for a "Task Loop"

On 7/6/2016 1:31 AM, upsidedown@downunder.com wrote:
>> *You* are relying on yourself to keep track of all the "current priorities"
>> in your system -- in your meatware.  This means you will never be able to
>> design a "complex" system (complex is anything that won't fit in a single
>> braincase)
>
> Done it for nearly 40 years.
>
> I try to limit the number of task to ten or less, so I can count them
> with my fingers. I might be able to increase it to 20 by using also my
> toes, but then I would have to take my socks off and my colleagues
> might not appreciate that :-)

As I said, not a "complex" system.

I spent the last two days just trying to answer the question:
    "What is the minimal complement of tools required to get a NetBSD
    system to boot diskless to multiuser?"
Note this doesn't ask anything about the inner workings of the kernel,
network stacks, device drivers, etc.  But, it *does* require knowledge of
the services that the basic system must provide and the interdependencies
between them -- on a *coarse* level.

I'd wager that none of the folks actively working with kernel development
on a day to day basis could rattle off *half* of the bootstrap activities.
("Why bother?  Check the sources!")

These are the sorts of complex systems that defy "a single braincase".
Having learned what I needed, I'll resort to consulting my written
notes -- too much complexity to keep track of (while everything "makes
sense" after its discovered, recalling any of it "cold" would be a
challenge!)

Increasingly, I see the days of little "islands of automation" disappearing
and, in their place, seeing interconnected systems co-operating to solve
a single application (or, suite of applications).  You'll have a *rough*
idea of what happens where -- but anything beyond that will too quickly
exceed the complexity threshold for individual developers.

The sorts of techniques used to manage small "islands" don't scale
well when faced with a multitude of similar islands, each with
competing needs in "The System".

task1() {
     do_something();
     do_something_else();
     do_still_more();
}

Pick a priority for task1.

Each of the constituent parts of it execute (sequentially) at that same
priority.

But, what if do_something() contains an IPC to task23?  During that
IPC, task1's work is being performed at task23's priority.  Which may
be higher or lower than task1's.  Similarly, task5 may also issue an IPC
to that same resource managed by task23.  I.e., task1 and task5 now
have regions of operation where their respective current priorities
are overridden by those of task23.  While accessing that service,
task1 and task5 are effectively executing at the same priority and
possibly in a FIFO manner -- regardless of the priorities of task1
and task5 just prior to those IPC's.

What if do_something_else() executes an RPC?  So, not only are
tasks (1 & 5) having their priorities mucked with, but, also,
tasks on other nodes.  Do you assign every task in the system
a priority and try to manage their interactions "in your head"?

Note that this already happens in single CPU systems but you
gloss over it.  A character received by an ISR is processed
at a different "priority" than the task that ultimately consumes
that character (or, emits one to feed a Tx ISR).  A task wanting to
push a packet onto the network relies on the protocol stack to
decide *when* it's packet sees the wire -- regardless of the
"priority" of the task making the request.

Shouldn't the network stack schedule the packets with the same
RELATIVE priorities of the tasks issuing them?  Why should a
packet issued by a high priority task have to wait for queued
outgoing traffic originated by a LOW priority task?

Shouldn't an IPC adjust the priority of the receiving thread
to match that of the sending thread WHILE PROCESSING IT'S
REQUEST?

Shouldn't an RPC cause the network stack on the local node to schedule
the outbound IPC message with the "caller's" priority -- and, shouldn't
the network stack on the remote node receiving the packet know to
treat it at the priority of the sending task on the originating node?
Doesn't this require some global assignment of priorities (so a particular
priority on node A is "as important" when encountered on node B)?

Priorities are a sloppy way of extending the foreground into the
background.  Ever work on a system with 20 interrupt priorities?
Ever wonder how easy it would be to pick *a* set of priority
assignments that would actually *work*, there?  Now, imagine
200 or 2,000!

As I said before, priorities tell you nothing about the timeliness
constraints of tasks.  You can just as well give them names of
fruits and vegetables and rank them using whatever criteria *seems*
to work, today...

On Wed, 06 Jul 2016 10:39:30 +0800, Reinhardt Behm wrote:

> Tim Wescott wrote:
> 
>> There was a slogan going around the Embedded community about a decade
>> or two ago "Real time doesn't mean real fast".  It's a concise way of
>> expressing your comment on latency and RTOS's.
> 
> The German term for "real time" is "Echtzeit". Some vary this to
> "Rechtzeit"
> which is best translated as "in time" and describes it much better.

I barely know enough German to successfully ask for directions to the loo, 
but it seems like "Rechtzeit" would also translate to "right time" or 
"correct time", which works even better for me.

-- 
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work!  See my website if you're interested
http://www.wescottdesign.com

On 16-07-06 13:06 , Don Y wrote:

> As I said before, priorities tell you nothing about the timeliness
> constraints of tasks.  You can just as well give them names of
> fruits and vegetables and rank them using whatever criteria *seems*
> to work, today...

I think you are looking at priorities from the wrong perspective -- a 
too high-level perspective.

Task priorities are a design and coding mechanism, of the same nature as 
procedures, statements, while-loops, if-then-else statements, and so on. 
Just as if-then-else statements let the designer tell the processor 
which of two statements should be executed, depending on some 
application-specific condition, so priorities let the designer tell the 
RTOS scheduler which of two tasks/threads should be executed in 
preference to the other, depending on some implementation-specific 
analysis or priority assignment rules.

It is the designer's job to map the higher-level timeliness requirements 
into an implementation in terms of task priorities, just as the designer 
maps higher-level functional requirements into sequential, conditional, 
or looping code. The result may be a set of fixed-priority tasks, or a 
design in which task priorites vary dynamically, for example to avoid 
priority inversions, or the designer may choose to use a different 
mechanism to control the scheduling, for example Earliest Deadline First.

For some applications, imperative constructs such as if-then-else and 
loops may not be a suitable algorithmic mechanism, and some other 
algorithm formalism such as functional or logical (rule-based) 
programming is more appropriate. Similarly, some time-sensitive 
applications may be difficult to implement with scheduling based on 
numerical priorities, and some other method for scheduling activities is 
more appropriate (but I must admit that I know of no other scheduling 
methods that seem useful for real-time systems, beyond priority and EDF).

Priority-based scheduling at least has systematic and mathematically 
verified design methods: rate-monotonic priority assignment, 
deadline-monotonic priority assignment, and their corresponding 
response-time analysis methods. And several variations and extensions of 
these.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

On Wed, 6 Jul 2016 21:37:12 +0300, Niklas Holsti
<niklas.holsti@tidorum.invalid> wrote:

>On 16-07-06 13:06 , Don Y wrote:
>
>> As I said before, priorities tell you nothing about the timeliness
>> constraints of tasks.  You can just as well give them names of
>> fruits and vegetables and rank them using whatever criteria *seems*
>> to work, today...
>
>I think you are looking at priorities from the wrong perspective -- a 
>too high-level perspective.
>
>Task priorities are a design and coding mechanism, of the same nature as 
>procedures, statements, while-loops, if-then-else statements, and so on. 
>Just as if-then-else statements let the designer tell the processor 
>which of two statements should be executed, depending on some 
>application-specific condition, so priorities let the designer tell the 
>RTOS scheduler which of two tasks/threads should be executed in 
>preference to the other, depending on some implementation-specific 
>analysis or priority assignment rules.

I think Don's point is that task priorities are merely a proxy for the
actual scheduling criteria - whatever that may be.  

Scheduling can be done without invoking any notion of numerical
"priority": e.g., a "fair" scheduler can work purely in terms of time
slices and number of tasks, a deadline scheduler can work with
timestamps and cycle estimates, etc.

The fact that *most* pre-emptive systems are priority based is an
artifact of history.  Leaving aside the difficulty of determining
priorities that actually make the system work, the _notion_ of
"priority" is easy to understand, and comparative priorities can be
trivially represented using simple numbers ... so priority was a
convenient [if not particularly "natural"] way to approach many
scheduling problems.

But I would claim - and I think Don would agree - that due to that
history, the notion of "priority" has become condicio sine qua non,
and, in the minds of many developers, priority has become conflated
with the actual scheduling criteria.


>It is the designer's job to map the higher-level timeliness requirements 
>into an implementation in terms of task priorities, 

Case in point.  "Priority" as the basis of scheduling is so ingrained
that many people have difficulty envisioning a pre-emptive system that
is not [directly] based on them.

But because "priority" really is just proxy for the actual scheduling
criteria - the assignment of priorities to make a system work properly
is not a straightforward process.


>just as the designer 
>maps higher-level functional requirements into sequential, conditional, 
>or looping code. The result may be a set of fixed-priority tasks, or a 
>design in which task priorites vary dynamically, for example to avoid 
>priority inversions, or the designer may choose to use a different 
>mechanism to control the scheduling, for example Earliest Deadline First.
>
>For some applications, imperative constructs such as if-then-else and 
>loops may not be a suitable algorithmic mechanism, and some other 
>algorithm formalism such as functional or logical (rule-based) 
>programming is more appropriate. Similarly, some time-sensitive 
>applications may be difficult to implement with scheduling based on 
>numerical priorities, and some other method for scheduling activities is 
>more appropriate (but I must admit that I know of no other scheduling 
>methods that seem useful for real-time systems, beyond priority and EDF).
>
>Priority-based scheduling at least has systematic and mathematically 
>verified design methods: rate-monotonic priority assignment, 
>deadline-monotonic priority assignment, and their corresponding 
>response-time analysis methods. And several variations and extensions of 
>these.


YMMV, 
George

On 7/6/2016 9:50 PM, George Neuner wrote:
> On Wed, 6 Jul 2016 21:37:12 +0300, Niklas Holsti
> <niklas.holsti@tidorum.invalid> wrote:
>
>> On 16-07-06 13:06 , Don Y wrote:
>>
>>> As I said before, priorities tell you nothing about the timeliness
>>> constraints of tasks.  You can just as well give them names of
>>> fruits and vegetables and rank them using whatever criteria *seems*
>>> to work, today...
>>
>> I think you are looking at priorities from the wrong perspective -- a
>> too high-level perspective.
>>
>> Task priorities are a design and coding mechanism, of the same nature as
>> procedures, statements, while-loops, if-then-else statements, and so on.
>> Just as if-then-else statements let the designer tell the processor
>> which of two statements should be executed, depending on some
>> application-specific condition, so priorities let the designer tell the
>> RTOS scheduler which of two tasks/threads should be executed in
>> preference to the other, depending on some implementation-specific
>> analysis or priority assignment rules.
>
> I think Don's point is that task priorities are merely a proxy for the
> actual scheduling criteria - whatever that may be.

Exactly.  "Priority" (in the sense of "set_task_priority()") is just
an expedient to make coding a scheduler easy.  It tells you *nothing*
about the task's "importance", "timeliness constraints", etc.
It's just a nice, small integer that can be used to "rank" a set
of competing consumers of a device's resources (i.e., tasks).

In my (above) description, I tried to substitute "timeliness" as
a synonym for "priority" -- while trying to avoid the connotations
of "priority" inherent in "set_task_priority()".

Of course, that suggests real-time constraints which just muddies the
water in a different way.

> Scheduling can be done without invoking any notion of numerical
> "priority": e.g., a "fair" scheduler can work purely in terms of time
> slices and number of tasks, a deadline scheduler can work with
> timestamps and cycle estimates, etc.

The advantage to deadlines (if we can avoid the RT taint) is that they
are "portable" -- a description of a deadline in a particular
application can be related DIRECTLY to a deadline in some completely
unrelated application:  they share an axis and unit of measure!

"Priority" (in the "set_task_priority()" sense) is just a completely
bogus number that ONLY means something in the context of the PARTICULAR
set of tasks that it is currently bound.  Add another task and it's
meaning changes (is "37" really important?  perhaps compared to "1" - "12"
but surely not when the new task is at "98656"!).

Is "2" twice as "important" as "1"?  Half as "important" as "4"?

> The fact that *most* pre-emptive systems are priority based is an
> artifact of history.  Leaving aside the difficulty of determining
> priorities that actually make the system work, the _notion_ of
> "priority" is easy to understand, and comparative priorities can be
> trivially represented using simple numbers ... so priority was a
> convenient [if not particularly "natural"] way to approach many
> scheduling problems.
>
> But I would claim - and I think Don would agree - that due to that
> history, the notion of "priority" has become condicio sine qua non,
> and, in the minds of many developers, priority has become conflated
> with the actual scheduling criteria.

And, has been erroneously treated as indicative of "priority"
beyond "set_task_priority()".  There needs to be another term that
isn't inherently tied to an implementation technique that can
be used to represent "rank" in terms of scheduling preference.

The folly of "priority" (set_task_priority) in scheduling is
illustrated in my immediately preceding example:  why don't
other actors performing services on behalf of a task "having"
(executing at) priority 'P' *assume* that (scheduling) priority
while acting on its behalf?  Magically, the priority of the
activities being performed to achieve your (task's) goal have
changed -- just because some other agency is performing them!?
And, when that agency has finished with its portion of the "job",
the originating task will continue at its *original* priority...?

WTF?  It's "importance" (again, a feeble synonym for priority)
varies based on who's doing the work?  Or, the nature of the work
being performed in/on it??

>> It is the designer's job to map the higher-level timeliness requirements
>> into an implementation in terms of task priorities,
>
> Case in point.  "Priority" as the basis of scheduling is so ingrained
> that many people have difficulty envisioning a pre-emptive system that
> is not [directly] based on them.
>
> But because "priority" really is just proxy for the actual scheduling
> criteria - the assignment of priorities to make a system work properly
> is not a straightforward process.

"Priority" (in scheduling) is just a sort of efficiency hack.  Let's
reduce the problem of scheduling to something simple:  small integers
that RANK the relative "importance" of the needs of individual tasks.

It's a direct carry-forward of interrupt priorities:  those being
scheduling decisions MADE IN HARDWARE at the level of the interrupt
controller (which acknowledges the fact that two or more different
activities are likely to occur simultaneously and something has
to make a CHOICE among them as to which ONE to grant access to the
CPU for this ISR).

And, if you look at most hardware systems, the activities mapped
onto individual IRQ "levels"/priorities are defined solely by
the hardware (chip) manufacturer.  The user/implementor has very
little option how to rearrange the relative priorities/levels
AS IMPLEMENTED IN THE HARDWARE; you can't arbitrarily decide
that the priority levels should be:
     UART_RxReady
     UART_TxReady
     ParityError
     PowerFail
     ReceiverOverrun
     NetworkPacketAvailable
     BREAK detected
vs:
     NetworkPacketAvailable
     BREAK detected
     UART_TxReady
     ParityError
     PowerFail
     UART_RxReady
     ReceiverOverrun

And, once you've migrated from the foreground into the background,
there's no guarantee that the "handlers" for these events will
correspond to the same relative priorities in the foreground!
E.g., the "PowerFail()" task may lead the list despite being
relatively LOW on that list in the foreground!

If you've ever had to "jigger" a priority, you should be asking,
"why did I *have* to do this?  what did I do *wrong* in making
the initial assignment? how will this CHANGE muck with the other
assumptions inherent in the assignment of the other priorities?"

>> just as the designer
>> maps higher-level functional requirements into sequential, conditional,
>> or looping code. The result may be a set of fixed-priority tasks, or a
>> design in which task priorites vary dynamically, for example to avoid
>> priority inversions, or the designer may choose to use a different
>> mechanism to control the scheduling, for example Earliest Deadline First.
>>
>> For some applications, imperative constructs such as if-then-else and
>> loops may not be a suitable algorithmic mechanism, and some other
>> algorithm formalism such as functional or logical (rule-based)
>> programming is more appropriate. Similarly, some time-sensitive
>> applications may be difficult to implement with scheduling based on
>> numerical priorities, and some other method for scheduling activities is
>> more appropriate (but I must admit that I know of no other scheduling
>> methods that seem useful for real-time systems, beyond priority and EDF).
>>
>> Priority-based scheduling at least has systematic and mathematically
>> verified design methods: rate-monotonic priority assignment,
>> deadline-monotonic priority assignment, and their corresponding
>> response-time analysis methods. And several variations and extensions of
>> these.

On 16-07-07 09:16 , Don Y wrote:
> On 7/6/2016 9:50 PM, George Neuner wrote:
>> On Wed, 6 Jul 2016 21:37:12 +0300, Niklas Holsti
>> <niklas.holsti@tidorum.invalid> wrote:
>>
>>> On 16-07-06 13:06 , Don Y wrote:
>>>
>>>> As I said before, priorities tell you nothing about the timeliness
>>>> constraints of tasks.  You can just as well give them names of
>>>> fruits and vegetables and rank them using whatever criteria *seems*
>>>> to work, today...
>>>
>>> I think you are looking at priorities from the wrong perspective -- a
>>> too high-level perspective.
>>>
>>> Task priorities are a design and coding mechanism, of the same nature as
>>> procedures, statements, while-loops, if-then-else statements, and so on.
>>> Just as if-then-else statements let the designer tell the processor
>>> which of two statements should be executed, depending on some
>>> application-specific condition, so priorities let the designer tell the
>>> RTOS scheduler which of two tasks/threads should be executed in
>>> preference to the other, depending on some implementation-specific
>>> analysis or priority assignment rules.
>>
>> I think Don's point is that task priorities are merely a proxy for the
>> actual scheduling criteria - whatever that may be.
>
> Exactly.  "Priority" (in the sense of "set_task_priority()") is just
> an expedient to make coding a scheduler easy.  It tells you *nothing*
> about the task's "importance", "timeliness constraints", etc.

That is not so, if you follow a systematic and proven 
priority-assignment rule. For example, if you use deadline-monotonic 
priorities then the order of task priorities is equivalent to the order 
of task deadlines (expressed as the maximum duration between task 
activation and completion). So then the task priorities certainly tell 
you a lot about the (relative) timeliness constraints.

If you just assign priorities based on some subjective "task importance" 
feeling, your statement is valid.

> The advantage to deadlines (if we can avoid the RT taint) is that they
> are "portable" -- a description of a deadline in a particular
> application can be related DIRECTLY to a deadline in some completely
> unrelated application:  they share an axis and unit of measure!

Yes, and priorities can represent deadlines, see above, in which case 
priorities are portable, too.

> "Priority" (in the "set_task_priority()" sense) is just a completely
> bogus number that ONLY means something in the context of the PARTICULAR
> set of tasks that it is currently bound.

Priorities are instructions to the scheduler. I agree that they have 
meaning only for a particular task set, because they represent only the 
*relative* scheduling preferences between the tasks in this set.

> Is "2" twice as "important" as "1"?  Half as "important" as "4"?

Those are meaningless questions. Priorities are an ordinal scale, not an 
interval or ratio scale 
(https://en.wikipedia.org/wiki/Statistical_data_type).

> The folly of "priority" (set_task_priority) in scheduling is
> illustrated in my immediately preceding example:  why don't
> other actors performing services on behalf of a task "having"
> (executing at) priority 'P' *assume* that (scheduling) priority
> while acting on its behalf?  Magically, the priority of the
> activities being performed to achieve your (task's) goal have
> changed -- just because some other agency is performing them!?

One can certainly design and implement such a priority-inheritance 
mechanism in a system, even a distributed system (though in the latter 
case one would have to define a system-wide priority scale). I know of 
two examples for non-distributed systems: priority inheritance for 
resources (https://en.wikipedia.org/wiki/Priority_inheritance) and 
priority inheritance occurring when one Ada task requests a service from 
another Ada task 
(http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-D-1.html).

Don't blame the priority concept for poor or deficient implementations 
of priorities.

> "Priority" (in scheduling) is just a sort of efficiency hack.

No, it is the basis for one important set of the mathematical methods 
for verifying real-time performance: schedulability analysis.

> It's a direct carry-forward of interrupt priorities:  those being
> scheduling decisions MADE IN HARDWARE at the level of the interrupt
> controller (which acknowledges the fact that two or more different
> activities are likely to occur simultaneously and something has
> to make a CHOICE among them as to which ONE to grant access to the
> CPU for this ISR).

Yes, so? This is "scheduling", and it applies as well to HW as to SW. In 
fact, there have been HW implementations of SW task schedulers -- RTOS 
"accelerators".

> And, if you look at most hardware systems, the activities mapped
> onto individual IRQ "levels"/priorities are defined solely by
> the hardware (chip) manufacturer.  The user/implementor has very
> little option how to rearrange the relative priorities/levels
> AS IMPLEMENTED IN THE HARDWARE; you can't arbitrarily decide
> that the priority levels should be:
>     UART_RxReady
>     UART_TxReady
>     ParityError
>     PowerFail
>     ReceiverOverrun
>     NetworkPacketAvailable
>     BREAK detected
> vs:
>     NetworkPacketAvailable
>     BREAK detected
>     UART_TxReady
>     ParityError
>     PowerFail
>     UART_RxReady
>     ReceiverOverrun

The SPARC processors I am familiar with do allow the application to 
configure the priorities of interrupts, to some extent.

Before microcontrollers and systems-on-chip, in the minicomputer era, 
many systems allowed application-specific interrupt priorities, because 
the priority of a peripheral interface was defined by the number of the 
slot into which the interface board was plugged.

The interrupt systems of CPU cores usually number the external interrupt 
lines and use the number as the priority. When the CPU core is embedded 
in an SoC or a microcontroller, the system designer assigns interrupt 
lines to on-chip peripherals, often with some specific type of 
application in mind, such as an auto engine controller. In this sense, 
interrupt priorities can still be application-specific.

Again, don't blame the priority concept for poor or deficient 
implementations of priorities.

> If you've ever had to "jigger" a priority, you should be asking,
> "why did I *have* to do this?

So don't "jigger" them. Use a systematic, mathematically proven priority 
assignment principle supporting a schedulability analysis method.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Sorry, but I don't have time to continue this discussion; I have
courseware to prepare and a project that needs to be specified and
finished in the next 4 weeks.

I'll leave you (and everyone reading) with one *simple* way to
"validate" the assertion that priority-based schedulers are
not toys (below):

On 7/7/2016 11:36 AM, Niklas Holsti wrote:
> On 16-07-07 09:16 , Don Y wrote:
>> On 7/6/2016 9:50 PM, George Neuner wrote:
>>> On Wed, 6 Jul 2016 21:37:12 +0300, Niklas Holsti
>>> <niklas.holsti@tidorum.invalid> wrote:
>>>
>>>> On 16-07-06 13:06 , Don Y wrote:
>>>>
>>>>> As I said before, priorities tell you nothing about the timeliness
>>>>> constraints of tasks.  You can just as well give them names of
>>>>> fruits and vegetables and rank them using whatever criteria *seems*
>>>>> to work, today...
>>>>
>>>> I think you are looking at priorities from the wrong perspective -- a
>>>> too high-level perspective.
>>>>
>>>> Task priorities are a design and coding mechanism, of the same nature as
>>>> procedures, statements, while-loops, if-then-else statements, and so on.
>>>> Just as if-then-else statements let the designer tell the processor
>>>> which of two statements should be executed, depending on some
>>>> application-specific condition, so priorities let the designer tell the
>>>> RTOS scheduler which of two tasks/threads should be executed in
>>>> preference to the other, depending on some implementation-specific
>>>> analysis or priority assignment rules.
>>>
>>> I think Don's point is that task priorities are merely a proxy for the
>>> actual scheduling criteria - whatever that may be.
>>
>> Exactly.  "Priority" (in the sense of "set_task_priority()") is just
>> an expedient to make coding a scheduler easy.  It tells you *nothing*
>> about the task's "importance", "timeliness constraints", etc.
>
> That is not so, if you follow a systematic and proven priority-assignment rule.
> For example, if you use deadline-monotonic priorities then the order of task
> priorities is equivalent to the order of task deadlines (expressed as the
> maximum duration between task activation and completion). So then the task
> priorities certainly tell you a lot about the (relative) timeliness constraints.
>
> If you just assign priorities based on some subjective "task importance"
> feeling, your statement is valid.

Then, EVERY product that employs a priority-based scheduler should have a
FORMAL document in part of its deliverables that clearly states these
priorities and the method by which they were derived (as you later call
them "the basis for one important set of the mathematical methods for
verifying real-time performance: schedulability analysis").  So, the
next bloke to look at the code knows exactly why they were chosen and
which assumptions he/she must *continue* to operate under for those
priority assignments to remain valid.

Ask yourself how many of those documents you've seen?  Authored?

If you're having a hard time coming up with one for EVERY such
system you've been exposed to, then where's the "mathematical
method" involved?  Or, is it just "some suggestive feeling"
that led to the small integers chosen?

     "I think I'll put a 2 amp fuse in this circuit... (why?)"

On 16-07-07 22:06 , Don Y wrote:
> Sorry, but I don't have time to continue this discussion;

I'm not in a hurry; come back when you have time.

> I'll leave you (and everyone reading) with one *simple* way to
> "validate" the assertion that priority-based schedulers are
> not toys (below):

[snips]

Don Y wrote:
>>> Exactly.  "Priority" (in the sense of "set_task_priority()") is just
>>> an expedient to make coding a scheduler easy.  It tells you *nothing*
>>> about the task's "importance", "timeliness constraints", etc.

Niklas Holsti wrote:
>> That is not so, if you follow a systematic and proven
>> priority-assignment rule.
>> For example, if you use deadline-monotonic priorities then the order
>> of task
>> priorities is equivalent to the order of task deadlines (expressed as the
>> maximum duration between task activation and completion). So then the
>> task
>> priorities certainly tell you a lot about the (relative) timeliness
>> constraints.
>>
>> If you just assign priorities based on some subjective "task importance"
>> feeling, your statement is valid.

Don Y wrote:
> Then, EVERY product that employs a priority-based scheduler should have a
> FORMAL document in part of its deliverables that clearly states these
> priorities and the method by which they were derived (as you later call
> them "the basis for one important set of the mathematical methods for
> verifying real-time performance: schedulability analysis").  So, the
> next bloke to look at the code knows exactly why they were chosen and
> which assumptions he/she must *continue* to operate under for those
> priority assignments to remain valid.

Ideally yes, just as every mechanical engineering project should 
document its design assumptions, stress and strength calculations, etc., 
and every SW project should deliver full design documentation, complete 
user manuals, maintenance manuals, etc.

But seriously, documentation requirements are a different dimension from 
the choice of design and implementation methods. Using a systematic 
design method does not oblige you to document the design, although it 
makes it much easier to document it.

> Ask yourself how many of those documents you've seen?  Authored?

Several, for both questions. All the day-job projects I work on have 
such, and I am usually the author.

> Or, is it just "some suggestive feeling"
> that led to the small integers chosen?

No. From the requirements, I derive a set of tasks and deadlines, and 
then assign priorities in deadline-monotonic order. Then I analyse or 
measure WCETs and crank the response-time algorithm to check 
schedulability. The main problem is that the task interactions are often 
more complex than assumed by the simpler schedulability analysis 
methods. Fortunately, in my projects it is usually possible to separate 
hard-real-time tasks from soft-real-time tasks, and the interactions of 
the hard-real-time tasks tend to be rather simple.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

On Thu, 07 Jul 2016 21:36:29 +0300, Niklas Holsti wrote:

> On 16-07-07 09:16 , Don Y wrote:
>> On 7/6/2016 9:50 PM, George Neuner wrote:
>>> On Wed, 6 Jul 2016 21:37:12 +0300, Niklas Holsti
>>> <niklas.holsti@tidorum.invalid> wrote:
>>>
>>>> On 16-07-06 13:06 , Don Y wrote:
>>>>
>>>>> As I said before, priorities tell you nothing about the timeliness
>>>>> constraints of tasks.  You can just as well give them names of
>>>>> fruits and vegetables and rank them using whatever criteria *seems*
>>>>> to work, today...
>>>>
>>>> I think you are looking at priorities from the wrong perspective -- a
>>>> too high-level perspective.
>>>>
>>>> Task priorities are a design and coding mechanism, of the same nature
>>>> as procedures, statements, while-loops, if-then-else statements, and
>>>> so on.
>>>> Just as if-then-else statements let the designer tell the processor
>>>> which of two statements should be executed, depending on some
>>>> application-specific condition, so priorities let the designer tell
>>>> the RTOS scheduler which of two tasks/threads should be executed in
>>>> preference to the other, depending on some implementation-specific
>>>> analysis or priority assignment rules.
>>>
>>> I think Don's point is that task priorities are merely a proxy for the
>>> actual scheduling criteria - whatever that may be.
>>
>> Exactly.  "Priority" (in the sense of "set_task_priority()") is just an
>> expedient to make coding a scheduler easy.  It tells you *nothing*
>> about the task's "importance", "timeliness constraints", etc.
> 
> That is not so, if you follow a systematic and proven
> priority-assignment rule. For example, if you use deadline-monotonic
> priorities then the order of task priorities is equivalent to the order
> of task deadlines (expressed as the maximum duration between task
> activation and completion). So then the task priorities certainly tell
> you a lot about the (relative) timeliness constraints.
> 
> If you just assign priorities based on some subjective "task importance"
> feeling, your statement is valid.
> 
>> The advantage to deadlines (if we can avoid the RT taint) is that they
>> are "portable" -- a description of a deadline in a particular
>> application can be related DIRECTLY to a deadline in some completely
>> unrelated application:  they share an axis and unit of measure!
> 
> Yes, and priorities can represent deadlines, see above, in which case
> priorities are portable, too.
> 
>> "Priority" (in the "set_task_priority()" sense) is just a completely
>> bogus number that ONLY means something in the context of the PARTICULAR
>> set of tasks that it is currently bound.
> 
> Priorities are instructions to the scheduler. I agree that they have
> meaning only for a particular task set, because they represent only the
> *relative* scheduling preferences between the tasks in this set.
> 
>> Is "2" twice as "important" as "1"?  Half as "important" as "4"?
> 
> Those are meaningless questions. Priorities are an ordinal scale, not an
> interval or ratio scale
> (https://en.wikipedia.org/wiki/Statistical_data_type).
> 
>> The folly of "priority" (set_task_priority) in scheduling is
>> illustrated in my immediately preceding example:  why don't other
>> actors performing services on behalf of a task "having" (executing at)
>> priority 'P' *assume* that (scheduling) priority while acting on its
>> behalf?  Magically, the priority of the activities being performed to
>> achieve your (task's) goal have changed -- just because some other
>> agency is performing them!?
> 
> One can certainly design and implement such a priority-inheritance
> mechanism in a system, even a distributed system (though in the latter
> case one would have to define a system-wide priority scale). I know of
> two examples for non-distributed systems: priority inheritance for
> resources (https://en.wikipedia.org/wiki/Priority_inheritance) and
> priority inheritance occurring when one Ada task requests a service from
> another Ada task
> (http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-D-1.html).
> 
> Don't blame the priority concept for poor or deficient implementations
> of priorities.
> 
>> "Priority" (in scheduling) is just a sort of efficiency hack.
> 
> No, it is the basis for one important set of the mathematical methods
> for verifying real-time performance: schedulability analysis.
> 
>> It's a direct carry-forward of interrupt priorities:  those being
>> scheduling decisions MADE IN HARDWARE at the level of the interrupt
>> controller (which acknowledges the fact that two or more different
>> activities are likely to occur simultaneously and something has to make
>> a CHOICE among them as to which ONE to grant access to the CPU for this
>> ISR).
> 
> Yes, so? This is "scheduling", and it applies as well to HW as to SW. In
> fact, there have been HW implementations of SW task schedulers -- RTOS
> "accelerators".
> 
>> And, if you look at most hardware systems, the activities mapped onto
>> individual IRQ "levels"/priorities are defined solely by the hardware
>> (chip) manufacturer.  The user/implementor has very little option how
>> to rearrange the relative priorities/levels AS IMPLEMENTED IN THE
>> HARDWARE; you can't arbitrarily decide that the priority levels should
>> be:
>>     UART_RxReady UART_TxReady ParityError PowerFail ReceiverOverrun
>>     NetworkPacketAvailable BREAK detected
>> vs:
>>     NetworkPacketAvailable BREAK detected UART_TxReady ParityError
>>     PowerFail UART_RxReady ReceiverOverrun
> 
> The SPARC processors I am familiar with do allow the application to
> configure the priorities of interrupts, to some extent.
> 
> Before microcontrollers and systems-on-chip, in the minicomputer era,
> many systems allowed application-specific interrupt priorities, because
> the priority of a peripheral interface was defined by the number of the
> slot into which the interface board was plugged.
> 
> The interrupt systems of CPU cores usually number the external interrupt
> lines and use the number as the priority. When the CPU core is embedded
> in an SoC or a microcontroller, the system designer assigns interrupt
> lines to on-chip peripherals, often with some specific type of
> application in mind, such as an auto engine controller. In this sense,
> interrupt priorities can still be application-specific.
> 
> Again, don't blame the priority concept for poor or deficient
> implementations of priorities.
> 
>> If you've ever had to "jigger" a priority, you should be asking,
>> "why did I *have* to do this?
> 
> So don't "jigger" them. Use a systematic, mathematically proven priority
> assignment principle supporting a schedulability analysis method.

You know, I've had nearly this same conversation with him (you're giving 
more detail, though).  About a month ago.  It didn't stick.  He's either 
very obtuse, or he's enjoying himself.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!

On Thu, 07 Jul 2016 23:09:08 +0300, Niklas Holsti wrote:

> On 16-07-07 22:06 , Don Y wrote:
>> Sorry, but I don't have time to continue this discussion;
> 
> I'm not in a hurry; come back when you have time.
> 
>> I'll leave you (and everyone reading) with one *simple* way to
>> "validate" the assertion that priority-based schedulers are not toys
>> (below):
> 
> [snips]
> 
> Don Y wrote:
>>>> Exactly.  "Priority" (in the sense of "set_task_priority()") is just
>>>> an expedient to make coding a scheduler easy.  It tells you *nothing*
>>>> about the task's "importance", "timeliness constraints", etc.
> 
> Niklas Holsti wrote:
>>> That is not so, if you follow a systematic and proven
>>> priority-assignment rule.
>>> For example, if you use deadline-monotonic priorities then the order
>>> of task priorities is equivalent to the order of task deadlines
>>> (expressed as the maximum duration between task activation and
>>> completion). So then the task priorities certainly tell you a lot
>>> about the (relative) timeliness constraints.
>>>
>>> If you just assign priorities based on some subjective "task
>>> importance" feeling, your statement is valid.
> 
> Don Y wrote:
>> Then, EVERY product that employs a priority-based scheduler should have
>> a FORMAL document in part of its deliverables that clearly states these
>> priorities and the method by which they were derived (as you later call
>> them "the basis for one important set of the mathematical methods for
>> verifying real-time performance: schedulability analysis").  So, the
>> next bloke to look at the code knows exactly why they were chosen and
>> which assumptions he/she must *continue* to operate under for those
>> priority assignments to remain valid.
> 
> Ideally yes, just as every mechanical engineering project should
> document its design assumptions, stress and strength calculations, etc.,
> and every SW project should deliver full design documentation, complete
> user manuals, maintenance manuals, etc.
> 
> But seriously, documentation requirements are a different dimension from
> the choice of design and implementation methods. Using a systematic
> design method does not oblige you to document the design, although it
> makes it much easier to document it.
> 
>> Ask yourself how many of those documents you've seen?  Authored?
> 
> Several, for both questions. All the day-job projects I work on have
> such, and I am usually the author.
> 
>> Or, is it just "some suggestive feeling"
>> that led to the small integers chosen?
> 
> No. From the requirements, I derive a set of tasks and deadlines, and
> then assign priorities in deadline-monotonic order. Then I analyse or
> measure WCETs and crank the response-time algorithm to check
> schedulability. The main problem is that the task interactions are often
> more complex than assumed by the simpler schedulability analysis
> methods. Fortunately, in my projects it is usually possible to separate
> hard-real-time tasks from soft-real-time tasks, and the interactions of
> the hard-real-time tasks tend to be rather simple.

I have never had a problem doing this separation myself, although I've 
inherited code from other people that fails at this, and rather badly.  
The most egregious example of this was code that put the most important 
two jobs into one superloop inside of one task -- and did so in such a 
way that bollixed up the whole system if incoming commands exceeded a 
rather moderate rate.

I'm not entirely sure, but I think there's a possibility that if your 
code _does_ have such an interaction between tasks, then it means that 
there's something fundamentally wrong with your software design, or 
possibly your system design as a whole.

-- 
Tim Wescott
Control systems, embedded software and circuit design
I'm looking for work!  See my website if you're interested
http://www.wescottdesign.com