<div dir="ltr"><div><div><div>Hello all,<br><br></div>I just make a pull request including the enhancement and a heuristic example.<br>I believe this patch is good for further use in more general real-time task models. <br>To demonstrate the differences, a heuristic example called deadlinemiss is prepared in testsuites/samples/ to show the benefit of the enhancement.<br></div><div>This enhancement only affect those timeout cases without changing any behaviour in normal cases.<br></div><div><br>However as Joel said, so far there is no standard requirements for how to deal with missed periods. <br></div><div>Maybe RMS manger can have more flexibility to decide the way it reacts.<br>I can show some academic papers as the reference if it is necessary.<br></div><div><br></div>Cheers,<br></div>Kuan-Hsun<br><div><div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2016-08-02 10:45 GMT+02:00 Kuan Hsun Chen <span dir="ltr"><<a href="mailto:kuan-hsun.chen@tu-dortmund.de" target="_blank">kuan-hsun.chen@tu-dortmund.de</a><wbr>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div><div class="gmail_extra"><div class="gmail_quote"><span>2016-08-01 19:11 GMT+02:00 Joel Sherrill <span dir="ltr"><<a href="mailto:joel@rtems.org" target="_blank">joel@rtems.org</a>></span>:<br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><p dir="ltr"></p>
<p dir="ltr">On Aug 1, 2016 1:04 PM, "Gedare Bloom" <<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>> wrote:<span><br>
><br>
> On Mon, Aug 1, 2016 at 9:49 AM, Kuan Hsun Chen<br>
> <<a href="mailto:kuan-hsun.chen@tu-dortmund.de" target="_blank">kuan-hsun.chen@tu-dortmund.de</a><wbr>> wrote:<br>
> > Hello All,<br>
> ><br>
> > I have used rate_monotonic function series to do some cycle-accuracy<br>
> > emulation quite a long time. I believe that some missing features of<br>
> > scheduling are essentially required. As I'm not aware of any discussion<br>
> > about this before, please correct me if I misunderstand.<br>
> ><br>
> > If I understand correctly, the current implementation of<br>
> > rtems_rate_monotonic_period() is explicitly assumed the implicit deadline or<br>
> > constraint deadline model that the task deadline is always less than or<br>
> > equal to the period deadline. If rtems_rate_monotonic_period() is called, it<br>
> > is the moment that either the task is finished on time or earlier than its<br>
> > period (or inactivate as the first call). If a task misses its period, the<br>
> > watchdog will mark the period as RATE_MONOTONIC_EXPIRED and update the<br>
> > deadline of watchdog.<br>
> ><br></span>
> Yes I think you understand correctly. Except, I don't think the<br>
> deadline of the watchdog is updated by the watchdog.</p>
<p dir="ltr">+1</p></blockquote></span><div>Aha yes, the deadline of watchdog is updated by _Rate_monotonic_Release_job() instead of itself.<br></div><div><div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<p dir="ltr"><span>> > However, the behavior is not correct currently. From my point of view, the<br>
> > periodic task should always release its workload on time, even it misses its<br>
> > deadline. If there are already two expired periods, the task should have two<br>
> > more remaining instances workload to execute.<br>
> > Especially if the task has arbitrary deadline or even the task is a soft<br>
> > real time task, this feature should behave correctly.<br>
> > (Soft Real Time task: If a task misses its deadline, it is still valuable to<br>
> > gather its result no matter when. If the utilization of uniprocessor is not<br>
> > 100%, the tardiness is proved to be bounded.)<br>
> ><br>
> > Here I aim at a case that the task misses its deadline with the current<br>
> > implementation.<br>
> > If a task period is time out (marked as RATE_MONOTONIC_EXPIRED), by<br>
> > referring to _Rate_monotonic_Block_while_ex<wbr>pired(), the next call of<br>
> > rtems_rate_monotonic_period() will only release one following instance and<br>
> > manipulate the task period with the calling moment + the next length of<br>
> > period. However, this way of scheduling is in fact changing the behaviour of<br>
> > a periodic task:<br>
> ><br>
> > There may be more than one instances which are postponed due to the<br>
> > preemption of higher priority tasks. Trivially release only one instance is<br>
> > not correct in the sense of scheduling.<br>
><br></span>
> I understand that counting the number of missed deadlines could be<br>
> correct for certain applications. The way to handle missed deadlines<br>
> should be a parameter of the RM manager though, since handling missed<br>
> deadlines is application specific property of how "soft" the deadlines<br>
> are.</p>
<p dir="ltr">There are no standard requirements for how to deal with missed periods. The current implementation does precisely what is required for RMS per the original paper and nothing more.</p>
<p dir="ltr">We can discuss what to do on missed periods but having academic papers to back that up would be ideal.</p></blockquote></div></div><div>I can find some collections which are more related to this requirement. (Also my emulation I did for.)<br></div><span><div></div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<p dir="ltr"><span>> > The period of expired task is shifted and unpredictable. This should be<br>
> > calculated correctly and rapidly by taking the time point of first period<br>
> > released. The deadline of watchdog in this case should be assigned with an<br>
> > absolute tick.<br>
> ><br></span>
> Yes. I would deal with this by having the watchdog timeout reprogram<br>
> itself with the next period immediately when it expires in<br>
> _Rate_monotonic_Timeout, along with incrementing the RM_Control<br>
> counter for currently missed deadlines/pending jobs. This way another<br>
> expiration indicates another deadline miss, or so the task finishes<br>
> its current job it can immediately start the next job with the correct<br>
> deadline already programmed in the watchdog.<span><br></span></p></blockquote></span><div>This is a great way. I deal with this by RM manager side. <br>I should do this inside the watchdog for more precise control.<br></div><span><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><p dir="ltr"><span>
><br>
> > I have enhanced this feature in the system by adding three additional<br>
> > counters in Rate_monotonic_Control structure and one more function to do the<br>
> > correct assignment of deadline and job release. I also prepare a heuristic<br>
> > example to demonstrate the results. I'm going to fix the case for arbitrary<br>
> > deadline later on.<br>
> ><br></span>
> By arbitrary deadline you mean explicit deadlines? I don't think this<br>
> is a common requirement, but it would be a welcome addition if the<br>
> complexity is not that great and the common case (implicit deadline)<br>
> is negligibly affected.<span><br></span></p></blockquote></span><div>The arbitrary deadline model is that the task relative deadline could be larger than its period as shown in [1-2] for example. <br>In this model, a task may have multiple ready jobs. A common assumption is that those jobs are scheduled on a First-Come-First Serve basis.<br></div><div>Therefore, the period is no longer "timeout". The deadline can only be expired by the task it belongs to.<br></div><div><br>I'm not sure how the others use RTEMS, but I make the application itself detect deadline misses with absolute tick instead of watching the status of period.<br></div><div>In some common cases, the task deadline is no more than its period so-called constraint deadline model. <br>Deadline monotonic is optimal in this model, which is similar to RMS.<br></div><div><br>I think implicit deadline case can always keep as it is, if we do it carefully. <br>As Gedare said, it might be a good way to prepare a option there in RM manager.<br></div><div>I believe having an enhanced scheduler is great to the community of RTEMS anyway.<br></div><div>So I will do this right now and evaluate the overhead from my side.<br></div><div><br>[1] Andersson etal., Scheduling Arbitrary-Deadline Sporadic Task Systems on Multiprocessors, RTSS'08<br>[2] Huang etal., <span>Response time bounds for sporadic arbitrary-deadline tasks under global fixed-priority scheduling on multiprocessors. RTNS'15<br></span></div><div><div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><p dir="ltr"><span>
><br>
> > Please let me know if this feature is sound and essential. I can patch it.<br>
> ><br></span>
> The feature seems useful for some applications, but may be not all of<br>
> them will want to have this behavior for a missed deadline.<span><br>
><br></span></p></blockquote><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><p dir="ltr"><span>
> > Best Regards,<br>
> > Kuan-Hsun<br>
> ><br>
> > --<br>
> > M.Sc. Kuan-Hsun Chen<br>
> ><br>
> > TU Dortmund<br>
> > Department of Computer Science 12<br>
> > Design Automation of Embedded Systems<br>
> > Otto-Hahn-Strasse 16, Room 102<br>
> ><br>
> > 44227 Dortmund<br>
> > Germany<br>
> ><br>
> > Phone:  <a value="+492317556124" href="tel:%2B49%20231%20755%206124" target="_blank">+49 231 755 6124</a><br>
> > Mail:   <a href="mailto:kuan-hsun.chen@tu-dortmund.de" target="_blank">kuan-hsun.chen@tu-dortmund.de</a><br>
> ><br></span><span>
> > ______________________________<wbr>_________________<br>
> > users mailing list<br>
> > <a href="mailto:users@rtems.org" target="_blank">users@rtems.org</a><br>
> > <a href="http://lists.rtems.org/mailman/listinfo/users" target="_blank">http://lists.rtems.org/mailman<wbr>/listinfo/users</a><br>
> ______________________________<wbr>_________________<br>
> users mailing list<br>
> <a href="mailto:users@rtems.org" target="_blank">users@rtems.org</a><br>
> <a href="http://lists.rtems.org/mailman/listinfo/users" target="_blank">http://lists.rtems.org/mailman<wbr>/listinfo/users</a><br></span></p>
</blockquote></div></div></div><div><div><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr">M.Sc. Kuan-Hsun Chen<br>
<br>
TU Dortmund<br>
Department of Computer Science 12<br>
Design Automation of Embedded Systems<br>
Otto-Hahn-Strasse 16, Room 102<br>
<br>
44227 Dortmund<br>
Germany<br>
<br>
Phone:  <u><span style="color:rgb(0,0,255)"><a value="+492317556124" href="tel:%2B49%20231%20755%206124" target="_blank">+49 231 755 6124</a></span></u><br>
Mail:   <a href="mailto:kuan-hsun.chen@tu-dortmund.de" target="_blank">kuan-hsun.chen@tu-dortmund.de</a><a href="mailto:kuan-hsun.chen@tu-dortmund.de" target="_blank"></a></div></div>
</div></div></div></div></div></div></div>
</blockquote></div><br><br clear="all"><br>-- <br><div data-smartmail="gmail_signature"><div dir="ltr">M.Sc. Kuan-Hsun Chen<br>
<br>
TU Dortmund<br>
Department of Computer Science 12<br>
Design Automation of Embedded Systems<br>
Otto-Hahn-Strasse 16, Room 102<br>
<br>
44227 Dortmund<br>
Germany<br>
<br>
Phone:  <u><span style="color:rgb(0,0,255)"><a href="tel:%2B49%20231%20755%206124" value="+492317556124" target="_blank">+49 231 755 6124</a></span></u><br>
Mail:   <a href="mailto:kuan-hsun.chen@tu-dortmund.de" target="_blank">kuan-hsun.chen@tu-dortmund.de</a><a href="mailto:kuan-hsun.chen@tu-dortmund.de" target="_blank"></a></div></div>
</div></div></div></div></div></div>