rate monotonic scheduler + interrupt

Hi everyone,

now that I've learned about 'rate monotonic scheduling' (see my previous 
post here: <news:cc1b52Fah05U1@mid.individual.net>) I'd like to 
understand whether or not on such algorithm I can think about plugging 
an 'interrupt' in order to start the repeated cycle.

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.

So I'm wondering whether using S as an interrupt for the scheduler can 
be a good solution or if there are any other alternatives I can think 
of.

Any pointer is appreciated.

Al

-- 
A: Because it messes up the order in which people normally read text. 
Q: Why is top-posting such a bad thing? 
A: Top-posting. 
Q: What is the most annoying thing on usenet and in e-mail?

On Mon, 10 Nov 2014 14:20:58 +0000, alb wrote:

> Hi everyone,
> 
> now that I've learned about 'rate monotonic scheduling' (see my previous
> post here: <news:cc1b52Fah05U1@mid.individual.net>) I'd like to
> understand whether or not on such algorithm I can think about plugging
> an 'interrupt' in order to start the repeated cycle.

You seem to be missing the fact that rate monotonic scheduling is a design 
procedure -- it's not some algorithm that you run in the embedded system.

Rate monotonic scheduling is how you decide whether your real-time system 
will meet its design goals.

> 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.
> 
> So I'm wondering whether using S as an interrupt for the scheduler can
> be a good solution or if there are any other alternatives I can think
> of.

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.

But, here goes:

You probably want to service that event with an interrupt.  If you knew 
how long it takes to service the event, how long it takes to service all 
the other events in your system, AND if you understood what rate monotonic 
scheduling was really about, then you could decide if your system was 
going to work when you were done.

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.

-- 

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

Hi Al,

On 11/10/2014 7:20 AM, alb wrote:
> Hi everyone,
>
> now that I've learned about 'rate monotonic scheduling' (see my previous
> post here: <news:cc1b52Fah05U1@mid.individual.net>) I'd like to
> understand whether or not on such algorithm I can think about plugging
> an 'interrupt' in order to start the repeated cycle.

<frown>  I think you are "chasing (brightly colored) butterflies".  :<
You have to decide if your application can use STATIC scheduling
(presumably, for the "bus resource") or *needs* more advanced
run-time scheduling of that resource.

 From your previous comments, it *seems* like you can do a simple (?)
schedulability analysis AT DESIGN TIME and "hard code" this into your
implementation.  No need to burn CPU cycles repeatedly verifying
that "2+3=5"!

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

> So I'm wondering whether using S as an interrupt for the scheduler can
> be a good solution or if there are any other alternatives I can think
> of.
>
> Any pointer is appreciated.

I think you are conflating too many disparate issues

Hi Tim,

Tim Wescott <seemywebsite@myfooter.really> wrote:
[]
>> now that I've learned about 'rate monotonic scheduling' (see my previous
>> post here: <news:cc1b52Fah05U1@mid.individual.net>) I'd like to
>> understand whether or not on such algorithm I can think about plugging
>> an 'interrupt' in order to start the repeated cycle.
> 
> You seem to be missing the fact that rate monotonic scheduling is a design 
> procedure -- it's not some algorithm that you run in the embedded system.

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.

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

>> 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.
>> 
>> So I'm wondering whether using S as an interrupt for the scheduler can
>> be a good solution or if there are any other alternatives I can think
>> of.
> 
> 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? Ok, even 
though I read about rate monotonic scheduling I have to admit I do not 
know anything about it more than what I read, meaning no experience to 
say if we can pull it off or not.

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.

> You probably want to service that event with an interrupt.  If you knew 
> how long it takes to service the event, how long it takes to service all 
> the other events in your system, AND if you understood what rate monotonic 
> scheduling was really about, then you could decide if your system was 
> going to work when you were done.

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.

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.

> 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

Hi Don,

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

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

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.

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.

-- 

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

On 11/10/2014 9:20 AM, alb wrote:
> Hi everyone,
>
> now that I've learned about 'rate monotonic scheduling' (see my previous
> post here: <news:cc1b52Fah05U1@mid.individual.net>) I'd like to
> understand whether or not on such algorithm I can think about plugging
> an 'interrupt' in order to start the repeated cycle.
>
> 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.
>
> So I'm wondering whether using S as an interrupt for the scheduler can
> be a good solution or if there are any other alternatives I can think
> of.
>
> Any pointer is appreciated.

The polling is pointless for another reason.  The polling would most 
likely have to be based on a timer interrupt to be accurate enough.  So 
if you are going to use an interrupt, why not the S signal?

Schedulers typically use timer based interrupts so that tasks can be 
preempted.  Are you running tasks or just calling routines from a main 
loop?

-- 

Rick

On 11/11/2014 2:40 AM, alb wrote:
> Hi Don,
>
> 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. 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.

So where exactly is the problem?  If you have a physical signal S which 
can be used as an interrupt, that sounds like the way to do it.

-- 

Rick

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.

Rate monotonic scheduling is a method where you assign the higher "rate" 
operations higher priority (rate in quotes as an infrequent, but needing 
fast response, operation is considered as a high rate, it is really the 
allowed response time that determines priority, but the overall rate 
does get into the calculation of feasability.

Rate monotonic scheduling has the advantage that every task has a static 
priority, and you can verify if you can be sure that you will meet all 
deadlines (sometimes you won't be able to prove you can when you can, 
but if the algorithm says you will, they you will as long as you feed it 
valid data).

Sometimes, when timing is tight, Rate monotonic will not only not prove 
meeting timing but also not meet the timing when some other, more 
complicated and possibly dynamic scheduling algorithm might be able to 
meet the requirements.

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.