Hi Marc,
Marc Jet wrote:
> I notice there is some overlap between what we came up with :-)
<grin> If you do this sort of thing long enough, you end up
touching on damn near every possible implementation strategy
(unless, of course, you take a pedestrian approach to it and
"settle" for "the first thing that works" :> )
>> Do you put the Scheduler into the same set of signal consumers?
>> (that would be cool as it would let scheduling be treated as just
>> another "thread")
>
> I don't understand the question. Maybe the comments below resolve it,
> otherwise please elaborate. What can be said is that both the ISR and
> Attach/Detach work at the same abstraction level (they reprogram the
> timer hardware). On the task switching level, the ISR executes
> asynchronously and interacts with the scheduler, while Attach/Detach
> always execute in the context of the calling task. Due to a potential
> race, Detach sometimes also interacts with the scheduler.
I *think* that's close to what I am suggesting (asking) above
(barring terminology).
I've taken several approaches to the *basic* structure of
timer/scheduler over the years (here, I am ignoring implementation
of the actual timers themselves but, rather, how the "timing
service" relates to the "scheduling").
By far, the most common approach has been to create a periodic
interrupt ("tick") that the hardware uses to signal a *timing*
service. This directly or indirectly updates the "timers"
(how is not important). A "special" timer is the "scheduling
timer" that defines the time left on the executing thread's
timeslice. When that timer expires, the scheduler is invoked to
"preempt" the current thread [there are lots of caveats, here,
that can be ignored... important thing is "scheduler sits atop
timing service"]. Again, the mechanism by which the scheduler
is invoked is not important (and can be varied).
[Note that the "tick" can thus be semantically different from
the "jiffy". Further, that threads can have different size
timeslices -- e.g., this allows finer partitioning of the
CPU *within* a priority level]
Also common with this scheme, time doesn't exist outside of
the scope of the "tick". A practical consequence of this is
that a thread that yields/blocks just prior to its timeslice
ending (to be pedantic: "just prior to the next tick") can
*cheat* the next thread to execute out of a portion of its
timeslice. This is because the scheduler runs (because of the
yield) AS IF it had run at the preceding tick. So, the next
thread is activated... and a tick comes along (coincidentally)
immediately thereafter! :>
You can work around this by crediting the thread with a partial
tick (in effect, increasing its timeslice by [0,1) tick) -- but
that just adds a bias in the other direction (i.e., instead of getting
cheated out of a tick, it *gets* some portion of a free tick).
To "fix" this problem, you can have the scheduler restart the
"tick interval" as it activates the next thread. In effect,
resynchronizing the tick with the jiffy at each thread activation.
In that case, a thread that does NOT block or yield is guaranteed
its entire timeslice.
But, now the tick is running at a varying frequency. (and, the
scheduler is having to muck with hardware!) This complicates
use of the tick (which drives the jiffy) for reliable timing.
You can "fix" this problem by running the timing services independant
of the scheduler (e.g., another "clock"). Or, you can "do the math"
(keep track of residuals) to track the "jitter" in this "clock"
so that scheduling/timing are unaffected (i.e., compensated).
Or, just live with the problem. (i.e., pretend it doesn't happen often
and/or that it happens "equally" to all threads)
What I was suggesting was letting the timing service run the
IRQ exclusively. It peeks at an ordered queue of "timers"
and programs the hardware timer (clock) with the period of
the next timer (at head of queue). I.e., this is the soonest
"thing" (temporal event) that is going to happen so any "clock"
IRQ's prior to that would be "uneventful".
Now, have the scheduler feed events (which should be at most one?)
into that same queue. So, coincident with activating the next
thread to execute, the scheduler injects a timer event into that
queue with an expiration time of "now + timeslice" -- and *remembers*
a handle for that event!
If the scheduler gets invoked prior to that time, it has the
responsibility of deleting that (no longer pertinent) event
and reinserting a *new* one for the thread that it is activating
*now* (which may have a different timeslice!).
The problem with this approach is there is nothing that limits
the granularity of events in that queue. E.g., if you allow time
to be specified in "timer clock cycles", then you could
conceivably have the two events in the queue differing by only
a few clock cycles -- too close temporally to be handled as
distinct events. (so, you want to be restrict the values
that can be used for "times" -- which brings you back to the
first implementation -- effectively)
>> It still seems to avoid the (to me) obvious chances for
>> optimization/exploitation -- e.g., these timeouts aren't
>> "general purpose timers" that can be used to initiate
>> events. They are *always* used in the same way -- to
>> unblock a thread waiting on some service/resource.
>> If all services are synchronous, then a thread can ONLY
>> be blocking on one at a time. I.e., there is only need for
>> one "service timer" per thread. And, that the use of that
>> timer is preordained.
>
> Not necessarily. In the async API described in my previous post, the
> "timer signal" describes a moment in time and triggers when that
> moment is reached. The trigger mechanism is implemented using my
> abstract concept of signal producers (which in this case represents
> the timer ISR side), and the trigger event manifests as signal on the
> sensor (which always represents a task).
>
> A task can block on one or multiple sensors. The obvious use case for
> blocking on a single sensor is the sleep() function. A use case for
> multiple sensors, is to wait for IO to finish plus a timeout.
>
> At first sight it doesn't make sense to simultanously block on
> multiple timer signal sensors, because there is always one to time out
> first. But even that is a possible use case! Specifically when a
> function implements own timeouts and ALSO honors timeouts from the
> upper layers (e.g. given as function argument). If it wasn't allowed
> to block on multiple timeouts simultanously, it would have to deep-
> inspect them all and find the first one to expire.
Correct. I allow any number of "general purpose" timers.
Note that I also allow timers to be inspected. I.e., a
consumer can "time" how long something takes (and that
thing can, in turn, time how long parts of *it* take, etc.).
This is essential if you want your code to adapt to the
temporal constraints of its environment (instead of just
breaking -- missed deadline -- as load increases). It
makes more sense to implement "timers" (as in "measure
elapsed time") this way and have the consumer track the
"initial value" than to have the timing service do it.
> Note that my signal sensors and producers are generic entities, while
> the timer signal is a specific implementation using them. Although
> it's the most prominent one that I made and use, the producer / sensor
> concept is generic IPC and removes the task scheduling aspects from
> drivers and ISRs.
Understood.
> BTW your example code snippet, ported to my polled API, would look
> almost identical. Except there is no handle + struct/object, but
> rather the handle IS the struct/object.
Yes -- but then you can't drag the timer out of the user's
address space. I.e., the user can always directly access
the contents of the timer struct in your implementation.
My API allows the OS to "hide"/protect the timer *from*
the "user" (a bug in your code overwriting some key part
of the struct could crash the timer service, for example).
> This is a very important thing to understand. There can be as many
> independent time references as the application desires. They can be
> duplicated, passed to other modules, and dropped without caring about
> storage ownership.
Yes, though see above.
> From the multitasking point of view, with the polled API there's no
> effect beyond the current task.
Yes, the current task (thread) essentially acts as its own
timing service. OTOH, there are no guarantees that it will
promptly "see" an expired timer (e.g., the entire thread may
be blocked when the timer expires; or, the thread may not
be executing that code when the timer actually expires).
The first MTOS that I designed used a similar timing service
except the timers were updated by a "timer thread" (i.e.,
timers were no different from any other "task"/service).
The timer thread, in turn, polled a global variable updated
by the tick ISR (i.e., nothing happened in the tick ISR
other than incrementing a counter). Timers were arranged
in an array (that the timer thread managed). A consumer
could directly reference the value *in* a timer (e.g.,
by accessing "timer[i]").
This made for an incredibly powerful programming model.
Since checking the timer was very efficient, you wrote
code like:
if (DATA_AVAILABLE != check_uart()) {
/* nothing here, yet */
if (timer[UART_TIMEOUT] > 0) {
/* timer hasn't yet expired */
blink_light();
/* keep waiting */
yield();
} else {
/* timeout waiting for data */
}
} else {
/* received data; process it */
}
I.e., it was *faster* to just peek at the timer's
current value and "yield" than it was to implement
an API to "wait_for_timer()". It also let you *do*
things while waiting which, otherwise, required a
separate thread *or* a heavier implementation.
(I still use this approach on *tiny* designs)
> With the async API on the other hand,
> there's a common (sorted) list for all timer signals that are
> "attached" to the global producer (which basically is the timer ISR).
> "Attaching" DOES affect beyond the scope of the current application
> (cpu-wise, not memory wise). More timer signals on the list
> translates to slower attaching for everybody, and also more ISR
> activity.
>
>> I think I'll see what the cost of including it as part of
>> the thread state and an implicit part of the scheduler gives
>> me in terms of performance and cost.
>
> Merging my polled API into the thread would not be beneficial, because
> it would prohibit using several timeouts at once. They are useful for
> nested timeouts, e.g. when a subfunction decides to implement a
> timeout without exposing it on the API. Also, in more complex
> statemachines I often find myself using several time references
> simultanously (e.g. last character received, last some_event, last lcd
> update).
>
> If you referred to merging the async timer signals into the thread, it
> may have less negative impact - but still has. It would reduce them
> to really just be "an absolute timeout" for "the current activity".
Exactly. The "current activity" is a service invocation.
Since service invocations are synchronous (my choice), there
can be only one (for each thread). Note that this does not
preclude having general purpose timers -- as many as you
want -- in addition to this "service timer". I'm just
exploiting the fact that the "service timer" has a fixed
and inflexible role. It need not have the same capabilities
of a general purpose timer (e.g., it *belongs* to a particular
thread; something that isn't necessarily a requirement to
be imposed on general purpose timers).
I think this will let me make it lightweight enough that
it ends up a net savings over using a general purpose timer
for the same purpose (both in terms of space *and* time).
> It would mean that there (suddenly) must be a strict boundary between
> OS functionality (which unconditionally aborts all action upon
No. OS doesn't have to "abort" anything. I.e., if I were
to implement deadline handlers to do this same sort of thing,
then they *would* (typically) abort pending/blocked operations
9service calls). [this makes coding the application simpler
but adds a lot of machinery in the OS -- as well as forcing the
application to handle the asynchronous nature of aborted
services].
If, OTOH, I adopt the *practice* that every service supports
the concept of a timeout and is *coded* with this in mind,
then they can assume (at some cost) the responsibility of
watching -- and compensating -- for their own missed deadlines.
> timeout) and application functionality (which initiates retry
> mechanisms and sane error handling, instead of just passing the
> timeout error upstream). Also, to a lesser degree the previous
> paragraph also applies here.