From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,cae92f92d6a1d4b1 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news3.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Niklas Holsti Newsgroups: comp.lang.ada Subject: Re: Ada.Execution_Time Date: Fri, 31 Dec 2010 01:49:16 +0200 Organization: Tidorum Ltd Message-ID: <8o4k3tFko2U1@mid.individual.net> References: <4d05e737$0$6980$9b4e6d93@newsspool4.arcor-online.net> <1wmsukf0wglz3$.odnzonrpayly.dlg@40tude.net> <6n1c5myuf2uz$.10jl3ln7il3aq.dlg@40tude.net> <8n0mgnFv2sU1@mid.individual.net> <1n3o55xjdjr9t.1u33kb75y2jfl$.dlg@40tude.net> <8n1142Fto2U1@mid.individual.net> <1o5cbm4b1l20d$.19winbma6k5qw.dlg@40tude.net> <8n4mskF7mmU1@mid.individual.net> <8nm30fF7r9U1@mid.individual.net> <8o0p0lF94rU1@mid.individual.net> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net QOtpreojg3OQrvfrJGkKXAAUUisvEKPV9VpofUk5556JJ81BXv Cancel-Lock: sha1:4jHeHf6j04uIlBWyQfKkLdttaho= User-Agent: Mozilla-Thunderbird 2.0.0.24 (X11/20100328) In-Reply-To: Xref: g2news2.google.com comp.lang.ada:17240 Date: 2010-12-31T01:49:16+02:00 List-Id: Before I answer Randy's points, below, I will try to summarise my position in this discussion. It seems that my convoluted dialog with Dmitry has not made it clear. I'm sorry that this makes for a longish post. I am not proposing or asking for new requirements on Ada.Execution_Time in RM D.14. I accept that the accuracy and other qualities of the implementation are (mostly) not specified in the RM, so Randy is right that the implementors can (mostly) just provide an interface to whatever services exist, and Dmitry is also (mostly) right when he says that Ada.Execution_Time can deliver garbage results and still satisfy the RM requirements. However, I think we all hope that, as Randy said, implementers are going to provide the best implementation that they can. Speaking of a "best" implementation implies that there is some ideal solution, perhaps not practically realizable, against which the quality of an implementation can be judged. Moreover, since the RM defines the language and is the basis on which implementors work, I would expect that the RM tries to describe this ideal solution, perhaps only through informal definitions, rationale, implementation advice, or annotations. This is what I have called the "intent of Ada.Execution_Time" and it includes such questions as the intended meaning of a CPU_Time value and what is meant by "execution time of a task". My background for this discussion and for understanding Ada.Execution_Time is real-time programming and analysis, and in particular the various forms of schedulability analysis. In this domain the theory and practice depend crucially on the execution times of tasks, usually on the worst-case execution time (WCET) but sometimes on the whole range or distribution of execution times. Moreover, the theory and practice assume that "the execution time of a task" has a physical meaning and a strong relationship to real time. For example, it is assumed (usually implicitly) that when a task is executing uninterrupted on a processor, the execution time of the task and the real time increase at the same rate -- this is more or less the definition of "execution time". Another (implicitly) assumed property is that if a processor first runs task A for X seconds of execution time, then switches to task B for Y seconds of execution time, the elapsed real time equals X + Y plus some "overhead" time for the task switch. (As a side comment, I admit that some of these assumptions are becoming dubious for complex processors where tasks can have strong interactions, for example through the cache.) I have assumed, and still mostly believe, that this concept of "execution time of a task" is the ideal or intent behind Ada.Execution_Time, and that approaching this ideal is an implementer's goal. My participation in this thread started with my objection to Dmitry's assertion that "CPU_Time has no physical meaning". I may have misunderstood Dmitry's thought, leading to a comedy of misunderstandings. Perhaps Dmitry only meant that in the absence of any accuracy requirements, CPU_Time may not have a useful physical meaning in a poor implementation of Ada.Execution_Time. I accept that, but I think that a good implementation should try to give CPU_Time the physical meaning that "execution time" has in the theory and practice of real-time systems, as closely as is practical and desired by the users of the implementation. My comments in this thread therefore show the properties that I think a good implementation of Ada.Execution_Time should have, and are not proposed as new requirements. At most they could appear as additions to the rationale, advice, or annotations for RM D.14. I measure the "goodness" of an implementation as "usefulness for implementing real-time programs". Others, perhaps Randy or Dmitry, may have other goodness measures. This thread started by a question about how Ada.Execution_Time is meant to be used. I think it is useful to discuss the properties and uses that can be expected of a good implementation, even if the RM also allows poor implementations. Randy Brukardt wrote: > "Niklas Holsti" wrote in message > news:8o0p0lF94rU1@mid.individual.net... >> I'm sure that the proposers of the package Ada.Execution_Time expected the >> implementation to use the facilities of the underlying system. But I am >> also confident that they had in mind some specific uses of the package and >> that these uses require that the values provided by Ada.Execution_Time >> have certain properties that can reasonably be expected of "execution >> time", whether or not these properties are expressly written as >> requirements in the RM. > > Probably, but quality of implementation is rarely specified in the Ada > Standard. When it is, it generally is in the form of Implementation Advice > (as opposed to hard requirements). The expectation is that implementers are > going to provide the best implementation that they can -- implementers don't > purposely build crippled or useless implementations. Moreover, that is > *more* likely when the Standard is overspecified, simply because of the need > to provide something that meets the standard. I agree. >> You put "time" in quotes, Randy. Don't you agree that there *is* a valid, >> physical concept of "the execution time of a task" that can be measured in >> units of physical time, seconds say? At least for processors that only >> execute one task at a time, and whether or not the system provides >> facilities for measuring this time? > > I'm honestly not sure. The problem is that while such a concept might > logicially exist, as a practical matter it cannot be measured outside of the > most controlled circumstances. I don't think that measurement is so difficult or that the circumstances must be so very controlled. Let's assume a single-processor system and a measurement mechanism like the "Model A" that Dmitry described. That is, we have a HW counter that is driven by a fixed frequency. For simplicity and accuracy, let's assume that the counter is driven by the CPU clock so that the counter changes are synchronized with instruction executions. I think such counters are not uncommon in current computers used in real-time systems, although they may be provided by the board and not the processor. We implement Ada.Execution_Time by making the task-switching routines and the Clock function in Ada.Execution_Time read the value of the counter to keep track of how much the counter increases while the processor is running a given task. The accumulated increase is stored in the TCB of the task when the task is not running. Randy, why do you think that this mechanism does not measure the execution time of the tasks, or a good approximation of the ideal? There are of course nice questions about exactly when in the task-switching code the counter is read and stored, and what to do with interrupts, but I think these are details that can be dismissed as in RM D.14 (11/2) by considering them implementation defined. It is true that execution times measured in that way are not exactly repeatable on today's processors, even when the task follows exactly the same execution path in each measurement, because of external perturbations (such as memory access delays due to DRAM refresh) and inter-task interferences (such as cache evictions due to interrupts or preempting tasks). But this non-repeatability is present in the ideal concept, too, and I don't expect Ada.Execution_Time.Clock to give exactly repeatable results. It should show the execution time in the current execution of the task. > Thus, that might make sense in a bare-board > Ada implementation, but not in any implementation running on top of any OS > or kernel. The task concept is not so Ada-specific. For example, I would call RTEMS a "kernel", and it has a general (not Ada-specific) service for measuring per-task execution times, implemented much as Dmitry's Model A except that the "RTC counter" may be the RTEMS interrupt-driven "clock tick" counter, not a HW counter. And what is an OS but a kernel with a large set of services, and usually running several unrelated applications / processes, not just several tasks in one application? Task-specific execution times for an OS-based application are probably less repeatable, and less useful, but that does not detract from the principle. > As such, whether the concept exists is more of an "angels on the > head of a pin" question than anything of practical importance. It is highly important for all practical uses of real-time scheduling theories and algorithms, since it is their basic assumption. Of course, some real-time programmers are of the opinion that real-time scheduling theories are of no practical importance. I am not one of them :-) >> If so, then even if Ada.Execution_Time is intended as only a window into >> these facilities, it is still intended to provide measures of the physical >> execution time of tasks, to some practical level of accuracy. > > The problem is that that "practical level of accuracy" isn't realistic. I disagree. I think execution-time measurements using Dmitry's Model A are practical and can be sufficiently accurate, especially if they use a hardware counter or RTC. > Moreover, I've always viewed such facilities as "profiling" ones -- it's the > relative magnitudes of the values that matter, not the absolute values. In > that case, the scale of the values is not particularly relevant. When profiling is used merely to identify the CPU hogs or bottlenecks, with the aim of speeding up a program, I agree that the scale is not relevant. Profiling is often used in this way for non-real-time systems. It can be done also for real-time systems, but would not help in the analysis of schedulability if the time-scale is arbitrary. If profiling is used to measure task execution times for use in schedulability analysis or even crude CPU load computations, the scale must be real time, because the reference values (deadlines, load measurement intervals) are expressed in real time. >> It has already been said, and not only by me, that Ada.Execution_Time is >> intended (among other things, perhaps) to be used for implementing task >> scheduling algorithms that depend on the accumulated execution time of the >> tasks. This is supported by the Burns and Wellings paper referenced above. >> In such algorithms I believe it is essential that the execution times are >> physical times because they are used in formulae that relate (sums of) >> execution-time spans to spans of real time. > > That would be a wrong interpretation of a algorithms, I think. (Either that, > or the algorithms themselves are heavily flawed!). The important property is > that all of the execution times have a reasonably proportional relationship > to the actual time spent executing each task (that hypothetical concept); > the absolute values shouldn't matter much I think you are wrong. The algorithms presented in the Burns and Wellings paper that I referred to implement "execution-time servers" which, as I understand them, are meant to limit the fraction of the CPU power that is given to certain groups of tasks and work as follows in outline. The CPU fraction is defined by an execution-time budget, say B seconds, that the tasks in the group jointly consume. When the budget is exhausted, the tasks in the group are either suspended or demoted to a background priority. The budget is periodically replenished (increased up to B seconds) every R seconds, with B < R for a one-processor system. The goal is thus to let this task group use at most B/R of the CPU time. In other words, that the CPU load fraction from this task group should be no more than B/R. The B part is measured in execution time (CPU_Time differences as Time_Spans) and the R part in real time. If execution time is not scaled properly, the load fraction B/R is wrong in proprtion, and the CPU time (1-B/R) left for other, perhaps more critical tasks could be too small, causing deadline misses and failures. It is essential that execution time (B) is commensurate with real time (R). The examples in the paper also show this assumption. As usual for academic papers in real-time scheduling, Burns and Wellings make no explicit assumptions about the meaning of execution time. They do mention measurement inaccuracies, but a systematic difference in scale is not considered. > (just as the exact priority values > are mostly irrelevant to scheduling decisions). The case of priority values is entirely different. I don't know of any real-time scheduling methods or analyses in which the quantitative values of priorities are important; only their relative order is important. In contrast, all real-time scheduling methods and analyses that I know of depend on the quantitative, metric, values of task execution times. Perhaps some heuristic scheduling methods like "shortest task first" are exceptions to this rule, but I don't think they are suitable for real-time systems. > Moreover, when the values > are close, one would hope that the algorithms don't change behavior much. Yes, I don't think the on-line execution-time dependent scheduling algorithms need very accurate measures of execution time. But if the time-scale is wrong by a factor of 2, say, I'm sure the algorithms will not perform as expected. Burns and Wellings say that one of the "servers" they describe may have problems with cumulative drift due to measurement errors -- similar to round-off or truncation errors -- and they propose methods to correct that. But they do not discuss scale errors, which should lead to a much larger drift. > The values would be trouble if they bore no relationship at all to the > "actual time spent executing the task", but it's hard to imagine any > real-world facility in which that was the case. I agree, but Dmitry claimed the opposite ("CPU_Time has no physical meaning") to which I objected. And indeed it seems that under some conditions the execution times measured with the Windows "quants" mechanism are zero, which would certainly inconvenience scheduling algorithms. >> The question is how much meaning should be read into ordinary words like >> "time" when used in the RM without a formal definition. >> >> If the RM were to say that L is the length of a piece of string S, >> measured in meters, and that some parts of S are colored red, some blue, >> and some parts may not be colored at all, surely we could conclude that >> the sum of the lengths in meters of the red, blue, and uncolored parts >> equals L? And that the sum of the lengths of the red and blue parts is at >> most L? And that, since we like colorful things, we hope that the length >> of the uncolored part is small? >> >> I think the case of summing task execution time spans is analogous. > > I think you are inventing things. Possibly so. RM D.14 (11/2) tries to define "the execution time of a task" by using an English phrase "... is the time spent by the system ...". I am trying to understand what this definition might mean, as a description of the ideal or intent in the minds of the authors, who certainly intended the definition to have *some* meaning for the reader. I strongly suspect that the proposers of D.14 meant "execution time" as understood in the real-time scheduling theory domain, and that they felt it unnecessary to define it or its properties more formally, partly out of habit, as those properties are implicitly assumed in academic papers, partly because any definition would have had to include messy text about measurement errors, and they did not want to specify accuracy requirements. > There is no such requirement in the standard, and that's good: I agree and I don't want to add such a requirement. > I've never seen a real system in which this has been true. I don't think it will be exactly true in a real system. I continue to think that it will be approximately true in a good implementation of Ada.Execution_Time (modulo the provision on interrupt handlers etc), and that this is necessary if Ada.Execution_Time is to be used as Burns and Wellings propose. > Even the various profilers I wrote for MS-DOS (the closest system to a bare > machine that will ever be in wide use) never had this property. I can't comment on that now, but I would be interested to hear what you tried, and what happened. >> Moreover, on a multi-process systems (an Ada program running under Windows >> or Linux, for example) some of the CPU time is spent on other processes, >> all of which would be "overhead" from the point of view of the Ada >> program. I don't think that the authors of D.14 had such systems in mind. > > I disagree, in the sense that the ARG as a whole certainly considered the > use of this facility in all environments. Aha. Well, as I said above on the question of Ada vs kernel vs OS, the package should be implementable under and OS like Windows or Linux, too. I don't think D.14 makes any attempt to exclude that, and why should it. > (I find that it would be very > valuable for profiling on Windows, for instance, even if the results only > have a weak relationship to reality). Yes, if all you want are the relative execution-time consumptions of the tasks in order to find the CPU hogs. And the quant-truncation problem may distort even the relative execution times considerably. Randy wrote in another post: > It's clear that he [Niklas] would never be happy > with a Windows implementation of Ada.Execution_Time -- too bad, > because it still can be useful. I probably would not be happy to use Windows at all for a real-time system, so my happiness with Ada.Execution_Time is perhaps moot. But it is all a question of what accuracy is required and can be provided. If I understand the description of Windows quants correctly, an implementation of Ada.Execution_Time under Windows may have tolerable accuracy if the average span of non-interrupted, non-preempted, and non-suspended execution of task is much larger than a quant, as the truncation of partially used quants then causes a relatively small error. I don't know if the scheduling methods of Windows would let one make good use the measured execution times. I have no experience of Windows programming on that level, unfortunately. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ .