Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 71
Текст из файла (страница 71)
Absence of dynamic data structuresThe WCET analysis concerns only the temporal properties of a program. Thetemporal characteristics of a program can be abstracted into a WCET bound forevery program statement using the known WCET bound of the basic languageconstructs. For example, the WCET bound of a conditional statementS: ifðexpÞthen S1else S2;can be abstracted asTðSÞ ¼ max ½TðexpÞ þ TðS1 Þ; TðexpÞ þ TðS2 Þwhere T(S) is the maximum execution time of statement S, with T(exp), T(S1), andT(S2) being the WCET bounds of the respective constructs.
Such a formula forreasoning about the timing behavior of a program is called a timing schema [Sha89].The WCET analysis of a program which is written in a high-level language mustdetermine which program path, i.e., which sequence of instructions, will be executedin the worst-case scenario. The longest program path is called the critical path.Because the number of program paths normally grows exponentially with the programsize, the search for the critical path can become intractable if the search is not properlyguided and the search space is not reduced by excluding infeasible paths.Compiler Analysis.
The next problem concerns the determination of the maximumexecution time of the basic language constructs of the source language under theassumption that the maximum execution times of the machine language commands10.2 Worst-Case Execution Time245are known and context independent. For this purpose, the code generation strategy ofthe compiler must be analyzed, and the timing information that is available at thesource code level must be mapped into the object code representation of the programsuch that an object-code timing analysis tool can make use of this information.Execution Time Analysis.
The next problem concerns the determination of theworst-case execution time of the commands on the target hardware. If the processorof the target hardware has fixed instruction execution times, the duration of thehardware instructions can be found in the hardware documentation and can beretrieved by an elementary table look-up. Such a simple approach does not work ifthe target hardware is a modern RISC processor with pipelined execution units andinstruction/data caches. While these architectural features result in significantperformance improvements, they also introduce a high level of unpredictability.Dependencies among instructions can cause pipeline hazards, and cache misses willlead to a significant delay of the instruction execution.
To make things worse, thesetwo effects are not independent. A significant amount of research deals with theexecution time analysis on machines with pipelines and caches. The excellentsurvey article by Wilhelm et al. [Wil08] presents the state of the art of WCETanalysis in research and industry and describes many of the tools available for thesupport of WCET analysis.Preemptive S-Tasks. If a simple task (S task) is preempted by another independenttask, e.g., a higher priority task that must service a pending interrupt, the executiontime of the S-task under consideration is extended by three terms:1. The WCET of the interrupting task (task B in Fig.
10.4)2. The WCET of the operating system required for context switching3. The time required for reloading the instruction cache and the data cache of theprocessor whenever the context of the processor is switchedWe call the sum of the worst-case delays caused by the context switch (2), andthe cache reloading (3) the Worst-Case Administrative Overhead (WCAO) of a taskpreemption. The WCAO is an unproductive administrative operating system overhead that is avoided if task preemption is forbidden.The additional delay caused by the preemption of task A by task B is the WCETof the independent task B and the sum of the two WCAOs for the two contextswitches (shaded area in Fig.
10.4). The times spent in Microarchitecture-1 andMicroarchitecture-2 are the delays caused by cache reloading. The Microarchitecture-2 time of the first context switch is part of the WCET of task B, because task BWCAOFig. 10.4 Worst-caseadministrative overhead(WCAO) of a task preemptionWCAOtask Amicroarchitecture-1operating systemmicroarchitecture-2task Bfirstcontext switchtimesecondcontext switch24610 Real-Time Schedulingis assumed to start on an empty cache.
The second context switch includes the cachereload time of task A, because in a non-preemptive system, this delay would notoccur. In many applications with modern processors, the micro-architecture delayscan be the significant terms that determine the cost of task preemption because theWCET of the interrupting task is normally quite short. The problem of WCAOanalysis in operating systems is studied in [Lv09].10.2.2 WCET of Complex TasksWe now turn to the WCET analysis of a preemptive complex task (C-task) thataccesses protected shared objects.
The WCET of such a task depends not only onbehavior of the task itself, but also on the behavior of other tasks and the operatingsystem of the node. WCET analysis of a C-task is therefore not a local problem of asingle task, but a global problem involving all the interacting tasks within a node.In addition to the delays caused by the task preemption (which was analyzed inthe previous section), an additional delay that originates from the direct interactionscaused by the intended task dependencies (mutual exclusion, precedence) must beconsidered.
In the last few years, progress has been made in coping with the directinteractions caused by the intended task dependencies – e.g., access to protectedshared objects controlled by the priority ceiling protocol [Sha94]. This topic will beinvestigated in Sect. 10.4.2 on the scheduling of dependent tasks.10.2.3 Anytime AlgorithmsIn practice, the time difference between the best-case execution time (BCET) and aguaranteed upper bound for the worst-case execution time (WCET) of a task can besubstantial. Anytime algorithms are algorithms that use this time difference toimprove the quality of the result as more execution time is provided [Chu08].Anytime algorithms consist of a root segment that calculates a first approximationof the result of sufficient quality and a periodic segment that improves the quality ofthe previously calculated result. The periodic segment is executed repeatedly untilthe deadline, i.e.
the guaranteed worst-case execution time of the root segment, isreached. Whenever the deadline occurs, the last version of the available result isdelivered to the client. When scheduling an anytime algorithm, the completion ofthe root segment of the anytime algorithm must be guaranteed in order that a resultof sufficient quality is available at this instant. The remaining time until thedeadline is used to improve this result. The WCET problem of an anytime algorithm is thus reduced to finding a guaranteed upper bound for the WCET of the rootsegment. A loose upper bound of the WCET is of no serious concern, since the slacktime between BCET and WCET is used to improve the result.10.2 Worst-Case Execution Time247Most iterative algorithms are anytime algorithms.
Anytime algorithms are usedin pattern recognition, planning, and control.An anytime algorithm should have the following properties [Zil96]:1. Measurable quality: It must be possible to measure the quality of a result.2. Monotonic: The quality of the result must be a non-decreasing function of timeand should improve with every iteration.3. Diminishing returns: The improvement of the result should get smaller as thenumber of iterations increases.4.
Interruptability: After the completion of the root segment, the algorithm can beinterrupted at any time and deliver a reasonable result.10.2.4 State of PracticeThe previous discussion shows that the analytic calculation of a reasonable upperWCET bound of an S-task which does not make use of operating system services ispossible under restricting assumptions. There are a number of tools that supportsuch an analysis [Wil08].
It requires an annotated source program that containsprogrammer-supplied application-specific information to ensure that the programterminates and a detailed model of the behavior of the hardware to achieve areasonable upper WCET bound.Bounds for the WCET of all time-critical tasks are needed in almost all hard realtime applications. This important problem is solved in practice by combining anumber of diverse techniques:1. Use of a restricted architecture that reduces the interactions among the tasks andfacilitates the a priori analysis of the control structure. The number of explicitsynchronization actions that require context switches and operating systemservices is minimized.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
