rate monotonic scheduler + interrupt

On 11/11/14 18:27, Tim Wescott wrote:
> On Tue, 11 Nov 2014 08:57:52 +0100, David Brown wrote:
>
>> On 10/11/14 23:22, alb wrote:
>>> Hi Tim,
>>>
>>> Tim Wescott <seemywebsite@myfooter.really> wrote:
>>
>>>> I feel like I'm sending a kid fresh off the train from the city into
>>>> the deep dark woods with a rusty shotgun and a printed sheet
>>>> describing the differences between a black bear and a grizzly.
>>>
>>> Is there really a difference between them w.r.t. the kid?
>>
>> Either bear will chase you up a tree.  If it then climbs the tree and
>> eats you, it's a grizzly.  If it pushes the tree down and eats you, it's
>> a black bear.  That's the difference :-)
>>
>> (You might take that as a warning that you should read the shotgun's
>> manual before hunting bears.  I'm sure Tim can point you at a good book
>> that explains rate monotonic scheduling, among other things...)
>
> Actually, I learned all that stuff on the job, from various industry
> articles, from conference classes, and from discussions with experts.
>

That's where I learned too.  I had some basic electronics at school, and 
studied mathematics and theoretical computing (algorithm design, formal 
methods, etc.) at university - I learned practical embedded systems 
development on the job.

> I put up a good front, but I'm actually an analog circuit designer by
> training -- however, in this degenerate age the best and most versatile
> analog circuit building block is a good fast microcontroller with adequate
> analog to digital converters, or possibly with really good off-board ADCs.
> Aside from the conference classes, my only formal software training is a
> one-term course in college where we had to write code in assembly,
> Fortran, and (I think) Pascal.
>
> All the embedded software expertise is just so that I can make things work
> right.
>
> I'd recommend Jack Ganselle's "Art of Embedded Design" book, however, just
> because so many other people do.
>

Hi Al,

On 11/11/2014 12:40 AM, alb wrote:
> Don Y <this@is.not.me.com> wrote:
> []
>>> The need for an external interrupt is to serve a peripheral which has a
>>> very low throughput but whose information is crucial to system
>>> performance. The unit under discussion is what we call Local On Board
>>> Time (LOBT). It's a counter, which can be programmed to generate a
>>> periodic signal S on which the whole activity schedule is based.
>>>
>>> Now S has a period P ~1 sec. and I have to perform a certain number of
>>> activities within a time T after S is asserted, where T << P. Now in
>>> order to know whether S has been activated or not I can either poll it's
>>> status with a frequency that is < T, or I should react on an external
>>> interrupt.
>>>
>>> Unfortunately polling with that frequency will disrupt the other tasks,
>>> running in 'parallel', so I'd like to avoid polling for ~1 sec. to serve
>>> an event that is only happening once a second and is at the edge of the
>>> cycle.
>>
>> Why poll?  Can't you derive "S" from something ELSE that is already
>> periodic?  E.g., a higher frequency periodic IRQ that drives a
>> divider that creates "S"?  So, you (that higher frequency IRQ)
>> *KNOW* when S will occur!  E.g., let the IRQ assert an event that
>> S blocks awaiting.  Once the IRQ finishes, the scheduler sees that
>> S is now "ready" to run and starts it, automatically.
>
> Unfortunately this is not quite the case. The 'S' signal is periodic but
> the end user of the system may tune the period /slightly/ in order to
> compensate clock drifts.

Wait.  Let's back up.

Do *you* synthesize the S signal?  Or, is it something that The Outside World
provides that you *observe*?

Is it a real "signal" (in the sense of "a wire that twitches in a particular
way")?  Or, is it something more abstract (like a pattern in some data)?

> Therefore I cannot simply foresee when the 'S'
> signal will come. Sure is that I do have a time window within which 'S'
> will come.

How big is the window -- in absolute time units as well as a percentage of
S's nominal period?

> This uncertainty on the 'S' signal forces me to use an interrupt to
> break the current cycle sequence and start a new one. This means that
> the whole scheduler is working only in the specific 'S' period and when
> it reaches the end of the sequence it won't do anything until the next
> 'S' comes.

So, S is triggering an IRQ?  (If so, then there's no need to poll for it
as it announces itself very notably)

If not, what specifically do you use for the "interrupt"?

Or, do you mean that you (asynchronously) *abort* the current cycle sequence
when you detect a new 'S'?

On 11/11/2014 12:57 AM, David Brown wrote:
> On 10/11/14 23:22, alb wrote:
>> Hi Tim,
>>
>> Tim Wescott <seemywebsite@myfooter.really> wrote:
>
>>> I feel like I'm sending a kid fresh off the train from the city into the
>>> deep dark woods with a rusty shotgun and a printed sheet describing the
>>> differences between a black bear and a grizzly.
>>
>> Is there really a difference between them w.r.t. the kid?
>
> Either bear will chase you up a tree.  If it then climbs the tree and
> eats you, it's a grizzly.  If it pushes the tree down and eats you, it's
> a black bear.  That's the difference :-)

 From a visual graphic that I have, on hand:

    In light of the rising frequency of human/grizzly bear confrontations,
    the Wildlife Department is advising campers and hikers to take extra
    precautions and be alert for bears.  When in the wild, wear small bells
    on your clothing to avoid startling bears as you approach them, as you
    will often be unaware of their presence.  Carry a can of pepper spray
    to be used in case of an encounter.

    Be on the lookout for signs of bear activity.  These include fresh
    claw marks on tree bark, trampled foliage, etc.  Be particularly wary
    around streams and watering holes that wildlife may frequent.

    Being able to recognize the difference between black bear and grizzly
    bear droppings can alert you to the type of bears you are likely to
    encounter in your area.  Black bear droppings are smaller and contain
    lots of berries and fur.  Grizzly bear droppings have little bells in
    them and smell like pepper.

On Monday, November 10, 2014 5:22:54 PM UTC-5, alb wrote:
[]
> I'm thinking at architecture level, I have no idea whether it will be a 
> processor or an FPGA or a ton of bistable elements to perform the 
> scheduling. What I know is the cycle has a fixed, absolute, rate and I 
> can organize activities in order to achieve the required functionality 
> simply allocating the needed amount of bus utilisation to each unit.
> 
> I'm not sure I understood what you mean by 'design procedure' but if 
> this is the mental process involved in allocating resources to meet 
> deadlines, latency and throughput for each unit than I guess we are on 
> the same page.


Sounds to me like you are not thinking at the architecture level, but at the bit, clock cycle level.
> 
> > Rate monotonic scheduling is how you decide whether your real-time system 
> > will meet its design goals.
> 
> yep, and in my terminology is an algorithm in the sence of step-by-step 
> procedure to achieve a specific result. BTW the real-time system in this 
> case is probably sitting in an FPGA and can be a combination of an 
> embedded processor and an FSM. Probably the processor will be programmed 
> on bare metal, no RTOS.

An FSM is not a scheduler. (It can mimic one).

 And a scheduler may be included in a RTOS but it isn't necessarily an RTOS.

[]
> 
> Yet, I've seen several times full blown RTOSes mishandling concurrent 
> tasks and hanging up in ways are hard to describe. The KISS principle is 
> always applicable and if an RTOS is the simplest solution than by all 
> means I'm with it, but I'm far from convinced that I need to rely on 
> such solution for the current problem.

> 
> I can calculate with a rather good approximation how long is needed to 
> serve the interrupt, is a context switch *and* a bus transaction. I have 
> more problems in verifying if I *really* understood what rate monotonic 
> schedling is about.

I think you  don't. A scheduler has nothing to do with counting clock cycles,
approximate or exact.
> 
> First of all let's forget about RTOS and computing and let's reason in 
> terms of periodic tasks and a common resource they need to execute. The 
> common resource is the bus which allows transaction to occur (our tasks) 
> and each transaction has to occur with the above mentioned period.
> 
> In my case I do not necessary need to implement a preempting 
> multitasking method, but a simpler cooperative one. Transactions are 
> deterministic and do not need to be interrupted, they can simply be 
> 'splitted' in multiple chunks to allow /parallel/ execution.
> 

Yes, that is the do all loop programming, not a scheduler. have fun with that. Such a design is very brittle, meaning you go in the code next year, make a small bug fix, and it all comes crashing down!

> > In systems that have a heartbeat like this, it's often best to have a 
> > hardware interrupt that sets an event in the RTOS (or flag, or semiphore, 
> > or collection of events -- different RTOS's have different terms).  Then 
> > you want to have all the various tasks that need to fire off on that clock 
> > tick depend on the event.  You may well have different tasks with 
> > different priorities doing different things in response to the event.
> 
> That is a good point, indeed each task can be initiated immediately on 
> the interrupt, and through its priority I can serve all units according 
> to their needs. I should dimension the bus bandwidth to accommodate the 
> maximum throughput necessary for each unit, including the recovery 
> activity in case of a failure.
> 
> Al

Now you seem to be moving on the right train of thought.

Ed

>>>> I feel like I'm sending a kid fresh off the train from the city into the
>>>> deep dark woods with a rusty shotgun and a printed sheet describing the
>>>> differences between a black bear and a grizzly.

>>> Is there really a difference between them w.r.t. the kid?

>> Either bear will chase you up a tree.  If it then climbs the tree and
>> eats you, it's a grizzly.  If it pushes the tree down and eats you, it's
>> a black bear.  That's the difference :-)

Other way. Black bears climb. Brown bears (including grizzly) don't. But
they can run 30mph. So they'll get to the tree first.

Not really relevant, but I spent the night up a tree once in grizzly
country.

On Sun, 16 Nov 2014 19:04:29 +0000 (UTC), mac <acolvin@efunct.com>
wrote:

>>>>> I feel like I'm sending a kid fresh off the train from the city into the
>>>>> deep dark woods with a rusty shotgun and a printed sheet describing the
>>>>> differences between a black bear and a grizzly.
>
>>>> Is there really a difference between them w.r.t. the kid?
>
>>> Either bear will chase you up a tree.  If it then climbs the tree and
>>> eats you, it's a grizzly.  If it pushes the tree down and eats you, it's
>>> a black bear.  That's the difference :-)
>
>Other way. Black bears climb. Brown bears (including grizzly) don't. But
>they can run 30mph. So they'll get to the tree first.
>
>Not really relevant, but I spent the night up a tree once in grizzly
>country.

There's a joke that [paraphrased] goes:

When hiking in bear country, people are advised to wear strings of
bells to warn bears of their approach and to carry pepper spray in
case the bears get too close.  They also should learn to identify
local bears by the remnants left in their scat.  Black bear scat
contains little bits of twigs and berries.  Grizzly bear scat smells
like pepper and contains little bells.

George

Hi Ed,

Ed Prochak <edprochak@gmail.com> wrote:
[]
>> I'm thinking at architecture level, I have no idea whether it will be a 
>> processor or an FPGA or a ton of bistable elements to perform the 
>> scheduling. What I know is the cycle has a fixed, absolute, rate and I 
>> can organize activities in order to achieve the required functionality 
>> simply allocating the needed amount of bus utilisation to each unit.
[]
> 
> Sounds to me like you are not thinking at the architecture level, but 
> at the bit, clock cycle level.

I have never mentioned neither bits nor clock rates, rather functional 
requirements (the T period for instance). I'm not sure where you see the 
implementation aspect in my wording.

[]
>> yep, and in my terminology is an algorithm in the sence of step-by-step 
>> procedure to achieve a specific result. BTW the real-time system in this 
>> case is probably sitting in an FPGA and can be a combination of an 
>> embedded processor and an FSM. Probably the processor will be programmed 
>> on bare metal, no RTOS.
> 
> An FSM is not a scheduler. (It can mimic one).
> 
> And a scheduler may be included in a RTOS but it isn't necessarily an 
> RTOS.

quoting Wikipedia (which might be wrong, I agree, yet usually provides a 
shared view about the topic): In computing, scheduling is the method by 
which threads, processes or data flows are given access to system 
resources (e.g. processor time, communications bandwidth)

an FSM may be the method to allocate access to system resources.

[]
>> I can calculate with a rather good approximation how long is needed to 
>> serve the interrupt, is a context switch *and* a bus transaction. I have 
>> more problems in verifying if I *really* understood what rate monotonic 
>> schedling is about.
> 
> I think you don't. A scheduler has nothing to do with counting clock 
> cycles, approximate or exact.

A scheduler is all about giving enough resources to accomplish a task in 
within a specified amount of *time*. If you are taking the time variable 
out of your architecture it will likely not meet your timing 
requirements.
 
[]
>> In my case I do not necessary need to implement a preempting 
>> multitasking method, but a simpler cooperative one. Transactions are 
>> deterministic and do not need to be interrupted, they can simply be 
>> 'splitted' in multiple chunks to allow /parallel/ execution.
>> 
> 
> Yes, that is the do all loop programming, not a scheduler. have fun 
> with that. Such a design is very brittle, meaning you go in the code 
> next year, make a small bug fix, and it all comes crashing down!

'do all loop programming', as you qualify it, does not necessary mean 
brittle. We've controlled mission critical equipments with that same 
philosophy while on the contrary I've seen 'small bug fixes' bringing 
down much more complex and sophisticated solutions, therefore I have the 
tendency to make it as simple as possible (but not simpler!).

Al

Hi Don,

Don Y <this@is.not.me.com> wrote:
[]
>> Unfortunately this is not quite the case. The 'S' signal is periodic 
>> but the end user of the system may tune the period /slightly/ in 
>> order to compensate clock drifts.
> 
> Wait.  Let's back up.
> 
> Do *you* synthesize the S signal?  Or, is it something that The 
> Outside World provides that you *observe*?
> 
> Is it a real "signal" (in the sense of "a wire that twitches in a 
> particular way")?  Or, is it something more abstract (like a pattern 
> in some data)?

After long discussions the customer accepted that we produce the 'S' 
signal in a very predictable way (each N local clock cycles). So no more 
need for interruption since we know when the signal will come. 

Apologize for the confusion but in this event we managed to convince the 
customer about the lack of such a need as 'resynchronization'.

With this extra information I believe that the system is much simpler 
than what was initially conceived. No need for fast reaction to events 
(like 'S'). Everything is foreseable and schedulable in a deterministic 
way.

Al

Hi Richard,

Richard Damon <Richard@damon-family.org> wrote:
> On 11/11/14, 2:40 AM, alb wrote:
>> Unfortunately this is not quite the case. The 'S' signal is periodic but
>> the end user of the system may tune the period /slightly/ in order to
>> compensate clock drifts. Therefore I cannot simply foresee when the 'S'
>> signal will come. Sure is that I do have a time window within which 'S'
>> will come.
>>
>> This uncertainty on the 'S' signal forces me to use an interrupt to
>> break the current cycle sequence and start a new one. This means that
>> the whole scheduler is working only in the specific 'S' period and when
>> it reaches the end of the sequence it won't do anything until the next
>> 'S' comes.
>>
>> Al
>>
> 
> Something seams very wrong (or simplistic) with your scheduler. Normally 
> a scheduler will see that the "highest priority" ready operation runs 
> (or and Idle task if nothing is ready). Your description of a fixed 
> pattern of operations sounds like a crude non interrupt (maybe 
> non-preemptive) base system without real scheduler.

that is probably right and after the latest evolutions with the customer 
we do not seem to see anymore anything but a 'crude non interrupt base 
system, without a scheduler'.

Yet activities need to be 'scheduled' in order to meet timing 
constraints, so even if the scheduler does not correspond to what 
commonly might be referred as a scheduler, I still need a schedule to be 
listed and implemented.

A scheduler is method of assigning resources, nothing more.

> In your case, it sounds like the response to S needs a fast response, so 
> the operation that response to it needs a high priority. When S occurs, 
> lower priority tasks will be put aside for a bit to allow this operation 
> to process, and when it is done, they will be resumed.

As mentioned elsewhere in this thread the need for S to be asynchronous 
has disappeared, therefore I can deterministically anticipate how much 
time I have left before the S will come and prepare all the activities 
in order to meet performances.

Al

On 2014-11-17, George Neuner <gneuner2@comcast.net> wrote:

> When hiking in bear country, people are advised to wear strings of
> bells to warn bears of their approach and to carry pepper spray in
> case the bears get too close.  They also should learn to identify
> local bears by the remnants left in their scat.  Black bear scat
> contains little bits of twigs and berries.  Grizzly bear scat smells
> like pepper and contains little bells.

Many years ago, when driving into Banff national park up by Lake
Louise in Alberta, they were handing out little brochures about bears.

In one section it described what you do when attacked by a bear, and
it said something like this:

  If attacked by a black bear: you curl up in a ball and pull your
  coat or backpack up high on your back to protect the back of your
  neck, and then you wait until the bear stops batting you around and
  leaves.

  If attacked by a grizzly bear: you die.

  Here's how to avoid getting attacked by a grizzly bear: ...

-- 
Grant Edwards               grant.b.edwards        Yow! I need to discuss
                                  at               BUY-BACK PROVISIONS
                              gmail.com            with at least six studio
                                                   SLEAZEBALLS!!