Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 72
Текст из файла (страница 72)
The design of WECT models and the analytic analysis of sub-problems (e.g., themaximum execution time analysis of the source program) such that an effectiveset of test cases biased towards the worst-case execution time can be generatedautomatically.3.
The controlled measurement of sub-systems (tasks, operating system servicetimes) to gather experimental WCET data for the calibration of the WCETmodels.4. The implementation of an anytime algorithm, where only a bound for WCET ofthe root segment must be provided.5. The extensive testing of the complete implementation to validate the assumptions and to measure the safety margin between the assumed WCET and theactual measured execution times.The state of current practice is not satisfactory, because in many cases theminimal and maximum execution times that are observed during testing are taken24810 Real-Time Schedulingfor the BCET and WCET.
Such an observed upper bound cannot be considered aguaranteed upper bound. It is to be hoped that in the future the WCET problem willget easier, provided simple processors with private scratchpad memory will formthe components of multi-processor systems-on-chips (MPSoCs).10.3Static SchedulingIn static or pre-runtime scheduling, a feasible schedule of a set of tasks is calculatedoff-line. The schedule must guarantee all deadlines, considering the resource,precedence, and synchronization requirements of all tasks. The construction ofsuch a schedule can be considered as a constructive sufficient schedulability test.The precedence relations between the tasks executing in the different nodes can bedepicted in the form of a precedence graph (Fig. 10.5).10.3.1 Static Scheduling Viewed as a SearchStatic scheduling is based on strong regularity assumptions about the points in timewhen future service requests will be honored.
Although the occurrence of externalevents that demand service is not under the control of the computer system, therecurring points in time when these events will be serviced can be established apriori by selecting an appropriate sampling rate for each class of events. Duringsystem design, it must be ascertained that the sum of the maximum delay times untila request is recognized by the system plus the maximum transaction response timeis smaller than the specified service deadline.The Role of Time.
A static schedule is a periodic time-triggered schedule. Thetimeline is partitioned into a sequence of basic granules, the basic cycle time. Thereis only one interrupt in the system: the periodic clock interrupt denoting the start ofa new basic granule. In a distributed system, this clock interrupt must be globallystimulusT0T1T2M1M2T3T4T5T6node AT7Fig.
10.5 Example of aprecedence graph of adistributed task set [Foh94]node Bresponse10.3 Static Scheduling249synchronized to a precision that is much better than the duration of a basic granule.Every transaction is periodic, its period being a multiple of the basic granule. Theleast common multiple of all transaction periods is the schedule period. At compiletime, the scheduling decision for every point of the schedule period must bedetermined and stored in a dispatcher table for the operating system for the fullschedule period. At run time, the preplanned decision is executed by the dispatcherafter every clock interrupt.Example: If the periods of all tasks are harmonic, e.g., either a positive or negative powerof two of the full second, the schedule period is equal to the period of the task with thelongest period.Static scheduling can be applied to a single processor, to a multiple-processor, or toa distributed system.
In addition to preplanning the resource usage in all nodes, theaccess to the communication medium must also be preplanned in distributedsystems. It is known that finding an optimal schedule in a distributed system is inalmost all realistic scenarios an NP-complete problem, i.e., computationally intractable. But even a non-optimal solution is sufficient if it meets all deadlines.The Search Tree.
The solution to the scheduling problem can be seen as finding apath, a feasible schedule, in a search tree by applying a search strategy. An exampleof a simple search tree for the precedence graph of Fig. 10.5 is shown in Fig. 10.6.Every level of the search tree corresponds to one unit of time. The depth of thesearch tree corresponds to the period of the schedule. The search starts with anempty schedule at the root node of this tree. The outward edges of a node point tothe possible alternatives that exist at this point of the search.
A path from the rootnode to a particular node at level n records the sequence of scheduling decisionsthat have been made up to time-point n. Each path to a leaf node describes acomplete schedule. It is the goal of the search to find a complete schedule thatobserves all precedence and mutual exclusion constraints, and which completesbefore the deadline.
From Fig. 10.6, it can be seen that the right branch of the searchtree will lead to a shorter overall execution time than the left branches.A Heuristic Function Guiding the Search. To improve the efficiency of the search,it is necessary to guide the search by some heuristic function. Such a heuristicfunction can be composed of two terms, the actual cost of the path encountered untilthe present node in the search tree, i.e., the present point in the schedule, and theestimated cost until a goal node. Fohler [Foh94] proposes a heuristic function thatestimates the time needed to complete the precedence graph, called TUR (time until1T6T7T6T5T7T5T7T2M1&T3M2&T4T2M1&T1T3&T4M2&T63456T0Fig.
10.6 A search tree forthe precedence graph ofFig. 10.5T5T12time slot7825010 Real-Time Schedulingresponse). A lower bound of the TUR can be derived by summing up the maximumexecution times of all tasks and message exchanges between the current task andthe last task in the precedence graph, assuming true parallelism constrained by thecompetition for CPU resources of tasks that reside at the same node. If thisnecessary TUR is not short enough to complete the precedence graph on time, allthe branches from the current node can be pruned and the search must backtrack.10.3.2 Increasing the Flexibility in Static SchedulesOne of the weaknesses of static scheduling is the assumption of strictly periodic tasks.Although the majority of tasks in hard real-time applications is periodic, there are alsosporadic service requests that have hard deadline requirements. An example of such arequest is an emergency stop of a machine.
Hopefully it will never be requested – themean time between emergency stops can be very long. However, if an emergency stopis requested, it must be serviced within a small specified time interval.The following three methods increase the flexibility of static scheduling:1. The transformation of sporadic requests into periodic requests2. The introduction of a sporadic server task3. The execution of mode changesTransformation of a Sporadic Request to a Periodic Request. While the futurerequest times of a periodic task are known a priori, only the minimum inter-arrivaltime of a sporadic task is known in advance. The actual points in time when asporadic task must be serviced are not known ahead of the request event.
Thislimited information makes it difficult to schedule a sporadic request before runtime. The most demanding sporadic requests are those that have a short responsetime, i.e., the corresponding service task has a low latency.It is possible to find solutions to the scheduling problem if an independent sporadictask has a laxity l. One such solution, proposed by Mok [Mok93, p.
44], is thereplacement of a sporadic task T by a pseudo-periodic task T0 as seen in Table 10.1.This transformation guarantees that the sporadic task will always meet itsdeadline if the pseudo-periodic task can be scheduled. The pseudo-periodic taskcan be scheduled statically. A sporadic task with a short latency will continuouslydemand a substantial fraction of the processing resources to guarantee its deadline,although it might request service very infrequently.Sporadic Server Task. To reduce the large resource requirements of apseudo-periodic task with a long inter-arrival time (period) but a short latency,Table 10.1 Parameters of the pseudo-periodic taskParameterSporadic taskComputation time, ccDeadline interval, ddPeriod, ppPseudo-periodic taskc0 ¼ cd0 ¼ cp0 ¼ Min(l 1, p)10.4 Dynamic Scheduling251Sprunt et al.
[Spr89] have proposed the introduction of a periodic server task forthe service of sporadic requests. Whenever a sporadic request arrives during theperiod of the server task, it will be serviced with the high priority of the server task.The service of a sporadic request exhausts the execution time of the server. Theexecution time will be replenished after the period of the server.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
