Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #29043

Re: Task priorities in non strictly real-time systems

Show all headers | View raw

[attrs elided]

On 1/6/2020 6:39 AM, upsidedown@downunder.com wrote:
>> [There are certain contexts where it takes on very specific -- and
>> numerical -- meanings]
>>
>> There's nothing magical about the jiffy.  But, it's typically
>> wired to an IRQ (directly or indirectly).  With all the right
>> mechanisms in place for a preemptive system, the jiffy can just
>> raise an event (JIFFY_OCCURRED) and a very high priority "task"
>> *in* the kernel will be dispatched which will run the scheduler.
> 
> Unless you want to update a time of day time clock, what is the use of
> regular timer interrupts ?

It gives you a quantifiable way of accounting for the passage of time.

How do you blink an indicator at a nominal rate without some notion of
when it's next time to turn it on/off?

How do you detect a long SPACE on a serial port line?

A "regular" timer IRQ typically drives your timing system.  Apps
then use *that* for their notion of elapsed time (both to measure and
to wait/delay)

> In some systems an I/O may arm a one shot clock interrupt waiting for
> the I/O or until a timeout occurs. If the I/O is completed in time,
> the receiver routine disables the timer request and the timer
> interrupt never occurs.

Wonderful if you have a HARDWARE timer to dedicate to each such use.

How do you decide when to drop a TELNET connection because you've not
received a keep-alive in the required interval?  How many such sessions
can you keep active at a time?

[Sharing hardware timers is fraught with opportunities to f*ck up.
You inevitably end up missing events because they occur to close
in time *or* they occur before you can finish the bookkeeping to
set up the timer for "them"!]

> The scheduler needs to be executed only when a "significant event"
> such as an interrupt or task going to wait for a significant event
> will occur,  no need to run it for routine clock interrupts, unless a
> timeout has occurred.

The scheduler SHOULD be run any time something that COULD alter the
run-queue has happened.  (There are lots of opportunities to inject
hints that can dramatically reduce the need to run when nothing
really HAS happened to the run queue)

E.g., if your system doesn't allow tasks to block awaiting memory
resources (imagine blocking INSIDE a malloc!), then there's no need
for the scheduler to be run when the current memory allocation
changes (e.g., in free()).

Note that a lot of dubious systems DON'T run the scheduler as
often as they should.  Instead, they rely on a lazier evaluation strategy
and may delay the scheduler's execution to some other convenient
"happening" -- like a periodic interrupt (in a "time-sliced" system)

IMO, this results in clumsier applications.  If I "do something"
(e.g., raise an event) then I should be able to KNOW that the next line
of code won't have been executed until the task (of higher priority,
BY DESIGN) *waiting* on that event has had a chance to run.

[There's no guarantee that it will run *immediately* -- there may be
other tasks that are higher priority than "I" that could also sneak
in; but, the intended task WILL run before I get another chance!
Unless it's not currently waiting!]

>> An event raised by a UART IRQ can be handled identically.  The
>> task(s) that are waiting on the assertion of that event are
>> "immediately" run as the scheduler discovers them to be ready
>> (and, presumably, of sufficient "priority" to cause the currently
>> running task to be preempted).
> 
> In a typical RT system nearly all (and most of the time all) task are
> in some sort of wait state waiting for a hardware (or software)

Misconception.  That depends on the system's utilization factor
which, in turn, depends on the pairing of hardware resources to application
needs.

I build an STB.  Two conceptual tasks:  one records video (when needed);
the other elides commercials in recorded video (which may be "live"
from the recording task *or* clips that have been accumulated, over
time.)

Yeah, the "recording" task may sleep waiting for an "alarm clock event"
to command it to record an upcoming broadcast.  But, the commercial
zapper is willing to use every possible CPU cycle available to
finish its job.

In applications where the hardware is under-provisioned, the system
runs "in overload", at times, and plays catch-up when the load
decreases.  It may NEVER be able to twiddle its thumbs!

> interrupt. Some time one or more tasks can become runnable due to some
> event and on a single processor system the one runnable task with
> highest priority (first in the runnable task list) is running
> (executing).

>> As an "event" carries no real information (data) beyond the fact
>> that it *occurred*, it is typically a very lightweight mechanism.
>> There are typically very few of them supported by the OS -- often
>> defined by the number of bits in the native "word size" (this
>> allows a task to specify a *set* of events in which it may have
>> an interest -- as a bit-vector; any ONE will suffice).  This
>> simplifies the work of deciding if ANY of the waiting task's
>> significant events have made it eligible to run.
> 
> In a more complicated systems each task could be waiting for a mask of
> events and if the system wide mask has one of the same mask (wait for
> logical OR) or until all (wait for logical AND) required bits are set.
> However, this still needs scanning the task list in priority order.

"Scanning" implies a sequential activity.  Most systems store the
run queue in priority-sorted order.  So, the head of the queue *is*
the next task to select.  (after the effects of the "event" have
been reflected to the LIST of tasks enqueued on those events)

[These sorts of algorithm optimizations differentiate MTOS implementations
from RTOS as the "professional" RTOS implementations go to pains to
make operations predictable in their timeliness; an MTOS just has to
implement *functionality*]

>> [Note that events are transient; they aren't stored like "flags".
>> So, if an event happens and you're not watching for it, you never
>> *see* it!]
> 
> Depends on implementation.

If events "latch", then you have to store the fact that a waiting
task has *seen* its assertion.  AND, you have to be able to differentiate
between it having seen the FIRST assertion vs. the NEXT assertion.

By contrast, a "flag" is just a bit of state that can be examined.

>>> Here is example how a very simple pre-emptive RT kernel worked:
>>>
>>> In the original version for a processor with only a few registers and
>>> when the hardware saved all registers on the stack before the
>>> interrupt service routine (ISR) was executed and restored after the
>>> return from interrupt instruction was executed.
>>>
>>> When the system was started in the main program, a subroutine call was
>>> executed for each task to be created. This subroutine allocated a
>>> local stack for the task as well as a 3 byte task control block
>>> consisting of 1 byte task state and 2 byte saved stack pointer. The
>>> task was started, which then performed a software interrupt storing
>>> original registers for that task on the local stack.
>>
>> This (storing present state on the task's stack) is a common approach.
>> It is also possible to store the register state *in* the TCB (a larger
>> structure being needed for that).  But, these are just efficiency tradeoffs.
> 
> If you put the local stack in the TCB, you either have to use a fixed
> size stack for each task or use a linked list to access the next TCP.

No.

There need be NO stacks (see my other comments on this).

There's no requirement that the processor state must reside ON
the TOS.

The TCBs can be implemented as an array, indexed by the "task id"
(or, referenced by a "TCB*").

The state can be "manually" stored (in the context switch) into
the "current" TCB (by dereferencing TCB* or index into array)
and the state of the newly selected task can be "manually restored"
from its TCB as it is activated.

The TCB has everything pertinent to the task accessible through it.
The task's "priority" (or other scheduling criteria), state, list
of resources held by it, etc.

In my RTOSs, I keep the state of the floating point unit (regardless of
whether it is a piece of hardware or a software emulation) in a set
of separate structures.  If a task declares that it has no need of the
FPU, then it has no need for such a structure.  OTOH, if a task DOES
use the FPU, then the TCB contains a link to that structure.

[This allows for lazy updates to the FPU as well as support for
true concurrent processing in the FPU.  I.e., what if the FPU
hasn't finished a computation when you decide it's time to switch
tasks?  Do you spin waiting for it?  What if the next scheduled
task has no need for the FPU resource?  Why sit there waiting
if you could just leave the FPU as an independent actor to work
as/how it wants??]

> In the scheduler walking through a linked list is often less effective
> than selecting the next entry in an array on a small microprocessor.

Then the scheduler has to manipulate that list as "happenings"
alter it.

>>> executed using the local stack, potentially altering the runnability
>>> of some other dormant task.
>>>
>>> Before performing a return from interrupt the scheduler was executed.
>>
>> The problem with this is that the scheduler may end up being bulky
>> and take a nontrivial amount of time to make up its mind.
> 
> The RT kernel described above for 6809 was about 1-2 KB and even with
> a dozen tasks took 36 instructions (worst case) to find which the next
> task should be executing. Stack manipulation in task swathing required
> some additional instructions.

On small processors, you can implement the basics of an MTOS in
a few hundred bytes -- depending on what you decide you NEED to
code in that environment.  On a Z180, I think I could yield()
from the current task to the next task in ~8 microseconds (?).

If you can keep this overhead low/fast, then you can engage in
vary different programming styles without compromising the
application.

["Programming in the small" is an educational experience as you
question EVERY assumption as to its actual "essentialness" and
effectiveness.]

>> Another approach is to "schedule" the scheduler to run at the COMPLETION
>> of the ISR.  I.e., interpose the scheduler's invocation between the
>> "return-from-interrupt" and the actual "return to task that was interrupted".
> 
> I just tried to explain that the scheduler is executed after the ISR
> code but before executing the return from interrupt instruction either
> to the just interrupted task or to a separate task interrupted seconds
> or days earlier.

But you need to take special steps to ensure the ISR returns to the SCHEDULER
and not to the interrupted task.  The norm is to let the ISR return to the
task and wait for the scheduler to be invoked at some time later (e.g.,
in a time-slicing system)

>>> The scheduler checked the task state byte of each created task
>>> (requiring just 3 instructions/task). If no new higher priority task
>>> had become runnable, the scheduler performed a simple return from
>>> interrupt restoring the registers from the local stack and the
>>> suspended task was resumed.
>>
>> Deciding and picking can often be far more complicated actions.
>> And, the criteria used to make that selection are often not simple
>> (static?) priorities.
> 
> Why complicate things with dynamically changing priorities ? For
> avoiding priority inversion or improve user responsiveness ? But as I

I find the whole notion of "priorities" to be abhorrent.  It suggests
that you KNOW what the priorities SHOULD be -- as part of the DESIGN
of the system.  In practice, they tend to be twiddled after-the-fact
when things don't quite work as you'd HOPED (i.e., you screwed up
the design and are now using a rejiggering of priorities to try to
coax it into behaving the way you'd HOPED)

When you assign arbitrary numeric values to impose an ordering on
tasks ("relative importance"), do you prepare a formal justification
for those choices?  A *rationale* that defends your choices?

(If you put a 1/2W resistor in a circuit, you'd be prepared to explain
EXACTLY why it was needed, wouldn't you?)

And, any ordering of "relative importances" means that each new addition
to the system ("task list") *or* refactoring means you have to reevaluate
those decisions.

You should schedule based on some other, more defensible criteria (e.g.,
deadlines in an RT system).

> said, having separate lists is justifiable only with a large number of
> tasks.

If the task that ends up being ready is always at the (far!) end of the
list, then your context switch takes artificially longer.

> Try to avoid risk for priority inversion by avoiding complicated
> locks.
> 
> Just use fixed priorities.

Priority inversion doesn't ONLY manifest with "complicated locks".
It can happen any time you have competing uses for a "lock" by
tasks executing at different priorities.

A > B > C

C takes lock (because it just happened to get to that line of
code before anybody else got to THEIR line of code).  A preempts
C (perhaps it was waiting on some "happening" that only recently
came to pass).  A tries to take lock but is forced to block
because C is holding it.  IN THEORY, C would then be able to
run and finish up it's need for the lock, releasing it -- which
would "immediately" cause A to gain control of the processor
("preemption").  But, before C can release the lock, B runs
and twiddles its thumbs, thus preventing C from running
(which, in turn, prevents A from running).

> With hundreds of tasks it would make sense to have a separate lists of
> runnable tasks in priority order. There is no need to check for
> non-runnable tasks. When a task becomes runnable, it is moved from the
> waiting list to runnable list. In a well behaving RT systems, there
> are only one  or a small number of tasks in the runnable list.

Another misconception.  The number of runnable tasks has no bearing on
how "well behaved" the system is!

In a *small* system, I'll typically have:
- a task to "handle" each UART (a step above the ISR, implements line protocol)
- a task to scan the keypad switches (to detect and debounce key closures)
- a task to generate sounds
- a task to refresh the display (line by line, digit by digit, etc.)
- a task to interact with the user
- a task to interact with each mechanism/actuator
- a task to provide timekeeping services
- a task to monitor AC mains power
- a task to monitor battery charge level (charging and discharging)
etc.

Each of these tries to be greedy as how quickly they can achieve their goals
is directly reflected in the device's performance.  Granted, UART handlers are
effectively rate-limited by the line-rate in use -- but, that can always be
changed (configuration) by the user/operator (and the handlers would have
to keep up with any new rate!)

Such systems can continue to run well into overload -- but, with noticeable
impact on their performance.  (if there is NO impact on performance, it
suggests that the system is overprovisioned for "nominal" use!)

>> Imagine how you'd implement multitasking in a *tiny* PIC!
>>
>> [This last restriction proves to be of little consequence when
>> designing for small processors -- that often can't AFFORD a stack
>> per process and would be content to share the same stack for ALL
>> processes!]
> 
> I do not know about PICs but even primitive processors like 6502 with
> 256 byte stack pointer addressability range could support multiple
> stacks. With simple processors with a few registers a 32 bytes/task
> stack was more than enough.

Some devices have TINY stacks (e.g., a handful of levels) and/or don't
let you alter or examine the stack's contents (it's just a BAL mechanism)

>>> Thus, a RT kernel can be really simple.
>>
>> The semantic issue becomes one of deciding whether or not the
>> implementation really provides RT services and guarantees.
> 
> What services ? The RMX-80 for 8080/8085 was quite adequate, the
> RMX-86 for 8086/8088 was bloatware :-).
> 
> The RT kernel doesn't give any timeliness quarantees other than
> execution in priority order, it is up to the application programmer to
> make sure that the high priority tasks do not consume too much time.

I adopt the convention that an RT solution provides timeliness guarantees;
otherwise, it's not RT.  Nor is RT "real fast".  (a Mars mission will be
real-time -- despite taking months!)  Nor is RT "life/mission critical".

(In RT, time is a primary aspect of the solution's "correctness")

This is yet another instance of how loose-goosey the taxonomy is (and
continues to become).  Having more rigid definitions of what terms mean
(and their implications) makes design easier -- because your thoughts
carry consequences instead of just "fuzziness".

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Task priorities in non strictly real-time systems pozz <pozzugno@gmail.com> - 2020-01-03 14:41 +0100
  Re: Task priorities in non strictly real-time systems David Brown <david.brown@hesbynett.no> - 2020-01-03 15:19 +0100
    Re: Task priorities in non strictly real-time systems pozz <pozzugno@gmail.com> - 2020-01-05 01:25 +0100
      Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-05 13:32 -0600
        Re: Task priorities in non strictly real-time systems Richard Damon <Richard@Damon-Family.org> - 2020-01-05 16:49 -0500
          Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-05 21:05 -0600
        Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-05 17:08 -0700
          Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-05 21:26 -0600
            Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-05 22:10 -0700
              Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-06 07:37 -0600
                Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-06 17:21 -0700
                Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-07 19:23 -0600
              Re: Task priorities in non strictly real-time systems Richard Damon <Richard@Damon-Family.org> - 2020-01-06 20:36 -0500
                Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-07 01:38 -0600
                Re: Task priorities in non strictly real-time systems Richard Damon <Richard@Damon-Family.org> - 2020-01-07 06:53 -0500
            Re: Task priorities in non strictly real-time systems George Neuner <gneuner2@comcast.net> - 2020-01-06 07:13 -0500
            Re: Task priorities in non strictly real-time systems David Brown <david.brown@hesbynett.no> - 2020-01-07 10:11 +0100
              Re: Task priorities in non strictly real-time systems Richard Damon <Richard@Damon-Family.org> - 2020-01-07 07:05 -0500
              Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-07 19:34 -0600
          Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-06 10:44 +0200
            Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-06 02:51 -0700
              Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-06 15:39 +0200
                Re: Task priorities in non strictly real-time systems George Neuner <gneuner2@comcast.net> - 2020-01-06 13:29 -0500
                Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-06 14:38 -0700
                Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-07 07:05 +0200
                Re: Task priorities in non strictly real-time systems George Neuner <gneuner2@comcast.net> - 2020-01-07 13:09 -0500
                Re: Task priorities in non strictly real-time systems Dimiter_Popoff <dp@tgi-sci.com> - 2020-01-07 20:53 +0200
                Re: Task priorities in non strictly real-time systems Clifford Heath <no.spam@please.net> - 2020-01-08 08:43 +1100
                Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-08 00:33 +0200
                Re: Task priorities in non strictly real-time systems Dimiter_Popoff <dp@tgi-sci.com> - 2020-01-08 15:26 +0200
                Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-08 00:08 +0200
                Re: Task priorities in non strictly real-time systems David Brown <david.brown@hesbynett.no> - 2020-01-07 10:37 +0100
                Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-06 16:10 -0700
                Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-07 07:37 +0200
                Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-07 01:49 -0600
                Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-07 06:43 -0700
                Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-07 10:21 +0200
                Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-07 06:42 -0700
                Re: Task priorities in non strictly real-time systems Richard Damon <Richard@Damon-Family.org> - 2020-01-07 22:23 -0500
                Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-09 22:07 +0200
                Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-07 10:54 +0200
                Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-07 06:43 -0700
          Re: Task priorities in non strictly real-time systems Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-06 18:01 +0100
            Re: Task priorities in non strictly real-time systems Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-06 19:47 +0200
    Re: Task priorities in non strictly real-time systems pozz <pozzugno@gmail.com> - 2020-01-05 01:58 +0100
      Re: Task priorities in non strictly real-time systems Clifford Heath <no.spam@please.net> - 2020-01-05 14:26 +1100
        Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-05 11:21 +0200
          Re: Task priorities in non strictly real-time systems David Brown <david.brown@hesbynett.no> - 2020-01-05 14:07 +0100
            Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-05 17:46 +0200
              Re: Task priorities in non strictly real-time systems David Brown <david.brown@hesbynett.no> - 2020-01-05 19:08 +0100
        Re: Task priorities in non strictly real-time systems David Brown <david.brown@hesbynett.no> - 2020-01-05 13:56 +0100
        Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-05 13:39 -0600
          Re: Task priorities in non strictly real-time systems Clifford Heath <no.spam@please.net> - 2020-01-06 07:44 +1100
            Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-05 21:00 -0600
              Re: Task priorities in non strictly real-time systems Clifford Heath <no.spam@please.net> - 2020-01-06 14:50 +1100
                Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-06 07:12 -0600
      Re: Task priorities in non strictly real-time systems Paul Rubin <no.email@nospam.invalid> - 2020-01-04 22:34 -0800
        Re: Task priorities in non strictly real-time systems David Brown <david.brown@hesbynett.no> - 2020-01-05 14:12 +0100
          Re: Task priorities in non strictly real-time systems Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-05 18:00 +0200
        Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-05 13:44 -0600
      Re: Task priorities in non strictly real-time systems George Neuner <gneuner2@comcast.net> - 2020-01-06 14:52 -0500
      Re: Task priorities in non strictly real-time systems George Neuner <gneuner2@comcast.net> - 2020-01-06 15:05 -0500
        Re: Task priorities in non strictly real-time systems gtwrek@sonic.net (gtwrek) - 2020-01-06 22:41 +0000
        Re: Task priorities in non strictly real-time systems Don Y <blockedofcourse@foo.invalid> - 2020-01-06 19:50 -0700
          Re: Task priorities in non strictly real-time systems George Neuner <gneuner2@comcast.net> - 2020-01-07 13:26 -0500
  Re: Task priorities in non strictly real-time systems Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-03 16:28 +0200
    Re: Task priorities in non strictly real-time systems pozz <pozzugno@gmail.com> - 2020-01-05 01:37 +0100
      Re: Task priorities in non strictly real-time systems Les Cargill <lcargill99@comcast.com> - 2020-01-05 13:46 -0600
        Re: Task priorities in non strictly real-time systems Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-05 22:44 +0200
  Re: Task priorities in non strictly real-time systems Rick C <gnuarm.deletethisbit@gmail.com> - 2020-01-03 11:49 -0800
  Re: Task priorities in non strictly real-time systems upsidedown@downunder.com - 2020-01-03 22:51 +0200
    Re: Task priorities in non strictly real-time systems pozz <pozzugno@gmail.com> - 2020-01-05 01:48 +0100
  Re: Task priorities in non strictly real-time systems Joe Chisolm <jchisolm6@earthlink.net> - 2020-01-03 15:34 -0600
  Re: Task priorities in non strictly real-time systems Richard Damon <Richard@Damon-Family.org> - 2020-01-03 21:46 -0500

csiph-web