Björn, thanks for the explanation.<br><br>I've been studying the overhead accounting approach in Devi's thesis. I have some questions.<br><br>1) There are four types of overhead mentioned there. The three that doesn't depend on the application are scheduling, context-switching and tick overheads.<br>
<br>I've been comparing them with ft_tools overheads. "Plugin" overheads are completely included in their counterparts, right? So we don't use them.<br><br>Scheduling = SCHED + SCHED2<br>Context-Switching = CXS<br>
Tick = TICK<br><br>Though the text doesn't deal with release overheads, is it ok to add them directly to the WCET? Releases only happen once per job.<br><br>T.e = T.e(b) + oh_release(p-EDF) + 2 · oh_sch(p-EDF) + ...<br>
<br><br>2) Scheduling and release overheads depend on the number of elements in the queues, and therefore on the task set being scheduled. When we talk about oh_sch(p-EDF), is it the maximum scheduling overhead for all task sets analyzed in the experiment? Or do we consider the maximum overhead for each task set separately?<br>
<br>Thanks,<br>Felipe<br><br>2012/2/19 Björn Brandenburg <span dir="ltr"><<a href="mailto:bbb@mpi-sws.org" target="_blank">bbb@mpi-sws.org</a>></span><br>
<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><br>
On Feb 17, 2012, at 6:28 PM, Felipe Cerqueira wrote:<br>
<br>
> Hmm... The overhead costs obtained from ft_tools are not 100% exact because of the unpredictabilities of the system, but at least the approach doesn't depend on scheduling decisions, right? What I was trying to do is much less reliable.<br>
<br>
</div>Any approach relying on *measured* overheads is not truly safe. To get absolute certainty, you need to analytically derive worst-case execution time (WCET) bounds.<br>
<br>
On x86, this is essentially infeasible, for several reasons.<br>
<br>
1) The required processor documentation is not available (you can't derive an exact processor model for the WCET analysis).<br>
<br>
2) Existing x86 processors are highly unpredictable and tuned towards good average-case throughput at the expense of worst-case delays.<br>
<br>
3) The processor interconnects used in x86 multicores are highly unpredictable (and also not openly documented).<br>
<br>
Even if these obstacles would be overcome somehow, Linux (and hence LITMUS^RT) is not well suited to WCET analysis since it uses unbounded loops, copious amounts of function pointers, etc.<br>
<br>
Therefore, some compromises have to be made both when working with any RTOS on x86 and when working with Linux on any platform.<br>
<br>
Does this mean that schedulability analysis and overhead accounting is useless? Not at all.<br>
<br>
With property WCET analysis, you get the following guarantee if a task set passes a schedulability test.<br>
<br>
[1] "hardware does not fail" && "processor model correct" && "WCET analysis correct" => "no deadlines will be missed"<br>
<br>
If instead you use measured overheads and measured execution times, you get the following property.<br>
<br>
[2] "hardware does not fail" && "actual WCET does not exceed assumed/measured WCET" && "actual overheads do not exceed assumed/measured WCET" => "no deadlines will be missed"<br>
<br>
While [2] is not as strong as [1], it is still a lot stronger than what simply running and observing the system for X time units (e.g., doing a test run for 24 hours), which is the following:<br>
<br>
[3] "hardware does not fail" && "actual WCET does not exceed WCET during test run" && "actual overheads do not exceed overheads as they occurred during test run" && "actual arrival sequence is not 'more difficult to schedule' than the one that occurred during the test run" => "no deadlines will be missed"<br>
<br>
The key difference is that [2] holds true for *any* arrival sequence and *any* combination of overheads within the assumed limits, whereas [3] only applies to a particular execution sequence and a particular combination of overheads, which may or may not be representative of the worst case. I think that makes a huge difference in the degree of "trustworthiness" achieved by the final system. It's not perfect, but in my opinion it's a whole lot better than the "ship it if it didn't crash during testing" approach.<br>
<br>
Note that [2] can be made more resilient in practice by assuming higher WCETs and overheads than measured, that is, it is reasonable to add some "engineering margin" to measurements in practical systems.<br>
<br>
Sorry for the long reply, but I hope it provides some context for LITMUS^RT is and what it is aimed at.<br>
<br>
Cheers,<br>
Björn<br>
<br>
PS: I've also touched on this topic on pages 161-164 in <a href="http://www.cs.unc.edu/%7Ebbb/diss/brandenburg-diss.pdf" target="_blank">http://www.cs.unc.edu/~bbb/diss/brandenburg-diss.pdf</a>.<br>
<div><div><br>
<br>
_______________________________________________<br>
litmus-dev mailing list<br>
<a href="mailto:litmus-dev@lists.litmus-rt.org" target="_blank">litmus-dev@lists.litmus-rt.org</a><br>
<a href="https://lists.litmus-rt.org/listinfo/litmus-dev" target="_blank">https://lists.litmus-rt.org/listinfo/litmus-dev</a><br>
</div></div></blockquote></div><br>